Parece que para médias K e outros algoritmos relacionados, o agrupamento é baseado no cálculo da distância entre pontos. Existe alguém que funciona sem ele?
machine-learning
clustering
data-mining
k-means
user154510
fonte
fonte
Respostas:
Um exemplo desse método são os Modelos de Mistura Finita (por exemplo, aqui ou aqui ) usados para agrupar. Em FMM você considerar a distribuição ( ) da sua variável X como uma mistura de K distribuições ( f 1 , . . . , F k ):f X K f1,...,fk
onde é um vector de parâmetros θ = ( π ' , θ ' 1 , . . . , θ ' K ) ' e π k é uma proporção de k 'th distribuição na mistura e θ k é um parâmetro (ou parâmetros) de distribuição f k .ϑ ϑ=(π′,ϑ′1,...,ϑ′k)′ πk k ϑk fk
Um caso específico para dados discretos é a Análise de Classe Latente (por exemplo, aqui ) definida como:
onde é a probabilidade de observar a classe latente k (ou seja, π k ), P ( x ) é a probabilidade de observar um valor x e P ( x | k ) é a probabilidade de x estar na classe k .P(k) k πk P(x) x P(x|k) x k
Normalmente, o algoritmo EM FMM e LCA EM é usado para estimativa, mas a abordagem bayesiana também é possível, mas um pouco mais exigente devido a problemas como identificação de modelo e troca de etiqueta (por exemplo, o blog de Xi'an ).
Portanto, não há medida de distância, mas um modelo estatístico que define a estrutura (distribuição) dos seus dados. Por esse outro nome desse método, "cluster baseado em modelo".
Confira os dois livros no FMM:
Um dos mais pacotes de agrupamento populares que usa FMM é
mclust(confira aqui ou aqui ) que é implementado em R . No entanto, FMMs mais complicados também são possíveis, verifique, por exemplo,flexmixpacote e sua documentação . Para o LCA, existe um pacote R poLCA .fonte
Existem várias abordagens de cluster baseadas em grade . Eles não calculam distâncias, porque isso geralmente geraria tempo de execução quadrático. Em vez disso, eles particionam os dados e os agregam em células da grade. Mas a intuição por trás de tais abordagens geralmente está intimamente relacionada às distâncias.
Existem vários algoritmos de armazenamento em cluster para dados categóricos , como COOLCAT e STUCCO. As distâncias não são fáceis de usar com esses dados (a codificação one-hot é um hack e não gera distâncias particularmente significativas). Mas eu nunca ouvi falar de alguém usando esses algoritmos ...
Existem abordagens de cluster para gráficos. Mas eles se reduzem a problemas gráficos clássicos, como localização de clique ou quase clique e coloração de gráfico, ou estão intimamente conectados ao cluster baseado em distância (se você tiver um gráfico ponderado).
Clusters baseados em densidade como DBSCAN têm um nome diferente e não se concentram em minimizar distâncias; mas "densidade" é geralmente especificada em relação a uma distância, portanto tecnicamente esses algoritmos são baseados em distância ou em grade.
A parte essencial da sua pergunta que você deixou de lado é quais são seus dados ?
fonte
Além das respostas legais anteriores, eu sugeriria considerar os modelos de mistura de Dirichlet e os modelos de processo hierárquico hierárquico baseado em Bayesiano . Para uma visão geral abrangente e abrangente das abordagens e métodos para determinar um número ideal de clusters , consulte esta excelente resposta no StackOverflow : /programming//a/15376462/2872891 .
fonte
Uma abordagem puramente discriminativa é a "maximização regularizada da informação", de Gomes et al . Não há noção de similaridade / distância envolvida nela.
A idéia é ter uma regressão logística como o modelo que coloca pontos nas caixas. Mas, em vez de treiná-lo para maximizar alguma forma de probabilidade logarítmica dos rótulos das classes, a função objetivo é aquela que coloca pontos em diferentes grupos.
A extensão para métodos de kernel ou redes neurais para cluster não linear é simples.
fonte