Алгоритм цепочки ближайших соседей

Метод кластеризации на основе стека

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

Основная идея алгоритма заключается в поиске пар кластеров для слияния путем следования по путям в графе ближайших соседей кластеров. Каждый такой путь в конечном итоге заканчивается парой кластеров, которые являются ближайшими соседями друг друга, и алгоритм выбирает эту пару кластеров в качестве пары для слияния. Чтобы сэкономить работу, повторно используя как можно больше каждого пути, алгоритм использует структуру данных стека для отслеживания каждого пути, которому он следует. Следуя по путям таким образом, алгоритм цепочки ближайших соседей объединяет свои кластеры в другом порядке, чем методы, которые всегда находят и объединяют ближайшую пару кластеров. Однако, несмотря на это различие, он всегда генерирует одну и ту же иерархию кластеров.

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

Фон

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

Многие проблемы в анализе данных касаются кластеризации , группировки элементов данных в кластеры тесно связанных элементов. Иерархическая кластеризация — это версия кластерного анализа, в которой кластеры образуют иерархию или древовидную структуру, а не строгое разбиение элементов данных. В некоторых случаях этот тип кластеризации может быть выполнен как способ выполнения кластерного анализа в нескольких различных масштабах одновременно. В других случаях данные, которые должны быть проанализированы, естественно имеют неизвестную древовидную структуру, и цель состоит в том, чтобы восстановить эту структуру путем выполнения анализа. Оба эти вида анализа можно увидеть, например, в применении иерархической кластеризации к биологической таксономии . В этом приложении различные живые существа группируются в кластеры в различных масштабах или уровнях сходства ( вид, род, семейство и т. д. ). Этот анализ одновременно дает многомасштабную группировку организмов настоящего века и направлен на точное восстановление процесса ветвления или эволюционного дерева , которое в прошлые века произвело эти организмы. ^[1]

Входные данные для задачи кластеризации состоят из набора точек. ^[2] Кластер — это любое правильное подмножество точек, а иерархическая кластеризация — это максимальное семейство кластеров со свойством, что любые два кластера в семействе либо вложены, либо не пересекаются . В качестве альтернативы иерархическая кластеризация может быть представлена ​​в виде бинарного дерева с точками на его листьях; кластеры кластеризации — это наборы точек в поддеревьях, спускающихся от каждого узла дерева. ^[3]

В методах агломеративной кластеризации входные данные также включают функцию расстояния, определенную на точках, или численную меру их несходства. Расстояние или несходство должны быть симметричными: расстояние между двумя точками не зависит от того, какая из них рассматривается первой. Однако, в отличие от расстояний в метрическом пространстве , оно не обязательно должно удовлетворять неравенству треугольника . ^[2] Затем функция несходства расширяется с пар точек на пары кластеров. Различные методы кластеризации выполняют это расширение по-разному. Например, в методе кластеризации с одной связью расстояние между двумя кластерами определяется как минимальное расстояние между любыми двумя точками из каждого кластера. Учитывая это расстояние между кластерами, иерархическая кластеризация может быть определена жадным алгоритмом , который изначально помещает каждую точку в свой собственный кластер из одной точки, а затем многократно формирует новый кластер путем слияния ближайшей пары кластеров. ^[2]

Узким местом этого жадного алгоритма является подзадача поиска двух кластеров для слияния на каждом шаге. Известные методы многократного нахождения ближайшей пары кластеров в динамическом наборе кластеров либо требуют сверхлинейного пространства для поддержания структуры данных , которая может быстро находить ближайшие пары, либо они тратят больше линейного времени на нахождение каждой ближайшей пары. ^{[4] [5]} Алгоритм цепочки ближайших соседей использует меньшее количество времени и пространства, чем жадный алгоритм, объединяя пары кластеров в другом порядке. Таким образом, он избегает проблемы многократного нахождения ближайших пар. Тем не менее, для многих типов задач кластеризации можно гарантированно получить ту же иерархическую кластеризацию, что и жадный алгоритм, несмотря на другой порядок слияния. ^[2]

Алгоритм

Анимация алгоритма с использованием расстояния Уорда. Черные точки — это точки, серые области — более крупные кластеры, синие стрелки указывают на ближайших соседей, а красная полоса обозначает текущую цепочку. Для визуальной простоты, когда слияние оставляет цепочку пустой, оно продолжается с недавно слитым кластером.

Интуитивно понятно, что алгоритм цепочки ближайших соседей многократно следует цепочке кластеров A → B → C → ... , где каждый кластер является ближайшим соседом предыдущего, пока не будет достигнута пара кластеров, которые являются ближайшими соседями друг друга. ^[2]

