多段支持度數據頻繁模式關聯規則挖掘仿真

王培培，孟 蕓

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

1 引言

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

自關聯規則挖掘問題被提出后，有部分人不斷質疑其局限性，為了避免產生冗余虛假規則，引入新的閾值，從而加強對關聯規則的評判。

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

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

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

2 多段支持度分析

2.1 多段支持度算法

關聯規則可以有效的反應出眾多數據中各個對象之間的關聯程度，并能夠挖掘出數據集內所包含的重要信息，并在多各領域中廣泛應用。

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

建立多段支持度模型，關聯規則挖掘使用的是逐步搜索方法，在眾多候選項集內選取頻繁項集。依據數據項在數據集內出現的頻率來選擇最少支持度閾值，規則Min Supt等于所蘊含的全部數據項的最少MIS。那么規則R的表達式即：

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

(1)

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

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

(2)

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

I={i1，i2，…，im}

(3)

對象之間相關數據[5]集合表達式為

D={T1，T2，…，Tn}

(4)

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

首先，項集X的支持度表達式為

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

(5)

式中，|D|作為數據集D的事務數，σx作為數據集D內所蘊含項集X的事務數。

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

其次，若X=>Y事務集內的支持度，數據集D中蘊含的X，Y的事務數量和蘊含X的事務數量之比值，公式為

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

(6)

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

2.2 最小支持度計算

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

達到預期最小支持度和最小置信度的關聯規則顯得格外關鍵。挖掘數據頻繁模式關聯規則[7]主要步驟分為：

步驟1：挖倔數據集內所有頻繁集。

步驟2：依據頻繁集，挖掘相對的關聯規則。

因為步驟2較為簡便，只要獲得頻繁集，就能輕易推導出關聯規則，所以步驟1的處理顯得尤為重要，其決定著關聯規則的挖掘性能，同時也是衡量挖掘方法的首要標準。在各個結點中巧妙的通過互聯網傳對重要信息進行有效的轉換，最終在整個事務數據庫中挖掘出關聯規則。

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

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

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

(7)

那么可知公式為

MIS(A)=4

MIS(B)=3

MIS(C)=1

MIS(D)=2

(8)

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

sup(AB)=2

(9)

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

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

(10)

故子集(ABC)是頻繁集。

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

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

3 數據頻繁模式關聯規則挖掘

3.1 數據集縮減

關聯規則是指在特定數據集中頻繁出現項集的規則[9]，關聯規則挖掘的重要方向就是從數據庫中獲取滿足支持度和信任度閾值的規則。

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

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

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

為了更好地對關聯規則進行有效挖掘。故描述算法如下：

輸入：DB原有數據集，Lk是DB內的項集，db是新增數據集，s是指出度閾值[12]。

1)1項集挖掘

2)k項集挖掘

(11)

掃描db，累積在W內的項在db中的支持度，計算C在db中的支持度。

運用數據集縮減技術，把集合P作為非頻繁項，若事務中包含P，可知該事務在頻繁模式關聯規則挖掘中，將不重要，可將其從數據集內去除。頻繁掃描數據集DB和db，達到縮減數據集的效果。

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

3.2 FP-tree算法

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

表1 局部數據庫

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

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

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

(12)

在結點P1，P2以及P3中，按照E建立FP-tree1，FP-tree2和FP-tree3。每個局部FP-treei僅包括全局頻繁項目。

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

(13)

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

F2≠?

(14)

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

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

(15)

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

(16)

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

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

(17)

通過以上算法，可以很明確的在數據集中尋找到最終產生頻繁模式進行關聯規則有效挖掘，使挖掘更加便捷，算法性能優勢更加明顯，具有較強優越性。

4 實驗分析

為了驗證挖掘方法的有效性，在實驗中采用運行環境主機CPU主頻是1.7GHz，2GB的內存容量，使用Windows XP操作應用系統，C++語言編程代碼，數據結構定義以C++的STL標準模板庫。

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

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

圖1 運行時間

從圖1中可以看出，采用3種算法進行比較分析，多段支持度算法具有快速收斂的性質，其最終產生的運行時間始終保持平衡。圖2作為關聯規則的數量。

圖2 關聯規則數量

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

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

圖3 不同方法的置信度

5 總結

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