Установить сходство - вычислить индекс Жакара без квадратичной сложности

14

У меня есть группа из n наборов, для которых мне нужно вычислить значение типа «уникальность» или «сходство». Я остановился на индексе Жакара как на подходящей метрике. К сожалению, индекс Жакара работает только с двумя наборами одновременно. Для того чтобы вычислить сходство между всеми множествами, потребуется порядка n 2 вычислений Жакара.NN2

(Если это помогает, обычно составляет от 10 до 10000, и каждый набор содержит в среднем 500 элементов. Кроме того, в конце концов, мне все равно, насколько похожи какие-либо два конкретных набора - скорее, меня интересует только какое внутреннее сходство всей группы множеств есть. (Другими словами, среднее (или, по крайней мере, достаточно точное приближение среднего) всех индексов Жакара в группе))N

Два вопроса:

  1. Есть ли способ по-прежнему использовать индекс Jaccard без сложности ?N2
  2. Есть ли лучший способ вычислить сходство / уникальность набора для группы наборов, чем тот, который я предложил выше?
rinogo
источник
Не могли бы вы сначала уточнить, что вы подразумеваете под «внутренним сходством»?
Суреш
Другими словами, среднее (или, по крайней мере, достаточно точное приближение среднего) всех индексов Жакара в группе.
5
Если вы хотите приблизить ответ, то вы можете использовать минимальное хеширование для приблизительной оценки расстояния Жакара, а затем использовать полученное представление для вычисления желаемого среднего.
Суреш
6
Я не знаю, что вы подразумеваете под «достаточно точным», но один из способов оценить среднее для многих вещей - это просто вычислить несколько из них (в данном случае индексы Жакара для нескольких пар множеств) случайным образом и вычислить их среднее. Затем вы можете использовать границу Черноффа, чтобы получить верхнюю границу вероятности того, что эта оценка далека от истинного среднего.
Tsuyoshi Ito

Ответы:

4

Можно было бы использовать Схему подписи [1], фильтрацию по размеру : схему, которая использует информацию о размере, чтобы уменьшить количество пар наборов, которые необходимо учитывать.

Они также экспериментируют с взвешенной формой; где веса основаны на IDF.

[1] Арасу, Арвинд, Венкатеш Ганти и Рагхав Каушик. «Эффективное соединение точного набора-подобия». В материалах 32-й Международной конференции по базам данных очень больших размеров, 918–929. VLDB '06. Фонд VLDB, 2006

В
источник
Эта ссылка, кажется, умерла. Попробуйте обновить его до vldb.org/conf/2006/p918-arasu.pdf .
j_random_hacker
0

Другой вариант - использовать локальную чувствительность к хешированию вики-ссылки . Я видел, как Ву и Цзоу использовали его для обнаружения сходства в сообществе ( метод инкрементального обнаружения сообщества для систем социальных тегов, использующих хеширование с учетом локальных особенностей , Neural Networks 58: 14–28; ACM DL ), который в основном обнаруживает сходство между целым числом или наборы строк.

dinos66
источник
1
Пожалуйста, суммируйте содержание ссылок и приведите статью. Если ссылки устаревают, текущий ответ становится бесполезным.
vonbrand