Limbaje de Interogare In Big Data

CAPITOLUL 1 Tehnologia big data

De la primele forme de scriere la centrele de date moderne, omenirea a adunat mereu informații. Inovarea în tehnologie a condus la o explozie de date, care necesită sisteme mai sofisticate de stocare. În 1880, sumarizarea recensănântului din S.U.A. a durat 7 ani și s-a estimat ca sumarizarea recensământului din 1890 va dura 13 ani folosind metodele disponibile atunci. Fără un avans tehnologic, catalogarea nu ar fi fost terminată înainte de următorul recensământ. La sfârșitul anilor 1880, Herman Holerith a inventat mașina de catalogat pentru a ajuta la sumarizarea rezultatelor recensământului din 1890, urmând ca după succesul înregistrat, inventatorul american să își înființeze propria companie în 1896 – Tabulating Machine Company – care a continuat sa dezvolte independent invenția până în anul 1911 când s-a alăturat alor 3 companii formând Compania de Catalogare Computerizată a Înregistrărilor, Computing Tabulaion Records Company (CTR), redenumită mai târziu în Mașini de Afaceri Internaționale, International Business Machines (IBM).

Termenul de explozie a informației a fost folosit prima oară în anul 1941, în acea perioadă, scriitorul american Fremont Rider a estimat că bibliotecile universităților americane își dublează numărul de materiale la fiecare 17 ani, și astfel, în anul 2040, biblioteca Yale va avea aproxmativ 200 de milioane de volume, care vor ocupa 10 mii de km de rafturi și va fi necesar un personal de 6000 de persoane pentru catalogare. Pentru a încetini puțin explozia informației, în anum 1967,

************ mai trebuie scris cum s-a ajuns la big data ****************

Big data este un termen general ce definește seturile largi sau complexe de date pentru care, în mod normal, o aplicație de procesare ar fi inadecvată. În această categorie sunt incluse acțiunile de analiza, captare, căutare, partajare, stocare, transfer și vizualizare a datelor. De cele mai multe ori termenul de big data se referă la acțiunile de analiză predictivă (realizarea de estimări asupra evoluției viitoarelor fenomene de marketing) sau alte metode avansate de extragere a valorilor din date, și rareori la o mărime particulară a seturilor de date. Acuratețea acestei analize duce la creșterea eficienței operaționale, reducerea costurilor, dar și a riscurilor.

Analiza acestor seturi de date poate poate fi folosită în identificarea tendințelor de business, prevenirea bolilor și combaterea crimei organizate. Oamenii de afaceri, guvernele, specialiștii în media și publicitate întâmpină adesea dificultăți în utilizarea seturilor mari de date. Oamenii de stiinta se confrunta cu limitari ale serviciului e-Science cum ar fi meteorologia, genomica, conexiunile sistemului nervos, simulari fizice complex, cercetari biologice si de mediu.

Mărimea seturilor de date se află într-o continuă creștere datorită procesului de detactare – învățare a dispozitivelor mobile, ce include: conectări software, camere, microfoane, identificarea frecvențelor radio, senzorii de rețea wireless. Capacitatea de strocare a informațiilor în mediu tehnologic pe cap de locuitor s-a dublat aproape la fiecare 40 de luni din anul 1980(creștere exponențiala). Din anul 2012, sunt creați zilnic câte 2.5 exabytes (2.5×1018) de date.

Sistemele de gestiune a bazelor de date au adesea dificultăți în manipularea volumelor mari de date, un astfel de sistem are nevoie de un software de paralelizare masivă ce lucreaza pe zeci, sute chiar mii de servere. Ceea ce este considerat a fi “Big Data”, în acest moment, peste câțiva ani va deveni un mediu de stocare obișnuit.

De obicei Big data include seturi de date cu o mărime mai mare decât cele folosite de instrumentele software obișnuite pentru captare, gestionare, și prelucrare a datelor. Mărimea pusă la dispozitie de tehnologia Big data își schimbă în mod constant ținta, plecându-se de la câțiva zeci de terabytes la o mulțime de petabytes de date. Big data este un set de tehnici și tehnologii care necesită noi forme de integrare pentru a descoperii în cel mai scurt timp, valorile ascunse într-un volum imens de date.

Într-un raport de cercetare din anul 2001 și alte lecturi de acelasi tip, analistul Doug Laney, de la compania META Group (Gartner – numele actual) definește provocările creșterii datelor ca fiind pe trei dimensiuni: creșterea volumului, creșterea vitezei, și creșterea varietății datelor (multitudinea tipurilor de date și a surselor). În 2012, Gartner și-a actualizat definiția: „Big Data este volumul mare, de mare viteză, și / sau varietate mare de informații care necesită noi forme de prelucrare pentru a permite o luare de decizii îmbunătățită, o înțelegere completă și o optimizare a proceselor.” În plus, un nou V „Veridicitatea”, este adăugată de unele organizații să-l descrie.

Dacă definiția lui Gartner (cei 3 V) este încă în uz, maturitatea crescândă a conceptului ascunde o diferență mai profundă între Big Data și Business Inteligence, cu privire la date și folosința lor:

Domeniul Business Intelligence folosește statistici descriptive cu date de o densitate informatică înaltă pentru a măsura lucruri și pentru a determina tendințe;

Big Data folosește statistici introductive și concepte din sistemele de indenticare nelineare pentru interactiunea legilor (regresie, relatii neliniare) din seturile mari de date cu denistate infromationala scazuta pentru a determina relatii si dependinte. Pe baza acesorea se vor face predictii ale rezultatelor si comportamentelor.

Caracteristici

Tehnologia Big data este definita de urmatoarele caracteristici

Volumul – Cantitatea de date care se generează este foarte importantă în acest context. Volumul este cel care determina valoarea și potențialul datelor ce urmează să fie luate în considerare, dacă datele sunt încadrate ca fiind „big data” sau nu.

Tipul – Se referă la categoria în care se incadreaza datele. Acest lucru este un aspect esențial ce trebuie știut de către analiștii, pentru a utiliza în mod eficient datele, confirmând astfel importanța tehnologiei Big Data.

Rapiditatea – Se referă la viteza de generare și procesare a datelor pentru a răspunde cerințelor și provocărilor care stau în calea creșterii și dezvoltării.

Variabilitatea – Variabilitatea este factorul problematic pentru cei ce se ocupa de analiza datelor. Acest termen face referire la inconsistenta datelor ce poate impiedica procesul de genstionare si utilizare a datelor intr-un mod eficient.

Veridicitate – Calitatea datelor ce au fost stocate poate varia foarte mult. Acuratetea analizei depinde de veridicitatea acestor date.

Complexitatea – Gestionarea datelor poate devenii un proces complex atunci cand un sistem se confrunta cu un volum mare de date ce vin din mai multe surse. Aceste date trebuie etichetate, conectate si corelate astfel incat informatia sa poata fi controlata pentru a fi transmise in mod corect.

Sisteme de lucru din fabrică pot avea un sistem 6C:

Conexiune (senzor și rețele),

Cloud

Cyber (modelul și memorie),

Conținut / context (sens și corelare),

comunitate (de partajare și colaborare)

personalizare.

În acest scenariu, pentru a oferi o bună înțelegere asupra gestionării fabricii, datele trebuie să fie procesate cu instrumente avansate (analitice și algoritmi) pentru a genera informații semnificative. Având din vedere atât problemele vizibile cât și cele mai puțin vizibile dintr-o fabrică industrială, algoritmul de generare a informatiilor trebuie sa fie capabil sa detecteze si sa abordeze aceste probleme mai putin vizibile, cum arr fi degradarea, uzura componentelor,etc.

