Алгоритм кластеризации Canopy

Алгоритм кластеризации купола — это неконтролируемый алгоритм предварительной кластеризации , предложенный Эндрю МакКаллумом , Камалем Нигамом и Лайлом Унгаром в 2000 году. ^[1] Он часто используется в качестве этапа предварительной обработки для алгоритма K-средних или алгоритма иерархической кластеризации . Он предназначен для ускорения операций кластеризации на больших наборах данных , где непосредственное использование другого алгоритма может оказаться нецелесообразным из-за размера набора данных.

Описание

Алгоритм работает следующим образом, используя два порога $T_{1}$ (свободное расстояние) и $T_{2}$ (небольшое расстояние), где $T_{1}>T_{2}$ . ^[1]^[2]

Начните с набора точек данных, которые необходимо кластеризовать.
Удалите точку из набора, начав новый «навес», содержащий эту точку.
Для каждой точки, оставшейся в наборе, назначьте ее новому куполу, если ее расстояние до первой точки купола меньше свободного расстояния. $T_{1}$ .
Если расстояние до точки дополнительно меньше минимального расстояния $T_{2}$ , удалите его из исходного набора.
Повторяйте, начиная с шага 2, пока в наборе для кластеризации больше не останется точек данных.
Эти относительно дешевые сгруппированные купола можно разделить на подкластеры, используя более дорогой, но точный алгоритм.

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

Применимость

Поскольку алгоритм использует функции расстояния и требует указания порогов расстояния, его применимость для многомерных данных ограничена проклятием размерности . Только когда доступна дешевая и аппроксимативная – малоразмерная – функция расстояния, полученные навесы сохранят кластеры, созданные с помощью K-средних.

Его преимущества включают в себя:

Уменьшается количество экземпляров обучающих данных, которые необходимо сравнивать на каждом этапе.
Есть некоторые свидетельства того, что полученные кластеры улучшаются. ^[3]

Ссылки

^ Jump up to: ^а ^б МакКаллум, А.; Нигам, К.; и Унгар Л.Х. (2000) «Эффективная кластеризация наборов данных большой размерности с применением сопоставления ссылок» , Труды шестой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных, 169-178. дои : 10.1145/347090.347123
^ «Алгоритм навесов» . курсы.cs.washington.edu . Проверено 6 сентября 2014 г.
^ Описание Mahout Canopy-Clustering Проверено 02 июля 2022 г.

[original-1] Jump up to: ^а ^б МакКаллум, А.; Нигам, К.; и Унгар Л.Х. (2000) «Эффективная кластеризация наборов данных большой размерности с применением сопоставления ссылок» , Труды шестой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных, 169-178. дои : 10.1145/347090.347123

[2] «Алгоритм навесов» . курсы.cs.washington.edu . Проверено 6 сентября 2014 г.

[3] Описание Mahout Canopy-Clustering Проверено 02 июля 2022 г.

[1]

[2]

[3]