Metode de analiză a clusterelor. metode iterative. Tipuri de proceduri de analiză cluster Metodă de analiză cluster de căutare a concentrațiilor

analiza grupului(CLA) este un set de metode de clasificare multidimensionale, al căror scop este formarea de grupuri (clustere) de obiecte similare între ele. Spre deosebire de grupările tradiționale considerate în teoria generală a statisticii, CL conduce la împărțirea în grupuri, luând în considerare toate caracteristicile de grupare simultan.

Metodele CL permit rezolvarea următoarelor probleme:

— realizarea clasificării obiectelor, luând în considerare o varietate de caracteristici;

- verificarea ipotezelor făcute despre prezenţa unei structuri în setul de obiecte studiat, i.e. căutarea unei structuri existente;

- construirea de noi clasificări pentru fenomene slab studiate, când este necesar să se stabilească prezenţa unor legături în cadrul populaţiei şi să se încerce introducerea structurii în aceasta.

Pentru a scrie algoritmii CL formalizați, se folosesc următoarele: conventii:

– set de obiecte de observare;

– i-a observațieîn spațiul caracteristic m-dimensional ();

este distanța dintre obiectele --lea și --lea;

– valori normalizate ale variabilelor inițiale;

este matricea distanțelor dintre obiecte.

Pentru a implementa orice metodă CL, este necesar să se introducă conceptul de „asemănare obiect”. Mai mult, în procesul de clasificare, obiectele care au cea mai mare asemănare între ele în ceea ce privește variabilele observate ar trebui să se încadreze în fiecare cluster.

Pentru cuantificare similaritate, se introduce conceptul de metrică. Fiecare obiect este descris prin -trăsături și reprezentat ca un punct în spațiul -dimensional. Asemănarea sau diferența dintre obiectele clasificate se stabilește în funcție de distanța metrică dintre ele. De regulă, se folosesc următoarele măsuri ale distanței dintre obiecte:

este distanța euclidiană ;

este distanța euclidiană ponderată ;

— distanța oraș-bloc ;

este distanța Mahalanobis,

unde este distanța dintre obiectele --lea și --lea;

, sunt valorile variabilei și, respectiv, ale obiectelor -lea și -lea;

, – vectori de valori variabile pentru obiectele -lea și -lea;

este matricea generală de covarianță;

este ponderea atribuită variabilei --a.

Toate metodele CL pot fi împărțite în două grupe: ierarhice (aglomerative și divizibile) și iterative (metoda -medie, metoda de căutare a concentrațiilor).

Analiza clusterului ierarhic. Dintre toate metodele de analiză a clusterelor, cea mai comună este algoritmul de clasificare aglomerativă. Esența aglogritmului constă în faptul că, la prima etapă, fiecare obiect eșantion este considerat ca un grup separat. Procesul de combinare a clusterelor are loc secvenţial: pe baza matricei de distanţe sau a matricei de similaritate, cele mai apropiate obiecte sunt combinate. Dacă matricea distanțelor are inițial dimensiunea (), atunci procesul de îmbinare este finalizat în pași (). Ca rezultat, toate obiectele vor fi combinate într-un singur cluster.

Secvența de îmbinare poate fi reprezentată ca o dendrogramă prezentată în Figura 3.1. Dendrograma arată că la primul pas al doilea și al treilea obiect sunt combinate într-un singur grup cu o distanță între ele de 0,15. La a doua etapă, primul obiect le-a alăturat. Distanța de la prima caracteristică până la clusterul care conține a doua și a treia caracteristică, 0,3 și așa mai departe.

Multe metode de analiză a clusterelor ierarhice se disting prin algoritmi de asociere (similaritate), dintre care cei mai des întâlniți sunt: metoda conexiunii unice, metoda conexiunii complete, metoda conexiunii medii, metoda Ward.

Metoda legăturilor complete - includerea unui nou obiect în cluster are loc numai dacă asemănarea dintre toate obiectele nu este mai mică decât un anumit nivel de similaritate (Figura 1.3).

Metoda medie de conectare - atunci când un obiect nou este inclus într-un cluster existent, se calculează valoarea medie a măsurătorii de similaritate, care este apoi comparată cu un anumit nivel de prag. Dacă vorbim despre unirea a două clustere, atunci se calculează măsura similitudinii dintre centrele lor și se compară cu o anumită valoare de prag. Luați în considerare un exemplu geometric cu două grupuri (Figura 1.4).

Figura 1.4. Combinând două grupuri folosind metoda link-ului mediu:

Dacă măsura asemănării dintre centrele clusterelor () nu este mai mică decât un anumit nivel, atunci clusterele și vor fi fuzionate într-unul singur.

Metoda lui Ward - la primul pas, fiecare grup este format dintr-un obiect. Inițial, cele mai apropiate două grupuri sunt fuzionate. Pentru ei, se determină valorile medii ale fiecărei caracteristici și se calculează suma abaterilor pătrate

, (1.1)

unde este numărul grupului, este numărul obiectului, este numărul caracteristicii; - numărul de trăsături care caracterizează fiecare obiect; este numărul de obiecte din -mcluster.

Mai mult, la fiecare pas al algoritmului, acele obiecte sau grupuri sunt combinate care dau cel mai mic increment al valorii .

Metoda lui Ward duce la formarea de clustere de dimensiuni aproximativ egale cu variații minime intracluster.

Algoritmul de analiză a clusterului ierarhic poate fi reprezentat ca o secvență de proceduri:

— normalizarea valorilor inițiale ale variabilelor;

— calculul matricei distanțelor sau al matricei măsurilor de similaritate;

– determinarea unei perechi de obiecte cele mai apropiate (clustere) și combinarea acestora în funcție de algoritmul selectat;

- repetarea primelor trei proceduri până când toate obiectele sunt combinate într-un singur grup.

Măsura asemănării pentru combinarea a două grupuri este determinată prin următoarele metode:

- metoda „cel mai apropiat vecin” - gradul de asemănare dintre clustere este estimat prin gradul de similaritate dintre obiectele cele mai asemănătoare (cel mai apropiate) ale acestor clustere;

— metoda „vecinului îndepărtat” - gradul de asemănare se estimează prin gradul de asemănare dintre cele mai îndepărtate (disimilare) obiecte ale clusterelor;

- metoda conexiunii medii - gradul de similaritate este estimat ca valoarea medie a gradelor de asemanare dintre obiectele clusterelor;

- metoda conexiunii mediane - distanța dintre orice cluster S și un nou cluster, care a rezultat din unirea clusterelor p și q, este definită ca distanța de la centrul clusterului S până la mijlocul segmentului care leagă centrele clusterelor p și q.

Metoda de căutare a condensului. Una dintre metodele iterative de clasificare este algoritmul de căutare a concentrațiilor. Esența algoritmului iterativ aceasta metoda constă în folosirea unei hipersfere de o rază dată, care se deplasează în spațiul caracteristicilor de clasificare pentru a căuta concentrații locale de obiecte.

Metoda de căutare a concentrațiilor necesită, în primul rând, calculul matricei distanțelor (sau matricei măsurilor de similitudine) dintre obiecte și alegerea centrului inițial al sferei. De obicei, la prima etapă, centrul sferei este obiectul (punctul), în vecinătatea cea mai apropiată din care se află cel mai mare număr de vecini. Pe baza razei date a sferei (R), se determină un set de puncte care se încadrează în interiorul acestei sfere și se calculează coordonatele centrului pentru acestea (vectorul valorilor medii ale caracteristicilor).

Când următoarea recalculare a coordonatelor centrului sferei duce la același rezultat ca în pasul precedent, mișcarea sferei se oprește, iar punctele care intră în ea formează un grup și sunt excluse din procesul de grupare ulterioară. . Procedurile de mai sus se repetă pentru toate punctele rămase. Lucrarea algoritmului este finalizată într-un număr finit de pași, iar toate punctele sunt distribuite pe grupuri. Numărul de clustere formate nu este cunoscut în prealabil și depinde puternic de raza sferei.

Pentru a evalua stabilitatea partiției rezultate, este recomandabil să repetați procesul de grupare de mai multe ori pentru diferite valori ale razei sferei, modificând de fiecare dată raza cu o cantitate mică.

Există mai multe moduri de a alege raza unei sfere. Dacă este distanța dintre obiectele --lea și --lea, atunci se alege limita inferioară a razei (), iar limita superioară a razei poate fi definită ca .

Dacă algoritmul începe cu o valoare și se modifică cu o valoare mică de fiecare dată când este repetat, atunci este posibil să se identifice valorile razelor care duc la formarea aceluiași număr de clustere, adică. la o partiție stabilă.

Exemplul 1. Pe baza datelor din Tabelul 1.1, este necesar să se clasifice cinci întreprinderi utilizând analiza cluster aglomerativă ierarhică.

Tabelul 1.1

Aici: - costul mediu anual major active de producție, miliarde de ruble; - costuri materiale pe o rublă de produse fabricate, copeici; - volumul produselor fabricate, miliarde de ruble.

Soluţie. Înainte de a calcula matricea distanțelor, normalizăm datele inițiale folosind formula

Matricea valorilor variabilelor normalizate va arăta ca

