相関ルールとその周辺
岡田 孝，元田 浩……l…‖＝＝‖＝＝‖‖‖‖‖‖＝‖‖‖州……l………‖‖‖‖‖‖＝＝‖川l川……lIll……………………lIll……l……ll…l……刷……附‖……………川…………＝‖‖州l…………………l川…………‖‖＝‖‖‖＝＝＝‖‖‖‖…………川Il……‖‖…

が現れるようなトランザクションの割合を支持度

1． はじめに（ざ㍑♪），条件部のアイテムを購眉した顧客中で帰結部

最近のデータマイニングの発展を要素技術の観点かのアイテムを買った人の割合を確信度（co，げ）と呼ぶ．

ら振り返ると，1993年にAgrawalらが提起した相関

最低支持度（椚才乃5〟♪）と最低確信度（研わ‡CO，げ）を指定

ルールが大きな要因となっている［1］．元来の相関ル

して，データベースからすべての相関ルールを求める

ールは，スーパーマーケットでの買い物篭の内容を調ことが，Agrawalらの提起した問題である［1］．

べて，販売促進や店舗レイアウトに役立てようというこの間題を次のように定式化することができる．全バスケット分析を指向して提起された方法論である．

アイテムの集合をJ＝（fl，あ，…，才椚），′≠βとし，そのしかし，その枠組みが一般的なデータ解析に適由でき部分集合をアイテムセットと呼ぶ．βを全トランザ

る柔軟なものであることが評価され，現在でも非常にクションの集合とする．ここで各トランザクション

活発な研究が行われている．今後もデータマイニング

rはJの部分集合である．β≠ズ，y⊂Jでかつガn主要技術の一つとして位置づけられていくであろう

y＝￠を満たすものを，相関ルールズ⇒yと呼ぶ．

［2］．すでに邦文でも，人工知能学会誌の特集号［3］やアイテムセットズの支持度5〟♪（ガ）とは，β中のズ

福田らの書籍［4］で解説されているが，本稿では改めを含むトランザクションの割合であり，ルール方⇒て相関ルールの紹介を行うとともに，その間題点と関yの支持度鼠ゆ（ズ⇒y）は∫‡ゆ（ガリy）で，また確信連する最近の代表的な成果を取り上げて解説し，今後度coクげ（ズ⇒y）はざ〟♪（ガリy）／ぶα♪（ズ）で定義されの課題を明らかにしたい．

る．
ルールの確信度は通常の条件付き確率にすぎないが，

2．バスケット分析と相関ルール

スーパーマーケットでこのようなルールを調査すれば，2．1相関ルールとは（1）右辺に利益率の高い商品が現れるルールを調べ，そマーケットで売られている個々の商品をアイテム，の左辺から目玉商品を選定する，（2）よく併売される商

一人の顧客が購眉したアイテムのリストをトランザク

品群を近くに配置する，（3）多数のルールで条件部に現ションと呼ぶ．データベース中の全トランザタションれる商品をチラシに載せる，など多くの応用が考えらを解析すると，例えば，「バターを買った顧客は，それる．

の80％がパンと牛乳も買っており，この3種の商品

属性とその値の対をアイテムとすれば，表形式を含

すべてを買った人は全顧客の4％である」というようむ一般的なデータに相関ルールの枠組みを活用できる．

な知見が得られるであろう．これを次のように表した

例えば，トランザタション以外に性別，年齢が表形式

ものが相関ルールである．

データとして利用できれば，次のようなルールの検出［バター］⇒［パン，牛乳］：封ゆ＝4％，CO，げ＝80％が可能となる．

ここで，ルールの条件部，帰結部ともに複数のアイテ［性別：男，年齢：40代，ワイン］⇒［チーズ］

ムを含んでよい．また，ルール中のすべてのアイテム

また，帰結部をクラス属性に固定すれば，クラス識別

おかだ たかしの要因を説明するルールのみを取り出せる．ただし，関西学院大学情報メディア教育センター〒662−8501西宮市上ヶ原1−1−155

本来相関ルールは特徴を説明するためのもの（Char−

もとだ ひろし大阪大学産業科学研究所〒56ト0047大阪府茨木市美穂ヶ丘8−1
2002年9月号

acterizationru1e）であって，識別するためのもの（Disctriminationrule）ではないことに注意しよう．
数値属性はカテゴリー化する必要があるが，トラン© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（3）565

