Процедура кластеризации, где каждый кластер имеет равное количество точек?

25

У меня есть несколько точек в R p , и я хочу сгруппировать точки так, чтобы:Иксзнак равно{Икс1,,,,,ИксN}рп

  1. Каждый кластер содержит равное количество элементов . (Предположим, что число кластеров делит n .)ИксN

  2. Каждый кластер в некотором смысле является «пространственно связным», как кластеры из средних.К

Легко придумать множество процедур кластеризации, которые удовлетворяют одной или другой из них, но кто-нибудь знает способ получить оба сразу?

Не Дурретт
источник
2
Размер кластера также указан? Тогда, как уже говорилось, проблема кажется мне неразрешимой. Рассмотрим следующий случай с : X = { - 1 , 0.99 , 1 , 1.01 } . Если вы хотите 2 кластера, вы получите либо разные размеры, либо не «пространственно связные». Или вы хотите что-то вроде «как можно более пространственно связное» - минимизировать максимальное внутрикластерное расстояние или около того? Другое решение было бы разрешить любой делитель n в качестве размера кластера - но тогда всегда есть тривиальное решение из n кластеров размером 1Nзнак равно4,пзнак равно1Иксзнак равно{-1,0,99,1,1,01}NN1,
Эрик П.
1
Хорошая точка зрения. В идеале я хотел бы, чтобы что-то было «как можно более пространственно сплоченным» при соблюдении ограничения равной мощности. Но мне было бы интересно услышать о любых процедурах, которые делают здесь другие компромиссы, так как, возможно, они могут быть адаптированы.
Не Дурретт
Будет ли достаточно разделения данных по квантилям? Если значения не являются монотонными по отношению друг к другу, я не вижу, как еще они могут быть «пространственно связными».
Целениус
4
Недавно было проведено несколько исследований по кластеризации с ограничениями. Google google.com/search?q=constrained+k-means .
whuber
Просто одна не проверенная идея. При кластеризации часто используется так называемая силуэтная статистика. Он показывает вам, насколько хорошо объект кластеризован и каков лучший соседний кластер, в котором он может быть зарегистрирован. Итак, вы можете начать с K-MEANS или другой классификации с другими кластерами n . Затем перемещайте объекты, которые не очень хорошо классифицированы (в соответствии со статистикой), в их лучшие соседние кластеры с меньшим n, пока не получите равное n . Я ожидаю итераций: переместить некоторые объекты, пересчитать статистику, переместить некоторые объекты и т. Д. Это будет компромиссный процесс.
ttnphns

Ответы:

6

Я предлагаю двухэтапный подход:

  1. получить хорошие начальные оценки центров кластеров, например, с использованием жестких или нечетких K-средних.

  2. Используйте глобальное присвоение ближайшего соседа, чтобы связать точки с центрами кластеров: вычислить матрицу расстояний между каждой точкой и каждым центром кластера (вы можете сделать задачу чуть меньше, рассчитав только разумные расстояния), реплицировать каждый центр кластера X раз и решить линейную задачу проблема назначения . Для каждого центра кластера вы получите ровно X совпадений с точками данных, так что в глобальном масштабе расстояние между точками данных и центрами кластеров сведено к минимуму.

Обратите внимание, что вы можете обновить центры кластеров после шага 2 и повторить шаг 2, чтобы в основном запустить K-средних с фиксированным числом точек на кластер. Тем не менее, будет хорошей идеей сначала получить правильное предположение.

Jonas
источник
4

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

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

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

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

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

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

Шаг E : вычислить обновленные центры кластеров, как в обычном k-средних

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

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

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

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

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

Хорошее место для начала может быть с реализацией k-средних в ELKI , которая, кажется, уже поддерживает три разные инициализации (включая k-means ++), и авторы сказали, что они также хотят иметь разные стратегии итерации, чтобы охватить все различные общие варианты по модульному принципу (например, Lloyd, MacQueen, ...).

Anony-Мус
источник
2
Аналогичный подход включен в ELKI как учебное пособие и в модуль «расширения» учебного пособия: elki.dbs.ifi.lmu.de/wiki/Tutorial/SameSizeKMeans
Эрих Шуберт,
3

Это проблема оптимизации. У нас есть Java-библиотека с открытым исходным кодом, которая решает эту проблему (кластеризация, где количество на кластер должно быть между заданными диапазонами). Вам нужно, чтобы ваше общее количество очков было не более нескольких тысяч, но не более 5000 или, может быть, 10000.

Библиотека находится здесь:

https://github.com/PGWelch/territorium/tree/master/territorium.core

Сама библиотека настроена на проблемы географического / ГИС-типа - поэтому вы увидите ссылки на X и Y, широты и долготы, клиентов, расстояние и время и т. Д. Вы можете просто игнорировать «географические» элементы и использовать их как чистый кластеризатор.

Вы предоставляете набор изначально пустых входных кластеров, каждый из которых имеет минимальное и максимальное целевое количество. Кластерер назначит точки вашим входным кластерам, используя эвристический алгоритм оптимизации (свопы, ходы и т. Д.). При оптимизации он, во-первых, устанавливает приоритеты для каждого кластера в пределах своего минимального и максимального количественного диапазона, а затем, во-вторых, минимизирует расстояния между всеми точками в кластере и центральной точкой кластера, поэтому кластер является пространственно связным.

Вы предоставляете решателю метрическую функцию (то есть функцию расстояния) между точками, используя этот интерфейс:

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/TravelMatrix.java

Метрика на самом деле структурирована так, чтобы возвращать как расстояние, так и «время», потому что она предназначена для географических задач, основанных на путешествиях, но для произвольных проблем кластеризации просто установите «время» равным нулю, а расстояние - как фактическую метрику, которую вы используете между точки.

Вы бы настроили свою проблему в этом классе:

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/Problem.java

Ваши баллы будут «Клиенты», а их количество будет 1. В классе клиентов убедитесь, что вы установили costPerUnitTime = 0 и costPerUnitDistance = 1, предполагая, что вы возвращаете метрическое расстояние в поле «расстояние», возвращаемое TravelMatrix.

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/Customer.java

Смотрите здесь пример запуска решателя:

https://github.com/PGWelch/territorium/blob/master/territorium.core/src/test/java/com/opendoorlogistics/territorium/TestSolver.java

Open Door Logistics
источник
2

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

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)
Александр Каин
источник
1
Спасибо за этот вклад, @ user2341646. Не могли бы вы добавить какую-нибудь экспозицию, объясняющую, что это за решение, как оно работает и почему это решение?
gung - Восстановить Монику
ХОРОШО. По сути, алгоритм начинается с случайного назначения членства, но в кластере имеется около G членов, а всего K кластеров. Мы определяем функцию ошибки, которая измеряет средние расстояния между данными в одном кластере, усредненные по всем кластерам. Систематически просматривая все пары данных, мы видим, приводит ли обмен членством этих двух данных к меньшей ошибке. Если это так, мы обновляем минимально возможную ошибку, в противном случае мы отменяем переключение членства. Мы делаем это до тех пор, пока не останется больше ходов за один проход.
Александр Каин