數(shù)據(jù)挖掘挖掘頻繁模式關(guān)聯(lián)和相關(guān)課件

1、2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)1第5章：挖掘頻繁模式、關(guān)聯(lián)和相關(guān)5.1 基本概念和路線圖5.2 有效的和可伸縮的頻繁項集挖掘方法5.3 挖掘各種類型的關(guān)聯(lián)規(guī)則5.4 由關(guān)聯(lián)挖掘到相關(guān)性分析5.5 基于約束的關(guān)聯(lián)挖掘5.6 小結(jié)2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)2什么是關(guān)聯(lián)挖掘?關(guān)聯(lián)規(guī)則挖掘：在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。應(yīng)用：購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計、賠本銷售分析（loss-leader analysis）、聚集、分類等。舉例： 規(guī)則形式： “Body Head support, confidenc

2、e”.buys(x, “diapers”) buys(x, “beers”) 0.5%, 60%major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)3關(guān)聯(lián)規(guī)則：基本概念給定: (1)交易數(shù)據(jù)庫 (2)每筆交易是：一個項目列表 (消費者一次購買活動中購買的商品)查找: 所有描述一個項目集合與其他項目集合相關(guān)性的規(guī)則E.g., 98% of people who purchase tires and auto accessories also get automotive services done應(yīng)用* 護理用

3、品 (商店應(yīng)該怎樣提高護理用品的銷售？)家用電器 * (其他商品的庫存有什么影響?)在產(chǎn)品直銷中使用附加郵寄2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)4規(guī)則度量：支持度與可信度查找所有的規(guī)則 X & Y Z 具有最小支持度和可信度支持度, s, 一次交易中包含X 、 Y 、 Z的可能性置信度, c, 包含X 、 Y的交易中也包含Z的條件概率設(shè)最小支持度為50%, 最小可信度為 50%, 則可得到A C (50%, 66.6%)C A (50%, 100%)買尿布的客戶二者都買的客戶買啤酒的客戶2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)5關(guān)聯(lián)規(guī)則挖掘：路線圖布爾 vs. 定量 關(guān)聯(lián) (基于規(guī)則中所處理數(shù)據(jù)的

4、值類型)buys(x, “SQLServer”) buys(x, “DMBook”) buys(x, “DBMiner”) 0.2%, 60%age(x, “30.39”) income(x, “42.48K”) buys(x, “PC”) 1%, 75%單維 vs. 多維 關(guān)聯(lián) (基于規(guī)則中涉及的數(shù)據(jù)維)(例子同上)單層 vs. 多層 分析(基于規(guī)則集所涉及的抽象層)那個品種牌子的啤酒與那個牌子的尿布有關(guān)系?各種擴展相關(guān)性、因果分析關(guān)聯(lián)并不一定意味著相關(guān)或因果最大模式和閉合項集2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)6第6章：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則6.1 關(guān)聯(lián)規(guī)則挖掘6.2由事務(wù)數(shù)據(jù)庫挖掘單維

5、布爾關(guān)聯(lián)規(guī)則6.3由事務(wù)數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則6.5由關(guān)聯(lián)挖掘到相關(guān)性分析6.6基于約束的關(guān)聯(lián)挖掘6.7小結(jié)2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)7關(guān)聯(lián)規(guī)則挖掘一個例子對于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%Apriori的基本思想:頻繁項集的任何子集也一定是頻繁的最小值尺度 50%最小可信度 50%2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)8關(guān)鍵步驟：挖掘頻繁集頻繁集:是指滿足最小支持度的項目集合頻繁集的子集也一定是頻繁的如, 如果AB

6、 是頻繁集，則 A B 也一定是頻繁集從1到k（k-頻繁集）遞歸查找頻繁集用得到的頻繁集生成關(guān)聯(lián)規(guī)則2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)9Apriori算法連接: 用 Lk-1自連接得到候選k-項集Ck修剪: 一個k-項集，如果他的一個k-1項集（他的子集 ）不是頻繁的，那他本身也不可能是頻繁的。偽代碼:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = frequent items;for (k = 2; Lk-1 !=; k+) do begin Ck = candidates generated from

