改進的PrefixSpan算法在客流計數中的應用

王爭,李晉宏

摘 要： 序列模式挖掘是基于關聯規則的頻繁項集的挖掘，其實質是在關聯模型中加入時間屬性。利用改進的PrefixSpan算法對客流計數系統中不同時段的數據進行挖掘分析，給出不同時段的客流高峰的頻繁序列模式，對于提高客流計數系統的精度，給管理決策者調配人力，物力，財力提供技術支持，對于最大限度地發掘購物中心的潛力，提高利潤，具有重要的經濟意義。

關鍵詞： 序列模式挖掘； 關聯模型； PrefixSpan算法； 客流計數

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2013）06-50-03

Application of improved PrefixSpan algorithm in counting passenger flow

Wang Zheng， Li Jinhong

（North China University of Technology， Beijing 100144， China）

Abstract： Sequential pattern mining is a frequent item sets mining based on association rules， and its essence is to add the time attribute to the relation model. In this paper， data in different times of passenger flow counting system is mined and analyzed by the improved PrefixSpan algorithm. Frequent sequential patterns of the peak passenger flow in the different periods are given. It has important economical meaning for improving passenger flow counting system accuracy， providing technical support for the managers to allocate human， material and financial resources， maximizing the potential of the shopping center， and increasing profits.

Key words： sequential pattern mining； correlation model； PrefixSpan algorithm； passenger flow counting

0 引言

客流、物流、財流是購物中心、公園、娛樂場等成功的三大因素。其中客流是公認的各個場所經營管理重要的衡量工具。因為顧客、游客是貨幣的攜帶者，也是商品的潛在購買者，研究其流量的規律，可以增加銷售機會，將他們由觀察者轉變為購物者，可以最大限度地挖掘購物中心的銷售潛力，增加利潤。

購物中心與傳統的百貨業、廉價的超級市場和全天候服務的便利店的經營管理模式都不盡相同。現代購物中心采用的是一種先進的經營管理模式，需要先進的觀念配合科技和技巧方能成功。現代購物中心的設計、運作和管理突破了傳統的零售業的種種局限，成功依賴于理念、策略與科技。 購物廣場的開發目標是追求物業升值最大化和店鋪租金持續升值最大化。越來越多的購物中心把自營部分和出租部分的比例相對調整了很多，更多的購物中心采取的經營策略是只租不售，統一管理。零售業要想把利益最大化的經營方式和理念逐步擴展，逐步規范化，就必須關注客流、物流、財流三個關鍵因素。如何去獲取準確的客流數據，以及確定客流的高峰時段，深層挖掘，準確反映客流量變化趨勢，為經營管理提供準確及時的數據參考依據來訂制營商策略，是一個有價值的研究課題。

1 序列模式挖掘

序列模式的概念最早是由Agrawal和Srikant提出的[1]，是挖掘相對時間或其他模式出現頻率高的模式。給定一個由不同序列組成的集合，其中，每個序列由不同的元素按順序有序排列，每個元素由不同項目組成，同時給定一個用戶指定的最小支持度閾值，序列模式挖掘就是找出所有的頻繁子序列，即該子序列在序列集中的出現頻率不低于用戶指定的最小支持度閾值。

序列模式挖掘是指從序列數據庫中挖掘出頻繁序列模式，為此需要將數據庫轉換為序列數據庫。方法是把用戶ID相同的記錄合并，有時每個事務的發生時間可以忽略，僅保持事務間的偏序關系。

項集（Itemset）是所有在序列數據庫出現過的單項組成的集合。

元素（Element）可表示為（x1，x2…xm），xk（1<=k<=m）為不同的單項。元素內的單項不考慮順序關系，一般默認按照ID的字典序排列。

序列（Sequence）是不同元素（Element）的有序排列，序列s可以表示為s=，sj（1<=j<=l）為序列s的元素。

