ABONAMENTE VIDEO REDACȚIA
RO
EN
×
▼ LISTĂ EDIȚII ▼
Numărul 37
Abonament PDF

Descoperirea entităților similare în modele BigData

Ovidiu Petridean
Senior Software Developer @ SDL Research
PROGRAMARE


Scopul articolului este prezentarea unei modalități de a descoperi entităţi similare în modele BigData.Vom expune în cele ce urmează abordarea MapReduce a unui algoritm utilizat pentru a găsi texte similare într-un corp foarte mare de date. Chiar dacă exemplele prezentate se concentrează pe găsirea de texte similare, acest algoritm poate fi folosit pentru a găsi orice fel de entităţi asemănătoare care pot fi descrise printr-un set de caracteristici.

Problema

Cum găsim propoziţii similare într-un set foarte mare de date (Peta-bytes de date). O problemă foarte importantă care apare atunci când încercăm să găsim elemente similare de orice fel este ca probabilitatea prezenței unui număr prea mare de perechi să îngreuneze procesul de analiză și identificare a relației de similaritate dintre ele. Chiar dacă timpul în care se determină dacă o pereche este similară sau nu este foarte scurt, este nerealist să credem că putem să le comparăm pe toate.

Soluția

Examinarea elementelor similare este o problemă fundamentală de data-mining. În cele ce urmează vom arăta cum problema găsirii propoziţiilor similare se poate transforma într-o problemă de identificare a elementelor similare.

Noţiuni Generale

Data mining O definiţie destul de populară spune că "data mining" reprezintă procesul de descoperire a modelelor pentru date. Un model poate totuşi să reprezinte mai multe lucruri. Se disting astfel următoarele: modelare statistică, învăţare automată, sumarizare (e.g PageRank de la Google), extragerea caracteristicilor.

Funcții de dispersie

O funcție de dispersie h primeste o cheie ca argument și produce un număr de "compartiment".Numărul de compartiment este un număr întreg, în mod normal, în intervalul 0 până la B - 1, unde B este numărul de compartimente.

Elemente similare

Pentru a defini elementele similare vom utiliza Similaritatea Jaccard. Similaritatea Jaccard a seturilor S și T este

\|S ∩ T \|/\|S ∪ T \|, ceea ce reprezintă raportul dintre numărul de elemente comune și numărul total de elemente pe care cele două seturi le au.

Să prezentăm un exemplu. Notăm similaritatea Jaccard a seturilor S și T cu SIM(S, T ).

Să presupunem că există două seturi S și T. Intersecția celor două seturi este formată din 3 elemente, iar în total cele două au 8 elemente. Astfel SIM(S, T ) = 3/8.

Similaritatea documentelor (propoziţiilor) O clasă importantă de probleme pe care similaritatea Jaccard le implică este aceea a găsirii documentelor sau a propozițiilor similare într-un corp de date foarte mare. Printre aplicaţiile cele mai cunoscute se numără: Plagiatul, Paginile Web "în oglindă" sau Articole care provin din aceeaşi sursă.

Algoritmul pentru găsirea elementelor similare

Algoritmul prezentat are trei pași principali: "decuparea", "minhashing" și "dispersie sensibilă la localizare". Pentru prezentarea algoritmului vom utiliza o aplicaţie practică și anume aceea a găsirii propoziţiilor similare într-un set foarte mare de date.

1.Decuparea Documentelor (Propoziţiilor)

Cel mai eficace mod de a reprezenta documentele ca seturi, pentru a putea identifica documente similare este să construim din fiecare document un set de succesiuni de caractere care apar în ele. Utilizarea de decupări formate din caractere este o abordare bună, dar cu toate acestea în cazul nostru este mult mai eficient să folosim decupări formate din cuvinte.

Dispersia decupărilor

În loc să utilizăm cuvintele ca decupări, alegem o funcţie de dispersie care mapează aceste cuvinte generând un număr de compartimente. Fiecare compartiment va fi tratat în continuare ca o decupare.

Reprezentări care pastrează similaritatea seturilor

Seturile formate din decupări sunt foarte mari. Chiar dacă am reuși să le dispersăm folosind doar 4 bytes pentru fiecare, spaţiul necesar pentru a le stoca este de patru ori mai mare decât spaţiul ocupat de documentul iniţial.

Scopul pe care îl urmărim este să înlocuim seturile mari cu nişte reprezentări denumite "semnături". Proprietatea importantă pe care acestea trebuie să o aibă este aceea că trebuie să putem estima similaritatea Jaccard a două seturi doar prin compararea semnăturilor acestora.

Reprezentarea matricială a seturilor

