DEIM Forum 2016 G4-4

生態系モデルに基づくオンライン活動データの非線形解析
松原 靖子†

櫻井保志†

Christos Faloutsos††† 熊本大学自然科学研究科情報電気電子工学専攻†† Dept. of Computer Science, Carnegie Mellon University
E-mail: †{yasuko,yasushi}@cs.kumamoto-u.ac.jp, ††christos@cs.cmu.edu
あらまし

本論文では，大規模オンライン活動データのための非線形解析手法として E COW EB (Ecosystem on the Web)について述べる．本研究では，“Xbox”, “PlayStation”, “Wii” 等のオンライン検索キーワードの出現件数に関する時系
列データが与えられたとき，それらのキーワード間の潜在的な関連性や競合性，そして季節性等の重要なパターンを自動抽出することを目的とする．より具体的には，オンラインユーザ活動の推移パターンを，自然界の生態系における種内・種間競争として捉えることで，潜在的なユーザ資源 (ユーザの興味，時間等) を各アクティビティ (Xbox 等のキーワード) がどのように共有，あるいは競合しているかを非線形動的システムとして表現する．本研究ではさらに，非線形性を有する競合関係パターンを学習するためのアルゴリズムとして E COW EB -F IT を提案する．提案アルゴリズ
ムは，パラメータのチューニングを必要とせず，計算量は入力データのサイズに対して線形である．実データを用いた実験では，E COW EB が様々なオンライン活動における長期的な非線形パターンや季節性等の重要なトレンドを発見し，さらに，長期的な将来予測を高精度に行うことを確認した．
キーワード

生態系モデル，時系列データ，非線形動的システム

1. ま え が きFacebook や Twitter を始めとするオンラインメディアの発展と，Web 上でのユーザ活動の活発化に伴い，社会活動，経済

相当し，Web 上において，d 個のキーワード（アクティビティ）がユーザ資源を取り合うことで競合関係を形成し，さらに，季節性を伴いながら推移を繰り返すようなシステムであると仮定する．

活動等における行動分析の機会が増えつつある [1], [2], [7], [8].

本論文では，大規模オンライン活動データのための非線形

例えば，“Xbox”, “PlayStation”, “Wii” 等のオンライン検索キー解析手法である E COW EB (Ecosystem on the Web) について述べワードの出現件数に関する時系列データが与えられたとき，本る [3]（注 1）. より具体的には，以下の問題を扱う．

研究の目的は，それらのキーワード間の潜在的なパターンやルールを発見することで，社会学的，行動学的な分析，あるいは，市場調査等の重要なタスクを実現することである．
一般に，従来の時系列データ解析手法では，フーリエ変換，

d 個のキーワード（アクティビティ），n の期間で構成される大規模時系列データ X = {x1 , · · · , xd } が与えられたとき，以下の重要なタスクを解決する．

•

ウェーブレット変換，あるいは，自己回帰モデル (AR: autore-

潜在的な競合関係の発見（“Xbox” vs. “PlayStation” 等）•

gressive model), カルマンフィルタ (KF: Kalman filters) 等の既存

季節性の発見（クリスマス，夏休み等）•

将来のユーザの行動予測技術を用いて特徴分析を行うが，これらの手法では，ドメイン
知識に応じた特徴的なパターンをモデル化することができない．

具体例. 図 1 は，Google（注 2） におけるビデオゲーム産業に関連

しかしながら，多くの場合，時系列データは，ドメインに応じする d = 4 個のアクティビティ：“Xbox” (x1 ), “PS2, PS3” (x2 ),た潜在的なルールに従い自然に生成されるものであり，それら“Wii” (x3 ), “Android” (x4 ) のクエリ検索数に対する E COW EBのダイナミクスを理解し表現することで，従来手法にはない，の解析結果を示している．ここでは，2004 年から 2014 年にかより柔軟な時系列解析を行うことができる．例えば，本研究でけて，週毎のデータを用いている．E COW EB は，以下のような扱う Web 上の検索キーワードの時系列データは，ユーザのオ重要なパターンを発見することができる．

ンライン活動のパターンに基づき生成されるため，ユーザの潜•

長期的な非線形パターンの学習: 図 1 (a) は，4 つのアク在的な行動パターンを理解することで，データを新たな側面か

ティビティ（キーワード）に対するオリジナルデータ（丸ら解析することができる．より具体的には，本研究では，キー印）と学習結果（実線）を示している．図からも明らかな

ワード（アクティビティ）毎の活動量（検索数）の推移を，自ように，提案モデルは年単位の周期性や，長期的な成長，然界の生態系 (ecosystem) における種 (species) の個体数の推移

減衰パターンを柔軟に表現している．例えば，2006 年にとして捉えることにより，Web 上の活動を非線形動的システム

発表された “Wii” の成功に伴い，競合関係にある “Xbox”

としてモデル化する．ここで，自然界の種 (species) に対する食料資源 (food resources) は，Web 上でのキーワード（アクティビ（注 1）：http://www.cs.kumamoto-u.ac.jp/∼yasuko/software.html

ティ）に対するユーザ資源（ユーザの時間，お金，興味等）に（注 2）：http://www.google.com/trends/

0.8

b1

Xbox

Black Friday
0.4

1

0.6

2

3

Play
Station

Wii

0.4
0.2
0
2004

Christmas

B (k=1)

2006

2008
2010
Time (weekly)

2012

Value

Volume @ time1

Fitting result − RMSE=0.058817