ザクション形式と表形式のデータを統一的に扱えるた納するが，∽ゴ乃ざ祝♪を満たすアイテムの種類を1，000

め，受講科目解析による履修指導やカルテの分析など，としても，すべての組み合わせを数えれば，C2で50

伝統的なデータ解析においては手がつけにくかった領万，C3では1億近い数の候補が存在する．図1の例

域でも素直な分析が可能である．

では，F2の組み合わせでC3を作る．ここで，C3

2．2 アプリオリアルゴリズム

中の（abc）は（ab）と（bc）から生成されるが，（ac）

大量のデータを対象とした時，すべての相関ルール

はF2の中に存在しない．したがって実際に数えるまを計算することは実際には困難であった．この課題をでもなく，（abc）の支持度が朋才那Z￠を超えることは現実的な時間で処理することに成功し，しかも以降のなく，C3からこのようなアイテムセットをあらかじ

研究の立脚点となったのがアプリオリ（apriori）ア

め除去できる．

ルゴリズムである［5］．このアルゴリズムの第1段階

ラティス中でアイテムセットの支持度は，下部に進では，ダ＝（ズ⊂′lざ〟♪（X）＞椚g乃ざ〟♪）で定義される頻

むほど単調に減少する．アプリオリアルゴリズムは，

出アイテムセットを網羅的に計算し，第2段階はこの単調性1を候補アイテムセットの枝狩りに利用す

研わ官COクげ以上の確信度を持つルールを，これらのアることで，効率的な計算を可能にしたといえる．

イテムセット聞から見出す．後段は簡単に行えるため，

2．3 相関ルールの問題点

以下前段の内容を図1に示す例に沿って説明する．

多くの研究者がこの方法に注目するとともに，そのアイテム群J＝（α，∂，C，d，e）とし，図1左に示す

間題点も明らかにされてきた．主要な論点は以下の4

トランザクションから，∽ゴ乃5以♪＝3／8として頻出ア種と考えられる．

イテムセットのラティスを構築しよう．図の右側には，（1）相関ルールの英語はassociation ruleであって，アイテムセットとその支持度数が示されており，下線

correlationではない．すなわち，バターを買うで示されたものが頻出アイテムセットである．計算は人の80％が牛乳を買うとしても，もし全顧客の以下のように進める．（1）1アイテムのみからなるすべ

80％が牛乳を買っているな．らば，これらの間に統ての候補アイテムセットClを準備し，データベース

計的な相関はなくルールは無意味である．

を読んでこれらの支持度を求める．支持度が∽古刀5乙ゆ（2）アイテムが密な状況（例えば多変量解析で扱う表

以上のアイテムセットのみをFlとして残す（この場形式データ）では，ラティスの第3層以下におい合はFl＝Cl）．（2）Fl内のすべてのアイテムセットても頻出アイテムセットが多数現れ，ラティスサ

対から長さ2の候補アイテムセットC2を生成し，デイズの組み合わせ爆発により計算が不能となる．

「タベースを読んで頻出アイテムセットF2を決定す（3）データベースのサイズが大きく主記憶に常駐できる．（3）F2のすべての対からC3を生成する．C3中ない時，その読み込みに時間がかかる．またサイのアイテムセットに対し，1アイテムを削除した長さズが小さくとも，ラティスの各層ごとに候補アイ

2のアイテムセットのすべてがF2の中に存在するか

テムの支持度を数えるにはコストがかかる．

否かを調べ，もし存在しなければC3から削除する．

（4）出力されるルール数が莫大な数に上り，ルールのデータベースを読んで，残ったC3の支持度からF3

視察が実質的に困難である．∽オ乃5〟久椚ブ乃CO玖／を決定する．（4）以下F4，F5を同様に求め，頻出ア

値を上げてルール数を減らすと，その内容は既知

イテムセットがなくなったところで，計算を止める．

のことばかりとなり，解析自体が無意味となる．

このアルゴリズムで計算コストが高いのは，トラン

以下の各節では上記問題点に関連する事項に絞って，ザクションを読み候補アイテムセットの支持度を更新する所である．候補アイテムセットはハッシュ木に格［cl〕 血5 血5 血13 血4 血3

最近の注目すべき成果を取り上げて解説する．

