Поиск похожего объекта

Question

Предположим, у меня есть следующий массив объектов:

Object 0:
  [0]=1.1344
  [1]=2.18
  ...
  [N]=1.86
-----------
Object 1 :
  [0]=1.1231
  [1]=2.16781
  ...
  [N]=1.8765
------------- 
Object 2 :
  [0]=1.2311
  [1]=2.14781
  ...
  [N]=1.5465  
--------
Object 17:
  [0]=1.31
  [1]=2.55
  ...
  [N]=0.75

Как я могу сравнить эти объекты?

Вы видите, что объект 0 и объект 1 очень похожи, но объект 17 неткак и любой из них.

Я бы хотел, чтобы алгоритм, который дает мне все подобные объекты в моем массиве

Answer 1

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

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

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

Подробнее о теме поиска ближайших соседей и евклидовом расстоянии здесь и здесь .Удачи!

Answer 2

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

Если вам нужно найти, какой объект больше всего похож на выбранный объект-m, вы можете использовать ближайшийалгоритм соседей или, если вам нужно найти похожие наборы объектов, вы можете использовать алгоритм k-средних для поиска k наборов.

Answer 3

Вы помечаете этот вопрос с помощью Algorithm (а я не эксперт в C ++), поэтому давайте дадим псевдокод.

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

Рассмотрим A как массив с n объектами и m как число полей в каждом объекте.

threshold  = 0.1
for i in (0, n):
    for j in (i+1,n):
        flag = true;
        for k in (1,m):
            if (abs(A[i][k] - A[j][k]) > threshold) 
                flag = false // if the absolute value of the diff is above the threshold object are not similar 
                break // no need to continue checks
        if (flag)
            print: element i and j similar // and do what ever

Сложность по времени O(m * n^2).

Обратите внимание, что вы можете использовать тот же алгоритм для сортировки массива объектов - объявите функцию сравнения как max diff для поля и затем выполните соответствующую сортировку.

Надеюсь, это поможет!