Bajardi: Ochilov Raufjon Tekshirdi: Hamiyev A. T. Samarqand-2022 Mavzu: Klaster tahliliga kirish

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI

Kompyuter injiniring fakulteti 201-18 guruhi

Bioinformatika va biomexanika fanidan
MUSTAQIL ISH

Mavzu: Klaster tahlili


Bajardi: Ochilov Raufjon
Tekshirdi: Hamiyev A.T.

Samarqand-2022

Mavzu: Klaster tahlili
Klaster tahliliga kirish
Ijtimoiy-iqtisodiy hodisalarni tahlil qilish va prognoz qilishda tadqiqotchi ko'pincha ularning tavsifining ko'p qirrali bo'lishiga duch keladi. Bu bozorni segmentlarga ajratish muammosini hal qilishda, juda ko'p ko'rsatkichlarga asoslangan mamlakatlar tipologiyasini tuzishda, ayrim tovarlarga bozor sharoitlarini bashorat qilishda, iqtisodiy tushkunlikni va boshqa ko'plab muammolarni o'rganish va bashorat qilishda ro'y beradi.
Ko'p o'lchovli tahlil usullari ko'plab xususiyatlar bilan tavsiflangan ijtimoiy-iqtisodiy jarayonlarni o'rganishning eng samarali miqdoriy vositasidir. Bularga klasterli tahlil, taksonomiya, naqshni aniqlash, omillarni tahlil qilish kiradi.
Klaster tahlilida tasnifdagi ko'p o'zgaruvchan tahlilning xususiyatlari, omillarni tahlil qilish - muloqotni o'rganishda eng aniq aks ettirilgan.
Ba'zida klaster tahlilining yondashuvi adabiyotda raqamli taksonomiya, raqamli tasnif, o'z-o'zini o'rganishni tan olish va boshqalar deb ataladi.
Klaster tahlilining birinchi qo'llanilishi sotsiologiyada topilgan. Klaster nomini tahlil qilish inglizcha klaster so'zidan kelib chiqqan - to'da, klaster. Birinchi marta 1939 yilda klaster tahlilining predmeti tadqiqotchi Trion tomonidan aniqlangan va tasvirlangan. Klaster tahlilining asosiy maqsadi o'rganilayotgan ob'ektlar va xususiyatlar to'plamini tegishli ma'noda bir hil guruhlarga yoki klasterlarga bo'lishdir. Bu shuni anglatadiki, ma'lumotlarni tasniflash va undagi tegishli tuzilmani aniqlash vazifasi hal qilinmoqda. Klasterlarni tahlil qilish usullari har xil holatlarda qo'llanilishi mumkin, hatto oddiy guruhlashda ham, hamma narsa miqdoriy o'xshashlikka asoslangan guruhlarning shakllanishiga bog'liq.
Klaster tahlilining katta afzalligi shundaki, u ob'ektlarni bitta parametr bo'yicha emas, balki butun funktsiyalar to'plami bo'yicha ajratish imkonini beradi. Bundan tashqari, klasterli tahlil, aksariyat matematik va statistik usullardan farqli o'laroq, ko'rib chiqilayotgan ob'ektlar turiga hech qanday cheklovlar qo'ymaydi va deyarli ixtiyoriy xarakterdagi har xil dastlabki ma'lumotlarni ko'rib chiqishga imkon beradi. Bu, masalan, kon'yunkturani prognoz qilish uchun, ko'rsatkichlar xilma -xil shaklga ega bo'lsa, bu an'anaviy ekonometrik yondashuvlarni qo'llashni qiyinlashtiradi.
Klasterlarni tahlil qilish bizga juda katta hajmdagi ma'lumotlarni ko'rib chiqish va ijtimoiy-iqtisodiy ma'lumotlarning katta hajmini keskin qisqartirish, siqish, ularni ixcham va vizual qilish imkonini beradi.
Klasterlar tahlili iqtisodiy rivojlanishni tavsiflovchi vaqt qatorlari yig'indisiga (masalan, umumiy iqtisodiy va tovarlik holatiga) nisbatan katta ahamiyatga ega. Bu erda mos keladigan ko'rsatkichlarning qiymatlari etarlicha yaqin bo'lgan davrlarni ajratish, shuningdek, dinamikasi eng o'xshash bo'lgan vaqt qatorlari guruhlarini aniqlash mumkin.
Klaster tahlilini davriy ravishda ishlatish mumkin. Bunday holda, tadqiqot kerakli natijalarga erishilgunga qadar amalga oshiriladi. Bundan tashqari, bu erdagi har bir tsikl klaster tahlilini yanada qo'llash yo'nalishi va yondashuvlarini sezilarli darajada o'zgartirishi mumkin bo'lgan ma'lumotlarni taqdim etishi mumkin. Bu jarayon teskari aloqa tizimi bilan ifodalanishi mumkin.
Ijtimoiy-iqtisodiy prognozlash vazifalarida klaster tahlilini boshqasi bilan birlashtirish juda istiqbolli miqdoriy usullar(masalan, regressiya tahlili bilan).
Boshqa har qanday usul singari, klaster tahlilining ham ma'lum kamchiliklari va cheklovlari bor: Xususan, klasterlarning tarkibi va soni tanlangan bo'linish mezonlariga bog'liq. Dastlabki ma'lumotlar massivini ixchamroq shaklga tushirganda, ba'zi buzilishlar bo'lishi mumkin, shuningdek, ularni klaster parametrlarining umumlashtirilgan qiymatlari xususiyatlariga almashtirish orqali individual ob'ektlarning individual xususiyatlari yo'qolishi mumkin. Ob'ektlarni tasniflashda, ko'pincha ko'rib chiqilayotgan to'plamda klaster qiymatlari yo'qligi ehtimoli e'tiborga olinmaydi.
Klaster tahlilida quyidagilarga ishoniladi:
a) tanlangan xususiyatlar, asosan, klasterlarga kerakli bo'linishni tan oladi;
b) o'lchov birliklari (shkalasi) to'g'ri tanlangan.
O'lchov tanlovi o'ynaydi katta rol... Odatda, ma'lumotlar o'rtacha qiymatni chiqarib, standart og'ishlarga bo'linib, normallashtiriladi, shunda dispersiya bitta bo'ladi.
Klasterlarni tahlil qilish muammosi.

Klaster tahlilining vazifasi X to'plamidagi ma'lumotlarga asoslanib, G ob'ektlar to'plamini m (m - butun sonli) Q1, Q2, ..., Qm klasterlarga bo'lishdir. faqat bitta bo'limga tegishli va shuning uchun bitta klasterga tegishli ob'ektlar o'xshash, har xil klasterlarga tegishli ob'ektlar o'xshash emas.

Masalan, G ga n ta mamlakatni kiritsin, ularning har biri aholi jon boshiga YaIM (F1), har 1000 kishiga to'g'ri keladigan M avtomobillar soni (F2), aholi jon boshiga elektr energiyasi iste'moli (F3), po'lat iste'mol qilish (F4). , va boshqalar. Keyin X1 (o'lchov vektori) - bu birinchi mamlakat uchun ko'rsatilgan xususiyatlar to'plami, ikkinchisi uchun X2, uchinchi uchun X3 va boshqalar. Vazifa - mamlakatlarni rivojlanish darajasiga qarab ajratish.
Klasterlarni tahlil qilish muammosining echimi - bu optimallik mezoniga mos keladigan bo'limlar. Bu mezon ob'ektiv funktsiya deb ataladigan turli bo'limlar va guruhlarning maqsadga muvofiqlik darajasini ifodalovchi ma'lum funktsional bo'lishi mumkin. Masalan, burilish kvadratlarining guruh ichidagi yig'indisini ob'ektiv funktsiya sifatida qabul qilish mumkin:
bu erda xj - j -ob'ektning o'lchovlarini ifodalaydi.
Klaster tahlil masalasini hal qilish uchun o'xshashlik va heterojenlik tushunchasini aniqlash kerak.
Xi va Xj nuqtalari orasidagi masofa (masofa) etarlicha kichik bo'lganda, i-chi va j-chi ob'ektlar bitta klasterga tushishi va bu masofa etarlicha katta bo'lganida, har xil klasterlarga tushishi aniq. Shunday qilib, bir yoki turli xil ob'ektlar guruhiga tushish Epdan p-o'lchovli Evklid maydoni bo'lgan Xi va Xj orasidagi masofa tushunchasi bilan belgilanadi. Manfiy bo'lmagan d (Xi, Xj) funktsiya masofaviy funktsiya (metrik) deyiladi, agar:
a) d (Xi, Xj) ³ 0, Epdan barcha Xi va Xj uchun
b) d (Xi, Xj) = 0 agar va faqat Xi = Xj bo'lsa
c) d (Xi, Xj) = d (Xj, Xi)
d) d (Xi, Xj) £ d (Xi, Xk) + d (Xk, Xj), bu erda Xj; Xi va Xk - bu Epning har qanday uchta vektori.

Xi va Xj uchun d (Xi, Xj) qiymati Xi va Xj orasidagi masofa deb ataladi va tanlangan xususiyatlarga ko'ra (F1, F2, F3, ..., Fr) Gi va Gj orasidagi masofaga teng.

Eng ko'p ishlatiladigan masofaviy funktsiyalar:
1. Evklid masofasi d2 (Xi, Xj) =
2.l1 - norma d1 (Xi, Xj) =
3. Supremum - norma d ¥ (Xi, Xj) = sup
k = 1, 2, ..., p
4.lp - norma d (Xi, Xj) =
Evklid metrikasi eng mashhur hisoblanadi. L1 metrikasini hisoblash eng oson. Supremum-norma osongina hisoblab chiqiladi va buyurtma berish tartibini o'z ichiga oladi, lp-norma esa 1, 2, 3,.
X o'lchovlar X1, X2, ..., Xn p p o'lchamdagi ma'lumotlar matritsasi sifatida ifodalansin:
Keyin d (Xi, Xj) vektor juftlari orasidagi masofani nosimmetrik masofa matritsasi sifatida ko'rsatish mumkin:
Masofaga qarama -qarshi tushuncha Gi jismlari orasidagi o'xshashlik tushunchasidir. va Gj. S (Xi; Xj) = Sij manfiy bo'lmagan haqiqiy funktsiya o'xshashlik o'lchovi deb ataladi, agar:
1) 0 £ S (Xi, Xj)<1 для Хi¹ Хj
2) S (Xi, Xi) = 1
3) S (Xi, Xj) = S (Xj, Xi)
O'xshashlik o'lchovlari juftligini o'xshashlik matritsasiga birlashtirish mumkin:
Sij qiymati o'xshashlik koeffitsienti deb ataladi.
1.3. Klaster tahlil usullari.
Bugungi kunda klaster tahlilining ko'plab usullari mavjud. Keling, ulardan ba'zilari haqida to'xtalamiz (quyida keltirilgan usullar odatda minimal dispersiya usullari deb ataladi).
X kuzatuvlar matritsasi bo'lsin: X = (X1, X2, ..., Xu) va Xi va Xj o'rtasidagi Evklid masofasining kvadrati quyidagi formula bilan aniqlanadi:
1) To'liq ulanish usuli
Bu usulning mohiyati shundan iboratki, bitta guruhga (klasterga) tegishli ikkita ob'ekt ma'lum bir chegaraviy qiymatdan kam bo'lgan o'xshashlik koeffitsientiga ega. klasterning chegaraviy qiymati h dan oshmasligi kerak. Shunday qilib, h klasterni tashkil etuvchi kichik guruhning ruxsat etilgan maksimal diametrini belgilaydi.
2) Maksimal mahalliy masofa usuli.
Har bir ob'ekt bitta nuqta klasteri sifatida qaraladi. Ob'ektlar quyidagi qoida bo'yicha guruhlanadi: agar bitta klaster va boshqasining nuqtalari orasidagi maksimal masofa minimal bo'lsa, ikkita klaster birlashtiriladi. Protsedura n - 1 bosqichdan iborat bo'lib, natijada har qanday chegaraviy qiymatlar uchun oldingi usuldagi barcha mumkin bo'linmalarga to'g'ri keladigan bo'limlar paydo bo'ladi.
3) Word usuli.
Bu usulda, ob'ektiv funktsiya sifatida, har bir nuqta (ob'ekt) orasidagi masofalar va bu ob'ektni o'z ichiga olgan klasterdagi o'rtacha kvadratlar yig'indisidan boshqa narsa emas. Har bir bosqichda ikkita klaster birlashtirilib, ular maqsad funktsiyasining minimal o'sishiga olib keladi, ya'ni. guruhlararo kvadratlar yig'indisi. Bu usul bir -biriga yaqin joylashgan klasterlarni birlashtirishga qaratilgan.
4) Centroid usuli.
Ikki klaster orasidagi masofa bu klasterlarning markazlari (vositalari) orasidagi evklid masofasi sifatida belgilanadi:
d2 ij = (`X –`Y) T (` X –`Y) Klasterlash bosqichma -bosqich n - 1 bosqichda davom etadi, ikkita g va p klaster d2ij minimal qiymati bilan birlashtirilgan bo'lsa, n1 n2 dan katta bo'lsa, keyin ikkita klasterning birlashish markazlari bir -biriga yaqin joylashgan va klasterlar birlashtirilganda ikkinchi klasterning xususiyatlari amalda e'tiborga olinmaydi. Ba'zan bu usulni ba'zan og'irlikdagi guruh usuli deb ham atashadi.
1.4 Klasterlar ketma -ketligi algoritmi.
$ \ Phi = (\ phi1, \ phi2,… \ phn) $ ni (Ι1), (Ι2), ... (Ιn) klasterlar to'plami sifatida ko'rib chiqing. Keling, ulardan ikkitasini tanlaymiz, masalan, Ι i va Ι j, ular qaysidir ma'noda bir -biriga yaqinroq va ularni bir klasterga birlashtiradi. N-1 klasterlardan tashkil topgan yangi klasterlar to'plami quyidagicha bo'ladi:

(Ι1), (Ι2)…, (Ι i, Ι j),…, (Ιn).

Jarayonni takrorlab, biz (n-2), (n-3), (n-4) va boshqalardan iborat ketma-ket klasterlar to'plamini olamiz. klasterlar. Jarayon oxirida siz n ta ob'ektdan tashkil topgan va boshlang'ich Ι = (Ι1, Ι2,… Ιn) mos keladigan klasterni olishingiz mumkin.

Masofa o'lchovi sifatida biz evklid metrikasining di j2 kvadratini olamiz. va matrisani hisoblang D = (di j2), bu erda di j2 - orasidagi masofaning kvadrati

Ι1 Ι2 Ι3 …. N
Ι1 0 d122 d132 …. d1n2
Ι2 0 d232 …. d2n2
Ι3 0 …. d3n2
…. …. ….
N 0
Ι i va Ι j orasidagi masofa minimal bo'lsin:

di j2 = min (di j2, i ¹ j). Ι i va Ι j yordamida biz yangi klaster hosil qilamiz

(Ι i, Ι j). Keling, yangi ((n-1), (n-1)) masofali matritsani tuzaylik

(Ι i, Ι j) Ι1 Ι2 Ι3 …. N

(Ι i; Ι j) 0 j21 j22 j23 …. di j2n
Ι1 0 d122 d13 …. d12n
Ι2 0 j21 …. d2n
Ι3 0 …. d3n
N 0
(n-2) oxirgi matritsaning qatorlari oldingisidan olinadi va birinchi qator qayta hisoblab chiqiladi. Agar di j2k, k = 1, 2,…, n ifodalash mumkin bo'lsa, hisoblarni minimal darajaga tushirish mumkin; (k ¹ i ¹ j) asl matritsa elementlari orqali.

