Analiza klastrów

ocena (lub „Walidacja”) wyników klastrowania jest równie trudna, jak samo klastrowanie. Popularne podejścia obejmują” wewnętrzną ” ocenę, w której klastrowanie jest podsumowane do jednego wyniku jakości,” zewnętrzną „ocenę, w której klastrowanie jest porównywane z istniejącą klasyfikacją „prawdy gruntowej”, „ręczną” ocenę przez eksperta ludzkiego i „pośrednią” ocenę poprzez ocenę użyteczności klastra w jego zamierzonym zastosowaniu.,

Na przykład, można klastra zbiór danych przez współczynnik sylwetki; z tym wyjątkiem, że nie jest znany skuteczny algorytm dla tego. Używając takiej wewnętrznej miary do oceny, porównuje się raczej podobieństwo problemów optymalizacyjnych, a niekoniecznie użyteczność klastrowania.,

ocena zewnętrzna ma podobne problemy: gdybyśmy mieli takie etykiety „prawdy gruntowej”, to nie musielibyśmy gromadzić; a w zastosowaniach praktycznych zwykle nie mamy takich etykiet. Z drugiej strony, etykiety odzwierciedlają tylko jeden możliwy podział zbioru danych, co nie oznacza, że nie istnieje inny, a może nawet lepszy, klastrowanie.

żadne z tych podejść nie może zatem ostatecznie ocenić rzeczywistej jakości klastrów, ale wymaga to ludzkiej oceny, która jest wysoce subiektywna., Niemniej jednak takie statystyki mogą być dość pouczające w identyfikowaniu złych klastrów, ale nie należy lekceważyć subiektywnej oceny człowieka.

ocena Wewnętrznaedytuj

gdy wynik klastrowania jest oceniany na podstawie danych, które zostały same klastrowane, nazywa się to oceną wewnętrzną. Metody te zwykle przypisują najlepszy wynik algorytmowi, który wytwarza klastry o wysokim podobieństwie w klastrze i niskim podobieństwie między klastrami., Jedną z wad stosowania kryteriów wewnętrznych w ocenie klastra jest to, że wysokie wyniki w miarach wewnętrznych niekoniecznie skutkują skutecznymi aplikacjami do wyszukiwania informacji. Dodatkowo, ocena ta jest tendencyjna w kierunku algorytmów, które używają tego samego modelu klastra. Na przykład, K-oznacza klastrowanie w naturalny sposób optymalizuje odległości obiektów, a wewnętrzne kryterium oparte na odległości prawdopodobnie przekroczy wynik klastrowania.,

dlatego środki oceny wewnętrznej najlepiej nadają się do uzyskania pewnego wglądu w sytuacje, w których jeden algorytm działa lepiej niż inny, ale nie oznacza to, że jeden algorytm daje bardziej poprawne wyniki niż inny. Ważność mierzona takim wskaźnikiem zależy od twierdzenia, że taka struktura istnieje w zbiorze danych. Algorytm zaprojektowany dla pewnego rodzaju modeli nie ma szans, jeśli zbiór danych zawiera radykalnie inny zestaw modeli, lub jeśli ocena mierzy radykalnie inne kryterium., Na przykład, K-oznacza klastry mogą znajdować tylko klastry wypukłe, a wiele indeksów ewaluacyjnych zakłada klastry wypukłe. Na zbiorze danych z klastrami nie wypukłymi ani użycie K-środków, ani kryterium oceny, które zakłada wypukłość, nie jest prawidłowe.

istnieje ponad tuzin środków oceny wewnętrznej, Zwykle opartych na intuicji, że pozycje w tym samym klastrze powinny być bardziej podobne niż pozycje w różnych klastrach., zgodnie ze wzorem: 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)} gdzie n jest liczbą klastrów, c i {\displaystyle C}}. {\displaystyle C_ {i}} jest centroidem klastra i {\displaystyle i}, σ i {\displaystyle\Sigma _{i}} jest średnią odległością wszystkich elementów w klastrze i {\displaystyle i} do centroida C i {\displaystyle C_ {i}}, A D ( C i , c j) {\displaystyle d(C_{i}, C_ {J})} jest odległością między centroidami C i {\displaystyle C_ {i}} I c j {\displaystyle C_ {j}}., Ponieważ algorytmy wytwarzające klastry o niskich odległościach wewnątrz klastrów (wysokie podobieństwo wewnątrz klastrów) i wysokich odległościach między klastrami (niskie podobieństwo między klastrami) będą miały niski indeks Daviesa-Bouldina, algorytm klastrów wytwarzający zbiór klastrów o najmniejszym indeksie Daviesa–Bouldina jest uważany za najlepszy algorytm oparty na tym kryterium.

