時系列イベント発見のためのグラフクラスタリング手法の提案

本稿では，複数のセンサ群によって取得された人のインタラクションに関連するデータから意味のあるシーンを発見して人の行動にインデキシングを行うことを目的として，インタラクションの主体となる人や物をノードとして表現する重み付きグラフを複数の部分グラフに分割するための非階層クラスタリング手法を提案する．提案手法は，ノードとノードを結合するリンクに与えられた重みが時間にともなって変化するグラフを対象とし，時間の関数として定義される重み付き隣接行列に基づいて部分グラフを効率的かつ柔軟に抽出する．重みが動的に変化するグラフから抽出される部分グラフは，重みの変化に応じて生成や消滅，統合，分裂，拡大，縮小を繰り返す．提案手法では，重みの変化を時系列に追跡し，部分グラフに変化が生じる可能性がある場面においてのみ評価計算を行う．これにより，時間的かつ空間的に幅広い観点から評価できる．今回，ポスター展示会場という開放的な空間において人のインタラクションを観測し，人が集団で討論を行っているシーンや，複数の人が同じ展示物を見ているシーンを自動的に抽出することにより，提案手法の有用性を確認した．また，提案手法は強力なデータマインニングツールとして幅広く利用可能であり，たとえば複数人の会話の流れを構造化したり，ハイパーテキスト構造を有するWeb ページの関連性を発見したりするなど，様々な事例に適用できる．