Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

---

5. Evaluación de la calidad del clustering

El análisis de conglomerados consiste en descomponer un conjunto de datos en subconjuntos, cada subconjunto se denomina conglomerado y el conjunto de todos los subconjuntos se denomina conglomerado del conjunto de objetos. Un buen algoritmo de agrupación debería producir conglomerados de alta calidad y conglomerados de alta calidad, es decir, la similitud general dentro de los conglomerados es la más alta, mientras que la similitud general entre los conglomerados es la más baja.Dado que muchos algoritmos de agrupamiento incluyen$a$-El algoritmo de promedio, el algoritmo DBSCAN, etc. requieren que el usuario especifique la cantidad de clústeres en el clúster de antemano$a$, por lo tanto, el método de estimación simple de k se discutirá a continuación.

(1) Estimación del número de conglomerados

Muchos algoritmos de agrupamiento como $a$-Los algoritmos de promedio, incluso los algoritmos DIANA, etc., deben especificar el número de grupos por adelantado$a$,y$a$El valor de afectará en gran medida la calidad de la agrupación. Sin embargo, el número de agrupaciones debe determinarse de antemano.$a$ No es una tarea fácil. Primero podemos considerar dos casos extremos.
(1) Coloque todo el conjunto de datos$S$considerado como un grupo, es decir, $a=1$, esto parece simple y conveniente, pero los resultados de este análisis de conglomerados no tienen valor.
(2) Poner el conjunto de datos$S$Cada objeto de se trata como un grupo, es decir, dejemos que $a=|S|=norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte$ , produciendo así la agrupación más fina. Por lo tanto, no hay diferencias dentro del grupo en cada grupo y la similitud dentro del grupo alcanza el nivel más alto.Pero este tipo de agrupamiento no se puede utilizar para$S$proporcionar cualquier información sobre$S$una descripción general.
Se puede observar que el número de conglomerados$a$al menos debería satisfacer $2\le a\le norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte-1$, pero el número de conglomerados$a$Sigue siendo ambiguo exactamente qué valor es el más apropiado.
Generalmente considerado,$a$El valor de puede estimarse mediante la forma y escala de la distribución del conjunto de datos, así como la resolución de agrupamiento requerida por el usuario, y los académicos tienen muchos métodos de estimación diferentes, como el método del codo, el método de validación cruzada y la teoría de la información. métodos basados, etc.
Un sencillo y de uso común.$a$El método de estimación empírica del valor cree que para aquellos con$norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte$Un conjunto de datos de objetos, el número de grupos en los que está agrupado.$a$Elegir $\begin{array}{r}\sqrt{\frac{norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte}{2}}\end{array}$ Es apropiado.En este momento, según la expectativa promedio, cada grupo tiene aproximadamente$\sqrt{2norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte}$ objetos.Sobre esta base, algunas personas han propuesto restricciones adicionales adicionales, es decir, el número de grupos$a<\sqrt{norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte}$。
Por ejemplo, supongamos$norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte=8$, entonces el número de conglomerados $a=2$ es apropiado, y en promedio hay 4 puntos por grupo, y de acuerdo con la fórmula empírica adicional$a<2.83$ .Usando estas dos informaciones sobre el número de clusters$a$La fórmula empírica parece explicarse desde un lado, en el ejemplo 10-5 $a=2$ es el número más apropiado de clusters.

(2) Evaluación de calidad externa

Si tenemos una buena estimación del número de conglomerados$a$, puede utilizar uno o más métodos de agrupación, por ejemplo,$a$ -El algoritmo promedio, algoritmo jerárquico aglomerativo o algoritmo DBSCAN realiza análisis de conglomerados en conjuntos de datos conocidos y obtiene una variedad de resultados de agrupamiento diferentes. La pregunta ahora es qué método tiene mejores resultados de agrupación, o en otras palabras, cómo comparar los resultados de agrupación producidos por diferentes métodos. Ésta es la evaluación de la calidad de la agrupación.
En la actualidad, existen muchos métodos para elegir para la evaluación de la calidad de la agrupación, pero generalmente se pueden dividir en dos categorías, a saber, evaluación de la calidad externa (extrínseca) y evaluación de la calidad interna (intrínseca).
La evaluación de calidad externa supone que ya existe un grupo ideal en el conjunto de datos (generalmente construido por expertos) y lo compara como un método de referencia comúnmente utilizado con los resultados de agrupamiento de un determinado algoritmo. Su evaluación comparativa incluye principalmente la entropía de agrupamiento y la agrupación. son dos métodos comunes para la precisión de clases.

1. Método de entropía de agrupamiento

Conjunto de datos hipotéticos S = { X 1 , X 2 , … , X n } S={X_1,X_2,…,X_n}S={X1​,X2​,…,Xnorteorteorteorteorteorteorteorteorteorteorteorteorteorteorte​},y T = { T1, T2, …, Tm} T={T_1, T_2, …, T_m}yo={yo1​,yo2​,…,yometroetroetroetro​} es la agrupación estándar ideal proporcionada por expertos, y C = { C 1 , C 2 , … , C k } C={C_1,C_2,…,C_k}C={C1​,C2​,…,Ca​} está determinado por un algoritmo sobre$S$Un grupo de, luego para el grupo$C_i$En relación con la agrupación de referencia$yo$La entropía de agrupamiento de se define como
$$mi(C_i|yo)=-\sum _{yo=1}^{metroetroetroetro}\frac{|C_i\cap {yo}_{yo}|}{|C_i|}{\mathrm{Logramo}}_2\frac{|C_i\cap {yo}_{yo}|}{|C_i|}\text{\hspace{1em}(10-20)}$$ y$C$Acerca de los puntos de referencia$yo$La entropía de agrupación general de se define como todos los grupos$C_i$Acerca de los puntos de referencia$yo$El promedio ponderado de la entropía de agrupamiento, es decir
$$mi(C)=\frac{1}{\sum _{i=1}^a|C_i|}\sum _{i=1}^a|C_i|\times mi(C_i|yo)\text{\hspace{1em}(10-21)}$$ El método de entropía de agrupamiento cree que,$mi(C)$ Cuanto menor sea el valor, mayor$C$En relación con el valor inicial$yo$Cuanto mayor sea la calidad de la agrupación.
Vale la pena señalar que el denominador del primer término del lado derecho de la fórmula (10-21)$\begin{array}{r}\sum _{i=1}^a|C_i|\end{array}$ es la suma del número de elementos en cada grupo y no se puede utilizar$norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte$ para reemplazar.Porque sólo cuando$C$Cuando es un grupo de particiones, el denominador es$norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte$, y el denominador de los métodos de agrupación generales, como la agrupación DBSCAN, puede ser menor que$norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte$。

