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

1、數(shù)據(jù)挖掘原理與SPSS Clementine應(yīng)用寶典 元昌安 主編 鄧松李文敬劉海濤編著 電子工業(yè)出版社1210.8 約束性關(guān)聯(lián)規(guī)則挖掘10.9 數(shù)量關(guān)聯(lián)規(guī)則挖掘10.10 負(fù)關(guān)聯(lián)規(guī)則挖掘算法10.11 加權(quán)關(guān)聯(lián)規(guī)則挖掘算法10.12 應(yīng)用實(shí)例分析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ī)則算法10.1 關(guān)聯(lián)規(guī)則基本概念 關(guān)聯(lián)規(guī)則挖掘(Association Rule Mining)是幫助發(fā)現(xiàn)大量數(shù)據(jù)庫(kù)中項(xiàng)集之

2、間的關(guān)聯(lián)關(guān)系。310.1.1關(guān)聯(lián)規(guī)則定義設(shè) I = i1, i2, im, 為所有項(xiàng)目的集合，D 為事務(wù)數(shù)據(jù)庫(kù)事務(wù)T 是一個(gè)項(xiàng)目子集(TI)。每一個(gè)事務(wù)具有唯一的事務(wù)標(biāo)識(shí)Tid 。設(shè)A 是一個(gè)由項(xiàng)目構(gòu)成的集合，稱為項(xiàng)集。事務(wù)T 包含項(xiàng)集A，當(dāng)且僅當(dāng)A T 。410.1.1關(guān)聯(lián)規(guī)則定義最小支持度minsup 即用戶規(guī)定的關(guān)聯(lián)規(guī)則必須滿足的最小支持度，它表示了一組物品集在統(tǒng)計(jì)意義上的需滿足的最低程度。最小置信度minconf 即用戶規(guī)定的關(guān)聯(lián)規(guī)則必須滿足的最小置信度，它反應(yīng)了關(guān)聯(lián)規(guī)則的最低可靠度。510.1.2關(guān)聯(lián)規(guī)則分類1基于規(guī)則中處理的變量的類別，可以分為布爾型和數(shù)值型關(guān)聯(lián)規(guī)則6 布爾型關(guān)聯(lián)規(guī)

3、則處理的值都是離散的、種類化的，它顯示了這些變量之間的關(guān)系。 數(shù)值型關(guān)聯(lián)規(guī)則處理的是定量數(shù)據(jù)項(xiàng)（或?qū)傩裕┲g的關(guān)系，10.1.2關(guān)聯(lián)規(guī)則分類 2基于規(guī)則中數(shù)據(jù)的抽象層次，可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則 例如： IBM臺(tái)式機(jī)Sony打印機(jī)是一個(gè)細(xì)節(jié)數(shù)據(jù)上的單層關(guān)聯(lián)規(guī)則； 臺(tái)式機(jī)Sony打印機(jī)，（此處臺(tái)式機(jī)是IBM臺(tái)式機(jī)的較高層次抽象）。710.1.2關(guān)聯(lián)規(guī)則分類 3基于規(guī)則中涉及到的數(shù)據(jù)維數(shù)，可以分為單維關(guān)聯(lián)規(guī)則和多維關(guān)聯(lián)規(guī)則 例如： 啤酒尿布 (單維) 性別=“女”職業(yè)=“秘書” (多維)8關(guān)聯(lián)規(guī)則的挖掘就是在事務(wù)數(shù)據(jù)庫(kù)D中找出具有用戶給定的最小支持度minsup和最小置信度minconf

