情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences 2009 (IBIS2009)

共起成分の含意関係に基づくデータマイニングの実験と考察

Experiments and Considerations on Data Mining
Based on Cofactor Implication
二木 克也∗
Niki Katsuya

湊 真一†
Minato Shin-ichi

Abstract: We report some unknown relations among the items in the database can beextracted by focusing on cofactor implication. Cofactor implication can be found by using
ZDD which is eﬃcient algorithm for processing data. However, as the means has strict
restrictions for irregular data, some meaningful relations might be left unfound. In thispaper, we propose the way for extracting such linkage, and studied what can be extracted,
especially from the database which consists of one-hot type items.
Keywords: BDD, ZDD, data mining, transaction database, cofactor implication, sets ofcombinations

1

まえがき
近年，大規模記憶装置の発展などによって，大規模なデータベースの中から有用な規則を発見するデータマイニングの研究が盛んになっている．頻出アイテム集合マイニング（Frequent Itemset Mining）は，最も基本的なデータマイニングの問題の１つであり，Agrawal 等 [2]による Apriori アルゴリズムの研究に始まり，現在までに様々なアルゴリズムが提案されている．
我々はこれまでに，VLSI CAD の分野で大規模論理関数データの表現法として広く用いられている二分決定グラフ（BDD: Binary Decision Diagrams） [3]，その中でも「ゼロサプレス型 BDD（ZDD: Zero-suppressedBDD） [4]」と呼ばれるデータ構造を用いて，トランザクションデータベースにおける頻出アイテム集合を効率よく生成する手法に関する研究を進めている．ZDD を用いることにより，大規模な組合せ集合データを非明示的に列挙し，頻出アイテム集合の発見から解析に至る多様な演算を効率よく実行することができると期待されている．
一方，ZDD を用いることにより，「共起成分の含意関係」を検出する手法が湊らにより提案されている [1]．共起成分の含意関係が成り立つとは，２つのアイテム a，∗ 北海道大学大学院情報科学研究科アルゴリズム研究室, 060-0814

札幌市北区北 14 条西９丁目, e-mail niki@mx-alg.ist.hokudai.ac.jp
Algorithm Laboratory, Graduate School of Information Scienceand Technology, Hokkaido University , Sapporo, 060-0814 Japan.
† e-mail minato@ist.hokudai.ac.jp

b に関して，a と共起する成分の集合と，b と共起する成分の集合との間に含意関係が存在することをいう．共起成分の含意関係を抽出し，直接的な含意関係と比較することにより，アイテム同士に直接の含意関係がないにも関わらず，共起成分には含意関係があるようなアイテムの組を検出することができる．これらのアイテムの組には，これまで発見されていなかった，何らかの興味深い関係が存在している可能性がある．一例として，

mushroom [7] というデータベース例題より共起成分の含意関係を抽出した場合，このデータベースは n 者択一型のデータベースで，抽出された関係は全て，それぞれ同じ選択肢に属する複数のアイテム間の関係であった [11]．
しかしながら，現在提案されている手法では，a と共起する成分と b と共起する成分の包含関係に，わずかでも破れがあれば，どんなに強く共起成分の含意関係に準ずる性質をもつ関係であっても，これを抽出していない．そこで，本稿では，このような例外を許容した共起成分の含意関係を抽出する手法を提案し，抽出した結果が持つ意味，ならびに，その有用性について考察する．

2

共起成分の含意関係と ZDD

2.1

ZDD とトランザクションデータベース

BDD は，図 1 に示すような論理関数のグラフによる表現である．一般に，論理関数のそれぞれの変数につい図 3: トランザクションデータベースの例
図 1: 二分決定木と BDD，ZDD

本稿では，複数個のアイテムの組合せが１つ１つのレコードとなっている「トランザクションデータベース」を対象とする．図 3 に簡単な例を示す．トランザクショ
ンデータベースでは，個々のレコードは各アイテムが出現するかどうかの組合せのみを記録しており，アイテムの順序は問わない．つまり，ab と ba を区別しない．一
般的なデータマイニングでは，１つのデータベースに同じアイテム組合せが複数回出現するとき，その出現回数を「頻度」として意味を持たせるが，本稿では，問題をまず単純化して，１回以上表れたアイテム組合せを集合として扱うこととする．なお，頻度を扱う拡張も可能で

