Analisi cluster

La valutazione (o “validazione”) dei risultati del clustering è difficile quanto il clustering stesso. Gli approcci popolari comprendono la valutazione “interna”, in cui il clustering è riassunto in un singolo punteggio di qualità, la valutazione” esterna”, in cui il clustering viene confrontato con una classificazione” ground truth “esistente, la valutazione” manuale “da parte di un esperto umano e la valutazione” indiretta ” valutando l’utilità del clustering nella sua applicazione prevista.,

Le misure di valutazione interna soffrono del problema che rappresentano funzioni che possono essere viste come un obiettivo di clustering. Ad esempio, si potrebbe raggruppare il set di dati in base al coefficiente di Silhouette; tranne per il fatto che non esiste un algoritmo efficiente noto per questo. Usando una tale misura interna per la valutazione, si confronta piuttosto la somiglianza dei problemi di ottimizzazione, e non necessariamente quanto sia utile il clustering.,

La valutazione esterna ha problemi simili: se abbiamo tali etichette “ground truth”, allora non avremmo bisogno di raggruppare; e nelle applicazioni pratiche di solito non abbiamo tali etichette. D’altra parte, le etichette riflettono solo un possibile partizionamento del set di dati, il che non implica che non esista un clustering diverso, e forse anche migliore.

Nessuno di questi approcci può quindi giudicare in ultima analisi la qualità effettiva di un clustering, ma ciò richiede una valutazione umana, che è altamente soggettiva., Tuttavia, tali statistiche possono essere abbastanza istruttive nell’identificare brutti cluster, ma non si dovrebbe ignorare la valutazione umana soggettiva.

Valutazione internaledit

Quando un risultato di clustering viene valutato in base ai dati che sono stati raggruppati, questo è chiamato valutazione interna. Questi metodi di solito assegnano il punteggio migliore all’algoritmo che produce cluster con elevata somiglianza all’interno di un cluster e bassa somiglianza tra cluster., Uno svantaggio dell’utilizzo di criteri interni nella valutazione dei cluster è che i punteggi più alti su una misura interna non comportano necessariamente applicazioni di recupero delle informazioni efficaci. Inoltre, questa valutazione è orientata verso algoritmi che utilizzano lo stesso modello di cluster. Ad esempio, k-means clustering ottimizza naturalmente le distanze degli oggetti e un criterio interno basato sulla distanza probabilmente sovrascriverà il clustering risultante.,

Pertanto, le misure di valutazione interne sono più adatte per ottenere una panoramica delle situazioni in cui un algoritmo esegue meglio di un altro, ma ciò non implica che un algoritmo produca risultati più validi di un altro. La validità misurata da tale indice dipende dall’affermazione che questo tipo di struttura esiste nel set di dati. Un algoritmo progettato per alcuni tipi di modelli non ha alcuna possibilità se il set di dati contiene un insieme radicalmente diverso di modelli o se la valutazione misura un criterio radicalmente diverso., Ad esempio, k-means clustering può trovare solo cluster convessi e molti indici di valutazione assumono cluster convessi. Su un set di dati con cluster non convessi né l’uso di k-means, né di un criterio di valutazione che presuppone la convessità, è valido.

Esistono più di una dozzina di misure di valutazione interne, solitamente basate sull’intuizione che gli elementi nello stesso cluster dovrebbero essere più simili rispetto agli elementi in cluster diversi., seguente formula: B = 1 n ∑ i = 1 n max j ≠ i ( s 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)} dove n è il numero di cluster, c i {\displaystyle c_{i}} è il centroide del cluster {\displaystyle i} , σ i {\displaystyle \sigma _{i}} è la distanza media di tutti gli elementi del cluster di i {\displaystyle i} a baricentro c i {\displaystyle c_{i}} , e d ( c i , c j ) {\displaystyle d(c_{i},c_{j})} è la distanza tra i centroidi c i {\displaystyle c_{i}} e c j {\displaystyle c_{j}} ., Poiché gli algoritmi che producono cluster con basse distanze intra-cluster (alta somiglianza intra-cluster) e alte distanze inter-cluster (bassa somiglianza tra cluster) avranno un basso indice Davies–Bouldin, l’algoritmo di clustering che produce una raccolta di cluster con il più piccolo indice Davies–Bouldin è considerato il migliore algoritmo basato su questo criterio.

