一種基于主屬性判定的關(guān)聯(lián)規(guī)則挖掘約簡(jiǎn)算法*

熊中敏，汪 博，陶 然，鄭宗生，陳 明，2

(1.上海海洋大學(xué)信息學(xué)院，上海 201306；2.農(nóng)業(yè)部漁業(yè)信息重點(diǎn)實(shí)驗(yàn)室，上海 201306)

1 引言

關(guān)聯(lián)規(guī)則挖掘雖然已經(jīng)得到大量的應(yīng)用，但在實(shí)踐中仍然存在令人不滿意的地方，比較典型的問(wèn)題是在數(shù)據(jù)庫(kù)的挖掘過(guò)程中會(huì)得到大量的規(guī)則，導(dǎo)致用戶無(wú)所適從[1]。如何約簡(jiǎn)規(guī)則集的大小，使得到的規(guī)則數(shù)量減少且是用戶想要的，是影響到關(guān)聯(lián)規(guī)則挖掘項(xiàng)目能否有效實(shí)施的問(wèn)題。

關(guān)聯(lián)規(guī)則挖掘算法基本上是以Apriori算法為基礎(chǔ)的一系列改進(jìn)算法。算法的核心思想是計(jì)算頻繁項(xiàng)集，即統(tǒng)計(jì)數(shù)據(jù)項(xiàng)出現(xiàn)的概率是否大于事先設(shè)定好的最小支持度，由于每次都要掃描整個(gè)數(shù)據(jù)庫(kù)，這個(gè)計(jì)算過(guò)程非常耗時(shí)。很多國(guó)外研究者提出了改進(jìn)的措施，對(duì)事務(wù)數(shù)據(jù)庫(kù)不進(jìn)行多次掃描就能產(chǎn)生同樣的候選集[2 - 5]。這些算法雖然計(jì)算效率有所提高，但需要同時(shí)提高Apriori算法框架中的參數(shù)設(shè)定值，即比較大的最小置信度和最小支持度，或者設(shè)置一些數(shù)據(jù)約束，算法的效率才能有明顯改善。

國(guó)內(nèi)學(xué)者也展開(kāi)了相關(guān)的技術(shù)研究[6 - 13]，主要是算法的理論研究，注重采用新的技術(shù)方法提高算法的效率；另外則是應(yīng)用研究，將關(guān)聯(lián)規(guī)則分析方法引入到一些行業(yè)，得到原來(lái)不能得到的分析結(jié)果。這2類研究大多數(shù)沒(méi)有考慮規(guī)則集的約簡(jiǎn)問(wèn)題，另外一類理論研究和規(guī)則集的化簡(jiǎn)有關(guān)[11]，主要是找到最小置信度之外的一種新的評(píng)價(jià)關(guān)聯(lián)規(guī)則的測(cè)度，然后通過(guò)測(cè)度值重新進(jìn)行關(guān)聯(lián)規(guī)則的選擇。而本文從Apriori算法挖掘出的關(guān)聯(lián)規(guī)則的結(jié)構(gòu)分析出發(fā)(即利用數(shù)據(jù)庫(kù)模式規(guī)范化中“局部函數(shù)依賴”這種依賴結(jié)構(gòu)分析出冗余信息的頻繁出現(xiàn)會(huì)導(dǎo)致沒(méi)有實(shí)際價(jià)值的冗余信息被基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘處理為頻繁項(xiàng)和相應(yīng)的關(guān)聯(lián)規(guī)則)，沒(méi)有引入新的評(píng)價(jià)測(cè)度，分別基于數(shù)據(jù)庫(kù)模式設(shè)計(jì)中的主屬性和頻繁(K+1)項(xiàng)集中新增屬性對(duì)生成的關(guān)聯(lián)規(guī)則的影響，提出約簡(jiǎn)關(guān)聯(lián)規(guī)則集的算法。所以，本文的研究角度有別于上述文獻(xiàn)的算法，而且利用本文提出的算法約簡(jiǎn)關(guān)聯(lián)規(guī)則后，還可以進(jìn)一步利用上述新的規(guī)則評(píng)價(jià)測(cè)度重新評(píng)估并選擇關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則挖掘已經(jīng)獲得巨大的發(fā)展，但面臨著新的挑戰(zhàn):現(xiàn)有的挖掘方法不僅得到的規(guī)則過(guò)多，而且還包含了沒(méi)有什么關(guān)系的規(guī)則[1]。本文提出的化簡(jiǎn)關(guān)聯(lián)規(guī)則集的算法，正是針對(duì)上述關(guān)聯(lián)規(guī)則急需解決的問(wèn)題，但本文的研究方向不是如何改善算法在計(jì)算頻繁項(xiàng)集的執(zhí)行效率，而是在不改變基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘中的最小支持度和最小置信度的條件下，通過(guò)對(duì)關(guān)聯(lián)規(guī)則進(jìn)行結(jié)構(gòu)化分析，簡(jiǎn)化挖掘到的關(guān)聯(lián)規(guī)則集。

