Zichlikka asoslangan klasterlash algoritmlari

|
Zichlikka asoslangan klasterlash algoritmlari
|
bet | 5/7 | Sana | 14.05.2024 | Hajmi | 386,96 Kb. | | #232960 |
Zichlikka asoslangan klasterlash algoritmlari
Zichlikka asoslangan klasterlash misol zichligi yuqori bo'lgan hududlarni klasterlarga bog'laydi. Bu zich hududlar ulangan ekan, ixtiyoriy shakl taqsimotiga imkon beradi. Yuqori o'lchamli ma'lumotlar va turli zichlikdagi ma'lumotlar bilan bu algoritmlar muammolarga duch keladi. Dizayni bo'yicha, bu algoritmlar klasterlarga o'zgarib turadigan qiymatlarni belgilamaydi.
DBSCAN
Zichlikka asoslangan eng mashhur usul bu shovqinli ilovalarni zichlikka asoslangan fazoviy klasterlash (DBSCAN). Unda "zichlikka erishish imkoniyati" deb nomlangan aniq belgilangan klaster modeli mavjud.
Klasterlashning ushbu turi ma'lum bir zichlik mezonlarini (radiusdagi ob'ektlarning minimal soni) qondiradigan ma'lumotlar nuqtalarini bog'laydi. DBSCAN klasterlash tugallangandan so'ng, uchta turdagi nuqtalar mavjud: yadro, chegara va shovqin.
Agar siz yuqoridagi rasmga qarasangiz, yadro o'zidan ma'lum (n) masofada ba'zi (m) nuqtalarga ega bo'lgan nuqtadir. Chegara n masofada kamida bitta asosiy nuqtaga ega bo'lgan nuqtadir.
Shovqin - bu chegara ham, yadro ham bo'lmagan nuqta. Klasterlarni ajratish uchun zarur bo'lgan siyrak hududlardagi ma'lumotlar nuqtalari shovqin va kengroq nuqtalar hisoblanadi.
DBSCAN klasterlar qanday aniqlanganligini aniqlash uchun ikkita parametrdan foydalanadi:
minPts: mintaqani zich deb hisoblash uchun minimal ballar soni `minPts`bo'lishi kerak .
eps: istalgan nuqtalar yaqinidagi ma'lumotlar nuqtalarini aniqlash uchun `eps (e)` masofa o'lchovi sifatida ishlatiladi.
Mana DBSCAN algoritmining bosqichma-bosqich tushuntirishi:
DBSCAN tasodifiy ma'lumotlar nuqtasi (tashrif buyurilmagan nuqtalar) bilan boshlanadi.
Bu nuqtaning qo'shnisi epsilon e masofasidan foydalanib chiqariladi.
Klasterlash protsedurasi, agar ushbu hududda etarli ma'lumot nuqtalari mavjud bo'lsa va joriy ma'lumotlar nuqtasi eng yangi klasterdagi birinchi nuqtaga aylansa yoki nuqta shovqin sifatida belgilangan va tashrif buyurilgan bo'lsa boshlanadi.
Uning epsilon e masofali qo'shnisidagi nuqta ham yangi klasterning birinchi nuqtasi uchun bir xil klasterning bir qismiga aylanadi. Yuqoridagi klasterga qo'shilgan barcha yangi ma'lumotlar nuqtalari uchun barcha ma'lumotlar nuqtalarini bir xil klasterga tegishli qilish tartibi takrorlanadi.
Yuqoridagi ikki bosqich klasterdagi barcha nuqtalar aniqlanmaguncha takrorlanadi. Klasterning mahallasidagi barcha nuqtalarga tashrif buyurilgan va etiketlangan. Joriy klaster bilan ishlashni tugatganimizdan so'ng, yangi ko'rilmagan nuqta olinadi va qayta ishlanadi, bu esa klaster yoki shovqinni yanada aniqlashga olib keladi. Barcha ma'lumotlar nuqtalari tashrif buyurilgan deb belgilanmaguncha protsedura takrorlanadi.
DBSCAN ning hayajonli xususiyati uning past murakkabligidir. Bu ma'lumotlar bazasida chiziqli qator so'rovlarni talab qiladi.
DBSCAN bilan bog'liq asosiy muammo:
U klaster chegaralarini aniqlash uchun qandaydir zichlik pasayishini kutadi. DBSCAN yuqori misol zichligi hududlarini bog'laydi. G'alati shakldagi ma'lumotlarga kelsak, algoritm K-Means-dan yaxshiroqdir.
DBSCAN algoritmi haqida ajoyib narsa:
Bu oldindan belgilangan klasterlar sonini talab qilmaydi. Shuningdek, u shovqin va chegaralarni aniqlaydi. Bundan tashqari, o'zboshimchalik bilan o'lchamdagi va shakllangan klasterlar algoritm tomonidan juda yaxshi topilgan.
from numpy import where
from numpy import unique
from sklearn.datasets import make_classification
from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plot
# Initialize data
train_data, _ = make_classification(n_samples=1000,
n_features=2,
n_informative=2,
n_redundant=0,
n_clusters_per_class=1,
random_state=4)
# Define model
dbscan_model = DBSCAN(eps=0.25, min_samples=9)
# Train the model
dbscan_model.fit(train_data)
# Assign each data point to a cluster
dbscan_res = dbscan_model.fit_predict(train_data)
# obtain all the unique clusters
dbscan_clstrs = unique(dbscan_res)
# Plot the DBSCAN clusters
for dbscan_clstr in dbscan_clstrs:
# Obtain data point that belong in this cluster
index = where(dbscan_res == dbscan_clstr)
# plot
plot.scatter(train_data[index, 0], train_data[index, 1])
# show plot
plot.show()
Tarqatishga asoslangan klasterlash algoritmlari
Statistikaga chambarchas bog'liq bo'lgan klasterlash modeli tarqatish modellariga asoslanadi. Keyin klasterlar bir xil taqsimotga tegishli ob'ektlar sifatida belgilanishi mumkin. Ushbu yondashuv taqsimotdan tasodifiy ob'ektlarni tanlab olish yo'li bilan sun'iy ma'lumotlar to'plami qanday yaratilganiga juda o'xshaydi.
Ushbu usullarning nazariy jihatlari juda yaxshi bo'lsa-da, bu modellar haddan tashqari moslashishdan aziyat chekmoqda .
Gauss aralashmasi modeli
Gauss aralashmasi modeli (GMM) taqsimotga asoslangan klasterlash turlaridan biridir. Ushbu klasterlash yondashuvlari ma'lumotlar Gauss taqsimoti kabi taqsimotlardan iborat deb taxmin qiladi. Quyidagi rasmda taqsimotga asoslangan algoritm ma'lumotlarni uchta Gauss taqsimotiga to'playdi . Tarqatishdan masofa oshgani sayin, nuqtaning taqsimotga tegishli bo'lish ehtimoli kamayadi.
GMM K-Means bilan bir xil tarzda klasterlarni topish uchun ishlatilishi mumkin. Nuqtaning tarqatish markaziga tegishli bo'lish ehtimoli tarqatish markazidan masofa oshgani sayin kamayadi. Bantlar quyidagi rasmda ehtimollikning pasayishini ko'rsatadi. GMM kaput ostida ehtimoliy modelni o'z ichiga olganligi sababli, biz ehtimollik klaster tayinlanishini ham topishimiz mumkin. Agar siz ma'lumotlarning tarqatish turini bilmasangiz, boshqa algoritmdan foydalanishingiz kerak.
Keling, GMM ehtimolliklarni qanday hisoblashini va uni ma'lumotlar nuqtasiga belgilashini ko'rib chiqaylik:
GM - har biri k ∈ {1,…, K} bilan identifikatsiya qilingan bir nechta Gausslardan tashkil topgan funksiya, bu erda K - klasterlar soni. Aralashmadagi har bir Gauss K quyidagi parametrlardan iborat:
Uning markazini belgilaydigan o'rtacha m.
Uning kengligini aniqlaydigan S kovariatsiyasi.
Gauss funktsiyasi qanchalik katta yoki kichik yoki katta bo'lishini belgilaydigan aralashtirish ehtimoli.
Ushbu parametrlarni quyidagi rasmda ko'rish mumkin:
Klasterlarning kovariantligi, o'rtacha, dispersiya va og'irliklarini topish uchun GMM Expectation Maximization texnikasidan foydalanadi.
O'rtacha va kovariatsiya qiymatlari m1, m2, .. mk va S1, S2, .. Sk bo'lgan K Gauss taqsimotini anglatuvchi K klasterlar sonini belgilashimiz kerakligini ko'rib chiqaylik. Tarqatish zichligini ifodalovchi yana bir parametr Ii mavjud.
Gauss taqsimotini aniqlash uchun biz ushbu parametrlar uchun qiymatlarni topishimiz kerak. Biz allaqachon klasterlar sonini belgilab oldik va o'rtacha, kovariatsiya va zichlik uchun qiymat berdik. Keyingi bosqichlar Kutish bosqichi va Maksimallashtirish bosqichi bo'lib, ularni ushbu postda ko'rib chiqishingiz mumkin.
|
| |