図 2: ZDD の簡約化規則ある．て，0，1 の値を代入した結果を，二分岐の枝（0-枝/1枝）で場合分けし得られる論理関数の値を，2 値の定数2.2共起成分の含意関係節点（0-終端節点/1-終端節点）で表現すると，図 1 の共起成分の含意関係 [1] が成り立つとは，２つのアイような二分木状のグラフになる．このとき，場合分けすテム a，b に関して，a と共起する成分の集合と，b とる変数の順序を固定し，冗長な節点の削除と等価な節点共起する成分の集合との間に含意関係が存在することをの共有という 2 つの縮約規則を可能な限り適用するこという．

により，「規約」な形が得られ，論理関数をコンパクト且つ一意に表せることが知られている．

データベースに含まれる全てのアイテムの組合せの集合をあるアイテム a を含むか含まないか，および，アイBDD は元々は論理関数を表現するために考案された

テム b を含むか含まないかで Sab , Sab , Sab , Sab の４通ものだが，これを用いて組み合わせ集合データを表現・りに分類する（図 4）．このうち，a のみと共起する成操作することも出来る．組合せ集合とは，「n 個のアイテ分の集合 (Sab ) が，b のみと共起する成分の集合 (Sab )ムから任意個を選ぶ組み合わせ」を要素とする集合であに含まれるとき，すなわち，Sab ⊇Sab が成り立つとき，る．これを BDD で表現するとき，類似する組合せが多アイテム a はアイテム b に対して共起成分の含意関係にければ，部分的に共通する組合せがグラフ上で共有されあると（以下，a→b のように記述）いうことができる．て，記憶量や計算時間が大幅に削減される場合がある．

また，このとき，b→c が成り立つならば，a→c も成りさらに，組合せ集合に特化した「ゼロサプレス型 BDD立つ．一方，Sab が空集合であるとき，a そのものが必（ZDD）」 [4] を用いると，より簡潔な表現が得られ，一ず b と共起するので，すなわち，a は b に対して直接的層効率よく扱うことが出来る．

含意関係にあるということができる．

ZDD では，冗長な節点を削除する簡約化規則が通常の BDD と異なり，1-枝が 0-終端節点を直接指している節点を取り除く（図 2），という規則になっている．こ例えば，以下のような S という集合があれば，S = {bc, acd, ce, ac, abe, bd, bcd}
次のような集合へ分けられる．

れにより ZDD では図 1 のように，組合せ集合に一度もSab = {ce}選ばれることのないアイテムに関する節点が自動的に削Sab = {c, d, cd}
Sab = {cd, c}
Sab = {e}除されることになり，BDD よりも効率よく組合せ集合を表現・操作することが出来る．

図 6: Sab と Sab の関係
図 4: 共起成分の含意関係

全てのアイテムのペアに対して，約 n 倍高速なアルゴリズムで検出することが可能である [1]．
これまでの実験結果としては，現実のインフルエンザのアミノ酸配列のデータベースから，全ての共起成分の含意関係を，現実的な時間で抽出することに成功している [5]．また，そのようなアルゴリズムを実装したプログラムとして，VSOP [6] が公開されている．

3

誤差を許容した共起成分の含意関係

図 5: グラフ化した場合のクラスタ例

共起成分の含意関係を別の図（図 6）を用いて説明す

この例では，Sab ⊇Sab が成り立つので，a→b が成り立る．この図は，先ほどの４グループのうち，共起成分のつ，一方，Sab ⊇Sab は成り立たないので，b→a は成り立たない．
共起成分の含意関係を抽出し，直接的な含意関係と比含意関係を判定するにあたり必要となる Sab と Sab の関係を表したものである．Sab にも Sab にも含まれるものを αab ，Sab に含まれるが，Sab には含まれないものを較することにより，アイテム同士に直接の含意関係がな

βab ，反対に Sab に含まれるが，Sab には含まれないもいにも関わらず，共起成分には含意関係があるようなアのを γab という３つの集合に分けられる．すなわち，イテムの組を検出することができる．既存の研究の多くは，直接的含意関係に基づいているのに対して，共起成分の含意関係に基づいた研究は少ないので，これらのアイテムの組には，これまで発見されていなかった，何らかの興味深い関係が存在している可能性がある．直接的
含意関係とは，図 4 でいうところの Sab ，もしくは，Sabのどちらか一方が空集合である状態なので，本稿では，Sab と Sab がどちらも空集合ではない場合のみを指して，共起成分の含意関係として，取り扱うこととする．
特に，抽出された関係について，グラフ化すると，いくつかのクラスタを形成する場合があることがわかっている．図 5 は，本稿で実験に使用したデータベース例題

αab = Sab ∩ Sab ,βab = Sab \ Sab ,γab = Sab \ Sabとする．このとき，αab =∅，かつ，γab =∅ であるならば，Sab =∅ なので，直接的含意関係となり，αab ̸=∅，かつ，γab =∅ であるならば，Sab ⊇Sab が成り立つので，a→b という共起成分の含意関係が成り立つ．例えば，前章で用いた例では，
Sab = {c, d, cd}
Sab = {cd, c}であるので，次のように分類できる．

αab = {c, cd}
βab = {d}mushroom [7] より，共起成分の含意関係を抽出し，グラフを作成したものから，一部を抜粋したものである．
このクラスタに関するデータ構造には，何かしらの有意γab = {∅}
γ が空集合となっていることからも， a→b が成り立つな情報が含まれている可能性が高い．

ことが確認できる．また，αab = αba , βab = γba である．

なお，n 個のアイテムが存在するならば，共起成分のところで，もし，γab に一つでも要素があったとした

含意関係を抽出するためには，n(n − 1) 通りのアイテムら，どうだろう．仮に，ある組み合わせについて，上ののペアから制約条件を満たすものを全て抽出する必要がように分類したところ，αab が数千パターン存在する一あるが，ZDD を用いることにより，データベース中の方で，βab と γab がともに一つずつ要素を持っていたと

択一式データベースにおける共起4成分の含意関係
択一式データベースでは，図 7 のように，データベースに含まれるアイテムがいくつかのカテゴリーに分類でき，全てのカテゴリーから一つずつ選択されることで，1 件のレコードが複数の排他的選択肢の集合であるようなデータ構造になっており，それぞれのレコードに含まれるアイテム数はカテゴリー数に等しい．ここで，この
図 7: 択一式データベースの例

択一式データベースより共起成分の含意関係を抽出した

すると，その組み合わせは，共起成分の含意関係にはな

場合，カテゴリーを跨いだクラスタが検出されることがいので，従来手法では，その関係を抽出することができ理論上あり得ないことを示す．例えば，図 4 で a が Aなかった．しかしながら，そのような場合においても，というカテゴリーに属するアイテムで，b が B というカ共起成分の含意関係に準ずる関係にあると推認できるテゴリーに属するアイテムだとすると，Sab には，カテし，また，βab や γab に含まれているデータ自体が誤り

ゴリー B に属するアイテムがない組み合わせだけが含であったり，例外的なデータであったりする可能性は少まれるのに対して，Sab は，カテゴリー A に含まれるアなくない．したがって，このような関係の中にも，なにイテムがない組み合わせの集合となることから，これらかしらの重要な関係が隠れているかもしれない．そこで，に共通する αab は，絶対に存在し得ないからである．こ

本稿では，αab に何かしらの要素が含まれているものの，のことから，択一式データベースにおいては，本手法をβab や γab が空集合でないために共起成分の含意関係と用いた上で，例外を最大限許容することで，完全ではな

しては，抽出できなかった関係を抽出し，そのような関いものの，アイテムをカテゴリーごとに分類することが係が持つ意味について，議論する．

できる可能性がある．

なお，本稿では，共起成分の含意関係を抽出する場合と同様に，VSOP [6] を用いて実験を行ったが，このよ

5

実験と考察

うな例外を許した共起成分の含意関係に準じた関係を抽

5.1

択一式データベースにおける実験

出する処理は実装されていないので，３つの段階に分けて，関係を抽出した．
まず，αab が空集合ではない組み合わせを，VSOP により抽出し，それぞれに含まれるパターン数を数える．
次に，αab が空集合でない組み合わせに関して，βab とγab それぞれに含まれるパターン数を数える．そして最後に，αab ，βab ，γab のパターン数を比較することで，例外を許した共起成分の含意関係を抽出する．αab に対して，βab ，γab が十分に小さいことをもって，誤差の範囲であるとし，例外を許した共起成分の含意関係にあるとするが，比較する基準を変更することで，抽出できるパターン数がどのように変化するかについても考察する．
本稿では，αab が βab もしくは γab の x 倍以上のサイズを持つアイテムの組み合わせについて，x を変化させて，複数の条件で抽出する．また，誤差を最大限に許す場合として，αab が空集合でない組み合わせを全て抽出する．

まず，誤差を許容することにより，新たに抽出することができるようになった関係が，どのような意味を持つのか調べるために， データベース中の各アイテムの意味が分かっているデータベースである mushroom(FIMIベンチマーク [7] より) に対して，本手法を適用した．

