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

複数種類の関連度を組合せたファイル分類手法

Title(English)

A File Grouping Method Combining Multiple Types of InterfileRelationships

著者(和文)

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

Authors(English)

Yousuke WATANABE, Kenichi OTAGIRI, Haruo YOKOTA

掲載誌(和文)DEIM2009論文集

Citation(English)

Proc. DEIM2009

Vol, no, pages, ,発行日 / Pub. date2009, 3

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2009 B6-4

複数種類の関連度を組合せたファイル分類手法
渡辺 陽介†

小田切健一††

横田治夫†,††† 東京工業大学学術国際情報センター†† 東京工業大学大学院情報理工学研究科
E-mail: †{watanabe,otagiri}@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
あらまし

近年，個人が管理しなければならないファイルの数と種類が膨大となっており，大量のファイルを分類・整理し，目的のファイル群を効率的に探すための新たな情報管理技術が求められている．我々の研究グループでは，大量のファイルから関連するファイル同士を発見し，仮想的なディレクトリとして提示するシステムの開発を行っている．
ファイル間の関連度の計算法として，単語出現頻度に基づく尺度や，アクセスの共起関係に基づく尺度など，様々なものが提案されている．より現実的には，要求に応じてこれらを使い分け，組合せることで必要なファイルのグループが生成できることが望ましいが，異なる関連度尺度を統一的に用いるための枠組みについては，これまであまり提案がされていない．本稿では，複数種類の関連度を利用可能なデータキューブ型ファイルグループ分析ツールについて提案する．本ツールでは，複数の関連度から求めたクラスタリング結果等を多次元のキューブとして統合・操作することができる．利用者はスライスやドリルダウン・ロールアップなどのキューブ操作を行って要求に合ったグループ
を生成し，特定のファイルに関連するファイル群を見つけ出したり，大量のファイルを整理したりすることができる．
キーワード

ファイル間関連度，クラスタリング，データキューブ

A File Grouping Method Combining Multiple Types ofInterfile-Relationships
Yousuke WATANABE† , Kenichi OTAGIRI†† , and Haruo YOKOTA†,††† Global Scientific Information and Computing Center, Tokyo Institute of Technology†† Graduate School of Information Science and Engineering, Tokyo Institute of Technology
E-mail: †{watanabe,otagiri}@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
Abstract Since the number of files in PCs is increasing, we require file management tools to find target files
and to classify large amount of files. Our research group has been developing a system which provides virtual
directories consisting of related files. There are many types of methods to extract inter-file relationships, such as
word frequency, access co-occurrence, and so on. In practical, users need to select and combine multiple types ofinter-file relationships to form groups of files they want. For this purpose, we propose a tool for file group analysis
by introducing data-cube concept. This tool provides cube-like operations for a set of files, and helps users to findrelevant file groups.
Key words Inter-file relationships, clustering, data cube

1. は じ め に

デスクトップ検索ツールは，ファイルから，パス名，ファイルに付加されたタグ，ファイル内の文字列等に含まれるキーワー

近年，ネットワーク上で交換されるデータ量が増加し，メードを抽出し，索引付けを行っており，利用者が入力したキー

ル，文書，画像，動画など，個人の PC に蓄積されるファイル

ワードに合致したファイル群をリストとして提示する．そのたの数と種類は膨大なものとなっている [1]．利用者の記憶だけをめ，デスクトップ検索ツールは，特定キーワードを含むファイ

頼りに，大量のファイルの中から目的のファイル群を探し出す

ルをピンポイントで取得する目的に適している．だが，利用者ことは難しくなっており，デスクトップ検索ツール [11], [15] なが必要とするファイルが複数ある場合には，必ずしもそれら全どの支援を得ながらファイルを探索することが行われている．

てが特定キーワードに合致するとは限らないため，一般には複—1—

数回の検索行動が必要となってしまう．
論理的な関係のある複数のファイルを扱う際には，一部の2. 関 連 研 究

ファイルから残りを芋づる式に取得できるように事前に整理さまず，キーワード検索とキーワード以外の関連情報を組合れている状態が望ましい．そのためのアプローチとして，共通せた検索システムについて述べる．Google デスクトップサーの特徴をもったファイル同士をグループ化し，必要に応じてグ

チ [11] のタイムライン表示機能では，キーワード検索の結果

ループ単位で提示できるようにしておくことが考えられる．そファイルから，同じ時間帯に更新されたファイル群を時間軸上れは例えば，あるファイルと共通なキーワードを含むファイル

で探すことが可能である．また，FRIDAL [9] はファイルアク

群も一緒に提示するということであるが，ファイル同士を関連

セスログ中の共起関係を用いて，キーワード検索にマッチする

付ける特徴量はキーワード情報だけではない．最終更新時刻のファイルだけでなく，共起したファイルをも含めてランキング

近さや，パス名の類似性，内部的な参照関係など，様々な観点表示することができる．これらは単純なキーワード検索よりもから関連付けが可能である．我々の研究グループでも，ファイ

多くのファイルを探すことができるが，ファイルのグループ化

ルアクセスログからアクセス共起関係を抽出し，それらをファを目的としているわけではない．

イル間の関連度として用いる研究を行っている [8]．

ファイルに付与された複数の属性情報に基づいて，ファイル

これらのような関連度を個別に用いてファイル同士をクラスのグループを提示するシステムとしては Semantic File Sys-

タリングする研究は従来から行われてきたが，より高度で柔軟

