The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

1F1-02

定量的相関規則クラス分類手法とその変異原性データへの適応
Development of a Classifier by Using QAR Analysis and Application to Mutagenesis Datasets
中西 耕太郎∗1

鷲尾 隆∗1

藤本 敦∗1

元田 浩∗1岡田 孝∗2

Koutarou Nakanishi

Takashi Washio

Atsushi Fujimoto

Hiroshi Motoda

Takashi Okada∗1

大阪大学産業科学研究所高次推論方式

Department of Advanced Reasoning, Osaka University. The Institute of Scientific and Industrial Research∗2

関西学院大学理工学部

Department of Informatics, Kwansei Gakuin University

The present association-rule-based classifier needs pre-discretization of a dataset that includes numeric attributes. In this paper, we propose a new approach based on an association-rule-based classification method
called CAEP[Dong99] and QAR mining by Monotonic INTerval[Washio04] developed in our previous work. It
can directly and completely mine significant combinations of attributes for classification from datasets consistingof many categorical and numeric attributes and derive a classification rule set based on the combinations. The
result of our classification shows better performance than the results of conventional approaches. The applicationof the method to mutagenesis datasets has been made to get knowledge that is benefit for experts in the domainof quantitave structure-activity relationship(QSAR) analysis.

1.

はじめに

能性がある．しかし，これらの分類手法は数値を含むデータを扱う際に何らかの記号離散化前処理を必要とし，数値を含むデータを直接的に解析することができない．この方法では，次に述べるように離散化の際の区間境界が不適切だと，属性やその値同士の共起性を多頻度アイテム集合としてうまく捉えられない場合を生じ，それが分類規則の精度向上を阻む可能性がある．相関関係を用いる分類手法は高性能の分類規則を作り出す可能性を秘めているが，前述の欠点によって広範囲の適用が阻まれている．また数値属性の離散化については Srikant とAgrawal が「catch-22」[Agrawal96] と呼ばれる２つの問題を述べた．１つは，数値データの離散化幅が狭すぎると１つ１つの区間に含まれる要素数が少なく，支持度が低くなってしまう「最小支持度問題」である．そのため，最小支持度を下回らないようにある程度以上の粒度で離散化する必要がある．もう１
つは，離散化幅が広すぎると支持度は増加するが属性やその値間の共起性を捉える粒度が粗くなりすぎて，確信度が低くなってしまう「最小確信度問題」である．そのために最小確信度を下回らないように離散化幅を狭くする必要がある．
この問題を解決するために多くの研究が行われてきたが，何れも数値を含むトランザクションデータに関する実用的な最適相関ルールを現実時間で求めることができない．そこで，我々は現実的な時間計算量で属性やその値の間の共起が多頻度になる各数値区間とそれらの多頻度アイテム集合を同時に完全探索する QAR mining by Monotonic INTerval（QARMINT）[Washio04] という手法を提案した．
我々は QARMINT に前述の CAEP と呼ばれる相関関係に基づく分類手法を適用することにより，数値属性を含むデータに関する新たな相関規則に基づく分類手法（CAQEP）[中西 05]を開発した．この手法は前述の相関関係を分類に用いる手法の利点に加え，数値属性を含むデータから共起性を捉える数
値属性離散化区間を直接的に導出して分類規則に反映することにより，従来の分類手法には無い種々利点を有する．当報では CAQEP を変異原性データに適応し，生成された分類規則
より専門家にとって有益な知識を導出することを目的とする．

