必須コントラストパターンを利用した分類モデルに関する研究

必須コントラストパターンを利用した分類モデルに

関する研究

著者

西口 真央

内容記述

学位記番号：論経第81号, 指導教員：森田 裕之

「必須コントラストパターンを利用した分類

モデルに関する研究」

大阪府立大学大学院 経済学研究科

経済学専攻 博士後期課程

目 次

1 章 序章 . . . . 1 2 章 基礎的内容および関連研究 . . . . 5 2.1 節 基礎的内容 . . . . 5 2.2 節 特徴的パターンの定義 . . . . 6 2.3 節 特徴的パターンを利用した分類モデル . . . . 8 2.3.1 CAEP . . . . 9 2.3.2 CACP . . . . 12 2.4 節 CAEP および CACP を適用した応用事例 . . . . 14 2.5 節 パターン選択に関する既存研究 . . . . 17 2.6 節 パターンの視覚化 . . . . 19 3 章 提案手法 . . . . 21 3.1 節 CAECP . . . . 21 3.2 節 CRPD . . . . 23 4 章 計算実験 . . . . 27 4.1 節 ベンチマークデータに対する実験 . . . . 28 4.2 節 製造小売業データに対する実験 . . . . 36 4.3 節 スーパーマーケットの POS データに対する実験 . . . . 45 5 章 おわりに . . . . 54 A 主な略語リスト . . . . 56

1

章

序章

計算機の処理能力の向上とアルゴリズムの進化により，大規模なデータセット に頻出するパターン集合 (以下，頻出パターンと呼ぶ) を高速に列挙することが可 能となった. 頻出パターンの代表的な応用の１つとしてはアソシエーションルー ル [1] があり，パターンの興味深さの定義を行うことにより，あるスーパーマー ケットの店舗でよく同時に購買されている商品群を発見するような，商品間の関 連性分析を実施する際に有効なツールとなる. 頻出パターンはまた，対照的なク ラスラベルを持つデータセットが与えられた場合，あるクラスにのみ特徴的なパ ターンとして列挙することが可能である. この特徴的パターンの概念やアルゴ リズム，それらの応用研究分野は総称してコントラストデータマイニングと呼ば れ，ここ数十年のうちに数多くの研究論文が報告されている [2]. 特徴的パターン は，時空間をまたぐ変化や傾向を捉えたり，望ましいケースと望ましくないケー スの比較分析に用いられるだけではなく，その性質からクラスタリングや分類モ デルの説明変数として利用することにも適している. 特徴的パターンに基づくク ラスタリングとしては，Liu ら [3] が Contrast Patterns based Clustering Quality index(以下，CPCQ と呼ぶ) と呼ばれる，距離に頼らずにクラスタリングの質を 測定しクラスタを形成するための指標を提案している. [3] では，CPCQ を最大化 するようにクラスタを形成しており，従来の代表的なクラスタリング手法に比べ， データセットの事前知識を必要とせずに専門家が提供するクラスにより密接に対 応するクラスタを生成できることが実証されている. 特徴的パターンを利用した 分類モデルは，高い精度で予測可能なことに加え，モデルに使用されたパターン から有用な知識を抽出できる点が大きな長所である. たとえばある小売店舗にお いて, 購買行動履歴から長期的に利用してくれる顧客クラスとそうでない顧客ク ラスを分類予測したいという課題があったとする. この課題を解くにあたって, 高 い精度で予測できるモデルを構築することはもちろん, 2 つのクラスの特徴や差 分を分析し, 次のビジネスアクションにつなげることができるような手法が望ま しい. そのためビジネス領域では，特徴的パターンベースのモデルや決定木 [4] の ような可読性の高いモデルが利用されることが多い. 本研究は，特徴的パターン の分類モデルへの適用およびそのビジネス分野への応用研究に位置付けられるも のである.

特徴的パターンをベースとする代表的な分類モデル構築手法としては，Dong ら [5] が提案した, Emerging Pattern [6](以下，EP と呼ぶ) を利用した Classifi-cation by Aggregating Contrast Patterns(以下，CAEP と呼ぶ) や，Morita ら [7] が提案した, Contrast Pattern [8](以下，CP と呼ぶ) を利用した Classification by Aggregating Contrast Patterns(以下，CACP と呼ぶ) などが存在する. どちらの 手法も，モデルに利用するパターンにスコアを与え，そのスコアに従いトランザ クション ID(以下 TID と呼ぶ) に対してクラス投票を行うことでクラスを決定す るという非常にシンプルなモデル構築手順でありながら，高い予測精度のモデル を構築できることが実証されている. また，CAEP や CACP を用いて実生活に結 びつく課題を解き，比較的高い予測精度と有用な知見を得ることに成功した数多 くの事例研究が報告されている. しかしながら，いくつかの事例研究の中で，こ れらの手法は問題によってはモデル構築に非常に多くのパターンを必要とするこ とが明らかになった. これはモデルの可読性の観点からは望ましいことではない. また, 直感的にはより多くのパターンを利用した方が予測精度が高くなると思わ れるが, 大量のパターンを利用することで過学習を起こしてしまい, 予測精度を 落としてしまうケースもみられた. このような問題が発生する原因を調査すると， 一部の TID は非常に多くのパターンに該当している (以下，このような状況をパ ターンが TID をカバーすると定義する) のに対し，一部の TID は未カバーであ る，もしくはわずかしかカバーされていないという現象が発生していることが明 らかになった. また，一部の未カバー TID をカバーするパターンを採用するため には多くの説明力の弱いパターンを採用することが多く，結果として全体の予測 精度が悪くなるケースも確認された. 以上のことから筆者は， [5] や [7] で用いら れているパターン選択基準の他に，何らかの方法でカバーされる回数のばらつき が少なくなるようなパターン集合を発見することが重要ではないかと考えた. 特徴的パターンベースの分類モデルに利用するパターン集合を発見する課題 に取り組んでいる既存手法としては, [9] や [10] がある. [9] では，情報量と既に 採用したパターンとの冗長性を評価基準として, 採用するパターンを 1 つずつグ リーディに選択していき, すべての TID が任意の回数回カバーされると選択を終 了するというヒューリスティクス的アプローチを採用している. これにより，一 定数のパターンを削減することに成功している. 一方 [10] では，十分な数の候補 CP 集合から，任意の最小カバー率と最小カバー回数を制約条件として，Greedy

randomized adaptive search procedures [11] (以下，GRASP と呼ぶ) と呼ばれる 局所探索法を採用したアルゴリズムによって選択を実施しており，予測精度には ばらつきが見られたものの，非常に少ないパターン数でも精度の高いモデルを構 築できる可能性を示している. 本稿の目的の１つは，これらの既存手法を踏まえ， カバー率とカバー回数に着目して，候補となる CP 集合の中から予測に必要十分 な CP の組み合わせ集合を選択し，CACP をベースとした分類モデルを構築す る新たな手法，Classification by Aggregating Essential Contrast Patterns(以下， CAECP と呼ぶ) を提案することである. CAECP は，CACP の予測精度を落とさ ずに，より可読性の高い分類モデルとなることを期待する. 本稿のもう１つの目的は，モデルに使用された CP の解釈をより容易にするた めの，効果的な視覚化手法を提案することである. Novak ら [12] は，パターンの 視覚化手法について調査し，円グラフ，箱ひげ図，そして棒グラフによる表現方 法を紹介している. しかしながら，これらの方法ではパターンが持つ重要な情報 の一部しか表現できないため，十分であるとは言い難い. より多くの情報を含む 表現方法としては，パス図で表現することが考えられ, 筆者の既存研究や関連研 究でもよく利用されてきた. しかしながら, いずれも単純なパス図で表現されて いるため，視覚的に複雑になってしまうケースがしばしば確認された. 本稿では， モデルに使用した CP の所属クラスや影響力も表現し，かつパターンを構成する アイテムレベルでの解釈も可能とする新たな視覚化手法 Contrast Ranked Path Diagram(以下，CRPD と呼ぶ) を提案する.

