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?
fonte
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.Respostas:
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:
A saída foi (exemplos em itálico à esquerda do cluster dos quais são exemplos):
Executando-o em uma lista de 50 nomes aleatórios :
Parece ótimo para mim (isso foi divertido).
fonte
Symmetric
)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).
fonte
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.
fonte