ในวิทยาศาสตร์คอมพิวเตอร์และการทำเหมืองข้อมูลMinHash (หรือรูป แบบแฮชแบบ min-wise independent permutations locality sensitive hashing scheme) เป็นเทคนิคสำหรับการประเมินความคล้ายคลึงกันของสองชุดข้อมูลอย่างรวดเร็ว รูปแบบนี้ได้รับการเผยแพร่โดยAndrei Broderในการประชุมเมื่อปี 1997 ^{[ 1 ]}และถูกนำมาใช้ครั้งแรกใน เครื่องมือค้นหา AltaVistaเพื่อตรวจจับหน้าเว็บที่ซ้ำกันและกำจัดออกจากผลการค้นหา^{[ 2 ]} นอกจากนี้ยังถูกนำไปใช้ในปัญหา การจัดกลุ่มขนาดใหญ่เช่นการจัดกลุ่มเอกสารตามความคล้ายคลึงกันของชุดคำ^{[ 1 ]}

สัมประสิทธิ์ความคล้ายคลึงของจาคาร์ด ( Jaccard similarity coefficient)เป็นตัวบ่งชี้ที่ใช้กันทั่วไปในการวัดความคล้ายคลึงระหว่างเซตสองเซต ให้Uเป็นเซต และAกับBเป็นเซตย่อยของUแล้ว ดัชนีจาคาร์ดถูกกำหนดให้เป็นอัตราส่วนของจำนวนสมาชิกในส่วนที่ทั้งสองเซตตัดกัน (intersection)และจำนวนสมาชิกใน ส่วนที่ทั้งสองเซตรวมกัน (union) :

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

ค่านี้จะเป็น 0 เมื่อเซตทั้งสองไม่มีส่วนร่วมกันจะเป็น 1 เมื่อเซตทั้งสองเท่ากัน และจะเป็นค่าระหว่าง 0 ถึง 1 ในกรณีอื่นๆ เซตสองเซตจะมีความคล้ายคลึงกันมากขึ้น (กล่าวคือ มีสมาชิกที่เหมือนกันมากกว่า) เมื่อดัชนี Jaccard ของเซตทั้งสองใกล้เคียงกับ 1 เป้าหมายของ MinHash คือการประมาณค่าJ ( A , B )อย่างรวดเร็ว โดยไม่ต้องคำนวณส่วนร่วมและส่วนตัดกันอย่างชัดเจน

ให้hเป็นฟังก์ชันแฮชที่แมปสมาชิกของUไปยังจำนวนเต็มที่แตกต่างกัน ให้permเป็นการเรียงสับเปลี่ยน แบบสุ่ม ขององค์ประกอบในเซตUและสำหรับเซตย่อยS ใดๆ ของUให้กำหนดh _min ( S )เป็นสมาชิกที่เล็กที่สุดของSเมื่อเทียบกับh ∘ perm —นั่นคือ สมาชิกxของSที่มีค่าh ( perm ( x )) น้อยที่สุด (ในกรณีที่ฟังก์ชันแฮชที่ใช้ถือว่ามีคุณสมบัติแบบสุ่มเทียม การเรียงสับเปลี่ยนแบบสุ่มจะไม่ถูกนำมาใช้)

ทีนี้ เมื่อใช้h _minกับทั้งAและBและสมมติว่าไม่มีการชนกันของแฮช เราจะเห็นว่าค่าเท่ากัน ( h _min ( A ) = h _min ( B ) ) ก็ต่อเมื่อในบรรดาองค์ประกอบทั้งหมดขององค์ประกอบที่มีค่าแฮชต่ำสุดอยู่ในส่วนที่ตัดกันความน่าจะเป็นที่จะเป็นจริงเช่นนี้คือดัชนี Jaccard พอดี ดังนั้น: ${\displaystyle A\cup B}$${\displaystyle A\cap B}$

${\displaystyle {\text{Pr}}[h_{\text{min}}(A)=h_{\text{min}}(B)]=J(A,B),}$

