(57)【要約】【課題】  規則による行動属性変更プランをデータベースから自動的に発見する。【解決手段】  意思決定者に値が制御不可能および制御可能な属性である状態属性および行動属性、および結果属性を含むデータベースと、事例の好ましさを評価する事例評価関数とを用いて、事例の好ましさが向上する行動属性の値の変更方法を発見する。各領域において結果属性の値の分布が所定の結果属性分布基準を満たすように状態属性および行動属性による属性空間を分割して複数の状態領域および複数の行動領域を求め、各領域において行動属性の値が所定の行動属性分布基準を満たすように状態空間を分割して複数の政策評価状態領域を生成し、複数の状態領域と複数の政策評価状態領域とを用いて領域交差計算を行って複数の詳細状態領域を求め、詳細状態領域に属する事例集合の好ましさが向上する行動属性の値の変更方法を、詳細状態領域から前記行動領域への写像である政策改善ルールとして求める。【選択図】  図１
2006139469.tif 000002
【特許請求の範囲】
【請求項１】
意思決定者には値が制御不可能な属性である状態属性、意思決定者に値が制御可能な属性である行動属性、および結果属性を含む、複数の事例からなるデータベースと、
少なくとも前記行動属性の値および前記結果属性の値を用いて前記事例の好ましさを定量的に評価する事例評価関数とを用いて、
前記事例の好ましさが向上する前記行動属性の値の変更方法を発見する政策データマイニング装置であって：
前記状態属性および前記行動属性により形成される属性空間の部分領域に属する前記事例集合の結果属性の値が前記部分領域において所定の結果属性分布基準を満たすように、前記状態属性による状態空間を複数の状態領域に分割し且つ前記行動属性による行動空間を複数の行動領域に分割する、状態および行動領域生成手段と；
前記状態属性による状態空間を複数の政策評価状態領域に分割し、各前記政策評価状態領域に属する前記事例に含まれる行動属性の値は所定の行動属性分布基準を満たす政策評価状態領域生成手段と；
前記複数の状態領域と前記複数の政策評価状態領域とを用いて領域交差計算を行って複数の詳細状態領域を求める詳細状態領域生成手段と；
前記データベースと前記事例評価関数とを用いて、前記詳細状態領域に属する事例集合の好ましさが向上する前記行動属性の値の変更方法を、前記詳細状態領域から前記行動領域への写像である政策改善ルールとして生成する政策改善ルール生成手段と；
を備えた政策データマイニング装置。
【請求項２】
前記政策改善ルール生成手段は：
前記政策評価状態領域に含まれる前記データベース中の事例が前記複数の行動領域の各々に含まれる頻度に基づいて各前記行動領域に前記事例が含まれる確率をそれぞれ求め、前記政策評価状態領域に対して求めた前記確率の集合を政策ルールとして取得する政策ルール生成手段と；
各前記状態領域について、前記状態領域に含まれる前記事例を前記行動領域ごとに分類し、前記行動領域ごとに分類された事例集合を前記事例評価関数を用いて評価することにより前記行動領域ごとの評価値を算出し、さらに前記行動領域のうち最も高い評価を示す前記行動領域を最適行動として決定する最適行動決定手段と；
前記政策ルールと、各前記状態領域についての前記行動領域ごとの評価値および前記最適行動と、前記複数の詳細状態領域とを用いて、前記詳細状態領域の各々に対して、前記詳細状態領域に含まれる事例集合の行動属性の値を全て前記最適行動に変更することによる前記事例集合の好ましさの変化量を政策改善評価値として算出し、前記政策改善評価値が所定の採択条件を満たす場合は、前記詳細状態領域から前記最適行動への写像を前記政策改善ルールとして採択する政策改善ルール選択手段と；
を有することを特徴とする請求項１に記載の政策データマイニング装置。
【請求項３】
前記政策改善ルール選択手段は、前記政策改善評価値の算出において、前記詳細状態領域に含まれる事例集合が前記最適行動に従った場合に得られる前記事例評価関数の期待値から、前記詳細状態領域に含まれる事例集合が前記政策ルールに従った場合に得られる前記事例評価関数の期待値を減じる計算を含むこと、
を特徴とする請求項２に記載の政策データマイニング装置。
【請求項４】
前記政策改善ルール選択手段は、前記政策改善評価値の算出において、前記詳細状態領域に含まれる事例集合が前記最適行動に従った場合に得られる前記事例評価関数の期待値から、前記詳細状態領域に含まれる事例集合が前記政策ルールに従った場合に得られる前記事例評価関数の期待値を減じ、さらに前記政策ルールを前記最適行動に変更するコストを表す政策変更コストを減じる計算を含むこと、
を特徴とする請求項２に記載の政策データマイニング装置。
【請求項５】
意思決定者には値が制御不可能な属性である状態属性、意思決定者に値が制御可能な属性である行動属性、および結果属性を含む、複数の事例からなるデータベースと、
少なくとも前記行動属性の値および前記結果属性の値を用いて前記事例の好ましさを定量的に評価する事例評価関数とを用いて、
前記事例の好ましさが向上する前記行動属性の値の変更方法を発見する、コンピュータで実行される政策データマイニングプログラムであって：
前記状態属性および前記行動属性により形成される属性空間の部分領域に属する前記事例集合の結果属性の値が前記部分領域において所定の結果属性分布基準を満たすように、前記状態属性による状態空間を複数の状態領域に分割し且つ前記行動属性による行動空間を複数の行動領域に分割する、状態および行動領域生成ステップと；
前記状態属性による状態空間を複数の政策評価状態領域に分割し、各前記政策評価状態領域に属する前記事例に含まれる行動属性の値は所定の行動属性分布基準を満たす政策評価状態領域生成ステップと；
前記複数の状態領域と前記複数の政策評価状態領域とを用いて領域交差計算を行って複数の詳細状態領域を求める詳細状態領域生成ステップと；
前記データベースと前記事例評価関数とを用いて、前記詳細状態領域に属する事例集合の好ましさが向上する前記行動属性の値の変更方法を、前記詳細状態領域から前記行動領域への写像である政策改善ルールとして生成する政策改善ルール生成ステップと；
を備えた政策データマイニングプログラム。
【請求項６】
前記政策改善ルール生成ステップは：
前記政策評価状態領域に含まれる前記データベース中の事例が前記複数の行動領域の各々に含まれる頻度に基づいて各前記行動領域に前記事例が含まれる確率をそれぞれ求め、前記政策評価状態領域に対して求めた前記確率の集合を政策ルールとして取得する政策ルール生成ステップと；
各前記状態領域について、前記状態領域に含まれる前記事例を前記行動領域ごとに分類し、前記行動領域ごとに分類された事例集合を前記事例評価関数を用いて評価することにより前記行動領域ごとの評価値を算出し、さらに前記行動領域のうち最も高い評価を示す前記行動領域を最適行動として決定する最適行動決定ステップと；
前記政策ルールと、各前記状態領域についての前記行動領域ごとの評価値および前記最適行動と、前記複数の詳細状態領域とを用いて、前記詳細状態領域の各々に対して、前記詳細状態領域に含まれる事例集合の行動属性の値を全て前記最適行動に変更することによる前記事例集合の好ましさの変化量を政策改善評価値として算出し、前記政策改善評価値が所定の採択条件を満たす場合は、前記詳細状態領域から前記最適行動への写像を前記政策改善ルールとして採択する政策改善ルール選択ステップと；
を有することを特徴とする請求項５に記載の政策データマイニングプログラム。
【請求項７】
前記政策改善ルール選択ステップは、前記政策改善評価値の算出において、前記詳細状態領域に含まれる事例集合が前記最適行動に従った場合に得られる前記事例評価関数の期待値から、前記詳細状態領域に含まれる事例集合が前記政策ルールに従った場合に得られる前記事例評価関数の期待値を減じる計算を含むこと、
を特徴とする請求項６に記載の政策データマイニングプログラム。
【請求項８】
前記政策改善ルール選択ステップは、前記政策改善評価値の算出において、前記詳細状態領域に含まれる事例集合が前記最適行動に従った場合に得られる前記事例評価関数の期待値から、前記詳細状態領域に含まれる事例集合が前記政策ルールに従った場合に得られる前記事例評価関数の期待値を減じ、さらに前記政策ルールを前記最適行動に変更するコストを表す政策変更コストを減じる計算を含むこと、
を特徴とする請求項６に記載の政策データマイニングプログラム。
【請求項９】
意思決定者には値が制御不可能な属性である状態属性、意思決定者に値が制御可能な属性である行動属性、および結果属性を含む、複数の事例からなるデータベースと、
少なくとも前記行動属性の値および前記結果属性の値を用いて前記事例の好ましさを定量的に評価する事例評価関数とを用いて、
前記事例の好ましさが向上する前記行動属性の値の変更方法を発見する政策データマイニング方法であって：
前記状態属性および前記行動属性により形成される属性空間の部分領域に属する前記事例集合の結果属性の値が前記部分領域において所定の結果属性分布基準を満たすように、前記状態属性による状態空間を複数の状態領域に分割し且つ前記行動属性による行動空間を複数の行動領域に分割する、状態および行動領域生成ステップと；
前記状態属性による状態空間を複数の政策評価状態領域に分割し、各前記政策評価状態領域に属する前記事例に含まれる行動属性の値は所定の行動属性分布基準を満たす政策評価状態領域生成ステップと；
前記複数の状態領域と前記複数の政策評価状態領域とを用いて領域交差計算を行って複数の詳細状態領域を求める詳細状態領域生成ステップと；
前記データベースと前記事例評価関数とを用いて、前記詳細状態領域に属する事例集合の好ましさが向上する前記行動属性の値の変更方法を、前記詳細状態領域から前記行動領域への写像である政策改善ルールとして生成する政策改善ルール生成ステップと；
を備えた政策データマイニング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースから意思決定に役立つ知識を発見する政策データマイニング装置、政策データマイニングプログラムおよび政策データマイニング方法に関する。
【背景技術】
【０００２】
多くの属性からなる事例を蓄積したデータベースを用いて、意思決定者に有益な知識を発見するために、様々なデータマイニング技術が提案されている。例えば、クラスタリング技術は事例を似たグループに分類し、決定木技術は指定した属性を予測するための分類モデルを他の属性を用いて構築し、相関ルール発見技術は属性間に成立する規則性をルールとして発見することが可能である。意思決定者はこれらの知識を利用することで、これらの知識を利用しない場合と比較して質の高い意思決定を行うことが期待されている。
【０００３】
しかしながら、ある属性とある属性との関係が明らかになったり、ある属性を他の属性から予測する手段が明らかになったりしても、意思決定者がどのように意思決定の質を高めるべきかはこれらの知識からは得られない。例えば、商品の属性から売れ行きを正確に予測する方法が得られたとしても、利益を最大化するには何をすべきかが示されるわけではない。
【０００４】
特開2004-185598公報 に開示されたマーケティングシステムに関する発明では、意思決定者であるマーケッターが顧客にどのようなマーケティングアクション(ダイレクトメールなど)をすべきか、というプランを策定するための分析システムが示されている。しかし、プランを効率的に策定するための方法は示されていない。また、マーケティング以外の様々な問題領域に利用する方法は示されていない。
【０００５】
データベース中の事例の属性には意思決定者が制御可能な属性(以下行動属性と呼ぶ)と制御不可能な属性(以下状態属性と呼ぶ)とが存在する場合がある。行動属性の値は、状態属性の値と無関係なこともあれば状態属性の値に応じて何らかの法則に基づいて決定されていることもある。そのようなデータベースに対して、意思決定者の目的に応じて事例の好ましさを評価するための事例評価関数を用意し、どのように行動属性を変更すれば事例評価関数値が高くなるかというプランを自動的に発見できれば、意思決定者が行動属性を変化させるという意思決定を行うことにより、様々な問題領域において目的に応じて意思決定の質を改善できると考えられる。
【０００６】
Mining case bases for action recommendation, Q.Yang, and H.Cheng,Proceedings of IEEE International Conference on Data Mining 2002, (ICDM2002)に示されたデータマイニング方法では、好ましいと判断された実際の事例を事例ベースに保持し、好ましくないと判断された事例の属性を変化させて事例ベースの好ましい事例に等しくなるように変更するプランのうち、最も低コストなプランを探索することで、一般的な問題において行動属性を変更させるためのプランを自動的に発見することを可能にしている。
【特許文献１】特開2004-185598公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来の手法はある事例に対しての行動属性変更プランを発見することはできるが、例えば、状態属性がA という条件を満たす事例は行動属性をB という条件を満たすように変化させる、というような規則による行動属性変更プランを発見することができなかった。その結果、意思決定者は現状の意思決定のどこが問題なのか把握することが困難だった。また、行動属性変更プランを実行したらどの程度事例の好ましさが向上するのかを定量的に推定することもできなかった。
【０００８】
本発明は以上のような問題を解決するためになされたものであり、その目的は、様々な問題領域において、事例の好ましさを向上させるための、規則による行動属性変更プラン(政策改善ルール)をデータベースから自動的に発見することが可能な政策データマイニング装置、政策データマイニングプログラムおよび政策データマイニング方法を提供することにある。
【課題を解決するための手段】
【０００９】
本発明の一態様に従った政策データマイニング装置は、意思決定者には値が制御不可能な属性である状態属性、意思決定者に値が制御可能な属性である行動属性、および結果属性を含む、複数の事例からなるデータベースと、少なくとも前記行動属性の値および前記結果属性の値を用いて前記事例の好ましさを定量的に評価する事例評価関数とを用いて、前記事例の好ましさが向上する前記行動属性の値の変更方法を発見する政策データマイニング装置であって：前記状態属性および前記行動属性により形成される属性空間の部分領域に属する前記事例集合の結果属性の値が前記部分領域において所定の結果属性分布基準を満たすように、前記状態属性による状態空間を複数の状態領域に分割し且つ前記行動属性による行動空間を複数の行動領域に分割する、状態および行動領域生成手段と；前記状態属性による状態空間を複数の政策評価状態領域に分割し、各前記政策評価状態領域に属する前記事例に含まれる行動属性の値は所定の行動属性分布基準を満たす政策評価状態領域生成手段と；前記複数の状態領域と前記複数の政策評価状態領域とを用いて領域交差計算を行って複数の詳細状態領域を求める詳細状態領域生成手段と；前記データベースと前記事例評価関数とを用いて、前記詳細状態領域に属する事例集合の好ましさが向上する前記行動属性の値の変更方法を、前記詳細状態領域から前記行動領域への写像である政策改善ルールとして生成する政策改善ルール生成手段と；を備える。
【００１０】
本発明の一態様に従った政策データマイニングプログラムは、意思決定者には値が制御不可能な属性である状態属性、意思決定者に値が制御可能な属性である行動属性、および結果属性を含む、複数の事例からなるデータベースと、少なくとも前記行動属性の値および前記結果属性の値を用いて前記事例の好ましさを定量的に評価する事例評価関数とを用いて、前記事例の好ましさが向上する前記行動属性の値の変更方法を発見する、コンピュータで実行される政策データマイニングプログラムであって：前記状態属性および前記行動属性により形成される属性空間の部分領域に属する前記事例集合の結果属性の値が前記部分領域において所定の結果属性分布基準を満たすように、前記状態属性による状態空間を複数の状態領域に分割し且つ前記行動属性による行動空間を複数の行動領域に分割する、状態および行動領域生成ステップと；前記状態属性による状態空間を複数の政策評価状態領域に分割し、各前記政策評価状態領域に属する前記事例に含まれる行動属性の値は所定の行動属性分布基準を満たす政策評価状態領域生成ステップと；前記複数の状態領域と前記複数の政策評価状態領域とを用いて領域交差計算を行って複数の詳細状態領域を求める詳細状態領域生成ステップと；前記データベースと前記事例評価関数とを用いて、前記詳細状態領域に属する事例集合の好ましさが向上する前記行動属性の値の変更方法を、前記詳細状態領域から前記行動領域への写像である政策改善ルールとして生成する政策改善ルール生成ステップと；を備える。
【００１１】
本発明の一態様に従った政策データマイニング方法は、意思決定者には値が制御不可能な属性である状態属性、意思決定者に値が制御可能な属性である行動属性、および結果属性を含む、複数の事例からなるデータベースと、少なくとも前記行動属性の値および前記結果属性の値を用いて前記事例の好ましさを定量的に評価する事例評価関数とを用いて、前記事例の好ましさが向上する前記行動属性の値の変更方法を発見する政策データマイニング方法であって：前記状態属性および前記行動属性により形成される属性空間の部分領域に属する前記事例集合の結果属性の値が前記部分領域において所定の結果属性分布基準を満たすように、前記状態属性による状態空間を複数の状態領域に分割し且つ前記行動属性による行動空間を複数の行動領域に分割する、状態および行動領域生成ステップと；前記状態属性による状態空間を複数の政策評価状態領域に分割し、各前記政策評価状態領域に属する前記事例に含まれる行動属性の値は所定の行動属性分布基準を満たす政策評価状態領域生成ステップと；前記複数の状態領域と前記複数の政策評価状態領域とを用いて領域交差計算を行って複数の詳細状態領域を求める詳細状態領域生成ステップと；前記データベースと前記事例評価関数とを用いて、前記詳細状態領域に属する事例集合の好ましさが向上する前記行動属性の値の変更方法を、前記詳細状態領域から前記行動領域への写像である政策改善ルールとして生成する政策改善ルール生成ステップと；を備える。
【発明の効果】
【００１２】
本発明により、様々な問題領域において、事例の好ましさを向上させるための、規則による行動属性変更プランをデータベースから自動的に発見することができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面に基づいて、本発明の実施の形態について説明する。
【００１４】
図１は、本発明に関わる政策（ポリシー）データマイニング装置の一実施の形態を示した構成図である。図１に示されるように、この政策データマイニング装置は、データベース１０１、状態分割格納手段１０２、行動分割格納手段１０３、政策評価状態分割格納手段１０４、政策変更状態分割生成手段１０５、政策変更状態分割格納手段１０６、事例評価関数格納手段１０７、政策改善ルール生成手段１０８、政策改善ルール格納手段１０９、状態・行動分割生成手段１１０、および、政策評価状態分割生成手段１１１を備えている。各手段による機能は、ハードウェア処理によって、またはプログラムをコンピュータに実行させることによって達成される。
【００１５】
データベース１０１には、それぞれ少なくとも一つ以上の状態属性、行動属性および結果属性からなるデータベースレコードが保存されていなければならない。
【００１６】
図３はデータベースの例であり、一つのレコードがある商品の販売事例を表している。図３のデータベースの属性３０１には、状態属性（意思決定者が制御不可能な属性）として、{M, T, K}のいずれかの値をとる「タイプ(商品タイプを表す)」という離散属性と「品質(商品の品質を表す)」という連続属性とが含まれている。また、行動属性（意思決定者が制御可能な属性）として、「価格(商品の販売価格を表す)」という連続属性が含まれている。さらに、{良, 普, 悪}のいずれかの値をとる「売れ行き(商品の売れ行きを表す)」という結果属性が含まれている。データベーステーブル３０２には、これらの属性からなる複数の事例が表形式で保存されている。
【００１７】
なお、ある属性が状態属性か行動属性かは分析者の立場や分析の目的によって変わることがある。図３の属性の場合でも、例えば意思決定者が商品の設計者ならば、品質属性は制御可能であるので行動属性になることもある。
【００１８】
以下では、状態属性空間をX, 行動属性空間をA, 結果属性空間をR で表す。そして、データベースの一つの事例を
【数１】
2006139469.tif 000003
と表す。
【００１９】
図１において、状態・行動分割生成手段１１０では、データベース１０１に保存された事例データを用いて、状態属性と行動属性によって決まる属性空間の部分領域に含まれるデータベースの１０１事例に関して、結果属性の値の分布が均一になるように状態分割{Xi}と行動分割{Ak}を生成し、状態分割格納手段１０２と行動分割格納手段１０３にそれぞれ格納する。
【００２０】
すなわち、このようにして得られた状態分割と行動分割には、例えば、Xi とAk を指定すると：
【数２】
2006139469.tif 000004
という近似関係が成り立つ。
【００２１】
ここでProb(A|B)はB が成立する条件下でA が成立する確率を表す関数である。このことにより、Xi の任意の部分空間X’における結果属性の分布を新たに計算しなくてもXi とAk に対応する領域での分布によって代用することができるので、政策改善ルールの探索を効率化することが可能になる。
【００２２】
さらに、行動属性と結果属性とによって決まる事例評価関数f(a, r)を用いた場合の領域Xi,×Ak 内の事例評価の期待値V(Xi, Ak)：
【数３】
2006139469.tif 000005
に関しても、近似的に：
【数４】
2006139469.tif 000006
という関係が成り立つ。
【００２３】
このことにより、Xi の任意の部分空間X’における事例評価の期待値を新たに計算しなくてもXi とAk に対応する領域の事例評価期待値によって代用することができるので、政策改善ルールの探索を効率化することが可能になる。
【００２４】
状態分割と行動分割を求める方法としては、例えば、結果属性を予測する決定木(以下、結果決定木と呼ぶ)を用いる方法がある。決定木においてノード分割に用いられる属性の境界情報を用いて状態分割と行動分割を求めることができる。
【００２５】
図４は図３のデータに対する結果決定木の例であり、売れ行き属性を予測するために属性空間を(品質: {0.9}, 価格: {60,90}, タイプ: {M})という境界で分割している。これらの境界情報の中で状態属性のものを集めて状態分割を生成し、行動属性のものを集めて行動分割を生成することができる。
【００２６】
図５は図４の結果決定木４０１から生成された状態分割の例であり、状態属性である品質とタイプの境界を用いることにより、 {X1, X2, X3, X4}の4 つの要素からなる状態分割が生成されている。
【００２７】
また、図６は図４の結果決定木４０１から生成された行動分割の例であり、行動属性である価格の境界を用いることにより、{A1, A2, A3}の3 つの要素からなる行動分割が生成されている。
【００２８】
なお、以下では事例の状態属性値x が状態領域Xi に含まれる場合、この事例の状態がXi であると表現し、事例の行動属性値a が行動領域Ak に含まれる場合、この事例の行動がAk であると表現する。また、ある属性空間に含まれる事例の行動がAkとなる確率をすべての行動に対して集めたものを行動分布と呼ぶ。
【００２９】
図１において、政策評価状態分割生成手段１１１では、データベース１０１に保存された事例データと、行動分割格納手段１０３に格納された行動分割とを用いて、政策評価状態分割{Yj}を、状態がYj である事例の行動分布が均一になるように生成し、政策評価状態分割格納手段１０４に格納する。
【００３０】
すなわち、このようにして得られた政策評価状態分割{Yj}の要素には、近似的に：
【数５】
2006139469.tif 000007
という関係が成り立つ。
【００３１】
そこで、状態がY である事例の行動がA である確率をπ(Y, A)、全ての{Ak}の要素についてπ(Y, Ak)を集めたベクトル(状態Y の政策ベクトル)をπ(Y)と表すと、政策評価状態分割{Yj}の要素（政策評価状態領域）Yj に関して：
【数６】
2006139469.tif 000008
という関係が成り立つ。
【００３２】
このことにより、Yj の任意の部分空間Y’における政策ベクトルを新たに計算しなくてもYj の政策ベクトルで代用することができるので、政策改善ルールの探索を効率化することが可能になる。
【００３３】
また、状態領域Yj 内の行動分布は均一なので、政策評価状態分割{Yj}はデータベース中の事例における状態領域と行動領域との関係を最もシンプルに表すために適した状態分割と考えられる。そこで、政策評価状態分割{Yj}によって決定される各状態領域について、政策（行動）を評価改善する政策改善ルールを探索する。
【００３４】
政策評価状態分割を求める方法としては、例えば、行動分割を予測する決定木(以下、行動決定木と呼ぶ)を用いる方法がある。決定木においてノード分割に用いられる属性の境界情報を用いて政策評価状態分割を求めることができる。
【００３５】
図７は図３のデータと図６の行動分割に対する行動決定木の例であり、属性空間を(品質: {0.8})という境界で分割している。
【００３６】
これらの境界情報を集めて政策評価状態分割を生成することができる。
【００３７】
図８は図７の行動決定木７０１から生成された政策評価状態分割の例であり、{Y1, Y2}の2 つの要素からなる政策評価状態分割が生成されている。
【００３８】
図１において、政策変更状態分割生成手段１０５では、政策評価状態分割格納手段１０４に格納された各状態領域Yj に対して、状態分割格納手段１０２に格納された状態分割{Xi}を用いて領域交差計算を行うことで、詳細状態領域Z(j)hを生成し、生成した詳細状態領域Z(j)hの集合{Z(j)h}を政策変更状態分割として政策変更状態分割格納手段１０６に格納する。この詳細状態領域Z(j)hが最終的な政策改善ルールの条件部に相当する。
【００３９】
図９は、図８の政策評価状態分割に対して、図５の状態分割を用いて領域交差計算を行うことによって得られた政策変更状態分割９０１であり、各Yj について、詳細状態領域Z(j)hが求められている。
【００４０】
図２は、図１の政策改善ルール生成手段１０８の構成を詳細に示した構成図である。
【００４１】
図２に示されるように、この政策改善ルール生成手段１０８は、政策ルール生成手段２０１、政策ルール格納手段２０２、最適行動決定手段２０３、最適行動格納手段２０４および政策改善ルール選択手段２０５を備えている。
【００４２】
政策ルール生成手段２０１は、データベース１０１の事例、政策評価状態分割格納手段１０４に格納された政策評価状態分割、および、行動分割格納手段１０３に格納された行動分割を用いて、政策評価状態分割の各要素Yj について、状態がYj となるデータベース中の事例が行動Ak となる頻度をカウントすることで、その状態領域の行動確率である政策ベクトルを計算し、これらの政策ベクトルの集合を政策ルールとして政策ルール格納手段２０２に格納する。
【００４３】
図１１は政策ルール１１０１の例であり、各Yj について、行動分割{Ak}の全ての要素に関して確率値が計算されている。例えば状態領域Y1 における行動領域A1 の確率π(Y1,A1)（政策ベクトル）は：
【数７】
2006139469.tif 000009
と求められている。
【００４４】
図２において、最適行動決定手段２０３は、データベース１０１の事例、事例評価関数格納手段１０７に格納された事例評価関数、状態分割格納手段１０２に格納された状態分割、および、行動分割格納手段１０３に格納された行動分割を用いて、状態分割の各状態領域Xi について、状態がXi となるデータベース中の事例を行動ごとに分類し、分類された事例集合を事例評価関数に基づいて評価する。最も高い評価値を示す行動をXi の最適行動A*(Xi)として決定し、各行動の評価値とともに最適行動格納手段２０４に格納する。
【００４５】
分類された事例集合と事例評価関数とに基づいて領域の評価を行う方法としては様々な方法が考えられる。最も一般的なのは、領域内の事例評価期待値(平均値)である。例えば、事例評価関数が事例の行動属性a と結果属性r に依存するf(a,r)という関数の場合、Xi とAk によって決まる領域の評価値V(Xi, Ak)は：
【数８】
2006139469.tif 000010
となる。
【００４６】
この他、領域内のf(a, r)の最大値や最小値、f(a, r)の分布のパーセント点などを評価尺度としてもよい。また、結果属性が離散値の場合は、各Ak と結果属性値の組み合わせについて事例評価の期待値を集めた事例評価関数テーブルを用意すれば、各領域の評価値を計算する場合に、データベース中の事例を探索する必要がなくなる。
【００４７】
図１０は事例評価関数を構成する事例評価関数テーブルの例である。図１０のような事例評価関数テーブル１００１は、事例評価関数f(a, r)とデータベース中の事例を用いてあらかじめ計算しておくことができる。図１０では、例えば：
【数９】
2006139469.tif 000011
と求められている。
【００４８】
図１２は最適行動の例である。状態領域X1〜X4 に対して、各Ak における領域の評価値V(Xi, Ak)が計算され、最も大きな値をとる行動が最適行動A*(Xi)として決定されている。V(Xi, Ak)はデータベース中の事例を探索して求めても良いが、図１０の事例評価関数テーブルと図４の結果決定木のクラス分布を用いて計算しても良い。例えば、X1かつA1 は図４の結果決定木のノード402 に相当することを考慮すると、V(X1, A1)は：
【数１０】
2006139469.tif 000012
とデータベース探索なしに求めることができる。図１２の例では、X1 の最適行動A*(X1)はA1 と決定されている。
【００４９】
図２において、政策改善ルール選択手段２０５は、政策ルール格納手段２０２に格納された政策ルール、最適行動格納手段２０４に格納された最適行動、および、政策変更状態分割格納手段１０６に格納された政策変更状態分割を用いて、各政策ルールの条件部Yj に対応した政策変更状態分割{Z(j)h}の各詳細状態領域Z(j)h に対して、詳細状態領域中の行動を、現在の行動確率分布π(Z(j)h)から全て最適行動A*(Z(j)h)に変更することによる、領域の好ましさの変化量を表す政策改善評価値V(Z(j)h,π(Z(j)h)→A*(Z(j)h))を算出する。そして、算出した政策改善評価値が所定の条件を満たす場合のみ、詳細状態領域Z(j)h と最適行動A*(Z(j)h)の組を用いた政策改善ルールZ(j)h→A*(Z(j)h)を解として採用し、政策改善ルール格納手段１０９に格納する。
【００５０】
詳細状態領域Z における政策改善評価値としては、最適行動A*(Z)を確率1.0 で行ったときの詳細状態領域内の事例評価期待値V(Z, A*(Z))から現状政策π(Z)での詳細状態領域内の事例評価期待値V(Z, π(Z))を減じた値、
【数１１】
2006139469.tif 000013
を用いることができる。ただし、
【数１２】
2006139469.tif 000014
である。
【００５１】
この政策改善評価値は、政策変更時の事例評価の増加期待値と等しくなり、政策改善の好ましさの尺度として妥当なものである。
【００５２】
ここで、Z が、状態分割の要素X’と政策評価状態分割の要素Y’の交差計算によって得ら
れた詳細状態領域だとすると、
【数１３】
2006139469.tif 000015
が成立する。
【００５３】
このとき、V(Z, π(Z)→A*(Z))には、
【数１４】
2006139469.tif 000016
という関係が成り立つので、政策ルール１１０１に保存されているπ(Yj, Ak)と、最適行動１２０１におけるV(Xi, Ak)を用いてデータベースを探索することなくZ(j)h の政策改善評価値を求めることが可能となり、効率的な政策改善ルールの探索を行うことができる。
【００５４】
図１３は上述の政策改善評価値(図ではΔV と省略して記述)を用いた政策改善ルール選択１３０１の例である。
【００５５】
例えばZ14→A2（1.0）の場合の政策改善評価値ΔVは、
【数１５】
2006139469.tif 000017
として求められる。
【００５６】
仮にΔV>10 という条件を満たす政策改善ルールを選択条件すれば、Z14→A2 （詳細状態領域Z14から行動領域A2への写像）が解として選択される。選択された解は重要な政策改善ルールとしてユーザーに示すことができ、かつ、その規則を採用した場合の期待事例評価値の増加量を示すことが可能になる。
【００５７】
また、政策改善評価値は、詳細状態領域Z の空間的な大きさ|Z|を用いて、
【数１６】
2006139469.tif 000018
とすることもできる。この政策改善評価値を用いることにより、Zに含まれる新たな事例の発生確率や、Zの大きさ、データベースにおいてZに含まれる事例数を考慮した政策改善ルールの選択を行うことが可能になる。
【００５８】
さらに、政策改善評価値は、政策π(Z)を政策A*(Z)に変更するコストを表す関数
【数１７】
2006139469.tif 000019
を用意し、
【数１８】
2006139469.tif 000020
とすることもできる。この政策改善評価値を用いることにより、政策変更コスト（例えば商品のポスターを変更したり、ウェブサイトを変更したりするのに必要なコスト）を考慮した政策改善ルールの選択を行うことが可能になる。
【００５９】
以上に説明した本実施の形態により、様々な問題領域において、事例の好ましさを向上させるための規則による行動属性変更プランとしての政策改善ルールをデータベースから自動的に発見することが可能となる。
【００６０】
以上のように、本実施の形態によれば、個々の事例についての改善方法ではなく、属性領域（詳細状態領域）から属性領域（行動領域）への写像という形式の政策改善ルールを探索するので、意思決定者の理解が容易な、規則による行動属性変更プランを発見することができる。
【００６１】
また、本実施の形態によれば、状態属性と行動属性とによって形成される属性空間の部分領域において結果属性の値の分布が均一になるように前記属性空間を分割して状態領域および行動領域を生成するようにしたので、事例の評価値の分布も均一になり、政策改善ルールの効率的な探索が実現できる。  
また、本実施の形態によれば、行動属性の値の分布が均一になるように状態空間を分割して政策評価状態領域を生成するようにしたので、政策改善ルールの効率的な探索が実現できる。
【００６２】
また、本実施の形態によれば、詳細状態領域における事例集合の行動を政策ルールから最適行動へ変更した場合における事例集合の好ましさの変化量を政策改善評価値として算出するので、定量的な政策改善の価値が評価できる。
【００６３】
また、本実施の形態によれば、詳細状態領域における事例集合の行動を政策ルールから最適行動へ変更した場合における事例評価関数の期待値の変化量を政策改善評価値として算出するので、事例評価関数の期待値を最大化するような政策改善ルールを発見することができる。
【００６４】
また、本実施の形態によれば、詳細状態領域における事例集合の行動を政策ルールから最適行動へ変更した場合における事例評価関数の期待値の変化量から、政策変更コストを減じた値を政策改善評価値として用いるので、政策変更コストを考慮した政策改善ルールを発見することができる。
【図面の簡単な説明】
【００６５】
【図１】本発明の一実施形態に関わる政策データマイニング装置の構成図。
【図２】図１の政策改善ルール生成手段の詳細構成図。
【図３】データベースの例を示す図。
【図４】結果決定木の例を示す図。
【図５】状態分割の例を示す図。
【図６】行動分割の例を示す図。
【図７】行動決定木の例を示す図。
【図８】政策評価状態分割の例を示す図。
【図９】政策変更状態分割の例を示す図。
【図１０】事例評価関数テーブルの例を示す図。
【図１１】政策ルールの例を示す図。
【図１２】最適行動の例を示す図。
【図１３】政策改善ルールの例を示す図。
【符号の説明】
【００６６】
１０１  データベース
１０２  状態分割格納手段
１０３  行動分割格納手段
１０４  政策評価状態分割格納手段
１０５  政策変更状態分割生成手段
１０６  政策変更状態分割格納手段
１０７  事例評価関数格納手段
１０８  政策改善ルール生成手段
１０９  政策改善ルール格納手段
１１０  状態・行動分割生成手段
１１１  政策評価状態分割生成手段
２０１  政策ルール生成手段
２０２  政策ルール格納手段
２０３  最適行動決定手段
２０４  最適行動格納手段
２０５  政策改善ルール格納手段
３０１  データベースの属性の例
３０２  データベーステーブルの例
４０１  結果決定木の例
５０１  状態分割の例
６０１  行動分割の例
７０１  行動決定木の例
８０１  政策評価状態分割の例
９０１  政策変更状態分割の例
１００１  事例評価関数テーブルの例
１１０１  政策ルールの例
１２０１  最適行動の例
１３０１  政策改善ルールの例
【図１】
2006139469.tif 000021
【図２】
2006139469.tif 000022
【図３】
2006139469.tif 000023
【図４】
2006139469.tif 000024
【図５】
2006139469.tif 000025
【図６】
2006139469.tif 000026
【図７】
2006139469.tif 000027
【図８】
2006139469.tif 000028
【図９】
2006139469.tif 000029
【図１０】
2006139469.tif 000030
【図１１】
2006139469.tif 000031
【図１２】
2006139469.tif 000032
【図１３】
2006139469.tif 000033