2011年11月17日木曜日
2011年11月4日金曜日
クラスタリングメモ、続き
*Parallel Incremental Graph Partitioning, Chao-Wei Ou and Sanjay Ranka, Member, IEEE
線形計画法(LP)によるインクリメンタルグラフパーティショニング
(古い論文 : Parallel Incremental Graph Partitioning Using Linear Programming)
===
実装・実験するもの
・Full SC (k=2)
・Incremental SC (k=2)
(・Incremental Partitioning with LP (k=2, 3, ...) : 実装間に合わないと思う)
実行時間、収束回数
分割結果の評価(頂点コスト、通信コストを評価する?)
(Incremental Partitioning with LPで、初期分割はどうするか?)
クロネッカーグラフ
頂点重み(1)と辺重み(1?)は固定
===
以下を並行して行っていく
・SC, Incremental SCの実装に関するppt作成、ラフに
→11月中旬、下旬まで
・実装
→12月上旬、中旬まで
・実験
→12月内に
===
他の参考文献・URL
glaros.dtc.umn.edu/gkhome/publications/gp
METISとか
www.sciencedirect.com/science/article/pii/S1574013707000020
Glaph Clustering, サーベイ論文
2011年10月19日水曜日
クラスタリングメモ
辺の追加・更新→類似度行列の拡大・更新
更新される要素 : w_{i,j} ( = w_{j,i} )
類似度行列を拡大するとき、要素の初期値は0
スペクトラルクラスタリングは必ずしもグラフを対象をしたクラスタリング手法ではないが、
全頂点対間の類似度を類似度行列として扱っているので、
類似度行列をグラフの隣接行列とみなせばグラフにも使える、ということかな?
他のグラフクラスタリング手法について調査
===
Incremental Spectral Clustering With Application to Monitoring of Evolving Blog Communities
関連研究よりメモ
[14]Ng et al. On spectral clustering: Analysis and an algorithm.
マルチウェイ(k=3クラスタ以上)のクラスタリング手法。
固有値の小さいものから順にk個固有ベクトルを取り出して(k次元の特徴量を抽出して)
n×k行列を作成。各行を頂点の値としてk-meansなどでクラスタリング。
Spectral Clustering以外のIncremental Methodsについて
[9]Gupta et al. A single pass generalized incremental algorithm for clustering.
ストリームは辺じゃなくて頂点、というかそもそもグラフが対象じゃない。
クラスタ中心と追加された頂点との比較ができないといけないので。
[8]k-medoids?頂点ストリームが対象?
[2]これも距離空間上の頂点ストリームが対象
[4][11]PageRankの話
===
遺伝的アルゴリズムを使ったグラフ分割
2011年10月4日火曜日
2011年8月3日水曜日
ぱーてぃしょにんぐ、しらべもの
Spectral Clusteringについて
Data Similarity Graphというグラフを定義し、そのグラフを対象とした話。
他のGraph Partitioningアルゴリズムを考えるべきかも。
勘違いしてるかも。
参考文献、URL
・d.hatena.ne.jp/mamoruk/20090128/p1
・Qianjun Xu, Marie desJardins and Kiri L. Wagstaff. Active Constrained Clustering by Examining Spectral Eigenvectors. Proc of Discovery Science 2005.
・・(2章)
登録:
投稿 (Atom)