7、Lk-1; for each transaction t in database do increment the count of all candidates in Ck that are contained in t Lk = candidates in Ck with min_support endreturn k Lk;2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)10Apriori算法 例子數(shù)據(jù)庫 D掃描 DC1L1L2C2C2掃描 DC3L3掃描 D2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)11如何生成候選集假定 Lk-1 中的項按順序排列第一步: 自連接 Lk-1 insert into Ck

8、select p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1第二步: 修剪For all itemsets c in Ck doFor all (k-1)-subsets s of c doif (s is not in Lk-1) then delete c from Ck2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)12計算支持度為什么會成為一個問題？候選集的個數(shù)非常巨大 一筆交易可能包含多個候選集2

9、022/8/7數(shù)據(jù)挖掘：概念和技術(shù)13生成候選集的例子L3=abc, abd, acd, ace, bcd自連接 : L3*L3abc 和 abd 得到 abcd acd 和 ace 得到 acde修剪:ade 不在 L3中，刪除 acdeC4=abcd2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)14提高Apriori效率的方法1.基于Hash的項集計數(shù): 若 k-項集在hash-tree的路徑上的一個計數(shù)值低于閾值，那他本身也不可能是頻繁的。(157頁圖6-6)2.減少交易記錄: 不包含任何頻繁k-項集的交易也不可能包含任何大于k的頻繁集，下一步計算時刪除這些記錄。3.劃分: 一個項集要想在整個數(shù)據(jù)

10、庫中是頻繁的，那么他至少在數(shù)據(jù)庫的一個分割上是頻繁的。 兩次掃描數(shù)據(jù)。(157頁圖6-7)4.抽樣: 使用小的支持度+完整性驗證方法。在小的抽樣集上找到局部頻繁項集，然后在全部數(shù)據(jù)集找頻繁項集。5.動態(tài)項集計數(shù): 在添加一個新的候選集之前，先估計一下是不是他的所有子集都是頻繁的。2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)15Apriori 夠快了嗎? 性能瓶頸Apriori算法的核心:用頻繁的(k 1)-項集生成候選的頻繁 k-項集用數(shù)據(jù)庫掃描和模式匹配計算候選集的支持度Apriori 的瓶頸: 候選集生成巨大的候選集:104 個頻繁1-項集要生成 107 個候選 2-項集要找尺寸為100的頻繁模式

11、，如 a1, a2, , a100, 你必須先產(chǎn)生2100 1030 個候選集多次掃描數(shù)據(jù)庫： 如果最長的模式是n的話，則需要 (n +1 ) 次數(shù)據(jù)庫掃描2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)16挖掘頻繁集 不用生成候選集頻繁模式增長 (FP-增長)用Frequent-Pattern tree (FP-tree) 結(jié)構(gòu)壓縮數(shù)據(jù)庫, 高度濃縮，同時對頻繁集的挖掘又完備的避免代價較高的數(shù)據(jù)庫掃描 開發(fā)一種高效的基于FP-tree的頻繁集挖掘算法采用分而治之的方法學：分解數(shù)據(jù)挖掘任務(wù)為小任務(wù)避免生成關(guān)聯(lián)規(guī)則: 分別挖掘條件數(shù)據(jù)庫2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)17用 FP-tree挖掘頻繁集基本

12、思想 (分而治之)用FP-tree地歸增長頻繁集方法 對每個項，生成它的 條件模式庫, 然后是它的 條件 FP-tree對每個新生成的條件FP-tree，重復這個步驟直到結(jié)果FP-tree為空, 或只含維一的一個路徑 (此路徑的每個子路徑對應(yīng)的相集都是頻繁集)2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)18挖掘 FP-tree的主要步驟為FP-tree中的每個節(jié)點生成條件模式庫用條件模式庫構(gòu)造對應(yīng)的條件FP-tree遞歸構(gòu)造條件 FP-trees 同時增長其包含的頻繁集如果條件FP-tree直包含一個路徑，則直接生成所包含的頻繁集。2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)19步驟1: 建立 FP-tree