2 相關(guān)知識(shí)

2.1 規(guī)則分析方法

從海量的數(shù)據(jù)中挖掘隱含的知識(shí)，這是數(shù)據(jù)挖掘發(fā)展的目標(biāo)和動(dòng)力，也是很多大型企業(yè)或公司越來(lái)越關(guān)注并應(yīng)用數(shù)據(jù)挖掘技術(shù)的原因。關(guān)聯(lián)規(guī)則最初是用來(lái)研究顧客在超市中購(gòu)買的商品有無(wú)關(guān)聯(lián)性的問(wèn)題，這就是廣為傳頌的關(guān)聯(lián)規(guī)則挖掘故事“啤酒和尿布”，這種隱藏在數(shù)據(jù)中的聯(lián)系可帶來(lái)巨大的商業(yè)價(jià)值。現(xiàn)在隨著聯(lián)機(jī)分析處理OLAP(OnLine Analytical Process)技術(shù)的日趨成熟與廣泛運(yùn)用，OLAP技術(shù)與關(guān)聯(lián)規(guī)則同時(shí)使用的方法已經(jīng)成為非常受關(guān)注的研究方向。

關(guān)聯(lián)規(guī)則常用表達(dá)為：(X?Y，支持度=s，置信度=c)，在表達(dá)式中X是規(guī)則的前提條件，Y是規(guī)則的結(jié)論，s是包含了規(guī)則的前提條件的數(shù)據(jù)項(xiàng)在數(shù)據(jù)庫(kù)事務(wù)集中出現(xiàn)的次數(shù)占整個(gè)事務(wù)集中數(shù)據(jù)項(xiàng)個(gè)數(shù)的百分比，c是在數(shù)據(jù)庫(kù)事務(wù)集中規(guī)則前提條件和結(jié)論同時(shí)出現(xiàn)的次數(shù)占規(guī)則前提出現(xiàn)次數(shù)的百分比。顯然，支持度表示規(guī)則的頻度，置信度表示規(guī)則的強(qiáng)度。

關(guān)聯(lián)規(guī)則挖掘的理論基礎(chǔ)是Apriori算法[7]?；贏priori算法的關(guān)聯(lián)規(guī)則挖掘過(guò)程以頻繁項(xiàng)集的計(jì)算為基礎(chǔ)，統(tǒng)計(jì)超出支持度閾值的項(xiàng)集，統(tǒng)計(jì)過(guò)程包括以下2個(gè)步驟：

(1)首先利用遞推公式設(shè)計(jì)一個(gè)增量計(jì)算方法由“K-項(xiàng)集”計(jì)算“K+1-項(xiàng)集”，然后在“K+1-項(xiàng)集”中采用剪枝策略即Apriori性質(zhì)(如果一個(gè)候選項(xiàng)是頻繁的，那么它的任一個(gè)非空子集也是頻繁的)過(guò)濾其中的元素，直到計(jì)算的候選項(xiàng)集為空，則終止計(jì)算。

(2)通過(guò)設(shè)置的置信度閾值利用轉(zhuǎn)換規(guī)則，由計(jì)算得到的頻繁項(xiàng)集簡(jiǎn)單地推導(dǎo)出對(duì)應(yīng)的關(guān)聯(lián)規(guī)則。即對(duì)每個(gè)計(jì)算出的頻繁項(xiàng)L產(chǎn)生它的所有非空子集，然后對(duì)L的每個(gè)非空子集S，如果L在數(shù)據(jù)庫(kù)事務(wù)集中出現(xiàn)的次數(shù)與S在數(shù)據(jù)庫(kù)事務(wù)集中出現(xiàn)的次數(shù)的比值不小于置信度閾值，則產(chǎn)生一個(gè)關(guān)聯(lián)規(guī)則“S→L-S”。

