Literatura ng pagsusuri ng cluster. Ministri ng Edukasyon at Agham ng Russian Federation

Ipadala ang iyong mabuting gawa sa base ng kaalaman ay simple. Gamitin ang form sa ibaba

Ang mga mag-aaral, nagtapos na mga estudyante, mga batang siyentipiko na gumagamit ng base ng kaalaman sa kanilang pag-aaral at trabaho ay lubos na magpapasalamat sa iyo.

Panimula

1.History ng "cluster analysis"

2. Terminolohiya

2.1 Bagay at tanda

2.2 Distansya sa pagitan ng mga bagay (sukatan)

2.3 Densidad at lokalidad ng mga kumpol

2.4 Distansya sa pagitan ng mga kumpol

3. Mga pamamaraan ng pagpapangkat

3.1 Mga tampok ng hierarchical agglomerative na pamamaraan

3.2 Mga tampok ng umuulit na pamamaraan ng clustering

4. Feature clustering

5. Katatagan at kalidad ng clustering

Bibliograpiya

PANIMULA

"Ang pagsusuri ng cluster ay isang hanay ng mga pamamaraan sa matematika na idinisenyo upang bumuo ng medyo "malayuan" mula sa bawat isa na grupo ng mga "malapit" na bagay ayon sa impormasyon tungkol sa mga distansya o koneksyon (mga sukat ng kalapitan) sa pagitan nila. Ito ay katulad ng kahulugan sa mga termino: awtomatiko classification, taxonomy, pattern recognition nang walang guro." Ang kahulugan ng cluster analysis ay ibinigay sa pinakabagong edisyon ng Statistical Dictionary. Sa katunayan, ang "cluster analysis" ay isang pangkalahatang pangalan para sa isang medyo malaking hanay ng mga algorithm na ginagamit upang lumikha ng isang pag-uuri. Gumagamit din ang ilang publikasyon ng mga kasingkahulugan para sa pagsusuri ng kumpol bilang pag-uuri at paghahati. Ang pagsusuri ng cluster ay malawakang ginagamit sa agham bilang isang paraan ng pagsusuri sa typological. Sa anumang aktibidad na pang-agham, ang pag-uuri ay isa sa mga pangunahing sangkap, kung wala ito imposibleng bumuo at subukan ang mga siyentipikong hypotheses at teorya. Kaya, sa aking trabaho, itinuturing kong kinakailangang isaalang-alang ang mga isyu ng pagtatasa ng kumpol (ang batayan ng pagsusuri ng kumpol), gayundin ang pagsasaalang-alang sa terminolohiya nito at magbigay ng ilang halimbawa ng paggamit ng pamamaraang ito sa pagpoproseso ng data bilang aking pangunahing layunin.

1. KASAYSAYAN NG "CLUSTER ANALYSIS"

Ipinapakita ng pagsusuri sa mga publikasyong lokal at dayuhan na ginagamit ang pagsusuri ng kumpol sa iba't ibang larangang siyentipiko: kimika, biyolohiya, medisina, arkeolohiya, kasaysayan, heograpiya, ekonomiya, pilosopiya, atbp. Ang aklat ni VV Nalimov na "Probabilistic Model of Language" ay naglalarawan sa paggamit ng cluster analysis sa pag-aaral ng 70 analytical sample. Karamihan sa mga literatura sa pagsusuri ng kumpol ay lumitaw sa huling tatlong dekada, bagaman ang mga unang gawa na nagbanggit ng mga pamamaraan ng kumpol ay lumitaw nang matagal na ang nakalipas. Ang antropologo ng Poland na si K. Chekanowski ay naglagay ng ideya ng "pag-uuri ng istruktura", na naglalaman ng pangunahing ideya ng pagsusuri ng kumpol - ang paglalaan ng mga compact na grupo ng mga bagay.

Noong 1925, ang Soviet hydrobiologist na si P.V. Binuo ni Terentyev ang tinatawag na "paraan ng correlation pleiades", na nilayon para sa pagpapangkat ng mga nauugnay na tampok. Ang pamamaraang ito ay nagbigay ng lakas sa pagbuo ng mga pamamaraan ng pagpapangkat gamit ang mga graph. Ang terminong "cluster analysis" ay unang iminungkahi ng Trion. Ang salitang "cluster" ay isinalin mula sa Ingles bilang "bunch, brush, bunch, group". Para sa kadahilanang ito, ang ganitong uri ng pagsusuri ay orihinal na tinatawag na "cluster analysis". Noong unang bahagi ng 1950s, ang mga publikasyon nina R. Lewis, E. Fix at J. Hodges ay lumitaw sa hierarchical cluster analysis algorithm. Ang isang kapansin-pansing impetus sa pag-unlad ng trabaho sa pagtatasa ng kumpol ay ibinigay ng gawain ni R. Rosenblatt sa aparato ng pagkilala (perceptron), na naglatag ng pundasyon para sa pagbuo ng teorya ng "pagkilala sa pattern na walang guro."

Ang impetus para sa pagbuo ng mga pamamaraan ng clustering ay ang aklat na "Principles of Numerical Taxonomy", na inilathala noong 1963. dalawang biologist - sina Robert Sokal at Peter Sneath. Ang mga may-akda ng aklat na ito ay nagpatuloy mula sa katotohanan na upang lumikha ng epektibong biological na pag-uuri, ang pamamaraan ng clustering ay dapat tiyakin ang paggamit ng iba't ibang mga tagapagpahiwatig na nagpapakilala sa mga organismo na pinag-aaralan, tasahin ang antas ng pagkakapareho sa pagitan ng mga organismo na ito, at tiyakin ang paglalagay ng mga katulad na organismo. sa parehong grupo. Sa kasong ito, ang mga nabuong grupo ay dapat na sapat na "lokal", i.e. ang pagkakatulad ng mga bagay (organismo) sa loob ng mga grupo ay dapat na lumampas sa pagkakatulad ng mga grupo sa kanilang mga sarili. Ang kasunod na pagsusuri ng mga natukoy na grupo, sa opinyon ng mga may-akda, ay maaaring linawin kung ang mga pangkat na ito ay tumutugma sa iba't ibang biological species. Kaya, ipinalagay ni Sokal at Sneath na ang pagbubunyag ng istraktura ng pamamahagi ng mga bagay sa mga grupo ay nakakatulong upang maitaguyod ang proseso ng pagbuo ng mga istrukturang ito. At ang pagkakaiba at pagkakatulad ng mga organismo ng iba't ibang mga kumpol (grupo) ay maaaring magsilbing batayan para sa pag-unawa sa patuloy na proseso ng ebolusyon at pagpapaliwanag ng mekanismo nito.

Sa parehong mga taon, maraming mga algorithm ang iminungkahi ng mga may-akda tulad ng J. McKean, G. Ball at D. Hall gamit ang mga pamamaraan ng k-means; G. Lance at W. Williams, N. Jardine at iba pa - sa mga hierarchical na pamamaraan. Ang isang makabuluhang kontribusyon sa pagbuo ng mga pamamaraan ng pagsusuri ng kumpol ay ginawa ng mga domestic scientist - E.M. Braverman, A.A. Dorofeyuk, I.B. Muchnik, L.A. Rastrigin, Yu.I. Sa partikular, noong 60-70s. Maraming mga algorithm na binuo ng mga mathematician ng Novosibirsk na si N.G. Zagoruiko, V.N. Elkina at G.S. Lbov ang naging sikat. Ito ang mga kilalang algorithm tulad ng FOREL, BIGFOR, KRAB, NTTP, DRET, TRF, atbp. Batay sa mga paketeng ito, nilikha ang isang espesyal na pakete ng software ng OTEX. Walang gaanong kagiliw-giliw na mga produkto ng software na PPSA at Class-Master ang nilikha ng mga mathematician ng Moscow S.A. Aivazyan, I.S. Enyukov at B.G. Mirkin.

Sa ilang lawak, ang mga pamamaraan ng pagsusuri ng kumpol ay magagamit sa karamihan ng mga pinakakilalang domestic at dayuhang pakete ng istatistika: SIGAMD, DataScope, STADIA, SOMI, PNP-BIM, COPRA-2, SITO, SAS, SPSS, STATISTICA, BMDP, STATGRAPHICS , GENSTAT, S -PLUS, atbp. Siyempre, 10 taon pagkatapos ng paglalathala ng pagsusuri na ito, napakaraming nagbago, lumitaw ang mga bagong bersyon ng maraming mga istatistikal na programa, at ganap na bagong mga programa ang lumitaw na gumagamit ng parehong mga bagong algorithm at lubos na nadagdagan ang kapangyarihan ng pag-compute. Gayunpaman, karamihan sa mga istatistikal na pakete ay gumagamit ng mga algorithm na iminungkahi at binuo noong 60-70s.

Ayon sa magaspang na pagtatantya ng mga eksperto, ang bilang ng mga publikasyon sa pagsusuri ng kumpol at mga aplikasyon nito sa iba't ibang larangan ng kaalaman ay dumodoble kada tatlong taon. Ano ang mga dahilan para sa gayong mabagyong interes sa ganitong uri ng pagsusuri? Sa layunin, mayroong tatlong pangunahing dahilan para sa hindi pangkaraniwang bagay na ito. Ito ang paglitaw ng makapangyarihang teknolohiya sa pag-compute, kung wala ang pagsusuri ng cluster ng totoong data ay halos hindi magagawa. Ang pangalawang dahilan ay ang modernong agham ay lalong nakabatay sa pag-uuri sa mga konstruksyon nito. Bukod dito, ang prosesong ito ay lalong lumalalim, dahil kasabay nito ay mayroong pagtaas ng espesyalisasyon ng kaalaman, na imposible nang walang sapat na layunin na pag-uuri.

Ang ikatlong dahilan - ang pagpapalalim ng espesyal na kaalaman ay hindi maaaring hindi humahantong sa isang pagtaas sa bilang ng mga variable na isinasaalang-alang sa pagsusuri ng ilang mga bagay at phenomena. Bilang isang resulta, ang subjective na pag-uuri, na dati ay umaasa sa isang medyo maliit na bilang ng mga tampok na isinasaalang-alang, ay madalas na lumalabas na hindi maaasahan. At ang layunin ng pag-uuri, na may patuloy na tumataas na hanay ng mga katangian ng bagay, ay nangangailangan ng paggamit ng mga kumplikadong clustering algorithm na maaari lamang ipatupad sa batayan ng mga modernong computer. Ang mga kadahilanang ito ang nagbunga ng "cluster boom". Gayunpaman, sa mga manggagamot at biologist, ang pagsusuri ng kumpol ay hindi pa naging isang medyo popular at karaniwang paraan ng pananaliksik.

2 TERMINOLOHIYA

2. 1 BAGAY AT ALAMAT

Ipakilala muna natin ang mga konsepto tulad ng object at sign. Bagay - mula sa Latin na objectum - paksa. Kaugnay ng kimika at biyolohiya, sa pamamagitan ng mga bagay ay tutukuyin natin ang mga tiyak na paksa ng pananaliksik na pinag-aaralan gamit ang pisikal, kemikal at iba pang pamamaraan. Ang mga naturang bagay ay maaaring, halimbawa, mga sample, halaman, hayop, atbp. Ang isang tiyak na hanay ng mga bagay na magagamit ng mananaliksik para sa pag-aaral ay tinatawag na isang sample, o isang sample set. Ang bilang ng mga bagay sa naturang populasyon ay karaniwang tinatawag na sample size. Karaniwan, ang laki ng sample ay tinutukoy ng Latin na titik na "n" o "N".

Sign (kasingkahulugan - ari-arian, variable, katangian; Ingles - variable - variable.) - ay isang partikular na katangian ng bagay. Maaaring ipahayag ang mga katangiang ito bilang mga numeric o non-numeric na halaga. Halimbawa, ang presyon ng dugo (systolic o diastolic) ay sinusukat sa millimeters ng mercury, timbang sa kilo, taas sa sentimetro, atbp. Ang mga naturang palatandaan ay dami. Sa kaibahan sa mga tuluy-tuloy na katangiang pang-numero (mga kaliskis), ang isang bilang ng mga tampok ay maaaring magkaroon ng mga discrete, hindi tuloy-tuloy na mga halaga. Sa turn, ang mga naturang discrete features ay karaniwang nahahati sa dalawang grupo.

1) Ang unang pangkat ay mga variable ng ranggo, o bilang tinatawag ding mga ordinal na variable (mga sukat). Ang ganitong mga palatandaan ay nailalarawan sa pamamagitan ng pag-aari ng pag-order ng mga halagang ito. Kabilang dito ang mga yugto ng isang partikular na sakit, mga pangkat ng edad, mga marka ng kaalaman ng mag-aaral, ang 12-point Richter earthquake magnitude scale, atbp.

2) Ang pangalawang pangkat ng mga discrete na tampok ay walang ganoong pagkakasunud-sunod at tinatawag na nominal (mula sa salitang "nominal" - sample) o mga tampok ng pag-uuri. Ang isang halimbawa ng naturang mga palatandaan ay maaaring ang kondisyon ng pasyente - "malusog" o "may sakit", ang kasarian ng pasyente, ang panahon ng pagmamasid - "bago ang paggamot" at "pagkatapos ng paggamot", atbp. Sa mga kasong ito, kaugalian na sabihin na ang mga naturang tampok ay nabibilang sa sukat ng mga pangalan.

Ang mga konsepto ng isang bagay at isang tampok ay karaniwang tinatawag na "Object-property" o "Object-feature" matrix. Ang matrix ay magiging isang hugis-parihaba na talahanayan na binubuo ng mga halaga ng mga tampok na naglalarawan sa mga katangian ng sample ng mga obserbasyon sa ilalim ng pag-aaral. Sa kontekstong ito, ang isang obserbasyon ay itatala bilang isang hiwalay na linya na binubuo ng mga halaga ng mga tampok na ginamit. Ang isang hiwalay na katangian sa naturang data matrix ay kakatawanin ng isang hanay na binubuo ng mga halaga ng katangiang ito para sa lahat ng mga bagay sa sample.

2. 2 DISTANCE SA PAGITAN NG MGA BAGAY (METRIC)

Ipakilala natin ang konsepto ng "distansya sa pagitan ng mga bagay". Ang konseptong ito ay isang mahalagang sukatan ng pagkakapareho ng mga bagay sa bawat isa. Ang distansya sa pagitan ng mga bagay sa espasyo ng tampok ay tulad ng isang halaga d ij na nakakatugon sa mga sumusunod na axiom:

1. d ij > 0 (hindi negatibiti ng distansya)

2. d ij = d ji (symmetry)

3. d ij + d jk > d ik (hindi pagkakapantay-pantay ng tatsulok)

4. Kung ang d ij ay hindi katumbas ng 0, kung gayon ang i ay hindi katumbas ng j (kakayahang makilala ng mga di-magkaparehong bagay)

5. Kung d ij = 0, i = j (indistinguishability ng magkatulad na mga bagay)

Ito ay maginhawa upang kumatawan sa sukatan ng kalapitan (pagkakatulad) ng mga bagay bilang kapalit ng distansya sa pagitan ng mga bagay. Maraming publication na nakatuon sa cluster analysis ang naglalarawan ng higit sa 50 iba't ibang paraan upang kalkulahin ang distansya sa pagitan ng mga bagay. Bilang karagdagan sa terminong "distansya", ang isa pang termino ay madalas na matatagpuan sa panitikan - "sukat", na nagpapahiwatig ng isang paraan para sa pagkalkula ng isang partikular na distansya. Ang pinaka-accessible para sa perception at pag-unawa sa kaso ng quantitative features ay ang tinatawag na "Euclidean distance" o "Euclidean metric". Ang formula para sa pagkalkula ng distansya na ito ay:

Ginagamit ng formula na ito ang sumusunod na notasyon:

· d ij - distansya sa pagitan ng i-th at j-th na mga bagay;

· x ik - numerical value ng k-th variable para sa i-th object;

· x jk - numerical value ng k-th variable para sa j-th object;

· v - ang bilang ng mga variable na naglalarawan ng mga bagay.

Kaya, para sa case v=2, kapag mayroon lamang tayong dalawang quantitative sign, ang distansya d ij ay magiging katumbas ng haba ng hypotenuse ng isang right triangle, na nag-uugnay sa dalawang puntos sa isang rectangular coordinate system. Ang dalawang puntong ito ay tumutugma sa i-th at j-th na obserbasyon ng sample. Kadalasan, sa halip na ang karaniwang distansyang Euclidean, ang parisukat na d 2 ij ang ginagamit. Bilang karagdagan, sa ilang mga kaso, ang isang "timbang" na distansya ng Euclidean ay ginagamit, sa pagkalkula kung aling mga koepisyent ng timbang ang ginagamit para sa mga indibidwal na termino. Upang ilarawan ang konsepto ng Euclidean metric, gumagamit kami ng simpleng halimbawa ng pagsasanay. Ang data matrix na ipinapakita sa talahanayan sa ibaba ay binubuo ng 5 obserbasyon at dalawang variable.

