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

頻出ファイル集合のアクセス時間を考慮した仮想ディレクトリ生成手法

Title(English)

Virtual Directory Creation Considering Access-times in Frequent
Accessed File Sets

著者(和文)

小田切健一, 渡辺陽介, 横田治夫

Authors(English)

Kenichi Otagiri, Yousuke Watanabe, Haruo Yokota

出典(和文)

DEIM Forum 2010 F9-2, , ,Citation(English)

DEIM Forum 2010 F9-2, , ,

発行日 / Pub. date2010, 3

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2010 F9-2

頻出ファイル集合のアクセス時間を考慮した仮想ディレクトリ生成手法(O)
小田切健一†

渡辺 陽介††

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

近年、ストレージが進歩し、使用したファイル全てを保存しておくことが現実的になった。しかし、大量のファイルの中から過去の作業で用いたファイル群を発見するのは実際には困難である。特に大規模な作業はファイル数が多く複数ディレクトリにまたがっていることも多い。我々の研究グループではアクセスログの情報を利用し、複数ディレクトリに分散している同一作業で使用されたファイル群を発見し、仮想的なディレクトリとしてユーザに提示する研究を行っている。実際の一つの作業は、関係が密なファイル群が複数組み合わさって成り立っている。そのため、一つの作業全体のファイルを発見するには、近い時間に頻繁に使われるファイル群を発見するだけでなく、発見された複数のファイル群を一つに結合する必要がある。本稿では、発見されたファイル群に含まれるファイルの使用時間に着目する。アクセスログに対して頻出集合発見を行い、頻出するファイルの集合を発見した後、集合内の各ファイルの使用時間が重複している集合同士を結合することにより仮想ディレクトリの生成を行う。本稿では手法の詳しい解説と実データを用いた比較実験・考察を行う。
キーワード

ファイル管理, アクセス履歴, アプリオリアルゴリズム, クラスタリング, 情報爆発, 仮想ディレクトリ,

ファイル間関連度, 同一作業指数

Virtual Directory Creation
Considering Access-times in Frequent Accessed File Sets
Kenichi OTAGIRI† , Yousuke WATANABE†† , and Haruo YOKOTA†,††† Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo
Institute of Technology 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, Japan†† Global Scientiﬁc Information and Computing Center, Tokyo Institute of Technology 2-12-1 Ookayama,
Meguro-ku, Tokyo 152-8552, Japan
E-mail: †{otagiri,watanabe}@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
Abstract Due to the progress of storage technologies, it becomes easy to store all of used ﬁles. But it is diﬃcult
to discover the ﬁles that related to the speciﬁc task from a large amount of ﬁles. These ﬁles sometimes disperse overmany directories. Our research group has been developing a system which rediscovers the ﬁles used in the same task
and provides virtual directories including these ﬁles. A task includes some ﬁle groups whose ﬁles are used frequently
and simultaneously. We make groups of ﬁles that are used frequently and simultaneously. Then combine ﬁle groups
that belongs to the same task to create virtual directories. This paper proposes a new method that makes groups
by apriori algorithm and combines ﬁle groups by overlaps of use-times of their ﬁles. We explain about the proposed
method and experiment using real data.
Key words ﬁle management, access log, apriori algorithm, clustering, information explosion, virtual directory,
relationship between ﬁle, same work index—1—1. は じ め に
近年のストレージの増加により、データを全てストレージに保存しておくことが容易になった。保存したデータを再利用し、次の作業を効率的に行いたいという要求が高まっている。しかし、膨大なファイル群を適切に管理する手法が確立されておらず、本来再利用できるファイルを再利用できていない事が多い。
過去の作業のデータを再利用するには、再利用に必要な全てのファイルを発見することが必要である。例えば過去に作成したプログラムを再利用しようとしても、そのプログラムに必要な

図 1 仮想ディレクトリ

データファイルやドキュメントといったものも同時に発見できなければ十分に活用することが出来ない。そのため、過去の作多く入ってしまうので、頻出集合の発見を行って一定回数以上業において使用したファイル群を発見できる手法が必要となる。

出現する組み合わせのみを抽出する。その後、一定以上重複がデスクトップ検索 [1] [2] などが普及してきているが、キーワー

ある頻出集合を結合することで仮想ディレクトリを生成する。

ド検索ではテキストを含まないファイルを発見することが出来

これにより、FI 法は Recall を向上することに成功した。しかない。また、同じ作業であっても同じキーワードを含んでいる

し、FI 法であっても全てのファイルを発見できるわけではなとは限らないため、デスクトップ検索のキーワード検索だけでく、本来一つの仮想ディレクトリになるべきものが複数の仮想

