Identificarea necunoscutului cu valorile de grupare

Clustering este o metodă de învățare automată nesupravegheată pentru a împărți datele date în grupuri, bazate exclusiv pe caracteristicile fiecărui eșantion. Sortarea datelor în grupuri poate ajuta la identificarea asemănărilor necunoscute între eșantioane sau la dezvăluirea valorii aberante din setul de date. În lumea reală, gruparea are importanță în diverse domenii, de la marketing la biologie: aplicațiile de clusterizare includ segmentarea pieței, analiza rețelelor sociale și imagistica medicală de diagnosticare.

Deoarece acest proces este nesupravegheat, se pot forma mai multe rezultate de grupare în jurul diferitelor caracteristici. De exemplu, imaginați-vă că aveți un set de date compus din diferite imagini cu pantaloni roșii, pantaloni negri, cămăși roșii și cămăși negre. Un algoritm ar putea găsi grupuri bazate pe forma îmbrăcămintei, în timp ce altul ar putea crea grupuri bazate pe culoare.

Când analizăm un set de date, avem nevoie de o modalitate de a măsura cu precizie performanța diferiților algoritmi de grupare; putem dori să contrastăm soluțiile a doi algoritmi sau să vedem cât de aproape este un rezultat de grupare de o soluție așteptată. În acest articol, vom explora unele dintre valorile care pot fi utilizate pentru a compara diferite rezultate de grupare obținute din aceleași date.

Înțelegerea grupării: un scurt exemplu

Să definim un exemplu de set de date pe care îl vom folosi pentru a explica diferitele concepte de metrică de clustering și pentru a examina ce tipuri de clustere ar putea produce.

În primul rând, câteva notații și termeni obișnuiți:

• $D$: setul de date
• $A$, $B$: două clustere care sunt subseturi ale setului nostru de date
• $C$: gruparea de adevăr de bază a $D$ cu care vom compara un alt cluster
  • Clustering $C$ are $K$ clustere, $C = {C_1, …, C_k}$
• $C'$: o a doua grupare de $D$
  • Clustering $C'$ are $K'$ clustere, $C' = {C^\prime_1, …, C^\prime_{k^\prime}}$

Rezultatele grupării pot varia în funcție nu numai de caracteristicile de sortare, ci și de numărul total de clustere. Rezultatul depinde de algoritm, de sensibilitatea acestuia la mici perturbații, de parametrii modelului și de caracteristicile datelor. Folosind setul de date menționat anterior de pantaloni și cămăși negre și roșii, există o varietate de rezultate de grupare care ar putea fi produse din diferiți algoritmi.

Pentru a distinge între clusteringul general $C$ și exemplele noastre de clustering, vom folosi $c$ minuscule pentru a descrie exemplele noastre de clustering:

• $c$, cu grupuri bazate pe formă: $c = {c_1, c_2}$, unde $c_1$ reprezintă pantaloni și $c_2$ reprezintă cămăși
• $c'$, cu grupuri bazate pe culoare: $c' = {c'_1, c'_2}$, unde $c'_1$ reprezintă haine roșii și $c'_2$ reprezintă haine negre
• $c''$, cu clustere bazate pe formă și culoare: $c'' = {{c^{\prime \prime}}_1, {c^{\prime \prime}}_2, {c^{\prime \prime}}_3, {c^{\prime \prime}}_4}$, unde ${c^{\prime \prime}}_1$ reprezintă pantaloni roșii, ${c^{\prime \prime}}_2 $ reprezintă pantaloni negri, ${c^{\prime \prime}}_3$ reprezintă cămăși roșii și ${c^{\prime \prime}}_4$ reprezintă cămăși negre

Grupări suplimentare pot include mai mult de patru grupuri bazate pe caracteristici diferite, cum ar fi dacă o cămașă este fără mâneci sau cu mâneci.

După cum se vede în exemplul nostru, o metodă de grupare împarte toate eșantioanele dintr-un set de date în subseturi disjunse nevide. În cluster $c$, nu există nicio imagine care să aparțină atât subsetului de pantaloni, cât și subsetului de cămăși: $c_1 \cap c_2 = \emptyset$. Acest concept poate fi extins; nu există două subseturi ale niciunui cluster să aibă același eșantion.

O privire de ansamblu asupra valorilor de comparare a grupării

Majoritatea criteriilor de comparare a grupărilor pot fi descrise folosind matricea de confuzie a perechii $C, C'$. Matricea de confuzie ar fi o matrice $K \times K'$ al cărei $kk'$-lea element (elementul din $k$-lea rând și $k'$-a coloană) este numărul de mostre din intersecția clusterelor $ C_k$ din $C$ și $C'_{k'}$ din $C'$:

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

