論 文
頻出パタンマイニングのためのゼロサプレス型

 の変数順序付け

方法とその評価岩崎玄弥Ý 真一Ý 

湊

ツォイクマントーマスÝ         

            

あらまし 近年，ゼロサプレス型二分決定グラフ         を用いたデータベースの効果的な解析手法が提案されている．二分決定グラフ  は大規模論理関数データの表現方法として広く用いられている．今回はトランザクションデータベースに関して，大規模なアイテムの組合
せ集合を処理するのに適した  を用いる． のデータ構造は変数の順序に大きく影響を受ける．我々は， を生成する前処理としてアイテム変数の順序付けを行うことで，生成される  のサイズを小さくする研究を行ってきた．本稿では， 設計の分野で開発された「動的重み付け法」をトランザクションデー
タベースの変数順序付けに応用する手法を提案する．動的重み付け法は，トランザクションデータベースの構造情報を用いることで，よりよい順序付けを行う手法である．我々は，様々なトランザクションデータベースに対してこの手法を適用して  を生成する実験を行うことで，この手法の有効性を確認することができた．さらに，動的重み付けを行うプログラムを改良し高速化を行った．
キーワード



データマイニング， ， 頻出パタン，二分決定グラフ，変数順序付けいる．'  は大規模な組合せ集合データを非明示的はじめにに列挙し，頻出パタンの発見から解析に至る多様な演

近年，大規模記憶装置の発展などによって，大規模算を効率よく実行することができると期待されている．

なデータベースの中から有用な規則を発見するデータ'  のグラフの大きさは，同じ例題に対しても変マイニングの研究が盛んになっている．頻出パタンマ

数の順序によって大きく影響を受けることが知られてイニング 

いる．一般的な   は，最も基本的 の変数順序付け方法についてはなデータマイニング問題であり，    等  によ過去に多くの研究  + , があるが，'  を用いる   アルゴリズムの研究に始まり，現在までにたデータベース解析処理におけるアイテム変数の順序

様々なアルゴリズムが提案されている  ．

付けに関しては，まだ良い方法は知られていない．本

我々はこれまでに，  の分野で大規模論稿では，データベースの特徴に基づいて順序付けを行

理関数データの表現法として広く用いられている二う新しい発見的手法を提案し，その効果を示す．以下

分決定グラフ!

 " # $  

その中でも「ゼロサプレス型$$$)

 %$ &，