tems [3] がある．Semantic File Systems では，各ファイルはなファイル利用を促進するためには，どれかの尺度を単体で用実体のあるディレクトリに属す代わりに，属性に関する問合せいるだけでなく，複数の尺度を用途に応じて切り替え，あるいで表現される仮想的なディレクトリに属する．また，ファイルは組合せていくことが必要となる．例えば，共通のキーワード

システムとは異なるが，Windows Vista ではファイルのタグ情を含むという特徴だけではグループ分けが十分にできなかった報などを検索でき，検索結果を検索フォルダとして保存して再ファイル群を，さらにアクセス共起関係でサブグループに分け利用する機能が提供されている．これらはファイル自身の属性

ることは有用であると考えられる．しかし，これら複数種類の情報を用いたグループ化であり，ファイル間の関連度は用いてファイル間関連度を統一的に扱うファイルグループ化の枠組み

られていない．

については，まだ十分な検討がなされていない．

ファセット探索（ファセット検索）[5], [6] は，複数の属性情報

そこで本研究では，複数種類のファイル間関連度を統合可能を持つオブジェクトに対して，属性情報の値を順次指定していなファイルグループの分析ツールを提案する．本ツールでは，

くことで対象を絞り込む探索手法である．探索の過程では，選利用者の要求に合わせて，グループ分けに用いる尺度の選択，別されたオブジェクトの集合と，さらに絞り込むための属性値

グループ化の粒度の調節，条件に合ったグループの選別の操作の候補が提示される．ファセット探索をファイルのグループを等を行えるようにするため，それらの操作を実現可能なモデル探す目的で利用することは可能である．ただし，ファセット探として，OLTP で用いられているデータキューブ [4] を用いて索においては，ファイル名やタグ情報などのファイル自身の属いる．本ツールにおけるキューブの 1 つの次元（ディメンジョ

性情報を用いたグループ化は容易だが，アクセス共起のようなン）は，1 種類の関連度に基づいてファイルをクラスタリング

ファイル間の関係としてしか表現できないものは扱いが難しい．

した結果を表している．利用者は通常のデータキューブとほぼ参照関係や依存関係，コピーとオリジナルなどのファイル同士同様な操作を行って，必要な関連度において適切な粒度でグの関係を扱うシステムとして，Linking File Systems (LiFS) [2]

ループ化の行われた部分キューブを生成する．キューブ操作とや InfoSpaceGoverner [7] などがある．これらのシステムでは，して，特定の種類の関連度で生成されたグループを条件指定にファイル間の関係を説明するリンクを張ることができ，リンク

より選別し，部分キューブを切り出す操作であるスライス・ダを用いた検索や探索，依存関係に基づいた一貫性のチェックな

イスや，各関連度における階層的クラスタリングの結果を用いどの機能を提供している．本研究は，数値化されたファイル同て，必要に応じてグループ化の粒度を調整する操作であるロー士の関連度からファイルのグループを生成することを目的としルアップ・ドリルダウンを扱う．最終的に生成されたグループており，グラフ構造の扱い等については考慮していない．

は，ファイルの整理やデスクトップ検索の検索結果の拡張に利用される．本稿では，提案ツールの実装とそれを用いた評価実験についても述べる．

3. ファイル間関連度
本研究で用いるファイル間関連度の尺度について紹介する．

本稿の構成は以下のようになっている．まず，2. では関連研

ここで述べる以外にも様々な尺度は存在するが，ファイル間の究との関係について述べる．次に，3. では本研究で用いるファ関係を数値として表現できるものであれば，提案ツールに取り

イル間関連度について紹介する．そして，4. で本研究で提案す入れることは可能である．以下では，ファイル x とファイル y

るデータキューブ型ファイルグループ分析ツールについて説明の関連度 Sim(x, y) を [0,1] の区間に正規化するようにしていし，5. 節では実装システムについて述べる．6. では，評価実験

る．1 が最も関連が強く，0 は全く関連がないことを意味する．

の結果を示す．最後に 7. で，まとめと今後の課題を述べる．

3. 1 テキスト類似度
従来からテキストデータの検索やクラスタリングなどでよく使われている尺度である [10]．共通のキーワードが多く含ま—2—

れているファイル同士には強い関連があるとみなす．ここでは

3. 4 アクセス共起度

ファイル x, y に含まれるキーワードを抽出して単語出現頻度に2 つのファイルを同時にアクセスしていた場合，その 2 ファよる文書ベクトル vx , vy として表現し，ベクトル同士の成す角イルは同一の作業に利用していた可能性が高い．そのような共の余弦をテキスト類似度とする．

起が長期間や複数回に渡って発生していれば，より強い関係でSimtext (x, y) =vx · vy||vx ||||vy ||あるとみなすことができる．ファイル使用の共起は，ファイルのオープンとクローズのログを記録することで知ることがで

今回はファイルに付与されたタグ情報やファイル名自体は使用

きる．[9] では，ファイルサーバの Samba [14] のログを用いてしないものとする．画像などの非テキストファイルの場合は，おり，ファイルオープン時刻の近さや共起間隔などの要素も考自身との類似度だけが 1 で，それ以外は 0 とする．

慮されているが，ここでは最もシンプルに共起時間の累計を用

テキスト類似度を用いる利点は，文字列データ限定ではあるが，ファイルの中身に基づいて類似度が算出できることである．
利用者が探したいファイル群に共通のキーワードが含まれていいる．

Simcooccur (x, y) =t (x, y)
Σ0<
=n i
=i<
maxa,b∈F (Σ1<t (a, b))
=j <
=m j