2.2 關(guān)系模式規(guī)范化中的關(guān)鍵字及主屬性

選取一個(gè)比較優(yōu)化的關(guān)系模式是關(guān)系數(shù)據(jù)庫(kù)在規(guī)范化設(shè)計(jì)中需要考慮的現(xiàn)實(shí)問(wèn)題。數(shù)據(jù)依賴、范式和模式設(shè)計(jì)方法是規(guī)范化設(shè)計(jì)的理論所包含的內(nèi)容。數(shù)據(jù)依賴是規(guī)范化設(shè)計(jì)的核心，它研究數(shù)據(jù)之間的聯(lián)系，范式是數(shù)據(jù)庫(kù)模式設(shè)計(jì)要達(dá)到的標(biāo)準(zhǔn)，模式設(shè)計(jì)方法是為自動(dòng)化設(shè)計(jì)服務(wù)的。關(guān)系數(shù)據(jù)庫(kù)是否具有完整性和一致性，模式規(guī)范化理論起著決定性的作用。在數(shù)據(jù)庫(kù)中，屬性值之間會(huì)產(chǎn)生聯(lián)系，例如每個(gè)學(xué)生只有一個(gè)姓名，每門課程只有一個(gè)任課教師，每個(gè)學(xué)生學(xué)一門課只能有一個(gè)成績(jī)等。我們將這類聯(lián)系稱為函數(shù)依賴FD(Functio- nal Dependency)。

定義1[14]設(shè)有關(guān)系模式R，X和Y是屬性集U的子集，函數(shù)依賴是形為X→Y的一個(gè)命題，只要r是R的當(dāng)前關(guān)系，對(duì)r中任意2個(gè)元組t和s，都有t[X]=s[X]蘊(yùn)涵t[Y]=s[Y]，那么稱FDX→Y在關(guān)系模式R中成立。

函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。數(shù)據(jù)庫(kù)設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定，例如，規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名→年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在，則拒絕裝入該元組。

定義2[14]設(shè)關(guān)系模式R的屬性集是U，X是U的一個(gè)子集。如果X→U在R上成立，那么稱X是R的一個(gè)超關(guān)鍵字。如果X→U在R上成立，但對(duì)于X的任一真子集X1都有X1→U不成立，那么稱X是R上的一個(gè)候選關(guān)鍵字。

在實(shí)際使用中，經(jīng)常要判斷能否從已知的FD集F中推導(dǎo)出X→Y，即從FD集F推導(dǎo)出的所有函數(shù)依賴形成的集合F+是否包含X→Y，從F求F+是一個(gè)指數(shù)級(jí)問(wèn)題，而求屬性集閉包則是一個(gè)多項(xiàng)式級(jí)時(shí)間問(wèn)題[14]。

定義3[14]設(shè)F是屬性集U上的FD集，X是U的子集，那么(相對(duì)于F)屬性集X的閉包用X+表示，它是一個(gè)從F集使用FD推理規(guī)則推出的所有滿足X→A的屬性A的集合：X+={屬性A|X→A在F+中}。

定理1[14]X→Y能用FD推理規(guī)則推出的充分必要條件是Y?X+。

設(shè)屬性集X的閉包為X+，其計(jì)算過(guò)程如算法1所示[14]。

算法1求屬性X相對(duì)于FD集F的閉包X+

輸入：屬性X,FD集F。

輸出：X相對(duì)于F的閉包X+。

{X+=X;

do{ifF中有某個(gè)FDU→V滿足U?X+then

X+=X+∪V;}

while(X+有所改變);

}

定義4[14]如果關(guān)系模式R的每個(gè)關(guān)系r的屬性值都是不可分的原子值，那么稱R是第一范式1NF(First Normal Form)的模式。

1NF是關(guān)系模式應(yīng)具備的最起碼的條件。

定義5[14]如果A是關(guān)系模式R的候選鍵中屬性，那么稱A是R的主屬性；否則稱A是R的非主屬性。

定義6[14]對(duì)于FDW→A，如果存在X?W有X→A成立，那么稱W→A是局部依賴(A局部依賴于W)；否則稱W→A是完全依賴。

定義7[14]如果關(guān)系模式R是1NF，且每個(gè)非主屬性完全函數(shù)依賴于候選鍵，那么稱R是第二范式2NF(Second Normal Form)的模式。如果數(shù)據(jù)庫(kù)模式中每個(gè)關(guān)系模式都是2NF，則稱數(shù)據(jù)庫(kù)模式為2NF的數(shù)據(jù)庫(kù)模式。

3 基于主屬性判定的關(guān)聯(lián)規(guī)則分析

3.1 數(shù)據(jù)模式中冗余信息的頻繁出現(xiàn)

例如，關(guān)于選課信息數(shù)據(jù)庫(kù)的規(guī)范化關(guān)系模式(帶下劃線的字段為關(guān)鍵字)為：

學(xué)生(學(xué)號(hào)，姓名，年齡，性別)；課程(課程號(hào)，課程名，教師名)；選課(學(xué)號(hào)，課程號(hào)，成績(jī))。

在查詢選課信息時(shí)，通常會(huì)采用如下的數(shù)據(jù)視圖：

Create view course-view as

Select 選課.學(xué)號(hào),選課.課程號(hào),學(xué)生.姓名,學(xué)生.年齡,學(xué)生.性別,課程.課程名,課程.教師名,選課.成績(jī)

From 學(xué)生，課程，選課

Where選課.學(xué)號(hào)=學(xué)生.學(xué)號(hào) and選課.課程號(hào)=課程.課程號(hào)

雖然在規(guī)范化的設(shè)計(jì)中教師“張三”主講課程“線性代數(shù)”在數(shù)據(jù)庫(kù)中存儲(chǔ)的是一條記錄，但在綜合查詢信息時(shí)假設(shè)有25個(gè)同學(xué)選了這門課，那么“張三主講線性代數(shù)”冗余出現(xiàn)25次，即達(dá)到了關(guān)聯(lián)規(guī)則挖掘的頻繁度而成為頻繁項(xiàng)。但是，顯然我們只關(guān)注學(xué)生自主選課的頻繁性，即“線性代數(shù)”課程被多少學(xué)生選擇，而不是“張三主講線性代數(shù)”這樣頻繁出現(xiàn)的冗余信息，也就是說(shuō)，通過(guò)頻繁項(xiàng)計(jì)算后的關(guān)聯(lián)規(guī)則挖掘可以得到“張三?線性代數(shù)”這樣的關(guān)聯(lián)規(guī)則。但是，實(shí)際上在數(shù)據(jù)庫(kù)概念設(shè)計(jì)實(shí)體關(guān)系ER(Entity Relationship)建模時(shí)就可以確定“張三主講線性代數(shù)”這樣的實(shí)體關(guān)系，即這種模型可以確定的關(guān)系已經(jīng)沒(méi)有必要再經(jīng)過(guò)關(guān)聯(lián)規(guī)則挖掘算法得到，否則只會(huì)增加挖掘到的規(guī)則集的規(guī)模，使得用戶理解并使用規(guī)則的難度更大。

同樣地，如果一個(gè)學(xué)生選了10門課，則他的姓名、年齡和性別這樣的冗余信息也會(huì)頻繁出現(xiàn)10次，顯然關(guān)聯(lián)規(guī)則挖掘出的頻繁項(xiàng)不應(yīng)該是這樣頻繁出現(xiàn)的冗余信息。

根據(jù)定義6可知，在上述視圖中存在局部依賴，雖然上述關(guān)系模式符合2NF范式，即消除了局部依賴，但這些規(guī)范化的表通過(guò)連接操作形成完全的信息后出現(xiàn)了局部依賴，同時(shí)出現(xiàn)了冗余信息，而這些頻繁出現(xiàn)的冗余信息并不是我們想關(guān)注的數(shù)據(jù)中隱藏的具有一定關(guān)聯(lián)的頻繁項(xiàng)。事實(shí)上我們?cè)跀?shù)據(jù)存儲(chǔ)時(shí)是通過(guò)模式規(guī)范化分解避免這些冗余信息的頻繁出現(xiàn)，只不過(guò)是在用戶查詢的外模式即視圖級(jí)別的信息展示時(shí)通過(guò)規(guī)范化表之間的連接使得這些冗余信息頻繁出現(xiàn)了(冗余信息的頻繁出現(xiàn)并沒(méi)有數(shù)據(jù)上的挖掘價(jià)值，只是一種完全信息的展示)。

3.2 基于屬性閉包求一個(gè)候選關(guān)鍵字

