उच्च आयाम निकटतम पड़ोसी खोज और लोकैलिटी संवेदनशीलता हैशिंग

Question

यहां मुख्य समस्या है। मेरे पास 48 आयामी वैक्टरों का बहुत बड़ा डेटाबेस (25,000 या उससे अधिक) है, प्रत्येक 0-255 से लेकर मानों के साथ आबादी वाला है। विनिर्देश इतना महत्वपूर्ण नहीं हैं लेकिन मुझे लगता है कि यह संदर्भ देने में मदद कर सकता है।

मुझे निकटतम पड़ोसी की आवश्यकता नहीं है, इसलिए अनुमानित पड़ोसी खोज सटीकता की डिग्री के भीतर स्वीकार्य हैं। मैं Locality Sensitivity Hashing के साथ घूम रहा हूं लेकिन मैं बहुत खो गया हूं।

मैंने "स्थिर वितरण" के तहत आलेख में वर्णित एक हैश फ़ंक्शन लिखा है जैसा कि मैं कर सकता हूं। कोड यहाँ है।

def lsh(vector, mean, stdev, r = 1.0, a = None, b = None): 
if not a: 
    a = [normalvariate(mean, stdev) for i in range(48)] 
if not b: 
    b = uniform(0, r) 
hashVal = (sum([a[i]*vectorA[i] for i in range(48)]) + b)/r 
return hashVal 

हैशिंग फ़ंक्शन कम से कम कुछ 'काम कर रहा है'। यदि मैं हैश मान द्वारा बिंदुओं की एक सूची ऑर्डर करता हूं और किसी बिंदु और उसके पड़ोसी के बीच औसत दूरी की गणना करता हूं, तो औसत दूरी लगभग 400 है, जो किसी भी दो यादृच्छिक रूप से चयनित बिंदुओं के लिए लगभग 530 की औसत दूरी की तुलना में होती है।

मेरे सबसे बड़े प्रश्न ये हैं।

ए: कोई सुझाव जहां मैं इसके बारे में और अधिक पढ़ सकता हूं। मेरी खोज ने बहुत सारे नतीजे नहीं दिए हैं।

बी: विधि बताती है कि यह एक पूर्णांक मान (जो मेरा नहीं है) आउटपुट करता है। और फिर आप इस पूर्णांक मूल्य के लिए मिलान खोजने की कोशिश कर रहे हैं और एक मैच संभावित निकटतम पड़ोसी को दर्शाता है। मैं समझता हूँ कि मैं अपने सभी बिंदुओं के लिए हैश मैचों के लिए टेबल हैश मान की टेबल के कुछ सेट की गणना और फिर जाँच कहा करने वाला हूँ, लेकिन मूल्यों मैं लौट रहा हूँ काफी ठीक है कि मैं के साथ पहुंच जाएंगे होने लगते नहीं है बिल्कुल मेल खाता है। मेरे हिस्से पर अधिक परीक्षण की आवश्यकता है।

सी: अन्य हैशिंग विधियों के आधार पर हैश फ़ंक्शंस बनाने के निर्देशों पर निर्देश?

Answer 1

Maby यह एक छोटे से बंद विषय है, लेकिन आप डेटासेट के आयामी स्वरूप को कम करने के लिए पीसीए http://en.wikipedia.org/wiki/Principal_component_analysis उपयोग करने का प्रयास कर सकते हैं। NumPy के लिए डिज़ाइन किए गए बहुत सारे पीसीए मॉड्यूल होना चाहिए (उदाहरण के लिए: http://folk.uio.no/henninri/pca_module/)। विधि सरल है और मॉड्यूल का उपयोग करने के लिए तैयार है यह एक तस्वीर होगी।

मूल रूप से यह क्या करता है आयामों की दी गई संख्या के भीतर विचरण अधिकतम करके आयाम की संख्या (आप इच्छित संख्या निर्दिष्ट करने के लिए सक्षम होना चाहिए) को कम है।

बी: विकिपीडिया पृष्ठ इंगित करता है कि math.floor()hashVal पर इस्तेमाल किया जाना चाहिए: यह कैसे आप पूर्णांक प्राप्त है

Answer 2

यहाँ दो जवाब हैं।

सी: आप आलोचनात्मक विधि का उपयोग करना चाहते हैं, तो आप यह काफी बस को लागू कर सकते हैं: प्रत्येक आलोचनात्मक हैश फंक्शन बस एक समन्वय (0 और 47 के बीच) और थोड़ा संख्या से परिभाषित किया गया है (0 और के बीच 7) ।

bool(i & 2**b)