過去の作業のファイル群を発見することは困難である。そのたディレクトリに分割されてしまう事がわかった。同じ仕事に属め、ストレージに保存された大量のファイル群から過去の作業する頻出集合同士に全く要素の重複が無いことがあり、そうで使用したファイル群を発見する手法が必要となっている。

いった頻出集合同士が孤立してしまうためである。

我々の研究グループでは、一つの作業でありながら複数の

本稿では、頻出集合内のファイルの使用時間に着目した仮想ディレクトリに分散してしまったファイル群を発見し、そのファディレクトリ生成手法を提案する。ログファイルを区切りトラ

イル群を一つの仮想ディレクトリとしてユーザに提示する手法

ンザクションにし、頻出集合発見を行った後、頻出集合内の各の研究を行っている [3] [4]。ユーザは仮想ディレクトリを見る

ファイルの使用時間が重複している集合同士を結合をすることことで分散してしまった同一作業のファイル群を発見すること

により仮想ディレクトリを生成を行う。これにより、発見されができる。同じ作業に用いられたファイル群の発見には、ファた頻出集合同士に要素としての重複がない場合でも、使用時間

イルサーバのアクセスログのみを用いる。アクセスログのみをを元に同じ作業であるか判定できるようになる。この改良は使用しファイルの中身を使用しないため、以下のような利点がRecall が優れている FI 法のクラスタリングステップに時間的ある。

情報を用いる CO 法の手法を取り入れたことになる。同じ作業•

テキストを含まないファイルでも発見できる。

であっても FI 法では孤立していた頻出集合が、この手法によ•

ファイルサーバを用いている多くの組織で必要最小限のり結合されると考えられる。本論文では実データを用いて評価変更で利用できる。

•

クライアント PC に特殊な設定をする必要がない。

•

ファイルの中身をみる必要がないので、パーミッション等の問題がない。

実験を行い、CO 法・FI 法との比較実験を通して提案手法の効果の考察を行う。
本論文の構成は以下の通りである。2 節ではこれまでの仮想ディレクトリ生成手法について解説する。3 節では今回提案す

我々は今までの CO 法 [3] と FI 法 [4] という二つの手法を提る COFI 法について解説する。4 節では実データを用いた評価

案した。CO 法は Precision を重視した手法である。ファイルの実験を行う。5 節では関連論文の紹介を行う。6 節ではまとめ

使用時間が重複するファイルの組み合わせを発見し、その重複と今後の課題について述べる。

度合いをファイル間の関係の強さ（同一作業指数）とする。その情報を元に階層的クラスタリングを適用し、いくつかのファ

2. これまでの仮想ディレクトリ生成手法

イルクラスタを得る。各々のクラスタを仮想ディレクトリとし本研究では複数のディレクトリに分散した同一作業のファイてユーザに提示する。使用時間が確実に重複するファイルを発ル群を発見し、それらを仮想ディレクトリとしてユーザに提示見するので、比較的誤ったファイルが出にくい。しかし実際にすることを目的としている。例として図 1 のようにユーザが、は同じ作業で使用するファイルであっても使用時間が多少ずれ

文書・画像・動画・データの各々のディレクトリを作成してファていて重複がない場合が多い。

イルを管理していたとする。ファイルは一見整理されているよ

その問題に対処するために FI 法という手法を提案した。FI

うだが、実際には実験作業・書類作成作業といった各作業は複法ではログファイルを一定期間ごとに区切り、各々の区間をト数のディレクトリに分散している。数ヵ月後ユーザがファイル

ランザクションとする。同じトランザクションに入っていればを再利用しようとするが、配置関係を忘れてしまっているので関係があるとすることで、使用時間が重複しないが使用時間がディスク内を探索して複数のディレクトリを見つけなければな

近いファイルを発見可能にする。しかし、無関係なファイルも

らない。

—2—

図 2 CO 法の要素間の関係発見

図 3 FI 法の要素間の関係発見

本研究ではこういったファイル群を発見し、図 1 の下部のよ

重複しないケースがあった。そのため、CO 法では発見できる

うに一作業を一ディレクトリとする仮想ディレクトリを生成す

ファイルが少ないという問題があった。FI 法はログファイルをる。どのファイルが同じ作業で用いられているかという情報は、

一定時間ごとに区切り、その区間で使用があったファイルをト

ファイルサーバのアクセスログに記録された各ファイルのアク

ランザクションとする（図 3）。これにより、多少使用時間がず

セス時間から推測を行う。ファイルのコンテンツではなくアクれたファイルも同じトランザクションに入り、使用時間が重複

セス時間を用いるので、どのような種類のファイルであってもしないファイルも発見できる。しかし、これでは偶然近い時間発見できるという利点がある。ファイルサーバのログファイルに触ったファイルなどの無関係なファイルが入りやすい。そこには OPEN/CLOSE の時刻が記録されているものと、アクセで、トランザクションに対して頻出集合発見を行い、頻出する

スのタイミングのみが記録されているものがある。例として、

組み合わせのみを発見する。これにより、図 3 の偶然触った無

前者には Samba [5] のログ等があり、後者としては Windows

関係なファイル g のようなものが除去される。さらに、頻出集

Server 2003 の監査機能を用いて取得したアクセスログ等があ合を極大化して、小さな集合を除去する。その後、集合内の要る。CO 法で用いているファイル使用時間の推測では前者のロ素が類似する頻出集合同士を結合して大きなファイル集合を生グが必要だが、FI 法ではどちらのログでも使用可能である。

成し、それを仮想ディレクトリとして出力する。

我々は、今までに二つの仮想ディレクトリ生成手法を提案しファイルの使用時間を荒く見ることで多少使用時間がずれてきた。それらの概要を解説する。

たファイル同士も発見することができ、CO 法に対して Recall法を向上させることができる。しかし、類似する頻出集合同士

2. 1 COファイル使用時間の重複に基づくクラスタリング法 (CO 法：

を結合する際要素の重複を見ているので、ある作業「ファイルClustering using Overlap of ﬁle-use) [3] について解説する。

A,B,C,D,E,F」が二つの頻出集合「A,B,C」「D,E,F」として発「アクセスが重複するファイル同士は同一作業に用いられてい見された場合、この二つを結合することができないという問題る可能性が高い」という考え方に基づいて提案した手法であがある。

る。例として図 2 のようなファイル x,y,g があった場合、使用時間の重複に注目すると x と y は関係しているが g は無関係で

3. 提案手法 COFI 法

あると分かる。CO 法ではこの関係を元にファイルをノードと今回新しく提案する COFI 法（Clustering using Overlap of

してエッジの重みを重複時間とした重み付きネットワークを生

ﬁle-use time for Frequent Itemsets）の提案動機と具体的な処成し、階層的クラスタリングを適用することで結びつきの強い

理ステップについて解説する。

ファイル集合を発見し、仮想ディレクトリとして出力をする。

3. 1 動機

ファイル使用時間が比較的厳密に推測され、使用時間が本当に同じ作業のファイルは同時に使用されると考え、ログファイ

重複していたファイルのみ発見されるため理論的には Precision

ルをトランザクション化し頻出集合発見を行ってみると、発見が高くなる。しかし、実際には同じ作業で用いられていても使される頻出集合は作業の一部分であることが分かる。数十〜数用時間が重複しないファイルもあり、Recall の面で問題がある。

百ものファイルを扱う作業において、ユーザが全てのファイル

2. 2 FI

法を同時に扱うことはほぼない。そのため、発見された頻出集合

アプリオリアルゴリズムによる頻出ファイル集合発見法（FIは作業の断片であると考え、頻出集合同士を組み合わせて一つ法：Frequent Itemsets discovery of ﬁle-use）[4] について解説の作業を復元する必要がある。例として、「ファイル A,B,C,Dをする。CO 法では、使用時間が重複するファイルの関係を発と「ファイル B,C,D,E」のような頻出集合が発見されれば、こ見していた。しかし、実際の作業では関連するファイルの使用

れらは内容がほぼ同一なので同じ作業ではないかと予測が出来が前後することがあり、近い時間に使用していても使用時間がる。FI 法ではこのように要素の重複がある頻出集合同士を結—3—

3. 2 処 理 手 順
各ステップの処理内容を表した図 5 に沿って解説する。我々の提案手法は「ログクリーニング」「ログデータからファイルの使用時間の推測」「ファイル要素間の関係発見」「同一作業指数計算」「クラスタリング」というステップからなっている。

3. 2. 1 ログクリーニング
ログファイルには人のアクセスのほかに、バックアップ・自動プレビュー・ファイル検索等のユーザが意図しないアクセスが記録されている。ユーザが意図しないアクセスが含まれると手法の適応時に正しい結果が得られない。そこで、この段階でユーザが意図しないと思われるファイルアクセスを除去する。
今回は過去の報告 [4] で利用した一秒間に 4 ファイル以上の高
図 4 COFI 法の集合内ファイルの使用時間の重複図

頻度アクセスを機械アクセスとして除去する処理を行う。
また、本手法が対象としているのは、ユーザが作成・編集するファイルであり、実行ファイルや中間ファイルは対象としない。ここでフォルダ名やファイル名により不要なファイルを判別し、それらへのアクセスを除去する。

3. 2. 2 ファイル使用時間の推測
アクセスログに記録されている OPEN/CLOSE は、ファイルをすぐ閉じてしまうアプリケーション等の影響で必ずしもファイル使用時間に対応しない。また、厳密に使用時間を見て同時に使用したファイルを発見すると、極一部のファイルしか発見されない。前のファイルを閉じてから次のファイルを使うなど、ユーザがファイルを同時に使わない場合があるためである。

COFI 法ではログファイルをトランザクションという一定期間ごとに分割し、各トランザクションの中でアクセスがあった
ファイルを「そのトランザクションの中でずっと使用していた」と推測することにしている。これにより、多少使用時間がずれるファイルも同じ時間に使用していたと扱うことができる。一図 5 仮想ディレクトリ生成手順

つのトランザクションの期間は TransactionTime というパラメータで決定する。これは非常に荒い使用時間の推測に対応合して仮想ディレクトリを生成していた。しかし、「ファイルする。例として、「ファイル A: 12:13:18, 12:29:09, 15:56:09」

a,b,x,y,z」という作業が「a,b」と「x,y,z」という二つの頻出集「ファイル B: 12:05:00, 12:19:00, 19:27:08」というアクセスを合として発見されてしまうと、要素を見ただけでは同じ作業で考える。ここで TransactionTime を 30 分とすると、この処あるか判別することが出来ない。a,b が図表作成作業、x,y,z が理は次のように使用時間を推測することに対応する。「ファイ文書作成作業、のように小さな作業が組み合わさって一つの作

ル A: 12:00:00〜12:29:59, 15:30:00〜15:59:59」「ファイル B:

業を形成している場合に起こってしまう。しかし、同じ作業に

12:00:00〜12:29:59, 19:00:00〜19:29:59」

属しているので「a,b」と「x,y,z」が全く異なる時間に使われTransactionTime を大きくすることでより離れた時間で使ていたとは考えにくい。「a,b,x,y,z」全てが同時に使われた事用したファイルを発見可能になるが、より無関係ファイルも含がなくとも、図表を文書に取り入れる際などに「a と x」「b とみやすくなる。この処理は FI 法と共通で図 3 の左部分に対応z」といった組み合わせで同時に使われていたと考えられる。そする。

こで、「a,b のいずれかを使用していた時間」「x,y,z のいずれか

3. 2. 3 要素間の関係発見を使用して時間」に着目する。すると図 4 のように両方の使用

トランザクション化によりファイル使用時間を推測すると、していた時間が重複しており、これを用いて要素の重複がない

非常に多くのファイルが同一期間に使用されたことになる。使

「a,b」と「x,y,z」を統合することが出来る。このアイディアは用時間がずれたファイルも発見できるが、偶然使用したファイ

CO 法のファイルの使用時間の重複を用いる考え方に基づいてルなども多く含まれてしまう。そこで、アプリオリアルゴリズいる。

ム [6] による頻出集合の発見を行うことで、頻繁に同一期間内で使用されるファイルの組み合わせを発見する。ユーザが意図的に同時に使用するファイルと偶然同時に使用したファイルで

—4—

表1

は、その頻度に大きな差があるため、適切なサポート値を設定

実験データすることで偶然による組み合わせを除去できると考えられる。

ユーザ

サポート値は MinSup というパラメータを用いる。このパラ

ユーザ 1 2008/04/08〜2009/11/26

347,850,468

ユーザ 2 2008/08/07〜2009/11/25

1,110,478,322

メータを大きくすると、頻繁に出現した組み合わせのみを発見するため精度が上がる。小さくすると偶然使用したファイルが期間

ログサイズ (byte)

ユーザ 3 2008/06/09〜2009/12/11

769,136,350

ユーザ 4 2008/06/10〜2009/10/23

1,895,819,901

発見されやすくなり、精度が下がる。実際には低頻度でしか使用しないファイルが多いため、あまり高い MinSup を設定する

表2

正解セット

と頻出集合が出現しなくなってしまうということが分かっていユーザる。この処理は FI 法と共通で図 3 の右部分に対応する。

内容

代表的拡張子

ファイル数

セット S1

ユーザ 1 論文作成

pptx, png, tex

79

セット S2

ユーザ 1 講義課題

docx, java, png, pptx

84

セット S3

ユーザ 1 講義課題

java, pptx, tex

34

にくく、信頼性は高い。しかし、作業で使用したファイル全て

セット S4

ユーザ 2 論文作成

eps, pdf, pptx

