Filtrado bayesiano de spam

Los clasificadores Naive Bayes son populares estadísticas técnicas de filtrado de email. Se suelen utilizar un conjunto de palabras características para identificar los correos basura, un enfoque común en la clasificación de textos.

El texto que sigue es una traducción defectuosa.

Los clasificadores Naive Bayes trabajan correlacionandos a el uso de tokens (por lo general palabras o algunas veces otras cosas), con mensajes de correos electrónicos que no son correo basura y otros que sí lo son. Utilizando luego el Teorema de Bayes para calcular la probabilidad de que un correo electrónico es o no es correo basura.

El filtrado de correo basura bayesiano es una técnica de línea de base para tratar con el correo basura, se puede adaptar a las necesidades de correo electrónico de los usuarios individuales y dar pocos índices de falsos positivos en la detección de correo basura, que son generalmente aceptables para los usuarios. Es una de las formas más antiguas de hacer filtrado de correo basura, con raíces en la década de 1990.

Historia

El primer programa de filtrado de correo conocido por utilizar un clasificador de Naive Bayes era el programa iFile de Jason Rennie, lanzado en 1996. El programa fue utilizado para ordenar el correo dentro de las carpetas.^[1] La primera publicación académica sobre filtro bayesiano fue por Sahami et al. en 1998.^[2] Ese trabajo se desplegó poco después en filtros comerciales de correo basura. ^{[cita requerida]} Sin embargo, en 2002 Paul Graham disminuyó en gran medida la tasa de falsos positivos, por lo que podría ser utilizado por sí mismo como un solo filtro de correo basura.^[3][4]

Las variantes de la técnica básica se han aplicado en una serie de trabajos de investigación y de software comerciales de productos.^[5] Muchos clientes de correo modernos tienen implementado el filtrado de correo basura bayesiano. Los usuarios también pueden instalar diferentes programas de filtrado para email. Por parte de los servidores existen filtros de correo electrónico tales como: CRM114, correo basura, correo basuraAssassin,^[6] correo basuraBayes,^[7] Bogofilter and Anti-correo basura SMTP Proxy, que hacen uso de técnicas de filtrado de correo basura bayesiano, y la funcionalidad es a veces embebida dentro del servidor de correo del propio software.

Proceso

Palabras particulares tienen determinadas probabilidades de ocurrir en el correo electrónico, correo basura y en el correo electrónico legítimo. Por ejemplo, la mayoría de los usuarios de correo electrónico con frecuencia se encontrará con la palabra "Viagra" en el correo electrónico, correo basura, pero rara vez verlo en otro correo electrónico. El filtro no sabe estas probabilidades de antemano, y debe primero ser entrenado para que pueda aprender. Para entrenar el filtro, el usuario debe indicar manualmente si un nuevo correo electrónico es correo basura o no. Las palabras de los correos entrantes serán guardadas en la base de datos del filtro con una probabilidad que será ajustada según su aparición o no en el correo de correo basura. Por ejemplo, los filtros bayesianos de correo basura normalmente habrán aprendido una muy alta probabilidad de correo basura para las palabras "Viagra" y "refinanciar", pero una probabilidad muy baja de correo basura para las palabras que se ven solo en el correo electrónico legítimo, como los nombres de amigos y miembros de la familia.

Después del entrenamiento, las probabilidades de las palabras (también conocida como funciones de verosimilitud) se utilizan para calcular la probabilidad de que un correo electrónico con un determinado conjunto de palabras pertenece a una u otra categoría. Cada palabra en el correo electrónico contribuye a la probabilidad de que este correo sea correo basura, o solo las palabras más interesantes. Esta contribución se llama la probabilidad posterior y se calcula utilizando el Teorema de Bayes. Entonces, la probabilidad de correo basura se calcula sobre todas las palabras en el correo electrónico, y si el total supera un determinado umbral (digamos 95%), el filtro marcará el correo electrónico como correo basura.

Al igual que en cualquiera otra técnica de filtrado de correo basura el correo electrónico marcado como correo basura, se puede mover de forma automática a una carpeta de correo electrónico "basura", o incluso eliminarse por completo. Algunos programas de software implementan mecanismos de cuarentena que definen un marco de tiempo durante el cual se le permite al usuario revisar la decisión del software.

