Compartilhamento de tecnologia

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

---

5. Avaliação da qualidade do clustering

A análise de cluster consiste em decompor um conjunto de dados em subconjuntos, cada subconjunto é chamado de cluster e o conjunto de todos os subconjuntos é chamado de cluster do conjunto de objetos. Um bom algoritmo de agrupamento deve produzir clusters e clusters de alta qualidade, ou seja, a similaridade geral dentro dos clusters é a mais alta, enquanto a similaridade geral entre os clusters é a mais baixa.Dado que muitos algoritmos de cluster incluem$o$-Algoritmo de média, algoritmo DBSCAN, etc., todos exigem que o usuário especifique o número de clusters no cluster com antecedência$o$, portanto, o método de estimativa simples de k será discutido abaixo.

(1) Estimativa do número de clusters

Muitos algoritmos de clustering, como $o$-Algoritmos de média, até mesmo algoritmos DIANA, etc., precisam especificar o número de clusters com antecedência$o$,e$o$O valor de afetará muito a qualidade do agrupamento. No entanto, o número de clusters deve ser determinado antecipadamente.$o$ Não é uma tarefa fácil. Podemos primeiro considerar dois casos extremos.
(1) Coloque todo o conjunto de dados$S$considerado como um cluster, ou seja, $o=1$, isto parece simples e conveniente, mas os resultados desta análise de cluster não têm valor.
(2) Coloque o conjunto de dados$S$Cada objeto de é tratado como um cluster, ou seja, seja $o=|S|=e$ , produzindo assim o agrupamento mais refinado. Portanto, não há diferença intra-cluster em cada cluster, e a similaridade intra-cluster atinge o nível mais alto.Mas este tipo de agrupamento não pode ser usado para$S$fornecer qualquer informação sobre$S$uma descrição geral.
Pode-se ver que o número de clusters$o$deveria pelo menos satisfazer $2\le o\le e-1$, mas o número de clusters$o$Exatamente qual valor é mais apropriado permanece ambíguo.
Geralmente considerado,$o$O valor de pode ser estimado pela forma e escala da distribuição do conjunto de dados, bem como pela resolução de agrupamento exigida pelo usuário, e os estudiosos têm muitos métodos de estimativa diferentes, como o método do cotovelo, o método de validação cruzada e a teoria da informação- métodos baseados etc.
Um simples e comumente usado$o$O método de estimativa empírica de valor acredita que para aqueles com$e$Um conjunto de dados de objetos, o número de clusters em que ele está agrupado$o$Escolha $\begin{array}{r}\sqrt{\frac{e}{2}}\end{array}$ Isso é apropriado.Neste momento, sob a expectativa média, cada cluster tem aproximadamente$\sqrt{2e}$ objetos.Nesta base, algumas pessoas propuseram outras restrições adicionais, ou seja, o número de clusters$o<\sqrt{e}$。
Por exemplo, suponha$e=8$, então o número de clusters $o=2$ é apropriado, e em média há 4 pontos por cluster, e de acordo com a fórmula empírica adicional$o<2.83$ .Usando essas duas informações sobre o número de clusters$o$A fórmula empírica parece ser explicada de um lado, no Exemplo 10-5 $o=2$ é o número mais apropriado de clusters.

(2) Avaliação externa da qualidade

Se tivermos uma boa estimativa do número de clusters$o$, você pode usar um ou mais métodos de cluster, por exemplo,$o$ -O algoritmo médio, algoritmo hierárquico aglomerativo ou algoritmo DBSCAN realiza análise de cluster em conjuntos de dados conhecidos e obtém uma variedade de resultados de cluster diferentes. A questão agora é qual método apresenta melhores resultados de agrupamento, ou em outras palavras, como comparar os resultados de agrupamento produzidos por diferentes métodos. Esta é a avaliação da qualidade do agrupamento.
Actualmente, existem muitos métodos à escolha para a avaliação da qualidade do agrupamento, mas geralmente podem ser divididos em duas categorias, nomeadamente avaliação da qualidade externa (extrínseca) e avaliação da qualidade interna (intrínseca).
A avaliação externa da qualidade pressupõe que já existe um cluster ideal no conjunto de dados (geralmente construído por especialistas) e compara-o como um método de referência comumente usado com os resultados de agrupamento de um determinado algoritmo. são dois métodos comuns para precisão de classe.

1. Método de entropia de cluster

conjunto de dados hipotético S = { X 1 , X 2 , … , X n } S={X_1,X_2,…,X_n}S={X1​,X2​,…,Xe​},e T = { T 1 , T 2 , … , T m } T={T_1,T_2,…,T_m}E={E1​,E2​,…,Eeu​} é o agrupamento padrão ideal fornecido por especialistas, e C = { C 1 , C 2 , … , C k } C={C_1,C_2,…,C_k}C={C1​,C2​,…,Co​} é determinado por um algoritmo sobre$S$Um cluster de, então para o cluster$C_{eu}$Em relação ao cluster de linha de base$E$A entropia de agrupamento de é definida como
$$E(C_{eu}|E)=-\sum _{eu=1}^{eu}\frac{|C_{eu}\cap E_{eu}|}{|C_{eu}|}{\mathrm{eisg}}_2\frac{|C_{eu}\cap E_{eu}|}{|C_{eu}|}\text{\hspace{1em}(10-20)}$$ e$C$Sobre benchmarks$E$A entropia geral de clustering é definida como todos os clusters$C_{eu}$Sobre benchmarks$E$A média ponderada da entropia de agrupamento, ou seja
$$E(C)=\frac{1}{\sum _{eu=1}^o|C_{eu}|}\sum _{eu=1}^o|C_{eu}|\times E(C_{eu}|E)\text{\hspace{1em}(10-21)}$$ O método de entropia de agrupamento acredita que,$E(C)$ Quanto menor o valor, maior$C$Em relação à linha de base$E$Quanto maior a qualidade do cluster.
É importante notar que o denominador do primeiro termo do lado direito da fórmula (10-21)$\begin{array}{r}\sum _{eu=1}^o|C_{eu}|\end{array}$ é a soma do número de elementos em cada cluster e não pode ser usado$e$ para substituir.Porque só quando$C$Quando é um cluster de particionamento, o denominador é$e$, e o denominador de métodos gerais de agrupamento, como agrupamento DBSCAN, pode ser menor que$e$。