4、的關(guān)聯(lián)規(guī)則。如果項(xiàng)集的支持度超過(guò)用戶給定的最小支持度閾值(minsup)，就稱該項(xiàng)集是頻繁項(xiàng)集或大項(xiàng)集。910.2關(guān)聯(lián)規(guī)則算法原理10.2.1關(guān)聯(lián)規(guī)則挖掘算法的兩個(gè)步驟Step1 根據(jù)最小支持度閾值找出數(shù)據(jù)集D中所有頻繁項(xiàng)目集；Step2根據(jù)頻繁項(xiàng)目集和最小置信度閾值產(chǎn)生所有關(guān)聯(lián)規(guī)則。 10關(guān)聯(lián)規(guī)則挖掘的基本模型11算法1算法2數(shù)據(jù)集規(guī)則用 戶最小支持度最小置信度圖10-1 關(guān)聯(lián)規(guī)則挖掘的基本模型10.2.2基本關(guān)聯(lián)規(guī)則算法搜索算法 該類算法只適合于項(xiàng)集數(shù)量相對(duì)較小的數(shù)據(jù)集中的關(guān)聯(lián)規(guī)則挖掘。分層算法(寬度優(yōu)先算法) Apriori算法是這類算法的典型代表，該算法需掃描數(shù)據(jù)集的次數(shù)等于最大頻繁項(xiàng)

5、目集的項(xiàng)目數(shù)。1210.2.2基本關(guān)聯(lián)規(guī)則算法深度優(yōu)先算法 此類算法中最新最高效的是J.Han等人提出的FP-growth(Frequent-pattern Growth)算法。劃分算法 劃分算法的基本思想是將整個(gè)數(shù)據(jù)集劃分成可以存放在內(nèi)存中進(jìn)行處理的數(shù)據(jù)塊，以節(jié)省訪問(wèn)外存的I/0開銷。 抽樣算法 如何計(jì)算負(fù)邊界以找回部分遺漏的頻繁項(xiàng)集是抽樣算法的關(guān)鍵。 1310.2.3復(fù)雜關(guān)聯(lián)規(guī)則算法 多層次關(guān)聯(lián)規(guī)則挖掘一般有兩種途徑: 一種是把單層次關(guān)聯(lián)規(guī)則挖掘算法直接應(yīng)用于多層次。 另一種是在不同的層次應(yīng)用不同的支持度閾值和置信度閾值。1410.3 分層搜索算法-Apriori算法 10.3.1 頻繁項(xiàng)

6、集的產(chǎn)生Apriori算法使用層次順序搜索的循環(huán)方法（又稱作逐層搜索的迭代方法）產(chǎn)生頻繁項(xiàng)集，即用頻繁k-項(xiàng)集探索產(chǎn)生(k+1)-項(xiàng)集。首先，找出長(zhǎng)度為1的頻繁項(xiàng)集，記為 ， 用于產(chǎn)生頻繁2-項(xiàng)集 的集合，而用于產(chǎn)生頻繁3-項(xiàng)集 的，如此循環(huán)下去，直到不能找到新的頻繁k-項(xiàng)集。找每個(gè) 需要掃描數(shù)據(jù)庫(kù)一次。15舉例:已知事務(wù)數(shù)據(jù)庫(kù)D如表10.1所示，最小支持度計(jì)數(shù)為2，即 minsupport=2/9，利用Apriori算法挖掘所有滿足minsup的頻繁集。 16 (1)第一次掃描，掃描數(shù)據(jù)庫(kù)獲得每個(gè)候選項(xiàng)的計(jì)數(shù)，從而獲得頻繁1-項(xiàng)集。如表10-2所示。 17(2)根據(jù)L1生成2-候選集C2，然

7、后掃描數(shù)據(jù)庫(kù)D，計(jì)算各項(xiàng)集的支持度，如表10.3所示。從而得到頻繁2-項(xiàng)集，如表10.4所示。18 (3) L2進(jìn)行自連接得到C3=I1, I4, I5， I1, I2, I4， I1, I3, I4， I1, I3, I5， I2, I3, I4， I3, I4, I5 因?yàn)?I1, I2, I4的子集 I1, I2,和 I1, I3, I4、 I1, I3, I5的子集 I1, I3,及 I2, I3, I4的子集 I2, I3不在L2中 因此，從C3中刪除 I1, I2, I4、 I1, I3, I4、 I1, I3, I5、 I2, I3, I4得： C3= I1, I4, I5， I

