(57)【要約】【課題】本発明は、行動とその行動間の遷移確率をもとに生成した行動モデルを簡略化する簡略化方法に関し、行動モデルの元の情報を出来るだけ保持した状態で計算量を少なくして簡単化した行動モデルを自動生成することを目的とする。【解決手段】行動とその行動間の遷移確率をもとに行動モデルを生成するステップと、生成した行動モデル中の各行動を統合した後、分割したときの組み合わせが１つのときは分割し、複数あるときにそれぞれの評価値を算出するステップと、算出した評価値の最大となる組み合わせの分割に決定するステップと、分割後の行動モデルが指定された複雑度になるまで分割を繰り返すステップとを有する。【選択図】  図１
2004303070.tif 000002
【特許請求の範囲】
【請求項１】
行動とその行動間の遷移確率をもとに生成した行動モデルを簡略化する簡略化方法において、
行動とその行動間の遷移確率をもとに行動モデルを生成するステップと、
前記生成した行動モデル中の各行動を統合した後、分割したときの組み合わせが１つのときは分割し、複数あるときにそれぞれの評価値を算出するステップと、
前記算出した評価値の最大となる組み合わせの分割に決定するステップと、
前記分割後の行動モデルが指定された複雑度になるまで分割を繰り返すステップと
を有する行動モデル簡略化方法。
【請求項２】
前記分割時に、各行動の階層を予め定義した階層木を取り込み、当該階層木に従い分割することを特徴とする請求項１記載の行動モデル簡略化方法。
【請求項３】
前記分割時に、各行動間の距離をそれぞれ算出して昇順にソートしてグルーピング木を生成し、上位階層から順に分割して組み合わせが１つのときは分割し、組み合わせが複数のときは最大の評価値となる組合せに分割することを特徴とする請求項１記載の行動モデル簡略化方法。
【請求項４】
前記分割時に、各行動間の距離をそれぞれ算出し、取り込んだ各行動の階層を予め定義した階層木の各行動に当該算出した距離を付与し、上位階層から順に分割して組み合わせが１つのときは分割し、組み合わせが複数のときは最大の評価値となる組合せに分割することを特徴とする請求項１記載の行動モデル簡略化方法。
【請求項５】
前記複雑度として、行動モデルに現れる行動数（ノード数）としたことを特徴とする請求項１から請求項４のいずれかに記載の行動モデル簡略化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、行動とその行動間の遷移確率をもとに生成した行動モデルを簡略化する簡略化方法に関するものである。
【０００２】
【従来の技術】
従来、行動主体（例えば顧客）の各行動の初期確率と、２つの行動間の遷移確率を収集し、収集したこれらをもとに行動モデル（例えばマルコフモデル）を作成し、これを有向グラフで理解し易く表現することが行われている。
【０００３】
また、顧客動向に関する１以上の統計的推定量を決定する方法がある（特許文献１）。
【０００４】
【特許文献１】
特開２００２−１６３４３４号公報の〔０００７〕、〔０００８〕などを参照。
【０００５】
【発明が解決しようとする課題】
しかし、上述した前者の行動モデル中に現れる行動の数が非常に多くなってしまうと、理解し難くなってしまうという問題があった。
【０００６】
また、上述した後者では、顧客動向に関する１以上の統計的推定量を決定できるのみで、本願の行動モデル中に現れる行動の数が非常に多いときに重要なものを残して簡略化する手法について記載されていない。
【０００７】
本発明は、これらの問題を解決するため、行動モデルの元の情報を出来るだけ保持した状態で計算量を少なくして簡単化した行動モデルを自動生成することを目的としている。
【０００８】
【課題を解決するための手段】
本発明は、行動モデルをいったん情報の少ない単純化した行動モデルを生成し、これから徐々に詳細化しながらその過程で情報量を可及的に増加させ、簡略化した元の情報をできるだけ多く保持した行動モデルを計算量少なく高速に生成するようにしている。
【０００９】
図１を参照して課題を解決するための手段を説明する。
図１において、処理装置１は、プログラムに従い各種処理を実行するものであって、ここでは、行動モデル作成手段２、統合・分割手段３、評価手段４、および決定手段５などから構成されるものである。
【００１０】
行動モデル作成手段２は、行動データ１１をもとに行動モデル（例えばマルコフモデル）を作成するものである。
【００１１】
統合・分割手段３は、行動モデルの行動を１つにまとめた後、分割するものである。
【００１２】
評価手段４は、分割した候補の行動モデルを評価するものである。
決定手段５は、評価値をもとに分割を決定するものである。
【００１３】
行動データ１１は、各行動とその行動間の遷移を格納したものである。
次に、動作を説明する。
【００１４】
処理装置１を構成する行動モデル作成手段２が行動とその行動間の遷移確率を格納した行動データ１１をもとに行動モデルを生成し、統合・分割手段３が生成した行動モデル中の各行動を統合した後、分割したときの組み合わせが１つのときは分割し、評価手段４が複数あるときはそれぞれの評価値を算出し、決定手段５が算出した評価値の最大となる組み合わせの分割に決定するようにしている。
【００１５】
この際、分割時に、行動の階層を予め定義した階層木を取り込み、階層木に従い分割するようにしている。
【００１６】
また、分割時に、行動間の距離をそれぞれ算出して昇順にソートしてグルーピング木を生成し、上位階層から順に分割して組み合わせが１つのときは分割し、組み合わせが複数のときは最大の評価値（算出した距離差が最小）となる組合せに分割するようにしている。
【００１７】
また、分割時に、行動間の距離をそれぞれ算出し、取り込んだ行動の階層を予め定義した階層木の行動に算出した距離を付与し、上位階層から順に分割して組み合わせが１つのときは分割し、組み合わせが複数のときは最大の評価値（算出した距離差が最小）となる組合せに分割するようにしている。
【００１８】
また、複雑度として、行動モデルに現れる行動数（ノード数）とするようにしている。
【００１９】
従って、行動モデルの元の情報を出来るだけ保持した状態で計算量を少なくして簡単化した行動モデルを自動生成することが可能となる。
【００２０】
【発明の実施の形態】
次に、図１から図１６を用いて本発明の実施の形態および動作を順次詳細に説明する。
【００２１】
図１は、本発明のシステム構成図を示す。
図１において、処理装置１は、コンピュータにプログラムをローディングし当該コンピュータにより各種処理を実行するものであって、ここでは、行動モデル作成手段２、統合・分割手段３、評価手段４、および決定手段５などから構成されるものである。
【００２２】
行動モデル作成手段２は、行動データ１１をもとに行動モデル（例えばマルコフモデル）を作成するものである（図２、図３参照）。
【００２３】
統合・分割手段３は、行動モデルの行動を１つにまとめて統合した後、データが最も多くなる組合わせに分割するものである。
【００２４】
評価手段４は、分割した候補などの行動モデルの評価値を算出するものである。
【００２５】
決定手段５は、統合した行動モデルを分割する候補が複数あるときに算出された評価値の最も大きい組合わせの行動モデルに決定するものである。
【００２６】
行動データ１１は、行動とその行動間の遷移を格納したものである（例えば図２参照）。
【００２７】
分類階層データ１２は、行動モデルの行動を階層木で表現したものである（例えば図４参照）。
【００２８】
入力装置１３は、データや指示などを入力するものであって、マウス、キーボードなどである。
【００２９】
出力装置１４は、各種情報を出力するものであって、表示装置、印刷装置である。
【００３０】
まず、図２から図４を用いて行動データ、行動モデルであるマルコフモデル、分類階層木について説明する。
【００３１】
図２は、本発明の行動データ例を示す。行動データは、行動とその行動間の遷移（行動履歴）を収集して図示のように登録したものであって、図示の下記の情報を登録したものである。
【００３２】
・ＩＤ：
・行動履歴：
ここで、ＩＤは、行動履歴に付与した一意の番号である。行動履歴は、行動と、その行動から他の行動へ遷移したつながり（履歴）を登録したものであって、矢印が遷移の方向を示す。例えばＩＤ＝１の行動履歴は、行動”Ｘ／Ａ”から行動”Ｙ／Ａ”に遷移し、更に、行動”Ｙ／Ａ”から行動”Ｘ／Ｂ”に遷移するという行動履歴を表す。
【００３３】
以上のような行動データを収集することにより、最初に出現する行動の確率と、ある行動から他の行動へ遷移する遷移確率を、後述する図３のように算出することが可能となる。
【００３４】
図３は、本発明のマルコフモデル説明図を示す。
図３の（ａ）は、各行動の初期確率の例を示す。これは、既述した図２の行動データ１１の行動履歴のうちの、最初に出現する行動の全体に対する確率を算出したものである。例えばだ先頭の行動”Ｘ／Ａ”の初期確率”１０／２３”は、図２の行動データ１１の総数が２３個であり、行動”Ｘ／Ａ”が先頭に出現した数が１０個であるので、初期確率＝１０／２３として算出したものである。
【００３５】
図３の（ｂ）は、遷移確率の例を示す。遷移確率は、ある行動から他の行動に遷移した確率であって、ここでは、図２の行動データ１１の行動履歴から、全ての行動から行動の組合わせが８３個あるので、分母の８３となり、更に、左側の行動から上段の行動への遷移した個数を算出して設定したものが、図示の遷移確率のテーブルである。
【００３６】
図３の（ｃ）は、マルコフモデルのグラフ表現の例を示す。図示のマルコフモデルのグラフ表現は、図３の（ｂ）の遷移確率をもとに各行動を円の中に表現（ノードとして表現）し、実線、点線の矢印でその遷移方向を表現（アークで遷移を表現）し、数字（例えば１４／８３）で遷移確率を表現し、点線の矢印は遷移確率が小さい（ここでは、０．１以下）を表現する。
【００３７】
以上によって、図２の行動データ中の行動とその遷移の状態は、図３の（ｃ）の行動モデルである公知のマルコフモデルで表現でき、行動と、行動間の遷移確率を視覚的に認識しやすく表現することが可能となる。しかし、行動数が非常に多くなりしかも行動間の遷移の数が非常に多くなると、マルコフモデル中に多数のノード（行動）と、ノード間のアーク（遷移）が表現されて認識し難くなってしまうので、重要なノードとその遷移を簡単に抽出した指定した複雑度の行動モデル（マルコフモデル）を、自動生成する。以下図５から図１６を用いて順次詳細に説明する。
【００３８】
図４は、本発明の階層説明図を示す。
図４の（ａ）は分類階層データで表現した例を示し、図４の（ｂ）は分類階層木で表現した例を示す。両者は、同一であって、表現の仕方がことなるのみであり、ルート（ｔｏｐ）の下の階層にノード（行動）ＸとＹがある。Ｘの下の階層にノード（行動）Ｘ／Ａ，Ｘ／Ｂ，Ｘ／Ｃの３つがある。同様に，ノード（行動）Ｙの下の階層にノード（行動）Ｙ／Ｄ，Ｙ／Ｅの２つがある。
【００３９】
以上のように、階層分類データを定義することにより、ノード（行動）をどのように分割するかを指定することが可能となる。
【００４０】
次に、図５のフローチャートの順番に従い、図１の構成の動作を詳細に説明する。
【００４１】
図５は、本発明の動作説明フローチャート（その１）を示す。
図５において、Ｓ１は、行動データを取り込む。これは、例えば既述した図２の行動データ１１を取り込む。
【００４２】
Ｓ２は、マルコフモデルを生成する。これは、例えば既述した図３の（ｃ）のマルコフモデルを生成する。
【００４３】
Ｓ３は、基準値を指定する。これは、マルコフモデルの複雑度の基準値を指定、複雑度の基準値として例えば３を指定する。
【００４４】
Ｓ４は、モデルの複雑度≦基準値か判別する。これは、現在のマルコフモデルの複雑度（例えばノードの数）が基準値（例えばＳ３で指定した基準値＝３）よりも等しいあるいは小さいか比較する。ここでは、図３の（ｃ）のマルコフモデルの複雑度（ノードの数は５）であるので、ＮＯとなり、Ｓ５に進む。一方，ＹＥＳの場合には、Ｓ１２に進み、Ｓ１２でモデルを出力して終了する。
【００４５】
Ｓ５は、分類階層データを取り込む。これは、例えば既述した図４の（ａ）の分類階層データ１２を取り込む。
【００４６】
Ｓ６は、分類階層木を作成する。これは、Ｓ５で取り込んだ分類階層データ１２とに、図４の（ｂ）の分類階層木を作成する。
【００４７】
Ｓ７は、すべてのノードを統合した１つのノードを作成する。これは、Ｓ２で生成した図３の（ｃ）のマルコフモデルのすべてのノードを統合した後述する図６の（ｂ）の始めの１つのノードにする。
【００４８】
Ｓ８は、ある１つのノードあるいは分割した各ノードに注目し、ノード（親）とする。これは、後述する図６の（ｂ）に示すように、始めの１つに統合したノードをノード（親）とする。
【００４９】
Ｓ９は、ノード（親）を２つのノード（子）に分割したときの分割評価値を計算する。
【００５０】
Ｓ１０は、評価最大のノードを分割する。これらＳ９、Ｓ１０は、例えば後述する図６の（ｂ）で、
・１回目の分割▲１▼は、図４の（ｂ）の分類分割木から２つのノードにしか分割の組合わせがないので、そのまま分割する。
【００５１】
・しかし、２回目の分割▲２▼のときは、図４の（ｂ）の分類分割木から４通りの分割の組合わせがあるので、図６の（ｂ）の２回目の分割に記載されているように、分割前の情報量から分割後の情報量との差分（分割評価値Ｈ）が最大の組合わせを選択して図示のように分割する。
【００５２】
Ｓ１１は、モデルの複雑度＜基準値か判別する。ここでは、
・１回目の分割では、ノード数が図６の（ｂ）から２つなので、基準値＝３よりも小さく、Ｓ８に戻り更に分割し、
・２回目の分割では、ノード数が図６の（ｂ）から３つであるので、基準値＝３と等しく、ＮＯとなり、Ｓ１２でモデルを出力して終了する。一方、ＹＥＳの場合には、Ｓ８に戻り、更に分割する。
【００５３】
以上によって、行動データからマルコフモデルを作成し、分類階層木に従い順次分割し、分割の組合わせが２つのときはそのまま分割し、３つ以上の組合わせがあるときは分割前の情報量と分割後の情報量との差分（分割評価値Ｈ）が最大となる組合わせとなる１つの分割を選択して分割することを繰り返し、複雑度が基準値になるまで繰り返し、基準値になったときに分割を終了し、指定した複雑度の簡易化した理解し易いマルコフモデルを迅速に生成することが可能となる。
【００５４】
図６は、本発明の説明図（図５）を示す。
図６の（ａ）は、例：ノード数５のモデルをノード数３に単純化する例を示す。この場合の基準値＝３である（図５のＳ３）。
【００５５】
図６の（ｂ）は、統合・分割の様子を示す。
・始めは、既述した図３の（ｃ）のマルコフモデルの全てのノードを１つに統合した状態を示す（図５のＳ７）。
【００５６】
・１回目の分割▲１▼は、図４の（ｂ）の分類階層木（図５のＳ６で作成）に従い、Ｘのグループと、Ｙのグループに２分割するが、他に分割がないので、ここでは、そのまま図６の（ｂ）の１回目の分割▲１▼のように分割する。分割後のモデルの複雑度は２（ノード数＝２）であり、基準値＝３よりも小さいので、２回目の分割に進む。
【００５７】
・２回目の分割▲２▼は、図４の（ｂ）の分割階層木に従い、４つの組合わせがあるので、分割前の情報量Ｊ（Ｍ）と、分割後の４通りの情報量Ｊ（Ｍ’）をそれぞれ算出し図示の
Ｈ＝Ｊ（Ｍ’）−Ｊ（Ｍ）＝０．５１００３２−０．２３９４３３＝０．２７０５９９
となって図示の場合が分割評価値が最大となるので、当該最大の図示の組合わせに分割する。この状態でモデルのノード数が３となり、当該モデルの複雑度が基準値＝３と等しくなったので、分割を終了し、当該モデルを出力する。
【００５８】
図６の（ｃ）は、図６の（ｂ）の２回目の分割の他の例を示す。この他に、２つ、合計４つの組合わせがあり、既述した図６の（ｂ）の分割評価値Ｈをそれぞれ同様に計算すればよい。ここでは、既述したように、図６の（ｂ）の組合わせの分割評価値Ｈが最大となる。
【００５９】
図７は、本発明の説明図（図６）を示す。
図７の（ａ）は、情報量の定義例を示す。ここでは、図示のように、情報量を（式２）で定義する。
【００６０】
図７の（ｂ）は、分割評価値の例を示す。
図７の（ｂ−１）は、図５の場合の分割評価値を示す。
【００６１】
・Ｈ＝Ｊ（Ｍ’）−Ｊ（Ｍ）
図７の（ｂ−２）は、図９の場合の分割評価値を示す。
【００６２】
・Ｈ＝Ｊ（Ｍ’）
図７の（ｂ−３）は、図１１の場合の分割評価値を示す。
【００６３】
・Ｈ＝Ｊ（Ｍ’）−Ｊ（Ｍ）
図７の（ｂ−４）は、図１５の場合の分割評価値を示す。
【００６４】
・Ｈ＝Ｊ（Ｍ’）−Ｊ（Ｍ）
図８は、本発明の情報量の計算例を示す。これは、既述した図６の（ｂ）の２回目の分割▲２▼の情報量の計算例を示す。
【００６５】
図８の（ａ）は、モデルＭの情報量Ｊ（Ｍ）の算出例を示す。モデルＭは、既述した図６の（ｂ）の１回目の分割▲１▼のモデルＭの情報量Ｊ（Ｍ）であって、既述した図７の（ａ）の（式２）に代入して図示のように計算できる。
【００６６】
図８の（ｂ）は、モデルＭ’の情報量Ｊ（Ｍ’）の算出例を示す。モデルＭ’は、既述した図６の（ｂ）の２回目の分割▲２▼のモデルＭ’の情報量Ｊ（Ｍ’）であって、既述した図７の（ａ）の（式２）に同様に代入して図示のように計算できる。
【００６７】
以上のようにして算出した分割前のモデルＭの情報量Ｊ（Ｍ）と、分割後の１つのモデルＭ’の情報量Ｊ（Ｍ’）との差（分割評価値Ｈ）を既述した図６の（ｂ）の２回目の分割▲２▼のように求めて、ここでは、４通りの組合わせのうちの分割評価値Ｈが最大となったので、当該モデルＭ’に分割すると決定できる。
【００６８】
図９は、本発明の動作説明フローチャート（その２）を示す。
図９において、Ｓ２１は、行動データを取り込む。これは、例えば既述した図２の行動データ１１を取り込む。
【００６９】
Ｓ２２は、マルコフモデルを生成する。これは、例えば既述した図３の（ｃ）のマルコフモデルを生成する。
【００７０】
Ｓ２３は、基準値を指定する。これは、マルコフモデルの複雑度の基準値を指定、複雑度の基準値として例えば３を指定する。
【００７１】
Ｓ２４は、モデルの複雑度≦基準値か判別する。これは、現在のマルコフモデルの複雑度（例えばノードの数）が基準値（例えばＳ３で指定した基準値＝３）よりも等しいあるいは小さいか比較する。ここでは、図３の（ｃ）のマルコフモデルの複雑度（ノードの数は５）であるので、ＮＯとなり、Ｓ２５に進む。一方，ＹＥＳの場合には、Ｓ３４に進み、Ｓ３４でモデルを出力して終了する。
【００７２】
Ｓ２５は、分類階層データを取り込む。これは、例えば既述した図４の（ａ）の分類階層データ１２を取り込込む。
【００７３】
Ｓ２６は、分類階層木を作成する。これは、Ｓ２５で取り込んだ分類階層データ１２をもとに、図４の（ｂ）の分類階層木を作成する。
【００７４】
Ｓ２７は、すべてのノードを統合した１つのノード（Ｒ）を作成する。これは、Ｓ２２で生成した図３の（ｃ）のマルコフモデルのすべてのノードを統合した後述する図１０の（ｂ）の始めの１つのノード（Ｒ）にする。
【００７５】
Ｓ２８は、Ｒの子節点をすべて取り出す。
Ｓ２９は、すべての子節点を２分割したノードのすべての組合わせを作成する。
【００７６】
Ｓ３０は、モデルの複雑度＜基準値か判別する。ＹＥＳの場合には、Ｓ２９に戻り、繰り返す。ＮＯの場合には、分割したモデルの複雑度が基準値＝３より小さくなったので、Ｓ３１に進む。
【００７７】
以上によって、例えば図１０の（ｂ）に１つのモデルを右端に示すように、全ての子節点を取り出し、分類階層木に従い、これら子節点を２分割、更に２分割するというように繰り返し、基準値を満たす全ての組合わせのモデルを生成できたこととなる。
【００７８】
Ｓ３１は、複雑度を満たしたすべての組合わせの評価値を算出する。これは、複雑度を満たしたすべてのモデルの評価値、既述した図７の（ｂ−２）の評価値（情報量Ｈ＝Ｊ（Ｍ’））をそれぞれ算出する。
【００７９】
Ｓ３２は、評価値最大の組合わせを選択する。
Ｓ３３は、分割を実施する。これら、Ｓ３２、Ｓ３３は、Ｓ３１で基準値を満たすすべての組合わせのモデルの評価値のうちの最大のモデルに分割する。これにより、基準値を満たす分割可能なモデルのうち、最大評価値を持つモデルに分割できたこととなる。
【００８０】
Ｓ３４は、モデルを出力する。
以上によって、行動データからマルコフモデルを作成し、分類階層木に従い基準値を満たすすべての分割したモデルを作成し、これら全てのモデルの評価値をそれぞれ算出し、最大の評価値を持つモデルに分割することにより、指定した複雑度を持つ最適なモデルを迅速に生成することが可能となる。
【００８１】
図１０は、本発明の説明図（図９）を示す。
図１０の（ａ）は、例：ノード数５のモデルをノード数３に単純化する例を示す。この場合の基準値＝３である（図９のＳ２３）。
【００８２】
図１０の（ｂ）は、基準値を満たす組合わせモデルＭ’の例（右端）を示す。
この図示のモデルＭ’の評価値を既述した図７に従い計算すると、図示の値となる。
【００８３】
図１０の（ｃ）は、他の分割例を示す。基準値＝３の他の分割例を示す。
図１１は、本発明の動作説明フローチャート（その３）を示す。
【００８４】
図１１において、Ｓ４１は、行動データを取り込む。これは、例えば既述した図２の行動データ１１を取り込む。
【００８５】
Ｓ４２は、マルコフモデルを生成する。これは、例えば既述した図３の（ｃ）のマルコフモデルを生成する。
【００８６】
Ｓ４３は、基準値を指定する。これは、マルコフモデルの複雑度の基準値を指定、複雑度の基準値として例えば３を指定する。
【００８７】
Ｓ４４は、モデルの複雑度＜基準値か判別する。これは、現在のマルコフモデルの複雑度（例えばノードの数）が基準値（例えばＳ４３で指定した基準値＝３）よりも小さいか比較する。ここでは、図３の（ｃ）のマルコフモデルの複雑度（ノードの数は５）であるので、ＮＯとなり、Ｓ４５に進む。一方，ＹＥＳの場合には、Ｓ５０に進み、Ｓ５０でモデルを出力して終了する。
【００８８】
Ｓ４５は、ノード間の距離を計算して昇順ソートする。これは、後述する図１２に従い、各ノード間の距離を計算（図１３の（ａ））して昇順ソートする。
【００８９】
Ｓ４６は、グルーピング木を作成する。これは、Ｓ４５で昇順ソードした結果をもとに、図１３の（ｂ）に示すグルーピング木（後述する）を作成する。
【００９０】
Ｓ４７は、すべてのノードを結合したモデルを作成する。これは、Ｓ４６で生成したグルーピング木（図１３の（ｂ））の全てのノードを結合したモデル（図１４の（ｂ）の左端の１つのノードからなるモデルを作成する。
【００９１】
Ｓ４８は、グルーピング木中の分割候補を評価し、最適なものを分割する。これは、後述する図１４の（ｂ）に示すように、図１３の（ｂ）のグルーピング木に従い、例えば
・分割１回目は、グルーピング木から分割候補は２つであるので、そのまま図１４の（ｂ）の分割１回目に示すように、分割する。
【００９２】
・分割２回目は、グルーピング木から上側のノードは分割候補が２つであるので、そのまま図１４の（ｂ）の分割２回目に示すように、分割する。
【００９３】
・分割３回目は、グルーピング木から上側と、上から２番目とがそれぞれ２つに分割できるので、これら２つの分割候補の評価値を評価（分割前の評価値から分割後の評価値の差分（分割評価値）が大きい方、既述した図７の（ｂ−３）参照）し、最適なもの、ここでは、図示の３回目のように、分割する。
【００９４】
尚、基準値＝３の場合には、上述した分割２回目でモデルのノード数＝３となり、既に基準値を満たすので、Ｓ４９のＮＯとなり、モデルを出力する。分割３回目の分割を行なうのは、基準値＝４とした場合で分割３回目で基準値を満たしＳ４９のＮＯとなり当該分割３回目のモデルを出力する。
【００９５】
以上のように、行動データからマルコフモデルを作成し、ノード間の距離を算出して昇順ソートしてグルーピング木（図１３の（ｂ））を作成し、当該グルーピング木に従い、全てのノードを統括した状態から順次分割して分割候補が２つのときはそのまま分割し、３つ以上の組合わせがあるときは分割前の評価値と分割後の評価値との差分（分割評価値Ｈ）が最大となる組合わせとなる１つの分割を選択して分割することを繰り返し、複雑度が基準値になるまで繰り返し、基準値になったときに分割を終了し、指定した複雑度の簡易化した理解し易いマルコフモデルを迅速に生成することが可能となる。
【００９６】
図１２は、本発明の距離の定義例を示す。これは、既述した図１１のＳ４５でモデルのノード間の距離の計算について説明したものであり、ノード間の距離は図示の下記の（式３）で求める。（式３）で求めた距離は、ノード間の距離を求めようとする２つのノードａ，ｂが１つのノードに結合したときの情報量と結合前の情報量との差、即ち、
Ｄ（ａ，ｂ）＝Ｊ（Ｍ０−Ｊ（Ｍ＋）      （式３）
で求める。
【００９７】
図１３は、本発明の説明図（図１１）を示す。
図１３の（ａ）は、ノード間距離の例を示す。これは、既述した図１１のＳ４５で、図３の（ｃ）のマルコフモデルについてノード間の距離を求めた例を示す。
【００９８】
図１３の（ｂ）は、グルーピング木の例を示す。図示のグルーピング木は、既述した図１１のＳ４６で作成した例であって、図１３の（ａ）のノード間距離を昇順ソートし、当該昇順ソートの先頭から、ノードの組を順に結合して木構造とし、全てのノードが結合して１つの木構造になるまで結合を繰り返すことにより、作成したグルーピング木である。
【００９９】
図１４は、本発明の説明図（図１１）を示す。
図１４の（ａ）は、例：ノード数５のモデルをノード数４に単純化する例を示す。この場合の基準値＝４である（図１１のＳ４３）。
【０１００】
図１４の（ｂ）は、基準値を満たす組合わせモデルＭ’の例（右端）を示す。
この図示のモデルＭ’の評価値と、分割前のモデルＭの評価値との差（分割評価値）を既述した図７に従い計算すると、図示の値となる。
【０１０１】
図１４の（ｃ）は、他の分割例を示す。基準値＝４の他の分割例を示す。
図１５は、本発明の動作説明フローチャート（その４）を示す。
【０１０２】
図１５において、Ｓ５１は、行動データを取り込む。これは、例えば既述した図２の行動データ１１を取り込む。
【０１０３】
Ｓ５２は、マルコフモデルを生成する。これは、例えば既述した図３の（ｃ）のマルコフモデルを生成する。
【０１０４】
Ｓ５３は、基準値を指定する。これは、マルコフモデルの複雑度の基準値を指定、複雑度の基準値として例えば３を指定する。
【０１０５】
Ｓ５４は、モデルの複雑度≦基準値か判別する。これは、現在のマルコフモデルの複雑度（例えばノードの数）が基準値（例えばＳ５３で指定した基準値＝３）よりも等しいあるいは小さいか比較する。ここでは、図３の（ｃ）のマルコフモデルの複雑度（ノードの数は５）であるので、ＮＯとなり、Ｓ５５に進む。一方，ＹＥＳの場合には、Ｓ６１に進み、Ｓ６１でモデルを出力して終了する。
【０１０６】
Ｓ５５は、分類階層データを取り込み、分類階層木を作成する。これは、既述した図４の（ａ）の分類階層データ１２を取り込み、図４の（ｂ）の分類階層木を作成する。
【０１０７】
Ｓ５６は、ノード間の距離を計算して昇順ソートする。これは、既述した図１２に従い、各ノード間の距離を計算（既述した図１３の（ａ））して昇順ソートする。
【０１０８】
Ｓ５７は、グルーピング木を作成する。これは、Ｓ４５で昇順ソードした結果をもとに、
・距離が短く、かつ親が同じものにつなぐ。
【０１０９】
・親が異なっていたものは保留し、次回に使う
ようにして、図１６に示すグルーピング木（後述する）を作成する。
【０１１０】
Ｓ５８は、すべてのノードを結合したモデルを作成する。これは、Ｓ５７で生成したグルーピング木（図１６）の全てのノードを結合したモデルを作成する。
【０１１１】
Ｓ５９は、グルーピング木中の分割候補を評価し、最適なものを分割する。これは、後述する図１６に示すように、順次分割する。
【０１１２】
Ｓ６０は、モデルの複雑度＜基準値か判別する。ＹＥＳの場合には、Ｓ５９を繰り返し、更に分割することを繰り返す。一方、Ｓ６０のＮＯの場合には、基準値を満たしたので、Ｓ６１でモデルを出力する。
【０１１３】
以上のように、行動データからマルコフモデルを作成し、ノード間の距離を算出して昇順ソートして、分類階層木に従い、グルーピング木（図１６）を作成し、全てのノードを統括した状態から順次分割して分割候補が２つのときはそのまま分割し、３つ以上の組合わせがあるときは分割前の評価値と分割後の評価値との差分（分割評価値Ｈ）が最大となる組合わせとなる１つの分割を選択して分割することを繰り返し、複雑度が基準値になるまで繰り返し、基準値になったときに分割を終了し、指定した複雑度の簡易化した理解し易いマルコフモデルを迅速に生成することが可能となる。
【０１１４】
図１６は、本発明の説明図（階層付きグルーピング木）を示す。これは、既述した図１５のＳ５７で生成した図４の（ｂ）の分類階層木に従い、モデルのノード間の距離を算出した昇順ソートした結果（既述した図１３の（ａ））をもとに作成した、グルーピング木であって、下段に示すようにして作成したものである。
【０１１５】
（付記１）
行動とその行動間の遷移確率をもとに生成した行動モデルを簡略化する簡略化方法において、
行動とその行動間の遷移確率をもとに行動モデルを生成するステップと、
前記生成した行動モデル中の各行動を統合した後、分割したときの組み合わせが１つのときは分割し、複数あるときにそれぞれの評価値を算出するステップと、
前記算出した評価値の最大となる組み合わせの分割に決定するステップと、
前記分割後の行動モデルが指定された複雑度になるまで分割を繰り返すステップと
を有する行動モデル簡略化方法。
【０１１６】
（付記２）
前記分割時に、各行動の階層を予め定義した階層木を取り込み、当該階層木に従い分割することを特徴とする付記１記載の行動モデル簡略化方法。
【０１１７】
（付記３）
前記分割時に、各行動間の距離をそれぞれ算出して昇順にソートしてグルーピング木を生成し、上位階層から順に分割して組み合わせが１つのときは分割し、組み合わせが複数のときは最大の評価値（算出した距離差が最小）となる組合せに分割することを特徴とする付記１記載の行動モデル簡略化方法。
【０１１８】
（付記４）
前記分割時に、各行動間の距離をそれぞれ算出し、取り込んだ各行動の階層を予め定義した階層木の各行動に当該算出した距離を付与し、上位階層から順に分割して組み合わせが１つのときは分割し、組み合わせが複数のときは最大の評価値（算出した距離差が最小）となる組合せに分割することを特徴とする付記１記載の行動モデル簡略化方法。
【０１１９】
（付記５）
前記複雑度として、行動モデルに現れるノード数としたことを特徴とする付記１から付記４のいずれかに記載の行動モデル簡略化方法。
【０１２０】
（付記６）
行動とその行動間の遷移確率をもとに生成した行動モデルを簡略化する簡略化プログラムにおいて、
コンピュータに、
行動とその行動間の遷移確率をもとに行動モデルを生成するステップと、
前記生成した行動モデル中の各行動を統合した後、分割したときの組み合わせが１つのときは分割し、複数あるときにそれぞれの評価値を算出するステップと、
前記算出した評価値の最大となる組み合わせの分割に決定するステップと、
前記分割後の行動モデルが指定された複雑度になるまで分割を繰り返すステップと
して機能させる行動モデル簡略化プログラム。
【０１２１】
【発明の効果】
以上説明したように、本発明によれば、行動モデルをいったん情報の少ない単純化した行動モデルを生成し、これから徐々に詳細化しながらその過程で情報量を可及的に増加させ、簡略化した元の情報をできるだけ多く保持した行動モデルを計算量少なく高速に生成する構成を採用しているため、行動モデルの元の情報を出来るだけ保持した状態で計算量を少なくして簡単化した行動モデルを自動生成することが可能となる。
【図面の簡単な説明】
【図１】本発明のシステム構成図である。
【図２】本発明の行動データ例である。
【図３】本発明のマルコフモデル説明図である。
【図４】本発明の階層説明図である。
【図５】本発明の動作説明フローチャート（その１）である。
【図６】本発明の説明図（図５）である。
【図７】本発明の説明図（図６）である。
【図８】本発明の情報量の計算例である。
【図９】本発明の動作説明フローチャート（その２）である。
【図１０】本発明の説明図（図９）である。
【図１１】本発明の動作説明フローチャート（その３）である。
【図１２】本発明の距離の定義例である。
【図１３】本発明の説明図（図１１）である。
【図１４】本発明の説明図（図１１）である。
【図１５】本発明の動作説明フローチャート（その４）である。
【図１６】本発明の説明図（階層付きグルーピング木）である。
【符号の説明】
１：処理装置
２：行動モデル作成手段
３：統合・分割手段
４：評価手段
５：決定手段
１１：行動データ
１２：分類階層データ
１３：入力装置
１４：出力装置
【図１】
2004303070.tif 000003
【図２】
2004303070.tif 000004
【図３】
2004303070.tif 000005
【図４】
2004303070.tif 000006
【図５】
2004303070.tif 000007
【図６】
2004303070.tif 000008
【図７】
2004303070.tif 000009
【図８】
2004303070.tif 000010
【図９】
2004303070.tif 000011
【図１０】
2004303070.tif 000012
【図１１】
2004303070.tif 000013
【図１２】
2004303070.tif 000014
【図１３】
2004303070.tif 000015
【図１４】
2004303070.tif 000016
【図１５】
2004303070.tif 000017
【図１６】
2004303070.tif 000018