Un motor eficient de cautare in e-commerce
Istoric si motivatie 2.1 Istoric al cautarii informatiei
Yüklə 350,51 Kb.
|
2. Istoric si motivatie2.1 Istoric al cautarii informatieiPrimele colectii de documente au fost inregistrate pe peretii pictati ai pesterilor. Apoi, pana la inventia hartiei, anticii romani si greci au inregistrat informatia pe role de papirus. Unele artefacte de papirus aveau mici etichete atasate rolelor, care ajutau la gasirea informatiei. Cuprinsul unei lucrari au inceput sa apara in rolele din Grecia in secolul 2 i.Hr. Ulterior, s-a scris pe pergament, straturi subtiri de piele de animale. Pentru perioada aceasta, cele mai relevante metode de informatie erau cele pe cale orala. (Langville si Meyer, 2006) Inventarea hartiei, cel mai bun suport de stocare a informatiei, a crescut viteza inregistrarii documentelor si au inceput sa apara colectii tematice. Acest lucru a fost accelerat puternic prin inventarea presei tipografice de catre Johann Gutenberg in 1450. In anii 1700 au aparut in America biblioteci publice, la initiativa lui Benjamin Franklin. Astfel, a crescut dorinta de a ierarhiza informatiile. (Langville si Meyer, 2006) Primul sistem de organizare a informatiei a fost atribuit autorului roman Valerius Maxiums, care l-a folosit in anul 3 d.Hr. pentru a organiza informatia unei carti ale lui. Ulterior, au aparut sisteme ca sistemul decimal Dewey (1872), cataloagele de carti (inceputul anilor 1900), microfilmul (anii 1930), sistemul MARC (MAchine Readable Cataloging – catalog citibil de catre masini) in anii 1960. In ceea ce priveste cautarile in baze de date pentru carti au inceput cu un sistem SMART (inteligent) al Cornell in anii 1960. (Langville si Meyer, 2006) In anul 1989 stocarea, accesare si cautarea colectiilor de documente a fost revolutionata de o inventie numita World Wide Web (reteaua pentru lumea intreaga) de catre fondatorul sau, Tim Berners-Lee. Aceasta a devenit semnalul final al dominatiei Erei Informatiei si moartea Erei Industriale. Cu toate acestea, volumul mare de informatie facea cautarile initiale foarte greoaie. (Langville si Meyer, 2006) Primele motoare de cautare aveau dificultati in ierarhizarea informatiei. Lucrurile s-au schimbat radical odata cu aparitia Google. Intr-un document datat 29 ianuarie 1998, "The PageRank Citation Ranking: Bringing Order to the Web" (ierarhizarea bazata pe citari PageRank: aducand ordine in Internet), autorii, dintre care primii doi au fondat Google (Lawrence Page, Sergey Brin, Rajeev Motwani si Terry Winograd), prezentau PageRank, un algoritm care dadea o importanta resurselor gasite in cautari, pe masura volumului linkurilor catre o anumita resursa (cu precizarea ca o resursa putea acorda o valoare mai mare daca, la randul ei, avea multe linkuri). Autorii concluzionau ca "folosind PageRank, putem ordona cautarile, in asa fel incat paginile cele mai importante au pozitii preferentiale. In experimentele facute, asta a dus la rezultate de calitate ridicata pentru utilizatori". (Page et al., 2018) Documentul era o continuare a documentului „The Anatomy of a Large-Scale Hypertextual Web Search Engine” (anatomia unui motor de cautare pe Internet pe scala larga, si hipertextual), in care Sergey Brin si Lawrence Page prezentau motorul de cautare in detaliu, inclusiv formula de calculare a PageRank-ului: „Presupunem ca pagina A are linkuri de la paginile T1 ... Tn (aceste pagini o citeaza. Parametrul d este un factor de amortizare, care poate fi setat intre 0 si 1. In general, il stabilim la valoarea 0,85. De asemenea, C(A) este definit ca numarul de linkuri care pornesc dinspre pagina A spre alte pagini. PageRank-ul paginii A este definit astfel: PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) De notat ca PageRank-ul formeaza o distributie probabilistica peste toate paginile de Internet, asa ca suma tuturor PageRank-urilor va fi 1. PageRank-ul pentru 26 de milioane de pagini web poate fi calculat in cateva ore pe o statie de lucru medie.” (Brin si Page, 1998) Intr-o lucrare aparuta in 2006 (Langville si Meyer, 2006), formula este prezentata ca mai jos, o ecuatie simpla a sumelor, radacina carei deriva din cercetarile bibliometrice, analiza structurii citatiilor intre lucrarile academice. PageRank-ul paginii Pi, numita r(Pi), este suma tuturor PageRank-urilor paginii care directioneaza catre Pi. 
unde BPi este setul paginiilor care au trimitere catre Pi (trimit backlink catre Pi in cuvintele autorilor Sergey Brin si Lawrence Page), si |Pj| este numarul de linkuri externe (catre alte entitati) trimise din pagina Pj. De observat ca PageRank-ul paginilor care trimit linkuri catre entitate curenta r(Pj) din ecuatia anterior mentionata este temperat de numarul de recomandari facute de Pj, notat |Pj|. Problema cu ecuatia respectiva este ca valorile r(Pj), PageRank-ul paginilor care trimit catre pagina Pi, sunt necunoscute. Pentru a trece peste aceasta problema, autorii ecuatiei au folosit o procedura iterativa. Astfel, ei au presupus ca, la inceput, toate paginile au un PageRank egal una cu cealalta (sa zicem, 1/n, unde n este numarul de pagini din indexul web al lui Google). Acum regula in ecuatia prezentata este urmata pentru a calcula r(Pi) pentru fiecare pagina Pi din index. Regula dinecuatie este aplicata in mod succesiv, inlocuind valorile iteratiei anterioare in r(Pj). Introducem si alte notatii pentru a defini aceasta procedura iterativa. Fie rk+1(Pi) PageRank-ul paginii Pi pentru iteratia k + 1. Atunci,  (Langville si Meyer, 2006)
Procesul este initiat cu r0(Pi) = 1/n pentru toate paginile Pi si este repetat, in speranta ca scorurile Page Rank vor converge in final catre niste valori stabile. Aplicand ecuatia de mai sus retelei din figura de mai jos da urmatoarele valori pentru PageRank, dupa cateva iteratii:
3 6 5
4 Figura 2.1.1 Graf directionat, reprezentand o serie de sase pagini (Langville si Meyer, 2006)
Tabel 2.1.1 Primele cateva iteratii ale ecuatiei anterior prezentate asupra grafului (Langville si Meyer, 2006) Un alt algoritm al motoarelor de cautare este si HITS. Un acronim pentru „Hypertext Induced Topic Search” (cautare de subiecte induse prin hipertext), acesta a fost un algoritm aflat la baza Teoma, un motor de cautare lansat in 2001 si achizitionat in acelasi an de un alt motor de cautare, Ask Jeeves Inc. (The Globe si Mail, 2001) HITS, algoritm inventat de Jon Kleinberg in 1998 (aproximativ in aceeasi perioada in care Sergey Brin si Lawrence Page lucrau la algoritmul PageRank), asemenea PageRank, foloseste structura de URL-uri pentru a crea scoruri de popularitate asociate cu paginile web. Totusi, HITS are anumite diferente (detalii preluate din Langville si Meyer, 2006):
Cum functioneaza algoritmul? (Langville si Meyer, 2006) Fiecare pagina i are un scor de autoritate xi si un scor de hub yi. Fie E setul tuturor marginilor directionate in graful de Internet si fie eij marginea directionata de la nodul i catre nodul j. Dat fiind faptul ca fiecarei pagini i-a fost atribuita initial un scor de autoritate initiala xi si un scor de hub yi, HITS rafineaza in mod succesiv aceste scoruri calculand: 
, unde k = 1, 2, 3, ... Aceste ecuatii, care au fost ecuatiile originale ale inventatorului lor, Jon Kleinberg, pot fi scrise intr-o forma matriceala cu ajutorul matricei de adiacenta L a grafului de URL-uri directionate. (Langville si Meyer, 2006) P1 P2 P3 P4 P1 0 1 1 0
1 2
3 4 Figura 2.1.2 Graf pentru o retea de 4 elemente (Langville si Meyer, 2006) In notarea matriciala, ecuatiile precizate iau forma:
unde x(k) si y(k) sunt n x 1 vectori care pastreaza autoritatea aproximativa si scorurile fiecarui hub la fiecare iteratie. (Langville si Meyer, 2006) Algoritmul original HITS: (Langville si Meyer, 2006)
x(k) = LTy(k-1) y(k) = Lx(k) k = k + 1 Se normalizeaza x(k) si y(k). Lucrurile au evoluat, pe masura ce anii au trecut. Algoritmii s-au tot schimbat, la un moment dat Google afirma ca au 200 de factori. Intrebat despre asta, in 2010, CEO-ul Google, Eric Schmidt, a afirmat ca nu ii poate mentiona, pentru ca sunt intr-o continua schimbare, si, de asemenea, pentru ca sunt un secret comercial al companiei. (Sullivan, 2010) Potrivit informatiilor celor de la SearchEngineLand, un site important in lumea motoarelor de cautare, „RankBrain” este numele dat de catre Google unui sistem de inteligenta artificiala bazat pe invatare automata (machine-learning artificial intelligence system) care este folosit pentru a genera rezultatelor cautarilor. Prin machine learning, un calculator poate sa se invete pe sine insusi cum sa faca o sarcina, mai degraba decat sa urmeze o procedura predefinita. La data aparitiei articolului, algoritmul ocupa locul 3 in cele mai importante criterii dupa care un site era afisat in rezultatele cautarilor. Scopul lui? Interpretarea rezultatelor care nu contin cuvintele cautate in mod exact, ci cuvinte ce ar putea fi similare. Nevoia de a exista a algoritmului venit din faptul ca Google procesa in 2016 3 miliarde de cautari zilnic, iar in 2007 a afirmat undeva intre 20-25% din acele cautari nu au fost observate pana atunci (nu fusesera probabil cautate niciodata pana atunci). In 2016 e posibil sa fi ajuns la 15% din cautari, in continuare o valoare mare de cautari pentru care algoritmul isi justifica existenta. Sunt cautari in special formate din multi termeni („long-tail”, cautari foarte specifice, dar, totusi, numeroase). (Sullivan, 2016)
Tabel 2.1.2 Cota de piata la nivel mondial, motoare de cautare (StatCounter Global Stats, 2018) Va puteti intreba unde au loc cautarile in 2018, nu doar cele din motoare de cautare, ci, la modul general, pe toate platformele unde pot avea loc cautari. Date din februarie 2018 pentru piata din SUA arata dominatia Google, care detine motorul de cautare, Google Imagini si YouTube (cu un procent mult mai mic, si Google Harti). De remarcat ca Amazon, cel mai mare magazin online, are o cota un pic mai mare decat Bing, al doilea motor de cautare generalist, dupa Google. (Fishkin, 2018) 
Figura 2.1.3 Cota de piata a cautarilor web, februarie 2018, pentru piata din SUA (date din partea companiei Jumpshot) Cate motoare de cautare (generale, pentru tot Internetul) exista? Poate, din diferite surse, ati aflat ca exista „sute de motoare de cautare”. Majoritatea dintre acestea sunt insa fie variatii ale site-urilor principale (de exemplu, Google.fr pentru Franta sau Google.co.uk pentru Marea Britanie), fie sunt meta motoare de cautare, care folosesc rezultatele oferite de alte motoare de cautare (Dogpile, Mamma.com, Metacrawler). Da, exista unele motoare de cautare tematice (Wolfram|Alpha, IMDb), dar motoarele cele mai vizitate au un procent apropiat de 95% din piata motoarelor de cautare. (Grappone si Couzin, 2011) Exista si alte tipuri de algoritmi care pot sustine un motor de cautare. Platforma de clipuri video YouTube este al doilea motor de cautare, ce-i drept, specializat, dupa Google, cu aproximativ 3 miliarde de cautari pe luna, un volum de cautare mai mare decat cel al Bing, Yahoo!, AOL si Ask.com combinate. (Wagner, 2017) Lucrurile la care se uita cei 1,5 miliarde de utilizatori inregistrati ai platformei YouTube sunt influentate de o lista de clipuri asemanatoare. De fiecare data cand un internaut priveste un clip YouTube, i se prezinta intr-o bara laterala o lista de clipuri asemanatoare. Acea lista e considerata cel mai important factor in cresterea cotei de piata a YouTube. In una din putinele explicatii publice despre cum functioneaza formula, o lucrare academica care prezinta retelele neuronale ale algoritmului, inginerii YouTube o descriu drept una din "cele mai mari si sofisticate sisteme de recomandare la scala industriala existente in lume". (Lewis, 2018) Faptul ca Facebook, cea mai folosita retea sociala la nivel mondial – 2,2 miliarde de utilizatori activi pe luna, in al 4-lea trimestru al lui 2017 (Statista, 2018) –, cu un potential enorm in a ajuta utilizatorii in cautarea de produse si servicii pe plan local, cu un ecosistem format din milioane de pagini de afaceri, date despre locatie ale utilizatorilor, date de comportament, informatii demografice, rata de angajament, nu a reusit in anii recenti sa fie un concurent serios pentru Google in cautarile de afaceri locale poate fi un argument ca a fi relevant in cautari e o sarcina mai grea decat pare la o analiza superficiala.
Yüklə 350,51 Kb. Dostları ilə paylaş:
|