 統合型  クラスタにおける並列相関関係抽出の実行

原 明日香

指導教員：小口 正人  アルゴリズム

はじめに ! 年に  " らによって提案されたもので、発見された頻出アイテムセットから候補アイテムセットを生成し、繰り返し数え上げを行っていくアルゴリズムである。 回目のデータベーススキャンで長さ  の頻出  アイテムセットを抽出し、それらを元に長さ の候補  アイテムセットを生成する。 回目のデータベーススキャンで候補  アイテムセットから頻出  アイテムセットを抽出する。これを候補アイテムセットが生成されなくなるまで繰り返していくことで、頻出パターンをすべて発見していくアルゴリズムである。
 アルゴリズムには、候補アイテムセットを格納するために大容量のメモリが必要となる、何度も繰り返しデータベースをスキャンする可能性があるといった問題点がある。
 をベースにした並列相関関係抽出のアルゴリズムはいくつか提案されているが、本研究ではハッシュ関数を使用して  を並列化する # #$    を用いる。

近年、発達する情報化社会では、データの蓄積と運用が非常に重要になってきている。また、情報システムにおいて処理されるデータ量が膨大になってきている。ユーザにとって重要なデータが蓄積されているにも関わらず、使いこなせていない場合が少なくない。
本研究では膨大なデータから有益な規則や関係を抽出する相関関係抽出において代表的な  アルゴアルゴリズムを利用し、両者の比リズムと 較を行う。パラメータ条件によっては相関関係抽出における計算量、データ処理量は非常に多くなるため、並列化が不可欠となる。そこで分散メモリ型並列計算機である  クラスタを用いるが、その際にバックエンドのストレージネットワークを統合した   統合型  クラスタを用いて実行し、性能評価を行う。

 統合型  クラスタ

各ノードが独立して動作する 、メモリ、二次記憶を保有し、ノードが必要に応じてネットワークを介し互いに通信することで全体として並列分散処理を実現する分散メモリ型並列計算機の各ノードに汎用のパーソナルコンピュータとネットワークを用いたものを  クラスタ 図  という。 ノード間通信 は  、ストレージアクセス は  でネットワーク接続されている。
そこで図  のように   と  のネッ
トワークを同じ  ネットワークに統合した  
統合型  クラスタの実現を考えた。ネットワークを統合することでネットワーク構築コストと管理コストの削減が可能となる。

%%% 年に # らによって提案された & もので、巨大なトランザクションデータベースから相関関係抽出に必要な情報をコンパクトに圧縮したデータ構造である   を利用している。候補パターンを生成せずに頻出パターンを抽出することで、  アルゴリズムの問題点を改善したアルゴリズムである。
  は次のように構築される。 回目のデータベーススキャンで、各アイテムのサポート値を求め、頻出アイテムを抽出する。抽出された頻出アイテムをサポート値により、頻度が降順になるように並び替え これを "$ とする、空 '"" のラベルを持つ木のルートを作成 これを ( とする する。 回目のデータベー
ススキャンで、"$ に従ってトランザクションから頻出アイテムを抽出し、ソートする。( が "$ の要素である子を持っていれば、その子のカウントを  増やし、持っていなければ、新しくカウント  を持つ子を作る。"$ の最後までこの操作を繰り返す。 の構築例を図 & に示す。

ClientClient
ノート

LAN

Front-end

ServerLAN&IP-SAN
LAN&IP
-SAN
ストレージ
アクセス

ノート

ストレージ
アクセス

SAN
SAN

Back-end

Initiator
TargetStorage

図  通常の  クラスタ

図   アルゴリズム

  統合型 クラスタ

相関関係抽出とその並列化
相関関係抽出では、巨大なデータから有益な規則性や関係を抽出するためにあるパターンが現れる頻度 サ
ポート値 を調べる。その頻度が多ければ、そのパターンから得られる関係は有意義なデータとなり、販売戦略などに活用出来る。
相関関係抽出で扱うデータはしばしば巨大であるため、データベースを分散し計算処理を並列化して、多数台のコンピュータをネットワークで接続した  ク
ラスタなどの環境でマイニング処理を実行する並列相関関係抽出の研究が行われている 。以下に相関関係抽出の代表的な  つのアルゴリズムの概要を説明し、本研究で用いる並列化アルゴリズムを紹介する。

TIDItems

Frequent Items

100

f,a,c,d,g,i,m,pc,f,a,m,p200

a,b,c,f,l,m,oc,f,a,b,m

300

b,f,h,j,o

f,b

400

b,c,k,s,pc,b,p500

a,f,c,e,l,p,m,nc,f,a,m,proot
c:4

item

frequency

c4

f4

a3

b3

m3

p3

head

f:1

f:3

b:1

a:3

p:1

m:2

