楊 曉 波

(浙江財(cái)經(jīng)大學(xué)東方學(xué)院 浙江 杭州 314408)

?

基于投影模式支持集的數(shù)據(jù)挖掘算法研究

楊 曉 波

(浙江財(cái)經(jīng)大學(xué)東方學(xué)院 浙江 杭州 314408)

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

投影模式 基本策略 算法分析 數(shù)據(jù)挖掘

0 引 言

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

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

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

1.1 稀疏型PSS

稀疏型PSS是以數(shù)組為基礎(chǔ)，通常由局部模式列表(LPL)、塊隊(duì)列(BQ)和數(shù)組(Array)組成。其中局部模式列表(LPL)包含三個(gè)域，分別為塊指針、項(xiàng)目、計(jì)數(shù)器，塊指針將事務(wù)與塊隊(duì)列BQ相連，項(xiàng)目根據(jù)指定順序排列，每個(gè)事務(wù)存放于對(duì)應(yīng)的數(shù)組之中，這種基于事務(wù)集的稀疏型PSS拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 事務(wù)子集的稀疏型PSS

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

1.2 密集型PSS

密集型PSS以樹結(jié)構(gòu)為基礎(chǔ)，它是一種不同于遞歸構(gòu)造條件的方法[6-7]。

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

圖2 樹結(jié)構(gòu)的密集型PSS結(jié)構(gòu)圖

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

2 投影模式策略及其算法

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

2.1 投影模式的基本策略

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

策略1 對(duì)于超大型數(shù)據(jù)庫，模式生成樹的上半部可以采用寬度優(yōu)先算法來構(gòu)建，當(dāng)所有各層節(jié)點(diǎn)都能利用內(nèi)存表示時(shí)，選用深度優(yōu)先算法構(gòu)建模式生成樹的下半部。

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

策略3 當(dāng)使用稀疏型投影模式時(shí)，父節(jié)點(diǎn)需要有足夠的自由內(nèi)存與子節(jié)點(diǎn)建立對(duì)應(yīng)關(guān)系；當(dāng)采用基于樹結(jié)構(gòu)密集型投影模式時(shí)，首先需界定虛擬子節(jié)點(diǎn)的樹型結(jié)構(gòu)，如果密集型PSS收縮較快，則需建立過濾型的拷貝。

2.2 投影模式算法

以投影模式的基本策略為基礎(chǔ)，本文提出一種融合深度優(yōu)先與寬度優(yōu)先的投影模式算法(PMA)，該P(yáng)MA算法基于數(shù)組與樹狀結(jié)構(gòu)，由寬度優(yōu)先過程和具有向?qū)У纳疃葍?yōu)先過程組成[8]。

2.2.1 寬度優(yōu)先投影算法

寬度優(yōu)先投影算法是以內(nèi)存作為參數(shù)，控制整個(gè)遞歸過程，通過3個(gè)步驟創(chuàng)建模式生成樹的上半部。

步驟1 為當(dāng)前層k的每個(gè)節(jié)點(diǎn)v設(shè)計(jì)一個(gè)向量計(jì)數(shù)器，用于累計(jì)每個(gè)節(jié)點(diǎn)在PSS中項(xiàng)目的支持?jǐn)?shù)，每個(gè)按規(guī)定次序排列的子節(jié)點(diǎn)，其標(biāo)注項(xiàng)目在向量計(jì)數(shù)器中都有唯一的對(duì)應(yīng)向量。

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

步驟3 為每個(gè)節(jié)點(diǎn)v創(chuàng)建其子節(jié)點(diǎn)。當(dāng)v的值超過支持率閾值的計(jì)數(shù)分量，則相應(yīng)地有一個(gè)v的子節(jié)點(diǎn)，反之，則v沒有子節(jié)點(diǎn)，可以被刪除，如果v是其父節(jié)點(diǎn)的唯一子節(jié)點(diǎn)，則v的父節(jié)點(diǎn)也可被刪除。

2.2.2 向?qū)缴疃葍?yōu)先算法

假設(shè)節(jié)點(diǎn)在第k層結(jié)束，那么，只有長(zhǎng)度為k的路徑保存在模式生成樹中，模式生成樹的第k層以下將按照向?qū)缴疃葍?yōu)先算法來構(gòu)造,實(shí)現(xiàn)步驟如下：

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

步驟2 如果數(shù)據(jù)庫以稀疏型PSS形式表示，并且事務(wù)集Dp的密度估計(jì)值超過設(shè)定閾值，則為Dp創(chuàng)建樹狀密集型PSS表達(dá)形式，否則為Dp創(chuàng)建稀疏型PSS表達(dá)形式。如果數(shù)據(jù)庫以密集型PSS形式表示，則為Dp創(chuàng)建虛擬的密集型PSS，如果Dp規(guī)模遠(yuǎn)小于事務(wù)數(shù)據(jù)庫，則需要為Dp建立過渡型拷貝。

