Title

バンプ探索とその応用

Authors

行實隆広

Source

九州工業大学大学院情報工学研究院情報科学博士論文（情報工学、情工博甲第２２０号）, pp. 1-100 (2009.1.21)

Abstract

p個の特徴量を持つn個のデータをk個のクラスに分類する問題はこれまで広く研究されている。このとき、分類されたクラス内ではそのクラスに属さないデータができるだけ排除されるような方法を用いてきた。しかし、顧客データなどの実際のデータでは、どのように分類しても排除できないようなクラスが存在することがある。例えば、p次元空間において一様分布のように分布しているクラスが存在することがある。このとき、興味あるクラスを取り出すには従来の枠組みとは異なった方法が必要になる。そこで、p次元空間の中で興味あるクラスのデータが他のクラスよりも多くなるような領域を見つけることを考える。このような領域をバンプ領域と言い、この領域の境界を見つけることをバンプ探索と言う。本研究はこのバンプ探索についての研究である。
　バンプ領域を狭くすれば、興味あるクラスのデータは他の領域に比べて濃くなるが、領域内での興味あるクラスのデータの獲得数の全体に対する比は小さくなる。つまり、濃さ（pureness rateと言う）とこの獲得数の比（capture rateと言う）との間にはトレードオフの関係がある。本研究の第一の目的はこのトレードオフ曲線を作ることである。
　pureness rateを指定すれば、バンプ境界はp次元空間内で自由曲面をなすように形成されるが、それは一意には定まらない。また、自由曲面をそのまま解釈するのは容易ではない。ここでは、バンプ境界をルールとして解釈しやすくすることを重用視して、境界がp次元空間内の軸に平行になるような場合を考えた。こうすれば、if-then-ruleを使うことができ、決定木のような方法を使うことができる。ここでバンプ探索に決定木を用いる。
　従来の決定木では、元のグループでのエントロピーよりも分類した後の複数のグループでのエントロピーが小さくなるように、木の根から枝葉に向かって順に、分類が行われて行き、作られた木は一意に定まる。末端の葉では特定のクラスのデータが多く含まれるようになる。しかし、上のようなバンプ探索の場合、木の根から順に木を大きくしていっても、pureness rateが一定値以上になる節や葉でのcapture rateの和は大きいとは限らない。どの特徴量を木の節の分岐点に選ぶかでcapture rateの和が変わってくる。
そこで木を作る際には、木の全体像を形成した上で、木の節に置く特徴量をランダムに与え、分岐点は節の上下でのエントロピーの差が最大になるように決め、すべてのcapture rateの和の中で最大になるような木を作ることで、バンプ探索がなされたと解釈する。このことを効率的に行うために、節に置く特徴量の選定を遺伝的アルゴリズム（GA）を用いて行う。木特有のGAになるため、通常の交叉法などの進化法にも、特有な方法を用いた。これを、tree-GAと呼ぶ。
　tree-GAでは良いインヘリタンスを保つことを考えると、木は初期の状態から比較的近い範囲の種類の木の中での最適値に収束する性質を持つため、収束値は局所解となる傾向が強い。そこで、多くの初期値を用意しておき、得られた多くの局所解から、大域解に近い値を極値統計によって推定することを考える。ここでは、極値分布としGumbel分布を用いた。こうすることで、大域解でのルールは得られないが、使用するルールで得られるcapture rateがどの程度離れているかを知りながらルールを使うことができる点で、この方法はこれまでのGAにはない特徴を持つ。
　以上は、すべて教師データを用いたときでの最適なバンプ探索法であった。トレードオフ曲線が新規に得られるデータでも同じように機能するためには、テストデータを用いたトレードオフ曲線の評価が必要になってくる。そこで、tree-GAで木を進化させる際に、進化の段階で評価データを用いることにした。こうすることによって、収束段階での木が局所解を持つ性質が保たれるからである。また、最終段階での木の評価にはテストデータを用いて、テストデータとしての機能を持たせている。これを、new tree-GAと呼ぶ。つまり本研究では、サンプルされたデータを、教師、評価、テストの3つのグループにランダムに分け、実際に適用可能な最適なトレードオフ曲線をこれらによって求め、また、その大域解としてのトレードオフ曲線を極値分布を用いて推定し、適用可能なルールで得られるcapture rateが最適値からどの程度離れているかを知りながらこのルールを適用することができるという手法を提案した。
　この方法の妥当性については、シミュレーションデータにより確認を行い、また、有効性については、実データ（サンプル数n=20万件、特徴量数p=50、クラス数k=2）について確認を行っている。

Key Words

Citation

Times Cited in Web of Science:

Times Cited in Google Scholar:

Cited in Books:

Inspec:

WoS: