基于间隙约束的序列模式挖掘关键技术及其在特征提取中的应用

Sequential pattern mining with gap constraints can avoid mining numerous useless patterns and is a more flexible mining method which can easily meet users' special requirements. Pattern matching which can be used to calculate the support (or the number of occurrences) of a pattern in a sequence is one of the key issues of sequential pattern mining. Pattern matching and sequential pattern mining with gap constraints, as research hotspots, are harder to tackle. There are kinds of sequential pattern mining methods, but all of them are either anti-Apriori property or incompleteness. It is difficult to obtain good results when the frequent patterns are used in the feature selection task for the purpose of sequential classification. This project plans to investigate the following tasks..1) We develop effective algorithms to deal with approximate pattern matching under non-overlapping condition..2) We propose effective Apriori-based algorithms for solving the sequential pattern mining problems under non-overlapping condition and prove the completeness of mining algorithm. .3) We investigate effective algorithms to mine the patterns which are frequent patterns in positive class and infrequent patterns in negative class for kinds of sequential classification tasks, such as binary classification, multi-class classification and imbalanced data classification..With the successful implementation of the project, we can not only propose effective and complete mining algorithms with Apriori property for sequential pattern mining with gap constraints, but also will develop effective mining algorithms for sequential feature selection for the purpose of improving accuracy and interpretability of classifier in the future. This project will have a great significance on the fields of computing theory, data mining, bioinformatics, pattern recognition, and so on.

具有间隙约束的序列模式挖掘增加了挖掘的灵活性并能避免挖掘大量无意义的模式，其核心是一个模式匹配问题，即计算具有间隙约束的模式串在序列中的支持数或出现数。尽管目前具有间隙约束的序列模式挖掘有多种研究方法，但这些研究方法均无法兼顾Apriori性质和挖掘完备性。本项目拟对如下问题开展研究：无重叠条件近似模式匹配问题是更具有一般性的问题，对该问题拟探索高效的求解算法，以满足多种实际需要；对无重叠条件的序列模式挖掘进行研究，建立高效的挖掘算法并理论证明该算法能够兼顾Apriori性质和挖掘完备性，以提高算法的挖掘速度和挖掘准确率；探索无重叠条件的序列模式挖掘与其他类型的序列挖掘算法在生物序列挖掘结果中的优势，以扩大挖掘算法的应用领域。本项目的研究是对具有间隙约束的序列模式挖掘的核心问题进行研究，并为进一步实现序列分类的特征提取，以期为实现分类准确率的提高和分类模型的可解释性奠定基础，因此本课题将对计算理论、数据挖掘、生物信息学和模式识别等多方面具有重要意义。

本项目为一年期项目。间隙约束序列模式挖掘方法允许用户挖掘特定间隙要求的频繁模式，并在诸多应用中取得了重要应用，但是当前此类挖掘方法要么是不完备性挖掘；要么不支持Apriori性质，需要扩大搜索空间进行挖掘。针对该问题及其应用，按照预定的研究计划在如下方面取得进展：.(1)课题组研究了一种无重叠条件的间隙约束序列模式挖掘，并提出了NOSEP算法，该算法采用模式匹配策略并应用课题组提出的新型数据结构——网树结构来计算一个模式的支持度，并采用模式增长策略实现候选模式有效剪枝。课题组理论证明了NOSEP算法是一种支持Apriori性质的完备性挖掘方法，从而有效地解决当前此类研究面临的问题。在DNA序列、蛋白质序列数据库、时间序列数据库和公开的电子商务点击流数据库等多种真实实验数据上，与多种同类算法进行对比，实验结果不但验证了NOSEP算法挖掘的高效性，而且在相同条件下其可以发现更多且更加有意义的频繁模式。该成果已被IEEE汇刊录用。.(2)尽管NOSEP算法可以高效地挖掘无重叠条件的频繁模式，但是如何合理地设定频繁模式阈值难以解决。为此课题组提出高效的挖掘算法，无需设置最小支持度阈值，挖掘各个模式长度下的最频繁的k个模式。.(3)此外，NOSEP算法是针对单类样本挖掘频繁模式，为此课题组探索了针对二分类样本挖掘对比模式以形成新的特征抽取方法，以有利于分类器的分类效果的提高。.(4)为了探索学习机性能的提升，课题组还对极限学习机的学习方法进行了探索，提出了新的变步长增量极限学习机，并验证了该方法在学习效率和避免过拟合能力方面均有所提高。.受本项目资助，在一年执行期内共发表/录用4篇SCI期刊论文，其中2篇论文发表/录用在国内外学术影响力和认可度高的期刊：《IEEE Transactions on Cybernetics》和《Journal of Computer Science and Technology》（这两个期刊均为中国计算机学会推荐B类期刊，其中前者最新影响因子为7.384）。.上述成果初步表明了无重叠条件的序列模式挖掘的优势，为课题组进一步深入研究该挖掘方法及其在生物信息学和模式识别等方面的应用奠定了基础。