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

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

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

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

Фон

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

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

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

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

Алгоритм

Интуитивно понятно, что алгоритм цепочки ближайших соседей неоднократно следует за цепочкой кластеров $A \to B \to C \to ...$ , где каждый кластер является ближайшим соседом предыдущего, пока не достигнет пары кластеров, которые являются взаимными ближайшими соседями. ^[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$ итерации выталкивания и $n - 1$ итераций выталкивания. ^[2]

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

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

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

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

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

d (А \cup B, C) \geq min(d(A, C), d(B, C))

.

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

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

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

Метод Уорда

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

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|}}.

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

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

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

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

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) .Если $d(A,B)$ является наименьшим из трех расстояний в правой части (что обязательно было бы верно, если бы $A$ и $B$ являются взаимными ближайшими соседями), то отрицательный вклад от его члена компенсируется $n_{C}$ коэффициент одного из двух других членов, оставляя положительное значение, добавленное к средневзвешенному значению двух других расстояний. Следовательно, общее расстояние всегда не меньше минимального $d(A,C)$ и $d(B,C)$ , отвечающий определению сводимости.

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

Полная связь и среднее расстояние

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

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

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

Одинарная связь

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

d(A\cup B,C)=\min(d(A,C),d(B,C)),

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

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

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

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

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

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

История

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

Ссылки

^ Гордон, Аллан Д. (1996), «Иерархическая кластеризация» , в Arabie, P.; Хьюберт, LJ; Де Соете, Г. (ред.), Кластеризация и классификация , River Edge, Нью-Джерси: World Scientific, стр. 65–121, ISBN. 9789814504539 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н Мурта, Фионн (1983), «Обзор последних достижений в алгоритмах иерархической кластеризации» (PDF) , The Computer Journal , 26 (4): 354–359, doi : 10.1093/comjnl/26.4.354 .
^ Сюй, Руй; Вунш, Дон (2008), «3.1 Иерархическая кластеризация: Введение» , Кластеризация , Серия прессы IEEE по вычислительному интеллекту, том. 10, Джон Уайли и сыновья, с. 31, ISBN 978-0-470-38278-3 .
^ Jump up to: ^а ^б Эппштейн, Дэвид (2000), «Быстрая иерархическая кластеризация и другие применения динамических ближайших пар» , J. Experimental Algorithmics , 5 (1), ACM: 1–23, arXiv : cs.DS/9912014 , Bibcode : 1999cs... ....12014E , doi : 10.1145/351827.351829 , S2CID 1357701 .
^ Jump up to: ^а ^б Дэй, Уильям Х.Э.; Эдельсбруннер, Герберт (1984), «Эффективные алгоритмы для методов агломеративной иерархической кластеризации» (PDF) , Journal of Classification , 1 (1): 7–24, doi : 10.1007/BF01890115 , S2CID 121201396 .
^ Jump up to: ^а ^б Мурта, Фионн (2002), «Кластеризация в массивных наборах данных» , в Абелло, Джеймс М.; Пардалос, Панос М.; Ресенде, Маурисио Г.К. (ред.), Справочник по массивным наборам данных , Massive Computing, vol. 4, Springer, стр. 513–516, Bibcode : 2002hmds.book.....A , ISBN. 978-1-4020-0489-6 .
^ Информацию об этом правиле разрешения конфликтов и примере того, как необходимо разрешить конфликты для предотвращения циклов в графе ближайших соседей, см. Седжвик, Роберт (2004), «Рисунок 20.7», Алгоритмы на Java, Часть 5: Алгоритмы графов (3-е изд.), Аддисон-Уэсли, стр. 244, ISBN 0-201-36121-3 .
^ Jump up to: ^а ^б Брюйнуг, Мишель (1977), «Новые методы автоматической классификации многочисленных таксономических данных» , Статистика и анализ данных , 3 : 24–42 .
^ Jump up to: ^а ^б ^с ^д ^и Миркин, Борис (1996), Математическая классификация и кластеризация , Невыпуклая оптимизация и ее приложения, том. 11, Дордрехт: Kluwer Academic Publishers, стр. 140–144, ISBN. 0-7923-4159-7 , МР 1480413 .
^ Таффери, Стефан (2011), «9.10 Агломеративная иерархическая кластеризация», Интеллектуальный анализ данных и статистика для принятия решений , Серия Wiley по вычислительной статистике, стр. 253–261, ISBN 978-0-470-68829-8 .
^ Jump up to: ^а ^б ^с ^д ^и Лэнс, Дж.Н.; Уильямс, В.Т. (1967), «Общая теория классификационных стратегий сортировки. I. Иерархические системы», The Computer Journal , 9 (4): 373–380, doi : 10.1093/comjnl/9.4.373 .
^ Jump up to: ^а ^б Гронау, Илан; Моран, Шломо (2007), «Оптимальные реализации UPGMA и других распространенных алгоритмов кластеризации», Information Processing Letters , 104 (6): 205–210, doi : 10.1016/j.ipl.2007.07.002 , MR 2353367 .
^ Гауэр, Дж. К.; Росс, GJS (1969), «Минимальные остовные деревья и кластерный анализ с одной связью», Журнал Королевского статистического общества, серия C , 18 (1): 54–64, JSTOR 2346439 , MR 0242315 .
^ Мюлльнер, Дэниел (2011), Современные иерархические алгоритмы агломеративной кластеризации , том. 1109, arXiv : 1109.2378 , Bibcode : 2011arXiv1109.2378M .
^ Бенсекри, Ж.-П. (1982), «Построение иерархической восходящей классификации путем цепного поиска взаимных соседей» , Les Cahiers de l’Analyse des Data , 7 (2): 209–218 .
^ Хуан, Дж. (1982), «Программа иерархической классификации, использующая алгоритм цепного поиска взаимных соседей» , Les Cahiers de l'Analyse des Data , 7 (2): 219–225 .
^ де Рам, К. (1980), «Восходящая иерархическая классификация в соответствии с методом взаимных соседей» , Les Cahiers de l'Analyse des Data , 5 (2): 135–144 .

