挖掘数据流滑动时间窗口内Top-K频繁模式

由于数据流滑动时间窗口中流数据包含模式的支持度是动态变化的,很难给出一个合适的支持度门限来挖掘数据流滑动时间窗口内的频繁模式.在研究数据流滑动时间窗口内流数据变化特点的基础上,论文提出了一种挖掘数据流滑动时间窗口内Top-k频繁模式的方法,该方法能够在保证模式挖掘误差基础上快速删除窗口内不频繁模式信息,保留重要的模式信息,并能按照支持度降序输出Top-k频繁模式.仿真实验结果表明,该算法具有较好的效率和正确性,并优于其它同类算法.     

基于项集归减的高维频繁高效用项集挖掘多目标优化方法

频繁高效用项集挖掘是数据挖掘的一项重要任务,挖掘到的项集由支持度和效用这2个指标衡量.在一系列用于解决这类问题的方法中,进化多目标方法能够提供1组高质量解以满足不同用户的需求,避免传统算法中支持度和效用的阈值难以确定的问题.但是已有多目标算法多采用0-1编码,使得决策空间的维度与数据集中项数成正比,因此,面对高维数据集会出现维度灾难问题.鉴于此,设计一种项集归减策略,通过在进化过程中不断对不重要项进行归减以减小搜索空间.基于此策略,进而提出一种基于项集归减的高维频繁高效用项集挖掘多目标优化算法(IR-MOEA),并针对可能存在的归减过度或未归减到位的个体提出基于学习的种群修复策略用以调整进化方向.此外还提出一种基于项集适应度的初始化策略,使得算法在进化初期生成利于后期进化的稀疏解.多个数据集上的实验结果表明,所提出算法优于现有的多目标优化算法,特别是在高维数据集上.     

基于矩阵的数据流Top-k频繁项集挖掘算法

传统的数据挖掘算法在挖掘频繁项集时会产生大量的冗余项集,影响挖掘效率。为此,提出一种基于矩阵的数据流Top-k频繁项集挖掘算法。引入2个0-1矩阵,即事务矩阵和二项集矩阵。采用事务矩阵表示滑动窗口模型中的事务列表,通过计算每行的支持度得到二项集矩阵。利用二项集矩阵得到候选项集,将事务矩阵中对应的行做逻辑与运算,计算出候选项集的支持度,从而得到Top-k频繁项集。把挖掘的结果存入数据字典中,当用户查询时,能够按支持度降序输出Top-k频繁项集。实验结果表明,该算法在挖掘过程中能避免冗余项集的产生,在保证正确率的前提下具有较高的时间效率。     

去冗余Top-k对比序列模式挖掘

对比序列模式可以用来表征不同类别数据集之间的差异。在生物信息、物流管理、电子商务等领域,对比序列模式有着广泛的应用。Top-k对比序列模式挖掘的目标是发现数据集中对比度最高的前k个序列模式。在Top-k对比序列模式挖掘中,可能挖掘出冗余的序列模式。目前,虽然有Top-k对比序列模式发现算法被提出,但这些算法并未考虑冗余序列模式的问题。为此,本文提出了基于广度优先生成树的去冗余Top-k对比序列模式挖掘算法BFM（breadth-first miner）。使用BFM算法可以有效地解决冗余问题,得到去冗余的Top-k对比序列模式。在BFM算法的基础上,提出了性能更好的算法PBFM（pruning breadth-first miner）。通过在真实数据集上的实验分析与对比 ,验证了本文算法的有效性。     

一种基于ZBDD结构的Top-k挖掘算法

研究微阵列数据中挖掘Top-k频繁闭合项集问题,并设计挖掘算法ZDtop。算法采用ZBDD结构压缩存储数据集,使用自顶向下深度优先搜索策略挖掘项集长度不小于给定值min_l的Top-k频繁闭合项集,并对搜索空间进行有效修剪。通过实例证明该算法是正确有效的。     

多属性约束事件序列的关联规则挖掘方法

传统序列模式挖掘算法往往忽略了序列模式本身的时间特性,所考查的序列项都是单一事件,无属性约束.提出了一种挖掘多属性约束事件序列关联规则的方法.此方法基于传统的Apriori和AprioriAU算法.考虑了应用环境下事件序列模式中事件之间的过渡时间,采用分层式挖掘思想,先挖掘频繁序列模式,然后从频繁事件序列中挖掘多属性约束项的关联规则.实例分析为挖掘带时间限多属性约束的序列模式提供了实施思路.     

基于DBP的TOp-k高效用项集挖掘算法

针对Top-k高效用项集挖掘算法在挖掘过程中忽略内存管理的问题,提出基于DBP的Top-k高效用项集挖掘算法TKBPH(Top-k buffer pool high utility itemsets mining),采用数据缓冲池(DBP)结构存储效用链表,并由索引链表记录效用链表在DBP的位置.数据缓冲池根据挖掘过程情况在数据缓冲池尾部动态插入和删除效用链表,通过索引链表直接读取效用链表避免项集搜索时频繁的比较操作,有效减少内存空间和运行时间消耗.不同类型数据集上的实验结果表明,TKBPH算法在挖掘过程中执行速度更快、内存消耗更少.     

视频目标轨迹分析的改进PrefixSpan方法

从序列模式挖掘的角度对视频目标运动轨迹的分析和应用问题进行了研究,提出了一种基于改进 PrefixSpan的频繁轨迹模式挖掘算法,并给出了基于所挖掘的频繁模式进行在线目标运动异常检测的方法。该方法对目标的运动轨迹进行量化编码,采用改进的PrefixSpan算法挖掘其中连续出现的频繁模式,通过字符串近似匹配的方法来检测当前运动轨迹所表示的目标行为是否异常。由于不需要计算两两轨迹之间的相似性,该方法可以应用于规模较大、分布模式数目难以确定场合下的视频目标轨迹分析问题。对仿真和真实场景的实验验证了该方法的有效性。     

一种基于排序的基因表达数据频繁闭合模式挖掘算法

频繁闭合模式是频繁模式的无损压缩,因此采用频繁闭合模式的挖掘来代替频繁模式挖掘,可以适当的压缩计算和存储开销。文中针对已有的面向基因表达数据集频繁闭合模式挖掘算法CARPENTER多次扫描数据集转置表带来巨大开销的缺陷,提出了基于排序的频繁闭合模式挖掘算法SFCP。在真实数据集上的实验结果表明,该算法效率比CARPENTER算法高。     

基于车牌识别流数据的车辆伴随模式发现方法

针对伴随车辆检测这一新兴的智能交通应用,在一种特殊的流式时空大数据-车牌识别流式大数据下,重新定义Platoon伴随模式,提出PlatoonFinder算法,即时地在车牌识别数据流上挖掘Platoon伴随模式.本文的主要贡献包括：第一,将Platoon伴随模式发现问题映射为数据流上的带有时空约束的频繁序列挖掘问题.与传统频繁序列挖掘算法仅考虑序列元素之间位置关系不同,本文算法能够在频繁序列挖掘的过程中有效处理序列元素之间复杂的时空约束关系;第二,本文算法融入了伪投影等性能优化技术,针对数据流的特点进行了性能优化,能够有效应对车牌识别流式大数据的速率和规模,从而实现车辆Platoon伴随模式的即时发现.通过在真实车牌识别数据集上的实验分析表明,PlatoonFinder算法的平均延时显著低于经典的Aprior和PrefixSpan等频繁模式挖掘算法,也低于真实情况下交通摄像头的车牌识别最小时间间隔.因此,本文所提出的算法可以有效的发现伴随车辆组及其移动模式.     

Mining top-k frequent patterns with combination reducing techniques

Top-k frequent pattern mining finds interesting patterns from the highest support to the k-th support. The approach can be effectively applied in numerous fields such as marketing, finance, bio-data analysis, and so on since it does not need constraints by a minimum support threshold. Top-k mining methods use the support of the k-th pattern, not a user-specified minimum support. Thus, the methods conduct mining operations based on very low supports until the k-th pattern is detected. When a low support is used in the mining process, single-paths with numerous items are generated, where the top-k mining algorithm extracts valid patterns by combining the items for each single-path. Therefore, the bigger the number of combinations is, the larger the increase in time and memory consumption is. In this paper, in order to mine top-k frequent patterns more efficiently, we consider converting patterns obtained from single-paths into composite patterns during the mining process and recovering them as the original patterns when the top-k frequent patterns are extracted. For this, we define a new concept, the composite pattern, and propose novel techniques for reducing pattern combinations in the single-path. Two algorithms are introduced in this paper, where the former is CRM (Combination Reducing method), applying our reduction manner, and the latter is CRMN (Combination Reducing method for N-itemset), considering N-itemset, i.e., patterns’ lengths. A performance evaluation shows that CRM and CRMN algorithms can efficiently reduce pattern combinations in single-paths compared to state-of-the-art algorithms. The experimental results also illustrate that our approaches have outstanding performance in terms of runtime, memory, and scalability.     

