基于跳跃显露模式挖掘算法的癌症分类

分类问题是数据挖掘中的一项重要课题,然而目前对于癌症数据的分类研究还相对较少。近年来提出的强跳跃显露模式SJEP是一种具有很强区分能力的新模式,对于癌症数据的分类具有明显的优势。为了使癌症数据的分类精确度得以进一步提升,本文引入集成学习的思想,对原有的Boosting算法做出一些改进,并将改进后的Boosting算法与SP-树分类算法相结合,提出一种以SP-树分类算法作为基学习算法的SP_Boost算法。     

基于位置信息的显露序列模式挖掘研究

显露序列因为具有强区分能力,常被用来构建有效的分类器。当前算法大多关注序列模式的支持度或出现次数,而忽略序列模式在序列中的出现位置,这将导致一些重要的信息丢失。为此,提出一种带有局部位置信息的显露序列模式,并给出位置显露序列模式挖掘算法。该算法基于出现次数框架,结合后缀树,省略了候选模式的生成与选择步骤,能够快速有效地挖掘出位置显露序列模式。实验结果表明,采用位置显露序列模式构建的分类器在平均分类准确度上高于传统的显露序列模式挖掘算法。     

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

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

基于跳跃频繁模式的中文文本分类

基于频繁模式的文本关联分类方法与基于跳跃显露模式的文本分类方法各具优点与不足。本文集成这两种方法．提出基于频繁跳跃模式和非频繁跳跃模式的分类方法。实验结果表明，该方法的分类精度高于关联分类方法而召回率和分类速度优于基于跳跃显露模式的分类方法。有效弥补了两种分类方法的不足。     

改进的频繁模式挖掘算法

为解决传统频繁模式挖掘算法效率不高的问题,提出了一种改进的基于FP-tree （Frequent pattern tree）的Apriori频繁模式挖掘算法.首先,在Apriori算法的连接步加入连接预处理过程;其次,对CP-tree （Compact Pattern tree）进行扩展,构造了一个新的树结构ECP-tree （Extension of Compact Pattern tree）,新的树结构只需对数据库进行一次扫描就能构造出一棵紧凑的前缀树,且支持交互式挖掘与增量挖掘;然后,将改进点与APFT算法结合,用于挖掘频繁模式;最后,使用UCI数据库中两个数据集进行实验.实验结果表明：改进算法具有较高的挖掘效率,频繁模式挖掘速度显著提升.     

一种挖掘Web用户访问模式的新方法MFP

针对用户访问模式（User Access Pattern）问题，首次提出了一种新的挖掘方法MFP（Maximal Frequent Path），该方法采用两种兴趣度的度量标准（在考虑了用户覆盖面的同时，又考虑了个人贡献因素）．MFP方法提高了挖掘算法的精度，增加了挖掘算法的可用性，能挖掘出比其它方法更具有普遍意义的模式．并通过理论推导和实验验证了它的有效性．     

增量式隐私保护频繁模式挖掘算法

针对多数隐私保护的频繁模式挖掘算法需要多次数据库扫描以及计数时需要进行多次比较的不足，提出了一种增量的基于位图的部分隐藏随机化回答（IBRRPH）算法。首先，引入bitmap表示数据库中的事务，采用"位与"操作有效提高支持度的计算速度；其次，通过分析增量访问关系，引入增量更新模型，使得在数据增量更新时频繁模式挖掘最大限度地利用了之前挖掘结果。针对增量分别为1000至40000，与顾铖等提出的算法（顾铖，朱保平，张金康.一种改进的隐私保护关联规则挖掘算法.南京航空航天大学学报，2015，47（1）：119-124）进行了对比测试实验。实验结果表明，与顾铖等提出的算法相比，IBRRPH算法的效率提高幅度超过21%。     

基于位编码链表的快速频繁模式挖掘算法研究

多数基于FP-growth思想的频繁模式挖掘算法存在建树过程复杂、支持度计算繁琐的问题。针对这些问题，提出一种基于位编码链表（Bitmap-Code List，BC-List）的频繁项集挖掘算法（BC-List Frequent Itemsets Mining，BCLFIM）。该算法首先采用基于位图表示的节点编码模型生成位图树（BC-tree），以BC-tree的节点信息作为数据结构通过按位运算来快速获取BC-List的节点集，避免了复杂的交集运算，提高了连接效率；其次通过使用超集等价和支持度计数剪枝策略，缩小了挖掘频繁模式的搜索空间。实验结果证明，该算法相比于FIN算法和DFIN算法具有更快的挖掘速度。     

