Siluett (klustring)

Silhouette hänvisar till en metod för tolkning och validering av konsistens inom kluster av data . Tekniken ger en kortfattad grafisk representation av hur väl varje objekt har klassificerats. Det föreslogs av den belgiske statistikern Peter Rousseeuw 1987.

Silhuettvärdet är ett mått på hur likt ett objekt är sitt eget kluster (kohesion) jämfört med andra kluster (separation). Silhuetten sträcker sig från −1 till +1, där ett högt värde indikerar att objektet är väl anpassat till sitt eget kluster och dåligt matchat till angränsande kluster. Om de flesta objekt har ett högt värde är klustringskonfigurationen lämplig. Om många punkter har ett lågt eller negativt värde, kan klustringskonfigurationen ha för många eller för få kluster.

Silhuetten kan beräknas med valfritt avståndsmått , till exempel det euklidiska avståndet eller Manhattan-avståndet .

Definition

En plot som visar siluettpoäng från tre typer av djur från Zoo-datauppsättningen som återges av Orange data mining-svit. Längst ner på tomten identifierar silhuetten delfiner och tumlare som extremvärden i gruppen däggdjur.

Antag att data har klustrats via vilken teknik som helst, såsom k-medoider eller k-medel , till k kluster.

För datapunkt $i\in C_{I}$ (datapunkt i i klustret ${\displaystyle C_{I}})$ , låt

$a(i)={\frac {1}{|C_{I}|-1}}\summa _{j\in C_ {I},i\neq j}d(i,j)$

vara medelavståndet mellan i och alla andra datapunkter i samma kluster, där $|C_{I}|$ är antalet punkter som hör till kluster i , och d(i,j) är avståndet mellan datapunkterna i och j i klustret $C_{I}$ ( vi dividerar med $|C_{I}|-1$ eftersom vi inte inkluderar avståndet d(i,i) i summan). Vi kan tolka a(i) som ett mått på hur väl i är tilldelat dess kluster (ju mindre värde, desto bättre tilldelning).

Vi definierar sedan medelskillnaden mellan punkt i och något kluster $C_{J}$ som medelvärdet av avståndet från i till alla punkter i $C_{J}$ (där $C_{J}\neq C_{I}$ ).

För varje datapunkt $i\in C_{I}$ definierar vi nu

$b(i)=\min _{J\neq I}{\frac {1}{|C_{J}|}}\summa _{j\in C_{J}}d(i,j)$

att vara den minsta (därav operatorn $\min$ i formeln) betyder avståndet för i till alla punkter i något annat kluster (dvs. i ett kluster som i inte är medlem av). Klustret med denna minsta medelskillnad sägs vara det "angränsande klustret" av i eftersom det är det näst bäst passande klustret för punkt i .

Vi definierar nu en siluett (värde) av en datapunkt i

$s(i)={\frac {b(i)-a(i)}{\ max\{a(i),b(i)\}}}$ , om $|C_{I}|>1$

och

$s(i)=0$ , om $|C_{I}|=1$

Vilket också kan skrivas som:

$s(i)={\begin{cases}1-a(i)/b(i),&{\mbox{if }}a(i)< b(i)\\0,&{\mbox{if }}a(i)=b(i)\\b(i)/a(i)-1,&{\mbox{if }}a(i) )>b(i)\\\end{fall}}$

Av definitionen ovan är det tydligt att

$-1\leq s(i)\leq 1$

Observera att a(i) inte är tydligt definierat för kluster med storlek = 1, i vilket fall vi sätter $s(i)=0$ . Detta val är godtyckligt, men neutralt i den meningen att det är i mitten av gränserna, -1 och 1.

För att s(i) ska vara nära 1 kräver vi $a(i)\ll b(i)$ . Eftersom a(i) är ett mått på hur olik i är med sitt eget kluster, betyder ett litet värde att det är väl matchat. Dessutom innebär ett stort b(i) att i är dåligt matchat med dess närliggande kluster. Således betyder ett s(i) nära 1 att data är lämpligt klustrade. Om s(i) är nära -1, så ser vi med samma logik att i skulle vara mer lämpligt om den var klustrad i sitt angränsande kluster. Ett s(i) nära noll betyder att datumet är på gränsen till två naturliga kluster.