一個序列包含的所有單項的個數稱為序列的長度。長度為l的序列記為l-序列。

設序列α=，序列β=，ai和bi都是元素。如果存在整數1<=j1

2 PrefixSpan算法

該算法的基本思想是：采用分治的思想，不斷產生序列數據庫的多個更小的投影數據庫，然后在各個投影數據庫上進行挖掘。

基于該算法的相關定義如下。

⑴ 前綴：設每個元素中的所有項目按照字典序排列。給定序列α=，β=（m?n），如果ei'=ei（i?m-1），em'?em，并且（em-em'）中的項目均在em'中項目的后面，則稱β是α的前綴。

⑵ 投影：給定序列α和β，如果β是α的子序列，則α關于β的投影α'必須滿足：β是α'的前綴，α'是α的滿足上述條件的最大子序列。

⑶ 投影數據庫：設α為序列數據庫S中的一個序列模式，則α的投影數據庫為S中所有以α為前綴的序列相對于α的后綴，記為S|α。

⑷ 投影數據庫中的支持度：設α為序列數據庫S中的一個序列，序列β以α為前綴，則β在α的投影數據庫S|α中的支持度為S|α中滿足條件b?α.γ的序列γ的個數。

3 改進的PrefixSpan算法[3]

在基本算法過程中，我們發現構建投影數據的數量是先增加后減少的一個狀態，而且投影數據庫的數量跟頻繁項的位置有很大關系，所以針對投影數據的縮減，我們使用如下幾種方法改進算法，提升效率。

3.1 偽投影技術

所有的投影數據庫都以索引的形式給出，我們只給定一個初始的序列數據庫A，然后所有中間過程都記錄其下標的位置，然后利用下標去原始庫A中查找該字符序列。

3.2 PSD優化算法

首先找出各個頻繁單項，產生每個頻繁項對應的投影數據庫集合。因為非頻繁項出現次數已小于最小支持數。在其后的挖掘中也不會成為頻繁項，故只保存掃描該投影數據庫時得到的頻繁項。然后對每個投影數據庫進行單獨挖掘，之前先比較該投影數據庫所包含的序列數和最小支持數，若投影序列數小于最小支持數，將不會再有超過最小支持數的頻繁項，則退出對該投影數據庫的進一步挖掘。因為舍棄了非頻繁項，將大大減少保存投影數據庫所需內存空間，也將減少其后挖掘中掃描不必要項的時間，提高了算法執行效率。因為在對投影數據庫進行挖掘前，先比較了其包含的序列數和最小支持數，放棄挖掘序列數已小于最小支持度的投影數據庫，減少了掃描不可能出現頻繁序列的投影數據庫的時間，提高了算法執行效率。

3.3 IPMSP優化算法

在構建投影數據庫時，通過檢查序列數據庫關于前綴的前綴，避免對投影數據庫中同一頻繁前綴重復投影，減少投影的次數和數量，并且節省重復投影數據庫的構造時間和在投影數據庫上挖掘模式浪費的時間。同時，在PrefixSpan算法執行過程中，由于在投影序列數小于最小支持數的投影數據庫中，將不會出現超過最小支持數的頻繁項，因此在IPMSP算法中只保存掃描投影數據庫時得到的頻繁項，通過比較投影數據庫所包含的序列數和最小支持數，放棄挖掘序列數已小于最小支持數的投影數據庫，提前退出對投影數據庫的進一步挖掘，減少掃描不可能出現頻繁序列的投影數據庫的時間，從而提高算法執行效率。

3.4 改進PrefixSpan算法實現

⑴ 得到長度為l的序列模式。首先要掃描s，找出所有的頻繁項，每個頻繁項都是一個長度為I的序列模式，并將頻繁項按其支持度從大到小排序。

⑵ 根據頻繁項支持度的大小，依次對頻繁項進行投影，通過構建相應的投影數據庫并遞歸地挖掘每一個來進行挖掘。其中對每一個頻繁項，構建相應的投影數據庫，對投影數據庫掃描一次，得到其局部頻繁項。如果局部頻繁項與第1步得到的除當前頻繁前綴記為α以外的頻繁項相同，記為β，對第l步中的投影數據庫作關于β前綴的投影，判斷是否可以減少β重復投影及其挖掘。如果條件滿足，則只挖掘β前綴的序列模式一次，即得到β為前綴的序列模式的同時可以得到α連接β列模式。在找到原投影數據中對應于該頻繁項的所有后綴集合后，保存該頻繁項的投影數據庫，之后只保存在掃描原投影數據庫時得到的支持數大于min_sup的項，若該頻繁項的投影數據庫所含序列數小于min_sup，則結束在投影數據庫中繼續挖掘。

4 挖掘的數據準備

4.1 數據來源

挖掘所需的數據來源于某大型購物中心的客流自動統計系統。

4.2 挖掘的數據準備

首先作數據預處理。數據預處理有多種方法：數據清理，數據集成，數據變換，數據歸約等。這些數據處理技術在數據挖掘之前使用，大大提高了數據挖掘模式的質量，降低實際挖掘所需要的時間。

利用數據離散化算法將原始數據庫中的實時具體的數據轉化為所需的抽象的序列數據，也是將事務數據庫轉化為挖掘所需的序列數據庫。

將原始數據提取出來后進行分析處理，轉化為序列模式挖掘所需的數據格式，即轉化為序列數據。由于原始數據庫中存儲的數據是具體的實時數據，需要轉為挖掘所需的抽象的序列數據庫。

對原始數據的處理辦法：首先對源數據進行規范化，然后進行離散化處理。

數據規范化：將提取的數據逐條分析，對于空值記錄執行刪除操作。

數據離散化：利用區間劃分法進行離散化。所謂的區間劃分法：就是將數據的值域劃分為不同的區間，將具體的數據抽象為屬于某個區間，該區間用一個抽象的字母所表示，組成一個序列。例如：某個變量的值域為1-9，將其劃分為3個區間，1-3，4-6，7-9，所有屬于1-3區間的數值用A表示，所有屬于4-6區間的數值用B表示，所有屬于7-9區間的用C表示。而對于具體的值如2，2.5，3，4.1，5，6，7，8.5，9則可以分別表示為A，A，A，B，B，B，C，C，C。也就是說將具體的值分別劃分到不同的區間中去，進而實現數據的離散化處理。區間劃分法進行數據離散化處理可用下面的圖表示出來，劃分標準是0-100用A表示，101-200用B表示，201-300用C表示，301-400用D表示，以此類推。

表1和表2給出了部分原始數據及離散化結果。

表1 部分原始數據

5 挖掘結果及分析

給定支持度為2，根據表2的離散化數據挖掘出的頻繁模式為：AA，CJG，CJ，CG。

表2 離散化后的數據

通過實驗挖掘出的頻繁序列子模式可以分析某商場在周末的8：00到下午2：00的客流量都很大，而在周一，周二上午8：00到10：00客流都比較少，根據挖掘結果找到客流高峰時段的頻繁序列，用于預測購物中心客流的高峰時段，給管理人員提供調配人力，物力，財力等決策提供支持，以利于最大限度的挖掘購物中心的潛力，提高效率，增加經濟效益。

參考文獻：

[1] JiaWei Han， Micheline Kamber.數據挖掘概念與技術[M].機械工業

出版社，2001.

[2] 趙華，宋順林.改進的序列模式挖掘算法在交叉營銷中的應用[J].計

算機工程于設計，2007.3.

[3] 吳南，胡學剛.基于PrefixSpan序列模式挖掘的一種改進算法[J].電

腦知識與技術，2007.4.

[4] 汪林林，范軍.基于PrefixSpan的序列模式挖掘改進算法[J].計算機

工程，2009.12.