Сравнение расстояния между массивами?

Как сравнить сходство между двумя массивами? Скажем, у меня есть:

Base Array: [.5,0,0,0,.25,0,0,.25,0,0,0,0]

Array 1: [1,0,0,0,1,0,0,1,0,0,0,0]
Array 2: [0,0,1,0,0,0,1,0,0,1,0,0]
Array 3: [1,0,0,0,0,0,0,0,0,0,0,0]

Что касается приведенных выше массивов, ответ должен быть Массив 1. Ответ - Массив 1, потому что элементы массива «ближе» по структуре к элементам массива базового массива. В отличие от массива 3, .25 ближе к 1, чем к 0. Другой пример:

Base Array: [.75,0,0,0,0,0,0,0,.25,0,0,0]

Array 1: [1,0,0,0,1,0,0,1,0,0,0,0]
Array 2: [0,0,1,0,0,0,1,0,0,1,0,0]
Array 3: [1,0,0,0,0,0,0,0,0,0,0,0]

Что в этом случае, Массив 3 должен быть ответом.

Однако, используя мой текущий алгоритм (который я дам позже), ответ становится массивом 3. Вот что я использую:

for (int i = 0; i < basearray.Length; i++)
{
  temp = (basearray[i] - arrayX[i]);
  dist += temp * temp;
}

Итак, я думаю, что что-то не так с моим алгоритмом? Или, может быть, мне нужно использовать «другой» алгоритм, а не расстояние (поскольку, по сути, 0,25 ближе к 0, чем к 1, но я хочу другого).

Спасибо!

ОБНОВИТЬ:

Я нашел ответ! Спасибо всем за помощь. Вот:

float[] pbaseArrX = new float[3];
float[] pcompArrX = new float[3];

float dist1 = 0, dist2 = 0;

for (int i = 0; i < baseArrX.Count; i++)
{
  pbaseArrX[i] = baseArrX[i] / (baseArrX[0] + baseArrX[1] + baseArrX[2]);
}

//Do the following for both compArr1 and compArr2;
for (int i = 0; i < compArrX.Count; i++)
{
  pcompArrX[i] = pcompArrX[i] / (pcompArrX[0] + pcompArrX[1] + pcompArr[2]);
}

//Get distance for both
for (int i = 0; i < pcompArrX.Count; i++)
{
  distX = distX + ((pcompArrX[i] - pbaseArrX[i])^2);
}

//Then just use conditional to determine which is 'closer'

person user488792    schedule 17.06.2011    source источник
comment
Так что именно вам нужно, если не расстояние? т.е. почему массив 1 правильный ответ?   -  person Petar Ivanov    schedule 17.06.2011
comment
Пожалуйста, расширьте в противном случае.   -  person Richard Brightwell    schedule 17.06.2011
comment
Пожалуйста, приведите пример значений arrayX, которые дадут результат Array 1.   -  person Lisa    schedule 17.06.2011
comment
Ваш алгоритм вычисляет (квадрат) евклидово расстояние (я думаю, dist инициализирован равным 0 непосредственно перед циклом). Это вполне разумный выбор, и то, что будет делаться в большинстве случаев, и с этой мерой Array3 действительно ближе. Расстояние конечно можно определить многими другими способами, но вы так и не объяснили почему расстояние до Array1 должно быть короче, вам трудно помочь.   -  person Didier Dupont    schedule 17.06.2011
comment
Извините, я хотел сказать, что чем «ближе» элемент к «желаемому» элементу (без учета 0), то, кроме того, они должны добавляться к мере сходства для этого конкретного массива. т.е. 0,25 «ближе» к 1, чем 0 к 1. Я понимаю? Извини.   -  person user488792    schedule 17.06.2011
comment
@user488792 user488792 Вас вообще волнуют значения или только то, равны они нулю или нет? Например, 0,5 ближе к 1, чем 0,25, или оба варианта одинаково хороши? Потому что расстояние Хэмминга будет именно тем, что вам нужно, если конкретные значения не имеют значения.   -  person Michael J. Barber    schedule 17.06.2011


Ответы (4)


Похоже, вы хотите сравнить массивы как лучи (только направление), но вы сравниваете их как векторы (направление и величина). Я предлагаю сравнить массивы с косинусным сходством, которое представляет собой просто косинус угла между векторов и, таким образом, сравнение только их направлений. Для представленных массивов сходство по косинусу между базовым массивом и массивом 1 составляет 0,94, а для массива 2 — 0,82, что соответствует вашим ожиданиям.