Medelvärdet s(i) över alla punkter i ett kluster är ett mått på hur tätt grupperade alla punkter i klustret är. Således är medelvärdet s(i) över all data i hela datamängden ett mått på hur lämpligt data har grupperats. Om det finns för många eller för få kluster, vilket kan inträffa när ett dåligt val av k används i klustringsalgoritmen (t.ex. k-medel ), kommer vissa av klustren typiskt att visa mycket smalare silhuetter än resten. Således kan siluettplottar och medel användas för att bestämma det naturliga antalet kluster inom en datauppsättning. Man kan också öka sannolikheten för att siluetten maximeras vid rätt antal kluster genom att skala om data med hjälp av funktionsvikter som är klusterspecifika.

Kaufman et al. introducerade termen siluettkoefficient för det maximala värdet av medelvärdet s(i) över alla data i hela datasetet, dvs.

$SC=\max _{k}{\tilde {s}}\left(k\right),$

där ${\tilde {s}}\left(k\right)$ representerar medelvärdet s(i) över all data i hela datasetet för ett specifikt antal kluster k .

Förenklad Silhouette och Medoid Silhouette

Beräkning av siluettkoefficienten kräver alla O(N ² ) parvisa avstånd, vilket gör denna utvärdering mycket dyrare än klustring med k-medel. För en klustring med centra $\mu _{C_{I}}$ för varje kluster $C_{I}$ kan vi använda följande förenklade siluett för varje punkt ${ \displaystyle i\in C_{I}}$ istället, som kan beräknas med endast O(Nk) -avstånd:

$a'(i)=d(i,\mu _{C_{I}})$ och $b'(i)=\min _{C_{J}\neq C_{I}}d(i,\mu _{C_{J}})$ ,

som har den ytterligare fördelen att a'(i) alltid definieras, definiera sedan den förenklade siluetten och förenklade siluettkoefficienten

$s'(i)={\frac {b'(i)- a'(i)}{\max\{a'(i),b'(i)\}}}$

$SC'=\max _{k}{\frac {1}{N}}\summa _{i}s'\left(i\right)$ .

Om klustercentrumen är medoider (som i k-medoid-klustring) istället för aritmetiska medel (som i k-medel-klustring), kallas detta också för den medoidbaserade siluetten eller medoidsilhuetten.

Om varje objekt tilldelas närmaste medoid (som i k-medoids-klustring), vet vi att ${\displaystyle a'(i)\leq b'(i)} ,$ och därför $s'(i)={\frac {b '(i)-a'(i)}{b'(i)}}=1-{\frac {a'(i)}{b'(i)}}$ .

Silhouette Clustering

Istället för att använda den genomsnittliga siluetten för att utvärdera en klustring erhållen från t.ex. k-medoider eller k-medel, kan vi försöka direkt hitta en lösning som maximerar silhuetten. Vi har ingen lösning med sluten form för att maximera detta, men det är vanligtvis bäst att tilldela punkter till närmaste kluster enligt dessa metoder. Van der Laan et al. föreslagit att anpassa standardalgoritmen för k-medoider, PAM, för detta ändamål och kalla denna algoritm PAMSIL:

1. Välj initiala medoider genom att använda PAM
2. Beräkna den genomsnittliga siluetten av denna initiala lösning
3. För varje par av en medoid m och en icke-medoid x
   1. byt m och x
   2. beräkna den genomsnittliga siluetten av den resulterande lösningen
   3. kom ihåg det bästa bytet
   4. ta bort m och x för nästa iteration
4. Utför det bästa bytet och återgå till 3, annars sluta om ingen förbättring hittas.

Slingan i steg 3 exekveras för O(Nk) -par och O( ^N3ki involverar beräkning av silhuetten i O(N2 ⁾ , därför behöver denna algoritm )-tid, där i är antalet iterationer.

Eftersom detta är en ganska dyr operation, föreslår författarna att även använda den medoidbaserade siluetten och kallar den resulterande algoritmen PAMMEDSIL. Den behöver O(N ² k ² i) tid.

Batool et al. föreslå en liknande algoritm under namnet OSil, och föreslå en CLARA-liknande samplingsstrategi för större datamängder, som endast löser problemet för ett delprov.

Genom att anta de senaste förbättringarna av PAM-algoritmen, minskar FastMSC körtiden med hjälp av medoidsilhuetten till bara O(N ² i) .

Se även

• Davies–Bouldin index
• Bestämma antalet kluster i en datamängd