基于移动交易序列模式的用户行为模式增益挖掘方法

摘要

基于移动交易序列模式的用户行为模式增益挖掘，首先是基于增益模式集成移动模式挖掘高增益移动行为序列模式，其次是依赖频次模式挖掘解决不同类型商务模式的顾客行为序列模式，然后是在各种复杂环境下验证评价算法的执行效率。通过高增益模式与动态行为路径的集成探索出高效益的移动序列模式处理。本发明提出基于移动商务行为特征数据信息构造树算法，挖掘移动商务行为数据的品类特征信息，在同类算法结果比较中具有能较高水准地表达发掘移动序列行为模式。

说明书

技术领域：本发明涉及一种增益挖掘方法，特别是一种基于移动交易 序列模式的用户行为模式增益挖掘方法

背景技术：数据挖掘的行为是指在大数据库中发现潜在有用的信息的 过程。在行为信息学中，早期的研究集中在不同类别的应用中发掘各种用 户行为模式，例如在电子商务领域中的交叉营销模式，电子商务网站设计 与管理，规划移动商务框架。自从移动传媒设备及无线移动应用成为最流 行最重要的传播媒介之后，这些移动商务事务议题，如移动框架下挖掘移 动用户商业行为模式，在过去10几年发展中日趋成为热点研究课题。现 有的移动设备通过GPS设备功能服务日志记录了移动用户个性化系列行 为路径，因此，商业体会及时和准确获取移动用户移动行为路径细节。结 合行为日志与支付记录分析，用户这种移动购买事务动态路径序列能够激 发某种个性化的序列行为模式，在这些移动事务序列中暗含着有潜质的有 用信息。有学者提出基于移动框架下的动态路径及序列模式发掘移动用户 行为序列模式，即该序列模式包含用户动态路径计算及移动商务事务序 列。比如一个移动序列模式pattern{|￥_A:(trousers)|；|￥_B:(shoes)|；＠￥_A→ ￥_B}，这种移动序列模式揭示出客户的移动商务事务路径模式经常是{＠ ￥_A→…￥_B}，顾客习惯性的沿着该行为序列模式路径{＠￥_A→…￥_B}分 别在￥_A买trousers在￥_B买shoes，假设店主捕获了这些客户序列行为模 式，那么￥_A店老板就会针对shoes搞促销活动，迎合顾客的个性商业事 务行为需求，在本店内努力培养顾客的购买预期。

然而，在现实商业事务处理中，移动序列模式不能真实发掘数据库中 商品实际利润，这种序列行为挖掘客户行为信息存在一定的缺陷，如购买 黄金珠宝等饰品的顾客高价值商务行为，由于这些顾客的低频率购买行 为，因而这些给商家带来丰厚利润的高增益顾客没有被发掘出来。据此， 在传统商业事务数据库处理中增益挖掘被提出用于解决此类实际商业问 题。常用的处理手段是事先设定增益阈值，该值的设计可以考虑商品的特 性、价值、增益，希冀这种增益挖掘能在商务事务数据库中发掘出具有高 利润的高效益商务行为模式。所以按此观点，将增益挖掘加进移动模式挖 掘框架结构中用于发掘潜在的价值客户行为模式。这些有用的信息反馈给 行为模式的决策者，他们基于此就可制定反应敏捷的商务行为模式。假设 存在如下两种客户商务行为模式，如pattern₁{|￥_a:(skirts)|；|￥_f:(shoes)|；＠ ￥_a→￥_c→￥_e→￥_f}，和pattern₂{|￥_a:(skirts)|；|￥_f:(gold jewelry)|；＠￥_a→ ￥_b→￥_c→￥_d→￥_e→￥_f}。两种客户商务行为模式的路径起点和终点虽然 相同，但是行为模式的路径不同，因而客户最终购买模式也可能存在差异。 从客户购买模式来看，通常都会认识到两种商品shoes和gold jewelry的 利润价值差异较大。现实商务管理中，如果商店老板能事先发现客户的这 两种购买行为模式，依此商家就会基于模式pattern₂的行为路径中搞商品 促销与展销活动，以便吸引和培养客户在￥_a购买skirts之后能在￥_f购买 高利润的gold jewelry商品。

