Metode de analiză cluster. Metode iterative. Tipuri de proceduri de analiză a clusterelor Metodă de căutare a clusterelor de analiză a clusterelor

Analiza clusterelor (CLA) este un set de metode de clasificare multidimensională, al căror scop este de a forma grupuri (clustere) de obiecte similare. Spre deosebire de grupările tradiționale considerate în teoria generală a statisticii, CLA conduce la o împărțire în grupuri, luând în considerare simultan toate caracteristicile grupării.

Metodele CLA permit rezolvarea următoarelor sarcini:

- efectuarea clasificării obiectelor luând în considerare o varietate de caracteristici;

- verificarea ipotezelor prezentate cu privire la prezența unei structuri în setul de obiecte studiat, adică căutarea unei structuri existente;

- construirea de noi clasificări pentru fenomene slab studiate, atunci când este necesar să se stabilească prezența conexiunilor într-un set și să se încerce să aducă structură în el.

Pentru a scrie algoritmi CLA formalizați, se utilizează următoarele legendă:

- un set de obiecte de observare;

- observarea i-a în spațiul m-dimensional al semnelor ();

- distanța dintre obiectele -th și -th;

- valorile normalizate ale variabilelor inițiale;

- matricea distanțelor dintre obiecte.

Pentru a implementa orice metodă CLA, este necesar să se introducă conceptul de „similaritate a obiectelor”. Mai mult, în timpul procesului de clasificare, fiecare cluster ar trebui să includă obiecte care au cea mai mare asemănare între ele în ceea ce privește variabilele observate.

Pentru a cuantifica similitudinea, se introduce conceptul unei metrici. Fiecare obiect este descris prin caracteristici ș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 obicei, sunt utilizate următoarele măsuri de distanță între obiecte:

- Distanta euclidiana ;

- distanța euclidiană ponderată ;

- distanța blocului orașului ;

- distanța Mahalanobis,

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

, - valorile -variabilei și, respectiv, ale obiectelor -th și -th;

, - vectori de valori ale variabilelor obiectelor -th și -th;

- matricea generală de covarianță;

Greutatea este atribuită variabilei a.

Toate metodele CLA pot fi împărțite în două grupuri: ierarhică (aglomerativă și divizivă) și iterativă (metoda de mijloc, metoda de căutare a condensărilor).

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

Secvența de combinare poate fi reprezentată sub forma unei dendrograme, prezentată în Figura 3.1. Dendrograma arată că la primul pas al doilea și al treilea obiect sunt combinate într-un singur cluster cu o distanță de 0,15 între ele. În al doilea pas, primul obiect le-a unit. Distanța de la primul obiect la clusterul care conține al doilea și al treilea obiect, 0,3 etc.

Multe metode de analiză ierarhică a clusterelor diferă în algoritmii de combinare (similaritate), dintre care cele mai frecvente sunt: \u200b\u200bmetoda single link, metoda full link, metoda media link, metoda Ward.

Metoda legăturilor complete - un obiect nou este inclus în cluster numai dacă similitudinea dintre toate obiectele nu este mai mică decât un anumit nivel de similaritate specificat (Figura 1.3).

b)

Metoda relației medii - când un obiect nou este inclus într-un cluster deja existent, se calculează valoarea medie a măsurii de similaritate, care este apoi comparată cu un nivel de prag specificat. Dacă vorbim despre combinarea a două clustere, atunci se calculează măsura similarității dintre centrele lor și se compară cu o valoare prag predeterminată. Luați în considerare un exemplu geometric cu două clustere (Figura 1.4).

Figura 1.4. Combinarea a două clustere folosind metoda linkului mediu:

Dacă măsura similarității dintre centrele clusterelor () nu este mai mică decât nivelul specificat, atunci clusterele vor fi combinate într-un singur.

Metoda lui Ward - în primul pas, fiecare cluster constă dintr-un obiect. Cele două cele mai apropiate clustere sunt combinate inițial. Pentru ei, se determină valorile medii ale fiecărei caracteristici și se calculează suma pătratelor abaterilor

, (1.1)

unde - numărul clusterului, - numărul obiectului, - numărul caracteristicii; - numărul de caracteristici care caracterizează fiecare obiect; - numărul de obiecte din -cluster.

Ulterior, la fiecare pas al algoritmului, sunt combinate acele obiecte sau clustere care dau cea mai mică creștere a valorii.

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

Algoritmul ierarhic de analiză cluster poate fi reprezentat ca o succesiune de proceduri:

- normalizarea valorilor inițiale ale variabilelor;

- calcularea unei matrici de distanță sau a unei matrici de măsuri de similaritate;

- determinarea unei perechi de obiecte cele mai apropiate (clustere) și combinarea acestora în conformitate cu algoritmul ales;

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

Măsura de similaritate pentru combinarea a două clustere este determinată de următoarele metode:

- metoda „cel mai apropiat vecin” - gradul de asemănare între clustere este estimat de gradul de asemănare dintre cele mai similare (cele mai apropiate) obiecte ale acestor clustere;

- metoda „vecinului îndepărtat” - gradul de similitudine este evaluat de gradul de similitudine dintre cele mai îndepărtate obiecte cluster (disimilare);

- metoda conexiunii medii - gradul de similitudine este estimat ca valoarea medie a gradelor de similitudine dintre obiectele din clustere;

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

Metoda de căutare clump. Una dintre metodele de clasificare iterative este algoritmul de căutare a condensării. Esența algoritmului iterativ aceasta metoda constă în utilizarea unei hipersfere cu o rază dată, care se deplasează în spațiul semnelor de clasificare pentru a căuta condensarea locală a obiectelor.

Metoda de căutare a condenselor necesită, în primul rând, calcularea unei matrici de distanță (sau a unei matrici de măsuri de similaritate) între obiecte și alegerea centrului inițial al sferei. De obicei, la primul pas, centrul sferei este obiectul (punctul), în imediata vecinătate a căruia se află cel mai mare număr de vecini. Pe baza razei specificate a sferei (R), se determină un set de puncte care cad în interiorul acestei sfere, iar pentru ele se calculează coordonatele centrului (vectorul valorilor medii ale caracteristicilor).

Când următoarea recalculare a coordonatelor centrului sferei duce la același rezultat ca la pasul anterior, mișcarea sferei se oprește, iar punctele care cad în ea formează un cluster și sunt excluse din procesul de grupare suplimentar . Procedurile de mai sus sunt repetate pentru toate punctele rămase. Algoritmul se finalizează într-un număr finit de pași, iar toate punctele sunt distribuite pe clustere. 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, schimbând de fiecare dată raza cu o cantitate mică.

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

Dacă porniți algoritmul cu o valoare și îl modificați cu o valoare mică la fiecare repetare, atunci puteți identifica 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ă clasificarea a cinci întreprinderi utilizând analiza ierarhică a clusterelor.

Tabelul 1.1

Aici: - valoarea medie anuală a mijloacelor fixe, miliarde de ruble; - costuri materiale la o rublă de produse fabricate, copeici; - volumul produselor fabricate, miliarde de ruble

