秦晨普,張云華

(浙江理工大學(xué) 信息學(xué)院,杭州 310018)

1998 年,新加坡國立大學(xué)的Liu Bing 教授提出了一種將關(guān)聯(lián)規(guī)則挖掘和分類技術(shù)結(jié)合在一起的分類算法——關(guān)聯(lián)分類算法(Classification-Based Association,CBA)[1],因其較好的結(jié)合了關(guān)聯(lián)規(guī)則挖掘和傳統(tǒng)分類算法的優(yōu)點,受到了研究者的廣泛關(guān)注.實踐證明,關(guān)聯(lián)分類算法相較于決策樹、樸素貝葉斯、SVM 支持向量機等傳統(tǒng)的分類算法具有更優(yōu)的分類性能且分類模型更易理解.另一方面,關(guān)聯(lián)分類算法是基于傳統(tǒng)Apriori 算法挖掘事務(wù)項之間的關(guān)聯(lián)來產(chǎn)生分類規(guī)則,也因此也不可避免的繼承了關(guān)聯(lián)規(guī)則挖掘算法需要多次掃描數(shù)據(jù)庫、I/O 負載較大的缺點,算法效率不是很理想.之后的研究者又先后提出了關(guān)聯(lián)決策樹(Association based Decision Tree,ADT)方法[2]、基于多關(guān)聯(lián)規(guī)則的分類算法(Classification based on Mutiple Association Rules,CMAR)[3]、等,雖說在算法性能的提升上取得了一定的成果,但也或多或少的存在著算法魯棒性差、冗余節(jié)點多的問題.

在現(xiàn)有CBA 關(guān)聯(lián)分類算法的基礎(chǔ)上,本文提出了一種基于分類修剪的關(guān)聯(lián)分類算法改進方案ACCP,在分類關(guān)聯(lián)規(guī)則的挖掘過程中基于分類標識對事務(wù)數(shù)據(jù)集進行分類修剪,并加入了基于最大頻繁項集的事先剪枝,避免了無法生成規(guī)則的無效連接操作,有效提高了規(guī)則挖掘效率.同時,借鑒已有的研究成果在構(gòu)造分類器的過程中利用改進后的數(shù)據(jù)覆蓋法對分類規(guī)則進行修剪,提高分類準確率.

1 概念描述

關(guān)聯(lián)分類實質(zhì)上就是基于關(guān)聯(lián)規(guī)則挖掘的分類技術(shù),它既反映了知識的應(yīng)用特點——分類或預(yù)測,又體現(xiàn)了知識內(nèi)在的關(guān)聯(lián)特性[4].設(shè)D是一個包含著n條記錄的事務(wù)數(shù)據(jù)集,I={i1,i2,i3,···,im}是全體事務(wù)項的集合,I的子集一般稱為項集,根據(jù)子集中事務(wù)項的個數(shù)依次可稱為1-項集,2-項集,…,k-項集.數(shù)據(jù)庫中每條事務(wù)記錄ti(i=1,2,3,···,n)均對應(yīng)著I的一個子集,且具有唯一標識符TID.║D║表示數(shù)據(jù)集D中包含的事務(wù)數(shù)量.

定義1.項集X的支持度：數(shù)據(jù)集中包含項集X 的事務(wù)出現(xiàn)的頻率,記為

其中,| {T|X?T,T?D}|代表的是事務(wù)數(shù)據(jù)集D中包含項集X的事務(wù)總數(shù),即項集的支持數(shù).

定義2.頻繁項集：若項集的支持度超過或等于人為設(shè)定的最小支持度閾值minSupp,則稱此項集為頻繁項集.

定義3.最大頻繁項集：如果一個頻繁項集的任一直接超集都是非頻繁項集,那么就稱這個頻繁項集為最大頻繁項集.

定義4.規(guī)則置信度：假設(shè)數(shù)據(jù)集中關(guān)聯(lián)規(guī)則X?Y成立,則其置信度是指包含項集X的事務(wù)同時包含項集Y的概率,其表述的是規(guī)則的可靠性,表達式為：

