數(shù)據(jù)挖掘原理與SPSS Clementine應(yīng)用寶典第10章 關(guān)聯(lián)規(guī)則

1、1 數(shù)據(jù)挖掘原理與數(shù)據(jù)挖掘原理與spss clementine應(yīng)用寶典應(yīng)用寶典 元昌安元昌安 主編主編 鄧松李文敬劉海濤編著鄧松李文敬劉海濤編著 電子工業(yè)出版社電子工業(yè)出版社 2 10.8 約束性關(guān)聯(lián)規(guī)則挖掘 10.9 數(shù)量關(guān)聯(lián)規(guī)則挖掘 10.10 負關(guān)聯(lián)規(guī)則挖掘算法 10.11 加權(quán)關(guān)聯(lián)規(guī)則挖掘算法 10.12 應(yīng)用實例分析 10.13 小結(jié) 10.1 關(guān)聯(lián)規(guī)則基本概念 10.2 關(guān)聯(lián)規(guī)則算法原理 10.3 分層搜索經(jīng)典算法-apriori算法 10.4 并行挖掘算法 10.5 增量更新挖掘算法 10.6 多層關(guān)聯(lián)規(guī)則挖掘 10.7 多維關(guān)聯(lián)規(guī)則挖掘 第十章 關(guān)聯(lián)規(guī)則算法 3 10.1 關(guān)聯(lián)

2、規(guī)則基本概念 關(guān)聯(lián)規(guī)則挖掘(association rule mining)是幫 助發(fā)現(xiàn)大量數(shù)據(jù)庫中項集之間的關(guān)聯(lián)關(guān)系。 4 10.1.1關(guān)聯(lián)規(guī)則定義關(guān)聯(lián)規(guī)則定義 v設(shè) i = i1, i2, im, 為所有項目的集合，d 為事 務(wù)數(shù)據(jù)庫事務(wù)t 是一個項目子集(ti)。每一個事 務(wù)具有唯一的事務(wù)標識tid 。設(shè)a 是一個由項目構(gòu) 成的集合，稱為項集。事務(wù)t 包含項集a，當(dāng)且僅 當(dāng)a t 。 5 v最小支持度最小支持度minsup 即用戶規(guī)定的關(guān)聯(lián)規(guī)則必須滿即用戶規(guī)定的關(guān)聯(lián)規(guī)則必須滿 足的最小支持度，它表示了一組物品集在統(tǒng)計意義足的最小支持度，它表示了一組物品集在統(tǒng)計意義 上的需滿足的最低程度。

3、上的需滿足的最低程度。 v最小置信度最小置信度minconf 即用戶規(guī)定的關(guān)聯(lián)規(guī)則必須即用戶規(guī)定的關(guān)聯(lián)規(guī)則必須 滿足的最小置信度，它反應(yīng)了關(guān)聯(lián)規(guī)則的最低可靠滿足的最小置信度，它反應(yīng)了關(guān)聯(lián)規(guī)則的最低可靠 度。度。 10.1.1關(guān)聯(lián)規(guī)則定義關(guān)聯(lián)規(guī)則定義 6 10.1.2關(guān)聯(lián)規(guī)則分類 1基于規(guī)則中處理的變量的類別，可以分為布爾基于規(guī)則中處理的變量的類別，可以分為布爾 型和數(shù)值型關(guān)聯(lián)規(guī)則型和數(shù)值型關(guān)聯(lián)規(guī)則 布爾型關(guān)聯(lián)規(guī)則處理的值都是離散的、種類化布爾型關(guān)聯(lián)規(guī)則處理的值都是離散的、種類化 的，它顯示了這些變量之間的關(guān)系。的，它顯示了這些變量之間的關(guān)系。 數(shù)值型關(guān)聯(lián)規(guī)則處理的是定量數(shù)據(jù)項（或?qū)傩裕?shù)值型關(guān)

