Filtro Anti Spam

Embed Size (px)

DESCRIPTION

filtros anti-spam con redes neuronales

Citation preview

Algoritmos de aprendizaje automtico Los sistemas comerciales disponibles actualmente utilizan algoritmos de aprendizaje bayesianos simples. Los sistemas experimentales suelen utilizar otros algoritmos mas complejos basados tanto en aprendizaje bayesiano como en otros sistemas automticos de clasificacin. Trabajos recientes en el filtrado de spam, hacen uso del algoritmo de aprendizaje SVM con unos resultados satisfactorios. Nuestra investigacin se ha centrado principalmente en la utilizacin del algoritmo de aprendizaje basado en regresin logstica bayesiana BBR. Por otra parte, a modo de comparativa, se ha aplicado el algoritmo SVM y el algoritmo PLAUM. A continuacin, se describen brevemente dichos algoritmos. 2.1 BBR (Bayesian Binary Regression) Se trata de una implementacin de la regresin logstica bayesiana, aplicada a la clasificacin binaria. La clave de este algoritmo es la utilizacin de una distribucin de probabilidad previa (ver ecuacin 1) y algoritmos de optimizacin sucesiva de los ejemplos de entrenamiento suministrados. p(y 1 , x) ( x) T = = Ecuacin 1 Este algoritmo inicialmente realiza una regresin logstica de los datos de entrenamiento a partir de la distribucin de probabilidad elegida (Gausiana o Laplace), por medio de una funcin de enlace (ver ecuacin 2). (z) = exp(z) (1+exp(z)) Ecuacin 2 Una vez obtenido el modelo de regresin, se va optimizando sucesivamente a travs de la aplicacin de un algoritmo de regresin logstica en cadena. Se trata de un algoritmo de optimizacin de coordenada cclica descendente. Se comienza poniendo todas las variables a algn valor inicial, y se busca qu valor de la primera variable minimiza la funcin objetivo, asumiendo que todas las otras variables mantienen constantes sus valores iniciales. Este es un problema de optimizacin unidimensional. El mismo mtodo se lleva a cabo con la segunda variable, y as sucesivamente hasta que se han cruzado todas las variables. Este proceso se repite varias pasadas hasta encontrar un criterio de convergencia. De forma resumida, el algoritmo funciona como sigue : 1. Inicializar las variables j=0 (vector de parmetros), j=0 (conjunto de datos, o regin explorada), para j=1 hasta d (nmero de parmetros del modelo); i =0 (estimador previo de confianza), para i=1 hasta n (nmero de ejemplos).

2. Desde k=1, 2, ... hasta que se produzca la convergencia, hacer 2.1. Para j=1 hasta d, hacer: 2.1.1. Calcular

2.1.2. Calcular ( ( ), ) j = mn mx j j j , en los datos spam del subconjunto tratado. 2.1.3. Calcular i j ij i = x y , con i i i = + , para i=1,...,n. 2.1.4. Calcular j = j + j 2.1.5. Calcular (2 , / 2) i = mx j i , ampliando el tamao del subconjunto de spam tratado. 2.2 SVM El algoritmo SVM (Support Vector Machine) fue utilizado por primera vez en la Clasificacin de Texto en 1998 por T. Joachims . En trminos geomtricos, se puede ver como el intento de encontrar un espacio n-dimensional, que permita separar los ejemplos positivos de entrenamiento de los negativos, permitiendo especificar el margen ms amplio posible. El objetivo perseguido por este algoritmo es encontrar el hiperplano ptimo que maximice la distancia entre los casos positivos y los casos negativos. Como argumenta Joachims , las mquinas de vectores de soporte ofrecen dos grandes ventajas para la categorizacin de texto: Evita los problemas de sobrecarga de pruebas en espacios de grandes dimensiones. Realiza una optimizacin global, sin ptimos locales. Estos son los pasos principales del algoritmo SVM [2]: 1. Seleccionar el parmetro C como representante de la compensacin entre la reduccin al mnimo del error de clasificacin del conjunto de entrenamiento y maximizar el margen. 2. Seleccionar la funcin de kernel y cualquier parmetro del mismo. 3. Solucionar el problema cuadrtico dual resultante de la ecuacin 3 o una formulacin alternativa que use la programacin cuadrtica de forma apropiada o un algoritmo de programacin lineal. Ecuacin 3 4. Extraer la variable de umbral b, utilizando los vectores de apoyo. 5. Clasificar un punto nuevo x, siguiendo la ecuacin 4: Ecuacin 4 donde, xi (i=1,...,m) son los miembros del conjunto de puntos de entrenamiento; yi=1 son las etiquetas de la clase; y i son los vectores de soporte. En la figura 1 se pueden apreciar ejemplos de entrenamiento positivo y negativo. Las lneas representan los hiperplanos de separacin. La lnea ms gruesa es la que minimiza la distancia para cualquier ejemplo de entrenamiento. Figura 1: Representacin de puntos en SVM 2.3 PLAUM (Perceptron Algorithm with Uneven Margins) Se trata de algoritmo rpido y eficaz para realizar clasificaciones lineales. El algoritmo PLAUM es una extensin del algoritmo del Deteccin automtica de spam utilizando regresin logstica bayesianaPerceptron, adaptada para tratar problemas de separacin lineal de datos a travs de un hiperplano [14]. Tal como SVM se basa en la idea de encontrar un margen entre hiperplanos, y sus autores aseguran que funciona mejor que SVM para tareas de clasificacin de texto. Este algoritmo requiere: Un conjunto de entrenamiento linealmente separable de la forma: { } m z = (x, y)(X x 1,+1 ) . Un ndice de aprendizaje + . Un nmero mximo de iteraciones T. Dos parmetros que limitan los ejemplos negativos y positivos: + 1, +1 . El algoritmo funciona de acuerdo a los siguientes pasos :