मिनहैश

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

जैकार्ड सूची दो समुच्चयो के बीच समानता का सामान्यतः उपयोग किया जाने वाला संकेतक है। माना U समुच्चय हो और A और B के उपसमुच्चय U हों , तो जैकार्ड सूची को उनके प्रतिच्छेदन (समुच्चय सिद्धांत) के तत्वों की संख्या और उनके संघ (समुच्चय सिद्धांत) के तत्वों की संख्या के अनुपात के रूप में परिभाषित किया गया है ।

जैककार्ड समानता और न्यूनतम हैश मान

जैकार्ड सूची दो समुच्चयो के बीच समानता का सामान्यतः उपयोग किया जाने वाला संकेतक है। माना U समुच्चय हो और A और B के उपसमुच्चय U हों , तो जैकार्ड सूची को उनके प्रतिच्छेदन (समुच्चय सिद्धांत) के तत्वों की संख्या और उनके संघ (समुच्चय सिद्धांत) के तत्वों की संख्या के अनुपात के रूप में परिभाषित किया गया है ।

$J(A,B)={{|A\cap B|} \over {|A\cup B|}}.$

यह मान 0 है जब दो समुच्चय अलग समुच्चय होते हैं । जब वे समान होते हैं, और सख्ती से 0 और 1 के बीच अन्यथा दो समुच्चय अधिक समान होते हैं (अर्थात अपेक्षाकृत अधिक सदस्य होते हैं) जब उनका जैकार्ड सूची 1 के निकट होता है। मिनहैश J(A,B) का लक्ष्य अनुमान लगाना है। शीघ्रता से, प्रतिच्छेदन और संघ की स्पष्ट रूप से गणना किए बिना किया जाता है।

माना h हैश फलन हो जो सदस्यों U को मैप करता हो भिन्न पूर्णांकों के लिए मैप करता है । मान लीजिए पर्म समुच्चय के तत्वों का यादृच्छिक क्रमपरिवर्तन U हो , और किसी भी सबसेट के लिए S का U परिभाषित करता है । h_min(S) का न्यूनतम सदस्य होना S इसके संबंध में h ∘ perm—अर्थात् के न्यूनतम मूल्य के साथ S का सदस्य x है । h(perm(x)). (ऐसे स्थितियों में जहां उपयोग किए गए हैश फलन को छद्म-यादृच्छिक गुण माना जाता है, यादृच्छिक क्रमचय का उपयोग नहीं किया जाएगा।)।

अब, A और B दोनों के लिए h_min प्रयुक्त करना, और कोई हैश टकराव नहीं मानते हुए, हम देखते हैं कि मान समान हैं। (h_min(A) = h_min(B)) यदि और केवल यदि $A\cup B$ के सभी तत्वों के साथ तत्व न्यूनतम हैश मान प्रतिच्छेदन $A\cap B$ में निहित है। इसके सही होने की संभावना वास्तव में जैकार्ड सूची है। इसलिए:

Pr[ h_min(A) = h_min(B) ] = J(A,B),

अर्थात्, संभावना है कि h_min(A) = h_min(B) सत्य है। समानता J(A,B) के समान है जो एक समान वितरण से ड्राइंग perm को मानता है। दूसरे शब्दों में, यदि r यादृच्छिक चर है। जो एक है जब h_min(A) = h_min(B) और अन्यथा शून्य है, तो r J(A,B) का निष्पक्ष अनुमानक है। r का प्रसरण इतना अधिक है कि स्वयं जैककार्ड समानता के लिए उपयोगी अनुमानक नहीं बन सकता क्योंकि r सदैव शून्य या एक होता है। मिनहाश योजना का विचार एक ही तरह से निर्मित कई चरों को एक साथ जोड़कर इस भिन्नता को कम करना है।

एल्गोरिथम

कई हैश फलन के साथ संस्करण

