Identificazione dell'ignoto con le metriche di clustering

Il clustering è un metodo di apprendimento automatico non supervisionato per dividere dati in gruppi basati esclusivamente sulle caratteristiche di ciascun campione. L'ordinamento dei dati in cluster può aiutare a identificare somiglianze sconosciute tra i campioni o rivelare valori anomali nel set di dati. Nel mondo reale, il clustering ha un significato in diversi campi, dal marketing alla biologia: le applicazioni di clustering includono la segmentazione del mercato, l'analisi dei social network e l'imaging medico diagnostico.

Poiché questo processo non è supervisionato, possono formarsi più risultati di clustering attorno a diverse funzionalità. Ad esempio, immagina di avere un set di dati composto da varie immagini di pantaloni rossi, pantaloni neri, magliette rosse e magliette nere. Un algoritmo potrebbe trovare cluster in base alla forma dell'abbigliamento, mentre un altro potrebbe creare gruppi in base al colore.

Quando si analizza un set di dati, è necessario un modo per misurare con precisione le prestazioni di diversi algoritmi di clustering; potremmo voler confrontare le soluzioni di due algoritmi o vedere quanto sia vicino un risultato di clustering a una soluzione attesa. In questo articolo esploreremo alcune delle metriche che possono essere utilizzate per confrontare diversi risultati di clustering ottenuti dagli stessi dati.

Capire il clustering: un breve esempio

Definiamo un set di dati di esempio che utilizzeremo per spiegare vari concetti di metrica di clustering ed esaminare quali tipi di cluster potrebbe produrre.

Innanzitutto, alcune notazioni e termini comuni:

• $D$: il set di dati
• $A$, $B$: due cluster che sono sottoinsiemi del nostro set di dati
• $C$: il clustering della verità fondamentale di $D$ con cui confronteremo un altro cluster
  • Il clustering $C$ ha cluster $K$, $C = {C_1, …, C_k}$
• $C'$: un secondo raggruppamento di $D$
  • Il clustering $C'$ ha cluster $K'$, $C' = {C^\prime_1, …, C^\prime_{k^\prime}}$

I risultati del clustering possono variare in base non solo alle funzionalità di ordinamento, ma anche al numero totale di cluster. Il risultato dipende dall'algoritmo, dalla sua sensibilità a piccole perturbazioni, dai parametri del modello e dalle caratteristiche dei dati. Utilizzando il nostro set di dati precedentemente menzionato di pantaloni e camicie neri e rossi, ci sono una varietà di risultati di clustering che potrebbero essere prodotti da diversi algoritmi.

Per distinguere tra il clustering generale $C$ e il nostro esempio di clustering, useremo $c$ minuscolo per descrivere il nostro esempio di clustering:

• $c$, con gruppi basati sulla forma: $c = {c_1, c_2}$, dove $c_1$ rappresenta i pantaloni e $c_2$ rappresenta le camicie
• $c'$, con gruppi basati sul colore: $c' = {c'_1, c'_2}$, dove $c'_1$ rappresenta i vestiti rossi e $c'_2$ rappresenta i vestiti neri
• $c''$, con cluster basati su forma e colore: $c'' = {{c^{\prime \prime}}_1, {c^{\prime \prime}}_2, {c^{\prime \prime}}_3, {c^{\prime \prime}}_4}$, dove ${c^{\prime \prime}}_1$ rappresenta i pantaloni rossi, ${c^{\prime \prime}}_2 $ rappresenta i pantaloni neri, ${c^{\prime \prime}}_3$ rappresenta le camicie rosse e ${c^{\prime \prime}}_4$ rappresenta le camicie nere

I raggruppamenti aggiuntivi potrebbero includere più di quattro gruppi in base a caratteristiche diverse, ad esempio se una maglietta è senza maniche o senza maniche.

Come visto nel nostro esempio, un metodo di clustering divide tutti i campioni in un set di dati in sottoinsiemi disgiunti non vuoti. Nel cluster $c$, non c'è alcuna immagine che appartenga sia al sottoinsieme dei pantaloni che al sottoinsieme delle camicie: $c_1 \cap c_2 = \emptyset$. Questo concetto può essere esteso; non esistono due sottoinsiemi di alcun cluster con lo stesso campione.

Una panoramica delle metriche di confronto del clustering

La maggior parte dei criteri per confrontare i raggruppamenti possono essere descritti utilizzando la matrice di confusione della coppia $C, C'$. La matrice di confusione sarebbe una matrice $K \times K'$ il cui $kk'$esimo elemento (l'elemento nella $k$esima riga e $k'$esima colonna) è il numero di campioni nell'intersezione dei cluster $ C_k$ di $C$ e $C'_{k'}$ di $C'$:

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