定理1.項目集空間理論：頻繁項集的子集仍是頻繁項集,非頻繁項集的超集是非頻繁項集[5].

2 基于分類修剪的關(guān)聯(lián)分類模型ACCP

2.1 基于分類標識的規(guī)則挖掘

之前的研究人員所運用的基于分類標識的規(guī)則后項約束,大多先由頻繁k-1 項集的集合Lk-1自連接生成候選k項集的集合Ck,再對包含分類標識的候選k項集進行基于最小支持度閾值minSupp的剪枝操作.實際上,當(dāng)頻繁k-1 項集I1作為規(guī)則前項只出現(xiàn)在分類標識為Ci的事務(wù)中時,那么對分類標識不等于Ci的候選k項集{I1,Ci+1}進行支持度計數(shù)就顯得沒有必要,本文基于此思想對分類關(guān)聯(lián)規(guī)則的挖掘過程進行了改進.

將事務(wù)數(shù)據(jù)集D根據(jù)分類屬性值的不同,劃分為多個事務(wù)子集{D1,D2,D3,…,Dn},其中n為分類屬性值的個數(shù),每個事務(wù)子集中挖掘得到的規(guī)則項集具有統(tǒng)一的分類標識.對每個子集進行單獨的分類關(guān)聯(lián)規(guī)則挖掘,在分類標識為Ci的事務(wù)子集中,項集{Ii}的支持數(shù)和事務(wù)總集中包含分類標識Ci的規(guī)則項集{Ii,Ci}支持數(shù)一致,只要根據(jù)項集Ii的支持數(shù)進行連接剪枝即可,從而大幅的降低了每次掃描數(shù)據(jù)庫時的數(shù)據(jù)維度,避免了無法生成規(guī)則的項集的產(chǎn)生,減少了候選項集的數(shù)量.

2.2 基于最大頻繁項集的事先剪枝

原始的關(guān)聯(lián)規(guī)則挖掘過程有兩次剪枝操作,第一次是在Lk-1自連接之后,根據(jù)Apriori 算法性質(zhì)(項目集空間理論)剪除非頻繁項集,第二次是由候選項集Ck生成Lk時,通過計算項集支持度剪除非頻繁項集.本文將在此基礎(chǔ)上加入一次基于最大頻繁項集的事先剪枝,即在自連接之前利用項目集空間理論,提前判斷出頻繁k-1 項集的集合Lk-1中的某些最大頻繁項集,將其進行剪除,從而省去了它們的連接操作,進一步減少了候選項集數(shù),提高了分類關(guān)聯(lián)規(guī)則的挖掘效率.

根據(jù)項目集空間理論,頻繁k-項集的所有子集均為頻繁項集.由此可得,每個頻繁k-項集可抽取出k個頻繁k-1 項子集,則包含這k個頻繁k-1 項集的集合Lk-1當(dāng)中每個事務(wù)項出現(xiàn)的次數(shù)必然大于等于k-1.下面用一個簡單的例子說明這個原理.

已知4-項集{a,b,c,d}為頻繁項集,其有4 個頻繁3-項子集,分別為{a,b,c}、{a,b,d}、{a,c,d}、{b,c,d},則包含項集{a,b,c}、{a,b,d}、{a,c,d}、{b,c,d}的集合L3中,事務(wù)項a、b、c、d 出現(xiàn)的次數(shù)都至少為3.反之,若a、b、c、d 任意一個事務(wù)項在L3中出現(xiàn)次數(shù)小于3,則4 個3-項集中至少有一個不包含于L3即不是頻繁項集,由此可得{a,b,c,d}亦不是頻繁項集.推而廣之,不難得出：

定理2.頻繁k-1 項集中存在事務(wù)項在集合Lk-1中出現(xiàn)次數(shù)小于k-1 次是此頻繁項集為最大頻繁項集的充分條件.

對最大頻繁項集事先剪枝的具體實現(xiàn)步驟如下：

(1)計算頻繁k-1 項集的集合Lk-1中每個事務(wù)項出現(xiàn)的次數(shù),用Lk-1(p)表示；

