ეფექტურად იპოვეთ ფუნქციური დამოკიდებულებები მონაცემთა ბაზებში

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

დავალების შერჩევა

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

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

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

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

ქეშირების სქემები დანაყოფების კვეთაზე

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

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

აქ — ახლახან გამოთვლილი დანაყოფის უნიკალურობის ხარისხი ხოლო არის ინდივიდუალური ატრიბუტების უნიკალურობის ხარისხების მედიანა. ზემოთ აღწერილი სამივე მეტრიკა შემოწმდა, როგორც უნიკალურობის მეტრიკა. თქვენ ასევე შეგიძლიათ შეამჩნიოთ, რომ ევრისტიკაში ორი მოდიფიკატორია. პირველი მიუთითებს იმაზე, თუ რამდენად ახლოს არის მიმდინარე დანაყოფი ძირითად გასაღებთან და საშუალებას გაძლევთ უფრო დიდი ზომით მოაწყოთ ის ტიხრები, რომლებიც შორს არიან პოტენციური გასაღებისგან. მეორე მოდიფიკატორი საშუალებას გაძლევთ აკონტროლოთ ქეშის დაკავება და ამით წაახალისოთ ქეში მეტი დანაყოფების დამატება, თუ თავისუფალი სივრცე ხელმისაწვდომია. ამ პრობლემის წარმატებულმა გადაწყვეტამ საშუალება მოგვცა დაგვეჩქარებინა PYRO ალგორითმი 10-40%-ით, მონაცემთა ნაკრებიდან გამომდინარე. აღსანიშნავია, რომ PYRO ალგორითმი ყველაზე წარმატებულია ამ სფეროში.

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

დანაყოფების შენახვის ალტერნატიული გზა

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

$$display$$pi(X) = {{ქვედაჭერი{1, 2, 3, 4, 5}_{პირველი ინტერვალი}, ქვედა ფრჩხილი{7, 8}_{მეორე ინტერვალი}, 10}}\ downarrow{ შეკუმშვა} \ pi(X) = {{ქვედაჭერი{$, 1, 5}_{პირველი~ინტერვალი}, ქვედა ფრჩხილი{7, 8}_{მეორე~ინტერვალი}, 10}}$$display$$

ამ მეთოდმა შეძლო მეხსიერების მოხმარების შემცირება TANE ალგორითმის მუშაობისას 1-დან 25%-მდე. TANE ალგორითმი არის კლასიკური ალგორითმი ფედერალური კანონების მოსაძებნად; ის იყენებს დანაყოფებს მუშაობის დროს. როგორც პრაქტიკის ნაწილი, არჩეულ იქნა TANE ალგორითმი, რადგან ბევრად უფრო ადვილი იყო მასში ინტერვალური შენახვის დანერგვა, ვიდრე, მაგალითად, PYRO-ში, რათა შეფასდეს, მუშაობს თუ არა შემოთავაზებული მიდგომა. მიღებული შედეგები წარმოდგენილია ქვემოთ მოცემულ ფიგურაში. X ღერძი ლოგარითმულია.

კონფერენცია ADBIS-2019

კვლევის შედეგებზე დაყრდნობით, 2019 წლის სექტემბერში გამოვაქვეყნე სტატია ჭკვიანი ქეშირება ეფექტური ფუნქციური დამოკიდებულების აღმოჩენისთვის მონაცემთა ბაზებსა და საინფორმაციო სისტემებში მიღწევების შესახებ 23-ე ევროპულ კონფერენციაზე (ADBIS-2019). პრეზენტაციაზე ნამუშევარი აღნიშნა ბერნჰარდ ტალჰეიმმა, მონაცემთა ბაზების დარგში მნიშვნელოვანმა პირმა. კვლევის შედეგებმა საფუძველი ჩაუყარა ჩემს დისერტაციას სანქტ-პეტერბურგის სახელმწიფო უნივერსიტეტის მათემატიკისა და მექანიკის მაგისტრატურაში, რომლის დროსაც ორივე შემოთავაზებული მიდგომა (ქეშირება და შეკუმშვა) განხორციელდა ორივე ალგორითმში: TANE და PYRO. უფრო მეტიც, შედეგებმა აჩვენა, რომ შემოთავაზებული მიდგომები უნივერსალურია, რადგან ორივე ალგორითმზე, ორივე მიდგომით, დაფიქსირდა მეხსიერების მოხმარების მნიშვნელოვანი შემცირება, ასევე ალგორითმების მუშაობის დროის მნიშვნელოვანი შემცირება.

წყარო: www.habr.com