MinHash
कंप्यूटर विज्ञान और डेटा माइनिंग में, मिनहैश (या न्यूनतम-वार स्वतंत्र क्रमपरिवर्तन स्थानीय संवेदनशील हैशिंग योजना) यह जल्दी से अनुमान लगाने के लिए एक तकनीक है कि दो सेट कितने समान हैं। इस योजना का आविष्कार किया गया था, और शुरू में इसका उपयोग अल्ताविस्ता खोज इंजन में डुप्लिकेट वेब पृष्ठों का पता लगाने और उन्हें खोज परिणामों से हटाने के लिए किया गया था। इसे बड़े पैमाने पर क्लस्टरिंग समस्याओं में भी लागू किया गया है, जैसे कि क्लस्टरिंग दस्तावेज़ उनके शब्दों के सेट की समानता से। जैकार्ड समानता और न्यूनतम हैश मान जैकार्ड समानता गुणांक दो सेटों के बीच समानता का एक सामान्य रूप से उपयोग किया जाने वाला संकेतक है। मान लीजिए कि यह एक समुच्चय है और इसका उपसमुच्चय है, तो जैककार्ड सूचकांक को उनके प्रतिच्छेदन के तत्वों की संख्या और उनके संघ के तत्वों की संख्या के अनुपात के रूप में परिभाषित किया जाता हैः यह मान 0 है जब दो समुच्चय असंबद्ध होते हैं, 1 जब वे बराबर होते हैं, और अन्यथा सख्ती से 0 और 1 के बीच होता है। दो समूह अधिक समान हैं (अर्थात। समान रूप से अधिक सदस्य होते हैं) जब उनका जैककार्ड सूचकांक 1 के करीब होता है। मिनहैश का लक्ष्य प्रतिच्छेदन और संघ की स्पष्ट रूप से गणना किए बिना जल्दी से अनुमान लगाना है। मान लीजिए कि एक हैश फ़ंक्शन जो सदस्यों को अलग-अलग पूर्णांकों में मैप करता है, सेट के तत्वों का एक यादृच्छिक क्रमपरिवर्तन है, और परिभाषित के किसी भी सबसेट के लिए न्यूनतम सदस्य होने के संबंध में-यानी न्यूनतम मूल्य के साथ सदस्य। (ऐसे मामलों में जहां उपयोग किए गए हैश फ़ंक्शन में छद्म-यादृच्छिक गुण होते हैं, यादृच्छिक क्रमपरिवर्तन का उपयोग नहीं किया जाएगा।) अब, और दोनों पर लागू करते हुए, और यह मानते हुए कि कोई हैश टकराव नहीं है, हम देखते हैं कि मान बराबर हैं () यदि और केवल तभी जब सभी तत्वों के बीच, न्यूनतम हैश मूल्य वाला तत्व प्रतिच्छेदन में स्थित हो। इसके सही होने की संभावना बिल्कुल जैककार्ड सूचकांक है, इसलिएः एक समान वितरण से ड्राइंग मानते हुए, जो संभावना सच है वह समानता के बराबर है। दूसरे शब्दों में, यदि यादृच्छिक चर है जो एक है जब और शून्य अन्यथा, तो एक निष्पक्ष अनुमानक है। अपने आप में जैककार्ड समानता के लिए एक उपयोगी अनुमानक होने के लिए बहुत अधिक भिन्नता है, क्योंकि हमेशा शून्य या एक होता है। मिनहैश योजना का विचार एक ही तरह से निर्मित कई चरों को एक साथ औसत करके इस भिन्नता को कम करना है। कई हैश कार्यों के साथ एल्गोरिथम संस्करण मिन्हाश योजना का सबसे सरल संस्करण विभिन्न हैश कार्यों का उपयोग करता है, जहां एक निश्चित पूर्णांक पैरामीटर है, और इन कार्यों के लिए के मूल्यों द्वारा प्रत्येक सेट का प्रतिनिधित्व करता है। योजना के इस संस्करण का उपयोग करके अनुमान लगाने के लिए, आइए हैश कार्यों की संख्या के लिए, और अनुमान के रूप में उपयोग करें। यह अनुमान विभिन्न 0-1 यादृच्छिक चरों का औसत है, जिनमें से प्रत्येक एक है जब और शून्य अन्यथा, और जिनमें से प्रत्येक का एक निष्पक्ष अनुमानक है। इसलिए, उनका औसत भी एक निष्पक्ष अनुमानक है, और 0-1 यादृच्छिक चर के योग के लिए मानक विचलन द्वारा, इसकी अपेक्षित त्रुटि है। इसलिए, किसी भी स्थिरांक के लिए एक स्थिरांक ऐसा होता है कि अनुमान की अपेक्षित त्रुटि अधिक से अधिक हो। उदाहरण के लिए,. 05 से कम या उसके बराबर की अपेक्षित त्रुटि का अनुमान लगाने के लिए 400 हैश की आवश्यकता होगी। एकल हैश फ़ंक्शन के साथ भिन्नता एकाधिक हैश फ़ंक्शन की गणना करना कम्प्यूटेशनल रूप से महंगा हो सकता है, लेकिन मिनहैश योजना का एक संबंधित संस्करण केवल एक ही हैश फ़ंक्शन का उपयोग करके इस दंड से बचाता है और इसका उपयोग केवल एक एकल न्यूनतम मूल्य प्रति हैश फ़ंक्शन का चयन करने के बजाय प्रत्येक सेट से कई मूल्यों का चयन करने के लिए करता है। मान लीजिए कि यह एक हैश फ़ंक्शन है, और एक निश्चित पूर्णांक है। यदि के क्षेत्र में किसी भी या अधिक मूल्यों का समूह है, तो उन सदस्यों के उपसमुच्चय के रूप में परिभाषित करें जिनके सबसे छोटे मूल्य हैं। इस सबसेट का उपयोग सेट के लिए एक हस्ताक्षर के रूप में किया जाता है, और किसी भी दो सेट की समानता का अनुमान उनके हस्ताक्षर की तुलना करके लगाया जाता है। विशेष रूप से, ए और बी को कोई भी दो समूह होने दें। फिर के तत्वों का एक समूह है, और यदि एच एक यादृच्छिक फलन है तो के तत्वों के किसी भी उपसमुच्चय को चुने जाने की समान रूप से संभावना है; अर्थात, का एक सरल यादृच्छिक नमूना है। सबसेट उन सदस्यों का समूह है जो प्रतिच्छेदन से संबंधित हैं। इसलिए,।।/एक निष्पक्ष अनुमानक है। इस प्राक्कलनकर्ता और कई हैश कार्यों द्वारा उत्पादित प्राक्कलनकर्ता के बीच का अंतर यह है कि हमेशा बिल्कुल सदस्य होते हैं, जबकि कई हैश कार्यों से नमूने के तत्वों की संख्या कम हो सकती है क्योंकि इस संभावना के कारण कि दो अलग-अलग हैश कार्यों में एक ही मिनीमा हो सकता है। हालांकि, जब सेट के आकार के सापेक्ष छोटा होता है, तो यह अंतर नगण्य होता है। प्रतिस्थापन के बिना नमूने के लिए मानक चेरनोफ सीमा के अनुसार, इस अनुमानक ने त्रुटि की उम्मीद की है, जो मल्टीपल-हैश-फंक्शन योजना के प्रदर्शन से मेल खाती है। समय का विश्लेषण अनुमानक की गणना योजना के किसी भी प्रकार में दिए गए समुच्चय के दो हस्ताक्षरों से समय पर की जा सकती है। इसलिए, कब और कब स्थिर हैं, हस्ताक्षरों से अनुमानित समानता की गणना करने का समय भी स्थिर है। प्रत्येक सेट के हस्ताक्षर की गणना सेट के आकार पर रैखिक समय में की जा सकती है, इसलिए जब कई जोड़ीदार समानताओं का अनुमान लगाने की आवश्यकता होती है तो इस विधि से प्रत्येक सेट के सदस्यों की पूरी तुलना करने की तुलना में चलने के समय में पर्याप्त बचत हो सकती है। विशेष रूप से, सेट आकार के लिए कई हैश संस्करणों में समय लगता है। एकल हैश संस्करण आम तौर पर तेज होता है, जिसमें न्यूनतम हैश मूल्यों की कतार को बनाए रखने के लिए समय की आवश्यकता होती है। भार को शामिल करना मिनहैश की गणना में भार को शामिल करने के लिए विभिन्न तकनीकों का विकास किया गया है। सबसे सरल इसे पूर्णांक भार तक विस्तारित करता है। एक सेट सदस्य और एक पूर्णांक दोनों को स्वीकार करने के लिए हमारे हैश फ़ंक्शन का विस्तार करें, फिर प्रत्येक वस्तु के लिए उसके वजन के अनुसार कई हैश उत्पन्न करें। यदि वस्तु समय पर आती है, तो हैश उत्पन्न करें। हैश के इस विस्तारित सेट पर मूल एल्गोरिथ्म चलाएँ। ऐसा करने से टक्कर की संभावना के रूप में भारित जैकार्ड सूचकांक प्राप्त होता है। आगे के विस्तार जो बेहतर रनटाइम के साथ वास्तविक भार पर इस टकराव की संभावना को प्राप्त करते हैं, विकसित किए गए हैं, एक घने डेटा के लिए और दूसरा विरल डेटा के लिए। एक्सटेंशन का एक अन्य परिवार तेजी से वितरित हैश का उपयोग करता है। 0 और 1 के बीच एक समान यादृच्छिक हैश को सी. डी. एफ. व्युत्क्रम द्वारा एक घातीय वितरण का पालन करने के लिए परिवर्तित किया जा सकता है। यह विधि घातीय चर के न्यूनतम समूह के कई सुंदर गुणों का फायदा उठाती है। जैसा कि ऊपर वर्णित है, मिनहैश योजना को लागू करने के लिए, तत्वों पर एक यादृच्छिक क्रमपरिवर्तन को परिभाषित करने के लिए हैश फ़ंक्शन की आवश्यकता होती है, जहां तुलना किए जाने वाले सभी सेटों के संघ में अलग-अलग तत्वों की कुल संख्या होती है। लेकिन क्योंकि अलग-अलग क्रमपरिवर्तन हैं, इसलिए इसे वास्तव में यादृच्छिक क्रमपरिवर्तन को निर्दिष्ट करने के लिए बिट्स की आवश्यकता होगी, जो के मध्यम मूल्यों के लिए एक अविश्वसनीय रूप से बड़ी संख्या है। इस तथ्य के कारण, सार्वभौमिक हैशिंग के सिद्धांत के अनुरूप, क्रमपरिवर्तन के एक परिवार को खोजने पर महत्वपूर्ण काम किया गया है जो "न्यूनतम-वार स्वतंत्र" है, जिसका अर्थ है कि डोमेन के किसी भी सबसेट के लिए, किसी भी तत्व के न्यूनतम होने की समान संभावना है। यह स्थापित किया गया है कि क्रमपरिवर्तन के एक न्यूनतम-वार स्वतंत्र परिवार में कम से कम अलग-अलग क्रमपरिवर्तन शामिल होने चाहिए, और इसलिए इसे एक एकल क्रमपरिवर्तन को निर्दिष्ट करने के लिए बिट्स की आवश्यकता होती है, जो अभी भी अविश्वसनीय रूप से बड़ा है। व्यावहारिक न्यूनतम-वार स्वतंत्र हैश कार्य उपरोक्त अव्यावहारिकता के कारण, न्यूनतम-वार स्वतंत्रता की दो भिन्न धारणाएँ पेश की गई हैंः सीमित न्यूनतम-वार स्वतंत्र क्रमपरिवर्तन परिवार, और अनुमानित न्यूनतम-वार स्वतंत्र परिवार। सीमित न्यूनतम-वार स्वतंत्रता न्यूनतम-वार स्वतंत्रता संपत्ति है जो अधिक से अधिक कार्डिनलिटी के कुछ सेटों तक सीमित है। अनुमानित न्यूनतम-वार स्वतंत्रता में पूर्ण स्वतंत्रता से भिन्न होने की एक निश्चित संभावना है। 1999 में पियोटर इंडिक ने साबित किया कि हैश कार्यों का कोई भी के-वार स्वतंत्र परिवार भी काफी बड़े के लिए लगभग न्यूनतम-वार स्वतंत्र है। विशेष रूप से, ऐसे स्थिरांक हैं कि यदि, तो सभी सेटों के लिए और। (ध्यान दें, यहाँ इसका मतलब है कि संभावना अधिक से अधिक एक कारक है जो बहुत बड़ा है, और अधिक से अधिक बहुत छोटा है।) यह गारंटी, अन्य बातों के अलावा, मिनहैश एल्गोरिदम द्वारा आवश्यक जैककार्ड बाउंड देने के लिए पर्याप्त है। अर्थात्, यदि और सेट हैं, तो चूंकि के-वार स्वतंत्र हैश कार्यों को केवल बिट्स का उपयोग करके निर्दिष्ट किया जा सकता है, यह दृष्टिकोण पूरी तरह से न्यूनतम-वार स्वतंत्र क्रमपरिवर्तन का उपयोग करने की तुलना में बहुत अधिक व्यावहारिक है। हैश कार्यों का एक अन्य व्यावहारिक परिवार जो अनुमानित न्यूनतम-वार स्वतंत्रता देता है, वह है टैबुलेशन हैशिंग। मिनहैश के लिए मूल अनुप्रयोगों में वेब दस्तावेजों के बीच निकट-प्रतिकृतियों को क्लस्टरिंग और समाप्त करना शामिल था, जिन्हें उन दस्तावेजों में आने वाले शब्दों के सेट के रूप में दर्शाया गया था। इसी तरह की तकनीकों का उपयोग अन्य प्रकार के डेटा के लिए क्लस्टरिंग और लगभग-डुप्लिकेट उन्मूलन के लिए भी किया गया है, जैसे कि छवियाँः छवि डेटा के मामले में, एक छवि को उससे क्रॉप किए गए छोटे उप-छवियों के सेट के रूप में, या अधिक जटिल छवि विशेषता विवरण के सेट के रूप में दर्शाया जा सकता है। डेटा माइनिंग में, एसोसिएशन रूल लर्निंग के लिए एक उपकरण के रूप में मिनहैश का उपयोग करें। एक डेटाबेस को देखते हुए जिसमें प्रत्येक प्रविष्टि में कई विशेषताएँ होती हैं (प्रति डेटाबेस प्रविष्टि में एक पंक्ति और प्रति विशेषता में एक कॉलम के साथ 0-1 मैट्रिक्स के रूप में देखा जाता है) वे जैककार्ड सूचकांक के लिए मिनहैश-आधारित सन्निकटन का उपयोग करते हैं ताकि उन विशेषताओं के उम्मीदवार जोड़े की पहचान की जा सके जो अक्सर सह-घटित होते हैं, और फिर केवल उन जोड़े के लिए सूचकांक के सटीक मूल्य की गणना करें ताकि यह निर्धारित किया जा सके कि जिनकी सह-घटना की आवृत्ति दी गई सख्त सीमा से कम है। मिनहैश एल्गोरिदम को जैव सूचना विज्ञान के लिए अनुकूलित किया गया है, जहां जीनोम अनुक्रमों की तुलना करने की समस्या वेब पर दस्तावेजों की तुलना करने के समान सैद्धांतिक आधार है। मिनहैश-आधारित उपकरण संदर्भ जीनोम के साथ पूरे जीनोम अनुक्रमण डेटा की तेजी से तुलना करने की अनुमति देते हैं (रेफसेक में 90000 संदर्भ जीनोम के साथ एक जीनोम की तुलना करने के लिए लगभग 3 मिनट), और विशिष्टता के लिए उपयुक्त हैं और शायद सूक्ष्मजीव उप-प्रकार की सीमित डिग्री के लिए उपयुक्त हैं। मेटाजेनॉमिक्स और जीनोम संरेखण और जीनोम असेंबली के लिए मिनहैश व्युत्पन्न एल्गोरिदम के उपयोग के लिए भी अनुप्रयोग हैं। सटीक औसत न्यूक्लियोटाइड पहचान (एएनआई) मूल्यों को मिनहैश-आधारित एल्गोरिदम के साथ बहुत कुशलता से उत्पन्न किया जा सकता है। अन्य उपयोग मिनहैश योजना को स्थानीयता-संवेदनशील हैशिंग के एक उदाहरण के रूप में देखा जा सकता है, जो हैश कार्यों का उपयोग करने के लिए तकनीकों का एक संग्रह है जो वस्तुओं के बड़े सेट को छोटे हैश मानों तक इस तरह से मैप करता है कि जब दो वस्तुओं की एक दूसरे से थोड़ी दूरी होती है, तो उनके हैश मान समान होने की संभावना होती है। इस उदाहरण में, एक समूह के हस्ताक्षर को उसके हैश मूल्य के रूप में देखा जा सकता है। सेटों के बीच हैमिंग दूरी और वैक्टरों के बीच कोसाइन दूरी के लिए अन्य स्थानीय संवेदनशील हैशिंग तकनीकें मौजूद हैं; स्थानीय संवेदनशील हैशिंग के निकटतम पड़ोसी खोज एल्गोरिदम में महत्वपूर्ण अनुप्रयोग हैं। बड़ी वितरित प्रणालियों के लिए, और विशेष रूप से मैपरेड्यूस में, बिंदु आयाम पर कोई निर्भरता के बिना समानताओं की गणना करने में मदद करने के लिए मिनहैश के संशोधित संस्करण मौजूद हैं। मिन्हाश और सिमहैश एल्गोरिदम के प्रदर्शन की तुलना करने के लिए 2006 में गूगल द्वारा बड़े पैमाने पर मूल्यांकन किया गया था। 2007 में गूगल ने वेब क्रॉल करने के लिए डुप्लिकेट डिटेक्शन के लिए सिम्हाश का उपयोग करने और गूगल न्यूज वैयक्तिकरण के लिए मिन्हाश और एलएसएच का उपयोग करने की सूचना दी। यह भी देखें संदर्भ हैश कार्य क्लस्टरिंग मानदंड हैशिंग संभावित डेटा संरचनाएँ