张晓滨，李园园，郭 斌

ZHANG Xiaobin,LI Yuanyuan,GUO Bin

西安工程大学 计算机科学学院，西安710048

College of Computer Science,Xi’an Polytechnic University,Xi’an 710048,China

1 引言

传统的序列模式挖掘算法通常将用户历史行为数据作为整体进行频繁模式挖掘，发现用户购买行为习惯，产生推荐，并未考虑一段时间内，行为之间的内在关联性。而用户的行为并不是独立存在的，行为与行为之间存在着关联性[1]，尤其在移动环境下，具有情景敏感特性的用户序列行为的关联性更为显著[2]，通过研究前一行为与后续行为的联系，发现用户行为序列模式，根据发现的行为序列模式可以更准确地预测后续行为，提高推荐质量。文献[3]对比移动用户与传统用户的需求、行为差异性，提出移动用户需求面临的新挑战，即实时性、上下文感知等特点[4-5]。该文献定义情境即“上下文”，是用于描述实体状态的任何信息，其中，实体可以是人、地点或者和应用程序之间相互交互的客体[6-7]。文献[8]将用户位置、环境等情景信息与用户运动轨迹进行聚合，形成用户潜在社交网络，情景感知的自动聚合加快了潜在网络的发现速度和准确性，然而文献[8]中对情景数据进行简单聚合，并没有深入研究各情景要素对用户行为的影响。序列模式挖掘是用户行为研究的主要方法，文献[9]总结了序列模式挖掘近十年来的发展状况并提出了其未来的研究重点，即用户行为模式发现的片面性以及多情景属性对移动用户序列行为挖掘的巨大潜力[10]。本文在用户行为模式挖掘基础上加入情景敏感性因素，提出一种将描述实体状态的多情景属性与用户行为模式挖掘相结合的用户行为模式挖掘方法。

2 基于情景敏感的用户行为序列

研究从移动用户序列行为的情景敏感性入手，将收集到的用户序列行为记录以时间、位置因素对其进行约束处理，进而提出一种将约束后的用户序列行为转化成决策表的方法，此方法解决了进一步用粗糙集属性约简方法对决策表进行序列行为模式挖掘的首要问题。

2.1 序列项约束处理

用户历史数据中的序列行为必须在一定时间段内才有效、有意义，即序列行为是有时间、位置限制的。前序行为与后序行为如果相隔时间太长，则可能没有任何关系，可以认为前一序列活动已经结束；相反，如果连续的两个行为之间相隔时间太短，考虑用户不可能在同一时间同时完成多个行为可以判定这两个行为之间也是无关的。文献[11]以序列项之间的时间间隔和整个序列的时间间隔对用户签到段进行约束，这种方法充分考虑了序列项之间的时间特性，但忽视了项与项之间的位置变化，序列项之间的时间段的分割产生是随着项位置的改变而产生的，只有位置发生了改变才能将时间这个连续实体分割产生“时间段”，如果时间变了，位置没变，则用户的行为未发生转移。因此，将位置与时间结合起来对研究序列项更有实际意义。

将获得的原始签到段数据表示为I={I1,I2,…,I n}，每一个行为项由时间、位置等情景属性构成，即Ii∈I，Ii={(Pi,R)|Ti∈R,Pi∈R}，Pi表示位置，R表示描述项Ii的各情景属性组成的集合。行为序列I中，相邻两个项的时间差是ΔTnext(Ii)=(Ti-Ti-1)，整个序列的时间间隔是Twhole(In)=(Tn-T1)，由此定义Cmax-next和Cmin-next为相邻序列间最大和最小时间间隔，定义Cmax-whole和Cmin-whole为整个序列的最大和最小时间间隔。则由Cmax-next、Cmin-next、Cmax-whole、Cmin-whole、Pi五个参数对原始数据进行约束处理，基于时间、位置约束的序列项处理算法步骤如下：

步骤1将项集合中的每个项依次追加到事务项中，生成预处理事务项，并对生成的每一个预处理事务项进行步骤2 的约束处理。

步骤2对事务项进行约束处理，约束规则如下：

（1）如果该预处理事务项的相邻序列项时间差和整个序列的时间差在给定最大、最小时间差范围内，且位置不相等，就将该项加入事务项Sj，然后返回判断下一个项。

（2）如果该预处理事务项相邻项时间差小于Cmin-next，或者整个序列时间差小于Cmin-whole，或者位置相等，Ii是错误项，返回判断下一个项。

（3）如果该预处理事务相邻项时间差大于Cmax-next，或者整个序列时间差大于Cmax-whole，则结束当前序列Sj；开始下一个事务序列项Sj+1的判断。

步骤3经过约束处理后的事务项放入事务集合中，直至项集合遍历结束，得到事务集合。

算法实现如下：

输入：项的集合I={I1,I2,…,I n}，预处理事务项Sj'={I1}，Cmax-next，Cmin-next，Cmax-whole，Cmin-whole，Pi

输出：D

2.2 生成决策表

Pawlak[12]提出粗糙集属性约简与规则提取不仅能发现影响行为模式的各属性重要度，并且通过粗糙集规则提取挖掘基于多情景属性组合影响的用户行为模式[13-14]。

定义1（决策信息系统）IS={U,R,V,f}，U是有限对象集，x∈U,R=C∪D,C是条件属性，D是决策属性，C∩D=∅，V=Ra，Ra是属性a的值域，∀a∈R，f是U×R→V的一个信息函数，它为每个对象的每个属性赋予一个信息值，f(x,a)∈Ra。

