Çox sayda müşahidə ilə, klaster analizinin iyerarxik üsulları uyğun deyil. Belə hallarda bölməyə əsaslanan qeyri-ierarxik üsullardan istifadə edilir ki, bu da ilkin populyasiyanın parçalanmasının iterativ üsullarıdır. Bölmə prosesi zamanı dayandırma qaydası yerinə yetirilənə qədər yeni klasterlər formalaşır.
Bu cür qeyri-ierarxik klasterləşmə verilənlər toplusunun müəyyən sayda fərqli klasterlərə bölünməsindən ibarətdir. İki yanaşma var. Birincisi, klasterlərin sərhədlərini ilkin məlumatların çoxölçülü məkanında ən sıx sahələr kimi müəyyən etməkdir, yəni. böyük "nöqtələrin cəmləşməsi"nin olduğu bir klasterin tərifi. İkinci yanaşma obyekt fərqinin ölçüsünü minimuma endirməkdir
Alqoritm k-orta (k-vasitəsi)
Qeyri-ierarxik üsullar arasında ən çox yayılmışı k-means alqoritmidir ki, bu da sürətli klaster analizi adlanır. Alqoritmin tam təsviri Hartiqan və Vonqda (1978) tapıla bilər. Klasterlərin sayı haqqında ilkin fərziyyələr tələb etməyən iyerarxik üsullardan fərqli olaraq, bu metoddan istifadə etmək üçün klasterlərin ən çox ehtimal olunan sayı haqqında fərziyyənin olması lazımdır.
k-means alqoritmi bir-birindən mümkün qədər uzaq məsafədə yerləşən k klaster qurur. K-orta alqoritminin həll etdiyi problemlərin əsas növü klasterlərin sayı ilə bağlı fərziyyələrin (fərziyyələrin) olmasıdır, halbuki onlar mümkün qədər fərqli olmalıdır. k rəqəminin seçimi əvvəlki tədqiqatlara, nəzəri mülahizələrə və ya intuisiyaya əsaslana bilər.
Alqoritmin ümumi ideyası: müəyyən edilmiş sabit sayda k müşahidə klasterləri elə klasterlərlə müqayisə edilir ki, klasterdəki ortalamalar (bütün dəyişənlər üçün) bir-birindən mümkün qədər fərqlənsin.
Alqoritmin təsviri
- Obyektlərin klasterlər üzrə ilkin paylanması. k ədədi seçilir və ilk addımda bu nöqtələr klasterlərin “mərkəzi” hesab olunur. Hər bir klaster bir mərkəzə uyğun gəlir.
İlkin centroidlərin seçimi aşağıdakı kimi həyata keçirilə bilər:
- ilkin məsafəni maksimuma çatdırmaq üçün k-müşahidələrin seçilməsi;
- k-müşahidələrin təsadüfi seçimi;
- ilk k-müşahidələrin seçimi.
Nəticədə, hər bir obyekt müəyyən bir klasterə təyin olunur. - İterativ proses. Klasterlərin mərkəzləri hesablanır, sonra və sonra çoxluqların koordinat vasitələri hesab olunur. Obyektlər yenidən bölüşdürülür.
Mərkəzlərin hesablanması və obyektlərin yenidən bölüşdürülməsi prosesi aşağıdakı şərtlərdən biri yerinə yetirilənə qədər davam edir:
- klaster mərkəzləri sabitləşib; bütün müşahidələr cari iterasiyadan əvvəl aid olduqları klasterə aiddir;
- təkrarların sayı təkrarların maksimum sayına bərabərdir.
Şəkil 1 - k-orta alqoritminin işinə nümunə (k=2)
Klasterlərin sayının seçimi mürəkkəb məsələdir. Bu rəqəmlə bağlı heç bir fərziyyə yoxdursa, nəticələri müqayisə edərək 2 klaster, sonra 3, 4, 5 və s. yaratmaq tövsiyə olunur.
Klasterləşmənin keyfiyyətinin yoxlanılması
K-means metodundan istifadə edərək klaster analizinin nəticələrini əldə etdikdən sonra klasterləşmənin düzgünlüyünü yoxlamaq lazımdır (yəni, klasterlərin bir-birindən necə fərqləndiyini qiymətləndirmək). Bunun üçün hər klaster üçün orta dəyərlər hesablanır. Yaxşı qruplaşma bütün ölçmələr və ya ən azı onların əksəriyyəti üçün çox fərqli vasitələr yaratmalıdır.
k-orta alqoritminin üstünlükləri:
- istifadə rahatlığı;
- istifadə sürəti;
- alqoritmin aydınlığı və şəffaflığı.
- alqoritm ortanı təhrif edə bilən kənar göstəricilərə çox həssasdır. Bu problemin mümkün həlli alqoritmin modifikasiyasından - k-median alqoritmindən istifadə etməkdir;
- alqoritm böyük verilənlər bazalarında yavaş ola bilər. Bu problemin mümkün həlli məlumatların seçilməsindən istifadə etməkdir.
PAM k-orta alqoritminin, k-median alqoritminin (k-medoids) modifikasiyasıdır.
Alqoritm məlumat səs-küyünə və kənar göstəricilərə k-orta alqoritmindən daha az həssasdır, çünki mediana kənar göstəricilərdən daha az təsir göstərir.
PAM kiçik verilənlər bazaları üçün effektivdir, lakin böyük verilənlər bazaları üçün istifadə edilməməlidir. Ölçüdən əvvəl azalma
Məsələni nəzərdən keçirək. Bircins qruplara bölünməli olan şirkətin müştərilərinin məlumat bazası var. Hər bir müştəri 25 dəyişəndən istifadə etməklə təsvir olunur. Belə çoxlu sayda dəyişənlərin istifadəsi qeyri-səlis strukturun klasterlərinin seçilməsinə gətirib çıxarır. Nəticədə, analitik üçün yaranan klasterləri şərh etmək olduqca çətindir.
Daha başa düşülən və şəffaf klasterləşdirmə nəticələri o zaman əldə edilə bilər ki, ilkin dəyişənlər toplusu əvəzinə, sıxılmış formada dəyişənlər arasındakı əlaqələr haqqında məlumatı ehtiva edən bəzi ümumiləşdirilmiş dəyişənlər və ya meyarlar istifadə olunsun. Bunlar. verilənlərin ölçüsünün azaldılması problemi yaranır. Müxtəlif üsullardan istifadə etməklə həll edilə bilər; ən çox yayılmışlardan biri faktor analizidir. Onun üzərində daha ətraflı dayanaq.
Faktor təhlili
Faktor analizi dəyişənlərin dəyərləri arasındakı əlaqələri öyrənmək üçün istifadə olunan bir üsuldur.
Ümumiyyətlə, faktor analizinin iki məqsədi var:
- dəyişənlərin sayının azaldılması;
- dəyişənlərin təsnifatı - dəyişənlər arasında əlaqələrin strukturunun müəyyən edilməsi.
Faktor təhlili nəticəsində müəyyən edilmiş meyarlar və ya əsas amillər dəyişənlər arasında mövcud əlaqələr haqqında sıxılmış formada məlumatları ehtiva edir. Bu məlumat daha yaxşı klaster nəticələri əldə etməyə və klasterlərin semantikasını daha yaxşı izah etməyə imkan verir. Faktorların özlərinə müəyyən məna verilə bilər.
Amil analizinin köməyi ilə çoxlu sayda dəyişənlər daha kiçik sayda müstəqil təsir edən kəmiyyətlərə endirilir ki, bunlar da amillər adlanır.
"Sıxılmış" formada olan amil bir neçə dəyişən haqqında məlumat ehtiva edir. Bir-biri ilə yüksək korrelyasiyaya malik dəyişənlər bir amilə birləşdirilir. Amil təhlili nəticəsində nəzərdən keçirilən dəyişənlər arasındakı əlaqələri mümkün qədər dolğun şəkildə izah edən belə mürəkkəb amillər aşkar edilir.
Faktor təhlilinin ilk mərhələsində dəyişənlərin dəyərləri standartlaşdırılır, ehtiyac əvvəlki mühazirədə nəzərdən keçirilir.
Faktor təhlili təhlil edilən dəyişənlərin nisbətən az sayda bəzi gizli amillərin dolayı təzahürləri olduğu fərziyyəsinə əsaslanır.
Faktor təhlili müşahidə olunan dəyişənlər arasında gizli asılılıqların müəyyən edilməsinə və təhlilinə yönəlmiş metodlar toplusudur. Gizli asılılıqlara gizli asılılıqlar da deyilir.
Faktor təhlilinin üsullarından biri - əsas komponentlər metodu amillərin bir-birindən asılı olmaması fərziyyəsinə əsaslanır.
SPSS-də iterativ klasterləşdirmə Adətən, statistik paketlərdə geniş metodlar arsenalı həyata keçirilir ki, bu da əvvəlcə məlumat dəstinin ölçüsünü azaltmağa (məsələn, amil təhlilindən istifadə etməklə), sonra özünü klasterləşdirməyə (məsələn, sürətli klaster analizi metodundan istifadə etməklə) imkan verir. . SPSS paketində klasterləşmə üçün bu variantı nəzərdən keçirin.
İlkin məlumatların ölçüsünü azaltmaq üçün istifadə edirik faktor təhlili. Bunu etmək üçün menyuda seçin: Analiz et (Təhlil) / Məlumatların azaldılması (Məlumatların çevrilməsi) / Faktor (Faktor təhlili):
Çıxarma metodunu seçmək üçün Extraction: düyməsini istifadə edin. Yuxarıda qeyd olunan defolt Əsas Komponent Təhlilini tərk edəcəyik. Siz həmçinin fırlanma metodunu seçməlisiniz - gəlin ən populyarlarından birini - varimax metodunu seçək. Amil dəyərlərini dəyişənlər kimi saxlamaq üçün "Dəyərlər" sekmesinde "Dəyişənlər kimi saxla" işarəsi qoyulmalıdır.
Bu prosedurun nəticəsi olaraq istifadəçi seçilmiş amillərin sayını göstərən "İzah edilmiş ümumi dispersiya" hesabatını alır - bunlar öz dəyərləri birdən çox olan komponentlərdir.
Adətən fakt1_1, fakt1_2 və s. adları verilən amillərin əldə edilmiş qiymətləri k-means metodundan istifadə edərək klaster analizi üçün istifadə olunur. Tez klaster təhlili aparmaq üçün menyudan seçin:
Analyze/Classify/K-Means Cluster: (K-means cluster analizi).
K Means Cluster Analysis dialoq qutusunda (k-vasitəsi ilə klaster təhlili) fakt1_1, fakt1_2 və s. faktor dəyişənlərini qoymalısınız. sınaqdan keçirilmiş dəyişənlər sahəsində. Burada həmçinin klasterlərin sayını və təkrarlamaların sayını təyin etməlisiniz.
Bu prosedur nəticəsində biz formalaşmış klasterlərin mərkəzlərinin qiymətlərinin, hər bir klasterdə müşahidələrin sayının, həmçinin istifadəçi tərəfindən müəyyən edilmiş əlavə məlumatların çıxışı ilə hesabat əldə edirik.
Beləliklə, k-orta alqoritmi ilkin verilənlər toplusunu verilmiş sayda klasterlərə bölür. Alınan nəticələri vizuallaşdırmaq üçün qrafiklərdən biri, məsələn, səpələnmə qrafası istifadə edilməlidir. Bununla belə, ənənəvi vizuallaşdırma məhdud sayda ölçülər üçün mümkündür, çünki bildiyiniz kimi, insan yalnız üç ölçülü məkanı qavra bilər. Buna görə də, üçdən çox dəyişəni təhlil etsək, məlumatın təqdim edilməsi üçün xüsusi çoxölçülü metodlardan istifadə etməliyik, onlar kursun sonrakı mühazirələrindən birində müzakirə ediləcəkdir.
İterativ klasterləşdirmə üsulları aşağıdakı parametrlərin seçimində fərqlənir:
- başlanqıc nöqtəsi;
- yeni klasterlərin formalaşması qaydası;
- dayandırma qaydası.
Məsələn, SPSS-də həm kəmiyyət (məsələn, gəlir) və həm də kateqoriyalı (məsələn, ailə vəziyyəti) dəyişənlərlə işləmək lazımdırsa, həmçinin məlumatların miqdarı kifayət qədər böyükdürsə, İki Mərhələli Klaster Analizi metodu istifadə olunur. miqyaslana bilən klasterləşdirmə proseduru olan istifadə olunur.müxtəlif tipli verilənlərlə işləməyə imkan verən təhlil. Bunun üçün işin birinci mərhələsində qeydlər çoxlu sayda alt qruplara əvvəlcədən qruplaşdırılır. İkinci mərhələdə əldə edilən alt qruplar lazımi sayda qruplaşdırılır. Bu nömrə bilinmirsə, prosedur özü onu avtomatik olaraq müəyyən edir. Bu prosedurla bank işçisi, məsələn, eyni vaxtda yaş, cins və gəlir səviyyəsi kimi göstəricilərdən istifadə edərək insan qruplarını seçə bilər. Əldə edilən nəticələr kreditin ödənilməməsi riski olan müştəriləri müəyyən etməyə imkan verir.
Ümumi halda klaster təhlilinin bütün mərhələləri bir-biri ilə bağlıdır və onlardan birində qəbul edilən qərarlar sonrakı mərhələlərdəki hərəkətləri müəyyən edir.
Analitik bütün müşahidələrdən istifadə etmək və ya bəzi məlumatları və ya nümunələri məlumat dəstindən çıxarmaq barədə qərar verməlidir.
Metrik seçimi və ilkin məlumatların standartlaşdırılması metodu.
Klasterlərin sayının müəyyən edilməsi (iterativ klaster təhlili üçün).
Klasterləşmə metodunun müəyyən edilməsi (qaydaların birləşdirilməsi və ya əlaqələndirilməsi).
Bir çox ekspertlərin fikrincə, klasterlərin forma və spesifikliyinin müəyyən edilməsində klasterləşmə metodunun seçimi həlledicidir.
Klasterləşdirmə nəticələrinin təhlili. Bu mərhələ aşağıdakı sualların həllini nəzərdə tutur: nəticədə klasterləşmə təsadüfidir; bölmənin verilənlərin alt nümunələrində etibarlı və sabit olub-olmaması; klasterləşmənin nəticələri ilə klasterləşmə prosesində iştirak etməyən dəyişənlər arasında əlaqənin olub-olmaması; klasterləşmənin nəticələrini şərh etmək mümkün olub-olmaması.
Klasterləşdirmə nəticələrinin yoxlanılması. Klasterləşdirmənin nəticələri də rəsmi və qeyri-rəsmi üsullar. Formal metodlar klasterləşmə üçün istifadə olunan metoddan asılıdır. Qeyri-rəsmi olanlara klasterləşmənin keyfiyyətini yoxlamaq üçün aşağıdakı prosedurlar daxildir:
- verilənlər toplusunun müəyyən nümunələri üzrə əldə edilmiş klasterləşdirmə nəticələrinin təhlili;
- çarpaz doğrulama;
- verilənlər toplusunda müşahidələrin sırasını dəyişdirərkən klasterləşdirmənin aparılması;
- bəzi müşahidələrin silinməsi zamanı klasterləşmənin aparılması;
- kiçik nümunələr üzərində qruplaşma.
Klaster analizinin tətbiqi zamanı yarana biləcək çətinliklər və problemlər
Hər hansı digər üsullar kimi, klaster analizi metodlarının da müəyyən xüsusiyyətləri vardır zəif tərəfləri, yəni. bəzi çətinliklər, problemlər və məhdudiyyətlər.
Klaster təhlili apararkən nəzərə almaq lazımdır ki, klasterləşmənin nəticələri ilkin verilənlər toplusunun parçalanması meyarlarından asılıdır. Məlumat ölçüsü azaldıqda müəyyən təhriflər baş verə bilər, ümumiləşdirmələrə görə obyektlərin bəzi fərdi xüsusiyyətləri itirilə bilər.
Klasterləşdirmədən əvvəl nəzərə alınmalı olan bir sıra mürəkkəbliklər var.
- Klasterləşmənin aparıldığı xüsusiyyətlərin seçiminin mürəkkəbliyi. Düşünülməmiş seçim çoxluqlara qeyri-adekvat bölünməyə və nəticədə problemin düzgün həllinə gətirib çıxarır.
- Klasterləşdirmə metodunu seçməkdə çətinlik. Bu seçim üsulları və onların istifadəsi üçün ilkin şərtləri yaxşı bilmək tələb edir. Müəyyən bir mövzu sahəsində müəyyən bir metodun effektivliyini yoxlamaq üçün aşağıdakı proseduru tətbiq etmək məsləhətdir: bir-birindən apriori fərqli olan bir neçə qrupu nəzərdən keçirin və nümayəndələrini bir-biri ilə təsadüfi qarışdırın. Sonra, orijinal bölməni klasterlərə bərpa etmək üçün klasterləşdirmə aparılır. Müəyyən edilmiş və ilkin qruplarda obyektlərin üst-üstə düşmə nisbəti metodun effektivliyinin göstəricisidir.
- Klasterlərin sayının seçilməsi problemi. Klasterlərin mümkün sayı haqqında məlumat yoxdursa, bir sıra təcrübələr aparmaq və müxtəlif sayda klasterlərin sadalanması nəticəsində onların optimal sayını seçmək lazımdır.
- Klasterləşdirmə nəticələrinin şərhi problemi. Klasterlərin forması əksər hallarda birləşmə metodunun seçimi ilə müəyyən edilir. Bununla belə, nəzərə almaq lazımdır ki, konkret metodlar tədqiq olunan verilənlər bazasında faktiki olaraq klasterlər olmasa belə, müəyyən formalı klasterlər yaratmağa meyllidir.
Klasterləşdirmədən əvvəl analitikdə klaster təhlili metodlarının hansı qrupuna üstünlük veriləcəyi sualı yarana bilər. İyerarxik və qeyri-ierarxik üsullar arasında seçim edərkən aşağıdakı xüsusiyyətləri nəzərə almaq lazımdır.
Qeyri-ierarxik üsullar səs-küyə və kənar göstəricilərə qarşı daha yüksək müqaviməti, metrikanın düzgün seçilməməsini, klasterləşmədə iştirak edən dəstdə əhəmiyyətsiz dəyişənlərin daxil edilməsini aşkar edir. Metodun bu üstünlükləri üçün ödəniləcək qiymət “apriori” sözüdür. Analitik klasterlərin sayını, təkrarlamaların sayını və ya dayandırma qaydasını, eləcə də bəzi digər klasterləşmə parametrlərini əvvəlcədən müəyyən etməlidir. Bu, xüsusilə yeni başlayanlar üçün çətindir.
Klasterlərin sayı ilə bağlı heç bir fərziyyə yoxdursa, iyerarxik alqoritmlərdən istifadə etmək tövsiyə olunur. Bununla belə, seçmənin ölçüsü buna imkan vermirsə, mümkün yol müxtəlif sayda klasterlərlə bir sıra təcrübələr aparmaqdır, məsələn, verilənlər toplusunu iki qrupdan ayırmağa başlamaq və onların sayını tədricən artıraraq nəticələri müqayisə etməkdir. Nəticələrin bu "variasiyası" sayəsində kifayət qədər böyük klasterləşmə çevikliyi əldə edilir.
İyerarxik üsullar, iyerarxik olmayanlardan fərqli olaraq, klasterlərin sayını təyin etməkdən imtina edir, lakin yuvalanmış klasterlərin tam ağacını qurur.
İerarxik klasterləşdirmə üsullarının mürəkkəbliyi: verilənlər toplusunun həcminin məhdudlaşdırılması; yaxınlıq ölçüsünün seçimi; əldə edilmiş təsnifatların əyilməzliyi.
Bu metodlar qrupunun qeyri-ierarxik üsullarla müqayisədə üstünlüyü onların aydınlığı və məlumat strukturu haqqında ətraflı təsəvvür əldə etmək qabiliyyətidir.
İerarxik metodlardan istifadə edərkən verilənlər toplusunda kənar göstəriciləri kifayət qədər asanlıqla müəyyən etmək və nəticədə məlumatların keyfiyyətini yaxşılaşdırmaq mümkündür. Bu prosedur iki addımlı klasterləşdirmə alqoritminin əsasını təşkil edir. Belə bir məlumat dəsti daha sonra iyerarxik olmayan qruplaşma üçün istifadə edilə bilər.
Bu mühazirədə artıq qeyd olunan başqa bir cəhət də var. Bu, bütün məlumat kütləsinin və ya onun nümunəsinin qruplaşdırılması məsələsidir. Bu aspekt hər iki hesab edilən metodlar qrupu üçün vacibdir, lakin iyerarxik metodlar üçün daha vacibdir. İerarxik üsullar böyük məlumat dəstləri ilə işləyə bilməz və bəzi seçimlərin istifadəsi, yəni. məlumatların bir hissəsi bu üsulların tətbiqinə imkan verə bilər.
Klasterləşdirmə nəticələrinin kifayət qədər statistik əsaslandırması olmaya bilər. Digər tərəfdən, klasterləşmə məsələlərini həll edərkən, əldə edilmiş nəticələrin qeyri-statistik şərhi, eləcə də klaster konsepsiyası üçün kifayət qədər geniş çeşidli variantlar məqbuldur. Belə qeyri-statistik şərh analitikə qənaətbəxş klasterləşdirmə nəticələri əldə etməyə imkan verir ki, bu da digər metodlardan istifadə edərkən çox vaxt çətin olur.
Yeni alqoritmlər və klaster analizi alqoritmlərinin bəzi modifikasiyaları
Bu və əvvəlki mühazirələrdə nəzərdən keçirdiyimiz üsullar klaster analizinin “klassikləri”dir. Son vaxtlara qədər klasterləşdirmə alqoritminin qiymətləndirildiyi əsas meyar klasterləşmənin keyfiyyəti idi: bütün məlumat dəstinin uyğun olduğu güman edilirdi. təsadüfi giriş yaddaşı.
Ancaq indi, super böyük verilənlər bazalarının meydana gəlməsi ilə əlaqədar olaraq, klasterləşdirmə alqoritminin təmin etməli olduğu yeni tələblər var. Əsas olan, əvvəlki mühazirələrdə qeyd edildiyi kimi, alqoritmin miqyaslılığıdır.
Biz həmçinin klasterləşdirmə alqoritminin təmin etməli olduğu digər xassələri də qeyd edirik: nəticələrin daxil edilən məlumatların ardıcıllığından müstəqilliyi; alqoritm parametrlərinin daxil edilən məlumatlardan müstəqilliyi.
Bu yaxınlarda super böyük verilənlər bazalarını emal edə bilən yeni klasterləşdirmə alqoritmlərinin aktiv inkişafı müşahidə olunur. Onlar miqyaslılığa diqqət yetirirlər. Belə alqoritmlərə ümumiləşdirilmiş klaster təsviri, həmçinin əsas DBMS tərəfindən dəstəklənən məlumat strukturlarının seçilməsi və istifadəsi daxildir.
İerarxik klasterləşdirmə üsullarının digər üsullarla inteqrasiya olunduğu alqoritmlər işlənib hazırlanmışdır. Bu alqoritmlərə aşağıdakılar daxildir: BIRCH, CRE, CHAMELEON, ROCK.
BIRCH alqoritmi (İerarxiyalardan istifadə edərək balanslaşdırılmış iterativ azalma və klasterləşdirmə)
Alqoritm Tian Zang və onun həmkarları tərəfindən təklif edilib.
Klasterlərin ümumiləşdirilmiş təsvirləri sayəsində klasterləşmə sürəti artır, alqoritmdə isə böyük miqyas var.
Bu alqoritm iki mərhələli klasterləşmə prosesini həyata keçirir.
Birinci mərhələdə klasterlərin ilkin dəsti formalaşır. İkinci mərhələdə müəyyən edilmiş klasterlərə digər klasterləşdirmə alqoritmləri tətbiq edilir - RAM-da işləmək üçün uyğundur.
Bu alqoritmi təsvir edən aşağıdakı bənzətmə verilmişdir. Hər bir məlumat elementi masanın səthində uzanan bir muncuq kimi düşünülürsə, o zaman muncuq klasterləri tennis topları ilə "əvəz edilə" və tennis toplarının çoxluqlarının daha ətraflı tədqiqi aparıla bilər. Muncuqların sayı kifayət qədər böyük ola bilər, lakin tennis toplarının diametri elə seçilə bilər ki, ikinci mərhələdə ənənəvi klasterləşdirmə alqoritmlərindən istifadə edərək çoxluqların faktiki mürəkkəb formasını müəyyən etmək mümkün olsun.
Dalğa Klaster Alqoritmi
WaveCluster dalğa çevrilmələrinə əsaslanan klasterləşdirmə alqoritmidir. Alqoritmin əvvəlində verilənlər məkanına çoxölçülü qəfəs tətbiq edilməklə məlumatlar ümumiləşdirilir. Alqoritmin sonrakı addımlarında ayrı-ayrı nöqtələr deyil, qəfəsin bir xanasına düşən nöqtələrin ümumiləşdirilmiş xarakteristikaları təhlil edilir. Belə bir ümumiləşdirmə nəticəsində lazımi məlumatlar RAM-a uyğun gəlir. Sonrakı addımlarda alqoritm klasterləri müəyyən etmək üçün ümumiləşdirilmiş məlumatlara dalğa çevrilməsini tətbiq edir.
WaveCluster-in əsas xüsusiyyətləri:
- həyata keçirilməsinin mürəkkəbliyi;
- alqoritm ixtiyari formaların klasterlərini aşkar edə bilər;
- alqoritm səs-küyə həssas deyil;
- alqoritm yalnız aşağı ölçülü verilənlərə şamil edilir.
CLARA alqoritmi 1990-cı ildə Kaufmann və Rousseeuw tərəfindən böyük verilənlər bazalarında məlumatların toplanması üçün hazırlanmışdır. Bu alqoritm S+ kimi statistik analitik paketlərdə qurulub.
Alqoritmin mahiyyətini qısaca təsvir edək. CLARA alqoritmi verilənlər bazasından çoxlu nümunələr əldə edir. Nümunələrin hər birinə klasterləşdirmə tətbiq edilir, alqoritmin çıxışı kimi ən yaxşı klasterləşdirmə təklif olunur.
Böyük verilənlər bazaları üçün bu alqoritm PAM alqoritmindən daha səmərəlidir. Alqoritmin səmərəliliyi nümunə kimi seçilmiş məlumat dəstindən asılıdır. Seçilmiş dəstdə yaxşı klasterləşmə bütün məlumat dəstində yaxşı klasterləşməni təmin etməyə bilər.
Clarans, CURE, DBScan alqoritmləri
Clarans alqoritmi (RANdomized Axtarışa əsaslanan Böyük Tətbiqlərin Klasterləşdirilməsi) qruplaşma problemini qrafikdə təsadüfi axtarış kimi formalaşdırır. Bu alqoritmin nəticəsi olaraq, qrafik qovşaqlarının dəsti məlumat dəstinin istifadəçi tərəfindən müəyyən edilmiş çoxluqların sayına bölünməsidir. Yaranan klasterlərin "keyfiyyəti" kriteriya funksiyasından istifadə etməklə müəyyən edilir. Clarans alqoritmi məqbul həll axtarışında məlumat dəstinin bütün mümkün bölmələrini çeşidləyir. Həll axtarışı əvvəlcədən müəyyən edilmiş sayda yerli minimumlar arasında minimuma çatdığı qovşaqda dayanır.
Yeni miqyaslana bilən alqoritmlər arasında CURE alqoritmini - iyerarxik klasterləşdirmə alqoritmini və sıxlıq konsepsiyasından istifadə etməklə klaster konsepsiyasının tərtib olunduğu DBScan alqoritmini də qeyd etmək olar.
BIRCH, Clarans, CURE, DBScan alqoritmlərinin əsas çatışmazlığı onların bəzi nöqtə sıxlığı hədlərinin dəqiqləşdirilməsini tələb etməsidir ki, bu da həmişə məqbul olmur. Bu məhdudiyyətlər təsvir olunan alqoritmlərin çox böyük verilənlər bazalarına yönəldilməsi və böyük hesablama resurslarından istifadə edə bilməməsi ilə bağlıdır.
Bir çox tədqiqatçılar əsas vəzifəsi bu gün mövcud olan alqoritmlərin çatışmazlıqlarını aradan qaldırmaq olan miqyaslı metodlar üzərində fəal şəkildə işləyirlər.
Çox sayda müşahidə ilə, klaster analizinin iyerarxik üsulları uyğun deyil. Belə hallarda iyerarxik olmayan bölgüyə əsaslanan üsullardan istifadə olunur ki, bunlar da iterativ üsullar orijinal əhalinin bölünməsi. Bölünmə prosesində yeni klasterlər yaranır dayandırma qaydası.
Bu cür qeyri-ierarxik klasterləşmə verilənlər toplusunun müəyyən sayda fərqli klasterlərə bölünməsindən ibarətdir. İki yanaşma var. Birincisi, klasterlərin sərhədlərini ilkin məlumatların çoxölçülü məkanında ən sıx sahələr kimi müəyyən etməkdir, yəni. böyük "nöqtələrin cəmləşməsi"nin olduğu bir klasterin tərifi. İkinci yanaşma obyekt fərqinin ölçüsünü minimuma endirməkdir
Alqoritm k-orta (k-vasitəsi)
Qeyri-ierarxik üsullar arasında ən çox yayılmışdır k-alqoritmi deməkdir, həmçinin deyilir sürətli klaster analizi. Alqoritmin tam təsviri Hartiqan və Vonqda (1978) tapıla bilər. Klasterlərin sayı haqqında ilkin fərziyyələr tələb etməyən iyerarxik üsullardan fərqli olaraq, bu metoddan istifadə etmək üçün klasterlərin ən çox ehtimal olunan sayı haqqında fərziyyənin olması lazımdır.
k-alqoritmi deməkdir bir-birindən mümkün olan ən böyük məsafədə yerləşən k klaster qurur. Həll edən problemlərin əsas növü k-alqoritmi deməkdir, - klasterlərin sayı ilə bağlı fərziyyələrin (fərziyyələrin) olması, halbuki onlar mümkün qədər fərqli olmalıdır. k rəqəminin seçimi əvvəlki tədqiqatlara, nəzəri mülahizələrə və ya intuisiyaya əsaslana bilər.
Alqoritmin ümumi ideyası: müəyyən edilmiş sabit sayda k müşahidə klasterləri elə klasterlərlə müqayisə edilir ki, klasterdəki ortalamalar (bütün dəyişənlər üçün) bir-birindən mümkün qədər fərqlənsin.
Alqoritmin təsviri
- Obyektlərin klasterlər üzrə ilkin paylanması.
k ədədi seçilir və ilk addımda bu nöqtələr klasterlərin “mərkəzi” hesab olunur. Hər bir klaster bir mərkəzə uyğun gəlir.
İlkin centroidlərin seçimi aşağıdakı kimi həyata keçirilə bilər:
- ilkin məsafəni maksimuma çatdırmaq üçün k-müşahidələrin seçilməsi;
- k-müşahidələrin təsadüfi seçimi;
- ilk k-müşahidələrin seçimi.
Nəticədə, hər bir obyekt müəyyən bir klasterə təyin olunur.
- İterativ proses.
Hesablanır klaster mərkəzləri, o zaman və aşağıda klasterlərin orta koordinatlarıdır. Obyektlər yenidən bölüşdürülür.
Mərkəzlərin hesablanması və obyektlərin yenidən bölüşdürülməsi prosesi aşağıdakı şərtlərdən biri yerinə yetirilənə qədər davam edir:
- klaster mərkəzləri sabitləşdi, yəni. bütün müşahidələr cari iterasiyadan əvvəl aid olduqları klasterə aiddir;
- təkrarların sayı təkrarların maksimum sayına bərabərdir.
Əncirdə. 14.1 iş nümunəsidir k-alqoritmi deməkdir k üçün ikiyə bərabərdir.
düyü. 14.1.
Klasterlərin sayının seçimi mürəkkəb məsələdir. Bu rəqəmlə bağlı heç bir fərziyyə yoxdursa, nəticələri müqayisə edərək 2 klaster, sonra 3, 4, 5 və s. yaratmaq tövsiyə olunur.
Klaster analizi böyük miqdarda məlumatı siniflərə və ya qruplara bölməyə imkan verən statistik analizdir (İngilis dilindən, klaster- sinif) bəzi meyarlara və ya onların birləşməsinə görə.
Məlumatları təsnif etmək üçün X x,...,X səh metrik və ya məsafə anlayışından istifadə edin.
metrik bəzi metrik məkanı həqiqi ədədlər fəzasına uyğunlaşdıran və aşağıdakı xüsusiyyətlərə (metrik aksiomalar) malik olan p funksiyasıdır:
- 1) p(ZD>0,
- 2) p(X,Y)=s(Y, X),
- 3) p(X, Y) = 0 X=Y
- 4) P(X,Y) P(Z, Y).
Klaster analizi nəzəriyyəsi ayrı-ayrı nöqtələr (vektorlar) arasındakı məsafəni ölçmək üçün aşağıdakı ölçülərdən istifadə edir:
1) Evklid məsafəsi
2) çəkili evklid məsafəsi
Harada həftə - təsnifat məsələsində xüsusiyyətin əhəmiyyətinə mütənasib çəkilər. Çəkilər əlavə araşdırmadan sonra təyin edilir
və fərz edək ki, ^ w* = 1;
- 3) çəkic məsafəsi (və ya şəhər bloku) - xəritədə şəhərin məhəllələri arasındakı məsafə
4) Mahalanobis məsafəsi (və ya Mahalanobis bucağı)
burada A simmetrik müsbət müəyyən çəki matrisidir (çox vaxt diaqonal olaraq seçilir); A - vektor kovariasiya matrisi X 19 ..., X p;
5) Minkovski məsafəsi
Müstəqil təsadüfi dəyişənlərin normal paylanması zamanı 1), 2), 3) və ya 5) məsafələrdən istifadə olunur. X l9 ...,X n ~N(M,A) və ya onların geokimyəvi mənada bircins olması halında, hər bir vektor təsnifat üçün eyni dərəcədə vacib olduqda. Məsafə 4) vektorların kovariasiya əlaqəsi olduqda istifadə olunur X x,...,X P.
Metrik seçimi tədqiqatçı hansı nəticəni əldə etmək istədiyindən asılı olaraq həyata keçirir. Bu seçim rəsmiləşdirilməyib, çünki bu, bir çox amillərdən, xüsusən də gözlənilən nəticədən, tədqiqatçının təcrübəsindən, onun riyazi hazırlığının səviyyəsindən və s.
Bir sıra alqoritmlərdə vektorlar arasındakı məsafələrlə yanaşı, klasterlər və klasterlərin birləşmələri arasındakı məsafələrdən də istifadə olunur.
Qoy S(-dən ibarət /-ci klaster n t vektorlar və ya nöqtələr. Qoy
X (l) - klasterə düşən nöqtələr üzərində nümunə orta S f , yaxud klasterin ağırlıq mərkəzi 5.. Sonra içərisində başqa çoxluqlar olmayan çoxluqlar arasında aşağıdakı məsafələr fərqləndirilir:
1) “yaxın qonşu” prinsipinə əsasən klasterlər arasındakı məsafə
2) "uzaq qonşu" prinsipinə görə klasterlər arasındakı məsafə
3) qrupların ağırlıq mərkəzləri arasındakı məsafə
4) "orta əlaqə" prinsipinə görə klasterlər arasındakı məsafə
5) ümumiləşdirilmiş Kolmogorov məsafəsi
Digər siniflərin birliyi olan klasterlər arasındakı məsafə ümumi düsturla hesablana bilər:
Harada S^k^- sinifləri birləşdirməklə əldə edilən klaster S k Və S t .
Məsafələrin bütün xüsusi halları bu ümumiləşdirilmiş düsturdan əldə edilir. a = p = 1/2, 8 = -1/2, y = 0 ilə "yaxın qonşu" prinsipinə görə məsafəmiz var, a = p = 5 = 1/2, y = O - "uzaq" qonşu”,
a \u003d ---, p \u003d---, 5 \u003d 0, y \u003d 0 - ağırlıq mərkəzləri boyunca məsafədə
p k + n i p k + n i
qruplar.
Klaster təhlili üsulları I) aqlomerativ (birləşən), II) bölücü (ayırıcı) və III) iterativlərə bölünür.
Birincilər ardıcıl olaraq ayrı-ayrı obyektləri çoxluqlara birləşdirir, ikincisi, əksinə, çoxluqları obyektlərə parçalayır. Üçüncüsü ilk ikisini birləşdirir. Onların xüsusiyyəti bölmənin keyfiyyətini yaxşılaşdırmaq üçün alqoritmin işləməsi zamanı dəyişdirilə bilən bölmə şərtlərinə (sözdə parametrlər) əsaslanan klasterlərin formalaşmasıdır. İterativ üsullar adətən böyük həcmdə məlumatı təsnif etmək üçün istifadə olunur.
Aqlomerativ üsulları daha ətraflı nəzərdən keçirək. Aqlomerativ üsullar klaster analizi alqoritmləri arasında ən sadə və ən çox yayılmış üsullardır. İlk addımda hər bir vektor və ya obyekt X 19 ..., X səh mənbə məlumatları ayrıca klaster və ya sinif kimi qəbul edilir. Məsafələrin hesablanmış matrisinə görə, bir-birinə ən yaxın olanlar seçilir və birləşdirilir. Aydındır ki, proses bununla yekunlaşacaq (P - 1) nəticədə bütün obyektlərin bir klasterdə birləşdiriləcəyi bir addım.
Birləşmələrin ardıcıllığı dendroqram və ya ağac kimi təqdim edilə bilər. Əncirdə. 1.18 vektorların birinci addımda birləşdirildiyini göstərir X t , X 2 ,çünki onların arasındakı məsafə 0,3-dür.
İkinci mərhələdə onlara bir vektor əlavə edildi X 3 çoxluqdan uzaqda (X 1, X 2) 0,5 məsafəyə və s. Sonuncu mərhələdə bütün vektorlar bir klasterə birləşdirilir.
düyü. 1.18.
Aqlomerativ üsullara tək, orta, tam birləşmə üsulları və Uord metodu daxildir.
1.tək əlaqə üsulu. Qoy X v ..., X n - vektor məlumatları, hər bir vektor bir klaster təşkil edir. Əvvəlcə bu klasterlər arasındakı məsafələrin matrisi hesablanır və metrik olaraq ən yaxın qonşu məsafəsi istifadə olunur. Bu matrisdən istifadə edərək, ilk klaster 5-i təşkil edən ən yaxın iki vektor seçilir. Arasında növbəti addım S] və qalan vektorlar (bunları çoxluq hesab edirik), yeni bir məsafə matrisi hesablanır və klasterlər arasındakı məsafə siniflərə birləşdirilir (a = p = 1/2, 5 = -1/2, y = 0) metrik kimi istifadə olunur. Əvvəllər əldə edilmiş sinifə ən yaxın S( klaster onunla birləşərək əmələ gəlir S2. və s. vasitəsilə P- 1 addım, bütün vektorların bir klasterdə birləşdirildiyini alırıq.
Üstünlüklər: 1) alqoritmin hər addımında yalnız bir element əlavə olunur, 2) üsul son dərəcə sadədir, 3) alqoritm ilkin verilənlərin çevrilməsinə (fırlanma, sürüşmə, tərcümə, uzanma) həssas deyildir.
Qüsurlar: 1) məsafə matrisini daim yenidən hesablamaq lazımdır, 2) klasterlərin sayı əvvəlcədən məlumdur və azaldıla bilməz
- 2. Tam əlaqə üsulu. Metod praktiki olaraq vahid keçid metodunu təkrarlayır, istisna olmaqla, yeni obyektin klasterə daxil edilməsi yalnız və yalnız obyektlər (vektorlar və ya klasterlər) arasındakı məsafə əvvəlcədən müəyyən edilmiş bəzi rəqəmdən az olduqda baş verir. Nömrə istifadəçi tərəfindən təyin olunur. Məsafə yalnız "uzaq qonşu" prinsipinə əsasən hesablanır (eynini siniflərə birləşdirilən siniflər arasındakı məsafə haqqında da demək olar - yalnız os = p = 8 = 1/2, y = 0 üçün uzaq qonşu prinsipi).
- 3.Orta əlaqə üsulu. Klaster yaratma alqoritmi tək keçid alqoritmi ilə üst-üstə düşür, lakin yeni obyektin klasterə daxil edilib-edilməməsinə qərar verilərkən hesablamalar orta keçid prinsipinə əsasən aparılır. Tam keçid metodunda olduğu kimi, klasterlər arasında bütün hesablanmış məsafələr istifadəçi tərəfindən müəyyən edilmiş nömrə ilə müqayisə edilir. Və əgər (məsafə) verilmiş ədəddən azdırsa, yeni obyekt köhnə sinfə daxil edilir. Beləliklə, orta əlaqə üsulu tam əlaqə metodundan yalnız klasterlər arasındakı məsafənin hesablanması üsulu ilə fərqlənir.
- 4. WARD üsulu. Qoy X 19 ..., X səh- verilənlər, hər bir vektor bir klaster təşkil edir. Bəzi metriklərdən (məsələn, Mahalanobis məsafəsindən) istifadə edərək məsafə matrisini tapırıq, onun vasitəsilə bir-birinə ən yaxın olan klasterləri müəyyənləşdiririk. Klaster daxilində vektorların kvadratik kənarlaşmalarının cəmini hesablayın S k düstura görə:
Harada Kimə - klaster nömrəsi, mən- klasterdəki vektor nömrəsi, j- koordinat nömrəsi X t e U1 R, p üçün- klasterdəki vektorların sayı, Xjk- nümunə orta X i V S k . Dəyər Vk klaster daxilində vektorların bir-birindən sapmalarını xarakterizə edir (yeni Sk+Sf və ya köhnə^). Hesablama Vk birlikdən əvvəl və sonra həyata keçirilməlidir və hər şeyi təkrarlamaq lazımdır mümkün variantlar belə birliklər. Daha sonra klasterdə S k yalnız ən az dəyişikliklə nəticələnən vektorlar və ya klasterlər əlavə edilir Vk birləşmədən sonra və nəticədə orijinal çoxluqdan minimum məsafədə yerləşəcək S k .
Əlavə iterativ üsulları nəzərdən keçirin. İterativ metodların mahiyyəti ondan ibarətdir ki, klasterləşmə bəzi ilkin şərtlərin qoyulması ilə başlayır. Məsələn, alınacaq klasterlərin sayını təyin etmək və ya klasterin formalaşması prosesinin sonunu müəyyən edən məsafəni təyin etmək tələb olunur və s. İlkin şərtlər tədqiqatçıya lazım olan nəticəyə uyğun seçilir. Lakin onlar adətən aglomerativ üsullardan biri ilə tapılan məhlula görə təyin edilir. İterativ üsullara ^-ortalama metodu və konsentrasiyaların axtarışı metodu daxildir.
1. Metod /r- deməkdir. Qoy vektorlar olsun Xl9 ...,Xn e9F və onları bölmək lazımdır Kimə klasterlər. Sıfır pilləsində P vektorlar təsadüfi seçilir Kimə onların hər birinin bir çoxluq təşkil etdiyini fərz etsək. Ağırlıqları olan bir sıra istinad klasterləri,...,e[ 0) əldə edirik
coj 0) ,...,X. və arasındakı məsafə matrisini hesablayın x. və standartları e 1 (0),...,^ 0) bəzi metrikaya görə, məsələn, Evklidlərə görə:
Hesablanmış məsafə matrisinin biliyinə əsaslanaraq vektor X ( məsafəsi minimal olan standartda yerləşdirilir. Bunun nə olduğunu dəqiqlik üçün fərz edək. Formula uyğun olaraq əlavə edilmiş nöqtə nəzərə alınmaqla yenidən hesablanmış yenisi ilə əvəz olunur
Bundan əlavə, çəki də yenidən hesablanır:
Matrisdə iki və ya daha çox minimum məsafə baş verərsə, o zaman X tən aşağı sıra nömrəsi ilə klasterə daxil edilir.
Növbəti addımda qalanlardan növbəti vektor seçilir və prosedur təkrarlanır. Beləliklə, ( PC) hər birinə addımlar
standart e^~ k)çəkiyə uyğun olacaq və klasterləşdirmə proseduru başa çatacaq. Böyük ilə P və kiçik Kimə alqoritm tez bir zamanda sabit həllə, yəni alqoritmin ilk tətbiqindən sonra alınan standartların say və tərkibinə görə metodun təkrarlanması zamanı tapılan standartlarla üst-üstə düşdüyü həllə yaxınlaşır. Buna baxmayaraq, alqoritmik prosedur həmişə əvvəlki hesablamalarda əldə edilmiş bölmədən istinad vektorları (ilkin yaxınlaşma kimi) istifadə edərək bir neçə dəfə təkrarlanır: əvvəllər tapılmış istinadlar e[ p k e (2 p k) k)üçün götürüldü e (x 0) 9 ... 9 e (k 0) 9 və alqoritmik prosedur təkrarlanır.
- 2. Kondensasiya axtarış metodu. Bu, aşağıdakı iterativ alqoritmdir. Bu, klasterlərin sayının apriori dəqiqləşdirilməsini tələb etmir. İlk addımda aralarındakı məsafə matrisi X X9 ... 9 X p e Y1 p bəzi metrikaya görə. Sonra birinci klasterin mərkəzi rolunu oynamaq üçün təsadüfi bir vektor seçilir. Bu ilkin yaxınlaşmadır. Fərz edək ki, bu vektor p-ölçülü radiuslu sferanın mərkəzində yerləşir R, və bu radius tədqiqatçı tərəfindən müəyyən edilir. Bundan sonra vektorlar müəyyən edilir X Si ,... 9 X Sk , bu kürənin içərisində qapalı və seçim onlardan hesablanır
- - 1 Kimə
sabit gözlənti X \u003d ~ Y] X 5. Sonra kürənin mərkəzi
geyinilib X, və hesablama proseduru təkrarlanır. İterativ prosesin başa çatmasının şərti orta vektorların bərabərliyidir Xüzərində tapıldı T Və (t+ 1) addımlar. Sferanın içərisində sıxışan elementlər X 9 ... 9 X
biz onları bir klasterə daxil edirik və sonrakı tədqiqatlardan xaric edirik. Qalan nöqtələr üçün alqoritm təkrarlanır. Alqoritm ilkin yaxınlaşmanın istənilən seçimi və istənilən məbləğdə ilkin məlumat üçün birləşir. Bununla belə, sabit bölmə əldə etmək üçün (yəni, alqoritmin ilk tətbiqindən sonra tapılan klasterlərin sayı və tərkibinə görə metodun təkrarlanması zamanı tapılan klasterlərlə üst-üstə düşdüyü bölmə) alqoritmik proseduru bir neçə dəfə təkrarlamaq tövsiyə olunur. sferanın radiusunun müxtəlif dəyərləri üçün R. Sabit bir bölmənin əlaməti eyni tərkibə malik eyni sayda çoxluqların meydana gəlməsi olacaqdır.
Qeyd edək ki, klasterləşmə problemi yoxdur yeganə həll yolu. Nəticədə, məlumatların bütün icazə verilən bölmələrini siniflərə sadalamaq olduqca çətindir və həmişə mümkün deyil. Keyfiyyəti qiymətləndirmək üçün müxtəlif yollarla klasterləşdirmə ən yaxşı (tədqiqatçının nöqteyi-nəzərindən) bölmə üzrə minimum qiymət alan funksional bölmə keyfiyyəti anlayışını təqdim edir.
Qoy X X9 ... 9 X s e U1 R - siniflərə bölünən bəzi müşahidələr toplusu S = (S l9 ... 9 S k ) 9 və Kiməəvvəlcədən məlumdur. Sonra məlum sayda klasterlər üçün əsas bölmə keyfiyyəti funksiyaları formaya malikdir:
1) Sinifdaxili dispersiyaların çəkili cəmi
Harada a(1)- klasterin seçmə riyazi gözləntisi S l
Funksional Q((S) bütövlükdə bütün klasterlərin homojenlik dərəcəsini qiymətləndirməyə imkan verir.
2) Elementlər arasındakı qoşa sinifdaxili məsafələrin cəmi 
və ya
Harada səh 1- klasterdəki elementlərin sayı S { .
3) Ümumiləşdirilmiş sinifdaxili dispersiya
Harada n j- elementlərin sayı S., A; . -üçün nümunə kovariasiya matrisi sj.
Funksional hər bir klaster üçün hesablanmış ümumiləşdirilmiş sinifdaxili dispersiyaların arifmetik ortasıdır. Məlum olduğu kimi, ümumiləşdirilmiş dispersiya çoxvariantlı müşahidələrin dağılma dərəcəsini qiymətləndirməyə imkan verir. Buna görə də Q 3 (S) siniflərdə müşahidə vektorlarının orta səpələnməsini qiymətləndirməyə imkan verir S l9 ... 9 S k . Beləliklə, onun adı - ümumiləşdirilmiş sinifdaxili variasiya. Q 3 (S)ölçüsü orijinaldan kiçik olan məkanda verilənlərin sıxılması və ya müşahidələrin konsentrasiyası problemini həll etmək lazım olduqda istifadə olunur.
4) Müşahidələrin təsnifatının keyfiyyəti həm də Hotelling meyarından istifadə etməklə qiymətləndirilə bilər. Bunun üçün biz fərziyyənin yoxlanılması meyarını tətbiq edirik H 0 iki çoxölçülü populyasiyanın orta vektorlarının bərabərliyi haqqında və statistikanı hesablayın
Harada n t Və p t - siniflərdə vektorların sayı S l , S m ; X, X t- mərkəzləşdirilmiş ilkin məlumatlar; S*- klasterlərin birləşdirilmiş kovariasiya matrisi S n S m: S* =--- (XjX l + X^X m). Əvvəlki kimi, dəyər Q 4 (S)
p,+s t -2
düsturla hesablanmış cədvəl dəyəri ilə müqayisə edilir
Harada m- müşahidə vektorlarının ilkin ölçüsü və əhəmiyyət səviyyəsidir.
Hipoteza H 0 ehtimalı ilə (1-oc) qəbul edilir Q 4 (S) n _ m , və əks halda rədd edilir.
Siniflərə bölünmənin keyfiyyətini empirik olaraq qiymətləndirmək də mümkündür. Məsələn, hər bir sinif üçün tapılan seçmə vasitələrini bütün müşahidələr toplusunun seçmə ortalaması ilə müqayisə etmək olar. Əgər onlar iki və ya daha çox faktorla fərqlənirlərsə, onda bölmə yaxşıdır. Klaster seçmə vasitələrinin müşahidələrin bütün populyasiyasının seçmə ortalaması ilə daha düzgün müqayisəsi siniflərə bölünmənin keyfiyyətini qiymətləndirmək üçün dispersiya təhlilindən istifadə etməyə səbəb olur.
Əgər klasterlərin sayı S = (S l9 ...,S k )əvvəlcədən məlum deyilsə, ixtiyari seçilmiş tam ədəd üçün aşağıdakı bölmə keyfiyyəti funksiyalarından istifadə olunur. m:
IIKimə 1 1 m
- - sinifdaxili orta ölçü
P i=1 n i XjeSj X"tSj J
bayquş səpilməsi,
- (1 P/ 1W
- - X ~-~ r “ çoxluğun nöqtələrinin konsentrasiyasının ölçüsü
P nV l J J
S, - nöqtəni ehtiva edən çoxluqdakı elementlərin sayı X g
Qeyd edək ki, parametrin ixtiyari dəyəri üçün T funksional Z m (S) bərabər minimuma çatır I/ p, orijinal qruplaşma varsa S = (S l9 ...,S k ) monoklasterlərə bölmədir S. = (Xj), çünki V(Xt) = 1. Eyni zamanda Z m (S) əgər maksimum 1-ə çatır S- bütün ilkin məlumatları ehtiva edən bir klaster,
çünki V(X() = n. Xüsusi hallarda bunu göstərmək olar Z_ l (S) =-, Harada Kimə - müxtəlif klasterlərin sayı S = (S l9 ... 9 S k ) 9 Z X (S) = maksimum - ,
*"V P)
Harada n t - klasterdəki elementlərin sayı S i9 Z^(S) = min - ,
G " P)
Qeyd edək ki, klasterlərin sayı naməlum olduqda, bölmə keyfiyyəti funksiyaları yerinə yetirilir Q(S) iki funksionalın cəbri birləşməsi (cəm, fərq, məhsul, nisbət) kimi seçilə bilər Mən m (S), Z m (S),çünki birincisi azalan, digəri isə siniflərin sayının artan funksiyasıdır Kimə. Belə davranış Z m (S)
ekstremumun mövcudluğuna zəmanət verir Q(S).
Giriş
İlk dəfə 1939-cu ildə Tryon tərəfindən təqdim edilən klaster analizi termini 100-dən çox müxtəlif alqoritmi ehtiva edir.
Təsnifat problemlərindən fərqli olaraq, klaster təhlili verilənlər toplusu ilə bağlı aprior fərziyyələr tələb etmir, tədqiq olunan obyektlərin təsvirinə məhdudiyyətlər qoymur və müxtəlif növ məlumatların (interval məlumatları, tezliklər, ikili məlumatlar) göstəricilərini təhlil etməyə imkan verir. . Yadda saxlamaq lazımdır ki, dəyişənlər müqayisəli tərəzilərdə ölçülməlidir.
Klaster təhlili məlumatların ölçüsünü azaltmağa və onu vizual etməyə imkan verir.
Klaster təhlili zaman sıralarının çoxluğuna tətbiq oluna bilər, burada bəzi göstəricilərin oxşarlıq dövrlərini ayırd etmək və oxşar dinamikaya malik zaman seriyaları qruplarını müəyyən etmək olar.
Klaster təhlili biologiya, psixologiya və başqaları kimi bir neçə istiqamətdə paralel olaraq inkişaf etmişdir, ona görə də əksər metodların iki və ya daha çox adı var.
Klaster təhlili tapşırıqlarını aşağıdakı qruplarda qruplaşdırmaq olar:
Tipologiyanın və ya təsnifatın inkişafı.
Obyektlərin qruplaşdırılması üçün faydalı konseptual sxemlərin tədqiqi.
Məlumatların araşdırılmasına əsaslanan fərziyyələrin təqdim edilməsi.
Mövcud məlumatlarda bu və ya digər şəkildə müəyyən edilmiş növlərin (qrupların) həqiqətən mövcud olub-olmadığını müəyyən etmək üçün hipotez testi və ya araşdırma.
Bir qayda olaraq, klaster analizinin praktiki istifadəsində bu vəzifələrdən bir neçəsi eyni vaxtda həll edilir.
Dərsin məqsədi
Klaster analizinin iyerarxik və iterativ üsullarının praktiki tətbiqi bacarıqlarının əldə edilməsi.
Praktik tapşırıq
Yaxın qonşu üsulları üçün alqoritmlərin işlənib hazırlanması və k-orta və kompüter proqramları şəklində həyata keçirmək. DNC istifadə edərək 50 tətbiq yaradın x= (x 1 ,x 2) - koordinatları (3.8) intervalında bərabər paylanmış təsadüfi 2 ölçülü dəyişən. Hazırlanmış proqramlardan istifadə edərək, hər biri 0,15 radiuslu bir sferada yerləşdirilən minimum sayda klasterlərə paylayın.
Təlimatlar
Klaster analizi adı ingiliscə cluster - dəstə, toplanma sözündən yaranmışdır.Klaster analizi müşahidələrin bircins siniflərə - klasterlərə avtomatlaşdırılmış şəkildə qruplaşdırılmasına imkan verən çoxvariantlı statistik analiz prosedurlarının geniş sinfidir.
Klaster aşağıdakı riyazi xüsusiyyətlərə malikdir:
klaster dispersiyası;
standart sapma.
Klaster mərkəzi dəyişənlər fəzasındakı nöqtələrin yeridir.
Klaster radiusu - klasterin mərkəzindən nöqtələrin maksimum məsafəsi.
Klaster dispersiyası klasterin mərkəzinə nisbətən fəzada nöqtələrin yayılmasının ölçüsüdür.
Obyektlərin klaster mərkəzinə nisbətən standart sapması (RMS) klaster dispersiyasının kvadrat köküdür.
Klaster analiz üsulları
Klaster analiz üsullarını iki qrupa bölmək olar:
iyerarxik;
iyerarxik olmayan.
Hər bir qrupa bir çox yanaşma və alqoritm daxildir.
Klaster analizinin müxtəlif üsullarından istifadə edərək analitik eyni məlumat üzrə müxtəlif həllər əldə edə bilər. Bu normal hesab olunur.
Klaster analizinin iyerarxik üsulları
İerarxik klasterlərin mahiyyəti kiçik klasterlərin ardıcıl olaraq daha böyük klasterlərə birləşməsi və ya böyük klasterlərin daha kiçik qruplara bölünməsidir.
İerarxik Aqlomerativ Metodlar(Agglomerative Nesting, AGNES)
Bu üsullar qrupu ilkin elementlərin ardıcıl kombinasiyası və müvafiq olaraq klasterlərin sayında azalma ilə xarakterizə olunur.
Alqoritmin əvvəlində bütün obyektlər ayrı klasterlərdir. İlk addımda ən çox oxşar obyektlər klasterə birləşdirilir. Sonrakı addımlarda birləşmə bütün obyektlər bir çoxluq təşkil edənə qədər davam edir.
İerarxik bölünən (bölünən) üsullar(Divisive ANAlysis, DIANA)
Bu üsullar aqlomerativ metodların məntiqi əksidir. Alqoritmin əvvəlində bütün obyektlər bir klasterə aiddir, o, sonrakı addımlarda daha kiçik klasterlərə bölünür, nəticədə parçalanma qruplarının ardıcıllığı əmələ gəlir.
İerarxik klasterləşdirmə üsulları klasterlərin qurulması qaydalarında fərqlənir. Qaydalar, obyektlərin bir qrupa birləşdirildiyi zaman onların "oxşarlığı"na qərar verilərkən istifadə olunan meyarlardır.
Oxşarlıq ölçüləri
Obyektlər arasındakı məsafəni hesablamaq üçün metriklər və ya məsafə funksiyaları da adlandırılan müxtəlif oxşarlıq ölçülərindən (oxşarlıq ölçülərindən) istifadə olunur.
Evklid məsafəsiçoxölçülü fəzada həndəsi məsafədir və (4.1) düsturu ilə hesablanır.
Evklid məsafəsi (və onun kvadratı) standartlaşdırılmış məlumatlardan deyil, ilkin məlumatlar əsasında hesablanır.
Evklid məsafəsinin kvadratı (4.2) düsturu ilə hesablanır.
(4.2)
Manhetten məsafəsi (şəhər bloku məsafəsi), həmçinin "hamming" və ya "şəhər bloku" məsafəsi adlanır, koordinatlar üzərindəki fərqlərin ortalaması kimi hesablanır. Əksər hallarda bu məsafə ölçüsü Evklid məsafəsinin hesablamalarına oxşar nəticələrə gətirib çıxarır. Bununla belə, bu tədbir üçün fərdi kənar göstəricilərin təsiri Evklid məsafəsindən istifadə edərkən daha azdır, çünki burada koordinatlar kvadrat deyildir. Manhetten məsafəsi (4.3) düsturu ilə hesablanır.
(4.3)
Çebışev məsafəsi bir ölçüdə fərqlənən iki obyekti "fərqli" kimi təyin etmək lazım olduqda istifadə edilməlidir. Çebışev məsafəsi (4.4) düsturu ilə hesablanır.
(4.4)
Güc məsafəsi müvafiq obyektlərin çox fərqli olduğu ölçü ilə bağlı çəkisi tədricən artırmaq və ya azaltmaq istəyərkən istifadə olunur. Güc məsafəsi (4.5) düsturu ilə hesablanır.
(4.5)
Harada r Və p- istifadəçi tərəfindən müəyyən edilmiş parametrlər. Parametr səh ayrı-ayrı koordinatlar, parametr üzərində fərqlərin tədricən çəkisi üçün cavabdehdir r obyektlər arasında böyük məsafələrin mütərəqqi çəkisi üçün. Hər iki variant varsa r Və səh ikiyə bərabərdir, onda bu məsafə Evklid məsafəsi ilə üst-üstə düşür.
Razılaşma faizi məlumatlar kateqoriyalı olduqda istifadə olunur. Bu məsafə (4.6) düsturu ilə hesablanır.
(4.6)
Qoşulun və ya əlaqə üsulları
Birinci mərhələdə, hər bir obyekt ayrıca klaster olduqda, bu obyektlər arasındakı məsafələr seçilmiş ölçü ilə müəyyən edilir. Bununla belə, bir neçə obyekt bir-birinə bağlandıqda, klasterlər arasındakı məsafəni müəyyən etmək üçün başqa üsullardan istifadə edilməlidir. Klasterlərə qoşulmaq üçün bir çox üsul var:
Tək keçid (ən yaxın qonşu metodu) - iki klaster arasındakı məsafə müxtəlif klasterlərdə ən yaxın iki obyekt (ən yaxın qonşu) arasındakı məsafə ilə müəyyən edilir.
Tam əlaqə (ən uzaq qonşu metodu) - klasterlər arasındakı məsafələr müxtəlif klasterlərdəki hər hansı iki obyekt arasındakı ən böyük məsafə ilə müəyyən edilir (yəni "ən uzaq qonşular").
Çəkisiz cüt orta - iki müxtəlif klaster arasındakı məsafə onlarda olan bütün cüt obyektlər arasındakı orta məsafə kimi hesablanır.
Çəkili cüt orta – metod metodla eynidir çəkisiz cüt orta, istisna olmaqla, hesablamalarda çəki əmsalı kimi müvafiq klasterlərin ölçüsü (yəni, onların tərkibində olan obyektlərin sayı) istifadə olunur.
Çəkisiz mərkəz üsulu - iki çoxluq arasındakı məsafə onların ağırlıq mərkəzləri arasındakı məsafə kimi müəyyən edilir.
Çəkili mərkəz üsulu (median) - üsul çəkisiz mərkəz üsulu ilə eynidir, istisna olmaqla, hesablamalarda çoxluqların ölçüləri (yəni, onlarda olan obyektlərin sayı) arasındakı fərqi nəzərə almaq üçün çəkilərdən istifadə olunur.
Ward metodu - klasterlər arasındakı məsafə obyektlərin birləşməsi nəticəsində əldə edilən çoxluqların mərkəzlərinə kvadrat məsafələrinin cəminin artması kimi müəyyən edilir. Metod bütün digər metodlardan fərqlidir, çünki klasterlər arasındakı məsafələri qiymətləndirmək üçün ANOVA metodlarından istifadə edir. Metod hər addımda formalaşa bilən hər hansı iki (hipotetik) klaster üçün kvadratların cəmini minimuma endirir.
Ən yaxın qonşu metodu
İki sinif arasındakı məsafə onların ən yaxın üzvləri arasındakı məsafə kimi müəyyən edilir.
Alqoritmə başlamazdan əvvəl hesablanır məsafə matrisi obyektlər arasında. Təsnifat meyarına görə, birləşmə ən yaxın nümayəndələri arasındakı məsafə ən kiçik olan klasterlər arasında baş verir: bir klasterə ən kiçik məsafəyə malik iki obyekt seçilir. Bundan sonra, yeni klaster nəzərə alınmaqla məsafə matrisini yenidən hesablamaq lazımdır. Hər addımda məsafə matrisi ən yaxın iki çoxluq arasındakı məsafəyə uyğun gələn minimum dəyər üçün axtarılır. Tapılan klasterlər yeni klaster yaratmaq üçün birləşdirilir. Bu prosedur bütün klasterlər birləşdirilənə qədər təkrarlanır.
Ən yaxın qonşu metodundan istifadə edərkən, obyektlər arasında məsafə ölçüsünün seçilməsinə xüsusi diqqət yetirilməlidir. Bunun əsasında bütün sonrakı təsnifat prosesini təyin edən ilkin məsafə matrisi formalaşır.
iterativ üsullar.
Çox sayda müşahidə ilə, klaster analizinin iyerarxik üsulları uyğun deyil. Belə hallarda orijinal klasterlərin digər klasterlərə bölünməsinə əsaslanan və ilkin populyasiyanın parçalanması üçün iterativ üsullar olan qeyri-ierarxik üsullardan istifadə olunur. Bölmə prosesi zamanı dayandırma qaydası yerinə yetirilənə qədər yeni klasterlər formalaşır.
Bu cür qeyri-ierarxik klasterləşmə verilənlər toplusunun müəyyən sayda fərqli klasterlərə bölünməsindən ibarətdir. İki yanaşma var. Birincisi, klasterlərin sərhədlərini ilkin verilənlərin çoxölçülü məkanında ən sıx sahələr kimi müəyyən etmək, yəni böyük “nöqtə klasterinin” olduğu klasterin tərifi. İkinci yanaşma obyekt fərqinin ölçüsünü minimuma endirməkdir.
İerarxik təsnifat metodlarından fərqli olaraq, iterativ üsullar bir obyektin eyni vaxtda bir neçə klasterə aid ola bildiyi halda üst-üstə düşən klasterlərin yaranmasına səbəb ola bilər.
İterativ üsullara, məsələn, metod daxildir k-orta göstəricilər, konsentrasiyaların axtarışı üsulu və s. İterativ üsullar sürətlidir ki, bu da onlardan ilkin məlumatların böyük massivlərini emal etmək üçün istifadə etməyə imkan verir.
Alqoritm k-orta (k-vasitəsi)
İterativ üsullar arasında ən populyar üsul metoddur k- orta McKean. İerarxik metodlardan fərqli olaraq, bu metodun əksər tətbiqlərində istifadəçi özü adətən işarələnən son klasterlərin istənilən sayını göstərməlidir. k". Alqoritm k- orta quruluşlar k klasterlər mümkün qədər bir-birindən uzaqda yerləşir. Alqoritmin həll etdiyi problemlərin növü üçün əsas tələb k-orta göstəricilər - klasterlərin sayı ilə bağlı fərziyyələrin (fərziyyələrin) olması, halbuki onlar mümkün qədər fərqli olmalıdır. Nömrə seçimi kəvvəlki tədqiqatlara, nəzəri mülahizələrə və ya intuisiyaya əsaslana bilər.
İerarxik klasterləşdirmə metodlarında olduğu kimi, istifadəçi bu və ya digər oxşarlıq ölçülərini seçə bilər. Fərqli metod alqoritmləri k-verilmiş klasterlərin ilkin mərkəzlərinin seçilmə üsuluna görə orta göstəricilər də fərqlənir. Metodun bəzi versiyalarında istifadəçinin özü belə ilkin nöqtələri ya real müşahidələrdən seçməklə, ya da dəyişənlərin hər biri üçün bu nöqtələrin koordinatlarını təyin etməklə müəyyən edə bilər (ya da etməlidir). Bu metodun digər tətbiqlərində verilmiş bir nömrənin seçilməsi k ilkin nöqtələr təsadüfi istehsal olunur və bu ilkin nöqtələr (klaster mərkəzləri) sonradan bir neçə mərhələdə dəqiqləşdirilə bilər. Belə metodların 4 əsas mərhələsi var:
seçilmiş və ya təyin edilmişdir k klasterlərin əsas mərkəzləri olacaq müşahidələr;
zərurət yarandıqda, hər bir müşahidənin ən yaxın müəyyən edilmiş klaster mərkəzlərinə təyin edilməsi yolu ilə ara klasterlər formalaşdırılır;
bütün müşahidələr ayrı-ayrı klasterlərə təyin edildikdən sonra ilkin klaster mərkəzləri klaster orta göstəriciləri ilə əvəz olunur;
klaster mərkəzlərinin koordinatlarında dəyişikliklər minimal olana qədər əvvəlki iterasiya təkrarlanır.
Alqoritmin ümumi ideyası: müəyyən edilmiş sabit sayda k müşahidə klasterləri elə klasterlərlə müqayisə edilir ki, klasterdəki ortalamalar (bütün dəyişənlər üçün) bir-birindən mümkün qədər fərqlənsin.
Alqoritmin təsviri
Obyektlərin klasterlər üzrə ilkin paylanması.
Seçilmiş nömrə k Və k xal. Birinci mərhələdə bu nöqtələr klasterlərin “mərkəzi” hesab olunur. Hər bir klaster bir mərkəzə uyğun gəlir. İlkin centroidlərin seçimi aşağıdakı kimi həyata keçirilə bilər:
seçim k- ilkin məsafəni maksimuma çatdırmaq üçün müşahidələr;
təsadüfi seçim k- müşahidələr;
ilk seçim k- müşahidələr.
Sonra hər bir obyekt müəyyən bir ən yaxın klasterə təyin edilir.
İterativ proses.
Klasterlərin mərkəzləri hesablanır, sonra və sonra çoxluqların koordinat vasitələri hesab olunur. Obyektlər yenidən bölüşdürülür. Mərkəzlərin hesablanması və obyektlərin yenidən bölüşdürülməsi prosesi aşağıdakı şərtlərdən biri yerinə yetirilənə qədər davam edir:
klaster mərkəzləri sabitləşib, yəni bütün müşahidələr cari iterasiyadan əvvəl aid olduqları klasterə aiddir. Bu metodun bəzi versiyalarında istifadəçi meyarın ədədi dəyərini təyin edə bilər ki, bu da yeni klaster mərkəzlərinin seçilməsi üçün minimum məsafə kimi şərh olunur. Müşahidə namizədi kimi qəbul edilməyəcək yeni mərkəz klaster, onun klasterin dəyişdirilmiş mərkəzinə olan məsafəsi göstərilən nömrədən çox olarsa. Bir sıra proqramlarda belə bir parametr "radius" adlanır. Bu parametrə əlavə olaraq, bütün klaster mərkəzləri üçün məsafənin dəyişməsinin müqayisə edildiyi adətən kifayət qədər kiçik bir rəqəm təyin etmək mümkündür. Bu parametr adətən “konvergensiya” adlanır, çünki o, təkrarlanan klasterləşmə prosesinin yaxınlaşmasını əks etdirir;
təkrarların sayı təkrarların maksimum sayına bərabərdir.
Klasterləşmənin keyfiyyətinin yoxlanılması
üsulla klaster analizinin nəticələrini əldə etdikdən sonra k- orta hesabla, klasterləşmənin düzgünlüyünü yoxlamaq lazımdır (yəni, klasterlərin bir-birindən necə fərqləndiyini qiymətləndirin). Bunun üçün hər klaster üçün orta dəyərlər hesablanır. Yaxşı qruplaşma bütün ölçmələr və ya ən azı onların əksəriyyəti üçün çox fərqli vasitələr yaratmalıdır.
Üstünlüklərk-alqoritmi deməkdir:
istifadə rahatlığı;
istifadə sürəti;
alqoritmin aydınlığı və şəffaflığı.
Qüsurlark-alqoritmi deməkdir:
alqoritm ortanı təhrif edə bilən kənar göstəricilərə çox həssasdır. Bu problemin mümkün həlli alqoritmin modifikasiyasından - alqoritmdən istifadə etməkdir k- medianlar;
alqoritm böyük verilənlər bazalarında yavaş ola bilər. Bu problemin mümkün həlli məlumatların seçilməsindən istifadə etməkdir.
Hesabatda aşağıdakılar olmalıdır:
alqoritmlərin təsviri və blok-sxemləri;
proqram modullarının mənbə mətnləri;
alqoritmlərin nəticələrini qrafiklər şəklində.
Bu üsulların mahiyyəti ondan ibarətdir ki, təsnifat prosesi bəzi ilkin şərtlərin (təşəkkül edən klasterlərin sayı, təsnifat prosesini başa çatdırmaq üçün həddi və s.) müəyyən edilməsi ilə başlayır. Klaster analizinin iterativ üsullarına metod daxildir k-ortalar (McQueen), konsentrasiyaların axtarışı üsulu, qarşılıqlı udma üsulu və s. .
k-vasitə üsulu
Bu metodu həyata keçirmək üçün əvvəlcə obyektlərin mövcud kolleksiyasını bölmək lazım olan siniflərin sayı müəyyən edilir. İlkin şərtləri təyin etmək üçün hər ikisinin olması lazımdır Əlavə informasiya klasterlərin sayı haqqında məlumat verin və ya iyerarxik klaster prosedurlarından istifadə edərək klasterlərin sayını ilkin olaraq qiymətləndirin.
Təsnifat proseduruna başlamaq üçün təyin edin R təsadüfi seçilmiş obyektlər - sinif standartları ( ε ). Hər bir standarta seriya nömrəsi verilir ki, bu da eyni zamanda sinif nömrəsidir. Qalanlardan n-səh obyektlər, obyekt çıxarılır və standartlardan hansına daha yaxın olduğu yoxlanılır. Bu obyekt məsafəsi ən kiçik olan standarta əlavə olunur. Çəkilər və sinif standartları qaydaya uyğun olaraq yenidən hesablanır:
sinfin "çəkisi" haradadır, iterasiya nömrəsidir.
Bu zaman tədqiq olunan əhalinin təsadüfi seçilmiş nöqtələrindən istifadə etməklə sıfıra yaxınlaşma qurulur: , , .
vasitəsilə n-səh iterasiyalar, bütün obyektlər birinə təyin ediləcək səh klasterlər. Sabit bir bölməyə nail olmaq üçün hamısı n obyektlər yenidən bölünür səh siniflər. Yeni bölmə əvvəlki ilə müqayisə edilir. Əgər onlar uyğun gəlirsə, o zaman alqoritm dayandırılır, əks halda alqoritm təkrarlanır.
Kondensasiya axtarış metodu
Bu iterativ alqoritmin mahiyyəti nöqtələrin lokal konsentrasiyalarını axtarmaq üçün təsnifat xüsusiyyətləri məkanında hərəkət edən verilmiş radiuslu hipersferdən istifadə etməkdir.
Konsentrasiyaların axtarışı üsulu obyektlər arasında məsafə matrisinin (oxşarlıq ölçüləri matrisi) hesablanmasını tələb edir. Sonra birinci klasterin ilkin mərkəzi olan obyekt seçilir. Seçilmiş nöqtə verilmiş radiuslu hipersferin mərkəzi kimi qəbul edilir. Bu sferanın içərisinə düşən nöqtələr dəsti müəyyən edilir və onlar üçün mərkəzin koordinatları hesablanır (xüsusiyyətlərin orta qiymətlərinin vektoru). Sonra yenə eyni radiuslu, lakin yeni mərkəzi olan hipersferi nəzərdən keçiririk və ona düşən nöqtələr çoxluğu üçün yenidən orta qiymətlərin vektorunu hesablayırıq, onu sferanın yeni mərkəzi kimi götürürük və s. haqqında. Sferanın mərkəzinin koordinatlarının növbəti yenidən hesablanması əvvəlki addımda olduğu kimi eyni nəticəyə səbəb olduqda, kürənin hərəkəti dayanır və ona düşən nöqtələr çoxluq təşkil edir və sonrakı klasterləşmə prosesindən kənarlaşdırılır. Bütün qalan nöqtələr üçün prosedurlar təkrarlanır, yəni radius sferasının ilkin mərkəzi olan ixtiyari obyekt yenidən seçilir və s.
Beləliklə, alqoritmin işi sonlu sayda addımlarla tamamlanır və bütün nöqtələr klasterlər üzərində paylanır. Yaranan klasterlərin sayı əvvəlcədən məlum deyil və sferanın radiusunun seçimindən çox asılıdır. Alqoritmin bəzi modifikasiyaları sferanın radiusunu ardıcıl olaraq dəyişdirməklə çoxluğu verilmiş sayda klasterlərə bölməyə imkan verir.
Yaranan bölmənin sabitliyini qiymətləndirmək üçün, hər dəfə radiusu az miqdarda dəyişdirərək, sferanın radiusunun müxtəlif dəyərləri üçün klasterləşdirmə prosesini bir neçə dəfə təkrarlamaq məsləhətdir.
Sferanın radiusunu seçməyin bir neçə yolu var. Əgər -ci və -ci obyektlər arasındakı məsafədirsə, radiusun aşağı həddi kimi , seçilir və radiusun yuxarı həddi kimi müəyyən edilə bilər.
Əgər alqoritm dəyərlə başlayırsa və hər dəfə təkrarlananda kiçik bir dəyərlə dəyişirsə, o zaman eyni sayda klasterin yaranmasına, yəni sabitliyə səbəb olan radiusların qiymətlərini müəyyən etmək olar. bölmə.
Qarşılıqlı udma üsulu
İterativ qarşılıqlı udma alqoritmi də hipersfera ideyasından istifadə edir. Onun mahiyyəti ondan ibarətdir ki, hər biri üçün i ci obyekt, onun radiusu, məsələn, aşağıdakı kimi müəyyən edilir: , burada bəzi seçilmiş qiymət, bütün nöqtələr üçün sabit, .
Radiuslu kürələr mərkəzləri () nöqtələrində qurulur. Bu sferaların mərkəzlərini ehtiva edən nöqtələrdə qurulmuş radiuslu kürələrin kəsişmə sahəsinə qarşılıqlı udma bölgəsi deyilir. Və bu sahəyə düşən kürələrin mərkəzlərinin çoxluğuna klaster deyilir.
Dəyəri dəyişdirərək bölməni bir neçə dəfə təkrarlamaq mümkündür. Problemin son həlli olaraq, ən sabit kimi bir neçə dəyər üçün qorunan bölmə seçimini seçmək lazımdır.
Məqsədindən asılı olaraq klaster analizinin bütün vəzifələri aşağıdakı meyarlara görə bölünə bilər:
Təsnifat tapşırıqlarının bu cür ayrılması şərti olsa da, klaster prosedurlarının qurulduğu ideyalar və metodlardakı əsas fərq baxımından çox zəruridir. Beləliklə, iyerarxik klaster prosedurları əsasən bu tipli problemlərin həlli üçün nəzərdə tutulub A1B1, A1B2, A1B3, iterativ klaster prosedurları - A2B1, A2B2.