दो सूचियों के बीच समानता की गणना करें

Question

मैं विभिन्न लंबाई की दो सूचियों के बीच समानता की गणना करना चाहता हूं।

जैसे:

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 

तो मैं मूल रूप से सूचियों के आकार को शामिल करना चाहता हूं, और सूची में वस्तुओं का वितरण करना चाहता हूं।

कोई विचार?

Answer 1

शायद collections.Counter() का उपयोग करें; उन बहु सेट, या बैग, डेटाप्रकार की भाषा में कर रहे हैं:

from collections import Counter 

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

अब आप प्रविष्टियों या आवृत्तियों से इन तुलना कर सकते हैं:

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) 

:

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

आप का उपयोग कर अपने कोज्या समानता गणना कर सकते हैं

जो देता है:

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

आप आवश्यकतानुसार अन्य मीट्रिक में मिश्रण कर सकते हैं।

Answer 2

देखने के एक सैद्धांतिक दृष्टिकोण से: मैं सुझाव है कि आप कोज्या समानता http://en.wikipedia.org/wiki/Cosine_similarity

देखो आप अपने योजना फिट करने के लिए संशोधित करने के लिए है, लेकिन कोज्या समानता के विचार बहुत अच्छा है।

Answer 3

मेरा मानना ​​है कि आप एक सरणी में व्युत्क्रम की संख्या की गिनती करने के लिए है के लिए क्या देख रहे सवाल अपने जवाब है: Counting inversions in an array