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

一昨年の今日のブログ。

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

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

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

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

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

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

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

Read more Comments Retweet

GECCO初日は、SPEA2の開発者であるZitzilerのワークショプを見に行きました。
2時間のワークショップの前半は行けなかったので、Debの話は聞けなかったのですが、Zitzilerの話はEMO業界の動向とか、手法とその評価のまとめみたいな感じでした。
たぶん。

Workshop中、プレゼン資料で気になったところをいくつかメモったので、まとまってないけどとりあえず上げてみます。

Density estimation techniques
    MOGA : Kernel => 物理の万有引力fの強さ？
    SPEA2 : Nearest neighbor => 支配circleの面積
    PAES : Histogram

混雑度計測のテクニックは、大きく3種類にまとめられていました。
やっぱりPAES（PESA-IIのベースになってる手法）って有名らしいです。

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

いま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

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

Abstract

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

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

Read more Comments Retweet

ページ数の制約のせいでしょうが、アルゴリズムの説明に図がありません。
何を意図しているのかよく分からない部分もチラホラ...

...意味不明...

それでもなんとか結論の前まで読み終えた。
10ページの論文で、今日8ページ目の最初のところまで読めたので、あと文章は1ページほど。

直訳すると

VIENNA-mooの性能見積もりの為に用いたF-measureは、最終的に得られた集団に対して最も良い値となる。これは多くのアプリケーションの中で、我々が少数の他のクラスタリング候補をテストできるという我々の持論と直列である。

Read more Comments Retweet