Execute o agrupamento K-means (ou seus parentes próximos) com apenas uma matriz de distância, não dados de pontos por recurso

22

Quero executar o agrupamento K-means nos objetos que tenho, mas os objetos não são descritos como pontos no espaço, ou seja, por objects x featuresconjunto de dados. No entanto, sou capaz de calcular a distância entre dois objetos (ela se baseia em uma função de similaridade). Então, eu descarto a matriz de distância objects x objects.

Eu implementei K-means antes, mas isso ocorreu com a entrada do conjunto de dados de pontos; e com a entrada da matriz de distância, não está claro para mim como atualizar os clusters para serem os "centros" do cluster sem uma representação de ponto. Como isso seria feito normalmente? Existem versões do K-means ou métodos próximos a isso?

rato
fonte
Como assim, não são descritos como pontos?
curioso

Respostas:

24

Obviamente, k-means precisa ser capaz de calcular meios .

No entanto, existe uma variação bem conhecida dele conhecida como k-medoids ou PAM (Partitioning Around Medoids), onde o medóide é o objeto existente mais central do cluster. O K-medoids só precisa das distâncias aos pares.

Anony-Mousse -Reinstate Monica
fonte
21

Você está descrevendo exatamente a configuração do problema do kernel -means; quando você não pode representar um ponto de dados como um vetor euclidiano, mas se ainda puder calcular (ou definir) o produto interno entre dois pontos de dados, poderá fazer o kernel do algoritmo. A página a seguir fornece uma breve descrição do algoritmo:k

Kernel página -meansk

Esse truque do kernel é uma idéia muito popular e fundamental em Estatística e aprendizado de máquina.

Página Wiki no truque do kernel

Se você estiver interessado, o livro Aprendendo com Kernels, de Bernhard Schölkopf e Alexander J. Smola, será uma introdução muito interessante.

Esta nota de Max Welling parece muito legal; Além disso, se você estiver usando R você pode dar uma olhada este pacote de R .

O MDS pode ser uma maneira de resolver seu problema, mas não ataca diretamente o problema que você deseja resolver; enquanto o kernel significa.

d_ijk_stra
fonte
Eu queria incluir mais links, mas não consegui devido à baixa reputação. Esta nota de Max Welling nota parece muito bom; além disso, se você estiver usando R, poderá dar uma olhada neste pacote R
d_ijk_stra
(+1) Bem-vindo ao site. Eu adicionei os links no seu comentário ao corpo da postagem, bem como um ao texto Schölkopf e Smola.
cardeal
9

O @gung está absolutamente correto, sugerindo o dimensionamento multidimensional (MDS) como uma ferramenta preliminar para criar points X dimensions dados fora da matriz de distância. Vou adicionar apenas alguns traços. O agrupamento K-significa implica distâncias euclidianas . O MDS fornecerá coordenadas de pontos em dimensões, garantindo distâncias euclidianas. Você deve usar o MDS métrico e solicitar o número de dimensões o maior possível, pois seu objetivo é minimizar o erro de reconfigurar os dados, não mapeá-los em 2D ou 3D.

E se você não tiver o software MDS em mãos, mas tiver algumas funções de matriz, como decomposição de autovalor ou decomposição de valor singular? Em seguida, você mesmo pode executar o MDS métrico simples - Torgerson MDS, também conhecido como Análise de Coordenadas Principais (PCoA). Isso equivale a uma análise um pouco "distorcida" dos componentes principais. Não vou descrevê-lo aqui, embora seja bastante simples. Você pode ler sobre isso em muitos lugares, por exemplo, aqui .

Finalmente, é possível programar "meios K para entrada da matriz à distância" diretamente - sem chamar ou escrever funções executando PCoA ou outro MDS métrico. Sabemos que (a) a soma dos desvios quadrados do centróide é igual à soma das distâncias euclidianas quadradas aos pares, divididas pelo número de pontos; e (b) saber calcular distâncias entre centróides de cluster fora da matriz de distância ; (c) e sabemos ainda como as soma dos quadrados estão inter-relacionadas em K-médias. Tudo isso faz da redação do algoritmo que você deseja uma tarefa direta e não complexa. Deve-se lembrar, porém, que K-means é apenas para distâncias euclidianas / espaço euclidiano. Use K-medoids ou outros métodos para distâncias não euclidianas.

