Наука о данных включает большой спектр подходов и методов сбора, обработки, анализа и визуализации массивов данных любого размера. Отдельным практически важным направлением данной науки является работа с большими данными с помощью новых принципов математического и вычислительного моделирования, когда классические методы перестают работать ввиду невозможности их масштабирования. Настоящий курс призван помочь обучающемуся изучить основы предметной области через постановку и решение типичных задач, с которыми исследователь в области науки о данных может столкнуться в своей работе. Чтобы научить слушателя решать такие задачи, авторы курса предоставляют обучающемуся необходимый теоретический минимум и показывают, как пользоваться инструментальной базой на практике.
Алгоритм K-means
Loading...
來自 Saint Petersburg State University 的課程
Введение в науку о данных (An Introduction to Data Science)
26 個評分
從本節課中
Машинное обучение: обучение без учителя.
與講師見面
Блеканов Иван Станиславовичдоцент
Кафедра технологии программирования
Севрюков Сергей Юрьевичстарший преподаватель
кафедра Технологии программирования
Просолупов Евгений Викторовичк.ф.-м.н., доцент
кафедра Технологии программирования
Коротков Павел Алексеевичстарший преподаватель
кафедра Технологии программирования
Мишенин Алексей Николаевичстарший преподаватель
кафедра Технологии программирования
Утешев Алексей Юрьевичпрофессор
кафедра управления медико-биологическими системами
Вольф Дмитрий Александровичассистент
кафедра Технологии Программирования
Малютин Евгений Алексеевичассистент
кафедра Технологии Программирования
Камалов Михаил ВалерьевичАспирант
Кафедра Технологии программирования
[МУЗЫКА]
[МУЗЫКА]
Кластеризация 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, и выбрать то, при котором достигается резкое улучшения
качества кластеризации по заданному функционалу.
С такими методами, как метод «локтя», метод среднего силуэта или статистика
отклонений, вы можете ознакомиться в материалах для самостоятельного изучения.