• Dunn index

L’indice Dunn ha lo scopo di identificare cluster densi e ben separati. È definito come il rapporto tra la distanza minima tra i cluster e la distanza massima intra-cluster., Per ogni cluster della partizione, la Dunn indice può essere calcolato con la seguente formula: D = min 1 ≤ i < j ≤ n d ( i , j ) max 1 ≤ k ≤ n e d i ‘ ( k) {\displaystyle D={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,} dove p(i,j) rappresenta la distanza tra due cluster di i e j, e d ‘(k) misure intra-cluster distanza di cluster k. Inter-cluster distanza d(i,j) tra due cluster può essere un qualsiasi numero di misure di distanza, come la distanza tra i centroidi dei cluster., Allo stesso modo, la distanza intra-cluster d ‘(k) può essere misurata in vari modi, come la distanza massima tra qualsiasi coppia di elementi nel cluster k. Poiché il criterio interno cerca cluster con elevata somiglianza intra-cluster e bassa somiglianza inter-cluster, gli algoritmi che producono cluster con alto indice Dunn sono più desiderabili.

• Coefficiente silhouette

Il coefficiente silhouette contrasta la distanza media degli elementi nello stesso cluster con la distanza media degli elementi negli altri cluster., Gli oggetti con un valore di silhouette elevato sono considerati ben raggruppati, gli oggetti con un valore basso possono essere valori anomali. Questo indice funziona bene con k-means clustering e viene anche utilizzato per determinare il numero ottimale di cluster.

External evaluationEdit

Nella valutazione esterna, i risultati del clustering vengono valutati in base a dati non utilizzati per il clustering, ad esempio etichette di classe note e benchmark esterni. Tali benchmark consistono in un insieme di elementi pre-classificati e questi set sono spesso creati da esseri umani (esperti)., Pertanto, i set di benchmark possono essere considerati come un gold standard per la valutazione. Questi tipi di metodi di valutazione misurano la vicinanza del clustering alle classi di benchmark predeterminate. Tuttavia, è stato recentemente discusso se questo sia adeguato per dati reali, o solo su set di dati sintetici con una verità di base fattuale, poiché le classi possono contenere una struttura interna, gli attributi presenti potrebbero non consentire la separazione dei cluster o le classi possono contenere anomalie., Inoltre, dal punto di vista della scoperta della conoscenza, la riproduzione della conoscenza conosciuta potrebbe non essere necessariamente il risultato desiderato. Nello scenario speciale del clustering vincolato, in cui le meta informazioni (come le etichette di classe) vengono utilizzate già nel processo di clustering, la sospensione delle informazioni a fini di valutazione non è banale.

Un certo numero di misure sono adattate dalle varianti utilizzate per valutare le attività di classificazione., Invece di contare il numero di volte in cui una classe è stata assegnata correttamente a un singolo punto dati (noto come true positive), tali metriche di conteggio delle coppie valutano se si prevede che ogni coppia di punti dati che si trova nello stesso cluster si trovi nello stesso cluster.

Come per la valutazione interna, esistono diverse misure di valutazione esterna,:125-129 ad esempio:

• Purezza: la purezza è una misura della misura in cui i cluster contengono una singola classe. Il suo calcolo può essere pensato come segue: per ogni cluster, contare il numero di punti dati dalla classe più comune in detto cluster., Ora prendi la somma su tutti i cluster e dividi per il numero totale di punti dati. Formalmente, dato un insieme di cluster M {\displaystyle M} e un insieme di classi D {\displaystyle D} , entrambi di partizionamento N {\displaystyle N} di punti di dati, la purezza può essere definito come:

1 N ∑ m ∈ M max d ∈ D | m ∩ d | {\displaystyle {\frac {1}{N}}\sum _{m\in M}\max _{d\D}{|m\cap d|}} Questa misura non penalizzare avere il numero di cluster, e più cluster renderà più facile per produrre un alto grado di purezza. Un punteggio di purezza di 1 è sempre possibile inserendo ogni punto dati nel proprio cluster., Inoltre, la purezza non funziona bene per i dati squilibrati, dove anche gli algoritmi di clustering poco performanti daranno un valore di elevata purezza. Ad esempio, se un set di dati di dimensione 1000 è costituito da due classi, una contenente 999 punti e l’altra contenente 1 punto, ogni partizione possibile avrà una purezza di almeno il 99,9%.

• Indice Rand

L’indice Rand calcola quanto siano simili i cluster (restituiti dall’algoritmo di clustering) alle classificazioni di benchmark., Esso può essere calcolato utilizzando la seguente formula: R = T P + T N T P + F P + F + N + T N {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}} dove P {\displaystyle TP} è il numero di veri positivi, T N {\displaystyle TN} è il numero di veri negativi, F P {\displaystyle FP} è il numero di falsi positivi, e F N {\displaystyle FN} è il numero di falsi negativi. Le istanze che vengono contate qui sono il numero di assegnazioni corrette a coppie., Cioè, T P {\displaystyle TP} è il numero di coppie di punti che sono raggruppati insieme nella partizione prevista e nella partizione ground truth, F P {\displaystyle FP} è il numero di coppie di punti che sono raggruppati insieme nella partizione prevista ma non nella partizione ground truth ecc. Se il set di dati è di dimensione N, allora T P + T N + F P + F N = (N 2 ) {\displaystyle TP+TN+FP+FN={\binom {N}{2}}} .

