Давайте быстро рассмотрим типы алгоритмов кластеризации и когда следует выбирать каждый тип.
При выборе алгоритма кластеризации следует учитывать, масштабируется ли алгоритм для вашего набора данных. Наборы данных в машинном обучении могут иметь миллионы примеров, но не все алгоритмы кластеризации эффективно масштабируются. Многие алгоритмы кластеризации работают, вычисляя сходство между всеми парами примеров. Это означает, что их время выполнения увеличивается пропорционально квадрату числа примеров \(n\), обозначаемому как \(O(n^2)\) в обозначении сложности. Алгоритмы \(O(n^2)\) непрактичны, когда число примеров исчисляется миллионами. Этот курс фокусируется на алгоритме k-средних , который имеет сложность \(O(n)\), что означает, что алгоритм масштабируется линейно с \(n\).
Типы кластеризации
Существует несколько подходов к кластеризации. Полный список см . в «Всестороннем обзоре алгоритмов кластеризации» Xu, D. & Tian, Y. Ann. Данные. науч. (2015) 2: 165. Каждый подход лучше всего подходит для определенного распределения данных. Ниже приводится краткое обсуждение четырех распространенных подходов с акцентом на кластеризацию на основе центроидов с использованием k-средних.
Кластеризация на основе центроида
Кластеризация на основе центроида организует данные в неиерархические кластеры, в отличие от иерархической кластеризации, определенной ниже. k-means — это наиболее широко используемый алгоритм кластеризации на основе центроидов. Алгоритмы на основе центроидов эффективны, но чувствительны к начальным условиям и выбросам. Этот курс посвящен k-средним, потому что это эффективный, действенный и простой алгоритм кластеризации.
Кластеризация на основе плотности
Кластеризация на основе плотности объединяет области с высокой плотностью примеров в кластеры. Это позволяет использовать распределения произвольной формы, если можно соединить плотные области. Эти алгоритмы имеют трудности с данными различной плотности и высокой размерности. Кроме того, по замыслу эти алгоритмы не присваивают кластерам выбросы.
Кластеризация на основе распределения
Этот подход к кластеризации предполагает, что данные состоят из распределений, таких как распределения Гаусса . На рис. 3 алгоритм на основе распределения объединяет данные в три распределения Гаусса. По мере увеличения расстояния от центра распределения вероятность того, что точка принадлежит распределению, уменьшается. Полосы показывают уменьшение вероятности. Когда вы не знаете тип распределения в ваших данных, вы должны использовать другой алгоритм.
Иерархическая кластеризация
Иерархическая кластеризация создает дерево кластеров. Неудивительно, что иерархическая кластеризация хорошо подходит для иерархических данных, таких как таксономии. Для примера см. «Сравнение 61 секвенированного генома кишечной палочки » Оксаны Лукьянченко, Труди Вассенаар и Дэйва Ассери. Кроме того, еще одним преимуществом является то, что любое количество кластеров можно выбрать, разрезав дерево на нужном уровне.
