ფუნქციური დამოკიდებულებების შესავალი

ამ სტატიაში ვისაუბრებთ მონაცემთა ბაზებში ფუნქციონალურ დამოკიდებულებებზე - რა არის ისინი, სად გამოიყენება და რა ალგორითმები არსებობს მათ მოსაძებნად.

ჩვენ განვიხილავთ ფუნქციურ დამოკიდებულებებს რელაციური მონაცემთა ბაზების კონტექსტში. ძალიან უხეშად რომ ვთქვათ, ასეთ მონაცემთა ბაზებში ინფორმაცია ინახება ცხრილების სახით. შემდეგი, ჩვენ ვიყენებთ მიახლოებით ცნებებს, რომლებიც არ არის ურთიერთშემცვლელი მკაცრ რელაციურ თეორიაში: ჩვენ თვითონ ცხრილს დავარქმევთ ურთიერთობას, სვეტებს - ატრიბუტებს (მათი სიმრავლე - ურთიერთობის სქემა) და მწკრივის მნიშვნელობების სიმრავლეს ატრიბუტების ქვეჯგუფზე. - ტუპი.

მაგალითად, ზემოთ მოცემულ ცხრილში, (ბენსონი, M, M ორგანო) არის ატრიბუტების ტოპი (პაციენტი, პავლე, ექიმი).
უფრო ოფიციალურად, ეს ასე იწერება: [პაციენტი, სქესი, ექიმი] = (ბენსონი, M, M ორგანო).
ახლა ჩვენ შეგვიძლია შემოვიტანოთ ფუნქციური დამოკიდებულების კონცეფცია (FD):

განმარტება 1. კავშირი R აკმაყოფილებს ფედერალურ კანონს X → Y (სადაც X, Y ⊆ R) თუ და მხოლოდ თუ რომელიმე ტოპისთვის , ∈ R მოქმედებს: თუ [X] = [X], მაშინ [Y] = [Y]. ამ შემთხვევაში, ჩვენ ვამბობთ, რომ X (განმსაზღვრელი, ან ატრიბუტების განმსაზღვრელი ნაკრები) ფუნქციურად განსაზღვრავს Y (დამოკიდებულ სიმრავლეს).

სხვა სიტყვებით რომ ვთქვათ, ფედერალური კანონის არსებობა X → Y ნიშნავს, რომ თუ ჩვენ გვაქვს ორი ტოპი R და ისინი ემთხვევა ატრიბუტებს X, მაშინ ისინი დაემთხვევა ატრიბუტებში Y.
ახლა კი, წესრიგში. მოდით შევხედოთ ატრიბუტებს პაციენტი и Paul რისთვისაც გვინდა გავარკვიოთ არის თუ არა მათ შორის დამოკიდებულებები. ატრიბუტების ასეთი ნაკრებისთვის შეიძლება არსებობდეს შემდეგი დამოკიდებულებები:

1. პაციენტი → სქესი
2. სქესი → პაციენტი

როგორც ზემოთ იყო განსაზღვრული, იმისათვის, რომ პირველი დამოკიდებულება შენარჩუნდეს, თითოეული უნიკალური სვეტის მნიშვნელობა პაციენტი მხოლოდ ერთი სვეტის მნიშვნელობა უნდა ემთხვეოდეს Paul. და მაგალითად ცხრილისთვის ეს მართლაც ასეა. თუმცა, ეს არ მუშაობს საპირისპირო მიმართულებით, ანუ მეორე დამოკიდებულება არ არის დაკმაყოფილებული და ატრიბუტი Paul არ არის განმსაზღვრელი პაციენტი. ანალოგიურად, თუ ავიღებთ დამოკიდებულებას ექიმი → პაციენტი, ხედავთ, რომ დარღვეულია, რადგან მნიშვნელობა რობინ ამ ატრიბუტს აქვს რამდენიმე განსხვავებული მნიშვნელობა - ელისი და გრეჰემი.

