Изменение алгоритма K-средних с одинаковым размером кластера

Question

Я ищу самый быстрый алгоритм для группировки точек на карте в группы одинакового размера по расстоянию. алгоритм кластеризации k-средних выглядит простым и многообещающим, но не дает групп одинакового размера.

Существует ли разновидность этого алгоритма или другой, который допускает равное количество членовдля всех кластеров?

См. также: Группировать n точек в k кластерах одинакового размера

Answer 1

Это может помочь: примените алгоритм Ллойда , чтобы получить k центроидов.Сортируйте центроиды по убыванию размера их связанных кластеров в массиве.Для i = от 1 до k -1, нажмите точки данных в кластере i с минимальным расстоянием до любого другого центроида j ( i <<em> j ≤ k ) до j и пересчитать центроид i (но не пересчитыватькластера) до размера кластера n / k .

Сложность этого шага постобработки составляет O ( k ² n lg n ).

Answer 2

Фреймворк для анализа данных ELKI содержит учебник по k-средних равных размеров .

Это не конкретный хороший алгоритм, но это достаточно простая вариация k-средних, чтобы написать учебник и научить людей, как реализовывать свои собственные вариации алгоритма кластеризации;и, очевидно, некоторые люди действительно нуждаются в том, чтобы их кластеры имели одинаковый размер, хотя качество SSQ будет хуже, чем при использовании обычных k-средних.

В ELKI 0.7.5 вы можете выбрать этот алгоритм как tutorial.clustering.SameSizeKMeansAlgorithm.

Answer 3

Вы можете просматривать расстояния как определяющие взвешенный график.Многие алгоритмы разбиения графа явно основаны на попытке разбить вершины графа на два набора одинакового размера.Это проявляется, например, в алгоритме Кернигана-Лин и в разбиении спектрального графа с использованием лапласиана.Чтобы получить несколько кластеров, вы можете рекурсивно применить алгоритм разделения;об этом можно поговорить по ссылке на разделение спектральных графов.

Answer 4

Попробуйте эту вариацию k-средних:

Инициализация :

• выберите случайным образом k центров из набора данных или даже лучше, используя стратегию kmeans ++
• для каждой точки, вычислите расстояние до ее ближайшего центра кластера и постройте кучу для этой
• точек рисования из кучи и назначьте их ближайшему кластеру, если кластер ужепереполненный.Если это так, вычислите следующий ближайший центр кластера и заново вставьте в кучу

В конце вы должны иметь разделение, удовлетворяющее вашим требованиям + -1 к одинаковому количеству объектов на кластер (убедитесь, чтопоследние несколько кластеров также имеют правильный номер. Первые m кластеры должны иметь ceil объектов, остальные ровно floor объектов.)

Шаг итерации :

Реквизиты: список для каждого кластера с «предложениями обмена» (объекты, которые предпочли бы быть в другом кластере).

E шаг: вычислить обновленные центры кластеров, как вобычный k-means

M шаг: перебор всех точек (либо только одна, либо все в одном пакете)

Вычисление ближайшего центра кластера к объекту / всем центрам кластеракоторые ближе, чем текущие кластеры.Если это другой кластер:

• Если другой кластер меньше текущего кластера, просто переместите его в новый кластер
• Если есть предложение подкачки из другого кластера(или любой кластер с меньшим расстоянием), поменяйте местами два назначения кластера (если существует более одного предложения, выберите одно с наибольшим улучшением)
• в противном случае укажите предложение свопа для другого кластера

Размеры кластеров остаются неизменными (+ - разница потолок / этаж), объекты перемещаются только из одного кластера в другой до тех пор, пока это приводит к улучшению оценки.Поэтому он должен сходиться в некоторой точке, например, k-средних.Это может быть немного медленнее (то есть больше итераций).

Я не знаю, было ли это опубликовано или реализовано ранее.Это именно то, что я бы попробовал (если бы я попытался использовать k-means. Есть гораздо лучшие алгоритмы кластеризации.)

Answer 5

Прочитав этот вопрос и несколько похожих, я создал реализацию Python для k-средних того же размера, используя учебник Elki для https://elki -project.github.io / tutorial / same-size_k_means который использует реализацию K-Means от scikit-learn для большинства распространенных методов и знакомого API.

Моя реализация находится здесь: https://github.com/ndanielsen/Same-Size-K-Means

Логика кластеризации находится в этой функции: _labels_inertia_precompute_dense()

Answer 6

Как правило, группирование точек на карте в группы одинакового размера по расстоянию - невыполнимая задача в теории. Поскольку группировка точек в группы одинакового размера конфликтует с группировкой точек в кластерах по расстоянию.

см. Этот участок:

Есть четыре пункта:

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). Таким образом, требования кластера и групп одинакового размера не могут быть выполнены одновременно.

Answer 7

Происходит более чистая постобработка, учитывая кластерные центроиды.Пусть 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

Answer 8

Рассмотрим некоторую форму рекурсивного жадного слияния - каждая точка начинается как одноэлементный кластер и многократно объединяет два ближайших, так что такое слияние не превышает макс.размер.Если у вас не осталось выбора, кроме как превысить максимальный размер, то локально скопируйте.Это форма обратной иерархической кластеризации: http://en.wikipedia.org/wiki/Hierarchical_clustering

Answer 9

Недавно я сам нуждался в этом для небольшого набора данных. Мой ответ, хотя и имеет относительно длительное время работы, гарантированно сходится к локальному оптимуму.

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)

Answer 10

Добавлено январь 2012: Лучше, чем постобработка, было бы сохранить размеры кластеров примерно так же, как они растут.
Например, найдите для каждого X 3 ближайших центра, затем добавьте X к одному с лучшим расстояние - & лямбда; 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