person Michael J. Barber    schedule 17.06.2011
comment
+1 Интересно! Раньше не слышал о сходстве косинусов, и понятно, почему это можно использовать. Вполне может быть решением вопроса. - person Joel Goodwin; 17.06.2011
comment
Привет! Спасибо за это! Этот алгоритм подобия косинусов хорош на данный момент! Я проверил это, и иногда бывают случаи, когда я получаю неправильный ответ, но пока у меня еще нет алгоритма, я воспользуюсь им. Спасибо! - person user488792; 17.06.2011

Массив 3 - правильный ответ. Алгоритм, который вы используете, дает вам правильный результат.

По сути, для меня массив 3 больше похож на базовый массив, чем на массив 1. Какую модель вы ищете? Вы говорите, что результатом должен быть Array1... почему?

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

Если вы хотите, чтобы результатом был Array1, тогда:

  • Определите, ПОЧЕМУ Array1 должен быть результатом логических терминов.
  • Перевести ПОЧЕМУ Array1 должен быть результатом в математическую формулировку
  • Реализовать эту формулировку
person Jorge Córdoba    schedule 17.06.2011

Проблема здесь в том, что у вас нет четкого определения понятия «подобие». В зависимости от варианта использования данных существует бесконечно много способов определить сходство. Оставив ваш массив в стороне, для этого есть простой пример:

  • Очки и бинокль похожи, потому что вы используете их оба, чтобы смотреть на вещи.
  • Очки и велосипед похожи, потому что оба состоят из двух кругов, связанных друг с другом.
  • Очки и Трава похожи, потому что оба начинаются на «G» и заканчиваются на «S».

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

Если оставить в стороне этот момент, есть один распространенный случай подобия, который довольно часто используется для данных последовательности при интеллектуальном анализе данных. Это называется косинусным расстоянием, и оно ничем не отличается от того, что вы используете. Оно называется косинусным расстоянием. Вот алгоритм:

for (int i = 0; i < basearray.Length; i++)
{
  temp += (basearray[i] * arrayX[i]);
  f_base += (basearray[i] * basearray[i]);
  f_array += (array[i] * array[i]);
}
dist = 1 - (temp / sqrt( f_base * f_array ));

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

person LiKao    schedule 17.06.2011
comment
Я думаю, вам не хватает квадратного корня из знаменателя дроби в последней строке. - person Michael J. Barber; 17.06.2011
comment
@Майкл, спасибо за подсказку ... да, я случайно забыл эту часть. Буду редактировать в - person LiKao; 17.06.2011
comment
Я также вижу еще пару ошибок. Я внес исправления, но у меня недостаточно репутации, чтобы они отображались без проверки. - person Michael J. Barber; 17.06.2011
comment
@Майкл Спасибо за помощь. Думаю, мне не следует публиковать сообщения без достаточного количества кофе по утрам. Мне определенно нужно получить некоторые, пока мой код компилируется. - person LiKao; 17.06.2011
comment
Еще один совет с этой стороны: держите свои массивы нормализованными при выполнении задач интеллектуального анализа данных. Это защитит вас от ошибок в других местах (обычно, если я написал код выше, sqrt и деление там не будет). - person LiKao; 17.06.2011

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

В вашем примере третий массив определенно ближе всего к евклидову расстоянию, потому что ваш базовый массив намного ближе к нулевому массиву, чем ваш первый массив. У них может быть «похожая структура», но вы смотрите на это не так. Ваша мера расстояния заинтересована в числовом расстоянии, и 0 (в массиве 3) намного ближе к 0,25, чем 1 (в массиве 1).

Если вы смотрите на «структуру», это означает, что вы думаете, что 0 намного важнее любого другого числа. то есть вы хотите вознаградить соответствующий массив за то, что он имеет ненулевые значения в одном и том же месте, а не за то, что он численно близок к 0.

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

person Joel Goodwin    schedule 17.06.2011
comment
Расстояние Хэмминга будет соответствовать структурному различию (здесь используется свободная структура, без формального определения), которое вы даете. - person Michael J. Barber; 17.06.2011
comment
@Michael J. Barber - я не уверен, как реализовать расстояние Хэмминга с использованием реальных чисел. Я склонен считать, что ваше предложение о косинусном сходстве, скорее всего, будет полезным, но я думаю, что вопрос немного расплывчат в отношении конечного пункта назначения, и у меня создается впечатление, что у пользователя488792 также нет формального требования, но кто-то может сказать ему, на в каждом конкретном случае, выглядит ли что-то ОК/НЕ ОК. - person Joel Goodwin; 17.06.2011
comment
Самым простым способом для расстояния Хэмминга было бы просто создать новый базовый массив с двоичными значениями. Я не знаю, как это сделать, иначе. - person Michael J. Barber; 17.06.2011
comment
Ему действительно нужно уточнить, что он подразумевает под подобным. Может быть, он действительно хочет использовать что-то вроде расстояния Махаланобиса. - person Grantismo; 17.06.2011