(57)【要約】【課題】データマイニングのルール生成において、項目単位でしか探索空間を削減することができない。【解決手段】探索空間削減装置１０２が、データ記憶装置１０５にある元データ、及び、パラメータ記憶装置１０６にあるパラメータのデータを編集し、ある項目のある値のデータをすべて欠損値に置換する。さらに、ルール生成装置１０３は、欠損値は探索対象にしないようにする。【効果】大量データから有用な知識を抽出するルール生成処理において、項目単位という制限なしに、ルールを探索する際の探索空間を削減することができ、処理量削減を実現できる。【選択図】　図１
2004139370.tif 000002
【特許請求の範囲】
【請求項１】
データに内在する規則性をルール形式で抽出する方法であって、
データを入力する手段と、
ルールを探索する空間を削減する手段と、
抽出すべきルールの帰結節を予め指定する手段と、
データの欠損値をルールの探索対象から除外しつつ、データに内在する規則性を探索して、有用なルールを有限個だけ抽出する手段と、
抽出されたルールを出力する手段とを持つことを特徴とする、データ分析方法。
【請求項２】
上記請求項１記載の有用なルールを有限個だけ抽出する手段は、深さ優先探索をすることを特徴とするデータ分析方法。
【請求項３】
上記請求項１記載の有用なルールを有限個だけ抽出する手段は、幅優先探索をすることを特徴とするデータ分析方法。
【請求項４】
上記請求項１記載の有用なルールを有限個だけ抽出する手段は、ルールごとに全データレコードを走査するのではなく、全ルールに対応するデータレコード数のカウンタを用意しておき、データレコードごとに、そのデータレコードに適合するルールのデータレコード数のカウンタを変更することを特徴とするデータ分析方法。
【請求項５】
上記請求項１乃至４記載の、ルールを探索する空間を削減する手段とは、指定された項目の指定された値を欠損値に書き換えることを特徴とするデータ分析方法。
【請求項６】
上記請求項１乃至４記載の、ルールを探索する空間を削減する手段とは、指定された値をすべての項目にわたって欠損値に書き換えることを特徴とするデータ分析方法。
【請求項７】
上記請求項１乃至４記載の、ルールを探索する空間を削減する手段とは、指定された帰結節と同時正規しない項目と値をルール探索対象から除外することを特徴とするデータ分析方法。
【請求項８】
上記請求項１乃至４記載の、ルールを探索する空間を削減する手段とは、過去に実行されたルール生成結果を参照して、結果に出現した項目以外をルールの探索対象から除外することを特徴とするデータ分析方法。
【請求項９】
上記請求項１乃至４記載の、ルールを探索する空間を削減する手段とは、過去に実行されたルール生成結果を参照して、結果に出現した項目と値以外をルールの探索対象から除外することを特徴とするデータ分析方法。
【請求項１０】
請求項１から９までのいずれかに記載のデータ分析方法をプログラム形式にして格納してあることを特徴とする記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データベースなどに格納された大量データから有用な知識を抽出するデータ分析方法に関する。また、本発明は、データマイニング技術に関する。
【０００２】
【従来の技術】
大量のデータから有用な知識を抽出する技術にデータマイニング技術がある。
【０００３】
例えば、特許文献１では、複数の項目を持つデータレコードが複数あるような、いわゆる縦かける横の表形式のデータがあった場合、そこから、ｉｆ−ｔｈｅｎルールを抽出する方法について記述がある。ここでは、ｔｈｅｎ部を「ある項目がある値を持つ」と予め指定しておき、そのｔｈｅｎ部が成り立ちやすいｉｆ−ｔｈｅｎルールで、評価尺度の高いものをいくつか出力する。また、データに欠損値が含まれるとき、これをルール生成処理から一切無視する例も開示されている。
【０００４】
【特許文献１】
特開平８−７７０１０号公報
【０００５】
【発明が解決しようとする課題】
公知例１では、ｔｈｅｎ部を予め指定してｉｆ−ｔｈｅｎルールのｉｆ部を探索する際に、予めｉｆ部で用いることができる項目を選ぶことになっている。ｉｆ部で用いることができる項目を削減することはルールの探索空間を削減することにつながり、実行時間や必要な計算機資源の削減につながる効果があるが、このような処理が項目単位でしかできないという課題がある。
【０００６】
公知例１では、ｔｈｅｎ部を予め指定してｉｆ−ｔｈｅｎルールを求める際に、データの欠損値を無視して処理することができるが、欠損値が含まれていなければ、当然そのような処理は行われない。欠損値を無視して処理を進めることは、データ分析の処理量の削減に寄与する効果があるが、当然のことながら、欠損値が存在しない限りこの恩恵にはあずかれないという課題がある。
【０００７】
本発明の目的は、大量データから有用な知識を抽出するルール生成処理において、項目単位という制限なしに、ルールを探索する際の探索空間を削減するデータ分析方法を提供することにある。
【０００８】
本発明の別の目的は、欠損値を無視して処理を進めることを処理量削減の手段とみなし、欠損値が出現しない場合にもこれを利用できるようにすることにある。
【０００９】
【課題を解決するための手段】
本発明は、データの中で、指定した項目の指定した値を欠損値に置き換える手段を持つ。
【００１０】
本発明は、縦かける横の表形式のデータから、ｉｆ−ｔｈｅｎルールを抽出する際に、ｔｈｅｎ部の項目と値を予め指定する手段を持つ。
【００１１】
本発明は、ｔｈｅｎ部で指定した項目の値と同時に起こらない項目の値を検出し、それを欠損値に置き換える手段を持つ。
【００１２】
本発明は、過去に実行されたルール生成結果を参照して、これから実行するルール探索処理において探索する項目を取捨選択する手段を持つ。
【００１３】
本発明は、過去に実行されたルール生成結果を参照して、これから実行するルール探索処理の入力データを編集する手段を持つ。その際に、前記ルール生成結果で出現した項目について、出現した値以外のすべての値を欠損値に置き換える特徴を持つ。
【００１４】
本発明は、ｔｈｅｎ部で指定した項目の値が起こりやすいｉｆ−ｔｈｅｎルールを探索する手段を持つ。その際に、データの欠損値をルールの探索対象から除外する特徴を持つ。
【００１５】
【発明の実施の形態】
以下、本発明の実施の形態の一例を詳細に説明する。
【００１６】
図１は、本発明の実施の形態の一例の構成図を示す。
【００１７】
入力装置１０１、探索空間削減装置１０２、ルール生成装置１０３、出力装置１０４、データ記憶装置１０５、パラメータ記憶装置１０６、ルール記憶装置１０７が、バスまたはネットワーク１０８を介して相互接続されている。
【００１８】
図２は本発明の実施の形態の一例のフローチャートを示す。
【００１９】
ステップ２０１はルール生成前処理である。まず、データマイニングに用いるデータを、入力装置１０１で指定し、入力装置１０１を介してデータ記憶装置１０５に記憶する。ここで、データは、図３に示すような縦かける横のいわゆる表形式のデータとなっている。１行が１レコードとなっており、１レコードが複数の項目の値を持つ。第１行だけは特殊で、項目名の並ぶ行となっている。図３は顧客データの例だが、項目としては、例えば、顧客番号、性別、年齢、ダイレクトメール応答の有無などがある。これらの項目の値がそれぞれの行に入っている。次に、データマイニングのルール生成のパラメータを入力する。このパラメータはパラメータ記憶装置１０６に記憶される。記憶されるパラメータの項目の例を図４に示す。ルール生成ＩＤはルール生成を実行するごとに与えられるユニークなＩＤである。このパラメータのデータのキーＩＤにもなっている。実行目的、ユーザはそれぞれ該当の値を入れる。入力データ識別子は例えば、入力データのファイル名を表す。結論項目は、例えば、「ｉｆ〜ｔｈｅｎダイレクトメール応答＝あり」というルールを抽出したければ、ｔｈｅｎ部の項目を示す「ダイレクトメール応答」という項目ＩＤが入る。入力項目数は、図３に示したような、性別や年齢などの項目のうち、ｉｆ部に使ってよいとして指定した項目の種類の数が入る。入力項目には、前述の入力項目数分の項目ＩＤが入る。最大条件節数は、ｉｆ部が、「項目Ａ＝ａ　＆　項目Ｂ＝ｂ」、という複数条件の論理積になる場合の条件節数の最大値である。例えばこの例だと２となる。ヒット率・カバー率レベルは、出力されるルールを序列化するための評価尺度の式中のパラメータである。ルールの良さを評価するのにはヒット率とカバー率が考えられる。ｉｆ　Ａ　ｔｈｅｎ　Ｂのルールについて、ヒット率はＰ（Ｂ｜Ａ）で、Ａが起こったときのＡ＆Ｂの事後確率である。これはルールの精度を示す。カバー率はＰ（Ａ）である。これはルールの一般性を示す。ここで、Ｐ（Ｅ）は事象Ｅが起こる確率を表す。このヒット率とカバー率はトレードオフの関係にあるので、一般にルールの良さを表す一価の評価尺度として、両者を勘案して、例えば次式を考える。
【００２０】
ｕ　＝　Ｐ（Ａ）＾α　×　Ｐ（Ｂ｜Ａ）　×　ｌｏｇ（Ｐ（Ｂ｜Ａ）／Ｐ（Ｂ））・・式１
ここで、＾はべき乗を表す。
【００２１】
ここのαをヒット率・カバー率レベルと呼ぶ。
【００２２】
出力ルール数は、出力されるルールを評価尺度順にいくつ出力させたいかという数である。全レコード数は、データの全レコード数を表す。結論適合事例数は、上記の例で言うと、Ｂを満たすレコード数である。次に、項目ごとに、その項目の値の種類の数が入る。
【００２３】
記号値であれば、その記号値の種類の数。数値であれば、それをいくつかの閾値で分けたときの種類の数が入る。カテゴリ名称には、カテゴリ数だけそれぞれの名称が入る。例えば、数値項目で３分割した場合などは、「小」、「中」、「大」などが入ることがある。次に、この項目が数値か記号値かの別が入る。数値の場合には、この次に、それぞれのカテゴリに分けるときの閾値が必要な数だけ入る。
【００２４】
ステップ２０２は探索空間削減処理である。探索空間削減装置１０２が制御を行う。ここでは、図５でその処理のユーザインターフェイスを示す。既にステップ２０１でデータマイニングに用いる入力データは入力されていて、入力項目とその値（カテゴリになったもの）はわかっているので、図５（ａ）では、まず、入力項目の一覧を出力装置１０４に出力し、その中で、一つを入力装置１０１を介して指定する。決定ボタンを押すと、図５（ｂ）に遷移し、その項目の値が列挙される。ここでは、値は０個以上複数個選ぶことができる。ここで選ばれて決定ボタンが押されると、その項目のその値は、入力データにおいてすべて決損値に置換される。図１の構成図で言えば、探索空間削減装置１０２がデータ記憶装置１０５からデータを読み込み、該当データをすべて欠損値へ置換を行った後、データ記憶装置１０５にデータマイニングへの入力データとして記憶させる。さらに、パラメータ記憶装置１０６のパラメータのデータも書き換える。すなわち、欠損値になった項目については、その値はカテゴリから取り除かれる。その項目のカテゴリ数は減り、カテゴリ名称は削除され、閾値のデータは削除される。すべての値が削除された場合には、その項目自体のエントリが削除され、さらに、入力項目数が減り、入力項目も該当するものが削除される。ここで、この処理は、単にあるデータレコード１つ（図３でいう表の１行）を元々なかったことにする、というわけではなく、また、あるレコードのある項目の値だけを欠損値に置換して、元々なかったことにする、という処理ではない。例えば、図３で言えば、購入金額が０円から５００円までが「小」とカテゴリ化されていたときに、購入金額＝小、という探索空間を元々なかったことにする目的で、すべてのデータレコードにおいて、購入金額が０円から５００円までのデータについて、購入金額を欠損値に置換する。したがって、入力データの中に、購入金額＝小（すなわち、購入金額が０円から５００円まで）のレコードが存在しなくなるため、探索空間からはずせるわけである。以上のような処理をここでは行っている。
【００２５】
ステップ２０３はルール生成処理である。ルール生成装置１０３が制御を行う。図６のような探索空間の例を考える。ｉｆのところにどのような条件節がくるかという可能性を探索している。例えば▲１▼の例では、項目Ｘ＝値ｘ１という条件節１個のみが想定されている。この条件で、式１の評価尺度ｕを計算し、出力ルール数分のルールリストを評価尺度順に並べたメモリ（図９）を保持しつつ、探索空間を探索する。深さ優先探索を行うと、次に▲２▼のルールを試す。▲２▼は、ｉｆ部が、項目Ｘ＝値ｘ１　＆　項目Ｙ＝値ｙ１という条件節２個の論理積を表している。ここでも評価尺度ｕを計算し、前記の出力ルール数分のルールリストを評価尺度順に並べたメモリ（図９）に入れば入れるし、それよりも悪いルールであれば入れない。同様に▲３▼は３条件節の論理積を示す。このように図６の探索空間における縦方向には、最大条件節数まで進む。この探索空間で注意することは、欠損値は探索対象に入らないことである。前述したように、欠損値は既にカテゴリとして存在しないことになっているので、値として探索候補になることはない。また、当然のことながら、項目Ｘ＝値ｘ１を選んだとき、その下方向に探索するときにはもう項目Ｘの別の値を探索しなくてよい。一つの項目は一つの値しか持たないため、項目を一つ選べば、それと論理積を作るのはそれとは別の項目である。このように探索していけば、最終的に、最後の入力項目の最後の値という１条件節をチェックした時点で探索は終了する。最後の入力項目を含む２条件以上の論理積の条件については、既に事前に探索済みだからである。
【００２６】
ステップ２０４はルール出力処理である。この結果を出力装置１０４に出力し、さらに、ルール記憶装置１０７に記憶する。出力装置１０４からの出力例を図７に示す。ｉｆ部とｔｈｅｎ部がそれぞれ出力され、同時に、ヒット率、カバー率、評価尺度が示されている。このルールリストは、出力ルール数の数だけ、評価尺度順に出力されている。上部にある事前確率は、
（事前確率）　＝　（結論適合事例数）／（全レコード数）　・・式２
である。ｉｆ部をランダムに選んだときのルールのヒット率の期待値と考えられる。ヒット率はこの事前確率より高いことが少なくともよいルールの条件である。
【００２７】
以上本発明によれば、大量データから有用な知識を抽出するルール生成処理において、項目単位という制限なしに、ルールを探索する際の探索空間を削減することができる。さらに、ある項目がある値になることをルールで探索しなくてよい場合には予めそれを探索範囲から省いておくことができ、処理量削減を実現できる。
【００２８】
以上述べた実施の形態は次のように変更して実施することも可能である。
【００２９】
第一に、ステップ２０３のルール生成処理は、深さ優先探索であったが、幅優先探索であっても構わない。
【００３０】
第二に、ステップ２０３のルール生成処理は、深さ優先探索であり、上述の第一の変更例は、幅優先探索であったが、これらの二つの実施の形態のように、一つの条件について全レコードで評価して、それが終わってから次の条件に移る、という方法ではなくて、レコードを一つ読み込み、、そのレコードが満たす条件を全条件の中からを探して、予め条件ごとに用意していたカウンタをカウントアップし、その処理が終わったら、次にまたレコードを一つ読み込んで同様に処理を進める、という方法でも構わない。具体的には、それぞれの条件のところに、結論部を満たすカウンタと結論部を満たさないカウンタの二つを用意しておく。すなわち、条件Ａ（これは複数条件節の論理積をも意味するとする）ごとに、Ｎ（Ａ＆Ｂ）とＮ（Ａ＆！Ｂ）の二つのカウンタを用意する。ここで、Ｎ（Ｅ）は事象Ｅのレコード数を示す。！Ｅは事象Ｅの余事象を示す。Ｂは結論部を示す。あるレコードに対して、それが結論部を満たすかどうかは明らかにわかる。また、全条件のうち、そのレコードの項目の値の組み合わせと合致する条件もすべて決定できる。その条件に対して、結論部を満たす場合にはＮ（Ａ＆Ｂ）のカウンタを１だけカウントアップし、結論部を満たさない場合には、Ｎ（Ａ＆！Ｂ）のカウンタを１だけカウントアップする。そのレコードが満たす条件をすべて処理し終われば、次のレコードの処理に移る。すべてのレコードの処理が終われば、それぞれの条件について、Ｐ（Ａ）、Ｐ（Ｂ｜Ａ）を計算できる。
Ｐ（Ａ）＝（Ｎ（Ａ＆Ｂ）＋Ｎ（Ａ＆！Ｂ））／全レコード数・・式３
Ｐ（Ｂ｜Ａ）＝Ｎ（Ａ＆Ｂ）／（Ｎ（Ａ＆Ｂ）＋Ｎ（Ａ＆！Ｂ））ただし、分母が０（すなわちＰ（Ａ）が０）のときにはこの計算を行わない。
・・式４
Ｐ（Ａ）が０のときには、これが良いルールであることはないので、出力ルールには入れない。
【００３１】
この変更例によれば、データは１度しか読まないので、データは計算機のオンメモリになくて２次記憶装置にあったとしても、十分に効率的に処理が行える。また、全レコードを処理し終わる前に処理を停止して、途中経過としてルールの結果を表示できる。これは、例えば重要な、あるいは信頼性の高いデータから順に処理を行う際に有用である。また、例えば１００万件のレコードを分析する際に、レコードの順をランダムにしておいて、最初の１０００件の結果からだいたいのルール結果を出すときなどに有用である。また、上記のように処理の停止・途中経過の表示だけでなく、処理をそこから再開することも可能である。再開した後、また停止・途中経過表示もできるし、最後のレコードまで処理を終えて結果表示をすることもできる。また、データを１度しか読まないために、インクリメンタルな処理が可能となる。例えば、時系列のデータを順次データマイニング処理したいケースを考える。毎日、直近の１ヶ月のデータをデータマイニングしたい場合に、最初に１度だけ１ヶ月分のデータでデータマイニング処理をしておけば、その後の毎日の処理は、昨日分のレコードのカウントアップと、１ヶ月前の今日のレコードのカウントダウンの２日分の処理だけで済む。これは、データ分析処理の対象データのデータ量と、実際に処理するデータ量を無関係にできる効果を持ち、データ処理の効率を上げる。
【００３２】
第３に、ステップ２０２の探索空間削減処理は、任意の項目の任意の値を欠損値に変更していたために、まず項目を選び、その次にその項目の値を選んでいたが、例えばある値を持つすべての項目について欠損値に置換するという処理に変更できる。例えば、すべての項目について、値０をすべて欠損値に置換する、などの処理が考えられる。図８にそのユーザインタフェースを示す。まず、図８（ａ）では値を入れる。例えば、０を入力して決定ボタンを押す。次に画面は図８（ｂ）に遷移する。ここでは、値０のあった項目と、そのレコード数が一覧できる。ここである項目を指定すると、その項目に関しては値０の欠損値への置換を保留できる。決定ボタンを押せば確定して、データ記憶装置１０５のデータ、及び、パラメータ記憶装置１０６のデータが書き換えられる。この書き換え処理については上述のステップ２０２で記した通りである。
【００３３】
本変更例によれば、例えば、値０をすべて探索対象からはずし、出力されるルールには「何々がない」という述語が出ないようにしたいケースにおいて、当初の実施の形態によるよりはよりユーザが少ない労力ですべての項目での置換の指示が行える。
【００３４】
第４に、ステップ２０２の探索空間削減処理は、ユーザ入力を期待しているが、これをデータから自動的に行うようにすることも可能である。具体的には、第１の変更例にある幅優先探索で、１条件節のルールを一度ステップ２０２で先行して行ってしまう。そうすると、どの項目＝値の組み合わせが、結論項目と１レコードも同時生起がなかったかわかる。結論項目を１レコードも満たさない項目＝値の組み合わせはすべてデータにさかのぼってその値を欠損値に置換する。また、パラメータ記憶装置１０６のパラメータの値も書き換える。その後、改めてステップ２０３のルール生成処理に移る。本変更例によれば、最後のルール結果には決して出てこない条件を予め探索対象から削除することができ、処理を効率化できる。
【００３５】
第５に、ステップ２０２の探索空間削減処理で、過去の同じデータを元にした、最大条件節数が小さいルール生成結果を参照することによって、より最大条件節数が大きいルール生成をするときの探索空間を削減することができるように変更することが可能である。
【００３６】
例えば、今、最大条件節数３のルール生成を行おうとしているときに、同じデータを元にした、最大条件節数２の過去のルール生成結果があったとする。出力ルール数が１００とした場合、そこには、ｉｆ部に重複も含めて項目が高々２００個あるわけだが、そこに登場した項目のみを用いることにして、ルール生成を行う。項目の削減は、パラメータ記憶装置１０６のパラメータのデータのうち、入力項目数と入力項目と項目ごとのエントリ（カテゴリの情報部分）を編集することで可能である。また、出力ルール数が１００個だから１００ルールで見るのではなく、上からＮ個だけ選んでもよい。この変更例によれば、全探索はあきらめることになるかも知れないが、より高次の最大条件節数のルール生成をより簡単に行うことができる。
【００３７】
第６に、上記第５の変更例同様に、ステップ２０２の探索空間削減処理で、過去の同じデータを元にした、最大条件節数が小さいルール生成結果を参照する場合に、第５の変更例のように、項目単位で取捨選択するのではなく、項目と値の組み合わせで探索空間を削減するように変更することも可能である。例えば、今、最大条件節数３のルール生成を行おうとしているときに、同じデータを元にした、最大条件節数２の過去のルール生成結果があったとする。出力ルール数が１００とした場合、そこには、ｉｆ部に重複も含めて項目が高々２００個あるわけだが、そこに登場した項目の値のみを用いることにして、ルール生成を行う。具体的にはまず、項目単位の削減は、第５の変更例をそのまま用いる。さらに、項目としては出現するが、値として出現していないものがあれば、その出現していない値についてはすべて欠損値に置換する。これは、データ記憶装置１０５への変更、並びに、パラメータ記憶装置１０６の項目ごとのエントリ（カテゴリの情報部分）の変更によって実現できる。また、出力ルール数が１００個だから１００ルールで見るのではなく、上からＮ個だけ選んでもよい。この変更例によれば、全探索はあきらめることになるかも知れないが、より高次の最大条件節数のルール生成をより簡単に行うことができる。また、一つの値しか登場しない項目があった場合、他のすべての値について探索することはなくなるので第５の変更例よりさらに探索範囲を減らすことが可能となる。
【００３８】
【発明の効果】
以上本発明によれば、大量データから有用な知識を抽出するルール生成処理において、項目単位という制限なしに、ルールを探索する際の探索空間を削減することができ、処理量削減を実現できる。
【図面の簡単な説明】
【図１】本発明の実施の形態の一例の構成図。
【図２】本発明の実施の形態の一例のフローチャート。
【図３】入力データの例。
【図４】パラメータの項目。
【図５】探索空間削減処理の一例。
【図６】探索空間の例。
【図７】出力ルールの例。
【図８】第３の変更例。
【図９】評価尺度順にルールを並べたメモリ。
【符号の説明】
１０１…入力装置、１０２…探索空間削減装置、１０３…ルール生成装置、１０４…出力装置、１０５…データ記憶装置、１０６…パラメータ記憶装置、１０７…ルール記憶装置、１０８…バスまたはネットワーク。
【図１】
2004139370.tif 000003
【図２】
2004139370.tif 000004
【図３】
2004139370.tif 000005
【図４】
2004139370.tif 000006
【図５】
2004139370.tif 000007
【図６】
2004139370.tif 000008
【図７】
2004139370.tif 000009
【図８】
2004139370.tif 000010
【図９】
2004139370.tif 000011