Similarité et Pondération

UFR de sociologie et d'informatique pour les sciences humaines

Programmation de Modèles Linguistiques (I) 2020-21

Carlos González et Gaël Lejeune


Modèle Vectoriel Résumé

Du corpus à la matrice en passant par la matrice

  • Des documents ( $I$ lignes de la matrice )
  • Des descripteurs ( $J$ colonnes )
  • Une valeur brute (effectif, fréquence) avec ou sans foction de pondération
  • Une valeur affectée ( $A_{i, j}$ )
  • Un algorithme de calcul de distance (ou de similarité)
  • Une nouvelle matrice, carrée: $M_{k, l}$ est la distance entre le document $k$ et le document $l$

Ensemble de documents

document1 : "un trou noir empêche toute forme de matière ou de rayonnement de s' en échapper"

document2 : "le trou noir est un cocktail à base d' alcool généralement servi dans un shooter"

document3 : "les pays avérés du trou noir de le immobilier sont le Japon et l' Allemagne"

document4 : "un trou de ver relierait deux feuillets distincts un trou noir et un trou blanc"

document5 : "placer une saucisse cocktail au bord de une bande de pâte enrouler la pâte autour de la saucisse"

In [1]:
document1 = "un trou noir empêche toute forme de matière ou de rayonnement de s' en échapper"

document2 = "le trou noir est un cocktail à base d' alcool généralement servi dans un shooter"

document3 = "les pays avérés du trou noir de le immobilier sont le Japon et l' Allemagne"

document4 = "un trou de ver relierait deux feuillets distincts un trou noir et un trou blanc"

document5 = "placer une saucisse cocktail au bord de une bande de pâte enrouler la pâte autour de la saucisse"

documents = {"document1": document1, "document2": document2, "document3": document3, "document4": document4, "document5": document5}
In [2]:
documents["document4"]
Out[2]:
'un trou de ver relierait deux feuillets distincts un trou noir et un trou blanc'

Obtention du vocabulaire et creation d'index

In [3]:
def creer_index():

    index = {}

    for nom, texte in documents.items():
        for terme in texte.split():
            if terme not in index:
                index[terme] = set()
            index[terme].add(nom)

    index = {terme:sorted(list(noms)) for terme, noms in index.items()}        
    return index

index = creer_index()
for terme, noms in list(index.items())[:]:
    print(terme,noms)
        
un ['document1', 'document2', 'document4']
trou ['document1', 'document2', 'document3', 'document4']
noir ['document1', 'document2', 'document3', 'document4']
empêche ['document1']
toute ['document1']
forme ['document1']
de ['document1', 'document3', 'document4', 'document5']
matière ['document1']
ou ['document1']
rayonnement ['document1']
s' ['document1']
en ['document1']
échapper ['document1']
le ['document2', 'document3']
est ['document2']
cocktail ['document2', 'document5']
à ['document2']
base ['document2']
d' ['document2']
alcool ['document2']
généralement ['document2']
servi ['document2']
dans ['document2']
shooter ['document2']
les ['document3']
pays ['document3']
avérés ['document3']
du ['document3']
immobilier ['document3']
sont ['document3']
Japon ['document3']
et ['document3', 'document4']
l' ['document3']
Allemagne ['document3']
ver ['document4']
relierait ['document4']
deux ['document4']
feuillets ['document4']
distincts ['document4']
blanc ['document4']
placer ['document5']
une ['document5']
saucisse ['document5']
au ['document5']
bord ['document5']
bande ['document5']
pâte ['document5']
enrouler ['document5']
la ['document5']
autour ['document5']

Création de la "matrice" documents-termes