由3.1節(jié)的分析可知，冗余信息頻繁出現(xiàn)的原因是FD集中出現(xiàn)的局部依賴，而根據(jù)定義6判斷是否有局部依賴存在，其實(shí)就是判斷是否存在一個(gè)候選關(guān)鍵字中包含的主屬性為左部的函數(shù)依賴，所以判定主屬性是個(gè)關(guān)鍵問(wèn)題，現(xiàn)有教材[14]中只有主屬性的定義(見(jiàn)本文定義5)，并沒(méi)有提供如何判定主屬性的方法。由文獻(xiàn)[15，16]可知，求全部主屬性如同求所有候選關(guān)鍵字問(wèn)題都是NP難題，為此，本文提出了一種基于一個(gè)候選關(guān)鍵字進(jìn)行驗(yàn)證的算法來(lái)判定主屬性，從而完成基于主屬性判定的關(guān)聯(lián)規(guī)則挖掘算法的設(shè)計(jì)與實(shí)現(xiàn)。

算法2求關(guān)系R的一個(gè)候選關(guān)鍵字X

輸入：關(guān)系R的屬性集U，F(xiàn)D集F。

輸出：候選關(guān)鍵字X。

{X:=U;

調(diào)用算法1求X的閉包X+；//X一個(gè)超關(guān)鍵字

Old_X+:= X+;

Foreachx∈X并按出現(xiàn)在X中的先后次序do

{X:=X-x;

調(diào)用算法1求X的閉包X+；

ifOld_X+≠X+thendo/*推導(dǎo)的閉包發(fā)生變化即變小了，說(shuō)明刪除的屬性為主屬性，即當(dāng)前X不再是關(guān)鍵字*/

{X:=X∪{x};}/*主屬性不能刪除*/

}

return(X)}

定理2算法2正確地求出了關(guān)系R的一個(gè)候選關(guān)鍵字X。

證明很顯然關(guān)系R的所有屬性形成的集合U滿足U→U，由定義2 可知,U就是R的一個(gè)超關(guān)鍵字，由于算法2 刪除了超關(guān)鍵字中的所有非主屬性，根據(jù)定義2可知最后求得的X即為候選關(guān)鍵字。

□

3.3 頻繁項(xiàng)為主屬性的識(shí)別方法

由于關(guān)聯(lián)規(guī)則挖掘算法Apriori的關(guān)鍵步驟是計(jì)算出頻繁項(xiàng)集，然后根據(jù)轉(zhuǎn)換規(guī)則和置信度自動(dòng)生成關(guān)聯(lián)規(guī)則，所以如果能判斷頻繁項(xiàng)是否來(lái)自于局部依賴導(dǎo)致的冗余信息的頻繁出現(xiàn)，就能避免生成不必要的關(guān)聯(lián)規(guī)則，從而達(dá)到約簡(jiǎn)關(guān)聯(lián)規(guī)則集的效果。

根據(jù)定義2可知，候選關(guān)鍵字能唯一決定一條記錄，即不同的關(guān)鍵字和所決定的屬性值只能頻繁出現(xiàn)1次，故而可以認(rèn)為通過(guò)關(guān)聯(lián)規(guī)則挖掘算法Apriori計(jì)算出的頻繁項(xiàng)不會(huì)包含候選關(guān)鍵字，除非設(shè)置頻繁度為1，即只出現(xiàn)1次，而這種頻繁度設(shè)置失去了頻繁的意義。故而，只要檢測(cè)到頻繁項(xiàng)中屬性為主屬性就認(rèn)為該主屬性為某個(gè)候選關(guān)鍵字的子集，然后通過(guò)計(jì)算其屬性閉包識(shí)別該頻繁項(xiàng)是否源于一個(gè)局部依賴。

算法3判定頻繁項(xiàng)中元素x是否為主屬性

輸入：某個(gè)頻繁項(xiàng)中元素x，一個(gè)候選關(guān)鍵字K。

輸出：x為主屬性返回True，否則返回False。

{X:=K∪{x};//根據(jù)定義2，X是一個(gè)超關(guān)鍵字

將x置為屬性集X的最后元素并調(diào)用算法2求X包含的候選關(guān)鍵字M；

ifM≠KthenreturnTrue;

elsereturnFalse}

定理3算法3可正確地判定某個(gè)頻繁項(xiàng)中元素x是否為主屬性。