กล่าวคือความน่าจะเป็นที่h _min ( A ) = h _min ( B )เป็นจริงนั้น เท่ากับค่าความคล้ายคลึงJ ( A , B )โดยสมมติว่าสุ่มค่า permจากการแจกแจงแบบเอกรูป กล่าวอีกนัยหนึ่ง ถ้าrเป็นตัวแปรสุ่มที่มีค่าเป็น 1 เมื่อh _min ( A ) = h _min ( B )และมีค่าเป็น 0 ในกรณีอื่น ๆ แล้วrเป็นตัวประมาณค่าที่ไม่เอนเอียงของJ ( A , B )อย่างไรก็ตามr มี ความแปรปรวนสูงเกินไปที่จะเป็นตัวประมาณค่าที่มีประโยชน์สำหรับค่าความคล้ายคลึงของ Jaccard ด้วยตัวมันเอง เพราะr มีค่าเป็นศูนย์หรือหนึ่งเสมอ แนวคิดของวิธีการ MinHash คือการลดความแปรปรวนนี้โดยการหาค่าเฉลี่ยของตัวแปรหลายตัวที่สร้างขึ้นในลักษณะเดียวกัน ${\displaystyle r}$

รูปแบบที่ง่ายที่สุดของแผนการ minhash ใช้ฟังก์ชันแฮชที่แตกต่างกันk ฟังก์ชัน โดยที่ kเป็นพารามิเตอร์จำนวนเต็มคงที่ และแทนแต่ละเซตSด้วย ค่า h _min ( S )จำนวนk ค่า สำหรับฟังก์ชัน ทั้ง k ฟังก์ชันนี้

ในการประมาณค่าJ ( A , B )โดยใช้รูปแบบนี้ ให้yเป็นจำนวนฟังก์ชันแฮชที่h _min ( A ) = h _min ( B )และใช้y / kเป็นค่าประมาณ ค่าประมาณนี้เป็นค่าเฉลี่ยของ ตัวแปรสุ่ม 0-1 ที่แตกต่างกัน kตัว โดยแต่ละตัวจะมีค่าเป็น 1 เมื่อh _min ( A ) = h _min ( B )และเป็น 0 ในกรณีอื่น ๆ และแต่ละตัวเป็นตัวประมาณค่าที่ไม่เอนเอียงของ J ( A , B )ดังนั้น ค่าเฉลี่ยของพวกมันจึงเป็นตัวประมาณค่าที่ไม่เอนเอียงเช่นกัน และโดยค่าเบี่ยงเบนมาตรฐานสำหรับผลรวมของตัวแปรสุ่ม 0-1 ข้อผิดพลาดที่คาดหวังคือO (1/ √ k ) ^{[ 3 ]}

ดังนั้น สำหรับค่าคงที่ε > 0 ใดๆ จะมีค่าคงที่k = O(1/ε ² )ที่ทำให้ค่าความคลาดเคลื่อนที่คาดหวังของการประมาณมีค่าไม่เกิน  εตัวอย่างเช่น จะต้องใช้แฮช 400 ครั้งในการประมาณค่าJ ( A , B )โดยมีค่าความคลาดเคลื่อนที่คาดหวังน้อยกว่าหรือเท่ากับ 0.05

การคำนวณฟังก์ชันแฮชหลายฟังก์ชันอาจใช้ทรัพยากรมาก แต่รูปแบบหนึ่งของ MinHash จะหลีกเลี่ยงค่าใช้จ่ายนี้โดยใช้ฟังก์ชันแฮชเพียงฟังก์ชันเดียว และใช้ฟังก์ชันนั้นในการเลือกค่าหลายค่าจากแต่ละเซต แทนที่จะเลือกค่าต่ำสุดเพียงค่าเดียวต่อฟังก์ชันแฮช ให้hเป็นฟังก์ชันแฮช และให้kเป็นจำนวนเต็มคงที่ ถ้าSเป็นเซตของ ค่า kค่าขึ้นไปในโดเมนของhให้กำหนดh _{( k )} ( S )เป็นเซตย่อยของ สมาชิก k ตัวในS ที่มีค่า hน้อยที่สุด เซตย่อย h _{( k )} ( S )นี้ใช้เป็นลายเซ็นสำหรับเซตSและความคล้ายคลึงกันของสองเซตใดๆ จะถูกประเมินโดยการเปรียบเทียบลายเซ็นของเซตเหล่านั้น

