वेक्टर की कोज्या समानता, साथ <O (n^2) जटिलता

इसी तरह के मुद्दों के लिए इस साइट चारों ओर देखा, मैं इस पाया: http://math.nist.gov/javanumerics/jama/ और इस: http://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html वेक्टर की कोज्या समानता, साथ <O (n^2) जटिलता

हालांकि, यह इन हे में चलाने (एन लगता है^2)। मैं कुछ दस्तावेज क्लस्टरिंग कर रहा हूं और देखा कि छोटे दस्तावेज़ सेटों से निपटने के दौरान जटिलता का यह स्तर व्यवहार्य नहीं था। डॉट उत्पाद के लिए, हमें केवल दोनों वैक्टरों में निहित वेक्टर शब्दों की आवश्यकता होती है, यह वैक्टर को पेड़ में रखना संभव है और इस प्रकार डॉट उत्पाद को एन लॉग एन जटिलता के साथ गणना करना चाहिए, जहां एन सबसे कम संख्या में अद्वितीय शब्द है 2 दस्तावेजों में से 1।

क्या मुझे कुछ याद आ रही है? क्या कोई जावा पुस्तकालय है जो यह करता है?

धन्यवाद

स्रोत

2010-07-27 Ash

आपको उन सभी पृष्ठों को पढ़ने की उम्मीद करने की बहुत उम्मीद नहीं होगी। शायद आप अपनी समस्या को और अधिक स्पष्ट रूप से समझा सकते हैं - आप वैक्टरों को गुणा क्यों कर रहे हैं (और आपका क्या मतलब है, ओ (एन^2)? दो एन-आयामी वैक्टरों के डॉट-उत्पाद की गणना करना मुश्किल है ओ (एन), मुझे किसी पर संदेह है वेक्टर पैकेज उस बुरी तरह खराब हो सकता है) –

वह दस्तावेजों के हर * जोड़ी * के लिए डॉट उत्पाद की गणना कर रहा है। यह इसे चौकोर रूप से जटिल बनाता है। – Rekin

ब्लूराजा - डैनी पीएफएलयूघोफ्ट, यह समस्या बहुत बड़े-आयामी लेकिन बहुत अस्पष्ट वैक्टरों को गुणा करने के बारे में है; और n आयाम नहीं है लेकिन गैर-शून्य तत्वों की गिनती है। –

आप एक hashtable में वेक्टर तत्व संग्रहीत करते हैं, देखने ही लॉग ऑन n वैसे भी है, नहीं? छोटे दस्तावेज़ में सभी चाबियों पर लूप करें और देखें कि क्या वे बड़े में मौजूद हैं ..?

स्रोत

2010-07-27 18:13:05 Nicolas78

कोई भी वर्ग जो आप सुझाएंगे? मुझे लगता है कि यह एक बहुत अच्छा है, अगर स्मृति एक मुद्दा है: http://www.java2s.com/Code/Java/Collections-Data-Structure/Amemoryefficienthashmap.htm – Ash

वाह इसे इतनी जल्दी से न्याय नहीं कर सकता है, लेकिन आप कर सकते हैं हमेशा शुरू करने के लिए एक सामान्य java.util.HashMap के साथ जाओ। बीटीडब्ल्यू क्योंकि आप कह रहे हैं कि यह दस्तावेज़ संग्रह आकार का प्रभाव है: यदि आप प्रत्येक दस्तावेज़ को प्रत्येक दस्तावेज़ में तुलना करते हैं, तो आपके पास (n * log n) शब्द के चारों ओर लिपटे एक और वर्गबद्ध शब्द (अब दस्तावेज़ों की संख्या में) है। मेरे लिए, यह हिस्सा अक्सर वास्तविक कोसाइन गणना से कहीं अधिक समस्याग्रस्त रहा है। क्या यह आपके लिए भी मामला हो सकता है? – Nicolas78