Clasificarea se va realiza prin metoda aglomerativă ierarhică. Pentru a construi matricea distanțelor, vom folosi distanța euclidiană. Apoi, de exemplu, distanța dintre primul și al doilea obiect va fi

Matricea distanțelor caracterizează distanțele dintre obiecte, fiecare dintre acestea, la primul pas, fiind un grup separat

După cum se poate vedea din matrice, obiectele și sunt cele mai apropiate. Să le combinăm într-un singur grup și să îi atribuim un număr. Recalculăm distanțele tuturor obiectelor rămase (clustere) față de cluster, obținem o nouă matrice de distanțe

În matrice, distanțele dintre clustere sunt determinate de algoritmul „vecin departe”. Atunci distanța dintre obiect și cluster este

În matrice, găsim din nou cele mai apropiate clustere. Acestea vor fi și , . Prin urmare, la acest pas, combinăm și clustere; obține un nou cluster care conține obiecte, . Să-i dăm un număr. Acum avem trei grupuri (1.3), (2.5), (4).

Judecând după matrice, la pasul următor combinăm clusterele și, într-un singur cluster și îi atribuim un număr. Acum avem doar două grupuri:

Și în final, la ultimul pas, vom combina clusterele și la o distanță de 3.861.

Să prezentăm rezultatele clasificării sub forma unei dendrograme (Figura 1.5). Dendrograma indică faptul că clusterul este mai omogen în ceea ce privește compoziția obiectelor care intră, deoarece în el uniunea a avut loc la distanțe mai mici decât în cluster.

Figura 3.5 Dendrograma grupării a cinci obiecte

Exemplul 2. Pe baza datelor de mai jos, clasificați magazinele după trei criterii: - suprafață podeaua comercială, m2 , - cifra de afaceri per vanzator, den. unități, - nivelul de rentabilitate, %.

numărul magazinului				numărul magazinului

Pentru a clasifica magazinele, utilizați metoda de căutare a concentrațiilor (trebuie să selectați primul grup).

Soluţie. 1. Calculați distanțele dintre obiecte folosind metrica euclidiană

unde , sunt valorile standardizate ale variabilelor inițiale pentru obiectele -lea și respectiv --lea; t este numărul de caracteristici.

2. Pe baza matricei Z, calculăm matricea pătrată simetrică a distanțelor dintre obiecte ().

Analiza matricei distanțelor ajută la determinarea poziției centrului inițial al sferei și la alegerea razei sferei.

În acest exemplu, majoritatea distanțelor „mici” sunt pe prima linie, adică. primul obiect are o mulțime de vecini „apropiați”. Prin urmare, primul obiect poate fi luat drept centru al sferei.

3. Setați raza sferei. În acest caz, obiectele cad în sferă, distanța căreia până la primul obiect este mai mică de 2.

Analiza cluster este o analiză statistică care vă permite să împărțiți o cantitate mare de date în clase sau grupuri (din engleză, cluster- clasa) după un criteriu sau combinarea acestora.

Pentru a clasifica datele X x,...,X p utilizați conceptul de metrică sau distanță.

metric este o funcție p care mapează un spațiu metric în spațiul numerelor reale și are următoarele proprietăți (axiome metrice):

1) p(ZD>0,
2) p(X,Y)=p(Y, X),
3) p(X, Y) = 0 X=Y
4) P(X,Y) P(Z, Y).

Teoria analizei cluster folosește următoarele metrici pentru a măsura distanța dintre punctele individuale (vectori):

1) Distanța euclidiană

2) distanța euclidiană ponderată

Unde saptamana - ponderi proporționale cu importanța caracteristicii în problema de clasificare. Greutățile sunt stabilite după cercetări suplimentare

și presupunem că ^ w* = 1;

3) distanță de haming (sau bloc)- distanța pe hartă între cartierele orașului

4) Distanța Mahalanobis (sau unghiul Mahalanobis)

unde A este o matrice de greutate simetrică pozitiv-definită (adesea aleasă să fie diagonală); DAR - matricea de covarianță vectorială X 19..., X p;

5) Distanța Minkowski

Distanțele 1), 2), 3) sau 5) sunt utilizate în cazul distribuției normale a variabilelor aleatoare independente X l9 ...,X n ~N(M,A) sau în cazul omogenității lor în sens geochimic, când fiecare vector este la fel de important pentru clasificare. Distanța 4) este utilizată dacă există o relație de covarianță a vectorilor X x,...,X P.

Alegerea metricii este efectuată de cercetător, în funcție de ce rezultat dorește să obțină. Această alegere nu este formalizată, deoarece depinde de mulți factori, în special, de rezultatul așteptat, de experiența cercetătorului, de nivelul pregătirii sale matematice etc.

Într-o serie de algoritmi, împreună cu distanțele dintre vectori, sunt utilizate distanțele dintre clustere și uniunile de clustere.

Lasa S(- /-lea cluster, format din n t vectori sau puncte. Lasa

X (l) - media eșantionului peste punctele care se încadrează în cluster S f , sau centrul de greutate al clusterului 5.. Atunci se disting următoarele distanțe între clusterele care nu au alte clustere în interior:

1) distanța dintre clustere conform principiului „vecinului apropiat”.

2) distanța dintre clustere conform principiului „vecinului îndepărtat”

3) distanța dintre centrele de greutate ale grupurilor

4) distanța dintre clustere conform principiului „conexiunii medii”

5) distanța generalizată Kolmogorov

Distanța dintre grupurile care sunt uniunea altor clase poate fi calculată folosind formula generală:

Unde S^k^- cluster obtinut prin combinarea claselor SkȘi S t .

Toate cazurile speciale de distanțe sunt obținute din această formulă generalizată. Cu a = p = 1/2, 8 = -1/2, y = 0, avem o distanță după principiul „vecinului apropiat”, cu a = p = 5 = 1/2, y = O - „departe”. vecin",

la o \u003d ---, p \u003d---, 5 \u003d 0, y \u003d 0 - distanță de-a lungul centrelor de greutate

p k + n i p k + n i

grupuri.

Metodele de analiză a grupurilor sunt împărțite în I) aglomerativ (combinare), II) divizionare (separare) și III) iterativă.

Primele combină în mod constant obiectele individuale în grupuri, cele din urmă, dimpotrivă, dezmembrăază grupurile în obiecte. Al treilea le combină pe primele două. Caracteristica lor este formarea de clustere pe baza condițiilor de partiționare (așa-numiții parametri), care pot fi modificate în timpul funcționării algoritmului pentru a îmbunătăți calitatea partiționării. Metodele iterative sunt utilizate în mod obișnuit pentru a clasifica cantități mari de informații.

Să luăm în considerare metodele aglomerative mai detaliat. Metodele aglomerative sunt cele mai simple și mai comune dintre algoritmii de analiză a clusterelor. La primul pas, fiecare vector sau obiect X 19 ..., X p datele sursă sunt considerate ca un cluster sau o clasă separată. Conform matricei de distanțe calculate, cele mai apropiate unele de altele sunt selectate și combinate. Evident, procesul se va încheia în (P - 1) un pas în care, ca rezultat, toate obiectele vor fi combinate într-un singur grup.

Secvența de asociații poate fi reprezentată ca dendrogramă sau arbore. Pe fig. 1.18 arată că vectorii au fost combinați în prima etapă X t , X 2 ,întrucât distanța dintre ele este de 0,3.

La a doua etapă, le-a fost atașat un vector X 3 departe de cluster (X 1, X 2) la o distanță de 0,5 etc. La ultimul pas, toți vectorii sunt combinați într-un singur grup.

Orez. 1.18.

Metodele aglomerative includ metode de conectare unică, medie, completă și metoda lui Ward.

1.metoda de conectare unică. Lasa X v ..., X n - date vectoriale, fiecare vector formând un grup. În primul rând, se calculează o matrice a distanțelor dintre aceste grupuri, iar distanța vecină cea mai apropiată este utilizată ca metrică. Folosind această matrice, sunt selectați cei doi vectori cei mai apropiați, care formează primul cluster 5,. Următorul pas între S]și vectorii rămași (pe care îi considerăm clustere), se calculează o nouă matrice de distanțe și distanța dintre clustere combinată în clase (a = p = 1/2, 5 = -1/2, y = 0) este folosit ca metrică. Cel mai apropiat de clasa obținută anterior S( clusterul se unește cu acesta, formând S2. etc prin P- 1 pași, obținem că toți vectorii sunt combinați într-un singur cluster.

Avantaje: 1) se adaugă un singur element la fiecare pas al algoritmului, 2) metoda este extrem de simplă, 3) algoritmul este insensibil la transformările datelor inițiale (rotație, deplasare, translație, întindere).

dezavantaje: 1) este necesar să se recalculeze constant matricea distanțelor, 2) numărul de clustere este cunoscut dinainte și nu poate fi redus

