基于动态多最小支持度的用户频繁轨迹挖掘

严爱俐，刘漫丹

(华东理工大学 信息科学与工程学院，上海 200237)

0 引 言

融合移动互联网、大数据、云计算、物联网等现代化信息技术，推动校园教学管理、教师教学模式、学生学习模式等方面的改革，为广大师生提供了全面智能感知、个性化的服务[1,2]。随着高校的信息化建设，会产生一些校园数据，例如一卡通消费数据、图书馆借阅数据等，通过对这些数据进行频繁序列模式挖掘能够发现很多隐藏的信息。

常用的序列模式挖掘算法有Apriori算法[3]、FP-Growth(frequent pattern growth)算法[4]、FreeSpan算法[5]及PrefixSpan算法[6]等。针对数据量大、分布范围广的数据集，本文选择用PrefixSpan算法进行序列挖掘。但该算法在执行过程中，需要递归构造投影数据集，从而影响了算法的运行时间。目前，已有不少学者针对上述问题提出了改进。文献[7]中通过支持度末尾判断和后缀指针伪投影的方法进行改进，文献[8]中提出基于后缀索引的PrefixSpan算法和基于投影数据库的PrefixSpan改进算法，文献[9]中借助已生成的序列模式投影提出AprioriAll-PrefixSpan改进算法，等等。针对PrefixSpan算法存在的缺陷，本文从阈值、运行效率和运行内存角度出发，分别提出相应的改进举措。

1 相关定义及工作

本文采用PrefixSpan算法从获取的校园数据中挖掘出用户的频繁轨迹模式，PrefixSpan算法是由JW Han等[6]提出的，算法的思想与Apriori算法类似。从长度为1的前缀开始挖掘序列模式，搜索对应的投影数据库得到长度为1的前缀对应的频繁序列，然后递归挖掘长度为2的前缀所对应的频繁序列。以此类推，一直递归到不能挖掘到更长的前缀挖掘为止。

下面对PrefixSpan算法中涉及的相关概念抽象成具体的数学表达式，具体定义如下：

定义1 序列：假设存在序列数据集D={S1,S2,…,Sj,…,SN}， 其中序列Sj(1≤j≤N) 由m项构成，即Sj={ij,1,ij,2,…ij,k,…,ij,m}, (1≤k≤m)，ij,k表示Sj中的第k项；令序列s={ij,k}， 则称序列s是序列Sj的子序列，序列Sj为序列s的超序列；

定义2 支持度(Support)：一个序列的支持度被定义为数据集中包含该序列的记录数占数据集总序列数的比值。假设序列数据集D={S1,S2,…,SN}， 序列Sj={ij,1,ij,2,…ij,k,…,ij,m}， 则子序列s={ij,k} 的支持度即

(1)

定义3 最小支持度(Minimum Support)：用户定义衡量支持度的一个阈值，表示项在统计意义上的最低重要性，记作min_sup；

定义4 频繁序列：假设数据集D中存在子序列s，满足其支持度≥最小支持度，即sup(s)≥min_sup， 则子序列s称为频繁序列，若子序列s由n项组成，则子序列s又可称为频繁n-序列；

定义5 投影数据库：假设有序列Sj={ij,1,ij,2,…ij,k,…,ij,m}， 其中子序列sj={ij,1,ij,2,…,ij,k}, (1≤k≤m)， 则称序列sj是序列Sj的序列前缀，序列Sj为序列sj的序列投影；子序列s′j={ij,k+1,ij,k+2,…,ij,m}， 称其为序列Sj的序列后缀；由s′j(1≤j≤N) 组成的数据库称为投影数据库。

本文是基于PrefixSpan算法的改进，下面将通过表1中的具体实例解释PrefixSpan算法的整个运行过程，设定min_sup=0.5， 对应的最小支持度阈值次数为：min_sup*序列总数N=0.5*4=2次。

表1 序列数据集实例

首先对序列数据集第一次扫描，统计所有项出现的次数：{a}：4、{b}：4、{c}：4、{d}：3、{e}：2、{f}：2、{g}：1。其中{g}出现次数不满足最小支持度阈值次数，则频繁1-序列集如下：{a}、{b}、{c}、{d}、{e}、{f}。将这些频繁1-序列作为前缀并找出对应的投影数据库，见表2。

表2 频繁1-序列前缀及对应投影数据库

接着以前缀{d}为例介绍整个挖掘过程，其它序列前缀挖掘方法类似。对序列{a}对应的投影数据库进行统计：{a}：1、{b}：2、{c}：3、{e}：1、{f}：1、{_f}：1，其中满足min_sup阈值次数的是{b}、{c}，则频繁2-序列为{db}、{dc}。以频繁2-序列为前缀找出对应的投影数据库，见表3。