Talahanayan 1

Data matrix ng limang naobserbahang sample at dalawang variable.

Gamit ang Euclidean metric, kinakalkula namin ang matrix ng mga interobject na distansya, na binubuo ng mga halaga d ij - ang distansya sa pagitan ng i-th at j-th na mga bagay. Sa aming kaso, ang i at j ay ang bilang ng bagay, pagmamasid. Dahil ang laki ng sample ay 5, ang i at j, ayon sa pagkakabanggit, ay maaaring tumagal ng mga halaga mula 1 hanggang 5. Malinaw din na ang bilang ng lahat ng posibleng magkapares na distansya ay magiging 5*5=25. Sa katunayan, para sa unang bagay ay ang mga sumusunod na distansya: 1-1; 1-2; 1-3; 1-4; 1-5. Para sa object 2 magkakaroon din ng 5 posibleng distansya: 2-1; 2-2; 2-3; 2-4; 2-5 atbp. Gayunpaman, ang bilang ng iba't ibang mga distansya ay magiging mas mababa sa 25, dahil kinakailangang isaalang-alang ang pag-aari ng hindi pagkakakilanlan ng magkaparehong mga bagay - d ij = 0 para sa i = j. Nangangahulugan ito na ang distansya sa pagitan ng object #1 at ng parehong object #1 ay magiging zero. Ang parehong zero na distansya ay para sa lahat ng iba pang mga kaso i = j. Sa karagdagan, ito ay sumusunod mula sa symmetry property na d ij = d ji para sa anumang i at j. Yung. ang distansya sa pagitan ng mga bagay #1 at #2 ay katumbas ng distansya sa pagitan ng mga bagay #2 at #1.

Ang expression para sa Euclidean distance ay halos kapareho sa tinatawag na generalized Minkowski power distance, kung saan ibang value ang ginagamit sa halip na dalawa sa powers. Sa pangkalahatang kaso, ang halagang ito ay tinutukoy ng simbolo na "p".

Para sa p = 2 makuha namin ang karaniwang distansya ng Euclidean. Kaya ang expression para sa pangkalahatang sukatan ng Minkowski ay may anyo:

Ang pagpili ng isang tiyak na halaga ng exponent na "p" ay ginawa ng mananaliksik mismo.

Ang isang espesyal na kaso ng distansya ng Minkowski ay ang tinatawag na distansya ng Manhattan, o "distansya sa bloke ng lungsod", na tumutugma sa p=1:

Kaya, ang distansya ng Manhattan ay ang kabuuan ng mga module ng mga pagkakaiba ng kaukulang mga tampok ng mga bagay. Hinahayaan ang p ay may posibilidad na infinity, makukuha natin ang sukatan ng "dominance", o Sup-metric:

na maaari ding katawanin bilang d ij = max| x ik - x jk |.

Ang sukatan ng Minkowski ay talagang isang malaking pamilya ng mga sukatan, kabilang ang mga pinakasikat na sukatan. Gayunpaman, may mga pamamaraan para sa pagkalkula ng distansya sa pagitan ng mga bagay na sa panimula ay naiiba sa mga sukatan ng Minkowski. Ang pinakamahalaga sa mga ito ay ang tinatawag na distansya ng Mahalanobis, na may mga partikular na katangian. Expression para sa sukatang ito:

Dito sa pamamagitan ng X i At X j Ang mga column vector ng mga variable na halaga para sa i-th at j-th na mga bagay ay ipinahiwatig. Simbolo T sa pagpapahayag (X i - X j ) T nagsasaad ng tinatawag na vector transposition operation. Simbolo S ang karaniwang intra-group variance-covariance matrix ay ipinahiwatig. Isang simbolo -1 sa itaas S nangangahulugan na kailangan mong baligtarin ang matrix S . Hindi tulad ng Minkowski metric at Euclidean metric, ang Mahalanobis distance sa pamamagitan ng variance-covariance matrix S nauugnay sa mga ugnayan ng mga variable. Kapag ang mga ugnayan sa pagitan ng mga variable ay zero, ang distansya ng Mahalanobis ay katumbas ng parisukat ng distansya ng Euclidean.

Sa kaso ng paggamit ng dichotomous (may dalawang halaga lamang) na mga katangian ng husay, ang distansya ng Hamming ay malawakang ginagamit

katumbas ng bilang ng mga hindi pagkakatugma sa mga halaga ng kaukulang mga tampok para sa itinuturing na i-th at j-th na mga bagay.

2. 3 DISID AT LOKALIDAD NG MGA KLUSTER

Ang pangunahing layunin ng pagsusuri ng kumpol ay upang mahanap ang mga pangkat ng mga bagay na magkatulad sa isa't isa sa sample. Ipagpalagay natin na sa pamamagitan ng ilan sa mga posibleng pamamaraan ay nakuha natin ang mga naturang grupo - mga kumpol. Ang mga mahahalagang katangian ng mga kumpol ay dapat tandaan. Ang isa sa mga katangiang ito ay ang density ng pamamahagi ng mga puntos, mga obserbasyon sa loob ng isang kumpol. Binibigyang-daan kami ng property na ito na tukuyin ang isang cluster bilang isang cluster ng mga punto sa isang multidimensional na espasyo na medyo siksik kumpara sa iba pang mga rehiyon ng espasyong ito na alinman ay hindi naglalaman ng mga puntos sa lahat o naglalaman ng isang maliit na bilang ng mga obserbasyon. Sa madaling salita, gaano ka-compact ang cluster na ito, o kabaliktaran, kung gaano ito kalat. Sa kabila ng sapat na katibayan ng ari-arian na ito, walang malinaw na paraan upang makalkula ang naturang tagapagpahiwatig (densidad). Ang pinakamatagumpay na indicator na nagpapakilala sa pagiging compactness, ang density ng "packing" ng mga multidimensional na obserbasyon sa isang partikular na cluster, ay ang dispersion ng distansya mula sa gitna ng cluster hanggang sa mga indibidwal na punto ng cluster. Kung mas maliit ang dispersion ng distansyang ito, mas malapit ang mga obserbasyon sa gitna ng cluster, mas malaki ang density ng cluster. At kabaligtaran, mas malaki ang pagpapakalat ng distansya, mas kalat ang kumpol na ito, at, dahil dito, may mga punto na matatagpuan kapwa malapit sa gitna ng kumpol at medyo malayo mula sa gitna ng kumpol.

Ang susunod na pag-aari ng mga kumpol ay ang kanilang laki. Ang pangunahing tagapagpahiwatig ng laki ng isang kumpol ay ang "radius" nito. Ang property na ito ay lubos na sumasalamin sa aktwal na laki ng cluster kung ang itinuturing na cluster ay bilog at isang hypersphere sa isang multidimensional na espasyo. Gayunpaman, kung ang mga kumpol ay may mga pahabang hugis, kung gayon ang konsepto ng radius o diameter ay hindi na sumasalamin sa tunay na laki ng kumpol.

Ang isa pang mahalagang katangian ng isang kumpol ay ang kanilang lokalidad, pagkakahiwalay. Inilalarawan nito ang antas ng magkakapatong at magkalayo ng mga kumpol mula sa isa't isa sa isang multidimensional na espasyo. Halimbawa, isaalang-alang ang pamamahagi ng tatlong cluster sa espasyo ng mga bago, pinagsama-samang feature sa figure sa ibaba. Ang Axes 1 at 2 ay nakuha sa pamamagitan ng isang espesyal na pamamaraan mula sa 12 mga tampok ng mapanimdim na mga katangian ng iba't ibang anyo ng mga erythrocytes, na pinag-aralan gamit ang electron microscopy.

Larawan 1

Nakikita namin na ang cluster 1 ay may pinakamababang laki, habang ang cluster 2 at 3 ay may humigit-kumulang pantay na laki. Kasabay nito, maaari nating sabihin na ang pinakamababang density, at samakatuwid ang maximum na dispersion ng distansya, ay katangian ng cluster 3. Bilang karagdagan, ang cluster 1 ay pinaghihiwalay ng sapat na malalaking seksyon ng walang laman na espasyo mula sa parehong cluster 2 at cluster 3. Samantalang ang mga cluster Ang 2 at 3 ay bahagyang magkakapatong sa isa't isa. Ang kawili-wili ay ang katotohanan na ang cluster 1 ay may mas malaking pagkakaiba mula sa ika-2 at ika-3 na cluster sa kahabaan ng axis 1 kaysa sa kahabaan ng axis 2. Sa kabaligtaran, ang mga cluster 2 at 3 ay humigit-kumulang na magkaiba sa bawat isa kapwa sa kahabaan ng axis 1 at sa kahabaan ng mga axes 2. Malinaw na para sa gayong visual na pagsusuri ay kinakailangan na ang lahat ng mga obserbasyon ng sample ay naka-proyekto sa mga espesyal na palakol, kung saan ang mga projection ng mga elemento ng kumpol ay makikita bilang hiwalay na mga kumpol.

2. 4 DISTANCE SA PAGITAN NG MGA CLUSTERS

Sa isang mas malawak na kahulugan, ang mga bagay ay mauunawaan hindi lamang bilang mga orihinal na paksa ng pananaliksik, na ipinakita sa "object-property" na matrix bilang isang hiwalay na linya, o bilang mga indibidwal na punto sa isang multidimensional na feature space, kundi pati na rin bilang mga hiwalay na grupo ng mga naturang punto. , pinagsama ng isang algorithm o iba pa sa isang kumpol. Sa kasong ito, ang tanong ay lumitaw kung paano maunawaan ang distansya sa pagitan ng mga naturang akumulasyon ng mga puntos (mga kumpol) at kung paano kalkulahin ito. Sa kasong ito, ang iba't ibang mga posibilidad ay mas malaki kaysa sa kaso ng pagkalkula ng distansya sa pagitan ng dalawang obserbasyon sa isang multidimensional na espasyo. Ang pamamaraang ito ay kumplikado sa pamamagitan ng katotohanan na, hindi katulad ng mga punto, ang mga kumpol ay sumasakop sa isang tiyak na halaga ng multidimensional na espasyo at binubuo ng maraming mga punto. Sa pagsusuri ng kumpol, malawakang ginagamit ang mga distansya ng intercluster, na kinakalkula sa prinsipyo ng pinakamalapit na kapitbahay (pinakamalapit na kapitbahay), sentro ng grabidad, pinakamalayo na kapitbahay (pinakamalayo na kapitbahay), median. Apat na paraan ang pinakamalawak na ginagamit: single linkage, full linkage, average linkage, at Ward's method. Sa paraan ng nag-iisang link, ang isang bagay ay ikakabit sa isang umiiral nang cluster kung kahit isa sa mga elemento ng cluster ay may parehong antas ng pagkakapareho sa bagay na pinagsama. Para sa paraan ng kumpletong mga link, ang isang bagay ay nakakabit sa isang cluster lamang kung ang pagkakatulad sa pagitan ng kandidato para sa pagsasama at alinman sa mga elemento ng cluster ay hindi bababa sa isang tiyak na threshold. Para sa karaniwang paraan ng koneksyon, mayroong ilang mga pagbabago, na ilang kompromiso sa pagitan ng solong at buong koneksyon. Kinakalkula nila ang average na halaga ng pagkakatulad ng kandidato para sa pagsasama sa lahat ng mga bagay ng umiiral na kumpol. Isinasagawa ang attachment kapag ang nakitang average na halaga ng pagkakatulad ay umabot o lumampas sa isang partikular na threshold. Ang pinakakaraniwang ginagamit ay ang arithmetic mean na pagkakapareho sa pagitan ng mga bagay ng cluster at ng kandidato para sa pagsasama sa cluster.

Marami sa mga pamamaraan ng clustering ay naiiba sa bawat isa dahil ang kanilang mga algorithm sa bawat hakbang ay kinakalkula ang iba't ibang mga paggana ng kalidad ng partitioning. Ang sikat na paraan ng Ward ay ginawa sa paraang ma-optimize ang pinakamababang pagkakaiba-iba ng mga distansya ng intracluster. Sa unang hakbang, ang bawat kumpol ay binubuo ng isang bagay, dahil sa kung saan ang intracluster dispersion ng mga distansya ay katumbas ng 0. Sa pamamaraang ito, ang mga bagay na nagbibigay ng pinakamababang pagtaas ng dispersion ay pinagsama, bilang isang resulta kung saan ang pamamaraang ito ay may posibilidad na bumuo ng hyperspherical cluster.

Ang maramihang mga pagtatangka sa pag-uuri ng mga pamamaraan ng pagsusuri ng kumpol ay humahantong sa dose-dosenang o kahit na daan-daang iba't ibang klase. Ang ganitong pagkakaiba-iba ay nabuo sa pamamagitan ng isang malaking bilang ng mga posibleng paraan upang makalkula ang distansya sa pagitan ng mga indibidwal na obserbasyon, walang mas kaunting bilang ng mga pamamaraan para sa pagkalkula ng distansya sa pagitan ng mga indibidwal na kumpol sa proseso ng clustering, at iba't ibang mga pagtatantya ng pinakamainam ng pangwakas na istraktura ng cluster.

Ang pinaka-malawak na ginagamit sa mga sikat na statistical package ay dalawang grupo ng mga cluster analysis algorithm: hierarchical agglomerative method at iterative grouping method.

3. MGA PAMAMARAAN NG PAGPAPAKA-GRUPO

3. 1 MGA TAMPOK NG HIERARCHICAL AGGLOMERATIVE METHODS

Sa agglomerative hierarchical algorithm, na mas madalas na ginagamit sa tunay na biomedical na pananaliksik, sa simula ang lahat ng mga bagay (obserbasyon) ay itinuturing na hiwalay, independiyenteng mga kumpol na binubuo lamang ng isang elemento. Kung wala ang paggamit ng malakas na teknolohiya ng computer, ang pagpapatupad ng pagsusuri ng data ng kumpol ay napakaproblema.

Ang pagpili ng panukat ay ginawa ng mananaliksik. Pagkatapos kalkulahin ang distance matrix, magsisimula ang proseso mga agglomerations (mula sa Latin na agglomero - ikinakabit ko, nag-iipon), na dumadaan nang sunud-sunod na hakbang-hakbang. Sa unang hakbang ng prosesong ito, dalawang paunang obserbasyon (monocluster) na may pinakamaliit na distansya sa pagitan ng mga ito ay pinagsama sa isang kumpol, na binubuo na ng dalawang bagay (obserbasyon). Kaya, sa halip na ang mga dating N monocluster (mga kumpol na binubuo ng isang bagay), pagkatapos ng unang hakbang, magkakaroon ng mga kumpol ng N-1, kung saan ang isang kumpol ay maglalaman ng dalawang bagay (mga obserbasyon), at ang mga kumpol ng N-2 ay bubuo pa rin ng isang bagay lamang. Sa pangalawang hakbang, posible ang iba't ibang paraan ng pagsasama-sama ng mga kumpol ng N-2. Ito ay dahil ang isa sa mga kumpol na ito ay naglalaman na ng dalawang bagay. Para sa kadahilanang ito, dalawang pangunahing katanungan ang lumitaw:

· kung paano kalkulahin ang mga coordinate ng naturang kumpol ng dalawa (at higit pa sa dalawa) mga bagay;

· kung paano kalkulahin ang distansya sa naturang "poly-object" cluster mula sa "monoclusters" at sa pagitan ng "poly-object" clusters.

Sa huli, tinutukoy ng mga tanong na ito ang panghuling istraktura ng mga nagresultang cluster (ang istraktura ng mga cluster ay nangangahulugang ang komposisyon ng mga indibidwal na cluster at ang kanilang relatibong posisyon sa isang multidimensional na espasyo). Ang iba't ibang kumbinasyon ng mga sukatan at pamamaraan para sa pagkalkula ng mga coordinate at magkaparehong distansya ng mga cluster ay nagbubunga ng iba't ibang mga pamamaraan ng pagsusuri ng cluster. Sa pangalawang hakbang, depende sa mga napiling pamamaraan para sa pagkalkula ng mga coordinate ng isang kumpol na binubuo ng ilang mga bagay at ang pamamaraan para sa pagkalkula ng mga distansya ng intercluster, posible na muling pagsamahin ang dalawang magkahiwalay na obserbasyon sa isang bagong kumpol, o upang sumali sa isang bago pagmamasid sa isang kumpol na binubuo ng dalawang bagay. Para sa kaginhawahan, ang karamihan sa mga programa ng agglomerative-hierarchical na pamamaraan sa pagtatapos ng trabaho ay maaaring magbigay ng dalawang pangunahing mga graph para sa pagtingin. Ang unang graph ay tinatawag na dendrogram (mula sa Greek dendron - puno), na sumasalamin sa proseso ng pagsasama-sama, ang pagsasama ng mga indibidwal na obserbasyon sa isang solong panghuling kumpol. Magbigay tayo ng isang halimbawa ng isang dendrogram ng 5 obserbasyon sa dalawang variable.

