Abrir menú principal

Filtrado bayesiano de spam

técnica de línea de base para tratar con el 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 spam, un enfoque común en la clasificación de textos.

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 spam 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 spam.

El filtrado de spam bayesiano es una técnica de línea de base para tratar con el spam, 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 spam, que son generalmente aceptables para los usuarios. Es una de las formas más antiguas de hacer filtrado de spam, con raíces en la década de 1990.

HistoriaEditar

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 spam. [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 spam.[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 se spam 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, SPAM, SpamAssassin,[6]​ SpamBayes,[7]Bogofilter and Anti-Spam SMTP Proxy, que hacen uso de técnicas de filtrado de spam bayesiano, y la funcionalidad es a veces embebida dentro del servidor de correo del propio software.

ProcesoEditar

Palabras particulares tienen determinadas probabilidades de ocurrir en el correo electrónico spam 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 spam, 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 spam o no. Las palabras de los correos entrenantes 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 spam. Por ejemplo, los filtros bayesianos de spam normalmente habrán aprendido una muy alta probabilidad de spam para las palabras "Viagra" y "refinanciar", pero una probabilidad muy baja de spam para las palabras que se ven sólo 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 spam, o sólo 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 spam 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 spam.

Al igual que en cualquiera otra técnica de filtrado de spam el correo electrónico marcado como spam, 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 spam.

Algunos filtros de spam 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áticosEditar

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

  • una primera vez, para calcular la probabilidad de que el mensaje es spam, sabiendo que una palabra dada aparece en este mensaje;
  • por segunda vez, para calcular la probabilidad de que el mensaje es spam, 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 spamEditar

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:

 

dónde:

  •   es la probabilidad de que un mensaje es un correo no deseado, a sabiendas de que la palabra "réplica" está en él;
  •   es la probabilidad general de que cualquier mensaje dado es spam;
  •   es la probabilidad de que la palabra "réplica" aparece en los mensajes de spam;
  •   es la probabilidad general de que cualquier mensaje dado no es spam (es "legítimo");
  •   es la probabilidad de que la palabra "réplica" aparece en los mensajes legítimos.

El spamicity de una palabraEditar

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

 

Sin embargo, la mayoría del software de detección de spam 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]

 

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:

 

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

Esta cantidad se denomina "spamicity" (o "spaminess") de la palabra "réplica", y se puede calcular. El número   utilizado en esta fórmula es aproximado a la frecuencia de los mensajes que contienen "réplica" en los mensajes identificados como spam durante la fase de aprendizaje. Del mismo modo,   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 spam 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 spam o legítimo basado sólo 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 spamicities para determinar la probabilidad global de un mensaje de ser un correo no deseado.

Combinaciones de probabilides individualesEditar

La mayoría de los algoritmos de filtrado de spam bayesiano 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 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]

 

dónde:

  •   es la probabilidad de que el mensaje sospechoso es correo no deseado;
  •   es la probabilidad   que es saber un spam que contiene una primera palabra (por ejemplo, "réplica");
  •   es la probabilidad   que es saber un spam que contiene una segunda palabra (por ejemplo, "relojes");
  • etc...
  •   es la probabilidad   que es saber un spam 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 spam 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 spam o no. Si p es menor que el umbral, el mensaje se consideraba probable legítimo, de lo contrario se considera como probable spam.

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

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:

 

Tomando los logaritmos en ambos lados:

 

Dejar  . Por consiguiente,

 

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

 

Tratamiento para palabras rarasEditar

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 spamicity. 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 sólo 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 spam 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:

 

dónde:

  •   es la probabilidad corregida para que el mensaje sea correo no deseado, a sabiendas de que contiene una palabra dada;
  •   es la fuerza que le damos a la información de fondo sobre el spam entrante;
  •   es la probabilidad de cualquier mensaje entrante sea spam;
  •   es el número de ocurrencias de esta palabra durante la fase de aprendizaje;
  •   es la spamicity de esta palabra.

(Demostración:[13]​)

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

  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 spamicity 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 spamicity), y evalúa en este caso para  .

Otra heurísticaEditar

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 un spamicity 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 spamicity 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 sólo 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 spamicity de "Viagra es bueno para", en lugar de calcular los spamicities 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 mixtosEditar

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:

 

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 la discriminación de Markovian.

DiscusiónEditar

VentajasEditar

Una de las principales ventajas [cita requerida] del filtro bayesiano es que puede ser entrenado en base de un usuario. El spam 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 spam. 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 spam 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 spam 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 spam 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 spam. 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 spam, lo que podría superar el uso de la palabra "Nigeria".

DesventajasEditar

Dependiendo de la aplicación, el filtro bayesiano puede ser susceptible de envenenamiento bayesiano, una técnica utilizada por los spammers en un intento de degradar la efectividad 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 (obtenida de noticias legítimas o fuentes literarias). Las tácticas Spammer incluyen la inserción de palabras inocuas aleatorias que normalmente no se asocian con el spam, disminuyendo así la puntuación de spam del correo electrónico, por lo que es más propenso a deslizarse más allá de un filtro bayesiano de spam. Sin embargo,(por ejemplo) en el esquema de Paul Graham se utilizan sólo las probabilidades más significativas, de manera que el relleno del texto con las palabras no relacionadas con el spam no afecta a la probabilidad de detección de manera significativa.

Las palabras que aparecen normalmente en grandes cantidades en el spam también pueden ser transformadas por los spammers. Por ejemplo, «Viagra» sería sustituido por «Viaagra» o «V! Agra» en el mensaje de spam. 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 spam 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 spam 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 spammer 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 spammer 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 spam 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 bayesianoEditar

Si bien el filtrado Bayesiano es ampliamente utilizado para identificar correos electrónicos spam, 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énEditar

ReferenciasEditar

  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». 
  9. Process Software, Introduction to Bayesian Filtering
  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 y la última versión).
  16. Paul Graham (2002), A Plan for Spam
  17. «Gmail uses Google's innovative technology to keep spam out of your inbox». 

Enlaces externosEditar