TriMine: 複合イベントデータの時系列解析と将来予測

概要

多くの Web アプリケーションにおいて、時系列ログデータは高速かつ大量に生成され続けています。例えばWeb ホスティングサービスでは、ユーザとURLの情報を伴う何百万ものアクセスログが毎時刻生成されます。本研究では、主にWebクリックデータを対象として、大規模な時系列ログデータを効率的に分析し、イベント情報の将来予測を高精度かつ高速に行うためのアルゴリズムの開発に取り組んでいます。

trimine_goal

提案手法とその特徴時系列ログデータは、例えばWeb クリックデータの場合 {URL, user ID, timestamp, access devices, http/document referrer} のように、複数の属性から構成されます。このようなログデータを本研究では複合イベントと呼びます。そして、複合イベントシーケンスが与えられたとき、潜在的なトピックとその傾向を見つけ、将来のイベントを高速に予測する新手法を考案しました。

提案手法とその特徴

本研究では、複合イベントのシーケンスを3階のテンソル (u × v × n) に変換することで解析を行います。テンソルの各要素 (i, j, t) は、時刻tにおいて i 番目のオブジェクト (URL) に j 番目のアクター (user) が 出現した頻度を示しています。 例えば (‘cnn.com’, ‘Smith’, ‘3pm June 1, 2003’; 23) であった場合、「ユーザ Smith が cnn.com へ 2003 年 6月1日の午後3時から4時の間に23回アクセスした」ことを表しています。

提案手法であるTriMineは (object,actor,time) の3要素に対して潜在的なトピックを発見し、テンソルXを3つのベクトル (Object vector, Actor vector, Time vector) に分解します。各ベクトル内の要素は、トピック#1, #2, . . ., #k に対する関連度の強さを表現しています。

trimine_tensor

以下の図では、実データに対してTriMineを用いて分析を行なった結果を示しています。それぞれの潜在的トピックに対して、 (object , actor , time) の 3 つの要素がどのように分布しているかを表しています。ここでは最も頻出する 3 つのトピック について可視化しており、分布の傾向か らそれぞれのトピックに対して business、media、drive とラベルを付けています。予測精度など、具体的な実験結果については、関連研究で詳細を示しています。

trimine_result
関連文献
  • Yasuko Matsubara, Yasushi Sakurai, Christos Faloutsos, Tomoharu Iwata, Masatoshi Yoshikawa,“Fast Mining and Forecasting of Complex Time-Stamped Events”, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 271-279, Beijing, China, August 2012. [pdf] [ppt] [code]