k -означает++

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

Фон

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

Accord.NET содержит реализации C# для режимов k -means, k -means++ и k -mode.
ALGLIB содержит распараллеленные реализации C++ и C# для k -means и k -means++.
Apache Commons Math содержит k-means++
ELKI содержит несколько вариантов k-средних, включая k-means++ для заполнения. Платформа интеллектуального анализа данных
MATLAB имеет реализацию K-Means, которая по умолчанию использует k-means++ для заполнения.
OpenCV содержит реализацию K-средних на C++ и Python (с дополнительной инициализацией начального числа k-средних).
Orange включает виджет пользовательского интерфейса k-means++ и поддержку API.
R включает k-средние, а пакет «flexclust» может использовать k-means++.
scikit-learn имеет реализацию K-Means, которая по умолчанию использует k-means++.
Weka содержит k-средние (с дополнительным k-means++) и кластеризацию x-средних.

Ссылки

^ Артур, Д.; Васильвицкий, С. (2007). « k -means++: преимущества тщательного посева» (PDF) . Материалы восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики Филадельфии, Пенсильвания, США. стр. 1027–1035.
^ http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf Слайды для презентации метода Артура Д. и Васильвицкого С.
^ Островский Р.; Рабани, Ю.; Шульман, LJ; Свами, К. (2006). «Эффективность методов типа Ллойда для проблемы k-средних». Материалы 47-го ежегодного симпозиума IEEE по основам информатики (FOCS'06) . IEEE. стр. 165–174.
^ Дриней, П.; Фриз, А.; Каннан, Р.; Вемпала, С.; Винай, В. (2004). «Кластеризация больших графов с помощью разложения по сингулярным значениям» . Машинное обучение . 56 (1–3): 9–33. дои : 10.1023/B:MACH.0000033113.59016.96 .
^ Артур, Д.; Васильвицкий, С. (2006). «Насколько медленным является метод k -средних?». Материалы двадцать второго ежегодного симпозиума по вычислительной геометрии . ACM Нью-Йорк, штат Нью-Йорк, США . стр. 144–153.
^ Канунго, Т.; Маунт, Д.; Нетаньяху, Н.; Пятко, К. ; Сильверман, Р.; Ву, А. (2004), «Алгоритм аппроксимации локального поиска для k кластеризации -средних», Вычислительная геометрия: теория и приложения , 28 (2–3): 89–112, doi : 10.1016/j.comgeo.2004.03.003 .
^ Нильсен, Франк; Нок, Ричард (2013), «Общие дивергенции Дженсена: определение, свойства и кластеризация», Международная конференция IEEE по акустике, речи и обработке сигналов (ICASSP) , 2015 г., стр. 2016–2020, arXiv : 1309.7109 , Bibcode : 2013arXiv1309.7109N , дои : 10.1109/ICASSP.2015.7178324 , ISBN 978-1-4673-6997-8 , S2CID 463728 .
^ https://web.archive.org/web/20110927100642/http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf Алгоритмы аппроксимации метрики k -медианы Проблема
^ http://sir-lab.usc.edu/publications/2008-ICWSM2LEES.pdf. Архивировано 3 марта 2016 г. на сайте Wayback Machine, обнаруживающем взаимосвязи между тегами и геотегами, 2007 г.
^ http://www.cse.ohio-state.edu/~johansek/clustering.pdf ^{[ постоянная мертвая ссылка ]} Методы кластеризации для финансовой диверсификации, март 2009 г.
^ http://lingpipe-blog.com/2009/03/23/arthur-vassilvitski-2007-kmeans-the-advantages-of-careful-seeding/ Блог Lingpipe
^ Б. Бахмани, Б. Мозли, А. Ваттани, Р. Кумар, С. Васильвицкий «Масштабируемые K-средства ++» , 2012 г., Труды Фонда VLDB.

[1] Артур, Д.; Васильвицкий, С. (2007). « k -means++: преимущества тщательного посева» (PDF) . Материалы восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики Филадельфии, Пенсильвания, США. стр. 1027–1035.

[2] ttp://theory.stanford.edu/~sergei/slides/BATS-Means.pdf Слайды для презентации метода Артура Д. и Васильвицкого С.

[3] Островский Р.; Рабани, Ю.; Шульман, LJ; Свами, К. (2006). «Эффективность методов типа Ллойда для проблемы k-средних». Материалы 47-го ежегодного симпозиума IEEE по основам информатики (FOCS'06) . IEEE. стр. 165–174.

[4] Дриней, П.; Фриз, А.; Каннан, Р.; Вемпала, С.; Винай, В. (2004). «Кластеризация больших графов с помощью разложения по сингулярным значениям» . Машинное обучение . 56 (1–3): 9–33. дои : 10.1023/B:MACH.0000033113.59016.96 .

[5] Артур, Д.; Васильвицкий, С. (2006). «Насколько медленным является метод k -средних?». Материалы двадцать второго ежегодного симпозиума по вычислительной геометрии . ACM Нью-Йорк, штат Нью-Йорк, США . стр. 144–153.

[kanungo-6] Канунго, Т.; Маунт, Д.; Нетаньяху, Н.; Пятко, К. ; Сильверман, Р.; Ву, А. (2004), «Алгоритм аппроксимации локального поиска для k кластеризации -средних», Вычислительная геометрия: теория и приложения , 28 (2–3): 89–112, doi : 10.1016/j.comgeo.2004.03.003 .

[nn-7] Нильсен, Франк; Нок, Ричард (2013), «Общие дивергенции Дженсена: определение, свойства и кластеризация», Международная конференция IEEE по акустике, речи и обработке сигналов (ICASSP) , 2015 г., стр. 2016–2020, arXiv : 1309.7109 , Bibcode : 2013arXiv1309.7109N , дои : 10.1109/ICASSP.2015.7178324 , ISBN 978-1-4673-6997-8 , S2CID 463728 .

[8] ttps://web.archive.org/web/20110927100642/http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf Алгоритмы аппроксимации метрики k -медианы Проблема

[9] ttp://sir-lab.usc.edu/publications/2008-ICWSM2LEES.pdf. Архивировано 3 марта 2016 г. на сайте Wayback Machine, обнаруживающем взаимосвязи между тегами и геотегами, 2007 г.

[10] ttp://www.cse.ohio-state.edu/~johansek/clustering.pdf ^{[ постоянная мертвая ссылка ]} Методы кластеризации для финансовой диверсификации, март 2009 г.

[11] ttp://lingpipe-blog.com/2009/03/23/arthur-vassilvitski-2007-kmeans-the-advantages-of-careful-seeding/ Блог Lingpipe

[kmeans||-12] Б. Бахмани, Б. Мозли, А. Ваттани, Р. Кумар, С. Васильвицкий «Масштабируемые K-средства ++» , 2012 г., Труды Фонда VLDB.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]