Iskedyul1

Ang patayong axis ng naturang graph ay ang axis ng intercluster distance, at ang mga bilang ng mga bagay - mga kaso na ginamit sa pagsusuri - ay minarkahan kasama ang pahalang na axis. Makikita mula sa dendrogram na ito na ang mga bagay No. 1 at No. 2 ay unang pinagsama sa isang kumpol, dahil ang distansya sa pagitan ng mga ito ay ang pinakamaliit at katumbas ng 1. Ang pagsasanib na ito ay ipinapakita sa graph sa pamamagitan ng isang pahalang na linya na nagkokonekta sa patayo. mga segment na lumalabas sa mga puntos na minarkahan bilang C_1 at C_2. Bigyang-pansin natin ang katotohanan na ang pahalang na linya mismo ay pumasa nang eksakto sa antas ng intercluster na distansya na katumbas ng 1. Dagdag pa, sa ikalawang hakbang, ang object No. 3, na itinalaga bilang C_3, ay sumasali sa kumpol na ito, na kinabibilangan na ng dalawang bagay. Ang susunod na hakbang ay pagsamahin ang mga bagay #4 at #5, ang distansya sa pagitan ng kung saan ay katumbas ng 1.41. At sa huling hakbang, ang kumpol ng mga bagay 1, 2 at 3 ay pinagsama sa kumpol ng mga bagay 4 at 5. Ipinapakita ng graph na ang distansya sa pagitan ng dalawang penultimate na kumpol na ito (ang huling kumpol ay kinabibilangan ng lahat ng 5 bagay) ay mas malaki sa 5 , ngunit mas mababa sa 6, dahil ang itaas na pahalang na linya na nagkokonekta sa dalawang penultimate na kumpol ay dumadaan sa isang antas na humigit-kumulang katumbas ng 7, at ang antas ng koneksyon ng mga bagay 4 at 5 ay 1.41.

Ang dendrogram sa ibaba ay nakuha sa pamamagitan ng pagsusuri ng isang totoong dataset na binubuo ng 70 naprosesong sample ng kemikal, na ang bawat isa ay nailalarawan sa pamamagitan ng 12 mga tampok.

Tsart 2

Makikita sa graph na sa huling hakbang, kapag nagsanib ang huling dalawang kumpol, ang distansya sa pagitan ng mga ito ay humigit-kumulang 200 units. Makikita na ang unang cluster ay may kasamang mas kaunting mga bagay kaysa sa pangalawang cluster. Sa ibaba ay isang pinalaki na seksyon ng dendrogram kung saan malinaw na nakikita ang mga observation number, na tinutukoy bilang C_65, C_58, atbp. (kaliwa pakanan): 65, 58, 59, 64, 63, 57, 60, 62, 56, 44, 94, atbp.

Tsart 3 Pinalaki na bahagi ng tsart #2 sa itaas

Makikita na ang object 44 ay isang monocluster na pinagsama sa tamang kumpol sa penultimate step, at pagkatapos, sa huling hakbang, ang lahat ng mga obserbasyon ay pinagsama sa isang cluster.

Ang isa pang graph na binuo sa naturang mga pamamaraan ay isang graph ng mga intercluster na distansya sa bawat hakbang ng unyon. Nasa ibaba ang isang katulad na balangkas para sa dendrogram sa itaas.

Tsart 4

Sa isang bilang ng mga programa, posibleng ipakita sa tabular form ang mga resulta ng pagsasama-sama ng mga bagay sa bawat hakbang ng clustering. Sa karamihan ng mga talahanayang ito, upang maiwasan ang pagkalito, iba't ibang terminolohiya ang ginagamit upang italaga ang mga unang obserbasyon - mga monocluster, at ang aktwal na mga kumpol na binubuo ng dalawa o higit pang mga obserbasyon. Sa mga pakete ng istatistika sa wikang Ingles, ang mga unang obserbasyon (mga hilera ng data matrix) ay itinalaga bilang "case" - case. Upang maipakita ang pag-asa ng istraktura ng kumpol sa pagpili ng sukatan at pagpili ng algorithm ng cluster union, ipinakita namin sa ibaba ang isang dendrogram na naaayon sa buong algorithm ng koneksyon. At dito makikita natin na ang object #44 ay pinagsama sa natitirang bahagi ng pagpili sa pinakahuling hakbang.

Tsart 5

Ngayon, ihambing natin ito sa isa pang tsart na nakuha sa pamamagitan ng paggamit ng single link method sa parehong data. Sa kaibahan sa buong paraan ng koneksyon, makikita na ang pamamaraang ito ay bumubuo ng mahabang kadena ng mga sunud-sunod na nakakabit na mga bagay sa bawat isa. Gayunpaman, sa lahat ng tatlong mga kaso, maaari nating sabihin na dalawang pangunahing grupo ang namumukod-tangi.

Tsart 6

Bigyang-pansin din natin ang katotohanan na sa lahat ng tatlong kaso ang object No. 44 ay nagsasama bilang isang monocluster, bagama't sa iba't ibang mga hakbang ng proseso ng clustering. Ang pagpili ng naturang mga monocluster ay isang mahusay na paraan ng pag-detect ng mga maanomalyang obserbasyon, na tinatawag na mga outlier. Tanggalin natin itong "kahina-hinalang" object No. 44 at muling magsagawa ng clustering. Nakukuha namin ang sumusunod na dendrogram:

Tsart 7

Makikita na ang epekto ng "kadena" ay napanatili, tulad ng paghahati sa dalawang lokal na grupo ng mga obserbasyon.

3. 2 MGA TAMPOK NG ITERATIVE CLUSTERING METHODS

Sa mga umuulit na pamamaraan, ang pinakasikat na pamamaraan ay ang k-means na pamamaraan ng McKean. Hindi tulad ng mga hierarchical na pamamaraan, sa karamihan ng mga pagpapatupad ng paraang ito, ang gumagamit mismo ay dapat tukuyin ang nais na bilang ng mga huling kumpol, na karaniwang tinutukoy bilang "k". Tulad ng sa mga hierarchical clustering na pamamaraan, maaaring pumili ang user ng isa o ibang uri ng sukatan. Ang iba't ibang mga algorithm ng pamamaraang k-means ay nagkakaiba din sa paraan ng pagpili ng mga paunang sentro ng mga ibinigay na kumpol. Sa ilang bersyon ng pamamaraan, ang gumagamit mismo ay maaaring (o dapat) tukuyin ang mga naturang paunang punto, alinman sa pamamagitan ng pagpili sa mga ito mula sa mga tunay na obserbasyon, o sa pamamagitan ng pagtukoy sa mga coordinate ng mga puntong ito para sa bawat isa sa mga variable. Sa iba pang mga pagpapatupad ng pamamaraang ito, ang pagpili ng isang naibigay na numero k ng mga paunang puntos ay ginagawa nang sapalaran, at ang mga paunang puntong ito (mga butil ng klaster) ay maaaring pagkatapos ay pinuhin sa ilang mga yugto. Mayroong 4 na pangunahing yugto ng naturang mga pamamaraan:

· pumili o magtalaga ng mga obserbasyon na magiging pangunahing sentro ng mga kumpol;

· kung kinakailangan, ang mga intermediate cluster ay nabuo sa pamamagitan ng pagtatalaga ng bawat obserbasyon sa pinakamalapit na tinukoy na mga cluster center;

· pagkatapos italaga ang lahat ng mga obserbasyon sa mga indibidwal na cluster, ang mga pangunahing cluster center ay pinapalitan ng mga cluster average;

· ang nakaraang pag-ulit ay paulit-ulit hanggang ang mga pagbabago sa mga coordinate ng mga sentro ng kumpol ay maging minimal.

Sa ilang bersyon ng paraang ito, maaaring magtakda ang user ng numerical value ng criterion, na binibigyang-kahulugan bilang pinakamababang distansya para sa pagpili ng mga bagong cluster center. Ang isang obserbasyon ay hindi ituturing bilang isang kandidato para sa isang bagong cluster center kung ang distansya nito sa pinalitan na cluster center ay lumampas sa tinukoy na numero. Ang parameter na ito ay tinatawag na "radius" sa ilang mga programa. Bilang karagdagan sa parameter na ito, posible ring itakda ang maximum na bilang ng mga pag-ulit o maabot ang isang tiyak, kadalasang medyo maliit, na numero, kung saan inihahambing ang pagbabago sa distansya para sa lahat ng cluster center. Ang setting na ito ay karaniwang tinutukoy bilang "convergence" dahil sumasalamin sa convergence ng umuulit na proseso ng clustering. Sa ibaba ay ipinakita namin ang ilan sa mga resulta na nakuha gamit ang McKean k-means na pamamaraan sa nakaraang data. Ang bilang ng mga hinahangad na cluster ay unang itinakda sa 3, at pagkatapos ay sa 2. Ang kanilang unang bahagi ay naglalaman ng mga resulta ng isang one-way na pagsusuri ng variance, kung saan ang cluster number ay gumaganap bilang isang grouping factor. Ang unang column ay isang listahan ng 12 variable, na sinusundan ng sums of squares (SS) at degrees of freedom (df), pagkatapos ay Fisher's F-test, at sa huling column ang significance level na "p" na nakamit.

Talahanayan 2 McKean k-means na data na naaangkop sa 70 sample ng pagsubok.

Mga variable

Tulad ng makikita mula sa talahanayang ito, ang null hypothesis tungkol sa pagkakapantay-pantay ng mga paraan sa tatlong grupo ay tinanggihan. Nasa ibaba ang isang graph ng paraan ng lahat ng variable para sa mga indibidwal na cluster. Ang parehong ibig sabihin ng cluster ng mga variable ay ipinakita sa ibaba sa anyo ng isang talahanayan.

Talahanayan 3. Detalyadong pagsusuri ng data sa halimbawa ng tatlong kumpol.

Variable	Cluster #1	Cluster #2	Cluster #3

Tsart 8

Ang pagsusuri ng mga average na halaga ng mga variable para sa bawat kumpol ay nagbibigay-daan sa amin upang tapusin na, ayon sa tampok na X1, ang mga kumpol 1 at 3 ay may malapit na mga halaga, habang ang kumpol 2 ay may average na halaga na mas mababa kaysa sa iba pang dalawang kumpol. Sa kabaligtaran, ayon sa tampok na X2, ang unang cluster ay may pinakamababang halaga, habang ang ika-2 at ika-3 cluster ay may mas mataas at malapit na average na mga halaga. Para sa mga katangiang X3-X12, ang mga mean value sa cluster 1 ay mas mataas kaysa sa cluster 2 at 3. Ang sumusunod na talahanayan ng ANOVA analysis ng mga resulta ng clustering sa dalawang cluster ay nagpapakita rin ng pangangailangan na tanggihan ang null hypothesis tungkol sa pagkakapantay-pantay. ng grupo ay nangangahulugan para sa halos lahat ng 12 mga tampok, maliban sa variable na X4, kung saan ang nakamit na antas ng kahalagahan ay naging higit sa 5%.

Talahanayan 4. Talaan ng dispersion analysis ng mga resulta ng clustering sa dalawang cluster.

Mga variable

Nasa ibaba ang isang graph at talahanayan ng mga paraan ng pangkat para sa kaso ng clustering sa dalawang cluster.

Talahanayan 5. Talahanayan para sa kaso ng pagkumpol sa dalawang kumpol.

Mga variable	Cluster #1	Cluster #2

Tsart 9.

Sa kaso kapag ang mananaliksik ay hindi matukoy nang maaga ang pinaka-malamang na bilang ng mga kumpol, napipilitan siyang ulitin ang mga kalkulasyon, na nagtatakda ng ibang numero, katulad ng ginawa sa itaas. At pagkatapos, sa paghahambing ng mga resultang nakuha sa isa't isa, huminto sa isa sa mga pinaka-katanggap-tanggap na opsyon sa clustering.

4 . CLUSTERING NG MGA TAMPOK

Bilang karagdagan sa pag-cluster ng mga indibidwal na obserbasyon, mayroon ding mga tampok na clustering algorithm. Ang isa sa mga unang naturang pamamaraan ay ang paraan ng correlation pleiades Terentiev P.V. Ang mga primitive na larawan ng naturang mga pleiades ay madalas na matatagpuan sa mga biomedical na publikasyon sa anyo ng isang bilog na may tuldok na mga arrow na nagkokonekta ng mga palatandaan kung saan ang mga may-akda ay nakakita ng isang ugnayan. Ang ilang mga programa para sa pag-cluster ng mga bagay at tampok ay may hiwalay na mga pamamaraan. Halimbawa, sa SAS package para sa feature clustering, ang VARCLUS procedure (mula sa VARiable - variable at CLUSter - cluster) ay ginagamit, habang ang cluster analysis ng mga obserbasyon ay ginagawa ng iba pang procedure - FASTCLUS at CLUSTER. Ang pagtatayo ng isang dendrogram sa parehong mga kaso ay isinasagawa gamit ang pamamaraan ng TREE (puno).

Sa iba pang istatistikal na pakete, ang pagpili ng mga elemento para sa clustering - mga bagay o tampok - ay ginawa sa parehong module. Bilang sukatan para sa clustering ng feature, kadalasang ginagamit ang mga expression na kinabibilangan ng value ng ilang partikular na coefficient na sumasalamin sa lakas ng relasyon para sa isang pares ng feature. Sa kasong ito, napaka-maginhawa para sa mga palatandaan na may lakas ng koneksyon na katumbas ng isa (functional dependence) na kunin ang distansya sa pagitan ng mga palatandaan na katumbas ng zero. Sa katunayan, sa isang functional na koneksyon, ang halaga ng isang tampok ay maaaring tumpak na kalkulahin ang halaga ng isa pang tampok. Sa isang pagbaba sa lakas ng ugnayan sa pagitan ng mga tampok, ang distansya ay tumataas nang naaayon. Nasa ibaba ang isang graph na nagpapakita ng dendrogram ng kumbinasyon ng 12 feature na ginamit sa itaas noong nag-cluster ng 70 analytical sample.

Tsart 10. Dendrogramclustering 12 mga tampok.

Tulad ng makikita mula sa dendrogram na ito, kami ay nakikitungo sa dalawang lokal na pagpapangkat ng mga tampok: X1-X10 at X11-X12. Ang pangkat ng mga tampok na X1-X10 ay nailalarawan sa pamamagitan ng isang medyo maliit na halaga ng mga intercluster na distansya, hindi hihigit sa humigit-kumulang 100 mga yunit. Dito makikita rin natin ang ilang panloob na nakapares na subgroup: X1 at X2, X3 at X4, X6 at X7. Ang distansya sa pagitan ng mga tampok ng mga pares na ito, na napakalapit sa zero, ay nagpapahiwatig ng kanilang malakas na relasyon ng pares. Samantalang para sa pares na X11 at X12 ang halaga ng intercluster distance ay mas malaki at humigit-kumulang 300 units. Sa wakas, ang napakalaking distansya sa pagitan ng kaliwa (X1-X10) at kanan (X11-X12) na mga cluster, katumbas ng humigit-kumulang 1150 unit, ay nagpapahiwatig na ang relasyon sa pagitan ng dalawang pangkat ng mga feature na ito ay medyo minimal.

5. KATATAGAN AT KALIDAD NG CLUSTERING

Malinaw, magiging walang katotohanan na itaas ang tanong kung gaano ganap ito o ang pag-uuri na iyon na nakuha sa tulong ng mga pamamaraan ng pagsusuri ng kumpol. Kapag binago ang pamamaraan ng clustering, ang katatagan ay nagpapakita ng sarili sa katotohanan na ang dalawang kumpol ay malinaw na nakikita sa mga dendrogram.

