Алгоритм кластеризации Canopy - Canopy clustering algorithm
Алгоритм кластеризации сени является неконтролируемой пре- кластеризации алгоритма введен Эндрю МакКаллум , Камаль Nigam и Lyle Унгар в 2000 году часто используются в качестве предварительной обработки шага для K-средств алгоритма или иерархическая кластеризация алгоритм. Он предназначен для ускорения операций кластеризации на больших наборах данных , где использование другого алгоритма напрямую может быть нецелесообразным из-за размера набора данных.
Описание
Алгоритм работает следующим образом, используя два порога (свободное расстояние) и (точное расстояние), где .
- Начните с набора точек данных для кластеризации.
- Удалите точку из набора, начав новый «навес», содержащий эту точку.
- Для каждой точки, оставшейся в наборе, назначьте ее новому куполу, если расстояние от него до первой точки купола меньше, чем свободное расстояние .
- Если расстояние до точки дополнительно меньше минимального расстояния , удалите ее из исходного набора.
- Повторяйте с шага 2, пока в наборе для кластеризации не останется больше точек данных.
- Эти относительно дешево сгруппированные навесы могут быть сгруппированы с использованием более дорогого, но точного алгоритма.
Важное замечание: отдельные точки данных могут быть частью нескольких навесов. В качестве дополнительного ускорения можно использовать приблизительную и быструю метрику расстояния для 3, где более точную и медленную метрику расстояния можно использовать для шага 4.
Применимость
Поскольку алгоритм использует функции расстояния и требует указания пороговых значений расстояния, его применимость для данных большой размерности ограничена проклятием размерности . Только когда доступна дешевая и приближенная - низкоразмерная - функция расстояния, изготовленные навесы сохранят кластеры, полученные с помощью K-средних.
Его преимущества включают:
- Количество экземпляров обучающих данных, которые необходимо сравнивать на каждом шаге, уменьшается.
- Есть некоторые свидетельства того, что полученные кластеры улучшаются.