FOREL familie algoritmer

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 14. januar 2020; verifikation kræver 1 redigering .

FOREL (Formal Element) er en klyngealgoritme baseret på ideen om at kombinere objekter til en klynge i områder med deres største koncentration.

Formål med klyngedannelse

Opdel prøven i et sådant (tidligere ukendt) antal taxa , så summen af afstande fra klyngeobjekter til klyngecentre er minimal for alle klynger. Det vil sige, at vores opgave er at identificere grupper af objekter så tæt på hinanden som muligt, som i kraft af lighedshypotesen vil danne vores klynger.

Kvalitetsfunktionen minimeret af algoritmen

F=\sum _{{j=1}}^{k}\sum _{{x\in K_{j}}}\rho (x,W_{j}),

hvor den første summering er over alle prøveklynger, er den anden summering over alle objekter, der hører til den aktuelle klynge , og er midten af den aktuelle klynge og er afstanden mellem objekterne. $x$ $K_{j}$ $W_j$ $\rho (x,y)$

Forudsætninger for arbejde

Opfyldelse af kompakthedshypotesen , som antager, at objekter tæt på hinanden med stor sandsynlighed tilhører samme klynge (taxon).
Tilstedeværelsen af et lineært eller metrisk rum af klyngede objekter.

Input data

Klyngeprøver

Det kan specificeres ved funktionsbeskrivelser af objekter - et lineært mellemrum eller en matrix af parvise afstande mellem objekter.
Bemærk: i rigtige opgaver er det ofte umuligt eller meningsløst at gemme alle data, så de nødvendige data indsamles i klyngeprocessen

Parameter R er søgeradius for lokale koncentrationer

Den kan indstilles både ud fra a priori-hensyn (kendskab til klyngediameteren) og justeres ved glidende kontrol.

I modifikationer er det muligt at indføre parameteren k — antallet af klynger.

Aftryk

Klynger sig til et hidtil ukendt antal taxa.

Sådan virker det

Ved hvert trin vælger vi tilfældigt et objekt fra prøven, puster en kugle med radius R op omkring det, vælger tyngdepunktet inde i denne kugle og gør det til centrum af den nye kugle. Det vil sige, at vi ved hvert trin flytter kuglen i retning af lokal koncentration af prøveobjekter, det vil sige, vi forsøger at fange så mange prøveobjekter som muligt med en kugle med fast radius. Efter at midten af kuglen har stabiliseret sig, markerer vi alle objekter inde i kuglen med dette center som klyngede og kasserer dem fra prøven. Vi gentager denne proces, indtil hele prøven er klynget.

Algoritme

Vi vælger tilfældigt det aktuelle objekt fra markeringen;
Vi markerer prøveobjekterne placeret i en afstand mindre end R fra den nuværende;
Vi beregner deres tyngdepunkt, markerer dette centrum som et nyt aktuelt objekt;
Gentag trin 2-3, indtil det nye aktuelle objekt matcher det gamle;
Vi markerer objekterne inden for kuglen med radius R omkring det aktuelle objekt som klyngede, smider dem ud af markeringen;
Gentag trin 1-5, indtil hele prøven er samlet.

Pseudokode for algoritmen i et C -lignende sprog:

# define R 30 // local clustering search width - input parameter for clusterization_not_finished () algoritme ; // er alle objekter grupperet get_random_object (); // returnerer et vilkårligt ikke- klynget objekt get_neighbour_objects ( type * objekt ); // returnerer en matrix af objekter placeret <= R fra det aktuelle center_of_objects ( type * masse_af_objekter ) ; // returnerer tyngdepunktet for de angivne objekter delete_objects ( type * masse_af_objekter ) ; // fjerner de angivne objekter fra markeringen ( vi har allerede grupperet dem ) while ( clusterisation_not_finished ()) { current_object = get_random_object (); naboobjekter = få_naboobjekter ( nuværende_objekt ); center_object = center_of_objects ( naboobjekter ); while ( center_objekt ! = nuværende_objekt ) // indtil tyngdepunktet stabiliserer sig { nuværende_objekt = center_objekt ; _ naboobjekter = få_naboobjekter ( nuværende_objekt ); center_object = center_of_objects ( naboobjekter ); } slette_objekter ( naboobjekter ); }

Tyngdepunktsheuristik

I det lineære rum, massecentrum;
I et metrisk rum, et objekt, hvor summen af afstande er minimal, blandt alle inde i kuglen;
Et objekt, der inden for en kugle med radius R indeholder det maksimale antal andre objekter fra hele markeringen (langsom);
Objektet, der indeholder det maksimale antal objekter inde i en kugle med lille radius (fra en kugle med radius R).

Observationer

Konvergensen af algoritmen i et begrænset antal trin er bevist;
I det lineære rum kan tyngdepunktet være et vilkårligt punkt i rummet, i metrisk rum, kun prøvens objekt;
Jo mindre R, jo flere taxa (klynger);
I lineært rum sker søgningen efter centrum i O(n) tid, i metrisk rum O(n²);
Algoritmen opnår de bedste resultater på prøver med god opfyldelse af kompakthedsbetingelserne;
Ved gentagelse af iterationer er det muligt at reducere parameteren R, for den hurtigste konvergens;
Klynger er meget afhængig af den indledende tilnærmelse (valg af objektet i det første trin);
Det anbefales at køre algoritmen igen for at eliminere situationen med "dårlig" klyngedannelse på grund af et mislykket valg af indledende objekter.

Fordele

Nøjagtigheden af at minimere den funktionelle kvalitet (med et vellykket valg af parameteren R);
Visualisering af klyngevisualisering;
Konvergens af algoritmen;
Muligheden for operationer på centre af klynger - de er kendt i løbet af algoritmen;
Evne til at beregne mellemkvalitetsfunktioner, for eksempel længden af en kæde af lokale koncentrationer;
Mulighed for at teste hypoteser om lighed og kompakthed i processen med algoritmedrift.

Ulemper

Relativ lav ydeevne (introduktionen af funktionen til genberegning af søgningen efter centrum, når der tilføjes 1 objekt inde i kuglen er løst);
Dårlig anvendelighed af algoritmen med dårlig separerbarhed af prøven i klynger;
Ustabilitet af algoritmen (afhængig af valget af det oprindelige objekt);
Vilkårlig ved nummeropdeling i klynger;
Behovet for a priori viden om bredden (diameteren) af klynger.

Tilføjelser

Efter at algoritmen har arbejdet på den færdige klyngedannelse, kan du udføre nogle handlinger:

Udvælgelse af de mest repræsentative (repræsentative) objekter fra hver klynge. Du kan vælge centrene for klynger, du kan vælge flere objekter fra hver klynge under hensyntagen til a priori viden om den nødvendige repræsentativitet af prøven. Således har vi ifølge den færdige klyngedannelse mulighed for at bygge det mest repræsentative stik;
Genberegning af clustering (multilevelness) ved brug af KNI-metoden.

Omfang

Løsning af klyngeproblemer;
Løsning af problemer med at rangere en prøve.

Se også

klyngeanalyse

Litteratur

Vorontsov K. V. Forelæsninger om clustering og multidimensionelle skaleringsalgoritmer , Moscow State University, 2007
Zagoruiko N. G., Yolkina V. N., Lbov G. S. Algoritmer til påvisning af empiriske mønstre. - Novosibirsk: Nauka, 1985. - 999 s.
Zagoruiko NG Anvendte metoder til data- og videnanalyse. - Novosibirsk: IM SO RAN, 1999. - 270 s. - ISBN 5-86134-060-9 .