x1
x2
x3
x4

Summervacation

04
Android

2014

E3
0.2

(a) E COW EB の学習結果(b) 競合関係ネットワーク
図 1 E COW EB を用いた特徴自動抽出と出力結果．

Jan Mar May Jul Sep Nov
Time (weeks)(c) 季節活動パターン

Fig. 1 Modeling power of E COW EB: Our algorithm is fully automatic, requiring no user intervention.

••の検索数は一時的に低下している．その後 2011 年にかけ

ジャングルには，様々な生き物が生息している．例えば，複数て “Wii” の人気が低下傾向にあるが，これはおそらく，従のクモザルとリスザルが，同じテリトリー内においてバナナを

来の Wii のユーザが，モバイル端末 “Android” によるソー食べて集団生活をしている場合，次の時刻（例えば，来月，来シャルゲームへと興味を移したことによる影響であると考年等）には，何頭のクモザルが見込まれるだろうか．これは，えられる．

個体群生態学における重要な研究対象であり，生物の個体数の種間競合関係: E COW EB は，近年のオンラインソーシャル

推移を数学的にモデル化することは重要な課題である [5], [6].

ゲーム参入に伴うビデオゲーム産業界における競争関係の生態系における競合関係. 生態系における競合関係を表現する

複雑化を自動的に抽出することができる．図 1 (b) は，4にあたり重要なのは次の 2 つのメカニズムである．(a) 制約をつのアクティビティ（キーワード）に対する潜在的な関係伴わない上での成長：無限大の食物資源があると仮定した場合性を表現した，競合関係ネットワークである．各エッジはの個体の増加率 r．例えば，リスザルの各個体が次の時刻に r

2 つの異なるキーワード間の競合度を示しており，より太

匹の子を産むような状態．(b) 食物資源と種内・種間競争：有限いエッジは，より強い関係性を示す．例えば，“Wii” からの食物資源が与えられた上での（つまり，環境収容力 K に対“Android” の間の赤いエッジは，ユーザの興味が，“Wii” かする）個体の最大数 K の制限．ここで，種内競争とは，同種にら “Android” へ移っていく様子を表現している．同様に，よる競合（例えば，2 匹のリスザルが果物を奪い合う状況）で“Xbox” は，“PlayStation”，“Wii” と強い競合性（青線）があり，種間競争とは，異なる種による競合（リスザル対クモザあり，2007 年から 2010 年にかけて一時的な減衰パターン

ル）を示す．この競合関係は，種の個体数の爆発的増加を防ぐを有していることがわかる．

効果を持つ．例えば，生態系においてリスザルの個体数が多く，季節性を伴うユーザ活動: 図 1 (c) は，4 つのキーワードに果物の数が少なければ，競争は激化し，リスザルの個体数の成共通する周期的な時系列パターンを示している．具体的に長は制限される．

は，年単位の周期性を持ち，11 月の “Black Friday” と 12

上記の現象を表現するための最もシンプルな方法として，ロ月のクリスマスに大きなスパイクを持ち．さらに，毎年 6トカ・ボルテラの競争モデルが挙げられる [4]. このモデルは，月頃に開催される世界最大のコンピュータゲーム関連の見

次の非線形微分方程式を用いて，d 種の競争関係を表現する．
!
PddPi
j=1 aij Pj, (i = 1, 2, . . . , d)(1)
= r i Pi 1 −dt
Ki

本市：E3 (Electronic Entertainment Expo) に関連するスパイ
ク，そして夏休みにかけての中期的なピークを伴う．
本論文の貢献. 本研究では，生態系モデルに基づくオンライ
ン活動データの非線形解析手法である E COW EB を提案する．

ここで，

E COW EB は次の特長を持つ．

•

Pi : i 番目の種の個体数．

（ 1 ） 提案モデルは，潜在的な競合関係や季節活動等の時系列•

ri : i 番目の種の成長率．密度調整が生じない場合の繁殖率に相当する (ri >
= 0).

•

Ki : i 番目の種の（競合種が存在しない場合の）環境収容力 (Ki >= 0).

（ 3 ） 既存手法と比較し，高精度でのパラメータ学習を高速に•行うと同時に，非線形性を有する時系列パターンの長期的•

aii : 種内競争．i 番目の種内における食料資源競争 (aii = 1).
aij : 種間競争．異なる 2 種間での競合関係 (aij >= 0).

な予測を行うことができる．

このとき，時刻 t は連続値であり，dPi /dt は導関数とする．iパターンを柔軟に表現し，ユーザの直感に合致した重要な特徴を自動的に抽出する．
（ 2 ） 計算コストは入力データのサイズに対して線形である．

2. 背

景

番目の種に対し，現在の個体数 Pi に対し成長率 ri で毎時刻繁殖していく．このモデルは，複数の種間において，共通の

ここで，実世界のジャングルにおける生態系を考えてみる．

資源をめぐり競争関係が生じている状態を表現する．図 2 (a)

草や果実を食べる草食動物や，その草食動物を狙う肉食動物等，は，実世界のジャングルにおける野生動物の関係性を示してい表1

る（注 3）. これらの種が，果物や木の実等の食物資源を共有し，特アナロジー：ジャングルと Web における生態系の比較．

Table 1 Analogy: Jungle vs. Web.

定の地域で共生していると仮定すると，i 番目の種が摂取する
食物資源を共有している種の個体総数は，次の式で表現されP
る：ai1 P1 + · · · aij Pj · · · Pi + · · · aid Pd = dj=1 aij Pj . ここで，aij (i =| j) は，種間競争係数と呼ばれ，i 番目の種に対する j 番
目の種の影響力の強さを表す．

