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

ファイル検索に向けたアクセスログからのファイル間関連度の導出

Title(English)

Inter-file Relationship Derivation from Access Logs to Search for Files

著者(和文)

渡部 徹太郎, 小林 隆志, 横田 治夫

Authors(English)

Tetsutaro WATANABE Takashi KOBAYASHI Haruo YOKOTA, takashi
kobayashi, HARUO YOKOTA

出典(和文)

日本データベース学会Letters, Vol. 6, No. 2, pp. 65-68

Citation(English)

DBSJ Letters, Vol. 6, No. 2, pp. 65-68

発行日 / Pub. date2007, 9

権利情報 / Copyright

本著作物の著作権は日本データベース学会に帰属します。
Copyright (c) 2007 Database Society of Japan, DBSJ.

Powered by T2R2 (Science Tokyo Research Repository)

論文

DBSJ Letters Vol.6, No.2

ファイル検索に向けたアクセスログ
からのファイル間関連度の導出


Inter-ﬁle Relationship Derivation fromAccess Logs to Search for Files

渡部 徹太郎
横田 治夫 ♠♥

Tetsutaro WATANABE
Haruo YOKOTA

小林 隆志

433228 3 945

♦





図 1 本研究で提案するファイル検索の方法の例

Takashi KOBAYASHI

Fig. 1 An example of our search method

られてきた．しかし，全文検索ではキーワードを含まないファイ急速に増え続けるファイルに対して，デスクトップサーチなどルは，キーワードと関連があっても検索できないという問題点がのキーワード検索型の検索手段が用いられるようになってきてある．例えば論文ファイルは，その論文のタイトルや提案していいるが，ファイルにキーワードを含まない画像ファイルやデータる手法名で検索できるが，その論文中の図の画像ファイルや実験ファイルなどを見つけ出すことはできない．本稿では，キーワーで用いたデータファイルは，その論文と関連があるが，テキストドを含まないファイルも検索できるように，同時アクセスされるファイルではないため検索できない．しかしこのようなファイルファイル間の関連性を利用することを想定し，ファイルサーバのを検索したいという要求は高い．この要求に対し，画像に対するアクセスログから数値化した関連度を導出する方法を提案する．

キーワード検索では Google Image Search [6] が提案されていさらに，被験者実験により導出された関連度が，もともとのファるが，ファイルシステム内のファイルには画像参照情報が無い場イル間の関連性を反映していることを確認する．

合が多く適用できない．
本稿では全文検索できないファイル群に対して，キーワード検

Keyword based search functions like the desktop search have been used for ﬁles increased rapidly.
However, these functions are ineﬀective for ﬁles including no keyword, such as picture ﬁles or data ﬁles.
In this paper, we propose a method of deriving therelationship value from access logs of a ﬁle server
to enable search for ﬁles including no keyword using
the relationship. We also evaluate how the derived
values reﬂect the original relationship between ﬁles.

索を行うために必要なファイル間関連度を算出する手法を提案する．また，関連度算出の実装を行い，被験者実験により導出された関連度が，もともとのファイル間の関連性を反映していることを確認する．

2.

提案するファイル検索方法の概要

本研究では全文検索できないファイル群に対してキーワード検索を行う為に，準備としてファイルシステム内のファイルに対してファイル間関連度を数値化し格納する．キーワード検索要求が来た際は，まずキーワードで全文検索を行い，その結果と関連度

1.

はじめに近年，ファイルシステム内のファイルの数，サイズ共に爆発的の高いファイル群を検索結果に添えて提示する．これにより，全文検索できないファイル群に対してもキーワード検索を実現できる (図 1 参照)．に増加している [1]．増え続けるファイルに対して既存のファイ
ルシステムではディレクトリ階層構造が提供されているが，膨大3.

アクセスログを利用した関連度の抽出なファイル群に対して適切にディレクトリ階層を構成することは前節で説明したファイル検索を実現するためのファイル間関連難しい．また，全てのファイルが適切にディレクトリ階層に格納度として，本研究では頻繁に同時に使うファイル群に着目した．

されていたとしても，ファイル名が不適切であったり，ファイルコンピュータ上である作業をする際，関連するファイルを同時にが深い階層に格納されていた場合，ディレクトリ構造を辿るだけ開いて，参照しながら，あるいは必要な部分をカットアンドペー

では欲しいファイルを探すのは困難である．

