1.はじめに

データベースに蓄積されたデータから、有用な知識や法則を発見するデータマイニングの一手法であるクラス分類手法について、100ギガバイト超のデータを扱うことを目的として、PCクラス夕上での並列分散アルゴリズムを開発する。本稿ではクラス分類手法として、スライスアンドダイス分析手法と決定木構築手法の並列分散化について述べる。

2.スライスアンドダイス分析

表形式のデータを用いて、与えられた条件で選択されたレコード群に共通する特徴をデータベースの属性の属性値を用いて説明するスライスアンドダイス分析手法を開発した。

　例えば、図1(a)の小売業の売上データで、廃棄数の0以上のレコードを正例、他を負例とした場合、図1(b)のように単価と売上数の属性を直行した軸として生成される空間から、正例レコードの密集した空間を発見する。

図１：スライドアンドダイス分析

　分析対象データはPCクラス夕の各ノードに分散して配置し、各ノードで並列にデータをメモリ上に読み出す。分析対象属性がn個の場合、属性の細合せが2n一1通りあるので、2n-1個の空間について分析を行なう。

一つの空間の分析を一つのサブタスクとし、これらのサブタスクをPCクラスタの各ノードに割り付けることにより、容易に並列化が実現できる。

サブタスクの粒度は分析対象データの性質に依存するので、分析対象データを部分的に分析した結果を利用して負荷分散戦略を決疋すると、分析全体の高速化が期待できる。

3.決定木構築

決定木は、データマイニングで用いられる代表的な手法である。図2(a)のテーブルから図2(b)の木が生成される。決定木は、テーブルの属性からクラスを予測するための分類器である。

図２：トレーニングセットと決定木

　数100ギガバイト-数テラバイトクラスのデータを扱うことを目標に、並列決定木生成システムを構築した。ディスクサイズ、メインメモリサイズおよびコストバフォーマンスの面からPCクラスタをブラットフォームとした。IBMで開発されたSPRINT という決定木生成アルゴリズムをべースとしている。 SPRIINTは、メインメモリに乗らない大規模なデータを扱えるという特徴を持つ。これに改良を加えた。これは、木の内部ノード生成時に、各ノード生成処理で必要なメモリの大きさを調べ、スケジューリングを行なうというものである。ディスクアクセスが軽減され、全体の処理の高速化が期待できる。

4.おわりに

現在、上記2つのクラス分類方式を16ノードのPC クラスタ上で、100ギガバイト程度のデータを用いて分析実験を行なっている。

　今後は、テラバイト超のデータを扱えるように処理方式を拡張して行く予定である。