关联规则是等人首先提出的的一个重要R.Agrawal KDD 研究内容，近年来受到了数据库界的广泛关注。关联规则是寻找在同一个事件中出现的不同项的相关性，即找出事件中频繁发生的项或属性的所有子集，以及它们之间应用相互关联性。关联规则最早用于发现顾客交易数据库中不同商品间的联系，后来诸多的研究人员对关联规则的挖掘问题进行了大量的拓展和研究。他们的工作包括对原有算法的优化，如引入并行的思想，以提高算法的效率，对关联规则的应用进行扩展。关联规则挖掘具有计算量大，负载集中的特点。而I/O 且许多关联规则的实际应用涉及到海量数据。在这种情况下，即使对算法进行了优化，在单处理机上使用串行算法进行挖掘所需要的时间可能也是无法接受的。其主要原因在于单处理器本身受到内存和带宽的限制。因此，必须依靠I/O 高性能并行计算来有效地完成挖掘任务。关联规则的基本概念
1 关联规则的形式化描述如下：
{}12,,...,m i i i 令为项目集，为事物数据库，其中每I = D I T ?个事物是一个项目子集，并另有一个唯一的事物标
T ( )T X ?识符。如果，则事物包含项目集。
TID T X Y X ?I Y I X ??,一个关联规则是形如的蕴涵式这里并 , ,Y X ∩Y X ?且ф。规则在交易数据库中的支持度
= D (是交易数据库中和的交易数与所有交易数之比，
support)X Y Y X ?记为，即support(
)Y X ?{
}D D T T Y X T /,:∈?∪support( )= Y X ?规则在交易数据库中的可信度指包
D (confidence)含和的交易数与包含的交易数之比，记为
X Y X Y X ?，即
confidence( )confidence(Y X ?{}{}D T T X T D T T Y X T ∈?∈?∪,:/,: )=
给定一个交易集，关联规则的挖掘问题就是产生支持
D 度和可信度分别大于用户给定的最小支持度和最
(minsupp)小可信度的关联规则。
(minconf)关联规则的发掘分为两个步骤：找出所有支持度大(1)于最小支持度的频集；从频集中产生期望的规则。(2)串行关联规则挖掘算法2 目前所有并行关联规则算法都是在相应的串行算法的基础上提出的。本文首先对这些串行算法进行介绍和分析。
算法2.1 Apriori-like 在各种关联规则挖掘算法中，最经典、最广泛使用的就是等Agrawal [2]设计的算法，其核心思想是基于频集理Apriori 论的递推方法。首先产生频繁项集，然后是频繁项集，1-2-直到有某个值使频繁项集为空，算法停止。这里在第次r r-k 循环中，过程先通过对两个只有一个项不同的属于的频
k-1集做连接产生候选项集的集合。然后验证候选项集
(k-2)-k-k-中的每个元素来决定是否将其加入频集，这里的验证过程k-是算法性能的一个瓶颈。这个方法要求多次扫描数据库，这就需要很大的负载。I/O
等提出了一个高效地产生频繁集的基于杂凑Park (hash)的算法：算法。通过实验Dynamic Hashing and Pruning(DHP)可以发现寻找频集的主要计算是在生成频繁项集上。2-DHP 利用一个杂凑表在计算频繁项集时先大概计算出项集的1-2-支持度，从而减少了候选项集的数量。还采用了数据2-DHP 库修剪技术，通过修剪掉那些不包含频集的事物集以减小下一次循环中数据库的大小。然而，这种修剪技术的优化并不显著。其主要原因在于只能通过过滤对数据库执行逻辑上的
并行关联规则挖掘综述
尚学群，沈均毅
西安交通大学电信工程学院软件研究所，西安( 710049 )
摘要： 关联规则发现作为数据挖掘的重要研究内容，在许多实际领域内得到了广泛的应用。因为在挖掘过程中涉及到大量的数据和计算，高性能计算成为大规模数据挖掘应用的一个重要组成部分。该文介绍了当前并行关联规则挖掘方面的研究进展，对一些典型算法进行了分析和评价，从并行度、负载平衡以及和数据库的集成等方面展望了并行关联规则挖掘的研究方向。关键词： 数据挖掘；关联规则；并行算法
Survey of Parallel Association Rule Mining
，SHANG Xuequn SHEN Junyi
(Software Institute,School of Telecom Engineering, Xi'an Jiaotong University, Xi'an 710049)
【】Abstract Due to the huge size of data and amount of computation involved in data mining, high-performance computing is an essential
component for any successful large-scale data mining application. This paper provides a survey of the study in parallel association rule generation, reviews and analyses some typical algorithms, views the trend of parallel association rule mining based on the kind of parallelism exploited, the load balancing strategy used, and the integration with databases. The goal of this paper is to serve as a reference for both researchers and practitioners interested in the state-of-the-art in parallel association rule mining.【】Key words ；；Data mining Association rules Parallel algorithms
第30卷 第14期Vol.30 № 14计 算 机 工 程Computer Engineering
2004年7月 July 2004
?发展趋势/热点技术 ?
中图分类号： TP182
文章编号：1000—3428(2004)14 —0001—03
文献标识码：A
修剪，任何物理上的修剪意味着在每次循环中要改写数据库，这是不切实际的。
等提出了一种基于划分的算法。这种Savasere(partition)
算法把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集。然后把产生的频集合并，用以生成所有可能的频集，最后计算这些频集的支持度。算法很大程度上减小了负载。然而在处理高Partition I/O
项集时存在一些问题，而且它还有频集的错误处理的缺陷。
等提出的，也是基于划分Brin Dynamic Itemset Counting(DIC)
的一种算法。它通过在一个循环中生成不同长度的候选集以减少数据库扫描的次数，有效地改进了算法在低层的效率。然而该算法在同构数据的情况下具有较好的性能。例如，多数分块有相似的频集分布。否则，可能需要比更
DIC Apriori
多的对数据库的扫描。
在他的硕士论文中提出了种基于和Muellel4Apriori
的算法：算法，基于划分的算法，Partition SEAR TID SPTID
基于划分的算法和算法。算法与
SPEAR SPINC SEAR Apriori
算法相似，只是该算法用一个前缀数取代杂凑数
(prefix tree)
来存储候选项集，而且引入了一个循环绑定(hash tree)
的优化策略，即只要内存允许在一个循(pass bunding)
环中可生成不同长度的候选集，这样在对数据库的一
次扫描中就可以计算所有当前候选集的支持度。实验
表明，算法优于其他算法，具有较好的性能。
SEAR
等在论文中提出了基于数据的垂直分布的关Zaki
联规则发现算法。其中最简单的是算法，性能最
Eclat
好的是算法。当前多数关联规则挖掘算法采MaxClique
用的是水平数据分布方式，即数据由一系列事物构
成。使用这种格式，计算负载主要集中在支持计数
上。而且，数据的水平分布迫使每次循环均需遍历整
个数据库或每个局部划分。数据的垂直分布是指数据
集由一系列项目构成。数据垂直分布的优点在于可以
通过简单地链接任意两个子集生成候选项目
(k-1)-k-
集，不需要复杂的数据结构，无须对数据库进行遍历。
hash
以上介绍的都是基于的关联规则挖掘算法。即使
Apriori
已经进行了一定的优化，但是方法仍存在一些固有的
Apriori
无法克服的缺陷：可能产生大量的候选集；对数据库
(1)(2)
进行多次扫描。
算法
2.2 FP-growth
等提出了一种富有创新性的方法，即方Han FP-growth 法。这种算法采用了分而治之的策略，经过第次扫描之
1
后，把数据库中的频集压缩到一棵频繁模式树中，
(FP-tree)
同时依然保留其中的关联信息。随后再将划分为一些
FP-tree
条件库，每个库和一个长度为的频集相关。然后再对这些
1
条件库分别进行挖掘。只需对数据库进行二次扫
FP-growth
描，而且避免了产生大量候选集的问题。实验表明，FP-对不同长度的规则具有很好的适应性，同时在效率上growth
较之算法有很大的提高。
Apriori
并行关联规则挖掘算法
3
尽管关联规则的描述很简单，但是它却是一个计算和集中的任务。假设给定个项目集，那么存在
I/O m2m个
子集可能是频集。处理如此指数级的数据需要大量的磁盘I/。实验证明，在限定交易长度的情况下，关联规则的挖掘O
和数据库的大小呈线性递增的关系。而且，随着项目集的数量和维度的增加，以及交易数据库大小的增加，串行算法显然不具有良好的性能。因此必须依靠高性能并行计算来有效地完成挖掘任务。然而利用多处理器系统进行关联规则发现，要想获得好的性能并非易事。其中涉及到的问题包括：减小同步和通信，负载平衡，数据放置和减小磁盘。下
I/O
面从并行度、负载平衡、以及实现平台等方面对当前主要的并行关联规则发现算法进行介绍和分析。
基于的并行关联规则挖掘算法
3.1 Apriori
多处理器体系结构有种形式：共享内存系统
3(share-
，共享磁盘系统和不共享memory system)(share-disk system)
系统。在共享内存系统中，所有处理(share-nothing system)
器共享一个通用的，非常大的内存。这样任何一个处理器都可以访问所有的数据，具有动态负载平衡。在这种系统中，想要获得好的并行性能，关键在于处理好数据的同步问题。在共享磁盘和不共享系统中，数据分布在各个处理器节点上，它们之间的通信和是通过消息传递来实现的。因此
I/O
获得好的并行性能的关键就在于合理分布数据，以取得好的负载平衡，减小通信代价。
：数据项集的数目：处理器的数目：候选集的大小
N P M
图算法
1 CD
等
Agrawal[1]提出了种基于的并行关联规则挖掘
3Apriori
算法：，和Count Distribution(CD)Date Distribution(DD)
算法。它们是在不共享的
Candidate Distribution IBM POWER 并行系统上实现的。算法的主要计算代价是候选 SP2Apriori
集的生成及其支持度的计算。因此高度并行地完成此过程必然可以大大地降低算法执行的时间，提高算法的性能。一种并行的方法是复制候选集算法见图，另一种方法是
(CD)(1)
划分候选集算法见图，再就是将两种方法合成，即(DD)(2)
部分划分候选集的方法。算法将生
(Candidate Distribution)CD
成候选集的过程复制到所有处理器上。每个处理器生成一个完整的候选杂凑树，根据本地数据库分块独立地计算出候选项的局部支持计数，然后通过在所有处理器之间交换局部支持计数来得到全局支持计数。因为在处理器间只需交换支持数而不是合并不同的杂凑树，这种算法具有较小的通信负载。然而它并没有实现杂凑树构成过程的并行化，在处理器数量增加的情况下，将成为算法执行的瓶颈，而且它也没有有效地利用内存。算法用一种循环的方式将候选集划分
DD
到每个处理器中，然后由每个处理器负责计算本地存储的候选子项集的支持计数。这个过程需要每个处理器既要扫描分配给该处理器的数据库，还要扫描其他处理器上的数据库，从而导致了很高的通信负载，降低了该算法的性能。为了交
—2
—
换各自的支持计数或频集，算法和算法都需要在每次
CD DD 循环结束时进行处理器之间的同步。算Candidate Distribution 法，在循环中划分候选集，同时选择性地复制数据库以便l 每个处理器可以独立地生成候选集和全局支持计数。实验表明，较之其他两种算法，算法的性能最好。
CD ：数据项集的数目：处理器的数目：候选集的大小
N P
M 图算法
2 DD 算法是等提出的并行算法。该算法类似于
PDM Park DHP 算法，所有处理器含有相同的杂凑表和候选集。并行候CD 选集生成的过程，是通过每个处理器生成一个候选子项集，然后交换所有处理器上的子项集生成全局候选集来实现的。每个处理器通过一个杂凑表生成项集的局部支(hash table)k-持数和项集的近似局部支持数，然后通过全局广播的方k+1-式交换项集的局部支持数而得到项集的全局支持数。由k-k-于项集杂凑表很可能非常大，直接交换的代价将是非常2-高。该算法采用了一种优化策略，即只交换那些支持数大于最小支持数的项集。算法实现了杂凑表构成的并行，PDM 性能优于算法。
CD 等提出了种类似文献的算法：Shintani 3[1]Non-，和算法，是在Partition Simple-Partition Hash-Partition Apriori 不共享的有个节点的系统上实现的。64Fujitsu AP1000DDV 算法本质上和算法相同，不同之处在Non-Partition Apriori CD 于它使用了一个控制处理器完成全局支持数的累计过程。算法和算法一样。Simple-Partition Apriori DD Hash-Partition 算法类似于算法，采用杂Apriori Candidate Distribution 凑函数将候选集分配给处理器，减小了处理器间发送局部数据库分块的通信负载。
和Intelligent Data Distribution(IDD)Hybrid 算法是等Distribution(HD)Han [3]通过对算法的改进而DD 提出的并行关联规则挖掘算法，是在不共享的有个128节点的系统上实现的。在算法中，采用Cray T3D IDD 一种基于环的全局广播方式将本地数据库分块发送给其他所有的处理器。较之算法每个处理器都必须DD (发送数据给其他所有的处理器，只是在相邻的处)IDD 理器间执行一次点对点的通信，消除了算法存在的DD 通信竞争的问题。算法采用一个基于前缀的划分IDD 方法生成候选子项集，即每个处理器过滤掉那些不包含前缀的事物项集，从而减少冗余。算法合成了
HD 算法和算法。该算法将个处理器划分为个大小相CD IDD P G 等的组，视每个组为一个超级处理器，执行算法。在每CD 个组内，执行算法。在算法中，事物数据库水平分IDD HD 布在个超级处理器上，候选集被划分在每个组内的个
G P/G 处理器上。此外，在每个循环中，动态地决定组的数量。算法有效地减小了通信负载，且具有较好的负载平衡。
IDD 等提出的Zaki Common Candidate Partition Database 算法，以及等提出的(CCPD)Cheung Asynchronous Parallel 算法是在共享内存的系统上实现的。在Mining(APM)CCPD 算法中，所有处理器共享一个候选杂凑树，而数据库被逻辑
划分为大小相等的分块。该算法采用锁机制来实现杂凑树生成过程的并行。论文中指出，由于杂凑本身的特点，杂凑树具有很差的数据放置，加之共享杂凑树可能会造成支持计数时产生错误的结果。针对上述问题，他们提出了一些优化策略，如杂凑树平衡、优化内存布置(hash tree balancing)(memory 等。算法是基于的placement optimization)APM DIC 并行算法，对数据扭曲非常敏感，并且认为数据是同构的。在算法中，采用全局修剪技术来减APM 小候选项集的大小，这在存在大的数据扭曲的时2-候非常有效。在第一次循环中，数据库被逻辑划分为大小相等的块，对每个分块执行局部支持计数，
然后对它们进行群集，用以生成候选项集。接下来，数据2-库被划分为同构的分块，每个处理器在局部分块上独立地执行算法。这些在共享内存系统上实现的基于并行DIC Apriori 算法存在着一些严重的缺陷，如极高的负载、磁盘竞争I/O 和欠佳的数据放置。并行算法
3.2 FP-growth 等Zaiane [5]提出了基于的FP-growth Multiple Local 算法，它是在共享内存的有Frequent Pattern Tree(MLFPT)64个处理器的系统上实现的。算法只需对数据库进SGI MLFPT 行二次扫描，避免了生成大量候选集的问题，而且通过在挖掘过程的不同阶段采用不同的划分策略实现最佳的负载平衡。在频繁模式树生成阶段，数据库被划分为大小(FP tree)均等的分块，每个处理器生成一个局部频繁模式树(local FP 见图。在挖掘阶段，所有处理器共享这些局部频繁模tree)(3)式树，并生成相应的频繁项集的条件库，很大程度上减少1-了资源竞争的现象。
图局部频繁模式树的生成
3 结论与展望
4 本文讨论了现有的关联规则挖掘算法，并从实现平台、下转第页
(13)
—3
—
(21) for(each unmarked rule r a ∈?a ) do (22) append r a to ? ; (23) ? = sort(?)
算法首先对两个规则集合中的规则按照各自的优先级的降序分别排序(1行)。算法的核心就是要对两个规则集合中的规则进行对比，选择置信度较高的规则，裁减冗余规则。对?d 中的每个规则r d ，分析所有在?a 中的未标记规则。如果在?a 中找到和规则r d 有相同前件的规则r a ，并且它们的分类结果相同的话，则两个规则完全相同，就将该规则插入到?中，并设其精度为两个规则中较高的精度，同时标记r a (4-6行)；当两个规则前件相同但分类结果不同，如果两个规则分类精度相同，就将具有较高支持度的规则插入到?中并标记r a (7-10行)，否则就将具有较高精度的规则插入到?中并标记r a (11-13行)。如果r d 的前件被r a 的前件包含，并且如果r d 的精度高于r a 的精度，就可以裁减掉r a ，将r d 插入到?中并标记r a ；反之如果r a 比r d 更一般，且r a 的精度高于r d ，则将r a 插入到?中，同时标记r a (14-17行)。如果上述测试都不成立的话，就仅仅将r d 插入到?中(18行)。这样在外层循环完成后，就对?d 中的每个规则进行了处理。但是?a 中可能还留有一些规则未被处理(没有被标记)，就将这些未标记的规则插入到?中，并对?进行排序(21-23行)，最后就得到了所需要的最终分类规则集合?。
3 实验与分析
为了检验两套规则集的一致性和部分冲突性以及合并方法的性能，进行了一个实验。从Internet 上收集了136部MPEG 编码格式的视频剪辑，每个视频剪辑有各自不同的长度、帧尺寸以及帧速率。这些视频剪辑的类别分布情况为：爱情片(25部)、动作片(14部)、广告(34部)、音乐电视(52部)和足球比赛录像(11部)，总共有5个视频分类。值得注意的是，视频类别的确定往往归结为观众主观观点和视频语义的微妙差别。而当进行自动分类时，研究者必须仔细地选取那些相对容易定义和一般被广泛认可的风格类别。因为仅考虑了视频的静态视觉属性，所以对视频分类应当谨慎地加以选择，任何两个预定义视频分类应当在其视觉内容上能够有明显的差异。举例来说，运动类视频可以有许多子类，比如足球、篮球、赛车，它们具有完全不同的视觉内容，应当将它们定义为不同的视频分类。经过视频分割后我们得到了视频特征属性数据库，其格式如第1节所述。随机选取80%的视频特征属性元组作为训练视频集，其余的20%的作为测试视频集。
首先使用决策树和分类关联规则挖掘分别对训练视频属性数据集进行挖掘，提取出决策树分类规则集?d 和分类关联规则集?a ，对它们的一致性和部分冲突进行了验证。分别挖掘出了26条决策树规则，29条关联分类规则。然后使用了
测试视频集来测试这两套规则，用分类预测的准确率来度量这两套规则的分类精度。用决策树规则集进行预测准确率为76.47%，错误预测的样本数为4；用分类关联规则集的准确率为82.35%，错误预测的样本数是3，如表1所示。在两套规则错误预测的视频样本中，仅有一个样本是相同的，其余都不同，这样就表明两套规则之间具有互补性，可以合并它们以提高分类预测精度。
最后，比较了合并后规则集?和初始的两个规则集?d 和?a 的分类预测精度。根据2.3节的规则集合并算法，将两个规则集?d 和?a 合并后得到的新规则集?的大小是51条规则，用它们对测试视频集进行分类，得到的正确分类预测率为88.23%，如表1所示。最终的规则集?比?d 和?a 具有更高的分类精确度。
表1 实验结果
规则集 规则数 准确率 错误数 ?ｄ ２６ ７６．４７％ ４ ?ａ ２９ ８２．３５％ ３ ?
５１
８８．２３％
２
4 总结
本文基于数据挖掘技术，提出了一个新颖的基于内容的自动视频分类方法。首先进行视频分割，提取视频特征属性并形成视频特征属性数据库。然后在这个视频特征属性数据库提取决策树分类规则、挖掘关联分类规则。最后利用合并两个分类规则集的算法，生成了分类精度更高的合并规则集。实验结果表明，使用决策树规则和分类关联规则进行分类预测具有较好的一致性，并且它们之间有互补性，对它们进行合并后得到的合并规则集具有更高的分类预测精度。
参考文献
1 Zhang H J, Kankanhalli A,Smoliar S W. Automatic Partitioning of Full-motion Video. Multimedia Systems,1993,1(1):10-28
2 Yuan Y,Song Q B,Shen J Y.Automatic Video Classification Using Decision Tree Method.Proceedings of the First International Conference on Machine Learning and Cybernetics,Beijing,2002-11-04: 1153-1157
3 Quinlan J R.C4.5: Programs for Machine Learning. SanMateo, CA: Morgan Kaufmann, 1993
4 Liu B,Hsu W,Ma Y.Integrating Classification and Association Rule Mining.Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, [KDD 98],New York, NY, 1998-08:80-86
5 Li Wenmin,Han Jiawei,Pei Jian.Cmar:Accurate and Efficient Classi- fication Based on Multiple Class-association Rules.In IEEE Interna- tional Conference on Data Mining, 2001
收稿日期:2001 12 14;修返日期:2002 04 28 基金项目:湖北省自然科学基金资助项目(2001ABB006) 关联规则挖掘综述 * 颜雪松,蔡之华,蒋良孝,贺 毅 (中国地质大学信息工程学院,湖北武汉430074) 摘 要:介绍了关联规则挖掘的一般概念,并进一步导出它的一般框架;同时对一些典型算法进行了分 析和比较,介绍了关联规则的应用;最后展望了关联规则挖掘的未来研究方向。关键词:关联规则;频繁项目集;深度优先遍历;宽度优先遍历 中图法分类号:TP301 6 文献标识码:A 文章编号:1001 3695(2002)11 0001 04 Survey of Association Rule Mining YAN Xue song,CAI Zhi hua,JIANG Liang xiao,HE Yi (Colle ge o f Information Enginee ring ,China Unive rsit y o f Geosc ienc es,Wuhan Hubei 430074,China) Abstract:In this paper we explain the fundaments of association rule mining and moreover derive a general framework.At the same time compares and analyses some typical algorithms,introduces the application of the association rules.At the end,views some future directions in association rule generation. Key w ords:Association Rule;Frequent Itemsets;DFS;BFS 1 引言 面对海量的存储数据,如何从中发现有价值的信息或知识是一项非常艰巨的任务。数据挖掘就是为了满足这种要求而迅速发展起来的。数据挖掘是指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。数据挖掘是人工智能和数据库发展相结合的产物,是目前国际上数据库和信息决策系统最前沿的研究方向之一,已引起了学术界和工业界的广泛关注。目前研究的主要目标是发展有关理论、方法和工具,以支持从大量数据中提取有价化的知识和模式。在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题。它是由R.Agra wal 等人首先提出的。关联规则的一个典型例子就是: 90%的客户在购买面包的同时也会购买牛奶 ,其直观意义为顾客在购买某些商品的时候有多大的倾向会购买另外一些商品。 2 关联规则的基本概念 假设T 是事务的集合,在T 中的每一个事务都是项目集I 的子集。假设C 是I 的一个子集,我们定义C 的支持度如下: (C)=|{t|t !T,C t}|。 (C)表示包含在C 中的事务的数目。例如图1所示的事务集。事务的项目集I 是{Bread,Beer,Coke,Diaper,Milk}。{Diaper,Milk}的支持度是 {Diaper,M ilk}=3,而 {Diaper,Milk, Beer}=2。 TID Item s 1Bread,Coke,Mil k 2Beer,Bre ad 3Beer,Coke,Diape r,Mil k 4Beer,Bre ad,Diape r,Mil k 5 Coke,Dia pe r,Mil k 图1 Transactions from Supermarket 关联规则可描述为:!XY,X I,Y I 。关联规则X !Y 的支持度s 定义为: (X ?Y)/|T|,置信度 定义为 (X ?Y )/ (X)。例如,假设一条规则{Diaper,Milk}!{Beer},表示如果Diaper 和Milk 在一个事务中,就意味着Beer 也包含在这个事务中。这条规则的支持度是: (Di aper ,Milk,Beer)/5=40%。置信度为 (Diaper,Milk,Beer)/ (Diape r,Milk)=66%。如果一条规则的置信度很高的话,就说明这条规则很重要,因为它可以在规则中给项目关联提供精确的预测。同样的,规则的支持度也很重要,它可以暗示在事务中这条规则的出现频率有多高。支持度很低的规则通常是引不起人们的兴趣的。 这就是为什么大多数的算法[2] 忽视那些不能满足用户给定的最小支持度条件的规则的原因。这种用给定最小支持度过滤规则的方法可以减少产生的关联规则的数量,以便于管理。因为算法可能产生的规则的数量和项目集I 的子集的数量是成比例的,可能达到2|I|,因此,这种过滤在实际应用中是必需的。 发现关联规则的任务就是发现所有形如X !Y 的规则,规则的支持度大于或等于给定的最小支持度,规则的置信度大于或等于给定的最小置信度。发现关联规
关联规则挖掘综述 潮娇娇 摘要：关联规则挖掘是数据挖掘中的一个很重要的研究内容之一，近年来很多国内外研究人员对其进行了大量的研究。为了更进一步的了解关联规则挖掘技术，并掌握其发展方向和目前的研究现状。本文对关联规则挖掘技术进行了相关综述。首先介绍了关联规则的基本概念，其次分析了近年来一些经典关联规则算法的改进，并概述了相关算法在实际中的应用。最后对关联规则挖掘技术未来的发展趋势进行了讨论。 关键字：关联规则；算法；数据挖掘； Abstract: association rule mining is one of the important data mining research contents in this year, many domestic and foreign researchers have done a lot of research on it. In order to understand further the association rule mining technology, and grasp the development status and direction of research at present. This article of association rule mining technology related review. Firstly introduces the basic concepts of association rules, then analyzes the improvement of some classical algorithm of association rules in recent years, and summarizes the application of related algorithms in practice. At the end of the association rule mining technology development trend in the future are discussed. Key words: association rules; algorithms; data mining; 引言 随着计算机技术与数据库技术的飞速地发展，数据资源越来越多。但巨大的数据，依然没有解决我们的信息需求问题，针对这种情况，产生了数据库的数据挖掘。与传统技术相比，数据挖掘技术是一种新型的信息处理技术，能够自动和智能地把位置数据或者大量数据中潜在信息转换成人们需要的信息和知识的技术。它可以从数据库提取有用的知识、规律以及更高层次的信息，对这些进行分析，帮助人们更有效的利用海量数据中存在的价值。目前对数据挖掘的发展趋势及研究方向主要集中在数据挖掘的数据总结、分类、聚类、关联规则等方面。而关联规则挖掘作为数据挖掘的核心内容之一，进来得到了很快的发展。并已经成为当今数据挖掘的热点。为此，对关联挖掘技术的研究具有重要的意义。本文将重点介绍关联规则挖掘技术的相关研究。主要对近年来关联规则挖掘技术的算法改进进行综述以及未来的发展方向。 1、关联规则基本概念 1.1 相关介绍 关联规则作为数据挖掘的核心研究内容之一，它是大量数据中发现信息之间可能存在的某种关联或者相关联系。通过分析这些挖掘出的数据联系，可以在现实中帮助我们预测或决定某些事情将会发生。有效的提高了我们制定出准确的决策。目前，关联规则挖掘技术广泛应用于金融、互联网、医学等多个领域。最早的关联挖掘是未来发现交易数据库中不同商品之间的联系，通过分析这种联系获得有关购买者的一般的购买模式。从而有助于商家合理地安排进货、库存及货架设计，更好的制定发展计划和规避风险。
数据挖掘中关联规则挖掘的应用研究 吴海玲，王志坚，许峰 河海大学计算机及信息工程学院，江苏南京（210098） 摘 要：本文首先介绍关联规则的基本原理，并简单概括其挖掘任务，然后说明关联规则的经典挖掘算法Apriori 算法，通过一个实例分析进一步明确关联规则在CRM 中的应用，最后展望了关联规则挖掘的研究方向。 关键词：数据挖掘，关联规则，Apriori 算法，CRM 引言 关联规则是表示数据库中一组对象之间的某种关联关系的规则，关联规则挖掘的主要对象是交易(Transaction)数据库。这种数据库的一个主要应用是零售业，比如超级市场的销售管理。条形码技术的发展使得数据的收集变得更容易、更完整，从而可以存储大量的交易资料。关联规则就是辨别这些交易项目之间是否存在某种关系。例如：关联规则可以表示“购买了商品A 和B 的顾客中有80％的人又购买了商品C 和D”。这种关联规则提供的信息可以用作商品目录设计、商场货架的布置、生产安排、具有针对性的市场营销等。 [1] 1 关联规则的基本原理 设Ｉ＝｛i 1，i 2，……，i m ｝是项的集合，设任务相关的数据D 是数据库事务的集合，其中每个事务T 是项的集合，使得T I 。每一个事务有一个标识符，称作T ID 。设X 是一个项集，事务T 包含X 当且仅当X T 。关联规则是形如X Y 的蕴涵式，其中X I ，Y ?I ，并且X ∩Y ＝?。规则X Y 在事务集D 中成立，具有支持度s ，其中s 是D 中事务包含X ∪Y （即X 和Y 二者）的百分比，它是概率P （X ∪Y ）。规则X Y 在事务集中具有可信度c ，如果D 中包含X 的事务同时也包含Y 的百分比c 。这是条件概率P （X Y ∣）。即是 ??????support(X ?Y)= P （X Y ∪） confidence(X ?Y)= P （X Y ∣） 同时满足最小支持度(minsup)和最小可信度阈值（minconf ）的规则称作强规则[1]。 项的集合称为项集（itemset ）。包含k 个项的项集成为k －项集，例如集合{computer, software }是一个2—项集。项集的出现频率是包含项集的事务数，简称为项集的频率。项集满足最小支持度minsup ，如果项集的出现频率大于或者等于minsup 与D 中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集(frequent itemset) [2]。 2 关联规则的发现任务 关联规则挖掘的问题就是要找出这样的一些规则，它们的支持度或可信度分别大于指定的最小支持度minsup 和最小可信度minconf 。因此，该问题可以分解成如下两个子问题[3]： 1．产生所有支持度大于或等于指定最小支持度的项集，这些项目集称为频繁项目集（frequent itemsets ），而其他的项目集则成为非频繁项目集（non-frequent itemsets ） 2．由频繁项集产生强关联规则。根据定义，这些规则必须满足最小支持度和最小可信度。 关联规则挖掘的问题的主要特征是数据量巨大，因此算法的效率很关键。目前研究的重点在第一步，即发现频繁项目集，因此第二步相对来说是很容易的。
数据挖掘方法综述 [摘要]数据挖掘（DM，DataMining）又被称为数据库知识发现（KDD,Knowledge Discovery in Databases）,它的主要挖掘方法有分类、聚类、关联规则挖掘和序列模式挖掘等。 [关键词]数据挖掘分类聚类关联规则序列模式 1、数据挖掘的基本概念 数据挖掘从技术上说是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。这个定义包括好几层含义: 数据源必须是真实的、大量的、含噪声的、发现的是用户感兴趣的知识, 发现的知识要可接受、可理解、可运用, 并不要求发现放之四海皆准的知识, 仅支持特定的发现问题, 数据挖掘技术能从中自动分析数据进行归纳性推理从中发掘出潜在的数据模式或进行预测, 建立新的业务模型帮助决策者调整策略做出正确的决策。数据挖掘是是运用统计学、人工智能、机器学习、数据库技术等方法发现数据的模型和结构、发现有价值的关系或知识的一门交叉学科。数据挖掘的主要方法有分类、聚类和关联规则挖掘等 2、分类 分类（Classification）又称监督学习（Supervised Learning）。监
督学习的定义是：给出一个数据集D，监督学习的目标是产生一个联系属性值集合A和类标（一个类属性值称为一个类标）集合C的分类/预测函数，这个函数可以用于预测新的属性集合（数据实例）的类标。这个函数就被称为分类模型（Classification Model），或者是分类器（Classifier）。分类的主要算法有：决策树算法、规则推理、朴素贝叶斯分类、支持向量机等算法。 决策树算法的核心是Divide-and-Conquer的策略，即采用自顶向下的递归方式构造决策树。在每一步中，决策树评估所有的属性然后选择一个属性把数据分为m个不相交的子集，其中m是被选中的属性的不同值的数目。一棵决策树可以被转化成一个规则集，规则集用来分类。 规则推理算法则直接产生规则集合，规则推理算法的核心是Separate-and-Conquer的策略，它评估所有的属性-值对（条件），然后选择一个。因此，在一步中，Divide-and-Conquer策略产生m条规则，而Separate-and-Conquer策略只产生1条规则，效率比决策树要高得多，但就基本的思想而言，两者是相同的。 朴素贝叶斯分类的基本思想是：分类的任务可以被看作是给定一个测试样例d后估计它的后验概率，即Pr（C=c j︱d），然后我们考察哪个类c j对应概率最大，便将那个类别赋予样例d。构造朴素贝叶斯分类器所需要的概率值可以经过一次扫描数据得到，所以算法相对训练样本的数量是线性的，效率很高，就分类的准确性而言，尽管算法做出了很强的条件独立假设，但经过实际检验证明，分类的效果还是
关联规则挖掘的过程 关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(Frequentitemsets)，第二阶段再由这些高频项目组中产生关联规则(Association Rules)。 关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(Large Itemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。一项目组出现的频率称为支持度(Support)，以一个包含A与B两个项目的2-itemset为例，我们可以经由公式(1)求得包含{A,B}项目组的支持度，若支持度大于等于所设定的最小支持度(Minimum Support)门槛值时，则{A,B}称为高频项目组。一个满足最小支持度的k-itemset，则称为高频k-项目组(Frequent k-itemset)，一般表示为Large k或Frequent k。算法并从Large k的项目组中再产生Large k+1，直到无法再找到更长的高频项目组为止。 关联规则挖掘的第二阶段是要产生关联规则(Association Rules)。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度(Minimum Confidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。例如：经由高频k-项目组{A,B}所产生的规则AB，其信赖度可经由公式(2)求得，若信赖度大于等于最小信赖度，则称AB为关联规则。 就沃尔马案例而言，使用关联规则挖掘技术，对交易资料库中的纪录进行资料挖掘，首先必须要设定最小支持度与最小信赖度两个门槛值，在此假设最小支持度min_support=5% 且最小信赖度min_confidence=70%。因此符合此该超市需求的关联规则将必须同时满足以上两个条件。若经过挖掘过程所找到的关联规则「尿布，啤酒」，满足下列条件，将可接受「尿布，啤酒」的关联规则。用公式可以描述Support(尿布，啤酒)>=5%且Confidence(尿布，啤酒)>=70%。其中，Support(尿布，啤酒)>=5%于此应用范例中的意义为:在所有的交易纪录资料中，至少有5%的交易呈现尿布与啤酒这两项商品被同时购买的交易行为。Confidence(尿布，啤酒)>=70%于此应用范例中的意义为:在所有包含尿布的交易纪录资料中，至少有70%的交易会同时购买啤酒。因此，今后若有某消费者出现购买尿布的行为，超市将可推荐该消费者同时购买啤酒。这个商品推荐的行为则是根据「尿布，啤酒」关联规则，因为就该超市过去的交易纪录而言，支持了“大部份购买尿布的交易，会同时购买啤酒”的消费行为。 关联规则挖掘通常比较适用与记录中的指标取离散值的情况。如果原始数据库中的指标值是取连续的数据，则在关联规则挖掘之前应该进行适当的数据离散化（实际上就是将某个区间的值对应于某个值），数据的离散化是数据挖掘前的重要环节，离散化的过程是否合理将直接影响关联规则的挖掘结果。
INFO411/911 Laboratory exercises on Association Rule Mining Overview: Association rule mining can help uncover relationships between seemingly unrelated data in a transactional database. In data mining, association rules are useful in discovering consequences of commonly observed patterns within a set of transactions. What you need: 1.R software package (already installed on the lab computers) 2.The file "laboratory_week5.zip" on Moodle. Preparation: 1.Work in a group of size two to three (minimum size of a group is two. But no more than three students are to work together). Penalties apply if a group exeeds these limits. 2.Boot computer into Windows mode. 3.Download laboratory_week5.zip then save to an arbitrary folder, say "C:\Users\yourname\Desktop" 4.Uncompress laboratory_week 5.zip into this folder 5.Start "R" 6.Change the working directory by entering: setwd("C:/Users/yourname/Desktop") (Note that R expects forward slashes rather than backwars slashes as used by Windows.) Your task: Your are to submit a PDF document which contains your answers of the questions in this laboratory exercise. One document is to be submitted by each group. The header of the document must list the name and student number of all students in the group. Clearly indicate which question you have answered. The following link provides a documentation of the association rule module in R (called arules). The link can help you develop a better understanding of the usage and parameters of the association rule package in R: https://www.doczj.com/doc/b06722373.html,/web/packages/arules/arules.pdf Work through the following step and answer given questions: Step1: Familiarize yourself with the arules package in R. Start R and type: library(arules) to load the package. We shall start from the analysis of a small file sample1.csv that contains some transactional data. To load data into R enter: sample1.transactions <- read.transactions("sample1.csv", sep=",") To get information about the total number of transactions in a file sample1.csv enter: sample1.transactions To get a summary of data set sample1.csv enter: summary(sample1.transactions) The data set is described as sparse matrix that consists of 10 rows and five columns. The density of
关联规则挖掘的Apriori算法改进综述 1引言 数据挖掘是一种半自动地从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取出隐含在其中潜在有用的信息和知识的过程。数据挖掘从数据中提取人们感兴趣的可用信息和知识，并将提取出来的信息和知识表示成概念、规则、规律和模式。 数据挖掘，又称数据库中的知识发现(Knowledge Discovery in Database, KDD)，指的是从大型数据库的数据仓库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用信息，换言之，数据挖掘是一个利用各种分析工具在海量数据中，发现模型和数据间关系的过程，这些模型和关系可以用来作出预测。对于数据挖掘技术的研究已引起了国际人工智能和数据库等领域专家与学者的广泛关注，这其中在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题。关联规则是美国IBM Almaden research center的Rabesh Agrawal等人于1993年首先提出的，最近几年在数据挖掘研究领域对关联规则挖掘的研究开展得比较积极和深入[1]。关联规则挖掘是发现大量数据中项集之间有趣的关联或相关关系。随着大量数据不停被地收集和存储，许多业界人士对于从数据库中挖掘关联规则越来越感兴趣。 2 Apriori算法 2.1关联规则挖掘问题的形式化描述 对于经常使用的数据，同一文件的不同版本之间的内容往往会有重复，因此数据冗余比较多，如果采用增量式压缩就可以大大节省磁盘空间。但是这样的数据是压缩的，一旦用户需要查询/恢复数据就需要解压过程，因此这会使系统性能降低。设I={i1，i2，…，im}是由m个不同的项目组成的集合，给定一个事务数据库D，其中的每一个事务T是I中一组项目的集合，即T?I，T有一个唯一的标识符TID。若项集X?I 且X?T，则事务T包含项集X。一条相联规则就是形如X?Y的蕴涵式，其中X?I，Y?I，x∩Y=Φ。相联规则X?Y成立的条件是: (l)它具有支持度s，即事务数据库D中至少有s%的事务包含XY ∪； (2)它具有置信度c，即在事务数据库D中包含X的事务至少有c%同时也包含Y。 关联规则的挖掘问题就是在事务数据库 D 中找出具有用户给定的最小支持度minsup 和最小置信度minconf的关联规则。 2.2 Apriori算法简介 1994 年，Rakesh AgrawalRama 和Krishnan Skrikant 首先提出了Apriori算法[2]，它是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是使用候选项集找频繁项集。Apriori算法使用一种称作逐层搜索的迭代方法k-项集用于搜索以(k+l)-项集。首先，找出频繁1-项集的集合，该集合记作L1，L1 用于找频繁2-项集的集合L2，L2 从用于找L3.如此下去，直到不能找到频繁项集。 3 Apriori算法的改进 3.1 DDApriori算法[3] 从Apriori算法可以看出, 对每一Ci均对数据库扫描一次,而这时有些事务已经对频繁项集的生成不产生作用, 减少数据库 D 内不起作用的事务对于算法来说是很有必要的,本
数据挖掘实验报告（二）关联规则挖掘 姓名：李圣杰 班级：计算机1304 学号：02
一、实验目的 1. 1.掌握关联规则挖掘的Apriori算法； 2.将Apriori算法用具体的编程语言实现。 二、实验设备 PC一台，dev-c++ 三、实验内容 根据下列的Apriori算法进行编程：
四、实验步骤 1.编制程序。 2.调试程序。可采用下面的数据库D作为原始数据调试程序，得到的候选1项集、2项集、3项集分别为C1、C2、C3，得到的频繁1项集、2项集、3项集分别为L1、L2、L3。
代码 #include <> #include<> #define D 4 //事务的个数 #define MinSupCount 2 //最小事务支持度数 void main() { char a[4][5]={ {'A','C','D'}, {'B','C','E'}, {'A','B','C','E'}, {'B','E'} }; char b[20],d[100],t,b2[100][10],b21[100][10]; int i,j,k,x=0,flag=1,c[20]={0},x1=0,i1=0,j1,counter =0,c1[100]={0},flag1=1,j2,u=0,c2[100]={0},n[2 0],v=1; int count[100],temp; for(i=0;i
基于股票时间序列数据的关联规则挖掘研究 Study on Mining Association Rules from Stock Time Series Data 一．引言 随着计算机信息系统的日益普及，大容量存储技术的发展以及条形码等数据获取技术的广泛应用，人们在日常事务处理和科学研究中积累了大量的各种类型的数据。在这些数据中，有很大一部分是呈现时间序列（time series）类型的数据。所谓时间序列数据就是按时间先后顺序排列各个观测记录的数据集[1]，如金融证券市场中每天的股票价格变化；商业零售行业中，某项商品每天的销售额；气象预报研究中，某一地区的每天气温与气压的读数；以及在生物医学中，某一症状病人在每个时刻的心跳变化等等。然而，我们应该注意到：时间序列数据不仅仅是历史事件的记录，更重要的是蕴藏这些数据其中不显现的、有趣的模式。随着时间推移和时间序列数据的大规模增长，如何对这些海量数据进行分析处理，挖掘其背后蕴藏的价值信息，对于我们揭示事物发展规律变化的内部规律，发现不同事物之间的相互关系，为人们正确认识事物和科学决策提供依据具有重要的实际意义。 时间序列数据分析按照不同的任务有各种不同的方法，一般包括趋势分析、相似性搜索、与时间有关数据的序列模式挖掘、周期模式挖掘等[2]。本综述是针对证券业中股票时间序列分析的，试图通过列举、分析有关证券业中股票时间序列数据分析的原理、方法与技术，着重探讨数据挖掘中基于股票时间序列数据的关联规则挖掘的概念、原理技术、实施过程及存在的障碍和问题，以期能有新的发现和领悟。 二．股票时间序列传统研究方法概述 随着我国市场经济建设的发展，人们的金融意识和投资意识日益增强。股票市场作为市场经济的重要组成部分，正越来越多地受到投资者的关注。目前股票投资已经是众多个人理财中的一种重要方式。不言而喻，如果投资者能正确预测股票价格、选准买卖时机，无疑会给投资者带来丰厚的收益。于是，在股票的预测和分析方面出现了大量的决策分析方法和工具，以期能有效地指导投资者的投资决策。目前，我国股市用得较多的方法概括起来有两类[3]：一类是基本分析和技术分析，另一类是经济统计分析。 1．基本分析和技术分析 在股票市场上，当投资者考虑是否投资于股票或购买什么股票时，一般可以运用基本分析的方法对股市和股票进行分析；而在买卖股票的时机把握上，一般可以运用技术分析的方法[4]。 基本分析指的是通过对影响股票市场供求关系的基本因素（如宏观政治经济形势、金融政策、行业变动、公司运营财务状况等）进行分析，来确定股票的真正价值，判断未来股市走势，是长期投资者不可或缺的有效分析手段。 技术分析是完全根据股市行情变化而加以分析的方法，它通过对历史资料（成交价和成交量）进行分析，来判断大盘和个股价格的未来变化趋势，探讨股市里投资行为的可能转折，从而给投资者买卖股票的信号，适合于投资者作短期投资。目前技术分析常用的工具是各种各样的走势图（K线图、分时图）和技术指标（MA、RSI、OBV等）。 2．经济统计学分析
关联规则挖掘综述 摘要：近年来国内外学者对关联规则进行了大量的研究。为了更好地了解关联规则的挖掘技术，对研究现状有更深入的了解，首先本文对数据挖掘技术进行了介绍，接着介绍了关联数据挖掘的基本原理，最后对经典的挖掘算法进行分类介绍。 关键词：数据挖掘；关联规则；算法；综述 1.引言 数据挖掘是从海量的数据里寻找有价值的信息和数据。数据挖掘中常用的算法[1]有：关联规则分析法（解决事件之间的关联问题）、决策树分类法（对数据和信息进行归纳和分类）、遗传算法（基于生物进化论及分子遗传学理论提出的）、神经网络算法（模拟人的神经元功能）等。 数据挖掘最早使用的方法是关联分析，主要应用于零售业。其中最有名的是售货篮分析，帮助售货商制定销售策略。随着信息时代的到来，数据挖掘在金融[2]、医疗[3]、通信[4]等方面得到了广泛的应用。 2.关联规则基本原理 设项的集合I = { I1 ，I2 ，...，Im }，数据库事务的集合为D，我们用|D|表示事务数据库所有事务的个数，其中用T
表示每个事务，使得T I。我们用TID作为每个事务的唯一标识符。用X表示一个项集，满足X T，那么交易T包含X。根据上述相关描述，给出关联规则的相关定义。 2.1项集支持度 用X表示数据库事务D中的项集，项集X的支持度表示项集X在D中事务数所占的比例，用概率P（X）表示，那么Support（X）=P（X）=COUNT（X）/|D| （1） 2.2关联规则置信度 X Y关联规则的置信度是数据库事务D中包含X Y的事务数与包含X的事务数之比，表示方法如下： confidence（X Y）= support（X Y）/support（X）= P（Y|X）（2） 3.关联规则算法 3.1经典的Apriori挖掘算法 大多数关联规则的算法是将关联规则挖掘任务分为两个子任务完成。一是频繁项集的产生，频繁项集的目的是找到大于等于给定的最小支持度阈值的所有项集，这些项集我们称之为频繁项集。二是规则的产生，即从频繁项集中找到置信度比较高的规则，我们称之为强规则。Apriori挖掘算法是众多挖掘关联规则中比较经典的算法，它采用布尔关联规则，是一种宽度优先算法。 3.2Apriori算法优化
研究生课程论文 关联规则挖掘基本概念和算法 课程名称：数据仓库与数据挖掘 学院：交通运输 专业：交通运输规划与管理 年级：硕1003班 姓名：张令杰 学号：10121084 指导教师：徐维祥
摘要 (Ⅰ) 一、引言 (1) 二、关联规则的基本描述 (1) 三、经典频繁项集挖掘的Apriori算法 (3) 四、提高Apriori算法的效率 (6) 五、由频繁项集产生关联规则 (8) 六、总结 (9) 参考文献 (9)
目前，数据挖掘已经成为一个研究热点。关联规则数据挖掘是数据挖掘的一个主要研究内容，关联规则是数据中存在的一类重要的可被发现的知识。其核心问题是如何提高挖掘算法的效率。本文介绍了经典的关联规则挖掘算法Apriori并分析了其优缺点。针对该算法的局限性，结合Apriori性质，本文对Apriori中连接的步骤进行了改进。通过该方法，可以有效地减少连接步产生的大量无用项集并减少判断项集子集是否是频繁项集的次数。 关键词：Apriori算法；关联规则；频繁项集；候选集
一、 引言 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。如果两项或多项属性之间存在关联，那么其中一项的属性就可以依据其他属性值进行预测。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。 关联规则挖掘的一个典型例子是购物篮分析[1] 。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。 最著名的关联规则发现方法是R. Agrawal 提出的Apriori 算法。关联规则挖掘问题可以分为两个子问题：第一步是找出事务数据库中所有大于等于用户指定的最小支持度的数据项集；第二步是利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度进行取舍，最后得到强关联规则。识别或发现所有频繁项目集市关联规则发现算法的核心。 二、关联规则的基本描述 定义1. 项与项集 数据库中不可分割的最小单位信息，称为项目，用符号i 表示。项的集合称为项集。设集合{}k i i i I ,,,21 =是项集，I 中项目的个数为k ，则集合I 称为k -项集。例如，集合{啤 酒，尿布，牛奶}是一个3-项集。 定义2. 事务 设{}k i i i I ,,,21 =是由数据库中所有项目构成的集合，一次处理所含项目的集合用T 表示，{}n t t t T ,,,21 =。每一个i t 包含的的项集都是I 子集。 例如，如果顾客在商场里同一次购买多种商品，这些购物信息在数据库中有一个唯一的标识，用以表示这些商品是同一顾客同一次购买的。我们称该用户的本次购物活动对应一个数据库事务。 定义3. 项集的频数（支持度计数） 包括项集的事务数称为项集的频数（支持度计数）。 定义4. 关联规则 关联规则是形如Y X ?的蕴含式，其中X ，Y 分别是I 的真子集，并且φ=?Y X 。 X 称为规则的前提，Y 称为规则的结果。关联规则反映X 中的项目出现时，Y 中的项目也 跟着出现的规律
数据挖掘的其他基本功能介绍 一、关联规则挖掘 关联规则挖掘是挖掘数据库中和指标（项）之间有趣的关联规则或相关关系。关联规则挖掘具有很多应用领域，如一些研究者发现，超市交易记录中的关联规则挖掘对超市的经营决策是十分重要的。 1、 基本概念 设},,,{21m i i i I =是项组合的记录，D 为项组合的一个集合。如超市的每一张购物小票为一个项的组合（一个维数很大的记录），而超市一段时间内的购物记录就形成集合D 。我们现在关心这样一个问题，组合中项的出现之间是否存在一定的规则，如A 游泳衣，B 太阳镜，B A ?，但是A B ?得不到足够支持。 在规则挖掘中涉及到两个重要的指标： ①、支持度 支持度n B A n B A )()(?=?，显然，只有支持度较大的规则才是较有价值的规则。 ②、置信度 置信度) ()()(A n B A n B A ?=?，显然只有置信度比较高的规则才是比较可靠的规则。
因此，只有支持度与置信度均较大的规则才是比较有价值的规则。 ③、一般地，关联规则可以提供给我们许多有价值的信息，在关联规则挖掘时，往往需要事先指定最小支持度与最小置信度。关联规则挖掘实际上真正体现了数据中的知识发现。 如果一个规则满足最小支持度，则称这个规则是一个频繁规则； 如果一个规则同时满足最小支持度与最小置信度，则通常称这个规则是一个强规则。 关联规则挖掘的通常方法是：首先挖掘出所有的频繁规则，再从得到的频繁规则中挖掘强规则。 在少量数据中进行规则挖掘我们可以采用采用简单的编程方法，而在大量数据中挖掘关联规则需要使用专门的数据挖掘软件。关联规则挖掘可以使我们得到一些原来我们所不知道的知识。 应用的例子： * 日本超市对交易数据库进行关联规则挖掘，发现规则：尿片→啤酒，重新安排啤酒柜台位置，销量上升75%。 * 英国超市的例子：大额消费者与某种乳酪。 那么，证券市场上、期货市场上、或者上市公司中存在存在哪些关联规则，这些关联规则究竟说明了什么？
关联规则是等人首先提出的的一个重要R.Agrawal KDD 研究内容，近年来受到了数据库界的广泛关注。关联规则是寻找在同一个事件中出现的不同项的相关性，即找出事件中频繁发生的项或属性的所有子集，以及它们之间应用相互关联性。关联规则最早用于发现顾客交易数据库中不同商品间的联系，后来诸多的研究人员对关联规则的挖掘问题进行了大量的拓展和研究。他们的工作包括对原有算法的优化，如引入并行的思想，以提高算法的效率，对关联规则的应用进行扩展。关联规则挖掘具有计算量大，负载集中的特点。而I/O 且许多关联规则的实际应用涉及到海量数据。在这种情况下，即使对算法进行了优化，在单处理机上使用串行算法进行挖掘所需要的时间可能也是无法接受的。其主要原因在于单处理器本身受到内存和带宽的限制。因此，必须依靠I/O 高性能并行计算来有效地完成挖掘任务。关联规则的基本概念 1 关联规则的形式化描述如下： {}12,,...,m i i i 令为项目集，为事物数据库，其中每I = D I T ?个事物是一个项目子集，并另有一个唯一的事物标 T ( )T X ?识符。如果，则事物包含项目集。 TID T X Y X ?I Y I X ??,一个关联规则是形如的蕴涵式这里并 , ,Y X ∩Y X ?且ф。规则在交易数据库中的支持度 = D (是交易数据库中和的交易数与所有交易数之比， support)X Y Y X ?记为，即support( )Y X ?{ }D D T T Y X T /,:∈?∪support( )= Y X ?规则在交易数据库中的可信度指包 D (confidence)含和的交易数与包含的交易数之比，记为 X Y X Y X ?，即 confidence( )confidence(Y X ?{}{}D T T X T D T T Y X T ∈?∈?∪,:/,: )= 给定一个交易集，关联规则的挖掘问题就是产生支持 D 度和可信度分别大于用户给定的最小支持度和最 (minsupp)小可信度的关联规则。 (minconf)关联规则的发掘分为两个步骤：找出所有支持度大(1)于最小支持度的频集；从频集中产生期望的规则。(2)串行关联规则挖掘算法2 目前所有并行关联规则算法都是在相应的串行算法的基础上提出的。本文首先对这些串行算法进行介绍和分析。 算法2.1 Apriori-like 在各种关联规则挖掘算法中，最经典、最广泛使用的就是等Agrawal [2]设计的算法，其核心思想是基于频集理Apriori 论的递推方法。首先产生频繁项集，然后是频繁项集，1-2-直到有某个值使频繁项集为空，算法停止。这里在第次r r-k 循环中，过程先通过对两个只有一个项不同的属于的频 k-1集做连接产生候选项集的集合。然后验证候选项集 (k-2)-k-k-中的每个元素来决定是否将其加入频集，这里的验证过程k-是算法性能的一个瓶颈。这个方法要求多次扫描数据库，这就需要很大的负载。I/O 等提出了一个高效地产生频繁集的基于杂凑Park (hash)的算法：算法。通过实验Dynamic Hashing and Pruning(DHP)可以发现寻找频集的主要计算是在生成频繁项集上。2-DHP 利用一个杂凑表在计算频繁项集时先大概计算出项集的1-2-支持度，从而减少了候选项集的数量。还采用了数据2-DHP 库修剪技术，通过修剪掉那些不包含频集的事物集以减小下一次循环中数据库的大小。然而，这种修剪技术的优化并不显著。其主要原因在于只能通过过滤对数据库执行逻辑上的 并行关联规则挖掘综述 尚学群，沈均毅 西安交通大学电信工程学院软件研究所，西安( 710049 ) 摘要： 关联规则发现作为数据挖掘的重要研究内容，在许多实际领域内得到了广泛的应用。因为在挖掘过程中涉及到大量的数据和计算，高性能计算成为大规模数据挖掘应用的一个重要组成部分。该文介绍了当前并行关联规则挖掘方面的研究进展，对一些典型算法进行了分析和评价，从并行度、负载平衡以及和数据库的集成等方面展望了并行关联规则挖掘的研究方向。关键词： 数据挖掘；关联规则；并行算法 Survey of Parallel Association Rule Mining ，SHANG Xuequn SHEN Junyi (Software Institute,School of Telecom Engineering, Xi'an Jiaotong University, Xi'an 710049) 【】Abstract Due to the huge size of data and amount of computation involved in data mining, high-performance computing is an essential component for any successful large-scale data mining application. This paper provides a survey of the study in parallel association rule generation, reviews and analyses some typical algorithms, views the trend of parallel association rule mining based on the kind of parallelism exploited, the load balancing strategy used, and the integration with databases. The goal of this paper is to serve as a reference for both researchers and practitioners interested in the state-of-the-art in parallel association rule mining.【】Key words ；；Data mining Association rules Parallel algorithms 第30卷 第14期Vol.30 № 14计 算 机 工 程Computer Engineering 2004年7月 July 2004 ?发展趋势/热点技术 ? 中图分类号： TP182 文章编号：1000—3428(2004)14 —0001—03 文献标识码：A