本稿の構成は以下のとおりである. 第 2 章では，本稿で取り扱うデータ形式や 基礎的な用語の定義，および関連する研究の概要を説明する. 続く第 3 章では，提 案手法である CAECP と CRPD をそれぞれ詳細に説明する. 第 4 章では，まずは UCI Machine Learning Repositly [13] に登録されているデータの中から，CAECP に適した３つのデータセットに対してベンチマーク実験を行い，既存手法と結果 を比較することで提案手法の有効性を確認する. その後，ある製造小売業の購買 履歴データ及び店舗来店履歴データ1_{と，複数のスーパーマーケットの POS デー} タ2_{のそれぞれに対して，提案手法を活用した分析を実施し，実ビジネスの困難} 1_{経営科学系研究部会連合協議会主催, 平成 26 年度データ解析コンペティションで提供された} データ 2_{経営科学系研究部会連合協議会主催, 平成 27 年度データ解析コンペティションにて（株）ア} イディーズより提供された i-code データ

な課題を解く上で有用であることを示す. 最後に第 5 章で本稿のまとめ及び今後 の課題を述べる.

2

章

基礎的内容および関連研究

本章では, 2.1 節において本稿で取り扱うデータ形式や頻出パターンの定義と いった基礎的な用語を説明する. 2.2 節では, 代表的な特徴的パターンである CP と EP を説明し, 2.3 節で特徴的パターンを利用した分類モデル, 特に CAEP と CACP について述べる. 2.4 節では, CAEP と CACP の様々な領域への応用事例を紹介 し, そこから導き出された課題についても議論する. 2.5 節では, 本研究のテーマ の 1 つであるパターン選択の既存研究を 2 つ紹介し, 良い点や課題点を整理する. 最後に 2.6 節で, パターンの視覚化手法についてまとめる.

2.1

節

基礎的内容

本稿で取り扱うデータセットは, トランザクション形式を想定している. 1 行が 1 つのトランザクションを表しており, 各トランザクションにはそれぞれユニーク な ID（TID）が与えられている. トランザクション t のアイテム項目には, 1 つ以 上の属性が列挙されている必要がある. またデータセットとは, トランザクション の集合を意味する. 表 1 は, トランザクション形式データセットの簡単な例であ 表 1: トランザクション形式データセットの例 TID アイテム T1 牛乳, シリアル, 卵, パン T2 ジュース, パン, ヨーグルト T3 ジュース, 牛乳, シリアル, バター, パン T4 ジュース, パン, ヨーグルト T5 牛乳, 卵, パン る. 表 1 では 1 つのトランザクションはスーパーマーケットにおけるレシート 1 枚に対応していると仮定する. たとえば T5 は, 牛乳とシリアルとパンを 1 回の買 い物で購買したと考えることができる. パターンとは, 表 1 で出現するアイテムで 構成される集合 I = { おむつ, ジュース, 牛乳, シリアル, 卵, バター, パン, ヨーグ ルト_{} の部分集合である. 本稿ではパターンの順序は考慮しないため, { 牛乳, パ} ン_{} と { パン, 牛乳 } は同じパターンとみなされる. また, パターン内のアイテム}

は重複しない. たとえば T5 に含まれる全てのパターンは, トランザクションの部 分集合である_{{ 牛乳 }, { 卵 }, { パン }, { 牛乳, 卵 }, { 牛乳, パン }, { 卵, パン }, そ} して_{{ 牛乳, 卵, パン } である.} 次に, データセット D に頻出するパターンの定量的な指標であるサポートにつ いて説明する. より多くのトランザクションに含まれるパターンほど, より特徴 的なパターンとするのがサポートの考え方である. supD(x) = cntD(x) |D| (1) D に出現するパターン x のサポートは式 (1) で表される. ここで cntD(x) は,D の パターン x を含む TID 件数を示し,|D| は D の総レコード件数とする．頻出パター ンとは, 最小サポート σ(0≤ σ ≤ 1) が与えられたとき，supD1(x)≥ σ を満たすパ ターン x と定義される．たとえば表 1 において, 最小サポート 0.6 以上を満たす, つまり 3 件以上のトランザクションに出現する頻出パターンとしては,{ ジュース }, { 牛乳 }, { パン }, { ジュース, パン }, { 牛乳, パン } の 5 つが該当する.

2.2

節

特徴的パターンの定義

以下では, 2 つの異なるクラス 1, 2 のいずれか一方に属する TID からなるデー タセット D1,D2 を想定し, あるクラスにのみ特徴的なパターンである EP と CP の 定義を説明する. EP と CP はどちらも, サポートによって定義される頻出パター ンに基づく. 頻出パターンは, 頻度をもとに特徴的であるかどうかを定義している が, 今回のように複数のクラスの存在を想定している場合, 両方のクラスに多頻 度で出現するパターンは, あるクラスにのみ特徴的であるとはいえない. そこで, 頻出パターンの定義に加え, クラス間のサポート差を採用したものが CP であり, サポートの比率を採用したものが EP である. DFD1(x) = supD1(x)− supD2(x) (2) 式 (2) は,D1におけるパターン x のサポートの方が D2 におけるパターン x のサ ポートよりも大きい場合の, パターン x のクラス間のサポート差を表している．こ こで, 任意の最小サポート差 λ を与えたとき, 頻出パターンかつ DFD1(x)≥ λ を

満たすパターン x を, クラス 1 における CP と定義する. GRD1(x) =    sup_D1(x) sup_D2(x) , supD2(x) > 0 ∞ , supD2(x) = 0 (3) ρD1(x) = GRD1(x) GRD1(x) + 1 (4) 一方, x の D2に対する D1の増加率 (Growth Rate) は式 (3) で与えられる. この増 加率を, 式 (4) により 0 から 1 の間に基準化した値を ρ と呼ぶ. ここでクラス 1 にお ける EP とは, 任意の最小 ρ∗(ρ∗ ≤ 1) を与えたとき, 頻出パターンかつ ρD1(x)≥ ρ∗ であるような x を指す. 1.0 1.0 クラス 1 のサポート ク ラ ス2 の サ ポ ー ト σ λ ρ* 領域 B 領域 C 領域 A 図 1: EP と CP の存在領域 図 1 は, 各クラスのサポートを軸とした 2 次元空間におけるクラス 1 の EP と CP の関係を表している．σ 以上となる領域を, σ と λ を表す線分によって A, B, C の 3 つの領域に分ける．このとき, A と B を合わせた領域が EP の存在領域と なり, A と C を合わせた領域が CP の存在領域となる．このように, EP と CP で は定義の違いから存在領域のずれが発生する．EP と CP はどちらも, あるクラス

を特徴づける要因となるため, クラスを分類する強い説明変数にもなりうるが, そ の場合どちらのパターンを利用するかによって分類モデルの性質が異なってくる． ここで, いずれのクラスにもカバーされていないトランザクションは, いずれのク ラスのスコアも 0 となりクラスを予測することができないため, 未分類トランザ クションと呼ぶこととする. EP は, サポートの大きさよりも, 片側のクラスにの み顕著なパターンを優先するため, パターン単体の説明力は強い．しかし, その分 1 つ 1 つのパターンがカバーする範囲が小さくなる傾向があり, 未分類トランザク ションを発生させる可能性も高くなる．一方の CP は, 各クラスのサポートが比較 的大きなパターンも列挙可能であるため, このパターンを利用した分類モデルで は, 未分類トランザクションを減少させることができる. しかし,EP と比べ両方の クラスに一定程度出現するパターンも採用するため, 誤分類を生じる可能性も高 くなる．CACP と CAEP のどちらが精度良く予測できるかは対象となるデータ セットに依存するが, 予測精度に未分類トランザクションも考慮する場合, CACP の方がより少ないパターン数で比較的高い精度のモデルを構築できる傾向にある. 第 1 章でも述べたように, 本研究の目的の 1 つはモデルに利用するパターンを削 減することであるため, 本稿で提案するモデルには CP を採用している. 特徴的パ ターンベースの分類モデルについては次節で議論する.

2.3

節

特徴的パターンを利用した分類モデル

