クラスタを利用したバイオインフォデータマイニング
島本 真衣

指導教員：小口 正人

頻出パターンを抽出することで、   アルゴリズ
ムの問題点を改善したアルゴリズムである。
   は次のように構築される。 回目のデータ
ベーススキャンで各アイテムのサポート値を求め、頻出アイテムを抽出し、抽出された頻出アイテムをサポー
ト値により頻度が降順になるように並び替え これを  とする、空   のラベルを持つ木のルートを作成 これを  とする する。 回目のデータベース
スキャンで、  に従ってトランザクションから頻出アイテムを抽出し、ソートする。 が   の要素である子を持っていれば、その子のカウントを  増やし、持っていなければ、新しくカウント  を持つ子を作る。  の最後までこの操作を繰り返す。  の構築例を図  に示す。
    はこのように構築された    の性質を利用することにより、頻出パターンを発見していくアルゴリズムである。    の並列相関関係抽出のアルゴリズムは、本研究では   を元に行われた既存研究  で提案されたものを用いる。

はじめに近年、発達する情報化社会では、データの蓄積と運用が非常に重要になっており、情報システムにおいて処理されるデータ量が膨大になってきている。特にバイオインフォマティクス分野においては、将来的に役立つことが予想される貴重なデータが蓄積され続けており、それらを効率良く解析し利用することが求められている。これには既存のデータマイニング技術を応用できるが、データによっては属性値の種類が極めて多いなど、バイオ分野独特のデータ構造も考慮していく必要がある。
そこで本研究では、バイオデータを  クラスタシステム上でマイニングし、トランザクションデータを用いてマイニングを行った際とのシステムの振舞の違いを考察する。

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

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

Items

Frequent Items

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,prootc:4

  アルゴリズム

TID
100

item

frequency

c4

f4

a3

b3

m3

p3head図  

f:1

f:3

b:1

a:3

p:1

m:2

b:1

p:2

m:1b:1  の構造例バイオインフォデータ 
遺 伝 情 報 を コ ー ディン グ す る 生 体 物 質 を! "# $ !% % % と 呼 ぶ 。 ! はデオキシリボース（糖）とリン酸、塩基 アデニン
、グアニン &、シトシン 、チミン  から構成されていて、アデニン  はチミン  と、グアニン & はシトシン  とだけ結びつき、対を成す鎖は相補的な構造になっている。



図  で示すように、 ! 上で、それぞれの染色体が１塩基異なっている部位を '! '  !% 
 #( (一塩基多型 と呼ぶ。人によって薬の効き方や副作用の出方が違うのはこの '! が原因ではないかと考えられている。'! データは  )  プロジェクト * の  上で公開されている。

 アルゴリズム 年に   らによって提案されたもので、巨大なトランザクションデータベースから相関関係抽出に必要な情報をコンパクトに圧縮したデータ構造である   を利用している。候補パターンを生成せずに*図  '!

