Finding g Interesting Associations without Support Pruning Cohen, E., Datar, M., Fujiwara, S., Gionis, A., Indyk, P., Motwani, R., ... & Yang, C. Knowledge and Data Engineering, IEEE Transactions on, 13(1), 64-78, 2001 担当 ⼩中 (April 29, 29 2015) 1 Section Description • 関連規則の抽出 • 確信度と類似度 • アルゴリズムの挙動概要 • 関連⼿法の紹介 1 INTRODUCTION 2 MOTIVATION 3 MIN-HASHING MIN HASHING SCHEMES • MinHashの基本アイデア • 確率＝Jaccard係数の証明 • Row-Sorting/Hash-Count • K-MinHash Algorithm 4 LOCALITY-SENSITIVE HASHING SCHEMES • Min-LSHとパラメータ選択 • Hamming-LSH 5 EXPERIMENTS • 実験環境 • 実験結果 6 EXTENSION TO HIGH CONFIDENCE HIGH-CONFIDENCE ASSOCIATION RULES 7 MORE EXTENSIONS AND FURTHER WORK 8 SUMMARY • 本研究の⽬的 • 本稿の狙いと，相関ルールの確信度の定義 ， • 処理の流れ • 今後の展望 • 扱った問題 • 各アルゴリズムの概要 2 Section Description • 関連規則の抽出 • 確信度と類似度 • アルゴリズムの挙動概要 • 関連⼿法の紹介 1 INTRODUCTION 2 MOTIVATION 3 MIN-HASHING MIN HASHING SCHEMES • MinHashの基本アイデア • 確率＝Jaccard係数の証明 • Row-Sorting/Hash-Count • K-MinHash Algorithm 4 LOCALITY-SENSITIVE HASHING SCHEMES • Min-LSHとパラメータ選択 • Hamming-LSH 5 EXPERIMENTS • 実験環境 • 実験結果 6 EXTENSION TO HIGH CONFIDENCE HIGH-CONFIDENCE ASSOCIATION RULES 7 MORE EXTENSIONS AND FURTHER WORK 8 SUMMARY • 本研究の⽬的 • 本稿の狙いと，相関ルールの確信度の定義 ， • 処理の流れ • 今後の展望 • 扱った問題 • 各アルゴリズムの概要 3 相関ルールの抽出 • アプリオリが⾮常に有⽤ ‒ 抽出可能：⾼頻度の相関ルール Clustering – 抽出不可能：低頻度の相関ルール Association R l Rules 確信度がどんなに⾼くても beer&diaper caviar&vodka Copy Detection Text Mining Data Mining Collaborative Filtering The people The rich 4 確信度と類似度 5 アルゴリズムの挙動概要 1 Compute signatures 2 Generate candidates hash h h signaturesから i t から candidate pairsを⽣成 3 Prune candidates did t pairsが本当に i が本当に candidate 類似するかどうかの確認 元のテーブルに別のpassを ⽣成 各candidate pairに関して， 類似度を決定 6 関連⼿法（MinHash, LSH） ハッシュ法への要求 • 速度，精度 速度 精度 • ⼩さい signature の⽣成 false- の定義 正解 不正解 正解 truepositive falsepositive 不正解 falsefalse negative truetrue negative false-positive, g false-negativeの削減 MinHash LSH 精度が⾼い 速い 遅い 精度が低い 7 Section Description • 関連規則の抽出 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 • 本研究の⽬的 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 3 MIN-HASHING MIN HASHING SCHEMES • MinHashの基本アイデア • 確率＝Jaccard係数の証明 • Row-Sorting/Hash-Count • K-MinHash Algorithm 4 LOCALITY-SENSITIVE HASHING SCHEMES • Min-LSHとパラメータ選択 • Hamming-LSH 5 EXPERIMENTS • 実験環境 • 実験結果 6 EXTENSION TO HIGH CONFIDENCE HIGH-CONFIDENCE ASSOCIATION RULES 7 MORE EXTENSIONS AND FURTHER WORK 8 SUMMARY 1 INTRODUCTION 2 MOTIVATION • 本稿の狙いと，相関ルールの確信度の定義 ， • 処理の流れ • 今後の展望 • 扱った問題 • 各アルゴリズムの概要 8 MinHashのアイデア random d permutation 9 本当に確率でJaccard係数を推定できるのか？ 列数 1 n 0 0 1 1 0 0 ? 10 同じルールの下で並べ替えているので， 元の集合同⼠での列の対応関係が保存 されている 列数 列数 1 n 0 0 1 1 0 0 1 0 1 n 0 11 各列が ∩ に所属する確率 列数 1 0 1 n 0 12 証明 13 Phase1：Compute signatures 1 1 0 1 1 0 0 1 1 0 0 1 2 2 3 1 1 4 Jaccard係数 ハッシュ関数の 追加で解決 Jaccard推定量 14 なぜ推定量が有効なのか？ 15 証明 16 Phase2：Generation candidates ⾼速化のために，類似度の⾼そうな候補集合だけが欲しい 1 Row-Sorting 1.Row-Sorting 2.Hash-Count k Mi H hとほぼ同じ k-MinHashとほぼ同じ 17 Row-Sorting 18 Hash-Count 2 2 3 1 1 4 19 Hash-Count 2 2 3 1 1 4 20 K-MinHash 1 Compute signatures 2 Generate candidates 3 Prune candidates 21 Section Description • 関連規則の抽出 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 • 本研究の⽬的 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 3 MIN-HASHING MIN HASHING SCHEMES • MinHashの基本アイデア • 確率＝Jaccard係数の証明 • Row-Sorting/Hash-Count • K-MinHash Algorithm 4 LOCALITY-SENSITIVE HASHING SCHEMES • Min-LSHとパラメータ選択 • Hamming-LSH 5 EXPERIMENTS • 実験環境 • 実験結果 6 EXTENSION TO HIGH CONFIDENCE HIGH-CONFIDENCE ASSOCIATION RULES 7 MORE EXTENSIONS AND FURTHER WORK 8 SUMMARY 1 INTRODUCTION 2 MOTIVATION • 本稿の狙いと，相関ルールの確信度の定義 ， • 処理の流れ • 今後の展望 • 扱った問題 • 各アルゴリズムの概要 22 Min-LSHとパラメータ選択1 23 Min-LSHとパラメータ選択1 24 Min-LSHとパラメータ選択2 f l false-negativeの期待値 ti の期待値 false-positiveの期待値 25 Hamming-LSH 密度の増加とともに⾏列の並びを計算 ハミング距離 等しい⽂字数を持つ 2つの⽂字列において， 対応する位置にある 異なった⽂字の総数 (Wiki) 26 Section Description • 関連規則の抽出 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 • 本研究の⽬的 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 3 MIN-HASHING MIN HASHING SCHEMES • MinHashの基本アイデア • 確率＝Jaccard係数の証明 • Row-Sorting/Hash-Count • K-MinHash Algorithm 4 LOCALITY-SENSITIVE HASHING SCHEMES • Min-LSHとパラメータ選択 • Hamming-LSH 5 EXPERIMENTS • 実験環境 • 実験結果 6 EXTENSION TO HIGH CONFIDENCE HIGH-CONFIDENCE ASSOCIATION RULES 7 MORE EXTENSIONS AND FURTHER WORK 8 SUMMARY 1 INTRODUCTION 2 MOTIVATION • 本稿の狙いと，相関ルールの確信度の定義 ， • 処理の流れ • 今後の展望 • 扱った問題 • 各アルゴリズムの概要 27 実験環境 MH, K-MH, M-LSH, H-LSHの⽐較 アプリオリとの⽐較 使⽤コーパス 使⽤コ パス Reuter Press synthetic data real data 列数 ⾏数 列の密度 その他 Sun Microsystems Web serverの9 ⽇間のHTTPリクエストのログ． 列はURL，⾏はクライアントIP． 28 Fig.4 Running times for news article data set アプリオリと同じペアを，アプリオリより⾼速に抽出している． アプリオリで抽出できていない閾値0.01%でも抽出している． 29 Fig.5a & Fig.6a Fig.5a Fig.6a kの増加に伴って，S字カーブが鋭くなっている ⇒ 質が⾼まっている 30 Fig.5c & Fig.6c Fig.5c Fig.6c s*の増加に伴って，グラフは右にシフトしている 31 Fig.5d & Fig.6d Fig.5d Fig.6d 与えられたkに関して，線形に実⾏時間が減少 ⇒ より少なく より少なくcandidate candidateを⽣成しているため を⽣成しているため 32 Fig.5b & Fig.6b Fig.5b g Fig.6b g 5bは線形増加だが，6bはそうではない ⇒ データがスパースなため． 各列から得られるハッシュ値の数には列の”1” 各列から得られるハッシュ値の数には列の ”1”の数による上界がある． の数による上界がある． 33 Fig.7a & Fig.8a Fig.7a Fig.8a 34 Fig.7c & Fig.8c Fig.7c Fig.8c 35 Fig.7d & Fig.8d Fig.7d Fig.8d 36 Fig.7b & Fig.8b Fig.7b Fig.8b 37 Fig.9a & Fig9c Fig.9a Fig.9c 合計実⾏時間がfalse-negativeの閾値と反⽐例していることを⽰している MH系よりも MH 系よりもLSH LSH系のほうが早いが LSH系のほうが早いが， 系のほうが早いが H-LSH 系のほうが早いが，H LSHは閾値が低い場合はよくない は閾値が低い場合はよくない 38 Fig.9 • false-positiveの数はtolerance limitに反⽐例 g • H-LSH, M-LSHはfalse-negativeの増加を 許容するなら，false-positiveは減少 • MH, K-MHはPhase2とPhase3のトレードオフ の関係があるため，単調ではない • false-negativeを閾値内で維持するには… • kの増加でPhase2に時間を割く • 閾値s*を下げてPhase3でfalse-positiveを増やす s*の値と，それに対応した類似度を 持つcandidateの⽣成がポイント 39 Section Description • 関連規則の抽出 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 • 本研究の⽬的 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 3 MIN-HASHING MIN HASHING SCHEMES • MinHashの基本アイデア • 確率＝Jaccard係数の証明 • Row-Sorting/Hash-Count • K-MinHash Algorithm 4 LOCALITY-SENSITIVE HASHING SCHEMES • Min-LSHとパラメータ選択 • Hamming-LSH 5 EXPERIMENTS • 実験環境 • 実験結果 6 EXTENSION TO HIGH CONFIDENCE HIGH-CONFIDENCE ASSOCIATION RULES 7 MORE EXTENSIONS AND FURTHER WORK 8 SUMMARY 1 INTRODUCTION 2 MOTIVATION • 本稿の狙いと，相関ルールの確信度の定義 ， • 処理の流れ • 今後の展望 • 扱った問題 • 各アルゴリズムの概要 40 本稿の狙いと相関ルールの確信度 アプリオリでは抽出できないような， アプリオリでは抽出できないような 低頻度かつ⾼確信度を持つ相関ルールを サポートを使わずに抽出したい ポ 41 処理の流れ Row Sorting Row-Sorting Hash--Count Hash Countや やM-LSH LSHは は 不適切 42 Section Description • 関連規則の抽出 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 • 本研究の⽬的 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 3 MIN-HASHING MIN HASHING SCHEMES • MinHashの基本アイデア • 確率＝Jaccard係数の証明 • Row-Sorting/Hash-Count • K-MinHash Algorithm 4 LOCALITY-SENSITIVE HASHING SCHEMES • Min-LSHとパラメータ選択 • Hamming-LSH 5 EXPERIMENTS • 実験環境 • 実験結果 6 EXTENSION TO HIGH CONFIDENCE HIGH-CONFIDENCE ASSOCIATION RULES 7 MORE EXTENSIONS AND FURTHER WORK 8 SUMMARY 1 INTRODUCTION 2 MOTIVATION • 本稿の狙いと，相関ルールの確信度の定義 ， • 処理の流れ • 今後の展望 • 扱った問題 • 各アルゴリズムの概要 43 今後の展望 Problem Approach 44 Section Description • 関連規則の抽出 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 • 本研究の⽬的 • 確信度と類似度 • 提案⼿法の概要 • 関連⼿法の紹介 3 MIN-HASHING MIN HASHING SCHEMES • MinHashの基本アイデア • 確率＝Jaccard係数の証明 • Row-Sorting/Hash-Count • K-MinHash Algorithm 4 LOCALITY-SENSITIVE HASHING SCHEMES • Min-LSHとパラメータ選択 • Hamming-LSH 5 EXPERIMENTS • 実験環境 • 実験結果 6 EXTENSION TO HIGH CONFIDENCE HIGH-CONFIDENCE ASSOCIATION RULES 7 MORE EXTENSIONS AND FURTHER WORK 8 SUMMARY 1 INTRODUCTION 2 MOTIVATION • 本稿の狙いと，相関ルールの確信度の定義 ， • 処理の流れ • 今後の展望 • 扱った問題 • 各アルゴリズムの概要 45 サイズがメインメモリに収まる場合 → 実データの使⽤ そうではない場合 → 推定値を使⽤．確率的なcandidate⽣成によりfalse-positiveの除去が可能 推定値を使⽤ 確率的な did t ⽣成によりf l iti の除去が可能 MH(K-MH) M-LSH H-LSH ハッシュキーの連結 各列はハッシュキー連結を⽤いて，何回か 各列はハッシュキー連結を⽤いて 何回か 各列をバケツにハッシュする． もし2列の，あるハッシュ関数によるハッ シュ値が⼀致した場合は，衝突確率が⾼い． 衝突した場合，同じバケツにある全ての列 はcandidateとなる． これにより，MH系の列数の2乗時間を回避 46
© Copyright 2024 ExpyDoc