Decizie. Înainte de a calcula matricea distanței, normalizăm datele inițiale folosind formula

Matricea valorilor variabilelor normalizate va avea forma

.

Vom efectua clasificarea folosind metoda aglomerativă ierarhică. Pentru a construi matricea distanței, vom folosi distanța euclidiană. Apoi, de exemplu, distanța dintre primul și al doilea obiect va fi

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

.

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

.

În matrice, distanțele dintre clustere sunt determinate folosind algoritmul „vecinul îndepărtat”. Apoi, 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 clusterele; obținem un nou cluster care conține obiecte. Să-i atribuim un număr. Acum avem trei clustere (1,3), (2,5), (4).

.

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

.

Și, în cele din urmă, în ultimul pas, combinăm 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 compoziția obiectelor primite, deoarece unirea din acesta a avut loc la distanțe mai mici decât în \u200b\u200bcluster.

Figura 3.5 Dendrogramă de grupare a cinci obiecte

Exemplul 2. Pe baza datelor de mai jos, clasificați magazinele după trei criterii: - zonă etaj comercial, m2, - cifra de afaceri per vânzător, den. unități, - nivelul rentabilității,%.

Număr magazin				Număr magazin

Pentru a clasifica magazinele, utilizați metoda search clumps (trebuie selectat primul cluster).

Decizie. 1. Să calculăm distanța dintre obiecte în funcție de metrica euclidiană

,

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

.

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

Analiza matricii la distanță ajută la determinarea poziției centrului inițial al sferei și la selectarea razei sferei.

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

3. Setați raza sferei. În acest caz, sfera conține obiecte a căror distanță de 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ă, grup - clasă) după un criteriu sau combinația lor.

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

Metric se numește o funcție p care mapează un anumit spațiu metric în spațiul numerelor reale și are următoarele proprietăți (axiome ale metricei):

• 1) p (ZD\u003e 0,
• 2) p (X, Y) \u003d p(Y, X),
• 3) p (X, Y) \u003d 0 X \u003d Y,
• 4) P (X, Y) P (Z, Y).

În teoria analizei cluster, următoarele metrici sunt utilizate pentru a măsura distanța dintre punctele individuale (vectori):

1) Distanța euclidiană

2) distanța euclidiană ponderată

unde w k - greutăți proporționale cu importanța trăsăturii în problema clasificării. Ponderile sunt stabilite după cercetări suplimentare.

și presupuneți că ^ w * \u003d 1;

• 3) Distanța de lovire (sau bloc) - distanță pe hartă între cartierele din oraș

4) Distanța Mahalanobis (sau unghiul Mahalanobis)

unde A este o matrice pozitivă simetrică definită a coeficienților de greutate (adesea aleasă în diagonală); ȘI - matrice 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ță între vectori X x, ..., X P.

Alegerea metricei este făcută 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 scontat, de experiența cercetătorului, de nivelul de pregătire matematică al acestuia etc.

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

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

X (l) - eșantionul mediu peste punctele care cad în cluster S f, sau centrul de greutate al grupului 5 .. Apoi se disting următoarele distanțe între grupurile care nu au clusterele în interiorul altora:

1) distanța dintre clustere conform principiului „cel mai apropiat vecin”

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ță generalizată conform lui Kolmogorov

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

unde S ^ k ^ - un cluster obținut prin combinarea claselor S k și S t.

Toate cazurile speciale de distanțe sunt obținute din această formulă generalizată. Pentru a \u003d p \u003d 1/2, 8 \u003d -1/2, y \u003d 0, avem distanța conform principiului „celui mai apropiat vecin”, pentru a \u003d p \u003d 5 \u003d 1/2, y \u003d O - „vecinul îndepărtat”,

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

n k + n i n k + n i

grupuri.

Metodele de analiză cluster sunt subdivizate în I) aglomerativ (unitor), II) divizor (separat) și III) iterativ.

Primul combină secvențial obiecte individuale în clustere, al doilea, dimpotrivă, dezmembrează clustere în obiecte. Alții îi combină pe primii doi. Caracteristica lor este formarea de clustere pe baza condițiilor partiției (așa-numiții parametri), care pot fi modificate în timpul funcționării algoritmului pentru a îmbunătăți calitatea partiției. Metodele iterative sunt utilizate în mod obișnuit pentru a clasifica cantități mari de informații.

Să aruncăm o privire mai atentă asupra metodelor aglomerative. Metodele aglomerative sunt cele mai simple și mai frecvente dintre algoritmii de analiză cluster. În primul pas, fiecare vector sau obiect X 19 ..., X pag datele originale sunt tratate ca un cluster sau o clasă separată. Conform matricei calculate a distanțelor, cele mai apropiate unele de altele sunt selectate și combinate. Evident, procesul se va încheia în (P - 1) un pas când, ca rezultat, toate obiectele vor fi combinate într-un singur cluster.

O secvență de uniuni poate fi reprezentată ca o dendrogramă sau un arbore. În fig. 1.18 se arată că la primul pas vectorii X t, X 2, întrucât distanța dintre ele este de 0,3.

La al doilea pas, li s-a atașat un vector X 3, la distanță de cluster (X 1, X 2) la o distanță de 0,5 și așa mai departe. Ultimul pas combină toți vectorii într-un singur cluster.

Figura: 1.18.

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

1. Metoda legăturii unice.Lasa X v ..., X n - date vectoriale, fiecare vector formând un cluster. În primul rând, se calculează o matrice de distanțe între aceste grupuri, cu distanța conform principiului celui mai apropiat vecin folosit ca metrică. Folosind această matrice, sunt selectați doi vectori 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ță, iar distanța dintre clustere combinată în clase (a \u003d p \u003d 1/2, 5 \u003d -1/2, y \u003d 0 ) este folosit ca metrică. Cel mai apropiat de clasa obținută anterior S ( grupul se unește cu el, formându-se S 2 ... Etc. Prin p- 1 pași, obținem că toți vectorii sunt combinați într-un singur cluster.

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

dezavantaje: 1) este necesar să recalculăm constant matricea distanței, 2) numărul de clustere este cunoscut în avans ș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 anumit număr predeterminat. Numărul este stabilit de utilizator. Distanța se calculează numai pe baza principiului „vecinului îndepărtat” (același lucru se poate spune despre distanța dintre clase, unite în clase - numai principiul vecinului îndepărtat cu a \u003d p \u003d 8 \u003d 1/2, y \u003d 0).
• 3. Metoda legăturii medii.Algoritmul de formare a clusterului coincide cu algoritmul de legătură simplă, totuși, atunci când se decide asupra includerii unui nou obiect în cluster, calculele sunt efectuate în conformitate cu principiul legăturii medii. Ca și în metoda full link, toate distanțele calculate între clustere sunt comparate cu un număr specificat de utilizator. Și dacă (distanța) este mai mică decât numărul dat, noul obiect este inclus în clasa veche. Astfel, metoda de cuplare medie diferă de metoda de cuplare completă numai în metoda de calcul a distanței dintre clustere.
• 4. Metoda WARD.Lasa X 19 ..., X pag - date, fiecare vector formând un cluster. Găsim matricea distanțelor folosind unele metrice (de exemplu, distanța Mahalanobis), determinăm clusterele cele mai apropiate între ele folosind-o. Calculăm suma pătratelor deviațiilor vectorilor din cadrul clusterului S k conform formulei:

