การตรวจหาข้อมูลซ้ำแบบคล้ายกันด้วย Jaccard similarity และ MinHash

 (blog.nelhage.com)
1 คะแนน โดย GN⁺ 2024-07-06 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

การค้นหาเอกสารที่คล้ายกัน: Jaccard similarity และ MinHash

  • นิยามปัญหา
    • กล่าวถึงวิธีระบุเอกสารที่คล้ายกันในคอลเลกชันเอกสารขนาดใหญ่
    • ตัวอย่างเช่น เมื่อดึงข้อมูลผ่านการทำเว็บครอล อาจมีการดึงหน้าเดียวกันมาหลายครั้ง ทำให้เกิดความต่างเล็กน้อยในเมทาดาทา หรือมีหลายเวอร์ชันหลังการแก้ไขเพียงเล็กน้อย
    • บทความนี้สำรวจวิธี deduplication แบบประมาณค่าด้วย Jaccard similarity และ MinHash

ความคล้ายกัน

  • นิยามความคล้ายกัน
    • นิยามความคล้ายกันระหว่างเอกสารสองฉบับ และวิธีค้นหาคู่ที่มีค่าความคล้ายกันมากกว่าหรือเท่ากับค่าเกณฑ์ที่กำหนด
    • นิยามฟังก์ชันความคล้ายกัน S:U×U→[0,1] และถือว่าเอกสารสองฉบับเป็นข้อมูลซ้ำแบบประมาณค่าเมื่อ S(A,B)≥S_crit

Jaccard similarity

  • Jaccard similarity
    • ฟังก์ชันที่แสดงความคล้ายกันของเซตจำกัดสองเซตด้วยอัตราส่วนของอินเตอร์เซกชันต่อยูเนียน
    • J(A,B)=∣A∩B∣/∣A∪B∣
    • ยิ่งสองเซตคล้ายกันมาก ก็จะยิ่งมีองค์ประกอบส่วนใหญ่เหมือนกัน

การขยายการใช้ Jaccard similarity

  • วิธีการขยาย
    • แปลงเอกสารให้เป็นเซตของคุณลักษณะ แล้วค้นหาเซตที่มีค่า Jaccard similarity สูง
    • ใช้ได้โดยตรงกับคอร์ปัสขนาดเล็ก แต่จะไม่มีประสิทธิภาพในคอร์ปัสขนาดใหญ่

การประมาณค่า Jaccard similarity

  • ลายเซ็น MinHash
    • ใช้การสุ่มตัวอย่างเพื่อประมาณค่า Jaccard similarity
    • คำนวณลายเซ็นขนาดคงที่ล่วงหน้าสำหรับแต่ละเอกสาร เพื่อประเมินความคล้ายกันได้อย่างมีประสิทธิภาพ

การใช้แฮชฟังก์ชันมากขึ้น

  • แฮชฟังก์ชันหลายตัว
    • ใช้แฮชฟังก์ชันหลายตัวเพื่อสรุปแต่ละเอกสารเป็นเวกเตอร์ขนาด k องค์ประกอบ
    • นับจำนวนค่าแฮชที่ตรงกันระหว่างลายเซ็นสองชุดเพื่อประมาณค่า Jaccard similarity

การเปรียบเทียบเอกสารทั้งหมด

  • การจัดกลุ่มเอกสาร
    • จัดกลุ่มเอกสารเพื่อเปรียบเทียบเฉพาะเอกสารที่คล้ายกัน
    • ใช้ค่า MinHash เป็นคีย์สำหรับการจัดกลุ่มเพื่อค้นหาข้อมูลซ้ำแบบประมาณค่าได้อย่างมีประสิทธิภาพ

การตรวจหาข้อมูลซ้ำที่ยืดหยุ่นมากขึ้น

  • การใช้หลายคีย์
    • ใช้หลายคีย์เพื่อวางเอกสารลงในหลายบักเก็ต และเปรียบเทียบภายในแต่ละบักเก็ต
    • ทำให้สามารถตรวจหาข้อมูลซ้ำได้แม้ที่ค่าความคล้ายกันต่ำลง

บทสรุป

  • บทสรุป
    • สามารถค้นหาเอกสารที่คล้ายกันได้อย่างมีประสิทธิภาพด้วยอัลกอริทึมอย่าง MinHash
    • หวังว่าบทความนี้จะช่วยแนะนำอัลกอริทึมเหล่านี้ให้วิศวกรมากขึ้นและช่วยให้เข้าใจได้ง่ายขึ้น

ภาคผนวก: การแทนเอกสารเป็นเซต

  • n-gram

    • แทนเอกสารด้วย n-gram เพื่อใช้ในการเปรียบเทียบ
    • ความละเอียดของการเปรียบเทียบจะแตกต่างกันไปตามค่า n

  • การแบ่งคำ

    • แบ่งเอกสารเป็นคำหรือโทเค็นเพื่อใช้เป็นคุณลักษณะ
    • อาจใช้ tokenizer ที่ซับซ้อนยิ่งขึ้นได้เช่นกัน