3．データペーよの圧縮格納
計算高速化のため多くのアイデアが試されたが，もっとも有効とされたのは最初にデータベースを読みこ【∝］：：；；
ID 璃眉アイテム 口 a bc 2 a bd 3 a e 4 b c 5 a bc d 6 e 7 a bde 8 d【c3］ W3（a b c）？（b c d）？
図1頻出アイテムセットのラティス

566（4）

み，後の計算で必要となるアイテムセットの支持度を1頻出アイテムセットの部分集合は頻出アイテムセットでなければならない．すなわち，非頻出アイテムセットを部分集合として含むアイテムセットは頻出ではない．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

主記憶中に保持する戦略であった．FP−treeアルj リ

この木では，まず1アイテムセットを第1屑に辞書順

ズム［6］が有名であるが，ここではより簡明で効果もに配置する．第2層には，第1屑のアイテムを最後に高いとされる部分和の方法［7］を解説する．

持ち，辞雷順で親よりも先行する2アイテムセットを，

I＝（a，b，C，d）とし，24種のすべての可能なアイテ

やはり辞書順に配置する．以下同様に，P−tree中のムセットで表されるトランザタションが各一つ存在す

すべての節点を第3層以下にも配置する．各節点にはるデータベースを想定しよう．この方法では，すべて支持度を加算するためのカウンターを付しておく．

のアイテムセットを図2に示すsetenumeration tree

ここで，例えば￠（acd）による支持度への寄与を考の形で表現する．例えば，（a）の節点下には，（a）を含む

えてみよう．この寄与は，T−tree中のQ（a），0（ac）

長さ2のアイテムセット中から辞書順で最初の（a b）にはすでに取り入れられている．したがって，d，ad，を置く．（a b）の弟の位置に，bに続くc，dが付加さ

cd，aCdの支持度を計算する際のみ，これを取り込む

れた（ac），（ad）の節点を配置する．また，子の節点必要がある．この場合，T−tree中でacdの最後のアとして，（abc）を，さらにその兄弟として（abd）をイテムdの節点から始めて節点acdに至るまでの道

置く．このようにすれば，木にはすべてのアイテムセ

筋で，aCdの部分集合となっている節点にQ（acd）をットが正確に一度だけ出現する．

加算する．この操作をすべてのアイテムセットについ各トランザクションでそのアイテムセットが整列済
みなら，それを容易に図2の木で辿ることができる．

て行えば，結果としてT−treeの各節点に支持度が計算される．

各節点から見れば，トランザクションが自分の上を通この方法を実際に適用する場合，可能なすべてのアって子への途を辿るか，または自分が終点となる場合

イテムセットを用意するとP−treeのサイズが爆発すに，その回数を数える．これにより，図2の節点に付るので，トランザクションの読み込み過程で必要な節した数が得られる．このようにして得られた木をP−

点のみを動的に生成し，tree構造を構成していく操

tree，節点iに付された数を部分和OLと呼ぶ．

作が必要である［8］．また，相関ルールを求める際に節点ノと正確に一致するトランザクション数をろは，T−tree全体を生成しておく必要はない．アプリとすると，￠f＝∑ろ（∀ノ，ノ⊇g，ノカ肋紺S才辞書順）とオリアルゴリズムと組み合わせ，ラティスの各レベルなる．この値を使えば，アイテムセット才の支持は，毎にT−treeの対応するレベルを生成すればよい．最5㍑♪（f）＝￠ ＋∑ろ（∀ノ，ノ⊃才，ノ♪柁Cede5才辞雷傾）で低支持度に満たない節点を枝狩りすれば，効率的に頻表される．例えば，Sub（bc）＝0（bc）＋P（abc）

出アイテ皐セットの支持度を求められる．

典型的なバスケット分析に適用した結果では，P−＋P（abcd）＝Q（bc）＋0（abc）＝4となる．
辞書順で先行するアイテムセットをもれなく見つけtreeのサイズがほぼデータベースのサイズに比例して，支持度を計算するには図3のT−treeを利用する．

て増加し，アイテムの種類が増加しても組み合わせ爆発を起こさないことが示されている．ただし，FP−
treeでも同じであるが，いわゆるアイテムが密な表
形式データに適用した場合，実際にどの程度の属性数まで対応できるかは明らかでない．しかしこの方法は，データベースの圧縮・再構築と見なすべきものであり，

P−treeを主記憶中に置ける限りは，高速に各種の頻度を計算することができる．相関ルールのマイニング
図2 P−treeによる部分和の表現に限らず，データベースの対話的解析一般に活用できると思われる．

4．Correlationを求めて出力ルールに，COrrelationの意味での相関を表していないルールが多数混じっているならば，ルール群全体が利用者にとっては無意味に等しい．そこで，条
図3 T−treeによる支持度の計算
2002年9月号

件部を空とした場合との確信度の比c（〃げ（ズ⇒y）／© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（5）56丁coクげ（β⇒y）をリフト値と呼び，これによって興味深

オリアルゴリズム同様ラティスの各レベルで，上限値いルールのみを選択することが考えられた．一般的にに満たない節点から下のサブラティスを枝狩りするこは，ズ，yだけでなく度，アをも考慮した分割表をもとができる．実際にバスケットデータに適用したとことに，例えばズ2値による評価をルールに与えること

ろ，3アイテムのレベルではたった一つの候補を調べが考えられる．しかし，頻出アイテムセットだけが数ればよいほどであり，最低支持度による枝狩りと比べえられているため，生成されたラティスから分割表のてその効率ははるかに高い．密なアイテムのデータにすべてのセルの数値を求めることはできない．

よる評佃が待たれる．

Brinらは，相関の高い属性の集合が一度見つけら

5．カスケードモデル

れれば，そのすべての上位集合でも相関が高いことを指摘し，ズ2値が高い値を示す最小の属性の組と分割

筆者の一人により提案された本モデルも，相関ルー

表中で特徴的なセルを求める方法を提案した［9］．しルの1種の発展であると見なせる．例えば図5左の表

かし，マイニングの立場からすれば，同じ属性対間でで，属性A，Bの値からYの値p，nを説明する問題を高い相関が見い出されるにせよ，多くの属性集合で指考える．A，Bの値をアイテムとして構築されたラテ

定されるより限定された事例群には，一段と興味深いィスを，このモデルでは図右側のように描く．ここで，ルールが隠されている可能性が残る．

それぞれの湖が節点を，その間の滝がリンクを表す．

この点で興味深いのは，森下らによるズ2値にもと湖の広さと滝の幅は事例数と大まかに対応し，また湖

づく枝狩り法である［10］．ルールの右辺となるべき目の高さが目的属性Yの純度を表すと考えよう．ここ

的属性Cを固定し，図4左上に示す分割表を想定すで発電能力の大きな滝を選びルールとして表現するのる．乃と∽＝ざ〟♪（C）が固定されているので，ズ2値はが，カスケードモデルである［11］．

滝の発電能力を表現するため，Giniによる平方和

ヱ（′）＝S〟♪（J）とy（J）＝SZゆ（′UC）の関数となる．
ここでJ⊃∫なる新たな条件′に対応する分割表をを用いる［12］．数値変数の平方和定義は（1）式のように考えると，点（ェ（J），y（′））の値域は図4右上で点を打変形できるが，ここでカテゴリー値の場合も事例オ，ノった平行四辺形内に限られる．森下らはズ2の凸関数

間でのごf−∬Jの値を，∬ ＝みの時に0，他は1とす性を使い，どのように条件Jを選んでも，2点（y（J），

れば，（2）式の平方和定義が得られる．ただし，乃は全y（′）），（∬（J）⊥y（′），0）におけるズ2値の大きい方の値

事例数を表し，♪（α）はその属性が値αを取る確率でが上限となることを証明した．

ある．

例えば条件′での分割表が図4左下の分割表（a）で5S＝（Jf一み）2（1）

55＝昔（1一写如）2）（2）

表されるとき，Jに何らかのアイテムを付加した条件′のズ2値は図の右下に示す分割表（b），（C）から計算される43，25のうち，大きい方を上限値とすることに一群の事例をある属性の値でC個の群に分割したなる．あらかじめ最低のズ2値を与えるなら，アプリ

時，元の全平方和（7SS：Totalsumofsquares）は（3）式のようにそれぞれの群内平方和（耶S：WithinCC ∑ ロ yズ●γ ∫J ∑ m■ツn￣m−∫＋ッ m n￣〝‡ n￣∫ n（0，0）（刈lけ（り，0）J 20 30 50∑ 50 50 100

ブ 20 50 70

プ 50 30 gO∑ 50 50 10C 戸 ∑ J 30 20 50

C 戸 ∑ ノ 30 0 30（a）4．0（b）42．9∑ 50 50
C 己 ∑ ノ 0 2 20

