tp bayes vs spam

Trabajo Prctico

Naive Bayes contra la problemtica del SPAM

Sistemas de Soporte de Decisiones

Turno Viernes Noche 1er. Cuatrimestre 2011

Alumnos:

- Casarero, Eduardo

- Ruiz, Santiago

Sistemas de Soporte de Decisiones Trabajo Prctico Cuatrimestral 03/06/2011

135576/Casarero, 116764/Ruiz ii

Abstract En los ltimos aos el correo electrnico se ha vuelto una herramienta indispensable para la sociedad. Con el

crecimiento exponencial del trfico de correo electrnico tambin aumenta un problema asociado al email, el

SPAM o email comercial no solicitado. En el mercado existen diferentes soluciones comerciales u opensource

para combatir el spam. Estas herramientas incluyen por defecto Naive Bayes, adems de otras herramientas. El

presente trabajo prctico tiene por objetivo introducir al lector en las tcnicas de Naive Bayes para atacar el

problema del SPAM.

Introduccin El termino SPAM es utilizado generalmente para describir un email comercial no solicitado. El problema del

SPAM puede ser cuantificado en trminos econmicos, siendo que los trabajadores desperdician horas de

trabajo eliminando este tipo de trfico, o simplemente leyndolo para perder el tiempo.

Aunque segn el informe anual de Cisco Systems el trafico de SPAM en 2010 aparentemente comenz a

decrecer, ya sea por medidas implementadas por los gobiernos, o porque el auge de las redes sociales atrae

mas las actividades ilcitas que el spam, pero aun sigue siendo un gran problema, para visualizarlo, en 2010

Brasil envi 7 billones de spams y Estados Unidos 11 billones de spams.

Como administradores de sistemas antispam de dominios argentinos y latinoamericanos pudimos observar que

la mayora de las soluciones antispam (pagas o libres) estn enfocadas en su mayora a detectar el spam

generado para pases del hemisferio norte y angloparlantes.

La correcta implementacin de sistemas como Naive Bayes pueden contribuir con una mejora en la calidad de

deteccin del trafico local mejorando considerablemente la cantidad de falsos negativos y positivos.

El presente trabajo pretende ser una introduccin a esta tcnica, siendo que en base a nuestra experiencia

profesional no existe una documentacin accesible que permita a un administrador de sistemas conocer con

cierto detalle el funcionamiento de estos sistemas.


135576/Casarero, 116764/Ruiz iii

Naive Bayes Basado en una teora probabilstica el algoritmo de Bayes proporciona una forma de clasificacin de

informacin que no utiliza reglas, ni arboles, ni otro tipo de representacin de la clasificacin. Esta tcnica se

apoya en un Teorema del Reverendo Thomas Bayes (1702-1761), un pionero de la probabilidad y el primero en

usar la probabilidad en una forma inductiva.

La enunciacin del teorema

Sea 1, 2, 3, un conjunto de sucesos mutuamente excluyentes y exhaustivos, y tales que la

probabilidad de cada uno de ellos es distinta de cero. Sea B un suceso cualquiera del que se conocen las

probabilidades condicionales|. Entonces, la probabilidad | viene dada por la expresin:

|

|

donde:

son las probabilidades a priori.

| es la probabilidad de B en la hiptesis Ai.

PAi|B son las probabilidades a posteriori.

En sus inicios, las primeras tcnicas en la lucha contra el SPAM estaban basadas en reglas y listas no dinmicas,

o con una velocidad de cambio lenta para combatir las nuevas y diferentes tcnicas para enviar correo no

solicitado salteando estas protecciones. Surge entonces la idea de aplicar Naive Bayes para detectar spam,

porque es un algoritmo poco costoso de implementar y si los datos con los que se entrena el algoritmo son

bien seleccionados el rendimiento en la deteccin es aceptable.

Para poder construir un clasificador probabilstico para detectar spam, se utiliza una red Bayesiana. Una red

bayesiana es un grafo dirigido y a-cclico que representa una distribucin de probabilidad. En ese grafo, cada

