openminer中挖掘关联规则的算法实现概述

   关联规则挖掘算法很简单，比如Apriori，FPG这些都是典型的基础算法。但是一般的书籍却很少提到如何在真是的数据库上实现。真实的数据库不一定是海量数据库，哪怕是一个记录超过1W的关系表，如果属性很多，超过20个，那么中间过程中产生的候选项集也是很庞大的。其实所需的内存主要是保存候选项集和频繁项集。

   候选项集的产生是组合交叉产生的，如果以组合公式来计算，属性个数N=20,那么产生的候选项集中，最大可以达到2^20-1项，大约就是1MB个候选项。而如果属性个数超过32个，那么最大的候选个数就超过4GB，即使一个候选项只保存一个字节，也达到了32位机器的内存极限了。显然，无论如何，候选项集是不能保存在内存中的。

  现在大部分的书上的关联挖掘讲解都是基于算法演示，也没有多少运用于实际的数据库项目。OpenMiner里面需要关联挖掘的事务数据的事务项可能超过200个，显然不能同于一般数据挖掘教材上的那些算法了。

  OpenMiner的关联挖掘实现的核心算法跟一般的基于内存的是一致的，唯一不同的就是将中间结果，候选项集和频繁项集，存放于外存。当然，也不是完全存放于外存，只是大部分存放于外存，当前需要多次访问的还是存放在内存中。访问外存的速度远比访问内存速度慢，而且OpenMiner的支持多种外存存储介质，可以是OpenMiner自己建立的磁盘文件，也可以是系统数据库里面的数据表。OpenMiner是推荐使用后者作为其中间结果的保存，因为数据库管理系统能够提供更好的候选式和频繁式的查询和提取效率。而通过Hibernate这样的O/R Mapping工具，数据挖掘使用者可以很方便地将数据表映射成Java里面的常用数据结构对象，比如List这些，这一层就可以对于Apriori,FPG算法模块来说做到透明了。

   上述办法，OpenMiner解决了内存有限的问题，但是效率方面并没有解决。其实关于提高Apriori效率的研究早就已经有很多论文了。比如基于Hash-Tree的Apriori，以及后面的FPG等等，都是解决速度的不错方法，但是无论如何，关联挖掘的在进行支持度查找的时候，每次都要遍历整个数据表，实在快不起来。