Analiza grupului. Metode de analiză a clusterelor. Metode iterative Verificarea calității grupării

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 ținând cont de toate caracteristicile grupării simultan.

Metodele KLA vă permit să rezolvați următoarele probleme:

— clasificarea obiectelor ținând cont de multe caracteristici;

— verificarea ipotezelor făcute cu privire la 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, atunci când este necesar să se stabilească prezența legăturilor în cadrul unei populații și să se încerce introducerea structurii în ea.

Pentru a scrie algoritmi KLA formalizați, se folosesc următoarele convenții:

– un set de obiecte de observare;

– a-a observație în spațiul caracteristicilor m-dimensionale ();

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

– valori normalizate ale variabilelor originale;

– matricea distanțelor dintre obiecte.

Pentru a implementa orice metodă KLA, este necesar să se introducă conceptul de „asemănare obiect”. Mai mult, în timpul procesului de clasificare, fiecare grup ar trebui să includă obiecte care sunt cel mai asemănătoare între ele în ceea ce privește variabilele observate.

Pentru a cuantifica asemănarea, este introdus 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. În mod obișnuit, sunt utilizate următoarele măsuri ale distanței dintre obiecte:

- Distanta euclidiana ;

— distanța euclidiană ponderată ;

— distanța oraș-bloc ;

— Distanța Mahalanobis,

unde este distanța dintre al-lea și al-lea obiect;

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

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

– matricea generală de covarianță;

– ponderea atribuită variabilei-a.

Toate metodele KLA pot fi împărțite în două grupe: ierarhice (aglomerative și divizionare) și iterative (metoda mediilor, metoda de căutare a condensărilor).

Analiza clusterului ierarhic. Dintre toate metodele de analiză a clusterelor, cea mai comună este algoritmul de clasificare aglomerativă. Esența agrogritului este că, la primul pas, fiecare obiect eșantion este considerat un grup separat. Procesul de îmbinare 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 întregul proces de îmbinare este finalizat în pași (). Ca rezultat, toate obiectele vor fi combinate într-un singur cluster.

Secvența de asociere poate fi reprezentată ca o dendrogramă, prezentată în Figura 3.1. Dendrograma arată că la primul pas al doilea și al treilea obiect au fost combinate într-un singur grup cu o distanță între ele de 0,15. La al doilea pas, primul obiect le-a alăturat. Distanța de la primul obiect până la grupul care conține al doilea și al treilea obiect este de 0,3 etc.

Multe metode de analiză a clusterelor ierarhice diferă prin algoritmi de combinație (similaritate), dintre care cei mai des întâlniți sunt: metoda legăturii unice, metoda legăturii complete, metoda legăturii medii și metoda Ward.

