Я получил Список Точек X и Y, которые отображают положение в реальном мире.Я хотел бы создать кластеры примерно одинакового размера на основе этих данных.
Я попытался написать свою собственную реализацию на основе алгоритма k-средних, поскольку не мог понять или воссоздать какой-либоиз примеров, которые я нашел в Интернете.
Я создаю (отсортированный) список расстояний для каждой точки каждого кластера.Каждая точка помещается в стек, и я буду работать со стеком следующим образом:
, пока стек не пустой
Получить первую точку p из стека (stack.pop)
для всехрасстояния от p до всех кластеров
, если первый (ближайший) кластер не заполнен - поместите точку в этот кластер
иначе (ближайший кластер заполнен)
Есть ли точка pt в требуемом кластере сdst к желаемому> p.dst к желаемому
Да - удалите pt и добавьте p, затем добавьте pt в pointStack, чтобы пересчитать pt
Нет - ЧТО ДЕЛАТЬ ЗДЕСЬ?
Так что же я?В основном, я оптимизирую кластер, чтобы иметь наименьшее общее расстояние всех точек в кластере, в то время как кластер также имеет определенный максимум точек, которые он может иметь.
Код:
Stack<Point2D> pointsStack = new Stack<Point2D>();
//Find distances for every Point to every cluster
for (PT p : points) {
List<Distance> pDsts = new ArrayList<Distance>();
for (Cluster c : clusters) {
Distance d = null;
switch (dstFunction) {
case EUKLID:
d = new Distance(p, p.distanceFunc(c.x, c.y), c);
break;
case LINEAR:
d = new Distance(p, p.geoDistanceFunc(c.x, c.y), c);
break;
}
pDsts.add(d);
}
Collections.sort(pDsts);
p.dstsToClusters = pDsts;
pointsStack.push(p);
}
//For all points in the pointStack
while (!pointsStack.isEmpty()) {
Point2D p = pointsStack.pop();
//for all distances from p to all clusters
for (Distance d : p.dstsToClusters) {
boolean foundSwap = false;
if (d.cluster.size() < maxSizeCluster) {
d.cluster.addPoint(p);
break;
} else { //this cluster is full
//Is there a point pt in the desired cluster with dst to desired > p.dst to desired
//Yes - remove pt and add p, then add pt to the pointStack to recompute pt; No - find another cluster
for (Point2D pt : d.cluster.points) {//for ever point in the desired cluster
for (Distance dpt : pt.dstsToClusters) {//for every distance in every point in the desired cluster
//find a point in the desired cluster with dst < than p.dst to desired
if (dpt.cluster.clusterNumber() == d.cluster.clusterNumber() && d.dstToCluster < dpt.dstToCluster) {
d.cluster.addPoint(p);
d.cluster.removePoint(pt);
pointsStack.push(pt);
foundSwap = true;
break;
}
}
if (foundSwap) {
break;
}
}
}
if (foundSwap) {
break;
}
//ELSE -> All points are closer to cluster center than the one that
//wants to get into this cluster, so the point will be assigned to
//another cluster.
}
}
Мои результаты очень приятные и в большинстве случаев именно то, что я хотел, но в некоторых случаях результат будет страдать от того, что ничего не будет сделано, если точка захочет поменяться в кластере, но этот кластер ужеy заполнен и ни одна точка не находится дальше, чем текущая.Таким образом, эта точка будет помещена во второй лучший кластер или даже в третий, если то же самое (ни одна точка дальше от кластера, чем текущая) не произойдет снова.Вы можете ясно увидеть это на этом изображении здесь: 
Розовые / розовые точки вокруг синего не имеют никакого смысла, и их (что я бы сказал) «плохая» кластеризация.
Может кто-нибудь подсказать, как решить эту проблему?
Опять же ... эти формирования происходят потому, что синий кластер уже заполнен.Тогда одна из розовых / розовых точек (которые в данный момент на самом деле не имеют какого-либо цвета, но давайте просто назовем их розовыми / розовыми точками) хочет перейти в синюю группу, потому что она является ближайшей группой из всех окружающих.Однако ни одна из точек в синем кластере не имеет большего расстояния до центра кластера, чем точка розового / розового цвета, которая хочет войти в синий кластер.Таким образом, точка розового / розового цвета назначается следующему лучшему кластеру со вторым наилучшим расстоянием (в данном случае оранжевым или голубым).К сожалению, попытка вставить в эти два кластера приводит к той же проблеме.И теперь точка роза / роза будет назначена четвертому лучшему кластеру - кластеру роза / роза.Это означает, что кластеры будут расти вокруг других кластеров, которые я не хочу.
Решение, о котором я подумал, состояло бы в том, чтобы поменять местами розовые / розовые точки с некоторыми из точек синего кластера - предпочтительно сточки, которые находятся ближе всего к другому кластеру (который не должен быть заполненным [предпочтительно вторым наилучшим кластером для точки, которая меняется местами)), так что синий кластер «растет» немного ближе к левому нижнему краю, настолько, что всерозовые / розовые точки будут находиться в синей группе, а розовая / розовая группа будет немного больше и слегка переориентирована.Однако в настоящее время я не знаю, как реализовать эту логику.