Dasturiy injiniring” kafedrasi s. N. Iskandarova ma’lumotlarga dastlabki ishlov berish fanidan

Klaster algoritmlarida qo'llaniladigan masofaga asoslangan yaqinlik o'lchovlari

Ob'ektlar orasidagi masofalar ularning nuqta shaklida ifodalanishini nazarda tutadi  - o'lchovli bo'shliq  . Bunday holda, masofalarni hisoblashda turli xil yondashuvlardan foydalanish mumkin.
Quyida ko'rib chiqilgan chora-tadbirlar kirish o'zgaruvchilari maydoniga tegishli ikkita nuqta orasidagi masofani aniqlaydi. Quyidagi konventsiyalardan foydalaniladi:

1. 
   -m - o'lchovli real fazoning kichik to'plami bo'lgan ma'lumotlar to'plami;
   
2. 
   - ma'lumotlar to'plamining elementlari;
   
3. 
   - ma'lumotlar nuqtalarining o'rtacha qiymati;
   
4. 
   - kovariatsiya matritsasi  .
   

Yaqinlikning eng mashhur o'lchovlari.
Evklid fazosi. Ba'zan siz bir-biridan uzoqroq bo'lgan ob'ektlarga kattaroq og'irlik berish uchun standart Evklid masofasini kvadratga olishni xohlashingiz mumkin. Bu masofa quyidagicha hisoblanadi:
(4.1)
Hemming bo'ylab masofa . Bu masofa shunchaki koordinatalar farqlarining o'rtacha ko'rsatkichidir. Ko'pgina hollarda, bu masofa o'lchovi odatdagi Evklid masofasi bilan bir xil natijalarga olib keladi, lekin buning uchun alohida katta farqlarning (chetlarning) ta'siri kamayadi (chunki ular kvadrat emas). Hamming masofasi quyidagi formula bo'yicha hisoblanadi:
(4.2)
Chebychev masofasi. Ikki ob'ektni har qanday koordinatada (har qanday o'lchamda) farq qiladigan bo'lsa, "boshqa" deb belgilashni istasangiz, bu masofa foydali bo'lishi mumkin. Chebishev masofasi quyidagi formula bo'yicha hisoblanadi:
(4.3)
Mahalanobis masofasi bu kamchilikni bartaraf etadi, ammo agar kovariatsiya matritsasi kiritilgan ma'lumotlarning butun to'plami bo'yicha hisoblansa, bu masofa o'lchovi yaxshi ishlamaydi. Shu bilan birga, ma'lum bir sinfga (ma'lumotlar guruhi) qaratilgan bo'lib, bu masofa o'lchovi yaxshi natijalarni ko'rsatadi:
(4.4)
Peak masofa tasodifiy o'zgaruvchilar orasidagi mustaqillikni nazarda tutadi, bu ortogonal bo'shliqdagi masofani ko'rsatadi. Ammo amaliy ilovalarda bu o'zgaruvchilar mustaqil emas: 
(4.5)
Berilgan masofaviy o'lchovlardan har qandayini ishonch bilan tanlash mumkin, agar klasterlangan ma'lumotlarning tabiati haqida ma'lumot mavjud bo'lsa. Masalan, eng yuqori masofa tasodifiy o'zgaruvchilar orasidagi mustaqillikni nazarda tutadi, bu ortogonal fazodagi masofani ko'rsatadi. Ammo amaliy dasturlarda bu o'zgaruvchilar mustaqil emas.