[Alg] Array's vergelijken

[EdwinV]

Voor een project moet ik de mate van vergelijkbaarheid van twee objecten uitrekenen. In plaats van een boolean waarde heb ik echter een score nodig, bijvoorbeeld in de range [0,1]. Deze objecten kunnen ook arrays zijn, daarbij ben ik op zoek naar een percentage van overeenkomende elementen.

Een simpel voorbeeld:

Ruby:

[1,2,3].compare([1,2,3])   # 1.0

Er zullen natuurlijk ook gevallen zijn waarbij het antwoord minder simpel te bepalen is:

Ruby:

[1,2].compare( [1,3] )      # 0.5?
[1,2,4].compare( [1,3] )    # 0.5?
[1,2,3].compare( [1,3] )    # 1.0?

Mijn twee mogelijke oplossingen zijn:

Ruby:

def compare_array(first, second)
  ( second.length - (second-first).length ) / first.length
end

Hierbij ga je uit van de lengte van de eerste array en geldt de score dus expliciet één kant uit. (first -> second != second -> first)

Ruby:

def compare_array(first, second)
  t = first.uniq + second.uniq
  ( t.length - t.uniq.length )*2 / t.length
end

Deze gaat uit van de lengte van beide array's, waarbij dus geldt dat de score beide kanten op gelijk is. (first -> second = second -> first)

Wat vinden jullie van deze oplossingen? Heeft iemand andere suggesties die wellicht meer (wiskundig) onderbouwd kunnen worden? Alvast bedankt!

[Dricus]

Voor het vergelijken van arrays zou je eens kunnen kijken naar de Levenshtein Distance. Dit is een manier om te kijken in welke mate 2 strings van elkaar verschillen. Hoe groter de Levenshtein Distance, hoe meer insertions, substitutions of deletions er nodig zijn om de ene string te transformeren naar de andere string.
Ik denk dat dit ook wel toepasbaar is voor het vergelijken van 2 arrays.

[ Voor 11% gewijzigd door Dricus op 03-10-2007 17:04 ]

[KopjeThee]

Je kunt proberen een afstandsmaat te definieeren tussen arrays. Dus zeg dat je 2 array hebt A en B, dan verzin je een functie d(A,B) die aangeeft hoe "ver" A en B uit elkaar liggen. Dit zal je op heel veel manieren kunnen doen. Over het algemeen voldoen alle enigszins intuitieve afstandsfuncties aan 3 eigenschappen:
1) d(A,A) = 0 (de afstand van een array tot zichzelf is 0)
2) d(A,B) = d(B,A) (de afstand tussen A en B is hetzelfde als tussen B en A)
3) d(A,B) + d(B,C) >= d(A,C) (als je direct van A naar C gaat, dan is dat korter dan wanneer je dat via B zou doen, behalve als B op de route zou liggen natuurlijk)

Je moet eerst exact bepalen wat je als verschillend wilt zien: Maakt bijvoorbeeld de volgorde van de elementen uit? d([1,2],[2,1]) = 0?

[BestTested!]

KopjeThee schreef op woensdag 03 oktober 2007 @ 19:59:
Je kunt proberen een afstandsmaat te definieeren tussen arrays. Dus zeg dat je 2 array hebt A en B, dan verzin je een functie d(A,B) die aangeeft hoe "ver" A en B uit elkaar liggen. Dit zal je op heel veel manieren kunnen doen. Over het algemeen voldoen alle enigszins intuitieve afstandsfuncties aan 3 eigenschappen:
1) d(A,A) = 0 (de afstand van een array tot zichzelf is 0)
2) d(A,B) = d(B,A) (de afstand tussen A en B is hetzelfde als tussen B en A)
3) d(A,B) + d(B,C) >= d(A,C) (als je direct van A naar C gaat, dan is dat korter dan wanneer je dat via B zou doen, behalve als B op de route zou liggen natuurlijk)

Je moet eerst exact bepalen wat je als verschillend wilt zien: Maakt bijvoorbeeld de volgorde van de elementen uit? d([1,2],[2,1]) = 0?

Inderdaad, wat stellen de waardes in de array precies voor. Als je dat weet kan je een zinnige afstands-maat defineren.