8、3, I4, I5。然后再掃描數(shù)據(jù)庫(kù)D，計(jì)算各項(xiàng)集的支持度計(jì)數(shù)，如表10.5所示，從而得到頻繁3-項(xiàng)集L3，如表10.6所示。1920(4)L3進(jìn)行自連接得到C4= I1, I3, I4 , I5，由于 I1, I3, I4 , I5的子集 I1, I3, I4 ,不在L3中，因此刪除 I1, I3, I4 , I5后C4=，進(jìn)而L4=，算法終止。10.3.2產(chǎn)生關(guān)聯(lián)規(guī)則利用如下公式來(lái)計(jì)算所獲關(guān)聯(lián)規(guī)則的置信度。21 其中，support_count(AB)是包含項(xiàng)集AB的交易記錄數(shù)目，support_count(A)是包含項(xiàng)集A的交易記錄數(shù)目。利用頻繁項(xiàng)集生成規(guī)則的算法描述如下：for all

9、 頻繁k項(xiàng)集 ,k2 do begin H1= 中規(guī)則的后件，該規(guī)則的后件中只有一個(gè)項(xiàng)目； Call ap_genrules( ,H1);end;Procedure ap_genrules( ：頻繁項(xiàng)集, Hm：m個(gè)項(xiàng)目的后件的集合)22if(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

10、( );23例102 以表10.1所示數(shù)據(jù)為例，來(lái)說(shuō)明關(guān)聯(lián)規(guī)則的生成過(guò)程。頻繁項(xiàng)集 l = I1, I4, I5，以下將給出根據(jù)l所產(chǎn)生的關(guān)聯(lián)規(guī)則。L 的非空子集為： I1、 I4、I5、 I1, I4、 I4, I5和 I1, I5。以下就是據(jù)此所獲得的關(guān)聯(lián)規(guī)則及其置信度。24I1I4I5 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%如果最

11、小置信度閾值為70%，那么僅有第（1）個(gè)、第（2）個(gè)和第（4）個(gè)規(guī)則，由于它們的置信度大于最小置信度閾值而被保留下來(lái)作為最終的輸出。10.3.3 Apriori算法性能分析 對(duì)于存在大量頻繁模式、長(zhǎng)模式或者最小支持度閉值較小時(shí)，這類Apriori算法將面臨下面的困難: ( 1)算法將花費(fèi)較大的開銷來(lái)處理數(shù)目特別巨大的候選項(xiàng)集。 (2)多次掃描事務(wù)數(shù)據(jù)庫(kù)，需要很大的I/O負(fù)載。2510.3.4 Apriori算法改進(jìn) 有以下幾種算法： 數(shù)據(jù)劃分（Partition） 散列（Hash）方法 采樣(sampling)方法2610.4 并行挖掘算法 10.4.1并行算法思想開發(fā)并行算法有兩種途徑:其一

12、是對(duì)已有的串行算法進(jìn)行改進(jìn)，挖掘其中的并行性質(zhì)并加以利用，使得串行程序并行化；其二是對(duì)問(wèn)題的本質(zhì)重新審視，設(shè)計(jì)全新的并行算法。比較經(jīng)典的算法有基于Apriori算法、DHP算法、DIC算法的并行算法和基于集群和格遍歷的并行算法。 271算法CD(Count Distribution) CD算法的基本思想是:在每一個(gè)處理機(jī)上都存儲(chǔ)全局的候選項(xiàng)集和頻繁項(xiàng)集，每一步計(jì)算時(shí)利用 Apriori算法計(jì)算出候選集在本地?cái)?shù)據(jù)上的支持?jǐn)?shù)，然后做一次同步，各處理機(jī)交換本地的候選項(xiàng)集的支持?jǐn)?shù)，使得每個(gè)處理機(jī)的候選項(xiàng)集都得到全局支持?jǐn)?shù)，從而得到全局頻繁項(xiàng)集Lk。28 DD算法更好地利用了全局的有效存儲(chǔ)空間，它在每個(gè)

