O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
mustaqil ish
Bajardi: Kompyuter injiniringi
ta’lim yo‘nalishi 012-18 guruh talabasi Mirzajanov Xusan
Qabul qildi: Rahimov M.
Toshkent -2022
10.4. Zichlashtirishga asoslangan usullar
B
o'lish va ierarxik usullar sharsimon klasterlarni topish uchun mo'ljallangan. Ular 10.13-rasmdagi “S” shakli va oval klasterlar kabi ixtiyoriy shakldagi klasterlarni topishda qiynaladi. Bunday ma'lumotlarni hisobga olgan holda, ular shovqin yoki tashqi ko'rsatkichlar klasterlarga kiritilgan qavariq hududlarni noto'g'ri aniqlashlari mumkin.
10.13-rasm Ixtiyoriy shakllarning klasterlari.
Ixtiyoriy shakldagi klasterlarni topish uchun muqobil ravishda biz klasterlarni siyrak hududlar bilan ajratilgan ma'lumotlar maydonidagi zich hududlar sifatida modellashimiz mumkin. Bu zichlikka asoslangan klasterlash usullari ortidagi asosiy strategiya bo'lib, sharsimon bo'lmagan shakldagi klasterlarni aniqlay oladi. Ushbu bo'limda siz DBSCAN (10.4.1-bo'lim), OPTICS (10.4.2-bo'lim) va DENCLUE (10.4.3-bo'lim) uchta vakillik usulini o'rganish orqali zichlikka asoslangan klasterlashning asosiy usullarini o'rganasiz.
10.4.1. DBSCAN: Yuqori zichlikka ega ulangan hududlarga asoslangan zichlikka asoslangan klasterlash
"Biz zichlikka asoslangan klasterlashda zich hududlarni qanday topishimiz mumkin?" O jismning zichligini o ga yaqin bo`lgan jismlar soni bilan o`lchash mumkin. DBSCAN (Shovqinli ilovalarning zichlikka asoslangan fazoviy klasteri) asosiy ob'ektlarni, ya'ni zich qo'shnilarga ega bo'lgan ob'ektlarni topadi. U asosiy ob'ektlarni va ularning qo'shnilarini bir-biriga bog'lab, zich hududlarni klasterlar sifatida hosil qiladi.
"Qanday qilib DBSCAN ob'ektning qo'shniligini aniqlaydi?" Biz har bir ob'ekt uchun ko'rib chiqiladigan mahalla radiusini belgilash uchun foydalanuvchi tomonidan belgilangan parametr s > 0 ishlatiladi. O jismning s-qo'shnisi - markazi o nuqtada joylashgan s radiusdagi fazo. Ixtiyoriy shakldagi klasterlarni topish uchun muqobil ravishda biz klasterlarni siyrak hududlar bilan ajratilgan ma'lumotlar maydonidagi zich hududlar sifatida modellashimiz mumkin.
Bu zichlikka asoslangan klasterlash usullari ortidagi asosiy strategiya bo'lib, sharsimon bo'lmagan shakldagi klasterlarni aniqlay oladi. Ushbu bo'limda siz DBSCAN (10.4.1-bo'lim), OPTICS (10.4.2-bo'lim) va DENCLUE (10.4.3-bo'lim) uchta vakillik usulini o'rganish orqali zichlikka asoslangan klasterlashning asosiy usullarini o'rganasiz.
ϵ bilan parametrlangan qo'shni o'lchami tufayli mahallaning zichligini shunchaki mahalladagi ob'ektlar soni bilan o'lchash mumkin. Mahalla zich yoki zich emasligini aniqlash uchun DBSCAN foydalanuvchi tomonidan belgilangan boshqa parametr MinPts dan foydalanadi, bu zich hududlarning zichlik chegarasini belgilaydi. Ob'ektning s-mahallasida kamida MinPts obyektlari bo'lsa, ob'ekt asosiy ob'ekt hisoblanadi. Asosiy ob'ektlar - zich hududlarning ustunlari.
Ob'ektlarning D to'plamini hisobga olsak, biz barcha asosiy ob'ektlarni berilgan parametrlarga, ϵ va MinPtsga nisbatan aniqlay olamiz. Bunda klasterlash vazifasi zich mintaqalar klasterlar bo'lgan zich hududlarni shakllantirish uchun asosiy ob'ektlar va ularning qo'shnilaridan foydalanishga qisqartiriladi. Asosiy ob'ekt q va p ob'ekt uchun, agar p q ning ϵ-qo'shnisida bo'lsa, p to'g'ridan-to'g'ri q dan (ϵ va MinPts ga nisbatan) zichlikka erishish mumkin deb aytamiz. Shubhasiz, p ob'ekt boshqa q ob'ektidan to'g'ridan-to'g'ri zichlikka erishish mumkin, agar q asosiy ob'ekt bo'lsa va p q ning -qo'shnisida bo'lsa. To'g'ridan-to'g'ri zichlikka erishish mumkin bo'lgan munosabatdan foydalanib, asosiy ob'ekt o'zining s-mahallasidan barcha ob'ektlarni zich mintaqaga "olib kelishi" mumkin.
"Qanday qilib biz asosiy ob'ektlar joylashgan kichik zich hududlardan foydalangan holda katta zich hududni yig'ishimiz mumkin?" DBSCAN da p zichlikka q dan (D da ϵ va MinPts ga nisbatan) erishish mumkin, agar p1, …, pn jismlar zanjiri mavjud bo'lsa, p1 = q, pn = p, va pi + 1 p1 = q, pn = p, and pi + 1 to'g'ridan-to'g'ri zichlikdir. ϵ va MinPts ga nisbatan pi dan yetib borish mumkin, 1 ≤ i ≤ n, pi ∈ D uchun. E'tibor bering, zichlik-oluvchanlik ekvivalentlik munosabati emas, chunki u simmetrik emas. Agar o1 ham, o2 ham asosiy ob'ektlar bo'lsa va o1 zichlikka o2 dan erishish mumkin bo'lsa, u holda o2 o1 dan zichlikka erishish mumkin. Biroq, agar o2 asosiy ob'ekt bo'lsa, lekin o1 bo'lmasa, u holda o1 zichlikka o2 dan erishish mumkin, lekin aksincha emas.
Asosiy ob'ektlarni va ularning zich mintaqadagi qo'shnilarini ulash uchun DBSCAN zichlik bilan bog'liqlik tushunchasidan foydalanadi. Ikkita p1, p2 ∈ D ob'ektlar s va MinPts ga nisbatan zichlik bilan bog'langan, agar q ∈ D ob'ekt mavjud bo'lsa, p1 va p2 ham q dan ϵ va MinPts ga nisbatan zichlikka erishish mumkin. Zichlik - erishish mumkinligidan farqli o'laroq, zichlik - bog'liqlik ekvivalentlik munosabatidir. Ko'rsatish osonki, o1 , o2 va o3 jismlar uchun o1 va o2 zichlikka, o2 va o3 esa zichlikka bog'langan bo'lsa, u holda o1 va o3 ham shunday bo'ladi.
Zichlik-eluvchanlik va zichlik-bog'lanish
Aylanalar radiusi bilan ifodalangan berilgan s uchun 10.14-rasmni ko‘rib chiqamiz va aytaylik, MinPts = 3 bo‘lsin.
10.14-rasm Zichlikka asoslangan klasterlashda zichlikka erishish va zichlik-bog'lanish.
Belgilangan nuqtalardan m, p, o, r asosiy ob'ektlardir, chunki ularning har biri kamida uchta nuqtani o'z ichiga olgan s-mahallada joylashgan. Ob'ekt q m dan to'g'ridan-to'g'ri zichlikka erishish mumkin. m ob'ekti zichlikka to'g'ridan-to'g'ri p dan erishish mumkin va aksincha.
Ob'ekt q (bilvosita) zichlikka p dan erishish mumkin, chunki q to'g'ridan-to'g'ri zichlikka m dan va m to'g'ridan-to'g'ri zichlikka p dan erishish mumkin. Biroq, p ni q dan zichlikka erishib bo'lmaydi, chunki q asosiy ob'ekt emas. Xuddi shunday, r va s zichlikka o dan, o ga esa r dan erishish mumkin. Shunday qilib, o, r va s barcha zichlik bilan bog'langan.
Biz bog'langan zich hududlarni klaster sifatida topish uchun zichlik-bog'lanishning yopilishidan foydalanishimiz mumkin. Har bir yopiq to'plam zichlikka asoslangan klasterdir. Agar (1) har qanday ikkita ob'ekt uchun o1 , o2 ∈ C, o1 va o2 zichlik bilan bog'langan bo'lsa, C ⊆ D kichik to'plami klasterdir; va (2) o ∈ C ob'ekti va o' ∈ (D - C) boshqa ob'ekt mavjud emas, shunday qilib o va o' zichlik bilan bog'langan.
"DBSCAN klasterlarni qanday topadi?" Dastlab, ma'lum D ma'lumotlar to'plamidagi barcha ob'ektlar "tashrif buyurilmagan" sifatida belgilanadi. DBSCAN tasodifiy ravishda tashrif buyurilmagan p ob'ektini tanlaydi, p ni "tashrif buyurilgan" deb belgilaydi va p ning s-mahallasida kamida MinPts ob'ektlari mavjudligini tekshiradi. Agar yo'q bo'lsa, p shovqin nuqtasi sifatida belgilanadi. Aks holda, p uchun yangi C klasteri yaratiladi va p ning s-mahallasidagi barcha ob'ektlar nomzodlar to'plamiga qo'shiladi, N. DBSCAN hech qanday klasterga tegishli bo'lmagan N ob'ektlarini takroriy ravishda C ga qo'shadi. Bu jarayonda “tashrif buyurilmagan” belgisini olib yuruvchi N dagi p’ obyekti uchun DBSCAN uni “tashrif buyurilgan” deb belgilaydi va uning s-mahallasini tekshiradi. Agar p' ning s-mahallasida hech bo'lmaganda MinPts ob'ektlari bo'lsa, p' ning s-mahallasidagi bu ob'ektlar N ga qo'shiladi. DBSCAN C ni kengaytirib bo'lmaguncha, ya'ni N bo'sh qolguncha C ga ob'ektlar qo'shishda davom etadi. Bu vaqtda C klasteri tugallandi va shu bilan chiqadi.
Keyingi klasterni topish uchun DBSCAN qolgan ob'ektlardan tasodifiy ravishda ko'rilmagan ob'ektni tanlaydi. Klasterlash jarayoni barcha ob'ektlarga tashrif buyurilgunga qadar davom etadi. DBSCAN algoritmining psevdokodi 10.15-rasmda keltirilgan.
10.15-rasm DBSCAN algoritmi.
Agar fazoviy indeks ishlatilsa, DBSCAN ning hisoblash murakkabligi O(n log n), bu erda n ma'lumotlar bazasi ob'ektlari soni. Aks holda, murakkablik O(n2) ga teng. Foydalanuvchi tomonidan belgilangan parametrlar, s va MinPtsning tegishli sozlamalari bilan algoritm ixtiyoriy shakldagi klasterlarni topishda samarali bo'ladi.
|
