Возможный дубликат:
Изменение алгоритма K-варианта с равным размером кластера
EDIT: как casperOne указать мне, что этот вопрос является дубликатом. В любом случае здесь представлен более обобщенный вопрос, который охватывает этот: https://stats.stackexchange.com/info/8744/clustering-procedure-where-each-cluster-has-an-equal-number-of-points
Мои требования
В проекте мне нужно сгруппировать n точек (x, y) в k кластерах равного размера (n/k). Если x и y являются двойными плавающими числами, n может варьироваться от 100 до 10000, а k может варьироваться от 2 до 100. Кроме того, k известен до запуска алгоритма.
Мои эксперименты
Я начал решать проблему, используя алгоритм http://en.wikipedia.org/wiki/K-means_clustering, который работает отлично и быстро, чтобы создать ровно k кластеров примерно того же размера.
Но моя проблема заключается в том, что K-означает создание кластеров примерно того же размера, где мне нужны кластеры точно такого же размера (или, если быть более точным: мне нужно, чтобы они имели размер между полом (n/k) и ceil (n/k)).
Прежде чем указать мне на это, да, я попробовал первый ответ здесь. Вариант K-варианта алгоритма с равным размером кластера, который звучит как хорошая идея.
Основная идея состоит в том, чтобы опубликовать процесс создания кластера с помощью K-средств. От самого большого кластера до самого маленького. Мы уменьшаем размер кластеров, которые имеют более n/k членов, перемещая дополнительные точки в другой ближайший кластер. Оставляя в одиночку кластеры, которые уже сокращены.
Вот реализованный псевдо-код:
n is the number of point
k is the number of cluster
m = n / k (the ideal cluster size)
c is the array of cluster after K-means
c' = c sorted by size in descending order
for each cluster i in c' where i = 1 to k - 1
n = size of cluster i - m (the number of point to move)
loop n times
find a point p in cluster i with minimal distance to a cluster j in c' where j > i
move point p from cluster i to cluster j
end loop
recalculate centroids
end for each
Проблема с этим алгоритмом заключается в том, что ближе к концу процесса (когда я приближаюсь к k) мы должны выбрать кластер j в c '(где j> i, потому что нам нужно оставить только уже обработанные кластеры), но этот кластер j, который мы нашли, может быть далеко от кластера i, тем самым нарушая концепцию кластера.
Мой вопрос
Есть ли альтернативный алгоритм K-средних или вариант K-варианта, который может соответствовать моим требованиям, или я ошибаюсь с самого начала, и мне нужно найти другой алгоритм кластеризации?
PS: Я не против реализации самого решения, но было бы здорово, если бы я мог использовать библиотеку и в идеале в JAVA.