32を同時に触ることは少なく、ここで発見された集合は「書類 X

セット S5

ユーザ 2 CGI 作成

html, pl, pm

33

作成時に必要な図表を作成する際に使用したファイル群」「書類

セット S6

ユーザ 2 発表資料

pdf, docx, txt

19

X 本体」といったより小さな単位であることが多い。そこで、

セット S7

ユーザ 3 講義課題

pptx, java, txt

5

次のステップでこのような集合同士を結合し、ユーザにとってセット S8

ユーザ 4 実験データ pptx, wmf, xlsx

24

この処理により頻繁に近い時間に使用したファイル群を発見できる。このファイル群に偶然同時に使用したファイルは入り有益な「書類 X 作成」という作業を発見する。

3. 2. 4 頻出集合内のファイルの使用時間取得法を使う。前ステップで定義した同一作業指数が最も大きい頻FI 法では単純に要素の重複がある頻出集合同士を結合して出集合同士を結合することを複数回繰り返す。同一作業指数がいた。しかし、COFI 法では頻出集合内のファイルの使用時間最も大きい組み合わせの同一作業指数が Threshold 以下になっの重複がある集合同士を結合する。頻出集合内の各ファイルのたところで処理を終了する。Threshold を小さくすることで同使用時間を調べ、その和集合を頻出集合に付加する。実際には

一作業指数の小さな頻出集合同士も結合され、Recall が高くな

使用時間はトランザクションになっているので、頻出集合内のる。Threshold を大きくすることで同一作業指数の大きな頻出

各ファイルが出現するトランザクション ID を調べ、その和集集合同士のみが結合され、Precision が高くなる。

合を頻出集合に付与する。例として、頻出集合（A,B,C）があり各ファイルが出現したトランザクション ID を「A:1,2,6,7,9」「B:1,2,4,5,6,7」「C:2,3,7,8,9」とする。この時、頻出集合には「1,2,3,4,5,6,7,8,9」というトランザクション ID が付与される。
以下、集合 A のトランザクション ID を T ranIDs(A) と表記する。

3. 2. 5 同一作業指数の計算

同一作業指数の定義は異なるが、CO 法や FI 法でも階層的クラスタリングの手順は同様である。

4. 実

験

実際のログデータとユーザに作成してもらった正解セットを用いて、CO 法・FI 法・COFI 法の比較実験を行った。

4. 1 実験データ

二つの頻出集合が同じ作業に属している可能性を「同一作業実験には Samba [5] のアクセスログを使用した。各ユーザの指数」と呼ぶ。その同一作業指数を COFI 法では頻出集合内のログデータの期間とサイズを表 1 に示す。Samba のログにはファイルの使用時間の類似度を用いて定義する。図 4 の g1 とOPEN/CLOSE が記録されており、CO 法・FI 法・COFI 法全

g2 の共起に着目した計算になっている。g1 , g2 を集合としたとてのファイル使用時間推測手法で利用可能である。

き、dice 係数を用いて以下のように定義される。

4. 2 正解セット
本研究の目的は複数のディレクトリに分散したファイル群の同一作業指数 (g1 , g2 ) = dice(T ranIDs(g1 ), T ranIDs(g2 ))2|T ranIDs(g1 ) ∩ T ranIDs(g2 )|=|T ranIDs(g1 )| + |T ranIDs(g2 )|これにより、使用時間が近いファイル群を持つ頻出集合同士が結合される。

発見である。そのため、正解セットとしても複数ディレクトリ
に分散したファイルを使用した。詳細は表 2 の通りである。正解セットには画像や数値データといったテキスト検索では発見できないファイル群も含まれている。

4. 3 評 価 方 法

FI 法では同一作業指数を頻出集合内の要素の重複度合いで正解セット内の 2 ディレクトリ以上に属するファイル群を発定義していた。CO 法では同一作業指数をファイルの使用時間見できた仮想ディレクトリの Precision・Recall・F 値を評価すの重複度合いで定義していた。今回の COFI 法では、FI 法のる。正解セット内のファイル群を含んだ仮想ディレクトリが存頻出集合を使い、同一作業指数は CO 法的な使用時間の重複を在しても、そのファイル群が全て元々一つのディレクトリに属用いている。

している場合は評価しない。例として、プログラムディレクト

3. 2. 6 クラスタリング

リとレポートディレクトリが存在する正解セットの場合、プロ本手法ではクラスタの数などがあらかじめ不明でもクラスタ

グラムのみを含んだ仮想ディレクトリは評価対象外で、プログリングを行うことが出来る階層的クラスタリング [7] という手

ラムとレポートの両方を含んだ仮想ディレクトリが評価対象