2. Metoda de conectare completă. Metoda repetă practic metoda legăturii unice, cu excepția faptului că includerea unui nou obiect într-un cluster are loc dacă și numai dacă distanța dintre obiecte (vectori sau clustere) este mai mică decât un număr predeterminat. Numărul este stabilit de utilizator. Distanța se calculează numai după principiul „vecinului îndepărtat” (același lucru se poate spune despre distanța dintre clase combinate în clase - doar principiul vecinului îndepărtat pentru os = p = 8 = 1/2, y = 0).
3.Metoda medie de conectare. Algoritmul de formare a clusterului coincide cu algoritmul de legătură unică, totuși, atunci când se decide dacă se include un obiect nou într-un cluster, calculele sunt efectuate conform principiului legăturii medii. Ca și în cazul metodei de legătură completă, toate distanțele calculate dintre clustere sunt comparate cu un număr specificat de utilizator. Și dacă aceasta (distanța) este mai mică decât un număr dat, noul obiect este inclus în clasa veche. Astfel, metoda de conectare medie diferă de metoda de conectare completă doar prin modul în care este calculată distanța dintre clustere.
4. metoda WARD. Lasa X 19 ..., X p- date, fiecare vector formând un grup. Găsim matricea distanțelor folosind o metrică (de exemplu, distanța Mahalanobis), determinăm clusterele cele mai apropiate unul de celălalt. Calculați suma abaterilor pătrate ale vectorilor din cluster Sk dupa formula:

Unde la - numărul grupului, eu- numărul vectorului din cluster, j- numărul de coordonate X t e U1 R, p la- numărul de vectori din cluster, Xjk- medie eșantionului X iîn S k . Valoare Vk caracterizează abaterile vectorilor unul față de celălalt în cadrul clusterului (nou Sk+Sf sau vechi^). Plată Vk ar trebui efectuată înainte și după unire și este necesar să parcurgem toate variantele posibile ale unor astfel de uniuni. Mai târziu în cluster Sk sunt adăugați doar acei vectori sau clustere care au ca rezultat cea mai mică modificare Vk după comasare și, ca urmare, care va fi situat la distanța minimă de clusterul original S k .

Luați în considerare alte metode iterative. Esența metodelor iterative este că gruparea începe cu stabilirea unor condiții inițiale. De exemplu, se cere setarea numărului de clustere care urmează a fi obținute sau setarea distanței care determină sfârșitul procesului de formare a clusterelor etc. Condițiile inițiale sunt alese în funcție de rezultatul de care are nevoie cercetătorul. Cu toate acestea, acestea sunt de obicei fixate în funcție de soluția găsită prin una dintre metodele aglomerative. Metodele iterative includ metoda ^-mediilor și metoda de căutare a concentrațiilor.

1. Metoda /r-înseamnă. Să fie vectori Xl9 ...,Xn e9F și trebuie împărțite în la clustere. La pasul zero al P vectorii aleg aleatoriu la dintre ele, presupunând că fiecare formează un grup. Obținem un set de clustere de referință,...,e[ 0) cu ponderi

coj 0) ,...,X. și calculați matricea distanțelor dintre X.și standardele e 1 (0),...,^ 0) conform unor metrici, de exemplu, conform Euclidianului:

Pe baza cunoștințelor matricei de distanțe calculate, vectorul X ( este plasat în standard, distanța până la care este minimă. Să presupunem pentru certitudine ce este. Se inlocuieste cu unul nou, recalculat tinand cont de punctul atasat, conform formulei

În plus, greutatea este de asemenea recalculată:

Dacă în matrice apar două sau mai multe distanțe minime, atunci X t incluse în grupul cu cel mai mic număr de ordine.

La pasul următor, următorul vector este selectat dintre cei rămași, iar procedura se repetă. Astfel, prin ( PC) pași către fiecare

standard e^~ k) se va potrivi cu greutatea și procedura de grupare se va încheia. Cu o mare P si mici la algoritmul converge rapid către o soluție stabilă, adică către o soluție în care standardele obținute după prima aplicare a algoritmului coincid ca număr și compoziție cu standardele găsite la repetarea metodei. Cu toate acestea, procedura algoritmică se repetă întotdeauna de mai multe ori, folosind ca vectori de referință partiția obținută în calculele anterioare (ca aproximare inițială): referințe găsite anterior e[ p k e (2 p k) k) luat pentru e (x 0) 9 ... 9 e (k 0) 9 iar procedura algoritmică se repetă.

2. Metoda de căutare a condensului. Acesta este următorul algoritm iterativ. Nu necesită o specificare a priori a numărului de clustere. La primul pas, matricea distanțelor dintre X X9 ... 9 X p e Y1 str conform unor metrici. Apoi un vector este ales aleatoriu pentru a juca rolul centrului primului cluster. Aceasta este aproximarea inițială. Să presupunem că acest vector se află în centrul unei sfere p-dimensionale de rază R, iar această rază este stabilită de cercetător. După aceea, vectorii sunt determinați X Si ,... 9 X Sk , prins în interiorul acestei sfere, iar selecția este calculată din ele
- 1 la

așteptare fixă X \u003d ~ Y] X 5. Apoi centrul sferei

purtat in X, iar procedura de calcul se repetă. Condiția pentru sfârșitul procesului iterativ este egalitatea vectorilor medii X găsit pe TȘi (t+ 1) pași. Elemente prinse în interiorul sferei X 9 ... 9 X

le includem într-un grup și le excludem din cercetările ulterioare. Pentru punctele rămase, algoritmul se repetă. Algoritmul converge pentru orice alegere de aproximare inițială și orice cantitate de date inițiale. Totuși, pentru a obține o partiție stabilă (adică o partiție în care clusterele găsite după prima aplicare a algoritmului coincid ca număr și compoziție cu clusterele găsite la repetarea metodei), se recomandă repetarea procedurii algoritmice de mai multe ori. pentru diferite valori ale razei sferei R. Un semn al unei partiții stabile va fi formarea aceluiași număr de grupuri cu aceeași compoziție.

Rețineți că problema de clustering nu are singura solutie. Ca urmare, este destul de dificil și nu întotdeauna posibil să se enumere toate diviziunile admisibile ale datelor în clase. Pentru a evalua calitatea diferite căi clustering introduce noțiunea de calitate funcțională a partiției, care ia valoarea minimă pe cea mai bună (din punctul de vedere al cercetătorului) partiție.

Lasa X X9 ... 9 X p e U1 R - un set de observații, care este împărțit în clase S = (S l9 ... 9 S k ) 9și la cunoscute dinainte. Apoi, principalele funcționale de calitate a partiționării pentru un număr cunoscut de clustere au forma:

1) Suma ponderată a variațiilor intraclasă

Unde a(1)- așteptarea matematică selectivă a clusterului S l

Funcţional Q((S) ne permite să estimăm gradul de omogenitate al tuturor clusterelor în ansamblu.

2) Suma distanțelor intraclasă în perechi dintre elemente sau

Unde p 1- numărul de elemente din cluster S { .

3) Varianta generalizată intraclasă

Unde n j- numărul de elemente în S., DAR; . - matrice de covarianță eșantion pentru sj.

Funcționala este media aritmetică a variațiilor intraclase generalizate calculate pentru fiecare cluster. După cum se știe, varianța generalizată face posibilă estimarea gradului de dispersie a observațiilor multivariate. De aceea Q 3 (S) permite estimarea dispersiei medii a vectorilor de observare în clase S l9 ... 9 S k . De aici și numele său - varianță intraclasă generalizată. Q 3 (S) se foloseste atunci cand este necesara rezolvarea problemei comprimarii datelor sau concentrarii observatiilor intr-un spatiu cu o dimensiune mai mica decat cea originala.

4) Calitatea clasificării observațiilor poate fi evaluată și folosind criteriul Hotelling. Pentru a face acest lucru, aplicăm criteriul de testare a ipotezei H 0 despre egalitatea vectorilor medii ai două populații multidimensionale și calculați statisticile

Unde n tȘi p t - numărul de vectori din clase S l ,S m ; X, X t- date inițiale centrate; S*- matricea de covarianță combinată a clusterelor S n S m: S* =--- (XjX l + X^X m). Ca și înainte, valoarea Q 4 (S)

p,+p t -2

comparativ cu valoarea tabelului calculată conform formulei

Unde m- dimensiunea inițială a vectorilor de observație și este nivelul de semnificație.

Ipoteză H 0 se acceptă cu probabilitate (1-oc) dacă Q4(S)n_m și este respinsă altfel.

De asemenea, este posibil să se estimeze empiric calitatea divizării în clase. De exemplu, se poate compara mediile eșantionului găsite pentru fiecare clasă cu media eșantionului din întreaga populație de observații. Dacă diferă cu un factor de doi sau mai mulți, atunci partiția este bună. O comparație mai corectă a mediilor eșantionului cluster cu media eșantionului întregii populații de observații conduce la utilizarea analizei de varianță pentru a evalua calitatea împărțirii în clase.

Dacă numărul de clustere în S = (S l9 ...,S k ) nu este cunoscut în prealabil, atunci următoarele funcționale de calitate a partiționării sunt utilizate pentru un întreg ales arbitrar m:

eueula 1 1 m

- - măsura medie a intraclasei

P i=1 n i XjeSj X"tSj J

împrăștiere bufniță,

