本論文は、最適区間探索の構成的手法に関する研究について述べたものである。

　データの収集方法の大幅な進歩と、記憶装置の劇的な低価格化に伴って、非常に膨大なデータを蓄積することができるようになった。得られたデータをもとに、未来の経営戦略を立てることが、効果的な経営に重要となってきている。このように、膨大なデータ中に潜んでいる有意義な情報を抽出するデ一夕マイニングの理論や技術への需要がここ数年大きくなってきている。これに伴い、データマイニングに対するアルゴリズムの効率化が重要となってきている。本論文には、特に最適区間探索の構成的手法に関する研究を行う。最適区間を効率的に抽出するため、本論文は使いやすい区間クエリー言語を提案して、効率的な実現手法を示す。実装したシステムを喫茶店のPOSデータベースのような現実データを用いてテストした。実験の結果から、本論文提案した手法は高速かつ実用的であることが検証された。

　具体的に、本論文の枠組みと各章の内容を以下に述べる。

　第1章<lntroduction>では、本論文において行う研究の背景と目的について述べている。

　身の回りをみると、いたるところでデータが収集されていることに気がつく。デパートやスーパーマーケット、コンビニエンスストアではPOS端末と呼ばれる機械で、バーコードを読み取って、商品の在庫や顧客層の情報を蓄えている。このようにして蓄積された膨大なデータの中に，大量な有益な情報が潜んでいる。そこでは、この膨大な蓄積データをどのように分析すればよいのかということが課題となっている。そのような膨大なデータの中に潜んでいる規則性を抽出して、有用な情報を見つけ出すことを「データマイニング(data mining)」という。

　本論文の目的はデータに潜んでいる区間情報を抽出することである。例えば、スーパーで売上げた商品量が時刻と共に記録されているものとする。例えば、以下の表といった具合である。各行はある時刻にされた買物の状況を書かれている。例えば、1行目のデータは15時30分になされ、牛乳とパンの買った量である。営業収益を上げるため、どの時間帯で牛乳が売れるのかという情報を得ることは営業者に対して有用である。そうすると、この時間帯で大量な牛乳を用意することできる。例えば、牛乳の売上げ量は平均的に400であり、最小も100以上の時間帯を求める。もちろん、この時間帯はできるだけ長いほうがもうかるので、求めるのは前述の条件を満たす最長の時間帯、即ち、最適の時間区間である。

　現実のデータに対して、一つの区間だけでなく、複数の区間に対する最適区間を求めることが必要となってきている。これは多次元の最適区間である。

　本論文には、上に述べた最適区間(一次元と多次元と共に)問題を目指して研究を行う。最適区間問題とは、簡潔に言えば、「あるデータxが与えられたとき、性質pを満たす最適の部分を求める」という問題である。本論文で解決できる性質pは図1に示された述語である。

　第2章<Range querying language>では、本論文が提案した区間クエリー言語を紹介する。

　最適区間を探索する実例から、最適区間の特徴と使いやすい言語の要素をまとめる。これらを目安として、本論文はR〓Lと呼ばれるSQL風の言語を提案する。実例を通じてその文法と意味を説明する。特に中心としてFINDステートメントと述語(図1を参照)という区間が満たされるべき性質(range property)を論ずる。

　第3章<System overview>では、提案された言語を実装するシステムを概観する。システムの全体像を描く上、この言語を実現するときの核心問題をハイライトする。

　第4章<Compilation>では、最適区間を抽出するための前処理について述べる。この前処理はデータと言語両方に対して行われる。

　最適区間を求めるため、元データは区間に関する属性によって分類されなければならない。この膨大なデータを分類するには、実用的な方法が必要となっている。これで、ある準線形のbucketingアルゴリズムを用いて元データをbucketingする方法を紹介する。これによって、仮にデータを属性Aによって分類すると、bucketingした後のデータには、Aの値域はB1,B2,...,BMのような連続n-区間になる。

　そして、言語を効率的に実現するため、それを簡約(normalization)することが必要であるので、本章で最適区間に関する述語の簡約を明示する。簡約した後の述語は以下のような選言標準形をしている。

　そのうち、各pijは以下の特別な性質を持っている形をしている:〓は〓のような全順序の関係である。

　第5章<One dimensional range problem>では、一次元の最適区間問題の実現手法について説明する。

　データマイニングにおける一次元の最適区間問題は実際に最長部分列の問題である。というのは、「ある列xが与えられたときに、xの性質pを満たす最適の部分列を求める」という問題である。簡単な例として、列〓が与えられたとき、xの連続する部分列(segment)[xi,xi+1,...,xj]のうち、性質pを満たすようなのもののうち、最長のものを求めることである。ここでpは言語R〓lで定義されて、第4章で得た簡約形である。そのうち、基となる問題は、両端要素が大小関係を満たす最長部分列の問題である:数値列x=[x0,x1,...,xn-1]が与えられた時、xの連続する部分列[xl,xl+1,...,xr]の左端要素xlと右端要素の間に、〓という関係が成り立つようなもののうちで、最長のものを求める。

　本章ではこのような基本的な最長部分列問題に対してある効率のよい(線形時間)アルゴリズムを提案し、その上で、最小属性値を持つ多次元探索木を用いて基本的な問題を組み合わせた複雑な問題(述語が論理積である場合)を解決することについて述べる。

　第6章<Multiple range problem>では、多次元の最適区間問題の実現手法について述べる。

　一次元の最適区間の解決策を基づいて、二次元の最適区間問題に対するあるアルゴリズムを提案した上、　多次元への拡張する　ことを論ずる。