—5—

表3
手法

パラメータ

CO

0.7

FI

3600-2-0.1

3600-2-0.3

表4
手法

パラメータ

CO

0.6

FI

COFI

3600-2-0.6

手法

パラメータ

実験結果：ユーザ 3

正解セット Precision

Recall F-measure

0.368

0.177

0.239

CO

0.3

S7

0.600

0.600

0.600

S2

0.951

0.464

0.624

FI

1800-3-0.1

S7

1.00

0.600

0.750

COFI

1800-3-0.1

S7

1.00

0.600

0.750

S3

1.000

0.088

0.162

平均

0.779

0.243

0.342

S1

0.263

0.607

0.378

S2

0.829

0.405

0.544

手法

パラメータ

0.383

CO

0.4

S8

0.571

0.167

0.259

7200-3-0.4

S8

0.625

0.208

0.313

7200-2-0.4

S8

0.875

0.292

0.438

0.389

0.411

表6

平均

0.484

0.475

0.432

FI

S1

0.260

0.557

0.355

COFI

S2

0.486

0.429

0.456

S3

0.458

0.324

0.379

平均

0.402

0.436

0.397

実験結果：ユーザ 4

正解セット Precision

Recall F-measure

実験結果：ユーザ 2

正解セット Precision3600-2-0.3

Recall F-measure

S1

S3
COFI

表5

実験結果：ユーザ１正解セット Precision

Recall F-measure

S4

0.141

0.656

0.232

S5

1.000

0.333

0.500

S6

0.081

0.632

0.143

平均

0.407

0.540

0.292

S4

0.941

0.500

0.653

S5

1.000

0.212

0.350

S6

1.000

0.263

0.417

平均

0.980

0.325

0.473

S4

0.652

0.469

0.545

S5

0.813

0.394

0.531

4. 5 実 験 結 果

S6

0.889

0.421

0.571

各ユーザの実験結果を表 3,4,5,6 に示す。ユーザ 1 とユー

平均

0.785

0.428

0.549

ザ 2 は正解セットが複数あるため、表には正解セットごとの図 6 実験結果：全正解セット平均

Precisoin,Recall,F 値と平均値を示した。CO 法のパラメーとなる。複数の仮想ディレクトリにプログラムとレポートが含

タは、階層的クラスタリングの Threshold を表記している。

まれる場合は、F 値が最大の仮想ディレクトリを選択して評価

FI 法と COFI 法のパラメータは、TransactionTime-MinSup-する。

Threshold の順に表記している。さらに、全正解セットにおけ4. 4 最適パラメータの探索方法
現在提案している手法ではユーザごとに最適パラメータがる平均 Precision, 平均 Recall, 平均 F 値の比較図を図 6 に示す。

4. 6 考察

異なると考えられる。そこで、各手法の最適パラメータ探索は

4. 6. 1 パラメータの考察

ユーザごとに行った。各々のパラメータの組み合わせの中で平CO 法であってもユーザごとに最適なスレッショルドの値が均 F 値が最大になるものを選択する。CO 法において探索した

異なることが分かる。また FI 法や COFI 法についても、ユーパラメータ範囲は以下の通りである。Threshold は階層的クラザごとにパラメータがかなり異なっている。これはユーザの作スタリング時のスレッショルドの値である。

業スタイルやファイルの種類により最適なパラメータが異なる事を示している。

T hreshold = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]
FI 法と COFI 法において探索したパラメータ範囲は以下の通りである。TransactionTime は 1 つのトランザクションの期間である。MinSup は頻出集合発見の際の最低サポートである。

Threshold は階層的クラスタリング時のスレッショルドの値である。

各ユーザ内で FI 法と COFI 法を比較するとかなり最適パラ
メータが似通っていることが分かる。ユーザ 4 を除き、特にTransactionTime と MinSup が同一である。FI 法と提案する
COFI 法ではクラスタリングの処理が異なるが、それ以前の処
理のパラメータである TransactionTime と MinSup は余り影響を受けないこと示している。

4. 6. 2 性 能 比 較
T ransactionT ime = [1800, 3600, 7200][sec]M inSup = [2, 3, 4]
T hreshold = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]

図 6 の全正解セットの平均に着目すると、今回提案した COFI法が今までに提案した 2 手法に対して高い F 値を出していることが分かる。結論として、COFI 法は FI 法に対して Precision
は少し落ちたものの狙い通り Recall を改善出来たといえる。
各ユーザに着目すると、FI 法や COFI 法に対して CO 法の—6—

Recall が低いことが分かる。ユーザ 2 では Recall が高く見え