ジャングル

Web

種 (リスザル, カピバラ)

キーワード・アクティビティ (Wii, Xbox）

食料資源 (果物, 草)

ユーザ資源 (子供，成人)

個体数

注目度

気候・季節

季節のイベント (クリスマス)

3. 提案モデル
等のビデオゲームに興味を持つが，大抵の成人は，アンド

本章では，提案モデルである E COW EB について述べる．本研究で扱うオンライン活動データ：X = {x1 , · · · , xi , · · · , xd }は，d 個のキーワード，n の期間で構成され，xi は，i 番目のキーワードのシーケンス (xi = {xi (t)}nt=1 ) を表す．本研究の目的は，時系列データ X が与えられたとき，(a) X の非線形ダ
イナミクスを表現し，(b) 各シーケンス間の潜在的な関係性を発見し，(c) 将来のオンライン活動を予測することである．
ここで，異なる 2 つのキーワード間の関係性というものはどのように表現することができるだろうか．例えば，Xbox や Wiiの間の関係性，あるいは，Facebook と LinkedIn の違いとは一体なんであろうか．これらの Web 上のキーワードは，自然界の野生動物のように競合関係にあると言えるだろうか．
提案モデルの概要. Web 上の生態系とはどのように定義できるだろうか．Web における仮想的なコミュニティの中に，自然界と類似した現象は見られるだろうか．本研究では，Web 上に様々な仮想的な種 (virtual species) が存在し，それらの種が相互作用することにより，時間発展していくと仮定する．
図 2 (b) は，Web における生態系を表している．自然界のジャングルにおいて，クモザルやカピバラが生息しているように，

Web 上の空間にも Xbox, PlayStation のような仮想的な種（アクティビティ）が存在している．
以下では，提案モデルに対する 2 つの重要なアナロジーについて述べる．

•

キーワード（アクティビティ）= 種 (species): Web 上のキー
ワードは，ユーザからの興味を得ることで存在しており，自然界に生息する生物のように振る舞う．例えば，キーワード（Wii）とユーザ（子供）の関係は，リスザルと果物，あるいは，カピバラと草の関係に似ている．ジャング
ルにおいても，Web 上においても，資源なしに種は生存できない．

•

ユーザ資源 = 食料資源: ジャングルの生態系と同様に，Web
上には多くのユーザとユーザ資源が存在する．ここでのユーザ資源とは，例えば，ユーザの興味や注目，時間やおロイドを好む．
ここでさらに，上記のアナロジーに加え，本研究では次の 3 つの要素が必要となる．

•(G1): キーワードの非線形時系列パターン•(G2): 異なるキーワード間の競合関係•(G3): ユーザ活動の季節性
自然界の生態系では，種の個体数は，繁殖率や各個体の寿命に基づき，緩やかに時間発展していく．Web 上においても，各
キーワードの注目度（つまり，各ユーザの興味や関心の量）は時間とともに推移していく．もし，ある新商品（アンドロイド
等）が魅力的であった場合，多くのユーザがその商品に注目し，友人や他のユーザに推薦する．これにより，この商品の注目度
は指数関数的に成長する．本研究では，このような非線形的な時系列パターン (G1) を表現するために，非線形差分方程式を用いる．
続いて，異なる 2 つのキーワード間の潜在的な関係性 (G2)について考える．例えば，図 1 (a) において，Xbox x1 のシーケ
ンスは，PlayStation x2 のシーケンスと逆向きの成長のパターンを持つ．例えば 2007 年から 2010 年にかけて，PlayStation の値が増加している一方で，Xbox は減少傾向にある．つまり，これらの 2 つのキーワードは潜在的な競争関係にあると言える．
最後の要素は，年単位の周期性 (G3) である．例えば，図 1(a) において，全ての時系列シーケンスが，クリスマスのスパ
イクを有する．これは，ユーザの行動パターンが季節やイベン
トに応じて変化しているためである．自然界における野生動物
についても，天候の変化や季節に応じて行動を変化させる現象が見られる．
表 1 は，ジャングルと Web における生態系のアナロジーを示している．本研究では，Web 上のユーザの活動とアクティビ
ティの推移を，ジャングルの生態系における種内・種間競争として捉えることで，潜在的なユーザ資源をキーワード間でどのように共有，競合しているかを表現する．
次節では，提案モデルの詳細を示す．

金等に相当する．一般に，ユーザは，同時に複数の目的

3. 1 EcoWeb-基本モデル (G1)

（アクティビティ）のために時間や興味を消費することができない（注 4）．図 2 (b) に示すように，ユーザには様々なグループが存在する．例えば，子供は Xbox, PlayStation, Wii（注 3）：Image courtesy of xura, criminalatt, David Castillo Dominici, happykanppy at FreeDigitalPhotos.net.

（注 4）：例えば，N 人のユーザがいる場合，1 日あたり最大で N × 24 時間のユーザ資源が存在する．各キーワードに対するユーザ資源の量は，対象とする
キーワードの種類や，各ユーザの興味の対象により変化する．

ここでは，最も簡単な場合として，種間競争の生じない状況，
つまり，独立した単一のキーワードに対するシーケンスのモデル化について述べる．K を，単一のキーワードに対するユーザ
資源の上限（環境収容力），p を初期状態（時刻 t = 0）においてすでに消費されているユーザ資源の量とする．提案モデルでは，次のルールに従いアクティビティが推移すると仮定する．

•

種内・種間競争が生じない場合には，現時刻の注目度（つ4"#$56&))(7###*+,-(./#!"#$%&'()##*+,-(./#

8"#92:2;/#

0"#12%.32)2/#(#%&'!"#$%&'

2"#34+5#)"*&&'!"#$%(a) ジャングルの生態系
図26"#711#-"#.,/0+1/#&''($%)#*+,$%(b) Web 上の生態系

ジャングル（アマゾン熱帯雨林） と Web 上（ゲーム産業）における生態系の比較．

Fig. 2Illustration of jungle (e.g., Amazon rainforest) vs. Web (e.g., game industry).

まり，ユーザの興味の量）が維持される．

•!"#$%&'()&*+,#

時刻 t において，新たなユーザ資源を得ることで，成長率r で注目度が成長する．
P (t) を時刻 t におけるキーワードの注目度とすると，単一のの潜在的なユーザ資源の割合は，次式で表現される．
!
Pd
j=1 aij Pj (t)
,
1−
Ki

(4)

キーワードに対する時系列パターンの推移は次の差分方程式で競合関係係数 aij は，i 番目のキーワードに対し j 番目のキーワー表現される．

ドが影響を与える割合を示す．ここで，もし i 番目と j 番目のキーワード間に競合がない場合には（つまり，aij = 0 (i =| j)），



P (t)
,
P (t + 1) = P (t) 1 + r 1 −
K


(2)

aij = aji = 1 である場合には，2 つのキーワードは完全に同じ

さらに，P (0) = p は初期状態を示し，•中立関係が成り立ち，このモデルは式 (2) と同等である．逆に，

P (t): 時刻 t におけるキーワードの注目度（各ユーザにおけるキーワードへの注目量の総和）

ユーザ資源のグループを共有する強い競合関係を持ち，さらに，

aij = 1, aji = 0 だった場合には，片害関係を持つ．この場合には，i 番目のキーワードが j 番目のキーワードに強い影響を与•p: 初期状態，時刻 t = 0 における注目度.

•

r: 成長率, キーワードのユーザに対する魅力の強さ．

•

K: 環境収容力, つまり，キーワードに対するユーザ資源

えられる一方で，j 番目のキーワードは i 番目のキーワードからの干渉を受けない．

3. 3 EcoWeb-季節活動モデル (G3)

（注目度）の上限値．
i
h

(t)
は，現時刻における注目度 P (t)ここで， 1 + r 1 − PK(t)が，次の時刻における成長へ貢献する率を表し， 1 − PK

的な非線形ダイナミクスを表現するモデルについて議論したが，は，キーワードの時刻 t におけるユーザ資源の残量率を示す．

ある．Xbox や Amazon 等のキーワードは，常に一定数のユー

例えば，もしキーワードに対するユーザ資源が尽きた場合（つザが興味を持っているが，実際のユーザの行動は様々なイベン

まり P (t) = K ）には，注目度は定数へと向かう．さらに，式トにより変化している．例えば，Black Friday には Amazon.com(2) は，単一の種の場合 (d = 1) のロトカ・ボルテラ競争モデル

へのアクセスが集中し，普段より多くのユーザが見込まれる．

（式 (1)）を離散的に表したものと同等である．

これは，自然界の生態系においても見られる現象である．例

3. 2 EcoWeb-競合関係モデル (G2)

これまでは，d 個のシーケンス集合が与えられた場合の長期

Web 上の日々の詳細な活動パターンを表現するには，不十分でえば，大抵の場合，サルは，暖かで明るい日中に活動し，夜は次に，複数のキーワード間の競合関係 (G2) について述べる．

睡眠をとる．そして，このような季節性を伴う行動は，他の種一般に，関連するキーワードは共通のユーザ資源を持つ．例え（キーワード）と関連していることが多い．例えば，Amazon をば，Xbox と PlayStation の間には明らかな競合関係が存在して含む多くの小売店では，Black Friday に最も売上が集中する．そおり，大抵の場合，ユーザは，価格や好みのゲームタイトル等

こで本研究では，上記の現象を反映するため，季節活動パターに応じて 1 つのゲーム機を選択，購入する．

ン (G3) のための次のモデルを提案する．

［モデル 1］（E COW EB-競合関係） Pi (t) を，i 番目のキーワー［モデル 2］（E COW EB-full） Ci (t) を i 番目のキーワードの時

ドの時刻 t における注目度とする．E COW EB-競合関係モデル

刻 t における推定量とする．提案モデルは次式を用いてユーザ

は，次の式で表現される．
"の季節性を伴う活動を表現する．

Pi (t + 1) = Pi (t) 1 + ri

1−Pd

j=1 aij Pj (t)Ki!#

Ci (t) = Pi (t) [1 + ei (t)],(i = 1, · · · , d), (3)
ここで，ri > 0, Ki > 0, aii = 1, aij >= 0, Pi (0) = pi とする．
モデル 1 では，複数のキーワードが共通のユーザ資源に対し競合していると仮定する．時刻 t における，i 番目のキーワード(i = 1, · · · , d),(5)

ここで ei (t) は，i 番目のキーワードの季節活動パターンを表現する．
推定量 Ci (t) は，i 番目のキーワードが時刻 t において出現
した回数を示し，潜在的な注目度 Pi (t) と季節活動パターン

E = {ei (t)}d,ni,t=1 に依存する．E の各要素は，潜在的な注目度と実際のキーワードの出現回数の相対値を示し，祝日等の季節のイベントに関連する．もし，i 番目のキーワードが時(k = 1, 2, . . . )．

刻 t における季節活動パターンを持たない場合には（つまり季節活動パターンの発見. まず，最も単純な部分問題として，ei (t) = 0），キーワードの出現回収は潜在的な注目度と一致し，シーケンス X と基本パラメータ集合 {p, r, K, A} が与えられ

Ci (t) = Pi (t) となる．

ている場合を考える．モデル 1, モデル 2 に基づき，季節活動パ

季節活動パターンの表現と圧縮. データ集合 X における全てのターン E は，次式で計算される：

季節活動パターン E を表現するためには，合計で d × n 個のパラメータを必要であり，このままでは冗長で扱いにくい．さらに，ここでの重要な目的として，(a) Black Friday 等の周期的ei (t) =xi (t) − Pi (t)(i = 1, . . . , d; t = 1, . . . , n).
Pi (t)(7)

次に提案手法は，計算した E に対し，要約情報として W, B

なパターンの発見，(b) 小売店セール等の潜在的な季節活動グを計算する．ここで，W, B の最も簡易的な計算方法として考ループの発見を行いたい．そこで，本研究では，より純度の高えられるのは，長さ n の d 個の各シーケンスを，k = d 個の異いモデル化を行うために，E を分解する手法を提案する．より

なる季節活動パターンとして表現することである．しかし，こ具体的には，提案手法は，E を次の 2 つの行列に圧縮，およびの方法は，全シーケンス X を表現するために，d × n 個の独立分解する：季節行列 B (サイズ (k × np )), 重み行列 W (サイズ

したパラメータ集合が必要となる．この方法は，複数のシーケ(d × k)). ここで，B は長さ（周期） np の k 個の潜在的な季節行

ンス間の共通するパターンを表現することができないため，モ

列の成分であり，W は季節行列の成分が，各シーケンスに及ぼ

デルとして不十分である．

す影響（重み）を表す．まとめると，季節活動 E = {ei (t)}d,ni,t=1は，次式で表現される．

ei (t) ≃ f (i, t|W, B) =ターンを発見するための新たなアルゴリズムを提案する．図 4kXwij bj (τ ) (τ = [tmod np ])(6)

j=1

ここで，

•

np : 周期（1 年 =52 週）．

•

k: 季節行列における成分の数．

•

W = {wij }d,ki,j=1 : 重み行列, i 番目のキーワードの j 番目の成分への影響（重み）．

•

k,n

p
: 季節行列, 時刻 τ における j 番目の成分
B = {bj (τ )}j,τ =1の大きさ．
さらに，季節行列における成分の数 k は，自動的に推定するべきであり，詳細については次章で述べる．

EcoWeb- パラメータ集合. 図 3 は，提案モデルの概要を示す．d次元のシーケンス集合 X が与えられたとき，本研究の目的は，次の 3 つの重要な要素を自動抽出することである．(G1) 基本
要素：初期注目度: p = {pi }di=1 , 成長率: r = {ri }di=1 , 環境収容力: K = {Ki }di=1 ; (G2) 競合行列: A = {aij }d,di,j=1 ; (G3) k 個の
季節活動パターン (重み行列 W, 季節行列 B).
［定義 1］（EcoWeb のパラメータ集合） S を X を表現する全パラメータ集合 S = {p, r, K, A, W, B}) とする．