Bilang isa sa mga posibleng paraan upang suriin ang katatagan ng mga resulta ng pagsusuri ng kumpol, maaaring gamitin ang paraan ng paghahambing ng mga resultang nakuha para sa iba't ibang mga algorithm ng clustering. Ang iba pang paraan ay ang tinatawag na bootstrap method na iminungkahi ni B. Efron noong 1977, ang "jackknife" at "sliding control" na pamamaraan. Ang pinakasimpleng paraan ng pagsuri sa katatagan ng isang cluster solution ay maaaring random na hatiin ang paunang sample sa dalawang humigit-kumulang pantay na bahagi, i-cluster ang parehong bahagi, at pagkatapos ay ihambing ang mga resulta. Ang isang mas matagal na paraan ay kinabibilangan ng sunud-sunod na pagbubukod ng unang bagay sa simula at ang clustering ng natitirang (N - 1) na mga bagay. Dagdag pa, sunud-sunod na isinasagawa ang pamamaraang ito maliban sa pangalawa, pangatlo, atbp. bagay, sinusuri ang istraktura ng lahat ng nakuhang kumpol ng N. Ang isa pang algorithm para sa pagsuri sa katatagan ay nagsasangkot ng maramihang pagpaparami, pagdoble ng orihinal na sample ng N mga bagay, pagkatapos ay pagsasama-sama ang lahat ng mga nadobleng sample sa isang malaking sample (pseudo-general na populasyon) at random na pagkuha ng isang bagong sample ng N mga bagay mula dito. Pagkatapos nito, ang clustering ng sample na ito ay isinasagawa, pagkatapos ay isang bagong random na sample ay nakuha at ang clustering ay isinasagawa muli, atbp. Medyo labor intensive din ito.

Walang mas kaunting mga problema kapag tinatasa ang kalidad ng clustering. Ang ilang mga algorithm para sa pag-optimize ng mga solusyon sa kumpol ay kilala. Ang mga unang gawa na naglalaman ng mga formulation ng criterion para sa pagliit ng intracluster variance at isang algorithm (ng k-means type) para sa paghahanap ng pinakamainam na solusyon ay lumitaw noong 50s. Noong 1963 Ang artikulo ni J. Ward ay nagpakita rin ng katulad na hierarchical algorithm ng pag-optimize. Walang pangkalahatang pamantayan para sa pag-optimize ng solusyon sa kumpol. Ang lahat ng ito ay nagpapahirap sa mananaliksik na pumili ng pinakamainam na solusyon. Sa ganoong sitwasyon, ang pinakamahusay na paraan upang igiit na ang nahanap na cluster solution ay pinakamainam sa yugtong ito ng pag-aaral ay ang pagkakapare-pareho lamang ng solusyong ito sa mga konklusyong nakuha gamit ang iba pang mga pamamaraan ng multivariate statistics.

Sa pabor sa konklusyon tungkol sa pagiging mahusay ng clustering, mayroon ding mga positibong resulta ng pagsuri sa mga predictive na sandali ng nakuha na solusyon na nasa iba pang mga bagay ng pag-aaral. Kapag gumagamit ng mga hierarchical na pamamaraan ng cluster analysis, maaari naming irekomenda ang paghahambing ng ilang mga graph ng sunud-sunod na pagbabago sa intercluster na distansya sa isa't isa. Sa kasong ito, ang kagustuhan ay dapat ibigay sa opsyon kung saan ang isang patag na linya ng naturang pagtaas ay sinusunod mula sa unang hakbang hanggang sa ilang mga penultimate na hakbang na may matalim na vertical na pagtaas sa graph na ito sa huling 1-2 hakbang ng clustering.

KONKLUSYON

Sa aking trabaho, sinubukan kong ipakita hindi lamang ang pagiging kumplikado ng ganitong uri ng pagsusuri, kundi pati na rin ang pinakamainam na mga kakayahan sa pagproseso ng data, dahil madalas para sa katumpakan ng mga resulta na kailangan mong gamitin mula sa sampu hanggang daan-daang mga sample. Ang ganitong uri ng pagsusuri ay tumutulong sa pag-uuri at pagproseso ng mga resulta. Itinuturing ko rin na hindi mahalaga ang pagiging katanggap-tanggap ng mga teknolohiya ng computer sa pagsusuring ito, na ginagawang posible na gawing mas kaunting oras ang proseso ng pagproseso ng mga resulta at sa gayon ay nagbibigay-daan sa higit na pansin na mabayaran sa kawastuhan ng sampling para sa pagsusuri.

Sa paggamit ng cluster analysis, may mga ganitong subtlety at detalye na lumilitaw sa mga indibidwal na partikular na kaso at hindi agad nakikita. Halimbawa, ang papel ng laki ng mga tampok ay maaaring minimal, at maaaring nangingibabaw sa ilang mga kaso. Sa ganitong mga kaso kinakailangan na gumamit ng mga variable na pagbabago. Ito ay lalong epektibo kapag gumagamit ng mga pamamaraan na gumagawa ng mga non-linear na pagbabago sa tampok na karaniwang nagpapataas sa pangkalahatang antas ng mga ugnayan sa pagitan ng mga tampok.

Mayroong higit na higit na pagtitiyak sa paggamit ng pagsusuri ng kumpol kaugnay ng mga bagay na inilalarawan lamang ng mga katangiang husay. Sa kasong ito, ang mga pamamaraan ng paunang pag-digitize ng mga katangiang husay at pagsusuri ng kumpol na may mga bagong tampok ay medyo matagumpay. Sa aking trabaho, ipinakita ko na ang pagsusuri ng kumpol ay nagbibigay ng maraming bago at orihinal na impormasyon kapwa sa kaso ng aplikasyon nito sa sapat na pinag-aralan na mga sistema, at sa pag-aaral ng mga sistema na may hindi kilalang istraktura.

Dapat ding tandaan na ang pagsusuri ng kumpol ay naging kailangang-kailangan sa ebolusyonaryong pananaliksik, na nagpapahintulot sa pagtatayo ng mga punong phylogenetic na nagpapakita ng mga landas ng ebolusyon. Ang mga pamamaraang ito ay malawakang ginagamit din sa mga programang siyentipikong pananaliksik sa pisikal at analytical na kimika.

BIBLIOGRAPIYA

1) Aivazyan S. A., Enyukov I. S., Meshalkin L. D. Sa istraktura at nilalaman ng software package para sa inilapat na statistical analysis // Algorithmic at software para sa inilapat na statistical analysis.--M., 1980.

2) Ayvazyan S. A., Bezhaeva Z. I., Staroverov O. V. Pag-uuri ng mga multidimensional na obserbasyon.--M.: Statistics, 1974.

3) Becker V. A., Lukatskaya M. L. Sa pagsusuri ng istraktura ng matrix ng coupling coefficients // Mga isyu ng pang-ekonomiya at istatistikal na pagmomolde at pagtataya sa industriya.-- Novosibirsk, 1970.

4) Braverman E. M., Muchnik I. B. Mga istrukturang pamamaraan ng pagproseso ng data.--M.: Nauka, 1983.

5) Voronin Yu. A. Classification theory at mga aplikasyon nito.--Novosibirsk: Nauka, 1987.

6) Mabuting I.J. Botryology ng botryology//Classification and cluster.--M.: Mir, 1980.

7) Dubrovsky S. A. Inilapat ang multivariate na pagsusuri sa istatistika.--M.: Pananalapi at istatistika, 1982.

8) Duran N., Odell P. Cluster analysis.--M.: Statistics, 1977.

9) Eliseeva I.I., Rukavishnikov V.S. Pagpapangkat, ugnayan, pagkilala sa pattern.--M.: Statistics, 1977.

10) Zagoruiko N. G. Mga pamamaraan ng pagkilala at ang kanilang aplikasyon.--M .: Sobyet na radyo, 1972.

11) Zade L. A. Fuzzy set at ang kanilang aplikasyon sa pattern recognition at cluster analysis//Classification at cluster.--M.: Mir, 1980.

12) Kildishev G.S., Abolentsev Yu.I. Multidimensional groupings.--M.: Statistics, 1978.

13) Raiskaya II, Gostilin NI, Frenkel' AA Sa isang paraan upang suriin ang bisa ng paghahati sa cluster analysis.//Application ng multivariate statistical analysis sa economics at pagtatasa ng kalidad ng produkto.--Ch. P. Tartu, 1977.

14) Shurygin A. M. Distribution of interpoint distances and differences // Software at algorithmic na suporta para sa inilapat na multidimensional statistical analysis.--M., 1983.

15) Eeremaa R. Pangkalahatang teorya ng pagdidisenyo ng mga cluster system at algorithm para sa paghahanap ng kanilang mga numerical na representasyon: Proceedings of the Computing Center of TSU.--Tartu, 1978.

16) Yastremsky B.S. Napiling Mga Akda.--M.: Statistics, 1964.

Mga Katulad na Dokumento

Ang mga layunin ng segmentasyon ng merkado sa mga aktibidad sa marketing. Ang kakanyahan ng pagsusuri ng kumpol, ang mga pangunahing yugto ng pagpapatupad nito. Piliin kung paano sukatin ang distansya o sukat ng pagkakatulad. Hierarchical, non-hierarchical clustering na pamamaraan. Pagtatasa ng pagiging maaasahan at pagiging maaasahan.

ulat, idinagdag noong 02.11.2009

Ang mga pangunahing tagapagpahiwatig ng kalagayan sa pananalapi ng negosyo. Krisis sa negosyo, mga sanhi, uri at kahihinatnan nito. Mga modernong pamamaraan at tool ng pagsusuri ng kumpol, mga tampok ng kanilang paggamit para sa pagsusuri sa pananalapi at pang-ekonomiya ng negosyo.

thesis, idinagdag noong 10/09/2013

Magsagawa ng cluster analysis ng mga negosyo gamit ang Statgraphics Plus. Pagbuo ng isang linear regression equation. Pagkalkula ng mga coefficient ng elasticity sa pamamagitan ng mga modelo ng regression. Pagtatasa ng istatistikal na kahalagahan ng equation at ang koepisyent ng pagpapasiya.

gawain, idinagdag noong 03/16/2014

Konstruksyon ng mga typological regression para sa mga indibidwal na grupo ng mga obserbasyon. Spatial na data at temporal na impormasyon. Saklaw ng aplikasyon ng pagsusuri ng kumpol. Ang konsepto ng homogeneity ng mga bagay, mga katangian ng distance matrix. Nagsasagawa ng typological regression.

pagtatanghal, idinagdag noong 10/26/2013

Paglikha ng pinagsamang mga modelo at pamamaraan bilang modernong paraan ng pagtataya. Isang ARIMA-based na modelo para sa paglalarawan ng nakatigil at hindi nakatigil na serye ng oras sa paglutas ng mga problema sa clustering. Autoregressive AR na mga modelo at aplikasyon ng correlograms.

pagtatanghal, idinagdag noong 05/01/2015

Mga katangian ng iba't ibang uri ng sukatan. Pinakamalapit na paraan ng kapitbahay at mga paglalahat nito. Pinakamalapit na Neighbor Algorithm. Paraan ng Parzen window. Pangkalahatang metric classifier. Ang problema sa pagpili ng panukat. Manhattan at Euclidean na distansya. sukat ng cosine.

term paper, idinagdag 03/08/2015

Mga katangian ng industriya ng konstruksiyon ng Krasnodar Territory. Pagtataya ng pag-unlad ng pagtatayo ng pabahay. Mga modernong pamamaraan at tool ng pagsusuri ng kumpol. Multidimensional na istatistikal na pamamaraan para sa pag-diagnose ng pang-ekonomiyang estado ng isang negosyo.

thesis, idinagdag noong 07/20/2015

Mga katangian ng pagpapautang sa mortgage sa halimbawa ng rehiyon ng Bryansk. Pagsusuri ng mga pamamaraan sa paggawa ng desisyon sa matematika: mga pagsusuri ng eksperto, pagkakasunod-sunod at pairwise na paghahambing, pagsusuri ng hierarchy. Pagbuo ng isang programa sa paghahanap para sa pinakamainam na mortgage loan.

term paper, idinagdag noong 11/29/2012

Mga lugar ng aplikasyon ng pagsusuri ng system, lugar nito, papel, layunin at pag-andar sa modernong agham. Ang konsepto at nilalaman ng mga pamamaraan ng pagsusuri ng system, ang mga impormal na pamamaraan nito. Mga tampok ng heuristic at ekspertong pamamaraan ng pananaliksik at mga tampok ng kanilang aplikasyon.

term paper, idinagdag 05/20/2013

Pag-unlad at pananaliksik ng mga pamamaraang pang-ekonomiya, na isinasaalang-alang ang mga detalye ng data ng ekonomiya at alinsunod sa mga pangangailangan ng agham at kasanayan sa ekonomiya. Paglalapat ng mga pamamaraan at modelo ng ekonometric para sa pagsusuri sa istatistika ng data ng ekonomiya.

Ang aklat na ito ay nakatuon sa isa lamang sa mga pinaka-maaasahan na diskarte sa pagsusuri ng mga multidimensional na proseso at phenomena sa ganitong kahulugan - cluster analysis.

Ang pagsusuri ng cluster ay isang paraan ng pagpapangkat ng mga multidimensional na bagay, batay sa pagtatanghal ng mga resulta ng mga indibidwal na obserbasyon sa pamamagitan ng mga punto ng angkop na geometric na espasyo, na sinusundan ng pagpili ng mga grupo bilang "mga kumpol" ng mga puntong ito. Sa totoo lang, ang ibig sabihin ng “cluster” (cluster) sa Ingles ay “clot”, “bunch (of grapes)”, “cluster (of stars)”, atbp. Ang terminong ito ay hindi pangkaraniwang matagumpay na nababagay sa siyentipikong terminolohiya, dahil ang unang pantig nito ay tumutugma sa tradisyonal na terminong "klase", at ang pangalawa, kumbaga, ay nagpapahiwatig ng artipisyal na pinagmulan nito. Wala kaming alinlangan na papalitan ng terminolohiya ng pagsusuri ng cluster ang lahat ng mga konstruksyon na dati nang ginamit para sa layuning ito (unsupervised pattern recognition, stratification, taxonomy, awtomatikong pag-uuri, atbp.). Ang mga potensyal na posibilidad ng pagsusuri ng kumpol ay halata para sa paglutas, halimbawa, ang mga problema sa pagkilala sa mga grupo ng mga negosyo na tumatakbo sa magkatulad na mga kondisyon o may katulad na mga resulta, mga homogenous na grupo ng populasyon sa iba't ibang aspeto ng buhay o pamumuhay sa pangkalahatan, atbp.

Bilang isang pang-agham na direksyon, ang pagtatasa ng cluster ay nagpahayag ng sarili noong kalagitnaan ng 60s at mabilis na umuunlad mula noon, bilang isa sa mga sangay ng pinakamasinsinang paglago ng agham sa istatistika. Sapat na sabihin na ang bilang lamang ng mga monograp sa pagsusuri ng kumpol na inilathala hanggang sa kasalukuyan sa iba't ibang bansa ay sinusukat sa daan-daang (samantala, sabihin nating, ayon sa isang "karapat-dapat" na paraan ng multivariate na istatistikal na pagsusuri bilang factor analysis, halos hindi posibleng magbilang ng ilang dosenang aklat). At ito ay lubos na nauunawaan. Pagkatapos ng lahat, talagang pinag-uusapan natin ang pagmomodelo ng pagpapangkat ng operasyon, isa sa pinakamahalaga hindi lamang sa mga istatistika, ngunit sa pangkalahatan - kapwa sa katalusan at sa paggawa ng desisyon.

Ang isang bilang ng mga monograp ay nai-publish sa ating bansa na nakatuon sa pag-aaral ng mga tiyak na problema sa sosyo-ekonomiko gamit ang cluster analysis (1), ang pamamaraan para sa paggamit ng cluster analysis sa socio-economic na pananaliksik (2), ang pamamaraan ng cluster analysis tulad nito ( 3) (Mga Batayan ng istatistikal na pagsusuri )

Ang iminungkahing aklat ni I.D. Mandel ay, kumbaga, patayo sa klasipikasyong ito: ang nilalaman nito ay nauugnay sa bawat isa sa tatlong lugar na ito.

Ang layunin ng aklat ay upang ibuod ang kasalukuyang estado ng pagsusuri ng kumpol, upang pag-aralan ang mga posibilidad ng paggamit nito at ang mga gawain ng karagdagang pag-unlad. Ang ideyang ito sa sarili ay hindi maaaring pumukaw ng paggalang: ang isang walang kinikilingan na pagsusuri at paglalahat ay nangangailangan ng maraming trabaho, karunungan, katapangan, at na-rate ng siyentipikong komunidad na mas mababa kaysa sa pagsulong at pagbuo ng kanilang sariling mga disenyo. (Gayunpaman, naglalaman din ang aklat ng orihinal na mga pag-unlad ng may-akda na may kaugnayan sa "intensional" na pagsusuri at ang duality ng mga klasipikasyon.)

