論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――

データの傾向を考慮したストリー
ムデータの相関の計算方法の提案
Calculating Correlations of Stream Datawith Data Tendencies: A Proposal

畑中洋介♥

有次正義♦

Yousuke HATANAKA Masayoshi ARITSUGI

本稿では複数のストリームを監視し，ストリームのデータ傾向を考慮することによって誤差を少なくするストリーム相関の効率の良い求め方を提案する．ストリームデータの相関は時間によって変わるため，できるだけ効率よく相関を求めることが重要である．本稿では， sliding window を階層構造で管理することを考える．この際，データの傾向を考慮した近似を行うことにより，精度のよい相関の計算を可能にする．
A method for efficiently and accurately calculatingcorrelations of stream data with taking into account ofdata tendencies by monitoring multiple stream data isproposed in this paper. Since correlations of stream datachange with time, it is important to calculate themefficiently. In this paper, we try to manage a sliding
window in a hierarchical structure. We show that taking
into account of data tendencies allows us to obtain good
approximation of correlations.

1. はじめにストリームデータを扱うアプリケーションにおいては，多少の誤差が生じても，より速くユーザからの問合せに答えることが重要であると考えられる．このことは Data Stream
Management System[1]を設計する際の問題として挙げられている．ストリームデータは株式市場やセンサーモニター，Webサイト管理，ネットオークション，医療の分野において非常に多く発生している．ストリームデータは量が膨大で，新しいデータが極めて早いペースで到着するといった特徴がある．
本稿では複数のストリームデータを監視し，ストリームデータの相関を効率よく求める手法を提案する．相関を求める
際，データの傾向を考慮することによって誤差を少なく近似して求めることを考える．ストリームデータの相関は時間によって変わるため，できるだけ効率よく相関を求めることが重要である．同時に，ストリームデータの平均，分散という統計値についても考慮する．ストリームデータの相関等を求めることによって例えば以下のような利点が考えられる．株
式市場で発生しているストリームデータの相関を求めることができれば，連動している 2 つの銘柄を見つけることができ，ペアトレードをしている裁定業者にとって有利になる．
分散を効率良く求めることができれば，ある時間内において激しく変動している銘柄を見つけることができる．センサー
モニターで発生しているストリームデータの温度の相関を求めることによって，温度変化が連動している場所を特定することができ，1 つの場所で異常気象が発生した際もう 1 つの場所でも同じような異常気象が発生することが予想できる．降水量と川の水位の相関を求めることにより災害が発生しやすい場所を特定することができる．Web サイトを訪れたユーザの閲覧した軌跡を表すクリックストリームと呼ばれるストリームデータの相関を求めることにより，バナー広告，メールマガジンの効果が分かる．
ストリームデータの相関を求めるためには，相関係数を求めれば良い．相関係数を求めるために StatStream[2]で提案されている DFT 係数を使った近似手法を用いる．この手法を用いることによって，全てのデータを格納することなく，ストリームデータの相関係数を DFT 係数から近似して求めることができる．本稿では，StatStream で提案されている分割された sliding window を木構造で扱うことによって，最新のデータの誤差を小さく保ちながらストリームデータの平均，分散，相関という統計値を効率良く求める方法を提案する．
統計値を求める際，ノード内のデータの傾向を考慮することによって上位レベルの誤差が少なくなるような DFT 係数更新方法を提案する．

2. 関連研究関数の分解手法として wavelet がある．SWAT[3]では最も簡単な Haar wavelet を用いてストリームデータを近似的に扱っている．SWAT では最新のデータの誤差が小さくなるような構造をとっており，SWAT の木構造の各ノードにはデータの平均値が格納されている．SWAT ではシングルストリームデー
タの平均値のみを扱っている．一方 StatStream[2]では，相関係数というマルチストリームデータの統計値について扱っている．本稿では StatStream で提案されている分割された sliding window を SWAT のような階層構造で扱うことを考える．

