7- laboratoriya mashg’uloti Mavzu: Shaxs imzolarini «Maxmin» algoritmi asosida klasterlashning dasturiy ta’minoti

S2	0	1	0	1
0
S3	0	1	0	0	1
S4	1	0	1	0	0
S5	1	0	1	0	1
S6	0	1	0	1	1
S7	1	0	1	0	1
S8	1	1	0	1	1

Talab qilinadi: Maksmin algoritmidan foydalanib berilgan timsollar to’plamini sinflarga ajrating va bu jarayonda sinflar sonini hosil qiling.
Masalaning yechilishi. Timsollarning to’plamidan birinchi timsol ixtiyoriy tanlanadi va birinchi timsoldan barcha timsollargacha masofalar hisoblanadi:








Masofalar orasidan eng kattasi aniqlanadi:

Demak timsoldan eng uzoqda joylashgan timsol ekanligi aniqlandi. Shuning uchun ikkinchi yadro sifatida tanlanadi va ushbu timsoldan barcha timsollargacha masofalar hisoblanadi:








и timsollarga nisbatan hisoblangan masofalar orasidan eng kichigi aniqlanadi:


va qiymatlardan eng kattasi aniqlanadi:

va yadrolar orasidagi masofaning yarmi aniqlanadi:

va ushbu qiymat bo’sag’a sifatida o’rnatiladi.
Hosil qilingan bo’sag’a qiymat bilan taqqoslanadi: .
Bundan ko’rinadiki, topilgan eng katta qiymat qiymatdan oshmaypti. Shuning uchun yangi yadro topilmaydi. Aniqlangan ikkita va yadrolar orqali timsollar to’plamini ikkita va sinflarga ajratamiz..
Natija. Demak shartni qanoatlantiruvchi timsollarni sinfga va shartni qanoatlantiruvchi timsollarni sinfga birlashtiramiz (7.3-jadval).
7.3-jadval.

Sinflar	Timsollar	Belgilar
		a1	a2	a3	a4	a5
K1	S1	0	0	1	0	0
	S4	1	0	1	0	0
	S5	1	0	1	0	1
	S7	1	0	1	0	1
K2	S2	0	1	0	1	0
	S3	0	1	0	0	1
	S6	0	1	0	1	1
	S8	1	1	0	1	1

Natijada timsollar to’plami ikkita va sinflarga ajratildi.

Shaxs imzolarini maxmin algoritmi asosida sinflash algoritmi. Bizga shaxs imzolar toʻplamidan iborat tanlov ( -shaxs imzolardagi belgilar soni, -shaxs imzolar soni) berilgan boʻlsin. tanlovdagi -shaxs imzosini belgilar roʻyxatini berish mumkin.
tanlovdagi shaxs imzolarini oʻqituvchisiz, ya’ni oʻzini-oʻzi oʻrganish jarayonida sinf(shaxs)larga ajratishdan, y’ani dan tanlovni hosil qilishdan iborat, bu erda - hosil qilinisi kerak boʻlgan sinf(shaxs)lar soni.
shaxs imzolar toʻplamini sinflashda ikkita hol boʻlisi mumkin. Birinchisi shaxs imzolar toʻplamini oldindan ma’lum boʻlgan sinflarga ajratish boʻlsa, ikkinchisi shaxs imzolar toʻplamini sinflashda sinflar soni ma’lum boʻlmaydi. Ikkinchi holda hosil qilinadigan sinflar soni ma’lum boʻmaganda shaxs imzolar toʻplami avtomatik ravishda sinflarga ajratiladi, bunda sinflar soni shaxs imzolar toʻplami ni sinflash jarayonida hosil boʻladi.
Ushbu algoritmda birinch hol qaralgan boʻlib, unda shaxs imzolari toʻplamini sinflarga ajratishda sinflar soni oldindan ma’lum boʻlganda imzolarni ixtiyoriy tanlash asosida ularga nisbatan sinflarni hosil qilish masalasi qaralqan.
Algoritm quyidagi qadamlardan iborat:
1. Boshlangʻich ma’lumotlar: shaxs imzolari soni, imzolar tushiriladigan retseptor toʻrining oʻlchami kiritiladi.
2. Imzolar kiritiladi:
2.1. Shaxs nomi va imzolari skaner yordamida.
2.2. Shaxs nomi va imzolari sichqoncha yordamida.
3. Imzolar kodlashtiriladi:
4. imzoning retseptor toʻri bir oʻlchamli koʻrinishga keltiriladi.
5. Agar boʻlsa, u holda algoritm 3-qadamga oʻtadi, aks holda 6-qadamga oʻtadi.
7. Kodlashtirilgan imzolar ketma-ket tanlovga joylashtiriladi, bu erda - imzo belgilari soni, - imzolar soni.
7. tanlovdagi imzolar orasidagi masofalar yordamida aniqlanadi. Natijada masofalar matritsasi hosil boʻladi
, i=1,n; j=1,n.
8. matritsadan eng katta masofa topiladi. qiymatga mos keluvchi va imzolar boshlangʻich yadrolar sifatida tanlanadi.
9. Yadrolar va belgilanadi.
10. tanlovdagi shaxs imzolaridan va yadrolardan
tashqari yadrolar ixtiyoriy ravishda tanlanadi.
_11. shaxs imzolardan tanlangan yadrolar orasidan yadro olinadi.
_12. shaxs imzolardan tanlangan yadrolar orasidan yadro olinadi.
7. va yadrolar orasidagi masofa yordamida aniqlanadi.
_14. Agar boʻlsa, u holda algoritm 12-qadamga oʻtadi, aks holda 15-qadamga oʻtadi.
15. Natijada masofalar massivi hosil boʻladi.
17. masofalar massividan eng kichik masofa tanlanadi, ya’ni .
17. yadroga asosida eng yaqin yadro orasidagi masofaning yarmi topiladi.
_18. imzolar orasidan yadroga nisbatan hosil qilinadigan sinfga qarashliligi

aniqlanadi.
19. Agar boʻlsa, u holda algoritm 11-qadamga oʻtadi, aks holda 20-qadamga oʻtadi.
20. Natijada imzolar orasidan ixtiyoriy tanlangan yadrolarga nisbatan sinflar

hosil boʻladi. Bu erda .
Ushbu algoritm asosida dasturiy ta'minot ishlab chiqildi [20, 21].