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.
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.
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.
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.
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.
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.
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.
Î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.
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".
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.
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".
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.
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)].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:
h1(r), h2(r), . . . , hn(r)c are 0 pe linia r, atunci nu se întîmplă nimicc 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 ∞.
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.
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.
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.
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.
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.
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-sr.(1-sr)b.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 = ½.
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\<=10După 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 13Să efectuam calculele pentru prima bandă
(S1) p1 = 2*1 + 3*0 mod 13 = 2 (S2) p1 = 2*0 + 3*0 mod 13 = 0O 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 = 0Compartimentele 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 = 12Compartimentele 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 = 0Ceea 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 = 0Din 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.
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.
de Monica Rațiu
de Emil Luța