ამრიგად, ფუნქციური დამოკიდებულებები შესაძლებელს ხდის ცხრილის ატრიბუტების სიმრავლეს შორის არსებული ურთიერთობების დადგენას. აქედან მოყოლებული განვიხილავთ ყველაზე საინტერესო კავშირებს, უფრო სწორად ასეთებს X → Yრა არიან ისინი:

• არატრივიალური, ანუ დამოკიდებულების მარჯვენა მხარე არ არის მარცხენას ქვეჯგუფი (Y ̸⊆ X);
• მინიმალური, ანუ ასეთი დამოკიდებულება არ არსებობს Z → Yრომ Z ⊂ X.

ამ მომენტამდე განხილული დამოკიდებულებები მკაცრი იყო, ანუ ისინი არ ითვალისწინებდნენ რაიმე დარღვევას მაგიდაზე, მაგრამ მათ გარდა, არის ისეთებიც, რომლებიც იძლევა გარკვეულ შეუსაბამობას ტუპლების მნიშვნელობებს შორის. ასეთი დამოკიდებულებები მოთავსებულია ცალკეულ კლასში, რომელსაც ეწოდება მიახლოებითი და ნებადართულია დარღვეულის გარკვეული რაოდენობის ტოპებისთვის. ეს თანხა რეგულირდება შეცდომის მაქსიმალური ინდიკატორით emax. მაგალითად, შეცდომის მაჩვენებელი = 0.01 შეიძლება ნიშნავს, რომ დამოკიდებულება შეიძლება დაირღვეს ატრიბუტების განხილულ კომპლექტზე არსებული ტოპების 1%-ით. ანუ 1000 ჩანაწერისთვის მაქსიმუმ 10 ტუპლს შეუძლია დაარღვიოს ფედერალური კანონი. ჩვენ განვიხილავთ ოდნავ განსხვავებულ მეტრიკას, რომელიც დაფუძნებულია წყვილ-წყვილად შედარებული ტოტების სხვადასხვა მნიშვნელობებზე. დამოკიდებულებისთვის X → Y დამოკიდებულებაზე r ითვლება ასე:

მოდით გამოვთვალოთ შეცდომა ექიმი → პაციენტი ზემოთ მოყვანილი მაგალითიდან. ჩვენ გვაქვს ორი ტოპი, რომელთა მნიშვნელობები განსხვავდება ატრიბუტის მიხედვით პაციენტი, მაგრამ ემთხვევა ექიმი: [ექიმი, პაციენტი] = (რობინი, ელისი) და [ექიმი, პაციენტი] = (რობინი, გრეჰემი). შეცდომის განმარტების შემდეგ, ჩვენ უნდა გავითვალისწინოთ ყველა კონფლიქტური წყვილი, რაც ნიშნავს რომ იქნება ორი მათგანი: (, ) და მისი საპირისპირო (, ). მოდით ჩავანაცვლოთ იგი ფორმულაში და მივიღოთ:

ახლა შევეცადოთ ვუპასუხოთ კითხვას: "რატომ არის ეს ყველაფერი?" სინამდვილეში, ფედერალური კანონები განსხვავებულია. პირველი ტიპი არის ის დამოკიდებულებები, რომლებსაც განსაზღვრავს ადმინისტრატორი მონაცემთა ბაზის დიზაინის ეტაპზე. ისინი, როგორც წესი, ცოტანი არიან, მკაცრი და მთავარი პროგრამაა მონაცემთა ნორმალიზაცია და ურთიერთდამოკიდებულების სქემის დიზაინი.

მეორე ტიპი არის დამოკიდებულებები, რომლებიც წარმოადგენენ „ფარულ“ მონაცემებს და ატრიბუტებს შორის მანამდე უცნობ კავშირებს. ანუ, ასეთი დამოკიდებულებები არ იყო გააზრებული დიზაინის დროს და ისინი ნაპოვნია არსებული მონაცემთა ნაკრებისთვის, ასე რომ, მოგვიანებით, მრავალი გამოვლენილი ფედერალური კანონის საფუძველზე, შეიძლება გაკეთდეს ნებისმიერი დასკვნა შენახული ინფორმაციის შესახებ. სწორედ ამ დამოკიდებულებებთან ვმუშაობთ. მათ ეხება მონაცემთა მოპოვების მთელი სფერო, სხვადასხვა საძიებო ტექნიკით და მათ საფუძველზე აგებული ალგორითმებით. მოდით გაერკვნენ, თუ როგორ შეიძლება იყოს სასარგებლო აღმოჩენილი ფუნქციური დამოკიდებულებები (ზუსტი ან სავარაუდო) ნებისმიერ მონაცემში.

