Ierarxik klasterlash Utkirbek Qutfiddinov, 705-21

Ierarxik klasterlash

Utkirbek Qutfiddinov, 705-21

Kiberxavfsizlik fakulteti talabasi

Reja

• Klasterlash nima?
• Klasterlash algoritmlarining turlari
• K-means, Mean-shift, DBSCAN and EMGMM algoritmlari, ularning ishlash prinsipi va ularning afzallik va kamchiliklari haqida
• Ierarxik klasterlash
• Xulosa

Klasterlash nima?

Klaster tahlili yoki klasterlash deb bir biriga ko`proq o`xshash bo`lgan elementlarni bir guruhga jamlash amaliyotiga aytiladi.

Klasterlash algoritmlarining turlari

• K-Means klasterlash algoritmi
• Mean-Shift klasterlash algoritmi
• DBSCAN (Density-Based Spatial Clustering of Applications with Noise) klasterlash algoritmi
• EMCGMM (Expectation–Maximization Clustering using Gaussian Mixture Models) klasterlash algoritmi
• Agglomerativ klasterlash algoritmi

K-means klasterlash algoritmi

Afzallik va kamchiliklari

• Afzalligi:
• Ishlash tezligi yuqori
• Qisqa sondagi hisoblashlash yetarli
• Murakkabligi: O(n)

Kamchiligi:

• Tasodifiy tanlangan markazlar bilan ishlaydi
• Bir necha klasterlarni tanlaydi

Mean-shift Klasterlash algoritmi

to`liq jarayon

Afzallik va kamchiliklari

• Afzalliklari:
• Bir necha klasterlash guruhlarini tanlash shart emas
• Markazlar zichlikka ko`ra tanlanadi

Kamchiliklari:

• Nazorat radiusi juda katta bo`lishi mumkin

DBSCAN

Afzallik va kamchiliklari

• Afzalliklari:
• Bir necha klaster guruhlarini tanlash shart emas
• Hisoblashda chegara va shovqinlarni hisobga oladi
• Noodatiy shakldagi klasterlarni oson aniqlaydi

Kamchiliklari:

• Klasterlar zichligi turlicha bo`lgan holatda yomon ishlaydi

EMcGMM klasterlash algoritmi

Afzallik va kamchililari

• Afzalliklari:
• Yagona markazga ega bo`lgan turli xil klasterlarni payqay oladi
• Vaqt murakkabligi: O(n)

Kamchiligi:

• Bir nechta klasterlarni tanlab oladi

Ierarxik klasterlash

• Agglomerativ (pastdan-yuqoriga)
• Diviziv (yuqoridan-pastga) (DIANA)
• Yagona bog’lamli klasterlash
• Umumiy bog’lamli klasterlash
• O’rtacha bog’lamli klasterlash
• Vaqt murakkabligi

Ierarxik agglomerative klasterlash (HAC)

Yagona bog’lamli klasterlash

• Klasterlarni pastdan-yuqoriga tomon guruhlashga asoslangan, har qadamda bir-biriga eng yaqin masofada joylashgan klasterlar elementlari ustida amal bajariladi

Umumiy bog’lamli klasterlash

• Jarayon boshida har bir elementni alohida klaster deb faraz qilinadi. Keyin eng yaqin masofada joy;ashgan klasterlar juftliklari birlashtiriladi

O’rtacha bog’lamli klasterlash

• Algoritmning har qadamida eng yaqin masofadagi klasterlar birlashtiriladi

E’tiboringiz uchun rahmat!