Spark Jaccard benzerlik hesaplaması önemsiz yaklaşımla karşılaştırıldığında min hashing slow

Question

2 büyük değerler listesi verildiğinde, Spark kullanarak Scala'da jaccard similarity arasında hesaplamaya çalışıyorum.

colHashed1 öğesinin ilk listesini içerir ve colHashed2 ikinci listeyi içerir.

Yaklaşım 1 (Bu etkiyi): (minHashing kullanılarak)

val jSimilarity = colHashed1.intersection(colHashed2).distinct.count/(colHashed1.union(colHashed2).distinct.count.toDouble) 

yaklaşım 2: yaklaşım kullandık

here açıklanmıştır.

import java.util.zip.CRC32 

def getCRC32 (s : String) : Int = 
{ 
    val crc=new CRC32 
    crc.update(s.getBytes) 
    return crc.getValue.toInt & 0xffffffff 
} 

val maxShingleID = Math.pow(2,32)-1 
def pickRandomCoeffs(kIn : Int) : Array[Int] = 
{ 
    var k = kIn 
    val randList = Array.fill(k){0} 

    while(k > 0) 
    { 
    // Get a random shingle ID. 

    var randIndex = (Math.random()*maxShingleID).toInt 

    // Ensure that each random number is unique. 
    while(randList.contains(randIndex)) 
    { 
     randIndex = (Math.random()*maxShingleID).toInt 
    } 

    // Add the random number to the list. 
    k = k - 1 
    randList(k) = randIndex 
    } 

    return randList 
} 

val colHashed1 = list1Values.map(a => getCRC32(a)) 
val colHashed2 = list2Values.map(a => getCRC32(a)) 

val nextPrime = 4294967311L 
val numHashes = 10 

val coeffA = pickRandomCoeffs(numHashes) 
val coeffB = pickRandomCoeffs(numHashes) 

var signature1 = Array.fill(numHashes){0} 
for (i <- 0 to numHashes-1) 
{ 
    // Evaluate the hash function. 
    val hashCodeRDD = colHashed1.map(ele => ((coeffA(i) * ele + coeffB(i)) % nextPrime)) 

    // Track the lowest hash code seen. 
    signature1(i) = hashCodeRDD.min.toInt 
} 

var signature2 = Array.fill(numHashes){0} 
for (i <- 0 to numHashes-1) 
{ 
    // Evaluate the hash function. 
    val hashCodeRDD = colHashed2.map(ele => ((coeffA(i) * ele + coeffB(i)) % nextPrime)) 

    // Track the lowest hash code seen. 
    signature2(i) = hashCodeRDD.min.toInt 
} 


var count = 0 
// Count the number of positions in the minhash signature which are equal. 
for(k <- 0 to numHashes-1) 
{ 
    if(signature1(k) == signature2(k)) 
    count = count + 1 
} 
val jSimilarity = count/numHashes.toDouble 

Yaklaşım 1 defa hep açısından Yaklaşım 2 daha iyi performans gibi görünüyor. Kodu analiz ettiğimde, Yaklaşım 2'deki RDD'daki min() işlev çağrısı önemli ölçüde zaman alır ve bu fonksiyonun kaç karma işlevinin kullanıldığına bağlı olarak defalarca çağrılır.

Yaklaşım 1'de kullanılan kesişim ve birleştirme işlemleri, tekrarlanan min() işlev çağrılarına göre daha hızlı çalışıyor gibi görünüyor.

Neden minHashing'in burada yardımcı olmadığını anlamıyorum. MinHashing'in önemsiz yaklaşıma göre daha hızlı çalışmasını bekledim. Burada yanlış yaptığım bir şey var mı?

Örnek veri MinHash ile here

Answer 1

JaccardSimilarity izlenebilir vermiyor tutarlı sonuçlar:

import java.util.zip.CRC32 

object Jaccard { 
    def getCRC32(s: String): Int = { 
    val crc = new CRC32 
    crc.update(s.getBytes) 
    return crc.getValue.toInt & 0xffffffff 
    } 

    def pickRandomCoeffs(kIn: Int, maxShingleID: Double): Array[Int] = { 
    var k = kIn 
    val randList = Array.ofDim[Int](k) 

    while (k > 0) { 
     // Get a random shingle ID. 
     var randIndex = (Math.random() * maxShingleID).toInt 
     // Ensure that each random number is unique. 
     while (randList.contains(randIndex)) { 
     randIndex = (Math.random() * maxShingleID).toInt 
     } 
     // Add the random number to the list. 
     k = k - 1 
     randList(k) = randIndex 
    } 
    return randList 
    } 


    def approach2(list1Values: List[String], list2Values: List[String]) = { 

    val maxShingleID = Math.pow(2, 32) - 1 

    val colHashed1 = list1Values.map(a => getCRC32(a)) 
    val colHashed2 = list2Values.map(a => getCRC32(a)) 

    val nextPrime = 4294967311L 
    val numHashes = 10 

    val coeffA = pickRandomCoeffs(numHashes, maxShingleID) 
    val coeffB = pickRandomCoeffs(numHashes, maxShingleID) 

    val signature1 = for (i <- 0 until numHashes) yield { 
     val hashCodeRDD = colHashed1.map(ele => (coeffA(i) * ele + coeffB(i)) % nextPrime) 
     hashCodeRDD.min.toInt // Track the lowest hash code seen. 
    } 

    val signature2 = for (i <- 0 until numHashes) yield { 
     val hashCodeRDD = colHashed2.map(ele => (coeffA(i) * ele + coeffB(i)) % nextPrime) 
     hashCodeRDD.min.toInt // Track the lowest hash code seen 
    } 

    val count = (0 until numHashes) 
     .map(k => if (signature1(k) == signature2(k)) 1 else 0) 
     .fold(0)(_ + _) 


    val jSimilarity = count/numHashes.toDouble 
    jSimilarity 
    } 