高效的稀有序列模式挖掘方法

序列模式挖掘是数据挖掘领域的一个经典研究问题,目前的研究主要关注于频繁序列模式的挖掘。但是不频繁的序列模式,即“稀有序列模式（rare sequential pattern,RSP）”也可能蕴含着一些不寻常的规律,具有更高的挖掘价值。因此,给出了稀有序列模式挖掘的定义,并且提出了两种逐层挖掘稀有序列模式完全集的方法。为克服挖掘稀有序列模式全集时产生的组合爆炸问题,提出了一种高效的基于二分查找的算法来挖掘“最小稀有序列模式（minimal rare sequential pattern,MRSP）”全集,它包含了稀有序列模式全集的完整信息。通过实验验证了提出的算法可以有效地挖掘稀有序列模式。     

基于长度约束的蝙蝠高效用项集挖掘算法

为了挖掘满足用户特殊需求，如含指定项目数量的高效用项集（HUI），提出一种基于长度约束的蝙蝠高效用项集挖掘算法（HUIM-LC-BA）。该算法融合蝙蝠算法（BA）和长度约束构建高效用项集挖掘（HUIM）模型，首先将数据库转换为位图矩阵，实现高效的效用计算和数据库扫描；其次，采用重新定义的事务加权效用（RTWU）策略缩减搜索空间；最后，对项集进行长度修剪，使用深度优先搜索和轮盘赌注选择法确定修剪项目。在4个数据集的仿真实验中，当最大长度为6时，与HUIM-BA相比，HUIM-LC-BA挖掘的模式数量分别减少了91%、98%、99%与97%，同时运行时间也少于HUIM-BA；且在不同长度约束条件下，与FHM+(Faster High-utility itemset Ming plus)算法相比运行时间更稳定。实验结果表明，HUIM-LC-BA能有效挖掘具有长度约束的HUI，并减少挖掘模式的数量。     

基于增强显现模式的癌症分类算法

针对提取显现模式时在小样本情况下频率近似于概率的缺陷,在衡量分类信息能力熵的计算中引入贝叶斯方法估计概率P(Ci, Sj),提高熵的可靠度,在此基础上提取癌症表达中的增强显现模式,提出2种基于增强显现模式的癌症分类算法。在急性白血病数据集上进行实验,结果表明,该算法能提高癌症检测的正确率。     

Fast discovery and the generalization of strong jumping emerging patterns for building compact and accurate classifiers

Classification of large data sets is an important data mining problem that has wide applications. Jumping emerging patterns (JEPs) are those itemsets whose supports increase abruptly from zero in one data set to nonzero in another data set. In this paper, we propose a fast, accurate, and less complex classifier based on a subset of JEPs, called strong jumping emerging patterns (SJEPs). The support constraint of SJEP removes potentially less useful JEPs while retaining those with high discriminating power. Previous algorithms based on the manipulation of border as well as consEPMiner cannot directly mine SJEPs. In this paper, we present a new tree-based algorithm for their efficient discovery. Experimental results show that: 1) the training of our classifier is typically 10 times faster than earlier approaches, 2) our classifier uses much fewer patterns than the JEP-classifier to achieve a similar (and, often, improved) accuracy, and 3) in many cases, it is superior to other state-of-the-art classification systems such as naive Bayes, CBA, C4.5, and bagged and boosted versions of C4.5. We argue that SJEPs are high-quality patterns which possess the most differentiating power. As a consequence, they represent sufficient information for the construction of accurate classifiers. In addition, we generalize these patterns by introducing noise-tolerant emerging patterns (NEPs) and generalized noise-tolerant emerging patterns (GNEPs). Our tree-based algorithms can be adopted to easily discover these variations. We experimentally demonstrate that SJEPs, NEPs, and GNEPs are extremely useful for building effective classifiers that can deal well with noise.     

一种改进的字符图像二值化算法

