FLAMEクラスタリング

FLAME（Fuzzy Clustering by Local approximation of MEmberships）は、データセットの密な部分にクラスターを定義し、オブジェクト間の近傍関係のみに基づいてクラスター割り当てを行うデータクラスタリングアルゴリズムです。このアルゴリズムの主な特徴は、特徴空間における隣接オブジェクト間の近傍関係を用いて、ファジーメンバーシップ空間における隣接オブジェクトのメンバーシップを制約することです。

FLAMEアルゴリズムの説明

FLAME アルゴリズムは主に 3 つのステップに分かれています。

1. データセットからの構造情報の抽出:
   1. 各オブジェクトを K 近傍 (KNN) に接続するための近傍グラフを構築します。
   2. KNN への近さに基づいて各オブジェクトの密度を推定します。
   3. オブジェクトは 3 つのタイプに分類されます。
      1. クラスター サポート オブジェクト (CSO): 密度がすべての近隣オブジェクトよりも高いオブジェクト。
      2. クラスター外れ値: 密度がすべての近傍よりも低く、事前定義されたしきい値よりも低いオブジェクト。
      3. 残り。
2. ファジーメンバーシップのローカル/近傍近似:
   1. ファジーメンバーシップの初期化:
      1. 各 CSO には、1 つのクラスターを表すために、固定された完全なメンバーシップが割り当てられます。
      2. すべての外れ値には外れ値グループへの固定された完全なメンバーシップが割り当てられます。
      3. 残りは、すべてのクラスターと外れ値グループに均等に割り当てられます。
   2. 次に、タイプ 3 のすべてのオブジェクトのファジー メンバーシップが、ファジー メンバーシップのローカル/近傍近似と呼ばれる収束反復手順によって更新されます。この手順では、各オブジェクトのファジー メンバーシップが、最も近い近傍のファジー メンバーシップの線形結合によって更新されます。
3. ファジー メンバーシップからクラスターを構築するには、次の 2 つの方法があります。
   1. 1 対 1 のオブジェクト クラスター割り当て。各オブジェクトを、そのオブジェクトが最も高いメンバーシップを持つクラスターに割り当てます。
   2. 1 対複数のオブジェクト クラスターの割り当て。各オブジェクトを、しきい値よりも高いメンバーシップを持つクラスターに割り当てます。

FLAMEにおける最適化問題

ファジー メンバーシップのローカル/近傍近似は、次のように定義されるローカル/近傍近似誤差 (LAE/NAE) を最小化する手順です。

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

ここで、 はすべてのタイプ 3 オブジェクトのセット、はオブジェクト のファジー メンバーシップ ベクトル、はの最近傍のセット、 は最近傍の相対的な近さを反映する係数です。 ${\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\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}=1}$

NAE は、次の線形方程式を解くことによって最小化できます。この線形方程式は、値が 0 である NAE の唯一のグローバル最小値である唯一の解を持ちます。

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

ここで、CSOの数に1を加えた数（外れ値グループの場合）です。これらの線形方程式を解くには、以下の反復手順を使用できます。 ${\displaystyle M}$

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

2次元テストデータセットの簡単な図解

参照

• データクラスタリング
• ファジークラスタリング

外部リンク

• BMCバイオインフォマティクス（2007）：FLAME、DNAマイクロアレイデータの解析のための新しいファジークラスタリング手法
• FLAMEのCソースコードはGoogleCodeでFreeBSDライクなライセンスの下で公開されています