数据库关联规则挖掘算法研究.docVIP

数据库关联规则挖掘算法研究 摘要：该文介绍了数据挖掘、关联规则相关概念，分析了经典的挖掘布尔关联规则频繁项集的算法-Apriori算法，阐述了关联规则的生成过程，并通过实例进行验证。针对Apriori算法的缺陷进行了分析并列举了几种算法优化方法。 关键词：数据挖掘；关联规则；Apriori算法；阈值 中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）16-3721-03 Abstract： This article describes the conception of data mining and association rules， Analyzes apriori algorithm，It’s the classic algorithm in frequent itemsets mining base on boolean association rules， Describes the generation process of association rules and verified by examples. Analysis of the defects of apriori algorithm and several improved algorithms. Key words： data mining； association rules； Apriori algorithm； threshold 1 数据挖掘 随着计算机、网络和信息技术的发展，采集和保存数据的能力也大大提高，信息大量涌现，如何从海量信息中找出所需的、有用的知识，成为了一个重要研究课题。数据挖掘一般是指从大量的实际数据中，通过算法有哪些信誉好的足球投注网站提取隐藏于其中的、有用的信息和知识的过程，同时通过分析大量数据来揭示有意义的新的关系和趋势。数据挖掘融合了人工智能、机器学习、模式识别、统计学、数据库、可视化技术等多个领域的理论和技术，是数据库研究中的一个很重要且有应用价值的领域。 2 关联规则 数据关联是数据库中存在的可被发现的知识，若多个变量的取值存在某种规律性，就称为关联。关联分析在数据挖掘中用于揭示数据项集之间的相互关系，生成关联规则，形如[X?Y]的蕴含式。关联规则挖掘要先从数据集合中找出所有的频繁项目组（Frequent Itemsets），然后从频繁项目组中产生强关联规则（Association Rules）。具体描述如下： 假设[I i1，i2，…，im ]是一个项目集合。给定一个事务数据库[D t1，t2，…，tn ]，其中每个事务[ti（i 1，2，…，n）]具有唯一标识TID，且都对应I上的一个非空子集。设[X?I]，项目集[X]在数据库D上的支持度（support）指包含[X]的事务在D中的百分比，即： [support（X） t∈D|X∈I D] （1） 对于项目集I和事务数据库D，I中所有满足用户指定的最小支持度min_sup的项目集，称为频繁项目集。在频繁项目集中选出所有不被其他元素包含的项目集称为最大频繁项目集。 如果有[X?I，Y?I，X?Y φ]，则一个定义在I和D上的关联规则形如“[X?Y]”，其置信度（Confidence）指包含[X]和[Y]的事务数与包含[X]的事务数的比值，即： [Confidence（X?Y） support（X?Y）support（X）] （2） 关联规则挖掘就是用户根据需要设定最小支持度和最小置信度min_conf阈值，有哪些信誉好的足球投注网站满足这两个阈值的关联规则的过程，满足条件的关联规则称为强关联规则。 根据规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的是离散的、种类化的值，揭示这些变量之间的关系；数值型关联规则对数值型字段进行处理，可以将其进行动态分割，或直接对原始数据进行处理。 3 Apriori算法 3.1 算法描述 关联规则由Agrawal等人于1993年首次提出之后，研究人员对数据库关联规则挖掘方法进行了大量研究，提出了多种算法，如Apriori算法、基于划分的算法、FP-树频集算法等，其中最有影响的是Apriori算法。 Apriori算法是挖掘布尔关联规则频繁项集的经典算法，该算法首先使用逐层有哪些信誉好的足球投注网站的迭代法，根据最小支持度阈值，找出所有的频繁项集。然后由频繁项集产生强关联规则：给出最小置信度阈值，针对每个频繁项集，生成其所有非空子集，计算每个非空子集的置信度，置信度满足最小置信度阈值，则相应关联规则成立。算法核心思想描述如下： 1） [L1 find_frequent_1_itemsets（D）；] 2） [for（k 2；Lk-1≠φ；k++） ] 3） [Ck apriori_gen（Lk-1，min_sup）；] 4） [