ความเห็นของ GN⁺

  • ความสำคัญของการตรวจหาเอกสารที่คล้ายกัน

    • การกำจัดข้อมูลซ้ำในชุดข้อมูลขนาดใหญ่มีความสำคัญต่อการยกระดับคุณภาพข้อมูลและการประหยัดพื้นที่จัดเก็บ
    • โดยเฉพาะอย่างยิ่ง เป็นสิ่งจำเป็นในกระบวนการเว็บครอลหรือการรวบรวมข้อมูล

  • ข้อดีของ MinHash

    • MinHash สามารถตรวจหาเอกสารที่คล้ายกันได้อย่างมีประสิทธิภาพและขยายขนาดได้ดี
    • มีความยืดหยุ่นมากกว่าวิธี deduplication แบบอิงแฮชดั้งเดิม

  • เทคนิคอื่นที่คล้ายกัน

    • อัลกอริทึมสเก็ตช์อื่น ๆ เช่น HyperLogLog ก็สามารถใช้แก้ปัญหาที่คล้ายกันได้เช่นกัน
    • สามารถผสานสองอัลกอริทึมเข้าด้วยกันเพื่อสร้างโซลูชันที่ทรงพลังยิ่งขึ้น

  • ข้อพิจารณาเมื่อนำไปใช้จริง

    • ความสำคัญของการเลือกแฮชฟังก์ชัน: การเลือกแฮชฟังก์ชันส่งผลอย่างมากต่อความแม่นยำของผลลัพธ์
    • สมดุลระหว่างประสิทธิภาพและความแม่นยำ: ยิ่งใช้แฮชฟังก์ชันมาก ความแม่นยำก็ยิ่งสูง แต่ต้นทุนด้านประสิทธิภาพก็เพิ่มขึ้น

  • เทคโนโลยีที่แนะนำ

    • สามารถนำไปใช้ได้ง่ายด้วยเครื่องมืออย่าง Spark MinHashLSH implementation
    • แนะนำให้ใช้เทคนิคเหล่านี้อย่างจริงจังเพื่อ deduplication ที่มีประสิทธิภาพในชุดข้อมูลขนาดใหญ่

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-07-06
ความคิดเห็นจาก Hacker News

  • ความคล้ายแบบ Jaccard และคะแนน F1 สามารถใช้กับ fuzzy set ได้เหมือนกัน

    • สำหรับ fuzzy set ต้องเลือกคู่ T-Norm/T-Conorm ที่เหมาะสม
    • วิธีนี้มีประโยชน์สำหรับการตรวจสอบความถูกต้องของการแบ่งส่วนภาพทางการแพทย์
    • คนส่วนใหญ่มักตั้งค่า threshold ไว้ที่ 0.5 แล้วใช้ binary set
    • สิ่งนี้ทำให้ความแม่นยำของตัวดำเนินการตรวจสอบลดลงอย่างมาก

  • เคยมีประสบการณ์ทำการลบข้อมูลซ้ำในฐานข้อมูลของรัฐบาลฝรั่งเศสด้วย Python

    • ตอนนี้แนะนำ datasketch
    • ยังมีเครื่องมือใหม่ชื่อ rensa
    • rensa เป็นเวอร์ชันที่เร็วกว่าและเขียนด้วย Rust

  • นี่เป็นเทคโนโลยีที่พัฒนาขึ้นในช่วงแรกของ Google เพื่อใช้ลบข้อมูลซ้ำ

    • มีการอธิบายไว้อย่างละเอียดใน "Mining Massive Datasets" ของ Jeffrey Ullman
    • เทคโนโลยีนี้ถูกพัฒนาขึ้นครั้งแรกที่ AltaVista

  • เคยมีประสบการณ์สร้างระบบ Minhash

    • ใช้แก้ปัญหาการหา (pseudo-)inverse ของ submatrix ในเมทริกซ์ขนาดใหญ่
    • ใช้ Minhashing เพื่อค้นหาเมทริกซ์ที่คล้ายกัน
    • ใช้ multiresolution hash เพื่อปรับ search selectivity

  • กำลังพัฒนาเครื่องมือ visualization เพราะ Minhash และตัวแปรของมันเข้าใจได้ยาก

    • มีแผนจะรวมการคำนวณความคล้ายแบบ Jaccard ไว้ด้วย

  • การทำความเข้าใจเทคนิคนี้ผ่านตัวอย่างโค้ดทำได้ง่ายกว่า

    • ได้เรียนรู้เทคนิคนี้จาก Douglas Eck ของ Google
    • มันถูกนำไปใช้กับการจัดกลุ่มเพลง

  • ทีม NVIDIA ได้เปิดตัวอัลกอริทึมลบข้อมูลซ้ำแบบ fuzzy ที่เร่งด้วย GPU

    • มีทั้ง GitHub repository และเอกสารประกอบ
    • รวมตัวอย่าง Python ไว้ด้วย

  • กลยุทธ์การลบข้อมูลซ้ำที่ผสานการแฮช หรือ neural network ขนาดเล็ก เข้ากับ vector search engine เป็นเรื่องที่พบได้ทั่วไป

    • มีโมเดล RETSim ของ Google และโปรเจกต์เอนจิน USearch

  • ได้แจ้งผู้เขียนเรื่องคำพิมพ์ผิด

    • ควรเป็น S(A,C) ไม่ใช่ S(A,B)

  • กำลังแก้ปัญหาการรวมข่าวที่คล้ายกันให้เหลือรายการเดียวใน Postgres

    • มีรายการจากฟีด 600,000 รายการ
    • เนื้อหาและสรุปมีความคล้ายกันมาก