Big Data necesita tehnologii exceptionale pentru a eficientiza procesarea cantitatilor mari de date intr-un timp cat mai scurt. Raportul McKinsey din 2011 sugerează că tehnologiile adecvate includ testarea A / B, externalizarea unui serviciu, fuziunea și integrarea datelor, algoritmi genetici, mașini de învățare, procesarea limbajului natural, prelucrarea semnalului, simulare, analiza seriilor de timp și vizualizare. Datele multidimensionale pot fi, de asemenea, reprezentate ca tensori. Tehnologiile suplimentare aplicate datelor includ procesare paralela(MPP- massively parallel-processing) a bazelor de date (motoarele de cautare, data mining, sisteme de fișiere distribuite, baze de date distribuite, infrastructuri cloud (aplicații, depozitare și resurse de calcul) și Internet.

Hadoop este un framework dezvoltat in limbajul de programare Java ce suporta procesarea unor seturi mari de date intr-un mediu computational ditribuit.Este o parte a proiectului Apache sponsorizat de catre Apache Software Foundation.

Hadoop face posibila rularea aplicatiilor intr-un sistem cu mii de noduri ce includ mii de terabytes. Sistemul de fisiere partajat sub care este dezvolat faciliteaza transferul rapid de date dealungul nodurilor si permite sistemului sa isi continue activitatea in cazul in care un nod cedeaza. Aceasta abordare micsoreaza riscul defectarii intregului sistem, chiar daca un numar semnificativ de noduri sunt avariate.

Hadoop a fost inspirat din framework-ul dezvoltat de Google sub numele de MapReduce, care aborda metoda descopunerii aplicatiei in parti mai mici. Orice parte din aceasta aplicatie(numita fragment sau bloc)poate rula pe oricare nod al unui clauster. Doug Cutting, creatorul Hadoop, a numit acest framework dupa elefantul de plus al copilului sau

Actualul ecosistem Apache Hadoop este compus din: Hadoop Kernel, MapReduce, Hadoop distributed file system(HDFS) si alte proiecte inrudite cum ar fi Apache Hive, Apache Hbase, Apache Pig, Zookeeper, etc.

Hadoop reprezinta tehnologia ce sta la baza bunei functionari a fluxul de date pentru Google, Yahoo si IBM, in general pentru aplicatiile ce implica motoare de cautare si publicitate. In acest moment sistemele de operare pe care se opteaza implementarea framework-ului sunt Windows si Linux, dar el poate lucra si cu BSD sau OS X

The Apache Hadoop Project

Astazi Hadoop reprezinta o colectie de subproiecte conexe ce se aseaza pe infrastructura sistemelor de calcul distribuit.Aceste proiecte sunt gazduite de catre Apache Software Foundation. infrastructurii se regaseste in figura ….

Core

Un set de componente si interfete pentru sistemul de fisiere distribuit si sistemul general de intrare/iesire (serializare, structuri de date persistente)

Avro

Un sistem serializat de date pentru eficientizarea limbajului RPC, dar si eficientizarea stocarii de date persistente. Avro a fost creat doar ca un nou subproiect, acesta nefiind inca utilizat.

Pig

Pig este o platforma prin care se pot realiza programe de tip MapReduce folosind Hadoop. Limbajul folosit de aceasta platforma se numeste Pig Latin.Pig Latin abstactizeaza programarea Java din ideologia MapReduce intr-o forma similara limbajului SQL pentru sistemele de baza de date relationale. In Pig Latin exista posibilitatea creari de functii definite de catre utilizator (User Defined Functions – UDF). Ele pot utiliza limbajele Java, Python, Javascript, Ruby si Groovy si pot fi apelate direct din limbajul Pig Latin.

Pig a fost dezvoltat de catre Yahoo in anul 2006 pentru cercetatori, pentru a avea o metoda ad-hoc in crearea si executarea sarcinilor map-reduce pe un set mare de date. In 2007, Pig a intrat sub organizatia Apache Software Foundation.

Comunitatea Apache Pig isi continua dezvoltarea in doua arii majore:

Progrese recente ale platformei Pig

Functionalitatile platformei Pig

Pig a fost creat sa proceseze serii largi de operatii pe date, grupandu-le pe trei categorii de sarcini :

Procese Extract-transform-load (ETL),

Cautare in radurile de date,

Procesare iterativa de date

Indiferent de modul de utilizare, Pig va fi:

Utilizatorul poate folosii platforma Pig sub doua moduri, folosit comanda “pig” sau comanda “java”:

Modul MapReduce. Acesta este modul implicit de utilizare si necesita accesul la un cluster Hadoop.

Modul local. Cu acces la o singura masina fizica, toate fisierele sunt instalate si executate folosind statia locala de lucru si propirul sistem de fisiere.

Hive

Este un depozit de date distribuit. Hive gestioneaza datele stocate in HDFS si ofera un limbaj de bazat pe SQL pentru interogarea datelor, numit HiveQL. Interogarile in acest limbaj sunt translatate de catre motoarele de executie in sarcini MapReduce.

Chukwa

Chukwa este un colector de date distribuit si un sistem de analiza.

Chukwa foloseste Hadoop Distributed File System (HDFS) pentru stocarea datelor și MapReduce pentru a crea rapoarte. El moștenește scalabilitatea și robustețea Hadoop. Chukwa include, un set de instrumente flexibile pentru afișarea, monitorizarea și analizarea rezultatelor oferind astfel cea mai buna metoda de utilizare a datelor colectate.

MapReduce

MapReduce este un model de programare pentru procesarea datelor. In Hadoop se pot executa programe MapReduce scrise in diferite limbaje(Java, Ruby, Python, C++).

Map and Reduce

MapReduce functioneaza prin spargerea proceselor in doua faze: faza de mapare si faza de reducere. Fiecare faza are o pereche de valori cheie pentru valorile de intrare si valorile de iesire. Tipul acestora fiind ales de catre programator. De asemenea, programatorul mai trebuie sa specifice doua functii: o functie de mapare si o functie de reducere.

Valorile de intrare pentru faza de mapare sunt datele brute NCDC. Se alege formatul textul de intrare care va genera fiecare linie din seturile de date ca o valoare de tip text.

Sistemul distribuit de fisiere Hadoop(Hadoop Distributed Filesystem – HDFS)

Cand un set de date depaseste capacitatea de stocare a masinii fizice, este necesara o partitionare a datelor pe mai multe masini. Sistemul de fisiere ce administreaza stocarea datelor delungul unei retele de masini fizice se numeste sistem de fisiere disribuit. Fiind un sistem bazat pe distribuirea in retea, au fost intapinate dificultati in programarea retelei. Sistemul de fisiere distribuit a devenit mult mai complex decat un sistem de fisiere obinuit(cel al unui hard-disk). Una dintre cele mai mari provocari a reprezentat-o toleranta sistemului de fisiere la defectarea unui nod. Practic s-a dorit ca sistemul sa retina informatia intacta, in cazul defecarii unui nod din retea.

Hadoop vine cu un sistem de fisiere distribuite numit HDFS, acronimul venind de la Hadoop Distributed Filesystem

HDFS

Sistemul distribuit de fisiere (HDFS) ce poate opera pe un cluster de masini normale. Nu este neaparata de nevoie de utilizarea unui supercalculator.

Proiectarea HDFS

HDFS este un sistem de fisiere proiectat pentru stocarea fisierelor de dimensiuni mari, ce ruleaza pe un cluster format din calculatoare obisnuite.

Fisiere foarte mari

“Foarte mari” în acest context înseamnă fisiere care au ca mărime, sute de megabytes, gigabytes, sau terabytes. Există și clustere Hadoop ce stochează petabytes de date.

Acces direct la date

HDFS este cosiderat ca fiind cel mai eficient model de procesare de date, scrierea de date este permisa o singura data, citirea datelor se poate face de mai multe ori. Seteul de date este de obicei generat sau copiat de la sursa, urmad sa se faca diferite analize pe baza acestuia, intr-un anumit interval de timp. Fiecare analiza implica intr-o mare proportie un set de date, astfel, timpul de citire a intregului set de date este mai important decat lantenta in citirea primei inregistrari de date.

Mașini fizice obișnuite

Hadoop nu necesita masini fizice scumpe, extrem de fiabile pentru a functiona. Este proiectat sa opereze pe clusere cu o configurare hardware normala. Utilizarea unor astfel de masini poate mari posibilitatea de defectarea a nodurilor pe un clauster de scara larga. HDFS este construit astfel incat, orice intrerupere a unui nod sa nu poata fi observata de catre un utilizator.

Ca orice sistem, HDFS are si el limitarile sale, de accea se recomanda testarea aplicatiei in care se va dori includerea sistemului distribuit de fisiere HDFS. Cateva domenii în care HDFS nu a fi o alegere bună:

Accesul rapid la date

HDFS nu ar fi optim pentru aplicatiile ce necesita un acces rapid la date(aproximativ 10 milisecunde).HDFS este contruit pentru livrarea unui volum mare de date, in acest caz, el va fi un mare consumator de timp. HBase este o alegere mult mai buna in cazul accesului rapid.

O multime de fisiere mici

Din moment ce un anumit nod stocheaza in memorie o metadata despre sistemul de fisiere, limita numarului de fisiere intr-un sistem de fisiere este data de cantitatea de memorie din acel nod. Ca si regula de baza, fiecare fisier, director si bloc are o marime aproximativ egala cu 150 bytes. Spre exemplu pentru un milion de fisiere, stocate fiecare intr-un bloc, va fi necesara o memorie aproximativ egala cu 300 MB. In timp ce stocarea a milioane de fisiere este posibila, stocarea miliardelor nu se dovedeste a fi tocmai fezabila pe o configurare hardware normala.

Multiple writers, arbitrary file modifications

Files in HDFS may be written to by a single writer. Writes are always made at the end of the file. There is no support for multiple writers, or for modifications at arbitrary offsets in the file. (These might be supported in the future, but they are likely to be relatively inefficient.)

Fiserele in HDFS sunt scrise de un singur autor. Scriitori sunt mereu la

Concepte HDFS

Blocuri

Un disk are o marime de bloc. Un bloc reprezinta catitatea minima de date ce pot fi citite sau scrise. Sistemul de fisiere pentru un singur disk, utilizeaza metoda impartirii datelor in blocuri. Datele stocate in aceste blocuri trebuie sa aiba o marime egala cu un mutiplu intreg al blocului. Blocurile pentru sistemele de fisiere au de obicei o marime de cativa kilobytes, in timp ce blocurile de pe discuri au in mod normal o marime de 512 bytes.

HBase

HBase este o baza de date distribuita, orientata pe coloane,construita peste HDFS. HBase este o aplicatie Hadoop ce este folosita in citirea si scrierea in timp real a unor seturi mari de date. Desi exista numeroare strategi si implementari pentru stocarea datelor, majoritatea solutilor( in special cele de tip relational) nu sunt construite pentru un volum mare de date. Desi majoritatea comeciantilor ce ofera o structura relationala a bazelor de date, ajung sa ofere solutii pentru extinderea spatiului de stocare oferit de masina fizica, toate acestea se dovedesc, in cele din urma, a fi greu de instalat si intretinut. De asemnea legaturile, interograile complxe, trggeri, view-rile si cheile strine devin greu de executat intr-o structura RDBMS scalata, sau ajung sa nu functioneze deloc.

HBase aduce o rezolvare in problema scalabilitatii cu o viziune total opusa. Hbase nu este un concept relational si nu suporta limbajul SQL. El elimina problema spatiului. Este capabil sa jongleze foarte usor un volum mare de date aflate in claustere.

In mod obisnuit Hbase este utilizat pentru tablearea paginilor web si a atributelor sale, recunoscute dupa adresele URL.

Backdrop

Proiectul Hbase a conceput la sfarsitul anului 2006, de catre Chad Walters si Jim Kellerman. El a fost modelat dupa conceptul “Bigtable” de la Google(un sistem de stocare distribuit pentru datele structurate) imediat dupa publicarea sa.

The first HBase release was bundled as part of Hadoop 0.15.0. At the start of 2008, HBase became a Hadoop subproject at http://hadoop.apache.org/hbase (or http://hbase.org). HBase has been in production use at Powerset since late 2007. Other production users of HBase include WorldLingo, Streamy.com, OpenPlaces, and groups at Yahoo! and Adobe.

Prima lansare a produsului Hbase a fost odata cu lansarea Hadoop 0.15.0, acesta fiind o parte integrata

Prezentarea unui model de date

Aplicatile stocheaza datele intr-un tabel etichetat. Tabelele sunt construite din linii si coloane. Celulele tabelei (coordonatele intersectiei intre randuri si coloane ) sunt versionate. Implicit, versiunea este data de timpul asignat de catre Hbase in momentul inserarii datelor.

Cheile din randurile tabelei sunt byte arays, teoretic, toate tipurile date pot servi ca si cheie de rand, de la string-uri pana la reprezentatii binare, chiar si structuri serializate de date. Randurile tabelei sunt sortate prin cheia randului(cheia primara a tabelei). In mod implicit, sortarea se face orientata pe bit. Accesul catre tabele se face prin intermediul cheii primare. Randurile sunt grupate intr-o familie de coloane.

Regiuni

Tabelele sunt partiționate (orizontal), în mod automat, de către Hbase, în regiuni. Fiecare regiune cuprinde un subset de rânduri ale tabelului. O regiunie este definită de primul său rând, inclusiv, și ultimul său rând, exclusiv. În plus există și o regiune de identificare generată în mod aleator. Inițial un tabel cuprindea o singură regiune, dar prin continuă creștere, aceasta ajungea să depașească pragul admis alocat configurării. Astfel rândurile au fost împarțite în două noi regiuni de mărime aproximativ egală. Numarul de regiuni este direct proporțional cu volumul de date stocat în tabele. Regiunile sunt unitățile ce sunt distribuite pe cluster-ele Hbase. În acest mod, un tabel care deține o cantitate mare de date poate fi împărțit pe mai multe noduri ale cluster-ului, fiecare nod găzduind un subset de date. Acesta este de fapt mijlocul prin care încărcarea datelor în tabele se face distribuit.

Blocarea

Actuailizarea rândurilor este atomică, neținându-se cont din câte coloane este constituită tranzacția. Acest aspect face modelul de blocare simplu.

ZooKeeper

Zookeeper este un serviciu distribuit de coordonare, extrem de disponibil, ce utilizeaza tehnologia Hadoop. El ajuta la scrierea aplicatiilor distribuite.

Scrierea unei aplicatii distribuite este greoiae si asta se datoreaza in primul rand esecurilor partiale. Cand un mesaj este trimis dealungul unei retele, intre doua noduri, si conexiunea cedeaza, emitatorul nu poate intui daca receptorul a primit mesajul. Acest tip de eroare, poate reprezenta un esec partial(atunci cand nu se poate stii daca o operatie a fost efectuata sau nu).

ZooKeeper nu poate indeparta acest tip de esecuri, deoarece acestea sunt intrinseci sistemelor distribuite. Ce poate face Zookeeper, in schimb, este sa ofere un set de instrumente care ajuta la dezvoltarea aplicatiilor distribuite ce se pot ocupa de esecurile partiale.

ZooKeeper are urmatoarele caracteristici:

ZooKeeper este simplu

Zookeeper este, în esența, un sistem de fișiere ce expune cateva operatii simple și câteva abstractizări, cum ar fi cele de comandă și cele de notificări.

ZooKeeper este expresiv

Primitivele ZooKeeper-ului reprezinta un set bogat de blocuri ce pot fi folosite în construirea unei superclase ce coordonaza structuriile de date si a protocoalele.

ZooKeeper este foarte disponibil

Zookeeper este utilzat de mai multe masini fizice si este proiectat sa fie extrem de disponbil, astfel incat aplicatiile sa se poata baza pe el.

Zookeeper facilitează interacțiunile slab cuplate.

ZooKeeper suporta participanti ce nu au nevoie sa cunoasca informatii unul despre celalat. ZooKeeper poate fi folosit ca un mecanism de intalnire a proceselor independente, astfel incat procesele pot sa interactioneze si sa se cunoasca reciproc. Coordonarea partilor nu poate fi simultana, din moment ce un proces trimite un mesaj catre ZooKeeper, ce urmeaza a fi cititi de un alt proces, imediat dupa ce primul proces isi incheie activitatea

ZooKeeper este o librărie

ZooKeeper oferă un depozit open-source, partajat de implementări și rețete ale șabloanelor de coordonare comune. Programatorii individuali sunt scutiți de povara scrierii protocoalelor comune (protocoale care sunt adesea greu de implementat corect). În timp, comunitatea poate adăuga și îmbunătăți librăriile, lucru care este benefic tuturor.

ZooKeeper este și foarte peformant. La Yahoo!, unde a fost creat, transferul ZooKeeper a fost evaluat la 10000 de operații pe secundă pentru sarcini predominant de scriere. Pentru sarcini predominant de citire, tranferul este de cateva ori mai mare.

CAPITOLUL 3 Detecția fraudei. Soluții existente

Bancomatele(automated teller machines ATM) si cardurile de debit au devenit instrumente importante in retail banking, iar semnificația lor economică depășește cu mult scopul inițial de a se retrage bani numerar. Bancomatele și cardurile de debit sunt folosite acum pentru a autentifica clientii, pentru deschideri de conturi si tranzacții online/offline. ATM-urile si cardurile de debit sunt deosebit de atractive pentru infractorii cibernetici, fiind relativ ușor de falsificat. Se pot falsifica numere de card si PIN-urile folosind dispozitive skimming ușor accesibile, avand in vedere faptul ca multe din tranzactiile online nu necesita un card fizic.

Progresele tehnologice pot avea mari probleme de securitate si pot permite infractorilor să cloneze carduri și să fure sume mari de bani în numeroase locații, într-o perioadă scurtă de timp. Un exemplu il reprezinta un sistem de fraudă celebru efectuat în februarie 2009, cand un grup de criminali au extras toate datele unei companii americane de procesare a plăților. Au clonat 100 de carduri de debit, ce au fost folosite în același timp, cu scopul de a se retrage 9 milioane de dolari din la 130 de ATM-uri in 49 de tari.

Acest exemplu subliniază necesitatea critică a instituțiilor financiare de a implementa un sistem robust de supraveghere, care sa detecteze anomaliile in utilizarea cadului și sa furnizeze decizii în timp real pentru blocarea tranzacțiilor suspecte si frauduloase.

Frauda reprezinta una dintre cele mai mari amenintari ale dezvoltarii si sigurantei noaste. Desi nimeni nu cunoaste adevaratele proportii ale fraudei, rar trece o zi fara ca social-media sa nu anunte o frauda. Frauda poate provoca daune semnificative la nivel comunitar, organizational si individual, iar potențialele consecințe ale fraudei pentru organizatii pot fi strategice, legale, financiare sau operationale.

Fig. 1 Piramida potențialelor consecințe al fraudei pentru organizații

Cele mai multe fraude se înregistreaza în sfera bancară, iar sistemul acestora are nevoie de câteva ore pentru a detecta o activitate frauduloasa. Ceea ce s-a dorit, însa, a fost detectarea activitatilor suspecte inainte ca tranzactia sa fie acceptata. Un sistem de detectare a fraudelor in timp real, care sa permita respingerea tranzactiei și notificarea clientului, în vederea autorizării, printr-un apel telefonic catre un reprezentant bancar.

Furnizorul de servicii de operează un dispozitiv comutator(switch) de patru noduri pentru a directiona tranzactiile de la comercianți și bancomate catre bănciile care au emis cardul. Pentru , nodurile sunt împărțite între două centre de date, sunt dirijate spre comutator prin intermediul rețelei IP inteligent furnizorului. Comercianții online și băncile cu ATM-uri sunt similar asociate unor noduri specifice. În contrast, fiecare bancă poate avea traficul distribuit pe mai multe noduri. În acest fel, traficul tranzacțiilor este răspândit dealungul a 4 noduri din rețeaua activ/activ. Fiecare nod are o bază de date cu configurații care specifică ce comercianți, bănci servitoare și ce bănci emitente îi sunt asociate. Nodurile sunt interconectate într-o rețea de tip plasă de către motoarele de replicare bidirecțională a datelor, Shadowbase de la Gravic, Inc. O schimbare a bazei de date intrată în oricare nod din rețeaua aplicației este imediat replicată la celelalte noduri astfel încât toate nodurile să aibă o copie actualizată a bazei de date cu configurații. Baza de date cu configurații mai are o funcție de recuperare în caz de dezastru foarte importantă în care se specifică un nod de rezervă pentru fiecare conexiune în cazul în care nodul acesteia devine indisponibil. De regulă, dacă un nod devine indisponibil, rolul său este preluat de nodul însoțitor din același centru de date. În cazul unei probleme într-un centru de date în care ambele noduri devin indisponibile, rolul lor este preluat de către celălalt centru de date. Din cauza informațiillor de preluare la eroare conținute în baza de date cu configurații, datele replicate nu sunt o replica 1 la 1. Datele replicate pentru fiecare nod trebuiesc modificate astfel încât să reprezinte secvența de eroare pentru nodul respectiv.

Actualizări ale configurației sunt necesare când sunt adaugați și eliminați comercianți și bănci. Mai mult, un comerciant sau o bancă poate fi mutat către al nod pentru echilibrarea traficului. Desi este putin probabil ca doua actiuni qadministrative sa rezulte intr-o coliziune, se poate intampla, in acest caz, cea din urmă este acceptata. Tranzactiile cu cardul nu sunt replicate intre noduri, de vreme ce sunt de natura temporară.În schimb, fiecare nod isi grupeaza propiile tranzactii si trimite in mod frecvent grupuri de tranzactii catre alte noduri din rețeaua IP a furnizorului. data fiind aceasta arhitectura, orice nod pot sa primeasca o tranzactie pentru orice card. marile banci emitente pot avea conexiuni la toate nodurile si pot primii fiecare tranzactie de la nodul la care este conectat ATM-ul sau POS-ul ce a initiat tranzactia.Daca nodul ce a primit tranzactia nu serveste banca emitenta, tranzactia este rutata prin reteaua IP catre nodul corespunzator. Aceasta va fi trimisa mai departe catre banca. Banca emitenta este determinata de catre primele șase cifre ale cardului de credit sau de debit. Arhitectura sistemului activ / activ este utilizată pentru a elimina timpii morți de planificare ai dispozitivului. În cazul în care un nod trebuie să fie actualizat, conexiunile sale sunt atribuite unui alt nod din centrul de date. Nodul este scos din functiune, actualizat, și pus înapoi în serviciu. În acest fel, procesul de actualizare este în controlul personalului IT din centrului de date.

Arhitectura asigurata de furnizor ofera servicii de sute, chiar mii de dispozitive. Rețeaua poate să reziste la orice avariere, de la componetele de conexiune, la noduri de procesare până la întregul centru de date, iar monitorizrea tranzactiilor este continua. Detectarea fraudelor in timp real – vechiul mod de monitorizare pentru detectarea fraudei, cele mai multe bănci emitente oferi propriile lor sisteme. Tranzacțiile sunt scrise într-un fișier log. In acest fisier sunt înregistrate: numărul cardului, data de autorizare și ora, locația POS sau ATM activitatea, precum și suma tranzacției. Un sistem separat de detectare a fraudelor, inspectează periodic acest fisier de tip log. Acest sistem este optimizat, astfel încat sa efectueze analize complexe pe istoricul tranzacțiilor, intorcand un status printr-un flag, iar activitatiile suspecte sunt trecute intr-un alt fisier log si sunt trimise catre sistemul de autorizare. Dupa crearea fisierului, sistemul de autorizare poate lua măsuri corespunzătoare. Se pot accepta tranzacții; se pot nega tranzacții; sau, de exemplu, i se poate solicita clientului, apelarea un reprezentant bancar, pentru ca tranzacția sa poate fi autorizată. Problema acestei metode se rezumă la faptul că poate dura ore sau chiar zile pentru determinarea activităților suspecte. În general, banca este responsabilă pentru tranzacțiile frauduloase, iar această întârziere poate reprezenta un cost semnificativ pentrul banca in cauza.

Asigurarea unor sisteme analitice puternice pentru realizarea aceastor actiuni complexe, în timp real pot fi costisitoare, dar fraudele ar putea fi detectate mai devreme.

Fiecare server monitorizează un anumit numar de carduri. În cazul în care un server cedeaza, un alt server își va asuma responsabilitatea pentru acele carduri. Odata ce o tranzacție este primită în nodul de comutare, tranzacția nu numai ca este trimisă către banca pentru autorizare, dar este, de asemenea replicată pe un server local de detectare a fraudei denumit Shadowbase. Shadowbase determină serverul la care să trimite tranzacția în conformitate cu normele de rutare si numărul de card.

Serverul pe care a fost trimisă tranzactia, face o analiză asupra unor activități suspecte. Daca se determină ca tranzactia ar fi frauduloasa, se trimite o notificare catre nodul de comutare de pe serverul de replicare Shadowbase. Aceasta notificare include un „flag” care indica gradul de suspiciune a stranzatiei. Principalul scop este ca aceasta notificare sa fie trimisa inainte ca banca emitenta sa autorizeze tranzactia, deci o detectare în timp real.

In functie de tipul de „flag” returnat, switch-ul poate aproba tranzactia, o poate anula, sau poate cere clientului sa apeleze un reprezentant bancar inainte ca tranzactia sa fie autoizata. În orice caz, banca emitentă este înștiințată cu privire la activități suspecte, astfel încât titularul cardului să poată fi anuntat, iar banca sa cunoasca contextul de autorizare a tranzacțiilor viitoare.

O tranzacție ar putea trece prin orice nod din calea sa catre banca emitentă, în funcție de configurația facută pe serverul replicat. Prin urmare, este important ca ambele centre de date să cunoască toate activitățile recente asociate cu un anumit card. Pentru a realiza acest lucru, tranzacțiile sunt tamponate de către fiecare nod comutator și sunt transmise în timp aproape real la sistemul de detectare a fraudelor, din celălalt centrul de date.

CAPITOLUL 4 Detecția fraudei folosid Apache Hadoop

4.1 Data mining

Data minig, un subdomeniu interdisciplinar al domeniului IT, este procesul computațional de descoperire a șabloanelor în seturi mari de date ce implică metode ce țin de inteligență artificială, machine learning, statistică și baze de date. Scopul general al prcesului de data mining este să extragă informații dintr-un set de date și să le transforme într-o structură ușor de înțeles pentru uz ulterior. Pe lângă pasul de analiză, presupune și aspecte de întreținere a datelor și a bazelor de date, preprocesarea datelor, modelarea și inferența constatărilor, gradele de interes, complexitatea constatărilor, post-procesarea structurilor descoperite, vizualizarea și actualizarea.

Acest termen este impropriu, deoarece scopul este extragerea șabloanelor și cunoștințelor din volume mari de date, nu extragerea datelor însăși. Este de asemena frecvent folosit pentru orice formă de procesare a datelor sau informațiilor la scară largă (colecție, extracție, depozitare, analiză și statistică) cât și pentru orice aplicație de asistența computerizată în luarea deciziilor, incluzând inteligență artificială, machine learning și business intelligence. Adesea, termenii mai generali cum ar fi „analiză de date” sunt mai adecvate.

Procesul efectiv de data mining este analiza automată sau semiautomată a unor cantități mari de date pentru a extrage șabloane de interes, necunoscute anterior, cum ar fi grupuri de date (analiza de grup), date neobișnuite (detecția anomaliilor) și dependențe (colectarea regulilor de asociere). Acest lucru de obicei presupune folosirea unor tehnici de baze de date precum indicii spațiali. Șabloanele pot fi apoi văzute ca o sumarizare a datelor de intrare, și pot fi folosite în analiza ulterioare sau machine learning și analiză predictivă. De exemplu, pasul de data mining poate identifica mai multe grupuri în setul de date, care pot fi apoi folosite pentru rezultate mai exacte într-un sistem de asistență la decizii. Niciuna din colecția datelor, prepararea lor sau interpretarea și raportarea rezultatului nu fac parte din pasul de data mining, dar țin de procesul global sa pași adiționali.

Termenii data dredging, data fishing și data snooping fac referire la folosirea metodelor de data mining pentru a lua părți dintr-un set mai mare de date care sunt sau pot fi prea mici pentru a se face inferențe statistice sigure despre validitatea șabloanelor descoperite. Aceste metode, totuși, pot fi folosite în crearea de noi ipoteze de testat pe seturile mari de date.

4.2 k-NN

În recunoașterea șabloanelor, k-NN este o metodă non-parametrică folosită la clasificare și regresie. În ambele cazuri, intrarea este reprezentată de cele k mostre din spațiul trăsăturilor. Ieșirea depinde dacă metoda este folosită pentru clasificare sau regresie:

În clasificarea k-NN, ieșirea este apartenența la o clasă. Un obiect este clasificat după majoritatea voturilor vecinilor săi, obiectul fiind asociat clasei predominante dintre cei k cei mai apropiați vecini. Dacă k = 1, obiectul este asociat clasei celui mai apropiat vecin.

În regresia k-NN, ieșirea este valoarea proprietății obiectului. Această proprietate este media valorilor celor k cei mai apropiați vecini.

k-NN este un tip de învățare bazată pe instanțiere, unde funcția este aproximată doar local și toate calculale se execută la clasificare. Algoritmnul k-NN este printre cei mai simplii algoritmi de machine learing.

Atât pentru clasificare cât și pentru regresie, este util să fie asociată o valoare de importanță vecinilor, astfel încât, vecinii mai apropiați să contribuie cu mai mult la medie decât cei mai îndepărtați. De exemplu, o astfel de metodă des folosită este asocierea fiecărui vecin valoarea 1/d, unde d este distanța de la punctul de test până la acel vecin.

Vecinii sunt luați dintr-un set de obiecte pentru care clasa (pentru clasificarea k-NN) sau valoarea proprietății (pentru regresia k-NN) sunt cunoscute. Acesta poate fi văzut ca setul de învățare pentru algoritm, astfel nu este necesar un pas explicit pentru învățare.

O limitare a algoritmului k-NN este sensibilitatea la structura locală a detelor. Algoritmul nu are nicio legătură și nu trebuie confundat cu k-means, o altă tehnică de machine learning.

4.2.1 Algoritmul

Fig 1. Exemplu de clasificare k-NN

Mostra de test (cercul verde) trebuie clasificată fie ca prima clasă a pătratelor albastre, fie ca a doua clasă a triunghiurilor roșii. Dacă k = 3 (cercul cu linie continuă), mostra va fi clasificată ca fiind a doua clasa deoarece sunt două triunghiuri și un singur pătrat în cercul mic. Dacă k = 5 (cercul cu linie întreruptă) va fi clasificată ca fiind prima clasă (sunt 3 pătrate și 2 triunghiuri)

Mostrele de învățare sunt vectori într-un spațiu multidimensional de trăsături, fiecare cu având o etichetă a clasei. Faza de antrenare a algoritmului consta doar în stocarea vectorilor de trăsături și a etichetelor.

În faza de clasificare, k este o constantă definită de utilizator, și un vector neetichetat este clasificat prin asocierea unei etichete care apare cel mai des la cele k mostre de antrenament cel mai apropiate de punctul ce trebuie clasificat.

Măsura folosită cel mai des pentru variabile continue este distanța euclidiană. Pentru variabile discrete, cum ar fi clasificarea textului, se poate folosi altă măsură, cum ar fi măsura de suprapunere (sau distanța Hamming). În contextul datelor … Adesea acuratețea de clasificarea a k-NN poate fi îmbunătățită semnificativ dacă măsura de distanță este învățată cu algoritmi specializați cum ar fi „cel mai apropiat vecin cu margine mare” (Large Margin Nearest Neighbor) sau „analiza compenentelor din vecinătate” (Neighbourhood components analysis).

O problemă a clasificării pe baza votului majoritar apare când distribuția claselor este neuniformă. Mai exact, când mostrele de o clasă mai frecventă tind să domine predicția unei noi mostre din cauză că apar mai des printre cei k vecini datorită numărului lor mare. O modalitate de a evita această problemă este de a „cântări” clasificarea, luând în considerare și distanța dintre punctul de test și fiecare vecin din cei k. Clasa fiecărui vecin este înmulțtă cu o valoare invers proporțională cu distanța până la punctul de test.

4.2.2 Selecția parametrilor

Cea mai bună alergere a k-ului, depinde de data, în general, valorile mari ale k-ului reduc efectele de zgomot în clasificare, dar fac legăturile dintre clase mai greu de identificat. Un k bun poate fi selectat prin diferite tehnici euristice (optimizarea hyperparameter). În cazul în care o clasă se dovedeste a fi clasa mostrei cel mai apropiată (ex. când k = 1), atunci este denumita: algoritmul celui mai apropiat vecin.

Acuratețea algoritmului k-NN poate fi sever degradată de către prezența zgomotelor sau a trăsăturilor irelevante, sau dacă amplificarea trăsăturilor nu este consistentă în importanța ei. Mult efort de cercetare a fost depus în selectarea sau amplificarea trăsăturilor pentru a îmbunătăți clasificarea. O abordare populară este folosirea algoritmilor evolutivi pentru optimizarea amplificării.

În problemele de clasificare binară, este utilă folosirea unui număr impar pentru k deoarece se vor evita voturile egale.

4.2.3 Proprietăți

k-NN este un caz special al algoritmului de estimare a densității nucleu cu lățime de bandă variabilă, estimată cu un nucleu uniform.

Versiunea naivă a algoritmului este ușor de implementat calculând distanțele de la punctul de test la toate mostrele stocate, dar este greoi pentru seturi mari de mostre. Folosind un algoritm adecvat de căutare a celui mai apropiat vecin face k-NN mai ușor de executat chiar și pentru seturi mari de date. Mulți algoritmi de căutare au fost propuși dealungul anilor, aceștia încercând să reducă numărul de evaluări ale distanțelor.

Rezultatele k-NN sunt de o consistență puternică. Pe măsură ce crește volumul de date, algorimtul va avea o rată de erori apropiată de dublul ratei de erori Bayes (rata minimă de erori conform distribuției datelor). Este garantat că algoritmul k-NN se va apropia de rata de erori Bayes pentru o anumită valoare k. Diferite îmbunătățiri sunt posibile folosind grafice de proximitate.

4.2.4 Extracția de trăsături

Când datele de intrare în algoritm sunt prea mari să fie procesate și se suspectează ca fiind redundante, atunci ele vor fi transformate într-o reprezentare cu set redus de trăsături (numită și vector de trăsături). Transformarea datelor de intrare în setul de trăsături se numește extracție de trăsături. Dacă trăsăturile extrase sunt atent alese, se așteaptă ca setul de trăsături să extragă informații relevante din datele de intrare pentru a executa sarcina dorită folosind reprezentarea redusă în locul intrării complete. Extracția trăsăturilor este făcută pe datele neprocesate, înainte de aplicarea algoritmului k-NN pe datele transformate, în spațiul trăsăturilor.

4.2.5 Reducerea dimensiunilor

Pentru date cu multe dimensiuni, reducerea dimensiunilor este realizată de obicei înaintea aplicării algoritmului k-NN pentru a evita efectele multidimensionalității.

Efectele multidimensionalității în contextul k-NN se referă la faptul că distanța euclidiană devine inutilă în cazul unui număr mare de dimensiuni deoarece toți vectorii au aproape aceeași lungime. De exemplu, dacă mai multe puncte s-ar afla mai mult sau mai puțin pe un cerc și punctul de interogare ar fi în centru, distanțele de la punctul de interogare la celelalte puncte va fi aproape aceeași.

Extracția trăsăturilor și reducerea dimensiunilor pot fi cominate într-un singur pas folosind tehnicile de analiză a componentei principale – principal component analysis (PCA), analiza discriminantului liniar – linear discriminant analysis (LDA), sau analiza corelării canonice – canonical correlation analysis (CCA) ca pas de preprocesare, urmat de gruparea cu k-NN pe vectorii de trăsături în spațiu redus ca dimensiuni. În machine learning, acest proces este denumit low-dimensionalembedding.

Pentru seturi de date cu foarte multe dimensiuni (verificarea similarității unor fluxuri video, DNA, etc.) singura opțiune fezabilă ar fi execuția unei căutări k-NN rapide, aproximative, folosind hashing sensibil la locație, „proiecții aleatoare”, „schițe” sau alte tehnici de căutare a similarităților în date cu multe dimensiuni.

4.2.6 Granița de decizie

Regulile celui mai apropiat vecin, implicit, calculează granița de decizie. Este posibil ca aceasta să fie calculată și explicit, și calculată eficient, astfel încât complexitatea computațională să fie în funcție de complexitatea graniței.

4.2.7 Reducerea datelor

Reducerea datelor este una dintre cele mai mari probleme în utilizarea unui asemenea volum de date. De obicei, doar o parte din punctele de date sunt necesare pentru o clasificare corectă. Aceste date se numesc prototipuri și pot fi găsite după cum urmează:

Se selectează „aberațiile”, la o clasă, adică datele clasificate incorect de către algoritmnul k-NN.

Se separă restul de date în două părți:

prototipurile care sunt folosite pentru deciziile de clasificare

punctele absorbite care pot fi corect clasificate de k-NN folosind prototipuri. Aceste puncte pot fi apoi înlăturate din setul de antrenament.

Selecția anomaliilor la o clasă

O mostră de antrenament înconjurată de mostre de altă clasă este numită anomalie la clasă. Cauzele acestor anomalii pot fi:

erori aleatoare

insuficiente exemple de formare a clasei (apare un exemplu izolat în loc de o mulțime de exemple – ce formează un cluster)

lipsesc caracteristici importante (clasele sunt separate în alte dimensiuni, necunoscute)

prea multe mostre de antrenament de la alte clase (clase neechilibrate) care creează un fundal „ostil” pentru clasa mai mică

Anomaliile la clasă cu k-NN produc zgomot. Ele pot fi detectate și separate pentru analiză ulterioară. Fiind date două numere naturale, k>r>0, o mostră de antrenament este numit aberant la clasă (k,r)NN dacă cei mai apropiați k vecini ai săi includ mai mult de r mostre de altă clasă.

4.3 k-means clustering

K-means claustering este o metoda de cuantificare a vectorilor. Este cunoscuta pentru analiza de cluster în data mining. K-means isi proune sa partitioneze n puncte in k claustere. Fiecare punct apartine clauster-ului cu cel mai apropiat centru . Aceasta are ca rezultat o împărțire a spațiului date în celule Voronoi.

Problema este dificila din punct de vedere computational (Timp polinomial non-deterministic). Pentru rezolvarea problemei exista asa numitii algoritmi euristici care sunt utilizati pentru determinarea rapida a optime locale. Acestia sunt, de obicei, similari cu algoritmul așteptare-maximizare pentru amestecurile de distribuții gaussiene .

În plus, ambele folosesc centre de grup pentru a modela datele; Cu toate acestea, K-means clustering tinde să găsească claustere comparabil egale cu marimile spațiale, în timp ce mecanismul de așteptare-maximizare permite clusterelor sa aiba diferite forme.

Fiind dat un set de puncte (x1, x2, …, xn), unde fiecare punct este un vector d-dimensional, algoritmul k-means claustering isi proune sa partitioneze n puncte in k (≤ n) seturi S = {S1, S2, …, Sk} pentru a minimiza suma patratelor din clauster. Cu alte cuvinte, obiectivul este de a găsi:

unde μi este media punctelor din Si.

Algoritmul standard

Cel mai uzual algoritm foloseste o tehnica rafinata de iterativitate. Datorită ubicuității sale este adesea numit algoritmul k-means; este mentionat ca algoritmul Lloyd, în special în comunitatea informatică.

Pasul de atribuire: Atribuirea fiecarui punct la un cluster se face in functie de cea mai mică a suma a pătratelor din cluster. Având în vedere că suma pătratelor este distanța euclidiană la pătrat, aceasta este intuitiv "cel mai apropiata" distanța. (Matematic, aceasta înseamnă împărțirea punctelor, în conformitate cu diagrama Voronoi).

unde fiecare este atribuit exact unui singur , chiar dacă acesta poate fi atribuit mai multor grupuri(clustere).

Pasul de actualizare: Se calculează noile medii pentru a determinarea centroidului punctelor din noile grupuri(clustere)

. Din moment ce media aritmetica este ce estimeaza cele mai mici patrate, aceasta de asemenea, minimieaza suma patratelor din grupuri.

Argoritmul devine convergent atunci cand nu atribuirile raman neschimbate. Din moment ce ambii pasi optimieaza algoritmul SPIG (Suma Ptratelor din Interiorul Grupului), există doar un număr finit de astfel de partitionari. Algoritmul trebuie să conveargă spre un optim(local). Nu există nici o garanție că optimul global va fi găsit folosind acest algoritm.

De obicei, algoritmul este prezentat ca atribuirea de obiecte la grupul cel mai apropiat ca distanță. Algoritmul standard are ca scop minimizarea obiectivului SPIG (Suma Ptratelor din Interiorul Grupului) și asignarea dupa cea mai mica suma de patrare, care devine echivalentă cu atribuirea după cea mai mică distanță Euclidiană. Folosind o functie de distanță, alta decât distanța Euclidină (la patrat) poate opri algoritmul să ajungă la convergență.

Metodele de initializare

Cele mai utilizate metode de initializare sunt Forgy si Partitionarea Aleatoare. Metoda Forgy alege in mod aleator k puncte din grupare si le foloseste pe cele ca medii initaile. Metoda Partitionarii Aleatoare atribuie mai intai un grup aleatoriu pentru fiecare punct si apoi le trece in pasul de actualizare, astfel incat media initiala sa fie centroidul punctelor atribuite aleatoriu grupului. Metoda Forgy tinde sa imprastie media initiala inafra, in timp ce Partionarea Aleatorie paseaza media initiala aparape de centrul unui set de date. Metoda Partiionarii Aleatorie este mai utilizata pentru algoritmi de tip k-medie armonica.Pentru maximizarea așteptarii și algoritmii standard de K-means, metoda Forgy de initializare este de preferata.

Demonstrarea algoritmului standard

1. Initialele k-medii(in acest caz k=3), sunt generate in mod aleatoriu in domeniul de date(afisate in culori).

2. Sunt create k-clausere de care fiecare asociere de puncte cu medie apropiata. Partițiile generate de medii reprezintă diagrama Voronoi.

.

3. Centroidul pentru fiecare k-clauster devine noua medie.

4. Steps 2 and 3 are repeated until convergence has been reached. Pasii 2 si 3 sunt repetati pana la atingerea convergentei.

Deoarece este un algoritm euristic, nu există nicio garanție că va converge la optimul global, iar rezultatul poate depinde grupurile inițiale. Deoarece algoritmul este de obicei foarte rapid, se obișnuiește să se ruleze de mai multe ori cu diferite condiții inițiale. Cu toate acestea, în cel mai rău caz, k-means poate fi foarte lent: în special, sa demonstrat că există anumite seturi de puncte, chiar și în 2 dimensiuni, pe care k-means are nevoie de timp exponențială(2Ω(n)), pentru a converge. Aceste seturi de puncte nu par să apară în practică deoarece, în general, timpul de executie a algoritmului k-means este polinomial.

Pasul de atribuire face referinta si la "pasul de actualizare", ca un pas de maximizare, ceea ce face ca acest algoritm sa devina un algoritm de așteptare-maximizare generalizat.

Complexitate

În ceea ce privește complexitatea computationala, găsirea soluției optime pentru problema algoritmul k-means clustering în utilizarea punctelor in d dimensiuni este urmatorea:

NP-Hard pentru un numar general de k grupuri chiar si in plan.

Daca k si d(dimensiunile) sunt fixe, problema poate fi rezolvata in timp, cu formula , unde n reprezinta numarul de entitati ce urmeaza a fi grupate.

O varietatate de algoritmi euristici cum ar fi Lloyds, mentionat mai sus, sunt in general utilizati.

Timpul de executie al algitmului Lloyds este de obiecei dat de formula , unde n reprezinta numarul de vectori d-dimenionai, k reprezinta numarul de grupuri si i reprezinta numarul de iteratii necesare pana la atingerea convergentei. Pentru datele care nu au o structura de grupare, numarul de iteratii pana la atingerea convergentei este de obiecei mica, iar rezultatele se imbunatatesc usor dupa prima duzina de iteratii. Prin urmare, algoritmul Lloyds este adesea considerat, în practică, de o complexitate "liniară".

Following are some recent insights into this algorithm complexity behaviour. În cele ce urmează sunt prezentate cateva studii recente ale comportamentului complexității acestui algoritm.

Algoritmul Lloyd are un timp de executie polinomial. Se arată că pentru set arbitrar de n puncte cuprinse în, dacă fiecare punct este perturbat în mod independent de către o distribuție normală cu media și variație , atunci timpul de funcționare așteptat de algoritmul k-means este delimitat de formula , care este un polinom în , , și .

Limite mai bune au fost stabilite pentru cazuri simple. De exemplu, s-a arătat că timpul de execuție a algoritm k-means este delimitat de formula pentru n puncte din .

4.4 Canopy

Algoritmul canopy clustering este un algoritm nesupravegheat de pre-clustering, introdus de Andrew McCallum, Kamal Nigdam si Lyle Ungar in anul 2000. Este folosit in pasii de preprocesare a algoritmului k-means sau a algoritmului de grupare ierarhică. Acesta este destinat să accelereze operațiile de clustering pe seturi mari de date,

Algoritmul, foloseste două praguri (distanța de departare) și (distanța de apropiere), unde :

Se începe cu un set de puncte de date care urmează a fi grupate.

Se elimina un punct din set, si se începe un nou „canopy”.

For each point left in the set, assign it to the new canopy if the distance less than the loose distance . Fiecare punct ramas în set, se atribuie la noul „canopy” dacă distanța este mai mică decât distanța de departare

Daca distanta punctului este, in puls, mai mica decat distanța de apropiere , se va sterge punctul, din setul original.

Se repeta pasul 2 pana cand nu mai exista puncte de grupat in set.

Aceste „canopies” grupate relativ ușor din punct de vedere computațional pot fi sub-grupate folosind algoritmi mai dificili dar mai preciși.

Este important de notat faptul ca punctele de date individuale pot face parte din mai multe „canopies”. Ca o accelerare, o metrica de distanță aproximativă și rapida poate fi folosită la punctul 3, iar pentru punctul 4 se utilizeaza o metrică de distanță, mai precisă și mai lentă .

Deoarece algoritmul folosește funcțiile distanță și necesită specificarea pragurilor de distanță, aplicabilitatea sa pentru date de cu foarte multe dimnesiuni, este limitată de scalabilitatea algoritmului.

Beneficii: Determinarea numarului de grupuri si îmbunătățirea celor existente.

CAPITOLUL 5 Implementarea soluției

Pentru a demonstra capabilitățile sistemului hadoop, s-a optat pentru realizarea unei aplicații demonstrative ce permite simularea folosirii unui automat bancar din diferite locații geografice și la o anumită oră și dată.

Aplicația este compusă din două componente, un client și un server. Clientul prezintă o interfață grafică utilizatorului și comunică folosind tehnologia REST cu serverul care administrează baza de date și decide dacă să permită sau nu accesul.

Aceste două componente au fost scrise în limbajul Java folosind librăria Jersey atât în implementarea serviciului REST cât și în implementarea clientului REST. Pe langă librăria Jersey au mai fost folosite Swing pentru implementarea intefeței grafice, hadoop și HBase pentru conectivitatea serviciului REST la serverele hadoop și HBase instalate pe același sistem cu serviciul REST și Mahout pentru agregarea și interpretarea datelor despre istoricul tranzacțiilor.

Fig 5.1 Arhitectura aplicației

5.1 Aplicația client

Aplicația client este scructurată ca în figura de mai jos.

Fig 5.1.1 Structura de fișiere a aplicației client

Launcher.java este clasa ce conține funcția main. Aceasta creează o instanță a clasei ControlPanel pentru a afișa prima fereastră. A doua fereastră este definită în fișierul AtmDisplay.java, iar clientul pentru serviciul REST în fișierul RestClient.java. Toate celelalte fișiere java sunt modele de date folosite în comunicarea cu serviuciul REST.

Prima fereastră ce apare la pornirea aplicației permite configurarea parametrilor simulării, cum ar fi datele cardului virtual ce va fi introdus în bancomat, locația bancomatului accesat, data și ora simulate. Implementarea ferestrei a fost făcută cu ajutorul librăriei Java, Swing, folosind GridBagLayout pentru așezarea controalelor.

Fig. 5.1.2 Fereastra cu parametrii de simulare

GridBagLayout este unul din cele mai flexibile și complexe managere compoziționale din platforma Java. GridBagLayout așează componentele într-o grilă de rânduri și coloane, permițând anumitor componente să se întindă pe mai multe linii sau coloane. Nu toate rândurile au aceeași înălțime și nu toate coloanele au aceeași lățime. În esență, GridBagLayout așează componentele în celule și apoi se folosește de dimensiunea preferabilă a componentelor pentru a determina dimensiunea celulei.

Lista locațiilor este obținută de la serviciul REST la pornire și se află în baza de date HBase. Procedura de obținere a listei în componenta client și toate celelalte apeluri la serviciul REST sunt scrise în clasa RestClient unde se folosesc în stil „fluent” metode ale librăriei Jersey.

Fig. 5.1.3 Obținerea locațiilor cu metodele client din librăria Jersey

La apăsarea butonului “Start!”, se va ascunde fereastra curentă și se va afișa a doua fereastră ce simulează ecranul unui bancomat.

Fig 5.1.4 Fereastra de simulare a unui ATM

Această fereastră conține un panou de titlu ce este întotdeauna vizibil în partea de sus și mai multe panouri ce sunt afișate pe rând, în partea de jos a ferestrei. Aceste panouri sunt:

panoul mesaj – folosit pentru afișarea unui mesaj. Poate afișa și o imagine animată pentru a simboliza procesele active

panoul de introducere a PIN-ului

panoul principal – conține mai multe butoane pentru retrageri, depuneri și schimbare PIN

panoul de introducere suma – folosit pentru introducerea sumei de depus sau retras

panoul de schimbare PIN

La 3 secunde după deschiderea ferestrei „Simulator ATM”, se va simula introducerea cardului, iar pe ecran va fi afișat mesajul „Verificăm cardul”. Verificarea cardului presupune trimiterea datelor acestuia către serviciul REST unde se stabilește dacă se poate folosi cardul respectiv, verificând integritatea datelor, data expirării și ultimele tranzacții astfel încât să nu se poată folosi cardul concomitent în două bancomate diferite sau la intervale de timp foarte scurte, în locații îndepărtate una de cealaltă.

Dacă s-a determinat că nu se poate folosi cardul respectiv, se va afișa mesajul „Card invalid”, în caz contrar se va continua prin a cere introducerea codului PIN de către utilizator. În acest câmp, simulatorul permite doar 4 caractere numerice. După introducerea celor 4 cifre ale codului PIN, se va afișa mesajul „Tranzacție în curs”, de data această, vor fi reverificate datele cardului, după care se va determina dacă a fost introdus codul PIN corect. Codul PIN al fiecărui card este stocat în baza de date HBase sub formă criptată, algoritmul folosit fiind Bcrypt, un algoritm de hashing realizat de Niels Provos și David Mazières bazat pe cifrul simetric Blowfish prezentat la USENIX în anul 1999. Deoarece algoritmul de criptare este ireversibil, verificarea codului PIN se face prin criptarea codului introdus și compararea rezultatului cu cel din baza de date.

Dacă se determina că PIN-ul introdus nu este corect, se va afișa timp de 3 secunde mesajul „PIN incorect”, apoi se va reveni la eranul anterior. În caz contrar, se va afișa meniul principal ce conține date despre contul atașat cardului, deținătorul cardului, soldul și permite schimbarea codului PIN, extragerea și depunerea de numerar.

Fig 5.1.5 Meniul principal al bancomatului

În meniul principal, în partea stângă sunt poziționate butoanele pentru retragere de numerar. Primele 3 butoane vor retrage anumite valori prestabilite, iar al 4-lea va permite utilizatorului să introducă valoarea pe care dorește să o retragă din cont. Dacă tranzacția s-a finalizat cu succes, va fi afișat mesajul „Ridicați bancnotele din automat” și se va reda zgomotul produs de bancomat.

Pentru depunerea de numerar, se va afișa același ecran în care se va introduce valoarea ce va fi introdusă. La apăsarea butonului „Depunere”, se va afișa mesajul tranzacție în curs pe toată durata redării sunetului pe care îl face bancomatul atunci când numără bancnotele, apoi se va afișa mesajul „Tranzacție finalizată”. În ambele cazuri, și pentru retragere și pentru depunere, bancomatul se va închide după finalizarea tranzacției.

La apăsarea butonului „Schimbare PIN”, se va afișa panoul de introducere a codului PIN de două ori, pentru confirmare.

5.2 Serviciul REST

Serviciul REST are următoarea structură:

Fig 5.2.1 Structura de fișiere a serviciului REST

Serviciul REST este componenta cea mai importantă, care, după cum a mai fost menționat, a fost implementată cu ajutorul librăriei Jersey.

Serviciul se află pe unul din sistemele pe care este instalat hadoop, putând fi folosit în diferite configurații hadoop fără să fie modificat (ex. configurație cu un singur nod).

Fișierele ce intră în componența serviciului sunt în mare parte fie modele de date, fie clase ce implementează metodele REST. Excepție fac clasele BCrypt, Canopy, KMeans, EuclideanSpace și TransactionHistory care conțin implementări de algoritmi și alte funcții utile.

Clasele ce implementează metodele REST se deosebesc de celelalte prin terminația „Service”. Cea mai simplă astfel de clasă este LocationService.java ce conține o singură metodă, prima apelată de fiecare instanță a aplicației client și anume getLocations. Această metodă nu are legătură cu sistemul de detecție a fraudei, ci doar cu partea de simulare a unui ATM, ea returnând o listă cu locațiile ATM-urilor de la care se poate efectua o tranzacție. Motivul implementării acestei funcționalități este faptul că sunt folosite coordonatele geografice ale acestor locații în algoritmii de machine learning.

Lista locațiilor este preluată din baza de date HBase, mai exact din tabelul „atms” și încărcată într-o listă de tip ArrayList<Location>, „Location” fiind modelul folosit pentru fiecare element din listă, apoi transmisă spre client în formatul JSON (JavaScript Object Notation) unde este preluată într-un alt ArrayList folosind un model compatibil.

5.2.1 Baza de date

Baza de date conține 3 tabele structurate conform tabelului 5.2.1.1 în care numele din paranteză reprezintă numele stocat pe disk. Numele coloanelor și familiilor de coloane sunt cât mai scurte deoarece acestea sunt repetate pe disk pentru fiecare înregistrare.

Tabelul 5.2.1.1 Structura bazei de date

5.2.2 Clasele „Service”

5.2.2.1 SimulationService

Următoarea clasă ce implementează serviciul REST este SimulationService. Această clasă are mai multe roluri: administrează toți clienții conectați la serviciul REST și reține pentru fiecare parametrii simulării, cum ar fi locația, data și ora. Pentru funcționarea acestei clase sunt folosite mai multe modele care, evident, au un corespondent în aplicația client. Unul de ele este Simulation, care reține data simulării și locația. Acesta este completat de către aplicația client și transmit către serviciul REST ca solicitare pentru începerea simulării.

La primirea unei astfel de solicitări, serviciul REST generează un șir de caractere aleator pe care îl transmite clientului, acesta fiind folosit ca o parolă pentru solicitările ulterioare. Intern, serviciul va citi din baza de date latitudinea și longitudinea locației primite de la client (din motive de securitate) și, pe lângă parametrii simulării și token-ul clientului conectat, va mai reține și data și ora începerii simulării. Aceasta din urmă va fi folosită pentru a determina data și ora simulată la un moment dat.

Cealaltă metodă implementată de clasa SimulationService este stopSimulation care va șterge toate datele reținute pentru un anumit client conectat, acesta nemaiavând posibilitatea să mai efectueze tranzacții.

Pe lângă metodele REST, clasa SimulationService mai conține o metodă ce returnează datele despre un anumit client pe baza token-ului generat la conectarea acestuia.

5.2.2.2 CardService

Această clasă implementează toate acțiunile ce pot fi inițiate asupra unui card. Prima acțiune inițiată de client este checkCard. Această metodă verifică existența cardului și valabilitatea acestuia returnând către client o valoare boolean în text simplu (fără JSON). În cazul în care cardul introdus este valid, clientul va cere introducerea codului PIN, după care va apela metoda useCard. Această metodă verifică validitatea cardului și a codului PIN introdus după care asociază cardul introdus cu clientul administrat de clasa SimulationService. Verificarea codului PIN presupune extragerea codului criptat din baza de date și verificarea lui folosind metoda checkpw din clasa BCrypt. Aceasta este o clasă terță ce criptează codul primit de la client folosind algoritmul blowfish cu același cod „sare” cu care a fost criptat codul din baza de date. Acest lucru este necesar deoarece este generat un cod „sare” unic pentru fiecare cod PIN stocat în baza de date, acestu lucru prevenind un atacator care a obținut acces la baza de date să compromită conturile clienților care au același cod PIN, deoarece variantele criptate sunt diferite.

După autentificare, aplicația client va avea nevoie să afișeze date despre contul asociat cardului cum ar fi, numele și prenumele deținătorului, codul IBAN și balanța. O parte din aceste date le preia prin intermediul metodei getAccount ce primește token-ul clientului și returneaza un model Account în format JSON bazându-se pe cardul asociat de către metoda anterioară. Cealaltă parte este obținută prin intemediul metodei getUserInfo a clasei UserService care va fi detaliată mai jos.

Din acest punct, în funcție de acțiunile utilizatorului, se pot apela fie metoda withdraw, fie metoda deposit. Ambele metode primesc ca parametru token-ul clientului și o valoare de tip double reprezentând sumă ce va fi extrasă sau respectiv depusă în cont. Aceste două metode sunt cele care implementează algoritmul de recunoaștere a șabloanelor.

5.2.2.3 UserService

Clasa UserService conține o singură metodă REST, și anume getUserInfo. Această metodă primește ca parametru token-ul clientului și returnează în modelul User numele și prenumele deținătorului cardului.

5.2.3 Algoritmul de recunoaștere a șabloanelor

Pentru a determina dacă utilizatorul este într-adevăr deținătorul contului s-a optat pentru înregistrarea datelor despre fiecare tranzacție a acestuia și testarea dacă parametrii unei noi tranzacții se încadrează în șabloanele definite de tranzacțiile anterioare. Recunoașterea acestor șabloane a fost realizată cu algorimii canopy și k-means, iar determinarea dacă o anumită tranzacție este sau nu o anomalie s-a realizat cu un algoritm propriu ce are ca baza k-NN.

Clasa care implementează tot acest mecanism este TransactionHistory și expune o singură metodă, isTransactionSafe ce primește parametrii de simulare, contul utilizatorului și diferența dintre noua balanță și vechea balanță a contului. Pe langă această metodă și alte metode interne, clasa mai conține și o serie de constante menite să permită ajustarea parametrilor celor 3 algoritmi la compilare.

Fig 5.2.3.1 Parametrii algoritmilor de machine learning

Metoda isTransactionSafe mai întâi vectorizează datele tranzacției curente, normalizează vectorul, rulează cei doi algoritmi de grupare, canopy și k-means, pentru a obține lista de grupuri pe baza celor mai recente date, după care determină distanța de la punctul tranzacției curente la fiecare grup din listă. Dacă cea mai mică distanță este mai mare decât suma dintre raza grupului și constanta KNN_LOOSE_DISTANCE, atunci tranzacția este raportată ca fiind suspectă. În caz contrar se va stoca vectorul noii tranzacții în fișierul secvență pentru utilizatorul curent. Locația acestui fișier este calculata concatenand șirul de caractere „account_” urmat de codul IBAN al contului la constanta TRANSACTIONS_DIR definită și ea în clasa TransactionHistory. Numele fișierului secvență este „data_seq”. Alături de el mai există și fișierul „data_key” care reține ultimul identificator de rând folosit în fișierul secvență. Pentru a asigura validitatea datelor, hadoop creeaza automat, pentru fiecare fișier, și un fișier hash.

Pentru a asigura că există suficiente puncte de date în fișierul secvență, s-a creeat o constantă, LEARN_PERIOD, reprezentând numărul de tranzacții după care vor începe să fie rulați algoritmii de machine learning, înainte de atingerea acestui număr, toate tranzactiile vor fi raportate ca fiind normale.

Clasa EuclideanSpace conține 3 metode care au fost necesare în implementarea algoritmilor. Aceste metode permit determinarea distanței dintre două puncte n-dimensionale folosind formula lui Euclid, determinarea mediei punctelor dintr-o listă dată și norma 2 (norma Euclidiană) a unui vector.

Concluzii

Din ceea ce s-a prezentat pe parcursul întregii lucrari s-a ajuns la concluzia ca, fraudele bancare sunt intr-o continua dezvoltare, iar tehnologia este cea mai de preț armă în combaterea acestor infraciuni.

Securitatea si detectarea fraudelor bancare pot fi imbunatatite prin utilizarea unor tehnologii avansate.

În sistemul bancar au loc foarte multe tranzactii zilnice, iar detectarea in timp real a fraudelor reprezenta o problema, astfel, un sistem de stocare a datelor de tip relational se dovedeste ineficient si

Cea mai importanta resursa in combaterea fraudelor bancare, prezentata in aceasta lucrare, o reprezinta implementarea unei structuri de tip BIG DATA, în acest caz, framework-ul Hadoop Apache. Utilizarea acestui sistem permite procesarea distribuita a seturilor de date dealungul mai mulor custere de calculatoare.

Stocarea unui volum mare de date și procesarea rapida a acestora nu mai reprezinta o problema intr-un sistem de baze de date orientat pe coloane cum ar fi HBase.

O alta resursa importanta prezentata în aceasta lucrare este utilizarea

Bibliografie