Als de volgorde van de elementen per array hetzelfde is, dus [x1, x2, x3], kan je bijvoorbeeld de euclidische afstand berekenen. Deze voldoet aan bepaalde eigenschappen die KopjeThee hierboven beschreef wat zeer handig als je met deze afstanden nog verder moet rekenen. Een afstands-maat ('metric') voldoet aan al deze 3 eigenschappen, terwijl een gelijkheids-maat ('simularity') enkel aan eigenschap 1 en 2 hoeft te voldoen.

Verder kan je dingen proberen met in-producten, covariantie, cosinus afstanden, jaccard coefficienten, manhattan afstanden, Levensthein afstanden, er zijn er een hele boel. Maar zoals ik al zei, als je weet wat de elementen betekenen kan je een zinnige maat verzinnen/gebruiken.

[MSalters]

percentage van overeenkomende elementen

Je bedoelt dus f(U,V) = 2 |U ⋂ V| / ( |U| + |V| ) ? Dat komt redelijk overeen met je tweede voorbeeld.
Maar wat zijn je array elementen? Is f([0,999999], [1,00000]) 0 of 1?

[prototype]

MSalters schreef op donderdag 04 oktober 2007 @ 00:24:
[...]

Je bedoelt dus f(U,V) = 2 |U ⋂ V| / ( |U| + |V| ) ? Dat komt redelijk overeen met je tweede voorbeeld.
Maar wat zijn je array elementen? Is f([0,999999], [1,00000]) 0 of 1?

Wat bedoel je precies met deze notatie (met name de vertical bars bij U en V). Ik weet namelijk niet precies wat TS wil en of ik het probleem dus goed begrijp. De criteria voor het vergelijken ontbreekt vooral aan het verhaal van TS.

De intersecties en unions van 2 arrays lijkt me iig twijfelachtig. Een array gedraagd zich meer als een (bounded) lijst / (non-injectieve) sequentie, waarbij elementen dus vaker kunnen voorkomen en volgorde van belang is. Zo'n dergelijke lijst/non-injectieve sequentie kun je beschouwen als zijnde een set van 2-tuples (k,v) waarbij k de positie is en v de waarde. Ik weet niet in hoeverre de intersectie gedeeld door de vereniging van 2 van dergelijke sets bijdraagt aan wat TS zoekt, maar dat is dan ook het probleem opzich... waar slaat de factor 2 trouwens op?

[Tanuki]

prototype schreef op donderdag 04 oktober 2007 @ 00:43:
[...]


Wat bedoel je precies met deze notatie (met name de vertical bars bij U en V).

Die verticale bars geven aan dat die waarde absoluut is. Als U de waarde -1 heeft, komt er +1 te staan. Zelfde voor V.

[ Voor 19% gewijzigd door Tanuki op 04-10-2007 09:53 ]

[EdwinV]

Bedankt voor alle antwoorden en suggesties. Ik zal mijn probleem nog iets verder uitleggen.

We praten hier over een recommendation systeem voor een web winkel. Het doel is om uit te vinden welke producten passen bij een willekeurig product X. Daarvoor maak ik gebruik van een relatie compare(X, Y) = [0.0,1.0], de mate van overeenkomstigheid wordt dus aangegeven met een percentage.

Het vergelijken van twee producten kan op verschillende factoren gebeuren. Denk daarbij aan:

• Prijs
• Leverancier
• Trefwoorden
• Aankopen

De trefwoorden en aankopen bestaan uit arrays die een bepaald percentage overeenkomstige elementen hebben. Bijvoorbeeld:

code:

product1: Tag1, Tag2, Tag3
product2: Tag2, Tag3, Tag4

De aankopen vergelijk ik aan de hand van arrays met daarin user_id's. Als er geen mensen zijn die product X en product Y gekocht hebben, is het dus een slechte aanrader aan een klant. Heeft echter 99% van de mensen die product X gekocht hebben, ook product Y, dan is het veel interessanter om product Y aan te bevelen aan een klant.

In principe is alles relatief in dit systeem. Als ik kies voor een bepaalde berekening om een percentage overeenkomstigheid te krijgen, dan zal dat toegepast worden op alle vergelijkingen en zal als het goed is alles ten opzichte van elkaar goed zijn. Ik vrees alleen wat voor de randgevallen en daarom ben ik op zoek naar een bewezen theorie om dit te berekenen.

Tijdens de vergelijkingen ga ik van het volgende uit:

• De volgorde van de elementen is niet van belang, eventueel sorteer ik beide arrays als dat nodig is om een goede vergelijking te maken,
• De lengte van beide arrays is zelden gelijk,
• De waarden in de arrays valt niet mee te rekenen. Als er integers in staan zijn het id's van entiteiten binnen m'n datamodel.

De Levenshtein Distance lijkt me een goede berekening, maar de vraag is hoe je van de afstand een percentage kan maken. Dan zal je ook moeten berekenen hoeveel stappen het kost om twee totaal verschillende arrays om te zetten.

[Dricus]

Flydesign.nl schreef op donderdag 04 oktober 2007 @ 11:39:
De Levenshtein Distance lijkt me een goede berekening, maar de vraag is hoe je van de afstand een percentage kan maken. Dan zal je ook moeten berekenen hoeveel stappen het kost om twee totaal verschillende arrays om te zetten.

De maximale LD tussen 2 arrays is gelijk aan de lengte van de langste van die 2 arrays, dus het omzetten naar een percentage kan als volgt:

Java:

distance = LevenshteinDistance(array1, array2);
percentage = (distance * 100) / maximum(length(array1), length(array2));

[.oisyn]

Overigens is het wellicht niet handig om een generieke levenshtein distance implementatie te pakken, aangezien deze een tijd-complexiteit van O(n*m) heeft, waarbij n de lengte van de ene string is, en m de lengte van de andere string.

Je usecase in dit geval is veel simpeler, omdat je een vast aantal elementen hebt, waarbij elk element slechts 0 of 1 keer voor kan komen, en de volgorde doet er niet toe. Het is dan handiger om beide arrays gesorteerd te hebben (moet sowieso), en dan de dubbele elementen eruit te filteren. Het aantal elementen wat je overhoudt is dan je distance. Dit is O(n + m).

[MSalters]

prototype schreef op donderdag 04 oktober 2007 @ 00:43:
[...]
Wat bedoel je precies met deze notatie (met name de vertical bars bij U en V).

Standaard wiskunde, |U| is de grootte van de verzameling U.

De intersecties en unions van 2 arrays lijkt me iig twijfelachtig. Een array gedraagd zich meer als een (bounded) lijst / (non-injectieve) sequentie, waarbij elementen dus vaker kunnen voorkomen en volgorde van belang is. Zo'n dergelijke lijst/non-injectieve sequentie kun je beschouwen als zijnde een set van 2-tuples (k,v) waarbij k de positie is en v de waarde. Ik weet niet in hoeverre de intersectie gedeeld door de vereniging van 2 van dergelijke sets bijdraagt aan wat TS zoekt, maar dat is dan ook het probleem opzich... waar slaat de factor 2 trouwens op?

Tja, domeinkennis is hier essentieel. De TS had z'n arrays gesorteerd, wat suggereert dat volgorde niet van belang is.

De factor 2 is een simpele schaling zodat f(V,V)=1. Overigens is de formule niet perfect, omdat f(∅,∅) niet gedefinieerd is. Dat is wel enigzins logisch, want f(V,V)=1 en f(V,∅)=0 voor V≠∅

[.oisyn]

FYI: ∅ = Ø = { } = een lege verzameling

offtopic:
Die char zit overigens niet in m'n font

[ Voor 192% gewijzigd door .oisyn op 05-10-2007 00:26 ]

[EdwinV]

MrHuge schreef op donderdag 04 oktober 2007 @ 16:55:
[...]

De maximale LD tussen 2 arrays is gelijk aan de lengte van de langste van die 2 arrays, dus het omzetten naar een percentage kan als volgt:

Java:

distance = LevenshteinDistance(array1, array2);
percentage = (distance * 100) / maximum(length(array1), length(array2));

Dat klinkt inderdaad erg logisch. Ik heb het geïmplementeerd en er enkele tests over heen gehaald. De uitkomsten zien er prima uit.

Mijn huidige oplossing is de volgende:

Ruby:

def compare_array(first, second)
  return 0 if first.empty? or second.empty?
  t = (first.uniq+second.uniq)
  (t.length - t.uniq.length) / [first.length, second.length].max.to_f
end

De tip van .oisyn om rechtstreeks de dubbele elementen te nemen zorgt ervoor dat de code stukken minder complex is.

Bedankt voor alle antwoorden en tips!