(57)【要約】【課題】大量の移動体の行動履歴から、移動体が訪問する訪問場所と訪問順序と、各訪問場所における滞在時間とで表された、多くの移動体に共通する行動パターンを容易に抽出することができるデータ抽出方法および装置を提供する。【解決手段】複数の訪問場所のうち移動体が訪問した訪問場所と各訪問場所での滞在時間と各訪問場所への訪問順序とでそれぞれ表される複数の行動履歴データを記憶し、複数の行動履歴データを基に、複数の訪問場所のそれぞれについて、当該訪問場所における滞在時間を分類するための複数の区分を設定し、複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間について、複数の区分のそれぞれに対する適合性の評価値を求める。複数の行動履歴データと評価値を基に、複数の行動履歴データから、訪問場所と各該訪問場所における複数の区分のうちの１つと訪問順序で表される特徴行動パターンを抽出する。【選択図】  図１
2005056022.tif 000002
【特許請求の範囲】
【請求項１】
複数の訪問場所を含む空間内を移動する複数の移動体のそれぞれに対応する行動履歴データであって、前記複数の訪問場所のうち当該移動体が訪問した訪問場所と各訪問場所での滞在時間と各訪問場所への訪問順序とでそれぞれ表される複数の行動履歴データを記憶する記憶手段と、
前記複数の行動履歴データを基に、前記複数の訪問場所のそれぞれについて、当該訪問場所における滞在時間を分類するための複数の区分を設定する設定手段と、
前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間について、前記複数の区分のそれぞれに対する適合性の評価値を求める評価手段と、
前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における前記複数の区分のそれぞれに対する評価値とを基に、前記複数の行動履歴データから、それぞれが前記複数の訪問場所のうちの１つと当該訪問場所における前記複数の区分のうちの１つとで表された複数の第１の特徴行動パターンを抽出する抽出手段と、
前記複数の第１の特徴行動パターンを組み合わせて、それぞれが、前記複数の訪問場所のうちの２つの訪問場所と、当該２つの訪問場所のそれぞれにおける前記複数の区分のうちの１つと、当該２つの訪問場所への訪問順序とで表される複数の第１の行動パターンを生成する第１の生成手段と、
前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の前記複数の区分のそれぞれに対する評価値とを基に、前記複数の第１の行動パターンのなかから、前記複数の行動履歴データに出現する頻度の高い複数の第２の特徴行動パターンを選択する第１の選択手段と、
前記複数の第２の特徴行動パターンを組合せて、それぞれが、前記複数の訪問場所のうちの３つの訪問場所と、当該３つの訪問場所のそれぞれにおける前記複数の区分のうちの１つと、当該３つの訪問場所への訪問順序とで表される複数の第２の行動パターンを生成する第２の生成手段と、
前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の前記複数の区分のそれぞれに対する評価値とを基に、前記複数の第２の行動パターンのなかから、前記複数の行動履歴データに出現する頻度の高い複数の第３の特徴行動パターンを選択する第２の選択手段と、
を具備したことを特徴とするデータ抽出装置。
【請求項２】
前記抽出手段は、
それぞれが前記複数の訪問場所のうちの１つと当該訪問場所における複数の区分のうちの１つとで表される複数の第３の行動パターンを生成する第１の手段と、
前記複数の第３の行動パターンのそれぞれに対し、当該第３の行動パターンが前記複数の行動履歴データに出現する頻度を表す支持度を求める第２の手段と、
前記複数の第３の行動パターンのうち、予め指定された閾値以上の前記支持度を有する第３の行動パターンを前記第１の特徴行動パターンとして選択する第３の手段と、
を有することを特徴とする請求項１記載のデータ抽出装置。
【請求項３】
前記第２の手段は、
前記複数の行動履歴データから前記複数の第３の行動パターンのうちの１つである対象行動パターンを含む行動履歴データを求め、前記対象行動パターンで特定されている区分に対する、当該対象行動パターンを含む各行動履歴データの前記評価値の総和を当該対象行動パターンの支持度として求めることを特徴とする請求項２記載のデータ抽出装置。
【請求項４】
前記第１の選択手段は、
前記複数の第１の行動パターンのそれぞれに対し、当該第１の行動パターンが前記複数の行動履歴データに出現する頻度を表す支持度を求めて、前記複数の第１の行動パターンのうち予め指定された閾値以上の前記支持度を有する第１の行動パターンを前記第２の特徴行動パターンとして選択することを特徴とする請求項１記載のデータ抽出装置。
【請求項５】
前記第１の選択手段は、（ａ）前記複数の行動履歴データから前記複数の第１の行動パターンのうちの１つである対象行動パターンを含む行動履歴データを求め、（ｂ）前記対象行動パターンで特定されている各区分に対する、当該対象行動パターンを含む各行動履歴データの評価値を基に、対象行動パターンを含む行動履歴データの前記対象行動パターンに対する適合度を求め、（ｃ）前記対象行動パターンを含む各行動履歴データから求めた前記適合度の総和を当該対象行動パターンの支持度として算出することを特徴とする請求項４記載のデータ抽出装置。
【請求項６】
前記第１の生成手段は、
前記複数の訪問場所間の移動を制約する条件・規則を表した第１の条件データと、前記移動体が前記複数の訪問場所のうち任意の２つの訪問場所の間を移動する際に経由する訪問場所の数の上限値を定めた第２の条件データとを基に、前記複数の第１の特徴行動パターンを組み合わせて、前記複数の第１の行動パターンを生成することを特徴とする請求項１記載のデータ抽出装置。
【請求項７】
前記設定手段は、前記複数の訪問場所のそれぞれにおける滞在時間を分類するためのメンバーシップ関数を設定し、
前記評価手段は、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の、前記複数の区分のそれぞれに対する適合性の評価値を前記メンバシップ関数を用いて算出することを特徴とする請求項１記載のデータ抽出装置。
【請求項８】
前記複数の行動履歴データを基に、前記複数の訪問場所のそれぞれについて、滞在時間別に当該場所を訪問した移動体の総数を求めて、前記複数の訪問場所のそれぞれにおける滞在時間別の移動体の総数の分布状況を表すグラフを表示する手段と、
前記グラフに基づき、前記複数の訪問場所のそれぞれについて前記設定手段で前記複数の区分を設定するために必要なパラメータを入力するための手段と、
をさらに具備したことを特徴とする請求項１記載のデータ抽出装置。
【請求項９】
前記第２の選択手段は、
前記複数の第２の行動パターンのそれぞれに対し、当該第２の行動パターンが前記複数の行動履歴データに出現する頻度を表す支持度を求めて、前記複数の第２の行動パターンのうち予め指定された閾値以上の前記支持度を有する第２の行動パターンを前記第３の特徴行動パターンとして選択することを特徴とする請求項１記載のデータ抽出装置。
【請求項１０】
前記第２の選択手段は、（ａ）前記複数の行動履歴データから前記複数の第２の行動パターンのうちの１つである対象行動パターンを含む行動履歴データを求め、（ｂ）前記対象行動パターンで特定されている各区分に対する、当該対象行動パターンを含む各行動履歴データの評価値を基に、対象行動パターンを含む行動履歴データの前記対象行動パターンに対する適合度を求め、（ｃ）前記対象行動パターンを含む各行動履歴データから求めた前記適合度の総和を当該対象行動パターンの支持度として算出することを特徴とする請求項９記載のデータ抽出装置。
【請求項１１】
複数の訪問場所を含む空間内を移動する複数の移動体のそれぞれに対応する行動履歴データであって、前記複数の訪問場所のうち当該移動体が訪問した訪問場所と各訪問場所での滞在時間と各訪問場所への訪問順序とでそれぞれ表される複数の行動履歴データを記憶手段に記憶するステップと、
前記複数の行動履歴データを基に、前記複数の訪問場所のそれぞれについて、当該訪問場所における滞在時間を分類するための複数の区分を設定する設定ステップと、
前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間について、前記複数の区分のそれぞれに対する適合性の評価値を求める評価ステップと、
前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における前記複数の区分のそれぞれに対する評価値とを基に、前記複数の行動履歴データから、それぞれが前記複数の訪問場所のうちの１つと当該訪問場所における前記複数の区分のうちの１つとで表された複数の第１の特徴行動パターンを抽出する抽出ステップと、
前記複数の第１の特徴行動パターンを組み合わせて、それぞれが、前記複数の訪問場所のうちの２つの訪問場所と、当該２つの訪問場所のそれぞれにおける前記複数の区分のうちの１つと、当該２つの訪問場所への訪問順序とで表される複数の第１の行動パターンを生成する第１の生成ステップと、
前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の前記複数の区分のそれぞれに対する評価値とを基に、前記複数の第１の行動パターンのなかから、前記複数の行動履歴データに出現する頻度の高い複数の第２の特徴行動パターンを選択する第１の選択ステップと、
前記複数の第２の特徴行動パターンを組合せて、それぞれが、前記複数の訪問場所のうちの３つの訪問場所と、当該３つの訪問場所のそれぞれにおける前記複数の区分のうちの１つと、当該３つの訪問場所への訪問順序とで表される複数の第２の行動パターンを生成する第２の生成ステップと、
前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の前記複数の区分のそれぞれに対する評価値とを基に、前記複数の第２の行動パターンのなかから、前記複数の行動履歴データに出現する頻度の高い複数の第３の特徴行動パターンを選択する第２の選択ステップと、
を有することを特徴とするデータ抽出方法。
【請求項１２】
前記第１の抽出ステップは、
それぞれが前記複数の訪問場所のうちの１つと当該訪問場所における複数の区分のうちの１つとで表される複数の第３の行動パターンを生成する第１のステップと、
前記複数の第３の行動パターンのそれぞれに対し、当該第３の行動パターンが前記複数の行動履歴データに出現する頻度を表す支持度を求める第２のステップと、
前記複数の第３の行動パターンのうち、予め指定された閾値以上の前記支持度を有する第３の行動パターンを前記第１の特徴行動パターンとして選択する第３のステップと、
を有することを特徴とする請求項１１記載のデータ抽出方法。
【請求項１３】
前記第２のステップは、
前記複数の行動履歴データから前記複数の第３の行動パターンのうちの１つである対象行動パターンを含む行動履歴データを求め、前記対象行動パターンで特定されている区分に対する、当該対象行動パターンを含む各行動履歴データの前記評価値の総和を当該対象行動パターンの支持度として求めることを特徴とする請求項１２記載のデータ抽出方法。
【請求項１４】
前記第１の選択ステップは、
前記複数の第１の行動パターンのそれぞれに対し、当該第１の行動パターンが前記複数の行動履歴データに出現する頻度を表す支持度を求めて、前記複数の第１の行動パターンのうち予め指定された閾値以上の前記支持度を有する第１の行動パターンを前記第２の特徴行動パターンとして選択することを特徴とする請求項１１記載のデータ抽出方法。
【請求項１５】
前記第１の選択ステップは、（ａ）前記複数の行動履歴データから前記複数の第１の行動パターンのうちの１つである対象行動パターンを含む行動履歴データを求め、（ｂ）前記対象行動パターンで特定されている各区分に対する、当該対象行動パターンを含む各行動履歴データの評価値を基に、対象行動パターンを含む行動履歴データの前記対象行動パターンに対する適合度を求め、（ｃ）前記対象行動パターンを含む各行動履歴データから求めた前記適合度の総和を当該対象行動パターンの支持度として算出することを特徴とする請求項１４記載のデータ抽出方法。
【請求項１６】
前記第１の生成ステップは、
前記複数の訪問場所間の移動を制約する条件・規則を表した第１の条件データと、前記移動体が前記複数の訪問場所のうち任意の２つの訪問場所の間を移動する際に経由する訪問場所の数の上限値を定めた第２の条件データとを基に、前記複数の第１の特徴行動パターンを組み合わせて、前記複数の第１の行動パターンを生成することを特徴とする請求項１１記載のデータ抽出方法。
【請求項１７】
前記設定ステップは、前記複数の訪問場所のそれぞれにおける滞在時間を分類するためのメンバーシップ関数を設定し、
前記評価ステップは、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の、前記複数の区分のそれぞれに対する適合性の評価値を前記メンバシップ関数を用いて算出することを特徴とする請求項１１記載のデータ抽出方法。
【請求項１８】
複数の訪問場所を含む空間内を移動する複数の移動体のそれぞれに対応する行動履歴データであって、前記複数の訪問場所のうち当該移動体が訪問した訪問場所と各訪問場所での滞在時間と各訪問場所への訪問順序とでそれぞれ表される複数の行動履歴データを記憶手段に記憶するステップと、
前記複数の行動履歴データを基に、前記複数の訪問場所のそれぞれについて、当該訪問場所における滞在時間を分類するための複数の区分を設定する設定ステップと、
前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間について、前記複数の区分のそれぞれに対する適合性の評価値を求める評価ステップと、
前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における前記複数の区分のそれぞれに対する評価値とを基に、前記複数の行動履歴データから、それぞれが前記複数の訪問場所のうちの１つと当該訪問場所における前記複数の区分のうちの１つとで表された複数の第１の特徴行動パターンを抽出する抽出ステップと、
前記複数の第１の特徴行動パターンを組み合わせて、それぞれが、前記複数の訪問場所のうちの２つの訪問場所と、当該２つの訪問場所のそれぞれにおける前記複数の区分のうちの１つと、当該２つの訪問場所への訪問順序とで表される複数の第１の行動パターンを生成する第１の生成ステップと、
前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の前記複数の区分のそれぞれに対する評価値とを基に、前記複数の第１の行動パターンのなかから、前記複数の行動履歴データに出現する頻度の高い複数の第２の特徴行動パターンを選択する第１の選択ステップと、
前記複数の第２の特徴行動パターンを組合せて、それぞれが、前記複数の訪問場所のうちの３つの訪問場所と、当該３つの訪問場所のそれぞれにおける前記複数の区分のうちの１つと、当該３つの訪問場所への訪問順序とで表される複数の第２の行動パターンを生成する第２の生成ステップと、
前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の前記複数の区分のそれぞれに対する評価値とを基に、前記複数の第２の行動パターンのなかから、前記複数の行動履歴データに出現する頻度の高い複数の第３の特徴行動パターンを選択する第２の選択ステップと、
をコンピュータに実行させるためのデータ抽出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、膨大なデータのなかから有用な相関規則を抽出する情報抽出（データマイニング）装置に関する。
【０００２】
【従来の技術】
大規模なデータベースから規則性を抽出するためのデータマイニング手法として相関規則のマイニング方法が存在する。相関規則とは、同一レコード（レコードの構成単位をアイテムと呼ぶ）内に現れやすいアイテム集合の組み合わせである。例えば、「アイテム集合Ａを含むレコードはアイテム集合Ｂを含む」（Ａ→Ｂ）と記され、Ａは条件部、Ｂは結論部と呼ばれる。消費者の購買傾向を発見する等、幅広い分野に用いられている。
【０００３】
大規模データベースから相関規則を抽出する方法としては、Ｒ．  Ａｇｒａｗａｌ  らによるＡｐｒｉｏｒｉと呼ばれるものがある（例えば、非特許文献１、特許文献１参照）。
【０００４】
特許文献１記載の技術では、アイテム集合Ａ→アイテム集合Ｂという相関規則を含むレコード数が総レコード数に占める割合を支持度とあらわし、アイテム集合Ａ→アイテム集合Ｂを含むレコード数がアイテム集合Ａを含むレコード数に占める割合を確信度とする。この２つの指標の下限値、最小支持度、最小確信度をユーザが指定し、共にそれ以上となるような相関規則を抽出する。
【０００５】
また、Ａｐｒｉｏｒｉを応用した例として、時系列データより予め定めた一定時間幅における各種の属性変化パターンに対応した相関規則を抽出するデータマイニング方法がある（例えば、特許文献２参照）。
【０００６】
一方、データマイニング前処理として、属性値のグルーピングや特定条件を満たすレコードの選択をユーザが行い、抽出した相関規則のうちユーザが指定した項目を含む相関規則と相関規則数を結果表示部に表示する方法がある（例えば、特許文献３参照）。
【０００７】
大量に存在する離散的な行動履歴データより、多くの移動体に共通する特徴的な行動パターンを抽出したいというニーズがある。このニーズに対し従来技術を適用しようとする場合、次のような課題がある。
【０００８】
特許文献１記載の技術では、行動履歴データベースを用いることで、多くの移動体に共通する訪問場所を抽出することは可能である。しかし、移動体の行動パターンの抽出方法として考えた時、ある訪問場所に長時間滞在しているのか、短時間滞在しているのかによってそこでの行動は異なると考えられるが、特許文献１記載の技術では、それを区別して扱うことができない。また、訪問場所間に許される制約条件を考慮しておらず、不合理な解を出すおそれがあると同時に、計算量の増大を招く可能性がある。
【０００９】
特許文献２記載の技術は、行動履歴に時間の概念を入れてはいるものの、訪問場所における滞在時間を考慮するものではなく、本ニーズには対応できない。
【００１０】
特許文献３記載の技術は、数値属性をユーザの指定によって離散カテゴリ化して扱えるため、滞在時間を考慮できる。しかし、例えば、滞在時間３０分間未満を短期滞在、３０分間以上を長期滞在とする場合、２９分間と３０分間は１分しか滞在時間に違いがないにもかかわらず、短期と長期に分けられてしまうという問題点がある。また、結果に対してユーザがアイテムを指定することによって表示する相関規則を調節することができるが、調節するのはあくまでも表示部分のみであり、相関規則の抽出自体は同じ手続きである。
【００１１】
【非特許文献１】
”Ｆａｓｔ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｍｉｎｉｎｇ  Ａｓｓｏｃｉａｔｉｏｎ  Ｒｕｌｅｓ”（Ｐｒｏｃ．ｏｆ  ｔｈｅ  ２０ｔｈ  Ｉｎｔ’ｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｖｅｒｙ  Ｌａｒｇｅ  ＤａｔａＢａｓｅｓ、１９９４）
【００１２】
【特許文献１】
特開平８−２６３３４６号公報
【００１３】
【特許文献２】
特開２０００−２４２６３２公報
【００１４】
【特許文献３】
特開平１１−２５００８４号公報
【００１５】
【発明が解決しようとする課題】
このように、従来は、移動体が訪問する訪問場所と訪問順序と、各訪問場所における滞在時間とを考慮して、大量の移動体の行動履歴から、多くの移動体に共通する行動パターンを抽出することができないという問題点があった。
【００１６】
そこで、本発明は、上記問題点に鑑み、大量の移動体の行動履歴から、移動体が訪問する訪問場所と訪問順序と、各訪問場所における滞在時間とで表された、多くの移動体に共通する行動パターンを容易に抽出することができるデータ抽出方法および装置を提供することを目的とする。
【００１７】
【課題を解決するための手段】
本発明は、（ａ）複数の訪問場所を含む空間内を移動する複数の移動体のそれぞれに対応する行動履歴データであって、前記複数の訪問場所のうち当該移動体が訪問した訪問場所と各訪問場所での滞在時間と各訪問場所への訪問順序とでそれぞれ表される複数の行動履歴データを記憶手段に記憶し、（ｂ）前記複数の行動履歴データを基に、前記複数の訪問場所のそれぞれについて、当該訪問場所における滞在時間を分類するための複数の区分を設定し、（ｃ）前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間について、前記複数の区分のそれぞれに対する適合性の評価値を求める。（ｄ）前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における前記複数の区分のそれぞれに対する評価値とを基に、前記複数の行動履歴データから、それぞれが前記複数の訪問場所のうちの１つと当該訪問場所における前記複数の区分のうちの１つとで表された複数の第１の特徴行動パターンを抽出する。さらに、（ｅ）前記複数の第１の特徴行動パターンを組み合わせて、それぞれが、前記複数の訪問場所のうちの２つの訪問場所と、当該２つの訪問場所のそれぞれにおける前記複数の区分のうちの１つと、当該２つの訪問場所への訪問順序とで表される複数の第１の行動パターンを生成し、（ｆ）前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の前記複数の区分のそれぞれに対する評価値とを基に、前記複数の第１の行動パターンのなかから、前記複数の行動履歴データに出現する頻度の高い複数の第２の特徴行動パターンを選択する。さらに、（ｇ）前記複数の第２の特徴行動パターンを組合せて、それぞれが、前記複数の訪問場所のうちの３つの訪問場所と、当該３つの訪問場所のそれぞれにおける前記複数の区分のうちの１つと、当該３つの訪問場所への訪問順序とで表される複数の第２の行動パターンを生成し、（ｈ）前記複数の行動履歴データと、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の前記複数の区分のそれぞれに対する評価値とを基に、前記複数の第２の行動パターンのなかから、前記複数の行動履歴データに出現する頻度の高い複数の第３の特徴行動パターンを選択する。
【００１８】
本発明によれば、複数の移動体のそれぞれの行動履歴を当該移動体が訪問した訪問場所と各訪問場所での滞在時間と各訪問場所への訪問順序とで表し、大量の行動履歴を基に、各訪問場所について、当該訪問場所における滞在時間を分類するための複数の区分を設定して、各行動履歴に含まれる各訪問場所における滞在時間について、複数の区分のそれぞれに対する適合性の評価値を求めておく。このような前処理を行うことにより、上記大量の行動履歴から、多くの移動体に共通する第１の特徴行動パターン（１つの訪問場所と、当該訪問場所における複数の区分のうちの１つとで表される特徴行動パターン）と、第２の特徴行動パターン（２つの訪問場所と、当該２つの訪問場所のそれぞれにおける複数の区分のうちの１つと、当該２つの訪問場所への訪問順序とで表される特徴行動パターン）と、第３の特徴行動パターン（３つの訪問場所と、当該３つの訪問場所のそれぞれにおける複数の区分のうちの１つと、当該３つの訪問場所への訪問順序とで表される特徴行動パターン）を容易に抽出することができる。
【００１９】
好ましくは、各訪問場所における滞在時間を分類するためのメンバーシップ関数を設定し、前記複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の、前記複数の区分のそれぞれに対する適合性の評価値を前記メンバシップ関数を用いて算出することにより、区分間の境界に曖昧性をもたせて、行動履歴中の各訪問場所における滞在時間の各区分に対する評価値をより現実に即して求めることができる。その結果、信頼性の高い特徴行動パターンの抽出が可能となる。
【００２０】
また、複数の第１の特徴行動パターンを組み合わせて、複数の訪問場所間の移動を制約する条件・規則を表した第１の条件データ（制約データ）と、移動体が複数の訪問場所のうち任意の２つの訪問場所の間を移動する際に経由する訪問場所の数の上限値を定めた第２の条件データ（条件パラメータｃ）とを満たす、複数の第１の行動パターン（第２の特徴行動パターンを抽出する元となる行動パターンの集合（Ａ２））を生成する。そして、この複数の第１の行動パターンのなかかから第２の特徴行動パターンを選択する。第２の特徴行動パターンを選択する元となる行動パターンの集合（Ａ２）は、行動履歴データに出現する頻度の高い行動パターンの集合であり、候補数が予め絞り込まれているので、特徴行動パターン（第１の特徴行動パターン）を求めるための処理時間の短縮が図れる。
【００２１】
さらに、複数の行動履歴データから、複数の訪問場所のうちの３つ以上の訪問場所と、当該３つ以上の訪問場所のそれぞれにおける前記複数の区分のうちの１つと、当該３つ以上の訪問場所への訪問順序とで表される第ｎ（ｎは３以上の整数）の特徴行動パターンを抽出する際には、上記第３の特徴行動パターンを求める場合と同様である。すなわち、（ａ）第（ｎ−１）の特徴行動パターンを組み合わせて、それぞれが、複数の訪問場所のうちのｎ個の訪問場所と、当該ｎ個の訪問場所のそれぞれにおける前記複数の区分のうちの１つと、当該ｎ個の訪問場所への訪問順序とで表される複数の行動パターンを生成し、（ｂ）複数の行動履歴データと、当該複数の行動履歴データのそれぞれに含まれる各訪問場所における滞在時間の前記複数の区分のそれぞれに対する評価値とを基に、生成された複数の行動パターンのなかから、複数の行動履歴データに出現する頻度の高い複数の第ｎの特徴行動パターンを選択する。
【００２２】
【発明の実施の形態】
以下、本発明の実施形態について図面を参照して説明する。
【００２３】
（第１の実施形態）
図１は、本発明の実施形態にかかるデータマイニング装置の構成例を示したものである。図１において、データマイニング装置は、行動履歴データ記憶部１、滞在時間評価部２、条件設定部３、評価値付き履歴データ記憶部４、特徴行動パターン抽出部５、特徴行動パターン記憶部６、制約データ記憶部７、表示部８、入力部９から構成される。
【００２４】
行動履歴データ記憶部１には、複数の訪問場所（例えば、観光地、会合や演芸会などの催し物（イベント）、Ｗｅｂページ、人、組織、場所の位置など）を含む活動空間における複数の移動体（ユーザが所持する携帯電話やＰＤＡなどの携帯端末などや、ユーザそのものであってもよい）の行動履歴データであって、当該複数の訪問場所のうち各移動体が訪問した訪問場所と当該訪問場所における滞在時間とを訪問した順序に従って記録した当該複数の移動体のそれぞれに対応した複数の行動履歴データが記憶されている。ここでは、訪問場所の一例として、地理的な場所（例えば、観光地など）を用いて説明する。
【００２５】
なお、行動履歴データ記憶部１は、記憶装置や記録媒体であってもよい。
【００２６】
図２は、行動履歴データ記憶部１に記憶された行動履歴データの一例を示したものである。各移動体の行動履歴データには、各移動体を識別するための移動体識別ＩＤ（図２では、ＰＩＤ０１、ＰＩＤ０２）のほか、当該移動体が訪問した各訪問場所（図２では、Ｐ１〜Ｐ４）と、当該訪問場所への到着時刻（図２ではＡ＿ＴＩＭＥ１１〜Ａ＿ＴＩＭＥ２４）と、当該訪問場所における滞在時間（図２ではＳ＿ＴＩＭＥ１１〜Ｓ＿ＴＩＭＥ２４）とを訪問した順に記録したものである。図２に示す行動履歴データには、さらに、行動履歴中の訪問場所の数（図２では、シーケンス長ＮＵＭ＿ＰＩＤ０１、ＮＵＭ＿ＰＩＤ０２）が含まれている。訪問順序は、各訪問場所への到着時刻によっても表されている。なお、行動履歴データは、訪問場所への到着および訪問場所からの離脱をあらわすイベントフラグ、訪問場所及びイベント発生時間の組を時系列に格納したものでもよい。
【００２７】
例えば、図２に示した移動体「ＰＩＤ０１」の行動履歴データでは、訪問した場所が全部でＮＵＭ＿ＰＩＤ０１箇所であり、訪問場所Ｐ１には時刻Ａ＿ＴＩＭＥ１１に到着し、Ｓ＿ＴＩＭＥ１１時間滞在し、次に時刻Ａ＿ＴＩＭＥ１２に訪問場所Ｐ２に到着し、Ｓ＿ＴＩＭＥ１２時間滞在したことが表されている。
【００２８】
なお、以下の説明では、移動体識別ＩＤと訪問場所については文字列で表し、滞在時間、到着時刻については数値で表している。
【００２９】
ここで、行動履歴データに含まれる滞在時間について説明する。例えば、ある訪問場所で買い物をする場合と、当該訪問場所を通過する場合とを比較すると、前者の場合の滞在時間は後者の場合の滞在時間よりも格段に長くなるものである。一般的に、滞在時間には、このような行動の目的の違いが反映されるものと考えられる。そこで、本実施形態では、移動体が訪問する場所と訪問順序とともに、このような行動の目的などの違いを反映する各訪問場所における滞在時間とで表された行動パターンを行動履歴として記録しておく。そして、図１のデータマイニング装置では、大量の移動体のそれぞれから得られた上記行動履歴から、移動体が訪問する訪問場所や訪問順序の他に、各訪問場所における滞在時間が、多くの移動体で共通する行動パターン（これを特徴行動パターンと呼ぶ）を抽出する。
【００３０】
行動パターンとは、ここでは、少なくとも１つの訪問場所とそこでの滞在時間、訪問場所が複数あるときには、各訪問場所とそこでの滞在時間（具体的には後述する滞在時間のセグメント（区分））を、その訪問順序に従って繋げたものである。１つの訪問場所と１つのセグメントとからなる組を、単に行動とも呼び、行動を訪問順に繋げたものが行動パターンである。シーケンス長がｋ（ｋは１以上）の行動パターンは、ｋ個の行動を、行動した順に（訪問順）に時系列に並べたものであると云える。
【００３１】
滞在時間評価部２は、行動履歴データ記憶部１に記憶された全ての行動履歴データから、各訪問場所における移動体の滞在時間の分布状況（例えば、後述するヒストグラム）を求め、各滞在時間を、その長さに応じて分類するために、訪問場所毎に複数の区分（セグメント）を定義する。各セグメントにはラベルを与える。そして、行動履歴データ記憶部１に記憶された各行動履歴データについて、当該行動履歴データ中の各訪問場所における移動体の滞在時間について、当該滞在時間の、上記複数のセグメントのそれぞれに対する適合性を表した評価値（ラベル値）を与える。その結果、行動履歴データ記憶部１に記憶された各行動履歴データ中の各訪問場所における滞在時間に、上記各ラベルに対応する評価値の付加された評価値付き履歴データが、評価値付き履歴データ記憶部４に記憶される。
【００３２】
滞在時間評価部２で求めた上記ヒストグラムは、表示部８により所定のディスプレイに表示される。セグメントは、この表示されたヒストグラムを基に、ユーザが所望の分割点を指定することで生成される。ヒストグラム上の分割点の位置情報などは、マウスやキーボードなどの入力装置を介して入力部９から入力される。この分割点は、セグメントを設定するために必要なパラメータである。
【００３３】
図３は、評価値付き履歴データ記憶部４に記憶される評価値付き履歴データの一例を示したものである。評価値付き行動履歴データは、上記行動履歴データの各訪問場所について、当該訪問場所に定義されたセグメント（ラベル）の数（図３では、ＮＵＭ＿Ｐ１からＮＵＭ＿Ｐ４）と、当該訪問場所の滞在時間に対する各セグメントへの適合性を表した評価値とを追加したものである。
【００３４】
図１の条件設定部３は、特徴行動パターン抽出部５で特徴行動パターンを抽出する際に用いる条件を設定するためのものである。ここで設定される条件は、条件パラメータｃと最小支持度である。
【００３５】
条件パラメータｃは、行動パターン（行動履歴データや評価値付き履歴データ中の行動パターン、特徴行動パターン）で表された２つの連続する訪問場所間を移動体が移動する際に経由する訪問場所の数を制限するものである。すなわち、パラメータｃは、行動パターン内で連続する訪問場所間に許容される他の訪問場所の数を表す。
【００３６】
最小支持度は、抽出すべき特徴行動パターンの支持度の最小値を表したものである。
【００３７】
条件設定部３は、条件パラメータｃや最小支持度の値として、ユーザが所望の値を直接入力するようになっている。あるいは、条件設定部３には条件パラメータｃや最小支持度の値としていくつか予め記憶されており、その中から、ユーザが所望の値を選択するようになっている。
【００３８】
特徴行動パターン抽出部５は、評価値付き履歴データ記憶部４に記憶された評価値付き履歴データ（以下、簡単に履歴データと呼ぶ）から、多くの移動体に共通する、訪問場所と当該訪問場所における滞在時間（当該訪問場所に定義された滞在時間の長さを分類するための複数のセグメントのうちの１つ）と訪問順序を表す行動パターンを特徴行動パターンとして抽出する。すなわち、特徴行動パターンは、評価値付き履歴データ記憶部４に記憶された履歴データに頻出する（出現する頻度の高い）行動パターンである。
【００３９】
特徴行動パターンを抽出する際には、上記条件設定部３で設定された条件（条件パラメータｃと最小支持度）と、制約データ記憶部７に記憶された制約データを用いる。制約データは、訪問場所間の移動体の行動（例えば移動）を制約する物理的、時間的な条件・規則である。
【００４０】
制約データとしては、ここでは、図４に示すような訪問場所間の地理的な連結関係を表したデータであるとする。例えば、図４に示す訪問場所Ｐ１〜Ｐ３の間の地理的な連結関係は、場所Ｐ１と場所Ｐ２との間は、経路Ｒ１で移動可能であり、場所Ｐ２と場所Ｐ３との間は経路Ｒ２で移動可能であることを表している。制約データ記憶部７には、このような地理的な連結関係を図５に示すような訪問場所の総数×訪問場所の総数の行列データとして記憶されている。ある訪問場所（列）とある訪問場所（行）が交わる要素の値が、その２訪問場所間を直接結ぶ経路数を表している。図５では、場所Ｐ２（ｋ＝２）から場所Ｐ３（ｉ＝３）への経路数ＥｋｉはＥ２３と表されている。なお、ここでは、行列上の各要素の値Ｅｋｉは経路数であるとしたが、経路の有無を表すデータであってもよい。例えば、経路があれば「１」、なければ「０」となる。
【００４１】
訪問場所Ｐ１〜Ｐ３の間に、図４に示すような地理的な連結関係が存在した場合の制約データを、図６に示す。ここでは、同じ場所を繰り返し訪問することは不可能とみなし、対角要素（Ｅ１１、Ｅ２２、Ｅ３３…）の値は「０」とする。場所Ｐ１と場所Ｐ２との間には、経路Ｒ１が１つあるので、Ｅ１２とＥ２１の値は「１」となる。また、場所Ｐ２と場所Ｐ３との間には、経路Ｒ２が１つあるので、Ｅ２３とＥ３２の値は「１」となる。それ以外の要素値は、「０」となる。
【００４２】
なお、同じ訪問場所を繰返し訪問することが可能であるとすると（例えば、図７に示すように、そのような地理的な連結関係があるとすると）、図６に示す行列データ中の対角要素Ｅ１１、Ｅ２２、Ｅ３３は、「１」となる。また、２訪問場所間において両方からの通行が可能ならば、当該２訪問場所間の連結関係を行列で表すと図６に示すような対称行列となる。一方、２訪問場所間の通行が一方方向の場合には対象行列とはならない。２訪問場所間において、両方からの通行が可能ならば、その対称性を利用して、制約データのデータ量を１／２に減らすことができる。
【００４３】
制約データ記憶部７に記憶する上記制約データを入力するための入力部（図１では図示せず）が設けられていてもよい。また、この入力部には、図５に示すような制約データを入力するためのインターフェースをもっていてもよい。この入力部は、複数種類の制約データを予め記憶しており、このなかからユーザが選択するようになっていてもよい。さらに選択された制約データを基にユーザが新たな制約データを作成するようになっていてもよい。
【００４４】
経路数は、ユーザが数えて、それを行列の要素として入力するようにしてもよい。
【００４５】
次に、滞在時間評価部２の処理動作について、図８に示すフローチャートを参照して説明する。
【００４６】
滞在時間評価部２は、行動履歴データ記憶部１に記憶されている行動履歴データを基に、以下の処理を行う。まず、全ての行動履歴データから全ての訪問場所を抽出する（ステップＳ１）。各訪問場所について、行動履歴データに記録されている各訪問場所における滞在時間別に当該訪問場所を訪問した移動体の数を計数して、図９に示すような、滞在時間を横軸上にとり、各滞在時間上に、当該滞在時間の間当該訪問場所に滞在した移動体の総数を表すヒストグラムを生成する（ステップＳ２）。図９に示すヒストグラムは、ある訪問場所Ｐ１についてのヒストグラムであるが、このようなヒストグラムを全ての訪問場所について生成する。
【００４７】
次に、図９に示した訪問場所毎のヒストグラムを基に、滞在時間の長さに応じて複数のセグメントを設定する。
【００４８】
ここでセグメントの設定方法の一例を説明する。図９に示すようなヒストグラムの横軸上に、セグメントの境界を表す分割点（ＴＰ＿１、ＴＰ＿２）として、０．５時間（３０分）と１時間がそれぞれユーザにより指定されると、この分割点を境界とする３つのセグメントが得られる（ステップＳ３）。各セグメントにはラベルを与える（ステップＳ４）。ここでは、短い滞在時間（例えばここでは０．５時間以下）のセグメントにはラベルＴＩＭＥＰ１＿１を付し、長い滞在時間（例えばここでは１時間以上）のセグメントにはラベルＴＩＭＥＰ１＿３を付し、これらの中間の長さの滞在時間（例えば、ここでは０．５時間以上１時間未満）のセグメントにはラベルＴＩＭＥＰ１＿２を与えている。ステップＳ３、ステップＳ４の処理は、全ての訪問場所について行われる。このようにしてセグメントを設定することにより、各セグメントに属する滞在時間の範囲が定められたことになる。
【００４９】
なお、上記分割点は、ユーザにより指定される。すなわち、図９に示すような各訪問場所について求めたヒストグラムを表示部８に表示し、これを元に、ユーザは、入力部９から所望の分割点を指定する。
【００５０】
このようにして、各訪問場所について、そこでの移動体の滞在時間の分布状況に応じて複数のセグメントが設定されると、次に、行動履歴データ記憶部１に記憶された各行動履歴データ中の各訪問場所における滞在時間について、当該滞在時間の、当該訪問場所に設定された複数のセグメントのそれぞれに対応する適合性を表す評価値を求める（ステップＳ５）。
【００５１】
例えば、図９に示したように、セグメントが定められている場合、ある行動履歴データ中のある訪問場所における滞在時間が０．２５時間であるとき、これは、セグメント「ＴＩＭＰ１＿１」に定められている滞在時間の時間範囲内であるから、当該構想履歴データ中の滞在時間の当該セグメント「ＴＩＭＰ１＿１」に対する評価値は「１」、それ以外のセグメントに対する評価値は「０」となる。
【００５２】
このようにして、訪問場所別の滞在時間に対し評価値を求める処理を、行動履歴データ記憶部１に記憶された全ての行動履歴データの全てについて行う。そして、このような訪問場所別の滞在時間に対する評価値を行動履歴データに付加して、図３に示したような履歴データが生成され、評価値付き履歴データ記憶部４に記憶される。
【００５３】
図３に示した履歴データにおいて、移動体ＰＩＤ０１の最初の訪問場所Ｐ１での滞在時間Ｓ＿ＴＩＭＥ１１が０．７５時間（４５分）であるとき、この滞在時間は、ＴＩＭＰ１＿２に分類される。従って、滞在時間０．７５時間の、セグメント「ＴＩＭＰ１＿１」、「ＴＩＭＰ１＿２」、「ＴＩＭＰ１＿３」のそれぞれに対する適合性を表す評価値は、それぞれ「０」、「１」、「０」となる。
【００５４】
なお、ここでは、行動履歴データ記憶部１に記憶された行動履歴データから評価値付き履歴データを新たに作成する場合を示したが、この場合に限らず、行動履歴データ記憶部１に記憶された各行動履歴データ中の訪問場所別の滞在時間に対する評価値と求めたら、それを当該行動履歴データとは別個に記憶し、両者を対応付ける（ポインタなどを用いてリンクする）だけでもよい。
【００５５】
次に、特徴行動パターン抽出部５の処理動作について説明する。特徴行動パターン抽出部５は、評価値付き履歴データ記憶部４に記憶された上記履歴データを基に処理を行う。まず、ここでの処理動作の概略を図１０を参照して説明する。
【００５６】
図１０（ａ）は、ある１つの移動体の履歴データを示したものである。ここでは、当該移動体は訪問場所Ｐ１、Ｐ２をこの順序で訪問したときの履歴データである。訪問場所Ｐ１には２つのセグメントが設定され、その一方のセグメントをＴ１、他方のセグメントをＴ２と表している。また、訪問場所Ｐ２には３つのセグメントが設定され、そのうちの１つのセグメントをＴ３、他の１つのセグメントをＴ４、さらに他のセグメントをＴ５と表している。
【００５７】
図１０（ａ）に示し履歴データでは、ある移動体が、訪問場所Ｐ１、Ｐ２をこの順序に訪問し、訪問場所Ｐ１における滞在時間のセグメントＴ１に対する評価値は「１」、セグメントＴ２に対する評価値は「０」であり、訪問場所Ｐ２におけるセグメントＴ３に対する評価値は「０」、セグメントＴ４に対する評価値は「１」、セグメントＴ５に対する評価値は「０」であることを表している。また、場所Ｐ１とＰ２との間の経路は１つで両方向通行可能であり、同じ場所を繰返し訪問することは不可能であるという制約データが与えられているとする。
【００５８】
まず、訪問場所が１つである（シーケンス長が「１」である）特徴行動パターンを抽出する場合を考える。
【００５９】
特徴行動パターン抽出部５は、評価値付き履歴データ記憶部４に記憶されている履歴データに含まれている訪問場所とセグメントとから、訪問場所とセグメントとの組み合わせを全てを求める。この組合せを行動パターンと呼ぶ。例えば、図１０（ａ）に示した履歴データからは、５つの行動パターン（Ｐ１、Ｔ１）、（Ｐ１、Ｔ２）、（Ｐ２、Ｔ３）（Ｐ２、Ｔ４）（Ｐ２、Ｔ５）が生成される。この行動パターンの集合をＡ１と呼ぶ。
【００６０】
図１０（ａ）に示したような履歴データでは、各訪問場所における滞在時間の評価値が「０」であるようなセグメントは無視し得る。図１０（ａ）に示したような履歴データには、評価値が「１」であるセグメントと訪問場所との組合せである、シーケンス長が「１」の行動パターンとして、（Ｐ１、Ｔ１）、（Ｐ２、Ｔ４）が含まれている。この２つの行動パターンは、集合Ａ１の要素でもある。すなわち、集合Ａ１の要素である（Ｐ１、Ｔ１）、（Ｐ２、Ｔ４）という２つの行動パターンは、図１０（ａ）に示した履歴データに含まれているので、当該履歴データの行動パターン（Ｐ１、Ｔ１）、（Ｐ２、Ｔ４）に対する適合度は「１」である。この適合度の値「１」とは、当該履歴データ中の訪問場所Ｐ１やＰ２における滞在時間のセグメントＴ１やＴ４に対する評価値が「１」であることに起因する。従って、行動パターンの集合Ａ１の要素である行動パターン（Ｐ１、Ｔ１）、（Ｐ２、Ｔ４）の得点に、当該履歴データの適合度を加算する（図１０（ｂ）参照）。
【００６１】
他の全ての移動体についての履歴データについても、上記同様にして、行動パターンの集合Ａ１中のいずれかの行動パターンを含む履歴データの当該行動パターンに対する適合度を、当該行動パターンの得点に加算していく。最終的に得られた行動パターンの集合Ａ１の各要素の得点が、当該要素（行動パターン）の支持度である。そして、行動パターンの集合Ａ１の各要素の支持度と条件設定部３で設定された最小支持度とを比較して、集合Ａ１のなかから、最小支持度以上の支持度をもつ行動パターンを特徴行動パターンとして抽出する。この特徴行動パターンの集合をＢ１とし、ここでは、例えばＢ１＝｛（Ｐ１、Ｔ１）（Ｐ２、Ｔ３）（Ｐ２、Ｔ４）｝が抽出されたとする（図１０（ｃ）参照）。
【００６２】
次に、訪問場所が２つである（シーケンス長が「２」である）特徴行動パターンを抽出する場合を考える。この場合は、特徴行動パターンの集合Ｂ１と上記制約データとから、設定された条件パラメータｃを満たすような、２地点間の行動パターンを生成する。ここでは、場所Ｐ１とＰ２との間の経路は１つで、同じ場所を繰返し訪問することは不可能であるという制約データが与えられているので、特徴行動パターンＢ１の集合Ｂ１の異なる２地点のそれぞれに対応する２つの要素からなる配列であって、条件パラメータｃを満たすような配列を求める。この配列の集合が、ｋ＝２のときの行動パターンの集合Ａ２となる。
【００６３】
図１０（ａ）に示したような履歴データに含まれている、集合Ｂ１の要素からなるシーケンス長が「２」の行動パターン（評価値が「１」であるセグメントと訪問場所との組合せの配列）は、（Ｐ１、Ｔ１）（Ｐ２、Ｔ４）である。従って、上記同様にして、図１０（ａ）に示した履歴データの、集合Ａ１の要素である（Ｐ１、Ｔ１）（Ｐ２、Ｔ４）という行動パターンに対する適合度は「１」である。行動パターンの集合Ａ１の要素である行動パターン（Ｐ１、Ｔ１）（Ｐ２、Ｔ４）の得点に、当該履歴データの適合度を加算する（図１０（ｄ）参照）。
【００６４】
他の全ての移動体についての履歴データについても、上記同様にして、行動パターンの集合Ａ２中のいずれかの行動パターンを含む履歴データの当該行動パターンに対する適合度を、当該行動パターンの得点に加算していく。最終的に得られた行動パターンの集合Ａ２の各要素の得点が、当該要素（行動パターン）の支持度である。そして、行動パターンの集合Ａ２の各要素の支持度と、条件設定部３で設定された最小支持度とを比較して、集合Ａ２のなかから、最小支持度以上の支持度をもつ行動パターンを特徴行動パターンとして抽出する。この特徴行動パターンの集合をＢ２とする。
【００６５】
このようにして、大量の履歴データのなかから抽出された、シーケンス長別の行動履歴パターンは、特徴行動パターン記憶部６に記憶される。
【００６６】
特徴行動パターンは、少なくとも１つの訪問場所とそこでの滞在時間の長さに対応するセグメント（ラベル）、訪問場所が複数あるときには、各訪問場所とセグメント（ラベル）を、その訪問順序に従って並べた（繋げた）データである。セグメント自体、滞在時間を表しているので、特徴行動パターンは、上記行動パターンと同様、行動（１つの訪問場所と１つのセグメントとの組）の種類と、行動した順番を表すデータである。なお、行動の種類は、訪問場所とセグメントとの組で識別することができる。
【００６７】
特徴行動パターン記憶部６における特徴行動パターンの記憶例を図１１に示す。特徴行動パターンは、各特徴行動パターンを識別するためのＩＤ（特徴行動パターンＩＤであって、図１１では、ＦＩＤ２１、ＦＩＤ４１）、シーケンス長などともに、特徴行動パターン記憶部４に格納される。例えば、特徴行動パターンＦＩＤ２１は、Ｐ１にラベルＴＩＭＥＰ１＿３に対応する滞在時間だけ滞在した後、場所Ｐ２にラベルＴＩＭＥＰ２＿４に対応する滞在時間滞在するということを表している。
【００６８】
次に、特徴行動パターン抽出部５の処理動作について、図１２、図１３に示すフローチャートを参照して、より詳細に説明する。
【００６９】
ここでは、シーケンス長ｋの特徴行動パターンの集合Ｂｋを｛ｂｋ１、ｂｋ２、…｝と表す。また、特徴行動パターンになりうる候補の行動パターンであって、シーケンス長ｋの行動パターンの集合Ａｋを｛ａｋ１、ａｋ２、…｝と表す。ここで、生起の順序関係を保持したシーケンス長ｋの特徴行動パターンｂｋｉを＜ｂｉ１、ｂｉ２、・・・、ｂｉｋ＞と表記し、同じく集合Ａｋの要素である行動パターンａｋｊを＜ａｊ１、ａｊ２、・・・、ａｊｋ＞と表記する。
まず、行動パターンのシーケンス長が「１」の特徴行動パターン集合Ｂ１の抽出を行う。シーケンス長ｋの値を「１」とする（ステップＳ１０１）、行動パターンの集合Ａｋの生成方法は、シーケンス長ｋが「１」のとき、「２」のときと「３」以上のときで異なる。
【００７０】
ｋ＝１の場合（ステップＳ１０２）はステップＳ１０３へ進み、ｋ＝２の場合（ステップＳ２０１）はステップＳ２０２へ進み、ｋが３以上の場合はステップＳ２０３へ進み、ステップＳ１０３、ステップＳ２０２、ステップＳ２０３のそれぞれにおいて行動パターンの集合Ａｋを生成する。
【００７１】
ステップＳ１０３では、評価値付き履歴データ記憶部４に記憶されている履歴データを基に、履歴データ中に現れるすべての訪問場所とセグメント（ラベル）から、１つの訪問場所と１つのセグメント（ラベル）とからなる組合せを全て求めて、それをｋ＝１のときの行動パターンの集合Ａ１とする。例えば、訪問場所がＰ１、Ｐ２、Ｐ３の３箇所あり、各訪問場所におけるセグメントのラベルがそれぞれＴＩＭＥＰ１＿１、ＴＩＭＥＰ１＿２、ＴＩＭＥＰ１＿３、ＴＩＭＥＰ２＿１、ＴＩＭＥＰ２＿２、ＴＩＭＥＰ２＿３、ＴＩＭＥＰ２＿４、ＴＩＭＥＰ３＿１、ＴＩＭＥＰ３＿２であった場合、特徴行動パターン候補集合Ａ１の要素は、Ｐ１〜Ｐ３と上記各ラベルとからなる組合せであって、（Ｐ１、ＴＩＭＥＰ１＿１）、（Ｐ１、ＴＩＭＥＰ１＿２）、（Ｐ１、ＴＩＭＥＰ１＿３）、（Ｐ２、ＴＩＭＥＰ２＿１）、（Ｐ２、ＴＩＭＥＰ２＿２）、（Ｐ２、ＴＩＭＥＰ２＿３）、（Ｐ２、ＴＩＭＥＰ２＿４）、（Ｐ３、ＴＩＭＥＰ３＿１）、（Ｐ３、ＴＩＭＥＰ３＿２）といった全部で９種類の行動パターンである。
【００７２】
次に、ステップＳ１０４へ進み、行動パターンの集合Ａｋが空集合でないときはステップＳ１０５へ進み、空集合のときは、この時点で処理が終了する。
【００７３】
ステップＳ１０５以下の処理は、行動パターンの集合Ａｋの要素のなかから、上記最小支持度以上（あるいは最小支持度を超える）支持度をもつ行動パターンを選択して、それらを要素とする特徴行動パターンの集合Ｂｋを生成するための処理である。
【００７４】
まず、集合Ａｋの要素のなかから処理対象の行動パターンを１つ取り出す（ステップＳ１０５）。ｋ＝１の場合には、集合Ａ１の要素のなかから処理対象の行動パターンを１つ取り出す。そして、評価値付き履歴データ記憶部４に記憶された全ての移動体の履歴データをサーチして、それらのなかに、条件パラメータｃで指定された条件を満たす処理対称の行動パターンをもつ履歴データがあれば、それを抽出する（ステップＳ１０６）。なお、条件パラメータｃが、連続する訪問場所間に許容される他の訪問場所の数を表す場合には、ｋ＝１のときには、条件パラメータｃは利用されない。
【００７５】
処理対象の行動パターンを含む履歴データのそれぞれについて、当該履歴データから抽出された行動パターン中の各訪問場所のセグメントに対応する評価値から、図１０を参照して説明したようにして、当該履歴データの処理対象の行動パターンに対する適合度を求める（ステップＳ１０７）。そして、処理対象の行動パターンの得点（ここでは、これをＳＵＭと表す）に、当該適合度を加算する（ステップＳ１０８）。
【００７６】
行動パターンの集合Ａｋの各要素を処理対象として、上記ステップＳ１０５〜ステップＳ１０８の処理を行う。当該処理対象の行動パターンを含む履歴データが多ければ多いほど当該処理対称の行動パターンの得点が高くなる。当該処理対象の行動パターンを含む履歴データの適合度の総和が、当該処理対象の支持度である（ステップＳ１０９）。
【００７７】
行動パターンの集合Ａｋの全ての要素について求められた支持度と、条件設定部３で設定された最小支持度とを比較して、集合Ａｋのなかから、最小支持度以上の支持度をもつ行動パターンを特徴行動パターンとして選択する。この特徴行動パターンの集合をＢｋとする（ステップＳ１１０）。特徴行動パターンの集合Ｂｋは、特徴行動パターン総数、当該集合Ｂｋの各要素である１つあるいは複数の特徴行動パターンのレコードで構成され、特徴行動パターンのレコードは、図１１に示したように、特徴行動パターンＩＤ、支持度の他、訪問場所とセグメント（ラベルで表されている）の組を時系列に並べらて構成されている。
【００７８】
特徴行動パターンの集合Ｂｋが空集合であるときには（ステップＳ１１１）、ここで、処理を終了し、空集合でないときには、シーケンス長ｋの特徴行動パターンの集合Ｂｋを特徴行動パターン記憶部６に記憶し（ステップＳ１１２）、ｋを１つインクリメントして（ステップＳ１１３）、ステップＳ１０２へ戻る。
【００７９】
次に、ｋ＝２の場合について説明する。ｋ＝２の場合（ステップＳ２０１）は、ステップＳ２０２へ進み、行動特徴パターン記憶部６に記憶した特徴行動パターンの集合Ｂ１と制約データ記憶部７に記憶された制約データと条件パラメータｃとから、２地点間の行動パターンを生成する。ここで生成される行動パターンの集合をＡ２と表す。
【００８０】
具体的には、例えば、特徴行動パターンの集合Ｂ１の各要素で配列を作成しながら、その配列が制約データと条件パラメータｃとを満たすものであるかをチェックしながら、行動パターンの集合Ａ２の要素を生成する。すなわち、特徴行動パターンの集合Ｂ１の要素（訪問場所とセグメント（ラベルで表されている）との組合せを１つの要素とする）のうち、上記制約データを満たす移動可能な経路のある２地点（２つの訪問場所）を表す２つの要素からなる配列であって、当該２地点間を結ぶ経路上で経由する場所の数が条件パラメータｃで表されている数以内（あるいは未満）であるような配列を求める。このようにして求めた配列を要素とする集合が、行動パターンの集合Ａ２となる。
【００８１】
あるいは、特徴行動パターンの集合Ｂ１の全要素（訪問場所とセグメント（ラベルで表されている）との組合せを１つの要素とする）から、２つの要素からなる全配列を求め、その中から、上記制約データを用いて、２地点間を行き来するための経路がある配列のみを選択する。さらに、選択された配列の２地点間を結ぶ経路上で経由する場所の数が条件パラメータｃで表されている数以内（あるいは未満）であるような配列を、当該選択された配列のなかから選択する。このようにして選択された配列を要素とする集合が、行動パターンの集合Ａ２となる。
【００８２】
２地点間（２訪問場所間）に、条件パラメータｃで表されている数以内の訪問場所数を経由する経路があるかを検索するには、次式（１）を用いる。図５の制約データで表されている２訪問場所間を直接結ぶ道数の部分を行列式として抜き出す。この行列をＭ０と表す。制約パラメータｃの値と次式（１）とから、訪問場所数ｃ以下を経由するリンク数を表す行列Ｍｃは、以下の式で定義され、その出力を新たな制約データとする。
【００８３】
【数１】
2005056022.tif 000003
【００８４】
この新たな制約データにおいて、２訪問場所間を直接結ぶ経路数が「０」の場合は、経路が存在しない、「０」以外の場合は経路が存在すると判断する。
【００８５】
例えば、特徴行動パターンの集合Ｂ１が（Ｐ１、ＴＩＭＥＰ１＿１）、（Ｐ２、ＴＩＭＥＰ２＿１）、（Ｐ２、ＴＩＭＥＰ２＿３）、（Ｐ３、ＴＩＭＥＰ３＿２）の４種類であり、制約パラメータｃが「０」、３訪問場所間の地理関係が図４で与えられたとき、作成される行動パターンの集合Ａ２に含まれる行動パターンは、＜（Ｐ１、ＴＩＭＥＰ１＿１）、（Ｐ２、ＴＩＭＥＰ２＿１）＞、＜（Ｐ１、ＴＩＭＥＰ１＿１）、（Ｐ２、ＴＩＭＥＰ２＿３）＞、＜（Ｐ２、ＴＩＭＥＰ２＿１）、（Ｐ１、ＴＩＭＥＰ１＿１）＞、＜（Ｐ２、ＴＩＭＥＰ２＿１）、（Ｐ３、ＴＩＭＥＰ３＿２）＞、＜（Ｐ２、ＴＩＭＥＰ２＿３）、（Ｐ１、ＴＩＭＥＰ１＿１）＞、＜（Ｐ２、ＴＩＭＥＰ２＿３）、（Ｐ３、ＴＩＭＥＰ３＿２）＞、＜（Ｐ３、ＴＩＭＥＰ３＿２）、（Ｐ２、ＴＩＭＥＰ２＿１）＞、＜（Ｐ３、ＴＩＭＥＰ３＿２）、（Ｐ２、ＴＩＭＥＰ２＿３）＞、の８種類である。
【００８６】
以上のようにして、行動パターンの集合Ａ２を求めた後、ステップＳ１０４へ進み、上述同様にして、ステップＳ１０４以下の処理を行う。
【００８７】
次に、ｋが３以上の場合について説明する。ｋが３以上の場合（ステップＳ２０１）、ステップＳ２０３へ進み、行動特徴パターン記憶部６に記憶したシーケンス長がｋ−１のときの特徴行動パターンの集合Ｂｋ−１から、ｋ個の訪問場所を訪問する行動パターンを生成する。ここで生成される行動パターンの集合をＡｋと表す。
【００８８】
特徴行動パターンの集合Ｂｋ−１の各要素の特徴行動パターンは、１番目からｋ−１番目のｋ−１個の訪問場所とセグメント（ラベルで表されていてもよい）との組合せ（行動）を訪問順に並べたものである。そこで、集合Ｂｋ−１の要素のうちの１つである特徴行動パターン（第１の行動パターン）の１番目（最初の行動）からｋ−２番目までの行動と、集合Ｂｋ−１の要素のうちの他の１つである特徴行動パターン（第２の行動パターン）の２番目からｋ−１番目（最後の行動）までの行動とが全く同じであるとき、このような第１および第２の行動パターンを合成してｋ個の訪問場所を訪問する行動パターンを生成する。すなわち、第２の行動パターンの１番目の行動と、第１および第２の行動パターンで一致する部分（第１の行動パターンの１番目からｋ−２番目までの行動と、第２の行動パターンの２番目からｋ−１番目までの行動）と、第１の行動パターンのｋ−１番目の行動（最後の行動）をこの順で並べて、シーケンス長がｋの行動パターンを生成する。
【００８９】
第１の行動パターンｂｘｋ−１をｋ−１個の行動の配列で、＜ｂｘ１、ｂｘ２、・・・、ｂｘｋ−２、ｂｘｋ−１＞と表し、第２の行動パターンをｂｙｋ−１をｋ−１個の行動の配列で、＜ｂｙ１、ｂｙ２、・・・、ｂｙｋ−２、ｂｙｋ−１＞と表すと、＜ｂｘ１、ｂｘ２、・・・、ｂｘｋ−２＞と＜ｂｙ２、・・・、ｂｙｋ−２、ｂｙｋ−１＞が等しい場合には、＜ｂｙ１、ｂｘ１、ｂｘ２、・・・ｂｘｋ−１＞を生成し、これをシーケンス長ｋの行動パターンの集合Ａｋの要素である行動パターンとする。
【００９０】
例えば、シーケンス長ｋ＝３のとき、シーケンス長２の特徴行動パターンの集合Ｂ２が｛＜（Ｐ１、ＴＩＭＥＰ１＿１）、（Ｐ２、ＴＩＭＥＰ２＿１）＞、＜（Ｐ２、ＴＩＭＥＰ２＿３）、（Ｐ１、ＴＩＭＥＰ１＿１）＞、＜（Ｐ２、ＴＩＭＥＰ２＿３）、（Ｐ３、ＴＩＭＥＰ３＿２）＞、＜（Ｐ３、ＴＩＭＥＰ３＿２）、（Ｐ２、ＴＩＭＥＰ２＿３）＞｝であるとき（４種類の特徴行動パターンで構成されるとき）、＜（Ｐ２、ＴＩＭＥＰ２＿３）、（Ｐ１、ＴＩＭＥＰ１＿１）、（Ｐ２、ＴＩＭＥＰ２＿１）＞と、＜（Ｐ２、ＴＩＭＥＰ２＿３）、（Ｐ３、ＴＩＭＥＰ３＿２）、（Ｐ２、ＴＩＭＥＰ２＿３）＞と、＜（Ｐ３、ＴＩＭＥＰ３＿２）、（Ｐ２、ＴＩＭＥＰ２＿３）、（Ｐ１、ＴＩＭＥＰ１＿１）＞と、＜（Ｐ３、ＴＩＭＥＰ３＿２）、（Ｐ２、ＴＩＭＥＰ２＿３）、（Ｐ３、ＴＩＭＥＰ３＿２）＞の４種類の行動パターンからなるｋ＝３の行動パターンの集合Ａ３が作成される。
【００９１】
以上のようにして、行動パターンの集合Ａ３を求めた後、ステップＳ１０４へ進み、上述同様にして、ステップＳ１０４以下の処理を行う。
【００９２】
以上説明したように、上記第１の実施形態によれば、訪問場所間の地理的な連結関係（経路の有無、経路の数）や、条件パラメータｃを反映させて、各訪問場所での滞在時間の違いを取り扱いながら、大量の行動履歴のなかから、１つまたは複数の訪問場所への訪問順序と訪問した各場所における滞在時間とを表す特徴行動パターンを抽出できる。
【００９３】
（第２の実施形態）
次に、第２の実施形態について説明する。第２の実施形態にかかるデータマイニング装置は、図１と同様であり、ここでは、第１の実施形態と異なる部分について説明する。すなわち、第２の実施形態では、セグメントをメンバシップ関数で表現し、各履歴データ中の滞在時間のセグメントに対する評価値をファジィ集合で表現する場合について説明する。第１の実施形態と異なる点は、主に、滞在時間評価部２におけるセグメントの境界を定める手法である。従って、履歴データの各セグメントに対する評価値が「１」か「０」か（セグメントに属するか属さないかの２値）で表されるものではなく、各セグメントに属する度合いで表されることになる。その結果、特徴行動パターン抽出部５で特徴行動パターンを抽出する際に、行動パターンの集合Ａｋの各要素に対する各履歴データの適合度を求める処理も一部異なる。
【００９４】
まず、滞在時間評価部２の処理動作について、図８、図１４に示すフローチャートを参照して説明する。
【００９５】
第１の実施形態と同様、図８のステップＳ１〜ステップＳ２の処理で、各訪問場所について、行動履歴データに記録されている各訪問場所における滞在時間別に当該訪問場所を訪問した移動体の数を計数して、図１５（ａ）に示すような滞在時間を横軸上にとり、各滞在時間上に、当該滞在時間の間当該訪問場所に滞在した移動体の総数を表すヒストグラムを生成する。このヒストグラムは、表示部８から所定のディスプレイに表示される。ユーザはそのヒストグラムを見て、入力部９から、図１５（ａ）に示すように、分割点ＴＡ１、ＴＡ２を指定する。
【００９６】
次に、図１４のステップＳ３´へ進み、指定された分割点と予め定められた定義に基づいて滞在時間を分割するメンバシップ関数を作成する。例えば、台形型のメンバシップ関数が定義されているとき、図１５（ａ）においてユーザが指定したＴＡ１、ＴＡ２から、図１５（ｂ）に示すように、メンバシップ関数のパラメータがＴａ１、Ｔａ２、Ｔａ３、Ｔａ４が生成される。
【００９７】
図１６に示すような台形型のメンバシップ関数を用いて訪問場所Ｐ１の滞在時間をＴＩＭＥＰ１＿１、ＴＩＭＥＰ１＿２、ＴＩＭＥＰ１＿３という３つのラベルで表される３つのセグメントに分割する場合、メンバシップ関数のパラメータはＴＰ１＿１、ＴＰ１＿２、ＴＰ１＿３、ＴＰ１＿４の４箇所であり、その結果、次式（２）〜（４）に示すようなメンバシップ関数が作成される。
【００９８】
【数２】
2005056022.tif 000004
【００９９】
式（２）〜（４）、図１５（ｂ）に示すように、メンバシップ関数により、各セメントの境界に曖昧性を持たせることができる。
【０１００】
各訪問場所において、滞在時間の複数のセグメントと各セグメントを定めるメンバシップ関数を求めて、それを図１７や図１８に示したようなテーブル形式で記憶する（ステップＳ４´）。なお、図１７や図１８に示したテーブルは、ここでは、例えば、滞在時間評価部２内部に記憶するものとする。
【０１０１】
図１７に示すテーブルにより、各訪問場所における、セグメントの数（ラベルの数）とセグメントのラベルとが記憶されている。また、図１８に示すテーブルにより、各訪問場所について、ステップＳ３´でメンバーシップ関数を求める際に用いたパラメータの数とパラメータが記憶されている。
【０１０２】
なお、メンバシップ関数には、シグモイド関数やシグモイドロジスティック関数を用いてもよい。また、そのとき必要なパラメータはメンバシップ関数によって異なる。
【０１０３】
各訪問場所について、そこでの移動体の滞在時間の分布状況に応じて複数のセグメントがメンバシップ関数で設定されると、次に、図８のステップＳ５へ進み、次に、行動履歴データ記憶部１に記憶された各行動履歴データ中の各訪問場所における滞在時間について、当該滞在時間の、当該訪問場所に設定された複数のセグメントのそれぞれに対応する適合性を表す評価値を求める。
【０１０４】
例えば、図２に示した行動履歴データにおいて、移動体ＰＩＤ０１の最初の訪問場所Ｐ１での滞在時間Ｓ＿ＴＩＭＥ１１が０．５時間（３０分）であるとする。訪問場所Ｐ１では、図１９に示すように、式（２）〜（４）に示すようなメンバシップ関数にてセグメントが定められている場合（ここでは、例えば、ＴＰ＿１＝０．２５、ＴＰ＿２＝０．７５、ＴＰ＿３＝１．０、ＴＰ＿４＝１．５とする）、当該行動履歴データ中のある訪問場所における滞在時間が０．５時間であるとき、当該滞在時間のセグメント「ＴＩＭＰ１＿１」に対する評価値は、式（２）から、０．５となり、セグメント「ＴＩＭＰ１＿２」に対する評価値は、式（２）から、０．５となり、セグメント「ＴＩＭＰ１＿３」に対する評価値は、式（２）から、０．０となる。従って、訪問場所Ｐ１における滞在時間０．５時間のセグメント「ＴＩＭＰ１＿１」、「ＴＩＭＰ１＿２」、「ＴＩＭＰ１＿３」のそれぞれに対する適合性を表す評価値は、それぞれ「０．５」、「０．５」、「０」となる。
【０１０５】
このようにして、訪問場所別の滞在時間に対し評価値を求める処理を、行動履歴データ記憶部１に記憶された全ての行動履歴データの全てについて行う。そして、このような訪問場所別の滞在時間に対する評価値を行動履歴データに付加して、第１の実施形態と同様、図３に示したような履歴データが生成され、評価値付き履歴データ記憶部４に記憶される。
【０１０６】
次に、特徴行動パターン抽出部５の処理動作について説明する。特徴行動パターン抽出部５の処理動作は、図１２、図１３に示したフローチャートとほぼ同様であるが、この第２の実施形態では、図１３のステップＳ１０７において、履歴データの行動パターンの集合Ａ２の要素（行動パターン）に対する適合度を求める手法が第１の実施形態と異なる。それ以外は、第１の実施形態と同様である。すなわち、特徴行動パターン抽出部５は、評価値付き履歴データ記憶部４に記憶された上記履歴データを基に処理を行う。まず、ここでの処理動作の概略を図２０を参照して説明する。
【０１０７】
図２０（ａ）は、ある１つの移動体の履歴データを示したものである。ここでは、当該移動体は訪問場所Ｐ１、Ｐ２をこの順序で訪問したときの履歴データである。訪問場所Ｐ１には２つのセグメントが設定され、その一方のセグメントをＴ１、他方のセグメントをＴ２と表している。また、訪問場所Ｐ２には３つのセグメントが設定され、そのうちの１つのセグメントをＴ３、他の１つのセグメントをＴ４、さらに他のセグメントをＴ５と表している。
【０１０８】
図２０（ａ）に示し履歴データでは、ある移動体が、訪問場所Ｐ１、Ｐ２をこの順序に訪問し、訪問場所Ｐ１における滞在時間のセグメントＴ１に対する評価値は「０．５」、セグメントＴ２に対する評価値は「０．５」であり、訪問場所Ｐ２におけるセグメントＴ３に対する評価値は「０．３」、セグメントＴ４に対する評価値は「０．７」、セグメントＴ５に対する評価値は「０」であることを表している。また、場所Ｐ１とＰ２との間の経路は１つで、同じ場所を繰返し訪問することは不可能であるという制約データが与えられているとする。
【０１０９】
まず、訪問場所が１つである（シーケンス長が「１」である）特徴行動パターンを抽出する場合を考える。
【０１１０】
特徴行動パターン抽出部５は、評価値付き履歴データ記憶部４に記憶されている履歴データに含まれている訪問場所とセグメントとから、訪問場所とセグメントとの組み合わせ（行動パターン）を全てを求める。例えば、図２０（ａ）に示した履歴データからは、５つの行動パターン（Ｐ１、Ｔ１）、（Ｐ１、Ｔ２）、（Ｐ２、Ｔ３）（Ｐ２、Ｔ４）（Ｐ２、Ｔ５）を要素とする。行動パターンの集合Ａ１が生成される。
【０１１１】
図２０（ａ）に示したような履歴データでは、シーケンス長が「１」の行動パターンとして、（Ｐ１、Ｔ１）、（Ｐ１、Ｔ２）、（Ｐ２、Ｔ３）、（Ｐ２、Ｔ４）（Ｐ２、Ｔ５）が含まれている。これら５つの行動パターンは、集合Ａ１の要素でもある。この場合、図１３のステップＳ１０７では、当該履歴データの集合Ａ１中の上記４つの行動パターンのそれぞれに対する適合度を次のようにして求める。
【０１１２】
当該履歴データの行動パターン（Ｐ１、Ｔ１）のセグメントＴ１に対する評価値は「０．５」であるので、集合Ａ１の要素である（Ｐ１、Ｔ１）に対する当該履歴データの適合度は、当該評価値をそのまま用いて「０．５」とする。当該履歴データの行動パターン（Ｐ１、Ｔ２）のセグメントＴ２に対する評価値は「０．５」であるので、集合Ａ１の要素である（Ｐ１、Ｔ２）に対する当該履歴データの適合度は、当該評価値をそのまま用いて「０．５」とする。当該履歴データの行動パターン（Ｐ２、Ｔ３）のセグメントＴ３に対する評価値は「０．３」であるので、集合Ａ１の要素である（Ｐ２、Ｔ３）に対する当該履歴データの適合度は、当該評価値をそのまま用いて「０．３」とする。当該履歴データの行動パターン（Ｐ２、Ｔ４）のセグメントＴ４に対する評価値は「０．７」であるので、集合Ａ１の要素である（Ｐ２、Ｔ４）に対する当該履歴データの適合度は、当該評価値をそのまま用いて「０．７」とする。当該履歴データの行動パターン（Ｐ２、Ｔ５）のセグメントＴ５に対する評価値は「０．０」であるので、集合Ａ１の要素である（Ｐ２、Ｔ５）に対する当該履歴データの適合度は、当該評価値をそのまま用いて「０．０」とする。
【０１１３】
従って、行動パターンの集合Ａ１の要素である行動パターンの得点に、上記のようにして求めた当該履歴データの適合度をそれぞれ加算する（図２０（ｂ）参照）。
【０１１４】
他の全ての移動体についての履歴データについても、上記同様にして、行動パターンの集合Ａ１中のいずれかの行動パターンを含む履歴データの当該行動パターンに対する適合度を、当該行動パターンの得点に加算していく。最終的に得られた行動パターンの集合Ａ１の各要素の得点が、当該要素（行動パターン）の支持度である。そして、第１の実施形態と同様、行動パターンの集合Ａ１の各要素の支持度と条件設定部３で設定された最小支持度とを比較して、集合Ａ１のなかから、最小支持度以上の支持度をもつ行動パターンを特徴行動パターンとして抽出する。この特徴行動パターンの集合をＢ１とし、ここでは、例えばＢ１＝｛（Ｐ１、Ｔ１）、（Ｐ２、Ｔ３）、（Ｐ２、Ｔ４）｝であるとする（図２０（ｃ）参照）。
【０１１５】
次に、訪問場所が２つである（シーケンス長が「２」である）特徴行動パターンを抽出する場合を考える。この場合は、特徴行動パターンの集合Ｂ１と上記制約データとから、設定された条件パラメータｃを満たすような、２地点間の行動パターンを生成する。ここでは、場所Ｐ１とＰ２との間の経路は１つで両方向通行可能であり、同じ場所を繰返し訪問することは不可能であるという制約データが与えられているので、特徴行動パターンの集合Ｂ１の異なる２地点のそれぞれに対応する２つの要素からなる配列であって、設定された条件パラメータｃを満たすような配列を求める。この配列の集合が、ｋ＝２のときの行動パターンの集合Ａ２の要素となる。なお、Ａ２の要素は，＜（Ｐ１、Ｔ１）（Ｐ２、Ｔ３）＞、＜（Ｐ１、Ｔ１）（Ｐ２、Ｔ４）＞、＜（Ｐ２、Ｔ３）（Ｐ１、Ｔ１）＞、＜（Ｐ２、Ｔ４）（Ｐ１、Ｔ１）＞である。
【０１１６】
図２０（ａ）に示したような履歴データに含まれている、集合Ｂ１の要素からシーケンス長が「２」の行動パターン（訪問場所とセグメントの組合せの配列）は、＜（Ｐ１、Ｔ１）（Ｐ２、Ｔ３）＞、＜（Ｐ１、Ｔ１）（Ｐ２、Ｔ４）＞である。
【０１１７】
これら２つの行動パターンは、集合Ａ２の要素でもある。この場合、図１３のステップＳ１０７では、当該履歴データの集合Ａ１中の上記２つの行動パターンのそれぞれに対する適合度を次のようにして求める。
【０１１８】
まず、当該履歴データの、集合Ａ２の要素である行動パターン＜（Ｐ１、Ｔ１）、（Ｐ２、Ｔ３）＞に対する適合度は次のようにして求める。すなわち、当該履歴データ中の行動パターン（Ｐ１、Ｔ１）のセグメントＴ１に対する評価値は「０．５」、当該履歴データ中の行動パターン（Ｐ２、Ｔ３）のセグメントＴ３に対する評価値は「０．３」であるので、両者のうち値の低い方の評価値「０．３」を集合Ａ１の要素である行動パターン＜（Ｐ１、Ｔ１）、（Ｐ２、Ｔ３）＞に対する当該履歴データの適合度とする。あるいは、両者を乗算した結果（例えば、この場合、０．５×０．３＝０．１５）を適合値としてもよい（図２０（ｄ）参照）。
【０１１９】
次に、当該履歴データの、集合Ａ２の要素である行動パターン＜（Ｐ１、Ｔ１）、（Ｐ２、Ｔ４）＞に対する適合度は次のようにして求める。すなわち、当該履歴データ中の行動パターン（Ｐ１、Ｔ１）のセグメントＴ１に対する評価値は「０．５」、当該履歴データ中の行動パターン（Ｐ２、Ｔ４）のセグメントＴ４に対する評価値は「０．７」であるので、両者のうち値の低い方の評価値「０．５」を集合Ａ１の要素である行動パターン＜（Ｐ１、Ｔ１）、（Ｐ２、Ｔ４）＞に対する当該履歴データの適合度とする。あるいは、両者を乗算した結果（例えば、この場合、０．５×０．７＝０．３５）を適合値としてもよい（図２０（ｄ）参照）。
【０１２０】
以上のようにして求めた当該履歴データの行動パターンの集合Ａ２の要素である行動パターン＜（Ｐ１、Ｔ１）（Ｐ２、Ｔ３）＞、＜（Ｐ１、Ｔ１）（Ｐ２、Ｔ４）＞のそれぞれに対する適合度を、行動パターンの集合Ａ２の上記各要素の得点に加算する（図２０（ｄ）参照）。
【０１２１】
他の全ての移動体についての履歴データについても、上記同様にして、行動パターンの集合Ａ２中のいずれかの行動パターンを含む履歴データの当該行動パターンに対する適合度を、当該行動パターンの得点に加算していく。最終的に得られた行動パターンの集合Ａ２の各要素の得点が、当該要素（行動パターン）の支持度である。そして、行動パターンの集合Ａ２の各要素の支持度と、条件設定部３で設定された最小支持度とを比較して、集合Ａ２のなかから、最小支持度以上の支持度をもつ行動パターンを特徴行動パターンとして抽出する。この特徴行動パターンの集合をＢ２とする。
【０１２２】
このようにして、大量の履歴データのなかから抽出された、シーケンス長別の行動履歴パターンは、特徴行動パターン記憶部６に記憶される。
【０１２３】
第２の実施形態における、図１３のステップＳ１０７の処理動作を図２１に示すフローチャートを参照して説明する。
【０１２４】
ｋ＝１の場合には（ステップＳ１０７ａ）、図１２のステップＳ１０３において、１つの行動（１つの訪問場所と１つのセグメントで表現されているもの）からなる行動パターンの集合Ａ１が得られているので、図１３のステップＳ１０７では、行動パターンの集合Ａ１の要素である行動パターンを含む履歴データがあるときは、当該行動パターンを構成する行動に対応する当該履歴データ中の評価値を、そのまま、当該履歴データの当該行動パターンに対する適合度とする（ステップＳ１０７ｂ）。
【０１２５】
また、ｋが２以上の場合には（ステップＳ１０７ａ）、ステップＳ２０２やステップＳ２０３で、複数の行動をその順番に繋げてなる行動パターンの集合Ａｋが得られているので、図１３のステップＳ１０７では、行動パターンの集合Ａｋの要素である行動パターンを含む履歴データがあるときは、当該行動パターンを構成する複数の行動のそれぞれに対応する当該履歴データ中の評価値のうち、値が最も小さい評価値、あるいは、各行動に対応する評価値を乗算した結果を、当該履歴データの当該行動パターンに対する適合度とする（ステップＳ１０７ｃ）。
【０１２６】
このように、ステップＳ１０７ｂ、ステップＳ１０７ｃでは、履歴データの集合Ａｋの要素である行動パターンに対する適合度を算出する。行動パターンは、複数の行動（１つの訪問場所と１つのセグメントで表現されているもの）を行動の順番に繋げて表したものであるから、ある移動体の履歴データに含まれる行動パターンを、複数の行動ｘａ１、…、ｘａｋをこの順番に繋げて、Ｘａ＝＜ｘａ１、…、ｘａｋ＞と表し、その各行動の評価値をＸｃ＝＜ｘｃ１、・・・、ｘｃｋ＞と表わすとき、当該履歴データの当該行動パターンに対する適合度ｘｃは次式（５）あるいは（６）で計算することができる。
【０１２７】
【数３】
2005056022.tif 000005
【０１２８】
図１３のステップＳ１０８で説明したように、行動パターンの集合Ａｋの各要素（行動パターン）に対応する得点に、上記のようにして求めた適合度を加算していき、最終的に得られた各行動パターンの得点が当該行動パターンの支持度である。その後の処理は、第１の実施形態と同様である。
【０１２９】
以上説明したように、上記第２の実施形態によれば、滞在時間を分類するためのセグメントがメンバシップ関数で定められるので、セグメントの間の境界に曖昧性を持たせることができる。
【０１３０】
第１の実施形態では、セグメント間の境界がある１つの時点で区切られていたため、例えば滞在時間３０分未満を短期滞在のセグメント、３０分以上を長期滞在のセグメントと定めた場合には、行動履歴データ中の滞在時間が３０分と２９分とでは１分しか違いがないにもかかわらず、短期滞在と長期滞在のいずれかに分類されてしまうという問題点があった。しかし、第２の実施形態によれば、セグメント間の境界に曖昧性を持たせることで、行動履歴データ中の各行動に対する評価値（各訪問場所における滞在時間の各セグメントに対する評価値）をより現実に即して求めることができる。その結果、履歴データの、行動パターンの集合Ａｋの要素に対する適合度や、さらに、行動パターンの集合Ａｋの要素である行動パターンの支持度がより高精度に求めることができ、信頼性の高い特徴行動パターンの抽出が可能となる。
【０１３１】
なお、上記第１および第２の実施形態において、特徴行動パターン抽出部５で抽出された特徴行動パターンは、表示部８からユーザに提示される。抽出された全ての特徴行動パターンを表示する。あるいは、抽出された特徴行動パターンのうち、ユーザにより指定された、あるいは予め定められた条件（例えば、訪問場所や滞在時間や支持度などを指定するもの）を満たす特徴行動パターンのみを表示する。例えば、抽出された特徴行動パターンのうち、条件として指定されたある訪問場所を含む特徴行動パターンや、支持度が所定値以上の特徴行動パターンのみを表示する。
【０１３２】
また、ユーザに呈示するのは、特徴行動パターンだけでなく、特徴行動パターンの支持度や、当該特徴行動パターンを抽出する際に用いた行動パターンの集合Ａｋや、その要素である各行動パターンの支持度など、途中経過も表示するようにしてもよい。
【０１３３】
さらに、表示部８は、条件パラメータｃや最小支持度の値に応じて異なる抽出結果をユーザが容易に比較可能なように、それらを並べて表示する。例えば、図２８に示すようなテーブル形式で、条件パラメータの異なる複数の値のそれぞれに対応する抽出結果を表示する。
【０１３４】
（第３の実施形態）
第３の実施形態として、上記第１、第２の実施形態で説明したデータマイニング装置の効果を、具体的に説明する。
【０１３５】
本装置の効果の検証を行うため、図２２に示すようなＡ〜Ｐの１６箇所の観光地を廻る歩行者１０００人を想定して、擬似的に行動履歴データを生成する。滞在時間は対数変換し、各訪問場所について３つのセグメントを定め、それぞれについて短、中、長の滞在時間ラベルをつける。
【０１３６】
セグメントを定めるメンバシップ関数は、図２３に示すようなシグモイド関数を用いることとする。この場合、指定された分割点ＴＡ１、ＴＡ２から、このメンバーシップ関数のパラメータＴａ＿１、Ｔａ＿２、Ｔａ＿３、Ｔａ＿４が生成され、その結果、次式（７）〜（９）に示すようなメンバシップ関数が作成される。
【０１３７】
【数４】
2005056022.tif 000006
【０１３８】
ただしｌ１＝５０、ｌ２＝５０とする。
【０１３９】
ここで用いる１０００人の行動履歴データのサンプルには、図２４に示すような行動パターンを含んでいる。また、これら１０００件の行動履歴データについて得られる、観光地別の滞在時間と人数の関係を表すヒストグラムを図２５〜図２７に示す。
【０１４０】
また、条件パラメータｃとしては、「０」、「１」、「２」、「制限無し（無限大）」の４種類を用い、最小支持度を「０．２」とする。
【０１４１】
図２８は、図１のデータマイニング装置により得られた特徴行動パターンを条件パラメータの値別に、支持度の高いものから順に示したものである。
【０１４２】
一方、行動パターンの各行動に滞在時間という概念を含まない、単に訪問場所を訪問した順に並べて行動パターンを表す行動履歴データから特徴行動パターンを抽出する、従来の相関抽出法により抽出された特徴行動パターンを支持度の高いものから順に示したものが図２９のテーブルである。なお、この場合には、行動パターンを構成する各行動は、（滞在時間という属性を持たない）訪問場所である。
【０１４３】
図２８は、抽出されたシーケンス長ｋ＝３の特徴行動パターンのうち、支持度が高いものを順に３つ示している。図２９に示した従来技術による抽出結果と、図２８に示した本実施形態にかかる抽出結果との違いを考察する。従来技術では、行動パターン中の各行動を滞在時間による区別をしていないのに対して、本実施形態にかかる手法では、滞在時間の短、中、長を区別して扱い、抽出される特徴行動パターンにもその結果が反映されている。支持度が上位３つの特徴行動パターンが従来技術による抽出結果とまったく異なるのは、図２５〜図２７に示す滞在時間の分布より訪問場所Ｇ、Ｈ、Ｉ、Ｊの滞在時間が一様だったのに対し、訪問場所Ｂ、Ｃ、ＤやＦ、Ｋ、Ｍでは、滞在時間分布に偏り傾向があったことが反映されたためである。これらのことから本実施形態を用いることで、（Ｂ（長）、Ｃ（短）、Ｄ（短））や（Ｆ（短）、Ｋ（短）、Ｍ（短））といったような滞在時間を加味した特徴行動パターンが抽出できることが確認できる。
【０１４４】
次に、条件パラメータｃについて考察する。条件パラメータｃの値を増加させると得られる特徴行動パターンの種類が増加する。ｃ＝０のときに抽出される特徴行動パターンは、どの訪問場所も経由することなく直接結ばれている（Ｂ（長）、Ｃ（短）、Ｄ（短））のみであるのに対して、ｃ＝１のときに抽出される特徴行動パターンは、１箇所の訪問場所を経由することを許した経路によって結ばれた（Ｆ（短）、Ｋ（短）、Ｍ（短））や（Ｆ（短）、Ｍ（短）、Ｏ（長））まで抽出された。２地点間の経路上で経由可能な訪問場所の数を表す条件パラメータｃにより、現れる特徴パターンの種類を調節することが確認できる。
【０１４５】
図３０は、条件パラメータｃの値が「０」「１」「２」「無限大」のそれぞれにおいて、シーケンス長ｋ（ｋ＝１〜３）のときに生成される行動パターンの集合Ａｋの要素（行動パターン）の数の推移を示したものである。条件パラメータｃの値が小さいときほど、集合Ａｋの要素の数が予め絞り込まれていることが確認できる。この事から、条件パラメータｃの値を小さく設定することで、計算量が軽減されることが確認できる。
【０１４６】
（バリエーション）
（１）上記第１および第２の実施形態では、訪問場所間の地理的な連結関係を制約データとして用いているが、この場合に限らない。例えば、訪問場所Ａと訪問場所Ｂにおいて同時間帯に、異なるセミナーが開催されている場合、この時間帯では、いずれか一方のセミナーしか参加することができないことがある。このような場合には、この時間帯では、訪問場所Ａから訪問場所Ｂへの移動は不可能であるから、そのような行動パターンを集合Ａｋの要素として作成しても無意味となる可能性がある。そこで、訪問場所間に時間的な制約を与えるようにしてもよい。例えば、図１２のステップＳ２０２やステップＳ２０３などで、行動パターンの集合Ａｋを生成の際には、「訪問場所Ａと訪問場所Ｂとを繋げる場合に、訪問場所Ａにおける滞在時間がある一定時間以上でないと、訪問場所Ｂを繋げることはできない」といったような内容のデータを制約データとして用いてもよい。
【０１４７】
このような時間的な制約を与えることで、より現実に即した行動パターンが生成することができるとともに、行動パターンの集合Ａｋの要素数を絞り込むことができる。従って、処理時間の短縮が図れる。
【０１４８】
（２）上記第１および第２の実施形態では、訪問場所にその属性として滞在時間を対応付けたものを１つの行動として表し、１つまたは複数の行動を繋げることで行動パターンを表している。訪問場所に対応付ける属性としては、滞在時間の他に、例えば当該訪問場所を訪問する組織、訪問者の数や人間関係などがであってもよい。また、滞在時間、組織、訪問者の数、人間関係などの属性を複数個組合せて訪問場所に対応つけて１つの行動を表現してもよい。この場合も、上記実施形態の手法は容易に適用可能である。
【０１４９】
（３）特徴行動パターンを抽出するときの評価指標として、支持度のかわりに相関係数などの統計的な指標を用いて全行動履歴データから抽出する特徴行動パターンを決定してもよい。
【０１５０】
（４）活動空間は、実空間だけではなくサイバースペースであってもよい。例えば、ネットワークで接続された複数のサイトで構成されるサイバースペースがある場合に、複数のユーザのそれぞれについての行動履歴データ（訪問したサイトとそこでの滞在時間と訪問順序とを記録したもの）から特徴行動パターンを抽出する。
【０１５１】
（５）訪問場所は、地理的な場所に限らず、イベント、Ｗｅｂページ、人、組織、場所の位置を示すものであってもよい。
【０１５２】
（６）行動履歴データは、実際にその場で移動体の行動を観測しなくても、オンラインによってデータを収集してもよい。
【０１５３】
（７）上記第１および第２の実施形態では、訪問場所別のセグメントを設定する際にはヒストグラムを作成したが、この場合に限らず、散布図や折れ線グラフなどの他のグラフを用いて、訪問場所別の滞在時間と行動履歴データの分布を表すようにしてもよい。この場合においても、上記実施形態の手法は容易に適用可能である。
【０１５４】
以上説明したように、上記第１〜第３の実施形態によれば、ある活動空間内の大量の行動履歴データから共通する行動パターンを効率的に抽出可能となり、移動体の活動空間利用の特徴を的確に知ることができる。
【０１５５】
本発明の実施の形態に記載した本発明の手法（滞在時間評価部２や特徴行動パターン抽出部５などのの処理動作）は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、半導体メモリなどの記録媒体に格納して頒布することもできる。
【０１５６】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【０１５７】
【発明の効果】
以上説明したように、本発明によれば、大量の移動体の行動履歴から、移動体が訪問する訪問場所と訪問順序と、各訪問場所における滞在時間とで表された、多くの移動体に共通する行動パターンを容易に抽出することができる。
【図面の簡単な説明】
【図１】本発明の第１〜第３の実施形態にかかるデータマイニング装置の構成例を示した図。
【図２】行動履歴データ記憶部に記憶された、行動履歴データのデータ構造を示した図。
【図３】評価値付き履歴データ記憶部に記憶された、評価値付き履歴データのデータ構造を示した図。
【図４】制約データにて表されている、訪問場所間の地理的な連結関係を模式的に示した図。
【図５】制約データ記憶部に記憶されている制約データの記憶例を示した図。
【図６】図４の訪問場所間の地理的な連結関係を表す制約データの具体例を示した図。
【図７】同じ訪問場所を繰返し訪問することが可能な訪問場所間の地理的な連結関係を模式的に示した図。
【図８】滞在時間評価部の処理動作を説明するためのフローチャート。
【図９】滞在時間を横軸上にとり、各滞在時間上に、当該滞在時間の間当該訪問場所に滞在した移動体の総数を表すヒストグラムの具体例を示した図。
【図１０】特徴行動パターン抽出部の処理動作を説明するための図。
【図１１】特徴行動パターン記憶部６に記憶された特徴行動パターンのデータ構造を説明するための図。
【図１２】特徴行動パターン抽出部の処理動作を説明するためのフローチャート。
【図１３】特徴行動パターン抽出部の処理動作を説明するためのフローチャート。
【図１４】本発明の第２の実施形態に係る滞在時間評価部の処理動作を説明するためのフローチャート。
【図１５】メンバーシップ関数の設定方法について説明するための図。
【図１６】メンバーシップ関数を説明するための図。
【図１７】各訪問場所に設定されたセグメントに関するデータの記憶例を示した図。
【図１８】各訪問場所に設定されたメンバーシップ関数に関するデータの記憶例を示した図。
【図１９】行動履歴データの各訪問場所における滞在時間に対する評価値の算出方法を説明するための図。
【図２０】第２の実施形態に係る特徴行動パターン抽出部の処理動作を説明するための図。
【図２１】第２の実施形態に係る特徴行動パターン抽出部の処理動作を説明するためのフローチャート。
【図２２】複数の訪問場所（Ａ〜Ｏ）間の地理的な連結関係を模式的に表した図。
【図２３】第３の実施形態で用いたメンバーシップ関数を示した図。
【図２４】第３の実施形態で用いた行動履歴データに含まれる行動パターンを示した図。
【図２５】行動履歴データから各訪問場所（Ａ〜Ｆ）について生成した滞在時間の対数値と訪問者数の関係を表すヒストグラムを示した図。
【図２６】行動履歴データから各訪問場所（Ｇ〜Ｌ）について生成した滞在時間の対数値と訪問者数の関係を表すヒストグラムを示した図。
【図２７】行動履歴データから各訪問場所（Ｍ〜Ｏ）について生成した滞在時間の対数値と訪問者数の関係を表すヒストグラムを示した図。
【図２８】図１のデータマイニング装置により抽出された特徴行動パターンを示した図。
【図２９】従来技術により抽出された特徴行動パターンを示した図。
【図３０】条件パラメータの値が「０」「１」「２」「無限大」のそれぞれの場合において、シーケンス長ｋ（ｋ＝１〜３）のときに生成される行動パターンの集合Ａｋの要素（行動パターン）の数の推移を示した図。
【符号の説明】
１…行動履歴データ記憶部、２…滞在時間評価部、３…条件設定部、４…評価値付き履歴データ記憶部、５…特徴行動パターン抽出部、６…特徴行動パターン記憶部、７…制約データ記憶部、８…表示部、９…入力部。
【図１】
2005056022.tif 000007
【図２】
2005056022.tif 000008
【図３】
2005056022.tif 000009
【図４】
2005056022.tif 000010
【図５】
2005056022.tif 000011
【図６】
2005056022.tif 000012
【図７】
2005056022.tif 000013
【図８】
2005056022.tif 000014
【図９】
2005056022.tif 000015
【図１０】
2005056022.tif 000016
【図１１】
2005056022.tif 000017
【図１２】
2005056022.tif 000018
【図１３】
2005056022.tif 000019
【図１４】
2005056022.tif 000020
【図１５】
2005056022.tif 000021
【図１６】
2005056022.tif 000022
【図１７】
2005056022.tif 000023
【図１８】
2005056022.tif 000024
【図１９】
2005056022.tif 000025
【図２０】
2005056022.tif 000026
【図２１】
2005056022.tif 000027
【図２２】
2005056022.tif 000028
【図２３】
2005056022.tif 000029
【図２４】
2005056022.tif 000030
【図２５】
2005056022.tif 000031
【図２６】
2005056022.tif 000032
【図２７】
2005056022.tif 000033
【図２８】
2005056022.tif 000034
【図２９】
2005056022.tif 000035
【図３０】
2005056022.tif 000036