variable aleatoria Xi es seleccionada como nodo. Un arco dirigido entre dos nodos indica una influencia

probabilstica (dependencia) desde la variable padre hacia el nodo hijo. Consecuentemente, la estructura de la

red asume que cada nodo Xi es independiente de los nodos que no son sus hijos. Para describir una

distribucin de probabilidad que satisfaga estos supuestos, cada nodo Xi en la red esta asociada con una tabla

de probabilidad condiciona, que especifica la distribucin de Xi dado cualquier posible asignacin de sus

padres.

Un clasificador Bayesiano contiene un nodo C representando una clase de variable y un nodo Xi por cada una

de sus opciones. Dada una instancia especifica de x , , , , la red Bayesiana nos permite calcular la

probabilidad de | para cada posible clase . Esto es realizado mediante el teorema de Bayes

(explicado antes).


135576/Casarero, 116764/Ruiz iv

| !" |#! $%#! $%

!"

En el contexto de la clasificacin de texto, especficamente la deteccin de correo basura, se vuelve necesaria

la representacin del mensaje en un feature vector (vector de caractersticas).

El proceso de tokenizado, convierte el email de su formato estndar a un formato vectorizado para que

pueda usarse en la clasificacin bayesiana. La forma en que el mensaje se tokeniza tiene una profunda

influencia en los resultados que va a producir el motor de clasificacin. Existen diversas formas de tokenizar un

correo, sin embargo con el correr del tiempo y la mutacion normal del trafico, estas tcnicas tambin se van

refinando y mejorando para adaptarse a los cambios.

Los mensajes son separados en varios tipos de tokens, tokens de cabeceras, tokens de cuerpo y tokens

sintetizados. Los tokens de cabeceras identifican partes de los componentes del encabezado del correo y

permiten obviar informacin que no resulta importante para la clasificacin

Un ejemplo de tokenizado de headers:

Word Probability Times in ham Times in spam

content-type:multipart/related - 0 0

content-type:multipart/alternative 0.811987 1 8

to:name:eduardo casarero - 0 0

to:addr:eduardo.casarero - 0 0

to:addr:informaticaavanzada.com.ar - 0 0

Los tokens del cuerpo del mensaje son generados simplemente con una separacin del texto del mensaje por

palabras, teniendo en cuenta que algunos patrones en particular se detectan, como urls, contenido html (los

tags html se eliminan), el email de origen, etc.

Ejemplos de tokens del cuerpo del email:

Word Probability Times in ham Times in spam

webinar 0.908163 0 2

please 0.303408 3 2

send 0.155172 1 0

your 0.4478 3 4

comments 0.155172 1 0

and 0.5 3 5

feedback 0.539526 1 2

server 0.265886 2 1

skip:m 10 0.38764 2 2

attendees - 0 0


135576/Casarero, 116764/Ruiz v

Entrenamiento

Algo importante en la operatoria de clasificadores bayesianos es el tipo de entramiento que se va a realizar. A

continuacin se presentan los diferentes tipos:

- Entrenamiento de errores: Utilizando este criterio solamente entrenamos al clasificador cuando realiza

una categorizacin equivocada. Solo cuando el error de clasificacin es muy grosero se procede a

enviar el email mal categorizado al clasificador con su correcta clasificacin para que se ajusten los

valores de los tokens. Este tipo de entrenamiento puede tener como consecuencia una degradacin de

la performance bastante significativa debido al poco feedback por lo que ser necesario reiniciar la

base de datos con cierta periodicidad.

- Entrenamiento de unsures: Son los emails que estn en una zona gris, en la que el clasificador no

puede decidir. La diferencia con el caso anterior es que los mensajes que se usaran para el

entrenamiento no fueron mal categorizados, sino que no pudieron ser clasificados. Con el tiempo este

entrenamiento va a producir un decrecimiento de emails clasificados en esta zona gris. Si en la

implementacin se utiliza un buen lote inicial de entrenamiento los errores de clasificacin van a ser

pocos y por lo tanto con este tipo de entrenamiento se va a ir depurando la base de datos hasta tener

una buena performance.

