論文 / 著書情報
Article / Book Information
論題(和文)

ファイル RMC 操作に基づくタスク間関係を用いたファイル検索

Title(English)

File Search by Considering Relationship between Tasks based on RMC
Operations

著者(和文)

呉 怡, 渡辺 陽介, 横田治夫

Authors(English)

Yi WU, Yousuke WATANABE, Haruo Yokota

出典(和文)

DEIM Forum 2011 A9-2, , ,Citation(English)

DEIM Forum 2011 A9-2, , ,

発行日 / Pub. date2011, 3

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2011 A9-2

ファイル RMC 操作に基づくタスク間関係を用いたファイル検索
呉

怡†

渡辺

陽介††

横田 治夫†† 東京工業大学大学院 情報理工学研究科計算工学専攻 〒 152-8552 東京都目黒区大岡山 2-12-1†† 東京工業大学 学術国際情報センター 〒 152-8552 東京都目黒区大岡山 2-12-1
E-mail: †{goi,watanabe}@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
あらまし

近年，ファイルシステム内に格納されているファイルの数が爆発的に増加している．しかし，キーワード

によるデスクトップサーチによく用いられる全文検索では，テキストを含まないファイルが検索できない．我々はこれまで，キーワード検索の結果を改善するために，ユーザの操作を記録したファイルアクセスログを使って関連ファイルを発見する手法を提案してきた．本研究では，同一作業に関連するファイルは頻繁に近い時間に使用される傾向があることから，このようなファイル集合を「タスク」として抽出する．また，ファイル間の改名・移動・コピー（RMC）操作を考慮したタスク間関連度の評価式を用いて，全文検索に提案手法を取り入れた新たなファイル検索シ
ステムを開発し，被験者実験により，手法の有効性を確認する．
キーワード

デスクトップ検索，全文検索，タスクマイニング

File Search by Considering Relationship between Tasks based on
RMC Operations
Yi WU† , Yousuke WATANABE†† , and Haruo YOKOTA†† Department of Computer Science, Graduate School of Information Science and Engineering
2–12–1 Ookayama, Meguro-ku, Tokyo, 152–8552 Japan†† Global Scientific Information and Computing Center, Tokyo Institute of Technology
2–12–1 Ookayama, Meguro-ku, Tokyo, 152–8552 Japan
E-mail: †{goi,watanabe}@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
Abstract In recent years, there has been an explosive increase in the number of files stored in the file system.
However, full-text search which refers to a technique commonly used for keyword-based desktop search is not available for files not containing text. To improve keyword search, we have been proposed a method to find related files
by considering the history of file access. Assuming that files related to same work tend to be used at the same time
frequently, we extract such files as a ”task” and derive formulas for calculating the strength of association between
tasks in consideration of the rename, move and copy (RMC) operations. In this study, we develop a new file retrieval
system incorporating the formulas into full-text searching, and demonstrate validity of the method.
Key words desktop search, full text search, task mining

1. ま え が き

実現しているが，ファイル内のテキスト情報のほかに，ファイル名や作成時間といった簡単なメタ情報しか考慮していない．

情報爆発とも言われているように，ファイルシステム内にあそのため，たとえ辞書を利用してもキーワードから図やビデオ

るファイルの数が日々増加しており，ファイルの内容やファイファイルのようなファイルを検索することが難しく，テキスト

ル間の関係を把握することが容易ではない．この問題に対して，を含まないファイルに対して有効とは言い難い．

数多くのデスクトップ検索ツールが開発されてきた．よく知ら一方で，ファイル間のアクセス共起に基づく相関関係をれているものとして，グーグルの Google デスクトップ [1] や，

利 用 し た 研 究 も 始 まって い る ．例 と し て ，Connections [4]，マイクロソフトの Windows デスクトップ サーチ [2]，Mac OS

FRIDAL [5]〜[7] などがある．しかし，偶然の同時アクセスX に搭載されている Spotlight [3] などがある．これらのデスクにより，間違った相関関係が抽出されやすい．このような背景

トップ検索システムはどれも高速なインデックシングと検索をから我々は頻繁に近い時間にアクセスされたファイルを同一作

業に関連するものとし，このようなファイル群を「タスク」とファイル操作から，ファイル間における参照・被参照関係の有して抽出してから検索を行うことで，全文検索の課題を解決で無を推定し，参照されたファイル（input）から参照したファきると考えた．そして，作業間を結びつける要素として，ファイル（output）へと重み１のエッジを張る．ファイル検索を行

イルの改名（Rename）
・移動（Move）
・コピー（Copy）（以降，

う際は，エッジの向きと重みでノードであるファイルの重みをRMC）操作を考慮したタスク間関連度を提案している [8]．な

伝搬する．そうすることで全文検索の結果を拡張し，リラン

ぜなら，RMC 操作があったファイル同士では，それぞれのファキングを実現する．Connections では参照・書込み操作のほかイルが使われた作業間でも強い関連性があると考えられる．例に，コピーや改名といった操作も使われているが，ファイル間

