DEIM Forum 2019 H4-4

大域的・局所的データ分析を両立した効率的なフレームワーク
松本

拓海†

佐々木勇和†真†鬼塚† 大阪大学大学院情報科学研究科 〒 5650871 大阪府吹田市山田丘 1-5
E-mail: †{matsumoto.takumi,sasaki,onizuka}@ist.osaka-u.ac.jp
あらまし 探索的データ分析は，ビッグデータ時代における重要な研究の 1 つである．探索的データ分析の典型的なアプローチは，分析観点（グループ化属性や集約属性）や分析対象となるデータを変更することによって自動的に生成される多数の OLAP クエリの結果の中から興味深い結果を特定する．多くの分析観点や部分データが存在するた
め，分析に膨大な時間を要するという課題が存在する．この課題に対して，既存研究は色々な方法で高速化を行っているが，対象としている分析手法が大域的な例外データか局所的な例外データのどちらかにしか対応していない．本
稿は，大域的なデータ分析と局所的なデータ分析を両立した探索的データ分析のフレームワークを提案する．また，中心極限定理を用いた top-k 枝刈りとデータキューブを用いたクエリ共有化を行うことによって処理の最適化を行う．
更に，実データに対して適用した結果，最大 64.9% の実行時間の削減し，大域的・局所的な例外部分データを同時に高い精度で特定することを確認した．
キーワード OLAP，探索的データ分析，Data Cube

1. は じ め にJohn Tukey は 1977 年にデータから隠れた知見を発見する

0.5
0.375

ために仮説を立てることなく分析する手法 [1] を提唱し，探索

0.25

的データ分析 (EDA: Exploratory Data Analysis) [2] として

0.125

知られている．一方，統計的な仮説検証型のデータ分析 (CDA:

Confirmatory Data Analysis) は，ビックデータは 3V (Vari-

0
Dec

Jan

Feb

Mar

Apr

May

ety, Velocity, Volume) という特徴によって統計的な仮説を立

図 1 商品別正規化した月毎の売上．このグラフには 3 つのクラスター

てることが難しい．そのため，仮説検証型のデータ分析ではなが存在するが，赤色の線が大域例外であり，黄色の線が局所例外

く探索的データ分析 がビックデータに適しており，現在の研のデータである．

究のトレンドの 1 つである．探索的データ分析の主な目的は，統計的仮説を定義することなくデータを探索することで興味深い観測結果を得ることである．興味深い観測結果とは，データセット内に存在する平均的な動作を計算することや，例外的な点や異常傾向を特定することで計測される．

OLAP クエリ結果から異常傾向を特定する探索的データ分析の研究が数多く存在する [3–10]．これらの研究は，データ分
析の観点において例外的なクエリ探索と例外的な部分データ探全体を通して例外的なデータであると言える．

Example 1.2. 局所的な例外部分データ．図 1 において，橙
色の線と青色の線の傾向は x 軸全体を通して似た傾向を示している．しかし，Apr に関して値が低く，局所的な傾向の中での異常値であり，局所例外度が高く算出される部分データである
ため，局所的な例外データであると言える．

索の 2 つに大別することができる．分析対象のデータを D と

ほとんどの既存手法 [4–6, 10] は，複数のクエリ結果間の距

すると，例外的なクエリ探索は，データ D の部分データ S を離を計算することで大域例外 (Global Outlier Factor) を特定

入力し，クエリ結果 q(D) と q(S) が最も乖離する OLAP ク

することに効果的である．また，局所例外は多くのアプリケー

エリ q を特定する．一方，例外的な部分データ探索は，OLAP

ション領域でよく知られている概念である．例えば，クレジッ

クエリ q を入力し，クエリ結果 q(D) と q(S) が最も乖離する

トカードの異常な使用を検出する不正検出，顧客の異常行動を部分データ S を特定する．本研究では例外的な部分データ探

特定するカスタマイズマーケティング，あるいは様々な治療の索に取り組む．以下の例では，大域的・局所的な例外部分デー

異常な反応を発見する医用分析で用いられている [11]．小笠原

タついて説明する．