る場合に有効である．欠点として，当然ではあるが，画像や動ただし，ti (x, y) はファイル x, y の i 番目の共起における共起画などのテキスト情報が少ないファイル同士の関連度を正確に時間を表す．

計算することはできない．また，書類ファイルが定型の書式をアクセス共起度ではファイルオープンが共起してさえいればベースに作成されている場合などには，書式自身に含まれる単よく，また更新時刻類似度とは異なって閲覧中心のファイルと語が共通キーワードとなってファイル群がグループ化されてし編集中心のファイルを関連付けることが可能である．ただし，まうような事態が起こりうる．

滅多に使用しないファイルや作成直後のファイルの場合には，

3. 2 更新時刻類似度

共起関係がほとんど抽出できないため，グループを作ることがファイルの更新時刻同士の近さに応じて決まる尺度である．

難しい．

更新時刻が近いファイルは，一連の作業において作成・編集さ以上で述べた通り，ファイル間関連度の尺度は複数あるが，れた可能性が高く，時間が近いほど強い関連があるとみなせる．

どれにも長所・短所があり，利用者の習慣やファイルの種類等

以下の式で計算する．

によって左右される．そのため，用途に応じて使い分け，組合

Simmtime (x, y) = 1 −|mtime(x) − mtime(y)|maxa,b∈F (|mtime(a) − mtime(b)|)

ただし，mtime(f ) はファイル f における最終更新時刻（基準時からの経過秒数）を表すものとする．分母は [0,1] 区間に正規化するために入れられている．

せる必要がある．

4. データキューブ型ファイルグループ分析ツール
本節では，データキューブ型ファイルグループ分析ツールについて述べる．本ツールは，複数種類のファイル間関連度の情

更新時刻は，ファイル中のテキスト情報と違って，全てのファ報をもとに，様々な切り口のファイルのグループを提供する（図イルにおいて利用可能な情報であるという利点がある．ただし，

1）．データキューブの考え方に基づいているため，同様に次元閲覧中心のファイルと編集中心のファイルがあるような場合にや階層といった概念が存在する．また，通常のデータキューブ

は，閲覧中心のファイルは更新時刻が変化しないため，編集作と同様のスライスやドリルダウン等の操作を提供する．ただし，業が進めば進むほど，編集中心のファイルとのグループ化が難

通常のデータキューブが個々のデータやグループ自体よりも集しくなってしまうという問題点がある．

約処理結果を提示することを目的とするのに対して，本ツール

3. 3 パス類似度

におけるキューブはファイルの集合そのものの発見・生成を支

ファイルのパス名の近さに応じて決まる尺度である．同一援することを目的とする．

フォルダや親子兄弟関係にあるファイルには関連があると考え

4. 1 次元

る．本研究では編集距離に基づき，パスの類似度を算出する．

本ツールが提供するデータキューブの各次元（Dimension）

編集距離は文字の挿入・削除・置換によって同じ文字列を得る

は，特定の関連度尺度に基づいてファイル群をクラスタリングまでに必要な操作の回数によって表わされる．距離尺度である

した結果のクラスタの集合である．クラスタリングに用いる関ので，これを類似度に変換するために，[0,1] 区間に正規化した

連度は 3. で述べたものを対象とする．本研究で用いるクラス

後，1 との差を取っている．

タリング手法については 4. 1. 1 で述べる．図 1 は 3 つの関連度

Simpath (x, y) = 1 −editDistance(x, y)maxa,b∈F (editDistance(a, b))

パス類似度は，利用者がフォルダ名やファイル名を適切な名尺度のクラスタリング結果を使ったキューブを表している．例
えば，ファイル dews.ppt はテキスト類似度のクラスタリング
結果ではクラスタ t3 に属し，更新時刻類似度ではクラスタ m1

前を付与する場合においては有効である．逆に，デスクトップに属し，アクセス共起度ではクラスタ c1 に属するファイルで上などに無秩序にファイルを配置し，「新規テキストドキュメン

あることを表している．

ト.txt」といったデフォルトのファイル名のまま使用してしま

また，補助的な目的として，ファイル名（辞書順），ファイル

うような利用者の場合には，パス類似度が役に立たないことも

サイズ，ファイルタイプ等のファイル自身の属性情報も次元とある．

して用いる．複数種類の尺度によるクラスタリング結果とファ—3—

図 2 階層的クラスタリングによるデンドログラム（テキスト類似度）

Fig. 2 Dendrogram geenerated by hierarchical clusteringの荒いクラスタが生成され，逆により葉に近い断面で分割する

䉪䊤䉴䉺t1䊁䉨䉴䊃㘃ૃᐲ
䉪䊤䉴䉺䊥䊮䉫⚿ᨐ 䉪䊤䉴䉺t2と粒度の細かいクラスタが生成される．本研究では，このデン䉪䊤䉴䉺t3dews.ppt

icde.tex

ドログラムにおける併合関係の階層をデータキューブにおけるipsj.doc䉪䊤䉴䉺m1

概念階層としてグループの粒度調整に用いる．

ᦝᣂᤨೞ㘃ૃᐲ
䉪䊤䉴䉺m2䉪䊤䉴䉺䊥䊮䉫⚿ᨐ䉪䊤䉴䉺m3ᦝᣂᤨೞ䈪䊄䊥䊦䉻䉡䊮

䉪䊤䉴䉺c1 䉪䊤䉴䉺c2 䉪䊤䉴䉺c3䉝䉪䉶䉴౒⿠ᐲ
䉪䊤䉴䉺t1䉪䊤䉴䉺䊥䊮䉫⚿ᨐᦝᣂᤨೞ䉪䊤䉴䉺m1䈪䉴䊤䉟䉴䉪䊤䉴䉺t2䉪䊤䉴䉺m1’䉪䊤䉴䉺m2’䉪䊤䉴䉺t2䉪䊤䉴䉺t3dews.ppt

