k-means

Поделись знанием:
Перейти к: навигация, поиск

k-means (метод k-средних) — наиболее популярный метод кластеризации. Был изобретён в 1950-х годах математиком Гуго Штейнгаузом[1] и почти одновременно Стюартом Ллойдом[2]. Особую популярность приобрёл после работы Маккуина[3].

Действие алгоритма таково, что он стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров:

<math>V = \sum_{i=1}^{k} \sum_{x_j \in S_i} (x_j - \mu_i)^2 </math>

где <math>k</math> — число кластеров, <math>S_i</math> — полученные кластеры, <math>i = 1, 2, \dots, k</math> и <math>\mu_i</math> — центры масс векторов <math>x_j \in S_i</math>.

По аналогии с методом главных компонент центры кластеров называются также главными точками, а сам метод называется методом главных точек[4] и включается в общую теорию главных объектов, обеспечивающих наилучшую аппроксимацию данных[5].





Алгоритм

Алгоритм представляет собой версию EM-алгоритма, применяемого также для разделения смеси гауссиан. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k.

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

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

Как показали Дэвид Артур и Сергей Васильвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна <math>2^{\Omega(\sqrt{n})}</math>.[6]

Демонстрация алгоритма

Действие алгоритма в двумерном случае. Начальные точки выбраны случайно.

Проблемы k-means

  • Не гарантируется достижение глобального минимума суммарного квадратичного отклонения V, а только одного из локальных минимумов.
  • Результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен.
  • Число кластеров надо знать заранее.

Расширения и вариации

Широко известна и используется нейросетевая реализация K-means — сети векторного квантования сигналов (одна из версий нейронных сетей Кохонена).

Существует расширение k-means++, которое направлено на оптимальный выбор начальных значений центров кластеров.


Применение для задач глубокого обучения и машинного зрения

В алгоритмах глубокого обучения метод k-средних иногда применяют не по прямому назначению (классификация разбивкой на кластеры), а для создания так называемых фильтров (ядер свёртки, словарей). Например, для распознавания изображений в алгоритм k-средних подают небольшие случайные кусочки изображений обучающей выборки, допустим, размером 16х16 в виде линейного вектора, каждый элемент которого кодирует яркость своей точки. Количество кластеров k задается большим, например 256. Обученный метод k-средних при определенных условиях вырабатывает при этом центры кластеров (центроиды), которые представляют собой удобные базисы, на которые можно разложить любое входное изображение. Такие "обученные" центроиды в дальнейшем используют в качестве фильтров, например для свёрточной нейронной сети в качестве ядер свёртки или других аналогичных систем машинного зрения[8]. Таким образом осуществляется обучение без учителя при помощи метода k-средних.

Напишите отзыв о статье "K-means"

Ссылки

  1. Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.
  2. Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.
  3. MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.
  4. Flury B. (1990). Principal points. Biometrika, 77, 33-41.
  5. Gorban A.N., Zinovyev A.Y. (2009). [arxiv.org/pdf/0809.0490v2 Principal Graphs and Manifolds], Ch. 2 in: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods, and Techniques, Emilio Soria Olivas et al. (eds), IGI Global, Hershey, PA, USA, pp. 28-59.
  6. David Arthur & Sergei Vassilvitskii (2006). "[www.cs.duke.edu/courses/spring07/cps296.2/papers/kMeans-socg.pdf How Slow is the k-means Method?]". Proceedings of the 2006 Symposium on Computational Geometry (SoCG). 
  7. E.M. Mirkes, [www.math.le.ac.uk/people/ag153/homepage/KmeansKmedoids/Kmeans_Kmedoids.html K-means and K-medoids applet]. University of Leicester, 2011.
  8. Adam Coates and Andrew Y. Ng. [www.cs.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf Learning Feature Representations with K-means], Stanford University, 2012

Демонстрация и визуализация

  • Дж. Ту, Р. Гонсалес "Принципы распознавания образов", Издательство "Мир", Москва 1978, стр. 109-112 (описание алгоритма с численным примером).
  • [www.math.le.ac.uk/people/ag153/homepage/KmeansKmedoids/Kmeans_Kmedoids.html K-means and K-medoids] (апплет, демонстрирующий работу алгоритма и позволяющий исследовать и сравнивать два метода), Е. Миркес и [www2.le.ac.uk/ University of Leicester]
  • [home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html Интерактивный апплет, демонстрирующий работу алгоритма]


Отрывок, характеризующий K-means

