Asosiy tushunchalar va usullar Tasavvur qiling-a, siz AllElectronics kompaniyasining mijozlar bilan aloqalar bo'yicha direktorisiz va sizda beshta menejer ishlaydi

Klasterlashning asosiy usullariga umumiy nuqtai nazar
Adabiyotda ko'plab klaster algoritmlari mavjud. Klasterlash usullarining aniq tasnifini ta'minlash qiyin, chunki bu toifalar bir-biriga mos kelishi mumkin, shuning uchun usul bir nechta toifadagi xususiyatlarga ega bo'lishi mumkin. Shunga qaramay, klasterlash usullarining nisbatan tashkiliy rasmini taqdim etish foydalidir. Umuman olganda, asosiy klasterlash usullarini ushbu bobning qolgan qismida muhokama qilinadigan quyidagi toifalarga ajratish mumkin.
Bo'lish usullari: n ta ob'ekt to'plamini hisobga olgan holda, bo'linish usuli ma'lumotlarning k bo'limini tuzadi, bu erda har bir bo'lim klasterni va k ≤ n ni ifodalaydi. Ya'ni, u ma'lumotlarni k guruhga ajratadi, shunda har bir guruh kamida bitta ob'ektni o'z ichiga olishi kerak. Boshqacha qilib aytganda, bo'linish usullari ma'lumotlar to'plamlarida bir darajali bo'linishni amalga oshiradi. Asosiy qismlarga ajratish usullari odatda eksklyuziv klaster ajratishni qabul qiladi. Ya'ni, har bir ob'ekt aynan bitta guruhga tegishli bo'lishi kerak. Bu talabni, masalan, loyqa qismlarga ajratish texnikasida yumshatish mumkin. Bunday texnikaga havolalar bibliografik yozuvlarda keltirilgan (0.9-bo'lim).
Ko'pgina qismlarga ajratish usullari masofaga asoslangan. K ni hisobga olgan holda, qurish uchun bo'limlar soni, bo'linish usuli dastlabki bo'limni yaratadi. Keyin u ob'ektlarni bir guruhdan ikkinchisiga ko'chirish orqali bo'linishni yaxshilashga harakat qiladigan iterativ ko'chirish texnikasidan foydalanadi. Yaxshi bo'linishning umumiy mezoni shundaki, bir xil klasterdagi ob'ektlar "yaqin" yoki bir-biriga bog'liq, turli klasterlardagi ob'ektlar esa "uzoqda" yoki juda farq qiladi. Bo'limlarning sifatini baholash uchun turli xil boshqa mezonlar mavjud. An'anaviy qismlarga ajratish usullari to'liq ma'lumotlar maydonini qidirish o'rniga, pastki fazo klasteri uchun kengaytirilishi mumkin. Bu atributlar ko'p va ma'lumotlar siyrak bo'lsa foydali bo'ladi.
Bo'limlarga asoslangan klasterlashda global optimallikka erishish ko'pincha hisob-kitoblarni taqiqlaydi va potentsial ravishda barcha mumkin bo'lgan bo'limlarning to'liq ro'yxatini talab qiladi. Buning o'rniga, ko'pchilik ilovalar mashhur evristik usullarni qo'llaydi, masalan, k-vositalari va k-medoids algoritmlari kabi ochko'z yondashuvlar, ular klasterlash sifatini bosqichma-bosqich yaxshilaydi va mahalliy optimalga yaqinlashadi. Ushbu evristik klasterlash usullari kichik va o'rta o'lchamdagi ma'lumotlar bazalarida sharsimon klasterlarni topish uchun yaxshi ishlaydi. Murakkab shakllarga ega klasterlarni topish va juda katta ma'lumotlar to'plamlari uchun qismlarga bo'lishga asoslangan usullarni kengaytirish kerak. Bo'limga asoslangan klasterlash usullari 10.2-bo'limda chuqur o'rganilgan.
Ierarxik usullar: Ierarxik usul berilgan ma'lumotlar ob'ektlari to'plamining ierarxik dekompozitsiyasini yaratadi. Ierarxik usulni ierarxik parchalanish qanday shakllanganiga qarab aglomerativ yoki bo'linuvchi deb tasniflash mumkin. Aglomerativ yondashuv, shuningdek, pastdan yuqoriga yondashuv deb ataladi, har bir ob'ekt alohida guruhni tashkil qilishdan boshlanadi. U barcha guruhlar bittaga (ierarxiyaning eng yuqori darajasi) birlashtirilmaguncha yoki tugatish sharti bajarilmaguncha bir-biriga yaqin bo'lgan ob'ektlar yoki guruhlarni muvaffaqiyatli birlashtiradi. Yuqoridan pastga yondashuv deb ham ataladigan bo'linuvchi yondashuv bir xil klasterdagi barcha ob'ektlardan boshlanadi. Har bir ketma-ket iteratsiyada klaster kichikroq klasterlarga bo'linadi, natijada har bir ob'ekt bitta klasterda bo'lguncha yoki tugatish sharti bajariladi. Ierarxik klasterlash usullari masofaga asoslangan yoki zichlik va uzluksizlikka asoslangan bo'lishi mumkin. Ierarxik usullarning turli kengaytmalari kichik bo'shliqlarda klasterlashni ham ko'rib chiqadi.
Ierarxik usullar bir marta (birlashtirish yoki bo'linish) bir marta bajarilgandan so'ng, uni hech qachon bekor qilib bo'lmasligidan aziyat chekadi. Ushbu qat'iylik foydalidir, chunki u turli xil tanlovlarning kombinatsiyalangan soni haqida tashvishlanmaslik uchun kichik hisoblash xarajatlariga olib keladi. Bunday texnikalar noto'g'ri qarorlarni tuzata olmaydi; ammo ierarxik klasterlash sifatini oshirish usullari taklif qilingan. Ierarxik klasterlash usullari 10.3-bo'limda o'rganilgan.
Zichlikka asoslangan usullar: Ko'pgina qismlarga ajratish usullari ob'ektlar orasidagi masofaga qarab ob'ektlarni klasterlashadi. Bunday usullar faqat sharsimon klasterlarni topishi mumkin va ixtiyoriy shakllarning klasterlarini topishda qiyinchiliklarga duch keladi. Zichlik tushunchasi asosida boshqa klasterlash usullari ishlab chiqilgan. Ularning umumiy g'oyasi "mahalladagi" zichlik (ob'ektlar yoki ma'lumotlar punktlari soni) ma'lum bir chegaradan oshib ketguncha, ma'lum bir klasterni o'stirishni davom ettirishdir. Masalan, ma'lum bir klaster ichidagi har bir ma'lumot nuqtasi uchun ma'lum radiusning qo'shnisi kamida minimal sonli nuqtalarni o'z ichiga olishi kerak. Bunday usul shovqinni yoki chetga chiqishni filtrlash va o'zboshimchalik shaklidagi klasterlarni aniqlash uchun ishlatilishi mumkin.

Zichlikka asoslangan usullar ob'ektlar to'plamini bir nechta eksklyuziv klasterlarga yoki klasterlar ierarxiyasiga bo'lishi mumkin. Odatda, zichlikka asoslangan usullar faqat eksklyuziv klasterlarni ko'rib chiqadi va loyqa klasterlarni hisobga olmaydi. Bundan tashqari, zichlikka asoslangan usullar to'liq fazodan pastki fazo klasteriga qadar kengaytirilishi mumkin. Zichlikka asoslangan klasterlash usullari 0.4-bo'limda o'rganilgan.

To'rga asoslangan usullar: To'rga asoslangan usullar ob'ekt bo'shlig'ini to'r strukturasini tashkil etuvchi chekli sonli hujayralarga kvantlashtiradi. Barcha klasterlash operatsiyalari tarmoq strukturasida (ya'ni, kvantlangan fazoda) amalga oshiriladi. Ushbu yondashuvning asosiy afzalligi uning tez ishlov berish vaqti bo'lib, u odatda ma'lumotlar ob'ektlari sonidan mustaqil va faqat kvantlangan fazodagi har bir o'lchamdagi hujayralar soniga bog'liq.
To'rlardan foydalanish ko'pincha fazoviy ma'lumotlarni qidirishning ko'plab muammolariga, shu jumladan klasterlashtirishga samarali yondashuvdir. Shuning uchun gridga asoslangan usullar zichlikka asoslangan usullar va ierarxik usullar kabi boshqa klasterlash usullari bilan birlashtirilishi mumkin. Gridga asoslangan klasterlash 10.5-bo'limda o'rganilgan.
Ushbu usullar 10.1-rasmda qisqacha tavsiflangan. Ba'zi klasterlash algoritmlari bir nechta klasterlash usullarining g'oyalarini birlashtiradi, shuning uchun berilgan algoritmni faqat bitta klasterlash usuli toifasiga xos tarzda tasniflash ba'zan qiyin. Bundan tashqari, ba'zi ilovalar bir nechta klasterlash usullarini birlashtirishni talab qiladigan klasterlash mezonlariga ega bo'lishi mumkin.
Zichlikka asoslangan usullar ob'ektlar to'plamini bir nechta eksklyuziv klasterlarga yoki klasterlar ierarxiyasiga bo'lishi mumkin. Odatda, zichlikka asoslangan usullar faqat eksklyuziv klasterlarni ko'rib chiqadi va loyqa klasterlarni hisobga olmaydi. Bundan tashqari, zichlikka asoslangan usullar to'liq fazodan pastki fazo klasteriga qadar kengaytirilishi mumkin. Zichlikka asoslangan klasterlash usullari 0.4-bo'limda o'rganilgan.
To'rga asoslangan usullar: To'rga asoslangan usullar ob'ekt bo'shlig'ini to'r strukturasini tashkil etuvchi chekli sonli hujayralarga kvantlashtiradi. Barcha klasterlash operatsiyalari tarmoq strukturasida (ya'ni, kvantlangan fazoda) amalga oshiriladi. Ushbu yondashuvning asosiy afzalligi uning tez ishlov berish vaqti bo'lib, u odatda ma'lumotlar ob'ektlari sonidan mustaqil va faqat kvantlangan fazodagi har bir o'lchamdagi hujayralar soniga bog'liq.
To'rlardan foydalanish ko'pincha fazoviy ma'lumotlarni qidirishning ko'plab muammolariga, shu jumladan klasterlashtirishga samarali yondashuvdir. Shuning uchun gridga asoslangan usullar zichlikka asoslangan usullar va ierarxik usullar kabi boshqa klasterlash usullari bilan birlashtirilishi mumkin. Gridga asoslangan klasterlash 10.5-bo'limda o'rganilgan.
U
shbu usullar 10.1-rasmda qisqacha tavsiflangan. Ba'zi klasterlash algoritmlari bir nechta klasterlash usullarining g'oyalarini birlashtiradi, shuning uchun berilgan algoritmni faqat bitta klasterlash usuli toifasiga xos tarzda tasniflash ba'zan qiyin. Bundan tashqari, ba'zi ilovalar bir nechta klasterlash usullarini birlashtirishni talab qiladigan klasterlash mezonlariga ega bo'lishi mumkin.
1-rasm: Ushbu bobda muhokama qilingan klasterlash usullarining umumiy ko'rinishi. E'tibor bering, ba'zi algoritmlar turli usullarni birlashtirishi mumkin.


Keyingi bo'limlarda biz har bir klasterlash usulini batafsil ko'rib chiqamiz. Klasterlashning ilg'or usullari va tegishli masalalar 11-bobda ko'rib chiqiladi. Umuman olganda, quyidagi belgilar qo'llaniladi. D klasterlashtiriladigan n ta ob'ektdan iborat ma'lumotlar to'plami bo'lsin. Ob'ekt d o'zgaruvchilar bilan tavsiflanadi, bu erda har bir o'zgaruvchi atribut yoki o'lchov deb ham ataladi va shuning uchun d o'lchovli ob'ekt fazosidagi nuqta deb ham atalishi mumkin. Ob'ektlar qalin kursiv shrift bilan ifodalanadi (masalan, p).