Klasterlew mashqalası

Algoritmlerdi ajıratıw. Aglomerativlardan ayrıqsha bolıp esaplanıw, bóliniwshi klaster algoritmleri birinshi basqıshta barlıq elementler kompleksin I birden-bir klaster retinde ańlatıladı. Algoritmnıń hár bir basqıshında ámeldegi klasterlerden biri rekursiv túrde eki kishi klasterge bólinedi. Sonday etip, klasterler joqarıdan tómenge shekem iterativ tárizde qáliplesedi. Bunday jantasıw klaster analizi ádebiyatında aglomerativ algoritmler sıyaqlı keń xarakteristikalanbaǵan. Ol barlıq obyektler kompleksin salıstırǵanda kem sanlı klasterlerge bolıw zárúr bolǵanda qollanıladı.
Birinshi bóliniwshi algoritmlardan biri 1965 jılda Smit MakNaughton tárepinen usınıs etilgen. Birinshi basqıshta barlıq elementler bir klasterge C₁=I jaylastırılǵan. Keyin element bul klasterdegi basqa elementlerden eń úlken ortasha aralıq penen saylanadı. Ortashanı, mısalı, tómendegi formula járdeminde esaplaw múmkin:

Tańlanǵan aǵza klasterden óshiriledi hám ekinshi klasterdiń birinchi aǵzasın payda etedi.

Hár bir keyingi basqıshta klasterdegi element , bunıń  ushın ishinde jaylasqan elementlerge shekem  bolǵan ortasha aralıq hám ishinde qalǵan elementlerge shekem bolǵan ortasha aralıq ortasındaǵı parıq eń úlken bolǵan element ge otkiziledi.
1990 jılda Kaufman hám Roseuve hár bir dárejedegi eń úlken diametrli bóliniw ushın klasterdi tańlawdı usınıs etken hám ol tómendegi formula arqalı esaplanadı:

Klasterlerdiń rekursiv bóliniwi barlıq klasterler sigleton bolǵanǵa shekem (yaǵnıy, bir obyektten ibarat) yamasa birdey klasterdiń barlıq aǵzaları bir-birinen nol menen parıq etkenshe dawam etedi.
Ierarxiyalıq bolmaǵan algoritmler.
Maǵlıwmatlar kompleksin málim bir mániste klasterlerge (gruppalarǵa) boliwdiń maqul túsetuǵının tabıwǵa tiykarlanǵan algoritmler, klasterlew máselelerin sheshiwde júdá kóp qollanılıp kelmekte. Kóplegen máselelerde, olardıń abzallıqları sebepli, bólimdi qurıw algoritmleri qollanıladı. Bul algoritmler maǵlıwmatlardı (klasterlerge) sonday gruppalawǵa háreket etedi, bunda bóliniw algoritmınıń maqset funkciyası ekstremal (minimal)ǵa jetedi. Bóliw usıllarına tiykarlanǵan úsh tiykarǵı klasterlew algoritmın kórip shıǵayıq. Bul algoritmler tómendegi tiykarǵı túsiniklerden paydalanadı :

• 
  Bóliwge mólsherlengen oqıw kompleksi (kiriwshi maǵlıwmatlar kompleksi) M;
  
• 
  aralıq kórsetkishi:
  

Bul jerde matrica aralıq qanday esaplanǵanlıǵın anıqlaydı. Mısalı, identifikaciya matricası ushın biz Evklid aralıǵınan paydalanamız; 

• 
  klaster orayları vektorı C ;
  
• 
  klaster bólimleri matricası  U;
  
• 
  maqsetli funkciya
  
• 
  sheklewler toplamı.
  

