Clustering タグのついた記事一覧 - 京の路

一昨年の今日のブログ。

「英語論文を読んでます」

多目的クラスタリングの論文を調査しだした頃ですね。
クラスタリングとかデータマインングとかの本を読んで、ようやく英語の論文を読み始めたころ、だったかな？

で、去年のブログがこれ。

「GECCO受かった♪」
「GECCOのThe Best Paper Award、凄いっぽいぞ。」

多目的クラスタリングの論文が、GA関連で最大の国際学会に通って、ベストペーパーにまでノミネートされたってメールが来たのが去年の今日でした。

１年間でここまでいけたってのは、我ながらすごいと思う。
まぁそんな大したことしてないねんけど、テーマが良かったね。タイムリーで。

今年もこの時期は、某研究室でも誰かが英語論文を調査しだしたり、卒業を前に国際学会通ったりしてるんだろうか？

Read more Comments Retweet

データマイニング技術をスパムブログ検出に用いる事例が増えているのでしょうか？

今週は２度もそういったビジネスの話を聞く機会がありました。僕も大学院でデータマイニングの研究をかじったので、ちょっと親近感が沸きました。

僕がやってたのは単純な数値データのクラスタリングなので、テキストタイプのデータマイニングはあまりよく知りませんが、話を聞いた感じだと

1. 大量のテキストデータから似ている部分を探し出し
2. それらに類似度を付けた上でグルーピング化し
3. 一定の閾値を超えたものをスパムとする

という感じなのかな？

Read more Comments Retweet

修論5ページ進んだぜぃ！！
現在7ページで、あと1.5〜2ページくらいでMOCKの説明は終わる予定。

決してワザと理解できないように書いてる訳では無いけど、なかなかに訳の分からなさが漂う文章です。
まずクラスタとエッジの"interestingness"とかが意味分からんやろな。

明日はIGAの実験のため研究室に行きます。
研究室メンバーからも「良いお年を」と言われる回数が増えてますが、まだまだみんな来てますね（w

Comments Retweet

正しい綴りはgecko。

というわけで、Genetic and Evolutionary Computation Conference: GECCO 2007の論文をひとまず書き上げた。

まだ7ページだけど。
まだ自分でも通して読んでないけど。
まだ誰にもチェックもらってないけど。

明日先生に提出、できるかなぁ〜？

Read more Comments Retweet

12/12-13の間、OPTIS 2006（第7回最適化シンポジウム）に参加してきます。
先日のD&S2006と同じ日本機会学会の系列です。

発表題目は「多目的遺伝的アルゴリズムによる多目的クラスタリング」で、会場は淡路夢舞台国際会議場。（今年のOPTISは温泉じゃありません）

今週の木曜日には研究室内リハーサルが行われるため、そろそろパワポも作り上げないといけません。
で、とりあえず...

Read more Comments Retweet

ちゃんとやってるよ〜ってのをアピール。

VIENNAってやつが強敵だ。突然変異しかしないのだが、これはGAなのだろうか？
こいつが紹介されてる（おそらく最初で最後の）論文にパレートの図が無いので、どんなパレートが得られているのかが不明。クラスタ数はおそらく固定だから、あんまりパレート形状が出てこなさそうなんだけどなぁ〜
あと、「random Voronoi cell」がよくわかんない。某ドクターが昔ボロノイボロノイって言ってた気がするが。

まぁでもイメージとしては、MOCKが凝集法をベースにK-means法で香り付けした感じなのに対して、VIENNAはK-means法をベースに凝集法で味付けした感じ。

Read more Comments Retweet

Optisに向けて何をしていくか考えないと。

おそらく方向は２つで、
　１．クラスタ数自動決定アルゴリズムの改良
　２．実際にWebデータのクラスタリングをしてみる
のどちらかだと思うのだけど、現状ではセッション／クッキーごとのログを取る仕組みがこちらには無いので、２はちょっと難しいのだと思っている。
だとすると１を突き詰めていく方向だとは思うのだが、まだ具体的なアイディアは無い。

２次元でもクラスタリングできてなかったテストデータは、５次元でも解けなかったしなぁ〜
てか完全に重なっている２つのクラスタが存在するテストデータって。。