Parehong ang mga pakinabang ng libro at ang mga pagkukulang nito ay konektado sa pagsasakatuparan ng layuning ito. Ang mga pakinabang ay dapat isama:

· metodolohikal na pag-aaral ng mga konsepto ng homogeneity, pagpapangkat at pag-uuri, na isinasaalang-alang ang multidimensionality ng mga phenomena at proseso;

· isang sistematikong pagsusuri ng mga diskarte at pamamaraan ng pagsusuri ng kumpol (kabilang ang hanggang 150 partikular na algorithm);

· pagtatanghal ng teknolohiya at mga resulta ng eksperimentong paghahambing ng mga pamamaraan ng pagsusuri ng kumpol; Ang aklat na ito ay nakatuon sa isa lamang sa mga pinaka-maaasahan na diskarte sa pagsusuri ng mga multidimensional na proseso at phenomena sa ganitong kahulugan - cluster analysis.

Tinutukoy ng mga kalamangan na ito ang independiyenteng lugar ng aklat ng I. D. Mandel bukod sa iba pang mga publikasyon.

Ang mga pagkukulang ng aklat ay ang kalabuan ng ilang rekomendasyon at ang kawalan ng sistematikong pagsusuri sa mga isyu ng paggamit ng mga pamamaraan ng pagsusuri ng cluster sa mga aplikasyong sosyo-ekonomiko ng paksa. Totoo, ang huli ay dahil sa hindi sapat na paggamit ng cluster analysis sa lugar na ito.

Ang aklat ay nagbibigay ng isang pambuwelo, ang paggamit nito ay nagpapadali sa pag-unlad sa pinakamahirap na isyu ng anumang teorya - ang praktikal na paggamit ng mga tool na ibinibigay nito.

B. G. Mirkin

Unibersidad: VZFEI

Taon at lungsod: Moscow 2008

1. Panimula. Ang konsepto ng pamamaraan ng pagsusuri ng kumpol.

2. Paglalarawan ng pamamaraan para sa paglalapat ng cluster analysis. Kontrolin ang halimbawa ng paglutas ng problema.

4. Listahan ng mga ginamit na panitikan

Panimula. Ang konsepto ng pamamaraan ng pagsusuri ng kumpol.

Ang pagsusuri ng cluster ay isang hanay ng mga pamamaraan na nagbibigay-daan sa pag-uuri ng mga multidimensional na obserbasyon, na ang bawat isa ay inilalarawan ng isang hanay ng mga tampok (parameter) X1, X2, ..., Xk.

Ang layunin ng pagsusuri ng kumpol ay ang pagbuo ng mga pangkat ng mga bagay na magkatulad sa isa't isa, na karaniwang tinatawag na mga kumpol (klase, taxon, konsentrasyon).

Ang pagsusuri ng cluster ay isa sa mga lugar ng istatistikal na pananaliksik. Sinasakop nito ang isang partikular na mahalagang lugar sa mga sangay ng agham na nauugnay sa pag-aaral ng mass phenomena at mga proseso. Ang pangangailangan para sa pagbuo ng mga pamamaraan ng pagsusuri ng kumpol at ang kanilang paggamit ay idinidikta ng katotohanan na nakakatulong sila sa pagbuo ng mga klasipikasyong nakabatay sa siyentipiko, upang makilala ang mga panloob na ugnayan sa pagitan ng mga yunit ng naobserbahang populasyon. Bilang karagdagan, ang mga pamamaraan ng pagsusuri ng kumpol ay maaaring gamitin upang i-compress ang impormasyon, na isang mahalagang salik sa harap ng patuloy na pagtaas at pagiging kumplikado ng mga daloy ng istatistikal na data.

Ang mga pamamaraan ng pagsusuri ng cluster ay nagbibigay-daan sa paglutas ng mga sumusunod na problema:

Isinasagawa ang pag-uuri ng mga bagay, isinasaalang-alang ang mga tampok na sumasalamin sa kakanyahan, likas na katangian ng mga bagay. Ang solusyon sa naturang problema, bilang panuntunan, ay humahantong sa pagpapalalim ng kaalaman tungkol sa kabuuan ng mga bagay na inuri;

Sinusuri ang mga pagpapalagay na ginawa tungkol sa pagkakaroon ng ilang istraktura sa pinag-aralan na hanay ng mga bagay, i.e. maghanap para sa isang umiiral na istraktura;

Ang pagtatayo ng mga bagong klasipikasyon para sa hindi magandang pinag-aralan na mga phenomena, kapag kinakailangan upang maitaguyod ang pagkakaroon ng mga koneksyon sa loob ng populasyon at subukang ipakilala ang istraktura dito (1. pp. 85-86).

2. Paglalarawan ng pamamaraan para sa paglalapat ng cluster analysis. Kontrolin ang halimbawa ng paglutas ng problema.

Binibigyang-daan ka ng pagsusuri ng cluster na bumuo ng isang breakdown sa magkakatulad na mga grupo (mga kumpol) mula sa n mga bagay na nailalarawan sa pamamagitan ng mga tampok na k. Ang homogeneity ng mga bagay ay tinutukoy ng distansya p(xi xj), kung saan ang xi = (xi1, …., xik) at xj= (xj1,…,xjk) ay mga vectors na binubuo ng mga value ng k attribute ng i -th at j-th na mga bagay, ayon sa pagkakabanggit.

Para sa mga bagay na nailalarawan sa pamamagitan ng mga tampok na numero, ang distansya ay tinutukoy ng sumusunod na formula:

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

Ang mga bagay ay itinuturing na homogenous kung p(xi xj)< p предельного.

Ang isang graphic na representasyon ng unyon ay maaaring makuha gamit ang isang cluster union tree - isang dendrogram. (2. Kabanata 39).

Test case (halimbawa 92).


Dami ng benta

Uriin natin ang mga bagay na ito gamit ang prinsipyong "malapit sa kapitbahay". Hanapin natin ang mga distansya sa pagitan ng mga bagay gamit ang formula (1)* . Punan natin ang talahanayan.

Ipaliwanag natin kung paano napuno ang talahanayan.

Sa intersection ng row i at column j, ang distansya p(xi xj) ay ipinahiwatig (ang resulta ay bilugan hanggang sa dalawang decimal na lugar).

Halimbawa, sa intersection ng row 1 at column 3, ang distansya p(x1, x3) = √(1-6) 2 +(9-8) 2 ≈ 5.10 ay ipinahiwatig, at sa intersection ng row 3 at column 5, ang distansya p(x3 , x5) = √ (6-12) 2 + (8-7) 2 ≈ 6.08. Dahil p(xi, xj) = p(xj,xi), ang ibabang bahagi ng talahanayan ay hindi kailangang punan.

Ilapat natin ang prinsipyong "malapit sa kapitbahay". Nakita namin sa talahanayan ang pinakamaliit sa mga distansya (kung marami sa kanila, pagkatapos ay pipiliin namin ang alinman sa mga ito). Ito ay p 1.2 ≈ p 4.5 \u003d 2.24. Hayaan ang p min = p 4.5 = 2.24. Pagkatapos ay maaari nating pagsamahin ang mga bagay 4 at 5 sa isang pangkat, iyon ay, ang pinagsamang hanay 4 at 5 ay maglalaman ng pinakamaliit sa mga katumbas na bilang ng mga hanay 4 at 5 ng orihinal na talahanayan ng distansya. Ginagawa namin ang parehong sa mga linya 4 at 5. Kumuha kami ng isang bagong talahanayan.

Nakita namin sa resultang talahanayan ang pinakamaliit sa mga distansya (kung marami sa kanila, pipiliin namin ang alinman sa mga ito): р min = р 1.2 = 2.24. Pagkatapos ay maaari nating pagsamahin ang mga bagay 1,2,3 sa isang pangkat, iyon ay, ang pinagsamang column 1,2,3 ay maglalaman ng pinakamaliit sa mga katumbas na bilang ng column 1 at 2 at 3 ng nakaraang talahanayan ng distansya. Ginagawa namin ang parehong sa mga hilera 1 at 2 at 3. Kumuha kami ng bagong talahanayan.

Nakakuha kami ng dalawang kumpol: (1,2,3) at (4,5).

3. Paglutas ng mga problema para sa kontrol ng trabaho.

Suliranin 85.

Kundisyon: Ang limang pasilidad ng produksyon ay nailalarawan sa pamamagitan ng dalawang tampok: dami ng benta at ang average na taunang gastos ng mga fixed asset.


Dami ng benta
Average na taunang gastos ng mga fixed production asset

Solusyon: Hanapin natin ang mga distansya sa pagitan ng mga bagay gamit ang formula (1)* (iikot tayo sa dalawang decimal na lugar):

p 1,1 \u003d √ (2-2) 2 + (2-2) 2 \u003d 0

p 1.2 \u003d √ (2-5) 2 + (7-9) 2 ≈ 3.61

p 1.3 \u003d √ (2-7) 2 + (7-10) 2 ≈ 5.83

p 2.2 \u003d √ (5-5) 2 + (9-9) 2 \u003d 0

p 2.3 \u003d √ (5-7) 2 + (9-10) 2 ≈ 2.24

p 3.4 \u003d √ (7-12) 2 + (10-8) 2 ≈5.39

p 3.5 \u003d √ (7-13) 2 + (10-5) 2 ≈ 7.81

p 4.5 \u003d √ (12-13) 2 + (8-5) 2 ≈ 3.16

Batay sa mga resulta ng mga kalkulasyon, pinupunan namin ang talahanayan:

Ilapat natin ang pinakamalapit na prinsipyo ng kapitbahay. Upang gawin ito, makikita natin sa talahanayan ang pinakamaliit sa mga distansya (kung marami sa kanila, pagkatapos ay piliin ang alinman sa mga ito). Ito ay p 2.3=2.24. Hayaan ang p min = p 2.3 = 2.24, pagkatapos ay maaari nating pagsamahin ang mga bagay ng mga haligi "2" at "3", at pagsamahin din ang mga hilera ng mga bagay na "2" at "3". Sa bagong talahanayan, ipinasok namin ang pinakamaliit na halaga mula sa orihinal na talahanayan sa pinagsamang mga grupo.

Sa bagong talahanayan nakita namin ang pinakamaliit sa mga distansya (kung may ilan sa mga ito, pagkatapos ay pipili kami ng alinman sa mga ito). Ito ay p 4.5=3.16. Hayaan ang p min = p 4.5 = 3.16, pagkatapos ay maaari nating pagsamahin ang mga bagay ng mga haligi "4" at "5", at pagsamahin din ang mga hilera ng mga bagay na "4" at "5". Sa bagong talahanayan, ipinasok namin ang pinakamaliit na halaga mula sa orihinal na talahanayan sa pinagsamang mga grupo.

Sa bagong talahanayan nakita namin ang pinakamaliit sa mga distansya (kung may ilan sa mga ito, pagkatapos ay pipili kami ng alinman sa mga ito). Ito ay p 1, 2 at 3=3.61. Hayaan ang p min = p 1, 2 at 3 = 3.61, pagkatapos ay maaari nating pagsamahin ang mga bagay sa hanay na "1" at "2 at 3" at pagsamahin din ang mga hilera. Sa bagong talahanayan, ipinasok namin ang pinakamaliit na halaga mula sa orihinal na talahanayan sa pinagsamang mga grupo.

Kumuha kami ng dalawang kumpol: (1,2,3) at (4,5).

Ipinapakita ng dendrogram ang pagkakasunud-sunod ng pagpili ng mga elemento at ang kaukulang pinakamababang distansya pmin.

Sagot: Bilang resulta ng pagsusuri ng kumpol ayon sa prinsipyo ng "pinakamalapit na kapitbahay", 2 kumpol ng mga bagay na katulad ng bawat isa ay nabuo: (1,2,3) at (4,5).

Suliranin 211.

Kundisyon: Ang limang pasilidad ng produksyon ay nailalarawan sa pamamagitan ng dalawang tampok: dami ng benta at ang average na taunang halaga ng mga fixed asset.


Dami ng benta
Average na taunang gastos ng mga fixed production asset

Uriin ang mga bagay na ito gamit ang pinakamalapit na prinsipyo ng kapitbahay.

Solusyon: Upang malutas ang problema, ipinakita namin ang data sa orihinal na talahanayan. Tukuyin natin ang mga distansya sa pagitan ng mga bagay. Uuriin natin ang mga bagay ayon sa prinsipyo ng "pinakamalapit na kapitbahay". Ang mga resulta ay ipinakita sa anyo ng isang dendrogram.


Dami ng benta
Average na taunang gastos ng mga fixed production asset

Gamit ang formula (1)*, hinahanap natin ang mga distansya sa pagitan ng mga bagay:

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, 0, p 3.4 = 5.10, p 3.5 = 4.12, p 4 ,4=0, p4.5=1, p5.5=0.

Ang mga resulta ay ipinakita sa talahanayan:

Ang pinakamaliit na halaga ng mga distansya sa talahanayan ay p 4.5=1. Hayaan ang p min = p 4.5 = 1, pagkatapos ay maaari nating pagsamahin ang mga bagay ng mga haligi "4" at "5", at pagsamahin din ang mga hilera ng mga bagay na "4" at "5". Sa bagong talahanayan, ipinasok namin ang pinakamaliit na halaga mula sa orihinal na talahanayan sa pinagsamang mga grupo.

Ang pinakamaliit na halaga ng mga distansya sa bagong talahanayan ay p 2, 4 at 5=2. Hayaan ang p min = p 2, 4 at 5=2, pagkatapos ay maaari nating pagsamahin ang mga bagay ng mga hanay na "4 at 5" at "3", at pagsamahin din ang mga hilera ng mga bagay na "4 at 5" at "3". Sa bagong talahanayan, ipinasok namin ang pinakamaliit na halaga mula sa talahanayan sa pinagsamang mga grupo.

Ang pinakamaliit na halaga ng mga distansya sa bagong talahanayan ay p 3,4,5=2. Hayaan ang p min = p 3,4,5=2, pagkatapos ay maaari nating pagsamahin ang mga bagay ng mga hanay na "3,4,5" at "2", at pagsamahin din ang mga hilera ng mga bagay na "3,4,5" at " 2". Sa bagong talahanayan, ipinasok namin ang pinakamaliit na halaga mula sa talahanayan sa pinagsamang mga grupo.

o mag-log in sa site.

Mahalaga! Ang lahat ng ipinakitang Test paper para sa libreng pag-download ay inilaan upang gumuhit ng isang plano o batayan para sa iyong sariling gawaing siyentipiko.

Kaibigan! Mayroon kang isang natatanging pagkakataon upang matulungan ang mga mag-aaral na katulad mo! Kung nakatulong sa iyo ang aming site na makahanap ng tamang trabaho, tiyak na nauunawaan mo kung paano mapadali ng gawaing idinagdag mo ang gawain ng iba.

Kung ang Control Work, sa iyong opinyon, ay hindi maganda ang kalidad, o natugunan mo na ang gawaing ito, mangyaring ipaalam sa amin.

CLUSTER ANALYSIS SA MGA PROBLEMA NG SOCIO-ECONOMIC FORECASTING

Panimula sa pagsusuri ng kumpol.

Kapag sinusuri at hinuhulaan ang mga socio-economic phenomena, madalas na nakakaharap ng mananaliksik ang multidimensionality ng kanilang paglalarawan. Nangyayari ito kapag nilutas ang problema ng segmentasyon ng merkado, pagbuo ng isang tipolohiya ng mga bansa ayon sa isang sapat na malaking bilang ng mga tagapagpahiwatig, hinuhulaan ang sitwasyon sa merkado para sa mga indibidwal na kalakal, pag-aaral at paghula ng depresyon sa ekonomiya, at maraming iba pang mga problema.

Ang mga pamamaraan ng multivariate analysis ay ang pinaka-epektibong tool sa dami para sa pag-aaral ng mga prosesong sosyo-ekonomiko na inilarawan ng isang malaking bilang ng mga katangian. Kabilang dito ang cluster analysis, taxonomy, pattern recognition, at factor analysis.

Ang pagsusuri ng kumpol ay pinakamalinaw na sumasalamin sa mga tampok ng pagsusuri ng multivariate sa pag-uuri, pagsusuri ng kadahilanan - sa pag-aaral ng komunikasyon.

Minsan ang cluster analysis approach ay tinutukoy sa literatura bilang numerical taxonomy, numerical classification, self-learning recognition, atbp.