データマイニングの分野においては，クラスと呼ばれる目的
属性を含む大量のデータから，クラスを予測する分類規則を作成するクラス分類問題に関する手法の研究開発が主流の 1 つになっている．特に近年，相関規則集合に基づいて分類を行う
手法の研究が盛んになっている．従来の分類手法はアイテム間の相関関係を用い，高い精度の分類規則を作成できる．その初期の研究としては Liu，Hsu，Ma による相関規則の supportと confidence を用い最も優先度の高い相関規則を分類に使用する CBA[Liu98] がある．この手法では各クラス値を持つ事
例数によって相関規則の数に差が出来てしまい事例数の少ない
クラスについて正確な分類が出来ないという問題がある．この問題を解決するために Dong，Zhang，Wong，Li によってCAEP[Dong99] と呼ばれる手法が開発された．この手法ではあるクラス値についてのみ多頻度でかつ他のクラス値の事例においては相対的に多頻度でない属性集合である Emerging
Pattern（EP）を分類に用いる．この他にも Apriori アルゴリ
ズムに比べ，大量のデータや属性数の多いデータに対してより短い時間で相関規則を導出できる FP-growth と呼ばれるアル
ゴリズムを用いた CMAR[Li01] といった手法も開発されている．これらの相関関係を分類に用いる手法の主要な利点には次が挙げられる，1. 多数の属性を含むデータから分類に有用な属性の組み合
わせを自動的に完全導出できること．
2. 少数例のクラスに対する分類規則を網羅でき分類精度を落とさないこと．
3. パラメータの設定により過学習を起こり難くできること．
これらの理由で相関関係を分類に用いる手法は，C4.5 をはじめとする従来の手法に比べ高い精度の分類を達成できる可連絡先: 大阪大学産業科学研究所〒 567–0047 大阪府茨木市美穂ヶ丘 8-1
E-mail: nakanishi@ar.sanken.osaka-u.ac.jp1

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

2.

CAQEP

2.1

多頻度アイテム集合と多頻度領域

itemj



本 節 で は QARMINT に お け る 多 頻 度 ア イ テ ム 集 合 と多頻度領域について述べる．あるデータベース D において ，最 小 支 持 度 を 超 え る 頻 度 で 各 ト ラ ン ザ ク ション に 共起 す る ア イ テ ム 集 合 を「 多 頻 度 ア イ テ ム 集 合（frequent
itemset）」と呼ぶ．上記 Apriori アルゴリズムを数値アイ
テムの数値情報を含めて多頻度なアイテム集合を探索できるように拡張する．ここで，記号アイテムは記号属性 Asiと そ の 値 vsi の ペ ア hAsi , vsi i，数 値 ア イ テ ム は 同 様 に ，hAni , vni i と表されるものとし，従ってトランザクション t ={hAs1 , vs1 i, ..., hAsns , vsns i, hAn1 , vn1 i, ..., hAnmn , vnmn i}と な る ．次 に ，各 数 値 ア イ テ ム の 値 vni を 無 視 しt† = {hAs1 , vs1 i, ..., hAsns , vsns i, hAn1 i, ..., hAnmn i} とする．このような変換を施したデータに対して最小支持度を越える多頻度アイテム集合 f を探索する．次に，得られた fに含まれる全ての数値属性 Ani に注目し，f を含む各トラン
ザクション t の持つ数値属性の値 vni が密集している区間を抽出する．つまり，ある密集基準を満たし
V|{t| ∀An ∈f li ≤ vni ≤ ui , f ⊆ t}|i≥ minsup
|D|

j








iitemi（１）密集している場合
itemj

j

 
i

itemi

（２）密集していない場合を満足する領域を抽出すればよい．ただし li < ui ，Ani ∈ f
である．これによって得られた範囲を本稿では「多頻度領域（frequent region）」と呼ぶ．
多頻度領域を探索するためには，トランザクションが密集していると判断する基準が必要である．そこで本稿では，各数値
属性 Ani ごとに「それぞれのトランザクション t の持つ数値
属性の値 vni 同士が特定の値 ∆i より離れていなければ密集しているとみなす」という基準を設定する．この ∆i を数値属性
Ani に関する「許容距離（permissible range）」と呼ぶ．そして，多頻度アイテム集合に含まれる全ての数値属性に対して許容距離 ∆i 以内であるトランザクション同士を全て結合する．
即ち，トランザクション t の近傍集合 Ef (t) を