ストしながら進めることが多い．このような場合，作業毎に使そ の よ う な 背 景 か ら ，ファイ ル シ ス テ ム に 対 し て 全 文 検用するファイル群は類似するため，頻繁に同時に使われるファイ索 を 提 供 す る ，Google Desktop[2]， Windows Desktop[3]，ル群は関連が高いと考えられる．本研究ではこのようなファイル

Spotlight[4]，Namazu[5] を利用したファイル検索などが用い群を求めるために，ファイルサーバのアクセスログからユーザのファイル使用情報を抽出する．

♥学生会員 東京工業大学大学院情報理工学研究科計算工学専
攻 tetsu@de.cs.titech.ac.jp♦正 会 員 名 古 屋 大 学 大 学 院 情 報 科 学 研 究 科
♠

1

3.1

ファイル使用情報の抽出

本研究ではファイルサーバのアクセスログからそれぞれのユー

tkobaya@is.nagoya-u.ac.jp

ザ毎にファイルのオープン／クローズの情報を取得し，ファイル正会員 東京工業大学学術国際情報センター, 東京工業大学大学院情報理工学研究科計算工学専攻 yokota@cs.titech.ac.jp毎の使用時間情報を抽出する．基本的にはファイルのオープン時刻からクローズ時刻までをファイル使用時間とするのだが，対象

日本データベース学会 Letters Vol.6, No.2

論文

DBSJ Letters Vol.6, No.2

     Ta Tb

B2

図 2 問題 (B) への対処

2 Access

modiﬁcation

B1

A2
  
Fig.

A1

duration

dealingwiththe problem (B)図 3 問題 (C) への対処

Fig.

3 Access

modiﬁcation

duration

dealingwiththe problem (C)

図 4 共起の例

Fig. 4 An example of theduration of the simultaneous

図 5 使用開始時間の類似度の考慮

Fig.

5 Consideration

accesses

を Windows に限定し，Samba を利用したファイルサーバのア

p1

z1

クセスログを解析した結果，オープン／クローズと実際のファイ

t1

fC(f)

   d12

ル使用が異なる以下の問題があることが分かった．

p2z2p3A) いくつかの理由で，あるオープンに対するクローズが取れ

t2d23
z3

t3

kず，正確な使用時間が計算できない場合がある．

B) ユーザはファイルを開いたまま席を立つ場合がある．
C) ファイルをロックをするアプリケーションとメモリに読み込んで，ファイルのロックを開放してしまうアプリケーションがあり，後者の場合はオープン／クローズが実際のファイルの使用時間と一致しない．

ofopen-timing similarity

図6

関連度計算で用いる変数

Fig. 6 Variables for calculating the relationship degree

図7

f100502 010=G(f )51

ユーザによる採点の例

Fig. 7 An example of ratings by a user

本研究では，これらの問題に対し，以下のように対処することで，実際のファイル使用時間に近づける方法を提案する．

(A) への対処は，ログを先頭から探索していき，オープンを見め，関連度の大小関係を考慮する上で以下の 4 つのルールを導入した．

つけたら，対応するクローズを再帰的に探す．対象のログの末尾

ルール 1 共起時間の累計が長いほど関連度が高い．

まで対応するクローズが発見できない場合は，そのオープンの直ルール 2 共起回数が多いほど関連度が高い ．

後にクローズを補完する．(B)，(C) への対処のために，まず以ルール 3 共起の間隔が離れているほど関連度が高い．

下の情報をアクセスログから抽出する．

ルール 4 ファイル使用開始パターンが類似しているほど関連度ア) ユーザの活動時間:

ユーザのアクセスログから Ta の間隔でログの有無を調べ，ログがあれば活動していたと見做し，活動の有無を時系列でリストにしたもの．
イ) 直ぐに閉じてしまうファイルタイプのリスト:が高い．
これらのルールについて例を挙げて説明する．ルール 1，ルール 2，ルール 3 に関して，ファイル使用時間表が図 4 の様になっアクセスログている場合，ファイル使用時間表の重なっている部分を「共起」から拡張子別にファイル使用時間の平均を調べ，平均が Tcと呼び，この例では共起時間の累計が 100 分であり共起回数が以下のファイルタイプをリストにしたもの．

