Компактная кластеризация

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

Какой алгоритм / реализация кластеризации занимает меньше O (n ^ 2) места?

Есть ли где-нибудь список алгоритмов и их требования к времени и пространству?

K-Means и Mean-Shift используют необработанные выборочные дескрипторы (нет необходимости предварительно вычислять аффинную матрицу).

В противном случае для спектральной кластеризации или кластеризации с итерацией мощности вы можете использовать представление разреженной матрицы (например, сжатые разреженные строки) аффинной матрицы k-ближайших соседей (для некоторой метрики расстояния или аффинности). Если k мало (скажем, 5 или 10). Вы получите очень эффективное представление пространства (2 * n_samples * k * 8 байт для значений с плавающей запятой двойной точности).

Некоторые алгоритмы кластеризации могут использовать структуры пространственного индекса. Это позволяет, например, DBSCAN и OPTICS запускаться за время (если индекс разрешает запросы ).O ( n log $O(n\log n)$$O(\log n)$

Очевидно, что алгоритм, который работает с такой сложностью, не строит матрицу расстояний .$O(n^2)$

Для некоторых алгоритмов, таких как иерархическая кластеризация с одиночной и полной связью, существуют оптимизированные алгоритмы (SLINK, CLINK). Просто большинство людей используют то, что они могут получить, и то, что легко реализовать. И иерархическую кластеризацию легко реализовать наивно, используя итераций по матрице расстояний (что приводит к алгоритму ...).n 2 O ( n 3$n$$n^2$$O(n^3)$

Я не знаю полного списка, сравнивающего алгоритмы кластеризации. В конце концов, вероятно, существует более 100 алгоритмов кластеризации. Например, существует как минимум дюжина вариантов k-средних. Плюс, есть сложность во время выполнения так же как сложность памяти; есть средний случай и худший случай. Существуют огромные различия в реализации (например, упомянутая выше одиночная ссылка; и реализации DBSCAN, которые не используют индекс и, следовательно, находятся в , и при этом им не нужно хранить полную матрицу расстояний , тогда им еще нужно вычислить все попарные расстояния). Плюс есть множество параметров. Для k-средних,n × n k O ( n 2 ) O ( n ) O ( n log n ) O ( n $O(n^2)$$n\times n$$k$имеет решающее значение. Практически для любого алгоритма функция расстояния имеет огромное значение (во многих реализациях допускается только евклидово расстояние ...). И как только вы доберетесь до дорогих функций расстояния (помимо таких простых вещей, как евклидовы), число вычислений расстояния может быстро стать основной частью. Таким образом, вам нужно будет различать общее количество операций и количество необходимых вычислений расстояния. Таким образом, алгоритм, который находится в операциях, но только вычислений расстояния, может легко превзойти алгоритм, который в обоих случаях, когда функции расстояния действительно дороги (скажем, расстояние сама функция ).$O(n^2)$$O(n)$$O(n \log n)$$O(n)$

Хороший вопрос. Простой метод, скажем, для трех ближайших соседей - это выборка соседей N-выборки для каждой точки данных с сохранением ближайших 3. Хотя это тривиально, выполнение этого для нескольких значений N-выборки даст вам некоторое представление об отношении сигнал / шум, ближнем / фоновом шумах. , легко наносится на график для ваших данных. Дополнительный трюк состоит в том, чтобы затем проверить соседей соседей, чтобы увидеть, есть ли какие-либо из них ближе, чем прямые соседи. Кроме того, если входные данные уже хорошо перетасованы, сэмплируйте в блоках, иначе кэш будет работать быстрее.

(Добавлено): см. Fastcluster в R, и я верю в SciPy v0.11.
Текст см. В разделе google-all-pair-Similarity-search .

Повторите: «Соответствующая мера различий гораздо важнее для достижения успеха с кластеризацией, чем выбор алгоритма кластеризации» - выбор метода кластеризации .