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

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

1 引言

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

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

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

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

2 相關(guān)知識

2.1 規(guī)則分析方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：屬性X,FD集F。

輸出：X相對于F的閉包X+。

{X+=X;

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

X+=X+∪V;}

while(X+有所改變);

}

定義4[14]如果關(guān)系模式R的每個關(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]對于FDW→A，如果存在X?W有X→A成立，那么稱W→A是局部依賴(A局部依賴于W)；否則稱W→A是完全依賴。

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

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

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

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

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

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

Create view course-view as

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

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

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

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

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

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

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

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

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

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

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

{X:=U;

調(diào)用算法1求X的閉包X+；//X一個超關(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ā)生變化即變小了，說明刪除的屬性為主屬性，即當(dāng)前X不再是關(guān)鍵字*/

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

}

return(X)}

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

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

□

3.3 頻繁項為主屬性的識別方法

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

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

算法3判定頻繁項中元素x是否為主屬性

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

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

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

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

ifM≠KthenreturnTrue;

elsereturnFalse}

定理3算法3可正確地判定某個頻繁項中元素x是否為主屬性。

證明算法3中X為候選關(guān)鍵字K添加了一個元素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時必然將x前面的某個元素刪除。這是因為調(diào)用算法2時嘗試刪除這個元素后，因為x可等價替換這個主屬性，導(dǎo)致算法2中此時屬性閉包不會發(fā)生變化；否則如果沒有前面某個等價的主屬性刪除，而此時x為主屬性不會被作為冗余屬性刪除，則M=K∪{x}。根據(jù)定義2可知，因為K是候選關(guān)鍵字導(dǎo)致M是超關(guān)鍵字，這與M是候選關(guān)鍵字相矛盾。故而，算法3是正確的。

□

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

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

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

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

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

算法4基于主屬性判定的約簡關(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中所有頻繁項集Item-set；

for每個頻繁項集X∈Item-setdo

{for每個元素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)步找到的頻繁項集轉(zhuǎn)換為關(guān)聯(lián)規(guī)則集Associate-ruleset；

returnAssociate-ruleset；

end

定理6算法4是正確的。

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

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

□

4 實驗設(shè)計及分析

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

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

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

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

本節(jié)設(shè)置最小支持度為40%，利用現(xiàn)有關(guān)聯(lián)規(guī)則挖掘方法得到頻繁項集 93項，但其中包含了大量冗余信息，比如患者姓名、主治醫(yī)師等，運行結(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ī)師=王強4?腎細(xì)胞癌轉(zhuǎn)移情況=有轉(zhuǎn)移”“〈患者姓名= 張六，患者編號≥6〉?腎細(xì)胞癌轉(zhuǎn)移情況=有轉(zhuǎn)移”這樣的規(guī)則正是由于數(shù)據(jù)庫中存在如下的FD函數(shù)依賴{患者編號→患者姓名，患者編號→主治醫(yī)師}，這些局部依賴使得冗余信息頻繁出現(xiàn)，而這樣的規(guī)則是我們不關(guān)注的、沒有實際價值的關(guān)聯(lián)規(guī)則。

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

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

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

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