Palatalar usuli - Wards method - Wikipedia

Yilda statistika, Uord usuli qo'llaniladigan mezondir ierarxik klaster tahlili. Uordning minimal dispersiya usuli ning alohida holati ob'ektiv funktsiya dastlab Jou H. Ward, Jr.[1] Uord general taklif qildi aglomerativ ierarxik klasterlash protsedura, bu erda har bir bosqichda birlashadigan klaster juftligini tanlash mezonlari ob'ektiv funktsiyalarning maqbul qiymatiga asoslanadi. Ushbu ob'ektiv funktsiya "tergovchining maqsadini aks ettiruvchi har qanday funktsiya" bo'lishi mumkin. Klasterlashning ko'plab standart protseduralari ushbu umumiy sinfda mavjud. Protsedurani tasvirlash uchun Uord maqsad funktsiyasi bo'lgan misolni keltirdi kvadratlarning xato yig'indisi va bu misol sifatida tanilgan Uord usuli yoki aniqroq Uordning minimal dispersiya usuli.

The eng yaqin qo'shni zanjir algoritmi yordamida Uord usuli bilan aniqlangan bir xil klasterni, kirish hajmiga mutanosib ravishda topish uchun foydalanish mumkin masofa matritsasi va klasterlangan nuqtalar soni bo'yicha kosmik chiziqli.

Minimal dispersiya mezonlari

Uordning minimal dispersiya mezonlari klaster ichidagi umumiy dispersiyani minimallashtiradi. Ushbu usulni amalga oshirish uchun har bir qadamda klasterlar juftligini toping, bu esa birlashgandan so'ng klaster ichidagi dispersiyaning minimal o'sishiga olib keladi. Ushbu o'sish klaster markazlari orasidagi tortilgan kvadratik masofa. Dastlabki bosqichda barcha klasterlar singletonlardir (bitta nuqtani o'z ichiga olgan klasterlar). Qo'llash uchun rekursiv algoritm bu ostida ob'ektiv funktsiya, alohida ob'ektlar orasidagi dastlabki masofa kvadratga (mutanosib) bo'lishi kerak Evklid masofasi.

Shuning uchun Uordning minimal dispersiya usulidagi dastlabki klaster masofalari nuqtalar orasidagi kvadrat evklid masofasi sifatida aniqlanadi:

Eslatma: Ward usulini tatbiq etadigan dasturiy ta'minotda funktsiya argumentlari evklid masofalarini yoki kvadrat evklid masofalarini ko'rsatishi kerakligini tekshirish muhimdir.

Lens-Uilyams algoritmlari

Uordning minimal dispersiya usulini Lens-Uilyams algoritmi rekursiv ravishda aniqlab olishi va amalga oshirishi mumkin. Lens-Uilyams algoritmlari - bu har bir bosqichda klaster masofalarini yangilashning rekursiv formulasi bilan ifodalangan aglomerativ ierarxik klasterlash algoritmlarining cheksiz oilasi (har bir juft klaster birlashganda). Har bir qadamda ob'ektiv funktsiyani optimallashtirish kerak (birlashish uchun eng yaxshi klaster juftligini toping). Rekursiv formulalar optimal juftlikni topishni soddalashtiradi.

Deylik, klasterlar va birlashtirilishi kerak edi. Shu nuqtada barcha mavjud juftlik klaster masofalari ma'lum. Rekursiv formulalar klasterlarning birlashishini kutayotganidan so'ng yangilangan klaster masofalarini beradi va . Ruxsat bering

  • , va klasterlar orasidagi juftlik masofasi bo'ling , va navbati bilan,
  • yangi klaster orasidagi masofa va .

Agar yangilangan klaster masofasi bo'lsa, algoritm Lens-Uilyams oilasiga tegishli tomonidan rekursiv ravishda hisoblanishi mumkin

qayerda va parametrlar bo'lib, ular klaster o'lchamlariga bog'liq bo'lishi mumkin, ular klaster masofasi funktsiyasi bilan birgalikda klasterlash algoritmini aniqlang. Kabi bir nechta standart klaster algoritmlari bitta aloqa, to'liq bog'lanish, va guruh o'rtacha usuli yuqoridagi turdagi rekursiv formulaga ega. Standart usullar uchun parametrlar jadvali bir nechta mualliflar tomonidan berilgan.[2][3][4]

Uordning minimal dispersiya usuli Lens-Uilyams formulasi bo'yicha amalga oshirilishi mumkin. Ajratilgan klasterlar uchun va o'lchamlari bilan va mos ravishda:

Demak, Uordning metodini Lens-Uilyams algoritmi sifatida amalga oshirish mumkin

O'zgarishlar

Uord usulining mashhurligi uning turlicha bo'lishiga olib keldi. Masalan, Uordp funktsiyalar turli xil klasterlarda turli darajadagi ahamiyatga ega bo'lishi mumkin degan intuitiv g'oyadan kelib chiqib, klasterga xos xususiyatlar og'irliklaridan foydalanishni joriy qiladi. [5]

Adabiyotlar

  1. ^ Ward, J. H., Jr. (1963), "Ob'ektiv funktsiyani optimallashtirish uchun ierarxik guruhlash", Amerika Statistik Uyushmasi jurnali, 58, 236–244.
  2. ^ Cormack, R. M. (1971), "Tasnifning sharhi", Qirollik statistika jamiyati jurnali, A seriyasi, 134(3), 321-367.
  3. ^ Gordon, A. D. (1999), Tasnif, 2-nashr, Chapman va Xoll, Boka Raton.
  4. ^ Milligan, G. W. (1979), "Ultrametrik ierarxik klaster algoritmlari", Psixometrika, 44(3), 343–346.
  5. ^ R.C. de Amorim (2015). "Lp normasidan foydalangan holda Wardning iyerarxik klasterlashidagi xususiyatning dolzarbligi" (PDF). Tasniflash jurnali. 32 (1): 46–62. doi:10.1007 / s00357-015-9167-1. S2CID  18099326.

Qo'shimcha o'qish

  • Everitt, B. S., Landau, S. va Liz, M. (2001), Klaster tahlili, 4-nashr, Oxford University Press, Inc., Nyu-York; Arnold, London. ISBN  0340761199
  • Xartigan, J. A. (1975), Klasterlash algoritmlari, Nyu-York: Uili.
  • Jeyn, A. K. va Dubes, R. C. (1988), Ma'lumotlarni klasterlash algoritmlari, Nyu-Jersi: Prentis-Xoll.
  • Kaufman, L. va Russeu, P. J. (1990), Ma'lumotlardan guruhlarni topish: Klaster tahliliga kirish, Nyu-York: Uili.