4. 最適化アルゴリズム
本章では，モデルの学習アルゴリズムである E COW EB -F ITについて述べる．より具体的には，次の 2 つの課題：(1) 最適な
季節活動パターン（つまり W, B）の発見，(2) データ X に対する最適なパラメータ集合 S の推定に取り組む．

4. 1 季節活動パターンの自動分析
まず，1 つ目の課題として，最適な季節活動パターン W, Bの発見について述べる．この課題は，次の 2 つの部分問題に分
解される．

•
•

そこで本研究では，与えられた X に対する最適な季節活動パ

季節活動パターンの発見：成分の個数（サイズ）k が固定

は，提案アルゴリズムの概要を示している．季節活動 E が与えられたとき，提案アルゴリズムは，各シーケンスを長さ np の部分シーケンス集合に分割し，行列 Ê を生成する．ここで，Êのサイズは [d × ⌈n/np ⌉] × np である．次に，行列 Ê から k 個の成分を発見し，季節行列 B を生成する．重み行列 W は，式(6) を用いて，行列 E の復元エラー（E ≃ f (W, B)）が最小となるものを選ぶ．ここで重要な課題として，Ê の中から最適な
季節活動パターン B を抽出する手法が必要である．まず挙げられるのは，主成分分析 (PCA: principal component analysis) を用いた方法である．しかしながら，PCA は時系列データの重要な成分を発見することができる一方で，直行成分しか扱えないという短所がある．そこで本研究では，独立成分分析 (ICA:

independent component analysis) を用いた情報抽出手法を行う．
ICA は，PCA とは異なり，ガウス性を持たないシーケンスに対し，統計的に独立な成分を k 個発見することができる．
自動成分分析. 次に，成分の最適な個数 k の推定方法について議論する．本研究では，季節活動パターンを表現する 2 つの行
列 W, B の最適なサイズを自動的に推定するために，最小記述
長 (MDL:minimum description length) に基づく符号化スキームを導入する．直感的には，データがより圧縮できれば，よりよいモデルであるとみなす．

