Por que o k-significa não fornece o mínimo global?

17

Eu li que o algoritmo k-means apenas converge para um mínimo local e não para um mínimo global. Por que é isso? Posso pensar logicamente como a inicialização pode afetar o clustering final e existe a possibilidade de clustering abaixo do ideal, mas não encontrei nada que provasse isso matematicamente.

Além disso, por que o k-significa um processo iterativo? Não podemos apenas diferenciar parcialmente a função objetiva dos centróides, equipará-lo a zero para encontrar os centróides que minimizam essa função? Por que precisamos usar a descida gradiente para atingir o mínimo passo a passo?

clustering k-means convergence gradient-descent minimum Prateek Kulkarni
fonte

4

Quando uma função suave possui vários mínimos locais, necessariamente cada um deles será um ponto crítico (onde todas as derivadas parciais desaparecem); portanto, seu algoritmo está correto, mas geralmente é inútil: você pode obter uma equação terrivelmente complicada com um grande número de soluções (mesmo infinitas). Mas há outra questão: como você sabe que a função objetiva k-means é diferenciável em qualquer lugar?

whuber

1

Acredito que quando diferencio parcialmente a função objetivo em relação a um centróide, os pontos no cluster de outro centróide desaparecem na derivada. Portanto, o centróide que conseguirmos minimizará apenas a soma das distâncias ao quadrado de apenas um cluster específico.

Prateek Kulkarni

3

É parcialmente isso, mas realmente não explica o comportamento. De mais importância é o fato de que a atribuição de pontos aos centróides é a grande parte do que k-significa está fazendo. (Depois que a tarefa é feita, os centróides são facilmente calculados e não há mais nada a fazer.) Essa tarefa é discreta : não é algo que possa ser diferenciado. Além disso, é combinatoriamente complexo: existem

maneiras de atribuir

pontos a

clusters. De fato, é completamente desnecessário usar a descida de gradiente para encontrar os centróides.

O (n^{k})

$O(n^k)$

n

$n$

k

$k$

whuber

Concordo que a parte da tarefa não pode ser diretamente colocada na forma matemática. Somente por este passo isolado podemos mover os centróides para minimizar a função. Eis como eu vejo a descida do gradiente: se, por uma inicialização incorreta, estivermos perto dos mínimos locais, a descida do gradiente o arrastará para os mínimos locais. Se você estiver próximo dos mínimos globais por uma boa inicialização, ele os arrastará para os mínimos globais. Mas como esse movimento está mapeando para atribuições de cluster é um borrão.

Prateek Kulkarni

A não diferenciabilidade é superestimada: Leon Bottou fez algum trabalho na estimativa de K-Means com descida de gradiente estocástico em conjuntos de dados muito grandes, com algum sucesso. A não diferenciabilidade não apresenta um problema tão grande lá como em muitos problemas devido aos muitos pontos de dados. (por exemplo, redes convolucionais também são localmente não diferenciáveis, mas funcionam muito bem de qualquer maneira, assim como muitas arquiteturas de redes neurais com a função de transferência linear retificada). A verdadeira razão aqui é o mínimo múltiplo.

bayerj

10

Você pode ver o k-means como uma versão especial do algoritmo EM, o que pode ajudar um pouco.

Digamos que você esteja estimando uma distribuição normal multivariada para cada cluster com a matriz de covariância fixa à matriz de identidade para todos, mas a variável média onde é o índice do cluster. É evidente que, se os parâmetros são conhecidos, é possível atribuir a cada ponto o seu conjunto de probabilidade máxima (ou seja. O para que o raio de $\mu_i$ $i$ $\{\mu_i\}$ $p$ $\mu_i$ $p$ no mínimo). O algoritmo EM para esse problema é quase equivalente ao k-means.

Ao contrário, se você sabe quais os pontos pertencem a qual cluster, você pode estimar o ideal . A solução de forma fechada a esta (que encontra um ótimo global) basicamente diz que para encontrar os modelos de máxima verossimilhança $\mu_i$ $\{\hat\mu_i\}$ integrar sobre todas as tarefas possíveis de pontos para clusters. Como, mesmo com apenas trinta pontos e dois grupos, existem cerca de um bilhão dessas atribuições possíveis, isso é inviável de calcular.

Em vez disso, podemos adivinhar os parâmetros ocultos (ou os parâmetros do modelo) e iterar as duas etapas (com a possibilidade de terminar no máximo local). Se você permite que cada cluster assuma uma responsabilidade parcial por um ponto, você acaba com o EM; se você apenas atribuir o cluster ideal, obtém k-means.

Portanto, resumo executivo: em termos probabilísticos, existe uma solução global, mas requer que você itere todos os agrupamentos possíveis. Claramente, se você tem uma função objetiva, o mesmo é verdade. Você pode iterar sobre todas as soluções e maximizar a função objetivo, mas o número de iterações é exponencial no tamanho dos seus dados.

Pedro
fonte

Bem colocado! Vou marcar isso como a resposta!

Prateek Kulkarni

4

Este é o problema que você deseja resolver:

\begin{aligned} min_{x} \sum_{i = 1}^{n} \sum_{j = 1}^{k} x_{i j} | | p_{i} - c_{j} | |^{2} \\ subject to: \\ \sum_{j = 1}^{k} x_{i j} = 1 \forall i \\ c_{j} is the centroid of cluster j \\ x_{i j} \in {0, 1} \forall i, j \end{aligned}

$\begin{align} &\min_{x} \sum_{i=1}^n \sum_{j=1}^k x_{ij} || p_i - c_j||^2\\ &\text{subject to:} \\ &\sum_{j=1}^k x_{ij} = 1 \quad \forall i\\ & c_j\textit{ is the centroid of cluster j}\\ &x_{ij} \in \{0,1\} \quad \forall i, j \\ \end{align}$