2. Precisión de agrupación

La idea básica de la evaluación de la exactitud (precisión) del clúster es utilizar la mayor cantidad de categorías en el clúster como etiqueta de categoría del clúster, es decir, para el clúster.$C_i$,si existiera${yo}_{yo}$hacer ∣ C i ∩ T j ∣ = máx ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } |C_icap T_j|=máx{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}∣Ci​∩yoyo​∣=máximo{∣Ci​∩yo1​∣,∣Ci​∩yo2​∣,⋯,∣Ci​∩yometroetroetroetro​∣}, Es considerado eso$C_i$La categoría es${yo}_{yo}$ .Por lo tanto, el cúmulo$C_i$Acerca de los puntos de referencia$yo$La precisión se define como
J ( C i ∣ T ) = máx ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } ∣ C i ∣ (10-22) J(C_i|T)=frac{máx{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}}{|C_i|}tag{10-22}Yo(Ci​∣yo)=∣Ci​∣máximo{∣Ci​∩yo1​∣,∣Ci​∩yo2​∣,⋯,∣Ci​∩yometroetroetroetro​∣}​(10-22) y$C$Acerca de los puntos de referencia$yo$La precisión general de está definida para todos los grupos.$C_i$Acerca de los puntos de referencia$yo$El promedio ponderado de la precisión de agrupamiento, es decir
$$Yo(C)=\frac{1}{\sum _{i=1}^a|C_i|}\sum _{i=1}^a|C_i|\times Yo(C_i|yo)\text{\hspace{1em}(10-23)}$$ El método de precisión de agrupamiento cree que,$Yo(C)$ Cuanto mayor sea el valor, mayor será la agrupación.$C$En relación con el valor inicial$yo$Cuanto mayor sea la calidad de la agrupación.
Además, generalmente$1-Yo(C)$ llamado$C$Acerca de los puntos de referencia$yo$ tasa de error global.Por lo tanto, la precisión de agrupamiento$Yo(C)$ Tasa de error grande o general$1-Yo(C)$ En pequeño, muestra que el algoritmo de agrupación puede agrupar mejor objetos de diferentes categorías en diferentes grupos, es decir, la precisión de la agrupación es alta.

(3) Evaluación de calidad interna

No existen puntos de referencia externos conocidos para la evaluación de la calidad interna, solo se utilizan conjuntos de datos.$S$y agrupamiento$C$Evaluar las características y magnitudes intrínsecas de un conglomerado.$C$ la calidad de. Es decir, el efecto de agrupamiento generalmente se evalúa calculando la similitud promedio dentro de los grupos, la similitud promedio entre grupos o la similitud general.
La evaluación de la calidad interna está relacionada con el algoritmo de agrupación. El índice de efectividad de la agrupación se utiliza principalmente para evaluar la calidad del efecto de agrupación o para juzgar el número óptimo de agrupaciones. El efecto de agrupación ideal es tener la distancia dentro del grupo más pequeña. Por lo tanto, la efectividad de la agrupación generalmente se mide mediante alguna forma de relación entre la distancia dentro del grupo y la distancia entre grupos. Los indicadores comúnmente utilizados de este tipo incluyen el indicador CH, el indicador Dunn, el indicador I, el indicador Xie-eni, etc.

1. Indicador de canal

El índice CH es la abreviatura del índice Calinski-Harabasz. Primero calcula la suma de los cuadrados de la distancia entre cada punto del grupo y su centro del grupo para medir la cercanía dentro de la clase y luego calcula la suma del cuadrado de la distancia; entre cada punto central del grupo y el punto central del conjunto de datos a medir La separación del conjunto de datos y la relación entre separación y cercanía es el índice CH.
configuración${\overline{X}}_i$representa un grupo$C$punto central (media),$\overline{X}$representa un conjunto de datos$S$el punto central de$d({\overline{X}}_i,\overline{X})$ para${\overline{X}}_i$llegar$\overline{X}$Una cierta función de distancia de, luego agrupación$C$La compacidad de un grupo medio se define como
$$\text{Rastro}(A)=\sum _{i=1}^a\sum _{X_{yo}\in C_i}d(X_{yo},{\overline{X}}_i{)}^2\text{\hspace{1em}(10-24)}$$ Por lo tanto, Trace(A) es el cluster$C$ La suma de las distancias al cuadrado entre los centros del grupo.Y agrupamiento$C$El grado de separación se define como
$$\text{Rastro}(B)=\sum _{i=1}^a|C_i|d({\overline{X}}_i,\overline{X}{)}^2\text{\hspace{1em}(10-25)}$$ Es decir, Trace(B) se está agrupando$C$Cada punto central del grupo de$S$La suma ponderada de distancias cuadradas desde el punto central de .
De esto, si$\begin{array}{r}norte=\sum _{i=1}^a|C_i|\end{array}$ Entonces el indicador CH se puede definir como
$$V_{\text{es}}(a)=\frac{\text{Rastro}(B)/(a-1)}{\text{Rastro}(A)/(norte-a)}\text{\hspace{1em}(10-26)}$$ La fórmula (10-26) se utiliza generalmente en las dos situaciones siguientes:
(1) Evalúe qué agrupamiento obtenido por los dos algoritmos es mejor.
Supongamos que se utilizan dos algoritmos para analizar el conjunto de datos.$S$Se realizó un análisis de conglomerados y se obtuvieron dos conglomerados diferentes (ambos conteniendo$a$grupos), la agrupación correspondiente al valor CH más grande es mejor, porque cuanto mayor es el valor CH significa que cada grupo en el grupo está más cerca de sí mismo y los grupos están más dispersos.
(2) Evaluar cuál de dos conglomerados con diferente número de conglomerados obtenidos mediante el mismo algoritmo es mejor.
Supongamos que un algoritmo tiene un conjunto de datos.$S$Se realizó un análisis de conglomerados y el número de conglomerados se obtuvo como$a_1$y$b_2$ De los dos grupos, el resultado de agrupación con un valor CH mayor es mejor, lo que también significa que el número de grupos correspondientes a este grupo es más apropiado.Por lo tanto, aplicando repetidamente la fórmula (10-26), también podemos obtener un conjunto de datos$S$El número óptimo de clústeres para la agrupación.

