Identyfikowanie nieznanego za pomocą metryk klastrowania

Klastrowanie to nienadzorowana metoda uczenia maszynowego, która dzieli dane na grupy wyłącznie na podstawie cech każdej próbki. Sortowanie danych w klastry może pomóc zidentyfikować nieznane podobieństwa między próbkami lub ujawnić wartości odstające w zestawie danych. W rzeczywistym świecie tworzenie klastrów ma znaczenie w różnych dziedzinach, od marketingu po biologię: aplikacje klastrowe obejmują segmentację rynku, analizę sieci społecznościowych i diagnostyczne obrazowanie medyczne.

Ponieważ proces ten nie jest nadzorowany, wokół różnych funkcji może powstać wiele wyników grupowania. Na przykład wyobraź sobie, że masz zestaw danych składający się z różnych obrazów czerwonych spodni, czarnych spodni, czerwonych koszul i czarnych koszul. Jeden algorytm może znaleźć klastry na podstawie kształtu odzieży, podczas gdy inny może tworzyć grupy na podstawie koloru.

Analizując zbiór danych, potrzebujemy sposobu na dokładny pomiar wydajności różnych algorytmów klastrowania; możemy chcieć skontrastować rozwiązania dwóch algorytmów lub zobaczyć, jak blisko wyniku klastrowania jest oczekiwane rozwiązanie. W tym artykule przyjrzymy się niektórym metrykom, które można wykorzystać do porównywania różnych wyników klastrowania uzyskanych z tych samych danych.

Zrozumienie klastrowania: krótki przykład

Zdefiniujmy przykładowy zestaw danych, którego użyjemy do wyjaśnienia różnych koncepcji metryk klastrowania i zbadania, jakie rodzaje klastrów mogą one generować.

Najpierw kilka popularnych notacji i terminów:

• $D$: zbiór danych
• $A$, $B$: dwa klastry będące podzbiorami naszego zbioru danych
• $C$: grupowanie wartości podstawowej $D$, z którym będziemy porównywać inny klaster
  • Klastrowanie $C$ ma klastry $K$, $C = {C_1, …, C_k}$
• $C'$: drugie grupowanie $D$
  • Klastrowanie $C'$ ma klastry $K'$, $C' = {C^\prime_1, …, C^\prime_{k^\prime}}$

Wyniki grupowania mogą się różnić w zależności nie tylko od cech sortowania, ale także od całkowitej liczby klastrów. Wynik zależy od algorytmu, jego wrażliwości na małe perturbacje, parametrów modelu oraz cech danych. Korzystając z naszego wcześniej wspomnianego zestawu danych dotyczących czarnych i czerwonych spodni i koszul, istnieje wiele różnych wyników grupowania, które mogą być uzyskane z różnych algorytmów.

Aby odróżnić ogólne grupowanie $C$ od naszych przykładowych grupowań, użyjemy małej litery $c$ do opisania naszych przykładowych grupowań:

• $c$, z klastrami opartymi na kształcie: $c = {c_1, c_2}$, gdzie $c_1$ reprezentuje spodnie, a $c_2$ reprezentuje koszule
• $c'$, z klastrami opartymi na kolorze: $c' = {c'_1, c'_2}$, gdzie $c'_1$ reprezentuje czerwone ubrania, a $c'_2$ reprezentuje czarne ubrania
• $c''$, z klastrami opartymi na kształcie i kolorze: $c'' = {{c^{\prime \prime}}_1, {c^{\prime \prime}}_2, {c^{\prime \prime}}_3, {c^{\prime \prime}}_4}$, gdzie ${c^{\prime \prime}}_1$ oznacza czerwone spodnie, ${c^{\prime \prime}}_2 $ reprezentuje czarne spodnie, ${c^{\prime \prime}}_3$ reprezentuje czerwone koszule, a ${c^{\prime \prime}}_4$ reprezentuje czarne koszule

Dodatkowe skupienia mogą obejmować więcej niż cztery skupienia w oparciu o różne cechy, takie jak to, czy koszula jest bez rękawów czy z rękawami.

Jak widać w naszym przykładzie, metoda grupowania dzieli wszystkie próbki w zbiorze danych na niepuste rozłączne podzbiory. W klastrze $c$ nie ma obrazu, który należy zarówno do podzbioru spodni, jak i podzbioru koszul: $c_1 \cap c_2 = \emptyset$. Ta koncepcja może zostać rozszerzona; żadne dwa podzbiory klastra nie mają tej samej próbki.

