Filtrado bayesiano de spam

El filtrado de spam bayesiano (en referencia al teorema de Bayes ) es una detección técnica estadística de spam basada en el clasificador Naive Bayes .

Los filtros bayesianos funcionan correlacionando la presencia de ciertos elementos (generalmente palabras, a veces otras cosas) en un mensaje y si suelen aparecer en mensajes no deseados ( spam ) o en mensajes legítimos ( ham ) para calcular la probabilidad de que este mensaje sea spam.

El filtrado de spam bayesiano es una técnica poderosa para tratar el correo electrónico no deseado. Se adapta a los hábitos de envío de correos de los demás y produce una tasa de falsos positivos lo suficientemente baja como para ser aceptable.

Histórico

El primer programa de filtrado de correo electrónico que utilizó Bayes fue el programa iFile de Jason Rennie, lanzado en 1996. Este programa se utilizó para clasificar el correo en carpetas . La primera publicación académica sobre el filtrado de spam bayesiano fue realizada por Sahami et al. en 1998. En 2002, los principios del filtrado bayesiano llamaron la atención de un público más amplio en un artículo de Paul Graham .

Se han implementado variaciones de la técnica básica en varios trabajos de investigación y productos de software . Muchos agentes de correo electrónico modernos implementan filtros de spam bayesianos . Los usuarios también pueden instalar software de terceros especializado en este trabajo. También es posible implementar este tipo de filtros en servidores utilizando software especializado como DSPAM (en) , SpamAssassin , SpamBayes (en) , Altospam , Bogofilter , OutClock , Spamihilator o incluso ASSP (en) , y esta función a veces se integra con el propio servidor de correo.

Proceso

Es más probable que ciertas palabras aparezcan en correo no deseado y correo legítimo. Por ejemplo, la mayoría de las personas encontrarán con frecuencia la palabra " Viagra " en sus correos electrónicos no deseados, pero rara vez la encontrarán en sus correos electrónicos legítimos. El filtro no conoce estas probabilidades de antemano, por lo que se necesita una curva de aprendizaje para evaluarlas. El aprendizaje es responsabilidad del usuario, quien debe indicar manualmente si un mensaje es spam o no. Para cada palabra en cada mensaje "aprendido", el filtro ajustará las probabilidades de encontrar esa palabra en correo no deseado o correo legítimo y las almacenará en su base de datos. Por ejemplo, es muy probable que los filtros bayesianos tengan una alta probabilidad de enviar spam a la palabra "Viagra", pero una probabilidad muy baja para las palabras encontradas en el correo legítimo, como los nombres de amigos y parientes.

Después del entrenamiento, las probabilidades de palabras (también llamadas funciones de verosimilitud ) se utilizan para calcular la probabilidad de que un mensaje (todas estas palabras) sea spam. Cada palabra en el mensaje, o al menos cada palabra "interesante" en el mensaje, contribuye a la probabilidad de que el mensaje sea spam. Esta contribución se calcula utilizando el teorema de Bayes . Una vez que se completa el cálculo de todo el mensaje, comparamos su probabilidad de ser spam con un valor arbitrario (95% por ejemplo) para marcar o no el mensaje como spam.

Al igual que con cualquier otra técnica de filtrado de correo no deseado, los mensajes marcados como correo no deseado se pueden mover automáticamente a una carpeta de "correo no deseado" o incluso eliminarse en el acto. Algunos software implementan mecanismos de cuarentena que definen un intervalo de tiempo durante el cual el usuario tiene la oportunidad de revisar la decisión del software.

El aprendizaje inicial a menudo se puede refinar si alguna vez se identifican malas decisiones de software ( falsos positivos o falsos negativos ). Esto permite que el software se adapte a la naturaleza cambiante del spam.

Algunos filtros de spam combinan los resultados del filtrado de spam bayesiano con otros métodos heurísticos (reglas predefinidas con respecto al contenido del mensaje, examen del sobre del mensaje, etc. ), lo que conduce a un filtrado aún más preciso, a veces a expensas de la adaptabilidad.

Fundamentos matemáticos

Los filtros de spam bayesianos se basan en 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, considerando todas sus palabras, o un subconjunto significativo de sus palabras;
a veces una tercera vez, para tratar con palabras raras.

Calcule la probabilidad de que un mensaje que contenga una palabra determinada sea spam

Suponga que el mensaje sospechoso contiene la palabra " Réplica ". En 2009, la mayoría de las personas que están acostumbradas a recibir correos electrónicos saben que es probable que este mensaje sea spam, específicamente un intento de vender marcas de relojes famosas falsas. El software de detección de spam ignora estos hechos, sin embargo, todo lo que puede hacer es calcular probabilidades.

La fórmula que utiliza el software para determinar esta probabilidad se deriva del teorema de Bayes . Estos, en su forma más general, son:

P (S | M) = {\ frac {P (M | S) \ cdot P (S)} {P (M | S) \ cdot P (S) + P (M | H) \ cdot P (H) }}

o :

$P (S | M)$ es la probabilidad de que el mensaje sea spam, sabiendo que la palabra " Replica " está ahí;
$P (S)$ es la probabilidad absoluta de que cualquier mensaje sea spam;
$P (M | S)$ es la probabilidad de que aparezca " Replica " en los mensajes de spam;
$P (H)$ es la probabilidad absoluta de que cualquier mensaje no sea spam (es decir, " jamón ");
$P (M | H)$ es la probabilidad de que aparezca " Replica " en los mensajes de ham .

(Prueba: teorema de Bayes # Otros escritos del teorema de Bayes )

Espamicidad

Las estadísticas recientes muestran que la probabilidad actual de que cualquier mensaje sea spam es al menos del 80%:

P (S) = 0,8; P (H) = 0,2

La mayoría del software de detección de spam bayesiano considera que no existe una razón a priori por la que un mensaje recibido sea spam en lugar de ham , y considera que los dos casos tienen probabilidades idénticas del 50%:

P (S) = 0,5; P (H) = 0,5

Se dice que los filtros que hacen esta suposición son "imparciales", lo que significa que no tienen ningún sesgo en el correo recibido. Esta suposición permite simplificar la fórmula general mediante:

P (S | M) = {\ frac {P (M | S)} {P (M | S) + P (M | H)}}

Esta cantidad se denomina espamicidad de la palabra " réplica " y se puede calcular. El número que aparece en esta fórmula se aproxima por la frecuencia de mensajes que contienen " Réplica " entre los mensajes identificados como spam durante la fase de aprendizaje. Del mismo modo, se aproxima por la frecuencia de mensajes que contienen " Replica " entre los mensajes identificados como radioaficionados durante la fase de aprendizaje. Para que estas aproximaciones sean realistas, el conjunto de mensajes "aprendidos" debe ser lo suficientemente grande y representativo. Además, se recomienda que el conjunto de mensajes utilizado para el entrenamiento se ajuste a la suposición del 50% sobre la división entre mensajes no deseados y mensajes inocentes, es decir, el corpus de spam y el corpus de spam .ham tienen aproximadamente el mismo tamaño. $P (M | S)$ $P (M | H)$

Por supuesto, determinar si un mensaje es spam o no basándose únicamente en la presencia de la palabra " Réplica " puede generar el error, por lo que el software antispam intenta considerar varias palabras y combinar su envío de spam para determinar la probabilidad general de ser spam. .

Combinar probabilidades individuales

El software de filtrado de spam bayesiano asume ingenuamente que las palabras del mensaje son eventos independientes . Esto está mal en lenguajes naturales como el francés, donde la probabilidad de encontrar un adjetivo, por ejemplo, está influenciada por la probabilidad de tener un nombre. De todos modos, con este supuesto, podemos deducir otra fórmula del teorema de Bayes :

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})}}

o :

$pag$ es la probabilidad de que el mensaje sospechoso sea spam;
$p_1$ es la probabilidad de que sea spam, sabiendo que contiene una primera palabra (por ejemplo " Réplica "); $P (S | M_ {1})$
$p_2$ es la probabilidad de que sea spam, sabiendo que contiene una segunda palabra (por ejemplo, " relojes "); $P (S | M_ {2})$
etc.
$p_ {N}$ es la probabilidad de que sea spam, sabiendo que contiene una i-ésima palabra (por ejemplo, " casa "). $P (S | M_ {N})$ $NO$

(Demostración: combinación de probabilidades en el sitio MathPages)

Tales suposiciones hacen del software de filtrado bayesiano un proceso de clasificación bayesiano ingenuo .

El resultado generalmente se compara con un umbral dado para decidir si el mensaje es spam o no. Si está por debajo de este umbral, el mensaje se considera probablemente legítimo. De lo contrario, se considera probable que sea ilegítimo. $pag$ $pag$

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

A menudo, no se calcula directamente usando la fórmula anterior, porque tiende a producir soupassements aritméticos ( subflujos aritméticos ) una vez implementado en un programa de computadora. En su lugar, podemos usar logaritmos reescribiendo la fórmula original de esta manera: $pag$

{\ frac {1} {p}} - 1 = {\ frac {(1-p_ {1}) (1-p_ {2}) \ dots (1-p_ {n})} {p_ {1} p_ {2} \ dots p_ {n}}}

Tomando el logaritmo de ambos lados de la igualdad:

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

Vamos a posar . Entonces, $\ eta = \ sum _ {{i = 1}} ^ {N} \ left [\ ln (1-p_ {i}) - \ ln p_ {i} \ right]$

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