えば，論文執筆作業で使用した図をコピーして発表資料作成作のエッジの向きを決めるためだけに使用されている．これに対業で再利用する場合において，コピー操作を考慮すれば作業間して，本研究では，RMC 操作をタスク間関連度の算出に利用の依存関係がわかる．なお，本稿における作業とは書類作成のしている．

ような複数のファイルをアクセスしながら行う論理的にひとつ

Watanabe らが開発した FRIDAL [5]〜[7] では，キーワードの仕事で，ある作業に関連する複数のファイルの集合を「タスを含まないファイルを検索可能にするために，ファイルの open・ク」と表す．

close ログを使用している．FRIDAL では，同時に使用したファ

そこで，本研究ではファイルに対する参照・書込みなどのイルは互いに関連するとして，共起時間や共起回数といった情基本操作に加え，RMC 操作に着目したタスク間関連度と通常報に基づき，ファイル間関連度を数値化している．キーワードのキーワード検索と組合せた検索方式を SUGOI (Search by

検索の際には，検索語を含むファイルのスコアをファイル間関Utilizing Groups Of Interrelated files in a task) を提案する．

連度によって検索語を含まないファイルへと伝搬させることで，

SUGOI では検索前の準備段階において，ファイル間の共起情

キーワード非含有ファイルの検索が可能となる．これに対して，

報や RMC 操作を考慮して同一作業に使用されたファイル群を本研究では，アクセスログに基づき，よく近い時間にアクセスタスクとして抽出する．抽出されたタスク間の関連の強さを表されたファイルのグループをタスクとして抽出してから，RMCしたタスク間関連度はファイルの重複度から算出されるタスク

操作を考慮してタスク間関連度を算出している．

間類似度とファイル RMC 操作に基づくタスク間 RMC 関連度

本研究と同じくタスクマイニングを行っている研究として，によって算出される．その際，時間，編集回数，ファイルサイ

Chen らが提案した iMecho [9] というシステムがある．iMecho

ズの変化による関連度の減衰についても考慮する．

では，ファイルの内容とファイルアクセスログから以下３種類

検索する際には，まず全文検索によりキーワードを含むファの相関リンクを生成する．

イルを特定し，そのファイルが属するタスクを発見する．次に，•ファイル内容に基づく相関リンク（例：内容の類似度）

タスク間の関連度に基づいて，全文検索で見つけたタスクとの•ファイルアクセスログから直接的に得られる相関リンク

関連が強い他のタスクを発見する．SUGOI 検索方式により， （例：ファイルコピー）
キーワードを全く含んでいないファイルであっても，関連する•

タスクに属していれば検索結果として提示することが可能とな（例：同じタスクに属するファイル）

アクセスパターンから間接的に得られる相関リンク

る．我々の研究グループが日常的に使っているファイルサーバ

このように，iMecho はコピー操作とタスクマイニングの結果

におけるファイルアクセスログを利用した評価実験により，タをファイル間の相関リンクの生成に利用しているが，タスク間

スク間関連度を用いたことで，検索結果の適合率，再現率共にの関係を考慮していない．また，iMecho がランキングに使用向上させることが可能であることを示す．

するスコアは，PageRank [10] に基づくリンク解析の結果と全以下に論文の構成を述べる．2. 節ではデスクトップ検索と文検索のスコアの積によって定義されているため，キーワード

ファイル整理に関する既存研究を紹介する．3. 節でタスクとタを含まないファイルはキーワード検索の結果として提示される

スク間の関連を考慮したファイル検索手法について説明を行う．

ことはない．それに対して，本研究ではキーワードを含まない

4. 節において評価実験を記述し，5. 節にてまとめと今後の課題

ファイルであっても検索結果に含むことが可能である．

について述べる．

2. 関 連 研 究

2. 2 ファイルクラスタリング
小田切らは複数のディレクトリに分散している同一作業に関連するファイル群を発見する COFI (Clustering using Overlap

近年，個人が扱うファイルの数が増加し続け，パソコン上にof file-use time for Frequent Itemsets) 法 [11] を提案してい散らばっているデータから必要な情報を手軽に見つけ出せるよる．COFI 法では，同一作業に関連するファイルは頻繁に近い

うに，ファイル検索・整理を目的とした研究が数多くなされて時間に使われるという性質を利用してファイルを作業単位にクきた．本節では，本稿と同様にファイルアクセスログを利用しラスタリングして仮想ディレクトリ―として提供している．作

た既存研究について紹介する．

業ごとに使用されたファイル群を求めるため，COFI 法はまず，

2. 1 アクセスログを用いたファイル検索

頻出アイテム集合抽出によく用いられる Apriori アルゴリズ

1. 節でも言及した Connections [4] は，Soules らによって提ム [12] を使って，近い時間にアクセスが度々観測されるような案されたファイル検索ツールで，ファイルシステムコールのロ

ファイルの集合を発見する．次に，集合間のアクセス時間の重グを使用している．Connections はある一定の時間内における複度に基づき，階層的クラスタリングを行うことにより，ファ図 1 システムイメージ
図 2 トランザクションへの分割（T ransactionT ime = 3600sec）

