Klaster tahlili. Klaster tahlil usullari. Takroriy usullar Klasterlash sifatini tekshirish

Klaster tahlili (CLA) - bu ko'p o'lchovli tasniflash usullari to'plami bo'lib, ularning maqsadi o'xshash ob'ektlar guruhlarini (klasterlarini) shakllantirishdir. Statistikaning umumiy nazariyasida ko'rib chiqilgan an'anaviy guruhlardan farqli o'laroq, ClA bir vaqtning o'zida barcha guruhlash xususiyatlarini hisobga olgan holda guruhlarga bo'linishga olib keladi.

KLA usullari quyidagi muammolarni hal qilishga imkon beradi:

— ob'ektlarni ko'p xususiyatlarni hisobga olgan holda tasniflash;

— oʻrganilayotgan obʼyektlar toʻplamida qandaydir strukturaning mavjudligi haqidagi taxminlarni tekshirish, yaʼni. mavjud tuzilmani qidirish;

- populyatsiya ichida aloqalar mavjudligini aniqlash va unga strukturani kiritishga harakat qilish zarur bo'lganda, kam o'rganilgan hodisalar uchun yangi tasniflarni qurish.

Rasmiylashtirilgan KLA algoritmlarini yozish uchun quyidagi konventsiyalardan foydalaniladi:

– kuzatish ob’ektlari majmui;

– m o‘lchamli xususiyat fazosida i-chi kuzatish ();

– -th va -obyektlar orasidagi masofa;

- original o'zgaruvchilarning normallashtirilgan qiymatlari;

– jismlar orasidagi masofalar matritsasi.

Har qanday KLA usulini amalga oshirish uchun "ob'ektning o'xshashligi" tushunchasini kiritish kerak. Bundan tashqari, tasniflash jarayonida har bir klaster kuzatilgan o'zgaruvchilar nuqtai nazaridan bir-biriga eng o'xshash ob'ektlarni o'z ichiga olishi kerak.

O'xshashlikni miqdoriy aniqlash uchun metrikalar tushunchasi kiritiladi. Har bir ob'ekt -xususiyatlar bilan tavsiflanadi va -o'lchovli fazoda nuqta sifatida ifodalanadi. Tasniflangan ob'ektlar orasidagi o'xshashlik yoki farq ular orasidagi metrik masofaga qarab belgilanadi. Odatda ob'ektlar orasidagi masofaning quyidagi o'lchovlari qo'llaniladi:

- Evklid masofasi ;

- og'irlikdagi Evklid masofasi ;

— shahar va blok masofasi ;

- Mahalanobis masofasi,

th va th ob'ektlar orasidagi masofa qayerda;

, - o'zgaruvchining va mos ravishda - va -chi ob'ektlarning qiymatlari;

, – -chi va -chi ob'ektlar uchun o'zgaruvchan qiymatlar vektorlari;

– umumiy kovariatsiya matritsasi;

– th o‘zgaruvchiga tayinlangan og‘irlik.

