Xitoy shiviri (klasterlash usuli) - Chinese Whispers (clustering method)

Xitoy pichirlari mashhur nomi bilan atalgan tarmoq fanida qo'llaniladigan klasterlash usuli pichirlash o'yin.[1] Klasterlash usullari asosan ma'lum bir tarmoqdagi tugunlar yoki bog'lanishlar jamoalarini aniqlash uchun ishlatiladi. Ushbu algoritm tomonidan ishlab chiqilgan Kris Biemann va Sven Tereznyak 2005 yilda.[1] Ism aslida bu jarayonni tugunlar bir-biriga bir xil turdagi ma'lumotlarni yuboradigan jamoalarni ajratish sifatida modellashtirish mumkinligidan kelib chiqadi.[1]

Chinese Whispers - bu qattiq bo'linish, tasodifiy, tekis klaster (yo'q klasterlar orasidagi ierarxik munosabatlar ) usuli.[1] Tasodifiy xususiyat shuni anglatadiki, bir xil tarmoqdagi jarayonni bir necha marta bajarish turli xil natijalarga olib kelishi mumkin, qattiq qismlarga bo'linishi tufayli bitta tugun ma'lum bir lahzada faqat bitta klasterga tegishli bo'lishi mumkin. Asl algoritm yo'naltirilmagan, vaznli va vaznsiz grafikalar uchun amal qiladi. Xitoycha shivirlashlar vaqtga to'g'ri keladi, ya'ni tarmoqdagi tugunlar va havolalar soni juda ko'p bo'lsa ham, bu juda tez.[1]

Algoritm

Xitoy pichirlari amalda qanday ishlashiga misol. Turli xil ranglar turli sinflarni anglatadi.

Algoritm yo'naltirilmagan vaznsiz grafikada quyidagi tarzda ishlaydi:[1]

  1. Barcha tugunlar alohida sinfga biriktirilgan (Dastlabki sinflar soni tugunlar soniga teng).
  2. Keyin barcha tarmoq tugunlari tasodifiy tartibda birma-bir tanlanadi. Har bir tugun ushbu tugun eng ko'p bog'langan sinfga o'tadi. Tenglik holatida klaster tasodifiy teng bog'langan sinflar orasidan tanlanadi.
  3. Ikkinchi qadam oldindan belgilangan takrorlanish sonigacha yoki jarayon yaqinlashguncha takrorlanadi. Oxir oqibat paydo bo'layotgan sinflar tarmoqning klasterlarini ifodalaydi.

Takrorlashlar soni uchun oldindan belgilangan chegara kerak, chunki jarayon yaqinlashmasligi mumkin. Boshqa tomondan, taxminan 10000 tugunli tarmoqdagi klasterlar, hatto yaqinlashish bo'lmasa ham, 40-50 marta takrorlangandan keyin sezilarli darajada o'zgarmaydi.[1]

Kuchli va zaif tomonlari

Chinese Whispers-ning asosiy kuchi uning vaqtli xususiyatiga bog'liq. Tugun soniga qarab ishlov berish vaqti chiziqli ravishda ko'paygani uchun algoritm tarmoqdagi jamoalarni juda tez aniqlashga qodir. Shu sababli xitoycha pichirlashlar juda ko'p sonli tugunlarga ega bo'lgan grafadagi jamoat tuzilmalarini tahlil qilish uchun yaxshi vositadir. Agar tarmoq mavjud bo'lsa, usul samaradorligi yanada oshadi kichik dunyo mulki.[1]

Boshqa tomondan, algoritm kichik tugunli raqamda deterministik bo'lmaganligi sababli hosil bo'lgan klasterlar bir-biridan sezilarli darajada farq qiladi. Buning sababi shundaki, kichik tarmoq uchun iteratsiya jarayoni qaysi tugundan boshlanishi muhimroq, katta tarmoqlarda esa boshlang'ich nuqtalarning dolzarbligi yo'qoladi.[1] Shu sababli kichik grafikalar uchun klasterlashning boshqa usullari tavsiya etiladi.

Ilovalar

Chinese Whispers tarmoq fanining ko'plab subfediallarida qo'llaniladi. Ko'pincha bu kontekstda tilga olinadi tabiiy tilni qayta ishlash muammolar.[2][3] Boshqa tomondan, algoritm tarmoq doirasi bilan bog'liq har qanday hamjamiyatni identifikatsiya qilish muammolariga nisbatan qo'llaniladi. Chinese Whispers shaxsiy foydalanish uchun kengaytma to'plami sifatida mavjud Gephi[4] qaysi bir ochiq manba tarmoqni tahlil qilish uchun mo'ljallangan dastur.

Adabiyotlar

  1. ^ a b v d e f g h men Kris Biemann,"Xitoy shivirlashlari - grafiklarni klasterlashning samarali algoritmi va uning tabiiy tillarni qayta ishlash muammolariga tatbiq etilishi", 2006
  2. ^ Antonio Di Marko - Roberto Navigili,"Grafik asosidagi Word Sense induksiyasi yordamida veb-qidiruv natijalarini klasterlash va diversifikatsiya qilish", 2013
  3. ^ Ioannis Korkontzelos - Suresh Manandxar,"Ko'p so'zli iboralarda kompozitsionlikni aniqlash", 2009
  4. ^ ""Gephi bozori"". Arxivlandi asl nusxasi 2015-09-23. Olingan 2015-06-02.

Tashqi havolalar