Более подробно алгоритм выполняет следующие шаги: ^{[2] [6]}

• Инициализируйте набор активных кластеров, состоящий из n одноточечных кластеров, по одному для каждой входной точки.
• Пусть S — стековая структура данных , изначально пустая, элементами которой будут активные кластеры.
• При этом в наборе кластеров имеется более одного кластера:
  • Если S пуст, выберите произвольный активный кластер и поместите его в S.
  • Пусть C — активный кластер на вершине S. Вычислите расстояния от C до всех остальных кластеров, и пусть D — ближайший другой кластер.
  • Если D уже есть в S , он должен быть непосредственным предшественником C. Извлеките оба кластера из S и объедините их.
  • В противном случае, если D еще не находится в S , поместите его в S.

Когда возможно, что один кластер может иметь несколько равных ближайших соседей, то алгоритм требует последовательного правила разрешения конфликтов. Например, можно назначить произвольные индексные номера всем кластерам, а затем выбрать (среди равных ближайших соседей) тот, у которого наименьший индексный номер. Это правило предотвращает определенные виды непоследовательного поведения в алгоритме; например, без такого правила соседний кластер D может оказаться в стеке раньше, чем предшественник C. ^[7 ]

Анализ времени и пространства

Каждая итерация цикла выполняет один поиск ближайшего соседа кластера и либо добавляет один кластер в стек, либо удаляет из него два кластера. Каждый кластер добавляется в стек только один раз, потому что при повторном удалении он немедленно становится неактивным и объединяется. Всего в стек добавляется 2 n − 2 кластера: n одноточечных кластеров в исходном наборе и n − 2 внутренних узла, отличных от корня, в двоичном дереве, представляющем кластеризацию. Таким образом, алгоритм выполняет 2 n − 2 итераций push и n − 1 итераций pop. ^[2]

Каждая из этих итераций может тратить время на сканирование n − 1 межкластерных расстояний для поиска ближайшего соседа. Таким образом, общее количество вычислений расстояний, которые он делает, меньше 3 n ² . По той же причине общее время, используемое алгоритмом вне этих вычислений расстояний, составляет O( n ² ) . ^[2]

Поскольку единственной структурой данных является набор активных кластеров и стек, содержащий подмножество активных кластеров, требуемое пространство линейно зависит от количества входных точек. ^[2]

Корректность

Для того чтобы алгоритм был правильным, необходимо, чтобы извлечение и слияние двух верхних кластеров из стека алгоритма сохраняли свойство, что оставшиеся кластеры в стеке образуют цепочку ближайших соседей. Кроме того, необходимо, чтобы все кластеры, созданные в ходе алгоритма, были такими же, как кластеры, созданные жадным алгоритмом , который всегда объединяет два ближайших кластера, даже если жадный алгоритм в общем случае будет выполнять свои слияния в другом порядке, чем алгоритм цепочки ближайших соседей. Оба эти свойства зависят от конкретного выбора способа измерения расстояния между кластерами. ^[2]

Корректность этого алгоритма основана на свойстве его функции расстояния, называемом сводимостью . Это свойство было выявлено Брюнооге (1977) в связи с более ранним методом кластеризации, который использовал пары взаимных ближайших соседей, но не цепочки ближайших соседей. ^[8] Функция расстояния d на кластерах определяется как сводимая, если для каждых трех кластеров A , B и C в жадной иерархической кластеризации, таких, что A и B являются взаимными ближайшими соседями, выполняется следующее неравенство: ^[2]

d ( A ∪ B , C ) ≥ min(d( A , C ), d( B , C )) .

Если функция расстояния обладает свойством сводимости, то слияние двух кластеров C и D может вызвать изменение ближайшего соседа E только в том случае, если этот ближайший сосед был одним из C и D. Это имеет два важных последствия для алгоритма цепочки ближайших соседей. Во-первых, с помощью этого свойства можно показать, что на каждом шаге алгоритма кластеры в стеке S образуют допустимую цепочку ближайших соседей, поскольку всякий раз, когда ближайший сосед становится недействительным, он немедленно удаляется из стека. ^[2]

Во-вторых, и что еще важнее, из этого свойства следует, что если два кластера C и D оба принадлежат к жадной иерархической кластеризации и являются взаимными ближайшими соседями в любой момент времени, то они будут объединены жадной кластеризацией, поскольку они должны оставаться взаимными ближайшими соседями до тех пор, пока не будут объединены. Из этого следует, что каждая пара взаимных ближайших соседей, найденная алгоритмом цепочки ближайших соседей, также является парой кластеров, найденных жадным алгоритмом, и, следовательно, алгоритм цепочки ближайших соседей вычисляет точно такую ​​же кластеризацию (хотя и в другом порядке), как и жадный алгоритм. ^[2]

