LSH

Kontynuując poprzedni wpis… Wiemy już, że dokumenty mogą być reprezentowane przez sygnatury, które umożliwiają obliczenie odległości Jaccarda pomiędzy dowolną parą.
Nadal jednak pozostaje pewien problem. Jeśli chcemy znaleźć podobne do siebie dokumenty, to musimy porównać każdy z każdym, co w przypadku dużych zbiorów danych jest niewykonalne w sensownym czasie. Większość czasu będzie zmarnowana na obliczanie podobieństwa pomiędzy dokumentami, które prawie w ogóle nie są do siebie podobne (a przynajmniej poniżej tego co nas interesuje).
Idea LSH polega na tym, żeby iterować po całej kolekcji tylko raz i „wrzucać” każdy dokument do odpowiedniego koszyka z założeniem, że podobne elementy powinny trafić do tego samego koszyka. Wtedy, po skończeniu, w każdym koszyku powinny znaleźć się tylko elementy, które są do siebie podobne.
Za przydział do odpowiedniego koszyka mogłaby odpowiadać cała sygnatura dokumentu, jednak w celu zwiększenia prawdopodobieństwa, że podobne dokumenty zostaną kandydatami, tworzy się (zazwyczaj ok. 20) pasm (ang. „bands”). Dzięki temu sygnatury nie muszą zgadzać się w całości, aby dwa dokumenty zostały uznane za podobne.

Implementacja:

List<Dictionary<uint, List<int>>> buckets = new List<Dictionary<uint, List<int>>>();

Parallel.For(0, (_numHashFunctions / _numRowPerBand), (i) =>
{
    Dictionary<uint, List<int>> bucket = new Dictionary<uint, List<int>>();
    foreach (var userId in signatureMatrix.Keys)
    {
        uint hash = 0;
        for (int j = 0; j < _numRowPerBand; j++)
        {
            hash = unchecked(hash * 1174247 + signatureMatrix[userId][_numRowPerBand * i + j]);
        }

        if (!bucket.ContainsKey(hash))
        {
            bucket[hash] = new List<int>();
        }
        bucket[hash].Add(userId);
    }
    lock (sync)
    {
        buckets.Add(bucket);
    }
});

 
Kod wykonuje się równolegle dla każdego pasma.

Po przejściu przez całą kolekcję w buckets znajdują się już kandydaci – dokumenty podobne do siebie.
Pozostaje jedynie je połączyć i zbudować wynikową kolekcję.

Dictionary<int, HashSet<int>> NN = new Dictionary<int, HashSet<int>>();

foreach (var userId in users.Keys)
{//initialize
    NN[userId] = new HashSet<int>();
}

foreach (var bucket in buckets)
{
    foreach (var hash in bucket)
    {
        if (hash.Value.Count > 1)
        {
            foreach (var userId in hash.Value)
            {
                NN[userId].UnionWith(hash.Value);
            }
        }
    }
}

Podsumowanie.
Jeśli posiadamy dużą kolekcję dokumentów i chcemy w tej kolekcji znaleźć te, które są podobne do siebie to:
MinHash pozwala na zmniejszenie rozmiaru przechowywanych dokumentów z zachowaniem możliwości porównania odległości pomiędzy dokumentami.
LSH pozwala na obejście problemu porównywania każdego dokumentu z każdym, Przejście po kolekcji trwa wolniej ale za to robimy to tylko raz i pozbywamy się złożoności N^2.

Program.cs

2 thoughts on “LSH

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *