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

Мы испытали подобную проблему с помощью.NET 3.0 и DataGridView в системе парного монитора.

Наше приложение отобразило бы сетку с серым фоном, указав, что ячейки не могли быть изменены. После нажатия "кнопки" настроек изменения программа изменила бы цвет фона ячеек, белых, чтобы указать пользователю, что текст ячейки мог быть изменен. Кнопка "отмены" изменила бы цвет фона вышеупомянутых ячеек назад к серому.

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

Двойная буферизация управление, с помощью вышеупомянутого примера, решило нашу проблему. Мы значительно ценили Вашу справку.

6
задан reinierpost 15 December 2009 в 23:13
поделиться

7 ответов

Without knowing more details of the metric, it's hard to say. I don't have any ideas for eliminating the O(n^2) aspect, but there may be a way to reduce some of the constants involved. For example, if you had a Euclidean metric d(p,q) = sqrt( (p_1-q_1)^2 + ..+ (p_n-q_n)^2), you could square your distance d and compare it to the partial sums of (p_i-q_i)^2 and stop when you exceed d^2.

Whether this will actually save you time depends on how expensive the compare is to just calculating the summands and how many summand calculations you could expect to avoid by doing this (obviously, the smaller d is, the better).

1
ответ дан 17 December 2019 в 00:10
поделиться

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

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

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

1
ответ дан 17 December 2019 в 00:10
поделиться

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

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

1
ответ дан 17 December 2019 в 00:10
поделиться

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

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

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

0
ответ дан 17 December 2019 в 00:10
поделиться

I need to produce a data structure that maps any object o to the set of objects no more dissimilar to o than d, for some dissimilarity value d.

It might be fastest to just abandon the similarity computation when the subtotal becomes larger than d. For example, if your similarities are based on cosine or hausdorff distances this can easily be done.

PS: if this cannot be done, your problem might be related to the k-nearest neighbors problem (or more precise a nearest neighbor problem with a threshold neighborhood). You should look for algorithms that find close-by members without computing all distances (maybe something using triangle inequality). Wikipedia should help you to explore suitable algorithms.

2
ответ дан 17 December 2019 в 00:10
поделиться

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

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

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

Например, предположим, что «разница» - это сумма абсолютных значений разностей трех атрибутов, скажем a1, а2 и а3. Вы можете создать трехмерный массив и установить значение каждого узла массива для объекта с этими значениями, если таковые имеются. Затем, если вы хотите найти все объекты с разницей менее 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. Опять же о характере вычисления: если один из элементов, составляющих разницу, или какое-то небольшое подмножество, имеет тенденцию быть более значительным чем другие, затем создайте структуру данных, которая позволит вам быстро сравнить это в пределах диапазона. Если он находится в пределах допустимого диапазона, выполните полное сравнение. Если нет, то вы даже не смотрите на это.
1
ответ дан 17 December 2019 в 00:10
поделиться

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

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

1
ответ дан 17 December 2019 в 00:10
поделиться
Другие вопросы по тегам:

Похожие вопросы: