Ma’ruza №2 Mavzu: Data Mining usullari va rivojlanish bosqichlari Reja: 1

k-o’rtachalar usuli. Ma’lumotlarni mos elementlari soni k teng bo’lgan guruhlarga birlashadi. k-o’rtachalar usuli quyidagi tarzda klasterizatsiyani amalga oshiradi.

1. 
   Ma’lumotlar ajratilishi kerak bo’lgan guruhlar soni (k) belgilanadi. Tasodifiy tazda klasterlarni dastlabki markazi sifatida joriy to’plam k obyektlar tanlanadi (sentroidlar).
   
2. 
   Eng yaqin sentroid bo’yicha ma’lum guruhlarga taalluqli, ya’ni ular orasidagi masofani minimallashtirishni asosiy me’zonlari (odatda Evklid masofa foydalaniladi).
   
3. 
   Barcha klasterlar sentroidlarni koordnitalari sanab o’tiladi (odatda o’rtacha qiymat kabi hisoblanadi) va guruh ichidagi tarqlishlar hisoblanadi (within-cluster variation).
   
4. 
   Umumiy ichkaridagi tarqalishlarni minimallashtiriladi, bunda 2 va 3-qadamlar obyektlar guruhlarga taqsimlanmaguncha yoki berilgan iteratsiya soniga yetilmaguncha ko’p marta qaytariladi.
   

k-o’rtachalar usuli juda sodda va samarali algoritm bo’lishigaq aramasdan ikkita sezilarli muammoga ega. Birinchidan, oxirgi natijalar guruh markazlarini boshlang’ich tasodifiy tanloviga sezilarli. Bu muammoning yechimi boshlang’ich sentroidlarni turlicha tasodifiy tarzda belgilash va natijalarni taqqoslash bilan algoritmni ko’p marta bajarilishidan iborat. Ikkinchi muammo – ajratish uchun k klasterlarni aniq sonini berish zaruratidadir. k sonini optimal tanlovi “tirsak” usulidan foydalanish yoki Monte-Karlo imitatsion modeli asosida generatsiyalanadigan ajratish statistikasi (gap statistic) yordamida imkonlidir.
2.3-jadval
O’qituvchisiz o’qitish algoritmlari

O’zgaruvchilar	Qiymatlar yoki natijalar toifasi	k-o`rtachalar usuli bilan klasterizatsiya	Asosiy kompnentalar usuli	Birlashma qoidalari	Luvenskiy usuli	PageRank
Kirish	Binar qiymatlar
	Uzluksiz qiymatlar
	Uzellar va uchlar
Chiqish	Kategoriyalar
	Birlashmalar|(aloqalar)
	Ranglar

Asosiy komponentalar usuli. Tahlil uchun o’zgaruvchilar qiymati asosiy komponentalar deb nomlanuvchi yangi komponentalarga ulardan eng axboriylarini kombinatsiyalash yo’li bilan pasaytiriladi. Asosiy komponentalar joriy ta’sir belgilarini har biri ba’zi chiziqli kombinatsiyasi kabi olingan belgilar orasida korrelaytsiyalanmaydigan yangi to’plam hisoblanadi.

[9] ishda asosiy komponentalarni ajratish joriy belgili muhitni sezilarli buzilishiga olib kelishi mumkin, bu esa yangi belgilar muhitida obyektlar uchun ajralishni pasayishiga va singlashtirishni natijaviy miqdorini pasayishiga olib kelishi mumkin.
Birlashma qoidalar o’zaro bag’langan elementlar (hodisalar yoki obyektlar) orasida mantiqiy qonuniyatlarni topish mexanizmlaridir. Bu usul ma’lumotlar elementlari orasida birlashmalarni aniqlash imkonini beradi, masalan, birgalikda sotib olinayotgan tovarlar.
Birlashma qoidalar quyidagi ko’rinishga ega: agar qayerdadir mantiqy ifoda emas, balkim joriy qoidani o’z ichiga olgan obyektlar bilan bog’langan (birlashgan) obyektlar to’plami bo’lsa. Ko’rsatilgan ko’rinishdagi qoidalardan tashqari, bilvosita birlashma qoidalar, salbiy birlashma qoidalar, vaqt bilan bog’liq hodisalar uchun vaqtinchalik birlashma qoidalar va boshqalar mavjud.
Uchta odatiy birlashma o’lchovlar mavjud:

• 
  {X} qo’llab-quvvatlanishi, X qanchalik tez-tez paydo bo’lishini ko’rsatadi;
  
• 
  {X->Y} ishonchlilik Y X bo’lganda qanchalik tez-tez paydo bo’lishini ko’rsatadi;
  
• 
  {X->Y} lift X va Y ular alohida paydo bo’lishiga qaraganda qanchalik birgalikda paydo bo’lishini ko’rsatadi.
  

Birlashma qoidalar qidiruv algoritmi X va Y ni bog’lovchi barcha qoidalarni topish uchun mo’ljallangan, bunda bu qoidalarni qo’llab-quvvatlanishi va ishonchliligi oldindan aniqlangan ba’zi chegaralardan yuqori bo’lishi kerak. Birlashma qoidalar qidiruvi algoritmi trivial emas, muammolardan biri ma’lumot elementlari sonini oshishida hisoblash murakkabligi hisoblanadi.