Funksional asılılıqlara giriş

Bu məqalədə məlumat bazalarında funksional asılılıqların nə olduğu, harada tətbiq olunduqları və onların axtarılması üçün hansı alqoritmlərin mövcud olduğu haqqında danışacağıq.

Funksional asılılıqları relasional məlumat bazalarının kontekstində nəzərdən keçirəcəyik. Ümumiyyətlə desək, belə məlumat bazalarında məlumatlar cədvəl şəklində saxlanılır. Sonra yaxın anlayışları istifadə edəcəyik ki, bunlar sərt relasional nəzəriyyədə qarşılıqlı əvəz edilə bilməz: cədvəli münasibət, sütunları atributlar (onların bir çoxu — əlaqənin sxemi) adlandıracağıq və atributların alt dəstindəki satır dəyərləri — tupla.

Məsələn, yuxarıdakı cədvəldə, (Benson, M, M organ) atributlar üzrə tupladır (Pasient, Cins, Həkim).
Daha formal şəkildə bu aşağıdakı kimi yazılır: [Pasient, Cins, Həkim] = (Benson, M, M organ).
İndi funksional asılılıq (FA) anlayışını təqdim edə bilərik:

Tərif 1. Əlavə R, FA X → Y (burada X, Y ⊆ R) şərtini ödəndikdə, hər hansı tupların , ∈ R şərti təmin olunur: əgər [X] = [X], o zaman [Y] = [Y]. Bu halda X (determinanta, ya da müəyyən edən atributlar toplusu) Y-ni (asılı toplu) funksional olaraq müəyyən edir.

Başqa sözlə, FA-nın olması X → Y deməkdir ki, əgər bizdə R-də iki tupla varsa R və onlar atributlar üzrə üst-üstə düşürlərsə X, o zaman onlar atributlar üzrə də üst-üstə düşəcəklər. Y.
İndi isə addım-addım baxaq. Atributlar üzrə nəzərdən keçiririk Pasient və Cins onların arasında asılılığın olub-olmamasını bilmək istədiyimiz atributlardır. Bu atributlar arasında aşağıdakı asılılıqlar mövcud ola bilər:

1. Pasient → Cins
2. Cins → Pasient

Yuxarıdakı tərifə uyğun olaraq, ilk asılılığın qalması üçün hər bir unikal sütun dəyərinə yalnız bir sütun dəyəri uyğun gəlməlidir. Pasient Və nümunə cədvəlində bu doğrudan da belədir. Lakin geri istiqamətdə bu işləmir, yəni ikinci asılılıq icra olunmur, və atribut Cinsdeterminant deyil Cins Pasient . Eynilə, əgərHəkim → Pasient asılılığına baxsaq, onun pozulduğunu görə bilərik, çünkiRobin də bu atribut üzrə bir neçə fərqli dəyəri var — Ellis və Graham. Beləliklə, funksional asılılıqlar atribut topluları arasında mövcud olan əlaqələri müəyyən etməyə imkan tanıyır. Buna görə də, daha sonra ən maraqlı əlaqələri nəzərdən keçirəcəyik, yəni belə.

, ki onlar: X → Ytrivial olmayanlardır, yəni asılılığın sağ tərəfi sol tərəfin alt dəsti deyil

• (Y ̸⊆ X) minimaldır, yəni belə bir asılılıq yoxdur;
• Z → Y , kiZ ⊂ X Z ⊂ X.

İndidən əvvəl müzakirə olunan asılılıqlar sərt olub, yəni cədvəldə hər hansı pozuntuları gözləmirdi, lakin onlardan əlavə müəyyən dərəcədə qeyri-müəyyənlikləri qəbul edən asılılıqlar da var. Belə asılılıqlar ayrı bir sinifə ayırılır, yaxın asılılıqlar adlanır və müəyyən sayda kütlədə pozulmalarına icazə verilir. Bu say maksimum xətanın göstəricisi emax ilə tənzimlənir. Məsələn, xəta faizi = 0.01, asılılığın müzakirə edilən atributlar topluluğundakı 1000 qeyddən maksimum 10 kütlənin FZ-ni pozmasına icazə verə biləcəyini bildirə bilər. Biz bir az fərqli bir metrikaya baxacağıq ki, bu da müqayisə olunan kütlələrin cüt-cüt fərqli dəyərlərinə əsaslanır. Asılılıq X → Y nın nisbəti r bu cür müəyyən edilir:

Yuxarıda göstərilən nümunə üçün xətanı hesablayarıq. İki kütlə var ki, onların atributlarındakı dəyərləri fərqlidir, asılılığına baxsaq, onun pozulduğunu görə bilərik, çünki amma Pasienthəm də Doktor: [Doktor, Pasiyent] = (Robin, Ellis) və [Doktor, Pasiyent] = (Robin, Graham). Xəta anlayışına uyğun olaraq, bütün ziddiyyətli cütləri nəzərə almalıyıq, yəni bunlar iki olacaq: (, ) və tərsi (, ). Formulumuza qoyaq və alacağıq:

İndi isə sualın cavabını tapmağa çalışaq: «Bütün bunların nəyə gərək olduğu?». Gerçəkdə, FZ-lər müxtəlif olur. Birinci tip — bunlardır ki, administrator tərəfindən verilənləri müəyyən etməyə yönəlib, məlumat bazası hazırlanarkən. Onlar adətən azdır, sərt olurlar və əsas istifadə sahəsi — məlumatların normallaşdırılması və münasibət sxeminin dizaynıdır.

İkinci tip — «gizli» məlumatları təmsil edən asılılıqlardır və atributlar arasında əvvəllər bilinməyən əlaqələrdir. Yəni belə asılılıqlar layihələndirilərkən düşünülməyib, artıq mövcud məlumat bazası üçün tapılır ki, sonra aşkar edilmiş FZ-lərin topluluğuna əsaslanaraq saxlanılan məlumatlar haqqında bəzi nəticələr çıxarılsın. Biz elə belə asılılıqlarla işləyirik. Onlarla fərqli axtarış metodları və bu metodlara əsaslanan alqoritmlərlə bağlı geniş bir data mining sahəsi var. Gəlin, tapılmış funksional asılılıqların (düzgün və ya yaxın) müəyyən məlumatlarda necə faydalı ola biləcəyinə baxaq.

Bugün asılılıqların əsas tətbiq sahələrindən biri məlumatların təmizlənməsidir. Bu, «çirkli məlumatların» aşkar edilməsi və sonradan düzəldilməsi proseslərinin hazırlanmasını nəzərdə tutur. «Çirkli məlumatların» aydın nümunələri arasında dublikatlar, məlumatlardakı xətalar və yaxud yazı səhvləri, itirilmiş dəyərlər, köhnəlmiş məlumatlar, artıq boşluqlar və s. var.

Məlumatdakı xəta nümunəsi:

Məlumatlardakı dublikat nümunəsi:

Məsələn, bir cədvəlimiz və yerinə yetirilməli olan bir sıra FZ var. Bu halda məlumatların təmizlənməsi, məlumatların FZ-lərin düzgün olması üçün dəyişdirilməsi deməkdir. Bu zaman dəyişikliklərin sayı minimum olmalıdır (bu prosedur üçün xüsusi alqoritmlər mövcuddur, bunlara bu məqalədə diqqət yetirməyəcəyik). Aşağıda belə bir məlumat transformasiyasına bir nümunə təqdim olunur. Solda, açıq şəkildə tələb olunan FZ-lərin yerinə yetirilmədiyi orijinal əlaqə, sağda isə dəyişdirilmiş dəyərləri göstərən yaşıl hüceyrələrlə yenilənmiş əlaqə təqdim olunur. Belə bir prosedur keçirildikdən sonra tələb olunan asılılıqlar qorunmuşdur.

Başqa bir populyar tətbiq sahəsi verilənlər bazasının dizaynıdır. Burada normal formaların və normalizasiyanın xatırlanması vacibdir. Normalizasiya, bir əlaqəni müəyyən bir tələblər toplusuna uyğunlaşdırmaq prosesidir, hər biri öz şəkildə normal forma tərəfindən müəyyən edilir. Müxtəlif normal formanı tələb edən tələbləri izah etməyəcəyik (bu, yeni başlayanlar üçün verilənlər bazası kursunu əhatə edən istənilən kitabda edilir), yalnız qeyd edək ki, hər biri funksional asılılıq anlayışından öz cəhətləri ilə istifadə edir. Axı FZ-nin mahiyyəti etibarilə, verilənlər bazası dizaynında nəzərə alınan bütövlüyün təminatıdır (bu məsələdə FZ bəzən super açarlar adlandırılır).