Esto da la expresión alternativa de la fórmula para calcular la probabilidad combinada:

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

Tratar con palabras raras

En el caso de que nunca se haya encontrado la palabra " Réplica " durante la fase de aprendizaje, el numerador y el denominador son ambos cero, tanto en la fórmula general para calcular la probabilidad como un mensaje que contiene esta palabra es spam solo en la fórmula para calcular la espamicidad de esa palabra. El software de filtrado de correo puede decidir rechazar las palabras para las que no hay información disponible.

De manera más general, las palabras que solo se han encontrado un pequeño número de veces durante la fase de aprendizaje son problemáticas, porque sería un error confiar ciegamente en la información que brindan. Una solución simple es dejar esas palabras a un lado también.

Aplicando nuevamente el teorema de Bayes, y asumiendo que la clasificación entre spam y correo legítimo es una variable aleatoria que obedece a la ley beta , otro software decide usar una probabilidad corregida:

P '(S | M) = {\ frac {s \ cdot P (S) + n \ cdot P (S | M)} {s + n}}

o :

$P '(S | M)$ es la probabilidad corregida de que el mensaje sea spam, sabiendo que contiene una palabra determinada;
$s$ es la fuerza que le damos a la información sobre spam ambiental;
$P (S)$ es la probabilidad de que un mensaje entrante sea spam;
$no$ es el número de apariciones de esta palabra durante la fase de aprendizaje;
$P (S | M)$ es la espamicidad de la palabra.

(Demostración: en el artículo Un enfoque estadístico del problema del spam )

La probabilidad corregida se usa en lugar de la espamicidad en la fórmula que combina las probabilidades de cada palabra.

$P (S)$ de nuevo se puede tomar igual a , para evitar que un filtro sea demasiado sospechoso. es un buen valor para , lo que significa que se necesitan más de tres mensajes para tener más confianza en el valor del spam que en la información de spam ambiental. $0,5$ $3$ $s$

Esta fórmula se puede extender al caso donde es cero (y la espamicidad no está definida) y da en este caso . $no$ $P (S)$

Otras heurísticas

Por lo general, se ignoran las palabras neutrales como "le", "la", "un" (en francés) o sus equivalentes en otros idiomas.

De manera más general, la mayoría del software de filtrado bayesiano simplemente ignora cualquier palabra cuya espamicidad sea cercana a 0.5, porque no contribuye a una buena decisión. Las palabras consideradas son aquellas cuya espamicidad se acerca a 0.0 (signos distintivos de mensajes legítimos) o cercana a 1.0 (signos distintivos de mensajes ilegítimos). Un método puede ser mantener solo las diez palabras para las que el valor absoluto es mayor. $| 0,5 pI |$

Algunos programas tienen en cuenta el hecho de que una palabra determinada aparece más de una vez en el mensaje examinado, otros no.

Algunos programas utilizan patrones (grupos de palabras) en lugar de palabras sueltas en lenguaje natural. Por ejemplo, para una palabra de cuatro pop -up, calculan la spamicity de "Viagra es bueno para", en lugar de calcular el spamicity de "Viagra", "es", "bueno" y "para". Este método proporciona más sensibilidad al contexto y elimina mejor el ruido bayesiano , pero requiere una base de datos más grande.

Métodos mixtos

Hay otras formas de combinar probabilidades individuales para palabras diferentes que el enfoque “ingenuo”. Estos métodos difieren del método ingenuo en las suposiciones que se hacen sobre los datos de entrada. Estos diferentes supuestos dan como resultado fórmulas radicalmente diferentes para combinar las probabilidades individuales.

Por ejemplo, si asumimos que las probabilidades individuales siguen una ley de χ² con grados de libertad, podemos usar la fórmula: $2 \ cdot N$

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

donde es la inversa de la función χ². $C ^ {{- 1}}$

Las probabilidades individuales también se pueden combinar con técnicas de discriminación de Markov .

Discusión

Ventajas

Una de las principales ventajas del filtro bayesiano es que se adapta a su usuario.

El spam que recibe un usuario suele estar relacionado con su actividad en Internet. Por ejemplo, mientras navega por la web, es posible que, sin saberlo, lo hayan incluido en una lista de correo (presentada como una "carta comercial") que considerará spam. La mayoría de las veces, todos los mensajes enviados a esta lista contienen palabras comunes, como el nombre de la lista y la dirección de correo electrónico del remitente. El filtro bayesiano detectará estos puntos en común y les dará una alta probabilidad.

Asimismo, el correo legítimo recibido por múltiples usuarios tiende a ser diferente. Por ejemplo, en un entorno profesional, a menudo se mencionará el nombre de la empresa en la que se trabaja, así como los nombres de los clientes y proveedores. El filtro asignará una probabilidad baja a los correos que contengan estos nombres.