2.1 Wavelet
Wavelet は関数を階層的に分解する手法である．Haar
wavelet は最も単純な wavelet で，理解と実装が簡単だという特徴がある．1 次元データセット[2 8 3 3]を例として考える（表 1）．Wavelet 分解では初めにペアごとの平均値を計算する([5 3])．この処理で元のデータセットの情報が捨てられてしまう．しかしデータ値の差を 2 で割った[‑3 0](Detail Coefficient) を格納しておくことにより，データの平均値から元のデータを復元することが可能となる．この平均値計算と差を 2 で割る計算が繰り返し行われる．
表 1 Wavelet 分解
Table 1 Wavelet decomposition
Average
Detail Coefficient[2 8 3 3][5 3][‑3 0][4][1]♥

学生会員 群馬大学大学院工学研究科博士前期課程
hatanaka@dbms.cs.gunma-u.ac.jp♦正会員 群馬大学工学部情報工学科
aritsugi@cs.gunma-u.ac.jp1

日本データベース学会 Letters Vol.2, No.3

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
R3

L2[8-15]

S2[4-11]
L1
[4-7]

レベル 3
[0-15]
R2
S1
[2-5]
L0
[2-3]

レベル 2[0-7]R1S0[1-2]

レベル 1[0-3]
R0

レベル 0

[0-1]

図 1 sliding window サイズが 16 の時の SWAT
Fig.1 SWAT in case the size of sliding window is 16

2.2 SWAT
SWAT(StreamSummarizationusing
Wavelet‑based
Approximation Tree)[3]は Haar wavelet を用いてストリー
ムデータを近似する．これにより元のデータを全て格納することなく，各ストリームデータの値を近似的に求めることができる．時系列ストリームデータではデータ値が連続しているため，Detail Coefficient は 0 または小さい値となる．よって Detail Coefficient を省略しても誤差は小さくなることを利用して，SWAT ではノードに平均値のみを格納している．
例として sliding window のサイズが 16 の SWAT を図 1 に示
す．各ノードにはインデックスに含まれるデータの平均値が格納されている．例えば R1 のインデックスは[0‑3]であり最新のデータから 3 番目までのデータの平均値が格納されている．つまり，SWAT では新着データの近似の精度が古いデータの精度より高くなっている．[3]によれば，SWAT は histogramによる方法と比べると問合せ応答時間が早く，誤差が少ないという特徴がある．データの更新はノードのレベル毎に異なり，レベル i のノードは 2 i 個のデータが到着する毎に以下のように計算される．
• ノード Li にノード S i のデータをシフトする• ノード S i にノード Ri のデータをシフトする• ノード Ri のデータはノード Li −1 とノード Ri −1 から計算
本稿では SWAT の階層構造を応用して最新のデータの誤差が少なくなるように平均，分散，さらに相関係数を求めることを可能にする手法を提案する．に分け，basic window 毎に統計値を格納し全体の統計値を更新する． b 個のデータが到着すると新しい basic windowの統計値が計算され，最も古い basic window は削除される．
相関性が高いストリームデータのペアを効率的に求めるために，StatStream では basic window 内のデータに離散フーリエ変換(DFT)を行い近似的に相関係数を求める．また，多くのペアの近似相関計算を避けるためにグリッドデータ構造を使用している．本稿ではこの sliding window を木構造で扱うことを考え，近似的に相関係数を求めるために
StatStream で提案されている DFT を使った手法を用いる．

3. ストリームデータの統計値
3.1 平均，分散，相関係数
サ イ ズ w の sliding window 上 の ス ト リ ー ム デ ー タ( x 0 ,..., xi ,..., x w−1 )の平均，分散，及び二つのストリームデー
タ x, y の相関係数は，それぞれ以下のように表される．
平均：x =1 w−1∑ xiW i =0

分散：σ 2 =w−1

∑ ( xi − x ) 2i =0

相関係数：corr ( x, y ) =1 w−1∑ xi y i − x yw i =0w−1w−1i =0i =0

∑ ( xi − x ) 2 ∑ ( y i − y ) 2

分散が大きいストリームデータを見つけることにより，ある時間内において激しく変動しているストリームデータを見つけることができる．相関係数の高い 2 つのストリームデータを見つけることにより，連動しているストリームデータを見つけることができる．

