алгоритм кластеризации для безразмерных данных

12

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

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

Спасибо!

machine-learning lg.learning clustering банка краски
источник

Почему безразмерность делает эту проблему особенной?

Рафаэль

1

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

Paintcan

15

$k$ $k$ $k$ $k$

$k$

Обе эти проблемы являются NP-сложными в целом, и их трудно приблизить с точностью до произвольного фактора. Обратите внимание, что если вы отбросите условие метрики, все станет намного хуже с точки зрения приближенности.

$k$

В конечном итоге, как и в случае большинства проблем с кластеризацией, окончательный выбор зависит от приложения, размера данных и т. Д.

Суреш Венкат
источник

3

Спасибо за быстрый и понятный обзор. Мне понадобится как минимум несколько дней, чтобы определить, ответили ли вы на мой вопрос. Кажется, мне нужно многому научиться, прежде чем я в достаточной степени пойму мою проблему :)

paintcan 21.10.10

5

Существует также корреляционная кластеризация , которая имеет в качестве входной информации для каждой пары элементов, указывающих, принадлежат ли они к одному и тому же кластеру или к разным кластерам.

Уоррен Шуди
источник

да, это еще один хороший пример. И, конечно, Уоррен является экспертом в этом! Я не знаю, был ли ввод ОП +/- или мог быть преобразован через пороговое значение. Если это так, это определенно жизнеспособный вариант.

Суреш Венкат

5

Если вы просто ищете хорошую эмпирическую производительность, алгоритм распространения сродства обычно работает лучше, чем k-медианы. Существует код, доступный на нескольких языках, и публикации, описывающие алгоритм более подробно, находятся здесь: http://www.psi.toronto.edu/index.php?q=affinity%20propagation

\sum_{i} s (i, c_{i})

$\sum_{i} s(i, c_i)$

$s$ $c_i \in \mathbf{c}$ $i$ $s(i, i)$

dan_x
источник

5

Ваш вопрос, кажется, подразумевает, что вы ищете алгоритм с приличным вычислительным временем. Учитывая размер ваших вершин (или точек), можно создать представление ваших данных с помощью взвешенного графа и использовать кластерный алгоритм Маркова (MCL) для кластеризации графа.

http://www.micans.org/mcl/

MCL основан на случайных обходах взвешенных и невзвешенных графов для поиска плотных подграфов. Он способен обрабатывать большие графики и использовался во многих известных, широко используемых биоинформационных программах (таких как BLAST). -Boucher

Кристина Баучер
источник

1

Рассмотрим алгоритм k-ближайшего соседа .

Рафаэль
источник

Рафаэль, алгоритм k-NN на самом деле не алгоритм кластеризации, не так ли? разве вы неоднократно вытаскиваете k соседей узла?

Суреш Венкат

k

$k$

алгоритм кластеризации для безразмерных данных

Ответы: