FOREL familjealgoritmer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 14 januari 2020; verifiering kräver 1 redigering .

FOREL (Formal Element) är en klustringsalgoritm baserad på idén om att kombinera objekt till ett kluster i de områden där de har störst koncentration.

Syfte med klustring

Dela provet i ett sådant (tidigare okänt) antal taxa så att summan av avstånden från klusterobjekt till klustercentrum är minimal för alla kluster. Det vill säga vår uppgift är att identifiera grupper av objekt så nära varandra som möjligt, som i kraft av likhetshypotesen kommer att bilda våra kluster.

Kvalitetsfunktionen minimeras av algoritmen

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

där den första summeringen är över alla exempelkluster, är den andra summeringen över alla objekt som tillhör det aktuella klustret och är mitten av det aktuella klustret och är avståndet mellan objekten. $x$ $K_{j}$ $W_j$ $\rho (x,y)$

Förutsättningar för arbete

Uppfyllelse av kompakthetshypotesen , som antar att objekt nära varandra med hög sannolikhet tillhör samma kluster (taxon).
Närvaron av ett linjärt eller metriskt utrymme av klustrade objekt.

Indata

Klustrad provtagning

Det kan specificeras genom funktionsbeskrivningar av objekt — ett linjärt mellanrum eller en matris med parvisa avstånd mellan objekt.
Notera: i verkliga uppgifter är det ofta omöjligt eller meningslöst att lagra all data, så den nödvändiga informationen samlas in i klustringsprocessen

Parameter R är sökradien för lokala koncentrationer

Den kan ställas in både från a priori överväganden (kännedom om klusterdiametern) och justeras genom skjutreglage.

I modifieringar är det möjligt att införa parametern k — antalet kluster.

Imprint

Klustrar in i ett tidigare okänt antal taxa.

Hur det fungerar

Vid varje steg väljer vi slumpmässigt ett föremål från provet, blåser upp en sfär med radien R runt den, väljer tyngdpunkten inuti denna sfär och gör den till mitten av den nya sfären. Det vill säga, vid varje steg flyttar vi sfären i riktning mot lokal koncentration av provobjekt, det vill säga vi försöker fånga så många provobjekt som möjligt med en sfär med fast radie. Efter att sfärens mitt har stabiliserats, markerar vi alla objekt inuti sfären med detta centrum som klustrade och kasserar dem från provet. Vi upprepar denna process tills hela provet är klustrade.

Algoritm

Vi väljer slumpmässigt det aktuella objektet från urvalet;
Vi markerar provobjekten på ett avstånd mindre än R från det nuvarande;
Vi beräknar deras tyngdpunkt, markerar detta centrum som ett nytt aktuellt objekt;
Upprepa steg 2-3 tills det nya aktuella objektet matchar det gamla;
Vi markerar objekten inom sfären med radien R runt det aktuella objektet som klustrade, kastar ut dem ur markeringen;
Upprepa steg 1-5 tills hela provet är samlat.

Pseudokod för algoritmen i ett C -liknande språk:

# define R 30 // local clustering search width - input parameter för clusterization_not_finished () algoritm ; // är alla objekt klustrade get_random_object (); // returnerar ett godtyckligt icke- klustrat objekt get_neighbour_objects ( typ * objekt ); // returnerar en array av objekt placerade <= R från det aktuella centrum_av_objekt ( typ * massa_av_objekt ) ; // returnerar tyngdpunkten för de angivna objekten delete_objects ( typ * mass_of_objects ) ; // tar bort de angivna objekten från urvalet ( vi har redan klustrat dem ) while ( clusterisation_not_finished ()) { current_object = get_random_object (); neighbor_objects = get_neighbour_objects ( aktuellt_objekt ); center_object = center_of_objects ( granne_objekt ); while ( center_object ! = current_object ) // tills tyngdpunkten stabiliseras { current_object = center_object ; _ _ neighbor_objects = get_neighbour_objects ( aktuellt_objekt ); center_object = center_of_objects ( granne_objekt ); } delete_objects ( granne_objekt ); }

Tyngdpunktsheuristik

I det linjära rummet, masscentrum;
I ett metriskt utrymme, ett objekt, till vilket summan av avstånden är minimal, bland alla inne i sfären;
Ett objekt som, inom en sfär med radie R, innehåller det maximala antalet andra objekt från hela urvalet (långsamt);
Objektet som innehåller det maximala antalet objekt inom en sfär med liten radie (från en sfär med radie R).

Observationer

Konvergensen av algoritmen i ett ändligt antal steg bevisas;
I det linjära rymden kan tyngdpunkten vara en godtycklig punkt i rymden, i det metriska rummet, endast provets objekt;
Ju mindre R, desto fler taxa (kluster);
I det linjära rymden sker sökningen efter centrum i O(n) tid, i metriskt rum O(n²);
Algoritmen uppnår de bästa resultaten på prover med god uppfyllelse av kompakthetsvillkoren;
Vid upprepade iterationer är det möjligt att minska parametern R, för den snabbaste konvergensen;
Klustring är starkt beroende av den initiala approximationen (val av objekt i det första steget);
Det rekommenderas att köra algoritmen igen för att eliminera situationen med "dålig" klustring, på grund av ett misslyckat val av initiala objekt.

Fördelar

Noggrannheten för att minimera den funktionella kvaliteten (med ett framgångsrikt val av parametern R);
Visualisering av klustervisualisering;
Konvergens av algoritmen;
Möjligheten till operationer på centra av kluster - de är kända under algoritmens gång;
Förmåga att beräkna funktionaliteter av medelhög kvalitet, till exempel längden av en kedja av lokala koncentrationer;
Möjlighet att testa hypoteser om likhet och kompakthet i processen för algoritmdrift.

Nackdelar

Relativt låg prestanda (införandet av funktionen att räkna om sökningen efter centrum när man lägger till 1 objekt inuti sfären är löst);
Dålig tillämpbarhet av algoritmen med dålig separerbarhet av provet i kluster;
Algoritmens instabilitet (beroende på valet av det ursprungliga objektet);
Godtycklig genom nummeruppdelning i kluster;
Behovet av a priori kunskap om bredden (diametern) på kluster.

Tillägg

Efter att algoritmen har arbetat med den färdiga klustringen kan du utföra några åtgärder:

Val av de mest representativa (representativa) objekten från varje kluster. Du kan välja centra för kluster, du kan välja flera objekt från varje kluster, med hänsyn till a priori kunskap om provets representativitet. Således har vi enligt den färdiga klustringen möjlighet att bygga det mest representativa urvalet;
Omräkning av klustring (multilevelness) med KNI-metoden.

Omfattning

Lösa klustringsproblem;
Lösa problem med att rangordna ett prov.

Se även

klusteranalys

Litteratur

Vorontsov K. V. Föreläsningar om klustring och multidimensionella skalningsalgoritmer , Moscow State University, 2007
Zagoruiko N. G., Yolkina V. N., Lbov G. S. Algoritmer för att upptäcka empiriska mönster. - Novosibirsk: Nauka, 1985. - 999 sid.
Zagoruiko NG Tillämpade metoder för data- och kunskapsanalys. - Novosibirsk: IM SO RAN, 1999. - 270 sid. - ISBN 5-86134-060-9 .