K-означает ++ - K-means++

В сбор данных, k-значит ++[1][2] представляет собой алгоритм выбора начальных значений (или «семян») для k-средства кластеризации алгоритм. Он был предложен в 2007 году Дэвидом Артуром и Сергеем Васильвицким в качестве приближенного алгоритма для NP-жесткий k-средна проблема - способ избежать иногда плохой кластеризации, обнаруживаемой стандартным k- означает алгоритм. Он аналогичен первому из трех методов посева, предложенных в самостоятельной работе в 2006 г.[3] Рафаил Островский, Юваль Рабани, Леонард Шульман и Чайтанья Свами. (Распределение первого семени другое.)

Фон

В k- означает, что проблема состоит в том, чтобы найти центры кластеров, которые минимизируют внутриклассовую дисперсию, то есть сумму квадратов расстояний от каждой кластеризованной точки данных до центра кластера (ближайшего к нему центра). k- означает, что задача для произвольного ввода NP-сложна,[4] стандартный подход к поиску приближенного решения (часто называемый Алгоритм Ллойда или k-смысловой алгоритм) широко используется и часто быстро находит разумные решения.

Тем не менее k-средний алгоритм имеет как минимум два основных теоретических недостатка:

  • Во-первых, было показано, что время работы алгоритма в наихудшем случае является суперполиномиальным по размеру входных данных.[5]
  • Во-вторых, найденное приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией.

В kАлгоритм -means ++ устраняет второе из этих препятствий, определяя процедуру инициализации центров кластеров перед тем, как приступить к стандартной k- означает итерации оптимизации. k-значит ++ инициализацию, алгоритм гарантированно найдет решение, которое равно O (logk) конкурентоспособны к оптимальным k-значит решение.

Пример неоптимальной кластеризации

Чтобы проиллюстрировать потенциал k- означает, что алгоритм работает произвольно плохо по отношению к целевой функции минимизации суммы квадратов расстояний от точек кластера до центроида назначенных им кластеров, рассмотрим пример четырех точек в р2 которые образуют выровненный по оси прямоугольник, ширина которого больше его высоты.

Если k = 2, а два начальных центра кластера лежат в средних точках верхнего и нижнего сегментов прямоугольника, образованного четырьмя точками данных, k- означает, что алгоритм сходится немедленно, без перемещения этих центров кластера. Следовательно, две нижние точки данных сгруппированы вместе, а две точки данных, образующие верхнюю часть прямоугольника, сгруппированы вместе - субоптимальная кластеризация, поскольку ширина прямоугольника больше, чем его высота.

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

Улучшенный алгоритм инициализации

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

Точный алгоритм выглядит следующим образом:

  1. Выберите один центр равномерно случайным образом среди точек данных.
  2. Для каждой точки данных Икс еще не выбрано, вычислить D (Икс), расстояние между Икс и ближайший центр, который уже выбран.
  3. Случайным образом выберите одну новую точку данных в качестве нового центра, используя взвешенное распределение вероятностей, где точка Икс выбирается с вероятностью, пропорциональной D (Икс)2.
  4. Повторяйте шаги 2 и 3, пока k центры выбраны.
  5. Теперь, когда исходные центры выбраны, продолжайте использовать стандартные k-средства кластеризации.

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

Кроме того, авторы вычисляют коэффициент приближения для своего алгоритма. В k-means ++ алгоритм гарантирует коэффициент аппроксимации O (logk) в ожидании (по случайности алгоритма), где - количество используемых кластеров. Это в отличие от ванили k-средство, которое может генерировать кластеризацию произвольно хуже оптимальной.[6]Обобщение характеристик k-средних ++ по отношению к любому произвольному расстоянию представлено в.[7]

Приложения

