Нахождение ближайшего совпадения - PullRequest
Новая
       19

Нахождение ближайшего совпадения

4 голосов
/ 09 июня 2010

У меня есть объект с набором параметров, таких как: 

var obj = new {Param1 = 100; Param2 = 212; Param3 = 311; param4 = 11; Param5 = 290;}

С другой стороны у меня есть список объектов: 

var obj1  = new {Param1 = 1221 ; Param2 = 212 ; Param3 = 311 ; param4 = 11  ; Param5 = 290 ; }
var obj3  = new {Param1 = 35   ; Param2 = 11  ; Param3 = 319 ; param4 = 211 ; Param5 = 790 ; }
var obj4  = new {Param1 = 126  ; Param2 = 218 ; Param3 = 2   ; param4 = 6   ; Param5 = 190 ; }
var obj5  = new {Param1 = 213  ; Param2 = 121 ; Param3 = 61  ; param4 = 11  ; Param5 = 29  ; }
var obj7  = new {Param1 = 161  ; Param2 = 21  ; Param3 = 71  ; param4 = 51  ; Param5 = 232 ; }
var obj9  = new {Param1 = 891  ; Param2 = 58  ; Param3 = 311 ; param4 = 21  ; Param5 = 590 ; }
var obj11 = new {Param1 = 61   ; Param2 = 212 ; Param3 = 843 ; param4 = 89  ; Param5 = 210 ; }

Что является лучшим (самым простым)алгоритм поиска ближайшего совпадения для первого объекта в перечисленных объектах?

Ответы [ 3 ]

4 голосов
/ 09 июня 2010

Вы должны определить термин ближайшее совпадение , прежде чем пытаться его найти !!



1- Многие люди используют Среднее квадратичное отклонение (или Евклидово расстояние ):

Рассчитать среднеквадратичную ошибку для всех объектов: 

Sqr(obj.Param1-obj1.Param1) + Sqr(obj.Param2-obj1.Param2) + ..... // for obj1
Sqr(obj.Param1-obj2.Param1) + Sqr(obj.Param2-obj2.Param2) + ..... // for obj2

и выберите тот с минимальным значением ...



2- Вы также можете использовать Минимальную абсолютную ошибку: 

Abs(obj.Param1-obj1.Param1) + Abs(obj.Param2-obj1.Param2) + ..... // for obj1
Abs(obj.Param1-obj2.Param1) + Abs(obj.Param2-obj2.Param2) + ..... // for obj2

и выберите тот с минимальным значением ...



3- Также вы можете подать k-ближайший сосед с любыми критериями, которые вы выбрали выше



Все зависит от свойств этих параметров ...

Для получения дополнительной информации вы можете посмотреть Список алгоритмов классификации

1 голос
/ 09 июня 2010

Зависит, наверное.Мне на ум приходит несколько вариантов:

  • SAD: вычислите абсолютную разницу каждой пары параметров (тестируемого вами и каждого из ваших кандидатов) и суммируйте их.Наименьшее число - самое близкое
  • L2-норма: вычислить разницу каждой пары параметров, возвести их в квадрат, сложить их, взять квадратный корень
  • Косинус: умножить каждый параметр на другой параметр, суммавверх.Разделите результат на произведение длины (L2-норма) обоих объектов

Конечно, есть еще тысячи возможностей, поэтому вы должны указать, что именно вы хотите!

1 голос
/ 09 июня 2010

Вы также можете использовать Евклидово расстояние .

По сути, вы притворяетесь, что каждый объект является точкой в ​​5 измерениях, и ищете точку, которая является ближайшей (т.е. имеет наименьшее расстояние).

...