1-ma’ruza. Berilganlarni intellektual tahliliga kirish

K-means usuli. K-means (k-o‘rtacha) usuli 1950 yillarda Gugo Shteyngauz va Styuard Lloydlar tomonidan bir vaqtda kashf qilingan klasterizatsiyaning eng mashhur usulidir. Algoritmning mazmuni klaster nuqta (obyekt)larining shu klaster markazidan kvadratik og‘ishining yig‘indisini minimizatsiya qilishga harakat qilinadi:

bu yerda k – klasterlar soni, - olingan klasterlar, ва - эса vektorlarning massa markazi.
Ikki o‘lchamli alomatlar fazosida algoritm namoyishi:

Берилган барча нуқталар ва тасодифий танланган бошланғич нуқталар

Бошланғич марказларга тегишли нуқталар. Текисликни Воронов диаграммасига ёрдамида бошланғич марказларга нисбатан бўлиш.

Кластерлар янги маркази ҳисобланади. (масса маркази изланади)

Марказлар силжимай қолгунча олдинги қадамлар такрорланади.

Klasterlash algoritmlarini ko‘raylik.

Algoritm oldindan k – klasterlar sonini berilishini talab qiladi.

Algoritm quyidagi qadamlardan iborat bo‘ladi:

1. 
   Har bir k klaster uchun ixtiyoriy ravishda uning markazi sifatida bo‘lgan obraz tayinlanadi. Aksariyat holatlarda o‘rgatuvchi tanlanmaning birinchi (yoki tasoddifiy olingan) k та obrazlar olinadi.
   
2. 
   Tanlanmaning har bir obrazi, markazigacha bo‘lgan masofa minimal bo‘lgan sinfga tegishli deb hisoblanadi:
   

.

3. 
   Sinfga qanday obrazlar kirganligini inobatga olgan holda klasterlar markazi qayta aniqlanadi:
   

,
бу ерда sinfga tushgan obrazlar miqdori.

4. 
   Yaqinlashishga erishilguncha, ya’ni sinflar o‘zgarmay qolguncha 2 va 3 qadamlar takrorlanadi.
   

Garchi, k o‘rtacha algoritmi obrazlar juftligi uchun hisoblanadigan yaqinlik funksiyasiga asoslangan bo‘lsa ham, uning global o‘lchovni, ya’ni obrazlarning o‘z sinfining markaziga chetlashuvining o‘rtakvadratik yig‘indisini minimizatsiya qiladi.
k o‘rtacha algoritmining kamchiliklari:

• 
  sinflar sonini oldindan berilishidir. Ushbu muammoni yechish uchun algoritmni turli sondagi sinflar uchun amalga oshirib va ular ichidan qandaydir mezon bo‘yicha eng yaxshisini tanlashdir. Mezon sifatida obrazlardan sinflar markazlaridan masofalari yig‘indisini minimallashtirishda katta sondagi sinflar bo‘lgan yechimlarga ustunlikka erishadi, shu sababli yanada murakkab mezonlar talab qilinadi.
  
• 
  natija klaster boshlang‘ich markazlarini tanlashga bog‘liq, ularni optimal tanlash noma’lum.
  

Sinflar sonini oldindan berilishini talab qilmaydigan algoritmlar ham mavjud. Lekin ularning aksariyatida u yoki bu parametrlar qatnashadi. Klaster o‘lchami - bo‘sag‘ani berilishini talab qiluvchi sodda algoritmlardan biri quyidagi qadamlardan iborat bo‘ladi:

1. 
   O‘rgatuvchi tanlanmaning birinchi obrazidan bitta klaster
   

shakllantirilsin va hisoblansin.

2. 
   Navbatdagi, qaralmagan vektor tanlansin va
   

. Агар ушбу масофа бўсағадан кичик бўлса ( ), obraz mos sinfga tegishli deb hisoblansin, aks holda sinflar soni bittaga oshiriladi va markazi bo‘lgan yangi sinf shakllantiriladi.

3. 
   Tanlanmaning barcha obyektlari uchun 2 –qadam takrorlansin.
   

Bu algoritm har bir obrazni bir martagina qandaydir sinfga tegishli deb aniqlashni talab qiladi va hisoblash nuqtai-nazaridan samarali bo‘lsa ham obrazlarni taqdim etish ketma-ketligiga kuchli bog‘liqdir. Algoritmning o‘ziga xosligidan biri - bo‘sag‘aning barcha sinflarga bir xil ekanligidir.

Agar bo‘sag‘a qiymati oldindan ma’lum bo‘lmasa, algoritmni bir nechta bo‘sag‘alar uchun bajarib, qandaydir mezon bo‘yicha eng yaxshi yechim tanlanadi.
Shuni qayd qilish kerakki, algoritm inkrement o‘rganishning sodda algoritmi sifatida qiziqish uyg‘otadi. Haqiqatan ham, obrazlar ketma-ket taqdim qilinadi va uning ishlashini quyidagicha izohlash mumkin bo‘ladi: yangi uchragan obraz oldindan aniqlangan sinflarning birortasiga ham o‘xshamasa, demak u oldin uchramagan sinflarning biriga tegishli. Agar obyekt ishonchli ravishda sinflangan bo‘lsa, tanlanga sinf bo‘yicha ma’lumotni to‘ldiradi: uning asosida sinf modeli yanadi aniqlashadi (bu holda o‘rtacha vektor siljiydi).
Klasterlar qurishning boshqa strategiyalarini qo‘llashga asoslangan algoritmlar mavjud. Masalan, maksmin masofa algoritmida oldin sinflar prototipi sifatida bir-biridan eng uzoqlashgan (eng farqlanadigan) obrazlar ajratib olinadi. Shunday qilib, bir sinfga kiruvchi obyektlar o‘xshashligini maksimallashtirishdan tashqari turli sinflar obyektlarining farqlanishini ham maksimallashtiriladi.