Implementação k-means com matriz de distância personalizada na entrada

14

Alguém pode me indicar uma implementação de k-means (seria melhor se no matlab) que pode levar a matriz de distância na entrada? A implementação padrão do matlab precisa da matriz de observação na entrada e não é possível alterar de forma personalizada a medida de similaridade.

clustering matlab k-means Eugenio
fonte
2
Você pode tentar gerar dados brutos correspondentes à sua matriz de distâncias euclidianas e inseri-los no K-Means. Uma abordagem fácil alternativa poderia ser usar o método Ward de agrupamento hierárquico da matriz: K-Means e Ward compartilham ideologia semelhante do que é um cluster.
ttnphns
Além disso, para ttnphns e Not Durrett, você pode encontrar Está correto usar a distância de Manhattan com a ligação entre os cluster de Ward no cluster hierárquico? interessante
steffen
Não no Matlab, mas a página do python em " é possível especificar sua própria função de distância usando scikits-learn-k-means" pode usar qualquer uma das 20 métricas diferentes no scipy.spatial. distância.
Denis

Respostas:

13

Como o k-means precisa encontrar os meios de diferentes subconjuntos dos pontos que você deseja agrupar, não faz muito sentido solicitar uma versão do k-means que use uma matriz de distância como entrada.

Você pode tentar k-medoids . Existem algumas implementações do matlab disponíveis.

NF
fonte
1
Oi, obrigado pela resposta; em vez de fornecer diretamente a matriz de distância, seria possível fornecer como entrada uma métrica de distância personalizada? O ponto é que eu tenho que comparar dois métodos de agrupamento e, como no segundo uso uma matriz de similaridade personalizada, quero usar a mesma abordagem com kmeans para obter uma comparação justa.
Eugenio
2
O ELKI permite que você use funções de distância arbitrárias com k-means. Observe que o algoritmo pode falhar na convergência. O K-means é realmente projetado para a distância euclidiana ao quadrado (soma dos quadrados). Com outras distâncias, a média não pode mais otimizar e, boom, o algoritmo acabará por não convergir. Sério, considere usar k-medoids. Na verdade, foi escrito para permitir o uso da idéia de k-means com distâncias arbitrárias .
QuIT - Anony-Mousse
Há também é pyclustering um python / biblioteca C ++ que permite fornecer uma função métrica personalizada: github.com/annoviko/pyclustering/issues/417
CpILL
7

Você pode transformar sua matriz de distâncias em dados brutos e inseri-los no cluster K-Means. As etapas seriam as seguintes:

1) As distâncias entre seus N pontos devem ser quadradas euclidianas. Execute a " centralização dupla " da matriz: Média da linha de substrato de cada elemento; no resultado, a média da coluna do substrato de cada elemento; no resultado, adicione matriz média a cada elemento; divida por menos 2. A matriz que você tem agora é a matriz SSCP (soma de quadrados e produto cruzado) entre seus pontos em que a origem é colocada no centro geométrico da nuvem de N pontos. (Leia a explicação da dupla centralização aqui .)

2) Execute o PCA (análise de componentes principais) nessa matriz e obtenha a matriz de carregamento de componentes NxN . É provável que algumas das últimas colunas sejam todas 0, - portanto, corte-as. O que você fica agora são, na verdade, pontuações dos componentes principais, as coordenadas dos seus N pontos nos componentes principais que passam, como eixos, pela sua nuvem. Esses dados podem ser tratados como dados brutos adequados para a entrada K-Means.

PS Se suas distâncias não forem geometricamente corretas euclidianas ao quadrado, você poderá encontrar um problema: a matriz SSCP pode não ser positiva (semi) definida. Esse problema pode ser resolvido de várias maneiras, mas com perda de precisão.

ttnphns
fonte
Obrigado pela sua resposta! Na verdade, eu não tenho uma matriz de distâncias reais, mas uma matriz de similaridade (0 ... 1) entre objetos, e as semelhanças não são calculadas exatamente usando distâncias euclidianas, mas com um algoritmo personalizado que leva em consideração os dados brutos, mas não no maneira padrão. Acho que, neste caso, não posso aplicar seu procedimento, estou certo?
Eugenio
Você ainda pode, depois de converter semelhanças em distâncias. O último provavelmente não será verdadeiro euclidiano (e, portanto, o SSCP terá alguns autovalores negativos); tente adicionar pequenas constantes às distâncias até que o SSCP perca neg. eig. Também existem outras maneiras de solucionar o problema. E lembre-se de que você duplica a matriz central de distâncias ao quadrado .
ttnphns
PS E, a propósito. Se sua matriz é semelhanças, então, bem, é ainda melhor. Você apenas a trata como a matriz SSCP da qual eu estava falando e faz PCA com ela. Ainda assim, permanece o problema de possíveis autovalores negativos.
Tdnphns
@ttnphns, desculpe, eu estou perdendo a sua explicação para o passo 1. A matriz de distância X(digamos N * N) vai ser simétrica, assim colMeans(X) =rowMeans(X) e uma vez que você subtrair linha ou col meios: Y=X-rowMeans(X), mean(Y)é 0.
Zhubarb
1
@Zhubarb, quando digo You could turn your matrix of distances into raw data(pontos 1 e 2), refiro-me, essencialmente, à escala multidimensional de Torgerson (MDS) , na qual a dupla centralização é o passo inicial. Pesquise neste site (e também no Google) sobre esse procedimento. "Dupla centralização" é a conversão de distâncias (ao quadrado) na matriz de produto escalar correspondente definida sobre a origem colocada no centróide da nuvem dos pontos.
Ttnphns
3

Por favor, consulte este artigo, escrito por um dos meus conhecidos;)

http://arxiv.org/abs/1304.6899

Trata-se de uma implementação generalizada de k-means, que usa uma matriz de distância arbitrária como entrada. Pode ser qualquer matriz não negativa simétrica com uma diagonal zero. Observe que ele pode não fornecer resultados sensatos para matrizes de distância estranhas. O programa está escrito em C #.

O código-fonte pode ser obtido visitando o link acima, clicando em Outros formatos e, em seguida, clicando em Baixar fonte. Você receberá um arquivo .tar.gz contendo Program.cs. Como alternativa, o código-fonte também pode ser copiado do PDF.

szali
fonte
3

Você pode usar a Java Machine Learning Library. Eles têm uma implementação K-Means. Um dos construtores aceita três argumentos

  1. K Value.
  2. Um objeto disso é uma instância da classe DistanceMeasure .
  3. Número de iterações.

Pode-se facilmente estender a classe DistanceMeasure para alcançar o resultado desejado. A idéia é retornar valores de uma matriz de distância personalizada no método measure (Instance x, Instance y) dessa classe.

O K-Means é garantido para convergir assumindo certas propriedades da métrica de distância. Distância euclidiana, distância de Manhattan ou outras métricas padrão atendem a essas premissas. Como uma métrica de distância personalizada pode não atender a essas suposições, o construtor possui um terceiro parâmetro que especifica o número de iterações a serem executadas para a construção do clusterer.

Chaitanya Shivade
fonte