イルを作業ごとにまとめた仮想ディレクトリを生成する．これに対して，本研究におけるタスクマイニングはファイルクラス
タリングのためではなく，キーワード検索の結果を改善するた

タスクマイニングによって，ユーザがアクセスした多くのファイルは少なくともひとつのタスクに属することになる．

めである．また，COFI 法ではファイルの open・close ログの3. 1. 1 FI タ ス ク

みを利用しているが，本研究では RMC 操作まで考慮する．

論文執筆作業の際，tex ファイルのほかに pdf ファイルやグ

3. 提案手法 SUGOI

ラフなどの図のファイルに対して，近い時間にアクセスを繰り返すことがあるように，同一作業に関連するファイルは，頻繁

我々は文献 [8] において，RMC 操作を考慮したタスク関連度に近い時間にアクセスされることが多い．タスクを抽出するたを用いて，関連ファイルを発見する手法を提案している．本稿

め，COFI 法 [11] と同様に頻出アイテム集合であるファイル群で用いるタスク間関連度は，文献 [8] に拡張を加えたものであを発見する．

る．提案システムの構成は図 1 で示しているように，主な処理

我々は ま ず，ファイ ル ア ク セ ス ロ グ を 一 定 の 時 間 幅はタスク及びタスク間の関連を抽出する部分と，ユーザが与え(T ransactionT ime) でトランザクション単位に分割する (図た検索キーワードからファイルを検索する部分からなっている．

2) ．次に，Eclat アルゴリズム [13] を適用し，トランザクショ

手法適用に必要なファイルアクセスログはファイルシステム

ンにおける出現回数が M inSuppCnt 回以上の頻出ファイル集に対するアクセスを監視することによって取得する．ただし，合をタスク (T ) として抽出する．提案手法では，長い期間にログにはアクセスの時間，クライアントユーザを特定できる情

わたるファイルアクセスログを解析対象としているため，個別報，アクセスしたファイル，行われた操作といった項目を含む

ファイルのアクセス回数に比べ，トランザクションの件数が遥ものとする．本節において下記の処理について説明する．なお，

かに大きく，M inSuppCnt を低く設定する必要がある．そこ

ログクリーニングに関しては実験で使用した監視ツールに特化で，低い M inSuppCnt を設定してもパフォーマンスへの影響したものになっているため，4. 1. 1 節で記述する．

が小さい頻出アイテム集合マイニングアルゴリズム Eclat [13]（ 1 ） RMC 操作に着目したタスクマイニング (3. 1 節)を採用する．最後に，他の集合の部分集合でない集合のみを FI（ 2 ） RMC 操作を考慮したタスク間関連度の算出 (3. 2 節)

タスクとする．

（ 3 ） タスクとタスク間関連度を用いたファイル検索 (3. 3 節)

3. 1. 2 RMC タスク

3. 1 タスクマイニング

過去の作業で使われた複数のファイルをコピーなどをして，タスクマイニングの目的は作業ごとのファイル群を発見する

他の作業で再利用することがよくある．それ故，ある一定の時ことである．抽出対象のタスクは下記の 2 種類ある．

間幅の中で RMC されたファイル群を過去に行われたある作業

FI タスク: 頻出アイテム集合 (Frequent Itemset) であるタに関連するファイルのグループと考えられ，本稿では，このよ

スクである．その着眼点は同一作業に関連するファイルは頻繁

うなファイルのグループをタスクとして抽出する (図 3)．

に近い時間にアクセスされる傾向があることである．

3. 2 タスク間関連度の算出

RMC タスク: RMC 操作に基づいて抽出されるタスクで，本本研究においてはタスク間の関係を，各タスクをノードとし研究で新たに導入したものである．複数のファイルに対して，たグラフ構造で表現する．タスク同士をつなぐエッジには，タ

短時間のうちにまとめて RMC 操作が行われた場合，それらスク間の関連の強さを表す重みの数値が付与される．タスク間のファイル群は論理的に意味のあるまとまりであり，同一作業の関連を数値化する際に，タスクにあるファイルの重複を考慮に由来するものである可能性が高い．そこで，このようなまとしたタスク間類似度と，ファイル間 RMC 操作に着目したタス

まった RMC 操作の行われるファイル群については，アクセス

ク間 RMC 関連度を用いる．特にタスク間 RMC 関連度は，異が頻出でなくてもタスクとして取り扱い，RMC タスクとしてなるタスクにまたがるファイル間の RMC 操作の種類や回数の抽出する．

みならず，RMC 操作が発生してからの経過時間，編集回数，

rmcf (fi → fj ) =



α1





α2





 β1
β2




γ1





γ2




0

if fi was renamed to fj ,if fi was renamed from fj ,if fi was moved to fj ,if fi was moved from fj ,if fi was copied to fj ,if fi was copied from fj ,otherwise.
(3)

式 (3) では，ファイル fi からファイル fj へ RMC 操作が発生したことによって得られる fi ，fj 間のファイル RMC 関連度を定義している．α1 ，α2 ，β1 ，β2 ，γ1 ，γ2 は全てパラメータで

図 3 RMC タスクの抽出ある．
ファイルサイズの変化による関連度の減衰についても考慮してこのように定義されたファイル間 RMC 関連度は定数になるが，実際，同じ RMC 操作でも，より最近に RMC 操作のいる．
両タスク間関連度 R(Tm → Tn ) は，各作業で使われたファ

あったファイル間の関連が強い．また編集が重なることにより，イルの重複度合いを表したタスク間類似度 simt (Tm → Tn ) と，

RMC 操作のあったファイル内容に差分が大きくなることで，タスクをまたがったファイル間 RMC 操作の種類や回数を考慮

関連が弱くなる可能性があると考えられる．そこで，経過時間，したタスク間 RMC 関連度 rmct (Tm → Tn ) によって算出され編集回数，ファイルサイズの増減に基づく下記の３式を用いてる (式 (1))．

減衰の度合いを算出する．

R(Tm → Tn )= θ ∗ simt (Tm → Tn ) + (1 − θ) ∗ rmct (Tm → Tn )(1)
ただし，θ はタスク間類似度とタスク間 RMC 関連度を考慮する度合いを調節するためのパラメータで，(0 <= θ <= 1) を満たす．

(4)

E(fi , fj ) = ∆edit (fi , fj )−(5)S(fi , fj ) = ∆size (fi , fj )−σ(6)

ただし，T (fi , fj ) は経過時間，E(fi , fj ) は編集回数，S(fi , fj )はファイルサイズの増減によってファイル間 RMC 関連度に与える影響を表す．∆time (fi , fj ) はファイル fi ，fj 間で RMC操作が発生してから経過した時間で，τ は経過時間による影響

3. 2. 1 タスク間類似度
多くの共通ファイルを使った作業間の関係が強いと推測できるため，各タスクに含まれるファイルの重複の度合いに基づいてタスク間類似度を算出する．
タスク m，n 間のタスク間類似度 simt (Tm → Tn ) は式 (2)によって定義される．

|Tm ∩ Tn |simt (Tm → Tn ) =|Tm |T (fi , fj ) = ∆time (fi , fj )−τ

の度合いを調節するためのパラメータである．∆edit (fi , fj ) はファイル fi ，fj 間で RMC 操作が発生してから両ファイルに対する書込み操作の回数の和を表し， は編集回数による影響の度合いを調節するためのパラメータである．∆size (fi , fj ) はファイル fi ，fj 間で RMC 操作が発生してから両ファイルのサ
イズの増加分と減少分の絶対値の和で，σ はファイルサイズの(2)変化による影響の度合いを調節するためのパラメータである．
ファイル間 RMC 関連度に加え，RMC 操作があってからの

ただし，Tm と Tn はタスク A とタスク B に含まれるファイル

経過時間，編集回数，そしてファイルサイズの増減による関連の集合を表す．

度の減衰を考慮し，タスク間 RMC 関連度を下記の式 (7) に

3. 2. 2 タスク間 RMC 関連度
過去の作業で使用されたファイルをコピーなどをして，他のよって算出する．

rmct (Tm → Tn )作業で再利用することがよくある．そのため，RMC 操作のあったタスク間では他より関連が強いと思われる．そこで，タスク
間 RMC 関連度を算出するためのファイル間 RMC 関連度を式(3) で定義する．

=∑{rmcf (fi → fj )(7)

(fi ,fj )∈(Tm ,Tn )∗ T (fi , fj ) ∗ E(fi , fj ) ∗ S(fi , fj )}3. 3 キーワード検索の実現
本稿では，キーワードに関連するファイルを直接検索するだ
けではなく，タスク間関連度を用いて，キーワードに関連するタスクを探すことによって，キーワードを含まない関連ファイルの検索を実現する．以下においてキーワードによるファイル
検索の処理手順を記述する．

STEP 1: 既存の全文検索エンジンを用いて，キーワード qて，記録された IP アドレスからアクセス元のマシンを割り出を含むファイルを特定する．その際，全文検索エンジンによっ

し，使用したユーザを特定する．

てキーワードに対するファイルのスコアが算出される．我々は（ 2 ） 移動・コピー操作の検出： 移動操作は，改名として

全文検索エンジンが tf.idf 法 [14] に基づいて付けられたファイログに記録されているため，ここではディレクトリの変更を伴

ルスコア scoref (q, fj ) を利用して，そのファイルが所属する

なう改名操作を移動とする．またコピー操作に関しては，分単

タスク Tm のタスクスコアの初期値 score0t (q, Tm ) を算出する

位で区切った一連のファイルアクセスログの中，あるファイル(式 (8))．

f に対する新規作成操作の前，他のディレクトリにある同名の∑score0t (q, Tm ) =ファイル f 0 に対する参照操作が記録されていたら，f は f 0 のscoref (q, fj )(8)

fj ∈Tm

コピーとする．
（ 3 ） 対象外アクセスの除去： 収集されたファイルアクセス

