Guruh talabasi Uzbekov Baxtiyor

012-18 guruh talabasi
Uzbekov Baxtiyor
10.5. Gridga asoslangan usullar
Hozirgacha muhokama qilingan klasterlash usullari ma'lumotlarga asoslangan - ular ob'ektlar to'plamini bo'linadi va ob'ektlarni joylashtirish maydonida taqsimlanishiga moslashadi. muqobil ravishda, gridga asoslangan klasterlash usuli, kiritish ob'ektlarining taqsimlanishidan qat'iy nazar, joylashtirish maydonini hujayralarga bo'lish orqali bo'shliqqa asoslangan yondashuvni oladi.
To'rga asoslangan klasterlash usuli ko'p o'lchamli tarmoq ma'lumotlar strukturasidan foydalanadi. U ob'ekt bo'shlig'ini klasterlash bo'yicha barcha operatsiyalar bajariladigan panjara strukturasini tashkil etuvchi chekli sonli kataklarga aylantiradi. Yondashuvning asosiy afzalligi uning tez ishlov berish vaqti bo'lib, u odatda ma'lumotlar ob'ektlari sonidan mustaqil, lekin kvantlangan fazodagi har bir o'lchamdagi hujayralar soniga bog'liq.
Ushbu bo'limda biz ikkita odatiy misol yordamida gridga asoslangan klasterlashni tasvirlaymiz. STING (10.5.1-bo'lim) panjara hujayralarida saqlanadigan statistik ma'lumotlarni o'rganadi. CLIQUE (10.5.2-bo'lim) yuqori o'lchamli ma'lumotlar maydonida pastki fazolarni klasterlash uchun grid va zichlikka asoslangan yondashuvni ifodalaydi.


10.5.1. STING: Statistik ma'lumotlar tarmog'i
STING - bu tarmoqqa asoslangan ko'p o'lchamli klasterlash usuli bo'lib, unda kirish ob'ektlarining fazoviy maydoni to'rtburchaklar hujayralarga bo'linadi. Fazoni ierarxik va rekursiv tarzda ajratish mumkin. Bunday to'rtburchaklar hujayralarning bir necha darajalari turli xil ruxsat darajalariga to'g'ri keladi va ierarxik tuzilmani hosil qiladi: Yuqori darajadagi har bir hujayra keyingi pastki darajadagi bir qator hujayralarni hosil qilish uchun bo'linadi. Har bir katakchadagi atributlarga oid statistik ma'lumotlar, masalan, o'rtacha, maksimal va minimal qiymatlar oldindan hisoblab chiqiladi va statistik parametrlar sifatida saqlanadi. Ushbu statistik parametrlar so'rovlarni qayta ishlash va boshqa ma'lumotlarni tahlil qilish vazifalari uchun foydalidir.
10.19-rasmda STING klasterining ierarxik tuzilishi ko'rsatilgan. Yuqori darajali kataklarning statistik parametrlarini quyi darajadagi hujayralar parametrlaridan osongina hisoblash mumkin. Bu parametrlarga quyidagilar kiradi: atributdan mustaqil parametr, count; va atributga bog'liq parametrlar, o'rtacha, stdev (standart og'ish), min (minimal), maks (maksimal) va hujayradagi atribut qiymati ergashadigan taqsimot turi, masalan, normal, bir xil, eksponensial yoki yo'q (agar taqsimoti noma'lum). Bu erda atribut uy ob'ektlari narxi kabi tahlil uchun tanlangan o'lchovdir. Ma'lumotlar ma'lumotlar bazasiga yuklanganda, pastki darajadagi kataklarning soni, o'rtacha, stdev, min va max parametrlari to'g'ridan-to'g'ri ma'lumotlardan hisoblanadi. Agar tarqatish turi oldindan ma'lum bo'lsa yoki ch2 testi kabi gipoteza testlari orqali olingan bo'lsa, tarqatish qiymati foydalanuvchi tomonidan tayinlanishi mumkin. Yuqori darajadagi hujayraning tarqalish turini uning pastki darajali mos keladigan hujayralarining ko'pgina tarqatish turlaridan kelib chiqib, chegara filtrlash jarayoni bilan birgalikda hisoblash mumkin. Agar quyi darajadagi hujayralar taqsimoti bir-biriga mos kelmasa va chegara sinovidan o'tmasa, yuqori darajadagi hujayraning taqsimot turi "hech" deb o'rnatiladi.

