ルール評価支援手法における有効な学習モデル構築に必要な最少訓練事例数の見積もり法

ルール評価支援手法における有効な学習モデル構築に必要な最少

訓練事例数の見積もり法

A Method to Estimate Minimum Number of Training Instances for

a Valid Rule Evaluation Models

阿部秀尚

1∗

_津本周作

1

1

_{島根大学医学部医学科医療情報学講座}

1

_{Department of Medical Informatics, Shimane University, School of Medicine}

Abstract: In this paper, we present a method to estimate each minimum number of train-ing instances for constructtrain-ing a valid learntrain-ing model in a rule evaluation support method. In post-processing of data mining process, rule evaluation procedure is one of important and costly procedures, because it requires experties from human experts. To support such rule evaluation, we have developed a support method based on learning model called rule evaluation model. These models should be valid and constructed from smaller training instances to curb learning costs. Therefore, we have evaluated learning costs with accuracies for an entire training dataset and achive rates of sub-sampled training instances. Then, we show case studies on artificial evaluation results and an actual data mining result.

1

はじめに

データマイニングにおけるマイニング結果の後処理 では，専門家によるマイニング結果の評価手続きがデー タマイニングプロジェクト全体の成否を左右する重要 な手続きとして位置づけられている [1]．しかし，専門 家が介在する手続きには，専門家の養成や評価の獲得に 多大なコストがかかる問題がある．さらに，通常，デー タマイニングプロセスは 1 つのデータマイニングプロ ジェクトの中で繰り返し実行される必要がある．また， その繰り返しの中で各手続きも反復して実行される．そ のため，コストのかかるマイニング結果の評価作業も 繰り返し実行する必要があり，データマイニングプロ ジェクトを実行するための全体のコストを大きく引き 上げる． 以上の問題に対し，我々は，マイニング結果のうち IF-THEN ルールを対象にしたルール評価支援手法を 開発してきた [2]．本手法は，専門家のルール評価作業 を客観的指標群に基づくルール評価モデルを用いて反 復的な作業を支援することを目的としている．ルール 評価モデルは，各ルールを評価する客観的指標値と専 門家の評価 (教師信号) を基にルール評価モデルを学習 アルゴリズムにより獲得し，新規ルールの評価ラベル ∗_{連絡先：島根大学医学部医学科医療情報学講座}     〒 693-8051 出雲市塩冶町 89-1      [email protected] を予測することにより専門家のルール評価作業を支援 する (図 1 参照)． 本手法は，ルール評価作業の繰り返しを想定し，専 門家による所与のルール集合の一部の評価からルール 評価モデルを構築して評価ラベルの予測を行うことを 可能としている．しかしながら，ルール評価モデル構 築は，専門家の評価を必要とする点でコストについて の問題が生じる．このため，評価支援に有効なルール 評価モデルを出来るだけ少ない訓練事例によって学習 可能とすることが課題となる． 本稿では，所与のデータ集合での最多評価ラベルの 割合を単純に予測するよりも正確な予測が可能なルー ル評価モデルを有効なルール評価モデルとし，有効な ルール評価モデル構築に必要な最少訓練事例数を見積 もる手法について検討する．

2

有効な学習モデル構築に必要な最

少訓練事例数の評価手法

従来，学習アルゴリズムの性能評価では，再代入エ ラー率/正解率，テストデータ集合を用いたエラー率/ 正解率，交差検定が用いられている．しかしながら，訓 練データ集合の事例数の増減に伴い変化する性能を評 価し，最少訓練事例数を見出すための評価基準は未だ に確立されていない．通常，訓練データ集合の事例数

人工知能学会研究会資料

SIG-DMSM-A603-10 (2/28)

マイニングされた ルールセット

客観的指標値の 計算

Rule ID Accuracy Recall ... Human Expert

ルール評価モデル 訓練データセット 1 2 0.85 0.90 0.14 0.65 Interesting 各ルールに 対する評価 Not Interesting ... ... ... n 0.59 0.01 ... Not Understandable ルール評価モデル 学習アルゴリズム 予測段階: マイニング対象 データセット

Rule ID Accuracy Recall ...

