Por que apenas o valor médio é usado no método de agrupamento (K-means)?

8

Nos métodos de agrupamento, como médias K , a distância euclidiana é a métrica a ser usada. Como resultado, calculamos apenas os valores médios em cada cluster. E então são feitos ajustes nos elementos com base em sua distância para cada valor médio.

Fiquei me perguntando por que a função gaussiana não é usada como métrica? Em vez de usar xi -mean(X), podemos usar exp(- (xi - mean(X)).^2/std(X).^2). Portanto, não apenas a similaridade entre os clusters é medida (média), mas a similaridade dentro do cluster também é considerada (std). Isso também é equivalente ao modelo de mistura gaussiano ?

Está além da minha pergunta aqui, mas acho que a mudança de média pode surgir a mesma pergunta acima.

lennon310
fonte
1
Este tópico pode ser útil. stats.stackexchange.com/questions/76866/… Pesquise suas tags para outras perguntas relevantes.
DL Dahly
@DLDahly Obrigado Dahly. Podemos ver o GMM baseado em EM como um meio k ponderado (com diferentes pesos nas variações)?
lennon310
Não é assim que eu pensaria; ao contrário, vejo k-means como um GMM, onde as variações são limitadas a zero.
DL Dahly

Respostas:

5

Existem literalmente milhares de variações de k-means . Incluindo atribuição suave, variância e covariância (geralmente denominada Gaussian Mixture Modeling ou algoritmo EM).

No entanto, gostaria de salientar algumas coisas:

  • O K-significa não se baseia na distância euclidiana. É baseado na minimização da variação . Como a variação é a soma das distâncias euclidianas ao quadrado, a atribuição mínima de variação é a que possui a menor euclidiana ao quadrado e a função de raiz quadrada é monótona. Por razões de eficiência, é realmente mais inteligente não calcular a distância euclidiana (mas usar os quadrados)

  • Se você conectar uma função de distância diferente ao k-significa, ela poderá parar de convergir. Você precisa minimizar o mesmo critério nas duas etapas ; o segundo passo é recalcular os meios. A estimativa do centro usando a média aritmética é um estimador de mínimos quadrados e minimizará a variação. Como ambas as funções minimizam a variação, os meios k devem convergir. Se você deseja garantir a convergência com outras distâncias, use o PAM (particionando em torno do medoids. O medóide minimiza as distâncias dentro do cluster para funções de distância arbitrárias).

Mas no final, k-means e todas as suas variações são IMHO mais de uma otimização (ou mais precisamente, um algoritmo de quantização vetorial ) do que realmente um algoritmo de análise de cluster. Na verdade, eles não "descobrirão" a estrutura. Eles massagearão seus dados em k partições. Se você fornecer dados uniformes, sem nenhuma estrutura além da aleatoriedade, o k-means ainda encontrará quantos "aglomerados" você desejar. O k-means está feliz em retornar resultados que são essencialmente aleatórios .

Possui QUIT - Anony-Mousse
fonte
1
+1. No entanto, a afirmação de que o K-means não é um cluster parece muito radical, também um ponto de vista de "mineração de dados". Historicamente, o K-means é uma análise clássica de agrupamentos particionados. O fato de particionar alegremente dados "não estruturados" não o exclui do domínio do agrupamento: muitos tipos de análises podem ser, por assim dizer, mal utilizados e fornecer resultados tolos.
ttnphns
Mais um ponto: K-means is not based on Euclidean distancenão há espaço suficiente na sua resposta. Você e eu discutimos sobre isso no passado e mostrei que a minimização de variância está relacionada à soma do euclidiano par a dentro de cluster d ^ 2.
ttnphns
Estou afirmando claramente a relação com a distância euclidiana por variação. O problema é que você precisa substituir a variação por uma medida diferente (depois escolher a atribuição e atualizar de acordo), não trocar euclidianos e esperar que a média ainda seja significativa.
Quit - Anony-Mousse
Historicamente, k-means foi publicado por Lloyd como " Quantização de mínimos quadrados em PCM". Da mesma forma, Steinhaus tinha o desejo de realizar a quantização. O que explica muito bem por que o SSQ é usado, pois o SSQ é o erro quadrático da discretização. MacQueen menciona a análise de cluster como uma aplicação do algoritmo, mas sugere o uso de uma versão modificada do algoritmo que pode adicionar ou remover clusters conforme desejado (nesse ponto, na verdade, começa a ser mais do que quantificação).
QuIT - Anony-Mousse
O ponto que estou tentando enfatizar no final é analisar a quantização de vetores , não apenas o "agrupamento", pois a pesquisa de agrupamento recente é dominada pelo ponto de vista de mineração de dados (e na maioria das vezes não é mais baseado em k-means ) . A quantização vetorial pode ser o termo de pesquisa muito melhor (porque muito mais preciso) .
QuIT - Anony-Mousse
3

Existem muitas técnicas diferentes de agrupamento por aí, e o K-means é apenas uma abordagem. Como DL Dahly comentou, os algoritmos EM podem ser usados ​​para agrupar da mesma maneira que você descreveu. Vale a pena notar que a principal diferença entre o K-mean e o uso de EM com um modelo de mistura guassiano para agrupamento é a forma dos aglomerados: o centróide ainda aproximará de perto a média dos pontos no grupo, mas o K-mean dará uma cluster esférico, enquanto um núcleo gaussiano dará um elipsóide.

O cluster hierárquico usa uma abordagem completamente diferente. O clustering baseado na densidade é motivado por uma heurística semelhante à do cluster baseado na média, mas obviamente fornece resultados diferentes. Existem muitas técnicas de agrupamento que não consideram nenhum tipo de média.

Realmente, quando se trata disso, a escolha do algoritmo é uma função do domínio do problema e da experimentação (isto é, ver o que funciona).

David Marx
fonte
Obrigado David. Eu acho que o Hierarchical fornece resultados diferentes dos kmeans porque as definições de distância entre dois grupos não são as mesmas. Pode não ser fácil determinar qual métrica usar e se a variação deve ser incluída. Parece que diferentes grupos de pessoas desenvolveram suas próprias métricas em seus próprios problemas. O método apenas deu a esse problema um bom resultado, mas ainda não tinha suporte teórico sobre a opção dos métodos de agrupamento.
lennon310