（2）将Si中满足fk≥δ的相邻两项依次序转换成决策对Xi={Pi,Ri,Pi+1}，Pi表示行为Ii发生时所处位置信息，R是描述Ii的情景属性集合，Pi+1表示紧随Ii的后序行为项Ii+1发生时所处位置信息。

（3）决策对Xi={Pi,Ri,Pi+1}，Xi∈U，将Ii的属性集合Ri转化成决策信息系统IS中的条件属性集合C，Pi+1是项Ii+1的位置属性，将Pi+1转化成Xi的决策属性D，V=∪Ri∪Pi+1，∀a∈(Ri∪Pi+1)，f(xi,a)∈Va。

3 实验分析

实验中选取某市区100 位志愿者最近3 个月的签到记录作为实例数据，对大量签到数据进行统计实验分析得出，签到段所包含的签到序列记录的时间差在10～120 min内的概率为0.9以上，据此设置参数值Cmax-next=80 min，Cmin-next=15 min，Cmax-whole=130 min，Cmin-whole=100 min，δ=0.85，Pi是对位置语义本体信息概念分层后的场所地点“电影院”，根据时间、位置约束后的事务D={S1,S2,…,S4009}，经过fk约束后的事务项如下：

表1 信息决策表

Sn1(A,Ra1)→(B,Rb1)→(C,Rc1)→(F,Rf1)Sn2(A,Ra2)→(F,Rf2)

Sn3(A,Ra3)→(B,Rb3)→(F,Rf3)

Sn4(B,Rb4)→(F,Rf4)

其中A、B、C、F是位置信息，R是情景属性集合，将事务D转换成决策对，结果为：X1={A,Ra1,B}，X2={A,Ra2,F}，X3={A,Ra3,B}，X4={B,Rb1,C}，X5={B,Rb3,F}，X6={B,Rb4,F}，X7={C,Rc1,F}，（X1-X7顺序做了调整，与表1 对应）属性集合R由用户生理环境C1（心跳、体温、运动方式）和物理环境C2（时间、位置、湿度、交通状况）组成，各情景属性在数据预处理阶段需要进行概化和分层，条件属性R5的位置信息和决策属性D的位置信息由于不同标准的概念分层而产生不同结果。将决策对转换成决策信息表如表1 所示。

实验证明，经过时间、位置约束的序列项集合中已去除了无意义的签到数据，精确了样本数据，约束后的用户数据经过模式转换生成决策表的方法则解决了粗糙集挖掘基于情景敏感的行为模式所面临的首要、关键问题，此基于情景约束和情景感知的行为模式挖掘方法具有更好的有效性和准确性。

4 结束语

移动环境下，用户的兴趣和选择是实时的、动态的、情景敏感的[15]，针对当前移动用户序列行为挖掘的情景敏感性问题，本文提出一种对用户序列行为进行情景约束以及一种将约束后的用户序列行为转化成可用粗糙集属性约简方法进行序列行为模式挖掘的决策表方法。在此基础上，可以对基于情景敏感的用户序列行为进行挖掘，对基于情境敏感的用户兴趣建模和序列个性化推荐展开进一步研究。

[1] Lin Mingyen，Lee Suhyin.Efficient mining of sequential patterns with time constraints by delimited pattern growth[J].Knowledge and Information Systems，2005，7（4）：499-514.

[2] Staunstrup J，Tong F，Yu L，et al.Services in context[J].Computer System Application，2009，18（6）：161-167.

[3] 孟祥武，王凡，史艳翠，等.移动用户需求获取技术及其应用[J].软件学报，2014，25（3）：439-456.

[4] Mahmoud Q H，Al-Masri E，Wang Zhixin.Design and implementation of a smart system for personalization and accurate selection of mobile services[J].Requirements Engineering，2007，12（4）：221-230.

[5] Ricci F.Mobile recommender systems[J].Journal of Information Technology and Tourism，2011，12（3）：205-231.

[6] 王立才，孟祥武，张玉洁.上下文感知推荐系统[J].软件学报，2012，23（1）：1-20.

[7] 李蕊，李仁发.上下文感知计算及系统框架综述[J].计算机研究与发展，2007，44（2）：269-276.

[8] 曹怀虎，朱建明，潘耘，等.情景感知的P2P 移动社交网络构造及发现算法[J].计算机学报，2012，35（6）：1223-1233.

[9] 王虎，丁世飞.序列模式挖掘研究与发展[J].计算机科学，2009，36（12）：14-17.

[10] Adomavicius G，Sankaranarayanan R，Sen S，et al.Incorporating contextual information in recommender systems using a multidimensional approach[J].ACM Transactions on Information Systems，2005，23（1）：103-145.

[11] 夏英，孙冲武.基于时空序列模式匹配的兴趣点推荐方法[J].重庆邮电大学学报：自然科学版，2011，23（3）：368-373.

[12] Pawlak Z.Rough set[J].International Journal of Computer and Information Science，1982，11（5）：341-356.

[13] 杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报，2007，30（5）：815-816.

[14] 常犁云，王国胤，吴渝.一种基于Rough Set 理论的属性约简及规则提取方法[J].软件学报，1999，10（11）：1206-1211.

[15] 史翠艳，孟祥武，张玉洁，等.一种上下文移动用户偏好自适应学习方法[J].软件学报，2012，23（10）：2533-2549.