Datuetan dependentzia funtzionalak aurkitzea datu-analisiaren hainbat arlotan erabiltzen da: datu-baseen kudeaketan, datuen garbiketa, datu-baseen alderantzizko ingeniaritza eta datuen esplorazioa. Dagoeneko argitaratu dugu mendekotasunei buruz Anastasia Birillo eta Nikita Bobrov. Oraingoan, Anastasiak, aurten Informatika Zentroko lizentziatua, lan honen garapena partekatzen du zentroan defendatu zuen ikerketa lanaren baitan.
Zereginen hautaketa
CS zentroan ikasten ari nintzela datu-baseak sakonki aztertzen hasi nintzen, hau da, mendekotasun funtzional eta desberdinen bilaketa. Gai hau unibertsitateko nire kurtsoko gaiarekin erlazionatuta zegoen, beraz, ikastaroa lantzen ari nintzen bitartean, datu-baseetako hainbat mendekotasunei buruzko artikuluak irakurtzen hasi nintzen. Arlo honen berrikuspena idatzi nuen - nire lehenengoetako bat ingelesez eta SEIM-2017 kongresura aurkeztu zuen. Oso pozik geratu nintzen azkenean onartuta zegoela jakin nuenean, eta gaian sakontzea erabaki nuen. Kontzeptua bera ez da berria - 90eko hamarkadan hasi zen erabiltzen, baina orain ere arlo askotan erabiltzen da.
Zentroan nire bigarren seihilekoan, mendekotasun funtzionalak aurkitzeko algoritmoak hobetzeko ikerketa-proiektu bat hasi nuen. San Petersburgoko Estatuko Unibertsitateko Nikita Bobrov-ekin batera lan egin zuen JetBrains Research-en.
Mendekotasun funtzionalak bilatzeko konplexutasun konputazionala
Arazo nagusia konplexutasun konputazionala da. Mendekotasun gutxieneko eta ez hutsal posibleen kopurua balioaren arabera mugatzen da Non β taulako atributu kopurua. Algoritmoen funtzionamendu-denbora atributu kopuruaren araberakoa ez ezik, errenkada kopuruaren araberakoa da. 90eko hamarkadan, mahaigaineko ordenagailu arrunt batean lege federalen bilaketa-algoritmoek 20 atributu eta dozenaka mila errenkada dituzten datu multzoak prozesatu ditzakete hainbat ordutan. Nukleo anitzeko prozesadoreetan exekutatzen diren algoritmo modernoek ehunka atributu (gehienez 200) eta ehunka mila errenkadaz osatutako datu multzoen mendekotasunak hautematen dituzte gutxi gorabehera aldi berean. Hala ere, hori ez da nahikoa: halako denbora onartezina da mundu errealeko aplikazio gehienentzat. Hori dela eta, lehendik dauden algoritmoak bizkortzeko planteamenduak garatu ditugu.
Cache-eskemak partizioen elkarguneetarako
Lanaren lehen zatian, partizioen ebakidura metodoa erabiltzen duten algoritmo-klase baterako katxeatzeko eskemak garatu ditugu. Atributu baten partizioa zerrenda multzo bat da, non zerrenda bakoitzak atributu jakin baterako balio berdinak dituzten lerro-zenbakiak dituen. Horrelako zerrenda bakoitzari kluster esaten zaio. Algoritmo moderno askok partizioak erabiltzen dituzte mendekotasuna mantentzen den ala ez zehazteko, hots, lemara atxikitzen dira: Mendekotasuna. ospatu bada . hemen partizio bat izendatzen da eta partizioaren tamaina kontzeptua erabiltzen da - bertan dauden kluster kopurua. Partizioak erabiltzen dituzten algoritmoek, mendekotasuna urratzen denean, atributu gehigarriak gehitzen dituzte mendekotasunaren ezkerraldean, eta, ondoren, berriro kalkulatu, partizioen ebakidura eragiketa eginez. Eragiketa horri artikuluetan espezializazioa deitzen zaio. Baina espezializazio txanda batzuen ondoren bakarrik mantenduko liratekeen menpekotasunen partizioak aktiboki berrerabili daitezkeela ohartu gara, eta horrek algoritmoen exekuzio-denbora nabarmen murrizten du, elkargune-eragiketa garestia baita.
Hori dela eta, Shannon Entropy eta Ginny Uncertainty-n oinarritutako heuristika bat proposatu genuen, baita gure metrika ere, zeinari Reverse Entropy deitu genion. Shannon Entropy-ren aldaketa txiki bat da eta datu-multzoaren berezitasuna handitu ahala handitzen da. Proposatutako heuristikoa honako hau da:
Hemen β Duela gutxi kalkulatutako partizioaren berezitasun-maila Eta atributu indibidualen berezitasun-mailen mediana da. Goian deskribatutako hiru metrika guztiak berezitasun metrika gisa probatu ziren. Heuristikoan bi modifikatzaile daudela ere nabarituko duzu. Lehenengoak adierazten du uneko partizioa gako nagusitik zenbateraino dagoen hurbil eta gako potentzialetik urrun dauden partizioak neurri handiagoan gordetzeko aukera ematen du. Bigarren aldatzaileak cachearen okupazioa kontrolatzeko aukera ematen du eta, ondorioz, cachean partizio gehiago gehitzea bultzatzen du leku librea badago. Arazo honen konponbide arrakastatsuari esker, PYRO algoritmoa % 10-40 bizkortu genuen, datu-multzoaren arabera. Aipatzekoa da PYRO algoritmoa dela arlo honetan arrakasta handiena duena.
Beheko irudian proposatutako heuristikoa aplikatzearen emaitzak ikus ditzakezu txanponak iraultzeko oinarrizko cachearen ikuspegiarekin alderatuta. X ardatza logaritmikoa da.
Partizioak gordetzeko beste modu bat
Ondoren, partizioak gordetzeko modu alternatibo bat proposatu genuen. Partizioak kluster multzo bat dira, eta horietako bakoitzak atributu batzuen balio berdinak dituzten tupla kopurua gordetzen du. Multzo hauek tupla-zenbakien sekuentzia luzeak izan ditzakete, adibidez, taula bateko datuak ordenatuta badaude. Hori dela eta, partizioak gordetzeko konpresio eskema bat proposatu dugu, hots, partizio multzoetan balioak tarteko biltegiratzea:
$$display$$pi(X) = {{giltza azpian{1, 2, 3, 4, 5}_{Lehenengo tartea}, giltza azpian{7, 8}_{Bigarren tartea}, 10}}\ downarrow{ Konpresioa} \ pi(X) = {{giltza azpiko{$, 1, 5}_{Lehenengo~tartea}, azpiko giltza{7, 8}_{Bigarren ~tartea}, 10}}$$display$$
Metodo honek TANE algoritmoaren funtzionamenduan memoria-kontsumoa % 1etik % 25era murrizteko gai izan zen. TANE algoritmoa lege federalak bilatzeko algoritmo klasikoa da; bere lanean zehar partizioak erabiltzen ditu. Praktikaren barruan, TANE algoritmoa aukeratu zen, askoz errazagoa baita bertan tarteen biltegiratzea ezartzea, adibidez, PYROn baino, proposatutako ikuspegiak funtzionatzen duen ebaluatzeko. Lortutako emaitzak beheko irudian azaltzen dira. X ardatza logaritmikoa da.
ADBIS-2019 jardunaldia
Ikerketaren emaitzetan oinarrituta, 2019ko irailean artikulu bat argitaratu nuen Datu Baseetan eta Informazio Sistemen Aurrerapenei buruzko Europako 23. Konferentzian (ADBIS-2019). Aurkezpenean, datu-baseen alorreko pertsona esanguratsua den Bernhard Thalheim-ek nabarmendu du lana. Ikerketaren emaitzak San Petersburgoko Estatuko Unibertsitateko matematika eta mekanikako masterrean egin dudan tesiaren oinarria izan dira, eta bertan proposatutako bi ikuspegiak (cachinga eta konpresioa) bi algoritmoetan ezarri ziren: TANE eta PYRO. Gainera, emaitzek erakutsi zuten proposatzen diren planteamenduak unibertsalak direla, izan ere, bi algoritmoetan, bi ikuspegiekin, memoria-kontsumoaren murrizketa nabarmena ikusi zen, baita algoritmoen funtzionamendu-denboraren murrizketa nabarmena ere.
Iturria: www.habr.com