быстрое обнаружение сходства

StackOverflow https://stackoverflow.com/questions/1889065

Вопрос

У меня есть большая коллекция объектов, и мне нужно выяснить сходство между ними.

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

Мне нужна способность быстро находить по заданному объекту набор похожих на него объектов.

Если быть точным:Мне нужно создать структуру данных, которая сопоставляет любой объект o с набором объектов, не более отличающихся от o, чем d, для некоторого значения различия d, такого, чтобы перечисление объектов в наборе занимало не больше времени, чем если бы они были в массиве или связанном списке (и, возможно, они действительно есть).Как правило, набор будет намного меньше общего количества объектов, поэтому действительно стоит выполнить это вычисление.Это достаточно хорошо, если структура данных предполагает фиксированный d, но если это работает для произвольного d, то еще лучше.

Сталкивались ли вы с этой проблемой раньше или с чем-то похожим на нее?Что является хорошим решением?

Если быть точным:простое решение включает в себя вычисление различий между всеми парами объектов, но это происходит медленно - O (n2) где n - количество объектов.Существует ли общее решение с меньшей сложностью?

Это было полезно?

Решение

Трудно сказать, не зная более подробной информации о метрике.У меня нет идей по устранению аспекта O(n^2), но может быть способ уменьшить некоторые задействованные константы.Например, если у вас есть евклидова метрика d(p,q) = sqrt( (p_1-q_1)^2 + ..+ (p_n-q_n)^2), вы можете возвести в квадрат расстояние d и сравнить его с частичным суммы (p_i-q_i)^2 и останавливаются, когда вы превышаете d^2.

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

Другие советы

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

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

 

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

Если ваша мера сходства транзитивна, вам не нужно вычислять сходство для всех пар объектов, поскольку для объектов a, b, c:

similarity(a,c) = similarity(a,b) op similarity(b,c)

где op это бинарный оператор, например.умножение или сложение.

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

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

  2. В чем суть расчета?С одной стороны, если природа различия заключается, например, в разнице в росте между двумя людьми, то сохранение списка, отсортированного по росту, позволит вам очень быстро найти похожие объекты.Я предполагаю, что реальная проблема более сложна, но, следуя этой логике, если разность представляет собой сумму нескольких линейных величин, вы можете создать многомерный массив, а затем концептуально представить себе набор подобных объектов, подобных этим. внутри n-мерной сферы (т.е.круг, сфера, гиперсфера и т. д.), сосредоточенные вокруг эталонного объекта, и снова найдите их напрямую.На самом деле мне приходит в голову, что если вычисления радиуса слишком сложны или занимают слишком много времени, хорошим приближением было бы создание n-мерного куба (т.квадрат, куб, тессеракт и т. д.) вокруг эталонного объекта, извлеките все объекты, находящиеся внутри этого куба, как «кандидаты», а затем просто выполните фактические вычисления над кандидатами.

Например, предположим, что «разница» представляет собой сумму абсолютных значений разностей трех атрибутов, скажем, a1, a2 и a3.Вы можете создать трехмерный массив и установить значение каждого узла массива для объекта с этими значениями, если таковые имеются.Тогда, если вы хотите найти все объекты, разница которых меньше d с объектом o, вы можете написать:

for (x1=o.a1-d;x1<o.a1+d;++x1)
{
  for (x2=o.a2-d;x1<o.a2+d;++x2)
  {
    for (x3=o.a3-d;x1<o.a3+d;++x3)
    {
      if (array[x1][x2][x3]!=null
        && (abs(x1-o.a1)+abs(x2-o.a2)+abs(x3-o.a3)<=d)
        {
          ... found a match ...
        }
    }
  }
}

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

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

Нельзя ли использовать кd-дерево?

Возможно, потребуется (если возможно) нормализовать размеры.После этого вам просто нужно заполнить дерево, использовать поиск «ближайших N соседей» и попытаться найти любой объект в некотором диапазоне.

Пример объектов:Изображения, Документы.Конечно, работа с необработанным представлением этих объектов в большинстве случаев бесполезна.обычно можно предварительно обработать необработанную форму и превратить ее в некоторую нормализованную форму (для документов, скажем, вектор, для которого каждая запись представляет количество/процент повторов появления определенного слова, для изображений это может быть представление найденных визуальных особенностей). на изображении).

если d фиксировано и возможно предварительное вычисление n^2, вы можете просто использовать графическое представление, используя, например, связанный список для каждого объекта.Вы можете получить более эффективные решения за счет точности, используя приближенные алгоритмы ближайших соседей.

Можем ли мы предположить, что сходство транзитивно, т.е. diff(a,c) == diff(a,b) + diff(b,c)?Если да, то вы можете попробовать следующее:

  1. Отсортируйте коллекцию объектов.Если показатель сходства объектов не имеет приличного абсолютного значения, вы можете произвольно выбрать один объект как «нулевой» и отсортировать все остальные объекты по их сходству с этим объектом.
  2. Чтобы найти предметы, похожие друг на друга s к o, находить o в отсортированном списке и ищите слева и справа, пока разница не станет больше, чем s.

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

Звучит как БК-Дерево. Вот небольшой пример.По сути, вы создаете дерево и проверяете, какую ветвь следует использовать для поиска похожих объектов, а какую нет, чтобы предотвратить O(n2)

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top