Я реализовал алгоритм k-средних, и производительность сильно зависит от инициализации центроидов. Я нахожу случайную равномерную инициализацию, чтобы дать хорошее значение k-средних примерно в 5% случаев, тогда как при использовании k-означает ++ оно ближе к 50%. Почему доходность хороших k-средних такая низкая? Я должен отрицать, что я использовал только несколько наборов данных, и мои хорошие / плохие показатели указывают только на них, а не в целом.
Вот пример использования k-means ++, где конечный результат был невелик. Индекс Данна этой кластеризации равен 0,16.
И пример, где он отлично работал с индексом Данна 0,67.
Возможно, я находился под наивным впечатлением, что k-means ++ каждый раз создавал хорошие k-means. Возможно, что-то не так с моим кодом?
def initialize_centroids(points, k):
"""
Parameters:
points : a list of Points.
k : how many centroids to place.
Returns:
A list of centroids.
"""
clusters = []
clusters.append(choice(points)) # first centroid is random point
for _ in range(k - 1): # for other centroids
distances = []
for p in points:
d = inf
for c in clusters: # find the minimal distance between p and c
d = min(d, distance(p, c))
distances.append(d)
# find maximum distance index from minimal distances
clusters.append(points[distances.index(max(distances))])
return clusters
Это адаптировано из алгоритма, найденного в Википедии:
Выберите один центр случайным образом из числа точек данных.
Для каждой точки данных x вычислите D (x), расстояние между x и ближайшим центром, который уже был выбран.
Выберите одну новую точку данных случайным образом в качестве нового центра, используя взвешенное распределение вероятностей, где точка x выбрана с вероятностью, пропорциональной D (x) 2.
Повторяйте шаги 2 и 3, пока не будут выбраны k центров.
Теперь, когда начальные центры были выбраны, используйте стандартную кластеризацию k-средних.
Разница в том, что центроиды выбираются так, что это самое дальнее расстояние, а не вероятность выбора между самыми дальними расстояниями.
Мое намерение состоит в том, чтобы сравнить индекс Данна с различными значениями k, и эмпирически более высокий индекс Данна означает лучшую кластеризацию. Я не могу собрать (хорошие) данные, если половину времени они не работают, поэтому мои результаты искажены из-за ошибки k-means ++ или моей реализации.
Какие другие стратегии инициализации могут быть заняты, чтобы получить более последовательный результат?