13、處理中存儲(chǔ)不同的候選項(xiàng)集，這樣在處理機(jī)數(shù)量增加時(shí)，一步可以增加計(jì)算的候選項(xiàng)集數(shù)量。每個(gè)處理機(jī)為了計(jì)算本地候選項(xiàng)集的全局支持?jǐn)?shù)，必須既要計(jì)算候選項(xiàng)目集在本地的支持?jǐn)?shù)，也要計(jì)算在所有其它的處理機(jī)上的支持?jǐn)?shù)292.算法DD(Data Distribution) CaD算法綜合了DD和CD算法，以彌補(bǔ)它們各自的不足。 與DD算法相似，CaD算法也是在各節(jié)點(diǎn)間分配候選集，但它有選擇地對(duì)數(shù)據(jù)庫(kù)進(jìn)行分割，使每個(gè)節(jié)點(diǎn)可以根據(jù)本地的數(shù)據(jù)來(lái)處理它的候選集，減少處理器之間對(duì)數(shù)據(jù)和各候選集的依賴，從而減少同步，減少通信量。 303算法CaD(Candidate Distribution)10.5 增量更新挖掘算法10

14、.5.1增量挖掘 增量式關(guān)聯(lián)規(guī)則更新技術(shù)應(yīng)具備下列特性: (1)規(guī)則應(yīng)可隨數(shù)據(jù)的變化而變化； (2)規(guī)則更新時(shí)應(yīng)可避免再次處理舊數(shù)據(jù)，而可利用在先前發(fā)現(xiàn)過(guò)程中所獲得的結(jié)果； (3)更新維護(hù)方法應(yīng)盡可能獨(dú)立于具體的發(fā)現(xiàn)算法。3110.5.2 FUP 算法 算法的基本思想:和Apriori算法的框架一致的。每次循環(huán)對(duì)應(yīng)一定長(zhǎng)度的項(xiàng)集，循環(huán)從1-項(xiàng)集開始，在以后每一次循環(huán)，分別發(fā)現(xiàn)k-項(xiàng)集，直到?jīng)]有更長(zhǎng)的項(xiàng)集出現(xiàn)為止。而且，從第二次循環(huán)開始，每一次循環(huán)的候選項(xiàng)集都是根據(jù)前一次循環(huán)所發(fā)現(xiàn)的頻繁項(xiàng)集生成的。在每一次循環(huán)中，根據(jù)增加的數(shù)據(jù)庫(kù)db對(duì)L中的頻繁k-項(xiàng)集的支持度進(jìn)行更新，以過(guò)濾出淘汰者(lose

15、rs)，這一過(guò)程中只要遍歷增加的數(shù)據(jù)庫(kù)db。在遍歷增加的數(shù)據(jù)庫(kù)db時(shí)，根據(jù)db中的事務(wù)產(chǎn)生一組候選項(xiàng)集Ck，并計(jì)算它們?cè)跀?shù)據(jù)庫(kù)db中的支持度。然后根據(jù)D對(duì)候選項(xiàng)集Ck中的項(xiàng)目的支持度進(jìn)行更新，以發(fā)現(xiàn)新的頻繁項(xiàng)集。3210.6 多層關(guān)聯(lián)規(guī)則挖掘 10.6.1 概念層次（Conceptual Hierarchies ） 數(shù)據(jù)庫(kù)中的概念按照各部分的順序被組織起來(lái)，這被稱為概念層次。概念層用來(lái)說(shuō)明數(shù)據(jù)各部分之間的順序。概念層次組織為樹狀結(jié)構(gòu)，包含若干個(gè)節(jié)點(diǎn)。樹中的結(jié)點(diǎn)代表屬性的取值稱為概念，概念層次樹的根節(jié)點(diǎn)默認(rèn)指定為“ANY”。3310.6.2 多層關(guān)聯(lián)規(guī)則挖掘方法多層關(guān)聯(lián)規(guī)則的挖掘可以基于支持度-

