Filtrado de spam con método Bayes ingenuo

Técnica para filtrar correo electrónico spam

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 no deseado , un enfoque que se utiliza comúnmente en la clasificación de texto .

Los clasificadores Bayes ingenuos funcionan correlacionando el uso de tokens (normalmente palabras o, a veces, otras cosas) con correos electrónicos spam y no spam y luego utilizan el teorema de Bayes para calcular la probabilidad de que un correo electrónico sea o no spam.

El filtrado de spam Naive Bayes es una técnica básica para tratar el spam que puede adaptarse a las necesidades de correo electrónico de cada usuario y ofrecer índices bajos de detección de spam falsos positivos que, en general, son aceptables para los usuarios. Es una de las formas más antiguas de realizar el filtrado de spam, con orígenes en la década de 1990.

Historia

Los algoritmos bayesianos se empezaron a utilizar para filtrar el correo electrónico en 1996. Aunque los filtros bayesianos ingenuos no se popularizaron 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 bayesiano de spam fue la de Sahami et al. en 1998. ^[2]

Se han implementado variantes de la técnica básica en varios trabajos de investigación y productos de software comerciales. ^[3] 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 , ^[4] SpamBayes , ^[5] Bogofilter y ASSP , utilizan técnicas de filtrado de spam bayesiano, y la funcionalidad a veces está integrada en el propio software del servidor de correo . CRM114 , a menudo citado como un filtro bayesiano, no está destinado a utilizar un filtro bayesiano en producción, pero incluye la función ″unigram″ como referencia. ^[6]

Proceso

Algunas palabras tienen probabilidades particulares de aparecer en correos electrónicos no deseados y en correos electrónicos legítimos. Por ejemplo, la mayoría de los usuarios de correo electrónico encontrarán con frecuencia la palabra " Viagra " en 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 construirlas. Para entrenar al filtro, el usuario debe indicar manualmente si un correo electrónico nuevo es correo no deseado o no. Para todas las palabras en cada correo electrónico de entrenamiento, el filtro ajustará las probabilidades de que cada palabra aparezca en correos electrónicos no deseados o legítimos en su base de datos. Por ejemplo, los filtros de correo no deseado bayesianos normalmente habrán aprendido una probabilidad de correo no deseado muy alta para las palabras "Viagra" y "refinanciar", pero una probabilidad de correo no deseado 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 las 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 una de las categorías. Cada palabra del correo electrónico contribuye a la probabilidad de spam del correo electrónico, o solo las palabras más interesantes. Esta contribución se denomina 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 supera un cierto umbral (por ejemplo, el 95 %), el filtro marcará el correo electrónico como spam.

Como ocurre con cualquier otra técnica de filtrado de correo no deseado , el correo marcado como spam puede trasladarse automáticamente a la carpeta de correo no deseado o incluso eliminarse por completo. Algunos programas implementan mecanismos de cuarentena que definen un período de tiempo durante el cual el usuario puede revisar la decisión del programa.

El entrenamiento inicial suele poder perfeccionarse cuando se identifican juicios erróneos del software (falsos positivos o falsos negativos). Esto 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 , que se utiliza varias veces en el contexto del correo no deseado:

• por primera vez, para calcular la probabilidad de que el mensaje sea spam, sabiendo que una palabra dada aparece en este mensaje;
• una segunda vez, para calcular la probabilidad de que el mensaje sea spam, tomando en consideración todas sus palabras (o un subconjunto relevante de ellas);
• A veces una tercera vez, para tratar 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 correo electrónico saben que es probable que se trate de correo basura, más precisamente, una propuesta de venta de copias falsificadas de marcas conocidas de relojes. Sin embargo, el software de detección de correo basura no "conoce" tales hechos; todo lo que puede hacer es calcular probabilidades.

La fórmula utilizada por el software para determinarlo se deriva del teorema de Bayes.