Pentru a avea o imagine mai bună a colecțiilor de seturi este util să ne uităm la ceea ce se numeşte matricea caracteristicilor. Coloanele matricii corespund seturilor, iar liniile corespund elementelor setului universal din care elementele fiecărui set sunt extrase.

Fiecare din exemplele următoare tratează problema similarităţii a două propoziţii, dar evident eficienţa algoritmului se vede atunci când discutăm despre un corp foarte mare de date. Noi folosim algoritmul pentru a găsi similarităţi in peta-bytes de date.

Să presupunem că avem următoarele două propoziții:

S1: "I enjoyed my stay during summer at hotel California"

S2: "I enjoyed my stay during winter at hotel Napoca"

De aici rezultă următoarele două seturi:

S1 = {i, enjoyed, my, stay, during, summer, at, hotel, california}

S2 = {i, enjoyed, my, stay, during, winter, at, hotel, napoca}

Este important de reținut probabilitatea ca matricea de caracteristici să nu fie modul în care datele sunt stocate, dar că oferă un mod util de a vizualiza datele.

În exemplul precedent putem observa că similaritatea celor două seturi poate fi descrisă ca numărul de linii în care care cele două seturi au elemente identice. Astfel putem deduce că similaritatea este 7/11 adică 0.63.

După cum menționam mai sus, pentru stocarea acestor matrici ar fi nevoie de foarte mult spaţiu, astfel că introducem următoarea tehnică numită "mihashing".

2.Minhashing

Semnăturile pe care dorim să le construim pentru seturi sunt compuse din rezultatele unui număr mare de calcule, fiecare dintre acestea fiind un minhash al matricii de caracteristici.

Pentru a determina un minhash pentru un set (reprezentat de o coloană din matricea de caracteristici) alegem o permutare a liniilor. Valoarea minhash este numărul liniei (în ordinea permutată) în care pe coloană întâlnim cifra 1.

Exemplu

Să presupunem că avem următoarea ordine a matricii precedente. Această permutare defineşte o funcţie minhash h care mapează seturile la linii.

Să calculăm valoarea funcției minhash pentru setul S1 conform funcției h. Prima coloană, cea care corespunde setului S1, are 0 pe prima linie, așa că mergem la linia a doua. Aici vedem de asemenea că întâlnim 0, așa că mergem la linia a treia, unde găsim cifra 1. Astfel putem să tragem concluzia ca h(S1) = "at". Utilizând același raționament tragem concluzia că h(S2) = "napoca".

Minhashing și Similaritatea Jaccard

Există o corelație remarcabilă între minhashing și similaritatea Jaccard a seturilor pe care s-a aplicat minhashing.

Probabilitatea ca o funcţie de minhash pentru o permutare aleatoare de linii să producă aceeaşi valoare pentru două seturi este egală cu similaritatea Jaccard a seturilor respective.

Semnăturile Minhash

Să presupunem din nou că avem o colecţie de seturi reprezentate prin matricea lor de caracteristici M. Pentru a reprezenta aceste seturi alegem aleator un număr n de permutări ale liniilor matricii M.

Un numar de 100 de permutări este de cele mai multe ori suficient. Să denumim funcțiile minhash determinate de aceste permutari h1,h2,...,hn. Din coloana care reprezintă setul S construim semnătura minhash pentru S ca fiind vectorul

[h1(S), h2(S), . . . , hn(S)].

Determinarea Semnăturilor Minhash

Nu este realizabil să permutăm explicit matrici de caracteristici foarte mari. Din fericire este posibil să simulăm efectul permutărilor aleatoare utilizând o funcţie de dispersie care mapează fiecare linie într-un compartiment.

Astfel în loc de n permutări aleatoare de linii vom alege n funcţii de dispersie h1,h2,...,hn pe care le vom aplica pe linii. Construim astfel matricea de semnături păstrând ordinea iniţială a fiecărei linii. Fie SIG(i, c) elementul din matricea de semnături care corespunde funcţiei de dispersie cu hi și coloanei c. Iniţial SIG(i, c) este ∞ oricare ar fi i și c.

Pentru fiecare rând r vom executa următorii pași:

  1. Calculăm h1(r), h2(r), . . . , hn(r)
  2. Pentru fiecare coloană c executăm următoarele:
    • Dacă c are 0 pe linia r, atunci nu se întîmplă nimic
    • Dacă c are 1 pe linia r atunci pentru fiecare i=1,2,...,n setăm SIG(i,c) ca fiind minimul dintre SIG(i,c) și hi(r)

Să calculăm semnăturile minhash pentru matricea de caracteristici anterioară.

Să alegem aleator două funcţii de dispersie

h(x) = x mod 11, g(x) = (2*x + 1) mod 11.

În cele ce urmează vom simula algoritmul de calculare a matricii de semnături.

