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

Question

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

Спасибо

Answer 1

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

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

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

Для получения информации о мерах подобия см. Этот онлайн «инструмент для измерения подобия между двоичными строками» . Они упоминают: Сокала-Микенера, Жакара, Рассела-Рао, Хаманна, Соренсена, АнтиДайса, Сниз-Сокала, Роджера-Танимото, Очиаи, Йоля, Андерберга, Кульчинского, Фи Пирсона и Гауэра2, Точечный продукт, Коэффициент косинуса, Расстояние Хэмминга. Они также цитируют эти документы:

• Люк, Б. Т., Кластеризация бинарных объектов
• Лин Д., Информационно-теоретическое определение подобия.
• Toit, du S.H.C .; Steyn, A.G.W .; Штумпф, Р.Х .; Графический исследовательский анализ данных; Глава 3, с. 77, 1986; Springer-Verlag.

(мне лично нравится косинус. Есть также KL-дивергенция и ее аналог расстояния Дженсена.)

Answer 2

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

Answer 3

Было предложено много функций расстояния / подобия для двоичных векторов.

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

Answer 4

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