　第7章<Multi-dimensional searching trees with minimum attribute>では、最適区間の探索に対する基礎としての最小属性値を持つ多次元探索木を紹介する。

　多次元空間における最小値を検索することは実用と理論両面で有益なことである。これは元々計算幾何分野の問題であるが、本論文に述語が論理積である場合の最長部分列の解決することにも大変役に立つ。一方、最小値を検索する効率は基礎をなすデータ構造に依存している。本章では最小属性値を持つ多次元探索木(k-d-M木に略す)という新しいデータ構造を提案し、また0(log(k-1)n)時間で(kは次元の数)ある所与の多次元値が最小値かどうかを判断できるアルゴリズムを実現する。

　第8章<System for mining optimal ranges>では、実装したシステムの枠組みを明示する。ユーザの視点から、システムのインターフェース、マイニング条件の指定方法、及び結果画面を展示する。また、現実のデータを用いてシステムをテストすることでシステムの性能を評価する。

図1:区間性質を指定する述語

　本論文は、A Compositional Approach to Mining Optimal Ranges(邦訳:最適区間探索の構成的手法に関する研究)と題し、最適区間探索の構成的手法に関する研究について述べたものである。データの収集方法の大幅な進歩と記憶装置の低価格化に伴って、膨大なデータを蓄積することができるようになり、こうして得られた膨大なデータ中に潜んでいる有意義な情報を抽出するデータマイニングの理論や技術の重要性が高まってきている。本論文では、データマイニングに対するアルゴリズムの効率化について、とくに最適区間探索の構成的手法を扱っている。期待する最適区間の抽出のための表現法として、本論文では簡便で一般性のある区間問合せ言語を提案し、その効率的な実現手法を示している。また、実現したシステムを用いて実際のPOSデ一夕ベースに対して適用した実験結果により、提案した手法の有効性を実証している。

　第1章Introductionでは、本研究の背景と目的について述べている。膨大な蓄積データの分析に関する課題のなかで、とくにデータに潜んでいる区間情報を抽出することの意義を説明している。現実のデータに対しては、一つの区間だけではなく、複数の区間に対する最適区間を求めることも必要とされ、従来のアルゴリズムでは解決されていない問題点を指摘している。本論文では、このような最適区間問題に着目し、「あるデータが与えられたとき、性質を満たす最適区間を求める」一般的なアルゴリズムの構成法を対象としていることを述べている。

　第2章Range querying languageでは、最適区間を探索する実例から、最適区間の表現法とそのための言語の要素をまとめて説明し、RQL(Range Query Language)という、関係データベースの操作言語SQL(Structured Query Language)に似た表現の言語を定義している。

　第3章System overviewでは、提案した言語RQLを実現するシステムを概観し、そのために解決すべき課題を述べて、本研究の具体的な問題を明確に示している。

　第4章Compilationでは、最適区間を抽出するための前処理について述べている。この前処理は対象とするデータと言語RQLによる表現の両方に対して行なっている。データの前処理には、すでに知られている準線形時間のアルゴリズムを用いることができるが、言語の表現を効率的に実現するには、条件を表現する述語のあらたな標準化(normalization)が必要とされる。本章では最適区間に関する述語の標準化手法を示して、そのアルゴリズムを述べている。ここでは、区間に関する性質を表現するために、求められる区間の最左要素と最右要素の間に成り立つ順序関係による述語に着目している。

　第5章One dimensional range problemでは、一次元の最適区間問題の実現手法を述べている。データマイニングにおける一次元の最適区間問題は、既知の非負最長部分列の問題に帰着されることを述べ、これが第4章で扱った標準形になっていることを示している。標準形の述語に現われる関係式が1個の場合には、すでに線形時間アルゴリズムが知られているが、複数の関係式によって記述される述語に対して効率のよいアルゴリズムはこれまでに知られていない。この場合には、第7章で述べている極小属性値を持つ多次元探索木を用いて解決できると主張している。

　第6章Multiple range problemでは、多次元の最適区間問題の実現手法について述べている。一次元の最適区間の解決策を基礎として、二次元の最適区間問題に対するアルゴリズムを提案し、多次元への拡張を論じている。

　第7章Multi-dimensional searching trees with minimum attributeでは、最適区間の探索に対する基礎としての最小属性値を持つ多次元探索木を扱っている。多次元空間における極小性を判定するアルゴリズムが、述語が複数の関係式の論理積で表現された場合の最長部分列問題の解決に有効であることを述べ、これまでには得られていなかった効率的な検査のためのデータ構造を提案している。ここで提案した最小属性値を持つ多次元探索木(k-d-m tree)により、k次元空間における極小値であるかどうかをO(log^(k-1) n)時間で判定できるアルゴリズムを示している。

　第8章System for mining optimal rangesでは、実現したシステムについて、その概要を述べ、ユーザインターフェース、マイニング条件の指定方法、結果画面の表示法等を示した上で、実際のデータを用いた実験結果を示してシステムの性能を評価し、アルゴリズムの有効性を示している。

　以上、これを要するに、本研究は、大量のデータから希望する条件を満たす最適区間を抽出するという問題に対して、条件の表現法を提案するとともに、その条件に対する効率的なアルゴリズムの一般的な構成法を与えたものである。また、その方法によってプロトタイプシステムを構築して、実際に現実のデータに対して実用性を確認している。この成果は情報工学上貢献するところが多大である。よって本論文は博士(工学)の論文として合格と認められる。