Metoda conexiunilor complete - un obiect nou este inclus într-un cluster numai dacă asemănarea dintre toate obiectele nu este mai mică decât un anumit nivel de similitudine (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 nivel de prag specificat. Dacă vorbim despre combinarea a două grupuri, atunci se calculează o măsură a similitudinii dintre centrele lor și se compară cu o anumită valoare de prag. Să luăm în considerare un exemplu geometric cu două clustere (Figura 1.4).

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

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

Metoda lui Ward - în 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; – numărul de obiecte din -mcluster.

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

Metoda lui Ward are ca rezultat grupuri de dimensiuni aproximativ egale, cu variații minime intracluster.

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

— normalizarea valorilor inițiale ale variabilelor;

— calcularea unei matrice de distanțe sau a unei matrice de măsuri de similitudine;

— determinarea unei perechi dintre cele mai apropiate obiecte (clustere) și combinarea acestora conform algoritmului selectat;

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

Măsura similarității pentru combinarea a două grupuri este determinată de următoarele metode:

— metoda „cel mai apropiat vecin” – gradul de similitudine dintre clustere se apreciază prin gradul de asemănare dintre obiectele cele mai asemănătoare (cel mai apropiate) ale acestor clustere;

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

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

- metoda conexiunii mediane - distanța dintre orice cluster S și un nou cluster, care a fost obținută ca urmare a combinării clusterelor p și q, este definită ca distanța de la centrul clusterului S la mijlocul segmentului care leagă centrele de clustere p și q.

Metodă de căutare a condensului. Una dintre metodele de clasificare iterativă este algoritmul de căutare în cluster. Esența algoritmului iterativ al acestei metode este utilizarea unei hipersfere cu o rază dată, care se mișcă în spațiul caracteristicilor de clasificare pentru a căuta concentrații locale de obiecte.

Metoda de căutare a condensărilor necesită, în primul rând, calcularea unei matrice de distanțe (sau a unei matrice de măsuri de similitudine) între obiecte și selectarea centrului inițial al sferei. De obicei, la prima etapă, centrul sferei este obiectul (punctul) în a cărui imediată apropiere 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 (vector al valorilor medii caracteristice) pentru ele.

Când următoarea recalculare a coordonatelor centrului sferei conduce la același rezultat ca în pasul precedent, mișcarea sferei se oprește, iar punctele care se încadrează în ea formează un grup și sunt excluse din procesul de grupare ulterioară. Procedurile de mai sus se repetă pentru toate punctele rămase. Algoritmul este finalizat într-un număr finit de pași și toate punctele sunt distribuite între grupuri. Numărul de clustere formate este necunoscut î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 selecta raza unei sfere. Dacă este distanța dintre al-lea și al-lea obiect, atunci alegeți ca limită inferioară a razei (), iar limita superioară a razei poate fi definită ca .

Dacă porniți algoritmul cu o valoare și o modificați cu o valoare mică de fiecare dată când se repetă, 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 să se clasifice cinci întreprinderi utilizând analiza cluster aglomerativă ierarhică.

Tabelul 1.1

Aici: – costul mediu anual al activelor fixe de producție, miliarde de ruble; – costurile materiale pentru o rublă de produse fabricate, copeici; – volumul produselor produse, miliarde de ruble.

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

Matricea valorilor variabilelor normalizate va arăta ca

Vom efectua clasificarea folosind 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, reprezintă un grup separat.

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

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

În matrice găsim din nou clusterele cele mai apropiate. Acestea vor fi și , . Prin urmare, la acest pas combinăm și clusterele; obținem 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, în pasul următor combinăm clustere și într-un singur cluster și îi atribuim un număr. Acum avem doar două grupuri:

Și în final, în ultimul pas vom combina clusterele 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 care intră, deoarece în el uniunea a avut loc la distanțe mai scurte decât în cluster.

Figura 3.5. Dendrograma grupării a cinci obiecte

Exemplul 2. Pe baza datelor prezentate mai jos, clasificați magazinele după trei criterii: – suprafață de vânzare, m2, – cifra de afaceri per vânzător, den. unități, – nivelul de rentabilitate, %.

Numărul magazinului				Numărul magazinului

Pentru a clasifica magazinele, utilizați metoda de căutare în cluster (trebuie să selectați primul cluster).

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

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

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

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

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

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

Analiza grupului(CLA) este un set de metode de clasificare multidimensionale, 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 ținând cont de toate caracteristicile grupării simultan.

Metodele KLA vă permit să rezolvați următoarele probleme:

Efectuarea clasificării obiectelor ținând cont de multe caracteristici;

Verificarea ipotezelor făcute cu privire la 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, atunci când este necesar să se stabilească prezența legăturilor în cadrul unei populații și să se încerce introducerea structurii în ea.

Pentru a scrie algoritmi KLA formalizați, se folosesc următoarele convenții:

– un set de obiecte de observare;

– a-a observație în spațiul caracteristicilor m-dimensionale ();

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

– valori normalizate ale variabilelor originale;

– matricea distanțelor dintre obiecte.

distanta euclidiana ;

Distanța euclidiană ponderată ;

Distanța oraș-bloc ;

distanta Mahalanobis,

unde este distanța dintre al-lea și al-lea obiect;

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

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

– matricea generală de covarianță;

– ponderea atribuită variabilei-a.

Toate metodele KLA pot fi împărțite în două grupe: ierarhice (aglomerative și divizionare) și iterative (metoda mediilor, metoda de căutare a condensărilor).

Metoda completă a legăturii– includerea unui nou obiect într-un cluster are loc numai dacă asemănarea dintre toate obiectele nu este mai mică decât un anumit nivel specificat de similitudine (Figura 1.3).

Metoda medie a linkului– 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 nivel de prag specificat. Dacă vorbim despre combinarea a două grupuri, atunci se calculează o măsură a similitudinii dintre centrele lor și se compară cu o anumită valoare de prag. Să luăm în considerare un exemplu geometric cu două clustere (Figura 1.4).

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

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

metoda lui Ward– la primul pas, fiecare cluster 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; – numărul de obiecte în - mcluster.

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

Metoda lui Ward are ca rezultat grupuri de dimensiuni aproximativ egale, cu variații minime intracluster.

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

Normalizarea valorilor inițiale ale variabilelor;

Calcularea unei matrice de distanțe sau a unei matrice de măsuri de similitudine;

Determinarea unei perechi dintre cele mai apropiate obiecte (clustere) și combinarea acestora conform algoritmului selectat;

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

Măsura similarității pentru combinarea a două grupuri este determinată de următoarele metode:

Metoda „cel mai apropiat vecin” – gradul de similitudine dintre clustere este evaluat prin gradul de similaritate dintre obiectele cele mai asemănătoare (cel mai apropiate) ale acestor clustere;

Metoda „vecinului îndepărtat” – gradul de similitudine se apreciază prin gradul de asemănare dintre obiectele cele mai îndepărtate (disimilare) ale clusterelor;

Metoda medie a conexiunii – gradul de similaritate este estimat ca valoarea medie a gradelor de similaritate dintre obiectele din clustere;

Metoda legăturii mediane - distanța dintre orice cluster Sși un nou cluster, care a rezultat din fuziunea clusterelor RȘi q, definită ca distanța de la centrul clusterului S până la mijlocul segmentului care leagă centrii clusterului RȘi q.

Metoda de căutare a condensului. Una dintre metodele de clasificare iterativă este algoritmul de căutare în cluster. Esența algoritmului iterativ al acestei metode este utilizarea unei hipersfere cu o rază dată, care se mișcă în spațiul caracteristicilor de clasificare pentru a căuta concentrații locale de obiecte.

Metoda de căutare a condensărilor necesită, în primul rând, calcularea unei matrice de distanțe (sau a unei matrice de măsuri de similitudine) între obiecte și selectarea centrului inițial al sferei. De obicei, la prima etapă, centrul sferei este obiectul (punctul) în a cărui imediată apropiere se află cel mai mare număr de vecini. Bazat pe o rază dată de sferă (R) se determină un set de puncte care se încadrează în această sferă și se calculează coordonatele centrului (vector al valorilor medii ale caracteristicilor).

Există mai multe moduri de a selecta raza unei sfere. Dacă este distanța dintre al-lea și al-lea obiect, atunci alegeți , iar limita superioară a razei poate fi definită ca .

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

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

Matricea valorilor variabilelor normalizate va arăta ca

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

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

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

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

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

Și în final, în ultimul pas vom combina clusterele 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 în el uniunea a avut loc la distanțe mai scurte decât în cluster.

Figura 3.5. Dendrograma grupării a cinci obiecte

Exemplul 2. Pe baza datelor prezentate mai jos, clasificați magazinele după trei criterii: – suprafață de vânzare, m2, – cifra de afaceri per vânzător, den. unități, – nivelul de rentabilitate, %.

Numărul magazinului				Numărul magazinului

Pentru a clasifica magazinele, utilizați metoda de căutare în cluster (trebuie să selectați primul cluster).

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

unde , sunt valorile standardizate ale variabilelor inițiale pentru al-lea și, respectiv, al-lea obiect; T– numărul de semne.

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

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

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

Pentru șase puncte (obiecte 1, 2, 3, 6, 7, 8) determinăm coordonatele centrului de greutate: .

4. La pasul următor al algoritmului, plasăm centrul sferei într-un punct și determinăm distanța fiecărui obiect până la noul centru.

Una dintre metodele de clasificare iterativă care nu necesită specificarea numărului de clustere este metoda de căutare a clusterelor. Metoda necesită calcularea unei matrice de distanțe, apoi selectarea unui 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 centru al unei hipersfere cu o rază R dată. Se determină setul de puncte care se încadrează în interiorul acestei sfere și se calculează coordonatele centrului (vector al valorilor medii caracteristice) pentru ele. Apoi, se ia în considerare o hipersferă de aceeași rază, dar cu un centru nou, iar pentru setul de puncte care se încadrează în ea, se calculează din nou un vector de valori 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 anterior, 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. În esență, sunt metode iterative de fragmentare a populației originale. În timpul procesului de divizare, se formează noi clustere și așa mai departe până când regula de oprire este îndeplinită. Metodele diferă între ele în alegerea punctului de plecare, în regula formării de noi clustere și în 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 de cluster pentru reprezentarea obiectelor - obiectele cu proprietăți similare aparțin aceleiași clase.

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

Î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 fac posibilă determinarea granițelor dintre clustere și utilizarea acestora pentru rezolvarea problemelor de analiză și clasificare a datelor.

Rezultatele analizei cluster sunt cel mai adesea prezentate grafic, sub forma unei dendrograme („arborele”), care arată ordinea combinării obiectelor în clustere. Interpretarea structurii clusterului, care în multe cazuri începe cu determinarea numărului de clustere, este o sarcină creativă. Pentru ca acesta să fie rezolvat eficient, cercetătorul trebuie să aibă suficiente informații despre obiectele care sunt grupate. Cu gruparea supravegheată, rezultatele pot fi prezentate sub formă de 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ă).

Să enumeram 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 cercetării în sine.

El implementează o metodă de cercetare inductivă 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 se îndreaptă pe calea testării ipotezelor, așa că nu este nevoie să folosiți în exces analiza clusterelor. Cel mai bine este să îl utilizați pentru a testa ipoteza despre prezența oricăror tipuri, mai degrabă decât 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 combinare a oamenilor în clustere, metoda de găsire a diferențelor, numărul de pași până la finalizarea algoritmului în metoda k-means etc. prin urmare, rezultatele pot varia, deși nesemnificativ, î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 cel mai apropiat, metoda legăturii complete, metoda legăturii medii și metoda Ward. Ultima este cea mai universală.

Există mai multe metode neierarhice, deși funcționează pe aceleași principii. În esență, sunt metode iterative de fragmentare a populației originale. În timpul procesului de divizare, se formează noi clustere și așa mai departe până când regula de oprire este îndeplinită. Metodele diferă între ele în alegerea punctului de plecare, în regula formării de noi clustere și în 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 obținute vor fi similare cu „temperatura medie din spital”. Pentru a se asigura că metoda aleasă este cu adevărat eficientă într-o anumită zonă, de regulă, se utilizează următoarea procedură:

Sunt luate în considerare mai multe grupuri diferite a priori, iar reprezentanții lor sunt amestecați la întâmplare. Apoi se efectuează o procedură de grupare pentru a restabili diviziunea inițială în grupuri. Un indicator al eficacității metodei va fi proporția de potriviri între obiectele din grupurile identificate și cele originale.

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 valorilor, includerea variabilelor nesemnificative în baza grupării etc. Dar prețul pentru aceasta este cuvântul „a priori”. Cercetătorul trebuie să înregistreze în prealabil numărul rezultat de clustere, regula de oprire și, dacă este justificat, centrul de cluster inițial. Ultimul punct afectează semnificativ eficiența algoritmului. Dacă nu există niciun motiv pentru a stabili artificial această condiție, în general, se recomandă utilizarea metodelor ierarhice. Să mai notăm și un punct care este esențial pentru ambele grupuri de algoritmi: gruparea tuturor observațiilor nu este întotdeauna soluția potrivită. Poate fi mai atent să ștergeți mai întâi eșantionul de valori aberante și apoi să continuați analiza. De asemenea, este posibil să nu setați criteriul de oprire foarte ridicat.

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

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

k-means algoritm

Cel mai frecvent printre metodele non-ierarhice k-means algoritm, numit si analiză rapidă a clusterelor. O descriere completă a algoritmului poate fi găsită în Hartigan și Wong (1978). Spre deosebire de metodele ierarhice, care nu necesită ipoteze preliminare privind numărul de clustere, pentru a putea folosi această metodă, este necesar să existe o ipoteză despre numărul cel mai probabil de clustere.

k-means algoritm construiește k clustere situate la distanțe cât mai mari unele de altele. Principalul tip de probleme pe care le rezolvă k-means algoritm, - prezența ipotezelor (ipotezelor) privind numărul de clustere, iar acestea să fie cât mai diferite. Alegerea lui k se poate baza pe cercetări anterioare, considerații teoretice sau intuiție.

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

Descrierea algoritmului

Distribuția inițială a obiectelor în clustere.
Se selectează numărul k, iar în primul pas aceste puncte sunt considerate „centrele” clusterelor. Fiecare grup corespunde unui centru.

Selectarea centroizilor inițiali se poate face după cum urmează:
- selectarea k-observațiilor pentru a maximiza distanța inițială;
- selecția aleatorie a k-observațiilor;
- selectarea primelor k-observaţii.
Ca rezultat, fiecare obiect este alocat unui anumit cluster.
Proces iterativ.
Calculat centre de cluster, care sunt apoi și mai departe considerate a fi medii în funcție de coordonate ale clusterelor. Obiectele sunt redistribuite.

Procesul de calculare a centrelor și de redistribuire a obiectelor continuă până când este îndeplinită una dintre condiții:
- centrele cluster s-au stabilizat, adică toate observațiile aparțin clusterului căruia i-au aparținut î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 operare k-means algoritm pentru k egal cu doi.

Orez. 14.1.

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.

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

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 o combinaţie a acestora.

Pentru a efectua clasificarea datelor X x,...,X p utilizați conceptul de metrică sau distanță.

Metrica este o funcție p care mapează un anumit 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 w k - ponderi proporționale cu importanța unei caracteristici într-o problemă de clasificare. Greutățile sunt stabilite după cercetări suplimentare

și presupunem că ^w* = 1;

3) Distanța de hamming (sau bloc) - distanța pe hartă între blocurile din oraș

4) Distanța Mahalanobis (sau unghiul Mahalanobis)

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

Alegerea metricii se face de către cercetător în funcție de ce rezultat dorește să obțină. Această alegere nu este formalizabilă, 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 cluster.

Lăsa S (- al-lea cluster format din n t vectori sau puncte. Lăsa

X (l) - media eșantionului de puncte 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 „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ța generalizată Kolmogorov

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

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

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

când a =---, p =---,5 = 0, y = 0 - distanța de-a lungul centrelor de greutate

p k + n i p k + n i

grupuri sti.

Metodele de analiză a clusterelor sunt împărțite în I) aglomerative (unificatoare), II) diviziale (divizoare) și III) iterative.

Primele unesc secvențial obiectele individuale în grupuri, cele din urmă, dimpotrivă, împart grupurile în obiecte. Al treilea le combină pe primele două. Caracteristica lor este formarea de clustere pe baza condițiilor de partiție (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 de aglomerare. Metodele aglomerative sunt cele mai simple și mai comune dintre algoritmii de analiză a clusterelor. În primul pas, fiecare vector sau obiect X 19...,X p datele sursă sunt considerate ca un cluster sau o clasă separată. Pe baza matricei de distanțe calculate, cele mai apropiate unele de altele sunt selectate și combinate. Evident, procesul se va încheia în (P - 1) pas când, ca rezultat, toate obiectele vor fi combinate într-un singur grup.

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

La a doua etapă, vectorul a fost atașat de ei X 3, la distanță 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 de aglomerare includ conexiune unică, medie, completă și metoda lui Ward.

1.Metoda de conectare unică. Lăsa Xv...,Xn - date vectoriale, fiecare vector formând un grup. Mai întâi, se calculează o matrice a distanțelor dintre aceste clustere, folosind distanța vecină cea mai apropiată 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 ] iar vectorii rămași (pe care îi considerăm clustere), se calculează o nouă matrice de distanțe, iar distanța dintre clustere combinate în clase este utilizată ca metrică (a = p = 1/2, 5 = -1/2, y = 0). Cel mai apropiat de clasa obținută anterior S ( clusterul se contopește cu acesta, formându-se S 2. etc. Via 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 sursă (rotație, deplasare, translație, întindere).

Defecte: 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 anumit număr predeterminat. Numărul este specificat 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 cu oc = p = 8 = 1/2, y = 0).
3.Metoda medie de conectare. Algoritmul de formare a clusterului coincide cu algoritmul de conexiune unică, totuși, atunci când se decide dacă se include un nou obiect într-un cluster, calculele se fac conform principiului conexiunii medii. Ca și în metoda de legătură completă, toate distanțele calculate între 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 legătură medie diferă de metoda de legătură completă doar prin modul în care calculează distanța dintre clustere.
4. metoda WARD. Lăsa X 19...,X p- date, fiecare vector formând un grup. Găsim matricea distanțelor folosind o metrică (de exemplu, distanța Mahalanobis) și o folosim pentru a determina clusterele care sunt cele mai apropiate unul de celălalt. Calculăm suma abaterilor pătrate ale vectorilor din cluster S k dupa formula:

Unde La - numărul grupului, eu- numărul vectorului din cluster, j- numărul de coordonate Xt e U1 R, p la- numărul de vectori din cluster, X jk- media eșantionului X i V S k. Magnitudinea Vk caracterizează abaterile vectorilor unul față de celălalt în cadrul unui cluster (nou S k + S f sau vechi^). Calcul Vk ar trebui efectuată înainte și după fuziune și este necesar să parcurgem toate opțiunile posibile pentru astfel de asociații. Mai târziu în cluster S k se adaugă doar acei vectori sau clustere care au ca rezultat cea mai mică modificare Vk după comasare și, în consecință, care va fi situat la o distanță minimă de clusterul inițial S k.

Să luăm în continuare în considerare metodele iterative. Esența metodelor iterative este că gruparea începe cu stabilirea unor condiții inițiale. De exemplu, este necesară setarea numărului de clustere rezultate sau setarea distanței 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 de obicei specificate folosind o soluție găsită prin una dintre metodele aglomerative. Metodele iterative includ metoda ^-mediilor și metoda de căutare a condensărilor.

1. metoda /r-means. Să fie vectori X l9 ...,X n e9F și trebuie împărțite în La clustere. La pasul zero de la P selectați aleatoriu vectori La dintre ele, având în vedere că fiecare formează un grup. Obținem un set de clustere standard,...,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, euclidiană:

Pe baza cunoștințelor matricei distanțelor calculate, vectorul X ( plasat în standardul a cărui distanță este minimă. Să presupunem cu certitudine că asta 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 Xt incluse în clusterul cu cel mai mic număr de serie.

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

standard e^~ k) greutatea se va potrivi și procedura de grupare se va încheia. Cu 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 cantitate și compoziție cu standardele găsite la repetarea metodei. Cu toate acestea, procedura algoritmică se repetă întotdeauna de mai multe ori, folosind partiția obținută în calculele anterioare ca vectori standard (ca aproximare inițială): standarde găsite anterior e[ p k e (2 p k) k) sunt luate pentru e (x 0) 9 ... 9 e (k 0) 9 iar procedura algoritmică se repetă.

2. Metodă de căutare a condensului. Acesta este următorul algoritm iterativ. Nu necesită o specificare a priori a numărului de clustere. La prima etapă, matricea distanțelor dintre X X9 ... 9 X p eU1 r conform unor metrici. Apoi un vector este selectat aleatoriu pentru a acționa ca centru al primului cluster. Aceasta este o aproximare 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ă aceasta se determină vectorii X Si ,... 9 X Sk , care se încadrează în această sferă, iar din ele se calculează alegerea
- 1 La

așteptări matematice fixe X = ~Y]X 5. Apoi centrul sferei este re-

este purtat in X, iar procedura de calcul se repetă. Condiția pentru încheierea procesului iterativ este egalitatea vectorilor de 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 grupării nu are o singură soluție. În consecință, este destul de dificil să enumerați toate partițiile admisibile ale datelor în clase și nu este întotdeauna posibilă. Pentru a evalua calitatea diferitelor metode de clustering, este introdus conceptul de funcțional al calității partiției, care ia valoarea minimă pe cea mai bună (din punctul de vedere al cercetătorului) partiție.

Lăsa X X9 ... 9 X p e U1 R - un anumit 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 ale calității partiției 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ă evaluăm gradul de omogenitate al tuturor clusterelor în ansamblu.

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

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

3) Varianta generalizată intraclasă

Unde n j- numărul de elemente în S., A; . - 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ă permite estimarea gradului de dispersie a observațiilor multivariate. De aceea Q 3 (S) vă permite să estimați răspândirea medie a vectorilor de observație în clase S l9 ... 9 S k . De aici și numele său - varianță generalizată intraclasă. 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 de asemenea evaluată folosind criteriul Hotelling. Pentru a face acest lucru, aplicăm un criteriu pentru a testa ipoteza H 0 asupra egalității vectorilor mediilor a două populații multidimensionale și calculați statisticile

Unde n tȘi p t - numărul de vectori din clase Sl,Sm; X,X t- date sursă centrate; S* - matrice de covarianță grupată 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-os) dacă Q 4 (S) n _ m, și este respins în caz contrar.

Calitatea împărțirii în clase poate fi, de asemenea, evaluată empiric. De exemplu, puteți 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 î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 în S = (S l9 ...,S k) este necunoscut în prealabil, apoi utilizați următoarele funcționale ale calității partiției pentru un număr întreg ales arbitrar m:

eueuLa 1 1 m

- - măsura medie în cadrul unei clase -

P i=1 n i XjeSj X"tSj J

împrăștiere bufniță,

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

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 Zm(S) atinge un minim egal cu eu/p, dacă gruparea inițială S = (S l9 ...,S k ) este o partiție în clustere mono S. = (Xj), deoarece V(X t) = 1. În același timp Zm(S) ajunge la maximum 1 dacă S- un cluster care conține toate datele originale,

deoarece V(X() = n.În cazuri speciale 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ției este funcțională Î(E) poate fi ales sub forma unei combinații algebrice (sumă, diferență, produs, raport) a două funcționale I m (S), Z m (S),întrucât prima este o funcţie descrescătoare iar cealaltă o funcţie crescătoare a numărului de clase La. Un astfel de comportament Zm(S)

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