Aşağıdakı şəkildə dörd normal formanı tətbiqini nəzərdən keçirək. Xatırladaq ki, Boyce-Codd normal forması üçüncü formadan daha sərtdir, lakin dördüncü forma ilə müqayisədə daha az sərtdir. Sonuncunu hələ nəzərdən keçirmirik, çünki onun tətbiqi çoxlu asılılıqları başa düşməyi tələb edir, bu məqalədə bizi maraqlandırmır.

Asılılıqların tətbiq edildiyi başqa bir sahə, sadə bayes təsnifatçısının qurulması, əhəmiyyətli xüsusiyyətlərin seçilməsi və regresiya modelinin təkrar parametrizasiyası kimi xüsusiyyətlər məkanının ölçüsünün azaldılmasıdır. Orijinal məqalələrdə bu problem artıq xüsusiyyətlərin artıq olması (feature redundancy) və uyğunluğu (feature relevancy) adlanır [5, 6] və verilənlər bazası anlayışlarının aktiv istifadəsi ilə həll olunur. Bu cür işlərin meydana çıxması ilə, bu gün verilənlər bazası, analitika və yuxarıda sadalanan optimallaşdırma problemlərinin həyata keçirilməsini bir alətə birləşdirmək üçün həllərə tələbin olduğunu söyləyə bilərik [7, 8, 9].

Məlumatlar dəstində FZ-ləri axtarmaq üçün bir çox alqoritm mövcuddur (həm müasir, həm də o qədər də müasir olmayan). Bu cür alqoritmlər üç qrupa bölünə bilər:

• Alqoritmlər, algebrik ştatları aşmaq üçün istifadə olunan (Lattice traversal algorithms)
• Dəyərlərin uyğun qiymətlərini axtaran alqoritmlər (Difference- and agree-set algorithms)
• Cütlərlə müqayisələrə əsaslanan alqoritmlər (Dependency induction algorithms)

Hər bir alqoritm tipinin qısa təsviri aşağıdakı cədvəldə təqdim edilmişdir:


Bu təsnifat haqqında daha ətraflı oxumaq olar [4]. Aşağıda hər bir tip üçün alqoritm nümunələri verilmişdir:

Hal-hazırda funksional asılılıqları axtaran bir neçə yanaşmanı özündə birləşdirən yeni alqoritmlər meydana çıxmaqdadır. Belə alqoritmlərə Pyro [2] və HyFD [3] misal ola bilər. Onların işləmə prinsipləri bu məqalələrin növbəti yazılarında müzakirə olunacaq. Bu məqalədə yalnız asılılıq aşkarlama texnikalarını başa düşmək üçün zəruri olan əsas anlayışları və teoremi izah edəcəyik.

Sadə bir şeylə başlayırıq — second tip alqoritmlərdə istifadə edilən difference-set və agree-set. Difference-set, dəyəri ilə uyğun gəlməyən tuple-lərdən ibarət bir kümedir, agree-set isə əksinə — dəyəri ilə uyğun gələn tuple-lərdir. Bu halda, yalnız asılılığın sol tərəfini nəzərdən keçiririk.

Yuxarıda qeyd olunan mühüm anlayışlardan biri algebrik lattadır. Çünki bir çox müasir alqoritmlər bu anlayışla işləyir, bunun nə olduğunu anlamaq vacibdir.

Lattanı təqdim etmək üçün qismən sıralanmış kümenin (partially ordered set, qısaca — poset) tərifinə ehtiyac var.

Tərif 2. S kümesi, ${≤}$ ikiqat münasibətinə görə qismən sıralanmışdır deyilir, əgər hər a, b, c ∈ S üçün aşağıdakı xassələr təmin olunursa:

1. Refleksivlik, yəni ${a ≤ a}$
2. Antisimetriya, yəni, əgər ${a ≤ b}$ və ${b ≤ a}$ isə, onda ${a = b}$
3. Transitivlik, yəni, ${a ≤ b}$ və ${b ≤ c}$ üçün ${a ≤ c}$ olmalıdır

Bu münasibət (səbrsiz) qismən sıralama münasibəti adlanır, öz növbəsində bu küme — qismən sıralanmış kümedir. Rəsmi işarə: ⟨S, ${≤}$⟩.

Qismən sıralanmış kümenin ən sadə misalı olaraq N təbii ədədlərin kutusunu ${≤}$ adlanan adi sıralama münasibəti ilə götürə bilərik. Bütün vacib aksiyaların yerinə yetirilməsini asanlıqla yoxlamaq olar.

Daha ətraflı bir misal. {1, 2, 3} kümesinin bütün alt kümləri, daxilolma münasibəti ilə sıralanmışdır. Həqiqətən, bu münasibət qismən sıralamanın bütün tələblərinə cavab verir, buna görə də ⟨P ({1, 2, 3}), ⊆⟩ — qismən sıralanmış bir kümedir. Aşağıdakı şəkil bu kümenin strukturunu təsvir edir: əgər bir elementdən digərinə oxlar arasında keçid varsa, deməli, onlar sıralama münasibətindədir.

Bizə daha iki sadə tərif lazımdır — supremum (supremum) və infimum (infimum).

Tərif 3. Tuta ⟨S, ⩽⟩ — qismən sıralanmış bir çoxluq, A ⊆ S. A-nın üst sərhədi — S-də olan u ∈ S elementi ki, ∀x ∈ S: x ⩽ u. U — S-in bütün üst sərhədlərinin çoxluğudur. Əgər U-da ən kiçik bir element varsa, o, sup A olaraq adlandırılır.

Eynilə dəqiq aşağı sərhəd anlayışı təqdim olunur.

Tərif 4. Tuta ⟨S, ⩽⟩ — qismən sıralanmış bir çoxluq, A ⊆ S. A-nın aşağı sərhədi — S-də olan l ∈ S elementi ki, ∀x ∈ S: l ⩽ x. L — S-in bütün aşağı sərhədlərinin çoxluğudur. Əgər L-də ən böyük bir element varsa, o, inf A olaraq adlandırılır.

Yuxarıda verilmiş qismən sıralanmış çoxluğu ⟨P ({1, 2, 3}), ⊆⟩ nümunə olaraq götürək və onun içində sup və inf i tapaq:

İndi algebrik lattığın tərifini vermək olar.

Tərif 5. Tuta ⟨P, ⩽⟩ — qismən sıralanmış bir çoxluq, belə ki, hər ikili alt çoxluğun dəqiq üst və aşağı sərhədləri var. Onda P algebrik latta adlanır. Bu halda sup{x, y} kimi x ∨ y, inf {x, y} isə x ∧ y kimi yazılır.

Gəlin, iş nümunəmiz ⟨P ({1, 2, 3}), ⊆⟩-nin latta olduğunu yoxlayaq. Həqiqətən, hər hansı a, b ∈ P ({1, 2, 3}) üçün a∨b = a∪b, a∧b = a∩b-dir. Məsələn, {1, 2} və {1, 3} çoxluqlarını götürüb, onların inf və sup-ni tapaq. Əgər onları kəsişdirsək, {1} çoxluğunu alırıq ki, bu da inf olacaq. Sup isə onların birləşməsi — {1, 2, 3} olacaq.

FZ aşkarlama alqoritmlərində axtarış sahəsi adətən latta şəklində təqdim olunur, burada bir elementdən ibarət çoxluqlar (oxu axtarış lattaının birinci səviyyəsi, burada asılılıqların sol tərəfi bir atributdan ibarətdir) hər bir atributu göstərir.
İlk əvvəl ∅ → şəklində asılılıqlar nəzərdən keçirilir. Tək atribut. Bu addım, hansı atributların birincil açar olduğunu müəyyən etməyə imkan tanıyır (belə atributlar üçün determinantlar olmur, buna görə də sol tərəf boştur). Daha sonra belə alqoritmlər lattada yuxarıya doğru hərəkət edir. Eyni zamanda, latta tam olaraq keçilə biləcəyini qeyd etmək lazımdır, yəni əgər istənilən sol tərəfin maksimal ölçüsünü ötürsəniz, o zaman belə bir ölçülü səviyyədən daha irəliləməyəcək.