Barcha KLA usullarini ikki guruhga bo'lish mumkin: ierarxik (aglomerativ va bo'linuvchi) va iterativ (o'rtachalar usuli, kondensatsiyalarni qidirish usuli).

Ierarxik klaster tahlili. Klaster tahlilining barcha usullaridan eng keng tarqalgani aglomerativ tasniflash algoritmidir. Agrogritning mohiyati shundaki, birinchi bosqichda har bir namunaviy ob'ekt alohida klaster sifatida ko'rib chiqiladi. Klasterlarni birlashtirish jarayoni ketma-ket sodir bo'ladi: masofa matritsasi yoki o'xshashlik matritsasi asosida eng yaqin ob'ektlar birlashtiriladi. Agar masofa matritsasi dastlab o'lchamga ega bo'lsa () bo'lsa, unda butun birlashtirish jarayoni () bosqichlarda yakunlanadi. Natijada, barcha ob'ektlar bitta klasterga birlashtiriladi.

Assotsiatsiyalar ketma-ketligi 3.1-rasmda ko'rsatilgan dendrogramma sifatida ifodalanishi mumkin. Dendrogramma shuni ko'rsatadiki, birinchi bosqichda ikkinchi va uchinchi ob'ektlar orasidagi masofa 0,15 bo'lgan bitta klasterga birlashtirilgan. Ikkinchi bosqichda birinchi ob'ekt ularga qo'shildi. Birinchi ob'ektdan ikkinchi va uchinchi ob'ektlarni o'z ichiga olgan klastergacha bo'lgan masofa 0,3 va hokazo.

Ierarxik klasterli tahlilning ko'plab usullari o'zlarining kombinatsiyalangan (o'xshashlik) algoritmlari bilan farqlanadi, ulardan eng keng tarqalganlari: yagona bog'lanish usuli, to'liq bog'lanish usuli, o'rtacha bog'lanish usuli va Ward usuli.

To'liq ulanishlar usuli - barcha ob'ektlar orasidagi o'xshashlik ma'lum darajadagi o'xshashlik darajasidan kam bo'lmagan taqdirdagina yangi ob'ekt klasterga kiritiladi (1.3-rasm).

O'rtacha ulanish usuli - mavjud klasterga yangi ob'ekt kiritilganda, o'xshashlik o'lchovining o'rtacha qiymati hisoblab chiqiladi, keyin belgilangan chegara darajasi bilan taqqoslanadi. Agar biz ikkita klasterni birlashtirish haqida gapiradigan bo'lsak, unda ularning markazlari o'rtasidagi o'xshashlik o'lchovi hisoblab chiqiladi va berilgan chegara qiymati bilan taqqoslanadi. Ikkita klasterli geometrik misolni ko'rib chiqamiz (1.4-rasm).

1.4-rasm. O'rtacha ulanish usuli yordamida ikkita klasterni birlashtirish:

Agar klaster markazlari orasidagi o'xshashlik o'lchovi () berilgan darajadan kam bo'lmasa, u holda klasterlar bittaga birlashtiriladi.

Uord usuli - birinchi bosqichda har bir klaster bitta ob'ektdan iborat. Dastlab, ikkita eng yaqin klaster birlashtiriladi. Ular uchun har bir xarakteristikaning o'rtacha qiymatlari aniqlanadi va kvadratik og'ishlar yig'indisi hisoblanadi

, (1.1)

qayerda klaster raqami, ob'ekt raqami, xususiyat raqami; - har bir ob'ektni tavsiflovchi xususiyatlar soni; -mclusterdagi ob'ektlar soni.

Keyinchalik, algoritmning har bir bosqichida qiymatning eng kichik o'sishini beradigan ob'ektlar yoki klasterlar birlashtiriladi.

Uord usuli klaster ichidagi minimal o'zgarishlar bilan taxminan teng o'lchamdagi klasterlarga olib keladi.

Ierarxik klasterni tahlil qilish algoritmi protseduralar ketma-ketligi sifatida ifodalanishi mumkin:

- o'zgaruvchilarning boshlang'ich qiymatlarini normallashtirish;

— masofalar matritsasi yoki oʻxshashlik oʻlchovlari matritsasini hisoblash;

— tanlangan algoritm bo'yicha eng yaqin ob'ektlar (klasterlar) juftligini va ularning kombinatsiyasini aniqlash;

- barcha ob'ektlar bitta klasterga birlashtirilgunga qadar dastlabki uchta protsedurani takrorlash.

Ikki klasterni birlashtirish uchun o'xshashlik o'lchovi quyidagi usullar bilan aniqlanadi:

— “yaqin qoʻshni” usuli – klasterlar orasidagi oʻxshashlik darajasi ushbu klasterlarning eng oʻxshash (yaqin) obʼyektlari oʻrtasidagi oʻxshashlik darajasi bilan baholanadi;

— “uzoq qoʻshni” usuli – oʻxshashlik darajasi klasterlarning eng uzoqdagi (oʻxshash boʻlmagan) obʼyektlari orasidagi oʻxshashlik darajasi bilan baholanadi;

- o'rtacha ulanish usuli - o'xshashlik darajasi klasterlar ob'ektlari orasidagi o'xshashlik darajalarining o'rtacha qiymati sifatida baholanadi;

- median ulanish usuli - har qanday S klaster va p va q klasterlarini birlashtirish natijasida olingan yangi klaster o'rtasidagi masofa S klaster markazidan markazlarini bog'laydigan segmentning o'rtasigacha bo'lgan masofa sifatida aniqlanadi. p va q klasterlari.

Kondensatsiyalarni qidirish usuli. Takroriy tasniflash usullaridan biri klasterni qidirish algoritmidir. Ushbu usulning iterativ algoritmining mohiyati ob'ektlarning mahalliy kontsentratsiyasini izlash uchun tasniflash belgilari fazosida harakatlanadigan berilgan radiusli gipersferadan foydalanishdan iborat.

Kondensatsiyalarni qidirish usuli, birinchi navbatda, ob'ektlar orasidagi masofalar matritsasi (yoki o'xshashlik o'lchovlari matritsasi) ni hisoblash va sferaning boshlang'ich markazini tanlashni talab qiladi. Odatda, birinchi bosqichda sferaning markazi eng ko'p qo'shnilar yaqinida joylashgan ob'ekt (nuqta) hisoblanadi. Sferaning berilgan radiusi (R) asosida shu sfera ichiga tushadigan nuqtalar to'plami aniqlanadi va ular uchun markazning koordinatalari (o'rtacha xususiyat qiymatlari vektori) hisoblanadi.

Sfera markazining koordinatalarini keyingi qayta hisoblash oldingi bosqichdagi kabi natijaga olib kelganda, sharning harakati to'xtaydi va uning ichiga kiradigan nuqtalar klaster hosil qiladi va keyingi klasterlash jarayonidan chiqariladi. Yuqoridagi protseduralar qolgan barcha nuqtalar uchun takrorlanadi. Algoritm cheklangan miqdordagi bosqichlarda yakunlanadi va barcha nuqtalar klasterlar o'rtasida taqsimlanadi. Tuzilgan klasterlar soni oldindan noma'lum va sfera radiusiga kuchli bog'liq.

Olingan bo'limning barqarorligini baholash uchun har safar radiusni oz miqdorda o'zgartirib, sfera radiusining turli qiymatlari uchun klasterlash jarayonini bir necha marta takrorlash tavsiya etiladi.

Sfera radiusini tanlashning bir necha yo'li mavjud. Agar th va th ob'ektlar orasidagi masofa bo'lsa, u holda radiusning pastki chegarasi () ni tanlang va radiusning yuqori chegarasi sifatida aniqlanishi mumkin.

Agar siz algoritmni qiymat bilan boshlasangiz va har safar takrorlanganda uni kichik qiymatga o'zgartirsangiz, u holda bir xil miqdordagi klasterlarning shakllanishiga olib keladigan radiuslarning qiymatlarini aniqlashingiz mumkin, ya'ni. barqaror bo'limga.

Misol 1. 1.1-jadvaldagi ma'lumotlarga asoslanib, ierarxik aglomerativ klaster tahlilidan foydalangan holda beshta korxonani tasniflash kerak.

1.1-jadval

Bu erda: – asosiy ishlab chiqarish fondlarining o'rtacha yillik qiymati, milliard rubl; – ishlab chiqarilgan mahsulotning bir rubli uchun moddiy xarajatlar, tiyinlar; - ishlab chiqarilgan mahsulot hajmi, milliard rubl.

Yechim. Masofa matritsasini hisoblashdan oldin formuladan foydalanib, dastlabki ma'lumotlarni normallashtiramiz

Normallashtirilgan o'zgaruvchilar qiymatlari matritsasi shunday ko'rinadi

Biz tasnifni ierarxik aglomerativ usul yordamida amalga oshiramiz. Masofa matritsasini qurish uchun biz Evklid masofasidan foydalanamiz. Keyin, masalan, birinchi va ikkinchi ob'ektlar orasidagi masofa bo'ladi

Masofa matritsasi ob'ektlar orasidagi masofalarni tavsiflaydi, ularning har biri birinchi bosqichda alohida klasterni ifodalaydi.

Matritsadan ko'rinib turibdiki, eng yaqin ob'ektlar va. Keling, ularni bitta klasterga birlashtiramiz va unga raqam beramiz. Keling, qolgan barcha ob'ektlarning (klasterlarning) klastergacha bo'lgan masofalarini qayta hisoblab chiqamiz va yangi masofa matritsasini olamiz.

Matritsada klasterlar orasidagi masofalar "uzoq qo'shni" algoritmi yordamida aniqlanadi. Keyin ob'ekt va klaster orasidagi masofa

Matritsada biz yana eng yaqin klasterlarni topamiz. Bular va , bo'ladi. Shuning uchun, bu bosqichda biz klasterlarni ham birlashtiramiz; ob'ektlarni o'z ichiga olgan yangi klasterni olamiz. Keling, unga raqam beraylik. Endi bizda uchta klaster mavjud (1,3), (2,5), (4).

Matritsaga ko'ra, keyingi bosqichda biz klasterlarni va bitta klasterga birlashtiramiz va unga raqam beramiz. Endi bizda faqat ikkita klaster mavjud:

Va nihoyat, oxirgi bosqichda biz klasterlarni 3.861 masofada birlashtiramiz.

Tasniflash natijalarini dendrogramma shaklida keltiramiz (1.5-rasm). Dendrogramma klasterning kiruvchi ob'ektlar tarkibida bir hil ekanligini ko'rsatadi, chunki unda birlashma klasterga qaraganda qisqaroq masofalarda sodir bo'lgan.

3.5-rasm, beshta ob'ektni klasterlash

2-misol. Quyida keltirilgan ma'lumotlarga asoslanib, do'konlarni uchta mezon bo'yicha tasniflang: – savdo maydoni, m2, – sotuvchiga to'g'ri keladigan aylanma, uy. birlik, – rentabellik darajasi, %.

Do'kon raqami				Do'kon raqami

Do'konlarni tasniflash uchun klasterni qidirish usulidan foydalaning (birinchi klasterni tanlashingiz kerak).

Yechim. 1. Evklid metrikasi yordamida jismlar orasidagi masofalarni hisoblang

bu yerda , mos ravishda th va th ob'ektlar uchun boshlang'ich o'zgaruvchilarning standartlashtirilgan qiymatlari; t - xususiyatlar soni.

2. Z matritsasi asosida ob'ektlar orasidagi masofalarning kvadrat simmetrik matritsasini hisoblaymiz ().

Masofa matritsasini tahlil qilish sferaning boshlang'ich markazining o'rnini aniqlashga va sfera radiusini tanlashga yordam beradi.

Ushbu misolda "kichik" masofalarning aksariyati birinchi qatorda, ya'ni. birinchi ob'ektning juda ko'p "yaqin" qo'shnilari bor. Shuning uchun birinchi ob'ektni sharning markazi sifatida olish mumkin.

3. Sfera radiusini o'rnating. Bunda birinchi ob'ektgacha bo'lgan masofa 2 dan kichik bo'lgan jismlar sharga tushadi.

Klaster tahlili(CLA) ko'p o'lchovli tasniflash usullari to'plami bo'lib, ularning maqsadi o'xshash ob'ektlar guruhlarini (klasterlarini) shakllantirishdir. Statistikaning umumiy nazariyasida ko'rib chiqilgan an'anaviy guruhlardan farqli o'laroq, ClA bir vaqtning o'zida barcha guruhlash xususiyatlarini hisobga olgan holda guruhlarga bo'linishga olib keladi.

KLA usullari quyidagi muammolarni hal qilishga imkon beradi:

Ko'pgina xususiyatlarni hisobga olgan holda ob'ektlarni tasniflashni amalga oshirish;

O'rganilayotgan ob'ektlar to'plamida qandaydir strukturaning mavjudligi haqida qilingan taxminlarni tekshirish, ya'ni. mavjud tuzilmani qidirish;

Kam o'rganilgan hodisalar uchun yangi tasniflarni qurish, agar populyatsiya ichida aloqalar mavjudligini aniqlash va unga tuzilmani kiritishga harakat qilish kerak.

Rasmiylashtirilgan KLA algoritmlarini yozish uchun quyidagi konventsiyalardan foydalaniladi:

– kuzatish ob’ektlari majmui;

– m o‘lchamli xususiyat fazosida i-chi kuzatish ();

– -th va -obyektlar orasidagi masofa;

- original o'zgaruvchilarning normallashtirilgan qiymatlari;

– jismlar orasidagi masofalar matritsasi.

Evklid masofasi ;

Og'irlangan Evklid masofasi ;

Masofa shahar-blok ;

Mahalanobis masofasi,

th va th ob'ektlar orasidagi masofa qayerda;

, - o'zgaruvchining va mos ravishda - va -chi ob'ektlarning qiymatlari;

, – -chi va -chi ob'ektlar uchun o'zgaruvchan qiymatlar vektorlari;

– umumiy kovariatsiya matritsasi;

– th o‘zgaruvchiga tayinlangan og‘irlik.

Barcha KLA usullarini ikki guruhga bo'lish mumkin: ierarxik (aglomerativ va bo'linuvchi) va iterativ (o'rtachalar usuli, kondensatsiyalarni qidirish usuli).

To'liq havola usuli- klasterga yangi ob'ektni kiritish faqat barcha ob'ektlar o'rtasidagi o'xshashlik ma'lum bir belgilangan o'xshashlik darajasidan kam bo'lmasa sodir bo'ladi (1.3-rasm).

O'rtacha ulanish usuli- mavjud klasterga yangi ob'ekt kiritilganda, o'xshashlik o'lchovining o'rtacha qiymati hisoblab chiqiladi, so'ngra belgilangan chegara darajasi bilan taqqoslanadi. Agar biz ikkita klasterni birlashtirish haqida gapiradigan bo'lsak, unda ularning markazlari o'rtasidagi o'xshashlik o'lchovi hisoblab chiqiladi va berilgan chegara qiymati bilan taqqoslanadi. Ikkita klasterli geometrik misolni ko'rib chiqamiz (1.4-rasm).

1.4-rasm. O'rtacha ulanish usuli yordamida ikkita klasterni birlashtirish:

Agar klaster markazlari orasidagi o'xshashlik o'lchovi () berilgan darajadan kam bo'lmasa, u holda klasterlar bittaga birlashtiriladi.

Uord usuli- birinchi bosqichda har bir klaster bitta ob'ektdan iborat. Dastlab, ikkita eng yaqin klaster birlashtiriladi. Ular uchun har bir xarakteristikaning o'rtacha qiymatlari aniqlanadi va kvadratik og'ishlar yig'indisi hisoblanadi

, (1.1)

qayerda klaster raqami, ob'ekt raqami, xususiyat raqami; - har bir ob'ektni tavsiflovchi xususiyatlar soni; – ob'ektlar soni - mklaster.

Keyinchalik, algoritmning har bir bosqichida qiymatning eng kichik o'sishini beradigan ob'ektlar yoki klasterlar birlashtiriladi.

Uord usuli klaster ichidagi minimal o'zgarishlar bilan taxminan teng o'lchamdagi klasterlarga olib keladi.

Ierarxik klasterni tahlil qilish algoritmi protseduralar ketma-ketligi sifatida ifodalanishi mumkin:

O'zgaruvchilarning boshlang'ich qiymatlarini normallashtirish;

Masofalar matritsasi yoki o'xshashlik o'lchovlari matritsasini hisoblash;

Eng yaqin ob'ektlar (klasterlar) juftligini aniqlash va ularni tanlangan algoritm bo'yicha birlashtirish;

Barcha ob'ektlar bitta klasterga birlashtirilgunga qadar dastlabki uchta protsedurani takrorlang.

Ikki klasterni birlashtirish uchun o'xshashlik o'lchovi quyidagi usullar bilan aniqlanadi:

“Eng yaqin qo‘shni” usuli – klasterlar o‘rtasidagi o‘xshashlik darajasi ushbu klasterlarning eng o‘xshash (yaqin) ob’ektlari o‘rtasidagi o‘xshashlik darajasi bilan baholanadi;

"Uzoq qo'shni" usuli - o'xshashlik darajasi klasterlarning eng uzoqdagi (o'xshash bo'lmagan) ob'ektlari o'rtasidagi o'xshashlik darajasi bilan baholanadi;

O'rtacha ulanish usuli - o'xshashlik darajasi klasterlardagi ob'ektlar orasidagi o'xshashlik darajalarining o'rtacha qiymati sifatida baholanadi;

Median ulanish usuli - har qanday klaster orasidagi masofa S va klasterlarning birlashishi natijasida paydo bo'lgan yangi klaster R Va q, klaster markazidan masofa sifatida aniqlanadi S klaster markazlarini bog'laydigan segmentning o'rtasiga R Va q.

Kondensatsiyani qidirish usuli. Takroriy tasniflash usullaridan biri klasterni qidirish algoritmidir. Ushbu usulning iterativ algoritmining mohiyati ob'ektlarning mahalliy kontsentratsiyasini izlash uchun tasniflash belgilari fazosida harakatlanadigan berilgan radiusli gipersferadan foydalanishdan iborat.

Kondensatsiyalarni qidirish usuli, birinchi navbatda, ob'ektlar orasidagi masofalar matritsasi (yoki o'xshashlik o'lchovlari matritsasi) ni hisoblash va sferaning boshlang'ich markazini tanlashni talab qiladi. Odatda, birinchi bosqichda sferaning markazi eng ko'p qo'shnilar yaqinida joylashgan ob'ekt (nuqta) hisoblanadi. Berilgan shar radiusi asosida (R) bu sfera ichiga tushadigan nuqtalar to'plami aniqlanadi va ular uchun markazning koordinatalari (o'rtacha xususiyat qiymatlari vektori) hisoblanadi.

Sfera radiusini tanlashning bir necha yo'li mavjud. Agar th va th ob'ektlar orasidagi masofa bo'lsa, unda tanlang , va radiusning yuqori chegarasi sifatida belgilash mumkin .

1-misol. 1.1-jadvaldagi ma'lumotlarga asoslanib, ierarxik aglomerativ klaster tahlilidan foydalangan holda beshta korxonani tasniflash kerak.

1.1-jadval

Yechim. Masofa matritsasini hisoblashdan oldin formuladan foydalanib, dastlabki ma'lumotlarni normallashtiramiz

Normallashtirilgan o'zgaruvchilar qiymatlari matritsasi shunday ko'rinadi

Masofa matritsasi ob'ektlar orasidagi masofalarni tavsiflaydi, ularning har biri birinchi bosqichda alohida klasterni ifodalaydi.

Matritsadan ko'rinib turibdiki, eng yaqin ob'ektlar va. Keling, ularni bitta klasterga birlashtiramiz va unga raqam beramiz . Keling, qolgan barcha ob'ektlarning (klasterlarning) klastergacha bo'lgan masofalarini qayta hisoblab chiqamiz va yangi masofa matritsasini olamiz.

Matritsada klasterlar orasidagi masofalar "uzoq qo'shni" algoritmi yordamida aniqlanadi. Keyin ob'ekt va klaster orasidagi masofa

Matritsada biz yana eng yaqin klasterlarni topamiz. Bular va , bo'ladi. Shuning uchun, bu bosqichda biz klasterlarni ham birlashtiramiz; ob'ektlarni o'z ichiga olgan yangi klasterni olamiz. Keling, unga raqam beraylik . Endi bizda uchta klaster mavjud (1,3), (2,5), (4).

Matritsaga ko'ra, keyingi bosqichda biz klasterlarni va bitta klasterga birlashtiramiz va unga raqam beramiz. Endi bizda faqat ikkita klaster mavjud:

Va nihoyat, oxirgi bosqichda biz klasterlarni 3.861 masofada birlashtiramiz.

3.5-rasm, beshta ob'ektni klasterlash

2-misol. Quyida keltirilgan ma'lumotlarga asoslanib, do'konlarni uchta mezon bo'yicha tasniflang: - savdo maydoni, m2, - sotuvchiga to'g'ri keladigan aylanma, uy. birlik, – rentabellik darajasi, %.

Do'kon raqami				Do'kon raqami

Do'konlarni tasniflash uchun klasterni qidirish usulidan foydalaning (birinchi klasterni tanlashingiz kerak).

Yechim. 1. Evklid metrikasi yordamida jismlar orasidagi masofalarni hisoblang

bu yerda , mos ravishda th va th ob'ektlar uchun boshlang'ich o'zgaruvchilarning standartlashtirilgan qiymatlari; T- belgilar soni.

2. Z matritsasi asosida ob'ektlar orasidagi masofalarning kvadrat simmetrik matritsasini hisoblaymiz () .

Masofa matritsasini tahlil qilish sferaning boshlang'ich markazining o'rnini aniqlashga va sfera radiusini tanlashga yordam beradi.

Ushbu misolda "kichik" masofalarning aksariyati birinchi qatorda, ya'ni. birinchi ob'ektning juda ko'p "yaqin" qo'shnilari bor. Shuning uchun birinchi ob'ektni sharning markazi sifatida olish mumkin.

3. Sfera radiusini o'rnating. Bunda birinchi ob'ektgacha bo'lgan masofa 2 dan kichik bo'lgan jismlar sharga tushadi.

Olti nuqta uchun (1, 2, 3, 6, 7, 8-ob'ektlar) og'irlik markazining koordinatalarini aniqlaymiz: .

4. Algoritmning keyingi bosqichida sharning markazini bir nuqtaga joylashtiramiz va har bir ob'ektning yangi markazgacha bo'lgan masofasini aniqlaymiz.

Klasterlar sonini ko'rsatishni talab qilmaydigan iterativ tasniflash usullaridan biri bu klasterlarni qidirish usulidir. Usul masofa matritsasini hisoblashni, so'ngra birinchi klasterning boshlang'ich markazi bo'lgan ob'ektni tanlashni talab qiladi. Bunday ob'ektni tanlash o'zboshimchalik bilan bo'lishi mumkin yoki u nuqtalarni va ularning atrofini oldindan tahlil qilishga asoslangan bo'lishi mumkin.

Tanlangan nuqta ma'lum R radiusli gipersferaning markazi sifatida qabul qilinadi. Ushbu sfera ichiga tushadigan nuqtalar to'plami aniqlanadi va ular uchun markazning koordinatalari (o'rtacha xususiyat qiymatlari vektori) hisoblanadi. Keyinchalik, bir xil radiusli, ammo yangi markazga ega bo'lgan gipersfera ko'rib chiqiladi va uning ichiga tushadigan nuqtalar to'plami uchun yana o'rtacha qiymatlar vektori hisoblab chiqiladi, bu esa sferaning yangi markazi sifatida qabul qilinadi, va hokazo. Sfera markazining koordinatalarini keyingi qayta hisoblash oldingi bosqichdagi kabi natijaga olib kelganda, sharning harakati to'xtaydi va unga tushadigan nuqtalar klaster hosil qiladi va keyingi klasterlash jarayonidan chiqariladi. Qolgan barcha nuqtalar uchun protseduralar takrorlanadi.

Shunday qilib, ko'proq ierarxik bo'lmagan usullar mavjud, garchi ular bir xil printsiplarda ishlaydi. Aslini olganda, ular asl populyatsiyani parchalashning iterativ usullaridir. Bo'linish jarayonida yangi klasterlar hosil bo'ladi va to'xtash qoidasi bajarilgunga qadar davom etadi. Usullar bir-biridan boshlang'ich nuqtani tanlashda, yangi klasterlarni shakllantirish qoidasida va to'xtatish qoidasida farqlanadi. Eng ko'p ishlatiladigan algoritm K- degani.

Xulosa

Klaster tahlili - bu ob'ektlarning xossalari haqidagi eksperimental ma'lumotlarga asoslanib, ob'ektlarni sinflarga guruhlash usuli.

Bunday holda, ob'ektlarni ifodalash uchun klaster modeli qo'llaniladi - o'xshash xususiyatlarga ega ob'ektlar bir xil sinfga tegishli.

Klaster tahlili turli tasniflash algoritmlari to‘plamini o‘z ichiga oladi (klasterli tahlil usuliga misol sifatida dendrogramma usulini keltirish mumkin).

Bunda, qoida tariqasida, ob'ektlar to'plami va klaster tahlilining maqsadlari haqidagi umumiy ma'lumotlarga asoslanib, sinflar soni va sinflarga bo'linish tamoyillari oldindan belgilanadi.

Klasterlarni tahlil qilish usullari diskriminant tahlil usullari bilan to'ldiriladi, bu klasterlar orasidagi chegaralarni aniqlash va ulardan ma'lumotlarni tahlil qilish va tasniflash muammolarini hal qilishda foydalanish imkonini beradi.

Klaster tahlilining natijalari ko'pincha ob'ektlarni klasterlarga birlashtirish tartibini ko'rsatadigan dendrogram ("daraxt") ko'rinishida grafik tarzda taqdim etiladi. Ko'p hollarda klasterlar sonini aniqlashdan boshlanadigan klaster tuzilishini talqin qilish ijodiy vazifadir. Uni samarali hal etish uchun tadqiqotchi klasterlangan ob'ektlar haqida yetarli ma'lumotga ega bo'lishi kerak. Nazorat ostidagi klasterlash yordamida natijalar har bir sinfga tayinlangan ob'ektlar ro'yxati ko'rinishida taqdim etilishi mumkin.

Klaster tahlilining asosiy afzalliklari tahlilda qo'llaniladigan o'zgaruvchilarni taqsimlashda cheklovlarning yo'qligi; sinflar soni va tabiati to'g'risida apriori ma'lumotlar mavjud bo'lmagan hollarda ham tasniflash (klasterlash) imkoniyati; universallik (klaster tahlili nafaqat ob'ektlar to'plamiga, balki o'zgaruvchilar to'plamiga yoki boshqa tahlil birliklariga ham qo'llanilishi mumkin).

Keling, klaster tahlilining kamchiliklarini sanab o'tamiz:

Faktor tahlili singari, u beqaror klasterlarni keltirib chiqarishi mumkin. Tadqiqotni boshqa odamlarda takrorlang va tasniflash natijalarini solishtiring. Katta ehtimol bilan ular boshqacha bo'ladi. Tadqiqotning o'zi qanchalik sifatli ekanligi masalasi.

U xususiydan umumiygacha bo'lgan induktiv tadqiqot usulini amalga oshiradi, bu esa ilmga zid xulosalar bilan to'la. Ideal holda, tasniflash uchun namuna juda katta, heterojen bo'lishi kerak, tercihen tabaqalanish yoki randomizatsiya yo'li bilan tanlangan bo'lishi kerak. Fan gipotezalarni sinab ko'rish yo'lida harakat qilmoqda, shuning uchun klaster tahlilini ortiqcha ishlatishning hojati yo'q. Noldan tasnif yaratishdan ko'ra, har qanday turlarning mavjudligi haqidagi gipotezani sinab ko'rish uchun undan foydalanish yaxshidir.

Har qanday ko'p o'lchovli masshtablash usuli singari, klaster tahlili ichki usullar bilan bog'liq ko'plab xususiyatlarga ega. Odamlarni klasterlarga birlashtirish mezoni nima, farqlarni topish usuli, k-o'rtacha usulida algoritm tugaguniga qadar bo'lgan qadamlar soni va boshqalar. shuning uchun natijalar, protseduraning "sozlamalari" ga qarab, ahamiyatsiz bo'lsa-da, farq qilishi mumkin.

Usullarning ikki guruhi mavjud klaster tahlili: ierarxik va ierarxik bo'lmagan.

Ierarxik klaster tahlilining asosiy usullari eng yaqin qo'shni usuli, to'liq bog'lanish usuli, o'rtacha bog'lanish usuli va Vard usulidir. Oxirgisi eng universal hisoblanadi.

Ko'proq ierarxik bo'lmagan usullar mavjud, garchi ular bir xil printsiplarda ishlaydi. Aslini olganda, ular asl populyatsiyani parchalashning iterativ usullaridir. Bo'linish jarayonida yangi klasterlar hosil bo'ladi va to'xtash qoidasi bajarilgunga qadar davom etadi. Usullar bir-biridan boshlang'ich nuqtani tanlashda, yangi klasterlarni shakllantirish qoidasida va to'xtatish qoidasida farqlanadi. Eng ko'p ishlatiladigan algoritm K- degani. Bu shuni anglatadiki, tahlilchi olingan bo'limdagi klasterlar sonini oldindan aniqlaydi.

Muayyan klasterlash usulini tanlash haqida gapirganda, biz yana bir bor ta'kidlaymizki, bu jarayon tahlilchidan usullarning tabiati va shartlarini yaxshi bilishini talab qiladi, aks holda olingan natijalar "kasalxonadagi o'rtacha harorat" ga o'xshash bo'ladi. Tanlangan usul ma'lum bir sohada haqiqatan ham samarali bo'lishini ta'minlash uchun, qoida tariqasida, quyidagi tartib qo'llaniladi:

Bir nechta apriori turli guruhlar ko'rib chiqiladi va ularning vakillari tasodifiy aralashtiriladi. Keyin guruhlarga dastlabki bo'linishni tiklash uchun klasterlash jarayoni amalga oshiriladi. Usul samaradorligining ko'rsatkichi aniqlangan va asl guruhlardagi ob'ektlar o'rtasidagi moslik nisbati bo'ladi.

Ierarxik va ierarxik bo'lmagan usullarni tanlashda siz quyidagi fikrlarga e'tibor berishingiz kerak:

Ierarxik bo'lmagan usullar, o'lchovlarni noto'g'ri tanlash, klasterlash asosiga ahamiyatsiz o'zgaruvchilarni kiritish va hokazolarga nisbatan yuqori qarshilikni ko'rsatadi. Lekin buning narxi "apriori" so'zidir. Tadqiqotchi klasterlarning natijaviy sonini, to'xtatish qoidasini va agar kerak bo'lsa, dastlabki klaster markazini oldindan yozib qo'yishi kerak. Oxirgi nuqta algoritmning samaradorligiga sezilarli ta'sir qiladi. Agar ushbu shartni sun'iy ravishda o'rnatish uchun hech qanday sabab bo'lmasa, umuman olganda, ierarxik usullardan foydalanish tavsiya etiladi. Algoritmlarning ikkala guruhi uchun ham muhim bo'lgan yana bir narsani ta'kidlab o'tamiz: barcha kuzatuvlarni klasterlash har doim ham to'g'ri echim emas. Avvalo namunani chetlab o'tish va keyin tahlilni davom ettirish ehtiyotkor bo'lishi mumkin. To'xtash mezonini juda yuqori belgilamaslik ham mumkin.

Ko'p sonli kuzatishlar bilan klaster tahlilining ierarxik usullari mos kelmaydi. Bunday hollarda bo'linishga asoslangan ierarxik bo'lmagan usullar qo'llaniladi, bular iterativ usullar asl aholining parchalanishi. Bo'linish jarayonida yangi klasterlar hosil bo'ladi to'xtatish qoidasi.

Bunday ierarxik bo'lmagan klasterlash ma'lumotlar to'plamini ma'lum miqdordagi individual klasterlarga bo'lishdan iborat. Ikkita yondashuv mavjud. Birinchisi, manba ma'lumotlarining ko'p o'lchovli maydonida eng zich joylar sifatida klasterlarning chegaralarini aniqlash, ya'ni. katta "nuqtalarning kondensatsiyasi" mavjud bo'lgan klasterni belgilash. Ikkinchi yondashuv ob'ektlar orasidagi farqni minimallashtirishdir

k - algoritmni anglatadi

Ierarxik bo'lmagan usullar orasida eng keng tarqalgan k - algoritmni anglatadi, deb ham ataladi tezkor klaster tahlili. Algoritmning to'liq tavsifini Hartigan va Vong (1978) da topish mumkin. Klasterlar soni bo'yicha dastlabki taxminlarni talab qilmaydigan ierarxik usullardan farqli o'laroq, ushbu usuldan foydalanish uchun klasterlarning eng ko'p soni haqida gipotezaga ega bo'lish kerak.

k - algoritmni anglatadi bir-biridan mumkin bo'lgan eng katta masofada joylashgan k klasterlarni quradi. U hal qiladigan muammolarning asosiy turi k - algoritmni anglatadi, - klasterlar soni bo'yicha taxminlar (gipotezalar) mavjudligi va ular iloji boricha farq qilishi kerak. k ni tanlash oldingi tadqiqotlarga, nazariy mulohazalar yoki sezgilarga asoslangan bo'lishi mumkin.

Algoritmning umumiy g'oyasi: klasterdagi o'rtacha ko'rsatkichlar (barcha o'zgaruvchilar uchun) iloji boricha bir-biridan farq qilishi uchun kuzatuv klasterlarining ma'lum qat'iy soni k klasterlar bilan taqqoslanadi.

Algoritmning tavsifi

Ob'ektlarni klasterlarga dastlabki taqsimlash.
K raqami tanlanadi va birinchi bosqichda bu nuqtalar klasterlarning "markazlari" hisoblanadi. Har bir klaster bitta markazga to'g'ri keladi.

Boshlang'ich markazlarni tanlash quyidagicha amalga oshirilishi mumkin:
- boshlang'ich masofani maksimallashtirish uchun k-kuzatishlarni tanlash;
- k-kuzatishlarni tasodifiy tanlash;
- birinchi k-kuzatishlarni tanlash.
Natijada, har bir ob'ekt ma'lum bir klasterga biriktiriladi.
Iterativ jarayon.
Hisoblangan klaster markazlari, ular keyinchalik va keyinchalik klasterlarning koordinatali o'rtacha ko'rsatkichlari hisoblanadi. Ob'ektlar yana qayta taqsimlanadi.

Markazlarni hisoblash va ob'ektlarni qayta taqsimlash jarayoni shartlardan biri bajarilmaguncha davom etadi:
- klaster markazlari barqarorlashdi, ya'ni. barcha kuzatishlar joriy iteratsiyadan oldin tegishli bo'lgan klasterga tegishli;
- takrorlash soni maksimal takrorlash soniga teng.
Shaklda. 14.1 operatsiya misolini ko'rsatadi k - algoritmni anglatadi k uchun ikkiga teng.

Guruch. 14.1.

Klasterlar sonini tanlash murakkab masala. Agar bu raqam bo'yicha hech qanday taxminlar bo'lmasa, olingan natijalarni taqqoslab, 2 ta klasterni, keyin 3, 4, 5 va hokazolarni yaratish tavsiya etiladi.

algoritm katta ma'lumotlar bazalarida sekin bo'lishi mumkin. Ushbu muammoning mumkin bo'lgan yechimi ma'lumotlar namunalaridan foydalanishdir.

Klaster tahlili - bu katta hajmdagi ma'lumotlarni sinflarga yoki guruhlarga bo'lish imkonini beruvchi statistik tahlil (ingliz tilidan, klaster- sinf) ba'zi bir mezon yoki ularning kombinatsiyasiga ko'ra.

Ma'lumotlarni tasniflashni amalga oshirish uchun X x,...,X p metrik yoki masofa tushunchasidan foydalaning.

Metrika maʼlum bir metrik fazoni haqiqiy sonlar fazosiga joylashtiradigan p funksiya boʻlib, quyidagi xossalarga ega (metrik aksiomalar):

1) p(ZD>0,
2) p(X,Y)=p(Y,X),
3) p(X, Y) = 0 X = Y,
4) P(X,Y) P(Z,Y).

Klaster tahlili nazariyasi alohida nuqtalar (vektorlar) orasidagi masofani o'lchash uchun quyidagi ko'rsatkichlardan foydalanadi:

1) Evklid masofasi

2) vaznli Evklid masofasi

Qayerda w k - tasniflash muammosidagi xususiyatning ahamiyatiga proportsional vaznlar. Og'irliklar qo'shimcha tadqiqotlardan so'ng o'rnatiladi

va ^w* = 1 deb faraz qilaylik;

3) Hamming masofasi (yoki shahar bloki) - xaritada shahardagi bloklar orasidagi masofa

4) Mahalanobis masofasi (yoki Mahalanobis burchagi)

bu erda A - tortish koeffitsientlarining simmetrik musbat aniq matritsasi (ko'pincha diagonal tanlangan); A - vektor kovariatsiya matritsasi X 19 ..., X p;

5) Minkovskiy masofasi

Mustaqil tasodifiy miqdorlar normal taqsimlanganda 1), 2), 3) yoki 5) masofalar qo'llaniladi. X l9 ...,X n ~N(M,A) yoki ularning geokimyoviy ma'nosi bo'yicha bir hil bo'lgan taqdirda, har bir vektor tasniflash uchun bir xil ahamiyatga ega bo'lganda. Masofa 4) vektorlar orasidagi kovariatsiya munosabati mavjud bo'lganda qo'llaniladi X x,...,X P.

Ko'rsatkichni tanlash tadqiqotchi tomonidan qanday natija olishni istayotganiga qarab amalga oshiriladi. Ushbu tanlov rasmiylashtirilmaydi, chunki u ko'plab omillarga, xususan kutilgan natijaga, tadqiqotchining tajribasiga, uning matematik tayyorgarlik darajasiga va boshqalarga bog'liq.

