avaliação (ou “validação”) dos resultados de clustering é tão difícil quanto a própria clustering. Abordagens populares envolvem avaliação “interna”, onde o agrupamento é resumido a uma única pontuação de qualidade, Avaliação” Externa”, onde o agrupamento é comparado a uma classificação” verdade de terreno “existente, avaliação” manual “por um especialista humano, e avaliação” indireta”, avaliando a utilidade do agrupamento em sua aplicação pretendida.,as medidas de Avaliação Interna sofrem do problema de representarem funções que podem ser vistas como um objectivo de agrupamento. Por exemplo, pode-se agrupar o conjunto de dados pelo coeficiente de silhueta; exceto que não há algoritmo eficiente conhecido para isso. Ao usar tal medida interna para avaliação, compara-se a similaridade dos problemas de otimização, e não necessariamente o quão útil é o agrupamento.,
a avaliação externa tem problemas semelhantes: se tivermos tais rótulos de “verdade de terreno”, então não precisaríamos de agrupar; e em aplicações práticas normalmente não temos tais rótulos. Por outro lado, os rótulos reflectem apenas um possível particionamento do conjunto de dados, o que não implica que não exista um agrupamento diferente, e talvez ainda melhor.
nenhuma destas abordagens pode, portanto, em última análise, julgar a qualidade real de um agrupamento, mas isso precisa de Avaliação Humana, o que é altamente subjetivo., No entanto, tais estatísticas podem ser bastante informativas na identificação de clusterings ruins, mas não se deve descartar a avaliação humana subjetiva.
Interno evaluationEdit
Quando um cluster resultado é avaliado com base nos dados que foi agrupado em si, isso é chamado de avaliação interna. Estes métodos geralmente atribuem a melhor pontuação ao algoritmo que produz clusters com alta similaridade dentro de um cluster e baixa similaridade entre clusters., Uma desvantagem do uso de critérios internos na avaliação de clusters é que Pontuações Elevadas em uma medida interna não resultam necessariamente em aplicações de recuperação de informação eficaz. Além disso, esta avaliação é tendenciosa para algoritmos que usam o mesmo modelo de cluster. Por exemplo, k-means clustering naturally optimizes object distances, and a distance-based internal criterion will likely overrate the resulting clustering.,
portanto, as medidas de avaliação interna são mais adequadas para obter alguma visão de situações em que um algoritmo tem um desempenho melhor do que outro, mas isso não implica que um algoritmo produza resultados mais válidos do que outro. A validade medida por esse índice depende da alegação de que este tipo de estrutura existe no conjunto de dados. Um algoritmo projetado para algum tipo de modelos não tem chance se o conjunto de dados contém um conjunto radicalmente diferente de modelos, ou se a avaliação mede um critério radicalmente diferente., Por exemplo, k-means clustering can only find convex clusters, and many evaluation indexes assum convex clusters. Em um conjunto de dados com aglomerados não convexos, nem o uso de K-means, nem de um critério de avaliação que assume convexidade, é sólido.
Existem mais de uma dúzia de medidas de avaliação interna, geralmente com base na intuição de que os itens no mesmo grupo devem ser mais semelhantes do que os itens em diferentes grupos., seguinte fórmula: D B = 1 n ∑ i = 1 n max j ≠ i ( σ i + σ j d ( c i , c j ) ) {\displaystyle DB={\frac {1}{n}}\sum _{i=1}^{n}\max _{j\neq i}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{i},c_{j})}}\right)}, onde n é o número de clusters, c i {\displaystyle c_{i}} é o centróide do cluster i {\displaystyle i} , σ i {\displaystyle \sigma _{i}} é a distância média de todos os elementos no cluster i {\displaystyle i} para centróide c i {\displaystyle c_{i}} , e d ( c i , c j ) {\displaystyle d(c_{i},c_{j})} é a distância entre os centróides c i {\displaystyle c_{i}} e c j {\displaystyle c_{j}} ., Desde algoritmos que produzem cachos com baixa intra-cluster de distâncias (alta intra-cluster de semelhança) e alta inter-cluster distâncias (baixo inter-cluster de semelhança) terá um baixo Davies–Bouldin índice, o algoritmo de clustering, que produz um conjunto de clusters com o menor Davies–Bouldin índice é considerado o melhor algoritmo baseado neste critério.
- Índice Dunn
o índice Dunn visa identificar aglomerados densos e bem separados. É definida como a relação entre a distância mínima entre os aglomerados e a distância máxima entre eles., Para cada cluster de partição, o índice Dunn pode ser calculado pela seguinte fórmula: D = min 1 ≤ i < j ≤ n d ( i , j ) max 1 ≤ k ≤ n d ‘ ( k ) , {\displaystyle D={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,}, onde d(i,j) representa a distância entre os clusters i e j, e, d ‘(k) medidas intra-cluster distância de cluster k. O inter-cluster distância d(i,j) entre dois clusters pode ser qualquer número de distância de medidas, tais como a distância entre os centróides dos clusters., Da mesma forma, o intra-cluster distância d ‘(k) pode ser medida de diversas maneiras, tais como a distância máxima entre qualquer par de elementos em cluster k. Desde interno critério de buscar clusters com elevado intra-cluster de semelhança e de baixa inter-cluster semelhança, algoritmos que produzem cachos com alto índice Dunn são mais desejáveis. coeficiente de silhueta o coeficiente de silhueta contrasta a distância média aos elementos do mesmo aglomerado com a distância média aos elementos de outros aglomerados., Objetos com alto valor de silhueta são considerados bem agrupados, objetos com baixo valor podem ser anómalos. Este índice funciona bem com K-significa agrupamento, e também é usado para determinar o número ideal de aglomerados.
avaliação externa edit
na avaliação externa, os resultados da agregação são avaliados com base em dados que não foram utilizados para agregação, tais como rótulos de classe conhecidos e marcos de referência externos. Tais benchmarks consistem de um conjunto de itens pré-classificados, e esses conjuntos são muitas vezes criados por humanos (especialistas)., Assim, os conjuntos de referência podem ser pensados como um padrão-ouro para a avaliação. Estes tipos de métodos de avaliação medem até que ponto o agrupamento está próximo das classes de referência pré-determinadas. No entanto, tem sido discutido recentemente se isso é adequado para dados reais, ou apenas em conjuntos de dados sintéticos com uma verdade factual de base, uma vez que as classes podem conter estrutura interna, os atributos presentes podem não permitir a separação de clusters ou as classes podem conter anomalias., Além disso, do ponto de vista da descoberta do conhecimento, a reprodução do conhecimento conhecido pode não ser necessariamente o resultado pretendido. No cenário especial de agrupamento restrito, em que a meta-informação (como etiquetas de classe) já é usada no processo de agrupamento, a retenção de informação para fins de avaliação não é trivial.algumas medidas são adaptadas a partir de variantes utilizadas para avaliar as tarefas de classificação., Em lugar de contar o número de vezes que uma classe foi correctamente atribuídos a um único ponto de dados (conhecido como verdadeiros positivos), tal par de contagem de métricas de avaliar se cada par de pontos de dados que está verdadeiramente no mesmo cluster está previsto para ser no mesmo cluster.tal como na avaliação interna, existem várias medidas de Avaliação Externa:125-129 por exemplo:
- pureza: a pureza é uma medida da medida em que os clusters contêm uma única classe. Seu cálculo pode ser pensado da seguinte forma: para cada conjunto, conte o número de pontos de dados da classe mais comum no referido conjunto., Agora pegue a soma sobre todos os aglomerados e divida pelo número total de pontos de dados. Formalmente, dado um conjunto de clusters M {\displaystyle M} e um conjunto de classes D {\displaystyle D} , tanto de particionamento N {\displaystyle N} de pontos de dados, a pureza pode ser definido como:
1 N ∑ m ∈ M max d ∈ D | m ∩ d | {\displaystyle {\frac {1}{N}}\sum _{m\no M}\max _{d\D}{|m\cap d|}} Esta medida não penalizar ter muitos clusters, e mais clusters vai torná-lo mais fácil produzir um alto grau de pureza. Uma pontuação de pureza de 1 é sempre possível colocando cada ponto de dados em seu próprio conjunto., Além disso, a pureza não funciona bem para dados desequilibrados, onde até mesmo algoritmos de clustering de desempenho deficiente dará um alto valor de pureza. Por exemplo, se um conjunto de dados de tamanho 1000 consiste em duas classes, uma contendo 999 pontos e a outra contendo 1 ponto, então cada partição possível terá uma pureza de pelo menos 99,9%.
- Rand index
O Rand index calcula o quão semelhantes os clusters (retornados pelo algoritmo de clustering) são às classificações de referência., Ele pode ser calculado usando a seguinte fórmula: R I = T P + T a N T e P + F P + F N + T N {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}}, onde T P {\displaystyle TP} é o número de verdadeiros positivos, T N {\displaystyle TN} é o número de verdadeiros negativos, F P {\displaystyle FP} é o número de falsos positivos, e F N {\displaystyle FN} é o número de falso-negativos. As instâncias que estão sendo contadas aqui são o número de atribuições corretas emparelhadas., Isto é, T P {\displaystyle TP} é o número de pares de pontos que estão agrupados em previsões de partição e no chão verdade partição, F P {\displaystyle FP} é o número de pares de pontos que estão agrupados em previsões de partição, mas não no chão verdade partição, etc. Se o conjunto de dados for do tamanho N, Então T P + T N + F P + F n = (n 2 ) {\displaystyle TP+TN+FP+FN={\binom {n}{2}}}}.
um problema com o índice Rand é que falsos positivos e falsos negativos são igualmente ponderados. Esta pode ser uma característica indesejável para algumas aplicações de agrupamento., A medida F aborda esta preocupação, assim como o índice Rand ajustado corrigido por chance.
- F-measure
A F-measure pode ser usada para equilibrar a contribuição de falsos negativos, ponderando a recolha através de um parâmetro β ≥ 0 {\displaystyle \beta \geq 0} . Deixar de precisão e recall (tanto externos como medidas de avaliação em si) ser definida da seguinte forma: P = T P T P T P + F P {\displaystyle P={\frac {TP}{TP+FP}}} R = T P T P T P + F N {\displaystyle R={\frac {TP}{TP+FN}}} onde P {\displaystyle P} é a taxa de precisão e R {\displaystyle R} é o recall de taxa., Podemos calcular o F-measure usando a seguinte fórmula: F β = ( β 2 + 1 ) ⋅ P ⋅ I β 2 ⋅ P + R {\displaystyle F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}} Quando β = 0 {\displaystyle \beta =0} , F 0 = P {\displaystyle F_{0}=P} . Em outras palavras, recall não tem impacto na medida-F Quando β = 0 {\displaystyle \beta =0}, e aumentando β {\displaystyle \beta } aloca uma quantidade crescente de peso para recall na medida-F final. Também o t n {\displaystyle TN} não é tido em conta e pode variar de 0 para cima sem limite.,
- Índice Jaccard
o índice Jaccard é usado para quantificar a semelhança entre dois conjuntos de dados. O índice Jaccard assume um valor entre 0 e 1. Um índice de 1 significa que os dois conjuntos de dados são idênticos, e um índice de 0 indica que os conjuntos de dados não têm elementos comuns. O índice de Jaccard é definido pela seguinte fórmula: J ( A , B ) = | A ∩ B | | A ∪ B | = T P T P T P + F P + F N {\displaystyle J(A,B)={\frac {|Um\cap|B}{|Um\copa do B|}}={\frac {TP}{TP+FP+FN}}} Este é simplesmente o número de elementos comuns a ambos os conjuntos, dividido pelo número total de elementos exclusivos em ambos os conjuntos., Também o t n {\displaystyle TN} não é tido em conta e pode variar de 0 para cima sem limite.
- Dados de índice
Os Dados simétrica medida de dobra o peso em T P {\displaystyle TP} enquanto ainda ignorando T N {\displaystyle TN} : D e S C = 2 T P 2 T P + F P + F N {\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}}
- Fowlkes–Mallows índice
O Fowlkes–Mallows índice calcula a similaridade entre os clusters retornado pelo algoritmo de clustering e o ponto de referência classificações., Quanto maior o valor do Índice Fowlkes–Mallows, mais semelhantes são os clusters e as classificações de referência. Ele pode ser calculado usando a seguinte fórmula: C M = T P T P T P + F P ⋅ T P T P T P + F N {\displaystyle FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}} onde T P {\displaystyle TP} é o número de verdadeiros positivos, F P {\displaystyle FP} é o número de falsos positivos, e F N {\displaystyle FN} é o número de falso-negativos., O índice F m {\displaystyle FM} é a média geométrica da precisão e recolha p {\displaystyle P} E r {\displaystyle R}, e é também conhecido como a medida G, enquanto a medida F é a sua média harmónica. Além disso, a precisão e a recolha são também conhecidas como índices b i {\displaystyle b^{i}} e B i {\displaystyle B^{II}} de Wallace . As versões normalizadas do Chance de recall, precision e G-measure correspondem a Informedness, Markedness e Matthews Correlation e se relacionam fortemente com a Kappa.,
- a informação mútua é uma medida teórica da informação de quanto a informação é compartilhada entre um agrupamento e uma classificação Terra-verdade que pode detectar uma similaridade não-linear entre dois agrupamentos. Informação mútua normalizada é uma família de variantes corrigidas por chance deste que tem um viés reduzido para vários números de clusters.
- matriz de confusão
uma matriz de confusão pode ser usada para visualizar rapidamente os resultados de um algoritmo de classificação (ou agrupamento). Mostra como um conjunto é diferente do padrão-ouro.,
Cluster tendencyEdit
para medir a tendência do cluster é medir o grau de clusters existem nos dados a serem agrupados, e pode ser realizado como um teste inicial, antes de tentar agrupar. Uma maneira de fazer isso é comparar os dados com os dados aleatórios. Em média, os dados aleatórios não devem ter aglomerados.
- Hopkins statistic
existem múltiplas formulações da Estatística Hopkins. Um típico é o seguinte. Que o X {\displaystyle X} seja o conjunto de pontos de dados n {\displaystyle n} no espaço dimensional d {\displaystyle d}., Considere uma amostra aleatória (sem substituição) dos pontos de dados m ≪ n {\displaystyle M\ll n} com os membros x i {\displaystyle x_{i}. Gerar também um conjunto Y {\displaystyle Y} de m {\displaystyle M} uniformemente distribuídos pontos de dados aleatoriamente. Agora definir duas medidas de distância, u i {\displaystyle u_{i}} para ser a distância de y i ∈ U {\displaystyle y_{i}\Y)} a partir de seu mais próximo vizinho em X e w i {\displaystyle w_{i}} para ser a distância de x i ∈ X {\displaystyle x_{i}\X} a partir do seu vizinho mais próximo em X., Podemos, então, definir o Hopkins estatística como: H = ∑ i = 1 m u i a d ∑ i = 1 m u i a d + ∑ i = 1 m i d a , {\displaystyle H={\frac {\sum _{i=1}^{m}{u_{i}^{d}}}{\sum _{i=1}^{m}{u_{i}^{d}}+\sum _{i=1}^{m}{w_{i}^{d}}}}\,,} Com esta definição, uniforme dados aleatórios deve tendem a ter valores próximos a 0,5, e dados de cluster deve tendem a ter valores mais próximos de 1., No entanto, os dados contendo apenas um Gaussiano também marcarão perto de 1, uma vez que esta estatística mede o desvio de uma distribuição uniforme, não a multimodalidade, tornando esta estatística em grande parte inútil na aplicação (como os dados reais nunca são remotamente uniformes).