STEP 2: タスク間関連度を用いて，キーワードに関連すログの中には，アプリケーションなどによる機械アクセスや直るタスクを検索するための処理を行う．本稿では Connec-

接作業に関係のないアクセスが多く含まれている．機械アクセ

tions や FRIDAL で用いられた関連度算出方法をベースに，スの例として，ファイルの編集や検索によって生成されたテン

タスク間関連度に基づき，全タスクに対して，タスクスコア

ポラリファイルへのアクセスや，プレビューの表示によるアクscorekt (q, Tm )(1 <=k<= K) を伝搬させる処理を K 回繰り返す．

セスなどがある．また，バックアップやプログラムのコンパイ

scorekt (q, Tm ) は式 (9) に従って算出される．

ルで発生するファイルアクセスは直接作業に関係のないファイ
ルアクセスの一例である．そこで，２種類のスレッショルドをscorekt (q, Tm ) = scorek−1(q, Tm )t+∑scorek−1(q, Tn ) ∗ R(Tn → Tm )t

(9)

Tn ∈InLink(Tm )用いて機械アクセスを除去する．

•

T Hmin：一分間におけるアクセス回数の上限値•

T Hsec：一秒間におけるアクセス回数の上限値

ただし，InLink(Tm ) は Tm に対するタスク関連度 R(Tn →その他に拡張子を用いたフィルタリングも行う．本稿では，拡Tm ) > 0 となる Tn の集合を表す．

張子が.db，.dll，.ico，.ini，.class などのファイルを対象外とSTEP 3: タ ス ク ス コ ア の 値 を 正 規 化 し ，ス コ アする．そのほかに，フォルダへのアクセスもログに含まれるが，scoreKt (q, Tm ) > T Hscore を満たす全ての Tm をキーワードに

本稿ではキーワードに関連するファイルを検索することが目的

対する検索結果として出力する．

のため，フォルダへのアクセスも除去対象とする．

4. 評 価 実 験
タスクとタスク間関連度を用いたキーワード検索方式の性能を確認するために実験を行う．

4. 1. 2 全 文 検 索
キーワード検索では，全文検索エンジンである Hyper Es-

traier [16] を使用している．Hyper Estraier は N-gram 方式による検索が可能で，インデックスを使って高速に大量の文章を検

4. 1 実 験 環 境

索できる．実験では設定により，プレーンテキスト，HTML の4. 1. 1 ファイルアクセスログ

ほかに，拡張子が.pdf，.doc，.xls，.ppt，.docx，.xlsx，.pptx

評価実験を行うため，我々の研究グループが日常的に使用してのファイルを検索対象にした．

いる共有ファイルサーバ（Windows Server 2003 SP2, NTFS）

4. 2 実 験 方 法にアクセス監視を目的としたツール FAccLog [15] をインストー

実験では，7 名の被験者の協力を得てアクセスログに記録さルし，サーバへのファイルアクセスをモニタリングする．アクれたファイルの中から，キーワードに関連するファイルを選出

セスのモニタリングは OS からの情報収集と LAN アダプタかして正解集合を作成する．評価では正解集合と比較して行ってらアクセス情報を基に行うという．ログ収集はほぼリアルタイ

いる．なお，本稿執筆の時点でファイルシステムから削除されムで行うことができ，ログにはアクセスした時間，クライアンたファイルは評価対象外とする．実験用データセットの概要を

トのユーザ名または使用されたマシンの名前，アクセス元の IP

表 1 にまとめた．表中「全文」とは Hyper Estraier によってアドレス，アクセスしたファイルのフルパス，およびファイル

索引が抽出できたファイルの数で，ファイル数の半分にも満たに対する操作，ファイルサイズなどの情報が含まれている．記ないケースが多いことが分かる．ただし，被験者 E, F, G に関録されるファイル操作は参照，書込，新規作成，削除，改名のしてはプライバシーの理由で一部のファイルに対してのみイン

５種類である．また，改名の場合では，パスは「改名前のパス

デクシングを行った．

 改名後のパス」の形で記録される．

固定したパラメータとして，ログクリーニングでは T Hmin =このように集めたファイルアクセスログの多くはユーザ名が30，T Hsec = 5 とし，関連ファイル検索におけるスコアの閾値記録されておらず，移動とコピーの情報も含まれていない．まを T Hscore = 0 に設定した．また，スコア伝搬の繰り返し回数

た，機械アクセスや対象外のファイルに対するアクセスが含ま

K = 3 とした．

れている．そこでログクリーニングによって手法適用に必要な情報を補完・検出し，不要なアクセスを除去する．
（ 1 ） ユーザ名の補完： ユーザ名が欠如しているログに対し

4. 3 タスクマイニングに関する実験
本稿では，キーワード検索では探せないファイルを検索可能にするため，アクセスログに基づき，同一作業に関連するファ表1
被験者 ログ数

実験用データセット

ファイル

全文

キーワード

正解数

A

3591

201

137

デスクトップ検索

70

B

2808

416

113

日本支部

25

C

3424

318

276

RAPoSDA

32

D

5911

764

311

XCP

84

E