Vom descompune acest lucru folosind exemplul nostru simplificat de pantaloni și cămăși negre și roșii, presupunând că setul de date $D$ are 100 de pantaloni roșii, 200 de pantaloni negri, 200 de cămăși roșii și 300 de cămăși negre. Să examinăm matricea de confuzie a lui $c$ și $c''$:

Deoarece $K = 2$ și $K'' = 4$, aceasta este o matrice $2 \times 4$. Să alegem $k = 2$ și $k'' = 3$. Vedem acel element $n_{kk'} = n_{23} = 200$. Aceasta înseamnă că intersecția dintre $c_2$ (cămăși) și ${c^{\prime\prime}}_3$ (cămăși roșii) este 200, ceea ce este corect deoarece $c_2 \cap {c^{\prime\prime} }_3$ ar fi pur și simplu setul de cămăși roșii.

Valorile de grupare pot fi clasificate pe scară largă în trei grupuri, pe baza metodei de comparare a grupurilor de bază:

În acest articol, atingem doar câteva dintre multele valori disponibile, dar exemplele noastre vor ajuta la definirea celor trei grupuri de valori de grupare.

Numărarea perechilor

Numărarea perechilor necesită examinarea tuturor perechilor de eșantioane, apoi numărarea perechilor în care grupările sunt de acord și în dezacord. Fiecare pereche de eșantioane poate aparține unuia dintre cele patru seturi, unde numărul elementelor set ($N_{ij}$) este obținut din matricea de confuzie:

• $S_{11}$, cu elemente $N_{11}$: elementele perechii sunt în același grup atât sub $C$ cât și sub $C'$
  • O pereche de două cămăși roșii ar scădea sub $S_{11}$ când se compară $c$ și $c''$
• $S_{00}$, cu elemente $N_{00}$: elementele perechii sunt în grupuri diferite atât sub $C$ cât și sub $C'$
  • O pereche de cămașă roșie și pantaloni negri ar scădea sub $S_{00}$ când se compară $c$ și $c''$
• $S_{10}$, cu elemente $N_{10}$: elementele perechii sunt în același cluster în $C$ și grupuri diferite în $C'$
  • O pereche de cămașă roșie și o cămașă neagră ar scădea sub $S_{10}$ când se compară $c$ și $c''$
• $S_{01}$, cu elemente $N_{01}$: elementele perechii sunt în grupuri diferite în $C$ și același grup în $C'$
  • $S_{01}$ nu are elemente ($N_{01} = 0$) când se compară $c$ și $c''$

Indicele Rand este definit ca $(N_{00} + N_{11})/(n(n-1)/2)$, unde $n$ reprezintă numărul de mostre; poate fi citit și ca (număr de perechi tratate în mod similar)/(număr total de perechi). Deși teoretic valoarea sa variază între 0 și 1, intervalul său este adesea mult mai restrâns în practică. O valoare mai mare înseamnă mai multă similitudine între grupări. (Un indice Rand de 1 ar reprezenta o potrivire perfectă în cazul în care două grupări au grupuri identice.)

O limitare a indicelui Rand este comportamentul său atunci când numărul de clustere crește pentru a se apropia de numărul de elemente; în acest caz, converge către 1, creând provocări în măsurarea precisă a similarității grupării. Au fost introduse mai multe versiuni îmbunătățite sau modificate ale indexului Rand pentru a rezolva această problemă. O variație este indicele Rand ajustat ; totuși, se presupune că două grupări sunt desenate aleatoriu cu un număr fix de clustere și elemente de cluster.

Teoria informației

Aceste metrici se bazează pe noțiuni generice de teoria informației. Vom discuta două dintre ele: entropia și informația reciprocă (MI).

Entropia descrie cât de multă informație există într-o grupare. Dacă entropia asociată cu o grupare este 0, atunci nu există nicio incertitudine cu privire la clusterul unui eșantion ales aleatoriu, ceea ce este adevărat atunci când există un singur cluster.

MI descrie cât de multe informații oferă o grupare despre cealaltă. MI poate indica cât de mult cunoașterea clusterului unui eșantion în $C$ reduce incertitudinea cu privire la clusterul eșantionului în $C'$.

Informația reciprocă normalizată este MI care este normalizată prin media geometrică sau aritmetică a entropiilor grupărilor. MI standard nu este legat de o valoare constantă, astfel încât informațiile reciproce normalizate oferă o metrică de grupare mai interpretabilă.

O altă măsură populară din această categorie este variația informațiilor (VI) care depinde atât de entropia, cât și de MI a grupărilor. Fie $H(C)$ entropia unei grupări și $I(C, C')$ fie MI dintre două grupări. VI între două grupări poate fi definit ca $VI(C,C') = H(C)+H(C')-2I(C,C')$. Un VI de 0 reprezintă o potrivire perfectă între două grupări.

Setați suprapunerea

Setarea valorilor de suprapunere implică determinarea celei mai bune potriviri pentru clustere în $C$ cu clustere în $C'$ pe baza suprapunerii maxime dintre clustere. Pentru toate valorile din această categorie, un 1 înseamnă că grupările sunt identice.

Măsura de potrivire maximă scanează matricea de confuzie în ordine descrescătoare și se potrivește mai întâi cu cea mai mare intrare a matricei de confuzie. Apoi elimină clusterele potrivite și repetă procesul secvenţial până când clusterele sunt epuizate.

Măsura F este o altă metrică de suprapunere setată. Spre deosebire de măsura de potrivire maximă, măsura F este frecvent utilizată pentru a compara o grupare cu o soluție optimă, în loc de a compara două grupări.

Aplicarea valorilor de grupare cu măsură F

Datorită utilizării obișnuite a măsurătorii F în modelele de învățare automată și în aplicații importante, cum ar fi motoarele de căutare, vom explora măsura F mai detaliat cu un exemplu.

Măsura F Definiție

Să presupunem că $C$ este adevărul nostru de bază, sau soluția optimă. Pentru orice $k$-lea cluster din $C$, unde $k \in [1, K]$, vom calcula o măsură F individuală cu fiecare cluster din rezultatul grupării $C'$. Această măsură F individuală indică cât de bine clusterul $C^\prime_{k'}$ descrie clusterul $C_k$ și poate fi determinată prin precizie și rechemare (două metrici de evaluare a modelului) pentru aceste clustere. Să definim $I_{kk'}$ ca intersecția elementelor din $k$-lea cluster al lui $C$ și $C'$-al-lea cluster și $\lvert C_k \rvert$ ca număr de elemente din $k$-lea cluster.

• Precizie $p = \frac{I_{kk'}}{\lvert C'_{k'} \rvert}$

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

  

Apoi, măsura F individuală a $k$-lea și $k'$-lea cluster poate fi calculată ca medie armonică a preciziei și a reamintirii pentru aceste clustere:

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

Acum, pentru a compara $C$ și $C'$, să ne uităm la măsura F generală. În primul rând, vom crea o matrice similară unui tabel de contingență ale cărui valori sunt măsurile F individuale ale clusterelor. Să presupunem că am mapat clusterele lui $C$ ca rânduri ale unui tabel și clusterele lui $C'$ ca coloane, cu valorile tabelului corespunzătoare măsurilor F individuale. Identificați perechea de cluster cu măsura F individuală maximă și eliminați rândul și coloana corespunzătoare acestor clustere. Repetați acest lucru până când clusterele sunt epuizate. În cele din urmă, putem defini măsura F generală:

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

După cum puteți vedea, măsura F generală este suma ponderată a măsurilor F individuale maxime pentru clustere.

Configurarea datelor și rezultatele așteptate

Orice notebook Python potrivit pentru învățarea automată, cum ar fi un notebook Jupyter, va funcționa ca mediul nostru. Înainte de a începe, poate doriți să examinați fișierul README al depozitului meu GitHub, fișierul exemplu readme_help_example.ipynb extins și fișierul requirements.txt (bibliotecile necesare).

Vom folosi eșantionul de date din depozitul GitHub, care este format din articole de știri. Datele sunt aranjate cu informații, inclusiv category , headline , date și short_description :

Putem folosi panda pentru a citi, analiza și manipula datele. Vom sorta datele după dată și vom selecta un eșantion mic (10.000 de titluri de știri) pentru demonstrația noastră, deoarece setul complet de date este mare:

 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())

La rulare, ar trebui să vedeți ca notebook-ul scoate rezultatul 30, deoarece există 30 de categorii în acest eșantion de date. De asemenea, puteți rula df.head(4) pentru a vedea cum sunt stocate datele. (Ar trebui să se potrivească cu tabelul afișat în această secțiune.)

Optimizarea caracteristicilor de clusterizare

Înainte de a aplica gruparea, ar trebui mai întâi să preprocesăm textul pentru a reduce caracteristicile redundante ale modelului nostru, inclusiv:

• Actualizarea textului pentru a avea un caz uniform.
• Eliminarea caracterelor numerice sau speciale.
• Efectuarea lematizării.
• Eliminarea cuvintelor 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)

Titlurile preprocesate rezultate sunt afișate ca processed_input , pe care le puteți observa rulând din nou df.head(4) :

Acum, trebuie să reprezentăm fiecare titlu ca un vector numeric pentru a-i putea aplica orice model de învățare automată. Există diferite tehnici de extragere a caracteristicilor pentru a realiza acest lucru; vom folosi TF-IDF (termen frecvență-frecvență inversă a documentului). Această tehnică reduce efectul cuvintelor care apar cu frecvență înaltă în documente (în exemplul nostru, titlurile de știri), deoarece acestea nu ar trebui să fie caracteristicile decisive în gruparea sau clasificarea lor.

 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

În continuare, vom încerca prima noastră metodă de grupare, gruparea aglomerativă, pe acești vectori de caracteristici.

Metoda de clusterizare 1: Clustering aglomerativ

Considerând categoriile de știri date ca soluție optimă, să comparăm aceste rezultate cu cele ale grupării aglomerative (cu numărul dorit de clustere de 30, deoarece există 30 de categorii în setul de date):

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

Vom identifica clusterele rezultate prin etichete întregi; titlurilor aparținând aceluiași cluster li se atribuie aceeași etichetă întreg. Funcția cluster_measure din modulul compare_clusters al depozitului nostru GitHub returnează măsura F agregată și numărul de clustere care se potrivesc perfect, astfel încât să putem vedea cât de precis a fost rezultatul nostru de clustering:

 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)

Comparând rezultatele acestor clustere cu soluția optimă, obținem o măsură F scăzută de 0,198 și 0 clustere care se potrivesc cu grupurile de clasă reale, care arată că clusterele aglomerative nu se aliniază cu categoriile de titlu pe care le-am ales. Să verificăm un cluster din rezultat pentru a vedea cum arată.

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

La examinarea rezultatelor, vedem că acest cluster conține titluri din toate categoriile:

 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

Deci, măsura noastră F scăzută are sens, având în vedere că clusterele rezultatelor noastre nu se aliniază cu soluția optimă. Cu toate acestea, este important să ne amintim că clasificarea categoriei dată pe care am ales-o reflectă doar o posibilă diviziune a setului de date. O măsură F scăzută aici nu implică faptul că rezultatul grupării este greșit, dar că rezultatul grupării nu se potrivește cu metoda dorită de partiționare a datelor.

Metoda de grupare 2: K-medii

Să încercăm un alt algoritm popular de grupare pe același set de date: k-means clustering. Vom crea un nou cadru de date și vom folosi din nou funcția 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)