[1] Гордон, Аллан Д. (1996), «Иерархическая кластеризация» , в Arabie, P.; Хьюберт, LJ; Де Соете, Г. (ред.), Кластеризация и классификация , River Edge, Нью-Джерси: World Scientific, стр. 65–121, ISBN. 9789814504539 .

[murtagh-tcj-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н Мурта, Фионн (1983), «Обзор последних достижений в алгоритмах иерархической кластеризации» (PDF) , The Computer Journal , 26 (4): 354–359, doi : 10.1093/comjnl/26.4.354 .

[3] Сюй, Руй; Вунш, Дон (2008), «3.1 Иерархическая кластеризация: Введение» , Кластеризация , Серия прессы IEEE по вычислительному интеллекту, том. 10, Джон Уайли и сыновья, с. 31, ISBN 978-0-470-38278-3 .

[e-jea-4] Jump up to: ^а ^б Эппштейн, Дэвид (2000), «Быстрая иерархическая кластеризация и другие применения динамических ближайших пар» , J. Experimental Algorithmics , 5 (1), ACM: 1–23, arXiv : cs.DS/9912014 , Bibcode : 1999cs... ....12014E , doi : 10.1145/351827.351829 , S2CID 1357701 .

[day-edels-5] Jump up to: ^а ^б Дэй, Уильям Х.Э.; Эдельсбруннер, Герберт (1984), «Эффективные алгоритмы для методов агломеративной иерархической кластеризации» (PDF) , Journal of Classification , 1 (1): 7–24, doi : 10.1007/BF01890115 , S2CID 121201396 .

[murtagh-hmds-6] Jump up to: ^а ^б Мурта, Фионн (2002), «Кластеризация в массивных наборах данных» , в Абелло, Джеймс М.; Пардалос, Панос М.; Ресенде, Маурисио Г.К. (ред.), Справочник по массивным наборам данных , Massive Computing, vol. 4, Springer, стр. 513–516, Bibcode : 2002hmds.book.....A , ISBN. 978-1-4020-0489-6 .

[7] Информацию об этом правиле разрешения конфликтов и примере того, как необходимо разрешить конфликты для предотвращения циклов в графе ближайших соседей, см. Седжвик, Роберт (2004), «Рисунок 20.7», Алгоритмы на Java, Часть 5: Алгоритмы графов (3-е изд.), Аддисон-Уэсли, стр. 244, ISBN 0-201-36121-3 .

[b77-8] Jump up to: ^а ^б Брюйнуг, Мишель (1977), «Новые методы автоматической классификации многочисленных таксономических данных» , Статистика и анализ данных , 3 : 24–42 .

[mirkin-9] Jump up to: ^а ^б ^с ^д ^и Миркин, Борис (1996), Математическая классификация и кластеризация , Невыпуклая оптимизация и ее приложения, том. 11, Дордрехт: Kluwer Academic Publishers, стр. 140–144, ISBN. 0-7923-4159-7 , МР 1480413 .

[10] Таффери, Стефан (2011), «9.10 Агломеративная иерархическая кластеризация», Интеллектуальный анализ данных и статистика для принятия решений , Серия Wiley по вычислительной статистике, стр. 253–261, ISBN 978-0-470-68829-8 .

[lance-williams-11] Jump up to: ^а ^б ^с ^д ^и Лэнс, Дж.Н.; Уильямс, В.Т. (1967), «Общая теория классификационных стратегий сортировки. I. Иерархические системы», The Computer Journal , 9 (4): 373–380, doi : 10.1093/comjnl/9.4.373 .

[gm07-12] Jump up to: ^а ^б Гронау, Илан; Моран, Шломо (2007), «Оптимальные реализации UPGMA и других распространенных алгоритмов кластеризации», Information Processing Letters , 104 (6): 205–210, doi : 10.1016/j.ipl.2007.07.002 , MR 2353367 .

[13] Гауэр, Дж. К.; Росс, 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 Data , 7 (2): 209–218 .

[16] Хуан, Дж. (1982), «Программа иерархической классификации, использующая алгоритм цепного поиска взаимных соседей» , Les Cahiers de l'Analyse des Data , 7 (2): 219–225 .

[17] де Рам, К. (1980), «Восходящая иерархическая классификация в соответствии с методом взаимных соседей» , Les Cahiers de l'Analyse des Data , 5 (2): 135–144 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]