一種用于FTTx網(wǎng)絡規(guī)劃的頻繁序列挖掘算法FSM+

宋楚平

(南通紡織職業(yè)技術學院，江蘇南通 226007)

0 引言

近年來，隨著光纖接入(fiber to the x，F(xiàn)TTx)網(wǎng)絡技術日趨成熟，以及用戶對寬帶的更高需求，基于無源光網(wǎng)絡(passive optical network，PON)技術的FTTx接入模式和解決方案在國內外得到越來越廣泛的應用［1］。在 FTTx網(wǎng)絡規(guī)劃過程中，如何在現(xiàn)有光線路終端 (optical line terminal，OLT)、光纖分布網(wǎng) (optical distribution network，ODN)和光網(wǎng)絡單元 (optical network unit，ONU)數(shù)據(jù)的基礎上，結合城市發(fā)展規(guī)劃和用戶對寬帶業(yè)務需求的發(fā)展趨勢，提前發(fā)現(xiàn)FTTx網(wǎng)絡中OLT，ODN，ONU建設規(guī)模隨城市發(fā)展和用戶需求的關聯(lián)關系，挖掘其中規(guī)律，識別最佳的未來網(wǎng)絡規(guī)劃路徑，成為促進FTTx網(wǎng)絡應用的研究熱點和挑戰(zhàn)。本文提出的頻繁序列挖掘算法(命名為FSM+)采用頻繁項集擴展序列枚舉樹，根據(jù)頻繁序列特征和頻繁序列擴展性質，從電信網(wǎng)路規(guī)劃海量數(shù)據(jù)中挖掘基于最小支持度的頻繁路徑，完成對FTTx網(wǎng)絡工程數(shù)據(jù)進行分析和處理，發(fā)現(xiàn)網(wǎng)絡規(guī)劃中重要的建設路徑，使網(wǎng)絡規(guī)劃更加有序和科學，提高FTTx網(wǎng)絡規(guī)劃的效率。

1 相關性質和理論

近年來隨著序列模式挖掘算法的改進和優(yōu)化，序列模式挖掘在網(wǎng)絡規(guī)劃方面也得到了應用。但現(xiàn)有算法有很多不足之處，如傳統(tǒng)FP－Growth算法生成大量的頻繁候選項集，并且支持度計算比較繁瑣［3］。SPADE算法利用基于格的搜索技術和簡單交運算降低了數(shù)據(jù)庫的掃描次數(shù)，算法效率有了明顯的改善，但仍有大量非頻繁項集參與序列的擴展計算，算法的性能和可伸縮性有待改善［4］。也有一些改進算法采用多次對數(shù)據(jù)庫掃描，在候選項集的產生與選擇上花費大量的時空代價［5－6］，影響了挖掘的效率。因此，如何利用格的方法通過減少對數(shù)據(jù)庫掃描次數(shù)以及控制候選項集的產生就成為研究的重點。

2 頻繁序列改進算法FSM+

2.1 算法基本思想

FTTx網(wǎng)絡規(guī)劃頻繁序列挖掘工作主要分為3個步驟:①構建網(wǎng)絡規(guī)劃路徑樹;②計算并標記樹中各點未來時間的預計總流量和用戶選用該點的概率;③基于最小支持度閥值來挖掘頻繁序列路徑［7］。在數(shù)據(jù)挖掘前，要經(jīng)歷以下3 個階段［8］。

1 )數(shù)據(jù)抽取與預處理:挖掘數(shù)據(jù)的結構和內容不一致，需進行預處理轉換成規(guī)范、統(tǒng)一的數(shù)據(jù)結構，以增強數(shù)據(jù)分析的通用性。如原來施工時用來表示網(wǎng)絡實體拓撲關系的格式為(OLT_Id，Sm Id，time，Persion Id)，(OBD_Id，Sm Id，time，PersionId)，(ONU_Id，Sm Id，time，Persion Id)，現(xiàn)統(tǒng)一將其轉化為(OLT_Id，OBD_Id，ONU_Id，time)。

2 )數(shù)據(jù)清理與壓縮:利用同一用戶在不同時間網(wǎng)絡開通數(shù)據(jù)的掃描，以及新的建筑群成批網(wǎng)絡注冊的掃描，可以對數(shù)據(jù)進行清理和壓縮，以盡可能降低數(shù)據(jù)冗余，加快對數(shù)據(jù)的處理。

3 )路徑確定:將同一 OLT_Id，OBD_Id，ONU_Id依據(jù)時間進行排序，就可得到網(wǎng)絡部署路徑，所有的路徑構成了挖掘數(shù)據(jù)的項目集。

頻繁模式是指在時間序列中出現(xiàn)次數(shù)大于最小支持度的子序列［9］。分析網(wǎng)絡信號從OLT，ODN到ONU所經(jīng)過的所有流動過程稱為路徑選擇。同一用戶的網(wǎng)絡接入可以有不同的路徑選擇。因此，路徑選擇有經(jīng)濟可比性和施工難易可比性。根據(jù)上述頻繁序列特征和頻繁序列擴展性質，從電信網(wǎng)絡規(guī)劃海量數(shù)據(jù)中挖掘基于最小支持度的頻繁路徑。

本算法共有2步。第1步挖掘頻繁size(1)－序列，第2步挖掘size(k)－序列。第1步顯然可以利用當前有效的頻繁項集挖掘方法，如 FP－Growth，F(xiàn)PTree 等進行處理［3，10］。對于 size(k)－序列的挖掘，則采用第1個子任務得到的頻繁項集，結合頻繁項集序列擴展運算枚舉出所有頻繁size(k)－序列。整個過程如下。

1 )掃描數(shù)據(jù)庫1次，找出所有頻繁項集合F1;

2 )遍歷序列節(jié)點，進行支持度檢查，找出所有的繁項集合FI，亦找到size(1)－頻繁序列集合FS;

3 )采用深度優(yōu)先對頻繁size(1)－序列α逐個進行序列擴展，得到候選序列Cs;

4 )對Cs進行支持度檢查，若Cs是頻繁序列，則放入頻繁序列集合FS中;

5 )重復步驟3)，4)，最后輸出FS。

2.2 算法描述

輸入:序列數(shù)據(jù)庫D，最小支持度閥值min_sup。

注意，算法FSM+沒有進行非頻繁項集的擴展，明顯減少了無效候選序列的數(shù)量。但在枚舉過程中，仍產生了一定量的無效序列擴展候選。

3 實驗結果與分析

FTTx網(wǎng)絡決策與支撐系統(tǒng)數(shù)據(jù)項多、數(shù)據(jù)量大，OLT編碼、OBD編碼、IAD編碼、ONU編碼、BAN箱編碼、用戶網(wǎng)絡安裝信息等采用人工輸入，各設備的空間物理位置(posX，posY)采用北京超圖Super－Map采集。對網(wǎng)絡拓展數(shù)據(jù)的頻繁模式挖掘，可以得出未來某一區(qū)域滿足最小支持度的頻繁路徑［11］。以此進行業(yè)務用戶數(shù)量預測和業(yè)務量預測，作為最佳網(wǎng)路規(guī)劃路徑的基礎，以便合理安排施工計劃，降低施工成本，以及為未來用戶預留合適的網(wǎng)絡容量，支持城市快速信息化發(fā)展。為驗證FSM+算法的性能，我們用VC++6.0在內存1 GByte，CPU為Pentium(R)Dual2.4 GHz、操作系統(tǒng)為Windows XP的環(huán)境下進行了 FSM+算法與經(jīng)典算法 SPADE，F(xiàn)PGrowth的性能比較測試。利用某電信公司2009至2012年48個月采集的FTTx網(wǎng)絡用戶裝機數(shù)據(jù)來進行實驗。序列的持續(xù)時間定為60 min，時間間隔為60～120 min。從48個月的數(shù)據(jù)中抽取2個數(shù)據(jù)集 DS1，DS2，如表 1 所示。

表1 實驗數(shù)據(jù)Tab.1 Experimental data

保持2種規(guī)格的數(shù)據(jù)集不變，改變最小支持度min_sup，對比算法 FSM+與 SPADE，F(xiàn)P－Growth 的執(zhí)行時間，結果如圖1、圖2所示。

由圖1可以看出，本文提出的FSM+算法在數(shù)據(jù)集較小時，時間性能與SPADE，F(xiàn)P－Growth相比沒有明顯的效率優(yōu)勢。但在數(shù)據(jù)集較大時，如圖2所示FSM+的時間性能明顯提升，為SPADE的5倍多，是FP－Growth的7倍多。其主要原因在于:①FSM+算法產生的候選序列是由頻繁項集序列擴展得來的，序列中沒有非頻繁項集，候選序列數(shù)量得到明顯縮減。②FSM+采用了位圖輸入序列壓縮存儲技術［12］，對擴展預算和支持度計算提供了有效的支持，提高了算法的效率。在支持度較小時，F(xiàn)SM+的性能優(yōu)勢更為明顯，此時有更多頻繁模式輸出。而在支持度 min_sup較大時，F(xiàn)SM+與 SPADE，F(xiàn)PGrowth算法的執(zhí)行效率沒有明顯的差距，主要原因在于:FSM+算法在計算過程中保留了所有頻繁項集的位圖，占據(jù)了大量的內存空間，這在一定程度上影響了FSM+算法的效率。而SPAM僅存儲了頻繁項的位圖，所需內存空間較少。FP－Growth采用頻繁模式樹保留項集相關信息，當數(shù)據(jù)量較大時，算法的I/O代價較大，造成算法效率較低。

圖1 在數(shù)據(jù)集DS1上的時間性能比較Fig.1 Time performance comparison in DS1

圖2 在數(shù)據(jù)集DS2上的時間性能比較Fig.2 Time performance comparison in DS2

在準確性測試方面，采用歷史數(shù)據(jù)，設定相同最少支持度，分別執(zhí)行算法 SPADE，F(xiàn)P－Growth和FSM+，其挖掘出的頻繁序列均是相同的，驗證了FSM+挖掘結果是準確的，該算法是可行的。另外由于FSM+算法具有較高的運行效率，因此在實際應用過程中，可以在較大的最小支持度一定區(qū)間范圍內，多次計算信任度較高的頻繁模式，并與人工經(jīng)驗干預相結合，進一步來保證預測數(shù)據(jù)準確有效。

4 結語

本文提出的挖掘算法FSM+在某電信公司的FTTx網(wǎng)絡決策與支撐系統(tǒng)中得到了實施與應用。FSM+算法是基于對FTTx網(wǎng)絡規(guī)劃行為分析，得到某區(qū)域一定時間內FTTx網(wǎng)絡用戶安裝的規(guī)律;也就是說，在一定時間序列內找到了一種具有一定可信度的企業(yè)共性的網(wǎng)絡規(guī)劃模式。它可以幫助電信等企業(yè)分析網(wǎng)絡施工的特點，乃至未來網(wǎng)絡規(guī)劃和管理等問題。實驗和實踐證明，和已有的經(jīng)典算法SPADE，SPAM等相比，F(xiàn)SM+算法更能有效發(fā)現(xiàn)頻繁模式，能較為準確預測FTTx網(wǎng)絡規(guī)劃的下一節(jié)行為。

為了更全面、更高效地挖掘與利用FTTx網(wǎng)絡施工數(shù)據(jù)，下一步的研究將集中在算法的剪枝策略上，來有效減少候選序列產生的數(shù)量，盡可能縮減非頻繁序列的枚舉，進一步提高算法效率。同時，對序列數(shù)據(jù)的時間約束進行合理的評估，使FTTx網(wǎng)絡施工數(shù)據(jù)得到更充分的利用。

