Căutând inspirație în algoritmul kNN

Vlad Adrian
Senior Software Programmer @ Cegedim

Este recomandat ca o interfață web să fie atrăgătoare din punct de vedere grafic și să conțină elemente intuitiv de utilizat atunci când este nevoie de interacțiuni cu utilizatorul. Însă putem să nu ne rezumăm doar la aceste aspecte. În beneficiul utilizatorului, suntem liberi să creăm funcționalități suplimentare, poate chiar neobservabile, care să îmbunătățească fluxul de lucru în browser. Prim urmare ne propunem să implementăm o căutare client side într-o listă de obiecte, astfel încât rezultatele cele mai relevante să fie afișate primele.

De fapt, lista noastră de obiecte poate fi reprezentată printr-un tabel, o linie în tabel afișând valorile unui obiect iar coloanele tabelului reprezentând proprietățile obiectului.

Așadar, putem spune că avem o matrice cu n linii și n coloane:

Avem nevoie să căutăm date în tabelul reprezentat. În mod natural, căutarea se efectuează pe baza unor sintagme, una sau mai multe propoziții. Prin urmare, avem mai multe cuvinte care trebuie căutate pe fiecare linie a tabelului, verificate din punctul de vedere al potrivirii gramaticale cu fiecare valoare a unui element al matricii.

O să descriem această lista de cuvinte ca un vector de dimensiune p unde p reprezintă numărul de cuvinte de căutat:

Pentru a determina rezultatele relevante ale căutării, avem nevoie să calculăm distanța dintre cuvintele de căutare și fiecare valoare din matrice:

În expresia de mai sus, este distanța (nu Euclidiană) calculată folosind o formulă personalizată, adaptată nevoilor noastre de căutare.

Așadar, folosind această distanță, putem defini coeficientul de relevanță pentru fiecare linie din tabel, în raport cu lista de cuvinte de intrare:

Aceasta este toată "magia". Acum avem tot ceea ce ne trebuie: o listă de obiecte în care fiecare dintre acesta are propria relevanță raportată la un set de date utilizate în procesul de căutare.

Pentru a afișa rezultatele finale, avem nevoie să sortăm obiectele ascendent în funcție de relevanța calculată. Una dintre posibilități ar putea fi ca, după fiecare căutare, să afișăm lista cu toate obiectele sortate. În aceast mod, liniile cu relevanța cea mai mare vor fi afișate primele în listă, iar la final vom găsi întotdeauna linille cu relevanță zero.

Pentru optimizarea memoriei, putem afișa în lista de rezultate doar obiectele cu relevanță mai mare decât zero. Pentru a optimiza și mai mult timpul de execuție, putem afișa doar primii k cei mai apropiați vecini găsiți, adică primele k obiecte cu cea mai mare relevanță calculată până în acel moment.

Una dintre provocările metodei este de a defini metrica pentru calculul distanței dintre fiecare cuvânt de căutat și valoarea unui element al matricii.

Presupunând că avem cuvântul w și valoarea d, iar index este poziția lui w în d, facem o reducție modulo 1 a poziției detectate pentru a ne asigura că avem tot timpul 1 ca distanță maximă dintre un cuvânt și valoarea unui element al matricii. De aici deducem că distanța unei linii este o sumă de distanțe ale elementelor. Astfel, valoarea 0 indică cea mai mare potrivire a căutării pe când valoarea 1 nu indică nicio potrivire. În limbajul de programare JavaScript se poate scrie:

/**
 * Default metric between a word and a cell value
 * @param {String} word from vector search
 * @param {String} data value for a field’s object
 * @returns {Number}
*/
#metric(word, data) {
  let index = String(data).toLowerCase().indexOf(word);
  if (index > -1) {
    return 1 - 1/(1 + index);
  }
  return 1;
}

Desigur, folosind alte limbaje de programare, implementarea metodei va beneficia de avantajele și caracteristicile fiecărui limbaj în parte. Considerăm că este importantă metoda ce poate fi extinsă și reutilizată.