मिनहाश पद्धति k का सबसे सरल संस्करण उपयोग करता है। विभिन्न हैश फलन, जहाँ k निश्चित पूर्णांक मापदंड है, और प्रत्येक समुच्चय का प्रतिनिधित्व करता है। S से k का मान h_min(S) इन के लिए k फलन करता है।

अनुमान लगाने के लिए J(A,B) पद्धति के इस संस्करण का उपयोग करते हुए, आइए y हैश फलन की संख्या हो जिसके लिए h_min(A) = h_min(B), और उपयोग करें y/k अनुमान के रूप में यह अनुमान का औसत है । k विभिन्न 0-1 यादृच्छिक चर, जिनमें h_min(A) = h_min(B) से प्रत्येक एक जब है और शून्य अन्यथा, और जिनमें से प्रत्येक का J(A,B) निष्पक्ष अनुमानक है। इसलिए, उनका औसत भी निष्पक्ष अनुमानक है, और 0-1 यादृच्छिक चर के योग के लिए मानक विचलन द्वारा, इसकी अपेक्षित O(1/√k) त्रुटि है।

इसलिए, किसी भी स्थिरांक k = O(1/ε²) के लिए ε > 0 नियतांक है। जैसे अनुमान की अपेक्षित त्रुटि अधिक से अधिक ε होती है। उदाहरण के लिए,.05 से कम या उसके समान अपेक्षित त्रुटि के साथ J(A,B) अनुमान लगाने के लिए 400 हैश की आवश्यकता होती है।

एकल हैश फलन के साथ संस्करण

यह कई हैश फलन की गणना करने के लिए कम्प्यूटेशनल रूप से महंगा हो सकता है। किन्तु मिनहाश पद्धति का संबंधित संस्करण केवल एक हैश फलन का उपयोग करके इस दंड से बचा जाता है और इसका उपयोग प्रत्येक हैश फलन के लिए केवल न्यूनतम मान का चयन करने के अतिरिक्त प्रत्येक समुच्चय से कई मानों का चयन करने के लिए करता है। माना h हैश फलन है और निश्चित पूर्णांक है। यदि S k का कोई समुच्चय है या अधिक मान के डोमेन में h, परिभाषित करना h_(k)(S) का सबसेट होना k के सदस्यों S जिसके सबसे छोटे मान h हैं। यह उपसमुच्चय h_(k)(S) समुच्चय S के लिए हस्ताक्षर के रूप में प्रयोग किया जाता है और किन्हीं दो समुच्चयो की समानता का अनुमान उनके हस्ताक्षरों की तुलना करके लगाया जाता है।

विशेष रूप से, A और B को कोई भी दो समुच्चय होने दें। तब X = h_(k)(h_(k)(A) ∪ h_(k)(B)) = h_(k)(A ∪ B) k तत्वों का समुच्चय A ∪ B है , और यदि h यादृच्छिक फलन है तो k तत्वों के किसी उपसमुच्चय के चुने जाने की समान संभावना है। जो कि X A ∪ B का साधारण यादृच्छिक प्रतिरूप है। उपसमुच्चय Y = X ∩ h_(k)(A) ∩ h_(k)(B) के सदस्यों का समुच्चय है जो प्रतिच्छेदन X के हैं जो A ∩ B से संबंधित हैं। इसलिए, |Y|/k J(A,B) का निष्पक्ष अनुमानक है। इस अनुमानक और एकाधिक हैश फलन द्वारा उत्पादित अनुमानक के बीच का अंतर यह है कि X सदैव k सदस्य स्पष्ट होता है, जबकि कई हैश फलन से प्रतिरूप तत्वों की छोटी संख्या हो सकती है। इस संभावना के कारण कि दो अलग-अलग हैश फलन में एक ही मिनिमा हो सकती है। चूँकि, जब k समुच्चय के आकार के सापेक्ष छोटा है, यह अंतर नगण्य है।

प्रतिस्थापन के बिना प्रतिरूप के लिए मानक चेरनॉफ़ सीमा से, इस अनुमानक ने त्रुटि की अनुमान O(1/√k) की है। बहु-हैश-फलन पद्धति के प्रदर्शन का मिलान होता है।

