Como posso agrupar strings por temas comuns?

10

Estou tentando agrupar, por exemplo, strings sobre programação com outras strings sobre programação, strings sobre física com outras strings sobre física, etc., para uma ampla gama de tópicos. Apesar do aspecto linguístico teórico gritante do problema, estou procurando fazer isso usando programação / software.

Resumo: Dado um grande número de strings, como eu os agruparia por tema semântico?

A aplicação específica: tenho ~ 200.000 perguntas triviais que gostaria de categorizar em grupos comuns (carros, computadores, política, Canadá, comida, Barack Obama, etc.).

O que eu procurei: A Wikipedia tem uma lista de kits de ferramentas de processamento de linguagem natural (supondo que o que estou tentando fazer seja realmente chamado de PNL), então observei alguns, mas nenhum parece fazer algo semelhante às minhas necessidades.

Notas: Foi salientado que isso requer conhecimento adicional (por exemplo, um Porsche sendo um carro, C ++ sendo uma linguagem de programação). Suponho que sejam necessários dados de treinamento, mas se eu tiver apenas a lista de perguntas e respostas, como posso gerar dados de treinamento? E então, como uso os dados de treinamento?

Mais notas: Se a formatação atual das minhas perguntas e respostas (embora pareça com JSON, é basicamente um arquivo de texto bruto):

// row 1: is metadata
// row 2: is a very specific kind of "category"
// row 3: is the question
// row 4: is the answer
{
  15343
  A MUSICAL PASTICHE
  Of classical music's "three B's", he was the one born in Hamburg in 1833
  Johannes Brahms
}

Mas antes que alguém aponte que já existe uma categoria, observe que existem ~ 200 mil perguntas e respostas como essa e basicamente tantas "categorias". Estou tentando agrupá-los em grupos mais amplos, como os listados acima. Além disso, essa formatação pode ser alterada para todas as perguntas com muita facilidade, faço-o programaticamente.

E mais notas: na verdade, não sei quantas categorias vou precisar (pelo menos 10 a 20), porque eu mesmo não li todas as perguntas. Eu estava parcialmente esperando ter o número finito determinado de alguma forma durante a categorização. De qualquer forma, sempre posso criar manualmente várias categorias.

Whymarrh
fonte
Como você estava usando cenoura? Da minha breve leitura sobre o assunto, parece que ele deve lidar facilmente com registros de 200k.
Demorou muito mais do que eu pensava, e me forçou a aumentar a quantidade de memória inicial da JVM para 1024m e a memória máxima para 2048m. Não foi tão ruim quanto eu possa ter feito esse som.
Você só precisa de dados de treinamento suficientes e poderá classificar as perguntas nessas categorias. Uma abordagem totalmente automática provavelmente acabará agrupando-os por outros meios, por exemplo, perguntas que contenham a palavra "carro". Você não pode aprender sinônimos ao mesmo tempo que cria um agrupamento.
Quit - Anony-Mousse
Ei, você está fazendo processamento em massa; fornecer à JVM não é realmente um problema. Quanto tempo levou? De onde você estava carregando os documentos? Uma fonte personalizada?
Demorei talvez 10 minutos, mas concordo que o processamento em massa é, por definição, demorado e consome muita memória. Embora toda essa discussão sobre asfixia não fosse o problema, mais uma observação lateral.

Respostas:

4

Esse é um problema bastante padrão na PNL, e as palavras mágicas do Google que você procura são "modelagem de tópicos". Embora suas seqüências de caracteres sejam bastante curtas, você pode ter algum sucesso com a Alocação de Dirichlet Latente ou um método semelhante. Há um bom post de Edwin Chen aqui , que expõe a idéia geral por trás do algoritmo. Os detalhes da implementação são abordados nesta nota por Yi Wang.

Se você está procurando uma solução pronta para o uso, recomendo experimentar o topicmodelspacote para o R, pois isso fornece uma interface razoavelmente boa para o LDA e um modelo de tópico correlacionado mais sofisticado. Também há uma boa lista de implementações mantidas por David Mimno aqui .

Martin O'Leary
fonte
Obrigado, a postagem de Chen parece ser certa sobre o que estou tentando fazer. Existe alguma chance de você ter usado alguma das coisas que listou / fez antes? Estou aqui por motivos completamente novos e gostaria de conhecer o que eu precisaria fazer (usando uma das soluções prontas para uso). Como devo formatar meus "documentos"? Devo aplicar IDs a cada P&R para permitir identificar qual documento está em qual grupo? Como uso os dados emitidos? Como eu disse, não entendo muitos detalhes.
Whymarrh
Eu usei o pacote topicmodels do R bastante. Eu certamente recomendaria que revelasse seu próprio código - há alguma documentação com um exemplo útil em cran.r-project.org/web/packages/topicmodels/vignettes/… . A formatação específica de cada documento realmente não importa, pois tudo será reduzido a uma representação de "saco de palavras". Basta jogar todo o texto associado em uma sequência.
Martin O'Leary
4