図4 凸関数性によるズ2値の上限
568（6）xに（C）25．0

図5 ラティスのカスケード表現© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

−grOuPSumOfsquares）および群開平方和（BSS：

目的属性Zに対する・βSざ値が大きなリンクを選択

Betweengroupssumofsquares）に分割できる．なし，これを図6下側に示すルールとして表す．ここで，お，βS5は（4）式で定義し，添字U，エは分割前と後

ルール左辺は主条件部と前提条件部に分かれている．

を指示する．

この場合，リンクに沿って付加されたアイテム［B：Cy］が主条件を表し，上側節点のアイテムセット［A：73S＝∑（耶Sg＋βSざg）y］が前提条件となる．ルール右辺には，β55値とと

ダ＝1

もに，目的属性Zの分布が主条件の付加によりどの

βSS♂＝与写（♪乞（gト♪駅g））2

U，上で指定される事例群を滝の上側と下側に対応するラティス内の節点と見なせるので，このβ5Sgを滝の発電能力と解釈できる．したがって，ラティス中でβS5値の大きなリンクを選択して，それをルールとように変化したかを示す．図の属性Dのように主条
件と相関の高い属性が存在する場合は，たとえそれが説明変数であっても，付加的な右辺情報としてルール中に表示する．この情報は説明変数間の高い相関を示すため，実際の問題に適用してルールの解釈を行う際して提示すればよい．
図6はラティス中のリンクとそれから導かれるルーには，非常に有効な情報を与える．

ルの一例を示す．ここで，問題は説明属性A−Dの低カスケードモデルの計算でルールを検知するには，から，目的属性Zの値を説明することであり，またラティス中でその上下節点だけを生成すればよい．すすべての属性はy，nいずれかの値を取るとする．図では，上側節点がアイテムセット［A：y］で表され，

なわち図6のルールの場合，［A：y B：y D：yZ：n］のようなアイテムセットを生成する必要がない．

［B：y］のアイテムが滝に沿って付加されている．こ

したがって，密にアイテムが分布する場合でも，ラテこで，両節点の右に示す表には，属性A以外の各ア

ィス上層部の節点を調べるだけで強い相関を検知し，イテムの支持度数を示す．これらの度数から中央の表に示すように各属性毎にβ5S値を計算できる．β55
値が大きいD，Zの属性では，下側節点での支持度数
が［D：y］，［z：n］に偏っており，付加されたアイテ
ム［B：y］とこれらの属性が高い相関を持つことがわ

しかも他の説明変数との関連まで含んだ有効なルールを生成することができる［13］．

図6のルールは，分割表で表現すれば図7で表される．ズ2値が分割表全体を対象とした相関の有無を問題とするのに対し，カスケードモテリレではこの表のB

かる．反対に，属性Cの分布は上下節点でまったく行でのZ値の分布を∑行に示されるZ値の分布と比変化せず，βSS値も0となる．

較し，相関の有無をβS5値として表していることになる．

ところで，図6の上側節点から［B：y］を付加した
n

B
C
D
Z

60
50
60
40

40
50
40
60

l〟SS

24．O
25．O
24．O
24．0

下側節点を次の屑に生成するとき，βSS（B）の値はあ
らかじめ計算できる．他方βS5（Z）の値は，この場合
βSS（B）を上限値とすることが証明されている［13］．

したがって，下側節点におけるZ属性の各アイテム
βSS 血†
B
9．60 0．16
C O．00 0．00
D
6．67 0．11
Z
5．40 0．90

支持度を計算するまでもなく，このリンクからはβ5S（Z）値が10よりも大きなルールを導けない．
この上限値はこれより下部に存在するすべてのリンクに適用できるものではないが，より下層のラティス

n

B
C
D
Z

M／SS

60 0 0．O
30 30 15．O
56 4 3．73
6 54 5．40の近似的な枝狩りに用いることができる．ただし，現
実に表データを扱う場合，この上限値による枝刈りでlF【B：y】addedon【A：y】
THEN【司BSS＝5．40（．40．60）＝＝＞（．10．90）

THEN【D］BSS＝6．67（．60．40）＝＝＞（．93．07）∑ 40 的 100
Z Z ∑ β 6 54 朗） す 34 6 40

図6 リンクからのルール表現

2002年9月号

図7 分割表で見たカスケードモデル© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（7）569

