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

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