4、聯(lián)規(guī)則處理的是定量數(shù)據(jù)項（或?qū)傩裕?之間的關(guān)系，之間的關(guān)系， 7 2基于規(guī)則中數(shù)據(jù)的抽象層次，可以分為單層關(guān) 聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則 例如： ibm臺式機sony打印機是一個細節(jié)數(shù)據(jù)上的單 層關(guān)聯(lián)規(guī)則； 臺式機sony打印機，（此處臺式機是ibm臺式 機的較高層次抽象）。 10.1.2關(guān)聯(lián)規(guī)則分類 8 3基于規(guī)則中涉及到的數(shù)據(jù)維數(shù)，可以分為單維 關(guān)聯(lián)規(guī)則和多維關(guān)聯(lián)規(guī)則 例如： 啤酒尿布 (單維) 性別=“女”職業(yè)=“秘書” (多維) 10.1.2關(guān)聯(lián)規(guī)則分類 9 10.2關(guān)聯(lián)規(guī)則算法原理 v關(guān)聯(lián)規(guī)則的挖掘就是在事務(wù)數(shù)據(jù)庫d中找出具有用 戶給定的最小支持度minsup和最小置信度minconf 的

5、關(guān)聯(lián)規(guī)則。 v如果項集的支持度超過用戶給定的最小支持度閾值 (minsup)，就稱該項集是頻繁項集或大項集。 10 10.2.1關(guān)聯(lián)規(guī)則挖掘算法的兩個步驟 vstep1 根據(jù)最小支持度閾值找出數(shù)據(jù)集d中所有頻 繁項目集； vstep2根據(jù)頻繁項目集和最小置信度閾值產(chǎn)生所有 關(guān)聯(lián)規(guī)則。 11 關(guān)聯(lián)規(guī)則挖掘的基本模型 算法算法1算法算法2數(shù)據(jù)集數(shù)據(jù)集規(guī)則規(guī)則 用用 戶戶 最小支持度最小支持度最小置信度最小置信度 圖圖10-1 關(guān)聯(lián)規(guī)則挖掘的基本模型關(guān)聯(lián)規(guī)則挖掘的基本模型 12 10.2.2基本關(guān)聯(lián)規(guī)則算法 搜索算法搜索算法 該類算法只適合于項集數(shù)量相對較小的數(shù)據(jù)集中 的關(guān)聯(lián)規(guī)則挖掘。 分層算法(寬

6、度優(yōu)先算法) apriori算法是這類算法的典型代表，該算法需掃 描數(shù)據(jù)集的次數(shù)等于最大頻繁項目集的項目數(shù)。 13 深度優(yōu)先算法深度優(yōu)先算法 此類算法中最新最高效的是j.han等人提出的fp- growth(frequent-pattern growth)算法。 劃分算法 劃分算法的基本思想是將整個數(shù)據(jù)集劃分成可 以存放在內(nèi)存中進行處理的數(shù)據(jù)塊，以節(jié)省訪問 外存的i/0開銷。 抽樣算法 如何計算負邊界以找回部分遺漏的頻繁項集是 抽樣算法的關(guān)鍵。 10.2.2基本關(guān)聯(lián)規(guī)則算法 14 10.2.3復(fù)雜關(guān)聯(lián)規(guī)則算法 多層次關(guān)聯(lián)規(guī)則挖掘一般有兩種途徑: 一種是把單層次關(guān)聯(lián)規(guī)則挖掘算法直接應(yīng)用 于多層次

7、。 另一種是在不同的層次應(yīng)用不同的支持度閾 值和置信度閾值。 15 10.3 分層搜索算法-apriori算法 1 l 1 l 2 l 3 l k l 10.3.1 頻繁項集的產(chǎn)生頻繁項集的產(chǎn)生 vapriori算法使用層次順序搜索的循環(huán)方法（又稱 作逐層搜索的迭代方法）產(chǎn)生頻繁項集，即用頻 繁k-項集探索產(chǎn)生(k+1)-項集。首先，找出長度為 1的頻繁項集，記為 ， 用于產(chǎn)生頻繁2-項集 的集合，而用于產(chǎn)生頻繁3-項集 的，如此循環(huán) 下去，直到不能找到新的頻繁k-項集。找每個 需要掃描數(shù)據(jù)庫一次。 16 舉例: 已知事務(wù)數(shù)據(jù)庫d如表10.1所示，最小支持度計數(shù) 為2，即 minsupport

8、=2/9， v利用apriori算法挖掘所有滿足minsup的頻繁集。 17 (1)第一次掃描，掃描數(shù)據(jù)庫獲得每個候選項的計數(shù)，從而獲得頻 繁1-項集。如表10-2所示。 (2)根據(jù)l1生成2-候選集c2，然后掃描數(shù)據(jù)庫d，計算各項集的支持 度，如表10.3所示。從而得到頻繁2-項集，如表10.4所示。 18 19 (3) l2進行自連接得到c3=i1, i4, i5， i1, i2, i4， i1, i3, i4， i1, i3, i5， i2, i3, i4， i3, i4, i5 因為 i1, i2, i4的子集 i1, i2,和 i1, i3, i4、 i1, i3, i5的子集 i1

9、, i3,及 i2, i3, i4的子 集 i2, i3不在l2中 因此，從c3中刪除 i1, i2, i4、 i1, i3, i4、 i1, i3, i5、 i2, i3, i4得： c3= i1, i4, i5， i3, i4, i5。然后再掃描 數(shù)據(jù)庫d，計算各項集的支持度計數(shù)，如表10.5 所示，從而得到頻繁3-項集l3，如表10.6所示。 20 (4)l3進行自連接得到c4= i1, i3, i4 , i5，由于 i1, i3, i4 , i5的子集 i1, i3, i4 ,不在l3中，因此刪除 i1, i3, i4 , i5后c4=，進而l4=，算法終止。 21 10.3.2產(chǎn)生關(guān)

