Literatura de analiză a clusterelor. Ministerul Educației și Științei al Federației Ruse

Trimiteți-vă munca bună în baza de cunoștințe este simplu. Utilizați 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

„Analiza cluster este un set de metode matematice menite să formeze grupuri de obiecte care sunt relativ „depărtate” unele de altele, „aproape” unele de altele, pe baza informațiilor despre distanțe sau conexiuni (măsuri de proximitate) între ele. Semnificația este similar termenilor: clasificare automată, taxonomie, recunoaștere a modelelor fără profesor." Această definiție a analizei cluster este dată în cea mai recentă ediție a Dicționarului Statistic. De fapt, „analiza cluster” este un nume generalizat pentru un set destul de mare de algoritmi folosiți pentru a crea o clasificare. Un număr de publicații folosesc, de asemenea, sinonime pentru analiza clusterului, cum ar fi clasificarea și partiționarea. Analiza 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 construirea și testarea ipotezelor și teoriilor științifice este imposibilă. Astfel, în munca mea, scopul meu principal este să iau în considerare problemele analizei cluster (elementele de bază ale analizei cluster), precum și să iau în considerare terminologia acesteia și să dau 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 V.V. 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. Czekanovsky a prezentat ideea „clasificării structurale”, care conținea ideea principală a analizei cluster - identificarea grupurilor compacte de obiecte.

În 1925, hidrobiologul sovietic P.V. Terentyev a dezvoltat așa-numita „metodă de corelare a galaxiilor”, 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 grupului”. La începutul anilor '50, publicațiile lui R. Lewis, E. Fix și J. Hodges au apărut pe algoritmi ierarhici pentru analiza cluster. Un impuls notabil dezvoltării lucrărilor privind analiza cluster a fost dat de munca lui R. Rosenblatt asupra unui dispozitiv 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 „Principii de taxonomie numerică”, 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 trebuie să asigure utilizarea diverșilor indicatori care caracterizează organismele studiate, să evalueze gradul de similitudine dintre aceste organisme și să asigure plasarea unor organisme similare. in acelasi grup. În acest caz, grupurile formate trebuie să fie suficient de „locale”, adică. asemănarea obiectelor (organismelor) în cadrul grupurilor trebuie să depășească asemănarea grupurilor între ele. Analiza ulterioară a grupurilor identificate, conform autorilor, poate determina dacă aceste grupuri corespund unor specii biologice diferite. Astfel, Sokal și Snit au presupus că identificarea structurii distribuției obiectelor în grupuri ajută la stabilirea procesului de formare a acestor structuri. Iar diferențele și asemănările dintre organisme ale diferitelor grupuri (grupuri) pot servi ca bază pentru înțelegerea procesului evolutiv care a avut loc ș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 - folosind metode ierarhice. Oamenii de știință autohtoni au avut, de asemenea, o contribuție semnificativă la dezvoltarea metodelor de analiză a clusterelor - E.M. Braverman, A.A. Dorofeyuk, I.B. Muchnik, L.A. Rastrigin, Yu.I. Zhuravlev, I.I. Eliseeva și alții, î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 au fost foarte populari. Aceștia sunt niște algoritmi cunoscuți precum FOREL, BIGFOR, KRAB, NTTP, DRET, TRF etc. Pe baza acestor pachete, a fost creat un pachet software specializat OTEKS. 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.

În diferite grade, metodele de analiză a clusterelor sunt disponibile în majoritatea celor mai cunoscute pachete statistice interne și externe: SIGAMD, DataScope, STADIA, SOMI, PNP-BIM, SORRA-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, folosind atât algoritmi noi, cât și putere 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 sale în diferite domenii ale cunoașterii se dublează la fiecare trei ani. Care sunt motivele pentru un interes atât de intens 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 cluster a datelor reale este practic imposibil de implementat. 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 adâncește 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 este că aprofundarea cunoștințelor de specialitate duce inevitabil la o creștere a numărului de variabile luate în considerare la analizarea anumitor obiecte și fenomene. Ca urmare, clasificarea subiectivă, care anterior se baza pe un număr destul de mic de caracteristici luate în considerare, se dovedește adesea a fi nesigură. Iar 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 CARACTERISTICA

Să introducem mai întâi concepte precum obiect și atribut. 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 alte metode. 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 populație eșantion. 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ă cu litera latină „n” sau „N”.

Atribut (sinonime - proprietate, variabilă, caracteristică; engleză - variabilă - variabilă.) - reprezintă o proprietate specifică a unui obiect. 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 (scale), 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 rangul sau, după cum se mai numesc, variabilele ordinale (scale). Astfel de caracteristici au proprietatea de a ordona aceste semnificații. Acestea includ etapele unei anumite boli, grupele de vârstă, scorurile de cunoștințe ale studenților, o scară de 12 puncte a magnitudinii cutremurului conform Richter etc.

2) Al doilea grup de caracteristici discrete nu are o astfel de ordonare și se numește caracteristici nominale (din cuvântul „nominal” - eșantion) sau caracteristici de clasificare. Un exemplu de astfel de semne ar putea 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 scalei de numire.

Conceptele de obiect și atribut sunt de obicei numite matrice „proprietate-obiect” sau „atribut-obiect”. Matricea va fi un tabel dreptunghiular format din valorile caracteristicilor care descriu proprietățile eșantionului de observații studiat. În acest context, o observație va fi înregistrată ca o linie separată constând din valorile caracteristicilor utilizate. O caracteristică separată într-o astfel de matrice de date va fi reprezentată de o coloană constând din valorile acestei caracteristici pentru toate obiectele din eșantion.

2. 2 DISTANȚA DINTRE OBIECTE (METRICE)

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 valoare d ij care satisface următoarele axiome:

1. d ij > 0 (distanță nenegativă)

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 (discernibilitatea obiectelor neidentice)

5. Dacă d ij = 0, atunci i = j (indiscernibilitatea obiectelor identice)

Este convenabil să se reprezinte măsura proximității (asemănării) obiectelor ca inversul distanței dintre obiecte. Numeroase publicații dedicate analizei cluster descriu mai mult de 50 de metode diferite pentru calcularea distanței dintre obiecte. Pe lângă termenul „distanță”, un alt termen este adesea găsit î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 al-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ă caracteristici cantitative, distanța d ij va fi egală cu lungimea ipotenuzei triunghiului dreptunghic, care leagă două puncte din sistemul 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 ponderare 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, atunci 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 egal cu 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 indistinguire a obiectelor identice - d ij = 0 pentru i = j. Aceasta înseamnă că distanța dintre obiectul nr. 1 și același obiect nr. 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 nr. 1 și nr. 2 este egală cu distanța dintre obiectele nr. 2 și nr. 1.

Expresia pentru distanța euclidiană amintește foarte mult de așa-numita distanță de putere generalizată Minkowski, în care se folosește o altă mărime în puteri în loc de două. În general, această valoare este indicată prin simbolul „p”.

Când p = 2 obținem distanța euclidiană obișnuită. Deci expresia pentru metrica Minkowski generalizată are forma:

Alegerea unei valori specifice a exponentului de putere „p” este făcută 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 valorilor absolute ale diferențelor dintre caracteristicile corespunzătoare ale obiectelor. Lăsând p să meargă la infinit, obținem metrica „dominanței” sau Sup-metrică:

care poate fi reprezentat şi sub forma 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ă și metode pentru calcularea distanței dintre obiecte care sunt fundamental diferite de metrica Minkowski. Cea mai importantă dintre ele 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 vectorii coloană ai valorilor 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 denotă matricea globală varianță-covarianță în cadrul grupului. Un simbol -1 de mai sus S înseamnă că este necesară inversarea matricei 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 discrepanțe dintre valorile caracteristicilor corespunzătoare pentru obiectele i-lea și j-lea luate în considerare.

2. 3 DENSITATEA ȘI LOCALITATEA CLUSTELOR

Scopul principal al analizei cluster este de a găsi grupuri de obiecte care sunt similare între ele într-un 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 distribuției punctelor, observațiilor în cadrul clusterului. Această proprietate ne permite să definim un cluster ca un cluster de puncte într-un spațiu multidimensional, relativ dens în comparație cu alte zone ale acestui spațiu, care fie nu conțin deloc puncte, fie conțin un număr mic de observații. Cu alte cuvinte, cât de compact este un cluster dat sau, dimpotrivă, 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 și densitatea „împachetarii” 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 clusterul dat este mai rar și, prin urmare, 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 mărimii clusterului este „raza” acestuia. Această proprietate reflectă cel mai pe deplin dimensiunea reală a clusterului dacă clusterul în cauză are o formă rotundă și este o hipersferă într-un spațiu 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 și separabilitatea acestuia. Caracterizează gradul de suprapunere și distanța reciprocă a clusterelor unul față de celălalt în spațiul multidimensional. De exemplu, luați în considerare distribuția celor 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 semne ale proprietăților reflectorizante ale diferitelor forme de eritrocite, studiate cu ajutorul microscopiei electronice.

Poza 1

Vedem că clusterul 1 are dimensiunea minimă, iar 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 suprafețe destul 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. Evident. , pentru o astfel de analiză vizuală este necesară proiectarea tuturor observațiilor eșantionului 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 obiecte originale de studiu, 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 unul sau altul algoritm într-un cluster. În acest caz, se pune întrebarea cum să înțelegem distanța dintre astfel de acumulări de puncte (clustere) și cum să o calculăm. În acest caz, există posibilități chiar mai diverse 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ă un anumit volum de spațiu multidimensional și constau din mai multe puncte. În analiza clusterelor, distanțele dintre clustere sunt utilizate pe scară largă, calculate conform principiului celui mai apropiat vecin, centru de greutate, cel mai îndepărtat vecin și mediane. Cele mai utilizate patru metode sunt legarea unică, legătura completă, legătura medie și metoda Ward. În metoda legăturii unice, un obiect va fi alăturat unui cluster deja existent dacă cel puțin unul dintre elementele clusterului are același nivel de similitudine cu obiectul îmbinat. Pentru metoda de legătură completă, un obiect este adăugat la un cluster numai dacă asemănarea dintre un candidat pentru includere și oricare dintre elementele clusterului nu este mai mică de un anumit prag. Există mai multe modificări ale metodei de legătură medie care reprezintă un compromis între legătura unică și cea completă. Ei calculează valoarea medie a asemănării unui candidat pentru includere cu toate obiectele grupului existent. Alăturarea se realizează atunci când valoarea medie de similaritate găsită atinge sau depășește un anumit prag. Cea mai des folosită este media aritmetică a asemănării dintre obiectele clusterului și candidatul pentru includerea în cluster.

Multe dintre metodele de grupare diferă unele de altele prin faptul că algoritmii lor calculează diferite funcționale de calitate a partiției la fiecare pas. Metoda populară Ward este concepută pentru a optimiza variația minimă a distanțelor intra-cluster. La primul pas, fiecare cluster este format dintr-un obiect, din cauza căruia dispersia intracluster a distanțelor este egală cu 0. Folosind această metodă, acele obiecte sunt combinate care dau o creștere minimă a dispersiei, drept urmare această metodă tinde să generează clustere hipersferice.

Încercările repetate de a clasifica metodele de analiză a clusterelor conduc la zeci sau chiar sute de clase diferite. O astfel de diversitate este generată de un număr mare de metode posibile pentru calcularea distanței dintre observațiile individuale, un număr la fel de mare de metode de calculare a distanței dintre clusterele individuale în procesul de grupare și estimări diverse ale optimității structurii clusterului final.

Cele mai răspândite în pachetele statistice populare sunt două grupuri de algoritmi de analiză a clusterelor: 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 utilizați mai des î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 de calcul puternice, implementarea analizei datelor cluster este foarte problematică.

Alegerea metricii este făcută chiar de cercetător. După calcularea matricei distanțelor, începe procesul aglomerări (din latinescul agglomero - adaug, acumulez), trecând secvenţial pas cu pas. La prima etapă a acestui proces, două observații inițiale (monoclustere), între care există distanța minimă, sunt combinate într-un singur cluster, format din două obiecte (observații). Astfel, în loc de fostele 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 doar din un singur obiect. La al doilea pas, sunt posibile diferite metode de combinare a clusterelor N-2 între ele. 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 apoi mai mult de două) obiecte;

· cum se calculează distanța până la astfel de clustere „multi-obiect” de la „mono-clustere” și între clustere „multi-obiect”.

Aceste întrebări determină în cele din urmă structura finală a clusterelor finale (structura clusterelor înseamnă compoziția clusterelor individuale și locația relativă a acestora în spațiul multidimensional). Diverse combinații de metrici și metode pentru calcularea coordonatelor și distanțelor reciproce ale clusterelor dau naștere la varietatea de metode de analiză a clusterelor. La a doua etapă, în funcție de metodele selectate pentru calcularea coordonatelor unui cluster format din mai multe obiecte și de metoda de calcul a distanțelor dintre clustere, este posibil fie să reuniți din nou două observații separate într-un grup nou, fie să uniți o nouă observație. la un cluster format din două obiecte. Pentru comoditate, majoritatea programelor pentru metode aglomerative-ierarhice pot oferi două grafice principale pentru vizualizare la finalizare. 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 pentru două variabile.

Programa1

Axa verticală a unui astfel de grafic reprezintă axa distanței dintre clustere, iar axa orizontală indică numărul de obiecte - cazuri utilizate în analiză. Din această dendrogramă reiese clar că obiectele nr. 1 și nr. 2 sunt mai întâi combinate într-un singur grup, deoarece distanța dintre ele este minimă și egală cu 1. Această fuziune este afișată pe grafic printr-o linie orizontală care leagă segmentele verticale care ies. 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. Apoi, în a doua etapă, la acest cluster se adaugă obiectul nr. 3, desemnat ca C_3, care include deja două obiecte. Următorul pas implică îmbinarea obiectelor nr. 4 și nr. 5, distanța dintre care este de 1,41. Și la ultimul pas, grupul de obiecte 1, 2 și 3 este îmbinat 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 egal cu 1,41.

Dendrograma de mai jos a fost obținută prin analiza unei matrice de date reale constând din 70 de probe chimice procesate, fiecare dintre acestea fiind caracterizată de 12 caracteristici.

Programul 2

Graficul arată că la ultimul pas, când ultimele două clustere s-au îmbinat, 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 în care numerele de observație, desemnate ca C_65, C_58 etc., sunt destul de clar vizibile. (de la stânga la dreapta): 65, 58, 59, 64, 63, 57, 60, 62, 56, 44, 94 etc.

Graficul 3 Secțiunea mărită a graficului nr. 2 de mai sus

Se poate observa că obiectul 44 este un monocluster care se unește la penultimul pas cu clusterul din dreapta și 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 modificărilor distanțelor dintre clustere la fiecare pas de îmbinare. Mai jos este un grafic similar pentru dendrograma de mai sus.

Programul 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”. 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 la ultimul pas.

Programul 5

Acum să o comparăm cu o altă diagramă obținută folosind metoda single link cu aceleași date. Spre deosebire de metoda de conectare completă, este clar că această metodă generează lanțuri lungi de obiecte atașate secvenţial unele de altele. Cu toate acestea, în toate cele trei cazuri putem spune că există două grupuri principale.

Programul 6

Să remarcăm, de asemenea, că în toate cele trei cazuri, obiectul nr. 44 se alătură ca un monocluster, deși la diferite etape ale procesului de grupare. Identificarea 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 gruparea din nou. Obținem următoarea dendrogramă:

Programul 7

Se poate observa că efectul de „lanț” a fost păstrat, la fel ca și împărțirea în două grupuri locale de observații.

3. 2 CARACTERISTICI ALE METODELOR ITERATIVE DE CLUSTERIZARE

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 necesar de clustere finale, care este de obicei notat cu „k”. Ca și în metodele de grupare ierarhică, utilizatorul poate selecta unul sau altul tip de metrică. Diferiți algoritmi ai metodei k-means diferă și prin modul în care selectează centrele inițiale ale clusterelor specificate. În unele versiuni ale metodei, utilizatorul însuși poate (sau trebuie) să specifice astfel de puncte inițiale, fie selectându-le din observații reale, fie specificând coordonatele acestor puncte pentru fiecare dintre variabile. În alte implementări ale acestei metode, un număr dat k de puncte inițiale este selectat aleatoriu, iar aceste puncte inițiale (semințele grupului) pot fi ulterior rafinate în mai multe etape. Există 4 etape principale ale unor astfel de metode:

· k observații sunt selectate sau atribuite pentru a 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 schimbările în coordonatele centrilor clusterului devin minime.

În unele variante ale acestei metode, utilizatorul poate specifica o valoare numerică a criteriului, 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ă se stabilească numărul maxim de iterații sau să se realizeze un anumit număr, de obicei destul de mic, cu care se compară modificarea distanței pentru toate centrele clusterului. Acest parametru se numește de obicei „convergență” deoarece reflectă convergența procesului de clustering iterativ. Mai jos prezentăm câteva dintre rezultatele obținute folosind metoda McKean k-means la datele anterioare. Numărul de clustere necesare a fost setat inițial la 3, apoi la 2. Prima parte conține rezultatele unei analize unidirecționale a varianței, în care numărul clusterului acționează ca un factor de grupare. Prima coloană conține o listă de 12 variabile, urmate de sumele pătratelor (SS) și gradele de libertate (df), apoi testul F Fisher și în ultima coloană nivelul de semnificație atins „p”.

Tabelul 2 Datele obținute prin metoda k-means McKean, aplicabile la 70 de probe studiate.

Variabile

După cum se poate observa din acest tabel, ipoteza nulă a egalității de medii în cele trei grupe este respinsă. Mai jos este un grafic al valorilor medii ale tuturor variabilelor pentru grupuri individuale. Aceste medii de grup ale variabilelor sunt prezentate mai jos sub formă de tabel.

Tabelul 3. Examinarea detaliată a datelor folosind exemplul a trei grupuri.

Variabil	Clusterul nr. 1	Clusterul nr. 2	Clusterul nr. 3

Programul 8

Analiza valorilor medii ale variabilelor pentru fiecare cluster ne permite să concluzionam că, conform atributului 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 atributului 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 mai apropiate. Pentru caracteristicile X3-X12, valorile medii în clusterul 1 sunt semnificativ mai mari decât în clusterele 2 și 3. Următorul tabel de analiză a varianței rezultatelor grupării în două clustere arată, de asemenea, necesitatea respingerii ipotezei nule a egalității de medii de grup pentru aproape toate cele 12 caracteristici, cu excepția variabilei X4, pentru care nivelul de semnificație atins a fost mai mare de 5%.

Tabelul 4. Tabelul analizei varianței rezultatelor grupării în două grupuri.

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 nr. 1	Clusterul nr. 2

Programul 9.

În cazul în care cercetătorul nu este în măsură să determine în prealabil cel mai probabil număr de clustere, el este obligat să repete calculele, precizând un număr diferit al acestora, similar cu ceea ce s-a făcut mai sus. Și apoi, comparând rezultatele obținute între ele, alegeți una dintre cele mai acceptabile opțiuni de grupare.

4 . CLUSTER DE CARACTERISTICI

Pe lângă gruparea observațiilor individuale, există și algoritmi pentru gruparea caracteristicilor. Una dintre primele astfel de metode este metoda de corelare a galaxiilor de P.V. Terentyev. Imaginile primitive ale unor astfel de galaxii 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 descoperit o corelație. Un număr de programe au proceduri separate pentru gruparea obiectelor și caracteristicilor. De exemplu, în pachetul SAS, procedura VARCLUS (de la VARiable - variabilă și CLUSter - cluster) este utilizată pentru a clusteriza caracteristicile, în timp ce analiza cluster a observațiilor este efectuată prin alte proceduri - FASTCLUS și CLUSTER. În ambele cazuri, dendrograma este construită folosind procedura TREE (arborele).

În alte pachete statistice, selecția elementelor pentru grupare - obiecte sau caracteristici - se face în același modul. Expresiile care includ valoarea anumitor coeficienți care reflectă puterea relației pentru o pereche de caracteristici sunt adesea folosite ca metrică atunci când sunt grupate caracteristici. În acest caz, este foarte convenabil ca caracteristicile cu o putere de conectare egală cu unu (dependență funcțională) să ia distanța dintre caracteristici egală cu zero. Într-adevăr, cu o conexiune funcțională, valoarea unei caracteristici poate fi utilizată pentru a calcula cu precizie valoarea unei alte caracteristici. Pe măsură ce puterea conexiunii dintre caracteristici scade, distanța crește în consecință. Mai jos este un grafic care arată dendrograma pentru combinarea celor 12 caracteristici care au fost utilizate mai sus la gruparea celor 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 trăsături: X1-X10 și X11-X12.Grupul de trăsături 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ă între perechi. În timp ce pentru perechea X11 și X12, distanța dintre clustere este mult mai mare și este de aproximativ 300 de unități. În cele din urmă, distanța foarte mare dintre clusterele stânga (X1-X10) și dreapta (X11-X12), egală cu aproximativ 1150 de unități, sugerează că relația dintre aceste două grupuri de caracteristici este destul de minimă.

5. STABILITATEA ȘI CALITATEA CLUSTERIZĂRII

În mod evident, ar fi absurd să punem întrebarea cât de absolută este cutare sau cutare clasificare obținută prin metodele de analiză a clusterelor. La schimbarea metodei de grupare, stabilitatea se manifestă prin faptul că două clustere sunt destul de clar vizibile în 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 diferiț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 testare a robusteței unei soluții cluster ar fi împărțirea aleatorie a eșantionului original în două părți aproximativ egale, gruparea ambelor părți și apoi compararea rezultatelor. O modalitate mai intensivă de muncă implică excluderea secvenţială a primului obiect mai întâi şi gruparea celorlalte (N - 1) obiecte. Apoi, efectuând succesiv această procedură, cu excepția celei de-a doua, a treia etc. obiecte, se analizează structura tuturor N clustere rezultate. Un alt algoritm de testare a robusteței implică propagarea multiplă, dublând eșantionul original de N obiecte, apoi combinând toate probele duplicate într-un singur eșantion mare (pseudo-populație) și extragerea aleatorie a unui nou eșantion de N obiecte din acesta. După aceasta, se realizează gruparea acestui eșantion, apoi se extrage o nouă probă aleatoare și se realizează din nou gruparea etc. Aceasta este, de asemenea, o cale destul de intensivă în muncă.

Nu există mai puține probleme atunci când se evaluează calitatea grupării. Există destul de mulți algoritmi pentru optimizarea soluțiilor de cluster. Primele lucrări care conțineau formulări ale unui criteriu pentru minimizarea varianței intra-cluster și ale unui algoritm (cum ar fi k-means) pentru găsirea unei soluții optime au apărut în anii 50. În 1963 Articolul lui J. Ward a subliniat și un algoritm similar de optimizare ierarhică. Nu există un criteriu universal pentru optimizarea unei soluții de cluster. Toate acestea fac dificil pentru cercetător să aleagă soluția optimă. Într-o astfel de situație, cel mai bun mod de a stabili 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ă.

Concluzia despre optimitatea clusterizării este susținută și de rezultatele pozitive ale testării momentelor predictive ale soluției obținute 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 există o linie plată a unui astfel de increment de la primul pas la câțiva pași penultim, cu o creștere verticală bruscă a acestui grafic în 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 prelucrare a datelor, deoarece de multe ori pentru acuratețea rezultatelor este necesară utilizarea de la zeci la sute de mostre. Acest tip de analiză ajută la clasificarea și procesarea rezultatelor. De asemenea, cred că nu este lipsit de importanță faptul că tehnologia computerizată este acceptabilă în această analiză, ceea ce face posibil ca procesul de prelucrare a rezultatelor să fie mai puțin intensiv în muncă și, prin urmare, ne permite să acordăm mai multă atenție selecției corecte a probelor pentru analiză.

Există subtilități și detalii în utilizarea analizei cluster care apar în cazuri specifice individuale și nu sunt vizibile imediat. De exemplu, rolul scalei caracteristicilor poate fi minim sau poate fi dominant într-un număr de 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 de realizare a analizei cluster 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 atunci când sunt aplicate la sisteme suficient de studiate, cât și atunci când studiem sisteme cu o structură necunoscută.

De asemenea, trebuie remarcat faptul că analiza clusterelor a devenit indispensabilă în studiile evolutive, 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) Ayvazyan S. A., Enyukov I. S., Meshalkin L. D. Despre structura și conținutul unui pachet software pentru analiza statistică aplicată // Algoritmic și software pentru analiza statistică aplicată. - M., 1980.

2) Ayvazyan S. A., Bezhaeva Z. I., Staroverov O. V. Clasificarea observațiilor multidimensionale - M.: Statistică, 1974.

3) Becker V. A., Lukatskaya M. L. Despre analiza structurii matricei coeficienților de cuplare // Probleme de modelare și prognoză economico-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. Botriologia Botriologiei // Clasificarea și clusterul.- M.: Mir, 1980.

7) Dubrovsky S.A. Analiză statistică multivariată aplicată - M.: Finanțe și Statistică, 1982.

8) Durand 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 neclare și aplicarea lor în recunoașterea modelelor și analiza clusterelor // Clasificare și cluster. - M.: Mir, 1980.

12) Kildishev G. S., Abolentsev Yu. I. Grupări multidimensionale. - M.: Statistică, 1978.

13) Raiskaya I. I., Gostilin N. I., Frenkel A. A. Despre o modalitate de verificare a validității 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ă multivariată 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.: Statistică, 1964.

Documente similare

Obiectivele segmentării pieței în activități de marketing. Esența analizei cluster, principalele etape ale implementării acesteia. Selectarea unei metode de măsurare a distanței sau a unei măsuri de similitudine. Metode de grupare ierarhică, non-ierarhică. Evaluarea fiabilității și validității.

raport, adaugat 11.02.2009

Principalii indicatori ai stării financiare a întreprinderii. Criza din întreprindere, cauzele, tipurile și consecințele acesteia. Metode și instrumente moderne de analiză a clusterelor, caracteristicile utilizării lor pentru evaluarea financiară și economică a unei întreprinderi.

teză, adăugată 10.09.2013

Efectuarea analizei cluster a întreprinderilor folosind programul Statgraphics Plus. Construirea unei ecuații de regresie liniară. Calculul coeficienților de elasticitate folosind modele de regresie. Aprecierea 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. Domenii de aplicare a 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 metodă modernă de prognoză. Model bazat pe ARIMA pentru descrierea seriilor de timp staționare și non-staționare atunci când se rezolvă probleme de clustering. Modele AR autoregresive și aplicații ale corelogramelor.

prezentare, adaugat 05.01.2015

Caracteristicile diferitelor tipuri de metrici. Metoda vecinilor cei mai apropiați ș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 curs, adăugată 03.08.2015

Caracteristicile industriei construcțiilor din regiunea Krasnodar. Prognoza dezvoltării construcției de locuințe. Metode și instrumente moderne pentru analiza clusterelor. Metode statistice multivariate pentru diagnosticarea stării economice a unei întreprinderi.

teză, adăugată 20.07.2015

Caracteristicile creditării ipotecare folosind exemplul regiunii Bryansk. Revizuirea metodelor matematice de luare a deciziilor: evaluări ale experților, comparații secvențiale și perechi, analiza ierarhiilor. Elaborarea unui program de găsire a creditului ipotecar optim.

lucrare curs, adaugat 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 tehnicilor de analiză a sistemelor, metodele sale informale. Caracteristicile metodelor de cercetare euristică și expertă și caracteristicile aplicării acestora.

lucrare curs, adaugat 20.05.2013

Dezvoltarea și cercetarea metodelor econometrice ținând cont de specificul datelor economice și în conformitate cu nevoile științei și practicii economice. Aplicarea metodelor și modelelor econometrice pentru analiza statistică a datelor economice.

Această carte este dedicată uneia dintre cele mai promițătoare abordări în acest sens ale analizei proceselor și fenomenelor multidimensionale - analiza clusterului.

Analiza cluster este o metodă de grupare a obiectelor multidimensionale, bazată pe reprezentarea rezultatelor observațiilor individuale prin puncte dintr-un spațiu geometric adecvat, urmată de identificarea grupurilor ca „clumps” ale acestor puncte. De fapt, „cluster” în engleză înseamnă „clump”, „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 termenului tradițional „ clasa”, iar a doua pare să indice 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.). Potențialul analizei cluster este evident 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.

Analiza cluster a apărut ca direcție științifică la mijlocul anilor ’60 și s-a dezvoltat rapid de atunci, fiind una dintre ramurile celei mai intense creșteri a științei statistice. Este suficient să spunem că numărul de monografii numai despre analiza clusterului, publicate până în prezent în diferite țări, este măsurat în sute (în timp ce, să zicem, pe o astfel de metodă „meritată” 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ției de grupare, una dintre cele mai importante nu numai în statistică, ci în general - atât în cunoaștere, 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ă acestei clasificări: conținutul ei este legat de fiecare dintre aceste trei domenii.

Scopul cărții este de a rezuma starea actuală a analizei cluster, de a analiza posibilitățile de utilizare a acesteia și sarcinile de dezvoltare ulterioară. Acest plan în sine nu poate decât să trezească respect: analiza imparțială și generalizarea necesită multă muncă, erudiție, curaj și sunt apreciate 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.)

Realizarea acestui obiectiv este asociată atât cu avantajele cărții, cât și cu dezavantajele acesteia. Avantajele includ:

· elaborarea metodologică a 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ă uneia dintre cele mai promițătoare abordări în acest sens ale analizei proceselor și fenomenelor multidimensionale - analiza clusterului.

Analiza cluster a apărut ca direcție științifică la mijlocul anilor ’60 și s-a dezvoltat rapid de atunci, 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 clusterului, elaborarea de scheme generale de utilizare a metodelor de analiză cluster, implementate în tabele destul de clare; 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 utilizării metodelor de analiză a clusterelor în aplicațiile socio-economice specifice 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

Universitatea: VZFEI

Anul și orașul: Moscova 2008

1. Introducere. Conceptul de metoda analizei cluster.

2. Descrierea metodologiei de aplicare a analizei cluster. Exemplu de testare de rezolvare a problemelor.

4. Lista referințelor utilizate

Introducere. Conceptul de metoda analizei cluster.

Analiza cluster este un set de metode care fac posibilă clasificarea observațiilor multidimensionale, fiecare dintre acestea fiind descrisă de un set de caracteristici (parametri) X1, X2,…, Xk.

Scopul analizei cluster este formarea de grupuri de obiecte similare, care sunt de obicei numite clustere (clasă, taxon, condensare).

Analiza clusterelor este unul dintre domeniile cercetării statistice. Ocupă un loc deosebit de important în acele ramuri ale științei care sunt asociate cu studiul fenomenelor și proceselor de masă. Necesitatea de a dezvolta metode de analiză a clusterelor și utilizarea lor este dictată de faptul că acestea ajută la construirea clasificărilor bazate științific și la identificarea conexiunilor interne între unitățile populației observate. În plus, metodele de analiză a clusterelor pot fi utilizate pentru comprimarea informațiilor, care este un factor important în contextul creșterii și complexității constante a fluxurilor de date statistice.

Metodele de analiză a clusterelor vă permit să rezolvați următoarele probleme:

Efectuarea clasificării obiectelor luând în considerare caracteristicile care reflectă esența și natura obiectelor. Rezolvarea unei astfel de probleme, de regulă, duce la aprofundarea cunoștințelor despre totalitatea obiectelor clasificate;

Verificarea ipotezelor făcute cu privire la prezența unei structuri în setul de obiecte studiat, i.e. căutarea unei structuri existente;

Construirea de noi clasificări pentru fenomene slab studiate, atunci când este necesar să se stabilească prezența legăturilor în cadrul unei populații și să se încerce introducerea structurii în ea (1, pp. 85-86).

2. Descrierea metodologiei de aplicare a analizei cluster. Exemplu de testare de rezolvare a problemelor.

Analiza cluster permite ca n obiecte caracterizate prin k caracteristici să fie împărțite în grupuri omogene (clustere). Omogenitatea obiectelor este determinată de distanța p(xi xj), unde xi = (xi1, …., xik) și xj= (xj1,…, xjk) sunt vectori formați din valorile k caracteristici ale i -lea și respectiv j-lea obiecte.

