データマイニングアルゴリズム「アプリオリ」と「ＩＤ３」の比較

Presentation on theme: "データマイニングアルゴリズム「アプリオリ」と「ＩＤ３」の比較"— Presentation transcript:

1 データマイニングアルゴリズム「アプリオリ」と「ＩＤ３」の比較
菊池研　 阿久津忍　倉野奈央子

2 はじめに データマイニング 主要な二つのアルゴリズム －アプリオリ －決定木 大量のデータの中から有益な情報、知識を抽出する技術。
金曜日に紙おむつと缶ﾋﾞｰﾙを一緒に買う男性が多い 朝食用にｼﾘｱﾙを購入する来店客は同時にﾊﾞﾅﾅを買う例が多かっ た 主要な二つのアルゴリズム　 　　　　　－アプリオリ 　　　　　－決定木

3 アプリオリ(Apriori) 最小サポート・確信度による相関ルールX⇒Yの効率的な検索 条件を満たす全てのルールの抽出
[Rakesh Agrawalら　1993] 　 アプリオリ(Apriori)　 最小サポート・確信度による相関ルールX⇒Yの効率的な検索 条件を満たす全てのルールの抽出 X⇒Y,Y⇒X,X∧Y⇒Z,・・・ サポート（支持度） 　　ルールの出現頻度 　　　　Supp(X⇒Y)=b/N 確信度 　ルールの確からしさ 　　　　Conf(X⇒Y)=b/a 1993年に米IBMのRakesh Agrawalらが提出したMining Associations between Sets of Items in Massive Databases

4 決定木（ＩＤ3） エントロピー最小化による分類 単一の決定木の抽出 ターゲット属性 知りたい項目（ターゲット属性）がある時に使う。
[John Ross Quinlan 　1979] 　 ターゲット属性 エントロピー最小化による分類 知りたい項目（ターゲット属性）がある時に使う。 誤差の少ない決定木が１つ抽出 単一の決定木の抽出 H(S)=-plogp-(1-p)log(1-p)

5 アプリオリと決定木(ID3)の違い アプリオリ 決定木(ID3) 出力 複数のルール 単一の木 ターゲット属性 なし あり 原理
サポート・確信度 エントロピー

6 目的 ２つのアルゴリズムでは同じ結果が得られるか？ １．アプリオリシステムの性能 ２．出現属性の比較 ３．論理関係の比較

7 アンケートデータ 対象：東海大学生１００人(男６３、女３７) 実施期間：２００６年５月下旬～７月上旬
形式：２択の質問項目(２０問)を属性として　用いる 属性は恋愛感について。（無関係の属性も含む） 束縛する人について興味がありました！

8 ２．出現属性の比較 目的 ２つのアルゴリズムでは同じ結果が得られるか？ １．アプリオリシステムの性能 ３．論理関係の比較
決定木とアプリオリにおける出現属性の一致度を確かめる。

9 重要属性の比較 決定木 （例１） 相手色に染まらない⇒ 海外ある ダイエット中でない∧ 相手色に染まらない⇒ 感情を表に出さない⇒
海外に行った経験があるか 相手色に染まるか （例１） アプリオリ 相手色に染まらない⇒ 　 海外ある ダイエット中でない∧ 　 相手色に染まらない⇒ 感情を表に出さない⇒ 感情を表に出すか

10 重要属性の比較・適合率 アプリオリの適合率は2/3 決定木の適合率は1/2 アプリオリ Q12 Q9 Q14 Q18 Q19 決定木 属性
ターゲット ID3 アプリオリ Supp=0.3,Conf=0.6 m=2 m=3 Q1 Q4 　○ Q12 1 Q9 3 2 Q14 4 Q18 Q19 Q20 Q12 Q9 Q14 Q18 Q19 アプリオリの適合率は2/3 決定木の適合率は1/2 決定木 N=20,m=2

11 １．アプリオリシステムの性能 ２．出現属性の比較 ３．論理関係の比較

12 論理関係の比較 アプリオリとID3の出力したルールに矛盾がないかを確かめる。 全ルールを確かめた結果 アプリオリ：菊池研⇒つぶあん派
決定木：菊池研⇒こしあん派 全ルールを確かめた結果 矛盾はなかった 一致するルールが少なかった 矛盾！！ 次のスライドの説明をした方がいいっぽいので、 さらりと説明したらどうかと思って入れてみたけど、 必要なかったら消してくださいｗ →両者のルールのサポートの違いに起因

13 サポートと確信度の散布図

14 まとめ 決定木で上位に出現する属性は、アプリオリでも相関が高い。
抽出された知識の論理的な関係に矛盾はないが、アプリオリでの相関ルールに対応する葉は少なかった。 両者の出力形式の違いや、抽出ルールのサポートの違いに起因している。 他の属性について行った場合の考察は、 「同じようになるのではないか」としか思いつかなかった･･･(^^;; それを文にしてもいいけど、元々文だらけのまとめだしどうしよう。

15 束縛する人はこんな人！

16 ご清聴ありがとうございました

17 予備スライド

18 Q3 異性間の友情は・・・ 成立する 成立しない Q4 海外に行ったことが・・・ ある ない Q5 さびしがり屋ですか？ はい いいえ
見にくいのでいくつかに絞った方がいいみたい。 説明しやすいものだけ残して削ってくださいな。

19 １．アプリオリシステムの性能 ２．出現属性の比較 ３．論理関係の比較

20 アプリオリシステムの性能 最小確信度とルール数の関係 最小サポートとルール数の関係

21 出現属性の比較 決定木とアプリオリにおける出現属性の一致度を確かめる。 重要属性の比較 出現属性の再現率 高さや出現回数に注目
一致の度合い（再現率）

22 重要属性の比較 決定木 （例２） ケータイ見てない⇒ 束縛しない⇒ 異性の友情は成立する⇒ 一人の時間は大切 一人の時間は大切
人のケータイを黙って見たことがあるか （例２） アプリオリ 異性の友情は成立する⇒ 　 一人の時間は大切 ケータイ見てない⇒ 　一人の時間は大切 束縛しない⇒ 異性の友情は成立する∧交際経験ある⇒ 交際経験があるか 異性間の友情は成立するか

23 出現属性の再現率 アプリオリの方が多くの相関ルールが出力されるため、平均値は小さい。 ターゲット属性 ID3 アプリオリ Q4 2/4
2/7 Q7 3/4 3/5 Q9 3/3 3/14 平均再現率 0.75 0.37 アプリオリの方が多くの相関ルールが出力されるため、平均値は小さい。

24 論理関係の比較 抽出された規則の論理的な矛盾がないかどうか検討する。

25 アプリオリとID3 ８個中１個完全一致、残り７個無矛盾
ルール supp ｃｏｎｆ 染まらない∧ 感情出す⇒ 海外ある 0.20 0.80 自分嫌い∧ 感情出さない⇒ 海外ない 0.69 染まる⇒ 0.28 0.64 染まる 染まらない 感情出す

26 属性 ターゲット ID3 アプリオリ m=5,C=9 Supp=0.3,Conf=0.6 m=2 m=3 Q1 Q2 Q3 1 Q4 ○ Q5 Q6 Q7 Q8 Q9 3 2 Q10 Q11 Q12 Q13 Q14 4 Q15 Q16 Q17 Q18 Q19 Q20