王培培，孟 蕓

(河南大學(xué)民生學(xué)院，河南 開封 475000)

1 引言

伴隨數(shù)據(jù)信息的迅速傳播，數(shù)據(jù)挖掘技術(shù)可以使人們在巨大網(wǎng)絡(luò)空間當(dāng)中選取自己所需要的信息和知識。數(shù)據(jù)挖掘是從含有大量數(shù)據(jù)集合中提取隱藏的重要信息或關(guān)鍵知識，將其轉(zhuǎn)化為另一種簡便、易懂的形式。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中必不可少的一部分，數(shù)據(jù)信息之間存在的相關(guān)聯(lián)系得到人們高度重視，具有廣泛的應(yīng)用前景。

自關(guān)聯(lián)規(guī)則挖掘問題被提出后，有部分人不斷質(zhì)疑其局限性，為了避免產(chǎn)生冗余虛假規(guī)則，引入新的閾值，從而加強(qiáng)對關(guān)聯(lián)規(guī)則的評判。

朱益立[1]等人提出了一種有向無環(huán)圖的挖掘算法，根據(jù)候選項集構(gòu)建二進(jìn)制表，計算出所構(gòu)建二進(jìn)制表支持度，作為有向無環(huán)圖邊權(quán)值，運用人工設(shè)置閾值判斷計算出的邊權(quán)值是否需要保留，整個構(gòu)建過程只需掃描一次數(shù)據(jù)庫，不會產(chǎn)生候選項集。具有較好的性能。

喬少杰[2]等人提出了一種正負(fù)雙支持度的關(guān)聯(lián)規(guī)則挖掘算法，在頻繁項集發(fā)現(xiàn)階段，引入最大支持度以解決過頻繁問題，再運用建立負(fù)項頻繁模式樹進(jìn)行遞歸挖掘，引入支持度計數(shù)矩陣提高了正負(fù)頻繁項的發(fā)現(xiàn)效率。強(qiáng)關(guān)聯(lián)規(guī)則發(fā)現(xiàn)階段，通過設(shè)置合適的置信度閾值和采用互信息進(jìn)行相關(guān)性分析判定藥物項集的關(guān)聯(lián)關(guān)系。最后驗證了所提方法較在挖掘的時效性和準(zhǔn)確性上有較大提高。

上述兩種方法在關(guān)聯(lián)規(guī)則挖掘時忽略了數(shù)據(jù)在集合內(nèi)分布頻率的不同特點，在挖掘時，存在時間較長、復(fù)雜度高、規(guī)則冗余等問題，本文所提方法通過多段支持度算法獲得最小支持度和最小置信度，在挖掘時利用數(shù)據(jù)集縮減，實現(xiàn)多段支持度數(shù)據(jù)頻繁模式關(guān)聯(lián)規(guī)則挖掘，且具有較高適用性和可行性。

2 多段支持度分析

2.1 多段支持度算法

關(guān)聯(lián)規(guī)則可以有效的反應(yīng)出眾多數(shù)據(jù)中各個對象之間的關(guān)聯(lián)程度，并能夠挖掘出數(shù)據(jù)集內(nèi)所包含的重要信息，并在多各領(lǐng)域中廣泛應(yīng)用。

在相關(guān)規(guī)則[3]當(dāng)中，把一個數(shù)據(jù)項集內(nèi)各個對象的數(shù)量作為項集長度，且長度是k的數(shù)據(jù)項集作為k項集。數(shù)據(jù)集中頻繁項集就是滿足最小支持度的項集，頻繁項集整體模式就是其包含的項集的數(shù)量，利用各個項集中多段支持度的計算，尋找最頻繁的項集。假設(shè)有m個項目，在多個不相同的項集中數(shù)量增加到2m-1個，在眾多數(shù)據(jù)集D內(nèi)，依據(jù)網(wǎng)絡(luò)中產(chǎn)生的頻率確定其最少支持度閥值，并挖掘出多段支持度數(shù)據(jù)頻繁模式中有效關(guān)聯(lián)規(guī)則。

建立多段支持度模型，關(guān)聯(lián)規(guī)則挖掘使用的是逐步搜索方法，在眾多候選項集內(nèi)選取頻繁項集。依據(jù)數(shù)據(jù)項在數(shù)據(jù)集內(nèi)出現(xiàn)的頻率來選擇最少支持度閾值，規(guī)則Min Supt等于所蘊(yùn)含的全部數(shù)據(jù)項的最少MIS。那么規(guī)則R的表達(dá)式即：