documents/termes $terme_1$ $terme_2$ $terme_3$ $\cdots$ $terme_J$
$document_1$ $A_{1,1}$ $A_{1,2}$ $A_{1,3}$ $\cdots$ $A_{1, J}$
$document_2$ $A_{2,1}$ $\ddots$ $\vdots$
$document_3$ $A_{3,1}$ $\ddots$ $\vdots$
$\vdots$ $\vdots$ $\ddots$ $\vdots$
$document_I$ $A_{I,1}$ $\cdots$ $\cdots$ $\cdots$ $A_{I,J}$
In [4]:
def creer_index_inverse():

    index_inverse = {}

    for nom, texte in documents.items():
        index_inverse[nom] = dict()
        for terme in texte.split():
            if terme not in index_inverse[nom]:
                index_inverse[nom][terme] = 1
            else:
                index_inverse[nom][terme] += 1

    return index_inverse

index_inverse = creer_index_inverse()
print(index_inverse)
{'document1': {'un': 1, 'trou': 1, 'noir': 1, 'empêche': 1, 'toute': 1, 'forme': 1, 'de': 3, 'matière': 1, 'ou': 1, 'rayonnement': 1, "s'": 1, 'en': 1, 'échapper': 1}, 'document2': {'le': 1, 'trou': 1, 'noir': 1, 'est': 1, 'un': 2, 'cocktail': 1, 'à': 1, 'base': 1, "d'": 1, 'alcool': 1, 'généralement': 1, 'servi': 1, 'dans': 1, 'shooter': 1}, 'document3': {'les': 1, 'pays': 1, 'avérés': 1, 'du': 1, 'trou': 1, 'noir': 1, 'de': 1, 'le': 2, 'immobilier': 1, 'sont': 1, 'Japon': 1, 'et': 1, "l'": 1, 'Allemagne': 1}, 'document4': {'un': 3, 'trou': 3, 'de': 1, 'ver': 1, 'relierait': 1, 'deux': 1, 'feuillets': 1, 'distincts': 1, 'noir': 1, 'et': 1, 'blanc': 1}, 'document5': {'placer': 1, 'une': 2, 'saucisse': 2, 'cocktail': 1, 'au': 1, 'bord': 1, 'de': 3, 'bande': 1, 'pâte': 2, 'enrouler': 1, 'la': 2, 'autour': 1}}

Requêter le corpus

In [5]:
def requeter_documets(requete, index):
    documents_trouves = list()
    requete_mots = requete.split() # découper la requête en mots
    
    # chercher pour chaque mot les documents où il apparaît
    for mot in requete_mots: 
        if mot in index:
            for document in index[mot]:
                if document not in documents_trouves:
                    documents_trouves.append(document)

    return documents_trouves


requete = "matière et le trou noir"
documents_trouves = requeter_documets(requete, index)
print(documents_trouves)
['document1', 'document3', 'document4', 'document2']

Similarité de Jaccard

$ J(A,B) = { {|A \cap B| } \over |A \cup B| }$

$|A \cap B|$ : Taille de l'intersection des documents considérés

$|A \cup B|$ : Taille de l'union des documents considérés

  • ### Marice de similarité (Jaccard) pour l'ensemble de documents
In [6]:
def creer_matrice_jaccard(index_inverse):

    matrice_sim = dict()
    
    for nom, termes_document in index_inverse.items():
        matrice_sim[nom] = dict()
        for nom_int, termes_document_int in index_inverse.items():
            #Taille de l'intersection des documents considérés 
            intersection = len(set(termes_document).intersection(set(termes_document_int)))
            #Taille de l'union des documents considérés 
            union = len(set(termes_document).union(set(termes_document_int)))
            matrice_sim[nom][nom_int] = intersection/union

    noms = matrice_sim.keys()
    print("JACCARD\t\t"+"\t".join(noms))
    for nom in noms:
        print(nom, end="\t")
        for nom_int in noms:
            print("{:.3f}".format(matrice_sim[nom][nom_int]), end="\t\t")
        print("")
    return matrice_sim