समय विश्लेषण

अनुमानक |Y|/k की गणना समय O(k) पर की जा सकती है। दिए गए समुच्चय के दो हस्ताक्षरों से, पद्धति के किसी भी प्रकार में इसलिए, जब ε और k स्थिरांक हैं। हस्ताक्षरों से अनुमानित समानता की गणना करने का समय भी स्थिर है। प्रत्येक समुच्चय के हस्ताक्षर की गणना समुच्चय के आकार पर रैखिक समय में की जा सकती है। इसलिए जब कई जोड़ीदार समानताओं का अनुमान लगाने की आवश्यकता होती है, तो इस विधि से प्रत्येक समुच्चय के सदस्यों की पूर्ण तुलना करने की तुलना में चलने के समय में पर्याप्त बचत हो सकती है। विशेष रूप से, समुच्चय आकार के लिए n अनेक हैश वैरिएंट O(n k) समय लेता है। सिंगल हैश वैरिएंट आम तौर पर तेज़ होता है, जिसमें n >> k मानने वाले न्यूनतम हैश मानों की कतार बनाए रखने के लिए O(n) समय की आवश्यकता होती है।

वजन सम्मिलित करना

मिनहैश की गणना में वज़न प्रस्तुत करने के लिए कई तरह की विधियों का विकास किया गया है। सरलतम इसे पूर्णांक भार तक बढ़ाता है।

हमारे हैश फलन का विस्तार करें । h समुच्चय सदस्य और पूर्णांक दोनों को स्वीकार करने के लिए, फिर प्रत्येक आइटम के लिए उसके वजन के अनुसार कई हैश उत्पन्न करें। यदि आइटम i घटित होना n बार, हैश $h(i,1),h(i,2),\ldots ,h(i,n)$ उत्पन्न करता है। हैश के इस विस्तारित समुच्चय पर मूल एल्गोरिथम चलाएं ऐसा करने से टक्कर की संभावना के रूप में जैकार्ड सूची जैककार्ड समानता और दूरी प्राप्त होती है।