らの研究 [12] では，部分データ探索において局所例外の特定をExample 1.1. 大域的な例外の部分データ．図 1 において，緑
色や青色の線は比較的同様の傾向を示す部分データが存在する．
しかし，赤色の部分データでは，M ar, Apr, M ay 以外の月に関して他の部分データなどと比較して乖離が大きいため，x 軸実現している．しかし，大域例外の特定と局所例外の特定を両立している既存技術は存在していない．
本研究は，部分データ探索問題に対して大域的・局所的な 異常傾向の検出を両立した，探索的データ分析のための効率的なフレームワークを提案する．top-k 枝刈りとクエリ共有化によ関数である．母集団の平均値 µ の信頼係数が p である確率点で計算するこzp は累積分布関数を使用すると，Φ(zp ) = p+12とができる．以上より，クエリ結果の信頼区間は式 (3) で求め
られる．

√
¯
Y¯n − ϵn <=µ<
= Y n + ϵn , ϵ n =zp2 Tn,2 (v)n(3)

2. 2 LOF (Local Outlier Factor)
図2

LOF は，密度に基づく最近傍ベースの代表的な外れ値検知

提案フレームワークの概要手法であり，各データ（例えば，部分データ 1 つ 1 つ）を Nる最適化を行うことで高速化を行う．クエリや部分データの候

次元距離空間上の 1 つの点とみなし LOF 値を計算する．任意

補は膨大に存在するため，入力データをストリーム（レコードの点 A は，0 以上の実数 ai (1 <= N ) の N 個の組で表さ=i<毎に）処理することでデータキューブと Join 処理し，データれる座標として，次式で定義される．

キューブを段階的に維持する効率的なアプローチを行う [9, 13]．

A := [a1 , a2 , · · · , an ]データキューブのセルが top-k の候補に含まれないと判定する(4)と，データキューブから対象のセルを削除する．さらに，効率距離空間における局所的な範囲を決定するため，ユーザが事前的な top-k 枝刈りのために Online Aggregation 技術 [14, 15]に設定するパラメータ k を用いて，点毎の近傍（以後，k 近傍）を採用する．

を特定する．点 A の k 近傍 Nk (A) は，次式で定義される．

図 2 は提案するフレームワークの概要を表す．入力データに対するストリーム処理に User Defined Aggregation Function

Nk (A) := { B ∈ P − {A} | d(A, B) <= k-distance(A) }(5)(UDAF) を使用して，Spark の上に提案フレームワークを実装

但し，P は距離空間上の点の集合，d(A, B) は A と B の間のする．

ユークリッド距離，k-distance(A) は A から k 番目に近い点

本稿の構成は，以下の通りである．2. 章にて事前知識につと A との間のユークリッド距離を表す．すなわち，Nk (A) は，いて説明し，3. 章において提案フレームワークの詳細を示し，A から k-distance(A) 以下の距離に位置する点を含む集合で4. 章にて評価実験について説明し，5. 章にて関連研究についてある．A の LOF 値は，LOFk (A) として次式で定義される．

述べ，6. 章にて本稿をまとめ，今後の課題を論ずる．

∑
LOFk (A) :=2. 事 前 知 識
本章では，提案フレームワークに用いた信頼区間，LOF の上/下限値推定や分析アプリケーションについて説明する．2. 1
節では中心極限定理を用いた OLAP クエリ結果の区間推定について 2. 2 節では LOF (Local Outlier Factor) について説明

B∈Nk (A) lrdk (B)/ |Nk (A)|lrdk (A)(6)

LOFk (A) は，A の k 近傍内の点 B との密度 (lrdk ) の比で表される．lrdk (A) は次式で定義される．

|Nk (A)|B∈Nk (A) reach-distk (A, B)

lrdk (A) := ∑する．そして，2. 3 節で分析アプリケーションに関する問題定(7)

但し，reach-distk (A, B) は，B から A への到達可能距離

義や有用性の定義を説明する．

(reachability distance) を表す．reach-distk (A, B) は次式で定

2. 1 中心極限定理を用いたクエリ結果の区間推定
信頼区間とは，母数の値がどのような範囲に存在するかを確義される．

率的に表す方法である．中心極限定理より，真の集約値 µ の信
頼区間の式を導出する．標本集約値を Y¯n ，標本集約値分散をreach-distk (A, B) := max{d(A, B), k-distance(B)} (8)θ2 とすると，標本集約値が真の集約値 µ の信頼区間に含まれk の値は 10 以上に設定すると統計的変動を小さく抑えることる確率は以下のように定義される．

ができる．

P r(ϵ) := P r[|Y¯n − µ| <= ϵ]

2. 2. 1 LOF 上限・下限推定(1)

LOF 値の計算には，部分データのクエリ結果間の距離を導また，サンプルサイズ n が大きい場合，分散 θ2 の値は不変分

出することと，部分データの k 近傍を特定することが必要であ