დღეს, დამოკიდებულების ერთ-ერთი მთავარი აპლიკაცია მონაცემთა გაწმენდაა. ის მოიცავს პროცესების შემუშავებას „ბინძური მონაცემების“ იდენტიფიცირებისთვის და შემდეგ მათი გამოსწორებისთვის. „ბინძური მონაცემების“ თვალსაჩინო მაგალითებია დუბლიკატები, მონაცემების შეცდომები ან ბეჭდვითი შეცდომები, დაკარგული მნიშვნელობები, მოძველებული მონაცემები, დამატებითი სივრცეები და ა.შ.

მონაცემთა შეცდომის მაგალითი:

მონაცემების დუბლიკატების მაგალითი:

მაგალითად, ჩვენ გვაქვს ცხრილი და ფედერალური კანონების ნაკრები, რომელიც უნდა შესრულდეს. მონაცემთა გაწმენდა ამ შემთხვევაში გულისხმობს მონაცემების შეცვლას ისე, რომ ფედერალური კანონები სწორი გახდეს. ამ შემთხვევაში ცვლილებების რაოდენობა მინიმალური უნდა იყოს (ამ პროცედურას აქვს თავისი ალგორითმები, რაზეც ამ სტატიაში ყურადღებას არ გავამახვილებთ). ქვემოთ მოცემულია ასეთი მონაცემთა ტრანსფორმაციის მაგალითი. მარცხნივ არის ორიგინალური ურთიერთობა, რომელშიც, ცხადია, აუცილებელი FL-ები არ არის დაკმაყოფილებული (წითლად არის მონიშნული ერთ-ერთი FL-ის დარღვევის მაგალითი). მარჯვნივ არის განახლებული ურთიერთობა, მწვანე უჯრედები აჩვენებს შეცვლილ მნიშვნელობებს. ამ პროცედურის შემდეგ დაიწყო საჭირო დამოკიდებულებების შენარჩუნება.

კიდევ ერთი პოპულარული პროგრამა არის მონაცემთა ბაზის დიზაინი. აქ ღირს ნორმალური ფორმების გახსენება და ნორმალიზება. ნორმალიზაცია არის ურთიერთობის შესაბამისობაში მოყვანის პროცესი გარკვეული მოთხოვნების კომპლექტთან, რომელთაგან თითოეული განსაზღვრულია ნორმალური ფორმით თავისებურად. ჩვენ არ აღვწერთ სხვადასხვა ნორმალური ფორმის მოთხოვნებს (ეს კეთდება დამწყებთათვის მონაცემთა ბაზის კურსის ნებისმიერ წიგნში), მაგრამ მხოლოდ აღვნიშნავთ, რომ თითოეული მათგანი იყენებს ფუნქციური დამოკიდებულების კონცეფციას თავისებურად. ყოველივე ამის შემდეგ, FL-ები არსებითად მთლიანობის შეზღუდვებია, რომლებიც მხედველობაში მიიღება მონაცემთა ბაზის შექმნისას (ამ ამოცანის კონტექსტში, FL-ებს ზოგჯერ სუპერკლავებსაც უწოდებენ).

განვიხილოთ მათი განაცხადი ოთხი ნორმალური ფორმისთვის ქვემოთ მოცემულ სურათზე. შეგახსენებთ, რომ ბოის-კოდის ნორმალური ფორმა უფრო მკაცრია ვიდრე მესამე ფორმა, მაგრამ ნაკლებად მკაცრი ვიდრე მეოთხე. ამ უკანასკნელს ჯერჯერობით არ განვიხილავთ, რადგან მისი ფორმულირება მოითხოვს მრავალმნიშვნელოვანი დამოკიდებულებების გაგებას, რაც ჩვენთვის საინტერესო არ არის ამ სტატიაში.

