本報告ではImprovements to the scalability of multiobjective clustering[1]の調査結果を述べる。調査文献でHandlらはMOCKのデータサイズやデータの次元数に対するスケーラビリティを向上させるために、新たな初期化と突然変異、最良解を唯一に決定するために用いるランダムデータの生成法を提案している。またデータサイズ、データの次元共に大きなテスト問題を用意するため、テストデータ生成方法についても述べ、それらのテストデータを用いた実験を通して従来の単目的クラスタリング手法との性能比較を行っている。本報告では新たに提案されたオペレータとテストデータ生成方法についてまとめる。
従来よりMOCKでは、個体レベルでは各個体を最小全域木（MST）に基づいて生成し、近接したデータが同じクラスタに含まれやすくしていた。またクラスタレベルでは、MSTの中から長いリンクを取り除くことで生成されるクラスタは、凝集法に近い性質を示した。これらの性質によりMOCKでは質の高い初期個体を得ることが可能であった。
しかしながら凝集法の欠点である、著しく孤立したクラスタが他のクラスタから隔離され、多くの個体が非常に似通ったものになるという現象を引き起こした。この問題を解決するため、新たな初期化手法を導入する。新初期化手法は凝集法よりパレート最適解フロントに沿った個体集合を生成することができる手法として、k-means法を用いる。新手法はMSTとk-meansを組み合わせることにより、従来よりもより良い初期個体集合を形成する。
凝集法のデメリットを解決するため、我々はinterestingnessという指標を定義し、そのリンクを取り除いたら外れ値の分離を引き起こす"un-interesting"なリンクとそのリンクを取り除いたら異なるクラスタ形状を生じる"interesting"なリンクとに分けることにする。
定義1.1 i→jへのリンクがinterestingであるとは、以下の事を示す。 iがjの近傍範囲内l番目に存在し、かつiがjの近傍範囲内k番目に存在し、 l>L、k>Lである。（Lは近傍データ数パラメータ） interestingnessの値はd=min(l,k)である。
定義1.2 クラスタリングソリューションCがinterestingであるとは、以下の事を示す。 CはMSTからinterestingなリンクのみを取り除くことで生成される。
与えられたデータセットに対して、 interestingなMSTに基づくソリューションは以下の手順で生成される。
次にk-meansソリューションの生成を考える。このスキームでは、あらかじめk-means法を異なるkについてそれぞれ10試行程度繰り返しておく。（kは[2,fsize-(min(I,0.5*fsize)+1)]の範囲内）k-meansの結果はMSTベースの遺伝子表現に変換される。このステップでMSTで得られた情報を高いレベルで保存することにより、アルゴリズムの収束性が大幅に高速になる。ここで注意すべきことは、最終的に得られるクラスタ数は初期個体で決定される事は無く、MSTの内部構造によってクラスタ数は増減することもあるということである。
MOCKの突然変異オペレータでは、あるデータがリンクする候補データの数を限定することにより、探索空間を大幅に削減している。従来の突然変異スキームでは、ある個体の各遺伝子が突然変異を行う確率は1/Nで均等であった。 しかしながら直感的に「長いリンク」は好ましくないと思われる。よってi番目の遺伝子の突然変異率pm_iを以下のようにする。
pm_i= 1/N + (l/N)^2
ここでlはiが突然変異前にリンクしている遺伝子がiから何番目に近いかを示す値である。
従来のMOCKでは（最終的に唯一の最良解を選択する際に用いる）コントロールデータの生成にポワソンモデルを用いており、コントロールデータはデータの定義域内に一様ランダムに生成されていた。この定義域はデータの各次元の最大/最小値により定められていた。しかしながらこのモデルは次元が低い時には有効に働くものの、次元が高くなるにつれ徐々に元のデータの定義域とは外れた場所にデータを生む可能性が高まるものであった。これは従来のモデルでは計測不可能な次元間の関連性により生じる問題である。
そこで本論ではSarleの改良Null Modelを用いることにした。ここでもポワソン分布が用いられるのだが、今回のモデルではデータは主成分空間内にセットされる。具体的には主成分分析によりオリジナルデータの相関マトリクスを生成し、得られた固有ベクトルと固有値を用いて一様分布のデータを生成する。この処理によりデータは固有空間内に生成され、各次元の固有値により各次元での単位ベクトル長が調節される。そうして生成されたデータは元のオリジナル空間の定義域内に再度変換しなおされる。
新アルゴリズムの性能を評価する為、２つのテストデータ生成アルゴリズムを構築した。これらは http://www.dbk.ch.umist.ac.uk/handl/generators/にて公開されている。
最初のジェネレータは多変量正規分布を用いた標準クラスタモデルに基づいている。収束マトリクスは対称性と正数という制約を受けるが、対称性と正数の制約を満たすことは対角成分が正の対角成分のみを持つ対角優位行列により保証される。以下に簡潔に多変量クラスタを定義する。
±y, y=x^2 , x∈[0,1]でyの正負は確率1/2でランダムに決定される。
ここでy=x^2の分布は細長いクラスタの生成に役立つ。
データジェネレータは単純なトライアル-エラースキームに基づいている。クラスタは繰り返し構築され、単純なヒューリスティクスがそれらの間の重なりを検知する。重なったクラスタは取り除かれ、再びその代替クラスタが生成される。この処理は要求を満たすクラスタが生成されるまで繰り返される。
低次元のデータセットではクラスタは高い確率で細く引き伸ばされ、向きもむちゃくちゃである。しかしながら高次元（10次元以上）になるとクラスタの形はより（高次元の）円形に近くなり、中心に沿って整列する。円形に近くなるのは、高次元では１つの次元での大きな差がデータアイテム間のユークリッド距離にほとんど影響しないためである。中心に沿って整列するのは、高次元では収束行列の非対角要素が相対的に対角成分と比較して小さくなるからである。このジェネレータでは円形クラスタの性質が不足するため、我々はもう一つのデータジェネレータを考案した。
このジェネレータでは、任意の方向の主要な軸にそって回転楕円体のクラスタを生成する。クラスタ境界は以下の４つのパラメータで定義される。
各々のクラスタに対して、データアイテムは、主要な軸上の一様ランダムな点からガウス分布に従った距離の場所に、ランダムな方向に生成される。そして境界を越えたデータアイテムは取り除かれる。 すべてのデータアイテムが生成されると、遺伝的アルゴリズムを用いてそれぞれのクラスタの中心点の場所が変換される。これによりoverall deviationの計算コストと重なったクラスタのペナルティが最小化される。
Copyright (C) 2006 Nobukazu Matake, All rights reserved. Copyright (C) 2006 Tomoyuki Hiroyasu, All rights reserved. Copyright (C) 2006 Mitsunori Miki, All rights reserved. No part of this document may be reproduced, copied, distributed, transferred, modified, or transmitted, in any form or by any means, without the prior written permission of the authors. In no event shall the authors be liable for any damages caused in any way out of the use of this document．