icde.tex

ipsj.doc

䉪䊤䉴䉺c1 䉪䊤䉴䉺c2 䉪䊤䉴䉺c3

dews.ppt

層

通常のデータキューブでは，各次元（Dimension）をより抽
象的な単位で集約化するために，概念階層を用いる．本ツール
でも同様に階層情報を用いたファイルのグループ化を行う．

䉪䊤䉴䉺t3䉪䊤䉴䉺t1

4. 2 階icde.tex

ipsj.doc䉪䊤䉴䉺m3’䉪䊤䉴䉺m4’䉪䊤䉴䉺m5’䉪䊤䉴䉺m6’䉪䊤䉴䉺c1 䉪䊤䉴䉺c2 䉪䊤䉴䉺c3

ファイル自身の属性情報を扱う次元の場合，階層関係の情報は事前に用意したものを用いるものとする．例えばファイルタ
イプであれば，.doc や.png をより抽象化した上位の概念として，文書や画像といった階層関係を用いる．

図 1 データキューブ

クラスタの場合は，概念階層の代わりに階層的クラスタリン

Fig. 1 Data cube

グの出力であるデンドログラムの情報を用いる．4. 1. 1 で述べた通り，デンドログラムはクラスタ同士の併合順序を表わして

イル自身の属性情報とを組合せ，ファイル集合に対するグルー

おり，根に近いほど荒い粒度でのグループ化の結果を表わしてプ化を行っていく．

いる．これらの階層情報を用いて，キューブ操作のロールアッ

4. 1. 1 クラスタリング手法
3. のファイル間関連度の計算式を使って，N 個のファイルにプ・ドリルダウンの操作が行われる．

4. 3 キューブ操作

対して関連度を計算すると N × N の関連度行列を生成できる．

4. 3. 1 スライス・ダイス

この生成した関連度行列に対してクラスタリング手法を適用す

スライスはキューブの 1 つの次元における条件を指定して，る．本研究では，ファイルのクラスタリングには凝集型階層的部分キューブを取り出す操作である．2 つ以上の次元においてクラスタリング手法 [4] を用いる．これは，各要素だけで成る最条件を指定し，部分キューブを切りだす操作はダイスと呼ばれ小のクラスタ集合からスタートして，関連度の強いクラスタをる．本ツールにおいても，利用者はキューブから自分の必要な順に併合していき，最後に全体を統合したクラスタができるま部分キューブを取り出すことができる．クラスタに対するスラで併合処理を繰り返すというものである．クラスタ同士の関連

イスの条件としては，クラスタラベルを直接指定する方法だけ度を求める方法には，クラスタ内の要素間の関連度の最小値をでなく，「ファイル A を含むクラスタ」といったクラスタ内要素

用いるもの（単連結法），最大値を用いるもの（完全連結法），に基づく条件も指定可能とする．図 1 左下は，「更新時刻類似度

平均値を用いるもの（群平均法）などがある．

のクラスタラベルがクラスタ m1」であるもの，という条件でクラスタを併合する過程は，デンドログラムと呼ばれるツスライスを行った場合である．

リーであらわすことができる．図 2 は著者のホームディレクト

4. 3. 2 ロールアップ・ドリルダウン

リに置かれたファイル 300 個に対して，テキスト類似度によるデータキューブにおいてロールアップは，「月単位」のグルー

階層的クラスタリングを行った様子である．根に近い方で併合

プを「年単位」にするなど，概念階層におけるより上位の単位されているクラスタは，関連度が低いとみなせる．階層的クラでデータをまとめ直す操作である．逆にドリルダウンはより詳

スタリングでは，このツリーをある閾値の高さで部分木に切断

細な単位でデータをグループ化し直す操作である．

することで，その閾値よりも強い関連度をもったファイル同士

本ツールにおいて，ファイルの属性情報の次元については，のクラスタが生成できる．より根に近い断面で分割すると粒度

通常のロールアップ，ドリルダウン操作と同様の動作である．

—4—

例えばファイルタイプでは，.doc などの拡張子によるグループ䊐䉜䉟䊦䉫䊦䊷䊒

分けをロールアップして，文書や画像などのより大きなグルー䉨䊠䊷䊑ᠲ૞

プに変える．

䊂䊷䉺䉨䊠䊷䊑⴫␜ㇱ

クラスタに対するロールアップ・ドリルダウンは，クラスタ
リングの粒度を変える操作として用いる．デンドログラムのツ䉪䊤䉴䉺䊥䊮䉫⚿ᨐ䊐䉜䉟䊦ዻᕈᖱႎ

リーを，より高い位置で分割することで粒度の荒いクラスタを䊂䊷䉺䉨䊠䊷䊑೙ᓮㇱ䉪䊤䉴䉺㓏ጀ

䉪䊤䉴䉺㓏ጀ

生成し，逆に低い位置で分割することで粒度の細かいクラスタを生成する．図 1 右下は，更新時刻類似度についてドリルダウンを行い，クラスタをより細かい単位にした例である．

䊌䉴㘃ૃᐲ䊁䉨䉴䊃㘃ૃᐲ

䉪䊤䉴䉺㓏ጀ

ᦝᣂᤨೞ㘃ૃᐲ

䊁䉨䉴䊃㘃ૃᐲ
᛽಴ㇱ

䊌䉴㘃ૃᐲ
᛽಴ㇱ

ᦝᣂᤨೞ㘃ૃᐲ
᛽಴ㇱන⺆䈱಴⃻㗫ᐲ䊐䉜䉟䊦䊌䉴

䊐䉜䉟䊦䉝䉪䉶䉴

4. 3. 3 ピ ボット䉝䉪䉶䉴౒⿠ᐲ

䉝䉪䉶䉴౒⿠ᐲ
᛽಴ㇱ/home/userන⺆K

ピボットはキューブを視覚化するときの軸の方向や表示順序䉪䊤䉴䉺㓏ጀ

䉪䊤䉴䉺↢ᚑㇱ

න⺆2
paper

work

materialන⺆1

等をかえる操作である．これについては，従来のデータキュー
ブとほぼ同様である．

図 3 システムアーキテクチャ

Fig. 3 System architecture

5. プロトタイプシステム
本節では，現在開発中のデータキューブ型ファイル分析ツール

る．hclust 関数では，クラスタ同士の関連度を計算する方法の実装について述べる．本システムは Ruby(ActiveScriptRuby)（単連結法，完全連結法，群平均法等）を引数で切り替えるこ

および R [13] で実装されている．主要部分は Ruby だが，クラとができる．

スタリングの処理に関しては R を用いている．システムアーキ

5. 3 データキューブ制御部

テクチャを図 3 に示す．本システムは，関連度抽出部，クラス

データキューブ制御部では，クラスタ生成部が出力したク

タ生成部，データキューブ制御部，データキューブ表示部からラスタ階層の情報を統合してキューブとして扱えるようにし，なる．

データキューブ表示部へ必要な情報を提供する．表示部からの5. 1 関連度抽出部

ロールアップ，ドリルダウン命令に基づいて，対応する類似度

関連度抽出部はファイルシステム中のファイル群から関連度のクラスタ階層を閾値で切断し，適切な粒度のクラスタを生成の情報を取得するためのモジュールである．現状では，3. で述する処理も行う．

べたテキスト類似度，更新時刻類似度，パス類似度，アクセス

5. 4 データキューブ表示部

共起度が抽出可能である．

利用者がファイルのグループを閲覧し，またキューブ操作をテキスト類似度抽出部では，全文検索システム Hypere-

するためのインターフェースとしての機能を提供する．表示部

straier [12] の類似検索機能の出力を用いている．利用者はテキ

は，Microsoft Excel をベースにしたインターフェースとなってスト類似度の抽出対象にしたいファイル群をあらかじめ Hyper-

いる．もともと Excel にはピボットテーブルと呼ばれるキュー

estraier に登録しておく必要がある．Hyperestraier に付属するブに近い機能があったため，現実装の表示部ではピボットテー

ファイルコンバーター xdoc2txt の機能により，プレーンテキ

ブルを含んだ Excel ファイルとして結果を出力するようになっ

ストだけでなく Office 文書や一部の PDF からのテキスト抽出ている．図 4 はテキスト類似度とパス類似度のクラスタリングが可能である．

結果を 2 次元の表に出した様子である．Excel のピボットテー

パス類似度および更新時刻類似度の抽出部は，ファイルシス

ブルでは，画面右側のメニューで，どの次元を列と行に表示す

テムをスキャンして，直接パスやファイル更新時刻の値を取得るかを自由に選ぶことができる．ドリルダウン，ロールアップ

している．

の操作については Excel から実行できないため，別ウインドウ

アクセス共起度抽出部は，ファイルサーバ上の Samba [14] がからの操作となる．

記録したログ情報を用いて関連度を算出する．Samba のログ

5. 5 利 用 例には，ファイルのオープンまたはクローズに関する情報が時刻，

実際に著者のファイルをグループ化した場合の操作例を紹介

ユーザ名，ファイル名等と共に記録されている．オープンのみする（図 5）．まず要求 1 として，「テキスト類似度のクラスタで対応するクローズが存在しないような壊れたログも一部記録をアクセス共起度で細分化して見たい」を考える．

されるが，FRIDAL [9] と同様のログクリーニング手法を用い（ 1 ） 図中の要求 1(a) のキューブは，テキスト類似度の次て補間を行っている．

元のみ 10 分割し，それ以外は分割なしにした状態である．こ5. 2 クラスタ生成部のとき，対象クラスタ「text06」は共通キーワードを含む 7 個

クラスタ生成部では，各関連度に対して階層的クラスタリンのファイルから構成されている．

グを実行し，それぞれの関連度に基づくクラスタ階層を得る．

（ 2 ） 図中の要求 1(b) は，(a) のキューブに対してドリルダ

クラスタの併合過程を表わすツリーを生成するところまでが，ウンを行い，アクセス共起度の次元を 10 分割にした状態であ

このモジュールの役目である．この部分は完全に既存手法である．この操作により，対象クラスタ「text06」はアクセス共起るので，本システムでは R が提供する hclust 関数を用いてい—5—

表 1 実験ファイル拡張子

Table 1 Extensions of experiment files.JPG .PNG .ai .bib .css .csv .doc .docm .docx .eml .eps .htm
.html .ico .jpg .pdf .png .ppt .pptx .rtf .tex .txt .xls .xlsx
表 2 人手で分類された正解集合

Table 2 Answer set created by human

