本論文は8章から構成される。1章においては、研究の動機を示し、2章では、情報幾何とクラスタリング問題の概要を提示し、3章では、特徴多様体という枠組の提案とその応用例を示し、4章では、クラスタリング問題の持つ幾何的性質を解析した。5章では、計算量を評価し、6章では、アルゴリズムを提案した。7章では、実験および応用例を示し、8章では、結論を野別。 類似度に応じてオブジェクトをいくつかのグループに分類するクラスタリング問題は統計学の古典的な問題であり,医学,生物学,人類学,経済学,情報科学等様々な分野で実際に幅広く活用されている. その応用によってさまざまな種類の異なるクラスタリング問題が提示されてきているがこれらはすべて各オブジェクト間の類似度に基づいた評価関数に関する離散最適化問題と考えることができる.この類似度の定義方法により問題の背後には良い性質を持つ幾何構造が潜んでいる場合が非常に多い.たとえば各オブジェクトがd個の数値属性として表現されている場合,各オブジェクトを特徴空間と呼ばれるd次元空間の点とみなし,二つのオブジェクト間の類似度を該当する二点間のユークリッド距離の関数,あるいは二つのベクトルのなす角度の三角関数の関数,あるいは二点間のカルバックライブラーダイバージェンスの関数等として幾何的に定義することが一般には行なわれている.しかしいったん二つのオブジェクト間の類似度を定義された後は問題の持つ幾何構造が意識されることは稀でありたとえばn点の二分割の総数はO(2n)個あるのに対しd次元n点の線形二分割の総数はたかだかO(nd)個であるといった幾何的に良い性質が問題の解法に利用される例は少ない.また類似度の定義方法および評価基準の違いによりそれぞれの問題がまったく別個のものとして取り扱われていることが多い. 本研究は、クラスタリング問題を、d次元多様体の分割問題と捉え,幾何的な良い性質を利用しながら包括的かつ統一的に扱うための枠組を提示しこの枠組の中で問題の持つ幾何構造を利用しながらクラスタリング問題を扱ったものである。問題が本質的に持つ複雑度の解析を行ない厳密解法および近似解法の提案を行なった。また上にあげた個別の問題を我々の提案する枠組の中の一例として取り扱うことによりより詳細な解析および実験実装例を示した. 具体的にはパラメタが構成する空間のうち双対平坦(Dually Flat)という良い微分幾何構造を持つものを特徴多様体(Feature Manifold)と定義しそこで定義される不変量である一般形ダイバージェンスを類似度とする加算的評価関数を持つn点k-クラスタリング問題を研究した. 双対平坦な多様体上には二つの平坦な接続とそれに対応する二つのアファイン座標系が存在し,特殊ケースとして自己双対な構造を持つユークリッド空間や指数型分布族のパラメタが張る空間を含むことが知られている.特に指数型分布族に関しては最尤推定量が一つのアファイン座標系における重心に対応するという統計的意味のある幾何的な性質が知られている.まず既存のモデルおよびいくつかのクラスタリング問題を例にとりそれぞれの問題が特徴多様体という微分幾何的な枠組の中でその幾何構造を利用しながら統一的に取り扱えることを示した. 特徴多様体上で定義される一般形ダイバージェンスは,測地線の積分として定義される距離とは異なり数値的に計算することが可能であり,関連するアファイン座標系でポテンシャル関数およびその接平面を考えることにより線形化可能であるという特徴を持っている.またその特殊ケースとしてユークリッド二乗距離,カルバックライブラーダイバージェンス,ヘリンジャー距離等を含んでいる.ダイバージェンスの線形化可能という性質を利用することによりダイバージェンスによるボロノイ図が構成できることが知られているが本論文では,これをダイバージェンスに重みづきボロノイ図に拡張しダイバージェンスによる加算的評価基準を持つクラスタリング問題の最適解が重みづきボロノイダイアグラムで特徴づけられることを示した.次にn点のダイバージェンスボロノイ分割のプライマリーシャッター関数を評価することによりこの問題の持つ本質的な複雑度の評価を行なう.この結果に基づきO(nO(kd))時間の厳密解法を示した後いくつかの近似解法を提案した.まず比較的小さいkについて代表点制限つきの問題がO(nk)時間で厳密に解けることを利用した近似解法を示しそのうち近似比が抑えられる特殊ケースを示す.次に再帰的に階層化クラスタリングを構成するためのO(dn log n)時間の軸鉛直クラスタリング法およびランダム抽出技法を用いた確率的近似解法を提案した.この確率的近似解法は抽出点数をmとした時O(mO(kd)n)時間アルゴリズムであり近似比はnとは関係ないmの関数として抑えられている,すなわち理論的には元々の問題のサイズがいかに大きくなってもある精度を満たすために必要な抽出点数は変わらずその結果問題を解くのに必要な時間は問題のサイズに対して線形にしか増えないということが言える. 次にこれらの解法によって得られるk-clusteringを初期解とする局所改良法の適用を行なった.最後に実験を行ない確率的近似アルゴリズムについて抽出点数と解の精度の関係が理論的な結果が実験により裏付けられることを示しまた局所改良法が有効であることを示した。最後に実際の適用例として色量子化問題への応用例を与えた. なお、本論文の内容は、今井浩と共著であり、6章の一部と7章は加藤直樹と共著、3章、4章、6章は定兼邦彦と共著であるが、論文提出者が主体となって提案、設計、実装、分析を行ったもので、論文提出者の寄与が充分であると判断する。 したがって、博士(理学)を授与できると認める。 |