目录
摘要：....................................................................................................... １1．介绍..................................................................................................... １
2.数据挖掘................................................................................................ １
3.关联规则................................................................................................ ２4．数据采掘工具的研制及其应用 ........................................................ ４5.程序实现................................................................................................ ５算法描述................................................................................................ ６数据结构............................................................................................ １０算法实现细节.................................................................................... １３
6.总结.................................................................................................... ２０
7.致谢.................................................................................................... ２０
摘要：
关联规则在数据挖掘是一个重要的研究内容。而产生频繁集则是产生关联规则的第一步。在大多数以前的实现中，人们普遍采用了类似于Apriori[2]的算法。这种算法有一个很大的缺点，就是使用了不断产生候选集并加以测试的方式来得到频繁集。但是，产生候选集的代价是很大的。
本文分析并且实现了在论文[1]中提出的FP-growth算法。FP-growth算法的优点是节省时间和空间，对大规模数据采用分治的办法以避免规模巨大难以接受。FP-growth算法主要通过FP-tree来构造频繁集。
FP-tree是一个数据库里跟产生频繁集有关的信息的压缩表示。在具体的实现中，我通过了一系列的从低到高的数据结构来实现它，并进而实现整个算法。该实现基于Windows 平台，编程工具是Visual C++ 6.0，许多地方还用到了C++的标准模板库。
1．介绍
数据挖掘技术的出现是伴随着当今时代信息的爆炸性增长和人们面对纷繁的数据得到决策支持而出现的.数据挖掘工具中要实现的一个很重要的功能就是关联规则的找寻，而关联规则找寻的第一步就是要找到相应的频繁集.
本文就是建立在对一个频繁集产生算法的分析和实现的基础上的.通过一个程序具体实现了FP-growth算法,并将它作为一个使用数据挖掘工具,ARMiner的一部分.
本文的第2部分将介绍一些数据挖掘的基本知识.
第3部分讨论关联规则的一些问题.
第4部分是本文所实现的程序所属的数据挖掘工具ARMiner的一些介绍.
第5部分结合程序设计着重讨论一下本文是怎样实现FP-growth算法的。
2.数据挖掘
数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。
何为知识?从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。
这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。
数据挖掘的主要过程如下:
1. 确定业务对象
清晰地定义出业务问题,认清数据挖掘的目的是数据挖掘的重要一步.挖掘的最后结构是不可预测的,但要探索的问题应是有预见的,为了数据挖掘而数据挖掘则带有盲目性,是不会成功的.
2. 数据准备
1) 数据的选择
搜索所有与业务对象有关的内部和外部数据信息,并从中选择出适用于数据挖掘应用的数据.
2) 数据的预处理
研究数据的质量,为进一步的分析作准备.并确定将要进行的挖掘操作的类型.
3) 数据的转换
将数据转换成一个分析模型.这个分析模型是针对挖掘算法建立的.建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键.
3. 数据挖掘
对所得到的经过转换的数据进行挖掘.除了完善从选择合适的挖掘算法外,其余一切工作都能自动地完成.
4. 结果分析
解释并评估结果.其使用的分析方法一般应作数据挖掘操作而定,通常会用到可视化技术.
5. 知识的同化
将分析所得到的知识集成到业务信息系统的组织结构中去.
数据挖掘技术目前已经有不少成功的范例.其实在日常生活中我们也可以看到许多数据挖掘的应用.例如,如果你在沪上一家比较著名的电子商务网站购买了一张周星驰的经典搞笑片”大话西游”,该网站会提醒你,
【购买该商品的用户还买了这些商品】
行运一条龙
97家有喜事
武状元苏乞儿
月光宝盒
秀兰邓波儿（12套装）
这些就是用数据挖掘技术从购买这部片子的人群中统计出来的.当然这只是一种比较简单的应用.更复杂的应用见下面这个例子:
美国Firstar银行使用Marksman数据挖掘工具，根据客户的消费模式预测何时为客户提供何种产品。Firstar银行市场调查和数据库营销部经理发现：公共数据库中存储着关于每位消费者的大量信息，关键是要透彻分析消费者投入到新产品中的原因，在数据库中找到一种模式，从而能够为每种新产品找到最合适的消费者。Marksman能读取800到1000个变量并且给它们赋值，根据消费者是否有家庭财产贷款、赊帐卡、存款证或其它储蓄、投资产品，将它们分成若干组，然后使用数据挖掘工具预测何时向每位消费者提供哪种产品。预测准客户的需要是美国商业银行的竞争优势。
3.关联规则
关联规则是关联分析中的一种常用技术（另一种是序列模式）。关联规则是寻找在同一
个事件中出现的不同项的相关性。其形式化的陈述如下。（参照[2]）
设L={i1,i2,...im}是所有项的集合。D是交易集合，其中每个交易T是一个项的集合并且T?L。每一个交易T都有一个唯一的标识，TID。如果项集合X?L且X?T,我们就说交易T包含X.一个关联规则(association rule)就是这样一种形式的关系:X==>Y,其中X?L,Y?L,并且X?Y=?.
另外两个和关联规则有关的概念是支持度(support)和可信度(confidence)
根据[2]的定义,对于一个关联规则X==>Y,.在交易集合D中, Txy={T|(X?Y)?T?T∈D},Tx={T|X?T?T∈D},支持度为s,如果|Txy|/|D|=s%;可信度为c,如果|Txy|/|Tx|=c%.
举例来说,有一个特定的关联规则,锤子==>钉子,这个规则可能意味着买锤子的人也有倾向买钉子.在一个有10000条交易记录的交易数据库中,若有300条记录既包含了锤子又包含了钉子,则我们说此关联规则的支持度为300/10000=3%.这个支持度还是比较的高,但我们并不能就此作出这个关联有意义的结论.假如通过统计发现一共有6000条记录包含了”锤子”,则仅有可信度300/6000=5%的购买了”锤子”的人又去购买了钉子，那么这个关联规则的可信度不高,它并没有告诉我们什么.但是假如只有600人购买了锤子,则我们可以知道其中有一半的人又去购买了钉子,这个现象就值得注意了.
另一个更详细的例子来自于[4].
总交易笔数:1000
包含”锤子”:50
包含”钉子”:80
包含”钳子”:20
包含”锤子”和”钉子”:15
包含”钳子”和”钉子”:10
包含”锤子”和”钳子”:10
包含”锤子”,”钳子”和”钉子”:15
则可以计算出:
“锤子和钉子”的支持度=1.5%(15/1000)
“锤子,钉子和钳子”的支持度=0.5(5/1000)
“锤子==>钉子”的可信度=30%(15/50)
“钉子==>锤子”的可信度=19%(15/80)
“锤子和钉子==>钳子”的可信度=33%(5/15)
“钳子==>锤子和钉子”的可信度=25%(5/20)
注意到数据挖掘得到的关联规则,它只是对数据库中数据之间相关性的一种描述。还没有其他数据来验证得到的规则的正确性.
除了支持度和可信度还有其他的关联规则评价标准如改善度(lift)和兴趣度(interest).
本文的实现当中,对支持度的定义和上述不同,参见第5部分.
4．数据采掘工具的研制及其应用
“数据采掘工具的研制及其应用”（863-306-02-05）是国家863项目，是前一阶段863项目研究的继续，由复旦大学计算机系数据库组承担。目前已经设计并实现系统原型数据采掘工具ARMiner（图1）。
图1
该工具的主要功能块的说明如下：(上图及说明主要参考[3])
数据预处理负责对待采掘的数据源作必要的准备，
其各模块功能如下：
（1）数据获取
指定要使用的数据集的名称及位置。
（2）数据取样
对获取的数据从中取样，取样的方式有很多种，根据数据采掘的目的性灵活选用。例如，随机取样，数据集中每一组观测值都有相同的被取样概率；等距取样，对数据编号，取样的观测值之间的距离相等；分层取样，将样本总体分成若干层次，每个层次中的观测值都具有相同的被选用概率，但不同层次之间设定的概率可不同，使模型具有更好的拟和度；起始顺序取样，从输入数据的起始处开始取样，对取样数量预先规定；分类取样，按观测值的某种属性分类，取样以类为单位。
（3）数据筛选
通过数据筛选筛选掉不希望包括进来的观测值。例如，对于分类变量可给定某一类的类值说明此类观测值是要排除于取样范围之外的，对于区间变量可指定其值大于或小于某值的那些观测值排除于取样范围之外。
（4）数据转换
将某一个数据进行某种转换操作，然后将转换后的值作为新的变量存放在样本数据中，而转换的目的是为了把数据和将来要建立的模型拟和得更好。
数据采掘即对经过预处理的数据进行采掘，可分为两个模块：
（1）数据采掘数据库
在进行数据采掘分析模型的操作之前，要建立一个数据采掘的数据库(DMDB)，放置此次要进行操作的数据，可预先进行一些诸如变量最大、最小、平均、标准差等处理，为数据
采掘建立一个良好的工作环境。
（2）数据采掘过程
利用某一种数据采掘算法进行数据采掘。
数据评价即用一种通用的数据采掘评价的架构来比较不同模型的效果；预报各种不同类型分析工具的结果。在进行各种比较和预报的评价之后，给出一系列标准的图表，供用户进行定量评价。
本文所基于的程序实现即是属于上面数据采掘部分,数据采掘过程中的关联规则部分.
5.程序实现
程序所要实现的FP-growth算法是一个频繁集产生算法,与一般的类似于Apriori的频繁集产生算法相比,FP-growth的优点在于它不需要产生大量的候选集,因而在时间和空间上都有很好的效率.关于FP-growth请参看本部分中的算法描述部分。
程序的实现是基于Windows95/NT平台,编译器是Visual C++6.0.这是为了与程序所属的数据挖掘工具ARMiner相兼容.
程序在定义数据结构和实现算法的时候主要有以下一些考量。
首先,程序必须注意速度.速度问题在频繁集产生的算法中应该是比较重要的.因为它们常常涉及大量数据的处理.因此在程序中许多需要排序的数据结构都使用了平衡树,这是一种高效的对全序元素的组织方式.
其次,是对空间占用的考量。同样因为要处理大量的数据,所以对内存的管理要尤其严格,如果出现内存泄漏将是很麻烦的事情.
第三，是编程风格的考虑.要尽量采用通用化的代码.因为对于一个比较大的系统来说，任何一个小的部分都应该清楚明白,便于别人阅读和修改.
基于上面三点的考量，我在对程序的数据结构的定义和算法的实现的时候大量采用了C++的标准模板库(STL,Standard Template Library).这是基于以下的事实,关联规则的挖掘所涉及到的数据结构和基本算法都是以往的常用数据结构和算法,如向量类,集合类,快速排序算法等.而STL正是包含了这样许多通用的数据结构和基本算法的库.
模板实际上是一种宏,但比宏安全可靠的多.它在编译期间就被处理了,因此根本不会影响程序的执行速度.又因为，STL中的种种数据结构和算法都是精心编写的,对同一问题的实现一般是比较经典的.不仅在速度上有优势,而且还避免了许多低层次上的内存泄漏问题.使我们把注意力集中到各个函数接口上面.
由于STL本身就是一中很通用的库,因此可以很好的满足第三个条件.用他编写的代码,对类似的数据结构和算法的处理都很相象.
例如,在STL中有一大类模板叫容器模板(container),简单的说就是包含了许多元素的类的模板,象vector,array,set等就属于容器模板.对于这些模板中的元素的访问都可以通过它们的遍历子,用完全一致的方式进行.请看下面两段程序清单:
void print(FreqSet* pSet){
FreqSet_Iter fit;
for(fit=pSet->begin();fit!=pSet->end();fit++){
printf("%s %d \n",(*fit)https://www.doczj.com/doc/b26891795.html,,(*fit).second.count);
}
}
void print(Table* pTable){
Table_Iter tit;
for(tit=pTable->begin();tit!=pTable->end();tit++){
printf("%s %d \n",(*tit).name,(*tit).count);
}
}
这两个函数是在调试的时候分别打印出频繁集pSet和头表pTable中的元素的.
尽管pSet的类FreqSet是由map模板生成的,pTable的类Table是由multiset生成的,但对它们的元素的访问形式几乎一模一样都是利用相应的遍历子.涉及的函数名也很相似.其实,所有的容器模板都定义了函数begin()和end()代表元素列表的起始和结束.另外还有大量的具有相同名字和类似功能的函数,方便了我们对数据结构的管理。
在选择数据库访问方式的时候,用了最近比较流行的ADO方式,它比ODBC更加灵活,速度也有改善.对网络数据库的支持也很好.
下面首先对要实现的算法做一个描述,然后针对数据结构和算法两方面对程序的实现进行详细说明.
算法描述
本文所实现的频繁集产生算法建立在两个基本的函数之上.
在具体描述这两个算法之前,还要介绍一些建立它们所需要的知识.
FP-tree
论文[1]对FP-tree的定义如下:
1,它有一个标记为”null”的根节点,它的子节点为一个项前缀子树(item prefix subtree)的集合,还有一个频繁项(frequent item)组成的头表(header table).
2,每个项前缀子树的节点有三个域:item-name,count,node_link.item-name记录了该节点所代表的项的名字.count记录了所在路径代表的交易(transaction)中达到此节点的交易个数.node_link指向下一个具有同样的item-name域的节点,要是没有这样一个节点,就为null.
3,频繁项头表(frequent item header table)的每个表项(entry)由两个域组成:(1)item-name.(2)node_link.node_link指向FP-tree中具有与该表项相同item-name域的第一个节点.
第一个算法的就是根据一个数据库建立这样一棵FP-tree.
下面是一个比较形式化的描述.
Algorithm1
输入:一个交易数据库DB和一个最小支持度threshold.
输出:它的FP-tree.
步骤:
1,扫描数据库DB一遍.得到频繁项的集合F和每个频繁项的支持度.把F按支持度递降排序,结果记为L.
2,创建FP-tree的根节点,记为T,并且标记为?null?.然后对DB中的每个交易Trans做如下的步骤.
根据L中的顺序,选出并排序Trans中的频繁项.把Trans中排好序的频繁项列表记为[p|P],其中p是第一个元素,P是列表的剩余部分.调用insert_tree([p|P],T).
函数insert_tree([p|P],T)的运行如下.
如果T有一个子结点N,其中N.item-name=p.item-name,则将N的count域值增加1;否则,创建一个新节点N,使它的count为1,使它的父节点为T,并且使它的node_link和那些具有相
同item_name域串起来.如果P非空,则递归调用insert_tree(P,N).
完毕.
通过一个例子,可以更清楚的看到一棵FP-tree是怎样建立的.
表1.
我们首先扫描一遍这个数据库,计算每个项的计数值并保存在频繁项的集合F 中,F={(a:3),(b:3),(c:4),(d:1),(e:1),(f:4),(g:1),(h:1),(i:1),(j:1),(k:1),(l:2),(m:3),(n:1),(o:2),(p:3)}.集合中每个元素的第二个分量代表第一个分量所代表项的支持度.我们假定最小支持度为3.选出F中支持度大于3的项,并按支持度递降排列,将结果放入列表L中,此时,L={(f:4),(c:4),(a:3),(b:3),(m:3),(p:3)}.
执行算法的第二步,创建一个标记为”null”的根节点.开始对数据库的第二遍扫描.对第一个交易的扫描将建立这棵树的第一个分支:<(f:1),(c:1),(a:1),(m:1),(p:1)>.注意,在这个交易中的频繁项已经被按照L中的顺序进行排序了.对于第二个交易来说,它已经排序好的频繁项列表
为了方便对树的遍历.一个频繁项头表(frequent item header table)被建立了，头表表项的node_link指向树里面具有相同item_name的节点.具有相同item_name的节点通过node_link 被连结在一起.
图2
FP-tree是一个压缩的数据结构,它用较少的空间存储了后面频繁集挖掘所需要的全部信息.
算法二建立在算法一所产生的F-tree上面.它会递归调用自己,并且反复调用算法一产生新的FP-tree.
输入:一棵用算法一建立的树Tree
输出:所有的频繁集
步骤:
调用FP-growth(Tree,null).
下面是对过程FP-growth的伪码描述.
Procedure FP-growth(Tree,α)
{
if Tree只有一条路径P
then 对P中的节点的每一个组合(记为β)做(1)
(1)产生频繁集β?α,并且把它的支持度指定为β中节点的最小支持度.
else 对Tree的头表从表尾到表头的每一个表项(记为a)做(2)-(5)
(2)产生频繁集β=a?α,并且支持度为a的支持度
(3)建立β的条件模式库(conditional pattern base)和β的条件树(conditional FP-tree)Tree2
(4)i f Tree2!=?
(5)t hen调用FP-growth(Tree2,β)
}
关于什么是条件模式库(conditional pattern base)和条件树(conditional FP-tree),我们继续上面那个例子来介绍.
我们把图2中已经得到的FP-tree和相应的头表作为算法二的输入.按照从表尾到表头的顺序考察表中的每一个表项.
从表项p出发,先可以得到一个频繁集(p:3).然后,我们可以得到包含p的所有模式.顺着p 表项的node_link域,我们找到所有包含p的路径
接着考察m,先还是得到(m:3).顺着它的node_link得到2条路径
类似的,表项b产生一个频繁集(b:3)和3条路径
模式库上面运用算法一,得到一棵空树,对含有b 的频繁集的挖掘到此为止.
表2
(f:2,c:2,a:2)
(f:1.c:1,a:1.b:1)
…m?的条件模式库
头表
算法一产生的FP-tree
图2
数据结构
对应于算法描述中所出现的各个对象分别定义了一些数据结构.下面予以分别介绍.(有关代码的清单只列出重要部分，如类中的普通的构造函数之类就不予详细描述了.) 1．Item
class Item{
public:
CString name;
int count;
LPVOID lpvoid;
Item();
Item(const Item& item);
Item(CString strName,int icount);
~Item();
Item& operator=(const Item& right);
bool operator==(const Item& right);
bool operator<(const Item& right);
};
Item类对应于算法中的项.为了操作方便其中的成员变量和成员函数都定义为public类型.
成员变量name用来存放项的名字.
count则是每个项的记数值,在最后的输出之中,它的意义就变成了支持度.
还有一个变量lpvoid,是没有在算法描述中出现过的,用来在使用过程中指向一个新分配的Table_Iter对象.因为Table_Iter类还没有声明,所以只好用LPVOID类型的指针.对它的释放在析构函数~Item()中.~Item()又调用DeleteV oid(LPVOID),这个函数在class Item声明之前声明,但又在class Table_Iter定义之后定义,因此可以用它来删除这个对象.
三个构造函数Item(),Item(const Item& item)和Item(CString strName,int icount)在实例化对象的时候起到不同的作用.其中第二个是一个赋值构造函数,因为在后面定义的一些类中需要使用class Item做为类型参数,根据约定,需要class Item实现一个赋值构造函数.最后三个成员函数重载了两个运算符?==?和?
2.Trans
class Trans:public std::vector
{
public:
int TID;
Trans(){TID=0;};
Trans(int t){
TID=t;
}
bool operator==(const Trans& right);
bool operator<(const Trans& right);
}
typedef Trans::iterator Trans_Iter;
Trans类对应于交易对象(Transaction).对它的定义利用了STL中的vector模板,把它定义为一个以Item为元素的向量.把它定义为向量,是因为后来需要对其中的元素进行排序,向量可以使用快速排序.
这个Trans 类身肩两任,它不仅代表交易对象,还在最后的结果输出中还被用来存放频繁集.
Trans_Iter是Trans类的遍历子.在以后使用STL容器模板定义的类都会有一个与之相对应的遍历子,不再赘述.
3.DB
typedef std::list
typedef DB::iterator DB_Iter;
DB对应于数据库对象,它是一个存在于内存中的”数据库”.它的定义借助于STL的list模板就非常的简明.之所以使用list模板而不是vector是因为对一个数据库的操作我们通常只需要对其进行遍历,不需要查找,排序等操作,因此list最合适,效率因此也最高。
4.FreqSet
typedef std::map
typedef FreqSet::iterator FreqSet_Iter;
FreqSet跟我们要得到的频繁集并不是一回事,它只是一个中间的数据结构.我们在扫描数据库的时候需要计算每个项的记数值,因此需要建立一个项的集合类,其中有所有的项,每次在数据库中扫描到一个项就增加其中相应的项的记数值.它相当于算法描述中的频繁项集合.
为了使得查找相应项的速度加快,用map模板来定义FreqSet.
STL在实现map的时候,实际上在其内部维持了一个平衡树, 因此其插入，查找,删除的速度是O(ln).map模板使用第一个类型参数作为比较的键值类型,第二个类型参数做为节点内部值.在这里,键值类型为CString,节点内部值类型为Item.我们就利用Item的成员变量name 为键值.就可以根据Item的名字来寻找它在FreqSet中的位置,在O(ln)时间内完成对相应项的操作.
使用map模板的另外一个原因参见后面的算法实现细节部分对函数(f5)的说明.
5.NodeVector和Node
class Node;
typedef std::vector
typedef NodeVector::iterator NVector_Iter;
class Node{
public:
CString name;
int count;
Node* node_link;
NodeVector* pChildren;
Node* pParent;
Node(){
pChildren=(NodeV ector*) new NodeVector;
node_link=NULL;
pParent=NULL;
count=0;
name="";
}
~Node(){
if(pChildren)delete pChildren;//在析构函数中删除
}
};
class Node 是建立FP-tree的关键数据结构,节点。其中pChildren指针指向子节点,由于一个节点的子节点的数目是不定的，所以用了一个NodeVector类来管理子节点.因为我们要在Node类的构造函数中给pChildren分配空间,所以需要在定义Node之前定义NodeVector.
NodeVector是一个以Node*为元素的向量类.所以我们在定义它之前声明了Node类.虽然我们在后面的算法中需要根据名字在pChildren中查找子节点,我们并没有使用hash表或者平衡树这样复杂但高效的数据结构,是因为子节点的数目一般都不是很多,使用复杂的这样复杂的数据结构对于少量的数据来说时间并没有缩短多少,空间却要浪费一些.因此使用了一个向量类,查找的时候使用简单的遍历算法.
成员变量name和count的意义很清楚,它们分别是节点的名字和计数值.
pParent指向父节点,定义这样一个变量的作用在函数DB* Generate2(Node* node,int& retcount)中可以看到.
node_link也是一个Node*类型的变量,它用来指向下一个同名的节点,其作用在函数Node* SetupFP(FreqSet* pSet,Table* pTable,DB* pDB)中可以看到.
6.Entry
class Entry{
public:
CString name;
int count;
Node* head_link;
Entry();
Entry(const Entry& entry);
Entry(const Item& item);
};
Entry类对应于头表中的表项.因此它有一个name成员,所指项的名字,还有一个Node*类,head_link,用来串起同名的项.
成员变量count是为了优化算法而添加的,它的作用可以在下面Table的说明看到.
7.Table
class Compare2{
public:
Compare2(){};
bool operator()(const Entry& l,const Entry& r){
if(l.count==r.count)return https://www.doczj.com/doc/b26891795.html, return l.count>r.count; } }; typedef std::multiset typedef Table::iterator Table_Iter; 最后一个重要的数据结构是Table类，它对应于算法描述中的头表. Table是由multiset模板定义的.multiset也是一个集合模板,其中的实现也是借助于一棵内部维护的平衡树.它和map模板的区别在于不需要另外指定键值类型，它直接使用内部节点值类型作为键值类型.在这里,我们使用Entry作为它的内部值类型. 因此,需要对Entry类的比较作出规定,我们使用Compare2类作为比较算子.它通过重载运算符()(const Entry& l,const Entry& r)来实现比较.比较的原则可以在这个函数的定义中看到.count较大的比较大,count一样的其name按字典序较前面的较大. 算法实现细节 本程序的输入和最终输出都需要访问数据库,因此首先对程序涉及到数据库访问的部分做一下说明. 因为使用了ADO(ActiveX Data Object)方式访问数据库,在程序的源代码中有这样两行语句: #import "c:\program files\common files\system\ado\msado15.dll" no_namespace rename("EOF","adoEOF") #import "c:\program files\common files\system\ole db\oledb32.dll" rename_namespace("oledb") 它们负责包含进库文件”msado.dll”和”oledb32.dll”,这两个文件包含的类和函数使的ADO 的访问方式成为可能. 跟数据库打交道的只有三个函数: (f1)_ConnectionPtr GetConnection(); (f2)DB* GetDB(_ConnectionPtr& pConn); (f3)void StorePatterns(DB* pDB,_ConnectionPtr pConn); 函数(f1)的作用是弹出一个数据源选择对话框,当使用者选定数据源之后,我们就得到一个连接字符串(connection string).把这个字符串传给ADO中的连接对象(_ConnectionPtr)的Open函数,就得到了一个连接对象.最后把这个连接对象返回.注意,在被打开的数据库中必须有一个名为TRANSDB的表,并且表结构为(TID long not null,IID text(50) not null,COUNT long not null).3个属性分别代表交易编号,项编号,项计数值. 函数(f2)利用(f1)得到的连接对象扫描数据库,将其中的交易放如一个动态分配的DB对象中,然后返回它.为了方便，我们假定数据库中的交易都按照交易编号进行了排序.下面的程序清单是这个函数的主要部分.(pRs是数据库对象) DB* pDB=(DB*) new DB; int tid=pRs->Fields->GetItem("TID")->Value.lVal; pDB->push_front(Trans(tid)); while(!pRs->adoEOF){ int ttid=pRs->Fields->GetItem("TID")->Value.lVal; if(ttid!=tid){ tid=ttid; pDB->push_front(Trans(tid)); } CString name=fieldsvalue(pRs,IID).bstrVal; int count=fieldsvalue(pRs,COUNT).lVal; (*pDB->begin()).push_back(Item(name,count)); pRs->MoveNext(); } return pDB; 函数(f3)被程序最后调用,它将pDB中已经得到的频繁集存入连接对象pConn代表的数据库中.它将要求使用者输入一个表名,用来创建存放频繁集的新表。这个新表有3个属性(PID long not null,IID text(50) not null,SUP integer not null),分别代表模式编号,项编号,和该模式的支持度. (f4) void Algorithm1(DB* db,Node*& tree,Table*& pTable){ DB_Iter dbit; FreqSet* pSet=(FreqSet*)new FreqSet; pTable=(Table*) new Table; for(dbit=db->begin();dbit!=db->end();dbit++){ Scan1(pSet,&(*dbit)); } SetupTable(pSet,pTable); SortTrans(db,pSet); Node* root=SetupFP(pSet,pTable,db); tree=root; delete pSet; } 函数(f4)基本上对应于算法描述中的算法一,它通过db中传来的数据库,得到一棵FP-tree,其根结点为tree和相应的头表.它依次调用下面的几个函数.(f5)-(f8) (f5) void Scan1(FreqSet* pSet,Trans* pTrans){ Trans_Iter transit; for(transit=pTrans->begin();transit!=pTrans->end();transit++){ std :: pair < FreqSet :: iterator , bool > rpair = pSet -> insert ( FreqSet :: value_type ( ( *transit ) . name , * transit ) ) ; if(rpair.second==false){ (*rpair.first).second.count+=(*transit).count; } } } 这个函数的作用很简单,它只是从pTrans所代表的交易中取出每个项,然后试图将其插入到pSet中去(pSet->insert(...)),如果插入失败(if(rpair.second==false)),则表明pSet中已经有此项了,因此只须增加其计数值((*rpair.first).second.count+=(*transit).count;)就可以了. 从这里我们可以看出在数据结构里把使用map而不使用set或multiset模板定义FreqSet 的另外一个原因。这3个模板在实现数据结构的时候都在内部维护了一个平衡树,使得元素在插入以后就已经按键值排好了序.但是set和multiset都使用插入元素本身作为键值,因此在 插入以后就不允许修改这些元素,除非删除它们.因为任何一个对元素的修改都是对键值的修改,会使得平衡树不在保持原有的有序性。而map模板将元素和键值分离开来,你可以使用另外一个不变的量来充当键值,从而可以放心的对元素进行各种修改,在这里我们主要修改每个元素的计数值. (f6) void SetupTable(FreqSet* pSet,Table* pTable){ FreqSet_Iter fit,fit2; Table_Iter tit; for(fit=pSet->begin();fit!=pSet->end();){ if((*fit).second.count fit2=fit++; pSet->erase(fit2); continue; } tit=pTable->insert((*fit).second); fit->second.lpvoid=new Table_Iter; *(Table_Iter*)fit->second.lpvoid=tit; fit++; } } 这个函数的作用是根据频繁项集合pSet建立头表pTable. 首先是删除那些支持度小于threshold的项.把剩下的插入到头表中去.注意到头表的类Table是建立在multiset的基础上的，所以每个元素在被插入以后就已经被排好了序. 这是我们可以看到Item类的lpvoid域被分配了内存对象.程序利用它所指向的内存对象来记录相应项在头表中的位置.这样当我们知道项的名字的时候可以通过名字查找它在频繁项集合(用数据结构FreqSet表示)中的位置(注意一下FreqSet的说明,我们可以在时间O(ln)中完成查找),再通过频繁项集合中每个项的lpvoid找到它在头表中的位置,在通过头表表项中的node_link指针完成对树中相应路径的遍历. (f7) void SortTrans(DB* pDB,FreqSet* pSet){ DB_Iter dbit; Trans_Iter tit; for(dbit=pDB->begin();dbit!=pDB->end();dbit++){ if(dbit->size()==1){ if(pSet->find(dbit->begin()->name)==pSet->end()) dbit->begin()->count=0; }else std::sort(dbit->begin(),dbit->end(),Compare(pSet)); tit=dbit->begin(); while(tit!=dbit->end()&&tit->count) tit++; if(tit!=dbit->end())dbit->erase(tit,dbit->end()); } } 这个函数是根据pSet中的项对pDB中的每个交易进行排序.在算法描述中我们只是说根据头表对交易进行排序.但是直接利用头表对每一个交易中的项进行排序,需要进行大量的比较，因此不太合适.其实原先的算法只要求头表中的项按照支持度递降排序就可以了,并不在乎相同支持度的项的相对位置.因此每个交易为了与头表保持一致,都必须在排序中时刻查询头表,以决定每个项的相对位置.在这里,我们定义头表中的项不仅要按照支持度递降排序,而且支持度相同的项按照字典序排列.(参见数据结构部分对Table类的说明)这时,对交易的排序就不需要比较头表中的每个项了,它只需要知道每个项的支持度就可以排出与头表中项相同的相对顺序.这个支持度可以通过项的名字(https://www.doczj.com/doc/b26891795.html,)在频繁项集合(pSet)中查找. std::sort(dbit->begin(),dbit->end(),Compare(pSet)); 上面这条语句就是对交易(由dbit代表)排序.排序的方式和附加的操作在比较算子Comapare类里面.这里的sort(...) 函数是STL中的一个快速排序算法. 比较算子的主要部分如下: bool operator()(Item& l,Item& r){ int lcount,rcount; FreqSet_Iter fit; if((fit=set->find(https://www.doczj.com/doc/b26891795.html,))==set->end())l.count=lcount=0; else lcount=fit->second.count; if((fit=set->find(https://www.doczj.com/doc/b26891795.html,))==set->end())r.count=rcount=0; else rcount=fit->second.count; if(lcount==rcount)return https://www.doczj.com/doc/b26891795.html, return lcount>rcount; } 对于那些在pSet中没有找到的项,把它们的支持度都置为0,排序以后这些支持度为0的项(也就是支持度小于最小支持度的项)都被排在最后面,最后通过语句 while(tit!=dbit->end()&&tit->count) tit++; if(tit!=dbit->end())dbit->erase(tit,dbit->end()); 把它们全部删除掉. (f8) Node* SetupFP(FreqSet* pSet,Table* pTable,DB* pDB); 这是Algorithm1(...)中最关键的一个函数.它通过上面几步建立频繁项集合pSet,头表pTable,每个交易都已经排序好的数据库pDB得到一棵FP-tree. 该函数的主要清单如下: for(dit=pDB->begin();dit!=pDB->end();dit++){//对数据库中每个交易 node=root; for(tit=dit->begin();tit!=dit->end();tit++){对某个交易中的每个项 Node* temp; temp=find_node(node->pChildren->begin(),node->pChildren->end(),tit->name); if(temp==NULL){ //如果子节点中没有要找的项则创建一个 Node* temp2=(Node*)new Node; temp2->name=tit->name; temp2->count=tit->count; node->pChildren->push_back(temp2); temp2->pParent=node; node=temp2; }else{ temp->count+=tit->count;//否则,增加该项的支持度 node=temp; continue; } fit=pSet->find(node->name); tait=*((Table_Iter*)fit->second.lpvoid);//通过频繁项集合pSet中项的lpvoid域//找到相应头表表项 node->node_link=tait->head_link;//更新头表表项中的node_link tait->head_link=node; } } 关于该函数的情况,请看程序清单中的注释。 在算法的描述中只规定了根节点的标记为”null”,并没有要求它和其它的节点一样具有count和node_link域.为了不用给根节点另外建立一个类,就简单使用了一般节点的类Node.把其中的count设为0,node_link设为null. Node* find_node(NVector_Iter f,NVector_Iter l,CString name)在子节点的集合中查找是否含有name的子节点,并返回之,若无,则返回null.该函数只是简单的遍历所有要查找的节点,其原因已经在数据结构部分的”NodeVector和Node”中说明了. (f9) void Algorithm2(Node* tree,Table* pTable,DB *pDB,Trans set){ if(tree==NULL)return; Node* tree2=tree; if(HasNoBranch(tree)){//如果tree没有分支 Trans set2; while(true){//把tree的唯一路径上面的所有节点都放入set2中 if(tree->name!="") set2.push_back(Item(tree->name,tree->count)); if(tree->pChildren->empty())break; tree=*tree->pChildren->begin(); } Generate1(set2,pDB,set);//产生频繁集 }else{ Table_Iter tit; for(tit=pTable->end();tit!=pTable->begin();){//从尾到头遍历每一个头表表项DB* db; tit--; int count; db=Generate2(tit->head_link,count);//tit-> Table* table; Node* node; if(!db->empty()) Algorithm1(db,node,table); delete db; Trans set2(set); set2.push_back(Item(tit->name,count)); Algorithm2(node,table,pDB,set2); } } delete tree2; delete pTable; } 函数(f9)基本对应于算法描述中的算法二.它接受一棵由(f4) 产生的FP-tree,node,相应头表pTable,一个存放找到的频繁集的数据库结构pDB,和存放中间模式的pSet. Trans类和DB类本来是用来存放交易和交易数据库的,这里又用它来存放频繁集和频繁集数据库.频繁集和交易的数据结构在算法描述的时候是不太一样的. 交易和频繁集都需要记录项.但是交易需要对每个项都记录相应的支持度,一个频繁集却只需要一个支持度.为了方便对它们采用了相同的数据结构.但是频繁集中每个项的支持度都是相同的. 在该函数中使用了函数(f10)-(f). (f10) bool HasNoBranch(Node* tree){ NV ector_Iter nit; while(tree){ if(tree->pChildren->empty())return true;//若tree节点没有子节点,返回true nit=tree->pChildren->begin();//nit为tree的第一个子节点 nit++;//得到第二个子节点 if(nit--!=tree->pChildren->end())//若第二个子节点存在 return false;//返回false tree=(*nit);//节点向下移动 } return true; } 这个函数判断以tree为根节点的树是否只有一条路径. 具体的执行方式参见源代码中的注释. (f11) void Generate1(Trans& set2,DB* pDB,Trans& set) { int size=set2.size(); unsigned int maxsize=pow(2,size); bitint bit; int count; if(set2.empty()){//如果set2为空 if(set.empty())return;//如果set也为空,返回 count=set.begin()->count;//否则这里产生的频繁集的支持度为set的支持度 }else{如果set2不为空 Trans_Iter tit=set2.end(); tit--; count=tit->count;//频繁集的支持度是set2中最小的,即最后一个 } for(;bit { Trans trans; int i=0; Trans_Iter tit; for(i=0,tit=set2.begin();tit!=set2.end();tit++,i++){ if(bit[i]) trans.push_back(Item(tit->name,count)); } for(tit=set.begin();tit!=set.end();tit++) trans.push_back(Item(tit->name,count)); if(!trans.empty()) pDB->push_back(trans); } } } 该函数的作用是将每一个set2中项的组合与set合并,其结果即为一个频繁集,然后将产生的频繁集放入pDB中. bitint是我自己定义的一个类.它跟产生一个集合的所有组合有关. bitint实际上是一个无符号长整数,但我们可以根据其中的成员函数得到这个无符号长整数的每一个比特位为0还是为1.这样当我们把这个长整数从0每次加1,递增到pow(2,n)-1,选出那些比特位为1所代表的元素就得到了有n个元素的集合的所有组合. (f12) DB* Generate2(Node* node,int& retcount){ DB* pDB=(DB*)new DB; retcount=0; while(node){ Trans trans; Node* node2=node->pParent; int count=node->count; while(node2->name!=""){ trans.push_back(Item(node2->name,count)); node2=node2->pParent; } retcount+=count; pDB->push_back(trans); node=node->node_link; } return pDB; 关联规则数据挖掘 学习报告 目录 引言 2 案例 2 关联规则 3 （一）关联规则定义 （二）相关概念 （三）关联规则分类 数据 6 （一）小型数据 （二）大型数据 应用软件7 （一）WEKA （二）IBM SPSS Modeler 数据挖掘12 总结27 一、引言 数据库与互联网技术在日益发展壮大，人们每天可以获得的信息量呈指数级增长。如何从这浩如瀚海的数据中找出我们需要的数据显得尤为重要。数据挖掘又为资料探勘、数据采矿。它是数据库知识发现中的一个步骤。数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。数据挖掘通常与计算机科学有关，并通过统计、在线分析处理、情报检索、机器学习、专家系统（依靠过去的经验法则）和模式识别等诸多方法来实现上述目标。 数据挖掘大致分为以下几类：分类（Classification）、估计（Estimation）、预测（Prediction）、相关性分组或关联规则（Affinity grouping or association rules）、聚类（Clustering）、复杂数据类型挖掘(Text, Web ,图形图像，视频，音频等)。 二、案例 "尿布与啤酒"的故事。 在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是："跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在"尿布与啤酒"背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。 按常规思维，尿布与啤酒风马牛不相及，若不是借助数据挖掘技术对大量交易数据进行挖掘分析，沃尔玛是不可能发现数据内在这一有价值的规律的。 数据收集及处理 数据描述： 本文的所采用的数据集来源于网络数据中心数据堂所提供的，来自主要电商平台：京东，淘宝，天猫，亚马逊，一号店的2013年10月20日至2013年10月22日的爽肤水交易信息。数据集主要分为3个部分，第一部分为各平台上爽肤水的交易记录，单日的交易数据包含了19203条交易记录，14个变量，变了包括商品ID，电商名称，日期，商品名称，商品URL，促销价，商品销量销售额，店铺名称，店铺等级，品牌功效，适合皮肤，容量，如图所示为在EXCEL中打开的京东在2013年10月20日的交易数据。第二部分为买家购买后的评价，单日包含925条的评论信息，6个变量，变量包含商品ID，购买时间，评论时间，昵称，评分，评论内容，如图所示就是2013年10月20日京东的评论信息。第三部分为品牌数据集，一共51990条数据，7个变量，包括类目，品牌，电商平台，平均价格，日总销量，对应商品ID。如图所示就是2013年10月20日所有电商平台的评判信息。 本论文所采用的数据全部来自于知名网络数据中心数据堂，具有相当的可信度。经过对数据的观察，为了使得研究过程能够更加方便，我们选择数据较为完整并且有序的自于京东平台的交易信息。由于本文目的是建立如何选择商品的模型，因此不会对结果造成影响。 数据初步处理： 本轮问所有的数据都采用SAS中SQL语言与EXCEL相结合进行 处理。 先对对京东平台上爽肤水的交易记录进行处理。首先应该去掉与本文研究不相关的信息。由于电商名称，日期，店铺名称与本文研究目标不匹配，同时在京东平台上并没有店铺信息，商品名称内容包含于品牌名称等其他变量中。因此我们只选择其中的变量：商品ID，促销价，商品销量销售额，品牌功效，适合皮肤，容量。 将源数据导入SAS之后采用EM模块的InputData节点对销量变量进行描述性统计如图所示： 我们可以发现,其中大多数商品的销售额都为0，是因为这里仅仅采用3天的交易数据，所以大多都没有销量。因为没有销量的商品对本文的并无研究意义，因此我们只研究销售量大于0的商品。 采用SQL语言将3日的交易数据合并，并选取所需变量，并且将相同的商品进行合并。 Proc sql; CREATE table Homework.JD as select * FROM Homework.JINGD1 UNION ALL select * FROM Homework.JINGD2 UNION ALL select * FROM Homework.JINGD3; 数据挖掘考试题目——关联分析 一、10个选择 1.以下属于关联分析的是（） A．CPU性能预测B．购物篮分析 C．自动判断鸢尾花类别D．股票趋势建模 2.维克托?迈尔-舍恩伯格在《大数据时代：生活、工作与思维的大变革》一书中，持续强调了一个观点：大数据时代的到来，使我们无法人为地去发现数据中的奥妙，与此同时，我们更应该注重数据中的相关关系，而不是因果关系。其中，数据之间的相关关系可以通过以下哪个算法直接挖掘（） A．K-means B．Bayes Network C．C4.5 D．Apriori 3.置信度(confidence)是衡量兴趣度度量（）的指标。 A．简洁性B．确定性 C．实用性D．新颖性 4.Apriori算法的加速过程依赖于以下哪个策略（） A．抽样B．剪枝 C．缓冲D．并行 5.以下哪个会降低Apriori算法的挖掘效率（） A．支持度阈值增大B．项数减少 C．事务数减少D．减小硬盘读写速率 6.Apriori算法使用到以下哪些东东（） A．格结构、有向无环图B．二叉树、哈希树 C．格结构、哈希树D．多叉树、有向无环图 7.非频繁模式（） A．其置信度小于阈值B．令人不感兴趣 C．包含负模式和负相关模式D．对异常数据项敏感 8.对频繁项集、频繁闭项集、极大频繁项集的关系描述正确的是（）[注：分别以1、2、3代表之] A．3可以还原出无损的1 B．2可以还原出无损的1 C．3与2是完全等价的D．2与1是完全等价的 9.Hash tree在Apriori算法中所起的作用是（） A．存储数据B．查找 C．加速查找D．剪枝 10.以下不属于数据挖掘软件的是（） A．SPSS Modeler B．Weka C．Apache Spark D．Knime 二、10个填空 1.关联分析中表示关联关系的方法主要有：和。 2.关联规则的评价度量主要有：和。 3.关联规则挖掘的算法主要有：和。 4.购物篮分析中，数据是以的形式呈现。 5.一个项集满足最小支持度，我们称之为。 6.一个关联规则同时满足最小支持度和最小置信度，我们称之为。 数据挖掘实验报告（二）关联规则挖掘 姓名：李圣杰 班级：计算机1304 学号：1311610602 一、实验目的 1. 1.掌握关联规则挖掘的Apriori算法； 2.将Apriori算法用具体的编程语言实现。 二、实验设备 PC一台，dev-c++5.11 三、实验内容 根据下列的Apriori算法进行编程： 四、实验步骤 1.编制程序。 2.调试程序。可采用下面的数据库D作为原始数据调试程序，得到的候选1项集、2项集、3项集分别为C1、C2、C3，得到的频繁1项集、2项集、3项集分别为L1、L2、L3。 代码 #include 关联规则分析报告 2009年7月8日 目录 一前言 (1) 二数据预处理 (1) 三前7710条真实数据分析 (2) 1商品按小类分析 (2) 2商品按中类分析 (4) 3商品按大类分析 (4) 4分析比较 (5) 四后44904条随机数据分析 (5) 1商品按小类分析 (5) 2商品按中类分析 (7) 3商品按大类分析 (8) 4分析比较 (8) 五52614条混合数据分析 (8) 1商品按小类分析 (8) 2商品按中类分析 (11) 3商品按大类分析 (11) 4分析比较 (12) 六总结 (12) 一前言 使用关联规则挖掘算法分析购物清单时，会产生不止“啤酒→尿布”的单一关联规则，而将出现涉及多种商品的“纵横交错”的多条关联规则。针对这一实际问题，本文利用学生日常购物记录数据进行关联分析，通过概念分层从不同粒度上分析商品之间的关联性，从而找到商品之间的关联规则，实现优化超市货物摆放次序的目的。 二数据预处理 1)在SQL server 2000 查询分析器里执行下面的SQL语句 declare @sql varchar(8000) set @sql = 'select zid ,xh' select @sql = @sql + ' , max(case goodsid when ''' + goodsid + ''' then goodsid end) [' + 'n'+ goodsid + ']' from (select distinct goodsid from rcxfjl) as a set @sql = @sql + ' into table_a from rcxfjl group by zid,xh' exec(@sql) 2)在PB里将有购买记录的列改为”yes” for i=1 to dw_1.rowcount() for li_index=1 to long(dw_1.object.datawindow.column.count) if integer(dw_1.getitemstring(i,dw_1.describe('#' + string(li_index) + ".name")))>0 then dw_1.setitem(i,dw_1.describe('#' + string(li_index) + ".name"),"yes") end if next next 3)将处理好的数据直接导出到Excel中 4)将Excel表中的空格替换成”?”(在weka中?表示缺省值) 聚类分析和关联规则属于数据挖掘这个大概念中的两类挖掘问题， 聚类分析是无监督的发现数据间的聚簇效应。 关联规则是从统计上发现数据间的潜在联系。 细分就是 聚类分析与关联规则是数据挖掘中的核心技术； 从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。 从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。 聚类分析是一种探索性的分析，在分类的过程中，人们不必事先给出一个分类的标准，聚类分析能够从样本数据出发，自动进行分类。聚类分析所使用方法的不同，常常会得到不同的结论。不同研究者对于同一组数据进行聚类分析，所得到的聚类数未必一致。 从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。而且聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他算法（如分类和定性归纳算法）的预处理步骤。 关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(FrequentItemsets)，第二阶段再由这些高频项目组中产生关联规则(AssociationRules)。 关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(LargeItemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。 关联规则挖掘的第二阶段是要产生关联规则(AssociationRules)。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度(MinimumConfidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。 数据挖掘算法之-关联规则挖掘(Association Rule) (2009-09-20 21:59:23) 转载 标签： 分类：DM dm 在数据挖掘的知识模式中，关联规则模式是比较重要的一种。关联规则的概念由Agrawal、Imielinski、Swami 提出，是数据中一种简单但很实用的规则。关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。 一、关联规则的定义和属性 考察一些涉及许多物品的事务：事务1 中出现了物品甲，事务2 中出现了物品乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙在事务中的出现相互之间是否有规律可循呢？在数据库的知识发现中，关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大的影响。 现实中，这样的例子很多。例如超级市场利用前端收款机收集存储了大量的售货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处理时间，顾客购买的物品、物品的数量及金额等。这些数据中常常隐含形式如下的关联规则：在购买铁锤的顾客当中，有70 ％的人同时购买了铁钉。这些关联规则很有价值，商场管理人员可以根据这些关联规则更好地规划商场，如把铁锤和铁钉这样的商品摆放在一起，能够促进销售。 有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合，但稍微转换一下思考角度，仍然可以像售货数据一样处理。比如人寿保险，一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。通过分析这些数据，可以得到类似以下这样的关联规则：年龄在40 岁以上，工作在A 区的投保人当中，有45 ％的人曾经向保险公司索赔过。在这条规则中， 研究生课程论文 关联规则挖掘基本概念和算法 课程名称：数据仓库与数据挖掘 学院：交通运输 专业：交通运输规划与管理 年级：硕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 中的项目也 跟着出现的规律 数据挖掘考试题目一一关联分析 一、10个选择 1. 以下属于关联分析的是（ ） A. CPU 性能预测 B .购物篮分析 C.自动判断鸢尾花类别 D.股票趋势建模 2. 维克托？迈尔-舍恩伯格在《大数据时代：生活、工作与思维的大变革》一书中，持续强 调了一个观点：大数据时代的到来， 们更应该注重数据中的相关关系， 下哪个算法直接挖掘（ ） A. K-means C. 3. 置信度（confidence ）是衡量兴趣度度量（ A.简洁性 C.实用性 算法的加速过程依赖于以下哪个策略（ A 抽样 C.缓冲 使我们无法人为地去发现数据中的奥妙，与此同时，我 而不是因果关系。其中，数据之间的相关关系可以通过以 Bayes Network Ap riori ）的指标。 B .确定性 D.新颖性 ） B .剪枝 D.并行 ） B . D. 5.以下哪个会降低 Apriori 算法的挖掘效率（ A 支持度阈值增大 C.事务数减少 算法使用到以下哪些东东（ ） A.格结构、有向无环图 C.格结构、哈希树 7. 非频繁模式（） A 其置信度小于阈值 C.包含负模式和负相关模式 B .项数减少 D.减小硬盘读写速率 B .二叉树、哈希树 D.多叉树、有向无环图 B .令人不感兴趣 D.对异常数据项敏感 8. 对频繁项集、频繁闭项集、极大频繁项集的关系描述正确的是（ A. 3可以还原出无损的 1 C. 3与2是完全等价的 tree 在Apriori 算法中所起的作用是（ A 存储数据 C.加速查找 10.以下不属于数据挖掘软件的是（ A. SPSS Modeler C. Apache Spark B . D. ) B . D. ）［注：分别以1、2、3代表之］ 2可以还原出无损的1 2与1是完全等价的 查找 剪枝 B . D. Weka Knime 二、10个填空 1. 关联分析中表示关联关系的方法主要 有： 2. 关联规则的评价度量主要有： _______ 3. 关联规则挖掘的算法主要有： _______ 4. 购物篮分析中，数据是以 ___________ ____ 禾n _ ____ 禾n _ 的形式呈现。 5.一个项集满足最小支持度，我们称之为 _____________ o 6?—个关联规则同时满足最小支持度和最小置信度，我们称之为 关联规则挖掘综述 摘要：近年来国内外学者对关联规则进行了大量的研究。为了更好地了解关联规则的挖掘技术，对研究现状有更深入的了解，首先本文对数据挖掘技术进行了介绍，接着介绍了关联数据挖掘的基本原理，最后对经典的挖掘算法进行分类介绍。 关键词：数据挖掘；关联规则；算法；综述 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算法优化 关联规则挖掘算法综述 一、10个选择 1.以下属于关联分析的是（） A．CPU性能预测B．购物篮分析 C．自动判断鸢尾花类别D．股票趋势建模 2.维克托?迈尔-舍恩伯格在《大数据时代：生活、工作与思维的大变革》一书中，持续强调了一个观点：大数据时代的到来，使我们无法人为地去发现数据中的奥妙，与此同时，我们更应该注重数据中的相关关系，而不是因果关系。其中，数据之间的相关关系可以通过以下哪个算法直接挖掘（） A．K-means B．Bayes Network C．D．Apriori 3.置信度(confidence)是衡量兴趣度度量（）的指标。 A．简洁性B．确定性 C．实用性D．新颖性 算法的加速过程依赖于以下哪个策略（） A．抽样B．剪枝 C．缓冲D．并行 5.以下哪个会降低Apriori算法的挖掘效率（） A．支持度阈值增大B．项数减少 C．事务数减少D．减小硬盘读写速率 算法使用到以下哪些东东（） A．格结构、有向无环图B．二叉树、哈希树 C．格结构、哈希树D．多叉树、有向无环图 7.非频繁模式（） A．其置信度小于阈值B．令人不感兴趣 C．包含负模式和负相关模式D．对异常数据项敏感 8.对频繁项集、频繁闭项集、极大频繁项集的关系描述正确的是（）[注：分别以1、2、3代表之] A．3可以还原出无损的1 B．2可以还原出无损的1 C．3与2是完全等价的D．2与1是完全等价的 tree在Apriori算法中所起的作用是（） A．存储数据B．查找 C．加速查找D．剪枝 10.以下不属于数据挖掘软件的是（） A．SPSS Modeler B．Weka C．Apache Spark D．Knime 二、10个填空 1.关联分析中表示关联关系的方法主要有：和。 2.关联规则的评价度量主要有：和。 3.关联规则挖掘的算法主要有：和。 4.购物篮分析中，数据是以的形式呈现。 5.一个项集满足最小支持度，我们称之为。 6.一个关联规则同时满足最小支持度和最小置信度，我们称之为。 数据挖掘中关联规则挖掘的应用研究 吴海玲，王志坚，许峰 河海大学计算机及信息工程学院，江苏南京（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．由频繁项集产生强关联规则。根据定义，这些规则必须满足最小支持度和最小可信度。 关联规则挖掘的问题的主要特征是数据量巨大，因此算法的效率很关键。目前研究的重点在第一步，即发现频繁项目集，因此第二步相对来说是很容易的。 本技术提供了一种基于大数据挖掘的虚拟身份关联分析算法模型，属于大数据挖掘技术领域。该方法包括获取电子串号信息和物理地址信息；对源数据进行清洗处理、规则过滤；并对处理后的数据进行属性分割、特征提取、指标计算；针对样本类别不平衡问题，调整不同类别训练样本；搭建Logistic Regression算法模型，以计算手机物理地址和电子串号之间关系的匹配度，实现虚拟身份的挖掘分析和关联匹配，本技术可以通过轨迹追查，确定犯罪轨迹，对犯罪嫌疑人实施跟踪和追捕，侦破案件，最终达到对犯罪的有效控制和打击。 技术要求 1.一种基于大数据挖掘的虚拟身份关联分析算法模型，其特征在于，包括以下步骤： S1：电子串号及物理地址数据预处理；分别对无线数据采集终端的电子串号和物理地址 的脏数据进行处理； S2：关联数据筛选及存储；将满足筛选规则的数据存储于数据库中； S3：样本特征构建及提取；对关联数据进行属性分割及结合，构建M个样本特征，并对特征数据进行降维处理，使样本变量维度变为N； S4：类别不平衡问题处理；采用Fisher判别法调整不同类别训练样本； S5：建立及优化电子串号与物理地址关联模型；根据算法建立模型，得出电子串号与物 理地址的匹配度。 2.根据权利要求1所述的基于大数据挖掘的虚拟身份关联分析算法模型，其特征在于，所述步骤S2中筛选规则具体步骤为： S201、将时间差范围内(即|t1-t2|<Δt，其中t1和t2分别表示电子串号和物理地址被采集到的时间)采集到的电子串号和物理地址数据中的无线数据采集终端经纬度字段进行匹配，若经纬度一致，则将此组电子串号和物理地址作为匹配对，并转入步骤S202；若不一致，则舍弃； S202、从预处理后的数据中分别取出匹配对相应的电子串号/物理地址、采集时间、经度和纬度等字段，满足以下条件的匹配对保留作为匹配组并存储：|d1-d2| 数据挖掘中的关联规则 程晓飞2009306202008 摘要： 近年来，数据挖掘己经引起了信息产业界的极大关注，这是快速增长的数据量和曰益贫乏的信息量之间矛盾运动的必然结果，对数据挖掘技术进行系统、深入、全面、详尽地研究是全球信息化发展的客观需要。本文对数据挖掘技术，尤其是关联规则数据挖掘技术进行了系统、深入、全面、详尽地分析和研究。 关键词：数据挖掘；关联规则；Ａｐｒｉｏｒｉ算法；基于划分的算法 1.什么是关联规则 在描述有关关联规则的一些细节之前，我们先来看一个有趣的故事："尿布与啤酒"的故事。 在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是："跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在"尿布与啤酒"背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。 按常规思维，尿布与啤酒风马牛不相及，若不是借助数据挖掘技术对大量交易数据进行挖掘分析，沃尔玛是不可能发现数据内在这一有价值的规律的。 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算 关联规则挖掘在商业销售中的应用 戚芸 （班级：数科院08（6）班学号：08213118） [摘要]数据挖掘是近些年企业界相当热门的话题，它利用统计与人工智能的算法，从庞大的企业历史资料中，找出隐藏的规律并简历准确的模型，用以预测未来。其中关联规则的挖掘是数据挖掘的一个重要问题。[关键字]关联规则支持度置信度增益 一、关联规则的概述 关联规则一般用以发现交易数据库中不同商品 (项)之间的联系 ,用这些规则找出顾客的购买行为模式 ,比如购买了某一种商品对购买其他商品的影响 ,这种规则可以应用于超市商品货架设计、货物摆放以及根据购买模式对用户进行分类等。进而引伸至寻找一个变量间不同选择之间的关系,或寻找不同变量间的关系。以交易数据为例描述关联规则 : 给定一个交易集 ,该交易集包含一系列商品 ,则一条关联规则可以表示为 : X → Y 二、关联规则的分类 （1）按关联规则中处理变量的类别,可将关联规则分为布尔型和数值型布尔型关联规则中对应变量都是离散变量或类别变量,它显示的是离散型变量间的关系,比如“买啤酒→买婴儿尿布”;数值型关联规则处理则可以与多维关联或多层关联规则相结合,处理数值型变量,如“月收入5000 元→每月交通费约800 元”。 （2）按关联规则中数据的抽象层次,可以分为单层关联规则和多层关联规则单层关联规则中,所有变量都没有考虑到现实的数据具有多个不同的层次;而多层关联规则中,对数据的多层性已经进行了充分的考虑。比如“买夹克→买慢跑鞋”是一个细节数据上的单层关联规则,而“买外套→慢跑鞋”是一个较高层次和细节层次间的多层关联规则。 （3）按关联规则中涉及到的数据维数可以分为单维关联规则和多维关联规则单维关联规则只涉及数据的一个维度(或一个变量) ,如用户购买的物品;而多维关联规则则要处理多维数据,涉及多个变量,也就是说,单维关联规则处理单一属性中的关系,而多维关联规则则处理多个属性间的某些关系。比如“买啤酒→买婴儿尿布”只涉及用户购买的商品,属于单维关联规则,而“喜欢野外活动→购买慢跑鞋”涉及到两个变量的信息,属于二维关联规则。 数据挖掘关联分析 1 引言 在大型数据库中，关联规则挖掘是最常见的数据挖掘任务之一．关联规则挖掘就是从大量数据中发现项集之间的相关联系．Apriori 算法，前者采用逐层搜索的迭代策略，先产生候选集，再对候选集进行筛选，然后产生该层的频繁集。 2 Apriori 算法 Apriori 算法是关联规则挖掘中最基本也是最常见的算法．它是由Agrawal 等人于1993年提出的一种最有影响的挖掘布尔关联规则频繁项集的算法，主要用来在大型数据库上进行快速挖掘关联规则。 2.1 算法基本思想 Apriori 算法采用逐层迭代搜索方法，使用候选项集来找频繁项集。其基本思想是: 首先找出所有频繁1－项集的集合L l，L1用于找频繁2－项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k－项集。并利用事先设定好的最小支持度阈值进行筛选，将小于最小支持度的候选项集删除，再进行下一次的合并生成该层的频繁项集。经过筛选可减少候选项集数，从而加快关联规则挖掘的速度。 2.2 算法的挖掘 如果一个项集是频繁的，那么它的所有子集都是频繁的 先验原理成立的原因: X s Y Y ? ? ? X≥ ,Y X ( ) ( ) ) s (: 一个项集的支持度不会超过其任何子集的支持度 该性质称作支持度的反单调性质 2.2.1候选项集的生成 Apriori 算法使用了Apriori性质来产生候选项集．任何非频繁的( k－1 )项集都不可能是频繁k－项集的子集．因此，如果一个候选k－项集的( k－1 )－子集不在L k －1中，则该候选项集也不可能是频繁的，从而可以从C k中删除． 2.2.2由L k-1 生成L k 设定k=1 扫描事务数据库一次，生成频繁的1-项集 如果存在两个或以上频繁k-项集，重复下面过程： [候选产生] 由长度为k的频繁项集生成长度为k+1的候选项集 [候选前剪枝] 对每个候选项集，若其具有非频繁的长度为k的子集，则删除该候选项集 [支持度计算] 扫描事务数据库一次，统计每个余下的候选项集的支持度 [候选后剪枝] 删除非频繁的候选项集，仅保留频繁的(k+1)-项集，设定k = k+1 关联规则数据挖掘 学习报告 . 目录 引言 2 案例 2 关联规则 3 （一）关联规则定义 （二）相关概念 （三）关联规则分类 数据 6 （一）小型数据 （二）大型数据 应用软件7 （一）WEKA （二）IBM SPSS Modeler 数据挖掘12 总结27 一、引言 数据库与互联网技术在日益发展壮大，人们每天可以获得的信息量呈指数级增长。如何从这浩如瀚海的数据中找出我们需要的数据显得尤为重要。数据挖掘又为资料探勘、数据采矿。它是数据库知识发现中的一个步骤。数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。数据挖掘通常与计算机科学有关，并通过统计、在线分析处理、情报检索、机器学习、专家系统（依靠过去的经验法则）和模式识别等诸多方法来实现上述目标。 数据挖掘大致分为以下几类：分类（Classification）、估计（Estimation）、预测（Prediction）、相关性分组或关联规则（Affinity grouping or association rules）、聚类（Clustering）、复杂数据类型挖掘(Text, Web ,图形图像，视频，音频等)。 二、案例 "尿布与啤酒"的故事。 在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是："跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在"尿布与啤酒"背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。 按常规思维，尿布与啤酒风马牛不相及，若不是借助数据挖掘技术对大量交易数据进行挖掘分析，沃尔玛是不可能发现数据内在这一有价值的规律的。关联规则数据挖掘
(整理)数据挖掘-关联
最新数据挖掘考试题目——关联分析资料
数据挖掘实验报告-关联规则挖掘
数据挖掘关联规则分析报告
聚类分析、数据挖掘、关联规则这几个概念的关系
数据挖掘算法之关联规则
关联规则挖掘基本概念和算法--张令杰10121084
数据挖掘考试题目——关联分析
关联规则挖掘综述
关联规则挖掘算法综述
本文介绍了关联规则的基本概念和分类方法， 列举了一些关联规则挖掘算法并简 要分析了典型算法，展望了关联规则挖掘的未来研究方向。
1 引言
关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。 它在数据挖掘中 是一个重要的课题，最近几年已被业界所广泛研究。 关联规则挖掘的一个典型例子是购物篮分析。 关联规则研究有助于发现交易数据 库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对 购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购 买模式对用户进行分类。 Agrawal 等于 1993 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题 [AIS93b]，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们 的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算 法挖掘规则的效率；对关联规则的应用进行推广。 最近也有独立于 Agrawal 的频集方法的工作[HPY00]，以避免频集方法的一些缺 陷，探索挖掘关联规则的新方法。也有一些工作[KPR98]注重于对挖掘到的模式 的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。
2 基本概念
设 I={i1,i2,..,im}是项集，其中 ik(k=1,2,…,m)可以是购物篮中的物品，也可 以是保险公司的顾客。设任务相关的数据 D 是事务集，其中每个事务 T 是项集， 使得 TÍI。设 A 是一个项集，且 AÍT。 关联规则是如下形式的逻辑蕴涵：A Þ B，AÌI, AÌI，且 A∩B=F。关联规则具有如下两个重要的属性： 支持度: P(A∪B)，即 A 和 B 这两个项集在事务集 D 中同时出现的概率。 置信度: P(B｜A)，即在出现项集 A 的事务集 D 中，项集 B 也同时出现的概率。 同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。 给定一个事务集 D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度 和最小可信度的关联规则，也就是产生强规则的问题。
3 关联规则种类数据挖掘考试题目——关联分析
数据挖掘中关联规则挖掘的应用研究
基于大数据挖掘的虚拟身份关联分析算法模型的制作方法
数据挖掘中的关联规则2
数据挖掘中的关联规则
数据挖掘关联分析
关联规则数据挖掘
相关主题
文本预览