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

情報処理学会 Web Site 被引用文献3件

書誌事項

タイトル別名
  • ジケイレツ イベント ハッケン ノ タメ ノ グラフクラスタリング シュホウ ノ テイアン
  • Detecting Time Series Events by Graph Clustering
  • 知識処理

この論文をさがす

抄録

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

This paper proposes a new non-hierarchical clustering method, which divides weighted graphs into some significant subgraphs. Our goal is to find significant scenes using interaction data captured by multiple sensors and to add meaningful indices to human activities. Therefore, we express people and objects which consist of interactions as nodes. Our target is the graphs where weights associated with links are changeable while, on the contrary, the targets of conventional clustering methods are those where weights are fixed. In short, proposed method can divide those graphs whose weights can be defined as time functions into some subgraphs according to their weighted adjacency matrices. Subgraphs are often created, extinguished, divided, expanded, and diminished according to the change of weights. Proposed method watches the change of subgraphs and judge whether they change only when they can, which results in flexible evaluations from spacio-temporal viewpoint. We have confirmed the usefulness of proposed method by the experiments to find such significant scenes automatically as, for example, those where people discussed together and those where people watched something together, in poster exhibitions. Moreover we believe that proposed method is widely available as a useful tool for data mining and can be applied to many problems.

収録刊行物

被引用文献 (3)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