კიდევ ერთი სფერო, რომელშიც დამოკიდებულებებმა იპოვეს მათი გამოყენება, არის ფუნქციების სივრცის განზომილების შემცირება ამოცანები, როგორიცაა გულუბრყვილო Bayes კლასიფიკატორის შექმნა, მნიშვნელოვანი მახასიათებლების იდენტიფიცირება და რეგრესიის მოდელის რეპარამეტრიზაცია. თავდაპირველ სტატიებში ამ ამოცანას ეწოდება ზედმეტი და მახასიათებლის შესაბამისობის განსაზღვრა [5, 6] და ის მოგვარებულია მონაცემთა ბაზის კონცეფციების აქტიური გამოყენებით. ასეთი სამუშაოების მოსვლასთან ერთად, შეგვიძლია ვთქვათ, რომ დღეს არის მოთხოვნა გადაწყვეტილებებზე, რომლებიც საშუალებას გვაძლევს გავაერთიანოთ მონაცემთა ბაზა, ანალიტიკა და ზემოაღნიშნული ოპტიმიზაციის პრობლემების განხორციელება ერთ ინსტრუმენტად [7, 8, 9].

არსებობს მრავალი ალგორითმი (როგორც თანამედროვე, ასევე არც ისე თანამედროვე) ფედერალური კანონების საძიებლად მონაცემთა ნაკრებში.ასეთი ალგორითმები შეიძლება დაიყოს სამ ჯგუფად:

• ალგორითმები ალგებრული გისოსების გადაკვეთის გამოყენებით (ლატის გადაკვეთის ალგორითმები)
• ალგორითმები, რომლებიც დაფუძნებულია შეთანხმებული მნიშვნელობების ძიებაზე (განსხვავებების და შეთანხმების დადგენის ალგორითმები)
• ალგორითმები დაფუძნებული წყვილთა შედარებებზე (დამოკიდებულების ინდუქციური ალგორითმები)

თითოეული ტიპის ალგორითმის მოკლე აღწერა მოცემულია ქვემოთ მოცემულ ცხრილში:


შეგიძლიათ მეტი წაიკითხოთ ამ კლასიფიკაციის შესახებ [4]. ქვემოთ მოცემულია ალგორითმის მაგალითები თითოეული ტიპისთვის:

ამჟამად ჩნდება ახალი ალგორითმები, რომლებიც აერთიანებს რამდენიმე მიდგომას ფუნქციონალური დამოკიდებულებების მოსაძებნად. ასეთი ალგორითმების მაგალითებია Pyro [2] და HyFD [3]. მათი მუშაობის ანალიზი მოსალოდნელია ამ სერიის შემდეგ სტატიებში. ამ სტატიაში ჩვენ განვიხილავთ მხოლოდ ძირითად ცნებებსა და ლემას, რომლებიც აუცილებელია დამოკიდებულების გამოვლენის ტექნიკის გასაგებად.

დავიწყოთ უბრალო ერთით - სხვაობა-და ვეთანხმები სიმრავლით, რომელიც გამოიყენება მეორე ტიპის ალგორითმებში. განსხვავება-სიმრავლე არის ტოპების ერთობლიობა, რომლებსაც არ აქვთ ერთი და იგივე მნიშვნელობები, ხოლო თანხმობა-სიმრავლე, პირიქით, არის ტოპები, რომლებსაც აქვთ იგივე მნიშვნელობები. აღსანიშნავია, რომ ამ შემთხვევაში ჩვენ განვიხილავთ მხოლოდ დამოკიდებულების მარცხენა მხარეს.

კიდევ ერთი მნიშვნელოვანი კონცეფცია, რომელიც ზემოთ შეგვხვდა, არის ალგებრული გისოსი. ვინაიდან ბევრი თანამედროვე ალგორითმი მუშაობს ამ კონცეფციაზე, ჩვენ უნდა გვქონდეს წარმოდგენა იმის შესახებ, თუ რა არის ეს.