โดยเฉพาะอย่างยิ่ง ให้AและBเป็นเซตใดๆ สองเซต แล้วX = h _{( k )} ( h _{( k )} ( A ) ∪ h _{( k )} ( B )) = h _{( k )} ( A ∪ B )คือเซตของ สมาชิก kตัวในA ∪ Bและถ้าhเป็นฟังก์ชันสุ่ม เซตย่อยใดๆ ที่มี สมาชิก kตัวจะมีโอกาสถูกเลือกเท่าๆ กัน นั่นคือXเป็นตัวอย่างสุ่มอย่างง่ายของA ∪ Bเซตย่อยY = X ∩ h _{( k )} ( A ) ∩ h _{( k )} ( B )คือเซตของสมาชิกในXที่อยู่ในส่วนที่ตัดกันของA ∩ Bดังนั้น | Y |/ kจึงเป็นตัวประมาณค่าที่ไม่เอนเอียงของJ ( A , B )ความแตกต่างระหว่างตัวประมาณค่านี้กับตัวประมาณค่าที่ได้จากฟังก์ชันแฮชหลายตัวคือXจะมี สมาชิก k ตัวเสมอ ในขณะที่ฟังก์ชันแฮชหลายตัวอาจทำให้จำนวนองค์ประกอบที่สุ่มได้น้อยลง เนื่องจากความเป็นไปได้ที่ฟังก์ชันแฮชสองฟังก์ชันที่แตกต่างกันอาจมีค่าต่ำสุดเดียวกัน อย่างไรก็ตาม เมื่อkมีขนาดเล็กเมื่อเทียบกับขนาดของเซต ความแตกต่างนี้ก็แทบจะไม่มีนัยสำคัญ

ตามขอบเขตมาตรฐานของ Chernoffสำหรับการสุ่มตัวอย่างโดยไม่ใส่คืน ตัวประมาณค่านี้มีข้อผิดพลาดที่คาดหวังO(1/ √ k )ซึ่งตรงกับประสิทธิภาพของวิธีการฟังก์ชันแฮชหลายตัว

ตัวประมาณค่า| Y |/ kสามารถคำนวณได้ในเวลาO( k )จากลายเซ็นสองชุดของเซตที่กำหนด ในรูปแบบใดก็ได้ของแผนการ ดังนั้น เมื่อεและkเป็นค่าคงที่ เวลาในการคำนวณความคล้ายคลึงโดยประมาณจากลายเซ็นก็จะเป็นค่าคงที่เช่นกัน ลายเซ็นของแต่ละเซตสามารถคำนวณได้ในเวลาเชิงเส้นตามขนาดของเซต ดังนั้นเมื่อจำเป็นต้องประมาณความคล้ายคลึงแบบคู่จำนวนมาก วิธีนี้สามารถช่วยประหยัดเวลาในการทำงานได้อย่างมากเมื่อเทียบกับการเปรียบเทียบสมาชิกของแต่ละเซตทั้งหมด โดยเฉพาะอย่างยิ่ง สำหรับขนาดเซตnรูปแบบแฮชหลายตัวใช้ เวลา O( n k )รูปแบบแฮชเดี่ยวโดยทั่วไปจะเร็วกว่า โดยต้องใช้ เวลา O( ⁿ )ในการรักษาคิวของค่าแฮชขั้นต่ำโดยสมมติว่าn >> k [ ^{1 ]}

มีการพัฒนาเทคนิคต่างๆ มากมายเพื่อนำน้ำหนักมาใช้ในการคำนวณ MinHashes วิธีที่ง่ายที่สุดคือการขยายไปสู่น้ำหนักจำนวนเต็ม^{[ 4 ]} ขยายฟังก์ชันแฮชh ของเรา ให้ยอมรับทั้งสมาชิกเซตและจำนวนเต็ม จากนั้นสร้างแฮชหลายรายการสำหรับแต่ละรายการตามน้ำหนัก หากรายการiปรากฏnครั้ง ให้สร้างแฮชเรียกใช้อัลกอริทึมดั้งเดิมกับชุดแฮชที่ขยายนี้ การทำเช่นนี้จะให้ดัชนี Jaccard ที่ถ่วงน้ำหนักเป็นความน่าจะเป็นของการชนกัน ${\displaystyle h(i,1),h(i,2),\ldots ,h(i,n)}$