Dastlab, masofa faqat bitta elementli klasterlar o'rtasida aniqlanadi, lekin bir nechta elementni o'z ichiga olgan klasterlar orasidagi masofani aniqlash kerak. Bu har xil usulda amalga oshirilishi mumkin va tanlangan usulga qarab, biz har xil xususiyatlarga ega klasterli tahlil algoritmlarini olamiz. Masalan, i + j klasteri va boshqa k guruhlar orasidagi masofani i va k klasterlari va j va k klasterlari orasidagi masofalarning o'rtacha arifmetikasiga teng qo'yishimiz mumkin:

di + j, k = ½ (di k + dj k).

Lekin siz di + j, k ni bu ikki masofaning minimali sifatida belgilashingiz mumkin:

di + j, k = min (di k + dj k).

Shunday qilib, aglomerativ ierarxik algoritmning birinchi bosqichi tasvirlangan. Keyingi harakatlar ham shunga o'xshash.

Agar masofalarni qayta hisoblash uchun quyidagi umumiy formula ishlatilsa, juda keng algoritmlar sinfini olish mumkin:

di + j, k = A (w) min (dik djk) + B (w) maksimal (dik djk), bu erda

A (w) = agar dik £ djk

A (w) = agar dik> djk bo'lsa

B (w) = agar dik £ djk bo'lsa

B (w) = agar dik> djk bo'lsa

bu erda ni va nj - i va j klasterlaridagi elementlar soni, w - erkin parametr, uning tanlovi ma'lum algoritmni aniqlaydi. Masalan, w = 1 uchun biz "o'rtacha ulanish" algoritmini olamiz, uning uchun masofani qayta hisoblash formulasi quyidagicha bo'ladi:

di + j, k =

Bu holda, algoritm ishining har bir bosqichida ikkita klaster orasidagi masofa barcha juft elementlar orasidagi masofalarning o'rtacha arifmetikasiga teng bo'lib chiqadi, shuning uchun juftlikning bir elementi bir klasterga, ikkinchisiga tegishli.

W parametrining aniq ma'nosi, agar w® put qo'yilsa, aniq bo'ladi. Masofani qayta hisoblash formulasi quyidagicha:

di + j, k = min (di, k djk)

Bu "yaqin qo'shni" deb nomlangan algoritm bo'ladi, bu o'zboshimchalik bilan murakkab shaklli klasterlarni ajratish imkonini beradi, agar bunday klasterlarning turli qismlari bir-biriga yaqin elementlar zanjirlari bilan bog'langan bo'lsa. Bunday holda, algoritm ishining har bir bosqichida ikkita klaster orasidagi masofa shu ikki klasterga tegishli bo'lgan eng yaqin ikkita element orasidagi masofaga teng bo'lib chiqadi.

Ko'pincha, guruhlanadigan elementlar orasidagi dastlabki masofalar (farqlar) berilgan deb taxmin qilinadi. Ba'zi vazifalarda bu to'g'ri. Biroq, bu ma'lumotlar asosida faqat ob'ektlar o'rnatiladi va ularning xarakteristikalari va masofaviy matritsa quriladi. Ob'ektlar orasidagi masofalar hisoblanadimi yoki ob'ektlarning xarakteristikalari o'rtasida turlicha bo'ladigan usullar qo'llaniladi.

Ob'ektlarni tahlil qilishda, farqning eng keng tarqalgan o'lchovi evklid masofasining kvadratidir

