Agrupando uma longa lista de strings (palavras) em grupos de similaridade

31

Tenho o seguinte problema em mãos: Tenho uma lista muito longa de palavras, possivelmente nomes, sobrenomes etc. É necessário agrupar essa lista de palavras, de modo que palavras semelhantes, por exemplo palavras com distância de edição semelhante (Levenshtein), apareçam no mesmo cluster. Por exemplo, "algoritmo" e "alogritmo" devem ter grandes chances de aparecer no mesmo cluster.

Conheço bem os métodos clássicos de cluster não supervisionado, como o k-means cluster, o clustering EM na literatura de reconhecimento de padrões. O problema aqui é que esses métodos funcionam em pontos que residem em um espaço vetorial. Eu tenho palavras de cordas na minha mão aqui. Parece que a questão de como representar strings em um espaço vetorial numérico e calcular "meios" de agrupamentos de strings não é suficientemente respondida, de acordo com meus esforços de pesquisa até agora. Uma abordagem ingênua para atacar esse problema seria combinar o agrupamento k-Means com a distância de Levenshtein, mas a questão ainda permanece: "Como representar" os meios "das cordas?". Existe um peso chamado de peso TF-IDF, mas parece que ele está relacionado principalmente à área de agrupamento de "documentos de texto", não ao agrupamento de palavras únicas. http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf

Minha pesquisa nessa área ainda está em andamento, mas eu também queria obter idéias daqui. O que você recomendaria neste caso, alguém conhece algum método para esse tipo de problema?

Ufuk Can Bicici
fonte
1
Eu aprendi sobre a existência de uma variante de k-means chamada "K-medoids". pt.wikipedia.org/wiki/K-medoids Ele não funciona com a distância euclidiana L2 e não precisa do cálculo de médias. Ele usa o ponto de dados mais próximo dos outros em um cluster como o "medóide".
amigos estão dizendo sobre ufuk can bicici
1
It seems that there are some special string clustering algorithms. Se você vem especificamente de um campo de mineração de texto, não de estatísticas / análise de dados, esta declaração é garantida. No entanto, se você aprender a ramificação de clustering, descobrirá que não existem algoritmos "especiais" para dados de string. O "especial" é como você pré-processa esses dados antes de inseri-los em uma análise de cluster.
precisa saber é o seguinte
Observe a diferença entre a propagação de afinidade e o cluster K-Means e como isso afetará o tempo de computação. Quora.com/…
Gabriel Alon

Respostas:

37

Recomendação Seconding @ mican para propagação de afinidade .

Do artigo: L Frey, Brendan J. e Delbert Dueck. "Agrupando passando mensagens entre pontos de dados." Science 315,5814 (2007): 972-976. .

É super fácil de usar através de muitos pacotes. Funciona em qualquer coisa que você possa definir a similaridade pareada. O que você pode obter multiplicando a distância de Levenshtein por -1.

Juntei um exemplo rápido usando o primeiro parágrafo da sua pergunta como entrada. No Python 3:

import numpy as np
import sklearn.cluster
import distance

words = "YOUR WORDS HERE".split(" ") #Replace this line
words = np.asarray(words) #So that indexing with a list will work
lev_similarity = -1*np.array([[distance.levenshtein(w1,w2) for w1 in words] for w2 in words])

affprop = sklearn.cluster.AffinityPropagation(affinity="precomputed", damping=0.5)
affprop.fit(lev_similarity)
for cluster_id in np.unique(affprop.labels_):
    exemplar = words[affprop.cluster_centers_indices_[cluster_id]]
    cluster = np.unique(words[np.nonzero(affprop.labels_==cluster_id)])
    cluster_str = ", ".join(cluster)
    print(" - *%s:* %s" % (exemplar, cluster_str))

