Klasterləşdirmə metodu obyektlər toplusunu elə qruplaşdırmaq tapşırığıdır ki, onlar eyni qrupdakı digər sənaye obyektlərinə nisbətən bir-birinə daha çox bənzəsinlər. Bu, məlumatların öyrənilməsinin əsas vəzifəsi və maşın öyrənməsi, nümunənin tanınması, təsvirin tanınması, məlumat axtarışı, məlumatların sıxılması və kompüter qrafikası da daxil olmaqla bir çox sahələrdə istifadə edilən ümumi statistik analiz texnikasıdır.
Optimallaşdırma problemi
Klasterləşdirmə metodunun özü bir xüsusi alqoritm deyil, həll edilməli olan ümumi tapşırıqdır. Buna qrupun nədən ibarət olduğunu anlamaqda və onu necə səmərəli şəkildə tapmaqda əhəmiyyətli dərəcədə fərqlənən müxtəlif alqoritmlərlə nail olmaq olar. Metasubyektlərin formalaşması üçün klasterləşmə metodunun istifadəsi ilə bir qrupun istifadə edilməsi daxildirüzvlər arasında kiçik məsafələr, məkanın sıx bölgələri, intervallar və ya müəyyən statistik paylanmalar. Buna görə də, klasterləşdirmə çoxməqsədli optimallaşdırma problemi kimi formalaşdırıla bilər.
Müvafiq metod və parametr parametrləri (istifadə ediləcək məsafə funksiyası, sıxlıq həddi və ya gözlənilən klasterlərin sayı kimi elementlər daxil olmaqla) fərdi məlumat dəstindən və nəticələrin nəzərdə tutulan istifadəsindən asılıdır. Təhlil avtomatik tapşırıq deyil, biliklərin kəşfi və ya interaktiv çoxməqsədli optimallaşdırmanın iterativ prosesidir. Bu qruplaşdırma metoduna sınaq və səhv cəhdləri daxildir. Nəticə istənilən xassələrə nail olana qədər məlumatların əvvəlcədən işlənməsini və model parametrlərini dəyişdirmək çox vaxt lazımdır.
"Klasterləşmə" termininə əlavə olaraq, avtomatik təsnifat, ədədi taksonomiya, botriologiya və tipoloji analiz daxil olmaqla, oxşar mənaları olan bir sıra sözlər var. İncə fərqlər tez-tez metasubject əlaqələri yaratmaq üçün klaster metodunun istifadəsində olur. Məlumatların çıxarılması zamanı yaranan qruplar maraq doğursa da, avtomatik təsnifatda artıq bu funksiyaları yerinə yetirən ayrı-seçkilik gücüdür.
Klaster təhlili 1932-ci ildə Kroeberin çoxsaylı əsərlərinə əsaslanırdı. 1938-ci ildə Zubin və 1939-cu ildə Robert Tryon tərəfindən psixologiyaya daxil edilmişdir. Və bu əsərlər 1943-cü ildən Cattell tərəfindən klasterləşdirmə üsullarının nəzəriyyədə təsnifatını göstərmək üçün istifadə edilmişdir.
Müddət
"Klaster" anlayışını dəqiq müəyyən etmək mümkün deyil. Bu, çoxlu klaster metodlarının olmasının səbəblərindən biridir. Ümumi məxrəc var: məlumat obyektləri qrupu. Bununla belə, müxtəlif tədqiqatçılar fərqli modellərdən istifadə edirlər. Və klasterləşdirmə metodlarının bu istifadələrinin hər biri müxtəlif məlumatları ehtiva edir. Müxtəlif alqoritmlər tərəfindən tapılan konsepsiya öz xüsusiyyətlərinə görə əhəmiyyətli dərəcədə fərqlənir.
Klasterləşdirmə metodundan istifadə təlimatlar arasındakı fərqləri başa düşmək üçün açardır. Tipik klaster nümunələrinə aşağıdakılar daxildir:
- Centroid s. Bu, məsələn, k-means klasterləşməsi hər klasteri bir orta vektorla təmsil etdiyi zamandır.
- Qoşulma modeli s. Bu, məsələn, məsafə əlaqəsinə əsaslanan modellər quran iyerarxik qruplaşmadır.
- Paylaşma modeli s. Bu halda, klasterlər metamövzu üzrə statistik paylanmaları formalaşdırmaq üçün klasterləşdirmə metodundan istifadə etməklə modelləşdirilir. Gözləmənin maksimumlaşdırılması alqoritminə tətbiq olunan çoxdəyişənli normal ayırma kimi.
- Sıxlıq modeli s. Bunlar, məsələn, DBSCAN (Səs-küy ilə Məkan Klasterləşdirmə Alqoritmi) və OPTICS (Strukturun Aşkarlanması üçün Sifariş Nöqtələri) klasterləri məlumat məkanında əlaqəli sıx bölgələr kimi müəyyən edir.
- Alt kosmos modeli c. İki qruplaşmada (həmçinin birgə qruplaşma və ya iki rejim kimi tanınır) qruplar hər iki element və müvafiq atributlarla modelləşdirilir.
- Model s. Bəzi alqoritmlər yoxdurmeta-mövzu nəticələrini yaratmaq və sadəcə olaraq məlumat qruplaşdırılmasını təmin etmək üçün onların klasterləşdirmə metodu üçün dəqiqləşdirilmiş əlaqə.
- Qrafikə əsaslanan model. Klik, yəni qovşaqların alt çoxluğu, kənar hissədəki hər iki əlaqə klaster formasının prototipi hesab edilə bilər. Ümumi tələbin zəifləməsi kvazi-kliklər kimi tanınır. Eyni ad HCS qruplaşdırma alqoritmində təqdim olunur.
- Neyro modellər s. Ən məşhur nəzarətsiz şəbəkə özünü təşkil edən xəritədir. Məhz bu modellər adətən meta-mövzu nəticələrinin formalaşması üçün yuxarıda göstərilən klasterləşdirmə metodlarından birinə və ya bir neçəsinə oxşar kimi xarakterizə edilə bilər. Bu, neyron şəbəkələri əsas və ya müstəqil komponent analizinin zəruri formasını həyata keçirdikdə alt kosmos sistemlərini əhatə edir.
Bu termin, əslində, adətən verilənlərin klasterləşdirmə metodları dəstindəki bütün obyektləri ehtiva edən belə qruplar toplusudur. Bundan əlavə, bir-birinə qurulmuş sistemlərin iyerarxiyası kimi klasterlərin bir-biri ilə əlaqəsini göstərə bilər. Qruplaşdırma aşağıdakı aspektlərə bölünə bilər:
- Hard centroid klaster üsulu. Burada hər bir obyekt qrupa aiddir və ya qrupdan kənardır.
- Yumşaq və ya qeyri-səlis sistem. Bu nöqtədə hər bir obyekt artıq müəyyən dərəcədə istənilən klasterə aiddir. O, həmçinin c-mənalı qeyri-səlis klasterləşdirmə metodu adlanır.
Və daha incə fərqlər də mümkündür. Məsələn:
- Ciddi bölmə qruplaşması. Budurhər bir obyekt tam olaraq bir qrupa aiddir.
- İddialılarla ciddi bölmə qruplaşması. Bu halda, obyektlər də heç bir klasterə aid olmaya və lazımsız hesab edilə bilər.
- Üst-üstə düşən qruplaşma (həmçinin alternativ, çoxsaylı baxışlarla). Burada obyektlər birdən çox budağa aid ola bilər. Adətən bərk klasterləri əhatə edir.
- İyerarxik klasterləşdirmə üsulları. Alt qrupa aid olan obyektlər də əsas alt sistemə aiddir.
- Alt fəzanın formalaşması. Üst-üstə düşən klasterlərə bənzər olsa da, unikal müəyyən edilmiş sistem daxilində qarşılıqlı qruplar üst-üstə düşməməlidir.
Təlimatlar
Yuxarıda qeyd edildiyi kimi, klasterləşdirmə alqoritmləri onların klaster modelinə əsasən təsnif edilə bilər. Aşağıdakı baxış bu təlimatların yalnız ən görkəmli nümunələrini sadalayacaqdır. 100-dən çox dərc edilmiş alqoritm ola bildiyinə görə, hamısı öz klasterləri üçün model təmin etmir və buna görə də asanlıqla təsnif edilə bilməz.
Obyektiv olaraq düzgün klasterləşdirmə alqoritmi yoxdur. Ancaq yuxarıda qeyd edildiyi kimi, göstəriş həmişə müşahidəçinin baxış sahəsindədir. Müəyyən bir problem üçün ən uyğun klaster alqoritmi, bir modeli digərindən üstün tutmaq üçün riyazi səbəb olmadığı halda, çox vaxt eksperimental olaraq seçilməlidir. Qeyd etmək lazımdır ki, bir növ üçün nəzərdə tutulmuş alqoritm adətən işləmirkökündən fərqli bir mövzu ehtiva edən verilənlər toplusu. Məsələn, k-vasitələr qabarıq olmayan qrupları tapa bilməz.
Əlaqə əsaslı qruplaşma
Bu birlik həm də iyerarxik model adı ilə tanınır. Bu tipik fikrə əsaslanır ki, obyektlər çox uzaqda olanlardan daha çox qonşu hissələrlə bağlıdır. Bu alqoritmlər obyektləri birləşdirir, onların məsafəsindən asılı olaraq müxtəlif klasterlər yaradır. Qrup əsasən klasterin müxtəlif hissələrini birləşdirmək üçün lazım olan maksimum məsafə ilə təsvir edilə bilər. Bütün mümkün məsafələrdə dendroqramdan istifadə etməklə təmsil oluna bilən digər qruplar yaranacaq. Bu, "ierarxik qruplaşma" ümumi adının haradan gəldiyini izah edir. Yəni, bu alqoritmlər verilənlər toplusunun tək bölməsini təmin etmir, əksinə geniş səlahiyyət sırasını təmin edir. Məhz onun sayəsində müəyyən məsafələrdə bir-biri ilə drenaj var. Dendroqramda y oxu çoxluqların birləşdiyi məsafəni bildirir. Obyektlər X xətti boyunca düzülüb ki, qruplar bir-birinə qarışmasın.
Bağlantıya əsaslanan klasterləşdirmə məsafələri hesablama üsulu ilə fərqlənən bütün üsullar ailəsidir. Məsafə funksiyalarının adi seçiminə əlavə olaraq, istifadəçi də əlaqə meyarına qərar verməlidir. Klaster bir neçə obyektdən ibarət olduğundan, onu hesablamaq üçün bir çox variant var. Məşhur seçim tək qollu qruplaşdırma kimi tanınır, bu üsuldurUPGMA və ya WPGMA-dan ibarət tam keçid (arifmetik orta ilə ölçülməmiş və ya çəkilmiş cütlər ansamblı, həmçinin orta keçid qruplaşması kimi tanınır). Bundan əlavə, iyerarxik sistem aqlomerativ (ayrı-ayrı elementlərdən başlayaraq və onları qruplara birləşdirən) və ya bölmə (tam məlumat dəstindən başlayaraq onu bölmələrə bölmək) ola bilər.
Paylanmış klasterləşdirmə
Bu modellər bölünmələrə əsaslanan statistika ilə ən yaxından əlaqəlidir. Klasterlər asanlıqla eyni paylanmaya aid olan obyektlər kimi müəyyən edilə bilər. Bu yanaşmanın əlverişli xüsusiyyəti ondan ibarətdir ki, o, süni verilənlər dəstlərinin yaradılması üsuluna çox oxşardır. Paylanmadan təsadüfi obyektlərin seçilməsi ilə.
Bu metodların nəzəri əsasları əla olsa da, modelin mürəkkəbliyinə məhdudiyyətlər qoyulmadıqda, onlar həddindən artıq uyğunlaşma kimi tanınan bir əsas problemdən əziyyət çəkirlər. Daha böyük assosiasiya adətən məlumatları daha yaxşı izah edərək düzgün metodu seçməyi çətinləşdirir.
Qauss qarışığı modeli
Bu üsul bütün növ gözləntilərin maksimumlaşdırılması alqoritmlərindən istifadə edir. Burada verilənlər bazası adətən təsadüfi olaraq işə salınan və parametrləri verilənlər bazasına daha yaxşı uyğunlaşmaq üçün iterativ olaraq optimallaşdırılan sabit sayı (əsl üstünlük verməmək üçün) Qauss paylamaları ilə modelləşdirilir. Bu sistem yerli optimala yaxınlaşacaq. Buna görə bir neçə qaçış verə bilərmüxtəlif nəticələr. Ən sıx klasterləşməni əldə etmək üçün xüsusiyyətlər çox vaxt aid olduqları Gauss paylanmasına təyin edilir. Daha yumşaq qruplar üçün bu lazım deyil.
Paylaşmaya əsaslanan klasterləşdirmə atributlar arasında korrelyasiya və asılılığı əldə edə bilən mürəkkəb modellər yaradır. Lakin bu alqoritmlər istifadəçiyə əlavə yük qoyur. Bir çox real dünya verilənlər bazası üçün qısa şəkildə müəyyən edilmiş riyazi model olmaya bilər (məsələn, Qauss paylanmasının kifayət qədər güclü fərziyyə olduğunu fərz etsək).
Sıxlığa əsaslanan qruplaşma
Bu misalda qruplar əsasən məlumat dəstinin qalan hissəsinə nisbətən daha yüksək keçiriciliyə malik sahələr kimi müəyyən edilmişdir. Bütün komponentləri ayırmaq üçün zəruri olan bu nadir hissələrdə olan obyektlər adətən səs-küy və kənar nöqtələr hesab olunur.
Ən məşhur sıxlığa əsaslanan klasterləşdirmə üsulu DBSCAN-dır (Spatial Noise Clustering Alqoritmi). Bir çox yeni üsullardan fərqli olaraq, o, "sıxlıq əldə etmək imkanı" adlı yaxşı müəyyən edilmiş çoxluq komponentinə malikdir. Bağlantı əsaslı klasterləşməyə bənzər şəkildə, o, müəyyən məsafə həddində olan əlaqə nöqtələrinə əsaslanır. Bununla belə, bu üsul yalnız sıxlıq meyarına cavab verən elementləri toplayır. Bu radiusda digər obyektlərin minimum sayı kimi müəyyən edilən orijinal versiyada klaster bütün elementlərdən ibarətdir.sıxlıqla əlaqəli elementlər (bir çox digər üsullardan fərqli olaraq sərbəst forma qrupu yarada bilər) və icazə verilən diapazonda olan bütün obyektlər.
DBSCAN-ın digər maraqlı xüsusiyyəti ondan ibarətdir ki, onun mürəkkəbliyi kifayət qədər aşağıdır - o, verilənlər bazasına qarşı xətti sayda diapazon sorğuları tələb edir. Həm də qeyri-adi odur ki, o, hər qaçışda mahiyyətcə eyni nəticələri tapacaq (bu, əsas və səs-küy nöqtələri üçün deterministikdir, lakin sərhəd elementləri üçün deyil). Buna görə də, onu bir neçə dəfə işə salmağa ehtiyac yoxdur.
DBSCAN və OPTICS-in əsas çatışmazlığı ondan ibarətdir ki, onlar klaster sərhədlərini aşkar etmək üçün sıxlığın müəyyən qədər azalmasını gözləyirlər. Məsələn, üst-üstə düşən Qauss paylamaları olan verilənlər dəstlərində - süni obyektlər üçün ümumi istifadə halı - bu alqoritmlər tərəfindən yaradılan klaster sərhədləri çox vaxt ixtiyari görünür. Bu, qrupların sıxlığının davamlı olaraq azalması ilə baş verir. Qauss qarışığı verilənlər bazasında isə bu alqoritmlər demək olar ki, həmişə bu tip sistemləri dəqiq şəkildə modelləşdirməyə qadir olan EM klasterləşdirmə kimi metodlardan üstündür.
Orta yerdəyişmə hər bir obyektin bütün nüvənin təxmininə əsaslanaraq qonşuluqdakı ən sıx sahəyə hərəkət etdiyi qruplaşma yanaşmasıdır. Sonda obyektlər yerli keçilməzlik maksimumlarına yaxınlaşır. k-vasitəsilə qruplaşmaya bənzər, bu "sıxlıq cəlbediciləri" verilənlər bazası üçün nümayəndə kimi xidmət edə bilər. Amma orta yerdəyişməDBSCAN-a bənzər ixtiyari formalı klasterləri aşkar edə bilər. Bahalı iterativ prosedura və sıxlığın qiymətləndirilməsinə görə, orta yerdəyişmə adətən DBSCAN və ya k-Means-dan daha yavaş olur. Bundan əlavə, yüksək ölçülü məlumatlara tipik yerdəyişmə alqoritminin tətbiqi nüvə sıxlığı təxmininin qeyri-bərabər davranışı səbəbindən çətindir və bu, klaster quyruqlarının həddindən artıq parçalanmasına səbəb olur.
Reytinq
Klasterləşdirmə nəticələrini yoxlamaq klasterləşdirmənin özü qədər çətindir. Populyar yanaşmalara “daxili” qiymətləndirmə (burada sistemin vahid keyfiyyət ölçüsünə endirilməsi) və təbii ki, “xarici” qiymətləndirmə (klasterləşmənin mövcud “əsas həqiqət” təsnifatı ilə müqayisə edildiyi) daxildir. Və insan ekspertin əl ilə balı və dolayı balı nəzərdə tutulan tətbiqdə klasterləşdirmənin faydalılığını yoxlayaraq tapılır.
Daxili bayraq ölçüləri problemdən əziyyət çəkir ki, onlar özləri qruplaşma hədəfləri sayıla bilən xüsusiyyətləri təmsil edirlər. Məsələn, Silhouette əmsalı ilə verilən məlumatları qruplaşdırmaq mümkündür, lakin bunun üçün məlum effektiv alqoritm yoxdur. Qiymətləndirmə üçün belə daxili ölçüdən istifadə edərək optimallaşdırma problemlərinin oxşarlığını müqayisə etmək daha yaxşıdır.
Xarici işarənin oxşar problemləri var. Əgər belə “əsas həqiqət” etiketləri varsa, o zaman klasterləşdirməyə ehtiyac yoxdur. Praktik tətbiqlərdə isə adətən belə anlayışlar yoxdur. Digər tərəfdən, etiketlər məlumat dəstinin yalnız bir mümkün bölməsini əks etdirir, bu o demək deyilbaşqa (bəlkə də daha yaxşı) çoxluq yoxdur.
Beləliklə, bu yanaşmaların heç biri son nəticədə faktiki keyfiyyəti mühakimə edə bilməz. Ancaq bu, çox subyektiv olan insan qiymətləndirməsini tələb edir. Buna baxmayaraq, bu cür statistika pis qrupların müəyyən edilməsində məlumatlandırıcı ola bilər. Ancaq bir insanın subyektiv qiymətləndirilməsinə güzəşt edilməməlidir.
Daxili işarə
Klasterləşmənin nəticəsi klasterləşdirilmiş məlumat əsasında qiymətləndirildikdə, bu termin kimi istinad edilir. Bu üsullar ümumiyyətlə ən yaxşı nəticəni qruplar daxilində yüksək və qruplar arasında aşağı oxşarlıqlara malik qruplar yaradan alqoritmə təyin edir. Klasterin qiymətləndirilməsində daxili meyarlardan istifadənin çatışmazlıqlarından biri yüksək balların mütləq məlumat axtarışı üçün effektiv tətbiqlərə gətirib çıxarmamasıdır. Həmçinin, bu xal eyni modeli istifadə edən alqoritmlərə qarşı qərəzlidir. Məsələn, k-klasterləşdirmə xüsusiyyət məsafələrini təbii olaraq optimallaşdırır və ona əsaslanan daxili meyar çox güman ki, nəticədə yaranan klasterləşməni yüksək qiymətləndirə bilər.
Buna görə də, bu qiymətləndirmə tədbirləri bir alqoritmin digərindən daha yaxşı çıxış etdiyi vəziyyətlər haqqında fikir əldə etmək üçün ən uyğundur. Amma bu o demək deyil ki, hər bir məlumat digərlərindən daha etibarlı nəticələr verir. Belə bir indekslə ölçülən etibarlılıq müddəti strukturun verilənlər bazasında mövcud olmasının təsdiqindən asılıdır. Bəzi növlər üçün hazırlanmış bir alqoritmin, əgər çoxluq radikal ehtiva edərsə, heç bir şansı yoxdurfərqli tərkib və ya qiymətləndirmə fərqli meyarları ölçürsə. Məsələn, k-vasitəsilə qruplaşma yalnız qabarıq klasterləri tapa bilər və bir çox xal indeksləri eyni formatı qəbul edir. Qeyri-qabarıq modelləri olan verilənlər bazasında k-vasitəsi və tipik qiymətləndirmə meyarlarından istifadə etmək uyğun deyil.
Xarici qiymətləndirmə
Bu cür toplama ilə qruplaşdırma nəticələri qruplaşdırma üçün istifadə olunmayan verilənlər əsasında qiymətləndirilir. Yəni məlum sinif etiketləri və xarici testlər kimi. Belə suallar əvvəlcədən təsnif edilmiş maddələr toplusundan ibarətdir və çox vaxt ekspertlər (insanlar) tərəfindən yaradılır. Beləliklə, istinad dəstləri qiymətləndirmə üçün qızıl standart kimi görünə bilər. Bu cür qiymətləndirmə üsulları klasterləşmənin verilmiş istinad siniflərinə nə qədər yaxın olduğunu ölçür. Bununla belə, bu yaxınlarda bunun real məlumatlar üçün və ya yalnız faktiki əsas həqiqəti olan sintetik dəstlər üçün adekvat olub olmadığı müzakirə edilmişdir. Çünki siniflər daxili struktura malik ola bilər və mövcud atributlar klasterlərin ayrılmasına imkan verməyə bilər. Həmçinin, biliyin kəşfi nöqteyi-nəzərindən məlum faktların təkrar istehsalı mütləq gözlənilən nəticəni verməyə bilər. Qruplaşdırma prosesində meta-məlumatın (məsələn, sinif etiketləri kimi) artıq istifadə olunduğu xüsusi məhdudlaşdırılmış klasterləşdirmə ssenarisində qiymətləndirmə məqsədləri üçün bütün məlumatların saxlanılması əhəmiyyətsiz deyil.
İndi klasterləşdirmə metodlarına nəyin aid olmadığı və bu məqsədlər üçün hansı modellərin istifadə olunduğu aydındır.