- Entrenamiento de Errores y de unsures: Este entrenamiento es la suma de los dos anteriores y cubre

los dos anteriores tipos. Una problema de este entrenamiento es que puede generar bayes poisoning

que significa que la base de datos de tokens se va corrompiendo porque se ingresan emails muy

diferentes en ambas categoras, y esta especie de envenenamiento baja extremadamente la

performance.

- Entrenamiento de Todo: Esta es una de las cosas mas fciles de hacer, si nuestro sistema de correo

electrnico puede aprender de las carpetas Inbox / Junk de nuestro cliente de correo es mucho mas

sencillo aun. El problema con esta tcnica es que debemos revisar con cierta periodicidad que los

mensajes en Junk no tengan un falso positivo para no contaminar nuestra base de conocimiento.

- Otras tcnicas: existen otros criterios pero solo mencionamos estos para dar una idea de las opciones

existentes y posibles.

Adems de Como entrenar a spam bayes hay otra pregunta importante Hasta cuando entrenar al

clasificador? Algunos criterios son:

- Hasta que la performance es aceptable

- Hasta que se supera cierto umbral de cantidad mensajes entrenados

- Hasta que se supera un periodo de tiempo.

- Entrenar para siempre

Finalmente algo a tener en cuenta es que ya sea que sufrimos bayes poisining (autogenerado por nosotros, o

por ataques de terceros) es probable que cada cierto tiempo tengamos que reiniciar la base de datos y

comenzar el entrenamiento nuevamente.


135576/Casarero, 116764/Ruiz vi

SpamBayes, de la teora a la practica

Un ejemplo practico

A los efectos de mostrar un ejemplo de clasificacin real vamos a tomar el caso de un email con 4 palabras:

palabra1, palabra2, palabra3, palabra4. Obviamos la parte de tokenizado y determinacin de la probabilidad de

spam y ham del token porque implica ciertas correcciones de calculo utilizando otros modelos para por

ejemplo agrupar en un solo token las palabras (recomendar, recomendacin, por ejemplo).

Para poder realizar el calculo de la probabilidad de spam de un email hay que asumir que la ocurrencia de las

palabras es un evento independiente, aunque en la realidad esto no sea asi ya que si en una oracin existe un

adjetivo tambin debera existir un sustantivo. Teniendo en cuenta esta consideracin la formula para agrupar

las probabilidades independientes seria:

&'( )*( * +(,-.( ,(- ,&-+ &. &. &. &0

&. &. &. &0 1 1 2 &1 2 &1 2 &1 2 &0

Siendo & la probabilidad de que el mensaje sea spam si contiene la palabra1.

Caso

1

Caso

2

Caso

3

Caso

4

Prob(Email es spam si contiene 'palabra1') 0,3 0,5 0,4 0,9




Prob Spam: 0,01 0,60 0,40 0,99

En la tabla se pueden observar los 3 casos mas usuales en la clasificacin bayesiana. Los Casos 1 y 4 muestran

una clasificacin en los extremos, siendo el caso 1 un email genuino y el caso 4 un email spam. Casos 2 y 3

estan en una zona gris en donde generalmente el clasificador bayesiano etiqueta el correo como neutro y seria

necesario que el usuario entrene al clasificador con estos casos para refinar la tcnica de clasificacin.


135576/Casarero, 116764/Ruiz vii

Descripcin de la maqueta

Los datos utilizados en la maqueta surgen del trfico diario de la casilla de correo laboral de Eduardo Casarero.

Adems el entrenamiento que se realizo del trafico (para determinar si es spam o ham) fue aleatorio ya que se

intenta presentar la tcnica en general y no realizar un anlisis de su performance o tasa de error.

Maqueta de pruebas:

Como software para la realizacin de las pruebas y ejemplos de este trabajo practico se decidi utilizar