matrice_sim = creer_matrice_jaccard(index_inverse)
print("*"*40)
print(matrice_sim)
JACCARD		document1	document2	document3	document4	document5
document1	1.000		0.125		0.125		0.200		0.042		
document2	0.125		1.000		0.120		0.136		0.040		
document3	0.125		0.120		1.000		0.190		0.040		
document4	0.200		0.136		0.190		1.000		0.045		
document5	0.042		0.040		0.040		0.045		1.000		
****************************************
{'document1': {'document1': 1.0, 'document2': 0.125, 'document3': 0.125, 'document4': 0.2, 'document5': 0.041666666666666664}, 'document2': {'document1': 0.125, 'document2': 1.0, 'document3': 0.12, 'document4': 0.13636363636363635, 'document5': 0.04}, 'document3': {'document1': 0.125, 'document2': 0.12, 'document3': 1.0, 'document4': 0.19047619047619047, 'document5': 0.04}, 'document4': {'document1': 0.2, 'document2': 0.13636363636363635, 'document3': 0.19047619047619047, 'document4': 1.0, 'document5': 0.045454545454545456}, 'document5': {'document1': 0.041666666666666664, 'document2': 0.04, 'document3': 0.04, 'document4': 0.045454545454545456, 'document5': 1.0}}
  • ### Pondération des resultats avec la similarité de Jaccard
In [7]:
def calculer_ponderation_jaccard(requete, index_inverse, documents_trouves):
    
    ponderations = dict()
    requete_mots = requete.split()
    
    for document in documents_trouves:
        #Termes du document trouvé
        termes_document = index_inverse[document]
        #Taille de l'intersection des documents considérés 
        intersection = len(set(termes_document).intersection(set(requete_mots)))
        #Taille de l'union des documents considérés 
        union = len(set(termes_document).union(set(requete_mots)))
        ponderations[document] = intersection/union
    
    return ponderations
            
requete = "matière et le trou noir"
documents_trouves = requeter_documets(requete, index)
print(documents_trouves)
ponderations_jaccard = calculer_ponderation_jaccard(requete, index_inverse, documents_trouves)
print(ponderations_jaccard)
['document1', 'document3', 'document4', 'document2']
{'document1': 0.2, 'document3': 0.26666666666666666, 'document4': 0.23076923076923078, 'document2': 0.1875}

Similarité cosinus

Permet de calculer la similarité entre deux documents ($A$ et $B$) à $n$ termes en déterminant le cosinus de l'angle entre eux.

$sim(A,B) = \cos(\mathbf{A},\mathbf{B}) = \frac{\mathbf{A} \cdot \mathbf{B}}{||\mathbf{A}|| \cdot ||\mathbf{B}||} ; [-1,+1]$

$\mathbf{A} \cdot \mathbf{B} = \sum_{i=1}^{n} A_iB_i $ ; produit scalaire entre $\mathbf{A}$ et $\mathbf{B}$

$||\mathbf{A}|| = \sqrt{\sum{_{i=1}^{n}}A_i^2}$ ; norme de $\mathbf{A}$

$||\mathbf{B}|| = \sqrt{\sum{_{i=1}^{n}}B_i^2}$ ; norme de $\mathbf{B}$


$A$ = le chat noir mignon

$B$ = le chien blanc mignon

documents/termes le chat noir chien blanc mignon
$A$ 1 1 1 0 0 1
$B$ 1 0 0 1 1 1

$n = 6 $

$\mathbf{A} = (1,1,1,0,0,1)$

$\mathbf{B} = (1,0,0,1,1,1)$

$\mathbf{A} \cdot \mathbf{B} = \sum_{i=1}^{n} A_iB_i = (1\times1)+(1\times0)+(1\times0)+(0\times1)+(0\times1)+(1\times1) = 2$

$||\mathbf{A}|| = \sqrt{\sum{_{i=1}^{n}}A_i^2} = \sqrt{1^2+1^2+1^2+0^2+0^2+1^2} = \sqrt{4} = 2$

$||\mathbf{B}|| = \sqrt{\sum{_{i=1}^{n}}B_i^2} = \sqrt{1^2+0^2+0^2+1^2+1^2+1^2} = \sqrt{4} = 2$

$sim(A,B) = \cos(\mathbf{A},\mathbf{B}) = \frac{\mathbf{A} \cdot \mathbf{B}}{||\mathbf{A}|| \cdot ||\mathbf{B}||} = \frac{2}{2 \times 2} = \frac{2}{4} = \frac{1}{2} = 0.5$

  • ### Calculer la similarité cosinus entre deux documents