${\displaystyle J_{\mathcal {W}}(x,y)={\frac {\sum _{i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}}}$

ส่วนขยายเพิ่มเติมที่ทำให้ความน่าจะเป็นของการชนกันนี้เกิดขึ้นกับน้ำหนักจริงด้วยเวลาการทำงานที่ดีขึ้นได้รับการพัฒนาขึ้น โดยหนึ่งสำหรับข้อมูลหนาแน่น^{[ 5 ]}และอีกหนึ่งสำหรับข้อมูลเบาบาง^{[ 6 ]}

อีกกลุ่มหนึ่งของส่วนขยายใช้แฮชที่มีการกระจายแบบเอกซ์โปเนนเชียล แฮชแบบสุ่มสม่ำเสมอระหว่าง 0 ถึง 1 สามารถแปลงให้มีการกระจายแบบเอกซ์โปเนนเชียลได้โดยการผกผันฟังก์ชันสะสม (CDF inversion ) วิธีนี้ใช้ประโยชน์จากคุณสมบัติที่ยอดเยี่ยมมากมายของค่าต่ำสุดของชุดตัวแปรเอกซ์โปเนนเชียล

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

ส่งผลให้ความน่าจะเป็นของการชนกันเป็นดัชนีความน่าจะเป็น Jaccard ^{[ 7 ]}

${\displaystyle 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)}}}$

ในการนำวิธีการ MinHash ไปใช้ตามที่อธิบายไว้ข้างต้น จำเป็นต้องใช้ฟังก์ชันแฮชhเพื่อกำหนดการเรียงสับเปลี่ยนแบบสุ่มบนองค์ประกอบn ตัว โดยที่ nคือจำนวนองค์ประกอบที่แตกต่างกันทั้งหมดในผลรวมของเซตทั้งหมดที่จะนำมาเปรียบเทียบ แต่เนื่องจากมี การเรียงสับเปลี่ยนที่แตกต่างกัน n ! แบบ จึงต้องใช้ บิต Ω( n log n )เพื่อกำหนดการเรียงสับเปลี่ยนแบบสุ่มอย่างแท้จริง ซึ่งเป็นจำนวนที่มากเกินไปจนไม่สามารถทำได้แม้แต่กับค่าn ที่ไม่มากนัก ด้วยเหตุนี้ โดยเปรียบเทียบกับทฤษฎีการแฮชแบบสากลจึงมีการศึกษาค้นคว้าอย่างมากเกี่ยวกับการค้นหาตระกูลของการเรียงสับเปลี่ยนที่เป็น "อิสระแบบ min-wise" ซึ่งหมายความว่าสำหรับเซตย่อยใด ๆ ของโดเมน องค์ประกอบใด ๆ ก็มีโอกาสเท่ากันที่จะเป็นค่าต่ำสุด ได้มีการพิสูจน์แล้วว่าตระกูลของการเรียงสับเปลี่ยนที่เป็นอิสระแบบ min-wise จะต้องมีอย่างน้อย

${\displaystyle \operatorname {lcm} (1,2,\cdots ,n)\geq e^{no(n)}}$

การเรียงสับเปลี่ยนที่แตกต่างกัน และด้วยเหตุนี้จึงต้องใช้บิตΩ( n ) เพื่อระบุการเรียงสับเปลี่ยนเพียงรายการเดียว ซึ่งยังคงมีขนาดใหญ่เกินกว่าจะเป็นไปได้ ^{[ 2 ]}

เนื่องจากความไม่สามารถปฏิบัติได้จริงข้างต้น จึงมีการนำแนวคิดความเป็นอิสระขั้นต่ำสองรูปแบบมาใช้ ได้แก่ ตระกูลการเรียงสับเปลี่ยนที่เป็นอิสระขั้นต่ำแบบจำกัด และตระกูลที่เป็นอิสระขั้นต่ำโดยประมาณ ความเป็นอิสระขั้นต่ำแบบจำกัดคือคุณสมบัติความเป็นอิสระขั้นต่ำที่จำกัดไว้เฉพาะเซตที่มีขนาดไม่เกินk [ ^{8 ] ความ} เป็นอิสระขั้นต่ำโดยประมาณมีความน่าจะเป็นคงที่สูงสุดεที่จะแตกต่างจากความเป็นอิสระอย่างสมบูรณ์^{[ 9 ]}