$J_{\mathcal {W}}(x,y)={\frac {\sum _{i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}}$

उत्तम रनटाइम के साथ वास्तविक भार पर इस टकराव की संभावना को प्राप्त करने वाले और विस्तार विकसित किए गए हैं। सघन डेटा के लिए, और दूसरा विरल डेटा के लिए उपयोग किया जाता है।

एक्सटेंशन का और समूह तेजी से वितरित हैश का उपयोग करता है। 0 और 1 के बीच समान रूप से यादृच्छिक हैश को व्युत्क्रम परिवर्तन प्रतिरूप द्वारा घातीय वितरण का पालन करने के लिए परिवर्तित किया जा सकता है। यह विधि एक्सपोनेंशियल डिस्ट्रीब्यूशन के कई खूबसूरत गुणों का फायदा उठाती है। न्यूनतम एक्सपोनेंशियल रैंडम वेरिएबल्स का वितरण होता है।

$H(x)={\underset {i}{\operatorname {arg\,min} }}{\frac {-\log(h(i))}{x_{i}}}$

इससे टक्कर की संभावना के रूप में जैककार्ड सूची प्रायिकता जैकार्ड समानता और दूरी प्राप्त होती है।

$J_{\mathcal {P}}(x,y)=\sum _{x_{i}\neq 0 \atop y_{i}\neq 0}{\frac {1}{\sum _{j}\max \left({\frac {x_{j}}{x_{i}}},{\frac {y_{j}}{y_{i}}}\right)}}$

न्यूनतम स्वतंत्र क्रमपरिवर्तन

जैसा कि ऊपर बताया गया है, मिनहैश पद्धति को प्रयुक्त करने के लिए हैश फलन h की आवश्यकता होती है। यादृच्छिक क्रमचय को परिभाषित करने के लिए n तत्व, जहां n तुलना किए जाने वाले सभी समुच्चयो के संघ में अलग-अलग तत्वों की कुल संख्या है। किन्तु क्योंकि हैं n! विभिन्न क्रमपरिवर्तन, इसकी आवश्यकता होगी Ω(n log n) बिट्स वास्तव में यादृच्छिक क्रमचय निर्दिष्ट करने के लिए, यहां तक ​​​​कि मध्यम मूल्यों के लिए अविश्वसनीय रूप से बड़ी संख्या n. इस तथ्य के कारण, सार्वभौमिक हैशिंग के सिद्धांत के अनुरूप, क्रमचय के समूह को खोजने पर महत्वपूर्ण काम किया गया है। जो कि न्यूनतम स्वतंत्र है, जिसका अर्थ है कि डोमेन के किसी भी उपसमुच्चय के लिए, कोई भी तत्व समान रूप से न्यूनतम होने की संभावना है। यह स्थापित किया गया है कि क्रमपरिवर्तन के न्यूनतम स्वतंत्र समूह में कम से कम सम्मिलित होना चाहिए।

$\operatorname {lcm} (1,2,\cdots ,n)\geq e^{n-o(n)}$

विभिन्न क्रमपरिवर्तन, और इसलिए इसकी Ω(n) आवश्यकता है। बिट्स एकल क्रमचय निर्दिष्ट करने के लिए, अभी भी अव्यवहारिक रूप से बड़ा है।

व्यावहारिक न्यूनतम स्वतंत्र हैश फलन

उपरोक्त अव्यावहारिकता के कारण, न्यूनतम स्वतंत्रता के दो भिन्न विचारों को प्रस्तुत किया गया है। प्रतिबंधित न्यूनतम स्वतंत्र क्रमपरिवर्तन समूह और अनुमानित न्यूनतम स्वतंत्र समूह प्रतिबंधित न्यूनतम स्वतंत्रता न्यूनतम स्वतंत्रता प्रोपर्टी है। जो कार्डिनैलिटी k के कुछ समुच्चयो तक सीमित है।

अनुमानित न्यूनतम स्वतंत्रता की अधिक से अधिक निश्चित ε पूर्ण स्वतंत्रता से भिन्न संभावना होती है।

1999 में पीटर इंडिक सिद्ध हुए। कि कोई भी के-इंडिपेंडेंट_हैशिंग|के हैश फलन का स्वतंत्र समूह भी लगभग न्यूनतम $k$ स्वतंत्र है। बहुत पर्याप्त विशेष रूप से,$c,c'>0$ स्थिरांक होते हैं। ऐसा कि यदि $k\geq c\log {\tfrac {1}{\epsilon }}$, तब

$\Pr _{h\in {\mathcal {H}}}[h(x)<\min h(X)]={\frac {1}{|X|+1}}(1\pm \epsilon ),$

सभी समुच्चयो के लिए $|X|\leq \epsilon nc'$ और $x\in X$. (ध्यान दें, यहाँ $(1\pm \epsilon )$ इसका कारण है कि संभावना अधिक से अधिक कारक है। $1+\epsilon$ बहुत बड़ा, और अधिक से अधिक $1-\epsilon$ बहुत छोटा।)

यह गारंटी, अन्य बातों के अतिरिक्त, मिनहैश एल्गोरिथम द्वारा आवश्यक जैककार्ड बाउंड देने के लिए पर्याप्त है। अर्थात यदि $A$ और $B$ समुच्चय हैं। फिर

$\Pr _{h\in {\mathcal {H}}}[\min h(A)=\min h(B)]={\frac {|A\cap B|}{|A\cup B|}}\pm \epsilon .$

चूंकि के-इंडिपेंडेंट हाशिंग के स्वतंत्र हैश फलन $k\log n$ बिट्स को बस का उपयोग करके निर्दिष्ट किया जा सकता है। यह दृष्टिकोण पूरी तरह न्यूनतम स्वतंत्र क्रमपरिवर्तन का उपयोग करने से कहीं अधिक व्यावहारिक है।

हैश फलन का अन्य व्यावहारिक समूह जो लगभग न्यूनतम स्वतंत्रता देता है। सारणीयन हैशिंग है।

अनुप्रयोग

मिनहाश के लिए मूल अनुप्रयोगों में वेब दस्तावेज़ों के बीच क्लस्टरिंग और निकट-प्रतिरूप को समाप्त करना सम्मिलित था। जो उन दस्तावेज़ों में आने वाले शब्दों के समुच्चय के रूप में दर्शाए गए थे। अन्य प्रकार के डेटा के लिए क्लस्टरिंग और निकट-प्रतिरूप उन्मूलन के लिए भी इसी तरह की विधियों का उपयोग किया गया है। जैसे कि छवियां छवि डेटा के स्थिति में, छवि को छोटे सबइमेज के समुच्चय के रूप में या उससे अधिक के समुच्चय के रूप में दर्शाया जा सकता है। जटिल छवि सुविधा विवरण डाटा माइनिंग में, कोहेन et al. (2001) एसोसिएशन नियम सीखना के लिए टूल के रूप में मिनहैश का उपयोग करें। डेटाबेस को देखते हुए जिसमें प्रत्येक प्रविष्टि में कई विशेषताएँ होती हैं ( तार्किक आव्यूह के रूप में देखा जाता है। 0-1 आव्यूह पंक्ति प्रति डेटाबेस प्रविष्टि और स्तंभ प्रति विशेषता के साथ) वे उम्मीदवारों के जोड़े की पहचान करने के लिए जैकार्ड सूची के लिए मिनहैश-आधारित सन्निकटन का उपयोग करते हैं। अधिकांशतः सह-होता है, और उसके बाद केवल उन जोड़े के लिए सूचकांक के स्पष्ट मूल्य की गणना करें जिनकी सह-घटना की आवृत्ति निश्चित सीमा से नीचे है।

मिनहैश एल्गोरिदम को जैव सूचना विज्ञान के लिए अनुकूलित किया गया है। जहां जीनोम अनुक्रमों की तुलना करने की समस्या वेब पर दस्तावेजों की तुलना करने के समान सैद्धांतिक आधार है। मिनहैश-आधारित उपकरण संदर्भ जीनोम के साथ पूरे जीनोम अनुक्रमण डेटा की तेजी से तुलना की अनुमति दें (संदर्भ में 90000 जीनोम के साथ जीनोम की तुलना करने के लिए लगभग 3 मिनट), और अटकलों के लिए उपयुक्त हैं और संभवतः माइक्रोबियल उप-टाइपिंग की सीमित डिग्री मेटाजेनोमिक्स के लिए भी आवेदन हैं और जीनोम संरेखण और जीनोम असेंबली के लिए मिनहैश व्युत्पन्न एल्गोरिदम का उपयोग करते है। स्पष्ट औसत न्यूक्लियोटाइड पहचान (एएनआई) मूल्यों को मिनहाश-आधारित एल्गोरिदम के साथ बहुत कुशलतापूर्वक उत्पन्न किया जा सकता है।

अन्य उपयोग

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

मूल्यांकन और बेंचमार्क

2006 में गूगल द्वारा बड़े मापदंड पर मूल्यांकन किया गया था। मिनहैश और सिमहैश के प्रदर्शन की तुलना करने के लिए एल्गोरिदम 2007 में गूगल ने वेब क्रॉलिंग के लिए प्रतिरूप डिटेक्शन के लिए सिम्हाश का उपयोग करने की सूचना दी थी और गूगल समाचार वैयक्तिकरण के लिए मिन्हाश और लोकैलिटी-सेंसिटिव हैशिंग का उपयोग करता है।

यह भी देखें

• ब्लूम फिल्टर
• काउंट-मिन स्केच
• डब्ल्यू-शिंगलिंग