2. Indicador Dunn

El indicador Dunn utiliza clusters$C_i$con racimo$C_{yo}$distancia mínima entre $d_s(C_i,C_{yo})$ para calcular la separación entre conglomerados utilizando el diámetro de conglomerado más grande entre todos los conglomerados máx ⁡ { Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } máx{varPhi(C_1), varPhi(C_2),...,varPhi(C_k)}máximo{Φ(C1​),Φ(C2​),...,Φ(Ca​)} Para caracterizar la estrechez dentro de un cluster, el índice de Dunn es el valor mínimo de la relación entre el primero y el segundo, es decir
VD ( k ) = mín ⁡ i ≠ jds ( C i , C j ) máx ⁡ { Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } (10-27) V_D(k)=min_{i≠j}frac{d_s(C_i,C_j)}{max{varPhi(C_1), varPhi(C_2),...,varPhi (C_k)}}etiqueta{10-27}VD​(a)=i=yomín.​máximo{Φ(C1​),Φ(C2​),...,Φ(Ca​)}ds​(Ci​,Cyo​)​(10-27) Cuanto mayor sea el valor de Dunn, mayor será la distancia entre los grupos y mejor será la agrupación correspondiente.Similar al índice de evaluación CH, el índice de Dunn se puede usar para evaluar la calidad de los conglomerados obtenidos por diferentes algoritmos, y también se puede usar para evaluar qué conglomerados obtenidos por el mismo algoritmo con diferentes números de conglomerados son mejores, es decir, puede usarse para buscar$S$el número óptimo de conglomerados.

6. Minería atípica

Los valores atípicos son datos especiales del conjunto de datos que se desvían significativamente de la mayoría de los datos. El objetivo de los algoritmos de minería de datos, como la clasificación y la agrupación presentados anteriormente, es descubrir patrones regulares que se apliquen a la mayoría de los datos. Por lo tanto, muchos algoritmos de minería de datos intentan reducir o eliminar el impacto de los valores atípicos y reducir los valores atípicos al implementar la minería. o ignorado como ruido, pero en muchas aplicaciones prácticas, la gente sospecha que la desviación de los puntos atípicos no es causada por factores aleatorios, sino que puede ser causada por otros mecanismos completamente diferentes, que deben desenterrarse para un análisis y utilización especiales. Por ejemplo, en campos de aplicación como la gestión de seguridad y el control de riesgos, el patrón de identificación de valores atípicos es más valioso que el patrón de datos normales.

(1) Descripción general de cuestiones relacionadas

La palabra Outlier suele traducirse como valor atípico, pero también como anomalía. Sin embargo, existen muchos alias en diferentes situaciones de aplicación, como puntos aislados, puntos anormales, puntos nuevos, puntos de desviación, puntos de excepción, ruido, datos anormales, etc. La minería de valores atípicos tiene términos similares, como minería de datos anómalos, detección de datos anómalos, minería de datos atípicos, minería de datos excepcionales y minería de eventos raros en la literatura china.

1. La generación de valores atípicos

(1) Los datos provienen de anomalías causadas por fraude, intrusión, brotes de enfermedades, resultados experimentales inusuales, etc. Por ejemplo, la factura telefónica promedio de una persona es de unos 200 yuanes, pero de repente aumenta a varios miles de yuanes en un mes determinado; la tarjeta de crédito de alguien suele consumir unos 5.000 yuanes al mes, pero en un mes determinado el consumo supera los 30.000 yuanes, etc. Estos valores atípicos suelen ser relativamente interesantes en la minería de datos y uno de los puntos clave de aplicación.
(2) Causado por cambios inherentes en las variables de datos, que reflejan las características naturales de la distribución de datos, como el cambio climático, nuevos patrones de compra de los clientes, mutaciones genéticas, etc. También una de las áreas de interés interesantes.
(3) Los errores de medición y recopilación de datos se deben principalmente a errores humanos, fallas del equipo de medición o presencia de ruido. Por ejemplo, la calificación de -100 de un estudiante en un determinado curso puede deberse al valor predeterminado establecido por el programa; el salario de los altos directivos de una empresa es significativamente más alto que el salario de los empleados comunes y corrientes, puede parecer un caso atípico, pero lo es. Datos razonables.

2. Problema minero atípico

Por lo general, el problema de la minería atípica se puede descomponer en tres subproblemas para describir.
(1) Definir valores atípicos
Dado que los valores atípicos están estrechamente relacionados con problemas prácticos, definir claramente qué tipo de datos son valores atípicos o datos anormales es la premisa y la tarea principal de la minería de valores atípicos. Generalmente, es necesario combinar la experiencia y el conocimiento de los expertos en el dominio para proporcionar un análisis preciso de los valores atípicos. . Dé una descripción o definición adecuada.
(2) Valores atípicos de minería
Una vez definidos claramente los puntos atípicos, la tarea clave de la extracción de valores atípicos es qué algoritmo utilizar para identificar o extraer eficazmente los puntos atípicos definidos. El algoritmo de minería de valores atípicos generalmente proporciona a los usuarios datos atípicos sospechosos desde la perspectiva de patrones que pueden reflejarse en los datos, para atraer la atención del usuario.
(3) Comprender los valores atípicos
La explicación razonable, la comprensión y la orientación de la aplicación práctica de los resultados de la minería son los objetivos de la minería atípica. Dado que el mecanismo por el cual se generan los valores atípicos es incierto, si los "valores atípicos" detectados por el algoritmo de minería de valores atípicos realmente corresponden al comportamiento anormal real no puede ser explicado ni explicado por el algoritmo de minería de valores atípicos, sino que solo puede explicarse por el algoritmo de minería de valores atípicos. Expertos de la industria o del dominio para comprender y explicar las instrucciones.