SpamBayes (http://spambayes.sourceforge.net) debido a que la arquitectura aunque puede resultar

complicada para implementar en un ambiente de produccin masivo es simple para la demostracin del

funcionamiento del clasificador, adems de tener una interface web amigable y estar desarrollado

ntegramente en python, cuestin que facilita la lectura del cdigo.

La maqueta en accin

Una vez que la maqueta esta operativa, procedemos a generar trafico para que empiece a pasar por el proxy,

de esta forma podemos empezar a entrenarlo y a observar que calidad de deteccin obtenemos.

Inicialmente cargamos unos 15 correos como spam y despus empezamos a mandar emails para que los

procese internamente. Spambayes va a decidir sobre todos los emails, si son spam o ham o unsure y va a

agregar en los headers del email los siguientes tems:

X-Spambayes-Classification: unsure

X-Spambayes-MailId: 1305867441

El primer campo nos indica en que categora clasifico el mensaje, y el segundo nos indica un id para poder ir a

la interfase web y recategorizar el mensaje si es necesario.

Ademas, tenemos una consola administrativa en la que podemos ver una lista de todos los mensajes que se

clasificaron pero que no se confirmaron en spambayes, de esta forma podemos ver rpidamente todos los

mensajes nuevos y reclasificarlos.


135576/Casarero, 116764/Ruiz viii

En esta pantalla podemos ver el asunto del email, el remitente, la accin a tomar (se puede descartar,

demorar, aprender como genuino, aprender como spam) y adems se pueden ver las clues y los tokens.

Bsicamente las clues son un subconjunto (bastante acotado) de tokens del correo electrnico en el cual

spambayes se esta basando para tomar una decisin.

Consulta de palabras

Algo que tambin podemos realizar desde la interface es la consulta de palabras particulares para averiguar el

peso que tienen en la categorizacin.

En este caso la palabra nagios tiene una probabilidad baja de ser spam, de hecho que fuera catalogada en 2

emails como spam probablemente indique una mala categorizacin.


135576/Casarero, 116764/Ruiz ix

Como encaja Spam Bayes en la gran escala.

Como paso previo a la conclusin de este trabajo practico entendimos que es necesario situar Spam Bayes en

el flujo real del correo electrnico. El diagrama presenta una arquitectura simplificada pero bastante certera de

cmo el es flujo de un correo electrnico desde que sale del servidor de origen hasta que llega a la bandeja de

entrada del cliente. Basados en nuestra experiencia personal un solo administrador de sistemas puede

mantener un servicio antispam para mas de 100.000 casillas de usuarios, ahora bien, para el administrador es

inviable re-categorizar todo el trafico que fue falso negativo o positivo. La verdadera potencia de este tipo de

clasificadores es que con un entrenamiento bsico los propios usuarios pueden contribuir a mejorar la

performance de clasificacin con herramientas adecuadas de feedback.

Conclusin Esta tcnica de deteccin de spam contribuye de forma significativa a la mejora de la calidad de los filtros de

spam. El uso de un sistema de puntaje que provee una zona gris de clasificacin reduce la exposicin de los

usuarios a mensajes no solicitados casi eliminando los falsos positivos. Si bien la parte terica no es simple,

creemos que el desafo esta en la consolidacin del feedback (re-entrenamiento) de los mensajes por parte de

los usuarios, ya que para algunas decenas de usuarios se puede implementar de forma sencilla, pero para miles

de usuarios consolidados en un solo servicio de correo puede llegar a ser un reto importante.


135576/Casarero, 116764/Ruiz x

Bibliografa

SpamBayes-Development-Team, "SpamBayes: Bayesian anti-spam classifier written in Python",

[online] 2003, http://spambayes.org (Accedido: 10 de Mayo de 2011)

P. Graham, "A Plan for Spam", [online] 2002, http://www.paulgraham.com/spam.html (Accedido: 10

de Mayo de 2011)

Ian H Witten, Eibe Frank, Data Mining: Practical Machine Learning tools Morgan Kaufmann

Publishers USA [2000]

Zhiwei Fu, Isa Sarac. A computational Study of Nave Bayes Learning in Anti-spam Management

Virginia International University (2004)

G. Cornmak, Email spam filtering: A systematic review. Foundation and trends in information

retrieval, vol 1, no. 4. Pp 335-455, 2008.

tp bayes vs spam

Documents