E COW EB の全パラメータ集合 S の表現コストは以下の要素から構成される：次元数 d，および，時系列の長さ n：log∗ (d)+ log∗ (n) ビット（注 5）．初期注目度, 成長率, 環境収容力 (つまり{p, r, K}) と競合行列 A にそれぞれ，d × 3 と (d × d − d) のパ
ラメータを要する．つまり，CostM (p, r, K) + CostM (A) =cF · d(3 + d − 1) と な り，cF は 浮 動 小 数 点 の コ ス ト を 示
す （注 6）．同様に，k 個の季節活動成分は，CostM (k, W, B) =log∗ (k) + log∗ (np ) + cF (dk + knp ) で表現される．
モデルパラメータ集合 S が与えられた上での X の符号化コされた上での季節活動行列 W, B の最適化．

（注 5）：ここで，log∗ は整数のユニバーサル符号長を表す．

自 動 成 分 分 析：最 適 な 成 分 の 個 数（ サ イ ズ ）k の 推 定（注 6）：本論文では浮動小数点を cF = 8 ビットにデジタイズした．

Initial Growth Carrying
popularity rate capacity

Original data

p

(G1)

d

d

d

(G2)

d

d

,
1

n
図3

K

1

{

≅

X

r

Interaction
matrix

1

1

(G3)

A

1

Participation
matrix!"W×

Seasonality
matrix

B
k

np

d
1

d

,

}

