以前の類似したデータベースの解析結果からの効率の良いデータマイニング
野中 康太郎 (9851082)
近年の計算機の高速化や記憶装置の発達に伴い，大量の情報を記憶した
データベースシステムのデータの全てが
(ランダムサンプリングなどのように一部のデータのみに対してではなく)
解析可能になった．
このような大規模データベースの内容全体を解析することにより，
データベースの利用者にとって有益な情報を得ることをデータマイニング
と呼ぶ．
データマイニングによって得たい情報として，
頻出集合や有意な連想規則を求めることが挙げられる．
これらのアルゴリズムはさまざまな文献で提案されている．
しかし，これらのアルゴリズムの性能は
ベンチマーク上でしか評価されていない．
これに対して，(a)頻出集合の最大サイズや
(b)有意な連想規則の最大右辺サイズを求める問題を多項式時間で
効率良く解くことができないことが既に示されている．
つまり，一般には，これらの問題は効率良く解けない．
そこで，本研究ではデータベースの類似性に着目した．
これは，例えば小売店のセールスデータベースを月ごとに分割した場合、
毎年同じ月のデータが類似しているという性質である．
例えば，ここで1998年4月のデータベースをDとし，
1999年4月のデータベースをD'とする．
このとき，次に挙げる3つのアルゴリズムを提案した．
(i)Dの解析結果からD'中の頻出集合を効率良く求めるアルゴリズム．
(ii)Dの解析結果からD'中の有意な連想規則を効率良く求めるアルゴリズム．
(iii)DとD'が類似しているかどうかを効率良く判定するアルゴリズム．