A saída foi (exemplos em itálico à esquerda do cluster dos quais são exemplos):

  • ter: chances, editar, mão, ter, alto
  • seguinte: seguinte
  • problem: problem
  • I: eu, a, at, etc, na lista de
  • possivelmente: possivelmente
  • cluster: cluster
  • palavra: por, e, por muito tempo, precisa, deve, muito, palavra, palavras
  • similar: similar
  • Levenshtein: Levenshtein
  • distance: distance
  • o: que, o, isso, para, com
  • mesmo: exemplo, lista, nomes, mesmo, tal, sobrenomes
  • algoritmo: algoritmo, alogritmo
  • apareça: apareça, apareça

Executando-o em uma lista de 50 nomes aleatórios :

  • Diane: Deana, Diane, Dionne, Gerald, Irina, Lisette, Minna, Nicki, Ricki
  • Jani: Clair, Jani, Jason, Jc, Kimi, Lang, Marcus, Maxima, Randi, Raul
  • Verline: Destino, Kellye, Marylin, Mercedes, Sterling, Verline
  • Glenn: Elenor, Glenn, Gwenda
  • Armandina: Armandina, Augustina
  • Shiela: Ahmed, Estella, Milissa, Shiela, Thresa, Wynell
  • Laureen: Outono, Haydee, Laureen, Lauren
  • Alberto: Albertha, Alberto, Robert
  • Lore: Ammie, Doreen, Eura, Josef, Lore, Lori, Porter

Parece ótimo para mim (isso foi divertido).

Lyndon White
fonte
é possível ter o mesmo algoritmo usando apenas o sklearn? ou use scipy.spatial.distance com hamming? qual é a vantagem de usar levenshtein? Eu acho que vou ter que tentar usar esta pergunta: stackoverflow.com/questions/4588541/...
pierre
1
@pierre Levenshtein é o que eu chamaria de "distância do corretor ortográfico", é um bom indicador da chance de um erro de ortografia humana. Damerau Levenshtein pode ser ainda melhor. Não sei se a Distância de Hamming é definida para seqüências de caracteres de comprimentos não iguais. Só permite trocas, não inserções. determinar como preencher / aparar a corda mais razoavelmente é quase tão difícil quanto calcular a distância de Levenshtein. Você deve preencher / aparar o início? O fim? Alguns do meio?
Lyndon White
Se você realmente queria evitar a dependência de distâncias. você poderia usar a implementação de código Rossetta
Lyndon White
lendo o en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance, posso ver como a transposição pode fazer a diferença, especialmente para erros de digitação e python. Eu posso ver como posso usar isso em uma lista de palavras e obter o "mais próximo", mas pode não ser o mais importante. Eu tenho que pegar minha lista e verificar com o tf-idf. Legal obrigado
pierre
1
@dduhaime quase certamente. Em geral, a Propagação por Afinidade funciona para perferências não-simétricas, mas como isso é simétrico, vá em frente. Estou certo de que algo no SciPy tem um tipo de matriz triangular que se identifica como uma matriz completa. Eu estive na terra de julia-lang por muito tempo e não consigo me lembrar de como isso é feito em python. (Em julia você usaria Symmetric)
Lyndon White
5

Use algoritmos de agrupamento de gráficos, como o agrupamento de Louvain, o RNSC (Restricted Neighborhood Search Clustering), o Affinity Propgation Clustering (APC) ou o algoritmo Markov Cluster (MCL).

micans
fonte
E o método K-medoids que encontrei? Preciso implementar essa solução o mais rápido possível, para que pareça uma boa solução para mim. Estou ciente da existência desses métodos baseados em gráficos, mas tenho medo de não poder dispor do tempo necessário para compreendê-los e implementá-los.
Ufuk Can Bicici
Para todos eles, o software está disponível com acordos de licenciamento bastante restritivos, como o GNU GPL. Eu não sou um grande fã do tipo de algoritmo k-mediods principalmente por causa do parâmetro k, mas depende de você naturalmente. Se você precisar de uma implementação interna, acho que a APC e a MCL são provavelmente as mais fáceis de implementar. Se você fosse fazer isso, experimente-os primeiro, é claro.
micans
2

Você pode tentar o modelo de espaço vetorial com n-gramas das palavras como entradas de espaço vetorial. Eu acho que você teria que usar uma medida como a semelhança de cosseno neste caso, em vez de editar a distância.

peace_within_reach
fonte