(57)【要約】【課題】本発明は、行動をノードおよび当該行動の遷移をアークで表現するグラフを表示する行動データ表示方法および行動データ表示装置に関し、マルコフモデルを表示する場合にグラフの規模が大きくて多数のノードから多数のアークが出ていると、アークが何重にも交錯してしまい、非常に特徴的な部分があったとしても、特徴的でない部分も多量に表示されるために、結果として特徴的な部分を見つけ出すことができなくなってしまう問題を解決することを目的とする。【解決手段】行動主体の行動履歴をもとに各行動の初期確率および行動間の遷移確率を算出するステップと、算出した各行動の初期確率および行動間の遷移確率をもとに、行動あるいは行動から他の行動への遷移を取り除いたときの単純性を算出するステップと、算出した単純性の最小のものを取り除くステップと、単純化した後の各行動および行動間の遷移確率をもとに当該行動をノードおよび行動間の遷移をアークで表現したグラフを生成するステップとを有する。【選択図】　図１
2004102681.tif 000002
【特許請求の範囲】
【請求項１】
行動をノードおよび当該行動の遷移をアークで表現するグラフを表示する行動データ表示方法において、
行動主体の行動履歴をもとに各行動の初期確率および行動間の遷移確率を算出するステップと、
前記算出した各行動の初期確率および行動間の遷移確率をもとに、行動あるいは行動から他の行動への遷移を取り除いたときの単純性を算出するステップと、
前記算出した単純性の最小のものを取り除くステップと、
前記単純化した後の各行動および行動間の遷移確率をもとに当該行動をノードおよび行動間の遷移をアークで表現したグラフを生成するステップと
を有する行動データ表示方法。
【請求項２】
前記単純化は、行動あるいは遷移の取り除く前から後の情報量の減少量に対する、取り除く前から後の行動の減少量の比が最小のものを取り除くことを特徴とする請求項１記載の行動データ表示方法。
【請求項３】
前記行動履歴中の行動の遷移確率が類似した複数の行動をまとめて１つの行動としてグループ化したことを特徴とする請求項１あるいは請求項２記載の行動データ表示方法。
【請求項４】
前記複数の行動をまとめて１つの行動にグループ化する際に、予め定義された行動の階層に従ってまとめることを特徴とする請求項３記載の行動データ表示方法。
【請求項５】
行動をノードおよび当該行動の遷移をアークで表現するグラフを表示する行動データ表示装置において、
行動主体の行動履歴をもとに各行動の初期確率および行動間の遷移確率を算出する手段と、
前記算出した各行動の初期確率および行動間の遷移確率をもとに、行動あるいは行動から他の行動への遷移を取り除いたときの単純性を算出する手段と、
前記算出した単純性の最小のものを取り除く手段と、
前記単純化した後の各行動および行動間の遷移確率をもとに当該行動をノードおよび行動間の遷移をアークで表現したグラフを生成する手段と
を備えたことを特徴とする行動データ表示装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、行動をノードおよび当該行動の遷移をアークで表現するグラフを表示する行動データ表示方法および行動データ表示装置に関するものである。
【０００２】
【従来の技術】
従来、個々の行動主体の行動履歴（行動の種類と順序）と、それ以外の属性の値をもとに当該行動主体の行動をできるだけ判り易い形でモデル化し、表示する手法とし、マルコフモデルを生成して表示することが行われている。
【０００３】
例えばデパートの購買データでは、会員カードを利用している顧客については、属性としてカード入会時に登録する住所、年齢、職業などの個人データ、行動履歴として、その会員カードを利用して、どのような商品をどのような順序で購入しているかをデータとして取得することができる。
【０００４】
【発明が解決しようとする課題】
しかし、モデル中に表れる行動の種類（有向グラフのノードの数）や遷移確率が０以上となる行動のペアの数（有向グラフのアークの数）が多い場合には、対応する有向グラフを表示しても、その意味を理解するのは困難である。例えば、図２６は、行動の種類が約８００あるマルコフモデルに対応する有向グラフを表示した例である。この図２６から、行動履歴に関する何らかの特徴を見出し分析することは実際上できないという問題があった。
【０００５】
本発明は、マルコフモデルを表示する場合にグラフの規模が大きくて多数のノードから多数のアークが出ていると、アークが何重にも交錯してしまい、非常に特徴的な部分があったとしても、特徴的でない部分も多量に表示されるために、結果として特徴的な部分を見つけ出すことができなくなってしまう問題を解決することを目的としている。
【０００６】
【課題を解決するための手段】
図１を参照して課題を解決するための手段を説明する。
【０００７】
図１において、マルコフモデル生成手段７は、行動履歴などをもとにマルコフモデルを生成するものである。
【０００８】
単純化モデル生成手段８は、マルコフモデルを単純化したものを生成するものである。
【０００９】
グラフ生成手段１３は、単純化されたモデルをもとにグラフを生成するものである。
【００１０】
次に、動作を説明する。
マルコフモデル生成手段７が行動主体の行動履歴をもとに各行動の初期確率および行動間の遷移確率を算出し、単純化モデル生成手段８が算出した各行動の初期確率および行動間の遷移確率をもとに行動あるいは行動から他の行動への遷移を取り除いたときの単純性を算出し、算出した単純性の最小のものを取り除き、グラフ生成手段１３が単純化した後の各行動および行動間の遷移確率をもとに当該行動をノードおよび行動間の遷移をアークで表現したグラフを生成するようにしている。
【００１１】
この際、単純化は、行動あるいは遷移の取り除く前から後の情報量の減少量に対する、取り除く前から後の行動の減少量の比が最小のものを取り除くようにしている。
【００１２】
また、行動履歴中の行動の遷移確率が類似した複数の行動をまとめて１つの行動としてグループ化し、単純化を行うようにしている。
【００１３】
また、複数の行動をまとめて１つ行動にグループ化する際に、予め定義された行動の階層に従ってまとめるようにしている。
【００１４】
また、行動履歴中の、指定された行動あるいは指定された行動の範囲についてのみ、グラフを生成するようにしている。
【００１５】
また、行動履歴に付随する属性をもとに、行動間の遷移確率の属性依存性を考慮し、単純化を行うようにしている。
【００１６】
従って、行動履歴をもとに各行動の初期確率および行動間の遷移確率を算出し、これらから単純性の高い行動あるいは遷移を取り除いて単純化を行い、行動をノードおよび行動間の遷移をアークで表現したグラフを生成することにより、グラフから単純性の高い行動、遷移を取り除いて情報量の多い特徴的な部分を見やすくしたグラフを自動生成することが可能となる。
【００１７】
【発明の実施の形態】
次に、図１から図８を用いて本発明の実施の形態および動作を詳細に説明する。
【００１８】
図１は、本発明のシステム構成図を示す。
図１において、行動履歴データ１は、行動主体の行動履歴（行動の種類と順序）（収集した履歴）であって、例えば後述する図４のデータなど）である。例えば会員カードを利用して、どのような商品をどのような順序で購入しているかのデータである。
【００１９】
属性データ２は、行動履歴の行動あるいは行動間の遷移の属性の値であって、例えば会員カード入会時に登録する住所、年齢、性別、職業などの個人データである。
【００２０】
分析範囲３は、行動履歴データのうち、単純化してグラフを生成する対象の行動、属性などの範囲（条件）であって、例えば性別が男性かつ所定の行動を満たす行動のみを抽出し、単純化してグラフを生成するための範囲（条件）である。
【００２１】
行動履歴データ入力手段４は、行動履歴データを入力するものである。
属性データ入力手段５は、行動あるいは遷移の属性データを入力するものである。
【００２２】
分析範囲入力手段６は、行動、遷移、属性などの単純化してグラフを生成する対象の範囲（条件）を入力するものである。
【００２３】
マルコフモデル生成手段７は、入力された行動履歴データ１、その属性データ２、および分析範囲３をもとにマルコフモデル（行動の初期確率および行動間の遷移確率）を生成するものである（図２から図８などを用いて後述する）。
【００２４】
単純化モデル生成手段８は、マルコフモデル（行動の初期確率と行動間の遷移確率）の単純化したモデルを生成するものである（図２から図８などを用いて後述する）。
【００２５】
行動グループ化手段９は、行動履歴データ中の類似した行動をグループ化するものである。
【００２６】
行動階層管理手段１０は、行動履歴データ中の類似した行動を、階層化して管理するものである。
【００２７】
単純化モデル評価手段１１は、マルコフモデル（各行動の初期確率と行動間の遷移確率）から単純性の高い行動、遷移を評価するものである。
【００２８】
属性依存性評価手段１２は、単純化モデルの属性依存性の評価を行うものである。
【００２９】
グラフ生成手段１３は、所定の単純化した後のモデル（各行動の初期確率と行動間の遷移確率）をもとに、行動をノード、遷移を行動間を結ぶ有効グラフを用いたグラフを生成するものである（図８など参照）。
【００３０】
グラフ出力手段１４は、生成されたグラフを表示などするものである。
次に、図２のフローチャートの順番に従い、図１の構成の全体の動作を説明する。
【００３１】
図２は、本発明の動作説明フローチャート（全体）を示す。
図２において、Ｓ１は、データを入力する。これは、既述した図１の行動履歴データ１、属性データ２、および分析範囲３を入力し、作業領域に格納、例えば行動履歴データ１として、後述する図４のデータを入力して作業領域に格納する。
【００３２】
Ｓ２は、初期確率と遷移確率を算出する。これは、Ｓ１で入力して行動履歴データ、例えば図４のデータの各行動の初期確率、および行動間の遷移確率を算出する（図５の初期確率、遷移確率を算出する）。
【００３３】
Ｓ３は、モデルの単純化を行う。これは、Ｓ２で算出した各行動の初期確率と行動間の遷移確率（マルコフモデル）の単純化を行う（例えばば後述する図３のフローチャートに示すようにして、モデルに含まれる行動あるいは遷移を１つ取り除いたときの前と後の情報量の減少量および前と後の単純性の減少量を算出し、情報量の減少量と単純性の減少量の比が最小のものを取り除く）。この単純化により、単純性の高い行動、遷移を取り除いて情報量の多い特徴的な部分を残したモデルに編集する。
【００３４】
Ｓ４は、グラフの生成を行う。これは、Ｓ３で単純性の高い行動、遷移を取り除いて情報量の多いモデルをもとに、特徴的な部分を見やすくしたグラフを生成する。
【００３５】
Ｓ５は、Ｓ４で生成したグラフを表示などする。後述する図８の（ａ）の単純化前のグラフから、単純化した情報量の多いモデルを可視できるグラフとして表示する。
【００３６】
以上によって、行動主体の行動履歴などをもとに単純性の高い行動、遷移を取り除いて情報量の多いモデルにしてこれを可視できるグラフを生成して表示することにより、多量の行動履歴に関するデータを、単純かつ情報量の多いモデルとして可視化することが可能となる。以下順次詳細説明する。
【００３７】
図３は、本発明の動作説明フローチャート（単純化）を示す。マルコフモデルの単純化では、もともとのモデルにどのような操作をすることで単純化を行うかが重要である。ここでは、情報量の少ない行動や遷移を１個ずつ取除いていくことで単純化モデルを選択する。
【００３８】
（１）　まず始めに単純化モデルＭを、全ての行動と全ての遷移を含むもとのマルコフモデルに初期化する（Ｓ１１）。つぎに、もし現在のモデルＭの単純性が与えられた閾値以下であるなら、十分単純なモデルが得られたので終了する（Ｓ１２のＹＥＳ）。もし単純性が閾値より大きい場合（Ｓ１２のＮＯ）は、全ての可能な単純化のための操作、すなわち現在のモデルからひとつの行動を取除いた場合と、遷移をひとつ取除いた場合の単純性と情報量の変化を計算する（Ｓ１３、Ｓ１４）。このとき、行動Ａを取除いたモデルを考える場合には、Ａがモデル中にあるにもかかわらず、Ａからの遷移とＡへの遷移がモデルに含まれているのはおかしいので、このような遷移も同時に取除く。次に、可能な操作の中から情報量の減少量Δｇと単純性の減少量Δｆとの比が最小である操作、すなわち、単純性の単位変化量あたりの情報量の減少が最小である操作を選択し、選択された操作を現在の単純化モデルに対して行う（Ｓ１５、Ｓ１６）。これを単純性が閾値以下になるまでつづける。
【００３９】
ここで、図２では、多数の行動を含むモデルから開始し、それを順次に単純化していくが、逆に、非常に単純なモデルから開始し、それに単純性が上限以下となる範囲内で順次、行動や遷移を付け加えていくことも可能である。
【００４０】
以上のようにグラフの対象となる単純化モデルが決定されたら、行動をノードおよび遷移をアークに対応する有向グラフを生成し、それを出力先にあわせて２次元ないしは多次元空間上での各ノードの座標を決定し、グラフを生成して表示する。これにより、マルコフモデル中で特徴的な部分のみを、利用者に分かり易いグラフという形式で表示し、利用者が行動データの持つ特徴を容易に知ることが可能となる。
【００４１】
（２）　ここで、上述したマルコフモデルの単純化について詳細に説明する。マルコフモデルの単純化モデルＭの評価は、モデルの単純性と情報量の２つの観点からなされる。このうち単純性は、モデル中に現れる行動や遷移の数で評価することができる。すなわち単純化モデルＭの単純性ｆ（Ｍ）は次のように計算する。α、β、γは、ここでは、α＝β＝１、γ＝０とする。
【００４２】
ｆ（Ｍ）＝α×（Ｍ中の行動の種類数）＋（１−α）×（Ｍ中の遷移数）　（式１）単純化モデルの情報量は、モデルをあらわす確率分布、すなわち初期確率分布と遷移確率分布が、モデル無しで予測される初期確率および遷移確率とどれだけ異なっているかで計算する。これらの確率分布が互いに等しければ、モデルによって新たに得られる情報はないから、情報量は０であり、確率分布の差が大きければ大きいほど、モデルＭによって得られる情報は大きくなる。モデルＭにおける行動Ａの初期確率をＰｉ（Ａ）、行動ＡからＢへの遷移確率をＰｔ（Ａ→Ｂ）、モデルＭなしでの行動Ａの初期確率の予測値をＱｉ（Ａ）、ＡからＢへの遷移確率の予測値をＱｔ（Ａ→Ｂ）とすると、モデルＭの情報量ｇ（Ｍ）を次のように計算する。
【００４３】
ｇ（Ｍ）＝（１−β−γ）×ΣＡ∈Ｍ　Ｐｉ（Ａ）×ｌｏｇ｛　Ｐｉ（Ａ）／Ｑｉ（Ａ）　｝
＋β×ΣＡ→Ｂ∈Ｍ　Ｐｔ（Ａ→Ｂ）×ｌｏｇ｛　Ｐｔ（Ａ→Ｂ）／Ｑｔ（Ａ→Ｂ）　｝
＋γ×ΣＡ→Ｂ∈Ｍ　｛Ｐｔ（Ａ→Ｂ｜Ａ→＊）＋　Ｐｔ（Ａ→Ｂ｜＊→Ｂ）｝×ｌｏｇ｛　Ｐｔ（Ａ→Ｂ）／Ｑｔ（Ａ→Ｂ）　｝　　　　　　　　　　　　　　　　　　　　　　　　　（式２）
ここで、第１項は初期確率分布の差、第２項は遷移確率分布の差をあらわす。第２項では、行動データ中に高い確率で表れる行動に関連する遷移確率の寄与が大きくなるため、データ中で典型的に表れる行動パターンをモデル中に残したい場合には向いているが、逆に少数のデータで表れる例外的なパターンは無視される。式２の第３項は、やはり遷移確率分布の差を表す項であるが、このような例外的なパターンからの寄与を大きくするための項である。第３項中で、Ｐｔ（Ａ→Ｂ｜Ａ→＊）は、行動Ａから開始される遷移中でのＢへの遷移の割合、Ｐｔ（Ａ→Ｂ｜＊→Ｂ）は行動Ｂへの遷移中における、Ａから（Ｂへ）の遷移の割合である。初期確率および遷移確率の予測値Ｑは、外部から与えられる場合にはそれを用いる。外部から与えられない場合は、以下のように計算する。まず，初期確率は、各行動（Ｍに含まれないものも含めて）で全て等しいとし、以下のようにする。
【００４４】
Ｑｉ（Ａ）＝１／（行動の種類数）　　　　　　　　（式３）
遷移確率については、各行動から始まる遷移の確率および各行動への遷移の確率は既知であり、各行動は独立に発生するとして、以下のように計算する。
【００４５】
Ｑｔ（Ａ→Ｂ）＝Ｐｔ（Ａ→＊）×Ｐｔ（＊→Ｂ）　　　　　　　（式４）
ここでＰｔ（Ａ→＊）はマルコフモデルでの、全遷移中でのＡへの遷移の割合、Ｐｔ（＊→Ｂ）は全遷移中Ｂへの遷移の割合である。
【００４６】
（３）　上に述べた評価基準のもとで良いモデルＭを選択する方法について述べる。一般に単純性と情報量は相反する評価基準である。すなわち、Ｍから行動や遷移を取除くことで単純性を改善すれば、取除かれた行動の初期確率や取除かれた遷移の遷移確率に関する情報が失われる。本発明は、獲得されたモデルを表示することが目的であり、表示されたものが人間にとってある程度理解可能なだけ単純であるならば、それ以上情報量を犠牲にして単純性を向上させる意味はない。そのため、単純性に関する閾値（式１は大きいほど複雑であるので上限値）を設定し、単純性がその範囲内に入っている単純化モデルのなかで情報量が最大となるモデルを選択する。マルコフモデルの単純化では、もともとのモデルにどのような操作をすることで単純化を行うかが重要である。情報量の少ない行動や遷移を１個づつ取り除いていくことで単純化モデルを選択する（詳細は図３のフローチャート参照）。
【００４７】
図４は、本発明の説明図（元データ）を示す。これは、行動主体の行動履歴を集めたもの（元データ）である。ここでは、属性（性別）および行動履歴（行動主体が取る行動とその順序）を集めたものである。
【００４８】
図５は、本発明の説明図（マルコフデータ）を示す。これは、図４の元データから各行動（Ｓ，Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ）の初期確率（行動履歴の先頭にある各行動履歴の割合）および各行動間の遷移（２つの行動間の遷移の割合）をそれぞれ算出してテーブルに設定したものである。
【００４９】
図５の（ａ）は、各行動の初期確率の例を示す。ここでは、各行動（Ｓ，Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ）の図４の行動履歴の先頭にある確率を示す。
【００５０】
図５の（ｂ）は、遷移確率の例を示す。ここでは、行の行動から列の行動への遷移の割合をテーブルに設定したものである。
【００５１】
図６は、本発明の説明図（情報量／評価値）を示す。ここで、図５のマルコフモデルを単純化モデルＭの初期値とすると、この単純化モデルＭの単純性が閾値５以下であるかどうかを既述した図３のフローチャートに従いチェックする場合には、Ｍは行動として、Ｓ，Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆの７種類を含むので、単純性は７であり、閾値より大きい。よって、単純化を行う必要がある。遷移の除去は単純性をまったく変化させないから、情報量の減少Δｇと単純性の変化Δｆとの比率は無限大となり、単純化のための操作としては選択されない。よって以下では行動の除去のみについて記述する。図５の（ｂ）の遷移確率をもとに、情報量の（式２）内の第２項におけるΣ内の各項
Ｐｔ（Ａ→Ｂ）×ｌｏｇ｛　Ｐｔ（Ａ→Ｂ）／Ｑｔ（Ａ→Ｂ）
の値を求める。各行動を取除いた際の情報量の変化量は、図５の（ｂ）中で、取除く行動からの遷移と、取除く行動への遷移に関する項の値の和であるから、図６の（ｂ）のようになる。一方、各行動を取除いたときの単純性の変化はいずれも１となるので、情報量の変化が最小となる行動、すなわちＡが、単純化のためにモデルＭから取除かれる。行動Ａを取除いてもＭは６個の行動を含むから、単純性の上限に関する上限を満足できず、さらに単純化する必要がある。上と同様にして、行動Ｓ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆを取除いた場合の情報量の変化を計算すると、図６の（ｃ）のようになる。よって、情報量の最小の行動Ｃを選択する。ＭからＣを除くと、行動数は５となる。よって単純性が閾値以下となるので単純化処理は終了し、行動Ｓ，Ｂ，Ｄ，Ｅ，Ｆからなる単純化モデルの各行動をノード、遷移をアークとする有向グラフに変換し、後述する図８の（ｂ）に示すように表示する。
【００５２】
図７は、本発明の説明図を示す。
図７の（ａ）は、行動Ａを取り除いたマルコフモデルの例を示す。これは、既述した図５のマルコフモデル（Ｓ，Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆの７つの行動）中から、既述した情報量／単純性の値の最小の行動Ａを取り除いた後のマルコフモデル（Ｓ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆの６つの行動）の初期確率および遷移確率を示す。
【００５３】
図７の（ｂ）は、行動Ａと行動Ｂを取り除いたマルコフモデルの例を示す。これは、既述した図７の（ａ）のマルコフモデル（Ｓ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆの６つの行動）中から、既述した情報量／単純性の値の最小の行動Ｃを取り除いた後のマルコフモデル（Ｓ，Ｂ，Ｄ，Ｅ，Ｆの５つの行動）の初期確率および遷移確率を示す。この状態で、行動が５つとなり、ここでは、既述した図３のＳ１２のＹＥＳとなり、単純化を終了する。このときの評価値は、既述した図６の（ｃ）の評価値となる。
【００５４】
図８は、本発明の説明図（グラフ）を示す。
図８の（ａ）は、単純化前のマルコフモデルの可視化例を示す。これは、既述した単純化前の図５および図６の（ａ）のマルコフモデルを可視化したものである。ここでは、情報量／単純性の小さい行動Ａ，Ｃが含まれ、全体のうちの特徴的な部分が認識し難い。しかし、本実施例でこれら情報量／単純性の小さい行動Ａ，Ｃを取り除いて図８の（ｂ）の見やすいグラフを生成することが可能となる。
【００５５】
図８の（ｂ）は、行動の削除によって単純化されたマルコフモデルの可視化例を示す。ここでは、既述した図４から図７より、図８の（ａ）のうちの情報量／単純性の最小の行動Ａ，Ｃを取り除いたマルコフモデルを可視化し、情報量の多い特徴的な部分を見やすくしたグラフを表示したものである。
【００５６】
次に、図９から図１４を用いて複数の行動をグループとし、１つの行動グループとして扱ったり、複数の行動をまとめて１つの行動グループとする場合の例を以下順次詳細に説明する。
【００５７】
（１）　ここでは、一部分を切り捨てることで単純性を改善するだけでなく、複数の行動をひとつのグループにまとめ、グラフ化する際に、各行動をノードとするのではなく、グループをノードとし、アークも個々の行動間の遷移ではなくグループ間の遷移をアークとすることで、行動や行動間の遷移を失わずに単純なグラフを生成するものである。
【００５８】
（２）　単純化されたモデルの評価は、モデルの単純性と情報量とで行う。単純性は既述した図２から図８と同様であるが、行動グループが通常のマルコフモデルでの行動になるので、モデルに含まれる行動の数のかわりに、モデルに含まれる行動グループの数を、また、行動間の遷移の数の変わりに行動グループ間の遷移の数を使う。すなわち、
ｆ（Ｍ）＝α×（Ｍ中の行動グループの数）＋（１−α）×（Ｍ中の遷移数）式５）一方、情報量も、モデルから得られる各行動の初期確率と行動間の遷移確率が、モデルなしで得られる初期確率および遷移確率とどれだけ異なるかで評価する。すなわち式２を用いる。ただし、ここでは、モデルが持つのは行動グループの初期確率と行動グループ間の遷移確率であるから、これらから各行動の初期確率と行動間の遷移確率を計算する必要がある。同じグループに属する行動は、初期確率や他の行動との遷移について同じ振る舞いをすると仮定し、行動Ａの初期確率Ｐｉ（Ａ）を、Ａが所属する行動グループＧの初期確率Ｐｉ（Ｇ）から次のように計算する。
【００５９】
Ｐｉ（Ａ）＝　Ｐｉ（Ｇ）／（Ｇに含まれる行動数）　　　　　　　（式６）
また、行動グループＧに属する行動Ａから、行動グループＨに属する行動Ｂへの遷移確率を、ＧからＨへの遷移確率から次のように計算する。
【００６０】
Ｐｔ（Ａ→Ｂ）＝Ｐｔ（Ｇ→Ｈ）×｛　Ｐｔ（Ａ→＊）／Ｐｔ（Ｇ→＊）　｝×｛　Ｐｔ（＊→Ｂ）／Ｐｔ（＊→Ｈ）｝　（式７）
ここで、Ｐｔ（Ｇ→＊）は、全遷移中で、行動グループＧに属する行動からの遷移の割合、Ｐｔ（＊→Ｈ）は、全遷移中行動グループＨに属する行動への遷移の割合である。
【００６１】
（３）ここでは、複数の行動のまとめ上げを許すので、モデルを単純化していく際の操作として、行動（グループ）や遷移を取り除くことだけではなく、２つないしはそれ以上のグループをまとめてひとつのグループとする操作も同時に考慮し、最適な操作を選択する。図９に、単純化のフローチャートを示す。
【００６２】
（４）　図９において、既述した図４の元データが与えられた場合の動作を説明する。図２から図８で説明した場合と同様に、α＝β＝１、γ＝０とする。また単純性の上限を５とする。既述したようにして図５のマルコフモデルを生成する。この本来のマルコフモデルをＭの初期値として設定（図９のＳ２１）し、単純化を行う。モデルＭは、７個の行動（グループ）を含むため、式５で定義される単純性は７であり、閾値５よりも大きい（Ｓ２２のＮＯ）。よって行動グループの削除、遷移の削除、グループのまとめ上げのなかから最適な単純化操作を選択し、それをＭに適用する。この例（図５）では、既述したと同様にα＝１であるので、遷移の削除は単純性の変化が０となるため、選択されない。この時点のＭでは、複数の行動からなる行動グループは存在しないので、各行動（グループ）を削除した場合の情報量の変化は、既述した図６の（ｂ）と同じであり、行動グループを取除く操作のなかで最適なのは、行動Ａ（だけからなる行動グループ）を取除くことであり、その評価値は０．１２４である。
【００６３】
次に、２つの行動（グループ）をまとめて一つのグループとする操作の評価をおこなう。例えば行動Ｂと行動Ｃをまとめる場合、まず、現在のＭの遷移確率分布（図５）から、ＢとＣをまとめた後の遷移確率分布を求める。これはＢとＣに対応する行および列内の確率を加算すればよいので、図１０のようになる。これをもとに、式２と式７を使って情報量を計算すると、単純化前後の情報量の変化はは０．１７６になる。単純性の変化は２つの行動が１のグループになるので、１つである。よって行動ＢとＣとをまとめてひとつにする操作の評価値は０．１７６となる。
【００６４】
同様にして他の行動のペアについても、まとめ上げを行った際の評価値を計算すると、行動ＥとＦをまとめたときの評価が０となり、最適となる。評価値が０となるのは、２つの行動に関する遷移確率が完全に比例している、すなわち他の行動との遷移関係が等しく、例えひとつのグループとしても情報量が全く減らないことを意味している。この評価値は行動グループを取除く場合の最適な操作の評価値０．１２４よりもよいので、単純化のための操作としてはＥとＦとをまとめる操作を選択する。よって、この操作をＭに適用する。適用後のマルコフモデルは図１１のようになる（Ｓ２３からＳ２７）。このマルコフモデルの単純性は、行動グループを６個ふくむので６である。よって単純化をさらに進める必要がある（Ｓ２２のＮＯ）。
【００６５】
同様にして、行動グループを取除く操作と、２つの行動グループをまとめる操作の評価値を計算すると、行動Ａを取除く場合が最適で評価値が０．１２４となる。よって、単純化モデルＭから、行動Ａを取除く。そのときのモデルを図１２に示す。このモデルの単純性は５であるので、閾値以下となる。よって単純化の動作が終了し、このモデルから得られた単純化モデルを有向グラフとして表示する（図１４）。
【００６６】
図１０は、本発明の説明図（行動ＢとＣをまとめたときの遷移確率）を示す。これは、既述した図５の（ｂ）の遷移確率の行動ＢとＣのものを加算して１つの行動グループ（Ｂ，Ｃ）としたものである。
【００６７】
図１１は、本発明の説明図（ＥとＦをまとめてひとつのグループとしたときのマルコフモデル）を示す。これは、図５の（ｂ）の行動ＥとＦの遷移確率を加算し、１つの行動グループ（Ｅ，Ｆ）に設定したものである。
【００６８】
図１２は、本発明の説明図（単純化されたマルコフモデル）を示す。これは、既述した図１１の（ｂ）遷移確率から既述した図９のフローチャートに従い、情報量／単純性の比が最小のもの（行動Ａ）を取り除いた後の遷移確率を示す。
【００６９】
図１３は、本発明の説明図（ＥとＦをひとつのグループにして後の各遷移の情報量）を示す。ここでは、図１２の（ｂ）の行動ＥとＦを１つの行動グループ（Ｅ，Ｆ）としたときの遷移確率を算出したものである。
【００７０】
図１４は、本発明の説明図（行動の削除とグループ化で単純化したマルコフモデルの可視化）を示す。ここでは、図９から図１３で説明したように、行動ＥとＦを１つの行動グループ（Ｅ，Ｆ）にまとめた後に、行動Ａを削除して単純化した後のマルコフモデルを可視化表示したものである。
【００７１】
以上の後者である図１４の結果と、既述した前者の図８の（ｂ）の結果とを比較すると、同じ５個のノードからなるグラフであるが、後者では行動Ｃが取除かれていない分だけ情報量が多い（上で述べたようにＥとＦは他の行動との遷移確率が全くひとしいので、ＥとＦをひとつのノードとしても遷移確率に関する情報は全く失われない）。このように、後者では、グラフ中の一つのノードで複数の行動を表すことで、単純性を悪化させずに、マルコフモデル中のより多くの部分を表示することができる。しかし、どのような行動が集まってひとつのノードとなるかは、集まることによる情報量の変化だけで決定されるから、最終的に得られるグラフを利用者が見たときに、各ノードの意味が分りづらい場合がある。例えば最初に例にあげたデパートの購買履歴では、「ビールの購入」と「発泡酒の購入」とう行動からなるグループは納得できるが、「ビールの購入」と「腕時計の購入」グループは、たとえ確率的には意味があったとしても、それを人間が理解することは難しい。
【００７２】
次に、図１５および図１６を用いて行動の階層上でより近い行動を優先的にまとめる処理について詳細に説明する。
【００７３】
（１）　行動のグループ化を行う際に、あらかじめ設定された行動のカテゴリ階層をもとに、生成される行動グループを制限することで、できるだけ行動の階層関係に従った行動グループを生成し、意味が分かり易いグループを生成する。生成される行動グループの制限は、モデルの単純化を行う際に、操作の結果について、行動の階層からみて意味がわかりづらいグループを生成する操作かどうかを判定し、そうでない操作のなかから評価値の最も良い操作を選択することで実現する。ここでは、与えられた操作の結果得られるモデルが次の条件を満足するかどうかで、その操作が許されるかどうかを判定する。
【００７４】
・条件：
行動の階層上での、行動Ｘと行動Ｙとの共通の上位カテゴリのなかで最も（階層上で）下位のカテゴリをａｎｓ（Ｘ，Ｙ）とする。もし与えられたモデルで、ａｎｓ（Ａ，Ｂ）がａｎｓ（Ａ，Ｃ）の上位カテゴリであり、かつＡとＢは同じ行動グループに属するならば、Ｃも同じグループに属さなければならない。
【００７５】
この条件は、行動の階層上でより近い行動を優先的にまとめることを意味している。
【００７６】
（２）　図４の例を使って説明する。行動間の階層が必要であるので、図１５のような階層が与えられたものとする。マルコフモデルの生成までの動作は既述したと同様であり、７個の行動それぞれを個別のグループとするマルコフモデルが単純化モデルＭの初期値として設定する。このＭに対して許される単純化の操作は、行動の削除については全て許されるが、２つの行動をまとめる場合には、ＳとＡ、ＢとＣ、ＢとＤ、ＣとＤの組合せのみが許される（図１５行動間の階層の同一レベルのみが許される）。各操作の評価値は既述したと全く同様である。すなわち、行動の削除については、Ａを削除するのが最適で、その評価値は０．１２４である。一方、２つの行動をまとめる操作については、既述した最適であったＥとＦとの組合せが許されず、許されるもののなかでの最適なものはＢとＣの組合せで、その評価は０．１７２である。よって単純化のための操作としてはＡの除去が選択される。以下同様にして、単純性が与えられた閾値以下となるまで単純化を続ける。
【００７７】
（３）　以上の結果得られたものが、図１６のマルコフモデルを可視化表示したものである。
【００７８】
次に、図１７から図１８を用いて、図４の元データのうちの一部のデータの特定の行動についてだけ、行動の特徴をグラフとして表示する場合について以下説明する。
【００７９】
（１）これは、与えられたデータ全体を対象としてマルコフモデルの生成とその単純化を行ってデータ全体の行動の特徴を知る必要はなく、一部のデータの特定の行動についてだけ、行動の特徴を表示したい場合も多い。このような場合には、全体での単純性が閾値以下となるようにマルコフモデルを単純化するため、知りたいと思っている部分に相当する行動が削除されたり、知りたい部分とは別の部分が多く表示される可能性がある。このような問題をさけるために、入力された分析範囲に関する条件を満足するデータだけ以後の処理の対象とすることで、知りたい範囲での情報量の大きいモデルを表示するものである。
【００８０】
（２）　まず、入力されたデータ中で、入力された条件を満足するデータを抜き出す。次に、抜き出したデータだけをつかってマルコフモデルを生成する。例えば既述した図４の元データに加えて分析範囲に関する条件、例えば
性別＝男性＆行動∈｛Ａ，Ｂ，　Ｄ，Ｅ，Ｆ｝
を与えると、図１７のようなデータを抜き出し（単に男性のデータを抜き出しているだけでなく、行動履歴から上の条件に含まれない行動、すなわちＳおよびＣを取除く）、これをもとに図１８のようなマルコフモデルを生成する。
【００８１】
（３）　これ以後は、既述したと同様に、単純化を行ってその結果をグラフとして表示する。
【００８２】
次に、図１９から図２５を用いて、元データの行動履歴だけでなく、その属性の値を考慮して単純化を行ってグラフ化する場合について詳細に説明する。
【００８３】
（１）　今までは、入力されたデータのうち、行動履歴にのみに着目してマルコフモデルの単純化を行い、それ以外の属性の値は無視していた。そのため、行動履歴中の行動順序が以外の属性の値によって大きく異なるような場合には、それをうまく捕らえることができない。例えば図４の例で、単純化のための操作として、最初にＥとＦを同一のグループとすることを選択する。これは、全データを対象としてみればＥとＦは他の行動との間の遷移確率が全く等しく、これらの行動をひとまとめにしても情報が失われないと考えられるからである。しかし、遷移確率を性別を考慮して調べると、ＢからＥへの遷移やＤからＦへの遷移が起こるのは男性の場合のみであり、逆にＢからＦへの遷移やＤからＥへの遷移は女性でのみ起こることが分かる。すなわち、ＥとＦとをまとめることは、このような性別による遷移の差に関する情報を失う結果となる。
【００８４】
（２）　このような問題点を解決するために、単純化されたモデルの情報量を評価する際に、全データから計算された初期確率および遷移確率のほかに、他の属性の可能な値毎に、その値をとるデータだけから求めた初期確率と遷移確率を使って、単純化のための操作による情報量の変化を評価する。すなわち、単純化モデルＭの情報量ｈ（Ｍ）を次のように計算する。
【００８５】
ｈ（Ｍ）＝（１−ω）×ｇａｌｌ（Ｍ）＋ω×Σｘ×Σｖ　ｐ（ｘ＝ｖ）×ｇｘ＝ｖ（Ｍ）　　（式８）
ここで、ｇａｌｌ（Ｍ）は、Ｍ内の初期確率および遷移確率を、全てのデータ中での確率として計算した場合の情報量を式２をつかって計算した量、ｇｘ＝ｖ（Ｍ）は、属性ｘの値がｖであるデータ中の確率として式２を使って計算した情報量、ｐ（ｘ＝ｖ）は全データ中で属性ｘの値がｖであるデータの割合である。ωが１の場合には、完全に各属性値毎の確率分布だけから情報量を計算し、ω＝０の場合は既述したと図４から図８の場合４と同様である。
【００８６】
（３）　図４の例を使って、動作を説明する。以下の説明では、図４から図８の実施例との差を明確にするため、情報量の評価で用いるパラメータを、ω＝１とする。すなわち、情報量の評価には、属性値毎のマルコフモデルのみを用いる。α、β、γはこれまでと同じく、α＝β＝１、γ＝０とする。また、図１５から図１６の実施例で用いた行動の階層は与えられていないもとのとする。すなわち、行動をまとめる場合には任意の組合せが許されるとする。
【００８７】
（４）　図４では、行動履歴以外の属性は性別しかなく、その値は男ないし女であるから、まず、性別が男であるデータのみを使ったマルコフモデルと、性別が女であるデータのみを使ったマルコフモデルを生成する（図１９および図２０）。これらのマルコフモデルを使って、行動の削除やまとめあげを行う。これまで通り、単純化における初期モデルは、全ての行動を、別々のグループとして含むモデルであり、その単純性は７である。これまでと同様、単純性の閾値を５とすると、初期モデルは十分単純ではないので、行動の除去ないしは、行動のまとめあげを行う。
【００８８】
（５）　これらの単純化のための操作では、いずれも単純性は１減少（減少は単純性の向上を表す）するから、その評価値は情報量の変化自身となる。まず、行動の除去の評価を考える。式８で示したように、ある行動を取り除いたときの情報量の変化は、性別＝男に対するモデルにおける情報量の変化と、性別＝女のモデルでの情報量の変化を、性別＝男と性別＝女の割合を重みとして足したものである。性別＝男と性別＝女のモデルから、各行動を取除いたときの情報量の変化は、図２１および図２２における各遷移の情報量から計算できて、図２４の（ａ）および（ｂ）のようになる。
【００８９】
（６）　一方、データ中に男および女の割合はそれぞれ５０％づつであるから、各行動を取除いたときの評価値は、図２４の（ｃ）のようになる。すなわち、行動Ａを取除くのが最もよく、その評価値は０．１２４である。一方、２つの行動をひとつのグループにまとめる操作も、男および女のモデルにおける情報量の変化の重み付き平均をとると、ＢとＣをまとめるのが最適で、その評価は０．１７６となる。ちなみに既述した図９から図１４の実施例では最適な操作として選択されたＥとＦとの選択は、性別が男の場合および女の場合の双方で、行動ＢおよびＤからの遷移確率が大きく異なるため、その評価値は悪化し、０．２４２である。その結果行動Ａの除去が最適な操作として選択される。Ａを除去してもモデルの単純性は６であるので、もう一度単純化の操作が必要になる。
【００９０】
（７）　最初の単純化と同様に各操作の評価値を計算すると、ＢとＣをまとめる操作が最適となる。その操作を行うと単純性が５、すなわち閾値以下となるので、単純化モデル選択部は終了する。図２５に得られた単純化したマルコフモデルの有向グラフの例を示す。
【００９１】
図１９は、本発明の説明図（性別＝男の場合のマルコフモデル）を示す。これは既述した図４の元データ中から性別＝男のみの行動履歴を取りだし、各行動の初期確率および行動間の遷移確率を算出してテーブルに設定したものである。
【００９２】
図２０、本発明の説明図（性別＝女の場合のマルコフモデル）を示す。これは既述した図４の元データ中から性別＝女のみの行動履歴を取りだし、各行動の初期確率および行動間の遷移確率を算出してテーブルに設定したものである。
【００９３】
図２１は、本発明の説明図（性別＝男のマルコフモデルにおける各遷移の情報量）を示す。これは、既述した図１９の性別＝男のマルコフモデルについて、算出した遷移の情報量である。
【００９４】
図２２は、本発明の説明図（性別＝女のマルコフモデルにおける各遷移の情報量）を示す。これは、既述した図１９の性別＝女のマルコフモデルについて、算出した遷移の情報量である。
【００９５】
図２３は、本発明の説明図（性別＝男と性別＝女の遷移確率から計算した情報量（の加重和））を示す。これは、既述した図２１の性別＝男、図２２の性別＝女のそれぞれの遷移の情報量の加重和を求めてテーブルに設定したものである。
【００９６】
図２４は、本発明の説明図（各行動を取除く単純化操作の評価値）を示す。これは、性別＝男における各行動の情報量、性別＝女における各行動の情報量、および各行動の評価値をそれぞれ算出して図２４の（ａ），（ｂ），（ｃ）に設定したものである。
【００９７】
図２５は、本発明の説明図（性別を考慮して単純化したマルコフモデルの可視化）を示す。ここでは、既述した図２１の性別＝男、図２２の性別＝女のマルコフモデルについてＢ，Ｃを１つの行動グループにまとめおよび行動Ａを削除した後の単純化したマルコフモデルをそれぞれグラフ化したものである。
【００９８】
（付記１）
行動をノードおよび当該行動の遷移をアークで表現するグラフを表示する行動データ表示方法において、
行動主体の行動履歴をもとに各行動の初期確率および行動間の遷移確率を算出するステップと、
前記算出した各行動の初期確率および行動間の遷移確率をもとに、行動あるいは行動から他の行動への遷移を取り除いたときの単純性を算出するステップと、
前記算出した単純性の最小のものを取り除くステップと、
前記単純化した後の各行動および行動間の遷移確率をもとに当該行動をノードおよび行動間の遷移をアークで表現したグラフを生成するステップと
を有する行動データ表示方法。
【００９９】
（付記２）
前記単純化は、行動あるいは遷移の取り除く前から後の情報量の減少量に対する、取り除く前から後の行動の減少量の比が最小のものを取り除くことを特徴とする付記１記載の行動データ表示方法。
【０１００】
（付記３）
前記行動履歴中の行動の遷移確率が類似した複数の行動をまとめて１つの行動としてグループ化したことを特徴とする付記１あるいは付記２記載の行動データ表示方法。
【０１０１】
（付記４）
前記複数の行動をまとめて１つの行動にグループ化する際に、予め定義された行動の階層に従ってまとめることを特徴とする付記３記載の行動データ表示方法。
【０１０２】
（付記５）
前記行動履歴中の、指定された行動あるいは指定された行動の範囲についてのみ、グラフを生成することを特徴とする付記１から付記４のいずれかに記載の行動データ表示方法。
【０１０３】
（付記６）
前記行動履歴に付随する属性をもとに、行動間の遷移確率の属性依存性を考慮し、前記単純化を行うことを特徴とする請求項１から請求項５のいずれかに記載の行動データ表示方法。
【０１０４】
（付記７）
行動をノードおよび当該行動の遷移をアークで表現するグラフを表示する行動データ表示装置において、
行動主体の行動履歴をもとに各行動の初期確率および行動間の遷移確率を算出する手段と、
前記算出した各行動の初期確率および行動間の遷移確率をもとに、行動あるいは行動から他の行動への遷移を取り除いたときの単純性を算出する手段と、
前記算出した単純性の最小のものを取り除く手段と、
前記単純化した後の各行動および行動間の遷移確率をもとに当該行動をノードおよび行動間の遷移をアークで表現したグラフを生成する手段と
を備えたことを特徴とする行動データ表示装置。
【０１０５】
【発明の効果】
以上説明したように、本発明によれば、行動履歴をもとに各行動の初期確率および行動間の遷移確率を算出し、これらから単純性の高い行動あるいは遷移を取り除いて単純化を行い、行動をノードおよび行動間の遷移をアークで表現したグラフを生成する構成を採用しているため、多量のデータから単純性の高い行動、遷移を取り除いて情報量の多い特徴的な部分を見やすくしたグラフを自動生成することが可能となる。
【図面の簡単な説明】
【図１】本発明のシステム構成図である。
【図２】本発明の動作説明フローチャート（全体）である。
【図３】本発明の動作説明フローチャート（単純化）である。
【図４】本発明の説明図（元データ）である。
【図５】本発明の説明図（マルコフデータ）である。
【図６】本発明の説明図（情報量／評価値）である。
【図７】本発明の説明図である。
【図８】本発明の説明図（グラフ）である。
【図９】本発明の他の動作説明フローチャート（単純化）である。
【図１０】本発明の説明図（行動ＢとＣをまとめたときの遷移確率）である。
【図１１】本発明の説明図（ＥとＦをまとめてひとつのグループとしたときのマルコフモデル）である。
【図１２】本発明の説明図（単純化されたマルコフモデル）である。
【図１３】本発明の説明図（ＥとＦをひとつのグループにした後の各遷移の情報量）である。
【図１４】本発明の説明図（行動の削除とグループ化で単純化したマルコフモデルの可視化）である。
【図１５】本発明の説明図（行動間の階層関係）である。
【図１６】本発明の説明図（マルコフモデルの例）である。
【図１７】本発明の説明図（マルコフモデル生成に使われるデータ／与えられた条件を満足するデータ）である。
【図１８】本発明の説明図（データから生成されるマルコフモデル）である。
【図１９】本発明の説明図（性別＝男の場合のマルコフモデル）である。
【図２０】本発明の説明図（性別＝女の場合のマルコフモデル）である。
【図２１】本発明の説明図（性別＝男の場合のマルコフモデルにおける各遷移の情報量）である。
【図２２】本発明の説明図（性別＝女の場合のマルコフモデルにおける各遷移の情報量）である。
【図２３】本発明の説明図（性別＝男と性別＝女の遷移確率から計算した情報量（の加重和））である。
【図２４】本発明の説明図（各行動を取除く単純化操作の評価値）である。
【図２５】本発明の説明図（性別を考慮して単純化したマルコフモデルの可視化）である。
【図２６】従来のマルコフモデルを単純化しないで表示した例である。
【符号の説明】
１：行動履歴データ
２：属性データ
３：分析範囲
４：行動履歴データ入力手段
５：属性データ入力手段
６：分析範囲入力手段
７：マルコフモデル生成手段
８：単純化モデル生成手段
９：行動グループ化手段
１０：行動階層管理手段
１１：単純化モデル評価手段
１２：属性依存性評価手段
１３：フラグ生成手段
１４：グラフ出力手段
【図１】
2004102681.tif 000003
【図２】
2004102681.tif 000004
【図３】
2004102681.tif 000005
【図４】
2004102681.tif 000006
【図５】
2004102681.tif 000007
【図６】
2004102681.tif 000008
【図７】
2004102681.tif 000009
【図８】
2004102681.tif 000010
【図９】
2004102681.tif 000011
【図１０】
2004102681.tif 000012
【図１１】
2004102681.tif 000013
【図１２】
2004102681.tif 000014
【図１３】
2004102681.tif 000015
【図１４】
2004102681.tif 000016
【図１５】
2004102681.tif 000017
【図１６】
2004102681.tif 000018
【図１７】
2004102681.tif 000019
【図１８】
2004102681.tif 000020
【図１９】
2004102681.tif 000021
【図２０】
2004102681.tif 000022
【図２１】
2004102681.tif 000023
【図２２】
2004102681.tif 000024
【図２３】
2004102681.tif 000025
【図２４】
2004102681.tif 000026
【図２５】
2004102681.tif 000027
【図２６】
2004102681.tif 000028