• indeks Dunna

indeks Dunna ma na celu identyfikację gęstych i dobrze oddzielonych gromad. Jest on zdefiniowany jako stosunek minimalnej odległości między klastrami do maksymalnej odległości wewnątrz klastrów., Dla każdego podziału klastra indeks Dunna można obliczyć według następującego wzoru: 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)}}\,} gdzie D(I, J) reprezentuje odległość między klastrami i I J, A D '(K) mierzy odległość wewnątrz klastra K. odległość między klastrami D(I,J) między dwoma klastrami może być dowolną liczbą miar odległości, takich jak odległość między centroidami klastrów. , Podobnie odległość wewnątrz klastra d '(k) może być mierzona na różne sposoby, takie jak maksymalna odległość między dowolnymi parami elementów w klastrze K. ponieważ kryterium wewnętrzne poszukuje klastrów o wysokim podobieństwie wewnątrz klastra i niskim podobieństwie między klastrami, algorytmy, które produkują klastry o wysokim indeksie Dunna są bardziej pożądane.

• współczynnik sylwetki

współczynnik sylwetki kontrastuje średnią odległość do elementów w tej samej gromadzie ze średnią odległością do elementów w innych gromadach., Obiekty o wysokiej wartości sylwetki są uważane za dobrze zgrupowane, obiekty o niskiej wartości mogą być odstające. Indeks ten dobrze współpracuje z k-means clustering, a także służy do określenia optymalnej liczby klastrów.

ewaluacja Zewnętrznaedytuj

w ewaluacji zewnętrznej wyniki grupowania są oceniane na podstawie danych, które nie były używane do grupowania, takich jak znane etykiety klas I Zewnętrzne benchmarki. Takie wzorce składają się z zestawu wstępnie sklasyfikowanych przedmiotów, a te zestawy są często tworzone przez (ekspertów) ludzi., W związku z tym zestawy wskaźników można traktować jako złoty standard oceny. Te rodzaje metod oceny mierzą, jak blisko klastrów jest do wcześniej określonych klas wzorcowych. Jednak niedawno dyskutowano, czy jest to odpowiednie dla rzeczywistych danych, czy tylko na syntetycznych zestawach danych z rzeczywistą prawdą gruntową, ponieważ klasy mogą zawierać wewnętrzną strukturę, obecne atrybuty mogą nie pozwalać na rozdzielenie klastrów lub klasy mogą zawierać anomalie., Dodatkowo, z punktu widzenia odkrywania wiedzy, reprodukcja znanej wiedzy niekoniecznie musi być zamierzonym rezultatem. W specjalnym scenariuszu ograniczonego klastrowania, gdzie meta informacje (takie jak etykiety klas) są używane już w procesie klastrowania, wstrzymanie informacji do celów oceny jest nietrywialne.

z wariantów stosowanych do oceny zadań klasyfikacyjnych zaadaptowano szereg miar., W miejsce zliczania liczby razy klasa została poprawnie przypisana do pojedynczego punktu danych( znany jako true positives), takie pary liczenie metryki ocenić, czy każda para punktów danych, które jest rzeczywiście w tym samym klastrze przewiduje się, że w tym samym klastrze.

podobnie jak w przypadku oceny wewnętrznej, istnieje kilka miar oceny zewnętrznej, np. 125-129:

• czystość: czystość jest miarą stopnia, w jakim klastry zawierają jedną klasę. Jego obliczenia można rozpatrywać w następujący sposób: dla każdego klastra policz liczbę punktów danych z najczęściej spotykanej klasy w danym klastrze., Teraz weź sumę wszystkich klastrów i podziel przez całkowitą liczbę punktów danych. Formalnie, biorąc pod uwagę pewien zbiór klastrów M {\displaystyle M} i pewien zbiór Klas D {\displaystyle D} , oba partycjonujące n {\displaystyle N} punkty danych, czystość może być zdefiniowana 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|}} ta miara nie penalizuje wiele klastrów i więcej klastrów ułatwi produkcję wysokiej czystości. Wynik czystości 1 jest zawsze możliwy dzięki umieszczeniu każdego punktu danych we własnym klastrze., Również czystość nie działa dobrze w przypadku danych niezrównoważonych, gdzie nawet słabo działające algorytmy klastrowania dają wysoką wartość czystości. Na przykład, jeśli zbiór danych o rozmiarze 1000 składa się z dwóch klas, jedna zawiera 999 punktów, a druga zawiera 1 punkt, to każda możliwa partycja będzie miała czystość co najmniej 99.9%.

• indeks Rand

indeks Rand oblicza, jak podobne są klastry (zwracane przez algorytm klastrowania) do klasyfikacji benchmarków., Można ją obliczyć za pomocą następującego wzoru: R I = T P + T N T P + F P + F N + t n {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}} gdzie T P {\displaystyle TP} jest liczbą prawdziwych pozytywów, T n {\displaystyle TN} jest liczbą prawdziwych negatywów, F P {\displaystyle FP} jest liczbą fałszywych pozytywów, a F N {\displaystyle displaystyle FN} to liczba fałszywych negatywów. Instancje, które są tu liczone, to liczba prawidłowych przypisań parowych., T P {\displaystyle TP} jest liczbą par punktów, które są zgrupowane razem w przewidywanej partycji i w partycji prawdy gruntowej, F P {\displaystyle FP} jest liczbą par punktów, które są zgrupowane razem w przewidywanej partycji, ale nie w partycji prawdy gruntowej itp. Jeśli zbiór danych jest wielkości N, to T P + T N + F P + F N = (N 2) {\displaystyle TP + TN + FP + FN={\binom {N} {2}}}.

jednym z problemów z indeksem Rand jest to, że fałszywie dodatnie i fałszywie ujemne są jednakowo ważone. Może to być niepożądana cecha dla niektórych aplikacji klastrowych., F-measure rozwiązuje ten problem, podobnie jak indeks Rand skorygowany o przypadek.

• f-measure

f-measure może być użyty do zrównoważenia udziału fałszywych negatywów przez ważenie przypomnienia za pomocą parametru β ≥ 0 {\displaystyle \beta \geq 0} . Niech precyzja i przypomnienie (obie zewnętrzne miary oceny same w sobie) będą zdefiniowane w następujący sposób: 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}}} gdzie p {\displaystyle P} to szybkość precyzji, A R {\displaystyle R} to szybkość przywoływania., Możemy obliczyć miarę F używając następującego wzoru: f β = (β 2 + 1) ⋅ p ⋅ r β 2 ⋅ P + R {\displaystyle f_ {\beta} ={\frac {(\beta ^ {2}+1) \ cdot p \ cdot R} {\beta ^{2} \ cdot P + R}}}} gdy β = 0 {\displaystyle \ beta = 0}, F 0 = p {\displaystyle F_{0}=P}. Innymi słowy, przypomnienie nie ma wpływu na F-miarę, gdy β = 0 {\displaystyle \beta =0}, a zwiększenie β {\displaystyle \ beta} przydziela rosnącą ilość masy do przywołania w końcowym f-miarze. Również T n {\displaystyle TN} nie jest brane pod uwagę i może różnić się od 0 w górę bez wiązania.,

• indeks Jaccarda

indeks Jaccarda jest używany do ilościowego określenia podobieństwa między dwoma zestawami danych. Indeks Jaccard przyjmuje wartość od 0 do 1. Indeks 1 oznacza, że dwa zbiory danych są identyczne, a indeks 0 oznacza, że zbiory danych nie mają wspólnych elementów. Indeks Jaccard definiuje się wzorem: 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}}}} jest to po prostu liczba unikalnych elementów wspólnych dla obu zbiorów podzielona przez całkowitą liczbę unikalnych elementów w obu zbiorach., Również T n {\displaystyle TN} nie jest brane pod uwagę i może różnić się od 0 w górę bez wiązania.