ในปี พ.ศ. 2542 Piotr Indykพิสูจน์^{[ 10 ]}ว่าตระกูลฟังก์ชันแฮชที่เป็นอิสระแบบ k-wise ใดๆ ก็เป็นอิสระแบบ min-wise โดยประมาณสำหรับค่าที่มากพอ โดยเฉพาะอย่างยิ่ง มีค่าคงที่บางค่าที่ถ้าแล้ว ${\displaystyle k}$${\displaystyle c,c'>0}$${\displaystyle k\geq c\log {\tfrac {1}{\epsilon }}}$

${\displaystyle \Pr _{h\in {\mathcal {H}}}[h(x)<\min h(X)]={\frac {1}{|X|+1}}(1\pm \epsilon ),}$

สำหรับทุกเซตและ. (หมายเหตุ ในที่นี้หมายความว่าความน่าจะเป็นมีค่ามากที่สุดมากเกินไปหนึ่งเท่า และมีค่ามากที่สุดน้อยเกินไปหนึ่งเท่า) ${\displaystyle |X|\leq \epsilon nc'}$${\displaystyle x\not \in X}$${\displaystyle (1\pm \epsilon )}$${\displaystyle 1+\epsilon }$${\displaystyle 1-\epsilon }$

การรับประกันนี้เพียงพอที่จะให้ขอบเขต Jaccard ที่จำเป็นสำหรับอัลกอริทึม MinHash กล่าวคือ ถ้าและเป็นเซตแล้ว ${\displaystyle A}$${\displaystyle B}$

${\displaystyle \Pr _{h\in {\mathcal {H}}}[\min h(A)=\min h(B)]={\frac {|A\cap B|}{|A\cup B|}}\pm \epsilon .}$

เนื่องจากฟังก์ชันแฮชที่เป็นอิสระแบบ k-wiseสามารถระบุได้โดยใช้เพียงบิต วิธีการนี้จึงใช้งานได้จริงมากกว่าการใช้การเรียงสับเปลี่ยนที่เป็นอิสระแบบ min-wise อย่างสมบูรณ์ ${\displaystyle k\log n}$

อีกหนึ่งตระกูลของฟังก์ชันแฮชที่ใช้งานได้จริงและให้ความเป็นอิสระแบบ min-wise โดยประมาณคือTabulation hashing

แอปพลิเคชันดั้งเดิมของ MinHash เกี่ยวข้องกับการจัดกลุ่มและกำจัดคำที่ซ้ำกันในเอกสารเว็บ ซึ่งแสดงเป็นชุดของคำที่ปรากฏในเอกสารเหล่านั้น^{[ 1 ] [ 2 ] [ 11 ]}เทคนิคที่คล้ายกันนี้ยังถูกใช้สำหรับการจัดกลุ่มและกำจัดคำที่ซ้ำกันสำหรับข้อมูลประเภทอื่น เช่น รูปภาพ: ในกรณีของข้อมูลรูปภาพ รูปภาพสามารถแสดงเป็นชุดของรูปภาพย่อยขนาดเล็กที่ตัดมาจากรูปภาพหลัก หรือเป็นชุดของคำอธิบายคุณลักษณะของรูปภาพที่ซับซ้อนกว่า^{[ 12 ]}

ในการทำเหมืองข้อมูลCohen et al. (2001)ใช้ MinHash เป็นเครื่องมือสำหรับการเรียนรู้กฎความสัมพันธ์โดยกำหนดฐานข้อมูลที่แต่ละรายการมีคุณลักษณะหลายอย่าง (มองเป็นเมทริกซ์ 0–1ที่มีแถวต่อรายการในฐานข้อมูลและคอลัมน์ต่อคุณลักษณะ) พวกเขาใช้การประมาณค่าดัชนี Jaccard ตาม MinHash เพื่อระบุคู่คุณลักษณะที่เป็นไปได้ซึ่งมักเกิดขึ้นร่วมกัน จากนั้นคำนวณค่าที่แน่นอนของดัชนีสำหรับคู่เหล่านั้นเท่านั้นเพื่อกำหนดคู่ที่มีความถี่ของการเกิดขึ้นร่วมกันต่ำกว่าเกณฑ์ที่เข้มงวดที่กำหนดไว้^{[ 13 ]}

อัลกอริทึม MinHash ได้รับการปรับใช้สำหรับชีวสารสนเทศซึ่งปัญหาของการเปรียบเทียบลำดับจีโนมมีพื้นฐานทางทฤษฎีที่คล้ายคลึงกับการเปรียบเทียบเอกสารบนเว็บ เครื่องมือที่ใช้ MinHash ^{[ 14 ] [ 15 ]} ช่วยให้สามารถเปรียบเทียบ ข้อมูล การจัดลำดับจีโนมทั้งหมดกับจีโนมอ้างอิงได้อย่างรวดเร็ว (ใช้เวลาประมาณ 3 นาทีในการเปรียบเทียบหนึ่งจีโนมกับจีโนมอ้างอิง 90,000 จีโนมในRefSeq ) และเหมาะสมสำหรับการระบุสปีชีส์และอาจรวมถึงการจำแนกประเภทย่อยของจุลินทรีย์ในระดับจำกัด นอกจากนี้ยังมีการประยุกต์ใช้สำหรับเมตาจีโนมิกส์^{[ 14 ]}และการใช้อัลกอริทึมที่ได้มาจาก MinHash สำหรับการจัดเรียงจีโนมและการประกอบจีโนม^{[ 16 ]}สามารถสร้างค่าความเหมือนของนิวคลีโอไทด์เฉลี่ย (ANI) ที่แม่นยำได้อย่างมีประสิทธิภาพมากด้วยอัลกอริทึมที่ใช้ MinHash ^{[ 17 ]}

รูปแบบ MinHash อาจมองได้ว่าเป็นตัวอย่างหนึ่งของการแฮชแบบไวต่อตำแหน่งซึ่งเป็นชุดของเทคนิคการใช้ฟังก์ชันแฮชเพื่อแมปชุดวัตถุขนาดใหญ่ลงเป็นค่าแฮชที่เล็กลงในลักษณะที่ว่า เมื่อวัตถุสองชิ้นมีระยะห่างจากกันน้อย ค่าแฮชของพวกมันมักจะเหมือนกัน ในกรณีนี้ ลายเซ็นของชุดอาจมองได้ว่าเป็นค่าแฮชของมัน เทคนิคการแฮชแบบไวต่อตำแหน่งอื่นๆ มีอยู่สำหรับระยะทางแฮมมิงระหว่างชุดและระยะทางโคไซน์ระหว่างเวกเตอร์การแฮชแบบไวต่อตำแหน่งมีการใช้งานที่สำคัญในอัลกอริทึมการค้นหาเพื่อนบ้านที่ใกล้ที่สุด^{[ 18 ]}สำหรับระบบกระจายขนาดใหญ่ และโดยเฉพาะอย่างยิ่งMapReduceมีเวอร์ชันที่แก้ไขของ MinHash เพื่อช่วยคำนวณความคล้ายคลึงกันโดยไม่ขึ้นอยู่กับมิติของจุด^{[ 19 ]}

ในปี 2549 Googleได้ทำการประเมินขนาดใหญ่^{[ 20 ]} เพื่อเปรียบเทียบประสิทธิภาพของอัลกอริทึม Minhash และSimHash ^{[ 21 ]}ในปี 2550 Google รายงานว่าใช้ Simhash สำหรับการตรวจจับรายการซ้ำในการรวบรวมข้อมูลเว็บ^{[ 22 ]}และใช้ Minhash และLSHสำหรับ การปรับแต่ง Google Newsให้เป็นส่วนตัว^{[ 23 ]}

• Bloom filter  – โครงสร้างข้อมูลสำหรับการประมาณค่าสมาชิกเซต
•  โครงสร้างข้อมูลเชิงความน่าจะเป็นในวิทยาการคอมพิวเตอร์ เรียกว่าCount–min sketch
• มุงหลังคาแบบ w