Позвольте мне, не заходя далеко, просто скопировать и вставить список опций из моей собственной функции !kmini(макрос для SPSS), найденный в коллекции «Кластеризация» здесь .
Способ создания или выбора начальных кластерных центров. Выбирать:
- RGC - центроиды случайных подвыборок . Данные разбиты случайным образом по
kнеперекрывающимся значениям, по членству, группам и центроидам этих групп назначаются начальные центры. Таким образом, центры рассчитываются, а не выбираются из существующих случаев набора данных. Этот метод позволяет получить центры, которые расположены близко друг к другу и к общему центроиду данных.
- RP - случайно выбранные точки .
kотдельные случаи данных случайным образом выбираются в качестве начальных центров.
- RUNFP - самые дальние точки ( текущий
выбор). Первые
kслучаи берутся за центры, а затем во время прогона остальных случаев набора данных постепенно производятся замены между центрами; Целью замен является получение в конечных kточках, наиболее удаленных друг от друга, в переменном пространстве. Эти точки (случаи), занимающие периферийные позиции в облаке данных, являются произведенными начальными центрами. (Этот метод используется по умолчанию в процедуре k-средних QUICK CLUSTERSPSS. Подробности см. В разделе Алгоритмы SPSS. См. Также описание здесь ).
- SIMFP - самые дальние точки (простой выбор). Первый центр выбран как случайный случай из набора данных. 2-й центр выбирается как случай, максимально удаленный от этого центра. 3-й центр выбирается как случай, максимально удаленный от этих двух (от ближайшего из двух), и так далее.
- KMPP - случайные дальние точки, или k-означает ++. Первый центр выбран как случайный случай из набора данных. Второй центр также выбирается случайным образом, но вероятность выбора случая пропорциональна расстоянию (квадратному евклидову) от него до этого (первого) центра. 3-й центр также выбирается случайным образом с вероятностью выбора, пропорциональной расстоянию случая до ближайшего из этих двух центров, и так далее. (Артур Д., Васильвицкий С.С. K-средства ++: преимущества тщательного посева. // Материалы 18-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. 2007. 1027–1035.)
- GREP - представитель группы точек . Идея метода - собирать как центры
kНаиболее представительные, «депутатские» дела. 1-й центр берется как случай, ближайший к общему центроиду данных. Затем остальные центры выбираются из точек данных таким образом, чтобы каждая точка рассматривалась на предмет того, находится ли она ближе (и на сколько в квадрате евклидова расстояния) к набору точек, чем каждая из последних в любой из уже существующих центров. Т.е. каждая точка рассматривается как кандидат для представления некоторой группы точек, еще недостаточно хорошо представленных уже собранными центрами. Точка, наиболее представительная в этом отношении, выбрана следующим центром. (Кауфман, Л. Руссеув, П. Дж. Поиск групп в данных: введение в кластерный анализ., 1990. См. Также: Пена, Дж. М. и др. Эмпирическое сравнение четырех методов инициализации для алгоритма K-средних // Распознавание образов Lett. 20 (10), 1999,
- [Существует также хороший метод, еще не реализованный мной в макросе, для генерации
kточек, которые являются случайными, но «менее случайными, чем случайные», где-то между случайностью и жадностью; увидеть потенциальную теоретическую основу для этого метода]
- Еще один метод - иерархическая кластеризация по методу Уорда. Вы можете сделать это на подвыборке объектов, если выборка слишком велика. Тогда средства произведенных им
kкластеров являются исходными семенами для процедуры k-средних. Ward's предпочтительнее, чем другие методы иерархической кластеризации, потому что он разделяет общую целевую цель с k-means.
Методы RGC, RP, SIMFP, KMPP зависят от случайных чисел и могут изменять их результат от прогона к прогону.
Метод RUNFP может быть чувствителен к порядку регистра в наборе данных; но метод GREP - нет (кроме случаев, когда в данных много идентичных случаев, связей). Метод GREP может не собрать все kцентры, если kон велик относительно количества наблюдений в данных ( n), особенно когда k>n/2. [Макрос сообщит, если данные не позволяют этому методу собирать kцентры]. Метод GREP является самым медленным, он вычисляет [в моей реализации] матрицу расстояний между всеми случаями, поэтому он не подойдет, если существует много десятков тысяч или миллионов случаев. Вы можете, однако, сделать это на случайной выборке данных.
В настоящее время я не обсуждаю, какой метод «лучше» и при каких обстоятельствах, потому что я до сих пор не провел обширного имитационного исследования вопроса. Мои предварительные и поверхностные впечатления заключались в том, что GREP является особенно достойным (но дорогостоящим), и что если вы хотите действительно дешевый метод, который все еще достаточно конкурентоспособен, то случайные k баллов, RP, являются достойным выбором.
В прошлый раз, когда я сделал всесторонний обзор литературы по этому вопросу, который, по общему признанию, почти 20 лет назад, двумя основными рекомендациями были:
В приложениях с большими данными метод Уорда работает не очень хорошо, хотя его можно применить к подвыборке.
Я провел несколько симуляций, которые я так и не нашел, и нашел, что:
Главный вывод, который я извлек из этого, заключается в том, что алгоритм SPSS на удивление хорош, но если у кого-то есть ресурсы, более 1000 случайных стартовых точек - это путь.
источник
С номенклатурой ttnphns я протестировал RGC, RP и KMPP на:
Я не рекомендую RGC, потому что полученные центры очень близки друг к другу: среднее многих точек близко к глобальному среднему (закон больших чисел). Это может сильно замедлить конвергенцию: требуется некоторое время, чтобы кластеры начали индивидуализироваться.
RP обычно хорош и рекомендовал бы в качестве первого легкого выбора.
KMPP очень популярен и очень хорошо работает в небольшом измерении: по сравнению с RP он имеет тенденцию уменьшать вероятность окончания локального минимума.
Однако, когда я работал над большими наборами данных (1 млн. Точек, представляющих собой мешок слов из текстовых документов с большим измерением), RP немного опережал KMPP в том смысле, что он заканчивался немного меньшим количеством итераций. Я был удивлен этим. В большом наборе данных / высоком измерении сходимость к глобальному минимуму невозможна, вы измеряете качество как «насколько хорош локальный минимум» = «насколько мал итоговый SOD». Оба метода имели одинаковое качество.
Обратите внимание, что важно использовать рандомизированный метод, если вы хотите использовать репликации для улучшения качества.
источник