Un termen la modă în informatică este "big data" (date de dimensiuni mari). Înmulţirea senzorilor ieftini conectaţi la internet (receptoare GPS, accelerometre, camere video) a adus o explozie de informaţie al cărei potenţial abia a început să fie descoperit.
Asta se datorează, în mare parte, timpului necesar pentru procesarea datelor.
Mulţi cercetători din domeniul informaticii încearcă să simplifice procesarea datelor de dimensiuni mari dezvoltând algoritmi mai eficienţi. Într-un articol recent, prezentat la conferinţa internaţională de la Association for Computing Machinery (Asociaţia Maşinăriilor Computerizate) despre Advances în Geographic Information Systems (SIG – Sisteme Informatice Geografice), cercetătorii de la MIT au propus o altă abordare prin descrierea unei noi căi de reprezentare a datelor în aşa fel încât să se micşoreze spaţiul ocupat în memorie, dar datele să fie procesate în modurile convenţionale. Deşi se promite o accelerare semnificativă a calculelor, abordarea poate fi mult mai general aplicabilă decât tehnicile de procesare "big-data" de vreme ce poate funcţiona cu algoritmii existenţi.
În noul articol, cercetătorii aplică tehnica lor pentru date de locaţie bidimensionale generate de receptoare GPS, o aplicaţie normală care demonstrează clar cum funcţionează tehnica. Daniel Rus, profesor în informatică, inginer şi director al laboratorului MIT (laborator de informatică şi inteligenţă artificială), descrie cum receptoarele GPS citesc date la fiecare 10 secunde, acumulându-se 1 gigabyte de date zilnic. Un sistem informatic ce se confruntă cu situaţia procesării datelor GPS a 10.000 de automobile, în scopul afişării situaţiei din trafic, poate deveni repede supraîncărcat şi nu va face faţă.
Însă, la analiza unei rute parcurse de o maşină, nu este necesar să se ia în calcul coordonatele precise ale fiecărui punct situat de-a lungul rutei. Informaţia esenţială o reprezintă punctele în care maşina îşi va schimba direcţia; lungimea dintre astfel de puncte poate fi aproximată printr-o linie dreaptă. Asta face noul algoritm.
Un aspect cheie ce îl are algoritmul – spune Dan Feldman, cercetător ştiinţific la studii postdoctorale, lider şi autor al noului articol din echipa lui Daniel Rus – este acela că poate comprima datele în timpul procesării. De exemplu, poate comprima primul megabyte de date pe care-l primeşte de la un automobil, apoi aşteaptă ca alt megabyte să fie creat, îl comprimă şi pe acesta, aşteaptă alt megabyte ş.a.m.d. – păstrându-se aproape aceeaşi cantitate de informaţie pe care a primit-o înainte de procesare şi comprimare.
Creionarea metodologiei
Problema aproximării căilor dintre puncte este similară cu o problemă rezolvată prin analiză de regresie, o procedură utilizată în statistică prin care, în cazul unei mulţimi de puncte, se va trasa o linie care descrie cel mai bine distribuţia punctelor ce nu sunt coliniare. Există, însă, o diferenţă majoră; aceea că algoritmul cercetătorilor trebuie să găsească o serie de segmente care să aproximeze cel mai bine lungimile dintre puncte.
Alegerea numărului de segmente implică un compromis între acurateţe şi complexitate. Feldman spune "Dacă ai N puncte, k..." – numărul de segmente – "... este un număr între 1 şi N. În momentul în care creşte k, eroarea va fi mai mică. În situaţia în care doar uneşti punctele, eroarea va fi zero, dar nu va fi o aproximaţie bună. Dacă alegi k = 1, ca în regresia liniară, aproximaţia va fi prea riguroasă." Aşadar, prima sarcină a algoritmului este să găsească compromisul optim dintre numărul de segmente şi eroare.
Următorul pas este calculul setului optim de segmente k – acelea care corespund cel mai bine datelor. Va urma alt pas, unul crucial: pe lângă memorarea unei reprezentări matematice a segmentului ce corespunde cel mai bine cu fiecare mulţime de puncte, algoritmul memorează şi coordonatele precise unui eşantion aleatoriu de puncte. Punctele situate cel mai departe de linie au o şansă mai mare să fie eşantionate, însă punctele eşantion vor avea o pondere invers proporţională cu şansa de a fi eşantionate. Punctele apropiate de linie au o şansă mai mică să fie eşantionate, dar dacă unul din ele va fi eşantionat, i se va da o pondere mai mare, de vreme ce este printre puţinele puncte eşantion.
Combinarea aproximaţiei lineare cu eşantioane aleatorii permite algoritmului să comprime datele în timpul procesării. La baza eşantioanelor, algoritmul poate calcula segmentele optime, la nevoie, imediat ce apar date noi.
Satisfacţie garantată
În timpul comprimării, o parte din informaţii va fi pierdută, însă Feldman, Rus şi studentul Cythia Sung, al 3-lea autor al proiectului, au fost capabili să ofere garanţii matematice că eroarea introdusă va rămâne sub pragul minim. În multe contexte big-data, o uşoară aproximare eronată este mult mai bună decât un calcul care nu poate fi efectuat deloc.
În principiu, aceeaşi abordare poate funcţiona cu orice tip de date, în mai multe dimensiuni faţă de cele două înregistrate de receptoarele GPS. De exemplu, cu fiecare citire GPS, o maşină poate înregistra în acelaşi timp, temperatura, presiunea aerului şi poate să creeze un instantaneu asupra drumului. Fiecare măsurătoare în plus va reprezenta o altă coordonată a unui punct în dimensiuni multiple. Aşadar, când comprimarea a fost efectuată, punctele eşantion aleatoare vor conţine fotografii şi date atmosferice. Datele pot servi ca bază unui sistem ce, de exemplu, va prelua fotografii ce surprinde orice porţiune de drum pe o hartă, pe lângă indicarea situaţiei din trafic.
Trucul căutării unor aplicaţii pentru noua tehnică constă în descoperirea unor cazuri în care aproximaţia liniară a mulţimilor de puncte are un scop clar. În cazul datelor GPS, este simplu: fiecare segment reprezintă calea aproximativă aleasă între punctele unde se schimbă direcţia de mers (curbe). Una dintre noile aplicaţii căutate de Feldman este analiza datelor video, unde fiecare segment reprezintă o scenă, iar punctele de legătură dintre segmente reprezintă tăieturi. Şi aici, reprezentarea finală a datelor li se vor insera automat cadre-eşantion din fiecare scenă.
Potrivit spuselor lui Alexandre Bayen, un profesor asociat de sisteme inginereşti la Universitatea din California, la Berkeley, proiectul cercetătorilor de la MIT "deschide drumul în domeniul extragerii repetate de tipare dintr-un semnal GPS şi folosirea acestor date pentru a produce hărţi în scopul transmiterii datelor GPS."
În limbajul ştiinţific de calcul, explică Bayen, un set de date redus ce poate fi procesat ca şi cum ar fi un set mai mare se numeşte "coreset" (set-nucleu). "Coreset-ul este o soluţie bună pentru problemele de tip big-data deoarece se extrag eficient părţi esenţiale ale semnalului ce vor fi suficiente pentru procesare," spune Bayen. "Aceste părţi esenţiale sunt selectate astfel încât rularea algoritmului pe datele din coreset este doar cu puţin mai neperformantă decât rularea algoritmului pe întregul set de date, iar aceste erori au limite garantate."
Traducere de Bogdan Mihalcea după Speeding algorithms by shrinking data.
Bibliografie suplimentară: Analiza de regresie pe înţelesul tuturor.