    // def approach1(list1Values: List[String], list2Values: List[String]) = { 
    // val colHashed1 = list1Values.toSet 
    // val colHashed2 = list2Values.toSet 
    // 
    // val jSimilarity = colHashed1.intersection(colHashed2).distinct.count/(colHashed1.union(colHashed2).distinct.count.toDouble) 
    // jSimilarity 
    // } 


    def approach1(list1Values: List[String], list2Values: List[String]) = { 
    val colHashed1 = list1Values.toSet 
    val colHashed2 = list2Values.toSet 

    val jSimilarity = (colHashed1 & colHashed2).size/(colHashed1 ++ colHashed2).size.toDouble 
    jSimilarity 
    } 

    def main(args: Array[String]) { 

    val list1Values = List("a", "b", "c") 
    val list2Values = List("a", "b", "d") 

    for (i <- 0 until 5) { 
     println(s"Iteration ${i}") 
     println(s" - Approach 1: ${approach1(list1Values, list2Values)}") 
     println(s" - Approach 2: ${approach2(list1Values, list2Values)}") 
    } 

    } 
} 

ÇIKIŞ: Neden bunu kullanıyor

Iteration 0 
- Approach 1: 0.5 
- Approach 2: 0.5 
Iteration 1 
- Approach 1: 0.5 
- Approach 2: 0.5 
Iteration 2 
- Approach 1: 0.5 
- Approach 2: 0.8 
Iteration 3 
- Approach 1: 0.5 
- Approach 2: 0.8 
Iteration 4 
- Approach 1: 0.5 
- Approach 2: 0.4 

?

Answer 2

Bana göre, MinHashing yaklaşımı için genel masraf, Spark'deki işlevselliğinden daha ağır basıyor. Özellikle numHashes artar. , while (randList.contains(randIndex)) bu bölümü mutlaka artar (RandList büyüklüğüne eşit arada olduğu) numHashes gibi sürecini yavaşlatacaktır

İlk: İşte kodunuzda buldum bazı gözlemler. Bu yöntem birine üç döngüler kolaylaştırır

var count = 0 
for (i <- 0 to numHashes - 1) 
{ 
    val hashCodeRDD1 = colHashed1.map(ele => ((coeffA(i) * ele + coeffB(i)) % nextPrime)) 
    val hashCodeRDD2 = colHashed2.map(ele => ((coeffA(i) * ele + coeffB(i)) % nextPrime)) 

    val sig1 = hashCodeRDD1.min.toInt 
    val sig2 = hashCodeRDD2.min.toInt 

    if (sig1 == sig2) { count = count + 1 } 
} 

içine

var signature1 = Array.fill(numHashes){0} 
for (i <- 0 to numHashes-1) 
{ 
    // Evaluate the hash function. 
    val hashCodeRDD = colHashed1.map(ele => ((coeffA(i) * ele + coeffB(i)) % nextPrime)) 

    // Track the lowest hash code seen. 
    signature1(i) = hashCodeRDD.min.toInt 
} 

var signature2 = Array.fill(numHashes){0} 
for (i <- 0 to numHashes-1) 
{ 
    // Evaluate the hash function. 
    val hashCodeRDD = colHashed2.map(ele => ((coeffA(i) * ele + coeffB(i)) % nextPrime)) 

    // Track the lowest hash code seen. 
    signature2(i) = hashCodeRDD.min.toInt 
} 


var count = 0 
// Count the number of positions in the minhash signature which are equal. 
for(k <- 0 to numHashes-1) 
{ 
    if(signature1(k) == signature2(k)) 
    count = count + 1 
} 

: Bu kod yeniden eğer

İkincisi, bazı zamandan tasarruf edebilirsiniz. Bununla birlikte, bu hesaplama zamanlarında büyük bir artış sağlayacağından emin değilim.

Bir başka öneri Ben, ilk yaklaşım değiştirme setleri özelliğini kullanmaktır ilk yaklaşım hala çok daha hızlı olarak çıkıyor varsayarak: bununla

val colHashed1_dist = colHashed1.distinct 
val colHashed2_dist = colHashed2.distinct 
val intersect_cnt = colHashed1_dist.intersection(colHashed2_dist).distinct.count 

val jSimilarity = intersect_cnt/(colHashed1_dist.count + colHashed2_dist.count - intersect_cnt).toDouble 

yerine alma birliği kesişmenin değerini yeniden kullanabilirsiniz.

Answer 3

Aslında, LSH uygulamasında, belgelerinizin her biri için minHash'i yalnızca bir kez hesaplar ve daha sonra, her bir olası belge çifti için iki tane minyatür karşılaştırırsınız. Ve önemsiz yaklaşım durumunda, mümkün olan her çift belge için belgelerin tam karşılaştırmasını gerçekleştirecektiniz. Hangi kabaca N^2/2 karşılaştırma sayısıdır. Bu nedenle, yeterli sayıda belge için minHashes hesaplama ekstra maliyet ihmal edilebilir.

Aslında önemsiz yaklaşımının performansını karşılaştırmak gerekir:

val jSimilarity = colHashed1.intersection(colHashed2).distinct.count/(colHashed1.union(colHashed2).distinct.count.toDouble) 

ve Jaccard mesafe hesaplama performansı (Kodunuzdaki son satır):

var count = 0 
// Count the number of positions in the minhash signature which are equal. 
for(k <- 0 to numHashes-1) 
{ 
    if(signature1(k) == signature2(k)) 
    count = count + 1 
} 
val jSimilarity = count/numHashes.toDouble