随着数字图像处理和模式识别技术的发展,字符识别技术得到了广泛的应用。二值化技术作为字符预处理的一个重要环节,对后续的字符分割和特征提取有着很大的影响。本文针对字符图像的特点,提出了一种改进的基于直方图特征和形态学处理的Otsu二值化算法。仿真表明,该算法在减少运算量的同时,可以有效处理字符笔划残缺造成的干扰,并增强字符的连通性。     

A sliding windows based dual support framework for discovering emerging trends from temporal data

In this paper we present the dual support Apriori for temporal data (DSAT) algorithm. This is a novel technique for discovering jumping and emerging patterns (JEPs) from time series data using a sliding window technique. Our approach is particularly effective when performing trend analysis in order to explore the itemset variations over time. Our proposed framework is different from the previous work on JEP in that we do not rely on itemsets borders with a constrained search space. DSAT exploits previously mined time stamped data by using a sliding window concept, thus requiring less memory, minimum computational cost and very low dataset accesses. DSAT discovers all JEPs, as in “naïve” approaches, but utilises less memory and scales linearly with large datasets sets as demonstrated in the experimental section.     

基于均匀尺度不变局部三元模式的背景建模及其在Intel HD显卡上的并行实现

针对尺度不变局部三元模式(SILTP)背景建模算法复杂度较高、计算速度较慢,不利于高速视频处理的问题,提出了一种新的均匀尺度不变局部三元模式(USILTP)背景建模并行算法。首先,通过规范SILTP编码的跳变次数得到USILTP纹理特征,实现了SILTP特征降维;其次,设计并实现基于英特尔核芯显卡(Intel HD)及开放式计算语言(OpenCL)的USILTP背景建模并行算法,进一步加速了USILTP背景建模算法;最后,通过融合多颜色通道模型结果,优化了USILTP背景建模算法的前景效果。实验结果表明,在Intel HD 4600上处理320×240分辨率的视频,该算法将速度提升至98 frame/s,比SILTP背景建模算法快4倍;在前景检测方面,该算法在背景公开数据库上的性能比SILTP背景建模算法提升了2.1%。     

有效的不确定数据概率频繁项集挖掘算法

针对已有概率频繁项集挖掘算法采用模式增长的方式构建树时产生大量树节点,导致内存空间占用较大以及发现概率频繁项集效率低等问题,提出了改进的不确定数据频繁模式增长(PUFP-Growth)算法。该算法通过逐条读取不确定事务数据库中数据,构造类似频繁模式树(FP-Tree)的紧凑树结构,同时更新项头表中保存所有尾节点相同项集的期望值的动态数组。当所有事务数据插入到改进的不确定数据频繁模式树(PUFP-Tree)中以后,通过遍历数组得到所有的概率频繁项集。最后通过实验结果和理论分析表明:PUFP-Growth算法可以有效地发现概率频繁项集;与不确定数据频繁模式增长(UF-Growth)算法和压缩的不确定频繁模式挖掘(CUFP-Mine)算法相比,提出的PUFP-Growth算法能够提高不确定数据概率频繁项集挖掘的效率,并且减少了内存空间的使用。     

成对旋转不变的共生自适应完全局部三值模式

针对成对旋转不变的共生局部二值模式（PRICoLBP）旋转不变性较差及其相关改进算法EPRICoELBP对光照变化和噪声干扰较为敏感的问题,提出了一种增强成对旋转不变的共生自适应阈值完全局部三值模式。通过自适应阈值局部三值模式（ALTP）将图像分成Upper和Lower模式;分别在两种模式中找出像素点LBP特征极大、极小值对应的邻域起始编码点,利用中心像素点与其LBP特征极大、极小值对应的邻域起始编码点作为方向矢量,来确定中心像素点的上下文共生点对;利用自适应阈值完全局部三值模式（ACLTP）提取Upper和Lower模式中共生点对的局部纹理信息;联合上下文共生点对的特征直方图训练卡方核支持向量机,进行纹理图像识别检测。在应用广泛的Brodatz、Outex（TC10、TC12-h、TC12-t、TC14）、CUReT、KTH_TIPS、UIUC标准纹理库中,该算法相较于原始的PRICoLBP算法和其他算法在分类准确率上均有一定的提升,且在添加了高斯噪声和椒盐噪声的KTH_TIPS纹理库中,该算法依旧保持了较高的分类准确率。实验结果表明,该算法对旋转、光照变化和噪声干扰具有较强的鲁棒性。