Применение к определенным расстояниям кластеризации

Метод Уорда

Метод Уорда — это метод агломеративной кластеризации, в котором различие между двумя кластерами A и B измеряется величиной, на которую объединение двух кластеров в один более крупный кластер увеличит среднеквадратичное расстояние точки до ее кластерного центроида . ^[9] То есть,

${\displaystyle d(A,B)=\sum _{x\in A,y\in B}{\frac {d^{2}(x,y)}{|A|+|B|}}-\sum _{x,y\in A}{\frac {d^{2}(x,y)}{|A|}}-\sum _{x,y\in B}{\frac {d^{2}(x,y)}{|B|}}.}$

Выраженная через центроид и мощность двух кластеров, она имеет более простую формулу: ${\displaystyle c_{A}}$ ${\displaystyle n_{A}}$

${\displaystyle d(A,B)={\frac {d^{2}(c_{a},c_{b})}{1/n_{A}+1/n_{B}}},}$

позволяя вычислять его за постоянное время на расчет расстояния. Хотя метод Уорда очень чувствителен к выбросам , он является наиболее популярной вариацией агломеративной кластеризации как из-за круглой формы кластеров, которые он обычно формирует, так и из-за его принципиального определения как кластеризации, которая на каждом шаге имеет наименьшую дисперсию в пределах своих кластеров. ^[10] В качестве альтернативы это расстояние можно рассматривать как разницу в стоимости k-средних между новым кластером и двумя старыми кластерами.

Расстояние Уорда также может быть сокращено, что можно легко увидеть из другой формулы для расчета расстояния объединенного кластера из расстояний кластеров, из которых он был объединен: ^{[9] [11]}

${\displaystyle d(A\cup B,C)={\frac {n_{A}+n_{C}}{n_{A}+n_{B}+n_{C}}}d(A,C)+{\frac {n_{B}+n_{C}}{n_{A}+n_{B}+n_{C}}}d(B,C)-{\frac {n_{C}}{n_{A}+n_{B}+n_{C}}}d(A,B).}$

Формулы обновления расстояния, такие как эта, называются формулами "типа Ланса–Вильямса" в честь работы Ланса и Уильямса (1967). Если — наименьшее из трех расстояний в правой части (что обязательно было бы верно, если бы и были взаимными ближайшими соседями), то отрицательный вклад его члена отменяется коэффициентом одного из двух других членов, оставляя положительное значение, добавленное к средневзвешенному значению двух других расстояний. Таким образом, объединенное расстояние всегда по крайней мере так же велико, как минимум и , что соответствует определению сводимости. ${\displaystyle d(A,B)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n_{C}}$ ${\displaystyle d(A,C)}$ ${\displaystyle d(B,C)}$

Поскольку расстояние Уорда является сокращаемым, алгоритм цепочки ближайших соседей, использующий расстояние Уорда, вычисляет точно такую ​​же кластеризацию, как и стандартный жадный алгоритм. Для n точек в евклидовом пространстве постоянной размерности требуется время O ( n ² ) и пространство O ( n ) . ^[6]

Полное сцепление и среднее расстояние

Кластеризация с полной связью или кластеризация с дальним соседом — это форма агломеративной кластеризации, которая определяет несходство между кластерами как максимальное расстояние между любыми двумя точками из двух кластеров. Аналогично, кластеризация со средним расстоянием использует среднее попарное расстояние в качестве несходства. Как и расстояние Уорда, эти две формы кластеризации подчиняются формуле типа Ланса–Вильямса. При полной связи расстояние является максимальным из двух расстояний и . Следовательно, оно по крайней мере равно минимальному из этих двух расстояний, что является требованием сокращаемости. Для среднего расстояния — это просто средневзвешенное значение расстояний и . Опять же, это по крайней мере столько же, сколько минимальное из двух расстояний. Таким образом, в обоих этих случаях расстояние сокращаемо. ^{[9] [11]} ${\displaystyle d(A\cup B,C)}$ ${\displaystyle d(A,C)}$ ${\displaystyle d(B,C)}$ ${\displaystyle d(A\cup B,C)}$ ${\displaystyle d(A,C)}$ ${\displaystyle d(B,C)}$

