Klasterlashtirish haqida

I.Klasterlashtirish haqida
1.1 Klastertlashtirish va uning ahamiyati.
Klaster - bu foydalanuvchi nuqtai nazaridan yagona apparat resursini ifodalovchi yuqori tezlikdagi aloqa kanallari orqali ulangan kompyuterlar guruhi. Klaster umumiy ilovalarni bajarish uchun birgalikda ishlaydigan va foydalanuvchiga yagona tizim sifatida ko'rinadigan bir nechta hisoblash tizimlarining erkin bog'langan to'plamidir. Klaster texnologiyasining birinchi me'morlaridan biri Gregori Pfister klasterga quyidagicha ta'rif berdi: "Klaster - parallel yoki taqsimlangan tizimning bir turi bo'lib, u:

• 
  o'zaro bog'langan bir nechta kompyuterlardan iborat;
  
• 
  yagona, yagona kompyuter resursi sifatida foydalaniladi.
  

Odatda, klasterlarning quyidagi asosiy turlari ajratiladi:

• 
  muvaffaqiyatsiz klasterlar (yuqori mavjud klasterlar, HA, yuqori mavjudlik klasterlari)
  
• 
  Yuklarni muvozanatlash klasterlari
  
• 
  hisoblash klasterlari (Yuqori unumdorlikdagi hisoblash klasterlari, HPC)
  
• 
  taqsimlangan hisoblash tizimlari
  

Klasterlash - bu qandaydir mezon bo'yicha bir klasterdagi ob'ektlar boshqa klasterlar ob'ektlariga qaraganda bir-biriga o'xshash bo'lishi uchun ob'ektlar to'plamini kichik to'plamlarga (klasterlarga) guruhlash vazifasidir.Klasterlash muammosi nazoratsiz ta'lim muammolari sinfiga kiradi.
Klasterlash muammosining bayoni X bo'lsin ob'ektlar to'plamidir, Y klasterlarning identifikatorlari (yorliqlari) to'plamidir. X to'plamida r(x,x′) obyektlar orasidagi masofa funksiyasi berilgan. Xm={x1,…,xm}⊂X ob'ektlarning cheklangan o'quv to'plami berilgan. Namunani kichik to'plamlarga (klasterlarga) bo'lish kerak, ya'ni har bir ob'ekt xi∈Xm. mos yorliq yi∈Y, shuning uchun har bir klaster ichidagi ob'ektlar r metrikasiga nisbatan yaqin bo'ladi, va turli klasterlardagi ob'ektlar sezilarli darajada farq qildi.
Ta'rif:
Klasterlash algoritmi - a:X→Y funksiyasi, bu har qanday ob'ekt uchun x∈X, y∈Y klaster identifikatorini bog‘laydi.Y belgilang ba'zi hollarda oldindan ma'lum, lekin ko'pincha vazifa klasterlarning optimal sonini, klasterlash sifatining u yoki bu mezonini aniqlashdan iborat. Klasterlash (nazoratsiz ta'lim) tasniflashdan (nazorat ostidagi ta'lim) farq qiladi, chunki o'quv majmuasidan ob'ektlarning teglari yi. dastlab belgilanmagan va hatto Y to'plamining o'zi ham noma'lum bo'lishi mumkin.
Klasterlash muammosini hal qilish bir qator sabablarga ko'ra ob'ektiv noaniqdir:
-Klasterlash sifati uchun aniq mezon yo'q. Bir qator algoritmlar aqlli "qurilish bo'yicha" klasterlashni amalga oshirishi ma'lum, ammo ularning barchasi turli natijalar berishi mumkin. Shu sababli, klasterlash sifatini aniqlash va tanlangan klasterlarni baholash uchun mavzu bo'yicha mutaxassis kerak;
-Klasterlar soni, qoida tariqasida, oldindan ma'lum emas va sub'ektiv mezonlar bo'yicha tanlanadi. Algoritm sinflar sonini oldindan bilishni talab qilmasa ham, aniq amalga oshirish ko'pincha ushbu parametrni ko'rsatishni talab qiladi ;
-Klasterlash natijasi sezilarli darajada metrikaga bog'liq. Biroq, muammolarning ma'lum sinflari uchun ko'rsatkichlarni tanlash bo'yicha bir qator tavsiyalar mavjud .
Klaynbergning imkonsizlik teoremasi
Klasterlash algoritmlarini rasmiylashtirish uchun aksiomatik nazariyadan foydalanilgan. Klaynberg uchta oddiy xususiyatni klasterlash aksiomalari sifatida ilgari surdi va bu xususiyatlar bilan bog'liq teoremani isbotladi.
Ta'rif:
Klasterlash algoritmi a har qanday masofa funksiyasi uchun r bo'lsa, masshtabda o'zgarmasdir va har qanday doimiy a>0 masofalar yordamida natijalarni klasterlash r va a⋅r mos kelish.
Birinchi aksioma intuitivdir. U klasterlash funktsiyasi masofaviy funksiyalar sanoq tizimidan mustaqil bo'lishini va o'quv namunasining metrik fazosining chiziqli kengayishi va qisqarishiga befarq bo'lishini talab qiladi.
Ta'rif:
To'liqlik (inglizcha boylik). Algoritmning klasterlash natijalari to'plami a masofa funksiyasining o'zgarishiga qarab r X ob'ektlar to'plamining barcha mumkin bo'lgan bo'limlari to'plamiga to'g'ri kelishi kerak. Ikkinchi aksioma shuni ko'rsatadiki, klasterlash algoritmi ba'zi masofaviy funktsiya r uchun o'quv namunasini istalgan sobit bo'limga klasterlash imkoniyatiga ega bo'lishi kerak.
Ta'rif:
Функция расстояния ρ′ является допустимым преобразованием функции расстояния ρ, если

1. 
   ρ′(xi,xj)⩽ρ(xi,xj) если xi и xj лежат в одном кластере;
   
2. 
   ρ′(xi,xj)⩾ρ(xi,xj), если xi и xj лежат в разных кластерах.
   

Ta'rif:
Klasterlash algoritmi, agar masofa funksiyasining haqiqiy o'zgarishidan keyin klasterlash natijasi o'zgarmasa, izchil bo'ladi. Uchinchi aksioma klasterlarning saqlanishini talab qiladi, chunki klaster ichidagi masofa kamayadi va klasterlararo masofa oshadi.

1. Ob'ektlarning dastlabki joylashuvi va ularning klasterlanishi

2. O'lchov o'zgarmasligiga misol. Y o'qi bo'ylab shkala yarmiga kamaydi.
3. Yaroqli konvertatsiyaga misol. Har bir ob'ekt o'z sinfining centroidiga ikki baravar yaqin. Sinf ichidagi masofa qisqardi, sinflararo masofa oshdi.
Ushbu aksiomalarga asoslanib, Klaynberg quyidagi teoremani shakllantirdi va isbotladi:
Teorema (Klaynberg, imkonsizlik haqida):
Ikki yoki undan ortiq elementlardan tashkil topgan ob'ektlar to'plami uchun bir vaqtning o'zida masshtabda o'zgarmas, izchil va to'liq bo'ladigan klasterlash algoritmi mavjud emas.
Bu teoremaga qaramay, Kleinberg turli to'xtash mezonlari bo'lgan yagona bo'g'inli ierarxik klasterlash uchta aksiomadan ikkitasini qanoatlantirishini ko'rsatdi.