表3 频繁2-序列前缀及对应投影数据库

同理对2-序列前缀的投影数据库中各项进行统计，前缀{dc}中项{b}出现2次得到频繁3-序列{dcb}对应的投影数据库见表4。根据投影数据库发现没有满足条件的项，因此无法产生频繁4-序列，以{d}为序列前缀挖掘的所有频繁序列如下：{d}、{db}、{dc}、{dcb}。

表4 频繁3-序列前缀及对应投影数据库

2 动态多最小支持度前缀投影挖掘算法(DMS-PrefixSpan)

由于PrefixSpan算法的基本思想是，根据确定的最小支持度min_sup从序列集合中挖掘出满足条件的频繁序列。因此min_sup的选择就显得极为重要，如果min_sup设置过高会导致一些重要的隐藏信息被丢失，反之设置过低则挖掘的结果中混入大量干扰信息。针对用户的频繁轨迹挖掘，其移动轨迹中通常会包含一些热点地区，但这些地区在轨迹中的重要程度相对较低。例如在校园中大部分用户会在特定时间出现在食堂、教室等地点，如果仅根据这些数据希望挖掘出各个用户之间的社会关系，很大程度上会得到所有人的行为轨迹都是相似的。另外，同一个地点对不同用户的重要性是不同的。例如在博物馆工作的工作人员和去博物馆游览的游客，明显能够看出博物馆在后者轨迹模式中重要性明显超过前者，在这种情况下确定的工作人员和游客去博物馆的最小支持度应该有所区别。

其次，用户不同的需求促使用户有不同的行为，随着年龄、角色、生活环境的变化需求也在不断发生变化。例如，校园网络中的用户在大二、大三选修的课程不同，因此其上课的教室、时间、同学也是不同的；选修的课程安排在上学期或者下学期，会对其某段时间的生活作息产生影响。因此通过分析用户行为的转变，试着分析其背后行为转变的原因对学生管理和资源分配具有指导意义。

针对上文提到的单一最小支持度和行为模式变化问题，本文将从以下两个方面：多最小支持度和动态频繁序列挖掘进行讨论。此外，由于使用数据集时间跨度很长且用户数据量很多，因此算法改进还需要考虑到内存消耗问题。本文将引入动态多最小支持度的PrefixSpan改进算法称为动态多最小支持度前缀投影挖掘算法，简称DMS-Prefix-Span算法。

2.1 序列压缩和序列匹配

由于PrefixSpan算法挖掘的结果存在大量的冗余，为了减少挖掘结果的内存占用，提出序列压缩和序列匹配两个概念，将引入序列压缩和序列匹配的PrefixSpan算法称为最长频繁项集挖掘算法，简称L-PrefixSpan算法。其中序列压缩和序列匹配的概念如下：

假设从数据集D中存在频繁n-序列，频繁n-序列是从频繁1-序列中衍生增长而来的，可以发现频繁1～(n-1) 序列为频繁n-序列的子序列，则只保留频繁n-序列即可，这种操作称为序列压缩。

遍历整个挖掘结果序列集合，若其中某序列为其它序列的子序列，则去除这条冗余的子序列，以保证结果中所有序列互相不为子序列或超序列的关系，这种操作称为序列匹配。

根据图1可以发现，挖掘的频繁项如下： {a},{ab},{ac},{af},{abc},{abb},{acb},{abcf},{abbf}， 经过序列压缩可得到如下的结果： {abcf},{abbf},{acb},{af}； 根据序列压缩结果可以进一步发现：序列 {af} 为序列 {abcf} 和 {abbf} 的子序列，则经过序列匹配可得到最终的结果： {abcf},{abbf},{acb}。 以此类推，可以发现经过序列压缩和序列匹配，挖掘的频繁序列会大大减少，因此占用内存空间也会减少。

图1 PrefixSpan算法挖掘结果示例

2.2 多最小支持度的计算

某无线网络中所有用户的轨迹序列集合为UR={R1,R2,…,Ru,…,RN}， 该无线网络中采集的所有地点区域项集为L={l1,l2,…,li,…,lM}， 其中M为该无线网络中地点区域总数。则地点区域li的地点热度用群体地点分布频率(frequency of locations in the group，FLG)表示，如式(2)所示

(2)

式中：N(li) 为统计的轨迹序列中含有地点区域li的序列出现次数，N为轨迹序列中所有轨迹序列总数。

