(57)【要約】【課題】  時系列に並んだデータから、頻出する部分データ列を抽出（シーケンシャルパターンマイニング）し、それを特徴的なパターンとして推薦に利用する場合、データの流れは同じでも、データの並び順が違っていたり、データ名が異なったりしていると、頻出パターンの検出が困難になり、抽出した頻出パターンは汎用的でないことが多かった。【解決手段】  アイテム操作の時系列データを複数のアイテム操作集合に分割し、アイテム操作集合間の集合類似度を用いて、抽象アイテム操作集合を生成する。抽象アイテム操作集合の順序列から頻出する順序列のパターンを抽出する。頻出する順序列のパターンを用いて、ユーザにアイテムさらにはアイテムの操作を推薦する。【選択図】  図６
2013143039.tif 000002
【特許請求の範囲】
【請求項１】
アイテムの操作履歴データベースからユーザ単位のアイテム操作の時系列データを取得する取得手段と、
前記アイテム操作の時系列データを複数のアイテム操作集合に分割する分割手段と、
前記アイテム操作集合間の集合類似度を計算する集合類似度計算手段と、
前記類似度を用いて前記アイテム操作集合から抽象アイテム操作集合を生成する生成手段と、
前記抽象アイテム操作集合の順序列のうち、頻出する順序列のパターンを抽出する抽出手段と、
を有する頻出パターン抽出装置。
【請求項２】
前記分割手段は、前記アイテム操作の時系列データを固定時間毎に複数のアイテム操作集合に分割することを特徴とする請求項１記載の頻出パターン抽出装置。
【請求項３】
前記分割手段は、前記アイテム操作の時系列データを前記アイテム操作間の時間が一定時間以上の個所で複数のアイテム操作集合に分割することを特徴とする請求項１記載の頻出バターン抽出装置。
【請求項４】
前記アイテム同士のアイテム類似度を計算するアイテム類似度計算手段と、
前記アイテム類似度を用いて、アイテムをクラスタリングするクラスタリング手段と、を更に有し、
前記アイテム操作集合は、前記アイテムが前記クラスタリング手段でクラスタ単位にクラスタリングされている集合であることを特徴とする請求項１記載の頻出パターン抽出装置。
【請求項５】
前記アイテム類似度は、前記アイテム同士のコピー履歴を用いて計算することを特徴とする請求項４記載の頻出パターン抽出装置。
【請求項６】
前記アイテム類似度は、前記アイテムの属性を用いて計算することを特徴とする請求項４記載の頻出パターン抽出装置。
【請求項７】
前記アイテム類似度は、前記アイテムの共起利用情報を利用して計算することを特徴とする請求項４記載の頻出パターン抽出装置。
【請求項８】
前記抽象アイテム操作集合の順序列は、隣接する前記抽象アイテム操作集合に共通の前記アイテムまたは前記クラスタ単位のアイテムを持たない個所で単位が区切られることを特徴とする請求項１記載の頻出パターン抽出装置。
【請求項９】
前記抽出した頻出する順序列のパターンを用いて、ユーザにアイテムを推薦する推薦手段を更に有することを特徴とする請求項１又は４記載の頻出パターン抽出装置。
【請求項１０】
前記推薦手段で、アイテムに加えてアイテムの操作を推薦することを特徴とする請求項９記載の頻出パターン抽出装置。
【請求項１１】
ユーザの直近のアイテム操作の時系列データを分割して得た前記アイテム操作集合と前記集合類似度の高い前記操作履歴データベースから得た抽象アイテム操作集合を判定する類似抽象アイテム操作集合判定手段をさらに有することを特徴とする請求項９記載の頻出パターン抽出装置。
【請求項１２】
ユーザの直近のアイテム操作の時系列データから得た前記抽象アイテム操作集合の順序列があてはまる前記操作履歴データベースから得た頻出する順序列のパターンを推定する推定手段をさらに有することを特徴とする請求項９記載の頻出パターン抽出装置。
【請求項１３】
アイテムの操作履歴データベースからユーザ単位のアイテム操作の時系列データを取得する取得工程と、
前記アイテム操作の時系列データを複数のアイテム操作集合に分割する分割工程と、
前記アイテム操作集合間の集合類似度を計算する集合類似度計算工程と、
前記類似度を用いて前記アイテム操作集合から抽象アイテム操作集合を生成する生成工程と、
前記抽象アイテム操作集合の順序列のうち、頻出する順序列のパターンを抽出する抽出工程と、
を有する頻出パターン抽出方法。
【請求項１４】
コンピュータを、
アイテムの操作履歴データベースからユーザ単位のアイテム操作の時系列データを取得する取得手段と、
前記アイテム操作の時系列データを複数のアイテム操作集合に分割する分割手段と、
前記アイテム操作集合間の集合類似度を計算する集合類似度計算手段と、
前記類似度を用いて前記アイテム操作集合から抽象アイテム操作集合を生成する生成手段と、
前記抽象アイテム操作集合の順序列のうち、頻出する順序列のパターンを抽出する抽出手段と、として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザのアイテム操作履歴を用いて、特徴的な頻出パターンを抽出する方法とそれを用いてユーザにアイテム、さらにはそのアイテムの操作を推薦する方法に関する。
【背景技術】
【０００２】
ユーザが所望のアイテムを検索する手段として、従来からキーワードによるマッチング方式や、分類・階層化されたアイテムの階層を選択して絞り込んでいく方法が使われている。しかし、これら従来の手法はユーザに掛かる負担が大きく、また、ユーザの技量によっては最悪の場合、所望のアイテムが見つけられない可能性もある。そこで、ユーザの手間を軽減し、必要としているアイテムを自動的に検索してユーザへ提示する推薦手法が提案されている。
【０００３】
推薦手法として有名なものに、ＥＣサイトなどで広く普及している協調フィルタリングがある。これは、過去の利用履歴からアイテムの利用傾向が似ている類似ユーザを抽出し、その類似ユーザの利用履歴を用いてお薦めするアイテムを予測するものである。
【０００４】
しかし、オフィスにおいて所望するアイテムは社内文書やＷｅｂ上の文書など、情報を作成するための情報源としての情報だけではない。ある仕事を達成するための手順であったり、効率的に仕事を進める為の方法であったり、何かしらのノウハウとしての情報も探している。こういった情報は経験的に整理されワークフローとして明文化されている場合は良いが、明文化されていない場合、知っていそうな人に聞いたり、推測して試行錯誤したりなどかなりの時間と労力を情報を探すことに費やしてしまう。
【０００５】
そこで時系列に並んだ利用履歴から、頻出する部分データ列を抽出（シーケンシャルパターンマイニング）し、それを特徴的なパターンとして推薦に利用する各種技術が提案されている。例えば、Ｗｅｂのアクセスログを解析し、ページＡを見た後には、ページＦをよく見るなどのパターンを抽出することで、ページＡを見たユーザに対して、次にページＦを見ることを推薦することができる。このようにアイテムを利用する順序が重要なケースにおいて、この種の推薦手法は広く提案されている。
【０００６】
特許文献１では、１つ以上の（主に家電）機器の操作履歴から、頻出操作パターンを抽出し、操作者の推定を行い、操作者に特化したサービスや情報を提供する。操作の時間的まとまりをエレメントと呼び、エレメント間で頻出する操作を頻出操作パターンとして抽出する。
【０００７】
また、利用履歴を使って、今行っている作業と同じ過去の作業を探し、それを用いて推薦する技術が提案されている。特許文献２では、過去に作業に用いた文書とその作業における文書の利用状況や編集内容を作業記録として記憶し、それをユーザへの関連文書推薦に利用する。ユーザの現在の文書への操作内容の類似性から過去の類似作業を抽出し、その作業で利用されていた文書を抽出することで、作業目的にあった精度の高い関連情報を推薦する。過去の類似作業の類推は、文書ＩＤが一致した上で、操作内容の類似性から判断する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特許第３８６０６０２号
【特許文献２】特開２００９−２１１３８５
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従来手法のように、このような推薦を行う基本的な方法は次の通りである。
１．  事前に、利用履歴から特徴的な頻出操作パターンを抽出する
２．  ユーザの直近の操作から現在行っている操作が、どの頻出操作パターンにあてはまるかを推定する
３．  推定した頻出操作パターンを基に、ユーザに次の操作を推薦する
【００１０】
しかし、オフィスにおける文書利用を考えた場合、特徴的な頻出操作パターンを抽出する際に大きな問題がある。一般的に、ワークフローは大まかな文書操作の流れは同じでも、細かく見ると操作の順番が順不同であったり、操作対象の文書名が異なったりすることが多い。そのような場合、頻出するパターンを見つけることが困難になる上に、抽出した操作パターンは汎用的でない可能性が高い。
【００１１】
例えば、見積書を作成するワークフローを考えた場合、二人のユーザＡとユーザＢでは大まかな操作の流れは同じでも、作成する見積書の文書名は異なるし、参考にするために開く文書名も異なる上に、開く順番も異なる可能性が高い。ここでは、ユーザ間の差異について述べたが、同ユーザでもその時々によって微妙に操作内容は異なることも多々あり、全く同じ頻出操作パターンは発見が困難と考えられる。仮に、発見できたとしても、それは特化され過ぎた操作パターンとなる可能性が高く、ユーザの操作に対してワークフローを推定する能力が低くなる。
【課題を解決するための手段】
【００１２】
本発明に係る頻出パターン抽出装置は、以下の構成を備える。即ち、アイテムの操作履歴データベースからユーザ単位のアイテム操作の時系列データを取得する取得手段と、前記アイテム操作の時系列データを複数のアイテム操作集合に分割する分割手段と、前記アイテム操作集合間の集合類似度を計算する集合類似度計算手段と、前記類似度を用いて前記アイテム操作集合から抽象アイテム操作集合を生成する生成手段と、前記抽象アイテム操作集合の順序列のうち、頻出する順序列のパターンを抽出する抽出手段。
【発明の効果】
【００１３】
本発明によれば、文書名や、利用した順番の違いを吸収し、汎用的なワークフローを抽出することができる。このワークフローを用いて、ユーザにアイテム、さらにはアイテム操作を推薦することが可能である。
【図面の簡単な説明】
【００１４】
【図１】実施形態１を実施するシステムの構成例
【図２】実施形態１を実施する装置の構成例
【図３】実施形態１を構成するブロック図の例
【図４】実施形態におけるファイル操作履歴
【図５】実施形態におけるファイル操作ログ
【図６】実施形態におけるワークフロー抽出のフローチャート
【図７】実施形態における仮タスク抽出
【図８】実施形態における仮タスク抽出２
【図９】実施形態におけるファイルコピー関係によるファイル間類似度
【図１０】実施形態２を構成するブロック図の例２
【図１１】実施形態におけるファイルの階層クラスタ
【図１２】実施形態における仮タスクの抽象化
【図１３】実施形態における仮タスク間の類似度計算
【図１４】実施形態におけるタスク生成
【図１５】実施形態におけるファイル操作推薦のフローチャート
【図１６】実施形態における仮ワークフロー抽出
【図１７】実施形態における仮ワークフロー抽出２
【図１８】実施形態におけるワークフロー推定
【図１９】実施形態におけるワークフロー抽出
【図２０】実施形態におけるワークフロー
【図２１】実施形態におけるワークフロー推定のフローチャート
【図２２】実施形態におけるワークフロー推定の仮タスク抽出
【図２３】実施形態におけるワークフロー推定の仮タスク抽象化
【図２４】実施形態におけるワークフロー推定のタスク推定
【発明を実施するための形態】
【００１５】
［実施形態１］
本発明における頻出パターン抽出方法の例を図面に基づいて説明する。本実施形態では、アイテムとして、フォルダ（またはディレクトリ）構造を持つファイルを対象とし、ファイル管理システムの一機能として頻出パターン抽出機能を設ける。なお、本実施形態では、アイテムとして、ファイルを対象としているがそれに限定されない。例えば、デジタルカメラなどの機器や、ＰＣなどのアプリケーションソフトの場合には、その操作メニューや設定項目などをアイテムと見なすことができ、本発明を適用することでその操作のナビゲーションを効果的に行うことが可能となる。
【００１６】
本例でのシステム構成を図１を用いて説明する。ファイル管理システムは、クライアントサーバモデルとして実現される。端末Ａ１０２、端末Ｂ１０３、端末Ｃ１０４、ファイル管理サーバー１０５はネットワーク１０１を介して接続されており、それぞれ相互間で各種情報の授受を実行する。ユーザはそれぞれ端末Ａ１０２、端末Ｂ１０３、端末Ｃ１０４上の専用のクライアントツールを用いて、ファイルの登録、閲覧、削除、印刷、複製などのファイル操作を行う。
【００１７】
図２は、本発明に関する処理を実施する図１の各装置の構成例である。図２において、２０１は制御部であり、ＣＰＵ等で構成される。制御部２０１はバス２０２を介してメモリ部２０３、大規模記憶部２０４、表示部２０５、入力部２０６、出力部２０７、ネットワーク接続部２０８に接続されている。メモリ部２０３はＲＡＭ等で構成される電子的な記憶装置である。制御部２０１はこのメモリ部２０３に配置されたプログラムおよびデータに従って動作するとともに、接続された各部を制御し、データの入出力をおこなう。大規模記憶部２０４は、ハードディスク、光学ディスク等のデータ蓄積装置である。表示部２０５は、本システムを使用するユーザに対し、文書等を表示するディスプレイ装置である。入力部２０６は、表示部２０５の表示内容に連動した指示を入力するためのマウス、スティック、パッド等のポインティングデバイスである。タッチパネル機能付きディスプレイ等、表示部２０５と入力部２０６を兼ねる装置を用いてもよい。出力部２０７は、データを紙に出力するプリンタデバイス等である、ネットワーク接続部２０８は、データを装置外から取り込んだり装置外に送信したりする為のネットワークインターフェースである。本図２の２０１〜２０８はＰＣ等の汎用コンピュータ単体として構成しても良いし、あるいはＭＦＰ等の電子機器内に構築してもよい。また、互いに接続された複数のコンピュータやサーバー、およびディスプレイやＰＤＡ等の周辺機器の集合によって構築されてもよい。
【００１８】
図３は、図２のＰＣ等で実行される処理を構成するブロック図の例である。３０３〜３０９はそれぞれが図２の制御部２０１が２０２〜２０８の各部と連携して実行するプログラムである。本例では、ファイル管理サーバー１０５にファイル管理システム３０２を設け、ユーザ端末３０１に不図示のクライアントツールを設ける。ファイル管理システムは、操作取得部３０３、ファイル管理部３０４、データベース３０５、操作履歴管理部３０６、操作履歴データベース３０７、情報送信部３０８と本発明の特徴であるワークフロー抽出部３０９を有する。
【００１９】
次に各処理について説明する。なお、本例ではファイル管理システムの中にワークフロー抽出機能を組み込む形で実施しているが、これに限定されるわけではない。それぞれの機能を単体で実施してもよいし、別の他のシステムに組み込む形で実施してもよい。また、ファイル管理システムとしてクライアントサーバモデルで実施しているが、これに限定されるわけではなく、クライアント単体でも実施可能なことは言うまでもない。
【００２０】
３０３は操作取得部であり、ユーザ端末３０１上のクライアントツールから入力されたファイル操作情報を受け取り、ファイル管理部３０４、操作履歴管理部３０６へファイル操作情報を伝達する。
【００２１】
３０４はファイル管理部であり、操作取得部３０３からファイル操作情報を受け取り、ファイル操作情報に基づきデータベース３０５と連携し所定のファイル操作処理を行う。ここで言うファイル操作とは、例えば、ファイルの新規登録や、オープン、コピー、削除、また、フォルダに対する操作などを指し、その処理内容は一般的なファイル管理システムと同様である。処理結果の情報は、情報送信部３０８を通じて、ユーザ端末３０１に送られ、ユーザ端末３０１上のクライアントツールに表示される。
【００２２】
３０５はデータベースであり、ファイル管理システム３０２で管理するファイルやフォルダの情報や、ファイル管理システム３０２を利用するユーザの情報などを格納したり、取得したりする。ユーザ情報としては、ユーザ名やユーザＩＤなどユーザ単体の情報だけではなく、ユーザが所属するグループや、グループに所属しているユーザのリストなどのユーザグループに関する情報も含んでいる。データベース３０５の詳細な内部構成については、本発明の本質とは異なるため説明を省略する。
【００２３】
３０６は操作履歴管理部であり、操作取得部３０３からファイル操作情報を受け取り、操作履歴データベース３０７にファイル操作履歴としてファイル操作情報を格納する。ファイル操作履歴として登録されるファイル操作情報の例を図５に示す。５０１はログＩＤで、ファイル操作情報を一意に識別するための記号であり、５０２はファイル操作が行われた時間情報を表す。５０３はユーザＩＤで、ファイル操作を行ったユーザを識別するための情報であり、５０４はファイルＩＤで、操作対象のファイルを識別するための情報である。５０５は実行されたファイル操作イベントの種類を表す。ここで挙げたファイル操作情報は一例であり、これに限定されるわけではない。
【００２４】
３０９はワークフロー抽出部である。ここで言うワークフローとは、ある目的を達成するための作業の流れを指し、ファイル操作の集合で表す。単純には、ファイル操作をシーケンシャルに並べたものとし、その頻出パターンを抽出すべきワークフローと考えることが出来る。しかし、ワークフローを単純にシーケンシャルな操作パターンとして捉えると、頻出するパターンが少なく、見つけることが困難になる上に、たとえ、発見し抽出したとしても、そのワークフローは汎用的でない可能性が高い。その理由は、一般的に、オフィスでの仕事のパターンは大まかな流れは似ていても、細かい操作単位で見ると操作の順番が順不同であったり、操作対象のファイルが異なったりすることが多いためである。例えば、図４では、ユーザＡとＢが見積書を作成したときのファイル操作履歴例の時系列データを示しているが、ファイル操作単位で見ると両者には、例えば、次のようなファイル操作の違いがある。
【００２５】
・テンプレートをコピーして作成した見積書のファイル名が異なる
・参考資料として開いたファイルが異なる
・ファイルをリネームしてからムーブするか、ムーブしてからリネームするかなど、順序を変えても結果に差がない操作では、操作順が異なる
このような違いのために、ユーザＡとＢはファイル操作のシーケンシャルなパターンとしては、違うものとして解釈されてしまう。しかし、オフィスでの作業はこのような違いはあることが当たり前であり、このような違いを吸収して同様のワークフローとして解釈する必要がある。そこで本発明では、ファイル操作単位での微妙な差異を吸収するために、複数のファイル操作から成る意味のあるまとまりを抽象アイテム利用操作集合なるタスクとして定義する。タスクをシーケンシャルに並べたものを頻出する抽象アイテム利用操作集合の順序列なるワークフローとする。
【００２６】
続いて、ワークフロー抽出部３０９によるワークフロー抽出の処理ついて図６のフローチャートを用いて説明する。このフローチャートは、ＣＰＵ１０１が制御プログラムを実行することにより実現される。
【００２７】
まず、ステップＳ６０１での処理について、図７，８を用いて述べる。図７に示すファイル操作履歴７０１から、ユーザ単位でのファイル操作履歴７０２を切り出し、そのファイル操作履歴７０２からある区切り指標を用いて、近い時間に行われたファイル操作群（これを、仮タスク７０３とする。）に分割し、アイテム利用操作集合なる仮タスク集合を生成する。ある区切り指標とは例えば、固定時間の間隔に区切る方法でもよいし、ファイル操作間の時間がある一定時間以上長い個所を区切りとしてもよい。例えば、図８（ａ）で示すように、１５分の固定時間間隔でログを分割し仮タスクを生成してもよいし、図８（ｂ）で示すように、フィル操作間の時間が５分以上長い個所で区切り仮タスクを生成してもよい。また、ファイルのチェックアウト−チェックインなど特定のファイル操作に基づき分割しても良いし、ユーザが明示的に作業の区切りを入力できるようにし、それに基づき分割しても良い。
【００２８】
ステップＳ６０２では、ファイル間の類似度（アイテム類似度）の計算を行う。ファイル間の類似度としては、単純に文書内容の類似性を指標とするのではなく、作業におけるファイルの使用され方が似ているものを類似度が高いと見なす指標を用いる。例えばそのような指標として次のようなものが利用できる。
・ファイルのコピー関係
・ファイルの構造情報（ＸＭＬ構造）
・ファイルの共起頻度情報
・ファイルの属性情報
【００２９】
それぞれの指標における類似度は必要に応じて単体で用いても、また、複数を組み合わせて用いてもよい。また、これらに限定されるわけではない。それぞれの指標におけるファイル間の類似度の計算方法について以下で詳しく説明していく。
【００３０】
ファイルのコピー関係によるファイル間の類似度について説明する。例えば、あるテンプレートがあり、そのテンプレートをコピーして作成したファイルＡと、ファイルＢがあったとき、ファイルＡとファイルＢは同じ目的の作業に使用された可能性が高いと考えられる。このような考えから、ファイルのコピー関係（コピー履歴）を利用してファイル間の類似度を定義することが出来る。単純な方法では、例えば、コピー関係にあるファイルを図９のように木構造で表すと、自分自身との類似度を１とし、自分から離れていく毎に減衰係数を類似度に掛けて他のファイルのとの類似度を求めることができる。図９（ａ）に示すコピー関係の場合、減衰係数を０．９としたときの各ファイル間の類似度は図９（ｂ）に示す通りになる。例えばＦｉｌｅ１１１はＦｉｌｅ１をコピーして作成したファイルＦｉｌｅ１１をコピーして作成したファイルなので、Ｆｉｌｅ１とＦｉｌｅ１１１の間の類似度は１×０．９×０．９＝０．８１となる。
【００３１】
次に、ファイルの構造情報（ＸＭＬ構造）によるファイル間の類似度について説明する。近年、文書ファイルは独自形式から、ＸＭＬ形式に変わってきているものが多い。ＸＭＬ形式では文書内容にタグ付けがしてあり、文書の構造と内容とを分離して処理し易い点が特徴である。そこで、文書ファイル間で文書内容には因らず、文書構造が似たものを容易に探すことが可能である。例えば、同じテンプレートから作成されたファイルＡとファイルＢは文書内容は異なるが、同じテンプレートから引き継いだ文書構造は似ているため、文書構造による類似度は有効な指標となる。
【００３２】
次に、ファイルの共起頻度情報によるファイル間の類似度について説明する。例えば、Ｆｉｌｅ１はＦｉｌｅ２とＦｉｌｅ３と一緒に使用される確率が高いとし、また別のＦｉｌｅ１０もＦｉｌｅ２とＦｉｌｅ３と一緒に使用される確率が高いとき、Ｆｉｌｅ１とＦｉｌｅ１０は同じ目的の作業において使用された方が似ていると推定することができる。このような考え方からファイルの共起頻度情報を用いてファイル間の類似度を定義できる。類似度の単純な算出方法としては、二つのファイル間で共通している共起ファイル数を、それぞれのファイルの共起ファイル数の平均で割るなどすればよい。なお、共通している共起ファイルとは、同一のファイルだけを指すわけではなく、類似したファイルを含むようにしても良い。
【００３３】
最後に、ファイルの属性情報によるファイル間の類似度について説明する。ファイル間の類似度を計算する上で有効な情報として、ファイル名やパス名などがある。同じ目的の作業はファイル名に共通性が見られ、一部分が異なっていることが多い。そのような例として、例えば、会議の議事録などは、ファイル名の違いが日付であったり、何かの調査だったりすると、ファイル名の違いはユーザ名だったりする。このようにファイル名に共通性が見られるものをファイル間の類似度が高いとすればよい。例えば、ｆｉｌｅＡとｆｉｌｌｅＢのファイル名による類似度ｓｉｍ（ｆｉｌｅＡ，ｆｉｌｅＢ）として単純には次のように定義できる。
【００３４】
【数１】
2013143039.tif 000003
【００３５】
ここで、ｌｅｎ（ｆｉｌｅＡ）はｆｉｌｅＡのファイル名の長さを表し、ｍｉｎ（ｌｅｎ（ｆｉｌｅＡ），  ｌｅｎ（ｆｉｌｅＢ））はｆｉｌｅＡとｆｉｌｅＢでファイル名が短いほうの長さを表す。またＬＣＳ（ｆｉｌｅＡ，  ｆｉｌｅＢ）はｆｉｌｅＡのファイル名とｆｉｌｅＢのファイル名の最長共通部分列  （Ｌｏｎｇｅｓｔ  Ｃｏｍｍｏｎ  Ｓｕｂｓｅｑｕｅｎｃｅ，  ＬＣＳ）を表す。部分列  （Ｓｕｂｓｅｑｕｅｎｃｅ）  は系列のいくつかの要素を取り出してできた系列のこと。二つの系列の共通の部分列を共通部分列  （Ｃｏｍｍｏｎ  Ｓｕｂｓｅｃｕｅｎｃｅ）と呼ぶ。共通部分列のうち、もっとも長いものを最長共通部分列  （Ｌｏｎｇｅｓｔ  Ｃｏｍｍｏｎ  Ｓｕｂｓｅｑｕｅｎｃｅ，  ＬＣＳ）  と呼ぶ。
【００３６】
また、ファイル名による類似度の他の例として、編集距離と呼ばれる、情報理論において二つの文字列がどの程度異なっているかを示す数値を用いることもできる。具体的には、文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。
【００３７】
以上、４つの指標におけるファイル間の類似度の計算方法について説明した。
【００３８】
ステップＳ６０３では、前ステップＳ６０２で計算したファイル間の類似度を用いて、ファイルをクラスタリングする。クラスタリングの手法としては、階層型と非階層型の大きく２つに分かれるが、ここでは、クラスタの数を予め定める必要のない階層型クラスタリングの手法を用いる。階層型クラスタリングの代表的な手法に、最短距離法、最長距離法、群平均法、ウォード法などがあるがどれを用いてもよい。なお、それぞれの手法の説明については本発明の本質ではないため省略する。本ステップでは、結果として、作業におけるファイルの使用され方が似ているものをグループとしてまとめたものをファイルクラスタとして出力する。なお、ファイルクラスタは１つ以上のファイルのまとまりであり、類似するファイルが１つもないファイルでも、それ単体でファイルクラスタとする。階層型クラスタリングによって生成されたファイルクラスタ（ＦＣ）の例を図１１に示す。ここでは、ＦＣ１はファイル１、ファイル４５、ファイル９５を含むファイルクラスタであり、また、ＦＣ２はファイル１３のみを含むファイルクラスタである。
【００３９】
ステップＳ６０４では、ステップＳ６０１で生成した仮タスクに対して、ステップＳ６０３で出力したファイルクラスタを用いて、仮タスクを構成するファイル操作群のファイルを、そのファイルが含まれるファイルクラスタに置き換えることを行う。これを仮タスクの抽象化と呼ぶ。具体的な処理の例について図１２を用いて説明する。図１２の左はステップＳ６０１で生成された仮タスクを表し、右は本ステップによりファイルをファイルクラスタに置き換えた仮タスクである。例えば、仮タスク１の最初の要素であるＦｉｌｅ１−ｏｐｅｎは、Ｆｉｌｅ１がステップＳ６０３で生成したＦＣ（ファイルクラスタ）１に含まれるため、ＦＣ１−ｏｐｅｎに置き換えられる。以降、仮タスクが持つすべての要素についてそのファイルが含まれるファイルクラスタに置き換え、図１２の右のような仮タスクを生成する。
【００４０】
ステップＳ６０５では、前ステップまでで生成されたファイルクラスタ単位の仮タスクを用いて、仮タスク間の集合類似度を計算する。仮タスク間の集合類似度としては、仮タスクに含まれるファイルクラスタ操作集合の要素の一致度を類似性指標とする。このような集合の類似性の指標としては、ジャッカード係数やダイス係数、シンプソン係数などが知られている。どの係数も分子は集合間で一致する要素数となり、分母がそれぞれ、二集合間の和集合の要素数、平均要素数、小さい集合の要素数と異なる。それぞれ類似度は０．０〜１．０の値をとる。例えば、図１３に示す仮タスク１と仮タスク１０の間のシンプソン係数を使った類似度は、４／５＝０．８となる。同様に仮タスク１０と仮タスク１００の間のシンプソン係数を使った類似度は１／６＝０．１７となり、仮タスク１０は、仮タスク１００より仮タスク１と類似していると求めることができる。ここで、前ステップＳ６０４により、ファイルを、作業におけるファイルの使用され方が似ているものにまとめたファイルクラスタに抽象化を行ったことが有効に働いてくる。本来、同じ目的の作業を行っていても、その作業で扱うファイルはその都度違うことがあり、その結果ファイル単位で仮タスク間類似度を測ると、同じ目的の作業にも関わらず類似度は低くなってしまう。このような事態を避けるために、ファイルは作業における使用され方が似ているものにまとめて抽象化することが望ましい。
【００４１】
ステップＳ６０６では、前ステップＳ６０５で計算した仮タスク間の類似度を用いて、仮タスクをクラスタリングする。クラスタリングの処理方法については、ステップＳ６０３のファイルのクラスタリングと同様の方法であるので割愛する。
【００４２】
ステップＳ６０７では、前ステップＳ６０６で作成した仮タスクのクラスタリングを用いて、タスクの抽出を行う。タスクは、作成した仮タスクのクラスタリングの１つ１つとする。ここで、仮タスククラスタに含まれる仮タスク数が閾値以上のものだけをタスクとしてもよい。仮タスククラスタに含まれる仮タスク数が多いということは、それだけそのタスクはよく行われ、汎用的であると言える。逆に、少ない場合には、あまり汎用的ではなく、タスクとして重要ではない可能性がある。
【００４３】
タスクを表現するファイル操作の要素は、仮タスククラスタに含まれる仮タスクが持つファイル操作の要素から求められる。タスクを表現するファイル操作の要素を求める例について図１４を用いて説明する。図１４（ａ）は仮タスククラスタ１に仮タスク１と仮タスク１０が含まれるとし、そこからタスク１を生成している例である。ここでは、タスク１を表現するファイル操作の要素は、仮タスク１と仮タスク１０が持つファイル操作要素の和集合としている。このようにタスクを表現するファイル操作の要素は、仮タスククラスタに含まれるすべての仮タスクが共通して持っているファイル操作要素としてもよいし、または、ある一定数、あるいは一定の割合数の仮タスクに含まれるファイル操作要素としてもよい。さらに、図１４（ｂ）に示すように、各ファイル操作に対して、それを含む仮タスク数を、仮タスククラスタに含まれる全仮タスク数で割ることで出現割合とし、ファイル操作と出現割合をセットにした要素でタスクを表現してもよい。もちろん、出現割合に閾値を設け、閾値以上の出現割合のファイル操作のみに絞ってもよい。
【００４４】
ステップＳ６０８では、タスクをシーケンシャルに並べたものである抽象アイテム利用操作集合の系列なる仮ワークフローの抽出を行う。仮ワークフローの抽出方法の例について、図１６、１７を用いて説明する。図１６（ａ）の１６０１はあるユーザのファイル操作履歴であり、そこからステップＳ６０１によって仮タスクが抽出されている。仮ワークフロー抽出するにあたっては、ある条件により仮タスク間で分割することを行う。例えば、図１６（ａ）では、時間的条件により仮タスク間を分割しており、この例では、仮タスク間に３０分以上の間隔がある場合に分割するとし、間隔が４８分である仮タスク３と仮タスク４の間で分割される。次に、分割することで得られた仮タスク１→仮タスク２→仮タスク３のシーケンスを、前ステップＳ６０７で抽出したタスクに置き換えることで、タスクのシーケンスへと変換する。この例では、仮タスク１はタスク１へ、仮タスク２はタスク２へ、仮タスク３はタスク３へと置き換えることで、タスク１→タスク２→タスク３というタスクのシーケンスへと変換される。このようにして得られたタスクシーケンスを仮ワークフローとして抽出する。
【００４５】
図１６（ａ）では、時間的条件により仮タスク間を分割したが、これに限らない。時間的条件で分割する方法では、作業の途中で休憩や、会議などを挟んだ場合に不具合が生じる為注意が必要である。別の方法として、図１６（ｂ）では、仮タスク間に共通のファイルを１つも持たない個所で、仮タスク間を分割している例である。仮タスク１、仮タスク２、仮タスク３にはＦｉｌｅ１に対する操作が含まれており、これら仮タスクは同じ目的の作業が継続していると推測できる。仮タスク３と仮タスク４の間には共通のファイルが存在しないため、仮タスク３と仮タスク４は別の目的の作業と推測しここで仮タスク間を分割する。仮タスク間で分割したあと、仮ワークフローを抽出するまでの流れは図１６（ａ）を用いて前述した通りである。もちろん、時間的条件と組み合わせて仮ワークフローを抽出するようにしてもよい。
【００４６】
また、図１７が示すように、例えば、仮タスク２が含まれるタスクが存在しない場合には、抽出される仮ワークフロー１はタスク１→タスク３となる。
【００４７】
ステップＳ６０９では、前ステップＳ６０８で抽出した仮ワークフローに対して、シーケンシャルパターンマイニングを行い、頻出するタスクシーケンスを発見し、これを最終的にワークフローとして抽出する。シーケンシャルパターンマイニングは次のように定義される処理である。
【００４８】
Ｉ＝｛ｉ１，  ｉ２,…,  ｉｎ｝を、アイテム集合とする。集合Ｉの空でない部分集合をエレメントと言う。また、ある閾値ξ＞０が与えられたとき、集合Ｉにおいてξ回以上現れるアイテムを頻出アイテムと言う。エレメントの順序列をシーケンスと言う。さらに、シーケンスα＝〈ａ１，  ａ２，  …，  ａｎ〉とシーケンスβ＝〈ｂ１，  ｂ，  …，  ｂｎ〉に対して、ａ１⊆ｂｊ１,  ａ２⊆ｂｊ２,  …,  ａｎ⊆ｂｊｎなる整数１＜ｊ１＜ｊ２＜…＜  ｊｎ＜ｍがあるとき、αをβのサブシーケンスと言いα⊆βと表記する。シーケンスｉｄのｓｉｄとシーケンスｓのタプル〈ｓｉｄ,  ｓ〉の集合であるＳ＝｛〈ｓｉｄ１,  ｓ１〉，  〈ｓｉｄ２,  ｓ２〉，  …,〈ｓｉｄｎ,  ｓｎ〉｝をシーケンスデータベースと呼ぶ。さらに、系列αの系列データベースＳにおけるサポートとは、Ｓ中のすべての系列のうち、系列αを含むタプルの数と定義される。閾値ξ（最小サポート値と呼ぶ）以上の個数の〈ｓｉｄ,  ｓ〉に含まれているシーケンスをシーケンシャルデータベースにおけるシーケンシャルパターンと言う。シーケンシャルパターンマイニングとは、シーケンスデータベースＳと最小サポート値ξが与えられたときに、Ｓにおけるシーケンシャルパターンを全て見付けることである。代表的なシーケンシャルパターマイニングの手法として、Ａｐｒｉｏｒｉアルゴリズム（Ａｇｒａｗａｌ，  Ｒ．  ａｎｄ  Ｓｒｉｋａｎｔ，  Ｒ．，  “Ｆａｓｔ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｍｉｎｉｎｇ  Ａｓｓｏｃｉａｔｉｏｎ  Ｒｕｌｅｓ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２０ｔｈ  ＶＬＤＢ  Ｃｏｎｆｅｒｅｎｃｅ，  １９９４，  ｐ４８７−４９９）、ＰｒｅｆｉｘＳｐａｎ（Ｊ．  Ｐｅｉ，  Ｊ．  Ｈａｎ，  Ｂ．  Ｍｏｒｔａｚａｖｉ−Ａｓｌ，  Ｑ．  Ｃｈｅｃｎ，  Ｕ．  Ｄａｙａｌ，  ａｎｄ  Ｍ．Ｃ．  Ｈｓｕ，  “ＰｒｅｆｉｘＳｐａｎ：  Ｍｉｎｉｎｇ  ｓｅｑｕｅｎｔｉａｌ  ｐａｔｔｅｒｎｓ  ｅｆｆｉｃｉｅｎｔｌｙ  ｂｙ  ｐｒｅｆｉｘ−ｐｒｏｊｅｃｔｅｄ  ｐａｔｔｅｒｎ  ｇｒｏｗｔｈ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＣＤＥ，  ２００１，  ｐ２１５−２２４）などがある。
【００４９】
本実施形態においては、上記シーケンシャルパターンマイニングの説明でのアイテムをタスク、シーケンスを仮ワークフロー、シーケンスデータベースを仮ワークフロー集合としてシーケンシャルパターンマイニングを適用する。そして、タスクのシーケンシャルパターンを最終的な目的であるワークフローとして抽出する。仮ワークフロー集合からワークフローを抽出する例を図１９を用いて説明する。図１９の１９０１は仮ワークフロー集合である。集合は４つの仮ワークフローから成り、例えば仮ワークフロー１はタスク１→タスク２→タスク３のタスクシーケンスから成る。このような仮ワークフロー集合に対して、最小サポート値２のシーケンシャルパターンを抽出した結果、タスク１→タスク２→タスク３、タスク１→タスク４の２つのワークフローを含むワークフロー集合１９０２を得ることができる。なお、ここで抽出したシーケンシャルパターンは他のシーケンシャルパターンのサブシーケンスになるものを除いたものであり、このようなシーケンシャルパターンをクローズドシーケンシャルパターンと呼ぶ。
【００５０】
以上、ワークフロー抽出部３０９によるワークフロー抽出の処理ついて、ステップＳ６０１〜Ｓ６０９のフローチャートに従って説明した。なお、ワークフローは、複数のファイル操作から成る意味のあるまとまりをタスクとして定義し、タスクをシーケンシャルに並べたものであり、最終的に抽出されたワークフローのイメージを図２０に載せる。
【００５１】
以上、本発明における頻出パターン抽出方法を、ファイル管理システムにおけるファイル操作履歴からのワークフローの抽出という実施形態で説明した。このように、本発明では、文書名や、利用した順番の違いを吸収し、より汎用的なワークフローを抽出することができる。抽出したワークフローは仕事の効率を向上させることに利用可能である。例えば、可視化して業務の見直しに役立てたり、ワークフローシステム構築の参考にしたり、ユーザのファイル操作をナビゲートするファイル推薦など幅広く利用可能である。
【００５２】
［実施形態２］
本発明における頻出パターン抽出方法およびアイテム推薦方法の例を図面に基づいて説明する。本実施形態では、アイテムとして、フォルダ（またはディレクトリ）構造を持つファイルを対象とし、実施形態１のファイル管理システムに機能を追加する形でアイテム推薦、さらにはアイテムの操作推薦機能を設ける。本実施形態における、システム構成例、各装置の構成例は実施形態１と同様である。なお、本実施形態では、アイテムとして、ファイルを対象としているがそれに限定されない。例えば、デジタルカメラなどの機器や、ＰＣなどのアプリケーションソフトの場合には、その操作メニューや設定項目などをアイテムと見なすことができ、本発明を適用することでその操作のナビゲーションを効果的に行うことが可能となる。
【００５３】
図１０は本実施形態で実行される処理を構成するブロック図である。ファイル管理システム１００１が持つ一部を除いた各手段とその処理は実施形態１で説明した通りである。例えば、ワークフロー抽出部１００６は、ワークフロー抽出部３０９と同様に、ステップＳ６０１〜ステップＳ６０９の手順で操作履歴からワークフローを抽出する。本実施形態では、アイテム推薦機能を有するファイル操作推薦部１００４が追加されていることが特徴である。なお、本例ではファイル管理システムの中にアイテム推薦機能などを組み込む形で実施しているが、これに限定されるわけではない。それぞれの機能を単体で実施してもよいし、別の他のシステムに組み込む形で実施してもよい。また、ファイル管理システムとしてクライントサーバモデルで実施しているが、これに限定されるわけではなく、クライアント単体でも実施可能なことは言うまでもない。
【００５４】
ファイル操作推薦部１００４は、ワークフロー推定部１００５を含み、ユーザの現在のファイル操作が操作履歴から得られるどのワークフローに当てはまるか推定し、推定したワークフローに基づいて次に操作すべきファイルを推薦する。さらには、ファイルの操作を推薦する。推薦するファイル、ファイル操作情報は情報送信部１００３を通じて、ユーザ端末１００２に送る。ユーザ端末１００２上のクライアントツールは、ファイル管理システム１００１より送られてきた推薦ファイル操作情報を表示する。
【００５５】
続いて、ファイル操作推薦部１００４による抽出したワークフローに基づいたファイル、さらにはファイル操作の推薦方法について説明する。ファイル操作推薦部１００４は、ワークフロー推定部１００５を含み、まずワークフロー推定部１００５により、ユーザの直近のファイル操作が操作履歴から得られるどのワークフローに当てはまるか推定を行う。それから、推定したワークフローに基づいて、ユーザに次のファイル、さらにはファイル操作を推薦する。
【００５６】
はじめに、ワークフロー推定部１００５による処理を図２１のフローチャートを用いて説明する。このフローチャートは、ＣＰＵ１０１が制御プログラムを実行することにより実現される。
【００５７】
ステップＳ２１０１では、ユーザの直近のファイル操作ｎ個を入力として受け取り、ワークフロー抽出部１００６のステップＳ６０１と同様の方法により、仮タスクを抽出する。例えば、図２２で示すようなファイル操作履歴８個が入力されたとすると、仮タスク１０００と仮タスク１００１の２つが抽出される。
【００５８】
ステップＳ２１０２では、仮タスクの抽象化を行う。該ワークフロー抽出部１００６のステップＳ６０３で作成されたファイルクラスタを利用し、ステップＳ６０４と同様に仮タスクの抽象化を行う。すると、図２３に示すようにファイルクラスタの操作に抽象化された仮タスク１、仮タスク２が得られる。
【００５９】
ステップＳ２１０３では、抽象化した仮タスクと該ワークフロー抽出部１００６により操作履歴から抽出されたタスクとの類似度を計算し、似たタスクを推定する。類似度の計算方法は、該ワークフロー抽出部１００６のステップＳ６０５と同様である。その結果、図２４に示すように、仮タスク１０００、仮タスク１００１はそれぞれ、タスク１、タスク２と推定される。
【００６０】
ステップＳ２１０４では、推定されたタスクのシーケンスが操作履歴から得られるどのワークフローに当てはまるか推定を行う。推定は単純にシーケンスの一致度の高いワークフローを現在ユーザが行っているワークフローとして推定すればよい。また、一致度に加え、現在のタスクの後ろに残っている部分シーケンス長が長いワークフローを優先したり、ワークフローの頻出頻度が高いワークフローを優先したりしてもよい。最終的に、図１８で示すように、タスク１→タスク２へのシーケンスが一致するワークフロー１が推定結果となる。
以上、図２１のフローチャートを用いてワークフロー推定部１００５について説明した。
【００６１】
次に、ワークフロー推定部１００５によって推定されたワークフローを用いて、ユーザにファイル、さらにはそのファイル操作を推薦する処理について図１５のフローチャートを用いて説明する。このフローチャートは、ＣＰＵ１０１が制御プログラムを実行することにより実現される。
【００６２】
ステップＳ１５０１では、推定されたワークフローにおける、ユーザの現在のタスクを特定する。図１８で示すようにユーザの現在のタスクはタスク２であると特定される。
【００６３】
ステップＳ１５０２では、特定したタスクの中で、ユーザがまだ行っていないファイル操作を推薦する。ここで、タスクは具体的なファイル操作ではなく、抽象化されたファイルクラスタで構成されているので、実際にファイル操作を推薦する際には、ファイルクラスタから具体的なファイルへと変換する必要がある。つまり、特定したタスク２の中でまだユーザが行っていないファイルクラスタ操作はファイルクラスタ６２に含まれるファイルを開くであるが、ファイルクラスタ６２に含まれるどのファイルを開くかを特定する、もしくはランキング付けすることが望ましい。そのような方法としては、例えば、ファイルクラスタの中で、アクセスの新しい順、アクセス頻度が高い順、直近にそのユーザが開いたファイルと一緒に使用された頻度、などから求めればよい。特定せずに、ファイルクラスタ６２に含まれるすべてのファイルを提示し、いずれかを開くように推薦してももちろんよい。
【００６４】
ステップＳ１５０３では、特定したタスク内のすべてのファイルクラスタ操作をユーザが行ったかを判断し、まだ残っていればステップＳ１５０３へ、完了していれば、次のステップＳ１５０４へ進む。
【００６５】
ステップＳ１５０４では、推定したワークフロー内のすべてのタスクをユーザが行ったかを判断し、まだタスクが残っていればステップＳ１５０１へ、完了していれば、ワークフローの完了として、そのワークフローに関するファイル操作の推薦を終了する。
【００６６】
以上、図１５のフローチャートを用いてファイル操作推薦部１００４によるユーザにファイル操作を推薦する処理について説明した。もちろん、ファイル操作を推薦するのでなく、システムが自動的にそのファイル操作を行うようにしてもよい。
【００６７】
以上、本発明における頻出パターン抽出および推薦システムを、ファイル管理システムにおけるファイル操作履歴からのワークフローの抽出、そして抽出したワークフローを用いてのファイル操作の推薦という実施形態で説明した。このように、文書名や、利用した順番の違いを吸収し、より汎用的なワークフローを抽出することができ、それを用いることで、ユーザのファイル操作をナビゲートするなど、作業の効率化をはかることが出来る。
【００６８】
［実施形態３］
なお、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録したコンピュータ可読の記憶媒体を、システムあるいは装置に供給することによっても、達成される。また、システムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても、達成してもよい。
【００６９】
この場合、記憶媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００７０】
プログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。
【００７１】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現される。また、プログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態が実現される場合も含まれる。
【符号の説明】
【００７２】
３０１  ユーザ端末
３０２  ファイル管理システム
３０３  操作取得部
３０４  ファイル管理部
３０５  データベース
３０６  操作履歴管理部
３０７  操作履歴データベース
３０８  情報送信部
３０９  ワークフロー抽出部
【図１】
2013143039.tif 000004
【図２】
2013143039.tif 000005
【図３】
2013143039.tif 000006
【図４】
2013143039.tif 000007
【図５】
2013143039.tif 000008
【図６】
2013143039.tif 000009
【図７】
2013143039.tif 000010
【図８】
2013143039.tif 000011
【図９】
2013143039.tif 000012
【図１０】
2013143039.tif 000013
【図１１】
2013143039.tif 000014
【図１２】
2013143039.tif 000015
【図１３】
2013143039.tif 000016
【図１４】
2013143039.tif 000017
【図１５】
2013143039.tif 000018
【図１６】
2013143039.tif 000019
【図１７】
2013143039.tif 000020
【図１８】
2013143039.tif 000021
【図１９】
2013143039.tif 000022
【図２０】
2013143039.tif 000023
【図２１】
2013143039.tif 000024
【図２２】
2013143039.tif 000025
【図２３】
2013143039.tif 000026
【図２４】
2013143039.tif 000027