unde la - numărul clusterului, eu - numărul vectorului din cluster, j - numărul coordonatelor X t e Y1 R, n to - numărul de vectori din cluster, X jk - media eșantionului X i în S k. Cantitatea V k caracterizează abaterile vectorilor unul de celălalt în cadrul clusterului (nou S k + S f sau vechi ^). Plată V k ar trebui să fie efectuate înainte și după unire și este necesar să se enumere toate variantele posibile ale acestor uniuni. Mai departe de cluster S k se adaugă doar acei vectori sau clustere care duc la cea mai mică schimbare V k după îmbinare și, în consecință, care va fi localizat la o distanță minimă de clusterul original S k.

Să luăm în considerare metodele iterative în continuare. Esența metodelor iterative constă în faptul că gruparea începe cu stabilirea unor condiții inițiale. De exemplu, este necesar să setați numărul de clustere obținute sau să setați distanța care determină sfârșitul procesului de formare a clusterelor etc. Condițiile inițiale sunt selectate în funcție de rezultatul de care are nevoie cercetătorul. Cu toate acestea, ele sunt stabilite de obicei printr-o soluție găsită prin una dintre metodele aglomerative. Metodele iterative includ metoda ^ -mediilor și metoda de căutare a condenselor.

1. Metoda / r-înseamnă.Să existe vectori X l9 ..., X n e9F și trebuie împărțite în la clustere. La pasul zero de la p vectorii aleg la întâmplare la dintre ele, presupunând că fiecare formează un grup. Obținem un set de clustere de referință, ..., e [0) cu greutăți

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

Pe baza cunoașterii matricei distanței calculate, vectorul X ( este plasat în standard, a cărui distanță este minimă. Din motive de claritate, să presupunem că este. Se înlocuiește cu unul nou, recalculat ținând cont de punctul atașat, conform formulei

În plus, greutatea este, de asemenea, recalculată:

Dacă matricea conține două sau mai multe distanțe minime, atunci X t inclus în grupul cu cel mai mic număr ordinal.

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

standard e ^ ~ k) greutatea va corespunde și procedura de grupare va fi finalizată. Cu o mare p și mic la algoritmul converge rapid către o soluție stabilă, adică la o soluție în care standardele obținute după prima aplicare a algoritmului coincid în cantitate și compoziție cu standardele găsite atunci când metoda este aplicată din nou. Cu toate acestea, procedura algoritmică este întotdeauna repetată de mai multe ori, folosind partiția obținută în calculele anterioare ca vectori de referință (ca aproximare inițială): standarde găsite anterior f [p la e (2 p la) k) luat pentru f (x 0) 9 ... 9 f (k 0) 9 iar procedura algoritmică se repetă.

• 2. Metoda de căutare clump.Acesta este următorul algoritm iterativ. Nu necesită atribuirea a priori a numărului de clustere. La primul pas, matricea distanțelor dintre X X9 ... 9 X n eY1 p de unele metrice. Apoi, un vector este selectat aleatoriu pentru a juca rolul centrului primului cluster. Aceasta este o presupunere inițială. Presupunem că acest vector se află în centrul sferei p-dimensionale de rază R, iar această rază este stabilită de cercetător. Apoi vectorii X Si, ... 9 X Sk care se încadrează în această sferă, iar din ele se calculează alegerea
• - 1 la

așteptarea matematică exactă X \u003d ~ Y] X 5 ... Atunci centrul sferei este

purtat în X , iar procedura de calcul se repetă. Condiția pentru sfârșitul procesului iterativ este egalitatea vectorilor mijloacelor Xgă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 de la cercetări ulterioare. Pentru punctele rămase, algoritmul se repetă. Algoritmul converge pentru orice alegere a aproximării inițiale și pentru orice cantitate de date inițiale. Cu toate acestea, pentru a obține o partiție stabilă (adică o partiție în care clusterele găsite după prima aplicare a algoritmului coincid în număr și compoziție cu clusterele găsite când metoda a fost aplicată din nou), se recomandă repetarea procedurii algoritmice 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 clustere cu aceeași compoziție.

Rețineți că problema de grupare nu are singura soluție... Prin urmare, este destul de dificil să enumerăm toate defalcările de date admisibile în clase și nu este întotdeauna posibil. Pentru a evalua calitatea căi diferite în grupare, se introduce conceptul unei funcții de calitate a partiției, care ia o valoare minimă pe cea mai bună partiție (din punctul de vedere al cercetătorului).

Lasa X X9 ... 9 X pag e U1 R - o colecție de observații, care este împărțită în clase S \u003d (S l9 ... 9 S k) 9 în plus la cunoscut din timp. Apoi, funcționalitățile principale ale calității partiției pentru un număr cunoscut de clustere au forma:

1) Suma ponderată a varianțelor intraclasă

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

Funcţional Q ((S) vă permite să evaluați gradul de omogenitate al tuturor clusterelor în general.

2) Suma distanțelor intraclasă pereche între elemente sau

unde n 1 - numărul de elemente din cluster S { .

3) Varianță intraclasă generalizată

unde n j - numărul de elemente din S., ȘI; ... - eșantion matrice de covarianță pentru Sj.

Funcționalul este media aritmetică a varianțelor generalizate intraclasă calculate pentru fiecare cluster. După cum știți, varianța generalizată vă permite să estimați gradul de dispersie a observațiilor multivariate. prin urmare Q 3 (S)vă permite să estimați răspândirea medie a vectorilor de observare în clase S l9 ... 9 S k. De aici și numele său - varianță intraclasă generalizată. Q 3 (S) este utilizat atunci când este necesar să se rezolve problema comprimării datelor sau concentrării observațiilor într-un spațiu cu o dimensiune mai mică decât cea inițială.

4) Calitatea clasificării observațiilor poate fi de asemenea evaluată utilizând criteriul Hotelling. Pentru aceasta, aplicăm criteriul pentru a testa ipoteza H 0 privind egalitatea vectorilor mijloacelor a două populații multidimensionale și calculați statisticile

unde n t și n t - numărul de vectori din clase S l, S m; X, X t - date sursă centrate; S * - matrice combinată de covarianță în cluster S n S m: S * \u003d --- (XjX l + X ^ X m)... Ca și înainte, valoarea Q 4 (S)

n, + n t -2

comparativ cu valoarea tabelului calculată conform formulei

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

Ipoteză H 0 se acceptă cu probabilitate (1-oss) dacă Q 4 (S) n _ m și este respins în caz contrar.