は組み合わせ爆発を防げない．そこで，カスケードモ

ルプリズムと同様に進行する．ただし，（f＋1）層の候デルの適用に際しては別に枝刈り用のβ55値を与え，補グラフは，古層の頻出グラフの対（自分自身と対に

これよりもβ55（B）値が小さいリンクの展開を抑止なってもよい）から（才一1）個の項点を重ね合わせてしてラティスサイズを制御している．

生成する．また，生成される候補グラフ群に同型のものが重複して現れないように，格別の注意が必要であ

6．ラティス意味論の拡張

る．

これまでのすべての説明で，アイテムセットラティ

ここで，特定の頻出グラフで，例えば発ガン性の有スにおける節点間のリンクには，上下両側アイテムセ

無がデータセット全体と比べて大きく有に偏っている

ット間に部分集合関係の存在が前提とされてきた．半ならば，そのグラフに対応する部分構造が化学発ガン

順序関係を前提とした範囲内でも，他の意味をアイテ性の原因となっているのではないか，という・仮説を立ムセット問のリンクに与えることができる．このようてることができる．グラフの種類を化学構造式のような例として，離散時系列とグラフのマイニングを簡単

な色つき無向グラフから，サイクルを持たない有向グに紹介する．

ラフへと換えることにより，購買層歴よりもより一般

相関ルール研究の初期から，各トランザクションに的なネットワークフロー型時系列データのマイニング

購入者IDとタイムスタンプを付した形式のデータがを行うことができる．問題領域毎に異なった意味をラ取り上げられてきた［14］．顧客毎に購入履歴を時系列

ティス中の節点とその間の半順序関係に与えれば，無順にまとめて，例えば［小泉（（b）（b）（a d））］のような

限に豊富なマイニングが可能となる．

上位レベルのレコードを作成する．他方，ラティス内

7．おわりにの節点には（（b）（c））や（（b）（b）（d））のような購買アイ

テムの時系列順のリストを割り当てる．アイテム間の相関ルールは，「何でもアイテム化してバスケット

相対的順序を保った部分列関係がリスト間に存在するに放り込めば分析が可能」という非常に柔軟な方法論

時にのみ，節点間にリンクを張る．このようにすれば，であり，カルテや雑多な社会事象なども取り扱える可（（b）（b））⇒（（b）（b）（d））のようなルールを導くことが能性があることから，今後が大いに期待されている．

できる．これにより，顧客の購買履歴から次にどのよ

反面，まだまだ若い方法論であり，理論面から実装技

うな商品が売れるであろうかという，時系列的な分析術，応用に至るまで多くの課題が山」横している．今後が可能となる．沼尾の解説には，表形式データと組み一層の研究の発展が期待されている．

合わせた要因結果分析も解説されているので参照されたい［15］．

最後に，問題点としてあげながら触れることのなかった，多すぎるルール数の問題を考えてみたい．出力

トランザクションの形式を，さらに複雑なグラフ構

されるルール数を削減する必要は広く認識され，すで造に拡張した例が，Apriori−based graph miningでに多くの研究がなされている．相関ルールを定義通りある［16］．ここでトランザタションとしては，化学構に生成すると，（a）⇒（b c）のルールと並んで（a b）⇒

造式のグラフ表現に発ガン性などの生理活性を付加し（c）のような冗長なルールが現れる．形式的な側面かたものを想定しよう．図8には，この方法で生成されら不要と判断できるルールを削減する研究が多く行わるラティスの一部を示す．ラティス中の才番目の層にれており，実際にルール数を減らすことができる．他

は，項点数fのグラフが格納され，グラフ間に部分同方，節4で述べたcorrelationの意味で有効なルール

型関係が存在する場合にリンクが張られる．頻出グラのみを出力することもルール数の減少に寄与する．さフからなるラティスの生成は，基本的にア7Pリオリア

らにズ2やβ55のように単一の数値でルールの強さに全順序をつけることも，多数の候補からのルール選

a−a

［2］

択を容易にする．また，ルール群を可視化することにa−bより，データの全体的な傾向を把握させる試みも多い．

a＿ a a＿ a a− a
【3］

a

／＼ a

図8 グラフへの拡張
5TO（8）b／

しかし，筆者らの独断ではあるが，ルール数の多さはもっと本質的な問題点に根ざしているかのように思える．例えば，二つのルール（a b）⇒（d）と（a c）⇒（d）が出現し，しかもbとcの間には非常に高い相関が© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