8203

642

335

語学番組

244

F

5123

3422 1152

MTTDL

227

G

13102

3258

338 video slide keyword

73

表 2 FI タスクの実験結果

TransactionTime [秒]

900

1800

3600

5400

7200

MinSuppCnt=2 [F 値] 0.543 0.513 0.507 0.470 0.506
図 4 FI タスクの実験結果

MinSuppCnt=3 [F 値] 0.452 0.432 0.450 0.411 0.453

表 3 RMC タスクの実験

イルをタスクとして抽出し，同じタスクにあるファイルを同

RMCTaskTime [秒]等に扱っている．そこでまずタスクマイニング用パラメータ

適合率

0.776 0.758 0.762 0.762 0.756

再現率

0.669 0.674 0.673 0.675 0.684

F値

0.684 0.681 0.679 0.684 0.684

T ransactionT ime, M inSuppCnt, RM CT askT ime の値を決めるために実験を行う．なお，タスク間関連度算出用パラメー
タは下記の値に設定した．θ = 0.5, (α1 , α2 , β1 , β2 , γ1 , γ2 ) =

表4

60

180

300

600

ファイル間 RMC 関連度に関する実験の構成(1.0, 1.0, 1.0, 1.0, 1.0, 1.0), (τ, , σ) = (0.0, 0.0, 0.0)．

移動

コピー

4. 3. 1 FI タスク抽出用パラメータの選定

実験構成

α1

α2

β1

β2

γ1

γ2

FI タスクの抽出に用いる T ransactionT ime，M inSuppCnt

RMC なし

0

0

0

0

0

0

の 値 を 決 め る た め ，FI タ ス ク の み を 検 索 対 象 と

改名

1

1

0

0

0

0

し，T ransactionT ime = {900, 1800, 3600, 5400, 7200} [秒],

移動

0

0

1

1

0

0

コピー

0

0

0

0

1

1

RMC 考慮

1

1

1

1

1

1

M inSuppCnt = {2, 3} の組み合わせで実験を行った．

1800

改名

被験者全員の F 値の平均を表 2 に示すように，T ransactionT ime が同じの場合，M inSuppCnt = 2 のほうが M inSuppCnt = 3 より良い性能を示している．それは

M inSuppCnt を上げることで，タスクに属さないファイル数が増え，タスク間関連度でも辿り着けないファイルが多くなったことが原因だと考えられる．また，T ransactionT ime の増大により，F 値に低下傾向が見られたが，M inSuppCnt ほどの影響はなかった．その原因は T ransactionT ime が増えることにより，使用時間に多少の間隔があっても同じトランザクショ
ンに入ることができ，他のファイルと関連付けやすくなるが，T ransactionT ime 内における複数回のアクセスが 1 度としかカウントされないため，M inSuppCnt を満たさなくなる可能性が大きくなるからである．
被験者別の実験結果の詳細を省略するが，解析の結果被験者

A, B, E では T ransactionT ime = 3600 において高い F 値を示し，被験者 C, D, F, G では T ransactionT ime = 900 での良い性能を示している．このことから被験者の作業パターンの違いが推測でき，以降の実験ではそれぞれ異なる T ransactionT ime
を使用して実験を行う．

4. 3. 2 RMC タスク抽出用パラメータの選定
RMC タ ス ク の 抽 出 に 用 い る RM CT askT ime の 値 を 決
め る た め に FI タ ス ク に 加 え ，RM CT askT ime = {60，180, 300, 600, 1800}[秒] の時に抽出された RMC タスクを用いて検索を行った．
表 3 で実験結果を示しているように，RM CT askT ime の増加によって再現率が上昇していくものの，適合率がわずかに低下した．RMC タスクを抽出することで関係のないファイ
ル同士が近い時間に RMC されたことにより，同一作業に関連するものとされてしまうことによる適合率の低下が原因である．しかし，RMC 操作は頻繁に行われていないため，その影響が小さくて F 値の変化が少ない．また，以降の実験ではRM CT askT ime = 60 に設定する．
4. 4 タスク間関連度に関する実験
タスク関連度の算出において多くのパラメータを使用している．各パラメータの特性を調べるために実験を行った．

4. 4. 1 タスク間 RMC 関連度に関する実験
タスク間関連度の算出に用いるタスク間 RMC 関連度 (式(7)) は RMC 操作の種類と向きを考慮したファイル間 RMC 関
連度を用いている．ここでは，タスク間 RMC 関連度の算出に関わるパラメータの適切な値を調べるために実験を行う．
ファイル間 RMC 関連度は式 (3) によって定義されており，ファイル間 RMC 操作の種類と向きを区別するために α1 ，α2 ，β1 ，β2 ，γ1 ，γ2 の 6 つのパラメータを使用している．実験では，(α1 , α2 , β1 , β2 , γ1 , γ2 ) を表 4 の構成で行った．
実験結果を図 5 にて示している．今回実験で使用したデータセットでは RMC のうち改名と移動の効果があまり見られな
かった．改名，移動したファイルはファイルシステムに存在しないため，評価対象でないことや，ファイルに対する改名と移

