Я ищу самый быстрый алгоритм для группировки точек на карте в группы с одинаковым размером по расстоянию. k-означает алгоритм кластеризации выглядит просто и многообещающе, но не дает групп одинакового размера.
Есть ли вариант этого алгоритма или другой, который допускает равное количество членов для всех кластеров?
Смотрите также: Группируйте n точек в k кластерах равного размера
Это может сделать трюк: примените алгоритм Ллойда, чтобы получить k centroids. Сортируйте центроиды, уменьшая размер связанных кластеров в массиве. Для я = 1 - k-1, толкайте точки данных в кластере я с минимальным расстоянием до любого другого центроида j (i < j ≤ k) до j и пересчитывайте центроид я (но не перекомпонуйте кластер) до тех пор, пока размер кластера равен n/k.
Сложность этого этапа постобработки - O (k² n lg n).
Вы можете просмотреть расстояния как определение взвешенного графика. Довольно много алгоритмов разбиения графов явно основаны на попытке разбиения вершин графа на два набора равных размеров. Это появляется, например, в алгоритме Kernighan-Lin и в спектральном графике разделение с использованием лапласиана. Чтобы получить несколько кластеров, вы можете рекурсивно применять алгоритм разбиения; там хорошо обсуждается это по ссылке на разбиение спектрального графа.
В ELKI структура интеллектуального анализа данных содержит учебник по равный размер k-означает.
Это не очень хороший алгоритм, но это достаточно простой вариант k-вариантов для написания учебника и обучения людей тому, как реализовать их собственный алгоритм алгоритма кластеризации; и, по-видимому, некоторым людям действительно нужны их кластеры одинакового размера, хотя качество SSQ будет хуже, чем с обычными k-средствами.
Попробуйте эту вариацию k-вариантов:
Инициализация
k центры из набора данных в произвольном порядке или еще лучше с помощью стратегии kmeans ++.В конце концов, вы должны иметь парификацию, которая удовлетворяет вашим требованиям к +1 к одному количеству объектов на кластер (убедитесь, что последние несколько кластеров также имеют правильное число. Первые кластеры m должны иметь ceil объекты, остальное точно floor объектов.)
Шаг итерации:
Реквизиты: список для каждого кластера с "предложениями свопинга" (объекты, которые предпочитают находиться в другом кластере).
E: вычислите обновленные центры кластеров, как в обычных k-средних
M: Итерация через все точки (либо одна, либо все в одной партии)
Вычислить ближайший центр кластера для объекта/всех кластерных центров, которые ближе, чем текущие кластеры. Если это другой кластер:
Размеры кластера остаются неизменными (+ - разница между потолком/полом), объекты перемещаются только от одного кластера к другому, пока это приводит к улучшению оценки. Поэтому он должен сходиться в некоторой точке, например, к-значению. Это может быть немного медленнее (т.е. Больше итераций).
Я не знаю, было ли это ранее опубликовано или реализовано. Это просто то, что я хотел бы попробовать (если бы я попытался использовать k-средство, там есть намного лучшие алгоритмы кластеризации.)
Рассмотрим некоторую форму рекурсивного жадного слияния - каждая точка начинается как одноэлементный кластер и многократно объединяет ближайшие две такие, что такое слияние не превосходит max. размер. Если у вас нет выбора, но чтобы превысить максимальный размер, тогда локально откройте. Это форма иерархической кластеризации обратного отслеживания: http://en.wikipedia.org/wiki/Hierarchical_clustering
Добавлено янв. 2012:
Лучше, чем постобработка, это сохранить размеры кластеров
примерно так же, как они растут.
Например, найдите для каждого X 3 ближайших центра,
затем добавьте X к одному с лучшим
расстояние - & lambda; clustersize.
Простой жадный постпроцесс после k-средств может быть достаточно хорош, если ваши кластеры из k-сред примерно равны.
(Это аппроксимирует алгоритм присваивания на матрице расстояний Npt x C от k-средних.)
Можно было итерации
diffsizecentres = kmeans( X, centres, ... )
X_centre_distances = scipy.spatial.distance.cdist( X, diffsizecentres )
# or just the nearest few centres
xtoc = samesizeclusters( X_centre_distances )
samesizecentres = [X[xtoc[c]].mean(axis=0) for c in range(k)]
...
Я был бы удивлен, если бы итерации сильно изменили центры, но это будет зависеть от & trade;.
О том, насколько велики ваши Npoint Ncluster и Ndim?
#!/usr/bin/env python
from __future__ import division
from operator import itemgetter
import numpy as np
__date__ = "2011-03-28 Mar denis"
def samesizecluster( D ):
""" in: point-to-cluster-centre distances D, Npt x C
e.g. from scipy.spatial.distance.cdist
out: xtoc, X -> C, equal-size clusters
method: sort all D, greedy
"""
# could take only the nearest few x-to-C distances
# add constraints to real assignment algorithm ?
Npt, C = D.shape
clustersize = (Npt + C - 1) // C
xcd = list( np.ndenumerate(D) ) # ((0,0), d00), ((0,1), d01) ...
xcd.sort( key=itemgetter(1) )
xtoc = np.ones( Npt, int ) * -1
nincluster = np.zeros( C, int )
nall = 0
for (x,c), d in xcd:
if xtoc[x] < 0 and nincluster[c] < clustersize:
xtoc[x] = c
nincluster[c] += 1
nall += 1
if nall >= Npt: break
return xtoc
#...............................................................................
if __name__ == "__main__":
import random
import sys
from scipy.spatial import distance
# http://docs.scipy.org/doc/scipy/reference/spatial.distance.html
Npt = 100
C = 3
dim = 3
seed = 1
exec( "\n".join( sys.argv[1:] )) # run this.py N= ...
np.set_printoptions( 2, threshold=200, edgeitems=5, suppress=True ) # .2f
random.seed(seed)
np.random.seed(seed)
X = np.random.uniform( size=(Npt,dim) )
centres = random.sample( X, C )
D = distance.cdist( X, centres )
xtoc = samesizecluster( D )
print "samesizecluster sizes:", np.bincount(xtoc)
# Npt=100 C=3 -> 32 34 34
Недавно мне это было нужно для не очень большого набора данных. Мой ответ, хотя и имеет относительно продолжительное время работы, гарантированно сходится к локальному оптимуму.
def eqsc(X, K=None, G=None):
"equal-size clustering based on data exchanges between pairs of clusters"
from scipy.spatial.distance import pdist, squareform
from matplotlib import pyplot as plt
from matplotlib import animation as ani
from matplotlib.patches import Polygon
from matplotlib.collections import PatchCollection
def error(K, m, D):
"""return average distances between data in one cluster, averaged over all clusters"""
E = 0
for k in range(K):
i = numpy.where(m == k)[0] # indeces of datapoints belonging to class k
E += numpy.mean(D[numpy.meshgrid(i,i)])
return E / K
numpy.random.seed(0) # repeatability
N, n = X.shape
if G is None and K is not None:
G = N // K # group size
elif K is None and G is not None:
K = N // G # number of clusters
else:
raise Exception('must specify either K or G')
D = squareform(pdist(X)) # distance matrix
m = numpy.random.permutation(N) % K # initial membership
E = error(K, m, D)
# visualization
#FFMpegWriter = ani.writers['ffmpeg']
#writer = FFMpegWriter(fps=15)
#fig = plt.figure()
#with writer.saving(fig, "ec.mp4", 100):
t = 1
while True:
E_p = E
for a in range(N): # systematically
for b in range(a):
m[a], m[b] = m[b], m[a] # exchange membership
E_t = error(K, m, D)
if E_t < E:
E = E_t
print("{}: {}<->{} E={}".format(t, a, b, E))
#plt.clf()
#for i in range(N):
#plt.text(X[i,0], X[i,1], m[i])
#writer.grab_frame()
else:
m[a], m[b] = m[b], m[a] # put them back
if E_p == E:
break
t += 1
fig, ax = plt.subplots()
patches = []
for k in range(K):
i = numpy.where(m == k)[0] # indeces of datapoints belonging to class k
x = X[i]
patches.append(Polygon(x[:,:2], True)) # how to draw this clock-wise?
u = numpy.mean(x, 0)
plt.text(u[0], u[1], k)
p = PatchCollection(patches, alpha=0.5)
ax.add_collection(p)
plt.show()
if __name__ == "__main__":
N, n = 100, 2
X = numpy.random.rand(N, n)
eqsc(X, G=3)
Существует более чистая пост-обработка, учитывая кластерные центроиды. Пусть N - количество элементов, K количество кластеров и S = ceil(N/K) максимальный размер кластера.
(item_id, cluster_id, distance)(item_id, cluster_id, distance) в отсортированном списке кортежей:
cluster_id превышает S ничего не делатьitem_id в кластер cluster_id.Это выполняется в O (NK lg (N)), должно давать сопоставимые результаты решению @larsmans и проще реализовать. В псевдо-питоне
dists = []
clusts = [None] * N
counts = [0] * K
for i, v in enumerate(items):
dist = map( lambda x: dist(x, v), centroids )
dd = map( lambda (k, v): (i, k, v), enumerate(dist) )
dists.extend(dd)
dists = sorted(dists, key = lambda (x,y,z): z)
for (item_id, cluster_id, d) in dists:
if counts[cluster_id] >= S:
continue
if clusts[item_id] == None:
clusts[item_id] = cluster_id
counts[cluster_id] = counts[cluster_id] + 1
После прочтения этого вопроса и нескольких подобных я создал реализацию python одномерных k-средств, используя учебник Elki на https://elki-project.github.io/tutorial/same-size_k_means, который использует реализацию K-Meys scikit-learn для большинства распространенных методов и знакомого API.
Моя реализация находится здесь: https://github.com/ndanielsen/Same-Size-K-Means
В этой функции найдена логика кластеризации: _labels_inertia_precompute_dense()
Могу ли я смиренно предложить вам попробовать этот проект ekmeans.
Java K-означает реализацию кластеризации с необязательным специальным равным параметром, который применяет ограничение равных мощностей для кластеров, оставаясь как можно более пространственным связыванием.
Это еще экспериментально, поэтому просто знайте известные ошибки.
Также посмотрите на дерево K-d, которое разделяет данные, пока члены каждого раздела не будут меньше BUCKET_SIZE, который является входом в алгоритм.
Это не приводит к тому, что ведра/разделы будут иметь одинаковый размер, но они будут меньше, чем BUCKET_SIZE.
Я тоже пытаюсь решить этот вопрос. Тем не менее, я понимаю, что я использовал неверное ключевое слово все это время. Если вы хотите, чтобы число членов результирующего точечного объекта было того же размера, вы делаете группировку, а не кластеризацию. Я, наконец, смог решить проблему, используя простой python script и postgis-запрос.
Например, у меня есть таблица с названием tb_points, которая имеет 4000 координатных точек, и вы хотите разделить ее на 10 одинаковых групп размеров, каждая из которых будет содержать по 400 координатных точек. Вот пример структуры таблицы
CREATE TABLE tb_points (
id SERIAL PRIMARY KEY,
outlet_id INTEGER,
longitude FLOAT,
latitide FLOAT,
group_id INTEGER
);
Тогда вам нужно сделать следующее:
Это реализация в python:
import psycopg2
dbhost = ''
dbuser = ''
dbpass = ''
dbname = ''
dbport = 5432
conn = psycopg2.connect(host = dbhost,
user = dbuser,
password = dbpass,
database = dbname,
port = dbport)
def fetch(sql):
cursor = conn.cursor()
rs = None
try:
cursor.execute(sql)
rs = cursor.fetchall()
except psycopg2.Error as e:
print(e.pgerror)
rs = 'error'
cursor.close()
return rs
def execScalar(sql):
cursor = conn.cursor()
try:
cursor.execute(sql)
conn.commit()
rowsaffected = cursor.rowcount
except psycopg2.Error as e:
print(e.pgerror)
rowsaffected = -1
conn.rollback()
cursor.close()
return rowsaffected
def select_first_cluster_id():
sql = """ SELECT a.outlet_id as ori_id, a.longitude as ori_lon,
a.latitude as ori_lat, b.outlet_id as dest_id, b.longitude as
dest_lon, b.latitude as dest_lat,
ST_Distance(CAST(ST_SetSRID(ST_Point(a.longitude,a.latitude),4326)
AS geography),
CAST(ST_SetSRID(ST_Point(b.longitude,b.latitude),4326) AS geography))
AS air_distance FROM tb_points a CROSS JOIN tb_points b WHERE
a.outlet_id != b.outlet_id and a.group_id is NULL and b.group_id is
null order by air_distance desc limit 1 """
return sql
def update_group_id(group_id, ori_id, limit_constraint):
sql = """ UPDATE tb_points
set group_id = %s
where outlet_id in
(select b.outlet_id
from tb_points a,
tb_points b
where a.outlet_id = '%s'
and a.group_id is null
and b.group_id is null
order by ST_Distance(CAST(ST_SetSRID(ST_Point(a.longitude,a.latitude),4326) AS geography),
CAST(ST_SetSRID(ST_Point(b.longitude,b.latitude),4326) AS geography)) asc
limit %s)
""" % (group_id, ori_id, limit_constraint)
return sql
def clustering():
data_constraint = [100]
n = 1
while n <= 10:
sql = select_first_cluster_id()
res = fetch(sql)
ori_id = res[0][0]
sql = update_group_id(n, ori_id, data_constraint[0])
print(sql)
execScalar(sql)
n += 1
clustering()
Надеюсь, что это поможет
Вы хотите взглянуть на кривую заполнения пространства, например, на z-кривую или на гильбертовую кривую. Я думаю о кривой заполнения пространства, чтобы уменьшить двумерную задачу до 1-мерной задачи. Хотя индекс sfc является только переупорядочением 2-мерных данных, а не идеальной кластеризацией данных, он может быть полезен, когда решение не должно удовлетворять идеальному кластеру и должно быть достаточно быстро вычислено.
В общем, точки группировки на карте в группы с одинаковым размером, по расстоянию - теоретически невозможная миссия. Поскольку группировка точек в группы с одинаковым размером конфликтует с точками группировки в кластерах по расстоянию.
см. этот сюжет: введите здесь описание изображения
Есть четыре точки:
A.[1,1]
B.[1,2]
C.[2,2]
D.[5,5]
Если мы сгруппируем эти точки в два кластера. Очевидно, что (A, B, C) будет кластером 1, D будет кластером 2. Но если нам нужны группы с одинаковым размером, (A, B) будет одним кластером, (C, D) будет другим. Это нарушает правила кластера, потому что C ближе к центру (A, B), но принадлежит кластеру (C, D). Поэтому требование кластеров и групп одинакового размера не может быть выполнено одновременно.