3.2 DFT を用いた相関係数の近似
slinging window の DFT 係数 ( X i ) と分散 (σ x2 ) を計算する
ことにより，相関係数を近似的に求めことが可能であることを簡単に説明する．以下ではまず DFT とその性質について説明する．次に DFT と分散を用いた相関係数の近似方法を説明する．

3.2.1 離散フーリエ変換(DFT)とその性質
時系列データ x = {x0 , x1 ,..., x w−1} が与えられたときの離散 フ ー リ エ 変 換 で あ る 複 素 数 列 （ DFT 係 数 列 ）X = { X 0 , X 1 ,..., X w−1} は以下のように計算できる[2]．

XF =図 2 sliding window と basic window
Fig.2 A sliding window and basic windows

2.3 StatStream
StatStream(Statistical Monitoring of Thousands ofData Streams in Real Time)[2]では sliding window 中の平均，標準偏差，分散といったシングルストリームデータの統計値だけでなく，ストリームデータ同士の相関係数というマルチストリームデータの統計値についても考えている．図 2のように， sliding window を同じ大きさの basic window

21w−1∑ xi e − j 2πFi / ww i =0

F = 0,1,..., w − 1 , j = − 1
DFT の性質として系列 x と系列 y のユークリッド距離をd ( x, y ) , 系列 x と系列 y の DFT を X , Y と表したとき以下のような性質がある．

d ( x, y ) = d ( X , Y )3.2.2 相関係数の近似方法
ストリームデータ x , y の相関係数 corr ( x, y ) は，以下のように近似して計算できる[4]．

日本データベース学会 Letters Vol.2, No.3

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
1 2d ( xˆ , yˆ )21
= 1 − d 2 ( Xˆ , Yˆ )2
1 2 ˆ ˆ≈ 1 − d n ( X , Y ) ‥‥(i)2
ただし xˆ , yˆ は以下のように，元の系列 ( x = {x 0 , x1 ,..., x w−1 } ,y = { y , y ,..., y }) を正規化した系列であり，d 2 ( Xˆ , Yˆ ) はcorr ( x, y ) = 1 −

0w−1

1

散，DFT 係数は， b2 i 個のデータが到着する毎に以下のように更新すればよい．

n正規化した系列 xˆ , yˆ の DFT 係数のうち初めの n 個の DFT 係数( X 0 , X 1 ,..., X n (n < w − 1)) のユークリッド距離を表している．

xˆ = {xˆ 0 , xˆ1 ,..., xˆ w−1}xˆi =xi − xσx =図 3 sliding window の階層構造
Fig.3 The layered structure of sliding window( i = 0,1,..., w − 1 )σxw−1∑ ( xi − x )4.1 平均の更新
レベル i のノードの平均は以下のように更新すればよい．
x Li = x Si （ノード S i の平均をノード Li にシフト）2i =0

式(i)より d n ( Xˆ , Yˆ ) の値が小さくなれば，ストリームデー
2

タ x , y の相関係数が大きくなるため，ストリームデータ

x , y の相関性が高いといえる．つまり相関性が高いストリームデータのペアを求めたい場合は， d 2 ( Xˆ , Yˆ ) が小さいス

x Si = x Ri （ノード Ri の平均をノード S i にシフト）
x Ri =( x Li −1 + x Ri −1 )2

（レベルが1つ下のノードである Li −1と Ri −1 から Ri の平均を計算）

nトリームデータのペアを探せばよい．

X i と X̂ i の関係は以下のように表すことができる[4]．

 Xˆ 0 = 0ˆ
X i ‥‥(ii)X i = σx式(i), (ii)を使って，sliding window の DFT 係数 ( X i ) と分散 (σ x ) から相関係数を近似的に求めることができる．
2

