DEIM Forum 2013 A8-2

複数 GPU による確率的頻出アイテム集合マイニングの高速化
小澤

佑介†

天笠

俊之††,†††

北川 博之††† 筑波大学大学院システム情報工学研究科 〒 305–8573 茨城県つくば市天王台 1–1–1†† 筑波大学システム情報系 〒 305–8573 茨城県つくば市天王台 1–1–1††† 宇宙航空研究開発機構 宇宙科学研究所 〒 305–8505 茨城県つくば市千現 2–1–1
E-mail: †kyusuke@kde.cs.tsukuba.ac.jp, ††{amagasa,kitagawa}@cs.tsukuba.ac.jp
あらまし

実世界に大量に存在する，不確実性を含むデータを，効果的かつ効率的に扱う技術が近年注目を集めている．このような不確実データに対して，頻出アイテム集合マイニングを行なう手法がいくつか提案されてきている．
しかし，不確実性を考慮した処理の計算量が多いため，巨大なデータを扱うためにはさらなる高速化が必要と考えられる．そこで，我々は GPGPU を用いた高速化の研究を行なっている． 先行研究では単一 GPU による手法を提案し，その有効性を示した．本稿では，これを発展させ，複数の GPU を用いる手法を提案する．提案手法は，CPU-GPU間のデータ転送を削減し，かつ GPU 間の負荷分散を行なう．さらに，実験により提案手法の性能を評価する．
キーワード

GPGPU, 不確実データベース, 頻出アイテム集合マイニング

Yusuke KOZAWA† , Toshiyuki AMAGASA††,††† , and Hiroyuki KITAGAWA††† Graduate School of Systems and Information Engineering, University of Tsukuba
Tennoundai 1–1–1, Tsukuba, Ibaraki, 305–8573 Japan†† Faculty of Engineering, Information and Systems, University of Tsukuba
Tennoundai 1–1–1, Tsukuba, Ibaraki, 305–8573 Japan††† Institute of Space and Astronautical Science, Japan Aerospace Exploration Agency
Sengen 2–1–1, Tsukuba, Ibaraki, 305–8505 Japan
E-mail: †kyusuke@kde.cs.tsukuba.ac.jp, ††{amagasa,kitagawa}@cs.tsukuba.ac.jp

1. 序

論

そこで，我々は GPGPU (General-Purpose computation onGPU) を用いた，確率的頻出アイテム集合マイニングの高速

実世界では不確実性を含むデータが爆発的に増加しており，化を行なっている [10]．GPGPU は，元々はグラフィック処理

これらを扱う技術が近年非常に注目されてきている．例えば，用のプロセッサである GPU を，グラフィック処理以外の一般

RFID センサを利用した購買行動の分析の際，センサの誤読を的な処理の高速化に利用する手法である．GPU は数百以上のする可能性があるため，不正確なデータを扱う必要がある．こ演算ユニットを有しているため，極めて並列度の高いデータ

れ以外にも，ノイズやプライバシ保護などの様々な理由によっ処理を行なうことができる．また，GPU を効果的に用いるこて不確実データが生成されうる．このようなデータを効果的かとで，省電力かつ安価で CPU 以上の性能を出すことが可能な

つ効率的に処理するために，不確実データベースの研究が広くため，近年非常に注目されており，多くの研究がなされてい行なわれてきている [1]．

る [7], [9], [13], [15]．さらに，GPU はその構造が比較的単純でこのとき，不確実データを対象に，主要なデータマイニング
手法の一つである頻出アイテム集合マイニングを適用することあるため，処理性能の向上が目覚ましく，GPGPU は今後ます
ます重要な技術になると考えられる．

も可能であり，多くの研究が見られる [5], [6], [16], [17]．ここで，先行研究では，一つの GPU のみを用いた確率的頻出アイテ

データの不確実性は確率によって表現されるため，この問題はム集合マイニングの高速化を行なってきた．本稿では，これを確率的頻出アイテム集合マイニングと呼ばれる．この問題に対発展させ，複数 GPU を用いた手法を提案する．複数 GPU をする手法がいくつか存在するが，確率的頻出アイテム集合マイ用いる利点として，GPU の増加による並列度の向上がある．

ニング中の確率計算の処理が計算量の多いものであるため，大また，GPU のメモリはそれほど大きくないが，複数 GPU に量のデータを処理するためにはさらなる高速化が必要である．

することで利用可能なメモリ領域が増加し，巨大なデータを扱

表 1 不確実トランザクションデータベースの例

うことも可能となる．一方，複数 GPU を利用する上で問題になる点として，GPU 間でのデータ通信がある．通常，GPU は

ID

アイテム集合存在確率

PCI-Express によって接続されているが，ここの通信のメモリ

T1{game, music}

0.8

T2

{music, video}

0.7

T3

{game}

0.9

T4{game, music, video}

0.5

バンド幅が小さいため，ボトルネックになる可能性が高い．そのため，GPU 間でのデータの依存をできるだけ削減することが望ましい．提案手法では，GPU 間でのデータ通信の削減に加え，負荷分散を行ない処理の高速化を図る．さらに，複数
また，実験により，提案手法の性能を評価した．
本稿の構成は以下の通りである．2 節で，本研究で扱う問題の定義と，提案手法の元となる pApriori アルゴリズムについprobability

0.5

GPU を持つノードからなるクラスタにおける手法も提案する．

0.47

0.4
0.28

0.3
0.22
0.2
0.1
0.03

て説明する．3 節で提案手法について説明し，4 節で評価実験

0.0

0

1

の結果と考察を述べる．関連研究について 5 節で説明し，最後