13、 （159頁圖6-8）從FP-tree的頭表開始按照每個頻繁項的連接遍歷 FP-tree列出能夠到達此項的所有前綴路徑，得到條件模式庫步驟2:建立條件FP-tree進行挖掘（159頁圖6-9）對每個模式庫計算庫中每個項的支持度用模式庫中的頻繁項建立FP-tree2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)20為什么 頻繁集增長 速度快？性能研究顯示FP-growth 比Apriori快一個數(shù)量級, 同樣也比 tree-projection 快。原因不生成候選集，不用候選測試。使用緊縮的數(shù)據(jù)結(jié)構(gòu)避免重復數(shù)據(jù)庫掃描基本操作是計數(shù)和建立 FP-tree 樹2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)21FP-gro

14、wth vs. Apriori: 相對于支持度的擴展性Data set T25I20D10K2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)22FP-growth vs. Tree-Projection:相對于支持度的擴展性Data set T25I20D100K2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)23關(guān)聯(lián)規(guī)則結(jié)果顯示 (Table Form )2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)24關(guān)聯(lián)規(guī)則可視化Using Plane Graph2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)25關(guān)聯(lián)規(guī)則可視化Using Rule Graph2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)26第6章：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則6.1 關(guān)聯(lián)規(guī)則挖

15、掘6.2由事務(wù)數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則6.3由事務(wù)數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則6.5由關(guān)聯(lián)挖掘到相關(guān)性分析6.6基于約束的關(guān)聯(lián)挖掘6.7小結(jié)2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)27多層關(guān)聯(lián)規(guī)則項通常具有層次底層的項通常支持度也低某些特定層的規(guī)則可能更有意義交易數(shù)據(jù)庫可以按照維或?qū)泳幋a可以進行共享的多維挖掘食品面包牛奶脫脂奶光明統(tǒng)一酸奶白黃2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)28挖掘多層關(guān)聯(lián)規(guī)則自上而下，深度優(yōu)先的方法：先找高層的“強”規(guī)則：牛奶 面包 20%, 60%.再找他們底層的“弱”規(guī)則：酸奶 黃面包 6%, 50%.多層關(guān)聯(lián)規(guī)則的變種1 支持度不

16、變: 在各層之間使用統(tǒng)一的支持度（164頁圖6-12）+ 一個最小支持度閾值. 如果一個項集的父項集不具有最小支持度，那他本身也不可能滿足最小支持度。 底層項不會成為頻繁集，如果支持度太高 丟失底層關(guān)聯(lián)規(guī)則太低 生成太多的高層關(guān)聯(lián)規(guī)則2 支持度遞減: 隨著層次的降低支持度遞減（164頁圖6-13）2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)29多層關(guān)聯(lián)規(guī)則: 支持度不變 vs. 支持度遞減3層次交叉單項過濾： （165頁圖6-14）4層次交叉K-項過濾： （165頁圖6-15）4種搜索策略：層與層獨立用k-項集跨層過濾用項跨層過濾用項進行可控跨層過濾2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)30支持度不變支

17、持度不變多層挖掘牛奶support = 10%酸奶 support = 6%脫脂奶support = 4%層 1min_sup = 5%層 2min_sup = 5%2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)31支持度遞減支持度遞減多層挖掘酸奶 support = 6%脫脂奶 support = 4%層 1min_sup = 5%層 2min_sup = 3%牛奶support = 10%2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)32多層關(guān)聯(lián)：冗余過濾由于“祖先”關(guān)系的原因，有些規(guī)則可能是多余的。例子奶制品 白面包 support = 8%, confidence = 70%酸奶 白面包 support

18、= 2%, confidence = 72%酸奶占奶制品25%我們稱第一個規(guī)則是第二個規(guī)則的祖先參考規(guī)則的祖先，如果他的支持度與我們“預期”的支持度近似的話，我們就說這條規(guī)則是冗余的。2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)33數(shù)據(jù)挖掘查詢的逐步精化為什么要逐步精化挖掘操作的代價可能高或低，結(jié)果可能過細致或粗糙在速度和質(zhì)量之間折衷：逐步精化超集覆蓋特征：預存儲所有正面答案允許進一步正確性驗證，而不必驗證已經(jīng)錯誤的2或多步挖掘：先執(zhí)行粗糙的、容易的操作 (超集覆蓋)然后在減少后的候選集上進行計算量大的算法 (Koperski & Han, SSD95).2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)34第6章

19、：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則6.1 關(guān)聯(lián)規(guī)則挖掘6.2由事務(wù)數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則6.3由事務(wù)數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則6.5由關(guān)聯(lián)挖掘到相關(guān)性分析6.6基于約束的關(guān)聯(lián)挖掘6.7小結(jié)2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)35多維關(guān)聯(lián)規(guī)則： 概念單維規(guī)則：buys(X, “milk”) buys(X, “bread”)多維規(guī)則： 2個以上維/謂詞維間關(guān)聯(lián)規(guī)則 (維詞不重復)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)混合維關(guān)聯(lián)規(guī)則 (維詞重復)age(X,”19-25”) buys(X, “po

20、pcorn”) buys(X, “coke”)類別屬性有限個值, 值之間無順序關(guān)系數(shù)量屬性數(shù)字的，值之間隱含了順序關(guān)系2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)36挖掘多維關(guān)聯(lián)的技術(shù)搜索頻繁k-維詞集合：如: age, occupation, buys 是一個3-維詞集合。按照對 age 處理方式的不同，分為：1. 用靜態(tài)方法把數(shù)值屬性離散化數(shù)值屬性可用預定義的概念層次加以離散化。2. 帶數(shù)量的關(guān)聯(lián)規(guī)則根據(jù)數(shù)據(jù)的分布，動態(tài)的把數(shù)值屬性離散化到不同的“箱”。3. 基于距離的關(guān)聯(lián)規(guī)則用數(shù)據(jù)點之間的距離動態(tài)的離散化2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)37數(shù)值屬性的靜態(tài)離散化在挖掘之前用概念層次先離散化數(shù)值

21、被替換為區(qū)間范圍關(guān)系數(shù)據(jù)庫中，要找到所有頻繁k-維詞需要k或k+1次表掃描。適宜使用數(shù)據(jù)立方體N維立方體的每個單元 對應(yīng)一個維詞集合使用數(shù)據(jù)立方體速度更快(income)(age)()(buys)(age, income)(age,buys)(income,buys)(age,income,buys)2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)38帶數(shù)量的關(guān)聯(lián)規(guī)則age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high resolution TV”)動態(tài) 離散化數(shù)值屬性使?jié)M足某種挖掘標準，如最大化挖掘規(guī)則的置信度緊湊性.2-維數(shù)量關(guān)聯(lián)規(guī)則： Aquan1 Aq

22、uan2 Acat用2-維表格把“鄰近”的關(guān)聯(lián)規(guī)則組合起來例子 2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)39ARCS (關(guān)聯(lián)規(guī)則聚集系統(tǒng)) （170頁圖6-18）ARCS 流程1. 分箱2. 查找頻繁維詞 集合3. 關(guān)聯(lián)規(guī)則聚類4. 優(yōu)化2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)40ARCS的局限性數(shù)值屬性只能出現(xiàn)在規(guī)則的左側(cè)左側(cè)只能有兩個屬性 (2維)ARCS 的改進不用基于柵格的方法等深分箱基于局部完整性 測度的聚集“Mining Quantitative Association Rules in Large Relational Tables” by R. Srikant and R. Agraw