I1∧I2∧…∧Ik?Ik+1∧…∧Ir

(1)

其中Ii∈I，那么所得公式表示即

MinSupt(R)==min(MIS(I1)，MIS(I2)，…，MIS(Ir))

(2)

式(2)作為滿足規(guī)則的最小支持度[4]。假設(shè)數(shù)據(jù)項整體集的公式為

I={i1，i2，…，im}

(3)

對象之間相關(guān)數(shù)據(jù)[5]集合表達(dá)式為

D={T1，T2，…，Tn}

(4)

如對象T作為數(shù)據(jù)項子集，為T?I，每個項目中都具有一個識別編號TID。對象I中所得到的每個子集是X作為D所包含的項集，假設(shè)|X|=k，那么項集X作為對象k-的項集，若X?Ti，那么對象Ti中就蘊(yùn)含項集X。

首先，項集X的支持度表達(dá)式為

sup(X)=σx/|D|*100%

(5)

式中，|D|作為數(shù)據(jù)集D的事務(wù)數(shù)，σx作為數(shù)據(jù)集D內(nèi)所蘊(yùn)含項集X的事務(wù)數(shù)。

如sup(X)大于或等于指定的最小支持度，那么X就稱為頻繁集[6]，與之相反，若小于指定的最小支持度，那么X就稱為非頻繁集。關(guān)聯(lián)規(guī)則是類似X=>Y的邏輯式，式中X?T，Y?T，且X∩Y=Φ。

其次，若X=>Y事務(wù)集內(nèi)的支持度，數(shù)據(jù)集D中蘊(yùn)含的X，Y的事務(wù)數(shù)量和蘊(yùn)含X的事務(wù)數(shù)量之比值，公式為

X=>Y=sup(X∪Y)/sup(X)*100%

(6)

式(6)中，sup(X∪Y)是指規(guī)則X=>Y的多段支持度。

2.2 最小支持度計算

多段支持度的構(gòu)造過程需要2次掃描數(shù)據(jù)庫，第一次掃描累積事務(wù)數(shù)據(jù)庫內(nèi)的各個項以及支持度的計數(shù)和葉子數(shù)，計算其最小支持度。通過第二次掃描來擴(kuò)展事務(wù)數(shù)據(jù)庫。挖掘過程中也不需生成大量的候選項目集和頻繁地進(jìn)行模式匹配。

達(dá)到預(yù)期最小支持度和最小置信度的關(guān)聯(lián)規(guī)則顯得格外關(guān)鍵。挖掘數(shù)據(jù)頻繁模式關(guān)聯(lián)規(guī)則[7]主要步驟分為：

步驟1：挖倔數(shù)據(jù)集內(nèi)所有頻繁集。

步驟2：依據(jù)頻繁集，挖掘相對的關(guān)聯(lián)規(guī)則。

因為步驟2較為簡便，只要獲得頻繁集，就能輕易推導(dǎo)出關(guān)聯(lián)規(guī)則，所以步驟1的處理顯得尤為重要，其決定著關(guān)聯(lián)規(guī)則的挖掘性能，同時也是衡量挖掘方法的首要標(biāo)準(zhǔn)。在各個結(jié)點中巧妙的通過互聯(lián)網(wǎng)傳對重要信息進(jìn)行有效的轉(zhuǎn)換，最終在整個事務(wù)數(shù)據(jù)庫中挖掘出關(guān)聯(lián)規(guī)則。

在多段支持度模型中，給數(shù)據(jù)項集內(nèi)各個單獨項設(shè)定滿足所需條件的最小支持度。尋找頻繁集時，利用相關(guān)項集內(nèi)每個項最小支持度的最大值或最小值進(jìn)行挖掘。

以最小值作為最小支持度的算法，在頻繁子集內(nèi)不能保證全部子集都是頻繁的。設(shè)定數(shù)據(jù)集為

D，I={A，B，C，D}

(7)

那么可知公式為

MIS(A)=4

MIS(B)=3

MIS(C)=1

MIS(D)=2

(8)

依據(jù)多支持度最小值算法，在挖掘2-項集的過程中，可得出式(9)即

sup(AB)=2

(9)

故子集(AB)是非頻繁集。在挖掘3-項集的過程中，可得出式(10)即：

sup(ABC)==2>min(MIS(A)，MIS(B)，MIS(C))

(10)

故子集(ABC)是頻繁集。