10.19-rasm STING klasterlash uchun ierarxik tuzilma.

"Ushbu statistik ma'lumot so'rovlarga javob berish uchun qanday foydali?" Statistik parametrlardan yuqoridan pastga, gridga asoslangan holda quyidagi tarzda foydalanish mumkin. Birinchidan, ierarxik tuzilma ichidagi qatlam aniqlanadi, undan so'rovlarga javob berish jarayoni boshlanadi. Bu qatlam odatda kam sonli hujayralarni o'z ichiga oladi. Joriy qatlamdagi har bir katak uchun yacheykaning berilgan so‘rovga mosligini aks ettiruvchi ishonch oralig‘ini (yoki taxminiy ehtimollik oralig‘ini) hisoblaymiz. Tegishli bo'lmagan hujayralar keyingi ko'rib chiqishdan olib tashlanadi. Keyingi pastki darajadagi ishlov berish faqat qolgan tegishli hujayralarni tekshiradi. Bu jarayon pastki qatlamga yetguncha takrorlanadi. Ayni paytda, agar so'rov spetsifikatsiyasi bajarilsa, so'rovni qondiradigan tegishli kataklarning hududlari qaytariladi. Aks holda, tegishli kataklarga tushadigan ma'lumotlar olinadi va so'rov talablariga javob berguncha qayta ishlanadi.

STING ning qiziqarli xususiyati shundaki, agar granularlik 0 ga yaqinlashsa (ya'ni, juda past darajadagi ma'lumotlarga nisbatan) DBSCAN klasterlash natijasiga yaqinlashadi. Boshqacha qilib aytganda, son va hujayra o'lchami ma'lumotlaridan foydalangan holda, STING yordamida zich klasterlarni aniqlash mumkin. Shuning uchun, STINGni zichlikka asoslangan klasterlash usuli sifatida ham ko'rib chiqish mumkin.
"STING boshqa klasterlash usullaridan qanday afzalliklarga ega?" STING bir qancha afzalliklarni taqdim etadi: (1) tarmoqqa asoslangan hisoblash so‘rovdan mustaqil, chunki har bir yacheykada saqlanadigan statistik ma’lumotlar so‘rovdan mustaqil ravishda tarmoq yacheykasidagi ma’lumotlarning umumiy ma’lumotlarini ifodalaydi; (2) tarmoq strukturasi parallel ishlov berish va bosqichma-bosqich yangilashni osonlashtiradi; va (3) usulning samaradorligi asosiy afzallik hisoblanadi: STING hujayralarning statistik parametrlarini hisoblash uchun ma'lumotlar bazasidan bir marta o'tadi va shuning uchun klasterlarni yaratishning vaqt murakkabligi O(n), bu erda n - ob'ektlarning umumiy soni. Ierarxik tuzilmani yaratgandan so'ng, so'rovlarni qayta ishlash vaqti O (g) ni tashkil qiladi, bu erda g - eng past darajadagi panjara hujayralarining umumiy soni, odatda n dan ancha kichikdir.
STING klaster tahlilida ko'p rezolyutsiyali yondashuvdan foydalanganligi sababli, STING klasterlash sifati grid strukturasining eng past darajasining granularligiga bog'liq. Agar granularlik juda yaxshi bo'lsa, qayta ishlash narxi sezilarli darajada oshadi; ammo, agar panjara strukturasining pastki darajasi juda qo'pol bo'lsa, u klaster tahlilining sifatini pasaytirishi mumkin. Bundan tashqari, STING ota-ona hujayrasini qurish uchun bolalar va ularning qo'shni hujayralari o'rtasidagi fazoviy munosabatlarni hisobga olmaydi. Natijada, hosil bo'lgan klasterlarning shakllari izotetikdir, ya'ni barcha klaster chegaralari gorizontal yoki vertikal bo'lib, diagonal chegara aniqlanmaydi. Bu texnikaning tez ishlov berish vaqtiga qaramay, klasterlarning sifati va aniqligini pasaytirishi mumkin.