Bir qator algoritmlarda vektorlar orasidagi masofalar bilan bir qatorda klasterlar va klaster birlashmalari orasidagi masofalar qo'llaniladi.

Mayli S (- dan iborat /-chi klaster n t vektorlar yoki nuqtalar. Mayli

X (l) - klasterga tushadigan nuqtalarning o'rtacha namunasi S f, yoki klasterning og'irlik markazi 5.. Keyin ichida boshqa klasterlar bo'lmagan klasterlar orasida quyidagi masofalar ajratiladi:

1) "yaqin qo'shni" tamoyiliga asoslangan klasterlar orasidagi masofa

2) "uzoq qo'shni" tamoyili bo'yicha klasterlar orasidagi masofa

3) guruhlarning og'irlik markazlari orasidagi masofa

4) "o'rtacha ulanish" tamoyili bo'yicha klasterlar orasidagi masofa

5) umumlashtirilgan Kolmogorov masofasi

Boshqa sinflarning birlashmalari bo'lgan klasterlar orasidagi masofani umumiy formuladan foydalanib hisoblash mumkin:

Qayerda S^k^- sinflarni birlashtirish orqali olingan klaster S k Va S t.

Masofalarning barcha maxsus holatlari ushbu umumlashtirilgan formuladan olinadi. a = p = 1/2, 8 = -1/2, y = 0 uchun biz "yaqin qo'shni" tamoyiliga ko'ra masofaga egamiz, a = p = 5 = 1/2, y = O - "uzoq qo'shni" uchun ”,