2

3

0.0
4

supportに 6 節でまとめと今後の課題について述べる．

図 1 支持度確率質量関数 f{music} .

2. 確率的頻出アイテム集合マイニング
本節では，確率的頻出アイテム集合の定義とマイニングの手法について説明する．まず，従来の，不確実でないデータベースに対する問題の定義を 2. 1 節で述べ，2. 2 節で確率的頻出ア
イテム集合マイニングの定義を行なう．2. 3 節では Sun ら [16]の提案した pApriori アルゴリズムについて説明する．

2. 1 頻出アイテム集合
アイテム全体の集合を I とする．アイテム i ∈ I の集合をア
イテム集合と言い，要素数 k のアイテム集合を k-アイテム集合と呼ぶ．ID とアイテム集合のペアをトランザクション T ，トランザクションの集合をトランザクションデータベース T という．トランザクション数 n のトランザクションデータベース Tとアイテム集合 X が与えられたとき，T における X の支持度を sup(X) と表す．ここで，アイテム集合 X の支持度とは，Xを含むトランザクションの数を指す．ユーザが与えた最小支持
度 minsup 以上の支持度を持つアイテム集合を頻出アイテム集
合という．

2. 2 確率的頻出アイテム集合
トランザクションデータベース T の各トランザクションに存在確率を与えたものを，不確実トランザクションデータベー

確率は 0.8 · (1 − 0.7) · (1 − 0.9) · (1 − 0.5) = 0.012 となる．
このとき，アイテム集合 X の支持度 sup(X) は各可能世界ごとに異なるため，確率変数になると考えられ，支持度の分布は確率質量関数によって表される．アイテム集合 X の支持度の確率質量関数を支持度確率質量関数 (Support Probability Mass

Function, SPMF) fX と呼ぶ．特に，fX (k) は sup(X) = kとなる確率を示す．ここで，k は sup(X) が取りうる値，すな
わち k ∈ {0, 1, ..., |U|} である．例えば，表 1 における SPMF

f{music} は図 1 のようになる．横軸は支持度，縦軸はその支持度となる確率を表している．
以下の条件を満たすアイテム集合を確率的頻出アイテム集合と呼ぶ：

P (sup(X) >= minsup) =|U |∑fX (k) >= minprob,(1)

k=minsupここで，minprob ∈ (0, 1] はユーザに与えられるしきい値である．例えば，minsup = 2, minprob = 0.5 としたとき，表 1 の
不確実トランザクションデータベースにおいて，P (sup({music}) >= minsup) = f{music} (2) + f{music} (3)ス U という．存在確率は，トランザクションがデータベース中= 0.47 + 0.28に存在する確率を表す．表 1 に不確実トランザクションデータ

= 0.75 > minprob

ベースの例を示す．これはある店の客の購買行動を表す．すな
わち，game と music が同時に購入される確率は 0.8，music ととなるため，アイテム集合 {music} は確率的頻出アイテム集合

video が同時に購入される確率は 0.7，などである．

である．

不確実トランザクションデータベースは一般的に，可能世界

本研究で扱う問題は以下のように定義できる．

意味論によって解釈される．すなわち，不確実トランザクショ

問題 （確率的頻出アイテム集合マイニング）．不確実トラン

ンデータベースは，それぞれ別々のトランザクションの組み合

ザクションデータベース U ，minsup, minprob の三つが与えら

わせからなる可能世界の集合を生成すると考える．例えば，表れたとき，U からすべての確率的頻出アイテム集合を抽出する．

1 のデータベースは，∅, {T1 }, {T2 }, {T3 }, {T4 }, {T1 , T2 } など，

2. 3 pApriori アルゴリズム

全部で 16 個の可能世界を生成する．また，各可能世界はそれ

pApriori アルゴリズム [16] は，Agrawal ら [3] によって提案

ぞれ存在確率を持つ．この存在確率は，各世界に含まれるトラ

された Apriori アルゴリズムを，不確実データベースに適用しンザクションをもとに計算される．例として表 1 における可能たものである．pApriori アルゴリズムでは，まず，1-アイテム

世界 {T1 } を考えると，その存在確率は，T1 が存在する確率と集合が確率的頻出アイテム集合であるかを，SPMF を計算する

T2 , T3 , T4 が存在しない確率から求められる．すなわち，そのことによって判定する．次に，k = 2 として処理を行なっていく．確率的頻出 (k − 1)-アイテム集合から，候補 k-アイテム集［補題 2］ cnt(X) < minsup ならば，アイテム集合 X は確率合を生成し，これらの候補の中から確率的頻出 k-アイテム集合

的頻出アイテム集合ではない．

を抽出する．そして k を 1 増やす．これらの処理を，確率的頻［補題 3］ µ = esup(X), σ = (minsup − µ − 1) / µ とする．

出アイテム集合が見つからなくなるまで続ける．最終的に，不

このとき，
−σµ
•σ>
< minprob= 2e − 1 かつ 2
( −σ 2 µ )• 0 < σ < 2e − 1 かつ exp< minprob
4のどちらかが成り立つならば，アイテム集合 X は確率的頻確実トランザクションデータベースから得られる全ての確率的
頻出アイテム集合を結果として返す．以下の節で，候補の生成と確率的頻出アイテム集合の抽出について説明していく．

2. 3. 1 候補アイテム集合の生成

出アイテム集合ではない．

候補アイテム集合の生成は二つのフェイズに分けられる．一つ目は結合フェイズ，二つ目は枝刈りフェイズである．
結合フェイズでは，二つの確率的頻出 (k − 1)-アイテム集合

