Calcul de similitude par MinHash

J'ai implémenté un exemple de calcul de similarité par MinHash.

Référence Jugement de similarité rapide et peu encombrant par b-Bit Min Hash

Selon le document ci-dessus, MurmurHash3 (python wrapper) pour le calcul du hachage. ) A été utilisé.

minhash.py


# -*- coding: utf-8


import mmh3


MIN_HASH_VALUE = 2 ** 128


def min_hash(words, seed):
    min_hash_word = None
    min_hash_value = MIN_HASH_VALUE

    for word in words:
        hash_ = mmh3.hash128(word, seed)
        if hash_ < min_hash_value:
            min_hash_word = word
            min_hash_value = hash_

    return min_hash_word


def get_score(s1, s2, k):
    """Get the similarity between s1 and s2 using min-hash algorithm

    k: the number of hash functions
    """
    num_match = 0

    for seed in xrange(k):
        if min_hash(s1, seed) == min_hash(s2, seed):
            num_match += 1

    return float(num_match) / k


def main():
    s1 = ['a', 'b']
    s2 = ['a']
    s3 = ['b']
    # a-z
    s4 = [chr(ascii) for ascii in xrange(97, 123)]

    k = 2 ** 10

    # Should be ~0.074
    print get_score(s1, s4, k)
    # Should be ~0.370
    print get_score(s2, s4, k)
    # Should be ~0.370
    print get_score(s3, s4, k)


if __name__ == '__main__':
    main()
[yamaneko]$ time python min_hash.py 
0.078125
0.046875
0.03125

real    0m0.112s
user    0m0.076s
sys     0m0.015s

Lorsque la valeur de k a été augmentée, la valeur a convergé, mais le temps de calcul a augmenté.

Ensuite, je veux implémenter B-bit Min Hash.

Recommended Posts

Calcul de similitude par MinHash
[Python] Calcul de la similarité d'image (coefficient de dés)
Calcul des indicateurs techniques par TA-Lib et pandas
Calcul numérique du fluide compressible par la méthode des volumes finis
Calcul de la similitude entre les phrases à l'aide de Word2Vec (version simplifiée)
Calcul de la matrice d'homographie par la méthode des moindres carrés (méthode DLT)
Visualisation des données par préfecture
[Calcul scientifique / technique par Python] Fonctionnement de base du tableau, numpy
À propos du calcul des coûts de MeCab
Comparaison de la vitesse de calcul en implémentant python mpmath (calcul de précision arbitraire) (Note)
Visualisation de la matrice créée par numpy
Calcul sans erreur avec le big.Float de Golang
Calcul de la fidélité des clients dans les séries chronologiques
Erreur divisée par 0 Traitement de ZeroDivisionError 2
Extension du dictionnaire python par argument
Calcul du vecteur normal par convolution
Erreur divisée par 0 Gestion de ZeroDivisionError
Jugement du if par la notation d'inclusion de liste
Résumé de l'implémentation de base par PyTorch
Train_test_split du montant de fonction détenu par dict
Calcul du courant dans le circuit électrique CC
Calcul du nombre d'associations de Klamer
Calcul de la classe auto-fabriquée et de la classe existante
Liste des packages installés par conda
Tracé de la droite de régression par tracé des résidus
10 sélections d'extraction de données par pandas.DataFrame.query
Comportement de python3 par le serveur de Sakura
Animation des géodonnées par geopandas
[Python] Calcul du coefficient kappa (k)
Amélioration de la vitesse grâce à l'auto-implémentation de numpy.random.multivariate_normal
Exemple de réécriture de code par ast.NodeTransformer
Calcul du coefficient de corrélation de rang de Spearman
Histoire d'approximation de puissance par Python
Projet Euler 9 Conservation des résultats des calculs
Calcul de similarité entre les épisodes précurseurs à l'aide de la chronologie en direct et du modèle de sujet
[Calcul scientifique / technique par Python] Ajustement par fonction non linéaire, équation d'état, scipy
[Calcul scientifique / technique par Python] Calcul du produit de la matrice par l'opérateur @, python3.5 ou supérieur, numpy
[Ingénierie de contrôle] Calcul des fonctions de transfert et des modèles d'espace d'états par Python