论文部分内容阅读
随着社会经济与科学技术的发展，信息技术得到了广泛的应用，许多领域积累了大量的数据，迫切需要一种新技术与工具来帮助人们快速地从海量的数据中找出重要的有价值的信息，数据挖掘技术就是基于这种背景应运而生。而作为数据挖掘的一个重要研究内容一序列模式挖掘，已经得到了许多研究，提出了许多有关序列模式挖掘的算法，如AprioriAll算法、SPADE算法以及PrifixSpan算法等等，而且序列模式挖掘在许多领域得到了广泛的应用，如顾客购买行为分析、Web访问模式分析以及DNA序列分析等等。
但是，目前已经提出的许多序列模式挖掘算法仅仅是挖掘出满足用户指定的最小支持度minsup的序列模式，并没有考虑序列模式的重要性，即虽算法挖掘出的所有的序列模式都满足用户指定最小支持度minsup，但用户可能更关注比较重要的序列模式，它们虽然不能满足用户指定最小支持度，但是这些序列对用户来说比较有价值；相反地，有些序列模式可能对用户来说重要程度并不是很大，并不需要挖掘，这就需要算法能够自适应地调整以挖掘出符合用户需求的序列模式，但已提出的挖掘算法没有考虑这种特征，无法挖掘出这样的序列模式。
由于形式概念分析中的概念格模型只需访问一次数据库就可构建成功，并且它的知识与层次表达能力强，将序列引入概念格中，只需存储最大公共子序列，减少了冗余序列的产生。为此，本文对序列模式挖掘与模糊概念格的结合进行了系统的研究，主要研究成果如下：
(1)针对目前概念格构造算法在较大规模稀疏的数据集或分布式的数据集上，生成概念时仍然需要耗费大量的时间，本文提出了一种基于IE-Tree(Intension andExtension Tree)与特征空间划分的概念生成算法IETreeCS(Concept Set based onIntension and Extension Tree)。IETreeCS算法首先将形式背景转为IE-Tree，减少了数据集的存储量；然后该算法在IE-Tree的基础上进行了特征空间的描述与划分，最后给出了完整的IETreeCS算法。实验结果表明该算法在较大规模稀疏的数据集或分布式的数据集上性能优越，有明显地提高。同时，IETreeCS算法也为序列模糊概念格的构建提供了算法支持。
(2)为了组织与挖掘有价值的满足多需求的序列模式，本文提出了一种序列模糊概念格模型，并给出了序列模糊概念格的构造算法SeqFuzCL(Sequence FuzzyConcept Lattice)。在传统的模糊形式背景的基础上，本文将其在序列上进行了扩展，定义了序列模糊形式背景；利用扩展的序列模糊形式背景，定义了概念的Galois闭包连接、序列模糊概念及其格结构，最后给出了序列模糊概念格的构建算法SeqFuzCL。通过实验表明，序列模糊概念格模型不仅可以方便有效的组织自适应序列模式，在时间与空间上都具有良好的性能，而且还可以在序列模糊概念格上挖掘传统意义下的序列模式，同时，为进一步挖掘自适应序列模式提供了理论支持。
(3)由于在实际应用中，许多大型数据库是以分布式的形式存在的，为了能够有效与方便地处理分布环境下的序列，本文在序列模糊概念格的基础上提出了分布序列模糊概念格模型及其构建算法DSeqFuzCL(Distributed Sequence FuzzyConcept Lattice)。在分布序列模糊概念格模型上，不仅可以有效挖掘分布序列模式，而且还可以挖掘满足用户多需求的特殊分布序列模式，如分布加权序列模式等。通过实验证明，本文提出的分布序列模糊概念格构建算法DSeqFuzCL具有良好的时间与空间性能。
(4)在序列模糊概念格的基础上，利用序列权重与序列的重要度阈值，本文定义了序列自适应系数及其自适应序列模式SASP(Self-adaptive Sequence Pattern)，给出了基于序列模糊格的自适应序列模式的发现算法SASeqP(Self-adaptiveSequence Pattern)。它可以自适应地调整用户指定的最小支持度minsup，以挖掘出满足用户需求的特别有价值的序列模式。