k

E COW EB の概要．提案手法は d 次元のシーケンス X から重要なパターンを自動抽出する．
Fig. 3 Illustration of E COW EB structure. Given a set of d sequences X of length n, we extract important properties of online activities: (G1) (G2) (G3).

E

d

列 A，(G3) 季節活動パターン {W, B} を同時に学習したい．

!"#"$%!"#&$%!"#'$%!"#($%!"#)$%!"#*$%

最もシンプルな方法として挙げられるのは，S 内の全てのパ!&#"$%!&#&$%!&#'$%!&#($%!&#)$%!&#*$%

ラメータの最適解を見つける方法である．しかしながら，これ!"#"$%!"#&$%!"#'$%!"#($%!"#)$%!"#*$%

 n  ! #"$%
 n p  ! #'$%&!&#&$%&!&#($%!&#)$%!&#*$%d
×は (3d + (d2 − d) + k(d + np )) 個のパラメータを同時に推定すnÊ

る必要があり，現実的でない．さらに，季節活動パラメータを最適化するために，k (1 <=k<= d) 個の異なる解のコストを計B

算しなくてはいけない．

!"#"$%!"#&$%

そこで本研究では，全パラメータ集合 S を 2 つの部分集合k{p, r, K, A}, と {W, B} に分けて反復的にパラメータを推定す!&#"$%!&#&$%る手法として，S TEP F IT を提案する．より具体的には，提案アルnp

ゴリズムはまず，季節活動パターンが存在しない状態（k = 0）npを仮定し，基本パラメータ集合を学習する．次に，4. 1 節で示

図4

季節活動パターンの発見の概要（np = 2 の場合）．

したように，自動成分分析を用いて最適な B と W を発見する．

Fig. 4Illustration of seasonal component analysis (for np = 2).

コスト関数（式 (8)）の最小化には，非線形性を有する学習に適ストは，ハフマン符号を用いた情報圧縮により，負の対数尤度したレーベンバーグ・マルカート法 (LM: Levenberg-Marquardt)

を用いて次のように表現することができる：

を用いる．

CostC (X|S) =しかしながら，依然として S TEP F IT は，d 個のシーケンス集合

Pd,n

−1
i,t=1 log2 pGauss(µ,σ 2 ) (xi (t) − Ci (t)),のための基本パラメータ {p, r, K} に加え，サイズ (d × d) の競

ここで xi (t) と Ci (t) はぞれぞれ，i 番目のキーワードの時刻 t

合行列 A の更新コストを必要とする．言い換えれば，S TEP F ITにおけるオジリナルデータと推定値 (モデル 2) を示す．さらに，は，d 個のキーワード全ての間の関係性 (競合関係) を同時に推µ, σ 2 はそれぞれ，オリジナルデータの値と，推定値の間の平定しなくてはならない．一般に，非線形モデルにおける多数の（注 7）

均，分散を示す．まとめると，パラメータ集合 S に対するパラメータの同時推定は，最適解の学習が非常に難しく，計算コストも高い．そこで本研究では，全パラメータ集合 S を高速

データ X の符号長は次の式で与えられる．

かつ効果的に推定するためのアルゴリズムとして E COW EB -F IT

CostT (X; S) = log∗ (d) + log∗ (n) + CostM (p, r, K)を提案する．

+CostM (A) + CostM (k, W, B) + CostC (X|S) (8)結論として，提案アルゴリズムは，季節活動成分の最適な個数 kopt を，次式で求めることができる：kopt = arg mink

CostT (X; S).
4. 2 学習アルゴリズム
ここまでは，シーケンス X に対する基本パラメータ集合{p, r, K, A} が与えられている場合に，どのようにして季節活
動行列 {W, B} を発見するかについて述べた．次の課題は，全てのパラメータ集合 S を高速かつ効率的に推定することである．
具体的には，(G1) 基本パラメータ集合 {p, r, K}，(G2) 競合行