从现有的研究文献看，虽然针对移动模式挖掘与增益挖掘都有相关的 研究成果，目前国内还没有实现两者相融合的研究，国外针对两者在移动 商务模式中的潜在信息挖掘研究开展的也不够深入与系统，离实际应用还 有差距。本文旨在基于增益挖掘集成移动序列模式行为发掘高增益移动序 列模式。为解决此问题，本文提出了逐层扩展算法与构造树算法两种类型 算法，逐层扩展算法属于过程处理发现，构造树算法属于深度优先搜索与 宽度优先策略，构造树算法树形结构表述了移动商务行为数据的品类特征 信息，如产地、产品名目、行为路径及利润等商务数据库相关的信息。从 实验结果分析，构造树算法能充分表示客户商务行为特征，在同类算法结 果比较中具有能较高水准地表达发掘移动序列行为模式。

发明内容：针对上述现有技术的不足，本发明基于增益挖掘、集成挖 掘移动序列交易数据，发现高增益电子商务移动序列模式，挖掘发现移动 商业交易框架下的用户事务行为路径与综合挖掘用户倾向性的交易行为， 提供了一种用户行为模式增益挖掘方法。

为实现上述目的，本发明采用的技术方案是：基于移动交易序列模式 的用户行为模式增益挖掘方法，先对符号表示及语义做出说明：

表1符号表示及语义

其具体步骤是：

一、算法的输入

序列增益模式U_SP(T_i)树的构造过程是一遍扫描源数据库，在U_SP(T_i) 树中每个节点P都包含节点位置、项目集、节点标号及路径列表等信息， 采用公式P|location,[itemset_i],T_ID,Path_list|表示构造树节点完整信息。P_location记录节点位置，相同节点可以具有多个项目集P_[itemseti]，P_TID表示移动序列 交易标识，路径列表表示节点项目集交易路线图，算法中的头表的作用能 有效连接U_SP(T_i)树的每个节点，是算法的输入。

树形算法的处理过程是基于移动交易序列数据库D_site及其高增益表 2，具体假设的最小支持度阈值A_threshold与最小增益阈值U_threshold的设定可 以参照移动序列加权位置项集交易事务映射表3。项目模式挖掘框架及模 式挖掘流程框架如图1和图2。

表2商品分类增益

表3基于移动序列加权位置项集交易事务映射

图4序列增益模式U_SP(T_i)树的构造过程是一遍扫描源数据库，在 U_SP(T_i)树中每个节点P都包含节点位置、项目集、节点标号及路径列表等 信息，采用公式P|location,[itemset_i],T_ID,Path_list|表示构造树节点完整信息。 P_location记录节点位置，相同节点可以具有多个项目集P_[itemseti]，P_TID表示移 动序列交易标识，路径列表表示节点项目集交易路线图，算法中的头表的 作用能有效连接U_SP(T_i)树的每个节点，是算法的输入。图5是U_SP(T_i)树 构造图。

二、构造树节点插入

构造树的过程是逐层读取移动交易数据库D_site，开始时第一个交易序 列T₁被读取，接着读取该序列中第一个交易|￥_a:[C_item-1,1]|，其中包含位 置商品信息￥_a:[C_item-1]，按照移动序列加权位置项集交易事物映射表，基 于移动序列加权位置项集交易事务映射转化为￥_a:t₁，然后插入U_SP(T_i)构 造树。通过相应的方式构造其余节点，数据库D_site中所有的序列点被插 入后，得到构造树。

三、基于构造树加权高增益挖掘

现在介绍构造树U_SP(T_i)后算法中发掘移动序列加权高增益SP_weighted。 基本思路是依赖U_SP(T_i)构造树，采用深度优先策略发掘增益SP_weighted。首 先是回溯U_SP(T_i)构造树的输入头表Htable，产生基于加权位置项集高增 益U_SP，然后是在满足条件的U_SP(T_i)构造树中产生基于移动序列加权高增 益SP_weighted，有效地压缩存储在基于移动序列加权高增益SP_weighted构造树 节点i-itemset中。