Lo analizzeremo usando il nostro esempio semplificato di pantaloni e camicie neri e rossi, supponendo che il set di dati $D$ abbia 100 pantaloni rossi, 200 pantaloni neri, 200 camicie rosse e 300 camicie nere. Esaminiamo la matrice di confusione di $c$ e $c''$:

Poiché $K = 2$ e $K'' = 4$, questa è una matrice $2 \times 4$. Scegliamo $k = 2$ e $k'' = 3$. Vediamo quell'elemento $n_{kk'} = n_{23} = 200$. Ciò significa che l'intersezione di $c_2$ (camicie) e ${c^{\prime\prime}}_3$ (camicie rosse) è 200, il che è corretto poiché $c_2 \cap {c^{\prime\prime} }_3$ sarebbe semplicemente il set di magliette rosse.

Le metriche di clustering possono essere suddivise in tre gruppi in base al metodo di confronto del cluster sottostante:

In questo articolo, tocchiamo solo alcune delle molte metriche disponibili, ma i nostri esempi serviranno a definire i tre gruppi di metriche di clustering.

Conteggio coppie

Il conteggio delle coppie richiede l'esame di tutte le coppie di campioni, quindi il conteggio delle coppie in cui i raggruppamenti sono d'accordo e in disaccordo. Ogni coppia di campioni può appartenere a uno dei quattro insiemi, dove i conteggi degli elementi dell'insieme ($N_{ij}$) sono ottenuti dalla matrice di confusione:

• $S_{11}$, con elementi $N_{11}$: gli elementi della coppia sono nello stesso cluster sia sotto $C$ che $C'$
  • Un paio di due magliette rosse rientrerebbero sotto $S_{11}$ quando si confrontano $c$ e $c''$
• $S_{00}$, con elementi $N_{00}$: gli elementi della coppia sono in cluster diversi sia sotto $C$ che $C'$
  • Un paio di camicia rossa e pantaloni neri rientrerebbero sotto $S_{00}$ se si confrontano $c$ e $c''$
• $S_{10}$, con elementi $N_{10}$: gli elementi della coppia sono nello stesso cluster in $C$ e cluster diversi in $C'$
  • Un paio di camicia rossa e camicia nera rientrerebbero sotto $S_{10}$ quando si confrontano $c$ e $c''$
• $S_{01}$, con elementi $N_{01}$: gli elementi della coppia sono in cluster diversi in $C$ e lo stesso cluster in $C'$
  • $S_{01}$ non ha elementi ($N_{01} = 0$) quando si confronta $c$ e $c''$

L' indice Rand è definito come $(N_{00} + N_{11})/(n(n-1)/2)$, dove $n$ rappresenta il numero di campioni; può anche essere letto come (numero di coppie trattate in modo simile)/(numero totale di coppie). Sebbene in teoria il suo valore sia compreso tra 0 e 1, in pratica il suo intervallo è spesso molto più ristretto. Un valore più alto significa maggiore somiglianza tra i raggruppamenti. (Un indice Rand di 1 rappresenterebbe una corrispondenza perfetta in cui due raggruppamenti hanno raggruppamenti identici.)

Una limitazione dell'indice Rand è il suo comportamento quando il numero di cluster aumenta per avvicinarsi al numero di elementi; in questo caso, converge verso 1, creando sfide nella misurazione accurata della somiglianza del clustering. Diverse versioni migliorate o modificate dell'indice Rand sono state introdotte per risolvere questo problema. Una variazione è l' indice Rand rettificato ; tuttavia, presuppone che due raggruppamenti vengano estratti casualmente con un numero fisso di cluster ed elementi del cluster.

Teoria dell'informazione

Queste metriche si basano su nozioni generiche di teoria dell'informazione. Ne discuteremo due: entropia e informazione reciproca (MI).

Entropy descrive quante informazioni ci sono in un clustering. Se l'entropia associata a un clustering è 0, non c'è incertezza sul cluster di un campione prelevato casualmente, il che è vero quando c'è un solo cluster.

MI descrive quante informazioni fornisce un raggruppamento sull'altro. MI può indicare quanto conoscere il cluster di un campione in $C$ riduce l'incertezza sul cluster del campione in $C'$.

L'informazione reciproca normalizzata è MI che è normalizzata dalla media geometrica o aritmetica delle entropie dei raggruppamenti. L'MI standard non è vincolata da un valore costante, quindi le informazioni reciproche normalizzate forniscono una metrica di clustering più interpretabile.

