K-Means

https://www.coursera.org/course/ml

После линейной регрессии была логистическая регрессия. А потом начались нейросети — Neural Networks. Потом нас учили правильно применять изученные алгоритмы (Advice for Applying Machine Learning). А потом нам рассказали про Support Vector Machines (SVMs) и Kernels.

А потом была неделя посвященная темам Clustering (K-Means) и Dimensionality Reduction (PCA). Тему снижения размерности мы отложим на потом. Сегодня поглядим на алгоритм кластеризации под названием K-Means.

Clustering (кластеризация) это класс проблем из раздела Unsupervised Learning, в отличие от рассмотренных ранее, относящихся к Supervised Learning. Принципиальная разница между этими двумя разделами заключается в том, что в проблемах Supervised Learning данные для обучения всегда содержат ответ (метку, label). Нет, так неясно. Давайте так: в тренировочном наборе данных для обучения распознаванию рукописных цифр всегда есть значение цифры изображенной на распознаваемой картинке. Если еще проще, то машина строит догадку – «это цифра 3», а супервайзер бьет ее по рукам линейкой и рявкает – «дура, это цифра 5», после чего машина корректирует коэффициенты в вычислениях, чтобы следующий раз угадать точнее.

А вот в проблемах Unsupervised Learning никаких готовых ответов нет. Есть только наборы данных и их надо как-то структурировать. Например разложить по кучкам согласно некоей общности характеристик (features). Эти кучки и будут кластеры, а процесс отнесения записей данных в тот или иной кластер — кластеризация.

Так как же делается кластеризация? Один из наиболее употребимых алгоритмов называется «K-Means Algorithm».

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

Теперь машина итеративно, до схождения (или ограничения по количеству циклов/времени) делает два шага:

1. Распределяет точки по кластерам (двум, в примере) по принципу близости к центроиду. Cluster Assignment Step.

2. Двигает центроиды кластеров (точки по плоскости) в центр/среднее положение в кластере (облаке точек). Move Centroid Step.

Всё, вот и весь алгоритм.

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

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

Теперь вопрос — а как назначить оптимальное количество кластеров? Ответ очевиден — посчитать Cost Function для разного количества кластеров, построить график и заценить, где на графике происходит резкий (относительно) переход. Это будет метод локтя (Elbow Method).

А вообще-то, обычно количество кластеров назначают вручную, исходя из предполагаемого применения результата. Например разбиение размеров футболок по группам (S, M, L, XL) или (S, SM, M, L, XL, XXL) — что лучше для бизнеса продажи футболок — 4 размера для упрощения производства или 6 размеров для более точного подгона одежды по фигуре?

Что любопытно, в практическом задании мы применяли кластеризацию (K-Means) для сжатия картинок. Уменьшалась цветовая палитра (до 16 цветов) и, как итог, размер файла изображения. Приблизительно в шесть (6) раз.

Фактически, пиксели группировались в 16 кластеров в контексте похожести/близости цвета, после чего группам пикселов присваивался некий «средний» для группы цвет.

Получилось забавно.

 

original post http://vasnake.blogspot.com/2014/06/k-means.html