Las probabilidades pueden cambiar con el tiempo, a través del aprendizaje continuo, siempre que el filtro clasifique erróneamente un mensaje. Como resultado, un filtro bayesiano suele ser más preciso que las reglas predefinidas.

Los filtros bayesianos son particularmente buenos para evitar falsos positivos, es decir, clasificar los mensajes legítimos como spam. Por ejemplo, si el correo electrónico contiene la palabra "Nigeria", que a menudo aparece en spam de tipo estafa nigeriano , un conjunto de reglas predefinido lo rechazará automáticamente. Un filtro bayesiano marcaría la palabra "Nigeria" como una característica del spam, pero también tendría en cuenta otras palabras importantes, como el nombre del cónyuge o los nombres de amigos, que suelen ser signos de correo legítimo y tendrán prioridad. La presencia de la palabra "Nigeria".

Desventajas

El envenenamiento bayesiano es una técnica utilizada por los spammers para intentar degradar la eficacia de los filtros de spam bayesianos. Consiste en colocar en el correo una gran cantidad de texto inocuo (de sitios de noticias o literatura por ejemplo), o ensalada textual (secuencias aleatorias de palabras que parecen consistentes pero no significan nada), para ahogar el texto no deseado y engañar al filtro.

Los spammers también pueden transformar palabras que normalmente solo aparecen en spam. Así, "Viagra" se transformará, por ejemplo, en "Viaagra" o "V! Agra". El destinatario aún puede leer, pero cada una de estas palabras transformadas solo se encontrará en raras ocasiones, lo que penaliza el aprendizaje mediante el filtro bayesiano. En la práctica, esta técnica funciona bastante mal, porque las propias palabras derivadas acaban siendo reconocidas por el filtro.

Otra técnica utilizada por los spammers para intentar engañar al filtro bayesiano es reemplazar el texto con imágenes. Todo el texto, o parte de él, se reemplaza por una imagen donde se "dibuja" este mismo texto. El filtro de spam generalmente no puede analizar esta imagen que contiene palabras sensibles como "Viagra". Sin embargo, muchos usuarios desactivan la visualización de imágenes por razones de seguridad, lo que hace que los spammers lleguen menos a sus objetivos. Además, el tamaño de una imagen es mayor que el texto equivalente y los spammers necesitan más ancho de banda para enviar mensajes que contienen imágenes. Algunos filtros tienden a decidir que un mensaje es spam cuando tiene demasiado contenido gráfico. Finalmente, Google ha propuesto una solución que probablemente sea más eficiente y que es utilizada por el sistema de correo electrónico Gmail : procesar cualquier imagen mediana o grande mediante reconocimiento óptico de caracteres para analizar el texto que contiene.

Notas y referencias

(en) Jason Rennie, " ifile " [texto]1996(consultado el 23 de abril de 2020 )
(in) Jason DM Rennie, " ifile: An Application of Machine Learning to E-Mail Filtering " [PDF] , Boston, MA USA, KDD-2000 Text Mining Workshop2000(consultado el 23 de abril de 2020 )
(en) Sr. Sahami, S. Dumais, D. Heckerman, E. Horvitz, Un enfoque bayesiano para filtrar el correo electrónico no deseado , Taller AAAI'98 sobre el aprendizaje para la categorización de textos ,1998.
(en) Paul Graham , " Un plan para el spam " [html] ,2002(consultado el 23 de abril de 2020 ) .
(en) Dylan Mors y Dermot Harnett, " State of Spam, un aplazamiento mensual, aplazamiento # 33 " (al 23 de marzo de 2019 en Internet Archive ) .
(en) Gary Robinson, “ Una aproximación estadística al problema del spam ” , Linux Journal ,1 st de marzo de de 2003( leer en línea , consultado el 23 de abril de 2020 ).
(in) Trevor Stone, " Parametrización de Naïve Bayes para el filtrado de spam ", otoño de 2003
(en) Software de proceso, Introducción al filtrado bayesiano
(in) " Combinando probabilidades " en el sitio MathPages.
(en) Brian Burton, " SpamProbe - Ajustes de filtrado de spam bayesiano " ,2003.
(en) Jonathan A. Zdziarski, " Reducción de ruido bayesiano: simetría lógica contextual utilizando análisis de patrones de coherencia " ( Archivo • Wikiwix • Archive.is • Google • ¿Qué hacer? ) ,2004.
(in) " Gmail utiliza la tecnología innovadora de Google para mantener el spam fuera de su bandeja de entrada »

Ver también

enlaces externos

(en) filtros bayesianos Spam Guía: 1 st parte , 2 de parte .
(es) Explicación detallada de las fórmulas de Paul Graham por Tim Peters
(en) el blog de Gary Robinson sobre spam
Fundamento matemático del aprendizaje Estadística