證明算法3中X為候選關(guān)鍵字K添加了一個(gè)元素x后形成的超關(guān)鍵字，并且將x置為屬性集X的最后元素并調(diào)用算法2求X包含的候選關(guān)鍵字M，如果x為非主屬性，即x為超關(guān)鍵字X中唯一的冗余屬性，則x肯定被算法2從X中刪除，從而得到的候選關(guān)鍵字仍然為K；反之，如果x為主屬性，根據(jù)定義2，將x置為屬性集X的最后元素并調(diào)用算法2求X包含的候選關(guān)鍵字M時(shí)必然將x前面的某個(gè)元素刪除。這是因?yàn)檎{(diào)用算法2時(shí)嘗試刪除這個(gè)元素后，因?yàn)閤可等價(jià)替換這個(gè)主屬性，導(dǎo)致算法2中此時(shí)屬性閉包不會(huì)發(fā)生變化；否則如果沒(méi)有前面某個(gè)等價(jià)的主屬性刪除，而此時(shí)x為主屬性不會(huì)被作為冗余屬性刪除，則M=K∪{x}。根據(jù)定義2可知，因?yàn)镵是候選關(guān)鍵字導(dǎo)致M是超關(guān)鍵字，這與M是候選關(guān)鍵字相矛盾。故而，算法3是正確的。

□

3.4 基于主屬性識(shí)別的約簡(jiǎn)關(guān)聯(lián)規(guī)則挖掘

關(guān)系R的一個(gè)候選關(guān)鍵字中的主屬性可分為3種：(1)只包含在FD集中函數(shù)依賴的左部的R的屬性；(2)在FD集中沒(méi)有出現(xiàn)過(guò)的關(guān)系R的屬性；(3)在FD集中函數(shù)依賴的左部和右部都出現(xiàn)過(guò)的R的屬性。

定理4[15]在FD集中沒(méi)有出現(xiàn)過(guò)的關(guān)系R的屬性必為主屬性。

定理5[15]只包含在FD集中函數(shù)依賴的左部的關(guān)系R的屬性必為主屬性。

由文獻(xiàn)[15]可知,在FD集中函數(shù)依賴的左部和右部都出現(xiàn)過(guò)的關(guān)系R的屬性不一定為主屬性，需要進(jìn)行判定。為了描述方便，本文記只包含在FD集中函數(shù)依賴的左部的R的屬性構(gòu)成集合為K1={FD集中所有依賴的左部}-{FD集中所有依賴的右部}，在FD集中沒(méi)有出現(xiàn)過(guò)的關(guān)系R的屬性構(gòu)成集合為K2=關(guān)系R的屬性集U-{FD集包含的所有屬性}，在FD集中函數(shù)依賴的左部和右部都出現(xiàn)過(guò)的R的屬性構(gòu)成集合為K3=關(guān)系R的屬性集U-K1-K2。

算法4基于主屬性判定的約簡(jiǎn)關(guān)聯(lián)規(guī)則挖掘 Apriori-KAD(Apriori based on Key Attributes Decision)

輸入：事務(wù)集I，minsupp，minconf。

輸出：關(guān)聯(lián)規(guī)則集Associate-ruleset。

begin

(1) 利用最小支持度minsupp和“Apriori性質(zhì)”找到事務(wù)集I中所有頻繁項(xiàng)集Item-set；

for每個(gè)頻繁項(xiàng)集X∈Item-setdo

{for每個(gè)元素x∈Xdo

{ifx∈K1then

{FD集中左部包含x的所有依賴的左部構(gòu)成屬性集X1并求其閉包X1+；

ifX∈X1+then

Item-set:=Item-set-{X};}

ifx∈K3then

{調(diào)用算法3判定x是否為主屬性；

ifx為主屬性then

{FD集中左部包含x的所有依賴的左部構(gòu)成屬性集X1并求其閉包X1+；

ifX∈X1+then

Item-set:=Item-set-{X};}}}}

(2) 利用最小置信度minconf將第(1)步找到的頻繁項(xiàng)集轉(zhuǎn)換為關(guān)聯(lián)規(guī)則集Associate-ruleset；

returnAssociate-ruleset；

end

定理6算法4是正確的。