Un'altra metrica popolare in questa categoria è la variazione dell'informazione (VI) che dipende sia dall'entropia che dall'MI dei raggruppamenti. Sia $H(C)$ l'entropia di un raggruppamento e $I(C, C')$ sia l'MI tra due raggruppamenti. VI tra due raggruppamenti può essere definito come $VI(C,C') = H(C)+H(C')-2I(C,C')$. Un VI di 0 rappresenta una corrispondenza perfetta tra due raggruppamenti.

Imposta Sovrapposizione

Le metriche di sovrapposizione impostate implicano la determinazione della corrispondenza migliore per i cluster in $C$ con i cluster in $C'$ in base alla sovrapposizione massima tra i cluster. Per tutte le metriche in questa categoria, un 1 indica che i raggruppamenti sono identici.

La misura di corrispondenza massima esegue la scansione della matrice di confusione in ordine decrescente e corrisponde per prima alla voce più grande della matrice di confusione. Quindi rimuove i cluster corrispondenti e ripete il processo in sequenza fino all'esaurimento dei cluster.

La misura F è un'altra metrica di sovrapposizione impostata. A differenza della misura di corrispondenza massima, la misura F viene spesso utilizzata per confrontare un raggruppamento con una soluzione ottimale, invece di confrontare due raggruppamenti.

Applicazione di metriche di clustering con la misura F

A causa dell'uso comune della misura F nei modelli di apprendimento automatico e in applicazioni importanti come i motori di ricerca, esploreremo la misura F in modo più dettagliato con un esempio.

Definizione della misura F

Assumiamo che $C$ sia la nostra verità fondamentale, o soluzione ottimale. Per ogni $k$esimo cluster in $C$, dove $k \in [1, K]$, calcoleremo una singola misura F con ogni cluster nel risultato del cluster $C'$. Questa singola misura F indica quanto bene il cluster $C^\prime_{k'}$ descrive il cluster $C_k$ e può essere determinata attraverso la precisione e il richiamo (due metriche di valutazione del modello) per questi cluster. Definiamo $I_{kk'}$ come l'intersezione di elementi nel $k$esimo cluster di $C$ e nel $k'$esimo cluster di $C'$, e $\lvert C_k \rvert$ come numero di elementi nel $k$esimo cluster.

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

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

Quindi, la misura F individuale del $k$esimo e $k'$esimo cluster può essere calcolata come media armonica della precisione e del richiamo per questi cluster:

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

Ora, per confrontare $C$ e $C'$, diamo un'occhiata alla misura F complessiva. In primo luogo, creeremo una matrice simile a una tabella di contingenza i cui valori sono le singole misure F dei cluster. Supponiamo di aver mappato i cluster di $C$ come righe di una tabella e i cluster di $C'$ come colonne, con valori di tabella corrispondenti a singole misure F. Identificare la coppia di cluster con la massima misura F individuale e rimuovere la riga e la colonna corrispondenti a questi cluster. Ripetere l'operazione finché i grappoli non sono esauriti. Infine, possiamo definire la misura F complessiva:

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

Come puoi vedere, la misura F complessiva è la somma ponderata delle nostre misure F massime individuali per i cluster.

Impostazione dei dati e risultati attesi

Qualsiasi notebook Python adatto per l'apprendimento automatico, come un notebook Jupyter, funzionerà come il nostro ambiente. Prima di iniziare, potresti voler esaminare il file README del mio repository GitHub, il file di esempio readme_help_example.ipynb esteso e il file requirements.txt (le librerie richieste).

Useremo i dati di esempio nel repository GitHub, che è composto da articoli di notizie. I dati sono organizzati con informazioni che includono category , headline , date e short_description :

Possiamo usare i panda per leggere, analizzare e manipolare i dati. Ordineremo i dati per data e selezioneremo un piccolo campione (10.000 titoli di notizie) per la nostra demo poiché il set di dati completo è ampio:

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

Durante l'esecuzione, dovresti vedere il notebook emettere il risultato 30, poiché ci sono 30 categorie in questo campione di dati. Puoi anche eseguire df.head(4) per vedere come vengono archiviati i dati. (Dovrebbe corrispondere alla tabella visualizzata in questa sezione.)

Ottimizzazione delle funzionalità di clustering

Prima di applicare il clustering, dovremmo prima preelaborare il testo per ridurre le caratteristiche ridondanti del nostro modello, tra cui:

• Aggiornare il testo per avere un caso uniforme.
• Rimozione di caratteri numerici o speciali.
• Esecuzione della lemmatizzazione.
• Rimozione delle parole d'arresto.

 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)

