FLAME-gruppering - FLAME clustering

Fuzzy clustering by Local Approximation of MEmberships (FLAME) är en dataklastringsalgoritm som definierar kluster i de täta delarna av ett datasats och utför klustertilldelning enbart baserat på grannskapens relationer mellan objekt. Nyckelfunktionen i denna algoritm är att grannrelationerna mellan angränsande objekt i funktionsutrymmet används för att begränsa medlemskapen till angränsande objekt i det fuzzy medlemsutrymmet.

Beskrivning av FLAME-algoritmen

FLAME-algoritmen är huvudsakligen uppdelad i tre steg:

1. Utdragning av strukturinformation från datasatsen:
   1. Konstruera en kvartsgrafik för att ansluta varje objekt till dess K-närmaste grannar (KNN);
   2. Uppskatta en densitet för varje objekt baserat på dess närhet till KNN;
   3. Objekt klassificeras i 3 typer:
      1. Cluster Supporting Object (CSO): objekt med högre densitet än alla dess grannar;
      2. Cluster Outliers: objekt med densitet lägre än alla dess grannar och lägre än ett fördefinierat tröskelvärde;
      3. resten.
2. Lokal / grannskapsberäkning av fuzzy medlemskap:
   1. Initialisering av fuzzy medlemskap:
      1. Varje CSO tilldelas sig ett fast och fullt medlemskap till sig själv för att representera ett kluster;
      2. Alla utdelare tilldelas fast och fullständigt medlemskap i outlier-gruppen;
      3. Resten tilldelas lika medlemskap i alla kluster och utflyttargruppen;
   2. Sedan uppdateras de fuzzy-medlemskapen av alla typ 3-objekt genom ett konvergerande iterativt förfarande som kallas Local / Neighborhood Approximation of Fuzzy Memberships , där det fuzzy medlemskapet för varje objekt uppdateras med en linjär kombination av de fuzzy-medlemmarna i dess närmaste grannar.
3. Klusterkonstruktion från fuzzy medlemskap på två möjliga sätt:
   1. En-till-en-objekt-klustertilldelning, för att tilldela varje objekt till det kluster där det har det högsta medlemskapet;
   2. En-till-flera objekt-kluster-tilldelning, för att tilldela varje objekt till det kluster där det har ett medlemskap högre än en tröskel.

Optimeringsproblemet i FLAME

Lokalt / grannskapets tillnärmning av fuzzy medlemsskap är ett förfarande för att minimera det lokala / grannskapsmässiga tillnärmningsfelet (LAE / NAE) definierat som följande:

${\ displaystyle E (\ {{\ boldsymbol {p}} \}) = \ sum _ {{\ boldsymbol {x}} \ i {\ boldsymbol {X}}} {\ bigg \ |} {\ boldsymbol {p (x)}} - \ sum _ {\ boldsymbol {y \ i {\ mathcal {N}} (x)}} w _ {\ boldsymbol {xy}} {\ boldsymbol {p (y)}} {\ bigg \ |} ^ {2}}$

var är uppsättningen av alla typ 3-objekt, är den fuzzy medlemsvektorn för objektet , är uppsättningen av närmaste grannar till , och med är koefficienterna som återspeglar de relativa närheten till de närmaste grannarna. ${\ displaystyle {\ boldsymbol {X}}}$${\ displaystyle {\ boldsymbol {p (x)}}}$${\ displaystyle {\ boldsymbol {x}}}$${\ displaystyle {\ mathcal {N}} (x)}$${\ displaystyle {\ boldsymbol {x}}}$${\ displaystyle w _ {\ boldsymbol {xy}}}$${\ displaystyle \ sum _ {\ boldsymbol {y \ i {\ mathcal {N}} (x)}} w _ {\ boldsymbol {xy}} = 1}$

NAE kan minimeras genom att lösa följande linjära ekvationer med unik lösning som är det unika globala minimumet för NAE med värdet noll:

${\ displaystyle p_ {k} ({\ boldsymbol {x}}) - \ sum _ {\ boldsymbol {y \ i {\ mathcal {N}} (x)}} w _ {\ boldsymbol {xy}} p_ {k } ({\ boldsymbol {y}}) = 0, \ quad \ forall {{\ boldsymbol {x}} \ i {\ boldsymbol {X}}}, \ quad k = 1, ..., M}$

var är antalet CSO: er plus en (för den utvidgade gruppen). Följande iterativa procedur kan användas för att lösa dessa linjära ekvationer: ${\ displaystyle M}$

${\ displaystyle {{\ boldsymbol {p}} ^ {t + 1} ({\ boldsymbol {x}})} = \ sum _ {\ boldsymbol {y \ i {\ mathcal {N}} (x)}} w _ {\ boldsymbol {xy}} {{\ boldsymbol {p}} ^ {t} ({\ boldsymbol {y}})}}$

En enkel illustration på ett testdatasystem med 2 dimensioner

Se även

• Dataklustering
• Fuzzy clustering

externa länkar

• BMC Bioinformatics (2007): FLAME, en ny fuzzy clustering-metod för analys av DNA-mikroarray-data
• FLAME-källkoder i C släpps under FreeBSD-liknande licens på GoogleCode