b:1

p:2

m:1

図 &   の構造例)*b:1



は構築された   の性質を利用することにより、頻出パターンを発見していくアルゴリズの並列相関関係抽出のアルゴリムである。
ズムは、本研究では # を元に行われた既存研究 !
で提案された """+  を用いる。

%クラスタにおけるPFPの%クラスタにおけるHPAの

35

1200

30

1000

25
local SCSIiSCSI iSCSI' 

600
400

 [s]

 [s]

800

local SCSIiSCSI iSCSI' 

20
15
10200

50010K

20K

40K

80K

160K

10K

トランザクション$

20K

40K

80K

160K

トランザクション$

実験内容と実験環境# アルゴリズムと  アルゴリズムの並列化プ
ログラムを、ローカルデバイス   ディスク を用いた  クラスタ、   統合型  クラスタ、バックエンド   を用いた非統合型  クラスタで実行し、そのときの実行時間をそれぞれ測定する。実験には ! 台の  を ,- .  で接続した  クラスタを用いる。   を用いる場合には、  ターゲット用の  がもう ! 台接続されている。各  は
 が  '/! 0*,#+、メインメモリが &1!2、
3 が '4 050 55)  & である。

図 * # アルゴリズム 図 5  アルゴリズムの実行結果

まとめと今後の課題 の並列化アルゴリズム # と  の並列化アルゴリズム  を、ローカルデバイスを用いた  クラスタ、   統合型  クラスタ、バックエンド   を用いた非統合型  クラスタにおいて実行し、実行時間を比較した。# アルゴリズ
ムと  アルゴリズムの比較では、今回用いたトランザクションデータが小規模であったということもあり、今回の実験では  アルゴリズムの方が格段に速いという結果になった。
ただし、トランザクションデータ数を多くすると、  が大きくなってしまい  アルゴリズムは今回の実験環境ではうまく動作しなかったが、その場合も # アルゴリズムはきちんと動作していた。このことからデータ量と実行環境に応じて使用するアルゴリズムを使い分ける必要があると考えられる。
ローカルデバイスを用いた  クラスタ、   統合型  クラスタ、バックエンド   を用いた非統合型  クラスタの比較では、どちらのアルゴリズムにおいても、& つの  クラスタにおける実行結果はほとんど変わらなかった。同じ性能を示すなら、コストが安く、ネットワークの管理のしやすい  
統合型  クラスタが有効であると考えられる。

実行結果と考察

アイテム数を %%% とし、トランザクション数が %6、%6、!%6、1%6、5%6 のトランザクションデータを用い、最小サポート値を %0) ％としたときの実行時間
を、ローカルデバイスを用いた  クラスタ、  統合型  クラスタ、バックエンド   を用いた非統合型  クラスタ上で測定した。今回用いた プログラムの性質により、比較的小規模なトランザクションデータを用いて実験を行った。
図 ! に同じ大きさのトランザクションデータにおける つのアルゴリズムの実行時間を示す。明らかに アルゴリズムの方が速いことがわかる。これは、#
アルゴリズムが頻出アイテムセットから候補アイテムセットを作るという動作を、データの大きさに関係なく何度も繰り返し行っているためである。反対に アルゴリズムはデータの大きさによって、  の大きさが変わるため、データ量が小さい今回の実験では、良い結果が出たと考えられる。
図 * に # アルゴリズム、図 5 に  アルゴリズムのそれぞれのクラスタにおける実行時間を示す。
どのクラスタにおいても実行時間はほとんど変わらなかった。   統合型  クラスタは、バックエンドとフロントエンドで同じネットワークを使用するため性能が落ちる可能性が予想されたが、本実験で性能は変わらないということが分かった。
iSCSI

参考文献

 福田剛志、森本康彦、徳山剛志7データマイニング78 共立出版
 小口正人、喜連川優7 (2 結合  クラスタにおける動的リモートメモリ利用方式を用いた並列データマイニングの実行78 電子情報通信学会論文
誌89"0:1!; 8 0 8 0&&5&! 8 %% 年 月

& :  #8 : 8  <  <72
='  $  '   ,
78 2  ,23;%%%8082>%%%!  /'  2$' 6$'  7($ ' ' -$ """ ='  2   "'$ 78 ;.? %%&80*&)
*& 8 /- %%&* 原明日香、神坂紀久子、小口正人7   統合型  クラスタにおける相関関係抽出の実行78
情報処理学会第 5 回全国大会8**8%%) 年 & 月

PCクラスタにおける2つのアルゴリズムの

1200

1000

 [s]

800

HPA
PFP

600

400

200

010K

20K

40K

80Kの実行結果

160K

トランザクション$

図 ! トランザクションデータごとの  つのアルゴリ

発表予定

ズムの実行時間)5