23、al.2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)41挖掘基于距離的關(guān)聯(lián)規(guī)則分箱的方法沒有體現(xiàn)數(shù)據(jù)間隔的語義基于距離的分割是更有“意義”的離散化方法，考慮：區(qū)間內(nèi)密度或點的個數(shù)區(qū)間內(nèi)點的“緊密程度2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)42第6章：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則6.1 關(guān)聯(lián)規(guī)則挖掘6.2由事務(wù)數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則6.3由事務(wù)數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則6.5由關(guān)聯(lián)挖掘到相關(guān)性分析6.6基于約束的關(guān)聯(lián)挖掘6.7小結(jié)2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)43強關(guān)聯(lián)規(guī)則不一定是有趣的（168例5.8）由關(guān)聯(lián)分析到相關(guān)分析 項集A與項集B獨立 P(AB)=P(A

24、)P(B) 項集A、B的相關(guān)性提升度 corrAB=P(AB)/P(A)P(B)（169頁例5.9）卡方分析 卡方值 （169頁例5.10）全置信度 余弦度量比較四種相關(guān)度量 （170頁例5.11）2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)44第6章：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則6.1 關(guān)聯(lián)規(guī)則挖掘6.2由事務(wù)數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則6.3由事務(wù)數(shù)據(jù)庫挖掘多層關(guān)聯(lián)規(guī)則6.4由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則6.5由關(guān)聯(lián)挖掘到相關(guān)性分析6.6基于約束的關(guān)聯(lián)挖掘6.7小結(jié)2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)456.6.1 基于約束的挖掘使用約束的必要性在數(shù)據(jù)挖掘中常使用的幾種約束：知識類型約束：指定要

25、挖掘的知識類型 如關(guān)聯(lián)規(guī)則數(shù)據(jù)約束： 指定與任務(wù)相關(guān)的數(shù)據(jù)集 Find product pairs sold together in Vancouver in Dec.98.維/層次約束:指定所用的維或概念結(jié)構(gòu)中的層in relevance to region, price, brand, customer category.規(guī)則約束：指定要挖掘的規(guī)則形式(如規(guī)則模板)單價 (price $200).興趣度約束：指定規(guī)則興趣度閾值或統(tǒng)計度量如 (min_support 3%, min_confidence 60%).2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)46假定AllElectronics的一個

26、銷售多維數(shù)據(jù)庫有如下關(guān)系(176頁)Sales(customer_name,item_name,transaction_id)Lives(customer_name,region,city)Items(item_name,category，price)Transaction(transaction_id,day,month,year) (1) mine associations as (2)lives(C,_,”Pudong”)sales(C,I,S)=sales(C,JT) (3) from sales (4)where S.year=1999 &T.year=1999 &I.categor

27、y=J.category (5)group by C,I.category (6)having sum(I.price=500 (7)with support threshold=1% (8)with confidence threshold=50%Lives(C,_,”Pudong”)Sales(C,”Census_CD”,_)Sales(C,”MS/Office”,_)=Sales(C,”MS/SQLSever”,_) 1.5%,65%2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)476.6.2 約束的分類單調(diào)性約束(monotone constraint)反單調(diào)性約束(anti-monotone

28、constraint)可轉(zhuǎn)變的約束(convertibale constraint)簡潔性約束(succinct constraint)不可轉(zhuǎn)變的約束(non-convertibale constraint)2022/8/7數(shù)據(jù)挖掘：概念和技術(shù)48約束的有關(guān)概念項目集：I=i1,i2,im,交易：T=模式S是項目集的子集，S=ij1,ij2,ijk模式S包含與T,T=,iff S=It; S是S的子模式(subpattern)且S 是S的超模式(superpattern)，if 有S=v ， v是S的一個項集約束Cm 是單調(diào)的iff.對于任給的滿足Cm的項集(模式) S, 每一個S的超集都能夠

