Jaccard benzerliği ve MinHash ile yaklaşık yinelenenleri tespit etme

Benzer belgeleri bulma: Jaccard benzerliği ve MinHash

• Problem tanımı
  • Büyük ölçekli belge koleksiyonlarında benzer belgelerin nasıl tanımlanacağı tartışılıyor
  • Örneğin, web taraması yoluyla aynı sayfa birden fazla kez alındığında, üstveride küçük farklar veya küçük düzenlemelerden sonra oluşmuş birden fazla sürüm bulunabilir
  • Bu yazı, Jaccard benzerliği ve MinHash kullanarak yaklaşık yinelenenleri kaldırma yöntemini inceliyor

Benzerlik

• Benzerlik tanımı
  • İki belge arasındaki benzerliği tanımlama ve benzerlik değeri belirli bir eşik değerin üzerinde olan çiftleri bulma yöntemi
  • S:U×U→[0,1] benzerlik fonksiyonu tanımlanır ve S(A,B)≥S_crit ise iki belge yaklaşık yinelenen olarak kabul edilir

Jaccard benzerliği

• Jaccard benzerliği
  • İki sonlu küme arasındaki benzerliği, kesişimlerinin birleşimlerine oranı olarak ifade eden fonksiyon
  • J(A,B)=∣A∩B∣/∣A∪B∣
  • İki küme ne kadar benzerse, çoğu öğeyi o kadar ortak paylaşır

Jaccard benzerliğinin genişletilmesi

• Genişletme yöntemi
  • Belgeleri özellik kümelerine dönüştürüp yüksek Jaccard benzerliğine sahip kümeleri arama
  • Küçük bir korpusta doğrudan uygulanabilir, ancak büyük korpuslarda verimsizdir

Jaccard benzerliğini yaklaşık hesaplama

• MinHash imzası
  • Jaccard benzerliğini yaklaşık hesaplamak için örnekleme kullanılır
  • Her belge için sabit boyutlu bir imza önceden hesaplanarak benzerlik verimli biçimde tahmin edilir

Daha fazla hash fonksiyonu kullanma

• Çoklu hash fonksiyonları
  • Her belgeyi k öğeli bir vektöre özetlemek için birden fazla hash fonksiyonu kullanılır
  • Jaccard benzerliği, iki imza arasındaki eşleşen hash sayısı sayılarak yaklaşık hesaplanır

Tüm belgeleri karşılaştırma

• Belge gruplama
  • Belgeler gruplanarak yalnızca benzer belgeler karşılaştırılır
  • MinHash değerleri, yaklaşık yinelenenleri verimli şekilde bulmak için gruplama anahtarı olarak kullanılır

Daha esnek yinelenen tespiti

• Birden çok anahtar kullanımı
  • Belgeleri birden fazla kovaya yerleştirmek ve her kova içinde karşılaştırmak için birden çok anahtar kullanılır
  • Bu sayede daha düşük benzerlik değerlerinde de yinelenenler tespit edilebilir

Sonuç

• Sonuç
  • MinHash gibi algoritmalarla benzer belgeler verimli şekilde bulunabilir
  • Bu yazının, daha fazla mühendise bu tür algoritmaları tanıtması ve anlamayı kolaylaştırması umuluyor

Ek: Belgeleri küme olarak temsil etmek

• n-gramlar

  • Belgeler karşılaştırma için n-gramlarla temsil edilir
  • Karşılaştırmanın hassasiyeti n değerine göre değişir

• Sözcük bölütleme

  • Belgeler sözcüklere veya token'lara ayrılarak özellik olarak kullanılır
  • Daha gelişmiş tokenizer'lar da kullanılabilir

GN⁺ görüşü

• Benzer belge tespitinin önemi

  • Büyük veri kümelerinde yinelenenleri kaldırmak, veri kalitesini artırmak ve depolama alanından tasarruf etmek açısından önemlidir
  • Özellikle web taraması veya veri toplama süreçlerinde gereklidir

• MinHash'in avantajları

  • MinHash, benzer belgeleri verimli ve ölçeklenebilir bir şekilde tespit edebilir
  • Geleneksel hash tabanlı yinelenen kaldırma yöntemlerinden daha esnektir

• Diğer benzer teknikler

  • HyperLogLog gibi diğer sketch algoritmaları da benzer sorunları çözmek için kullanılabilir
  • İki algoritma birleştirilerek daha güçlü bir çözüm oluşturulabilir

• Gerçek uygulamalarda dikkat edilmesi gerekenler

  • Hash fonksiyonu seçiminin önemi: Hash fonksiyonu seçimi, sonuçların doğruluğunu büyük ölçüde etkiler
  • Performans ve doğruluk arasındaki denge: Daha fazla hash fonksiyonu kullanıldıkça doğruluk artar, ancak performans maliyeti de yükselir

• Önerilen teknoloji

  • Spark'ın MinHashLSH uygulaması gibi araçlarla kolayca uygulanabilir
  • Büyük veri kümelerinde verimli yinelenen kaldırma için bu tekniklerin etkin biçimde kullanılması önerilir

[GN⁺]

Hacker News görüşleri

• Jaccard benzerliği ve F1 skoru, bulanık kümelerde de aynı şekilde kullanılabilir

  • Bulanık kümelerde uygun bir T-Norm/T-Conorm çifti seçmek gerekir
  • Bu yöntem, tıbbi görüntü segmentasyonu doğrulamasında faydalıdır
  • Çoğu insan eşiği 0.5 olarak ayarlayıp ikili kümeler kullanır
  • Bu da doğrulama operatörünün hassasiyetini önemli ölçüde azaltır

• Python ile Fransız hükümetinin veritabanında mükerrer kayıt temizleme uyguladığım bir deneyimim oldu

  • Şu anda datasketch tavsiye ediyorum
  • rensa adlı yeni bir araç da var
  • rensa, Rust ile yazılmış daha hızlı bir sürüm

• Bu, Google’ın ilk dönemlerinde mükerrer temizleme için geliştirilen bir teknolojiydi

  • Jeffrey Ullman’ın "Mining Massive Datasets" kitabında ayrıntılı olarak anlatılır
  • Bu teknoloji ilk olarak AltaVista’da geliştirildi

• Bir Minhash sistemi uygulama deneyimim var

  • Büyük bir matrisin alt matrislerinin (yaklaşık) ters matrisini bulma problemini çözdü
  • Benzer matrisleri bulmak için Minhashing kullandım
  • Arama seçiciliğini ayarlamak için çoklu çözünürlüklü hash kullandım

• Minhash ve türevlerini anlamak zor olduğu için bir görselleştirme aracı geliştiriyorum

  • Jaccard benzerliği hesaplamasını da içerecek

• Tekniği kod örnekleriyle anlamak daha kolay

  • Bu tekniği Google’dan Douglas Eck’ten öğrendim
  • Şarkı kümeleme için kullanılıyor

• NVIDIA ekibi GPU hızlandırmalı bulanık mükerrer temizleme algoritmaları yayınladı

  • GitHub deposu ve dokümantasyon sağlanıyor
  • Python örnekleri de içeriyor

• Hashing veya küçük bir sinir ağı ile vektör arama motorunu birleştiren mükerrer temizleme stratejileri yaygın

  • Google’ın RETSim modeli ve USearch motoru projesi var

• Yazara bir yazım hatasını bildirdim

  • S(A,B) yerine S(A,C) olmalı

• Postgres’te benzer haber öğelerini teke indirme problemini çözüyorum

  • 600.000 feed öğesi var
  • İçerik ve özetler çok benzer