Python ではじめる機械学習 12. パターンマイニング

12. パターンマイニング ユーザ（ ⼈） 潜在因⼦（ 個） 商品（ 種類） … ユーザ番号 … ⼥性 … 商品番号 都会暮らし 12.1 「教師なし・パターンマイニング」の問題の定義 12.2 頻出項目抽出 12.3 連想規則抽出 12.4 行列分解 荒木雅弘 : 『Pythonではじめる機械学 習』 （森北出版，2025年） スライドとコード

• https://masahiroaraki.github.io/ja/
• https://www.morikita.co.jp/books/mid/085861
• https://masahiroaraki.github.io/MachineLearning3/

12. パターンマイニング 問題設定 （疎な）ベクトル → 規則性 規則性の例 頻出項目，連想規則，低次元ベクトル 機械学習 教師あり学習 中間的学習 教師なし学習 モデル推定 応用例 推薦システム パターン マイニング

12.1 「教師なし・パターンマイニング」問題の定義 (1/2) データセット（正解なし） {xi } (i = 1, … , N ) （疎な）d 次元のカテゴリまたは数値ベクトル ​ 値が数値でも，順序尺度（例：5段階評価値）のような実質的にはカテゴリとみなせるもの 問題設定1 データセット中で一定頻度以上で現れる特徴の組み合わせや規則を抽出 菓⼦パンとビスケットの 両⽅で True が頻出する リフト値 lift 0.84 その他 ベビー 菓⼦ ビス ⾷料品 ⽤品 パン ケット クーポン ジュース お茶 1.25 ⽔ 0.82 確信度 confidence 0.8 1.2 0.78 ビスケットを買う → 菓⼦パンも買う 0.76 0.74 1.15 1.1 0.72 0.7 0.3 0.35 0.4 0.45 ⽀持度 support (a) スーパーマーケットの購買記録 (b) 抽出された規則 0.5

12.1 「教師なし・パターンマイニング」問題の定義 (2/2) 問題設定2 似ているデータを参考にして，空所の値を予測する ユーザの商品評価 2 4 5 1 1 4 2 5 × 商品の特徴 = 2 4 2 5 3 ⾏列分解 ユーザの特徴

12.2 頻出項目抽出 12.2.1 頻出の基準と問題の難しさ (1/2) 例題：バスケット分析（1件分のデータをトランザクションとよぶ） トランザクション集合中で，一定割合以上出現する項目集合を抽出 No. ミルク パン 1 t t 2 バター 雑誌 t 3 t 4 t t t 5 t t 6 t t

12.2.1 頻出の基準と問題の難しさ (2/2) 頻出の基準：支持度 (support) 全トランザクション数 T に対する，項目集合 items が出現するトランザクション数 Titems の割合 ​ support(items) = Titems T ​ ​ バスケット分析の問題点 すべての可能な項目集合について支持度を計算することは現実的には不可能 商品の種類数 1,000 の店なら，項目集合の数は 21000 高頻度の項目集合に絞って計算を行う必要がある

12.2.2 アプリオリアルゴリズム (1/3) アプリオリな原理: 「ある項目集合が頻出」 ならば 「その部分集合も頻出である」 例） 「パン・ミルク」 が頻出ならば 「パン」 も頻出 対偶：「ある項目集合が頻出でない」 ならば 「その項目集合を含む上位集合も頻 出ではない」 例） 「バター・雑誌」 が頻出でないならば 「バター・雑誌・パン」 も頻出でない

12.2.2 アプリオリアルゴリズム (2/3) アプリオリな原理の対偶を用いて頻出項目集合の候補を削減 {2,3} の項⽬集合が 頻出でないならば 01 計算の⽅向 0 1 2 3 02 03 12 13 013 023 012 0123 23 123 {2,3} を含むこれらも 頻出ではない

12.2.2 アプリオリアルゴリズム (3/3) 頻出項目集合抽出の手順 入力 : 正解なしデータ D ，支持度の閾値 出力 : 頻出項目集合 1. 項目数1の集合 C1 を求める 2. C1 から支持度が閾値以下の要素を削除し，集合 F1 を求める ​ ​ 3. k = 2 から始め，Fk = ∅（空集合）になるまで以下を繰り返す ​ Fk−1 の要素を組み合わせ，項目数 k の集合 Ck を作成する Ck の要素で，その部分集合が Fk−1 に含まれないものを削除する Ck から支持度が閾値以下の要素を削除し，Fk とする ​ ​ ​ ​ ​ ​ 4. 上記ループ終了時点までの Fk の和集合を返す ​

12.2.3 FP-Growth アルゴリズム (1/4) アプリオリアルゴリズムの高速化 トランザクションをコンパクトに表現し，重複計算を避ける 1. トランザクションの前処理 1. トランザクションを出現する特徴名の集合に変換 2. 各集合を出現頻度順にソート 3. 低頻度特徴をフィルタリング 2. prefixを共有する木構造(FP木)に順次挿入 3. FP木を用いて項目集合の出現頻度を高速計算

12.2.3 FP-Growth アルゴリズム (2/4) トランザクションの前処理 トランザクションを出現する特徴名の集合に変換 各集合を出現頻度順にソート 低頻度特徴をフィルタリング 1 {r,z,h,j,p} 1 {z,r} 2 {z,y,x,w,v,u,t,s} 2 {z,x,y,s,t} 3 {z} 3 {z} 4 {r,x,n,o,s} 4 {x,s,r} 5 {y,r,x,z,q,t,p} 5 {z,x,y,r,t} 6 {y,z,x,e,q,s,t,m} 6 {z,x,y,s,t} (a) トランザクション (b) ソート，フィルタリング後のデータ

