Correspondência de itens semelhantes de um conjunto

10

Estou tentando combinar itens. Dado um conjunto de itens, posso classificar em uma escala de 0 a 100 de quão semelhantes eles são entre si. Por exemplo, se o item é leite e o item também é leite, a semelhança entre e seria 100%. Se for refrigerante, a similaridade entre e seria, talvez, 80% e assim por diante.nn1 1n2n1 1n2n3n1 1n3

Estou tentando descobrir como agrupar os itens em grupos de itens semelhantes, mas é um problema desafiador. Eu me deparo com o seguinte problema: Um cavalo é semelhante a uma vaca, que é semelhante a uma cabra, que é em parte semelhante ao queijo de cabra, que é semelhante ao queijo, que está correlacionado com biscoitos. No entanto, eu não esperaria que um cavalo estivesse no mesmo grupo que biscoitos. Cada item pode estar correlacionado em pares, mas o começo e o fim podem não estar.n

Alguma ideia?

Jason
fonte
Na biologia evolutiva, os resultados desse agrupamento pareado são chamados de árvores filogênicas ; portanto, você pode adicioná-lo ao seu conjunto de termos de pesquisa úteis.
hardmath

Respostas:

7

O que você deseja fazer aqui é particionar N observações em K clusters que exibem propriedades semelhantes. Isso é chamado de cluster e você pode encontrar mais informações aqui .

Como você já possui uma medida de similaridade numérica, isso me faz pensar em usar o algoritmo K-Means , no qual você opera em várias etapas:

  • Inicialize centróides de cluster aleatoriamente
  • Atribua cada observação ao cluster correspondente ao centróide mais próximo.
  • Atualize os centróides como a nova média dos elementos no cluster.

Você pode verificar a convergência quando os centróides pararem de se mover ou dentro de um determinado limite.

Isso garantiria que os itens de cada cluster estivessem um pouco correlacionados, e você pode ter clusters mais refinados aumentando o número de clusters no algoritmo (o "K"). Encontrar o número de clusters depende de cada problema, e eu recomendo que você tente vários valores para seus problemas, veja o que sai agrupado e veja o que faz sentido.

Espero que ajude.

Charles Menguy
fonte
5

Eu acho que o que você está procurando é chamado "análise de cluster" ou "clustering". Existem muitos algoritmos diferentes. No seu caso, você deseja alguns "clustering de conectividade", ou seja, agrupar elementos com base em uma propriedade que vincula cada um.

Veja os algoritmos de agrupamento em scikits.learn (código Python) e as referências mencionadas lá.

GertVdE
fonte