假设无线网络中的某用户u其轨迹序列集合为Ru={ru,1,ru,2,…,ru,x,…,ru,Ku}， 其中Ku为该用户轨迹序列总长度，元素ru,x为轨迹点记录，ru,x=(tu,x,lu,x) 表示用户u的第x个轨迹记录的出现时间tu,x和出现地点lu,x。 用户个人的地点偏好用个人地点分布频率(frequency of locations in the personal tracks，FLP)表示，如式(3)所示

(3)

式中：K(lu,i) 为用户u轨迹序列中含有地点区域li的序列出现次数。

综合考虑地点热度和个人地点概率分布，需要将FLG(li) 和FLP(lu,i) 分别根据其与最小支持度的变化规律进行非线性映射转换。由于FLP(lu,i) 表示用户u的地点偏好程度，计算得到的数值越大表明地点li对用户越重要。选择映射函数的时候要考虑到min_sup与用户在地点出现的频率成正比，所以选用的映射函数在 [0,1] 范围内单调递增的自然对数函数进行变换，具体函数如式(4)所示

f(x)=ln(x+1)

(4)

FLG(li) 表示地点热度，数值越大则表明地点li的热度越高。而min_sup与该地点在整个轨迹序列中出现的次数成反比，因此选择映射函数在 [0,1] 范围内为单调递减的函数。由于指数函数和对数函数互为反函数，所以FLG(li) 的映射函数选用标准对数函数，具体如式(5)所示

(5)

SuperMap建库的核心工作是对数据进行转换处理，转换处理的标准数据能直接应用于后续数据的处理，采用的建库模式是从临时库到标准库再到调查库。

f(x)=exp(-πx2)

(6)

根据式(2)至式(6)，可得用户u在地点li的最小支持度，记为MIS(lu,i)， 具体表达式如式(7)所示

MIS(lu,i)=ln(FLP(lu,i)+1)*exp(-π(FLG(li))2)

(7)

根据式(7)，求得用户u在该无线网络中所有地点的多最小支持度阈值，记为MMS(L)， 具体表达式如式(8)所示

MMS(L)={MIS(lu,1),MIS(lu,2),…,MIS(lu,i),…,MIS(lu,M)}

(8)

2.3 动态频繁序列挖掘

一般情况下，对数据流频繁项的挖掘都是基于某个时间段对数据的分析和研究[10]。主要有两个原因：一是数据量过于庞大挖掘过程会消耗很多时间，二是不同时间段的数据重要程度不同。根据数据流中的不同时序范围，可以把数据流模型划分为如下3类：快照模型、界标模型和滑动窗口模型[11]。参考文献[12]中提到，根据挖掘模式结果集合的精简程度，可以分为全集模式挖掘方法和压缩模式挖掘方法等；压缩模式主要包括闭合模式、最大模式、top-k模式以及三者之间的组合模式。根据2.1节中提到的序列压缩和序列匹配，本文中的挖掘模式为压缩模式中的最大模式挖掘。

挖掘用户频繁轨迹的过程中，综合考虑到数据量和时效性两方面，选择用滑动窗口模型，即窗口的起始时间和结束时间都是变化的。在整个过程中，存在用户本身在不同时段对不同地点偏好程度不同的问题，因此用户在不同时间段内不同地点的min_sup是不同的。文献[13-15]中涉及上述问题，无论是采用滑动窗口模型还是衰减窗口模型，无论数据集是密集数据集或者稀疏数据集，均根据所有之前时间窗口的事务占比确定项的权重，但本文的权值是基于前一个时间窗口的事务占比，通过不断循环该操作既没有忽视之前的数据，同时也大大缩短了计算消耗的时间，其对于内存消耗、运行时间及实验结果均有所改善。

用户u的轨迹序列集合为Ru={ru,1,ru,2,…,ru,x,…,ru,Ku} 且ru,x=(tu,x,lu,x)， 以周期T为窗口大小划分用户轨迹，假设用户数据的起始时间为start、 结束时间为end， 则用户的轨迹序列的滑动窗口划分方式如下： 〈start,start+T,…,start+kT,…,end〉， 且有n个周期。

当Tk=[start+(k-1)T,start+kT], 1≤k≤n时，由式(7)可得用户u在地点li的最小支持度，记为MIS(luTk,i)， 则用户u在n个周期内地点li的最小支持度MMS(lu,i) 如式(9)所示

MMS(lu,i)={MIS(luT1,i),MIS(luT2,i),…,MIS(luTn,i)}

(9)

(10)

(11)

根据Tk周期内用户u的在地点li出现的概率为Pu,li， 在计算T(k+1)周期地点li的最小支持度时需要迭加权值计算，具体计算如式(12)所示