為了達(dá)到最小值作為最小支持度算法的地推性，把數(shù)據(jù)項集I內(nèi)的每個單獨項以MIS值實施有序排列，事務(wù)T內(nèi)的每個單獨項也按照MIS值實施有序排列。在形成頻繁集L2的過程中，運用待選集C1并非頻繁集L1，因頻繁集L1內(nèi)不包括原本支持度比本身MIS小的項，且比之前各個項MIS的項。用頻繁集Lk-1所形成的待選集Ck，由于使用了排序，每個數(shù)據(jù)項按照MIS的項進(jìn)行升序排列，把較高M(jìn)IS值的數(shù)據(jù)項擴(kuò)大，確保了達(dá)到最小值作為最小支持度算法的地推性。

在關(guān)聯(lián)規(guī)則挖掘的過程中，能有效地結(jié)合實際情況，挖掘出讓用戶感興趣的規(guī)則[8]，在最小支持度的基礎(chǔ)上進(jìn)行頻繁項集挖掘，能夠排除許多冗余特征和虛假規(guī)則，減少工作量、節(jié)省時間。

3 數(shù)據(jù)頻繁模式關(guān)聯(lián)規(guī)則挖掘

3.1 數(shù)據(jù)集縮減

關(guān)聯(lián)規(guī)則是指在特定數(shù)據(jù)集中頻繁出現(xiàn)項集的規(guī)則[9]，關(guān)聯(lián)規(guī)則挖掘的重要方向就是從數(shù)據(jù)庫中獲取滿足支持度和信任度閾值的規(guī)則。

在關(guān)聯(lián)規(guī)則挖掘的過程中，頻繁模式的發(fā)掘顯得尤為重要。根據(jù)挖掘過程中所獲結(jié)果的不確定性，關(guān)聯(lián)規(guī)則的挖掘可以分為4種，分別是完全頻繁項集挖掘、頻繁閉項集挖掘、頻繁表示集挖掘以及最大頻繁項集挖掘。按照頻繁項集向上閉包原則[10]，最大頻繁項集內(nèi)具有全部頻繁項集，并且在大多數(shù)挖掘過程中，最大頻繁項集能夠滿足現(xiàn)實需求，故最大頻繁項集挖掘具有較強(qiáng)適用性。

在待挖掘的用戶群中，掃描其對應(yīng)的數(shù)據(jù)集D，建立起訪問頁面矩陣，并以及訪問整體數(shù)量進(jìn)行統(tǒng)計，然后依次排序，進(jìn)行矩陣掃描，按照排序順序經(jīng)訪問頁面建立起節(jié)點構(gòu)建FP-tree樹，最后按照排序，依次對樹中每個結(jié)點進(jìn)行一次訪問，不小于支持度的作為頻繁模式。

在訪問頁面按照順序建立樹節(jié)點，可準(zhǔn)確、有效的挖掘頻繁模式。(A，C，E)，(A，D，E)，(A，B，E)的支持度大于規(guī)定值，若依照常規(guī)樹結(jié)構(gòu)挖掘方法[11]輸入后遍歷，那么就不是頻繁模式，繼續(xù)調(diào)整順序再次輸入，因頁面A，E的數(shù)量較大，而(A，E)的支持度不小于規(guī)定值，故是頻繁模式。

為了更好地對關(guān)聯(lián)規(guī)則進(jìn)行有效挖掘。故描述算法如下：

輸入：DB原有數(shù)據(jù)集，Lk是DB內(nèi)的項集，db是新增數(shù)據(jù)集，s是指出度閾值[12]。

1)1項集挖掘

2)k項集挖掘

(11)

掃描db，累積在W內(nèi)的項在db中的支持度，計算C在db中的支持度。

運用數(shù)據(jù)集縮減技術(shù)，把集合P作為非頻繁項，若事務(wù)中包含P，可知該事務(wù)在頻繁模式關(guān)聯(lián)規(guī)則挖掘中，將不重要，可將其從數(shù)據(jù)集內(nèi)去除。頻繁掃描數(shù)據(jù)集DB和db，達(dá)到縮減數(shù)據(jù)集的效果。

使用多支持度中的最小值對頻繁項集進(jìn)行剪枝，降低了算法的時間復(fù)雜度，不會造成規(guī)則遺漏的現(xiàn)象，用時短，挖掘快速。

3.2 FP-tree算法

若數(shù)據(jù)庫內(nèi)有個結(jié)點分別是P1，P2以及P3，那么局部數(shù)據(jù)庫就分為DB1，DB2和DB3。在任意結(jié)點的數(shù)據(jù)庫如表1所示，最小支持度的閾值為minsup=0.4。

表1 局部數(shù)據(jù)庫