Przegląd wskaźników porównania klastrów

Większość kryteriów porównywania skupień można opisać za pomocą macierzy pomyłek pary $C, C'$. Macierz pomyłek byłaby macierzą $K \times K'$, której $kk'$ty element (element w $k$-tym wierszu i $k'$-tej kolumnie) jest liczbą próbek w przecięciu skupień $ C_k$ z $C$ i $C'_{k'}$ z $C'$:

\[n_{kk'} = |C_k \cap C'_{k'}|\]

Przeanalizujemy to za pomocą naszego uproszczonego przykładu czarno-czerwonych spodni i koszul, zakładając, że zbiór danych $D$ zawiera 100 czerwonych spodni, 200 czarnych spodni, 200 czerwonych koszul i 300 czarnych koszul. Zbadajmy macierz pomyłek $c$ i $c''$:

Ponieważ $K = 2$ i $K'' = 4$, jest to macierz $2 \times 4$. Wybierzmy $k = 2$ i $k'' = 3$. Widzimy, że element $n_{kk'} = n_{23} = 200$. Oznacza to, że przecięcie $c_2$ (koszule) i ${c^{\prime\prime}}_3$ (czerwone koszule) wynosi 200, co jest poprawne, ponieważ $c_2 \cap {c^{\prime\prime} }_3$ to po prostu zestaw czerwonych koszulek.

Metryki klastrowania można ogólnie podzielić na trzy grupy w oparciu o podstawową metodę porównywania klastrów:

W tym artykule dotykamy tylko kilku z wielu dostępnych metryk, ale nasze przykłady pomogą zdefiniować trzy grupy metryk klastrowania.

Liczenie par

Liczenie par wymaga zbadania wszystkich par próbek, a następnie zliczenia par, w których skupienia zgadzają się i nie zgadzają. Każda para próbek może należeć do jednego z czterech zbiorów, gdzie zliczeń elementów zbioru ($N_{ij}$) otrzymuje się z macierzy pomyłek:

• $S_{11}$, z elementami $N_{11}$: elementy pary znajdują się w tym samym klastrze zarówno w $C$, jak i $C'$
  • Para dwóch czerwonych koszul spadłaby poniżej $S_{11}$ przy porównywaniu $c$ i $c''$
• $S_{00}$, z elementami $N_{00}$: elementy pary znajdują się w różnych klastrach zarówno w $C$, jak i $C'$
  • Para czerwonej koszuli i czarnych spodni spadłaby poniżej $S_{00}$ przy porównywaniu $c$ i $c''$
• $S_{10}$, z elementami $N_{10}$: elementy pary znajdują się w tym samym klastrze w $C$ i różnych klastrach w $C'$
  • Para czerwonej i czarnej koszuli spadłaby poniżej $S_{10}$ przy porównywaniu $c$ i $c''$
• $S_{01}$, z elementami $N_{01}$: elementy pary znajdują się w różnych klastrach w $C$ i tym samym klastrze w $C'$
  • $S_{01}$ nie zawiera elementów ($N_{01} = 0$) przy porównywaniu $c$ i $c''$

Indeks Rand jest zdefiniowany jako $(N_{00} + N_{11})/(n(n-1)/2)$, gdzie $n$ reprezentuje liczbę próbek; można go również odczytać jako (liczba podobnie potraktowanych par)/(całkowita liczba par). Chociaż teoretycznie jego wartość zawiera się w przedziale od 0 do 1, w praktyce często jest to zakres znacznie węższy. Wyższa wartość oznacza większe podobieństwo między skupieniami. (Wskaźnik Rand równy 1 reprezentuje idealne dopasowanie, gdy dwa skupienia mają identyczne skupienia).

Jednym z ograniczeń wskaźnika Rand jest jego zachowanie, gdy liczba klastrów wzrasta, aby zbliżyć się do liczby elementów; w tym przypadku zbliża się do 1, stwarzając wyzwania w dokładnym pomiarze podobieństwa klastrów. W celu rozwiązania tego problemu wprowadzono kilka ulepszonych lub zmodyfikowanych wersji indeksu Rand. Jedną z odmian jest skorygowany indeks Rand ; zakłada jednak, że dwa skupienia są losowane ze stałą liczbą skupień i elementów skupień.

Teoria informacji

Te metryki są oparte na ogólnych pojęciach teorii informacji. Omówimy dwa z nich: entropię i informację wzajemną (MI).

Entropia opisuje, ile informacji znajduje się w grupowaniu. Jeśli entropia związana z grupowaniem wynosi 0, nie ma niepewności co do skupienia losowo wybranej próbki, co jest prawdą, gdy istnieje tylko jedno skupienie.

MI opisuje, ile informacji daje jedno skupienie o drugim. MI może wskazać, jak bardzo znajomość skupienia próbki w $C$ zmniejsza niepewność dotyczącą skupienia próbki w $C'$.

Znormalizowana wzajemna informacja to MI, która jest znormalizowana przez średnią geometryczną lub arytmetyczną entropii skupień. Standardowy MI nie jest związany stałą wartością, więc znormalizowane wzajemne informacje zapewniają bardziej zrozumiałą metrykę grupowania.

Inną popularną metryką w tej kategorii jest zmienność informacji (VI), która zależy zarówno od entropii, jak i MI skupień. Niech $H(C)$ będzie entropią grupowania, a $I(C, C')$ będzie MI pomiędzy dwoma grupowaniami. VI pomiędzy dwoma skupieniami można zdefiniować jako $VI(C,C') = H(C)+H(C')-2I(C,C')$. VI równe 0 reprezentuje idealne dopasowanie między dwoma grupowaniami.

Ustaw nakładanie

Ustaw metryki nakładania się obejmują określenie najlepszego dopasowania dla klastrów w $C$ z klastrami w $C'$ na podstawie maksymalnego nakładania się klastrów. Dla wszystkich metryk w tej kategorii 1 oznacza, że ​​klastry są identyczne.

Miara maksymalnego dopasowania skanuje macierz pomyłek w kolejności malejącej i najpierw dopasowuje największy wpis w macierzy pomyłek. Następnie usuwa dopasowane klastry i powtarza proces sekwencyjnie, aż klastry zostaną wyczerpane.

Miara F to kolejny zestaw miar nakładania się. W przeciwieństwie do miary maksymalnego dopasowania, miara F jest często używana do porównywania grupowania z optymalnym rozwiązaniem, zamiast porównywania dwóch grupowań.

Stosowanie metryk klastrowania z miarą F

Ze względu na powszechne zastosowanie miary F w modelach uczenia maszynowego i ważnych aplikacjach, takich jak wyszukiwarki, omówimy ją bardziej szczegółowo na przykładzie.

Definicja środka F

Załóżmy, że $C$ jest naszą podstawową prawdą, czyli rozwiązaniem optymalnym. Dla dowolnego $k$tego klastra w $C$, gdzie $k \in [1, K]$, obliczymy indywidualną miarę F dla każdego klastra w wyniku grupowania $C'$. Ta indywidualna miara F wskazuje, jak dobrze klaster $C^\prime_{k'}$ opisuje klaster $C_k$ i może być określona przez precyzję i przypomnienie (dwie metryki oceny modelu) dla tych klastrów. Zdefiniujmy $I_{kk'}$ jako przecięcie elementów w $k$-tym klastrze $C$ i $C'$ w $k'$-tym klastrze, a $\lvert C_k \rvert$ jako liczbę elementów w klastrze $k$th.

• Dokładność $p = \frac{I_{kk'}}{\lvert C'_{k'} \rvert}$

• Przypomnijmy $r = \frac{I_{kk'}}{\lvert C_{k} \rvert}$

Następnie indywidualna miara F skupienia $k$-tego i $k'$-tego może zostać obliczona jako średnia harmoniczna precyzji i przywołania dla tych skupień:

\[F_{kk'} = \frac{2rp}{r+p} = \frac{2I_{kk'}}{|C_k|+|C'_{k'}|}\]

Teraz, aby porównać $C$ i $C'$, spójrzmy na ogólną miarę F. Najpierw stworzymy macierz podobną do tabeli kontyngencji, której wartości są poszczególnymi miarami F skupień. Załóżmy, że zmapowaliśmy skupienia $C$ jako wiersze tabeli, a skupienia $C'$ jako kolumny, z wartościami tabeli odpowiadającymi poszczególnym miarom F. Zidentyfikuj parę skupień z maksymalną indywidualną miarą F i usuń wiersz i kolumnę odpowiadające tym skupieniom. Powtarzaj to, aż klastry się wyczerpią. Na koniec możemy zdefiniować ogólną miarę F:

\[F(C, C') = \frac{1}{n} \sum_{i=1}^K n_imax(F(C_i, C'_j)) \forall j \in {1, K'}\ ]

Jak widać, ogólna miara F jest sumą ważoną naszych maksymalnych indywidualnych miar F dla klastrów.

Konfiguracja danych i oczekiwane wyniki

Każdy notatnik Pythona odpowiedni do uczenia maszynowego, taki jak notatnik Jupyter, będzie działał jako nasze środowisko. Zanim zaczniemy, możesz sprawdzić README mojego repozytorium GitHub, rozszerzony przykładowy plik readme_help_example.ipynb oraz plik Requirements.txt ( requirements.txt biblioteki).

Użyjemy przykładowych danych z repozytorium GitHub, które składa się z artykułów z wiadomościami. Dane są uporządkowane według informacji obejmujących category , headline , date i short_description :

Możemy używać pand do odczytywania, analizowania i manipulowania danymi. Posortujemy dane według daty i wybierzemy małą próbkę (10 000 nagłówków wiadomości) do naszego demo, ponieważ pełny zestaw danych jest duży:

 import pandas as pd df = pd.read_json("./sample_data/example_news_data.json", lines=True) df.sort_values(by='date', inplace=True) df = df[:10000] len(df['category'].unique())

Po uruchomieniu powinieneś zobaczyć, jak notebook wyświetla wynik 30, ponieważ w tej próbce danych jest 30 kategorii. Możesz także uruchomić df.head(4) , aby zobaczyć, jak przechowywane są dane. (Powinna być zgodna z tabelą wyświetlaną w tej sekcji.)

Optymalizacja funkcji klastrowania

Przed zastosowaniem klastrowania powinniśmy najpierw wstępnie przetworzyć tekst, aby zredukować nadmiarowe funkcje naszego modelu, w tym:

• Aktualizacja tekstu w celu ujednolicenia przypadku.
• Usuwanie znaków numerycznych lub specjalnych.
• Wykonywanie lematyzacji.
• Usuwanie słów stop.

 import re import nltk from nltk.corpus import stopwords from nltk.stem import WordNetLemmatizer wordnet_lemmatizer = WordNetLemmatizer() nltk.download('stopwords') stop_words = stopwords.words('english') nltk.download('wordnet') nltk.download('omw-1.4') def preprocess(text: str) -> str: text = text.lower() text = re.sub('[^az]',' ',text) text = re.sub('\s+', ' ', text) text = text.split(" ") words = [wordnet_lemmatizer.lemmatize(word, 'v') for word in text if word not in stop_words] return " ".join(words) df['processed_input'] = df['headline'].apply(preprocess)

Wynikowe wstępnie przetworzone nagłówki są wyświetlane jako processed_input , które można zaobserwować ponownie uruchamiając df.head(4) :

Teraz musimy przedstawić każdy nagłówek jako wektor liczbowy, aby móc zastosować do niego dowolny model uczenia maszynowego. Aby to osiągnąć, istnieją różne techniki ekstrakcji cech; będziemy używać TF-IDF (termin częstotliwości dokumentu odwrotnej częstotliwości). Ta technika zmniejsza wpływ słów pojawiających się z dużą częstotliwością w dokumentach (w naszym przykładzie nagłówki wiadomości), ponieważ wyraźnie nie powinny one decydować o ich grupowaniu lub klasyfikowaniu.

 from sklearn.cluster import AgglomerativeClustering, KMeans from sklearn.feature_extraction.text import TfidfVectorizer vectorizer = TfidfVectorizer(max_features=300, tokenizer=lambda x: x.split(' ')) tfidf_mat = vectorizer.fit_transform(df['processed_input']) X = tfidf_mat.todense() X[X==0]=0.00001

Następnie wypróbujemy naszą pierwszą metodę grupowania, grupowanie aglomeracyjne, na tych wektorach cech.

Metoda grupowania 1: Grupowanie aglomeracyjne

Biorąc pod uwagę podane kategorie wiadomości jako optymalne rozwiązanie, porównajmy te wyniki z wynikami klastrowania aglomeracyjnego (przy pożądanej liczbie klastrów jako 30, ponieważ w zbiorze danych jest 30 kategorii):

 clusters_agg = AgglomerativeClustering(n_clusters=30).fit_predict(X) df['class_prd'] = clusters_agg.astype(int)

Zidentyfikujemy powstałe klastry za pomocą etykiet liczb całkowitych; nagłówki należące do tego samego klastra mają przypisaną tę samą etykietę liczby całkowitej. Funkcja cluster_measure z modułu compare_clusters naszego repozytorium GitHub zwraca zagregowaną miarę F i liczbę idealnie dopasowanych klastrów, dzięki czemu możemy zobaczyć, jak dokładny był nasz wynik klastrowania:

 from clustering.compare_clusters import cluster_measure # 'cluster_measure` requires given text categories to be in the column 'text_category` df['text_category'] = df['category'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.19858339749319176, 0)

Porównując te wyniki skupień z optymalnym rozwiązaniem, otrzymujemy niski wskaźnik F wynoszący 0,198 i 0 skupień odpowiadających rzeczywistym grupom klasowym, co oznacza, że ​​skupienia aglomeracyjne nie pokrywają się z wybranymi przez nas głównymi kategoriami. Sprawdźmy klaster w wyniku, aby zobaczyć, jak wygląda.

 df[df['class_prd'] == 0]['category'].value_counts()

Po przeanalizowaniu wyników widzimy, że klaster ten zawiera nagłówki ze wszystkich kategorii:

 POLITICS 1268 ENTERTAINMENT 712 THE WORLDPOST 373 HEALTHY LIVING 272 QUEER VOICES 251 PARENTS 212 BLACK VOICES 211 ... FIFTY 24 EDUCATION 23 COLLEGE 14 ARTS 13

Tak więc nasza niska miara F ma sens, biorąc pod uwagę, że klastry naszych wyników nie pokrywają się z optymalnym rozwiązaniem. Należy jednak pamiętać, że wybrana przez nas klasyfikacja kategorii odzwierciedla tylko jeden możliwy podział zbioru danych. Niska miara F w tym przypadku nie oznacza, że ​​wynik grupowania jest błędny, ale że wynik grupowania nie pasuje do naszej pożądanej metody partycjonowania danych.

Metoda grupowania 2: K-średnie

Wypróbujmy inny popularny algorytm grupowania na tym samym zbiorze danych: grupowanie k-średnich. Stworzymy nową ramkę danych i ponownie użyjemy funkcji cluster_measure :

 kmeans = KMeans(n_clusters=30, random_state=0).fit(X) df2 = df.copy() df2['class_prd'] = kmeans.predict(X).astype(int) res_df, fmeasure_aggregate, true_matches = cluster_measure(df2) fmeasure_aggregate, len(true_matches) # Outputs: (0.18332960871141976, 0)

Podobnie jak wynik grupowania aglomeracyjnego, nasz wynik grupowania k-średnich utworzył klastry, które są niepodobne do naszych danych kategorii: ma miary F równe 0,18 w porównaniu z rozwiązaniem optymalnym. Ponieważ oba wyniki grupowania mają podobne miary F, byłoby interesujące porównać je ze sobą. Mamy już skupienia, więc wystarczy obliczyć miarę F. Najpierw sprowadzimy oba wyniki do jednej kolumny, przy czym class_gt ma wynik grupowania aglomeracyjnego, a class_prd ma wynik grupowania k-średnich:

 df1 = df2.copy() df1['class_gt'] = df['class_prd'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df1, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.4030316435020922, 0)

Przy wyższej wartości F wynoszącej 0,4 możemy zaobserwować, że klastrowania dwóch algorytmów są bardziej podobne do siebie niż do rozwiązania optymalnego.

Dowiedz się więcej o ulepszonych wynikach klastrowania

Zrozumienie dostępnych metryk porównywania klastrów rozszerzy analizę modelu uczenia maszynowego. Widzieliśmy w działaniu miernik grupowania z miarą F i przedstawiliśmy podstawy potrzebne do zastosowania tych wniosków do następnego wyniku grupowania. Aby dowiedzieć się jeszcze więcej, oto moje najlepsze propozycje do dalszej lektury:

• Porównanie klastrów — przegląd autorstwa Dorothei Wagner i Silke Wagner
• Porównanie klastrów — odległość oparta na informacjach autorstwa Mariny Meila
• Teoretyczne miary informacji do porównywania skupień: warianty, właściwości, normalizacja i poprawka na przypadek autorstwa Nguyena Xuana Vinha, Juliena Eppsa i Jamesa Baileya

---

Dalsza lektura na blogu Toptal Engineering:

• Wykresy analizy danych za pomocą Python/NetworkX
• Częściowo nadzorowana klasyfikacja obrazów z danymi nieoznakowanymi
• Osadzania w uczeniu maszynowym: uproszczenie złożonych danych

Blog Toptal Engineering wyraża wdzięczność Luisowi Bronchalowi za przejrzenie próbek kodu przedstawionych w tym artykule.