In [8]:
import math
def calculer_sim_cosinus(docA, docB):
    termes_communs = list(set(docA).intersection(set(docB)))
    
    #produit scalaire
    AB = 0
    for terme_commun in termes_communs:
        AB += docA[terme_commun] * docB[terme_commun]

    #norme A
    A_norme = 0
    for terme, freq in docA.items():
        A_norme += pow(freq, 2)
    A_norme = math.sqrt(A_norme)

    #norme B
    B_norme = 0
    for terme, freq in docB.items():
        B_norme += pow(freq, 2)
    B_norme = math.sqrt(B_norme)
    
    sim_cosinus = AB / (A_norme * B_norme)
    
    return sim_cosinus

r1 = calculer_sim_cosinus(index_inverse["document1"], index_inverse["document2"])
print(r1)
r2 = calculer_sim_cosinus(index_inverse["document1"], index_inverse["document5"])
print(r2)
0.21170244960998524
0.3471825374147068
  • ### Marice de similarité (Cosinus) pour l'ensemble de documents
In [9]:
import itertools
def creer_matrice_cosinus(index_inverse):

    matrice_sim = dict()
    paires_docs = list(itertools.permutations(index_inverse.keys(), 2))    
    
    for docA, docB in paires_docs:
        if docA not in matrice_sim:
            matrice_sim[docA] = dict()
        a=calculer_sim_cosinus(index_inverse[docA], index_inverse[docB])
        matrice_sim[docA][docB] = calculer_sim_cosinus(index_inverse[docA], index_inverse[docB])

    noms = matrice_sim.keys()
    print("COSINUS\t\t"+"\t".join(noms))
    for nom in noms:
        print(nom, end="\t")
        for nom_int in noms:
            if nom_int not in matrice_sim[nom]:
                print("1.000", end="\t\t")    
            else:
             print("{:.3f}".format(matrice_sim[nom][nom_int]), end="\t\t")
        print("")
    return matrice_sim

matrice_sim = creer_matrice_cosinus(index_inverse)
print("*"*40)
print(matrice_sim)
COSINUS		document1	document2	document3	document4	document5
document1	1.000		0.212		0.265		0.420		0.347		
document2	0.212		1.000		0.235		0.467		0.043		
document3	0.265		0.235		1.000		0.280		0.129		
document4	0.420		0.467		0.280		1.000		0.102		
document5	0.347		0.043		0.129		0.102		1.000		
****************************************
{'document1': {'document2': 0.21170244960998524, 'document3': 0.26462806201248157, 'document4': 0.41996052556580804, 'document5': 0.3471825374147068}, 'document2': {'document1': 0.21170244960998524, 'document3': 0.23529411764705882, 'document4': 0.46676002800933664, 'document5': 0.042874646285627205}, 'document3': {'document1': 0.26462806201248157, 'document2': 0.23529411764705882, 'document4': 0.280056016805602, 'document5': 0.12862393885688161}, 'document4': {'document1': 0.41996052556580804, 'document2': 0.46676002800933664, 'document3': 0.280056016805602, 'document5': 0.10206207261596574}, 'document5': {'document1': 0.3471825374147068, 'document2': 0.042874646285627205, 'document3': 0.12862393885688161, 'document4': 0.10206207261596574}}
  • ### Pondération des resultats avec la similarité cosinus
In [10]:
def indexer_requete(requete):
    
    index_requete = dict()
    
    for terme in requete.split():
        if terme not in index_requete:
            index_requete[terme] = 1
        else:
            index_requete[terme] += 1
            
    return index_requete

def calculer_ponderation_cosinus(requete, index_inverse, documents_trouves):
    
    ponderations = dict()
    index_requete = indexer_requete(requete)
    
    for docA in documents_trouves:
    
        ponderations[docA] = calculer_sim_cosinus(index_inverse[docA], index_requete)
    
    return ponderations
            