Úyrenilip atırǵan maǵlıwmatlar kóp ólshewli keńisliktegi vektorlar kompleksi retinde usınıs etiledi, olar obyekt tarawınıń bazıbir obyektlerin xarakteristikalaydı. Hár bir vektor atributlar dep atalatuǵın koordinatalar kompleksinen ibarat. Hár bir atributtıń ayriqsha ózgesheligi (cifrlı yamasa taypalı) hám ayriqsha mánisler kompleksi bar. Atributtıń cifrlı ózgesheligine iye bolǵan mánisler kompleksi cifrlı kósherdiń bir yamasa bir neshe intervalları formasında kórsetilgen. Atributtıń taypalı tábiyatı bolsa, mánisler kompleksi múmkin bolǵan mánislerin sanap ótiw arqalı belgilenedi. Klasterlew ushın maǵlıwmatlardı tayarlawda maǵlıwmatlardı tazalaw hám normallastırıw úlken áhmiyetke iye. Maǵlıwmatlardı tazalaw bir pútkil retinde kiriw kompleksi ushın da, atributlar kompleksi ushın da ámelge asıriladı. Bir neshe atributlar ushın maǵlıwmatlardı tazalawǵa baylanıslı atributlardı esaptan tısqarı etiw ushın zárúr, bul nátiyjege tásir etpeydi, lekin maǵlıwmatlardı qayta islew ushın zárúr bolǵan waqıttı asıradı. Klasterlew nátiyjelerine individual atributlar mánislerinıń túrli diapazonları tásir etpewi ushın normalizaciyalaw zárúr. Sonıń menen birge, cifrlı hám taypalı atributlar basqasha tárizde normallastırıladı. Nátiyjede, hár bir atribut birlik aralıǵindaǵı mánis arqalı ańlatıladı.
Aralıq kórsetkishi, klasterlewde isletiletuǵın eń zárúrli túsinik bolıp tabıladı. Kiriw vektorları arasındaǵı aralıq járdeminde olardıń uqsaslıǵı yamasa parqı anıqlanadı. Aralıqtı esaplawdıń kóplegen usılları bar: Evklid, Hamming, Mezgilanobis aralıǵı hám basqalar. Aralıqtı esaplaw usılın tańlaw úyrenilip atırǵan obyektlerdiń tábiyatına baylanıslı hám nátiyjege tikkeley tásir etedi.
Maqsetli funkciya - bul minimallastırıw klasterlew máselesine sheshim beretuǵın funkciya. Maqset funkciyasınıń minimalın izlewdi ámelge asırıwshı háreketler izbe-izligi klasterlew algoritmı bolıp tabıladı.
Bólim matricası ierarxiyalıq bolmaǵan klasterlewdiń tiykarǵı nátiyjesi bolıp tabıladı. Bólim matricası - bul keste bolıp, hár bir ketek málim bir vektordıń málim klasterge aǵzalıq funkciyası mánisin óz ishine aladı. Bul matricaǵa tıykarlanıp, juwmaqlawshı bólim alınadı. Kóplegen algoritmlarda aǵzalıq matricasınan tısqarı, nátiyjede klaster orayları kompleksi payda boladı. Klaster orayı bul berilgen klasterge tiyislilik dárejesi maksimal bolǵan vektor bolıp tabıladı. Sheklewler kompleksi aǵzalıq matricası elementleriniń mánislerine qoyılǵan shártler menen baylanıslı. Bul shegaralar klasterlew ushın isletiletuǵın algoritm menen belgilenedi.
Ierarxiyalıq bolmaǵan algoritmlarǵa k-means (Hard-c-means) algoritmı, Fuzzy Ñ-Means algoritmı hám anıq bolmaǵan klasterlew algoritmı kiredi. 
Juwmaq
• Klasterlewdiń wazıypası úyrenilip atırǵan obyektler kompleksin klasterler dep atalatuǵın uqsas obyektler gruppalarına bóliw bolıp esaplanadı.
• Obyektlerdiń "uqsaslıǵın" anıqlaw ushın aralıq dep atalatuǵın jaqınlıq ólshewi kiritiledi. Aralıqlardı esaplawdıń túrli usılları bar: Evklid, Manxetten, Chebishev hám basqalar.
• Klasterlew nátiyjeleri túrli jollar menen usınıs etiliwi múmkin. Eń kóp qollanılatuǵınlarınıń biri dendrogramma - izbe-iz klasterlew procesiniń kórinisi.
• Klasterlewdiń tiykarǵı usılları ierarxiyalıq hám ierarxiyalıq bolmaǵanlarǵa bólinedi. Birinshisi dendrogrammalardı tómennen joqarıǵa (aglomerativ) yamasa joqarıdan tómenge (bóliniwshi) qarap dúziwi múmkin.
• Ierarxiyalıq bolmaǵan algoritmlerden eń kóp qollanıltuǵını k -means algoritmı jáne onıń variantları bolıp tabıladı. Usıldıń ideyası k klasterlerdiń orayların anıqlaw hám hár bir klasterge bul oraylarǵa qońsılas obyektlerdi belgilew bolıp tabıladı.
• Maslasıwshı klasterlewden paydalanıw klasterlew mashqalasın jáne de nátiyjeli sheshiwge hám nátiyjeni bahalawǵa jáne de teń salmaqlı jantasıwǵa járdem beredi. Soǵan qaramay, sapanı bahalaw kriteryaın tańlaw mashqalasın sheshiw ushın zárúr bolıwı múmkin.