用户行为模式挖掘问题的研究

在软件可用性测试中,分析用户行为模式是一个关键的问题。为解决具有序列长度长、以序列片断为支持度计算依据等特点的用户行为模式挖掘问题,提出了一种有效的基于前缀树的频繁事件序列扩展方法,给出了比特图索引表的构造、事件扩展、事务扩展以及支持度计算的算法。使频繁事件序列能够简单快速地被确定。     

一种用户行为模式的挖掘算法

最大频繁事件序列挖掘是数据挖掘中重要的研究课题之一。该文提出了一种新的挖掘用户行为模式的算法。该算法采用位图索引表的数据格式，使用一种有效的基于前缀树的频繁事件序列扩展方法，结合有效的剪枝技术，明显地加速了最大频繁事件序列的生成。     

具有周期间隙约束的负序列模式挖掘

间隙约束的序列模式挖掘是一种特殊形式的序列模式挖掘方法，该方法能够揭示一定间隔下的频繁出现(发生)的子序列。但当前间隙约束的序列模式挖掘方法只关注正序列模式的挖掘，忽略了事件中的缺失行为。为解决该问题，探索了周期间隙约束的负序列模式(Negative Sequential Pattern with Periodic Gap Constraints, NSPG)挖掘方法，该方法能够更灵活地反映元素与元素之间的关系。为高效求解NSPG挖掘问题，提出了NSPG-INtree(Incomplete Nettrees)算法，该算法主要包括两个步骤：候选模式生成和支持度计算。在候选模式生成方面，为了减少候选模式的数量，该算法采用模式连接策略；在支持度计算方面，为了提高模式支持度计算效率并减少空间消耗，该算法采用不完整网树结构计算模式支持度。实验结果表明，NSPG-INtree算法不仅具有较高的挖掘效率，而且能同时挖掘间隙约束的正序列模式和负序列模式。与其他间隙约束的序列模式挖掘算法相比，NSPG-INtree能够多发现209%～352%的模式；与不同策略的对比算法相比，NSPG-INtree能够缩...     

使用序列模式精简基挖掘序列模式

传统的序列模式挖掘方法在挖掘由短的频繁序列模式组成的数据库时有良好的性能．但在挖掘长的序列模式或支持度阈值很低时，这些方法可能遇到固有的困难，因为产生的频繁序列模式的数量经常太大．在许多情况下，用户可能只需要那些覆盖许多短模式的长模式．此外，在很多应用中，只要得到产生的频繁序列模式的近似支持度就已足够，而不需要它们的精确支持度．介绍了能将误差控制在确定范围内的频繁序列模式精简基的概念，并开发了一个挖掘这种序列模式精简基的算法．实验结果显示计算频繁序列模式精简基是很有前途的．     

多支持度下用户行为序列模式挖掘方法研究

针对现有用户行为序列模式挖掘方法的单一支持度局限性问题,提出一种基于前缀树结构的多支持度序列模式挖掘方法。设计一种多支持度条件下的前缀树结构MSLP-tree,并基于此结构提出一种序列模式增长算法MSLP-growth。通过考虑各数据项不同最小支持度,获取更精确的频繁序列模式,在确保挖掘结果的准确性和完整性的前提下,大大压缩搜索空间,缩短挖掘时间。实验结果表明,相较于MS-GSP算法,MSLP-growth算法具有更高的挖掘效率和可扩展性。     

融合多种支持度定义的频繁情节挖掘算法

事件序列中蕴藏的频繁情节刻画了用户或系统的行为规律.现有的频繁情节挖掘算法在各自支持度定义下具有较好的挖掘效果，但在支持度定义发生变化时却很难甚至无法直接挖掘频繁情节.针对用户多变的支持度定义需求，提出了一种频繁情节挖掘算法FEM-DFS（frequent episode mining-depth first search）.该算法通过单遍扫描事件序列，以深度优先搜索方式来发现频繁情节，以共享前/后缀树来存储频繁情节，以单调性、前缀单调性或后缀单调性来压缩频繁情节的搜索空间.实验评估证实了所提出算法的有效性.     

带有间隔约束的多序列模式挖掘

研究这样一个问题：给定多序列、支持度阈值和间隔约束,从多序列中挖掘所有出现次数不小于支持度阈值的频繁序列模式,这里要求模式中任意两个相邻元素在序列中的出现都要满足用户自定义的间隔约束,并且模式在序列中的出现要满足one-off条件。在解决该问题上,已有算法M-OneOffMine在计算模式的支持度时,只考虑模式的每个字符在序列中的首次出现,导致计算的模式支持度远小于其真实支持度,以致许多频繁的模式没有被挖掘出来。为此,设计了一个有效的带有间隔约束的多序列模式挖掘算法--MMSP算法：首先,通过采用二维表保存模式的候选位置;然后,根据候选位置采用最左最优的思想选择匹配位置。通过生物DNA序列进行实验,多序列中元素序列数目不变而序列长度变化时,MMSP挖掘出的频繁模式总数是同类算法M-OneOffMine的3.23倍;在元素序列个数变化时,MMSP挖掘出的频繁模式个数平均是M-OneOffMine的4.11倍;这两种情况下MMSP都有更好的时间性能。在模式长度变化时,MMSP挖掘出的频繁模式个数分别平均是M-OneOffMine的2.21倍和MPP的5.24倍。同时还验证了M-OneOffMine挖掘到的模式是MMSP挖掘到的频繁的子集。实验结果表明,MMSP算法不仅可以挖掘到更多的频繁模式,而且时间花费更少,更适合于实际的应用。     

一种改进的PrefixSpan算法及其在Web用户行为模式挖掘中的应用

序列模式挖掘是从序列数据库中挖掘相对时间或其他模式出现频率高的模式。针对PrefixSpan算法构造投影数据库时开销巨大、扫描效率不高的问题,通过以序列扩展代替项集进行扩展、放弃挖掘序列数小于阈值min＿support的投影数据库以及直接递归局部频繁项等方式进行改进,并将改进方法应用于Web用户行为模式挖掘中,对日志记录中的规律进行分析和研究。实验分析表明,相比PrefixSpan算法,该改进算法在算法效率方面有一定的提高。     

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

为解决频繁轨迹模式挖掘中单一最小支持度带来的问题,提出一种多最小支持度的频繁序列挖掘算法,根据获取的用户历史轨迹数据确定用户多最小支持度获取模型。由于仅通过Prefix Span算法挖掘出用户的历史频繁轨迹模式,无法了解用户在一段时间内的地点偏好变化,通过动态加权的方式结合之前挖掘出的用户频繁轨迹模式得到用户在不同时期的地点偏好变化,利用序列压缩和序列匹配减少用户频繁轨迹模式的存储空间。通过实例挖掘,验证了改进算法的有效性。     

基于频繁序列树的交互式序列模式挖掘算法

为了减少在序列模式挖掘过程中由于重复运行挖掘算法而产生的时空消耗,提出了一种基于频繁序列树的交互式序列模式挖掘算法(ISPM). ISPM算法采用频繁序列树作为序列存储结构,频繁序列树中存储数据库中满足频繁序列树支持度阈值的所有序列模式及其支持度信息.当支持度发生变化时,通过减少本次挖掘所要构造投影数据库的频繁项的数量来缩减投影数据库的规模,从而减少时空消耗.实验结果表明,ISPM算法在时间性能上优于PrefixSpan算法和Inc-Span算法