De asemenea, puteți evalua empiric calitatea diviziunii clasei. De exemplu, puteți compara eșantionul mediu găsit pentru fiecare clasă cu eșantionul mediu al întregii populații de observații. Dacă diferă de două ori sau mai multe, atunci partiția este bună. O comparație mai corectă a eșantionului de medii cluster cu media eșantionului a întregului set de observații conduce la utilizarea analizei varianței pentru a evalua calitatea împărțirii în clase.

Dacă numărul de clustere din S = (S l9 ..., S k) nu este cunoscut în prealabil, apoi următoarele funcționalități de calitate a partiției sunt utilizate pentru un întreg ales în mod arbitrar m:

EuEula 1 1 m

- este măsura medie a intraclasei

P i=1 n i XjeSj X "tSj J

împrăștierea bufniței,

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

p nV l J J

S, - numărul de elemente din cluster 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 / n, dacă gruparea originală S \u003d (S l9 ..., S k) este o partiție mono cluster S. \u003d (Xj), deoarece V (X t) \u003d 1. În același timp Z m (S) atinge un maxim egal cu 1 dacă S - un cluster care conține toate datele originale,

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

* "V p)

unde n t - numărul de elemente dintr-un cluster S i9 Z ^ (S) \u003d min -,

r " p)

Rețineți că, în cazul unui număr necunoscut de clustere, funcționalitatea calității partiției Q (S) poate fi ales ca o combinație algebrică (sumă, diferență, produs, raport) a două funcționale I m (S), Z m (S), întrucât prima este în scădere și cealaltă este o funcție în creștere a numărului de clase la. Un astfel de comportament Z m (S)

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

Introducere

Termenul de analiză cluster, inventat pentru prima dată de Tryon în 1939, cuprinde peste 100 de algoritmi diferiți.

Spre deosebire de sarcinile de clasificare, analiza cluster nu necesită ipoteze a priori despre setul de date, nu impune restricții asupra reprezentării obiectelor studiate și vă permite să analizați indicatori ai diferitelor tipuri de date (date de interval, frecvențe, date binare) . Cu toate acestea, trebuie amintit că variabilele trebuie măsurate pe scări comparabile.

Analiza cluster vă permite să reduceți dimensiunea datelor, pentru a le clarifica.

Analiza cluster poate fi aplicată agregatelor de serii temporale, perioadele de similaritate ale unor indicatori pot fi distinse aici și pot fi determinate grupuri de serii temporale cu dinamică similară.

Analiza clusterelor 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ă cluster pot fi grupate în următoarele grupuri:

Dezvoltarea unei tipologii sau clasificări.

Explorează scheme conceptuale utile pentru gruparea obiectelor.

Prezentarea ipotezelor bazate pe explorarea datelor.

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

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

Scopul lecției

Câștigarea abilităților în aplicarea practică a metodelor ierarhice și iterative de analiză cluster.

Sarcină practică

Dezvoltați algoritmi pentru metode apropiate și k-mediu și implementați-le sub formă de programe de calculator. Generați 50 de realizări folosind RNG x= (x 1 , X 2) - o variabilă bidimensională aleatorie, 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 ele fiind plasat într-o sferă de rază 0,15.

Instrucțiuni metodice

Numele de analiză cluster provine din cuvântul englezesc cluster - un grup, cluster. Analiza cluster 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:

• varianța clusterului;

  deviație standard.

Centrul clusterului este media geometrică a punctelor din spațiul variabil.

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

Varianța clusterului este o măsură a dispersiei punctelor în spațiu în raport cu centrul clusterului.

Deviația rădăcină-medie-pătrat (RMSD) a obiectelor în raport cu centrul clusterului este rădăcina pătrată a varianței clusterului.

Metode de analiză cluster

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

ierarhic;

neierarhice.

Fiecare grup include multe abordări și algoritmi.

Folosind diferite metode de analiză cluster, analistul 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 combinația secvențială a clusterelor mai mici în cele mai mari sau împărțirea clusterelor mari în cele mai mici.