3. Relatividad de los valores atípicos

Los valores atípicos son datos especiales en el conjunto de datos que obviamente se desvían de la mayoría de los datos, pero "obviamente" y "en su mayoría" son relativos, es decir, aunque los valores atípicos son diferentes, son relativos. Por lo tanto, hay varias cuestiones a considerar al definir y extraer valores atípicos.
(1) Valores atípicos globales o locales
Un objeto de datos puede ser un valor atípico en relación con sus vecinos locales, pero no en relación con todo el conjunto de datos. Por ejemplo, un estudiante que mide 1,9 metros de altura es un caso atípico en la Clase 1 de la especialidad de matemáticas de nuestra escuela, pero no entre la gente de todo el país, incluidos jugadores profesionales como Yao Ming.
(2) Número de valores atípicos
Aunque se desconoce el número de puntos atípicos, el número de puntos normales debería exceder con creces el número de puntos atípicos. En general, se cree que el número de puntos atípicos debería representar una proporción menor. de puntos atípicos debería ser inferior al 5% o incluso inferior al 1%.
(3) Factor atípico de punto
No puede usar "sí" o "no" para informar si un objeto es un valor atípico. En su lugar, debe usar el grado de desviación del objeto, es decir, el factor de valor atípico (Factor de valor atípico) o la puntuación de valor atípico (Puntuación de valor atípico). para caracterizar la desviación de un dato del grado del grupo, y luego filtrar los objetos con factores atípicos superiores a un cierto umbral, proporcionarlos a los tomadores de decisiones o expertos en el dominio para su comprensión y explicación, y aplicarlos en el trabajo práctico.

(2) Método basado en la distancia

1. Conceptos básicos

Definición 10-11 hay un numero entero positivo$a$, objeto$X$de $a$-La distancia del vecino más cercano es un número entero positivo que satisface las siguientes condiciones $d_a(X)$：
(1) excepto$X$Además, existen al menos$a$objetos$Y$satisfacer $d(X,Y)\le d_a(X)$。
(2) excepto$X$Además, hay como máximo $a-1$ objetos$Y$satisfacer $d(X,Y)<d_a(X)$。
en$d(X,Y)$ es un objeto$X$y$Y$alguna función de distancia entre ellos.

de un objeto $a$-Cuanto mayor sea la distancia del vecino más cercano, más probable será que el objeto esté lejos de la mayoría de los datos, por lo que el objeto puede ser$X$de $a$-distancia del vecino más cercano $d_a(X)$ como su factor atípico.

Definición 10-12 hacer D ( X , k ) = { Y ∣ d ( X , Y ) ≤ dk ( X ) ∧ Y ≠ X } D(X,k)={Y|d(X,Y)≤d_k(X)cuña Y≠X}D(X,a)={Y∣d(X,Y)≤da​(X)∧Y=X}, entonces se llama $D(X,a)$ Sí$X$de $a$-Vecino más cercano (Dominio).

Se puede ver en la definición 10-12 que$D(X,a)$ Sí$X$como centro, distancia$X$No excede $d_a(X)$ Objeto$Y$ La colección compuesta por. Vale la pena prestar especial atención a,$X$no le pertenece $a$-vecino más cercano, es decir $X\notin D(X,a)$ . En particular,$X$de $a$-Vecino más cercano $D(X,a)$ El número de objetos contenidos puede exceder con creces$a$,Ahora mismo $|D(X,a)|\ge a$。

Definición 10-13 hay un numero entero positivo$a$, objeto$X$de $a$-El factor atípico del vecino más cercano se define como
$${\text{DE}}_1(X,a)=\frac{\sum _{Y\in D(X,a)}d(X,Y)}{|D(X,a)|}\text{\hspace{1em}(10-28)}$$

2. Descripción del algoritmo

Para un conjunto de datos dado y el número de distancias de vecinos más cercanos$a$, podemos usar la fórmula anterior para calcular el$a$-Factores atípicos del vecino más cercano y generarlos en orden de mayor a menor. Entre ellos, es más probable que varios objetos con factores atípicos más grandes sean valores atípicos, y deben ser analizados y juzgados por los tomadores de decisiones o los expertos de la industria. , Qué puntos son realmente atípicos.

Algoritmo 10-8 Algoritmo de detección de valores atípicos basado en la distancia
Entrada: conjunto de datos$S$, el número de distancias de vecinos más cercanos$a$
Salida: Lista descendente de puntos atípicos sospechosos y factores atípicos correspondientes
(1) REPETIR
(2) tomar$S$un objeto sin procesar en$X$
(3) OK$X$de$a$-Vecino más cercano$D(X,a)$
(4) Cálculo$X$de$a$-factor atípico del vecino más cercano${\text{DE}}_1(X,a)$
(5) HASTA$S$Cada punto ha sido procesado.
(6) Sí${\text{DE}}_1(X,a)$Ordenar en orden descendente y salida$(X,{\text{DE}}_1(X,a))$

3. Ejemplos de cálculo

Ejemplo 10-12 Un conjunto de datos bidimensional con 11 puntos.$S$Está dado por la Tabla 10-10, sea$a=2$, utilice el cálculo de la distancia euclidiana al cuadrado $X_7,X_{10},X_{11}$ Factor atípico para todos los demás puntos.

desatar: Para comprender intuitivamente el principio del algoritmo, usaremos$S$Los objetos de datos se muestran en el plano de la Figura (10-27) a continuación.

A continuación se calculan los factores atípicos del punto especificado y de otros puntos, respectivamente.