Natagpuan ng pagsusuri ng cluster ang unang aplikasyon nito sa sosyolohiya. Ang pagtatasa ng cluster ng pangalan ay nagmula sa salitang Ingles na cluster - bunch, accumulation. Sa unang pagkakataon noong 1939 ang paksa ng pagsusuri ng kumpol ay tinukoy at ang paglalarawan nito ay ginawa ng mananaliksik na Trion. Ang pangunahing layunin ng pagsusuri ng kumpol ay hatiin ang hanay ng mga bagay at tampok na pinag-aaralan sa mga grupo o kumpol na magkakatulad sa naaangkop na kahulugan. Nangangahulugan ito na ang problema sa pag-uuri ng data at pagtukoy ng kaukulang istruktura dito ay nalutas na. Ang mga pamamaraan ng pagsusuri ng cluster ay maaaring ilapat sa iba't ibang mga kaso, kahit na sa mga kaso kung saan pinag-uusapan natin ang tungkol sa isang simpleng pagpapangkat, kung saan ang lahat ay bumababa sa pagbuo ng mga grupo ayon sa dami ng pagkakatulad.

Ang mahusay na bentahe ng pagtatasa ng kumpol ay nagbibigay-daan sa iyo upang hatiin ang mga bagay hindi sa pamamagitan ng isang parameter, ngunit sa pamamagitan ng isang buong hanay ng mga tampok. Bilang karagdagan, ang pagsusuri ng kumpol, hindi katulad ng karamihan sa mga pamamaraan sa matematika at istatistika, ay hindi nagpapataw ng anumang mga paghihigpit sa uri ng mga bagay na isinasaalang-alang, at nagbibigay-daan sa amin na isaalang-alang ang isang set ng paunang data na halos arbitraryong kalikasan. Malaki ang kahalagahan nito, halimbawa, para sa pagtataya ng conjuncture, kapag ang mga indicator ay may iba't ibang anyo na nagpapahirap sa paggamit ng mga tradisyonal na econometric approach.

Ginagawang posible ng pagsusuri ng cluster na isaalang-alang ang isang medyo malaking halaga ng impormasyon at lubhang bawasan, i-compress ang malaking halaga ng socio-economic na impormasyon, gawin itong compact at visual.

Malaki ang kahalagahan ng pagsusuri sa cluster kaugnay ng mga set ng time series na nagpapakilala sa pag-unlad ng ekonomiya (halimbawa, pangkalahatang kondisyon ng ekonomiya at kalakal). Dito posible na iisa ang mga panahon kung kailan ang mga halaga ng kaukulang mga tagapagpahiwatig ay medyo malapit, pati na rin upang matukoy ang mga pangkat ng mga serye ng oras, ang mga dinamika na kung saan ay halos magkapareho.

Maaaring gamitin ang pagsusuri ng cluster nang paikot. Sa kasong ito, ang pag-aaral ay isinasagawa hanggang sa makamit ang ninanais na mga resulta. Kasabay nito, ang bawat cycle dito ay makakapagbigay ng impormasyon na maaaring magbago nang malaki sa direksyon at mga diskarte ng karagdagang aplikasyon ng pagsusuri ng cluster. Ang prosesong ito ay maaaring katawanin bilang isang feedback system.

Sa mga problema ng sosyo-ekonomikong pagtataya, napaka-promising na pagsamahin ang cluster analysis sa iba pang quantitative na pamamaraan (halimbawa, sa regression analysis).

Tulad ng anumang iba pang pamamaraan, ang pagsusuri ng kumpol ay may ilang mga kawalan at limitasyon: Sa partikular, ang komposisyon at bilang ng mga kumpol ay nakasalalay sa napiling pamantayan sa paghati. Kapag binabawasan ang paunang data array sa isang mas compact na form, maaaring mangyari ang ilang mga pagbaluktot, at ang mga indibidwal na katangian ng mga indibidwal na bagay ay maaari ding mawala dahil sa kanilang pagpapalit ng mga katangian ng mga pangkalahatang halaga ng mga parameter ng cluster. Kapag nag-uuri ng mga bagay, kadalasan ang posibilidad ng kawalan ng anumang mga halaga ng kumpol sa itinuturing na hanay ay hindi pinansin.

Sa pagsusuri ng kumpol, itinuturing na:

a) pinahihintulutan ng mga napiling katangian, sa prinsipyo, ang nais na clustering;

b) ang mga yunit ng pagsukat (scale) ay napili nang tama.

Ang pagpili ng sukat ay may malaking papel. Karaniwan, ang data ay na-normalize sa pamamagitan ng pagbabawas ng mean at paghahati sa karaniwang paglihis upang ang pagkakaiba ay katumbas ng isa.

Ang problema ng pagsusuri ng kumpol.

Ang gawain ng pagtatasa ng kumpol ay hatiin ang hanay ng mga bagay G sa m (m ay isang integer) mga kumpol (subset) Q1, Q2, ..., Qm, batay sa data na nakapaloob sa set X, upang ang bawat bagay na Gj nabibilang sa isa at isang partition subset lamang at ang mga bagay na kabilang sa parehong cluster ay magkapareho, habang ang mga bagay na kabilang sa iba't ibang cluster ay magkakaiba.

Halimbawa, hayaan ang G na magsama ng n bansa, na ang bawat isa ay nailalarawan sa pamamagitan ng GNP per capita (F1), ang bilang ng M ng mga sasakyan sa bawat 1,000 tao (F2), per capita electricity consumption (F3), per capita steel consumption (F4), atbp. Pagkatapos ang X1 (measurement vector) ay isang set ng mga tinukoy na katangian para sa unang bansa, X2 para sa pangalawa, X3 para sa pangatlo, at iba pa. Ang hamon ay hatiin ang mga bansa ayon sa antas ng pag-unlad.

Ang solusyon sa problema ng pagtatasa ng kumpol ay mga partisyon na nakakatugon sa isang tiyak na pamantayan ng pinakamainam. Ang pamantayang ito ay maaaring ilang functional na nagpapahayag ng mga antas ng kagustuhan ng iba't ibang partisyon at pagpapangkat, na tinatawag na layunin na function. Halimbawa, ang kabuuan ng intragroup ng mga squared deviations ay maaaring kunin bilang layunin na function:

kung saan ang xj - ay kumakatawan sa mga sukat ng j-th object.

Upang malutas ang problema ng pagsusuri ng kumpol, kinakailangan upang tukuyin ang konsepto ng pagkakapareho at heterogeneity.

Malinaw na ang i-th at j-th na mga bagay ay mahuhulog sa parehong kumpol kapag ang distansya (distansya) sa pagitan ng mga puntong Xi at Xj ay magiging sapat na maliit at mahuhulog sa iba't ibang mga kumpol kapag ang distansya na ito ay sapat na. Kaya, ang pagpasok sa isa o magkakaibang kumpol ng mga bagay ay tinutukoy ng konsepto ng distansya sa pagitan ng Xi at Xj mula sa Ep, kung saan ang Ep ay isang p-dimensional na Euclidean space. Ang isang di-negatibong function na d(Xi, Xj) ay tinatawag na isang function ng distansya (metric) kung:

a) d(Xi , Xj) ³ 0, para sa lahat ng Xi at Xj mula sa Ep

b) d(Xi, Xj) = 0 kung at kung Xi = Xj lamang

c) d(Xi, Xj) = d(Xj, Xi)

d) d(Xi, Xj) £ d(Xi, Xk) + d(Xk, Xj), kung saan Xj; Ang Xi at Xk ay anumang tatlong vectors mula sa Ep.

Ang halagang d(Xi, Xj) para sa Xi at Xj ay tinatawag na distansya sa pagitan ng Xi at Xj at katumbas ng distansya sa pagitan ng Gi at Gj ayon sa mga napiling katangian (F1, F2, F3, ..., Fр).

Ang pinakakaraniwang ginagamit na mga function ng distansya ay:

1. Euclidean distance d2(Хi , Хj) =

2. l1 - pamantayan d1(Хi , Хj) =

3. Supremum - norm d¥ (Хi , Хj) = sup

k = 1, 2, ..., p

4. lp - pamantayan dр(Хi , Хj) =

Ang Euclidean metric ang pinakasikat. Ang sukatan ng l1 ay ang pinakamadaling kalkulahin. Ang supremum-norm ay madaling kalkulahin at may kasamang pamamaraan ng pag-order, habang ang lp-norm ay sumasaklaw sa mga function ng distansya 1, 2, 3,.

Hayaang ang mga sukat na X1, X2,..., Xn ay kinakatawan bilang isang p ´n data matrix:

Kung gayon ang distansya sa pagitan ng mga pares ng mga vectors d(Хi , Хj) ay maaaring katawanin bilang isang simetriko na distansyang matrix:

Ang konsepto na kabaligtaran ng distansya ay ang konsepto ng pagkakatulad sa pagitan ng mga bagay na Gi. at si Gj. Ang isang di-negatibong real function S(Хi ; Хj) = Sij ay tinatawag na sukatan ng pagkakatulad kung:

1) 0 £ S(Xi , Xj)<1 для Хi¹ Хj

2) S(Хi , Хi) = 1

3) S(Xi, Xj) = S(Xj, Xi)

Ang mga pares ng mga halaga ng sukat ng pagkakatulad ay maaaring pagsamahin sa isang matrix ng pagkakatulad:

Ang halaga ng Sij ay tinatawag na koepisyent ng pagkakatulad.

1.3. Mga pamamaraan ng pagsusuri ng kumpol.

Ngayon maraming mga paraan ng pagsusuri ng kumpol. Isaalang-alang natin ang ilan sa mga ito (ang mga pamamaraan na ibinigay sa ibaba ay karaniwang tinatawag na mga pamamaraan ng pinakamababang pagkakaiba).

Hayaang X ang observation matrix: X = (X1, X2,..., Xu) at ang parisukat ng Euclidean distance sa pagitan ng Xi at Xj ay tinutukoy ng formula:

1) Ang paraan ng kumpletong koneksyon.

Ang kakanyahan ng pamamaraang ito ay ang dalawang bagay na kabilang sa parehong pangkat (kumpol) ay may pagkakatulad na koepisyent na mas mababa sa ilang halaga ng threshold S. Sa mga tuntunin ng Euclidean na distansya d, nangangahulugan ito na ang distansya sa pagitan ng dalawang punto (mga bagay) ng hindi dapat lumampas ang cluster sa ilang halaga ng threshold h. Kaya, tinutukoy ng h ang maximum na pinapayagang diameter ng isang subset na bumubuo ng isang kumpol.

2) Paraan ng maximum na lokal na distansya.

Ang bawat bagay ay itinuturing bilang isang kumpol na may isang punto. Ang mga bagay ay pinagsama ayon sa sumusunod na panuntunan: dalawang kumpol ay pinagsama kung ang maximum na distansya sa pagitan ng mga punto ng isang kumpol at mga punto ng isa pa ay minimal. Ang pamamaraan ay binubuo ng n - 1 na hakbang at nagreresulta sa mga partisyon na tumutugma sa lahat ng posibleng partisyon sa nakaraang pamamaraan para sa anumang mga halaga ng threshold.

3) Paraan ng salita.

Sa pamamaraang ito, ang intragroup na kabuuan ng mga squared deviations ay ginagamit bilang isang layunin na function, na hindi hihigit sa kabuuan ng mga squared na distansya sa pagitan ng bawat punto (object) at ang average para sa cluster na naglalaman ng bagay na ito. Sa bawat hakbang, dalawang kumpol ang pinagsama na humahantong sa pinakamababang pagtaas sa layunin ng function, i.e. intragroup kabuuan ng mga parisukat. Ang pamamaraang ito ay naglalayong pagsamahin ang mga kumpol na malapit sa pagitan.

4) Paraan ng Centroid.

Ang distansya sa pagitan ng dalawang kumpol ay tinukoy bilang ang Euclidean na distansya sa pagitan ng mga sentro (mga average) ng mga kumpol na ito:

d2 ij = (`X – `Y)Т(`X – `Y) Ang pag-cluster ay nagpapatuloy nang sunud-sunod sa bawat n–1 na hakbang ay pinagsasama ang dalawang cluster na G at p na may pinakamababang halaga d2ij Kung ang n1 ay mas malaki kaysa sa n2, kung gayon ang mga sentro ng pagsasama ng dalawang kumpol ay malapit sa isa't isa at ang mga katangian ng pangalawang kumpol ay halos hindi pinapansin kapag ang mga kumpol ay pinagsama. Minsan ang pamamaraang ito ay tinatawag ding pamamaraan ng mga may timbang na grupo.

1.4 Sequential clustering algorithm.

Isaalang-alang ang Ι = (Ι1, Ι2, … Ιn) bilang isang set ng mga cluster (Ι1), (Ι2),…(Ιn). Pumili tayo ng dalawa sa kanila, halimbawa, Ι i at Ι j, na kung saan ay mas malapit sa isa't isa at pagsamahin ang mga ito sa isang kumpol. Ang bagong hanay ng mga kumpol, na binubuo na ng mga n-1 na kumpol, ay magiging:

(Ι1), (Ι2)…, (Ι i , Ι j), …, (Ιn).

Sa pag-uulit ng proseso, nakakakuha tayo ng magkakasunod na hanay ng mga kumpol na binubuo ng (n-2), (n-3), (n-4), atbp. mga kumpol. Sa pagtatapos ng pamamaraan, maaari kang makakuha ng isang kumpol na binubuo ng n mga bagay at kasabay ng paunang hanay Ι = (Ι1, Ι2, … Ιn).

Bilang sukatan ng distansya, kinukuha namin ang parisukat ng Euclidean metric na di j2. at kalkulahin ang matrix D = (di j2), kung saan ang di j2 ay ang parisukat ng distansya sa pagitan

1	Ι2	Ι3	….	Ιn
1	0	d122	d132	….	d1n2
Ι2	0	d232	….	d2n2
Ι3	0	….	d3n2
….	….	….
Ιn	0

Hayaan ang distansya sa pagitan ng Ι i at Ι j ay minimal:

di j2 = min (di j2, i ¹ j). Sa tulong ng Ι i at Ι j bumuo tayo ng bagong cluster

(I, Ιj). Bumuo ng bagong ((n-1), (n-1)) distance matrix

(ako, ako j)	1	Ι2	Ι3	….	Ιn
(ako ; Ι j)	0	sa j21	sa j22	sa j23	….	di j2n
1	0	d122	d13	….	d12n
Ι2	0	sa j21	….	d2n
Ι3	0	….	d3n
Ιn	0

(n-2) na mga row para sa huling matrix ay kinuha mula sa nauna, at ang unang row ay muling kinukuwenta. Ang mga kalkulasyon ay maaaring bawasan sa pinakamababa kung ang di j2k,k = 1, 2,…, n ay maaaring ipahayag; (k ¹ i ¹ j) sa pamamagitan ng mga elemento ng orihinal na matrix.

Sa una, ang distansya ay tinutukoy lamang sa pagitan ng mga kumpol ng solong elemento, ngunit kinakailangan din na matukoy ang mga distansya sa pagitan ng mga kumpol na naglalaman ng higit sa isang elemento. Magagawa ito sa iba't ibang paraan, at depende sa napiling paraan, nakakakuha tayo ng mga algorithm ng pagsusuri ng cluster na may iba't ibang katangian. Ang isa, halimbawa, ay maaaring itakda ang distansya sa pagitan ng cluster i + j at ilang iba pang cluster k na katumbas ng arithmetic mean ng mga distansya sa pagitan ng cluster i at k at cluster j at k:

di+j,k = ½ (di k + dj k).

Ngunit maaari ding tukuyin ng isa ang di+j,k bilang pinakamababa sa dalawang distansyang ito:

di+j,k = min(di k + dj k).

Kaya, ang unang hakbang ng agglomerative hierarchical algorithm na operasyon ay inilarawan. Ang mga susunod na hakbang ay pareho.

Ang isang medyo malawak na klase ng mga algorithm ay maaaring makuha kung ang sumusunod na pangkalahatang formula ay ginagamit upang muling kalkulahin ang mga distansya:

di+j,k = A(w) min(dik djk) + B(w) max(dik djk), where

A(w) = kung dik £ djk

A(w) = kung dik > djk

B(w) = kung dik £ djk

B(w) = kung dik > djk

kung saan ang ni at nj ay ang bilang ng mga elemento sa mga kumpol na i at j, at ang w ay isang libreng parameter, na ang pagpili ay tumutukoy sa isang tiyak na algorithm. Halimbawa, sa w = 1, nakuha namin ang tinatawag na "average na koneksyon" na algorithm, kung saan ang formula para sa muling pagkalkula ng mga distansya ay kinuha ang form:

di+j,k =

Sa kasong ito, ang distansya sa pagitan ng dalawang cluster sa bawat hakbang ng algorithm ay lumalabas na katumbas ng arithmetic mean ng mga distansya sa pagitan ng lahat ng mga pares ng mga elemento kung kaya't ang isang elemento ng pares ay kabilang sa isang cluster, ang isa sa isa pa.

Ang visual na kahulugan ng parameter w ay nagiging malinaw kung ilalagay natin ang w®¥. Ang formula ng conversion ng distansya ay kinuha ang form:

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

Ito ang tinatawag na "pinakamalapit na kapitbahay" na algorithm, na nagbibigay-daan sa iyo upang pumili ng mga kumpol ng arbitraryong kumplikadong hugis, sa kondisyon na ang iba't ibang bahagi ng naturang mga kumpol ay konektado sa pamamagitan ng mga kadena ng mga elemento na malapit sa isa't isa. Sa kasong ito, ang distansya sa pagitan ng dalawang cluster sa bawat hakbang ng algorithm ay lumalabas na katumbas ng distansya sa pagitan ng dalawang pinakamalapit na elemento na kabilang sa dalawang cluster na ito.

Kadalasan ay ipinapalagay na ang mga paunang distansya (mga pagkakaiba) sa pagitan ng mga pinagsama-samang elemento ay ibinibigay. Sa ilang mga kaso, ito ay totoo. Gayunpaman, ang mga bagay lamang at ang kanilang mga katangian ang tinukoy, at ang distansya matrix ay itinayo batay sa mga datos na ito. Depende sa kung ang mga distansya sa pagitan ng mga bagay o sa pagitan ng mga katangian ng mga bagay ay kinakalkula, iba't ibang mga pamamaraan ang ginagamit.

Sa kaso ng pagsusuri ng kumpol ng mga bagay, ang pinakakaraniwang sukatan ng pagkakaiba ay alinman sa parisukat ng Euclidean na distansya.

(kung saan ang xih, xjh ay ang mga halaga ng h-th attribute para sa i-th at j-th na mga bagay, at m ay ang bilang ng mga katangian), o ang Euclidean distance mismo. Kung ang mga tampok ay itinalaga ng iba't ibang mga timbang, kung gayon ang mga timbang na ito ay maaaring isaalang-alang kapag kinakalkula ang distansya

Minsan ginagamit ang distansya bilang sukatan ng pagkakaiba, na kinakalkula ng formula:

na tinatawag na: "Hamming", "Manhattan" o "city-block" na distansya.

Ang natural na sukatan ng pagkakapareho ng mga katangian ng bagay sa maraming problema ay ang koepisyent ng ugnayan sa pagitan ng mga ito

kung saan ang mi ,mj ,di ,dj ay ang mean at root-mean-square deviations para sa mga katangiang i at j, ayon sa pagkakabanggit. Ang halaga 1 - r ay maaaring magsilbi bilang isang sukatan ng pagkakaiba sa pagitan ng mga katangian. Sa ilang mga problema, ang tanda ng koepisyent ng ugnayan ay hindi gaanong mahalaga at nakasalalay lamang sa pagpili ng yunit ng pagsukat. Sa kasong ito, ang ô1 - ri j ô ay ginagamit bilang sukatan ng pagkakaiba sa pagitan ng mga katangian

1.5 Bilang ng mga kumpol.

Ang isang napakahalagang isyu ay ang problema sa pagpili ng kinakailangang bilang ng mga kumpol. Minsan m bilang ng mga kumpol ay maaaring mapili ng isang priori. Gayunpaman, sa pangkalahatang kaso, ang numerong ito ay tinutukoy sa proseso ng paghahati ng set sa mga kumpol.

Ang mga pag-aaral ay isinagawa nina Fortier at Solomon, at nalaman na ang bilang ng mga kumpol ay dapat kunin upang makamit ang posibilidad na ang pinakamahusay na pagkahati ay matatagpuan. Kaya, ang pinakamainam na bilang ng mga partisyon ay isang function ng isang binigay na fraction b ng pinakamahusay o, sa ilang kahulugan, mga magagawa na partisyon sa hanay ng lahat ng posibleng mga partisyon. Ang kabuuang scattering ay magiging mas malaki, mas mataas ang fraction b ng mga tinatanggap na partisyon. Gumawa sina Fortier at Solomon ng isang talahanayan kung saan makikita ng isa ang bilang ng mga partisyon na kailangan. S(a,b) depende sa a at b (kung saan ang a ay ang posibilidad na ang pinakamahusay na partisyon ay matatagpuan, b ay ang proporsyon ng pinakamahusay na mga partisyon sa kabuuang bilang ng mga partisyon) Bukod dito, bilang isang sukatan ng heterogeneity, hindi ang scattering ang panukalang-batas ay ginagamit, ngunit ang panukalang-batas sa pagiging miyembro na ipinakilala nina Holzenger at Harman. Ang talahanayan ng mga halaga ng S(a,b) ay ibinigay sa ibaba.

S(a,b) na talahanayan ng halaga

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

Kadalasan, ang criterion para sa pagsasama-sama (ang bilang ng mga kumpol) ay ang pagbabago sa kaukulang function. Halimbawa, mga kabuuan ng mga squared deviation:

Ang proseso ng pagpapangkat ay dapat na tumutugma dito sa isang pare-parehong minimum na pagtaas sa halaga ng criterion E. Ang pagkakaroon ng isang matalim na pagtalon sa halaga ng E ay maaaring bigyang-kahulugan bilang isang katangian ng bilang ng mga kumpol na obhetibong umiiral sa populasyon na pinag-aaralan.

Kaya, ang pangalawang paraan upang matukoy ang pinakamahusay na bilang ng mga kumpol ay ang pagtukoy sa mga pagtalon na tinutukoy ng phase transition mula sa isang malakas na pinagsama sa isang mahinang pinagsamang estado ng mga bagay.

1.6 Mga Dendogram.

Ang pinakamahusay na kilalang paraan ng kumakatawan sa isang distansya o pagkakatulad na matrix ay batay sa ideya ng isang dendogram o tree diagram. Maaaring tukuyin ang Dendogram bilang isang graphic na representasyon ng mga resulta ng sequential clustering process, na isinasagawa sa mga tuntunin ng isang distance matrix. Sa tulong ng isang dendogram, posible na graphical o geometrical na ilarawan ang pamamaraan ng clustering, sa kondisyon na ang pamamaraang ito ay gumagana lamang sa mga elemento ng distansya o pagkakatulad na matrix.

Mayroong maraming mga paraan upang bumuo ng mga dendrogram. Sa dendrogram, ang mga bagay ay matatagpuan patayo sa kaliwa, ang mga resulta ng clustering ay nasa kanan. Ang mga halaga ng distansya o pagkakatulad na tumutugma sa istraktura ng mga bagong kumpol ay ipinapakita sa isang pahalang na tuwid na linya sa ibabaw ng mga dendrogram.

Ipinapakita ng Figure 1 ang isang halimbawa ng isang dendogram. Ang Figure 1 ay tumutugma sa kaso ng anim na bagay (n=6) at k na katangian (mga tampok). Ang mga Object A at C ay ang pinakamalapit at samakatuwid ay pinagsama sa isang cluster sa proximity level na katumbas ng 0.9. Ang mga bagay D at E ay pinagsama sa antas na 0.8. Ngayon mayroon kaming 4 na kumpol:

Ang uri ng dendogram ay nakasalalay sa pagpili ng sukat ng pagkakatulad o distansya sa pagitan ng bagay at ng cluster at ang pamamaraan ng clustering. Ang pinakamahalagang punto ay ang pagpili ng isang sukatan ng pagkakatulad o isang sukatan ng distansya sa pagitan ng isang bagay at isang kumpol.

Masyadong malaki ang bilang ng mga algorithm ng pagsusuri ng cluster. Lahat ng mga ito ay maaaring nahahati sa hierarchical at non-hierarchical.

Ang mga hierarchical algorithm ay nauugnay sa pagbuo ng mga dendogram at nahahati sa:

a) agglomerative, na nailalarawan sa pamamagitan ng isang pare-parehong kumbinasyon ng mga paunang elemento at isang kaukulang pagbaba sa bilang ng mga kumpol;

b) divisible (divisible), kung saan ang bilang ng mga kumpol ay tumataas, simula sa isa, bilang isang resulta kung saan ang isang pagkakasunud-sunod ng paghahati ng mga grupo ay nabuo.

Ang mga algorithm ng pagsusuri ng cluster ngayon ay may mahusay na pagpapatupad ng software na nagbibigay-daan sa paglutas ng mga problema sa pinakamataas na dimensyon.

1.7 Data

Maaaring ilapat ang pagsusuri ng cluster sa data ng pagitan, mga frequency, binary na data. Mahalaga na ang mga variable ay nagbabago sa maihahambing na mga sukat.

Ang heterogeneity ng mga yunit ng pagsukat at ang kasunod na imposibilidad ng isang makatwirang pagpapahayag ng mga halaga ng iba't ibang mga tagapagpahiwatig sa parehong sukat ay humahantong sa katotohanan na ang distansya sa pagitan ng mga punto, na sumasalamin sa posisyon ng mga bagay sa puwang ng kanilang mga pag-aari, ay lumalabas. na umaasa sa isang arbitraryong napiling sukat. Upang maalis ang heterogeneity ng pagsukat ng paunang data, ang lahat ng kanilang mga halaga ay preliminarily normalized, i.e. ay ipinahayag sa pamamagitan ng ratio ng mga halagang ito sa isang tiyak na halaga na sumasalamin sa ilang mga katangian ng tagapagpahiwatig na ito. Ang normalisasyon ng paunang data para sa pagsusuri ng kumpol ay minsan ay isinasagawa sa pamamagitan ng paghahati ng mga paunang halaga sa pamamagitan ng karaniwang paglihis ng kaukulang mga tagapagpahiwatig. Ang isa pang paraan ay ang pagkalkula ng tinatawag na standardized na kontribusyon. Tinatawag din itong Z-contribution.

Ang z-contribution ay nagpapakita kung gaano karaming mga standard deviations ang isang naibigay na obserbasyon ay naghihiwalay mula sa mean:

Kung saan ang xi ay ang halaga ng pagmamasid na ito, ay ang ibig sabihin, ang S ay ang karaniwang paglihis.

Ang ibig sabihin para sa Z-contributions ay zero at ang standard deviation ay 1.

Ang standardisasyon ay nagbibigay-daan sa paghahambing ng mga obserbasyon mula sa iba't ibang distribusyon. Kung ang distribusyon ng isang variable ay normal (o malapit sa normal) at ang mean at variance ay kilala o tinatantya mula sa malalaking sample, kung gayon ang Z-contribution ng isang obserbasyon ay nagbibigay ng mas tiyak na impormasyon tungkol sa lokasyon nito.

Tandaan na ang mga pamamaraan ng normalisasyon ay nangangahulugan ng pagkilala sa lahat ng mga tampok bilang katumbas mula sa punto ng view ng pagpapaliwanag ng pagkakapareho ng mga bagay na isinasaalang-alang. Napansin na na may kaugnayan sa ekonomiya, ang pagkilala sa pagkakapantay-pantay ng iba't ibang mga tagapagpahiwatig ay hindi laging makatwiran. Ito ay kanais-nais, kasama ng normalisasyon, na bigyan ang bawat isa sa mga tagapagpahiwatig ng isang timbang na sumasalamin sa kahalagahan nito sa kurso ng pagtatatag ng mga pagkakatulad at pagkakaiba sa pagitan ng mga bagay.

Sa sitwasyong ito, ang isa ay kailangang gumamit sa paraan ng pagtukoy ng mga timbang ng mga indibidwal na tagapagpahiwatig - isang survey ng mga eksperto. Halimbawa, kapag nilutas ang problema ng pag-uuri ng mga bansa ayon sa antas ng pag-unlad ng ekonomiya, ginamit namin ang mga resulta ng isang survey ng 40 nangungunang eksperto sa Moscow sa mga problema ng mga binuo na bansa sa isang sampung puntong sukat:

pangkalahatang mga tagapagpahiwatig ng pag-unlad ng socio-economic - 9 puntos;

mga tagapagpahiwatig ng pamamahagi ng sektor ng populasyon na may trabaho - 7 puntos;

mga tagapagpahiwatig ng pagkalat ng upahang paggawa - 6 na puntos;

mga tagapagpahiwatig na nagpapakilala sa elemento ng tao ng mga produktibong pwersa - 6 na puntos;

mga tagapagpahiwatig ng pag-unlad ng mga materyal na produktibong pwersa - 8 puntos;

tagapagpahiwatig ng pampublikong paggasta - 4 na puntos;

"military-economic" indicator - 3 puntos;

socio-demographic indicator - 4 na puntos.

Ang mga pagtatantya ng mga eksperto ay medyo matatag.

Ang mga pagtatasa ng eksperto ay nagbibigay ng isang kilalang batayan para sa pagtukoy ng kahalagahan ng mga tagapagpahiwatig na kasama sa isang partikular na grupo ng mga tagapagpahiwatig. Ang pagpaparami ng mga normal na halaga ng mga tagapagpahiwatig sa pamamagitan ng isang koepisyent na tumutugma sa average na marka ng pagtatasa ay ginagawang posible upang makalkula ang mga distansya sa pagitan ng mga punto na sumasalamin sa posisyon ng mga bansa sa isang multidimensional na espasyo, na isinasaalang-alang ang hindi pantay na bigat ng kanilang mga tampok.

Kadalasan, kapag nilutas ang mga naturang problema, hindi isa, ngunit dalawang kalkulasyon ang ginagamit: ang una, kung saan ang lahat ng mga palatandaan ay itinuturing na katumbas, ang pangalawa, kung saan binibigyan sila ng iba't ibang mga timbang alinsunod sa mga average na halaga ng mga pagtatantya ng eksperto.

1.8. Application ng cluster analysis.

Isaalang-alang natin ang ilang aplikasyon ng pagsusuri ng kumpol.

Ang paghahati ng mga bansa sa mga pangkat ayon sa antas ng pag-unlad.

65 na bansa ang pinag-aralan ayon sa 31 indicators (national income per capita, the share of the population employed in industry in %, savings per capita, the share of the population employed in agriculture in %, average life expectancy, the number of cars per 1 libong mga naninirahan, ang bilang ng mga armadong pwersa sa bawat 1 milyong naninirahan, ang bahagi ng GDP sa industriya sa%, ang bahagi ng GDP sa agrikultura sa%, atbp.)

Ang bawat isa sa mga bansa ay kumikilos sa pagsasaalang-alang na ito bilang isang bagay na nailalarawan sa pamamagitan ng ilang mga halaga ng 31 mga tagapagpahiwatig. Alinsunod dito, maaari silang katawanin bilang mga puntos sa isang 31-dimensional na espasyo. Ang ganitong espasyo ay karaniwang tinatawag na espasyo ng pag-aari ng mga bagay na pinag-aaralan. Ang paghahambing ng distansya sa pagitan ng mga puntong ito ay magpapakita ng antas ng kalapitan ng mga bansang isinasaalang-alang, ang kanilang pagkakatulad sa isa't isa. Ang socio-economic na kahulugan ng pag-unawang ito ng pagkakatulad ay nangangahulugan na ang mga bansa ay itinuturing na mas magkatulad, mas maliit ang mga pagkakaiba sa pagitan ng parehong mga tagapagpahiwatig kung saan sila ay inilarawan.

Ang unang hakbang ng naturang pagsusuri ay ang tukuyin ang pares ng pambansang ekonomiya na kasama sa similarity matrix, ang distansya sa pagitan ng kung saan ay ang pinakamaliit. Ang mga ito ay malinaw na magiging pinakakatulad, katulad na mga ekonomiya. Sa sumusunod na pagsasaalang-alang, ang parehong mga bansang ito ay itinuturing na isang grupo, isang solong kumpol. Alinsunod dito, ang orihinal na matrix ay binago upang ang mga elemento nito ay ang mga distansya sa pagitan ng lahat ng posibleng mga pares ng hindi 65, ngunit 64 na mga bagay - 63 mga ekonomiya at isang bagong nabagong kumpol - isang kondisyon na unyon ng dalawang pinaka magkatulad na mga bansa. Ang mga row at column na tumutugma sa mga distansya mula sa isang pares ng mga bansang kasama sa unyon sa lahat ng iba pa ay itinatapon mula sa orihinal na similarity matrix, ngunit may idinagdag na row at column na naglalaman ng distansya sa pagitan ng cluster na nakuha ng unyon at ibang mga bansa.