Nu vom parcurge întregul proces ci doar paşii relevanți pentru acest exemplu.

Pentru că avem 11 linii, vom efecta 11 calcule ale funcțiilor h și g. Iniţializăm matricea cu ∞.

Pasul 1:

Dacă privim matricea iniţială vedem că pe prima linie atât S1 cât și S2 au valoarea 1, așa că vom calcula funcţiile h(x) și g(x), unde x este numărul de ordine al liniei, care în acest caz este 1.

Astfel, h(1) = 1 și g(1) = 3. Evident ambele valori sunt mai mici decât ∞ astfel că matricea precedentă se modifică în felul următor.

Pasul 2:

Ne uităm acum la linia 2 și observăm ca atât S1 cât și S2 au valoarea 1 aici. Așa că vom calcula valorile funcțiilor de dispersie. Astfel, h(2) = 2 și g(2) =5 . Pentru că ambele valori sunt mai mari decât ceea ce avem acum în matricea de semnături, nu vom schimba nimic.

Cum paşii 3 și 4 nu vor duce la nici un fel de modificări, trecem la pasul 5.

Pasul 5:

După cum putem observa atât S1 cât și S2 au 1 pe linia 5 astfel că vom calcula h(5) și g(5). Deoarece atât h(5) cât și g(5) au valoarea 0, vom actualiza valoarea corespunzătoare funcţiei g.

Pașii de la 6 la 10 nu schimbă nimic. Atunci trecem la pasul 11.

Pasul 11:

Putem observa că doar S2 are valoare 1 pe linia 11 ceea ce înseamnă că după ce calculăm atât h(11) cât și g(11) vom actualiza doar valorile corespunzătoare lui S2 dacă va fi cazul.

Astfel, h(11) = 0 si g(11) = 1 ceea ce conduce la forma finală a matricii de semnături.

Analizând acum procesul anterior putem trage concluzia că cele două seturi sunt similare în una din cele două linii ale matricii de semnături. Aceasta înseamnă că similaritatea lor este estimată ca fiind 0.5, acest număr fiind relativ apropiat de 0.63 atât cat este similaritatea Jaccard. Evident pentru a obţine rezultate mai bune ar trebui să adăugăm mai multe funcţii ceea va conduce la estimări mai precise. De cele mai multe ori vrem să analizăm doar acele perechi care au un grad de similaritate peste un anumit ,,prag". Există o teorie care ajută să ne îndreptăm atenția doar spre acele perechi și este numită ,,dispersie bazată pe localizare (LSH - locality-sensitive hashing)"sau căutarea celui mai apropiat vecin.

3.Dispersie bazată pe localizare pentru Semnături Minhash

Abordarea generală a LSH este să aplice mai multe funcţii de dispersie asupra elementelor în așa fel încât să se maximizeze probabilitatea ca elementele similare să fie "trimise" în acelaşi compartiment. Considerăm apoi fiecare pereche care a fost trimisă în acelaşi compartiment ca fiind o pereche candidat. Aceste perechi candidat vor fi singurele pe care le verificăm dacă într-adevăr sunt similare. Dacă avem semnături minhash pentru elemente un mod eficient de a lucra este să împărțim matricea de semnături în b benzi formate din r linii. Pentru fiecare bandă vom alege o funcție de dispersie care primește ca argument un vector format din r elemente întregi și le "trimite" într-un număr mare de compartimente.

Analiza tehnicii cu Benzi

Să presupunem că avem b benzi fiecare formate din r linii. Să presupunem apoi că o pereche de documente au similaritatea Jaccard egală cu s. Putem calcula probabilitatea ca aceste seturi (sau mai degrabă semnăturile lor) să devină o pereche candidat în felul următor:

  1. Probabilitatea ca semnăturile să fie identice pe toate liniile unei benzi este s/r.
  2. Probabilitatea ca semnăturile să nu fie identice pe cel puţin o linie dintr-o anumită bandă este egală cu 1-sr.
  3. Probabilitatea ca semnăturile să nu fie identice în cel puţin o linie a fiecărei benzi este (1-sr)b.
  4. Probabilitatea ca semnăturile să fie identice pe toate liniile a cel puţin unei benzi și să devină o pereche candidat este 1-(1-sr)b.

Definim pragul minim ca fiind o funcţie de b și r care exprimă valoarea de similaritate s pentru care o pereche devine candidat. O aproximare a calculului pragului minim este (1/b)1/r. De exemplu pentru b = 16 si r = 4 pragul minim este de aproximativ s = ½.

Exemplu