特徴的パターンベースの分類アルゴリズムは, トレーニングフェーズで特徴的 パターン集合を列挙し, そのパターン集合を利用した何かしらの分類戦略に従い, 分類決定に至る. 最初に提案された分類アルゴリズムは Classification Based on Associations [14] (以下, CBA と呼ぶ) であり, 続いて CAEP が提案された. 以降, information based classification by aggregating emerging patterns [15] (iCAEP), Jumping Emerging Patterns Classifier [16] (JEP-C), Decision-making by Emerg-ing Patterns [17] (DeEPs), Classification based on Multiple Association Rules [18] (CMAR), Classification based on Predictive Association Rules [19] (CPAR), CACP など, 多くの分類アルゴリズムが提案されてきた. 上記分類アルゴリズムは, 分類 戦略やモデルに利用するパターンの選択基準, 基準化方法等に違いがあるが, CBA 以外はいずれも, 分類戦略としてパターン集約アプローチを採用している. 本節

では, 多くの後発アルゴリズムの基本型となった CAEP と, 本稿で提案する分類 モデルのベースとなる CACP についてのみ詳細に説明する. 2.3.1 CAEP CAEP 構築の手順は, 図 2 に表されるように大きく 6 ステップに分けられる. 入 入力：トレーニングデータセット , パラメータ 出力：予測結果 , 利用パターン集合 列挙：候補パターン集合を列挙 剪定：冗長なパターンを除外 得点：利用パターンにパターンスコア (p スコア ) を付与 投票：p スコアを基準に各 TID に対してクラス投票を実施 図 2: CAEP 構築の手順 力ステップで与えられるトレーニングデータセットは, 表 1 で示したトランザク ション形式のデータにクラスラベルが与えられた, 表 2 のようなデータ形式であ る. クラスは原則として 2 クラスであり, 時間, 場所, その他要因またはそれらの 表 2: クラスラベル付きトランザクション形式の例 TID アイテム クラス T1 牛乳, シリアル, 卵, パン クラス 1 T2 ジュース, パン, ヨーグルト クラス 2 T3 ジュース, 牛乳, シリアル, バター, パン クラス 2 T4 ジュース, パン, ヨーグルト クラス 1 T5 牛乳, 卵, パン クラス 1 組み合わせにより, 対照となるよう定義される. クラスはたとえばガンの良性と

悪性の比較や, 大学を卒業する学生とそうでない学生のように, 望ましいケースと 望ましくないケースに分けるクラス設定が用いられることが多い. クラスが 3 ク ラス以上の場合には, 全てのクラスのペアごとにモデル構築を行うことも可能で あるが, あるクラスとそれ以外のクラスとすることで, 2 クラスに置き換えること が一般的である. 入力ステップではまた, パターンの列挙の際の制御パラメータで ある ρ∗や σ などが与えられる. 列挙ステップでは, 入力パラメータに従って, モデルに利用する候補となる EP 集合がそれぞれのクラスで列挙される. 候補 EP 集合には, 似たようなアイテムの 組み合わせである, いわゆる冗長なパターンが多く生成されるため, パターンの剪 定が実行される．包含関係にある 2 つの EP, EP∗ ⊂ EP∗∗_{が存在するとき, 必ず}

sup(EP∗)≥ sup(EP∗∗) が成立するため, GR(EP∗)≥ GR(EP∗∗) であれば, EP∗は

EP∗∗よりもカバーする範囲が広くかつ判別能力も高いことになる. したがって,

このような条件を満たす EP∗∗_{が剪定され, 残った EP}∗_{をモデルに利用している．}

モデルに利用する EP には, 式 (5) に基づきパターンスコア (以下, p スコアと呼 ぶ) が与えられる. これが得点ステップである.

epscoreD1(EP) = ρD1(EP)× supD1(EP) (5)

続く投票ステップでは, この p スコアを基準に, 予測する各 TID に対してクラス 投票を実施する. etscore(t，D1) = ∑ EP⊆t,EP∈EP1 epscoreD1(EP) (6) 投票ステップではまず, 式 (6) のように，予測する各 TID のクラス 1 の各トラン ザクションのスコア (以下, t スコアと呼ぶ) を算出する．ここで t はあるトランザ クション, EP1_{はクラス 1 に属する EP 集合を意味する．同様の方法によってク} ラス 2 の各 t スコアが計算される．CAEP では, 分類すべき各レコードの各クラ スの t スコアの大小によって所属クラスを予測している. 投票ステップの直感的 な理解のために, 簡単な例を図 3 で示す. 図 3 では, モデルに利用する EP は 3 つ であり, 予測する TID も 3 つであると仮定する. 図 3 の左上の表は, 得点ステップ で得られた p スコアであり, 右上の表は各 TID と各 PID の対応リストである. こ れらの 2 つの表を元に, 各クラスの t スコアが算出される. 図下の表の 2 列目と 3 列目がその結果である. この各クラスの t スコアの大きい方が予測クラスとなり,

各 PID の p スコア TID と PID の対応リスト

各 TID の t スコアと予測結果

PID クラス 1 の p スコア クラス 2 の p スコア TID 該当する PID

P1 P2 P3 3.2 5.6 2.9 T1 T2 T3 P3 P1, P2, P3 P1, P2 TID T1 T2 T3 クラス 1 の t スコア クラス 2 の t スコア 2.9 6.1 5.6 5.6 3.2 実際のクラス 予測クラス 正誤 クラス 2 クラス 1 正 誤 正 クラス 2 クラス 2 クラス 1 クラス 1 図 3: スコア投票の例 予測クラスと実際のクラスが一致しているかどうかで, 正しく予測されたかどう かを判定する. ただし, 実際の分類問題を解くにあたって, t スコアの大小をそのまま比較して しまうと，各クラスの t スコア分布が大きく異なる場合，明らかに一方のクラス の t スコアの値が過大評価される危険性がある．そのため， [5] では各クラスの t スコアのメディアンで除した基準化 t スコアを用いて計算する方法を提案してい る．たとえば, 各 TID の各クラスの et スコアが表 3 で示される値であり, クラス 表 3: 各 TID の各クラスの t スコア及び基準化 t スコア クラス 1 クラス 2 TID クラス 1 の クラス 2 の の基準化 の基準化 t スコア t スコア t スコア t スコア 1 0.00 0.42 0.00 3.50 2 0.016 0.24 1.60 2.00 3 0.018 0.20 1.80 1.67 4 0.00 0.00 0.00 0.00 · · · · · · · · · · · · · · ·

