evaluarea (sau „validarea”) rezultatelor grupării este la fel de dificilă ca gruparea în sine. Abordările populare implică evaluarea „internă”, în care gruparea este rezumată la un singur scor de calitate, evaluarea” externă”, în care gruparea este comparată cu o clasificare existentă” ground truth”, evaluarea” manuală „de către un expert uman și evaluarea” indirectă ” prin evaluarea utilității grupării în aplicația prevăzută.,măsurile de evaluare internă suferă de problema că ele reprezintă funcții care ele însele pot fi văzute ca un obiectiv de grupare. De exemplu, s-ar putea grupa datele stabilite de coeficientul de siluetă; cu excepția faptului că nu există un algoritm eficient cunoscut pentru acest lucru. Folosind o astfel de măsură internă pentru evaluare, se compară mai degrabă similitudinea problemelor de optimizare și nu neapărat cât de utilă este gruparea.,evaluarea externă are probleme similare: dacă avem astfel de etichete „adevăr la sol”, atunci nu ar trebui să ne aglomerăm; iar în aplicații practice, de obicei, nu avem astfel de etichete. Pe de altă parte, etichetele reflectă doar o posibilă partiționare a setului de date, ceea ce nu implică faptul că nu există o grupare diferită și poate chiar mai bună.prin urmare, niciuna dintre aceste abordări nu poate judeca în cele din urmă calitatea reală a unei grupări, dar aceasta are nevoie de o evaluare umană, care este extrem de subiectivă., Cu toate acestea, astfel de statistici pot fi destul de informative în identificarea clusterelor proaste, dar nu ar trebui să respingem evaluarea umană subiectivă.
internal evaluationEdit
când un rezultat de grupare este evaluat pe baza datelor care au fost grupate în sine, aceasta se numește evaluare internă. Aceste metode atribuie, de obicei, cel mai bun scor algoritmului care produce clustere cu similitudine ridicată într-un cluster și similitudine scăzută între clustere., Un dezavantaj al utilizării criteriilor interne în evaluarea clusterului este că scorurile mari pe o măsură internă nu duc neapărat la aplicații eficiente de recuperare a informațiilor. În plus, această evaluare este părtinitoare față de algoritmi care utilizează același model de cluster. De exemplu, K-means clustering optimizează în mod natural distanțele obiectelor, iar un criteriu intern bazat pe distanță va depăși probabil gruparea rezultată.,prin urmare, măsurile de evaluare internă sunt cele mai potrivite pentru a obține o perspectivă asupra situațiilor în care un algoritm are performanțe mai bune decât altul, dar acest lucru nu implică faptul că un algoritm produce rezultate mai valide decât altul. Valabilitatea măsurată de un astfel de indice depinde de afirmația că acest tip de structură există în setul de date. Un algoritm conceput pentru un fel de modele nu are nicio șansă dacă setul de date conține un set radical diferit de modele sau dacă evaluarea măsoară un criteriu radical diferit., De exemplu, K-înseamnă clustering pot găsi numai clustere convexe, și mulți indici de evaluare presupun clustere convexe. Pe un set de date cu clustere ne-convexe, nici utilizarea mijloacelor k, nici a unui criteriu de evaluare care presupune convexitate nu este solidă.există mai mult de o duzină de măsuri de evaluare internă, de obicei bazate pe intuiția că elementele din același cluster ar trebui să fie mai asemănătoare decât elementele din diferite clustere., următoarea formulă: 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)} unde n este numărul de clustere, c i {\displaystyle c_{i}} este centroidul clusterului am {\displaystyle i} , σ m {\displaystyle \sigma _{i}} este distanța medie dintre toate elementele din grup am {\displaystyle i} la centrul de greutate c i {\displaystyle c_{i}} și d ( c i , c j ) {\displaystyle d(c_{i},c_{j})} este distanța între centrele de greutate c i {\displaystyle c_{i}} și c j {\displaystyle c_{j}} ., Deoarece algoritmii care produc clustere cu distanțe intra-cluster scăzute (similitudine intra-cluster ridicată) și distanțe inter-cluster ridicate (similitudine inter-cluster scăzută) vor avea un indice Davies–Bouldin scăzut, algoritmul de grupare care produce o colecție de clustere cu cel mai mic indice Davies–Bouldin este considerat cel mai bun algoritm bazat pe acest criteriu.
- indexul Dunn
indexul Dunn are ca scop identificarea clusterelor dense și bine separate. Acesta este definit ca raportul dintre Distanța minimă inter-cluster la distanța maximă intra-cluster., Pentru fiecare cluster partiție, Dunn indice poate fi calculat prin următoarea formulă: 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)}}\,,}, unde d(i,j) reprezintă distanța dintre grupuri i și j, și d ‘(k) măsuri intra-cluster distanță de cluster k. Inter-cluster distanța d(i,j) între două grupuri poate fi orice număr de distanta de măsuri, cum ar fi distanța dintre centroizii clusterelor., În mod similar, intra-cluster distanța d ‘(k) poate fi măsurată într-o varietate de moduri, cum ar fi distanța maximă între orice pereche de elemente din cluster k. Deoarece interne criteriu caute grupuri cu mare intra-cluster similitudine și joasă inter-cluster similitudine, algoritmi care produc clustere cu mare Dunn index sunt mai de dorit.
- coeficientul de siluetă
coeficientul de siluetă contrastează distanța medie față de elementele din același cluster cu distanța medie față de elementele din alte clustere., Obiectele cu o valoare ridicată a siluetei sunt considerate bine grupate, obiectele cu o valoare scăzută pot fi aberante. Acest indice funcționează bine cu gruparea k-means și este, de asemenea, utilizat pentru a determina numărul optim de clustere.
evaluare Externăedit
în evaluarea externă, rezultatele clustering sunt evaluate pe baza datelor care nu au fost utilizate pentru clustering, cum ar fi etichete de clasă cunoscute și repere externe. Astfel de repere constau dintr-un set de elemente pre-clasificate, iar aceste seturi sunt adesea create de oameni (experți)., Astfel, seturile de referință pot fi considerate ca un standard de aur pentru evaluare. Aceste tipuri de metode de evaluare măsoară cât de aproape este gruparea de clasele de referință predeterminate. Cu toate acestea, s-a discutat recent dacă acest lucru este adecvat pentru date reale sau numai pe seturi de date sintetice cu un adevăr de bază faptic, deoarece clasele pot conține structură internă, atributele prezente nu pot permite separarea clusterelor sau clasele pot conține anomalii., În plus, din punct de vedere al descoperirii cunoștințelor, reproducerea cunoștințelor cunoscute poate să nu fie neapărat rezultatul dorit. În scenariul special de clustering constrâns, unde meta-informațiile (cum ar fi etichetele de clasă) sunt utilizate deja în procesul de clustering, reținerea informațiilor în scopuri de evaluare este non-trivială.o serie de măsuri sunt adaptate din variantele utilizate pentru evaluarea sarcinilor de clasificare., În locul numărării de câte ori o clasă A fost atribuită corect unui singur punct de date (cunoscut sub numele de adevărate pozitive), astfel de valori de numărare a perechilor evaluează dacă fiecare pereche de puncte de date care se află cu adevărat în același cluster este prevăzută a fi în același cluster.
cu evaluarea internă, mai multe evaluarea externă există măsuri,:125-129 de exemplu:
- Puritate: Puritatea este o măsură a gradului în care grupuri conțin o singură clasă. Calculul său poate fi gândit după cum urmează: pentru fiecare cluster, numărați numărul de puncte de date din cea mai comună clasă din clusterul menționat., Acum luați suma peste toate clusterele și împărțiți numărul total de puncte de date. Formal, având în vedere un set de clustere M {\displaystyle M} și un set de clase D {\displaystyle D} , atât de partiționare N {\displaystyle N} de puncte de date, puritate poate fi definit ca:
1 N ∑ m ∈ M max d ∈ D | m ∩ d | {\displaystyle {\frac {1}{N}}\sum _{m\în M}\max _{d\D}{|m\cap d|}} Această măsură nu penaliza cu multe clustere, și mai multe grupuri va face mai ușor pentru a produce o mare puritate. Un scor de puritate de 1 este întotdeauna posibil prin punerea fiecărui punct de date în propriul cluster., De asemenea, puritatea nu funcționează bine pentru datele dezechilibrate, unde chiar și algoritmii de grupare cu performanțe slabe vor da o valoare ridicată de puritate. De exemplu, dacă un set de date de dimensiune 1000 este format din două clase, una conținând 999 de puncte și cealaltă conținând 1 punct, atunci fiecare partiție posibilă va avea o puritate de cel puțin 99,9%.
- Rand index
indicele Rand calculează cât de asemănătoare sunt clusterele (returnate de algoritmul de grupare) cu clasificările de referință., Acesta poate fi calculat folosind următoarea formulă: R I = T P + T N T P + F P + F N + T N {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}} unde T P {\displaystyle TP} este numărul de rezultate fals pozitive, T N {\displaystyle TN} este numărul de adevărat negative, F P {\displaystyle FP} este numărul de rezultate fals pozitive, și F N {\displaystyle FN} este numărul de rezultate fals negative. Cazurile fiind numărate aici sunt numărul de misiuni pereche corecte., Asta este, T P {\displaystyle TP} este numărul de perechi de puncte care sunt grupate împreună în prezis partiție și în pământ adevărul partiție, F P {\displaystyle FP} este numărul de perechi de puncte care sunt grupate împreună în prezis partitie dar nu în pământ adevărul partiție etc. Dacă setul de date este de mărimea N, atunci T P + T N + F P + F N=(N 2 ) {\displaystyle TP+TN+FP+FN = {\binom {n}{2}}} .
o problemă cu indicele Rand este că falsele pozitive și falsele negative sunt ponderate în mod egal. Aceasta poate fi o caracteristică nedorită pentru unele aplicații de grupare., Măsura F abordează această preocupare, la fel ca și indicele Rand ajustat corectat de șanse.
- F-measure
F-măsura poate fi folosit pentru a echilibra contribuția de fals negative prin ponderarea reamintim printr-un parametru β ≥ 0 {\displaystyle \beta \geq 0} . Să precizia și recall (ambele evaluare externă măsuri în ei înșiși) să fie definite după cum urmează: 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}}} unde P {\displaystyle P} este rata de precizie și R {\displaystyle R} este reamintim rata., Putem calcula F-measure, cu ajutorul formulei: F β = ( β 2 + 1 ) ⋅ P ⋅ R β 2 ⋅ P + R {\displaystyle F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}} atunci Când β = 0 {\displaystyle \beta =0} , F 0 = P {\displaystyle F_{0}=P} . Cu alte cuvinte, amintiți-are niciun impact asupra F-measure când β = 0 {\displaystyle \beta =0} , și creșterea β {\displaystyle \beta } alocă o cantitate tot mai mare de greutate să amintim, în final F-measure. De asemenea, T n {\displaystyle tn} nu este luat în considerare și poate varia de la 0 în sus fără a fi legat.,
- Jaccard index
indicele Jaccard este utilizat pentru a cuantifica similitudinea dintre două seturi de date. Indicele Jaccard are o valoare între 0 și 1. Un indice de 1 înseamnă că cele două seturi de date sunt identice, iar un indice de 0 indică faptul că seturile de date nu au elemente comune. La Jaccard index este definit prin următoarea formulă: J ( a , B ) = | A ∩ B | | A ∪ B | = T P T P + F P + F N {\displaystyle J(a,B)={\frac {|A\cap B|}{|O\cupa B|}}={\frac {TP}{TP+FP+FN}}} Acest lucru este pur și simplu numărul de elemente unice, comune pentru ambele seturi împărțit la numărul total de elemente unice în ambele seturi., De asemenea, T n {\displaystyle tn} nu este luat în considerare și poate varia de la 0 în sus fără a fi legat.
- Zaruri index
Zarurile simetric măsură dublează greutatea pe T P {\displaystyle TP} în timp ce încă ignoră T N {\displaystyle TN} : D S C = 2 T P 2 T P + F P + F N {\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}}
- Fowlkes–Mallows index
Fowlkes–Mallows index calculează similitudinea între clustere revenit prin algoritm de clustering și de referință clasificări., Cu cât este mai mare valoarea indicelui Fowlkes–Mallows, cu atât sunt mai similare clusterele și clasificările de referință. Acesta poate fi calculat folosind următoarea formulă: 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}}}}} unde T P {\displaystyle TP} este numărul de rezultate fals pozitive, F P {\displaystyle FP} este numărul de rezultate fals pozitive, și F N {\displaystyle FN} este numărul de rezultate fals negative., F M {\displaystyle FM} index este media geometrică dintre precizia și recall-P {\displaystyle P} și R {\displaystyle R} , și astfel este, de asemenea, cunoscut sub numele de G-măsură, în timp ce F-measure este medie armonică. În plus, precizia și recall sunt, de asemenea, cunoscut sub numele lui Wallace indici B I {\displaystyle B^{I}} și B I I {\displaystyle B^{II}} . Sansa normalizat versiuni de rechemare, precizie și G-măsură corespund Informedness, Markedness și Matthews Corelație și se referă puternic la Kappa.,
- informația reciprocă este o măsură teoretică a informațiilor despre cât de multă informație este împărtășită între o grupare și o clasificare a adevărului la sol care poate detecta o similitudine neliniară între două grupări. Informațiile reciproce normalizate reprezintă o familie de variante corectate pentru șansă, care are o prejudecată redusă pentru diferite numere de cluster.
- matricea de confuzie
o matrice de confuzie poate fi utilizată pentru a vizualiza rapid rezultatele unui algoritm de clasificare (sau grupare). Acesta arată cât de diferit este un cluster de cluster standard de aur.,
Cluster tendencyEdit
Pentru a măsura cluster tendința este de a măsura în ce măsură grupuri există în datele să fie grupate, și poate fi efectuată ca un test inițial, înainte de a încerca clustering. O modalitate de a face acest lucru este de a compara datele cu datele aleatorii. În medie, datele aleatorii nu ar trebui să aibă clustere.există mai multe formulări ale statisticii Hopkins. Unul tipic este după cum urmează. X {\displaystyle X} fie setul de n {\displaystyle n} de puncte de date în d {\displaystyle d} dimensională de spațiu., Ia în considerare un eșantion aleatoriu (fără înlocuire) de m abona n {\displaystyle m\ll n} de puncte de date cu membrii x i {\displaystyle x_{i}} . De asemenea, generați un set y {\displaystyle y} de m {\displaystyle M} puncte de date distribuite uniform aleatoriu. Defini acum două distanta de măsuri, u i {\displaystyle u_{i}} să fi distanța dintre y i ∈ Y {\displaystyle y_{i}\în Y} de cel mai apropiat vecin în X și w i {\displaystyle w_{i}} pentru a fi la distanta de x i ∈ X {\displaystyle x_{i}\în X} de cel mai apropiat vecin în X., Apoi vom defini Hopkins statistice ca: 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}}}}\,,} Cu această definiție, uniformă aleatoare de date ar trebui să tind să aibă valori apropiate la 0,5, și grupate de date ar trebui să tind să aibă valori mai apropiate de 1., Cu toate acestea, datele care conțin doar un singur Gaussian vor înscrie, de asemenea, aproape de 1, deoarece această statistică măsoară abaterea de la o distribuție uniformă, nu multimodalitate, făcând această statistică în mare măsură inutilă în aplicare (deoarece datele reale nu sunt niciodată uniforme de la distanță).