Jaccard समानता और MinHash का उपयोग करके समान-डुप्लिकेट पहचान

 (blog.nelhage.com)
1 पॉइंट द्वारा GN⁺ 2024-07-06 | 1 टिप्पणियां | WhatsApp पर शेयर करें

समान दस्तावेज़ खोजना: Jaccard समानता और MinHash

  • समस्या की परिभाषा
    • बड़े दस्तावेज़ संग्रह में समान दस्तावेज़ों की पहचान करने के तरीके पर चर्चा की गई है
    • उदाहरण के लिए, वेब क्रॉलिंग के जरिए एक ही पेज कई बार लाए जाने पर मेटाडेटा में हल्का अंतर या छोटे संपादन के बाद के कई वर्ज़न हो सकते हैं
    • इस लेख में Jaccard समानता और MinHash का उपयोग करके approximate deduplication के तरीकों का अध्ययन किया गया है

समानता

  • समानता की परिभाषा
    • दो दस्तावेज़ों के बीच समानता को परिभाषित करना, और ऐसे युग्म ढूँढ़ना जिनका समानता मान किसी निश्चित threshold से अधिक हो
    • समानता फ़ंक्शन S:U×U→[0,1] को परिभाषित किया जाता है, और यदि S(A,B)≥S_crit हो तो दोनों दस्तावेज़ों को approximate duplicate माना जाता है

Jaccard समानता

  • Jaccard समानता
    • दो सीमित समुच्चयों की समानता को उनके intersection और union के अनुपात के रूप में व्यक्त करने वाला फ़ंक्शन
    • J(A,B)=∣A∩B∣/∣A∪B∣
    • जितने अधिक दो समुच्चय समान होंगे, उनमें अधिकांश तत्व समान होंगे

Jaccard समानता का विस्तार

  • विस्तार की विधि
    • दस्तावेज़ों को फीचर समुच्चयों में बदलकर, उच्च Jaccard समानता वाले समुच्चयों की खोज की जाती है
    • छोटे corpus में इसे सीधे लागू किया जा सकता है, लेकिन बड़े corpus में यह अक्षम हो जाता है

Jaccard समानता का approximation

  • MinHash signature
    • Jaccard समानता का approximation करने के लिए sampling का उपयोग किया जाता है
    • प्रत्येक दस्तावेज़ के लिए निश्चित आकार की signature पहले से गणना कर, समानता का कुशल अनुमान लगाया जाता है

अधिक hash functions का उपयोग

  • बहु hash functions
    • कई hash functions का उपयोग कर प्रत्येक दस्तावेज़ को k-तत्व वाले vector में सारांशित किया जाता है
    • दो signatures के बीच मेल खाने वाले hash की संख्या गिनकर Jaccard समानता का approximation किया जाता है

सभी दस्तावेज़ों की तुलना

  • दस्तावेज़ समूहकरण
    • दस्तावेज़ों को समूहित कर केवल समान दस्तावेज़ों की ही तुलना की जाती है
    • MinHash मानों को grouping key के रूप में उपयोग कर कुशलता से approximate duplicates खोजे जाते हैं

अधिक लचीली डुप्लिकेट पहचान

  • कई keys का उपयोग
    • कई keys का उपयोग कर दस्तावेज़ों को कई buckets में रखा जाता है, और प्रत्येक bucket के भीतर तुलना की जाती है
    • इससे कम समानता मानों पर भी duplicates की पहचान की जा सकती है

निष्कर्ष

  • निष्कर्ष
    • MinHash जैसे algorithms के माध्यम से समान दस्तावेज़ों को कुशलता से खोजा जा सकता है
    • आशा है कि यह लेख अधिक इंजीनियरों को ऐसे algorithms से परिचित कराएगा और उनकी समझ बढ़ाएगा

परिशिष्ट: दस्तावेज़ों को समुच्चय के रूप में व्यक्त करना

  • n-gram

    • दस्तावेज़ों को n-gram के रूप में व्यक्त कर तुलना की जाती है
    • n के मान के अनुसार तुलना की सटीकता बदलती है

  • शब्द विभाजन

    • दस्तावेज़ों को शब्दों या tokens में विभाजित कर फीचर के रूप में उपयोग किया जाता है
    • अधिक परिष्कृत tokenizer का भी उपयोग किया जा सकता है

