基于改進ＰｒｅｆｉｘＳｐａｎ算法的移動Ｗｅｂ序列模式挖掘
2007-12-31 00:00:00王素鳳鄧玫
商場現代化 2007年23期
[摘要] 隨著移動商務的迅速發展，移動用戶面臨的帶寬限制和信息貧乏問題也日益凸顯。Web使用挖掘通過對用戶訪問Web時在服務器留下的訪問記錄進行挖掘，在海量Web日志數據中自動、快速地發現用戶訪問序列模式。通過模式分析向移動用戶推薦其感興趣的內容。論文在比較幾種常用序列模式挖掘算法的基礎上，著重對PrefixSpan算法進行了研究和優化。
[關鍵詞] 移動商務 Web使用挖掘 PrefixSpan算法 序列模式
一、引言
隨著移動網絡的快速發展和電子商務的廣泛應用，移動網絡用戶對于商務信息的需求也大幅提升。據中國互聯網絡信息中心（CNNIC）2007年1月發布的《第19次中國互聯網絡發展狀況統計報告》顯示，截至2006年底，我國網民人數達到了1.37億，其中，新興上網方式——手機上網也初具規模，達到1700萬人。手機上網將成為互聯網接入方式的新潮流。但在對使用手機上網的網民進行調查發現，有72.2％和30.9％的網民使用手機上網主要是收發郵件和瀏覽信息，而費用高(占86.4%）、網速慢(占33.4%）是網民使用手機上網經常遇到的問題;此外，不方便、可獲取信息太少等也成為網民不使用手機上網的原因。一方面是以手機為代表的移動設備的迅速發展，而另一方面卻是移動商務網站上的信息貧乏和服務落后，解決方法之一就是進行Web使用挖掘，尋找移動商務客戶感興趣的內容并向其推薦。
Web使用挖掘是對用戶訪問Web時在服務器留下的訪問記錄進行挖掘，挖掘對象是在服務器上的日志信息，也稱為Web日志挖掘，其目的是在海量的Web日志數據中自動、快速地發現用戶的訪問模式（即序列模式）。在經過對這些模式進行分析和可視化之后，可以為用戶提供個性化的服務。序列模式挖掘是模式發現中運用得比較成功的方法，本文在比較幾種常用的序列模式挖掘算法的基礎上，對PrefixSpan算法進行了研究和優化。
二、序列模式挖掘算法
序列模式挖掘是從序列數據庫中發現頻繁子序列作為模式，被廣泛應用于客戶購買行為模式預測、網絡訪問模式預測、疾病治療早期診斷、自然災害預測及DNA序列破譯等方面。序列模式最早由Agrawal R和Srikant R提出，常用算法有：
·AprioriAll算法在每一次掃描數據庫時，利用上一次掃描時產生的大序列生成候選序列，并在掃描同時計算支持度，滿足支持度的候選序列作為下次掃描的大序列。算法主要缺陷在于容易生成龐大的候選序列集和需要多次掃描數據庫，不易發現長序列模式并導致較大開銷；
·GSP（Generalized Sequential Patterns）算法類似于Apriori算法，但引入了時間約束、滑動時間窗和分類層次技術，有效減少了候選序列數量和無用模式。然而GSP算法仍然需要對序列數據庫進行循環掃描；若序列數據庫規模比較大，可能產生大量候選序列模式；且難以處理長序列模式的情況；
·FreeSpan算法以Apriori-based演算法為基礎，但改進了產生候選序列的方式并驗證是否為高頻序列。該方法將搜尋區域由大范圍的完整資料庫改為小范圍的映射資料庫，產生的候選序列數量較少，也減少了掃描資料庫的時間，并提升了挖掘的效率。但該算法必須完整保留與該項目有關的序列，且在產生候選序列時并不考慮順序性，因此可能產生過多的候選序列。
本文將要論述的PrefixSpan算法與FreeSpan類似，但PrefixSpan不需要產生候選序列，從而大大縮減了檢索空間；相對于原始的序列數據庫而言，投影數據庫的規模不斷減小。PrefixSpan算法的缺點在于建立映射資料區間的成本很高，若資料項目平均分配在每個序列中，則成本便會急劇增加。下面對該算法進行介紹和優化。
三、PrefixSpan算法及其改進
1.符號化表示
序列（Sequence）:是不同項目集（ItemSet）的有序排列，一個序列S可以表示為，，為項目集（ItemSet），也稱為序列S的元素。
子序列:設如果存在整數使得則稱序列α為序列β的子序列，記為。
序列α在序列數據庫S中的支持數:序列數據庫S中包含序列 α的序列個數，記為Suuport(α)。
序列模式:給定支持度閾值ξ，如果序列α在序列數據庫中的支持數不低于ξ，則稱序列α為序列模式。長度為1的序列模式記為1-模式。
2.算法描述
給定序列數據庫和最小支持度閾值，序列模式挖掘就是要找出序列數據庫中所有的序列模式。具體算法如下：
·掃描序列數據庫，生成所有長度為1的序列模式；
·根據長度為1的序列模式，生成相應的投影數據庫；
·在相應的投影數據庫上重復上述步驟，直到在相應的投影數據庫上不能產生長度為1的序列模式為止。算法描述如圖1所示。
例如:序列數據庫S如表1所示，并設用戶指定的最小支持度min_support=2。
通過對表1給出的序列數據庫S進行掃描，產生長度為1的序列模式有::4，:4，
序列模式的全集是分別以，，
分別對不同的投影數據庫重復上述過程，直到沒有新的長度為1的序列模式產生為止。
3.PrefixSpan算法
輸入:序列數據庫 及最小支持度閾值min_sup
輸出:所有的序列模式
方法:調用子程序PrefixSpan(<>，0，S)
在子程序PrefixSpan(α，L，S｜α)中，參數α為一個序列模式， L為序列模式α的長度，當α為空則S｜α為S，否則為α的投影數據庫。子程序算法如下：
·掃描S｜α，找到滿足下述要求的長度為1的序列模式b:（1） b可以添加到α的最后一個元素中并為序列模式;（2）可以α的最后一個元素并為序列模式;
·對每個生成的序列模式b，將b添加到α形成序列模式α`，并輸出α`;
·對每個α`，構造α`的投影數據庫S｜α`，并調用子程序PrefixSpan(α，L+1，S｜α`)
四、PrefixSpan算法改進
由于PrefixSpan算法的主要開銷在于投影數據庫的構造，因此對PrefixSpan算法的改進主要是從減少投影數據庫入手。
1.隔層投影
使用隔層投影代替逐層投影，從而可以有效減小投影數據庫的個數。
仍以前面所述的序列數據庫為例，改用隔層投影，具體步驟如下：
（1)掃描序列數據庫，產生所有長度為1的序列模式;
（2)再次掃描序列數據庫，構造一個下三角矩陣(如表3所示），得到所有長度為2的序列模式；
（3)構造長度為2的序列模式所對應的掃描數據庫，并對每個投影數據庫重復上面的操作，直到沒有新的序列模式產生為止。
2.偽投影
當序列數據庫可以直接放入內存時，可使用偽投影代替實際的投影數據庫，從而有效減少構造投影數據庫的開銷;同時，不需要構造所有的序列模式對應的投影數據庫，可使用指向數據庫中序列的指針及其偏移量作為偽投影。
例如，針對上述序列數據庫構造α投影數據庫時，序列S1=
五、結論
本文在比較幾種常用序列模式挖掘算法的基礎上，重點介紹了PrefixSpan算法并對其改進，以隔層投影代替逐層投影和偽投影方式，減少序列模式掃描過程中產生的投影數據庫，從而降低系統開銷，提高挖掘效率。下一步將致力于建立個性化移動商務推薦系統，更好地為移動客戶服務。
參考文獻:
[1]中國互聯網信息中心（CNNIC）. 第19次中國互聯網絡發展狀況統計報告[EB/OL].http://www.cnnic.net.cn/html/Dir/2007/01/22/4395.htm
[2]來玲楊寶森:用Web挖掘方法擴充大學圖書館知識庫研究[J].情報雜志，2005(2）:18-20
[3]Agrawal R，Srikant R. Mining Sequential Patterns [A]. Proceedings of the International Conference on Data Engineering[C].Tapei:IEEE Computer Society，1995. 3-14
[4]Agrawal R，Srikant R. Mining Sequential Patterns：Generalizations and Performance Improvements [A]. Proceedings of the International Conference on Extending Database Technology（EDBT）. Avgnon：Lecture Notes in Computer Science，1996. 3-17
[5]Han JiaWei，PeiJian. FreeSpan：Frequent Pattern-projected Sequential Pattern Mining [A]. Proceedings of the International Conference on Knowledge Discovery and Data Mining（KDD’00）[C]. Boston：MAAC Press，2000. 35-359
[6]Pei Jian，Han Jiawei. Mining Squential Patterns by Pattern-growth：The PrefixSpan Approach [J]. IEEE Translations Knowledge and Data Engineering，2004，6（10）：1-17
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