El entrenamiento inicial por lo general puede ser refinado cuando los juicios erróneos del software son identificados (falsos positivos o falsos negativos). Eso permite que el software pueda adaptarse dinámicamente a la naturaleza siempre cambiante de los correos basura.

Algunos filtros de correo basura combinan los resultados del filtro bayesiano con otras heurísticas ((reglas predefinidas sobre el contenido, búsqueda específica dentro del mensaje, etc.), lo que resulta en una mayor precisión de filtrado, a veces a costa de la capacidad de adaptación.

Fundamentos matemáticos

Los filtros de correo electrónico bayesianos utilizan el Teorema de Bayes. El teorema de Bayes se utiliza varias veces en el contexto de correo basura:

• una primera vez, para calcular la probabilidad de que el mensaje es correo basura, sabiendo que una palabra dada aparece en este mensaje;
• por segunda vez, para calcular la probabilidad de que el mensaje es correo basura, teniendo en cuenta la totalidad de sus palabras (o un subconjunto relevante de ellos);
• a veces una tercera vez, para hacer frente a las palabras raras.

Cálculo de la probabilidad de que un mensaje que contiene una palabra dada es correo basura

Supongamos que el mensaje sospechoso contiene la palabra "réplica". La mayoría de las personas que están acostumbrados a recibir correos electrónicos saben que este mensaje es probable que sea un correo no deseado, más precisamente una propuesta para vender copias falsificadas de marcas conocidas de relojes. El software de detección de correos no deseados, sin embargo, no "sabe" tales hechos; todo lo que puede hacer es probabilidades de cómputo.

La fórmula utilizada por el software para determinar que se deriva del Teorema de Bayes es:

${\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 es un correo no deseado, a sabiendas de que la palabra "réplica" está en él;
• ${\displaystyle \Pr(S)}$ es la probabilidad general de que cualquier mensaje dado es correo basura;
• ${\displaystyle \Pr(W|S)}$ es la probabilidad de que la palabra "réplica" aparece en los mensajes de correo basura;
• ${\displaystyle \Pr(H)}$ es la probabilidad general de que cualquier mensaje dado no es correo basura (es "legítimo");
• ${\displaystyle \Pr(W|H)}$ es la probabilidad de que la palabra "réplica" aparece en los mensajes legítimos.

La basurabilidad de una palabra en el correo

Estadísticas recientes^[8] muestran que la probabilidad actual de cualquier mensaje sea correo basura es del 80%, como mínimo:

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

Sin embargo, la mayoría del software de detección de correo basura bayesiano hace la suposición de que no hay ninguna razón a priori para cualquier mensaje entrante sea un correo no deseado en lugar de legítimo, y considera en ambos casos tener probabilidades iguales de 50%: ^{[cita requerida]}

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

Los filtros que utilizan esta hipótesis se dice que son "no sesgados", lo que significa que no tienen prejuicios con respecto a los correos electrónicos entrantes. Este supuesto permite la simplificación de la fórmula general:

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

Esto es funcionalmente equivalente a preguntar: "¿qué porcentaje de las apariciones de la palabra" réplica "aparecen en los mensajes de correo basura?"

Esta cantidad se denomina basurabilidad (del término inglés spamicity) de la palabra "réplica", y se puede calcular. El número ${\displaystyle \Pr(W|S)}$ utilizado en esta fórmula es aproximado a la frecuencia de los mensajes que contienen "réplica" en los mensajes identificados como correo basura durante la fase de aprendizaje. Del mismo modo, ${\displaystyle \Pr(W|H)}$ se aproxima a la frecuencia de los mensajes que contienen "réplica" en los mensajes identificados como legítimos durante la fase de aprendizaje. Por estas aproximaciones para dar sentido, el conjunto de mensajes de aprendizaje tiene que ser lo suficientemente grande y representativo. También es recomendable que el conjunto de aprendizaje de los mensajes se ajuste al 50% de hipótesis acerca de reparto entre correos basura y correos legítimos, es decir, que los conjuntos de datos de correos no deseados y el de correos legítimos sean del mismo tamaño.^[9]

Por supuesto, para determinar si un mensaje es correo basura o legítimo basado solo en la presencia de la palabra "réplica" es propenso a errores, por lo que el software de correo basura bayesiano intenta considerar varias palabras y combinar sus correo basurabilidades para determinar la probabilidad global de un mensaje de ser un correo no deseado.

Combinaciones de probabilides individuales

La mayoría de los algoritmos de filtrado de correo basura bayesiano 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 no se cumple en general (por ejemplo, en las lenguas 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, sobre todo porque las correlaciones estadísticas entre palabras individuales no suelen ser conocidas. Sobre esta base, se puede derivar la siguiente fórmula del teorema de Bayes:^[10]

${\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 es correo no deseado;
• ${\displaystyle p_{1}}$ es la probabilidad ${\displaystyle p(S|W_{1})}$ que es saber un correo basura que contiene una primera palabra (por ejemplo, "réplica");
• ${\displaystyle p_{2}}$ es la probabilidad ${\displaystyle p(S|W_{2})}$ que es saber un correo basura que contiene una segunda palabra (por ejemplo, "relojes");
• etc...
• ${\displaystyle p_{N}}$ es la probabilidad ${\displaystyle p(S|W_{N})}$ que es saber un correo basura que contiene una n-ésima palabra (por ejemplo, "casa").

Esta es la fórmula que hace referencia Paul Graham en su artículo de 2002. Algunos comentarios tempranos decían que "Graham sacó sus fórmulas de la nada",^[11] pero Graham en realidad había referenciado a su fuente,^[12] que incluye una explicación detallada de la fórmula, y las idealizaciones sobre las que él se basa.

Los software de filtrado de correo basura basados en esta fórmula se refieren a veces como un Clasificador Naive Bayes. El resultado de p se suele comparar con un umbral dado para decidir si el mensaje es correo basura o no. Si p es menor que el umbral, el mensaje se consideraba probable legítimo, de lo contrario se considera como probable correo basura.

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

Generalmente p no se calcula directamente usando la fórmula anterior debido al punto flotante underflow. En su lugar, p puede ser calculada en el dominio de logaritmos 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 los logaritmos en ambos lados:

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

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

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

De ahí que la fórmula alternativa para el cálculo de la probabilidad combinada:

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

Tratamiento para palabras raras

En el caso de que una palabra no se ha conocido durante la fase de aprendizaje, tanto el numerador como el denominador son iguales a cero, tanto en la fórmula general y en la fórmula basurabilidad del correo. El software puede decidir descartar tales palabras para las cuales no hay información disponible.

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

Aplicando de nuevo el teorema de Bayes, y suponiendo que la clasificación entre los correos electrónicos correo basura y legítimos que contengan una palabra determinada ("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 para que el mensaje sea correo no deseado, a sabiendas de que contiene una palabra dada;
• ${\displaystyle s}$ es la fuerza que le damos a la información de fondo sobre el correo basura entrante;
• ${\displaystyle \Pr(S)}$ es la probabilidad de cualquier mensaje entrante sea correo basura;
• ${\displaystyle n}$ es el número de ocurrencias de esta palabra durante la fase de aprendizaje;
• ${\displaystyle \Pr(S|W)}$ es la basurabilidad de esta palabra.

(Demostración:^[13])

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

${\displaystyle \Pr(S)}$ de nuevo se puede tomar igual a 0.5, para evitar ser demasiado sospechoso con el correo electrónico entrante. 3 es un buen valor para s, lo que significa que el cuerpo aprendido debe contener más de 3 mensajes con esa palabra para poner más confianza en el valor basurabilidad que en el valor predeterminado.

Esta fórmula puede extenderse para el caso en que n es igual a cero (y donde no se define la basurabilidad), y evalúa en este caso para ${\displaystyle Pr(S)}$.

Otra heurística

Palabras "neutrales" como "el", "a", "algunos", o "es", o sus equivalentes en otros idiomas, se pueden ignorar. En términos más generales, algunos filtros bayesianos simplemente ignoran todas las palabras que tienen una basurabilidad próxima a 0,5, ya que contribuyen muy poco para una buena decisión. Las palabras que se tienen en cuenta son aquellos cuya basurabilidad está al lado de 0.0 (signos distintivos de los mensajes legítimos), o al lado de 1,0 (signos distintivos de correo no deseado). Un método puede ser, por ejemplo para mantener solo las diez palabras, en el mensaje examinado, que tiene el mayor valor absoluto |0.5 − pI|.

Algunos software tienen en cuenta el hecho de que una palabra dada aparece varias veces en el mensaje examinado,^[14] otros no lo hacen.

Algunos productos de software utilizan patrones (secuencias de palabras) en vez de palabras de aislados idiomas naturales.^[15] Por ejemplo, con una "ventana de contexto" de cuatro palabras, que calculan la basurabilidad de "Viagra es bueno para", en lugar de calcular las basurabilidad de "Viagra "," es "," bueno ", y" para ". Este método da más sensibilidad al contexto y elimina el ruido bayesiano mejor, a expensas de una base de datos más grande.

Métodos mixtos

Hay otras maneras de combinar probabilidades individuales para diferentes palabras que usando el enfoque de "naive". Estos métodos difieren de ella en los supuestos que hacen en las propiedades estadísticas de los datos de entrada. Estas hipótesis diferentes resultan fórmulas distintas radicalmente para combinar las probabilidades individuales.

Por ejemplo, suponiendo que las probabilidades individuales siguen una distribución chi-cuadrado con 2N 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 se pueden combinar con las técnicas de la discriminación de Markovian.

Discusión

Ventajas

Una de las principales ventajas ^{[cita requerida]} del filtro bayesiano es que puede ser entrenado en base de un usuario. El correo basura que recibe un usuario está a menudo relacionado con las actividades del usuario en línea. Por ejemplo, un usuario puede haberse suscrito a un boletín en línea que el usuario considere correo basura. Este boletín de noticias en línea es probable que contenga las palabras que son comunes a todos los boletines de noticias, tales como el nombre del boletín de noticias y su dirección de correo electrónico de origen. Un filtro de correo basura bayesiano finalmente asigna una probabilidad superior basada en patrones específicos del usuario. Los correos legítimos que un usuario recibe tenderán a ser diferente. Por ejemplo, en un entorno corporativo, se mencionan a menudo el nombre de la empresa y el nombre del cliente o los clientes. El filtro asignará una probabilidad inferior a los correos electrónicos de correo basura que contienen esos nombres.

Las probabilidades de las palabras son únicas para cada usuario y pueden evolucionar con el tiempo con el aprendizaje correctivo cuando el filtro clasifica erróneamente un correo electrónico. Como resultado, la precisión del filtrado de correo basura bayesiano después del entrenamiento es a menudo superior que las reglas pre-definidas. Se puede especializar bien en evitar falsos positivos,^{[cita requerida]} donde el correo electrónico legítimo se clasifica incorrectamente como correo basura. Por ejemplo, si el correo electrónico contiene la palabra "Nigeria", que se utiliza con frecuencia en Estafa nigeriana, un filtro de reglas predefinidas podría rechazarla de plano. Un filtro bayesiano marcaría la palabra "Nigeria" como una palabra probablemente indeseada, pero tendría en cuenta otras palabras importantes que generalmente indican correo electrónico legítimo. Por ejemplo, el nombre de un cónyuge puede indicar fuertemente el correo no es correo basura, lo que podría superar el uso de la palabra "Nigeria".

Desventajas

Dependiendo de la aplicación, el filtro bayesiano puede ser susceptible de envenenamiento bayesiano, una técnica utilizada por los remitentes de correo basura en un intento de degradar la efectividad de los filtros de correo basura que se basan en el filtrado bayesiano. Un remitente de correo basura que practica el envenenamiento bayesiano enviará correos electrónicos con grandes cantidades de texto legítimo (obtenida de noticias legítimas o fuentes literarias). Las tácticas de los remitentes de correo basura incluyen la inserción de palabras inocuas aleatorias que normalmente no se asocian con el correo basura, disminuyendo así la puntuación de correo basura del correo electrónico, por lo que es más propenso a deslizarse más allá de un filtro bayesiano de correo basura. Sin embargo,(por ejemplo) en el esquema de Paul Graham se utilizan solo las probabilidades más significativas, de manera que el relleno del texto con las palabras no relacionadas con el correo basura no afecta a la probabilidad de detección de manera significativa.

Las palabras que aparecen normalmente en grandes cantidades en el correo basura también pueden ser transformadas por los remitentes de correo basura. Por ejemplo, «Viagra» sería sustituido por «Viaagra» o «V! Agra» en el mensaje de correo basura. El destinatario del mensaje todavía puede leer las palabras cambiadas, pero cada una de estas palabras se reunieron más raramente por el filtro bayesiano, lo que dificulta su proceso de aprendizaje. Como regla general, esta técnica correo basura no funciona muy bien, porque las palabras derivadas terminan reconocidos por el filtro al igual que las normales.^[16]

Otra técnica utilizada para tratar de derrotar a los filtros de correo basura bayesiano es reemplazar texto con imágenes, ya sea directamente incluidos o vinculados. Todo el texto del mensaje, o alguna parte de ella, se reemplaza por un cuadro en el que el mismo texto se "dibuja". El filtro de correo no deseado suele ser incapaz de analizar este cuadro, que contendría las palabras sensibles como «Viagra». Sin embargo, ya que muchos clientes de correo desactivan la visualización de imágenes vinculadas por razones de seguridad, el remitente de correo basura envía enlaces a imágenes distantes que podrían llegar a menos objetivos. Además, el tamaño de una imagen en bytes es más grande que el tamaño del texto equivalente, por lo que el remitente de correo basura necesita más ancho de banda para enviar mensajes directamente que contengan imágenes. Algunos filtros son más proclives a decidir que un mensaje es correo basura si tiene contenidos en su mayoría gráficos. Una solución utilizada por Google en su sistema de correo electrónico Gmail en su sistema de correo electrónico OCR (Optical Character Recognition) a cada imagen de gran tamaño, analizando el texto dentro.^[17]

Aplicaciones generales de filtrado bayesiano

Si bien el filtrado Bayesiano es ampliamente utilizado para identificar correos electrónicos correo basura, la técnica puede clasificar (o "cluster") casi cualquier tipo de datos. Tiene usos en la ciencia, la medicina y la ingeniería. Un ejemplo es un programa de clasificación de propósito general llamada AutoClass que originalmente se utilizó para clasificar estrellas de acuerdo a las características espectrales que eran de otro modo demasiado sutil para darse cuenta.

Véase también

• Técnicas Anti-correo basura
• Filtrado de Email
• Discriminación de Markovian
• Mozilla Thunderbird Cliente con implementación de técnicas de filtrado bayesiano

Referencias

1. Jason Rennie (1996). «ifile».
2. M. Sahami, S. Dumais, D. Heckerman, E. Horvitz (1998). «A Bayesian approach to filtering junk e-mail». AAAI'98 Workshop on Learning for Text Categorization.
3. Paul Graham (2003), Better Bayesian filtering
4. Brian Livingston (2002), Paul Graham provides stunning answer to spam e-mails
5. «Junk Mail Controls». MozillaZine. noviembre de 2009.
6. «Installation». Ubuntu manuals. 18 de septiembre de 2010. Archivado desde el original el 29 de septiembre de 2010. Consultado el 18 de septiembre de 2010. «Gary Robinson’s f(x) and combining algorithms, as used in SpamAssassin».
7. «Background Reading». SpamBayes project. 18 de septiembre de 2010. Archivado desde el original el 6 de septiembre de 2010. Consultado el 18 de septiembre de 2010. «Sharpen your pencils, this is the mathematical background (such as it is).* The paper that started the ball rolling: Paul Graham's A Plan for Spam.* Gary Robinson has an interesting essay suggesting some improvements to Graham's original approach.* Gary Robinson's Linux Journal article discussed using the chi squared distribution.»
8. Dylan Mors and Dermot Harnett (2009). «State of Spam, a Monthly Report - Report #33». Archivado desde el original el 7 de octubre de 2009. Consultado el 27 de octubre de 2015.
9. Process Software, Introduction to Bayesian Filtering Archivado el 6 de febrero de 2012 en Wayback Machine.
10. «Combining probabilities». at MathPages
11. http://mail.python.org/pipermail/python-dev/2002-August/028216.html Tim Peter's comment on the algorithm used by Graham
12. «Graham's web page referencing the MathPages article for the probability formula used in his spam algorithm.».
13. Gary Robinson (2003). «A statistical approach to the spam problem». Linux Journal.
14. Brian Burton (2003). «SpamProbe - Bayesian Spam Filtering Tweaks».
15. Jonathan A. Zdziarski (2004). «Bayesian Noise Reduction: Contextual Symmetry Logic Utilizing Pattern Consistency Analysis». (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
16. Paul Graham (2002), A Plan for Spam
17. «Gmail uses Google's innovative technology to keep spam out of your inbox».

Enlaces externos

• Guide to Bayesian correo basura filters: part 1, part 2.
• Gary Robinson's correo basura blog

• Datos: Q812531