11-Mavzu. O’qituvchisiz (Unsupervised) o’qitish algoritmlari Reja: O’qituvchisiz o’qitish tushunchasi va uning usullari

11-Mavzu. O’qituvchisiz (Unsupervised) o’qitish algoritmlari

Reja:

1. O’qituvchisiz o’qitish tushunchasi va uning usullari.

2. Obyektlarni klasterlash masalasini formallashtirish va echish.

3. Obyektlarni klasterlash usullari va ulardan foydalanish.

4. Obyektlar to’plamidan yadro obyektlarni tanlash usullari.

5. Klasterlar soni oldindan berilganda klasterlash algoritmlari.

5.1. Ikkita yadro ob’yekt asosida klasterlash algoritmi.

5.2. K ta yaqin qo’shnilarni izlash algoritmi.

5.3. Tayanch obyektlar asosidaklasterlash algoritmi.

5.4. Belgilarni ketma-ket tanlash asosida klasterlash algoritmi.

6. Klasterlar soni oldindan berilmaganda klasterlash algoritmlari.

6.1. Maksmin algoritmi.

6.2. K o’rtacha algoritmi.

6.3. Izodata algoritmi.

7. Klsterlash dasturlar paketi va uning tasnifi

7.1. Dasturiy paket strukturasi.

7.2. Dasturiy paketning tasnifi va undan foydalanish tartibi.

Obyekt, belgi, oʻqituvchisiz o’qitish, oʻqituvchili o’qitish, o’qituvchisiz o’qitish, tanlanma, xossa, klaster, hal qiluvchi funksiya, klasterizatsiyalsh, binar xossalar toʻplami, butun sonlar toʻplami, kesmadagi nuqtalar toʻplami, nominal xossalar toʻplami, sohalarga ajratuvchi chegaralar, yadro, tayanch obyekt, Maksmin algoritmi, K o’rtacha algoritmi, Izodata algoritmi. Bul vektori, ajratuvchi funksiya, hal qiluvchi funksiya, deterministik, stoxastik, ehtimolli, yaqinlik o’lchovi, bo’sag’a qiymat, o’xshashlik koeffisiyenti, bog’liqlik koeffisiyenti, metrik fazo, qaror qabul qiluvchi qoida, Yevklid masofasi, potensial funksiya, Xemming masofasi, Manxetten masofasi, boshqaruvchi vector.
Tayanch iboralar:
Misol. Agar belgilar bilan berilgan OTni qarasak, u holda ularni K1 va K2 klassterlarga xatosiz ajratuvchi funksiyani 11.5- rasmdagidek va xatoli ajratuvchi funksiyani 11.6 - rasmdagidek tasavvur qilamiz:
f(x)>0
f(x)<0
K1
K2
11.5-rasm. OTni klassterlarga xatosiz ajratish
f(x)>0
f(x)<0
K1
K2
11.6 - rasm. OTni klassterlarga xatoli ajratish
11.7-rasm 11.8-rasm 11.9-rasm
11.10-rasm 11.11-rasm 11.12-rasm
Umumiy holda tanlanmadagi OTni klasterlarga yadrolar yordamida ajratish quyidagicha amalga oshiriladi: qandaydir usullar (evristik, tavakkal) bilan ta boshlang’ich yadrolar topiladi. Undan keyin tanlangan yadrolar asosida klasterlashtiriladi. Hosil bo’lgan klasterlarda yana yangi yadrolar topiladi va ushbu yadrolar asosida obyektlar yana klasterlashtiriladi va oldingi klasterlar bilan solishtiriladi. Agar solishtirish natijasida klasterlar va yadrolar o’zgarmasa, u holda klasterlashtirish jarayoni tugallangan hisoblanadi, aks holda yana yangi yadrolar topiladi va ularga nisbatan klasterlashtirish jarayoni davom etadi[4, 7, 8].
Bu jarayonni quyidagi rasm yordamida tushuntiramiz. Rasmda “.” belgi yordamida tanlanmadagi obyektlarni belgilaymiz. Klasterlar soni K oldindan berilganda (bu rasmda K=2) har bir klasterdan bittadan yadroviy obyekt tanlanadi va bu yadrolarni mos ravishda “.” va “X” bilan belgilaymiz(11.13-расм). Bu yadrolarni ixtiyoriy olishimiz mumkin.
a) b)
v) g) d)
11.13-расм. bu yerda -boshlang’ich obyekt, - C1 klaster, X - C2 klaster.
Undan keyin har bir yadroga eng yaqin bo’lgan obyekt olinadi va ushbu obyektlarga nisbatan C1 va C2 klasterlarni hosil qilinadi. Keyin yangi yadrolar topiladi. Bu yadrolar sifatida C1 va C2 klasterlardagi markaziy obyektlarga yaqin bo’lgan obyektlar olinadi va bu obyektlar yordamida vaqtinchalik C1 va C2 klasterlar hosil qilinadi va h.k. Bu jarayon C1 va C2 klasterlar o’zgarmaguncha davom ettiriladi va hosil bo’lgan klasterlarlar o’zgarmas klasterlar sifatida qabul qilinadi [10-13].
Har bir klaster uchun yadrolarni topishning yana bir usullaridan biri, bu yadro sifatida har bir klasterdan markaziy obyektni olishdir. Ushbu markaziy obyektlar yordamida tanlanmadagi OT klasterlashtiriladi.
Keyin ushbu klasterlardagi markaziy obyektlarga eng yaqin bo’lgan boshqa ikkita obyekt yordamida yana boshqa klasterlar hosil qilinadi. Bu jarayon klasterlar o’zgarmas holda kelguncha davom ettiriladi.
Yadrolarni tanlashning ikkinchi bir usuli, bu ehtimol qonunlariga asoslangan bo’lib, bunda yadro sifatida ixtiyoriy obyekt olinadi. Shuning uchun bu holda bir nechta klasterlar olinishi mumkin. Lekin amaliyot ko’rsatadiki, bu holda ba’zi bir obyektlar majmuasi ko’p hollarda bitta klasterga tushadi, ba’zi bir obyektlar goh bir klasterga, goh boshqa klasterga tushadi. Bir klasterga tushadigan obyektlarni kuchli obyektlar va klasterlarni o’zgartiradigan obyeklarni esa kuchsiz obyektlar deb ataymiz.
5. Klasterlar soni oldindan berilganda klasterlash algoritmlari
OTni klasterlash algoritmlarining umumiy strukturasi 11.14-rasmda keltirilgan.
11.14-rasm.
OT
Determinalli
Extimolli
Nominal
Mantiqiy
Strukturali
Obyektning belgilari
Obyektlarning belgilari
Obyektlarni o’zini-o’zi o’rganish asosida avtomatik klasterlash
Obyektlarni l ta klasterlarga ajratish
Yangi obyektlarni klasterlash
Qaror qabul qiluvchi qoidani qurish
O’qituvchisiz
obyektlarni klasterlash
5. Ob’yektlarni va klasterlarga ajratish qoidasi
Ushbu algoritmning dasturiy ta’minot 11.15-rasmda keltirilgan.
11.15. –rasm.
OTni klasterlarga ajratishda klasterlar soni oldindan ma’lum bo’lganda, OTni bir-biridan eng uzoqda joylashgan yadroviy ob’yektlar asosida klasterlash algoritmning EHMda bajariladigan operasiyalar soni tanlanmadagi belgilar soni n va obyektlar soni m ga bevosita bog’liq.