存在する状況が考えられる．この場合，形式的にはこternswithoutcandidategeneration

れらのルールは独立に扱われるべきものであろう．しpp．l−12，ACM（2000）．

，Proc．SIGMOD，【7〕Coenen Fリ Goulbourne G．and Leng P．H．：
Computing association rules using partialtotaIs ，かし，実際はこれらのルールは同じ山を違った方向から見ているにすぎない．

Proc．PKDD，pP．54−66，Springer（2001）．

重回帰分析でdをa，b，Cにより説明しようとする［8］GoulbourneG．，Coenen F．and Leng P．H．： Algor−

ならば，相関の高い説明変数を除くために変数選択のithmsforcomputingassociationrulesuslngapartial

過程が必要となる．単純に計算を進めると，数値的な−SuppOrt tree ，JKnowledde一触ed Systems，Vol・13，

不安定性などの問題を引き起こす．それに引き替え，

pp．141−149（2000）．

ルールの導出では見かけ上何の問題も起こらず，すべ［9］Brin S．，MotwaniR．and Silverstein C．： Beyondては解析者による視察に押しつけた形となっている．

market baskets：generalizing association rules to

多変最解析が長年月をかけて取り組んできた共繰性のcorrelations

問題が，ルール数の多さというまったく違った形で現（1997）．

，Proc．SIGMOD，pp．265−276，ACM［10］Morishita S．and SeseJ．： Traversingitemset
latticewithstatisticalmetricpruning ，Proc．PODS，れてきたのが本質である，と見るべきであろう．このことは問題解決の困難さを予想させるものではあるが，pp．226−236，ACM（2000）．

反面ルール表現を使えば，同一の事象を複数の異なっ［11］Okada T∴ Ruleinductionin cascade model
basedonsumofsquaresdecornposition ，Proc．PKDD，た側面から浮き彫りにできる可能性をも示している．
現在，解析者の横極的なレスポンスをマイニング過pp．468−474，Springer（1999）．

程に取り入れることを重視したアクティブマイニング［12］GiniC．W．：

が注目されている［17］．ルール数の多さを欠点として

Variabilityandmutability，COntribu−

tiontothestudy ofstatisticaldistributions and rela・ではなく，更なる飛躍への踏み台として考える中から，

tions ，5J〟d才放0乃0∽fco−Cf〟わdブcf（ねJ山風肋f〝β和才由

解析者との積極的な相互作用が可能になるものと期待

de CkqlidYi，（1912）．Reviewedin Light R．J．andされる．

MargolinB．H．： AnanalysISOfvarianceforcategor−
icaldata

参考文献，JAmer．Stat．Assoc．，Vol．66，pP．534（1971）．

［1］AgrawalR．，ImielinskiT．andSwamiA．N．：

1ng aSSOCiation rules between sets ofitemsinlarge
databases［2］元田，鷲尾：Efhcient detection oflocalinterac−tionsin the cascade model，Proc．PAKDD，pp．193−，Proc．SIGMOD，pp．207−216，ACM（1993）．203，Springer（2000）．
データマイニング展望 ，システム／制御／［14］AgrawalR．and Srikant R．：

情報，Vol．46，pp．169−176（2002）、

patterns［3］沼尾編： 大規模データベースからの知識穫得 ，人工

Mining sequential，Proc．ICI）E，pp．3−14，IEEE（1995）．

［15］沼尾，清水： 流通業におけるマイニング ，文献［3］，

知能学会誌，Vol．12，No．4，pP．496−549（1997）．
［4］福田，森本，徳山： データマイニング ，データサイエ

pp．528−535．

［16］InokuchiA．，Washio T．and Motod。iI．：

ンスシリーズ3，共立（2001）．

An

apriori−basedalgorithmformlnlng・frequentsubstruc−［5］AgrawalR．and Srikant R．：

Fast algorithmsfor

mlnlng aSSOCiationrulesinlarge databases，Proc．

VLDB，pp．487−499，MorganKaufmann（1994）．

［6］HanJ．，PeiJ，and Yin Y．： Mining frequent pat−

2002年9月号

Min−［13］Okada T．：

turesfromgraphdata，Proc．PKDD，pp．13−23，Sprin・ger（2000）．

［17］Motoda H．（ed．）：

Active mining，IOS press（2002）．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（9）5Tl