基于中国观鸟数据的移动对象周期模式发现

移动对象的轨迹数据中包含大量时空信息,挖掘时空信息背后隐藏的周期模式对掌握移动对象变化规律具有重要作用。为此,提出一种三阶段移动对象周期模式检测算法,通过研究轨迹点的时空特征识别并剔除重复数据,利用密度聚类算法发现轨迹点密集区域并找出密集区域中每一类移动对象的周期模式,解决移动对象轨迹周期模式挖掘中轨迹数据重复、采样数据不连续及潜在周期模式发现问题。基于2003年—2015年中国观鸟记录中心、中国观鸟年报等公开数据的实验结果表明,该算法可有效处理轨迹数据并准确挖掘出规律性移动对象的周期模式。     

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

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

一种高效的移动对象伴随模式挖掘算法

从时空维度中寻找轨迹相似、时间相近的对象集合,即挖掘移动对象的伴随模式,在基于地理位置的用户行为分析中被广泛使用.然而现有移动对象相似性挖掘算法难以处理时间连续、空间离散、时空相关并且数据量大的时空数据.针对此类数据,设计基于滑动窗口、Apriori性质和贪心选择策略的宽度优先搜索算法,对移动对象伴随模式挖掘问题进行求解.同时结合基于哈希的迭代剪枝算法和基于摘要信息的剪枝算法,设计两层剪枝算法以去除冗余的中间结果.在真实数据上的实验结果表明,与仅使用哈希迭代或摘要信息的剪枝算法相比,该算法的剪枝效率较高,并且能够稳定去除99%以上的冗余数据.     

一种基于MDL的日志序列模式挖掘算法

日志数据是互联网系统产生的过程性事件记录数据,从日志数据中挖掘出高质量序列模式可帮助工程师高效开展系统运维工作。针对传统模式挖掘算法结果冗余的问题,提出一种从时序日志序列中挖掘序列模式（DTS）的算法。DTS采用启发式思路挖掘能充分代表原序列中事件关系和时序规律的模式集合,并将最小描述长度准则应用于模式挖掘,设计一种考虑事件关系和时序关系的编码方案,以解决模式规模爆炸问题。在真实日志数据集上的实验结果表明,与SQS、CSC与ISM等序列模式挖掘算法相比,该算法能高效挖掘出含义丰富且冗余度低的序列模式。     

一种无线通信环境中用户移动模式的挖掘算法

发现无线通信环境中用户的移动模式是移动对象管理中的一个关键问题.提出一种快速挖掘该模式的算法SAM(split and merge),用来挖掘移动对象所产生有序数据集中潜在的移动模式,从而为移动对象管理提供服务.该算法将自底向上搜索和自顶向下过滤技术相结合,采用图存储压缩数据集方法,利用非频繁项集分解子图和频繁长模式过滤数据集相结合的技术,大大减少了迭代次数,降低了CPU时间.最后给出了算法性能比较和算法分析.结果表明,该算法是有效的.     

多模式移动对象不确定性轨迹预测模型

以移动设备、车辆、飞机、飓风等移动对象不确定性轨迹预测问题为背景,将大规模移动对象数据作为研究对象,以频繁轨迹模式挖掘、高斯混合回归技术为主要研究手段,提出多模式移动对象轨迹预测模型,关键技术包括:1）针对单一运动模式,提出一种基于频繁轨迹模式树FTP-tree的轨迹预测方法,利用基于密度的热点区域挖掘算法将轨迹点划分成不同的聚簇,构建轨迹频繁模式树,挖掘频繁轨迹模式预测移动对象连续运动位置.不同数据集上实验结果表明基于FTP-tree的轨迹预测算法在保证时间效率的前提下预测准确性明显优于已有预测算法.2）针对复杂多模式运动行为,利用高斯混合回归方法建模,计算不同运动模式的概率分布,将轨迹数据划分为不同分量,利用高斯过程回归预测移动对象最可能运动轨迹.实验证明,相比于基于隐马尔科夫模型和卡尔曼滤波的预测方法,所提方法具有较高的预测准确性和较低的时间代价.     

多显型疾病中致病模式和保护模式的挖掘

在多显型疾病中发现致病模式和保护模式具有很大的挑战性.以前的研究都是针对两类数据,即通过发病人群和正常人群对照得到疾病的发病模式,在多显型疾病(多种疾病或多亚型疾病)中同时发现致病模式和保护模式没有得到进一步研究.而关联规则挖掘的瓶颈在于产生大量的规则,其中有很多是冗余规则,已存在的挖掘非冗余规则算法虽然去掉了冗余规则,还是有很多规则对给定应用领域是不感兴趣的或兴趣度太低.针对这样的问题,基于统计方法定义了致病模式(vital pattern)和保护模式(protect pattern),提出了一个新的算法MVP,实现了在多显型疾病中发现致病模式和保护模式.挖掘出的模式已经被专家认可.这些规则的产生为医疗研究发展提供了精确而又非常有用的信息,被广泛应用在医疗研究中.最后基于这些规则得出分类器,实验结果验证了该算法的高效性和实用性.     

