Klyngeanalyse

Klyngeanalyse er en multidimensionel  statistisk procedure, der indsamler data, der indeholder information om en prøve af objekter, og derefter arrangerer objekter i relativt homogene grupper [1] [2] [3] [4] . Klyngeproblemet refererer til statistisk bearbejdning og også til en bred klasse af uovervågede læringsproblemer .

De fleste forskere (se f.eks. [5] ) er tilbøjelige til at tro, at udtrykket "klyngeanalyse" ( engelsk  klynge  - bundt, koagel, bundle) for første gang blev foreslået af psykologen R. Tryon [6] . Efterfølgende opstod der en række begreber, som i dag anses for at være synonyme med begrebet "klyngeanalyse": automatisk klassifikation, botryologi.

Anvendelsesområdet for klyngeanalyse er meget bredt: det bruges i arkæologi , medicin , psykologi , kemi , biologi , offentlig administration , filologi , antropologi , marketing , sociologi , geologi og andre discipliner. Anvendelsens universalitet har imidlertid ført til fremkomsten af ​​en lang række inkompatible termer, metoder og tilgange, der gør det vanskeligt entydigt at bruge og konsekvent fortolke klyngeanalyse.

Opgaver og betingelser

Klyngeanalyse udfører følgende hovedopgaver:

Uanset studieemnet involverer brugen af ​​klyngeanalyse følgende trin:

Du kan finde en beskrivelse af to grundlæggende krav til data - ensartethed og fuldstændighed. Homogenitet kræver, at alle klyngede enheder er af samme natur, beskrevet af et lignende sæt af karakteristika [7] . Hvis klyngeanalyse er forudgået af faktoranalyse , behøver prøven ikke at blive "repareret" - de angivne krav udføres automatisk af selve faktormodelleringsproceduren (der er en anden fordel - z-standardisering uden negative konsekvenser for prøven; hvis det udføres direkte til klyngeanalyse, det kan føre til at resultere i et fald i klarheden af ​​adskillelsen af ​​grupper). Ellers skal prøven justeres.

Typologi af klyngeproblemer

Input datatyper

I moderne videnskab bruges flere algoritmer til behandling af inputdata. Analyse ved at sammenligne objekter baseret på træk (mest udbredt i de biologiske videnskaber) kaldes Q -type analyse, og i tilfælde af sammenligning af træk baseret på objekter - R - type analyse. Der er forsøg på at bruge hybride analysetyper (for eksempel RQ- analyse ), men denne metode er endnu ikke blevet ordentligt udviklet.

Mål for klyngedannelse

I det første tilfælde forsøger de at gøre antallet af klynger mindre. I det andet tilfælde er det vigtigere at sikre en høj grad af lighed mellem objekter inden for hver klynge, og der kan være et hvilket som helst antal klynger. I det tredje tilfælde er individuelle objekter, der ikke passer ind i nogen af ​​klyngerne, af størst interesse.

I alle disse tilfælde kan hierarkisk clustering anvendes , når store klynger opdeles i mindre, som igen opdeles endnu mindre osv. Sådanne opgaver kaldes taksonomiopgaver . Resultatet af taksonomi er en trælignende hierarkisk struktur. Derudover er hvert objekt kendetegnet ved en opregning af alle klynger, som det tilhører, normalt fra store til små.

Klyngemetoder

Der er ingen almindeligt accepteret klassificering af klyngemetoder, men der kan skelnes mellem en række grupper af tilgange (nogle metoder kan henføres til flere grupper på én gang, og derfor foreslås det at betragte denne typificering som en tilnærmelse til den reelle klassificering af klyngedannelse. metoder) [9] :

  1. Probabilistisk tilgang . Det antages, at hvert objekt under overvejelse tilhører en af ​​k-klasserne. Nogle forfattere (for eksempel A. I. Orlov) mener, at denne gruppe slet ikke tilhører klyngedannelse og modsætter sig den under navnet "diskriminering", det vil sige valget af at tildele objekter til en af ​​de kendte grupper (træningsprøver).
  2. Tilgange baseret på kunstige intelligenssystemer: en meget betinget gruppe, da der er mange metoder, og metodisk er de meget forskellige.
  3. logisk tilgang. Konstruktionen af ​​et dendrogram udføres ved hjælp af et beslutningstræ.
  4. Grafteoretisk tilgang.
  5. Hierarkisk tilgang. Tilstedeværelsen af ​​indlejrede grupper (klynger af forskellige rækkefølger) antages. Algoritmer er til gengæld opdelt i agglomerative (forenende) og dividerende (adskillende). I henhold til antallet af funktioner skelnes der nogle gange mellem monotetiske og polytetiske klassificeringsmetoder.
  6. Andre metoder. Ikke inkluderet i de tidligere grupper.
    • Statistiske klyngealgoritmer
    • Ensemble af clusterers
    • Algoritmer fra KRAB-familien
    • Algoritme baseret på sigtemetoden
    • DBSCAN osv.

