● 摘要
随着技术的进步和社会的发展，各领域内的数据库规模不断扩大，而且日益呈现出大样本、多指标、时序性、含噪声等特点。具有这些特点的大规模复杂数据集对现有关联规则挖掘方法的挖掘效率提出了新的挑战。因此，如何从含大量噪声的大规模复杂数据集中提取有效信息，如何针对大规模复杂数据集设计高效的关联规则挖掘算法，如何提高关联规则挖掘的效率和质量，便成为目前关联规则挖掘研究中的一个核心问题。针对目前关联规则挖掘方法在挖掘大规模复杂数据集时所面临的效率问题，本文从理论模型的构建，理论方法的设计，理论模型与方法的应用与实证三个方面对大规模复杂数据集关联规则挖掘问题展开了深入研究，提出了一套高效的大规模复杂数据关联规则挖掘方法，具有重要的理论、现实意义和应用价值。具体来说，本论文的主要研究内容和创新成果如下：。1、提出了基于数据简约和数据压缩思想的大规模复杂数据关联规则挖掘模型。Agrawal关联规则挖掘模型在描述大规模复杂数据关联规则挖掘过程时存在很大的局限性。本论文在Agrawal关联规则挖掘模型基础上，结合数据简约和数据压缩思想及其方法，对Agrawal关联规则挖掘模型进行了拓展，提出了基于数据简约和数据压缩思想的大规模复杂数据关联规则挖掘模型，为今后大规模复杂数据集关联规则挖掘研究提供了模型框架。2、提出了三种高效的大规模复杂数据关联规则挖掘算法。（1）提出了基于二元关系矩阵及其运算的频繁项集挖掘算法（Binary Relation Matrix Frequent Itemset Mining, BRMM）针对Apriori算法在挖掘大规模复杂数据集时存在的数据结构、连接和剪枝策略、搜索空间等方面的不足，首先将简约压缩后的事务数据库进一步压缩映射为二元关系矩阵数据结构，在此基础上，提出了一种新的剪枝和连接策略以及搜索空间的动态压缩策略，应用二元关系矩阵数据结构和相应的优化策略，设计了基于二元关系矩阵及其运算的频繁项集挖掘算法，并通过示例和实验对算法的性能进行了分析比较，实验结果表明，无论是在大规模稀疏数据集还是稠密数据集上，BRMM算法的挖掘效率都要明显优于Apriori算法。最后为了适应更大规模关联规则挖掘的需要，将BRMM算法进行了拓展，设计了基于二元关系矩阵及其运算的并行频繁项集挖掘算法（Parallel Binary Relation Matrix Frequent Itemset Mining, PBRMM），并对算法性能进行了分析。分析说明，PBRMM算法同样是一种高效的并行频繁项集挖掘算法。（2）提出了基于频繁项目关系矩阵的频繁项集挖掘算法（Frequent Item Matrix Mining, FIMM）和相应的事务间关联规则挖掘算法。针对Apriori算法和Fp-growth算法在挖掘大规模稠密和稀疏数据集时各自存在的不足，提出了空间压缩效率更高、挖掘效率更好的频繁项目关系矩阵数据结构。在此基础上，将Apriori算法和Fp-growth算法的优点进行了结合，提出了宽度优先和深度优先相结合的基于频繁项目关系矩阵的频繁项集挖掘算法和相应的关联规则挖掘算法。并通过示例和实验对算法的性能进行了分析比较。实验结果表明，无论是在大规模稀疏还是稠密数据集上，FIMM算法的挖掘效率均要明显优于Apriori算法和FP-growth算法，说明了FIMM算法对于不同特点的数据集具有更好的适应性。（3）提出了基于时间约束频繁项目关系矩阵的频繁项集挖掘算法（Temporal Frequent Item Matrix Mining, TFIMM）和相应的关联规则挖掘算法。 针对具有时间约束的事务间关联规则挖掘问题，和现有事务间关联规则挖掘算法E-Apriori、EH-Apriori、FITI在挖掘大规模复杂数据集时存在的不足，对频繁项目关系矩阵数据结构进行了拓展，提出了时间约束频繁项目关系矩阵数据结构。在此基础上，将宽度优先算法和深度优先算法的优点进行了结合，提出了基于时间约束频繁项目关系矩阵的频繁项集挖掘算法和相应的关联规则挖掘算法。并通过示例和实验对算法性能进行了分析比较。实验结果表明，无论是在大规模稀疏还是稠密数据集上，TFIMM算法的挖掘效率均要明显优于FITI算法，说明了TFIMM算法对于不同特点的数据集具有更好的适应性，是一种高效的事务间关联规则挖掘算法。3、对中国A股市场2001-2006年各行业板块间的板块关联效应进行了挖掘分析选取了wind金融数据库中2001年-2006年中国A股市场所有股票1444个交易日的开盘价、最高价、最低价、收盘价、成交量、成交额、换手率、成交均价行情数据为初始样本点，首先根据本文提出的基于数据简约和数据压缩思想的关联规则挖掘模型，利用中信证券二级行业风格指数和涨跌幅指标对初始数据进行了简约和压缩处理，在此基础上，利用本文提出的基于频繁项目关系矩阵的关联规则挖掘算法和基于时间约束频繁项目关系矩阵的关联规则挖掘算法，对中国A股市场各行业板块间的板块联动和轮动效应进行了挖掘分析，一方面验证了本文所提模型和算法的有效性，另一方面也实证了2001年-2006年，中国A股市场中各行业板块间的确存在板块联动效应，但不存在明显的板块轮动效应。