Shlukování FLAME - FLAME clustering

Zdá se, že hlavní přispěvatel do tohoto článku má úzké spojení s jeho předmětem. Může vyžadovat vyčištění, aby vyhovovalo zejména obsahovým zásadám Wikipedie neutrální hledisko. Diskutujte prosím dále o diskusní stránka. (Srpna 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Fuzzy shlukování podle místní aproximace MEmbershipů (FLAME) je shlukování dat algoritmus, který definuje klastry v hustých částech datové sady a provádí přiřazení klastrů výhradně na základě sousedských vztahů mezi objekty. Klíčovým rysem tohoto algoritmu je, že sousedské vztahy mezi sousedními objekty v prostoru funkcí se používají k omezení členství sousedních objektů ve fuzzy členském prostoru.

Popis algoritmu FLAME

Algoritmus FLAME je rozdělen hlavně do tří kroků:

1. Extrakce strukturních informací z datové sady:
   1. Vytvořte sousední graf pro připojení každého objektu k jeho K-Nearest Neighbors (KNN);
   2. Odhadněte hustotu pro každý objekt na základě jeho blízkosti k jeho KNN;
   3. Objekty jsou rozděleny do 3 typů:
      1. Cluster Supporting Object (CSO): objekt s hustotou vyšší než všichni jeho sousedé;
      2. Cluster Outliers: objekt s hustotou nižší než všichni jeho sousedé a nižší než předdefinovaná prahová hodnota;
      3. zbytek.
2. Místní / sousedská aproximace fuzzy členství:
   1. Inicializace fuzzy členství:
      1. Každý CSO je přiřazen s pevným a plným členstvím, aby zastupoval jeden klastr;
      2. Všechny odlehlé hodnoty jsou přiřazeny s pevným a plným členstvím do odlehlé skupiny;
      3. Zbytek je přiřazen se stejným členstvím všem klastrům a odlehlé skupině;
   2. Potom se fuzzy členství všech objektů typu 3 aktualizuje konvergující iterativní procedurou s názvem Místní / sousedská aproximace fuzzy členství, ve kterém je fuzzy členství každého objektu aktualizováno lineární kombinací fuzzy členství jeho nejbližších sousedů.
3. Konstrukce clusteru z fuzzy členství dvěma možnými způsoby:
   1. Individuální přiřazení klastru objektů k přiřazení každého objektu ke klastru, ve kterém má nejvyšší členství;
   2. Přiřazení clusterů objektů jeden k více, přiřadit každý objekt ke clusteru, ve kterém má členství vyšší než prahová hodnota.

Problém s optimalizací v FLAME

Místní / sousedská aproximace fuzzy členství je postup k minimalizaci místní / sousedské aproximační chyby (LAE / NAE) definované takto:

${displaystyle E ({{oldsymbol {p}}}) = součet _ {{oldsymbol {x}} v {oldsymbol {X}}} {igg |} {oldsymbol {p (x)}} - součet _ {oldsymbol { yin {mathcal {N}} (x)}} w_ {oldsymbol {xy}} {oldsymbol {p (y)}} {igg |} ^ {2}}$

kde ${displaystyle {oldsymbol {X}}}$ je sada všech objektů typu 3, ${displaystyle {oldsymbol {p (x)}}}$ je fuzzy vektor členství objektu ${displaystyle {oldsymbol {x}}}$, ${displaystyle {mathcal {N}} (x)}$ je sada nejbližších sousedů ${displaystyle {oldsymbol {x}}}$, a ${displaystyle w_ {oldsymbol {xy}}}$ s ${displaystyle sum _ {oldsymbol {yin {mathcal {N}} (x)}} w_ {oldsymbol {xy}} = 1}$ jsou koeficienty odrážející relativní blízkosti nejbližších sousedů.

NAE lze minimalizovat řešením následujících lineárních rovnic jedinečným řešením, které je jedinečným globálním minimem NAE s hodnotou nula:

${displaystyle p_ {k} ({oldsymbol {x}}) - součet _ {oldsymbol {yin {mathcal {N}} (x)}} w_ {oldsymbol {xy}} p_ {k} ({oldsymbol {y}} ) = 0, quad forall {{oldsymbol {x}} v {oldsymbol {X}}}, quad k = 1, ..., M}$

kde ${displaystyle M}$ je počet organizací občanské společnosti plus jedna (pro odlehlou skupinu). K řešení těchto lineárních rovnic lze použít následující iterační postup:

${displaystyle {{oldsymbol {p}} ^ {t + 1} ({oldsymbol {x}})} = součet _ {oldsymbol {yin {mathcal {N}} (x)}} w_ {oldsymbol {xy}} { {oldsymbol {p}} ^ {t} ({oldsymbol {y}})}}$

Jednoduchý obrázek na 2-dimenzionální testovací datové sadě

Viz také

• Shlukování dat
• Fuzzy shlukování

externí odkazy

• BMC Bioinformatics (2007): FLAME, nová metoda fuzzy shlukování pro analýzu dat z DNA microarray
• Zdrojové kódy FLAME v jazyce C vydané pod licencí typu FreeBSD na GoogleCode