改进的PrefixSpan算法在客流计数中的应用
2013-04-29王争,李晋宏
王争,李晋宏
摘 要： 序列模式挖掘是基于关联规则的频繁项集的挖掘，其实质是在关联模型中加入时间属性。利用改进的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=
一个序列包含的所有单项的个数称为序列的长度。长度为l的序列记为l-序列。
设序列α= 2 PrefixSpan算法 该算法的基本思想是：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行挖掘。
基于该算法的相关定义如下。
⑴ 前缀：设每个元素中的所有项目按照字典序排列。给定序列α=
⑵ 投影：给定序列α和β，如果β是α的子序列，则α关于β的投影α'必须满足：β是α'的前缀，α'是α的满足上述条件的最大子序列。
⑶ 投影数据库：设α为序列数据库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.