證明由定理2、定理3和定理4可知，算法4正確地判定了關(guān)聯(lián)規(guī)則挖掘算法Apriori計(jì)算得到的頻繁項(xiàng)中是否包含主屬性。由定義6可知，當(dāng)x∈K2時(shí)，由于x是在FD集中沒(méi)有出現(xiàn)過(guò)的關(guān)系R的屬性，即不存在關(guān)于x的函數(shù)依賴，也就不會(huì)存在關(guān)于x的局部依賴，即本文考慮的冗余信息的頻繁出現(xiàn)問(wèn)題不會(huì)出現(xiàn)，所以算法只考慮x∈K1和x∈K32種情況下會(huì)出現(xiàn)的局部依賴。由定理4可知，x∈K1時(shí)x必為主屬性，由定理2可知,x∈K3時(shí)算法3可以正確判定x是否為主屬性。

根據(jù)前文的描述，我們認(rèn)為最小支持度應(yīng)該大于1，即只頻繁出現(xiàn)1次的現(xiàn)實(shí)意義不大，所以關(guān)聯(lián)規(guī)則挖掘算法Apriori計(jì)算得到的頻繁項(xiàng)中不會(huì)包含候選關(guān)鍵字。因?yàn)楦鶕?jù)定義2可知，一個(gè)候選關(guān)鍵字能唯一標(biāo)識(shí)數(shù)據(jù)庫(kù)中一條記錄，即候選關(guān)鍵字和數(shù)據(jù)庫(kù)中屬性字段的值是一一對(duì)應(yīng)的，由此可以斷定算法Apriori計(jì)算得到的頻繁項(xiàng)中若包含了主屬性且該頻繁項(xiàng)屬于這個(gè)主屬性相關(guān)的屬性閉包，則由定義6可知，該頻繁項(xiàng)中屬性構(gòu)成了一個(gè)局部依賴。這正是導(dǎo)致規(guī)范化表通過(guò)連接形成綜合信息時(shí)會(huì)頻繁出現(xiàn)冗余信息的原因，即算法4正確地找到了挖掘算法Apriori計(jì)算得到的頻繁項(xiàng)中包含的局部依賴。故算法4達(dá)到了約簡(jiǎn)算法Apriori計(jì)算得到頻繁項(xiàng)集的目的，即算法4是正確的。

□

4 實(shí)驗(yàn)設(shè)計(jì)及分析