3 回である．これらの値が大きいほど関連度が高いとする．また共起の間隔時間の合計は 110 分であるが，この値が大きいほど(B) のログへの対処法は，まず (ア) より活動時間外のファイル使用を消す．加えて，Tb 以上活動時間が空いた場合は，ファイルを閉め忘れて帰宅したと見做して，それ以降のログを消す (図2 参照)．(C) のログへの対処法は，(イ) の対象となるファイルタイプに対して，(ア) の活動時間内で最初のファイルアクセスから長期間経過後も二つのファイルを一緒に使っていたことになるので，値が大きいほど関連度が高いとする．ルール 4 に関して，図5 の A1 , B2 の方が B1 , B2 よりファイル使用開始時間が近いものが多く，一緒に使い始めることが多いと考えられるので，より最後のファイルアクセスまでをずっと使用していたと見做して，関連度が高いとする．

使用時間を拡大する (図 3 参照)．

3.2.2

3.2

関連度の算出

関連度の算出上述の大小関係を考慮した関連度の算出方法を説明する．二つ

前節で作成したファイル使用情報を基にファイル間の関連度をのファイルの共起時間の合計を T ，共起回数を C ，共起の間隔度計算する．関連度の算出方法の説明の前に，関連度の大小関係をを D，ファイル使用開始パターンの類似度を P としたとき，関定義する．

3.2.1

関連度の大小関係

連度 R は α, β, γ, δ(0 ≤ α, β, γ, δ ≤ 1) を定数として

R = T α · C β · Dγ · P δ

本研究では，関連度の高いファイル同士は長い期間，各作業となる．また同時に使用したことがない二つのファイルの関連度の度に，同じタイミングで利用されるものと仮定する．そのたは 0 とする．加えて二つのファイルが同じディレクトリに属して2

日本データベース学会 Letters Vol.6, No.2

論文

DBSJ Letters Vol.6, No.2

いる場合，すでに使用者によって関連があると分類されているのログを採取した．システムファイル等のアクセスは無視するようで，検索対象から除くために関連度を 0 とする．に解析対象の拡張子は bib，doc，gif，htm，html，jpg，mpg，

つ の ファイ ル の 各 共 起 を {z1 , z2 , · · · , zn } と し ，そ の 時 間 をmpeg，pdf，ppt，tex，txt，xls とした．また 3.1 節の各定数はTa = 30[分] ，Tb = 5[時間] ，Tc = 10[秒] とした．

{t1 , t2 , · · · , tn }，共起の間の時間を {d12 , d23 , · · · , d(n−1)n }，さ4.2

各 値 の 算 出 方 法 を 説 明 す る ．図 6 を 参 照 さ れ た い ．二実験らに各共起の基となっている二つのファイル使用の使用開始時間

まず，それぞれの被験者のログからファイル使用時間表を作成の差を {p1 , p2 , · · · , pn } として，各値は下記のように計算する．

した．次に全ファイルの中からランダムに選び，被験者に二つのT =ファイルの関連に対して○×採点を行ってもらった．その中から