図 1: itemi , itemj における多頻度領域

Ff = {Cf ||Cf |≥ minsup}|D|

Idf = { [min(vni ), max(vni )] | Ani ∈ f }
t∈Ff

t∈Ff

例として 2 種類の数値アイテム itemi , itemj の多頻度領域を求めると図 1 のようになる．ただし，最小支持度は 4 とする．
図におけるそれぞれの点をトランザクションとすると，（１）では各数値アイテムに対して許容距離 ∆ 以下であるトランザク
ションを結合してゆけば多頻度集合の候補の要素数は 5 となる．よって，最小支持度を上回るので図のような長方形の多頻度領域が得られる．また，（２）においてはトランザクションの結合はなされるが，多頻度集合の候補の要素数が 3 であり，最小支持度を下回るために多頻度領域は得られない．

Ef (t) = {t0 ∈ D| ∧∀ Ani ∈f |vn0 i − vni | ≤ ∆i } ∪ {t}として，すべての t について求まった近傍集合 Ef (t) の集合
を ESf とする．但し，hAni , vni i ∈ t である．ここで，任意の Ef (ti )，Ef (tj )（ ∈ ESf ）の積集合が空集合でないとき，「Ef (ti ) と Ef (tj ) は直接結合している（directly connected）」と呼ぶ．また ESf について，任意の Ef (ti )，Ef (tj ) に対して

2.2

多頻度領域抽出アルゴリズム

本節では QARMINT によって多頻度領域を抽出するアルゴ
リズムについて述べる．まず属性数が 1 の多頻度アイテム集
合 Ff (1) の多頻度領域抽出法を述べる．多頻度アイテム集合が記号のみからなる場合，そのアイテムに関してはこの処理はしなくてよい．数値アイテムである場合は，それぞれの数値属性
Ani に対応する許容距離 ∆i を用いて近傍集合を生成し，多頻度領域を抽出する．この多頻度アイテム集合における多頻度領域を抽出するために最も計算時間を要する部分はクイックソー
トであり，計算時間は N = |D| とした時に最悪 O(N log N )である．
属性数が 2 つ以上の多頻度アイテム集合 Ff (l) (l ≥ 2) の多頻度領域を探索するには，単一属性のみに密なだけでなく関連する全ての数値属性に関して値が密な必要がある．このとき支持度の単調性より，Ff (l) に含まれる数値アイテムからなる任意の集合のうち 1 つでも多頻度領域を持たないものがあれば，その Ff (l) は多頻度領域を持たない．よって，Ff (l) に含まれEf (t1(i→j) ), Ef (t2(i→j) ), ..., Ef (tm(i→j) )が存在し，Ef (ti ), Ef (t1(i→j) ), ..., Ef (tm(i→j) ), Ef (tj )がこの順序で直接結合している場合，「Ef (ti ) と Ef (tj ) は結合している（connected）」と呼ぶ．この近傍集合の集合 ESf をもとにして得られる極大な多頻度集合の候補 Cf は
Cf = {Ef (t) ∈ ESf |Ef (t)s are mutually connected in ESf }となる．このような Cf は ESf から複数得られる．これによって生成された多頻度集合の候補 Cf に含まれる要素数が最小支持度以上であるとき，それを多頻度集合 Ff と呼び，Ffにおける各数値属性 Ani の最大値と最小値で囲まれた範囲が多頻度領域 Idf となる．

2

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

2.3

