王培培，孟 蕓

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

1 引言

伴隨數(shù)據(jù)信息的迅速傳播，數(shù)據(jù)挖掘技術(shù)可以使人們?cè)诰薮缶W(wǎng)絡(luò)空間當(dāng)中選取自己所需要的信息和知識(shí)。數(shù)據(jù)挖掘是從含有大量數(shù)據(jù)集合中提取隱藏的重要信息或關(guān)鍵知識(shí)，將其轉(zhuǎn)化為另一種簡(jiǎ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)對(duì)關(guān)聯(lián)規(guī)則的評(píng)判。

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

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

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

2 多段支持度分析

2.1 多段支持度算法

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

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

建立多段支持度模型，關(guān)聯(lián)規(guī)則挖掘使用的是逐步搜索方法，在眾多候選項(xiàng)集內(nèi)選取頻繁項(xiàng)集。依據(jù)數(shù)據(jù)項(xiàng)在數(shù)據(jù)集內(nèi)出現(xiàn)的頻率來選擇最少支持度閾值，規(guī)則Min Supt等于所蘊(yùn)含的全部數(shù)據(jù)項(xiàng)的最少M(fèi)IS。那么規(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ù)項(xiàng)整體集的公式為

I={i1，i2，…，im}

(3)

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

D={T1，T2，…，Tn}

(4)

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

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

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

(5)

式中，|D|作為數(shù)據(jù)集D的事務(wù)數(shù)，σx作為數(shù)據(jù)集D內(nèi)所蘊(yùn)含項(xiàng)集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 最小支持度計(jì)算

多段支持度的構(gòu)造過程需要2次掃描數(shù)據(jù)庫(kù)，第一次掃描累積事務(wù)數(shù)據(jù)庫(kù)內(nèi)的各個(gè)項(xiàng)以及支持度的計(jì)數(shù)和葉子數(shù)，計(jì)算其最小支持度。通過第二次掃描來擴(kuò)展事務(wù)數(shù)據(jù)庫(kù)。挖掘過程中也不需生成大量的候選項(xiàng)目集和頻繁地進(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ù)頻繁集，挖掘相對(duì)的關(guān)聯(lián)規(guī)則。

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

在多段支持度模型中，給數(shù)據(jù)項(xiàng)集內(nèi)各個(gè)單獨(dú)項(xiàng)設(shè)定滿足所需條件的最小支持度。尋找頻繁集時(shí)，利用相關(guān)項(xiàng)集內(nèi)每個(gè)項(xiàng)最小支持度的最大值或最小值進(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-項(xiàng)集的過程中，可得出式(9)即

sup(AB)=2

(9)

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

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

(10)

故子集(ABC)是頻繁集。

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

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

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

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

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

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

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

在訪問頁面按照順序建立樹節(jié)點(diǎn)，可準(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ī)定值，故是頻繁模式。

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

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

1)1項(xiàng)集挖掘

2)k項(xiàng)集挖掘

(11)

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

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

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

3.2 FP-tree算法

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

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

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

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

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

(12)

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

結(jié)點(diǎn)P1利用FP-tree1，采用頻繁模式增長(zhǎng)算法計(jì)算出DB1的局部頻繁項(xiàng)集即

(13)

結(jié)點(diǎn)P2利用FP-tree2，采用頻繁模式增長(zhǎng)算法計(jì)算出DB2的局部頻繁項(xiàng)集即

F2≠?

(14)

結(jié)點(diǎn)P3利用FP-tree3，采用頻繁模式增長(zhǎng)算法計(jì)算出DB3的局部頻繁項(xiàng)集即

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

(15)

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

(16)

運(yùn)用頂端和低端策略對(duì)F′實(shí)施修剪，獲得挖掘的全局頻繁項(xiàng)集為：

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

(17)

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

4 實(shí)驗(yàn)分析

為了驗(yàn)證挖掘方法的有效性，在實(shí)驗(yàn)中采用運(yùn)行環(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)模板庫(kù)。

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

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

圖1 運(yùn)行時(shí)間

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

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

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

圖3用于檢測(cè)不同方法的置信度，置信度也成為可靠度，置信區(qū)間范圍越大證明方法的可靠度越高。從圖3中可以看出，本文方法的置信范圍始終在40之內(nèi)，而文獻(xiàn)[1]方法的置信范圍較小，且多數(shù)在0處波動(dòng)?？梢宰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ùn)行時(shí)間上都有顯著的優(yōu)越性。