3. GPGPU を用いた
確率的頻出アイテム集合マイニング

X, Y が結合可能であるかを判定する．ここで二つの (k − 1)-ア

本節では，GPU を用いた確率的頻出アイテム集合マイニン

イテム集合 X, Y が結合可能とは，X.itemi が X 中の i 番目のアグの手法について述べる．3. 1 節では先行研究の単一 GPU にイテムを表すとすると，X.item1 = Y.item1 ∧· · ·∧X.itemk−2 =よる手法 [10] について簡単に説明する．その後，3. 2 節で単一

Y.itemk−2 ∧ X.itemk−1 < Y.itemk−1 が成り立つことをいう．

ノード上での複数 GPU による手法を，3. 3 節で複数ノード上結合可能ならば，X と Y の和集合から，候補 k-アイテム集合の手法を述べる．

を作り，その候補を候補 k-アイテム集合の集合 Ck に格納する．
枝刈りフェイズでは，以下の補題を利用して枝刈りを行う [16]．
［補題 1］（逆単調性）
アイテム集合 X が確率的頻出アイテム集合ならば，X の部
分集合も確率的頻出アイテム集合である．
この補題の対偶から，アイテム集合 X の部分集合が確率的
頻出アイテム集合でなければ，X も確率的頻出アイテム集合で

3. 1 単一 GPU による高速化
単一 GPU による手法の基本的な流れは pApriori アルゴリズ
ムと同様で，候補の生成と確率的頻出アイテム集合の抽出の二つの処理からなる．候補の生成は 2. 3. 1 節で説明したアルゴリ
ズムにより GPU 上で行なう．また，確率的頻出アイテム集合の抽出は，(1) 包含判定，(2) 枝刈り，(3) フィルタリング，(4)SPMF の計算，の四つのステップからなる．

無いことが分かる．すなわち，結合フェイズで作成した各候補

包含判定では，生成された各候補が，不確実トランザクショ

k-アイテム集合について，その要素数 k − 1 の部分集合が確率

ンデータベースの各トランザクションに含まれているかを判定

的頻出アイテム集合であるかを確認し，そうでなければ Ck かする．一つのトランザクションに対する判定結果は 1 ビットでらその候補を削除する．

表現することが可能なため，判定結果はビット列によって保持2. 3. 2 確率的頻出アイテム集合の抽出する．これにより，k > 1 の場合は，k − 1 のときの包含判定結

アイテム集合 X が確率的頻出アイテム集合であるかは，X果を利用することで，高速に処理することが可能となる．すなの SPMF を計算し，式 1 を調べなければならない．そのため，

わち，ある k-アイテム集合の包含判定をするには，そのアイテ

SPMF を効率的に計算することが重要となる．Sun らは動的計

ム集合の生成に利用された，二つの確率的頻出 (k − 1)-アイテ

画法による方法と，分割統治法による方法の二種類の計算法を

ム集合の包含判定結果の間のビット単位の AND 演算を行なえ提案している．ここではより計算量の少なく，GPU 上での処ばよい．

理に適している分割統治法による方法のみを説明する．

二つめのステップの枝刈りでは，2. 3. 3 節で説明した二つのこのアルゴリズムは，入力として不確実トランザクション

値を計算し枝刈りを行なう．枝刈りされなかった候補に対して

データベース U とアイテム集合 X を受け取り，アイテム集合

は，フィルタリングを行なう．ここでは，候補を含んでいない

X の SPMF fX を返す．U が一つのトランザクションのみから

トランザクションを，SPMF の計算から除くための前処理をすなる場合は，SPMF を直接計算する．U がトランザクションをる．これは，トランザクションが候補を含まない場合，そのト二つ以上含んでいる場合は U を二つに水平分割する．そして，

ランザクションの存在確率は候補の SPMF に影響しないためそれぞれのデータベースに対して再帰的に SPMF を計算し，計である．この前処理の後，実際に SPMF を計算し，候補が確算された二つの SPMF を畳み込みにより一つにする．畳み込

率的頻出アイテム集合であるかを判定する．

みをそのまま計算すると O(n2 ) の計算量となるが，高速フーリ
エ変換を利用することで O(n log n) に抑えることができる．

3. 2 単一ノード・複数 GPU による高速化
複数 GPU を用いる場合，メモリが分散して存在するため，い2. 3. 3 枝 狩 りかにデータを分割するかが重要となる．分散メモリ環境におけるSPMF の計算は計算量が多いため，実際に計算する前に確率

頻出アイテム集合マイニングの研究は数多く存在する [4], [18]．

的頻出アイテム集合でないものを判定したい．そのために以下

これらの研究のデータの分割方式は主に (1) 支持度のカウントの二つの指標を用いる．不確実トランザクションデータベースの分割，(2) データベースの分割，(3) 候補の分割，の三つに分

U 中の，アイテム集合 X を含むトランザクションの数を表す

けられる．本稿では，候補の分割に基づく手法を提案する．こcnt(X) と，sup(X) の期待値を表す esup(X) である．

れにより，pApriori アルゴリズム中で最も計算量の多い SPMF

このとき，以下の二つの補題が成り立つ [16]．

Algorithm 1: Prefix partitioning
1

k = 1

2

包含判定・枝刈り // CPU3

CPU から各 GPU に候補とすべての包含判定結果を転送

4

フィルタリング・SPMF の計算 // GPU

5

確率的頻出 1-アイテム集合を CPU 側に集約

GPU1

GPU2

GPU3

GPU4

ab
ac
ad
ae
af
ag
ah

bc
bd
be
bf
bg
bh

cd
ce
cf
cg
ch

de
df
dg
dh