16、置信度框架。一般來(lái)說(shuō)，可以采用自頂向下的策略，由最高概念層向下，到較低的更特定的概念層，對(duì)每個(gè)概念層計(jì)算頻繁項(xiàng)集累加計(jì)數(shù)，直到不能再找到頻繁集。對(duì)于每一概念層次（挖掘），可以使用已有的發(fā)現(xiàn)頻繁集的任何算法來(lái)尋找頻繁項(xiàng)集，如Apriori算法或類似算法。 3410.6.2 多層關(guān)聯(lián)規(guī)則挖掘方法 利用遞減支持閾值挖掘多層關(guān)聯(lián)規(guī)則，有以下四種常用的搜索策略:逐層獨(dú)立利用單項(xiàng)進(jìn)行跨層次過(guò)濾利用k-項(xiàng)集進(jìn)行跨層次過(guò)濾受控利用單項(xiàng)進(jìn)行跨層次過(guò)濾。 3510.7約束性關(guān)聯(lián)規(guī)則挖掘 在約束性關(guān)聯(lián)規(guī)則挖掘中，整個(gè)挖掘是在用戶所提供的各種約束條件指導(dǎo)下進(jìn)行的，這些約束包括： (1) 知識(shí)類型的約束。 (2) 數(shù)據(jù)

17、約束。 (3)維或?qū)哟渭s束。 (4)興趣度約束。 (5)規(guī)則約束。3610.7.1數(shù)據(jù)挖掘中約束的作用 約束在數(shù)據(jù)挖掘中的使用可以在如下方面起到關(guān)鍵作用: (1)聚焦挖掘任務(wù)，提高挖掘效率。 (2)保證挖掘的精確性。 (3)控制系統(tǒng)的使用規(guī)模。 3710.7.2約束的類型 從挖掘所使用約束的類型看，可以把用于關(guān)聯(lián)規(guī)則挖掘的約束分為: 1單調(diào)性約束 (Monotone Constraint) 2反單調(diào)性約束(Anti-monotone Constraint) 3可轉(zhuǎn)變的約束(Convertible Constraint) 4簡(jiǎn)潔性約束(Succinct Constraint)3810.7.6時(shí)態(tài)

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

19、類屬性數(shù)值屬性分類屬性”這樣的規(guī)則。 4110.8.3數(shù)量關(guān)聯(lián)規(guī)則挖掘的步驟 可以將數(shù)量關(guān)聯(lián)規(guī)則挖掘分為以下5個(gè)步驟：Step1 數(shù)值屬性的離散化Step2離散區(qū)間整數(shù)化Step 3在離散化的數(shù)據(jù)集上生成頻繁項(xiàng)集Step 4產(chǎn)生關(guān)聯(lián)規(guī)則Step 5規(guī)則輸出4210.8.4數(shù)值屬性離散化及算法 數(shù)值屬性的離散化是數(shù)量關(guān)聯(lián)規(guī)則挖掘的最關(guān)鍵步驟，其實(shí)質(zhì)就是將連續(xù)屬性值劃分成區(qū)間。劃分的方法對(duì)數(shù)量關(guān)聯(lián)規(guī)則挖掘的質(zhì)量起著決定性作用。4310.9多維關(guān)聯(lián)規(guī)則挖掘 根據(jù)是否允許同一個(gè)維重復(fù)出現(xiàn)，可以又細(xì)分為維間的關(guān)聯(lián)規(guī)則 （不允許維重復(fù)出現(xiàn)） 和混合維關(guān)聯(lián)規(guī)則 （允許維在規(guī)則的左右同時(shí)出現(xiàn)）。 4410.9

20、.1多維關(guān)聯(lián)規(guī)則挖掘原理在挖掘維間關(guān)聯(lián)規(guī)則和混合維關(guān)聯(lián)規(guī)則時(shí)，還要考慮不同的字段種類：種類型和數(shù)值型。對(duì)于種類型的字段，原先的算法都可以處理。4510.9.1多維關(guān)聯(lián)規(guī)則挖掘原理 對(duì)于數(shù)值型的字段，需要進(jìn)行一定的處理之后才可以進(jìn)行。處理數(shù)值型字段的方法基本上有以下幾種： (1) 數(shù)值字段被分成一些預(yù)定義的層次結(jié)構(gòu)。 (2) 數(shù)值字段根據(jù)數(shù)據(jù)的分布分成了一些布爾字段。 (3) 數(shù)值字段被分成一些能體現(xiàn)它含義的區(qū)間。 (4) 直接用數(shù)值字段中的原始數(shù)據(jù)進(jìn)行分析。4610.9.1多維關(guān)聯(lián)規(guī)則挖掘原理 挖掘多維關(guān)聯(lián)規(guī)則的技術(shù)可以根據(jù)量化屬性的處理分為三類第一種方法，使用預(yù)定義的概念分層對(duì)量化屬性離散化

21、。這種離散化在挖掘之前進(jìn)行。第二種方法，根據(jù)數(shù)據(jù)的分布，將量化屬性離散化到“箱”。這些可能在挖掘過(guò)程中進(jìn)一步組合。 第三種方法，量化屬性離散化，以緊扣區(qū)間數(shù)據(jù)的語(yǔ)義。 4710.9.2 MAQA算法Step 1 對(duì)于多值屬性A, 取值范圍為L(zhǎng),R。若為數(shù)量屬性,則應(yīng)用聚類算法確定屬性的劃分;若為類別屬性, 則進(jìn)行歸納劃分。Step 2 將劃分后的屬性區(qū)段Lk,Rk或?qū)傩灾涤成涑尚驅(qū)?A,K),進(jìn)而映射為布爾屬性Am, 所有這樣的屬性構(gòu)成項(xiàng)集。Step 3 采用了基本的Apriori 算法從項(xiàng)集中尋找所有有價(jià)值的項(xiàng), 構(gòu)成頻繁項(xiàng)集；有價(jià)值的項(xiàng)是指支持它的交易量超過(guò)給定的最小支持度的項(xiàng)。4810.

22、9.2 MAQA算法Step 4在頻繁集中迭代地搜索出組合后的支持度超過(guò)給定閾值的兩個(gè)項(xiàng), 并將其組合并入頻繁集中；如果是相同屬性的相鄰區(qū)間, 則進(jìn)一步合并。Step 5 應(yīng)用頻繁集產(chǎn)生關(guān)聯(lián)規(guī)則。Step 6 確定有價(jià)值的（Interesting）關(guān)聯(lián)規(guī)則作為輸出。4910.9.3確定多屬性劃分的聚類算法如果一個(gè)數(shù)量屬性的取值數(shù)目過(guò)多時(shí),則將這個(gè)屬性劃分為若干個(gè)區(qū)段。如果一個(gè)類別屬性的取值過(guò)多時(shí),則將其屬性值進(jìn)行歸納5010.9.3確定多屬性劃分的聚類算法for 每個(gè)取值數(shù)N的屬性 doStep 1 計(jì)算每個(gè)屬性值所對(duì)應(yīng)的交易數(shù)Cj;Step 2 尋找所有的局部最大點(diǎn)Maxi和最小點(diǎn)MinLi

23、和MinRi來(lái)確定區(qū)段;Step 3 計(jì)算每個(gè)MinLi和MinRi之間的交易數(shù)Sumi;Step 4 如果滿足合并條件則合并兩個(gè)相鄰區(qū)段,得到K個(gè)區(qū)段;5110.9.3確定多屬性劃分的聚類算法Step 5 S=SumimaxSumiminSumi;Step 6 Save=S(K2);Step 7 尋找所有大于c*Save的Sumi,并將結(jié)果存于Stmp;Step 8 For Stmp中每個(gè)區(qū)段j do if Sumi/(MinRi-MinLi)S(MinR-MinL) then 保存區(qū)段j于Sres結(jié)果為有價(jià)值的區(qū)段,保存在Sres中。5210.10負(fù)關(guān)聯(lián)規(guī)則挖掘算法在數(shù)據(jù)集中還存在著形如A