Pni=1 ti
(1D = Pn−1

i=1 di(i+1)

3.2.3

n=0o.w.

C=n(1P = ` Pni=1 pi´−1∀i pi = 0o.w.

関連度のパラメータの決定

ランダムに半分のファイルを選択し学習用セットとし，そこから計算された最適パラメータと最適閾値は以下のようになった．

(α∗ , β ∗ , γ ∗ , δ ∗ )(0.2, 0.3 , 0.1 ,0.3)(0.1 , 0.6 , 0.2, 0.8)

0.628

0.150

∗

G

関連度 R のパラメータ (α, β, γ, δ) の決定法を説明する．本研
究ではパラメータの決定のために，ユーザのファイル関連に対すこれらの値を用いて，評価セットの各ファイル f に対して再現率る採点を用いる．

REC(f ) と適合率 P RE(f ) を求め，それぞれの値を評価セット■手順 1 採点の対象となるファイル集合を H とする．各 f ∈ H

内のファイルで平均したものが以下のようになった．

に対して C(f ) をファイル f と共起しているファイルの集合とする．C(f ) の各要素に対してファイルの使用ユーザが見て関連被験者Ａ被験者Ｂがあるものを○，関連がないものを×の二値に分類する (図 7

再現率の平均値

81.0 ％

82.6 ％

参照)．

適合率の平均値

66.2 ％

45.0 ％■手順 2

各 f ∈ H に対して，ファイル別閾値 G(f ) を求め，そ4.3

考察の平均を関連度閾値 G とする．G(f ) の求め方は，f に対して関連度のパラメータについては，共起時間の累計だけを考える

C(f ) の中で「○の評価が付いている」かつ「最も f との関連度が最も低い」要素 k を求め，G(f ) = R(f, k) とする．言い換え
ると，C(f ) 内の関連度 G(f ) 以上の要素の集合が○の再現率を100 ％とするような G(f ) を求めている．
■手順 3 各 f ∈ H に対して，ファイル別再現率 REC(f ) を求め，その平均を再現率 REC とする．REC(f ) の求め方は，まず f に対して Ĉ(f ) = {c|c ∈ C(f ), R(f, c) ≥ G} とする．つまり Ĉ(f ) は C(f ) の中で関連度が G 以上の要素の集合である．
次に各 f に対してファイル別再現率 REC(f ) を以下のように計(1,0,0,0) の組み合わせや，共起回数だけを考慮する (0,1,0,0) の算する．

を被験者に合わせて組み合わせた方が，より有効な関連度を計算できることがわかった．
再現率，適合率に関しては，本研究では全文検索で見つからないファイルを探すのが目的であるため，多少不適合ファイルがあっても再現率の向上を優先する．そこで，被験者 A，B 共に再現率の平均が 80 ％以上であった結果より，提案する検索手法を実現する際に，この関連度を用いることが可能であると考える．
ログのクリーニングに関しては評価実験は行っていないが，具Ĉ(f ) 中の○の数
REC(f ) =C(f ) 中の○の数■手 順 4 REC は あ る パ ラ メ ー タ の 基 で 求 ま る の でREC(α, β, γ, δ) と 書 き 直 す．こ の と き 最 適 パ ラ メ ー タ(α∗ , β ∗ , γ ∗ , δ ∗ ) を以下のように計算する．
(α∗ , β ∗ , γ ∗ , δ ∗ ) = argmax(REC(α, β, γ, δ))
本研究では，この最適パラメータを関連度算出に用いるとともに，最適パラメータを与える関連度閾値を最適閾値 G∗ とし，ファイル検索の際に関連度が G∗ 以上の関連のみを考慮することによって，検索結果のフィルタリングに用いる．

4.

組み合わせよりも，回数，使用開始パターンの類似，共起の間隔評価実験

体的な事例として，(A)(B) の問題を修正したことによって本来関連の無い二つのファイルの共起が除去されたことを確認している．また，(C) の問題を修正したことにより，ある論文の Texファイルのログが修正され，論文の図の画像ファイルや，グラフの基となっている実験データファイルと論文の Tex ファイルの共起が抽出できた．このような事例が観測されたため，ログのクリーニングは有効であったと考える．

5.

関連研究

関連研究について三つの観点から議論する.

5.1

階層構造の問題点への解決

Griﬀord らの Semantic File Systems[7] では，各ファイルは本研究では，節 3. で提案した関連度が，もともとのファイルディレクトリに所属しない代わりに複数の属性を持ち，この属性間の関連性を反映しているかどうかを，被験者実験により確認を用いてファイルを管理するファイルシステムであり，情報共有する．

等に役立つと報告している．また，石川らの研究 [8] では属性の4.1

実験環境

表現に RDF[9] を用いることにより，セマンティックウェブ関連実験では，現在広く用いられている Windows 互換ファイルの技術の応用を容易にし，ファイルの整理や一貫性の管理を実現

サーバの Samba2.2.3a をログレベル 2 で実行し，それを Win-している．これらの研究は階層構造の問題点への解決という点でdowsXP から二人の被験者に約 4ヶ月間使ってもらい，アクセスは本研究と一致するが，キーワードに関連するものを探すことは3

日本データベース学会 Letters Vol.6, No.2

論文

DBSJ Letters Vol.6, No.2

していないので，その点で本研究と異なる．

5.2

ユーザの動作履歴利用

俺デスク [10] はイベントログと組み込んだプラグインから動作履歴を抽出し，それを基にウェブページやファイル (以降まとめてデータと呼ぶ) の着目度，データ間の関連度を算出する．そして，関連度を基にしたデータ名による関連検索と，時系列のビューアを提供するシステムである．俺デスクでは，動作履歴を抽出するためユーザ環境に手を加える必要があるが，本研究ではアクセスログを利用するので，手を加えること無くシステムを実現できる．また，俺デスクの検索ではデータ名を入力し関連しているデータを提示するものであって，本研究で提案するキーワードによるファイル検索とは異なる．関連度の算出においても，俺デスクではデータアクセス開始時間のみを考慮しているのに対し，本研究では共起時間の累計，共起回数，間隔等を考慮しており，関連ファイル間の識別能力に違いがある．

5.3

データ間関連度

増田らの近傍検索システム [11] では，ファイルを含むディレク
トリ構造，ファイルの更新時間，ファイルの内容の３つの情報を基に，ファイル間の関連度を算出し，ファイル間の連想アクセスシステムを提案している．しかし，ファイル内容の関連度計算は文書ファイルに限っている．これに対して，本研究では文書ファ
イル以外の画像ファイル，データファイル等のファイルに対しても等しく関連度を算出できる．

6.

まとめと今後の課題

既存の全文検索ではキーワードを含んでいないファイルは，そのキーワードと関連があっても検索できないという問題点があっ[文献][1] Nitin Agrawal, William J. Bolosky, John R. Douceur,
Jacob R. Lorch: A Five-Year Study of File-System
Metadata, 5th USENIX Conference on File and Storage Technologies(FAST’07), 2007.
[2] About Google Desktop,
http://desktop.google.com/about.html[3] Windows Desktop Search, http://www.microsoft.com/windows/desktopsearch/default.mspx[4] Spotlight, http://www.apple.com/jp/macosx/features/spotlight/[5] 全文検索システム Namazu, http://www.namazu.org/[6] Google Image Search, http://images.google.com/[7] D.K.Giﬀord, P.Jouvelot,M.A.Sheldoon,
J.W.O’Toole,Jr: Semantic File Systems, 13th ACM
Symposium on Operating Systems Principles, 1991.
[8] 石川憲一, 森嶋厚行, 田島敬史: 大規模ドキュメント空間管理のための意味ファイルシステムの構築, 信学技報 DE2006115 pp.139-144,2006.
[9] W3C.Resource Description Framework(RDF),http://www.w3g.org/RDF[10] 大澤亮, 高汐一紀, 徳田英幸: 俺デスク:ユーザ操作履歴に基づく情報想起支援ツール, 情報処理学会第 47 回プログラミング・シンポジウム, 2005.
[11] 増井俊之, 塚田浩二, 高林哲: 近傍関係にもとづく情報検索システム, 11th Workshop on InteractiveSystems andSoftware (WISS2003), 2003.

た．本稿では全文検索できないファイルをキーワード検索する手法を実現するために必要なファイル間関連度を，同時に用いられ渡部 徹太郎 Tetsutaro WATANABEるファイル間の関係に着目し，ファイルサーバへのアクセスログ

平 18 東工大・工・情報工卒．同大大学院・情報理工・計算工・修から抽出する手法を提案した．また関連度算出を実装し，その関士課程在学中．日本データベース学会学生会員．

連度を用いてあるファイルと関連度の高いファイル群を提示した

小林 隆志 Takashi KOBAYASHI所，そのファイル群の正解 (ユーザが関連があると判断した）の

平 9 東工大・工・情報工卒．平 11 同大大学院・情報理工・計算再現率が 80 ％以上であった．この結果より，提案する検索手法

工・修士課程了．平 16 同大大学院・同専攻・博士課程了．平 14を実現する際，この関連度を用いることが可能であると考える．

同大学学術国際情報センター・助手．平 19 名大大学院・情報科

今後の課題としては以下の 4 点が挙げられる．

学研究科・特任准教授．日本データベース学会，電子情報通信学• 検索手法の実装を最後まで行い，その評価を行う．
• より多くのユーザを対象として評価実験を行う．
• 関連の方向や時間的減衰を考慮に入れた関連度算出手法の考会，日本ソフトウェア科学会，情報処理学会，ACM 各会員．

案する．

• ファイルの使用時間の情報のみでなく，ファイルのコピーや移動をアクセスログから抽出し検索結果のフィルタリングに利用する．

横田 治夫 Haruo YOKOTA
昭 55 東工大・工・電物卒．昭 57 同大大学院・情報・修士課程了．
同年富士通（株）．同年 6 月（財）新世代コンピュータ開発機構
研究所．昭 61（株）富士通研究所．平 4 北陸先端大学・情報・助教授．平 10 東工大・情報理工・助教授．平 13 東工大・学術国際情報センター・教授．工学博士．日本データベース学会理事．電子情報通信学会，情報処理学会，人工知能学会，IEEE，ACM［謝辞］各会員．

本研究の一部は，文部科学省科学研究費補助金特定領域研究(19024028)，東京工業大学 21 世紀 COE プログラム「大規模知識資源の体系化と活用基盤構築」および独立行政法人科学技術振興機構戦略的創造研究推進事業 CREST の助成により行なわれた．

4

日本データベース学会 Letters Vol.6, No.2