(1) Objeto de cálculo$X_7$factor atípico
Como se puede observar en la figura, la distancia$X_7=(6,8)$ El punto más cercano es$X_{10}=(5,7)$,y $d(X_7,X_{10})=1.41$, otros puntos más cercanos pueden ser $X_{11}=(5,2)$，$X_9=(3,2)$，$X_8=(2,4)$；
Calculado$d(X_7,X_{11})=6.08$，$d(X_7,X_9)=6.71$，$d(X_7,X_8)=5.66$
porque$a=2$,entonces $d_2(X_7)=5.66$, entonces según la definición 10-11 tenemos D(X7,2)={X10,X8}D(X7​,2)={X10​,X8​}
Según la fórmula (10-28),$X_7$factor atípico
$$\begin{array}{rl}{\text{DE}}_1(X_7,2)& =\frac{\sum _{Y\in norte(X_7,2)}d(X_7,Y)}{|norte(X_7,a)|}=\frac{d(X_7,X_{10})+d(X_7,X_8)}{2}\\ & =\frac{1.41+5.66}{2}=3.54\end{array}$$(2) Objeto de cálculo$X_{10}$factor atípico ${\text{DE}}_1(X_{10},2)=2.83$

(3) Objeto de cálculo$X_{11}$factor atípico ${\text{DE}}_1(X_{11},2)=2.5$

(4) Objeto de cálculo$X_5$factor atípico ${\text{DE}}_1(X_5,2)=1$

De manera similar, se pueden calcular los factores atípicos de los objetos restantes; consulte la siguiente tabla (10-11).

4. Umbral del factor atípico

de acuerdo a$a$ -En la teoría del vecino más cercano, cuanto mayor es el factor atípico, más probable es que sea un valor atípico. Por lo tanto, se debe especificar un umbral para distinguir los valores atípicos de los puntos normales. El método más simple es especificar el número de puntos atípicos, pero este método es demasiado simple y, a veces, omite algunos puntos atípicos reales o atribuye demasiados puntos normales a posibles puntos atípicos, lo que dificulta que los expertos en el dominio o los tomadores de decisiones surjan dificultades. en la comprensión e interpretación de valores atípicos.
(1) El método de umbral de segmentación de factores atípicos primero organiza los factores atípicos en orden descendente y, al mismo tiempo, vuelve a numerar los objetos de datos en orden ascendente de acuerdo con los factores atípicos.
(2) Basado en el factor atípico${\text{DE}}_1(X,a)$ es la ordenada y el número de serie del factor atípico es la abscisa, es decir, (número de serie,${\text{DE}}_1$valor) están marcados en el plano y conectados para formar una polilínea que no aumenta, y se encuentra que el punto donde la polilínea se cruza con una disminución pronunciada y una disminución suave corresponde al factor atípico como el umbral Objetos con un factor atípico menor. mayores o iguales a este umbral son objetos normales, los demás son posibles valores atípicos.

Ejemplo 10-13 Conjunto de datos para el ejemplo 10-12$S$ , sus factores atípicos se resumen en orden descendente y número de serie en la Tabla 10-11. Intente encontrar el umbral de puntos atípicos basándose en el método de umbral de segmentación de factores atípicos.

desatar: Primero, utilice el (número de serie, ${\text{DE}}_1$ valor) como puntos en el plano, marcados en el plano y conectados por polilíneas. Como se muestra en la Figura 10-28 a continuación.

Luego, observando la Figura 10-28, podemos encontrar que la polilínea a la izquierda del cuarto punto (4, 1.27) cae muy abruptamente, mientras que la polilínea a la derecha cae muy suavemente. Por lo tanto, se selecciona el factor atípico 1.27 como el. límite.porque$X_7、X_{10}$ y$X_{11}$ Los factores atípicos son 3,54, 2,83 y 2,5 respectivamente, y todos son mayores que 1,27. Por lo tanto, es más probable que estos tres puntos sean puntos atípicos, mientras que los puntos restantes son puntos ordinarios.
Mirando nuevamente la Figura 10-27, podemos encontrar que$X_7、X_{10}$ y$X_{11}$ de hecho, muy lejos de la densa mayoría de objetos de la izquierda, así que trátelos como un conjunto de datos$S$Los valores atípicos son razonables.

5. Evaluación de algoritmos

La mayor ventaja del método de detección de valores atípicos basado en la distancia es que es simple en principio y fácil de usar. Sus deficiencias se reflejan principalmente en los siguientes aspectos.
(1) Parámetros$a$La selección carece de un método simple y eficaz para determinar el impacto de los resultados de las pruebas en los parámetros.$a$No existe un resultado analítico universalmente aceptado sobre el grado de sensibilidad.
(2) La complejidad del tiempo es$Oh(|S{|}^2)$, carece de escalabilidad para conjuntos de datos a gran escala.
(3) Debido al uso de un umbral de factor de valores atípicos globales, es difícil extraer valores atípicos en conjuntos de datos con regiones de diferentes densidades.

(3) Método basado en la densidad relativa

El método de distancia es un método de verificación de valores atípicos globales, pero no puede manejar conjuntos de datos en diferentes áreas de densidad, es decir, no puede detectar valores atípicos en áreas de densidad local. En aplicaciones prácticas, no todos los datos se distribuyen con una única densidad. Cuando el conjunto de datos contiene múltiples distribuciones de densidad o es una mezcla de diferentes subconjuntos de densidad, los métodos de detección de valores atípicos globales, como la distancia, generalmente no funcionan bien, porque el hecho de que un objeto sea un valor atípico depende no solo de su relación con los datos circundantes. está relacionado con la densidad del barrio.

1. El concepto de densidad relativa

Desde la perspectiva de la vecindad de densidad, los valores atípicos son objetos en áreas de baja densidad. Por lo tanto, es necesario introducir los conceptos de densidad de vecindad local y densidad relativa de objetos.

Definición 10-14 (1) un objeto$X$de$a$-La densidad local del vecino más cercano (densidad) se define como
$$\text{Distrito}(X,a)=\frac{|D(X,a)|}{\sum _{Y\in D(X,a)}d(X,Y)}\text{\hspace{1em}(10-29)}$$ (2) un objeto$X$de$a$-Densidad relativa local del vecino más cercano (densidad relativa)
$$\text{rdsty}(X,a)=\frac{\sum _{Y\in D(X,a)}\text{Distrito}(X,a)/|D(X,a)|}{\text{Distrito}(X,a)}\text{\hspace{1em}(10-30)}$$ en$D(X,a)$ es el objeto$X$de$a$- vecino más cercano (dado en la Definición 10-12),$|D(X,a)|$ es el número de objetos de la colección.

