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

Slides:



Advertisements
Similar presentations
画像処理・実習 第十四回:パターン認識 東海大学 情報理工学部 情報メディア学科 濱本和彦. 今回の内容 5. パターン認識 5.1 マッチングの原理 5.2 テンプレートマッチング 実習 相互相関とテンプレートマッチング.
Advertisements

土木計画学 第3回:10月19日 調査データの統計処理と分析2 担当:榊原 弘之. 標本調査において,母集団の平均や分散などを直接知ることは できない. 母集団の平均値(母平均) 母集団の分散(母分散) 母集団中のある値の比率(母比率) p Sample 標本平均 標本分散(不偏分散) 標本中の比率.
電子書籍の検索機能の改善 木下研究室 201002713 鴫原 善寿. 背景 スマートフォンなどの携帯端末の普及と ともに電子書籍に注目が浴びた。中でも amazon の kindle など電子書籍の専用端末も 現れた。 電子書籍はデータなので本棚もいらず、 持ち運びも容易になるなど様々な恩恵を もたらした。
大規模コーパスから獲得した 名詞の出現パターンを用いた 事態名詞の項構造解析
LZ符号化 森田 岳史.
商品に対して効果的な POP広告の研究と提案
情報処理の基礎 私たちとコンピュータの扱うデータの違い 明治学院大学 法学部消費情報環境法学科 鶴貝 達政
ヒープソートの演習 第13回.
CCC DATAset における マルウェアの変遷
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
論文紹介 青年期における恋愛相手の選択基準とアイデンティティ発達との関係
国内線で新千歳空港を利用している航空会社はどこですか?
J-POPの歌詞の分析 諸橋ゼミ 3年 須田 勇大.
JavaによるCAI学習ソフトウェアの開発
女性下着広告の 購買意思決定への影響  山本 和菜.
情報知能学科「アルゴリズムとデータ構造」
4Y-4 印象に残りやすい日本語パスワードの合成法
先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning
大学生におけるSNSの利用と社会的心理・対人関係との 関連について
経営学部 経営学科 ITビジネスコース 菊地真実子
数独パズルの難易度判定 ~解法ロジックを用いた数値化の提案~
聴き比べに特化した 音楽の鑑賞と知識学習のための Webアプリケーション
卒業研究 先輩の経験談に基づいた就職活動の目標管理方法
大阪教育大学大学院教育学研究科 総合基礎科学専攻 中窪 仁
J-POPの歌詞の分析 諸橋ゼミ 3年 須田 勇大.
2009年度卒業研究発表会資料 excelによるデータ分析手法を研究 氏名:荒尾 直也 ゼミ名:飯田ゼミ.
メディア計算機工学特論 2003 年度 Webにおける情報・知識の探索と検索の事例を とおして、現代的知識ベースとその利用法を理解する。
I-Scoverチャレンジ2013 ~I-Scoverでできる こんなこと、あんなこと~ データ分析/可視化カテゴリ 論文キーワードの特徴分析 ~どんなキーワードを付けているのか~ GOMI Hiroshi.
メソッド名とその周辺の識別子の 相関ルールに基づくメソッド名変更支援手法
Vegetabooo ついで買いしたくなる!? 新感覚ネオ野菜スイーツ
初心者のためのセキュリティ/プライバシー講座
小売店舗における陳列改善策の検討とVRの活用に関する研究
モバイルP2Pを用いた携帯電話 動画配信手法の提案 第3回
没入型仮想現実を用いた テニス練習システムの開発と評価
プログラム実行履歴を用いたトランザクションファンクション抽出手法
練習問題アイテムバンクの開発研究 ~再生形式~
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
情報管理論 2018/11/9 情報分析の道具 2018/11/9 情報分析の道具 情報分析の道具.
決定木とランダムフォレスト 和田 俊和.
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
第5章:特徴の評価とベイズ誤り確率 5・3:ベイズ誤り確率とは
利用関係に基づく類似度を用いたJavaコンポーネント分類ツールの作成
研究発表方法の例 ○○大学 ○○研究科 名無権兵衛.
WWW上の効率的な ハブ探索法の提案と実装
決定木 Decision Tree DT 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
市場調査の手順 問題の設定 調査方法の決定 データ収集方法の決定 データ収集の実行 データ分析と解釈 報告書の作成 標本デザイン、データ収集
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
GPGPUによる 飽和高価値 アイテム集合マイニング
不確実データベースからの 負の相関ルールの抽出
黒はいや!   白のパンダにして!.
Javaソフトウェア部品検索システムSPARS-Jの実験的評価
マルウェアの通信履歴と 定点観測の相関について
コードクローンの理解支援を目的としたコードクローン周辺コードの解析
SA:石井 チーム:地底人 メンバー:大嶽・青山・野口
見た目から受ける 印象について ~バドミントン競技において 強そうに見える条件はあるのか~
第16章 動的計画法 アルゴリズムイントロダクション.
C9 石橋を叩いて渡るか? ~システムに対する信頼度評価~
発表会用テンプレート このテンプレートの枚数で発表をすれば、ほぼ15分で終了するであろう。
アルゴリズムとデータ構造 2011年6月16日
クローン検出ツールを用いた ソフトウェアシステムの類似度調査
A-17 検索履歴のプライバシーを秘匿した ユーザクラスタリング
分散ハニーポット観測からのダウンロードサーバ間の相関ルール抽出
アルゴリズムとデータ構造 2013年6月20日
大学生の私服について.
統計現象 高嶋 隆一 6/26/2019.
分散ハニーポット観測からのダウンロードサーバ間の相関ルール抽出
心理学情報処理法Ⅰ データ処理と統計(1).
映像を用いた 「からだ気づき」実習教材の開発
プログラム依存グラフを用いた ソースコードのパターン違反検出法
Presentation transcript:

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

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

アプリオリ(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

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

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

目的 2つのアルゴリズムでは同じ結果が得られるか? 1.アプリオリシステムの性能 2.出現属性の比較 3.論理関係の比較

アンケートデータ 対象:東海大学生100人(男63、女37) 実施期間:2006年5月下旬~7月上旬 形式:2択の質問項目(20問)を属性として 用いる 属性は恋愛感について。(無関係の属性も含む) 束縛する人について興味がありました!

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

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

重要属性の比較・適合率 アプリオリの適合率は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

1.アプリオリシステムの性能 2.出現属性の比較 3.論理関係の比較

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

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

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

束縛する人はこんな人!

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

予備スライド

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

1.アプリオリシステムの性能 2.出現属性の比較 3.論理関係の比較

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

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

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

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

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

アプリオリとID3 8個中1個完全一致、残り7個無矛盾 ルール supp conf 染まらない∧ 感情出す⇒ 海外ある 0.20 0.80 自分嫌い∧ 感情出さない⇒ 海外ない 0.69 染まる⇒ 0.28 0.64 染まる 染まらない 感情出す

属性 ターゲット 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