Identificando o desconhecido com métricas de cluster

O clustering é um método de aprendizado de máquina não supervisionado para dividir dados em grupos com base apenas nos recursos de cada amostra. A classificação de dados em clusters pode ajudar a identificar semelhanças desconhecidas entre amostras ou revelar discrepâncias no conjunto de dados. No mundo real, o agrupamento tem importância em diversos campos, do marketing à biologia: Os aplicativos de agrupamento incluem segmentação de mercado, análise de redes sociais e diagnóstico por imagem médica.

Como esse processo não é supervisionado, vários resultados de agrupamento podem se formar em torno de diferentes recursos. Por exemplo, imagine que você tenha um conjunto de dados composto de várias imagens de calças vermelhas, calças pretas, camisas vermelhas e camisas pretas. Um algoritmo pode encontrar clusters com base na forma da roupa, enquanto outro pode criar grupos com base na cor.

Ao analisar um conjunto de dados, precisamos de uma maneira de medir com precisão o desempenho de diferentes algoritmos de agrupamento; podemos querer contrastar as soluções de dois algoritmos ou ver quão próximo um resultado de agrupamento está de uma solução esperada. Neste artigo, exploraremos algumas das métricas que podem ser usadas para comparar diferentes resultados de agrupamento obtidos dos mesmos dados.

Noções básicas sobre clustering: um breve exemplo

Vamos definir um conjunto de dados de exemplo que usaremos para explicar vários conceitos de métricas de agrupamento e examinar quais tipos de agrupamentos ele pode produzir.

Primeiro, algumas notações e termos comuns:

• $D$: o conjunto de dados
• $A$, $B$: dois clusters que são subconjuntos do nosso conjunto de dados
• $C$: o agrupamento de verdade de $D$ com o qual compararemos outro agrupamento
  • Clustering $C$ tem clusters $K$, $C = {C_1, …, C_k}$
• $C'$: um segundo agrupamento de $D$
  • Agrupar $C'$ tem $K'$ clusters, $C' = {C^\prime_1, …, C^\prime_{k^\prime}}$

Os resultados do clustering podem variar com base não apenas nos recursos de classificação, mas também no número total de clusters. O resultado depende do algoritmo, de sua sensibilidade a pequenas perturbações, dos parâmetros do modelo e das características dos dados. Usando nosso conjunto de dados mencionado anteriormente de calças e camisas pretas e vermelhas, há uma variedade de resultados de agrupamento que podem ser produzidos a partir de diferentes algoritmos.

Para distinguir entre o clustering geral $C$ e nossos clusters de exemplo, usaremos um $c$ minúsculo para descrever nossos clusters de exemplo:

• $c$, com agrupamentos baseados na forma: $c = {c_1, c_2}$, onde $c_1$ representa calças e $c_2$ representa camisas
• $c'$, com clusters baseados na cor: $c' = {c'_1, c'_2}$, onde $c'_1$ representa roupas vermelhas e $c'_2$ representa roupas pretas
• $c''$, com agrupamentos baseados em forma e cor: $c'' = {{c^{\prime \prime}}_1, {c^{\prime \prime}}_2, {c^{\prime \prime}}_3, {c^{\prime \prime}}_4}$, onde ${c^{\prime \prime}}_1$ representa calças vermelhas, ${c^{\prime \prime}}_2 $ representa calças pretas, ${c^{\prime \prime}}_3$ representa camisas vermelhas e ${c^{\prime \prime}}_4$ representa camisas pretas

Agrupamentos adicionais podem incluir mais de quatro agrupamentos com base em recursos diferentes, como se uma camisa é sem mangas ou com mangas.

Como visto em nosso exemplo, um método de agrupamento divide todas as amostras em um conjunto de dados em subconjuntos disjuntos não vazios. No cluster $c$, não há imagem que pertença ao subconjunto de calças e ao subconjunto de camisa: $c_1 \cap c_2 = \emptyset$. Este conceito pode ser estendido; não há dois subconjuntos de qualquer cluster com a mesma amostra.

Uma visão geral das métricas de comparação de cluster

A maioria dos critérios para comparar agrupamentos pode ser descrita usando a matriz de confusão do par $C, C'$. A matriz de confusão seria uma matriz $K \times K'$ cujo $kk'$th elemento (o elemento na $k$th linha e $k'$th coluna) é o número de amostras na interseção dos clusters $ C_k$ de $C$ e $C'_{k'}$ de $C'$:

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