EcoWeb-Fit. E COW EB -F IT は，S TEP F IT を拡張し，大規模なシーケンス集合 X の中から重要なパターンを高速に学習する手法である．具体的には，S TEP F IT が X のパラメータを同時に学習するのに対し，E COW EB -F IT はまず種間競争が存在しない状態を仮定した上で（つまり，A = Id , aij = 0 (i =| j)) として），各キーワード xi (i = 1, . . . , d) を独立シーケンスとして扱い，各モデルパラメータ Si = {pi , ri , Ki , wii , bi } を個別に学習する．ここで，Si の学習には S TEP F IT を用いる．次に，i
番目と j 番目の二つの異なるキーワードに対し，競合関係がある場合を仮定し，最適な競合ペア (xi , xj ) として，コスト関数

CostT (xi , xj |Sij ) を最小化するような全てのシーケンスペアを見つける．最後に，全体のシーケンス集合 X に対し，S TEP F IT

（注 7）
：ここで， µ, σ 2 は 2cF ビットを要するが，これらのコストは定数である
ため，モデル推定の際には除外することができる．

を用いて全パラメータ集合 S を最適化する．

Depot と Lowes の関係を除き，各キーワード間には，明ら

5. 評 価 実 験
本論文では E COW EB の有効性を検証するため，実データをかな競合関係は存在しない．

•

季節活動パターン: 図 (d-iii) は，E COW EB が発見した k = 2

用いた実験を行なった．具体的には，本章では以下の項目につ個の季節活動パターンを示している．第一成分 (b1 ，黄色)いて検証する．

は，Home Depot と Lowes のパターン，第二成分 (b2 ，紫Q1 オンライン活動データに関する提案手法の有効性色) は，Amazon, Walmart, Best Buy, Costco のパターンを表Q2 提案アルゴリズムの精度の検証

現している．両成分における，Black Friday のスパイクにQ3 パターン抽出に対する計算時間の検証

加え，Home Depot と Lowes (b1 ) には，アメリカ合衆国内

5. 1 Q1: 提案手法の有効性の祝日（Memorial Day，5 月の最終月曜日；独立記念日，7

本節では，大規模オンライン活動データに対する E COW EB

月 4 日；労働者の日，9 月の第一月曜日）に相当するスパの情報抽出の効果を検証する．本研究では，GoogleTrend におイクが確認できる．

ける次の 5 つのカテゴリに関連するキーワード（アクティビ

5. 2 Q2: 提案手法の精度

