Verilənlərdə funksional asılılıqların tapılması verilənlərin təhlilinin müxtəlif sahələrində istifadə olunur: verilənlər bazasının idarə edilməsi, məlumatların təmizlənməsi, verilənlər bazasının əks mühəndisliyi və verilənlərin kəşfiyyatı. Biz artıq asılılıqların özləri haqqında dərc etmişik Anastasiya Birillo və Nikita Bobrov. Bu dəfə Kompüter Elmləri Mərkəzinin bu il məzunu olan Anastasiya mərkəzdə müdafiə etdiyi tədqiqat işi çərçivəsində bu işin inkişafını bölüşür.
Tapşırıq seçimi
CS mərkəzində oxuyarkən verilənlər bazalarını, yəni funksional və fərqli asılılıqların axtarışını dərindən öyrənməyə başladım. Bu mövzu universitetdəki kurs işinin mövzusu ilə bağlı idi, ona görə də kurs işi üzərində işləyərkən verilənlər bazalarında müxtəlif asılılıqlar haqqında məqalələr oxumağa başladım. Mən bu sahəyə rəy yazdım - mənim ilklərimdən biri ingilis dilində hazırlamış və SEIM-2017 konfransına təqdim etmişdir. Nəhayət, onun qəbul olunduğunu biləndə çox sevindim və mövzunu daha dərindən araşdırmaq qərarına gəldim. Konsepsiya özü yeni deyil - o, hələ 90-cı illərdə istifadə olunmağa başladı, lakin indi də bir çox sahələrdə istifadə olunur.
Mərkəzdə işlədiyim ikinci semestr ərzində funksional asılılıqların tapılması üçün alqoritmləri təkmilləşdirmək üçün tədqiqat layihəsinə başladım. O, JetBrains Research-də Sankt-Peterburq Dövlət Universitetinin aspirantı Nikita Bobrov ilə birlikdə bu iş üzərində işləmişdir.
Funksional asılılıqların axtarışının hesablama mürəkkəbliyi
Əsas problem hesablama mürəkkəbliyidir. Mümkün minimal və qeyri-trivial asılılıqların sayı yuxarıda dəyərlə məhdudlaşır Hara — cədvəl atributlarının sayı. Alqoritmlərin işləmə müddəti təkcə atributların sayından deyil, həm də sıraların sayından asılıdır. 90-cı illərdə adi masaüstü kompüterdə federal qanun axtarış alqoritmləri bir neçə saat ərzində 20-yə qədər atribut və on minlərlə cərgədən ibarət məlumat dəstlərini emal edə bilirdi. Çoxnüvəli prosessorlarda işləyən müasir alqoritmlər təxminən eyni vaxtda yüzlərlə atributdan (200-ə qədər) və yüz minlərlə cərgədən ibarət məlumat dəstləri üçün asılılıqları aşkar edir. Bununla belə, bu kifayət deyil: belə bir vaxt real dünya tətbiqlərinin əksəriyyəti üçün qəbuledilməzdir. Buna görə də mövcud alqoritmləri sürətləndirmək üçün yanaşmalar hazırladıq.
Bölmə kəsişmələri üçün keşləmə sxemləri
İşin birinci hissəsində bölmələrin kəsişmə metodundan istifadə edən alqoritmlər sinfi üçün keşləmə sxemlərini hazırladıq. Bir atribut üçün bölmə, hər bir siyahıda verilmiş bir atribut üçün eyni dəyərləri olan sətir nömrələrini ehtiva edən siyahılar toplusudur. Hər bir belə siyahı klaster adlanır. Bir çox müasir alqoritmlər asılılığın saxlanılıb-saxlanmadığını müəyyən etmək üçün bölmələrdən istifadə edir, yəni lemmaya əməl edirlər: Asılılıq əgər keçirilir . Burada arakəsmə təyin edilir və bölmə ölçüsü anlayışından istifadə olunur - içindəki klasterlərin sayı. Bölmələrdən istifadə edən alqoritmlər, asılılıq pozulduqda, asılılığın sol tərəfinə əlavə atributlar əlavə edir və sonra bölmələrin kəsişməsi əməliyyatını yerinə yetirərək onu yenidən hesablayır. Bu əməliyyat məqalələrdə ixtisaslaşma adlanır. Ancaq biz fərq etdik ki, yalnız bir neçə ixtisaslaşma mərhələsindən sonra saxlanılacaq asılılıqlar üçün bölmələr aktiv şəkildə yenidən istifadə edilə bilər, bu da alqoritmlərin işləmə müddətini əhəmiyyətli dərəcədə azalda bilər, çünki kəsişmə əməliyyatı bahalıdır.
Buna görə də biz Şennon Entropiyası və Cinni Qeyri-müəyyənliyinə əsaslanan bir evristik, həmçinin Əks Entropiya adlandırdığımız metrikanı təklif etdik. Bu, Shannon Entropy-nin cüzi modifikasiyasıdır və məlumat dəstinin unikallığı artdıqca artır. Təklif olunan evristik aşağıdakı kimidir:
Burada — bu yaxınlarda hesablanmış bölmənin unikallıq dərəcəsi Və fərdi atributlar üçün unikallıq dərəcələrinin medianıdır. Yuxarıda təsvir edilən hər üç göstərici unikallıq metrikası kimi sınaqdan keçirilmişdir. Evristikdə iki dəyişdiricinin olduğunu da görə bilərsiniz. Birincisi, cari bölmənin əsas açara nə qədər yaxın olduğunu göstərir və potensial açardan uzaq olan bölmələri daha çox keşləşdirməyə imkan verir. İkinci modifikator sizə keşin doldurulmasına nəzarət etməyə imkan verir və bununla da boş yer varsa, keşə daha çox bölmə əlavə etməyi təşviq edir. Bu problemin uğurlu həlli bizə verilənlər bazasından asılı olaraq PYRO alqoritmini 10-40% sürətləndirməyə imkan verdi. Qeyd etmək lazımdır ki, PYRO alqoritmi bu sahədə ən uğurludur.
Aşağıdakı şəkildə siz əsas sikkə ilə keşləmə yanaşması ilə müqayisədə təklif olunan evristikanın tətbiqinin nəticələrini görə bilərsiniz. X oxu loqarifmikdir.
Arakəsmələri saxlamaq üçün alternativ bir yol
Daha sonra arakəsmələri saxlamaq üçün alternativ üsul təklif etdik. Arakəsmələr hər biri müəyyən atributlar üçün eyni dəyərlərə malik olan dəstlərin sayını saxlayan çoxluqlar toplusudur. Bu klasterlər, məsələn, cədvəldəki məlumatlar sıralanırsa, uzun ardıcıllıqlar ardıcıllığını ehtiva edə bilər. Buna görə də, arakəsmələrin saxlanması üçün sıxılma sxemini, yəni arakəsmələrin qruplarında dəyərlərin interval saxlanmasını təklif etdik:
$$display$$pi(X) = {{alt bağlama{1, 2, 3, 4, 5}_{Birinci interval}, alt bənd{7, 8}_{İkinci interval}, 10}}\ aşağı ox {sıxılma} \ pi(X) = {{alt bağlama{$, 1, 5}_{Birinci~interval}, alt bənd{7, 8}_{İkinci~interval}, 10}}$$display$$
Bu üsul TANE alqoritminin işləməsi zamanı yaddaş sərfini 1%-dən 25%-ə qədər azaltmağa müvəffəq olmuşdur. TANE alqoritmi federal qanunları axtarmaq üçün klassik alqoritmdir, iş zamanı arakəsmələrdən istifadə edir. Təcrübənin bir hissəsi olaraq, TANE alqoritmi seçildi, çünki təklif olunan yanaşmanın işlədiyini qiymətləndirmək üçün, məsələn, PYRO-dan fərqli olaraq, interval yaddaşını həyata keçirmək daha asan idi. Alınan nəticələr aşağıdakı şəkildə təqdim olunur. X oxu loqarifmikdir.
Konfrans ADBIS-2019
Araşdırmanın nəticələrinə əsasən, 2019-cu ilin sentyabr ayında bir məqalə dərc etdim Məlumat Bazaları və İnformasiya Sistemlərində İrəliləyişlər üzrə 23-cü Avropa Konfransında (ADBIS-2019). Təqdimat zamanı iş verilənlər bazası sahəsində önəmli şəxs olan Bernhard Thalheim tərəfindən qeyd edilmişdir. Tədqiqatın nəticələri Sankt-Peterburq Dövlət Universitetində riyaziyyat və mexanika üzrə magistr pilləsində dissertasiya işinin əsasını təşkil etdi və bu müddət ərzində hər iki təklif olunan yanaşma (keşləmə və sıxılma) hər iki alqoritmdə həyata keçirildi: TANE və PYRO. Üstəlik, nəticələr göstərdi ki, təklif olunan yanaşmalar universaldır, çünki hər iki alqoritmdə hər iki yanaşma ilə yaddaş istehlakının əhəmiyyətli dərəcədə azalması, eləcə də alqoritmlərin işləmə müddətinin əhəmiyyətli dərəcədə azalması müşahidə edilmişdir.
Mənbə: www.habr.com