Pentru obiectele caracterizate prin caracteristici numerice, distanța este determinată de următoarea formulă:

p(xi , xj) = √ ∑(x1m-xjm) 2 (1)*

Obiectele sunt considerate omogene dacă p(xi xj)< p предельного.

O reprezentare grafică a uniunii poate fi obținută folosind un arbore de unire cluster - o dendrogramă. (2. Capitolul 39).

Caz de testare (exemplul 92).


Volumul vânzărilor

Să clasificăm aceste obiecte folosind principiul „cel mai apropiat vecin”. Să găsim distanțele dintre obiecte folosind formula (1)*. Să completăm tabelul.

Să explicăm cum este completat tabelul.

La intersecția rândului i și coloanei j, este indicată distanța p(xi xj) (rezultatul este rotunjit la două zecimale).

De exemplu, la intersecția rândului 1 și coloanei 3 este indicată distanța p(x1, x3) = √(1-6) 2 +(9-8) 2 ≈ 5,10, iar la intersecția rândului 3 și coloanei 5 distanța p(x3 , x5) = √ (6-12) 2 + (8-7) 2 ≈ 6,08. Deoarece p(xi, xj) = p(xj,xi), partea inferioară a tabelului nu trebuie completată.

Să aplicăm principiul „cel mai apropiat vecin”. Găsim în tabel cea mai mică dintre distanțe (dacă există mai multe astfel de distanțe, atunci alegeți oricare dintre ele). Acesta este p 1,2 ≈ p 4,5 = 2,24. Fie p min = p 4,5 = 2,24. Apoi putem combina obiectele 4 și 5 într-un singur grup, adică coloana combinată 4 și 5 va avea cel mai mic dintre numerele corespunzătoare din coloanele 4 și 5 din tabelul de distanțe inițial. Facem același lucru cu rândurile 4 și 5. Obținem un tabel nou.

Găsim în tabelul rezultat cea mai mică dintre distanțe (dacă sunt mai multe, atunci alegeți oricare dintre ele): p min = p 1,2 = 2,24. Apoi putem combina obiectele 1,2,3 într-un singur grup, adică coloana combinată 1,2,3 va conține cel mai mic dintre numărul corespunzător de coloane 1 și 2 și 3 din tabelul de distanțe anterior. Facem același lucru cu rândurile 1, 2 și 3. Obținem un nou tabel.

Avem două grupuri: (1,2,3) și (4,5).

3. Rezolvarea problemelor pentru test.

Problema 85.

Conditii: Cinci unități de producție se caracterizează prin două caracteristici: volumul vânzărilor și costul mediu anual al mijloacelor fixe.


Volumul vânzărilor
Costul mediu anual al mijloacelor fixe

Soluţie: Să găsim distanțele dintre obiecte folosind formula (1)* (rotunjind la două zecimale):

р 1,1 = √ (2-2) 2 + (2-2) 2 = 0

р 1,2 = √ (2-5) 2 + (7-9) 2 ≈ 3,61

р 1,3 = √ (2-7) 2 + (7-10) 2 ≈ 5,83

p 2.2 = √ (5-5) 2 + (9-9) 2 =0

р 2,3 = √ (5-7) 2 + (9-10) 2 ≈ 2,24

p 3,4 = √ (7-12) 2 + (10-8) 2 ≈5,39

p 3,5 = √ (7-13) 2 + (10-5) 2 ≈ 7,81

р 4,5 = √ (12-13) 2 + (8-5) 2 ≈ 3,16

Pe baza rezultatelor calculului, completați tabelul:

Să aplicăm principiul „cel mai apropiat vecin”. Pentru a face acest lucru, găsim cea mai mică dintre distanțe din tabel (dacă există mai multe astfel de distanțe, atunci selectați oricare dintre ele). Acesta este p 2,3=2,24. Fie p min = p 2,3 = 2,24, apoi putem îmbina obiectele coloanelor „2” și „3”, precum și șirurile de obiecte „2” și „3”. În noul tabel, introducem cele mai mici valori din tabelul original în grupurile combinate.

În noul tabel găsim cea mai mică dintre distanțe (dacă sunt mai multe, atunci selectați oricare dintre ele). Acesta este p 4,5 = 3,16. Fie p min = p 4,5 = 3,16, apoi putem îmbina obiectele coloanelor „4” și „5”, precum și șirurile de obiecte „4” și „5”. În noul tabel, introducem cele mai mici valori din tabelul original în grupurile combinate.

În noul tabel găsim cea mai mică dintre distanțe (dacă sunt mai multe, atunci selectați oricare dintre ele). Acesta este p 1, 2 și 3 = 3,61. Fie p min = p 1, 2 și 3 = 3,61, apoi putem îmbina obiectele coloană „1” și „2 și 3” și, de asemenea, putem îmbina rândurile. În noul tabel, introducem cele mai mici valori din tabelul original în grupurile combinate.

Obținem două grupuri: (1,2,3) și (4,5).

Dendrograma arată ordinea de selecție a elementelor și distanțele minime corespunzătoare p min.

Răspuns: Ca rezultat al analizei cluster folosind principiul „cel mai apropiat vecin”, s-au format 2 clustere de obiecte similare: (1,2,3) și (4,5).

Problema 211.

Conditii: Cinci unități de producție se caracterizează prin două caracteristici: volumul vânzărilor și costul mediu anual al mijloacelor fixe.


Volumul vânzărilor
Costul mediu anual al mijloacelor fixe

Clasificați aceste obiecte folosind principiul „cel mai apropiat vecin”.

Soluţie: Pentru a rezolva problema, prezentăm datele în tabelul original. Să determinăm distanțele dintre obiecte. Să clasificăm obiectele după principiul „cel mai apropiat vecin”. Prezentăm rezultatele sub forma unei dendrograme.


Volumul vânzărilor
Costul mediu anual al mijloacelor fixe

Folosind formula (1)* găsim distanțele dintre obiecte:

p 1,1 =0, p 1,2 =6, p 1,3 =8,60, p 1,4 =6,32, p 1,5 =6,71, p 2,2 =0, p 2,3 =7,07, p 2,4 =2, p 2,5 =3,32, p 3,3 = 0, p 3,4 =5,10, p 3,5 =4,12, p 4,4 =0, p 4,5 =1, p 5,5 =0.

Prezentăm rezultatele în tabel:

Cea mai mică valoare a distanțelor din tabel este p 4,5=1. Fie p min = p 4,5 = 1, apoi putem îmbina obiectele coloanelor „4” și „5”, precum și șirurile de obiecte „4” și „5”. În noul tabel, introducem cele mai mici valori din tabelul original în grupurile combinate.

Cea mai mică valoare a distanțelor din noul tabel este p 2, 4 și 5=2. Fie p min = p 2, 4 și 5=2, apoi putem îmbina obiectele coloanelor „4 și 5” și „3”, precum și rândurile obiectelor „4 și 5” și „3”. În noul tabel, introducem cele mai mici valori din tabel în grupurile combinate.

Cea mai mică valoare a distanțelor din noul tabel este p 3,4,5=2. Fie p min = p 3,4,5=2, apoi putem îmbina obiectele coloanelor „3,4,5” și „2” și, de asemenea, unim rândurile obiectelor „3,4,5” și „2”. În noul tabel, introducem cele mai mici valori din tabel în grupurile combinate.

sau conectați-vă la site.

Important! Toate testele trimise pentru descărcare gratuită sunt destinate să elaboreze un plan sau o bază pentru propriile lucrări științifice.

Prieteni! Aveți o oportunitate unică de a ajuta studenții la fel ca tine! Dacă site-ul nostru v-a ajutat să găsiți jobul de care aveți nevoie, atunci cu siguranță înțelegeți cum jobul pe care îl adăugați poate ușura munca altora.

Dacă munca de testare, în opinia dumneavoastră, este de proastă calitate sau ați văzut deja această lucrare, vă rugăm să ne anunțați.

ANALIZA CLUSTERULUI ÎN SARCINI DE PREVIZIONARE SOCIO-ECONOMICA

Introducere în analiza clusterelor.