Un problema con l’indice Rand è che i falsi positivi e i falsi negativi sono ugualmente ponderati. Questa può essere una caratteristica indesiderabile per alcune applicazioni di clustering., La misura F risponde a questa preoccupazione, così come l’indice Rand corretto con correzione casuale.

• F-measure

La F-measure può essere utilizzata per bilanciare il contributo dei falsi negativi ponderando il richiamo attraverso un parametro β ≥ 0 {\displaystyle \beta \geq 0} . Sia la precisione che il richiamo (entrambe misure di valutazione esterne in sé) siano definiti come segue: P = T P T P + F P {\displaystyle P={\frac {TP}{TP + FP}}} R = T P T P + F N {\displaystyle R={\frac {TP}{TP+FN}}} dove P {\displaystyle P} è la velocità di precisione e R {\displaystyle R} è la velocità di richiamo., Siamo in grado di calcolare la F-misura utilizzando la seguente formula: F β = ( β 2 + 1 ) ⋅ P ⋅ R β 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} . In altre parole, il richiamo non ha alcun impatto sulla misura F quando β = 0 {\displaystyle \ beta =0} e l’aumento di β {\displaystyle \ beta} assegna una quantità crescente di peso da richiamare nella misura F finale. Anche T N {\displaystyle TN} non viene preso in considerazione e può variare da 0 verso l’alto senza bound.,

• Indice Jaccard

L’indice Jaccard viene utilizzato per quantificare la somiglianza tra due set di dati. L’indice Jaccard assume un valore compreso tra 0 e 1. Un indice di 1 indica che i due set di dati sono identici e un indice di 0 indica che i set di dati non hanno elementi comuni. L’indice di Jaccard è definito dalla seguente formula: J ( A , B ) = | A ∩ B | | A ∪ B | = T P T P + F P + F N {\displaystyle J(A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {TP}{TP+FP+FN}}} Questo è semplicemente il numero di elementi comuni ad entrambi gli insiemi diviso per il numero totale di elementi univoci in entrambi i set., Anche T N {\displaystyle TN} non viene preso in considerazione e può variare da 0 verso l’alto senza bound.

• Dadi indice