ルール評価モデル の予測対象 データセット new1 new2 0.75 0.88 0.24 0.56 ... ... ... new n 0.95 0.32 ... 領域の専門家 Human Expert Unknown Unknown Unkown 予測結果の 提示 ルール評価モデルによる ルールの評価ラベル予測 構築されたルール評価モデル 訓練段階： 新規の マイニング対象 データセット 客観的指標値の 計算 マイニングされた ルールセット 領域の専門家 図 1: 客観的指標群に基づくルール評価支援手法の概観． が変化する場合，各時点での再代入エラー率/正解率や 交差検定の結果が用いられるが，我々は訓練データ集 合の部分集合を用いて，所与のデータ集合全体に対し て有効な学習モデルを獲得するために必要な最少訓練 事例数を見出す基準が必要だと考えた． まず，我々は，再代入正解率を基準とし，訓練デー タ部分集合による学習モデルの訓練データ集合全体に 対する正解率が単純な最多クラスの予測割合を上回る 時点でその学習アルゴリズムは分類予測に有効な学習 モデルが得られたこととした．訓練データ部分集合と 訓練データ集合全体に対する正解率，有効な学習モデ ルが得られる時点の関係を図 2 に示す． 100 O 100 データ集合全体に対する正解率 (%) 最多クラス の割合 訓練データ部分集合の割合(%) 有効な学習モデルが 得られた訓練データ部分集合 アルゴリズムA 図 2: 有効な学習モデルが得られる訓練データ部分集 合と訓練データ集合全体に対する正解率の関係． さらに，訓練データ集合全体で学習を行った場合に対 する学習達成率を導入することにより，学習アルゴリズ ム間で学習モデルが正確になっていく速度の比較が可 能となる．学習達成率は，訓練データ集合の部分集合の 再代入正解率が訓練データ集合全体を用いて学習した ときに比べてどの程度の性能を達成しているかを次式 のように定義する．ただし，Dtiは ti(0%≤ ti ≤ 100%) の訓練データ部分集合を意味し，D は訓練データ集合 全体を意味する．また，Accuracy は訓練データ集合全 体に対する正解率を意味し，訓練データ部分集合に対 しては N 回の平均をとる． AchieveRate =Accuracy(Dti) Accuracy(D) (1) Accyracy(Dti) = 1 N N  j=1 Accuracy(Dti, j) (2)

3

人工的な評価ラベルによる最少訓

練事例数評価実験

本実験では，客観的にルールを評価する指標群にそ れぞれの値とは関係しないランダムな評価ラベルを与 え，データ集合を作成する．これは，専門家による特 定の評価基準が介在しない場合を想定し，クラス分布 やデータ集合の事例数が有効な学習モデルの構築にど のような影響を与えるかを評価することを目的として いる． はじめに，UCI 機械学習リポジトリー [3] からの 10 データ集合について，bagged PART[5] によって得た

表 1: UCI 機械学習リポジトリーデータから得たルー ル集合に対して生成されたデー集合． L1 L2 L3 (0.30) (0.35) (0.35) anneal 95 33 39 23 41.1 audiology 149 44 58 47 38.9 autos 141 30 48 63 44.7 balance-scale 281 76 102 103 36.7 breast-cancer 122 41 34 47 38.5 breast-w 79 29 26 24 36.7 colic 61 19 18 24 39.3 credit-a 230 78 73 79 34.3 credit-g 450 122 160 168 37.3 diabetes 89 25 37 27 41.6 (0.30) (0.50) (0.20) anneal 95 26 47 22 49.5 audiology 149 44 69 36 46.3 autos 141 40 72 29 51.1 balance-scale 281 76 140 65 49.8 breast-cancer 122 40 62 20 50.8 breast-w 79 29 36 14 45.6 colic 61 19 35 7 57.4 credit-a 230 78 110 42 47.8 credit-g 450 140 213 97 47.3 diabetes 89 25 46 18 51.7 (0.30) (0.65) (0.05) anneal 95 26 63 6 66.3 audiology 149 49 91 9 61.1 autos 141 41 95 5 67.4 balance-scale 281 90 178 13 63.3 breast-cancer 122 42 78 2 63.9 breast-w 79 22 55 2 69.6 colic 61 22 36 3 59.0 credit-a 230 69 150 11 65.2 credit-g 450 135 291 24 64.7 diabetes 89 26 59 4 66.3 クラスラベルの数 最多クラス の割合 分布III 分布II 分布I 生成された ルール数 ルール集合に対し，39 種類の客観的指標 [4] を計算する． これらのデータ集合に対し，多項分布によるランダムな 評価ラベルを 3 種類の分布 (分布 IP = (0.3, 0.35, 0, 35)， 分布 IIP = (0.3, 0.5, 0.2)，分布 IIIP = (0.3, 0.65, 0.05)) で割り当て，表 1 に示すデータ集合を作成した． これらのデータ集合に対し，Weka[6] に実装された J4.8[7]，バックプロパゲーション学習ニューラルネット ワーク (BPNN)[8]，SVM1_{[9]，Classification via Linear}

