Изчислете приликата между два списъка

Бих искал да изчисля приликата между два списъка с различна дължина.

eg:

listA = ['apple', 'orange', 'apple', 'apple', 'banana', 'orange'] # (length = 6)
listB = ['apple', 'orange', 'grapefruit', 'apple'] # (length = 4)

както можете да видите, един елемент може да се появи няколко пъти в списък, а дължините са с различни размери.

Вече мислех да сравня честотите на всеки елемент, но това не обхваща размера на всеки списък (списък, който е просто два пъти по-голям от друг списък, трябва да е подобен, но не напълно подобен)

eg2:

listA = ['apple', 'apple', 'orange', 'orange']
listB = ['apple', 'orange']
similarity(listA, listB) # should NOT equal 1

Така че основно искам да обхвана размера на списъците и разпределението на елементите в списъка.

Някакви идеи?


python set algorithm similarity
person kmace    schedule 06.02.2013    source източник
comment
Това са списъци, а не комплекти.   -  person Martijn Pieters    schedule 06.02.2013
comment
Под similarity имате предвид да създадете трети списък, който съдържа елементите, които се появяват както в listA, така и в listB? така че резултатът във вашия случай да бъде ['apple', 'orange']?   -  person Konsol Labapen    schedule 06.02.2013
comment
под сходство имам предвид някаква мярка за това колко си приличат. така че сравняването на 2 идентични комплекта (или списък) ще ви даде резултат 1, а 2 напълно различни набора ще ви дадат нула. тези набори обаче са различни по размер и могат да съдържат повтарящи се елементи   -  person kmace    schedule 06.02.2013

Отговори (3)


arrow_upward
27
arrow_downward

Използвайте collections.Counter() може би; това са мулти-набори или чанти, на езика на типа данни:

from collections import Counter

counterA = Counter(listA)
counterB = Counter(listB)

Сега можете да ги сравните по записи или честоти:

>>> counterA
Counter({'apple': 3, 'orange': 2, 'banana': 1})
>>> counterB
Counter({'apple': 2, 'orange': 1, 'grapefruit': 1})
>>> counterA - counterB
Counter({'orange': 1, 'apple': 1, 'banana': 1})
>>> counterB - counterA
Counter({'grapefruit': 1})

Можете да изчислите тяхната косинусова прилика, като използвате:

import math

def counter_cosine_similarity(c1, c2):
    terms = set(c1).union(c2)
    dotprod = sum(c1.get(k, 0) * c2.get(k, 0) for k in terms)
    magA = math.sqrt(sum(c1.get(k, 0)**2 for k in terms))
    magB = math.sqrt(sum(c2.get(k, 0)**2 for k in terms))
    return dotprod / (magA * magB)

Което дава:

>>> counter_cosine_similarity(counterA, counterB)
0.8728715609439696

Колкото по-близо до 1 е тази стойност, толкова по-сходни са двата списъка.

Косинусното сходство е един резултат, който можете да изчислите. Ако ви интересува дължината на списъка, можете да изчислите друг; ако поддържате и този резултат между 0,0 и 1,0, можете да умножите двете стойности за краен резултат между -1,0 и 1,0.

Например, за да вземете предвид относителните дължини, можете да използвате:

def length_similarity(c1, c2):
    lenc1 = sum(c1.itervalues())
    lenc2 = sum(c2.itervalues())
    return min(lenc1, lenc2) / float(max(lenc1, lenc2))

и след това комбинирайте във функция, която приема списъците като входове:

def similarity_score(l1, l2):
    c1, c2 = Counter(l1), Counter(l2)
    return length_similarity(c1, c2) * counter_cosine_similarity(c1, c2)

За вашите два примерни списъка това води до:

>>> similarity_score(['apple', 'orange', 'apple', 'apple', 'banana', 'orange'], ['apple', 'orange', 'grapefruit', 'apple'])
0.5819143739626463
>>> similarity_score(['apple', 'apple', 'orange', 'orange'], ['apple', 'orange'])
0.4999999999999999

Можете да смесвате други показатели, ако е необходимо.

person Martijn Pieters    schedule 06.02.2013
comment
този вид работи, но ако разгледаме примера, където списък c1 е просто двоен брой на c2, тогава приликата все още е 1. така че не е точно това, което търся. все пак благодаря за кода. - person kmace; 06.02.2013
comment
@kamula: Това е отправна точка; ако cos приликата е 1, вижте дали единият има по-голям брой горни точки от другия (.most_common(1) на който и да е), за да коригирате и т.н. - person Martijn Pieters; 06.02.2013
comment
Ако не искате нормализираният по дължина резултат, който осигурява косинусното разстояние, можете да изчислите евклидовото разстояние между двата списъка - person duhaime; 17.12.2014

arrow_upward
1
arrow_downward

От теоретична гледна точка: Препоръчвам ви да потърсите косинусово сходство http://en.wikipedia.org/wiki/Cosine_similarity

Може да се наложи да промените, за да пасне на вашата схема, но идеята за косинус подобие е страхотна.

person Vigneshwaren    schedule 06.02.2013

arrow_upward
0
arrow_downward

Вярвам, че това, което търсите, е да преброите броя на инверсиите в масив. Въпросът има вашия отговор: Броене на инверсии в масив

person Computernerd    schedule 06.02.2013
comment

Не виждам къде заглавката HumanPlayer.h включва дефиниция на клас Player.

- person kmace; 06.02.2013