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

Как да сравним приликата между два масива? Кажете, че имам:

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

И така, мисля, че нещо не е наред с моя алго? Или може би трябва да използвам „различен“ вид алгоритъм, а не разстояние (тъй като по същество .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
Моля, дайте пример за стойности на масив X, които биха дали резултат от масив 1.   -  person Lisa    schedule 17.06.2011
comment
Вашият алгоритъм изчислява (на квадрат) евклидово разстояние (предполагам, че dist е инициализирано на 0 точно преди цикъла). Това е напълно разумен избор и това, което би било направено през повечето време и с тази мярка, Array3 наистина е по-близкият. Разбира се, възможно е да се определи разстоянието по много други начини, но вие, тъй като не обяснихте защо разстоянието до Array1 трябва да бъде по-късо, трудно е да ви помогна.   -  person Didier Dupont    schedule 17.06.2011
comment
Съжалявам, това, което исках да кажа, е, че колкото „по-близо“ е един елемент до „желания“ елемент (без да се взема предвид 0), тогава допълнително, те трябва да добавят към мярката за сходство за този конкретен масив. Т.Е. .25 е „по-близо“ до 1, отколкото 0 до 1. Имам ли смисъл? съжалявам   -  person user488792    schedule 17.06.2011
comment
@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 е верният отговор. Алгоритъмът, който използвате, ви дава правилния резултат.

По принцип за мен Array 3 е по-сходен с основния Array, отколкото Array1. Какъв е моделът, който търсите? Казвате, че Array1 трябва да е резултатът... защо?

Разстоянието е просто начин за сравняване на два масива чрез произволно математическо предположение, зад него няма истинска „логика“, но ние му я даваме.

Ако искате резултатът да бъде Array1, тогава:

  • Дефинирайте ЗАЩО Масив1 трябва да бъде резултат от логически условия.
  • Преведете ЗАЩО Масив1 ще бъде резултатът в математическа формулировка
  • Приложете тази формулировка
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
@Michael, благодаря за подсказката... да, случайно забравих тази част. Ще го редактирам - person LiKao; 17.06.2011
comment
Виждам и други няколко грешки. Направих корекциите, но нямам достатъчна репутация, за да се покажат без преглед. - person Michael J. Barber; 17.06.2011
comment
@Michael Благодаря за помощта. Предполагам, че не трябва да публикувам без достатъчно кафе сутрин. Определено трябва да изтегля малко, докато кодът ми се компилира. - 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 - Не съм сигурен как се прилага разстоянието на Хеминг, използвайки реални числа. Склонен съм да смятам, че вашето предложение за косинусово сходство е по-вероятно да бъде полезно, но мисля, че въпросът е малко неясен за крайната дестинация и имам чувството, че user488792 също няма официално изискване, но някой може да му каже, на за всеки отделен случай, дали нещо изглежда ОК/НЕ ОК. - person Joel Goodwin; 17.06.2011
comment
Най-лесният начин за разстоянието на Хеминг би бил просто да се направи нов основен масив с двоични стойности. Иначе не знам как да го направя. - person Michael J. Barber; 17.06.2011
comment
Той наистина трябва да прецизира какво има предвид под подобни. Може би наистина иска да използва нещо като разстоянието на Махаланобис. - person Grantismo; 17.06.2011