वैक्टरों के सेट में सबसे अच्छी कोसाइन समानता ढूँढना

Question

मेरे पास एन वैक्टर हैं, प्रत्येक एम तत्वों (वास्तविक संख्या) के साथ। मैं जोड़ी ढूंढना चाहता हूं जहां सभी जोड़ों में कोसाइन समानता अधिकतम है।

सीधा समाधान के लिए ओ (एन मीटर) समय की आवश्यकता होगी।

क्या कोई बेहतर समाधान है?

अद्यतन

Cosine similarity/distance and triangle equation मुझे प्रेरित है कि मैं के साथ "तार की लंबाई" जो परिशुद्धता खो देता है, लेकिन बढ़ जाती है एक बहुत तेजी लाने "कोज्या समानता" की जगह सकता है।

Answer 1

कोसाइन समानता sim(a,b)related to Euclidean distance|a - b| है

|a - b|² = 2(1 - sim(a,b)) 

द्वारा इकाई वैक्टर a और b के लिए (वहाँ कई मौजूदा समाधान मीट्रिक स्थान में निकटतम पड़ोसी को सुलझाने ANN की तरह, कर रहे हैं)।

इसका मतलब है कि कोसाइन समानता सबसे बड़ी है जब एल 2 मानदंड द्वारा सामान्यीकृत करने के बाद यूक्लिडियन दूरी सबसे छोटी होती है, और समस्या closest pair of points problem तक कम हो जाती है, जिसे ओ (एन एलजी एन) समय में हल किया जा सकता है।

Answer 2

आप प्रोजेक्ट सिम्बेस https://github.com/guokr/simbase के साथ जांच सकते हैं, यह एक वेक्टर समानता nosql डेटाबेस है।

Simbase अवधारणाओं नीचे का उपयोग करें:

• वेक्टर सेट: वैक्टर का एक सेट
• आधार: वैक्टर के लिए आधार, एक वेक्टर सेट में वैक्टर एक ही आधार
• सिफारिश की है: एक एक दिशा बाइनरी दो वेक्टर सेटों के बीच संबंध जो समान आधार हैं

आप सीधे प्रशासन कार्यों के लिए रेडिस-क्ली का उपयोग कर सकते हैं, या आप अलग-अलग भाषा में रेडिस क्लाइंट बाइंडिंग का उपयोग कर सकते हैं एक प्रोग्रामिंग तरीके से rectly। यहां एक पायथन उदाहरण

import redis 

    dest = redis.Redis(host='localhost', port=7654) 
    schema = ['a', 'b', 'c'] 
    dest.execute_command('bmk', 'ba', *schema) 
    dest.execute_command('vmk', 'ba', 'va') 
    dest.execute_command('rmk', 'va', 'va', 'cosinesq')