${\displaystyle \Pr(S|W)={\frac {\Pr(W|S)\cdot \Pr(S)}{\Pr(W|S)\cdot \Pr(S)+\Pr(W|H)\cdot \Pr(H)}}}$

dónde:

• ${\displaystyle \Pr(S|W)}$es la probabilidad de que un mensaje sea spam, sabiendo que la palabra "réplica" está en él;
• ${\displaystyle \Pr(S)}$es la probabilidad general de que cualquier mensaje dado sea spam;
• ${\displaystyle \Pr(W|S)}$es la probabilidad de que la palabra "réplica" aparezca en los mensajes de spam;
• ${\displaystyle \Pr(H)}$es la probabilidad general de que un mensaje determinado no sea spam (sea "jamón");
• ${\displaystyle \Pr(W|H)}$es la probabilidad de que la palabra "réplica" aparezca en los mensajes de radioaficionados.

(Para una demostración completa, consulte el Teorema de Bayes # Forma extendida ).

El carácter spam de una palabra

Las estadísticas ^[7] muestran que la probabilidad actual de que cualquier mensaje sea spam es del 80%, como mínimo:

${\displaystyle \Pr(S)=0.8;\Pr(H)=0.2}$

Se dice que los filtros que utilizan esta hipótesis son "no sesgados", es decir, que no tienen prejuicios con respecto al correo electrónico entrante. Esta suposición permite simplificar la fórmula general a:

${\displaystyle \Pr(S|W)={\frac {\Pr(W|S)}{\Pr(W|S)+\Pr(W|H)}}}$

Esto es funcionalmente equivalente a preguntar: "¿qué porcentaje de ocurrencias de la palabra 'réplica' aparecen en los mensajes de spam?"

Esta cantidad se denomina "spamicidad" (o "spaminidad") de la palabra "réplica" y se puede calcular. El número utilizado en esta fórmula se aproxima a la frecuencia de los mensajes que contienen "réplica" en los mensajes identificados como spam durante la fase de aprendizaje. De manera similar, se aproxima a la frecuencia de los mensajes que contienen "réplica" en los mensajes identificados como ham 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 aprendidos se ajuste a la hipótesis del 50% sobre la repartición entre spam y ham, es decir, que los conjuntos de datos de spam y ham sean del mismo tamaño. ^[8] ${\displaystyle \Pr(W|S)}$ ${\displaystyle \Pr(W|H)}$

Por supuesto, determinar si un mensaje es spam o no 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 spamicidades para determinar la probabilidad general de que un mensaje sea spam.

Combinando probabilidades individuales

La mayoría de los algoritmos bayesianos de filtrado de spam se basan en fórmulas que son estrictamente válidas (desde un punto de vista probabilístico) sólo si las palabras presentes en el mensaje son eventos independientes . Esta condición no se cumple generalmente (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 normalmente no se conocen. Sobre esta base, se puede derivar la siguiente fórmula del teorema de Bayes:

${\displaystyle p={\frac {p_{1}p_{2}\cdots p_{N}}{p_{1}p_{2}\cdots p_{N}+(1-p_{1})(1-p_{2})\cdots (1-p_{N})}}}$

dónde:

• ${\displaystyle p}$es la probabilidad de que el mensaje sospechoso sea spam;
• ${\displaystyle p_{1}}$es la probabilidad de que aparezca la primera palabra (por ejemplo "réplica"), dado que el mensaje es spam; ${\displaystyle p(W_{1}|S)}$
• ${\displaystyle p_{2}}$es la probabilidad de que aparezca la segunda palabra (por ejemplo "relojes"), dado que el mensaje es spam; ${\displaystyle p(W_{2}|S)}$
• etc...

El software de filtrado de spam basado en esta fórmula a veces se denomina clasificador bayesiano ingenuo , ya que "ingenuo" se refiere a los supuestos de independencia fuertes entre las características. El resultado p se compara normalmente con un umbral determinado para decidir si el mensaje es spam o no. Si p es inferior al umbral, el mensaje se considera probablemente spam; de lo contrario, se considera probablemente spam.

Otra expresión de la fórmula para combinar probabilidades individuales

Por lo general , p no se calcula directamente con la fórmula anterior debido al desbordamiento de coma flotante . En cambio, p se puede calcular en el dominio logarítmico reescribiendo la ecuación original de la siguiente manera:

${\displaystyle {\frac {1}{p}}-1={\frac {(1-p_{1})(1-p_{2})\dots (1-p_{N})}{p_{1}p_{2}\dots p_{N}}}}$

Tomando registros de ambos lados:

${\displaystyle \ln \left({\frac {1}{p}}-1\right)=\sum _{i=1}^{N}\left[\ln(1-p_{i})-\ln p_{i}\right]}$

Sea . Por lo tanto , ${\displaystyle \eta =\sum _{i=1}^{N}\left[\ln(1-p_{i})-\ln p_{i}\right]}$

${\displaystyle {\frac {1}{p}}-1=e^{\eta }}$

De ahí la fórmula alternativa para calcular la probabilidad combinada:

${\displaystyle p={\frac {1}{1+e^{\eta }}}}$

Cómo manejar palabras raras

En el caso de que una palabra no haya sido encontrada durante la fase de aprendizaje, tanto el numerador como el denominador son iguales a cero, tanto en la fórmula general como en la fórmula de spamicidad. El software puede decidir descartar aquellas palabras para las que no hay información disponible.

En términos más generales, las palabras que se encuentran pocas veces durante la fase de aprendizaje causan un problema, porque sería un error confiar ciegamente en la información que proporcionan. Una solución sencilla es simplemente evitar tener en cuenta también esas palabras poco fiables.

Aplicando de nuevo el teorema de Bayes, y asumiendo que la clasificación entre spam y ham de los correos que contienen una determinada palabra ("réplica") es una variable aleatoria con distribución beta , algunos programas deciden utilizar una probabilidad corregida:

${\displaystyle \Pr '(S|W)={\frac {s\cdot \Pr(S)+n\cdot \Pr(S|W)}{s+n}}}$

dónde:

• ${\displaystyle \Pr '(S|W)}$es la probabilidad corregida de que el mensaje sea spam, sabiendo que contiene una palabra determinada;
• ${\displaystyle s}$es la fuerza que le damos a la información de fondo sobre el spam entrante;
• ${\displaystyle \Pr(S)}$es la probabilidad de que cualquier mensaje entrante sea spam;
• ${\displaystyle n}$es el número de ocurrencias de esta palabra durante la fase de aprendizaje;
• ${\displaystyle \Pr(S|W)}$es la spamicidad de esta palabra.

(Demostración: ^[9] )

Esta probabilidad corregida se utiliza en lugar de la spamicidad en la fórmula de combinación.

Esta fórmula se puede extender al caso donde n es igual a cero (y donde la spamicidad no está definida), y evalúa en este caso como . ${\displaystyle Pr(S)}$

Otras heurísticas

Las palabras "neutrales" como "the", "a", "some", o "is" (en inglés), o sus equivalentes en otros idiomas, pueden ignorarse. Estas también se conocen como Stop words (palabras vacías ) . De manera más general, algunos filtros bayesianos simplemente ignoran todas las palabras que tienen una spamicidad próxima a 0,5, ya que contribuyen poco a una buena decisión. Las palabras que se toman en consideración son aquellas cuya spamicidad está próxima a 0,0 (signos distintivos de mensajes legítimos), o próxima a 1,0 (signos distintivos de spam). Un método puede ser, por ejemplo, mantener solo aquellas diez palabras, en el mensaje examinado, que tengan 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, ^[10] otros no.

Algunos productos de software utilizan patrones (secuencias de palabras) en lugar de palabras aisladas de lenguajes naturales. ^[11] 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 brinda más sensibilidad al contexto y elimina mejor el ruido bayesiano, a expensas de una base de datos más grande.

Métodos mixtos

Existen otras formas de combinar probabilidades individuales para distintas palabras que no sean el método "ingenuo". Estos métodos difieren de éste 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, suponiendo que las probabilidades individuales siguen una distribución de chi-cuadrado con 2 N grados de libertad, se podría utilizar la fórmula:

${\displaystyle p=C^{-1}(-2\ln(p_{1}p_{2}\cdots p_{N}),2N)\,}$

donde C ⁻¹ es la inversa de la función chi-cuadrado .

Las probabilidades individuales también pueden combinarse con las técnicas de discriminación markoviana .

Discusión

Ventajas

El correo basura que recibe un usuario suele estar relacionado con sus actividades en línea. Por ejemplo, es posible que un usuario se haya suscrito a un boletín informativo en línea que considere correo basura. Es probable que este boletín contenga palabras comunes a todos los boletines, como el nombre del boletín y la dirección de correo electrónico de origen. Un filtro de correo basura bayesiano asignará una probabilidad más alta en función de 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 los clientes se mencionarán con frecuencia. El filtro asignará una probabilidad menor de spam a los correos electrónicos que contengan esos nombres.

Las probabilidades de las palabras son exclusivas de cada usuario y pueden evolucionar con el tiempo mediante un entrenamiento correctivo cada vez que el filtro clasifica 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.

Desventajas

Dependiendo de la implementación, el filtrado bayesiano de spam 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 se basan en el filtrado bayesiano. Un spammer que practica 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 los spammers incluyen la inserción de palabras inocuas al azar que normalmente no se asocian con el spam, lo que disminuye la puntuación de spam del correo electrónico, lo que hace que sea más probable que pase por 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 significativamente la probabilidad de detección.

Las palabras que normalmente aparecen en grandes cantidades en el correo basura también pueden ser transformadas por los spammers. Por ejemplo, «Viagra» se sustituiría por «Viaagra» o «V!agra» en el mensaje basura. El destinatario del mensaje puede seguir leyendo las palabras modificadas, pero el filtro bayesiano encuentra cada una de ellas con menos frecuencia, 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 igual que las normales. ^[12]

Otra técnica utilizada para intentar vencer a los filtros de spam bayesianos es reemplazar el texto con imágenes, ya sea directamente incluidas o enlazadas. El texto completo del mensaje, o parte de él, se reemplaza con una imagen donde se "dibuja" el mismo texto. El filtro de spam normalmente no puede analizar esta imagen, que contendría palabras sensibles como "Viagra". Sin embargo, dado que muchos clientes de correo desactivan la visualización de imágenes enlazadas por razones de seguridad, el spammer que envía enlaces a imágenes lejanas 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 que incluyan imágenes directamente. Algunos filtros son más propensos a decidir que un mensaje es spam si tiene principalmente 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. ^{[13] [14]}

Aplicaciones generales del filtrado bayesiano

Aunque el filtrado bayesiano se utiliza ampliamente para identificar correo basura, la técnica puede clasificar (o "agrupar") casi cualquier tipo de datos. Tiene aplicaciones en ciencia, medicina e ingeniería. Un ejemplo es un programa de clasificación de propósito general llamado AutoClass que se utilizó originalmente para clasificar estrellas según características espectrales que de otro modo serían demasiado sutiles para notarlas. ^[15]

Véase también

• Técnicas antispam
• Envenenamiento bayesiano
• Filtrado de correo electrónico
• Discriminación markoviana
• Cliente de correo Mozilla Thunderbird con implementación nativa de filtros Bayes ^{[16] [17]}

Referencias

1. Brunton, Finn (2013). Spam: una historia en la sombra de Internet. MIT Press . p. 136. ISBN 9780262018876Archivado desde el original el 23 de marzo de 2019. Consultado el 13 de septiembre de 2017 .
2. M. Sahami; S. Dumais; D. Heckerman; E. Horvitz (1998). "Un enfoque bayesiano para filtrar el correo basura" (PDF) . Taller AAAI'98 sobre aprendizaje para la categorización de textos. Archivado (PDF) desde el original el 27 de septiembre de 2007. Consultado el 15 de agosto de 2007 .
3. "Controles de correo basura". MozillaZine. Noviembre de 2009. Archivado desde el original el 23 de octubre de 2012. Consultado el 16 de enero de 2010 .
4. "Instalación". Manuales de Ubuntu. 18 de septiembre de 2010. Archivado desde el original el 29 de septiembre de 2010. Consultado el 18 de septiembre de 2010. Algoritmos f(x) y de combinación de Gary Robinson, tal como se utilizan en SpamAssassin
5. "Lectura de fondo". Proyecto SpamBayes. 18 de septiembre de 2010. 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 artículo que dio inicio a la situación: A Plan for Spam de Paul Graham.* Gary Robinson tiene un ensayo interesante que sugiere algunas mejoras al enfoque original de Graham.* El artículo de Gary Robinson en Linux Journal analiza el uso de la distribución de chi cuadrado.
6. "Copia archivada". Archivado desde el original el 7 de octubre de 2016. Consultado el 9 de julio de 2016 .{{cite web}}: CS1 maint: archived copy as title (link)
7. Dylan Mors y Dermot Harnett (2009). "State of Spam, a Monthly Report - Report #33" (PDF) . Archivado desde el original (PDF) el 2009-10-07 . Consultado el 2009-12-30 .
8. Software de procesos, Introducción al filtrado bayesiano Archivado el 6 de febrero de 2012 en Wayback Machine
9. Gary Robinson (2003). "Un enfoque estadístico del problema del spam". Linux Journal . Archivado desde el original el 22 de octubre de 2010. Consultado el 19 de julio de 2007 .
10. Brian Burton (2003). "SpamProbe - Ajustes del filtrado de spam bayesiano". Archivado desde el original el 1 de marzo de 2012. Consultado el 19 de enero de 2009 .
11. Jonathan A. Zdziarski (2004). "Reducción de ruido bayesiano: lógica de simetría contextual que utiliza análisis de consistencia de patrones".^{[ enlace muerto permanente ]}
12. Paul Graham (2002), Un plan para el spam Archivado el 4 de abril de 2004 en Wayback Machine.
13. "Gmail utiliza la innovadora tecnología de Google para mantener el spam fuera de tu bandeja de entrada". Archivado desde el original el 13 de septiembre de 2015. Consultado el 5 de septiembre de 2015 .
14. 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 el spam". Notas de clase en ingeniería eléctrica . 269 . Dordrecht: Springer: 2155–2159. doi :10.1007/978-94-007-7618-0_261.
15. 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". 4.ª Conferencia Europea sobre Principios y Prácticas del Descubrimiento de Conocimiento en Bases de Datos (PKDD-2000) . Lyon, Francia: Laboratorio de Ingeniería de Software y Conocimiento Instituto de Informática y Telecomunicaciones Centro Nacional de Investigaciones Científicas “Demokritos”: 1–13. arXiv : cs/0009009 . Código Bibliográfico :2000cs........9009A.
16. Hristea, Florentina T. (2013). El modelo bayesiano ingenuo para la desambiguación no supervisada del sentido de las palabras . Londres; Berlín: Springer- Verlag Heidelberg Berlin. p. 70. ISBN 978-3-642-33692-8.
17. Zheng, J.; Tang, Yongchuan (2005). "Una generalización del Bayes ingenuo a conjuntos difusos y el diseño del clasificador Bayes ingenuo difuso". En Mira, Jose; Álvarez, Jose R (eds.). Aplicaciones de la inteligencia artificial y la ingeniería del conocimiento: un enfoque bioinspirado . Lecture Notes in Computer Science. Vol. 3562. Berlín: Springer, Berlín, Heidelberg. p. 281. doi :10.1007/11499305_29. ISBN . 978-3-540-26319-7. ISSN  0302-9743.