1 の t スコアのメディアンが 0.01, クラス 2 の t スコアのメディアンが 0.12 であっ たとすると, 各 TID の各クラスの基準化 t スコアは表 3 の値のように与えられる． TID=1 と TID=2 は,t スコアも基準化 t スコアもクラス 2 の方が大きいため, クラ ス 2 に属すると予測される. しかし TID=3 では,t スコアはクラス 2 の方が大きい が, 基準化 t スコアではクラス 1 の方が大きい．したがって,TID=3 はクラス 1 と 予測される．また, 両クラスの t スコアが 0 である TID=4 は, モデルに使用され るパターンを 1 つも含んでいないレコードであることを意味し, このレコードは どちらのクラスのスコア値も, より大きいと判断する事ができないので, 未分類レ コードとなる． 以上のステップを踏み, 最終的に出力としてモデルに利用した EP と予測結果が 返ってくるのが CAEP モデルである. このようにパターンを集約し, クラス投票 により予測クラスを決定する戦略は多くの特徴的パターンベース分類アルゴリズ ムで採用されており, 本研究のベースとなる CACP もその 1 つである. 2.3.2 CACP CACP の構築手順は CAEP と同じであるが, スコアの算出方法,t スコアの基 準化方法, そして剪定方法が異なる. 剪定基準は増加率ではなくサポート差とな る. すなわち, 包含関係にある 2 つの CP, CP∗ _⊂CP∗∗_{が存在するとき, DF (CP}∗₎ ≥ DF (CP∗∗_{) となるような CP}∗∗_{が剪定される.} CACP のスコアは,CP の誤分類が大きくなるというデメリットを抑えるよう考 慮されている. cpscoreD1(CP, D1, D2, θ) = θ× {supD1(CP)} 2 + (1− θ) × {supD2(CP)− 1} 2 (7) ctscore(t，D1, D2, θ, CP1) = ∑ CP⊆t,CP∈CP1 cpscoreD1(CP, D1, D2, θ) (8) 式 (7) と式 (8) はそれぞれ, CACP における p スコアと t スコアの算出方法である. ここで, t はあるトランザクション, D1, D2はそれぞれクラス 1 とクラス 2 のデー タセット, CP1_{は, クラス 1 の候補 CP の集合, θ は任意のパラメータ (0}≤ θ ≤ 1) を意味する．図 4 は, 式 (7) で示されている p スコア値が同じになる等高線を,0.6, 0.7, そして 0.8 について図示したものである．図 4 では, θ の値は 0.3 に設定して

図 4: p スコアとサポートの関係 いる．図から分かるように, 同じサポート差のパターンでも, クラス 2 に対するク ラス 1 のサポートの割合がより大きなパターンが, より大きな p スコアをとる仕 組みとなっている．図 5 は, θ と p スコアの関係を表している．この図では, p スコ アは 1 に固定している．図 5 から分かるように, θ の値が小さいほど, 同じサポー ト差でも, クラス 2 に対するクラス 1 のサポートの割合がより大きなパターンが, より大きな p スコアを持つようになり, 逆に θ の値を大きくすると, 同じサポート 差のパターンでも, 該当クラスのサポートがより大きなパターンが, より大きな p スコアを持つようになる．θ の値が 0.5 のときは, 同じサポート差でも, クラス 2 に 対するクラス 1 のサポートの割合がより大きなパターンと, 該当クラスのサポー トがより大きなパターンが, 同等に高く評価されることを意味する．θ の値は, サ ポート分布に依存するパラメータである．しかし, サポート差が大きいパターン があまり出現しないとき, より該当クラスのサポートが大きなパターンに高いス コアをつけた方が, 誤分類は少なくなると予想される．そのため, θ は高く設定し た方が良い. 逆に, サポート差が大きなパターンが比較的多く出現しているような ときは, θ の値は低い方がより予測精度は向上すると思われる. また, t スコアの

図 5: θ と p スコアの関係 基準化にはメディアンではなく z 得点を使用し, 負の値にならないよう, Z 得点に 50 を加えた値を基準化 t スコアとしている．

2.4

節

CAEP

および

CACP

を適用した応用事例

このような CAEP や CACP を, 実生活に結びつく様々な課題を解くために適用 した以下のような事例研究が報告されている. [20] では, オフィスビルのエント ランスホールの属性値を用いて, 感性評価値に基づくイメージや清潔感などの高 クラスと低クラスを CAEP によって分類し, 既存の決定木モデルやサポートベク ターマシンと比較して分類精度が良いことを計算機実験から示している. [21] で は, ひったくり犯罪の発生地域クラスと未発生地域クラスを設定し, 犯罪発生に 関係する様々なデータをアイテムとして CAEP を適用し, 決定木モデルやロジス ティック回帰での予測結果よりも優れた結果であることを計算実験から示してい る. [22] は, フラッシュマーケティングを実践している某共同購入クーポンサイト 運営企業の販売履歴データを対象として, 多様な購買行動を行っている顧客クラ

ス等を CACP によって高精度で予測することに成功している. [23] は, ドラッグ ストアの 3 つの商品分類におけるブランドスイッチに関するクラスを設定し, 対象 ブランドと競合ブランドの価格差などの情報をアイテムに組み込むという工夫を 施した上で, 系列情報を考慮した EP [24]（以下, ESP と呼ぶ）を利用した CAEP を適用している. 計算機実験では, 系列情報を考慮しない CAEP を用いた方法など と比較し, 設定した問題においては CAESP の方が優れていることを示している. その他にも, アイテムのタクソノミーを取り入れた分類モデルへの応用 [25] [26] や, 順序情報持つ系列データとトランザクションデータが混在するようなデータ への応用事例 [27] [28], さらにはメロディデータへの CAEP の適用と音楽検索シ ステムへの応用 [29] といった, 様々な工夫をこらした応用事例もみられる. 以上のように, CAEP や CACP は, カテゴリデータを対象とした分類モデルと しては優れた手法であり, 比較的高い予測精度と有用な知見を得ることに成功し た数多くの成功事例が報告されているが, いくつかの問題点もある. 直感的には, より多くのパターンを利用した方が予測精度が高くなると思われ, 実際に [25] な どの研究では利用パターンを増やすことで予測精度を高める工夫を行っている. しかしながら, ある一定数を超えると過学習を起こす原因となり, 逆に予測精度を 落としてしまうことも明らかになっている [7] [10]. 特徴的パターンベース分類 モデルの長所の１つである可読性の高さという観点からも，モデルに使用するパ ターンは少ないほど良い. 図 6 は, パターン数が可読性にもたらす影響を示すた DJ HB 2 BFRORUBFDWHJ RU\BLG B 2 BUHVHUYHBIOJ B : %B]RQHBLG B 2 BVDOHBIOJB 2 B]RQHBLG B : %BLWHP BVP DOOBLG B 2 BVL]HBLG B 2 BVL]HBLG B WRG RIXNHQB 2 BUHVHUYHBIOJ B 2 BFRORUBLG B : %BLWHP BE LJ BLG B 2 BLWHP BE LJ BLG B ෇ྎ㉎㈙ ෇ྎ㉎㈙ ㉎㈙๓㜀ぴ ࢩࣙࢵࣉ$ ㉎㈙๓㜀ぴ ࢖ࣥࢸࣜ࢔ ㉎㈙๓㜀ぴ㞧㈌ ㉎㈙๓㜀ぴ ࢰ࣮ࣥ㸱 ㉎㈙๓㜀ぴ ࢩࣙࣝࢲ࣮ࣂࢵࢢ ㉎㈙๓㜀ぴ ࢰ࣮ࣥ ࢰ࣮ࣥ㉎㈙ Ⅼ㉎㈙ ௦๓༙ ᮾᾏ࣭㏆␥ᆅ᪉ ዪᛶ ࣂࢵࢢ㉎㈙ ⏨ᛶ ࢰ࣮ࣥ㉎㈙ ࡑࡢ௚Ⰽ㉎㈙ 2B]RQHBLGB 2BFRORUBFDWHJRU\BLGB :%B]RQHBLGB 2BFRORUBLGB 2BLWHPBELJBLGB 2BUHVHUYHBIOJB EX\BRQH 2B]RQHBLGB :%BVKRSBLGB :%BEUDQGBLGB DJHB :%B]RQHBLGB :%BLWHPBVPDOOBLGB :%BLWHPBELJBLGB DJHB VH[B WRGRIXNHQB 2BVL]HBLGB 2BVL]HBLGB :%B]RQHBLGB VH[B WRGRIXNHQB 2BVDOHBIOJB :%B]RQHBLGB :%B]RQHBLGB 2BEUDQGBLGB 2BFRORUBLGB 2BLWHPBELJBLGB WRGRIXNHQB2BLWHPBELJBLGB 2BVKRSBLGB 2BLWHPBVPDOOBLGB :%BVKRSBLGB:%BEUDQGBLGB DJHB 2BSULFHBFDWHJRU\B :%B]RQHBLGB EX\BPRUH :%BLWHPBELJBLGB :%BVKRSBLGB :%B]RQHBLGB 2BSULFHBFDWHJRU\B :%B]RQHBLGB 2BSULFHBFDWHJRU\B :%BEUDQGBLGB 2BVL]HBLGB :%BLWHPBVPDOOBLGB :%BVKRSBLGB 2BUHVHUYHBIOJB 2BSULFHBFDWHJRU\B:%BVKRSBLGB :%BLWHPBELJBLGB 2BLWHPBELJBLGB :%B]RQHBLGB :%BLWHPBELJBLGB DJHB 2BSULFHBFDWHJRU\B:%BVKRSBLGB:%BLWHPBELJBLGB 2B]RQHBLGB :%BEUDQGBLGB :%BVKRSBLGB DJHB :%BEUDQGBLGB:%BLWHPBVPDOOBLGB:%BVKRSBLGB:%BLWHPBELJBLGB:%BLWHPBELJBLGB 2BVDOHBIOJB:%BLWHPBELJBLGB

パターン数 25 パターン数 275

図 6: パターン数が可読性にもたらす影響

めに, 275 のパターン集合と 25 のパターン集合をシンプルなパス図で描画したも のである. パス図の複雑性は, パターン数だけではなく, パターン間の関連性や配