一种无阈值的频繁模式生成算法

在数据挖掘的关联规则挖掘算法中,传统的频繁模式挖掘算法需要用户指定项集的最小支持度。引入Top-k模式挖掘概念的改进算法虽然无需指定最小支持度,但仍需指定阈值k。针对上述问题,对传统挖掘算法进行改进,提出一种新的频繁模式挖掘算法(TNFP- growth)。该算法无需指定最小支持度或阈值,按照支持度降序排列进行模式挖掘,有序地返回频繁模式给用户。实验结果证明,该算法的执行效率更高,具有更强的伸缩性。     

Sliding window based weighted maximal frequent pattern mining over data streams

As data have been accumulated more quickly in recent years, corresponding databases have also become huger, and thus, general frequent pattern mining methods have been faced with limitations that do not appropriately respond to the massive data. To overcome this problem, data mining researchers have studied methods which can conduct more efficient and immediate mining tasks by scanning databases only once. Thereafter, the sliding window model, which can perform mining operations focusing on recently accumulated parts over data streams, was proposed, and a variety of mining approaches related to this have been suggested. However, it is hard to mine all of the frequent patterns in the data stream environment since generated patterns are remarkably increased as data streams are continuously extended. Thus, methods for efficiently compressing generated patterns are needed in order to solve that problem. In addition, since not only support conditions but also weight constraints expressing items’ importance are one of the important factors in the pattern mining, we need to consider them in mining process. Motivated by these issues, we propose a novel algorithm, weighted maximal frequent pattern mining over data streams based on sliding window model (WMFP-SW) to obtain weighted maximal frequent patterns reflecting recent information over data streams. Performance experiments report that MWFP-SW outperforms previous algorithms in terms of runtime, memory usage, and scalability.     

动态数据库中增量Top-k高效用模式挖掘算法

高效用模式的挖掘需要设定一个合适的阈值,而阈值设定对用户来说并非易事,阈值过小导致产生大量低效用模式,阈值过大可能导致无高效用模式生成。因而Top-k高效用模式挖掘方法被提出,k指效用值前k大的模式。并且大量的高效用挖掘研究仅针对静态数据库,但在实际应用中常常会遇到新事务的加入的情况。针对以上问题,提出了增量的Top-k高效用挖掘算法TOPK-HUP-INS。算法通过四个有效的策略,在增量数据的情况下,有效地挖掘用户所需数量的高效用模式。通过在不同数据集上的对比实验表明TOPK-HUP-INS算法在时空性能上表现优异。     

基于模式增长的高效用序列模式挖掘算法

高效用序列模式挖掘是数据挖掘领域的一项重要内容, 在生物信息学、消费行为分析等方面具有重要的应用.与传统基于频繁项模式挖掘方法不同, 高效用序列模式挖掘不仅考虑项集的内外效用, 更突出项集的时间序列含义, 计算复杂度较高.尽管已经有一定数量的算法被提出应用于解决该类问题, 挖掘算法的时空效率依然成为该领域的主要研究热点问题.鉴于此, 本文提出一个基于模式增长的高效用序列模式挖掘算法HUSP-FP.依据高效用序列项集必须满足事务效用闭包属性要求, 算法首先在去除无用项后建立全局树, 进而采用模式增长方法从全局树上获取全部高效用序列模式, 避免产生候选项集. 在实验环节与目前效率较好的HUSP-Miner、USPAN、HUS-Span三类算法进行了时空计算对比, 实验结果表明本文给出算法在较小阈值下仍能有效挖掘到相关序列模式, 并且在计算时间和空间使用效率两方面取得了较大的提高.     

基于滑动窗口的数据流闭合频繁模式的挖掘

频繁闭合模式集惟一确定频繁模式完全集并且数量小得多，然而，如何挖掘滑动窗口中的频繁闭合模式集是一个很大的挑战．根据数据流的特点，提出了一种发现滑动窗口中频繁闭合模式的新方法DS_CFI．DS_CFI算法将滑动窗口分割为若干个基本窗口，以基本窗口为更新单位。利用已有的频繁闭合模式挖掘算法计算每个基本窗口的潜在频繁闭合项集，将它们及其子集存储到一种新的数据结构DSCFI_tree中，DSCFI_tree能够增量更新，利用DSCFI_tree可以快速地挖掘滑动窗口中的所有频繁闭合模式．最后，通过实验验证了这种方法的有效性．