出谋划策1：有关关联规则的阈值设定

改善关联规则挖掘时间的办法很多，比如采样sampling,或者cbar基于聚类的关联规则挖掘，今天看到一种办法好象不错，就是类似缓冲cache的办法，有限制性条件下的加速。

因为很多查询可能只是查特定的一部分的交易类型，扫描全数据库没有意义的。

大家查询的时候有没有不停的改变support/confidence值，来试探合适的结果的时候？

正在看这篇文章：

An Efficient Method for Mining Association Rules
with Item Constraints
Shin-Mu Vincent Tseng
Computer Science Division, EECS Department
University of California, Berkeley
Berkeley, CA94720
Email: tsengsm@cs.berkeley.edu
Abstract
Most existing studies on association rules discovery focused on finding
the association rules between all items in a large database that
satisfy user-specified minimum confidence and support. In practice,
users are often interested in finding association rules involving only
some specified items. Meanwhile, based on the search results in former
queries, users tend to change the minimal confidence and support
requirements to obtain suitable number of rules. Under these
constraints, the existing mining algorithms can not perform efficiently
due to high and repeated disk access overhead. In this research, we
present a novel mining algorithm that can efficiently discover the
association rules between the user-specified items or categories via
feature extraction approach. At most one scan of the database is needed
for each query; hence, the disk access overhead can be reduced
substantially and the query be responded quickly.

马上有讨论奉上，请各位大虾发表一下自己的实践挖掘情况阿

1. 采用采样技术，快速给出support/confidence的建议值(论文作者说具体技术正在设计中）

讨论：是否可以倒推，比如用户指定想要20条结果规则，结合采样技术，倒推出minsupp/minconfidentce值来？
请大家给点意见

2. 当用户提交关联规则查询（特定support/confidence,特定的项目items)时，扫描一遍全数据库，建立特征向量库和支持度库。
特征向量由0/1串构成（在稀疏情况下还可以压缩），每个item对应一个向量，这样当考虑候选itemset的出现次数时，不需要再扫描数据库，对特征向量作And操作，数1的个数就可以了。

另一种方法是将交易数据库按交易长度分群，然后用cbar(cluster-based association rules)/cdar来选频繁集。

各位用到的挖掘工具里有没有使用类似算法的呢？

Qing 20061030

这篇论文介绍的是对关联规则挖掘算法的优化吗？

其实我更加关心，如何设定support/confidence的阈值，用来提取有意义的规则。

关于这个问题，前面有过几次探讨，比如：

1、"解读关联规则" http://groups.google.com/group/ttnn/browse_thread/thread/8383f2d29ad2b71/efab8bebd11925d9?lnk=gst&q=%E5%85%B3%E8%81%94%E8%A7%84%E5%88%99&rnum=2#efab8bebd11925d9
2、"关联规则解读再探" http://groups.google.com/group/ttnn/browse_thread/thread/dfe176553a22a7de/696bc2974bf5e114?lnk=gst&q=%E5%85%B3%E8%81%94%E8%A7%84%E5%88%99&rnum=1#696bc2974bf5e114
3、"读’从属性到身份’" http://groups.google.com/group/ttnn/msg/d0cf3a016bd37017

在第一篇文章中，总结了一下第一次做关联规则的解读的结果。比较遗憾，虽然试图通过支持度、置信度来设定阈值，但最终以失败告终。

原因是，一条有意义的关联规则，并非仅仅通过支持度、置信度来表现的，它还跟关联业务的选择、对业务之间的潜在关联理解有关系。这后面两者，目前并没有任何量化的东西可以表示。通过支持度、置信度，确实能够得到范围比较少的规则，便于去解读。可另一方面，又担心，这个限定导致一些实际有意义的规则被剔除出去（也许这是无谓的担心，但谁知道呢）。因此，矛盾啊，最后还是换了一种思路——针对具体的业务，分析所有与之关联的其他业务，当然，用人脑。

不过，这在做两项业务之间的关联是，可以这么作，但如果对于多项业务关联，组合太多，恐怕还得结合支持度、置信度的限定来考虑。

朱思征对这个问题颇有研究，不妨来论论。

Hunter 20061031

没错，支持度，置信度并不是很好的指标（对于多数实际应用），毕竟是13年前的东西了啊！（呵呵，没准那时侯只喜欢玩电脑游戏的俺未卜先知去研究挖掘也能提出关联规则呢：）

目前看别人的东西的初步印象是

1。用其他指标，unexpectedness等
2。结合领域知识，搞taxonomy，概念分类，然后来挖掘更相关的规则

