关联规则Eclat算法改进研究-计算机系统结构专业论文.docxVIP

重庆大学硕士学位论文中文摘要 重庆大学硕士学位论文 中文摘要 I I 摘 要 数据挖掘是从海量数据中获取有效的、新颖的、潜在有用的知识，并最终形 成可理解的模式的非平凡过程。现今的数据库系统已经能够实现查询、统计和报 表，但处理方式相对单一，都只是对一定范围内的数据进行简单的数字化处理， 而不能提取隐藏在这些数据背后的内在信息。随着各行各业广泛应用信息管理系 统，带来了数据量的急速膨胀，人们迫切希望有一种功能，它能够提供更高层次 的数据分析，从而更好地支持决策或科研工作。关联规则挖掘是数据挖掘中关联 分析的运用，是数据挖掘一个非常重要的学科，具有很高的理论价值和广泛的应 用前景。 关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或 多个事物之间存在着一定的关联关系，那么其中一个事物就能够通过其他事物预 测到。关联规则挖掘算法用于发现关联规则，诸多的研究人员和学者对其进行了 大量的研究。现有的关联规则算法大多数是基于 Apriori 和 FP-growth 的迭代算法。 通常数据库有水平数据表示和垂直数据表示两种形式，本文深入分析了频繁项集 的挖掘问题，描述了现有的关联规则分类和挖掘算法，并着重对传统 Apriori 算法 和 AprioriTid 算法进行分析，指出了他们各自的优缺点。对于挖掘算法的性能，通 常采用垂直数据表示的算法要高于水平数据表示，Eclat 算法是首个采用垂直数据 表示的经典关联挖掘算法。 本文首先对 Eclat 算法进行了深入地研究和分析，并在此基础上提出了一种改 进算法——hEclat。该算法把散列表与布尔矩阵相结合，提出散列布尔矩阵的思想， 对传统 Eclat 算法中求两个 Tidsets 集合交集的操作进行改进，以提高求交集的速度， 从而达到提升整个算法生成频集、挖掘关联规则的效率。 对关联规则挖掘而言，已有的很多研究只注重解决算法的时间效率，而忽视 了关联规则的多维特性，通过在关系数据库中提取出用户感兴趣的多维关联规则， 在商务决策方面将更具指导意义，也更能够满足实际情况的需要。本文在传统 Eclat 算法基础上提出 MD-Eclat 算法，并构造了一种新的数据预处理方法，实现从关系 数据库的普通表或视图中进行多维关联挖掘。由于算法利用了垂直数据表示的结 构特征，因此不必对数据库进行多次扫描，也不必频繁构造模式树，只需要扫描 数据库一次，改进后的算法执行时间效率高于同类算法。 关键词：关联规则，垂直数据表示，散列，布尔矩阵，多维关联规则 重庆大学硕士学位论文英文摘要 重庆大学硕士学位论文 英文摘要 II II ABSTRACT Data mining is a non-trivial process which is to obtain effective, novel and potentially useful knowledge from the mass of data and ultimately form understandable patterns. Database systems of nowadays have been able to achieve query, statistics and reports, but the treatment were relatively homogeneous which are only simple digital processing for a certain range of data, and also cannot extract the inherent information hidden in the back of data. With the widely usage of Information Management System in various industry fields, it bring about the rapid expansion of the amount of data. Therefore, people are eager to have a function which can provide a higher level of data analysis, so that the decision-making and scientific work can be better supported. Association rule mining is the application of associated analysis in data mining, which is a very important subject with high th