散 Tn,2 値に近似する．中心極限定理より，式 (1) は以下のよる．従って LOF 値の上限・下限を推定するためには，(1) 信頼

うに表される．

区間を持つクエリ結果間の距離の上限・下限を導出し，(2) ク√ ¯√n(Yn − µ) <ϵ n
P {|Y¯n − µ| <|= √}= ϵ} = P {| √Tn,2 (v)Tn,2 (v)√ϵ n)−1≈ 2Φ( √
Tn,2 (v)

エリ結果が信頼区間を伴う状態において，各部分データの k 近
傍候補を特定することが必要である．
初めに，LOF [16] をベースとした LOF 値の上限・下限の(2)

但し，ϵ >= 0 であり，Φ は標準正規分布の確率変数の累積分布導出式を定義する [12]．式 (6) を拡張し，A の LOF 値の上限を，分母に lrdk (A) の下限を取り，分子に lrdk (B) の上限の平均を取るように定義する．また，クエリ結果が信頼区間を伴う状態では，各部分データの k 近傍は正確に特定できない．そこで，lrdk (B) の上限の平均を計算する際，A の k 近傍候補内の各 B に対して lrdk (B) の上限を求め，その中から lrdk (B)の上限上位 k 件を選択しその平均を計算する．これにより，信頼区間の信頼度に基づく誤差の範囲で LOFk (A) の上限を定めることができる．A の LOF 値の下限の導出式は，同様の方法で定義する．式 (6) に基づき，A の LOF 値の上限・下限
図 3 フレームワークの概要(LOFk (A).upper, LOFk (A).lower) を次式で定義する．
∑
B∈Lmax(A) lrdk (B).upper/kk
LOFk (A).upper :=lrdk (A).lower∑
B∈Lmin(A) lrdk (B).lower/kk
LOFk (A).lower :=lrdk (A).upper

し，有益な上位 k 件のデータを探索する具体的な分析例として，大域例外部分データの探索問題 [10] や局所例外部分データの探索問題 [12] が存在する．任意の条件から得られる全ての部
分データの OLAP クエリ結果に対し乖離度を数値化する必要kLmax(A) := arg max lrdk (B).upperk′
B∈Nk (A)がある．有用性が高い分析結果を生み出す部分データとは，大域例外部分データでは全体データの分析結果との乖離が大きいkLmin(A) := arg min lrdk (B).lower
k
′

(9)

B∈Nk (A)と仮定し，局所例外部分データでは近傍点と密度差が大きいと仮定する．これらの探索タスクでは，部分データ集合と単一の′

但し，Nk (A) は A の k 近傍候補を表し，Lmax(A) は，A のkk 近傍候補内の B において，lrdk (B).upper 上位 n 件の B の(A) は，A の k 近傍候補内の B において，集合を表し，Lmink

集約属性，グループ化属性を事前にユーザが指定し，部分デー
タ集合 S から乖離度の大きい上位 k 件の部分データ S を求める．複数クエリ結果間の乖離度を数値化する関数として，大域

lrdk (B).lower 下位 n 件の B の集合を表す．lrdk (B).upper

例外データの特定の場合はユークリッド距離を，局所例外デーと lrdk (B).lower はそれぞれ lrdk (B) の上限と下限を表す．

タの特定の場合は LOF 値を採用すると，上位 k 件の例外部分

2. 3 分析アプリケーション

データの探索問題は以下のように定義される．

有用性の定義に基づく評価関数を作成することで，ユーザ定義 1. 部分データ集合 S，OLAP クエリ q ，特定する例外部が発見したい分析結果を定量的に評価することが可能となる．

分データの件数 k を指定し，部分データ集合 S に属する全て

ここで全体データを D とし，D の部分集合を部分データ Sの S の中で D(q ′ (S)) 上位 k 件の S を特定する．

で表現し，部分データの集合を S とする．全体データ D はレコード d1 , d2 , · · · , d|D|（|D| は全体データのレコード数）から構成される．レコード di (1 <= i <= |D|) は集約属性と次元属性の集合で構成される．集約属性の集合 A は，集約属性

a1 , a2 , · · · , a|A|（|A| は集約属性の総数），次元属性の集合 B は，次元属性 b1 , b2 , · · · , b|B|（|B| は次元属性の総数）で構成される．
次元属性 bi (1 <=i<
= |B|) の値が Y である部分データ S とkarg max D(q(S))
S∈S

大域例外部分データを特定する際の D(q(S)) は以下の式で表される．但し，X は x 軸の属性値集合を表す．

D(q(S)) = Σx∈X |qx (S) − qx (D)|部分データ集合 S は，関係代数における選択演算 σ を使用す局所例外部分データを特定する際の D(q(S)) は以下の式で表さると式 (10),(11) で定義される．

れる．但し，LOF 値計算における近傍の範囲を n とする．

S := σbi =Y (D)(10)

D(q(S)) = LOFn (q(S))

|B|

S :=

∪

{σbi =Y (D) | Y ∈ bi }(11)

3. 提案フレームワーク

i=1

単一の集約属性 ai と次元属性 bi から成る OLAP クエリ q は
式 (12) ように定義される．

q := bi Gw=f (ai )本章では，複数部分データに対するクエリ処理を同時実行すると共に，上位 k 件検索による探索空間の削減手法を両立したフレームワークを説明する．このフレームワークは，Apache(12)

Spark 上に UDAF を用いて実装した．3. 1 節でフレームワー
クの動作，3. 2 節でデータキューブの更新方法，3. 3 節でフレー

但し，G は各レコードを次元属性 bi でグループ化し各グルー

ムワークのアルゴリズム，3. 4 節では本稿で用いた分析アルゴ

プ毎に集約関数 f を ai に適用する処理，w はその集約値でリズムについて説明する．

ある．

2. 3. 1 大域・局所例外データの特定ユーザが単一の集約属性 ai と次元属性 bi ，次元属性を指定

3. 1 フレームワークの概要
ある部分データは式 (10) で得られ，部分データに対してク
エリ式 (12) を実行する．探索的データ分析では，様々なパター

件の属性集合を全て含む属性集合を入力して，各属性を 1 辺とするデータキューブを構築する．そして，クエリ q とデータキューブについて，クエリ q(S) の結果は group-by 属性によって分割された複数のキューボイドで表される．データキューブ
は OLAP のクエリ q(S) 結果の区間推定に必要な統計情報 （標本数と標本集約値平均，標本集約値分散）を内部で保持する．
このデータキューブはキューブの最小単位であるベースキュー
ボイドから構成されている．具体的には，図 4 のデータキュー
ブは，M onth, City, Carrier の 3 つの属性をもとに構築されており，それぞれの属性毎に特定の値を指定することによって具体的なベースキューボイドを特定することができる．例えば，(LA, AA, April) は 1 つのベースキューボイドの例である．

図 4 データキューブの例

3. 2 データキューブの更新

ンで集約処理を実行するため，膨大な部分データに対してクエリを実行する必要がある．提案するフレームワークの処理の概要は以下のとおりである．データを読み込む都度そのレコードが対象となる複数の部分データに対するクエリを同時実行
し，クエリ結果をデータキューブの形式で保持する．これによりデータ D を 1 スキャンする事で複数の OLAP クエリの結果を同時に作成することができる．更に，統計的信頼区間の技術 [14, 15, 17, 18] を利用することで，一部のデータに対するク
エリ結果をもとに全体データに対するクエリ結果を推定し，上位 k 件の候補に成り得ないデータキューブを枝刈りする．上位

k 件の枝刈り判定は分析アルゴリズムによって異なるため，枝刈り判定自体は分析アルゴリズムが行い，フレームワーク側はその判定に従いデータキューブの更新をスキップすることで高速化を図る．
提案するフレームワークの処理の流れは以下の通りである．

step.2, 3 の詳細は 3. 2 節で述べる．
step.1 統計的信頼区間の技術を適用するためには入力データ
D をランダム順に格納する必要がある．そのため，レコードを選択し格納先のデータブロックをランダムに選択する

（注 1）

こと

でランダム性を保証する．

データキューブの更新は次の 3 つのステップから構成される．
まず入力レーコードに対して差分更新するベースキューボイド
を特定する．次に，特定したキューボイドに対しデータの差分更新する．そして，データキューブの信頼区間の計算を式 (3)を用いて行う．以降各ステップの詳細を説明する．
入力レコードに含まれるキューブを構成する各属性の属性値
を key とし，入力レコード毎に既存のキューブから差分更新するベースキューボイドを特定する．次に特定したキューボイド
が保持している標本数と標本集約値平均，標本集約値分散に関して，レコード毎に計算して以下のように差分更新する．過去に処理した全てのデータブロックである A に，新たに処理しているデータブロック B を差分更新する場合を考える．デー
タブロック A，B のそれぞれの要素数を na , nb ，標本集約値平均を meana , meanb ，標本集約値分散を var a , varb とすると，データブロック A ∪ B の要素数 nab と平均 meanab は以下のように計算する事ができる．

nab = na + nb
meanab =varab =

条件が成立するまで step.2-5 を実行 （条件）上位 k 件が確定

meana na + meanb nbnabna (vara + mean2a ) + nb (varb + mean2b )− mean2abnabする，あるいは，分割したデータ集合を全て処理

差分更新した結果を用いて，クエリ q(S) 結果の信頼区間の計

step.2 分割したデータブロックごとに，レコードを逐次的に算を行う時に，中心極限定理の式 (3) を適用する．具体的には，読む込むことで複数部分データに対するクエリ q(S) を同時実

キューボイドが保持しているデータ（標本数 N ，標本集約値平

行し，データキューブの基本単位であるキューボイドを差分更均 Average，標本集約値分散 V ar ）からクエリ結果 q(S) の信

新する．

頼区間は以下のように表される．但し，Ȳ が推定したい集約値

step.3 統計的信頼区間推定技術を適用し，クエリ q(S) の結

である．

√

果の式 (3) より信頼区間をキューボイドの値を用いて推定する．

step.4 クエリ q(S) 結果の信頼区間を用いて，クエリ結果の有用性の上限値と下限値を計算し，有用性の上限値と下限値から上位 k 件に成り得ないクエリ q(S) を特定する．

step.5 特定した上位 k 件に成り得ないクエリ q(S) の枝刈りを行う．

3. 1. 1 データ構造
定義 1 のクエリ q の group-by 属性と部分データの選択条（注 1）：分割個数はパラメータで指定

Y interval = [Ȳ − ϵ, Ȳ + ϵ], ϵ = zp

V ar
N −1

(13)

3. 3 フレームワークのアルゴリズム
Algorithm1 を用いて，本システムのフレームワーク部の動作の詳細を説明する．ユーザは入力として，探索した結果として得たい有用性の高い部分データの件数 k ，中心極
限定理における信頼係数 zp ，データセットを分割する割合

x array = [x0 %, x1 %, · · · , xl %]，データキューブを作成する際に使用する属性集合 Dimension，使用するデータセット D，Algorithm 1: フレームワークの動作
Input : k,zp ,x array,Dimension,DataSet

データの枝刈りを行う．
データキューブから例外部分データを特定する部分データとOutput: Results

グループ化属性の粒度のキューボイドを作成し，全体データに

1

DataRDDs ← RandomSampling(Dataset,x array)

関する OLAP クエリ結果のデータキューボイドは複数のベー

2

CUBE ← ∅スキューボイドを合算し作成する．部分データ集合 S，OLAP

3

Subset key ← ∅クエリ q ，特定する例外部分データの件数 k ，閾値は乖離度の4

foreach records ∈ DataRDDs do

上限値が k 番目に大きい部分データの乖離度の下限値を式 (14)5

if Subset key.size > k or Cube is empty then6

records.filterling(Subsetkey)

7

Cube ++ = QueryExecute(records)

8

foreach (subsetkey,value) ∈ Cube do

9

Cube1[subsetkey].Upper = value + ϵ

10

Cube1[subsetkey].Lower = value - ϵ

11

end

12

Results, Subset key ← ComputeUtility(Cube1)

13

foreach (subset, value) ∈ Cube do

14

if subset ∈/ Subset key then

15

Cube.Remove(subset)
end

16

end

17
18
19

end
end

とすると，上位 k 件に成り得る部分データの集合 Nk (S) を
式 (15) のように定義する．

threshold := T op k(D(q(S)).lower)(14)

Nk (S) := {S ∈ S | D(q(S)).upper >= threshold} (15)
Algorithm 2 を用いて探索空間の削減手法の詳細について説明する．Algorithm 2 では，データキューブ DataCube，探索する部分データの件数 k を入力 (Input) として，上位 k 件に成り得る部分データ名を出力 (Output) する．入力として与えられるデータキューブの値は既に統計的信頼区間推定の技術を適用したクエリ結果の上限値と下限値を保持している状態である（注 3）．まず，データキューブから全体データに関するクエリ
結果を保持するデータキューブを作成し（2 行目），同様に部分
データに関するデータキューブを使用する粒度のデータキュー
ブを作成する（3 行目）．部分データ毎に乖離度 D(q(S)) の上

クエリ q を入力し，上位 k 件の有用性の高い部分データを出限値と下限値を計算する（4 行目から 6 行目）．ここで使用す力する．最初にユーザが指定した分割割合 x array のレコー

る有用性の定義にあった評価関数を用いて，各グループ化属性

ドを保持する l 個のデータブロックに入力データ D を分割すの値での乖離度の最大値と最小値を算出する．そして，乖離度る（1 行目）．分割されたデータブロック毎に枝刈りされていの上限値が k 番目に大きい部分データの乖離度 D(q(S)) の下ない q(S), S ∈ S に合致しないレコードをスキップする（6 行目）（注 2）．その後，入力となる各レコードごとに UDAF を適用

限値を閾値に設定する (7 行目)．上位 k 件の候補集合を探索し（8 行目から 12 行目），候補集合 Nk (S) と乖離度を出力する．

することで複数部分データに対するクエリ処理を同時に処理してその結果を用いてデータキューブを差分更新する (7 行目)．

4. 評 価 実 験

データキューブのすべてのキューボイドに対して上限値と下限

本章では提案したエンジンにおいて複数クエリの同時実行と値を式 (3) を用いて計算する（9, 10 行目）．上限値と下限値

探索空間削減手法を両立したフレームワークの有効性を評価を保持したキューボイドを用いて，クエリ q(S), S ∈ S の有用した．

性を計算し，有用性の低い部分データ S の枝刈り判定を行う

4. 1 実 験 設 定（12 行目）．有用性の計算 · 枝刈り判定は分析アプリケーショ

提案フレームワークの有効性を検証するために，FlightData

ンが決定する（詳細は 3. 4 節で述べる）．枝刈り判定の結果をの実データに対して以下の 3 手法の実行時間と分析結果の精度

もとにデータキューブから有用性の低いクエリ q(S) に関するを，探索件数 k を変化させた場合とスケーラビリティに対してキューボイドの削除を行う（13 行目から 16 行目）．

比較する実験を行った．

3. 4 分析アルゴリズムと枝刈り•

Baseline

集約関数は AV G か SU M に限定して議論を進める．大量•

Query sharing (Share)の部分データを全て計算するのはコストが大きい．分析アルゴ•

Pruning and Query sharing (SharePruning)

リズムに使用する有用性にそぐわない部分データも存在するた

また分析結果の精度の指標として，Precision と以下の式 (16) でめ，統計的信頼区間推定技術を適用し上位 k 件の候補になり得

定義される nDCG (Normalized Discounted Cumulative Gain)

ない部分データを早期に特定し，その部分データの探索を枝刈を採用した．

りすることで高速化を図る．各標本に対し統計的信頼区間の技術を適用したクエリ結果を用いて，全体データからの乖離度の上限値と下限値を推定し，上位 k 件の候補になり得ない部分（注 3）：部分データに関して，グループ化属性値の中に集約対象のレコードが存（注 2）：但し，最初のデータブロックでは枝刈り条件が無いためレコードのスキッ

在しない場合，そのグループ化属性値の集約値を 0 とすることで，グループ化属

プは行わない．

性値の数を統一Algorithm 2: 有用性の計算

Baseline

Input : k，DataCube // k: 探索する件数，DataCube: クエ

Share

SharePruning

800

リ結果の信頼区間を保持するデータキューブ

Output: Subset key
DevianceArray ← ∅ // 乖離度を保持する変数2

All ← All GroupByAggregate(DataCube)

3

SubsetCube ← Subset GroupByAggregate(DataCube)

4

foreach (key, XY) ∈ SubsetCube do

5time (s)6001deviance ← CalucDevianceInterval(XY)

400

200

DevianceArray[key] ← deviance
6

end

7

threshold ← GetTop k(DevianceArray, k)8Subset key ← {}

9
10

13

1

5

10

15

20

25

30

k

foreach (key, deviance) ∈ DevianceArray do
if threshold ← <= deviance.Upper then

図 5 高速化性能の実験結果

Subset key + = {key}

11
12

0

end

リ共有化のみを行った場合とクエリ共有化と枝刈りを両立した

end

場合の実行時間は 10% 程度の削減しか出来ていない．
以上のことから，大域的・局所的な例外部分データの探索を，

DCG = rel1 +

k
∑
reli
i=2

nDCG =

探索件数を変化させても高精度の分析結果を出力できていることがわかる. 大域的な例外の上位 k 件に成り得ないかつ局所的

log2 i

DCG, IDCG : 理想状態の DCG
IDCG

な例外の上位 k 件に成り得ない，また例外計算に不要であると(16)

但し，ランキング中の i 番目の要素の適合度を表している reliとして，分析アプリケーションで定義された有用性を枝刈りせず正確に計算した場合の数値を採用する．
本実験には，CPU が Intel(R) Core(TM) i5 − 6600，クロッ
ク周波数は 3.30GHz ，コア数は 4，メモリは 16GB の PC を使用した．

FlightData. アメリカの航空に関するデータ（注 4）であり，出発/到着日時・出発/到着予定時刻・空港・距離やキャリアなど
属性が 111 種類存在する．また，使用したデータは 2017 年の全データであり 5, 674, 621 レコードを使用した．このデータが含むレコードの一部を表 1 などの属性と属性値から構成されている．

4. 2 実験結果と考察
OLAP クエリ： 使用したクエリは，部分データ集合のためのディメンション属性を月，集約関数を AV G，集約属性を遅延時間，グループ化属性を出発都市名とした．
パラメータ： 分析者の入力パラメータは，サンプリングにおいて 95% 信頼区間を用い (すなわち，Zp は 1.96 となる)，デー
タの分割割合を 20% のデータ集合 5 個とし，それぞれのパラメータで 5 回実行した平均値で比較を行う．
探索する部分データの件数 k を k = [1, 5, 10, 15, 20, 25, 30]と変化させた場合の実行時間の結果は図 5 であリ，精度結果は
表 2 である．高速化性能はベースラインに比べ最大 64.9% の実
行時間の削減が確認でき，すべての k の値において Precision,nDCG 共に高い値を維持していることがわかる．しかし，クエ（注 4）：https://transtats.bts.gov/DL_SelectFields.asp?Table_ID=236&

DB_Short_Name=On-Timeいう条件を満たす部分データが少なかったため，枝刈りによる

5. 関 連 研 究
SEEDB [6, 8] は，クエリ探索問題を定義しそれを自動化したフレームワークとデータドリブンで分析するためのデータ構造を提案している．水野ら [10] は，部分データ探索において大域例外を自動で特定するフレームワークを提案している．ユー
ザが入力したグラフ設定を使用して，Hoeﬀding の確率不等式
を用いて top-k の大域例外を効率的に特定する．小笠原ら [12]は，分析工程の自動化アプローチが SEEDB や水野らとは異なり，事前計算を必要とせず top-k に入り得ない部分データを枝刈りすることで高速化を行い効率的に局所例外を特定する．

Zenvisage [5] は，多数の OLAP クエリを共有化する組み合
わせパターンが膨大に存在するため，最適な組み合わせを高速に求めるのは NP 困難であるとされている問題に取り組むことで高速化を行っている．また，最適な組み合わせの OLAP
クエリを生成するための言語である ZQL を提案している．そして，3 次元のデータ構造を使用することでクエリ探索と部分
データ探索を両立している．

EKI [4] は現存する OLAP ツールが単一の Insights に対し一度の集約演算しか行うことができない問題とツールを使用するユーザからの入力 (group-by attribute や OLAP cell or

dimensions) を必要としている問題に取り組んでいる研究である．具体的には，従来の OLAP ツールと比べより複雑な演算処理が可能であり，Insights 間の結果を比較するための評価関数を提案している．ユーザの入力としてデータと演算回数を行
う回数のみを必要とし，複雑な演算を行うために演算子と演算を行う軸となる属性の組を自動的に作成し指定された演算回数の結果の top-k 件を出力する．さらに，基本的な集約関数，ラ表 1 FlightData に含まれるレコードの例

Year Quarter Month DayOfWeek FlightDate · · ·Carrier OriginStateName DestStateName DepDelay ArrDelay

2017

4

11

6

2017-11-04 · · ·

UA

Texas

North Carolina

-9.0

-12.0

2017

2

5

7

2017-05-14 · · ·AA

California

California

-4.0

-5.0

表 2 精度実験の結果

k

Precision / nDCG
Baseline, Share SharePruning

1

1.0 / 1.0

1.0 / 1.05

1.0 / 1.0

0.875 / 0.99

10

1.0 / 1.0

1.0 / 0.987

15

1.0 / 1.0

1.0 / 0.991

20

1.0 / 1.0

1.0 / 1.025

1.0 / 1.0

1.0 / 1.030

1.0 / 1.0

1.0 / 1.0

ンキング評価，%，平均からの乖離値，x 軸の前の値からの増減などの処理を行う演算子を追加している．そして，異なる演
算子間の結果をランキング付けするための新たな評価関数として，Impact Measure と Significance Measure の積を提案している．Impact Measure はビジネスの観点では対象としている部分データが Sibiling Group 内で占める割合を表している．

Significance Measure は p-value に基づいた演算子毎に適切な帰無仮説を設定し，異常度などの数値である．Data Cube を使用している点，複数の Insights を考慮している点は同一であるが，局所例外探索を適応していないこと，部分データの探索の枝刈りを実施していないことなどの点において本研究と異なる．

6. ま と め
本稿は，中心極限定理を用いた top-k 枝刈りとデータキュー
ブを用いたクエリ共有化を行うことによって処理の最適化を行った，大域的なデータ分析と局所的なデータ分析を両立した
探索的データ分析のフレームワークを提案した．実データに対して適用した結果，最大 64.9% の実行時間の削減し，大域的・局所的な例外部分データを同時に高い精度で特定することを確
認した．

謝

辞

本研究は JSPS 科研費 JP16K00154 の助成を受けたものです．また，この成果は、国立研究開発法人新エネルギー・産業技術総合開発機構 (NEDO) の委託業務の結果得られたものです．

文

献[1] J.W. Tukey, EXPLORATORY DATA ANALYSIS, AddisonWesley, 1977.
[2] W.L. Martinez, A.R. Martinez, and A. R, Exploratory Data
Analysis with MATLAB, vol.169, 2004.
[3] S. Idreos, O. Papaemmanouil, and S. Chaudhuri, “Overview
of Data Exploration Techniques,” Proceedings of the ACM
SIGMOD, 2015.

[4] B. Tang, S. Han, M. Lung, Y. Rui, and D. Dongmei, “Extracting Top-K Insights from Multi-dimensional Data,” Proceedings of the ACM SIGMOD, 2017.
[5] T. Siddiqui, A. Kim, J. Lee, K. Karahalios, and
A. Parameswaran, “Eﬀortless Data Exploration with zenvisage: An Expressive and Interactive Visual Analytics System,” Proceedings of the VLDB Endowment, 2016.
[6] M. Vartak, and S. Madden, “SEEDB : Automatically Generating Query Visualizations,” Proceedings of the VLDB,
vol.7, no.13, pp.1581–1584, 2014.
[7] A. Parameswaran, N. Polyzotis, and H. Garcia-Molina,“SeeDB: Visualizing Database Queries Eﬃcientl,” Proceedings of the VLDB Endowment, vol.7, no.4, pp.325–328,
2013.
[8] M. Vartak, S. Rahman, S. Madden, A. Parameswaran, and
N. Polyzotis, “SEEDB : Eﬃcient Data-Driven Visualization
Recommendations to Support Visual Analytics,” Proceedings of the VLDB Endowment, 2015.
[9] N. Kamat, P. Jayachandran, K. Tunga, and A. Nandi, “Distributed and interactive cube exploration,” Proceedings ofthe ICDE, pp.472–483, 2014.
[10] M. Yohei, S. Yuya, and O. Makoto, “Eﬃcient Data Slice
Search for View Detection,” Proceedings of the DOLAP,2017.
[11] L.O. Factor, “Mining Top-n Local Outliers in Large
Databases,” Proceedings of the ACM SIGKDD, pp.293–298,
2001.
[12] 小笠原麻斗，水野陽平，佐々木勇和，鬼塚真，“局所例外部分デー
タの自動探索，” Proceedings of the DEIM，2017.
[13] B. Mozafari, “Approximate Query Engines: Commercial
Challenges and Research Opportunities,” Proceedings of
the ACM SIGMOD, 2017.
[14] P.J. Haas, and S. Jose, “Large-Sample and Deterministic
Confidence Intervals for Online Aggregation,” Proceedingsof the SSDBM, 1997.
[15] J.F. Naughton, “Technical Perspective: Optimized Wandering for Online Aggregation,” Proceedings of the ACM
SIGMOD, vol.46, 2017.
[16] M.M. Breunig, H.P. Kriegel, R.T. Ng, and J. Sander, “LOF:
Identifying Density-Based Local Outliers,” Proceedings of
the ACM SIGMOD, no.October 2017, pp.1–12, 2000.
[17] J.M. Hellerstein, P.J. Haas, and H.J. Wang, “Online aggregation,” Proceedings of the ACM SIGMOD, 1997.
[18] F. Li, B. Wu, K. Yi, and Z. Zhao, “Wander Join: Online
Aggregation via Random Walks,” Proceedings of the ACM
SIGMOD, 2016.