(57)【要約】【課題】  分類精度の高い分類規則を短時間で生成する。【解決手段】  それぞれ所定の属性に属する複数の属性値を含むレコードの集合を用いて、複数の部分規則からなる分類規則を生成し、分類精度が所定の基準に達しない前記部分規則を選択し、  選択された前記部分規則の条件を満たす属性値を有するレコードを前記レコードの集合から検出し、検出された前記レコードに対して新たに追加する追加属性を決定し、検出された前記レコードについて前記追加属性の属性値を検索することを検索システムに依頼し、前記検索システムによって検索された前記属性値を用いて、選択された前記部分規則に代わる部分規則を再生成する。【選択図】  図１
2006048129.tif 000002
【特許請求の範囲】
【請求項１】
それぞれ所定の属性に属する複数の属性値を含むレコードの集合を用いて、複数の部分規則からなる分類規則を生成する分類規則生成部と、
分類精度が所定の基準に達しない前記部分規則を選択する部分規則選択部と、
選択された前記部分規則の条件部を満たす属性値を有するレコードを前記レコードの集合から検出するレコード検出部と、
新たに追加する追加属性を決定する追加属性決定部と、
検出された前記レコードについて前記追加属性の属性値を検索することを指定された検索システムに依頼する検索依頼部と、
前記検索システムによって検索された前記追加属性の属性値を用いて、選択された前記部分規則に代わる部分規則を再生成する部分規則再生成部と、
を備えたデータ分析装置。
【請求項２】
前記分類規則生成部は、前記分類規則として決定木を生成するものであり、前記決定木におけるルートノードから末端ノードへ至るパスに対応付けられる規則は前記部分規則に対応することを特徴とする請求項１に記載のデータ分析装置。
【請求項３】
前記レコード検出部は、前記部分規則の条件部を満たす属性値を有するレコードから、目的属性の属性値が相異なるレコードをそれぞれサンプリングにより抽出することを特徴とする請求項１又は２に記載のデータ分析装置。
【請求項４】
前記検索依頼部は、
再生成された前記部分規則を含む分類規則からその分類規則中に含まれる属性を検出し、
前記レコードの集合のうち、検出された前記属性の属性値を含まないレコードについて、検出された前記属性の属性値を検索することを前記検索システムに依頼し、
前記分類規則生成部は、前記レコードの集合における各前記レコードの前記検出された属性の属性値を用いて分類規則を再生成する、
ことを特徴とする請求項１又は２に記載のデータ分析装置。
【請求項５】
前記レコードの集合を格納し、外部から与えられた情報に基づいて前記レコードの集合に前記レコードを追加又は前記レコードを更新するデータ記憶部をさらに備え、
前記部分規則選択部は、前記データ記憶部を監視し、前記レコードの追加又は更新が発生した場合は、前記分類規則内に前記所定の基準に達しない部分規則が発生したか否かを判断し、発生した場合は前記部分規則を選択することを特徴とする請求項１又は２に記載のデータ分析装置。
【請求項６】
処理停止指示が入力された場合は、前記部分規則選択部による処理を停止させる処理停止部をさらに備えたことを特徴とする請求項５に記載のデータ分析装置。
【請求項７】
前記レコード検出部は、選択された前記部分規則の条件部を満たす属性値を有するレコードから、目的属性の属性値が相異なるレコードをそれぞれサンプリングにより抽出し、
前記検索依頼部は、
前記サンプリングによって抽出されたレコードについて前記追加属性の属性値を検索することを前記検索システムに依頼し、
前記サンプリングによって抽出されたレコードについて前記検索システムによって検索された前記追加属性の属性値に基づき、前記サンプリングによって抽出されたレコードを所定の水準により分類できる追加属性を前記追加属性の中から特定し、
選択された前記部分規則の条件部を満たす属性値を有するレコードのうち前記サンプリングによって抽出された以外のレコードについて、特定された前記追加属性の属性値を検索することを前記検索システムに依頼し、
前記部分規則再生成部は、選択された前記部分規則の条件部を満たす属性値を有するレコードについて検索された前記特定された追加属性の属性値を用いて、選択された前記部分規則に代わる部分規則を再生成する、
ことを特徴とする請求項１又は２に記載のデータ分析装置。
【請求項８】
それぞれ所定の属性に属する複数の属性値を含むレコードの集合を用いて、複数の部分規則からなる分類規則を生成し、
分類精度が所定の基準に達しない前記部分規則を選択し、
選択された前記部分規則の条件部を満たす属性値を有するレコードを前記レコードの集合から検出し、
新たに追加する追加属性を決定し、
検出された前記レコードについて前記追加属性の属性値を検索することを指定された検索システムに依頼し、
前記検索システムによって検索された前記追加属性の属性値を用いて、選択された前記部分規則に代わる部分規則を再生成する、
データ分析方法。
【請求項９】
前記分類規則として決定木を生成し、前記決定木におけるルートノードから末端ノードへ至るパスに対応付けられる規則は前記部分規則に対応することを特徴とする請求項８に記載のデータ分析方法。
【請求項１０】
選択された前記部分規則の条件部を満たす属性値を有するレコードから、目的属性の属性値が相異なるレコードをそれぞれサンプリングにより抽出することを特徴とする請求項８又は９に記載のデータ分析方法。
【請求項１１】
再生成された前記部分規則を含む分類規則からその分類規則中に含まれる属性を検出し、
前記レコードの集合のうち、検出された前記属性の属性値を含まないレコードについて、検出された前記属性の属性値を検索することを前記検索システムに依頼し、
前記レコードの集合における各前記レコードの前記検出された属性の属性値を用いて分類規則を再生成する、
ことを特徴とする請求項８又は９に記載のデータ分析方法。
【請求項１２】
前記レコードの集合を格納し、外部から与えられた情報に基づいて前記レコードの集合に前記レコードを追加又は前記レコードを更新するデータ記憶部を監視し、
前記レコードの追加又は更新が発生した場合は、前記分類規則内に前記所定の基準に達しない部分規則が発生したか否かを判断し、
発生した場合は前記部分規則を選択する
ことを特徴とする請求項８又は９に記載のデータ分析方法。
【請求項１３】
処理停止指示が入力された場合は、前記データ記憶部を監視する処理及び前記所定の基準に達しない部分規則が発生したか否かを判断する処理を停止することを特徴とする請求項１２に記載のデータ分析方法。
【請求項１４】
選択された前記部分規則の条件部を満たす属性値を有するレコードから、目的属性の属性値が相異なるレコードをそれぞれサンプリングにより抽出し、
前記サンプリングによって抽出されたレコードについて前記追加属性の属性値を検索することを前記検索システムに依頼し、
前記サンプリングによって抽出されたレコードについて前記検索システムによって検索された前記追加属性の属性値に基づき、前記サンプリングによって抽出されたレコードを所定の水準により分類できる追加属性を前記追加属性の中から特定し、
選択された前記部分規則の条件部を満たす属性値を有するレコードのうち前記サンプリングによって抽出された以外のレコードについて、特定された前記追加属性の属性値を検索することを前記検索システムに依頼し、
選択された前記部分規則の条件部を満たす属性値を有するレコードについて検索された前記特定された追加属性の属性値を用いて、選択された前記部分規則に代わる部分規則を再生成する、
ことを特徴とする請求項８又は９に記載のデータ分析方法。
【請求項１５】
それぞれ所定の属性に属する複数の属性値を含むレコードの集合を用いて、複数の部分規則からなる分類規則を生成する分類規則生成ステップと、
分類精度が所定の基準に達しない前記部分規則を選択する部分規則選択ステップと、
選択された前記部分規則の条件部を満たす属性値を有するレコードを前記レコードの集合から検出するレコード検出ステップと、
新たに追加する追加属性を決定する追加属性決定ステップと、
検出された前記レコードについて前記追加属性の属性値を検索することを指定された検索システムに依頼する検索依頼ステップと、
前記検索システムによって検索された前記追加属性の属性値を用いて、選択された前記部分規則に代わる部分規則を再生成する部分規則再生成ステップと、
をコンピュータに実行させるデータ分析プログラム。
【請求項１６】
前記分類規則生成ステップは、前記分類規則として決定木を生成し、前記決定木におけるルートノードから末端ノードへ至るパスに対応付けられる規則は前記部分規則に対応することを特徴とする請求項１５に記載のデータ分析プログラム。
【請求項１７】
前記レコード検出ステップは、選択された前記部分規則の条件部を満たす属性値を有するレコード前記レコードから、目的属性の属性値が相異なるレコードをそれぞれサンプリングにより抽出し、
前記検索依頼ステップは、
前記サンプリングによって抽出されたレコードについて前記追加属性の属性値を検索することを前記検索システムに依頼し、
前記サンプリングによって抽出されたレコードについて前記検索システムによって検索された前記追加属性の属性値に基づき、前記サンプリングによって抽出されたレコードを所定の水準により分類できる追加属性を前記追加属性の中から特定し、
選択された前記部分規則の条件部を満たす属性値を有するレコードのうち前記サンプリングによって抽出された以外のレコードについて、特定された前記追加属性の属性値を検索することを前記検索システムに依頼し、
前記部分規則再生成ステップは、選択された前記部分規則の条件部を満たす属性値を有するレコードについて検索された前記特定された追加属性の属性値を用いて、選択された前記部分規則に代わる部分規則を再生成する、
ことを特徴とする請求項１５又は１６に記載のデータ分析プログラム。
【請求項１８】
前記検索依頼ステップは、
再生成された前記部分規則を含む分類規則からその分類規則中に含まれる属性を検出し、
前記レコードの集合のうち、検出された前記属性の属性値を含まないレコードについて、検出された前記属性の属性値を検索することを前記検索システムに依頼し、
前記分類規則生成ステップは、前記レコードの集合における各前記レコードの前記検出された属性の属性値を用いて分類規則を再生成する、
ことを特徴とする請求項１５又は１６に記載のデータ分析プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理方法及びデータ処理プログラムに関する。
【背景技術】
【０００２】
収集・蓄積されたデータに内在する規則性の発見、そして、発見した規則を適用して予測を行う、データマイニング技術はコンピュータの発達により実用化されるようになった。また、インターネットの普及はネットワークを介して様々な情報の収集を可能とし、ナビゲーションシステムの発達は高精度な地理情報を電子化するに至っている。
【０００３】
現在のデータマイニングは最初から分析を目的として、ある程度のコストをかけて収集されたデータ（例えば顧客データなど）を対象にしているが、より大量かつ広範なデータを低コストで収集しようとすると、インターネットや地理情報システムを用いた情報収集が有効である。しかしながら、これらインターネットや地理情報システム等の手段を用いた情報収集は、探索範囲をいくらでも広げることができる代わりに、検索に時間がかかるという欠点がある。以後、コストをかけて収集し、高速にアクセスできるデータベースに登録されたデータを「内部データ」と呼び、一方、外部から検索して得るデータを「外部データ」と呼ぶことにする。
【０００４】
ところで、データマイニング方法の一つに分類発見がある。これは与えられたデータ集合を特定の特徴に着目して分類するものである。例えば、（身長、体重、視力、睡眠時間）から「風邪をひきやすい人」と「ひきにくい人」を分類する規則を発見するようなものである。代表的な手法として決定木が知られている。身長、体重、視力、睡眠時間などの項目を属性と呼び、その値、例えば160cm、60Kgといった項目に対応した値を属性値と呼ぶ。規則を生成するためのデータは（身長、体重、視力、睡眠時間、最近風邪を引いたか）といった属性値のタプルで与えられる。属性の中から分析対象である目的属性（この例では「最近風邪を引いたか」）を指定し、目的属性以外の属性で目的属性の属性値を予測する規則を発見することが分類発見である。（以後、目的属性以外の属性を単に「属性」と呼ぶことにする。）
【０００５】
ここで、風邪の引きやすさを分類するために、身長、体重、視力、睡眠時間を用いただけでは十分な精度が得られなかったとする。この場合、例えば「居住場所の気温」データを加えることで分類精度が上がるかも知れない。住所が既知であるならば、地理情報システムを用いて居住場所の平均気温を検索し、新たな属性「居住場所の気温」の値を追加することができる。このように外部からデータを検索し、分析対象データに新しい属性値として追加することで分析性能を上げることが期待できる。
【特許文献１】特開平１０−２２２３７０号公報
【特許文献２】特開２００４−３８４１２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、従来の分類発見方式は、目的属性を最も分類できる属性群をトップダウンに選ぶことで処理が進む。目的属性を最も分類できる属性を選択するためには、各属性を選択した場合の効果をすべて求め、最も高い効果を持つ属性を選ばなければならない。外部データを追加して分類規則の生成する場合は、分析対象の全データ（全レコード）について、追加属性の属性値を検索する必要がある。
しかし、上述のように、外部からのデータ検索には時間を要するため、このように外部から属性値を検索する時間が、分類発見処理全体の時間を長くする要因となっていた。
【０００７】
本発明は、上記問題点に鑑みてなされたものであり、その目的は、分類精度の高い分類規則を短時間で生成できるデータ処理装置、データ処理方法及びデータ処理プログラムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明のデータ分析装置は、それぞれ所定の属性に属する複数の属性値を含むレコードの集合を用いて、複数の部分規則からなる分類規則を生成する分類規則生成部と、分類精度が所定の基準に達しない前記部分規則を選択する部分規則選択部と、選択された前記部分規則の条件部を満たす属性値を有するレコードを前記レコードの集合から検出するレコード検出部と、新たに追加する追加属性を決定する追加属性決定部と、検出された前記レコードについて前記追加属性の属性値を検索することを指定された検索システムに依頼する検索依頼部と、前記検索システムによって検索された前記追加属性の属性値を用いて、選択された前記部分規則に代わる部分規則を再生成する部分規則再生成部と、を備える。
【０００９】
本発明のデータ分析方法は、それぞれ所定の属性に属する複数の属性値を含むレコードの集合を用いて、複数の部分規則からなる分類規則を生成し、分類精度が所定の基準に達しない前記部分規則を選択し、選択された前記部分規則の条件部を満たす属性値を有するレコードを前記レコードの集合から検出し、新たに追加する追加属性を決定し、検出された前記レコードについて前記追加属性の属性値を検索することを指定された検索システムに依頼し、前記検索システムによって検索された前記追加属性の属性値を用いて、選択された前記部分規則に代わる部分規則を再生成する。
【００１０】
本発明のデータ分析プログラムは、それぞれ所定の属性に属する複数の属性値を含むレコードの集合を用いて、複数の部分規則からなる分類規則を生成する分類規則生成ステップと、分類精度が所定の基準に達しない前記部分規則を選択する部分規則選択ステップと、  選択された前記部分規則の条件部を満たす属性値を有するレコードを前記レコードの集合から検出するレコード検出ステップと、新たに追加する追加属性を決定する追加属性決定ステップと、検出された前記レコードについて前記追加属性の属性値を検索することを指定された検索システムに依頼する検索依頼ステップと、前記検索システムによって検索された前記追加属性の属性値を用いて、選択された前記部分規則に代わる部分規則を再生成する部分規則再生成ステップと、をコンピュータに実行させる。
【発明の効果】
【００１１】
本発明により、分類精度の高い分類規則を短時間で生成できる。
【発明を実施するための最良の形態】
【００１２】
（第１の実施の形態）
図１は、本発明に従ったデータ処理装置の一実施の形態を示すブロック図である。
【００１３】
データ記憶装置１１は、データ分析を目的として予め収集されたデータ（内部データ）をデータベースに格納する。データベースは、複数のレコードを含み、各レコードはそれぞれ複数の属性値を含む。各属性値はそれぞれ所定の属性に属する。このデータベースは高速にアクセス可能である。
【００１４】
検索システム１２は、検索要求を受け付け、検索要求に基づく検索を行い、検索結果を返す。検索システム１２は、例えばインターネットや地理情報システムである。検索システム１２による検索は、時間がかかる。
【００１５】
規則生成器１３は、データ記憶装置１１に記録された内部データを用いて分類規則を生成する。また、規則生成器１３は、内部データを用いて、分類規則から、分類精度の低い規則（部分規則）を発見する。
【００１６】
規則記憶装置１４は、規則生成器１３によって生成された分類規則を記憶する。
【００１７】
追加データ選定器１５は、規則生成器１３によって分類精度が低いと判断された部分規則の精度を向上させるため、新たに追加する属性を、予め与えられた属性の中から所定の手法により選定する。所定の手法としては、例えばランダム、優先順位順によるものなどがある。追加データ選定器１５は、追加の属性を利用者から受け付けてもよい。追加データ選定器１５は、規則生成器１３によって分類精度が低いと判断された部分規則が適用されるデータベース内のレコードについて、選定されたあるいは指定された属性の属性値を検索することをデータ管理器１６に指示する。ここで、部分規則が適用されるレコードとは、部分規則の条件部を満たす属性値を有するレコードのことである。
【００１８】
データ管理器１６は、追加データ選定器１５による検索指示を受けて、検索システム１２に検索を依頼し、検索結果（外部データ）を受け取る。データ管理器１６は、受け取った外部データをデータ記憶装置１１内のデータベースに追加する。これにより分類精度が低いと判断された部分規則が適用されるレコードについて新たな属性値が追加される。
【００１９】
図２は、図１のデータ処理装置による処理手順を説明するフローチャートである。
【００２０】
以下、具体例を用いて、図１のデータ処理装置による処理手順について詳しく説明する。
【００２１】
予めデータ記憶装置１１には、図３に示す内部データが記憶されているとする。
【００２２】
図３において、A1〜A3は属性であり、Yは目的属性（例えば風邪をひきやすい場合は○、ひきにくい場合は×）である。内部データはレコードR1〜R8を含む。ここでは、内部データとして８個のレコードを示したが、本発明はこのようなレコードの数に限定されない。
【００２３】
規則生成器１３は、図３に示す内部データを用いて分類規則を生成する（ステップS1）。ここでは、分類規則として、決定木を生成するとする。但し、本発明は、分類規則としてその他の規則、例えばCHAIDを生成することも含む。
【００２４】
図４は、生成された決定木を示す図である。
【００２５】
この決定木では、内部データに含まれる属性A1〜A3のうち、属性A1のみが用いられている。この決定木は、２つの部分規則を含む。１つは、「Ａ１が０ならば目的値は○」、もう１つは、「Ａ１が０ならば目的値は×」である。このように各部分規則は、決定木におけるルートノードから末端ノードに至るパスに対応付けられる。「Ａ１が０」及び「Ａ１が１」はそれぞれ各規則の条件部である。
【００２６】
規則生成器１３は、生成された決定木において、分類精度が低い部分規則が存在するかどうかを判断する（ステップS2）。
【００２７】
規則生成器１３は、分類精度の低い規則が存在しない場合は（ステップS2のない）、生成された決定木を規則記憶装置１４に記録する（ステップS3）。
【００２８】
一方、規則生成器１３は、分類精度の低い規則が存在する場合は（ステップS2のある）、分類精度の低い規則を１つ選ぶ（ステップS4）。
【００２９】
ここで、図３の内部データにおける各レコードR1〜R8を、図４の決定木に適用して分類精度が低い規則が存在するか否かを調べる。図４における値が○である末端ノードL1を含む規則が適用されるレコードはレコードR1〜R4であり、これらのうちレコードR1〜R3はいずれも目的属性Yの属性値が○であるが、レコードR4は×である。従って、末端ノードL1を含む規則の分類精度は75%（＝3/4）である。一方、図４における値が×である末端ノードL2を含む規則が適用されるレコードはレコードR5〜R8であり、これらのレコードR5〜R8はいずれも目的属性Yの属性値が×である。従って、末端ノードL2を含む規則の分類精度は100%（＝4/4）である。仮に分類精度の基準を90%とすると図４における末端ノードL1を含む規則の分類精度は低いということになる。
【００３０】
追加データ選定器１５は、分類精度が低い規則が適用されるレコード（本例ではR1〜R4）に追加すべき属性を所定の手法により選定する、あるいは追加属性の入力を利用者から受け付ける。追加データ選定器１５は、分類精度が低い規則が適用されるレコードについて、選定したあるいは入力された属性の属性値を検索することをデータ管理器１６に指示する（ステップS5）。
【００３１】
データ管理器１６は、追加データ選定器１５から受けた検索指示に基づく検索依頼を検索システム１２に対して行い、検索システム１２により検索された外部データ（追加属性の属性値）を受け取り、受け取った外部データ（追加属性の属性値）を、データ記憶装置１１内の内部データに追加する（ステップS6）。
【００３２】
図５は、図３の内部データに外部データが追加された状態を示す図である。
【００３３】
レコードR1〜R４ついて、新たな属性A4〜A8の属性値が追加されている。
【００３４】
規則生成器１３は、追加された外部データを用いて、分類精度が低い規則を再生成する（ステップS7）。
【００３５】
図６は、図５に示す外部データを用いて、図４の決定木における末端ノードL1を含む規則を再生成した状態を示す。図４における末端ノードL1を含むパス上に、新たな属性A4が追加されている。この決定木によれば、図５の各レコードR1〜R4は、いずれも正しく分類される。即ち、図５において、目的属性Yの値が○であるレコードR1〜R3は、値が○である末端ノードL1Aに分類され、目的属性Yの値が×であるレコードR4は、値が×である末端ノードL1Bに分類される。従って決定木の分類精度は向上している。
【００３６】
規則生成器１３は、この後、ステップS2に戻り、分類精度の低い規則がなくなるまで以上のステップS4〜S7を繰り返し、分類精度の低い規則がなくなったら（ステップS2のない）、最終状態の決定木を規則記憶装置１４に記録する（ステップS3）。
【００３７】
以上のように、本実施の形態によれば、分類精度の低い規則が適用されるレコードについてのみ、追加属性の属性値を検索すればよいため、検索対象となるデータ数を従来よりも低減でき、これにより分類精度の高い決定木を高速に作成できる。
【００３８】
従来であれば、例えば図３に示す全レコードR1〜R8について属性値を取得して図７に示すデータベースを構築し、このデータベースに基づいて再度決定木を作成し直す必要があった。つまり、従来においては、本実施の形態では不要なレコードR5〜R8についても属性値を検索する必要があるため検索に多くの時間を要し、この結果決定木の生成が遅くなった。
【００３９】
これに対し、本実施の形態では、上述のように、最小限のレコードについてのみ属性値を取得すればよいので、検索時間が少なくて済み、よって、決定木を高速に生成できる。
【００４０】
（第２の実施の形態）
第１の実施の形態では、分類精度が低い規則が適用されるレコード（例えば図３のレコードR1〜R4）全てについて、選択あるいは指定された属性（例えばA4〜A8）の属性値を検索した。しかし、選択あるいは指定された属性の中には最終的に決定木で使用されない属性（例えばA5〜A8）も含まれ得、そのような属性についてはできるだけ検索を省くことが、決定木の生成速度を高める上で効率的である。本実施の形態は以上の観点に鑑みてなされたものである。以下、本実施の形態について詳述する。
【００４１】
本実施の形態におけるデータ処理装置の構成は追加データ選定器１５の機能が第１の実施の形態と一部異なる。その他の構成要素は第１の実施の形態と同一である。
【００４２】
図８は、本実施の形態におけるデータ処理装置による処理手順を説明するフローチャートである。
【００４３】
図８においてステップS15〜S18以外のステップは第１の実施の形態と同じであるので、以下、ステップS15〜S18を中心に説明する。
【００４４】
追加データ選定器１５は、ステップS14で選択された分類精度の低い規則が適用されるレコードの中から、目的属性の値が相異なるレコードをそれぞれサンプリングにより抽出し、抽出されたレコードについてのみ追加属性の属性値を検索することをデータ管理器１６に指示する（ステップS15）。検索指示を受けたデータ管理器１６は、検索システム１２に対し検索要求を出力し、検索結果を受け取り、受け取った検索結果をデータ記憶装置１１に追加する（ステップS16）。
【００４５】
図９は、図４の決定木における末端ノードL1を含む規則が適用されるレコードR1〜R４の中から、目的属性Yの値が○と×のレコードをそれぞれ所定数（ここでは１つでそれぞれレコードR3、R4）選択し、選択されたレコードについてのみ追加属性の属性値を取得した状態を示す。次に、追加データ選定器１５は、追加属性の中から、少なくともサンプリングされたレコードを分類できる追加属性を選択する（ステップS17）。
【００４６】
図９では、追加属性A4〜A8のうち、属性A4、A5がこの条件を満たすので、これらの属性A4、A5を選択する。
【００４７】
追加データ選定器１５は、分類精度の低い規則が適用されるレコードのうち、サンプリングされたレコード以外のレコードについて、選択された追加属性の属性値を検索することをデータ管理器１６に指示する（ステップS17）。検索指示を受けたデータ管理器１６は、検索システム１２に対し検索要求を出力し、検索結果を受け取り、受け取った検索結果をデータ記憶装置１１に追加する（ステップS18）。
【００４８】
図１０は、レコードR1〜R4のうち、サンプリングされたレコードR3、R4以外のレコードR1、R2について、選択された追加属性A4、A5の属性値を取得した状態を示す。
【００４９】
次に、規則生成器１３は、分類精度が低い規則が適用されるレコードについて取得され且つ選択された追加属性の属性値を用いて、分類精度の低い規則を再生成する（ステップS19）。
【００５０】
図１０においてレコードR１〜R4について取得された追加属性A4、A5の属性値から再生成される規則は、前述した図６におけるA1→A4→L1A、A1→A4→L2Bと同じである。即ち、本実施の形態でも、図４に示す決定木から、第１の実施の形態と同じ図６の決定木が生成される。
【００５１】
以上までに説明したことを、別例を用いて再度説明する。
【００５２】
図１１（Ａ）、は予めデータ記憶装置１１に与えられた内部データを示し、図１１（Ｂ）は、図１１（Ａ）の内部データに基づき、規則生成器１３によって生成された決定木を示す。なお、図１１（Ａ）の内部データは、レコードR8の目的属性Yの値が異なる以外は図３に示す内部データと同一である。
【００５３】
図１１（Ａ）におけるレコードR1〜R4は、図１１（Ｂ）における末端ノードL1を含む規則が適用され、分類精度は、前述同様75%である。一方、図１１（Ａ）におけるレコードR5〜R8は、図１１（Ｂ）における末端ノードL2を含む規則が適用され、分類精度は、これも75%である。分類精度の基準を90%とすると、いずれの規則も分類精度は低いことになる。
【００５４】
図１２（Ａ）は、図１１（Ｂ）における末端ノードL1を含む規則が適用されるレコードR1〜R4について、図８のステップS15〜S18に従って取得された属性値を、図１１（Ａ）の内部データに追加した状態を示す。ここでは、属性A4、A5の属性値が追加されている。図１２（Ｂ）は、図８のステップS19に従って、図１２（Ａ）に示す追加された属性A4、A5の属性値を用いて、図１１（Ｂ）における末端ノードL1を含む規則を再生成した状態を示す。
【００５５】
図１３（Ａ）は、図１２（Ｂ）における末端ノードL2を含む規則が適用されるレコードR5〜R8について、図８のステップS15〜S18（２ループ目）に従って取得された属性値を、図１２（Ａ）のデータベースに追加した状態を示す。ここでは、属性A6〜A8の属性値が追加されている。図１３（Ｂ）は、図８のステップS19に従って、図１３（Ａ）に示す追加された属性A6〜A8の属性値を用いて、図１２（Ｂ）における末端ノードL2を含む規則を再生成した状態を示す。
【００５６】
図１３（Ｂ）における決定木の各規則は、いずれも分類精度は100%であり、従って図１１（Ｂ）に示す元の決定木よりも分類精度は向上している。
【００５７】
以上のように、本実施の形態によれば、所定の手法により選択されたあるいは利用者から入力された属性から、サンプリングされたレコードを少なくとも分類できる属性を選択し、選択された属性についてのみ、サンプリングされた以外のレコードについても属性値を検索するため、第１の実施の形態に比べて、検索する属性値の数を低減でき、よって、第１の実施の形態よりも高速に分類精度の高い決定木を生成できる。
【００５８】
（第３の実施の形態）
上述した第１及び第２実施の形態のように逐次的に属性値を取得して、部分的に決定木を修正していくと、決定木のサイズが冗長になる場合がある。そこで、本実施の形態では、第１又は第２の実施の形態により生成された決定木に含まれる属性の属性値だけを用いて、決定木全体を再構築する。
【００５９】
本実施の形態におけるデータ処理装置の構成は、追加データ選定器１５の機能が第１及び第２の実施の形態と一部異なる。その他の構成要素は第１及び第２の実施の形態と同一である。
【００６０】
図１４は、本実施の形態におけるデータ処理装置による処理手順を説明するフローチャートである。
【００６１】
まず、データ処理装置は、第１又は第２の実施の形態に従って決定木を生成する（ステップS21）。
【００６２】
ここでは、第２の実施の形態に従って決定木を生成し、生成された決定木を図１３（Ｂ）とし、データ記憶装置１１には図１３（Ａ）に示すデータベースが登録されているとする。
【００６３】
次に、データ処理装置における追加データ選定器１５は、決定木で参照されている属性に関して値を有さないレコードを内部データから検出し、そのレコードについて前記属性の属性値を検索することをデータ管理器１６に指示する（ステップS22）。
【００６４】
図１３（Ｂ）の決定木で参照されている属性はA1、A4、A6であるので、追加データ選定器１５は、これらの属性の値を有さないレコードについてのみ、属性値の検索をデータ管理器１６に指示する。具体的には、レコードR5〜R8について属性A4の属性値、レコードR1〜R4について属性A6の属性値の検索を指示する。
【００６５】
検索指示を受けたデータ管理器１６は、検索システム１２に検索を依頼し、検索結果をデータ記憶装置１１内の内部データに追加する（ステップS23）。
【００６６】
図１５は、図１３（Ａ）の内部データに属性値が追加された状態を示す。
【００６７】
規則生成器１３は、決定木で参照されている属性の属性値だけを用いて、決定木を再構築する（ステップS24）。
【００６８】
図１３（Ｂ）の決定木で参照されている属性はA1、A4、A6であるので、これらの属性の属性値だけを用いて決定木を再構築する。これにより、よりコンパクトな決定木を構築できる場合がある。
【００６９】
以上のように、本実施の形態によれば、第１又は第２の実施の形態により生成された決定木に含まれる属性の属性値だけを用いて決定木を再構築するため、よりコンパクトな決定木を生成できる。内部データの全てを参照して決定木を生成する従来の方法よりも、参照すべき属性がある程度絞られているため、従来の方法よりも高速にコンパクトで分類精度の高い決定木を生成できる。
【００７０】
（第４の実施の形態）
データ記憶装置内にレコードが時々刻々と集積される又はデータ記憶装置内のレコードが時々刻々と更新される場合、過去に作成した決定木の分類精度が低下してくることがある。本実施の形態は、このように決定木の分類精度が低下した場合に、決定木における分類精度が低い規則を、第１の実施の形態又は第２の実施の形態を用いて再生成しようとするものである。
【００７１】
本実施の形態におけるデータ記憶装置１１は、外部から時々刻々と入力されるレコードを内部データに追加し、また外部から時々刻々入力される更新データに基づきレコードを更新する。
【００７２】
図１６は、本実施の形態におけるデータ処理装置による処理手順を説明するフローチャートである。
【００７３】
まず、このデータ処理装置は、第１、第２又は第３の実施の形態に従って決定木を生成し、生成した決定木を規則記憶装置１４に格納する（ステップS31）。
【００７４】
データ処理装置における規則生成器１３は、本処理の停止指示を利用者から入力されたか否かを判定し、入力された場合は（ステップS32のはい）、処理を停止する。例えば、以下のステップS34に示す規則生成器１３による処理を停止する。
【００７５】
時々刻々とデータ記憶装置１１内のデータベースが書き換えられる（ステップS33）。
【００７６】
規則生成器１３は、時々刻々と書き換えられるデータベース内のレコードに基づいて、規則記憶装置１４内の決定木に分類精度の低い規則が発生したか否かを検査する（ステップS34）。即ち、規則生成器１３は、データ規則装置１１を監視し、レコードの追加又は更新が生じた場合は、分類精度の低い規則が発生したか否かを検査する。
【００７７】
規則生成器１３は、決定木に分類精度の低い規則が発生していない場合は（ステップS34のない）、データベース内のレコードを用いて決定木を更新する（ステップS35）。つまりデータベース内の全レコードを用いて決定木を再度作成する。
【００７８】
一方、規則生成器１３は、決定木に分類精度の低い規則が発生した場合は（ステップS34のある）、分類精度の低い規則を１つ選択する（ステップS36）。この後、第１の実施の形態と同様にして、追加属性の属性値をデータ記憶装置１１に登録し、分類精度の低い規則を再生成する（ステップS37〜S39）。ここでは第１の実施の形態を用いて規則を再生成したが第２の実施の形態を用いてもよい。
【００７９】
以上のように、本実施の形態によれば、時々刻々と更新されるデータベースを用いて決定木における各規則の分類精度を検査し、分類精度が低下した場合は、第１又は第２の実施の形態を用いて、分類精度の低い規則を再生成するようにしたので、分類精度の高い決定木をデータベースの更新速度に大きく遅れることなく維持できる。
【図面の簡単な説明】
【００８０】
【図１】本発明の第１の実施の形態に従ったデータ処理装置を示すブロック図である。
【図２】図１のデータ処理装置による処理手順を説明するフローチャートである。
【図３】内部データの一例を示す図である。
【図４】図３の内部データから生成された決定木を示す図である。
【図５】図３の内部データに外部データが追加された状態を示す図である。
【図６】図５における外部データを用いて、図４の決定木における末端ノードL1を含む規則を再生成した状態を示す図である。
【図７】従来の手法を用いた場合に構築されるデータベースの一例を示す図である。
【図８】本発明の第２の実施の形態におけるデータ処理装置による処理手順を説明するフローチャートである。
【図９】サンプリングされたレコードについて取得された追加属性の属性値を示す図である。
【図１０】サンプリングされた以外のレコードについて取得された、選択された追加属性の属性値を示す図である。
【図１１】本発明の第２の実施の形態を具体例を用いて説明する図である。
【図１２】本発明の第２の実施の形態を具体例を用いて説明する図である。
【図１３】本発明の第２の実施の形態を具体例を用いて説明する図である。
【図１４】本発明の第３の実施の形態におけるデータ処理装置による処理手順を説明するフローチャートである。
【図１５】本発明の第３の実施の形態により生成されたデータベースを示す図である。
【図１６】本発明の第４の実施の形態におけるデータ処理装置による処理手順を説明するフローチャートである。
【符号の説明】
【００８１】
１1  データ記憶装置
１２  検索システム
１３  規則生成器
１４  規則記憶装置
１５  追加データ選定器
１６  データ管理器
【図１】
2006048129.tif 000003
【図２】
2006048129.tif 000004
【図３】
2006048129.tif 000005
【図４】
2006048129.tif 000006
【図５】
2006048129.tif 000007
【図６】
2006048129.tif 000008
【図７】
2006048129.tif 000009
【図８】
2006048129.tif 000010
【図９】
2006048129.tif 000011
【図１０】
2006048129.tif 000012
【図１１】
2006048129.tif 000013
【図１２】
2006048129.tif 000014
【図１３】
2006048129.tif 000015
【図１４】
2006048129.tif 000016
【図１５】
2006048129.tif 000017
【図１６】
2006048129.tif 000018