基于投影模式支持集的數據挖掘算法研究

楊 曉 波

(浙江財經大學東方學院 浙江 杭州 314408)

?

基于投影模式支持集的數據挖掘算法研究

楊 曉 波

(浙江財經大學東方學院 浙江 杭州 314408)

為了進一步提高頻繁模式數據挖掘算法的效率，提出一種基于投影模式支持集的數據挖掘算法。具體研究過程為：首先分析兩種類型模式支持集的數據處理過程，接著研究投影模式的基本策略和實現算法，最后采用對比實驗來驗證投影模式數據挖掘算法的可行性。研究結果表明：該算法在支持率閾值低于0.1%時，系統處理性能高出其他類型的數據挖掘算法2倍以上，為高效的數據挖掘奠定了理論基礎。

投影模式 基本策略 算法分析 數據挖掘

0 引 言

數據挖掘過程中經常采用頻繁模式挖掘算法，該算法可以解決數據挖掘的常見問題，因而獲得較廣泛應用[1-5]。隨著應用的逐漸深入以及海量數據庫的出現，頻繁模式挖掘算法也暴露出一些弊端，如處理長模式的密集型數據庫時，挖掘效率較低；處理大型稀疏型數據庫時，誤差較大；對于密集型數據庫的投影與計數操作效率低于基于樹型的方法。本文將提出一種基于投影模式支持集的數據挖掘算法，以期解決頻繁模式挖掘算法中存在的主要問題。

1 模式支持集的類型與處理過程

模式支持集(簡稱:PSS)主要用于表示投影事務子集，PSS的投影規則直接影響算法的時間開銷。下面通過分析兩種類型的PSS，即稀疏型PSS和密集型PSS，研究事務數據的處理過程。

1.1 稀疏型PSS

稀疏型PSS是以數組為基礎，通常由局部模式列表(LPL)、塊隊列(BQ)和數組(Array)組成。其中局部模式列表(LPL)包含三個域，分別為塊指針、項目、計數器，塊指針將事務與塊隊列BQ相連，項目根據指定順序排列，每個事務存放于對應的數組之中，這種基于事務集的稀疏型PSS拓撲結構如圖1所示。

圖1 事務子集的稀疏型PSS

從圖1可知，項目a通過塊隊列BQ(a)連接事務01、03和05，事務01的模式列表為{a,c,f,m,p}，數組中只保留后四項，即{c,f,m,p}。稀疏型PSS的投影過程為：首先，選取LPL中的第一個條目為當前條目，如項目a通過塊隊列BQ(a)將第一個子節點(a.3)的事務聯系起來。然后，通過當前BQ中的事務向下一個BQ轉移，如事務01向事務03轉移，以此類推，一個事務通過項目子節點與下一個項目產生關聯，直到轉移到合適的BQ為止。

1.2 密集型PSS

密集型PSS以樹結構為基礎，它是一種不同于遞歸構造條件的方法[6-7]。

基于樹結構的密集型PSS包含兩部分內容，分別為項目列表(PL)和事務數組(BA)。密集型PSS為每個PL條目設置三個參數，分別為項目、計數器和塊指針，分別記作item、count和pointer,各條目按照指定的項目次序排列，并利用唯一的路徑表示每個事務。每個BA節點采用(i,n)表示，i表示項目，n表示從根節點到該節點路徑所訪問事務的數目。PL條目應與路徑上項目的排列順序相一致，通過PL條目可以將相同項目的所有節點鏈接起來，以便于查詢，密集型PPS的拓撲結構如圖2所示。

圖2 樹結構的密集型PSS結構圖

從圖2可知，密集型PSS通過樹結構路徑來表示事務，如路徑(a,2)-(c,2)-(f,2)-(m,1)-(p,1)表示事務01和05，事務2則通過路徑(a,2)-(b,2)-(c,3)-(f,1)-(m,2)來表示，項目列表PL的第四個條目的項目為f,通過塊指針(虛線箭頭)將節點(f,2)、(f,1)和(f,3)聯系在一起。

2 投影模式策略及其算法

為了獲得最優的時間效率和空間利用率，數據挖掘算法必須使模式生成樹的生成和搜索策略、PSS表示方法和投影方法等適應于數據特性，下面分析投影模式的策略及其相關算法。

2.1 投影模式的基本策略

由于在實際應用中數據庫規模存在差異，事務數據不能簡單地劃分為稀疏型或密集型，因此，投影模式的基本策略需兼顧時間效率和空間利用率兩方面。

策略1 對于超大型數據庫，模式生成樹的上半部可以采用寬度優先算法來構建，當所有各層節點都能利用內存表示時，選用深度優先算法構建模式生成樹的下半部。

策略2 在模式生成樹的高層，采用稀疏型PSS,在模式生成樹的中下層，則可采用密集型PSS。

