データベースの属性間関係に関する学習の効率化

本研究では、関係データベースの属性間の関数関係を見つけるためのアルゴリズムの効率化について研究した。近年、各種の手段で蓄積されたデータを解析し、その中から有効な情報をコンピュータを用いて(半)自動的に抽出するデータベースからの知識発見に関する研究が活発に進められている。知識発見研究の一つとして、対象データを関係データベースのタプルの集合とし、その属性間の関数的な関係をデータから発見するための各種の手法が検討されている。本研究は、このような関数関係の発見の基本となるアルゴリズムに関する研究として位置付けられる。1変数(1属性)間の関数関係の場合、関係は比較的容易に発見することができるが、複数属性の関数関係は、属性数に対して指数関数個ありうるため、すべての関数関係を発見することは計算量的に難しい。対象となるタプルの集合に対するサンプリングによる近似解法は、計算量を減少させるのに有効であったが、実用化するためには、対象データの属性数の増加に対して十分に効率的なアルゴリズムが必要になる。そこで、本研究では、属性数の増加に対して十分有効な関数関係の学習アルゴリズムについて検討を行ない、実用的な観点から有効な学習アルゴリズムを考案し実装した。このアルゴリズムは、属性間の関数関係を発見する問題とハイパーグラフのトランスバーサルを求める問題との類似性に着目したアルゴリズムで、試験的に作成したプログラムを用いて実験を行なったところ、属性数が50くらいまでの関係に対して、現実的な時間で解をもとめることが可能であることが確かめられた。

本研究では、関係データベースの属性間の関数関係を見つけるためのアルゴリズムの効率化について研究した。近年、各種の手段で蓄積されたデータを解析し、その中から有効な情報をコンピュータを用いて(半)自動的に抽出するデータベースからの知識発見に関する研究が活発に進められている。知識発見研究の一つとして、対象データを関係データベースのタプルの集合とし、その属性間の関数的な関係をデータから発見するための各種の手法が検討されている。本研究は、このような関数関係の発見の基本となるアルゴリズムに関する研究として位置付けられる。1変数(1属性)間の関数関係の場合、関係は比較的容易に発見することができるが、複数属性の関数関係は、属性数に対して指数関数個ありうるため、すべての関数関係を発見することは計算量的に難しい。対象となるタプルの集合に対するサンプリングによる近似解法は、計算量を減少させるのに有効であったが、実用化するためには、対象データの属性数の増加に対して十分に効率的なアルゴリズムが必要になる。そこで、本研究では、属性数の増加に対して十分有効な関数関係の学習アルゴリズムについて検討を行ない、実用的な観点から有効な学習アルゴリズムを考案し実装した。このアルゴリズムは、属性間の関数関係を発見する問題とハイパーグラフのトランスバーサルを求める問題との類似性に着目したアルゴリズムで、試験的に作成したプログラムを用いて実験を行なったところ、属性数が50くらいまでの関係に対して、現実的な時間で解をもとめることが可能であることが確かめられた。