る全ての数値属性が張る空間上で前述の Cf を直接求めるよりも，l = 1 から始めてボトムアップ的に最小支持度未満の多頻度領域の候補を切り捨てながら多頻度領域を生成した方が効率が良い．そこで，我々は数値アイテム集合に関して Apriori
アルゴリズムで多頻度領域を生成する手法を用いる．
まず，ある要素数 l の多頻度アイテム集合 Ff (l) に含まれる属性の集合を f (l) とすると，f (l) に含まれる全ての属性 Aniについて ∆i 以内の間隔に密集した 1 次元（属性数 1）の多頻度領域を求める．これによって生成された各数値属性ごとの多頻度領域をもとに，以下のように複数の数値アイテムを組み合
わせてゆき，l 次元（属性数 l）の多頻度領域を生成する．
まず，l 次元の Ff (l) を生成するには，l − 2 次元の要素が共通な l − 1 次元の２つの多頻度集合 Ff (l−1) ,Ff 0 (l−1) (|f (l −1) ∩ f 0 (l − 1)| = l − 2) を用い，f (l) = {f (l − 1) ∪ f 0 (l − 1)}
として Ai ∈ f (l) である全ての数値属性 Ani について一次元の多頻度領域を求める．ここで，f (l) 内の各数値アイテム Aniの多頻度領域 Id{Ani } は前述の通り複数存在しえるので，そsupCi (e) =growth rate(e) =8< supCi (e)sup¬C (e)する {Id{Ani } } の直積: ∞⊗Ani ∈f (l){Id{Ani } }i(sup¬Ci (e) 6= 0)(sup¬Ci (e) = 0,

supCi (e) 6= 0)

上記 Ci と e について growth rate と support が閾値を上回った場合，e を Ci を導く EP（Emerging Pattern）と呼ぶ．尚，
growth rate の閾値は 1 より大きい値とする．e を含むトラン
ザクションは Ci である可能性が高いので e ⇒ Ci という相関規則が導出される．下記の式によってこのような相関規則の確信を表す指標である aggregate score を求める．尚，growth rateの閾値は 1 より大きい値とする．

をとりその各要素に番号 mf (l) (= 1, ..., |P Idf (l) |) をふる．更に，P Idf (l) の各要素は f (l) に関する多頻度領域である可能性を有するのでそれらを多頻度集合の候補 If (l)mf (l) とする．このとき，If (l)mf (l) の要素数が最小支持度未満のものは切り捨
てる．こうして生成された If (l)mf (l) は多頻度集合であるが，1 次元増えたため内部に含まれるトランザクションの分布が疎になる場合がある．そのために多頻度集合かつ密集している部分を探索する．密集した部分を探すためには，2.1 節と同様に If (l)mf (l) において f (l) に含まれる各数値アイテム Ani に関して許容距離 ∆i 以下であるトランザクション t の近傍集合
Ef (l)mf (l) (t) すなわち

aggregate score(e) =growth rate(e)∗ supCi (e)growth rate(e) + 1

各分類対象クラス Ci に対応する EP の集合を E(Ci ) とし，
Ci に存在する全てのクラスが既知である t について E(Ci ) に
属し t に含まれる EP の aggregate score の総和を t の Ci に対する score とする．その定義は下の通りである．

Ef (l)mf (l) (t)=|{t ∈ Di e ⊆ t}||Di |今，クラス Ci について Ci 以外のクラスラベルを持つデータに ¬Ci という新たなクラスを何与する．次にアイテム集合 eについて対象クラス Ci がクラス ¬Ci に対して相対的に多頻度であることを示す指標である growth rate を以下の式で計算する．

の集合を {Id{Ani } } とする．そして，全ての Ani ∈ f (l) に関

P Idf (l) =CAEP

CAQEP では，QARMINT によって各分類対象クラス毎に得られた多頻度集合について，CAEP と呼ばれる手法を用いて分類規則を生成する．まず得られた多頻度アイテム集合について，各クラスを持つデータの中で多頻度アイテム集合を含むデータの割合（support）を求める. あるクラス Ci に属するデータ t の集合を Di としてアイテム集合 e についてのsupport を以下の式で計算する．

