Оцените минимальное расстояние между двумя кластерами.

Я разрабатываю агломеративный алгоритм восходящей кластеризации для миллионов 50-1000 размерных точек. В двух частях моего алгоритма мне нужно сравнить два кластера точек и определить разделение между двумя кластерами. Точное расстояние - это минимальное евклидово расстояние, взятое по всем парам точек P1-P2, где P1 берется из кластера C1, а P2 берется из кластера C2. Если у C1 есть X точек, а у C2 есть точки Y, то для этого требуются измерения расстояния X * Y.

В настоящее время я оцениваю это расстояние способом, требующим измерений X + Y:

  1. Найдите центр тяжести Ctr1 кластера C1.
  2. Найдите точку P2 в кластере C2, ближайшую к Ctr1. (Y сравнений.)
  3. Найдите точку P1 в C1, ближайшую к P2. (X сравнений.)
  4. Расстояние от P1 до P2 является приблизительной мерой расстояния между кластерами C1 и C2. Это верхняя граница истинного значения.

Если кластеры имеют примерно сферическую форму, это работает очень хорошо. Мои тестовые данные состоят из эллипсоидальных гауссовых кластеров, поэтому они работают очень хорошо. Однако, если кластеры имеют странные, изогнутые, изогнутые формы, это может привести к плохим результатам. Мои вопросы:

Есть ли алгоритм, который использует даже меньше измерений расстояний, чем X + Y, и в среднем дает хорошую точность?

OR

Есть ли алгоритм, который (как мой) использует измерения расстояния X + Y, но обеспечивает лучшую точность, чем мой?

