8.txt

This complete matlab for neural network

项一般具有概念层次关系。当存在概念层次关系时，用户通常对包含不同概
念层次的项的规则感兴趣，并称这种规则为广义关联规则或多层关联规则发
现。广义关联规则发现算法提高性能的关键也在于广义高频集发现的效率。
1995年，Srikant等[79]提出直接推广Apriori算法的广义高频集发现算法
Cumulate算法。此算法将数据库中所有事务的每个项的所有高层次概念项
都加入此事务中，形成扩展事务，然后再套用Apriori算法。由于和高层次
概念有关的项集一般有较大的支持度，和低层次概念有关的项集一般有较小
的支持度，而Cumulate算法对不同类型项集只能使用相同的最小支持度，
导致其发现结果不太有用。1995年，Han等[80]在Aprior算法基础上提出
多层高频集发现算法ML_T2L1。该算法首先将所有项替换为最高层次上的
项，同时设置较高的最小支持度，然后找出满足支持度要求的第一层次高频
集L1。在L1基础上，将所有项替换为第二层次上的项，降低最小支持度，
找出第二层次高频集L2。反复进行，直到Lk为空。
用户往往只对满足一定约束条件的高频集感兴趣，因此如果高频集发现算法
只发现满足用户指定约束条件的高频集，那么将大量节省用户处理不感兴趣
的高频集的时间，同时也可提高算法执行速度。1994年，Klemettinen等
[81]提出在关联规则中应用模板以发现用户感兴趣的关联规则。模板是用户
自定义词汇表示的规则，其中词汇使用项集进行定义。如果一条规则满足模
板，那么这条规则就是用户感兴趣的。但是由于用户自定义模板的复杂性，
高频集发现算法难以高效地检验一个高频集是否满足模板。1995年，Fu等
[82]提出元规则指导的关联规则发现，元规则可视为Klemettinen等提出的
模板概念的一种简单推广。1997年，Srikant等[83]提出三种项约束高频
集发现算法MultiJoins、Reorder和Direct，其中项约束就是要求所发现的
高频集必须包含或不包含用户所指定的若干项。这三种算法推广了Apriori
算法的候选高频集生成过程，在生成候选高频集时检验其满足项约束的情
况。崔立新等[84]提出Direct算法的改进算法Seperate。1998年，Ng等
[85]提出可使用单变量约束的CAP算法，其约束形式可以是项的合取和否
定，以及求均值等集合操作。Lakshmanan等[86]提出可使用双变量约束
的高频集发现算法。Pei等[87]提出可使用可转换约束的高频集发现算法。
可转换约束无法在Apriori算法框架中实现，但可在FP-growth算法框架中
实现。
长模式就是长度较长的高频集。在调查分析、基因组数据分析等领域普遍存
在长模式。由于Apriori类算法所生成的候选高频集数量与最长高频集的长
度成指数关系，所以对于长模式的高频集发现，此类算法不可行。1997
年，Gunopulos等[88]提出一种可用于长模式发现的随机高频集发现算
法。算法循环地试图随机扩展一个工作项集，直到失败。由于是随机算法，
所以此算法不能保证发现所有的长模式，但能够有效地发现其中的一部分。
不过它不能处理内存放不下的数据库。Zaki等[73]提出的MaxEclat和
MaxClique算法使用Apriori算法框架，试图在其生成-检验循环开始前识别
长模式，以减少候选高频集的生成数目。Lin等[89]提出Pincer-Search算
法，此算法同样使用Apriori算法框架，并在其生成-检验循环中识别长模
式。1998年，Bayardo等[90]提出的专门的长模式发现算法Max-Miner算
法。此算法按照启发式知识对项进行排序，以提高发现长模式的效率。在某
些数据集上Max-Miner算法比Apriori算法快1到2个数量级，而且其运行时
间与最大高频集数目和数据库大小成线性关系，与最长高频集的长度无关。
Apriori算法适用的前提之一是对于所有高频集使用相同的最小支持度。如
果在数据库中存在出现频率较低的项（称为稀疏项），同时用户对这些稀疏
项又比较感兴趣，那么需要使用可变的最小支持度以发现包含稀疏项的高频
集，同时不发现太多的用户不感兴趣的高频集。Lee等[91]将数据库根据项
出现频率分为几部分，然后对每部分应用不同的最小支持度进行高频集发
现。此方法难以发现跨越不同部分的高频集。而Han等[80]将若干相关的稀
疏项合并为高层次概念的项，以增加稀疏项的支持度，但这种方法无法发现
包含单个稀疏项的高频集。1999年，Liu等[92]提出的MSApriori算法是
Apriori算法的一种推广。此算法赋予每个项一个最小项支持度（MIS），并
以高频集所包含的项的最小项支持度作为高频集支持度的推广定义。通过将
项根据其MIS值从小到大排序，既可满足推广的高频集的逆单调性。2000
年，Wang等[93]提出Adaptive Apriori算法，将Apriori算法推广到使用
可变的最小支持度的情况。
发展方向
高频集发现算法发展到目前为止，已经获得了长足的进步。作为许多面向应
用的数据挖掘技术的基础，提高高频集发现算法的性能、满足不同应用背景
下的不同要求，依然是一项值得研究的课题。高频集发现算法的发展一方面
离不开有效的基本算法框架（比如Apriori类算法、FP-growth算法等）上
的突破，另一方面也离不开合理的问题抽象。支持度/可信度问题框架及其
关联规则发现算法所获得的广泛认同，得益于问题表达上的简单又不失其合
理有效。既能够找到高效的算法，使其在大型数据库上的有效运行成为现
实，又能够满足顾客购物分析、网络故障分析等实际应用的需要。因此，将
来高频集发现算法的进一步发展也离不开在这两方面的努力。
除此之外，还存在以下几个研究重点：
(1)	进一步发展以TreeProjection和FP-Growth为代表的新的高效算
法。在许多数据集上的实验结果已经证明了这些算法的效率。可在可扩展
性、并行化上作更多的研究工作，也可结合随机采样方法和分块方法以进一
步提高算法效率。
(2)	进一步发展可加入约束条件的算法以提高算法效率。MultiJoins和
Separate算法等可视为初步的工作。但其约束模型必须是DNF范式，由于
在许多场合用DNF范式表达先验知识非常繁琐，几乎不可行，因此发展更有
表达能力的约束模型及其高效实现算法，是很有意义的工作。
(3)	进一步发展长模式发现算法。在生物信息学、文本挖掘等许多重要
应用领域，存在大量超长模式，其发现算法必定和销售分析等短模式发现方
法存在本质差别。目前的MaxMiner算法使用一定的启发式方法，能够得到
比Apriori算法高1到2个数量级的速度。但其性能依然不能令人满意。如果
结合更多的启发式知识，以及使用近似搜索方法，MaxMiner算法的性能应
可得到进一步提高。
(4)	现在的高频集发现算法大多是在纯文件中进行挖掘的，如何将这些
算法整合进数据库管理系统，以真正实现数据库中知识发现的初衷，是一个
必须考虑的问题。由于不可能存在一种算法对不同的应用要求都是高效的，
所以这个问题的关键在于将各种算法分解细化为各个标准环节，为其制定标
准化的统一的调用接口，以便根据不同的应用要求将不同的模块拼接起来完
成任务。这种对算法的进一步分解和调用接口的标准化有助于研究人员的分
工合作，减少不同算法中的冗余重复部分，也有助于算法应用人员根据应用
特性组合各标准环节，对症下药，以最优的方式解决各种应用领域问题。

[1]	Agrawal R., Imielinski T, Swami A. 1993. Mining association 
rules between sets of items in large databases. In Proc. 1993 
ACM-SIGMOD Int. Conf. Management of Data, Washington, 
D.C., May 1993. 207-216
[2]	Brin S, Motwani R, Silverstein C. 1997. Beyond market basket: 
Generalizing association rules to correlations. In Proc. 1997 
ACM-SIGMOD Int. Conf. Management of Data, Tucson, 
Arizona, May 1997. 265-276.
[3]	Silverstein C, Brin S, Motwani R, Ullman J. 1998. Scalable 
techniques for mining causal structures. In Proc. 1998 Int. Conf. 
Very Large Data Bases, New York, NY, August 1998. 594-605.
[4]	Agrawal R. Srikant R. 1995. Mining sequential patterns. In Proc. 
1995 Int. Conf. Data Engineering, Taipei, Taiwan, March 1995. 
3-14
[5]	Parthasarathy S, Zaki M.J, Ogihara M, Dwarkadas S. 1999. 
Incremental and interactive sequence mining, In ACM 
International Conference on Information and Knowledge 
Management (CIKM99). Nov 1999.
[6]	Srikant R, Agrawal R. 1996. Mining sequential patterns: 
Generalizations and performance improvements. In 5th Intl. 
Conf. Extending Database Technology, Mar. 1996.
[7]	Mannila H, Toivonen H. 1996. Discovering generalized episodes 
using minimal occurrences. In 2nd Intl. Conf. Knowledge 
Discovery and Data Mining.
[8]	Mannila H, Toivonen H, Verkamo A. I. 1997. Discovery of 
frequent episodes in event sequences. Data Mining and 
Knowledge Discovery. 1:259-289.
[9]	Ng R, Lakshmanan L. V. S, Han J, Pang A. 1998. Exploratory 
mining and pruning optimizations of constrained associations 
rules. In Proc. 1998 ACM-SIGMOD Int. Conf. Management of 
Data, Seattle, Washington, June 1998. 13-23.
[10]	Han J, Gong W, Yin Y. 1998.Mining Segment-Wise Periodic 
Patterns in Time-Related Data. KDD98.
[11]	Han J, Dong G, Yin Y. 1999. Efficient mining of partial periodic 
patterns in time series database. In Proc. 1999 Int. Conf. Data 
Engineering (ICDE'99), Sydney, Australia, April 1999. 
[12]	Ozden B, Ramaswamy S, Silberschatz A. 1998. Cyclic 
association rules. In Proc. 1998 Int. Conf. Data Engineering 
(ICDE'98), Orlando, FL, Feb. 1998. 412-421.
[13]	Aggarwal C, Sun Z, Yu P. 1998. Online Algorithms for Finding 
profile association rules. In Proc. 1998 ACM-SIGMOD Int. Conf. 
Management of Data, Seattle, Washington, June 1998. 86-95.
[14]	Lu H, Han J, Feng L. 1998. Stock movement and n-dimensional 
inter-transaction association rules. In Proc. 1998 SIGMOD 
Workshop on Research Issues on Data Mining and Knowledge 
Discovery (DMKD'98), Seattle, Washington, June 1998. 12:1-7.
[15]	Tung A. K. H, Lu H, Han J, Feng L. 1999. Breaking the Barrier 
of Transactions: Mining Inter-Transaction Association Rules. 
KDD99. 1999.
[16]	Houtsma M, Swami A. 1995. Set-oriented Mining for 
Association Rules in Relational Databases. In Proceedings of the 
11th International Conference on Data Engineering. March 
1995, 24-32.
[17]	Agrawal R, Srikant R. 1994. Fast algorithms for mining 
association rules. In Proc. 1994 Int. Conf. Very Large Data 
Bases, Santiago, Chile, September 1994. 487-499.
[18]	Park J.S, Chen M.S, Yu P.S. 1995. An effective hash-based 
algorithm for mining association rules. In Proc. 1995 ACM-
SIGMOD Int. Conf. Management of Data, San Jose, CA, May 
1995. 175-186.
[19]	Savasere A, Omiecinski E, Navathe S. 1995. An efficient 
algorithm for mining association rules in large databases. In 
Proc. 1995 Int. Conf. Very Large Data Bases, Zurich, 
Switzerland, Sept. 1995. 432-443,
[20]	Brin S, Motwani R, Ullman J, Tsur S. 1997. Dynamic Itemset 
counting and implication rules for market basket data. 
SIGMOD97, 255-264.
[21]	Zaki M. J, Parthasarathy S, Li W, Ogihara M. 1997. Evaluation 
of Sampling for Data Mining of Association Rules. In 7th Intl.