Você está tentando resolver dois problemas aqui.

Problema 1: Categorize as sequências de perguntas na categoria apropriada.

Problema 2: Crie categorias apropriadas.

O primeiro problema pode ser resolvido pelos chamados algoritmos supervisionados; muitos classificadores podem fornecer precisão e desempenho muito bons. No entanto, o problema 2, criando categorias do nada (toneladas de dados), é muito mais complicado. Esse é um problema não supervisionado, considerando muitos dados que o computador decide autonomicamente categorias, com base em alguns critérios. Idealmente, esses critérios e o algoritmo devem organizar seus dados ordenadamente em clusters. Estes podem então ser rotulados. No entanto, como essa é uma tarefa muito mais difícil, eu diria que não há aqui uma solução aceitável que dê um bom resultado sem muito esforço de ajuste, o que provavelmente exigiria especialistas.

Então, receio que ainda não haja um botão mágico aqui. O que você pode fazer, no entanto, é ajudar a máquina um pouco. Por exemplo, você pode decidir sobre o conjunto de categorias. Quando você decide as categorias, pode criar dados de treinamento. Nesta configuração, os dados de treinamento são apenas perguntas e pares de categorias corretos.

Quanto mais dados de treinamento, melhor. No entanto, como a tarefa ainda é algo automaticamente, não faz sentido, a princípio, começar a fazer as coisas manualmente. Agora, por que você gostaria de ter dados de treinamento? Avaliação de precisão. Se você deseja bons resultados, é vital que você possa realizar algum tipo de avaliação sobre o desempenho de uma configuração. E a única maneira de fazer isso de maneira sistemática é rotular manualmente algumas questões. Caso contrário, você está cego.

Então, algumas novas questões surgem. Primeiro: Quantos dados de treinamento eu preciso? "Depende". Sem ter visto seus dados ou categorias, não tenho certeza de que adivinhe; mas posso fazer uma "estimativa aproximada" e dizer cerca de 500 perguntas. Note que eu poderia estar desligado por uma ordem de magnitude.

Isso realmente significa que você teria que marcar 500 perguntas manualmente? Sim e não. É possível usar resultados intermediários e alguma inteligência para classificar "bootstrap". No entanto, ainda é um trabalho manual e, quando você pensa sobre isso, 500 perguntas não demoram muito para serem etiquetadas. Ser inteligente aqui pode rapidamente dar resultados piores do que ser diligente.

Quando você tiver dados de treinamento em quantidade suficiente, pegue 75% deles e crie um classificador usando sua ferramenta favorita (por exemplo, os mencionados aqui ou outros enfeites). Agora, deixe o classificador tentar rotular os 25% dos dados contidos e medir a precisão resultante. Se o resultado for bom, tome champanhe. Caso contrário, faça mais dados de treinamento ou tente outro classificador.

TL; DR

Em resumo, eis como eu teria feito isso.

0) Use a supervised learner.
1) Create a category set yourself. 
2) Label manually about 500 questions
3) Use 75% of those to train a classifier.
4) Check performance.
5) If good then cheers else goto 2.

fonte
Uma pequena pergunta: você diz "cerca de 500 perguntas" para os dados de treinamento e para marcá-las manualmente, mas também "eu poderia estar em uma ordem de grandeza"; portanto, se eu usasse perguntas de 5 ou 50 mil, ainda assim marcar manualmente quantos?
A coisa é; sem ter visto seus dados nem ter uma idéia muito clara de todos os detalhes do seu projeto, é difícil fazer uma boa estimativa. No entanto, e isso é importante lembrar, se os 500 forem muito baixos, o esforço de marcação não foi desperdiçado. Você ainda precisa de perguntas rotuladas manualmente para avaliação. Quanto mais dados de avaliação você tiver, melhores serão as avaliações.
Por uma ordem de grandeza, eu quis dizer 50-500-5000. Eu não acho que você precisará classificar 50k. Isso é 1/4 do seu corpus inteiro! Se 500 perguntas forem muito baixas, é possível inicializar os classificadores. A idéia aqui é que você treine o classificador em um pequeno corpus inicial (por exemplo, seu 500) e depois marque o resto. Agora, você pode usar alguns dos casos em que o classificador estava muito confiante para treinar novamente um novo classificador maior.
Outra coisa importante a ter em mente; o desempenho de muitos classificadores não é linear na quantidade de dados de treinamento, mas normalmente será uma curva sigmóide. Isso significa que mais 500 perguntas marcadas podem ser um benefício quase tão bom quanto 5000. Meu conselho é trabalhar em pequenas etapas.
Quais detalhes forneceriam informações adicionais sobre o meu projeto? Posso compartilhar alguns exemplos de perguntas para mostrar minha formatação, mas estou disposto a adaptar o formato das minhas Perguntas e Respostas para se adequar ao processo de categorização. Agradeço a ajuda.