29、滿足 Cm e.g: Cm : min(S)=v, v是S的一個項集第九章 數(shù)據(jù)挖掘的應(yīng)用和發(fā)展趨勢9.1 復雜數(shù)據(jù)對象的多維分析和描述性挖掘9.2 空間數(shù)據(jù)挖掘9.3 多媒體數(shù)據(jù)挖掘9.4 時序數(shù)據(jù)和序列數(shù)據(jù)的挖掘9.5 文本數(shù)據(jù)庫挖掘9.6 Web挖掘9.1 復雜數(shù)據(jù)對象的多維分析和描述性挖掘結(jié)構(gòu)化數(shù)據(jù)的概化空間和多媒體數(shù)據(jù)概化中的聚集和近似計算對象標識符和類/子類層次的概化類復合層次的概化對象立方體的構(gòu)造與挖掘用分而治之方法對規(guī)劃數(shù)據(jù)庫進行基于概化的挖掘9.2 空間數(shù)據(jù)挖掘空間數(shù)據(jù)立方體構(gòu)造和空間OLAP空間關(guān)聯(lián)分析空間聚類方法空間分類和空間趨勢分析光柵數(shù)據(jù)庫挖掘9.3 多媒體數(shù)據(jù)挖掘多

30、媒體數(shù)據(jù)的相似性搜索 基于顏色直方圖的特征標識；多特征構(gòu)成的特征標識；基于小波的特征標識；帶有區(qū)域粒度的小波特征表識多媒體數(shù)據(jù)的多維分析多媒體數(shù)據(jù)的分類和預測分析多媒體數(shù)據(jù)中的關(guān)聯(lián)規(guī)則挖掘9.4 時序數(shù)據(jù)和序列數(shù)據(jù)的挖掘趨勢分析 長期或趨勢變化；循環(huán)變動或循環(huán)變化； 季節(jié)性變動或季節(jié)性變化；非規(guī)則或隨機變化時序分析中的相似搜索序列模式挖掘周期分析 挖掘全周期模式；挖掘部分周期模式； 挖掘循環(huán)或周期關(guān)聯(lián)規(guī)則。9.5 文本數(shù)據(jù)庫挖掘文本數(shù)據(jù)分析和信息檢索 研究大量文本文檔的信息組織和檢索 基本度量：查準率；查全率。文本挖掘：基于關(guān)鍵字的關(guān)聯(lián)和文檔分類9.6 Web挖掘挖掘Web鏈接結(jié)構(gòu)，識別權(quán)威W

31、eb頁面Web文檔的自動分類多層Web信息庫的構(gòu)造Web使用記錄的挖掘第十章 數(shù)據(jù)挖掘的應(yīng)用和發(fā)展趨勢10.1 數(shù)據(jù)挖掘的應(yīng)用10.2 數(shù)據(jù)挖掘系統(tǒng)產(chǎn)品和研究原型10.3 數(shù)據(jù)挖掘的其他主題10.4 數(shù)據(jù)挖掘的社會影響10.5 數(shù)據(jù)挖掘的發(fā)展趨勢10.1 數(shù)據(jù)挖掘的應(yīng)用針對生物醫(yī)學和DNA數(shù)據(jù)分析的數(shù)據(jù)挖掘針對金融數(shù)據(jù)分析的數(shù)據(jù)挖掘零售業(yè)中的數(shù)據(jù)挖掘電信業(yè)中的數(shù)據(jù)挖掘10.2 數(shù)據(jù)挖掘系統(tǒng)產(chǎn)品和研究原型怎樣選擇一個數(shù)據(jù)挖掘系統(tǒng) 數(shù)據(jù)類型；系統(tǒng)問題；數(shù)據(jù)源；數(shù)據(jù)挖掘的功能和方法；數(shù)據(jù)挖掘系統(tǒng)和數(shù)據(jù)倉庫系統(tǒng)的結(jié)合；可伸縮性；可視化工具；數(shù)據(jù)挖掘查詢語言和圖形用戶接口。 商用數(shù)據(jù)挖掘系統(tǒng)的例子 In