2. Precisão de agrupamento

A ideia básica da avaliação da exatidão (precisão) do cluster é usar o maior número de categorias no cluster como o rótulo da categoria do cluster, ou seja, para o cluster$C_{eu}$,se existir$E_{eu}$fazer ∣ 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|}∣Ceu​∩Eeu​∣=máx.{∣Ceu​∩E1​∣,∣Ceu​∩E2​∣,⋯,∣Ceu​∩Eeu​∣}, considera-se que$C_{eu}$A categoria é$E_{eu}$ .Portanto, o aglomerado$C_{eu}$Sobre benchmarks$E$A precisão é definida 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}Eu(Ceu​∣E)=∣Ceu​∣máx.{∣Ceu​∩E1​∣,∣Ceu​∩E2​∣,⋯,∣Ceu​∩Eeu​∣}​(10-22) e$C$Sobre benchmarks$E$A precisão geral de é definida para todos os clusters$C_{eu}$Sobre benchmarks$E$A média ponderada da precisão do agrupamento, ou seja
$$Eu(C)=\frac{1}{\sum _{eu=1}^o|C_{eu}|}\sum _{eu=1}^o|C_{eu}|\times Eu(C_{eu}|E)\text{\hspace{1em}(10-23)}$$ O método de precisão de agrupamento acredita que,$Eu(C)$ Quanto maior o valor, o agrupamento$C$Em relação à linha de base$E$Quanto maior a qualidade do cluster.
Além disso, geralmente$1-Eu(C)$ chamado$C$Sobre benchmarks$E$ taxa de erro geral.Portanto, a precisão do agrupamento$Eu(C)$ Taxa de erro grande ou geral$1-Eu(C)$ Pequeno, mostra que o algoritmo de agrupamento pode agrupar melhor objetos de diferentes categorias em diferentes agrupamentos, ou seja, a precisão do agrupamento é alta.

(3) Avaliação interna da qualidade

Não existem benchmarks externos conhecidos para avaliação interna da qualidade, apenas conjuntos de dados são usados$S$e agrupamento$C$Para avaliar as características e magnitudes intrínsecas de um cluster$C$ a qualidade de. Ou seja, o efeito de agrupamento é geralmente avaliado calculando a similaridade média dentro dos clusters, a similaridade média entre os clusters ou a similaridade geral.
A avaliação da qualidade interna está relacionada ao algoritmo de agrupamento. O índice de eficácia do agrupamento é usado principalmente para avaliar a qualidade do efeito de agrupamento ou para julgar o número ideal de agrupamentos. maior cluster. Portanto, a eficácia do cluster é geralmente medida por alguma forma de proporção entre a distância intra-cluster e a distância entre clusters. Indicadores comumente usados ​​deste tipo incluem indicador CH, indicador Dunn, indicador I, indicador Xie-eni, etc.

1. Indicador CH

O índice CH é a abreviatura do índice Calinski-Harabasz. Ele primeiro calcula a soma dos quadrados da distância entre cada ponto do cluster e seu centro do cluster para medir a proximidade dentro da classe; entre cada ponto central do cluster e o ponto central do conjunto de dados para medir A separação do conjunto de dados e a relação entre separação e proximidade é o índice CH.
configurar${\overline{X}}_{eu}$representa um aglomerado$C$ponto central (média),$\overline{X}$representa um conjunto de dados$S$o ponto central de$e({\overline{X}}_{eu},\overline{X})$ para${\overline{X}}_{eu}$chegar$\overline{X}$Uma certa função de distância e então agrupamento$C$A compacidade de um cluster intermediário é definida como
$$\text{Vestígio}(A)=\sum _{eu=1}^o\sum _{X_{eu}\in C_{eu}}e(X_{eu},{\overline{X}}_{eu}{)}^2\text{\hspace{1em}(10-24)}$$ Portanto, Trace(A) é o cluster$C$ A soma das distâncias quadradas entre os centros do cluster.E agrupamento$C$O grau de separação é definido como
$$\text{Vestígio}(B)=\sum _{eu=1}^o|C_{eu}|e({\overline{X}}_{eu},\overline{X}{)}^2\text{\hspace{1em}(10-25)}$$ Ou seja, Trace(B) está agrupando$C$Cada ponto central do cluster de$S$A soma ponderada das distâncias quadradas do ponto central de .
A partir disso, se$\begin{array}{r}Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão=\sum _{eu=1}^o|C_{eu}|\end{array}$ Então o indicador CH pode ser definido como
$$V_{\text{CH}}(o)=\frac{\text{Vestígio}(B)/(o-1)}{\text{Vestígio}(A)/(Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão-o)}\text{\hspace{1em}(10-26)}$$ A fórmula (10-26) é geralmente usada nas duas situações a seguir:
(1) Avalie qual agrupamento obtido pelos dois algoritmos é melhor.
Suponha que dois algoritmos sejam usados ​​para analisar o conjunto de dados$S$A análise de cluster foi realizada e dois clusters diferentes (ambos contendo$o$clusters), o agrupamento correspondente ao maior valor de CH é melhor, porque quanto maior o valor de CH significa que cada cluster no cluster está mais próximo de si mesmo e os clusters estão mais dispersos.
(2) Avalie qual dos dois clusters com números diferentes de clusters obtidos pelo mesmo algoritmo é melhor.
Suponha que um algoritmo tenha um conjunto de dados$S$A análise de cluster foi realizada e o número de clusters foi obtido como$o_1$e$b_2$ Dos dois clusters, o resultado do cluster com um valor CH maior é melhor, o que também significa que o número de clusters correspondente a este cluster é mais apropriado.Portanto, aplicando repetidamente a fórmula (10-26), também podemos obter um conjunto de dados$S$O número ideal de clusters para clustering.