I Dadi simmetrici misura raddoppia il peso su T P {\displaystyle TP} mentre ancora ignorare T N {\displaystyle TN} : S C = 2 T P 2 T P + F P + F N {\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}}

• Fowlkes–Mallows indice

Il Fowlkes–Mallows indice calcola la somiglianza tra i cluster restituito dall’algoritmo di clustering e il punto di riferimento classificazioni., Più alto è il valore dell’indice Fowlkes–Mallows più simili sono i cluster e le classificazioni di riferimento. Esso può essere calcolato utilizzando la seguente formula: F = M = T P T P + F P ⋅ T P T P + F N {\displaystyle FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}} dove P {\displaystyle TP} è il numero di veri positivi, F P {\displaystyle FP} è il numero di falsi positivi, e F N {\displaystyle FN} è il numero di falsi negativi., L’indice F M {\displaystyle FM} è la media geometrica della precisione e del richiamo P {\displaystyle P} e R {\displaystyle R}, ed è quindi noto anche come G-measure, mentre la F-measure è la loro media armonica. Inoltre, precisione e richiamo sono noti anche come indici di Wallace B I {\displaystyle B^{I}} e B I I {\displaystyle B^{II}}. Possibilità versioni normalizzate di richiamo, precisione e G-measure corrispondono alla Informedness, Markedness e Matthews Correlazione e si riferiscono fortemente a Kappa.,

• L’informazione reciproca è una misura teorica dell’informazione di quanta informazione è condivisa tra un clustering e una classificazione della verità di base che può rilevare una somiglianza non lineare tra due clustering. L’informazione reciproca normalizzata è una famiglia di varianti corrette per caso di questo che ha una polarizzazione ridotta per la variazione dei numeri di cluster.
• Matrice di confusione

Una matrice di confusione può essere utilizzata per visualizzare rapidamente i risultati di un algoritmo di classificazione (o clustering). Mostra quanto sia diverso un cluster dal cluster gold standard.,

Cluster tendencyEdit

Per misurare la tendenza del cluster è quello di misurare fino a che punto i cluster esistono nei dati da raggruppare e possono essere eseguiti come test iniziale, prima di tentare il clustering. Un modo per farlo è confrontare i dati con i dati casuali. In media, i dati casuali non dovrebbero avere cluster.

• Hopkins statistic

Esistono molteplici formulazioni della Hopkins statistic. Un tipico è il seguente. Sia X {\displaystyle X} l’insieme di n {\displaystyle n} punti dati in d {\displaystyle d} spazio dimensionale., Si consideri un campione casuale (senza sostituzione) di m n n {\displaystyle m\ll n} punti dati con membri x i {\displaystyle x_{i}} . Genera anche un set Y {\displaystyle Y} di m {\displaystyle m} punti dati distribuiti in modo uniforme e casuale. Ora definisci due misure di distanza, u i {\displaystyle u_ {i}} per essere la distanza di y i {Y {\displaystyle y_{i}\ in Y} dal suo vicino più vicino in X e w i {\displaystyle w_ {i}} per essere la distanza di x i X X {\displaystyle x_{i}\ in X} dal suo vicino più vicino in X., Abbiamo quindi definire Hopkins, come la statistica: H = ∑ i = 1 m u i d ∑ i = 1 m u i d + ∑ i = 1 m w i d {\displaystyle H={\frac {\sum _{i=1}^{m}{u_{i}^{d}}}{\sum _{i=1}^{m}{u_{i}^{d}}+\sum _{i=1}^{m}{w_{i}^{d}}}}\,,} Con questa definizione uniforme di dati casuali, dovrebbe tendere a valori vicino a 0,5, e di cluster di dati deve tendono ad avere valori più vicino a 1., Tuttavia, i dati contenenti solo un singolo gaussiano segneranno anche vicino a 1, poiché questa statistica misura la deviazione da una distribuzione uniforme, non la multimodalità, rendendo questa statistica in gran parte inutile nell’applicazione (poiché i dati reali non sono mai lontanamente uniformi).