【正文】 buys(X,―coke‖) ? 混合維度 (hybriddimension)關(guān)聯(lián)規(guī)則 (重復謂詞 ) age(X,‖1925‖) ? buys(X, ―popcorn‖) ? buys(X, ―coke‖) ? 分類 (Categorical)屬性 ? 有限的幾個可能值 ,值之間不可排序 ? 數(shù)量 (Quantitative)屬性 ? 數(shù)值的 ,值之間有固有的排序 69 多層關(guān)聯(lián)規(guī)則 :冗余濾除 ? 根據(jù)項之間的 ‖先輩 ‖ (ancestor)關(guān)系 ,一些規(guī)則可能是冗余的 . ? 示例 ? milk ? wheat bread [support = 8%, confidence = 70%] ? 2% milk ? wheat bread [support = 2%, confidence = 72%] ? 我們說第 1個規(guī)則是第 2個規(guī)則的先輩 . ? 一個規(guī)則是冗余的 ,當其支持度接近基于先輩規(guī)則的 ‖預期 ‖(expected)值 . 70 多層關(guān)聯(lián)規(guī)則 :逐步深化 (Progressive Deepening) ? 一個自上而下的 ,逐步深化的方法 : ? 首先挖掘高層的頻繁項 : milk (15%), bread (10%) ? 然后挖掘它們的較低層 ‖較弱 ‖ (weaker)頻繁項 : 2% milk (5%), wheat bread (4%) ? 多層之間不同的最小支持度閾值導致了不同的算法 : ? 如果在多個層次間采用了相同的最小支持度 ,若 t的任何一個先輩都是非頻繁的則扔棄 (toss)t. ? 如果在較低層采用了減少的最小支持度，則只檢驗那些先輩的支持度是頻繁的／不可忽略的派生（ descendents）即可． 71 多維關(guān)聯(lián)規(guī)則挖掘的技術(shù) ? 搜索頻繁 k謂詞集 (predicate set): ? 示例 : {age, occupation, buys}是一個 3謂詞集 ? 以 age處理的方式 ,技術(shù)可以如下分類 1. 利用數(shù)量屬性的統(tǒng)計離散 (static discretization)方法 利用預先確定的概念層次對數(shù)量屬性進行統(tǒng)計離散化 2. 量化關(guān)聯(lián)規(guī)則 ? 基于數(shù)據(jù)的分布 ,數(shù)量屬性被動態(tài)地離散化到不同的容器空間 (bins) 3. 基于距離 (Distancebased)的關(guān)聯(lián)規(guī)則 ? 這是一個動態(tài)離散化的過程 ,該過程考慮數(shù)據(jù)點之間的距離 72 數(shù)量屬性的統(tǒng)計離散化 ? 挖掘之前利用概念層次離散化 ? 數(shù)值被范圍 (ranges)替代 . ? 關(guān)系數(shù)據(jù)庫中 ,找出所有的頻繁 k謂詞 (predicate)集要求 k 或 k+1次表掃描 . ? 數(shù)據(jù)立方體 (data cube)非常適合數(shù)據(jù)挖掘 . ? N維立方體的 cells 與謂詞集 ( predicate sets)相對應 . ? 通過數(shù)據(jù)立方體挖掘會非?？焖?. (ine) (age) () (buys) (age, ine) (age,buys) (ine,buys) (age,ine,buys) 73 量化關(guān)聯(lián)規(guī)則 age(X,”3034”) ? ine(X,”24K 48K”) ? buys(X,”high resolution TV”) ? 數(shù)值屬性動態(tài)離散化 ? 這樣挖掘的規(guī)則的可信度或緊密度最大化 ? 2維 量化關(guān)聯(lián)規(guī)則 : Aquan1 ? Aquan2 ? Acat ? 示例 74 量化關(guān)聯(lián)規(guī)則 ? ARCS: Association Rule Clustering System (關(guān)聯(lián)規(guī)則聚類系統(tǒng) ) 借鑒了圖像處理中的思想 . 本質(zhì)上 , 這種方法映射一對數(shù)量屬性到滿足給定的分類屬性條件的 2維元組格 . 然后對柵格搜索找到聚類點 ,由其生成關(guān)聯(lián)規(guī)則 . ? ARCS 步驟 : 裝箱 (Binning) 找出頻繁謂詞集 (predicate sets) 聚類關(guān)聯(lián)規(guī)則 75 量化關(guān)聯(lián)規(guī)則 ? 裝箱 (Binning): 劃分 過程被認為是裝箱 ,即稱作間隔為箱柜 (bins). 三種常用裝箱策略是 : ? Equiwidth binning, where the intervalsize of each bin is the same ? Equidepth: where each bin has approximately the same number of tuples assigned to it ? Homogeneitybased binning, where bin size is determined so that the tuples in each bin are uniformly distributed. 76 量化關(guān)聯(lián)規(guī)則 ?找出頻繁謂詞集 : Once the 2D array containing the count distribution for each category is set up, this can be scanned in order to find the frequent predicate sets that also satisfy minimum confidence. ?聚類關(guān)聯(lián)規(guī)則 : age(X,”3435”) ? ine(X,”31K 50K”) ? buys(X,”high resolution TV”) 77 ARCS (Association Rules Clustering System) ARCS 1. Binning 2. Frequent Items Set 3. Clustering 4. Optimization 78 ? ARCS: ? 成功的應用聚類的概念到分類中 . ? 但僅限于基于 2維規(guī)則的分類 ,如 A ? B ? Classi 的格式所示 ? 利用裝箱 (Binning)方法將數(shù)據(jù)屬性值離散化 ,因此 ACRS的準確度與使用的離散化程度強烈相關(guān) . ARCS 的特點 79 基于關(guān)聯(lián)規(guī)則的分類 (Classification Based on Association rules, CBA) ? 分類規(guī)則挖掘與關(guān)聯(lián)規(guī)則挖掘 ? 目標 ? 一個小的規(guī)則集作為分類器 ? 所有規(guī)則依照最小支持度與最小可信度 ? 語法 (Syntax) ? X ? y ? X? Y 80 為何及如何結(jié)合 ? 分類規(guī)則挖掘與關(guān)聯(lián)規(guī)則挖掘都是實際應用中必需的 . ? 結(jié)合著眼于關(guān)聯(lián)規(guī)則的一個特定子集 ,其右件限制為分類的類屬性 . ? CARs: Class Association Rules 81 CBA: 三個步驟 ? 若有連續(xù)值 ,則離散化 . ? 生成所有的 class association rules (CARs) ? 構(gòu)建一個若干生成的 CARs的分類器 . 82 CAR集 ? 生成完整的 CARs的集合 ,其滿足用戶指定的最小支持度與最小可信度約束 . ? 由 CARs構(gòu)建一個分類器 . 83 規(guī)則生成 :基本概念 ? 規(guī)則項 (Ruleitem) condset, y :條件集 condset 是一個項集 , y 是一個類標簽(class label) 每個規(guī)則項表示一個規(guī)則 : condsety ? 條件集支持度 (condsupCount) ? D中包含 condset的事例 (case)數(shù) ? 規(guī)則支持度 (rulesupCount) ? D中包含 condset 及標注類別 y的事例 (case)數(shù) ? 支持度 Support=(rulesupCount/|D|)*100% ? 可信度 Confidence=(rulesupCount/condsupCount)*100% 84 規(guī)則生成 :基本概念 (Cont.) ? 頻繁規(guī)則項 (frequent ruleitems) ? 一個規(guī)則項是頻繁的 ,當其支持度不小于最小支持度 minsup. ? 精確規(guī)則 (Accurate rule) ? 一個規(guī)則是精確的 ,當其可信度不小于最小可信度 minconf . ? 潛在規(guī)則 (Possible rule) ? 對所有包含同樣條件集 condset的規(guī)則項 , 可信度最大的規(guī)則項為這一規(guī)則項集合的潛在規(guī)則 . ? 類別關(guān)聯(lián)規(guī)則 class association rules (CARs) 包含所有的潛在規(guī)則 possible rules (PRs) ,其即是頻繁的又是精確的 . 85 規(guī)則生成 : 一個示例 ? 一個規(guī)則項 :{(A,1),(B,1)},(class,1) ? 假定 ? 條件集 condset (condsupCount) 的支持度計數(shù)為 3, ? 規(guī)則項 ruleitem (rulesupCount) 的支持度計數(shù)為 2, ? |D|=10 ? 則 (A,1),(B,1) (class,1) ? [supt=20% (rulesupCount/|D|)*100% ? confd=% (rulesupCount/condsupCount)*100%] 86 RG: 算法 1 F 1 = {large 1ruleitems}。 F k1? 216。 //find all the ruleitems in Ck whose condsets are supported by d 8 for each candidate c? C d do 9 ++。 //select the ruleitems both accurate and frequent 15 prCAR k = pruneRules(CAR k )。 //Step1:sort R according to the relation “?” ? 2 for each rule r ? R in sequence do ? 3 temp = 216。 ? 10 selecting a default class for the current C。 minimum support threshold (minsup)。 // identify the plete clusters of C 3 for each Cluster(C)t do E = genClusterrules(cluset, class)。 // construct the set of frequent cluster_rules 12 MP = genRules (F)。 // sort MPs based on their precedence 2 for each MP? R in sequence do 3 temp = ? 。 10 selecting a default class for the current L。 16 DeMP classifier = L 102 Example of MOUCLAS application The well logging data sets include attributes (well logging curves) of GR (gamma ray), RDEV (deep resistivity), RMEV (shallow resistivity), RXO (flushed zone resistivity), RHOB (bulk density), NPHI (neutron porosity), PEF (photoelectric factor) and DT (sonic travel time). A hypothetically useful MP may suggest a relation between well logging data and the class label of oil/gas formation since. 103 Mining Distancebased Association Rules ? Binning methods do not capture the semantics of interval data ? Distancebased partitioning, more meaningful discretization considering: ? density/number of points in an interval ? ―clos