Как измерить форму кластера?

14

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

Есть ли мера нелинейности (или «формы») кластеров?

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

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

Мирослав Сабо
источник
1
en.wikipedia.org/wiki/Topological_data_analysis может помочь, хотя форма не совсем соответствует тому, что вы имеете в виду.
Цзыюан
1
Возможно, вы могли бы адаптировать концепцию компактности для вашей цели.
user12719

Ответы:

4

Мне нравятся модели Gaussian Mixture (GMM's).

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

Поэтому, если вам известны параметры оптимального приближения AICc или BIC с использованием GMM, вы можете проецировать их на меньшие размеры. Вы можете повернуть его и посмотреть на главные оси компонентов аппроксимирующего GMM.

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

РЕДАКТИРОВАТЬ: (конечно, Whuber)

Есть несколько способов взглянуть на форму.

  • Вы можете посмотреть на тенденции в средствах. Логнормальное значение аппроксимируется рядом гауссиан, что означает постепенное сближение, а вес которых уменьшается по мере развития. Сумма приближается к более тяжелому хвосту. В n-измерениях последовательность таких компонентов будет составлять лепесток. Вы также можете отслеживать расстояния между средними (преобразовать в большие измерения) и направлять косинусы между ними. Это приведет к гораздо более доступным измерениям.
  • Вы можете создать трехмерную систему, осями которой являются вес, величина среднего и величина дисперсии / ковариации. Если у вас очень большое количество кластеров, это способ просмотреть их в сравнении друг с другом. Это ценный способ конвертировать 50k частей с 2k измерениями в несколько облаков в трехмерном пространстве. Я могу выполнить управление процессом в этом пространстве, если я выберу. Мне нравится рекурсия использования управления моделью гауссовой смеси на основе компонентов модели гауссовой смеси, соответствующих параметрам детали.
  • С точки зрения устранения беспорядка вы можете выбросить очень маленький вес, или вес за ковариацию, или что-то подобное.
  • р2
  • Вы можете смотреть на это как на пузыри, пересекающиеся . Положение равной вероятности (нулевая дивергенция Кульбака-Лейблера) существует между каждой парой кластеров GMM. Если вы отслеживаете эту позицию, вы можете фильтровать по вероятности членства в этом месте. Это даст вам точки классификации границ. Это поможет вам изолировать «одиночки». Вы можете посчитать количество таких границ выше порогового значения для каждого члена и получить список «связности» для каждого компонента. Вы также можете посмотреть на углы и расстояния между локациями.
  • Вы можете повторно сэмплировать пространство, используя случайные числа, заданные в гауссовых PDF-файлах, а затем выполнить основной анализ компонентов и посмотреть на собственные формы и собственные значения, связанные с ними.

РЕДАКТИРОВАТЬ:

Что означает форма? Они говорят, что специфика - это душа всего хорошего общения. Что вы имеете в виду под "мерой"?

Идеи о том, что это может означать:

  • Чувство нормального ощущения / ощущения общего вида. (чрезвычайно качественная, визуальная доступность)
  • мера формы GD & T (копланарность, концентричность и т. д.) (чрезвычайно количественная)
  • что-то числовое (собственные значения, ковариации и т. д.)
  • полезная уменьшенная координата измерения (например, параметры GMM становятся размерами)
  • система с пониженным шумом (сглажена некоторым образом, затем представлена)

Большинство из "нескольких способов" являются некоторыми вариациями на них.

EngrStudent - Восстановить Монику
источник
3

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

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

Получив собственные значения (также называемые спектром), вы можете проверить их относительные размеры, чтобы определить, насколько «растянут» кластер в определенных измерениях. Чем менее однородный спектр, тем более «сигарообразный» кластер и чем более однородный спектр, тем более сферический кластер. Вы могли бы даже определить какую-то метрику для указания, насколько неоднородны собственные значения (спектральная энтропия?); см. http://en.wikipedia.org/wiki/Spectral_flatness .

Дополнительным преимуществом является то, что вы можете изучить основные компоненты (собственные векторы, связанные с большими собственными значениями), чтобы увидеть, «куда» указывают «сигарообразные» кластеры в вашем пространстве данных.

Естественно, это грубое приближение для произвольного кластера, поскольку он моделирует только точки в кластере как один эллипсоид. Но, как я уже сказал, это может дать вам некоторое представление.

lmjohns3
источник
+1 Упрощенно, возможно; но это выглядит эффективным и практичным. Кажется, нет никакого преимущества для многомерной гауссовой подгонки: просто используйте SVD центрированных внутри кластерных данных (которые по сути являются PCA в кластере).
whuber
@ whuber да, я думаю о тех, кто делает то же самое! Соответствие - это больше того, что, согласно теории, происходит за кулисами, в то время как PCA является конкретной реализацией этого процесса. Я отредактирую свой ответ, чтобы сделать это более понятным.
lmjohns3
2

Алгоритмы корреляционной кластеризации, такие как 4C, ERiC или LMCLUS, обычно рассматривают кластеры как линейные многообразия. Т.е. k-мерные гиперплоскости в d-мерном пространстве. Что ж, для 4C и ERiC только локально линейно, поэтому они на самом деле могут быть невыпуклыми. Но они все еще пытаются обнаружить кластеры с уменьшенной локальной размерностью.

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

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

Также взгляните на сложность вычисления выпуклой оболочки в более высоких измерениях ...

Кроме того, у вас есть реальный вариант использования для этого, помимо любопытства?

ВЫЙТИ - Anony-Mousse
источник
2

Если ваша размерность не намного больше, чем 2 или 3, то может оказаться возможным проецировать интересующий кластер в 2D-пространство несколько раз и визуализировать результаты или использовать 2D-измерение нелинейности. Я думал об этом из-за метода случайных проекций http://users.ics.aalto.fi/ella/publications/randproj_kdd.pdf .

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

Для конкретности вы можете подумать о проецировании шара на плоскую поверхность. Неважно, как вы это спроектируете, Нью-Йорк и Нью-Джерси будут вместе, но лишь изредка вы будете толкать Нью-Йорк и Лондон вместе.

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

Джеймс
источник