一种有效的基于图遍历的加权序列模式挖掘算法

为解决加权遍历模式挖掘问题,概括了加权有向图的种类,提出一种边加权有向图与顶点加权有向图间的变换模型,并基于该模型提出一种基于图遍历的加权序列模式挖掘算法GTWSPMiner.该算法根据遍历模式中的项的连续性特点,采用一种加权前缀投影序列模式增长方法,将原挖掘序列数据库的任务分解成一组挖掘局部投影数据库的小任务.对比实验结果表明"该算法能快速有效地挖掘加权频繁遍历模式.

     

利用局部图关联信息挖掘加权频繁模式*

遍历模式数据挖掘方法已经在多种应用中被提出,传统的遍历模式挖掘仅仅考虑了非加权遍历。为解决加权遍历模式挖掘问题,首先提出了一种从EWDG（边加权有向图）到VWDG（顶点加权有向图）的变换模型;基于这种模型,提出了在具有层次特性的局部图遍历中,挖掘加权频繁模式的LGTWFPMiner(局部图遍历加权频繁模式挖掘法)及其支持度/权值界的局部评估方法。针对合成数据的实验结果表明该算法能够有效地进行基于图遍历的加权频繁模式挖掘。     

基于加权有向图的权频繁模式挖掘算法

为解决加权图遍历模式的挖掘问题,提出了一种从加权有向图中挖掘加权频繁模式算法.在该算法中,利用图全局拓扑结构和顶点权值信息评估遍历模式的权支持度,从而将剪枝问题转化成模式可扩展性问题,再利用可扩展模式产生候选模式集.本算法把图,顶点权值融合进来,提高了挖掘结果的准确度.实验结果表明,该算法可以有效地进行基于加权向图的权频繁模式挖掘.     

一种改进的加权序列模式挖掘算法

在加权序列模式挖掘中,基于候选码生成-测试方法的MWSP是目前应用性最好的算法之一,然而在挖掘过程中容易出现候选组合爆炸的情况,为此文章提出了一种高效的加权序列模式挖掘算法（PWSM）。PWSM算法引入k-最小加权支持数概念并利用前缀投影数据库原理有效地避免了候选组合爆炸的发生,并且在挖掘的过程中充分利用最小加权支持数,再次对算法进行优化。实验表明,该算法较MWSP算法能更加有效地从序列数据库中挖掘加权序列模式。     

基于序列树的增量式序列模式更新算法

在序列数据库更新时,现有的增量式序列模式挖掘算法只提到序列的插入操作和序列的扩展操作两种情况,没有针对序列删除操作。提出了一种基于序列树的增量式序列模式更新算法（ISPST）。当数据库更新时,ISPST算法只需要对与删除序列有关的序列构造投影数据库,实现对序列树的更新操作,通过深度优先遍历序列树得到更新后数据库中的所有序列模式。实验结果表明,当支持度发生变化时,ISPST算法在时间性能上优于PrefixSpan算法和IncSpan算法。     

一种新的Web频繁访问模式挖掘算法

提出了一种基于有向图的从Web日志中挖掘用户频繁访问模式的新算法,与传统使用基于关联规则挖掘的序列模式挖掘技术相比,本算法采用有向图来记录Web访问序列和它的计数,在挖掘过程中只需要扫描数据库一次,不产生数量庞大的候选模式,即可直接挖掘出所有的Web频繁访问路径,大大提高了Web访问模式的发现效率。     

基于改进PrefixSpan的序列模式挖掘算法

针对PrefixSpan算法构造投影数据库开销大的问题,提出一种基于改进PrefixSpan的序列模式挖掘算法SPMIP。该方法通过添加剪枝步和减少某些特定序列模式生成过程的扫描,来减少投影数据库的规模及扫描投影数据库的时间,提高算法效率,并最终得到需要的序列模式。实验结果证明在获得序列模式不受影响情况下,SPMIP算法比PrefixSpan算法效率更高。     

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

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

一种分布式序列模式挖掘算法

针对分布式环境下的序列模式挖掘问题,提出了一种分布式序列模式挖掘(DSPM)算法。DSPM以PrefixSpan算法为基础,使用抽样检测技术平衡了任务负载,将挖掘任务分解后分配到多台计算机上以多进程、多线程并行执行。另外采用了伪投影技术来降低生成投影数据库的开销。实验结果表明,DSPM算法能够快速有效地挖掘分布式环境下的全局序列模式。     

基于完井业务流程的加权序列模式挖掘算法研究

针对完井移动平台Web访问模式中用户对整体上符合完井业务流程习惯的序列模式更加感兴趣的特点,提出一种基于完井业务流程的加权序列模式挖掘算法.通过对完井业务流程模型和完井Web访问日志作分析,确定完井业务依赖强度计算模型并作为序列的权重,同时在加权挖掘的过程中采用k-最小加权支持数技术,对PrefixSpan算法进行改进.该算法在加权挖掘的过程中可以舍弃一大批不满足业务流程的访问序列,有效地避免候选组合爆炸的发生.实验表明该算法能快速地挖掘出有意义的完井访问序列模式.     

用户访问兴趣路径挖掘方法

针对当前挖掘用户访问模式算法仅将频繁访问路径作为用户浏览兴趣路径的问题,依据使用Web日志挖掘用户兴趣页面时,通过引入页面信息量参数,综合考虑页面访问次数、浏览时间和页面信息量大小来定义用户兴趣度,提出了基于兴趣度的用户访问模式挖掘算法。实验证明该算法是有效的,在用户浏览兴趣度量方面比当前的频繁访问路径挖掘算法更准确。     

基于图结构的候选序列生成算法

先生成候选序列再判断候选序列是否为频繁序列，最后获得频繁序列是序列数据挖掘中基于候选序列挖掘算法的一般结构，如Apriori类算法，GSP算法，SPADE算法等。因此，研究候选序列生成算法具有普遍意义。本文首先研究了序列数据集(序列数据库)与图结构间的关系，证明了一个序列是频繁序列的必要条件是该序列对应于一个完全子图。以此为基础提出了基于图结构的候选序列生成算法，文中给出了算法正确性证明。在T25110D10K和T25120D100K数据集上的挖掘实验表明在本文提出的候选序列生成算法上进行挖掘比用Apriori算法进行挖掘的效率更高。     

赋权有向图的最小生成树算法

针对赋权有向图最小生成树问题存在可行解的情况,根据树节点入度最大值为1的性质,提出赋权有向图最小生成树性质。采用反证法,调整生成树根节点到弧头的路径来证明赋权有向图MST性质的正确性。基于赋权有向图MST性质,给出改进的Prim和Kruskal算法及其时间复杂度分析。实验给出构造某赋权有向图实例最小生成树的具体步骤,表明这2种算法能正确有效地构造赋权有向图最小生成树。     

Analyzing Sequential Patterns in Retail Databases

Finding correlated sequential patterns in large sequence databases is one of the essential tasks in data mining since a huge number of sequential patterns are usually mined, but it is hard to find sequential patterns with the correlation. According to the requirement of real applications, the needed data analysis should be different. In previous mining approaches, after mining the sequential patterns, sequential patterns with the weak affinity are found even with a high minimum support. In this paper, a new framework is suggested for mining weighted support affinity patterns in which an objective measure, sequential ws-confidence is developed to detect correlated sequential patterns with weighted support affinity patterns. To efficiently prune the weak affinity patterns, it is proved that ws-confidence measure satisfies the anti-monotone and cross weighted support properties which can be applied to eliminate sequential patterns with dissimilar weighted support levels. Based on the framework, a weighted support affinity pattern mining algorithm （WSMiner） is suggested. The performance study shows that WSMiner is efficient and scalable for mining weighted support affinity patterns.     

基于Dandelion编码生成有界树宽CP-nets

针对条件偏好网络（CP-nets）图模型在进行推理运算时的高时间复杂度的问题,提出了一种基于Dandelion编码生成有界树宽的CP-nets（BTW-CP-nets Gen）算法。首先,通过Dandelion编码与树宽为k的树结构（k-tree）之间的双向映射原理推导出Dandelion编码与k-tree之间的解码与编码算法,实现编码与树结构的一对一映射;其次,利用k-tree来约束CP-nets结构的树宽,并利用k-tree的特征树得到了CP-nets的有向无环图结构;最后,利用离散多值函数的双射计算出各CP-nets结构节点的条件偏好表,然后针对生成的有界树宽CP-nets进行占优查询检测。理论分析和实验数据表明,与Pruffer编码生成k-tree（Pruffer code）算法相比,BTW-CP-nets Gen算法的运行时间在生成简单结构和复杂结构时的下降幅度分别为21.1%和30.5%;而BTW-CP-nets Gen算法所生成的图模型在进行占优查询时的节点遍历比在简单结构和复杂结构上分别提高了18.48%和29.03%。BTW-CP-nets Gen算法在更短的时间内,占优查询时遍历的节点率更高。可见,BTW-CP-nets Gen算法在图模型的推理中能够有效提高算法效率。     

从图数据库中挖掘频繁跳跃模式

很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保留在挖掘结果中.此外,跳跃模式还具有抗噪声干扰能力强等优点.然而,由于跳跃模式不具有反单调性质,挖掘它们非常具有挑战性.通过研究跳跃模式自身的特性,提出了两种新的裁剪技术:基于内扩展的裁剪和基于外扩展的裁剪.在此基础上又给出了一种高效的挖掘算法GraphJP(an algorithm for mining jump patterns from graph databases).另外,还严格证明了裁剪技术和算法GraphJP的正确性.实验结果表明,所提出的裁剪技术能够有效地裁剪图模式搜索空间,算法GraphJP是高效、可扩展的.     

基于加权序列模式的推荐算法研究

由于考虑了用户的访问顺序,基于序列模式的推荐方法正在成为推荐系统研究的热点之一。为提高推荐结果的个性化程度,提出了一种基于加权序列模式的推荐算法PRWSP。首先,给出了新的加权序列模式模型,该模型在设置权重时充分考虑了项目在不同序列中的不同重要程度。其次,通过近似估计序列权重的方式,论证了挖掘加权序列模式时同样满足反单调性,从而约简了搜索空间。最后,定义了序列模式匹配程度的度量标准。实验结果表明,PRWSP算法具有较高的挖掘效率和推荐精度。     

Efficient data mining for calling path patterns in GSM networks

In this paper, we explore a new data mining capability that involves mining calling path patterns in global system for mobile communication (GSM) networks. Our proposed method consists of two phases. First, we devise a data structure to convert the original calling paths in the log file into a frequent calling path graph. Second, we design an algorithm to mine the calling path patterns from the frequent calling path graph obtained. By using the frequent calling path graph to mine the calling path patterns, our proposed algorithm does not generate unnecessary candidate patterns and requires less database scans. If the corresponding calling path graph of the GSM network can be fitted in the main memory, our proposed algorithm scans the database only once. Otherwise, the cellular structure of the GSM network is divided into several partitions so that the corresponding calling path sub-graph of each partition can be fitted in the main memory. The number of database scans for this case is equal to the number of partitioned sub-graphs. Therefore, our proposed algorithm is more efficient than the PrefixSpan and a priori-like approaches. The experimental results show that our proposed algorithm outperforms the a priori-like and PrefixSpan approaches by several orders of magnitude.