【正文】 = (5)group by C, (6)having sum(=100)amp。 Han, SSD’95). 2020/10/5 89 數(shù)據(jù)挖掘：概念和技術(shù) 89第 6章：從大數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則 ? 關(guān)聯(lián)規(guī)則挖掘 ? ? ? ? ? ? 2020/10/5 90 數(shù)據(jù)挖掘：概念和技術(shù) 90多維關(guān)聯(lián)規(guī)則： 概念 ? 單維規(guī)則： buys(X, ―milk‖) ? buys(X, ―bread‖) ? 多維規(guī)則： 2個(gè)以上維 /謂詞 ? 維間關(guān)聯(lián)規(guī)則 (維詞 不重復(fù) ) age(X,‖1925‖) ? occupation(X,―student‖) ? buys(X,―coke‖) ? 混合維關(guān)聯(lián)規(guī)則 (維詞重復(fù) ) age(X,‖1925‖) ? buys(X, ―popcorn‖) ? buys(X, ―coke‖) ? 類別屬性 ? 有限個(gè)值 , 值之間無(wú)順序關(guān)系 ? 數(shù)量屬性 ? 數(shù)字的，值之間隱含了順序關(guān)系 2020/10/5 91 數(shù)據(jù)挖掘：概念和技術(shù) 91挖掘多維關(guān)聯(lián)的技術(shù) ? 搜索頻繁 k維詞集合 ： ? 如 : {age, occupation, buys} 是一個(gè) 3維詞集合。 2020/10/5 74 數(shù)據(jù)挖掘：概念和技術(shù) 74步驟 1: 建立 FPtree （ 159頁(yè)圖 68） ? 從 FPtree的頭表開始 ? 按照每個(gè)頻繁項(xiàng)的連接遍歷 FPtree ? 列出能夠到達(dá)此項(xiàng)的所有前綴路徑，得到條件模式庫(kù) 步驟 2:建立條件 FPtree進(jìn)行挖掘（ 159頁(yè)圖 69） ? 對(duì)每個(gè)模式庫(kù) ? 計(jì)算庫(kù)中每個(gè)項(xiàng)的支持度 ? 用模式庫(kù)中的頻繁項(xiàng)建立 FPtree 2020/10/5 75 數(shù)據(jù)挖掘：概念和技術(shù) 75為什么 頻繁集增長(zhǎng) 速度快？ ? 性能研究顯示 ? FPgrowth 比 Apriori快一個(gè)數(shù)量級(jí) , 同樣也比 treeprojection 快。 2020/10/5 65 數(shù)據(jù)挖掘：概念和技術(shù) 65Apriori算法 — 例子 T ID Ite m s100 1 3 4200 2 3 5300 1 2 3 5400 2 5數(shù)據(jù)庫(kù) D ite m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 4 } 1{ 5 } 3i te m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 5 } 3掃描 D C1 L1 item set{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}ite m s et s up{ 1 2} 1{ 1 3} 2{ 1 5} 1{ 2 3} 2{ 2 5} 3{ 3 5} 2ite m s e t s u p{ 1 3 } 2{ 2 3 } 2{ 2 5 } 3{ 3 5 } 2L2 C2 C2 掃描 D C3 L3 item set{2 3 5}掃描 D ite m s e t s u p{ 2 3 5 } 22020/10/5 66 數(shù)據(jù)挖掘：概念和技術(shù) 66如何生成候選集 ? 假定 Lk1 中的項(xiàng)按順序排列 ? 第一步 : 自連接 Lk1 insert into Ck select , , …, k1, from Lk1 p, Lk1 q where =, …, k2=, ? 第二步 : 修剪 For all itemsets c in Ck do For all (k1)subsets s of c do if (s is not in Lk1) then delete c from Ck 2020/10/5 67 數(shù)據(jù)挖掘：概念和技術(shù) 67? 計(jì)算支持度為什么會(huì)成為一個(gè)問題 ？ ? 候選集的個(gè)數(shù)非常巨大 ? 一筆交易可能包含多個(gè)候選集 2020/10/5 68 數(shù)據(jù)挖掘：概念和技術(shù) 68生成候選集的例子 ? L3={abc, abd, acd, ace, bcd} ? 自連接 : L3*L3 ? abc 和 abd 得到 abcd ? acd 和 ace 得到 acde ? 修剪 : ? ade 不在 L3中，刪除 acde ? C4={abcd} 2020/10/5 69 數(shù)據(jù)挖掘：概念和技術(shù) 69提高 Apriori效率的方法 Hash的項(xiàng)集計(jì)數(shù) : 若 k項(xiàng)集在 hashtree的路徑上的一個(gè)計(jì)數(shù)值低于閾值，那他本身也不可能是頻繁的。 ? 應(yīng)用： ? 購(gòu)物籃分析 、 交叉銷售、產(chǎn)品目錄設(shè)計(jì) 、 賠本銷售分析（ lossleader analysis） 、 聚集、分類等。 ? 將兩個(gè)類別的數(shù)據(jù)概化到相同的層次。 ? 只能分析，不能自動(dòng)的選擇哪些字段和相應(yīng)的概念層次 2020/10/5 8 面向?qū)傩缘臍w納 ? KDD Workshop(89)中提出 ? 不限制于種類字段和特定的匯總方法 ? 方法介紹： ? 使用 SQL等收集相關(guān)數(shù)據(jù) ? 通過數(shù)據(jù)屬性值刪除和屬性值概化來實(shí)現(xiàn)概化 ? 聚集通過合并相等的廣義元組，并累計(jì)他們對(duì)應(yīng)的計(jì)數(shù)值進(jìn)行 ? 和使用者之間交互式的呈現(xiàn)方式 . 2020/10/5 9 基本方法 ? 數(shù)據(jù)聚焦 :選擇和當(dāng)前分析相關(guān)的數(shù)據(jù)，包括維。 ? 結(jié)果的表示 :概化關(guān)系、交叉表、 3D立方體 2020/10/5 11 示例 ? DMQL: use Big_University_DB mine characteristics as “Science_Students” in relevance to name, gender, major, birth_place, birth_date, residence, phone, gpa from student where status in “graduate” ? 相應(yīng)的 SQL: Select name, gender, major, birth_place, birth_date, residence, phone, gpa from student where status in {“Msc”, “MBA”, “PhD” } 2020/10/5 12 類特征化：示例 N am e G en d er M ajo r B irt h P la ce B irt h _d ate R esid e n ce P h on e G P AJimW o od m an M C S V an cou ve r, B C ,C an ad a 81 2 76 35 1 1 M a in S t. ,R ich m on d68 7 45 9 8 3. 6 7S cot tL ach an ce M C S M on tr e al, Q u e,C an ad a28 7 7 5 34 5 1 st A v e. ,R ich m on d25 3 91 0 6 3. 7 0L au r a L ee… F…P h ys ics…Se a t t le , W A , U SA…25 8 7 0…1 2 5 A ust in A v e .,B ur na by…42 0 52 3 2…3. 8 3…R e m o v e d R e t a ine d Sc i,E ng ,B usC ou n tr y A ge ran ge C ity R em oved E xc l,V G , . .G e n d e r M a j o r B i r t h _ r e g i o n A g e _ r a n g e R e s i d e n c e G P A C o u n t M S c i e n c e C a n a d a 2 0 2 5 R i c h mo n d V e r y g o o d 1 6 F S c i e n c e F o r e i g n 2 5 3 0 B u r n a b y E x c e l l e n t 2 2 … … … … … … … B i r t h _ R e g i o nG e n d e rC a n a d a F o r e i g n To t a l M 1 6 1 4 3 0 F 1 0 2 2 3 2 T o t a l 2 6 3 6 6 2Prime Generalized Relation Initial Relation 2020/10/5 13 概化結(jié)果的表示 ? 概化關(guān)系 : ? 一個(gè)表格，其中有屬性字段，后附匯總方法。 ? 概念描述：只有正樣本。 Lk1 !=?。在小的抽樣集上找到局部頻繁項(xiàng)集，然后在全部數(shù)據(jù)集找頻繁項(xiàng)集。 ? – 底層項(xiàng)不會(huì)成為頻繁集，如果支持度 ? 太高 ? 丟失底層關(guān)聯(lián)規(guī)則 ? 太低 ? 生成太多的高層關(guān)聯(lián)規(guī)則 2 支持度遞減 : 隨著層次的降低支持度遞減 （ 164頁(yè)圖 613） 2020/10/5 84 數(shù)據(jù)挖掘：概念和技術(shù) 84多層關(guān)聯(lián)規(guī)則 : 支持度不變 vs. 支持度遞減 3層次交叉單項(xiàng)過濾 ： （ 165頁(yè)圖 614） 4層次交叉 K項(xiàng)過濾 ： （ 165頁(yè)圖 615） ? 4種搜索策略： ? 層與層獨(dú)立 ? 用 k項(xiàng)集跨層過濾 ? 用項(xiàng)跨層過濾 ? 用項(xiàng)進(jìn)行可控跨層過濾 2020/10/5 85 數(shù)據(jù)挖掘：概念和技術(shù) 85支持度不變 支持度不變多層挖掘 牛奶 [support = 10%] 酸奶 [support = 6%] 脫脂奶 [support = 4%] 層 1 min_sup = 5% 層 2 min_sup = 5% 2020/10/5 86 數(shù)據(jù)挖掘：概念和技術(shù) 86支持度遞減 支持度遞減多層挖掘 酸奶 [support = 6%] 脫脂奶 [support = 4%] 層 1 min_sup = 5% 層 2 min_sup = 3% 牛奶 [support = 10%] 2020/10/5 87 數(shù)據(jù)挖掘：概念和技術(shù) 87多層關(guān)聯(lián)：冗余過濾 ? 由于“祖先”關(guān)系的原因，有些規(guī)則可能是多余的。amp。 S’是 S的子模式 (subpattern)且 S 是 S’的超模式(superpattern)， if 有 S’=S. 2020/10/5 104 數(shù)據(jù)挖掘：概念和技術(shù) 104約束的有關(guān)概念（續(xù)） ? 定義約束 : C是作用于項(xiàng)目集 I的冪集 (powerset)上的謂詞 ,C(S)=True/False。 3. 基于距離的關(guān)聯(lián)規(guī)則 ? 用數(shù)據(jù)點(diǎn)之間的距離動(dòng)態(tài)的離散化 2020/10/5 92 數(shù)據(jù)挖掘：概念和技術(shù) 92數(shù)值屬性的靜態(tài)離散化 ? 在挖掘之前用概念層次先離散化 ? 數(shù)值被替換為區(qū)間范圍 ? 關(guān)系數(shù)據(jù)庫(kù)中，要找到所有頻繁 k維詞需要 k或 k+1次表掃描。 面包 [20%, 60%]. ? 再找他們底層的“弱”規(guī)則： 酸奶 174。 兩次掃描數(shù)據(jù)。 ? 偽代碼 : Ck: Candidate itemset of size k