60-yillar oxiri, 70-yillar boshiga to’g’ri keladi

Noierarxik algoritmlar
Klasterizatsiya masalasini yechishda masalaning ma’nosidan kelib chiqqan holda bo’linish hosil qiluvchi algoritmlardan foydalaniladi. Berilgan algoritmlar ma’lumotlarni shunday guruhlashga harakat qiladiki, bo’lish algoritmining maqsad funksiyasi ekstremumga (minimumga) erishsin.
Klasterizatsiyaning bo’lishlar usuliga asoslangan uchta asosiy algoritmini qaraymiz. Berilgan algoritmlarni tahlil qilishda quyidagi bazaviy tushunchalardan foydalanamiz.

• 
  M o’rganilayotgan bo’linishlar to’plami;
  
• 
  Quyidagi formula masofa matritsasi formulasi deyiladi:
  

(4)
bu yerda A matritsa – masofani hisoblash usulini aniqlaydi. Masalan, birlik matritsa bo’yicha Evklad masofasidan foydalanish.

• 
  C – klasterlar markazlari vektori;
  
• 
  U – klasterizatsiya bo’yicha bo’linish matritsasi;
  
• 
  – maqsad funksiyasi;
  
• 
  Chegaralanishlar majmuasi.
  

k – means algoritmi (K-means). Yaxshiroq ko’rish uchun ikkita parameter – kosacha bargning uzunligi va kengligi bilan chegaralanamiz. Bu ma’lumotni ikki o’lchamli fazoda ifodalashga imkon beradi. Nuqtalar ob’ektlar nomeri bilan belgilangan. Dastlab, barcha ob’ektlar fazosidagi nuqtalar markazlardan ixtiyoriy k boshlang’ich nuqtalar olinadi. Bu markazlarni bo’lish usuli muhim emas, boshlang’ich nuqtalarni tanlash hisoblash vaqtida namoyon bo’ladi. Masalan, I to’plamdagi dastlabki k ta ob’ekt bo’linishi mumkin. Berilgan misolda bu nuqta 1, 2 va 3. Ikkinchi qadamda jarayon iteratsion bajariladi.