mushroom はキノコの生態に関するデータベースで，各アイテムは色やにおい，生息場所などを表している．デー
タベース中には 119 個のアイテムが存在し，それらは23 のカテゴリーのいずれかに分類され，それぞれのカテゴリーの中からアイテムが一つずつ選択されることにより，8124 件のレコードが表現されている．例えば，赤いキノコのレコードであれば，色のカテゴリーから赤というアイテムだけがそのレコードに含まれ，紫や橙といったアイテムが同時に含まれることはない．においなど，他のカテゴリーについても，同様であるので，各レコードは 23 個ずつのアイテムを含む．また，例外を許さない共起成分の含意関係は 53 組である．
本手法を実行したところ，αxy が空集合ではない (x, y)のペアが 106 組存在した．これらのペアを全て許容し，グラフを描写した場合，23 のカテゴリーの内，６カテ

図 8: mushroom からの抽出結果
ゴリーで，全てのアイテムを含むクラスタが抽出でき，

図 9: インフルエンザウイルスデータからの抽出結果

その他のカテゴリーに関しても，過半数のアイテムがクラスタとして抽出しているものが多かった．
次に，α と β ，γ の差が 10 倍を超えるほどの差がある場合を考えてみる．これを例外を許した共起成分の含意関係とするならば，抽出された関係は 62 組，すなわ
ち，新たに抽出できるようになった関係は 9 組である．

図 10: BMS-Web-View-1 からの抽出結果

この内，6 組は例外を許さない共起成分の含意関係を抽出し，グラフ化した場合でも存在していたクラスタ内の小関係に基づいて，グラフを作成すると，各クラスタ内アイテム同士の関係で，残りの 3 組は，全く新しい関係の関係性に着目することにより，有意な情報を抽出できであった．中でも，several と solitary の関係などは，双る可能性があるのではないかと思料される．

方の意味が近いことから，データベースへ登録した観察者が同種のキノコを別の表現を用いてデータベースへ記

5.2

非択一式データベースにおける実験択一式ではないデータベースに本手法を適用した場合録したことに由来している可能性がある．
なお，実行環境は 2GHz Intel Core2 Duo，4GB

では，どのような関係が抽出できるのか調べるために，1067MHz DDR3 である．また，以降の実験についてもインターネット通販サイトの閲覧履歴のデータベースで同様の環境で実行した．

ある BMS-Web-View-1(FIMI ベンチマーク [7] より) へ

次に，択一式で，より大規模，かつ，実用的なデータ適用した．このデータベースには，497 個のアイテムかベースに対して，本手法を適用した．このデータベース

らなる，42629 件のレコードが登録されている．一つ一には，インフルエンザウイルスのアミノ酸配列が登録さつのアイテムはの通販サイト上のページ一つ一つに対応れている．登録されているレコード数は 1750 件で，アしており，一つのレコードは，一人の顧客が訪問した際，イテム数は 1182 個である．また，共起成分の含意関係閲覧したページの情報で構成されている．なお，例外をは 77 組抽出できている．このデータベースでは，位置許さない共起成分の含意関係は 25 組抽出されている．

情報とその場所を占めるアミノ酸の種類が一つのアイテ

本手法を適用したところ，α が空集合ではないペアはムとなっていることから，特定の位置に関して，唯一のアミノ酸の種類を選択するという択一式のデータベース

91139 組存在した．この，データベースもインフルエン
ザウイルスのデータベースと同様に，α が β ，γ よりもとなっている．

小さいことから，例外を許した共起成分の含意関係とし本手法を適用すると，α が空集合ではないペアが 337て，新たに抽出された関係はなかった．また，α が空集組存在した．これらのペアは，やはり，同じ選択肢に含合でないペアの数もかなり大きな数字であることから，まれるアイテム同士の組み合わせであった．このデータ

少なくともこのデータベースに関しては，本手法を用いベースでは，mushroom の場合と比べ，β ，γ が α よりることによって，有意な関係を抽出することは難しい可も圧倒的に大きい組み合わせが目立った．これは，イン能性が高い．

フルエンザウイルスのアミノ酸が変化する中で，当該組み合わせが変異する前と後，両方の配列が登録されてい6

結論る場合，この二つの配列が α の成分として，検出され本稿では，例外を許容した共起成分の含意関係を検出ている可能性がある一方で，当該組み合わせ以外でも変するする手法を提案し，この手法を実際のデータベース化が起こっている場合，その結果として生まれた配列がへ適用する方法について述べた．択一式のデータ構造をβ や γ の成分として分類されるためである可能性があると考えられる．このため，例外を許した共起成分の含意持つデータベースに適用したところ，そのデータ構造を関係として，新しい関係を抽出することはできなかった