• indeks Kości

miara symetryczna Kości podwaja wagę na T P {\displaystyle TP} przy jednoczesnym ignorowaniu t n {\displaystyle TN} : D S C = 2 T P 2 T P + F P + F n {\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}

• indeks Fowlkes–Mallows

indeks Fowlkes–Mallows oblicza podobieństwa między klastrami zwracanymi przez algorytm klastrowania a klasyfikacjami benchmarków., Im wyższa wartość wskaźnika Fowlkes-Mallows, tym bardziej podobne są klastry i klasyfikacje benchmarkowe. Można ją obliczyć za pomocą następującego wzoru: 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}}}}}} gdzie T P {\displaystyle TP} jest liczbą true positives, F P {\displaystyle FP} jest liczbą false positives, A F N {\displaystyle FN} jest liczbą false positives.liczba fałszywych negatywów., Indeks F M {\displaystyle FM} jest średnią geometryczną precyzji i przypomnienia P {\displaystyle P} i R {\displaystyle R} i dlatego jest również znany jako miara G, podczas gdy F-miara jest ich średnią harmoniczną. Ponadto, precyzja i przypomnienie są również znane jako wskaźniki Wallace ' a B I {\displaystyle B^{I}} i B I i {\displaystyle B^{II}}. Przypadkowe znormalizowane wersje pamięci, precyzji i miary G odpowiadają informatyzacji, Znamionowości i korelacji Matthewsa i silnie odnoszą się do Kappa.,

• wzajemna informacja to teoretyczna miara informacji określająca, ile informacji jest dzielonych między klastrem a klasyfikacją prawdy gruntowej, która może wykryć nieliniowe podobieństwo między dwoma klastrami. Znormalizowana informacja wzajemna to rodzina skorygowanych dla przypadku wariantów tego, które mają zmniejszone odchylenie dla różnych liczb klastrów.
• macierz zamieszania

macierz zamieszania może być używana do szybkiej wizualizacji wyników algorytmu klasyfikacji (lub grupowania). Pokazuje, jak różni się klaster od klastra gold standard.,

tendencjaedytuj

aby zmierzyć tendencję klastra, należy zmierzyć, w jakim stopniu klastry istnieją w danych, które mają być klastrowane. Jednym ze sposobów na to jest porównanie danych z przypadkowymi danymi. Przeciętnie losowe DANE nie powinny mieć klastrów.

• Statystyka Hopkinsa

istnieje wiele sformułowań statystyki Hopkinsa. Typowy jest następujący. Niech X {\displaystyle X} będzie zbiorem n {\displaystyle n} punktów danych w d {\displaystyle d} przestrzeni wymiarowej., Rozważmy próbę losową (bez zastępowania) punktów danych m ≪ n {\displaystyle m\ll N} z członami X i {\displaystyle x_{i}}. Również wygenerować zbiór Y {\displaystyle Y} M {\displaystyle m} równomiernie rozmieszczonych punktów danych. Teraz zdefiniuj dwie miary odległości, u i {\displaystyle u_ {i}} być odległością y i ∈ y {\displaystyle y_{i} \ in y} od najbliższego sąsiada w X i w I {\displaystyle w_{i}} być odległością x i ∈ x {\displaystyle x_{i}\in X} od najbliższego sąsiada w X., Następnie definiujemy statystykę Hopkinsa 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 _{u_{i}^{d}}+\sum _{i=1}^{m} {w_{i}^{D}}}}}\,,} z tą definicją, jednolite dane losowe powinny mieć wartości zbliżone do 0,5, a dane klastrowe powinny mieć wartości zbliżone do 1., Jednak dane zawierające tylko jeden Gaussian będzie również wynik blisko 1, Jak ta statystyka mierzy odchylenie od równomiernego rozkładu, a nie multimodalności, dzięki czemu ta statystyka w dużej mierze bezużyteczne w aplikacji (jak rzeczywiste dane nigdy nie jest zdalnie jednolite).