Metode aglomerative ierarhice (Cuibărire aglomerativă, 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 clustere separate. În primul pas, cele mai similare obiecte sunt combinate într-un cluster. În pașii următori, îmbinarea continuă până când toate obiectele formează un singur cluster.

Metode ierarhice divizibile (divizibile) (DIvisive ANAlysis, DIANA)

Aceste metode sunt opusul logic al metodelor aglomerative. La începutul algoritmului, toate obiectele aparțin unui singur cluster, care este împărțit în clustere mai mici în etapele ulterioare, rezultând o succesiune de grupuri de divizare.

Metodele ierarhice de clusterizare diferă în regulile de construire a clusterelor. Regulile sunt criteriile care sunt folosite atunci când se decide asupra „similitudinii” obiectelor atunci când acestea sunt combinate într-un grup.

Măsuri de similitudine

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

distanta euclidiana este o distanță geometrică în spațiul multidimensional și se calculează prin formula (4.1).

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

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

(4.2)

Distanța Manhattan (distanța blocului orașului), numită și distanța „ciocănit” sau „blocului orașului”, este calculată ca medie a diferențelor de coordonate. În majoritatea cazurilor, această măsură a distanței duce la rezultate similare cu calculele distanței euclidiene. Cu toate acestea, pentru această măsură, efectul valorilor aberante individuale este mai mic decât atunci când se utilizează distanța euclidiană, deoarece coordonatele nu sunt pătrate aici. Distanța Manhattan este calculată folosind ecuația (4.3).

(4.3)

Distanța Chebyshev ar trebui să fie utilizat atunci când este necesar să se definească două obiecte ca „diferite” dacă acestea diferă în orice dimensiune. Distanța Chebyshev este calculată prin formula (4.4).

(4.4)

Distanța de putereutilizat în cazurile în care se dorește să crească sau să scadă progresiv greutatea aferentă unei dimensiuni pentru care obiectele corespunzătoare diferă foarte mult. Distanța de putere este calculată prin formula (4.5).

(4.5)

unde r și p -parametrii definiti de utilizator. Parametru p este responsabil pentru cântărirea treptată a diferențelor de către coordonatele individuale, parametrul r pentru cântărirea progresivă a unor distanțe mari între obiecte. Dacă ambii parametri r și p sunt egale cu două, atunci această distanță coincide cu distanța euclidiană.

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

(4.6)

Combinarea sau legarea metodelor

În primul pas, când fiecare obiect este un cluster separat, distanțele dintre aceste obiecte sunt determinate de măsura selectată. Cu toate acestea, atunci când mai multe obiecte sunt legate între ele, trebuie utilizate alte metode pentru determinarea distanței dintre clustere. Există multe metode de combinare a clusterelor:

Single Link (Metoda celui mai apropiat vecin) - Distanța dintre două clustere este determinată de distanța dintre cele două obiecte cele mai apropiate (vecinii cei mai apropiați) din clustere diferite.

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

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

Media pe perechi ponderată - metoda este identică cu metoda medie pe perechi neponderatăcu excepția faptului că în calcule, dimensiunea grupurilor respective (adică numărul de obiecte pe care le conțin) este utilizată ca factor de ponderare.

Metoda centroidului neponderat - Distanța dintre două clustere 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ă calculele utilizează greutăți 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 în suma pătratelor distanțelor obiectelor la centrele clustere, obținută ca urmare a unirii lor. Metoda diferă de toate celelalte metode, deoarece folosește analiza varianței pentru a estima distanțele dintre clustere. Metoda minimizează suma pătratelor pentru oricare două clustere (ipotetice) care pot fi formate la fiecare pas.

Cea mai apropiată metodă de vecin

Distanța dintre două clase este definită ca distanța dintre reprezentanții lor cei mai apropiați.

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

Atunci când se utilizează metoda celui mai apropiat vecin, trebuie acordată o atenție specială alegerii distanței dintre obiecte. Pe baza acesteia, se formează o matrice de distanță inițială, care determină întregul proces de clasificare suplimentar.

Metode iterative.

Cu un număr mare de observații, metodele ierarhice de analiză cluster nu sunt potrivite. În astfel de cazuri, se utilizează metode neierarhice, bazate pe împărțirea grupurilor originale în alte grupuri și care sunt metode iterative de împărțire a populației inițiale. În procesul de diviziune, se formează noi clustere până la îndeplinirea regulii de oprire.

Acest cluster non-ierarhic constă în împărțirea unui set de date într-un număr de clustere distincte. Există două abordări. Primul constă în definirea limitelor clusterelor ca fiind cele mai dense zone din spațiul multidimensional al datelor inițiale, adică, definirea unui cluster unde există o „concentrație mare de puncte”. A doua abordare este de a minimiza măsura diferențelor dintre obiecte.

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

Metodele iterative includ, de exemplu, metoda k- medii, metoda de căutare a condensărilor și altele. Metodele iterative sunt cu acțiune rapidă, ceea ce le permite să fie utilizate pentru procesarea unor matrice mari de informații inițiale.

Algoritmul k-înseamnă

Dintre metodele iterative, cea mai populară metodă este k- mediu McKean. 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-construcții medii k grupuri situate la cele mai mari distanțe posibile între ele. Principala cerință pentru tipul de probleme rezolvate de algoritm k-mijloace, - prezența unor ipoteze (ipoteze) cu privire la numărul de clustere, în timp ce acestea ar trebui să fie cât mai diferite posibil. Selectarea numărului k se poate baza pe rezultatele cercetărilor anterioare, considerații teoretice sau intuiție.

Ca și în metodele ierarhice de clusterizare, utilizatorul poate selecta unul sau alt tip de măsură de similaritate. Diferiti algoritmi de metoda k-mijloacele diferă, de asemenea, prin metoda de alegere a centrelor inițiale ale clusterelor date. În unele versiuni ale metodei, utilizatorul însuși poate (sau trebuie) să specifice astfel de puncte de plecare, 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 în mod aleatoriu, iar aceste puncte inițiale (centrele cluster) pot fi ulterior rafinate în mai multe etape. Există 4 etape principale ale acestor metode:

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

dacă este necesar, grupurile intermediare se formează prin atribuirea fiecărei observații celor mai apropiați centre de cluster specificate;

după atribuirea tuturor observațiilor la clustere individuale, centrele de clustere primare sunt înlocuite cu medii de clustere;

iterația anterioară se repetă până când modificările în coordonatele centrelor cluster devin minime.

Ideea generală a algoritmului: un număr fix dat de clustere de observare sunt comparate cu clustere astfel încât media din cluster (pentru toate variabilele) să difere cât mai mult posibil una de cealaltă.

Descrierea algoritmului

Distribuția inițială a obiectelor în clustere.

Numărul este selectat k și k puncte. În primul pas, aceste puncte sunt considerate „centrele” grupurilor. Fiecare cluster are un centru. Alegerea centroidelor inițiale se poate face după cum urmează:

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

selectie aleatorie k-observații;

alegerea primului k-observații.

Apoi, fiecare obiect este atribuit unui cluster specific cel mai apropiat.

Un proces iterativ.

Se calculează centrele clusterelor, care sunt considerate apoi și în continuare mediile coordonate ale clusterelor. Obiectele sunt redistribuite din nou. Procesul de calculare a centrelor și realocarea obiectelor continuă până când una dintre condiții este îndeplinită:

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

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

Verificarea calității clusterizării

După obținerea rezultatelor analizei cluster prin metodă k-mediile trebuie verificate pentru corectitudinea grupării (de exemplu, evaluați diferența dintre grupuri). Pentru aceasta, valorile medii sunt calculate pentru fiecare cluster. Cu o grupare bună, ar trebui obținute mijloace foarte diferite pentru toate măsurătorile sau cel puțin pentru cele mai multe dintre ele.

Avantajek-înseamnă algoritm:

ușurință în utilizare;

viteza de utilizare;

claritatea și transparența algoritmului.

dezavantajek-înseamnă 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 ar trebui să conțină:

descrierea și diagramele bloc ale algoritmilor;

coduri 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 utilizează metode de partiționare non-ierarhizate, care sunt metode iterative de partiționare a populației inițiale. În procesul de divizare, se formează noi clustere până la îndeplinirea regulii de oprire.

Acest cluster non-ierarhic constă în împărțirea unui set de date într-un număr de clustere distincte. Există două abordări. Primul este de a defini limitele clusterelor ca fiind cele mai dense zone din spațiul multidimensional al datelor inițiale, adică definirea unui cluster unde există o „concentrație mare de puncte”. A doua abordare este de a minimiza măsura diferențelor dintre obiecte

K-înseamnă algoritm

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

Algoritmul k-înseamnă construiește k clustere situate la distanțe cât mai mari între ele. Principalul tip de probleme pe care algoritmul k-mijloace le rezolvă este prezența unor ipoteze (ipoteze) cu privire la numărul de clustere, în timp ce acestea ar trebui să fie cât mai diferite. Alegerea numărului k se poate baza pe rezultatele cercetărilor anterioare, considerații teoretice sau intuiție.

Ideea generală a algoritmului: un anumit număr fix k de clustere de observare sunt comparate cu clustere astfel încât media din cluster (pentru toate variabilele) să difere cât mai mult posibil una de cealaltă.

Descrierea algoritmului

1. Distribuția inițială a obiectelor în clustere. Se alege numărul k, iar la primul pas, aceste puncte sunt considerate „centrele” clusterelor. Fiecare cluster are un centru.
   Alegerea centroidelor inițiale se poate face după cum urmează:
   - selectarea observațiilor k pentru a maximiza distanța inițială;
   - selectarea aleatorie a k-observațiilor;
   - selectarea primelor k-observații.
   Ca rezultat, fiecare obiect este atribuit unui cluster specific.
2. Un proces iterativ. Se calculează centrele clusterelor, care sunt considerate apoi și în continuare mediile coordonate ale clusterelor. Obiectele sunt redistribuite din nou.
   Procesul de calculare a centrelor și realocarea obiectelor continuă până când una dintre condiții este îndeplinită:
   - centrele de cluster s-au stabilizat, adică toate observațiile aparțin grupului de care aparțineau înainte de iterația curentă;
   - numărul de iterații este egal cu numărul maxim de iterații.

În fig. 14.1 prezintă un exemplu de algoritm k-înseamnă pentru k egal cu doi.

Figura 1 - Un exemplu de algoritm k-înseamnă (k \u003d 2)

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

Verificarea calității clusterizării

După obținerea rezultatelor analizei clusterului prin metoda k-means, ar trebui să verificați corectitudinea clusterizării (adică să evaluați cum diferă clusterele unele de altele). Pentru aceasta, valorile medii sunt calculate pentru fiecare cluster. Cu o grupare bună, ar trebui obținute mijloace foarte diferite pentru toate măsurătorile sau cel puțin pentru cele mai multe dintre ele.

Avantajele algoritmului k-means:

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

Dezavantaje ale algoritmului k-means:

1. 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;
2. algoritmul poate fi lent pe baze de date mari. O posibilă soluție la această problemă este utilizarea eșantionării datelor.

Algoritm PAM (partiționare în jurul medoizilor)

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

Algoritmul este mai puțin sensibil la zgomot și valori externe decât algoritmul k-înseamnă, deoarece mediana este mai puțin afectată de valori anormale.

PAM este eficient pentru bazele de date mici, dar nu trebuie utilizat pentru seturile de date mari. Reducerea pre-dimensionalității

Să vedem un exemplu. Există o bază de date cu clienții firmei, 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 alocarea clusterelor cu o structură fuzzy. Ca rezultat, este destul de dificil pentru un analist să interpreteze grupurile rezultate.

Se pot obține rezultate de clustere mai clare și mai transparente dacă, în locul unui set de variabile inițiale, se utilizează unele variabile generalizate sau criterii care conțin informații concise despre relațiile dintre variabile. Acestea. apare problema scăderii dimensiunii datelor. Poate fi rezolvat folosind diverse metode; una dintre cele mai frecvente este analiza factorială. Să ne oprim mai detaliat.

Analiza factorilor

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

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

1. reducerea numărului de variabile;
2. clasificarea variabilelor - definirea structurii relațiilor dintre variabile.

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

Criteriile sau principalii factori identificați ca urmare a analizei factorilor conțin într-o formă concisă informații despre relațiile existente între variabile. Aceste informații vă permit să obțineți rezultate de clustering mai bune și să explicați mai bine semantica clusterelor. Factorilor înșiși li se poate da un anumit sens.

Cu ajutorul analizei factorilor, un număr mare de variabile sunt reduse la un număr mai mic de cantități independente care influențează, care se numesc factori.

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

La primul pas al analizei factorilor, valorile variabilelor sunt standardizate, a căror necesitate a fost discutată în cursul anterior.

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 care vizează identificarea și analiza dependențelor ascunse dintre variabilele observate. Dependențele latente se mai numesc și dependențe latente.

Una dintre metodele de analiză a factorilor, analiza componentelor principale, se bazează pe presupunerea că factorii sunt independenți unul de celălalt.

Clusterarea iterativă în SPSS De obicei, pachetele statistice implementează o gamă largă de metode, care vă permit să reduceți mai întâi dimensiunea setului de date (de exemplu, folosind analiza factorială), apoi clusterizarea efectivă (de exemplu, prin metoda analizei rapide a clusterelor). Să luăm în considerare această variantă de grupare în pachetul SPSS.
Pentru a reduce dimensiunea datelor inițiale, vom folosi analiza factorială. Pentru a face acest lucru, selectați din meniu: Analize / Reducere date / Factor (Analiza factorilor):
Folosind butonul Extracție: selectați metoda de selecție. Vom lăsa analiza implicită a componentei principale menționată mai sus. De asemenea, ar trebui să alegeți metoda de rotație - vom alege una dintre cele mai populare - metoda varimax. Pentru a salva valorile factorilor ca variabile în fila „Valori”, bifați caseta „Salvați ca variabile”.

Ca urmare a acestei proceduri, utilizatorul primește raportul „Variație cumulată explicată”, care arată numărul de factori selectați - aceștia sunt acele componente ale căror valori proprii depășesc unul.

Valorile obținute ale factorilor, cărora li se oferă de obicei denumirile fact1_1, fact1_2 etc., sunt folosite pentru a efectua analize cluster folosind metoda k-means. Pentru a efectua o analiză rapidă a clusterului, selectați din meniu:

Analiza / Clasificare / Cluster K-Means: Analiza K-Means Cluster.

În caseta de dialog K Means Cluster Analysis, variabilele factor factor1_1, fact1_2 etc. trebuie plasate. în câmpul variabilelor testate. Aici trebuie să specificați și numărul de clustere și numărul de iterații.

Ca urmare a acestei proceduri, obținem un raport cu ieșirea valorilor centrelor clusterelor formate, numărul de observații din fiecare cluster, precum și cu informatii suplimentaresetate de utilizator.

Astfel, algoritmul k-media împarte setul de date de intrare într-un număr dat de clustere. Pentru a putea vizualiza rezultatele obținute, ar trebui să utilizați unul dintre grafice, de exemplu, o diagramă scatter. Cu toate acestea, vizualizarea tradițională este posibilă pentru un număr limitat de 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 de prezentare a informațiilor, acestea vor fi discutate într-una din prelegerile ulterioare ale cursului.

Metodele de clusterizare iterative diferă în alegerea următorilor parametri:

1. punct de start;
2. regula pentru formarea de noi clustere;
3. regula de oprire.

Alegerea metodei de grupare depinde de cantitatea de date și de necesitatea de a lucra simultan cu mai multe tipuri de date.

În pachetul SPSS, de exemplu, dacă trebuie să lucrați atât cu cantități (de exemplu, venituri), cât și categorice (de exemplu, starea civilă), iar dacă cantitatea de date este suficient de mare, se folosește metoda Analizei clusterelor în două etape, care este o procedură de analiză scalabilă a clusterelor care vă permite să lucrați cu date de diferite tipuri. Pentru aceasta, la prima etapă de funcționare, înregistrările sunt pre-grupate într-un număr mare de sub-clustere. În a doua etapă, subgrupurile rezultate sunt grupate în suma necesară... Dacă această cantitate este necunoscută, procedura o determină automat. Folosind 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 permit identificarea clienților care sunt expuși riscului de nerambursare a împrumutului.

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

Analistul ar trebui să decidă dacă să utilizeze toate observațiile sau să excludă unele date sau mostre din setul de date.

Alegerea metricei și metodei pentru standardizarea datelor sursă.

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

Determinarea metodei de grupare (reguli de unire sau legătură).

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

Analiza rezultatelor grupării. Această etapă implică soluția unor astfel de întrebări: este partiția rezultată în clustere aleatorii; dacă partiționarea este fiabilă și stabilă față de submostele de date; dacă există o relație între rezultatele clusteringului și variabilele care nu au fost implicate în procesul de clustering; dacă este posibil să se interpreteze rezultatele obținute în cluster.

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 clusterizării:

1. analiza rezultatelor grupării obținute pe anumite eșantioane ale setului de date;
2. verificare încrucișată;
3. gruparea la schimbarea ordinii observațiilor din setul de date;
4. gruparea la ștergerea unor observații;
5. grupându-se pe probe mici.

Una dintre opțiunile pentru verificarea calității clusterizării este utilizarea mai multor metode și compararea rezultatelor. Lipsa similitudinii nu va însemna că rezultatele sunt incorecte, dar prezența grupurilor similare este considerată un semn al grupării de calitate.

Dificultăți și probleme care pot apărea atunci când se aplică analiza cluster

Ca orice alte metode, metodele de analiză cluster au anumite laturile slabe, adică unele dificultăți, probleme și limitări.

La efectuarea analizei clusterului, trebuie avut în vedere faptul că rezultatele clusteriză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; din cauza generalizărilor, unele caracteristici individuale ale obiectelor se pot pierde.

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

1. Complexitatea alegerii caracteristicilor, pe baza căreia se realizează gruparea. O alegere rapidă duce la o grupare inadecvată și, în consecință, la o soluție incorectă a problemei.
2. Dificultate în alegerea unei metode de grupare. Această alegere necesită o bună cunoaștere a metodelor și condițiilor prealabile pentru utilizarea lor. Pentru a testa eficiența unei anumite metode într-un anumit domeniu, este recomandabil să se aplice următoarea procedură: să se ia în considerare mai multe grupuri diferite a priori și să se amestece reprezentanții lor între ei în mod aleatoriu. Apoi, clusterizarea se efectuează pentru a restabili clusterizarea originală. Procentul coincidențelor obiectelor din grupurile identificate și inițiale este un indicator al eficacității metodei.
3. Problema alegerii numărului de clustere. Dacă nu există informații despre numărul posibil de clustere, este necesar să efectuați o serie de experimente și, ca urmare a enumerării unui număr diferit de clustere, alegeți numărul lor optim.
4. Problema interpretării rezultatelor grupării. Forma clusterelor este, în majoritatea cazurilor, determinată de alegerea metodei de fuzionare. Cu toate acestea, trebuie avut în vedere 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 clusterizare ierarhice și neierarhice

Înainte de a efectua clustering-ul, analistul poate avea o întrebare cu privire la grupul de metode de analiză cluster care trebuie preferat. Atunci când alegeți între metode ierarhice și neierarhice, este necesar să luați în considerare următoarele caracteristici.

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

Dacă nu există presupuneri cu privire la numărul de clustere, se recomandă algoritmi ierarhici. Cu toate acestea, dacă dimensiunea eșantionului nu permite acest lucru, modalitate posibilă - efectuarea unei serii de experimente cu un număr diferit de clustere, de exemplu, începeți să împărțiți un set 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 suficient de mare a grupării.

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

Dificultăți ale metodelor ierarhice de clusterizare: limitarea dimensiunii setului de date; alegerea măsurii de proximitate; inflexibilitatea clasificărilor rezultate.

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

Prin utilizarea metodelor ierarhice, este posibil să se identifice valorile aberante din setul de date destul de ușor și, ca urmare, să se îmbunătățească calitatea datelor. Această procedură se află în centrul algoritmului de grupare în doi pași. Acest set de date poate fi apoi utilizat pentru gruparea non-ierarhică.

Există încă un aspect care a fost deja menționat în această prelegere. Este vorba de gruparea întregului set de date sau a unui eșantion din acesta. Acest aspect este esențial pentru ambele grupuri de metode considerate, dar este mai critic pentru metodele ierarhice. Metodele ierarhice nu pot funcționa cu seturi de date mari, dar utilizarea unor selecții, adică bucăți de 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 grupare, este admisibilă o interpretare nestatistică a rezultatelor obținute, precum și o varietate destul de largă de variante ale conceptului de cluster. Această interpretare nestatistică permite analistului să obțină rezultate de grupare satisfăcătoare, ceea ce este adesea dificil cu alte metode.

Noi algoritmi și unele modificări ale algoritmilor de analiză cluster

Metodele pe care le-am discutat în prelegerile anterioare și anterioare sunt „clasice” ale analizei cluster. Până de curând, principalul criteriu prin care a fost evaluat algoritmul de clusterizare a fost calitatea clusterizării: s-a presupus că întregul set de date s-ar potrivi în RAM.

Cu toate acestea, acum, în legătură cu apariția bazelor de date super-mari, au apărut noi cerințe care trebuie satisfăcute de algoritmul de grupare. Principala, așa cum am menționat în prelegerile anterioare, este scalabilitatea algoritmului.

Remarcăm și alte proprietăți pe care algoritmul de clusterizare trebuie să le îndeplinească: 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 noilor algoritmi de clusterizare capabili să proceseze baze de date ultra-mari. Se concentrează pe scalabilitate. Acești algoritmi includ reprezentarea sumară a cluster-ului, precum și preluarea și utilizarea structurilor de date acceptate de SGBD-ul subiacent.

Au fost dezvoltate algoritmi în care metodele ierarhice de clusterizare sunt integrate cu alte metode. Acești algoritmi includ: BIRCH, CURE, CHAMELEON, ROCK.

Algoritm BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)

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