10、聯(lián)規(guī)則 v利用如下公式來計算所獲關(guān)聯(lián)規(guī)則的置信度。 unt(a)support_co b)unt(asupport_co )|()(bapbaconfidence 其中，support_count(ab)是包含項集ab的交易記錄 數(shù)目，support_count(a)是包含項集a的交易記錄數(shù)目。 22 v利用頻繁項集生成規(guī)則的算法描述如下： for all 頻繁k項集 ,k2 do begin h1= 中規(guī)則的后件，該規(guī)則的后件中只有 一個項目； call ap_genrules( ,h1); end; procedure ap_genrules( ：頻繁項集, hm： m個項目的后件的集合)

11、 k l k l k l k l 23 vif(km+1) then begin hm+1=apriori_gen(hm) for all hm+1 hm+1 do begin conf=support( )/support( -hm+1); if(confminconf) then output 規(guī)則 -hm+1hm+1 with confidence=conf and support=support( ); k l k l k l k l 24 v例102 以表10.1所示數(shù)據(jù)為例，來說明關(guān)聯(lián)規(guī) 則的生成過程。頻繁項集 l = i1, i4, i5，以下將 給出根據(jù)l所產(chǎn)生的關(guān)聯(lián)規(guī)則。l

12、的非空子集為： i1、 i4、i5、 i1, i4、 i4, i5和 i1, i5。以 下就是據(jù)此所獲得的關(guān)聯(lián)規(guī)則及其置信度。 i1i4i5 confidence=2/2=100% i1i5i4 confidence=2/2=100% i4i5i1 confidence=2/4=50% i1i4i5 confidence=2/2=100% i4i1i5 confidence=2/7=28.5% i5i1i4 confidence=2/6=33.3% 如果最小置信度閾值為70%，那么僅有第（1）個、第（2）個和第 （4）個規(guī)則，由于它們的置信度大于最小置信度閾值而被保留下來 作為最終的輸出。 2

13、5 10.3.3 apriori算法性能分析 對于存在大量頻繁模式、長模式或者最小支 持度閉值較小時，這類apriori算法將面臨下面的 困難: ( 1)算法將花費較大的開銷來處理數(shù)目特別巨 大的候選項集。 (2)多次掃描事務(wù)數(shù)據(jù)庫，需要很大的i/o負載。 26 10.3.4 apriori算法改進 有以下幾種算法： l 數(shù)據(jù)劃分（partition） l 散列（hash）方法 l 采樣(sampling)方法 27 10.4 并行挖掘算法 10.4.1并行算法思想并行算法思想 v開發(fā)并行算法有兩種途徑:其一是對已有的串行算法 進行改進，挖掘其中的并行性質(zhì)并加以利用，使得 串行程序并行化；其二

14、是對問題的本質(zhì)重新審視， 設(shè)計全新的并行算法。 v比較經(jīng)典的算法有基于apriori算法、dhp算法、 dic算法的并行算法和基于集群和格遍歷的并行算 法。 28 vcd算法的基本思想是:在每一個處理機上都存儲 全局的候選項集和頻繁項集，每一步計算時利用 apriori算法計算出候選集在本地數(shù)據(jù)上的支持數(shù)， 然后做一次同步，各處理機交換本地的候選項集 的支持數(shù)，使得每個處理機的候選項集都得到全 局支持數(shù)，從而得到全局頻繁項集lk。 1算法算法cd(count distribution) 29 dd算法更好地利用了全局的有效存儲空間，算法更好地利用了全局的有效存儲空間， 它在每個處理中存儲不同的

15、候選項集，這樣在處它在每個處理中存儲不同的候選項集，這樣在處 理機數(shù)量增加時，一步可以增加計算的候選項集理機數(shù)量增加時，一步可以增加計算的候選項集 數(shù)量。每個處理機為了計算本地候選項集的全局數(shù)量。每個處理機為了計算本地候選項集的全局 支持數(shù)，必須既要計算候選項目集在本地的支持支持數(shù)，必須既要計算候選項目集在本地的支持 數(shù)，也要計算在所有其它的處理機上的支持數(shù)數(shù)，也要計算在所有其它的處理機上的支持數(shù) 2.算法算法dd(data distribution) 30 cad算法綜合了算法綜合了dd和和cd算法，以彌補它們算法，以彌補它們 各自的不足。各自的不足。 與與dd算法相似，算法相似，cad算法

16、也是在算法也是在 各節(jié)點間分配候選集，但它有選擇地對數(shù)據(jù)庫進各節(jié)點間分配候選集，但它有選擇地對數(shù)據(jù)庫進 行分割，使每個節(jié)點可以根據(jù)本地的數(shù)據(jù)來處理行分割，使每個節(jié)點可以根據(jù)本地的數(shù)據(jù)來處理 它的候選集，減少處理器之間對數(shù)據(jù)和各候選集它的候選集，減少處理器之間對數(shù)據(jù)和各候選集 的依賴，從而減少同步，減少通信量。的依賴，從而減少同步，減少通信量。 3算法算法cad(candidate distribution) 31 10.5 增量更新挖掘算法 v10.5.1增量挖掘增量挖掘 增量式關(guān)聯(lián)規(guī)則更新技術(shù)應(yīng)具備下列特性: (1)規(guī)則應(yīng)可隨數(shù)據(jù)的變化而變化； (2)規(guī)則更新時應(yīng)可避免再次處理舊數(shù)據(jù)，而可利

17、 用在先前發(fā)現(xiàn)過程中所獲得的結(jié)果； (3)更新維護方法應(yīng)盡可能獨立于具體的發(fā)現(xiàn)算法。 32 10.5.2 fup 算法 算法的基本思想:和apriori算法的框架一致的。每次 循環(huán)對應(yīng)一定長度的項集，循環(huán)從1-項集開始，在以后每 一次循環(huán)，分別發(fā)現(xiàn)k-項集，直到?jīng)]有更長的項集出現(xiàn)為 止。而且，從第二次循環(huán)開始，每一次循環(huán)的候選項集都 是根據(jù)前一次循環(huán)所發(fā)現(xiàn)的頻繁項集生成的。在每一次循 環(huán)中，根據(jù)增加的數(shù)據(jù)庫db對l中的頻繁k-項集的支持度 進行更新，以過濾出淘汰者(losers)，這一過程中只要遍 歷增加的數(shù)據(jù)庫db。在遍歷增加的數(shù)據(jù)庫db時，根據(jù)db中 的事務(wù)產(chǎn)生一組候選項集ck，并計算它們

18、在數(shù)據(jù)庫db中的 支持度。然后根據(jù)d對候選項集ck中的項目的支持度進行 更新，以發(fā)現(xiàn)新的頻繁項集。 33 10.6 多層關(guān)聯(lián)規(guī)則挖掘 10.6.1 概念層次（概念層次（conceptual hierarchies ） 數(shù)據(jù)庫中的概念按照各部分的順序被組織起來， 這被稱為概念層次。概念層用來說明數(shù)據(jù)各部分之間 的順序。概念層次組織為樹狀結(jié)構(gòu)，包含若干個節(jié)點。 樹中的結(jié)點代表屬性的取值稱為概念，概念層次樹的 根節(jié)點默認指定為“any”。 34 10.6.2 多層關(guān)聯(lián)規(guī)則挖掘方法 v多層關(guān)聯(lián)規(guī)則的挖掘可以基于支持度-置信度框架。 一般來說，可以采用自頂向下的策略，由最高概念 層向下，到較低的更特定的