Atunci când analizează și prognozează fenomene socio-economice, cercetătorul întâlnește destul de des 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 bazată pe un număr destul de mare de indicatori, se prognozează condițiile de piață pentru bunuri individuale, se studiază și se prognozează depresiunea economică și multe alte probleme.

Metodele de analiză multivariată reprezintă cel mai eficient instrument cantitativ pentru studierea proceselor socio-economice descrise de 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 relațiilor.

Uneori abordarea analizei cluster este denumită în literatură 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 descris de 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 utilizate într-o mare varietate de cazuri, chiar și în cazurile în care vorbim de grupare simplă, în care totul se rezumă la formarea de grupuri pe baza similitudinii cantitative.

Marele avantaj al analizei cluster este că vă permite să divizați obiectele nu în funcție de un parametru, ci în funcție de 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 permite să se ia în considerare o varietate de date inițiale de natură aproape arbitrară. Acest lucru este de mare importanță, de exemplu, pentru prognoza situației pieței, când indicatorii au o formă diversă, ceea ce face dificilă utilizarea abordărilor econometrice tradiționale.

Analiza cluster vă permite să luați în considerare o cantitate destul de mare de informații și să reduceți și să comprimați dramatic cantități mari de informații socio-economice, făcându-le compacte și vizuale.

Analiza grupurilor este importantă în legătură cu seturile de serii cronologice care caracterizează dezvoltarea economică (de exemplu, condițiile economice generale și ale mărfurilor). Aici puteți evidenția perioadele în care valorile indicatorilor corespunzători au fost destul de apropiate și, de asemenea, puteți determina grupuri de serii temporale a căror dinamică este cel mai asemănătoare.

Analiza cluster poate fi utilizată iterativ. În acest caz, cercetarea se efectuează până la obținerea rezultatelor necesare. Mai mult, fiecare ciclu de aici poate oferi informații care pot schimba foarte mult direcția și abordările pentru aplicarea ulterioară a analizei cluster. Acest proces poate fi reprezentat ca un sistem de feedback.

În sarcinile de prognoză socio-economică, combinarea analizei cluster cu alte metode cantitative (de exemplu, analiza regresiei) este foarte promițătoare.

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ție selectate. La reducerea matricei de date originale la o formă mai compactă, pot apărea anumite distorsiuni, iar caracteristicile individuale ale obiectelor individuale se pot pierde din cauza înlocuirii lor cu caracteristicile valorilor generalizate ale parametrilor clusterului. La clasificarea obiectelor, posibilitatea absenței oricăror valori de grup în setul luat în considerare este foarte des ignorată.

În analiza clusterului se consideră că:

a) caracteristicile selectate permit, în principiu, împărțirea dorită în clustere;

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, pe baza datelor conținute în mulțimea X, mulțimea de obiecte G în m (m este un întreg) clustere (subseturi) Q1, Q2, ..., Qm, astfel încât fiecare obiect Gj aparține unuia și numai unui subset al partiției și astfel încât 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, dintre care oricare este caracterizată prin PNB pe cap de locuitor (F1), numărul M de mașini la 1 mie 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 etc. Scopul este de a clasifica țările după nivelul de dezvoltare.

Soluția problemei analizei cluster sunt partițiile care îndeplinesc un anumit criteriu de optimitate. Acest criteriu poate fi un fel de funcțional care exprimă nivelurile de dezirabilitate ale diferitelor partiții și grupări, care se numește funcție obiectiv. De exemplu, suma din cadrul grupului a abaterilor pătrate poate fi luată ca funcție obiectiv:

unde xj reprezintă măsurătorile j-lea obiect.

Pentru a rezolva problema analizei cluster, este necesar să se definească conceptul de similaritate și eterogenitate.

Este clar că obiectele i-th și j-th ar cădea într-un grup atunci când distanța (depărtarea) 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, căderea î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(Хi, Хj) ³ 0, pentru toate Хi și Хj din Ep

b) d(Хi, Хj) = 0, dacă și numai dacă Хi = Хj

c) d(Хi, Хj) = d(Хj, Хi)

d) d(Xi, Xj) £ d(Xi, Xk) + d(Xk, Xj), unde Xj; Xi și Xk sunt oricare trei vectori din Ep.

Valoarea d(Хi, Хj) pentru Хi și Хj se numește distanța dintre Хi și Хj ș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 comandă, iar norma lp acoperă funcțiile de distanță 1, 2, 3,.

Fie reprezentate n dimensiuni X1, X2,..., Xn ca o matrice de date de dimensiunea p ´n:

Atunci distanța dintre perechile de vectori d(Хi, Хj) poate fi reprezentată ca o matrice simetrică a distanțelor:

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(Хi, Хj) = S(Хj, Хi)

Perechile de valori de măsurare a similitudinii pot fi combinate într-o matrice de similaritate:

Valoarea Sij se numește coeficient de similitudine.

1.3. Metode de analiză a clusterelor.

Astăzi există destul de multe metode de analiză a clusterelor. Să ne uităm la unele dintre ele (metodele prezentate mai jos sunt de obicei numite metode ale variației minime).

Fie X o matrice de observații: 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) a clusterului nu trebuie să depășească o anumită valoare prag h. Astfel, h definește diametrul maxim admisibil al subsetului care formează clusterul.

2) Metoda distanței locale maxime.

Fiecare obiect este tratat ca un singur grup de puncte. Obiectele sunt grupate după următoarea regulă: două grupuri sunt combinate dacă distanța maximă dintre punctele unui grup și punctele celuilalt este minimă. Procedura constă din n - 1 pași și rezultatul sunt partiții care coincid cu toate partițiile posibile din metoda anterioară pentru orice valoare de prag.

3) Metoda cuvântului.

Î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 grupului care conține acest obiect. La fiecare pas, două clustere sunt combinate care duc la o creștere minimă a funcției obiectiv, adică. suma de pătrate în cadrul grupului. Această metodă are ca scop combinarea clusterelor strâns localizate.

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) Clustering are loc pas cu pas la fiecare dintre n–1 pași, două clustere G și p sunt combinate, având o valoare minimă d2ij Dacă n1 este mult mai mare decât n2, atunci centrele de fuziune a celor două clustere sunt apropiate unul de celălalt, iar caracteristicile celui de-al doilea cluster sunt practic ignorate la combinarea clusterelor. Această metodă este uneori numită și metoda grupului ponderat.

1.4 Algoritm de clustering 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 într-un anumit sens sunt mai aproape unul de celălalt și le combinăm într-un singur grup. Noul set de clustere, constând deja din n-1 clustere, va fi:

(I1), (I2)…, (I i, I j),…, (I 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). Folosind Ι i și Ι j formăm un nou grup

(I i, I j). Să construim 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

Rândurile (n-2) pentru ultima matrice sunt preluate din cea anterioară, iar primul rând este recalculat. Calculele pot fi minimizate dacă putem exprima di j2k,k = 1, 2,…, n; (k ¹ i ¹ j) prin elementele matricei originale.

Inițial, distanța este determinată doar între clustere cu un singur element, dar este necesar să se determine distanța dintre clusterele care conțin mai mult de un element. Acest lucru se poate face în diverse moduri, iar în funcție de metoda aleasă, obținem algoritmi de analiză a clusterelor cu proprietăți diferite. Puteți, de exemplu, să puneți distanța dintre clusterul 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 putem 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 algoritmului ierarhic aglomerativ. Pașii următori sunt similari.

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 este determinată de un algoritm specific. De exemplu, când w = 1 obținem așa-numitul algoritm de „conexiune medie”, pentru care formula de recalculare a distanțelor ia forma:

di+j,k =

În 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 astfel de perechi de elemente în care un element al perechii aparține unui grup, celălalt altuia.

Sensul vizual al parametrului w devine clar dacă punem w®¥. Formula pentru recalcularea distanțelor ia forma:

di+j,k = min (di,k djk)

Acesta va fi așa-numitul algoritm „cel mai apropiat vecin”, care vă permite să identificați grupuri de orice formă complexă, cu condiția ca diferitele 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ă distanțele inițiale (diferențele) dintre elementele grupate sunt date. În unele probleme, acest lucru este într-adevăr adevărat. Cu toate acestea, sunt specificate doar obiectele și caracteristicile lor, iar pe baza acestor date este construită o matrice de distanțe. Î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 caracteristicii h-a pentru obiectele i-a și j-a, 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ă folosind formula:

care se numesc: distanță „Hamming”, „Manhattan” sau „bloc”.

O măsură naturală a asemănării caracteristicilor obiectelor în multe sarcini este coeficientul de corelație dintre ele

unde mi, mj, di, dj sunt abaterile medii și standard pentru caracteristicile i și, respectiv, j. O măsură a diferenței dintre caracteristici poate fi valoarea 1 - r. Î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.

O problemă foarte importantă este problema alegerii numărului necesar de clustere. Uneori puteți alege m număr de clustere a priori. Cu toate acestea, în cazul general, acest număr este determinat în procesul de împărțire a setului în grupuri.

Au fost efectuate cercetări de către Fortier și Solomon și s-a stabilit că numărul de clustere trebuie adoptat 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 partiții admisibile din mulțimea tuturor celor posibile. Cu cât este mai mare proporția b de partiții admisibile, cu atât este mai mare împrăștierea totală. Fortier și Solomon au dezvoltat un tabel care poate fi folosit pentru a găsi numărul de împărțiri 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 ponderea celor mai bune partiții în numărul total de partiții) În plus, măsura eterogenității nu este măsura dispersie, ci măsura apartenenței introdusă de Holzenger și Harman. Tabelul valorilor S(a,b) este prezentat mai jos.

Tabel de valori 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 o modificare a funcției corespunzătoare. De exemplu, suma abaterilor pătrate:

Procesul de grupare trebuie 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 determina cel mai bun număr de clustere se rezumă la identificarea salturilor determinate de tranziția de fază de la o stare a obiectelor puternic legată la o stare slab legată.

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ă. O dendogramă poate fi definită ca o reprezentare grafică a rezultatelor unui proces de grupare secvenţială, care se realizează în termenii unei matrice de distanţe. Folosind o dendogramă, puteți reprezenta grafic sau geometric o procedură de clustering, cu condiția ca această procedură să opereze numai pe elemente ale matricei de distanță sau similaritate.

Există multe moduri de a construi dendograme. În dendogramă, obiectele sunt situate vertical în stânga, rezultatele grupării sunt situate în dreapta. Valorile distanței sau similarității corespunzătoare structurii noilor clustere sunt reprezentate de-a lungul unei linii orizontale deasupra dendogramelor.

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 un nivel de proximitate de 0,9. Obiectele D și E sunt combinate la nivelul 0,8. Acum avem 4 clustere:

Tipul dendogramei depinde de alegerea măsurii de similitudine sau de distanța dintre un obiect și un cluster și de metoda de grupare. Cel mai important punct este alegerea măsurii de similitudine sau a distanței dintre obiect și cluster.

Numărul de algoritmi de analiză a clusterelor 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 prin combinarea secvențială a elementelor 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, rezultând formarea unei secvențe de grupuri de scindare.

Algoritmii de analiză a clusterelor au astăzi o implementare software bună, ceea ce permite rezolvarea problemelor de cea mai mare dimensiune.

1.7 Date

Analiza cluster poate fi aplicată datelor de interval, frecvențe și date binare. Este important ca variabilele să varieze pe scale comparabile.

Eterogenitatea unităților de măsură și imposibilitatea rezultată de a exprima în mod valid valorile diferiților indicatori pe aceeași scară duce la faptul că distanțele dintre punctele care reflectă poziția obiectelor în spațiul proprietăților lor se dovedesc a depinde de o scară aleasă în mod arbitrar. Pentru a elimina eterogenitatea în măsurarea datelor sursă, toate valorile acestora sunt pre-normalizate, adică sunt exprimate prin raportul dintre aceste valori la o anumită valoare care reflectă anumite proprietăți ale unui indicator dat. 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 separă o observație dată 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 pentru o observație oferă informații mai specifice despre locația acesteia.

Rețineți că metodele de standardizare înseamnă recunoașterea tuturor caracteristicilor ca echivalente din punctul de vedere al determinării asemănării obiectelor luate în considerare. S-a remarcat deja că în ceea ce privește economia, recunoașterea echivalenței diferiților indicatori nu pare întotdeauna justificată. Ar fi de dorit, împreună cu standardizarea, să se acorde fiecărui indicator o pondere care să reflecte semnificația sa în stabilirea asemănărilor și diferențelor obiectelor.

În această situație, este necesar să se recurgă la o metodă de determinare a ponderilor indicatorilor individuali - un sondaj de experți. De exemplu, atunci când s-a rezolvat problema clasificării țărilor după nivelul de dezvoltare economică, rezultatele unui sondaj a 40 de experți de top din Moscova privind problemele țărilor dezvoltate au fost utilizate 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 de prevalență a forței de muncă angajate – 6 puncte;

indicatori care caracterizează elementul uman al forțelor productive – 6 puncte;

indicatori de dezvoltare a forțelor productive materiale – 8 puncte;

indicatorul cheltuielilor guvernamentale – 4 puncte;

indicatori „militar-economici” – 3 puncte;

indicatori socio-demografici – 4 puncte.

Evaluările experților au fost relativ stabile.

Evaluările experților oferă o anumită bază pentru a determina importanța indicatorilor incluși într-un anumit grup de indicatori. Înmulțirea valorilor normalizate ale indicatorilor cu coeficientul corespunzător punctajului mediu de evaluare permite calcularea distanțelor dintre puncte care reflectă poziția țărilor în spațiul multidimensional, ținând cont de ponderea inegală a caracteristicilor acestora.

Destul de des, atunci când se rezolvă astfel de probleme, se utilizează nu unul, ci două calcule: primul, în care toate caracteristicile sunt considerate echivalente, al doilea, în care li se acordă ponderi diferite în conformitate cu valorile medii ale evaluărilor experților.

1.8. Aplicarea analizei cluster.

Să ne uităm la câteva aplicații ale analizei cluster.

Împărțirea țărilor în grupuri după nivelul de dezvoltare.

65 de țări au fost studiate după 31 de indicatori (venitul național pe cap de locuitor, procentul populației ocupate în industrie, economiile pe cap de locuitor, procentul populației ocupate în agricultură, speranța medie de viață, numărul de mașini la 1 mie de locuitori, numărul forțelor armate). la 1 milion de locuitori, ponderea PIB-ului industriei în%, ponderea PIB-ului agriculturii în% etc.)

Fiecare țară acționează în acest considerent ca un obiect caracterizat prin anumite valori a 31 de indicatori. În consecință, ele pot fi reprezentate ca puncte în spațiul cu 31 de dimensiuni. Un astfel de spațiu se numește de obicei spațiul proprietăților obiectelor studiate. Compararea distanței dintre aceste puncte va reflecta gradul de proximitate al țărilor în cauză, 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 al unei astfel de analize este identificarea unei perechi de economii naționale luate î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 discuția următoare, ambele țări sunt considerate un singur grup, un singur grup. În consecință, matricea originală este transformată astfel încât elementele sale să devină 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. Din matricea de similitudine inițială se elimină rânduri și coloane corespunzătoare distanțelor de la perechea de țări incluse în fuziune la toate celelalte, dar se adaugă un rând și o coloană care conține distanța dintre clusterul obținut în timpul fuziunii ș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 considerat ca un întreg cu caracteristici aproximativ egale cu media caracteristicilor țărilor incluse în acesta.

Al doilea pas al analizei este să luăm în considerare matricea astfel transformată cu 64 de rânduri și coloane. Din nou, se identifică o pereche de economii, distanța dintre care este cea mai puțin semnificativă și ele, la fel ca în primul caz, sunt reunite. În acest caz, distanța cea mai mică poate fi între o pereche de țări, sau între orice țară și asociația 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 obiectele rămase; atunci perechea de obiecte cele mai apropiate este identificată în matricea modificată. Analiza continuă până când matricea este complet epuizată (adică până când toate țările sunt combinate într-un singur întreg). Rezultatele generalizate ale analizei matriceale pot fi prezentate 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 complexă decât diagrama în care apar doar cinci economii naţionale. Acest arbore, în funcție de numărul de obiecte comparate, include 65 de niveluri. Primul nivel (inferior) conține puncte corespunzătoare fiecărei țări separat. Conectarea acestor două puncte la al doilea nivel arată o pereche de țări care sunt cele mai apropiate din punct de vedere al tipului general de economie națională. La al treilea nivel, se notează următorul raport similar de țări pe perechi (după cum sa menționat deja, acest raport poate conține fie o nouă pereche de țări, fie o nouă țară și o pereche deja identificată de țări similare). Ș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 (exclusiv SUA)