Uma pergunta semelhante .

ttnphns
fonte
7

Certamente não sei como é "normalmente" feito e, para constar, não sei muito sobre análise de cluster. No entanto, você conhece o Dimensionamento multidimensional ? ( Aqui está outra referência, o wiki , e você pode pesquisar CV sob a tag de .) O dimensionamento multidimensional leva em uma matriz de distâncias aos pares, que soa como a sua situação. No MDS, você pode obter os locais dos objetos no espaço de menor dimensão necessário para representá-los adequadamente. Eu acho que você poderia usar esses locais para fazer uma análise de cluster subsequente como k-means; Como alternativa, depois de obter a saída, talvez você não precise mais da CA.

Não sei se você usa R, mas aqui está a visão da tarefa para psicometria, que inclui uma seção sobre MDS em R. Hope que ajuda.

- Reinstate Monica
fonte
4

k

No seu caso, o que você basicamente precisa fazer é:

  1. D
  2. DijDjEu
  3. Dc
  4. Sc=-12Dc
  5. ScScS~c
  6. S~c=VΛV
  7. n-1X=VΛ1/2

n

blubb
fonte
Os passos descritos são nada menos que a Análise das Coordenadas Principais, mencionada na minha resposta.
ttnphns
Por favor, exemplifique sua etapa 5. Subtrair o (s) último (s) autovalor (es) dos elementos da matriz S parece não ajudar a tornar S positivo semidefinido.
ttnphns
@ttnphns: Basicamente é PCA, sim, mas não exige que as distâncias sejam métricas. A descrição da etapa 5 foi lamentável, obrigado por identificá-la. Agora está claro?
Blubb
Subtraindo a soma dos valores próprios negativos a partir de todos os valores próprios da matriz e, em seguida, restauração S é equivalente a subtrair desta soma dos elementos da diagonal de S. Esta endeed marcas S positivo (semi) definida, mas ...
ttnphns
... mas dessa maneira é muito ruim, no sentido de que os dados euclidianos resultantes X produzem distâncias euclidianas D_new, que estão muito longe das dissimilaridades originais D. Portanto, eu não recomendaria o passo 5. Parece muito melhor simplesmente definir valores negativos. autovalores para 0 e pule para a etapa 7. Ou, abordagem um pouco mais fina: defina autovalores negativos para 0, redimensione valores próprios positivos para que somarem originais (= trace (S)) e, em seguida, pule para a etapa 7. É assim que parece para mim.
ttnphns
2

Seus dados também podem ser vistos como uma rede e você pode usar um dos muitos algoritmos de cluster de rede disponíveis. Para isso, você provavelmente precisará aplicar um limite nos pesos das arestas e transformar distâncias em semelhanças. Não é o modo "estatístico" de fazer as coisas, mas a análise de cluster é um problema subespecífico e, como as ferramentas exploratórias, os algoritmos de clustering de rede funcionam muito bem.

micans
fonte
2

Não sei por que é tão incomum na literatura, no entanto, a solução sugerida por @gung e @ttnphns (primeiro projetando suas distâncias aos pares em um espaço euclidiano usando a Análise de Coordenadas Principais, por exemplo, neste pacote, se você usar R, e depois fazer K-significa o modo usual) é simples e não requer algoritmos especializados. Eu pessoalmente o usei aqui incorporado em uma estrutura de otimização e funcionou bastante bem.

Francesco Napolitano
fonte
1

Com relação ao clustering e ao MDS, sugiro os seguintes recursos:

Essas referências também cobrem bem os tópicos de funções de similaridade e distância (medidas de proximidade) para dados binários e contínuos.

user1137731
fonte