2. Indicador Dunn

Indicador Dunn usa clusters$C_{eu}$com cluster$C_{eu}$distância mínima entre $e_e(C_{eu},C_{eu})$ para calcular a separação entre clusters usando o maior diâmetro de cluster entre todos os clusters máx. ⁡ { Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } máx. {varPhi(C_1), varPhi(C_2),...,varPhi(C_k)}máx.{Φ(C1​),Φ(C2​),...,Φ(Co​)} Para caracterizar a rigidez dentro de um cluster, o índice de Dunn é o valor mínimo da razão entre o primeiro e o segundo, ou seja
VD ( k ) = min ⁡ 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}VE​(o)=eu=eumínimo​máx.{Φ(C1​),Φ(C2​),...,Φ(Co​)}ee​(Ceu​,Ceu​)​(10-27) Quanto maior for o valor de Dunn, maior será a distância entre os clusters e melhor será o agrupamento correspondente.Semelhante ao índice de avaliação CH, o índice de Dunn pode ser usado para avaliar a qualidade dos clusters obtidos por diferentes algoritmos, e também pode ser usado para avaliar quais clusters obtidos pelo mesmo algoritmo com diferentes números de clusters são melhores, ou seja, é pode ser usado para procurar$S$o número ideal de clusters.

6. Mineração atípica

Outliers são dados especiais no conjunto de dados que se desviam significativamente da maioria dos dados. O foco dos algoritmos de mineração de dados, como classificação e clustering introduzidos anteriormente, é descobrir padrões regulares que se aplicam à maioria dos dados. Portanto, muitos algoritmos de mineração de dados tentam reduzir ou eliminar o impacto de valores discrepantes e tratar valores discrepantes ao implementar a mineração. ou ignorado como ruído, mas em muitas aplicações práticas, as pessoas suspeitam que o desvio de pontos discrepantes não é causado por fatores aleatórios, mas pode ser causado por outros mecanismos completamente diferentes, que precisam ser escavados para análise e utilização especiais. Por exemplo, em campos de aplicação como gerenciamento de segurança e controle de risco, o padrão de identificação de valores discrepantes é mais valioso do que o padrão de dados normais.

(1) Visão geral de questões relacionadas

A palavra Outlier é geralmente traduzida como outlier, mas também como anomalia. No entanto, existem muitos aliases em diferentes situações de aplicação, como pontos isolados, pontos anormais, pontos novos, pontos de desvio, pontos de exceção, ruído, dados anormais, etc. A mineração atípica tem termos semelhantes, como mineração de dados de anomalias, detecção de dados de anomalias, mineração de dados atípicos, mineração de dados de exceção e mineração de eventos raros na literatura chinesa.

1. A geração de outliers

(1) Os dados provêm de anomalias causadas por fraude, intrusão, surtos de doenças, resultados experimentais incomuns, etc. Por exemplo, a conta telefônica média de alguém é de cerca de 200 yuans, mas aumenta repentinamente para vários milhares de yuans em um determinado mês; o cartão de crédito de alguém geralmente consome cerca de 5.000 yuans por mês, mas em um determinado mês o consumo excede 30.000 yuans, etc. Esses valores discrepantes são geralmente relativamente interessantes na mineração de dados e são um dos principais pontos de aplicação.
(2) Causada por alterações inerentes às variáveis ​​dos dados, refletindo as características naturais da distribuição dos dados, tais como alterações climáticas, novos padrões de compra dos clientes, mutações genéticas, etc. Também uma das áreas de foco interessantes.
(3) Os erros de medição e recolha de dados devem-se principalmente a erro humano, falha do equipamento de medição ou presença de ruído. Por exemplo, a nota -100 de um aluno em um determinado curso pode ser devido ao valor padrão definido pelo programa; Dados razoáveis.

2. Problema de mineração atípico

Normalmente, o problema de mineração atípica pode ser decomposto em três subproblemas para descrever.
(1) Definir valores discrepantes
Como os valores discrepantes estão intimamente relacionados a problemas práticos, definir claramente que tipo de dados são discrepantes ou anormais é a premissa e a principal tarefa da mineração de valores discrepantes. Geralmente, é necessário combinar a experiência e o conhecimento de especialistas no domínio para fornecer orientação sobre. outliers. Forneça uma descrição ou definição apropriada.
(2) Valores discrepantes de mineração
Depois que os pontos discrepantes são claramente definidos, qual algoritmo usar para identificar ou extrair efetivamente os pontos discrepantes definidos é a tarefa principal da mineração de discrepâncias. O algoritmo de mineração de outliers geralmente fornece aos usuários dados de outliers suspeitos da perspectiva de padrões que podem ser refletidos nos dados, de modo a atrair a atenção do usuário.
(3) Entenda os valores discrepantes
Explicação razoável, compreensão e orientação da aplicação prática dos resultados da mineração são os objetivos da mineração atípica. Como o mecanismo pelo qual os outliers são gerados é incerto, se os "outliers" detectados pelo algoritmo de mineração de outliers realmente correspondem ao comportamento anormal real não pode ser explicado e explicado pelo algoritmo de mineração de outliers, mas só pode ser explicado pelo algoritmo de mineração de outliers . Especialistas do setor ou do domínio para compreender e explicar as instruções.

