k-significa vs k-significa ++

Até onde eu sei, o k-means escolhe os centros iniciais aleatoriamente. Como eles são baseados em pura sorte, eles podem ser muito mal selecionados. O algoritmo K-means ++ tenta resolver esse problema, espalhando os centros iniciais uniformemente.

• Os dois algoritmos garantem os mesmos resultados? Ou é possível que os centróides iniciais mal escolhidos levem a um resultado ruim, não importa quantas iterações.

• Digamos que haja um determinado conjunto de dados e um determinado número de clusters desejados. Nós executamos um algoritmo k-means desde que ele convergisse (sem mais movimento do centro). Existe uma solução exata para esse problema de cluster (dado SSE) ou o k-means produzirá resultados às vezes diferentes ao executar novamente?

• Se houver mais de uma solução para um problema de cluster (dado conjunto de dados, número determinado de clusters), o K-means ++ garante um resultado melhor ou apenas mais rápido? Por melhor, quero dizer menor SSE.

A razão pela qual estou fazendo essas perguntas é porque estou procurando um algoritmo k-means para agrupar um grande conjunto de dados. Encontrei alguns k-means ++, mas também existem algumas implementações CUDA. Como você já sabe, o CUDA está usando a GPU e pode executar mais centenas de threads em paralelo. (Para realmente acelerar todo o processo). Mas nenhuma das implementações CUDA - que eu encontrei até agora - tem inicialização k-means ++.

O K-means começa com a alocação de centros de cluster aleatoriamente e, em seguida, procura soluções "melhores". K-means ++ começa com a alocação de um centro de cluster aleatoriamente e, em seguida, procura por outros centros, dado o primeiro. Assim, ambos os algoritmos usam inicialização aleatória como um ponto de partida, por isso pode dar resultados diferentes em diferentes execuções. Como exemplo, você pode conferir esta palestra: Agrupando como um exemplo de problema de inferência , cerca de 40 minutos há exemplos de execuções k-médias, mas toda a palestra é interessante.

Então, respondendo suas perguntas:

• Não, porque há uma inicialização aleatória, diferentes execuções podem gerar resultados diferentes (veja exemplos na palestra). Eles devem fornecer resultados comparáveis, mas isso não é garantido. Além disso, como todos os centros são inicializados aleatoriamente em k-médias, ele pode fornecer resultados diferentes de k-médias ++.
• K-significa pode dar resultados diferentes em execuções diferentes.
• O documento k-means ++ fornece resultados de simulação de monte-carlo que mostram que o k-means ++ é mais rápido e oferece um melhor desempenho, portanto não há garantia, mas pode ser melhor.

Quanto ao seu problema: o que o k-means ++ escolhe os centros e inicia um k-means "clássico". Portanto, o que você pode fazer é (1) usar a parte do algoritmo que escolhe os centros e, em seguida, (2) usar esses centros nas implementações de k-means da GPU. Dessa forma, pelo menos uma parte do problema é resolvida no software baseado em GPU, portanto, deve ser mais rápido.

Visualizando os centróides iniciais de K-means e K-means ++

Para adicionar uma visão intuitiva da diferença entre os centróides iniciais dos dois algoritmos, considere o seguinte conjunto de dados de brinquedos, que consiste em três quadrados gerados uniformemente

Aqui estão os histogramas 2D mostrando onde os algoritmos k-means e k-means ++ inicializam seus centróides iniciais (simulações de 2000).

Claramente, o k-médio padrão inicializa os pontos de maneira uniforme, enquanto o k-médio ++ tende a inicializar próximo ao centro dos quadrados

Muitas vezes, a inicialização aleatória do KMeans leva menos tempo que o KMeans ++, mas fornece resultados ruins. Por causa da inicialização aleatória, muitas vezes obtemos o ideal local, porque nosso conjunto inicial de centros não é distribuído pelo conjunto de dados.

Então, respondendo à sua pergunta:

1. Não, porque os centros do KMeans ++ são distribuídos pelos dados, é mais provável que tenham menos custo (dentro da soma do quadrado do cluster) do que a inicialização aleatória.
2. como é uma inicialização aleatória no KMeans, fornece resultados diferentes, dependendo do seu conjunto inicial de centros
3. Em primeiro lugar, não existe uma solução definitiva para o KMeans, pois é um aprendizado não supervisionado. O que podemos fazer é reduzir o custo do KMeans (SSE). O KMeans escolhe o centro inicial de forma inteligente; é preciso menos iteração dos llyods para convergir e fornecer melhores resultados do que Random