Vamos dividir isso usando nosso exemplo simplificado de calças e camisas pretas e vermelhas, supondo que o conjunto de dados $D$ tenha 100 calças vermelhas, 200 calças pretas, 200 camisas vermelhas e 300 camisas pretas. Vamos examinar a matriz de confusão de $c$ e $c''$:

Como $K = 2$ e $K'' = 4$, esta é uma matriz $2 \times 4$. Vamos escolher $k = 2$ e $k'' = 3$. Vemos que o elemento $n_{kk'} = n_{23} = 200$. Isso significa que a interseção de $c_2$ (camisas) e ${c^{\prime\prime}}_3$ (camisas vermelhas) é 200, o que está correto, pois $c_2 \cap {c^{\prime\prime} }_3$ seria simplesmente o conjunto de camisas vermelhas.

As métricas de clustering podem ser amplamente categorizadas em três grupos com base no método de comparação de cluster subjacente:

Neste artigo, abordamos apenas algumas das muitas métricas disponíveis, mas nossos exemplos servirão para ajudar a definir os três grupos de métricas de clustering.

Contagem de pares

A contagem de pares requer o exame de todos os pares de amostras e, em seguida, a contagem de pares em que os agrupamentos concordam e discordam. Cada par de amostras pode pertencer a um dos quatro conjuntos, onde as contagens de elementos do conjunto ($N_{ij}$) são obtidas da matriz de confusão:

• $S_{11}$, com elementos $N_{11}$: os elementos do par estão no mesmo cluster em $C$ e $C'$
  • Um par de duas camisas vermelhas ficaria abaixo de $S_{11}$ ao comparar $c$ e $c''$
• $S_{00}$, com elementos $N_{00}$: os elementos do par estão em clusters diferentes em $C$ e $C'$
  • Um par de camisa vermelha e calça preta ficaria abaixo de $S_{00}$ ao comparar $c$ e $c''$
• $S_{10}$, com elementos $N_{10}$: os elementos do par estão no mesmo cluster em $C$ e clusters diferentes em $C'$
  • Um par de uma camisa vermelha e uma camisa preta ficaria abaixo de $S_{10}$ ao comparar $c$ e $c''$
• $S_{01}$, com elementos $N_{01}$: os elementos do par estão em clusters diferentes em $C$ e o mesmo cluster em $C'$
  • $S_{01}$ não tem elementos ($N_{01} = 0$) ao comparar $c$ e $c''$

O índice Rand é definido como $(N_{00} + N_{11})/(n(n-1)/2)$, onde $n$ representa o número de amostras; também pode ser lido como (número de pares tratados de forma semelhante)/(número total de pares). Embora teoricamente seu valor varie entre 0 e 1, seu intervalo geralmente é muito mais estreito na prática. Um valor mais alto significa mais similaridade entre os agrupamentos. (Um índice Rand de 1 representaria uma combinação perfeita onde dois agrupamentos têm agrupamentos idênticos.)

Uma limitação do índice Rand é seu comportamento quando o número de clusters aumenta para se aproximar do número de elementos; neste caso, converge para 1, criando desafios para medir com precisão a similaridade de agrupamento. Várias versões aprimoradas ou modificadas do índice Rand foram introduzidas para resolver esse problema. Uma variação é o índice Rand ajustado ; no entanto, assume que dois agrupamentos são sorteados aleatoriamente com um número fixo de agrupamentos e elementos de agrupamento.

Teoria da Informação

Essas métricas são baseadas em noções genéricas da teoria da informação. Discutiremos dois deles: entropia e informação mútua (MI).

A entropia descreve quanta informação existe em um agrupamento. Se a entropia associada a um agrupamento for 0, então não há incerteza sobre o agrupamento de uma amostra escolhida aleatoriamente, o que é verdade quando há apenas um agrupamento.

MI descreve quanta informação um agrupamento fornece sobre o outro. O MI pode indicar o quanto conhecer o cluster de uma amostra em $C$ reduz a incerteza sobre o cluster da amostra em $C'$.

Informação mútua normalizada é MI que é normalizada pela média geométrica ou aritmética das entropias dos agrupamentos. O MI padrão não é limitado por um valor constante, portanto, as informações mútuas normalizadas fornecem uma métrica de agrupamento mais interpretável.

Outra métrica popular nesta categoria é a variação de informação (VI) que depende tanto da entropia quanto do MI dos agrupamentos. Seja $H(C)$ a entropia de um agrupamento e $I(C, C')$ o MI entre dois agrupamentos. VI entre dois agrupamentos pode ser definido como $VI(C,C') = H(C)+H(C')-2I(C,C')$. Um VI de 0 representa uma combinação perfeita entre dois agrupamentos.

Definir sobreposição

Definir métricas de sobreposição envolve determinar a melhor correspondência para clusters em $C$ com clusters em $C'$ com base na sobreposição máxima entre os clusters. Para todas as métricas nesta categoria, 1 significa que os agrupamentos são idênticos.

A medida de correspondência máxima varre a matriz de confusão em ordem decrescente e corresponde primeiro à maior entrada da matriz de confusão. Em seguida, ele remove os clusters correspondentes e repete o processo sequencialmente até que os clusters se esgotem.

A medida F é outra métrica de sobreposição definida. Ao contrário da medida de correspondência máxima, a medida F é frequentemente usada para comparar um agrupamento com uma solução ótima, em vez de comparar dois agrupamentos.

Aplicando métricas de cluster com F-measure

Devido ao uso comum da F-measure em modelos de aprendizado de máquina e aplicativos importantes, como mecanismos de pesquisa, exploraremos a F-measure com mais detalhes com um exemplo.

Definição da medida F

Vamos supor que $C$ seja nossa solução de verdade, ou ótima. Para qualquer $k$th cluster em $C$, onde $k \in [1, K]$, calcularemos uma F-measure individual com cada cluster no resultado de clustering $C'$. Esta F-measure individual indica quão bem o cluster $C^\prime_{k'}$ descreve o cluster $C_k$ e pode ser determinada através da precisão e recall (duas métricas de avaliação de modelo) para esses clusters. Vamos definir $I_{kk'}$ como a interseção de elementos no $k$th cluster de $C$ e $k'$th cluster de $C'$, e $\lvert C_k \rvert$ como o número de elementos no cluster $k$th.

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

  

• Lembre-se $r = \frac{I_{kk'}}{\lvert C_{k} \rvert}$

Então, a F-measure individual dos clusters $k$th e $k'$th pode ser calculada como a média harmônica da precisão e recall para esses clusters:

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

Agora, para comparar $C$ e $C'$, vejamos a medida F geral. Primeiro, criaremos uma matriz semelhante a uma tabela de contingência cujos valores são as F-medidas individuais dos clusters. Vamos supor que mapeamos os clusters de $C$ como linhas de uma tabela e os clusters de $C'$ como colunas, com valores de tabela correspondentes a F-measures individuais. Identifique o par de clusters com a medida F individual máxima e remova a linha e a coluna correspondentes a esses clusters. Repita isso até que os clusters estejam esgotados. Finalmente, podemos definir a medida F geral:

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

Como você pode ver, a medida F geral é a soma ponderada de nossas medidas F individuais máximas para os clusters.

Configuração de dados e resultados esperados

Qualquer notebook Python adequado para aprendizado de máquina, como um notebook Jupyter, funcionará como nosso ambiente. Antes de começarmos, você pode querer examinar o README do meu repositório GitHub, o arquivo de exemplo readme_help_example.ipynb estendido e o arquivo requirements.txt (as bibliotecas necessárias).

Usaremos os dados de amostra no repositório GitHub, que é composto por artigos de notícias. Os dados são organizados com informações, incluindo category , headline , date e short_description :

Podemos usar pandas para ler, analisar e manipular os dados. Classificaremos os dados por data e selecionaremos uma pequena amostra (10.000 manchetes de notícias) para nossa demonstração, pois o conjunto de dados completo é grande:

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

Ao executar, você deverá ver a saída do notebook com o resultado 30, pois existem 30 categorias nesta amostra de dados. Você também pode executar df.head(4) para ver como os dados são armazenados. (Deve corresponder à tabela exibida nesta seção.)

Otimizando recursos de cluster

Antes de aplicar o clustering, devemos primeiro pré-processar o texto para reduzir os recursos redundantes do nosso modelo, incluindo:

• Atualizando o texto para ter um caso uniforme.
• Removendo caracteres numéricos ou especiais.
• Fazendo a lematização.
• Removendo palavras de parada.

 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)

Os títulos pré-processados ​​resultantes são mostrados como processed_input , que você pode observar executando novamente df.head(4) :

Agora, precisamos representar cada título como um vetor numérico para poder aplicar qualquer modelo de aprendizado de máquina a ele. Existem várias técnicas de extração de recursos para conseguir isso; estaremos usando TF-IDF (frequência do documento inverso da frequência do termo). Essa técnica reduz o efeito de palavras que ocorrem com alta frequência em documentos (no nosso exemplo, manchetes de notícias), pois esses claramente não devem ser os recursos decisivos para agrupá-los ou classificá-los.

 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

Em seguida, testaremos nosso primeiro método de agrupamento, agrupamento aglomerativo, nesses vetores de recursos.

Método de agrupamento 1: agrupamento aglomerativo

Considerando as categorias de notícias fornecidas como a solução ideal, vamos comparar esses resultados com os do cluster aglomerativo (com o número desejado de clusters como 30, pois há 30 categorias no conjunto de dados):

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

Vamos identificar os clusters resultantes por rótulos inteiros; títulos pertencentes ao mesmo cluster recebem o mesmo rótulo de número inteiro. A função cluster_measure do módulo compare_clusters do nosso repositório GitHub retorna a F-measure agregada e o número de clusters perfeitamente correspondentes para que possamos ver a precisão do resultado do 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)

Ao comparar esses resultados de cluster com a solução ótima, obtemos uma medida F baixa de 0,198 e 0 clusters combinando com grupos de classes reais, mostrando que os clusters aglomerativos não se alinham com as categorias principais que escolhemos. Vamos verificar um cluster no resultado para ver como ele se parece.

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

Ao examinar os resultados, vemos que este cluster contém títulos de todas as categorias:

 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

Portanto, nossa baixa F-measure faz sentido considerando que os clusters de nosso resultado não se alinham com a solução ótima. No entanto, é importante lembrar que a classificação de determinada categoria que escolhemos reflete apenas uma possível divisão do conjunto de dados. Uma medida F baixa aqui não implica que o resultado do agrupamento esteja errado, mas que o resultado do agrupamento não correspondeu ao nosso método desejado de particionamento dos dados.

Método de agrupamento 2: K-means

Vamos tentar outro algoritmo de agrupamento popular no mesmo conjunto de dados: agrupamento k-means. Vamos criar um novo dataframe e usar a função cluster_measure novamente:

 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)