19、概念層，對每個概念層 計算頻繁項集累加計數(shù)，直到不能再找到頻繁集。 對于每一概念層次（挖掘），可以使用已有的發(fā)現(xiàn) 頻繁集的任何算法來尋找頻繁項集，如apriori算法 或類似算法。 35 利用遞減支持閾值挖掘多層關(guān)聯(lián)規(guī)則，有以下 四種常用的搜索策略: l逐層獨立 l利用單項進行跨層次過濾 l利用k-項集進行跨層次過濾 l受控利用單項進行跨層次過濾。 10.6.2 多層關(guān)聯(lián)規(guī)則挖掘方法 36 10.7約束性關(guān)聯(lián)規(guī)則挖掘 在約束性關(guān)聯(lián)規(guī)則挖掘中，整個挖掘是在用戶 所提供的各種約束條件指導(dǎo)下進行的，這些約束 包括： (1) 知識類型的約束。 (2) 數(shù)據(jù)約束。 (3)維或?qū)哟渭s束。 (4)興趣度約束

20、。 (5)規(guī)則約束。 37 10.7.1數(shù)據(jù)挖掘中約束的作用 約束在數(shù)據(jù)挖掘中的使用可以在如下方面起 到關(guān)鍵作用: (1)聚焦挖掘任務(wù)，提高挖掘效率。 (2)保證挖掘的精確性。 (3)控制系統(tǒng)的使用規(guī)模。 38 10.7.2約束的類型 從挖掘所使用約束的類型看，可以把用于關(guān)聯(lián) 規(guī)則挖掘的約束分為: 1單調(diào)性約束單調(diào)性約束 (monotone constraint) 2反單調(diào)性約束反單調(diào)性約束(anti-monotone constraint) 3可轉(zhuǎn)變的約束可轉(zhuǎn)變的約束(convertible constraint) 4簡潔性約束簡潔性約束(succinct constraint) 39 10

21、.7.6時態(tài)約束關(guān)聯(lián)規(guī)則挖掘 時態(tài)關(guān)聯(lián)規(guī)則為了能真正反映不同時間間隔內(nèi)的時間 數(shù)據(jù)的內(nèi)在規(guī)律，通常分為三個子過程： 1.初始階段： 2.關(guān)聯(lián)規(guī)則發(fā)現(xiàn)階段 3.結(jié)果關(guān)聯(lián)規(guī)則的表達 40 10.8.2數(shù)量關(guān)聯(lián)規(guī)則的分類 1根據(jù)數(shù)值屬性的處理方式進行分類根據(jù)數(shù)值屬性的處理方式進行分類 （1）數(shù)值屬性的靜態(tài)離散化 （2）數(shù)值屬性的動態(tài)離散化 （3）基于特定的技術(shù)進行數(shù)值屬性的離散化 41 2.根據(jù)使用的規(guī)則模版進行分類根據(jù)使用的規(guī)則模版進行分類 （1）類似于）類似于“數(shù)值屬性數(shù)值屬性分類屬性數(shù)值屬性分類屬性數(shù)值屬性分類分類 屬性屬性”這樣的規(guī)則這樣的規(guī)則 （2）分類規(guī)則的挖掘模版 簡單的挖掘模版形式類

22、 似于“數(shù)值屬性分類屬性數(shù)值屬性分類屬性” 這樣的規(guī)則。 （3）其它挖掘模版 例如，挖掘模版形式類似于 “分類屬性數(shù)值屬性分類屬性”這樣的規(guī)則。 10.8.2數(shù)量關(guān)聯(lián)規(guī)則的分類 42 10.8.3數(shù)量關(guān)聯(lián)規(guī)則挖掘的步驟 可以將數(shù)量關(guān)聯(lián)規(guī)則挖掘分為以下5個步驟： step1 數(shù)值屬性的離散化 step2離散區(qū)間整數(shù)化 step 3在離散化的數(shù)據(jù)集上生成頻繁項集 step 4產(chǎn)生關(guān)聯(lián)規(guī)則 step 5規(guī)則輸出 43 10.8.4數(shù)值屬性離散化及算法 數(shù)值屬性的離散化是數(shù)量關(guān)聯(lián)規(guī)則挖掘的最關(guān)鍵 步驟，其實質(zhì)就是將連續(xù)屬性值劃分成區(qū)間。劃 分的方法對數(shù)量關(guān)聯(lián)規(guī)則挖掘的質(zhì)量起著決定性 作用。 44 根據(jù)

