vyhodnocení (nebo „validace“) výsledků shlukování je stejně obtížné jako samotné shlukování. Populární přístupy zahrnují „vnitřní“ hodnocení, kde clustering je shrnout do jediného skóre kvality, „vnější“ hodnocení, kde clustering je ve srovnání se stávající „ground truth“ klasifikace „ruční“ hodnocení lidského expert, a „nepřímé“ hodnocení hodnotící nástroj clusterů v jeho zamýšlené použití.,
interní evaluační opatření trpí problémem, že představují funkce, které samy o sobě mohou být považovány za shlukový cíl. Například by se dalo shlukovat data nastavená koeficientem siluety; kromě toho, že pro to neexistuje žádný známý efektivní algoritmus. Použitím takového interního opatření pro hodnocení se spíše porovnává podobnost optimalizačních problémů a ne nutně to, jak užitečné je shlukování.,
externí hodnocení má podobné problémy: pokud máme takové štítky“ ground truth“, nemuseli bychom se shlukovat; a v praktických aplikacích obvykle takové štítky nemáme. Na druhé straně štítky odrážejí pouze jedno možné rozdělení datové sady, což neznamená, že neexistuje jiný, a možná ještě lepší, shlukování.
žádný z těchto přístupů proto nemůže nakonec posoudit skutečnou kvalitu shlukování, ale to vyžaduje lidské hodnocení, což je vysoce subjektivní., Nicméně takové statistiky mohou být docela informativní při identifikaci špatných shluků, ale neměli bychom odmítnout subjektivní hodnocení člověka.
Vnitřní evaluationEdit
Když clustering výsledek je hodnocen na základě dat, která byla klastru sám, toto je nazýváno vnitřní hodnocení. Tyto metody obvykle přiřazují nejlepší skóre algoritmu, který vytváří klastry s vysokou podobností v clusteru a nízkou podobností mezi klastry., Jednou z nevýhod použití interních kritérií při hodnocení clusteru je, že vysoké skóre na interním opatření nemusí nutně vést k efektivním aplikacím pro vyhledávání informací. Toto hodnocení je navíc zaujaté vůči algoritmům, které používají stejný model clusteru. Například k-znamená shlukování přirozeně optimalizuje objektové vzdálenosti a interní kritérium založené na vzdálenosti pravděpodobně překoná výsledné shlukování.,
Proto je vnitřní hodnocení, která se nejlépe hodí k získat vhled do situace, kde jeden algoritmus provádí lépe než jiné, ale to neznamená, že jeden algoritmus produkuje více platné výsledky než jiný. Platnost měřená takovým indexem závisí na tvrzení, že tento druh struktury existuje v datové sadě. Algoritmus určený pro nějaký druh modelů nemá šanci, pokud datová sada obsahuje radikálně odlišnou sadu modelů nebo pokud hodnocení měří radikálně odlišné kritérium., Například k-znamená shlukování může najít pouze konvexní klastry a mnoho hodnotících indexů předpokládá konvexní klastry. Na datové sadě s nekonvexními klastry není ani použití k-prostředků, ani hodnotícího kritéria, které předpokládá konvexnost, zvuk.
existuje více než tucet Interních hodnotících opatření, obvykle založených na intuici, že položky ve stejném clusteru by měly být podobnější než položky v různých klastrech., následující vzorec: 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)}, kde n je počet shluků, c i {\displaystyle c_{i}} je centroid clusteru jsem {\displaystyle i} , σ já {\displaystyle \sigma _{i}} je průměrná vzdálenost všech prvků v clusteru jsem {\displaystyle i} k těžišti c i {\displaystyle c_{i}} , a d ( c i , c j ) {\displaystyle d(c_{i},c_{j})} je vzdálenost mezi centroidy c i {\displaystyle c_{i}} a c j {\displaystyle c_{j}} ., Protože algoritmy, které produkují shluky s nízkou intra-cluster vzdálenosti (vysoká intra-cluster podobnosti) a vysokou inter-cluster vzdálenosti (nízká inter-cluster podobnosti), bude mít nízký Davies–Bouldin index, clustering algoritmus, který produkuje kolekce shluky s nejmenší Davies–Bouldin index je považován za nejlepší algoritmus na základě tohoto kritéria.
- Dunn index
cílem Dunn indexu je identifikovat husté a dobře oddělené klastry. Je definován jako poměr mezi minimální vzdáleností mezi klastry a maximální vzdáleností uvnitř klastru., Pro každý shluk oddíl, Dunn index může být vypočítán podle následujícího vzorce: D = min 1 ≤ i < j ≤ n d ( i , j ) max 1 ≤ k ≤ n d ( k),, {\displaystyle D={\frac {\min _{1\leq<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,}, kde d(i,j) představuje vzdálenost mezi shluky i a j, a d ‚(k) opatření v rámci clusteru vzdálenost clusteru k. Inter-cluster vzdálenost d(i,j) mezi dvěma shluky může být libovolný počet, vzdálenost, opatření, jako je vzdálenost mezi centroidy clusterů., Stejně tak intra-cluster vzdálenost d(k) může být měřena v mnoha různými způsoby, jako je například maximální vzdálenost mezi libovolnou dvojicí prvků v clusteru k. Od vnitřní kritérium hledat clustery s vysokou intra-cluster podobnosti a nízkou inter-cluster podobnosti, algoritmy, které produkují shluky s vysokou Dunn index jsou více žádoucí.
- koeficient siluety
koeficient siluety kontrastuje průměrnou vzdálenost k prvkům ve stejném clusteru s průměrnou vzdáleností k prvkům v jiných shlucích., Objekty s vysokou hodnotou siluety jsou považovány za dobře seskupené, objekty s nízkou hodnotou mohou být odlehlé. Tento index funguje dobře s K-znamená shlukování a také se používá k určení optimálního počtu klastrů.
Vnější evaluationEdit
V externím hodnocení, clustering výsledky jsou hodnoceny na základě dat, která nebyla použita pro clustering, jako je známý třídy štítky a externích měřítek. Taková měřítka se skládají ze souboru předem klasifikovaných položek a tyto sady jsou často vytvářeny (odbornými) lidmi., Srovnávací sady lze tedy považovat za zlatý standard pro hodnocení. Tyto typy metod hodnocení měří, jak blízko je shlukování k předem stanoveným srovnávacím třídám. Nicméně, to nedávno diskutovalo, zda je to dostatečné pro reálná data, nebo pouze na syntetických datových sad s faktickou pozemní pravdu, od tříd může obsahovat vnitřní strukturu, atributy současnosti neumožňuje separaci skupin nebo tříd může obsahovat anomálie., Navíc z hlediska objevu znalostí nemusí být reprodukce známých znalostí nutně zamýšleným výsledkem. Ve speciální scénář omezených clustering, kde meta informace (jako třídy štítky) se používá již v clustering proces, hold-out informací pro účely hodnocení je non-triviální.
řada opatření je upravena z variant používaných k vyhodnocení klasifikačních úkolů., Místo počítání, kolikrát třídy byl správně přiřazen jeden datový bod (známý jako true positives), tyto dvojice počítání metriky posoudit, zda každou dvojici datových bodů, které je opravdu ve stejném clusteru se předpokládá být ve stejném clusteru.
stejně Jako s interní evaluace, několik externích hodnocení opatření existují,:125-129 například:
- Čistoty: Čistota je měřítkem toho, do jaké míry shluky obsahují jedinou třídu. Jeho výpočet lze považovat za následující: u každého clusteru Spočítejte počet datových bodů z nejběžnější třídy v uvedeném clusteru., Nyní vezměte součet nad všemi klastry a vydělte celkovým počtem datových bodů. Formálně, vzhledem k tomu, některé z hvězdokup M {\displaystyle M} a nějakou sadu tříd D {\displaystyle D} , dělení N {\displaystyle N} datové body, čistoty lze definovat jako:
1 N ∑ m ∈ M max d ∈ D | m ∩ d | {\displaystyle {\frac {1}{N}}\sum _{m\in M}\max _{d\in D}{|m\cap d|}} Toto opatření není trestat, že mnoho klastrů, a více klastrů bude dělat to jednodušší, aby produkovat vysoké čistoty. Skóre čistoty 1 je vždy možné vložením každého datového bodu do vlastního clusteru., Čistota také nefunguje dobře pro nevyvážená data, kde i špatně fungující algoritmy shlukování poskytnou vysokou hodnotu čistoty. Například pokud datový soubor velikosti 1000 sestává ze dvou tříd, z nichž jedna obsahuje 999 bodů a druhá obsahuje 1 bod, pak každý možný oddíl bude mít čistotu nejméně 99,9%.
- Rand index
Rand index vypočítá, jak podobné jsou shluky (vrácené algoritmem shlukování) klasifikacím benchmarku., To může být vypočítána pomocí následujícího vzorce: R I = T P + T N T P + F P + F N + T N {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}}, kde T P {\displaystyle TP} je počet true pozitivní, T, N {\displaystyle TN} je počet pravda, negativy, F P {\displaystyle FP} je počet falešných poplachů, a F N {\displaystyle FN} je počet falešně negativních. Případy, které se zde počítají, jsou počet správných párových přiřazení., To je, T, P, {\displaystyle TP} je počet párů bodů, které jsou seskupeny dohromady v předpokládané oddíl a v zemi pravdu oddíl, F P {\displaystyle FP} je počet párů bodů, které jsou seskupeny dohromady v předpokládané partition, ale ne v zemi pravdu oddíl atd. Pokud má datový soubor velikost N, pak T P + T N + F P + F N = (N 2 ) {\displaystyle TP+TN+FP+FN={\binom {N}{2}}} .
jedním z problémů s indexem Rand je, že falešná pozitiva a falešná negativa jsou stejně vážená. To může být nežádoucí charakteristika některých clusteringových aplikací., F-opatření řeší tento problém, stejně jako index Rand korigovaný šancí.
- F-measure
F-měření mohou být použity k vyvážení příspěvek falešně negativních vážením připomeňme, přes parametr β ≥ 0 {\displaystyle \beta \geq 0} . Ať precision a recall (jak vnější hodnocení opatření v sobě) je definována takto: 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}}}, kde P {\displaystyle P} je přesnost, rychlost a R {\displaystyle R} je sazba odvolání., Můžeme vypočítat F-měření pomocí následujícího vzorce: F β = ( β 2 + 1 ) ⋅ P ⋅ R β 2 ⋅ P + R, {\displaystyle F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}}, Když β = 0 {\displaystyle \beta =0} , F 0 = P {\displaystyle F_{0}=P} . Jinými slovy, odvolání nemá žádný vliv na F-measure, když β = 0 {\displaystyle \beta =0} , a zvýšení β {\displaystyle \beta } přiděluje zvyšující se množství hmotnost odvolání v poslední F-measure. Také T n {\displaystyle TN} se nebere v úvahu a může se lišit od 0 nahoru bez vazby.,
- Jaccard index
Jaccard index se používá ke kvantifikaci podobnosti mezi dvěma soubory údajů. Index Jaccard nabývá hodnoty mezi 0 a 1. Index 1 znamená, že obě datové sady jsou identické a index 0 znamená, že datové sady nemají žádné společné prvky. Na Jaccard index je definován podle následujícího vzorce: J ( A , B ) = | A ∩ B | | A ∪ B | = T P T P + F P + F N {\displaystyle J(A,B)={\frac {|A\cap B|} {|\cup B|}}={\frac {TP}{TP+FP+FN}}} To je prostě počet unikátních prvků společné pro obě sady, děleno celkový počet unikátních prvků v obou sadách., Také T n {\displaystyle TN} se nebere v úvahu a může se lišit od 0 nahoru bez vazby.
- Kostky index
Kostky symetrické opatření zdvojnásobuje váhu na T P {\displaystyle TP}, zatímco stále ignoruje 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 počítá podobnost mezi shluky vrácené clustering algoritmus a referenční klasifikace., Čím vyšší je hodnota indexu Fowlkes-Mallows, tím podobnější jsou klastry a srovnávací klasifikace. To může být vypočítána pomocí následujícího vzorce: 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}}}}}, kde T P {\displaystyle TP} je počet true pozitivní, F P {\displaystyle FP} je počet falešných poplachů, a F N {\displaystyle FN} je počet falešně negativních., F M {\displaystyle FM} index je geometrický průměr precision a recall P {\displaystyle P} a R {\displaystyle R} , a je tedy také známý jako G-opatření, zatímco F-measure je jejich harmonický průměr. Kromě toho, přesnost a odvolání jsou také známé jako Wallace indexy b i {\displaystyle B^{I}} a B i {\displaystyle B^{II}} . Šance normalizované verze odvolání, přesnost a G-opatření odpovídají informovanosti, Markedness a Matthews korelace a silně se vztahují k Kappa.,
- vzájemná informace je informační teoretická míra toho, kolik informací je sdíleno mezi shlukováním a klasifikací ground-truth, která dokáže detekovat nelineární podobnost mezi dvěma shluky. Normalizovaná vzájemná informace je rodina korigovaných variant, která má sníženou zaujatost pro různá čísla klastrů.
- matrice záměny
matici záměny lze použít k rychlé vizualizaci výsledků algoritmu klasifikace (nebo shlukování). Ukazuje, jak odlišný je cluster od zlatého standardního clusteru.,
Clusteru tendencyEdit
změřit clusteru tendence je změřit, do jaké míry klastry existují v data do clusteru, a může být provedena jako počáteční test, před pokusem clustering. Jedním ze způsobů, jak toho dosáhnout, je porovnat data s náhodnými daty. V průměru by náhodná data neměla mít klastry.
- Hopkinsova statistika
existuje více formulací Hopkinsovy statistiky. Typický je následující. Nechť X {\displaystyle X} je sada n {\displaystyle n} datových bodů v D {\displaystyle D} rozměrového prostoru., Zvažte náhodný vzorek (bez náhrady) datových bodů m ≪ n {\displaystyle m\ll n} s členy x i {\displaystyle x_{i}} . Také Vygenerujte sadu Y {\displaystyle Y} m {\displaystyle m} rovnoměrně náhodně distribuovaných datových bodů. Nyní definovat vzdálenost dvou opatření, u jsem {\displaystyle u_{i}}, aby byla vzdálenost z y i ∈ Y {\displaystyle y_{i}\v Y} od svého nejbližšího souseda v X a w i {\displaystyle w_{i}} být vzdálenost x i ∈ X {\displaystyle x_{i}\in X} od svého nejbližšího souseda v X, Pak jsme definovat Hopkins statistiku jako: 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}}}}\,,} S touto definicí, rovnoměrné náhodné údaje by měly tendenci mít v blízkosti hodnoty 0,5, a clustered data by měla tendenci mají hodnoty blíže 1., Data obsahující pouze jeden Gaussian však budou také skóre téměř 1, protože tato statistika měří odchylku od rovnoměrného rozdělení, nikoli multimodality, takže tato statistika je v aplikaci do značné míry zbytečná (protože skutečná data nikdy nejsou vzdáleně jednotná).