模糊关联规则知识发现算法研究+文献综述(5)
3.3 关联规则的发现算法
关联规则的发现问题其实质是挖掘和用户所指定的最小置信度minconf与最小支持度minsup的关联规则。这个问题我们可以分成两个问题：第一就是求出数据库D中所有符合最小支持度minsup的全部项目集；第二是检测出符合最小支持度minsup的全部项目集是否能符合最小置信度minconf，从而生成相应的关联规则[5]。
3.3.1 关联规则的发现步骤
关联规则的发现就是我们要从海量的数据库中找出对我们有价值的数据项之间相互联系的有关知识。关联规则挖掘的一般对象是事务(Transational)数据库，这种数据库的一个主要应用是销售产业。关联规则挖掘是一般我们可以分为两个步骤。
Step1：发现出全部的频繁项集。在这一步我们会用到频繁项集的性质。就是频繁项集的全部非空子集也都必须是频集。即，如果 或者 中有一个不为频繁的，那么 也一定不为频繁的。采用这样的性质，可以提高计算的效率，当有一个项集中含非频繁的子集，我们就可以直接将它删除掉。
Step2：根据频繁项集来得到强关联规则。这里的强关联规则，就是必须要同时满足最小置信度minconf和最小支持度minsup的关联规则[5]。
3.3.2 Apriori算法
自Agrawal等人首次提出了挖掘顾客交易数据库中项集间的关联规则问题以来，研究学者开始行了大量研究和进一步优化原有的算法，提出了例如随机采样、并行等思想，使原有的挖掘规则算法的效率、准确性和伸缩性都有了提高，并且推广了关联规则的应用范围。
关联规则的挖掘算法有许多，最经典且常用的是Apriori和AprioriTid，本论文采用的是Apriori算法。Apriori算法扫描 很多遍，第 遍计算 项集。假如顶层项集中它的元素个数为 ，则该算法在扫描 时至少是 遍，也可能是 遍。对Apriori算法的改进主要利用 的方法，通过减小记录总数、减小待定项集的个数、减少记录长度的方法，从而达到减少验证记录 支持 的计算。
Apriori算法的基本思想是：首先找出所有的频集，然后由频集产生强关联规则。该算法利用层次顺序搜索的循环方法，通过对数据库D的多趟扫描来发现所有的频繁项集。
Apriori算法的具体步骤如下：
Step1：计算所有的待定1-项集的集合 ，找出全部的频繁1-项集 。
Step2：根据频繁1-项集 确定待定2-项集的集合 ，从 中找出全部的频繁2-项集 。
Step3：根据频繁2-项集 确定待定3-项集的集合 。从 中找出所有的频繁3-项集 。
Step4：依此循环下去，直到不再有待定项集。
Apriori算法核心思想的描述如下：
1. ;
2. ;
3. //新的待定集
4. ;
5. //事务 中包含的待定集
对上述的算法进行分析我们可知，在第K次的循环中产生待定K-项集的集合 中的项集是用来产生频集的待定集，最后的频集 必须是 的一个子集。 中的各个元素是否需要加入 是通过在交易数据库中来验证的，这里所用的验证过程为算法性能一个瓶颈。这个算法执行过程可能产生大量的待定集，以及可能需要重复扫描数据库，这是Apriori算法的主要缺点。
4. 模糊关联规则知识发现算法
4.1 模糊概念的引入
现实中，集合是对某些客观事物的一种高度抽象，而一个模糊的集合S应该可以有这样一种对象的集合：对于任何一个对象，除了有 和 两种可能之外，还可能存在这种情况我们不能精确地判断对象O是否属于集合S。这种这种“属于”的状态处于 和 之间，这就是集合S的模糊性。
1973年,L.A.Zadeh首次提出模糊关联的最初基本框架。1974年,英国科学家E.H.Mamdani首次将模糊关联技术应用于自动控制,并取得了巨大成功。20世纪80年代末,随着计算机技术的快速发展,基于模糊关联的模糊控制技术也得到广泛应用,并取得巨大发展。L.A.Zadeh等人提出的模糊集合理论及其在此基础上快速发展起来的模糊逻辑把事物所具有的模糊性反映了出来,使得对客观存在的模糊性进行了有效的处理。同时,它也为模糊关联提供了理论支持。