置等様々な要因に影響されるが, 経験的には単純なパス図ではパターン数が 100 を超えると直感的理解が難しくなってくる. モデルに利用したパターンを解釈す るためには, 多くとも数十のパターンに抑えることが必要である. 実際に [28] な どは利用パターン数を抑えることも試みている. しかしながら, 実ビジネスのデー タに対する計算実験において数百のパターンを用いていることから, まだ十分に 少ないとは言い難い. 他の事例研究においても, 予測精度の良いモデル構築のた めに非常に多くのパターンを採用している. このような問題が発生する原因を調査すると，一部の TID は非常に多くのパ ターンにカバーされているのに対し，一部の TID は未カバーである，もしくは わずかしかカバーされていないという現象が発生していることが分かった. 図 7 P1 P2 P3 P4 P5 P6 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 クラス 1 に属する TID クラス 2 に属する TID 採 用 さ れ た パ タ ー ン 図 7: カバー回数が偏っている例 は,TID によってカバー回数が偏っている例を表しており, 灰色で塗りつぶされて いることが, カバーされていることを意味している. 図では, T5 や T6 は多くの パターンにカバーされているが, 一方の T1 や T9, T10 は 1 回もカバーされてい ない. このような偏りは，たとえばサポートもサポート差も小さいパターンにし かカバーされない TID が存在するとき, 従来の σ や λ などのパターン選択基準だ けだと, これらの TID をカバーするパターンを採用するためには, その他多くの 説明力の弱いパターンも採用しなければならないために発生してしまう. そこで

筆者は，従来のパターン選択基準の他に，何らかの方法でカバーされる回数のば らつきが少なくなるようなパターン集合を発見することが重要ではないかと考え た. 次節では, カバーに着目したパターン選択手法を提案している 2 つの既存研究 を紹介する.

2.5

節

パターン選択に関する既存研究

Cheng ら [9] は, 候補となる頻出パターン集合を用意し, 情報量と既に採用した パターンとの冗長性を評価基準として 1 つずつグリーディに選択していき, すべ ての TID が任意の回数回カバーされると選択を終了するというアルゴリズムを提 案している. 分類モデルは, 選択された頻出パターン集合を説明変数として, SVM や C4.5 などの従来の分類アルゴリズムにより構築されている. Algorithm 1 は, Algorithm 1 Cheng ら [9] が提案している選択アルゴリズム Input: 頻出パターン集合 FPs, カバー回数の閾値 th, 関連性 S, 冗長性 J Output: 選択パターン集合 FP∗s 最も関連性の高いパターンを FP1とする; FPs = {FP1}; while true do FPs - FP∗s のパターン集合の中で, ゲイン g(FP) が最大となるパターン FP を探す; if FP が 1 つ以上の TID をカバーしている then FP∗s = FP∗s ∪ {FP}; end if FPs = FPs - {FP}; if 全ての TID が th 回以上カバーされている, または FP = ϕ then break; end if end while return FP∗s Novak らが提案している選択アルゴリズムの詳細である. ここで, ゲイン g(FP) は 式 (9) で定義される. g(F P ) = S(F P )− max F P∗∈F P∗sJ (F P, F P ∗_{) (9)}

ここで FP, FP∗はそれぞれ, 候補頻出パターンと既に採用が決まっている頻出パ ターンを表し, FP∗s は採用パターン集合である. また, S(FP) はある選択状態にお いて FP を採用した場合の情報ゲイン, J(FP, FP∗_{) は FP と FP}∗_{との間の Jaccard} 係数と定義する. つまり, ある選択状態において, 最も情報ゲインが高く, かつ冗 長ではないパターンを採用していくというアプローチを取っている. Cheng らの 提案手法は, UCI [13] に蓄積されている様々なデータセットに適用し, 少数のパ ターンで高い予測精度を算出することに成功している. 筆者は, Cheng らの情報 ゲインを採用している点やヒューリスティクスアプローチ, そしてカバーに着目 している点にはパターン削減の妥当性があり, 明確な停止基準も設けられている ところは良い点であると考え, 提案手法の参考としている. しかしながら, 計算実 験では比較的予測が容易なデータセットに対しても数百のパターンを必要として おり, 実用性としてはまだ不十分である. 筆者はこの原因として, ゲインの計算の 対象がすべての TID であるため, 弱いパターンにしかカバーされていない TID を 見つけにくくなっているのではないかと考えた. そこで本稿で提案する手法では, よりカバー回数の偏りをなくし, 必要十分なパターンのみを採用するために, よ り明確に未カバー TID をカバーさせる戦略を取り入れている. 詳細は次章で説明 する. また [10] では, 十分な数の CP 集合から，任意のカバー率と平均カバー回数を制 約条件として，GRASP と呼ばれる局所探索法を採用したアルゴリズムによって 選択した CP を利用し，CACP によりモデルを構築する手法を提案している. こ こでカバー率とは，総 TID 数に対するカバーされている TID 数の割合とし，平 均カバー回数とは，総 TID 数に対するカバーされている TID のべ数の割合とす る. カバー率と平均カバー回数について直感的に理解してもらうために, 簡単な 図を用いて説明する. 図 8 では, TID とそれをカバーしている PID の簡単な例で あり, 灰色で塗りつぶされていることはカバーされていることを意味し, カバーフ ラグが 1 となる. この図のケースでは, 4 つの TID のうち 3 つがカバーされている ことから, カバー率は 3/4 となり, 全 TID で 5 回カバーされていることから, 平均 カバー回数は 5/4 となる. [10] も [9] と同様に, 計算実験においていくつかの UCI に蓄積されているデータセットに対して手法を適用し, 非常に少ないパターン数 でも CACP より精度良くモデルを構築できることを示した. この点は非常に有意 義であった反面, GRASP というランダム性を採用したアルゴリズムによる結果

PID P₁ P₂ P₃ TID T₁ T₄ T₃ T₂ カバー フラグ カバー回数 1 2 0 1 1 1 0 2 図 8: カバー率とカバー回数の例 であるため，改善理由を明確にすることが出来ない点と，アルゴリズムの明確な 停止基準を定めることが難しい点が研究の限界として挙げられる. 本稿で提案す る手法も, [10] のように CACP でモデル構築し, カバー率とカバー回数も考慮し た上で, [9] のような妥当性のあるアルゴリズムを目指す. 計算実験では, UCI の 同じデータセットをベンチマークデータセットとし, パターン数と予測精度の観 点から [9] や [10] の実験結果との比較検証を行う.

2.6

節

パターンの視覚化

Novak ら [12] の研究では, 円グラフ, 箱ひげ図, 棒グラフによってパターンの情 報を表現する視覚化手法を紹介している. これらの手法は, サポートやサポート 差, そしてパターンの属するクラスを視覚的に捉えることが可能である. しかし ながら, これらの手法では, パターンを構成するアイテム間の関連性や, アイテム の頻出度合いといった, アイテムレベルでの表現には向いていない. このような アイテムレベルの情報を表現するためには, 筆者が調査した事例研究ではパス図 が用いられることが多い [20] [21] [22] [23] [26] [28]. しかし, 既存研究では非常 に単純なパス図でしか描画していないため, 複雑なものになっている. それゆえ 彼らは, 長さ 2 のパターンのみに絞り, クラスも 1 つに制限するなど, 部分的なパ ターンに限定したパス図を作成することで対処している. さらに, 従来の単純な パス図では, パターンの各クラスへの影響力を表現することはできても, アイテム

単体の影響力を表すには至っていない. 本稿では, エッジの太さや種類, ノードの 位置などの情報に意味を持たせることで, 少数の CP の持つ情報を効果的に表現 する手法である CRPD を提案する. CRPD の詳細は次章で説明する.

3

章

提案手法

本章では, 本稿で提案するモデル構築手法である CAECP と, モデルに利用し た CP の視覚化手法である CRPD を順に説明する.

3.1

節

CAECP

本稿で提案するモデルの構築手順は, 基本的には CACP と同じである. ただし, [10] と同様に, 剪定ステップが以下で説明する新たな選択アルゴリズムに置き換わ る. 提案手法の詳細は Algorithm 2 に示している. ここで cr(R) は選択 CP 集合 Algorithm 2 本稿で提案する選択アルゴリズム