gh
6

k = 2

7

候補 k-アイテム集合の生成 // CPU

8

候補を prefix をもとに分割し GPU に転送

910// 包含判定には k − 1 の包含判定結果を利用
確率的頻出 k-アイテム集合の抽出 // GPU

12

確率的頻出 k-アイテム集合を CPU 側に集約

13

各 GPU にすべての確率的頻出 k-アイテム集合を転送

14

k ←k+1

15

候補 k-アイテム集合の生成 // GPU

ef
eg
eh

図 2 Prefix partitioning

while 候補集合 Ck =| ∅ do

11

fg
fh

GPU1

GPU2

GPU3

GPU4

ab
af
bd
bh
cg
dg
eh

ac
ag
be
cd
ch
dh
fg

ad
ah
bf
ce
de
ef
fh

ae
bc
bg
cf
df
eg
gh

図 3 Round-robin partitioningの計算を，各 GPU が独立して処理できるようになる．3. 2. 1から 4 に prefix が a から d の候補をそれぞれ割り当てたあと，節で，単純な候補の分割方式による手法を，3. 2. 2 節と 3. 2. 3

prefix が e の候補を GPU4 に，prefix が f の候補を GPU3 に，

節では負荷分散を考慮した手法を説明する．

という順番で割り当てていく．

3. 2. 1 Prefix Partitioning

次に，3. 1 節で述べた手法により，各 GPU 上で確率的頻出

ここでは，二つのアイテム集合の prefix が異なる場合には

k-アイテム集合の抽出をする（11 行目）．その後，発見された結合可能とならない，という性質を生かした手法について説明

確率的頻出 k-アイテム集合を CPU 側に集約し（12 行目），こする．本手法における処理の流れを Algorithm 1 に示す．このれらをすべての GPU にブロードキャストする（13 行目）．こ

手法は候補の prefix をもとに分割を行なっているため，Prefix

れは，次に行なう候補の生成の枝刈りフェイズに必要なためでPartitioning (PP) と呼ぶ．PP は (1) k = 1 の処理, (2) k = 2

ある．ただし，候補の生成のもととなる確率的頻出アイテム集における候補の分割, (3) その後の処理，の三つのフェイズに分合はそれぞれの GPU 上で発見されたもののみを用いる．このけられる．

ように，9–15 行目を候補が無くなるまで繰り返す．

まず，不確実トランザクションデータベースから候補 1-ア

PP は候補を prefix にしたがって分割することで，k = 2 以降

イテム集合を生成し，それらに対し CPU 上で包含判定と枝刈は GPU 間のデータの依存関係を少なくできる．しかし，prefix

りを行なう（2 行目）．GPU ではなく，CPU 上でこの処理をに従って候補を分割すると，SPMF の計算が必要な候補が多いすることで，データベースを GPU に転送する必要が無くな

グループとそうでないグループができる可能性があり，負荷分

り，データ転送量を削減できる．また，単一 GPU の手法では，散の観点からは望ましくないものとなる．この点を改善した手GPU の特性上これらのステップを別々に行なったほうが高速法を以下の節で述べる．

であったが，実際にはこれらのステップはまとめて処理可能で

3. 2. 2 Round-Robin Partitioning

あるため，ここでは同時に処理している．この時点で残ってい本節で説明する手法は，候補を round-robin 方式で分割する

る候補を等分して，各 GPU に転送する（3 行目）．このとき同ため，Round-Robin Partitioning (RRP) と呼ぶ．基本的な流時に，後の包含判定で必要となるため，すべての候補の包含判

れは PP と同様である．主な違いは，Algorithm 1 の 8 行目，定結果も転送しておく．その後，各 GPU の担当する候補に対

10–11 行目，13–15 行目に存在する．具体的に言うと，8 行目をしてフィルタリング・SPMF の計算をし（4 行目），CPU 側に

8

ラウンドロビン方式で候補を GPU に割り当て転送

確率的頻出 1-アイテム集合を転送する（5 行目）．

k = 2 では，5 行目で集めた確率的頻出 1-アイテム集合をもに，10–11 行目をとに，候補 2-アイテム集合を生成する（7 行目）．そして，候10// 包含判定には k = 1 の包含判定結果を利用

補を prefix をもとに分割し GPU に転送する（8 行目）．例え

11

確率的頻出 k-アイテム集合の抽出 // GPU

ば，8 個の確率的頻出 1-アイテム集合 {a}, {b}, {c}, {d}, {e},{f}, {g}, {h} が発見され，GPU が四つあると仮定すると，図2 のように候補が割り当てられる．各 GPU に対して割り当てられる候補の数をできるだけ均等にするために，図 2 のようにジグザグに prefix による割り当てを行なう．すなわち，GPU1に，13–15 行目を
13k ←k+1

14

候補 k-アイテム集合の生成 // CPU

15

ラウンドロビン方式で候補を GPU に割り当て転送にしたものとなる．

表2

ノードの構成CPU

GPU

Processor Intel Xeon E5645 (2.4GHz, 6 コア) x2 NVIDIA Tesla M2090 (1.3GHz, 512 コア) x2
メモリ

48 GB

6GB/GPU

表 3 実験に用いたデータセット
データセット

アイテム数 トランザクションの平均要素数

トランザクション数

密度

Accidents

468

33.8

340,183

7.2%

T25I10D500K

7558

25

499,960

0.33%

Kosarak

41270

8.1

990,0020.020%

8 行目では，図 3 に示すように，各 GPU にラウンドロビン
方式で順々に候補を割り当て，転送をする．

