Guruh talabasi Uzbekov Baxtiyor

10.5.2. CLIQUE: Aprioriga o'xshash pastki fazoni klasterlash usuli
Ma'lumotlar ob'ekti ko'pincha o'nlab atributlarga ega, ularning aksariyati ahamiyatsiz bo'lishi mumkin. Atributlarning qiymatlari sezilarli darajada farq qilishi mumkin. Ushbu omillar butun ma'lumotlar maydonini qamrab oladigan klasterlarni topishni qiyinlashtirishi mumkin. Buning o'rniga ma'lumotlarning turli pastki bo'shliqlari ichida klasterlarni qidirish yanada mazmunli bo'lishi mumkin. Misol uchun, sog'liqni saqlash-informatika ilovasini ko'rib chiqing, unda bemor yozuvlarida shaxsiy ma'lumotlar, ko'plab alomatlar, holatlar va oila tarixini tavsiflovchi keng qamrovli atributlar mavjud.
Barcha yoki hatto ko'pgina atributlari bir-biriga mos keladigan bemorlarning ahamiyatsiz guruhini topish dargumon. Masalan, parranda grippi bilan og'rigan bemorlarning yoshi, jinsi va ish atributlari turli qiymatlar doirasida keskin farq qilishi mumkin. Shunday qilib, butun ma'lumotlar maydonida bunday klasterni topish qiyin bo'lishi mumkin. Buning o'rniga, pastki bo'shliqlarni qidirish orqali biz past o'lchamli bo'shliqda o'xshash bemorlar klasterini topishimiz mumkin (masalan, yuqori isitma, yo'tal kabi alomatlar bo'yicha bir-biriga o'xshash, ammo burun oqishi yo'q va yoshi 3 dan 3 gacha bo'lgan bemorlar). 16).
CLIQUE (QUEstda klasterlash) - bu pastki bo'shliqlarda zichlikka asoslangan klasterlarni topish uchun oddiy gridga asoslangan usul. CLIQUE har bir o'lchamni bir-biriga mos kelmaydigan intervallarga ajratadi va shu bilan ma'lumotlar ob'ektlarining butun joylashtirish maydonini hujayralarga ajratadi. U zich va siyrak hujayralarni aniqlash uchun zichlik chegarasidan foydalanadi. Agar ob'ektlar soni zichlik chegarasidan oshib ketgan bo'lsa, hujayra zich hisoblanadi.
Nomzodni qidirish maydonini aniqlash uchun CLIQUE orqasidagi asosiy strategiya zich hujayralarning o'lchamlarga nisbatan monotonligidan foydalanadi. Bu tez-tez naqsh va assotsiatsiya qoidalarini qazib olishda ishlatiladigan Apriori mulkiga asoslangan (6-bob). Pastki fazolardagi klasterlar kontekstida monotonlik quyidagilarni aytadi. Agar (k − 1) o‘lchamli kichik fazodagi hujayra bo‘lgan c ning har bir (k − 1) o‘lchovli proyeksiyasi kamida l bo‘lsa, k o‘lchamli c(k > 1) katak kamida l nuqtaga ega bo‘lishi mumkin. ball. 10.20-rasmni ko'rib chiqing, bu erda ma'lumotlarni joylashtirish maydoni uchta o'lchovni o'z ichiga oladi: yosh, ish haqi va ta'til. Ikki o'lchamli hujayra, aytaylik, yosh va ish haqi bo'yicha hosil bo'lgan pastki fazoda, agar ushbu hujayraning har bir o'lchovdagi proyeksiyasi, ya'ni yoshi va ish haqi, kamida l nuqtani o'z ichiga olsagina, l nuqtani o'z ichiga oladi.

10.20-rasm Ish haqi va ta'til o'lchovlari uchun yoshga nisbatan topilgan zich birliklar yuqori o'lchamdagi zich birliklarni qidirish maydonini ta'minlash uchun kesishadi.