2. Descripción del algoritmo

por $\text{rdsty}(X,a)$ como un caso atípico${\text{DE}}_2(X,a)$, su cálculo se divide en dos pasos
(1) Según el número de vecinos$a$, calcula cada objeto$X$de$a$-Densidad local del vecino más cercano $\text{Distrito}(X,a)$
(2) Cálculo$X$la densidad media de los vecinos más cercanos y$a$-Densidad relativa local del vecino más cercano $\text{rdsty}(X,a)$
Un conjunto de datos consta de múltiples grupos naturales. La densidad relativa de objetos cerca del punto central dentro del grupo es cercana a 1, mientras que la densidad relativa de objetos en el borde del grupo o fuera del grupo es relativamente grande. Por lo tanto, cuanto mayor sea el valor de densidad relativa, más probable será que sea un valor atípico.

Algoritmo 10-9 Algoritmo de detección de valores atípicos basado en densidad relativa
Entrada: conjunto de datos$S$, el número de vecinos más cercanos$a$
Salida: Lista descendente de puntos atípicos sospechosos y factores atípicos correspondientes
(1) REPETIR
(2) tomar$S$un objeto sin procesar en$X$
(3) OK$X$de$a$-Vecino más cercano$D(X,a)$
(4) Utilización$D(X,a)$calcular$X$Densidad$\text{Distrito}(X,a)$
(5) HASTA$S$Cada punto ha sido procesado.
(6) REPETIR
(7) tomar$S$primer objeto en$X$
(8) Está bien$X$densidad relativa de$\text{rdsty}(X,a)$y asignarlo a${\text{DE}}_2(X,a)$
(9) HASTA$S$Todos los objetos en han sido procesados.
(10) Derecha${\text{DE}}_2(X,a)$Ordenar en orden descendente y salida$(X,{\text{DE}}_2(X,a))$

Ejemplo 10-14 Para el conjunto de datos bidimensional dado en el ejemplo 10-12$S$ (Consulte la Tabla 10-10 para obtener más detalles), por lo que$a=2$, intenta calcular la distancia euclidiana $X_7,X_{10},X_{11}$ Factor de valor atípico basado en la densidad relativa de objetos iguales.

desatar:porque$a=2$, por lo que necesitamos la densidad local de los 2 vecinos más cercanos de todos los objetos.

(1) Encuentre los 2 vecinos más cercanos de cada objeto de datos en la Tabla 10-11 $D(X_i,2)$。
Según el mismo método de cálculo del ejemplo 10-12, podemos obtener
D ( X 1 , 2 ) = { X 2 , X 3 , X 5 } ， D ( X 2 , 2 ) = { X 1 , X 6 } ， D ( X 3 , 2 ) = { X 1 , X 4 } ， D ( X 4 , 2 ) = { X 3 , X 5 } ， D ( X 5 , 2 ) = { X 1 , X 4 , X 6 , X 9 } ， D ( X 6 , 2 ) = { X 2 , X 5 , X 8 } ， D ( X 7 , 2 ) = { X 10 , X 8 } ， D ( X 8 , 2 ) = { X 2 , X 6 } ， D ( X 9 , 2 ) = { X 5 , X 4 , X 6 } ， D ( X 10 , 2 ) = { X 7 , X 8 } ， D ( X 11 , 2 ) = { X 9 , X 5 } $$begin{aligned} &D(X_1,2)={X_2,X_3,X_5}，D(X_2,2)={X_1,X_6}， D(X_3,2)={X_1,X_4}，\ &D(X_4,2)={X_3,X_5}， D(X_5,2)={X_1,X_4,X_6,X_9}，D(X_6,2)={X_2,X_5,X_8}，\ &D(X_7,2)={X_{10},X_8}， D(X_8,2)={X_2,X_6}， D(X_9,2)={X_5,X_4,X_6}，\ &D(X_{10},2)={X_7,X_8}， D(X_{11},2)={X_9,X_5} end{aligned}$$ ​D(X1​,2)={X2​,X3​,X5​}，D(X2​,2)={X1​,X6​}，              D(X3​,2)={X1​,X4​}，D(X4​,2)={X3​,X5​}，       D(X5​,2)={X1​,X4​,X6​,X9​}，D(X6​,2)={X2​,X5​,X8​}，D(X7​,2)={X10​,X8​}，     D(X8​,2)={X2​,X6​}，               D(X9​,2)={X5​,X4​,X6​}，D(X10​,2)={X7​,X8​}，     D(X11​,2)={X9​,X5​}​

(2) Calcule la densidad local de cada objeto de datos. $\text{Distrito}(X_i,2)$：

① Calcular$X_1$Densidad
porque D(X1,2)={X2,X3,X5}D(X1​,2)={X2​,X3​,X5​}, entonces después del cálculo, tenemos $d(X_1,X_2)=1$，$d(X_1,X_3)=1$，$d(X_1,X_5)=1$；
Según la fórmula (10-29), obtenemos:
$$\begin{array}{rl}\text{Distrito}(X_1,2)& =\frac{|D(X_1,2)|}{\sum _{Y\in norte(X_1,2)}d(X_1,Y)}\\ & =\frac{|norte(X_1,2)|}{d(X_1,X_2)+d(X_1,X_3)+d(X_1,X_5)}\\ & =\frac{3}{1+1+1}=1\end{array}$$

② Cálculo$X_2$Densidad
porque D(X2,2)={X1,X6}D(X2​,2)={X1​,X6​}, por lo que el calculado $d(X_2,X_1)=1$，$d(X_2,X_6)=1$；
Según la fórmula (10-29), obtenemos:
$$\begin{array}{rl}\text{Distrito}(X_2,2)& =\frac{|D(X_2,2)|}{\sum _{Y\in norte(X_2,2)}d(X_2,Y)}=\frac{2}{1+1}=1\end{array}$$

La densidad local de otros objetos de datos se puede calcular de manera similar; consulte la Tabla 10-12 a continuación.

(3) Calcular cada objeto$X_i$densidad relativa de $\text{rdsty}(X_i,2)$y considerarlo como un factor atípico ${\text{DE}}_2$。
① Calcular$X_1$densidad relativa de
Usando el valor de densidad de cada objeto en la Tabla 10-12, según la fórmula de densidad relativa (10-30):
$$\begin{array}{rl}\text{rdsty}(X_1,2)& =\frac{\sum _{Y\in norte(X_1,2)}\text{Distrito}(Y,2)/|norte(X_1,2)|}{\text{Distrito}(X_1,2)}\\ & =\frac{(1+1+1)/3}{1}=1={\text{DE}}_2(X_1,2)\end{array}$$

② Se puede obtener un cálculo similar $X_2、X_3、\dots 、X_{11}$ valor de densidad relativa.
Por ejemplo$X_5$La densidad relativa de:
$$\begin{array}{rl}\text{rdsty}(X_5,2)& =\frac{\sum _{Y\in norte(X_5,2)}\text{Distrito}(Y,2)/|norte(X_5,2)|}{\text{Distrito}(X_5,2)}\\ & =\frac{(1+1+1+0.79)/4}{1}=0.95={\text{DE}}_2(X_5,2)\end{array}$$ Los resultados se resumen en las Tablas 10-13 a continuación.

Ejemplo 10-15 Dado el conjunto de datos que se muestra en la Tabla 10-14, utilice la distancia euclidiana para$a=2,3,5$, calcula el valor de cada punto$a$-densidad local del vecino más cercano,$a$-Densidad relativa local del vecino más cercano (factor atípico${\text{DE}}_2$) y basado en$a$-Factor atípico para la distancia del vecino más cercano${\text{DE}}_1$。

desatar: (1) Para facilitar la comprensión, se puede$S$Las posiciones relativas de los puntos están marcadas en el plano bidimensional (Figura 10-30).

(2) Utilice algoritmos basados ​​en distancia y densidad relativa 10-8 y 10-9 respectivamente.Calcula cada objeto por separado.$a$-Densidad local del vecino más cercano$\text{Distrito}$、$a$-Densidad relativa local del vecino más cercano (factor atípico${\text{DE}}_2$) y basado en$a$-Factor atípico para la distancia del vecino más cercano${\text{DE}}_1$, los resultados se resumen en la Tabla 10-15.

(3) Análisis simple
① Como se puede ver en la Figura 10-30,$X_{15}$y$X_{16}$Sí$S$Hay dos valores atípicos obvios, y los métodos basados ​​en la distancia y la densidad relativa pueden detectarlos mejor;
② En este ejemplo, los dos algoritmos tienen$a$No es tan sensible como se esperaba, tal vez sea un caso atípico.$X_{15}$y$X_{16}$La separación de otros objetos es muy obvia.
③Como se puede ver en la Tabla 10-15, no importa$a$Toma 2, 3 o 5,$X_1$de la región $\text{Distrito}$ los valores son significativamente más bajos que$X_7$de la región $\text{Distrito}$ valor, que es consistente con la densidad de área que se muestra en la Figura 10-30.Pero el valor de densidad relativa de las dos regiones${\text{DE}}_2$ Pero casi no hay una diferencia obvia. Esto está determinado por la naturaleza de la densidad relativa, es decir, para puntos de datos distribuidos uniformemente, la densidad relativa de los puntos centrales es 1, independientemente de la distancia entre los puntos.

7. Otros métodos de agrupación

1. Algoritmo de agrupación mejorado

  （1）$a$-modificación ($a$-modos) el algoritmo es para$a$ -El algoritmo promedio sólo es adecuado para la limitación de atributos numéricos y se propone para lograr una agrupación rápida de datos discretos.porque$a$-El algoritmo modular utiliza un método simple de coincidencia 0-1 para calcular la distancia entre dos valores de atributos bajo el mismo atributo discreto, lo que debilita la diferencia entre los valores de atributos ordinales, es decir, no puede reflejar completamente la diferencia entre dos valores de atributos. Bajo el mismo atributo ordinal todavía hay margen de mejora y mejora.
  （2）$a$-prototipo ($a$-Prototipo) algoritmo combinado con$a$-Algoritmo de promediado con$a$ -La ventaja del algoritmo modular es que puede agrupar conjuntos de datos con atributos tanto discretos como numéricos (llamados atributos mixtos).Se necesitan atributos discretos.$a$-Objeto de cálculo de algoritmo modular$X$y$Y$la distancia entre $d_1(X,Y)$, para atributos numéricos, utilice$a$-Los métodos del algoritmo de promediado calculan la distancia entre objetos. $d_2(X,Y)$, y finalmente use el método de ponderación, es decir $\alpha d_1(X,Y)+(1-\alpha )d_2(X,Y)$ como un objeto de conjunto de datos$X$y$Y$la distancia entre $d(X,Y)$,en $\alpha \in [0,1]$ es el coeficiente de peso, generalmente puede ser$\alpha =0.5$。
