Ma'lumotlardagi funktsional bog'liqlikni topish ma'lumotlar tahlilining turli sohalarida qo'llaniladi: ma'lumotlar bazasini boshqarish, ma'lumotlarni tozalash, ma'lumotlar bazasini teskari muhandislik va ma'lumotlarni o'rganish. Biz allaqachon bog'liqliklarning o'zlari haqida nashr qilganmiz Anastasiya Birillo va Nikita Bobrov. Bu safar kompyuter fanlari markazining joriy yil bitiruvchisi Anastasiya markazda himoya qilgan tadqiqot ishlari doirasida ushbu ishning rivojlanishi bilan o'rtoqlashmoqda.
Vazifa tanlash
CS markazida o'qiyotganimda, men ma'lumotlar bazalarini chuqur o'rganishni boshladim, ya'ni funktsional va farqlarga bog'liqliklarni qidirish. Bu mavzu universitetdagi kurs ishim mavzusi bilan bog'liq edi, shuning uchun kurs ishi ustida ishlayotganda ma'lumotlar bazalaridagi turli bog'liqliklar haqidagi maqolalarni o'qiy boshladim. Men ushbu sohaga sharh yozdim - bu mening birinchi sharhlarimdan biri ingliz tilida tayyorladi va SEIM-2017 konferensiyasiga taqdim etdi. Uning qabul qilinganini bilganimda juda xursand bo'ldim va mavzuni chuqurroq o'rganishga qaror qildim. Kontseptsiyaning o'zi yangi emas - u 90-yillarda qo'llanila boshlandi, ammo hozir ham u ko'plab sohalarda qo'llanilmoqda.
Markazdagi ikkinchi semestrda men funksional bog‘liqliklarni topish algoritmlarini takomillashtirish bo‘yicha tadqiqot loyihasini boshladim. U JetBrains Research kompaniyasida Sankt-Peterburg davlat universiteti aspiranti Nikita Bobrov bilan birga ishlagan.
Funktsional bog'liqliklarni qidirishning hisoblash murakkabligi
Asosiy muammo - bu hisoblashning murakkabligi. Mumkin bo'lgan minimal va ahamiyatsiz bog'liqliklar soni yuqorida qiymat bilan cheklangan qayerda — jadval atributlari soni. Algoritmlarning ishlash vaqti nafaqat atributlar soniga, balki qatorlar soniga ham bog'liq. 90-yillarda oddiy ish stoli kompyuterida federal qonunlarni qidirish algoritmlari bir necha soat ichida 20 tagacha atribut va o'n minglab qatorlarni o'z ichiga olgan ma'lumotlar to'plamini qayta ishlashga qodir edi. Ko'p yadroli protsessorlarda ishlaydigan zamonaviy algoritmlar taxminan bir vaqtning o'zida yuzlab atributlardan (200 tagacha) va yuz minglab qatorlardan iborat ma'lumotlar to'plamiga bog'liqlikni aniqlaydi. Biroq, bu etarli emas: bunday vaqt ko'pchilik real ilovalar uchun qabul qilinishi mumkin emas. Shuning uchun biz mavjud algoritmlarni tezlashtirish uchun yondashuvlarni ishlab chiqdik.
Bo'lim kesishmalari uchun keshlash sxemalari
Ishning birinchi qismida biz qismlarni kesish usulidan foydalanadigan algoritmlar sinfi uchun keshlash sxemalarini ishlab chiqdik. Atribut uchun bo'lim - bu ro'yxatlar to'plami bo'lib, unda har bir ro'yxatda berilgan atribut uchun bir xil qiymatlarga ega bo'lgan qator raqamlari mavjud. Bunday ro'yxatlarning har biri klaster deb ataladi. Ko'pgina zamonaviy algoritmlar bo'limlardan bog'liqlik saqlanib qolgan yoki yo'qligini aniqlash uchun foydalanadi, ya'ni ular lemmaga amal qiladi: Bog'liqlik agar o'tkaziladi ... Bu yerda bo'lim belgilanadi va bo'lim hajmi tushunchasi qo'llaniladi - undagi klasterlar soni. Bo'limlardan foydalanadigan algoritmlar, agar bog'liqlik buzilgan bo'lsa, bog'liqlikning chap tomoniga qo'shimcha atributlar qo'shib, keyin bo'limlarni kesish operatsiyasini bajarib, uni qayta hisoblab chiqadi. Ushbu operatsiya maqolalarda ixtisoslashuv deb ataladi. Ammo biz bir necha ixtisoslashuvdan so'ng saqlanib qoladigan bog'liqliklar bo'limlarini faol ravishda qayta ishlatish mumkinligini payqadik, bu algoritmlarning ishlash vaqtini sezilarli darajada qisqartirishi mumkin, chunki kesishish operatsiyasi qimmat.
Shuning uchun biz Shennon entropiyasi va Jinni noaniqligiga asoslangan evristikani, shuningdek, biz teskari entropiya deb atagan o'lchovimizni taklif qildik. Bu Shannon Entropiyasining ozgina modifikatsiyasi bo'lib, ma'lumotlar to'plamining o'ziga xosligi oshgani sayin ortadi. Taklif etilayotgan evristik usul quyidagicha:
u — yaqinda hisoblangan bo'limning o'ziga xoslik darajasi va individual xususiyatlar uchun o'ziga xoslik darajalarining medianasidir. Yuqorida tavsiflangan barcha uchta ko'rsatkich noyoblik ko'rsatkichi sifatida sinovdan o'tkazildi. Evristikda ikkita modifikator mavjudligini ham sezishingiz mumkin. Birinchisi joriy bo'limning asosiy kalitga qanchalik yaqinligini ko'rsatadi va potentsial kalitdan uzoq bo'lgan qismlarni ko'proq keshlash imkonini beradi. Ikkinchi modifikator kesh bandligini kuzatish imkonini beradi va shu bilan bo'sh joy mavjud bo'lsa keshga qo'shimcha qismlar qo'shishni rag'batlantiradi. Ushbu muammoni muvaffaqiyatli hal qilish bizga PYRO algoritmini ma'lumotlar to'plamiga qarab 10-40% ga tezlashtirishga imkon berdi. Shuni ta'kidlash kerakki, PYRO algoritmi bu sohada eng muvaffaqiyatli hisoblanadi.
Quyidagi rasmda siz taklif qilingan evristikni qo'llash natijalarini tanga bilan keshlashning asosiy yondashuviga nisbatan ko'rishingiz mumkin. X o'qi logarifmikdir.
Bo'limlarni saqlashning muqobil usuli
Keyin biz bo'limlarni saqlashning muqobil usulini taklif qildik. Bo'limlar klasterlar to'plami bo'lib, ularning har biri ma'lum atributlar uchun bir xil qiymatlarga ega bo'lgan kortejlar sonini saqlaydi. Ushbu klasterlar, masalan, jadvaldagi ma'lumotlar tartiblangan bo'lsa, uzun qator raqamlarni o'z ichiga olishi mumkin. Shuning uchun biz bo'limlarni saqlash uchun siqish sxemasini taklif qildik, ya'ni bo'limlar klasterlarida qiymatlarni intervalgacha saqlash:
$$display$$pi(X) = {{pastki chiziq{1, 2, 3, 4, 5}_{Birinchi interval}, pastki qavs{7, 8}_{Ikkinchi interval}, 10}}\ pastga yoʻnaltirish{ Siqish} \ pi(X) = {{astarlash{$, 1, 5}_{Birinchi~interval}, pastki brace{7, 8}_{Ikkinchi~interval}, 10}}$$displey$$
Ushbu usul TANE algoritmining ishlashi davomida xotira sarfini 1 dan 25% gacha kamaytirishga muvaffaq bo'ldi. TANE algoritmi federal qonunlarni qidirish uchun klassik algoritm bo'lib, u ish paytida bo'limlardan foydalanadi. Amaliyotning bir qismi sifatida TANE algoritmi tanlandi, chunki taklif qilingan yondashuvning ishlashini baholash uchun, masalan, PYRO-ga qaraganda, unda intervalli saqlashni amalga oshirish ancha oson edi. Olingan natijalar quyidagi rasmda keltirilgan. X o'qi logarifmikdir.
ADBIS-2019 konferensiyasi
Tadqiqot natijalariga ko'ra, 2019 yil sentyabr oyida men maqola chop etdim Maʼlumotlar bazalari va axborot tizimlaridagi yutuqlar boʻyicha 23-Yevropa konferensiyasida (ADBIS-2019). Taqdimot chog‘ida ma’lumotlar bazalari sohasidagi salmoqli shaxs Bernxard Talxaym ishni ta’kidlab o‘tdi. Tadqiqot natijalari Sankt-Peterburg davlat universitetining matematika va mexanika magistratura bosqichidagi dissertatsiyamning asosini tashkil etdi, uning davomida ikkala taklif qilingan yondashuvlar (keshlash va siqish) ikkala algoritmda ham amalga oshirildi: TANE va PYRO. Bundan tashqari, natijalar shuni ko'rsatdiki, taklif qilingan yondashuvlar universaldir, chunki ikkala algoritmda ham ikkala yondashuvda ham xotira sarfini sezilarli darajada kamaytirish, shuningdek algoritmlarning ishlash vaqtini sezilarli darajada qisqartirish kuzatildi.
Manba: www.habr.com