[B! clustering] FLAB_SUMIのブックマーク

SpectralClustering - PukiWiki

2018-01-09 FSH2007ST6/BarCode 2016-08-09 論理と計算 2014-11-17 (ymken)/Keplar Conjecture 2014-10-20 MenuBar 2014-08-28 Seminar/20140901 2014-07-09 RecentDeleted Seminar 2014-07-03 Sminar/20140905 2013-10-15 Seminar/20131026 2013-10-08 (ymken)/卒業レポート

FLAB_SUMI 2009/08/06

clustering

リンク

駆け足で読むRで学ぶクラスタ解析第７章　スペクトラルクラスタリンググラフ分割としてのクラスタリング - ryamadaの遺伝学・遺伝統計学メモ

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

FLAB_SUMI 2009/08/06

clustering

リンク

Garbage: 論文#5

長らく放置していたことに気づいたところで，最近勉強中のSpectral Clusteringについて簡単にまとめてみる． Spectral Clustering というのは簡単にいえばグラフの分割問題．あるグラフがあたえられたとき，出来るだけ少ないリンクを切っていくつかの密なサブグラフへと分割する．リンクを切る際のコストとして，Ncutと言う基準がある．グラフをA,Bという2つのサブグラフに分けるとき， Ncut(A, B) = cut(A, B) / d(A) + cut(A, B) / d(B) ここで，cut(A, B)はAに含まれるノードとBに含まれるノードを結ぶリンクの重みの総和． d(A)はAに含まれるノードと接続しているリンクの重みの総和．このNcutを最小にするようなA, Bが最良の分割となる． Ncutを最小にするような分割を求めるには，可能なすべて

FLAB_SUMI 2009/08/05

clustering

リンク

スペクトラルクラスタリングは次元圧縮しながらKmeansする手法 - 武蔵野日記

機械学習系のエントリを続けて書いてみる。クラスタリングについて知らない人は以下のエントリ読んでもちんぷんかんぷんだと思うので、クラスタリングという概念については知っているものとする。それで、今日はスペクトラルクラスタリングの話。自然言語処理以外でも利用されているが、これはグラフのスペクトルに基づくクラスタリングの手法で、半教師あり学習への拡張がやりやすいのが利点。なにをするかというとクラスタリングをグラフの分割問題(疎であるエッジをカット)に帰着して解く手法で、どういうふうに分割するかによって Normalized cut (Ncut) とか Min-max cut (Mcut) とかいろいろある。完全にグラフが分割できる場合はこれでめでたしめでたしなのだが、実世界のグラフはそんな簡単に切れないことが往々にしてある。それで近似してこのグラフ分割問題を解くのだが、Normalized c