Datorită vizualizărilor generalizate ale clusterelor, viteza de clusterizare este crescută, în timp ce algoritmul este foarte scalabil.

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

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

Următoarea analogie descrie acest algoritm. Dacă fiecare bucată de date este considerată a fi o mărgele întinsă pe o suprafață a mesei, atunci grupurile de margele pot fi „înlocuite” cu mingi de tenis și trec la un studiu mai detaliat al grupurilor de mingi de tenis. Numărul de margele poate fi destul de mare, dar diametrul bilelor de tenis poate fi ales în așa fel încât în \u200b\u200ba doua etapă ar fi posibil, folosind algoritmi tradiționali de grupare, să se determine forma complexă efectivă a clusterelor.

Algoritmul WaveCluster

WaveCluster este un algoritm de grupare a formelor de undă. La începutul algoritmului, datele sunt generalizate prin impunerea unei rețele multidimensionale pe spațiul de date. În etapele ulterioare ale algoritmului, nu sunt analizate punctele individuale, ci caracteristicile generalizate ale punctelor care cad într-o celulă a rețelei. Ca urmare a acestei generalizări, informațiile necesare se încadrează în memoria RAM. În etapele ulterioare, algoritmul aplică forma de undă datelor agregate pentru a determina clusterele.

Caracteristici cheie ale WaveCluster:

1. complexitatea implementării;
2. algoritmul poate detecta clustere de forme arbitrare;
3. algoritmul nu este sensibil la zgomot;
4. 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 date în baze de date mari. Acest algoritm este încorporat în pachete de analiză statistică precum S +.

Să prezentăm pe scurt esența algoritmului. Algoritmul CLARA preia multe eșantioane din baza de date. Clusterizarea se aplică fiecăruia dintre eșantioane, ieșirea algoritmului sugerează o clusterizare mai bună.

Pentru bazele de date mari, acest algoritm este mai eficient decât algoritmul PAM. Performanța algoritmului depinde de setul de date ales ca eșantion. Este posibil ca un clustering bun pe un set de date selectat să nu producă un clustering bun pe întregul set de date.

Algoritmi Clarans, CURE, DBScan

Algoritmul Clarans (Clustering Large Applications based on RANdomized Search) algoritmul formulează problema de clustering ca o căutare aleatorie într-un grafic. Ca urmare a acestui algoritm, setul de noduri grafice este o partiție a setului de date în numărul de clustere definite de utilizator. „Calitatea” grupurilor rezultate este determinată utilizând o funcție 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 dintre un număr prestabilit de minime locale.

Noii algoritmi scalabili includ, de asemenea, algoritmul CURE, un algoritm ierarhic de clusterizare și algoritmul DBScan, unde conceptul de cluster este formulat utilizând conceptul de densitate.

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

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