3. Relatividade dos valores discrepantes

Outliers são dados especiais no conjunto de dados que obviamente se desviam da maioria dos dados, mas "obviamente" e "principalmente" são relativos, ou seja, embora os outliers sejam diferentes, eles são relativos. Portanto, há diversas questões a serem consideradas ao definir e explorar valores discrepantes.
(1) Valores discrepantes globais ou locais
Um objeto de dados pode ser um valor atípico em relação aos seus vizinhos locais, mas não em relação a todo o conjunto de dados. Por exemplo, um aluno com 1,9 metros de altura é uma exceção na classe 1 do curso de matemática da nossa escola, mas não é uma exceção entre as pessoas em todo o país, incluindo jogadores profissionais como Yao Ming.
(2) Número de valores discrepantes
Embora o número de pontos discrepantes seja desconhecido, o número de pontos normais deve exceder em muito o número de pontos discrepantes. Ou seja, o número de pontos discrepantes deve representar uma proporção menor no grande conjunto de dados. de pontos discrepantes Deve ser inferior a 5% ou até inferior a 1%.
(3) Fator outlier do ponto
Você não pode usar "sim" ou "não" para informar se um objeto é um outlier. Em vez disso, você deve usar o grau de desvio do objeto, ou seja, o fator outlier (Outlier Factor) ou a pontuação outlier (Outlier Score). caracterizar o desvio de um dado do grau do grupo e, em seguida, filtrar os objetos com fatores discrepantes superiores a um determinado limite, fornecê-los aos tomadores de decisão ou especialistas do domínio para compreensão e explicação e aplicá-los no trabalho prático.

(2) Método baseado em distância

1. Conceitos básicos

Definição 10-11 Existe um número inteiro positivo$o$, objeto$X$de $o$-A distância do vizinho mais próximo é um número inteiro positivo que satisfaz as seguintes condições $e_o(X)$：
(1) exceto$X$Além disso, há pelo menos$o$objetos$E$satisfazer $e(X,E)\le e_o(X)$。
(2) exceto$X$Além disso, há no máximo $o-1$ objetos$E$satisfazer $e(X,E)<e_o(X)$。
em$e(X,E)$ é um objeto$X$e$E$alguma função de distância entre eles.

de um objeto $o$-Quanto maior a distância do vizinho mais próximo, maior a probabilidade de o objeto estar longe da maioria dos dados, então o objeto pode ser$X$de $o$-distância do vizinho mais próximo $e_o(X)$ como seu fator outlier.

Definição 10-12 fazer D ( X , k ) = { Y ∣ d ( X , Y ) ≤ dk ( X ) ∧ Y ≠ X } D(X,k)={Y|d(X,Y)≤d_k(X)cunha Y≠X}E(X,o)={E∣e(X,E)≤eo​(X)∧E=X}, então é chamado $E(X,o)$ sim$X$de $o$-Vizinho mais próximo (domínio).

Pode ser visto na definição 10-12 que$E(X,o)$ Sim$X$como centro, distância$X$Não excede $e_o(X)$ Objeto$E$ A coleção composta por. Vale a pena prestar atenção especial,$X$não pertence a isso $o$-vizinho mais próximo, ou seja, $X\notin E(X,o)$ . Em particular,$X$de $o$-vizinho mais próximo $E(X,o)$ O número de objetos contidos pode exceder em muito$o$,Agora mesmo $|E(X,o)|\ge o$。

Definição 10-13 Existe um número inteiro positivo$o$, objeto$X$de $o$-O fator outlier do vizinho mais próximo é definido como
$${\text{DE}}_1(X,o)=\frac{\sum _{E\in E(X,o)}e(X,E)}{|E(X,o)|}\text{\hspace{1em}(10-28)}$$

2. Descrição do algoritmo

Para um determinado conjunto de dados e o número de distâncias dos vizinhos mais próximos$o$, podemos usar a fórmula acima para calcular o$o$-Fatores discrepantes vizinhos mais próximos e produzi-los em ordem de grande para pequeno. Entre eles, vários objetos com fatores discrepantes maiores têm maior probabilidade de serem discrepantes. Geralmente, eles precisam ser analisados ​​​​e julgados por tomadores de decisão ou especialistas do setor. , Quais pontos são realmente discrepantes.

Algoritmo 10-8 Algoritmo de detecção de valores discrepantes baseado em distância
Entrada: conjunto de dados$S$, o número de distâncias vizinhas mais próximas$o$
Saída: Lista decrescente de pontos suspeitos de valores discrepantes e fatores discrepantes correspondentes
(1) REPETIR
(2) Pegue$S$um objeto não processado em$X$
(3) OK$X$de$o$-vizinho mais próximo$E(X,o)$
(4) Cálculo$X$de$o$-fator discrepante do vizinho mais próximo${\text{DE}}_1(X,o)$
（5）ATÉ$S$Cada ponto foi processado
(6) Sim${\text{DE}}_1(X,o)$Classifique em ordem decrescente e saída$(X,{\text{DE}}_1(X,o))$

3. Exemplos de cálculo

Exemplo 10-12 Um conjunto de dados bidimensional com 11 pontos$S$É dado pela Tabela 10-10, seja$o=2$, use o cálculo da distância euclidiana ao quadrado $X_7,X_{10},X_{11}$ Fator outlier para todos os outros pontos.

desatar: Para compreender intuitivamente o princípio do algoritmo, iremos$S$Os objetos de dados são exibidos no plano da Figura (10-27) abaixo.

