论文部分内容阅读
频繁模式挖掘是一类基本的数据挖掘问题,可以广泛应用于关联规则分析、相关性分析、孤立点分析、分类和聚类等多种数据挖掘任务,是一个具有重要理论意义和广阔应用前景的课题。本文对频繁模式挖掘问题进行了深入研究和探索,主要内容如下:1.对频繁序列挖掘问题进行深入研究,探讨典型的挖掘算法—GSP、SPADE、SPAM、PrefixSpan,在此基础上,应用新的扩展策略,提出了一种全新的、高效的频繁序列挖掘算法—FINDER。该算法采用深度优先策略枚举搜索空间,使用垂直位图与水平位图向量格式表示项集、事务数据库、序列,摒弃了以往算法所采用的复杂的散列技术和数据库的多遍扫描。FINDER算法采用频繁项集序列扩展策略,最大限度地减少非频繁扩展。最后采用权威数据集生成程序生成测试数据集,验证算法的正确性与有效性。新算法FINDER的效率虽然没有SPAM高,但是,效率接近于SPAM,与其他典型的算法相比,效率提高约3～5倍。2.对FINDER算法进行改进,采取格理论对枚举空间进行划分,设计并行序列挖掘算法pFINDER。pFINDER继承了FINDER的特性,仍然没有采用散列技术,具有较好的局部性特征。pFINDER采取中间数据的划分技术,减少了远程数据的同步与数据传输。因此,pFINDER算法具有良好的可伸缩性。3.结合加权频繁序列挖掘问题,改进FINDER,设计交互式加权频繁序列挖掘算法。该算法采取项重命名机制,把加权项转化为平凡项,使之适合于有效的频繁序列挖掘算法,简化了加权序列挖掘问题,特别适合于交互式挖掘。该算法对于实际应用特别有效。4.频繁模式挖掘是一项十分复杂的I/O密集型和计算密集型的挖掘任务,搜索空间的剪枝是有效提高效率的手段。通过对频繁模式挖掘算法搜索空间的深入研究,在认真分析现有剪枝策略的基础上提出新的搜索空间剪枝策略SEP和IEP。同时证明了相关的定理与推论,保证了两种剪枝策略的理论正确性。5.对典型的频繁模式挖掘算法进行分析,应用新的剪枝策略SEP与IEP,对文献资料上普遍认为比较高效的SPAM、SPADE、MAFIA、CHARM等频繁模式挖掘算法进行改进,形成新的频繁序列挖掘算法或频繁项集挖掘算法SPAM+、SPADE+、MAFIA+、CHARM+,结合公认的测试数据集或测试集生成程序,对各算法进行实验,并进行对比分析,以验证剪枝策略的正确性与有效性。实验表明,利用剪枝策略SEP、IEP改进后的算法SPAM+、SPADE+、MAFIA+、CHARM+分别比原来的算法效率提高最多达10倍,对大数据集,效率的提高也在30%～50%。6.所提出的SEP与IEP剪枝策略不仅可以大大改善算法的性能,同时,通过对多个算法的改进,也表明了该策略可以被多种算法和挖掘问题共用,表现了SEP、IEP独立于挖掘算法的特性。