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