मैं तुलनात्मक रूप से तुलना करने के लिए क्लस्टर सेट पर ट्रिम कर रहा हूं, लेकिन जीएएचसी जैसे कुछ के लिए आप पूरी तरह से सही हैं, आपके पास एन^2 समस्या है, जहां एन की तुलना करने के लिए क्लस्टर की संख्या है। – Ash

हैशमैप अच्छा है, लेकिन इसमें बहुत मेमोरी लग सकती है।

यदि आपके वैक्टर कुंजी द्वारा क्रमबद्ध कुंजी-मूल्य जोड़े के रूप में संग्रहीत किए जाते हैं तो वेक्टर गुणा को ओ (एन) में किया जा सकता है: आपको केवल दोनों वैक्टरों पर समानांतर में पुनरावृत्ति करना होगा (उसी पुनरावृत्ति का उपयोग किया जाता है जैसे मर्ज सॉर्ट एल्गोरिदम)। गुणन के लिए स्यूडोकोड:

i = 0 
j = 0 
result = 0 
while i < length(vec1) && j < length(vec2): 
    if vec1[i].key == vec2[j].key: 
    result = result + vec1[i].value * vec2[j].value 
    else if vec1[i].key < vec2[j].key: 
    i = i + 1 
    else 
    j = j + 1

स्रोत

2010-07-27 19:22:05

मुझे यह विचार पसंद है, धन्यवाद। क्या कोई जावा लाइब्रेरी है जो इस सिद्धांत का उपयोग करती है? – Ash

मुझे नहीं पता; लेकिन लुसीन (http://lucene.apache.org/java/docs/index.html) में ऐसे एल्गोरिदम हो सकते हैं। –

धन्यवाद dmitry-vk, ऐसा लगता है कि एक क्रमबद्ध नक्शा शायद सबसे अच्छा होगा: http://java.sun.com/j2se/1.4.2/docs/api/java/util/SortedMap.html – Ash

आप केवल सीमित आइटम सिफारिश करने के लिए, उदाहरण के मीटर मदों के लिए, एन के आकार के साथ एक सेट में हर आइटम चाहते हैं, जटिलता n^2, लेकिन मीटर होने के लिए नहीं जरूरत * एन। चूंकि एम स्थिर है, जटिलता रैखिक है।

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

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

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

स्रोत

2014-06-12 15:14:53 Mountain

यदि आप इसी तरह के दस्तावेज़ों के क्लस्टर ढूंढने के तरीके के रूप में कोसाइन समानता का उपयोग करने की योजना बना रहे हैं, तो आप con साइडर locality-sensitive hashing में देख रहा है, एक हैश-आधारित दृष्टिकोण जिसे विशेष रूप से इस दिमाग में डिजाइन किया गया था। सहजता से, एलएसएच वैक्टर को इस तरह से धोता है कि उच्च संभावना के साथ समान बाल्टी और दूरस्थ तत्वों को समान बाल्टी में अलग-अलग तत्वों में रखा जाता है। एलएसएच योजनाएं हैं जो कोसाइन समानता का उपयोग अपनी अंतर्निहित दूरी के रूप में करती हैं, इसलिए क्लस्टर को खोजने के लिए आप चीजों को बाल्टी में छोड़ने के लिए एलएसएच का उपयोग करते हैं और फिर केवल उसी बाल्टी में तत्वों की जोड़ी की दूरी की गणना करते हैं। सबसे बुरे मामले में यह वर्गबद्ध होगा (यदि सब कुछ एक ही बाल्टी में पड़ता है), लेकिन यह अधिक संभावना है कि आपके पास काम में एक महत्वपूर्ण गिरावट होगी।

आशा है कि इससे मदद मिलती है!

स्रोत

2014-06-12 17:21:41 templatetypedef

वेक्टर की कोज्या समानता, साथ <O (n^2) जटिलता

उत्तर

संबंधित मुद्दे