24、B(項(xiàng)集A 的出現(xiàn)會(huì)抑制項(xiàng)集B 的出現(xiàn)) 、AB(項(xiàng)集A 不出現(xiàn)會(huì)誘導(dǎo)項(xiàng)集B 的出現(xiàn)) 、AB(項(xiàng)集A 不出現(xiàn)會(huì)抑制項(xiàng)集B 的出現(xiàn)) 的關(guān)聯(lián)規(guī)則, 這三種形式的蘊(yùn)含關(guān)系稱為負(fù)關(guān)聯(lián)規(guī)則。傳統(tǒng)的形如AB 的蘊(yùn)含關(guān)系稱為正關(guān)聯(lián)規(guī)則。負(fù)關(guān)聯(lián)規(guī)則挖掘的是項(xiàng)目集中的否定聯(lián)系。5310.10.1直接Apriori算法直接Apriori算法的思想是將事務(wù)集看成是一個(gè)布爾矩陣，對(duì)于每一列，增加一個(gè)列。從初始的項(xiàng)目集的補(bǔ)集中挖掘正關(guān)聯(lián)規(guī)則與負(fù)關(guān)聯(lián)規(guī)則，假定給定一個(gè)初始項(xiàng)目集的矩陣，它的每一行代表一個(gè)事務(wù)，初始項(xiàng)目集的補(bǔ)集將初始項(xiàng)目集的每一個(gè)字節(jié)0、1互換。5410.10.2“近似”負(fù)關(guān)聯(lián)規(guī)則算法 定理1 設(shè)，則有

25、 其中： 為支持度函數(shù)。定理1描述的是三種不同形式的負(fù)關(guān)聯(lián)規(guī)則支持度的計(jì)算方法。55定理2 設(shè) ，則有56其中： 為置信度函數(shù)，如 表示的是負(fù)關(guān)聯(lián)規(guī)則 的置信度 10.11 加權(quán)關(guān)聯(lián)規(guī)則挖掘算法1加權(quán)關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法-MINWAL(O)算法 MINWAL(O)算法類似Apriori算法，挖掘加權(quán)頻繁k-項(xiàng)候是從候選（k-1）-項(xiàng)集通過(guò)連接得到，然后同樣通過(guò)剪枝和檢查刪除這些不可能是其它加權(quán)頻繁項(xiàng)集的子集的候選項(xiàng)，把加權(quán)頻繁項(xiàng)集加入L；把可能成為加權(quán)頻繁項(xiàng)集子集的項(xiàng)目集放入Ck ,以生成更高項(xiàng)加權(quán)頻繁項(xiàng)集或候選頻繁項(xiàng)集。5710.12 應(yīng)用實(shí)例 目前很多高校對(duì)教學(xué)評(píng)價(jià)主要基于數(shù)值計(jì)算，把學(xué)生的評(píng)

26、價(jià)作一總結(jié)，將結(jié)果通報(bào)給老師，作為晉升職稱、評(píng)優(yōu)等的依據(jù)，系里對(duì)老師做一獎(jiǎng)懲及引導(dǎo)，不做深層的思考。這里我們將對(duì)教學(xué)評(píng)價(jià)數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，試圖挖掘教學(xué)效果與教師的性別、年齡、職稱、學(xué)歷等的關(guān)聯(lián)，找到課堂教學(xué)效果與教師整體素質(zhì)的關(guān)系，從而合理調(diào)配一個(gè)班的上課老師，使學(xué)生能夠較好地保持良好的學(xué)習(xí)狀態(tài)，從而為教學(xué)部門提供決策支持信息，以便更好地開展教學(xué)工作，提高教學(xué)質(zhì)量。58 1. 數(shù)據(jù)準(zhǔn)備 這是我們隨機(jī)抽取某高校教師教學(xué)質(zhì)量評(píng)估表1000份，將教師編號(hào)、年齡、性別、職稱、學(xué)歷、公費(fèi)進(jìn)修、工作量和評(píng)定分?jǐn)?shù)8項(xiàng)輸入數(shù)據(jù)庫(kù)，忽略其它信息。我們將通過(guò)數(shù)據(jù)挖掘找出性別、年齡、職稱、學(xué)歷、公費(fèi)進(jìn)修、工作量和評(píng)定分?jǐn)?shù)之間的關(guān)系。表10.8給出了部