(bu erda xih, xjh-i-chi va j-chi ob'ektlar uchun h-chi xususiyatning qiymatlari, m-xarakteristikalar soni) yoki Evklid masofasining o'zi. Agar har xil og'irliklar xususiyatlarga tegishli bo'lsa, masofani hisoblashda bu og'irliklar hisobga olinishi mumkin

Ba'zida masofa quyidagi formula bo'yicha hisoblangan farq o'lchovi sifatida ishlatiladi:

"Hamming", "Manxetten" yoki "shahar bloki" masofasi deb nomlanadi.

Ko'p masalalarda ob'ektlar xususiyatlarining o'xshashligining tabiiy o'lchovi ular orasidagi korrelyatsion koeffitsientdir

bu erda mi, mj, di, dj - mos ravishda i va j xarakteristikalari uchun o'rtacha va standart og'ishlar. Xususiyatlar orasidagi farqni 1 - r qiymati bilan o'lchash mumkin. Ba'zi muammolarda korrelyatsiya koeffitsientining belgisi ahamiyatsiz va faqat o'lchov birligini tanlashga bog'liq. Bunda ô1 - ri j ô xarakteristikalar orasidagi farq o'lchovi sifatida ishlatiladi

1.5 Klasterlar soni.

Juda muhim masala - kerakli miqdordagi klasterlarni tanlash muammosi. Ba'zida m a klasterlar sonini tanlash mumkin. Biroq, umumiy holatda, bu raqam to'plamni klasterlarga bo'lish jarayonida aniqlanadi.

Tadqiqot Fortier va Sulaymon tomonidan olib borildi va eng yaxshi bo'linish ehtimoliga erishish uchun klasterlar sonini hisobga olish kerakligi aniqlandi. Shunday qilib, bo'linmalarning optimal soni - bu eng yaxshi yoki ma'lum ma'noda, mumkin bo'lgan bo'linmalar to'plamidagi ruxsat berilgan bo'laklarning b funktsiyasi. Umumiy tarqalish qanchalik katta bo'lsa, ruxsat etilgan bo'limlarning b qismi qanchalik baland bo'lsa. Fortier va Sulaymon kerakli bo'limlar sonini topish uchun jadval yaratdilar. S (a, b) a va b ga bog'liq (bu erda a - eng yaxshi bo'linish ehtimoli, b - bo'limlarning umumiy sonidagi eng yaxshi bo'limlarning ulushi) , lekin Xolsenger va Xarman tomonidan kiritilgan a'zolik chorasi. Quyida S (a, b) qiymatlari jadvali berilgan.

S qiymatlari jadvali (a, b)

b \ a 0.20 0.10 0.05 0.01 0.001 0.0001

0.20 8 11 14 21 31 42
0.10 16 22 29 44 66 88
0.05 32 45 59 90 135 180
0.01 161 230 299 459 689 918
0.001 1626 2326 3026 4652 6977 9303
0.0001 17475 25000 32526 55000 75000 100000
Ko'pincha, tegishli funktsiyani o'zgartirish birlashma mezoniga aylanadi (klasterlar soni). Masalan, burilishlar kvadratlarining yig'indisi:

Guruhlash jarayoni bu erda E mezonining qiymatining ketma -ket minimal o'sishiga mos kelishi kerak. E qiymatining keskin sakrashining mavjudligi o'rganilgan populyatsiyada ob'ektiv ravishda mavjud bo'lgan klasterlar sonining xarakteristikasi sifatida talqin qilinishi mumkin.

Shunday qilib, eng yaxshi klasterlar sonini aniqlashning ikkinchi usuli, ob'ektlarning kuchli bog'langan holatdan kuchsiz bog'langan holatiga fazaviy o'tish bilan aniqlanadigan sakrashlarni aniqlashga kamayadi.

— Источник: https://serviceproekt.ru/uz/biznes/referat-klasternyi-analiz-klasternyi-analiz-i-ego-zadachi-ustoichivost-i/ © serviceproekt.ru