策略3 當使用稀疏型投影模式時，父節點需要有足夠的自由內存與子節點建立對應關系；當采用基于樹結構密集型投影模式時，首先需界定虛擬子節點的樹型結構，如果密集型PSS收縮較快，則需建立過濾型的拷貝。

2.2 投影模式算法

以投影模式的基本策略為基礎，本文提出一種融合深度優先與寬度優先的投影模式算法(PMA)，該PMA算法基于數組與樹狀結構，由寬度優先過程和具有向導的深度優先過程組成[8]。

2.2.1 寬度優先投影算法

寬度優先投影算法是以內存作為參數，控制整個遞歸過程，通過3個步驟創建模式生成樹的上半部。

步驟1 為當前層k的每個節點v設計一個向量計數器，用于累計每個節點在PSS中項目的支持數，每個按規定次序排列的子節點，其標注項目在向量計數器中都有唯一的對應向量。

步驟2 將事務t沿根節點路徑向第k層節點投影，每投影一次，就將向量計數并累加。如果事務t能夠投影至第k層節點并使該節點的向量增值，則t還可以向k+1層節點投影，并將t增加至D，否則，事務數將逐層減少。

步驟3 為每個節點v創建其子節點。當v的值超過支持率閾值的計數分量，則相應地有一個v的子節點，反之，則v沒有子節點，可以被刪除，如果v是其父節點的唯一子節點，則v的父節點也可被刪除。

2.2.2 向導式深度優先算法

假設節點在第k層結束，那么，只有長度為k的路徑保存在模式生成樹中，模式生成樹的第k層以下將按照向導式深度優先算法來構造,實現步驟如下：

步驟1 首先掃描數據庫，確定支持節點P及其事務集Dp，并獲得Dp的LPL。如果數據庫信息以磁盤或稀疏型PSS形式表示，則創建相應的LPL；如果數據庫以樹狀密集型PSS形式表示，則LPL已經保存在父親列表中。

步驟2 如果數據庫以稀疏型PSS形式表示，并且事務集Dp的密度估計值超過設定閾值，則為Dp創建樹狀密集型PSS表達形式，否則為Dp創建稀疏型PSS表達形式。如果數據庫以密集型PSS形式表示，則為Dp創建虛擬的密集型PSS，如果Dp規模遠小于事務數據庫，則需要為Dp建立過渡型拷貝。

步驟3 為每個事務節點創建與其項目相同的子節點，如果節點所在層次大于設定值，則在此時創建子節點；反之，節點由項目初期創建，如果遍歷整個事務數據庫檢索不到子節點，則表明子節點在模式生成樹的分枝最大長度小于設定值，可以不必創建。

向導式深度優先策略在執行效率方面優于無向導的深度優先策略，因為前者可避免重復創建終止于模式生成樹上半部分的路徑。

2.2.3 PMA算法

PMA算法是融合了寬度優先與深度優先的投影模式算法，該算法結合了寬度優先算法和深度優先算法的優點，是一種比前兩種算法計算復雜度更低的算法，因而更有利于實際應用。PMA算法的實現步驟如下：

步驟1 利用搜索樹的圖論特點，任意一個節點只通過其父節點與其他非子節點發生聯系，將父節點與其他節點分隔開，其后代節點便形成獨立的區域。

步驟2 將搜索樹分成左右相等的兩部分，左半部分執行深度優先算法，右半部分執行寬度優先算法，兩部分算法可同時進行。

步驟3 為了降低計算復雜度，首先執行深度優先算法，接著執行寬度優先算法，深度優先算法獲得的結果可用于寬度優先算法之中。

3 對比實驗及性能評價

為了驗證投影模式算法的有效性，本文采用對比實驗，將投影模式算法與Apriori[9]、FP-Growth[10]和H-Mine[6]算法的效率和有效性進行對比分析，實驗數據采用大數據集，實驗環境為：2 GHz的Pentium IV CPU、1 GB內存和100 GB硬盤，操作系統采用Microsoft Windows 2008 Server。

3.1 實驗數據集

實驗數據集采用電器零售商近5年的商業銷售數據，這些數據被劃分成多個稀疏型數據集，分別為：etailer-POS、etailer-Web-1和etailer-Web-2。其中etailer-POS為POS機的銷售數據, etailer-Web-1和etailer-Web-2為兩個電子商務網站的點擊數據。當支持率閾值設定為0.1%時，etailer-Web-1的頻繁模式為3 985，etailer-Web-2的頻繁模式達到24 056; 當支持率閾值設定為0.03%時, etailer-Web-1的頻繁模式數為1 188 067, etailer-Web-2的頻繁模式數為1 352 615。