ティ）集合に対する解析を行った：ビデオゲーム (#1), プログ

次に，提案モデルの精度を検証するため，既存手法である LV

ラミング言語 (#2), ソーシャルメディア (#3), アパレル企業 (#4),

モデルとの比較を行った．本研究ではさらに，提案アルゴリズ

リテール企業 (#5).

ムの効果を検証するために，モデル学習に S TEP F IT のみを用い

以下では，3 つのカテゴリに対する解析結果の考察を行う．

た手法として E COW EB-Plain との比較も行った．図 6 は，5 つ#1. ビデオゲーム. 既に図 1 において示したように，提案手法のオリジナルデータセット (#1-#5) と推定値との二乗平均誤差

は，Xbox, PlayStation, Wii の 3 つのゲーム機の長期的な時間発(RMSE: root mean square error) を示している．LV モデルは季節

展と，Android の出現を表現し，Black Friday やクリスマス等の性を伴う活動パターンを表現できないため，周期的に発生する

季節性を伴うイベントのパターンを発見した．

スパイクに影響され，長期的な時間発展を正しく学習すること#2. プログラミング言語. 図 5 (a) は，プログラミング言語に関ができない．E COW EB-Plain は，周期性を表現する能力を有す

連する 3 つのキーワード：“C”, “R”, “MATLAB” に対する解析

るが，複雑な競合関係パラメータの学習ができない．図に示す

結果を示している.

通り，LV モデルと E COW EB-Plain と比較し，提案手法は高い••

長期的な時間発展と競合関係: 図 5 (a-i) は，E COW EB の学精度でのデータの学習に成功した．

習結果（線）とオリジナルシーケンス（丸印）を示す．図5. 3 Q3: 提案手法の学習時間に示す通り，提案モデルはオリジナルの時系列パターンを

次に，E COW EB -F IT の計算時間を検証する．図 7 はデータ柔軟に表現している．図 5 (a-ii) は，競合関係ネットワークのサイズ n を変化 (5 年間から 10 年間) させた上での提案手法を表現しており，“C” と “R” の間に潜在的な関係がある一の計算時間を示している．図に示す通り，E COW EB -F IT は高方で，“MATLAB” は独立していることを示している．図 5

速かつ高精度に重要なパターンを発見することができる．ここ(a-i) に示すように，2004 年から現在にかけ，ビッグデータ

で，E COW EB -F IT はデータの入力サイズ n に対し線形であり，解析ツールとしての利用等により “R” のアクティビティは

E COW EB-Plain と比較し最大で 20 倍, LV と比較し 7 倍の性能増加傾向にある一方，“C” は著しく下降している．

向上を達成している．

季節活動パターン: 図 5 (a-iii) は，E COW EB の全パラメー

6. アプリケーション

タ集合を示している．ここで，濃度の高いパラメータは，高い値を示す．興味深いことに，プログラミング言語に関連する季節活動パターン (図 5 (a-iii) 下段：W, B) は，大学のアカデミックカレンダーと強い相関関係にある．明ら

図 8 はビデオゲーム (#1) に対する予測結果を示している．

かに，これらのクエリの入力ユーザの多くは大学生であり，

ここでは，シーケンス全体の 2/3（黒線）を学習データとしプロのエンジニア，プログラマの活動パターンとは異なる．

て用い，その後の 2012 年以降を予測した．提案モデルの精度

例えば，春休み，夏休み，冬休みの間，各キーワード（とを検証するため，自己回帰モデル (AR: autoregressive model) とりわけ MATLAB) の検索数は，著しく低下している．つまの比較を行った．公平な比較をするために，AR の回帰係数はりこの結果から，大学生である彼らの大半は，コーディン

E COW EB のパラメータ数と同様になるように設定した．図 8 上

グの手を止め，休暇を楽しんでいるということがわかる．

#5. リテール企業. 図 5 (b) は，6 つの主要なリテール企業に関連するキーワードに対する解析結果である．

•

本章では，E COW EB の最も需要なアプリケーションであるオ
ンライン活動データの将来予測について述べる．

長期的な時間発展と競合関係: Amazon を始めとするオンラ
インサービスの成功により，主なリテール企業は，著しく成長している一方で，家電量販店 Best Buy は横ばいとなっている．日曜大工 (DIY: do it yourself) 専門店である Home段はオリジナルデータ，中下段はそれぞれ，E COW EB と AR の予測結果を示している．図に示した通り，提案手法は非線形性を有する長期的なアクティビティの推移を表現するとともに，季節性を伴うスパイクも柔軟にすることができる．

7. む す び
本論文では，大規模オンライン活動データのための非線形解
析手法として E COW EB について述べた．E COW EB は，Web 上

Fitting result − RMSE=0.076417
x1
x2
x3

Volume @ time

1
0.8

1

0.6

3

2

0.4
0.2

Keywords
C

x1

0
2004

2006

2008
2010
Time (weekly)

2012

2014

x2

R

x3

MATLAB(a-i) E COW EB の学習結果(a-ii) 競合関係

(a-iii) 全パラメータ集合(a) プログラミング言語に関するパターン発見．
Fitting result − RMSE=0.065173
x1
x2
x3
x4
x5
x6

Volume @ time

1
0.8
0.6
0.4

1
6
5

3
4

x1
x2
x3
x4
x5
x6

0.2
0
2004

2

2006

2008
2010
Time (weekly)

2012

2014

(b-i) E COW EB の学習結果

Keywords
AmazonWalmartHome Depot
Best buy
Lowes
Costco(b-ii) 競合関係

(b-iii) 全パラメータ集合(b) リテール企業に関するパターン発見．
図5Fig. 5

2 つのカテゴリに関連するキーワードに対する E COW EB の学習結果．

Fitting results of E COW EB for (a) Programming languages and (d) retail companies.

EcoWeb−Fit
EcoWeb−Plain
LV

0.15

0.1

0.05
#1

図6

#2

#3
#4
Data ID#5

E COW EB -F IT と既存手法の精度比較．
Fig. 6

Accuracy of E COW EB -F IT.

Wall clock time (sec.)

Fitting error (RMSE)

0.2
1500

Original sequences

EcoWeb−Fit
EcoWeb−Plain
LV

1
0.5

1000

0
2004 2006 2008 2010 2012 2014
EcoWeb
1

500
0
5

6

7
8
9
Datasize (years)

10

図7

E COW EB -F IT の計算コスト．

Fig. 7E COW EB -F IT scales linearly.

02004 2006 2008 2010 2012 2014
AR
1のオンラインユーザ活動の推移パターンを，自然界の生態系に0.5おける種内・種間競争として捉えることで，潜在的なユーザ資

02004 2006 2008 2010 2012 2014

源 (ユーザの興味) を共有，または競合することで時間発展していくような非線形動的システムとして表現する．実データを用いた実験では，E COW EB が Web 上の様々な種類のオンライン
活動において，長期的な成長や競合パターンや季節性等の重要なトレンドを発見し，さらに，長期的な将来予測を高精度に行うことを確認した．
文

献[1] J. Ginsberg, M. Mohebbi, R. Patel, L. Brammer, M. Smolinski, and
L. Brilliant. Detecting influenza epidemics using search engine querydata. Nature, 457:1012–1014, 2009.
[2] J. Leskovec, L. Backstrom, and J. M. Kleinberg. Meme-tracking andthe dynamics of the news cycle. In KDD, pages 497–506, 2009.
[3] Y. Matsubara, Y. Sakurai, and C. Faloutsos. The web as a jungle:
Non-linear dynamical systems for co-evolving online activities. In
WWW, pages 721–731, 2015.

0.5

図8

E COW EB による将来予測 (ビデオゲーム (#1) )．
Fig. 8

Forecasting future evolutions.

[4] J. Murray. Mathematical Biology II: Spatial Models and Biomedical
Applications. Intercisciplinary Applied Mathematics: Mathematical
Biology. Springer, 2003.
[5] M. Nowak. Evolutionary Dynamics. Harvard University Press, 2006.
[6] E. Odum and G. Barrett. Fundamentals of Ecology. Thomson
Brooks/Cole, 2005.
[7] Y. Sakurai, Y. Matsubara, and C. Faloutsos. Mining and forecastingof big time-series data. In SIGMOD, Tutorial, pages 919–922, 2015.
[8] Y. Zhao, N. Sundaresan, Z. Shen, and P. S. Yu. Anatomy of a webscale resale market: a data mining approach. In WWW, pages 1533–
1544, 2013.