Klasterlash usuli - bu bir guruhdagi ob'ektlar to'plamini boshqa tarmoqlardagi ob'ektlarga qaraganda bir-biriga o'xshash tarzda guruhlash vazifasi. Bu maʼlumotlarni qidirishning asosiy vazifasi va koʻplab sohalarda qoʻllaniladigan umumiy statistik tahlil texnikasi, jumladan, mashinani oʻrganish, naqshni aniqlash, tasvirni aniqlash, axborotni qidirish, maʼlumotlarni siqish va kompyuter grafikasi.
Optimallashtirish muammosi
Klasterlash usulining oʻzi bitta aniq algoritm emas, balki hal qilinishi kerak boʻlgan umumiy vazifadir. Bunga guruh nimadan iboratligini va uni qanday samarali topishni tushunishda sezilarli darajada farq qiluvchi turli xil algoritmlar yordamida erishish mumkin. Metamavzularni shakllantirish uchun klasterlash usulidan foydalanish guruhdan foydalanishni o'z ichiga oladia'zolar orasidagi kichik masofalar, bo'shliqning zich hududlari, intervallar yoki ma'lum statistik taqsimotlar. Shuning uchun klasterlash ko‘p maqsadli optimallashtirish muammosi sifatida shakllantirilishi mumkin.
Tegishli usul va parametr sozlamalari (jumladan, foydalaniladigan masofa funksiyasi, zichlik chegarasi yoki kutilayotgan klasterlar soni kabi elementlar) individual maʼlumotlar toʻplamiga va natijalardan maqsadli foydalanishga bogʻliq. Tahlil avtomatik vazifa emas, balki bilimlarni kashf qilish yoki interaktiv ko'p maqsadli optimallashtirishning iterativ jarayonidir. Ushbu klasterlash usuli sinov va xato urinishlarini o'z ichiga oladi. Natija kerakli xususiyatlarga erishilgunga qadar tez-tez ma'lumotlarni qayta ishlash va model parametrlarini o'zgartirish kerak bo'ladi.
“Klasterlash” atamasi bilan bir qatorda avtomatik tasnif, sonli taksonomiya, botriologiya va tipologik tahlil kabi ma’nolari o’xshash bir qancha so’zlar ham mavjud. Nozik farqlar ko'pincha metasub'ekt munosabatlarini shakllantirish uchun klasterlash usulidan foydalanishda yotadi. Ma'lumot olishda natijada paydo bo'lgan guruhlar qiziqish uyg'otsa-da, avtomatik tasniflashda bu funktsiyalarni bajaradigan diskriminatsion kuch allaqachon mavjud.
Klaster tahlili 1932-yilda Kroberning koʻplab ishlariga asoslangan edi. U 1938 yilda Zubin va 1939 yilda Robert Tryon tomonidan psixologiyaga kiritilgan. Va bu ishlardan Cattell 1943 yildan beri nazariy jihatdan klasterlash usullarining tasnifini ko'rsatish uchun ishlatib kelinmoqda.
Muddat
"Klaster" tushunchasiga aniq ta'rif berib bo'lmaydi. Bu juda ko'p klasterlash usullari mavjudligining sabablaridan biridir. Umumiy maxraj mavjud: ma'lumotlar ob'ektlari guruhi. Biroq, turli tadqiqotchilar turli modellardan foydalanadilar. Klasterlash usullaridan foydalanishning har biri turli ma'lumotlarni o'z ichiga oladi. Turli xil algoritmlar tomonidan topilgan tushuncha o'z xususiyatlarida sezilarli darajada farqlanadi.
Klasterlash usulidan foydalanish ko'rsatmalar orasidagi farqni tushunishning kalitidir. Odatda klaster naqshlari quyidagilardan iborat:
- Centroid s. Bu, masalan, k-maʼnolarni klasterlash har bir klasterni bitta oʻrtacha vektor bilan ifodalaganida.
- Ulanish modeli s. Bu, masalan, masofaviy ulanishga asoslangan modellarni yaratadigan ierarxik klasterlash.
- Taqsimot modeli s. Bunday holda, klasterlar metamavzular bo'yicha statistik taqsimotlarni shakllantirish uchun klasterlash usuli yordamida modellashtiriladi. Kutishni maksimallashtirish algoritmiga taalluqli koʻp oʻlchovli normal ajratish kabi.
- Zichlik modeli s. Bular, masalan, DBSCAN (shovqin bilan fazoviy klasterlash algoritmi) va OPTICS (Tuzilishni aniqlash uchun tartib nuqtalari), ular klasterlarni maʼlumotlar maydonida ulangan zich hududlar sifatida belgilaydi.
- Subpace modeli c. Ikki klasterlashda (shuningdek, birgalikda klasterlash yoki ikkita rejim deb ataladi) guruhlar ikkala element va tegishli atributlar bilan modellashtiriladi.
- Model s. Ba'zi algoritmlarda bunday emasmeta-mavzu natijalarini yaratish va shunchaki ma'lumotni guruhlashni ta'minlash uchun ularning klasterlash usuli uchun aniqlangan aloqa.
- S grafik asosidagi model. Klik, ya'ni chekka qismidagi har ikkita ulanishni klaster shaklining prototipi sifatida ko'rib chiqish mumkin bo'lgan tugunlarning kichik to'plami. Umumiy talabning zaiflashishi kvazi-kliklar deb ataladi. Aynan shu nom HCS klasterlash algoritmida keltirilgan.
- Neyron modellar s. Eng mashhur nazoratsiz tarmoq o'z-o'zini tashkil qiluvchi xaritadir. Va aynan shu modellar odatda meta-mavzu natijalarini shakllantirish uchun yuqoridagi klasterlash usullaridan biriga yoki bir nechtasiga o'xshash sifatida tavsiflanishi mumkin. U neyron tarmoqlar asosiy yoki mustaqil komponentlar tahlilining zarur shaklini amalga oshiradigan subkosmik tizimlarni oʻz ichiga oladi.
Bu atama, aslida, ma'lumotlarni klasterlash usullari to'plamidagi barcha ob'ektlarni o'z ichiga olgan bunday guruhlar to'plamidir. Bundan tashqari, u bir-biriga o'rnatilgan tizimlar ierarxiyasi kabi klasterlarning bir-biriga munosabatini ko'rsatishi mumkin. Guruhlash quyidagi jihatlarga bo'linishi mumkin:
- Qattiq centroid klasterlash usuli. Bu yerda har bir obyekt guruhga tegishli yoki undan tashqarida.
- Yumshoq yoki loyqa tizim. Bu vaqtda har bir ob'ekt ma'lum darajada har qanday klasterga tegishli. Bu, shuningdek, c-means loyqa klasterlash usuli deb ataladi.
Va boshqa nozik farqlar ham mumkin. Masalan:
- Qat'iy qismlarga ajratish klasteri. Bu yerdahar bir obyekt aynan bitta guruhga tegishli.
- Chet koʻrsatkichlar bilan qatʼiy qismlarga ajratish. Bunday holda, ob'ektlar ham klasterga tegishli bo'lmasligi va keraksiz deb hisoblanishi mumkin.
- Bir-biriga oʻxshash klasterlash (shuningdek, muqobil, bir nechta koʻrish bilan). Bu erda ob'ektlar bir nechta filiallarga tegishli bo'lishi mumkin. Odatda qattiq klasterlarni o'z ichiga oladi.
- Ierarxik klasterlash usullari. Bolalar guruhiga tegishli ob'ektlar ham asosiy quyi tizimga tegishli.
- Kostki fazoning shakllanishi. Bir-biriga o'xshash klasterlarga o'xshash bo'lsa-da, noyob belgilangan tizimda o'zaro guruhlar bir-biriga mos kelmasligi kerak.
Koʻrsatmalar
Yuqorida aytib o'tilganidek, klasterlash algoritmlarini klaster modeli asosida tasniflash mumkin. Quyidagi sharhda ushbu ko'rsatmalarning faqat eng mashhur misollari keltirilgan. 100 dan ortiq eʼlon qilingan algoritmlar boʻlishi mumkinligi sababli, hamma ham oʻz klasterlari uchun modellarni taqdim etavermaydi va shuning uchun ularni osongina tasniflab boʻlmaydi.
Obyektiv ravishda toʻgʻri klasterlash algoritmi yoʻq. Ammo, yuqorida aytib o'tilganidek, ko'rsatma har doim kuzatuvchining ko'rish sohasida bo'ladi. Muayyan muammo uchun eng mos klasterlash algoritmi, agar bir modelni boshqasidan ustun qo'yish uchun matematik sabab bo'lmasa, ko'pincha eksperimental ravishda tanlanishi kerak. Shuni ta'kidlash kerakki, bitta turga mo'ljallangan algoritm odatda ishlamayditubdan boshqa mavzuni o'z ichiga olgan ma'lumotlar to'plami. Masalan, k-vositalar qavariq bo'lmagan guruhlarni topa olmaydi.
Ulanishga asoslangan klasterlash
Ushbu ittifoq oʻz nomi bilan ham tanilgan, ierarxik model. U ob'ektlar uzoqroqda joylashgan qismlarga qaraganda qo'shni qismlarga ko'proq bog'langan degan odatiy fikrga asoslanadi. Bu algoritmlar ob'ektlarni bir-biriga bog'lab, ularning masofasiga qarab turli klasterlarni hosil qiladi. Guruhni asosan klasterning turli qismlarini ulash uchun zarur bo'lgan maksimal masofa bilan tavsiflash mumkin. Barcha mumkin bo'lgan masofalarda dendrogramma yordamida ifodalanishi mumkin bo'lgan boshqa guruhlar hosil bo'ladi. Bu "ierarxik klasterlash" umumiy nomi qayerdan kelganligini tushuntiradi. Ya'ni, bu algoritmlar ma'lumotlar to'plamining yagona bo'limini ta'minlamaydi, aksincha, vakolatning keng tartibini ta'minlaydi. Unga rahmat, ma'lum masofalarda bir-biri bilan drenaj mavjud. Dendrogrammada y o'qi klasterlarning birikish masofasini bildiradi. Guruhlar aralashmasligi uchun ob'ektlar X chizig'i bo'ylab joylashtirilgan.
Ulanishga asoslangan klasterlash - bu masofalarni hisoblashda farq qiluvchi usullarning butun oilasi. Masofa funktsiyalarining odatiy tanlovidan tashqari, foydalanuvchi ulanish mezonini ham hal qilishi kerak. Klaster bir nechta ob'ektlardan iborat bo'lganligi sababli, uni hisoblashning ko'plab variantlari mavjud. Ommabop tanlov bitta tutqichli guruhlash deb nomlanadi, bu usulUPGMA yoki WPGMA ni o'z ichiga olgan to'liq havola (o'rtacha arifmetik bo'lgan, shuningdek, o'rtacha havola klasteri sifatida ham tanilgan, vaznsiz yoki vaznli juftlik ansambli). Bundan tashqari, ierarxik tizim aglomerativ (alohida elementlardan boshlab va ularni guruhlarga birlashtirish) yoki bo‘linuvchi (to‘liq ma’lumotlar to‘plamidan boshlab va uni bo‘limlarga bo‘lish) bo‘lishi mumkin.
Taqsimlangan klasterlash
Bu modellar boʻlinishlarga asoslangan statistik maʼlumotlar bilan chambarchas bogʻliq. Klasterlarni bir xil taqsimotga tegishli bo'lgan ob'ektlar sifatida osongina aniqlash mumkin. Ushbu yondashuvning qulay xususiyati shundaki, u sun'iy ma'lumotlar to'plamini yaratish usuliga juda o'xshaydi. Taqsimotdan tasodifiy ob'ektlarni tanlash orqali.
Ushbu usullarning nazariy asoslari mukammal boʻlsa-da, modelning murakkabligiga cheklovlar qoʻyilmasa, ular haddan tashqari moslashish deb nomlanuvchi asosiy muammodan aziyat chekadi. Kattaroq assotsiatsiya odatda maʼlumotlarni yaxshiroq tushuntiradi, bu esa toʻgʻri usulni tanlashni qiyinlashtiradi.
Gauss aralashmasi modeli
Ushbu usul barcha turdagi kutishlarni maksimallashtirish algoritmlaridan foydalanadi. Bu erda ma'lumotlar to'plami odatda tasodifiy ishga tushirilgan va parametrlari ma'lumotlar to'plamiga yaxshiroq moslashish uchun iterativ optimallashtirilgan Gauss taqsimotlarining qat'iy soni bilan modellashtiriladi. Ushbu tizim mahalliy optimalga yaqinlashadi. Shuning uchun bir nechta yugurishlar berishi mumkinturli natijalar. Eng qattiq klasterni olish uchun xususiyatlar ko'pincha ular tegishli bo'lgan Gauss taqsimotiga tayinlanadi. Yumshoqroq guruhlar uchun esa bu shart emas.
Taqsimotga asoslangan klasterlash atributlar oʻrtasidagi bogʻliqlik va bogʻliqlikni aniqlay oladigan murakkab modellarni yaratadi. Biroq, bu algoritmlar foydalanuvchiga qo'shimcha yuklaydi. Ko'pgina real dunyo ma'lumotlar to'plamlari uchun qisqacha aniqlangan matematik model bo'lmasligi mumkin (masalan, Gauss taqsimotini juda kuchli taxmin deb hisoblasak).
Zichlikka asoslangan klasterlash
Ushbu misolda guruhlar asosan maʼlumotlar toʻplamining qolgan qismiga qaraganda yuqori oʻtkazuvchanlikka ega boʻlgan hududlar sifatida belgilangan. Barcha komponentlarni ajratish uchun zarur boʻlgan ushbu noyob qismlardagi obyektlar odatda shovqin va chekka nuqtalar hisoblanadi.
Eng mashhur zichlikka asoslangan klasterlash usuli DBSCAN (Spatial Noise Clustering Algoritm) hisoblanadi. Ko'pgina yangi usullardan farqli o'laroq, u "zichlikka erishish imkoniyati" deb nomlangan aniq belgilangan klaster komponentiga ega. Bog'lanishga asoslangan klasterlash kabi, u ma'lum masofa chegaralaridagi ulanish nuqtalariga asoslanadi. Biroq, bu usul faqat zichlik mezoniga javob beradigan narsalarni to'playdi. Ushbu radiusdagi boshqa ob'ektlarning minimal soni sifatida belgilangan asl versiyada klaster barcha elementlardan iborat.zichlikka oid elementlar (boshqa usullardan farqli ravishda erkin shakldagi guruhni tashkil qilishi mumkin) va ruxsat etilgan diapazondagi barcha ob'ektlar.
DBSCAN-ning yana bir qiziqarli xususiyati shundaki, uning murakkabligi ancha past - bu ma'lumotlar bazasiga nisbatan chiziqli qator so'rovlarni talab qiladi. Va g'ayrioddiy narsa shundaki, u har bir ishda deyarli bir xil natijalarni topadi (bu asosiy va shovqin nuqtalari uchun deterministik, lekin chegara elementlari uchun emas). Shuning uchun uni bir necha marta ishga tushirishning hojati yo'q.
DBSCAN va OPTICS ning asosiy kamchiligi shundaki, ular klaster chegaralarini aniqlash uchun zichlikning biroz pasayishini kutishadi. Masalan, Gauss taqsimotlari bir-biriga o'xshash bo'lgan ma'lumotlar to'plamlarida - sun'iy ob'ektlar uchun umumiy foydalanish holati - bu algoritmlar tomonidan yaratilgan klaster chegaralari ko'pincha o'zboshimchalik bilan ko'rinadi. Bu guruhlarning zichligi doimiy ravishda kamayib borayotganligi sababli sodir bo'ladi. Va Gauss aralashmasi ma'lumotlar to'plamida bu algoritmlar deyarli har doim bunday tizimlarni aniq modellashtirishga qodir bo'lgan EM klasterlash kabi usullardan ustun turadi.
Oʻrtacha siljish - bu klasterlash usuli boʻlib, unda har bir obʼyekt butun yadroni baholash asosida yaqin atrofdagi eng zich hududga oʻtadi. Oxir-oqibat, ob'ektlar mahalliy o'tkazmaslik maksimallariga yaqinlashadi. K-vositalari klasterlashiga o'xshab, bu "zichlik jalb qiluvchilar" ma'lumotlar to'plamining vakili bo'lib xizmat qilishi mumkin. Ammo o'rtacha siljishDBSCAN ga o'xshash o'zboshimchalik bilan shakllangan klasterlarni aniqlay oladi. Qimmatbaho iterativ protsedura va zichlikni baholash tufayli o'rtacha siljish odatda DBSCAN yoki k-Means ga qaraganda sekinroq bo'ladi. Bundan tashqari, odatdagi siljish algoritmini yuqori o'lchamli ma'lumotlarga qo'llash yadro zichligi taxminining bir xil bo'lmagan harakati tufayli qiyin, bu klaster dumlarining haddan tashqari parchalanishiga olib keladi.
Reyting
Klasterlash natijalarini tekshirish xuddi klasterlash kabi qiyin. Ommabop yondashuvlar orasida "ichki" baholash (tizim yagona sifat ko'rsatkichiga tushiriladi) va, albatta, "tashqi" ball (bu erda klasterlash mavjud "asosiy haqiqat" tasnifi bilan taqqoslanadi). Mutaxassisning qo‘lda qo‘llagan balli va bilvosita bahosi mo‘ljallangan ilovada klasterlashning foydaliligini tekshirish orqali topiladi.
Ichki bayroq oʻlchovlari klasterlash maqsadlari deb hisoblanishi mumkin boʻlgan xususiyatlarni ifodalash muammosidan aziyat chekadi. Masalan, Silhouette koeffitsienti bo'yicha berilgan ma'lumotlarni guruhlash mumkin, faqat buni amalga oshirish uchun ma'lum samarali algoritm mavjud emas. Baholash uchun bunday ichki o'lchovdan foydalanib, optimallashtirish muammolarining o'xshashligini solishtirish yaxshiroqdir.
Tashqi belgida ham xuddi shunday muammolar mavjud. Agar "asosiy haqiqat" ning bunday yorliqlari mavjud bo'lsa, unda klasterlashning hojati yo'q. Va amaliy dasturlarda, odatda, bunday tushunchalar mavjud emas. Boshqa tomondan, teglar ma'lumotlar to'plamining faqat bitta mumkin bo'lgan qismini aks ettiradi, bu degani emasboshqa (balki undan ham yaxshiroq) klaster yo'qligi.
Demak, bu yondashuvlarning hech biri oxir-oqibat haqiqiy sifatni baholay olmaydi. Ammo bu juda sub'ektiv bo'lgan insoniy baholashni talab qiladi. Shunga qaramay, bunday statistika yomon klasterlarni aniqlashda informatsion bo'lishi mumkin. Lekin insonning sub'ektiv bahosini bekor qilmaslik kerak.
Ichki belgi
Klasterlash natijasi oʻzi klasterlangan maʼlumotlar asosida baholansa, bu atama deb ataladi. Bu usullar, odatda, eng yaxshi natijani guruhlar ichida o'xshashligi yuqori va guruhlar orasida past bo'lgan guruhlarni yaratadigan algoritmga beradi. Klaster baholashda ichki mezonlardan foydalanishning kamchiliklaridan biri shundaki, yuqori ball ma’lumotlarni qidirishda samarali dasturlarga olib kelishi shart emas. Bundan tashqari, bu ball bir xil modeldan foydalanadigan algoritmlarga qarama-qarshidir. Masalan, k-klasterlash funksiya masofalarini tabiiy ravishda optimallashtirishni anglatadi va unga asoslangan ichki mezon natijasida hosil bo'lgan klasterni ortiqcha baholashi mumkin.
Shuning uchun, ushbu baholash choralari bir algoritm boshqasidan yaxshiroq ishlaydigan vaziyatlar haqida tasavvurga ega bo'lish uchun eng mos keladi. Ammo bu har bir ma'lumot boshqalarga qaraganda ishonchliroq natijalar beradi degani emas. Bunday indeks bilan o'lchanadigan amal qilish muddati strukturaning ma'lumotlar to'plamida mavjudligi haqidagi tasdiqga bog'liq. Ba'zi turlar uchun ishlab chiqilgan algoritm, agar to'plamda radikal bo'lsa, hech qanday imkoniyat yo'qturli tarkib yoki agar baholash turli mezonlarni o'lchaydi. Misol uchun, k-o'rtacha klasterlash faqat qavariq klasterlarni topishi mumkin va ko'p ball indekslari bir xil formatni qabul qiladi. Qavariq boʻlmagan modellarga ega maʼlumotlar toʻplamida k-oʻrtacha va odatiy baholash mezonlaridan foydalanish nooʻrin.
Tashqi baholash
Bunday toʻplash bilan klasterlash natijalari guruhlashda foydalanilmagan maʼlumotlar asosida baholanadi. Ya'ni, ma'lum sinf belgilari va tashqi testlar kabi. Bunday savollar oldindan tasniflangan narsalar to'plamidan iborat bo'lib, ko'pincha mutaxassislar (odamlar) tomonidan yaratiladi. Shunday qilib, ma'lumot to'plamlarini baholash uchun oltin standart sifatida ko'rish mumkin. Ushbu turdagi baholash usullari klasterlash berilgan mos yozuvlar sinflariga qanchalik yaqinligini o'lchaydi. Biroq, yaqinda bu haqiqiy ma'lumotlar uchun yoki faqat haqiqiy asosli haqiqatga ega bo'lgan sintetik to'plamlar uchun etarlimi yoki yo'qmi, muhokama qilindi. Chunki sinflar ichki tuzilishga ega bo'lishi mumkin va mavjud atributlar klasterlarni ajratishga imkon bermasligi mumkin. Bundan tashqari, bilimlarni kashf qilish nuqtai nazaridan, ma'lum faktlarni takrorlash kutilgan natijani berishi shart emas. Guruhlash jarayonida meta-ma'lumotlar (masalan, sinf yorliqlari) allaqachon qo'llaniladigan maxsus cheklangan klasterlash stsenariysida baholash uchun barcha ma'lumotlarni saqlash ahamiyatsiz emas.
Endi klasterlash usullariga nima taalluqli emasligi va bu maqsadlar uchun qanday modellar qoʻllanilishi aniq boʻldi.
