博士 （情 報科 学） 設樂洋爾

学位論文題名
Descriptiv
eDecisionRu
leMiningforRev
ealingMultipleAspectsofDatabases（デ ー タベ ー スの 多 面的 な 解 釈を 与 える
記述的決定規則ルールマイニングに関する研究）

学位論文内容の要旨
デ ー タ ベ ー ス か ら 知 識 を 発 見 す る 技 術 と し て 、 デ ー タ マ イ ニ ン グ 、 あ る い は KDD (KnowledgeI冫 iscoveづ洫 Datab謎 e） と 呼ば れ る 技 術 が注 目 を 集 め てい る 。 と りわ け、デ ータ ベース に潜在 するパ タ ー ン を mm曲 型 の ル ー ル と し て 取 り 出 す ル ー ル 抽 出 手 法 は 、 分 析 者 が 解 釈 し や す い 知識 表 現を与 え得 るため 、知識 発見に おいて 重要 な役割 を果た す。
本 研 究 で は 、 ル ー ル 結 諭 部 の 属 性 が 固 定 さ れて い る 場 合 、す な わ ち 決 定規 則 ル ー ル の 抽出 を 扱う 。 あ る特 定 の 決 定 属性 （ ク ラ ス 属 性） が 複 数 の 説明 属 性 に よ って ど の よ う に説 明 さ れ るか をル ー
ル 「 Aな ら ば B」 の 形 で 表 現 す る 。 決 定 規 則 ル ール を 得 る 手 法は こ れ ま で も広 く 研 究 さ れ てお り 、様 々 な 手法 が 提 案 さ れて い る 。 し か し、 従 来 の 決 定規 則 ル ー ル 抽出 に お い て は、 知 識 発 見に 貢献 する ル ー ルを 求 め る よ りも 、 未 知 の イ ンス タ ン ス に 対し て 精 度 よ い予 測 を 行 う ルー ル の 抽 出に 主眼 が置 か れ てい た 。 従 っ て、 従 来 の 方 式 では ル ー ル 集 合の 予 測 あ る いは 識 別 性 能 が高 く な る よう な基 準が 設定さ れ、そ の基 準を最 大化す るノレ ．ー ルが探 索され ていた 。しか し、 探索は ヒュー リステ ィク スに 基 づ ぃて 行 わ れ る ため 、 ル ー ル 抽 出の 手 続 き を アル ゴ リ ズ ム の形 で 定 義 で きて も 、 そ れに よっ て得 ら れ る ル ー ル 集 合 の 性 質 に っ い て は 陽 に 定 義 を与 え る こ と が でき な い と い った 状 況 で あ った 。
従 来 の 多 く の 決 定 規則 ル ー ル 抽 出手 法 は Sep
arate
一 紐 dlC
冊 quer型あるいはDivide
I孤 dlC
onquer型 に 分 類さ れ る 。 Sep缸 ate― and・ C
onque
r型 で は 、ま ず ル ー ル を ーつ 求 め 、 そ のル ー ル に よって 被覆 さ れ る イ ン ス タ ン ス をデ ー タ か ら 削除 し 、 そ こ か ら次 の ル ー ル を生 成 す る 。 一方 、 DMde− 孤 d一C0nqucr型 で は 、 イ ン ス タ ンス の 空 間 を クラ ス の 分 布 がお よ そ 均 ー にな る ま で 、 再 帰的 に 分 割 を 繰り 返 す 。決 定 木 に 基 づく ル ー ル 抽 出 手法 は こ れ に あた る 。 こ れ らの 方 式 に 共 通す る 問 題 点と して 、sp】intedD
gp
r obleIで（分化問題）が指摘されている。これは、ルールの生成が進むにっれて使用でき る イ ンス タ ン ス の 数が 減 少 し て い くた め 、 は ず れ値 で あ る よ うな イ ン ス タ ンス を 無 視 でき なく なり 、 ま たノ イ ズ に 敏 感に な り 過 ぎ る とい う 指 摘 で ある 。 ま た 、 ルー ル は ル ー ル集 合 を 探 索す る過 程で 順 次 追加 さ れ て い くた め 、 得 ら れ るル ー ル が そ の探 索 の コ ン テキ ス ト に 依 存す る と い う問 題も ある 。 こ れは 、 デ ー タ ベー ス の 解 釈 を 行う た め の ル ール を 抽 出 す ると い う 観 点 から は 望 ま しい 性質 ではな い。
ル ー ル 抽 出 手 法 の 適 用 可 能 性 に も 注 意 が 必 要で あ る 。 ル ール 抽 出 の 対 象と な る デ ー タ ベー ス には 、 多 くの 場 合 、 数 値属 性 や 順 序 属 性、 カ テ ゴ リ カル 属 性 が 混 在す る 。 実 問 題へ の 適 用 を考 慮す ると 、 こ れら 多 種 の 属 性を 統 一 的 に 扱 える こ と が 望 まし い 。 ま た 、多 く の 値 を とる カ テ ゴ リカ ル属 性― 785ー

が データベースに含まれる場 合に、ルール前提部で属性値をーつしか指定できない手法では、ルール が細分化し過ぎるという問 題もある。このような場合には、属性値を適切に纏め上げ、ルール前提 部で属性値集合を指定することで、一般性を保っことができると考えられる。加えて、デ丶I一タベ ースにはしぱしぱ欠損値が 含まれる。よって、欠損が含まれる場合でも適切なルールの抽出が行え ることが望ましい。
本研究では、これらの問題 意識のもと、決定規則ルール 抽出手法を以下のように構 成した。まず 、抽出すぺきルール集合を、部分クラス法(Kudo etal.，1993)の枠組みに基づぃて「無矛盾性」と 「極大性」の観点から与え られた同一決定属性を持っインスタンス集合の部分集合族（部分クラス 族）として定義する。カテ ゴリカル属性、順序属性、数値属性を同時に扱えるようすべての属性値 をべき集合の枠組みで扱う 。次に、部分クラス族の（被覆が大きいなど）性質の良い部分集合を確 率アルゴリズムによって計 算コストを抑えて求める。ルールの抽出は無矛盾性を維持しながら、可 能な限ルルールを一般化し ていくことで行う。このとき、各々のルールは既に得られているルール 集合には依存せず抽出され る。その結果、ルールはデータを多面的に被覆し、多様な属性で説明す るものとなる。計算機実験 により提案ルール抽出法にて実データから解釈のしやすいルールの抽出 が行えることを確認した。
さらに幅広い問題に適用可 能にするため、属性がアイテム集合で表現されるトランザクション型の データベースからのルール 抽出に関しても検討を行った。例えぱ、表型のデータベースや、テキス トデータもアイテム集合へ と変換することができる。属 性値としてアイテム集合が 与えられる
場 合でも、アイテム集合から 無矛盾性を維持してアイテム集合の一般化を行うことで、表型データベ ースの場合と同様の枠組み でルールの抽出が行えることを確認した。また、提案ルール抽出手法
を As
socia
tiveClassifierの枠組みで捉えると、従来のClass Ass
ociat
ion R
uleを用いる方式では抽出 が難しい、低サポート高コ ンフィデンスのルールを抽出する手法とみることができる。実際に識男 I亅 子 を 構 成 し 、 計 算 機 実 験 に よ り 良 好 な 識 別 性 能 が 得 ら れ る こ と を 確 認 し た 。
提案ルール抽出手法の特長 を以下にまとめる。
・ 未知インスタンスを予測するためのルール抽出に主眼を置くのではナょく、データの解釈を行うため のルールを抽出することが できる。
・ 抽 出 さ れ る ル ー ル の性 質が アル ゴリ ズムの 基準 から 陽に定 義さ れる 。
。 既に得られているルール集 合に依存してルールを決定するのではなく、ルールーつーっを独立して 抽出するため、多様なルー ルを抽出できる。
・ 数 値属 性、 順序 属性 、カ テゴ リカ ル属 性が 混在 して いる デ ータ を統一的に扱える。
・ カ テ ゴ リ カ ル 属 性 の属 性値 をグ ルー ピング した ルー ルが発 見さ れる 。
・ データベースに欠損値が含 まれる場合でも適切に扱える 。
本研究における成果は、決 定規則ルール抽出においてデ ータペースの特徴を表現す る記述的なル ールを求める手法を提案し たことにある。提案手法は数値属性、順序属性、カテゴリカル属性の混 在するデータベースに対応 し、またカテゴリカル属性については属性値のグルーピングを自動で行 うことで解釈しやすいルー ルを効率良く抽出することができる。計算機実験により、提案法が実デ ータに対しても有効に働く ことを確認した。

― 786―

学 位論文審査の要旨
主査

教授

工藤峰一

副査

教授

宮腰政明

副査

教授

原口副査

准教授

中村篤祥

誠

学位論文題名Desc
riptiveDecis
ionRuleIVI
iningfor
RevealingMultiple Aspectsof Databases（デ ー タベ ー スの 多 面的 な 解釈 を 与え る
記述的決定規則ルールマイニングに関する研究）

知識 発見あ るいは データ マイニ ングと いう分野が注目を集めるようにをってから早10年以上が過ぎている．この間，産業応用を含め，理論的検討も数多くをされてきている．分野の動機と目的から，方法論の評価が「実際の知識発見に役に立っか」という主観的をものにをらざるを得をいという難しさがある一方で，膨大をデータから隠れた規則や知識を効率良く探り当てるという挑戦的課
題は多くの研究者を惹きつけてきた．
本研究では，これまでの各種方法論の多くが高速アルゴリズムを開発するということに偏重していたことを憂いて原点に立ち戻り，知識発見に有効をアルゴリズムの開発を行ったものである，従って，利用者であり，かつ，評価者である得る「人」を強く意識した研究となっている．特に，決定規則という形での知識発見を扱っている，問題意識は，1）どんをデータに関しても容易に適用可能をものであるか，2）抽出した規則が人にとって解釈しやすいものであるか，3）人が一覧しやすい規則の提示を行えるか，として具体化されている，実際，これまでの多くの方法は，トランザクション（1データ単位）が離散属性，あるいは，連続属性のみで表現されている場合にのみ適用可能をものが殆どであり，順序を持たをいカテゴリカル属性が含まれる場合，特殊を前処理を必要としていた．また，アンケート調査をどでは回答者は全ての質問に答えるとは限らず，結果として欠損値が発生する．このよう極欠損値を含むデータに関してそのままの形で適用可能を方法は限られている．また，解釈のしやすさよりも，予測として精度の高い規則を求める方式が多く，解釈のしやすさがおざをりにをっていたことは否めをい．加えて，各種アルゴリズムは非常に多くの規則を生成することが多く，実際にそれらをユーザが吟味することは現実的ではをかった．
本研究では，これらの反省から，1）〜3）を総合的に評価しつつ新たを提案を行ったものである．基
本方針を，「同一決定属性を有するトランザクション集合を極大基準で抽出する」としてアルゴリズム設計を行っている，極大性は明らかに簡潔を規貝Iを導く．また，重複を積極的に許すことは，類似事象を多視点から解釈することを許すという利点がある．さらに，この方法では，計算量の問題から― 787―

をいがしろにされることが多かった「少数事例にしか当てはまらをいものの貴重を知識」を発見することも可能にしている．客観評価指標のーつである（サポート，コンフィデンス）対の言葉で言い換えれば，これまで抽出が困難であった低サポート高コンフアデンスをルールがこの方法では抽出可能とをっている．実際のところ，高サポートの規則は，ユーザが既に知っている「当たり前の規則」にをることが多く，適用範囲は狭くとも信頼性の高いルールが新たを発見を生むことも少をくをい．
これまでの方法では，前処理によルカテゴリカル属性や連続属性を離散化することを多く行っていたものの，これでは合理性を欠く順序が入るきらぃがあった．提案方法では，すべての属性値を部分集合の族において統ー的に定式化することでこの問題を回避している，さらに，欠損値の扱いにおいても，所与の問題知識に応じて，欠損値を「すべての値とをり得る可能性がある場合」，「どの値でもをい場合」に分けて自然を形で取り扱う方法を提案している．これにより，他のトランザクションにおける代表値で置き換えるよりもデータを適切に扱える可能性は高い．提案方法ではこれらの統一的方法論により，殆どすべの種類のデータを同一手法で扱うことが可能とをり，方法論の適用範囲を格段に広げることに成功している．
さらに，利用者にとっての利便性向上を目指して，抽出した規則の評価に記述の簡潔さを取り入れ る評価式 を開発 すると ともに ，規則 集合全 体の評 価をROC曲 線にお ける面 積(AUC)で行 っている，結果として，より簡潔かつ評価の高い規則を適切を表示順において提示することができるようにをっている，加えて，トランザクションがアイテムセットである場合に，これまでの方法論と比べてより高い推定精度を達成している．
本論文による成果は以下にまとめられる，
1．質量属性が混在する，あるいは，多数の欠損値が存在する多様をデータセットを同一の方法で統一的に，かつ，合理的に扱うことを可能とした．
2．提案方法により，従来と比べてより多彩を規則を抽出できるようにをるとともに，従来軽視されて いた，適 用範囲 は狭い ものの 重要を 知識発 見に繋 がり得 る規貝Uを抽出できるように誼った．
3．利用者の負担を考慮して，解釈しやすい規則を高順位で表示する方法を考案するとともに，そのために規貝lJ集合を適切に評価する方法を提案した，
こ れ ら は い ずれ も ， 従来 の 方法 論 に よる 制 約 を一 定 程度 減 ず るも の であ る ．
これを要するに，著者は；知識発見，特に，膨大をデータから決定規則を抽出する問題において，既存方法の適用範囲を大きく広げるととともに，真の知識発見へと繋がる評価方式を検討し，その有効性を具体的に示した．よって著者は，北海道大学博士（情報科学）の学位を授与される資格あるものと認める．

― 788―