Os fatores discrepantes do ponto especificado e de outros pontos são calculados separadamente abaixo.

(1) Objeto de cálculo$X_7$fator atípico
Como pode ser visto na figura, a distância$X_7=(6,8)$ O ponto mais próximo é$X_{10}=(5,7)$,e $e(X_7,X_{10})=1.41$, outros pontos mais próximos podem ser $X_{11}=(5,2)$，$X_9=(3,2)$，$X_8=(2,4)$；
Calculado$e(X_7,X_{11})=6.08$，$e(X_7,X_9)=6.71$，$e(X_7,X_8)=5.66$
porque$o=2$,então $e_2(X_7)=5.66$, então de acordo com a definição 10-11 temos D ( X 7 , 2 ) = { X 10 , X 8 } D(X_7,2)={X_{10},X_8}E(X7​,2)={X10​,X8​}
De acordo com a fórmula (10-28),$X_7$fator atípico
$$\begin{array}{rl}{\text{DE}}_1(X_7,2)& =\frac{\sum _{E\in Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão(X_7,2)}e(X_7,E)}{|Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão(X_7,o)|}=\frac{e(X_7,X_{10})+e(X_7,X_8)}{2}\\ & =\frac{1.41+5.66}{2}=3.54\end{array}$$(2) Objeto de cálculo$X_{10}$fator atípico ${\text{DE}}_1(X_{10},2)=2.83$

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

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

Da mesma forma, os fatores discrepantes dos objetos restantes podem ser calculados, consulte a tabela a seguir (10-11).

4. Limite do fator atípico

de acordo com$o$ -A teoria do vizinho mais próximo, quanto maior o fator outlier, maior a probabilidade de ser um outlier. Portanto, um limite deve ser especificado para distinguir os valores discrepantes dos pontos normais. O método mais simples é especificar o número de pontos discrepantes, mas esse método é muito simples e às vezes perde alguns pontos discrepantes reais ou atribui muitos pontos normais a possíveis pontos discrepantes, o que torna difícil para especialistas no domínio ou tomadores de decisão. na compreensão e interpretação de outliers.
(1) O método de limite de segmentação de fatores discrepantes primeiro organiza os fatores discrepantes em ordem decrescente e, ao mesmo tempo, renumera os objetos de dados em ordem crescente de acordo com os fatores discrepantes.
(2) Com base no fator outlier${\text{DE}}_1(X,o)$ é a ordenada, e o número de série do fator discrepante é a abcissa, ou seja, (número de série,${\text{DE}}_1$valor) são marcados no plano e conectados para formar uma polilinha não crescente, e o ponto onde a polilinha cruza com um declínio acentuado e um declínio suave corresponde ao fator discrepante como o limite Objetos com um fator discrepante menor. iguais ou iguais a este limite são objetos normais, os outros são possíveis valores discrepantes.

Exemplo 10-13 Conjunto de dados para o Exemplo 10-12$S$ , seus fatores discrepantes estão resumidos em ordem decrescente e número de série na Tabela 10-11. Tente encontrar o limite de pontos discrepantes com base no método de limite de segmentação de fator discrepante.

desatar: Primeiro, use o (número de série, ${\text{DE}}_1$ valor) como pontos no plano, marcados no plano e conectados por polilinhas. Conforme mostrado na Figura 10-28 abaixo.

Então, olhando para a Figura 10-28, podemos descobrir que a polilinha à esquerda do quarto ponto (4, 1,27) cai muito acentuadamente, enquanto a polilinha à direita cai muito suavemente. Portanto, o fator outlier 1,27 é selecionado como o fator discrepante 1,27. limite.porque$X_7、X_{10}$ e$X_{11}$ Os fatores discrepantes são 3,54, 2,83 e 2,5, respectivamente, todos maiores que 1,27. Portanto, é mais provável que esses três pontos sejam pontos discrepantes, enquanto os pontos restantes são pontos comuns.
Olhando novamente para a Figura 10-27, podemos descobrir que$X_7、X_{10}$ e$X_{11}$ na verdade, longe da densa maioria dos objetos à esquerda, então trate-os como um conjunto de dados$S$Os valores discrepantes são razoáveis.

5. Avaliação do algoritmo

A maior vantagem do método de detecção de valores discrepantes baseado em distância é que ele é, em princípio, simples e fácil de usar. Suas deficiências refletem-se principalmente nos seguintes aspectos.
(1) Parâmetros$o$A seleção carece de um método simples e eficaz para determinar o impacto dos resultados dos testes nos parâmetros$o$Não existe um resultado analítico universalmente aceito sobre o grau de sensibilidade.
(2) A complexidade do tempo é$O(|S{|}^2)$, carece de escalabilidade para conjuntos de dados em grande escala.
(3) Devido ao uso de um limite de fator atípico global, é difícil extrair valores atípicos em conjuntos de dados com regiões de densidades diferentes.

(3) Método baseado na densidade relativa

O método de distância é um método global de verificação de outliers, mas não consegue lidar com conjuntos de dados em diferentes áreas de densidade, ou seja, não consegue detectar outliers em áreas de densidade local. Em aplicações práticas, os dados não são todos distribuídos com uma única densidade. Quando o conjunto de dados contém múltiplas distribuições de densidade ou é uma mistura de diferentes subconjuntos de densidade, os métodos globais de detecção de valores discrepantes, como a distância, geralmente não funcionam bem, porque o fato de um objeto ser um valor discrepante não depende apenas de sua relação com os dados circundantes. está relacionado à densidade da vizinhança.

1. O conceito de densidade relativa

Do ponto de vista da vizinhança de densidade, os outliers são objetos em áreas de baixa densidade. Portanto, é necessário introduzir os conceitos de densidade de vizinhança local e densidade relativa de objetos.