Aşağıdakı şəkil FZ tapma vəzifəsində algebrik lattanın necə istifadə oluna biləcəyini göstərir. Burada hər bir kənar (X, XY) asılılığı təmsil edir. X → YMəsələn, birinci səviyyəni keçdikdə asılılığın saxlandığını bilirik A → B (bunu vertikallar arasında yaşıl əlaqə ilə göstərək A və B). Deməli, latta yuxarıya doğru irəlilədikdə, asılılığı yoxlamağa ehtiyacımız olmayacaq A, C → B, çünki o, artıq minimal olmayacaq. Eynilə, əgər asılılıq saxlanırsa, onu yoxlamazdıq C → B.

Bundan əlavə, adətən, bütün müasir FZ axtarış alqoritmləri, paritisi (mənbədə - stripped partition [1]) kimi bir məlumat strukturu istifadə edir. Paritisin rəsmi tərifi belədir:

Tərif 6. Tutaq ki, X ⊆ R - r münasibəti üçün atributlar toplusudur. Klaster, eyni X dəyərinə sahib olan r tərtiblərinin indeksləri toplusunu ifadə edir, yəni c(t) = {i|ti[X] = t[X]}. Paritisi, tək uzunluqda klasterləri istisna edən klasterlər toplusudur:

Sadə sözlə, atribut üçün paritisi X bir-birinin eyni dəyərləri olan sıra nömrələrini əhatə edən siyahılar toplusu kimi nəzərdən keçirilir X. Müasir ədəbiyyatda paritiləri təmsil edən struktur position list index (PLI) adlanır. Tək uzunluqda klasterlər PLI-nin sıxılma məqsədilə istisna edilir, çünki bunlar unikal dəyərə sahib olan tək qeyd nömrəsini ehtiva edir ki, bu da həmişə asanlıqla təyin oluna bilər.

Gəlin bir misal nəzərdən keçirək. Həmin xəstə cədvəlinə qayıdaq və sütunlar üçün paritilər yaradaq Pasient və Cins (solda yeni bir sütun ortaya çıxdı, burada cədvəldəki sıra nömrələri qeyd olunub):

Bu halda, tərifə uyğun olaraq, sütun üçün paritisi Pasient əslində boş olacaq, çünki tək klasterlər paritidən istisna edilir.

Paritiləri bir neçə atribut üzrə əldə etmək mümkündür. Bu məqsədlə iki yol var: cədvəldən keçərək bütün lazım olan atributlara uyğun bir pariti yaratmaq, ya da alt atributlar dəsti üzrə paritilərin kəsişməsi əməliyyatı ilə yarada bilərik. FZ axtarış alqoritmləri ikinci variantdan istifadə edir.

Sadə sözlə, məsələn, sütunlar üçün paritiləri əldə etmək üçün ABC, AC paritiləri (və ya hər hansı digər kəsişməyən alt dəst) götürülə bilər və bunlar bir-biri ilə kəsişdirilə bilər. İki paritinin kəsişməsi əməliyyatı, hər iki paritidə ən uzun klasterləri ayırır. AC və B (və ya hər hansı digər kəsişməyən alt dəst) götürülə bilər və bunlar bir-biri ilə kəsişdirilə bilər. İki paritinin kəsişməsi əməliyyatı, hər iki paritidə ən uzun klasterləri ayırır.

Gəlin bir misala nəzər salaq:

Birinci halda biz boş paritini əldə etdik. Cədvələ diqqət yetirsək, həqiqətən də, iki atribut üzrə eyni dəyərlər yoxdur. Lakin təsadüfən dəyişdirdiyimiz cədvəl (sağdakı halda) artıq boş olmayan kəsişmə verəcəkdir. Burada 1 və 2-nin sıraları həqiqətən də atributlar üzrə bənzər dəyərləri ehtiva edir. Cins və Həkim.