a =---, p =---,5 = 0, y = 0 bo'lganda - tortishish markazlari bo'ylab masofa

p k + n i p k + n i

sti guruhlari.

Klaster tahlil usullari I) aglomerativ (birlashtiruvchi), II) bo‘linuvchi (bo‘linuvchi) va III) iterativlarga bo‘linadi.

Birinchisi alohida ob'ektlarni ketma-ket klasterlarga birlashtiradi, ikkinchisi, aksincha, klasterlarni ob'ektlarga ajratadi. Uchinchisi birinchi ikkitasini birlashtiradi. Ularning xususiyati bo'lim sifatini yaxshilash uchun algoritmning ishlashi davomida o'zgartirilishi mumkin bo'lgan bo'linish shartlariga (parametrlar deb ataladigan) asoslangan klasterlarni shakllantirishdir. Katta hajmdagi ma'lumotlarni tasniflash uchun iterativ usullar odatda qo'llaniladi.

Keling, aglomerativ usullarni batafsil ko'rib chiqaylik. Aglomerativ usullar klasterli tahlil algoritmlari orasida eng sodda va keng tarqalgani hisoblanadi. Birinchi bosqichda har bir vektor yoki ob'ekt X 19..., X p manba ma'lumotlari alohida klaster yoki sinf sifatida ko'rib chiqiladi. Hisoblangan masofa matritsasi asosida bir-biriga eng yaqin bo'lganlar tanlanadi va birlashtiriladi. Shubhasiz, jarayon shu bilan tugaydi (P - 1) natijada barcha ob'ektlar bitta klasterga birlashtirilgan bosqich.