Input: 候補 CP 集合 Rposと Rneg, 最初に選択するクラス f c, レイヤー上限 α, 1

回の探索回数上限 γ, 最小カバー率 η, 最小カバー回数 β Output: 選択パターン集合 R

選択クラス c = fc, R = ϕ, layer = 0

while {cr(R) ≤ ηかつ ac(R) ≤ β} または layer ≤ α do

Rcのエントロピーゲインを計算し, エントロピーゲイン降順に並び替え; for each p in γ do if ag(R, p) > 0 then R∪ {p}; Rc\ {p}; c をもう一方のクラスに変更; end if end for if R に追加されなかった場合 then layer = layer + 1 end if end while return R のカバー率, ac(R) は選択 CP 集合の平均カバー回数, ag(R, p) は候補 CP である p を加えることで得られる正答率の上昇値である. 提案アルゴリズムの本質は, あ る選択状態においてベストであると判断された CP を 1 つずつ採用していく, グ リーディな戦略である. したがって, 1 つ CP を採用するたびに次のベストな CP が変化するため, 選択前にどちらのクラスの CP から採用するかは予測結果に重

要な影響を与える. しかし, 事前にそれを知ることは困難である. したがって筆 者は, 最初に選択するクラスを決めるパラメータ f c を採用している. 候補 CP を 採用する基準は, 該当 CP を採用した時に正答率が上昇するかどうかで判断する が, そのチェックはエントロピーゲインが高い CP 順に行われる. つまり, 正答率 を改善する候補 CP のうち, エントロピーゲインが最も高い CP が, ある選択回に おけるベストな CP であると定義している. エントロピーは式 (10) によって得ら れ, エントロピーゲインは式 (11) によって得られる. Ent(v) =− 2 ∑ c=1 rclog2rc (10)

eg(p) = Ent(v0)− (rv1 · Ent(v1) + rv2 · Ent(v2)) (11)

式 (10) の v は節点, c はクラス, rcはある節点におけるクラス c の比率を表し, 式 (11) の v0は選択前の節点, v1は選択された側の節点, v2は未選択側の節点, rv1は 節点 v1の分割割合, rv2 は節点 v2の分割割合を表している. 提案手法では, このエントロピーゲインが大きいほど良い候補 CP であるとし ている. ただし, 節点 v0 のクラス比率が偏っており, 選択クラス側が少ない場合, たとえエントロピーゲインが高くとも, 節点 v1 の選択クラス側の比率が逆に低く なる可能性があることに注意されたい. これは意図する改善ではないため, この ようなケースとなる候補 CP は採用しないよう制限を加えている. さらに提案手 法では, 比較的少数の CP にしかカバーされていないような TID に対して有効な CP を発見するために, エントロピーゲインを計算する際に layer という概念を取 り入れる工夫を行なっている. layer はカバー回数の閾値であり, 候補 CP のエン トロピーゲインは layer 以下の TID を対象に計算される. たとえば図 8 の例だと, T3はカバー回数 0, T4はカバー回数 1, T1と T2はカバー回数 2 のため, layer = 1 のとき, エントロピーゲインは T3と T4のみを対象に計算され, layer = 2 であれ ば, 全ての TID が計算対象となる. ただし, layer のカバー回数の定義は特殊で, 選 択された CP と同じクラスに属する TID のみカバー回数がカウントされる. layer は, ある探索回で条件を満たす候補 CP が存在しなかった場合に 1 つ増加 (α まで) し, 次の探索が開始する. この layer によって, 平均カバー回数およびカバー回数 の偏りを可能な限り抑えながら, カバー率および予測精度を改善することが可能 となる. また 1 回の探索実行回数は, 計算の高速化のために γ によって制御され

ている. ある候補 CP が選択され R に追加されると, 選択クラス c はもう一方の クラスに変更され, 次の探索回が開始される. 以上の選択プログラムは任意のカ バー率 η と平均カバー回数 β を満たす, または layer が α を超えると終了する.

3.2

節

CRPD

以下では, 表 4 のようなモデルが出力されたと仮定し, CRPD の作図プロセス と表現方法を説明していく. まずは, 従来のシンプルなパス図で表現した例を図 表 4: 出力されたモデルの例 PID パターン スコア クラス P1 item1 item2 2 2 P2 item3 item4 3 1 P3 item1 item3 1 2 P4 item4 item5 4 1

P5 item4 item5 item6 4 1

P6 item4 item7 item8 4 2

P7 item2 item3 1 2 P8 item0 item3 2 1 P9 item0 2 1 P10 item1 item7 1 2 9 に示す. パス図では, ノードラベルはアイテム名を意味し, パターンはエッジで 結ばれている. エッジの太さは p スコアの大きさに比例し, item0 のようなセルフ ループはパターンの長さ 1 であることを表す. 長さ 3 以上のパターンの場合は, パ ターン内の全てのアイテムをエッジで接続し, 完全グラフとして表現している. パ ス図での表現は, パターン間の関連性を表現でき, モデルの解釈を促進する良い 表現方法であるが, いくつか課題もある. たとえばクラス 2 の, item1 と item2 と item3, そして item4 と item7 と item8 はどちらも完全グラフとなっており, 一見 するとどちらも長さ 3 のパターンに見える. しかし, 前者は長さ 2 のパターンが 3 つ連結しているだけであり, このような状況を区別することが難しい. 既存研究で は, 長さ 2 のパターンに限定するなどの工夫で対処している. また既存研究では, 複雑さを回避するためにクラスごとにパス図を描画しているが, その場合 item3

クラス 1 に出現した CP クラス 2 に出現した CP item1 item2 item3 item7 item8 item4 item4 item5 item6 item0 item3 item4 item5 item6 図 9: 単純なパス図 と item4 のように, どちらのクラスにも出現しているアイテムを視覚的に捉える ことが困難になる. CRPD は, これらの課題を解決するように設計されている. 上述のパス図と比較して, CRPD は大きく 3 つの特徴を持っている. 1 つめは, 2 つの異なるクラスへの出現パターンを同時に, かつ対照的に表現していること である. これにより, 2 つのクラスに出現しているパターンを識別することを試み ている. 2 つめは, クラスへの相対的な影響力にもとづいて, アイテムにランクを 付与し, ランクごとにノードの位置を整えていることである. これにより, パター ンの重要度だけではなく, アイテムレベルでの考察もより容易にしている. ラン クの設定方法については後述する. 3 つめは, パターンの長さを線の種類で区別す ることで, 誤った解釈となることを防いでいることである. これらの工夫により, CRPD が数十の CP に対してより洗練された視覚化手法となり, モデルの可読性 を高めることを期待している. 図 10 は, 表 4 を CRPD で作図した例である. 図 9 と同様に, ノードラベルはア イテム名, パターンはエッジの接続で表現されており, エッジの太さは p スコアの 大きさに比例し, item0 のようなセルフループはパターンの長さ 1 であることを表

クラス 1 に強いノード クラス 2 に強いノード rank3 rank2 item5 item6 rank1 rank0 item0 item3 rank-1 item4 item8 item7 rank-2 item2 rank-3 item1 図 10: CRPD す. 長さ 3 以上のパターンも同様に完全グラフとして表現される. CRPD ではま た, 実線のエッジは長さ 2 を, 点線は長さ 3 のパターンを表している. そして, 図 下の軸がアイテムのクラスへの影響度を表すランクである. ランクは, 左に位置 するほどクラス 1 に強い影響を与えるアイテムとなり，逆に右に位置するほどク ラス 2 に強い影響を与えるアイテムとなる. ただし，両方のクラスに出現するア イテムは rank0 に配置している. あるアイテムのランクは， あるアイテムを要素 とするパタンのスコアの合計値を算出後，その合計値を基準にクラスごとに均等 三分割して算出する. 例えば図 10 では， クラス 1 には 2 つのパターングループ が出現していることが分かる. そして item5 が最高ランクに位置し, かつ item4 と item6 と共起しているため，このパターングループがクラス 1 に強い影響を与え ていると解釈することができる. 一方のクラス 2 でも 2 つのパターングループが みられ, item7 がキーアイテムであることが分かる. また item4 は rank0 に位置し, 接続されているエッジの数やその太さから, クラスを問わず頻出するアイテムで あり, このアイテムもまた 1 つの特徴的なアイテムであると解釈できる.