В отличие от метода Уорда, эти две формы кластеризации не имеют метода постоянного времени для вычисления расстояний между парами кластеров. Вместо этого можно поддерживать массив расстояний между всеми парами кластеров. Всякий раз, когда два кластера объединяются, формулу можно использовать для вычисления расстояния между объединенным кластером и всеми другими кластерами. Поддержание этого массива в ходе алгоритма кластеризации занимает время и пространство O ( n ² ) . Алгоритм цепочки ближайших соседей может использоваться в сочетании с этим массивом расстояний, чтобы найти ту же кластеризацию, что и жадный алгоритм для этих случаев. Его общее время и пространство, используя этот массив, также составляют O ( n ² ) . ^[12]

Те же самые временные и пространственные ограничения O ( n ² ) могут быть достигнуты и другим способом, с помощью техники, которая накладывает структуру данных очереди приоритетов на основе квадродерева поверх матрицы расстояний и использует ее для выполнения стандартного жадного алгоритма кластеризации. Этот метод квадродерева является более общим, поскольку он работает даже для методов кластеризации, которые не являются редуцируемыми. ^[4] Однако алгоритм цепочки ближайших соседей соответствует своим временным и пространственным ограничениям, используя более простые структуры данных. ^[12]

Одинарное соединение

В кластеризации с одиночной связью или кластеризации по ближайшему соседу, старейшей форме агломеративной иерархической кластеризации, ^[11] различие между кластерами измеряется как минимальное расстояние между любыми двумя точками из двух кластеров. С этим различием,

${\displaystyle d(A\cup B,C)=\min(d(A,C),d(B,C)),}$

удовлетворяя требованию сводимости как равенство, а не неравенство. (Односвязность также подчиняется формуле Лэнса–Вильямса ^{[9] [11],} но с отрицательным коэффициентом, из которого сложнее доказать сводимость.)

Как и в случае с полной связью и средним расстоянием, сложность вычисления расстояний кластеров приводит к тому, что алгоритму цепочки ближайших соседей требуется время и пространство O ( n ² ) для вычисления кластеризации с одной связью. Однако кластеризация с одной связью может быть найдена более эффективно с помощью альтернативного алгоритма, который вычисляет минимальное остовное дерево входных расстояний с помощью алгоритма Прима , а затем сортирует ребра минимального остовного дерева и использует этот отсортированный список для управления слиянием пар кластеров. В алгоритме Прима каждое последующее ребро минимального остовного дерева может быть найдено последовательным поиском по несортированному списку наименьших ребер, соединяющих частично построенное дерево с каждой дополнительной вершиной. Этот выбор экономит время, которое алгоритм в противном случае потратил бы на корректировку весов вершин в своей очереди приоритетов . Использование алгоритма Прима таким образом потребовало бы времени O ( n ² ) и пространства O ( n ) , что соответствует наилучшим границам, которые могут быть достигнуты с помощью алгоритма цепочки ближайших соседей для расстояний с постоянным временем вычислений. ^[13]

Расстояние до центра масс

Другой мерой расстояния, обычно используемой в агломеративной кластеризации, является расстояние между центроидами пар кластеров, также известное как метод взвешенной группы. ^{[9] [11]} Его можно легко вычислить за постоянное время на расчет расстояния. Однако он не является сокращаемым. Например, если входные данные образуют набор из трех точек равностороннего треугольника, объединение двух из этих точек в более крупный кластер приводит к уменьшению расстояния между кластерами, что является нарушением сокращаемости. Поэтому алгоритм цепочки ближайших соседей не обязательно найдет ту же кластеризацию, что и жадный алгоритм. Тем не менее, Муртаг (1983) пишет, что алгоритм цепочки ближайших соседей обеспечивает «хорошую эвристику» для метода центроидов. ^[2] Другой алгоритм Дэя и Эдельсбруннера (1984) можно использовать для поиска жадной кластеризации за время O ( n ² ) для этой меры расстояния. ^[5]

Расстояния, чувствительные к порядку слияния

Представление выше явно запрещает расстояния, чувствительные к порядку слияния. Действительно, разрешение таких расстояний может вызвать проблемы. В частности, существуют кластерные расстояния, чувствительные к порядку, которые удовлетворяют сводимости, но для которых вышеуказанный алгоритм вернет иерархию с субоптимальными затратами. Поэтому, когда кластерные расстояния определяются рекурсивной формулой (как некоторые из рассмотренных выше), необходимо следить за тем, чтобы они не использовали иерархию способом, чувствительным к порядку слияния. ^[14]

История