一定程度上可以自动化或者半自动话，效果比argawal的老指标好（呵呵，为什么看什么文章他老人家都列第一，俺不服不行，太强了）

Zhusizheng 20061102

support/confidence模式是关联规则规则的基础，这是因为关联规则的整个理论体系是建立在数理统计上的。支持度是概率，置信度是条件概率，可以简单的这么去理解。

对于hunter提的两个问题，我认为应该从更多的方面去解读关联规则，前面也做过一定的尝试，但因为时间的关系到目前为止还没能完全出炉。

简单的说，除了支持度、置信度模型以外，对一个关联规则的评价和生成与挖掘者和挖掘的业务息息相关。
目前对于一个关联规则的评价的指标主要分为两类，一类是客观性指标，另一类就是主观性指标。

客观性指标有：支持度，置信度，相关度（有的也称为提升度，兴趣度），支持度是描述项集在整体事务集合中所占的比率，置信度是描述前件在项集中的比率，置信度是描述关联规则前件与后件间的相关性指标，或者说是描述前件与后件之间的独立程度，这是概率论上的独立性的概念。只所以把这三个称为客观性指标，是因为他们都有明确的数学模型和定义。

主观性指标有：新颖度，简洁度和用户感兴趣度等指标。新颖度是指通过与已经建立起的规则库中的关则进行一系列比对来判定一个规则的新颖程度，基本上用于科研场所。简洁度是用来衡量关联规则的最终可理解程度的指标。它表现在两个方面：一方面表现在规则的个数上，如果规则项数很多将不利于对这条规则的理解。因此，规则的项数越少，规则的简洁性越好。另一方面表现在规则所包含的抽象层次上，规则包含的抽象层次越高，它对应的解释力越强。用户感性度指标是为了满足用户只想看包含自己想看的项的规则而设定的指标，比如用户在业务进行中对某个项比较感兴趣，他就可以指定计算与这个项相关的规则。

相比较而言，支持度，置信度及相关度的理解和实现相对简单。支持度可在关联规则生成的第一步：频繁项集的生成中获得，具体的获得过程因算法的不同而各异。如Apriori算法中在剪枝的过程中生成，FP-Growth算法中在对Fp树遍历生成频繁项集时生成（关于算法，可再议。hunter兄在第2问中提及的思想是利用二进制串来生成关联规则，优点和缺点都比较明显）。在生成支持度计数的前提下，可以计算置信度与相关度的值，而计算的时机在关联规则挖掘的第二大步：关联规则的生成算法中进行。目前可以采用的关联规则生成算法主要有两类：递归和利用二进制串思想的FAS算法，此时二进制串思想的优异性得以长足的体现。因此，对客观性指标都有一个明确的度量可计算，对于工程技术人员来说不是问题。

对于主观性指标，因为掺杂了太多的人和业务的因素在里面，一直是一个比较头痛的话题。前面和庆兄等各位也进行过一定的探讨，但都没有一个明确的结论。hunter兄所讨论的问题集中在技术实现领域，因此我也近可能的从技术实现领域来再次探讨一下这个话题。

先来说一下新颖度，因为这个问题要牵扯到一定的人工智能，而且应用的领域一般在科研领域（如专家库等），所以我们不会做过多的讨论。新颖度是用来衡量一个规则新鲜度的指标，可以通过对比规则的频繁项集、规则的前件、规则的后件、规则的前件子集等与已经建立的规则库中的信息通过指定的算法进行一系列比较从而得出一个综合指标值。从架构上说，这个属于AI方面的可能性要多于BI方面。

再说简洁度，为什么要提出一个简洁度的概念？我们看关联规则的本质是为了反映事物或者称为属性间的联系，从哲学的范畴来讲，事物是普遍联系的。而我们的目标就是从众多的联系中找出有用的联系，也就是目标逐步缩小的过程。简洁度的概念就是为了更加明确的指定缩小的程度和范围而引入的一个指标。影响规则集简洁度的主要指标有：1，规则的个数；2：规则的长度。规则的个数多了，容易造成信息泛滥；规则的长度大了，容易造成理解上的混淆。而且，根据关联规则生成算法，一个规则的长度等于该规则所在频繁项集的长度。而一个长度为K的频繁项集可以产生的关联规则数约为2的k次方个（置信度为0的情况下），也就是说关联规则的长度对关联规则的个数有决定性的影响。所以可以在算法的实现过程中引入一个"指定生成的频繁项集的长度"的指标，来提升规则的可读性。另一方面，由于指定了频繁项集的长度，从而无形中也减少了Aprior算法中扫描事务数据库的次数（在Fp-Growth算法中却带来了一定的小问题，如需要更改频繁项集的算法，但从整体上来讲算法效率是得到了提高），从而提升了效率。目前，在MS sql 2005中的关联规则算法中已经引入了这个概念。