(3) El algoritmo BIRCH (Reducción iterativa equilibrada y agrupación mediante jerarquías) es un método integral de agrupación jerárquica.Utiliza características de agrupación en clústeres (CF) y un árbol de características de agrupación en clústeres (árbol CF, similar al árbol B) para resumir los grupos de clústeres.$C_i$,en ${\text{CF}}_i=(ni,{\text{LS}}_i,{\text{Espartano}}_i)$ es un triplete,${norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte}_i$es el número de objetos en el grupo,${\text{LS}}_i$Sí${norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte}_i$suma lineal de componentes del objeto,${\text{Espartano}}_i$Sí${norteorteorteorteorteorteorteorteorteorteorteorteorteorteorte}_i$La suma de los cuadrados de los componentes de un objeto.
(4) El algoritmo CURE (agrupación mediante representantes) es para$a$ -Otra mejora al algoritmo de promediado. Muchos algoritmos de agrupación solo son buenos para agrupar grupos esféricos, mientras que algunos algoritmos de agrupación son más sensibles a puntos aislados. Para resolver los dos problemas anteriores, el algoritmo CURE ha cambiado$a$-El algoritmo de promedio utiliza la suma del centro del cluster$a$-El algoritmo de punto central utiliza un solo objeto específico para representar un grupo, un método tradicional, pero utiliza múltiples objetos representativos en el grupo para representar un grupo, de modo que pueda adaptarse a la agrupación de grupos no esféricos y reducir el impacto de ruido al agruparse.
(5) El algoritmo ROCK (RObust Clustering usando linK) es un algoritmo de agrupación propuesto para conjuntos de datos de atributos binarios o categóricos.
(6) El algoritmo OPTICS (Ordenar puntos para identificar la estructura de agrupación) se utiliza para reducir la densidad del algoritmo DBSCAN.$(\epsilon ,\text{MinPts})$ sensibilidad del parámetro. No genera explícitamente grupos de resultados, pero genera una clasificación de grupos aumentada para el análisis de grupos (por ejemplo, un gráfico de coordenadas con la distancia alcanzable como eje vertical y el orden de salida de los puntos de muestra como eje horizontal). Esta clasificación representa la estructura de agrupamiento basada en la densidad de cada punto de muestra.Podemos obtener de esta clasificación en función de cualquier parámetro de densidad.$(\epsilon ,\text{MinPts})$ Resultados de agrupamiento del algoritmo DBSCAN.

2. Otros métodos nuevos de agrupación

Utilice algunas teorías o técnicas nuevas para diseñar nuevos métodos de agrupación.

(1) Método de agrupación en clústeres basado en cuadrículas
El método basado en cuadrícula cuantifica el espacio del objeto en un número limitado de celdas para formar una estructura de cuadrícula, y la información de posición de los puntos divisorios en cada dimensión se almacena en la matriz. Las líneas divisorias atraviesan todo el espacio y todas las agrupaciones. Las operaciones se realizan en Realizadas en esta estructura de cuadrícula (es decir, espacio de cuantificación). La principal ventaja de este método es que su velocidad de procesamiento es muy rápida. Su velocidad de procesamiento es independiente de la cantidad de objetos de datos y solo está relacionada con la cantidad de celdas en cada dimensión del espacio de cuantificación. a expensas de agrupar los resultados. A expensas de la precisión. Dado que el algoritmo de agrupación en cuadrícula tiene el problema de la escala de cuantificación, generalmente comenzamos a buscar grupos a partir de unidades pequeñas primero, luego aumentamos gradualmente el tamaño de las unidades y repetimos este proceso hasta encontrar grupos satisfactorios.

(2) Método de agrupación basado en modelos
Los métodos basados ​​en modelos suponen un modelo para cada grupo y encuentran el mejor ajuste de los datos al modelo dado. Los métodos basados ​​en modelos intentan optimizar la adaptabilidad entre datos dados y ciertos modelos de datos estableciendo funciones de densidad que reflejan la distribución espacial de muestras para ubicar grupos.

(3) Método de agrupación basado en conjuntos difusos
En la práctica, no existe un valor de atribución estricto al que pertenece la mayoría de los objetos. Existe un valor intermedio o incierto en su forma y valor de atribución, lo que es adecuado para la partición suave. Debido a que el análisis de conglomerados difusos tiene la ventaja de describir la intermediación de la atribución de muestras y puede reflejar objetivamente el mundo real, se ha convertido en uno de los puntos calientes en la investigación actual del análisis de conglomerados.
El algoritmo de agrupamiento difuso es un método de aprendizaje no supervisado basado en una teoría matemática difusa y un método de agrupamiento incierto. Una vez que se propuso la agrupación difusa, recibió gran atención por parte de la comunidad académica. La agrupación difusa es una gran "familia" de agrupación, y la investigación sobre la agrupación difusa también es muy activa.

(4) Método de agrupación basado en un conjunto aproximado
La agrupación aproximada es un método de agrupación incierto basado en la teoría de conjuntos aproximados. Desde la perspectiva del acoplamiento entre conjuntos aproximados y algoritmos de agrupamiento, los métodos de agrupamiento aproximado se pueden dividir en dos categorías: agrupamiento aproximado de acoplamiento fuerte y agrupamiento aproximado de acoplamiento débil.
Por supuesto, las nuevas direcciones de investigación del análisis de conglomerados son mucho más que éstas. Por ejemplo, la minería de flujo de datos y los algoritmos de agrupamiento, los datos inciertos y sus algoritmos de agrupamiento, la computación cuántica y los algoritmos de agrupamiento genético cuántico son todas tecnologías de agrupamiento que han surgido en los últimos años. Temas de investigación de vanguardia.

3. Otros métodos de minería atípicos

Los métodos de minería atípica presentados anteriormente son solo dos representantes de la minería atípica. Hay muchos métodos de minería atípicas más maduros en aplicaciones prácticas. Se pueden determinar a partir del tipo de tecnología utilizada en el método de minería o del uso de conocimientos previos. ángulos: grado.

(1) Tipo de tecnología utilizada
Existen principalmente métodos estadísticos, métodos basados ​​en distancia, métodos basados ​​en densidad, métodos basados ​​en agrupaciones, métodos basados ​​en desviaciones, métodos basados ​​en profundidad, métodos basados ​​en transformadas wavelet, métodos basados ​​en gráficos, métodos basados ​​en patrones y redes neuronales. métodos, etc

(2) Utilización de conocimientos previos
Dependiendo de la disponibilidad de información de clase normal o atípica, existen tres enfoques comunes:
① Método de detección de valores atípicos no supervisado, es decir, no existe conocimiento previo, como etiquetas de categorías, en el conjunto de datos;
② Método de detección de valores atípicos supervisados, es decir, extraer las características de los valores atípicos mediante la existencia de un conjunto de entrenamiento que contiene valores atípicos y puntos normales;
③ Método de detección de valores atípicos semisupervisado. Los datos de entrenamiento contienen datos normales etiquetados, pero no hay información sobre los objetos de datos atípicos.