1. дома
  2. Вопрос и ответ
  3. Кластеризация разреженного набора данных двоичных векторов

Кластеризация разреженного набора данных двоичных векторов

2011-12-20 2 views
5

Если у меня есть разреженный набор данных, где каждый данные описываются вектором из 1000 элементов, каждый элемент этого вектора может быть либо 0, либо 1 (много 0 и некоторые 1), do вы знаете какую-либо функцию расстояния, которая может помочь мне сгруппировать их? Что-то вроде евклидова расстояния удобно в этом случае? Я хотел бы знать, есть ли простая удобная метрика расстояния для такой ситуации, чтобы попробовать мои данные.Кластеризация разреженного набора данных двоичных векторов

Благодаря

источник

2011-12-20 shn

+0

Как насчет функции искажения, используемой в K-meloids? Он не очень отличается от евклидова расстояния. – Neo

+0

@CRK K-meloids использует [расстояние Минковского] (http://en.wikipedia.org/wiki/Minkowski_distance) с p = 1, что является общим случаем евклидова расстояния, не так ли? – shn

ответ

3

взглянуть на расстояния функций, используемых для разреженных текстовых векторов, таких как косинус расстояния и для сравнения множеств, таких как расстояние Jaccard.

источник

2011-12-21 08:10:13

0

Если это действительно много 0 и несколько 1, вы можете попробовать кластеризацию для первого или последнего 1 - см http://aggregate.org/MAGIC/#Least Существенная 1 Bit

источник

2011-12-20 08:45:37

+0

Первый или последний? Какова метрика функции между двумя указанными в этом случае векторами? Расстояние (V1, V2) – shn

10

Ваш вопрос не имеет ни одного ответа. В зависимости от домена существуют лучшие практики.

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

  • Карлос Ордоньесы. Кластеризация двоичных потоков данных с помощью K-средств. PDF
  • Tao Li. Общая модель кластеризации двоичных данных. PDF

Для идей о мерах подобия см это онлайн "tool for measuring similarity between binary strings". Они упоминают: Сокал-Мишнер, Жаккар, Рассел-Рао, Хаманн, Соренсен, Антидиск, Снейт-Сокал, Роджер-Танимото, Очьяй, Юле, Андерберг, Кульчинский, Пири Пинь и Гауэр2, Точечный продукт, Косинус-коэффициент, Хэмминг-Дистрикт. Они также ссылаются на эти документы:

  • Люк Б. Т., кластеризация двоичных объектов
  • Лин Д. Теоретико-информационное Определение похожести.
  • Toit, du S.H.C .; Steyn, A.G.W .; Stumpf, R.H .; Анализ графических разведочных данных; Глава 3, стр. 77, 1986; Springer-Verlag.

(я лично, как косинус. Существует также KL-дивергенция, и его Jensen расстояние аналог.)

источник

2011-12-20 10:39:55 cyborg

+0

Спасибо за ваш ответ, это интересная ссылка. Но, скажем, мы используем Хэмминг (или косинус или любое другое расстояние), как мы можем узнать представителя каждой группы векторов.Я имею в виду, допустим, у нас есть v1 = 0100100001100 и v2 = 0001100001100, они близки друг к другу, поскольку они отличаются только двумя битами (2-я и 3-я позиции), тогда расстояние Хэмминга, например, будет 2 (косинус будет 0,7500), проблема заключается в следующем: каков будет репрезентативный вектор v1 и v2? Как (узнать) только значения вектора, которые должны представлять v1 и v2, и всех других векторов, которые близки к ним. – shn

+1

Репрезентативный вектор - средний (* centroid *, не двоичный) или * medoid *. Прочтите документы, чтобы найти их. – cyborg

+1

Инструмент Dead Link "для измерения сходства между двоичными строками" – Ahue

Смежные вопросы

 Смежные вопросы