Definição 10-14 (1) um objeto$X$de$o$-A densidade local do vizinho mais próximo (densidade) é definida como
$$\text{dsty}(X,o)=\frac{|E(X,o)|}{\sum _{E\in E(X,o)}e(X,E)}\text{\hspace{1em}(10-29)}$$ (2) um objeto$X$de$o$- Densidade relativa local do vizinho mais próximo (densidade relativa)
$$\text{rdsty}(X,o)=\frac{\sum _{E\in E(X,o)}\text{dsty}(X,o)/|E(X,o)|}{\text{dsty}(X,o)}\text{\hspace{1em}(10-30)}$$ em$E(X,o)$ É o objeto$X$de$o$- vizinho mais próximo (dado na definição 10-12),$|E(X,o)|$ é o número de objetos na coleção.

2. Descrição do algoritmo

por $\text{rdsty}(X,o)$ como um estranho${\text{DE}}_2(X,o)$, seu cálculo é dividido em duas etapas
(1) De acordo com o número de vizinhos$o$, calcule cada objeto$X$de$o$- Densidade local do vizinho mais próximo $\text{dsty}(X,o)$
(2) Cálculo$X$a densidade média dos vizinhos mais próximos e$o$- Densidade relativa local do vizinho mais próximo $\text{rdsty}(X,o)$
Um conjunto de dados consiste em vários clusters naturais. A densidade relativa de objetos próximos ao ponto central dentro do cluster é próxima de 1, enquanto a densidade relativa de objetos na borda do cluster ou fora do cluster é relativamente grande. Portanto, quanto maior o valor da densidade relativa, maior a probabilidade de ser um valor discrepante.

Algoritmo 10-9 Algoritmo de detecção de outliers baseado na densidade relativa
Entrada: conjunto de dados$S$, o número de vizinhos mais próximos$o$
Saída: Lista decrescente de pontos suspeitos de valores discrepantes e fatores discrepantes correspondentes
(1) REPETIR
(2) Pegue$S$um objeto não processado em$X$
(3) OK$X$de$o$-vizinho mais próximo$E(X,o)$
(4) Utilização$E(X,o)$calcular$X$Densidade$\text{dsty}(X,o)$
（5）ATÉ$S$Cada ponto foi processado
（6）REPETIR
(7) Pegue$S$primeiro objeto em$X$
(8) OK$X$densidade relativa de$\text{rdsty}(X,o)$e atribuí-lo a${\text{DE}}_2(X,o)$
（9）ATÉ$S$Todos os objetos foram processados
(10) Certo${\text{DE}}_2(X,o)$Classifique em ordem decrescente e saída$(X,{\text{DE}}_2(X,o))$

Exemplo 10-14 Para o conjunto de dados bidimensionais fornecido no Exemplo 10-12$S$ (Veja a Tabela 10-10 para detalhes), então$o=2$, tente o cálculo da distância euclidiana $X_7,X_{10},X_{11}$ Fator discrepante baseado na densidade relativa de objetos iguais.

desatar:porque$o=2$, portanto, precisamos da densidade local dos 2 vizinhos mais próximos de todos os objetos.

(1) Encontre o vizinho mais próximo de cada objeto de dados na Tabela 10-11 $E(X_{eu},2)$。
De acordo com o mesmo método de cálculo do Exemplo 10-12, podemos obter
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}$$ ​E(X1​,2)={X2​,X3​,X5​}，E(X2​,2)={X1​,X6​}，              E(X3​,2)={X1​,X4​}，E(X4​,2)={X3​,X5​}，       E(X5​,2)={X1​,X4​,X6​,X9​}，E(X6​,2)={X2​,X5​,X8​}，E(X7​,2)={X10​,X8​}，     E(X8​,2)={X2​,X6​}，               E(X9​,2)={X5​,X4​,X6​}，E(X10​,2)={X7​,X8​}，     E(X11​,2)={X9​,X5​}​

(2) Calcule a densidade local de cada objeto de dados $\text{dsty}(X_{eu},2)$：

① Calcular$X_1$Densidade
porque D ( X 1 , 2 ) = { X 2 , X 3 , X 5 } D(X_1,2)={X_2,X_3,X_5}E(X1​,2)={X2​,X3​,X5​}, então após o cálculo, temos $e(X_1,X_2)=1$，$e(X_1,X_3)=1$，$e(X_1,X_5)=1$；
De acordo com a fórmula (10-29), obtemos:
$$\begin{array}{rl}\text{dsty}(X_1,2)& =\frac{|E(X_1,2)|}{\sum _{E\in Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão(X_1,2)}e(X_1,E)}\\ & =\frac{|Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão(X_1,2)|}{e(X_1,X_2)+e(X_1,X_3)+e(X_1,X_5)}\\ & =\frac{3}{1+1+1}=1\end{array}$$

② Cálculo$X_2$Densidade
porque D ( X 2 , 2 ) = { X 1 , X 6 } D(X_2,2)={X_1,X_6}E(X2​,2)={X1​,X6​}, então o calculado $e(X_2,X_1)=1$，$e(X_2,X_6)=1$；
De acordo com a fórmula (10-29), obtemos:
$$\begin{array}{rl}\text{dsty}(X_2,2)& =\frac{|E(X_2,2)|}{\sum _{E\in Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão(X_2,2)}e(X_2,E)}=\frac{2}{1+1}=1\end{array}$$

A densidade local de outros objetos de dados pode ser calculada de forma semelhante, consulte a Tabela 10-12 abaixo.

(3) Calcule cada objeto$X_{eu}$densidade relativa de $\text{rdsty}(X_{eu},2)$, e considerá-lo como um fator atípico ${\text{DE}}_2$。
① Calcular$X_1$densidade relativa de
Usando o valor da densidade de cada objeto na Tabela 10-12, de acordo com a fórmula da densidade relativa (10-30):
$$\begin{array}{rl}\text{rdsty}(X_1,2)& =\frac{\sum _{E\in Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão(X_1,2)}\text{dsty}(E,2)/|Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão(X_1,2)|}{\text{dsty}(X_1,2)}\\ & =\frac{(1+1+1)/3}{1}=1={\text{DE}}_2(X_1,2)\end{array}$$

② Cálculo semelhante pode ser obtido $X_2、X_3、\dots 、X_{11}$ valor de densidade relativa.
por exemplo$X_5$A densidade relativa de:
$$\begin{array}{rl}\text{rdsty}(X_5,2)& =\frac{\sum _{E\in Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão(X_5,2)}\text{dsty}(E,2)/|Nãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoãoão(X_5,2)|}{\text{dsty}(X_5,2)}\\ & =\frac{(1+1+1+0.79)/4}{1}=0.95={\text{DE}}_2(X_5,2)\end{array}$$ Os resultados estão resumidos nas Tabelas 10-13 abaixo.

Exemplo 10-15 Dado o conjunto de dados mostrado na Tabela 10-14, use a distância euclidiana para$o=2,3,5$, calcule o valor de cada ponto$o$-densidade local do vizinho mais próximo,$o$- Densidade relativa local do vizinho mais próximo (fator discrepante${\text{DE}}_2$) e com base em$o$-Fator outlier para distância do vizinho mais próximo${\text{DE}}_1$。

desatar: (1) Para facilitar a compreensão, pode-se$S$As posições relativas dos pontos estão marcadas no plano bidimensional (Figura 10-30).

(2) Utilize algoritmos baseados em distância e densidade relativa 10-8 e 10-9, respectivamente.Calcule cada objeto separadamente$o$- Densidade local do vizinho mais próximo$\text{dsty}$、$o$- Densidade relativa local do vizinho mais próximo (fator discrepante${\text{DE}}_2$) e com base em$o$-Fator outlier para distância do vizinho mais próximo${\text{DE}}_1$, os resultados estão resumidos na Tabela 10-15.

(3) Análise simples
① Como pode ser visto na Figura 10-30,$X_{15}$e$X_{16}$sim$S$Existem dois valores discrepantes óbvios, e métodos baseados na distância e na densidade relativa podem melhor desenterrá-los;
② A partir deste exemplo, os dois algoritmos têm$o$não é tão sensível quanto o esperado, talvez seja um valor atípico.$X_{15}$e$X_{16}$A separação de outros objetos é muito óbvia.
③Como pode ser visto na Tabela 10-15, não importa$o$Pegue 2, 3 ou 5,$X_1$da região $\text{dsty}$ os valores são significativamente inferiores aos$X_7$da região $\text{dsty}$ valor, que é consistente com a densidade de área mostrada na Figura 10-30.Mas o valor da densidade relativa das duas regiões${\text{DE}}_2$ Mas quase não há diferença óbvia. Isto é determinado pela natureza da densidade relativa, ou seja, para pontos de dados distribuídos uniformemente, a densidade relativa dos pontos centrais é 1, independentemente da distância entre os pontos.

7. Outros métodos de agrupamento

1. Algoritmo de cluster aprimorado

  （1）$o$-mod ($o$-modes) algoritmo é para$o$ -O algoritmo médio é adequado apenas para a limitação de atributos numéricos e é proposto para obter agrupamento rápido de dados discretos.porque$o$-O algoritmo modular usa um método simples de correspondência 0-1 para calcular a distância entre dois valores de atributos sob o mesmo atributo discreto, o que enfraquece a diferença entre valores de atributos ordinais, ou seja, não pode refletir totalmente a diferença entre dois valores de atributos ​​sob o mesmo atributo ordinal Ainda há espaço para melhorias e melhorias.
  （2）$o$-protótipo ($o$-Protótipo) algoritmo combinado com$o$-Algoritmo de média com$o$ -A vantagem do algoritmo modular é que ele pode agrupar conjuntos de dados com atributos discretos e numéricos (chamados de atributos mistos).É necessário para atributos discretos$o$-Objeto de cálculo de algoritmo modular$X$e$E$a distância entre $e_1(X,E)$, para atributos numéricos, use$o$-Métodos no algoritmo de média calculam a distância entre objetos $e_2(X,E)$e, finalmente, use o método de ponderação, ou seja $\alpha e_1(X,E)+(1-\alpha )e_2(X,E)$ como um objeto de conjunto de dados$X$e$E$a distância entre $e(X,E)$,em $\alpha \in [0,1]$ é o coeficiente de peso, geralmente pode ser$\alpha =0.5$。
