Algoritmo de big data: algoritmo de clasificación
El algoritmo KNN, concretamente el algoritmo K vecino más cercano, es un algoritmo de clasificación básico. El principio fundamental es: para un dato que necesita ser clasificado, compárelo con un conjunto de muestras que han sido clasificadas y etiquetadas, y obtenga las K muestras más cercanas. La categoría a la que pertenecen más las K muestras es la categoría de. los datos que es necesario clasificar. A continuación les dibujo un diagrama esquemático del algoritmo KNN.
En la figura, los puntos en colores rojo, azul y verde son datos de muestra, que pertenecen a tres categorías: , , . Para clasificar el punto, calcule los 5 puntos más cercanos (es decir, K es 5. Las categorías más comunes a las que pertenecen estos 5 puntos son (4 puntos pertenecen a , 1 punto pertenece a), luego la categoría de es. clasificado como .
El flujo del algoritmo de KNN también es muy simple. Consulte el diagrama de flujo a continuación.
El algoritmo KNN es un algoritmo de clasificación muy simple y práctico que se puede utilizar en varios escenarios de clasificación, como clasificación de noticias, clasificación de productos, etc., e incluso se puede utilizar para el reconocimiento de texto simple. Para la clasificación de noticias, se pueden anotar manualmente varias noticias por adelantado, marcar las categorías de noticias y calcular los vectores de características. Para un artículo de noticias no clasificado, después de calcular su vector de características, la distancia se calcula con todas las noticias etiquetadas y luego se utiliza el algoritmo KNN para la clasificación automática.
Después de leer esto, seguramente te preguntarás, ¿cómo calcular la distancia de los datos? ¿Cómo obtener el vector de características de las noticias?
La clave del algoritmo KNN es comparar la distancia entre los datos que deben clasificarse y los datos de muestra. Esto generalmente se hace en el aprendizaje automático: extraer los valores propios de los datos y formar un. Número real de n dimensiones basado en los valores propios del espacio vectorial (este espacio también se llama espacio de características) y luego calcula la distancia espacial entre vectores. Existen muchos métodos para calcular distancias entre espacios, los más utilizados incluyen la distancia euclidiana, la distancia del coseno, etc.
Para la suma de datos, si su espacio de características es un espacio vectorial de números reales n-dimensional, es decir, entonces su fórmula de cálculo de distancia euclidiana es
Esta fórmula de distancia euclidiana es en realidad cuando Estábamos en la escuela secundaria. Aprendí que la distancia entre dos puntos en geometría plana y geometría sólida también se calcula usando esta fórmula. Es solo que n = 2 en geometría plana (geometría bidimensional) y n = 3 en geometría sólida. geometría (geometría tridimensional), y cada dato que el aprendizaje automático necesita enfrentar puede tener n dimensiones, es decir, cada dato tiene n valores de características. Pero no importa cuál sea el valor propio n, la fórmula de cálculo para la distancia espacial entre dos datos sigue siendo esta fórmula de cálculo euclidiana. La mayoría de los algoritmos de aprendizaje automático necesitan calcular la distancia entre los datos, por lo que dominar la fórmula de cálculo de la distancia de los datos es la base para dominar los algoritmos de aprendizaje automático.
La distancia euclidiana es la fórmula de cálculo de datos más utilizada, pero en el aprendizaje automático de datos de texto y datos de evaluación del usuario, el método de cálculo de distancia más utilizado es la similitud del coseno.
Cuanto más cerca esté el valor de la similitud del coseno a 1, más similar será, y cuanto más cerca esté de 0, mayor será la diferencia. El uso de la similitud del coseno puede eliminar parte de la información redundante de los datos y. en algunos casos está más cerca de la esencia de los datos. Permítanme dar un ejemplo simple. Por ejemplo, los valores de características de dos artículos son: "big data", "aprendizaje automático" y "tiempo geek". El vector de características del artículo A es (3, 3, 3). es decir, estas tres El número de apariciones de palabras es 3; el vector de características del artículo B es (6, 6, 6), es decir, el número de apariciones de estas tres palabras es 6. Si solo miras los vectores de características, los dos vectores son muy diferentes. Si usas el cálculo de la distancia euclidiana, de hecho son muy diferentes. Sin embargo, los dos artículos son en realidad muy similares, solo que su longitud es diferente. , lo que significa que son muy similares.
La similitud del coseno en realidad calcula el ángulo entre vectores, mientras que la fórmula de distancia euclidiana calcula la distancia espacial. La similitud del coseno presta más atención a la similitud de los datos. Por ejemplo, si dos usuarios califican dos elementos como (3, 3) y (4, 4) respectivamente, entonces las preferencias de los dos usuarios para los dos elementos son similares. En este caso, la similitud del coseno es más razonable que la distancia euclidiana.
Sabemos que los algoritmos de aprendizaje automático necesitan calcular la distancia, y calcular la distancia requiere conocer el vector de características de los datos. Por lo tanto, extraer el vector de características de los datos es un trabajo importante, a veces incluso. el trabajo más importante. Diferentes datos y diferentes escenarios de aplicación requieren la extracción de diferentes valores de características. Tomemos como ejemplo los datos de texto más comunes para ver cómo extraer vectores de características de texto.
El valor característico de los datos de texto es extraer palabras clave de texto. El algoritmo TF-IDF es un algoritmo de extracción de palabras clave de texto intuitivo y de uso común. Este algoritmo se compone de dos partes: TF e IDF.
TF es Frecuencia de términos, que representa la frecuencia con la que aparece una palabra en un documento. Cuanto más frecuentemente aparece una palabra en un documento, mayor será el valor de TF.
Frecuencia de palabras:
IDF es la frecuencia inversa de documentos (Inverse Document Frequency), que indica la escasez de esta palabra en todos los documentos. Cuantos menos documentos aparezca esta palabra, mayor. el valor de la FDI.
Frecuencia de documentos inversa:
El producto de TF e IDF es TF-IDF.
Entonces, si una palabra aparece con frecuencia en un determinado documento pero rara vez aparece en todos los documentos, es probable que esa palabra sea una palabra clave de ese documento. Por ejemplo, en un artículo técnico sobre energía atómica, palabras como "fisión nuclear", "radiactividad" y "vida media" aparecerán con frecuencia en este documento, es decir, TF es muy alto pero su frecuencia en todos los documentos es; relativamente bajo, es decir, el IDF también es relativamente alto. Por lo tanto, el valor TF-IDF de estas palabras será muy alto y pueden ser las palabras clave de este documento. Si este es un artículo sobre la energía atómica de China, tal vez la palabra "China" también aparezca con frecuencia, es decir, el TF también es alto, pero "China" también aparece en muchos documentos, entonces las FDI serán relativamente bajas y, finalmente, "China" El TF-IDF de esta palabra es muy bajo y no se convertirá en una palabra clave para este documento.
Después de extraer las palabras clave, puede utilizar la frecuencia de las palabras clave para construir un vector de características. Por ejemplo, en el ejemplo anterior de un artículo sobre energía atómica, las tres palabras "fisión nuclear", ". radioactividad" y "vida media" son los valores característicos. El número de apariciones es 12, 9 y 4 respectivamente. Entonces, el vector de características de este artículo es (12, 9, 4). Luego, utilice la fórmula de cálculo de distancia espacial mencionada anteriormente para calcular la distancia a otros documentos. Combinada con el algoritmo KNN, se puede lograr la clasificación automática de documentos.
La fórmula de Bayes es un algoritmo de clasificación basado en la probabilidad condicional. Si ya conocemos la probabilidad de ocurrencia de A y B, y conocemos la probabilidad de que A ocurra cuando ocurre B, podemos usar la fórmula de Bayes Calcular. la probabilidad de que B suceda si A sucede. De hecho, podemos juzgar la probabilidad de B, es decir, la posibilidad de B, en función de la situación de A, es decir, los datos de entrada, y luego clasificar.
Por ejemplo: Supongamos que en un colegio hay un 60% de niños y un 40% de niñas. Los niños siempre usan pantalones y las niñas usan medio pantalón y media falda. Supongamos que estás caminando por el campus y un estudiante que lleva pantalones camina hacia ti. ¿Puedes deducir la probabilidad de que el estudiante que lleva pantalones sea un niño?
La respuesta es 75%. El algoritmo específico es:
Este algoritmo utiliza la fórmula de Bayes. La fórmula de Bayes se escribe como:
Significa la probabilidad. de que B suceda bajo las condiciones de que A suceda es igual a la probabilidad de que A suceda bajo las condiciones de B, multiplicada por la probabilidad de que B suceda, dividida por la probabilidad de que A suceda. Siguiendo usando el ejemplo anterior, si te pregunto cuál es la probabilidad de que el estudiante que lleva falda y camina hacia ti sea una niña. También usando la fórmula bayesiana podemos calcular que la probabilidad de ser niña es del 100%. De hecho, también podemos inferir este resultado basándonos en el sentido común, pero muchas veces, el sentido común se ve interferido por varios factores y se desviará. Por ejemplo, cuando alguien vio un artículo de noticias sobre un estudiante de doctorado que trabajaba para un jefe con un título de secundaria, se lamentó de que estudiar era inútil. De hecho, es raro y extraño, y el tamaño de la muestra es demasiado pequeño. Las reglas estadísticas de una gran cantidad de datos pueden reflejar con precisión la probabilidad de clasificación de las cosas.
Una aplicación típica de la clasificación bayesiana es la clasificación de spam. A través de estadísticas de correos electrónicos de muestra, conocemos la probabilidad de que aparezca cada palabra en el correo electrónico. También conocemos la probabilidad de que aparezcan correos electrónicos normales y correos electrónicos no deseados. También se puede calcular cada palabra en el correo electrónico no deseado. Ahora que llega un nuevo correo electrónico, podemos calcular en función de las palabras que aparecen en el correo electrónico, es decir, podemos obtener la probabilidad de que el correo electrónico sea spam cuando aparecen estas palabras. y luego determine si el correo electrónico es spam.
En realidad, podemos obtener la probabilidad en el lado derecho del signo igual de la fórmula bayesiana a través de estadísticas de big data. Cuando llegan nuevos datos, podemos incorporar la fórmula bayesiana anterior para calcular su probabilidad.
Y si establecemos la probabilidad de exceder un cierto valor y pensamos que sucederá, entonces clasificaremos y predeciremos los datos. El proceso específico se muestra en la siguiente figura.
La muestra de entrenamiento son nuestros datos originales. A veces, los datos originales no contienen los datos dimensionales que queremos calcular. Por ejemplo, si queremos utilizar la fórmula bayesiana para clasificar automáticamente los correos electrónicos no deseados, primero debemos clasificar. Marque los correos electrónicos originales, debe marcar qué correos electrónicos son correos electrónicos normales y cuáles son spam. Este tipo de capacitación en aprendizaje automático que requiere etiquetar datos también se denomina aprendizaje automático supervisado.