Assotsiatsiyalar ketma-ketligi dendrogram yoki daraxt sifatida ifodalanishi mumkin. Shaklda. 1.18-rasm birinchi bosqichda vektorlar birlashtirilganligini ko'rsatadi X t , X 2 , chunki ular orasidagi masofa 0,3 ga teng.

Ikkinchi bosqichda vektor ularga biriktirilgan X 3, klasterdan uzoqda (X 1, X 2) 0,5 masofada va hokazo. Oxirgi bosqichda barcha vektorlar bir klasterga birlashtiriladi.

Guruch. 1.18.

Aglomerativ usullarga bitta, o'rta, to'liq ulanish va Uord usuli kiradi.

1.Yagona ulanish usuli. Mayli Xv...,Xn - vektor ma'lumotlari, har bir vektor bitta klasterni tashkil qiladi. Birinchidan, metrik sifatida eng yaqin qo'shni masofadan foydalanib, ushbu klasterlar orasidagi masofalar matritsasi hisoblanadi. Ushbu matritsadan foydalanib, ikkita eng yaqin vektor tanlanadi, ular birinchi klaster 5, ni tashkil qiladi. O'rtasidagi keyingi qadam S ] va qolgan vektorlar (biz klasterlar deb hisoblaymiz), yangi masofa matritsasi hisoblab chiqiladi va sinflarga birlashtirilgan klasterlar orasidagi masofa metrik sifatida ishlatiladi (a = p = 1/2, 5 = -1/2, y = 0). Oldindan olingan sinfga eng yaqin S ( klaster u bilan birlashadi, hosil qiladi S 2. Va boshqalar orqali P- 1 qadamda biz barcha vektorlar bitta klasterga birlashtirilganligini olamiz.

Afzalliklar: 1) algoritmning har bir bosqichida faqat bitta element qo'shiladi, 2) usul juda oddiy, 3) algoritm manba ma'lumotlarini o'zgartirishga (aylantirish, siljish, tarjima, cho'zish) sezgir emas.

Kamchiliklar: 1) masofa matritsasini doimiy ravishda qayta hisoblash kerak, 2) klasterlar soni oldindan ma'lum va uni qisqartirib bo'lmaydi.

2. To'liq ulanish usuli. Usul amalda yagona bog'lanish usulini takrorlaydi, bundan tashqari yangi ob'ektni klasterga kiritish, agar ob'ektlar (vektorlar yoki klasterlar) orasidagi masofa ma'lum bir oldindan belgilangan raqamdan kam bo'lsa, sodir bo'ladi. Raqam foydalanuvchi tomonidan belgilanadi. Masofa faqat "uzoq qo'shni" printsipi bo'yicha hisoblanadi (sinflarga birlashtirilgan sinflar orasidagi masofa haqida ham aytish mumkin - faqat oc = p = 8 = 1/2, y = 0 bilan uzoq qo'shni printsipi).
3.O'rtacha ulanish usuli. Klasterni shakllantirish algoritmi yagona ulanish algoritmiga to'g'ri keladi, ammo klasterga yangi ob'ektni kiritish to'g'risida qaror qabul qilishda hisob-kitoblar o'rtacha ulanish printsipi bo'yicha amalga oshiriladi. To'liq ulanish usulida bo'lgani kabi, klasterlar o'rtasida hisoblangan barcha masofalar foydalanuvchi tomonidan belgilangan raqam bilan taqqoslanadi. Va agar u (masofa) berilgan raqamdan kam bo'lsa, yangi ob'ekt eski sinfga kiritilgan. Shunday qilib, o'rtacha bog'lanish usuli to'liq bog'lanish usulidan faqat klasterlar orasidagi masofani hisoblash usuli bilan farq qiladi.
4. WARD usuli. Mayli X 19..., X p- ma'lumotlar, har bir vektor bitta klasterni tashkil qiladi. Biz ba'zi bir metrik (masalan, Mahalanobis masofasi) yordamida masofa matritsasini topamiz va undan bir-biriga eng yaqin bo'lgan klasterlarni aniqlash uchun foydalanamiz. Biz klaster ichidagi vektorlarning kvadratik og'ishlari yig'indisini hisoblaymiz S k formula bo'yicha:

Qayerda Kimga - klaster raqami, men- klasterdagi vektor raqami, j- koordinata raqami Xt e U1 R, p to- klasterdagi vektorlar soni, Xjk- o'rtacha namuna X i V S k. Kattalik Vk klaster ichidagi vektorlarning bir-biridan chetlanishini tavsiflaydi (yangi S k + S f yoki eski ^). Hisoblash Vk qo'shilishdan oldin va keyin amalga oshirilishi kerak va bunday uyushmalar uchun barcha mumkin bo'lgan variantlardan o'tish kerak. Keyinchalik klasterda S k faqat eng kichik o'zgarishlarga olib keladigan vektorlar yoki klasterlar qo'shiladi Vk birlashgandan so'ng va natijada asl klasterdan minimal masofada joylashgan bo'ladi S k.

Keling, iterativ usullarni ko'rib chiqaylik. Iterativ usullarning mohiyati shundan iboratki, klasterlash ba'zi dastlabki shartlarni belgilashdan boshlanadi. Masalan, hosil bo'ladigan klasterlar sonini belgilash yoki klasterni shakllantirish jarayonining oxirini belgilovchi masofani belgilash kerak va hokazo. Dastlabki shartlar tadqiqotchiga kerakli natijaga qarab tanlanadi. Biroq, ular odatda aglomerativ usullardan biri bilan topilgan eritma yordamida aniqlanadi. Iterativ usullarga ^-vositalar usuli va kondensatsiyalarni qidirish usuli kiradi.

1. /r-means usuli. Vektorlar bo'lsin X l9 ...,X n e9F va ular bo'linishi kerak Kimga klasterlar. Nolinchi qadamda P tasodifiy vektorlarni tanlash Kimga ularning har biri bitta klasterni tashkil etishini hisobga olsak. Biz standart klasterlar to'plamini olamiz,...,e[ 0) og'irliklari bilan

coj 0) ,...,X. va orasidagi masofalar matritsasini hisoblang X. va standartlar e 1 (0),...,^ 0) ba'zi metrikaga muvofiq, masalan, Evklid:

Hisoblangan masofa matritsasi bilimlari asosida vektor X ( masofa minimal bo'lgan ushbu standartga joylashtirilgan. Keling, buni aniq deb taxmin qilaylik. U formula bo'yicha biriktirilgan nuqtani hisobga olgan holda qayta hisoblangan yangisi bilan almashtiriladi

Bundan tashqari, vazn qayta hisoblab chiqiladi:

Agar matritsada ikki yoki undan ortiq minimal masofalar yuzaga kelsa, u holda Xt eng past seriya raqami bilan klasterga kiritilgan.

Keyingi bosqichda qolganlardan keyingi vektor tanlanadi va protsedura takrorlanadi. Shunday qilib, orqali ( Kompyuter) hamma uchun qadamlar

standart e^~ k) vazn mos keladi va klasterlash jarayoni tugaydi. Katta bilan P va kichik Kimga algoritm tezda barqaror yechimga, ya'ni algoritmni birinchi marta qo'llashdan keyin olingan standartlar miqdori va tarkibi bo'yicha usul takrorlanganda topilgan standartlar bilan mos keladigan yechimga yaqinlashadi. Shu bilan birga, algoritmik protsedura har doim bir necha marta takrorlanadi, oldingi hisob-kitoblarda olingan bo'lim standart vektorlar sifatida (dastlabki yaqinlashish sifatida): ilgari topilgan standartlar e[ p k e (2 p k) k) uchun olinadi e (x 0) 9 ... 9 e (k 0) 9 va algoritmik protsedura takrorlanadi.

