Olim yo Scalability: Ko'pgina klasterlash algoritmlari bir necha yuzdan kam ma'lumotlar ob'ektini o'z ichiga olgan kichik ma'lumotlar to'plamlarida yaxshi ishlaydi

Download 27,97 Kb.
Sana	17.01.2024
Hajmi	27,97 Kb.
	#139716

Bog'liq
10. Klaster tahlili Asosiy tushunchalar va usullar Tasavvur qili-fayllar.org

xmlns:w="urn:schemas-microsoft-com:office:word"
xmlns="http://www.w3.org/TR/REC-html40">
10. Klaster tahlili Asosiy tushunchalar va usullar Tasavvur qiling-a, siz AllElectronics kompaniyasining mijozlar bilan aloqalar bo'yicha direktorisiz va sizda beshta menejer ishlaydi
Olim yo Scalability: Ko'pgina klasterlash algoritmlari bir necha yuzdan kam ma'lumotlar ob'ektini o'z ichiga olgan kichik ma'lumotlar to'plamlarida yaxshi ishlaydi; ammo, katta ma'lumotlar bazasi millionlab yoki hatto milliardlab ob'ektlarni o'z ichiga olishi mumkin, ayniqsa veb-qidiruv stsenariylarida. Katta ma'lumotlar to'plamining faqat namunasi bo'yicha klasterlash noto'g'ri natijalarga olib kelishi mumkin. Shuning uchun yuqori darajada kengaytiriladigan klasterlash algoritmlari kerak.
Ixtiyoriy shaklga ega bo'lgan klasterlarni kashf qilish: Ko'pgina klasterlash algoritmlari Evklid yoki Manxetten masofa o'lchovlari asosida klasterlarni aniqlaydi (2-bob). Bunday masofaviy o'lchovlarga asoslangan algoritmlar o'xshash o'lcham va zichlikka ega bo'lgan sferik klasterlarni topishga moyildir. Biroq, klaster har qanday shaklda bo'lishi mumkin. Masalan, atrof-muhitni nazorat qilish uchun tez-tez ishlatiladigan sensorlarni ko'rib chiqing. Sensor ko'rsatkichlari bo'yicha klaster tahlili qiziqarli hodisalarni aniqlashi mumkin. Ko'pincha sharsimon bo'lmagan o'rmon yong'inlari chegarasini topish uchun klasterlashdan foydalanishni xohlashimiz mumkin. Ixtiyoriy shakllarning klasterlarini aniqlay oladigan algoritmlarni ishlab chiqish muhimdir.
Shovqinli ma'lumotlar bilan ishlash qobiliyati: Aksariyat real ma'lumotlar to'plamlari chet va/yoki etishmayotgan, noma'lum yoki noto'g'ri ma'lumotlarni o'z ichiga oladi. Sensor ko'rsatkichlari, masalan, ko'pincha shovqinli bo'ladi - ba'zi ko'rsatkichlar sezgir mexanizmlar tufayli noto'g'ri bo'lishi mumkin va ba'zi o'qishlar atrofdagi vaqtinchalik ob'ektlarning shovqinlari tufayli noto'g'ri bo'lishi mumkin. Klasterlash algoritmlari bunday shovqinlarga sezgir bo'lishi va sifatsiz klasterlarni keltirib chiqarishi mumkin. Shuning uchun bizga shovqinga chidamli klasterlash usullari kerak.
Yuqori o'lchamli ma'lumotlarni klasterlash imkoniyati: Ma'lumotlar to'plamida ko'plab o'lchamlar yoki atributlar bo'lishi mumkin. Hujjatlarni klasterlashda, masalan, har bir kalit so'z o'lchov sifatida ko'rib chiqilishi mumkin va ko'pincha minglab kalit so'zlar mavjud. Ko'pgina klasterlash algoritmlari faqat ikki yoki uch o'lchovli ma'lumotlar to'plami kabi past o'lchamli ma'lumotlarni qayta ishlashda yaxshi. Yuqori o'lchamli makonda ma'lumotlar ob'ektlarining klasterlarini topish juda qiyin, ayniqsa bunday ma'lumotlar juda siyrak va juda egri bo'lishi mumkinligini hisobga olsak.
Talqin qilish va foydalanish qulayligi: foydalanuvchilar klasterlash natijalarini izohlash, tushunarli va foydalanishga yaroqli bo'lishini xohlashadi. Ya'ni, klasterlash muayyan semantik talqinlar va ilovalar bilan bog'lanishi kerak bo'lishi mumkin. Ilova maqsadi klasterlash xususiyatlari va klasterlash usullarini tanlashga qanday ta'sir qilishi mumkinligini o'rganish muhimdir.
Quyida klasterlash usullarini solishtirish mumkin bo'lgan ortogonal jihatlar keltirilgan:
siyosatsportfutbolbasketbol beysbol" va "xokkey" "sport" sub mavzulari sifatida mavjud bo'lishi mumkin. So'nggi to'rtta submavzu ierarxiyada "sport" ga qaraganda pastroq darajada.
O'xshashlik o'lchovi: Ba'zi usullar ikki ob'ekt orasidagi o'xshashlikni ular orasidagi masofaga qarab aniqlaydi. Bunday masofani Evklid fazosi, yo'l tarmog'i, vektor fazosi yoki boshqa fazoda aniqlash mumkin. Boshqa usullarda o'xshashlik zichlik yoki yaqinlik asosida bog'lanish bilan aniqlanishi mumkin va ikki ob'ekt orasidagi mutlaq masofaga tayanmasligi mumkin. O'xshashlik ko'rsatkichlari klasterlash usullarini loyihalashda asosiy rol o'ynaydi. Masofaga asoslangan usullar ko'pincha optimallashtirish usullaridan foydalanishi mumkin bo'lsa-da, zichlik va uzluksizlikka asoslangan usullar ko'pincha ixtiyoriy shakldagi klasterlarni topishi mumkin.
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.
10.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).
http://fayllar.org

Download 27,97 Kb.