Tilgange 4 og 5 kombineres nogle gange under navnet på den strukturelle eller geometriske tilgang, som har et mere formaliseret koncept om nærhed [10] . På trods af de betydelige forskelle mellem de anførte metoder, er de alle afhængige af den oprindelige " kompakthedshypotese ": i objektrummet skal alle tætte objekter tilhøre den samme klynge, og alle forskellige objekter skal henholdsvis være i forskellige klynger.

Formel erklæring om klyngeproblemet

Lad være  et sæt af objekter,  være et sæt tal (navne, etiketter) af klynger. Afstandsfunktionen mellem objekter er angivet . Der er et begrænset træningssæt af objekter . Det er påkrævet at opdele prøven i ikke-overlappende delmængder, kaldet klynger , så hver klynge består af objekter, der er tæt på metrisk , og objekterne i forskellige klynger adskiller sig væsentligt. I dette tilfælde tildeles hvert objekt et klyngenummer .

Klyngealgoritmen  er en funktion , der forbinder ethvert objekt med et klyngenummer . Sættet er i nogle tilfælde kendt på forhånd, men oftere er opgaven at bestemme det optimale antal klynger i forhold til et eller andet kriterium for klyngekvalitet.

Clustering (ikke-overvåget læring ) adskiller sig fra klassificering ( overvåget læring ) ved, at etiketterne for de originale objekter ikke er sat til at begynde med, og selve sættet kan endda være ukendt .

Løsningen af ​​klyngeproblemet er grundlæggende tvetydig, og det er der flere årsager til (ifølge en række forfattere):

Ansøgning

I biologi

Inden for biologi har klyngedannelse mange anvendelser inden for en lang række områder. For eksempel i bioinformatik bruges det til at analysere komplekse netværk af interagerende gener, nogle gange bestående af hundredvis eller endda tusindvis af elementer. Klyngeanalyse giver dig mulighed for at identificere undernet, flaskehalse, hubs og andre skjulte egenskaber ved det undersøgte system, hvilket i sidste ende giver dig mulighed for at finde ud af hvert gens bidrag til dannelsen af ​​det undersøgte fænomen.

Inden for økologi er det meget brugt til at identificere rumligt homogene grupper af organismer, samfund osv. Mindre almindeligt bruges klyngeanalysemetoder til at studere samfund over tid. Heterogeniteten af ​​strukturen af ​​fællesskaber fører til fremkomsten af ​​ikke-trivielle metoder til klyngeanalyse (for eksempel Czekanowski-metoden ).

Historisk set er mål for lighed mere almindeligt brugt som mål for nærhed i biologi , snarere end mål for forskel (afstand).

I sociologi

Når man analyserer resultaterne af sociologisk forskning, anbefales det at udføre analysen ved hjælp af metoderne fra en hierarkisk agglomerativ familie, nemlig Ward-metoden, hvor den minimale spredning er optimeret inden for klyngerne, som følge heraf klynger af omtrent lige store størrelser er skabt. Wards metode er den mest succesrige til analyse af sociologiske data. Som et mål for forskel er den kvadratiske euklidiske afstand bedre, hvilket bidrager til en forøgelse af kontrasten af ​​klynger. Hovedresultatet af hierarkisk klyngeanalyse er et dendrogram eller "istapdiagram". Ved fortolkning af det står forskerne med et problem af samme art som fortolkningen af ​​resultaterne af faktoranalyse - manglen på entydige kriterier for at identificere klynger. Det anbefales at bruge to metoder som de vigtigste - visuel analyse af dendrogrammet og sammenligning af resultaterne af clustering udført ved forskellige metoder.