図 4 ファイルグループ出力 (行：テキスト類似度クラスタ，列：パス
類似度クラスタ)
Fig. 4 Output of file groups (row: clusters based on text similar-

ity, column: clusters based on path similarity

研究発表 1(1 件) 研究発表 2(29 件)
イベント 1(3 件) イベント 2(8 件) イベント 3(13 件)
ソフト開発 1(16 件) ソフト開発 2(24 件) ソフト開発 3(5 件)
ソフト開発 4(49 件) ソフト開発 5(54 件)
会議資料 1(6 件) 会議資料 2(9 件) 会議資料 3(4 件) 会議資料 4(3 件)
備品管理 1(4 件) 備品管理 2(3 件) 備品管理 3(9 件) 備品管理 4(6 件)
レビュー 1(2 件) レビュー 2(2 件) レビュー 3(1 件) レビュー 4(2 件)
レビュー 5(3 件) レビュー 6(3 件) レビュー 7(3 件)
事務書類 1(3 件) 事務書類 2(4 件) 事務書類 3(2 件) 事務書類 4(2 件)
事務書類 5(5 件) 事務書類 6(3 件) 事務書類 7(4 件) 事務書類 8(1 件)
事務書類 9(1 件) 事務書類 10(1 件) 事務書類 11(2 件) 事務書類 12(3 件)
その他 1(5 件) その他 2(2 件)

7 日〜12 月 24 日までの Samba ログには，300 個のうちの 135
個のファイルについての共起関係が 834 件記録されていた．

度により 2 つのグループへ細分化されている．

正解セットを作るため，これらのファイルに対して人手に（ 3 ） 図中の要求 1(c) は，(b) のキューブに対してさらにド

よって分類を行って，表 2 のような 39 種類のラベルを付与しリルダウンを行い，アクセス共起度のグループ化の粒度を 20た．
「研究発表」は論文の Tex や発表 ppt ファイル，「イベント」

分割に状態である．この操作により，対象クラスタ「text06」

は会議の参加案内や名簿ファイル，「ソフト開発」ではマニュア

は，3 ファイル，2 ファイル，2 ファイルのグループへと分けら

ルや設定ファイル，アイコン画像などを含む．
「事務書類」は出

れ，より共起関係の強いものだけのグループを生成することが張などの申請書で，同型のテンプレートのものを多く含む．

できる．
次に要求 2 として，「要求 1 で見つけたグループの 1 つと同時

各ファイル間関連度を用いて生成されるクラスタ数はすべて20 個とした．クラスタリングにおけるクラスタ間関連度の計算期に更新したファイルを知りたい」を考える．

法には群平均法を用いている．キーワードが抽出できなかった（ 1 ） 図中の要求 2(a) は，要求 1(c) と同じキューブである．

り，共起関係が存在しないファイル群は未分類グループとして

ここで対象とするグループは「text06 および cooccur02 に属す

まとめるものとした．

セル」に対応するグループとする．

6. 2 実 験 結 果（ 2 ） 図中の要求 2(b) は，(a) のキューブに対してドリルダ

1 つ以上の関連度尺度を用いたグループ化の実験結果は表 3ウンを行い，更新時刻類似度の次元を 10 分割に変更した状態

である．表の 1 列目は関連度の組合せを表し，2 列目はその時である．この時，対象グループは更新時刻類似度のクラスタに生成されたグループ数，3 列目はグループ内の平均ファイル「mtime01」に属しており，要求 2 を満たすには mtime01 に属数，4 列目は全グループのエントロピーの平均値/最大値を表すグループだけに条件を絞ればよいことがわかる．

す．1 つのグループが全て同じラベルを持つファイルから構成（ 3 ） 図中の要求 2(c) は，(b) のキューブに対してスライスされる場合は，エントロピーが 0 となる．まず，各関連度尺度を行い，更新時刻類似度のクラスタ「mtime01」で切断した状を単体で用いて生成されたクラスタの特徴について説明し，次態である．表示されている各セルは，対象グループと同時期にに 2 つ以上のファイル間関連度を組合せた場について述べる．

更新されたファイルのグループに対応する．

6. 2. 1 各関連度尺度単体での特徴

以上のように，本ツールによって容易に複数の関連度尺度を用

テキスト類似度は，平均エントロピーが 4 つの中で最も高く，いたファイルの分類を行うことができる．

6. 評 価 実 験

様々なラベルの混ざったクラスタが出る結果となった．特徴的なクラスタとして，関連する研究内容を扱った「研究発表 1」と「研究発表 2」をまとめたクラスタや，「備品管理 1」と「備複数のファイル間関連度を組合せることで，ファイルのグ

品管理 2」の物品リストや見積書をまとめたクラスタ等が生成

ループ化をよりきめ細かく行えることを確認するため，プロトされた．また，出張届など同型のテンプレートに記入して作成

タイプシステムを使って評価実験を行った．

された事務書類をまとめたクラスタや，複製されたファイル同

6. 1 実験データ

士のクラスタなども確認された．当然ながらキーワードの抽出

今回は実験データとして，著者のホームディレクトリに置かできなかったファイルはグループ化できていない．

れたファイルのうち，表 1 の拡張子を持つもの 300 個を用い

更新時刻類似度でのクラスタでは，大まかな時期ごとには別た．300 個のうち，Hyperestraier でキーワードが抽出できた

れたが，まだ様々な仕事で作成したファイルが混ざった状態でのは 200 ファイルであった．また，実験で用いた 2008 年 8 月あった．更新時刻類似度の場合には 20 の分割ではまだ粗すぎ

—6—

ᦝᣂᤨೞ
㘃ૃᐲ

要求 1 (a)要求 1 (b)

䉝䉪䉶䉴
౒⿠ᐲ

ᦝᣂᤨೞ
㘃ૃᐲ
䉝䉪䉶䉴
౒⿠ᐲ

䊁䉨䉴䊃㘃ૃᐲ

䊁䉨䉴䊃㘃ૃᐲ

䊄䊥䊦䉻䉡䊮䊁䉨䉴䊃㘃ૃᐲ䈱䉂10ಽഀ䊁䉨䉴䊃㘃ૃᐲ䈫䉝䉪䉶䉴౒⿠ᐲ䈪10ಽഀ

ⷐ᳞1:䈖䈱䉪䊤䉴䉺䉕౒⿠㑐ଥ䈪⚦ಽൻ䈚䈢䈇

䊄䊥䊦
䉻䉡䊮
ᦝᣂᤨೞ
㘃ૃᐲ

ᦝᣂᤨೞ
㘃ૃᐲ

要求 1 (c)要求 2 (a)

䉝䉪䉶䉴
౒⿠ᐲ

䉝䉪䉶䉴
౒⿠ᐲ
䊁䉨䉴䊃㘃ૃᐲ

䊁䉨䉴䊃㘃ૃᐲ

䊁䉨䉴䊃㘃ૃᐲ䈪10ಽഀ䉝䉪䉶䉴౒⿠ᐲ䈪20ಽഀ䉝䉪䉶䉴౒⿠ᐲ䈱䉪䊤䉴䉺ᢙ䉕10䈎䉌20䈻
DEIM↳ㄟ䉂೨ᛂว䈞⾗ᢱppt䈫
WebDBf䉝䊑䉴䊃䊤䉪䊃䋧䊘䉴䉺䊷㑐ㅪ䊒䊨䉳䉢䉪䊃䊄䉨䊠䊜䊮䊃䈖䉏䉌䈱૞ᬺ䈫หᤨᦼ䈮ᦝᣂ䈚䈢䊐䉜䉟䊦䉕⍮䉍䈢䈇
ⷐ᳞2:䈖䉏䉌䈱૞ᬺ䈫หᤨᦼ䈮ᦝᣂ䈚䈢䊐䉜䉟䊦䉕⍮䉍䈢䈇

WebDBf⺰ᢥTex䉸䊷䉴䈫PDF

䊄䊥䊦
䉻䉡䊮

ᦝᣂᤨೞ
㘃ૃᐲ

要求 2 (b)要求 2 (c)䉝䉪䉶䉴౒⿠ᐲኻ⽎䊐䉜䉟䊦䈲ᦝᣂᤨೞ䉪䊤䉴䉺m me01䈮฽䉁䉏䉎䊁䉨䉴䊃㘃ૃᐲ

ᦝᣂᤨೞ㘃ૃᐲ
m me01䉝䉪䉶䉴౒⿠ᐲ䊁䉨䉴䊃㘃ૃᐲ

䉴䊤䉟䉴ᦝᣂᤨೞ㘃ૃᐲ
䈪䈘䉌䈮10ಽഀ䊁䉨䉴䊃㘃ૃᐲ䈪10ಽഀ䉝䉪䉶䉴౒⿠ᐲ䈪20ಽഀ
ᦝᣂᤨೞm me01䈪䉴䊤䉟䉴

ⷐ᳞2:䈖䉏䉌䈱૞ᬺ䈫หᤨᦼ䈮ᦝᣂ䈚䈢䊐䉜䉟䊦䉕⍮䉍䈢䈇

図5 利 用 例

Fig. 5 Examples of file grouping

るということが考えられる．
パス類似度のクラスタでは，実際のフォルダ階層に近いクラ係が記録されたファイルの組が多くないこともあり，半数以上のファイルがグループ化できなかった．

スタが生成された．クラスタリングの粒度を細かくすると，階6. 2. 2 複数尺度の組合せ

層の深いところと浅いところのファイルは別れたが，兄弟関係

基本的にどの組合せであってもより細かくファイルのグルーにあるフォルダにあるファイルはなかなか分離されなかった．

プを作ることができたが，特にテキスト類似度やアクセス共起

著者は事務書類を兄弟関係にあるフォルダに置く習慣があるが，度が単体では扱うことができなかったファイル群は，パス類似

これらはクラスタ数 20 では分離できなかった．

度や更新時刻類似度を組合せることで分割された．以下では，

アクセス共起度では，「ソフト開発 1」のソフトウェアのマニュ生成されたグループのうち特徴的だったものについて紹介する．

アルとそのソフトの設定ファイルのクラスタや，「研究発表 2」

テキスト類似度で同じクラスタにされた同型テンプレートのの論文 Tex とコンパイル後の PDF のクラスタ，「レビュー 6」

事務書類は，更新時刻類似度と組合せることで時期ごとに分けの論文とレビュー結果のようなクラスタが生成された．共起関ることができた．それに対しテキスト類似度とパス類似度の組係が抽出できたファイルのグループはかなり純度が高く，それ合せでは，同型テンプレートの事務書類を分けることができな

が平均エントロピーの低さにつながっている．しかし，共起関

かった．これは事務書類を兄弟関係にあるフォルダに置くとい—7—

表 3 実験結果 (各次元クラスタ数=20)

Table 3 Experiment result (20 clusters in each dimension)
尺度

グループ数

平均ファイル数

エントロピー (平均/最大)

備考

Simtext
Simmtime
SimpathSimcooccur

20
20
20
20

15.0
15.0
15.0
15.0

0.369 / 1.105
0.382 / 0.920
0.174 / 1.291
0.064 / 1.270

分類不可 100 件

Simtext × Simcooccur
Simmtime × Simcooccur
Simtext × Simpath
Simmtime × Simpath
Simtext × Simmtime
Simpath × Simcooccur

47
48
57
63
75
42

6.38
6.25
5.26
4.76
4.00
7.14

0.137 / 1.080
0.112 / 1.270
0.112 / 1.045
0.092 / 0.700
0.091 / 0.678
0.080 / 1.302

Simtext × Simpath × Simcooccur
Simmtime × Simpath × Simcooccur
Simtext × Simmtime × Simcooccur
Simtext × Simmtime × Simpath

83
84
100
107

3.61
3.57
3.00
2.80

0.065 / 1.073
0.061 / 0.728
0.053 / 0.678
0.036 / 0.602

Simtext × Simmtime × Simpath × Simcooccur

126

2.38

0.022 / 0.602

う著者の習慣が効いてしまっているためと考えられる．
更新時刻類似度とパス類似度との組合せでは，ソフト開発で用いたアイコン画像など，同じフォルダに一括コピーして置いたままのファイル群がかなり明確にグループとして生成された．
同じフォルダにあっても，何度も編集作業を加えたファイルは別のグループになっている．
アクセス共起度とパス類似度の組合せは，2 種類の組合せの中では平均エントロピーは最も低くなったが，最大エントロ
ピーは最も高い．純度の高いグループとそうでないグループの偏りがあった．

3 種類以上の関連度の組合せでは，さらに細かくグループが生成されている．ただし，今回の実験データでは正解セットのラベルが 39 種類しかないため，過剰に分割されたグループのエントロピーを評価することはしない．

4 種類すべてを組合せた場合は 126 個のグループが生成されているが，ファイル数 10 未満のグループへ分離されないファイル群が 3 つ発見された．これらはいずれも同時期に同じフォルダに一括コピーした画像ファイルだった．今回は画像ファイルに対しては，更新時刻類似度とパス類似度しか手がかりがな
いため，このような結果になった．画像同士の類似度を求める手法も古くから研究されているので，それらの成果を取り入れることも今後の課題である．

7. まとめと今後の課題
本稿では，デスクトップ上のファイルの整理，検索のためのキューブ型ファイルグループ分析ツールを提案した．本ツール
は，様々なファイル間関連度を用いて，ファイルグループの生成の支援を行う．最終的に生成されたグループは，ファイルの整理やデスクトップ検索の検索結果の拡張に利用可能である．
今後の課題としては，複数の利用者のファイル集合を対象にグループ化を行って，出力結果等についてのより詳細な評価を文

分類不可 165 件

献[1] Nitin Agrawal, William J. Bolosky, John R. Douceur andJacob R. Lorch. “A Five-Year Study of File-System Metadata”, ACM Trans. Storage, Vol. 3, No. 3, p. 9, 2007.
[2] Alexander Ames, Carlos Maltzahn, Nikhil Bobb, Ethan L.
Miller, Scott A. Brandt, Alisa Neeman, Adam Hiatt andDeepa Tuteja. “Richer File System Metadata Using Links
and Attributes”, Proc. IEEE NASA Goddard Conference on
Mass Storage Systems and Technologies, pp. 49–60, 2005.
[3] D.K.Gifford, P.Jouvelot, M.A.Sheldoon, J.W.O Toole,Jr.
“Semantic File Systems”, Proc. ACM Symposium on Operating Systems Principles, pp. 16–25, 1991.
[4] Jiawei Han and Micheline Kamber. “Data Mining: Concepts
and Techniques” Morgan Kaufmann, 2006.
[5] Greg Smith, Mary Czerwinski, Brian Meyers, Daniel
C. Robbins, George G. Robertson and Desney S. Tan.
“FacetMap: A Scalable Search and Browse Visualization
Visualization and Computer Graphics”, IEEE Trans. Vis.
Comput. Graph., Vol. 12, No. 5, pp. 797–804, 2006.
[6] Ka-Ping Yee, Kirsten Swearingen, Kevin Li and Marti
Hearst. “Faceted Metadata for Image Search and Browsing,” Proc. CHI, pp. 401-408, 2003.
[7] 石川憲一, 森嶋厚行, 鈴木勇, 杉本重雄. 「共有ファイルサーバにおけるコミュニティ情報管理ツールの提案」第 17 回データ工学
ワークショップ DEWS2006.
[8] 小田切健一, 渡辺陽介, 横田治夫. 「アクセス履歴に基づくファイ
ル間関連度を用いたデスクトップ情報管理ツールの開発」WebDB
forum 2008 (ポスター発表).
[9] 渡部徹太郎，小林隆志，横田治夫．
「キーワード非含有ファイルを検索可能とするファイル間関連度を用いた検索手法の評価」第
19 回データ工学ワークショップ DEWS2008．
[10] 北研二, 津田和彦, 獅々堀正幹．
「情報検索アルゴリズム」共立出
版, 2002.
[11] Google デスクトップ.
http://desktop.google.com/ja/features.html[12] Hyper Estraier.
http://hyperestraier.sourceforge.net/index.ja.html[13] R Project. http://www.r-project.org/[14] Samba, http://us3.samba.org/samba/[15] Windows Search.
http://www.microsoft.com/windows/products/winfamily/desktopsearch/default.mspx

行うことがあげられる．また，ユーザーインターフェースとしての使い勝手の評価も行う必要があると考えられる．
謝辞 本研究の一部は，独立行政法人科学技術振興機構戦略的創造研究推進事業 CREST，および文部科学省科学研究費補
助金特定領域研究 (#19024028) の助成により行なわれた．

—8—