［1］張海飛，曲豫賓，劉全.GIS技術在FTTx網(wǎng)絡接入規(guī)劃中的應用［J］.武漢科技大學學報:自然科學版，2011，34(5):395－397.

ZHANG Haifei，QU Yubin，LIU Quan.Application of GIS technology to FTTx network access planning［J］.Journal ofWuhan University of Science and Technology:Natural Science Edition，2011，34(5):395－397.

［2］AGRAWAL R，SRIKANT R.Mining Sequential Patterns［C］//In Proceedings of the Eleventh International Conference on Data Engineering(ICDE 1995).Taipei:IEEE Computer Society Press，1995:3－14.

［3］楊云，羅艷霞.FP－Growth算法的改進［J］.計算機工程與設計，2010，31(57):156－158.

YANG Yun，LUO Yanxia.Improved algorithm based on FP－Growth ［J］.Computer Engineering and Desig，2010，31(57):156－158.

［4］郭平，劉潭仁.基于圖結構的候選序列生成算法［J］.計算機科學，2004，31(1):136－139.

GUO Ping，LIU Tanren.Graph－Based Candidate Frequent Patterns Generating Algorithm ［J］.Computer Science，2004，31(1):136－139.

［5］MASSEGLIA F，PONCELET P，TEISSEURE M.Incrementalmining of sequential patterns in large database［J］.Data and Knowledge Engineering，2003，46(1):97－121.

［6］LIN M Y，LEE SY.Incremental update on sequential pat－terns in large databases［C］//Proceedings of 10th IEEE International Conference on Tools with Artificial Intelligence.Taipei:IEEE，2001:24－31.

［7］RAJANISH Dass.An efficient algorithm for frequent patternmining for real－time business intelligence analytices in dense datasets［C］//Proceedings of the 39 Annual Hawaii International Conference on System Sciences，HICSS’06.Kauai，HI，United States:Institute of Electrical and Electronics Engineers Computer Society，2006:145－147.

［8］田景紅，潘曉弘，王正肖.基于頻繁模式挖掘的實時供應鏈數(shù)據(jù)分析［J］.浙江大學學報:工學版，2009，43(12):261－265.

TIAN Jinghong，PAN Xiaohong，WANG Zhengxiao.Data analysis in real－time supply chain based on frequent patternmining［J］.Journal of Zhejiang University:Engineering Science，2009，43(12):261－265.

［9］萬里，廖建新，朱曉民.一種時間序列頻繁模式挖掘算法在WSAN行為預測中的應用［J］.電子與信息學報，2010，32(3):682－686.

WAN Li，LIAO Jianxin，ZHU Xiaomin.Time Series Frequent Pattern Mining Algorithm and its Application to WSAN Behavior Prediction ［J］.Journal of Electronics＆Information Technology，2010，32(3):682－686.

［10］陳晨，鞠時光.基于改進FP－tree的最大頻繁項集挖掘算法［J］.計算機工程與設計，2008，29(24):6237－6239.

CHEN Chen，JU Shiguang.Algorithm for mining maximal frequent itemset based on improved FP－tree［J］.Computer Engineering and Design，2008，29(24):6237－6239.

［11］楊勝琦.基于復雜網(wǎng)絡的大規(guī)模電信數(shù)據(jù)分析研究［D］.北京:北京郵電大學，2010:52－56.

YANG Shengqi.The analysis and research of large－scale telecom data based on complex network［D］.Beijing:Beijing University of Posts and Telecommunications，2010:52－56.

［12］DURDICK D，CALIMLIM M，GEHRKE J.A maximal frequent itemsetalgorithm for transactional database［C］//In Proceedings of 17th international conference on Data Engineering.Taipei:IEEE Computer Society Press，2001:450－452.

(編輯:田海江)