10–11 行目での大きな違いは，GPU 上で包含判定をする際GPU に割り当てられた候補の推定処理時間の合計を意味する．
その後，各候補に対して，担当処理時間が最小の GPU を探し
その GPU に候補を割り当てる，という処理を繰り返す．

に k − 1 の包含判定結果ではなく k = 1 のものを利用する点

k = 1 の場合はアイテム集合 X の cnt(X) が候補の分割時点である．RRP では prefix による分割ではないために，ある k-で計算されているため，処理時間の推定に cnt(X) の値をそのアイテム集合の生成元が別々の GPU に分散している可能性がまま利用できる．一方，k > 1 の場合には，候補の分割時点であり，k − 1 の包含判定結果を利用するには別の GPU が保持

は cnt が計算されていない．そこで，重みを計算する際には，しているデータを参照する必要がある．しかし，この処理にはアイテム集合 X の cnt(X) を minX ′ ⊂X,|X ′ |=k−1 cnt(X ′ ) で代GPU 間のデータ転送が必要なため，避けるべきである．一方，替する．これは，cnt(X) の上限の値を表し，実際にはこれよ

k = 1 の場合の包含判定結果は最初に GPU に転送してあるのりも低い値となることが予想される．しかし，処理時間の推定で，これを利用することで無駄な通信を削減できる．k-アイテに必要なのは cnt(X) 以上の 2 のべき乗の値であるため，あるム集合 X の包含判定は，各アイテム i ∈ X の包含判定結果を程度の誤差ならば結果には影響がないと考えられる．

用いて，k − 1 回のビット単位の AND で処理可能である．

3. 3 複数ノード・複数 GPU による高速化

13–15 行目での違いは，候補の生成を GPU 上ではなく CPU

本節では，各ノードが複数の GPU をもつクラスタを用いた上で行ない，ラウンドロビンで候補の分割を行なう点である．

確率的頻出アイテム集合マイニングの手法について述べる．ここれにより，毎イテレーションにおいて負荷分散を行なうこと

こでは，すべてのノードが入力の不確実トランザクションデーができる．また，候補の転送のみなのでデータの転送量もそれタベースを保持していると仮定する．

ほど多くならず，通信時間は小さく抑えられる．

基本的には 3. 2 節で説明した手法と同様の方式で，各ノー3. 2. 3 Count-Based Partitioning

ドに候補を分割して並列処理を行なう．ノード間の候補の分割

本節では，候補の cnt の値をもとに候補の分割を行なう手法には RRP または CBP を用いる．具体的な処理の流れは以下

Count-Based Partitioning (CBP) について説明する．3. 1 節のようになる．k = 1 の場合は，Algorithm 1 の 2–5 行目を各で述べたように，アイテム集合 X の SPMF の計算には cnt(X)

ノードが実行する．ここで，各ノードが処理する候補はノード個のトランザクションのみを用いればよい．すなわち，SPMF

ごとに異なるものを対象とするため，抽出される確率的頻出アの計算時間は cnt の値に依存する．また，GPU の処理時間のイテム集合も異なる．そのため，各ノードで確率的頻出アイテ

大部分を SPMF の計算が占めている．そのため，cnt を考慮しム集合を発見したあとに，次の候補生成のために他のノードにて候補を分割することで，GPU 間の負荷分散の達成が期待さ

その結果をブロードキャストする必要がある．
次に k = 2 に進み，候補の生成を行なう．各ノードが担当すれる．

GPU 上では，SPMF の計算の単純化のために，cnt(X) 個で⌈log2 cnt(X)⌉る候補は RRP または CBP によって決定する．このとき，ノー個のトランザクションを用いている [10]．

ド内の候補の分割も同様の手法を用いる．その後，各ノードでそのため，2 のべき乗個のトランザクションに対する SPMF の見つかった確率的頻出 2-アイテム集合をブロードキャストし，計算時間がわかれば，候補の処理時間の推定ができる．ここでk を 1 増やし次の反復に進む．以上のように，ノード間の通信は，これらの時間をあらかじめ計測しておき，その値を候補のを確率的頻出 k-アイテム集合のみにすることで，通信時間を極

処理時間の推定値として利用する．計測した値は実行環境依存力削減している．

はなく 2で，データには依存しないため，一度計測すればあとは使いまわすことができる．

CBP の処理の流れは RRP と同様で，候補の分割方式のみ

4. 実

験

4. 1 実 験 環 境が異なる．候補の分割は，各 GPU が担当する候補の処理時間提案手法を CUDA（注 1）, OpenMP, MPI を用いて実装した．

の合計が均等になるように行なう．まず，各 GPU の担当処理

実験は，表 2 に示したノード 8 個からなるクラスタ上で行なっ

時間を 0 に初期化する．ここで，GPU の担当処理時間とは，（注 1）：http://www.nvidia.com/object/cuda_home_new.html

2.2

2.2
PP

RRP

PP

RRP

CBP

PP

2.0

1.8
1.6
1.4
1.2

1.8
1.6
1.4
1.2

33

35

37

0.7

minsup (%)

0.75

0.8

0.85

RRP

CBP

1.9

1.6

39

0.4

0.5

0.6

1.0

1.0

37

CBP

1.2

1.3

1.0

RRP

1.4

1.6

1.3

PP

1.6

2.2

1.9

0.6

1.8

2.5

2.2

0.5

2.0
PP

Load imbalance factor

Load imbalance factor

CBP

0.4

(c) Kosarak: 性能向上率

2.8

35

0.3

minsup (%)

3.1
RRP

2.5

33

1.0 0.2(b) T25I10D500K: 性能向上率

2.8

31

1.4