從表1與minsup=0.4中得出全局的頻繁項目。依據(jù)支持度的排列順序，如表2所示。全局頻繁項目的集合為：

表2 全局頻繁模式及多段支持度

E={c，b，f，q，a，m，k}

(12)

在結(jié)點P1，P2以及P3中，按照E建立FP-tree1，F(xiàn)P-tree2和FP-tree3。每個局部FP-treei僅包括全局頻繁項目。

結(jié)點P1利用FP-tree1，采用頻繁模式增長算法計算出DB1的局部頻繁項集即

(13)

結(jié)點P2利用FP-tree2，采用頻繁模式增長算法計算出DB2的局部頻繁項集即

F2≠?

(14)

結(jié)點P3利用FP-tree3，采用頻繁模式增長算法計算出DB3的局部頻繁項集即

F3={{c，b}，{q，k}}

(15)

中心結(jié)點P0匯總得到全部結(jié)點局部頻繁項集的并集，其公式為

(16)

運用頂端和低端策略對F′實施修剪，獲得挖掘的全局頻繁項集為：

F={{c，b}，{c，a}}

(17)

通過以上算法，可以很明確的在數(shù)據(jù)集中尋找到最終產(chǎn)生頻繁模式進(jìn)行關(guān)聯(lián)規(guī)則有效挖掘，使挖掘更加便捷，算法性能優(yōu)勢更加明顯，具有較強(qiáng)優(yōu)越性。

4 實驗分析

為了驗證挖掘方法的有效性，在實驗中采用運行環(huán)境主機(jī)CPU主頻是1.7GHz，2GB的內(nèi)存容量，使用Windows XP操作應(yīng)用系統(tǒng)，C++語言編程代碼，數(shù)據(jù)結(jié)構(gòu)定義以C++的STL標(biāo)準(zhǔn)模板庫。

運用軟件Clementine中交易數(shù)據(jù)集進(jìn)行測試，其中有57354條記錄，30個屬性，分別表示商場內(nèi)的飲品、面包、薯片等商品，在數(shù)據(jù)集中0代表無出售，1代表有出售。需要對原數(shù)據(jù)集預(yù)處理，獲取出售2種商品以上的事務(wù)共42359條數(shù)據(jù)，以事務(wù)數(shù)據(jù)庫規(guī)格保存在文件內(nèi)。

根據(jù)多段支持度算法設(shè)置各項MIS，憑借項目在數(shù)據(jù)集內(nèi)的實際頻率乘以系數(shù)即f(i)×β，來分配MIS。在實驗中β=0.1，圖1作為多段支持度最小值算法、文獻(xiàn)[1]算法以及文獻(xiàn)[2]算法產(chǎn)生的運行時間比較。

圖1 運行時間

從圖1中可以看出，采用3種算法進(jìn)行比較分析，多段支持度算法具有快速收斂的性質(zhì)，其最終產(chǎn)生的運行時間始終保持平衡。圖2作為關(guān)聯(lián)規(guī)則的數(shù)量。

圖2 關(guān)聯(lián)規(guī)則數(shù)量

圖2是置信度為10%的情況下，各個算法中賦有的關(guān)聯(lián)規(guī)則的數(shù)量。從圖中可以看出，多段支持度算法能夠根據(jù)不同情況自動靈活調(diào)整各數(shù)據(jù)集內(nèi)最小支持度，對待選集和頻繁集進(jìn)行收斂。上述實驗采取了有效的剪枝，確保頻繁模式的可行性，挖掘出最具有價值的關(guān)聯(lián)規(guī)則。

圖3用于檢測不同方法的置信度，置信度也成為可靠度，置信區(qū)間范圍越大證明方法的可靠度越高。從圖3中可以看出，本文方法的置信范圍始終在40之內(nèi)，而文獻(xiàn)[1]方法的置信范圍較小，且多數(shù)在0處波動?？梢宰C明本文方法置信度更高，準(zhǔn)確性更好。

圖3 不同方法的置信度

5 總結(jié)

在多段支持度和數(shù)據(jù)集變化的情況下，進(jìn)行關(guān)聯(lián)規(guī)則挖掘，能夠清晰、明確地發(fā)現(xiàn)其中所蘊(yùn)含的頻繁模式，再挖掘出頻繁模式重要信息，提高挖掘性能。仿真結(jié)果表明：本文所提挖掘方法在基于多段支持度數(shù)據(jù)頻繁模式關(guān)聯(lián)規(guī)則挖掘中，相比其它方法在規(guī)則數(shù)量以及運行時間上都有顯著的優(yōu)越性。