Los clasificadores Naive Bayes son una técnica estadística popular de filtrado de correo electrónico . Por lo general, utilizan funciones de bolsa de palabras para identificar el correo electrónico no deseado, un enfoque comúnmente utilizado en la clasificación de texto .
Los clasificadores ingenuos de Bayes funcionan correlacionando el uso de tokens (generalmente palabras, oa veces otras cosas), con correos electrónicos no deseados y no spam y luego usan el teorema de Bayes para calcular la probabilidad de que un correo electrónico sea o no spam.
El filtrado de spam ingenuo de Bayes es una técnica básica para tratar el spam que puede adaptarse a las necesidades de correo electrónico de los usuarios individuales y proporcionar tasas bajas de detección de spam de falsos positivos que son generalmente aceptables para los usuarios. Es una de las formas más antiguas de filtrado de spam, con raíces en la década de 1990.
Historia
Los algoritmos bayesianos se utilizaron para el filtrado de correo electrónico ya en 1996. Aunque los filtros bayesianos ingenuos no se hicieron populares hasta más tarde, en 1998 se lanzaron varios programas para abordar el creciente problema del correo electrónico no deseado. [1] La primera publicación académica sobre el filtrado de spam bayesiano fue la de Sahami et al. en 1998. [2] Ese trabajo se implementó poco después en filtros comerciales de spam. [ cita requerida ] Sin embargo, en 2002 Paul Graham disminuyó considerablemente la tasa de falsos positivos, de modo que pudiera usarse por sí solo como un único filtro de spam. [3] [4]
Se han implementado variantes de la técnica básica en una serie de trabajos de investigación y productos de software comercial . [5] Muchos clientes de correo modernos implementan el filtrado de spam bayesiano. Los usuarios también pueden instalar programas de filtrado de correo electrónico independientes . Los filtros de correo electrónico del lado del servidor , como DSPAM , SpamAssassin , [6] SpamBayes , [7] Bogofilter y ASSP , utilizan técnicas de filtrado de spam Bayesiano, y la funcionalidad a veces está incrustada en el software del servidor de correo . CRM114 , a menudo citado como un filtro Bayesiano, no está diseñado para utilizar un filtro Bayes en producción, pero incluye la función ″ unigrama ″ como referencia. [8]
Proceso
Las palabras particulares tienen probabilidades particulares de aparecer en el correo electrónico no deseado y en el correo electrónico legítimo. Por ejemplo, la mayoría de los usuarios de correo electrónico encontrarán con frecuencia la palabra " Viagra " en los correos electrónicos no deseados, pero rara vez la verán en otros correos electrónicos. El filtro no conoce estas probabilidades de antemano y primero debe entrenarse para que pueda acumularlas. Para entrenar el filtro, el usuario debe indicar manualmente si un nuevo correo electrónico es spam o no. Para todas las palabras de cada correo electrónico de capacitación, el filtro ajustará las probabilidades de que cada palabra aparezca en correo no deseado o correo electrónico legítimo en su base de datos. Por ejemplo, los filtros de spam bayesianos normalmente habrán aprendido una probabilidad de spam muy alta para las palabras "Viagra" y "refinanciar", pero una probabilidad de spam muy baja para palabras que solo se ven en correos electrónicos legítimos, como los nombres de amigos y familiares.
Después del entrenamiento, las probabilidades de palabras (también conocidas como funciones de verosimilitud ) se utilizan para calcular la probabilidad de que un correo electrónico con un conjunto particular de palabras pertenezca a cualquiera de las categorías. Cada palabra en el correo electrónico contribuye a la probabilidad de spam del correo electrónico, o solo a las palabras más interesantes. Esta contribución se llama probabilidad posterior y se calcula utilizando el teorema de Bayes . Luego, la probabilidad de spam del correo electrónico se calcula sobre todas las palabras del correo electrónico, y si el total excede un cierto umbral (digamos 95%), el filtro marcará el correo electrónico como spam.
Como en cualquier otra técnica de filtrado de correo no deseado , el correo electrónico marcado como correo no deseado se puede mover automáticamente a una carpeta de correo electrónico "No deseado" o incluso eliminarse por completo. Algunos software implementan mecanismos de cuarentena que definen un período de tiempo durante el cual el usuario puede revisar la decisión del software.
La formación inicial normalmente se puede perfeccionar cuando se identifican juicios erróneos del software (falsos positivos o falsos negativos). Eso permite que el software se adapte dinámicamente a la naturaleza en constante evolución del spam.
Algunos filtros de spam combinan los resultados del filtrado de spam bayesiano y otras heurísticas (reglas predefinidas sobre el contenido, observación del sobre del mensaje, etc.), lo que da como resultado una precisión de filtrado aún mayor, a veces a costa de la adaptabilidad.
Fundamento matemático
Los filtros de correo electrónico bayesianos utilizan el teorema de Bayes . El teorema de Bayes se utiliza varias veces en el contexto del spam:
- una primera vez, calcular la probabilidad de que el mensaje sea spam, sabiendo que una determinada palabra aparece en ese mensaje;
- una segunda vez, para calcular la probabilidad de que el mensaje sea spam, teniendo en cuenta todas sus palabras (o un subconjunto relevante de ellas);
- a veces una tercera vez, para tratar con palabras raras.
Calcular la probabilidad de que un mensaje que contiene una palabra determinada sea spam
Supongamos que el mensaje sospechoso contiene la palabra " réplica ". La mayoría de las personas que están acostumbradas a recibir correos electrónicos saben que es probable que este mensaje sea spam, más precisamente una propuesta para vender copias falsificadas de marcas de relojes conocidas. El software de detección de spam, sin embargo, no "conoce" tales hechos; todo lo que puede hacer es calcular probabilidades.
La fórmula utilizada por el software para determinar eso se deriva del teorema de Bayes
dónde:
- es la probabilidad de que un mensaje sea spam, sabiendo que la palabra "réplica" está en él;
- es la probabilidad general de que un mensaje dado sea spam;
- es la probabilidad de que aparezca la palabra "réplica" en los mensajes de spam;
- es la probabilidad general de que un mensaje dado no sea spam (es "ham");
- es la probabilidad de que aparezca la palabra "réplica" en los mensajes de radioaficionados.
(Para una demostración completa, vea el teorema de Bayes # forma extendida ).
El espasmo de una palabra
Las estadísticas [9] muestran que la probabilidad actual de que cualquier mensaje sea spam es del 80%, como mínimo:
Sin embargo, la mayoría del software de detección de spam bayesiano asume que no existe una razón a priori para que un mensaje entrante sea spam en lugar de ham, y considera que ambos casos tienen probabilidades iguales del 50%: [ cita requerida ]
Se dice que los filtros que utilizan esta hipótesis "no están sesgados", lo que significa que no tienen prejuicios con respecto al correo electrónico entrante. Este supuesto permite simplificar la fórmula general para:
Esto es funcionalmente equivalente a preguntar, "¿qué porcentaje de apariciones de la palabra" réplica "aparece en los mensajes de spam?"
Esta cantidad se llama "espamicidad" (o "espamidad") de la palabra "réplica" y se puede calcular. El númeroutilizado en esta fórmula se aproxima a la frecuencia de mensajes que contienen "réplica" en los mensajes identificados como spam durante la fase de aprendizaje. Similar,se aproxima a la frecuencia de mensajes que contienen "réplica" en los mensajes identificados como radioaficionados durante la fase de aprendizaje. Para que estas aproximaciones tengan sentido, el conjunto de mensajes aprendidos debe ser lo suficientemente grande y representativo. También es aconsejable que el conjunto de mensajes aprendido se ajuste a la hipótesis del 50% sobre el reparto entre spam y ham, es decir, que los conjuntos de datos de spam y ham son del mismo tamaño. [10]
Por supuesto, determinar si un mensaje es spam o ham basándose únicamente en la presencia de la palabra "réplica" es propenso a errores, por lo que el software de spam bayesiano intenta considerar varias palabras y combinar sus espamicidades para determinar la probabilidad general de que un mensaje sea correo no deseado.
Combinando probabilidades individuales
La mayoría de los algoritmos de filtrado de spam bayesianos se basan en fórmulas que son estrictamente válidas (desde un punto de vista probabilístico) solo si las palabras presentes en el mensaje son eventos independientes . Esta condición generalmente no se cumple (por ejemplo, en lenguajes naturales como el inglés la probabilidad de encontrar un adjetivo se ve afectada por la probabilidad de tener un sustantivo), pero es una idealización útil, especialmente porque las correlaciones estadísticas entre palabras individuales generalmente no conocido. Sobre esta base, se puede derivar la siguiente fórmula del teorema de Bayes: [11]
dónde:
- es la probabilidad de que el mensaje sospechoso sea spam;
- es la probabilidad que es un spam sabiendo que contiene una primera palabra (por ejemplo, "réplica");
- es la probabilidad que es un spam sabiendo que contiene una segunda palabra (por ejemplo, "relojes");
- etc ...
- es la probabilidad que es un spam sabiendo que contiene un N º palabra (por ejemplo "casa").
Esta es la fórmula a la que hace referencia Paul Graham en su artículo de agosto de 2002 . Algunos de los primeros comentaristas afirmaron que "Graham sacó sus fórmulas de la nada", [12] pero Graham había hecho referencia a su fuente, [13] que incluía una explicación detallada de la fórmula y las idealizaciones en las que se basa.
El software de filtrado de correo no deseado basado en esta fórmula a veces se denomina clasificador de Bayes ingenuo , ya que "ingenuo" se refiere a los fuertes supuestos de independencia entre las funciones. El resultado p se compara típicamente con un umbral dado para decidir si el mensaje es spam o no. Si p es más bajo que el umbral, el mensaje se considera como probable jamón; de lo contrario, se considera probable spam.
Otra expresión de la fórmula para combinar probabilidades individuales
Por lo general, p no se calcula directamente usando la fórmula anterior debido al subdesbordamiento de punto flotante . En cambio, p se puede calcular en el dominio logarítmico reescribiendo la ecuación original de la siguiente manera:
Tomando troncos en ambos lados:
Dejar . Por lo tanto,
De ahí la fórmula alternativa para calcular la probabilidad combinada:
Lidiar con palabras raras
En el caso de que una palabra nunca se haya cumplido durante la fase de aprendizaje, tanto el numerador como el denominador son iguales a cero, tanto en la fórmula general como en la de espamicidad. El software puede decidir descartar las palabras para las que no hay información disponible.
De manera más general, las palabras que se encontraron solo unas pocas veces durante la fase de aprendizaje causan un problema, porque sería un error confiar ciegamente en la información que brindan. Una solución simple es simplemente evitar tener en cuenta palabras tan poco confiables.
Aplicando nuevamente el teorema de Bayes, y asumiendo que la clasificación entre spam y ham de los correos electrónicos que contienen una palabra determinada ("réplica") es una variable aleatoria con distribución beta , algunos programas deciden utilizar una probabilidad corregida:
dónde:
- es la probabilidad corregida de que el mensaje sea spam, sabiendo que contiene una palabra determinada;
- es la fuerza que le damos a la información de fondo sobre el spam entrante;
- es la probabilidad de que cualquier mensaje entrante sea spam;
- es el número de apariciones de esta palabra durante la fase de aprendizaje;
- es la espamicidad de esta palabra.
(Demostración: [14] )
Esta probabilidad corregida se usa en lugar de la espamicidad en la fórmula de combinación.
nuevamente se puede tomar igual a 0.5, para evitar sospechar demasiado sobre el correo electrónico entrante. 3 es un buen valor para s , lo que significa que el corpus aprendido debe contener más de 3 mensajes con esa palabra para poner más confianza en el valor de espamicidad que en el valor predeterminado [ cita requerida ] .
Esta fórmula se puede extender al caso donde n es igual a cero (y donde la espamicidad no está definida), y se evalúa en este caso como.
Otras heurísticas
Las palabras "neutrales" como "the", "a", "some" o "is" (en inglés), o sus equivalentes en otros idiomas, pueden ignorarse. De manera más general, algunos filtros de filtrado bayesianos simplemente ignoran todas las palabras que tienen una espamicidad próxima a 0.5, ya que contribuyen poco a una buena decisión. Las palabras que se tienen en cuenta son aquellas cuya espamicidad está próxima a 0.0 (signos distintivos de mensajes legítimos), o cerca de 1.0 (signos distintivos de spam). Un método puede ser, por ejemplo, mantener solo las diez palabras, en el mensaje examinado, que tienen el mayor valor absoluto | 0.5 - pI |.
Algunos productos de software tienen en cuenta el hecho de que una palabra determinada aparece varias veces en el mensaje examinado, [15] otros no.
Algunos productos de software utilizan patrones (secuencias de palabras) en lugar de palabras aisladas en lenguajes naturales. [16] Por ejemplo, con una "ventana de contexto" de cuatro palabras, calculan la espamicidad de "Viagra es bueno para", en lugar de calcular las espamicidades de "Viagra", "es", "bueno" y "para". . Este método da más sensibilidad al contexto y elimina mejor el ruido bayesiano , a expensas de una base de datos más grande.
Métodos mixtos
Hay otras formas de combinar probabilidades individuales para diferentes palabras que utilizando el enfoque "ingenuo". Estos métodos se diferencian de él en las suposiciones que hacen sobre las propiedades estadísticas de los datos de entrada. Estas diferentes hipótesis dan como resultado fórmulas radicalmente diferentes para combinar las probabilidades individuales.
Por ejemplo, asumiendo que las probabilidades individuales siguen una distribución chi-cuadrado con 2 N grados de libertad, se podría usar la fórmula:
donde C −1 es la inversa de la función chi-cuadrado .
Las probabilidades individuales también se pueden combinar con las técnicas de discriminación de Markov .
Discusión
Ventajas
Una de las principales ventajas [ cita requerida ] del filtrado de spam bayesiano es que se puede entrenar por usuario.
El spam que recibe un usuario suele estar relacionado con las actividades del usuario en línea. Por ejemplo, un usuario puede estar suscrito a un boletín en línea que el usuario considera spam. Es probable que este boletín en línea contenga palabras que son comunes a todos los boletines, como el nombre del boletín y su dirección de correo electrónico de origen. Un filtro de spam bayesiano eventualmente asignará una mayor probabilidad según los patrones específicos del usuario.
Los correos electrónicos legítimos que recibe un usuario tienden a ser diferentes. Por ejemplo, en un entorno corporativo, el nombre de la empresa y los nombres de clientes o clientes se mencionarán con frecuencia. El filtro asignará una menor probabilidad de spam a los correos electrónicos que contengan esos nombres.
Las probabilidades de palabras son únicas para cada usuario y pueden evolucionar con el tiempo con entrenamiento correctivo siempre que el filtro clasifique incorrectamente un correo electrónico. Como resultado, la precisión del filtrado de spam bayesiano después del entrenamiento suele ser superior a las reglas predefinidas.
Puede funcionar particularmente bien para evitar falsos positivos, [ cita requerida ] donde el correo electrónico legítimo se clasifica incorrectamente como spam. Por ejemplo, si el correo electrónico contiene la palabra "Nigeria", que se utiliza con frecuencia en spam de fraude de tarifas anticipadas , un filtro de reglas predefinido podría rechazarlo por completo. Un filtro bayesiano marcaría la palabra "Nigeria" como una palabra probablemente spam, pero tendría en cuenta otras palabras importantes que normalmente indican correo electrónico legítimo. Por ejemplo, el nombre de un cónyuge puede indicar claramente que el correo electrónico no es spam, lo que podría superar el uso de la palabra "Nigeria".
Desventajas
Dependiendo de la implementación, el filtrado de spam bayesiano puede ser susceptible al envenenamiento bayesiano , una técnica utilizada por los spammers en un intento de degradar la eficacia de los filtros de spam que dependen del filtrado bayesiano. Un spammer que practique el envenenamiento bayesiano enviará correos electrónicos con grandes cantidades de texto legítimo (recopilado de noticias legítimas o fuentes literarias). Las tácticas de spam incluyen la inserción de palabras inocuas aleatorias que normalmente no están asociadas con el spam, lo que reduce la puntuación de spam del correo electrónico, lo que hace que sea más probable que se escape de un filtro de spam bayesiano. Sin embargo, con (por ejemplo) el esquema de Paul Graham, solo se utilizan las probabilidades más significativas, de modo que rellenar el texto con palabras no relacionadas con el spam no afecta la probabilidad de detección de manera significativa.
Los spammers también pueden transformar las palabras que normalmente aparecen en grandes cantidades en el spam. Por ejemplo, «Viagra» se sustituirá por «Viaagra» o «V! Agra» en el mensaje de spam. El destinatario del mensaje aún puede leer las palabras modificadas, pero cada una de estas palabras se encuentra con menos frecuencia con el filtro bayesiano, lo que dificulta su proceso de aprendizaje. Por regla general, esta técnica de spam no funciona muy bien, porque las palabras derivadas acaban siendo reconocidas por el filtro al igual que las normales. [17]
Otra técnica utilizada para intentar derrotar a los filtros de spam bayesianos es reemplazar el texto con imágenes, ya sea directamente incluidas o vinculadas. Todo el texto del mensaje, o parte de él, se reemplaza por una imagen en la que se "dibuja" el mismo texto. El filtro de spam generalmente no puede analizar esta imagen, que contendría palabras sensibles como «Viagra». Sin embargo, dado que muchos clientes de correo deshabilitan la visualización de imágenes vinculadas por razones de seguridad, el spammer que envía vínculos a imágenes distantes puede llegar a menos objetivos. Además, el tamaño de una imagen en bytes es mayor que el tamaño del texto equivalente, por lo que el spammer necesita más ancho de banda para enviar mensajes directamente con imágenes. Algunos filtros se inclinan más a decidir que un mensaje es spam si tiene mayoritariamente contenido gráfico. Una solución utilizada por Google en su sistema de correo electrónico Gmail es realizar un OCR (reconocimiento óptico de caracteres) en cada imagen de tamaño mediano a grande, analizando el texto que contiene. [18] [19]
Aplicaciones generales del filtrado bayesiano
Si bien el filtrado bayesiano se usa ampliamente para identificar el correo electrónico no deseado, la técnica puede clasificar (o "agrupar") casi cualquier tipo de datos. Tiene usos en ciencia, medicina e ingeniería. Un ejemplo es un programa de clasificación de propósito general llamado AutoClass que originalmente se usó para clasificar estrellas de acuerdo con características espectrales que de otra manera serían demasiado sutiles para notar.
[20]
Ver también
- Técnicas anti-spam
- Envenenamiento bayesiano
- Filtrado de correo electrónico
- Discriminación markoviana
- Cliente de correo Mozilla Thunderbird con implementación nativa de filtros Bayes [21] [22]
Referencias
- ^ Brunton, Finn (2013). Spam: una historia oculta de Internet . Prensa del MIT . pag. 136. ISBN 9780262018876. Archivado desde el original el 23 de marzo de 2019 . Consultado el 13 de septiembre de 2017 .
- ^ M. Sahami; S. Dumais; D. Heckerman; E. Horvitz (1998). "Un enfoque bayesiano para filtrar el correo electrónico no deseado" (PDF) . Taller AAAI'98 sobre el aprendizaje para la categorización de textos. Archivado (PDF) desde el original el 26 de junio de 2013 . Consultado el 15 de agosto de 2007 .
- ^ Paul Graham (2003), Mejor filtrado bayesiano. Archivado el 21 de junio de 2010en la Wayback Machine.
- ^ Brian Livingston (2002), Paul Graham proporciona una respuesta sorprendente a los correos electrónicos no deseados. Archivado el 10 de junio de 2010 en Wayback Machine.
- ^ "Controles de correo basura" . MozillaZine. Noviembre de 2009. Archivado desde el original el 25 de octubre de 2012 . Consultado el 16 de enero de 2010 .
- ^ "Instalación" . Manuales de Ubuntu. 2010-09-18. Archivado desde el original el 29 de septiembre de 2010 . Consultado el 18 de septiembre de 2010 .
Gary Robinson f (x) y algoritmos de combinación, como se usa en SpamAssassin
- ^ "Lectura de antecedentes" . Proyecto SpamBayes. 2010-09-18. Archivado desde el original el 6 de septiembre de 2010 . Consultado el 18 de septiembre de 2010 .
Afile sus lápices, este es el trasfondo matemático (tal como es). * El documento que puso en marcha la bola: Un plan para el spam de Paul Graham. * Gary Robinson tiene un ensayo interesante que sugiere algunas mejoras al enfoque original de Graham. * Gary Robinson El artículo de Linux Journal analiza el uso de la distribución chi cuadrado.
- ^ "Copia archivada" . Archivado desde el original el 7 de octubre de 2016 . Consultado el 9 de julio de 2016 .CS1 maint: copia archivada como título ( enlace )
- ^ Dylan Mors y Dermot Harnett (2009). "Estado del spam, un informe mensual - Informe n. ° 33" (PDF) . Archivado (PDF) desde el original el 7 de octubre de 2009 . Consultado el 30 de diciembre de 2009 .
- ^ Software de proceso, introducción al filtrado bayesiano. Archivado el 6 de febrero de 2012 en la Wayback Machine.
- ^ "Combinando probabilidades" . Archivado desde el original el 18 de septiembre de 2016 . Consultado el 8 de septiembre de 2016 . en MathPages
- ^ http://mail.python.org/pipermail/python-dev/2002-August/028216.html Archivado el 4 de julio de 2006 en elcomentario de Tim Peter de Wayback Machine sobre el algoritmo utilizado por Graham
- ^ "Página web de Graham que hace referencia al artículo de MathPages para la fórmula de probabilidad utilizada en su algoritmo de spam" . Archivado desde el original el 10 de marzo de 2013 . Consultado el 22 de mayo de 2013 .
- ^ Gary Robinson (2003). "Una aproximación estadística al problema del spam" . Diario de Linux . Archivado desde el original el 22 de octubre de 2010 . Consultado el 19 de julio de 2007 .
- ^ Brian Burton (2003). "SpamProbe - Ajustes de filtrado de spam bayesiano" . Archivado desde el original el 16 de abril de 2012 . Consultado el 19 de enero de 2009 .
- ^ Jonathan A. Zdziarski (2004). "Reducción de ruido bayesiano: lógica de simetría contextual utilizando análisis de coherencia de patrones" .[ enlace muerto permanente ]
- ↑ Paul Graham (2002), A Plan for Spam Archivado el 4 de abril de 2004 en la Wayback Machine.
- ^ "Gmail utiliza la tecnología innovadora de Google para mantener el spam fuera de su bandeja de entrada" . Archivado desde el original el 13 de septiembre de 2015 . Consultado el 5 de septiembre de 2015 .
- ^ Zhu, Z .; Jia, Z; Xiao, H; Zhang, G; Liang, H .; Wang, P. (2014). Li, S ; Jin, Q; Jiang, X; Park, J (eds.). "Un Bayes de Riesgo Mínimo Modificado y su Aplicación en Spam". Apuntes de conferencias en Ingeniería Eléctrica . Dordrecht: Springer. 269 : 2155–2159. doi : 10.1007 / 978-94-007-7618-0_261 .
- ^ Androutsopoulos, Ion; Paliouras, Georgios; Karkaletsis, Vangelis; Sakkis, Georgios; Spyropoulos, Constantine D .; Stamatopoulos, Panagiotis (2000). Gallinari, P ; Rajman, M; Zaragoza, H (eds.). "Aprender a filtrar correo electrónico no deseado: una comparación de un enfoque bayesiano ingenuo y uno basado en la memoria". IV Congreso Europeo sobre Principios y Práctica del Descubrimiento del Conocimiento en Bases de Datos (PKDD-2000) . Lyon, Francia: Laboratorio de Ingeniería del Conocimiento y del Software Instituto de Informática y Telecomunicaciones Centro Nacional de Investigación Científica “Demokritos”: 1–13. arXiv : cs / 0009009 . Código Bibliográfico : 2000cs ........ 9009A .
- ^ Hristea, Florentina T. (2013). El modelo ingenuo de Bayes para la desambiguación del sentido de las palabras sin supervisión . Londres; Berlín: Springer- Verlag Heidelberg Berlín. pag. 70. ISBN 978-3-642-33692-8.
- ^ Zheng, J .; Tang, Yongchuan (2005). Mira, José; Álvarez, Jose R (eds.). "Una generalización de los Bayes ingenuos a conjuntos difusos y el diseño del clasificador Bayes ingenuo difuso". Apuntes de conferencias en Ciencias de la Computación . Berlín: Springer, Berlín, Heidelberg. 3562 : 281. doi : 10.1007 / 11499305_29 . ISBN 978-3-540-26319-7. ISSN 0302-9743 .