I titoli preelaborati risultanti vengono mostrati come processed_input , che puoi osservare eseguendo nuovamente df.head(4) :

Ora, dobbiamo rappresentare ogni titolo come un vettore numerico per potervi applicare qualsiasi modello di machine learning. Esistono varie tecniche di estrazione delle caratteristiche per raggiungere questo obiettivo; useremo TF-IDF (termine frequenza inversa della frequenza del documento). Questa tecnica riduce l'effetto delle parole che ricorrono con alta frequenza nei documenti (nel nostro esempio, i titoli delle notizie), poiché queste chiaramente non dovrebbero essere le caratteristiche determinanti nel raggrupparle o classificarle.

 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

Successivamente, proveremo il nostro primo metodo di clustering, il clustering agglomerato, su questi vettori di caratteristiche.

Metodo di clustering 1: clustering agglomerato

Considerando le categorie di notizie fornite come la soluzione ottimale, confrontiamo questi risultati con quelli del raggruppamento agglomerato (con il numero desiderato di cluster pari a 30 poiché ci sono 30 categorie nel set di dati):

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

Identificheremo i cluster risultanti mediante etichette intere; ai titoli appartenenti allo stesso cluster viene assegnata la stessa etichetta intera. La funzione cluster_measure dal modulo compare_clusters del nostro repository GitHub restituisce la misura F aggregata e il numero di cluster perfettamente corrispondenti in modo da poter vedere quanto fosse accurato il nostro risultato di 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)

Confrontando questi risultati di cluster con la soluzione ottimale, otteniamo una misura F bassa di 0,198 e 0 cluster corrispondenti ai gruppi di classi effettivi, mostrando che i cluster agglomerati non si allineano con le categorie di titoli che abbiamo scelto. Esaminiamo un cluster nel risultato per vedere come appare.

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

Dopo aver esaminato i risultati, vediamo che questo cluster contiene titoli di tutte le categorie:

 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

Quindi, la nostra misura F bassa ha senso considerando che i cluster del nostro risultato non si allineano con la soluzione ottimale. Tuttavia, è importante ricordare che la classificazione di categoria data che abbiamo scelto riflette solo una possibile divisione del set di dati. Una misura F bassa qui non implica che il risultato del clustering sia errato, ma che il risultato del clustering non corrisponde al metodo desiderato di partizionamento dei dati.

Metodo di raggruppamento 2: K-medie

Proviamo un altro popolare algoritmo di clustering sullo stesso set di dati: k-means clustering. Creeremo un nuovo dataframe e utilizzeremo nuovamente la funzione 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)

Come il risultato del clustering agglomerato, il nostro risultato di clustering k-medie ha formato cluster dissimili dalle nostre categorie date: ha una misura F di 0,18 rispetto alla soluzione ottimale. Poiché i due risultati di raggruppamento hanno misure F simili, sarebbe interessante confrontarli tra loro. Abbiamo già i raggruppamenti, quindi dobbiamo solo calcolare la misura F. Innanzitutto, porteremo entrambi i risultati in una colonna, con class_gt con l'output di clustering agglomerato e class_prd con l'output di clustering 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)

Con una misura F maggiore di 0,4, possiamo osservare che i raggruppamenti dei due algoritmi sono più simili tra loro di quanto non lo siano alla soluzione ottima.

Scopri di più sui risultati del clustering avanzato

La comprensione delle metriche di confronto del clustering disponibili amplierà l'analisi del modello di machine learning. Abbiamo visto la metrica di clustering della misura F in azione e ti abbiamo fornito le nozioni di base necessarie per applicare queste conoscenze al tuo prossimo risultato di clustering. Per saperne di più, ecco le mie scelte migliori per ulteriori letture:

• Clustering a confronto: una panoramica di Dorothea Wagner e Silke Wagner
• Confronto dei raggruppamenti: una distanza basata sulle informazioni di Marina Meila
• Misure teoriche dell'informazione per il confronto dei cluster: varianti, proprietà, normalizzazione e correzione per il caso di Nguyen Xuan Vinh, Julien Epps e James Bailey

---

Ulteriori letture sul blog di Toptal Engineering:

• Graph Data Science con Python/NetworkX
• Classificazione delle immagini semi-supervisionata con dati senza etichetta
• Incorporamenti nell'apprendimento automatico: semplificare i dati complessi

Il Toptal Engineering Blog estende la sua gratitudine a Luis Bronchal per aver esaminato gli esempi di codice presentati in questo articolo.