2007-02-11
_ [研究] 講演内容を詳しく紹介していただきました
先日風間さんに呼ばれて研究会で講演をしましたが、そのときの様子を風間さんが紹介してくださっています。大変詳細で感動しました。ありがたいことです。風間さんどうもありがとうございます。
Cafe Babe - 招待講演「大規模Webアーカイブの時空間分析とその実際」
これを見たょゎさんという方が、WWW2006で発表した論文を読んでくださったようで、概要を紹介して頂きました。ちょっとご期待からは外れていたようですが、なにかヒントにはなりそうとの感想を頂きました。これもまた大変ありがたいことです。つまんねーとか書かれなくてよかったあ。
READMEと日記の書き方
クラスタリングについて研究していますしましまです<br>Cafe Babe さんのところにコメントをつけさせていただいたのですが，Cafe Babe さんの以下の一文に該当する資料がどれかお教えいただけませんでしょうか？<br>--- Cafe Babe さんのところにつけさせていただいたコメント ---<br>> Webコミュニティチャートの生成で，私……<br>の一文ですが，プレゼン資料に該当するページを見つけることができませんでした．どのページにあたるかお教えいただけますか？<br>クラスタリングで三角形構造だとDelaunay三角形分割とかが思い浮かびますすが，そういったものでしょうか？
しましまさま、コメントありがとうございます。プレゼン資料だと6から7ページ目にあたります。Hypertext2001で発表したものです。クラスタリングと言うのはおこがましいような単純な手法で、どちらかというとグラフの分割に当たります。辺を共有する三角形の集合を塊として抽出することで、グラフ中の密な部分(クリークよりは薄い、1連結よりは濃い)を取り出しています。これでお答えになっておりますでしょうか。
しましまさんの質問に続けて、ぼくも風間さんのブログに書き込んでしまいました。同じ質問になりますが：クラスタリングのときもページ単位で行っているんですか？つまり、アルゴリズム的に百億ノードに対するクラスタリングを行っているのか、あるいはなんたかの塊(サイト？)にまとめてからクラスタリングしているのかを知りたいのですが。
基本的にはページ単位です。ただし最初に、被リンク数が一定以上というフィルタをかまして、1千万ページ程度に絞り込んでいます。で、それを100万程度のクラスタに分割しているというような形です。
そうなんですか。一千万ノードなら、ぼくらのシステムでも処理できそうな気がします。Newman のアルゴリズムにちょっと手を加えた方法で、最高速の(やや精度の劣る)バージョンだと 400万ノードで 35 分でした。いま、さらに高速化を図った新しいバージョンを実装中です。1000万ノードなら2時間以内にいけるんじゃないかな。
あ、クラスタリング対象ページは1千万に絞るんですが、実際にページ間の関連度を計算する際には、元の数十億ノード・エッジグラフを局所的に参照するという方法になっています。ちょっとややこしいですね。でもそのスピードなら、サイトに縮約したグラフなら結構いけそうな気がします。Newmanのアルゴリズムは、質の良いコミュニティが出てきそうでしょうか？
お返事どうもありがとうございます．<br>こちらの情報で，ほぼ分かりました．
ありがとうございます。ウェブのデータを持っていないので、試したことがないんですが、グローバルな指標を使った最適化なのでどんな結果がでるのか試してみたいところです。
サイトグラフのデータはあるので試してみます？今度、適当に勉強会でもやりましょうか。ご興味ありましたら連絡ください。
ありがとうございます。来週から少し暇ができますので、是非、お願いします。
ちょっと分りにくかったですね。勉強会のことです。1千万の解析については勉強会でお話しすることにします。まだ、完成していないのですが、CPU というよりはメモリ効率の改善をしています。そちらの機械だったらすぐに動いてしまうかもしれませんけど。
いつも思うんですが、そういうでかいデータを扱うシステムを組む場合、プログラムのテストってどうやるのでしょうか？テストのoracle(「正しい値」の根拠…かな？)として何を使ってどうやってテストデータを作成しているのか教えて下さいまし。<br><br>ちなみにおいらの場合だと、oracleは自分で考えた計算モデルです。(それを考える事自体が研究の一部だったんですが)解析対象がJavaプログラムなので色々なパターンのコードを書いてみて「処理前」と「処理後」をしこしこ手で並べたものがテストデータです。<br><br>たかがJavaプログラムの解析ツールでもテストデータを作るのが結構面倒臭いです。ひょっとしたらコーディングそのものよりも辛いかも。oracleもテストデータも他人が作ってくれたものがあればそれを流用するというのも有りだと思いますけどね、というかそうしたいです。
クラスタリングの場合、アルゴリズムの特徴によってまるで異なるクラスタリングが提示されるので、普通の意味でのテスティングができないです。テストデータを共有することはできても、それに対する正解を与えることはできないので困ります。
kwakitaさんじゃまたあとでちょっと、日程調整をお願いします。<br>マイニングのプログラムだとやはりカチッとしたテストをするのは難しいですね。もっぱらサンプリング＆経験＆念力に頼っています。
そっちの方で面白いネタがあったらなあ、とちらっと思ったりしましたが、やはり難しいですか。結局、本質的に smoke testing 以上の事は出来なさそうですよね。どうも御回答有り難うございました。