Но Ростов вырвал свою руку и с такою злобой, как будто Денисов был величайший враг его, прямо и твердо устремил на него глаза.
– Ты понимаешь ли, что говоришь? – сказал он дрожащим голосом, – кроме меня никого не было в комнате. Стало быть, ежели не то, так…
Он не мог договорить и выбежал из комнаты.
– Ах, чог'т с тобой и со всеми, – были последние слова, которые слышал Ростов.
Ростов пришел на квартиру Телянина.
– Барина дома нет, в штаб уехали, – сказал ему денщик Телянина. – Или что случилось? – прибавил денщик, удивляясь на расстроенное лицо юнкера.
– Нет, ничего.
– Немного не застали, – сказал денщик.
Штаб находился в трех верстах от Зальценека. Ростов, не заходя домой, взял лошадь и поехал в штаб. В деревне, занимаемой штабом, был трактир, посещаемый офицерами. Ростов приехал в трактир; у крыльца он увидал лошадь Телянина.
Во второй комнате трактира сидел поручик за блюдом сосисок и бутылкою вина.
– А, и вы заехали, юноша, – сказал он, улыбаясь и высоко поднимая брови.
– Да, – сказал Ростов, как будто выговорить это слово стоило большого труда, и сел за соседний стол.
Оба молчали; в комнате сидели два немца и один русский офицер. Все молчали, и слышались звуки ножей о тарелки и чавканье поручика. Когда Телянин кончил завтрак, он вынул из кармана двойной кошелек, изогнутыми кверху маленькими белыми пальцами раздвинул кольца, достал золотой и, приподняв брови, отдал деньги слуге.
– Пожалуйста, поскорее, – сказал он.
Золотой был новый. Ростов встал и подошел к Телянину.
– Позвольте посмотреть мне кошелек, – сказал он тихим, чуть слышным голосом.
С бегающими глазами, но всё поднятыми бровями Телянин подал кошелек.
– Да, хорошенький кошелек… Да… да… – сказал он и вдруг побледнел. – Посмотрите, юноша, – прибавил он.
Ростов взял в руки кошелек и посмотрел и на него, и на деньги, которые были в нем, и на Телянина. Поручик оглядывался кругом, по своей привычке и, казалось, вдруг стал очень весел.
– Коли будем в Вене, всё там оставлю, а теперь и девать некуда в этих дрянных городишках, – сказал он. – Ну, давайте, юноша, я пойду.
Ростов молчал.
– А вы что ж? тоже позавтракать? Порядочно кормят, – продолжал Телянин. – Давайте же.
Он протянул руку и взялся за кошелек. Ростов выпустил его. Телянин взял кошелек и стал опускать его в карман рейтуз, и брови его небрежно поднялись, а рот слегка раскрылся, как будто он говорил: «да, да, кладу в карман свой кошелек, и это очень просто, и никому до этого дела нет».
– Ну, что, юноша? – сказал он, вздохнув и из под приподнятых бровей взглянув в глаза Ростова. Какой то свет глаз с быстротою электрической искры перебежал из глаз Телянина в глаза Ростова и обратно, обратно и обратно, всё в одно мгновение.
– Подите сюда, – проговорил Ростов, хватая Телянина за руку. Он почти притащил его к окну. – Это деньги Денисова, вы их взяли… – прошептал он ему над ухом.
– Что?… Что?… Как вы смеете? Что?… – проговорил Телянин.
Но эти слова звучали жалобным, отчаянным криком и мольбой о прощении. Как только Ростов услыхал этот звук голоса, с души его свалился огромный камень сомнения. Он почувствовал радость и в то же мгновение ему стало жалко несчастного, стоявшего перед ним человека; но надо было до конца довести начатое дело.
– Здесь люди Бог знает что могут подумать, – бормотал Телянин, схватывая фуражку и направляясь в небольшую пустую комнату, – надо объясниться…
– Я это знаю, и я это докажу, – сказал Ростов.
– Я…
Испуганное, бледное лицо Телянина начало дрожать всеми мускулами; глаза всё так же бегали, но где то внизу, не поднимаясь до лица Ростова, и послышались всхлипыванья.
– Граф!… не губите молодого человека… вот эти несчастные деньги, возьмите их… – Он бросил их на стол. – У меня отец старик, мать!…
Ростов взял деньги, избегая взгляда Телянина, и, не говоря ни слова, пошел из комнаты. Но у двери он остановился и вернулся назад. – Боже мой, – сказал он со слезами на глазах, – как вы могли это сделать?
– Граф, – сказал Телянин, приближаясь к юнкеру.
– Не трогайте меня, – проговорил Ростов, отстраняясь. – Ежели вам нужда, возьмите эти деньги. – Он швырнул ему кошелек и выбежал из трактира.


Вечером того же дня на квартире Денисова шел оживленный разговор офицеров эскадрона.
– А я говорю вам, Ростов, что вам надо извиниться перед полковым командиром, – говорил, обращаясь к пунцово красному, взволнованному Ростову, высокий штаб ротмистр, с седеющими волосами, огромными усами и крупными чертами морщинистого лица.
Штаб ротмистр Кирстен был два раза разжалован в солдаты зa дела чести и два раза выслуживался.
– Я никому не позволю себе говорить, что я лгу! – вскрикнул Ростов. – Он сказал мне, что я лгу, а я сказал ему, что он лжет. Так с тем и останется. На дежурство может меня назначать хоть каждый день и под арест сажать, а извиняться меня никто не заставит, потому что ежели он, как полковой командир, считает недостойным себя дать мне удовлетворение, так…
– Да вы постойте, батюшка; вы послушайте меня, – перебил штаб ротмистр своим басистым голосом, спокойно разглаживая свои длинные усы. – Вы при других офицерах говорите полковому командиру, что офицер украл…
– Я не виноват, что разговор зашел при других офицерах. Может быть, не надо было говорить при них, да я не дипломат. Я затем в гусары и пошел, думал, что здесь не нужно тонкостей, а он мне говорит, что я лгу… так пусть даст мне удовлетворение…
– Это всё хорошо, никто не думает, что вы трус, да не в том дело. Спросите у Денисова, похоже это на что нибудь, чтобы юнкер требовал удовлетворения у полкового командира?
Денисов, закусив ус, с мрачным видом слушал разговор, видимо не желая вступаться в него. На вопрос штаб ротмистра он отрицательно покачал головой.