Centroid-ga asoslangan klasterlash algoritmlari / bo‘linuvchi klasterlash algoritmlari

|
Centroid-ga asoslangan klasterlash algoritmlari / bo‘linuvchi klasterlash algoritmlari
|
bet | 4/7 | Sana | 14.05.2024 | Hajmi | 386,96 Kb. | | #232960 |
Centroid-ga asoslangan klasterlash algoritmlari / bo‘linuvchi klasterlash algoritmlari
Centroid/bo'limli klasterlashda klasterlar markaziy vektor bilan ifodalanadi, bu ma'lumotlar to'plamining a'zosi bo'lishi shart emas. Hatto ushbu maxsus klasterlash turida ham K qiymatini tanlash kerak. Bu optimallashtirish muammosi: markazlar sonini yoki K qiymatini topish va ob'ektlarni yaqin atrofdagi klaster markazlariga belgilash. Ushbu qadamlar klasterlardan kvadrat masofa maksimal bo'ladigan tarzda bajarilishi kerak.
Keng qo'llaniladigan centroid asosidagi klasterlash algoritmlaridan biri K-Means bo'lib, uning kamchiliklaridan biri K qiymatini oldindan tanlash kerakligidir.
K-Means algoritmi berilgan ma'lumotlar to'plamini ma'lum masofa o'lchovidan foydalangan holda oldindan belgilangan (K) klasterlar soniga ajratadi. Har bir klaster/guruhning markazi centroid deb ataladi.
K-Means algoritmi qanday ishlaydi?
Dastlab, K sonli centroidlar tanlanadi. K uchun to'g'ri qiymatni tanlashning turli usullari mavjud.
Ma'lumotlarni aralashtirib yuboring va centroidlarni ishga tushiring - almashtirmasdan centroidlar uchun K ma'lumot nuqtalarini tasodifiy tanlang.
Har bir oldingi markazga tayinlangan barcha namunalarning o'rtacha qiymatini hisoblab, yangi markazlarni yarating.
Markazda hech qanday o'zgarish bo'lmaguncha markazni tasodifiy ishga tushiring, shuning uchun ma'lumotlar nuqtalarining klasterga tayinlanishi o'zgarmaydi.
K-Means klasterlash nuqtalar orasidagi masofani aniqlash uchun Evklid masofasidan foydalanadi.
Eslatma: K-Means klasterlash misoli quyidagi foydalanish holatlari bo'limida mijozlar segmentatsiyasi misollari bilan tushuntirilgan.
K ning to'g'ri qiymatini tanlashning ikkita usuli mavjud: tirsak va siluet.
Tirsak usuli
Tirsak usuli qiymatlar oralig'ini tanlaydi va ular orasidan eng yaxshisini oladi. U K ning turli qiymatlari uchun Kvadratning klaster yig'indisini (WCSS) hisoblaydi. Kvadrat nuqtalar yig'indisini hisoblab chiqadi va o'rtacha masofani hisoblaydi.
Yuqoridagi formulada Yi Xi ni kuzatish markazidir. WCSS pasayishni boshlagan joyda K qiymatini tanlash kerak. WCSS ga qarshi K syujetida bu tirsak shaklida ko'rinadi .
Siluet usuli
Silhouette ball/koeffitsienti (SC) har bir namuna uchun o'rtacha klaster ichidagi masofa (m) va eng yaqin klaster masofasining o'rtacha qiymati (n) yordamida hisoblanadi.
Yuqoridagi formulada n - ma'lumotlar nuqtasi va uning qismi bo'lmagan eng yaqin klaster orasidagi masofa. Biz barcha namunalar bo'yicha o'rtacha SCni hisoblashimiz va klasterlar sonini aniqlash uchun ko'rsatkich sifatida foydalanishimiz mumkin.
SC qiymati -1 dan 1 gacha o'zgarib turadi. 1 klasterlar yaxshi ajratilgan va ajralib turishini bildiradi. Agar qiymat -1 bo'lsa, klasterlar noto'g'ri tayinlangan.
Bular K-Means ning boshqa algoritmlarga nisbatan bir qancha afzalliklari:
Amalga oshirish oson.
U katta ma'lumotlar to'plamlari uchun kengaytirilishi mumkin, shuningdek, katta ma'lumotlar to'plamlari uchun tezroq.
U tez-tez yangi misollarga moslashadi.
K-Means algoritmi K-Means algoritmiga nisbatan yana bir klasterlash algoritmidir, bundan tashqari klaster markazlari mediana yordamida qayta hisoblab chiqiladi. Katta ma'lumotlar to'plamlari uchun median vektorni sekinroq hisoblash uchun tartiblash kerak bo'lganligi sababli, K-Media algoritmida chetdagilarga nisbatan sezgirlik kamroq.
K-Means ba'zi kamchiliklarga ega; K-Means klaster markazlarining tasodifiy ishga tushirilishi bilan boshlanganligi sababli algoritm turli yugurishlarda turli klasterlash natijalarini berishi mumkin. Imkoniyat shundaki, olingan natijalar takrorlanmasligi mumkin.
K-Means algoritmining boshqa kamchiliklari quyidagilardir:
K-Means klasterlash, agar klasterlar sharsimon shaklga ega bo'lsa, ma'lumotlar strukturasini olishda yaxshi. U har doim markaz atrofida chiroyli sharsimon shakl yaratishga harakat qiladi. Bu shuni anglatadiki, klasterlar turli xil geometrik shakllarga ega bo'lgan daqiqada K-Means ma'lumotlarni klasterlashda yomon ish qiladi.
Ma'lumotlar nuqtalari bir xil klasterga tegishli bo'lsa ham, K-Means ma'lumotlar nuqtalarini bir-biridan uzoqlashtirishga ruxsat bermaydi va ular bir xil klasterni baham ko'radi.
K-Means algoritmi o'zgaruvchan qiymatlarga sezgir.
O'lchovlar soni ortishi bilan o'lchovlilik kamayadi.
Klasterlash uchun K-Means dan foydalanishda eslash kerak bo'lgan ba'zi fikrlar:
K-Means algoritmini qo'llashda ma'lumotlarni standartlashtiring, chunki bu sizga sifatli klasterlarni olishga va klasterlash algoritmining ish faoliyatini yaxshilashga yordam beradi. K-Means ma'lumotlar nuqtalari orasidagi o'xshashlikni topish uchun masofaga asoslangan o'lchovdan foydalanganligi sababli, standart og'ish bir va o'rtacha nolga teng bo'lishi uchun ma'lumotlarni standartlashtirish yaxshidir. Odatda, har qanday ma'lumotlar to'plamida mavjud bo'lgan xususiyatlar turli o'lchov birliklariga ega bo'ladi, masalan, daromadga nisbatan yosh.
K-vositalari kattaroq klasterlarga ko'proq og'irlik beradi.
Klasterlar sonini tanlashda foydalaniladigan tirsak usuli yaxshi ishlamaydi, chunki xato funksiyasi barcha K.lar uchun kamayadi.
Agar klasterlar o'rtasida o'xshashlik bo'lsa, K-Means har bir ma'lumot nuqtasini qaysi klasterni belgilashni aniqlash uchun bir-biriga mos keladigan mintaqaga tegishli misollar uchun noaniqlik uchun ichki o'lchovga ega emas.
K-Means ma'lumotlarni klasterlash mumkin bo'lmasa ham, masalan, yagona taqsimotdan keladigan ma'lumotlar.
Mini-Batch K-Means klasterlash algoritmi
K-Means mashhur klasterlash algoritmlaridan biri bo'lib, u asosan yaxshi vaqt ishlashi tufayli. Ma'lumotlar to'plamining hajmi kattalashganda, K-Means xotira muammosiga olib keladi, chunki u butun ma'lumotlar to'plamiga muhtoj. Shu sabablarga ko'ra, algoritmning vaqt va makon murakkabligini kamaytirish uchun Mini-Batch K-Means deb nomlangan yondashuv taklif qilindi.
Mini-Batch K-Means algoritmi ma'lumotlarni asosiy xotiraga shunday joylashtirishga harakat qiladiki, algoritm tasodifiy tanlangan sobit o'lchamdagi ma'lumotlarning kichik partiyalaridan foydalanadi. Mini-Batch K-Means algoritmiga e'tibor berish kerak bo'lgan bir nechta fikrlar:
Klasterlar ma'lumotlar to'plamidan yangi ixtiyoriy namunalarni olish yo'li bilan har bir iteratsiyada yangilanadi (klaster markazlarining oldingi joylashuviga qarab) va bu qadamlar yaqinlashgunga qadar takrorlanadi.
Ba'zi tadqiqotlar shuni ko'rsatadiki, bu usul hisob-kitob vaqtini sezilarli darajada tejaydi, klaster sifatini biroz yo'qotadi. Ammo klaster sifatiga ta'sir ko'rsatadigan klasterlar sonini yoki ularning hajmini aniqlash uchun qizg'in tadqiqotlar o'tkazilmagan.
Klasterlarning joylashuvi har bir partiyadan olingan yangi nuqtalar asosida yangilanadi.
Amalga oshirilgan yangilanish gradient descent yangilanishi bo'lib, u odatdagi K-Means partiyasidan sezilarli darajada tezroq.
|
| |