東京工業大学学術国際情報センター教授横田治夫 1
2 現状 身の回りでファイルが大量に増えている ネットワークを含めた情報環境整備等により 企業内のファイル増大に関する報告 Nitin Agrawal et al. [FAST 2007] Microsoft 内の 6 万台の WindowsPC のファイルシステムを調査 2000 年 ~2004 年 (5 年間 ) 平均ファイルサイズ 約 2 倍 平均ファイル数 約 3 倍 問題点 欲しいファイルが見つからない 簡単に見つけたい
3 ディレクトリ階層 ファイルフォルダとその入れ子構造 階層関係は作成者の概念構造に依存 問題点 : 概念構造は一様ではない 人によって違う 組織やグループの共有ファイルシステムでは ファイルがどこにあるか分からない 時間が経つと変わる 自分が作った概念階層も忘れてしまい どこに置いたか分からなくなる 特に階層が深くなると問題は大きい 浅くするとフォルダ内で探すのが大変 階層 A 階層 B プロジェクト X 企画 見積 X 企画 X 報告報告 X プロジェクトY 提出書類 2008/04 企画 X 2009/03 報告 X 計算データ見積 X
4 デスクトップサーチ キーワードを与えてファイルを全文検索 ディレクトリ構造に依存せず ディレクトリを横断した検索 全文検索ベースのファイル検索システムの例 Windows Desktop Search (Microsoft) Google Desktop Spotlight (Mac OS X) Hyper Estraier Namazu を利用したファイル検索 全文検索の問題点 対象がキーワードを含むファイルのみ キーワードを含まない画像 データファイル等は対象外
メタデータサーチ ファイルごとにメタデータ ( 付加情報 ) を付与 Semantic File System [Grifford, et al.1991] 他 問題点 膨大なファイルすべてに対して検索に有効となるような適切なメタデータの付加は非現実的 文書ファイルからの参照情報を利用 Google Image Search ウェブ上の画像をキーワード検索 HTML ファイル内の画像参照情報を利用している 問題点 ファイルシステム内のファイルは, 基本的には画像への参照情報を含んでいない ( 特にコピー & ペーストだと ) 5
6 人間が物を探すとき : あの時の あの時一緒に使っていた図のファイルは? あの報告書に使ったデータは? 同時に使っていたファイルは関連が深い 関連しないファイルも開いているかもしれないが でもその頻度は低い 関連が深いファイルは高頻度で同時に開く その関連性を使って検索 でもどうやって? ファイルのアクセスログを解析する 期待される効果 キーワードを含まない図やデータも検索可能 メタデータを用意する必要もない
写真 文書 図 データ 7
ファイルアクセスログ ( 履歴 ) を取得 例えば Samba の設定を変更すれば可能 ファイルのオープン時刻 クローズ時刻 ファイルアクセスログの精錬 アプリケーションによってログの残し方が違う 利用開始時にオープン 終了時にクローズ オープンしてすぐクローズ きちんとクローズされない アクセスログの解析 頻繁に同時に使われるファイルの間の関係を数値化 数値化した関連度を基に検索 8
ァイルアクセスログ9 フ1:00 open 1:20 open 1:50 close 2:30 close 3:00 open 4:00 close オープン時刻からクローズ時刻をファイル使用期間とする ログクリーニング 活動時間情報 直ぐに閉じるファイルタイプのリスト 実際にユーザが使用したファイルの時間と, 異なる幾つかの問題 フ1:00 2:30 3:00 4:00 実際にユーザが使用したファイルの時間と近い情報 ァイル使用期間ユーザの
共起 = ファイル使用期間の重なり 四つの関連度要素を導入する 大きいほど関連度が高い T: 共起時間の累計 C: 共起回数 D: 共起間隔の累計 P: 使用開始時間の類似度 共起 1 2 関連度の計算 関連度 = T α C β D γ P δ 時間 3 10
芋づる方式 従来のキーワードサーチ ( 全文検索 ) を行い その検索結果であるファイルと関連する ( 同時に使われていた ) ファイルも関連度に従って出力する 仮想ディレクトリ方式 関連度に従ってクラスタリングを行い 同時に使っていた頻度の高いファイル群を仮想ディレクトリ ( 仮想フォルダ ) として提供する 11
ファイルシステム 検索可能にする ファイルシステム 全文検索結果 1 位 2 位 検索結果 3 位 4 位 関連度 12 芋づる方式の検索対象 5 位
Samba ファイルサーバのアクセスログを利用 Samba 2.2.3a の debug level 2 のログ Samba 自体には手を入れていない 関連度計算部分 関連検索部分は Java で実装 Web アプリケーションとして動作 コンポーネントは既存ソフトウェアを利用 全文検索エンジンは Hyper Estraier 1.4.13 を利用 Hyper Estraier は N グラムインデックス法を利用 Web アプリケーションコンテナは Tomcat 5.5.9 利用 関連度格納 DB は Oracle 10g PostgreSQL でも実現可能 13
FRIDAL: File Retrieval by Inter-file relationship Derived from Access Log ファイル使用 ユーザ 検索結果 検索要求 ファイル使用準備検索 ファイルサーバー (Samba) FRIDAL アクセスログ取得 ウェブインターフェイス 検索要求 ファイル使用 関連度計算 関連度格納 関連度 DB 得点計算 関連ファイルの検索 全文インデックス 全文検索 コントローラ (java) 全文検索エンジン (Hyper Estraier) 全文インデックス作成 ファイルシステム 14
ファイル間関連による得点TF-IDF による得点 検索されたファイル 15
関連度が大きいファイルから結合 1-A 1-B デンドログラム 下で結合しているほど関連度が高く 上で結合しているほど関連度が低い 結合 結合 閾値 A 4 3 1-B 2-B 1-A 2-A 1-A 3 1-B 2-B 2-A 4 1-B 2-B 2-A 16 閾値 A 以下で結合したクラスタを仮想ディレクトリとして提示
デンドログラム 閾値 0.4 共起ファイル数 295 17
研究室内のファイルサーバのアクセスログ利用 被験者による評価 関連度算出式のパラメータ調整 α β γ δ T C D P 他の手法との比較 単なる全文検索 全文検索結果ファイルが含まれるディレクトリ中のファイル キーワードを含まないファイルを検索できるか調査 他人のディレクトリにあるファイルを探してもらう 他の手法では探せないファイルも見つけだすことができた 適合率 再現率の評価 18
19 検索対象の拡大 これまで検索することが困難であった図 データなど様々な形態のファイルが 同時期にアクセスしたという履歴から探し出すことが可能になる 実現容易性 ファイルアクセスログを取得するのは容易 ファイル 1 つ 1 つにメタデータを付与しなくても 他のファイルとの関連から芋づる式に見つけ出すことができる あの時に対応するキーワードから 新たな検索結果提示法 関連度を使ったファイルの分類手法によって ある作業で使ったファイルの集合を見つけ 仮想的なフォルダ あるいはディレクトリとして提供できる あの時のあれらのファイル
エンタープライズサーチ 企業のシステムに載せ 企画書に使った関連資料の整理など 企業内のファイルの検索に利用 個人デスクトップサーチ 個人の PC に載せて 従来のディスクトップサーチエンジンの置き換え ( 全文検索の補完 ) 初心者 高齢者向けファイル管理 ディレクトリ構造の理解が困難である利用者に対し 何も考えずに格納しても 仮想的なディレクトリ構造を提供 20
Web 検索市場は既に寡占状態 Google Yahoo Microsoft エンタープライズサーチは導入が始まったところ エンタープライズサーチにおける検索機能の満足度はまだ低い 初心者 高齢者向け対策も注目されている 21
実用的な環境への対応企業のファイルシステム等の大規模かつ多様なアクセスログを用いた評価実験 学生を対象としたため, 検索要求が限られた 手法の改善 ファイル間関連度 ファイル検索法の改良 検索要求に応じた検索結果提示法の改善 22 さらなる展開の可能性に向けて ファイルだけでなく Web アクセスログとの連携 文書作成で参考にした Web ページも検索を可能に 他の関連度との連携 文書や図形の類似度など 2008/3/4
発明の名称 : ファイル検索システム 出願番号 : 特願 2007-161612 出願人 : 東京工業大学 発明者 : 横田治夫 渡部徹太郎 小林隆志 関連情報 試作ソフトウェアの提供は可能 23
研究者 横田治夫 東京工業大学学術国際情報センター教授 152-8552 目黒区大岡山 2-12-1 TEL:03-5734-3505 E-MAIL: yokota@cs.titech.ac.jp 技術移転支援者 加藤大三 東京工業大学産学連携推進本部 Coordinator 226-8503 横浜市緑区長津田町 4259-S2-10 TEL:045-924-5171,-5101 E-MAIL: kato@sangaku.titech.ac.jp 技術移転プランナー 牧本三夫 科学技術振興機構シーズ展開課 TEL:03-5214-7519 E-MAIL: m2makimo@jst.go.jp 24