(2)記錄下出現(xiàn)次數(shù)小于k-1 的事務(wù)項,記作P={p||Lk-1(p)|＜k-1}；

(3)將Lk-1中包含有P中任一元素的頻繁項集刪除,記為Lk-1'；

(4)Lk-1'自連接,生成候選k-項集的集合Ck.

2.3 實例分析

我們以表1所示的事務(wù)數(shù)據(jù)集為例,簡單闡述一下改進后的關(guān)聯(lián)分類算法的分類關(guān)聯(lián)規(guī)則挖掘過程.

表1 數(shù)據(jù)庫示例

由表1可得,事務(wù)數(shù)據(jù)集D有兩個類別屬性值A(chǔ)1,A2,可將事務(wù)數(shù)據(jù)集分為表2,表3所示的事務(wù)子集D1,D2.

表2 分類得到的事務(wù)子集D1

表3 分類得到的事務(wù)子集D2

Ck表示候選k-項集的集合,Lk表示頻繁k-項集的集合,Ri表示事務(wù)子集Di中挖掘出的分類規(guī)則集,假定最小支持數(shù)minSupp為2,首先對事務(wù)子集D1進行規(guī)則挖掘.如圖1所示,第一次掃描事務(wù)子集D1后得到候選1-項集的集合C1及其中各項集所對應(yīng)的支持數(shù),將C1中支持數(shù)小于最小支持數(shù)minSupp的項集剪除便得到頻繁1-項集的集合L1,圖1左上表便是C1到L1的剪枝過程,其中邊框為虛線的項集即為被剪枝的非頻繁項集.將L1自連接可得到候選2-項集的集合C2,基于最小支持數(shù)minSupp剪枝后得到頻繁2-項集的集合L2= {{a,b},{a,c},{b,c},{b,d}}.

圖1 分類關(guān)聯(lián)規(guī)則挖掘過程示例

接著對集合L2進行遍歷,記錄L2中每個事務(wù)項出現(xiàn)的次數(shù).不難發(fā)現(xiàn),事務(wù)項a 同時包含于頻繁2-項集{a,b}、{a,c},即事務(wù)項a 在L2中出現(xiàn)了2 次,同理可得事務(wù)項b 出現(xiàn)3 次,事務(wù)項c 出現(xiàn)2 次,事務(wù)項d 只出現(xiàn)了1 次.由于屬性項目d 出現(xiàn)的次數(shù)小于L2中項集的項數(shù),由定理2 可得L2中所有包含項目d 的項集均為最大頻繁項集,將其剪除后即得到最終的L2'.由L2'自連接可得到候選3-項集C3={{a,b,c}}并最終確定L3={{a,b,c}},因其無法再進行自連接,頻繁項集挖掘結(jié)束.將最終生成的集合L中所有頻繁項集加入分類標識A1便得到分類關(guān)聯(lián)規(guī)則集R1,循環(huán)挖掘所有事務(wù)子集并將最后得到的分類規(guī)則集合并便得到整個數(shù)據(jù)庫的分類關(guān)聯(lián)規(guī)則集R.

2.4 規(guī)則修剪

由于分類關(guān)聯(lián)規(guī)則挖掘所得到的規(guī)則數(shù)量巨大,在構(gòu)造分類器時會占用大量內(nèi)存空間,并且會對分類準確率產(chǎn)生不利影響,本文基于改進后的數(shù)據(jù)庫覆蓋方法對規(guī)則集進行規(guī)則修剪.

首先基于置信度、支持度從大到小以及規(guī)則項集維度從小到大的方式對分類規(guī)則進行優(yōu)先級排序.從優(yōu)先級最高的規(guī)則依次進行考察,遍歷事務(wù)數(shù)據(jù)集記錄下正確分類的比例并將此規(guī)則所能覆蓋的所有事務(wù)樣本刪除,直到?jīng)]有剩余樣本或已考察完所有規(guī)則.最后刪除分類性能較差的規(guī)則并多次執(zhí)行以上步驟不斷提高規(guī)則集的分類準確率[6].規(guī)則修剪的算法一般性描述如下：