Regression(CLR)2_{[10]，OneR[11] の 5 種類の学習アル} ゴリズムを適用した．このとき，学習アルゴリズムの 各パラメータは既定の値を用いた． 表 2 に各学習アルゴリズムによる学習モデルの正解 率が最多クラスの割合を越える事例数を示す．各訓練 データ部分集合に対する正解率は N = 10 とし，10 回 のランダムサンプリングによる部分集合による正解率 の平均を用いている． この結果から，分布 I のように均一なクラス分布をも つデータ集合に対して，5 種類の学習アルゴリズムのほ とんどは訓練データ集合の 20%程度で有効なルール評 価モデルを構築することが可能であったことが分かる． 1_{多項式カーネルを用いる．} 2_{AIC に基づく変数追加式選択法を適用した線形モデルによる分} 類． 表 2: 各学習アルゴリズムによるルール評価モデルが 最多クラスの割合を越えるインスタンス数 J4.8 BPNN SVM CLR OneR anneal 20 14 17 29 29 audiology 21 18 65 64 41 autos 38 28 76 77 70 balance-scale 12 14 15 15 32 breast-cancer 16 17 22 41 22 breast-w 7 10 10 18 14 colic 8 8 9 22 14 credit-a 9 12 16 30 28 credit-g 40 49 0 87 84 diabetes 14 10 24 33 20 J4.8 BPNN SVM CLR OneR anneal 29 20 16 42 46 audiology 36 45 - 61 67 autos 49 39 49 123 88 balance-scale 81 84 69 221 168 breast-cancer 31 28 102 40 46 breast-w 14 11 23 30 26 colic 24 20 36 42 36 credit-a 51 74 - 134 109 credit-g 112 245 - 273 275 diabetes 33 25 47 55 54 J4.8 BPNN SVM CLR OneR anneal 54 58 64 76 -audiology 64 73 45 76 107 autos 66 102 84 121 98 balance-scale 118 103 133 162 156 breast-cancer 50 31 80 92 80 breast-w 44 36 31 48 71 colic 28 24 46 30 42 credit-a 118 159 - - 173 credit-g 251 283 353 18 383 diabetes 50 42 60 - 72 分布I 分布II 分布III さらに，訓練データ集合全体が小さい anneal, breast-w, colic においては有効なルール評価モデルを得るために 必要な最少訓練事例数は訓練データ集合の 10%程度と なる．しかしながら，分布 II・分布 III といった不均一 なクラス分布をもつデータセットについては，元の訓 練データ集合の大きさによらず，より多くの訓練事例 が必要であることが明らかとなった．

4

髄膜炎データマイニング結果での

最少訓練事例数評価実験

3 節では，ルールの各客観的指標値とクラスラベル が特定の関係を持たない場合，有効な学習モデル構築 に必要な訓練事例数が訓練データ集合の大きさやクラ ス分布によってどのように変化するかを示した．これ に対し，本節では，ルールの客観的指標値とクラスラ

ベルの間に専門家の評価基準が介在し，何らかの関係 が生じているデータを扱う． 本節では，表 3 に示す髄膜炎データマイニング結果 [12] について，39 種類の客観的指標を計算し，データ 集合を作成する．各ルールの評価は専門家が専門知識 に基づく「ルールの記述する内容の興味深さ」を基準 に 3 種類のラベル (I:興味深い，NI:妥当，NU:理解不 能) を与えた．本実験で用いる学習アルゴリズムは 3 節 と同様に 5 種類である． 表 3: 6 種類の髄膜炎データセットとそれらに対するマ イニング結果． データ名 ルール数 興味深い 妥当 理解不能 Diag 53 15 38 0 C Course 22 3 18 1 Culture+diag 57 7 48 2 Diag2 35 8 27 0 Course 53 12 38 3 Cult find 24 3 18 3 計 244 48 187 9 表 4 に各訓練データ部分集合での正解率 (N = 10) を 示す．この結果，最多クラスの割合 (76.6%) を越える 有効なルール評価モデルを学習するためには，SVM や CLR で 10%の訓練データ部分集合で済むことが分かる． また，BPNN では 20%，J4.8 と OneR では 30%と，よ り多くの訓練事例が必要であることが明らかとなった． 表 4: 各訓練データ部分集合での訓練データ集合全体 に対する正解率．