四、通过剪枝减少构造树搜索空间

在处理节点i-itemset过程中，如果回溯检测路径过长，则调整检测技 术进行剪枝以适应用户设定的阈值，表4为序列加权位置项集高增益剪枝 数据库映射集。即对itemset形成SP_weighted时，相对于 SUP(2-Profit_Itemset-x)≥A_threshold及U_SP(2-Profit_Itemset-x)≥U_threshold时，则被 剪掉。经过这种动态剪枝，剪掉无用的输入节点，从而减少搜索空间，提 高了挖掘效率。图3给出了剪枝过程。

表4序列加权位置项集高增益剪枝数据库映射

本发明提出了基于移动序列商业环境下高增益新数据挖掘算法，涉及 两方面的主题，即移动交易序列模式及增益挖掘，同时做了代表算法效果 的比较。未来算法还要在算法执行效率及其商业实现环境扩展方面努力实 现扩展与提升。实验结果表明，基于树形移动用户交易序列模式挖掘算法 能发现交易事物行为路径与用户交易倾向性行为，提高移动电子商务交易 平台管理与规划。

附图说明

图1模式挖掘框架。

图2基于深度优先的树形移动序列高增益模式挖掘流程框架。

图3基于数据库Dsite的移动序列加权高增益候选树的剪枝过程。

图4U_SP(T_i)构造树算法流程。

图5U_SP(T_i)算法构造图。

具体实施方式：

如图4所示：U_SP(T_i)树的构造过程是一遍扫描源数据库，在U_SP(T_i) 树中每个节点P都包含节点位置、项目集、节点标号及路径列表等信息， 采用公式P|location,[itemset_i],T_ID,Path_list|表示构造树节点完整信息。P_location记录节点位置，相同节点可以具有多个项目集P_[itemseti]，P_TID表示移动序列 交易标识，路径列表表示节点项目集交易路线图，算法中的头表的作用能 有效连接U_SP(T_i)树的每个节点，是算法的输入。

如图5所示：构造树的过程是逐层读取移动交易数据库D_site，开始时 第一个交易序列T₁被读取，接着读取该序列中第一个交易|￥_a:[C_item-1,1]|， 其中包含位置商品信息￥_a:[C_item-1]，按照表4基于移动序列加权位置项集 交易事务映射转化为￥_a:t₁，然后插入U_SP(T_i)构造树。通过相应的方式构 造其余节点，数据库D_site中所有的序列点被插入后，得到图5的构造树。

实验结果：

实验是对两种算法的执行效果验证，算法的优劣必须从执行时间与占 用系统内存等方面反映出来。试验环境配置为Pentium(R)Dual-Core CPU  E6500@2.93GHz，内存2GB，操作系统Microsoft windows XP Professional  Service Pack3。移动商业环境参数设置具有限制增益挖掘效果，要求环境 一致下变更参数阈值与移动序列规模比较算法效果。两类算法在系统限定 内存及不同移动序列模式下挖掘高增益SP_weighted时的执行时间与内存需 求占用等方面效果看，在相同实验环境与商业环境下，在执行时间方面构 造树法相对要优化于逐层法，但是在占用内存方面构造树法由于在节点构 造和回溯时占用更多的内存空间。如表5算法执行效率比较。

表5算法执行效率比较

从实验结果看，构造树法在阶段I、II中算法模式与算法参数阈值的 规划有助于挖掘过程中的剪枝处理，因而从实验效果看相对于逐层法较优 化。

本发明提出了两类基于移动序列商业环境下高增益新数据挖掘算法， 涉及两方面的主题，即移动交易序列模式及增益挖掘，同时做了两类算法 效果的比较。未来算法还要在算法执行效率及其商业实现环境扩展方面努 力实现扩展与提升。