K-means: Quais são algumas boas maneiras de escolher um conjunto eficiente de centróides iniciais?

Quando uma inicialização aleatória de centróides é usada, diferentes execuções de médias K produzem diferentes SSEs totais. E é crucial no desempenho do algoritmo. Quais são algumas abordagens eficazes para resolver esse problema? Abordagens recentes são apreciadas.

Uma abordagem que produz resultados mais consistentes é o K-means ++ . Essa abordagem reconhece que provavelmente existe uma escolha melhor dos locais iniciais do centróide do que a simples atribuição aleatória. Especificamente, os meios K tendem a ter um desempenho melhor quando os centróides são semeados de uma maneira que não os agrupe no espaço.

Em suma, o método é o seguinte:

1. Escolha um dos seus pontos de dados aleatoriamente como um centróide inicial.
2. Calcule , a distância entre o centróide inicial e todos os outros pontos de dados, x .$D(x)$$x$
3. Escolha o seu próximo centróide dos pontos de dados restantes com probabilidade proporcional a $D(x)^2$
4. Repita até que todos os centróides tenham sido atribuídos.

Nota: deve ser atualizado à medida que mais centróides são adicionados. Deve ser definido como a distância entre um ponto de dados e o centróide mais próximo.$D(x)$

Você também pode estar interessado em ler este documento que propõe o método e descreve seu desempenho geral esperado.

Posso estar entendendo mal a sua pergunta, mas geralmente o k-means escolhe seus centróides aleatoriamente para você, dependendo do número de clusters que você definir (ou seja, k). Escolher o número para k tende a ser um exercício subjetivo. Um bom lugar para começar é um gráfico de cotovelo / seixos, que pode ser encontrado aqui:

http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set#The_Elbow_Method

A abordagem usual para esse problema é executar novamente o algoritmo K-means várias vezes, com diferentes inicializações aleatórias dos centróides, e manter a melhor solução. Você pode fazer isso avaliando os resultados em seus dados de treinamento ou por meio de validação cruzada.

Existem muitas outras maneiras de inicializar os centróides, mas nenhuma delas terá o melhor desempenho para todos os problemas. Você pode avaliar essas abordagens juntamente com a inicialização aleatória para o seu problema específico.

Eu concordo com a trama Elbow / Scree. Achei mais intuitivamente sensível do que uma semente aleatória. Aqui está um código de exemplo para experimentá-lo.

Ks=30
mean_acc=np.zeros((Ks-1))
std_acc=np.zeros((Ks-1))
ConfustionMx=[];
for n in range(1,Ks):    
    #Train Model and Predict  
    kNN_model = KNeighborsClassifier(n_neighbors=n).fit(X_train,y_train)
    yhat = kNN_model.predict(X_test)
    mean_acc[n-1]=np.mean(yhat==y_test);
    std_acc[n-1]=np.std(yhat==y_test)/np.sqrt(yhat.shape[0])

plt.plot(range(1,Ks),mean_acc,'g')
plt.fill_between(range(1,Ks),mean_acc - 1 * std_acc,mean_acc + 1 * std_acc, alpha=0.10)
plt.legend(('Accuracy ', '+/- 3xstd'))
plt.ylabel('Accuracy ')
plt.xlabel('Number of Nabors (K)')
plt.tight_layout()
plt.show()

print( "The best accuracy was with", mean_acc.max(), "with k=", mean_acc.argmax()+1)