[МУЗЫКА]
[МУЗЫКА]
Кластеризация K-means, или k-средних — это метод разбиения
немаркированного набора данных на K различных неперекрывающихся кластеров.
Этот алгоритм прост для реализации, относительно быстрый,
легко адаптируется и очень часто применяется на практике.
Для выполнения алгоритма кластеризации необходимо изначально задать количество
кластеров, и в дальнейшем алгоритм сам назначит каждому наблюдению тот или
иной из K кластеров.
Предположим, что у нас есть набор из N наблюдений, в d-мерном пространстве.
Нашей задачей будет назначить каждому наблюдению один из K кластеров,
учитывая, что K уже изначально задано.
Давайте формализуем данную постановку задачи,
а именно введем сначала d-мерные вектора μk, где k будет изменяться от 1 до K,
в котором μk представляют собой центроиды k-кластеров,
причем они не являются точками пространства признаков x,
хотя они находятся в одном и том же пространстве.
Таким образом, нашей целью будет назначить каждому
наблюдению свой вектор μk так, чтобы сумма квадратов расстояний от
каждой точки данных до ее ближайшего вектора μk была минимальной.
Таким образом можно определить следующий функционал.
Данная функция представляет собой сумму квадратов
расстояний от каждой точки данных до ее назначенного вектора μk.
Другими словами, для каждого объекта в каждом кластере расстояние
от объекта до центра кластера возводится в квадрат, а расстояния суммируются.
И этацелевая функция пытается сделать полученные k-кластеры
компактными и как можно более разделимыми.
Алгоритм кластеризации K-means можно разделить на две фазы,
а именно на фазу инициализации и на фазу итераций.
На этапе инициализации алгоритм случайным образом назначает наблюдения в k-кластеры.
На этапе итерации алгоритм вычисляет расстояние между наблюдением и
каждым кластером и присваивает регистр ближайшему кластеру.
Алгоритм завершается, когда на какой-то итерации у нас не будет
происходить изменения центров кластеров.
Это произойдет определенно за конечное число итераций, так как количество
возможных разбиений конечного множества конечно, а на каждом шаге суммарное
квадратичное отклонение не возрастает, поэтому зацикливание невозможно.
Метод k-средних не гарантирует сходимость к глобальному оптимуму и часто
заканчивается в локальном.
Поэтому для получения более качественных результатов желательным
является запуск данного алгоритма для различных значений параметра K.
Рассмотрим набор объектов двумерной плоскости, как показано на рисунке.
Пусть параметр K у нас будет равен 2, соответственно,
алгоритм кластеризации должен разделить данный набор точек на два кластера.
Согласно алгоритму, мы произвольно выбираем два объекта и назначаем их
начальными центрами кластеров.
Обозначаем их плюсом, как показано на рисунке b.
Каждому объекту присваивается ближайший расположенный центр кластеров.
Такое распределение формирует силуэты, покрашенные в красный и синий цвета,
как показано на рисунке c.
Затем данные центры обновляются.
Соответственно, каждое среднее значение кластера
пересчитывается на основе текущих объектов кластера.
И используются новые центры кластеров.
Объекты, соответственно, также перераспределяются в кластеры,
и такое перераспределение формирует новые силуэты, как показано на рисунках d и e.
Этот процесс приводит к рисунку f.
В конце концов переназначения объектов в любом кластере не происходит, и поэтому
процесс завершается, и полученные кластеры возвращаются процессом кластеризации.
Рассмотрим вычислительную сложность данного алгоритма.
Требования к памяти для алгоритма K-means достаточно скромны, поскольку нам
необходимо хранить только наборы данных и центроиды для этих кластеров.
В частности, формулу вы можете увидеть на экране, где n — это количество данных,
k — это количество кластеров, а d — это размерность нашего пространства признаков.
Требования времени k-средних линейно по количеству данных.
И формулу вы можете увидеть также на экране, где I — это количество итераций,
необходимых для сходимости.
И поскольку наше это количество итераций обычно мало,
может быть безопасно привязано, поскольку большинство изменений обычно происходят
только в первых изменениях назначения центров кластеров.
Поэтому количество итераций сильно меньше количества данных.
Таким образом, можно сделать вывод, что алгоритм K-means является
относительно масштабируемым и эффективным при обработке больших наборов данных.
Алгоритм K-means работает достаточно хорошо, если наши кластеры соответствуют
некой определенной модели, а именно: все эти кластеры имеют выпуклую форму,
то есть точки данных в кластере сосредоточены вокруг этого кластера; и
также распространение либо дисперсия кластеров похожи,
то есть каждая точка данных принадлежит ближайшему кластеру.
Если какой-либо из этих принципов нарушается,
то локальные минимумы алгоритма k-средних будут противоречивыми.
Поэтому на графике вы можете увидеть, как будет работать данный алгоритм,
если кластеры у нас не имеют выпуклую, или сферическую, форму.
Отметим слабые места данного алгоритма, а именно: если кластеры у нас разного
размера, то вы можете увидеть пример на графике работы данного алгоритма.
Также кластеры разной плотности не всегда хорошо идентифицируются данным методом.
Помимо этого, этот алгоритм имеет проблемы с обработкой так называемых
зашумленных данных, или данных с выбросами.
Ну и последним нетривиальным случаем для него является
определение количества кластеров, то есть неправильное количество кластеров у
нас может привести к неправильному определению структуры данных.
Алгоритм k-средних имеет некоторые недостатки.
В частности, производительность данного алгоритма зависит от инициализации
начальных центров.
Поэтому важной проблемой является возможность выбора хороших начальных
центров.
Некоторые обычно используемые методы для первоначального выбора центров включают
метод Форджи, в котором случайным образом выбираются k начальных центров
из наблюдений, в таком случае случайные кластеры не имеют внутренней однородности.
Также популярным является метод случайного разбиения, в котором каждое
наблюдение просто случайным образом приписывается к одному из кластеров,
а затем определяются начальные центроиды.
Также интересен метод Максимина,
который произвольно выбирает первый центр кластеров,
а каждый последующий i-тый центр кластера выбирается как точка,
которая имеет наибольшее минимальное расстояние до ранее выбранных центров.
Эти методы легко понять и реализовать.
Однако на практике, хоть они и имеют низкую вычислительную сложность,
эти методы не обеспечивают значительную экономию времени,
поскольку они часто приводят к медленной сходимости алгоритма k-средних.
Поэтому во многих приложениях желательным
является использование таких методов, как Var-Part или метод главных компонент,
для определения начальных центров кластеров в этом алгоритме.
Алгоритм кластеризации K-means требует предварительно задать количество
кластеров.
Таким образом, кластеризация может оказаться неадекватной в том случае,
если изначально неверно задано число кластеров.
Стандартная рекомендация: провести кластеризацию при различных значениях
параметра k, и выбрать то, при котором достигается резкое улучшения
качества кластеризации по заданному функционалу.
С такими методами, как метод «локтя», метод среднего силуэта или статистика
отклонений, вы можете ознакомиться в материалах для самостоятельного изучения.
Блеканов Иван Станиславовичдоцент
Севрюков Сергей Юрьевичстарший преподаватель
Просолупов Евгений Викторовичк.ф.-м.н., доцент
Коротков Павел Алексеевичстарший преподаватель
Мишенин Алексей Николаевичстарший преподаватель
Утешев Алексей Юрьевичпрофессор
Вольф Дмитрий Александровичассистент
Малютин Евгений Алексеевичассистент
Камалов Михаил ВалерьевичАспирант