入力：CP 集合 , CP と TID の対応リスト 出力：アイテムランク , エッジの種類 , エッジの太さの情報    が与えられた dot ファイル ランクの算出：  ・パターンスコアをクラス別にアイテムごとに合計  ・合計されたパターンスコアを基準に , クラス別に   アイテムを 3 つに均等分割  ・両方のクラスに出現している場合 , ランク = 0 に変換 エッジの種類を指定：  ・パタン長が 1 または 2 であれば実線  ・3 以上なら点線 エッジの太さを指定：  ・パタン内のアイテムの全組み合わせを列挙  ・上記アイテム組み合わせごとにパターンスコアを合計  ・上記合計パターンスコアを 1∼10 の値に線形変換 図 11: CRPD

4

章

計算実験

本章では, 提案手法である CAECP と CRPD を, ベンチマークデータと 2 つの 実データに対して適用し, 有効性を確認する. ベンチマークデータには UCI に保 存されている 3 つのデータセットを用い, 既存手法との比較を行う. 実データは, ある製造小売業社から提供された購買履歴データ及び店舗来店履歴データと, 複 数のスーパーマーケットの POS データを用いる. 分類モデルの性能は, 正答率と 使用パターン数, そして計算時間で評価し, 10 回の交差検証の平均値を使用する. 正答率は未分類 TID の数を考慮しており, 表 5 から式 (12) によって計算される. 表 5: 分類表 予測されたクラス クラス 1 クラス 2 未分類 合計人数 クラス 1 T P F N U P T P + F N + U P 実際の クラス 2 T N F P U F T N + F P + U F クラス 合計人数 T P + T N F N + F P U P + U F 総 TID 数 accuracy = T P + T N 総レコード件数 (12) 計算時間は, データの入力から予測結果の出力までの時間を計測し, 実験に使用 した計算機のスペックは以下の通りである. また, CP の列挙部分は LCM [31] に 表 6: 計算機のスペック

機種 MacBook Air (13-inch, Early 2015)

CPU 2.2 GHz Intel Core i7

メモリ 8 GB 1600 MHz DDR3

ストレージ 250GB

4.1

節

ベンチマークデータに対する実験

ベンチマーク実験では, UCI Machine Learning Repository で提供されている データセットの中から, 目的変数が 2 値で, かつ説明変数が離散値である 3 つのデー タセット, Chess End-Game King+Rook versus King+Pawn on a7(以下, Chess と 呼ぶ), Mushroom database(以下, MR と呼ぶ), Breast cancer data(以下, BC と呼 ぶ) を使用する. 表 7 から表 9 は, Chess, MR, BC それぞれにおける, 訓練データ と検証データのクラス別 TID 数を示している. 今回は 10 回の交差検証であるた め, 訓練データはトータル TID 数の 9 割, 検証データは 1 割となる. 実験結果は, 表 7: Chess データの各クラスの TID 数 クラス名 訓練データ 検証データ トータル won 1,502 167 1,669 nowin 1,375 152 1,527 トータル 2,877 319 3,196 表 8: MR データの各クラスの TID 数 クラス名 訓練データ 検証データ トータル edible 4,039 449 4,488 poisonous 3,535 393 3,928 トータル 7,574 842 8,416 表 9: BC データの各クラスの TID 数 クラス名 訓練データ 検証データ トータル no-recurrence 76 9 85 recurrence 181 20 201 トータル 257 29 286 いくつかの実験を通して最も良い結果を出した設定パラメータによるものを掲載 している. 設定パラメータは表 10 に示す.

表 10: 設定パラメータ パラメータ Chess MR BC 最小パターン長 1 1 1 最大パターン長 3 3 3 θ 0.7 0.7 0.7 topK 10,000 30,000 3,000 最小サポート件数 2 2 2 η 0.99 0.99 0.99 β 2.5 2.5 2.75 α 5 5 5 γ 500 500 1,000 表 11: 評価値の比較 Chess MR BC 正答率 パターン数 正答率 パターン数 正答率 パターン数 CAECP 0.941 4 0.975 9 0.731 39 CACP 0.870 309 0.974 588 0.717 181 比較手法 0.971 136 0.949 11

表 11 は, 正答率と採用パターン数を既存手法と比較したものである. CACP の結果も提案手法と同様, いくつかの実験を通して最も結果の良かった設定パラ メータによる結果である. また, 表中の比較手法では, Chess データでは [9] に記 載された結果を, MR データでは [10] に記載された結果を示している. BC データ の実験結果を掲載している関連論文は見当たらなかったため, 空白としている. ま ず Chess データの結果を確認する. 提案手法による結果は, CACP による結果と 比較して, 正答率と利用パターン数のどちらにおいても大幅に改善している.  比 較手法に対しては, 正答率は劣るものの, 利用パターン数は 136 からわずか 4 つに まで削減することに成功している. 続いて MR データへの適用結果を確認すると, 既存手法 2 つに比べ最も少ないパターン数で最も高い正答率のモデルを構築でき ていることが確認できる. BC データでも, 正答率は決して高いとは言えないもの の, 正答率の高さと利用パターン数の少なさの両方で CACP を上回っている. 以 上の比較結果から, 筆者が提案する手法は, これらの 3 つベンチマークデータセッ トに対しては, 既存手法の予測精度を保ちつつ, より少ない利用パターン数でモデ ル構築が可能であることが確認できた. 計算時間やカバー率など, その他の計算結果を確認していく. 表 12 を見ると, 表 12: 計算結果 Chess MR BC 計算時間 (秒) 403.5 358.9 5.6 正答率 (訓練) 0.940 0.975 0.865 正答率 (検証) 0.941 0.975 0.731 カバー率 (訓練) 1.000 1.000 1.000 カバー率 (検証) 1.000 1.000 1.000 平均カバー回数 (訓練) 2.357 2.518 2.671 平均カバー回数 (検証) 2.605 2.393 2.751 全てのデータセットに対して数秒から数分という現実的な時間でモデル構築でき ていることがわかる. 正答率は, Chess と MR においては訓練データと検証デー タの値がほぼ同じであり, 非常に安定したモデルとなっている. しかし BC デー タでは, 訓練データと検証データで大きく差が開いており, やや過学習を起こして しまっている. しかし, カバー率と平均カバー回数を見ると, いずれのデータセッ

トでも訓練データと検証データに大きな差はなく, 適切な選択が行えているよう に見える. 図 12, 図 13, 図 14 は, Chess データ, MR データ, BC データそれぞれ のモデルにおける, TID が CP にカバーされた回数の分布を棒グラフにより図示 したものである. これらの図から, Chess データと MR データでは訓練データと 検証データの分布がほぼ同じという理想的な状態になっている. 一方 BR データ では, 訓練データの最頻値は 3 回であるが, 検証データでは 2 回となっている. ま た, 検証データでは 5 回以上カバーされている TID の割合が増加しており, この ような分布の偏りが予測精度を下げる原因と思われる. カバーされた回数 1 2 3 TID 数 の 全 体 に 占 め る 割 合 0 50 (%) 訓練 検証 図 12: Chess データのカバー回数分布 どのような CP が選択されているのかを確認するために, データセットごとに 候補 CP と選択 CP をサポート空間上にプロットしたものが図 15 から図 17 であ る. Chess データの選択を示す図 15 を見ると, won クラスの選択 CP はいずれ もスコアは高いものの, サポートが高い CP, サポート差が高い CP, そしてサポー トもサポート差も高いという, 異なる特徴を持つ 3 つの CP がバランス良く選択 されている. また, nowin クラスに対してはたった 1 つの CP で予測可能であるこ とが分かった. MR データの選択である図 16 を見ると, スコアの高い CP は選択 されているものの, スコアや従来の選択基準では採用されにくい CP もいくつか 選択されている. こうした CP を適切な数だけ採用できたことが, 少ない CP での モデル構築を実現したと思われる. BC データの選択である図 16 を見ると, MR データと同様に, 様々な位置の CP が採用されているが, スコアの低い CP の採用