%training

sample 10 20 30 40 50 60 70 80 90 100

J4.8

73.4 74.7 79.8 78.6 72.8 83.2 83.7 84.5 85.7 85.7

BPNN

74.8 78.1 80.6 81.1 82.7 83.7 85.3 86.1 87.2 86.9

SMO78.1 78.6 79.8 79.8 79.8 80.0 79.9 80.2 80.4 81.6

CLR

76.6 78.5 80.3 80.2 80.3 80.7 80.9 81.4 81.0 82.8

OneR

75.2 73.4 77.5 78.0 77.7 77.5 79.0 77.8 78.9 82.4

4.1

学習達成率による最少訓練事例数の評価

表 4 の各訓練データ部分集合での正解率に対し，学習 達成率を式 (1) に基づいて計算した結果を図 3 に示す． この結果，学習達成率の曲線は右上りの曲線となり， 表 4 で得られた最少訓練事例数よりも大きな訓練デー タ部分集合を用いることによって，より正解率の高い ルール評価モデルが構築可能であることが示された． それぞれの学習アルゴリズムの曲線を見ると，髄膜 炎データマイニング結果に対して超平面モデルを学習 する SVM や CLR といった学習アルゴリズムでは，達 70 75 80 85 90 95 100 0 20 40 60 80 100 Accuracy ratio

on the entire training dataset

%training sample SMO CLR J4.8 OneR BPNN 図 3: 5 種類の学習アルゴリズムの学習達成率． 成率が早く訓練データ集合全体を使った場合の正解率 に近づくことが分かる．一方，有効なルール評価モデ ルの獲得に多くの訓練事例を必要とする J4.8 と BPNN では，学習達成率が緩やかに上昇し，訓練データ集合 全体を使った正解率に到達する．以上のことから，訓 練事例数が少ない段階で所与のデータ集合全体の分類 予測を行う場合は，SVM や CLR など超平面を学習す るアルゴリズムが適していると言える．しかしながら， ルール評価作業の繰り返しによって専門家による評価 が済んだ事例が増加した場合は，J4.8 や BPNN など非 線型の分割をおこなう学習アルゴリズムによってより 正確なルール評価モデルを構築する必要がある．

4.2

交差検定による最少訓練事例数の評価

本節では，髄膜炎データマイニング結果からのデー タ集合において，評価対象とした 5 種類の学習アルゴ リズムからの最少訓練データ部分集合での性能を評価 する． 通常，交差検定では N− 1 : 1 に分割したデータ集 合のうち，N− 1 を訓練データ集合，1 を検証データ 集合とする．しかし，本節ではデータ集合を N− 1 : 1 に分割し，N − 1 を検証データ集合，1 を訓練データ 集合として交差検定を行った (図 4 参照)． 髄膜炎データマイニング結果のデータ集合に対する 5 回繰り返し 10 回交差検定の結果を表 5 に示す．この 結果より，SVM の平均正解率が最多クラスの割合を越 えることが明らかとなった．しかし，これら 5 種類の 学習アルゴリズムから得られた標準偏差の範囲内に最 多クラスの割合が含まれることから，10%の訓練デー タ部分集合に対して最多クラス割合とほぼ同等の正解 率をもつルール評価モデルが構築できると言える． さらに，各学習アルゴリズム間で Corrected repeated

通常の10回交差検定 今回の10回交差検定 データ集合 データ集合 訓練データ集合 訓練データ集合 検証データ集合 検証データ集合 図 4: 訓練データ集合と検証データ集合の割合を入れ 換えた交差検定法． 表 5: 交差検定による各学習アルゴリズムの平均正解 率と標準偏差． J4.8 BPNN SVM CLR OneR 正解率 72.3 73.9 77.1 75.9 75.5 （標準偏差） (6.4) (4.5) (3.2) (3.7) (3.3) k-fold cv test[13] を実行し，統計的に有意な差が生じ ているかについて検定した．検定の結果，5 種類の学 習アルゴリズム間に統計的に有意な差は生じていない ことが明らかとなった． 以上の結果から，髄膜炎データマイニング結果から のデータ集合において，データ集合の 10%程度で，ほ ぼ最多クラス割合と同等のルール評価モデルが構築可 能であることが示された．さらに，4.1 の学習達成率の 曲線から，10% の訓練データ部分集合よりも大きい訓 練データ部分集合では，より高い正解率となるルール 評価モデルが構築可能であると考えられる．