23、是否允許同一個維重復(fù)出現(xiàn)，可以又細 分為維間的關(guān)聯(lián)規(guī)則 （不允許維重復(fù)出現(xiàn)） 和混 合維關(guān)聯(lián)規(guī)則 （允許維在規(guī)則的左右同時出現(xiàn)）。 10.9多維關(guān)聯(lián)規(guī)則挖掘 45 10.9.1多維關(guān)聯(lián)規(guī)則挖掘原理 v在挖掘維間關(guān)聯(lián)規(guī)則和混合維關(guān)聯(lián)規(guī)則時，還要 考慮不同的字段種類：種類型和數(shù)值型。 v對于種類型的字段，原先的算法都可以處理。 46 對于數(shù)值型的字段，需要進行一定的處理之后才 可以進行。處理數(shù)值型字段的方法基本上有以下 幾種： (1) 數(shù)值字段被分成一些預(yù)定義的層次結(jié)構(gòu)。 (2) 數(shù)值字段根據(jù)數(shù)據(jù)的分布分成了一些布爾 字段。 (3) 數(shù)值字段被分成一些能體現(xiàn)它含義的區(qū)間。 (4) 直接用數(shù)值字段中

24、的原始數(shù)據(jù)進行分析。 10.9.1多維關(guān)聯(lián)規(guī)則挖掘原理 47 挖掘多維關(guān)聯(lián)規(guī)則的技術(shù)可以根據(jù)量化屬性 的處理分為三類 v第一種方法，使用預(yù)定義的概念分層對量化屬性 離散化。這種離散化在挖掘之前進行。 v第二種方法，根據(jù)數(shù)據(jù)的分布，將量化屬性離散 化到“箱”。這些可能在挖掘過程中進一步組合。 v第三種方法，量化屬性離散化，以緊扣區(qū)間數(shù)據(jù) 的語義。 10.9.1多維關(guān)聯(lián)規(guī)則挖掘原理 48 10.9.2 maqa算法 step 1 對于多值屬性a, 取值范圍為l,r。若 為數(shù)量屬性,則應(yīng)用聚類算法確定屬性的劃 分;若為類別屬性, 則進行歸納劃分。 step 2 將劃分后的屬性區(qū)段lk,rk或?qū)傩?值

25、映射成序?qū)?a,k),進而映射為布爾屬性 am, 所有這樣的屬性構(gòu)成項集。 step 3 采用了基本的apriori 算法從項集中尋 找所有有價值的項, 構(gòu)成頻繁項集；有價值 的項是指支持它的交易量超過給定的最小 支持度的項。 49 10.9.2 maqa算法 step 4在頻繁集中迭代地搜索出組合后的支持度超 過給定閾值的兩個項, 并將其組合并入頻繁集中； 如果是相同屬性的相鄰區(qū)間, 則進一步合并。 step 5 應(yīng)用頻繁集產(chǎn)生關(guān)聯(lián)規(guī)則。 step 6 確定有價值的（interesting）關(guān)聯(lián)規(guī)則作為 輸出。 50 10.9.3確定多屬性劃分的聚類算法 v如果一個數(shù)量屬性的取值數(shù)目過多時,

26、則將這個 屬性劃分為若干個區(qū)段。如果一個類別屬性的 取值過多時,則將其屬性值進行歸納 51 for 每個取值數(shù)n的屬性 do step 1 計算每個屬性值所對應(yīng)的交易數(shù)cj; step 2 尋找所有的局部最大點maxi和最小點minli 和minri來確定區(qū)段; step 3 計算每個minli和minri之間的交易數(shù)sumi; step 4 如果滿足合并條件則合并兩個相鄰區(qū)段,得到 k個區(qū)段; 10.9.3確定多屬性劃分的聚類算法 52 step 5 s=sumimaxsumiminsumi; step 6 save=s(k2); step 7 尋找所有大于c*save的sumi,并將結(jié)果存