Ang distansya sa pagitan ng bagong nakuhang cluster at ng mga bansa ay ipinapalagay na katumbas ng average ng mga distansya sa pagitan ng huli at ng dalawang bansa na bumubuo sa bagong cluster. Sa madaling salita, ang pinagsamang pangkat ng mga bansa ay tinatrato bilang isang buo na may mga katangiang halos katumbas ng average ng mga katangian ng mga bumubuo nitong bansa.

Ang ikalawang hakbang ng pagsusuri ay isaalang-alang ang isang matrix na binago sa ganitong paraan na may 64 na row at column. Muli, ang isang pares ng mga ekonomiya ay natukoy, ang distansya sa pagitan ng kung saan ay hindi gaanong kahalagahan, at sila, tulad ng sa unang kaso, ay pinagsama-sama. Sa kasong ito, ang pinakamaliit na distansya ay maaaring pareho sa pagitan ng isang pares ng mga bansa, at sa pagitan ng alinmang bansa at ang unyon ng mga bansang nakuha sa nakaraang yugto.

Ang mga karagdagang pamamaraan ay katulad ng inilarawan sa itaas: sa bawat yugto, ang matrix ay binago upang ang dalawang hanay at dalawang hanay na naglalaman ng distansya sa mga bagay (mga pares ng mga bansa o asosasyon - mga kumpol) na pinagsama sa nakaraang yugto ay hindi kasama dito. ; ang mga ibinukod na row at column ay pinapalitan ng column at row na naglalaman ng mga distansya mula sa bagong pagsasama hanggang sa iba pang feature; higit pa, sa binagong matrix, ang isang pares ng pinakamalapit na bagay ay ipinahayag. Ang pagsusuri ay nagpapatuloy hanggang sa ganap na pagkaubos ng matrix (ibig sabihin, hanggang ang lahat ng mga bansa ay pinagsama-sama). Ang mga pangkalahatang resulta ng pagsusuri ng matrix ay maaaring katawanin sa anyo ng isang puno ng pagkakatulad (dendogram), katulad ng inilarawan sa itaas, na may pagkakaiba lamang na ang puno ng pagkakatulad, na sumasalamin sa kamag-anak na kalapitan ng lahat ng 65 na bansa na aming isinasaalang-alang, ay mas kumplikado kaysa sa iskema kung saan lumilitaw lamang ang limang pambansang ekonomiya. Kasama sa punong ito ang 65 na antas ayon sa bilang ng mga katugmang bagay. Ang unang (mas mababang) antas ay naglalaman ng mga puntos na naaayon sa bawat bansa nang hiwalay. Ang koneksyon ng dalawang puntong ito sa ikalawang antas ay nagpapakita ng isang pares ng mga bansa na pinakamalapit sa mga tuntunin ng pangkalahatang uri ng pambansang ekonomiya. Sa ikatlong antas, ang susunod na pinakakaparehong pares na ratio ng mga bansa ay nabanggit (tulad ng nabanggit na, alinman sa isang bagong pares ng mga bansa, o isang bagong bansa at isang natukoy na pares ng mga katulad na bansa ay maaaring nasa ratio na ito). At iba pa hanggang sa huling antas, kung saan ang lahat ng pinag-aralan na bansa ay kumikilos bilang isang set.

Bilang resulta ng paglalapat ng cluster analysis, nakuha ang sumusunod na limang grupo ng mga bansa:

grupong Afro-Asyano;

Latino-Asian group;

Latin-Mediterranean group;

pangkat ng mga mauunlad na kapitalistang bansa (walang USA)

Ang pagpapakilala ng mga bagong indicator na lampas sa 31 indicator na ginamit dito, o ang pagpapalit ng mga ito ng iba, ay natural na humahantong sa pagbabago sa mga resulta ng pag-uuri ng bansa.

2. Ang paghahati ng mga bansa ayon sa criterion ng proximity ng kultura.

Tulad ng alam mo, dapat isaalang-alang ng marketing ang kultura ng mga bansa (customs, tradisyon, atbp.).

Ang mga sumusunod na grupo ng mga bansa ay nakuha sa pamamagitan ng clustering:

Arabic;

Gitnang Silangan;

Scandinavian;

nagsasalita ng Aleman;

nagsasalita ng Ingles;

Romanesque European;

Latin American;

Malayong Silangan.

3. Pagbuo ng isang forecast ng merkado ng zinc.

Ang pagsusuri ng cluster ay gumaganap ng isang mahalagang papel sa yugto ng pagbabawas ng modelong pang-ekonomiya at matematika ng conjuncture ng kalakal, na nag-aambag sa pagpapadali at pagpapasimple ng mga pamamaraan sa pagkalkula, na tinitiyak ang higit na pagiging compact ng mga resulta na nakuha habang pinapanatili ang kinakailangang katumpakan. Ang paggamit ng pagsusuri ng kumpol ay ginagawang posible na hatiin ang buong paunang hanay ng mga tagapagpahiwatig ng merkado sa mga grupo (mga kumpol) ayon sa nauugnay na pamantayan, at sa gayon ay pinapadali ang pagpili ng pinakakinakatawan na mga tagapagpahiwatig.

Ang pagsusuri ng cluster ay malawakang ginagamit upang magmodelo ng mga kondisyon ng merkado. Sa pagsasagawa, ang karamihan sa mga gawain sa pagtataya ay batay sa paggamit ng pagsusuri ng kumpol.

Halimbawa, ang gawain ng pagbuo ng isang forecast ng merkado ng sink.

Sa una, 30 pangunahing tagapagpahiwatig ng pandaigdigang merkado ng zinc ang napili:

X1 - oras

Mga numero ng produksyon:

X2 - sa mundo

X4 - Europa

X5 - Canada

X6 - Japan

X7 - Australia

Mga tagapagpahiwatig ng pagkonsumo:

X8 - sa mundo

X10 - Europa

X11 - Canada

X12 - Japan

X13 - Australia

Mga stock ng producer ng zinc:

X14 - sa mundo

X16 - Europa

X17 - ibang mga bansa

Mga stock ng consumer ng zinc:

X18 - sa USA

X19 - sa England

X10 - sa Japan

Pag-import ng zinc ores at concentrates (libong tonelada)

X21 - sa USA

X22 - sa Japan

X23 - sa Germany

Pag-export ng zinc ores at concentrates (libong tonelada)

X24 - mula sa Canada

X25 - mula sa Australia

Pag-import ng zinc (libong tonelada)

X26 - sa USA

X27 - sa England

X28 - sa Germany

Pag-export ng zinc (libong tonelada)

X29 - mula sa Canada

X30 - mula sa Australia

Upang matukoy ang mga tiyak na dependencies, ginamit ang apparatus ng correlation at regression analysis. Ang mga relasyon ay nasuri batay sa isang matrix ng mga ipinares na coefficient ng ugnayan. Dito, tinanggap ang hypothesis ng normal na pamamahagi ng mga nasuri na tagapagpahiwatig ng conjuncture. Malinaw na ang rij ay hindi lamang ang posibleng tagapagpahiwatig ng kaugnayan ng mga tagapagpahiwatig na ginamit. Ang pangangailangan na gumamit ng pagsusuri ng kumpol sa problemang ito ay dahil sa ang katunayan na ang bilang ng mga tagapagpahiwatig na nakakaapekto sa presyo ng zinc ay napakalaki. May pangangailangan na bawasan ang mga ito para sa ilang mga sumusunod na dahilan:

a) kakulangan ng kumpletong istatistikal na data para sa lahat ng mga variable;

b) isang matalim na komplikasyon ng mga pamamaraan ng pagkalkula kapag ang isang malaking bilang ng mga variable ay ipinakilala sa modelo;

c) ang pinakamainam na paggamit ng mga pamamaraan ng pagsusuri ng regression ay nangangailangan ng labis sa bilang ng mga sinusunod na halaga sa bilang ng mga variable ng hindi bababa sa 6-8 beses;

d) ang pagnanais na gumamit ng mga independiyenteng variable ng istatistika sa modelo, atbp.

Napakahirap na isakatuparan ang naturang pagsusuri nang direkta sa isang medyo napakalaking matrix ng mga coefficient ng ugnayan. Sa tulong ng pagsusuri ng kumpol, ang buong hanay ng mga variable ng merkado ay maaaring hatiin sa mga grupo sa paraang ang mga elemento ng bawat kumpol ay malakas na magkakaugnay sa isa't isa, at ang mga kinatawan ng iba't ibang grupo ay nailalarawan sa pamamagitan ng mahinang ugnayan.

Upang malutas ang problemang ito, ang isa sa mga agglomerative hierarchical cluster analysis algorithm ay inilapat. Sa bawat hakbang, ang bilang ng mga kumpol ay nababawasan ng isa dahil sa pinakamainam, sa isang tiyak na kahulugan, unyon ng dalawang grupo. Ang criterion para sa pagsali ay baguhin ang kaukulang function. Bilang isang function nito, ginamit ang mga halaga ng mga kabuuan ng mga squared deviations na kinakalkula ng mga sumusunod na formula:

(j = 1, 2, …, m),

kung saan ang j ay ang cluster number, n ang bilang ng mga elemento sa cluster.

rij - koepisyent ng ugnayan ng pares.

Kaya, ang proseso ng pagpapangkat ay dapat tumutugma sa isang sunud-sunod na minimum na pagtaas sa halaga ng criterion E.

Sa unang yugto, ang paunang data array ay ipinakita bilang isang set na binubuo ng mga cluster, kabilang ang isang elemento bawat isa. Ang proseso ng pagpapangkat ay nagsisimula sa pagsasama ng naturang pares ng mga kumpol, na humahantong sa isang minimum na pagtaas sa kabuuan ng mga squared deviations. Nangangailangan ito ng pagtantya sa kabuuan ng mga squared deviation para sa bawat posibleng cluster union. Sa susunod na yugto, ang mga halaga ng mga kabuuan ng mga squared deviations ay isinasaalang-alang na para sa mga kumpol, at iba pa. Ang prosesong ito ay ititigil sa ilang hakbang. Upang gawin ito, kailangan mong subaybayan ang halaga ng kabuuan ng mga squared deviations. Isinasaalang-alang ang isang pagkakasunud-sunod ng pagtaas ng mga halaga, ang isang tao ay maaaring makakuha ng isang tumalon (isa o higit pa) sa dynamics nito, na maaaring bigyang-kahulugan bilang isang katangian ng bilang ng mga pangkat na "sa layunin" na umiiral sa pinag-aralan na populasyon. Sa halimbawa sa itaas, ang mga pagtalon ay naganap kapag ang bilang ng mga kumpol ay 7 at 5. Dagdag pa, ang bilang ng mga grupo ay hindi dapat bawasan, dahil ito ay humahantong sa pagbaba sa kalidad ng modelo. Matapos makuha ang mga kumpol, ang mga variable na pinakamahalaga sa pang-ekonomiyang kahulugan at pinaka malapit na nauugnay sa napiling pamantayan ng merkado - sa kasong ito, ang mga panipi ng London Metal Exchange para sa zinc - ay napili. Ang diskarte na ito ay nagpapahintulot sa iyo na i-save ang isang makabuluhang bahagi ng impormasyon na nilalaman sa orihinal na hanay ng mga paunang tagapagpahiwatig ng conjuncture.

Ang terminong "cluster analysis" ay unang ginamit ng American psychologist na si Robert Trion sa gawain ng parehong pangalan noong 1930. Sa kabila nito, ang mga terminong "cluster" at "cluster analysis" ay itinuturing ng mga katutubong nagsasalita bilang bago, na itinala ni Alexander Khrolenko, na nagsagawa ng corpus analysis ng paggamit ng lexeme na "cluster": "pinapansin ng karamihan sa mga may-akda na gumagamit ng terminong ito. ang pagiging bago nito" (Khrolenko , 2016, p. 106)

Kasama sa pagsusuri ng cluster ang maraming iba't ibang algorithm ng pag-uuri, ang layunin nito ay ayusin ang impormasyon sa mga cluster. Mahalagang tandaan na ang pagsusuri ng kumpol ay hindi sa sarili nitong isang tiyak na algorithm, ngunit mayroong isang gawain na kailangang lutasin. Sinabi ni Mark Ereshefsky sa kanyang akda na "The Scarcity of the Linear Hierarchy" na ang cluster analysis ay isa sa tatlong uri ng pag-uuri ng mga bagay sa mundo, kasama ang esensyaismo at historikal na pag-uuri.

Sa linggwistika, ang prinsipyo ng cluster ng paglalarawan ay nagpapahiwatig, bilang karagdagan sa pagsusuri ng mga yunit na kasama sa cluster na ito, pati na rin ang pagsusuri ng mga relasyon sa loob ng mga ito. Ito ay maaaring mga koneksyon ng iba't ibang antas: mula sa lohikal (paradigmatic at syntagmatic, halimbawa) hanggang sa pagbuo ng salita at phonetic na koneksyon.

Tinutukoy ni F. Brown ang mga sumusunod na hakbang ng pagsusuri ng kumpol (Brown):

1. Pagpili ng panukala at paggawa ng mga kinakailangang sukat, pamantayan o entidad na mauuri
2. Pagtatakda ng sukatan ng pagkakatulad
3. Pagbubuo ng mga panuntunan para sa pagtukoy ng pagkakasunud-sunod ng pagbuo ng kumpol
4. Paglalapat ng mga tuntunin sa pagbuo ng mga cluster

Dapat pansinin na ang ikatlong punto ay nagtataas ng mga katanungan, dahil ang tanda ng clustering bilang isang paraan ng pag-uuri ay ang kawalan ng mga tinukoy na klase. Ang clustering ng dokumento ay isang gawain sa pagkuha ng impormasyon. Hindi tulad ng pagkakategorya ng teksto, hindi kasama dito ang mga paunang natukoy na kategorya o set ng pagsasanay. Ang mga kumpol at ugnayan sa pagitan ng mga ito ay "awtomatikong kinukuha mula sa mga dokumento, at ang mga dokumento ay sunud-sunod na nakakabit sa mga kumpol na ito" (Golub, pp. 52-53) Ipinakilala ni Mark Ereshefsky ang cluster analysis bilang isang paraan ng pag-uuri. Naniniwala siya na "lahat ng anyo ng pagsusuri ng kumpol ay batay sa dalawang pagpapalagay: ang mga miyembro ng isang pangkat ng taxonomic ay dapat magbahagi ng isang kumpol ng mga katangian, at ang mga katangiang ito ay hindi maaaring lumitaw sa lahat o isang miyembro lamang ng pangkat na ito." (Ereshefsky, p. 15)

Sa kanyang gawaing "Cluster Approach in Linguistic Analysis" (Nurgalieva, 2013) N.Kh. Tinukoy ni Nurgalieva ang apat na pangunahing gawain ng pagsusuri ng kumpol:

1. Pagbuo ng isang tipolohiya o klasipikasyon
2. Paggalugad ng mga kapaki-pakinabang na conceptual scheme para sa pagpapangkat ng mga bagay
3. Paglalahad ng mga hypotheses batay sa mga nasaliksik na datos
4. Pagsubok ng mga hypotheses o pag-aaral upang matukoy kung ang mga uri (mga grupo) na natukoy sa isang paraan o iba ay aktwal na naroroon sa magagamit na data

Ang lahat ng mga pamamaraan ng pagsusuri ng kumpol ay maaaring nahahati sa "matigas", malinaw na pagsusuri ng kumpol, kapag ang bawat bagay ay kabilang sa isang kumpol o hindi, at "malambot", malabo na pagtatasa ng kumpol, kapag ang bawat bagay ay kabilang sa ilang grupo na may tiyak na antas ng posibilidad. .

Ang mga pamamaraan ng pagsusuri ng cluster ay nahahati din sa hierarchical at non-hierarchical. Ang mga hierarchical na pamamaraan ay nagpapahiwatig ng pagkakaroon ng mga nested na grupo, hindi katulad ng mga non-hierarchical na pamamaraan. Sinabi ni Nurgaliyeva na ang hierarchical na pamamaraan ay "tila ang pinaka-angkop para sa paglutas ng mga problema sa linggwistika" (Nurgaliyeva, p. 1), dahil pinapayagan ka nitong makita at suriin ang istraktura ng hindi pangkaraniwang bagay na pinag-aaralan.

Portal para sa mag-aaral. Pagsasanay sa sarili

Ipadala ang iyong mabuting gawa sa base ng kaalaman ay simple. Gamitin ang form sa ibaba

Mga Katulad na Dokumento

MGA KAUGNAY NA ARTIKULO