5

おわりに

本稿では，有効なルール評価モデル構築に必要な最 少訓練事例数を見積もる手法について述べた．人工的 な評価ラベルによる評価の結果，学習アルゴリズムが 有効なモデルを構築するためには少ない事例で均等な ラベル分布を持つ訓練データ集合が適していることが 示された．また，専門家による評価を得たデータ集合 では，分類予測に有効な学習モデルはラベル分布が偏っ ているにも拘わらず，訓練データ集合の 10%で有効な ルール評価モデルが構築可能であることが示された．以 上の結果から，専門家の評価基準が確立されている場 合は，マイニングアルゴリズムから得たルール集合の 10%程度を専門家に提示し，評価を得ることによりコ ストを削減することが可能であることが明らかとなっ た．また，人工的なラベル付けが専門家の評価基準を 用いていないことから，専門家の評価基準が確立され ていない段階では，我々が提案するルール評価支援手 法で必要な訓練事例数は少なく済むと言える． 今後は，専門家の評価基準が確立していく過程にお いて適切なルール評価モデルを構築する方法を学習戦 略を含めて検討し，ルール評価作業の繰り返しにおけ る全行程を支援する手法を開発していく予定である．

参考文献

[1] CRISP-DM:[http://www.crisp-dm.org/]

[2] Hidenao Abe, Shusaku Tsumoto, Miho Ohsaki, and Takahira Yamaguchi: A Rule Evaluation Support Method with Learning Models Based on Objective Rule Evaluation Indexes, in Proc. of the fifth Inter-national Conference on Data Mining (ICDM2005), pp. 549-552, (2005)

[3] Hettich, S., Blake, C. L., and Merz, C. J.: UCI Repository of machine learning databases [http://www.ics.uci.edu/˜mlearn/MLRepository.html], Irvine, CA: University of California, Department of Information and Computer Science, (1998)

[4] Ohsaki, M., Kitaguchi, S., Kume, S., Yokoi, H., and Yamaguchi, T.: Evaluation of Rule Interestingness Measures with a Clinical Dataset on Hepatitis, in Proc. of ECML/PKDD 2004, LNAI3202, pp. 362-373, (2004)

[5] Frank, E, Witten, I. H., Generating accurate rule sets without global optimization. Proc. of the Fif-teenth International Conference on Machine Learn-ing, pp. 144-151, (1998)

[6] Witten, I. H and Frank, E.: DataMining: Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann, (2000) [7] Quinlan, R.: C4.5: Programs for Machine Learning,

Morgan Kaufmann Publishers, (1993)

[8] Hinton, G. E.: “Learning distributed representations of concepts”, Proceedings of 8th Annual Conference

of the Cognitive Science Society, Amherest, MA.

REprinted in R.G.M.Morris (ed.) (1986)

[9] Platt, J.: Fast Training of Support Vector Machines using Sequential Minimal Optimization, Advances in Kernel Methods - Support Vector Learning, B. Sch¨olkopf, C. Burges, and A. Smola, eds., MIT Press, pp. 185-208, (1999)

[10] Frank, E., Wang, Y., Inglis, S., Holmes, G., and Wit-ten, I. H.: Using model trees for classification, Ma-chine Learning, Vol.32, No.1 (1998) 63–76

[11] Holte, R. C.: Very simple classification rules per-form well on most commonly used datasets, Machine Learning, Vol. 11, pp. 63-91, (1993)

[12] Hatazawa, H., Negishi, N., Suyama, A, Tsumoto, S., and Yamaguchi, T.: Knowledge Discovery Sup-port from a Meningoencephalitis Database Using an Automatic Composition Tool for Inductive Applica-tions, in Proc. of KDD Challenge 2000 in conjunction with PAKDD2000, pp. 28-33, (2000)

[13] Remco R. Bouckaert, Eibe Frank: Evaluating the Replicability of Significance Tests for Comparing Learning Algorithms, in Proc. of PAKDD 2004, pp. 3-12, (2004)