长生物数据集中频繁闭合模式挖掘算法研究

传统频繁项集挖掘算法在处理稠密或长数据集(如基因表达数据集)时效率低且产生大量冗余模式，为解决这些问题一些学者提出了闭合模式的概念和挖掘闭合模式的算法，研究证明挖掘闭合模式可以显著减少项集数量并消除大量冗余模式。该文针对生物数据特点提出了一个新颖的挖掘频繁闭合模式的算法REMFOR，该算法在闭合模式概念和行枚举思想的基础上，采用垂直数据结构和fp-tree技术，对行集建立行fp-tree来挖掘频繁闭合模式。通过实例和实验证明该算法是正确有效的。     

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

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

基于频繁项集的条件模式挖掘

在数据库挖掘中,要充分地快速地挖掘出数据库中的任意有趣模式,而现实数据挖掘查询等这种任意合成模式特别复杂,如果只利用现有的基于频繁项集算法直接进行复杂模式挖掘是困难的.为解决该问题,一种基于频繁项集的条件模式挖掘被提出.从条件模式定义,性质,条件模式挖掘算法等方面来阐述解决此类任意条件下模式挖掘的问题.该条件模式的挖掘,使得数据库进行任意模式的新知识新规律发现变得更快捷有效.在现实世界的知识挖掘中,条件模式挖掘更能贴近现实知识的发现.     

基于triemerging机制数据流滑动窗口模型的频繁模式挖掘

因树型结构的良好表达能力,在互联网中传输的信息流越来越多以树型结构形式存储。但由于流式数据的时效性,隐含在数据流中的知识会随着时间的推移发生改变。针对数据流场景下挖掘最近时间段内的频繁子树模式的问题,提出了一种滑动窗口模型下挖掘频繁子树模式算法——SWMiner算法,用于挖掘数据流下任意时刻窗口下所有的频繁子树模式。SWMiner算法使用基于前缀树的结构来压缩存储生成的树模式,并且使用trie merging机制有效地更新子树模式的支持度。实验结果表明,SWMiner算法在滑动窗口模型中的性能优于目前现有的常用算法,能有效地挖掘最近时间段内的频繁树模式。     

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.     

Novel techniques and an efficient algorithm for closed pattern mining

In this paper we show that frequent closed itemset mining and biclustering, the two most prominent application fields in pattern discovery, can be reduced to the same problem when dealing with binary (0–1) data. FCPMiner, a new powerful pattern mining method, is then introduced to mine such data efficiently. The uniqueness of the proposed method is its extendibility to non-binary data. The mining method is coupled with a novel visualization technique and a pattern aggregation method to detect the most meaningful, non-overlapping patterns. The proposed methods are rigorously tested on both synthetic and real data sets.     

一种直接生成跨层频繁模式的算法

定义了一种基于树的跨层模式信息表示，在此基础上提出了直接生成跨层频繁模式算法TBA－CLFP，它能高效地挖掘多层特别是跨层频繁模式，实验表明TBA－CLFP的时间效率与空间可伸缩性远优于Cumulate,Apriori等经典算法，TBA－CLFP可进一步推广到数量型频繁模式挖掘。     

基于Web日志的频繁偏爱路径挖掘算法

为了挖掘出更能如实反映Web用户兴趣偏好的使用模式,充分考虑了用户在页面的停留时间和点击次数两个因素,给出了频繁偏爱路径的定义,并提出了频繁偏爱路径的挖掘算法,该方法在求得最大向前路径的基础上,迭代产生更长的候选频繁偏爱路径,通过计算候选路径的频繁偏爱支持度来判断其是否为频繁偏爱路径.利用真实日志数据进行实验,实验结果表明,该算法具有较高的覆盖率和准确性.     

窗口模式下在线数据流中频繁项集的挖掘*

拟采用一种基于滑动窗模式的单遍挖掘算法,专注于处理近期数据;为了减少处理时间和占用的内存,设计了一种新的事务表示方法。通过处理这个事务的表达式,频繁项集可以被高效输出,并解决了使用基于Apriori理论的算法时,由候选频繁1-项集生成频繁2-项集时数据项顺序判断不准确问题。该算法称为MRFI-SW算法。     

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.     

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

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

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

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

Mining frequent trajectory patterns in spatial-temporal databases

In this paper, we propose an efficient graph-based mining (GBM) algorithm for mining the frequent trajectory patterns in a spatial-temporal database. The proposed method comprises two phases. First, we scan the database once to generate a mapping graph and trajectory information lists (TI-lists). Then, we traverse the mapping graph in a depth-first search manner to mine all frequent trajectory patterns in the database. By using the mapping graph and TI-lists, the GBM algorithm can localize support counting and pattern extension in a small number of TI-lists. Moreover, it utilizes the adjacency property to reduce the search space. Therefore, our proposed method can efficiently mine the frequent trajectory patterns in the database. The experimental results show that it outperforms the Apriori-based and PrefixSpan-based methods by more than one order of magnitude.