Continuând implementarea algoritmului, în JavaScript, am construit o clasa kNNSearch prin care se pot seta valorile vectorului de căutare, valoarea numărului k, metoda privată descrisă mai sus, plus alte două metode private pentru calculul distanțelor:

// calculate distance for a cell value using #metric() method 
#cellDistance(value) { /*...*/ }

// calculate distance for a row based on columns cofiguration
// using #cellDistance method
#rowDistance(row, columns) { /*..*/ }

Pentru calcularea rezultatelor, se apelează o metoda publică applySearch() în care se verifică vectorul de căutare, se apelează metodele de calcul al distanțelor, se elimină liniile fără relevanță și se oprește căutarea după primele k rezultate relevante detectate. Obținem, astfel, un prim set de rezultate grupate într-un obiect ce simulează o tabelă hash ai cărei indecși reprezintă relevanțele calculate. Pentru a obține lista finală, rezultatele grupate după relevanțe sunt sortate ascendent în funcție de relevanță, concatenate și returnate ca un tablou simplu neasociativ.

Încercând să exemplificăm un set de rezultate, în reprezentarea de mai jos avem un obiect cu relevanța 8, șapte obiecte cu relevanța 9, unul cu relevanța 9.98 și alte două relevanțe:

{
    "8": [{ id: 18 }],
    "9": [{ id: 4 }, { id: 6 }, { id: 9 }, { id: 11 }, { id: 16 }, { id: 33 }, { id: 46 }],
    "9.983333333333334": [{ id: 13 }],
    "9.967741935483872": [{ id: 14 }],
    "8.773929083828653": [{ id: 17 }]
}

Pentru rezultatele finale, datele de mai sus se ordonează și se concatenează într-o singură listă după cum urmează:

[{ id: 18 }, { id: 17 }, { id: 4 }, { id: 6 },
{ id: 9 }, { id: 11 }, { id: 16 }, { id: 33 }, 
{ id: 46 }, { id: 14 }, { id: 13 } ]

Clasa kNNSearch va putea fi utilizată și în alte module ori componente ori diferite servicii JavaScript astfel:

let kNN = new kNNSearch();
kNN.setK(numberValue);
kNN.setVector(stringValue);
let results = kNN.applySearch(rows, columns);

Bineînțeles că algoritmul poate fi optimizat ori îmbunătățit.

De exemplu, la procesarea vectorului de căutare, cuvintele pot fi triate pe baza unui alfabet predefinit. Astfel, eliminăm cuvintele fără nicio importanță în căutare, ca de exemplu cele de legătură: și, cu, la etc. Ori, putem împărți cuvintele în tokenuri de dimensiuni stabilite pentru a rafina precizia relevanțelor calculate sau pentru a efectua căutări asincrone pentru un plus de rapiditate.

Pentru calculul metricii, am creat o metodă privată. Această metodă poate fi injectată sub formă de callback în constructorul clasei de căutare. Astfel, lăsam la latitudinea programatorului să își creeze propria metodă de calculare a distanței.

Poate că în JavaScript suntem constrânși de lipsa unor resurse de calcul adecvate unor algoritmi puternici. Însă, chiar și așa, rezultate user friendly cred că pot fi obținute destul de ușor. Putem explora și alte metode euristice care, datorită simplității lor, să poată fi implementate în JavaScript, fie chiar și ca primă parte de procesare a unor seturi de date ce vor fi trimise către back-end.

Bibliografie:

1. Florin Leon, Inteligență artificială: raționament probabilistic, tehnici de clasificare, Ed. Tehnopress, 2012, Capitolul 9, Clasificarea bazată pe instanțe

2. Smaranda Belciug, Marina Gorunesc, Modele predictive și de clasificare în Matlab și Java, Ed. Albastră, 2012, Capitolul 5

3. Gerd Gigerenzer, Peter M. Todd, Metode euristice simple pentru decizii inteligente, Ed. Publica, 2010