Como faço para agrupar strings com base em uma relação entre duas strings?

5

Se você não conhece o WEKA, você pode tentar uma resposta teórica. Eu não preciso de código / exemplos literais ...

Eu tenho um enorme conjunto de dados de cadeias de caracteres em que eu quero agrupar as cadeias para encontrar as mais relacionadas, estas poderiam também ser vistas como duplicadas. Eu já tenho um conjunto de pares de strings para os quais eu sei que eles são duplicados um ao outro, então, agora eu quero fazer uma mineração de dados nesses dois conjuntos.

O resultado que estou procurando é um sistema que me retornaria os possíveis pares de strings mais relevantes para os quais não sabemos ainda que são duplicatas, acredito que eu precise de cluster para isso, qual tipo?

Note que quero me basear na comparação de ocorrências de palavras , não na interpretação ou no significado.

Aqui está um exemplo de duas cadeias das quais sabemos que são duplicadas (em nossa visão sobre elas):

  • O tempo está muito frio e está chovendo.

  • Está chovendo e o tempo está muito frio.

Agora, as seguintes strings também existem (menos relevantes, ignorando as palavras de parada):

  • O tempo está realmente tão frio hoje?

  • Os dias chuvosos são terríveis.

  • Eu vejo o sol lá fora.

O software retornaria as duas sequências a seguir como as mais relevantes, que não são conhecidas como duplicadas:

  • O tempo está muito frio e está chovendo.

  • O tempo está realmente tão frio hoje?

Em seguida, marcaria isso como duplicado ou não duplicado e me apresentaria outro casal.

Como faço para implementar isso da maneira mais eficiente que posso aplicar a um grande conjunto de dados?

    
por Tom Wijsman 15.08.2011 / 17:07
fonte

3 respostas

4

Isto é obviamente não trivial, mas existem algoritmos que pelo menos tentam fazer coisas como esta. Eu apresso-me a acrescentar, no entanto, que eles são estatísticos, então tentar usar apenas duas frases como base será extremamente duvidoso na melhor das hipóteses.

A abordagem usual é algo assim:

  1. filtrar palavras de parada
  2. use um dicionário de sinônimos para substituir uma palavra canônica por cada palavra
  3. conta ocorrências de palavras em cada documento / sentença
  4. calcula a distância do cosseno entre o (s) documento (s) base e cada documento similar candidato
  5. escolha o N mais próximo dos documentos base

Note que há espaço para muita variação aqui. Por exemplo, o dicionário de sinônimos pode obter resultados consideravelmente melhores se for sensível ao contexto e manter o contexto que você geralmente deseja manter as palavras interrompidas, pelo menos até que essa etapa seja concluída. Por exemplo, considere seus documentos de base sobre o clima sendo comparado a: "Estou resfriado" e "Está frio". Se você seguir as etapas acima, elas ficarão apenas "frias" na etapa 2 e ambas parecerão igualmente próximas dos documentos base.

Com um passo de thesaurus sensível ao contexto (uma ontologia, na verdade), você usaria as palavras extras para desambiguar os dois usos de "frio", então quando você calcula distâncias, alguém se referiria à doença chamada "o frio "e o outro para" tempo frio ". Os documentos base se refeririam tanto ao tempo frio, então seu resultado mostraria "É frio" como semelhante, mas "eu tenho um resfriado" como diferente.

Se você está tentando manter as coisas mais simples, no entanto, você pode pular o dicionário de sinônimos completamente, e apenas conter as palavras. Isso torna "chuvoso" e "chuvoso" ambos em "chuva", então quando você faz comparações, todos aparecem como sinônimos.

No que diz respeito aos detalhes, existem algumas listas de stopwords facilmente encontrado . Pelo menos nos meus testes, a escolha não é particularmente crítica.

Para um dicionário de sinônimos, eu usei o Moby Thesaurus , com algum processamento (substancial) para basicamente invertê-lo - - ou seja, em vez de encontrar vários sinônimos para uma palavra, encontre uma palavra canônica para uma determinada entrada.

Não há tantos artigos em contexto sinônimo sensível / pesquisa de definição - mas alguns ainda são muito bons . Muito trabalho sobre a "web semântica" e ontologias relacionadas também está ao longo desta linha (embora muito pouco seja de grande ajuda no seu caso).

Por causa disso, o Porter Stemmer é bem conhecido. Há uma versão mais nova e ligeiramente modificada (Porter2) que deve ser coberta em algum lugar na (s) mesma (s) página (s). Outro algoritmo bem conhecido é o Lancaster Stemmer . Há também o lemador Lovins, mas eu realmente não recomendaria 1 - embora ainda seja amplamente conhecido porque foi o primeiro algoritmo (conhecido) de stemming publicado. Note que a maioria (todos?) Destes tira apenas sufixos, não prefixos.

Alguns documentos discutem a distância do cosseno. É bem sabido que mesmo a entrada da Wikipedia é bem decente.

Algumas pessoas já reuniram essas peças em kits de ferramentas coerentes (pelo menos geralmente tentam ser coerentes), programas completos, etc. Alguns exemplos razoavelmente bem conhecidos incluem WordNet , NLTK , Apache OpenNLP e Freeling .

1 Em particular, Lovins só remove um sufixo um de uma palavra. Se você tivesse, por exemplo, "Loverly" e "amorosamente", Porter reduziria ambos para "lov" e eles apareceriam como sinônimos, mas Lovins os reduziria a "lover" e "loving", respectivamente, e eles apareceria como diferente. É possível repetir o algoritmo Lovins até que ele não remova mais sufixos, mas o resultado não é muito bom - Porter tem um pouco de sensibilidade de contexto (por exemplo) ele só remove um sufixo se não remover outro; múltiplas aplicações de Lovins não levariam isso em conta.

    
por 18.08.2011 / 06:59
fonte
1

O artigo Agrupamento de dados emparelhados por recozimento determinístico parece cobrir exatamente o que você precisa: você tem uma medida de similaridade entre pares e você deseja formar um determinado número de grupos com base nessa medida. (Consegui encontrar algumas pré-impressões de texto completo gratuitas deste artigo um tempo atrás, então talvez você não precise pagar para acessar essa, infelizmente eu não tenho tempo para procurá-las novamente agora).

Eu usei essa técnica no processamento de sinal ( veja p15) , mas não mineração de dados baseada em texto, então não tenho certeza de quanto eu poderei ajudar com os detalhes.

    
por 18.08.2011 / 07:00
fonte
0

Parece muito ambicioso. Isso é quase equivalente a entender uma sentença.

Eu não consigo nem pensar em uma maneira de parametrizar uma frase; você provavelmente não quer apenas inserir duas strings de caracteres em seu classificador. Você precisaria de um modelo muito complexo para descrever seu problema e, portanto, um enorme conjunto de dados. Seu modelo precisaria aprender quais palavras são sinônimos / antônimos ... entre muitas coisas que precisaria aprender.

    
por 15.08.2011 / 17:41
fonte