score(t, Ci ) =0{t0 ∈ If (l)mf (l) | ∧∀An ∈f (l) |vn− vni | ≤ ∆i }}iΣe⊆t,e∈E(Ci )aggregate score(e)i

各 Ci 毎に score 値のスケールが異なるので，score の規格化のために Ci の EP を持つトランザクションの score のメディ
アンを，その Ci の base score とし，score の正規化に用いる．
こうして得られた EP と base score を用いてクラスを分類する．クラスが未知のトランザクション t が各分類対象クラス Ci を持つ確信を表す指標として，以下のようにその tに含まれる EP の score の総和を base score で割ったものをnormalize score とする．

を求めればよい．これを If (l)mf (l) に含まれる全てのトランザクションに対して行い，近傍集合の集合を ESf (l)mf (l) とす
る．この近傍集合の集合 ESf (l)mf (l) をもとにして得られる多頻度集合の候補 Cf (l)mf (l) はCf (l)mf (l) = {Ef (l)mf (l) ∈ ESf (l)mf (l) |Ef (l)mf (l) s are mutually connected in ESf (l)mf (l) }となる．このような Cf (l)mf (l) は ESf (l)mf (l) から複数得ら

normalize score(Ci ) =れる．これによって生成された多頻度集合の候補 Cf (l)mf (l)ratio score(Ci )base score(Ci )全てのクラスについて normalize score を求め normalize score
が最大のクラスにトランザクションを分類する．

に含まれる要素数が最小支持度以上であるとき，それらの各
Cf (l)mf (l) における各数値属性 Ani の最大値と最小値で囲まれた超直方体の範囲を多頻度領域 Idf とする多頻度領域 Ff (l)が導出される．上記を，l を 1 つずつ増やしながら反復する．
このアルゴリズムで最も時間計算量を要するところは近傍集合を求める部分である．各近傍集合を求めるために各トランザ
クションの数値アイテムの値を比較するため，トランザクショ
ン数を N とすると，時間計算量は最悪 O(N 2 ) である．しかし実際は全トランザクションが同じ数値アイテム集合を含み，かつ密集しているということは少なく，O(N 2 ) より少なくなる．

3.

性能評価実験

本報で用いる CAQEP を，UC Irvine Machine Learning
Repository に公開されているデータを用いて 10 fold crossvalidation を実行し，従来のクラス分類手法と性能比較した．
その結果を下の表 1 に示す. 提案手法は実験の結果，Pima を除くデータについて従来の手法を超える分類精度を達成することに成功した．

3

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

表 1: 本手法と他手法との性能比較
データ名
Pima
Heart
Iris
Wine
Hepatitis
Ecoli

データ数
768
270
150
178
155
336

属性数 (数値属性数)
8(8)
13(6)
4(4)
13(13)
19(6)
8(7)

クラス数
2
2
3
3
2
8

NB
.759
.8222
.8392
-

PEOE PC+PEOE PCPEOE RPC+PEOE RPCvdw area
vdw vollogP(o/w)

meaning
The largest entry of A
If ri is the largest entry in row i of A,
then the radius is defined as the smallest value of ri
Sum of the positive pi
Sum of the negative pi
Magnitude of the largest positive pi
divided by the sum of the positive pi
Magnitude of the smallest negative
pi divided by the sum of the negative pi
The area of the van der Waals surface
Van der Waals volume
Log of the octanol/water partition coefficient

5.

CBA
.7303
.8187
.929
.916
.802
-

LB
.7577
.8222
.845
-

CAEP
.75
.8370
.9467
.9711
.8303
-

CAQEP
.669
.8444
.9667
.9722
.852
.831

むすび

本研究では数値アイテムを直接的に扱える相関関係を用いた分類手法をプログラム実装し，UC Irvine Machine Learning
Repository に公開されているデータを用いて性能評価実験を行った．その結果，幾つかのデータによって従来の分類手法を越える分類精度を達成した．また，提案手法を変異原性データに適応し，得られた相関規則から専門家にとって有益な情報を抽出することに成功した．今後取り組むべき課題としては，使用メモリの低減や計算の高速化が挙げられる．