MIS(luT(k+1),i)=MIS(luT(k+1),i)×e-PuTk,li,k=2,3,…,n

(12)

根据式(12)可以计算出用户u在T1～Tn周期地点li所有的最小支持度。

对M个地点重复上述步骤，得到用户u在该无线网络中所有地点的动态多最小支持度阈值，记为DMS(L)， 具体表达式如式(13)所示

DMS(L)={MMS(lu,1),MMS(lu,2),…,MMS(lu,i),…,MMS(lu,M)}

(13)

2.4 DMS-PrefixSpan算法的实现步骤

具体挖掘步骤如下：

步骤1 首先对移动轨迹的序列数据集预处理，然后将数据集以T为周期划分为n个区域称为Tk(k=1,2,…,n)， 令k=1；

步骤2 从Tk开始根据式(7)计算所有地点的多最小支持度阈值MMS(LTk)；

步骤3 结合MMS(LTk) 根据式(12)计算所有地点的动态多最小支持度阈值DMS(LTk)={MIS(luTk,1),MIS(luTk,2),…,MIS(luTk,i),…,MIS(luTk,M)}；

步骤4 对Tk区域内所有出现的地点进行计数，找出所有满足阈值DMS(LTk) 的地点保存作为频繁i-项集，令i=1；

步骤5 对于每个长度为i且满足阈值MIS(luTk,i) 要求的前缀进行递归挖掘：①找出前缀对应的投影数据库，如果投影数据库为空，则递归返回；②统计投影数据库中各个地点出现的次数，将满足阈值MIS(luTk,i) 要求的地点与当前的前缀合并，得到新的前缀；若不存在满足要求的地点，则递归返回；③令i=i+1， 保存合并后的前缀作为频繁i-项集，并递归返回步骤5；

步骤6 遍历频繁轨迹模式集合，进行序列匹配，剔除挖掘的冗余频繁序列；

步骤7 根据式(10)计算不同地点在用户的轨迹中出现的概率，令k=k+1， 递归返回步骤2；

经过n次周期的计算，获得用户在不同周期内所有的频繁序列集。

3 某高校用户频繁项挖掘

3.1 数据预处理

本仿真实验的硬件环境为Intel(R) Core(TM) i7-2600 CPU @ 3.40 GHz，4 GB内存，软件环境为Windows 8 64位操作系统，Matlab R2019b软件和Pycharm开发环境。本文采用2019年09月至2019年12月某高校学生移动轨迹数据共包含6991个用户，获取的真实数据包含“手机的MAC地址、AP的MAC地址、rssi、时间、地点类别、楼宇、房间”，具体信息见表5。

表5 某高校无线网络获取部分信息

首先根据获取的记录数量，保留记录数大于等于1000的用户共有4673名。然后对原始数据中的异常数据进行处理：根据获取的数据发现有些用户在同一时刻获取无线网络登录点是两个不同的MAC地址，所以将用户在5分钟以内的数据进行合并，使用接收无限信号最强的MAC地址作为其确切的登录点。

由于原始的PrefixSpan算法挖掘的结果不强调项之间的先后顺序，为解决这一问题，本文将原始的地点项做出一些改进。表6为用户u的部分移动轨迹数据，第2列时间是将原来的年月日表示方法转变为数值表示，第4列为改进地点项集表示，例如改进后的地点项(21,22)是由在当前时间点出现的地点和下一个出现的地点组成。

表6 用户u部分移动轨迹数据

3.2 实验结果及分析

本文从挖掘用户的频繁模式总数、平均频繁轨迹模式个数和平均轨迹序列模式序列长度3个方面，对比分析基本算法和改进算法的运行时间、运行效率等。另外，还分析了序列压缩和序列匹配对挖掘序列的个数影响，下面为具体实验的比较分析结果。

(1)L-PrefixSpan算法序列压缩与序列匹配效果对比

根据上文2.1节中提到的序列压缩与序列匹配的概念，为验证序列压缩和序列匹配去除冗余轨迹的效果，将PrefixSpan算法和L-PrefixSpan算法挖掘频繁序列的个数进行比较，具体的实验结果见表7，图2为不同最小支持度条件下PrefixSpan算法和L-PrefixSpan算法挖掘结果对比的柱形图。

表7 PrefixSpan算法和L-PrefixSpan算法 挖掘频繁轨迹数量对比