本文利用微軟公司的SQL SERVER 2008 R2提供的SSMS(SQL Server Management Studio)部件建立實(shí)驗(yàn)環(huán)境中的數(shù)據(jù)庫(kù)和SQL Server BIDS(Business Intelligence Development Studio)部件建立一個(gè)關(guān)聯(lián)規(guī)則挖掘分析項(xiàng)目。實(shí)驗(yàn)中使用的數(shù)據(jù)來(lái)源于網(wǎng)絡(luò)提供的一個(gè)用于測(cè)試的腎癌數(shù)據(jù)庫(kù)(http://www.wsbookshow.com/bookshow/jc/yjs/qtl/11269.html下載案例文件，見(jiàn)sql范例資料.xsl中腎癌數(shù)據(jù))。腎癌數(shù)據(jù)庫(kù)的表結(jié)構(gòu)如下所示(帶下劃線字段為關(guān)鍵字)：

腎癌(標(biāo)本編號(hào)，患者編號(hào)，患者的年齡(歲)，患者姓名，檢測(cè)日期，腎癌細(xì)胞核組織學(xué)分級(jí)，腎細(xì)胞癌分級(jí)，腎細(xì)胞癌血管內(nèi)皮生長(zhǎng)因子(VEGF)，腎細(xì)胞癌轉(zhuǎn)移情況，腎細(xì)胞癌組織內(nèi)微血管數(shù)(MVC)，主治醫(yī)師)。

在這個(gè)數(shù)據(jù)表中，關(guān)鍵字為“標(biāo)本編號(hào)”，候選關(guān)鍵字還有(患者編號(hào)，檢測(cè)日期)，存在如下的FD集：{ 患者編號(hào)→患者姓名，患者編號(hào)→主治醫(yī)師}。由于{患者編號(hào)}?{患者編號(hào)，檢測(cè)日期}，根據(jù)定義6可知上述2個(gè)依賴是局部依賴。

4.1 現(xiàn)有關(guān)聯(lián)規(guī)則挖掘方法分析結(jié)果

本節(jié)設(shè)置最小支持度為40%，利用現(xiàn)有關(guān)聯(lián)規(guī)則挖掘方法得到頻繁項(xiàng)集 93項(xiàng)，但其中包含了大量冗余信息，比如患者姓名、主治醫(yī)師等，運(yùn)行結(jié)果如圖1所示。

Figure 1 Associate rule set by the existing mining method with mini-support=40% and mini-conf=30%圖1 現(xiàn)有關(guān)聯(lián)規(guī)則挖掘方法得到的規(guī)則集(最小支持度為40%，置信度為30%)

從圖1可以看到“主治醫(yī)師=王強(qiáng)4?腎細(xì)胞癌轉(zhuǎn)移情況=有轉(zhuǎn)移”“〈患者姓名= 張六，患者編號(hào)≥6〉?腎細(xì)胞癌轉(zhuǎn)移情況=有轉(zhuǎn)移”這樣的規(guī)則正是由于數(shù)據(jù)庫(kù)中存在如下的FD函數(shù)依賴{患者編號(hào)→患者姓名，患者編號(hào)→主治醫(yī)師}，這些局部依賴使得冗余信息頻繁出現(xiàn)，而這樣的規(guī)則是我們不關(guān)注的、沒(méi)有實(shí)際價(jià)值的關(guān)聯(lián)規(guī)則。

4.2 基于主屬性判定的約簡(jiǎn)關(guān)聯(lián)規(guī)則挖掘

如前所述，在這個(gè)腎癌數(shù)據(jù)表上，關(guān)鍵字為“標(biāo)本編號(hào)”，候選關(guān)鍵字還有(患者編號(hào)，檢測(cè)日期)，存在如下的FD集：{患者編號(hào)→患者姓名，患者編號(hào)→主治醫(yī)師}。由于{患者編號(hào)}?{患者編號(hào)，檢測(cè)日期}，根據(jù)定義6,這個(gè)表中存在2個(gè)局部依賴，且“患者編號(hào)”是出現(xiàn)在頻繁項(xiàng)集中的主屬性，因?yàn)椤盎颊呔幪?hào)”存在于候選關(guān)鍵字(患者編號(hào)，檢測(cè)日期)上，算法4將消除(患者編號(hào)，患者姓名)，(患者編號(hào)，主治醫(yī)師)這些由于局部依賴導(dǎo)致的頻繁項(xiàng)。

消除局部依賴即冗余信息比如患者姓名、主治醫(yī)師后，在最小支持度為40%時(shí)，基于主屬性判定的約簡(jiǎn)關(guān)聯(lián)規(guī)則挖掘算法得到的頻繁項(xiàng)集有49項(xiàng)，運(yùn)行結(jié)果如圖2所示。從圖2可以看出，本文所提算法在消除了局部依賴帶來(lái)的冗余信息后，在最小支持度為40%時(shí)挖掘到的頻繁項(xiàng)集從93項(xiàng)約簡(jiǎn)為49項(xiàng)，設(shè)置最小置信度也為30%得到規(guī)則集的大小為27，比圖1中常規(guī)挖掘方法在同樣的設(shè)置參數(shù)下挖掘到關(guān)聯(lián)規(guī)則集為101個(gè)大大減少，而且因?yàn)橄巳哂嘈畔?lái)的頻繁出現(xiàn)，圖1中展示的冗余信息導(dǎo)致的關(guān)聯(lián)規(guī)則在圖2中沒(méi)有出現(xiàn)。

Figure 2 Associate rule set by the proposed algorithm with mini-support=40% and mini-conf=30%圖2 本文所提算法得到的規(guī)則集(最小支持度為40%，置信度為30%)

5 結(jié)束語(yǔ)

現(xiàn)有的基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘會(huì)產(chǎn)生很多規(guī)則，用戶難以準(zhǔn)確地理解這些規(guī)則，更難以挑選合適的規(guī)則。針對(duì)當(dāng)前關(guān)聯(lián)規(guī)則挖掘方法得到的關(guān)聯(lián)規(guī)則數(shù)量過(guò)多的現(xiàn)象，本文提出了基于頻繁項(xiàng)中包含主屬性的判定算法，并消除了因?yàn)榫植恳蕾噷?dǎo)致的冗余信息的頻繁出現(xiàn)，從而使挖掘出的關(guān)聯(lián)規(guī)則針對(duì)性強(qiáng)，也利于用戶的理解。實(shí)驗(yàn)結(jié)果也驗(yàn)證了本文算法的正確性和有效性。