3 實驗與結(jié)果分析

3.1 實驗環(huán)境

本次實驗的實驗環(huán)境如下：Intel(R)Core(TM)i5-2450M CPU @2.50 GHz 處理器；8 G 內(nèi)存；120 G SSD 固態(tài)硬盤；Windows 10 專業(yè)版操作系統(tǒng).實驗選取了UCI 標準數(shù)據(jù)庫中的5 個常用數(shù)據(jù)集Pima Indians Diabetes、Lymphography、Wine、Car Evaluation、Iris[7]分別涵蓋醫(yī)療衛(wèi)生、食品檢測、汽車評估、生物研究等領(lǐng)域,每個數(shù)據(jù)集的相關(guān)數(shù)據(jù)信息如表4所示.本實驗算法程序使用Java 語言實現(xiàn).

表4 實驗所用數(shù)據(jù)集相關(guān)信息統(tǒng)計

3.2 實驗結(jié)果分析

本實驗使用了10 折交叉驗證方法來避免過度擬合,從每個數(shù)據(jù)集中隨機選取80%的樣本作為訓(xùn)練數(shù)據(jù)集,其余20%作為測試數(shù)據(jù)集測試算法的分類性能.針對數(shù)據(jù)集中存在的數(shù)據(jù)缺失,根據(jù)缺失的屬性值是離散還是連續(xù),分別采用眾數(shù)原理將其設(shè)定為該屬性在數(shù)據(jù)集中出現(xiàn)次數(shù)最多的取值,或是設(shè)定為數(shù)據(jù)集中該屬性其他非缺失值的平均數(shù).本文選取了現(xiàn)有的CBA 算法以及傳統(tǒng)分類算法中的C4.5 決策樹算法進行對照試驗,實驗中最小支持度minSupp和最小置信度minConf分別設(shè)定為2%和60%,結(jié)果如表5所示.

本文采用正確分類的樣本數(shù)占測試樣本總數(shù)的比例即分類準確率來衡量分類器模型的優(yōu)劣.從表5中可以看出,關(guān)聯(lián)分類算法的準確率整體高于傳統(tǒng)的C4.5 決策樹算法.在部分數(shù)據(jù)集上CBA 算法的分類準確率等于或略小于C4.5 算法,而改進后的關(guān)聯(lián)分類算法ACCP 則在全部數(shù)據(jù)集上都明顯優(yōu)于C4.5 和CBA,平均分類準確率分別提高了5.29 和3.37 個百分點.與此同時,基于分類修剪并加入了預(yù)先剪枝的ACCP 算法在實驗所采用的所有數(shù)據(jù)集上的運行時間均較CBA 算法有所降低,在數(shù)據(jù)集屬性較多、事務(wù)數(shù)較大更為明顯.實驗結(jié)果證明,ACCP 算法取得來了良好的應(yīng)用效果.

表5 實驗結(jié)果對比

4 結(jié)語

本文提出了一種基于分類修剪的新關(guān)聯(lián)分類算法ACCP,通過將事務(wù)數(shù)據(jù)集根據(jù)分類標識分塊挖掘,極大地節(jié)省了內(nèi)存空間,提高了挖掘效率,同時在分類器構(gòu)造過程中加大規(guī)則修剪力度,剪除了規(guī)則集中分類性能較差的冗余規(guī)則,進一步優(yōu)化了分類模型.實驗證明,本文提出的方法相比傳統(tǒng)的C4.5 決策樹和CBA分類模型具有更優(yōu)的分類性能.

基于關(guān)聯(lián)規(guī)則產(chǎn)生分類器的過程并不有助于人們對分類模型的理解,反而會影響分類器的性能.因此,如何有效減少構(gòu)建分類器時所使用到的規(guī)則數(shù)量,提高單個規(guī)則的適用性,是接下來要研究解決的問題.

1 Liu B,Hsu W,Ma YM.Integrating classification and association rule mining.Proceedings of the 4th InternationalConference on Knowledge Discovery and Data Mining.New York,NY,USA.1998.80-86.