實驗數據集還采用了密集型數據集Connect, 該數據集來自機器學習數據集，當支持率閾值從80%降低到55%時，頻繁模式數則大幅增長，從29 137增加到84 315 246。另外，為了提高實驗的對比性，實驗數據集采用了IBM A.I.人工智能數據集，該數據集介于稀疏型數據集和密集型數據集之間。實驗數據集的基本特性如表1所示。

表1 數據集的基本特性

3.2 實驗結果

采用四種數據挖掘算法并利用etailer-POS數據集進行對比實驗，為了比較不同算法的分析結果，本文采用的性能指標是各算法在不同的支持率閾值運行時間。對比實驗的結果如圖3所示。圖中縱坐標表示時間，橫坐標表示支持率閾值，采用對數坐標和百分比。

圖3 四種數據挖掘算法對比實驗結果

從圖3可知，當支持率閾值超過0.4%時，四種算法的性能比較接近；支持率閾值在0.1%和0.2%之間時，FPGrowth算法性能與PMA相似；當支持率閾值低于0.1%時，各算法之間的差異較為顯著，處理相同的數據量，FPGrowth需要75秒，H-Mine需要282秒，Apriori需要768秒，而PMA只需要32秒，由此可知，本文提出的PMA算法相對于其他算法在合理的低支持率閾值范圍內，具有較高的處理性能。

另外，對于數據集etailer-Web-1、etailer-Web-2、Connect和IBM A.I.的算法性能進行對比分析，所得結果與etailer-POS數據集相類似，這里不再贅述。

4 結 語

本文在頻繁模式挖掘算法的基礎上，提出了一種基于投影模式支持集的數據挖掘算法，并得到以下結論。

1) 本文提出的數據挖掘算法，對于稀疏型和密集型數據庫都能節省算法的時間開銷，并能提高傳統頻繁模式算法的挖掘效率。

2) 由于算法集成了深度優先與寬度優先策略，能夠為模式支持集提供基于數組和數狀結構的表示形式，并能啟發式地應用基于樹的虛擬投影和基于數組的過濾型投影等方法，從而達到時間效率的最大化。

[1] Wang Z C, Xue L X. A fast algorithm for mining association rules in image[C]//IEEE International Conference on Software Engineering and Service Science. IEEE, 2014:513-516.

[2] Wang L, Xiwei K E. A Self-Adapted Algorithm for Mining Association Rules Based on Hash Pruning[J].Microcomputer Applications, 2009.

[3] Han J, Fu Y. Discovery of Multiple-Level Association Rules from Large Databases[J].Proc of Vldb, 2010:420-431.

[4] Srivastava S, Gupta D, Verma H K. Comparative Investigations and Performance Evaluation for Multiple-Level Association Rules Mining Algorithm[J].International Journal of Computer Applications,2010,4(10):40-45.

[5] Thakur R S, Jain R C, Pardasani K R. Mining level-crossing association rules from large databases[J].Journal of Computer Science, 2006,2(1):76-81.

[6] Sangam R S, Om H. Hybrid data labeling algorithm for clustering large mixed type data[J].Journal of Intelligent Information Systems, 2015, 45(2):273-293.

[7] Schafer J B, Frankowski D, Herlocker J, et al. Collaborative filtering recommender systems[C]//The adaptive web. Springer-Verlag, 2007:291-324.

[8] Lucchese C, Orlando S, Perego R, et al. Mining Frequent Closed Itemsets from Distributed Repositories[M]//Knowledge and Data Management in GRIDs,2007:221-234.

[9] Han Feng, Zhang Shumao, Du Yingshuang. The analysis and improvement of Apriori algorithm[J].Journal of Communication and Computer,2008,41(9):12-18.

[10] Hewanadungodage C, Xia Y, Lee J J, et al. Hyper-structure mining of frequent patterns in uncertain data streams[J].Knowledge and Information Systems, 2013,37(1):219-244.

RESEARCH ON DATA MINING ALGORITHM BASED ON PROJECTION SCHEME SUPPORT SET

Yang Xiaobo

(CollegeofDongFang,ZhejiangUniversityofFinanceandEconomics,Hangzhou314408,Zhejiang,China)

In order to improve the efficiency of frequent pattern mining algorithms, a data mining algorithm based on projection pattern support set is proposed. The specific research process is as follows. Firstly, it analyzed the data processing of two types projection pattern support set, then it studied the basic strategy and the realize algorithm of projection mode. Finally, the contrast experiment is applied to verify the feasibility of projection pattern data mining algorithm. The algorithm proposed in this paper is more than 2 times higher than other types of data mining algorithms when the threshold of the support rate is lower than 0.1%, which lays a theoretical foundation for the efficient data mining.

Projection scheme Basic strategy Algorithm analysis Data mining

2016-08-12。浙江財經大學東方學院學科專項課題(2013dfy001)。楊曉波，副教授，主研領域：數據挖掘和業務協同等。

TP311.13

A

10.3969/j.issn.1000-386x.2017.07.050