【正文】 治之 ) ? 用 FPtree地歸增長頻繁集 ? 方法 ? 對每個項，生成它的 條件模式庫 , 然后是它的 條件 FPtree ? 對每個新生成的條件 FPtree， 重復這個步驟 ? 直到結果 FPtree為 空 , 或只含 維一的一個路徑 (此路徑的每個子路徑對應的相集都是頻繁集 ) 2020/10/5 73 數(shù)據(jù)挖掘：概念和技術 73挖掘 FPtree的主要步驟 1) 為 FPtree中的每個節(jié)點生成條件模式庫 2) 用條件模式庫構造對應的條件 FPtree 3) 遞歸構造條件 FPtrees 同時增長其包含的頻繁集 ? 如果條件 FPtree直包含一個路徑，則直接生成所包含的頻繁集。 2020/10/5 88 數(shù)據(jù)挖掘：概念和技術 88數(shù)據(jù)挖掘查詢的逐步精化 ? 為什么要逐步精化 ? 挖掘操作的代價可能高或低，結果可能過細致或粗糙 ? 在速度和質量之間折衷：逐步精化 ? 超集覆蓋特征 ： ? 預存儲所有正面答案 —允許進一步正確性驗證，而不必驗證已經(jīng)錯誤的 ? 2或多步挖掘： ? 先執(zhí)行粗糙的、容易的操作 (超集覆蓋 ) ? 然后在減少后的候選集上進行計算量大的算法 (Koperski amp。amp。amp。 ? 按照對 age 處理方式的不同，分為： 1. 用靜態(tài)方法把數(shù)值屬性離散化 ? 數(shù)值屬性可用預定義的概念層次加以離散化 。 ? 原因 ? 不生成候選集，不用候選測試。 (157頁圖 66) : 不包含任何頻繁 k項集的交易也不可能包含任何大于 k的頻繁集，下一步計算時刪除這些記錄。 ? 舉例： ? 規(guī)則形式： “ Body ???ead [support, confidence]‖. ? buys(x, ―diapers‖) ?? buys(x, ―beers‖) [%, 60%] ? major(x, ―CS‖) ^ takes(x, ―DB‖) ???grade(x, ―A‖) [1%, 75%] 2020/10/5 58 數(shù)據(jù)挖掘：概念和技術 58關聯(lián)規(guī)則：基本概念 ? 給定 : (1)交易數(shù)據(jù)庫 (2)每筆交易是 ： 一個項目列表 (消費者一次購買活動中購買的商品 ) ? 查找 : 所有 描述一個項目集合與其他項目集合相關性的規(guī)則 ? ., 98% of people who purchase tires and auto accessories also get automotive services done ? 應用 ? * ? 護理用品 (商店應該怎樣提高護理用品的銷售？ ) ? 家用電器 ? * (其他商品的庫存有什么影響 ?) ? 在產(chǎn)品直銷中使用 附加郵寄 2020/10/5 59 數(shù)據(jù)挖掘：概念和技術 59規(guī)則度量：支持度與可信度 ? 查找所有的規(guī)則 X amp。 ? 用相同層次的描述對元組進行比較。 ? 屬性刪除 : 如果某個屬性包含大量不同值，但是 1)在該屬性上沒有概化操作， 或者 2）它的較高層概念用其它屬性表示。 ? PrimeGen:根據(jù)上一步的計算結果，對屬性概化到相應的層次，計算匯總值，得到主概化關系。 ? 方差和標準差都是代數(shù)的 ? ? ?????? ?????? ? ???22122 111)(11iini ixnxnxxns2020/10/5 47 直方圖（頻率直方圖） ? 圖形化表示類描述的基本統(tǒng)計信息 ? 頻率直方圖 2020/10/5 48 分位數(shù)圖 2020/10/5 49 分位數(shù) 分位數(shù) () 圖 2020/10/5 50 散布圖 2020/10/5 51 Loess 曲線 2020/10/5 52 圖形化的表示基本統(tǒng)計描述 ? 直方圖 : ? 盒圖 : ? 分位數(shù)圖 : each value xi is paired with fi indicating that approximately 100 fi % of data are ? xi ? 分位數(shù) 分位數(shù)圖 (qq) : graphs the quantiles of one univariant distribution against the corresponding quantiles of another ? 散布圖 : each pair of values is a pair of coordinates and plotted as points in the plane ? Loess (local regression) 曲線 : add a smooth curve to a scatter plot to provide better perception of the pattern of dependence 2020/10/5 53 特征化和比較 ? 什么是概念描述 ? ? 數(shù)據(jù)概化和基于匯總的特征化 ? 分析特征化 : 分析屬性之間的關聯(lián)性 ? 挖掘類比較 :獲取不同類之間的不同處 ? 在大型數(shù)據(jù)庫中挖掘描述統(tǒng)計度量 ? 討論 ? 總結 2020/10/5 54 面向屬性的歸納 vs. 示例學習方法 ? 原理和基本假設的不同 ? 機器學習：正負樣本。 for (k = 2。 (157頁圖 67) : 使用小的支持度 +完整性驗證方法。 黃面包 [6%, 50%]. ? 多層關聯(lián)規(guī)則的變種 1 支持度不變 : 在各層之間使用統(tǒng)一的支持度 （ 164頁圖 612） ? + 一個最小支持度閾值 . 如果一個項集的父項集不具有最小支持度，那他本身也不可能滿足最小支持度。 ? 適宜使用數(shù)據(jù)立方體 ? N維立方體的每個單元 對應一個維詞集合 ? 使用數(shù)據(jù)立方體速度更快 (ine) (age) () (buys) (age, ine) (age,buys) (ine,buys) (age,ine,buys) 2020/10/5 93 數(shù)據(jù)挖掘：概念和技術 93帶數(shù)量的關聯(lián)規(guī)則 age(X,”3034”) ? ine(X,”24K 48K”) ? buys(X,”high resolution TV”) ? 動態(tài) 離散化數(shù)值屬性 使?jié)M足某種挖掘標準，如最大化挖掘規(guī)則的置信度緊湊性 . ? 2維數(shù)量關聯(lián)規(guī)則： Aquan1 ? Aquan2 ? Acat ? 用 2維表格把“鄰近”的 關聯(lián)規(guī)則組合起來 ? 例子 2020/10/5 94 數(shù)據(jù)挖掘：概念和技術 94ARCS (關聯(lián)規(guī)則聚集系統(tǒng) ) （ 170頁圖 618） ARCS 流程 1. 分箱 2. 查找頻繁維詞 集合 3. 關聯(lián)規(guī)則聚類 4. 優(yōu)化 2020/10/5 95 數(shù)據(jù)挖掘：概念和技術 95ARCS的局限性 ? 數(shù)值屬性只能出現(xiàn)在規(guī)則的左側 ? 左側只能有兩個屬性 (2維 ) ? ARCS 的改進 ? 不用基于柵格的方法 ? 等深分箱 ? 基于 局部完整性 測度的聚集 ? ―Mining Quantitative Association Rules in Large Relational Tables‖ by R. Srikant and R. Agrawal. 2020/10/5 96 數(shù)據(jù)挖掘：概念和技術 96挖掘基于距離的關聯(lián)規(guī)則 ? 分箱的方法沒有體現(xiàn)數(shù)據(jù)間隔的語義 ? 基于距離的分割是更有“意義”的離散化方法，考慮 ： ? 區(qū)間內(nèi)密度或點的個數(shù) ? 區(qū)間內(nèi)點的“緊密程度 價格（ $ ）等寬( 寬度 $10)等深( 深度 2) 基于距離7 [ 0 , 1 0 ] [ 7 , 2 0 ] [ 7 , 7 ]20 [ 1 1 , 2 0 ] [ 2 2 , 5 0 ] [ 2 0 , 2 2 ]22 [ 2 1 , 3 0 ] [ 5 1 , 5 3 ] [ 5 0 , 5 3 ]50 [ 3 1 , 4 0 ]51 [ 4 1 , 5 0 ]53 [ 5 1 , 6 0 ]2020/10/5 97 數(shù)據(jù)挖掘：概念和技術 97第 6章：從大數(shù)據(jù)庫中挖掘關聯(lián)規(guī)則 ? 關聯(lián)規(guī)則挖掘 ? ? ? ? ? ? 2020/10/5 98 數(shù)據(jù)挖掘：概念和技術 98? 強關聯(lián)規(guī)則不一定是有趣的（ 168例 ） ? 由關聯(lián)分析到相關分析 項集 A與項集 B獨立 P(AB)=P(A)P(B) 項集 A、 B的相關性 提升度 corrAB=P(AB)/P(A)P(B)（ 169頁例 ） 卡方分析 卡方值 （ 169頁例 ） 全置信度 余弦度量 比較四種相關度量 （ 170頁例 ） 2020/10/5 99 數(shù)據(jù)挖掘：概念和技術 99第 6章：從大數(shù)據(jù)庫中挖掘關聯(lián)規(guī)則 ? 關聯(lián)規(guī)則挖掘 ? ? ? ? ? ? 2020/10/5 100 數(shù)據(jù)挖掘：概念和技術 100 基于約束的挖掘 ? 使用約束的必要性 ? 在數(shù)據(jù)挖掘中常使用的幾種約束： ? 知識類型約束： 指定要挖掘的知識類型 如關聯(lián)規(guī)則 ? 數(shù)據(jù)約束： 指定與任務相關的數(shù)據(jù)集 ? Find product pairs sold together in Vancouver in Dec.’98. ? 維 /層次約束 :指定所用的維或概念結構中的層 ? in relevance to region, price, brand, customer category. ? 規(guī)則約束： 指定 要挖掘的規(guī)則形式 (如規(guī)則模板 ) ? 單價 (price $10)的交易項目可能引發(fā)購買總額 (sum $200). ? 興趣度約束： 指定規(guī)則興趣度閾值或統(tǒng)計度量 ? 如 (min_support ? 3%, min_confidence ? 60%). 2020/10/5 101 數(shù)據(jù)挖掘：概念和技術 101? 假定 AllElectronics的一個銷售多維數(shù)據(jù)庫有如下關系 (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,{J}{T}) (3) from sales (4)where =1999 amp。 ? 滿意模式集 (satisfying pattern set) SATc(I)是指那些完全滿足約束 C的項目集的全體 ? 將約束條件用于頻繁集的查詢無非是找出那些滿足 C的頻繁集 2020/10/5 105 數(shù)據(jù)挖掘：概念和技術 105單調(diào)和反單調(diào)的規(guī)則約束 ? 規(guī)則 Ca 是 反單調(diào)的 (antimonotone) iff 對于任給的不滿足 Ca的項集 (模式 ) S, 不存在 S的超集能夠滿足 Ca : Ca : min(S)=v ， v是 S的一個項集 ? 約束 Cm 是 單調(diào)的 Cm的項集 (模式 ) S, 每一個 S的超集都能夠滿足 Cm : Cm : min(S)=v, v是 S的一個項集