Como obter a probabilidade de pertencer a clusters para k-means?

8

Preciso obter a probabilidade de cada ponto no meu conjunto de dados. A idéia é calcular a matriz de distâncias (a primeira coluna conecta as distâncias ao primeiro cluster, a segunda coluna conte as distâncias ao segundo cluster e etc). O ponto mais próximo tem probabilidade = 1, o mais distante tem probabilidade = 0. O problema é que a função linear (como MinMaxScaller) tem saída onde quase todos os pontos têm quase a mesma probabilidade.

Como escolher a não linearidade para esta tarefa? Como automatizar esse processo em python? Por exemplo, para o ponto mais próximo p=1, para o ponto mais distante que pertence ao cluster p=0.5, para o ponto mais distante p são os almóis 0.

Ou você pode propor outros métodos para calcular essa probabilidade.

Толкачёв Иван
fonte

Respostas:

12

Vamos falar brevemente sobre uma generalização probabilística de k- médias: o Modelo de Mistura Gaussiana (GMM).

Em k -eans, você executa o seguinte procedimento:
- especifique k centróides, inicializando suas coordenadas aleatoriamente
- calcule a distância de cada ponto de dados para cada centróide
- atribua cada ponto de dados ao centróide mais próximo
- atualize as coordenadas do centróide para o média de todos os pontos atribuídos a ele
- itere até a convergência.

Em um GMM, você executa o seguinte procedimento:
- especifica k gaussianos multivariados (denominados componentes ), inicializando sua média e variância aleatoriamente
- calcula a probabilidade de cada ponto de dados sendo produzido por cada componente (às vezes denominado a responsabilidade que cada componente assume pela ponto de dados)
- atribua cada ponto de dados ao componente ao qual ele pertence com a maior probabilidade
- atualize a média e a variação do componente com a média e a variação de todos os pontos de dados atribuídos a ele
- itere até convergência

Você pode perceber a semelhança entre esses dois procedimentos. De fato, k -means é um GMM com componentes de variação fixa. Sob um GMM, as probabilidades (acho) que você procura são as responsabilidades que cada componente assume para cada ponto de dados.

Existe uma implementação do GMM de aprendizado por scikit disponível, se você quiser analisar isso, mas acho que você só quer uma maneira rápida de alterar seu código existente; nesse caso, se você estiver feliz em presumir que seus clusters foram corrigidos de variação de Gauss, você pode transformar sua matriz de distância em elementosy=e-x (fornecendo uma queda exponencial) e calculando o softmax sobre suas colunas (normalizando sua distribuição para P(Y=1 1)+P(Y=2)+...+P(Y=k)=1 1)

Vale ressaltar que a suposição de que seus clusters são gaussianos de variação fixa não é necessariamente válida. Se suas dimensões tiverem escalas totalmente diferentes, isso poderá produzir resultados estranhos, pois as dimensões com unidades de menor magnitude parecerão mais "prováveis". A padronização de seus dados antes de executar o procedimento de armazenamento em cluster deve remediar isso.

R Hill
fonte
1

Por definição, os kmeans devem garantir que o cluster ao qual um ponto está alocado tenha o centróide mais próximo. Portanto, a probabilidade de estar no cluster não é realmente bem definida.

Conforme mencionado, o cluster do GMM-EM fornece uma estimativa de probabilidade de estar em cada cluster e é claramente uma opção.

No entanto, se você deseja permanecer na construção esférica de k-means, provavelmente poderá usar uma suposição / formulação mais simples se desejar atribuir alguma "pontuação de bondade" ao agrupamento de cada ponto. Isso pode ser útil caso você esteja amostrando um subconjunto da população e queira determinar quanto confiar no cluster designado a cada ponto da amostra.

Um esquema simples de "pontuação" poderia ser o primeiro a calcular a distância do escore z do SQRT em todas as dimensões usadas no agrupamento para cada um dos k centróides. Então assumindod1 1 para dk para cada um dos k-centróides, você pode atribuir a pontuação

Ponto=1 1dEu(n-1 1)/Eu=1 1k1 1dEu(n-1 1)

Onde n é o número de dimensões usadas para armazenamento em cluster.

Porque isso (n-1 1)th power on 1 1d? Pense no que acontece no espaço tridimensional com Gravidade ou Eletromagnetismo, onde a intensidade se dissipa pela distância ao quadrado. Da mesma forma, k-means cria aglomerados esféricos em n dimensões. Portanto, se você considerar cada um dos centróides do cluster como fontes pontuais de "energia", ele se dissipará à medida que d aumenta d para a(n-1 1)poder th. Como resultado, em qualquer ponto aleatório, a intensidade de "energia" proveniente de qualquer centróide de cluster é proporcional a1 1dEu(n-1 1) Onde dEué a distância do centróide. Portanto, você pode calcular essa pontuação de bondade que varia entre 0 e 1 e ter uma idéia de quão "confuso" o algoritmo k-means é para qualquer ponto com base nas dimensões e na estrutura do seu problema em questão.

NoNameMLer
fonte
0

Você pode encontrar uma probabilidade de que um ponto de dados dEu será agrupado em um cluster específico kj, P(kj|dEu), executando k-significa centenas de vezes e contando quantas vezes o ponto de dados dEu foi designado ao cluster kj.

Como os IDs de cluster não significam nada na vida real, é possível identificar clusters nas iterações k-means utilizando o valor dos centróides. Ou seja, após cada k-means convergir, remapear os IDs do cluster com base em uma lista de IDs indexados por valores de centróide.

Ulad Kasach
fonte
11
Para quem me rebaixou, seria útil ouvir o porquê. Isso é definido como k-means iterativo e é ensinado nas universidades.
Ulad Kasach 02/02