(3) O algoritmo BIRCH (Balanced Iterative Reduction and Clustering Using Hierarchies) é um método abrangente de agrupamento hierárquico.Ele usa Clustering Features (CF) e Clustering Feature Tree (CF Tree, semelhante à árvore B) para resumir os clusters de clusters.$C_{eu}$,em ${\text{FC}}_{eu}=(não,{\text{LS}}_{eu},{\text{SS}}_{eu})$ é um trigêmeo,$e_{eu}$é o número de objetos no cluster,${\text{LS}}_{eu}$sim$e_{eu}$soma linear dos componentes do objeto;${\text{SS}}_{eu}$sim$e_{eu}$A soma dos quadrados dos componentes de um objeto.
(4) O algoritmo CURE (Clustering Using Representatives) é para$o$ -Outra melhoria no algoritmo de média. Muitos algoritmos de agrupamento são bons apenas para agrupamento de clusters esféricos, enquanto alguns algoritmos de agrupamento são mais sensíveis a pontos isolados. Para resolver os dois problemas acima, o algoritmo CURE mudou$o$-Algoritmo de média usa soma central do cluster$o$-O algoritmo do ponto central usa um único objeto específico para representar um cluster, um método tradicional, mas usa vários objetos representativos no cluster para representar um cluster, para que possa se adaptar ao agrupamento de clusters não esféricos e reduzir o impacto de ruído no agrupamento.
(5) O algoritmo ROCK (RObust Clustering usando linK) é um algoritmo de cluster proposto para conjuntos de dados de atributos binários ou categóricos.
(6) O algoritmo OPTICS (Ordering Points To Identification the Clustering Structure) é usado para reduzir a densidade do algoritmo DBSCAN.$(\epsilon ,\text{Pontos mínimos})$ sensibilidade do parâmetro. Ele não gera explicitamente clusters de resultados, mas gera uma classificação de cluster aumentada para análise de cluster (por exemplo, um gráfico de coordenadas com distância alcançável como eixo vertical e ordem de saída de pontos de amostra como eixo horizontal). Esta classificação representa a estrutura de agrupamento baseada na densidade de cada ponto amostral.Podemos obter desta classificação com base em qualquer parâmetro de densidade$(\epsilon ,\text{Pontos mínimos})$ Clustering de resultados do algoritmo DBSCAN.

2. Outros novos métodos de cluster

Use algumas novas teorias ou técnicas para projetar novos métodos de agrupamento.

(1) Método de cluster baseado em grade
O método baseado em grade quantifica o espaço do objeto em um número limitado de células para formar uma estrutura de grade, e as informações de posição dos pontos divisórios em cada dimensão são armazenadas na matriz. As linhas divisórias percorrem todo o espaço e todo o agrupamento. as operações são realizadas em Executado nesta estrutura de grade (ou seja, espaço de quantização). A principal vantagem deste método é que sua velocidade de processamento é muito rápida. Sua velocidade de processamento é independente do número de objetos de dados e está relacionada apenas ao número de células em cada dimensão do espaço de quantificação. às custas do agrupamento de resultados. Como o algoritmo de agrupamento de grade tem o problema de escala de quantificação, geralmente começamos a procurar clusters a partir de unidades pequenas primeiro, depois aumentamos gradualmente o tamanho das unidades e repetimos esse processo até que clusters satisfatórios sejam encontrados.

(2) Método de agrupamento baseado em modelo
Os métodos baseados em modelo assumem um modelo para cada cluster e encontram o melhor ajuste dos dados ao modelo fornecido. Os métodos baseados em modelos tentam otimizar a adaptabilidade entre determinados dados e determinados modelos de dados, estabelecendo funções de densidade que refletem a distribuição espacial de amostras para localizar clusters.

(3) Método de agrupamento baseado em conjunto fuzzy
Na prática, não existe um valor de atribuição estrito ao qual pertence a maioria dos objetos. Há intermediário ou incerteza em seu valor e forma de atribuição, o que é adequado para particionamento suave. Como a análise de agrupamento difuso tem a vantagem de descrever a intermediação da atribuição da amostra e pode refletir objetivamente o mundo real, ela se tornou um dos pontos críticos na pesquisa atual de análise de agrupamento.
O algoritmo de agrupamento difuso é um método de aprendizagem não supervisionado baseado na teoria matemática difusa e um método de agrupamento incerto. Uma vez proposto o agrupamento difuso, ele recebeu grande atenção da comunidade acadêmica. O agrupamento difuso é uma grande "família" de agrupamento, e a pesquisa sobre agrupamento difuso também é muito ativa.

(4) Método de agrupamento baseado em conjunto aproximado
O agrupamento aproximado é um método de agrupamento incerto baseado na teoria dos conjuntos aproximados. Do ponto de vista do acoplamento entre conjuntos aproximados e algoritmos de agrupamento, os métodos de agrupamento aproximado podem ser divididos em duas categorias: agrupamento bruto de acoplamento forte e agrupamento bruto de acoplamento fraco.
É claro que as novas direções de pesquisa da análise de cluster são muito mais do que estas. Por exemplo, mineração de fluxo de dados e algoritmos de agrupamento, dados incertos e seus algoritmos de agrupamento, computação quântica e algoritmos de agrupamento genético quântico são todas tecnologias de agrupamento que surgiram nos últimos anos. temas de pesquisa de ponta.

3. Outros métodos de mineração atípicos

Os métodos de mineração atípicos introduzidos anteriormente são apenas dois representantes da mineração atípica. Existem muitos métodos de mineração atípicos mais maduros em aplicações práticas. Eles podem ser determinados a partir do tipo de tecnologia usada no método de mineração ou do uso de conhecimento anterior. ângulos: grau.

(1) Tipo de tecnologia utilizada
Existem principalmente métodos estatísticos, métodos baseados em distância, métodos baseados em densidade, métodos baseados em cluster, métodos baseados em desvio, métodos baseados em profundidade, métodos baseados em transformada wavelet, métodos baseados em gráficos, métodos baseados em padrões e redes neurais. métodos, etc.

(2) Utilização de conhecimento prévio
Dependendo da disponibilidade de informações de classe normal ou atípica, existem três abordagens comuns:
① Método de detecção de outliers não supervisionado, ou seja, não há conhecimento prévio, como rótulos de categoria no conjunto de dados;
② Método de detecção de outliers supervisionados, ou seja, extração das características dos outliers através da existência de um conjunto de treinamento contendo outliers e pontos normais;
③ Método de detecção de valores discrepantes semissupervisionados Os dados de treinamento contêm dados normais rotulados, mas não há informações sobre objetos de dados discrepantes.