4. sliding window の階層構造とその管理[3]で提案されている方法をそのまま用いてストリームデータの相関を求めようとすると，誤差が無視できないくらい大きくなることが考えられる．これは，[3]ではシングルストリームの統計値を扱うことは考えているが，相関などの複数のストリームデータの統計値を扱うことを考慮していないためである．具体的には，SWAT では Detail Coefficientsをすべて格納しないことによる効率化を図っているため，格納している平均値で元のデータを近似しているが，相関を求める場合にこれをそのまま適用してしまうと，一般に誤差が大きくなってしまう．そこで本稿では，平均と分散を使うことによってストリームデータの動きを近似的に表し，そのデータの傾向を使って誤差がより小さくなるようにストリームデータの相関を求めることを考える．
本稿では図 3 のような sliding window の木構造を考え，平均，分散，DFT 係数を階層ごとに更新していく方法を議論する．各ノードには平均 ( x ) ，分散 (σ 2 ) ，DFT 係数 ( X m ) を格納する．以下ではこの構造に基づく平均，分散，DFT 係数の更新方法について説明する．上位レベルの DFT 係数を求める際には，ノード内のデータの傾向を使うことによって誤差が少なくなる手法を提案する．レベル i のノードの平均，分34.2 分散の更新
分散の更新は[5]の Combination Rule を用いて更新できる．
具体的には，レベル i のノードの分散は以下のように更新すればよい．

σ L2i = σ S2i （ノード S i の分散をノード Li にシフト）σ S2i = σ R2i （ノード Ri の分散をノード S i にシフト）
σ R2i = σ L2i −1 + σ R2i −1 +b 2 i −1 × b 2 i −1b2i −1+ b2i −1( x Li −1 − x Ri −1 ) 2

つまり，レベルが 1 つ下のノードである Li −1 と Ri −1 の平均と分散を使って Ri の分散を計算すればよい．

4.3 データの傾向を考慮したDFT係数の近似計算
株式市場で発生しているストリームデータや，センサーモニターで発生している温度のストリームデータの様な時系
列ストリームデータを考えた際，データは連続的に変動する．
つまりデータは完全にランダムな動きはしないと考えられるため，各ノード内のデータには下記のような一定の傾向があると考えられる．
① 右肩上がりのデータ② 右肩下がりのデータ③ 変化が少ないデータ
ノード内のデータの傾向と分散，平均を使うことによってノード内の全ての元データを格納することなく，近似的にノード内のデータの動きを表すことができる．以下ではこのノード内のデータの傾向を使って誤差が少なくなる DFT 係数の近似計算方法を提案する．DFT 係数の誤差が少なくなれば相関係数をより正確に求めることができるようになり，相関性の高いストリームデータのペアをより正確に求めることができる．
ノード内のデータ ( xi (0 ≤ i ≤ b − 1)) の傾向を使って，上位

日本データベース学会 Letters Vol.2, No.3

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
レベルの DFT 係数を誤差が小さくなるように更新することを考える．レベル 1 の DFT 係数はレベル 0 の平均 ( x 0 ) と分散(σ 02 ) を使って表 2 の様にデータ値 ( xi ) を近似して求める．
表 2 ノード内のデータの傾向を使ったデータの近似
Table 2 Approximation with data tendencies in nodes
ノード内のデータの傾向

xixixi(0≤i≤b/3‑1)(b/3≤i≤2b/3‑1)(2b/3≤i≤b‑1)①右肩上がりx0 −②右肩下
がりx0 +③変化が少ないσ 02x0b

σ 02x0bx0x0x0 +x0 −σ 02bσ 02bx0

このように近似することによってノード内のデータの傾向を上位レベルの DFT 係数の計算に反映することができるため誤差が少なくなる．例えば L0 のデータの傾向が①で R0 のデータの傾向が③のとき R1 の DFT 係数は以下の様にして求めることができる．

X m _ R1 ≈
2  − j 2πFiσ Lo
1 b / 3−1 e 2 b ∑  x Lo −b w  i =1 +2b / 3−1∑

i =b / 3+x L0 e− j 2πFi2b− j 2πFi 2  − j 2πFi
2b −1 x + σ Lo e 2b +xe∑  Lo∑ R0 2b bi = 2b / 3i =b


b −1