2. Kondensatsiyalarni qidirish usuli. Bu quyidagi iterativ algoritmdir. Bu klasterlar sonining apriori spetsifikatsiyasini talab qilmaydi. Birinchi bosqichda, orasidagi masofalar matritsasi X X9 ... 9 X p eU1 r ba'zi ko'rsatkichlarga ko'ra. Keyin birinchi klasterning markazi sifatida harakat qilish uchun bitta vektor tasodifiy tanlanadi. Bu dastlabki taxmin. Faraz qilaylik, bu vektor radiusli p o'lchovli sharning markazida yotadi R, va bu radius tadqiqotchi tomonidan belgilanadi. Shundan so'ng vektorlar aniqlanadi X Si ,... 9 X Sk , bu sohaning ichiga tushib, ulardan tanlov hisoblab chiqiladi
- 1 Kimga

belgilangan matematik kutish X = ~Y]X 5. Keyin sharning markazi qayta-

ichida kiyiladi X, va hisoblash tartibi takrorlanadi. Takrorlash jarayonining tugash sharti o'rtacha vektorlarning tengligidir X, topilgan T Va (t+ 1) qadamlar. Sfera ichida ushlangan elementlar X 9 ... 9 X

biz ularni bitta klasterga kiritamiz va keyingi tadqiqotlardan chetlatamiz. Qolgan nuqtalar uchun algoritm takrorlanadi. Algoritm har qanday boshlang'ich taxminiy tanlovi va boshlang'ich ma'lumotlarning istalgan miqdori uchun birlashadi. Biroq, barqaror bo'limni olish uchun (ya'ni, algoritmning birinchi qo'llanilishidan keyin topilgan klasterlar soni va tarkibi bo'yicha usul takrorlanganda topilgan klasterlar bilan mos keladigan bo'lim) algoritmik protsedurani bir necha marta takrorlash tavsiya etiladi. shar radiusining turli qiymatlari uchun R. Barqaror bo'linishning belgisi bir xil tarkibga ega bir xil miqdordagi klasterlarning shakllanishi bo'ladi.

E'tibor bering, klasterlash muammosining yagona yechimi yo'q. Natijada, ma'lumotlarning barcha ruxsat etilgan bo'limlarini sinflarga sanab o'tish juda qiyin va har doim ham mumkin emas. Klasterlashning turli usullarining sifatini baholash uchun eng yaxshi (tadqiqotchi nuqtai nazaridan) bo'lim bo'yicha minimal qiymatni oladigan bo'lim sifati funktsional tushunchasi kiritiladi.

Mayli X X9 ... 9 X p e U1 R - sinflarga bo'lingan ma'lum kuzatishlar to'plami S = (S l9 ... 9 S k ) 9 va Kimga oldindan ma'lum. Keyin ma'lum miqdordagi klasterlar uchun bo'linish sifatining asosiy funktsiyalari shaklga ega:

1) Sinf ichidagi dispersiyalarning vaznli yig'indisi

Qayerda a(1)- klasterni tanlab matematik kutish S l.

Funktsional Q((S) bir butun sifatida barcha klasterlarning bir xillik darajasini baholash imkonini beradi.

2) Elementlar orasidagi juft sinf ichidagi masofalar yig'indisi yoki

Qayerda n 1- klasterdagi elementlar soni S { .

3) Umumlashtirilgan sinf ichidagi dispersiya

Qayerda n j- ichidagi elementlar soni S., A; . - uchun kovariatsiya matritsasi namunasi Sj.

Funktsional - har bir klaster uchun hisoblangan umumlashtirilgan sinf ichidagi dispersiyalarning o'rtacha arifmetik qiymati. Ma'lumki, umumlashtirilgan dispersiya ko'p o'lchovli kuzatuvlarning tarqalish darajasini baholashga imkon beradi. Shunung uchun 3-savol (S) sinflarda kuzatish vektorlarining o'rtacha tarqalishini baholashga imkon beradi S l9 ... 9 S k. Shuning uchun uning nomi - umumlashtirilgan sinf ichidagi dispersiya. 3-savol (S) asl o'lchamidan kichikroq bo'shliqda ma'lumotlarni siqish yoki kuzatishlarni kontsentratsiyalash muammosini hal qilish zarur bo'lganda qo'llaniladi.

4) Kuzatishlarni tasniflash sifatini Hotelling mezoni yordamida ham baholash mumkin. Buning uchun biz gipotezani tekshirish uchun mezonni qo'llaymiz H 0 ikkita ko'p o'lchovli populyatsiyalar o'rtacha vektorlarining tengligi bo'yicha va statistik ma'lumotlarni hisoblang

Qayerda n t Va p t - sinflardagi vektorlar soni Sl, Sm; X,X t- markazlashtirilgan manba ma'lumotlari; S* - birlashtirilgan klasterli kovariatsiya matritsasi S n S m: S* =--- (XjX l +X^X m). Avvalgidek, qiymat 4-savol (S)

p,+p t -2

formula bo'yicha hisoblangan jadval qiymati bilan solishtiriladi

Qayerda m- kuzatish vektorlarining boshlang'ich o'lchami va muhimlik darajasi.

Gipoteza H 0 ehtimol (1-os) bilan qabul qilinadi, agar Q 4 (S) n _ m, va aks holda rad etiladi.

Sinflarga bo'linish sifatini empirik tarzda ham baholash mumkin. Misol uchun, siz har bir sinf uchun topilgan namunaviy vositalarni butun kuzatishlar populyatsiyasining namunaviy o'rtacha qiymati bilan solishtirishingiz mumkin. Agar ular ikki yoki undan ko'p marta farq qiladigan bo'lsa, unda bo'linish yaxshi. Klaster tanlama vositalarini kuzatishlar to'plamining o'rtacha o'rtacha qiymati bilan to'g'ri taqqoslash, sinflarga bo'linish sifatini baholash uchun dispersiya tahlilidan foydalanishga olib keladi.

Agar klasterlar soni bo'lsa S = (S l9 ...,S k) oldindan noma'lum bo'lsa, o'zboshimchalik bilan tanlangan butun son uchun bo'lim sifatining quyidagi funktsiyalaridan foydalaning. m:

IIKimga 1 1 m

- - sinf ichidagi o'rtacha ko'rsatkich -

P i=1 n i XjeSj X"tSj J

boyo'g'li sochilishi,

(1 P/ 1 Vt
- X ~-~ r “ to'plam nuqtalari konsentratsiyasining o'lchovi

P nV l J J

S, - nuqtani o'z ichiga olgan klasterdagi elementlar soni X g

E'tibor bering, parametrning o'zboshimchalik qiymati uchun T funktsional Zm(S) ga teng minimal darajaga etadi I/p, agar dastlabki klasterlash bo'lsa S = (S l9 ...,S k ) monoklasterlarga bo'linishdir S. = (Xj), chunki V(X t) = 1. Shu bilan birga Zm (S) maksimal 1 ga etadi, agar S- barcha dastlabki ma'lumotlarni o'z ichiga olgan bitta klaster;

chunki V(X() = n. Maxsus holatlarda buni ko'rsatish mumkin Z_ l (S) =-, Qayerda Kimga - turli klasterlar soni S = (S l9 ... 9 S k ) 9 Z X (S) = maksimal -,

*" V P)

Qayerda n t - klasterdagi elementlar soni S i9 Z^(S) = min - ,

G" P)

E'tibor bering, klasterlar soni noma'lum bo'lsa, bo'lim sifati funktsionaldir Q(S) ikkita funksionalning algebraik birikmasi (yig‘indi, ayirma, mahsulot, nisbat) ko‘rinishida tanlanishi mumkin I m (S), Z m (S), chunki birinchisi sinflar sonining kamayuvchi, ikkinchisi esa ortib boruvchi funksiyasi Kimga. Bunday xatti-harakatlar Zm(S)

ekstremum mavjudligini kafolatlaydi Q(S).