表 3: クラス値とその領域
class
inactivelow
medium
high

TAN
.7577
.8333
-

radius，PC の相関が高い．即ち，疎水性であり，分子のサイズが小さく，電荷の分離も小さめである場合に変異原性が低いという示唆が得られる．
』という知見が述べられた．これより提案手法によって，専門家にとって有益な知識を導出することに成功したといえる．

表 2: 使用する属性
descriptor
diameterradius

C4.5
.711
.7669
.953
.927
.8
.824

regionactivity = -99-99 < activity < 00 ≤ activity < 33 ≤ activity

参考文献[Liu98] B.Liu, W.Hsu, Y. Ma, Integrating Classification and Association Rule Mining. SIGKDD, pp, 80-86 (1998)

4.

変異原性データからの知識獲得[Dong99] G.Dong, X.Zhang, L.Wong, J.Li: CAEP:Classification
by Aggregating Emerging Patterns, Int’l Confidence on Discovery Science, pp, 30-42 (1999).

これまでに変異原性と発癌性は高い相関関係を持っていることがわかっている．しかしながら，変異原性データの数が多
いため，専門家の考察によって変異原性を誘発する化学的条件を網羅的に抽出することが困難であった．そのため網羅的なデータの評価が望まれる．提案手法を変異原性データに関するHP[Mutagenicity00] に公開されている MOE データに対して適応し，その結果得られた相関規則より専門家にとって有益な知識を得るという実験を行った．MOE データはデータ数が230，属性数が 102，それら全てが数値属性であるが実験に使用した計算機のメモリの制約上，専門家から意見を聞き表 2 に記された重要属性に限定した．また提案手法は数値属性を直接的にクラス属性として取り扱うことができないので，専門家の意見に従い activity という数値属性を離散化し，クラスとした．各クラス値の activity 領域を表 3 に示す．提案手法によって得られたクラス inactive に関する相関規則の例を下に示す．

[中西 05] 中西 耕太郎，鷲尾 隆，藤本 敦，元田 浩: 定量的相関規則を用いたクラス分類手法の開発，第 69 回知識ベースシステム研究会，pp，143-150 (2005).
[Agrawal96] R.Srikant and R.Agrawal, Mining Quantitative Association Rules in Large Relational Tables, Proc. of the 1996
ACM SIGMOD International Conference on Management
od Data, pp. 1-12 (1996).
[Washio04] T.Washio, A.Fujimoto and H.Motoda, Extention ofBasket Analysis and Quantitative Association Rule Mining,
人工知能学会 知識ベースシステム研究会（第 67 回）SIG-KBSA403, pp. 117-122 (2004).
[Li01] W.Li, J.Han, J.Pei, CMAR:Accurate and Efficient Classification Based on Multiple Class-Association Rules, IEEE
Int’l Conf. on Data Mining, pp, 369-376 (2001)

例 1:[Mutagenicity00] http://www.clab.kwansei.ac.jp/mining/datasets/PAKDD2000/okd.htm,
Mutagenicity data descption.

logP(o/w):[1.69 - 2.63]⇒class:inactive[support=0.63,growth rate=4.01,aggregate score=0.50][UCirvine] http://www.ics.uci.edu/˜mlearn/MLRepository.html, University of California Irvine Machine Learning
Repository

例 2:

PEOE PC+:[0.65 - 1.11], PEOE PC-:[-1.11 - -0.65] ⇒ class:inactive[support=0.72, growth rate=1.46, aggregate score=0.432]

これらの相関規則に加え，クラス inactive においていくつかの aggreegate score の値が高い相関規則について，専門家から『クラス inactive に関しては Log，vdw area，vdw vol，4