A variável binária indica se o ponto está ou não atribuído ao cluster . Os símbolos e denotam as coordenadas do ponto e do centróide do ésimo cluster, respectivamente. Ambos estão localizados em $x_{ij}$ $i$ $j$ $p_i$ $c_j$ $i$ $j$ , onde é a dimensionalidade dos pontos de dados. $\mathbb{R}^d$ $d$

O primeiro grupo de restrições diz que cada ponto deve ser atribuído a exatamente um cluster. O segundo grupo de restrições (que não temos definido matematicamente) dizer que as coordenadas do centrde de aglomerado realmente dependem valores de variáveis. Podemos, por exemplo, expressar esta restrição como se segue: $j$ $x_{ij}$

c_{j} = \frac{\sum_{i} x_{i j} p_{i j}}{\sum_{i} x_{i j}}

$\begin{equation} c_j = \frac{\sum_{i} x_{ij} p_{ij}}{\sum_{i} x_{ij}} \end{equation}$

No entanto, em vez de lidar com essas restrições não lineares, em K-Means, resolvemos (aproximadamente) um problema diferente que tem a mesma solução ótima que o nosso problema original:

\begin{aligned} min_{x} \sum_{i = 1}^{n} \sum_{j = 1}^{k} x_{i j} | | p_{i} - y_{j} | |^{2} \\ subject to: \\ \sum_{j = 1}^{k} x_{i j} = 1 \forall i \\ x_{i j} \in {0, 1} \forall i, j \\ y_{j} \in R^{d} \forall j \end{aligned}

$\begin{align} &\min_{x} \sum_{i=1}^n \sum_{j=1}^k x_{ij} || p_i - y_j||^2\\ &\text{subject to:} \\ &\sum_{j=1}^k x_{ij} = 1 \quad \forall i\\ &x_{ij} \in \{0,1\} \quad \forall i, j \\ &y_j \in \mathbb{R}^d \quad \forall j \end{align}$

Em vez de minimizar a distância dos centróides, minimizamos a distância para qualquer conjunto de pontos que proporcionem uma solução melhor. Acontece que esses pontos são exatamente os centróides.

Agora, para resolver esse problema, iteramos nas etapas 2-3 deste algoritmo, até a convergência:

$y_j$
$y_{j}$ $x_{ij}$
$x_{ij}$ variáveis e encontre os valores ideais para $y_{j}$ variáveis.

Em cada etapa, a função objetivo melhora (ou permanece a mesma quando o algoritmo converge), pois a solução encontrada na etapa anterior está no espaço de pesquisa da etapa atual. No entanto, como estamos corrigindo algumas das variáveis em cada etapa, este é um procedimento de pesquisa local que não garante a otimização.

Felizmente, os problemas de otimização nas etapas 2 e 3 podem ser resolvidos de forma fechada. Se soubermos $x_{ij}$ (ou seja, se soubermos a qual cluster cada ponto está atribuído), os melhores valores para $y_j$ variáveis são os centróides de clusters. Se conhecermos valores para $y_j$ , obviamente, a melhor escolha para $x_{ij}$ variáveis é atribuir cada ponto ao ponto mais próximo $y_j$ .

Behrouz Babaki
fonte

2

Um exemplo simples pode ajudar ..

Vamos definir o conjunto de pontos a serem agrupados como A = {1,2,3,4}.

Digamos que você esteja tentando encontrar 2 grupos apropriados para A (2 médias). Existem (pelo menos) dois ajustes diferentes que satisfazem a condição estacionária dos meios k.

Configuração 1:

Center1 = 1, Cluster1 = {1}
Center2 = 3, Cluster1 = {2,3,4}

Aqui, o objetivo é 2. Na verdade, esse é um ponto de sela (tente center1 = 1 + epsilone center1 = 1 - epsilon)

Configuração 1:

Center1 = 1.5, Cluster1 = {1,2}
Center2 = 3.5, Cluster1 = {3,4}

aqui o objetivo é 1/4.

Se k-means fosse inicializado como a primeira configuração, ele seria bloqueado .. e isso não significa um mínimo global.

Você pode usar uma variante do exemplo anterior para criar dois mínimos locais diferentes. Pois A = {1,2,3,4,5}, definir cluster1={1,2}e cluster2={3,4,5}resultaria no mesmo valor objetivo que cluster1={1,2,3}ecluster2={4,5}

Finalmente, o que aconteceria se você escolher

A = {1,2,3,4,6}
center1={2.5} cluster1={1,2,3,4} and 
center1={6} cluster1={6}

vs

center1={2} cluster1={1,2,3} and 
center1={5} cluster1={4,6}

?

user25611
fonte

0

[Isso foi antes de @ Peter responder]
Depois de uma pequena discussão (na seção de comentários), sinto que tenho que responder minha própria pergunta.

I believe that when I partially differentiate the objective function with respect to one centroid, the points in the cluster of another centroid vanish in the derivative. So, the centroid we can get will minimize only the sum of squared distances of only the particular cluster.

@whuber adds:

That's partly it, but does not really explain the behavior. Of more import is the fact that the assignment of points to centroids is the big part of what k-means is doing. (Once the assignment is made, the centroids are easily computed and there's nothing left to do.) That assignment is discrete: it's not something that can be differentiated at all.

It would be awesome if anybody has more to add.

Prateek Kulkarni
fonte

0

Everybody has explained everything, but I would like to add that if a sample data is not distributed as a Gaussian distribution then it can stuck to a local minima. In the K-means algorithm we are actually trying to get that.

explorer
fonte

Rather than Gaussian, I think you mean “unimodal”

Peter Leopold

Por que o k-significa não fornece o mínimo global?

Respostas: