быстрое обнаружение подобия

Question

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

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

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

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

Вы видели эту проблему раньше или что-то похожее на нее? Что такое хорошее решение?

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

Answer 1

Не зная дополнительной информации о метрике, сказать сложно. У меня нет никаких идей для устранения аспекта 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, тем лучше).

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

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

 

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

Answer 5

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

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

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

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

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 ... 
     } 
    } 
    } 
} 

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

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

Answer 6

Невозможно использовать k d-tree?

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

Answer 7

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

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

Answer 8

Звучит как BK-Tree. Here is a small example. Вы в основном создаете дерево и проверяете, какая ветка должна использоваться для аналогичного поиска объектов, а какие нет, поэтому вы предотвращаете O(n2)