12.2.3 FP-Growthアルゴリズム (3/4) prefixを共有する木構造(FP木)を作成 ソート，フィルタリング後のトランザクションデータを順次FP木に挿入 {z, r} を挿⼊ {z, x, y, s, t} を挿⼊ r:1 もとの⽊にあるので カウントを増やす z:2 z:1 r:1 x:1 y:1 s:1 t:1 もとの⽊にないので ノードを追加

12.2.3 FP-Growthアルゴリズム (4/4) FP木を用いて項目集合の出現頻度を高速計算 FP⽊ ヘッダテーブル z:5 x:4 y:3 s:3 r:3 t:3 z:5 r:1 x:1 x:3 s:1 y:3 r:1 頻度計算 {x, r} の頻度を求める （頻度の低い r から始める） 親にxがない s:2 r:1 t:2 t:1 親にxがある +1 親にxがある +1

12.3 連想規則抽出 (1/4) 連想規則抽出とは 正解付きデータに対して正解を目的変数とみなし，それに対する入力変数の関係を記述 例 :「商品Aを買った人は商品Ｂも買う傾向がある」というような規則性を抽出したい 評価値の例 確信度: 前提部Aが起こったときに結論部Bが起こる割合 confidence(A → B) = support(A ∪ B) TA∪B = support(A) TA ​ ​ ​ ​ リフト値: Bだけが単独で起こる割合とAが起こったときにBが起こる割合との比 lift(A → B) = confidence(A → B) support(B) ​

12.3 連想規則抽出 (2/4) アプリオリな原理: 「ある項目集合を結論部に持つ規則」が頻出ならば，「その部 分集合を結論部に持つ規則」も頻出である 例）結論部が「パン・ミルク」の規則が頻出ならば，結論部が「パン」の規則も頻出で ある 対偶：「ある項目集合を結論部に持つ規則」が頻出でないならば， 「その上位集合 を結論部に含む規則」も頻出ではない 例） 結論部が「雑誌」の規則が頻出でないならば，結論部が「パン・雑誌」の規則も頻 出ではない

12.3.4 連想規則抽出 (3/4) アプリオリな原理に基づく探索 {3}を結論部に持つ規則 のスコアが低いならば 計算の⽅向 {3}を結論部に含むこれらの 規則のスコアも低いはず

12.3 連想規則抽出 (4/4) 連想規則抽出アルゴリズム 入力 : 頻出項目集合 F , 評価値の閾値 θ 出力 : 連想規則集合 for f in F : for all A ⊂ f : # A は f の真部分集合 B =f ∖A # f から A を除いたもの if 評価値(A ⇒ B ) ≥ θ : 規則 A ⇒ B を連想規則集合に追加 return 連想規則集合

12.4 行列分解 (1/4) 協調フィルタリング アイデア：疎な行列は低次元の行列の積で近似できる 少数の潜在因子を設定し，ユーザや商品の特徴をその潜在因子の重みで表現していると考える 空所の値を予測することにより推薦を行う 商品M種類 数字が埋まっていない ところの値を予測 商品情報M × K ⾏列 ユーザN⼈ × = ユーザ情報N × K ⾏列

12.4 行列分解 (2/4) 潜在因子によるデータ表現の考え方 図中の潜在因子の名前は行列分解の結果を解釈したものに過ぎない xmn = w1n v1m + w2n v2m + ⋯ + wkn vkm ​ ユーザ（ ​ ⼈） ​ ​ ​ 潜在因⼦（ ​ 個） 商品（ ​ 種類） … ユーザ番号 … ⼥性 … 商品番号 都会暮らし

12.4 行列分解 (3/4) 行列分解の方法 X − U V T の最小化問題を解く 1 1 min ∥E∥2F ro = min ∥X − UV T ∥2F ro U ,V 2 U ,V 2 ​ ​ ​ ​ ​ ​ 空欄を値0とみなしてしまっている 値が存在する要素だけに限って二乗誤差を最小化（+正則化） min ∑ (xij − uTi v j )2 + λ1 ∥U ∥2F ro + λ2 ∥V ∥2F ro ​ U ,V ​ ​ ​ ​ ​ ​ ​ ​ (i,j)∈Ω U , V の要素を非負に限定したものが非負値行列因子分解 (NMF : Nonnegative Matrix Factorization)

12.4 行列分解 (4/4) Factorization Machine 補助情報を予測に取り入れることができる行列分解 y = w0 + ∑ wi xi + ∑ v Ti v j xi xj ​ ​ ​ ​ i ​ ​ ​ ​ ​ i<j w0 : 定数項，wi :特徴 xi の重み，v i : 特徴 xi の潜在ベクトル（セルフアテンションと似たア ​ ​ ​ イディア） ​ 商品M種類 予測したい値 ユーザN⼈ ユーザに関する補助情報 ​ 商品に関する補助情報

まとめ パターンマイニングは有用な規則性を発見する アプリオリアルゴリズム 出現頻度の高い項目集合を見つける 出現頻度に基づき，有用な規則を見つける FPGrowth はアプリオリアルゴリズムの高速化版 行列分解 低次元ベクトル表現を見つけることにより，未知の値の予測を行う