Ob'ektlarni tekislikdagi nuqta shaklida joylashtirish 1-rasmda keltirilgan

7.1.5 Ierarxik klaster protseduralari

Ierarxik (daraxtga o'xshash) protseduralar - bu kompyuterda amalga oshirishga asoslangan klasterlarni tahlil qilishning eng keng tarqalgan algoritmlari. Ular ikki xil: alomerativ va bo'luvchi. Aromrativ protseduralarda boshlang'ich bo'lim subelement sinflaridan iborat bo'lim bo'lib, yakuniy bo'lim bitta sinfdan iborat; aksincha, bo'linishda.

Ierarxik alomerativ (bo'linuvchi) protseduralarning ishlash printsipi elementlar guruhlarini ketma-ket unifikatsiyalashdan (ajratishdan) iborat bo'lib, avvaliga eng yaqin (uzoq), so'ngra bir-biridan tobora uzoqroq (yaqin). Ushbu algoritmlarning aksariyati masofa (o'xshashlik) matritsasidan kelib chiqadi.

Ierarxik protseduralarning kamchiliklariga ularni hisoblashda amalga oshirishning noqulayligi kiradi. Algoritmlar matritsaning har bir bosqichida masofani hisoblashni talab qiladi, shuning uchun katta hajmli kompyuter xotirasi va ko'p vaqt talab etiladi. Shu munosabat bilan, kuzatuvlar soni, bir necha yuzdan ortiq bunday algoritmlarni amalga oshirish, amaliy emas, va ba'zi hollarda mumkin emas.

Keling, aglomerativ ierarxik algoritmga misol keltiraylik. Birinchi bosqichda har bir kuzatish X_i (i = 1,2,.... n) alohida klaster sifatida qaraladi. Kelajakda, algoritm ishining har bir bosqichida ikkita eng yaqin Klaster birlashtiriladi va qabul qilingan masofani hisobga olgan holda, masofa matritsasi formula bo'yicha hisoblab chiqiladi, uning o'lchami, albatta, bir birlikka kamayadi. Algoritm ishi barcha kuzatishlar bir sinfga birlashtirilganda tugaydi. Ierarxik tasniflash algoritmini amalga oshiradigan dasturlarning aksariyati tasnifning grafik ko'rinishini Dendrogramma shaklida taqdim etadi.

Misol 7.1

Har biri ikkita xususiyat bilan tavsiflangan n = 6 ta ob'ekt tasnifini o'tkazing:

Ob'ektlarni tekislikdagi nuqta shaklida joylashtirish 7.1-rasmda keltirilgan.

7.1-rasm. Ob'ektlarni tasnifi

Yechish:

Aglomerativ ierarxik tasniflash algoritmidan foydalanamiz. Ob'ektlar orasidagi masofa sifatida odatdagi Evklid masofasini oling. Keyin formulaga (7.2) ko'ra, birinchi va ikkinchi ob'ektlar orasidagi masofa

va birinchi va uchinchi ob'ektlar orasida

Shubhasiz, bu

Xuddi shunday, biz oltita ob'ekt orasidagi masofani topamiz va masofa matritsasini quramiz

Masofa matritsasidan to'rtinchi va beshinchi ob'ektlar P_4.5 = 1,00 ga eng yaqin bo'lib, shuning uchun bir guruhga qo'shiladi.

Ob'ektlarni birlashtirgandan so'ng bizda beshta klaster mavjud:

Klasterlar orasidagi masofa "eng yaqin qo'shni" tamoyili bo'yicha qayta hisoblash formulasidan (7.11) foydalanib aniqlanadi. Shunday qilib, ob'ekt S₁ va Klaster S_4.5 o'rtasidagi masofa

Shunday qilib, P_1.(4.5) masofasi 1 ob'ektidan S_(4.5) klasteriga kiruvchi eng yaqin ob'ektga, ya'ni p_1.(4.5) = p_1.4 = 5,10 ga teng. Keyin masofa matritsasi

Eng kichik masofaga ega bo'lgan ikkinchi va uchinchi narsalarni birlashtiramiz p_2.3= 1,41. Ob'ektlarni birlashtirgandan so'ng bizda to'rtta Klaster mavjud:

Shunga qaramay, masofa matritsasini topamiz. S_(2,3) klasteriga masofani hisoblash uchun R₂ masofa matritsasidan foydalanamiz. Masalan, S_(4,5) va S_(2,3) klasterlari orasidagi masofa tengdir

7.2-rasm. Dendrogramma

Shu kabi hisob-kitoblarni amalga oshirgandan so'ng, biz olamiz

Biz S_{( 4,5)} va S₍₆₎ klasterlarini birlashtiramiz, ular orasidagi masofa R₃ matritsasiga ko'ra, eng kichik p_{( 4 .5).6} = 2. Natijada, biz uchta klasterni olamiz

Masofa matritsasi shunday ko`rinishda paydo bo'ladi:

Keling ,S₁ va S_{( 2, 3)} klasterlarini birlashtiramiz, ular orasidagi masofa P_1.(2.3) = 2,24. Natijada biz ikkita guruhni olamiz: S_(1,2.3) va S_{( 4.5.6)}, "eng yaqin qo'shni" tamoyili bo'yicha topilgan masofa, P_{(1,2,3), (4,5,6)}=5 .

Ob'ektlarning ierarxik tasnifi natijalari 7.2-rasmda Dendrogramma shaklida keltirilgan.

7.2-rasmda ushbu bosqichda birlashtirilgan guruhlar (ob'ektlar) orasidagi masofa ko'rsatilgan. Bizning misolimizda, barcha ob'ektlar ikki guruhga birlashtirilganda tasnifning oldingi bosqichiga ustunlik berilishi kerak (7.2-rasm)