Visuel analyse af dendrogrammet involverer "skæring" af træet på det optimale niveau af lighed mellem prøveelementerne. "Vine branch" (terminologi af M. S. Oldenderfer og R. K. Blashfield [11] ) bør "afskæres" ved 5-mærket på Rescaled Distance Cluster Combine-skalaen, således vil et 80% lighedsniveau blive opnået. Hvis udvælgelsen af ​​klynger efter denne etiket er vanskelig (flere små klynger smelter sammen til en stor på den), så kan du vælge en anden etiket. Denne teknik er foreslået af Oldenderfer og Blashfield.

Nu opstår spørgsmålet om stabiliteten af ​​den vedtagne klyngeløsning. Faktisk kommer kontrol af stabiliteten af ​​clustering ned til at kontrollere dens pålidelighed. Der er en tommelfingerregel her - en stabil typologi bevares, når klyngemetoder ændres. Resultaterne af hierarkisk klyngeanalyse kan verificeres ved iterativ k-betyder klyngeanalyse. Hvis de sammenlignede klassifikationer af grupper af respondenter har en andel af tilfældigheder på mere end 70 % (mere end 2/3 af tilfældigheder), så træffes en klyngebeslutning.

Det er umuligt at kontrollere løsningens tilstrækkelighed uden at ty til en anden type analyse. I det mindste teoretisk er dette problem ikke blevet løst. Oldenderfer og Blashfields klassiske Cluster Analysis uddyber og afviser i sidste ende fem yderligere robusthedstestmetoder:

  1. kofenetisk korrelation  - ikke anbefalet og begrænset i brug;
  2. signifikanstest (variansanalyse) - giver altid et signifikant resultat;
  3. teknikken med gentagne (tilfældige) prøver, som dog ikke beviser gyldigheden af ​​beslutningen;
  4. signifikanstest for eksterne egenskaber er kun egnede til gentagne målinger;
  5. Monte Carlo metoder er meget komplekse og kun tilgængelige for erfarne matematikere .

I datalogi

Se også

Noter

  1. ↑ Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Anvendt statistik: Klassifikation og dimensionsreduktion. - M .: Finans og statistik, 1989. - 607 s.
  2. ↑ Mandel I. D. Klyngeanalyse. — M.: Finans og statistik, 1988. — 176 s.
  3. ↑ Khaidukov D.S. Anvendelse af klyngeanalyse i offentlig administration // Mathematics Philosophy: Actual Problemer. — M.: MAKS Press, 2009. — 287 s.
  4. ↑ Klassifikation og klynge. Ed. J. Wen Raizina. M.: Mir, 1980. 390 s.
  5. ↑ Mandel I. D. Klyngeanalyse. - M .: Finans og statistik, 1988. - S. 10.
  6. ↑ Tryon RC Cluster analyse. - London: Ann Arbor Edwards Bros, 1939. - 139 s.
  7. ↑ Zhambyu M. Hierarkisk klyngeanalyse og korrespondancer. — M.: Finans og statistik, 1988. — 345 s.
  8. ↑ Duran B., Odell P. Klyngeanalyse. — M.: Statistik, 1977. — 128 s.
  9. ↑ Berikov V. S., Lbov G. S. Moderne tendenser inden for klyngeanalyse Arkivkopi dateret 10. august 2013 på Wayback Machine // All-Russian konkurrencedygtigt udvalg af review- og analytiske artikler i den prioriterede retning "Information and telecommunication systems", 2008. - 26 s. ...
  10. ↑ Vyatchenin D. A. Fuzzy metoder til automatisk klassificering. - Minsk: Technoprint, 2004. - 219 s.
  11. ↑ Oldenderfer M.S., Blashfield R.K. Klyngeanalyse / Faktor-, diskriminant- og klyngeanalyse: pr. fra engelsk; Under. udg. I. S. Enyukova. — M.: Finans og statistik, 1989—215 s.

Links

På russisk På engelsk
  Gå til Wikidata-elementet  Ordbøger og encyklopædier
I bibliografiske kataloger