カスケードモデルによる識別ルールの発見と Datascape Datascape and

カスケードモデルによる識別ルールの発見と Datascape
Datascape and Rule Induction based on Cascade Model
岡 田 孝
関西学院大学 情報メディア教育センター
Abstract. !"#$
"%!"#"
& %%" "% "
&# "" % " % % " &
"##$
#' #
%()#
" *+ "" !"# "" %
""#
1.
はじめに
析者にとっては精度の高いルール群を得られることだけ
最近データマイニング技術が注目を集めている。分
が重要なのではない。他の説明変数群による別の視点か
類を目的とする場合、特徴づけを目的とする場合のいず
らの説明や、説明変数群間の相関関係もデータ全体の理
れにおいても、われわれはすでに十分な精度でルールを
解にとって重要である。この観点からは、共通問題の解
導出することができる。また、そのための環境も、ハー
に対する津本のコメントが参考になる 0-1。
ドウェア、ソフトウェアともに十分整備されている。し
,2. 原データ分布と解の照合。個別原データの分布状況
かし、データ解析をツールとして利用する他の研究分野
を解と照合させながら認識できることが重要である。ズ
において、特にデータ全体の理解を目的とする場合、そ
ーム機能を備えたレンズのように、鳥瞰的な視点、解内
の利用度は統計学と比較して依然極端に低いと言わざる
部のミクロな分布、等を調べられることが必要である 0/1。
を得ない。
上記の３点が、データスケープとして必要なすべて
本報告においてはまず、データ全体の理解を目的と
の点を網羅しているか否かは別として、現状で大部分の
する場合に、データ解析システムが備えるべき要件とし
ルール導出システムはこれらの要件を満たしておらず、
て、データスケープの概念を提唱する。よく利用される
今後とも理解を目的とした研究において、利用度の向上
統計学の方法論には備わっており、多くのルール導出シ
は望めないと思われる。
ステムには不備なものを考えれば、以下の諸点をデータ
スケープの要素としてあげることができよう。
著者らはすでに識別ルールを定量化できるカスケー
ドモデルを報告した 021。このモデルでは相関ルール探
,-. 解と問題の定量化。与えられた解が問題全体の何パ
索で使用される の束に注目する。各 を説
ーセントを解いたことになるのか、把握できることが望
明変数の0%3 1で表し、束を構成する各節点
ましい。特にルール群でデータを説明しようとする場合、
にインスタンスのクラス分布を付加すれば、節点間のリ
各ルール毎の説明力の定量化も必要である。通常行われ
ンクに次式で表す潜在パワーを定義することができる。
るカバーと精度（あるいは "" と ）によ
L− power (U → L) =
(1)
る表現も１種の定量化ではあるが、重回帰分析における
N ( L) ⋅ ( potential (U ) − potential ( D))
全平方和の説明平方和と残差平方和への分解のような意
ここで はリンクの上側および下側節点を表し、,
.
味では、定量化がなされていない。
は下側節点でのインスタンス数を表す。またポテンシャ
,/. データの依存関係。たとえば分類問題において、解
ルとしては、4! やエントロピーを想定する。
他方、根節点におけるポテンシャルとインスタンス
連絡先：岡田孝、関西学院大学情報メディア教育セ
ンター、〒55/4678- 西宮市上ヶ原 -4-4-77
93:##;"
数の積で を定義し、各インスタンスが
束内でとる最低ポテンシャルの和を と
ここで の定義として,6.式を与えるならば、,/.
する。各節点を湖、リンクを滝と見なすと、束全体を１
種の水力発電能力を持つカスケードと見ることができる。
式と全く同じ形式で が各群毎の と に分
クラス識別の問題は、このカスケードからできる限り多
解可能となる（証明は 051 参照）。
くの を説明する少数の滝の群を選択す
BSS g =
ることに帰着される。このモデルによると、選ばれた滝
ng
2
(p (α ) − p(α ))
∑
α
g
2
,
(8)
のパワーの和、各滝のパワー、解くべき問題全体のパワ
この は内容から考えても、リンクのパワーとして
ーおよびカスケード内の滝では説明不可能なパワーが統
用いることが適当であり、さらに束内のすべてのリンク
一的に表されることになる。
間で 値が比較可能であるため、有効なルール選択
本報告では、このカスケードモデルのパワー概念に
の基盤となりえる。実際、,-.式のポテンシャル差による
対して、平方和分解から導出される群間平方和を対応さ
パワー定義では、適切な取り扱いが不能であった図１の
せることにより、モデルをさらに合理的な形に構成でき
例においても、識別力の強い右側のリンクに大きな ることを示す。さらに識別ルールだけでなく特徴的ルー
値が与えられる。
ルをも同時に定式化できるため、上記データスケープを
800/200
よりよく満すルール導出が可能であることを実例に則し
TSS: 160
て解説する。
2.
BSS(1): 18
平方和の分解
連続値を持つ変数を対象とする場合、下記の,/.4,<.
式により全平方和 （&）を各群
760/40
40/160
WSS(1): 38
WSS(2): 32
毎 に 、 群 内 平 方 和 （ = " 図１．平方和分解の例
&）と群間平方和 （>"
&）に分割できることはよく知られている 0<1。
(
TSS = ∑ WSS g + BSS g
g
(
⋅ (x
)
− x)
WSS g = ∑ xa − x g
a∈g
BSS g = n g
g
)
,
(2)
2
,
(3)
BSS(2): 72
上記 の分解は多変数の場合にも拡張できる。ク
ラス変数の を規範としてルールとなるリンクを選
択した場合には識別ルールが得られ、説明変数群に対応
する多変数の 値を規範とする場合は、特徴的ルー
2
.
(4)
この群毎の群間平方和 をリンクのパワーとして採
用すれば、自然であろう。問題はこの定義をカテゴリー
ルが求められることになる。いずれの場合も、問題全体
の のできる限り多くの部分をルール群で説明する試
みであり、その精神において多変量解析の重回帰分析お
よび主成分分析と同じ位置づけを与えることができる。
変数へと拡張することにある。
( 071によると、 は平方和（）
表現が,7.式に変換でき、さらにカテゴリー変数における
距離定義として,5.式を採用するならば、変数値がαとな
る確率 ,α.を用いて,?.式で表現できることを示した。
ここで,?.式の括弧内がいわゆる 4! である。
1
2
SS = ∑∑(xa − xb ) ,
2n a b
 = 1 if xa ≠ xb ,
xa − xb 
 = 0 if xa = xb ,
n
2
SS =  1 − ∑ p(α )  .
2
α

対応し、 としては各インスタンスの束中
における最小 の合計を与えればよい。ただし、束
内で任意に選んだリンク群に対しては、それらの 値の合計が を越える場合があることに
注意する必要がある。
(5)
3.
リンクからのルール表現
値によりあるリンクが選択されたとき、ルール
(6)
としての一般的な表現は以下のように与えられる。ただ
し、各 は0%31の形式で表現される。
(7)
( らはこの,?.式で定義できる の差として
を与え、これに対する仮説検定法を提案した。
なお、 には根節点における が
@ 01
)9A 0 1 ここで、() 部はリンク下位節点上の に含ま
れる を表し、その中で がルールリンクにお
いて付加された として強調されている。
８ルール中からパワーの強い順に 7 ルールを示す。
他方、') 部はパワー定義に用いられた変数群に対
例えば、表１の５番目のルールは次のように解釈す
応する から選択する。クラス変数の をパワ
る。039@31の条件に0351の条件
ーとして採用した場合、結論部はクラス変数値を表す
が加わると、0 3 1の確率が -- ケース中の
となる。また、説明変数群を対象としてパワーを
7<#7Dから < ケース中の 8#8Dに落ちる。このルールの
定義した場合は、これら変数に対応する 群から
潜在パワー（(4）は 8#E< であるが、< ケース中の /
に対する寄与が大きい を選択することになり、
ケースはすでに 4/2 でカバーされているため、この
相関ルールと同様の右辺を与える。
ルールの有効なパワー（94）は 8#<? となる。なお、
ここで注意すべきは、ルールリンク両端の節点記述
このルールで新たに覆われる / ケースからなる節点を想
に現れる 群は () 部のみを指定していることであ
定し、根節点からそこへの直接のリンクを考えた場合、
る。') 部に現れる 群は、節点記述に含まれない
その有効なパワー（'4）は 8#26 である。
に対する両節点上での分布から導かれる。すなわ
全８ルールにより、このデータセット中のすべての
ち、') 部の記述に対応する節点はルール生成には不
ケースをカバーしている。この問題では 必要である。この点、相関ルール探索において0
と は 5#8 と 8#8 であり、最初のルール群
B1 0 B について、'4 と 94 の和を取るとそれぞれ 7#-?
B1の両辺に対応する節点を比較してルールを生
5#2< となる。前者に 4< の下位節点の （8#62）
成することと比較すれば対照的と言える 0?1。
を加えると、 のすべてが説明される。
') 部に記す の選択は、２段階からなる。最
表２には、この問題における９種の説明変数間の特
初に、指定したパラメータ値よりも大きな 要素を
徴的ルール例として、最初のルール群で得られた３ルー
有する変数を選択する。次いで、この変数の取り得る値
ルを示す。') の欄には、,6.式における (4 への寄
の中から,6.式の項中でもっとも大きな寄与を与える変数
与が -#8 以上の を選択して記載した。最後の欄の
値αを選択し、 として記述する。もし、同一の寄与
は (4 の和である。この特徴的ルール発見の問
をなす複数の変数値が存在する場合は、もっとも値の大
題では、 は <-#6- であり、表２の３ル
きな ,α.に相当する変数値αを表示することとする。こ
ールに対する 94 の和は -8#-? であった。リンクに
の選択法により、 ,α.が減少するような負の相互作用も
を加えると、この３ルールだけで の
ルールとして表現できる。
4.
おいて付加された 自身による 94 への寄与：5#-5
DISCAS システムと応用例
カスケードモデルに基づくシステムの構築に当たっ
2EDを説明したことになり、相関の集中していることが
わかる。他方、この３種のルールリンクにおいて、クラ
ス変数に対する 94 の和は //Dを説明するに過ぎず、
ては、束生成時の枝刈り、ルールの選択法に関して多く
燃費との相関は比較的低い。なお、識別ルール・特徴的
の選択肢が存在する。著者は *+ / を作成
ルールの双方において、２番目以降のルール群において
した。紙数の制約により詳細は省略するが、このシステ
も、大きな 値を持つルールが現れており、有効な
ムは以下のような特徴を有している。
知見を与えることが示された。
クラス変数に対する識別ルール、説明変数群間の依存
性を表す特徴的ルール、の双方を同時に生成する。
特徴的ルールの選択においては、 行列のトレー
5.
結論
平方和の分解にもとづき、識別ルールと特徴的ルー
スをパワーとして用いる。
ルを統一的に導出することができた。得られた結果は理
各インスタンスは対応するリンク群から、大きな潜在
解しやすいものであり、データスケープの本質的な要件
パワーを持つものをルール候補として推挙する。
を満たしていると思われる。本報告で提案した平方和の
複数のルール群を生成する。各群はカバーすべきイン
規範は、決定木、相関ルールなど他の方法においても容
スタンスがなくなったとき、ルールの生成を終了する。
易に取り入れることができ、今後ルールによる解析を行
本システムを自動車の燃費データ061に適用した。こ
う場合に参照すべき規範として広く使われることが期待
のデータ中の９種の説明変数群（すべて名義尺度）から
される。
燃費（ 3 CC）を推定することが問
また、マーケットバスケット分析において、例えば
題である。表１に、最初の識別ルール群として得られた
() 部の 数を２個に制限する場合、本報告で示し
[3] Okada, T.: Finding Discrimination Rules Based on
Cascade Model, submitted to J. Jpn. Soc. Artificial
Intelligence (1999). 岡田, 雄山: カスケードモデルに
よる共通データベースの解析、 人工知能学会知識ベ
ース研究会, SIG-KBS-9802-12, 75-82 (1999).
[4] 竹 内 他 編 : 統 計 学 大 辞 典 , 東 洋 経 済 新 報 388-390
(1990).
[5] Light, R.J., Margolin, B.H.: An Analysis of Variance for
Categorical Data, J. Amer. Stat. Assoc. Vol.66 534-544
(1971).
[6] Okada, T.: Sum of Squares Decomposition for Categorical
Variables, to appear in K. G. Studies in Computer Science
Vol.14 (1999). http://www.media.kwansei.ac.jp/home/
kiyou/kiyou99/kiyou99.html
[7] Agrawal, R., Srikant, R.: Fast Algorithms for Mining
Association Rules, Proc. VLDB 487-499 (1994).
[8] Ziarko, W.: The Discovery, Analysis, and Representation
of Data Dependencies in Databases, in: Piatetsky-Shapiro,
G., Frawley, W. (eds.): Knowledge Discovery in
Databases, AAAI Press 195-209 (1991).
[9] Silverstein, C., Brin, S., Motwani, R.: Beyond Market
Baskets: Generalizing Association Rules to Dependence
Rules, Data Mining and Knowledge Discovery, Vol.2 3968 (1998).
[10] Washio, T., Matsuura, H., Motoda, H.: Mining
Association Rules for Estimation and Prediction, in: Wu,
X., Kotagiri, R., Korb, K.B. (eds.) Research and
Development in Knowledge Discovery and Data Mining.
Lecture Notes in A.I. Vol. 1394 Springer-Verlag 417-419
(1998).
[11] Suzuki, E., Shimura, M.: Exceptional Knowledge
Discovery in Databases based on Information Theory,
Proc. KDD-96 275-278 (1996).
た方法によれば、/4 までの束を生成するだけで、
すべての相関ルールを生成することができる。データベ
ースへのアクセス回数が問題となる大規模なデータマイ
ニングにおいて、有効な方法として期待できる。
平方和分解の方法は、χ 検定に基づく方法 0E1 と比
べても、 値がリンク間で比較可能であり、もっとも
強い相互作用を示す変数値の組を直接検出できること、
それらの相互作用のすべてをルール形式で表現できるこ
と、等の点で優れていると考えられる。また、') に
列挙すべきすべての を自動的に表示し、例外的な
知識に大きな 値を与えるため、これまでの研究で
指摘された重要な要件も満たしている 0-8--1。
今後、 の値を利用した有効な枝刈り法や、検定
法についての検討を行う予定である。
謝辞
本研究の遂行にあたり有益な助言を頂いた関西学院
大学の杉原教授、雄山教授、地道助教授に感謝します。
参考文献
[1] 津本: 生成された知識の評価：仮説生成としてのルー
ル生成、人工知能学会知識ベース研究会、SIG-KBS9802-12, 89-90 (1999).
[2] 雄山, 岡田, 李, 李: 知識発見法による探索的データ
解析, 計算機統計学, Vol.9, 1-12 (1997).
Table 1. 自動車の燃費推定問題における識別ルール例（解説は本文を参照）
A
/
2
<
7
""
F3%"
3
35
39@G"3 F3"
3<G%3
35
39@G3
')
,D.
""
3 26#-3-88
/-35
/#88
/#88
/#88
3
E#73-88
/-3/
-#/<
-#/<
-#/<
3
/6#53-88
?3/
-#8/
-#8/
8#26
3
<7#7362#2
--35
8#65
8#65
8#<7
3 7<#738#8
--3<
8#E<
8#<?
8#26
(
9
'
Table 2. 自動車の燃費推定問題における説明変数群間の特徴的ルール例（解説は本文を参照）
A
/
2
""
"3
"3 %3
"3
3<
"3 35
"3
,D.
55#?3-88
7/#<366#E
27#2368#8
7/#E3-88
4
4
')
""
/-3E
-?37
/-3-/
(
-#88
-#/8
-#88
-#--
'
-#88
-#/8
-#8E
8#E/
4
4
<#22
2#E<
2#/7