」 ' ! '( * と呼ばれるデータ構造を用いて，の本文では，& 章で '  を用いたデータベース表
現について述べ，- 章では，データベース表現における '  の変数順序付けについて述べる．そして，

トランザクションデータベースにおける頻出パタンを章で本稿で提案する手法に関して行った実験の結果と効率よく生成する手法  & に関する研究を進めて考察を述べ，最後に  章で簡単なまとめを述べる．

Ý 北海道大学大学院情報科学研究科

            
                          
電子情報通信学会論文誌

   によるデータベース表現
ここでは以下に示すようなデータベースを考える．
まず，を空でない集合とする．

ムと呼ぶ．以下に示す図のように，    年  月の要素をアイテ.

 と電子情報通信学会論文誌   

 

 
























（






 


  !）図  二分決定木と %&'%
   %" (  "  & % "# '%

    
図データベース例題とタプル頻度表

    "#   !

タプル頻度表からは頻出タプルを，パタン頻度表か


 
" # #  "）              




（

図

 

らは頻出パタンを用意に見つけることができるので，頻度表は非常に重要である．我々はパタン頻度表をタ      !）プル頻度表を処理することで構成する．詳細は後ほど記述する．典型的なデータマイニング問題は，あるし$  "  













（$  "   !）きい値以上出現する頻出パタンを全て見つけるという

タプル頻度表とパタン頻度表

大きいものである場合が多いので，最も重要な問題は



この処理をどのようにして効率よく行うかである．

"#

問題である．例えば，図  の頻度表としきい値として/ が与えられた場合，データマイニングを行った結果はパタン

 を返すことになる．またしきい値を , とす，，， を返す．このような問題をると，パタン

扱う場合，現実的にはデータベースのサイズは非常に "   !

我々は，この問題を解決するために 0する．この集合から得られる全ての組合せの集合は
のべき集合





 である．部分集合  
.

 は組合

せ集合と呼ばれる．この組合せ集合の要素は，例えば のようにアイテムの集合である．記述を簡略化するために，  を  と書き，組合せ集合の要素 )(

%(01( )#$ # #  / と呼ばれるプログ

ラムを用いる．0 では，入力としてデータベースとしきい値を受け取ると，タプル頻度表を表す ' を内部で構築する．そして，我々の研究グループで開発した ' ( 2 法 & を用いてパタン頻度表

をタプルと呼ぶ．トランザクションデータベースはタを生成する．' ( 2 法では，与えられたしき

プルのリストである．

い値以上のパタン全てを表す '  をタプル頻度表

トランザクションデータベースから有用な規則を見から構築することができる．この二つの過程では同じつけるために，二種類の頻度表を考える．一つ目はタ

変数の順序付けが用いられており，この順序付けが生

プル頻度表である．タプル頻度表は二つの行からなっ成される '  のサイズに非常に大きな影響を与えており，最初の行にはデータベース中に存在する全てる（3& を参照）．

のタプルが入り，もう一つの行には各々のタプルの出
現頻度が入っている．図  はタプル頻度表の例であり，出現頻度の高い順に並べられている．
二つ目の頻度表はパタン頻度表と呼ばれている．パ   と 
これより，本研究で用いる二分決定グラフ， と '  について述べる．  & は，図 - に示すような論理関数のグラフによる表現である．図 - は，全ての部分集合が入っており，もう一つの行にはアイ  .    を表す  の例である．図 では  という順序付けを用いたが，順序付けが与テム集合のデータベース中の出現頻度が入っている．

えられれば， "  のアルゴリズムを用いてどのよ

タン頻度表の最初の行には，タプルとそれに含まれる

例えば，図 & ではパタンて，パタン と ， が , 回出現してい が / 回出現していることがわかる．

うな論理関数に対しても

 を構築することができる．現実の問題では非常に多くの論理関数を扱うこと

論文／頻出パタンマイニングのためのゼロサプレス型  の変数順序付け方法とその評価になるが，このアルゴリズムは非常に効果的であり，生成された は二分決定木に比べて効率のよい表  ¾ ½ ¼
            
¼ )    &
½ )   & ¾ )  