გისოსის ცნების დასანერგად საჭიროა განვსაზღვროთ ნაწილობრივ მოწესრიგებული ნაკრები (ან ნაწილობრივ მოწესრიგებული ნაკრები, შემოკლებით პოსეტი).

განმარტება 2. ნათქვამია, რომ S სიმრავლე ნაწილობრივ დალაგებულია ორობითი მიმართებით ⩽, თუ ყველა a, b, c ∈ S დაკმაყოფილებულია შემდეგი თვისებები:

1. რეფლექსურობა, ანუ a ⩽ a
2. ანტისიმეტრია, ანუ თუ a ⩽ b და b ⩽ a, მაშინ a = b
3. ტრანზიტულობა, ანუ a ⩽ b და b ⩽ c გამოდის, რომ a ⩽ c

ასეთ მიმართებას ეწოდება (ფხვიერი) ნაწილობრივი წესრიგის მიმართება, ხოლო თავად სიმრავლეს ეწოდება ნაწილობრივ მოწესრიგებული სიმრავლე. ფორმალური აღნიშვნა: ⟨S, ⩽⟩.

როგორც ნაწილობრივ მოწესრიგებული სიმრავლის უმარტივესი მაგალითი, შეგვიძლია ავიღოთ ყველა ნატურალური რიცხვის N სიმრავლე ჩვეულებრივი რიგის მიმართებით ⩽. მარტივია იმის შემოწმება, რომ ყველა საჭირო აქსიომა დაკმაყოფილებულია.

უფრო მნიშვნელოვანი მაგალითი. განვიხილოთ ყველა ქვესიმრავლეების სიმრავლე {1, 2, 3}, დალაგებული ⊆ ჩართვის მიმართებით. მართლაც, ეს მიმართება აკმაყოფილებს ყველა ნაწილობრივი შეკვეთის პირობას, ამიტომ ⟨P ({1, 2, 3}), ⊆⟩ არის ნაწილობრივ მოწესრიგებული ნაკრები. ქვემოთ მოყვანილი სურათი გვიჩვენებს ამ ნაკრების სტრუქტურას: თუ ერთი ელემენტი ისრებით შეიძლება მიაღწიოს მეორე ელემენტს, მაშინ ისინი წესრიგში არიან.

დაგვჭირდება კიდევ ორი ​​მარტივი განსაზღვრება მათემატიკის სფეროდან - supremum და infimum.

განმარტება 3. მოდით ⟨S, ⩽⟩ იყოს ნაწილობრივ მოწესრიგებული სიმრავლე, A ⊆ S. A-ს ზედა ზღვარი არის u ∈ S ელემენტი, რომ ∀x ∈ S: x ⩽ u. მოდით, U იყოს S-ის ყველა ზედა საზღვრების სიმრავლე. თუ U-ში არის უმცირესი ელემენტი, მაშინ მას უწოდებენ supremum და აღინიშნება sup A.

ანალოგიურად არის შემოღებული ზუსტი ქვედა ზღვრის კონცეფცია.

განმარტება 4. მოდით ⟨S, ⩽⟩ იყოს ნაწილობრივ მოწესრიგებული სიმრავლე, A ⊆ S. A-ს ინფიმუმი არის ელემენტი l ∈ S ისეთი, რომ ∀x ∈ S: l ⩽ x. ვთქვათ L არის S-ის ყველა ქვედა საზღვრების სიმრავლე. თუ L-ში არის ყველაზე დიდი ელემენტი, მაშინ მას infimum ეწოდება და აღინიშნება როგორც inf A.

მაგალითისთვის განვიხილოთ ზემოაღნიშნული ნაწილობრივ მოწესრიგებული სიმრავლე ⟨P ({1, 2, 3}), ⊆⟩ და იპოვეთ მასში უმაღლესი და ინფიმუმი:

ახლა ჩვენ შეგვიძლია ჩამოვაყალიბოთ ალგებრული გისოსის განმარტება.

