駆け足で読むRで学ぶクラスタ解析 第7章 スペクトラルクラスタリング グラフ分割としてのクラスタリング

  • データをグラフのノードとし、データ間の類似度をエッジで表現する。このとき、クラスタリングは、グラフからエッジを取り去り(cut)、いくつかの部分グラフに分ける作業にあたる。クラスタリングの評価は、取り去るエッジが少なく、残った部分グラフが密であることを基本とする
  • 評価関数
    • 部分グラフへの分割のよしあしを評価する関数
      • Mcut
      • Ncut
    • 評価関数の最適(近似)解は、固有値問題を解くことであることが知られていることから、以下で説明を加える、評価関数は、固有値問題に変換できる
    • 部分グラフ間の類似度の定義
      • W(A,B)=\sum_{a\in A,b\in B} sim(a,b)
        • sim(a,b)は、エッジに類似度を与えているとすれば、部分グラフAとBとの間を結ぶエッジの値の総和になる
      • AとBとに分けるようなcut(エッジの取り去り)によって、消失する類似度をcut(A,B)と表し、部分グラフA内の類似度をW(A)=W(A,A)と表すこととすると、Mcut,Ncutは次のように定義される
    • Mcut=\frac{cut(A,B)}{W(A)}+\frac{cut(A,B)}{W(B)}
    • Ncut
    • Ncut=\frac{cut(A,B)}{d_A}+\frac{cut(A,B)}{d_B}
    • d_Aは、次のように定める
      • ある要素と、それ以外のすべての要素との間の類似度の総和を、A,Bへの分割にあたって、Aに分類される要素についてのそれを足し合わせたもの