最後まで実行できるデータは限られていた。図 5 はアイテムの種類が + のときの   の実行結果の比較である。7 ＆ &2 のクラスタでは実行時間が約半分になっていることがわかる。 ・  共に 7＆ &2 のクラスタでの実行時間はほぼ半分程度の短縮であったが、アイテムの種類が ・最小サポート値が+ ％の   での実行時間は、 ( ＆ *,)2 のクラスタでは 6+［］だったのに対し、 ( ＆ &2のクラスタでは ［］と大幅に短縮された。

一塩基多型

実験内容と実験環境

本研究はトランザクション数 被験者数+ 人、アイテム種類数 塩基番号 約 + 個のデータを用いて実験を行う。まず公開されている '! データを相関関係抽出処理できるよう、出力方法、ハッシュ関数処理、ソーティング、フォーマット変換を行ったのち、変換したデータを  ノード分に分割し、   と    という  つの異なるアルゴリズムに基づいたプログラムを  クラスタ上で実行する。
実験には , 台の  を & $ -  で接続した  クラスタを用いる。各  は  . が /( 0+&1、メインメモリが *,)2、3' が4"050556   * である。

㪉㪈㪅㪍ᤨ㑆㪲㫊㪴㪈㪅㪋㪇㪅㪋㪇㪅㪉㪇㪈㪇䋦㩿㪋㪀㪈㪅㪌㪈㪈㪇䋦㩿㪋㪀㪉㪇䋦㩿㪐㪀㪊㪇䋦㩿㪈㪊㪀㪋㪇䋦㩿㪈㪏㪀㪌㪇䋦㩿㪉㪉㪀㪇㪅㪏㪇㪅㪍㪇㪅㪋㪇㪅㪌㪇㪅㪉㪇㪇㪌㪇㪈㪇㪇䉝䉟䊁䊛䈱⒳㘃

㪌㪇㪇㪌㪇

図 *   実行時間図 㪈㪇㪇䉝䉟䊁䊛䈱⒳㘃㪌㪇㪇 実行時間

㐳䈘㪉䉁䈪䈱㗫಴䉝䉟䊁䊛✚ᢙ㪉㪌㪇㪇㪇㪉㪇㪇㪇㪇ᦨዊ䉰䊘䊷䊃ഀว(ᢙ)
㪈㪇䋦㩿㪋㪀㪉㪇䋦㩿㪐㪀㪊㪇䋦㩿㪈㪊㪀㪋㪇䋦㩿㪈㪏㪀㪌㪇䋦㩿㪉㪉㪀㪈㪌㪇㪇㪇㪈㪇㪇㪇㪇㪌㪇㪇㪇㪇㪌㪇㪈㪇㪇㪌㪇㪇䉝䉟䊁䊛䈱⒳㘃

㪌㪇䋦㩿㪉㪉㪀

まとめと今後の課題

ハッシュ関数によって一定範囲に数値を出力する等、データの出力方法や   と  のプログラムの修正を行うことで、アイテムが  種類のデータまで実行することが出来た。しかしアイテムの種類が を超えると、  では、頻出アイテムの数が膨大になり、メモリ上に確保したデータ領域の容量を超え実行が途中で止まってしまう。バイオインフォデータは通常のトランザクションデータと比較してアイテム種類数が極めて多いなどの特徴を持ち、マイニング処理には工夫が必要であることがわかった。
そこで一台あたりのメインメモリが &2 の  クラスタ上でも同じデータを用いて実行したところ、実行時間が短縮されたが、最後まで実行できるデータのアイテムの数と最小サポート値には変化がなかった。
このことから実行が完了しない原因は全メモリ容量だ
けでなく、プログラム中におけるデータ領域の確保の仕方にもあることがわかった。今後は実行が止まってしまうプログラムの箇所を特定し、修正を行う。

ᦨዊ䉰䊘䊷䊃ഀว(ᢙ)

㪈ታⴕᤨ㑆㪲㫊㪴ታⴕᤨ㑆㪲㫊㪴㪈㪇䋦㩿㪋㪀㪉㪇䋦㩿㪐㪀㪊㪇䋦㩿㪈㪊㪀㪋㪇䋦㩿㪈㪏㪀㪌㪇䋦㩿㪉㪉㪀㪉㪇䋦㩿㪐㪀㪊㪇䋦㩿㪈㪊㪀 㪋㪇䋦㩿㪈㪏㪀ᦨዊ䉰䊘䊷䊃୯䋨ᢙ䋩

図 5 各クラスタでの実行結果の比較㪈㪅㪉ᦨዊ䉰䊘䊷䊃ഀว(ᢙ)

㪈㪇㪅㪍㪈㪅㪋

㪉㪈㪅㪉㪇㪅㪏 実行結果と考察㪉㪅㪌㪧㪼㫅㫋㫀㫌㫄㪋㩷㩽㩷㪊㪏㪋㪤㪙䉪䊤䉴䉺㪯㪼㫆㫅㩷㩽㩷㪋㪞㪙㩷䉪䊤䉴䉺㪈㪅㪏㪈㪇㪇㪇謝辞図 + 長さ  までの頻出アイテム総数

本研究を進めるにあたり、データ変換プログラムの提供および、大変有用なアドバイスを頂いた本学准教授の瀬々先生に深く感謝いたします。

データに手を加えアイテムの種類を変化させた時の実行時間を図 * と図  に、その際の長さ  の頻出アイテム総数を図 + に示す。
図 *、 からもわかるように  ・  のアルゴリ
ズム共にアイテムの種類が + までは問題なく実行できた。アイテムの種類を  にすると、  は実行できず、  も図 + のように頻出アイテムの数が急激に多くなってしまい、最小サポート値を高めに設定しないと、実行が途中で止まってしまう。また頻出アイテム数が多くなることから、候補アイテムの数も膨大になり、最小サポート値を高く設定しても実行時間が非常に長くなってしまうことがわかった。
そこで  . が / 7 *0,&1、メインメモリが&2、3' が 4"050++3'0+ の  クラス
タ上で同じデータを用いて実行したところ、頻出アイテム数が多い場合でも短い時間で実行が終了したが、参考文献

 小口正人、喜連川優8) 結合  クラスタにおける動的リモートメモリ利用方式を用いた並列データマイニングの実行89 電子情報通信学会論文
誌9: 0;, /9 !09 0**5*9  年  月

 /< (  )   = 
 8 
 %  $   >   )   %  89 -7*9'($ *プロジェクト9*  ) ??
0 ( 0 ?
 島本真衣、小口正人8  クラスタを利用したバ
イオインフォデータマイニング89 第 6 回情報処
理学会全国大会9@=+9, 年 * 月発表予定*