Long2をベースにして、テストデータを自分で作ってみる？？

Comments Retweet

多目的最適化は無視。
多目的遺伝的アルゴリズムも無視。
がしかし、スライドは35枚。
今はかったら20分かかってたので、まずはこれを15分にしなければ。

でも、今の内容じゃ伝わんないだろうなぁ〜。。
月曜日pinkさんにいじめてもらおう。

Comments Retweet

ヒューリスティックバイアスについて、表現型／遺伝子型のパターン数とクラスタ数／データ数との関連を図示されていて、そこからバイアスが読み取れるよってなことが書いてあるのだが、さっぱり意味不明。

第二種のスターリング数（Stirling number of the second kind）というのがあるらしい。

具象数学初級：スターリング数と冪和公式

なんかスターリング数でググッてたらPythonとHaskelの資料が出て来たんだが、これを知ってればプログラムが楽しくなるのだろうか？

ちょっと勉強してみる。

Comments Retweet

いまMOCKで一番ネックになりそうなのが、初期化時に全データを含む最小全域木を作るところです。最小全域木の生成アルゴリズムはいくつかあって、データ数（というかリンク数？）Nに対してO(NlogN)で最小全域木を作れるといわれているのだけど、どれも扱うリンクが最初から分かっているという想定なのです。でも実際には各データ間のリンクの重みを求めるのもそれをメモリにのせるのもO(N^2)で大変。特に大規模データではメモリ量が半端じゃない（double型ならN×N×8 [Byte]）。データ数に線形なメモリ量で（つまりすべてのデータ間のリンクを考えないで）、高速に最小全域木を作れるアルゴリズムが知りたかった。もしかしたらこの文献はビンゴかもしれない。

A Linear Algorithm for Analysis of Minimum Spanning and Shortest Path Trees of Planar Graphs

Read more Comments Retweet

いままでSPEA2+をベースにしてMOCKを開発してたのだけれど、別に+な部分は全然使ってなかったのです。そんな中なんといつの間にかSPEA2が公開されていて、しかも最近SPEA2+とSPEA2どちらもバージョンアップしてるじゃないですか！！

これを機にSPEA2にして、MOCKのための追加部分をプラグイン化して、どうしても本体部分をいじらないといけないところはパッチファイルを用意して...とかしておこうかな。

Read more Comments Retweet

ひとまず完成。MOCKのアルゴリズム自体は変えず、所持するデータと初期化時の最小全域木生成アルゴリズムを変更しました。ただし実行時間とデータ量を両方ともに減らすため、最小全域木の代わりに「準最小全域木」的なものを作り、さらにデータによっては最小全域木を作成できずにエラーになるという仕様なのですが。

メモリ使用量の面では、13,000データで100MB、26,000データで200MBというメモリ使用量になっており、データ数Nに対してO(N)にすることができました。

実行時間の面では、初期化には（おそらく必須の）O(N^2)の処理が含まれているのですが、いままでよりはかなり高速になりました。いままで自身に近いものから順に自身以外のデータのIDをならべた配列をすべてのデータについて作っており、そこでO(N^2*logN)のコストがかかっていたのですが、これをTop M個（Mはパラメータ）だけしか計測しないようにしてO(N*logN)にしたので。13,000個のデータで45分くらいかかってたのが、これが数分で終わるようになりました。ただし距離情報はいっさい持たないことにしたので、GAの評価部分は処理が数倍おそくなりました。まぁでもオーダーはO(N)でかわらないので大丈夫でしょう。

Read more Comments Retweet

なかなかいいんでないかい？
85点てとこかな。

テスト問題：Square1
データサイズ：13,000
クラスタ数：13

Comments Retweet

月曜日の昼から走らしてるMOCKが、まだ１試行目の第１世代！？
プログラム見直しや。。。

Comments Retweet

2次元なら13,000データまで、スワップ起こさずに扱えるようになった。実行時間は数時間程度。そして大部分が初期化処理に費やされている。全体が1時間だったら50分くらい初期化かな？

Square1というk-meansで最も解きやすいテスト問題を、1,000データから13,000データにして、クラスタ数を2から13に増やして実験してみたところ、性能は落ちるものの全く解けなくなることは無いかなという感触。