27、于stmp; step 8 for stmp中每個區(qū)段j do if sumi/(minri-minli)s(minr-minl) then 保存區(qū)段j于sres 結(jié)果為有價值的區(qū)段,保存在sres中。 10.9.3確定多屬性劃分的聚類算法 53 10.10負關(guān)聯(lián)規(guī)則挖掘算法 v在數(shù)據(jù)集中還存在著形如ab(項集a 的出現(xiàn)會 抑制項集b 的出現(xiàn)) 、ab(項集a 不出現(xiàn)會誘 導(dǎo)項集b 的出現(xiàn)) 、ab(項集a 不出現(xiàn)會抑制 項集b 的出現(xiàn)) 的關(guān)聯(lián)規(guī)則, 這三種形式的蘊含關(guān) 系稱為負關(guān)聯(lián)規(guī)則。傳統(tǒng)的形如ab 的蘊含關(guān) 系稱為正關(guān)聯(lián)規(guī)則。負關(guān)聯(lián)規(guī)則挖掘的是項目集 中的否定聯(lián)系。 54 10.10.

28、1直接apriori算法 v直接apriori算法的思想是將事務(wù)集看成是一個布爾矩陣， 對于每一列，增加一個列。從初始的項目集的補集中挖 掘正關(guān)聯(lián)規(guī)則與負關(guān)聯(lián)規(guī)則，假定給定一個初始項目集 的矩陣，它的每一行代表一個事務(wù)，初始項目集的補集 將初始項目集的每一個字節(jié)0、1互換。 55 定理定理1 設(shè)，則有 其中： 為支持度函數(shù)。定理1描述的是三 種不同形式的負關(guān)聯(lián)規(guī)則支持度的計算方 法。 10.10.2“近似”負關(guān)聯(lián)規(guī)則算法 )sup(1)sup(aa )sup()sup()sup(baaba )sup()sup()sup(babba )sup()sup()sup(1)sup(bababa )su

29、p(x 56 v定理定理2 設(shè) ，則有 baibia, )(1 )sup( )sup()sup( )(baconf a baa baconf )sup(1 )sup()sup( )( a bab baconf )(1 )sup(1 )sup()sup()sup(1 )(baconf a baba baconf 其中：其中： 為置信度函數(shù)，如為置信度函數(shù)，如 表示的是負表示的是負 關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則 的置信度的置信度 )(xconf )(baconf ba 57 1加權(quán)關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法加權(quán)關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法-minwal(o)算法算法 minwal(o)算法算法類似apriori算法，挖掘加權(quán)頻繁

30、k-項候是從候選（k-1）-項集通過連接得到，然后同 樣通過剪枝和檢查刪除這些不可能是其它加權(quán)頻繁 項集的子集的候選項，把加權(quán)頻繁項集加入l；把可 能成為加權(quán)頻繁項集子集的項目集放入ck ,以生成 更高項加權(quán)頻繁項集或候選頻繁項集。 10.11 加權(quán)關(guān)聯(lián)規(guī)則挖掘算法 58 10.12 應(yīng)用實例 目前很多高校對教學(xué)評價主要基于數(shù)值計算，把學(xué)生 的評價作一總結(jié)，將結(jié)果通報給老師，作為晉升職稱、評 優(yōu)等的依據(jù)，系里對老師做一獎懲及引導(dǎo)，不做深層的思 考。這里我們將對教學(xué)評價數(shù)據(jù)進行關(guān)聯(lián)規(guī)則挖掘，試圖 挖掘教學(xué)效果與教師的性別、年齡、職稱、學(xué)歷等的關(guān)聯(lián)， 找到課堂教學(xué)效果與教師整體素質(zhì)的關(guān)系，從而合理調(diào)配 一個班的上課老師，使學(xué)生能夠較好地保持良好的學(xué)習(xí)狀 態(tài)，從而為教學(xué)部門提供決策支持信息，以便更好地開展 教學(xué)工作，提高教學(xué)質(zhì)量。 59 1. 數(shù)據(jù)準備數(shù)據(jù)準備 這是我們隨機抽取某高校教師教學(xué)質(zhì)量評估表1000份， 將教師編號、年齡、性別、職稱、學(xué)歷、公費進修、工作