K-means: Какие есть хорошие способы выбрать эффективный набор начальных центроидов?

Когда используется случайная инициализация центроидов, разные прогоны K-средних дают разные общие SSE. И это имеет решающее значение в производительности алгоритма. Каковы некоторые эффективные подходы к решению этой проблемы? Недавние подходы приветствуются.

Подход, который дает более согласованные результаты, - это K-means ++ . Этот подход признает, что, вероятно, лучший выбор исходных местоположений центроидов, чем простое случайное распределение. В частности, K-средства имеют тенденцию работать лучше, когда центроиды высеваются таким образом, что они не слипаются в пространстве.

Короче говоря, метод заключается в следующем:

1. Выберите одну из ваших точек данных случайным образом в качестве начального центроида.
2. Рассчитайте , расстояние между вашим исходным центроидом и всеми другими точками данных, .$D(x)$$x$
3. Выберите свой следующий центр тяжести из оставшихся точек данных с вероятностью, пропорциональной$D(x)^2$
4. Повторяйте, пока все центроиды не будут назначены.

Примечание: следует обновить по мере добавления новых центроидов. Должно быть установлено расстояние между точкой данных и ближайшим центроидом.$D(x)$

Вам также может быть интересно прочитать этот документ, в котором предлагается метод и описываются его общие ожидаемые результаты.

Возможно, я неправильно понимаю ваш вопрос, но обычно k-means выбирает ваши центроиды случайным образом для вас в зависимости от количества кластеров, которые вы установили (т.е. k). Выбор числа для k имеет тенденцию быть субъективным упражнением. Хорошее место для начала - сюжет Elbow / Scree, который можно найти здесь:

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

Обычный подход к этой проблеме состоит в том, чтобы повторно запустить алгоритм K-средних несколько раз с различными случайными инициализациями центроидов и сохранить лучшее решение. Вы можете сделать это, оценивая результаты по вашим данным обучения или путем перекрестной проверки.

Есть много других способов инициализации центроидов, но ни один из них не будет наилучшим для каждой проблемы. Вы можете оценить эти подходы вместе со случайной инициализацией для вашей конкретной проблемы.

Я согласен с сюжетом Elbow / Scree. Я нашел это более интуитивно понятным, чем случайное семя. Вот пример кода, чтобы попробовать это.

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)