deyarli bir vaqtning o'zida Styuart Lloyd tomonidan nashr etilgan. Asosiy g'oya
shundan iboratki, har bir takrorlanishda massa markazi oldingi bosqichda olingan
har bir klaster uchun qayta hisoblab chiqiladi, so'ngra vektorlar yana yangi
markazlarning qaysi biri tanlangan metrikaga yaqin bo'lishiga qarab yana
klasterlarga bo'linadi.
Nazorat qilinmaydigan k-vositalari algoritmi k-ga eng yaqin qo'shni
klassifikatori
bilan yaxshi aloqaga ega, bu nom tufayli k-vositalar bilan tez-tez
aralashib ketadigan, tasniflash uchun mashhur nazorat ostida mashinalarni
o'rganish texnikasi. K-vositalari yordamida olingan klaster markazlariga 1 ta eng
yaqin qo'shni klassifikatorini qo'llash yangi ma'lumotlarni mavjud klasterlarga
ajratadi. Bu eng yaqin santroid klassifikatori yoki Rocchio algoritmi sifatida
tanilgan.
Standart algoritm k-means
Eng keng tarqalgan algoritmda takroriy
takomillashtirish texnikasi
qo'llaniladi. Hamma joyda mavjud bo'lganligi sababli, ko'pincha "
k-vositalari
algoritmi" deb nomlanadi; u Lloyd algoritmi deb ham ataladi, ayniqsa kompyuter
fanlari hamjamiyatida. Ba'zan uni "sodda k-vositalar" deb ham atashadi, chunki bu
erda tezroq alternativalar mavjud.
Tez-tez ishlatiladigan boshlang'ich usullari Forgy va Random Partition.
Forgy usuli tasodifiy ma'lumotlar to'plamidan k ta kuzatuvlarni tanlaydi va ularni
dastlabki vosita sifatida ishlatadi. Tasodifiy bo'lim birinchi navbatda tasodifiy
ravishda har bir kuzatuvga klasterni tayinlaydi, so'ngra yangilash bosqichiga o'tadi
va shu bilan boshlang'ich o'rtacha hisoblab, klasterning tasodifiy tayinlangan
nuqtalari markazida bo'ladi. Forgy usuli dastlabki vositalarni tarqatishga intiladi,
Random Partition esa ularning hammasini ma'lumotlar to'plamining markaziga
yaqinlashtiradi. Hamerli va boshqalarning fikriga ko'ra tasodifiy bo'linish usuli
odatda k-harmonik vositalar va loyqa k-vositalar
kabi algoritmlar uchun
afzalroqdir. Kutishni maksimal darajaga ko'tarish va standart k-algoritmlari uchun
"Forgy" ishga tushirish usuli afzalroqdir. Celebi va boshqalarning tomonidan
o'tkazilgan keng qamrovli tadqiqoti shuni ko'rsatdiki, Forgy, Random Partition va
Maximin kabi ommalashtirish usullari tez-tez yomon ishlaydi, Bredli va
Fayyodning yondashuvi "eng yaxshi guruh" da "izchil" ishlaydi. va k-vositalari ++
"umuman yaxshi" ishlaydi.
K-vositalari algoritmi amalga oshirishning oson usulini quydagicha bo’lishi
mumkin. Ommaboplikning sabablari k-vositalarining oson va soddaligi,
ko'lamliligi, yaqinlashish tezligi va siyraklikka moslashuvchanligi ma'lumotlar.
K-o'rtacha algoritmini gradient tushish deb hisoblash mumkin. Klasterli
tsentroidlarni boshlashdan boshlanadigan protsedura va maqsadni kamaytirish
uchun ushbu sentroidlarni takroriy ravishda yangilaydi qismdagi funktsiya. K-
vositalari har doim mahalliyga yaqinlashadi eng kam. Topilgan ma'lum mahalliy
minimum quyidagiga bog'liq boshlang'ich klasterlar. Globalni topish muammosi
minimal NP bilan to'ldirilgan. Algoritm k-vositalari yangilanadi mahalliy minimal
darajaga qadar klasterli tsentroidlar. 1-rasmda ko'rsatilgan k-vositalari
algoritmining umumlashtirilgan psevdokodlari; va an'anaviyk-degan ma'noni
anglatadi algoritmi shakl.
K-algoritmi yaqinlashguncha masofa hisob-kitoblar bir qator bajarilayotganda
amalga oshiriladi oxirgi marta, l qiymatini ayting, bu erda l musbat butun son
sifatida tanilgan k-takrorlashlar soni. L ning aniq qiymati o'zgaradi boshlang'ich
boshlang'ich klasteriga qarab ham bir xil ma'lumotlar to'plami. Shunday qilib. Ning
hisoblash vaqtining murakkabligi algoritmi O (nkl), bu erda n - ob'ektlarning
umumiy soni ma'lumotlar to'plami, k - biz aniqlagan klasterlarning kerakli soni va l
- takrorlash soni Eng taniqli va mashhur klasterlash algoritmi:
Taxminiy dastlabki klaster markazlari tanlaymiz.
Iteratsiya:
Har bir misolni eng yaqin markazga belgilang / klasterlang
Klasterdagi nuqtalarning o'rtacha qiymati sifatida markazlarni qayta hisoblang
K-means: Misol:
1-rasm.K-means: Markazlarni tasodifiy ravishda tanlash
2-rasm. K-means: markazga eng yaqinligi bo’yicha guruhlash
3-rasm. K-means: markazlarni qayta sozlash
9-rasm. K-means: Markazlarni aniqlash
10-rasm. K-means: Markazdan eng uzoq nuqtani aniqlash
K-vositalarni klasterlash usuli bu ma'lumotlar to'plamidagi ma'lumotlar
ob'ektlarining klasterlarini aniqlash uchun foydalaniladigan nazoratsiz mashinani
o'rganish texnikasi. Klasterlash usullarining xilma-xil turlari mavjud, ammo k-
vositalari eng qadimgi va eng qulay usullardan biridir.
Ushbu xususiyatlar, hatto
boshlang'ich dasturchilar va ma'lumot olimlari uchun ham Python-da k-vositalarini
klasterlashni amalga oshirishga imkon beradi.
11-rasm. K-means: Markazlarni aniqlash
Agar siz Python-da k-vositalari klasterini qanday va qachon amalga oshirishni
bilishni xohlasangiz, unda bu to'g'ri joy. Biz Python yordamida k-vositalari
klasterining oxiridan oxirigacha, ma'lumotlarni oldindan qayta ishlashdan
natijalarni baholashgacha yuritamiz.
Agar yangi hosil bo'lgan klasterlarning sentroidlari o'zgarmasa, algoritmni
to'xtatishimiz mumkin. Bir necha marta
takrorlangandan keyin ham, agar biz
barcha klasterlar uchun bir xil sentroidlarni olsak, algoritm hech qanday yangi
namunani o'rganmayapti va bu mashg'ulotni to'xtatish belgisidir.
Agar takrorlash algoritmini o'rgatgandan keyin ham ballar bir xil klasterda
qolsa, biz mashg'ulot jarayonini to'xtatishimiz kerak bo'lgan yana bir aniq belgi.
Va nihoyat, takroriy takrorlashning maksimal soniga erishilsa, mashg'ulotni
to'xtatishimiz mumkin. Deylik, agar biz takrorlanishlar sonini 100 deb belgilagan
bo'lsak. Jarayon to'xtashdan oldin 100 marta takrorlanadi.
Dostları ilə paylaş: