Trimiteți-vă munca bună în baza de cunoștințe este simplu. Foloseste formularul de mai jos
Studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vor fi foarte recunoscători.
Găzduit la http://www.allbest.ru/
Introducere
1. Definirea și sarcinile analizei cluster
2. Metode de analiză a clusterelor
3. Dendograme
Concluzie
Bibliografie
Introducere
analiza grupului- acesta este un set de metode care vă permit să clasificați observațiile multidimensionale. Termenul de analiză de cluster, introdus pentru prima dată de Tryon în 1939, include peste 100 de algoritmi diferiți.
Spre deosebire de problemele de clasificare, analiza cluster nu necesită ipoteze a priori despre setul de date, nu impune restricții privind reprezentarea obiectelor studiate și vă permite să analizați indicatori ai diferitelor tipuri de date (date de interval, frecvențe, date binare) . Trebuie amintit că variabilele trebuie măsurate pe scale comparabile.
Analiza cluster vă permite să reduceți dimensiunea datelor și să le faceți vizuale.
Analiza cluster este utilizată pentru a identifica grupuri de puncte din date care sunt în mod clar diferite unele de altele. Importanța rezolvării acestei probleme se datorează faptului că utilizarea instrumentelor standard de analiză a datelor (inclusiv proceduri econometrice standard) în prezența clusterelor în date va duce la o schimbare atât a estimărilor punctuale (coeficienți de regresie), cât și a erorilor standard, și deci la concluzii statistice incorecte. În plus, structura datelor și similitudinea observațiilor pot fi de interes independent.
Analiza clusterelor este concepută pentru a împărți un set de obiecte în grupuri omogene (clustere sau clase). În esență, aceasta este o sarcină de clasificare a datelor multidimensionale.
1. Definirea și sarcinile analizei cluster
Atunci când analizează și prognozează fenomene socio-economice, cercetătorul întâlnește adesea multidimensionalitatea descrierii acestora. Acest lucru se întâmplă atunci când se rezolvă problema segmentării pieței, se construiește o tipologie de țări în funcție de un număr suficient de mare de indicatori, se prezice situația pieței pentru bunuri individuale, se studiază și se prevede depresia economică și multe alte probleme.
Metodele de analiză multivariată reprezintă cel mai eficient instrument cantitativ pentru studierea proceselor socio-economice descrise printr-un număr mare de caracteristici. Acestea includ analiza clusterului, taxonomia, recunoașterea modelelor, analiza factorilor.
Analiza cluster reflectă cel mai clar caracteristicile analizei multivariate în clasificare, analiza factorială - în studiul comunicării.
Uneori, abordarea analizei cluster este menționată în literatură ca taxonomie numerică, clasificare numerică, recunoaștere prin auto-învățare etc.
Analiza cluster și-a găsit prima aplicație în sociologie. Numele de analiză a grupului provine din cuvântul englezesc cluster - bunch, cluster. Pentru prima dată în 1939, subiectul analizei cluster a fost definit și descrierea acestuia a fost făcută de către cercetătorul Trion. Scopul principal al analizei cluster este de a împărți setul de obiecte și caracteristici studiate în grupuri sau clustere care sunt omogene în sensul corespunzător. Aceasta înseamnă că problema clasificării datelor și identificării structurii corespunzătoare din acestea este în curs de rezolvare. Metodele de analiză a clusterelor pot fi aplicate într-o varietate de cazuri, chiar și atunci când este vorba de o simplă grupare, în care totul se reduce la formarea grupurilor prin similitudine cantitativă.
Marele avantaj al analizei cluster este că vă permite să partiționați obiectele nu după un parametru, ci după un întreg set de caracteristici. În plus, analiza cluster, spre deosebire de majoritatea metodelor matematice și statistice, nu impune nicio restricție asupra tipului de obiecte luate în considerare și ne permite să luăm în considerare un set de date inițiale de natură aproape arbitrară. Acest lucru este de mare importanță, de exemplu, pentru prognoza conjuncturii, când indicatorii au o varietate de forme care fac dificilă utilizarea abordărilor econometrice tradiționale.
Analiza cluster face posibilă luarea în considerare a unei cantități suficient de mare de informații și reducerea drastică, comprimarea unor palete mari de informații socio-economice, făcându-le compacte și vizuale.
Analiza clusterelor este de mare importanță în raport cu seturile de serii cronologice care caracterizează dezvoltarea economică (de exemplu, condițiile economice generale și ale mărfurilor). Aici este posibil să se evidențieze perioadele în care valorile indicatorilor corespunzători au fost destul de apropiate, precum și să se determine grupurile de serii temporale, a căror dinamică este cel mai asemănătoare.
Analiza cluster poate fi utilizată ciclic. În acest caz, studiul se efectuează până la obținerea rezultatelor dorite. În același timp, fiecare ciclu de aici poate oferi informații care pot schimba foarte mult direcția și abordările de aplicare ulterioară a analizei cluster. Acest proces poate fi reprezentat ca un sistem de feedback.
În sarcinile de prognoză socio-economică, este foarte promițător să se combine analiza clusterului cu altele metode cantitative(de exemplu, cu analiza de regresie).
Ca orice altă metodă, analiza clusterului are anumite dezavantaje și limitări: în special, compoziția și numărul de clustere depind de criteriile de partiționare selectate. La reducerea matricei de date inițiale la o formă mai compactă, pot apărea anumite distorsiuni, iar caracteristicile individuale ale obiectelor individuale pot fi, de asemenea, pierdute din cauza înlocuirii lor cu caracteristicile valorilor generalizate ale parametrilor clusterului. La clasificarea obiectelor, de foarte multe ori este ignorată posibilitatea absenței oricăror valori de grup în setul considerat.
În analiza clusterului, se consideră că:
a) caracteristicile selectate permit, în principiu, gruparea dorită;
b) unitățile de măsură (scara) sunt alese corect.
Alegerea scalei joacă un rol important. De obicei, datele sunt normalizate prin scăderea mediei și împărțirea la abaterea standard, astfel încât varianța să fie egală cu unu.
Sarcina analizei cluster este de a împărți mulțimea de obiecte G în m (m - întreg) clustere (subseturi) Q1, Q2, ..., Qm, pe baza datelor conținute în mulțimea X, astfel încât fiecare obiect Gj să aparțină la unul și doar un subset de partiții și că obiectele aparținând aceluiași cluster sunt similare, în timp ce obiectele aparținând unor clustere diferite sunt eterogene.
De exemplu, să fie G să includă n țări, fiecare dintre acestea fiind caracterizată de PNB pe cap de locuitor (F1), numărul M de mașini la 1.000 de persoane (F2), consumul de energie electrică pe cap de locuitor (F3), consumul de oțel pe cap de locuitor (F4), etc. Atunci X1 (vector de măsurare) este un set de caracteristici specificate pentru prima țară, X2 pentru a doua, X3 pentru a treia și așa mai departe. Provocarea este de a defalca țările după nivelul de dezvoltare.
Soluția problemei analizei cluster sunt partițiile care îndeplinesc un anumit criteriu de optimitate. Acest criteriu poate fi unul funcțional care exprimă nivelurile de dezirabilitate ale diferitelor partiții și grupări, care se numește funcție obiectiv. De exemplu, suma intragrupului a abaterilor pătrate poate fi luată ca funcție obiectiv:
unde xj - reprezintă măsurătorile obiectului j-lea.
Pentru a rezolva problema analizei cluster, este necesar să se definească conceptul de similaritate și eterogenitate.
Este clar că obiectele i-lea și j-lea ar cădea în același grup atunci când distanța (distanța) dintre punctele Xi și Xj ar fi suficient de mică și ar cădea în grupuri diferite când această distanță ar fi suficient de mare. Astfel, intrarea în unul sau mai multe grupuri de obiecte este determinată de conceptul distanței dintre Xi și Xj față de Ep, unde Ep este un spațiu euclidian p-dimensional. O funcție nenegativă d(Xi, Xj) se numește funcție de distanță (metrică) dacă:
a) d(Xi , Xj) i 0, pentru toate Xi și Xj din Ep
b) d(Xi, Xj) = 0 dacă și numai dacă Xi = Xj
c) d(Xi, Xj) = d(Xj, Xi)
d) d(Xi, Xj) J d(Xi, Xk) + d(Xk, Xj), unde Xj; Xi și Xk sunt oricare trei vectori din Ep.
Valoarea d(Xi, Xj) pentru Xi și Xj se numește distanța dintre Xi și Xj și este echivalentă cu distanța dintre Gi și Gj în funcție de caracteristicile selectate (F1, F2, F3, ..., Fр).
Cele mai frecvent utilizate funcții de distanță sunt:
1. Distanța euclidiană
2. l1 - normă
4. Supremum este norma
dҐ (Хi , Хj) = sup
k = 1, 2, ..., p
5. lp - normă
dр(Хi , Хj) =
Metrica euclidiană este cea mai populară. Valoarea l1 este cea mai ușor de calculat. Norma supremă este ușor de calculat și include o procedură de ordonare, în timp ce norma-lp acoperă funcțiile de distanță 1, 2, 3,.
Fie n măsurători X1, X2,..., Xn să fie reprezentate ca o matrice de date p × n:
Atunci distanța dintre perechile de vectori d(Хi , Хj) poate fi reprezentată ca o matrice de distanțe simetrice:
Conceptul opus distanței este conceptul de similitudine între obiectele Gi. iar Gj. O funcție reală nenegativă S(Хi ; Хj) = Sij se numește măsură de similitudine dacă:
1) 0Ј S(Хi , Хj)<1 для Хi № Хj
2) S(Хi , Хi) = 1
3) S(Xi, Xj) = S(Xj, Xi)
Perechile de valori de măsurare a similitudinii pot fi combinate într-o matrice de similaritate:
Valoarea lui Sij se numește coeficient de similitudine.
2. Metode de analiză a clusterelor
Metodele de analiză a grupurilor pot fi împărțite în două grupe:
* ierarhic;
* neierarhic.
Fiecare dintre grupuri include multe abordări și algoritmi.
Folosind diferite metode de analiză a clusterelor, un analist poate obține soluții diferite pentru aceleași date. Acest lucru este considerat normal. Luați în considerare metodele ierarhice și non-ierarhice în detaliu.
Esența grupării ierarhice este îmbinarea secvențială a clusterelor mai mici în clustere mai mari sau împărțirea clusterelor mari în altele mai mici.
Metode aglomerative ierarhice (Agglomerative Nesting, AGNES) Acest grup de metode se caracterizează printr-o unire consistentă a elementelor originale și o scădere corespunzătoare a numărului de clustere.
La începutul algoritmului, toate obiectele sunt grupuri separate. La primul pas, cele mai asemănătoare obiecte sunt combinate într-un grup. În pașii următori, fuziunea continuă până când toate obiectele formează un grup. Metode ierarhice divizibile (divizibile) (ANALIZA DIVISIVE, DIANA) Aceste metode sunt opusul logic al metodelor aglomerative. La începutul algoritmului, toate obiectele aparțin unui grup, care este împărțit în grupuri mai mici la pașii următori, ca urmare, se formează o secvență de grupuri de împărțire.
Metodele neierarhice relevă rezistență mai mare la zgomot și valori aberante, alegerea incorectă a metricii, includerea variabilelor nesemnificative în setul implicat în clustering. Prețul care trebuie plătit pentru aceste avantaje ale metodei este cuvântul „a priori”. Analistul trebuie să predetermina numărul de clustere, numărul de iterații sau regula de oprire, precum și alți parametri de clustering. Acest lucru este deosebit de dificil pentru începători.
Dacă nu există ipoteze cu privire la numărul de clustere, se recomandă utilizarea algoritmilor ierarhici. Cu toate acestea, dacă dimensiunea eșantionului nu permite acest lucru, o modalitate posibilă este de a efectua o serie de experimente cu un număr diferit de grupuri, de exemplu, începeți împărțirea setului de date din două grupuri și, crescând treptat numărul acestora, comparați rezultatele. Datorită acestei „variații” a rezultatelor, se obține o flexibilitate de grupare suficient de mare.
Metodele ierarhice, spre deosebire de cele non-ierarhice, refuză să determine numărul de clustere, dar construiesc un arbore complet de clustere imbricate.
Complexitatea metodelor de clustering ierarhic: limitarea volumului setului de date; alegerea măsurii de proximitate; inflexibilitatea clasificărilor obţinute.
Avantajul acestui grup de metode în comparație cu metodele neierarhice este claritatea lor și capacitatea de a obține o idee detaliată a structurii datelor.
Când se utilizează metode ierarhice, este posibil să se identifice valorile aberante dintr-un set de date destul de ușor și, ca rezultat, să se îmbunătățească calitatea datelor. Această procedură stă la baza algoritmului de grupare în doi pași. Un astfel de set de date poate fi folosit ulterior pentru clustering non-ierarhic.
Există un alt aspect care a fost deja menționat în această prelegere. Aceasta este o chestiune de grupare a întregii populații de date sau eșantionul acesteia. Acest aspect este esențial pentru ambele grupuri considerate de metode, dar este mai critic pentru metodele ierarhice. Metodele ierarhice nu pot funcționa cu seturi mari de date, iar utilizarea unei anumite selecții, de ex. o parte din date ar putea permite aplicarea acestor metode.
Rezultatele grupării pot să nu aibă o justificare statistică suficientă. Pe de altă parte, la rezolvarea problemelor de clustering, este acceptabilă o interpretare non-statistică a rezultatelor obținute, precum și o varietate destul de mare de opțiuni pentru conceptul de cluster. O astfel de interpretare non-statistică permite analistului să obțină rezultate satisfăcătoare de grupare, ceea ce este adesea dificil atunci când se utilizează alte metode.
1) Metoda conexiunilor complete.
Esența acestei metode este că două obiecte aparținând aceluiași grup (cluster) au un coeficient de similaritate care este mai mic decât o anumită valoare de prag S. În ceea ce privește distanța euclidiană d, aceasta înseamnă că distanța dintre două puncte (obiecte) de clusterul nu trebuie să depășească o anumită valoare prag h. Astfel, h determină diametrul maxim admisibil al unui subset care formează un cluster.
2) Metoda distanței locale maxime.
Fiecare obiect este considerat ca un cluster cu un singur punct. Obiectele sunt grupate după următoarea regulă: două grupuri sunt combinate dacă distanța maximă dintre punctele unui grup și punctele altuia este minimă. Procedura constă din n - 1 pași și are ca rezultat partiții care se potrivesc cu toate partițiile posibile din metoda anterioară pentru orice valoare de prag.
3) Metoda Word.
În această metodă, suma intragrup a abaterilor pătrate este utilizată ca funcție obiectiv, care nu este altceva decât suma distanțelor pătrate dintre fiecare punct (obiect) și media pentru clusterul care conține acest obiect. La fiecare pas se combină două clustere care conduc la creșterea minimă a funcției obiectiv, adică. suma de pătrate intragrup. Această metodă are ca scop combinarea clusterelor strâns distanțate.
4) Metoda centroidă.
Distanța dintre două clustere este definită ca distanța euclidiană dintre centrele (mediile) acestor clustere:
d2 ij = (`X -`Y)Т(`X -`Y) Clusteringul se desfășoară pas cu pas, la fiecare din n-1 pași, două clustere G și p sunt unite, având valoarea minimă d2ij Dacă n1 este mult mai mare decât n2, atunci centrele de unire a două clustere sunt apropiate unul de celălalt, iar caracteristicile celui de-al doilea cluster sunt practic ignorate atunci când clusterele sunt combinate. Uneori, această metodă este uneori numită și metoda grupurilor ponderate.
3. Dendograme
Cea mai cunoscută metodă de reprezentare a unei matrice de distanță sau similaritate se bazează pe ideea unei dendograme sau diagramă arborescentă. Dendograma poate fi definită ca o reprezentare grafică a rezultatelor procesului de grupare secvenţială, care se realizează în termenii unei matrice de distanţe. Cu ajutorul unei dendograme, este posibilă reprezentarea grafică sau geometrică a procedurii de grupare, cu condiția ca această procedură să funcționeze numai cu elemente ale matricei de distanță sau similaritate.
Există multe moduri de a construi dendrograme. În dendrogramă, obiectele sunt situate vertical în stânga, rezultatele grupării sunt în dreapta. Valorile de distanță sau de similitudine corespunzătoare structurii noilor clustere sunt afișate de-a lungul unei linii drepte orizontale peste dendrograme.
Figura 1 prezintă un exemplu de dendogramă. Figura 1 corespunde cazului a șase obiecte (n=6) și k caracteristici (trăsături). Obiectele A și C sunt cele mai apropiate și, prin urmare, sunt combinate într-un singur grup la nivelul de proximitate egal cu 0,9. Obiectele D și E sunt combinate la un nivel de 0,8. Acum avem 4 clustere:
Tipul dendogramei depinde de alegerea măsurii de similitudine sau de distanța dintre obiect și cluster și de metoda de grupare. Cel mai important punct este alegerea unei măsuri de similitudine sau a unei măsuri a distanței dintre un obiect și un cluster.
Numărul de algoritmi de analiză cluster este prea mare. Toate pot fi împărțite în ierarhice și neierarhice.
Algoritmii ierarhici sunt asociați cu construcția dendogramelor și sunt împărțiți în:
a) aglomerativ, caracterizat printr-o combinație consistentă de elemente inițiale și o scădere corespunzătoare a numărului de clustere;
b) divizibil (divizibil), în care numărul de clustere crește, începând de la unul, în urma căruia se formează o succesiune de grupuri de scindare.
Algoritmii de analiză a clusterelor au astăzi o implementare software bună care permite rezolvarea problemelor de cea mai mare dimensiune.
Concluzie
Analiza cluster este un instrument foarte convenabil pentru identificarea segmentelor de piață. Mai ales în epoca noastră de înaltă tehnologie, când mașinile vin în ajutorul unei persoane și un proces atât de laborios devine literalmente o chestiune de secunde.
Formarea segmentelor depinde de datele disponibile și nu este determinată în prealabil.
Variabilele care stau la baza grupării ar trebui alese pe baza experienței studiilor anterioare, a fondului teoretic, a ipotezelor testabile și, de asemenea, la discreția cercetătorului. În plus, ar trebui aleasă o măsură adecvată a distanței (similarității). O caracteristică a grupării ierarhice este dezvoltarea unei structuri ierarhice sau arborescente. Metodele de grupare ierarhică pot fi aglomerative sau divizibile. Metodele aglomerative includ: metoda de legare unică, metoda de legare completă și metoda de legare medie. O metodă de dispersie utilizată pe scară largă este metoda Bard. Metodele de grupare non-ierarhice sunt adesea denumite metode k-means. Aceste metode includ thresholding secvenţial, thresholding paralel şi optimizarea alocării. Metodele ierarhice și non-ierarhice pot fi utilizate împreună. Alegerea metodei de grupare și alegerea măsurii distanței sunt interdependente.
Decizia privind numărul de clustere se ia pe motive teoretice și practice. În gruparea ierarhică, un criteriu important pentru a decide numărul de clustere este distanța la care clusterele sunt combinate. Dimensiunile relative ale clusterelor ar trebui să fie astfel încât să aibă sens să păstrați acest cluster și să nu îl îmbinați cu altele. Clusterele sunt interpretate în termeni de centroizi cluster. Este adesea util să interpretați clusterele prin profilarea lor prin variabile care nu au stat la baza grupării. Fiabilitatea și validitatea soluțiilor de clustering sunt evaluate în diferite moduri.
dendrogramă aglomerativă ierarhică cluster
Bibliografie
1. Vasiliev V.I. și alte Analize statistice ale obiectelor de natură arbitrară. Introducere în statistica calității.- M.: IKAR, 2004.
2. Analiză economică şi statistică / Ed. Ilyenkova S.D. -M.: UNTIT, 2002.
3. Parsadanov G.A. Prognoza si planificarea sistemului socio-economic al tarii - M .: UNITI, 2001
Găzduit pe Allbest.ru
Documente similare
Programare liniară. Interpretare geometrică și metodă grafică de rezolvare a LLP. Metoda simplex pentru rezolvarea LLP. Metoda pe bază artificială. Algoritmul metodei elementului minim. Algoritmul metodei potenţialelor. Metoda Gomory. Algoritmul metodei Vogel.
rezumat, adăugat 02.03.2009
Metoda grafica de rezolvare a problemei de optimizare a proceselor de productie. Aplicarea algoritmului simplex pentru rezolvarea unei probleme economic optimizate a managementului producției. Metodă de programare dinamică pentru alegerea profilului optim de cale.
test, adaugat 15.10.2010
Metode analitice și numerice de optimizare necondiționată. Metoda eliminării și metoda multiplicatorului Lagrange (MML). Metoda lui Euler este o metodă clasică de rezolvare a problemelor de optimizare neconstrânsă. Problemă clasică de optimizare condiționată. Despre sensul practic al MML.
rezumat, adăugat 17.11.2010
Metode de bază pentru rezolvarea problemelor de programare liniară. Metoda grafică, metoda simplex. Problemă dublă, metoda potențialelor. Modelare și caracteristici de rezolvare a problemei transportului prin metoda potențială folosind capabilitățile Microsoft Excel.
test, adaugat 14.03.2014
Tipuri de manifestare a relaţiilor cantitative dintre trăsături. Definiții funcționale și corelații. Semnificația practică a stabilirii, direcției și forței corelației. Metoda pătratelor (metoda Pearson), metoda rangului (metoda Spearman).
prezentare, adaugat 19.04.2015
O modalitate geometrică de a rezolva probleme standard de programare liniară cu două variabile. O metodă universală pentru rezolvarea unei probleme canonice. Ideea principală a metodei simplex, implementare prin exemplu. Implementarea tabelară a unei metode simplex simple.
rezumat, adăugat 15.06.2010
Soluție de referință inițială evidentă. Metoda simplex pe bază naturală. Metodă grafică pentru rezolvarea problemelor de programare liniară. Problemă dublă, soluția sa optimă. Matricea coeficientului de cost. Schema completă a echilibrului intrare-ieșire.
test, adaugat 30.04.2009
Obiectivele segmentării pieței în activitățile de marketing. Esența analizei cluster, principalele etape ale implementării acesteia. Selectați modul de măsurare a distanței sau a similitudinii. Metode de grupare ierarhică, non-ierarhică. Evaluarea fiabilității și a fiabilității.
raport, adaugat 02.11.2009
Analiza metaclusterului: înțelegere, algoritm, sarcină. Caracteristicile cheie ale procedurii McKean. Graficul valorilor medii pentru trei grupuri. Metoda metodelor K, avantajele și dezavantajele câștigului. Înțelegerea algoritmilor de grupare a grilei (pe bază de grilă).
rezumat, adăugat 27.05.2013
Teoria matematică a deciziei optime. Metoda simplex tabelar. Formularea și rezolvarea problemei duale a programării liniare. Modelul matematic al problemei transportului. Analiza fezabilității fabricării produselor la întreprindere.
Trimiteți-vă munca bună în baza de cunoștințe este simplu. Foloseste formularul de mai jos
Studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vor fi foarte recunoscători.
Introducere
1. Istoricul „analizei cluster”
2. Terminologie
2.1 Obiect și caracteristică
2.2 Distanța dintre obiecte (metrică)
2.3 Densitatea și localitatea clusterelor
2.4 Distanța dintre clustere
3. Metode de grupare
3.1 Caracteristicile metodelor aglomerative ierarhice
3.2 Caracteristicile metodelor iterative de clustering
4. Gruparea caracteristicilor
5. Stabilitatea și calitatea grupării
Bibliografie
INTRODUCERE
„Analiză cluster – un set metode matematice, concepute pentru a forma relativ „distante” unele de altele grupuri de obiecte „apropiate” în funcție de informații despre distanțe sau conexiuni (măsuri de proximitate) dintre ele. Semnificația este similară cu termenii: clasificare automată, taxonomie, recunoaștere a modelelor fără profesor.” Această definiție a analizei cluster este dată în ultima ediție a Dicționarului Statistic. De fapt, „analiza cluster” este un nume generalizat pentru un set mare de algoritmi utilizați pentru a crea o clasificare. Într-o serie de publicații, sunt utilizate, de asemenea, sinonime ale analizei de cluster, cum ar fi clasificarea și partiționarea.Analiza de cluster este utilizată pe scară largă în știință ca mijloc de analiză tipologică. În orice activitate științifică, clasificarea este una dintre componentele fundamentale, fără de care este imposibil să se construiască și să testeze ipoteze și teorii științifice. Astfel, în lucrarea mea, scopul meu principal, consider că este necesar să luăm în considerare problemele analizei cluster (baza analizei cluster), precum și să ia în considerare terminologia acesteia și să dea câteva exemple de utilizare a acestei metode cu prelucrarea datelor.
1. ISTORIA „ANALIZA CLUSTERULUI”
O analiză a publicațiilor interne și străine arată că analiza cluster este utilizată într-o mare varietate de domenii științifice: chimie, biologie, medicină, arheologie, istorie, geografie, economie, filologie etc. Cartea lui VV Nalimov „Modelul probabilistic al limbajului” descrie utilizarea analizei cluster în studiul a 70 de eșantioane analitice. Cea mai mare parte a literaturii despre analiza clusterelor a apărut în ultimele trei decenii, deși primele lucrări care au menționat metodele cluster au apărut cu destul de mult timp în urmă. Antropologul polonez K. Chekanowski a prezentat ideea „clasificării structurale”, care conținea ideea principală a analizei cluster - alocarea grupurilor compacte de obiecte.
În 1925, hidrobiologul sovietic P.V. Terentyev a dezvoltat așa-numita „metodă a pleiadelor de corelare”, destinată grupării caracteristicilor corelate. Această metodă a dat impuls dezvoltării metodelor de grupare folosind grafice. Termenul „analiza cluster” a fost propus pentru prima dată de Trion. Cuvântul „cluster” este tradus din engleză ca „bunch, brush, bunch, group”. Din acest motiv, acest tip de analiză a fost inițial numit „analiza cluster”. La începutul anilor 1950, publicațiile lui R. Lewis, E. Fix și J. Hodges au apărut despre algoritmii de analiză a clusterelor ierarhice. Un impuls notabil dezvoltării lucrărilor privind analiza clusterului a fost dat de lucrările lui R. Rosenblatt privind dispozitivul de recunoaștere (perceptron), care a pus bazele dezvoltării teoriei „recunoașterii modelelor fără profesor”.
Impulsul dezvoltării metodelor de clustering a fost cartea „Principles of Numerical Taxonomy”, publicată în 1963. doi biologi - Robert Sokal și Peter Sneath. Autorii acestei cărți au pornit de la faptul că, pentru a crea clasificări biologice eficiente, procedura de grupare ar trebui să asigure utilizarea tuturor indicatorilor posibili care caracterizează organismele studiate, să evalueze gradul de similitudine dintre aceste organisme și să asigure plasarea unor organisme similare. organisme din același grup. În acest caz, grupurile formate ar trebui să fie suficient de „locale”, adică. asemănarea obiectelor (organismelor) în cadrul grupurilor ar trebui să depășească asemănarea grupurilor între ele. Analiza ulterioară a grupurilor identificate, în opinia autorilor, poate clarifica dacă aceste grupuri corespund unor specii biologice diferite. Astfel, Sokal și Sneath au presupus că dezvăluirea structurii distribuției obiectelor în grupuri ajută la stabilirea procesului de formare a acestor structuri. Iar diferența și asemănarea organismelor din diferite grupuri (grupuri) poate servi ca bază pentru înțelegerea procesului evolutiv în curs și elucidarea mecanismului acestuia.
În aceiași ani, mulți algoritmi au fost propuși de autori precum J. McKean, G. Ball și D. Hall folosind metode k-means; G. Lance și W. Williams, N. Jardine și alții - despre metodele ierarhice. O contribuție semnificativă la dezvoltarea metodelor de analiză a clusterelor a fost adusă de oamenii de știință autohtoni - E.M. Braverman, A.A. Dorofeyuk, I.B. Muchnik, L.A. Rastrigin, Yu.I. În special, în anii 60-70. Numeroși algoritmi dezvoltați de matematicienii din Novosibirsk N.G. Zagoruiko, V.N. Elkina și G.S. Lbov s-au bucurat de o mare popularitate. Aceștia sunt algoritmi atât de cunoscuți precum FOREL, BIGFOR, KRAB, NTTP, DRET, TRF, etc. Pe baza acestor pachete, a fost creat un pachet software specializat OTEX. Produsele software nu mai puțin interesante PPSA și Class-Master au fost create de matematicienii moscoviți S.A. Aivazyan, I.S. Enyukov și B.G. Mirkin.
Într-o oarecare măsură, metodele de analiză a clusterelor sunt disponibile în majoritatea celor mai cunoscute pachete statistice interne și externe: SIGAMD, DataScope, STADIA, SOMI, PNP-BIM, COPRA-2, SITO, SAS, SPSS, STATISTICA, BMDP, STATGRAPHICS , GENSTAT, S -PLUS etc. Desigur, la 10 ani de la publicarea acestei recenzii, s-au schimbat destul de multe, au apărut versiuni noi ale multor programe statistice și au apărut programe complet noi care folosesc atât algoritmi noi, cât și puterea de calcul mult crescută. Cu toate acestea, majoritatea pachetelor statistice folosesc algoritmi propuși și dezvoltați în anii 60-70.
Potrivit estimărilor aproximative ale experților, numărul publicațiilor despre analiza clusterului și aplicațiile acesteia în diferite domenii ale cunoașterii se dublează la fiecare trei ani. Care sunt motivele unui interes atât de furtunos pentru acest tip de analiză? În mod obiectiv, există trei motive principale pentru acest fenomen. Aceasta este apariția unei tehnologii de calcul puternice, fără de care analiza în cluster a datelor reale nu este practic fezabilă. Al doilea motiv este că știința modernă se bazează din ce în ce mai mult pe clasificare în construcțiile sale. Mai mult, acest proces se aprofundează din ce în ce mai mult, întrucât în paralel cu aceasta are loc o specializare tot mai mare a cunoștințelor, ceea ce este imposibil fără o clasificare suficient de obiectivă.
Al treilea motiv - aprofundarea cunoștințelor speciale duce inevitabil la o creștere a numărului de variabile luate în considerare în analiza anumitor obiecte și fenomene. Ca urmare, clasificarea subiectivă, care se baza anterior pe un număr destul de mic de caracteristici luate în considerare, se dovedește adesea a fi nesigură. Și clasificarea obiectivă, cu un set din ce în ce mai mare de caracteristici ale obiectelor, necesită utilizarea unor algoritmi de clustering complecși care pot fi implementați doar pe baza computerelor moderne. Aceste motive au dat naștere „boom-ului clusterului”. Cu toate acestea, printre medici și biologi, analiza cluster nu a devenit încă o metodă de cercetare destul de populară și comună.
2 TERMINOLOGIE
2. 1 OBIECTUL ȘI SEMNUL
Să introducem mai întâi concepte precum obiect și semn. Obiect - din latinescul objectum - subiect. În raport cu chimia și biologia, prin obiecte vom înțelege subiecte specifice de cercetare care sunt studiate prin metode fizice, chimice și de altă natură. Astfel de obiecte pot fi, de exemplu, mostre, plante, animale etc. Un anumit set de obiecte disponibile cercetătorului pentru studiu se numește eșantion sau set de mostre. Numărul de obiecte dintr-o astfel de populație se numește de obicei dimensiunea eșantionului. De obicei, dimensiunea eșantionului este indicată de litera latină „n” sau „N”.
Semnul (sinonime - proprietate, variabilă, caracteristică; engleză - variabilă - variabilă.) - este o proprietate specifică a obiectului. Aceste proprietăți pot fi exprimate ca valori numerice sau nenumerice. De exemplu, tensiunea arterială (sistolică sau diastolică) se măsoară în milimetri de mercur, greutatea în kilograme, înălțimea în centimetri etc. Astfel de semne sunt cantitative. Spre deosebire de aceste caracteristici numerice continue (scări), o serie de caracteristici pot avea valori discrete, discontinue. La rândul lor, astfel de caracteristici discrete sunt de obicei împărțite în două grupuri.
1) Primul grup este variabilele de rang, sau așa cum sunt numite și variabile ordinale (scale). Astfel de semne se caracterizează prin proprietatea de a ordona aceste valori. Acestea includ etapele unei anumite boli, grupele de vârstă, scorurile de cunoștințe ale studenților, scara de magnitudine a cutremurului Richter în 12 puncte etc.
2) Al doilea grup de caracteristici discrete nu are o astfel de ordine și se numește caracteristici nominale (din cuvântul „nominal” - eșantion) sau caracteristici de clasificare. Un exemplu de astfel de semne poate fi starea pacientului - „sănătos” sau „bolnav”, sexul pacientului, perioada de observație - „înainte de tratament” și „după tratament”, etc. În aceste cazuri, se obișnuiește să se spună că astfel de caracteristici aparțin scarei numelor.
Conceptele unui obiect și o caracteristică sunt de obicei numite matrice „Obiect-propietate” sau „Object-feature”. Matricea va fi un tabel dreptunghiular format din valorile caracteristicilor care descriu proprietățile eșantionului de observații studiate. În acest context, o observație va fi înregistrată ca o linie separată constând din valorile caracteristicilor utilizate. Un atribut separat într-o astfel de matrice de date va fi reprezentat de o coloană formată din valorile acestui atribut pentru toate obiectele din eșantion.
2. 2 DISTANȚA DINTRE OBIECTE (METRIC)
Să introducem conceptul de „distanță între obiecte”. Acest concept este o măsură integrală a asemănării obiectelor între ele. Distanța dintre obiectele din spațiul caracteristic este o astfel de valoare d ij care satisface următoarele axiome:
1. d ij > 0 (nonnegativitatea distanței)
2. d ij = d ji (simetrie)
3. d ij + d jk > d ik (inegalitatea triunghiului)
4. Dacă d ij nu este egal cu 0, atunci i nu este egal cu j (distingerea obiectelor neidentice)
5. Dacă d ij = 0, atunci i = j (nediferențierea obiectelor identice)
Este convenabil să se reprezinte măsura proximității (asemănării) obiectelor ca reciprocă a distanței dintre obiecte. Numeroase publicații dedicate analizei cluster descriu mai mult de 50 de moduri diferite de a calcula distanța dintre obiecte. Pe lângă termenul „distanță”, un alt termen se găsește adesea în literatură - „metric”, care implică o metodă de calcul a unei anumite distanțe. Cea mai accesibilă pentru percepție și înțelegere în cazul caracteristicilor cantitative este așa-numita „distanță euclidiană” sau „metrică euclidiană”. Formula de calcul a acestei distanțe este:
Această formulă folosește următoarea notație:
· d ij - distanta dintre obiectele i-lea si j-lea;
· x ik - valoarea numerică a k-a variabilă pentru i-lea obiect;
· x jk - valoarea numerică a k-a variabilă pentru j-lea obiect;
· v - numărul de variabile care descriu obiectele.
Astfel, pentru cazul v=2, când avem doar două trăsături cantitative, distanța d ij va fi egală cu lungimea ipotenuzei unui triunghi dreptunghic, care leagă două puncte dintr-un sistem de coordonate dreptunghiular. Aceste două puncte vor corespunde observațiilor i-a și j-a ale eșantionului. Adesea, în loc de distanța euclidiană obișnuită, se folosește pătratul său d 2 ij. În plus, în unele cazuri, se folosește o distanță euclidiană „ponderată”, în calculul căreia se folosesc coeficienți de greutate pentru termeni individuali. Pentru a ilustra conceptul de metrică euclidiană, folosim un exemplu simplu de antrenament. Matricea de date prezentată în tabelul de mai jos constă din 5 observații și două variabile.
tabelul 1
Matrice de date din cinci eșantioane observate și două variabile.
Folosind metrica euclidiană, calculăm matricea distanțelor interobiecte, constând din valorile d ij - distanța dintre obiectele i-lea și j-lea. În cazul nostru, i și j sunt numărul obiectului, observație. Deoarece dimensiunea eșantionului este 5, i și, respectiv, j, pot lua valori de la 1 la 5. De asemenea, este evident că numărul tuturor distanțelor posibile pe perechi va fi 5*5=25. Într-adevăr, pentru primul obiect acestea vor fi următoarele distanțe: 1-1; 1-2; 1-3; 1-4; 1-5. Pentru obiectul 2 vor exista si 5 distante posibile: 2-1; 2-2; 2-3; 2-4; 2-5 etc. Cu toate acestea, numărul de distanțe diferite va fi mai mic de 25, deoarece este necesar să se țină seama de proprietatea de indistingere a obiectelor identice - d ij = 0 pentru i = j. Aceasta înseamnă că distanța dintre obiectul #1 și același obiect #1 va fi zero. Aceleași distanțe zero vor fi pentru toate celelalte cazuri i = j. În plus, din proprietatea de simetrie rezultă că d ij = d ji pentru orice i și j. Acestea. distanța dintre obiectele #1 și #2 este egală cu distanța dintre obiectele #2 și #1.
Expresia pentru distanța euclidiană este foarte asemănătoare cu așa-numita distanță generalizată a puterii Minkowski, în care se folosește o altă valoare în loc de două în puteri. În cazul general, această valoare este notată prin simbolul „p”.
Pentru p = 2 obținem distanța euclidiană obișnuită. Deci expresia pentru metrica Minkowski generalizată are forma:
Alegerea unei valori specifice a exponentului „p” se face chiar de cercetător.
Un caz special al distanței Minkowski este așa-numita distanță Manhattan, sau „distanța oraș-bloc”, corespunzătoare p=1:
Astfel, distanța Manhattan este suma modulelor diferențelor caracteristicilor corespunzătoare obiectelor. Lăsând p să tinde spre infinit, obținem metrica „dominanței” sau Sup-metrică:
care poate fi reprezentat şi ca d ij = max| x ik - x jk |.
Valoarea Minkowski este de fapt o familie mare de valori, inclusiv cele mai populare valori. Cu toate acestea, există metode pentru calcularea distanței dintre obiecte care sunt fundamental diferite de metrica Minkowski. Cea mai importantă dintre acestea este așa-numita distanță Mahalanobis, care are proprietăți destul de specifice. Expresia pentru această valoare:
Aici prin X iși X j sunt indicați vectori coloană de valori variabile pentru obiectele i-lea și j-lea. Simbol T în exprimare (X i - X j ) T denotă așa-numita operație de transpunere vectorială. Simbol S este indicată matricea comună varianță-covarianță intra-grup. Un simbol -1 de mai sus S înseamnă că trebuie să inversați matricea S . Spre deosebire de metrica Minkowski și metrica euclidiană, distanța Mahalanobis prin matricea varianță-covarianță S asociate cu corelații de variabile. Când corelațiile dintre variabile sunt zero, distanța Mahalanobis este echivalentă cu pătratul distanței euclidiene.
În cazul utilizării caracteristicilor calitative dihotomice (având doar două valori), distanța Hamming este utilizată pe scară largă.
egal cu numărul de nepotriviri în valorile caracteristicilor corespunzătoare pentru obiectele i-a și j-a considerate.
2. 3 DENSITATEA ȘI LOCALITATEA CLUSTELOR
Scopul principal al analizei cluster este de a găsi grupuri de obiecte similare între ele în eșantion. Să presupunem că prin unele dintre metodele posibile am obținut astfel de grupuri - clustere. Trebuie remarcate proprietățile importante ale clusterelor. Una dintre aceste proprietăți este densitatea de distribuție a punctelor, observații în cadrul unui cluster. Această proprietate ne permite să definim un cluster ca un grup de puncte într-un spațiu multidimensional care este relativ dens în comparație cu alte regiuni ale acestui spațiu care fie nu conțin puncte deloc, fie conțin un număr mic de observații. Cu alte cuvinte, cât de compact este acest cluster, sau invers, cât de rar este. În ciuda dovezilor suficiente ale acestei proprietăți, nu există o modalitate clară de a calcula un astfel de indicator (densitate). Cel mai de succes indicator care caracterizează compactitatea, densitatea de „ambalare” a observațiilor multidimensionale într-un cluster dat, este dispersia distanței de la centrul clusterului la punctele individuale ale clusterului. Cu cât dispersia acestei distanțe este mai mică, cu atât observațiile sunt mai aproape de centrul clusterului, cu atât densitatea clusterului este mai mare. Și invers, cu cât dispersia distanței este mai mare, cu atât acest cluster este mai rar și, în consecință, există puncte situate atât în apropierea centrului clusterului, cât și destul de îndepărtate de centrul clusterului.
Următoarea proprietate a clusterelor este dimensiunea lor. Principalul indicator al dimensiunii unui cluster este „raza” acestuia. Această proprietate reflectă cel mai pe deplin dimensiunea actuală a clusterului dacă clusterul considerat este rotund și hipersferă în spațiul multidimensional. Cu toate acestea, dacă clusterele au forme alungite, atunci conceptul de rază sau diametru nu mai reflectă dimensiunea reală a clusterului.
O altă proprietate importantă a unui cluster este localitatea lor, separabilitatea. Caracterizează gradul de suprapunere și îndepărtarea reciprocă a clusterelor unul față de celălalt într-un spațiu multidimensional. De exemplu, luați în considerare distribuția a trei clustere în spațiul caracteristicilor noi, integrate din figura de mai jos. Axele 1 și 2 au fost obținute printr-o metodă specială din 12 caracteristici ale proprietăților reflectorizante ale diferitelor forme de eritrocite, studiate cu ajutorul microscopiei electronice.
Poza 1
Vedem că clusterul 1 are dimensiunea minimă, în timp ce clusterele 2 și 3 au dimensiuni aproximativ egale. În același timp, putem spune că densitatea minimă și, prin urmare, dispersia maximă la distanță, este caracteristică clusterului 3. În plus, clusterul 1 este separat de secțiuni suficient de mari de spațiu gol atât de clusterul 2, cât și de clusterul 3. În timp ce clusterele 2 și 3 se suprapun parțial unul cu celălalt. De asemenea, este interesant faptul că clusterul 1 are o diferență mult mai mare față de al 2-lea și al 3-lea cluster de-a lungul axei 1 decât de-a lungul axei 2. Dimpotrivă, clusterele 2 și 3 diferă aproximativ în mod egal între ele atât de-a lungul axei 1, cât și de-a lungul axei 2. Este evident că pentru o astfel de analiză vizuală este necesar ca toate observațiile eșantionului să fie proiectate pe axe speciale, în care proiecțiile elementelor cluster vor fi vizibile ca clustere separate.
2. 4 DISTANȚA DINTRE CURSE
Într-un sens mai larg, obiectele pot fi înțelese nu numai ca subiecte originale ale cercetării, prezentate în matricea „obiect-proprietate” ca o linie separată, sau ca puncte individuale într-un spațiu caracteristic multidimensional, ci și ca grupuri separate de astfel de puncte. , unite de un algoritm sau altul într-un cluster. În acest caz, se pune întrebarea cum să înțelegem distanța dintre astfel de acumulări de puncte (clusters) și cum să o calculăm. În acest caz, varietatea posibilităților este chiar mai mare decât în cazul calculării distanței dintre două observații într-un spațiu multidimensional. Această procedură este complicată de faptul că, spre deosebire de puncte, clusterele ocupă o anumită cantitate de spațiu multidimensional și constau din multe puncte. În analiza clusterelor, distanțele dintre clustere sunt utilizate pe scară largă, calculate pe principiul celui mai apropiat vecin (cel mai apropiat vecin), centru de greutate, cel mai îndepărtat vecin, mediane. Cele mai utilizate patru metode sunt: o singură legătură, o legătură completă, o legătură medie și metoda lui Ward. În metoda legăturii unice, un obiect va fi atașat la un cluster deja existent dacă cel puțin unul dintre elementele clusterului are același nivel de similitudine cu obiectul care este alăturat. Pentru metoda legăturilor complete, un obiect este atașat unui cluster numai dacă asemănarea dintre candidatul pentru includere și oricare dintre elementele clusterului nu este mai mică de un anumit prag. Pentru metoda de conectare medie, există mai multe modificări, care reprezintă un compromis între conexiunea unică și cea completă. Ei calculează valoarea medie a similarității candidatului pentru includere cu toate obiectele clusterului existent. Atașarea se realizează atunci când valoarea medie de similitudine găsită atinge sau depășește un anumit prag. Cel mai frecvent utilizat este similaritatea medie aritmetică dintre obiectele clusterului și candidatul pentru includerea în cluster.
Multe dintre metodele de grupare diferă unele de altele prin faptul că algoritmii lor la fiecare pas calculează diferite funcționale de calitate a partiționării. Metoda populară Ward este construită astfel încât să optimizeze variația minimă a distanțelor intracluster. La prima etapă, fiecare cluster este format dintr-un obiect, datorită căruia dispersia intracluster a distanțelor este egală cu 0. Conform acestei metode, acele obiecte care dau incrementul minim de dispersie sunt combinate, drept urmare această metodă tinde. pentru a genera clustere hipersferice.
Încercările multiple de a clasifica metodele de analiză a clusterelor conduc la zeci sau chiar sute de clase diferite. O astfel de varietate este generată de un număr mare de moduri posibile de a calcula distanța dintre observațiile individuale, nu mai puțin de un număr de metode de calculare a distanței dintre clustere individuale în procesul de grupare și estimări diverse ale optimității structurii clusterului final.
Două grupuri de algoritmi de analiză a clusterelor sunt cele mai utilizate pe scară largă în pachetele statistice populare: metodele aglomerative ierarhice și metodele de grupare iterativă.
3. METODE DE GRUPARE
3. 1 CARACTERISTICI ALE METODELOR AGLOMERATIVE IERARHICE
În algoritmii ierarhici aglomerativi, care sunt mai des folosiți în cercetarea biomedicală reală, inițial toate obiectele (observațiile) sunt considerate ca grupuri separate, independente, formate dintr-un singur element. Fără utilizarea unei tehnologii computerizate puternice, implementarea analizei datelor cluster este foarte problematică.
Alegerea metricii este făcută de cercetător. După calcularea matricei distanțelor, începe procesul aglomerări (din latinescul agglomero - atasez, acumulez), trecand secvential pas cu pas. La prima etapă a acestui proces, două observații inițiale (monoclustere) cu cea mai mică distanță între ele sunt combinate într-un singur grup, care este deja format din două obiecte (observații). Astfel, în locul fostelor N monoclustere (clustere formate dintr-un obiect), după primul pas vor exista N-1 clustere, dintre care un cluster va conține două obiecte (observații), iar N-2 clustere vor consta în continuare din un singur obiect. La a doua etapă, sunt posibile diferite metode de combinare a clusterelor N-2. Acest lucru se datorează faptului că unul dintre aceste clustere conține deja două obiecte. Din acest motiv, se ridică două întrebări principale:
· cum se calculează coordonatele unui astfel de grup de două (și mai mult de două) obiecte;
· cum se calculează distanța până la astfel de clustere „poli-obiect” de la „monoclustere” și între clustere „poli-obiect”.
Aceste întrebări determină în cele din urmă structura finală a clusterelor finale (structura clusterelor înseamnă compoziția clusterelor individuale și poziția relativă a acestora într-un spațiu multidimensional). Diverse combinații de metrici și metode pentru calcularea coordonatelor și distanțelor reciproce ale clusterelor dau naștere la varietatea metodelor de analiză a clusterelor. La a doua etapă, în funcție de metodele alese de calculare a coordonatelor unui cluster format din mai multe obiecte și de metoda de calcul a distanțelor dintre clustere, este posibil fie să se recombină două observații separate într-un nou cluster, fie să se alăture unui nou grup. observarea unui grup format din două obiecte. Pentru comoditate, majoritatea programelor de metode aglomerativ-ierarhice de la sfârșitul lucrării pot oferi două grafice principale pentru vizualizare. Primul grafic se numește dendrogramă (din grecescul dendron - arbore), reflectând procesul de aglomerare, fuziunea observațiilor individuale într-un singur cluster final. Să dăm un exemplu de dendrogramă cu 5 observații în două variabile.
Programa1
Axa verticală a unui astfel de grafic este axa distanței dintre clustere, iar numărul de obiecte - cazuri utilizate în analiză - este marcat de-a lungul axei orizontale. Din această dendrogramă se poate observa că obiectele nr. 1 și nr. 2 sunt mai întâi combinate într-un singur grup, deoarece distanța dintre ele este cea mai mică și este egală cu 1. Această fuziune este afișată pe grafic printr-o linie orizontală care conectează segmentele verticale care vin din punctele marcate ca C_1 și C_2. Să acordăm atenție faptului că linia orizontală în sine trece exact la nivelul distanței intercluster egală cu 1. Mai departe, la a doua etapă, obiectul nr. 3, desemnat ca C_3, se alătură acestui cluster, care include deja două obiecte. Următorul pas este să îmbinați obiectele #4 și #5, distanța dintre care este egală cu 1,41. Și la ultimul pas, grupul de obiecte 1, 2 și 3 este combinat cu grupul de obiecte 4 și 5. Graficul arată că distanța dintre aceste două penultime grupuri (ultimul grup include toate cele 5 obiecte) este mai mare de 5. , dar mai mică de 6, deoarece linia orizontală superioară care leagă cele două penultime clustere trece la un nivel aproximativ egal cu 7, iar nivelul de conectare al obiectelor 4 și 5 este 1,41.
Dendrograma de mai jos a fost obținută din analiza unui set de date real format din 70 de probe chimice prelucrate, fiecare dintre acestea fiind caracterizată de 12 caracteristici.
Diagrama 2
Din grafic se poate observa că la ultimul pas, când ultimele două clustere se îmbină, distanța dintre ele este de aproximativ 200 de unități. Se poate observa că primul cluster include mult mai puține obiecte decât al doilea cluster.Mai jos este o secțiune mărită a dendrogramei pe care sunt vizibile clar numerele de observație, notate ca C_65, C_58 etc. (de la stânga la dreapta): 65, 58, 59, 64, 63, 57, 60, 62, 56, 44, 94 etc.
Diagrama 3 Porțiune mărită a diagramei #2 de mai sus
Se poate observa că obiectul 44 este un monocluster care se combină cu clusterul din dreapta la penultima etapă, iar apoi, la ultima etapă, toate observațiile sunt combinate într-un singur cluster.
Un alt grafic care este construit în astfel de proceduri este un grafic al distanțelor dintre clustere la fiecare pas al uniunii. Mai jos este o diagramă similară pentru dendrograma de mai sus.
Diagrama 4
Într-un număr de programe, este posibil să se afișeze în formă tabelară rezultatele combinării obiectelor la fiecare pas de grupare. În cele mai multe dintre aceste tabele, pentru a evita confuziile, se folosește o terminologie diferită pentru a desemna observațiile inițiale - monoclustere, și clusterele reale formate din două sau mai multe observații. În pachetele statistice în limba engleză, observațiile inițiale (rândurile matricei de date) sunt desemnate ca „caz” - caz. Pentru a demonstra dependența structurii clusterului de alegerea metricii și alegerea algoritmului de combinare a clusterelor, prezentăm mai jos o dendrogramă corespunzătoare algoritmului de conexiune completă. Și aici vedem că obiectul #44 este îmbinat cu restul selecției în ultimul pas.
Diagrama 5
Acum să o comparăm cu o altă diagramă obținută prin utilizarea metodei single link pe aceleași date. Spre deosebire de metoda de conectare completă, se poate observa că această metodă generează lanțuri lungi de obiecte atașate secvențial între ele. Cu toate acestea, în toate cele trei cazuri, putem spune că două grupuri principale ies în evidență.
Diagrama 6
De asemenea, să acordăm atenție faptului că în toate cele trei cazuri obiectul nr. 44 se alătură ca un monocluster, deși la diferite etape ale procesului de grupare. Selectarea unor astfel de monoclustere este un mijloc bun de detectare a observațiilor anormale, numite valori aberante. Să ștergem acest obiect „suspect” nr. 44 și să realizăm din nou gruparea. Obținem următoarea dendrogramă:
Diagrama 7
Se poate observa că efectul de „lanț” este păstrat, la fel ca și împărțirea în două grupuri locale de observații.
3. 2 CARACTERISTICI ALE METODELOR ITERATIVE DE CLUSTERING
Dintre metodele iterative, cea mai populară metodă este metoda k-means a lui 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 cu „k”. Ca și în metodele de grupare ierarhică, utilizatorul poate alege unul sau altul tip de metrică. Diferiți algoritmi ai metodei k-means diferă și în modul de alegere a centrelor inițiale ale clusterelor date. În unele variante ale metodei, utilizatorul însuși poate (sau trebuie) să specifice astfel de puncte inițiale, fie selectându-le din observații reale, fie specificând coordonatele acestor puncte pentru fiecare dintre variabile. În alte implementări ale acestei metode, alegerea unui număr k dat de puncte inițiale se face în mod aleatoriu, iar aceste puncte inițiale (granule de cluster) pot fi ulterior rafinate în mai multe etape. Există 4 etape principale ale unor astfel de metode:
· selectați sau atribuiți k observații care vor fi centrele primare ale clusterelor;
· dacă este necesar, se formează clustere intermediare prin atribuirea fiecărei observații celor mai apropiate centre de cluster specificate;
· după atribuirea tuturor observațiilor clusterelor individuale, centrele clusterelor primare sunt înlocuite cu medii cluster;
· se repetă iterația anterioară până când modificările coordonatelor centrilor clusterului devin minime.
În unele variante ale acestei metode, utilizatorul poate seta o valoare numerică a criteriului, care este interpretată ca distanța minimă pentru selectarea noilor centre de cluster. O observație nu va fi considerată candidată pentru un nou centru de cluster dacă distanța sa până la centrul de cluster înlocuit depășește numărul specificat. Acest parametru se numește „rază” în unele programe. Pe lângă acest parametru, este posibil să setați numărul maxim de iterații sau să ajungeți la un anumit număr, de obicei destul de mic, cu care este comparată modificarea distanței pentru toate centrele clusterului. Această setare este denumită în mod obișnuit „convergență” deoarece reflectă convergența procesului de clustering iterativ. Mai jos prezentăm câteva dintre rezultatele care au fost obținute folosind metoda McKean k-means la datele anterioare. Numărul de grupuri dorite a fost setat inițial la 3 și apoi la 2. Prima lor parte conține rezultatele unui singur factor. analiza variatiei, în care numărul clusterului acționează ca un factor de grupare. Prima coloană este o listă de 12 variabile, urmată de sumele pătratelor (SS) și gradele de libertate (df), apoi testul F Fisher, iar în ultima coloană nivelul de semnificație „p” atins.
Tabelul 2 McKean k-means date aplicabile la 70 de probe de testare.
Variabile |
|||||||
După cum se poate observa din acest tabel, ipoteza nulă despre egalitatea mediilor în cele trei grupe este respinsă. Mai jos este un grafic al mediilor tuturor variabilelor pentru grupuri individuale. Aceleași medii de cluster ale variabilelor sunt prezentate mai jos sub forma unui tabel.
Tabelul 3. Revizuirea detaliată a datelor din exemplul a trei grupuri.
Variabil |
Clusterul #1 |
Clusterul #2 |
Clusterul #3 |
|
Diagrama 8
Analiza valorilor medii ale variabilelor pentru fiecare cluster ne permite să concluzionam că, conform caracteristicii X1, clusterele 1 și 3 au valori apropiate, în timp ce clusterul 2 are o valoare medie mult mai mică decât în celelalte două clustere. Dimpotrivă, conform caracteristicii X2, primul cluster are cea mai mică valoare, în timp ce al 2-lea și al 3-lea cluster au valori medii mai mari și apropiate. Pentru trăsăturile X3-X12, valorile medii în clusterul 1 sunt semnificativ mai mari decât în clusterele 2 și 3. Următorul tabel de analiză ANOVA a rezultatelor grupării în două clustere arată, de asemenea, nevoia de a respinge ipoteza nulă despre egalitate. a mediilor de grup pentru aproape toate cele 12 caracteristici, cu excepția variabilei X4, pentru care nivelul de semnificație atins sa dovedit a fi mai mare de 5%.
Tabelul 4. Tabelul analizei de dispersie a rezultatelor grupării în două clustere.
Variabile |
|||||||
Mai jos este un grafic și un tabel cu medii de grup pentru cazul grupării în două grupuri.
Tabelul 5. Tabel pentru cazul grupării în două clustere.
Variabile |
Clusterul #1 |
Clusterul #2 |
|
Diagrama 9.
In cazul in care cercetatorul nu este in masura sa determine in prealabil numarul cel mai probabil de clustere, el este obligat sa repete calculele, stabilind un alt numar, asemanator cu ceea ce s-a facut mai sus. Și apoi, comparând rezultatele obținute între ele, opriți-vă la una dintre cele mai acceptabile opțiuni de grupare.
4 . CLUSTER DE CARACTERISTICI
Pe lângă gruparea observațiilor individuale, există și algoritmi de grupare a caracteristicilor. Una dintre primele astfel de metode este metoda de corelare pleiade Terentiev P.V. Imaginile primitive ale unor astfel de pleiade pot fi adesea găsite în publicațiile biomedicale sub forma unui cerc punctat cu săgeți care leagă semne pentru care autorii au găsit o corelație. Un număr de programe pentru gruparea obiectelor și caracteristicilor au proceduri separate. De exemplu, în pachetul SAS pentru clustering de caracteristici, este utilizată procedura VARCLUS (de la VARiable - variabilă și CLUSter - cluster), în timp ce analiza cluster a observațiilor este efectuată prin alte proceduri - FASTCLUS și CLUSTER. Construcția unei dendrograme în ambele cazuri se realizează folosind procedura TREE (arborele).
În alte pachete statistice, selecția elementelor pentru grupare - obiecte sau caracteristici - se face în același modul. Ca măsurătoare pentru gruparea caracteristicilor, sunt adesea folosite expresii care includ valoarea anumitor coeficienți care reflectă puterea relației pentru o pereche de caracteristici. În acest caz, este foarte convenabil ca semnele cu o putere de conectare egală cu unu (dependență funcțională) să ia distanța dintre semne. zero. Într-adevăr, cu o conexiune funcțională, valoarea unei caracteristici poate calcula cu exactitate valoarea altei caracteristici. Odată cu scăderea puterii relației dintre caracteristici, distanța crește în consecință. Mai jos este un grafic care arată o dendrogramă a combinației de 12 caracteristici care au fost utilizate mai sus la gruparea a 70 de eșantioane analitice.
Graficul 10. Dendrogramagruparea a 12 caracteristici.
După cum se poate observa din această dendrogramă, avem de-a face cu două grupări locale de caracteristici: X1-X10 și X11-X12.Grupul de caracteristici X1-X10 se caracterizează printr-o valoare destul de mică a distanțelor dintre clustere, care nu depășește aproximativ 100 de unități. Aici vedem și câteva subgrupuri interne pereche: X1 și X2, X3 și X4, X6 și X7. Distanța dintre caracteristicile acestor perechi, care este foarte aproape de zero, indică relația lor puternică de pereche. În timp ce pentru perechea X11 și X12 valoarea distanței dintre clustere este mult mai mare și este de aproximativ 300 de unități. În cele din urmă, o distanță foarte mare între clusterele stânga (X1-X10) și dreapta (X11-X12), egală cu aproximativ 1150 de unități, indică faptul că relația dintre aceste două grupuri de caracteristici este destul de minimă.
5. STABILITATEA ȘI CALITATEA CLUSTERULUI
Evident, ar fi absurd să ne punem întrebarea cât de absolută este cutare sau cutare clasificare obținută cu ajutorul metodelor de analiză a clusterelor. Când metoda de grupare este schimbată, stabilitatea se manifestă prin faptul că două clustere sunt destul de clar vizibile pe dendrograme.
Ca una dintre modalitățile posibile de verificare a stabilității rezultatelor analizei cluster, poate fi utilizată metoda de comparare a rezultatelor obținute pentru diverși algoritmi de clustering. Alte moduri sunt așa-numita metodă bootstrap propusă de B. Efron în 1977, metodele „jackknife” și „sliding control”. Cel mai simplu mijloc de verificare a stabilității unei soluții de cluster poate fi împărțirea aleatorie a eșantionului inițial în două părți aproximativ egale, gruparea ambelor părți și apoi compararea rezultatelor. O modalitate mai consumatoare de timp implică excluderea secvenţială a primului obiect la început şi gruparea celorlalte (N - 1) obiecte. În plus, efectuarea secvenţială a acestei proceduri, cu excepţia celei de-a doua, a treia etc. obiecte, se analizează structura tuturor N clustere obținute. Un alt algoritm de verificare a stabilității implică reproducerea multiplă, duplicarea eșantionului original de N obiecte, apoi combinarea tuturor probelor duplicate într-un singur eșantion mare (populație pseudo-generală) și extragerea aleatorie a unui nou eșantion de N obiecte din acesta. După aceea, această probă este grupată, apoi este luată o nouă probă aleatoare și gruparea este efectuată din nou etc. Este, de asemenea, destul de intensivă în muncă.
Nu există mai puține probleme atunci când se evaluează calitatea grupării. Sunt cunoscuți destul de mulți algoritmi pentru optimizarea soluțiilor de cluster. Primele lucrări care au cuprins formulări ale criteriului de minimizare a varianței intracluster și un algoritm (de tipul k-means) pentru găsirea soluției optime au apărut în anii '50. În 1963 Articolul lui J. Ward a prezentat și un algoritm ierarhic de optimizare similar. Nu există un criteriu universal pentru optimizarea unei soluții de cluster. Toate acestea fac dificil pentru cercetător să aleagă soluția optimă. In asemenea situatie în cel mai bun mod posibil a afirma că soluția cluster găsită este optimă în această etapă a studiului, este doar coerența acestei soluții cu concluziile obținute folosind alte metode de statistică multivariată.
În favoarea concluziei despre optimitatea grupării, există și rezultate pozitive ale verificării momentelor predictive ale soluției obținute deja pe alte obiecte de studiu. Când folosiți metode ierarhice de analiză a clusterelor, vă putem recomanda compararea mai multor grafice ale modificărilor pas cu pas ale distanței dintre clustere. În acest caz, ar trebui să se acorde preferință opțiunii pentru care se observă o linie plată a unui astfel de increment de la primul pas la câțiva penultim pași cu o creștere verticală bruscă în acest grafic la ultimii 1-2 pași de grupare.
CONCLUZII
În munca mea, am încercat să arăt nu numai complexitatea acestui tip de analiză, ci și capabilitățile optime de procesare a datelor, deoarece de multe ori pentru acuratețea rezultatelor trebuie să utilizați de la zeci la sute de mostre. Acest tip de analiză ajută la clasificarea și procesarea rezultatelor. De asemenea, consider nu lipsită de importanță acceptabilitatea tehnologiilor informatice în această analiză, ceea ce face posibil ca procesul de prelucrare a rezultatelor să fie mai puțin consumator de timp și astfel permite să se acorde mai multă atenție corectitudinii eșantionării pentru analiză.
În utilizarea analizei cluster, există astfel de subtilități și detalii care apar în cazuri specifice individuale și nu sunt vizibile imediat. De exemplu, rolul scalei caracteristicilor poate fi minim și poate fi dominant în unele cazuri. În astfel de cazuri este necesar să se utilizeze transformări variabile. Acest lucru este eficient în special atunci când se utilizează metode care produc transformări neliniare ale caracteristicilor care cresc în general nivelul general de corelații între caracteristici.
Există o specificitate și mai mare în utilizarea analizei cluster în raport cu obiectele care sunt descrise doar prin caracteristici calitative. În acest caz, metodele de digitalizare preliminară a caracteristicilor calitative și analiza clusterului cu caracteristici noi sunt destul de reușite. În munca mea, am arătat că analiza cluster oferă o mulțime de informații noi și originale atât în cazul aplicării sale în sisteme suficient de studiate, cât și în studiul sistemelor cu structură necunoscută.
De asemenea, trebuie remarcat faptul că analiza clusterelor a devenit indispensabilă în cercetarea evolutivă, permițând construirea de arbori filogenetici care prezintă căi evolutive. Aceste metode sunt utilizate pe scară largă și în programele de cercetare științifică în chimie fizică și analitică.
BIBLIOGRAFIE
1) Aivazyan S. A., Enyukov I. S., Meshalkin L. D. Despre structura și conținutul pachetului software pentru analiza statistică aplicată//Algoritmică și software analiza statistică aplicată.--M., 1980.
2) Ayvazyan S. A., Bezhaeva Z. I., Staroverov O. V. Clasificarea observațiilor multidimensionale.--M.: Statistica, 1974.
3) Becker V. A., Lukatskaya M. L. Despre analiza structurii matricei coeficienților de cuplare// Probleme de modelare și prognoză economică și statistică în industrie.-- Novosibirsk, 1970.
4) Braverman E. M., Muchnik I. B. Metode structurale de prelucrare a datelor.--M.: Nauka, 1983.
5) Voronin Yu. A. Teoria clasificării și aplicațiile sale. - Novosibirsk: Nauka, 1987.
6) Bun I. J. Botryology of Botryology//Clasificarea și clusterul.--M.: Mir, 1980.
7) Dubrovsky S. A. Analiză statistică multivariată aplicată.--M.: Finance and statistics, 1982.
8) Duran N., Odell P. Cluster analysis.--M.: Statistics, 1977.
9) Eliseeva I.I., Rukavishnikov V.S. Gruparea, corelarea, recunoașterea modelelor.--M.: Statistică, 1977.
10) Zagoruiko N. G. Metode de recunoaștere și aplicarea lor.--M .: Radio sovietică, 1972.
11) Zade L. A. Seturile fuzzy și aplicarea lor în recunoașterea modelelor și analiza clusterelor//Clasificarea și clusterul.--M.: Mir, 1980.
12) Kildishev G.S., Abolentsev Yu.I. Grupări multidimensionale.--M.: Statistics, 1978.
13) Raiskaya II, Gostilin NI, Frenkel' AA Pe o singură modalitate de a verifica validitatea partiționării în analiza clusterului.//Aplicarea analizei statistice multivariate în economie și evaluarea calității produsului.--Ch. P. Tartu, 1977.
14) Shurygin A. M. Distribuția distanțelor și diferențelor între puncte // Suport software și algoritmic pentru analiza statistică multidimensională aplicată.--M., 1983.
15) Eeremaa R. Teoria generală a proiectării sistemelor cluster și a algoritmilor pentru găsirea reprezentărilor lor numerice: Proceedings of the Computing Center of TSU.--Tartu, 1978.
16) Yastremsky B.S. Lucrări alese.--M.: Statistics, 1964.
Documente similare
Obiectivele segmentării pieței în activitățile de marketing. Esența analizei cluster, principalele etape ale implementării acesteia. Selectați modul de măsurare a distanței sau a similitudinii. Metode de grupare ierarhică, non-ierarhică. Evaluarea fiabilității și a fiabilității.
raport, adaugat 02.11.2009
Principalele caracteristici starea financiaraîntreprinderilor. Criza la întreprindere, cauzele, tipurile și consecințele acesteia. Metode moderneși instrumente de analiză a clusterelor, caracteristici ale utilizării lor pentru evaluarea financiară și economică a întreprinderii.
teză, adăugată 10.09.2013
Efectuați o analiză de cluster a întreprinderilor folosind Statgraphics Plus. Construirea unei ecuații de regresie liniară. Calculul coeficienților de elasticitate prin modele de regresie. Evaluarea semnificației statistice a ecuației și a coeficientului de determinare.
sarcină, adăugată 16.03.2014
Construirea regresiilor tipologice pentru grupuri individuale de observații. Date spațiale și informații temporale. Domeniul de aplicare al analizei cluster. Conceptul de omogenitate a obiectelor, proprietăți ale matricei distanțelor. Efectuarea regresiei tipologice.
prezentare, adaugat 26.10.2013
Crearea de modele și metode combinate ca modalitate modernă de prognoză. Un model bazat pe ARIMA pentru descrierea seriilor de timp staționare și non-staționare în rezolvarea problemelor de clustering. Modele AR autoregresive și aplicarea corelogramelor.
prezentare, adaugat 05.01.2015
Caracteristică diferite feluri metrici. Metoda celui mai apropiat vecin și generalizările acesteia. Algoritmul celui mai apropiat vecin. Metoda ferestrei Parzen. Clasificator metric generalizat. Problema alegerii unei metrici. Manhattan și distanța euclidiană. măsura cosinusului.
lucrare de termen, adăugată 03.08.2015
Caracteristică industrie de contructie Teritoriul Krasnodar. Prognoza de dezvoltare construcția de locuințe. Metode și instrumente moderne de analiză a clusterelor. Metode statistice multidimensionale pentru diagnosticarea stării economice a unei întreprinderi.
teză, adăugată 20.07.2015
Caracteristicile creditării ipotecare pe exemplul regiunii Bryansk. Trecerea în revistă a metodelor matematice de luare a deciziilor: evaluări ale experților, comparații secvențiale și pereche, analiza ierarhiilor. Dezvoltarea unui program de căutare pentru creditul ipotecar optim.
lucrare de termen, adăugată 29.11.2012
Domeniile de aplicare ale analizei de sistem, locul, rolul, scopurile și funcțiile acesteia în știința modernă. Conceptul și conținutul metodelor de analiză a sistemului, metodele sale informale. Caracteristicile euristice și metode experte cercetarea și caracteristicile aplicării lor.
lucrare de termen, adăugată 20.05.2013
Dezvoltarea și cercetarea metodelor econometrice, ținând cont de specificul datelor economice și în concordanță cu nevoile științei și practicii economice. Aplicarea metodelor și modelelor econometrice pentru analiza statistică a datelor economice.
Această carte este dedicată doar uneia dintre cele mai promițătoare abordări ale analizei proceselor și fenomenelor multidimensionale în acest sens - analiza clusterului.
Analiza clusterelor este o modalitate de grupare a obiectelor multidimensionale, bazată pe prezentarea rezultatelor observațiilor individuale pe puncte ale unui spațiu geometric adecvat, urmată de selectarea grupurilor ca „clumps” ale acestor puncte. De fapt, „clusterul” (clusterul) în Limba englezăși înseamnă „cheag”, „cigh (de struguri)”, „cluster (de stele)”, etc. Acest termen se potrivește neobișnuit de bine în terminologia științifică, deoarece prima sa silabă corespunde termenului tradițional „clasă”, iar a doua, așa cum ar fi, indică originea sa artificială. Nu avem nicio îndoială că terminologia analizei cluster va înlocui toate constructele utilizate anterior în acest scop (recunoaștere nesupravegheată a modelelor, stratificare, taxonomie, clasificare automată etc.). Posibilitățile potențiale ale analizei cluster sunt evidente pentru rezolvarea, să zicem, a problemelor de identificare a grupurilor de întreprinderi care funcționează în condiții similare sau cu rezultate similare, a grupurilor omogene de populație în diverse aspecte ale vieții sau stilului de viață în general etc.
Ca direcție științifică, analiza cluster s-a declarat la mijlocul anilor '60 și de atunci se dezvoltă rapid, fiind una dintre ramurile celei mai intense creșteri a științei statistice. Este suficient să spunem că doar numărul de monografii privind analiza cluster publicate până în prezent în diferite țări este măsurat în sute (în timp ce, să zicem, conform unei astfel de metode „meritate” de analiză statistică multivariată precum analiza factorilor, cu greu se pot număra câteva zeci de cărți). Și acest lucru este destul de de înțeles. Până la urmă, vorbim de fapt despre modelarea operațiunii de grupare, una dintre cele mai importante nu numai în statistică, ci în general - atât în cogniție, cât și în luarea deciziilor.
În țara noastră au fost publicate o serie de monografii dedicate studiului problemelor socio-economice specifice folosind analiza cluster (1), metodologia de utilizare a analizei cluster în cercetarea socio-economică (2), metodologia analizei cluster ca atare ( 3) (Fundamentele analizei statistice)
Cartea propusă de I.D.Mandel este, parcă, perpendiculară pe această clasificare: conținutul ei este asociat cu fiecare dintre aceste trei domenii.
Scopul cărții este de a rezuma de ultimă oră analiza clusterului, analizează posibilitățile de utilizare a acestuia și sarcinile de dezvoltare ulterioară. Această idee în sine nu poate decât să trezească respect: o analiză imparțială și o generalizare necesită multă muncă, erudiție, curaj și sunt evaluate de comunitatea științifică mult mai puțin decât promovarea și dezvoltarea propriilor proiecte. (Cu toate acestea, cartea conține și dezvoltările originale ale autorului legate de analiza „intensională” și dualitatea clasificărilor.)
Atât avantajele cărții, cât și deficiențele ei sunt legate de realizarea acestui obiectiv. Avantajele ar trebui să includă:
· studiul metodologic al conceptelor de omogenitate, grupare și clasificare, ținând cont de multidimensionalitatea fenomenelor și proceselor;
· o revizuire sistematică a abordărilor și metodelor de analiză a clusterelor (inclusiv până la 150 de algoritmi specifici);
· prezentarea tehnologiei și a rezultatelor comparației experimentale a procedurilor de analiză a clusterelor; Această carte este dedicată doar uneia dintre cele mai promițătoare abordări ale analizei proceselor și fenomenelor multidimensionale în acest sens - analiza clusterului.
Analiza clusterelor este o modalitate de grupare a obiectelor multidimensionale, bazată pe prezentarea rezultatelor observațiilor individuale pe puncte ale unui spațiu geometric adecvat, urmată de selectarea grupurilor ca „clumps” ale acestor puncte. De fapt, „cluster” (cluster) în engleză înseamnă „cheag”, „buch (de struguri)”, „cluster (de stele)”, etc. Acest termen se potrivește neobișnuit de bine în terminologia științifică, deoarece prima sa silabă corespunde tradiționalului termenul „clasă”, iar al doilea, așa cum spune, indică originea sa artificială. Nu avem nicio îndoială că terminologia analizei cluster va înlocui toate constructele utilizate anterior în acest scop (recunoaștere nesupravegheată a modelelor, stratificare, taxonomie, clasificare automată etc.). Posibilitățile potențiale ale analizei cluster sunt evidente pentru rezolvarea, să zicem, a problemelor de identificare a grupurilor de întreprinderi care funcționează în condiții similare sau cu rezultate similare, a grupurilor omogene de populație în diverse aspecte ale vieții sau stilului de viață în general etc.
Ca direcție științifică, analiza cluster s-a declarat la mijlocul anilor '60 și de atunci se dezvoltă rapid, fiind una dintre ramurile celei mai intense creșteri a științei statistice. Este suficient să spunem că doar o serie de monografii privind analiza clusterului, elaborarea de scheme generale de utilizare a metodelor de analiză cluster, implementate în tabele destul de descriptive; caracterul de recomandare al prezentării.
Aceste avantaje determină locul independent al cărții lui I. D. Mandel printre alte publicații.
Neajunsurile cărții sunt ambiguitatea unor recomandări și lipsa unei analize sistematice a problemelor utilizării metodelor de analiză a clusterelor în aplicațiile socio-economice ale subiectului. Adevărat, aceasta din urmă se datorează utilizării insuficiente a analizei cluster în acest domeniu.
Cartea oferă o rampă de lansare, a cărei utilizare facilitează progresul în cea mai dificilă problemă a oricărei teorii - utilizarea practică a instrumentelor pe care le oferă.
B. G. Mirkin
1 . Adrianov A.Yu., Linzen L., Clusterele ca instrument de dezvoltare organizatii nonprofit// www.dis.ru.
2. Alimbaev A.A., Pritvorova T.P., Taubaev A.A. Formarea și dezvoltarea clusterelor în condițiile dezvoltării industriale și inovatoare a Republicii Kazahstan // www.liter.kz
3. Nota analitica pentru lunile iulie-august 2006 a Organului Teritorial Serviciul Federal statistici de statîn regiunea Astrakhan
4. Bludova S.N. Clusterele regionale ca modalitate de gestionare a complexului economic extern al regiunii // www.ncstu.ru
5. Borodatov A.V., Kozhevnikova V.D. Inițiativa de creare a unui cluster turistic și de agrement Sevastopol // Partener de afaceri. - 2004. - Nr. 10. - Cu. 33-37.
6. Buryak A.P., Voropov A.G. Analiza clusterelor - baza managementului competitivitatii la nivel macro // Marketing. - 2003. - Nr. 1. - Cu. 34-40.
7. Davydov A.R., Lyalkina G.B. Noi forme de organizare a procesului de inovare. Experiență internațională // www.dis.ru
8. Dranev Ya.N. Abordarea cluster a dezvoltării economice a teritoriilor. - M.: Editura „Skanrus”, 2003. - 195 p.
9. Zasimova L.S. Ratele de creștere ale producției din industria alimentară în regiunea Astrakhan // www.volgainform.ru
10. Kapustin A.N. Investiții în turism: calitate versus cantitate // www. astrakhan.net
11. Kut'in V.M. Agruparea economică teritorială (clasificarea) regiunilor rusești: aspect socio-geografic// Siguranța Eurasiei. - 2003. - Nr. 1. - Cu. 21-28.
12. Lee S. Clusters - noi forme de organizare a procesului de inovare // www.naukakaz.kz.
13. Lozinsky S., Prazdnichnykh A. Competitivitate și clustere industriale: o nouă agendă pentru afacerile și guvernul rusesc // World of Construction Industry. - 2003. - Nr. 2. - Cu. 32-41.
14. Martynov L.M. Ratele de creștere ale producției industriei alimentare din regiunea Astrakhan // www.caspy.net
15. Melnikova S.V. Baza prosperității turismului din Astrahan este o politică specială de mediu // Turismul în Rusia. - 2006. - Nr. 8. - Cu. 31-35.
16. Migranian A.A. Aspecte teoretice ale formării clusterelor competitive // www.dis.ru.
17. Mikheev Yu.V., Khasaev G.R. Clustere prin parteneriat pentru viitor // www.ptpu.ru.
18. Nikolaev M.V. Concentrarea clusterului de integrare efectivă a regiunilor în economia globală // www.subcontract.ru
19. Perkina M.V. Ospitalitate ia stelele din cer // Astrakhanskiye Vedomosti. - 2006. - Nr. 19. - Cu. 3.
20. Porter M.E. Concurenta: Per. din engleză: Uch. aşezare - M.: Editura Williams, 2000. - 495 p.
21. Porter M. Concurs internaţional. - M.: Intern. relaţii, 1993.- 869 p.
22. Decretul Guvernului regiunii Astrakhan din 2510.2006 Nr. 368-P privind programul țintă sectorial „Dezvoltarea turismului în regiunea Astrakhan pentru anul 2007”.
23. Programul de socializare dezvoltare economică Regiunea Astrakhan, ținând cont de dublarea produsului regional brut pentru 2005-2007.
24. Sviridov A.P. Ecoturismul poate salva regiunea Astrakhan // www.volga-astrakhan.ru
25. Simachev Yu.V. Clustering ca modalitate de a asigura competitivitatea regiunii // www.clusters-net.ru
26. Sokolenko S.I. De la cercetarea clusterelor la dezvoltarea structurilor comerciale și industriale de rețea// Russian Economic Journal. - 2004. - Nr. 6. - Cu. 10-15.
27. Sokolenko S.I. Dezvoltarea clusterelor turistice și recreative: o inițiativă regională a Ucrainei// Regiunii. - 2004. - Nr. 2. - Cu. 19-22.
28. Spankulova L.S. Probleme de dezvoltare a economiei cluster a industriei la nivel regional // AlPari. - 2004. - Nr. 2. - Cu. 16-
29. Anuarul statistic al dezvoltării socio-economice a regiunii Astrakhan 2004, 2005 / Organul teritorial al Serviciului Federal de Stat de Statistică pentru Regiunea Astrakhan
30. Steblyakova L.P. Probleme de creare și dezvoltare a clusterelor economice: experiența țărilor străine // Proceedings of the Karaganda University of Business, Management and Law. - 2005. - Nr. 2. - Cu. 22-29.
31. Steblyakova L.P., Vechkinzova E.A. Formarea clusterelor de competitivitate în Kazahstanul central // www.liter.kz
32. plan strategic dezvoltare municipalitate„Orașul Astrakhan” pentru 2005 - 2010
33. Strategia de dezvoltare a turismului în regiunea Astrakhan pe termen mediu și lung, 2005
34. Filippov P. Clustere de competitivitate // Expert. - 2003.- Nr. 43. - Cu. 10-15.
35. Tsikhan T.V. Teoria clusterelor a dezvoltării economice// Teoria și practica managementului. - 2003. - Nr. 5. - Cu. 22-25.
36 . Chulok A.A. Mecanisme de creștere a competitivității economiei regionale // www.subcontract.ru
37. Shehovtsova L.S. Clusterul ca instrument modern pentru creșterea competitivității în regiune // www.clusters-net.ru
38 www.astrahanpages.com
39. www.astrasocial.ru
40 www. astrgorod.ru
41 www. astrobl.ru
42 www. astour.ru
43. www.economy.astrobl.ru
ANALIZA CLUSTERĂ ÎN PROBLEME DE PROVIZIUNE SOCIO-ECONOMICA
Introducere în analiza clusterelor.
Atunci când analizează și prognozează fenomene socio-economice, cercetătorul întâlnește adesea multidimensionalitatea descrierii acestora. Acest lucru se întâmplă atunci când se rezolvă problema segmentării pieței, se construiește o tipologie de țări în funcție de un număr suficient de mare de indicatori, se prezice situația pieței pentru bunuri individuale, se studiază și se prevede depresia economică și multe alte probleme.
Metodele de analiză multivariată reprezintă cel mai eficient instrument cantitativ pentru studierea proceselor socio-economice descrise printr-un număr mare de caracteristici. Acestea includ analiza cluster, taxonomia, recunoașterea modelelor și analiza factorială.
Analiza cluster reflectă cel mai clar caracteristicile analizei multivariate în clasificare, analiza factorială - în studiul comunicării.
Uneori, abordarea analizei cluster este menționată în literatură ca taxonomie numerică, clasificare numerică, recunoaștere prin auto-învățare etc.
Analiza cluster și-a găsit prima aplicație în sociologie. Denumirea de analiză a grupului provine din cuvântul englezesc cluster - bunch, acumulation. Pentru prima dată în 1939, subiectul analizei cluster a fost definit și descrierea acestuia a fost făcută de către cercetătorul Trion. Scopul principal al analizei cluster este de a împărți setul de obiecte și caracteristici studiate în grupuri sau clustere care sunt omogene în sensul corespunzător. Aceasta înseamnă că problema clasificării datelor și identificării structurii corespunzătoare din acestea este în curs de rezolvare. Metodele de analiză a clusterelor pot fi aplicate într-o varietate de cazuri, chiar și atunci când este vorba de o simplă grupare, în care totul se reduce la formarea grupurilor prin similitudine cantitativă.
Marele avantaj al analizei cluster este că vă permite să partiționați obiectele nu după un parametru, ci după un întreg set de caracteristici. În plus, analiza cluster, spre deosebire de majoritatea metodelor matematice și statistice, nu impune nicio restricție asupra tipului de obiecte luate în considerare și ne permite să luăm în considerare un set de date inițiale de natură aproape arbitrară. Acest lucru este de mare importanță, de exemplu, pentru prognoza conjuncturii, când indicatorii au o varietate de forme care fac dificilă utilizarea abordărilor econometrice tradiționale.
Analiza cluster face posibilă luarea în considerare a unei cantități suficient de mare de informații și reducerea drastică, comprimarea unor palete mari de informații socio-economice, făcându-le compacte și vizuale.
Analiza clusterelor este de mare importanță în raport cu seturile de serii cronologice care caracterizează dezvoltarea economică (de exemplu, condițiile economice generale și ale mărfurilor). Aici este posibil să se evidențieze perioadele în care valorile indicatorilor corespunzători au fost destul de apropiate, precum și să se determine grupurile de serii temporale, a căror dinamică este cel mai asemănătoare.
Analiza cluster poate fi utilizată ciclic. În acest caz, studiul se efectuează până la obținerea rezultatelor dorite. În același timp, fiecare ciclu de aici poate oferi informații care pot schimba foarte mult direcția și abordările de aplicare ulterioară a analizei cluster. Acest proces poate fi reprezentat ca un sistem de feedback.
În problemele de prognoză socio-economică, este foarte promițătoare să se combine analiza clusterului cu alte metode cantitative (de exemplu, cu analiza de regresie).
Ca orice altă metodă, analiza clusterului are anumite dezavantaje și limitări: în special, compoziția și numărul de clustere depind de criteriile de partiționare selectate. La reducerea matricei de date inițiale la o formă mai compactă, pot apărea anumite distorsiuni, iar caracteristicile individuale ale obiectelor individuale pot fi, de asemenea, pierdute din cauza înlocuirii lor cu caracteristicile valorilor generalizate ale parametrilor clusterului. La clasificarea obiectelor, de foarte multe ori este ignorată posibilitatea absenței oricăror valori de grup în setul considerat.
În analiza clusterului, se consideră că:
a) caracteristicile selectate permit, în principiu, gruparea dorită;
b) unitățile de măsură (scara) sunt alese corect.
Alegerea scalei joacă un rol important. De obicei, datele sunt normalizate prin scăderea mediei și împărțirea la abaterea standard, astfel încât varianța să fie egală cu unu.
Problema analizei clusterelor.
Sarcina analizei cluster este de a împărți mulțimea de obiecte G în m (m este un întreg) clustere (subseturi) Q1, Q2, ..., Qm, pe baza datelor conținute în mulțimea X, astfel încât fiecare obiect Gj aparține unuia și numai unui subset de partiții și că obiectele aparținând aceluiași cluster sunt similare, în timp ce obiectele aparținând unor clustere diferite sunt eterogene.
De exemplu, să fie G să includă n țări, fiecare dintre acestea fiind caracterizată de PNB pe cap de locuitor (F1), numărul M de mașini la 1.000 de persoane (F2), consumul de energie electrică pe cap de locuitor (F3), consumul de oțel pe cap de locuitor (F4), etc. Atunci X1 (vector de măsurare) este un set de caracteristici specificate pentru prima țară, X2 pentru a doua, X3 pentru a treia și așa mai departe. Provocarea este de a defalca țările după nivelul de dezvoltare.
Soluția problemei analizei cluster sunt partițiile care îndeplinesc un anumit criteriu de optimitate. Acest criteriu poate fi unul funcțional care exprimă nivelurile de dezirabilitate ale diferitelor partiții și grupări, care se numește funcție obiectiv. De exemplu, suma intragrupului a abaterilor pătrate poate fi luată ca funcție obiectiv:
unde xj - reprezintă măsurătorile obiectului j-lea.
Pentru a rezolva problema analizei cluster, este necesar să se definească conceptul de similaritate și eterogenitate.
Este clar că obiectele i-lea și j-lea ar cădea în același grup atunci când distanța (distanța) dintre punctele Xi și Xj ar fi suficient de mică și ar cădea în grupuri diferite când această distanță ar fi suficient de mare. Astfel, intrarea în unul sau mai multe grupuri de obiecte este determinată de conceptul distanței dintre Xi și Xj față de Ep, unde Ep este un spațiu euclidian p-dimensional. O funcție nenegativă d(Xi, Xj) se numește funcție de distanță (metrică) dacă:
a) d(Xi , Xj) ³ 0, pentru toate Xi și Xj din Ep
b) d(Xi, Xj) = 0 dacă și numai dacă Xi = Xj
c) d(Xi, Xj) = d(Xj, Xi)
d) d(Xi, Xj) £ d(Xi, Xk) + d(Xk, Xj), unde Xj; Xi și Xk sunt oricare trei vectori din Ep.
Valoarea d(Xi, Xj) pentru Xi și Xj se numește distanța dintre Xi și Xj și este echivalentă cu distanța dintre Gi și Gj în funcție de caracteristicile selectate (F1, F2, F3, ..., Fр).
Cele mai frecvent utilizate funcții de distanță sunt:
1. Distanța euclidiană d2(Хi , Хj) =
2. l1 - norma d1(Хi , Хj) =
3. Supremum - norma d¥ (Хi , Хj) = sup
k = 1, 2, ..., p
4. lp - norma dр(Хi , Хj) =
Metrica euclidiană este cea mai populară. Valoarea l1 este cea mai ușor de calculat. Norma supremă este ușor de calculat și include o procedură de ordonare, în timp ce norma-lp acoperă funcțiile de distanță 1, 2, 3,.
Fie n măsurători X1, X2,..., Xn să fie reprezentate ca o matrice de date p´n:
Atunci distanța dintre perechile de vectori d(Хi , Хj) poate fi reprezentată ca o matrice de distanțe simetrice:
Conceptul opus distanței este conceptul de similitudine între obiectele Gi. iar Gj. O funcție reală nenegativă S(Хi ; Хj) = Sij se numește măsură de similitudine dacă:
1) 0 £ S(Xi , Xj)<1 для Хi¹ Хj
2) S(Хi , Хi) = 1
3) S(Xi, Xj) = S(Xj, Xi)
Perechile de valori de măsurare a similitudinii pot fi combinate într-o matrice de similaritate:
Valoarea lui Sij se numește coeficient de similitudine.
1.3. Metode de analiză a clusterelor.
Astăzi există multe metode de analiză a clusterelor. Să ne oprim asupra unora dintre ele (metodele prezentate mai jos sunt de obicei numite metode ale variației minime).
Fie X matricea de observație: X = (X1, X2,..., Xu) iar pătratul distanței euclidiene dintre Xi și Xj este determinat de formula:
1) Metoda conexiunilor complete.
Esența acestei metode este că două obiecte aparținând aceluiași grup (cluster) au un coeficient de similaritate care este mai mic decât o anumită valoare de prag S. În ceea ce privește distanța euclidiană d, aceasta înseamnă că distanța dintre două puncte (obiecte) de clusterul nu trebuie să depășească o anumită valoare prag h. Astfel, h determină diametrul maxim admisibil al unui subset care formează un cluster.
2) Metoda distanței locale maxime.
Fiecare obiect este considerat ca un cluster cu un singur punct. Obiectele sunt grupate după următoarea regulă: două grupuri sunt combinate dacă distanța maximă dintre punctele unui grup și punctele altuia este minimă. Procedura constă din n - 1 pași și are ca rezultat partiții care se potrivesc cu toate partițiile posibile din metoda anterioară pentru orice valoare de prag.
3) Metoda Word.
În această metodă, suma intragrup a abaterilor pătrate este utilizată ca funcție obiectiv, care nu este altceva decât suma distanțelor pătrate dintre fiecare punct (obiect) și media pentru clusterul care conține acest obiect. La fiecare pas se combină două clustere care conduc la creșterea minimă a funcției obiectiv, adică. suma de pătrate intragrup. Această metodă are ca scop combinarea clusterelor strâns distanțate.
4) Metoda centroidă.
Distanța dintre două clustere este definită ca distanța euclidiană dintre centrele (mediile) acestor clustere:
d2 ij = (`X – `Y)Т(`X – `Y) Agruparea se desfășoară pas cu pas la fiecare dintre n–1 pași, combină două grupuri G și p având valoarea minimă d2ij Dacă n1 este mult mai mare decât n2, atunci centrele de unire a două clustere sunt apropiate unul de celălalt, iar caracteristicile celui de-al doilea cluster sunt practic ignorate atunci când clusterele sunt combinate. Uneori, această metodă este uneori numită și metoda grupurilor ponderate.
1.4 Algoritm de grupare secvenţială.
Considerați Ι = (Ι1, Ι2, … Ιn) ca un set de clustere (Ι1), (Ι2),...(Ιn). Să alegem două dintre ele, de exemplu, Ι i și Ι j, care sunt într-un anumit sens mai aproape unul de celălalt și să le combinăm într-un singur grup. Noul set de clustere, format deja din n-1 clustere, va fi:
(Ι1), (Ι2)…, (Ι i , Ι j), …, (Ιn).
Repetând procesul, obținem seturi succesive de clustere formate din (n-2), (n-3), (n-4), etc. clustere. La sfârșitul procedurii, puteți obține un cluster format din n obiecte și care coincide cu mulțimea inițială Ι = (Ι1, Ι2, … Ιn).
Ca măsură a distanței, luăm pătratul metricii euclidiene di j2. și se calculează matricea D = (di j2), unde di j2 este pătratul distanței dintre
I1 | I2 | I3 | …. | Ιn | |
I1 | 0 | d122 | d132 | …. | d1n2 |
I2 | 0 | d232 | …. | d2n2 | |
I3 | 0 | …. | d3n2 | ||
…. | …. | …. | |||
Ιn | 0 |
Fie distanța dintre Ι i și Ι j minimă:
di j2 = min (di j2, i ¹ j). Cu ajutorul lui Ι i și Ι j formăm un nou grup
(I, Ij). Construiți o nouă matrice de distanțe ((n-1), (n-1)).
(I i , I j) | I1 | I2 | I3 | …. | Ιn | |
(I i ; I j) | 0 | di j21 | di j22 | di j23 | …. | di j2n |
I1 | 0 | d122 | d13 | …. | d12n | |
I2 | 0 | di j21 | …. | d2n | ||
I3 | 0 | …. | d3n | |||
Ιn | 0 |
(n-2) rânduri pentru ultima matrice sunt luate din cea anterioară, iar primul rând este recalculat. Calculele pot fi reduse la minimum dacă di j2k,k = 1, 2,…, n poate fi exprimat; (k ¹ i ¹ j) prin elementele matricei originale.
Inițial, distanța a fost determinată doar între clustere cu un singur element, dar este și necesar să se determine distanța dintre clusterele care conțin mai mult de un element. Acest lucru se poate face în diverse moduri și, în funcție de metoda aleasă, obținem algoritmi de analiză a clusterelor cu proprietăți diferite. Se poate, de exemplu, seta distanța dintre cluster i + j și un alt grup k egală cu media aritmetică a distanțelor dintre clusterele i și k și clusterele j și k:
di+j,k = ½ (di k + dj k).
Dar se poate defini și di+j,k ca minim dintre aceste două distanțe:
di+j,k = min(di k + dj k).
Astfel, este descris primul pas al operației algoritmului ierarhic aglomerativ. Următorii pași sunt aceiași.
O clasă destul de largă de algoritmi poate fi obținută dacă se folosește următoarea formulă generală pentru a recalcula distanțe:
di+j,k = A(w) min(dik djk) + B(w) max(dik djk), unde
A(w) = dacă dik £ djk
A(w) = dacă dik > djk
B(w) = dacă dik £ djk
B(w) = dacă dik > djk
unde ni și nj sunt numărul de elemente din clusterele i și j, iar w este un parametru liber, a cărui alegere determină un anumit algoritm. De exemplu, cu w = 1, obținem așa-numitul algoritm de „conexiune medie”, pentru care formula pentru recalcularea distanțelor ia forma:
di+j,k =
LA acest caz distanța dintre două grupuri la fiecare pas al algoritmului se dovedește a fi egală cu media aritmetică a distanțelor dintre toate perechile de elemente, astfel încât un element al perechii aparține unui grup, celălalt altuia.
Sensul vizual al parametrului w devine clar dacă punem w®¥. Formula de conversie a distanței ia forma:
di+j,k = min(di,k djk)
Acesta va fi așa-numitul algoritm „cel mai apropiat vecin”, care vă permite să selectați grupuri de forme arbitrar complexe, cu condiția ca diferite părți ale unor astfel de grupuri să fie conectate prin lanțuri de elemente apropiate unele de altele. În acest caz, distanța dintre două clustere la fiecare pas al algoritmului se dovedește a fi egală cu distanța dintre cele mai apropiate două elemente aparținând acestor două clustere.
Destul de des se presupune că sunt date distanțele inițiale (diferențele) dintre elementele grupate. În unele cazuri, acest lucru este adevărat. Cu toate acestea, sunt specificate doar obiectele și caracteristicile lor, iar matricea distanțelor este construită pe baza acestor date. În funcție de faptul că distanțele dintre obiecte sau dintre caracteristicile obiectelor sunt calculate, se folosesc metode diferite.
În cazul analizei în cluster a obiectelor, cea mai comună măsură a diferenței este fie pătratul distanței euclidiene
(unde xih, xjh sunt valorile atributului h-lea pentru obiectele i-lea și j-lea, iar m este numărul de caracteristici) sau distanța euclidiană în sine. Dacă caracteristicilor li se atribuie greutăți diferite, atunci aceste greutăți pot fi luate în considerare la calcularea distanței
Uneori, distanța este folosită ca măsură a diferenței, calculată prin formula:
care se numesc: „Hamming”, „Manhattan” sau „oraș-bloc” distanță.
O măsură naturală a asemănării caracteristicilor obiectelor în multe probleme este coeficientul de corelație dintre ele
unde mi ,mj ,di ,dj sunt abaterile medii și pătratice medii pentru caracteristicile i și, respectiv, j. Valoarea 1 - r poate servi ca măsură a diferenței dintre caracteristici. În unele probleme, semnul coeficientului de corelație este nesemnificativ și depinde doar de alegerea unității de măsură. În acest caz, ô1 - ri j ô este folosit ca măsură a diferenței dintre caracteristici
1.5 Numărul de clustere.
Foarte problema importanta este problema alegerii numărului necesar de clustere. Uneori, m număr de clustere poate fi ales a priori. Cu toate acestea, în cazul general, acest număr este determinat în procesul de împărțire a setului în grupuri.
Studiile au fost efectuate de Fortier și Solomon și s-a constatat că numărul de clustere trebuie luat pentru a obține probabilitatea ca cea mai bună partiție să fie găsită. Astfel, numărul optim de partiții este o funcție a unei fracții date b a celor mai bune sau, într-un anumit sens, a partițiilor fezabile din setul tuturor partițiilor posibile. Difuzarea totală va fi cu atât mai mare, cu cât fracția b de partiții admisibile este mai mare. Fortier și Solomon au dezvoltat un tabel din care se poate găsi numărul de partiții necesare. S(a,b) în funcție de a și b (unde a este probabilitatea ca cea mai bună partiție să fie găsită, b este proporția celor mai bune partiții în numărul total de partiții) Mai mult, ca măsură a eterogenității, nu a împrăștierii este folosită măsura, dar măsura aderării introdusă de Holzenger și Harman. Tabelul valorilor S(a,b) este prezentat mai jos.
Tabelul valorilor S(a,b).
b\a | 0.20 | 0.10 | 0.05 | 0.01 | 0.001 | 0.0001 |
0.20 | 8 | 11 | 14 | 21 | 31 | 42 |
0.10 | 16 | 22 | 29 | 44 | 66 | 88 |
0.05 | 32 | 45 | 59 | 90 | 135 | 180 |
0.01 | 161 | 230 | 299 | 459 | 689 | 918 |
0.001 | 1626 | 2326 | 3026 | 4652 | 6977 | 9303 |
0.0001 | 17475 | 25000 | 32526 | 55000 | 75000 | 100000 |
Destul de des, criteriul de combinare (numărul de clustere) este schimbarea funcției corespunzătoare. De exemplu, sumele abaterilor pătrate:
Procesul de grupare ar trebui să corespundă aici unei creșteri minime consistente a valorii criteriului E. Prezența unui salt brusc în valoarea lui E poate fi interpretată ca o caracteristică a numărului de clustere care există în mod obiectiv în populația studiată.
Deci, a doua modalitate de a defini cel mai bun număr clusterele se reduce la identificarea salturilor determinate de tranziția de fază de la o stare a obiectelor puternic cuplată la o stare slab cuplată.
1.6 Dendograme.
Cea mai cunoscută metodă de reprezentare a unei matrice de distanță sau similaritate se bazează pe ideea unei dendograme sau diagramă arborescentă. Dendograma poate fi definită ca o reprezentare grafică a rezultatelor procesului de grupare secvenţială, care se realizează în termenii unei matrice de distanţe. Cu ajutorul unei dendograme, este posibilă reprezentarea grafică sau geometrică a procedurii de grupare, cu condiția ca această procedură să funcționeze numai cu elemente ale matricei de distanță sau similaritate.
Există multe moduri de a construi dendrograme. În dendrogramă, obiectele sunt situate vertical în stânga, rezultatele grupării sunt în dreapta. Valorile de distanță sau de similitudine corespunzătoare structurii noilor clustere sunt afișate de-a lungul unei linii drepte orizontale peste dendrograme.
Figura 1 prezintă un exemplu de dendogramă. Figura 1 corespunde cazului a șase obiecte (n=6) și k caracteristici (trăsături). Obiectele A și C sunt cele mai apropiate și, prin urmare, sunt combinate într-un singur grup la nivelul de proximitate egal cu 0,9. Obiectele D și E sunt combinate la un nivel de 0,8. Acum avem 4 clustere:
Tipul dendogramei depinde de alegerea măsurii de similitudine sau de distanța dintre obiect și cluster și de metoda de grupare. Cel mai important punct este alegerea unei măsuri de similitudine sau a unei măsuri a distanței dintre un obiect și un cluster.
Numărul de algoritmi de analiză cluster este prea mare. Toate pot fi împărțite în ierarhice și neierarhice.
Algoritmii ierarhici sunt asociați cu construcția dendogramelor și sunt împărțiți în:
a) aglomerativ, caracterizat printr-o combinație consistentă de elemente inițiale și o scădere corespunzătoare a numărului de clustere;
b) divizibil (divizibil), în care numărul de clustere crește, începând de la unul, în urma căruia se formează o succesiune de grupuri de scindare.
Algoritmii de analiză a clusterelor au astăzi o implementare software bună care permite rezolvarea problemelor de cea mai mare dimensiune.
1.7 Date
Analiza cluster poate fi aplicată datelor de interval, frecvențe, date binare. Este important ca variabilele să se schimbe pe scale comparabile.
Eterogenitatea unităților de măsură și imposibilitatea care rezultă a unei exprimări rezonabile a valorilor diferiților indicatori pe aceeași scară duce la faptul că distanța dintre puncte, reflectând poziția obiectelor în spațiul proprietăților lor, se dovedește să depindă de o scară aleasă în mod arbitrar. Pentru a elimina eterogenitatea măsurării datelor inițiale, toate valorile lor sunt preliminar normalizate, adică. sunt exprimate prin raportul dintre aceste valori la o anumită valoare care reflectă anumite proprietăți ale acestui indicator. Normalizarea datelor inițiale pentru analiza cluster se realizează uneori prin împărțirea valorilor inițiale la abaterea standard a indicatorilor corespunzători. O altă modalitate este de a calcula așa-numita contribuție standardizată. Se mai numește și contribuția Z.
Contribuția z arată câte abateri standard se separă o anumită observație de medie:
Unde xi este valoarea acestei observații, este media, S este abaterea standard.
Media pentru contribuțiile Z este zero, iar abaterea standard este 1.
Standardizarea permite compararea observațiilor din diferite distribuții. Dacă distribuția unei variabile este normală (sau aproape de normal) și media și varianța sunt cunoscute sau estimate din eșantioane mari, atunci contribuția Z a unei observații oferă informații mai specifice despre locația acesteia.
Rețineți că metodele de normalizare înseamnă recunoașterea tuturor caracteristicilor ca echivalente din punctul de vedere al elucidării asemănării obiectelor luate în considerare. S-a remarcat deja că în raport cu economie, recunoașterea echivalenței diferiților indicatori nu pare întotdeauna justificată. Ar fi de dorit, împreună cu normalizarea, să se acorde fiecărui indicator o pondere care să reflecte semnificația sa în cursul stabilirii asemănărilor și diferențelor dintre obiecte.
În această situație, trebuie să recurgeți la metoda de determinare a ponderilor indicatorilor individuali - un sondaj de experți. De exemplu, atunci când am rezolvat problema clasificării țărilor în funcție de nivelul de dezvoltare economică, am folosit rezultatele unui sondaj a 40 de experți de top din Moscova privind problemele țărilor dezvoltate pe o scară de zece puncte:
indicatori generalizați ai dezvoltării socio-economice - 9 puncte;
indicatori de distribuție sectorială a populației ocupate - 7 puncte;
indicatori ai prevalenței forței de muncă angajate - 6 puncte;
indicatori care caracterizează elementul uman al forțelor productive - 6 puncte;
indicatori ai dezvoltării forțelor productive materiale - 8 puncte;
indicator al cheltuielilor publice - 4 puncte;
indicatori „militar-economici” - 3 puncte;
indicatori socio-demografici - 4 puncte.
Estimările experților au fost relativ stabile.
Evaluările experților oferă o bază binecunoscută pentru a determina importanța indicatorilor incluși într-un anumit grup de indicatori. Înmulțirea valorilor normalizate ale indicatorilor cu un coeficient corespunzător punctajului mediu al evaluării face posibilă calcularea distanțelor dintre punctele care reflectă poziția țărilor într-un spațiu multidimensional, ținând cont de ponderea inegală a caracteristicilor acestora.
Destul de des, atunci când se rezolvă astfel de probleme, se folosesc nu unul, ci două calcule: primul, în care toate semnele sunt considerate echivalente, al doilea, în care li se acordă ponderi diferite în conformitate cu valorile medii ale estimărilor experților.
1.8. Aplicarea analizei cluster.
Să luăm în considerare câteva aplicații ale analizei cluster.
Împărțirea țărilor în grupe în funcție de nivelul de dezvoltare.
65 de țări au fost studiate după 31 de indicatori (venitul național pe cap de locuitor, ponderea populației ocupate în industrie în %, economiile pe cap de locuitor, ponderea populației ocupate în agricultură în %, speranța medie de viață, numărul de mașini la 1). mii de locuitori, numărul forțelor armate la 1 milion de locuitori, pondere în PIB industrial în %, pondere în PIB Agriculturăîn % etc.)
Fiecare dintre țări acționează în acest considerent ca un obiect caracterizat prin anumite valori a 31 de indicatori. În consecință, ele pot fi reprezentate ca puncte într-un spațiu cu 31 de dimensiuni. Un astfel de spațiu este de obicei numit spațiu de proprietate al obiectelor studiate. Compararea distanței dintre aceste puncte va reflecta gradul de proximitate a țărilor luate în considerare, asemănarea lor între ele. Sensul socio-economic al acestei înțelegeri a similitudinii înseamnă că țările sunt considerate cu cât mai asemănătoare, cu atât diferențele dintre aceiași indicatori cu care sunt descrise sunt mai mici.
Primul pas într-o astfel de analiză este identificarea unei perechi economii nationale, luată în considerare în matricea de similaritate, distanța dintre care este cea mai mică. Acestea vor fi, evident, cele mai asemănătoare economii. În considerarea următoare, ambele țări sunt considerate un singur grup, un singur grup. În consecință, matricea originală este transformată astfel încât elementele sale să fie distanțele dintre toate perechile posibile, nu 65, ci 64 de obiecte - 63 de economii și un cluster nou transformat - o uniune condiționată a celor două țări cele mai asemănătoare. Rândurile și coloanele corespunzătoare distanțelor de la o pereche de țări incluse în unire la toate celelalte sunt eliminate din matricea de similaritate inițială, dar se adaugă un rând și o coloană care conțin distanța dintre clusterul obținut de uniune și alte țări.
Se presupune că distanța dintre noul cluster și țări este egală cu media distanțelor dintre acesta din urmă și cele două țări care alcătuiesc noul cluster. Cu alte cuvinte, grupul combinat de țări este tratat ca un întreg cu caracteristici aproximativ egale cu media caracteristicilor țărilor sale constitutive.
Al doilea pas al analizei este să luăm în considerare o matrice transformată în acest fel cu 64 de rânduri și coloane. Din nou, se identifică o pereche de economii, distanța dintre care este de cea mai mică importanță și ele, la fel ca în primul caz, sunt reunite. În acest caz, cea mai mică distanță poate fi atât între o pereche de țări, cât și între orice țară și uniunea de țări obținută în etapa anterioară.
Alte proceduri sunt similare cu cele descrise mai sus: în fiecare etapă, matricea este transformată astfel încât două coloane și două rânduri care conțin distanța până la obiecte (perechi de țări sau asociații - clustere) reunite în etapa anterioară sunt excluse din aceasta. ; rândurile și coloanele excluse sunt înlocuite cu o coloană și un rând care conține distanțele de la noile îmbinări la restul caracteristicilor; în continuare, în matricea modificată, se dezvăluie o pereche de obiecte cele mai apropiate. Analiza continuă până la epuizarea completă a matricei (adică până când toate țările sunt reunite). Rezultatele generalizate ale analizei matriceale pot fi reprezentate sub forma unui arbore de similaritate (dendogramă), similar celui descris mai sus, cu singura diferență că arborele de similaritate, care reflectă proximitatea relativă a tuturor celor 65 de țări pe care le luăm în considerare, este mult mai complicată decât schema în care apar doar cinci economii naţionale. Acest arbore include 65 de niveluri în funcție de numărul de obiecte potrivite. Primul nivel (inferior) conține puncte corespunzătoare fiecărei țări separat. Legătura dintre aceste două puncte la al doilea nivel arată o pereche de țări care sunt cele mai apropiate din punct de vedere al tipului general de economii naționale. La al treilea nivel, se notează următorul cel mai asemănător raport de perechi de țări (după cum sa menționat deja, fie o nouă pereche de țări, fie o nouă țară și o pereche deja identificată de țări similare pot fi în acest raport). Și așa mai departe până la ultimul nivel, la care toate țările studiate acționează ca un singur set.
Ca rezultat al aplicării analizei cluster, au fost obținute următoarele cinci grupuri de țări:
grup afro-asiatic;
grup latino-asiatic;
grup latino-mediteranean;
grup de țări capitaliste dezvoltate (fără SUA)
Introducerea de noi indicatori dincolo de cei 31 de indicatori utilizați aici, sau înlocuirea lor cu alții, duce în mod firesc la o modificare a rezultatelor clasificării țărilor.
2. Împărțirea țărilor după criteriul proximității de cultură.
După cum știți, marketingul trebuie să țină cont de cultura țărilor (obiceiuri, tradiții etc.).
Următoarele grupuri de țări au fost obținute prin grupare:
Arabic;
Orientul Mijlociu;
Scandinav;
vorbitor de germană;
Vorbitor de engleza;
romanic european;
America Latină;
Orientul îndepărtat.
3. Elaborarea unei prognoze a pieței zincului.
Analiza cluster joacă un rol important în stadiul de reducere a modelului economico-matematic al conjuncturii mărfurilor, contribuind la facilitarea și simplificarea procedurilor de calcul, asigurând o mai mare compactitate a rezultatelor obținute, păstrând în același timp acuratețea necesară. Utilizarea analizei cluster face posibilă împărțirea întregului set inițial de indicatori de piață în grupuri (clustere) în funcție de criteriile relevante, facilitând astfel selecția celor mai reprezentativi indicatori.
Analiza cluster este utilizată pe scară largă pentru a modela condițiile de piață. În practică, majoritatea sarcinilor de prognoză se bazează pe utilizarea analizei cluster.
De exemplu, sarcina de a dezvolta o prognoză a pieței zincului.
Inițial, au fost selectați 30 de indicatori cheie ai pieței globale de zinc:
X1 - timp
Cifre de productie:
X2 - în lume
X4 - Europa
X5 - Canada
X6 - Japonia
X7 - Australia
Indicatori de consum:
X8 - în lume
X10 - Europa
X11 - Canada
X12 - Japonia
X13 - Australia
Stocuri de zinc ale producătorilor:
X14 - în lume
X16 - Europa
X17 - alte țări
Stocuri de zinc de consum:
X18 - în SUA
X19 - în Anglia
X10 - în Japonia
Import de minereuri și concentrate de zinc (mii de tone)
X21 - în SUA
X22 - în Japonia
X23 - în Germania
Export de minereuri și concentrate de zinc (mii de tone)
X24 - din Canada
X25 - din Australia
Import de zinc (mii de tone)
X26 - în SUA
X27 - spre Anglia
X28 - în Germania
Export de zinc (mii de tone)
X29 - din Canada
X30 - din Australia
Pentru determinarea dependențelor specifice a fost utilizat aparatul de analiză de corelație și regresie. Relațiile au fost analizate pe baza unei matrice de coeficienți de corelație perechi. Aici a fost acceptată ipoteza distribuţiei normale a indicatorilor analizaţi ai conjuncturii. Este clar că rij nu sunt singurul indicator posibil al relației dintre indicatorii utilizați. Necesitatea utilizării analizei cluster în această problemă se datorează faptului că numărul de indicatori care afectează prețul zincului este foarte mare. Este necesar să le reducă din mai multe dintre următoarele motive:
a) lipsa datelor statistice complete pentru toate variabilele;
b) o complicare accentuată a procedurilor de calcul atunci când un număr mare de variabile sunt introduse în model;
c) utilizarea optimă a metodelor de analiză de regresie necesită depășirea numărului de valori observate asupra numărului de variabile de cel puțin 6-8 ori;
d) dorinta de a folosi variabile independente statistic in model etc.
Este foarte dificil să se realizeze o astfel de analiză direct pe o matrice relativ voluminoasă de coeficienți de corelație. Cu ajutorul analizei cluster, întregul set de variabile ale pieței poate fi împărțit în grupuri, astfel încât elementele fiecărui cluster să fie puternic corelate între ele, iar reprezentanții grupuri diferite au fost slab corelate.
Pentru a rezolva această problemă, a fost aplicat unul dintre algoritmii de analiză a clusterelor ierarhice aglomerative. La fiecare pas, numărul de clustere se reduce cu unul datorită unirii optime, într-un anumit sens, a două grupuri. Criteriul de alăturare este schimbarea funcției corespunzătoare. În funcție de aceasta, au fost utilizate valorile sumelor abaterilor pătrate calculate prin următoarele formule:
(j = 1, 2, …, m),
unde j este numărul clusterului, n este numărul de elemente din cluster.
rij - coeficient de corelație de pereche.
Astfel, procesul de grupare trebuie să corespundă unei creșteri minime secvențiale a valorii criteriului E.
În prima etapă, matricea inițială de date este prezentată ca un set format din clustere, incluzând câte un element fiecare. Procesul de grupare începe cu unirea unei astfel de perechi de clustere, ceea ce duce la o creștere minimă a sumei abaterilor pătrate. Aceasta necesită estimarea sumei abaterilor pătrate pentru fiecare dintre posibilele uniuni de cluster. În etapa următoare, valorile sumelor abaterilor pătrate sunt deja luate în considerare pentru clustere și așa mai departe. Acest proces va fi oprit la un pas. Pentru a face acest lucru, trebuie să monitorizați valoarea sumei abaterilor pătrate. Considerând o succesiune de valori crescătoare, se poate prinde un salt (una sau mai multe) în dinamica acesteia, care poate fi interpretat ca o caracteristică a numărului de grupuri „obiectiv” existente în populația studiată. În exemplul de mai sus, salturile au avut loc atunci când numărul de grupuri era 7 și 5. În plus, numărul de grupuri nu trebuie redus, deoarece aceasta duce la o scădere a calității modelului. După obținerea clusterelor, variabilele cele mai importante în sens economicși cel mai strâns legat de criteriul de piață ales - în acest caz, London Metal Exchange cotează pentru zinc. Această abordare vă permite să salvați o parte semnificativă a informațiilor conținute în setul original de indicatori inițiali ai conjuncturii.