Алгоритм цепочки ближайших соседей был разработан и реализован в 1982 году Жаном-Полем Бензекри ^[15] и Дж. Хуаном. ^[16] Они основали этот алгоритм на более ранних методах, которые строили иерархические кластеризации с использованием пар взаимных ближайших соседей без использования цепочек ближайших соседей. ^{[8] [17]}

Ссылки

1. Гордон, Аллан Д. (1996), «Иерархическая кластеризация», в Arabie, P.; Hubert, LJ; De Soete, G. (ред.), Кластеризация и классификация , River Edge, NJ: World Scientific, стр. 65–121, ISBN 9789814504539.
2. Муртаг, Фионн (1983), «Обзор последних достижений в области иерархических алгоритмов кластеризации» (PDF) , The Computer Journal , 26 (4): 354–359, doi : 10.1093/comjnl/26.4.354.
3. Сюй, Руй; Вунш, Дон (2008), "3.1 Иерархическая кластеризация: Введение", Кластеризация , Серия IEEE Press по вычислительному интеллекту, т. 10, John Wiley & Sons, стр. 31, ISBN 978-0-470-38278-3.
4. Эппштейн, Дэвид (2000), «Быстрая иерархическая кластеризация и другие приложения динамических ближайших пар», J. Experimental Algorithmics , 5 (1), ACM: 1–23, arXiv : cs.DS/9912014 , Bibcode : 1999cs.......12014E, doi : 10.1145/351827.351829, S2CID  1357701.
5. Day, William HE; Edelsbrunner, Herbert (1984), "Эффективные алгоритмы для агломеративных иерархических методов кластеризации" (PDF) , Journal of Classification , 1 (1): 7–24, doi :10.1007/BF01890115, S2CID  121201396.
6. Murtagh, Fionn (2002), «Кластеризация в массивных наборах данных», в Abello, James M.; Pardalos, Panos M.; Resende, Mauricio GC (ред.), Справочник по массивным наборам данных , Massive Computing, т. 4, Springer, стр. 513–516, Bibcode : 2002hmds.book.....A, ISBN 978-1-4020-0489-6.
7. Для этого правила разрешения конфликтов и примера того, как разрешение конфликтов необходимо для предотвращения циклов в графе ближайших соседей, см. Sedgewick, Robert (2004), "Рисунок 20.7", Algorithms in Java, Часть 5: Graph Algorithms (3-е изд.), Addison-Wesley, стр. 244, ISBN 0-201-36121-3.
8. Bruynooghe, Michel (1977), «Méthodes nouvelles enclassique de données Taxinomiqes nombreuses», Statistique et Analyse des Données , 3 : 24–42..
9. Миркин, Борис (1996), Математическая классификация и кластеризация, Невыпуклая оптимизация и ее приложения, т. 11, Дордрехт: Kluwer Academic Publishers, стр. 140–144, ISBN 0-7923-4159-7, МР  1480413.
10. Tuffery, Stéphane (2011), "9.10 Агломеративная иерархическая кластеризация", Data Mining and Statistics for Decision Making , Wiley Series in Computational Statistics, стр. 253–261, ISBN 978-0-470-68829-8.
11. Лэнс, GN; Уильямс, WT (1967), «Общая теория стратегий классификационной сортировки. I. Иерархические системы», The Computer Journal , 9 (4): 373–380, doi : 10.1093/comjnl/9.4.373.
12. Гронау, Илан; Моран, Шломо (2007), «Оптимальные реализации UPGMA и других распространенных алгоритмов кластеризации», Information Processing Letters , 104 (6): 205–210, doi :10.1016/j.ipl.2007.07.002, MR  2353367.
13. Gower, JC; Ross, GJS (1969), «Минимальные остовные деревья и кластерный анализ с одиночной связью», Журнал Королевского статистического общества, Серия C , 18 (1): 54–64, JSTOR  2346439, MR  0242315.
14. Мюлльнер, Дэниел (2011), Современные иерархические алгоритмы агломеративной кластеризации , том. 1109, arXiv : 1109.2378 , Bibcode : 2011arXiv1109.2378M.
15. Бензекри, Ж.-П. (1982), «Построение восходящей иерархической классификации для поиска и цепочки взаимных голосов», Les Cahiers de l'Analyse des Données , 7 (2): 209–218.
16. Хуан, Дж. (1982), «Программа иерархической классификации по алгоритму исследований в цепочке ответных голосов», Les Cahiers de l'Analyse des Données , 7 (2): 219–225.
17. де Рам, К. (1980), «La классификация восходящей иерархии selon la méthode des voisins reciproques», Les Cahiers de l'Analyse des Données , 5 (2): 135–144.