現となっている．
一般に，論理関数のそれぞれの変数に / の値を代入した結果を，二分岐の枝（/(枝4(枝）で場合分けし得られる論理関数の値を，& 値の定数節点（/(終端節点4(終端節点）で表現すると，図 - のような二分木状のグラフになる．このとき，場合分けする変数の順序を固定し，冗長な節点の削除と等価な節点を共有す

図  '% の表現   *るという & つの縮約規則を可能な限り適用することに進ベクトルによるタプル出現頻度の  " " +  !

より，「既約」な形が一意に得られることが知られてい の間においても，変としかできないため，そのままでは組合せの出現回数

数順序を固定すればグラフを共有することができる．

を表すことができない．これの解決法として，本稿で は，多くの実用的な論理関数を比較的少ないは整数値を & 進数に分解する方法を用いる． 個のる．複数の論理関数を表す

記憶量で一意に表現することができる．また，& つの' 

 ! !  をベクトル状に並べると，

 を入力とし，それらの二項論理演算の結果を表

最大 &   までの重みを表現することができる．す を直接生成するアルゴリズムが考案されてい

なわち，出現回数を二進数で符号化し，最下位ビット

する．このアルゴリズムはハッシュテーブルを巧みに用が  になる組合せ集合をいることで，データが計算機の主記憶の範囲に収まる

ような組合せ集合を限りは，その記憶量にほぼ比例する時間内で論理演算ることにより，図  のように，各項の重みを非明示的を効率よく実行できる．

に表すことができる．図  では，アイテムの集合が は元々は論理関数を表現するために考案され 変数の論理空間で組合せ集合を表すこともできる．ここで  は集合の要素数であり，組合せ集合とは，「 個のアイテムから任意たものだが，これを用いて個を選ぶ組合せ」を要素とする集合である．このよう.

，次のビットが  になる! ，という形で! まで並べ， ! . ， " .  のよ

うに符号化されおり，それぞれの桁は単純な ' 
によって表されている．また，この三つの '  は互いの部分グラフを共有している．
0プログラムを用いることで，トランザクショに，  を用いることで組合せ集合を現すことがでンデータベースにおいて，タプル頻度表を効率的に生きるが，'  を用いることでより効率よく組合せ集

成することができるが，しかしながら，一般に合を表すことができる．

個のアイテムからなるタプルは & 個のパタンを含んでい類似する組合せが多ければ，部分的に共通する組合るので，パタン頻度表はタプル頻度表よりもはるかにせがグラフ上で共有されて，記憶量や計算時間が大幅大きなものになる．しかし，'  を用いる場合，多に削減される場合がある．さらに，組合せ集合に特化

数の類似するパタンをグラフで共有してコンパクトにした '  * を用いると，より簡潔な表現が得られ，表現できるので，ある程度の規模までパタン頻度表を

一層効率よく扱うことができる．'  では，冗長現実的に生成できる可能性がある．このタプル頻度表

な節点を削除する簡約化規則が通常の とは異なから頻出パタンを表すパタン頻度表を生成する処理は，る．'  では (枝が /(終端節点を直接指している' ( 2 法を用いて行われる &．一旦パタン

節点を取り除く，という規則になっている．これによ

頻度表の生成に成功すれば，任意の頻度に対応する頻り，'  では図 - のように，組合せ集合に一度も選

出パタン集合をすべて同時に保持しているのと同等でばれることのないアイテムに関する節点が自動的に削あるため，非常に強力なデータ表現であり，その後は除されることになり，  よりも効率よく組合せ集

様々なデータベース解析処理を '  処理系の演算合を表現・操作することができる．

により効率よく解くことが可能となる．

 を用いた頻度表の表現  

 法による頻出パタン生成

ここで，'  を用いてどのように頻度表を表現

パタン頻度表は生成できれば強力であるが，中規模するのかを説明する．'  は組合せ集合を表すこ

以上のベンチマーク例題に対しては，'  が巨大に

電子情報通信学会論文誌   なり過ぎて，現実的な記憶量では表現することができ

変数の順序付けは，        となる．

ない．しかし，ある一定の頻度以上の頻出パタン集合

我々がこれまでに提案した '  によるデータマだけを抽出するだけであれば，最小頻度のしきい値

イニングの実験は，ほとんどがこの順序付けを用いてを大きくしていけばパタン数が単調減少するので，適いる．後出し上位順は，データベースの読み込みと同を与えれば '  を構築することが可時に行うことができるので，計算コストを無視するこ能となる．そこで我々の研究グループでは，'  のとができ，経験的には比較的良い順序を得られることベクトルで表現されたタプル頻度表から，パタン頻度が多い．しかし，この順序付けでは，同じ内容のデー

表を経由せずに，直接，頻出パタン集合を表す ' 

タベースでも，処理するレコードの順番によって変数を生成するアルゴリズム「' ( 2 法」を開発の順序が大きく変わるため，結果が不安定で，例題に度に大きいした &．これにより，中規模以上のベンチマーク例

よっては非常に悪い順序付けとなる場合がある．そこ

題でも頻出パタン集合を表す '  を生成できるよ

で我々は，与えられたデータベース例題の特徴に基づうになったが，それでもやはり '  が小さければいて，データベース中のアイテムの順序に依存せず，計算時間が少なくてすむため，良い変数順序付けを求より良い変数順序を安定的に求めるための発見的手法

めることは依然として重要な研究課題である．



データベース表現における  の
変数順序付け前述のように，'  を用いることで頻度表や頻出
パタン集合をコンパクトに表現できる可能性があるが，を提案する．この手法は従来の

 に対して用いられている手法を，データベース解析処理向けに改良したものである．よって，まず従来の に対する手法に関して説明する．

  論理回路における  の動的重み付け法
通常の の変数順序付け方法については，これ

データベースが大規模になると，'  を生成するこまでに  論理設計の分野で多くの研究がある．一とが困難になる．これを改善する手法として，本稿で般的に，最適な順序付けを求めることは 5

は，「アイテム変数の順序付け」を考える．すでに述べることが知られている - が，現実的な時間で比較的完全であたように，生成される '  のサイズは変数の順序

よい順序を求める発見的手法がいくつか提案  + ,

に大きな影響を受ける．よって，我々の目的は ' 

されている．ここでは，論理回路における  の「動のサイズができるだけ最小に近くなる順序付けを見つ的重み付け法」, を紹介する．この手法は，論理回路けることである．

における'  の性質上，最悪な順序付けを用いても節点ている．

数はパタンを羅列したときの総文字数を超えることが通常のない  ため，総文字数が少なければどのような順序付けでも，'  のサイズが膨らむことはない．この の入力の順序付けに関して効果を上げ
 においては，グラフの大きさに影響する要素として，次の & つの性質が知られている ．


局所計算性のある入力の組は，なるべく近い順

ことから，アイテム変数の順序付けにより指数関数的序にする．これにより，多くのサブグラフが共有できな効果が表れるためには，最悪な場合が指数関数的なるという傾向がある．例えば & 進数の加算器の論理回

節点数になる必要があるので，データ中にはパタンを路では，対応するビット同士の変数を並べて配置する羅列したときの総文字数が非常に多くなければならなと良いことが知られている．

いということがいえる．一般的に，パタンはアイテム&

出力を制御する力の強い入力は上位に配置する．

数の指数個あるので，アイテム変数の順序付けにより，

例えば，データセレクタの論理回路では，データ入力

大きな '  の簡単化効果が得られると期待できる．

を上位に並べた場合は制御入力を上位に並べた場合に本稿で使用した 0 プログラムでは，データベー

比べ，  のサイズが指数的に増大してしまう．こスに含まれるアイテムをアイテム変数として最初に宣れは，制御入力の値を先に決定すると，多くのデータ言する．宣言されなかった変数は，その変数が算術式中入力を無視できるという性質があるためと考えられる．

で使用されたときに，その場で新たに宣言したものとこれら & つの性質を満たすような順序付けを行えばして，最上位に追加される．
（以下では，この変数順序    

よいのであるが，実際には，& つの性質が同時に現れを「後出し上位順」と呼ぶ．
）例えば，て，互いに相反する順序付けを要求する場合があり，というリストを持つデータベースが与えられた場合，これを両立させて最適な順序を求めるのは難しい．ま論文／頻出パタンマイニングのためのゼロサプレス型  の変数順序付け方法とその評価

   , "#図  論理回路における動的重み付け法

    (" ! -   . "! " / # + 0  1

た，どんな順序でもそれほど変化の見られない回路もしたと仮定して，改めて重み付けを行う．このようにあり，その場合には，順序付けを工夫してもあまり効

動的に重み付けを行うことにより，前節  の局所計果が得られない．
以上の考察に基づいて，回路の結線情報から変数の順序付けを行う発見的手法がいくつか知られているが，算性も反映することができる．その様子を図  6 に示す．以下，これを動的重み付け法と呼ぶ．
動的重み付け法では，順序付けに必要な時間は，入その中の  つとして「動的重み付け法」が提案されて

力数 ，回路規模を % として，いる ,．この方法は，論理回路の出力の論理関数を付けによって，生成される で表す場合に，回路の結線情報から関数の性質を予想し，最適に近い順序を求めるものである．
動的重み付け法では，まず前述の & の性質を満たすため，制御性の高い入力を見つける．これは，以下のような傾向を持つ．

ファンアウト数が多い（出力に至るパスが多い）．

  である．順序

 のサイズに指数関数的な違いが見られるので，順序付けにこの程度の時間がかかっても十分有効である．

ト ラ ン ザ ク ション デ ー タ ベ ー ス に お け る の順序付けへの応用

ここまで論理回路における の順序付け法に関して説明してきたが，本稿では，これをトランザク

出力までの段数が少ない．

ションデータベースにおける '  の順序付けに応出力へ至るパス上のゲートのファンイン数が少

用する．

ない．
この傾向を評価するために，次に示すような簡単な重み付け法を用いる．

まず初めにデータベースの構造を表すグラフを作る．
各々のアイテムを表すノードを生成し，次に各々のタプルを表すノードを生成する．最後にデータベース全 を作る．さらに，ノード  から

 出力線の重みを  とする．

体を表すノード& 出力から入力に向かって重みを伝達させる．& 入

全てのタプルに対して枝を引き，各々のタプルから，力以上のゲートでは，出力線の重みをファンイン数でそのタプルに含まれないアイテムに対して枝を引く．

均等に分けて入力線に伝える．

論理回路においては，出力から重みを伝えていきゲー- ファンアウトがある信号線で，複数のゲートから重みが伝わるときにはそれらを伝える．
以上の手順で重み付けをした例を図   に示す．この図では，出力に与えられた重みが三つのファンインに均等に分けられたことが示されている．この重みがトの入力数に応じて重みを分配したが，本手法では，
 データベース全体の重みを  として，これをタプルの数で割った値をそれぞれのタプルの重みとして与える．
& 各々のタプルにおいてそのタプルに含まれない

最大となった入力が最も出力を制御しやすいとみなし，アイテムに対して，タプルに与えられた重みをその含

その入力に最上位の変数を割り当てる．

まれないアイテムの数で割った値を重みとして伝える．

次に，最上位の変数を決定した後，その下のサブグ
ラフを小さくすることを考える．このとき，すでに決- 複数のタプルから重みが伝わるときにはそれらを加える．の手順で重み付けを行う．

定された入力は / か  に固定されてしまっていると考この & の手順において，タプルに含まれるアイテ

えれば，その近くの信号線は，制御性が増大している

ムではなく，タプルに含まれないアイテムに重みを伝はずである．そこで，すでに決定された信号線を切断

えて行くところが，従来の論理回路での動的重み付け電子情報通信学会論文誌       , "#図  トランザクションデータベースにおける動的重み付け法

    -. / # +  " "    

法とは大きく異なる点である．タプルに含まれるパタきた手法では，トランザクションデータに対する順序ンを抽出する場合に，タプルに含まれるアイテムはパ付け法の説明の & に示されているように，各々のタタンを形成するアイテムの組合せに含まれるときと含プルに含まれないアイテムに対して重みを分配してきまれないときがあるが，タプルに含まれないアイテム

た．しかし，扱うデータベースは疎である場合が多い

は当然そのタプルが含むパタンの要素とはなりえず，

ので，このままでは非常に多くのアイテムに対して重このことから，タプルに含まれないアイテムは含まれみを分配するという処理が必要になってしまう．これるアイテムより出力に与える影響が大きいと考えられを解消するために，我々はまず全てのアイテムにるので，このように重み付けを行う．

に与える重みと同じ  を与える．次に，各々のタプル

このようにして重み付けをした例を図 +  に示す．

に含まれるアイテムに関して，タプルに与えられた重この重みが最大となったアイテムを '  のサイズ

みをタプルに含まれないアイテムの数で割った重みをに特に影響を与えるものとして，変数の最上位に割りそれぞれのアイテムから引くという処理を行う．この当てる．与えられた重みが同じものが複数あった場合

処理では，タプルに含まれないアイテムの重みが相対は，最も出現が早かったアイテムを選ぶ．

的に増加するので，以前の手法と同じ順序付けが得ら

次に，最上位の変数を決定した後の処理について述れる．また，タプルに含まれるアイテムに重みを伝え

 のるという処理に変更することによって，重みを伝える

場合と同様に取り除き，もしアイテムの順序付けが決アイテムの数が格段に減ることが予想される．例えまったことで，タプルからアイテムに伸びる線の全て

ば，アイテムの平均出現個数が全アイテム数に対してが無くなってしまったタプルがあれば，そのタプルは

7とすると約 // 倍高速になる．改良後の計算時間

以降の重み付けの際には存在しないものとして扱う．

は，アイテム数を ，データベースのサイズを

つまり，存在するタプルには，総タプル数から存在しると，なくなったタプルの数を引いた数で重み  を割った値て変数の順序付けを行った処理時間の比較についてはを重みとして与えることになる．これを図 + 6 に示

後述する．

べる．順序が決定したアイテムに関する線はす．この順序が決定したアイテムに関する線を取り除くという処理によって，取り除かれたアイテムの重みがそのアイテムと関係の深いアイテムに分配されることになるので，局所計算性を反映することができる．
以上の操作を繰り返すことでアイテム変数の順序付けを行う．

  変数順序付けプログラムの高速化




 とす
  となる．この手法と以前の手法を用い実験と考察

本実験において使用した  は  %，-3/89:，;  < *3-，主記憶 &6" で '  の最大節点数は /// 万個とした．はじめに，人工的な例題
における '  の順序付け法の効果に関して行った実験の結果を示し，次に実際のベンチマーク例題におさらに我々は，変数順序付けに要する計算時間を短ける '  の動的重み付け法に関して実験を行った

縮するため，以下の改良を行った．これまで説明して結果を示す．今回の実験で用いた順序付けは，動的重論文／頻出パタンマイニングのためのゼロサプレス型  の変数順序付け方法とその評価
人工的な例題における 2,3$ の処理時間と '%の節点数

み付け法，出現頻度の高いアイテムを上位に並べた

表「高頻度上位順」，逆に出現頻度の低いアイテムを上位 に並べた「低頻度上位順」と，アイテムの最初の出現が遅いものから上位に並べた「後出し上位順」の  つ -. / # 0    9
 3# " 5
! 
5 ! 






































 

&



& 

 

&

 

&  & 

 

& &&  & / !( : ;<である．

  人工的な例題におけるアイテム変数の順序付
け法の評価
まず，'  のアイテム変数の順序付け法に関して，人工的な例題における動的重み付け法の効果を調べる．今回は以下に示すような人工的に生成したデー
タベースを用いて実験を行う．

" # $    
! # $    
! " $    333

"  # $    
!  # $    
!  " $    
3
3
3

3
3
3

! " #     ! ! " #     !
このデータは，! " ! "  という形から  と  .   を取り除いたものを各レコードとしている．また，このデータベースに関して動的重み付け法を用いた場合のアイテム変数の順序付けと，低頻度上位順に並べた順序付けを以下に示す．

""# #$ $      !!
"#$     " #$     !!

・ 動的重み付け法!
・ 低頻度上位順!

 1!  " ! + 2,3$ 1  4
 "#  '% ,5 + /  ! % "! 6 78 ! 

く影響したと考えられる．
このように，アイテムの出現頻度だけでは効果的な順序付けができない場合においても，動的重み付け法
では効果的な順序付けができることが示された．



動的重み付け法の効果

今回は低頻度上位順を用いたが，高頻度上位順や後次に，実際のベンチマーク例題における '  の出し上位順でも低頻度上位順とほぼ同じ順序付けと動的重み付け法による順序付けの効果に関して行った

なった．

実験の結果を示す．実験は，動的重み付け法を用いて以上の場合において，タプル頻度表から頻出パタンを抽出する実験を行った結果を表  に示す．
こ の 結 果 を 見 る と ，ア イ テ ム 変 数 の 順 序 付 け がタプル頻度表を構築する 0スクリプトを生成し，そこから ' ( 2 法を用いて頻出パタンを抽出するという形で，生成される '  の節点数を調べ'  のサイズに大きな影響を及ぼすことがわかた．その結果を表 & に示す．データベース名の隣の 

る．動的重み付け法の場合はアイテム変数の数に比例内の数字は，抽出するパタンの最低頻度を表したもの

して '  のサイズが増加しているのに対して，低である．つまり，この数字より頻度が高いパタンを抽

頻度上位順では指数的にサイズが増加している．これ出するということになる．

は，今回の人工的なデータベースでは全てのアイテム

この実験結果より，今回の動的重み付け法はアイテの出現回数が同じであるので，出現回数で順序付けを

ム変数を低頻度上位順に並べたものと非常に近い効果
(=6 ( に関ししようとしても結局アイテムの出現順に並んでしまを得られることがわかった．

うため，低頻度上位順では効果的な順序付けができなては今回の手法の方がよい結果を得られている．また，かったためである．これに対して動的重み付け法では，高頻度上位順と比べると大きな縮約効果が得られてい つのアイテムの順序が決まったときに，その決まっることがわかる．

たアイテムの重みが関連の深いアイテムに分配される

また，動的重み付け法にかかる処理時間は表 - のよことになるので，'  のサイズに関して非常に縮約うになる．この表において，  が改良前の動的重み効果のある順序付けができたのだと考えられる．この付け法の計算時間であり， 6 が改良を加えた動的重ことから，この人工的な例題では，局所計算性が大きみ付け法の計算時間である．

電子情報通信学会論文誌   表

トランザクションデータベースにおける '% の動的重み付け法の効果

  7=  +  -. / # +  " "     -. / # /   95
! 5   &
&

&
!!  & &""  &


&
%/,4- 2 <4  &  &  

表  動的重み付け法の順序付けの計算時間  1!  " ! +  -. / #    !!
"" 
%/,4- 2 <4%/,4- 2 <4!
!  
  

 

      






& 

 

 

 

 
 

 3#  0    9! 
5&
& 

& 
&   & 3#  0  .
! 
5

&
 &   & 9

 3# ! 

 
 


おいては，順序付けにかかる計算時間が短い出現頻度に関する順序付け法の方が効果的なこともある．例えば，動的重み付け法の順序付けに

(=6 (では /3+ 秒かかっているが，単純に頻度を計算するだけなら /3, 秒ですむ．実用的な例題では，低頻度上位順で十分な縮約効果が得られるならば，低頻度上位
順で順序付けを行っても，比較的有効であるといえるのかもしれない．これは議論すべき課題の一つであるといえる．
また，実験では ' ( 2 を用いてタプル頻度
表から頻出パタンを抽出したが，その際にデータベー

以前の手法と改良を加えた手法を比較すると，格段スの種類やアイテム変数の順序付けによって，' に処理時間が削減されていることがわかる．この処理の生成にかかる時間が著しく変化することがわかった．

時間の削減の度合いに違いが見られるのは，データ

例えば，#2$$ では動的重み付け法では 3, 秒ですん

ベースがより疎なものほど処理時間の削減が顕著であだが，高頻度上位順では &/-+3+ 秒もかかった．しかし，%$2% においてはどの順序付けでも大きな処るからである．

  考察

理時間の差はなかった．これは，0 プログラムで今回の実験で，'  における動的重み付け法の順

は処理を高速に行うためにハッシュテーブルを用いて序付けによる '  の縮約効果が確認できた．出現

おり，そのハッシュテーブルの効果によって処理時間

頻度だけでは効果的な順序付けができない場合にも，に差が出てしまったと考えられる．

動的重み付け法は効果的な順序付けを行えることがわ
かった．しかし，実際のベンチマーク例題において実



おわりに

験を行った場合では，高頻度上位順と後出し上位順よ

本稿では，データベース解析において生成されるりは効果的な順序付けができていることが確認できた'  の簡単化に関して種々の実験を行った．その結が，低頻度上位順とは大きな差は見られなかった．こ果，トランザクションデータベースにおける ' 

れは，人工的な例題では局所計算性が非常に大きく影の動的重み付け法による '  の縮約効果が確認で響したが，実際のベンチマーク例題ではそれほど大ききた．人工的な例題においては局所計算性を反映する

く影響しなかったためと思われる．また，低頻度上位ことで，効果的な順序付けを行うことができた．また，順では出現頻度の低いアイテムから上位に並べられる

実際のデータベースにおいても効果的な順序付けを行が，これは動的重み付け法で出現頻度の低いアイテムえることが確認できたが，出現頻度を基に行った順序

により大きな重みが伝えられる傾向があるということ付けと大きな差が生まれない場合もあるということがと類似している．このことから，実際のベンチマークわかった．今後は様々なデータベースに関して実験を例題においては動的重み付け法と低頻度上位順では似行うとともに，データベースの特徴が順序付けの効果

たような順序付けになったと考えられる．

にどのように影響するのかも調べたい．また，現在のこのように，局所計算性よりもアイテムの出現頻度の方が '  のサイズに大きな影響を与える場合に

 回スキャンすることにな  時間かかり，大規模なデータベースを手法では，データベースをるので

論文／頻出パタンマイニングのためのゼロサプレス型  の変数順序付け方法とその評価扱う際にはまだ時間がかかりすぎる．このことから変数順序付け法に関して，データベースを定数回スキャンして効果のある順序付けを行う手法の検討など，より実用的な変数の順序付け法に関して研究していき
たい．
謝辞
基盤

本研究の一部は日本学術振興会科研費補助金
 「二分決定グラフに基づく大規模データベースの効率的解析処理アルゴリズムの研究」（課題番号
>-/// 研究代表者 湊 真一）による．

文

献> ? * .  < & @ / "" & * ,6 "& @ :" ""# .  2 6 !&   : ( + . "* & " .#: "  " A"< # : ( "#  /"" & / $ & 4 & 
> ? %( "& * 7& B 4  #! + % "+"" ! "  "& 777  " 1! & 14&  & 4 >? / C & @ C < "# D A <  7:  ""# ! : ! " + % " ! " ! #  # " " ( # " #  ! " $ +
777E.1/ " " " 1"+  " " 1!  4.# #   " 11.4&  4& D: "  >? C & /& C < & @& "# A < & D& 7: 4" "# ! ! " " + % " ! "! #   # " " ( # " #  !& " $.1/E777 " " " 1"+ " 1!  4.# #  "11.4&  & 4
>? F @ "& C $ & G G"& * / & /""   "$  " < 1 "##  B "  "H .   "4$  "  .  &   /"" "# A"<6 #: (&  & 4& >? / 6& ,& - " & . *& % ("& * A& "# 2" "4
 & . ,& 0  : I " " " ( # "#  ! "  ("  ":"! "& " $.1/E777 " " " 1"+ " 1!  4.# #  "11.4&  & 4>? , /" & D 
"# , G C!  ,  # 4" ( # " #  ! <  # #  +Æ " % " +"" ! "  " " $+  .1/E777   " .! " 1"+  ".1J&   4& F" >? 湊 真一& 石浦 菜岐佐& 矢島 脩三& 論理関数の共有二分決定グラフによる表現とその効率的処理手法& 情報処理学会
論文誌& 2  & D &4& F " (  
>? /" & ,& ' 4   # % +   ! " 4 " " !"  !& " $ 
.1/E777   " .! " 1"+ .14& &  4 > ? 湊真一& 2,3$H ゼロサプレス型 % に基づく「重み付き積和集合」 計算プログラム& 717  " * 
13/$ 4  4
> ? 湊真一& 有村博紀& ゼロサプレス型二分決定グラフを用いた
トランザクションデータベースの効率的解析手法& 電子情報通信学会論文誌& 2 F4& D &．  4  & 
> ? , /" & @ .!    " $  " /"""# A"< # "# 8" %  # " ' 4   #% " $   " " " -6 "
A"< # : ( " "#:      A4
&  4& ,  > ?  "& ,& @ ! & A& "# G C! & ,&  !48( +   ! :   # "  ! +  # " ( # " #  !& "  " " ",(! ! " . ! "# 1!  "& 0D1,4
 & , "  & 4> ? / F ' 6& ,  . ! + . " /"4
" & 777  " A"<    7"   &  4&（平成 88 年 88 月 88 日受付）

岩崎玄弥

 北大・工・電子工卒，現在& 同大大学院修士課程に在籍 二分決定グラフを用いたデータベース解析処理の研究に従事
情報処理学会会員

湊

真一

（正員）

 京大・工・情報卒，  同大大
学院修士課程了．  同博士（工学）．

 D 入社．以来，大規模論理デー
タの表現と処理アルゴリズムの研究開発に従事．  米国スタンフォード大客員研
究員．  D 未来ねっと研究所主任研員．  より北大情報科学研究科助教授（  准教授）．著
書K%" (  "  ! "# .  " + 20,1.K A < &   本会  周年記念論文優秀賞，
 情報処理学会山下記念研究賞&  人工知能学会研究会
優秀賞．777，情報処理学会& 人工知能学会各会員

ツォイクマントーマス
 ドイツ・フンボルト大大学院修士課程了．  同博士（理学）．同年同大助
手．  九大理学部基礎情報学研究施設
助教授．  同大大学院システム情報科
学研究科教授．  ドイツ・リューベック
大情報理学専攻教授．  より北大情報科学研究科教授 機械学習や知識処理に関する計算理論の研究に一貫して従事 同分野の国際学術誌・著名国際会議での研究発表および学会運営等& 継続的に活動している  より計算論的学習理論国際会議 .0 運営委員長

  %$?#" Æ#  %2) 1 )  6 $' $ 2 $ 6 $)3 )" $)  $"$% )$ $  6 1 2 ) 







'($$$) 2(6 $) $   1) @ A#  3 9  1#$  ' $ " # $   (  1# $ $#  " 1

$ 2 #2

  ($#  #%6    %$$   $ #  )  6 $$3 B2 '  $ :))$  2 @  6 ) 
1 %$ %  $ "$ $ $ $)3  2 $    $1   ($#   $ #  )  6 $$ "

 %2) 1 '  @  6 ) ) $2 < %  $$3)  %    '  1   6  " )# $  )

 %$ @  6 ) 