カバーされた回数 1 TID 数 の 全 体 に 占 め る 割 合 0 50 2 3 4 5 6 7 8 9 (%) 訓練 検証 図 13: MR データのカバー回数分布 カバーされた回数 1 TID 数 の 全 体 に 占 め る 割 合 0 50 (%) 2 3 4 5 6 7 訓練 検証 図 14: BC データのカバー回数分布

won クラスのサポート nowin ク ラ ス の サ ポ ー ト 0 1 1 図 15: Chess データの選択パターンの分布 edible クラスのサポート poisonous ク ラ ス の サ ポ ー ト 0 1 1 図 16: MR データの選択パターンの分布

no-recurrence クラスのサポート recurrence ク ラ ス の サ ポ ー ト 0 1 1 図 17: BC データの選択パターンの分布 数がやや多いように見える. 今回は, 候補 CP はできるだけ多く採用して実験を 行ったが, こうした説明力の弱い CP が選択されすぎると過学習を起こす原因と なるため, より候補 CP 集合を絞ったり, 選択時に重みをつけるといった対応を行 うことが必要と思われる. 最後に, 各データセットで出力されたモデルの解釈を行う. 図 18, 図 19, 図 20 はそれぞれ, Chess データ, MR データ, BC データで出力されたモデルを CRPD によって視覚化したものである. 図 18 では, 出力 CP が 4 つということもあり, 非 rank3 rank2 v14_f v25_f v27_f rank1 v10_f v32_f v33_f rank0 v21_t rank-1 rank-2 v21_f rank-3 won クラスに強いノード nowin クラスに強いノード 図 18: Chess データの出力モデル

常にシンプルな図となっている. ノードラベルのハイフンより左側の文字列は属 性の名前を, ハイフンより右側は属性の値を表している. 属性名は, たとえば v21 であれば, UCI Machine Learning Repositry に置かれている生データの 21 列目の 属性であることを意味する. 図から, win クラスにはパタン長 3 の CP が 2 つと長 さ 1 の CP が 1 つ出現していることが分かる. 特に, v14 と v25 と v27 がいずれも f であれば, 高い確率で白が勝つようようだ. 逆に, v21 が f であることは白が負 ける非常に強い要因となる. 図 19 を考察すると, edible クラスには 3 つか 4 つの 2 k n a r 3 k n a r ring_type_pendant odor_none veil_type_partial ring_number_one rank1 bruises_bruises spore_print_color_brown habitat_woods gill_spacing_crowded stalk_shape_tapering gill_attachment_free rank0 ring_number_two rank-1 stalk_color_below_ring_white stalk_shape_enlarging rank-2 stalk_color_above_ring_white rank-3 cap_shape_convex gill_size_narrow population_several gill_spacing_close veil_color_white bruises_no edible クラスに強いノード poisonous クラスに強いノード 図 19: MR データの出力モデル CP グループ, poinsonous クラスには 2 つか 3 つの CP グループがみられる. 例え

ば edible クラスでは, 無臭である odornone だけでは食用であるとは言えず, リン

グの数や型の種類, または内被膜かどうかもチェックする必要があるらしい. 一方 poisounous クラスでは, 菌膜が白く, ひだの間隔が密で, あざのないキノコは有毒 であるための 1 つの有力な条件となるようだ. 図 20 は, 採用 CP 数自体も多く, か つどちらのクラスにも出現するアイテムも多いため, 上の 2 つの図と比べ複雑な 図となってしまっている. つまり, 単体のアイテムには意味がなくとも, 組み合わ されることによって説明力が上昇するアイテムが多いデータであり, 予測が難し い分類問題であることが分かる. その中でも, どちらのクラスにも 1 つ強力なアイ テムが存在してるようだ. 出現パターンを考察すると, 右上部に位置することは 未再発に対して非常にポジティブな要因である. その他には年齢が比較的低いこ とやサイズが比較的小さいことなど, 直感的にも妥当なパターンが no-recurrence の方に出現している.

2 k n a r 3 k n a r breast-quad_right_up deg-malig_2 node-caps_yes deg-malig_3 inv-nodes_3-5 irradiat_no rank1 tumor-size_20-24 tumor-size_30-34 rank0 tumor-size_15-19 deg-malig_1 menopause_premeno age_30-39 breast-quad_left_up node-caps_no rank-1 irradiat_yes inv-nodes_6-8 inv-nodes_0-2 breast_right node-caps_? tumor-size_25-29 breast_left menopause_ge40 tumor-size_45-49 breast-quad_left_low tumor-size_5-9 age_60-69 rank-2 age_50-59 rank-3 age_40-49 no-recurence に強いノード recurence に強いノード 図 20: BC データの出力モデル

4.2

節

製造小売業データに対する実験

使用するデータは, ある製造小売業の 2013 年 5 月から約 1 年分の, 店舗やサイ トでの購買履歴, 顧客属性, 一部顧客の店舗訪問履歴データである. 当該企業は, 商品の企画開発から販売までを行う製造小売業であり, 日常生活全般にわたる商 品を製造販売している. このような製造小売業者の, 製造もしくは販売のみをお こなう企業と比較したときの競争優位性の 1 つは, POS データや位置データから, 誰がいつどの店舗に行き, 何を購買したのかといった詳細な顧客行動データを直 接取得することができ, これらのデータを分析することで, 商品企画や製品価格, 供給量の決定などに活かすことが可能なことである. データ分析の目的としては, 単に顧客全体の行動を把握することも重要であるが, 顧客をいくつかのクラスに 分け, それぞれのクラスに特徴的な購買行動を明確化する, いわゆるコントラスト データマイニングを実施することで, より興味深い示唆を得ることができる. た とえば, 自社商品を継続的に購買してくれる, いわゆるロイヤルカスタマーによ く見られる購買行動は, 継続購買につながる効果的な販売促進方法や, 新たなヒッ

ト商品を生み出すためのヒントとなるだろう. 逆に, 継続的に購買していたが, あ る時を境に長期間行わなくなってしまった顧客の購買行動は, 質の悪い商品の発 見や, 適切なプロモーションのタイミングなど, 価値ある改善のための多くの示 唆を与えてくれる. 当該データの特徴としては, 衣料品や食品, さらには家庭用品 といったように, 取り扱う商品分類が多岐にわたり, それらの商品分類の購買の 共起も考慮することでより興味深い知見が得られる可能性があることが挙げられ る. また, 季節性のある商品の存在や, 季節による購買量の変化なども考慮すると なると, 変数の組み合わせは膨大なものとなる. したがって分析に用いる手法は, 変数が独立して説明力を持つだけでなく, 本稿で提案する CAECP のような, 変 数間の組合せによる説明力も併せ持つ手法のほうが望ましいと考えられる. 本節では, ロイヤルティの高い顧客とそうでない顧客の商品購買行動の差別的 な要因を明らかにすることで, 適切なマーケティングを実施するための示唆を得 ることを目的に分類問題を設定する. 当該企業には, 毎年 3 月 1 日から 1 年間の購 買金額に応じて顧客ステージが更新され, 毎年 2 月末でリセットされる仕組みの 顧客システムがり, 最上位ステージの顧客になるためには 20 万円以上の購買が必 要となる. そこで本節では, 下記の 2 つの分類問題を設定した. 1 つは, 2013 年 3 月 1 日∼2014 年 2 月末までの期間で最上位ステージであった顧客のうち, 2014 年 3 月 1 日以降も購買履歴がある顧客 (以下, 継続クラスと呼ぶ) とそうでない顧客 (以下, 休眠クラスと呼ぶ) を分類する問題である. 以下ではこの問題を分類問題 1 と呼ぶ. もう 1 つは, 分類問題 1 で継続クラスであった顧客のうち, 2014 年 3 月 1 日以降の購買日数が平均以上である顧客 (以下, 高頻度クラス) とそうでない顧客 (以下, 低頻度クラス) を設定した. 以下ではこの問題を分類問題 2 と呼ぶ. 各分類 問題の各クラスの TID 数はそれぞれ表 13 と表 14 にまとめている. 表 13: 分類問題 1 の各クラスの TID 数 クラス名 訓練データ 検証データ トータル 継続 7,978 887 8,865 休眠 1,948 217 2156 トータル 9,926 1,104 11,030 基礎集計の結果より, 最上位ステージ会員の多くはシリーズ商品の同時購買を