minsup (%)(a) Accidents: 性能向上率

PP

1.6

1.2

1.0 0.65

39

CBP

1.8

Load imbalance factor

1.0 31

RRP

2.0

Speedup ratio

Speedup ratio

2.0

Speedup ratio

2.2

CBP

0.65

0.7

minsup (%)

0.75

0.8

0.85

0.2

minsup (%)

0.3

minsup (%)(d) Accidents: 各 GPU における SPMF の計算時(e) T25I10D500K: 各 GPU における SPMF の計(f) Kosarak: 各 GPU における SPMF の計算時間

間の偏り

算時間の偏りの偏り

図4

単一ノード上で複数 GPU を用いた実験結果

た．ノード間は InfiniBand QDR (Quad Data Rate) で接続さ

（ 3 ） Kosarak では CBP が最も良い性能を示している．

れている．

(1) の理由は，minsup の値が小さくなると候補の数が増加

三つのデータセットに対して実験を行なった．各データセッ

し，各 GPU が並列に処理できる仕事が増えるためである．たトの特徴を表 3 に示す．密度は，トランザクションの平均要素

だし，Accidents はアイテム数が少なく候補の数はそれほど多数をアイテム数で割ったものである．Accidents と Kosarak は，くならないが，良い性能向上率となっている．これは以下のよ（注 2）にある実データである．Accidents は比較

うに考えられる．SPMF の計算量は 2. 3. 3 節で述べた cnt に依的密なデータセットで，Kosarak は三つの中で最も疎なデータ存しているため，この値が大きいと SPMF の処理に時間がかかセットである．明記していない場合，minsup を，Accidents ではる．そして，Accidents では cnt の値が極めて大きくなるため，

トランザクション数の 33%，Kosarak ではトランザクション数

SPMF の計算時間が支配的となる．そのため，Accidents では，の 0.2%とする．T25I10D500K は，IBM data generator（注 3）に候補が少ない場合でも常に 2 倍程度の性能を示している．また，

よって生成された合成データである．minsup はデータセット

図 4(c) で minsup が 0.2%の場合に 2 倍以上の性能となっていのサイズの 0.65%とする．これらのデータセットに対して，トるのは，候補の数が非常に多くなった場合に，GPU 上の候補

ランザクションの存在確率を平均 0.5，分散 0.02 の正規分布に生成よりも，CPU 上の候補生成が高速になるためである．

FIMI Repositoryより与える．また，デフォルトの minprob を 0.5 とする．

(2) の理由は，RRP と CBP が，PP よりも上手く負荷分散

4. 2 単一ノードによる実験を行なえているためである．図 4(d)–4(f) は各提案手法を用い

本節では，単一ノード上の複数 GPU による手法について評たときの GPU 間の SPMF の計算時間の偏り度合いを示してい価する．図 4 に実験結果を示す．図 4(a)–4(c) は，単一 GPUる．縦軸は，各 GPU で行なった SPMF の計算時間をそれぞれによる手法 [10] に対する，三つの提案手法 (PP, RRP, CBP)

合計し，最大の計算時間を最小の計算時間で割ったものを示しの性能向上率を示している．これらのグラフから以下の三つのている．すなわち，1 の場合が最も負荷分散されていて，大きくことがわかる．

なるほど負荷が偏っていることを示している．図 4(d)–4(e) か（ 1 ） minsup の値が小さくなるにつれて，複数 GPU の手ら，PP では負荷が大きく偏っており，RRP と CBP は負荷分法の性能向上率があがっていく．

散が達成されていることがわかる．Accidents と T25I10D500K（ 2 ） Accidents と T25I10D500K では，RRP と CBP がではでは，候補の cnt の値にあまりばらつきがないため，RRP

PP と比較して常に良い性能を示している．

と CBP の性能はほぼ同じになっている．

(3) の理由は，他の二つのデータセットと違い，Kosarak で（注 2）：http://fimi.cs.helsinki.fi/（注 3）：http://miles.cnuce.cnr.it/~palmeri/datam/DCI/datasets.php

は候補の cnt の値に大きなばらつきがあるためである．この場
合，RRP では上手く負荷が分散されないが，CBP では cnt の

0.5

4

CBP-Comm
CBP-GPU
CBP-CPU

3
2
1
0 1

2

3

4

5

6

7

1.2
RRP-Comm
RRP-GPU
RRP-CPU

0.4
0.3
0.2
0.1
0.0 1

8

2

Number of nodes

3

4

5

6

7

1.2

1.1

1.0
3

4

5

6

0.2
2

7

4

5

6

7

8

2.2
RRP

CBP

1.2

1.1

1.0

8

3

(c) Kosarak: 処理時間とその内訳

Load imbalance factor

Load imbalance factor

CBP

1.3

2

0.4

Number of nodes

1.3

1

0.6

0.0 1

8

CBP-Comm
CBP-GPU
CBP-CPU

0.8(b) T25I10D500K: 処理時間とその内訳

1.4
RRP

RRP-Comm
RRP-GPU
RRP-CPU

1.0

Number of nodes(a) Accidents: 処理時間とその内訳

Load imbalance factor

CBP-Comm
CBP-GPU
CBP-CPU

Execution time (sec)RRP-Comm
RRP-GPU
RRP-CPU

Execution time (sec)

Execution time (sec)

5

1

2

Number of nodes

3

4

5

6

7

RRP

CBP

2.0
1.8
1.6
1.4
1.2
1.0

8

1

Number of nodes

2

3

4

5

6

7

8

Number of nodes(d) Accidents: 各 GPU における SPMF の計算時(e) T25I10D500K: 各 GPU における SPMF の計(f) Kosarak: 各 GPU における SPMF の計算時間