方法は FRIDAL とは異なり、使用時間の厳密な重複ではなくるが、これは正解セット S4 と S6 のファイル群が同じ仮想ディ「それらのファイルが N 秒以内にアクセスされたか」といったレクトリに入ってしまうなど無関係なものが一つの仮想ディレ尺度を使用している。これは FI 法のトランザクションの考え

クトリに入りすぎた結果である。そのため Recall が高いもの方に近い。ただし、ある 2 ファイルが N 秒以内にアクセスされの Precision が非常に悪くなっている。

たか見ているだけで、FI 法のように 3 ファイル以上の組み合

各ユーザの FI 法と COFI 法を比較すると、ユーザ 1 では悪わせを発見しているわけではない。

化し、ユーザ 2,4 では改善し、ユーザ 3 では変化がないことがまた、井ノ口らの研究 [10] では、ファイルアクセスの順序や分かる。ユーザ 3 の結果は正解セットが小さすぎたせいだと考アクセスの密度に着目した尺度を提案している。これらの方式えられる。ユーザ 2,4 では Recall が上昇しており、COFI 法のも仮想ディレクトリ生成に応用可能であると考えられる。

狙い通りに FI 法では分割されたままだった頻出集合が結合さ大澤らによる俺デスク [11] では、ブラウザや Word の動作れた結果だと考えられる。ユーザ 1 の悪化については、次のよを記録し、その操作履歴をタイムライン表示することでユーザうな事が考えられる。

が「Word で企画書を作成した時に参照していた Web ページ」

ユーザ 1 の正解セットには講義課題が含まれている。同じ時といった物を検索できるようにしている。イベントの共起をタ

期に複数の課題が集中するため、別々の講義課題が極めて近い

イムラインで表示するが、本研究のように自動で同時に使った時間に行われる。頻出集合発見時には低頻度の組み合わせが除ファイルを集約する機能がない点が異なる。

去されるため、正しいファイル集合が見つかる。課題 A と課

ファイル検索ではなくファイル整理という観点に立った研究

題 B の頻出集合同士は近い時間に行われていても、要素としてとして、Giﬀord らによる Semantic File Systems [12] がある。

は重複がない。従来の FI 法では要素の重複のある頻出集合同

このシステムは各ファイルから属性を抽出し、その属性を用い士が結合されるため、違う課題の頻出同士が結合される事は無て管理をするファイルシステムを提案している。しかし、属性

い。しかし、COFI 法では使用時間の近さで結合するため、課を抽出するためにファイルタイプごとに属性抽出プログラムを

題 A と課題 B に要素の重複がなくとも使用時間が重なってい書く必要があり、ファイル形式に依存しない本研究と異なる。

るため結合されてしまう。これにより Precision が下がってし

暦本は Time Machine Computing [13] を提案している。ファまった。本来 Recall は FI 法より高かったのだが、高い Recall

イルは全てデスクトップに置かれ時間とともに消えていくシスを出すときの Precision が悪いので最大 F 値で選択したところ

テムを提案している。ファイルを探したい場合は、過去のデス

FI 法より低い Recall が最適値になってしまっている。

クトップに遡ってそのときデスクトップに置かれていたファイ

このように、COFI 法は Recall の向上を実現できる場合もあル群と一緒に発見できる。時間の概念を利用している点では本るが、同時に複数の作業を行ったログでは悪化するということ研究と近いが、ユーザが明示的にファイルをデスクトップに置が言える。

く必要がある点と、本研究のディレクトリのような明確な分類

5. 関 連 研 究を行わない点が異なっている。
また、アクセスログのマイニングとしては、Web アクセスロ

ファイルを検索するシステムとしてはデスクトップ検索 [1] [2]

グを利用したリコメンデーション [14] などが関連する。これらが有名である。しかし、デスクトップ検索システムはファイルの成果を利用しファイルのリコメンデーションができれば有用に含まれるテキストにするキーワード検索を用いるため、テキである。しかし、Web アクセスログでは性質も異なり、そのまストが含まれないファイルは探すことができないという問題がま応用するのは難しいと考えられる。

ある。また、同じ作業に属するファイルであってもソースコー
ド・レポート・実験データ等で含まれるテキストは異なるため

6. まとめと今後の課題

共通のキーワードで全種類のファイルを探し出すことは難しい。

本論文では、アクセスログを用いて複数ディレクトリに分散

デスクトップ検索システムの改良として提案された手法としした同一作業に属するファイル群を発見する新しい手法を提案て渡部らの FRIDAL [8] がある。この手法ではキーワードでテした。アクセスログを用いて近い時間に頻繁に使われるファイ

キストを含むファイルを発見した後、テキスト検索で発見した