La fel ca rezultatul grupării aglomerative, rezultatul grupării k-means a format clustere care sunt diferite de categoriile noastre date: are o măsură F de 0,18 în comparație cu soluția optimă. Deoarece cele două rezultate de grupare au F-măsuri similare, ar fi interesant să le comparăm între ele. Avem deja grupările, așa că trebuie doar să calculăm măsura F. În primul rând, vom aduce ambele rezultate într-o singură coloană, class_gt având rezultatul de grupare aglomerativă și class_prd având rezultatul de grupare k-means:

 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)

Cu o măsură F mai mare de 0,4, putem observa că grupările celor doi algoritmi sunt mai asemănătoare între ele decât sunt cu soluția optimă.

Descoperiți mai multe despre rezultatele îmbunătățite de grupare

O înțelegere a valorilor de comparație de clustering disponibile va extinde analiza modelului de învățare automată. Am văzut în acțiune metrica de grupare a măsurării F și v-am oferit elementele de bază de care aveți nevoie pentru a aplica aceste învățari la următorul rezultat de grupare. Pentru a afla și mai multe, iată cele mai bune alegeri ale mele pentru lectură suplimentară:

• Comparing Clusterings - O privire de ansamblu de Dorothea Wagner și Silke Wagner
• Compararea grupărilor — o distanță bazată pe informații de Marina Meila
• Măsuri teoretice informaționale pentru compararea grupărilor: variante, proprietăți, normalizare și corecție pentru șansă de Nguyen Xuan Vinh, Julien Epps și James Bailey

---

Citiți suplimentare pe blogul Toptal Engineering:

• Graph Data Science cu Python/NetworkX
• Clasificarea imaginilor semi-supravegheate cu date neetichetate
• Încorporarea în învățarea automată: simplificarea datelor complexe

Blogul Toptal Engineering își exprimă recunoștința lui Luis Bronchal pentru revizuirea mostrelor de cod prezentate în acest articol.