В kПодход -means ++ применяется с момента его первоначального предложения. В обзоре Шиндлера:[8] который включает в себя множество типов алгоритмов кластеризации, считается, что этот метод успешно преодолевает некоторые проблемы, связанные с другими способами определения начальных центров кластеров для k- означает кластеризацию. Ли и др.[9] сообщить о применении k-средства ++ для создания географического кластера фотографий на основе информации о широте и долготе, прикрепленной к фотографиям. О приложении к финансовой диверсификации сообщают Ховард и Йохансен.[10] Другая поддержка метода и текущее обсуждение также доступны в Интернете.[11] Поскольку для инициализации k-means ++ требуется k передач данных, она не очень хорошо масштабируется для больших наборов данных. Bahman Bahmani et al. предложили масштабируемый вариант k-means ++, называемый k-means || который обеспечивает те же теоретические гарантии и при этом хорошо масштабируется.[12]

Программного обеспечения

  • Математика Apache Commons содержит k-среднее
  • ELKI Инфраструктура интеллектуального анализа данных содержит несколько вариантов k-средних, включая k-means ++ для заполнения.
  • MATLAB имеет реализацию K-средних, которая по умолчанию использует k-means ++ для заполнения.
  • OpenCV включает k-среднее значение для значений пикселей.
  • пикластеризация предоставляет реализацию K-Means ++ для инициализации начальных центров для K-средних, X-средних, EMA и т. д.
  • р включает k-средства, а пакет "flexclust" может выполнять k-средства ++
  • Scikit-Learn имеет реализацию K-средних, которая по умолчанию использует k-means ++.
  • Weka содержит k-средство (с необязательным k-средним ++) и кластеризацию x-средних.

Рекомендации

  1. ^ Arthur, D .; Васильвицкий С. (2007). "k-means ++: преимущества тщательного посева » (PDF). Материалы восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики Филадельфия, Пенсильвания, США. С. 1027–1035.
  2. ^ http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf Слайды для презентации метода Артура Д. и Васильвицкого С.
  3. ^ Островский, Р .; Rabani, Y .; Schulman, L.J .; Свами, К. (2006). «Эффективность методов Ллойда для проблемы k-средних». Материалы 47-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS'06). IEEE. С. 165–174.
  4. ^ Drineas, P .; Frieze, A .; Kannan, R .; Vempala, S .; Винай, В. (2004). «Кластеризация больших графов с помощью разложения по сингулярным значениям». Машинное обучение. 56 (1–3): 9–33. Дои:10.1023 / B: MACH.0000033113.59016.96.
  5. ^ Arthur, D .; Васильвицкий, С. (2006), «Как медленно k-смысл метод? ", ACM Нью-Йорк, Нью-Йорк, США, стр. 144–153
  6. ^ Канунго, Т .; Mount, D .; Нетаньяху, Н .; Пятко, С.; Silverman, R .; Ву, А. (2004), "Алгоритм аппроксимации локального поиска для k-Кластеризация средств » (PDF), Вычислительная геометрия: теория и приложения, 28 (2–3): 89–112, Дои:10.1016 / j.comgeo.2004.03.003, заархивировано из оригинал (PDF) на 2006-02-09.
  7. ^ Нильсен, Франк; Нок, Ричард (2013), Полные расхождения Дженсена: определение, свойства и кластеризация k-средних ++, arXiv:1309.7109, Bibcode:2013arXiv1309.7109N.
  8. ^ https://web.archive.org/web/20110927100642/http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf Аппроксимационные алгоритмы для метрики. k-MedianProblem
  9. ^ http://sir-lab.usc.edu/publications/2008-ICWSM2LEES.pdf В архиве 2016-03-03 в Wayback Machine Выявление взаимосвязей между тегами и геотегами, 2007 г.
  10. ^ http://www.cse.ohio-state.edu/~johansek/clustering.pdf[постоянная мертвая ссылка ] Методы кластеризации для финансовой диверсификации, март 2009 г.
  11. ^ http://lingpipe-blog.com/2009/03/23/arthur-vassilvitskii-2007-kmeans-the-advantages-of-careful-seeding/ Блог Lingpipe
  12. ^ Б. Бахмани, Б. Мозли, А. Ваттани, Р. Кумар, С. Васильвицкий «Масштабируемое K-средство ++» 2012 Труды фонда VLDB.