ル集合を発見すると、それらは一つの作業内のよく使われる組

ファイル群に更にそれらと関連する別のファイル群も検索結果

み合わせに過ぎず、一つの作業全体のファイルを発見するために含めて結果出力する。この関連ファイルの発見は、ファイルにはそのファイル集合を結合する必要があった。しかし、同じを同時に使用したという情報を使っている。これによりキー作業に属していても発見されたファイル集合同士に要素としてワードを含まないファイルであっても、キーワードで間接的に重複がないことがあり、これまでの要素の重複があるファイル

検索可能になる。CO 法はこのシステムの同時に使用したファ集合同士を結合する手法だけでは不十分であった。そこで、本イル群を発見する仕組みを利用している。

論文では発見されたファイル集合内の各ファイルの使用時間にSoules らによる Connections [9] も、同様のデスクトップ検

着目してファイル集合同士を結合する仮想ディレクトリ生成手

索の拡張である。テキスト検索の結果ファイル群と関連する法を提案した。実データを用いた実験を通して、実際に Recall

ファイル群も出力に含めることでキーワードを含まないファイが向上することを確認した。しかし、同時に複数の作業を行う

ルを検索可能にする。しかし、ファイル同士の関連を発見する

ユーザでは結果が悪化することがわかり、この手法が有効な作—7—

業タイプと有効でない作業タイプがあることが分かった。
今後の課題として、同時に複数の作業を行うユーザに対応できる手法の提案、より多様な正解セットによる評価、パラメー
タの自動設定方法、計算量・メモリ削減のための頻出集合発見の近似アルゴリズム採用などがあげられる。

謝

辞本研究の一部は文部科学省科学研究費補助金特定領域研究(#21013017) の助成により行われた。
文

献[1] Google デスクトップ. http://desktop.google.co.jp/.
[2] Windows デスクトップサーチ. http://www.microsoft.com/jap
an/windows/desktopsearch/default.mspx.
[3] 小田切健一, 渡辺陽介, 横田治夫. アクセス履歴を用いたユーザの作業に対応する仮想ディレクトリの生成, 2009. 第 1 回データ
工学と情報マネジメントに関するフォーラム（DEIM2009）.
[4] 小田切健一, 渡辺陽介, 横田治夫. ユーザ作業を反映する仮想ディ
レクトリ生成のためのアクセス履歴解析手法, 2009. 第 148 回
データベースシステム・第 95 回 情報学基礎 合同研究発表会.
[5] Samba. http://us3.samba.org/samba/.
[6] Rakesh Agrawal, Tomasz Imieliński, and Arun Swami.
Mining association rules between sets of items in large
databases. In SIGMOD ’93: Proceedings of the 1993 ACM
SIGMOD international conference on Management of data,
pp. 207–216, New York, NY, USA, 1993. ACM.
[7] 新納浩幸. R で学ぶクラスタ解析. オーム社, 2007.
[8] 渡部徹太郎, 小林隆志, 横田治夫. キーワード非含有ファイルを検索可能とするファイル間関連度を用いた検索手法の評価, 2008.
第 19 回データ工学ワークショップ (DEWS2008).
[9] Craig A. N. Soules and Gregory R. Ganger. Connections:using context to enhance ﬁle search. SIGOPS Oper. Syst.
Rev., Vol. 39, No. 5, pp. 119–132, 2005.
[10] 井ノ口伸人, 吉川正俊. アクセス履歴を考慮したファイル間の関連度を用いたデスクトップ検索 (履歴応用, 夏のデータベー
スワークショップ dbws 2006). 情報処理学会研究報告. データ
ベース・システム研究会報告, Vol. 2006, No. 77, pp. 141–146,
20060712.
[11] 大澤亮, 高汐一紀, 徳田英幸. 俺デスク:ユーザ操作履歴に基づく
情報想起支援ツール, 2006. 第 47 回プログラミング・シンポジ
ウム報告集，pp.15-21.
[12] David K. Giﬀord, Pierre Jouvelot, Mark A. Sheldon,
James W. O’Toole. Semantic File Systems, 1991. 13th
ACM Symposium on Operating Systems Principles.
[13] Jun Rekimoto. Time-machine computing: a time-centric
approach for the information environment. In UIST ’99:
Proceedings of the 12th annual ACM symposium on Userinterface software and technology, pp. 45–54, New York,NY, USA, 1999. ACM.
[14] B. Mobasher, H. Dai, T. Luo, and M. Nakagawa. Eﬀective
perssonalization based on association rule discovery fromweb usage data. In Proc. 3rd Intl. Workshop on Web information and data management, 2001.

—8—