(Я программирую это на C #, но описание алгоритма в псевдокоде или на любом другом языке подойдет. Избегайте ссылок на специализированные библиотечные функции из R или Matlab. Алгоритм с вероятностными гарантиями типа «95% вероятность того, что расстояние находится в пределах 5% от минимального значения "приемлемо.)

ПРИМЕЧАНИЕ. Я только что нашел этот связанный вопрос, в котором обсуждается аналогичная проблема, но не обязательно для больших размеров. Учитывая два (большие) наборы точек, как я могу эффективно найти пары, которые находятся ближе всего друг к другу?

ПРИМЕЧАНИЕ. Я только что обнаружил, что это называется проблемой бихроматической ближайшей пары.

Для контекста, вот обзор общего алгоритма кластеризации:

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

  2. На втором проходе выполняется агломерация одинарных связей путем объединения кластеров, если их минимальное расстояние меньше, чем максимальное расстояние связи. Это не иерархическая кластеризация; он основан на разделах. Все кластеры, минимальное расстояние которых друг от друга меньше, чем это максимальное расстояние связи, будут объединены. Этот шаг не имеет заранее определенного количества кластеров в качестве цели.

  3. На третьем проходе выполняется дополнительная агломерация с одной связью, сортируя все расстояния между кластерами и объединяя только кластеры до тех пор, пока количество кластеров не станет равным заранее определенному целевому количеству кластеров. Он обрабатывает некоторые выбросы, предпочитая объединять выбросы только с большими кластерами. Если имеется много выбросов (а их обычно бывает), это может не привести к уменьшению количества кластеров до целевого.

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


cluster-analysis distance algorithm approximation
person Paul Chernoch    schedule 06.01.2016    source источник
comment
вы пробовали что-то вроде этого?   -  person Borbag    schedule 06.01.2016
comment
Нет! Это помогает узнать название проблемы! Спасибо! Прочитаю статью.   -  person Paul Chernoch    schedule 06.01.2016
comment
Интересные алгоритмы в статье. Однако зависимость рекурсивного алгоритма «разделяй и властвуй» от D (количества измерений) является проблемой, потому что для меня D часто больше, чем K (количество кластеров). Буду изучать дальше.   -  person Paul Chernoch    schedule 06.01.2016
comment
Не могли бы вы попытаться уменьшить размерность, или все измерения примерно одинаково важны?   -  person kfx    schedule 06.01.2016
comment
@kfx - В моих реальных данных я обнаружил избыточные измерения и уменьшил их с 40 000 до 950 измерений. При последующей обработке я взвешиваю почтовые индексы по совокупности, но при кластеризации все измерения, которые не являются избыточными, считаются одинаково важными.   -  person Paul Chernoch    schedule 06.01.2016
comment
Нужно ли вам использовать измерение как есть, или вы можете выполнить анализ основных компонентов, оставив только значимые?   -  person Borbag    schedule 07.01.2016
comment
Я никогда не проводил PCA. Выглядит интересно, но математика пугает. Я действительно выполняю более простые сокращения своих данных, такие как удаление избыточных измерений или тех, которые имеют попарные сопоставления 1-1.   -  person Paul Chernoch    schedule 07.01.2016

Ответы (2)


arrow_upward
0
arrow_downward

Вы можете использовать индекс. Это очень классическое решение.

Пространственный индекс может помочь вам найти ближайшего соседа к любой точке примерно за O (log n) времени. Итак, если в ваших кластерах есть n и m объектов, выберите меньший кластер и проиндексируйте больший кластер, чтобы найти ближайшую пару в O (n log m) или O (m log n).

Более простой эвристический подход - повторить вашу идею несколько раз, сократив набор кандидатов. Итак, вы найдете хорошую пару объектов a, b из двух кластеров. Затем вы отбрасываете все объекты из каждого кластера, которые должны (по неравенству треугольника) быть дальше друг от друга (используя верхнюю границу!). Затем вы повторяете это, но не снова выбираете те же a, b. Как только ваши наборы кандидатов перестанут улучшаться, проведите попарные сравнения только с оставшимися объектами. В худшем случае этого подхода должно оставаться O (n * m).

person Has QUIT--Anony-Mousse    schedule 06.01.2016
comment
Мой первый проход с использованием кривой Гильберта аналогичен использованию пространственного индекса. Так я делаю первый разрез при кластеризации. Однако, если истинное решение имеет K кластеров, я, как правило, получаю от 5K до 10K кластеров после этого шага, то есть последующих проходов. Было бы плохой идеей использовать правильный пространственный индекс (например, R-дерево) для более чем 20 измерений. Меня интересуют пространственные индексы, разработанные для большого числа измерений, но на данный момент у меня нет навыков. - person Paul Chernoch; 06.01.2016
comment
При 20+ измерениях distance больше не является надежным. Вот почему индексы терпят неудачу. Смотрите проклятие размерности; все дело в том, что расстояния слишком похожи. Кривая Гильберта также часто ломается примерно в 5 измерениях. Потому что, чтобы разделить каждое измерение только один раз и иметь непустые разделы, вам понадобится 2 ^ d объектов. Если вам нужна красивая кривая, вам нужно иметь как минимум 2 ^ {4d} объекта. У вас есть 2 ^ 80 предметов? - person Has QUIT--Anony-Mousse; 06.01.2016
comment
Что касается комментария Anony о проклятии размерности, действительно ли ваши данные имеют расхождения по всем этим измерениям? Что означает PCA или SVD? - person nicholas; 06.01.2016
comment
Я слишком хорошо осведомлен о проклятии! Однако я обнаружил, что подход с использованием кривой Гильберта хорошо работает для меня для 500 измерений, но, возможно, я использую его не так, как другие. (R-деревья действительно заканчиваются в основном пустыми разделами, как вы правильно заметили, но я не создаю разделы.) Я предполагаю, что мои кластеры хорошо разделены. У меня есть планы написать алгоритм разделения для пятого прохода, чтобы разделить перекрывающиеся кластеры, если они выглядят мультимодальными. - person Paul Chernoch; 06.01.2016
comment
@nicholas - Для моих реальных данных я удаляю избыточные измерения (это уменьшает мою проблему с 40 000 измерений до 950 измерений). По этим 950 измерениям у меня ДЕЙСТВИТЕЛЬНО есть значимые расхождения. (Мой домен - это время доставки от почтового индекса к почтовому индексу через UPS или FedEx.) - person Paul Chernoch; 06.01.2016
comment
@PaulChernoch R-деревья никогда не могут иметь пустые разделы. Вы, может быть, думаете о квадродеревьях? - person Has QUIT--Anony-Mousse; 06.01.2016
comment
В том, что касается времени попарной доставки как сырых данных, вероятно, и заключается ваша ошибка ... каково значение евклидова расстояния в этих строках? Вместо этого попробуйте рассматривать эти данные как матрицу расстояний, а не как векторы данных. - person Has QUIT--Anony-Mousse; 06.01.2016
comment
@ Anony-Mousse - вы правы, квадродеревья могут иметь пустые ячейки. Но вам все равно нужно иметь точки 2 ^ D, чтобы сделать многие из этих древовидных структур полезными. - person Paul Chernoch; 06.01.2016
comment
Да ... но, как отмечалось выше, это тем более применимо к кривым Гильберта. Потому что кривые Гильберта - это линеаризованное квадродерево. - person Has QUIT--Anony-Mousse; 06.01.2016
comment
@ Anony-Mousse - значение евклидова расстояния таково. Если два почтовых индекса имеют одинаковое время доставки в днях от каждого почтового индекса нашего поставщика (несколько тысяч поставщиков), то их евклидово расстояние равно нулю. Поскольку время доставки у них схожее с аналогичными местами, они разделены небольшим расстоянием. Просто возьмите квадрат разницы во времени на почтовый индекс поставщика по всем измерениям поставщика между двумя почтовыми индексами пункта назначения, и вы получите квадрат декартова (евклидова) расстояния. - person Paul Chernoch; 06.01.2016
comment
да. Но почему бы вам просто не принять фактическое время доставки как расстояние? - person Has QUIT--Anony-Mousse; 06.01.2016
comment
Давайте продолжим это обсуждение в чате. - person Paul Chernoch; 06.01.2016

arrow_upward
0
arrow_downward

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

http://www.cs.umd.edu/~samir/grant/cp.pdf

Я попытаюсь реализовать его и посмотрю, работает ли оно.

ОБНОВЛЕНИЕ. После дальнейшего изучения становится очевидным, что время выполнения пропорционально 3 ^ D, где D - количество измерений. Это неприемлемо. Попробовав несколько других подходов, я пришел к следующему.

  1. Выполните грубую кластеризацию в K кластеров, используя эффективный, но неполный метод. Этот метод правильно сгруппирует некоторые точки, но даст слишком много кластеров. Эти небольшие кластеры еще предстоит консолидировать, чтобы сформировать более крупные кластеры. Этот метод определит расстояние DMAX от верхней границы между точками, которые считаются находящимися в одном кластере.
  2. Отсортируйте точки в порядке кривой Гильберта.
  3. Выбросьте все точки, которым непосредственно предшествовал и за ним последовал сосед из того же кластера. Чаще всего это внутренние точки кластера, а не точки поверхности.
  4. Для каждой точки P1 ищите вперед, но не дальше следующей точки из того же кластера.
  5. Вычислите расстояние от точки P1 из кластера C1 до каждой посещенной точки P2 из кластера C2 и запишите расстояние, если оно меньше любого предыдущего расстояния, измеренного между точками в C1 и C2.
  6. Однако, если точка P1 уже сравнивалась с точкой в ​​C2, не делайте этого снова. Сделайте только одно сравнение между P1 и любой точкой в ​​C2.
  7. После того, как все сравнения будут сделаны, будет записано не более K (K-1) расстояний, и многие будут отброшены, потому что они больше, чем DMAX. Это приблизительные расстояния до ближайших точек.
  8. Выполните слияние кластеров, если они ближе, чем DMAX.

Трудно представить себе, как кривая Гильберта колеблется среди кластеров, поэтому моя оценка эффективности этого подхода к поиску ближайших пар была пропорциональна K ^ 2. Однако мои тесты показывают, что он ближе к K. Это может быть около K * log (K). Необходимы дальнейшие исследования.

Что касается точности:

  • Сравнение каждой точки со всеми остальными точками на 100%.
  • Использование метода центроида, описанного в моем вопросе, имеет расстояния, которые примерно на 0,1% больше.
  • Использование этого метода позволяет находить расстояния, которые в худшем случае на 10% больше, а в среднем на 5% больше. Однако истинно ближайший кластер почти всегда оказывается среди ближайшего кластера с первого по третий, так что качественно это хорошо. Окончательные результаты кластеризации с использованием этого метода превосходны. Мой последний алгоритм кластеризации кажется пропорциональным DNK или DNK * Log (K).
person Paul Chernoch    schedule 07.01.2016