間の偏り

算時間の偏りの偏り

図5

複数ノードを用いた実験結果

値を考慮しているため負荷分散が達成されている．

4.5 倍の高速化となった．ノード数を増やしてもあまり高速化

図 4(b) で PP の性能向上率が大きく下がっている箇所があるを達成できていないのは，候補の cnt の値が小さく GPU がのは以下のような理由による．prefix ごとに生成される確率的行なう処理が少ないためである．そのため，すべてのノード

頻出アイテム集合の数にばらつきがあるため，抽出された確率が処理する k = 1 の包含判定と枝刈りが，全体の処理時間の的頻出 1-アイテム集合によって，仕事が上手く分散される場合

10–25%を占めており，この部分がボトルネックとなる．また，とされない場合がある．ここでは，図 4(e) からもわかるように，

CBP と RRP がほぼ同じ性能となったのは，候補間で cnt にあGPU 間で大きく仕事が偏ってしまい大幅に性能が下がった．

まりばらつきがないため，RRP でも負荷分散ができているた

4. 3 複数ノードによる実験めである（図 5(e)）．

本節では，複数ノードを用いた二つの手法 CBP と RRP に

一方，Kosarak では cnt の値にばらつきがあり，ノード数がついて評価する．図 5 に実験結果を示す．ここでは，各ノード増えるにつれて RRP の場合の負荷の偏りが大きくなっていくがデータを読み終えてから，マスターノードにすべての確率的（図 5(f)）．CBP では負荷が分散されているため，RRP と比較

頻出アイテム集合を集約するまでを処理時間としている．

して 1.3 倍程度の性能となった．

図 5(a)–5(c) は，各データセットに対してデフォルトの minsupを用い，ノード数を変化させたときの RRP と CBP の処理時間

5. 関 連 研 究とその内訳を示している．処理時間は，通信時間 (Comm)，GPU

本節では，関連研究について，頻出アイテム集合マイニング，

での処理時間 (GPU), CPU での処理時間 (CPU) の三つからなる．

確率的頻出アイテム集合マイニング，GPGPU の三つの観点か

ここで，GPU は k > 1 の包含判定，k > 1 の枝刈り，フィルタ

ら述べる．

リング，SPMF の計算を含み，CPU は k = 1 の包含判定と枝刈

頻出アイテム集合マイニング．相関ルールマイニングの問題

り，候補生成を含む．また，図 5(d)–5(f) は，4. 2 節と同様には Agrawal らによって初めて導入された [2]. 頻出アイテム集

GPU 間の負荷の偏り度合いを示している．

合マイニングは，相関ルールマイニングの部分問題の一つであAccidents の場合，CBP が RRP と比較して良い性能を示し

り，処理時間の大部分を占める．そのため，この問題を効率的ており，最大 7 倍の高速化を達成している．4. 2 節でも述べたに処理するために数多くのアルゴリズムが研究されてきている．

とおり，Accidents では SPMF の計算に非常に時間がかかるた

最も主要なアルゴリズムとして，Apriori [3] と FP-growth [8]め，各 GPU が並列に処理できる仕事量が多い．また，図 5(d)がある．

から，CBP の方が負荷分散できているため，良い性能向上率となった．

T25I10D500K では，CBP と RRP はほぼ同じ性能で最大また，これらのアルゴリズムの並列化の研究も数多くなされている．Agrawal ら [4] は Apriori をもとに，シェアード・ナッ
シング・アーキテクチャにおける三つの手法を提案した．この

他にも，1990 年代において，多くの研究が存在した [18]．これらの研究では主に分散メモリ環境を対象としている．
近年では，CPU のコア数の増加に伴い，マルチコアを活用する手法が見られる．Parthasarathy ら [14] は，共有メモリのマルチプロセッサにおいて，負荷分散やデータの局所性を考慮した Apriori の並列化を行なった．Liu ら [11] は，現代のマ
ルチコアプロセッサの活用を目指して，キャッシュを意識した

FP-growth の並列アルゴリズムについて研究した．
確率的頻出アイテム集合マイニング．上記の並列アルゴリズ
ムは従来のトランザクションデータベースが対象の場合は効率的に処理可能であるが，これらを不確実データベースにそのまま適用するのは実用的ではない．不確実データベースは近年非常に注目を集めており，様々な分野で多数の研究が行なわれている [1]．
不確実性を考慮した頻出アイテム集合マイニングの研究も盛んに行なわれており，多数の手法が存在する．Chui ら [6]は Apriori を不確実トランザクションデータベースへと適用した，U-Apriori を提案した．彼らは頻出アイテム集合の判定に支持度の期待値を用いていた．しかし，後に Bernecker ら [5]は，支持度の期待値では重要なアイテム集合を見逃す可能性があることを指摘した．代わりに，支持度の分布を考慮した手法を提案した．上記の研究は各アイテムに存在確率が付与されている，attribute-uncertainty model を対象としているが，Sun ら [16] は各トランザクションに存在確率が付与されている
tuple-uncertainty model を対象とした研究を行なった．また，Tong ら [17] は既存の代表的な手法を実装し，それらを公平な基準をもとに性能を評価した．

GPGPU．GPGPU は，高性能計算分野だけでなくデータ
ベース分野などにおいても，近年注目されている技術の一つである．例えば，He ら [9] は CPU-GPU のハイブリッドな手法による，関係演算の高速化の研究を行なった．また，GPGPUに関するサーベイ論文も存在する [13]．