表6

実験構成

実験構成

タスクマイニング タスク間関連度

SUGOI 構成１

FI タスクのみ使用 類似度のみ使用

SUGOI 構成２FI タスクのみ使用

類似度＋ RMCSUGOI 構成３ FI タスク＋ RMC タスク 類似度のみ使用
SUGOI 構成４ FI タスク＋ RMC タスク
表7

図5

ファイル間 RMC 関連度に関する実験の結果

類似度＋ RMC

実験結果

実験構成

適合率

再現率

全文検索のみ0.795

0.273 0.392

F値

SUGOI 構成１0.820

0.500 0.606

SUGOI 構成２0.820

0.500 0.306

SUGOI 構成３

0.784

0.638 0.668

SUGOI 構成４

0.776

0.669 0.684

4. 5 キーワード検索に関する実験
本稿ではタスクマイニングとタスク関連度の算出において

RMC 操作を考慮している．タスクマイニングでは，頻出ファ
イル集合のほかに近い時間に RMC されたファイルをタスクとして抽出する．また，タスク間関連度の算出では，タスク間類
似度のほかに RMC 操作を考慮したタスク間 RMC 関連度を用いている．RMC 操作を考慮したことによる結果が改善を確認するため，全文検索のみの場合のほかに，検索に用いるタスクの種類とタスク関連度を組み合わせた表 6 で示す４つの構成での検索結果を用いて比較を行った．ただし，タスク間 RMC 関
連度を用いる場合のパラメータは θ = 0.5 に設定し，タスク間
図 6 θ に関する実験結果

類似度のみ用いる場合では θ = 1.0 とした．
実験結果を図 7 で示すように，RMC 操作を考慮することで表 5 θ による点平均適合率の推移

1.0

検索結果は全文検索より再現率と F 値が改善したことが確認さ

11 点平均適合率 0.430 0.482 0.482 0.476 0.476 0.475

れた．その理由として，ファイルアクセスログを考慮することの平均値

で，キーワードを含まないファイルが，キーワードを含むファ

θ

0.0

0.2

0.4

0.6

0.8

イルと同じタスクまたはその関連するタスクに入っていたこと
動操作が少なかったこともその一因である．また，コピー操作が挙げられる．特に RMC 操作を考慮してタスクを抽出したこを考慮したことで再現率と F 値の改善につながった．

と（SUGOI 構成３，SUGOI 構成４）による再現率の改善が大4. 4. 2 θ に関する実験

きく，全文検索のみ用いたとき（0.273）よりも 0.3 以上上昇し

タスク間関連度を算出する際に，タスク間類似度とタスた (表 7)．その理由は，RMC 操作に基づいて抽出されたタス

ク間 RMC 関連度を使用し，パラメータ θ で重要視する指クには，キーワードに関係のないファイルよりも，多くの関連標を調節している．θ による検索結果の変化を調べるためファイルが含まれていたことが考えられる．また，適合率低下に，θ = {0.0, 0.2, 0.4, 0.6, 0.8, 1.0} に設定した時の 11 点平に関しては，近い時間に RMC されたファイルを RMC タスク

均適合率の平均値で評価を行った．ただし，その他のパラとして抽出したことで，無関係なファイルがわずかに混入したメータは (α1 , α2 , β1 , β2 , γ1 , γ2 ) = (1.0, 1.0, 1.0, 1.0, 1.0, 1.0)，と思われる．

(τ, , σ) = (0.0, 0.0, 0.0) に設定した．

タスクマイニング及びタスク間関連度の算出で RMC 操作

図 6 から分かるように，θ = 0.0 以外の場合におけるランキを考慮した SUGOI 構成４では，再現率と F 値が最も高い値

ング結果が優れているが，θ による影響が少なかった．それはとなった．その理由は RMC 操作を考慮したことにより，キー提案手法では他のタスクと密な関連にあるタスクが上位にラワードを含むファイルがなくて類似度だけでは見つからなかっ

ンキングされやすくため，タスク間関連度が多少変動してもたタスクにもスコアが配分されたと考えられる．

その性質により多くのスコアが付くためだと思われる．また，

4. 6 実験のまとめ

θ = {0.2, 0.4} では最も高い 11 点平均適合率の平均値を得られ4. 節において被験者実験により，提案手法 SUGOI の有効性

た (表 5)．θ = 0.0 における性能が低かった原因として RMC 操を確認し，パラメータの特性を調べ，以下の結論が得られた．

作が少なかったため，タスク間 RMC 関連度だけ使用しては十

タスクマイニングに関する実験では，M inSuppCnt = 2

分にタスク間を関連付けることが困難であることが挙げられる．

•

における F 値が M inSuppCnt = 3 の時より高く，トランザク

検索結果の適切な提示方法