Introducerea de noi indicatori dincolo de cei 31 de indicatori utilizați aici, sau înlocuirea acestora cu alții, duce în mod firesc la modificări ale rezultatelor clasificării țărilor.

2. Împărțirea țărilor după criteriul asemănării culturii.

După cum știți, marketingul trebuie să țină cont de cultura țărilor (obiceiuri, tradiții etc.).

Prin grupare s-au obținut următoarele grupuri de țări:

Arabic;

Orientul Mijlociu;

Scandinav;

vorbitor de limba germană;

Vorbitor de engleza;

romanic european;

America Latină;

Orientul Îndepărtat.

3. Elaborarea unei prognoze a condițiilor pieței zincului.

Analiza cluster joacă un rol important în etapa de reducere a modelului economic și matematic al pieței de mărfuri, ajutând 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 criterii adecvate, facilitând astfel selecția celor mai reprezentativi indicatori.

Analiza cluster este utilizată pe scară largă pentru a modela condițiile pieței. În practică, majoritatea problemelor de prognoză se bazează pe utilizarea analizei cluster.

De exemplu, sarcina de a dezvolta o prognoză pentru piața 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

Rezervele de zinc ale producătorilor:

X14 - în lume

X16 - Europa

X17 - alte țări

Rezervele de zinc ale consumatorilor:

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 de zinc și concentrate (mii de tone)

X24 - din Canada

X25 - din Australia

Import de zinc (mii de tone)

X26 - în SUA

X27 - în Anglia

X28 - în Germania

Exporturi 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. Analiza relațiilor a fost efectuată pe baza unei matrice de coeficienți de corelație perechi. Aici a fost acceptată ipoteza despre distribuția normală a indicatorilor de piață analizați. Este clar că rij nu sunt singurul indicator posibil al relației dintre indicatorii utilizați. Necesitatea de a utiliza analiza cluster în această sarcină 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 asupra tuturor variabilelor;

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ă ca numărul de valori observate să depășească numărul de variabile de cel puțin 6-8 ori;

d) dorinta de a folosi in model variabile independente statistic etc.

Este foarte dificil să se realizeze o astfel de analiză direct pe o matrice relativ greoaie de coeficienți de corelație. Folosind analiza clusterului, î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 diferitelor grupuri sunt caracterizați de o corelație slabă.

Pentru a rezolva această problemă, a fost utilizat unul dintre algoritmii de analiză a clusterelor ierarhice aglomerative. La fiecare pas, numărul de clustere este redus cu unul datorită combinației optime, într-un anumit sens, a două grupuri. Criteriul de îmbinare este modificarea funcției corespunzătoare. Ca o astfel de funcție, am folosit valorile sumelor abaterilor pătrate calculate folosind 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, fiecare incluzând câte un element. Procesul de grupare începe cu combinarea unei astfel de perechi de clustere, ceea ce duce la o creștere minimă a sumei abaterilor pătrate. Acest lucru necesită estimarea sumei pătratelor valorilor deviației pentru fiecare dintre combinațiile posibile de cluster. În etapa următoare, valorile sumelor abaterilor pătrate sunt luate în considerare pentru clustere etc. 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 percepe un salt (unul 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 dat, salturile au avut loc atunci când numărul de grupuri era 7 și 5. Numărul de grupuri nu trebuie redus și mai mult, deoarece aceasta duce la o scădere a calității modelului. După obținerea clusterelor, se selectează variabilele care sunt cele mai importante din punct de vedere economic și care sunt cel mai strâns legate de criteriul selectat al situației pieței - în acest caz, cu cotațiile de zinc la London Metal Exchange. Această abordare ne permite să păstrăm o parte semnificativă a informațiilor conținute în setul original de indicatori inițiali de piață.

Termenul „analiza cluster” a fost folosit pentru prima dată de psihologul american Robert Tryon în lucrarea sa cu același nume încă din 1930. În ciuda acestui fapt, termenii „cluster” și „cluster analysis” sunt percepuți de vorbitorii nativi ca noi, după cum a remarcat Alexander Khrolenko, care a efectuat o analiză de corpus a utilizării lexemului „cluster”: „majoritatea autorilor care folosesc acest termen acordă atenție. la noutatea sa” (Khrolenko , 2016, p. 106)

Analiza cluster include mulți algoritmi de clasificare diferiți, al căror scop este de a organiza informațiile în clustere. Este important să ne amintim că analiza cluster nu este un algoritm specific în sine, ci o problemă care trebuie rezolvată. În lucrarea sa „Scarcity of Linear Hierarchy”, Mark Ereshefsky notează că analiza cluster este unul dintre cele trei tipuri de clasificare a obiectelor din lumea înconjurătoare, împreună cu esențialismul și clasificarea istorică.

În lingvistică, principiul descriere a clusterului presupune, pe lângă analiza unităților incluse în acest cluster, și analiza relațiilor din cadrul acestora. Acestea pot fi conexiuni la diferite niveluri: de la logice (paradigmatice și sintagmatice, de exemplu) până la formarea cuvintelor și conexiuni fonetice.

F. Brown identifică următorii pași ai analizei cluster (Brown):

1. Selectarea unei măsuri și producerea măsurătorilor, criteriilor sau entităților necesare pentru a fi clasificate
2. Stabilirea măsurii de similitudine
3. Formularea regulilor pentru a determina ordinea formării clusterelor
4. Aplicarea regulilor pentru a forma clustere

Trebuie remarcat faptul că al treilea punct ridică întrebări, deoarece trăsătura distinctivă a grupării ca metodă de clasificare este absența claselor specificate. Gruparea documentelor este o sarcină de regăsire a informațiilor. Spre deosebire de categorizarea textului, aceasta nu implică categorii predefinite sau un set de antrenament. Clusterele și relațiile dintre ele sunt „extrase automat din documente, iar documentele sunt atribuite succesiv acestor clustere” (Golub, pp. 52-53) Mark Ereshefsky introduce analiza clusterului ca metodă de clasificare. El crede că „toate formele de analiză a clusterelor se bazează pe două ipoteze: membrii unui grup taxonomic trebuie să aibă un grup de trăsături în comun, iar acele trăsături nu pot apărea în toate sau doar într-un singur membru al acelui grup”. (Ereshefsky, p. 15)

În lucrarea sa „Cluster abordare în analiza lingvistică” (Nurgalieva, 2013) N.Kh. Nurgalieva identifică patru sarcini principale ale analizei cluster:

1. Elaborarea unei tipologii sau clasificări
2. Explorarea schemelor conceptuale utile pentru gruparea obiectelor
3. Prezentarea ipotezelor pe baza datelor studiate
4. Testarea ipotezelor sau studiilor pentru a determina dacă tipurile (grupurile) identificate într-un fel sau altul sunt efectiv prezente în datele disponibile

Toate metodele de analiză a clusterului pot fi împărțite în analiză cluster „hard”, clară, atunci când fiecare obiect fie aparține unui cluster sau nu, și în analiză cluster „soft”, neclară, când fiecare obiect aparține unui grup cu un anumit grad de probabilitate.

Metodele de analiză a clusterelor sunt, de asemenea, împărțite în ierarhice și non-ierarhice. Metodele ierarhice presupun prezența unor grupuri imbricate, spre deosebire de metodele neierarhice. Nurgalieva notează că metoda ierarhică „pare a fi cea mai potrivită pentru rezolvarea problemelor lingvistice” (Nurgalieva, p. 1), deoarece vă permite să vedeți și să analizați structura fenomenului studiat.

Portal pentru școlari. Auto-pregătire

Trimiteți-vă munca bună în baza de cunoștințe este simplu. Utilizați formularul de mai jos

Documente similare

ARTICOLE SIMILARE