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"
Ссылки
- ↑ Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.
- ↑ Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.
- ↑ 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.
- ↑ Flury B. (1990). Principal points. Biometrika, 77, 33-41.
- ↑ 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.
- ↑ 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).
- ↑ 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.
- ↑ 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 Интерактивный апплет, демонстрирующий работу алгоритма]
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий K-means
Но Ростов вырвал свою руку и с такою злобой, как будто Денисов был величайший враг его, прямо и твердо устремил на него глаза.– Ты понимаешь ли, что говоришь? – сказал он дрожащим голосом, – кроме меня никого не было в комнате. Стало быть, ежели не то, так…
Он не мог договорить и выбежал из комнаты.
– Ах, чог'т с тобой и со всеми, – были последние слова, которые слышал Ростов.
Ростов пришел на квартиру Телянина.
– Барина дома нет, в штаб уехали, – сказал ему денщик Телянина. – Или что случилось? – прибавил денщик, удивляясь на расстроенное лицо юнкера.
– Нет, ничего.
– Немного не застали, – сказал денщик.
Штаб находился в трех верстах от Зальценека. Ростов, не заходя домой, взял лошадь и поехал в штаб. В деревне, занимаемой штабом, был трактир, посещаемый офицерами. Ростов приехал в трактир; у крыльца он увидал лошадь Телянина.
Во второй комнате трактира сидел поручик за блюдом сосисок и бутылкою вина.
– А, и вы заехали, юноша, – сказал он, улыбаясь и высоко поднимая брови.
– Да, – сказал Ростов, как будто выговорить это слово стоило большого труда, и сел за соседний стол.
Оба молчали; в комнате сидели два немца и один русский офицер. Все молчали, и слышались звуки ножей о тарелки и чавканье поручика. Когда Телянин кончил завтрак, он вынул из кармана двойной кошелек, изогнутыми кверху маленькими белыми пальцами раздвинул кольца, достал золотой и, приподняв брови, отдал деньги слуге.
– Пожалуйста, поскорее, – сказал он.
Золотой был новый. Ростов встал и подошел к Телянину.
– Позвольте посмотреть мне кошелек, – сказал он тихим, чуть слышным голосом.
С бегающими глазами, но всё поднятыми бровями Телянин подал кошелек.
– Да, хорошенький кошелек… Да… да… – сказал он и вдруг побледнел. – Посмотрите, юноша, – прибавил он.
Ростов взял в руки кошелек и посмотрел и на него, и на деньги, которые были в нем, и на Телянина. Поручик оглядывался кругом, по своей привычке и, казалось, вдруг стал очень весел.
– Коли будем в Вене, всё там оставлю, а теперь и девать некуда в этих дрянных городишках, – сказал он. – Ну, давайте, юноша, я пойду.
Ростов молчал.
– А вы что ж? тоже позавтракать? Порядочно кормят, – продолжал Телянин. – Давайте же.
Он протянул руку и взялся за кошелек. Ростов выпустил его. Телянин взял кошелек и стал опускать его в карман рейтуз, и брови его небрежно поднялись, а рот слегка раскрылся, как будто он говорил: «да, да, кладу в карман свой кошелек, и это очень просто, и никому до этого дела нет».
– Ну, что, юноша? – сказал он, вздохнув и из под приподнятых бровей взглянув в глаза Ростова. Какой то свет глаз с быстротою электрической искры перебежал из глаз Телянина в глаза Ростова и обратно, обратно и обратно, всё в одно мгновение.
– Подите сюда, – проговорил Ростов, хватая Телянина за руку. Он почти притащил его к окну. – Это деньги Денисова, вы их взяли… – прошептал он ему над ухом.
– Что?… Что?… Как вы смеете? Что?… – проговорил Телянин.
Но эти слова звучали жалобным, отчаянным криком и мольбой о прощении. Как только Ростов услыхал этот звук голоса, с души его свалился огромный камень сомнения. Он почувствовал радость и в то же мгновение ему стало жалко несчастного, стоявшего перед ним человека; но надо было до конца довести начатое дело.
– Здесь люди Бог знает что могут подумать, – бормотал Телянин, схватывая фуражку и направляясь в небольшую пустую комнату, – надо объясниться…
– Я это знаю, и я это докажу, – сказал Ростов.
– Я…
Испуганное, бледное лицо Телянина начало дрожать всеми мускулами; глаза всё так же бегали, но где то внизу, не поднимаясь до лица Ростова, и послышались всхлипыванья.
– Граф!… не губите молодого человека… вот эти несчастные деньги, возьмите их… – Он бросил их на стол. – У меня отец старик, мать!…
Ростов взял деньги, избегая взгляда Телянина, и, не говоря ни слова, пошел из комнаты. Но у двери он остановился и вернулся назад. – Боже мой, – сказал он со слезами на глазах, – как вы могли это сделать?
– Граф, – сказал Телянин, приближаясь к юнкеру.
– Не трогайте меня, – проговорил Ростов, отстраняясь. – Ежели вам нужда, возьмите эти деньги. – Он швырнул ему кошелек и выбежал из трактира.
Вечером того же дня на квартире Денисова шел оживленный разговор офицеров эскадрона.
– А я говорю вам, Ростов, что вам надо извиниться перед полковым командиром, – говорил, обращаясь к пунцово красному, взволнованному Ростову, высокий штаб ротмистр, с седеющими волосами, огромными усами и крупными чертами морщинистого лица.
Штаб ротмистр Кирстен был два раза разжалован в солдаты зa дела чести и два раза выслуживался.
– Я никому не позволю себе говорить, что я лгу! – вскрикнул Ростов. – Он сказал мне, что я лгу, а я сказал ему, что он лжет. Так с тем и останется. На дежурство может меня назначать хоть каждый день и под арест сажать, а извиняться меня никто не заставит, потому что ежели он, как полковой командир, считает недостойным себя дать мне удовлетворение, так…
– Да вы постойте, батюшка; вы послушайте меня, – перебил штаб ротмистр своим басистым голосом, спокойно разглаживая свои длинные усы. – Вы при других офицерах говорите полковому командиру, что офицер украл…
– Я не виноват, что разговор зашел при других офицерах. Может быть, не надо было говорить при них, да я не дипломат. Я затем в гусары и пошел, думал, что здесь не нужно тонкостей, а он мне говорит, что я лгу… так пусть даст мне удовлетворение…
– Это всё хорошо, никто не думает, что вы трус, да не в том дело. Спросите у Денисова, похоже это на что нибудь, чтобы юнкер требовал удовлетворения у полкового командира?
Денисов, закусив ус, с мрачным видом слушал разговор, видимо не желая вступаться в него. На вопрос штаб ротмистра он отрицательно покачал головой.