步驟3 為每個(gè)事務(wù)節(jié)點(diǎn)創(chuàng)建與其項(xiàng)目相同的子節(jié)點(diǎn)，如果節(jié)點(diǎn)所在層次大于設(shè)定值，則在此時(shí)創(chuàng)建子節(jié)點(diǎn)；反之，節(jié)點(diǎn)由項(xiàng)目初期創(chuàng)建，如果遍歷整個(gè)事務(wù)數(shù)據(jù)庫檢索不到子節(jié)點(diǎn)，則表明子節(jié)點(diǎn)在模式生成樹的分枝最大長(zhǎng)度小于設(shè)定值，可以不必創(chuàng)建。

向?qū)缴疃葍?yōu)先策略在執(zhí)行效率方面優(yōu)于無向?qū)У纳疃葍?yōu)先策略，因?yàn)榍罢呖杀苊庵貜?fù)創(chuàng)建終止于模式生成樹上半部分的路徑。

2.2.3 PMA算法

PMA算法是融合了寬度優(yōu)先與深度優(yōu)先的投影模式算法，該算法結(jié)合了寬度優(yōu)先算法和深度優(yōu)先算法的優(yōu)點(diǎn)，是一種比前兩種算法計(jì)算復(fù)雜度更低的算法，因而更有利于實(shí)際應(yīng)用。PMA算法的實(shí)現(xiàn)步驟如下：

步驟1 利用搜索樹的圖論特點(diǎn)，任意一個(gè)節(jié)點(diǎn)只通過其父節(jié)點(diǎn)與其他非子節(jié)點(diǎn)發(fā)生聯(lián)系，將父節(jié)點(diǎn)與其他節(jié)點(diǎn)分隔開，其后代節(jié)點(diǎn)便形成獨(dú)立的區(qū)域。

步驟2 將搜索樹分成左右相等的兩部分，左半部分執(zhí)行深度優(yōu)先算法，右半部分執(zhí)行寬度優(yōu)先算法，兩部分算法可同時(shí)進(jìn)行。

步驟3 為了降低計(jì)算復(fù)雜度，首先執(zhí)行深度優(yōu)先算法，接著執(zhí)行寬度優(yōu)先算法，深度優(yōu)先算法獲得的結(jié)果可用于寬度優(yōu)先算法之中。

3 對(duì)比實(shí)驗(yàn)及性能評(píng)價(jià)

為了驗(yàn)證投影模式算法的有效性，本文采用對(duì)比實(shí)驗(yàn)，將投影模式算法與Apriori[9]、FP-Growth[10]和H-Mine[6]算法的效率和有效性進(jìn)行對(duì)比分析，實(shí)驗(yàn)數(shù)據(jù)采用大數(shù)據(jù)集，實(shí)驗(yàn)環(huán)境為：2 GHz的Pentium IV CPU、1 GB內(nèi)存和100 GB硬盤，操作系統(tǒng)采用Microsoft Windows 2008 Server。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

表1 數(shù)據(jù)集的基本特性

3.2 實(shí)驗(yàn)結(jié)果

采用四種數(shù)據(jù)挖掘算法并利用etailer-POS數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)，為了比較不同算法的分析結(jié)果，本文采用的性能指標(biāo)是各算法在不同的支持率閾值運(yùn)行時(shí)間。對(duì)比實(shí)驗(yàn)的結(jié)果如圖3所示。圖中縱坐標(biāo)表示時(shí)間，橫坐標(biāo)表示支持率閾值，采用對(duì)數(shù)坐標(biāo)和百分比。

圖3 四種數(shù)據(jù)挖掘算法對(duì)比實(shí)驗(yàn)結(jié)果

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

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

4 結(jié) 語

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

1) 本文提出的數(shù)據(jù)挖掘算法，對(duì)于稀疏型和密集型數(shù)據(jù)庫都能節(jié)省算法的時(shí)間開銷，并能提高傳統(tǒng)頻繁模式算法的挖掘效率。

2) 由于算法集成了深度優(yōu)先與寬度優(yōu)先策略，能夠?yàn)槟Ｊ街С旨峁┗跀?shù)組和數(shù)狀結(jié)構(gòu)的表示形式，并能啟發(fā)式地應(yīng)用基于樹的虛擬投影和基于數(shù)組的過濾型投影等方法，從而達(dá)到時(shí)間效率的最大化。

[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。浙江財(cái)經(jīng)大學(xué)東方學(xué)院學(xué)科專項(xiàng)課題(2013dfy001)。楊曉波，副教授，主研領(lǐng)域：數(shù)據(jù)挖掘和業(yè)務(wù)協(xié)同等。

TP311.13

A

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