Кластеризация методом K-средних

Кластеризация методом K-средних разделяет наблюдения на фиксированное число кластеров путем минимизации общей внутрикластерной суммы квадратов расстояний до центроидов кластеров.

Definition

Кластеризация методом K-средних — это метод разбиения, который размещает заданное количество центров кластеров и присваивает каждое наблюдение его ближайшему центру таким образом, чтобы минимизировать общую сумму квадратов евклидовых расстояний от наблюдений до их назначенных центров.

Scope

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

Core questions

• Как можно разделить наблюдения для минимизации внутрикластерной дисперсии?
• Почему алгоритм сходится только к локальному оптимуму и как это смягчается?
• Как выбирается количество кластеров?
• Какие формы и масштабы кластеров неявно предполагает метод?

Key theories

Минимизация внутрикластерной суммы квадратов

Метод K-средних ищет такое разбиение и набор центроидов, которые минимизируют общую сумму квадратов расстояний от точек до их центров кластеров — цель, для которой чередующаяся итерация присваивания-обновления монотонно уменьшает критерий.

Чувствительность к локальному оптимуму

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

Clinical relevance

K-средние — это быстрый, масштабируемый метод по умолчанию для разбиения больших наборов данных, который используется в векторном квантовании, уменьшении количества цветов изображений, сегментации клиентов и в качестве инициализации для более сложных моделей.

History

Идея разбиения на основе центроидов была формализована МакКуином, который назвал метод k-средних в 1967 году, основываясь на более раннем алгоритме квантования Ллойда. Он стал одним из наиболее широко используемых методов кластеризации благодаря своей простоте и скорости.

Debates

Неявные допущения метода k-средних

Минимизация квадрата евклидова расстояния благоприятствует приблизительно сферическим кластерам одинакового размера, поэтому метод k-средних может вводить в заблуждение, когда кластеры вытянуты, имеют неравный размер или невыпуклую форму, что мотивирует использование модельных или плотностных альтернатив.

Key figures

• James MacQueen
• Stuart Lloyd

Seminal works

• hastie2009
• everitt2011
• macqueen1967

Frequently asked questions

Почему метод k-средних дает разные результаты при разных запусках?

Его целевая функция не является выпуклой, поэтому алгоритм сходится к локальному оптимуму, который зависит от случайных начальных центров; стандартной практикой является запуск его несколько раз и выбор лучшего результата.

Как выбрать количество кластеров k?

Общие эвристики включают метод «локтя» для внутрикластерной суммы квадратов, статистику разрыва и среднюю ширину силуэта, хотя ни одна из них не является окончательной, и выбор часто определяется предметными знаниями.