しながら，例外を許さない共起成分の含意関係からの拡が，先の仮定が正しいという前提に立てば，β と γ の大張という観点からみると，観察者の視点というアナログ大まかではありながらも，抽出することができた．しか的要素を持つ mushroom においては，有意な関係を抽出することに成功したが，インフルエンザウイルスのアミノ酸配列データでは，新しい関係を抽出することはできなかった．むしろ，例外を許さない共起成分の含意関係が成り立つ状況こそが特異な状況であると言えるかもしれない．また，非択一式構造のデータベースであるネット通販サイトのページ閲覧履歴データでは，本手法を用

tions on Competers, Vol. C-35, No. 8, pp. 677–691（1986）[4] S. Minato: “Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems,” In Proc. of
30th ACM/IEEE Design Automation Conference(DAC’93), pp. 272–277（Jun. 1993）

いて，有用な関係性を抽出することはできなかった．

[5] S.Minato and K.Ito: “Symmetric Item Set Mining

なお，今後の展開としては，以下のようなものが挙げ

Method Using Zero-suppressed BDDs and Aplication to Biological Data,” Trans. of the JapaneseSociety of Artiﬁcial Intelligence, Vol. 22, No. 2, pp.

られる．

• 択一式データベースで，本手法により，抽出した結果をグラフ化した際，カテゴリーごとのクラスタが形成されるが，そのクラスタ内での関係性か[6] 湊: “VSOP：ゼロサプレス型 BDD に基づく「重み付ら，有用な情報が抽出できるか検討し，抽出できき積和集合」計算プログラム,” 電子情報通信学会コるのであれば，既存の手法と比較する．

ンピュテーション研究会, 信学技報

• 本稿では，例外を許すことが有用であるか否かに着目したために，全てのアイテムのペア（アイテム数の２乗個）についての検査を単純に繰り返し実行しているが，アルゴリズムを工夫することにより計算回数を削減し高速化できる可能性があると思われる．

Vol. 105, No.
72, COMP2005-10, pp. 31–38（May. 2005）[7] B. Goethals, M. Javeed Zaki (Eds.), Frequent Itemset Mining Dataset Repository, Frequent Itemset Mining Implementations (FIMI’03),
http://ﬁmi.cs.helsinki.ﬁ/data/ (2003)[8] 湊, 有村: “ゼロサプレス型二分決定グラフを用いた• 本稿では，個々のアイテムのペアに関する共起成トランザクションデータベースの効率的解析手法,”分の含意関係について考察したが，アイテムの組電子情報通信学会論文誌, Vol. J89-D, No. 2, pp.

合せのペアに関する共起成分まで議論を拡張し，172–182（Feb. 2006）

その有用性や計算時間について検討する．

7

156–164（Feb. 2007）

謝辞

ご指導をいただいた北海道大学アルゴリズム研究室
Thomas Zeugman 教授に感謝いたします．またご討論いただいた岩崎玄弥さんを始めとする同研究室の方々に感謝いたします．

参考文献[9] 湊: “データベースの頻出アイテム集合を表すゼロサ
プレス型 BDD の変数順序付けの理論的考察,” 電子情報通信学会コンピュテーション研究会, 信学技報

Vol. 106, No. 566, COMP2006-55 pp. 37–42（Mar.
2007）[10] 湊: “二分決定グラフ（BDD）を活用したデータマ
イニング・知識発見技術の最近の話題,” 電子情報通信学会 人工知能と知識処理研究会, 信学技報, Vol.

107, No. 78, AI2007-6, pp. 27–32（May. 2007）[1] 湊: “「共起成分の含意関係」を満たすアイテム集合のデータマイニング,” 人工知能学会 第６５回人工知能基本問題研究会 資料, SIG-FPAI-A603-10, pp.

53–58（Mar. 2005）[11] 湊: “「共起成分の含意関係」に基づくデータベー
スからの知識発見,” 人工知能学会 第 4 回 データマ
イニングと統計数理研究会 (SIG-DMSM) 講演報告集, SIG-DMSM（July. 2007）[2] R. Agrawal, H. Mannila, R. Strikant, H. Toivonenand A. I. Verkamo, “Fast Discovery of AssociationRules,” In Advances in Knowledge Discovery andDat Mining, MIT Press, 307–328（1996）[3] R. E. Bryant : “Graph-based algorithms for
Boolean function manipulation,” IEEE Transac-