32、telligent Miner: IBM Enterprise Miner :SAS; MineSet SGI; Clementine SPSS; DBMiner DBMiner Technology10.3 數(shù)據(jù)挖掘的其他主題可視化數(shù)據(jù)挖掘 數(shù)據(jù)可視化；數(shù)據(jù)挖掘結(jié)果可視化；數(shù)據(jù)挖掘過程可視化；交互式的數(shù)據(jù)挖掘視頻和音頻數(shù)據(jù)挖掘科學和統(tǒng)計數(shù)據(jù)挖掘數(shù)據(jù)挖掘的理論基礎(chǔ)數(shù)據(jù)挖掘和智能查詢應(yīng)答 例10.110.4 數(shù)據(jù)挖掘的社會影響數(shù)據(jù)挖掘是宣傳出來的還是持久的穩(wěn)定增長的商業(yè)數(shù)據(jù)挖掘只是經(jīng)理的事還是每個人的事數(shù)據(jù)挖掘?qū)﹄[私或數(shù)據(jù)安全構(gòu)成威脅么？10.5 數(shù)據(jù)挖掘的發(fā)展趨勢應(yīng)用的探索可伸縮的數(shù)據(jù)挖掘方法

33、數(shù)據(jù)挖掘與數(shù)據(jù)庫系統(tǒng)、數(shù)據(jù)倉庫系統(tǒng)和WEB數(shù)據(jù)庫系統(tǒng)的集成數(shù)據(jù)挖掘語言的標準化可視化數(shù)據(jù)挖掘復雜數(shù)據(jù)類型挖掘的新方法WEB挖掘數(shù)據(jù)挖掘中的隱私保護與數(shù)據(jù)信息安全Chapter 8. 聚類分析什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類分析方法分類劃分方法（Partitioning Methods）分層方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚類方法異常分析總結(jié) 劃分方法: 基本概念劃分方法: 將一個包含n個數(shù)據(jù)對象的數(shù)據(jù)庫組織成k個劃分（k=n），其中每個劃分代表一個簇（Cluster）。給定一個k，要構(gòu)造出k個簇，并滿足采用的劃分準則：全局最優(yōu):盡可能的列舉所有的

34、劃分；啟發(fā)式方法: k-平均和k-中心點算法k-平均 (MacQueen67):由簇的中心來代表簇；k-中心點或 PAM (Partition around medoids) (Kaufman & Rousseeuw87): 每個簇由簇中的某個數(shù)據(jù)對象來代表。 K-平均算法給定k，算法的處理流程如下:1.隨機的把所有對象分配到k個非空的簇中；2.計算每個簇的平均值，并用該平均值代表相應(yīng)的簇；3.將每個對象根據(jù)其與各個簇中心的距離，重新分配到與它最近的簇中； 4.回到第二步，直到不再有新的分配發(fā)生。K-平均算法例子K-平均算法優(yōu)點 相對高效的: 算法復雜度O(tkn), 其中n 是數(shù)據(jù)對象的個數(shù)

35、, k 是簇的個數(shù), t是迭代的次數(shù)，通常k, t n.算法通常終止于局部最優(yōu)解；缺點只有當平均值有意義的情況下才能使用，對于類別字段不適用；必須事先給定要生成的簇的個數(shù)；對“噪聲”和異常數(shù)據(jù)敏感；不能發(fā)現(xiàn)非凸面形狀的數(shù)據(jù)。K-平均算法的變種一些變種在下面幾個方面有所不同：初始k個平均值的選擇；相異度的計算；計算簇的平均值的策略；處理種類字段: k-模算法 (Huang98)用模來替代平均值；用新的相異度計算方法來處理類別字段；用基于頻率的方法來修改簇的模；k-原型算法：綜合k-平均和k-模算法，能同時處理類別字段和數(shù)值字段。K-中心點算法找出簇中位置最中心的對象，即中心點來代表簇PAM (P

36、artitioning Around Medoids, 1987)設(shè)定一個中心點的初始集合，然后反復的用非中心點對象來替代中心點對象，以改進聚類的質(zhì)量；PAM 算法在大數(shù)據(jù)集上效率較低，沒有良好的可伸縮性；CLARA (Kaufmann & Rousseeuw, 1990)CLARANS (Ng & Han, 1994): Randomized samplingPAM (Partitioning Around Medoids) (1987)PAM (Kaufman and Rousseeuw, 1987）用真實的數(shù)據(jù)對象來代表簇隨機選擇k個對象作為初始的中心點；Repeat對每一個由非中心對象

37、h 和中心對象 i, 計算i被h替代的總代價 Tcih 對每一個有h和I組成的對象對 If TCih 0, i 被 h替換然后將每一個非中心點對象根據(jù)與中心點的距離分配給離它最近的中心點Until不發(fā)生變化。PAM Clustering: Total swapping cost TCih=jCjihjihttihjhitjtihjCLARA (Clustering Large Applications) (1990)CLARA (Kaufmann and Rousseeuw in 1990)該算法首先獲得數(shù)據(jù)集的多個采樣，然后在每個采樣上使用PAM算法，最后返回最好的聚類結(jié)果作為輸出。優(yōu)點:

38、能夠處理大數(shù)據(jù)集。缺點:效率依賴于采樣的大??；如果樣本發(fā)生偏斜，基于樣本的一個好的聚類不一定代表得了整個數(shù)據(jù)集合的一個好的聚類；CLARANS (“Randomized” CLARA) (1994)CLARANS (A Clustering Algorithm based on Randomized Search) (Ng and Han94)CLARANS 在搜索的每一步動態(tài)的抽取一個樣本；聚類過程可以被描述為對一個圖的搜索，圖中的每個節(jié)點是一個潛在的解，即k個中心點的集合；在替換 了一個中心點后的結(jié)果被稱為當前結(jié)果的鄰居。如果找到了一個局部最優(yōu)，算法從隨即選擇的節(jié)點開始尋找新的局部最優(yōu)；比

39、PAM 和 CLARA更有效和有更好的伸縮性；采用聚焦技術(shù)和空間數(shù)據(jù)結(jié)構(gòu)等能進一步提高性能(Ester et al.95)Chapter 8. Cluster Analysis什么是聚類分析?聚類分析中的數(shù)據(jù)類型主要聚類分析方法分類劃分方法（Partitioning Methods）分層方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚類方法異常分析總結(jié)層次方法采用距離作為衡量聚類的標準。該方法不在需要指定聚類的個數(shù)，但用戶可以指定希望得到的簇的數(shù)目作為一個結(jié)束條件。Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d

40、eStep 4Step 3Step 2Step 1Step 0agglomerative(AGNES)divisive(DIANA)AGNES (Agglomerative Nesting)由 Kaufmann 和 Rousseeuw 提出；(1990)使用單鏈接方法和差異度矩陣； 合并那些具有最小差異度的節(jié)點；Go on in a non-descending fashion最后所有的對象合并形成一個簇。A Dendrogram Shows How the Clusters are Merged HierarchicallyDecompose data objects into a seve

41、ral levels of nested partitioning (tree of clusters), called a dendrogram. A clustering of the data objects is obtained by cutting the dendrogram at the desired level, then each connected component forms a cluster.DIANA (Divisive Analysis)由 Kaufmann 和 Rousseeuw 提出(1990)AGNES算法的逆過程；最終每個新的簇只包含一個對象；Mor

42、e on Hierarchical Clustering Methods層次方法的主要缺點：沒有良好的伸縮性: 時間復雜度至少是 O(n2)一旦一個合并或分裂被執(zhí)行，就不能修復；綜合層次聚類和其它的聚類技術(shù)：BIRCH (1996): uses CF-tree and incrementally adjusts the quality of sub-clustersCURE (1998): selects well-scattered points from the cluster and then shrinks them towards the center of the cluster

43、by a specified fractionCHAMELEON (1999): hierarchical clustering using dynamic modelingBIRCH (1996)Birch: Balanced Iterative Reducing and Clustering using Hierarchies, by Zhang, Ramakrishnan, Livny (SIGMOD96)增量的構(gòu)造一個CF樹Phase 1: 掃描數(shù)據(jù)庫，建立一個初始存放于內(nèi)存的CF樹，它可以被看作數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類結(jié)構(gòu)； Phase 2: 采用某個聚類算法對CF樹的葉子節(jié)點進行聚類；可伸縮性: 數(shù)據(jù)集合的單