GPU を用いた頻出アイテム集合マイニングの手法はいくつかの研究がある．Fang ら [7] は GPU ベースの手法と CPU-GPUのハイブリッドな手法の二つを提案した．また，Silvestri ら [15]は DCI アルゴリズム [12] の GPU による並列化を行なった.

6. ま と め
本稿では，先行研究で行なった単一 GPU による確率的頻出
アイテム集合マイニングの手法を発展させ，候補の分割にもとづく複数 GPU を用いた手法を提案した．提案手法 PP では，候補の prefix をもとに分割し，単一ノード上で複数 GPU による並列処理を行なった．さらに，負荷分散を考慮した二つの手法 RRP と CBP を提案した．また，RRP と CBP を発展させ，
複数 GPU を含むノードからなるクラスタを対象とした手法を開発した．評価実験により，CBP が最も良い性能となることを示した．さらに，クラスタを対象とした手法は，GPU が行なう仕事が十分にある場合に有効であることを示した．
謝辞

本研究の一部は科学研究費補助金基盤 A (24240015A)，「エクサスケール計算技術開拓による先端学際計算科学教育研

究拠点の充実」事業による．
文

献[1] C. C. Aggarwal and P. S. Yu, “A Survey of Uncertain Data
Algorithms and Applications,” IEEE Trans. Knowl. Data
Eng., vol. 21, pp. 609–623, May 2009.
[2] R. Agrawal, T. Imieliński, and A. Swami, “Mining Association Rules between Sets of Items in Large Databases,” Proc.
ACM SIGMOD Int’l Conf. Management of Data (SIGMOD), pp. 207–216, 1993.
[3] R. Agrawal and R. Srikant, “Fast Algorithms for Mining
Association Rules,” Proc. 20th Int’l Conf. Very Large Data
Bases (VLDB), pp. 487–499, 1994.
[4] R. Agrawal and J. C. Shafer, “Parallel Mining of Association Rules,” IEEE Trans. Knowl. Data Eng., vol. 8, pp.
962–969, Dec. 1996.
[5] T. Bernecker, H.-P. Kriegel, M. Renz, F. Verhein, andA. Zuefle, “Probabilistic Frequent Itemset Mining in Uncertain Databases,” Proc. 15th ACM SIGKDD Int’l Conf.
Knowledge Discovery and Data Mining (KDD), pp. 119–
128, 2009.
[6] C.-K. Chui, B. Kao, and E. Hung, “Mining Frequent
Itemsets from Uncertain Data,” Proc. 11th Pacific-Asia
Conf. Advances in Knowledge Discovery and Data Mining(PAKDD), pp. 47–58, 2007.
[7] W. Fang, M. Lu, X. Xiao, B. He, and Q. Luo, “Frequent
Itemset Mining on Graphics Processors,” Proc. Fifth Int’lWorkshop on Data Management on New Hardware (DaMoN), pp. 34–42, 2009.
[8] J. Han, J. Pei, and Y. Yin, “Mining Frequent Patterns
without Candidate Generation,” Proc. ACM SIGMOD Int’l
Conf. Management of Data (SIGMOD), pp. 1–12, 2000.
[9] B. He, M. Lu, K. Yang, R. Fang, N. K. Govindaraju,
Q. Luo, and P. V. Sander, “Relational Query Coprocessing on Graphics Processors,” ACM Trans. Database Syst.,
vol. 34, pp. 21:1–21:39, Dec. 2009.
[10] Y. Kozawa, T. Amagasa, and H. Kitagawa, “GPU Acceleration of Probabilistic Frequent Itemset Mining from Uncertain Databases,” Proc. 21st Int’l Conf. Information andKnowledge Management (CIKM), pp. 892–901, 2012.
[11] L. Liu, E. Li, Y. Zhang, and Z. Tang, “Optimization of Frequent Itemset Mining on Multiple-Core Processor,” Proc.
33rd Int’l Conf. Very Large Data Bases (VLDB), pp. 1275–
1285, 2007.
[12] S. Orlando, P. Palmerini, R. Perego, and F. Silvestri,“Adaptive and Resource-Aware Mining of Frequent Sets,”
Proc. IEEE Int’l Conf. Data Mining (ICDM), pp. 338–345,
2002.
[13] J. D. Owens, M. Houston, D. Luebke, S. Green, J. E. Stone,
and J. C. Phillips, “GPU Computing”, Proc. IEEE, vol. 95,
pp. 879–899, May 2008.
[14] S. Parthasarathy, M. J. Zaki, M. Ogihara, and W. Li, “Parallel Data Mining for Association Rules on Shared-Memory
Systems,” Knowl. Inf. Syst., vol. 3, pp. 1–29, Feb. 2001.
[15] C. Silvestri and S. Orlando, “gpuDCI: Exploiting GPUs in
Frequent Itemset Mining,” Proc. 20th Euromicro Int’l Conf.
Parallel, Distributed and Network-based Processing (PDP),
pp. 416–425, 2012.
[16] L. Sun, R. Cheng, D. W. Cheung, and J. Cheng, “Mining
Uncertain Data with Probabilistic Guarantees,” Proc. 16th
ACM SIGKDD Int’l Conf. Knowledge Discovery and Data
Mining (KDD), pp. 273–282, 2010.
[17] Y. Tong, L. Chen, Y. Cheng, and P. S. Yu, “Mining Frequent Itemsets over Uncertain Databases,” Proc. VLDB
Endow., vol. 5, no. 11, pp. 1650–1661, Jul. 2012.
[18] M. J. Zaki, “Parallel and Distributed Association Mining:
A Survey”, IEEE Concurrency, vol. 7, no. 4, pp. 14–25,
Oct. 1999.