andrewclegg / sketchy Goto Github PK

'''
This module implements the Locality Sensitive Hashing index
with MinHash (MinHash LSH) and Weighted MinHash (Weighted MinHash LSH)
Both indexes supports query with Jaccard similarity threshold.

Reference: Chapter 3, Mining of Massive Datasets
(http://www.mmds.org/)
'''
from collections import defaultdict
import math


_integration_precision = 0.001
def _integration(f, a, b):
    p = _integration_precision
    area = 0.0
    x = a
    while x < b:
        area += f(x+0.5*p)*p
        x += p
    return area, None

try:
    from scipy.integrate import quad as integrate
except ImportError:
    # For when no scipy installed
    integrate = _integration


def _false_positive_probability(threshold, b, r):
    _probability = lambda s : 1 - (1 - s**float(r))**float(b)
    a, err = integrate(_probability, 0.0, threshold)
    return a


def _false_negative_probability(threshold, b, r):
    _probability = lambda s : 1 - (1 - (1 - s**float(r))**float(b))
    a, err = integrate(_probability, threshold, 1.0)
    return a


def _optimal_param(threshold, num_perm, false_positive_weight,
        false_negative_weight):
    '''
    Compute the optimal `MinHashLSH` parameter that minimizes the weighted sum
    of probabilities of false positive and false negative.
    '''
    min_error = float("inf")
    opt = (0, 0)
    for b in range(1, num_perm+1):
        max_r = int(num_perm / b)
        for r in range(1, max_r+1):
            fp = _false_positive_probability(threshold, b, r)
            fn = _false_negative_probability(threshold, b, r)
            error = fp*false_positive_weight + fn*false_negative_weight
            if error < min_error:
                min_error = error
                opt = (b, r)
    return opt


class SketchLSH(object):
    '''
    The sketch LSH
    '''

    def __init__(self, threshold=0.9, num_perm=128, weights=(0.5,0.5)):
        if threshold > 1.0 or threshold < -1.0:
            raise ValueError("threshold must be in [-1.0, 1.0]")
        if num_perm < 2:
            raise ValueError("Too few permutation functions")
        if any(w < 0.0 or w > 1.0 for w in weights):
            raise ValueError("Weight must be in [0.0, 1.0]")
        if sum(weights) != 1.0:
            raise ValueError("Weights must sum to 1.0")

        # sketch lsh(d1, d2, p1, p2)
        # p1 = (180-d1)/180 where d1 and d2 is in degree
        threshold_degree = math.acos(threshold)/math.pi*180
        prob_threshold = (180-threshold_degree)/180
        threshold = prob_threshold

        self.threshold = threshold
        self.h = num_perm
        false_positive_weight, false_negative_weight = weights
        self.b, self.r = _optimal_param(threshold, num_perm,
                false_positive_weight, false_negative_weight)
        self.hashtables = [defaultdict(list) for _ in range(self.b)]
        self.hashranges = [(i*self.r, (i+1)*self.r) for i in range(self.b)]
        self.keys = dict()

    def split(self, sketch):
        if len(sketch) != self.h:
            raise ValueError("Expecting minhash with length %d, got %d"
                    % (self.h, len(minhash)))
        band_values = [sketch[start:end] for start, end in self.hashranges]
        return band_values

from sketchy import sparse_random_projection
import sys

def bitfield(n, size):
    b = [str(n >> i & 1) for i in range(size-1, -1, -1)]
    return ''.join(b)

def test_vector():
    hash_size = 500
    sketch_lsh = SketchLSH(threshold=0.7, num_perm=hash_size)

    for line in sys.stdin:
        fields = line.split()
        uid = fields[0]
        vec = map(float, fields[1:])
        hash_val = sparse_random_projection(vec, hash_size, 100, 1013)
        bit_val = bitfield(hash_val, hash_size)
        band_val = sketch_lsh.split(bit_val)
        for index, value in enumerate(band_val):
            print '%s:%s\t%s' % (index, value, uid)