再说用户感兴趣度，由于事务数据的巨大量，最终所生成的规则数目也是很多的。从数据－>信息的过程已经可以实现，但信息－>知识的抽取过程仍不完善。这是因为有效的信息对用户才是知识，简言之用户要感兴趣。虽然关联规则挖掘是一个无目的性质的过程，但用户往往会有一定的目的性，如想重点生成某种事务的规则等。用户感性度就为此而设。

前面分析客观性指标的时候，我们分析了支持度、置信度、相关度在算法中引入的时机。下面我们来分析分析简洁度和用户感性度的引入时机。简洁度的可以在两个时机内引入：

1，频繁项集生成时；
2，频繁项集生成后。

频繁项集生成时引入的优点是可以提高算法的效率（有时甚至是大幅提升）但缺点是要对算法进行更改（Apriori算法的修改比较简单，Fp_growth算法中比较复杂）。在频繁项集生成引入的优缺点与在频繁项集生成时引入相反。我个人倾向于赞同第一中方法：在频繁项集生成时引入，不知道微软使用的是哪种方案。不过通过对sql2005的使用，感觉是在频繁项集生成时引入。

引入用户感性度的时机只能在频繁项集生成后，因为置信度与相关度等指标计算的要求已经限定了其引入的时机。

上面我主要从算法角度分析了各个可能引入的阈值，下面再从其他方面进行一些探讨。最后还要再次回到前面讨论无数次而没有明确结论的问题。

关于关联规则的优化，前面hunter兄也说过毕竟关联规则算法也经历了13年的岁月，期间有无数个优化算法比如基于分布式并行算法等等林林总总。另外，基于划分、聚类的算法多用于多维多层关联规则，我对这一方面还不是太熟悉。还有基于隐私的关联规则挖掘中倒是对hunter兄前面提及的二进制串的思想应用广泛。

再次回到庆兄关心的话题，究竟设定什么样的阈值才能挖掘出有用的规则，目前以我的看法：凭经验。庆兄不要发火，呵呵，这真是一句大大的废话和屁话，但确实没有什么更能准确表达我的看法了。凭什么0.6可以、0.59就不行？没有人能够回答......会不会丢失一些有用的规则？兄弟，舍弃的都是不适合的，贪多嚼不烂....只能如是...........................

那些指标阈值有什么用？没有任何的作用，只是在帮助你下狠心学会放弃。说的好听一点是在帮你缩小范围。想想看数据挖掘是数据－>信息－>知识的过程，每一步不都会舍弃很多？所以，一定要相信自己的判断，数据挖掘不是万能的，它能的也只是提供信息的一种筛选方式。另外也提供了一点唬人的借口和资本......

Hunter 20061102

呵呵,今天看公式正好悟出来,用概念分类来推断support值的时候support特别像概率,从support(AZ)推support(BZ)的时候,Support(BZ)估计为support(AZ)*support(B)/support(A),正好和朱兄所说"持度是概率，置信度是条件概率"相印证。

还请各位高人讨论一下原始的问题啊:

1.大家查询的时候有没有不停的改变support/confidence值，来试探合适的结果的时候？总是查询全库还是一部分特定数据?
2.在关联规则里,有没有一种类似文献挖掘的时候,比较还原率的思想(就是让经验丰富的人手工给文档重分类,然后将机器生成结果和手工结果来比较的那个指标,具体名字忘了?),能评价挖掘结果的优劣,呵呵甚至类似图灵测试也行啊?
3.除了经验,阀值通常是怎么生成/计算/拍脑袋得出来的?

发现这个概率思想很有用，刚才发了一个帖子关于前后件的关系(conf(AB->C)>conf(A->C)，认真用概率一推，其可能性根本不存在，呵呵，连帖子好像都不存在了，真是恰好。

Zhusizheng 20061102

你说的这个现象有一个定理：

定理 1： 设S 是项集L 的任意非空子集，s 是S 的任意非空子集，则规则s=>(L-s) 的置信度不大于S=>(L-S) 的置信度。

定理1指明计算频繁项集所含关联规则的次序问题。对频繁项集L，记其子集S，先计算S较大的情况下 S=>(L-S)的置信度并与用户设定的最小置信度阈值比较，若其不小于最小置信度阈值则输出，否则不输出，并且不再计算由S的真子集生成的关联规则的置信度。

这属于关联规则生成优化的问题。