2010 年 12 月 15 日 データエンジニアリング 演習 情報処理システム データマイニング ~ データからの自動知識獲得手法 ~
1. 演習の目的 (1) 多種多様な膨大な量のデータを解析し, 企業の経営活動などに活用することが望まれている. 大規模データベースを有効に活用する, データマイニング技術の研究が脚光を浴びている 1
1. 演習の目的 (2) POS データを用いて顧客の購買パターンを分析する. 相関ルール抽出を体験 ( 例 1) コンビニエンスストアの商品配置もし, アイスクリーム と 缶コーヒー が同時に買われる可能性が高い この 2 つの商品を近くに置くことで, 購買意欲を促進させられる 2
2. データマイニングとは 大規模データベースを扱うことを前提とし, 必要かつ十分な情報を高速に得ようとする手法 膨大な量の一般的ルールの中に埋もれて今まで発見されなかったようなルールを抽出 データマイニングは, 高速性を必要とするため, 統計手法ほど厳密に解析できない 3
3. データマイニング手法の分類 相関ルールの抽出おにぎりとお茶が同時に売れるなどの商品間の相関を発見する. 代表的手法として, アプリオリアルゴリズムがある. クラスタリング顧客データから近々自動車を購入しそうな客のクラスタ ( 集合 ) を発見する. 分類ルールクレジットカードに新規入会を希望する顧客に対して, 過去のカード債務者データから, 優良顧客 危険顧客に分類して入会の判断を行う. 4
4.1 相関ルールの定義 (1) 定義 1( 相関ルール ) 商品 = アイテム レシート = トランザクション I を全アイテム集合 ( 全商品 ), X, Y を I の部分集合と定義. 各トランザクション ( レシート ) において, X が成立する時に Y が高い確率で成立する規則を相関ルールという. 5
4.1 相関ルールの定義 (2) 定義 2 X ならば,Y である ことを X Y と表す. ただし,X, Y I, X Y = φ である. 例 2 鮭弁当を買う人が, 温かいお茶を高い確率で買うこと は X ={ 鮭弁当 } Y = { 温かいお茶 } 6
4.2 相関ルールの評価基準 (1) 数ある相関ルールの中で, 実際には有用なルールだけを抽出したい. 相関ルールを評価する 7
4.2 相関ルールの評価基準 (2) 相関ルールを評価するための指標支持度 (support) 確信度 (confidence) 有用な相関ルールとして評価 8
4.2 相関ルールの評価基準 (3) 定義 3( 支持度 (support)) 全データベースに対して,X と Y を同時に含むトランザクションがどのくらいの割合を占めるかを表す. ここで n(x) は,X を含むトランザクションの個数を表す. 支持度が高いほど一般性の高いルールであると考えられる. 9
4.3 相関ルールの評価基準 (4) 例 3 表 1 でルール { お茶 } { 新聞 } の支持度を計算する. となり, 客の 50% が { お茶 } と { 新聞 } を同時に購入する. 10
4.3 相関ルールの評価基準 (5) 定義 4( 確信度 (confidence)) X を含むトランザクションに対して,X と Y を同時に含むトランザクションがどのくらいの割合を占めるかを表す. 注意 : n(i) ではない! 確信度が高いほど信頼性の高いルールであると考えられる. 11
4.3 相関ルールの評価基準 (6) 例 4 表 1 でルール { お茶 } { 新聞 }, ルール { 新聞 } { お茶 } の確信度を計算する. となり,{ お茶 } を買った人の67% が { 新聞 } を, { 新聞 } を買った人の100% が { お茶 } を購入する. 12
5.1 アプリオリアルゴリズム (1) 商品の POS データ ( 表 2) から, 購買パターンを抽出 商品が買われた場合を 1, 買われなかった場合を 0 とする. 13
5.1 アプリオリアルゴリズム (2) 1. i = 1 とする. アイテム 1 つずつを候補アイテム集合 C i ( ルールとして抽出される候補 ) と呼び, 全データベース D を検索して各候補アイテム集合 C i の出現回数をカウントし支持度を計算する. 2. 各候補アイテム集合 C i について, ユーザの定めた基準である最小支持度以上の支持度をもつものをラージアイテム集合 L i と呼ぶ. 3. ラージアイテム集合 L i 同士を組み合わせたものを新しく候補アイテム集合 C i+1 として出現回数をカウントし支持度を計算する. 4. i := i+1 とする. 候補アイテム集合 C i が空集合になった場合, 各パスにおけるラージアイテム集合を出力し, アルゴリズムを終了する. それ以外の場合,2. へ戻る. 14
5.1 アプリオリアルゴリズム (3) アイテム 1: お茶 2: 弁当 3: 新聞 4: 牛乳 5: コーヒー 15
5.2 アルゴリズムの例 ラージアイテム集合 L 2 が次の 3 つの場合, 候補アイテム集合 C 3 はそれぞれ次のようになる. L 2 = {{1,2}, {2,3}, {1,3}} の場合 候補アイテム集合 C 3 = {1,2,3} が導かれる L 2 = {{1,2}, {2,5}, {1,5}} の場合 候補アイテム集合 C 3 = {1,2,5} は導かれない L 2 = {{2,3}, {3,5}, {2,5}} の場合 候補アイテム集合 C 3 = {2,3,5} は導かれない 1つ前のラージアイテム集合に部分集合が全て出現する候補アイテム集合を抽出 16
5.3 出力結果の処理 (1) 定義 5 ルール L の抽出方法 ラージアイテム L i, i=1,2,3, から抽出される相関ルール L 1 からはルールが作られない L 2 ={a,b} からは [a b], [b a] の 2 つが抽出 L 3 ={a,b,c} からは [a b,c], [b a,c], [c a,b], [a,b c], [a,c b], [b,c a] の 6 つが抽出 17
5.3 出力結果の処理 (2) 例 5 ルール L の抽出方法 下図の L 2 の中のアイテム集合 {1,2} からは相関ルール [{1} {2}] と [{2} {1}] が作成される. 18
5.3 出力結果の処理 (3) ルール L の抽出方法 例 6 最小確信度 80% でルールを抽出すると となり, ルール [{1} {2}] が抽出される. > 最小確信度 < 最小確信度 19
6. 演習課題 以下のファイルを, 授業用 WEB ページより適当なディレクトリにダウンロードすること. apriori.cpp mushroom.txt zokusei.txt 授業用 WEB ページ http://lab.mgmt.waseda.ac.jp/unix/ 20
6.1 必須課題 (1) 1. 表 3 に示すデータベースからアプリオリを用いて, 最小支持度 50% でラージアイテム集合を計算 ( 手計算になる ) せよ. 21
6.1 必須課題 (2) 2. 1. で求めたラージアイテム集合から最小確信度 60% で相関ルールを抽出せよ. ただし, ラージアイテム集合から考えられる全てのパターンを相関ルールとする. 22
6.1 必須課題 (3) 3. アプリオリアルゴリズムのプログラムを用いて, キノコの種別データを解析せよ. ここで, 最小支持度 最小確信度は各自が定めるものとする. アイテムセットの中のアイテム数が多くなるように設定 最小支持度, 最小確信度の意味を考えること抽出された相関ルールについて, 授業用 WEB ページ上のリンクを参照にして, 考察せよ. ( 例 : 食用キノコ 毒キノコにはそれぞれどのような属性があるかなどを考察する ) 23
6.2 自由課題 必須ではないが自由課題の評価は必須課題の評価にプラスする. 自由課題を解かないためマイナスされることはない. 4. アプリオリアルゴリズムを改良しようと考えた以下の提案を評価しなさい. 候補アイテム集合 C からラージアイテム集合 L を導く時に, 支持度と確信度の両方で絞込みを行った方が効率の良いアルゴリズムにならないか? 24
6.3 レポート課題 課題 (1)~(4)( ただし,(4) は自由課題で任意 ) を行い, レポートにまとめて提出 期限 :12 月 22 日 ( 水 )12:00 場所 :51 号館 2 階レポート BOX 質問は, 後藤研究室 (51 号館 15 階 03 室 ) か, 下記メールアドレスまで comp_app_q@it.mgmt.waseda.ac.jp 25
7.1 ファイルの説明 (1) apriori.cpp ( アプリオリプログラム ) アプリオリのC 言語ソースプログラムである. コンパイルした後に実行する際, 以下の2つの.txt ファイルを同一のフォルダに入れておく必要がある. mushroom.txt( キノコの種別データ ) 今回解析対象となる, キノコの特徴が示されているデータである. データの内容については演習用の WEB ページで参照できる. ここではアイテムを1~128までの通し番号で表し, 結果についても番号で出力する. 26
7.1 ファイルの説明 (2) zokusei.txt( 属性値数データ ) キノコの種別データを解析する上で必要になる補助情報である. 特に気にする必要はないが, シミュレーションを実行するためには, このデータが必要となる. out.txt( 出力ファイル ) シミュレーションの結果が出力されるファイルである. 出力されたファイル自動的に作成され, シミュレーションを実行するたびに前に実行された結果は上書きされるため注意すること. 27
7.2 プログラムの実行方法 1. apriori.cpp,mushroom.txt,zokusei.txt を同じフォルダにダウンロード. 2. apriori.cpp のコンパイルを行い ( 警告文は無視してよい ), プログラムを実行する. $ g++ apriori.cpp -o apriori.out -lm $./apriori.out 3. apriori.cpp のコンパイルを行い ( 警告文は無視してよい ), プログラムを実行する. フォルダ内の出力ファイル out.txt に結果が出力されるため, ファイル内を参照する. $ emacs out.txt プログラムで入力する最小支持度, 最小確信度は, 値を変えることで結果が異なるため, 色々試してみるとよい. 28