CLIQUE klasterlashni ikki bosqichda amalga oshiradi. Birinchi bosqichda CLIQUE d o'lchamli ma'lumotlar maydonini bir-biriga yopishmaydigan to'rtburchaklar birliklarga bo'lib, ular orasidagi zich birliklarni aniqlaydi. CLIQUE barcha pastki bo'shliqlarda zich hujayralarni topadi. Buning uchun CLIQUE har bir o'lchamni intervallarga bo'ladi va kamida l nuqtadan iborat intervallarni aniqlaydi, bu erda l - zichlik chegarasi. Keyin CLIQUE iterativ ravishda ikkita k o‘lchamli zich hujayralarni, c1 va c2 kichik bo‘shliqlarda (Di1, …, Dik) va (Dj1, …, Djk) birlashadi, agar Di1 = Dj1, …, Dik − 1 = Djk − 1 bo‘lsa, va c1 va c2 bu o'lchamlarda bir xil intervallarni taqsimlaydi. Birlashtirish operatsiyasi fazoda yangi (k + 1) o'lchamli nomzod c katakchasini hosil qiladi (Di1, …, Dik - 1, Dik, Djk). CLIQUE c dagi nuqtalar soni zichlik chegarasidan o'tishini tekshiradi. Nomzodlar hosil bo'lmaganda yoki nomzod hujayralar zich bo'lmaganda iteratsiya tugaydi.

Ikkinchi bosqichda CLIQUE ixtiyoriy shaklga ega bo'lishi mumkin bo'lgan klasterlarni yig'ish uchun har bir kichik bo'shliqdagi zich hujayralardan foydalanadi. Maqsad minimal tavsif uzunligi (MDL) printsipini (8-bob) qo'llashdan iborat bo'lib, ulangan zich hujayralarni qoplash uchun maksimal hududlardan foydalanish kerak, bu erda maksimal mintaqa giperto'rtburchak bo'lib, bu hududga tushadigan har bir hujayra zich bo'ladi va mintaqa bo'lishi mumkin emas. pastki fazoda istalgan o'lchamda yanada kengaytirilgan. Umuman olganda, klasterning eng yaxshi tavsifini topish NP-Hard. Shunday qilib, CLIQUE oddiy ochko'z yondashuvni qo'llaydi. U o'zboshimchalik bilan zich hujayradan boshlanadi, hujayrani qoplaydigan maksimal hududni topadi va keyin hali qoplanmagan qolgan zich hujayralar ustida ishlaydi. Ochko'zlik usuli barcha zich hujayralar qoplanganida tugaydi.
"CLIQUE qanchalik samarali?" CLIQUE avtomatik ravishda eng yuqori o'lchamli pastki bo'shliqlarni topadi, shuning uchun bu pastki bo'shliqlarda yuqori zichlikli klasterlar mavjud. U kirish ob'ektlari tartibiga sezgir emas va hech qanday kanonik ma'lumotlarni taqsimlashni nazarda tutmaydi. U kirish hajmiga qarab chiziqli ravishda o'zgaradi va ma'lumotlardagi o'lchamlar soni ko'payganligi sababli yaxshi miqyoslilikka ega. Biroq, mazmunli klasterni olish panjara o'lchamini (bu erda barqaror tuzilma) va zichlik chegarasini to'g'ri sozlashga bog'liq. Bu amalda qiyin bo'lishi mumkin, chunki tarmoq o'lchami va zichlik chegarasi ma'lumotlar to'plamidagi o'lchamlarning barcha kombinatsiyalarida qo'llaniladi. Shunday qilib, klasterlash natijalarining aniqligi usulning soddaligi hisobiga yomonlashishi mumkin. Bundan tashqari, ma'lum bir zich mintaqa uchun mintaqaning pastki o'lchamli pastki bo'shliqlarga barcha proyeksiyalari ham zich bo'ladi. Bu xabar qilingan zich hududlar o'rtasida katta o'xshashlikka olib kelishi mumkin. Bundan tashqari, har xil o'lchamli pastki bo'shliqlar ichida juda boshqacha zichlikdagi klasterlarni topish qiyin.
Ushbu yondashuvning bir nechta kengaytmalari xuddi shunday falsafaga amal qiladi. Misol uchun, biz to'rni qo'zg'almas qutilar to'plami deb tasavvur qilishimiz mumkin. Har bir o'lcham uchun qattiq qutilardan foydalanish o'rniga, biz ma'lumotlarni tarqatish statistikasi asosida har bir o'lchov uchun qutilarni dinamik ravishda aniqlash uchun moslashtirilgan, ma'lumotlarga asoslangan strategiyadan foydalanishimiz mumkin. Shu bilan bir qatorda, zichlik chegarasidan foydalanish o'rniga, biz pastki fazo klasterlarining sifati o'lchovi sifatida entropiyadan (8-bob) foydalanishimiz mumkin.