Assim como o resultado de agrupamento aglomerativo, nosso resultado de agrupamento k-means formou agrupamentos que são diferentes de nossas categorias dadas: Ele tem uma medida F de 0,18 quando comparado à solução ótima. Como os dois resultados de agrupamento têm medidas F semelhantes, seria interessante compará-los. Já temos os agrupamentos, então só precisamos calcular a medida F. Primeiro, vamos trazer os dois resultados em uma coluna, com class_gt tendo a saída de cluster aglomerativa e class_prd tendo a saída de cluster 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)

Com uma medida F maior de 0,4, podemos observar que os agrupamentos dos dois algoritmos são mais semelhantes entre si do que com a solução ótima.

Descubra mais sobre os resultados de clustering aprimorados

Uma compreensão das métricas de comparação de cluster disponíveis expandirá sua análise do modelo de aprendizado de máquina. Vimos a métrica de agrupamento F-measure em ação e fornecemos o básico necessário para aplicar esses aprendizados ao seu próximo resultado de agrupamento. Para saber ainda mais, aqui estão minhas principais escolhas para leitura adicional:

• Comparando Clusterings - Uma Visão Geral por Dorothea Wagner e Silke Wagner
• Comparando agrupamentos—uma distância baseada em informações por Marina Meila
• Medidas Teóricas da Informação para Comparação de Clusters: Variantes, Propriedades, Normalização e Correção para Acaso por Nguyen Xuan Vinh, Julien Epps e James Bailey

---

Leitura adicional no Blog Toptal Engineering:

• Gráficos de ciência de dados com Python/NetworkX
• Classificação de imagem semi-supervisionada com dados não rotulados
• Incorporações no aprendizado de máquina: simplificando dados complexos

O Toptal Engineering Blog agradece a Luis Bronchal por revisar os exemplos de código apresentados neste artigo.