レベル2のノードのDFT係数を計算する方法は以下の2種類の方法が考えられる．
• レベル1の平均と分散だけを使って計算する• レベル1とレベル0の平均と分散を使って計算する
どちらの方法で計算したほうが誤差がより小さくなるかは，
L0 と R0 のノード内のデータの傾向による． L0 と R0 のデー
タが①＋②，②＋①の様に上下または下上という傾向を示しているときは，レベル1 ( L1 ) とレベル0 ( L0 と R0 ) の平均と分散を使ってレベル2のDFT係数を求めたほうが誤差は少なくなる．これは L0 と R0 のデータが上下，下上という傾向を示しているにもかかわらず，レベル1の平均と分散だけを使ってデータを近似するとほとんど変化がないデータと見なされてしまうからである．また①＋①，②＋②，③＋③の様に同じ傾向を示しているときは，レベル1の平均と分散だけを使ってレベル2のDFTを求めたほうが誤差は少なくなる．その他の場合（①＋③，②＋③，③＋①，③＋②）は，レベル1の平均と分散だけを使ってレベル2のDFT係数を求める．
同じようにしてレベル i のDFT係数を求めるとき，レベルi − 2 のノード Li − 2 と Ri − 2 のデータの傾向が上下，下上のときはレベル i − 1 ( Li −1 ) とレベル i − 2 ( Li − 2 と Ri − 2 ) の平均と分散を使って求める．その他の場合はレベル i − 1 ( Li −1 とRi −1 ) の平均と分散を使って求める．

誤差を少なくしてDFT係数を効率よく計算することが可能となる．

4.4 DFT係数の更新
レベル i のノードのDFT係数は以下のように更新される．

X m _ Li = X m _ Si
X m _ Si = X m _ Ri
4.3で示したようにレベル i より下のノードの平均，分散を使って新しい X m _ Ri を計算する．

4.5 考察図3のようなsliding windowの木構造を考えることによって以下のような利点がある．[2]の方法を使ってslidingwindow内のDFT係数を求める際， k をsliding windowの分割数とすると， Ο(k ) 個のデータを参照しなくてはならない．
一方本稿の方法では Ο(log k ) 個のデータを参照すれば良いた
め，[2]よりもDFT係数の更新が速くなると考えられる．精度についてはノード内のデータ傾向を考慮しているため，[3]をそのまま使ってDFT係数を求めるより良くなると考えられる．ただし本稿の方法は最新のデータの誤差は少なくできるが，過去のデータについては[2]より誤差が大きくなることが考えられる．このため[2]の方法と比べた場合，精度がどのようになるかは今後の課題である．

5. まとめと今後の課題
本稿ではストリームデータの相関を効率良く求めるために，階層的な DFT 係数の計算方法を提案した．この DFT 係数の計算方法は，ノード内のデータの傾向を使うことにより誤差を少なくすることが可能となっている．今後は，提案手法をシステムとして実装し，具体的な応用分野に適応してその有効性を検証していく予定である．

[文献][1]B.Babcock, S.Babu, M.Datar, R.Motwani and J.Widom.:“Models and issues in data stream systems”, Proc.
PODS, pp.1-16 (2002).
[2]Y.Zhu and D.Shasha: “StatStream: Statisticalmonitoring of thousands of data streams in real time”,
Proc. VLDB, pp.358-369 (2002).
[3]A.Bulut and A.K.Singh: “SWAT: Hierarchical streamsummarization in large networks”, Proc. ICDE,
pp303-314 (2003).
[4]R.Agrawal, C.Faloutsos and A.N.Swami: “Efficientsimilarity search in sequence databases”, Proc. FODO,
pp.69-84 (1993).
[5]B.Babcock, M.Datar, R.Motwani and L.O'Callaghan:“Maintaining variance and k-medians over data streamwindows”, Proc. PODS, pp234-243 (2003).

畑中洋介

Yousuke HATANAKA

群馬大学大学院工学研究科博士前期課程在学中． 2002 群馬大学工学部情報工学科卒業．ストリームデータ処理に興味を持つ．

有次正義Masayoshi ARITSUGI

群馬大学工学部情報工学科助教授．1991 九州大学工学部情報工学科卒．1996 同大大学院博士後期課程了．博士(工学)．
データベースシステム，分散並列データ処理等に興味を持つ．

以上のようにノード内のデータの傾向を使うことにより，

4

日本データベース学会 Letters Vol.2, No.3