मिनहैश: Difference between revisions

Revision as of 10:13, 26 May 2023

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

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

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

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

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

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

अब, आवेदन कर रहा हूँ $h min$ दोनों के लिए $A$ और $B$ , और कोई हैश टकराव नहीं मानते हुए, हम देखते हैं कि मान समान हैं ( $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/ \sqrt k)$ .^[3] इसलिए, किसी भी स्थिरांक के लिए $ε > 0$ एक नियतांक है $k = O(1/ε 2)$ जैसे अनुमान की अपेक्षित त्रुटि अधिक से अधिक हो $ε$ . उदाहरण के लिए, अनुमान लगाने के लिए 400 हैश की आवश्यकता होगी $J (A, B)$ .05 से कम या उसके बराबर अपेक्षित त्रुटि के साथ।

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

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

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

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

समय विश्लेषण

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

वजन शामिल करना

MinHashes की गणना में वज़न पेश करने के लिए कई तरह की तकनीकों का विकास किया गया है। सरलतम इसे पूर्णांक भार तक बढ़ाता है।^[4] हमारे हैश फ़ंक्शन का विस्तार करें $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})}}

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

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

इससे टक्कर की संभावना के रूप में जैककार्ड इंडेक्स#प्रायिकता जैकार्ड समानता और दूरी प्राप्त होती है^[7]

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)$ बिट्स एकल क्रमचय निर्दिष्ट करने के लिए, अभी भी अव्यवहारिक रूप से बड़ा है।^[2]

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

उपरोक्त अव्यावहारिकता के कारण, न्यूनतम-वार स्वतंत्रता के दो भिन्न विचारों को पेश किया गया है: प्रतिबंधित न्यूनतम-वार स्वतंत्र क्रमपरिवर्तन परिवार, और अनुमानित न्यूनतम-वार स्वतंत्र परिवार। प्रतिबंधित न्यूनतम-वार स्वतंत्रता न्यूनतम-वार स्वतंत्रता संपत्ति है जो कार्डिनैलिटी के कुछ सेटों तक सीमित है $k$ .^[8] अनुमानित न्यूनतम-वार स्वतंत्रता की अधिक से अधिक एक निश्चित संभावना होती है $ε$ पूर्ण स्वतंत्रता से भिन्न।^[9] 1999 में पीटर इंडिक साबित हुए^[10] कि कोई भी के-इंडिपेंडेंट_हैशिंग|के-वार हैश फ़ंक्शंस का स्वतंत्र परिवार भी लगभग न्यूनतम-वार स्वतंत्र है $k$ बहुत पर्याप्त। विशेष रूप से, स्थिरांक होते हैं $c,c'>0$ ऐसा कि अगर $k \geq c \log$

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Anonymous

Search