実行時間は初期化以外はちゃんとO(N)で行けてるので、問題は

• 初期化時のO(N^2)の処理
• メモリー容量

初期化部分は総当たりの距離計算とソート処理なので、少なくとも距離計算は並列化できそう。あとは並列化で使えるメモリーを増やしてやりさえすれば、SuperNova全部のメモリー使って大体130,000データは扱えるかなと。最悪距離計算の結果を配列で持たずに適時計算してやれば、それだけでメモリー制約からは解放される。計算時間がものすごい増えそうだけど。。。

Read more Comments Retweet

現在のプログラムだと、8,000件の2次元データを処理するために、初期化で30分以上かかる。
そして初期化が終わると5分くらい。
データの書き出しにまた5分くらい。

10,000件だと1時間経っても初期化が終わらない。

原因ははっきりしていて、MST生成時にO(N^2)のコストをかけているから。
Primのアルゴリズムを使うとO(NlogN)までコストが下がるらしいので、勉強してみるか。。。

あと10,000件で1.5GBメモリを食うので、そしてメモリはN^2に比例するので、100,000件のデータを処理する為には150GBのメモリが必要。
DBに退避させる（クラスタにDBが必要）か、距離は適宜計算する（「現在の計算コスト*世代数*個体数」分の計算コストがかかる。今1時間かかってるとしたら、ざっと計算して1[hours]*200[generations]*50[solutions]=10,000[hours]かかる。10,000[hours]⇒1年以上）か。。。

まぁ確実に前者な訳だけど、だとすると500,000件のデータを扱うためにはDB用にHDDが3.75TB必要。

マジ？
Googleさんって1億以上のサイトをどうやって処理してるの？？
1億って10,000の10,000倍...2次元の実数値データでも...150PB！？
GridとかHPCとかの次元でなんとかなるもんなの？？？

Read more Comments Retweet

【文献調査】Improvements to the scalability of multiobjective clustering

Abstract

本報告ではImprovements to the scalability of multiobjective clustering[1]の調査結果を述べた。調査文献でHandlらはMOCKのデータサイズやデータの次元数に対するスケーラビリティを向上させるために、新たな初期化と突然変異、最良解を唯一に決定するために用いるランダムデータの生成法を提案している。またデータサイズ、データの次元共に大きなテスト問題を用意するため、テストデータ生成方法についても述べ、それらのテストデータを用いた実験を通して従来の単目的クラスタリング手法との性能比較を行っている。本報告では新たに提案されたオペレータとテストデータ生成方法についてまとめた。

細かいとこも読んだよ。読んだけどさ...

Read more Comments Retweet

研究ミーティングにて自分の研究について発表した。で、そこでいろいろ議論してて、大切な論文を忘れてたことに気づく。

そうそう、これザーッとしか読んで無かったんだ。こいつをきちんと深くまで読まないと、進む先が決められないじゃないか！！

Improvements to the scalability of multiobjective clustering

Read more Comments Retweet

データをSOMにかけて２次元にマッピングしたあとでMOCKでクラスタリングをしようとしたけれど、SOMのマッピングは空間にほぼ均等にデータをばらまいてしまうようです。これじゃMOCKにはかけられない。

というか、そもそもSOMってよほど頑張らないと順序尺度しか扱えないんじゃないかな。２次元にマッピングできるというところが面白いところなだけで、今回狙っていたような動作はしないっぽいね。そしてMOCKはデータアイテム間の距離さえ分かればクラスタリングできるし。

Read more Comments Retweet

いままでは3列目にクラスタIDを出力していたので、おバカなエクセルではクラスタリング結果のグラフを描くのが超めんどくさかったのだが、今日すばらしい方法を発見♪

一番上の行は一番左のセルを空白にして、その次からクラスタID（ex. Cluster 1, Cluster 2, ...）を書いておく。
2行目からはデータの値を出力するわけだが、ここでX軸のデータを一番左に、Y軸のデータはその次の列からクラスタ事に列を変えて出力する。

プログラムの出力形式をこういう形にしておけば、エクセルを開いて全選択=>散布図作成とするだけでクラスタリング結果が出力される。

実際のエクセルファイル

俺天才♪

Comments Retweet