Я реализовал алгоритм kmeans ++ для инициализации кластеров при выполнении кластеризации K-средних. Цикл должен запускаться k раза. Мне было интересно, есть ли способ векторизовать алгоритм, чтобы он работал быстрее?
points - массив точек в d-измерениях, а k - количество возвращаемых центроидов.
Он работает, вычисляя минимальные расстояния от уже найденных кластеров, до всех точек, а затем вычисляя вероятность выбора следующего кластера из точек.
Проблема действительно в том, что он плохо масштабируется, когда k большой.
def init_plus_plus(points, k):
centroids = np.zeros_like(points[:k])
r = np.random.randint(0, points.shape[0])
centroids[0] = points[r]
for i in range(1, k):
min_distances = self.euclidian_distance(centroids[:i], points).min(1)
prob = min_distances / min_distances.sum()
cs = np.cumsum(prob)
idx = np.sum(cs < np.random.rand())
centroids[i] = points[int(idx)]
return centroids