Daha sonra, paritinin ölçüsü kimi bir anlayışa ehtiyacımız olacaq. Rəsmi olaraq:

Sadə desək, paritinin ölçüsü, paritiyə daxil olan klasterlərin sayını ifadə edir (unutmuruq ki, tək klasterlər paritiyə daxil olmur!):

İndi biz bir paritinin verildiyi durumda asılılığın var olub olmadığını müəyyənləşdirməyə imkan verən açar lemmanı müəyyən edə bilərik:

Lemma 1. A, B → C asılılığı, yalnız və yalnız

Lemaya əsasən, asılılığın var olub olmadığını müəyyən etmək üçün dörd mərhələ yerinə yetirilməlidir:

1. Solğun asılılığın sol hissəsi üçün partlayışı hesablayın
2. Solğun asılılığın sağ hissəsi üçün partlayışı hesablayın
3. Birinci və ikinci addımın hasilini hesablayın
4. Birinci və üçüncü addımda əldə edilən partlayışların ölçülərini müqayisə edin

Aşağıda, verilmiş lemmada asılılığın tutulub-tutulmadığını yoxlamaq üçün bir nümunə təqdim edilir:

Bu məqalədə biz funksional asılılıq, yaxın funksional asılılıq kimi anlayışları müzakirə etdik, onların harada tətbiq olunduğunu və hansı FZ axtarış alqoritmlərinin mövcud olduğunu araşdırdıq. Həmçinin, müasir FZ axtarış alqoritmlərində aktiv şəkildə istifadə olunan əsas, lakin vacib anlayışları da ətraflı şəkildə izah etdik.

Ədəbiyyat referansları:

1. Huhtala Y. və başqaları. TANE: funksional və yaxın asılılıqları aşkar etmək üçün effektiv alqoritm // The computer journal. – 1999. – V. 42. – №. 2. – S. 100-111.
2. Kruse S., Naumann F. Yaxın asılılıqları effektiv aşkar etmək // VLDB Endowment konfransının materialları. – 2018. – V. 11. – №. 7. – S. 759-772.
3. Papenbrock T., Naumann F. Funksional asılılığın aşkar edilməsi üçün hibrid yanaşma // 2016-cı il Beynəlxalq Məlumat İdarəsi Konfransının materialları. – ACM, 2016. – S. 821-833.
4. Papenbrock T. və başqaları. Funksional asılılığın aşkar edilməsi: Yeddi alqoritmin eksperimental qiymətləndirilməsi // VLDB Endowment konfransının materialları. – 2015. – V. 8. – №. 10. – S. 1082-1093.
5. Kumar A. və başqaları. Birləşməliyik, yoxsa birləşməməliyik?: Xüsusiyyət seçməzdən əvvəl bir daha düşünün // 2016-cı il Beynəlxalq Məlumat İdarəsi Konfransının materialları. – ACM, 2016. – S. 19-34.
6. Abo Khamis M. və başqaları. Sparse tensors ilə inzibatda öyrənmə // 37-ci ACM SIGMOD-SIGACT-SIGAI Məlumat Bazası Sistemləri Prinsipləri Simpoziumu. – ACM, 2018. – S. 325-340.
7. Hellerstein J. M. və başqaları. MADlib analitika kitabxanası: və ya MAD bacarıqları, SQL // VLDB Endowment konfransının materialları. – 2012. – V. 5. – №. 12. – S. 1700-1711.
8. Qin C., Rusu F. Terascale paylanmış gradient eniş optimallaşdırmaları üçün spekulyativ yaxınlaşmalar // Datalar üzərində analitika üzrə IV Seminar. – ACM, 2015. – S. 1.
9. Meng X. və başqaları. Mllib: apache spark-da maşın öyrənmə // Maşın Öyrənmə Tədqiqatı Jurnalı. – 2016. – V. 17. – №. 1. – S. 1235-1241.

Məqalənin müəllifləri: Anastasiya Birillo, JetBrains Araşdırma, , CS mərkəzinin tələbəsi və Nikita Bobrov, JetBrains Araşdırma

Mənbə: habr.com