(1 P/ 1W
- X ~-~ r „ măsura concentrației punctelor mulțimii

P nV l J J

S, - numărul de elemente din clusterul care conține punctul X g

Rețineți că pentru o valoare arbitrară a parametrului T funcţional Z m (S) atinge un minim egal cu eu/p, dacă gruparea originală S = (S l9 ...,S k ) este o partiție în mono-clustere S. = (Xj), deoarece V(Xt) = 1. În același timp Z m (S) ajunge la maximum 1 dacă S- un cluster care conține toate datele inițiale,

deoarece V(X() = n.În cazuri particulare, se poate demonstra că Z_ l (S) =-, Unde la - numărul de clustere diferite în S = (S l9 ... 9 S k ) 9 Z X (S) = max - ,

*" V P)

Unde n t - numărul de elemente din cluster S i9 Z^(S) = min - ,

G" P)

Rețineți că, în cazul unui număr necunoscut de clustere, calitatea partiționării este funcțională Î(E) poate fi aleasă ca o combinație algebrică (sumă, diferență, produs, raport) a două funcționale I m (S), Z m (S),întrucât prima este una descrescătoare iar cealaltă este o funcţie crescătoare a numărului de clase la. Un astfel de comportament Z m (S)

garantează existența unui extremum Î(S).

Introducere

Termenul de analiză a grupurilor, introdus pentru prima dată de Tryon în 1939, include peste 100 de algoritmi diferiți.

Spre deosebire de problemele de clasificare, analiza cluster nu necesită ipoteze a priori despre setul de date, nu impune restricții privind reprezentarea obiectelor studiate și vă permite să analizați indicatori ai diferitelor tipuri de date (date de interval, frecvențe, date binare) . Trebuie amintit că variabilele trebuie măsurate pe scale comparabile.

Analiza cluster vă permite să reduceți dimensiunea datelor și să le faceți vizuale.

Analiza cluster poate fi aplicată la seturi de serii temporale, aici se pot distinge perioade de similitudine ale unor indicatori și se pot determina grupuri de serii temporale cu dinamică similară.

Analiza cluster s-a dezvoltat în paralel în mai multe direcții, cum ar fi biologia, psihologia și altele, astfel încât majoritatea metodelor au două sau mai multe nume.

Sarcinile de analiză a clusterelor pot fi grupate în următoarele grupuri:

Dezvoltarea unei tipologii sau clasificări.

Explorarea schemelor conceptuale utile pentru gruparea obiectelor.

Prezentarea ipotezelor bazate pe explorarea datelor.

Testarea ipotezelor sau cercetarea pentru a determina dacă tipurile (grupurile) identificate într-un fel sau altul sunt de fapt prezente în datele disponibile.

De regulă, în utilizarea practică a analizei cluster, mai multe dintre aceste sarcini sunt rezolvate simultan.

Scopul lecției

Obținerea abilităților în aplicarea practică a metodelor ierarhice și iterative de analiză a clusterelor.

Sarcina practică

Dezvoltați algoritmi pentru metodele vecinului apropiat și k-mediu si implementeaza-le sub forma de programe de calculator. Generați 50 de implementări folosind DNC X= (X 1 ,X 2) - o variabilă bidimensională aleatoare, ale cărei coordonate sunt distribuite uniform în intervalul (3.8). Distribuiți-le folosind programele dezvoltate în numărul minim de clustere, fiecare dintre acestea fiind plasat într-o sferă cu o rază de 0,15.

Instrucțiuni

Denumirea de analiză a grupurilor provine din cuvântul englezesc cluster - bunch, acumulation.Cluster analysis este o clasă largă de proceduri de analiză statistică multivariată care permit gruparea automată a observațiilor în clase omogene - clustere.

Clusterul are următoarele caracteristici matematice:

dispersie cluster;
deviație standard.

Centrul clusterului este locul punctelor din spațiul variabilelor.

Raza clusterului - distanța maximă a punctelor de la centrul clusterului.

Dispersia clusterului este o măsură a răspândirii punctelor în spațiu în raport cu centrul clusterului.

Deviația standard (RMS) a obiectelor în raport cu centrul clusterului este rădăcina pătrată a varianței clusterului.

Metode de analiză a clusterelor

Metodele de analiză a grupurilor pot fi împărțite în două grupe:

ierarhic;

neierarhic.

Fiecare grup include multe abordări și algoritmi.

Folosind diferite metode de analiză a clusterelor, un analist poate obține soluții diferite pe aceleași date. Acest lucru este considerat normal.

Metode ierarhice de analiză a clusterelor

Esența grupării ierarhice este îmbinarea secvențială a clusterelor mai mici în clustere mai mari sau împărțirea clusterelor mari în altele mai mici.

Metode aglomerative ierarhice(Agglomerative Nesting, AGNES)

Acest grup de metode se caracterizează printr-o combinație secvențială a elementelor inițiale și o scădere corespunzătoare a numărului de clustere.

La începutul algoritmului, toate obiectele sunt grupuri separate. La primul pas, cele mai asemănătoare obiecte sunt combinate într-un grup. În pașii următori, fuziunea continuă până când toate obiectele formează un grup.

Metode ierarhice divizibile (divizibile).(Analiză divizivă, DIANA)

Aceste metode sunt opusul logic al metodelor aglomerative. La începutul algoritmului, toate obiectele aparțin unui grup, care este împărțit în grupuri mai mici la pașii următori, ca urmare, se formează o secvență de grupuri de împărțire.

Metodele de grupare ierarhică diferă în ceea ce privește regulile de construire a clusterelor. Regulile sunt criteriile care sunt folosite atunci când se decide asupra „asemănării” obiectelor atunci când acestea sunt combinate într-un grup.

Măsuri de similaritate

Pentru a calcula distanța dintre obiecte, se folosesc diverse măsuri de similaritate (măsuri de similaritate), numite și metrici sau funcții de distanță.

distanta euclidiana este o distanță geometrică într-un spațiu multidimensional și se calculează prin formula (4.1).

Distanța euclidiană (și pătratul său) este calculată din datele originale, nu din date standardizate.

Distanța euclidiană la pătrat se calculează prin formula (4.2).

(4.2)

Distanța de Manhattan (distanța blocului orașului), numită și distanța „hamming” sau „bloc oraș”, este calculată ca medie a diferențelor peste coordonate. În cele mai multe cazuri, această măsură a distanței conduce la rezultate similare cu calculele distanței euclidiene. Cu toate acestea, pentru această măsură, efectul valorii aberante individuale este mai mic decât atunci când se utilizează distanța euclidiană, deoarece aici coordonatele nu sunt pătrate. Distanța Manhattan este calculată folosind formula (4.3).

(4.3)

Distanța Cebyshev ar trebui utilizat atunci când este necesar să se definească două obiecte ca „diferite” dacă diferă într-o singură dimensiune. Distanța Chebyshev este calculată prin formula (4.4).

(4.4)

Distanța de putere este utilizat atunci când se dorește creșterea sau scăderea progresivă a greutății aferente unei dimensiuni pentru care obiectele corespunzătoare sunt foarte diferite. Distanța de putere este calculată prin formula (4.5).

(4.5)

Unde rȘi p- parametri definiți de utilizator. Parametru p este responsabil pentru ponderarea treptată a diferențelor asupra coordonatelor individuale, parametrul r pentru ponderarea progresivă a distanțelor mari între obiecte. Dacă ambele variante rȘi p sunt egale cu doi, atunci această distanță coincide cu distanța lui Euclid.

Procent de dezacord utilizat atunci când datele sunt categorice. Această distanță este calculată prin formula (4.6).

(4.6)

Metode de alăturare sau de legătură

La primul pas, când fiecare obiect este un grup separat, distanțele dintre aceste obiecte sunt determinate de măsura aleasă. Cu toate acestea, atunci când mai multe obiecte sunt legate între ele, trebuie utilizate alte metode pentru a determina distanța dintre clustere. Există multe metode de alăturare a clusterelor:

Legătură unică (metoda cel mai apropiat vecin) - distanța dintre două clustere este determinată de distanța dintre cele mai apropiate două obiecte (nearest neighbors) în grupuri diferite.

Conexiune completă (metoda celui mai îndepărtat vecin) - distanțele dintre grupuri sunt determinate de cea mai mare distanță dintre oricare două obiecte din grupuri diferite (adică „vecinii cei mai îndepărtați”).

Medie neponderată pe perechi - distanța dintre două grupuri diferite este calculată ca distanța medie dintre toate perechile de obiecte din ele.

Media ponderată pe perechi – metoda este identică cu metoda medie neponderată pe perechi, cu excepția faptului că calculul folosește dimensiunea clusterelor corespunzătoare (adică, numărul de obiecte pe care le conțin) ca factor de ponderare.

Metoda centroidului neponderat - distanța dintre două grupuri este definită ca distanța dintre centrele lor de greutate.

Metoda centroidului ponderat (mediană) - metoda este identică cu metoda centroidului neponderat, cu excepția faptului că ponderile sunt utilizate în calcule pentru a ține cont de diferența dintre dimensiunile clusterelor (adică, numărul de obiecte din ele).

Metoda lui Ward - distanța dintre clustere este definită ca creșterea sumei distanțelor pătrate ale obiectelor față de centrele clusterelor, obținută ca urmare a unirii acestora. Metoda diferă de toate celelalte metode deoarece utilizează metode ANOVA pentru a estima distanțele dintre clustere. Metoda minimizează suma pătratelor pentru oricare două grupuri (ipotetice) care pot fi formate la fiecare pas.

Metoda celui mai apropiat vecin

Distanța dintre două clase este definită ca distanța dintre cei mai apropiați membri ai acestora.

Înainte de a începe algoritmul, acesta este calculat matricea distanțelorîntre obiecte. Conform criteriului de clasificare, uniunea are loc între grupuri, distanța dintre cei mai apropiați reprezentanți ai cărora este cea mai mică: sunt selectate două obiecte cu distanța cea mai mică într-un grup. După aceea, este necesar să se recalculeze matricea distanțelor ținând cont de noul cluster. La fiecare pas, matricea distanțelor este căutată pentru valoarea minimă corespunzătoare distanței dintre cele mai apropiate două grupuri. Clusterele găsite sunt combinate pentru a forma un nou cluster. Această procedură se repetă până când toate clusterele sunt îmbinate.

Atunci când utilizați metoda celui mai apropiat vecin, trebuie acordată o atenție deosebită alegerii unei măsuri de distanță între obiecte. Pe baza acesteia, se formează o matrice de distanță inițială, care determină întregul proces de clasificare ulterioară.

metode iterative.

Cu un număr mare de observații, metodele ierarhice de analiză a clusterelor nu sunt potrivite. În astfel de cazuri, se folosesc metode non-ierarhice, bazate pe împărțirea clusterelor originale în alte clustere și care sunt metode iterative de împărțire a populației originale. În timpul procesului de divizare, se formează noi grupuri până la îndeplinirea regulii de oprire.

O astfel de grupare neierarhică constă în împărțirea unui set de date într-un anumit număr de clustere distincte. Există două abordări. Primul este de a defini granițele clusterelor ca zonele cele mai dense din spațiul multidimensional al datelor originale, adică definiția unui cluster unde există un „cluster de puncte” mare. A doua abordare este de a minimiza măsura diferenței obiectelor.

Spre deosebire de metodele de clasificare ierarhică, metodele iterative pot duce la formarea de clustere suprapuse, când un obiect poate aparține simultan mai multor clustere.

Metodele iterative includ, de exemplu, metoda k-medii, metoda de cautare a concentratiilor si altele. Metodele iterative sunt rapide, ceea ce le permite să fie utilizate pentru a procesa matrice mari de informații inițiale.

Algoritmul k-means (k-means)

Dintre metodele iterative, cea mai populară metodă este metoda k- McKean mediu. Spre deosebire de metodele ierarhice, în majoritatea implementărilor acestei metode, utilizatorul însuși trebuie să specifice numărul dorit de clustere finale, care este de obicei notat „ k". Algoritm k- constructii medii k ciorchine situate cât mai îndepărtate una dintre ele. Cerința principală pentru tipul de probleme pe care le rezolvă algoritmul k-medii - prezența unor ipoteze (ipoteze) privind numărul de clustere, în timp ce acestea ar trebui să fie cât mai diferite. Alegerea numărului k se poate baza pe cercetări anterioare, considerații teoretice sau intuiție.

Ca și în metodele de grupare ierarhică, utilizatorul poate alege unul sau altul tip de măsură de similitudine. Algoritmi de diferite metode k-mediile difera si prin modul de alegere a centrelor initiale ale clusterelor specificate. În unele versiuni ale metodei, utilizatorul însuși poate (sau trebuie) să specifice astfel de puncte inițiale, fie selectându-le din observații reale, fie specificând coordonatele acestor puncte pentru fiecare dintre variabile. În alte implementări ale acestei metode, alegerea unui număr dat k punctele inițiale sunt produse aleatoriu, iar aceste puncte inițiale (centri de cluster) pot fi ulterior rafinate în mai multe etape. Există 4 etape principale ale unor astfel de metode:

ales sau numit k observații care vor fi centrele primare ale clusterelor;

dacă este necesar, clusterele intermediare sunt formate prin atribuirea fiecărei observații celor mai apropiate centre de cluster date;

după atribuirea tuturor observațiilor clusterelor individuale, centrele clusterelor primare sunt înlocuite cu medii cluster;

iterația anterioară se repetă până când modificările coordonatelor centrilor clusterului devin minime.

Ideea generală a algoritmului: un anumit număr fix k de clustere de observație este comparat cu clustere în așa fel încât mediile din cluster (pentru toate variabilele) să difere cât mai mult una de cealaltă.

Descrierea algoritmului

Distribuția inițială a obiectelor pe clustere.

Numărul selectat kȘi k puncte. La primul pas, aceste puncte sunt considerate a fi „centrele” clusterelor. Fiecare cluster corespunde unui centru. Alegerea centroizilor inițiali poate fi efectuată după cum urmează:

alegere k- observații pentru a maximiza distanța inițială;

selectie aleatorie k- observatii;

prima alegere k- observatii.

Fiecare obiect este apoi atribuit unui anumit cluster cel mai apropiat.

Proces iterativ.

Se calculează centrele clusterelor, care apoi și mai departe sunt considerate a fi mijloacele coordonate ale clusterelor. Obiectele sunt redistribuite. Procesul de calcul al centrelor și redistribuirea obiectelor continuă până când este îndeplinită una dintre următoarele condiții:

centrii clusterului s-au stabilizat, adică toate observațiile aparțin clusterului căruia îi aparțineau înainte de iterația curentă. În unele variante ale acestei metode, utilizatorul poate seta o valoare numerică a criteriului, care este interpretată ca distanța minimă pentru selectarea noilor centre de cluster. Observarea nu va fi considerată candidat pentru centru nou cluster, dacă distanța sa până la centrul înlocuit al clusterului depășește numărul specificat. Un astfel de parametru într-un număr de programe se numește „rază”. În plus față de acest parametru, este posibil să se stabilească un număr de obicei suficient de mic, cu care se compară modificarea distanței pentru toate centrele clusterului. Acest parametru se numește de obicei „convergență”, deoarece reflectă convergența procesului de clustering iterativ;

numărul de iterații este egal cu numărul maxim de iterații.

Verificarea calității grupării

După obţinerea rezultatelor analizei cluster prin metoda k- medii, ar trebui să verificați corectitudinea grupării (adică, să evaluați modul în care clusterele diferă unele de altele). Pentru a face acest lucru, se calculează valori medii pentru fiecare cluster. O bună grupare ar trebui să producă mijloace foarte diferite pentru toate măsurătorile, sau cel puțin pentru majoritatea acestora.

Avantajek-means algoritm:

ușurință în utilizare;

viteza de utilizare;

claritatea și transparența algoritmului.

dezavantajek-means algoritm:

algoritmul este prea sensibil la valori aberante care pot distorsiona media. O posibilă soluție la această problemă este utilizarea unei modificări a algoritmului - algoritmul k- mediane;

algoritmul poate fi lent pe baze de date mari. O posibilă soluție la această problemă este utilizarea eșantionării datelor.

Raportul trebuie să conțină:

descrierea și diagramele bloc ale algoritmilor;

texte sursă ale modulelor de program;

rezultatele algoritmilor sub formă de grafice.

Cu un număr mare de observații, metodele ierarhice de analiză a clusterelor nu sunt potrivite. În astfel de cazuri, se folosesc metode non-ierarhice bazate pe divizare, care sunt metode iterative de împărțire a populației inițiale. În timpul procesului de divizare, se formează noi grupuri până la îndeplinirea regulii de oprire.

O astfel de grupare neierarhică constă în împărțirea unui set de date într-un anumit număr de clustere distincte. Există două abordări. Primul este de a defini granițele clusterelor ca zonele cele mai dense din spațiul multidimensional al datelor inițiale, i.e. definiția unui cluster unde există o mare „concentrație de puncte”. A doua abordare este de a minimiza măsura diferenței obiectelor

Algoritmul k-means (k-means)

Cea mai comună dintre metodele non-ierarhice este algoritmul k-means, numit și analiză rapidă de cluster. O descriere completă a algoritmului poate fi găsită în Hartigan și Wong (1978). Spre deosebire de metodele ierarhice, care nu necesită presupuneri preliminare cu privire la numărul de clustere, pentru a putea folosi această metodă, este necesar să existe o ipoteză despre numărul cel mai probabil de clustere.

Algoritmul k-means construiește k clustere distanțate cât mai mult posibil. Principalul tip de probleme pe care le rezolvă algoritmul k-means este prezența unor ipoteze (ipoteze) privind numărul de clustere, în timp ce acestea ar trebui să fie cât mai diferite. Alegerea numărului k se poate baza pe cercetări anterioare, considerații teoretice sau intuiție.

Descrierea algoritmului

Distribuția inițială a obiectelor pe clustere. Se alege numărul k, iar la prima etapă aceste puncte sunt considerate a fi „centrele” clusterelor. Fiecare cluster corespunde unui centru.
Alegerea centroizilor inițiali poate fi efectuată după cum urmează:
- alegerea k-observațiilor pentru a maximiza distanța inițială;
- selecția aleatorie a k-observațiilor;
- alegerea primelor k-observaţii.
Ca rezultat, fiecare obiect este alocat unui anumit cluster.
Proces iterativ. Se calculează centrele clusterelor, care apoi și mai departe sunt considerate a fi mijloacele coordonate ale clusterelor. Obiectele sunt redistribuite.
Procesul de calcul al centrelor și redistribuirea obiectelor continuă până când este îndeplinită una dintre următoarele condiții:
- centrele cluster s-au stabilizat; toate observațiile aparțin clusterului căruia îi aparțineau înainte de iterația curentă;
- numărul de iterații este egal cu numărul maxim de iterații.

Pe fig. Figura 14.1 arată un exemplu de modul în care algoritmul k-medii funcționează pentru k egal cu doi.

Figura 1 - Un exemplu de funcționare a algoritmului k-medii (k=2)

Alegerea numărului de clustere este o problemă complexă. Dacă nu există ipoteze despre acest număr, se recomandă crearea a 2 clustere, apoi 3, 4, 5 etc., comparând rezultatele.

Verificarea calității grupării

După obținerea rezultatelor analizei cluster folosind metoda k-means, ar trebui să se verifice corectitudinea grupării (adică, se evaluează modul în care clusterele diferă unele de altele). Pentru a face acest lucru, se calculează valori medii pentru fiecare cluster. O bună grupare ar trebui să producă mijloace foarte diferite pentru toate măsurătorile, sau cel puțin pentru majoritatea acestora.

Avantajele algoritmului k-means:

ușurință în utilizare;
viteza de utilizare;
claritatea și transparența algoritmului.

Dezavantajele algoritmului k-means:

algoritmul este prea sensibil la valori aberante care pot distorsiona media. O posibilă soluție la această problemă este utilizarea unei modificări a algoritmului - algoritmul k-median;
algoritmul poate fi lent pe baze de date mari. O posibilă soluție la această problemă este utilizarea eșantionării datelor.

Algoritmul PAM (partiționare în jurul Medoids)

PAM este o modificare a algoritmului k-means, algoritmul k-median (k-medoids).

Algoritmul este mai puțin sensibil la zgomotul datelor și valorile aberante decât algoritmul k-means, deoarece mediana este mai puțin afectată de valori aberante.

PAM este eficient pentru bazele de date mici, dar nu ar trebui utilizat pentru seturi de date mari. Pre-reducerea dimensiunii

Luați în considerare un exemplu. Există o bază de date cu clienții companiei, care ar trebui împărțită în grupuri omogene. Fiecare client este descris folosind 25 de variabile. Utilizarea unui număr atât de mare de variabile duce la selectarea clusterelor unei structuri fuzzy. Ca rezultat, este destul de dificil pentru un analist să interpreteze clusterele rezultate.

Rezultate de grupare mai inteligibile și mai transparente pot fi obținute dacă, în locul unui set de variabile inițiale, sunt folosite unele variabile sau criterii generalizate care conțin informații despre relațiile dintre variabile într-o formă comprimată. Acestea. se pune problema reducerii dimensionalității datelor. Se poate rezolva cu diverse metode; una dintre cele mai comune - analiza factorilor. Să ne oprim asupra ei mai detaliat.

Analiza factorilor

Analiza factorială este o tehnică folosită pentru a studia relațiile dintre valorile variabilelor.

În general, analiza factorială are două obiective:

reducerea numărului de variabile;
clasificarea variabilelor - determinarea structurii relaţiilor dintre variabile.

În consecință, analiza factorială poate fi utilizată pentru a rezolva probleme de reducere a dimensionalității datelor sau pentru a rezolva probleme de clasificare.

Criteriile sau factorii principali identificați ca rezultat al analizei factoriale conțin informații într-o formă comprimată despre relațiile existente între variabile. Aceste informații vă permit să obțineți rezultate mai bune de grupare și să explicați mai bine semantica clusterelor. Factorii înșiși pot primi un anumit sens.

Cu ajutorul analizei factoriale, un număr mare de variabile este redus la un număr mai mic de mărimi de influență independente, care se numesc factori.

Un factor într-o formă „comprimată” conține informații despre mai multe variabile. Variabilele care sunt foarte corelate între ele sunt combinate într-un singur factor. Ca rezultat al analizei factoriale, se găsesc astfel de factori complecși care explică cât mai complet relațiile dintre variabilele luate în considerare.

La prima etapă a analizei factoriale, valorile variabilelor sunt standardizate, necesitatea cărora a fost luată în considerare în prelegerea anterioară.

Analiza factorială se bazează pe ipoteza că variabilele analizate sunt manifestări indirecte ale unui număr relativ mic de factori ascunși.

Analiza factorială este un set de metode axate pe identificarea și analiza dependențelor ascunse între variabilele observate. Dependențe latente sunt numite și dependențe latente.

Una dintre metodele de analiză factorială - metoda componentelor principale - se bazează pe presupunerea că factorii sunt independenți unul de celălalt.

Clustering iterativ în SPSS De obicei, un arsenal larg de metode este implementat în pachetele statistice, ceea ce face posibilă mai întâi reducerea dimensiunii unui set de date (de exemplu, folosind analiza factorială) și apoi gruparea în sine (de exemplu, folosind metoda de analiză rapidă a clusterelor) . Luați în considerare această opțiune pentru gruparea în pachetul SPSS.
Pentru a reduce dimensiunea datelor inițiale, folosim analiza factorială. Pentru a face acest lucru, selectați din meniu: Analiză (Analiză) / Reducere date (Transformare date) / Factor (Analiza factorială):
Utilizați butonul Extracție: pentru a selecta metoda de extracție. Vom lăsa analiza componentelor principale implicită menționată mai sus. De asemenea, ar trebui să alegeți o metodă de rotație - să alegem una dintre cele mai populare - metoda varimax. Pentru a salva valorile factorilor ca variabile, fila „Valori” trebuie bifată „Salvare ca variabile”.

Ca urmare a acestei proceduri, utilizatorul primește raportul „Varianța totală explicată”, care arată numărul de factori selectați - acestea sunt componentele ale căror valori proprii depășesc unul.

Valorile obținute ale factorilor, cărora li se dau de obicei numele fact1_1, fact1_2 etc., sunt utilizate pentru analiza clusterului folosind metoda k-means. Pentru a efectua o analiză rapidă a grupului, selectați din meniu:

Analizați/Clasificați/K-Means Cluster: (K-Means Cluster).

În caseta de dialog K Means Cluster Analysis (Analiză cluster prin k-means), trebuie să puneți variabilele factor fact1_1, fact1_2 etc. în domeniul variabilelor testate. Aici trebuie, de asemenea, să specificați numărul de clustere și numărul de iterații.

În urma acestei proceduri, obținem un raport cu ieșirea valorilor centrelor clusterelor formate, numărul de observații din fiecare cluster, precum și informatii suplimentare, setat de utilizator.

Astfel, algoritmul k-means împarte setul de date inițiale într-un număr dat de clustere. Pentru a putea vizualiza rezultatele obținute, ar trebui folosit unul dintre grafice, de exemplu, un grafic de dispersie. Cu toate acestea, imagistica convențională este posibilă pentru cantitate limitata dimensiuni, deoarece, după cum știți, o persoană poate percepe doar spațiul tridimensional. Prin urmare, dacă analizăm mai mult de trei variabile, ar trebui să folosim metode multidimensionale speciale pentru prezentarea informațiilor, acestea urmând a fi discutate într-una din prelegerile ulterioare ale cursului.

Metodele de grupare iterativă diferă în alegerea următorilor parametri:

punct de start;
regula pentru formarea de noi clustere;
regula de oprire.

Alegerea metodei de grupare depinde de cantitatea de date și de necesitatea lucrului cu mai multe tipuri de date în același timp.

În pachetul SPSS, de exemplu, dacă trebuie să lucrați atât cu cele cantitative (de exemplu, venituri) cât și cu categorii (de exemplu, starea civilă) variabile, iar dacă cantitatea de date este suficient de mare, se utilizează metoda de analiză cluster în doi pași, care este o procedură scalabilă de analiză a clusterului care vă permite să lucrați cu date de diferite tipuri. Pentru a face acest lucru, la prima etapă de lucru, înregistrările sunt pre-clustere într-un număr mare de sub-clustere. În a doua etapă, sub-clusterele rezultate sunt grupate în suma necesară. Dacă acest număr este necunoscut, procedura în sine îl determină automat. Cu această procedură, un angajat al băncii poate, de exemplu, să selecteze grupuri de persoane, utilizând simultan indicatori precum vârsta, sexul și nivelul veniturilor. Rezultatele obținute fac posibilă identificarea clienților care sunt expuși riscului de nerambursare a creditului.

ÎN caz general toate etapele analizei cluster sunt interconectate, iar deciziile luate la una dintre ele determină acțiunile din etapele ulterioare.

Analistul trebuie să decidă dacă să folosească toate observațiile sau să excludă unele date sau mostre din setul de date.

Alegerea metricii și a metodei de standardizare a datelor inițiale.

Determinarea numărului de clustere (pentru analiza clusterului iterativă).

Definirea metodei de clustering (reguli de îmbinare sau de legare).

Potrivit multor experți, alegerea metodei de grupare este decisivă în determinarea formei și specificității clusterelor.

Analiza rezultatelor grupării. Această etapă implică rezolvarea următoarelor întrebări: este aleator gruparea rezultată; dacă partiția este fiabilă și stabilă pe subeșantioane de date; dacă există o relație între rezultatele grupării și variabilele care nu au participat la procesul de grupare; dacă este posibil să se interpreteze rezultatele grupării.

Verificarea rezultatelor grupării. Rezultatele grupării ar trebui, de asemenea, verificate prin metode formale și informale. Metodele formale depind de metoda utilizată pentru grupare. Cele informale includ următoarele proceduri pentru verificarea calității grupării:

analiza rezultatelor grupării obținute pe anumite eșantioane ale setului de date;
validare încrucișată;
efectuarea grupării la schimbarea ordinii observațiilor din setul de date;
efectuarea grupării la ștergerea unor observații;
gruparea pe mostre mici.

Una dintre opțiunile de verificare a calității grupării este utilizarea mai multor metode și compararea rezultatelor. Absența similitudinii nu va însemna rezultate incorecte, dar prezența unor grupuri similare este considerată un semn al grupării de înaltă calitate.

Dificultăți și probleme care pot apărea la aplicarea analizei cluster

Ca orice alte metode, metodele de analiză a clusterelor au anumite părțile slabe, adică unele dificultăți, probleme și limitări.

Atunci când se efectuează analiza cluster, ar trebui să se țină seama de faptul că rezultatele grupării depind de criteriile de împărțire a setului de date inițiale. Când dimensiunea datelor este redusă, pot apărea anumite distorsiuni și unele caracteristici individuale ale obiectelor se pot pierde din cauza generalizărilor.

Există o serie de complexități care ar trebui luate în considerare înainte de grupare.

Complexitatea alegerii caracteristicilor pe baza cărora se realizează gruparea. O alegere neconsiderată duce la o partițiune inadecvată în clustere și, în consecință, la o soluție incorectă a problemei.
Dificultate în alegerea unei metode de grupare. Această alegere necesită o bună cunoaștere a metodelor și a condițiilor prealabile pentru utilizarea acestora. Pentru a verifica eficacitatea unei anumite metode într-un anumit domeniu, este recomandabil să aplicați următoarea procedură: luați în considerare mai multe grupuri care sunt a priori diferite unele de altele și amestecați aleatoriu reprezentanții lor între ei. Apoi, gruparea este efectuată pentru a restabili partiția originală în clustere. Proporția coincidențelor obiectelor din grupele identificate și inițiale este un indicator al eficacității metodei.
Problema alegerii numărului de clustere. Dacă nu există informații despre numărul posibil de clustere, este necesar să se efectueze o serie de experimente și, ca urmare a enumerarii unui număr diferit de clustere, să se aleagă numărul optim al acestora.
Problema interpretării rezultatelor grupării. Forma clusterelor în majoritatea cazurilor este determinată de alegerea metodei de asociere. Cu toate acestea, trebuie luat în considerare faptul că metodele specifice tind să creeze clustere de anumite forme, chiar dacă de fapt nu există clustere în setul de date studiat.

Analiza comparativă a metodelor de grupare ierarhică și neierarhică

Înainte de grupare, un analist poate avea o întrebare despre ce grup de metode de analiză a grupului să-i acorde preferință. Atunci când alegeți între metode ierarhice și non-ierarhice, este necesar să țineți cont de următoarele caracteristici.

Metodele neierarhice relevă rezistență mai mare la zgomot și valori aberante, alegerea incorectă a metricii, includerea variabilelor nesemnificative în setul implicat în clustering. Prețul care trebuie plătit pentru aceste avantaje ale metodei este cuvântul „a priori”. Analistul trebuie să predetermina numărul de clustere, numărul de iterații sau regula de oprire, precum și alți parametri de clustering. Acest lucru este deosebit de dificil pentru începători.

Dacă nu există ipoteze cu privire la numărul de clustere, se recomandă utilizarea algoritmilor ierarhici. Cu toate acestea, dacă dimensiunea eșantionului nu permite acest lucru, cale posibilă- efectuarea unei serii de experimente cu un număr diferit de clustere, de exemplu, începeți împărțirea setului de date din două grupuri și, crescând treptat numărul acestora, comparați rezultatele. Datorită acestei „variații” a rezultatelor, se obține o flexibilitate de grupare suficient de mare.

Metodele ierarhice, spre deosebire de cele non-ierarhice, refuză să determine numărul de clustere, dar construiesc un arbore complet de clustere imbricate.

Complexitatea metodelor de clustering ierarhic: limitarea volumului setului de date; alegerea măsurii de proximitate; inflexibilitatea clasificărilor obţinute.

Avantajul acestui grup de metode în comparație cu metodele neierarhice este claritatea lor și capacitatea de a obține o idee detaliată a structurii datelor.

Când se utilizează metode ierarhice, este posibil să se identifice destul de ușor valorile aberante într-un set de date și, ca urmare, să se îmbunătățească calitatea datelor. Această procedură stă la baza algoritmului de grupare în doi pași. Un astfel de set de date poate fi utilizat ulterior pentru clustering non-ierarhic.

Există un alt aspect care a fost deja menționat în această prelegere. Aceasta este o chestiune de grupare a întregii populații de date sau eșantionul acesteia. Acest aspect este esențial pentru ambele grupuri considerate de metode, dar este mai critic pentru metodele ierarhice. Metodele ierarhice nu pot funcționa cu seturi mari de date, iar utilizarea unei anumite selecții, de ex. o parte din date ar putea permite aplicarea acestor metode.

Rezultatele grupării pot să nu aibă o justificare statistică suficientă. Pe de altă parte, la rezolvarea problemelor de clustering, este acceptabilă o interpretare non-statistică a rezultatelor obținute, precum și o varietate destul de mare de opțiuni pentru conceptul de cluster. O astfel de interpretare non-statistică permite analistului să obțină rezultate satisfăcătoare de grupare, ceea ce este adesea dificil atunci când se utilizează alte metode.

Algoritmi noi și unele modificări ale algoritmilor de analiză a clusterelor

Metodele pe care le-am luat în considerare în această prelegere și în cele anterioare sunt „clasicile” analizei cluster. Până de curând, principalul criteriu prin care se evalua algoritmul de clustering a fost calitatea clusterării: se presupunea că întregul set de date se va încadra în RAM.

Cu toate acestea, acum, datorită apariției bazelor de date super-mari, există noi cerințe pe care algoritmul de clustering trebuie să le satisfacă. Principalul, așa cum sa menționat în prelegerile anterioare, este scalabilitatea algoritmului.

Remarcăm și alte proprietăți pe care algoritmul de clustering trebuie să le satisfacă: independența rezultatelor față de ordinea datelor de intrare; independenţa parametrilor algoritmului faţă de datele de intrare.

Recent, a existat o dezvoltare activă a unor noi algoritmi de clustering capabili să proceseze baze de date foarte mari. Se concentrează pe scalabilitate. Astfel de algoritmi includ o reprezentare generalizată a clusterului, precum și eșantionarea și utilizarea structurilor de date susținute de SGBD-ul de bază.

Au fost dezvoltați algoritmi în care metodele de grupare ierarhică sunt integrate cu alte metode. Acești algoritmi includ: MESTEȘEN, VINDECARE, CAMELEON, STANCĂ.

Algoritmul BIRCH (reducere iterativă echilibrată și grupare folosind ierarhii)

Algoritmul a fost propus de Tian Zang și colegii săi.

Datorită reprezentărilor generalizate ale clusterelor, viteza de clustering crește, în timp ce algoritmul are o scalare mare.

Acest algoritm implementează un proces de grupare în două etape.

În prima etapă, se formează un set preliminar de clustere. În a doua etapă, alți algoritmi de clustering sunt aplicați clusterelor identificate - potrivite pentru lucrul în RAM.

În următoarea analogie este descrisă acest algoritm. Dacă fiecare element de date este gândit ca o mărgele care se află pe suprafața unei mese, atunci grupurile de margele pot fi „înlocuite” cu mingi de tenis și putem trece la un studiu mai detaliat al grupurilor de mingi de tenis. Numărul de margele poate fi destul de mare, dar diametrul mingilor de tenis poate fi ales în așa fel încât în a doua etapă să fie posibil, folosind algoritmi tradiționali de grupare, să se determine forma complexă reală a ciorchinelor.

Algoritmul WaveCluster

WaveCluster este un algoritm de grupare bazat pe transformări de unde. La începutul algoritmului, datele sunt generalizate prin impunerea unei rețele multidimensionale în spațiul de date. La etapele ulterioare ale algoritmului, nu sunt analizate punctele individuale, ci caracteristicile generalizate ale punctelor care se încadrează într-o celulă a rețelei. Ca urmare a unei astfel de generalizări, informațiile necesare se potrivesc în RAM. În pașii următori, algoritmul aplică o transformare de undă datelor generalizate pentru a determina clusterele.

Principalele caracteristici ale WaveCluster:

complexitatea implementării;
algoritmul poate detecta grupuri de forme arbitrare;
algoritmul nu este sensibil la zgomot;
algoritmul este aplicabil numai datelor cu dimensiuni reduse.

Algoritmul CLARA (Clustering LARge Applications)

Algoritmul CLARA a fost dezvoltat de Kaufmann și Rousseeuw în 1990 pentru a grupa datele în baze de date mari. Acest algoritm este construit în pachete analitice statistice, cum ar fi S+.

Să descriem pe scurt esența algoritmului. Algoritmul CLARA preia multe mostre din baza de date. Clusteringul este aplicat fiecăreia dintre eșantioane, cea mai bună grupare este propusă ca rezultat al algoritmului.

Pentru bazele de date mari, acest algoritm este mai eficient decât algoritmul PAM. Eficiența algoritmului depinde de setul de date ales ca eșantion. O bună grupare pe setul selectat poate să nu ofere o bună grupare pe întregul set de date.

Algoritmi Clarans, CURE, DBScan

Algoritmul Clarans (Clustering Large Applications based on RANdomized Search) formulează problema de grupare ca o căutare aleatorie într-un grafic. Ca rezultat al acestui algoritm, setul de noduri grafice este o partiție a setului de date în numărul de clustere specificat de utilizator. „Calitatea” clusterelor rezultate este determinată folosind funcția de criteriu. Algoritmul Clarans sortează toate partițiile posibile ale setului de date în căutarea unei soluții acceptabile. Căutarea unei soluții se oprește la nodul unde se atinge minimul între un număr prestabilit de minime locale.

Printre noii algoritmi scalabili se mai remarcă algoritmul CURE - un algoritm de clustering ierarhic și algoritmul DBScan, unde conceptul de cluster este formulat folosind conceptul de densitate.

Principalul dezavantaj al algoritmilor BIRCH, Clarans, CURE, DBScan este faptul că necesită specificarea unor praguri de densitate de puncte, ceea ce nu este întotdeauna acceptabil. Aceste limitări se datorează faptului că algoritmii descriși sunt concentrați pe baze de date foarte mari și nu pot utiliza resurse de calcul mari.

Mulți cercetători lucrează activ la metode scalabile, a căror sarcină principală este de a depăși deficiențele algoritmilor care există astăzi.

Una dintre metodele de clasificare iterativă care nu necesită specificarea numărului de clustere este metoda de căutare a grupurilor. Metoda necesită calculul matricei distanțelor, apoi este selectat obiectul, care este centrul inițial al primului cluster. Alegerea unui astfel de obiect poate fi arbitrară sau se poate baza pe o analiză preliminară a punctelor și a vecinătăților acestora.

Punctul selectat este luat ca centru al unei hipersfere cu o rază R dată. Se determină setul de puncte care se încadrează în această sfere și se calculează coordonatele centrului (vectorul valorilor medii ale caracteristicilor) pentru ele. . În continuare, se ia în considerare o hipersferă de aceeași rază, dar cu un centru nou, iar pentru setul de puncte care intră în ea, se calculează din nou vectorul valorilor medii, care este luat ca noul centru al sferei. , și așa mai departe. Când următoarea recalculare a coordonatelor centrului sferei duce la același rezultat ca în pasul precedent, mișcarea sferei se oprește, iar punctele care intră în ea formează un grup și sunt excluse din procesul de grupare ulterioară. Pentru toate punctele rămase, procedurile se repetă.

Astfel, există mai multe metode neierarhice, deși funcționează pe aceleași principii. De fapt, ele sunt metode iterative de împărțire a populației inițiale. În procesul de divizare, se formează noi grupuri și așa mai departe până când regula de oprire este îndeplinită. Printre ele, metodele diferă în alegerea punctului de plecare, regula pentru formarea de noi clustere și regula de oprire. Algoritmul cel mai des folosit K-înseamnă.

Concluzie

Analiza cluster este o metodă de grupare a obiectelor în clase, bazată pe date experimentale despre proprietățile obiectelor.

În acest caz, se utilizează un model cluster de reprezentare a obiectelor - obiectele cu proprietăți similare aparțin aceleiași clase.

Analiza cluster include un set de algoritmi de clasificare diferiți (metoda dendrogramei poate fi citată ca exemplu de metodă de analiză cluster).

În acest caz, de regulă, numărul de clase și principiile împărțirii în clase sunt determinate în prealabil pe baza informațiilor generale despre setul de obiecte și obiectivele analizei cluster.

Metodele de analiză a clusterelor sunt completate de metode de analiză discriminantă care vă permit să determinați granițele dintre clustere și să le utilizați pentru a rezolva probleme de analiză și clasificare a datelor.

Rezultatele analizei cluster sunt cel mai adesea prezentate grafic, sub forma unei dendrograme („arborele”), arătând ordinea în care obiectele sunt combinate în clustere. Interpretarea structurii cluster, care în multe cazuri începe cu numărul de clustere, este o provocare creativă. Pentru ca acesta să fie rezolvat eficient, cercetătorul trebuie să aibă suficiente informații despre obiectele grupate. Cu gruparea antrenamentului, rezultatele pot fi prezentate ca liste de obiecte alocate fiecărei clase.

Principalele avantaje ale analizei cluster sunt absența restricțiilor privind distribuția variabilelor utilizate în analiză; posibilitatea de clasificare (clustering) chiar și în cazurile în care nu există informații a priori despre numărul și natura claselor; universalitate (analiza cluster poate fi aplicată nu numai colecțiilor de obiecte, ci și seturi de variabile sau orice alte unități de analiză).

Enumerăm dezavantajele analizei cluster:

La fel ca analiza factorială, poate produce clustere instabile. Repetați studiul pe alte persoane și comparați rezultatele clasificării. Cel mai probabil vor fi diferite. Cât de mult este o chestiune de calitatea studiului în sine.

Implementează metoda inductivă de cercetare de la particular la general, care este plină de concluzii antiștiințifice. În mod ideal, eșantionul pentru clasificare ar trebui să fie foarte mare, eterogen, de preferință selectat prin stratificare sau randomizare. Știința merge pe calea testării ipotezelor, așa că nu ar trebui abuzată analiza cluster. Cel mai bine este să îl utilizați pentru a testa o ipoteză despre prezența oricăror tipuri și nu pentru a crea o clasificare de la zero.

Ca orice metodă de scalare multidimensională, analiza cluster are multe caracteristici asociate cu metodele interne. Care este criteriul de grupare a oamenilor în clustere, metoda de găsire a diferențelor, numărul de pași pentru a finaliza algoritmul în metoda k-means etc. prin urmare, rezultatele pot varia, deși nu semnificativ, în funcție de „setările” procedurii.

Există două grupe de metode analiza grupului: ierarhic şi neierarhic.

Principalele metode de analiză a clusterelor ierarhice sunt metoda vecinului apropiat, metoda conexiunii complete, metoda conexiunii medii și metoda Ward. Ultimul este cel mai versatil.

Există mai multe metode neierarhice, deși funcționează pe aceleași principii. De fapt, ele sunt metode iterative de împărțire a populației inițiale. În procesul de divizare, se formează noi grupuri și așa mai departe până când regula de oprire este îndeplinită. Printre ele, metodele diferă în alegerea punctului de plecare, regula pentru formarea de noi clustere și regula de oprire. Algoritmul cel mai des folosit K-înseamnă. Aceasta implică faptul că analistul fixează în avans numărul de clustere din partiția rezultată.

Vorbind despre alegerea unei metode specifice de grupare, subliniem încă o dată că acest proces necesită ca analistul să fie bine familiarizat cu natura și cerințele prealabile ale metodelor, altfel rezultatele vor fi similare cu „temperatura medie din spital”. Pentru a vă asigura că metoda aleasă este cu adevărat eficientă în acest domeniu, se aplică de obicei următoarea procedură:

Sunt luate în considerare mai multe grupuri diferite a priori, iar reprezentanții lor sunt amestecați aleatoriu între ei. Apoi, se efectuează o procedură de grupare pentru a restabili gruparea inițială. Indicatorul eficacității metodei va fi proporția coincidențelor obiectelor din grupurile identificate și inițiale.

Atunci când alegeți între metode ierarhice și non-ierarhice, ar trebui să acordați atenție următoarelor puncte:

Metodele non-ierarhice arată rezistență mai mare la valori aberante, alegerea incorectă a metricii, includerea de variabile nesemnificative în baza de grupare etc. Dar prețul pentru aceasta este cuvântul „a priori”. Cercetătorul trebuie să stabilească în prealabil numărul rezultat de clustere, regula de oprire și, dacă există motive pentru aceasta, centrul inițial al clusterului. Ultimul punct afectează semnificativ eficiența algoritmului. Dacă nu există niciun motiv pentru a seta artificial această condiție, în general vorbind, se recomandă utilizarea metodelor ierarhice. Mai notăm un punct care este esențial pentru ambele grupuri de algoritmi: gruparea tuturor observațiilor nu este întotdeauna soluția potrivită. Poate fi mai precis să ștergeți mai întâi eșantionul de valori aberante și apoi să continuați cu analiza. De asemenea, este posibil să nu setați criteriul de oprire foarte ridicat.

Ar putea fi util să citiți: