मिनहैश

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

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

जैकार्ड सूची दो समुच्चयो के बीच समानता का सामान्यतः उपयोग किया जाने वाला संकेतक है। माना $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 \circ 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/ \sqrt k)$ त्रुटि है।^[3]

इसलिए, किसी भी स्थिरांक $k = O(1/ε 2)$ के लिए $ε > 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) \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)$ समय लेता है। सिंगल हैश वैरिएंट आम तौर पर तेज़ होता है, जिसमें $n >> k$ मानने वाले न्यूनतम हैश मानों की कतार बनाए रखने के लिए $O(n)$ समय की आवश्यकता होती है।^[1]

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

मिनहैश की गणना में वज़न प्रस्तुत करने के लिए कई तरह की विधियों का विकास किया गया है। सरलतम इसे पूर्णांक भार तक बढ़ाता है।^[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 {\tfrac {1}{\epsilon }}$ , तब

\underset{h \in H}{Pr} [

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Anonymous

Search

मिनहैश

Namespaces

More

Page actions

Contents