从图2中可以观察到，随着最小支持度min_sup的增大，PrefixSpan算法和L-PrefixSpan算法挖掘结果数量也在随之减小。以最小支持度min_sup=0.05为例，可以发现经过序列压缩和序列匹配，L-PrefixSpan算法挖掘结果数量只占PrefixSpan算法的50%左右，换言之剔除的冗余率大概在50%左右，而其它的最小支持度结果比较的剔除冗余率也在50%左右。根据图2和表7的结果验证了序列压缩和序列匹配的效果，表明序列压缩和序列匹配对于剔除冗余率具有显著的效果。

图2 PrefixSpan算法和L-PrefixSpan算法挖掘结果对比

(2)多最小支持度结果分析

为验证DMS-PrefixSpan算法的有效性，本文将L-PrefixSpan算法与DMS-PrefixSpan算法的挖掘结果进行比较。表8为DMS-PrefixSpan算法挖掘结果，表9为不同最小支持度下L-PrefixSpan算法挖掘结果。表中UserNum为存在频繁轨迹挖掘结果的用户数，PatternNum为挖掘的频繁轨迹模式总数，AvgPatternNum为平均每个用户频繁轨迹模式数，AvgPatternNum/T为每个周期用户的平均频繁轨迹模式数，AvgPatternLen为平均每个频繁轨迹模式的序列长度，AvgPatternLen/T为每个周期的平均序列长度。

表8 DMS-PrefixSpan算法挖掘结果

表9 L-PrefixSpan算法挖掘结果

根据表9可以发现：对于L-PrefixSpan算法，随着最小支持度的增大，挖掘的UserNum值、PatternNum值、AvgPatternNum值、AvgPatternLen值都随之减小；对比DMS-PrefixSpan算法的挖掘结果，所有的AvgPatternLen值均稳定在4左右，但DMS-PrefixSpan算法中的AvgPatternNum值大于L-PrefixSpan算法在不同最小支持度条件下的AvgPatternNum数值。表明改进后的DMS-PrefixSpan算法不仅能够挖掘出用户所有的频繁项集，而且在保证挖掘结果的前提下也没有影响算法的运行效率，算法的具体运行时间见表11。

(3)动态频繁序列挖掘结果分析

根据表10的频繁序列结果展示，可以发现：该用户的行为轨迹在宿舍楼和教学楼之间徘徊(第一个数字“1”表示宿舍楼，“2”表示教学楼)；最长的频繁序列为 ((131，132)， (132，131))和((132，131)， (131，132))， 即用户最长的频繁序列为131→132→131或者132→131→132，符合数据集集中分布在宿舍楼的特点。用户具体的频繁序列移动轨迹如图3所示，其中线段较粗的表示该用户经常往返的路线，而线段较细的表示频繁序列轨迹中相对频率较低的。从图3中能够直观看出，该用户经常往返于宿舍与教学楼、教学楼之间和宿舍之间，表明该学生的行为模式较为单一。且该用户经常往返于教学楼之间，表明该用户的连续课程安排在不同的教学楼之间；学校可以根据用户行为之间的时间差及行动速度，合理安排课间休息时间及课程时间、地点的安排等。

表10 DMS-PrefixSpan算法频繁序列结果展示

(4)运行时间分析

表11为L-PrefixSpan算法和DMS-PrefixSpan算法运行时间对比，可以发现随着支持度的增加，L-PrefixSpan算法的运行时间在随之减少；而DMS-PrefixSpan算法的运行过程中，即使包含滑动窗口模型和多最小支持度模型，但是其运行时间介于min_sup=0.3和min_sup=0.4之间，表明改进后的DMS-PrefixSpan算法有较好的运行效率。

图3 用户的频繁移动轨迹

根据实验(1)～实验(4)的实验结果分析，实验(1)中实验结果验证了序列压缩和序列匹配的有效性，实验(2)、实验(4)分别从挖掘的用户频繁序列模式个数、平均序列长度及运行时间凸显了改进算法的优势。实验(3)中涉及到用户动态频繁序列模式挖掘，可以将挖掘结果进一步用于研究用户的异常行为及学校如何对课程进行合理安排。

表11 L-PrefixSpan和DMS-PrefixSpan算法运行时间比较

4 结束语

本文就传统的频繁项模式挖掘中的单一最小支持度存在的问题做出了改进，引入多最小支持度动态确定模型，在充分运用获取数据的基础上避免由于最小支持度的问题影响最终的挖掘结果。针对PrefixSpan算法中大量冗余的频繁序列，利用序列压缩和序列匹配极大减少了存储空间。为查看用户在一段时间的地点偏好，运用加权的方式使得挖掘结果综合考虑过去和现在不同的行为习惯，并且也大大缩短了挖掘的运行时间。分析研究挖掘的一系列结果，可以了解用户的行为习惯、地点偏好变化等情况。