Una dintre metodele de clasificare iterative care nu necesită specificarea numărului de clustere este metoda de căutare a condenselor. Metoda necesită calcularea unei matrice de distanță, apoi este selectat un obiect 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 împrejurimilor lor.

Punctul selectat este luat ca centrul unei hipersfere cu o rază dată R. Se determină un set de puncte care cad în interiorul acestei sfere, iar coordonatele centrului (vectorul valorilor medii ale caracteristicilor) sunt calculate pentru ele. Mai mult, se ia în considerare o hipersferă cu aceeași rază, dar cu un centru nou, iar pentru setul de puncte care au căzut î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 la pasul anterior, mișcarea sferei se oprește, iar punctele care cad în ea formează un cluster și sunt excluse din procesul de grupare suplimentar. Pentru toate punctele rămase, procedurile se repetă.

Astfel, există mai multe metode neierarhice, deși funcționează pe aceleași principii. În esență, acestea sunt metode iterative de fragmentare a populației inițiale. În procesul de divizare, se formează noi clustere, și așa mai departe, până când regula de oprire este îndeplinită. Metodele diferă între ele prin alegerea punctului de plecare, regula pentru formarea de noi clustere și regula de oprire. Cel mai frecvent utilizat algoritm K-mean.

Concluzie

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

În acest caz, se folosește un model de cluster pentru reprezentarea obiectelor - obiectele cu proprietăți similare aparțin aceleiași clase.

Analiza clusterului include un set de algoritmi de clasificare diferiți (un exemplu de metodă de analiză cluster este metoda dendrogramelor).

În același timp, 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ă discriminante care vă permit să determinați limitele dintre clustere și să le utilizați pentru a rezolva problemele de analiză și clasificare a datelor.

Rezultatele analizei cluster sunt cel mai adesea prezentate grafic, sub forma unei dendrograme („copac”) care arată ordinea în care obiectele sunt combinate în clustere. Interpretarea unei structuri de cluster, care în multe cazuri începe cu determinarea numărului de clustere, este o provocare creativă. Pentru ca acesta să fie rezolvat eficient, cercetătorul trebuie să aibă suficiente informații despre obiectele care sunt grupate. În gruparea „supravegheată”, rezultatele pot fi prezentate ca liste de obiecte atribuite fiecărei clase.

Principalele avantaje ale analizei cluster sunt absența restricțiilor privind distribuția variabilelor utilizate în analiză; posibilitatea clasificării (grupării) 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 seturilor de variabile sau oricărei alte unități de analiză).

Enumerăm dezavantajele analizei clusterului:

Ca și 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 calitate a cercetării în sine.

El implementează o metodă inductivă de cercetare de la particular la general, care este plină de concluzii antiscientifice. În mod ideal, eșantionul pentru clasificare ar trebui să fie foarte mare, eterogen, de preferință stratificat sau randomizat. Știința se îndreaptă spre testarea ipotezelor, deci nu este nevoie să folosiți în exces analiza clusterelor. Cel mai bine este să-l folosiți pentru a testa o ipoteză despre prezența oricăror tipuri, mai degrabă decât să creați o clasificare de la zero.

Ca și în cazul oricărei metode de scalare multidimensionale, analiza clusterului are multe caracteristici asociate cu metodele interne. Care este criteriul pentru combinarea oamenilor în clustere, metoda de găsire a diferențelor, numărul de pași pentru completarea algoritmului în metoda k-means etc. prin urmare, rezultatele pot varia, deși nu semnificativ, în funcție de „setările” procedurii.

Există două grupuri de metode analiza grupului: ierarhic și neierarhic.

Principalele metode de analiză ierarhică a clusterului sunt Metoda Vecinului, Metoda Legăturii complete, Metoda Legăturii Medii și Metoda Ward. Acesta din urmă este cel mai versatil.

Există mai multe metode neierarhice, deși funcționează pe aceleași principii. În esență, acestea sunt metode iterative de fragmentare a populației inițiale. În procesul de divizare, se formează noi clustere, și așa mai departe, până când regula de oprire este îndeplinită. Metodele diferă între ele prin alegerea punctului de plecare, regula pentru formarea de noi clustere și regula de oprire. Cel mai frecvent utilizat algoritm K-mean. 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ă cunoască bine natura și condițiile prealabile ale metodelor, altfel rezultatele obținute vor fi similare cu „temperatura medie din spital. " Pentru a ne asigura că metoda aleasă este cu adevărat eficientă în acest domeniu, de regulă, se aplică 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 împărțirea inițială în grupuri. 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 neierarhice, ar trebui să acordați atenție următoarelor puncte:

Metodele non-ierarhice arată o rezistență mai mare la valori aberante, alegerea greșită a valorilor metrice, includerea variabilelor nesemnificative în baza grupării etc. Dar prețul pentru aceasta este cuvântul „a priori”. Cercetătorul ar trebui să înregistreze în prealabil numărul rezultat de clustere, regula de oprire și, dacă există un motiv, centrul de pornire al clusterului. Ultimul punct afectează semnificativ eficiența algoritmului. Dacă nu există niciun motiv pentru stabilirea artificială a acestei condiții, în general vorbind, se recomandă utilizarea metodelor ierarhice. Observăm, de asemenea, încă un punct esențial pentru ambele grupuri de algoritmi: gruparea tuturor observațiilor nu este întotdeauna soluția corectă. Poate fi mai precis să eliminați mai întâi eșantionul valorilor aberante și apoi să continuați analiza. De asemenea, este posibil să nu se stabilească un criteriu de oprire foarte ridicat.

 

Ar putea fi util să citiți:

• Instrucțiuni tipice pentru un operator, un operator de ascensor pentru întreținerea ascensoarelor;
• Descrierea postului șefului departamentului de proiectare și aprobare Descrierea postului directorului pentru elaborarea documentației de proiect;
• Cine este o strângere de fonduri: un scurt ghid al profesiei Străduiți pentru inovație și schimbare constantă;
• Memorie utilă către Asistent;
• Director interimar într-o instituție bugetară Pozițiile din organizație sunt;
• Ce este un salariu oficial și diferența acestuia față de tariful tarifar;
• Demiterea CEO-ului într-o zi liberă;
• Descrierea postului șefului biroului de trecere;