8.txt

This complete matlab for neural network

发信人: GzLi (笑梨), 信区: DataMining
标  题: [合集]请问有没有有关关联规则发展的文章
发信站: 南京大学小百合站 (Tue Feb 18 18:17:15 2003)

vant (vant) 于Tue Jan 21 11:13:48 2003)
提到：

3x！


jimo (寂寞) 于Tue Jan 21 12:29:42 2003)
提到：

你看op的paper的后面的参考文献里的paper就行了
然后空间关联规则看han的综述就行了

【 在 vant (vant) 的大作中提到: 】
: 3x！


vant (vant) 于Tue Jan 21 12:38:16 2003)
提到：

sorry,op是who，han是who？
我都不懂，blush，麻烦你说明白点好吗？
【 在 jimo (寂寞) 的大作中提到: 】
: 你看op的paper的后面的参考文献里的paper就行了
: 然后空间关联规则看han的综述就行了
: 【 在 vant (vant) 的大作中提到: 】


jimo (寂寞) 于Tue Jan 21 14:52:59 2003)
提到：

上google搜索一下吧
南开的学生我一向认为不错的
呵呵

【 在 vant (vant) 的大作中提到: 】
: sorry,op是who，han是who？
: 我都不懂，blush，麻烦你说明白点好吗？
: 【 在 jimo (寂寞) 的大作中提到: 】


vant (vant) 于Tue Jan 21 15:50:34 2003)
提到：

可是偶是学文科的，不是学理科的
这方面的都不懂
【 在 jimo (寂寞) 的大作中提到: 】
: 上google搜索一下吧
: 南开的学生我一向认为不错的
: 呵呵
: 【 在 vant (vant) 的大作中提到: 】


jueww (觉·无我) 于Wed Jan 22 10:41:41 2003)
提到：

高频集发现方法综述
高频集发现就是从目标数据库中找出所有支持度大于预先给定的最小支持度
的项集。高频集发现在关联规则发现[47]、相关性发现[48]、因果关系发
现[49]、序列模式发现[50-52]、episode发现[53-55]、偏周期性发现
[56-58]、profile规则发现[59]、事务间关联规则发现[60,61]等领域起着
关键作用。
高频集发现和关联规则发现的关系最为密切。关联规则发现致力于发现满足
支持度/可信度要求的关联规则，它分为高频集发现和规则生成两个步骤。
由于高频集发现是关联规则发现算法提高性能的瓶颈，所以几乎所有对关联
规则算法的研究都致力于在保证精度的基础上提高算法的运行效率，其中精
度是指所发现高频集的满足要求的程度。1993年，Agrawal等[47]提出关
联规则发现问题，同时提出第一个高频集发现算法。此后，在各种问题背景
下，围绕着提高算法效率和结果的有用性（即用户对其感兴趣程度），研究
者们提出各种高频集发现算法。根据这些算法的研究重点不同，可将其分为
基本高频集发现算法和增强高频集发现算法。前者致力于设计各种算法框
架，高效地发现所有支持度大于某个不变的最小支持度的高频集。后者致力
于提高发现结果的有用性。基本高频集发现算法的结果往往不能满足用户要
求，比如所发现的高频集的有用性不高、发现的高频集数量过多、遗漏用户
感兴趣的高频集等等，增强高频集发现算法通过引入概念层次结构、约束条
件、可变支持度等方式克服这些缺陷。
基本高频集发现算法
基本高频集发现算法是在单数据库、单概念层次和最基本要求（即使用相同
的最小支持度发现所有高频集）的条件下发现高频集，它是其它更“高级”
高频集发现算法的基础。根据算法提出的时间和算法原理的不同，可将它们
细分为Apriori算法出现之前的算法、Apriori类算法、基于分块的算法、基
于采样的算法、新出现的高性能算法、基于最大高频集的算法和高频封闭项
集发现算法等。其中后三类算法在分析强相关性数据时有明显的性能优势。
在Apriori算法出现之前曾出现过两种算法。1993年，Agrawal等[47]提出
面向单个事务的高频集发现算法AIS。1995年，Houtsma等[62]提出面向
集合的高频集发现算法SETM。AIS和SETM算法根据每个事务中的已发现
高频集和此事务中的其它项生成候选高频集，因此生成的非候选高频集数量
很多，导致性能在各种情况下都不如Apriori算法，因此没有得到实际应
用。1994年，Agrawal等[63]提出简单又高效的高频集发现算法Apriori。
该算法利用了高频集的逆单调性－高频集的子集必定是高频集，通过在第k-
1次扫描数据库后所得到的长度为(k-1)的高频集（简记为(k-1)-高频集，下
同）生成k-候选高频集，然后在第k次扫描数据库时统计k-候选高频集的出
现次数。Apriori算法在巨型数据库上有良好性能。但是，Apriori算法使用
生成-检验循环的方式发现高频集，因此当数据库中高频集的密度比较大或
最长高频集比较长时，Apriori算法不能避免所生成的候选高频集数量的指
数爆炸，导致性能急剧下降。而且，Apriori算法需要多次扫描数据库，造
成沉重的I/O负担。此外，Apriori算法的并行化版本需要在每遍扫描数据库
后对各并行处理部分进行同步，以便对各并行处理部分的结果进行汇总，因
此其同步开销较大。Agrawal等[50,63]发现，Apriori算法运行时时间开销
最大的阶段是刚开始的几次生成-检验循环，特别是发现2-高频集的循环。
在此阶段生成大量无效的候选高频集。Park等[64]据此提出Apriori算法的
一种改进－DHP（直接乱散与删剪）算法。通过使用直接乱散技术，DHP比
Apriori算法少生成一个数量级的2-候选高频集，从而提高了算法性能。另
外，由于所生成的2-候选高频集数量大大减小，所以DHP算法可在发现2-
高频集之后就从数据库中删掉无需再考虑的事务和项。
1995年，Savasere等[65]提出基于分块原理的Partition算法。Partition
算法将原数据库分割为若干个子数据库，其中每个子数据库都充分小，足以
放入内存。由于任何高频集至少在其中一个子数据库中是高频的，所以可先
分别发现每个子数据库中的高频集，然后将这些高频集汇总作为总候选高频
集，再扫描一遍原数据库发现其中满足全局高频条件的高频集。由于每个子
数据库可放入内存，所以发现其中的高频集不需要使用非常耗时的I/O操
作，算法总体执行速度比较快。另外，Partition算法还是一种本质并行算
法。不过，当子数据库数目增大时，Partition算法生成的无效总候选高频集
数目快速增长，导致效率降低，因此Partition算法在较大数据库上的性能不
如Apriori算法[50]。Brin等[66]提出DIC（动态项集记数）算法，可视为
一种串行化的Partition算法。
Zaki等[67]认为，在高频集发现过程中使用采样技术至少可提高一个数量
级的速度，而且精度损失不多。1996年，Toivonen[68]提出一种基于采样
的高频集发现算法。其基本思想是对数据库进行采样，形成采样数据库，然
后用较小的最小支持度发现采样数据库中的高频集S。再将S和它的负边界
Bd-(S)合并，构成候选高频集S Bd-(S)。接着扫描一遍原数据库从S Bd-
(S)中发现所有高频集S’。如果其中Bd-(S)包含高频集，那么说明原数据
库中可能存在还未被发现的高频集。这时需要用公式S’=S’ Bd-(S’) 叠
代计算直到S’不再增大，然后将S’作为候选集再扫描一遍原数据库，发
现所有被遗漏的高频集。所以此算法在一般情况下只需扫描数据库一次，在
最差情况下需要扫描两次。1997年，Park等[69]提出两个可调节精度的算
法DS和SH。其中DS算法可视为DHP算法加入采样技术之后的推广。DS和
SH算法可用于为了提高效率而允许损失一些精度的场合。
Apriori类算法在数据库为高密度、长模式或低支持度等情况下性能急剧下
降，为此提出一些新的高性能高频集发现算法。2000年，Agarwal等
[70,71]提出一种全新的高效算法TreeProjection。此算法构造一个词典
树，并根据已发现的高频集，将数据库投影到一组精简的子数据库上。由于
词典树提升了检验候选高频集的效率，并且此算法还使用其它各种提高效率
的技术，所以TreeProjection算法比Apriori算法的性能高一个数量级。
2000年，Han等[72]提出一种不需要生成候选高频集的算法FP-growth。
此算法首先扫描两遍数据库，生成信息高度压缩的高频模式树，然后在其上
递归生成条件高频模式树，同时找出所有高频集。由于此算法不需要生成候
选高频集，避免了Apriori类算法本质具有的候选高频集数量指数爆炸情
况，因此获得比Apriori算法高一个数量级的性能。
如果一个高频集不是其它高频集的真子集，那么称此高频集为最大高频集。
1997年，Zaki等[73,74]提出基于最大高频集的高频集发现算法
ClusterApr。算法首先使用聚类技术将相关的项集分组，以此得到最大高频
集集合的超集，然后生成此超集的所有子集作为候选高频集，最后扫描一遍
数据库验证此候选高频集。ClusterApr算法的性能优于Apriori算法，逊于
Partition算法，但是此算法只能应用于垂直格式数据库上。Shen等[75]提
出和Zaki算法类似但可用于水平格式数据库的基于最大高频集的高频集发现
算法，并且此算法具有本质并行性。
高频封闭项集是一组事务都包含的项的最大项集。一个数据库的高频封闭项
集集合与其高频集集合的信息量相等，但是前者比后者小得多，因此发现高
频封闭项集能够减少数据库扫描遍数和CPU开销，从而提升高频集发现的效
率，并大幅减少输出冗余信息。1999年，Pasquier等[76]提出基于
Apriori算法框架的高频封闭项集发现算法Close。Close算法相对于Apriori
算法在分析强相关数据时具有明显的性能优势，可将数据库扫描遍数减少到
原来原遍数的1/4到1/2。1999年，Zaki等[77]提出使用垂直数据库结构
的高频封闭项集发现算法CHARM。Close算法和CHARM算法在发现长模式
或低支持度阈值时效率不高。2000年，Pei等[78]提出基于FP-growth算
法框架[72]的高频封闭项集发现算法CLOSET。
增强高频集发现算法