（金融商品 A = yes）バーコードやクレジットカードなど最近のデータ収集技術の大幅な進歩と、記憶装置の劇的な低価格化により、情報収集はたやすい作業になり、山に例えられるほど巨大なデータ（数ギガからテラ）がすでに存在する。特に、従来は敬遠されがちだった、時間情報（タイムスタンプ）の入った履歴データの収集も可能になってきている。
この山のようなデータベースから属性やデータ間に成り立つ規則を絞りだし、例えば営業戦略を立案する上で役に立つ、規則・法則のたぐいを得たいという自然な欲求が生まれる。ただし現行のデータベースシステムは検索・集計の簡易化と効率化を目標につくられており、残念ながら規則生成を目的には作られたわけではない。
しかし第一段階として、生データをデータベースシステムに格納し検索可能な状態にすることが考えられる。このようなシステムは大福帳システム・Information Warehouse ・Data Warehouse 等と呼ばれている。そして検索可能になった次の段階としてデータマイニングがある。
次の節で紹介するように、データマイニングやデータウエアハウスの研究開発は米国を中心に非常に活発ではあるが、計算機市場を拡大させるという観点からの貢献度は「ゆるやか」である点に注意が必要である。理由としては、巨大データベースを収集できる企業がかぎられていることが考えられる。例えば、銀行でいえば都銀や地銀クラスであれば巨大な顧客データベースや口座へのアクセスの履歴をもっているが、信用金庫クラスでデータマイニングが価値あるような量のデータをもっているとは限らない。また、流通業でいえば、全国的なチェーンをもつ百貨店やコンビニ、そして通信販売会社はデータマイニングする価値のあるデータベースをもってはいるものの、限定された地域で展開する小規模な企業の場合はデータマイニングの必要性が不明確であり、データマイニングシステムの売り込みは困難になってくる。
このように大規模なデータベースをもち、数十人の情報部門をもつような大企業は比較的大きな投資、例えば数億円の資金を、並列計算機とデータマイニングの組み合わせたシステムに投資できるであろう。しかしそれ以外の企業は外部に委託して自らのデータをデータマイニングしてもらうような、いわゆるアウトソーシングのようなことを体力的にせざるを得ないのではないか。シンクタンクがこのようなサービス業務を今後発展させ収益性の高いビジネスに結び付ける可能性がある。例として、最近テレビ等で話題になっている企業倒産の予測をするシステムではデータマイニング技術が使われている。
また企業ではないが、科学者は巨大なデータベースを構築しており、例としてゲノム情報、気象情報、天文情報等がある。分子生物学者や医学研究者は、ゲノム上に散在する複数の因子がどのように組み合わさり病気などの現象を引き起こすか解析するため大きなデータベースを構築している。データマイニングはこの作業の効率化に大きく貢献することが期待されている。症状が出る前の人を事前にチェックできる知識の発見は、早期に病気を予防する手立てを与え、製薬会社の開発ありかたに新たな方向性を与えるであろう。ただこの場合も企業のケースに似ており、科学者で巨大なデータベースを蓄積でき、かつ並列計算機のような大規模システムを購入できる機関は限られている。
以上の状況を鑑みると、データマイニングを軸とした大規模システムを現実に購入できる企業や機関には限りがあるため、計算機システムの市場を大きく切り開くような潜在性をデータマイニングに期待するのは無理があると思われる。むしろ、知識を売って行くシンクタンクのような企業を大きく伸ばすことにデータマイニングは貢献するであろう。科学データからの知識発見技術は、バイオ産業など計算機以外の他の産業へ影響を及ぼすようになると考えられる。
データマイニングには意味のある巨大なデータベースの存在が欠かせない。そして抽出された知識はデータベースを構築した組織の所有物にもなりうるし、科学データベースなら共有の財産にもなるであろう。ただ産業として魅力ある物にするには、データマイニングした知識を例えば特許化することが考えられ、後に議論する。
Information（Data）Warehouse等の利用形態は、従来のオンライン・トランザクション処理（OLTP）よりは、データ検索・集計等のデータ解析作業が中心となる。従って問い合わせの高速処理が望まれ、オンラインで実行できるほどの速度が望まれ、OLAP（On Line Analytical Processing）の名のもと研究開発が盛んである。
特に頻繁に使われ、かつ速度が要求されるのは効率的なアクセスパスが設定されていないデータベースへの非定型の問い合わせであり、典型的な例は集計作業である。例えば、顧客（Customer）が部品（Part）をどの問屋（Supplier）からいくら（SalesPrice）で購入したかを格納した関係 R から、部品と顧客の組合せごとの売上表をつくる作業を考えよう。この目的のためには、次のような問い合わせ文をつくればよい。
SELECT Part, Customer, SUM（SalesPrice）AS Sales from R GROUP BY Part, Customer ;
ユーザはさらに、部品と問屋との組合せや、部品別等の様々な組合せで売上高を集計する問い合わせをするであろう。属性を次元の軸と見立てると、多数の属性にたいする GROUP BY 問合せは多次元の空間中のデータ分布をみる作業に似ているため、多次元問合せと呼ばれ、出力されるテーブルはデータキューブと呼ばれる。
テーブルの属性集合の任意の部分集合に関して GROUP BY 処理を行う要求をユーザが何回にもわたって行う状況で応答時間を短縮することを考えよう。各属性に効率的なアクセスパスがはられている状況では、それらのパスを有効に用いて従来型の問合せ処理を行えばよいが、属性の数が 10 を超えるような状況ではすべての属性にアクセスパスを用意するのはデータ更新時のパスの保守を考えるとあまり現実的な選択ではない。むしろ、問合せの可能性のある仮想ビューをあらかじめ実体化（materialization）して、準備しておく方法が次善の策として考えられる。近年のデータベース分野では仮想ビューの実体化や保守に関して研究が進んでおり、これらの技術は多次元問合せを最適化するのに有効である。
多次元問合せにおける仮想ビューの実体化の方法について述べる。属性集合のすべての部分集合について GROUP BY 処理を行った仮想ビューを実体化して保存しておけるほど記憶スペースがある場合には、任意の部分集合についての問合せに対して即座に応答できる。しかし記憶スペースに限りがある場合には、そのスペース内に収まるように、実体化しておく仮想ビューの組合せを選別する必要がある。もし実体化していない仮想ビュー V に対する問合せがあった場合は、すでに実体化してある仮想ビューのどれか（例えば W）を使って V を生成することになるが、生成にかかるコストが最も小さいビュー W を利用すればよい。このコストは問合せの応答時間そのものである。記憶スペースが大きければ、実体化できる仮想ビューの数も増やせるので、コストを小さくすることができる。つまり実体化する仮想ビューを格納する記憶スペースは応答時間とトレードオフの関係にある。
現実には記憶スペースが固定されているので、スペースの制約から実体化できない仮想ビューを生成するためのコストが最小になるように、実体化すべき仮想ビューの組合せを選ぶことが望ましい。残念ながらこの問題は集合被覆問題と本質的に同等なので、最適化問題はNP 困難である。しかし幸い効率的な近似アルゴリズムをつくることができる。コスト削減する（応答時間を短くする）利得がもっとも大きい仮想ビューから順番に、記憶スペースがなくなるまで実体化してゆく貪欲なアルゴリズムを使ってできる仮想ビューの組合せは、コスト削減の利得という観点からは最良の組合せのよい近似解になることを Harinarayan らは示した［11］（詳しくは、最良の組合せの利得の約63％以上の利得があることが保証されている）。
多次元問い合わせは、従来型の検索・集計作業を効率化するのには有効であるが、データベースに潜む規則性を導き出すようなデータ解析の作業には向かない。
例として、数十の属性を含むデータベース、例えば銀行における数百万顧客の関係テーブルを考えよう。属性としては、当座取引有無・公共料金引落有無等の２値属性や、血液型等の離散属性、普通預金残高・年齢・取引期間等の数値属性があるとする。例えば
「先月発売した金融商品 A が売れている顧客層を明日の朝まで特定したい」
とする。いま条件 X を満たす顧客は高い確信度で金融商品 A を購入するというルールを
（金融商品 A = yes）と記述する。データマイニング・システムとは条件 X を自動的に抽出してくれるようなシステムのことである。例えば、
（当座取引有無 = 1）や、
（当座取引有無 = 1）かつ（公共料金引落有無 = 1）
などが条件の例である。このような条件部をもつルールを離散値属性間結合ルールと呼ぶことにする。離散値属性が数十数百ある場合には、システムが自動的に確信度の高い条件を取り出してくれると助かる。
また数値属性を使った条件としては、預金残高が区間 [X,Y] に入ることを示した
が考えられる。このような条件部をもつルールを数値属性間結合ルール（１次元版）と呼ぶことにする。システムは金融商品 A の購入者をできるだけ高い確信度で含む区間 [X,Y] を計算することが期待される。数値属性が数十数百ある場合には、やはりシステムが自動的に確信度の高い条件を取り出してくれると助かる。
また年齢と預金残高のペアがある連結領域 R に入ることを表現した
も条件として考えられ、システムは確信度の高い領域 R を求めて欲しい。このような条件部をもつルールを「数値属性間結合ルール（２次元版）」と呼ぶことにする。
以上のような規則を大規模データベースから高速に抽出しようとするのが、データマイニング・システムの一例である。以下、これらのルールを計算するための最適化手法を紹介する。また、後半では決定木や回帰木を生成する際に最適な区間や領域を計算することが役立つことを述べる。
スーパーマーケットの多くでは、商品にはバーコードのついたシールが張ってあり、レジにはその読みとり装置がついている。この装置は、金額の計算と同時に、どの商品とどの商品が、いつ、どのような人に、どれだけ売れたかがコンピュータに入力されたのである。このデータは特別な仕掛けを新たに作らなくても収集できる上に、顧客を知る重要な情報源となる。収集したデータから例えば「目玉商品 A を購入した顧客は高い確信度で日用品 B を購入する」という規則が得られたとすれば、目玉商品 A が他のどの日用品 B の売上に貢献するかが明瞭になる。さらに目玉商品 A を購入した顧客の何パーセントが日用品 B を購入するかが分かれば、売上の予測にもある程度つながる。
他の例では、銀行における顧客データベースから「普通口座を保有する顧客の１%は過去にカードローン支払いを延滞したが、普通口座を保有しかつサービス A を利用する顧客の場合は 0.05% しか支払延滞者がいない」という規則が得られたとする。この規則を発見出来れば、支払延滞率を下げるための有効な対策として、サービス A を顧客に勧めることを検討することができる。以後、「目玉商品 A を購入した顧客は高い確度で日用品 B を購入する」という規則を
（日用品 B = yes）と表現する。
では結合ルールの価値はどのように測るか？ 条件部を満たすデータが結論部も満たす割合を確信度（confidence）と呼び、条件部と結論部を同時に満たすデータの全データに対する割合をルールのサポート（support）と呼ぶ。特に断らない限り以下ではサポートはルールのサポートを指すことにする。条件部を満たすデータの割合は条件のサポートと呼ぶ。規則の価値を測る上で確信度が高いことが重要であることは当然であるが、ルールのサポートもある程度高いことが望ましい。
例えばルールのサポートが0.01% のルールは0.01%の顧客にしか当てはまらない出番の少ないルールであり、あまり価値がないからである。技術的な制約から言えば、非常に小さいサポートをもつルールまですべて探そうとすると、その数は容易に莫大になる。ユーザーにとっても、解析する気になるルールの数はせいぜい数千のオーダーであろう。極端に小さなサポート値のルールを排除し、かつルールの数を自然に制限する方法としては、出力するルールのサポートの最小値（最小サポートと呼ぶ）を設定するのが有効である。
IBM アルマデン研究所の Quest プロジェクトは、結合ルールを出力する本格的なシステムを世界に先駆けて開発した［2］。Quest システムはユーザーが最小サポートと最小確信度を与えると、すべての結合ルールを出力する。効率的に結合ルールを生成方法を設計する際に特に考慮しなければならないのは、データベースのサイズが大きく主記憶には入らず、２次記憶に置くしかない場合である。一方ルールの数は数千程度以下である場合がほとんどである。そこでデータベースの走査は２次記憶上で行うものの、ルール生成に必要な中間的なデータ構造は主記憶内に保持しながら計算することで実行効率をあげたAprioriアルゴリズム［3］を紹介する。
ルール「（A = a）かつ（B = b）（C = c）」のサポートと確信度は、
条件（A = a）かつ（B = b）
条件（A = a）かつ（B = b）かつ（C = c）
の各々のサポートから計算できることに注意しよう。すなわち後者の条件のサポートがルールのサポートそのものであり、ルールの確信度は、後者の条件のサポートを前者の条件のそれで割ったものである。従って、ルールを生成する際には、条件を生成し、そのサポートを計算すれば十分である。ではどのような順番で条件を生成するべきか。
条件「（A = a）かつ（B = b）かつ（C
= c）」を｛A = a, B = b, C = c｝のように集合表現し、条件集合と呼ぶことにする（条件集合はその要素である各条件がすべて −
どれかではない − 満たされる条件を意図していることに注意）。最小サポート以上のサポートをもつ条件集合を大きい条件集合と呼ぶことにする。例えば｛A
= a, B = b, C = c｝が大きい条件集合でない場合、ルール「（A
= a）かつ（B = b）（C = c）」のサポートは最小サポート以下なので、このルールは考察外となり、｛A
= a, B = b, C = c｝もルール生成に貢献しないので考察の対象からはずせる。この性質から一般に、ルール生成に関しては、大きい条件集合だけを生成してゆけば十分であることがわかる。
また｛A = a, B = b ｝が大きい条件集合でない場合は、｛A = a, B = b｝を部分集合として含む任意の条件集合 − 例えば｛A = a, B = b, C = c｝− も大きい条件集合になり得ない。すると、要素数の少ない条件集合から生成し、大きい条件集合か否かを調べてゆき、ある条件集合 − 例えば｛A = a, B = b｝− が大きくないと判定された場合にはそれを包含する条件集合 − 例えば｛A = a, B = b, C = c｝− を生成しないような戦略をとることで、大きな条件集合になりえない条件集合のサポートを無駄に計算しなくてすむ。最小サポートの設定方法にも依存するが、小さすぎない適切な値を設ければ、大きな条件集合とそのサポートの組を主記憶内に保持することができる。
次に各条件集合のサポートの計算方法について述べる。条件集合のサポートを計算する際には、２次記憶にあるデータベースを少なくとも１回は走査し、各レコードが条件集合を満たすかを調べ、満たされた条件集合のサポートを更新する必要がある。２次記憶上にあるデータベースを走査するのは処理のボトルネックとなるので、各条件集合ごとに走査するのではなく、１回の走査で複数の条件集合のサポートを計算することで効率を上げたい。Agrawal らは、要素数が１の条件集合すべてについてそのサポートを計算し、大きい条件集合か否かを判定し、続いて要素数が２の条件集合でその任意の部分集合が大きい条件集合であるものについてサポートを計算する、という作業を繰り返すことで大きい条件集合を枚挙する戦略を示した［3］。
この計算過程を分析してわかる性質のひとつに、要素数が１の条件集合のサポートを計算している際に、かなり早い段階で、例えば｛A = a｝と｛B = b｝が大きな条件集合であることが判明する場合がある。このケースでは要素数１の条件集合のサポートの計算中ではあるものの、並行して｛A = a, B = b｝のサポート計算も開始すれば、データベースの走査回数を減せる可能性が出てくる。Brin らはこの着想に基づき Agrawal らの戦略を拡張した方法を提示し、その有効性を実証している［5］。
Agrawal らの Apriori アルゴリズムを実装する際には、各レコードが満たす条件集合をすべて見つける手続きを効率化する必要がある。この高速化にはハッシュ木を使う方法による実装方法［3］やハッシュ表を使う方法［14］が提案されている。またデータを並列計算機上に均等分散して置けば、入出力を並列化できることに加えて、条件を満たすデータ数を集計する操作も自然に並列化でき、良好な台数効果も確認されている。
尚、最近はサポートと確信度だけでルールを評価するのではなく、伝統的な統計学の尺度で、例えば条件間の correlation を評価基準として用いることが提案され、その計算方法が考察されている［6］。
離散値属性間結合ルールは離散値をもつ属性を扱ったものである。現実のデータベースでは通常、年齢や預金残高のような数値属性が存在する。これら数値属性を離散値をもつ属性として考えても良いが、数値間の順序も考慮した結合ルールがあれば有用である。例えば「預金残高が V1 以上 V2 以下の顧客は高い確信度でサービス A を利用する」というルールから、サービス A を勧めるべき顧客層が浮かび上がってくる。このルールを離散値属性間結合ルールの形式に習って、
（サービス A = yes）のように記述する。
いま区間 [V1,V2] があらかじめ与えられていれば、条件「預金残高 ∈ [V1,V2]」を満たす顧客が何％の確信度で条件「（サービス A = yes）」も満たすかは容易に計算できる。しかし現実には区間そのものを見つけることに興味がある。しかも高い確信度を与える区間が分かれば、サービス A を利用する顧客をうまくモデル化したことになる。ここで問題になるのは、区間の取りかたは自由度が大きいことである。極端な例としては、ごく僅かなデータしか含まない極めて短い区間で、高い確信度を与える区間がいくつもありうる。いくら確信度が高くても、ごく僅かなデータしか含まない短い区間で意味のあるルールとは言えない。
いま条件「預金残高 ∈ [V1,V2]」を満たすデータの全データに占める割合を（預金残高に関する）区間 [V1,V2] のサポートと呼ぶことにする。ユーザーは考慮する区間がもつべきサポートの最低限の値を与える。すると、そのしきい値以上のサポートをもつ区間の中でルールの確信度を最も高くする区間 [V1,V2] が、サービス A を利用する顧客を一番特徴づけていると言える。このような区間を確信度最大化区間と呼び、ルールを最適確信度結合ルールと呼ぶことにする。これと双対的な概念として、ルールの確信度の最低限の値を与え、サポートが最大になる区間を求める問題が考えられる。このような区間をサポート最大化区間、ルールを最適サポート結合ルールと呼ぶ。
確信度最大化区間、およびサポート最大化区間を計算する初歩的な方法は、全ての区間を生成し、最大の区間を選択することである。データがソートされていれば、この方法の計算時間はデータ数の２乗に比例する。実は、計算幾何学的方法を使うと線形時間で解けることが知られている［7］。
この方法の計算時間上のボトルネックは、データを対象とする数値属性でソートしておく必要のある点にある。２次記憶上にある数百万件のデータを各数値属性毎にそのままソートするのは通常時間がかかるので、この計算時間を短縮しない限りは、計算幾何学的手法を用いた線形時間アルゴリズムも活かせない。
一つの解決案は、与えられたデータベースを、データの識別子と数値属性毎の値のペアへと垂直分解し、その数値属性値でソートする。このように分解したテーブルは今日の計算機の主記憶に十分格納できるので、ソートも十分速く実行できる。
もう一つの方法は、データ全体をソートしない方法である。かわりに、ランダムアルゴリズムを用いて、数値属性の値を細かい区間（バケット）に分割する。ただし、各区間に入るデータ数がほぼ均等になるように。このような均等なバケットを多数生成した後に、いくつか連続するバケットを繋ぎ合わせて確信度／サポート最大化区間をつくる。バケット分割処理を並列化してより一層の高速化もできる。バケット数としては数千程度用意すれば、最大化区間が非常に高い精度で得られる［7］。
次に、１つの数値属性だけでなく、複数の数値属性を条件部に含む結合ルールの生成について述べる。例えば、年齢と預金残高を使ってサービス A を特徴づける結合ルールとしては、次のようなルールが頭に浮かぶ。
（サービス A = yes）区間 I と区間 J の直積がつくる矩形領域は、サービス A を利用する顧客のいる範囲を大まかに教えてくれる。また、領域に入る顧客数の最低値をユーザーが与えると、最もサービス A を利用する顧客の確信度の大きい領域をみつけることが興味の対象になる。つまり１次元の場合に導入した最適確信度結合ルールの発見問題は２次元以上の場合にも自然に拡張できる。
更に一般的な形状をした連結領域 R を使えば、より柔軟にサービス A を利用する顧客を高い確信度で特徴付けられる。ルールとしては「年齢と預金残高が図の領域 R 入る顧客は高い確信度でサービス A を利用する」ことを意図した次の形のルールを求める。
（サービス A = yes）この場合にも１次元の場合と同様に最適確信度／サポート結合ルールを自然に定義できる。
まず、２つの属性が張る平面を格子状に分割し、ピクセルを生成する。通常は 20×20 から高々 1000×1000 のピクセルへと分解する。格子分解する作業をソートで実行すると時間がかかる。１次元の場合に用いたランダムサンプルを使う方法が有効である。
次にピクセルを繋ぎ合わせて矩形領域や連結領域をつくる。最適確信度／サポート結合ルールを生み出す領域を求める計算量は、矩形領域や連結領域等のどのタイプの領域を求めようとするかによって大きく異なる。矩形領域の場合は、問題を１次元の場合へ還元して解く方法が知られている限りベストで、ピクセル数を n とすれば O（n1.5）の計算量で解ける。
矩形領域よりは一般的な形をした連結領域であるx-単調領域（y 軸に平行な線との交わりが必ず連続か空となる領域）を考える。x-単調領域を対象にした最適確信度／サポート結合ルールはO（n m）（m はデータ数）で計算できるが、O（n ln m）で計算することは P=NP でない限り不可能である［8］。幸いイメージの濃淡度情報から x-単調領域を取り出す問題はイメージ処理の分野でよく調べられており［1］、浅野らの方法を変形することで、x-単調領域を対象にした最適確信度／サポート結合ルールの近似解をO（n ln m）で求めることができる［8］。
x-単調領域は一般的な形を表現することができるが、領域の境界が不必要にギザギザになる場合が多く、訓練用のデータでは確信度が最適な領域となっても、未知のテストデータに対しては、確信度がそれほど上がらないという問題点がある［18］。そこで領域の境界がより滑らかな直交凸領域 ─ y 軸だけでなく x 軸に平行な線との交わりも必ず連続か空となる領域─を用いた最適確信度／サポート結合ルールの近似解生成方法が提案されており、O（n1.5 ln m）で求めることができる［18］。また未知のテストデータに対しても良好な確信度が得られることが実験的に確認されており、後に述べる決定木や回帰木の予測精度もx-単調領域を用いる場合に比べて上がることが知られている［9、13］。
数百万件のデータで二次元結合ルールを生成する場合、単一プロセッサーでは格子分解が計算時間を支配することが実験により確かめられている。並列計算機を用いれば、格子分解を並列化してこのボトルネックを解消し、巨大データを高速に扱うことが検討されている。
例えば、患者がある病気（例えば糖尿病）であるかどうか検査を行なって判定する診断システムを考えよう。どのような検査をすると効率良く判定が出来るかを過去の病院の患者たちの健康診断データから診断システムを導出したい。このように、複数の数値属性（健康診断の数値）が与えられた大量のデータを、目的とする属性（例えば糖尿病であるかどうか）が満たされるクラスと満たされないクラスに分類するためのデータ構造として、代表的なものに決定木がある。決定木は木の高さ（一人の患者に対する検査の最大数）が小さく、木の端点数（用意すべき検査パターンの数）が小さいことが望ましい。決定木構成技術は意思決定支援システムとしてデータマイニング及び人工知能の分野でも非常に重要と考えられる。
病院において患者の過去の病歴がデータベース化されているとしよう。この過去のデータの蓄積から、どのような症状や健康状態の人に病気 A の病歴があるか否かを経験的に判定する知識を生成すれば、新たな患者が A を患っているか否かを判定するための助けになり便利である。また例えば、保険会社に蓄積された、利用者の過去の事故歴のデータベースから、特定の交通事故を起こしやすいか否かを経験的に判定する知識などを取り出したいというニーズがある。
木の各ノードはレコードに対するテストであり、テストで Yes と出たデータは左の枝に進み、No と出たら右の枝へ進む。決定木の各頂点でのテスト文には結合ルールに対応するものが用いられる。例えば、条件部の属性として最低血圧（数値）、血糖値（B）、コレステロール値（C）を考えて、血圧がある値以上か、もしくは他の値が ＋か−かでテストを行ない、最終的に、結論部として成人病症候群である（○）かない（×）かを判定する。このとき、テストの順番により、いろいろな決定木が作れるが、深さが小さく、頂点数も小さい決定木で良い判定が出来れば理想的である。
最小の決定木の構成問題は NP 困難といわれており［10］、従って、何らかの近似的な解法が必要になってくる。これに対するアプローチは様々なものがあり、有名なものに Quinlan のエントロピーを用いたヒューリスティクス［15］がある。この方法は決定木を上（根の方）から作っていくが、各段階で行なう判定を選ぶ時に、各々の条件文による判定でデータ集合がどのような分布に分割されるかを計算する。そこで、分割のエントロピーを計算し、それが最小になる（すなわち、分割の各成分で目的となる属性の分布がもっとも偏っている）条件文を選ぶ。この方法は、条件の属性が離散値をとるデータに対して、かなりいい決定木を生成する。Metha らによる SLIQ はエントロピーの代わりに Gini インデックスを利用したアプローチをとり、数千万件のデータに対しても現実的な時間で動作するシステムの構築に成功し注目されている［12］。
また Quinlan は、数値属性を持つデータに対しては数値属性たちの間に相関がある場合、従来の方法では不十分であることを指摘している［16］。例えば、属性として「体重」と「身長」を考えてみる。健康診断では、単一のルール
がかなり良く「健康」の判定を行なう。ところが、属性を1つづつ単独でテストする一次元ルールだけだと、結果として非常に大きな決定木を用いないと同等の性能を持つ決定木は作れない。
この欠陥を補うために、２つもしくは３つの数値属性の組を考え、対応する平面もしくは空間を、直線もしくは平面で二つの領域に切ることにより作った領域ルールでデータ分割を行なう試みもされている。しかしながら、直線や平面による分割は、計算時間が掛かる上に、分割の自由度が低いために、決定木の大きさを大幅には改善しない場合が多い。従って、それほど効果的ではないとされている。
そこでテスト文として（エントロピーを最小化し、情報量のゲインを最大化する）最適結合ルールを用いて数値属性を効果的に扱う方法が提案されている［9］。特に、２次元の最適結合ルールを判定に用いると、上述した数値属性たちの間に強い相関がある場合など、決定木の大きさは激減する。実際、身長と体重から「健康」を判定するには、判定文を（身長、体重）∈ R）の形（R は 条件＝「健康」に対応する領域）に取れば、単一の判定（高さ１の決定木）で良い診断を行なうものが出来る。このような単調な領域族をもちいたエントロピー最適化は、ピクセル数をn、データ数を m とすると実質的には直交凸領域でO（n1.5 ln m）、x-単調領域で O（n ln m）時間で求めることができる。
決定木が離散値属性の値を予測するためつくられる2分木であるのに対して、目的の数値属性の値を予測するための2分木として提案されたのが回帰木（Regression Tree）［4］である。例えば、為替レートや金相場の値動きを蓄積したデータベースから、各通貨がどのような値動きをしたとき、金の値がどの程度変化するかについて確度の高い経験則が得られれば、将来の予測に役立てることができる。
回帰木の各ノードはレコードに対するテストであり、レコードはテストを満たす場合は左の部分木に進み、満たさない場合は右の部分木に進む。この手順を繰り返すことで、各レコードは最終的に葉ノードに到達する。このような回帰木を現在あるデータベースから構築し、各葉ノードごとに、その葉ノードに到達する全レコードの目的の数値属性の平均値を計算しておく。そして目的の数値属性の値が未知のレコードが与えられたとき、回帰木のテストを繰り返し適用し、到達した葉ノードの平均値により目的の数値属性の値を予測することにする。
予測精度を上げるためには各ノードのテストをうまく選択する必要がある。その際に標準的に用いられるヒューリスティクスは、テストによる分割後に、各レコードの数値属性値とそれが属する部分集合の平均値の差の平方の平均（誤差自乗平均）を最小にするようなテストを選択する方法である［4］。テストの種類であるが、離散値属性に対する条件や、数値属性をある値の上下で2分割する条件が従来は用いられていた。数値属性の場合は、区間や領域を用いてデータ分割を行うことが決定木の場合と同様に自然であり、予測精度をあげる可能性がある。誤差自乗平均を最小化する領域を計算する問題は、エントロピー最小化問題と同様の方法で解くことができ、ピクセル数をn、データ数をmとすると実質的には直交凸領域でO（n1.5 ln m）、x-単調領域で O（n ln m）時間で計算できることが知られている［13］。さらにある値の上下で２分割する条件を使う従来の方法に比べて、未知のデータに対する予測精度を高めることができることが実証されている［13］。またx-単調領域を利用する場合よりも、直交凸領域を使ったほうが予測精度は良好な値をとる傾向にある。
今後の米国におけるデータウエアハウスやデータマイニングの技術的方向性を予測するのに、以下のような重要国際会議での発表内容の推移を見守ることは役立つと思われる。
まず最初の ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems は理論的色彩が強い会議であるが、近年の傾向を見るとデータマイニングに関する論文のセッションが毎回1つはできている。発表内容は例えば、データマイニングの計算量的限界（NP 困難等）の考察や、全データからデータマイニングするのではなくサンプリングにより精度の劣化を抑えつつ、計算時間を短縮する技法、計算幾何学の技術を使った効率化等の論文が見られる。
次に２番目の ACM SIGMOD Conference on Management of Data では理論的色彩も多少あるが、実用可能なアルゴリズムや実装方法の提案が主流であり、産業界からの発表も多い。IBMアルマデン研究所のアガラワラの結合ルールに関する記念すべき論文もこの会議で発表され、また、実体化したビューを使ったOLAPの応答時間を短縮する方法もスタンフォード大学のグループによりこの会議で発表されている。1998年度に採録された論文のタイトルをみても３セッションほどはデータマイニングとデータウエアハウスの論文が発表されるようである。
３番目の International Conference on Very Large Data Bases は、ACM SIGMOD Conference on Management of Data に比べさらに実用研究に近く、企業からの発表も多い。近年は、データマイニングの並列化や、決定木、回帰木の予測精度の向上をねらった現実的解法が提案されている。
１〜３番目までの会議が技術的シーズに的を絞っているのに対して、４番目の Knowledge Discovery and Data Mining では、データマイニング技術を使ってどのような問題が解けたかについての発表が多く、応用指向が強い。この会議はKDDと略称で呼ばれているが、近年アジア地区を中心として Pacific-Asia KDD も開催されており、アジアにおける研究開発も活発化している。
どの会議も倍率が平均して6〜7倍あり、発表内容も充実している。参考のために1998年度の各会議のURLを以下に挙げる。
これらの会議の内容から見て取れるように、米国における研究活動は層が厚く、理論、実装技術、応用に至るまで広くそして深くカバーしている。さらに、ハードウエアや OS の技術でも米国は他国を圧倒的に引き離しており、追随するのは困難である。
米国の圧倒的優位な状態で、日本の立場は苦しい。VHS のビデオ再生機が寡占状態になっており、レンタルビデオ屋でも VHSのビデオしかおいてない状態で、新たな録画方式を広めることは不可能に近いのに似ている。データマイニング産業で日本が選ぶ道は、データマイニング向けハードウェアの研究ではないように思う。いまから追随するのでは、多少論文の形にするのが精一杯であろう。米国では計算機産業の大きな柱になろうとしているのに残念であるが、隙間産業を狙って新たなビスネスの種を見つける努力をすべきであろう。
ソフトウェア技術に関しては日本の貢献はある程度知られているので、今後もソフトウェアへの投資は持続すべきであろう。しかしソフトウェアだけで大きな利潤を生み出すのは、困難であろう。はじめにも述べたようにデータマイニングに大規模な投資ができる国内の企業や機関の数が限られており、大量に売れたときはじめて莫大な利益が得られるソフトウェアにとっては厳しい状況である。
利益を生み出すためには応用に力点を置くのが有効と考える。具体的には、金融予測、経済予測等の分野でデータマイニングツールを他国よりうまく使いこなすノウハウを溜め込むのはどうか？ データマイニングでは意外に自動的に理想の知識が得られるわけではなく、パラメータのチューニングが重要である。チューニングは学術論文にはなりにくいものの、運用の要になり、スキルを向上させると、質のよい知識が抽出できるようになる。記号で表現された知識は顕現性が高いので、できれば特許のような形でおさえる事はどうか？
科学データベースに関しても、ただデータマイニングするだけでなく、得られた知識を特許化して特許料で稼げる体制をつくることができないだろうか？ というより、その方向で考える必要があると思う。私自身はゲノム情報から特許を抽出するデータマイニングシステムに興味を持ち研究を行っている。
＜参考文献＞