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

Maksmin algoritmi. Bu algoritm ni nechta klasterlarga ajratishda klasterlar soni oldindan ma’lum bo’lmaganda ni klasterlarga ajratishda va ushbu jarayonda avtomatik ravishda klasterlar soni ni hosil qilishda yadrolarni ixtiyoriy tanlashga asoslanadi.
timsollar to’plamidan N₁ yadro ixtiyoriy tanlanadi, ya’ni Z₁=S₁. Undan keyin Z₁, Z₂, …, Z_k yadrolar tanlanadi. Yadrolar soni nechta bo’lishi oldindan ma’lum emas. Bu holda yadrolar soni timsollarni klasterlashtirish jarayonida aniqlanadi va topilgan yadrolarga mos K₁, K₂, . . . ,K_m klasterlar hosil bo’ladi. Ushbu algoritm quyidagi qadamlardan iborat:
1. Boshlang’ich timsollar to’plamidan birinchi yadroviy timsol sifatida ixtiyoriy S_j tanlanadi, masalan Z₁=S₁.
2. Z₁ yadroviy timsol bilan barcha timsollar orasidagi masofalar (2.1-2.8) formulalar yordamida aniqlanadi. Natijada

masofalar matrisasi hosil bo’ladi .

3. masofalar matrisasidan topiladi.

4. Ikkinchi yadro sifatida qiymatga mos keluvchi S_j timsol tanlanadi, ya’ni Z₂=S_j .

5. Z₂ yadro timsoldan bilan barcha timsollar orasidagi masofalar (2.1-2.8) formulalar yordamida aniqlanadi. Natijada masofalar matrisasi hosil bo’ladi.
6. masofalar matrisasidan eng kichik masofa topiladi.
7. masofalar matrisasidan eng kichik masofa topiladi.
8. Z₁ va Z₂ yadrolar asosida topilgan va masofalardan eng kattasi

tanlanadi.
9. Z₁ va Z₂ yadrolar orasidagi masofaning yarmi topilad:
10. Agar bo’lsa, u holda yangi yadro sifatida qiymatga mos keluvchi timsol tanlanadi va yadro sifatida belgilanadi va 2-3- qadamlar bajariladi.
Agar klasterlar soni va yadrolar o’zgarmasdan qolsa, algoritm o’z ishini to’xtatadi. Topilgan porog deb nomlanuvchi , ya’ni yadrolar orasidagi masofaning yarmi timsollarni Z₁, Z₂, . . . , Z_l yadrolar yordamida K₁, K₂, . . . , K_l klasterlarga ajratadi. Shuningdek klasterlar soni ham aniqlanadi.
Misol sifatida 7.3- rasmda keltirilgan yadrolarni va klasterlarni keltirish mumkin.

7.3-rasm. Yadrolar va klasterlarni hosil qilish.
Misol. Masalaninig qo’yilishi. Aytaylik timsollar to’plamidan iborat berilgan bo’lsin (7.2-jadval) [2].
7.2-jadval. .

Timsollar	Belgilar
	a1	a2	a3	a4	a5
S1	0	0	1	0	0