论文部分内容阅读
[摘要] 随着移动商务的迅速发展，移动用户面临的带宽限制和信息贫乏问题也日益凸显。Web使用挖掘通过对用户访问Web时在服务器留下的访问记录进行挖掘，在海量Web日志数据中自动、快速地发现用户访问序列模式。通过模式分析向移动用户推荐其感兴趣的内容。论文在比较几种常用序列模式挖掘算法的基础上，着重对PrefixSpan算法进行了研究和优化。
[关键词] 移动商务 Web使用挖掘 PrefixSpan算法 序列模式
一、引言
随着移动网络的快速发展和电子商务的广泛应用，移动网络用户对于商务信息的需求也大幅提升。据中国互联网络信息中心（CNNIC）2007年1月发布的《第19次中国互联网络发展状况统计报告》显示，截至2006年底，我国网民人数达到了1.37亿，其中，新兴上网方式——手机上网也初具规模，达到1700万人。手机上网将成为互联网接入方式的新潮流。但在对使用手机上网的网民进行调查发现，有72.2％和30.9％的网民使用手机上网主要是收发邮件和浏览信息,而费用高(占86.4%）、网速慢(占33.4%）是网民使用手机上网经常遇到的问题;此外，不方便、可获取信息太少等也成为网民不使用手机上网的原因。一方面是以手机为代表的移动设备的迅速发展，而另一方面却是移动商务网站上的信息贫乏和服务落后，解决方法之一就是进行Web使用挖掘，寻找移动商务客户感兴趣的内容并向其推荐。
Web使用挖掘是对用户访问Web时在服务器留下的访问记录进行挖掘，挖掘对象是在服务器上的日志信息，也称为Web日志挖掘，其目的是在海量的Web日志数据中自动、快速地发现用户的访问模式（即序列模式）。在经过对这些模式进行分析和可视化之后，可以为用户提供个性化的服务。序列模式挖掘是模式发现中运用得比较成功的方法，本文在比较几种常用的序列模式挖掘算法的基础上，对PrefixSpan算法进行了研究和优化。
二、序列模式挖掘算法
序列模式挖掘是从序列数据库中发现频繁子序列作为模式，被广泛应用于客户购买行为模式预测、网络访问模式预测、疾病治疗早期诊断、自然灾害预测及DNA序列破译等方面。序列模式最早由Agrawal R和Srikant R提出，常用算法有：
·AprioriAll算法在每一次扫描数据库时，利用上一次扫描时产生的大序列生成候选序列，并在扫描同时计算支持度，满足支持度的候选序列作为下次扫描的大序列。算法主要缺陷在于容易生成庞大的候选序列集和需要多次扫描数据库，不易发现长序列模式并导致较大开销；
·GSP（Generalized Sequential Patterns）算法类似于Apriori算法，但引入了时间约束、滑动时间窗和分类层次技术，有效减少了候选序列数量和无用模式。然而GSP算法仍然需要对序列数据库进行循环扫描；若序列数据库规模比较大，可能产生大量候选序列模式；且难以处理长序列模式的情况；
·FreeSpan算法以Apriori-based演算法为基础，但改进了产生候选序列的方式并验证是否为高频序列。该方法将搜寻区域由大范围的完整资料库改为小范围的映射资料库，产生的候选序列数量较少，也减少了扫描资料库的时间，并提升了挖掘的效率。但该算法必须完整保留与该项目有关的序列，且在产生候选序列时并不考虑顺序性，因此可能产生过多的候选序列。
本文将要论述的PrefixSpan算法与FreeSpan类似，但PrefixSpan不需要产生候选序列，从而大大缩减了检索空间；相对于原始的序列数据库而言，投影数据库的规模不断减小。PrefixSpan算法的缺点在于建立映射资料区间的成本很高，若资料项目平均分配在每个序列中，则成本便会急剧增加。下面对该算法进行介绍和优化。
三、PrefixSpan算法及其改进
1.符号化表示
序列（Sequence）:是不同项目集（ItemSet）的有序排列，一个序列S可以表示为,,为项目集（ItemSet），也称为序列S的元素。
子序列:设如果存在整数使得则称序列α为序列β的子序列，记为。
序列α在序列数据库S中的支持数:序列数据库S中包含序列 α的序列个數，记为Suuport(α)。
序列模式:给定支持度阈值ξ，如果序列α在序列数据库中的支持数不低于ξ，则称序列α为序列模式。长度为1的序列模式记为1-模式。
2.算法描述
给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式。具体算法如下：
·扫描序列数据库，生成所有长度为1的序列模式；
·根据长度为1的序列模式，生成相应的投影数据库；
·在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为1的序列模式为止。算法描述如图1所示。
例如:序列数据库S如表1所示，并设用户指定的最小支持度min_support=2。
通过对表1给出的序列数据库S进行扫描，产生长度为1的序列模式有::4，:4，:4，:3，:3，:3。
序列模式的全集是分别以，，，，和为前缀的序列模式的集合，现构造不同前缀所对应的投影数据库，结果如表2所示:
分别对不同的投影数据库重复上述过程，直到没有新的长度为1的序列模式产生为止。
3.PrefixSpan算法
输入:序列数据库 及最小支持度阈值min_sup
输出:所有的序列模式
方法:调用子程序PrefixSpan(<>,0,S)
在子程序PrefixSpan(α,L,S｜α)中，参数α为一个序列模式， L为序列模式α的长度，当α为空则S｜α为S，否则为α的投影数据库。子程序算法如下：
·扫描S｜α，找到满足下述要求的长度为1的序列模式b:（1） b可以添加到α的最后一个元素中并为序列模式;（2）可以α的最后一个元素并为序列模式;
·对每个生成的序列模式b，将b添加到α形成序列模式α`，并输出α`;
·对每个α`，构造α`的投影数据库S｜α`，并调用子程序PrefixSpan(α,L+1,S｜α`)
四、PrefixSpan算法改进
由于PrefixSpan算法的主要开销在于投影数据库的构造，因此对PrefixSpan算法的改进主要是从减少投影数据库入手。
1.隔层投影
使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数。
仍以前面所述的序列数据库为例，改用隔层投影，具体步骤如下：
（1)扫描序列数据库，产生所有长度为1的序列模式;
（2)再次扫描序列数据库，构造一个下三角矩阵(如表3所示），得到所有长度为2的序列模式；
（3)构造长度为2的序列模式所对应的扫描数据库，并对每个投影数据库重复上面的操作，直到没有新的序列模式产生为止。
2.伪投影
当序列数据库可以直接放入内存时，可使用伪投影代替实际的投影数据库，从而有效减少构造投影数据库的开销;同时，不需要构造所有的序列模式对应的投影数据库，可使用指向数据库中序列的指针及其偏移量作为伪投影。
例如，针对上述序列数据库构造α投影数据库时，序列S1=所对应的伪投影为一个指向S1的指针，指针偏移设定为2。同样地，序列S1的投影数据库对应的伪投影也是一个指向S1的指针，但指针偏移设定为4。以此类推。
五、结论
本文在比较几种常用序列模式挖掘算法的基础上，重点介绍了PrefixSpan算法并对其改进，以隔层投影代替逐层投影和伪投影方式，减少序列模式扫描过程中产生的投影数据库，从而降低系统开销，提高挖掘效率。下一步将致力于建立个性化移动商务推荐系统，更好地为移动客户服务。
参考文献:
[1]中国互联网信息中心（CNNIC）. 第19次中国互联网络发展状况统计报告[EB/OL].http://www.cnnic.net.cn/html/Dir/2007/01/22/4395.htm
[2]来玲杨宝森:用Web挖掘方法扩充大学图书馆知识库研究[J].情报杂志，2005(2）:18-20
[3]Agrawal R，Srikant R. Mining Sequential Patterns [A]. Proceedings of the International Conference on Data Engineering[C].Tapei:IEEE Computer Society，1995. 3-14
[4]Agrawal R，Srikant R. Mining Sequential Patterns：Generalizations and Performance Improvements [A]. Proceedings of the International Conference on Extending Database Technology（EDBT）. Avgnon：Lecture Notes in Computer Science，1996. 3-17
[5]Han JiaWei，PeiJian. FreeSpan：Frequent Pattern-projected Sequential Pattern Mining [A]. Proceedings of the International Conference on Knowledge Discovery and Data Mining（KDD’00）[C]. Boston：MAAC Press，2000. 35-359
[6]Pei Jian，Han Jiawei. Mining Squential Patterns by Pattern-growth：The PrefixSpan Approach [J]. IEEE Translations Knowledge and Data Engineering，2004，6（10）：1-17
注：“本文中所涉及到的圖表、注解、公式等内容请以PDF格式阅读原文。”
[关键词] 移动商务 Web使用挖掘 PrefixSpan算法 序列模式
一、引言
随着移动网络的快速发展和电子商务的广泛应用，移动网络用户对于商务信息的需求也大幅提升。据中国互联网络信息中心（CNNIC）2007年1月发布的《第19次中国互联网络发展状况统计报告》显示，截至2006年底，我国网民人数达到了1.37亿，其中，新兴上网方式——手机上网也初具规模，达到1700万人。手机上网将成为互联网接入方式的新潮流。但在对使用手机上网的网民进行调查发现，有72.2％和30.9％的网民使用手机上网主要是收发邮件和浏览信息,而费用高(占86.4%）、网速慢(占33.4%）是网民使用手机上网经常遇到的问题;此外，不方便、可获取信息太少等也成为网民不使用手机上网的原因。一方面是以手机为代表的移动设备的迅速发展，而另一方面却是移动商务网站上的信息贫乏和服务落后，解决方法之一就是进行Web使用挖掘，寻找移动商务客户感兴趣的内容并向其推荐。
Web使用挖掘是对用户访问Web时在服务器留下的访问记录进行挖掘，挖掘对象是在服务器上的日志信息，也称为Web日志挖掘，其目的是在海量的Web日志数据中自动、快速地发现用户的访问模式（即序列模式）。在经过对这些模式进行分析和可视化之后，可以为用户提供个性化的服务。序列模式挖掘是模式发现中运用得比较成功的方法，本文在比较几种常用的序列模式挖掘算法的基础上，对PrefixSpan算法进行了研究和优化。
二、序列模式挖掘算法
序列模式挖掘是从序列数据库中发现频繁子序列作为模式，被广泛应用于客户购买行为模式预测、网络访问模式预测、疾病治疗早期诊断、自然灾害预测及DNA序列破译等方面。序列模式最早由Agrawal R和Srikant R提出，常用算法有：
·AprioriAll算法在每一次扫描数据库时，利用上一次扫描时产生的大序列生成候选序列，并在扫描同时计算支持度，满足支持度的候选序列作为下次扫描的大序列。算法主要缺陷在于容易生成庞大的候选序列集和需要多次扫描数据库，不易发现长序列模式并导致较大开销；
·GSP（Generalized Sequential Patterns）算法类似于Apriori算法，但引入了时间约束、滑动时间窗和分类层次技术，有效减少了候选序列数量和无用模式。然而GSP算法仍然需要对序列数据库进行循环扫描；若序列数据库规模比较大，可能产生大量候选序列模式；且难以处理长序列模式的情况；
·FreeSpan算法以Apriori-based演算法为基础，但改进了产生候选序列的方式并验证是否为高频序列。该方法将搜寻区域由大范围的完整资料库改为小范围的映射资料库，产生的候选序列数量较少，也减少了扫描资料库的时间，并提升了挖掘的效率。但该算法必须完整保留与该项目有关的序列，且在产生候选序列时并不考虑顺序性，因此可能产生过多的候选序列。
本文将要论述的PrefixSpan算法与FreeSpan类似，但PrefixSpan不需要产生候选序列，从而大大缩减了检索空间；相对于原始的序列数据库而言，投影数据库的规模不断减小。PrefixSpan算法的缺点在于建立映射资料区间的成本很高，若资料项目平均分配在每个序列中，则成本便会急剧增加。下面对该算法进行介绍和优化。
三、PrefixSpan算法及其改进
1.符号化表示
序列（Sequence）:是不同项目集（ItemSet）的有序排列，一个序列S可以表示为,,为项目集（ItemSet），也称为序列S的元素。
子序列:设如果存在整数使得则称序列α为序列β的子序列，记为。
序列α在序列数据库S中的支持数:序列数据库S中包含序列 α的序列个數，记为Suuport(α)。
序列模式:给定支持度阈值ξ，如果序列α在序列数据库中的支持数不低于ξ，则称序列α为序列模式。长度为1的序列模式记为1-模式。
2.算法描述
给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式。具体算法如下：
·扫描序列数据库，生成所有长度为1的序列模式；
·根据长度为1的序列模式，生成相应的投影数据库；
·在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为1的序列模式为止。算法描述如图1所示。
例如:序列数据库S如表1所示，并设用户指定的最小支持度min_support=2。
通过对表1给出的序列数据库S进行扫描，产生长度为1的序列模式有::4，:4，
序列模式的全集是分别以，，
分别对不同的投影数据库重复上述过程，直到没有新的长度为1的序列模式产生为止。
3.PrefixSpan算法
输入:序列数据库 及最小支持度阈值min_sup
输出:所有的序列模式
方法:调用子程序PrefixSpan(<>,0,S)
在子程序PrefixSpan(α,L,S｜α)中，参数α为一个序列模式， L为序列模式α的长度，当α为空则S｜α为S，否则为α的投影数据库。子程序算法如下：
·扫描S｜α，找到满足下述要求的长度为1的序列模式b:（1） b可以添加到α的最后一个元素中并为序列模式;（2）可以α的最后一个元素并为序列模式;
·对每个生成的序列模式b，将b添加到α形成序列模式α`，并输出α`;
·对每个α`，构造α`的投影数据库S｜α`，并调用子程序PrefixSpan(α,L+1,S｜α`)
四、PrefixSpan算法改进
由于PrefixSpan算法的主要开销在于投影数据库的构造，因此对PrefixSpan算法的改进主要是从减少投影数据库入手。
1.隔层投影
使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数。
仍以前面所述的序列数据库为例，改用隔层投影，具体步骤如下：
（1)扫描序列数据库，产生所有长度为1的序列模式;
（2)再次扫描序列数据库，构造一个下三角矩阵(如表3所示），得到所有长度为2的序列模式；
（3)构造长度为2的序列模式所对应的扫描数据库，并对每个投影数据库重复上面的操作，直到没有新的序列模式产生为止。
2.伪投影
当序列数据库可以直接放入内存时，可使用伪投影代替实际的投影数据库，从而有效减少构造投影数据库的开销;同时，不需要构造所有的序列模式对应的投影数据库，可使用指向数据库中序列的指针及其偏移量作为伪投影。
例如，针对上述序列数据库构造α投影数据库时，序列S1=
五、结论
本文在比较几种常用序列模式挖掘算法的基础上，重点介绍了PrefixSpan算法并对其改进，以隔层投影代替逐层投影和伪投影方式，减少序列模式扫描过程中产生的投影数据库，从而降低系统开销，提高挖掘效率。下一步将致力于建立个性化移动商务推荐系统，更好地为移动客户服务。
参考文献:
[1]中国互联网信息中心（CNNIC）. 第19次中国互联网络发展状况统计报告[EB/OL].http://www.cnnic.net.cn/html/Dir/2007/01/22/4395.htm
[2]来玲杨宝森:用Web挖掘方法扩充大学图书馆知识库研究[J].情报杂志，2005(2）:18-20
[3]Agrawal R，Srikant R. Mining Sequential Patterns [A]. Proceedings of the International Conference on Data Engineering[C].Tapei:IEEE Computer Society，1995. 3-14
[4]Agrawal R，Srikant R. Mining Sequential Patterns：Generalizations and Performance Improvements [A]. Proceedings of the International Conference on Extending Database Technology（EDBT）. Avgnon：Lecture Notes in Computer Science，1996. 3-17
[5]Han JiaWei，PeiJian. FreeSpan：Frequent Pattern-projected Sequential Pattern Mining [A]. Proceedings of the International Conference on Knowledge Discovery and Data Mining（KDD’00）[C]. Boston：MAAC Press，2000. 35-359
[6]Pei Jian，Han Jiawei. Mining Squential Patterns by Pattern-growth：The PrefixSpan Approach [J]. IEEE Translations Knowledge and Data Engineering，2004，6（10）：1-17
注：“本文中所涉及到的圖表、注解、公式等内容请以PDF格式阅读原文。”