謝辞本研究の一部は，日本学術振興会科学研究費補助金基盤研究(A)(#22240005) および文部科学省科学研究費補助金特定領域
研究 (#21013017) の助成により行われた．

文

図 7 RMC 操作を考慮した効果の検証実験

ションにおける共起回数が 2 回以上あれば，関連するファイル同士である可能性が高いことが分かった．
また，RMC タスク抽出用の RM CT askT ime を増やすこと
で適合率が低下し，再現率の増加傾向が見られたが，今回使用したデータセットにおいて RMC 操作が頻繁に行われていな
かったためその影響は小さい．

•

タスク間 RMC 関連度に関する実験では，改名，移動，コピーの 3 操作のうち，コピー操作が最も有効であることが分かった．元のファイルに変更を加えることなく，他の作業で使用するという作業パターンが多いことが推測できる．
式 (1) において，タスク間類似度とタスク間 RMC 関連度を考慮する度合いを調節するためのパラメータ θ に関する実験では，θ = {0.2, 0.4} におけるランキングの精度が最も良かった
結果となった．

•

RMC 操作を考慮した効果を検証するための実験では，

RMC タスク及びタスク間 RMC 関連度を利用した構成が既存の全文検索エンジンに比べ，F 値が 0.292 上昇し，RMC 操作を考慮した提案手法 SUGOI の有効性を示した．

5. まとめと今後の課題
パソコン内の情報が急速に増加しているが，全文検索だけでは検索できないファイルが存在する．本稿では，ファイルアク
セスログに基づき，ファイルを作業ごとにまとめ，ファイルの改名・移動・コピー（RMC）操作を考慮したタスク間関連度を
タスク間の関係を量る指標とした．そして，全文検索とタスク
間関連度を組合せた検索方式を提案した．被験者実験を行い，提案手法 SUGOI によって適合率と再現率が改善したことを確認した．
今後の課題として，以下４点について検討していきたい．
（ 1 ） 長期間にわたるアクセスログを用いて評価実験を行い，ユーザのアクセスパターンに合ったパラメータの自動設定方法（ 2 ） タスク間関連度の算出式及びそれを利用したスコアリ
ング手法の改善（ 3 ） 他のリンク解析手法の利用（ 4 ） タスクマイニングとタスク間関連度の情報を活かした

献[1] Google. Google デストップ. http://desktop.google.com.
[2] Microsoft Corporation. Windows デスクトップ サーチ.
http://www.microsoft.com/japan/windows/
desktopsearch/default.mspx.
[3] Apple Inc. Spotlight. http://www.apple.com/jp/macosx/
what-is-macosx/spotlight.html.
[4] Craig A. N. Soules and Gregory R. Ganger. Connections:using context to enhance file search. SIGOPS Oper. Syst.
Rev., Vol. 39, No. 5, pp. 119–132, 2005.
[5] 渡部徹太郎, 小林隆志, 横田治夫. ファイル検索におけるアクセ
スログから抽出した関連度の利用. 電子情報通信学会技術研究報
告. DE, データ工学, Vol. 107, No. 131, pp. 503–508, 2007.
[6] 渡部徹太郎, 小林隆志, 横田治夫. キーワード非含有ファイルを検索可能とするファイル間関連度を用いた検索手法の評価. 第19 回データ工学ワークショップ (DEWS2008), 2008.
[7] Tetsutaro Watanabe, Takashi Kobayashi, and Haruo
Yokota. A method for searching keyword-lacking files basedon interfile relationships. In OTM ’08, pp. 14–15, Berlin,
Heidelberg, 2008. Springer-Verlag.
[8] 呉怡, 渡辺陽介, 横田治夫. ファイル RMC 操作を考慮した関連
ファイルの発見. 第 150 回 データベースシステム研究発表会,
第 2010-DBS-150 巻, 2010.
[9] Jidong Chen, Hang Guo, Wentao Wu, and Wei Wang. iMecho: an associative memory based desktop search system.
In CIKM ’09: Proceeding of the 18th ACM conference on
Information and knowledge management, pp. 731–740, New
York, NY, USA, 2009. ACM.
[10] Larry Page, Sergey Brin, R. Motwani, and T. Winograd.
The pagerank citation ranking: Bringing order to the web.
Technical report, Stanford University, 1998.
[11] 小田切健一, 渡辺陽介, 横田治夫. 頻出ファイル集合のアクセス時間を考慮した仮想ディレクトリ生成手法. 第 2 回データ工学と情報マネジメントに関するフォーラム (DEIM2010), 2010.
[12] Rakesh Agrawal, Tomasz Imieliński, and Arun Swami.
Mining association rules between sets of items in large
databases. SIGMOD Rec., Vol. 22, No. 2, pp. 207–216,
1993.
[13] Mohammed J Zaki, Srinivasan Parthasarathy, Mitsunori
Ogihara, and Wei Li. New algorithms for fast discovery
of association rules. In KDD-97 Proceedings, pp. 283–286,
1997.
[14] Gerald Salton, editor. Automatic text processing. AddisonWesley Longman Publishing Co., Inc., 1988.
[15] だいこくネット. FAccLog. http://www2s.biglobe.ne.jp/
˜masa-nak/fal down.htm.
[16] Mikio Hirabayashi. Hyper estraier. http://fallabs.com/
hyperestraier/.