requete = "matière et le trou le noir"
documents_trouves = requeter_documets(requete, index)
print(documents_trouves)
ponderations_cosinus = calculer_ponderation_cosinus(requete, index_inverse, documents_trouves)
print(ponderations_cosinus)
['document1', 'document3', 'document4', 'document2']
{'document1': 0.23145502494313785, 'document3': 0.6002450479987809, 'document4': 0.3402069087198858, 'document2': 0.34299717028501764}

Représenter en termes de TF-IDF

À partir de notre exemple de Similarité cosinus :

$A$ = le chat noir mignon

$B$ = le chien blanc mingon

alldocs = {"A": {"le": 1, "chat": 1, "noir": 1, "mignon": 1},
           "B": {"le": 1, "chien": 1, "blanc": 1, "mignon": 1}}

allvoc = {"le": 2 , "chat": 1, "noir": 1, "mignon": 2, "chien": 1, "blanc":1}

Term Frequency (TF) : le taux d'apparition d'un mot dans un document. Il est toujours dans l'interval de 0 à 1 (inclus). Cette mesure présente si ce mot est fréquent (donc important) par rapport aux autres mots du même document.

$TF_{(terme_m, document_d)}=$ (nombre d'occurrence du $terme_m$ dans $document_d$) / (nombre total de toutes les occurrences de tous les termes dans $document_d$)

TF = {"A": {"le": 0.25, "chat": 0.25, "noir": 0.25, "mignon": 0.25},
           "B": {"le": 0.25, "chien": 0.25, "blanc": 0.25, "mignon": 0.25}}

Inverse Document Frequency (IDF) : Une mesure globale pour un terme. Cette mesure est dans l'interval de 0 à >1. Elle représente l'importance d'un mot pour marquer un document dans la base. Si un mot n'est présent dans qu'un seul document, ce mot est important pour retrouver le document. En revanche, si un mot est présent dans tous les documents de la base, il n'est pas significatif et son score IDF sera faible.

$IDF{(terme_m)} = log_{10}( $ (nombre total de documents)/(nombre de documents où $terme_m$ est présent) $)$

Total de documents : 2

IDF = {"le": 0.0 , "chat": 0.301, "noir": 0.301, "mignon": 0.0, "chien": 0.301, "blanc": 0.301}
In [11]:
print(math.log10(2/1))
print(math.log10(2/2))
0.3010299956639812
0.0

Finalement,

TF = {"A": {"le": 0.25, "chat": 0.25, "noir": 0.25, "mignon": 0.25},
      "B": {"le": 0.25, "chien": 0.25, "blanc": 0.25, "mignon": 0.25}}

IDF = {"le": 0.0 , "chat": 0.301, "noir": 0.301, "mignon": 0.0, "chien": 0.301, "blanc": 0.301}

TF-IDF = $TF \cdot IDF$

alldocs_TFIDF = {"A": {"le": 0.25*0.0, "chat": 0.25*0.301, "noir": 0.25*0.301, "mignon": 0.25*0.0},
                 "B": {"le": 0.25*0.0, "chien": 0.25*0.301, "blanc": 0.25*0.301, "mignon": 0.25*0.0}}

alldocs_TFIDF = {"A": {"le": 0.0, "chat": 0.075, "noir": 0.075, "mignon": 0.0},
                 "B": {"le": 0.0, "chien": 0.075, "blanc": 0.075, "mignon": 0.0}}

$A$ = le chat noir mignon

$B$ = le chien blanc mingon

documents/termes le chat noir chien blanc mignon
$A$ 0 0.075 0.075 0 0 0
$B$ 0 0 0 0.075 0.075 0
  • ### Calculer TF-IDF pour l'ensemble de documents
In [12]:
import math
import copy

def calculer_tfidf(index_inverse, index):

    tfidf_index_inverse = copy.deepcopy(index_inverse)

    # Calculer TF
    for nom, termes_document in index_inverse.items():
        totale_freqs = 0
        for _, freq in termes_document.items():
             totale_freqs += freq
        for terme in tfidf_index_inverse[nom].keys():
            tfidf_index_inverse[nom][terme] /= totale_freqs

    # Calculer IDF        
    totale_docs = len(index_inverse.keys())
    idf_index = copy.deepcopy(index)
    
    for terme, noms in idf_index.items():
        terme_rep = len(noms)
        idf_val = math.log10(totale_docs / terme_rep)
        idf_index[terme] = idf_val


    # Calculer TFIDF
    
    for nom, termes_document in tfidf_index_inverse.items():
        for terme in termes_document.keys():
            tfidf_index_inverse[nom][terme] *= idf_index[terme]
        
    return tfidf_index_inverse, idf_index

    
tfidf_index_inverse, idf_index = calculer_tfidf(index_inverse, index)


print(tfidf_index_inverse["document1"])
{'un': 0.014789916641090426, 'trou': 0.006460667533870428, 'noir': 0.006460667533870428, 'empêche': 0.04659800028906792, 'toute': 0.04659800028906792, 'forme': 0.04659800028906792, 'de': 0.019382002601611284, 'matière': 0.04659800028906792, 'ou': 0.04659800028906792, 'rayonnement': 0.04659800028906792, "s'": 0.04659800028906792, 'en': 0.04659800028906792, 'échapper': 0.04659800028906792}
In [13]:
print(index_inverse["document1"])
{'un': 1, 'trou': 1, 'noir': 1, 'empêche': 1, 'toute': 1, 'forme': 1, 'de': 3, 'matière': 1, 'ou': 1, 'rayonnement': 1, "s'": 1, 'en': 1, 'échapper': 1}
  • ### Marices de similarité (Jaccard et Cosinus) pour l'ensemble de documents
In [14]:
tfidf_matrice_jaccard = creer_matrice_jaccard(tfidf_index_inverse)

tfidf_matrice_cosinus = creer_matrice_cosinus(tfidf_index_inverse)
JACCARD		document1	document2	document3	document4	document5
document1	1.000		0.125		0.125		0.200		0.042		
document2	0.125		1.000		0.120		0.136		0.040		
document3	0.125		0.120		1.000		0.190		0.040		
document4	0.200		0.136		0.190		1.000		0.045		
document5	0.042		0.040		0.040		0.045		1.000		
COSINUS		document1	document2	document3	document4	document5
document1	1.000		0.025		0.010		0.052		0.012		
document2	0.025		1.000		0.066		0.079		0.022		
document3	0.010		0.066		1.000		0.047		0.004		
document4	0.052		0.079		0.047		1.000		0.004		
document5	0.012		0.022		0.004		0.004		1.000		
  • ### Pondération des resultats avec la similarité cosinus et TFIDF
In [15]:
def calculer_ponderation_cosinus_tfidf(requete, index_inverse, idf_index, documents_trouves):
    
    ponderations = dict()
    index_requete = indexer_requete(requete)
    
    for terme in index_requete.keys():
        index_requete[terme] *= idf_index[terme]
    
    for docA in documents_trouves:
        
        ponderations[docA] = calculer_sim_cosinus(index_inverse[docA], index_requete)
    
    return ponderations
   
    
    
requete = "matière et le trou noir"
documents_trouves = requeter_documets(requete, index)
print(documents_trouves)
print("....")

ponderations_cosinus = calculer_ponderation_cosinus(requete, index_inverse, documents_trouves)
print(ponderations_cosinus)
print("....")
ponderations_cosinus_tfidf = calculer_ponderation_cosinus_tfidf(requete, tfidf_index_inverse, idf_index, documents_trouves)
print(ponderations_cosinus_tfidf)
['document1', 'document3', 'document4', 'document2']
....
{'document1': 0.29277002188455997, 'document3': 0.5423261445466404, 'document4': 0.4303314829119352, 'document2': 0.32539568672798425}
....
{'document1': 0.2620224260154057, 'document3': 0.23818191176823345, 'document4': 0.11318687784798852, 'document2': 0.08789015753958132}