मिनहैश: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Data mining technique}} | {{Short description|Data mining technique}} | ||
[[कंप्यूटर विज्ञान]] और [[डेटा खनन|डेटा माइनिंग]] में, मिनहैश (या कम से कम स्वतंत्र क्रमपरिवर्तन [[स्थानीयता संवेदनशील हैशिंग]] स्कीम) दो समुच्चयो की समानता को मापने की विधि का शीघ्रता से अनुमान लगाने की | [[कंप्यूटर विज्ञान]] और [[डेटा खनन|डेटा माइनिंग]] में, मिनहैश (या कम से कम स्वतंत्र क्रमपरिवर्तन [[स्थानीयता संवेदनशील हैशिंग]] स्कीम) दो समुच्चयो की समानता को मापने की विधि का शीघ्रता से अनुमान लगाने की विधि है। पद्धति का आविष्कार {{harvs|first=एंड्री|last=ब्रॉडर|authorlink=एंड्री ब्रॉडर|year=1997|txt}} द्वारा किया गया था ,<ref name="b97">{{citation | ||
| last = Broder | | last = Broder | ||
| first = Andrei Z. | | first = Andrei Z. | ||
| Line 34: | Line 34: | ||
== जैककार्ड समानता और न्यूनतम हैश मान == | == जैककार्ड समानता और न्यूनतम हैश मान == | ||
[[जैकार्ड इंडेक्स|जैकार्ड सूची]] दो समुच्चयो के बीच समानता का सामान्यतः उपयोग किया जाने वाला संकेतक है। माना {{math|''U''}} | [[जैकार्ड इंडेक्स|जैकार्ड सूची]] दो समुच्चयो के बीच समानता का सामान्यतः उपयोग किया जाने वाला संकेतक है। माना {{math|''U''}} समुच्चय हो और {{math|''A''}} और {{math|''B''}} के उपसमुच्चय {{math|''U''}} हों , तो जैकार्ड सूची को उनके प्रतिच्छेदन (समुच्चय सिद्धांत) के तत्वों की संख्या और उनके [[संघ (सेट सिद्धांत)|संघ (समुच्चय सिद्धांत)]] के तत्वों की संख्या के अनुपात के रूप में परिभाषित किया गया है । | ||
:<math> J(A,B) = {{|A \cap B|}\over{|A \cup B|}}.</math> | :<math> J(A,B) = {{|A \cap B|}\over{|A \cup B|}}.</math> | ||
यह मान 0 है जब दो समुच्चय अलग समुच्चय होते हैं । जब वे समान होते हैं, और सख्ती से 0 और 1 के बीच अन्यथा दो समुच्चय अधिक समान होते हैं (अर्थात अपेक्षाकृत अधिक सदस्य होते हैं) जब उनका जैकार्ड सूची 1 के निकट होता है। मिनहैश {{math|''J''(''A'',''B'')}} का लक्ष्य अनुमान लगाना है। शीघ्रता से, प्रतिच्छेदन और संघ की स्पष्ट रूप से गणना किए बिना किया जाता है। | यह मान 0 है जब दो समुच्चय अलग समुच्चय होते हैं । जब वे समान होते हैं, और सख्ती से 0 और 1 के बीच अन्यथा दो समुच्चय अधिक समान होते हैं (अर्थात अपेक्षाकृत अधिक सदस्य होते हैं) जब उनका जैकार्ड सूची 1 के निकट होता है। मिनहैश {{math|''J''(''A'',''B'')}} का लक्ष्य अनुमान लगाना है। शीघ्रता से, प्रतिच्छेदन और संघ की स्पष्ट रूप से गणना किए बिना किया जाता है। | ||
माना {{math|''h''}} | माना {{math|''h''}} [[हैश फंकशन|हैश फलन]] हो जो सदस्यों {{math|''U''}} को मैप करता हो भिन्न पूर्णांकों के लिए मैप करता है । मान लीजिए {{math|''पर्म''}} समुच्चय के तत्वों का यादृच्छिक क्रम[[परिवर्तन]] {{math|''U''}} हो , और किसी भी सबसेट के लिए {{math|''S''}} का {{math|''U''}} परिभाषित करता है । {{math|''h''<sub>min</sub>(''S'')}} का न्यूनतम सदस्य होना {{math|''S''}} इसके संबंध में {{math|''h'' ∘ ''perm''}}—अर्थात् के न्यूनतम मूल्य के साथ {{math|''S''}} का सदस्य {{math|''x''}} है । {{math|''h''(''perm''(''x''))}}. (ऐसे स्थितियों में जहां उपयोग किए गए हैश फलन को छद्म-यादृच्छिक गुण माना जाता है, यादृच्छिक क्रमचय का उपयोग नहीं किया जाएगा।)। | ||
अब, {{math|''A''}} और {{math|''B''}} दोनों के लिए {{math|''h''<sub>min</sub>}} प्रयुक्त करना, और कोई हैश टकराव नहीं मानते हुए, हम देखते हैं कि मान समान हैं। ({{math|1=''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'')}}) यदि और केवल यदि <math>A\cup B</math> के सभी तत्वों के साथ तत्व न्यूनतम हैश मान प्रतिच्छेदन <math>A\cap B</math> में निहित है। इसके सही होने की संभावना वास्तव में जैकार्ड सूची है। इसलिए: | अब, {{math|''A''}} और {{math|''B''}} दोनों के लिए {{math|''h''<sub>min</sub>}} प्रयुक्त करना, और कोई हैश टकराव नहीं मानते हुए, हम देखते हैं कि मान समान हैं। ({{math|1=''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'')}}) यदि और केवल यदि <math>A\cup B</math> के सभी तत्वों के साथ तत्व न्यूनतम हैश मान प्रतिच्छेदन <math>A\cap B</math> में निहित है। इसके सही होने की संभावना वास्तव में जैकार्ड सूची है। इसलिए: | ||
:{{math|1=Pr[ ''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'') ] = ''J''(''A'',''B''),}} | :{{math|1=Pr[ ''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'') ] = ''J''(''A'',''B''),}} | ||
अर्थात्, [[संभावना]] है कि {{math|1=''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'')}} सत्य है। समानता {{math|''J''(''A'',''B'')}} के समान है जो एक समान वितरण से ड्राइंग {{math|''perm''}} को मानता है। दूसरे शब्दों में, यदि {{math|''r''}} यादृच्छिक चर है। जो एक है जब {{math|1=''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'')}} और अन्यथा शून्य है, तो {{math|''r''}} {{math|''J''(''A'',''B'')}} का | अर्थात्, [[संभावना]] है कि {{math|1=''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'')}} सत्य है। समानता {{math|''J''(''A'',''B'')}} के समान है जो एक समान वितरण से ड्राइंग {{math|''perm''}} को मानता है। दूसरे शब्दों में, यदि {{math|''r''}} यादृच्छिक चर है। जो एक है जब {{math|1=''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'')}} और अन्यथा शून्य है, तो {{math|''r''}} {{math|''J''(''A'',''B'')}} का निष्पक्ष अनुमानक है। {{math|''r''}} का प्रसरण इतना अधिक है कि स्वयं जैककार्ड समानता के लिए उपयोगी अनुमानक नहीं बन सकता क्योंकि r सदैव शून्य या एक होता है। मिनहाश योजना का विचार एक ही तरह से निर्मित कई चरों को एक साथ जोड़कर इस भिन्नता को कम करना है। | ||
== एल्गोरिथम == | == एल्गोरिथम == | ||
=== कई हैश फलन के साथ संस्करण === | === कई हैश फलन के साथ संस्करण === | ||
मिनहाश पद्धति {{math|''k''}} का सबसे सरल संस्करण उपयोग करता है। विभिन्न हैश फलन, जहाँ {{math|''k''}} | मिनहाश पद्धति {{math|''k''}} का सबसे सरल संस्करण उपयोग करता है। विभिन्न हैश फलन, जहाँ {{math|''k''}} निश्चित पूर्णांक मापदंड है, और प्रत्येक समुच्चय का प्रतिनिधित्व करता है। {{math|''S''}} से {{math|''k''}} का मान {{math|''h''<sub>min</sub>(''S'')}} इन के लिए {{math|''k''}} फलन करता है। | ||
अनुमान लगाने के लिए {{math|''J''(''A'',''B'')}} पद्धति के इस संस्करण का उपयोग करते हुए, आइए {{math|''y''}} हैश फलन की संख्या हो जिसके लिए {{math|1=''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'')}}, और उपयोग करें {{math|''y''/''k''}} अनुमान के रूप में यह अनुमान का औसत है । {{math|''k''}} विभिन्न 0-1 यादृच्छिक चर, जिनमें {{math|1=''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'')}} से प्रत्येक एक जब है और शून्य अन्यथा, और जिनमें से प्रत्येक का {{math|''J''(''A'',''B'')}} | अनुमान लगाने के लिए {{math|''J''(''A'',''B'')}} पद्धति के इस संस्करण का उपयोग करते हुए, आइए {{math|''y''}} हैश फलन की संख्या हो जिसके लिए {{math|1=''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'')}}, और उपयोग करें {{math|''y''/''k''}} अनुमान के रूप में यह अनुमान का औसत है । {{math|''k''}} विभिन्न 0-1 यादृच्छिक चर, जिनमें {{math|1=''h''<sub>min</sub>(''A'') = ''h''<sub>min</sub>(''B'')}} से प्रत्येक एक जब है और शून्य अन्यथा, और जिनमें से प्रत्येक का {{math|''J''(''A'',''B'')}} निष्पक्ष अनुमानक है। इसलिए, उनका औसत भी निष्पक्ष अनुमानक है, और 0-1 यादृच्छिक चर के योग के लिए मानक विचलन द्वारा, इसकी अपेक्षित {{math|O(1/{{sqrt|''k''}})}} त्रुटि है।<ref>{{citation|first=Sergey|last=Vassilvitskii|year=2011|title=COMS 6998-12: Dealing with Massive Data (lecture notes, Columbia university)|url=https://www.cs.columbia.edu/~coms699812/lecture1.pdf|archive-url=https://web.archive.org/web/20181024161246/https://www.cs.columbia.edu/~coms699812/lecture1.pdf|url-status=dead|archive-date=2018-10-24}}.</ref> | ||
इसलिए, किसी भी स्थिरांक {{math|1=''k'' = O(1/ε<sup>2</sup>)}} के लिए {{math|ε > 0}} | इसलिए, किसी भी स्थिरांक {{math|1=''k'' = O(1/ε<sup>2</sup>)}} के लिए {{math|ε > 0}} नियतांक है। जैसे अनुमान की अपेक्षित त्रुटि अधिक से अधिक {{math|ε}} होती है। उदाहरण के लिए,.05 से कम या उसके समान अपेक्षित त्रुटि के साथ {{math|''J''(''A'',''B'')}} अनुमान लगाने के लिए 400 हैश की आवश्यकता होती है। | ||
=== एकल हैश फलन के साथ संस्करण === | === एकल हैश फलन के साथ संस्करण === | ||
यह कई हैश फलन की गणना करने के लिए कम्प्यूटेशनल रूप से महंगा हो सकता है। किन्तु मिनहाश पद्धति का | यह कई हैश फलन की गणना करने के लिए कम्प्यूटेशनल रूप से महंगा हो सकता है। किन्तु मिनहाश पद्धति का संबंधित संस्करण केवल एक हैश फलन का उपयोग करके इस दंड से बचा जाता है और इसका उपयोग प्रत्येक हैश फलन के लिए केवल न्यूनतम मान का चयन करने के अतिरिक्त प्रत्येक समुच्चय से कई मानों का चयन करने के लिए करता है। माना {{math|''h''}} हैश फलन है और निश्चित पूर्णांक है। यदि {{math|''S''}} {{math|''k''}} का कोई समुच्चय है या अधिक मान के डोमेन में {{math|''h''}}, परिभाषित करना {{math|''h''<sub>(''k'')</sub>(''S'')}} का सबसेट होना {{math|''k''}} के सदस्यों {{math|''S''}} जिसके सबसे छोटे मान {{math|''h''}} हैं। यह उपसमुच्चय {{math|''h''<sub>(''k'')</sub>(''S'')}} समुच्चय {{math|''S''}} के लिए हस्ताक्षर के रूप में प्रयोग किया जाता है और किन्हीं दो समुच्चयो की समानता का अनुमान उनके हस्ताक्षरों की तुलना करके लगाया जाता है। | ||
विशेष रूप से, A और B को कोई भी दो समुच्चय होने दें। तब {{math|1=''X'' = ''h''<sub>(''k'')</sub>(''h''<sub>(''k'')</sub>(''A'') ∪ ''h''<sub>(''k'')</sub>(''B'')) = ''h''<sub>(''k'')</sub>(''A'' ∪ ''B'')}} k तत्वों का | विशेष रूप से, A और B को कोई भी दो समुच्चय होने दें। तब {{math|1=''X'' = ''h''<sub>(''k'')</sub>(''h''<sub>(''k'')</sub>(''A'') ∪ ''h''<sub>(''k'')</sub>(''B'')) = ''h''<sub>(''k'')</sub>(''A'' ∪ ''B'')}} k तत्वों का समुच्चय {{math|''A'' ∪ ''B''}} है , और यदि h यादृच्छिक फलन है तो k तत्वों के किसी उपसमुच्चय के चुने जाने की समान संभावना है। जो कि {{math|''X''}} {{math|''A'' ∪ ''B''}} का साधारण यादृच्छिक प्रतिरूप है। उपसमुच्चय {{math|1=''Y'' = ''X'' ∩ ''h''<sub>(''k'')</sub>(''A'') ∩ ''h''<sub>(''k'')</sub>(''B'')}} के सदस्यों का समुच्चय है जो प्रतिच्छेदन {{math|''X''}} के हैं जो {{math|''A'' ∩ ''B''}} से संबंधित हैं। इसलिए, |{{math|''Y''}}|/{{math|''k''}} {{math|''J''(''A'',''B'')}} का निष्पक्ष अनुमानक है। इस अनुमानक और एकाधिक हैश फलन द्वारा उत्पादित अनुमानक के बीच का अंतर यह है कि {{math|''X''}} सदैव {{math|''k''}} सदस्य स्पष्ट होता है, जबकि कई हैश फलन से प्रतिरूप तत्वों की छोटी संख्या हो सकती है। इस संभावना के कारण कि दो अलग-अलग हैश फलन में एक ही मिनिमा हो सकती है। चूँकि, जब {{math|''k''}} समुच्चय के आकार के सापेक्ष छोटा है, यह अंतर नगण्य है। | ||
प्रतिस्थापन के बिना प्रतिरूप के लिए मानक चेरनॉफ़ सीमा से, इस अनुमानक ने त्रुटि की अनुमान {{math|O(1/{{sqrt|''k''}})}} की है। बहु-हैश-फलन पद्धति के प्रदर्शन का मिलान होता है। | प्रतिस्थापन के बिना प्रतिरूप के लिए मानक चेरनॉफ़ सीमा से, इस अनुमानक ने त्रुटि की अनुमान {{math|O(1/{{sqrt|''k''}})}} की है। बहु-हैश-फलन पद्धति के प्रदर्शन का मिलान होता है। | ||
| Line 75: | Line 75: | ||
| year = 2008}}</ref> | | year = 2008}}</ref> | ||
हमारे हैश फलन का विस्तार करें । {{mvar|h}} | हमारे हैश फलन का विस्तार करें । {{mvar|h}} समुच्चय सदस्य और पूर्णांक दोनों को स्वीकार करने के लिए, फिर प्रत्येक आइटम के लिए उसके वजन के अनुसार कई हैश उत्पन्न करें। यदि आइटम {{mvar|i}} घटित होना {{mvar|n}} बार, हैश <math>h(i,1), h(i,2), \ldots, h(i,n)</math> उत्पन्न करता है। हैश के इस विस्तारित समुच्चय पर मूल एल्गोरिथम चलाएं ऐसा करने से टक्कर की संभावना के रूप में जैकार्ड सूची जैककार्ड समानता और दूरी प्राप्त होती है। | ||
: <math>J_\mathcal{W}(x,y) = \frac{\sum_i \min(x_i,y_i)}{\sum_i \max(x_i,y_i)}</math> | : <math>J_\mathcal{W}(x,y) = \frac{\sum_i \min(x_i,y_i)}{\sum_i \max(x_i,y_i)}</math> | ||
उत्तम रनटाइम के साथ वास्तविक भार पर इस टकराव की संभावना को प्राप्त करने वाले और विस्तार विकसित किए गए हैं। | उत्तम रनटाइम के साथ वास्तविक भार पर इस टकराव की संभावना को प्राप्त करने वाले और विस्तार विकसित किए गए हैं। सघन डेटा के लिए,<ref>{{cite arXiv | ||
| title=Exact weighted minwise hashing in constant time | | title=Exact weighted minwise hashing in constant time | ||
| eprint = 1602.08393 | | eprint = 1602.08393 | ||
| Line 92: | Line 92: | ||
| year = 2010| doi = 10.1109/ICDM.2010.80 | citeseerx = 10.1.1.227.9749 | isbn = 978-1-4244-9131-5 | s2cid = 9970906 }}</ref> | | year = 2010| doi = 10.1109/ICDM.2010.80 | citeseerx = 10.1.1.227.9749 | isbn = 978-1-4244-9131-5 | s2cid = 9970906 }}</ref> | ||
एक्सटेंशन का | एक्सटेंशन का और समूह तेजी से वितरित हैश का उपयोग करता है। 0 और 1 के बीच समान रूप से यादृच्छिक हैश को व्युत्क्रम परिवर्तन प्रतिरूप द्वारा घातीय वितरण का पालन करने के लिए परिवर्तित किया जा सकता है। यह विधि एक्सपोनेंशियल डिस्ट्रीब्यूशन के कई खूबसूरत गुणों का फायदा उठाती है। न्यूनतम एक्सपोनेंशियल रैंडम वेरिएबल्स का वितरण होता है। | ||
: <math>H(x) = \underset{i}{\operatorname{arg\,min}} \frac{-\log(h(i))}{x_i}</math> | : <math>H(x) = \underset{i}{\operatorname{arg\,min}} \frac{-\log(h(i))}{x_i}</math> | ||
| Line 100: | Line 100: | ||
== न्यूनतम स्वतंत्र क्रमपरिवर्तन == | == न्यूनतम स्वतंत्र क्रमपरिवर्तन == | ||
जैसा कि ऊपर बताया गया है, मिनहैश पद्धति को प्रयुक्त करने के लिए हैश फलन {{math|''h''}} की आवश्यकता होती है। | जैसा कि ऊपर बताया गया है, मिनहैश पद्धति को प्रयुक्त करने के लिए हैश फलन {{math|''h''}} की आवश्यकता होती है। यादृच्छिक क्रमचय को परिभाषित करने के लिए {{math|''n''}} तत्व, जहां {{math|''n''}} तुलना किए जाने वाले सभी समुच्चयो के संघ में अलग-अलग तत्वों की कुल संख्या है। किन्तु क्योंकि हैं {{math|''n''!}} विभिन्न क्रमपरिवर्तन, इसकी आवश्यकता होगी {{math|Ω(''n'' log ''n'')}} बिट्स वास्तव में यादृच्छिक क्रमचय निर्दिष्ट करने के लिए, यहां तक कि मध्यम मूल्यों के लिए अविश्वसनीय रूप से बड़ी संख्या {{math|''n''}}. इस तथ्य के कारण, सार्वभौमिक हैशिंग के सिद्धांत के अनुरूप, क्रमचय के समूह को खोजने पर महत्वपूर्ण काम किया गया है। जो कि न्यूनतम स्वतंत्र है, जिसका अर्थ है कि डोमेन के किसी भी उपसमुच्चय के लिए, कोई भी तत्व समान रूप से न्यूनतम होने की संभावना है। यह स्थापित किया गया है कि क्रमपरिवर्तन के न्यूनतम स्वतंत्र समूह में कम से कम सम्मिलित होना चाहिए। | ||
:<math>\operatorname{lcm}(1, 2, \cdots, n) \ge e^{n-o(n)}</math> | :<math>\operatorname{lcm}(1, 2, \cdots, n) \ge e^{n-o(n)}</math> | ||
विभिन्न क्रमपरिवर्तन, और इसलिए इसकी {{math|Ω(''n'')}} आवश्यकता है। बिट्स एकल क्रमचय निर्दिष्ट करने के लिए, अभी भी अव्यवहारिक रूप से बड़ा है।<ref name="bcfm"/> | विभिन्न क्रमपरिवर्तन, और इसलिए इसकी {{math|Ω(''n'')}} आवश्यकता है। बिट्स एकल क्रमचय निर्दिष्ट करने के लिए, अभी भी अव्यवहारिक रूप से बड़ा है।<ref name="bcfm"/> | ||
| Line 119: | Line 119: | ||
| year = 2003| citeseerx = 10.1.1.400.6757 | s2cid = 1483449 }}.</ref> | | year = 2003| citeseerx = 10.1.1.400.6757 | s2cid = 1483449 }}.</ref> | ||
अनुमानित न्यूनतम स्वतंत्रता की अधिक से अधिक | अनुमानित न्यूनतम स्वतंत्रता की अधिक से अधिक निश्चित {{math|ε}} पूर्ण स्वतंत्रता से भिन्न संभावना होती है।<ref>{{citation | ||
| last1 = Saks | first1 = M. | author1-link = Michael Saks (mathematician) | | last1 = Saks | first1 = M. | author1-link = Michael Saks (mathematician) | ||
| last2 = Srinivasan | first2 = A. | | last2 = Srinivasan | first2 = A. | ||
| Line 134: | Line 134: | ||
1999 में [[पीटर इंडिक]] सिद्ध हुए।<ref>Indyk, Piotr. "A small approximately min-wise independent family of hash functions." Journal of Algorithms 38.1 (2001): 84-90.</ref> कि कोई भी के-इंडिपेंडेंट_हैशिंग|के हैश फलन का स्वतंत्र समूह भी लगभग न्यूनतम <math>k</math> स्वतंत्र है। बहुत पर्याप्त विशेष रूप से,<math>c,c'>0</math> स्थिरांक होते हैं। ऐसा कि यदि <math>k\ge c \log\tfrac{1}{\epsilon}</math>, तब | 1999 में [[पीटर इंडिक]] सिद्ध हुए।<ref>Indyk, Piotr. "A small approximately min-wise independent family of hash functions." Journal of Algorithms 38.1 (2001): 84-90.</ref> कि कोई भी के-इंडिपेंडेंट_हैशिंग|के हैश फलन का स्वतंत्र समूह भी लगभग न्यूनतम <math>k</math> स्वतंत्र है। बहुत पर्याप्त विशेष रूप से,<math>c,c'>0</math> स्थिरांक होते हैं। ऐसा कि यदि <math>k\ge c \log\tfrac{1}{\epsilon}</math>, तब | ||
:<math>\Pr_{h\in \mathcal H}[h(x)<\min h(X)]=\frac{1}{|X|+1}(1\pm\epsilon),</math> | :<math>\Pr_{h\in \mathcal H}[h(x)<\min h(X)]=\frac{1}{|X|+1}(1\pm\epsilon),</math> | ||
सभी समुच्चयो के लिए <math>|X|\le \epsilon n c'</math> और <math>x\in X</math>. (ध्यान दें, यहाँ <math>(1\pm\epsilon)</math> इसका कारण है कि संभावना अधिक से अधिक | सभी समुच्चयो के लिए <math>|X|\le \epsilon n c'</math> और <math>x\in X</math>. (ध्यान दें, यहाँ <math>(1\pm\epsilon)</math> इसका कारण है कि संभावना अधिक से अधिक कारक है। <math>1+\epsilon</math> बहुत बड़ा, और अधिक से अधिक <math>1-\epsilon</math> बहुत छोटा।) | ||
यह गारंटी, अन्य बातों के अतिरिक्त, मिनहैश एल्गोरिथम द्वारा आवश्यक जैककार्ड बाउंड देने के लिए पर्याप्त है। अर्थात यदि <math>A</math> और <math>B</math> समुच्चय हैं। फिर | यह गारंटी, अन्य बातों के अतिरिक्त, मिनहैश एल्गोरिथम द्वारा आवश्यक जैककार्ड बाउंड देने के लिए पर्याप्त है। अर्थात यदि <math>A</math> और <math>B</math> समुच्चय हैं। फिर | ||
| Line 140: | Line 140: | ||
चूंकि के-इंडिपेंडेंट हाशिंग के स्वतंत्र हैश फलन <math>k\log n</math> बिट्स को बस का उपयोग करके निर्दिष्ट किया जा सकता है। यह दृष्टिकोण पूरी तरह न्यूनतम स्वतंत्र क्रमपरिवर्तन का उपयोग करने से कहीं अधिक व्यावहारिक है। | चूंकि के-इंडिपेंडेंट हाशिंग के स्वतंत्र हैश फलन <math>k\log n</math> बिट्स को बस का उपयोग करके निर्दिष्ट किया जा सकता है। यह दृष्टिकोण पूरी तरह न्यूनतम स्वतंत्र क्रमपरिवर्तन का उपयोग करने से कहीं अधिक व्यावहारिक है। | ||
हैश फलन का | हैश फलन का अन्य व्यावहारिक समूह जो लगभग न्यूनतम स्वतंत्रता देता है। सारणीयन हैशिंग है। | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
मिनहाश के लिए मूल अनुप्रयोगों में वेब दस्तावेज़ों के बीच क्लस्टरिंग और निकट-प्रतिरूप को समाप्त करना सम्मिलित था। जो उन दस्तावेज़ों में आने वाले शब्दों के समुच्चय के रूप में दर्शाए गए थे।<ref name="b97"/><ref name="bcfm"/><ref>{{cite book|last1=Manasse|first1=Mark|title=On the Efficient Determination of Most Near Neighbors: Horseshoes, Hand Grenades, Web Search, and Other Situations when Close is Close Enough|date=2012|publisher=Morgan & Claypool|isbn=9781608450886|pages=72}}</ref> अन्य प्रकार के डेटा के लिए क्लस्टरिंग और निकट-प्रतिरूप उन्मूलन के लिए भी इसी तरह की विधियों का उपयोग किया गया है। जैसे कि छवियां छवि डेटा के स्थिति में, | मिनहाश के लिए मूल अनुप्रयोगों में वेब दस्तावेज़ों के बीच क्लस्टरिंग और निकट-प्रतिरूप को समाप्त करना सम्मिलित था। जो उन दस्तावेज़ों में आने वाले शब्दों के समुच्चय के रूप में दर्शाए गए थे।<ref name="b97"/><ref name="bcfm"/><ref>{{cite book|last1=Manasse|first1=Mark|title=On the Efficient Determination of Most Near Neighbors: Horseshoes, Hand Grenades, Web Search, and Other Situations when Close is Close Enough|date=2012|publisher=Morgan & Claypool|isbn=9781608450886|pages=72}}</ref> अन्य प्रकार के डेटा के लिए क्लस्टरिंग और निकट-प्रतिरूप उन्मूलन के लिए भी इसी तरह की विधियों का उपयोग किया गया है। जैसे कि छवियां छवि डेटा के स्थिति में, छवि को छोटे सबइमेज के समुच्चय के रूप में या उससे अधिक के समुच्चय के रूप में दर्शाया जा सकता है। जटिल छवि सुविधा विवरण <ref>{{citation | ||
| last1 = Chum | first1 = Ondřej | | last1 = Chum | first1 = Ondřej | ||
| last2 = Philbin | first2 = James | | last2 = Philbin | first2 = James | ||
| Line 163: | Line 163: | ||
| url = http://www.bmva.org/bmvc/2008/papers/119.pdf | | url = http://www.bmva.org/bmvc/2008/papers/119.pdf | ||
| volume = 3 | | volume = 3 | ||
| year = 2008}}.</ref> डाटा माइनिंग में, {{harvtxt|कोहेन|दातर|फुजिवारा|जिओनीस|2001}} [[एसोसिएशन नियम सीखना]] के लिए | | year = 2008}}.</ref> डाटा माइनिंग में, {{harvtxt|कोहेन|दातर|फुजिवारा|जिओनीस|2001}} [[एसोसिएशन नियम सीखना]] के लिए टूल के रूप में मिनहैश का उपयोग करें। डेटाबेस को देखते हुए जिसमें प्रत्येक प्रविष्टि में कई विशेषताएँ होती हैं ( तार्किक आव्यूह के रूप में देखा जाता है। 0-1 आव्यूह पंक्ति प्रति डेटाबेस प्रविष्टि और स्तंभ प्रति विशेषता के साथ) वे उम्मीदवारों के जोड़े की पहचान करने के लिए जैकार्ड सूची के लिए मिनहैश-आधारित सन्निकटन का उपयोग करते हैं। अधिकांशतः सह-होता है, और उसके बाद केवल उन जोड़े के लिए सूचकांक के स्पष्ट मूल्य की गणना करें जिनकी सह-घटना की आवृत्ति निश्चित सीमा से नीचे है।<ref>{{citation | ||
| last1 = Cohen | first1 = E. | author1-link = Edith Cohen | | last1 = Cohen | first1 = E. | author1-link = Edith Cohen | ||
| last2 = Datar | first2 = M. | | last2 = Datar | first2 = M. | ||
| Line 180: | Line 180: | ||
| year = 2001| citeseerx = 10.1.1.192.7385 }}.</ref> | | year = 2001| citeseerx = 10.1.1.192.7385 }}.</ref> | ||
मिनहैश एल्गोरिदम को जैव सूचना विज्ञान के लिए अनुकूलित किया गया है। जहां जीनोम अनुक्रमों की तुलना करने की समस्या वेब पर दस्तावेजों की तुलना करने के समान सैद्धांतिक आधार है। मिनहैश-आधारित उपकरण <ref name=":0">{{Cite journal|last1=Ondov|first1=Brian D.|last2=Treangen|first2=Todd J.|last3=Melsted|first3=Páll|last4=Mallonee|first4=Adam B.|last5=Bergman|first5=Nicholas H.|last6=Koren|first6=Sergey|last7=Phillippy|first7=Adam M.|date=2016-06-20|title=Mash: fast genome and metagenome distance estimation using MinHash|journal=Genome Biology|volume=17|issue=1|pages=132|doi=10.1186/s13059-016-0997-x|issn=1474-760X|pmc=4915045|pmid=27323842}}</ref><ref>{{Cite web|url=https://sourmash.readthedocs.io/en/latest/|title=Welcome to sourmash! — sourmash 1.0 documentation|website=sourmash.readthedocs.io|language=en|access-date=2017-11-13}}</ref> [[संदर्भ]] जीनोम के साथ पूरे जीनोम अनुक्रमण डेटा की तेजी से तुलना की अनुमति दें (संदर्भ में 90000 जीनोम के साथ | मिनहैश एल्गोरिदम को जैव सूचना विज्ञान के लिए अनुकूलित किया गया है। जहां जीनोम अनुक्रमों की तुलना करने की समस्या वेब पर दस्तावेजों की तुलना करने के समान सैद्धांतिक आधार है। मिनहैश-आधारित उपकरण <ref name=":0">{{Cite journal|last1=Ondov|first1=Brian D.|last2=Treangen|first2=Todd J.|last3=Melsted|first3=Páll|last4=Mallonee|first4=Adam B.|last5=Bergman|first5=Nicholas H.|last6=Koren|first6=Sergey|last7=Phillippy|first7=Adam M.|date=2016-06-20|title=Mash: fast genome and metagenome distance estimation using MinHash|journal=Genome Biology|volume=17|issue=1|pages=132|doi=10.1186/s13059-016-0997-x|issn=1474-760X|pmc=4915045|pmid=27323842}}</ref><ref>{{Cite web|url=https://sourmash.readthedocs.io/en/latest/|title=Welcome to sourmash! — sourmash 1.0 documentation|website=sourmash.readthedocs.io|language=en|access-date=2017-11-13}}</ref> [[संदर्भ]] जीनोम के साथ पूरे जीनोम अनुक्रमण डेटा की तेजी से तुलना की अनुमति दें (संदर्भ में 90000 जीनोम के साथ जीनोम की तुलना करने के लिए लगभग 3 मिनट), और अटकलों के लिए उपयुक्त हैं और संभवतः माइक्रोबियल उप-टाइपिंग की सीमित डिग्री मेटाजेनोमिक्स के लिए भी आवेदन हैं <ref name=":0" />और जीनोम संरेखण और जीनोम असेंबली के लिए मिनहैश व्युत्पन्न एल्गोरिदम का उपयोग करते है।<ref>{{Cite journal|last1=Berlin|first1=Konstantin|last2=Koren|first2=Sergey|last3=Chin|first3=Chen-Shan|last4=Drake|first4=James P|last5=Landolin|first5=Jane M|last6=Phillippy|first6=Adam M|date=2015-05-25|title=एकल-अणु अनुक्रमण और स्थानीयता-संवेदनशील हैशिंग के साथ बड़े जीनोम को जोड़ना|journal=Nature Biotechnology|language=en|volume=33|issue=6|pages=623–630|doi=10.1038/nbt.3238|pmid=26006009|s2cid=17246729|issn=1546-1696}}</ref> स्पष्ट औसत न्यूक्लियोटाइड पहचान (एएनआई) मूल्यों को मिनहाश-आधारित एल्गोरिदम के साथ बहुत कुशलतापूर्वक उत्पन्न किया जा सकता है।<ref>{{cite journal |last1=Jain |first1=Chirag |last2=Rodriguez-R |first2=Luis M. |last3=Phillippy |first3=Adam M. |last4=Konstantinidis |first4=Konstantinos T. |last5=Aluru |first5=Srinivas |title=High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundaries |journal=Nature Communications |date=December 2018 |volume=9 |issue=1 |pages=5114 |doi=10.1038/s41467-018-07641-9 |pmid=30504855 |pmc=6269478 |doi-access=free}}</ref> | ||
== अन्य उपयोग == | == अन्य उपयोग == | ||
मिनहैश पद्धति को [[स्थानीयता-संवेदनशील हैशिंग]] के | मिनहैश पद्धति को [[स्थानीयता-संवेदनशील हैशिंग]] के उदाहरण के रूप में देखा जा सकता है। हैश फलन का उपयोग करने के लिए विधियों का संग्रह वस्तुओं के बड़े समुच्चय को छोटे हैश मानों में मैप करने के लिए इस तरह से है कि, जब दो वस्तुओं की एक दूसरे से थोड़ी दूरी हो , उनके हैश मान समान होने की संभावना है। इस उदाहरण में, समुच्चय के हस्ताक्षर को उसके हैश मान के रूप में देखा जा सकता है। [[यूक्लिडियन वेक्टर|यूक्लिडियन सदिश]] के बीच समुच्चय और [[कोसाइन दूरी]] के बीच [[हैमिंग दूरी]] के लिए अन्य इलाके संवेदनशील हैशिंग विधिय उपस्थित हैं। लोकैलिटी सेंसिटिव हैशिंग के पास [[निकटतम पड़ोसी खोज|निकटतम खोज]] एल्गोरिदम में महत्वपूर्ण अनुप्रयोग हैं।<ref>{{citation | ||
| last1 = Andoni | first1 = Alexandr | | last1 = Andoni | first1 = Alexandr | ||
| last2 = Indyk | first2 = Piotr | author2-link = Piotr Indyk | | last2 = Indyk | first2 = Piotr | author2-link = Piotr Indyk | ||
Revision as of 11:58, 27 May 2023
कंप्यूटर विज्ञान और डेटा माइनिंग में, मिनहैश (या कम से कम स्वतंत्र क्रमपरिवर्तन स्थानीयता संवेदनशील हैशिंग स्कीम) दो समुच्चयो की समानता को मापने की विधि का शीघ्रता से अनुमान लगाने की विधि है। पद्धति का आविष्कार एंड्री ब्रॉडर (1997) द्वारा किया गया था ,[1] और प्रारंभ में प्रतिरूप वेब पेजों का पता लगाने और उन्हें खोज परिणामों से हटाने के लिए अल्टाविस्टा सर्च इंजन में उपयोग किया गया था।[2] यह बड़े मापदंड पर क्लस्टर विश्लेषण समस्याओं में भी प्रयुक्त किया गया है । जैसे उनके शब्दों के समुच्चय की समानता से दस्तावेज़ क्लस्टरिंग से होता है।[1]
जैककार्ड समानता और न्यूनतम हैश मान
जैकार्ड सूची दो समुच्चयो के बीच समानता का सामान्यतः उपयोग किया जाने वाला संकेतक है। माना U समुच्चय हो और A और B के उपसमुच्चय U हों , तो जैकार्ड सूची को उनके प्रतिच्छेदन (समुच्चय सिद्धांत) के तत्वों की संख्या और उनके संघ (समुच्चय सिद्धांत) के तत्वों की संख्या के अनुपात के रूप में परिभाषित किया गया है ।