GN⁺ की राय

  • समान दस्तावेज़ पहचान का महत्व

    • बड़े datasets में duplicates हटाना डेटा गुणवत्ता बढ़ाने और storage space बचाने के लिए महत्वपूर्ण है
    • खास तौर पर वेब क्रॉलिंग या डेटा संग्रह की प्रक्रिया में यह आवश्यक है

  • MinHash के फायदे

    • MinHash समान दस्तावेज़ों की पहचान एक कुशल और scalable तरीके से कर सकता है
    • यह पारंपरिक hash-आधारित deduplication तरीकों की तुलना में अधिक लचीला है

  • अन्य समान तकनीकें

    • HyperLogLog जैसे अन्य sketch algorithms भी इसी तरह की समस्याओं के समाधान में उपयोग किए जा सकते हैं
    • दोनों algorithms को मिलाकर अधिक शक्तिशाली समाधान बनाया जा सकता है

  • वास्तविक उपयोग में ध्यान देने योग्य बातें

    • hash function चुनने का महत्व: hash function का चयन परिणामों की शुद्धता पर बड़ा प्रभाव डालता है
    • प्रदर्शन और शुद्धता के बीच संतुलन: अधिक hash functions उपयोग करने पर शुद्धता बढ़ती है, लेकिन performance cost भी बढ़ती है

  • अनुशंसित तकनीक

    • Spark की MinHashLSH implementation जैसे tools का उपयोग कर इसे आसानी से लागू किया जा सकता है
    • बड़े datasets में कुशल deduplication के लिए ऐसी तकनीकों का सक्रिय रूप से उपयोग करने की सिफारिश की जाती है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-07-06
Hacker News राय

  • Jaccard समानता और F1 स्कोर का उपयोग fuzzy sets में भी समान रूप से किया जा सकता है

    • fuzzy sets में उपयुक्त T-Norm/T-Conorm जोड़ी चुननी होती है
    • यह तरीका medical image segmentation validation में उपयोगी है
    • ज़्यादातर लोग threshold को 0.5 पर सेट करके binary sets का उपयोग करते हैं
    • इससे validation operator की precision काफ़ी कम हो जाती है

  • Python में फ्रांसीसी सरकारी database की deduplication लागू करने का अनुभव है

    • अभी datasketch की सिफारिश की जाती है
    • rensa नाम का एक नया टूल भी है
    • rensa, Rust में लिखा गया एक तेज़ version है

  • यह Google के शुरुआती दौर में deduplication के लिए विकसित की गई तकनीक है

    • Jeffrey Ullman की "Mining Massive Datasets" में इसका विस्तार से वर्णन है
    • यह तकनीक पहली बार AltaVista में विकसित की गई थी

  • Minhash system लागू करने का अनुभव है

    • बड़े matrices के submatrices के (लगभग) inverse matrices खोजने की समस्या हल की गई
    • Minhashing का उपयोग करके समान matrices खोजे गए
    • multi-resolution hash का उपयोग कर search selectivity को समायोजित किया गया

  • Minhash और उसके variants को समझना कठिन लगने पर एक visualization tool विकसित किया जा रहा है

    • इसमें Jaccard समानता की गणना भी शामिल की जाएगी

  • code examples के ज़रिए तकनीक को समझना अधिक आसान है

    • यह तकनीक Google के Douglas Eck से सीखी गई
    • इसका उपयोग गानों की clustering में किया गया

  • NVIDIA टीम ने GPU-accelerated fuzzy deduplication algorithm जारी किया है

    • GitHub repository और documentation उपलब्ध हैं
    • Python examples भी शामिल हैं

  • hashing या छोटे neural network को vector search engine के साथ जोड़ने वाली deduplication strategy आम है

    • Google का RETSim model और USearch engine project मौजूद हैं

  • लेखक को typo की ओर इशारा किया गया

    • S(A,B) की जगह S(A,C) होना चाहिए

  • Postgres में मिलते-जुलते news items को एक में समेटने की समस्या पर काम चल रहा है

    • 600,000 feed items हैं
    • content और summary बहुत समान हैं