განმარტება 5. მოდით ⟨P,⩽⟩ იყოს ნაწილობრივ მოწესრიგებული სიმრავლე ისე, რომ ყოველ ორ ელემენტიან ქვესიმრავლეს ჰქონდეს ზედა და ქვედა ზღვარი. მაშინ P-ს ეწოდება ალგებრული გისოსი. ამ შემთხვევაში, sup{x, y} იწერება როგორც x ∨ y, ხოლო inf {x, y} როგორც x ∧ y.

მოდით შევამოწმოთ, რომ ჩვენი სამუშაო მაგალითი ⟨P ({1, 2, 3}), ⊆⟩ არის გისოსი. მართლაც, ნებისმიერი a, b ∈ P ({1, 2, 3}), a∨b = a∪b და a∧b = a∩b. მაგალითად, განიხილეთ სიმრავლეები {1, 2} და {1, 3} და იპოვეთ მათი infimum და supremum. თუ მათ გადავკვეთთ, მივიღებთ სიმრავლეს {1}, რომელიც იქნება infimum. ჩვენ ვიღებთ უზენაესს მათი გაერთიანებით - {1, 2, 3}.

ფიზიკური პრობლემების იდენტიფიცირების ალგორითმებში საძიებო სივრცე ხშირად წარმოდგენილია გისოსის სახით, სადაც ერთი ელემენტის ნაკრები (წაიკითხეთ საძიებო გისოსის პირველი დონე, სადაც დამოკიდებულებების მარცხენა მხარე შედგება ერთი ატრიბუტისაგან) წარმოადგენს თითოეულ ატრიბუტს. თავდაპირველი ურთიერთობის.
პირველ რიგში, ჩვენ განვიხილავთ ∅ → ფორმის დამოკიდებულებებს ერთი ატრიბუტი. ეს ნაბიჯი საშუალებას გაძლევთ განსაზღვროთ რომელი ატრიბუტებია ძირითადი გასაღებები (ასეთი ატრიბუტებისთვის არ არსებობს განმსაზღვრელი და, შესაბამისად, მარცხენა მხარე ცარიელია). გარდა ამისა, ასეთი ალგორითმები მაღლა მოძრაობენ გისოსის გასწვრივ. აღსანიშნავია, რომ მთელი გისოსის გავლა არ შეიძლება, ანუ თუ მარცხენა მხარის სასურველი მაქსიმალური ზომა გადაეცემა შეყვანას, მაშინ ალგორითმი არ წავა უფრო შორს, ვიდრე ამ ზომის დონე.

ქვემოთ მოყვანილი სურათი გვიჩვენებს, თუ როგორ შეიძლება ალგებრული გისოსის გამოყენება FZ-ის პოვნის პრობლემაში. აქ ყოველი ზღვარი (X, XY) წარმოადგენს დამოკიდებულებას X → Y. მაგალითად, ჩვენ გავიარეთ პირველი დონე და ვიცით, რომ დამოკიდებულება შენარჩუნებულია A → B (ამას გამოვაჩენთ როგორც მწვანე კავშირს წვეროებს შორის A и B). ეს ნიშნავს, რომ შემდგომში, როდესაც ჩვენ მაღლა ავწევთ გისოსის გასწვრივ, შეიძლება არ შევამოწმოთ დამოკიდებულება A, C → B, რადგან ის აღარ იქნება მინიმალური. ანალოგიურად, ჩვენ არ შევამოწმებთ მას, თუ დამოკიდებულება შენარჩუნებული იყო C → B.

გარდა ამისა, როგორც წესი, ფედერალური კანონების ძიების ყველა თანამედროვე ალგორითმი იყენებს მონაცემთა სტრუქტურას, როგორიცაა დანაყოფი (თავდაპირველ წყაროში - გაშიშვლებული დანაყოფი [1]). დანაყოფის ოფიციალური განმარტება შემდეგია:

განმარტება 6. მოდით X ⊆ R იყოს ატრიბუტების სიმრავლე r მიმართებისთვის. კლასტერი არის r-ში ტოპების ინდექსების ერთობლიობა, რომლებსაც აქვთ იგივე მნიშვნელობა X-სთვის, ანუ c(t) = {i|ti[X] = t[X]}. დანაყოფი არის კლასტერების ნაკრები, ერთეულის სიგრძის მტევნის გამოკლებით:

მარტივი სიტყვებით, დანაყოფი ატრიბუტისთვის X არის სიების ნაკრები, სადაც თითოეული სია შეიცავს ხაზების ნომრებს იგივე მნიშვნელობებით X. თანამედროვე ლიტერატურაში, ტიხრების გამოსახულ სტრუქტურას პოზიციების სიის ინდექსი (PLI) ეწოდება. ერთეულის სიგრძის კლასტერები გამორიცხულია PLI შეკუმშვის მიზნებისთვის, რადგან ეს არის კლასტერები, რომლებიც შეიცავს მხოლოდ ჩანაწერის რიცხვს უნიკალური მნიშვნელობით, რომლის იდენტიფიცირება ყოველთვის ადვილი იქნება.

მოდით შევხედოთ მაგალითს. დავუბრუნდეთ იმავე ცხრილს პაციენტებთან ერთად და ავაშენოთ ტიხრები სვეტებისთვის პაციენტი и Paul (მარცხნივ გამოჩნდა ახალი სვეტი, რომელშიც მონიშნულია ცხრილის რიგის ნომრები):

უფრო მეტიც, განმარტების მიხედვით, დანაყოფი სვეტისთვის პაციენტი ფაქტიურად ცარიელი იქნება, რადგან ცალკეული კლასტერები გამორიცხულია დანაყოფიდან.

ტიხრების მიღება შესაძლებელია რამდენიმე ატრიბუტით. და ამის გაკეთების ორი გზა არსებობს: ცხრილის გავლით, ააგეთ დანაყოფი ერთდროულად ყველა საჭირო ატრიბუტის გამოყენებით, ან ააგეთ იგი დანაყოფების გადაკვეთის მოქმედების გამოყენებით ატრიბუტების ქვეჯგუფის გამოყენებით. ფედერალური კანონის საძიებო ალგორითმები იყენებენ მეორე ვარიანტს.

მარტივი სიტყვებით, მაგალითად, მიიღოთ დანაყოფი სვეტების მიხედვით ABC, შეგიძლიათ აიღოთ დანაყოფები AC и B (ან სხვა დისჯონური ქვესიმრავლეების ნაკრები) და გადაკვეთეთ ისინი ერთმანეთთან. ორი დანაყოფის გადაკვეთის ოპერაცია ირჩევს ყველაზე დიდი სიგრძის კლასტერებს, რომლებიც საერთოა ორივე დანაყოფისთვის.

მოდით შევხედოთ მაგალითს:

პირველ შემთხვევაში მივიღეთ ცარიელი დანაყოფი. თუ კარგად დააკვირდებით ცხრილს, მაშინ ნამდვილად არ არსებობს იდენტური მნიშვნელობები ორი ატრიბუტისთვის. თუ ცხრილს ოდნავ შევცვლით (ქეისი მარჯვნივ), უკვე მივიღებთ არაცარიელ კვეთას. უფრო მეტიც, 1 და 2 სტრიქონები რეალურად შეიცავს იგივე მნიშვნელობებს ატრიბუტებისთვის Paul и ექიმი.

შემდეგი, ჩვენ დაგვჭირდება ისეთი კონცეფცია, როგორიცაა დანაყოფის ზომა. ფორმალურად:

მარტივად რომ ვთქვათ, დანაყოფის ზომა არის დანაყოფში შემავალი კლასტერების რაოდენობა (გახსოვდეთ, რომ ცალკეული კლასტერები არ შედის დანაყოფში!):

ახლა ჩვენ შეგვიძლია განვსაზღვროთ ერთ-ერთი ძირითადი ლემა, რომელიც მოცემული ტიხრებისთვის საშუალებას გვაძლევს განვსაზღვროთ არის თუ არა დამოკიდებულება:

ლემა 1. დამოკიდებულება A, B → C მოქმედებს თუ და მხოლოდ თუ

ლემის მიხედვით, იმის დასადგენად, მოქმედებს თუ არა დამოკიდებულება, უნდა შესრულდეს ოთხი ნაბიჯი:

1. გამოთვალეთ დანაყოფი დამოკიდებულების მარცხენა მხარისთვის
2. გამოთვალეთ დანაყოფი დამოკიდებულების მარჯვენა მხარისთვის
3. გამოთვალეთ პირველი და მეორე საფეხურის ნამრავლი
4. შეადარეთ პირველ და მესამე საფეხურზე მიღებული დანაყოფების ზომები

ქვემოთ მოცემულია მაგალითი იმისა, რომ შეამოწმოთ არის თუ არა დამოკიდებულება ამ ლემის მიხედვით:

ამ სტატიაში ჩვენ განვიხილეთ ცნებები, როგორიცაა ფუნქციური დამოკიდებულება, სავარაუდო ფუნქციონალური დამოკიდებულება, დავაკვირდით, სად გამოიყენება ისინი, ასევე რა ალგორითმები არსებობს ფიზიკური ფუნქციების საძიებლად. ჩვენ ასევე დეტალურად განვიხილეთ ძირითადი, მაგრამ მნიშვნელოვანი ცნებები, რომლებიც აქტიურად გამოიყენება თანამედროვე ალგორითმებში ფედერალური კანონების მოსაძებნად.

ცნობები:

1. Huhtala Y. და სხვ. TANE: ეფექტური ალგორითმი ფუნქციური და მიახლოებითი დამოკიდებულებების აღმოსაჩენად //კომპიუტერული ჟურნალი. – 1999. – T. 42. – No. 2. – გვ.100-111.
2. Kruse S., Naumann F. მიახლოებითი დამოკიდებულებების ეფექტური აღმოჩენა // VLDB Endowment-ის შრომები. – 2018. – T. 11. – No. 7. – გვ 759-772.
3. Papenbrock T., Naumann F. ფუნქციონალური დამოკიდებულების აღმოჩენის ჰიბრიდული მიდგომა //მონაცემთა მენეჯმენტის 2016 წლის საერთაშორისო კონფერენციის შრომები. – ACM, 2016. – გვ.821-833.
4. Papenbrock T. და სხვ. ფუნქციური დამოკიდებულების აღმოჩენა: შვიდი ალგორითმის ექსპერიმენტული შეფასება //VLDB Endowment-ის Proceedings. – 2015. – T. 8. – No. 10. – გვ 1082-1093 წ.
5. Kumar A. და სხვ. შეუერთდე თუ არ შეუერთდე?: ორჯერ ფიქრობ შეერთებაზე მხატვრული არჩევის დაწყებამდე //მონაცემების მართვის შესახებ 2016 წლის საერთაშორისო კონფერენციის მასალები. – ACM, 2016. – გვ.19-34.
6. Abo Khamis M. და სხვ. მონაცემთა ბაზაში სწავლა მწირი ტენსორებით //ACM SIGMOD-SIGACT-SIGAI 37-ე სიმპოზიუმის შრომები მონაცემთა ბაზის სისტემების პრინციპებზე. – ACM, 2018. – გვ.325-340.
7. Hellerstein JM et al. MADlib ანალიტიკური ბიბლიოთეკა: ან MAD skills, SQL //VLDB Endowment-ის Proceedings. – 2012. – T. 5. – No. 12. – გვ 1700-1711 წწ.
8. Qin C., Rusu F. სპეკულაციური მიახლოებები ტერასკალის განაწილებული გრადიენტული დაღმართის ოპტიმიზაციისთვის //Cloud-ში მონაცემთა ანალიტიკის მეოთხე სემინარის შრომები. – ACM, 2015. – გვ. 1.
9. მენგ X. და სხვ. Mllib: მანქანათმცოდნეობა აპაჩის ნაპერწკალში //The Journal of Machine Learning Research. – 2016. – T. 17. – No. 1. – გვ 1235-1241 წ.

სტატიის ავტორები: ანასტასია ბირილო, მკვლევარი ზე JetBrains კვლევა, CS ცენტრის სტუდენტი и ნიკიტა ბობროვი, მკვლევარი ზე JetBrains კვლევა

წყარო: www.habr.com