Folosim aceleaşi două propoziții, dar pentru a face exemplul mai clar vom folosi 10 funcţii de dispersie pentru a calcula matricea de semnături. Setăm pragul de similaritate la 0.5 ceea ce înseamnă că vrem să vedem dacă propozițiile noastre au similaritatea Jaccard egală cu cel puţin 0.5.

Ştim de asemenea că avem 10 linii (numărul de funcţii de dispersie) și astfel dacă luăm în calcul și pragul setat la 0.5 atunci după efectuarea calculelor ajungem la concluzia că avem 5 benzi cu 2 linii pentru fiecare bandă.

Pasul 1. Calculăm matricea de semnături alegând următoarele funcţii de dispersie:

hn(x) = (n*x+1) mod 11, 0\<=n\<=10

După efectuarea calculelor ajungem la următoarea matrice de semnături:

Pasul 2 - Calculăm funcţiile polinomiale pentru fiecare bandă.

Datorită faptului că avem 5 benzi, vom avea nevoie de 5 funcţii polinomiale care primesc câte două argumente (valorile din coloane).

O sa alegem funcţii polinomiale de forma a1* X1+a2*X2+ ... +an*Xn mod m, unde n este numarul de functii iar m este un numar prim foarte mare.

Pentru exemplul nostru alegem următoarele funcţii:

p1 = 2*x1 + 3*x2 mod 13 p2 = 3*x1 + 5*x2 mod 13 p3 = 5*x1 + 7*x2 mod 13 p4
= 7*x1 + 9*x2 mod 13 p5 = 9*x1 + 11*x2 mod 13

Să efectuam calculele pentru prima bandă

(S1) p1 = 2*1 + 3*0 mod 13 = 2 (S2) p1 = 2*0 + 3*0 mod 13 = 0

O să denumim cele două compartimente rezultate B1-2 și B1-0

Calculele pentru bandă a două

(S1) p2 = 3*0 + 5*2 mod 13 = 10 (S2) p2 = 3*0 + 5*0 mod 13 = 0

Compartimentele care rezultă sunt B2-10 și B2-0

Pentru cea de-a treia bandă avem următoarele:

(S1) p3 = 5*0 + 7*0 mod 13 = 0 (S2) p3 = 5*1 + 7*1 mod 13 = 12

Compartimentele care rezultă sunt B3-0 și B3-12

Pentru a patra bandă avem următoarele calcule:

(S1) p4 = 7*0 + 9*0 mod 13 = 0 (S2) p4 = 7*0 + 9*0 mod 13 = 0

Ceea ce este remarcabil acum este că avem doar un compartiment rezultat B4-0. Acest lucru se întîmplă deoarece rezultatul ambelor funcţii este 0.

A cincea banda are următoarele calcule:

(S1) p5 = 9*0 + 11*0 mod 13 = 0 (S2) p5 = 9*0 + 11*0 mod 13 = 0

Din nou avem doar un compartiment rezultat, acesta fiind B5-0.

Avem astfel următoarele compartimente:

B1-2 = {S1}  
B1-0 = {S2}  
B2-10={S1}  
B2-0={S2}  
B3-0={S1}  
B3-12={S2}  
B4-0={S1,S2}  
B5-0={S1,S2}

Pentru că cele două propoziții au fost repartizate cel puţin o dată în acelaşi compartiment (de fapt avem două, B4-0 și B5-0) o să le considerăm ca fiind perechi candidat și o să calculăm coeficientul de similaritate Jaccard pentru ele.

Concluzii

Acest algoritm își dovedește eficiența atunci când este aplicat pe un corp foarte mare de date.

De asemenea pentru a putea gestiona aceste cantități mari de date se recomandă o implementare MapReduce.

Utilizarea algoritmului nu se reduce la găsirea de texte similare. Algoritmul poate fi utilizat pentru orice set de date ale cărui elemente pot fi individual descrise ca un set de caracteristici.

Cu cât semnăturile utilizate de algoritm sunt mai mari cu atât există mai puţine erori, dar asta evident aduce după sine un timp de procesare mai mare.

Chiar dacă algoritmul indică faptul că două segmente sunt similare deoarece fac parte dintr-o pereche candidat este totuși indicat să se calculeze procentul de similaritate Jaccard pentru respectiva pereche.

LANSAREA NUMĂRULUI 87

Prezentări articole și
Panel: Project management

Marți, 24 Septembrie, ora 18:00
Impact Hub, București

Înregistrează-te

Facebook Meetup

Conferință

Sponsori

  • ntt data
  • 3PillarGlobal
  • Betfair
  • Telenav
  • Accenture
  • Siemens
  • Bosch
  • FlowTraders
  • MHP
  • Connatix
  • UIPatj
  • MetroSystems
  • Globant
  • Colors in projects

Ovidiu Petridean a mai scris