基于数值属性的关联规则挖掘论文.doc

基于数值属性的关联规则挖掘
目 录
第一章 数据挖掘导论 1
1.1数据挖掘的历史与现状 1
1.2数据挖掘的基本知识 3
1.3数据挖掘的常用技术 5
第二章 工具介绍――VC++数据库接口 6
2.1 用VC++访问数据库的优点 6
2.2 ODBC数据库访问接口 6
第三章 关联规则挖掘 11
3.1 关联规则的基本概念 11
2.2 关联规则的种类 11
3.3 单维布尔关联规则挖掘 12
3.3.1 Apriori算法 12
3.3.2关联规则的生成 17
3.3.3 Apriori算法的改进 18
第四章 基于数值型的关联规则挖掘 19
4.1数值型关联规则 19
4.1.1数值关联规则挖掘问题的产生 19
4.1.2数值关联规则挖掘的基本方法 19
4.1.3数值关联规则挖掘问题的定义及分解 21
4.1.4 连续属性的离散化 21
4.1.5兴趣度 22
4.1.6数值关联规则的挖掘算法 22
4.2聚类分析 23
4.2.1 聚类定义 23
4.2.2对基于划分的经典算法的一些改进 24
4.2.3一个新的聚类算法DBCLAD 28
4.3算法的实现 33
4.3.1 DBCLAD算法的实现 33
4.3.2 DBCLAD算法一个应用实例 36
4.4算法的比较 38
结论与展望 39
毕业设计过程中所遇问题及解决方法 40
致 谢 41
第一章 数据挖掘导论
本章将从数据管理演化角度，介绍数据挖掘的由来以及数据挖掘的作用和意义，同时也将简单介绍数据挖掘领域使用的一些技术。
1.1数据挖掘的历史与现状
我们现在已经生活在一个网络化的时代，通信、计算机和网络技术正改变着整个人类和社会。如果用芯片集成度来衡量微电子技术，用CPU处理速度来衡量计算机技术，用信道传输速率来衡量通信技术，那么摩尔定律告诉我们，它们都是以每18个月翻一番的速度在增长，这一势头已经维持了十多年。在美国，广播达到5000万户用了38年；电视用了13年；Internet拨号上网达到5000万户仅用了4年。全球IP网发展速度达到每6个月翻一番，国内情况亦然。1999年初，中国上网用户为210万，现在已经达到600万。网络的发展导致经济全球化，在1998年全球产值排序前100名中，跨国企业占了51个，国家只占49个。有人提出，对待一个跨国企业也许比对待一个国家还要重要。在新世纪钟声刚刚敲响的时候，回顾往昔，人们不仅要问：就推动人类社会进步而言，历史上能与网络技术相比拟的是什么技术呢?有人甚至提出要把网络技术与火的发明相比拟。火的发明区别了动物和人，种种科学技术的重大发现扩展了自然人的体能、技能和智能，而网络技术则大大提高了人的生存质量和人的素质，使人成为社会人、全球人。
　　现在的问题是：网络之后的下一个技术热点是什么？让我们来看一些身边俯拾即是的现象：《纽约时报》由60年代的10～20版扩张至现在的100～200版，最高曾达1572版；《北京青年报》也已是16～40版；市场营销报已达100版。然而在现实社会中，人均日阅读时间通常为30～45分钟，只能浏览一份24版的报纸。大量信息在给人们带来方便的同时也带来了一大堆问题：第一是信息过量，难以消化；第二是信息真假难以辨识；第三是信息安全难以保证；第四是信息形式不一致，难以统一处理。人们开始提出一个新的口号：“要学会抛弃信息”。人们开始考虑：“如何才能不被信息淹没，而是从中及时发现有用的知识、提高信息利用率？”另一方面，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。
　　面对这一挑战，数据挖掘（DM）技术应运而生，并显示出强大的生命力。数据挖掘其实是一个逐渐演变的过程,电子数据处理的初期,人们就试图通过某些方法来实现自动决策支持,当时机器学习成为人们关心的焦点.机器学习的过程就是将一些已知的并已被成功解决的问题作为范例输入计算机,机器通过学习这些范例总结并生成相应的规则,这些规则具有通用性,使用它们可以解决某一类的问题.随后,随着神经网络技术的形成和发展,人们的注意力转向知识工程,知识工程不同于机器学习那样给计算机输入范例，让它生成出规则，而是直接给计算机输入已被代码化的规则，而计算机是通过使用这些规则来解决某些问题。专家系统就是这种方法所得到的成果，但它有投资大、效果不甚理想等不足。80年代人们又在新的神经网络理论的指导下，重新回到机器学习的方法上，并将其成果应用于处理大型商业数据库。随着在80年代末一个新的术语，它就是数据库中的知识发现，简称KDD(Knowledge discovery in database).它泛指所有从源数据中发掘模式或联系的方法，人们接受了这个术语，并用KDD来描述整个数据发掘的过程，包括最开始的制定业务目标到最终的结果分析，而用数据挖掘（data mining）来描述使用挖掘算法进行数据挖掘的子过程。但最近人们却逐渐开始使用数据挖掘中有许多工作可以由统计方法来完成，并认为最好的策略是将统计方法与数据挖掘有机的结合起来。
进化阶段
商业问题
支持技术
产品厂家
产品特点
数据搜集
(60年代)
“过去五年中我的总收入是多少？”
计算机、磁带和磁盘
IBM,CDC
提供历史性的、静态的数据信息
数据访问
(80年代)
“在新英格兰的分部去年三月的销售额是多少？”
关系数据库（RDBMS），结构化查询语言（SQL），ODBC Oracle、Sybase、Informix、IBM、Microsoft
Oracle、Sybase、Informix、IBM、Microsoft
在记录级提供历史性的、动态数据信息
数据仓库；
决策支持
(90年代)
“在新英格兰的分部去年三月的销售额是多少？波士顿据此可得出什么结论？”
联机分析处理（OLAP）、多维数据库、数据仓库
Pilot、Comshare、Arbor、Cognos、Microstrategy
在各种层次上提供回溯的、动态的数据信息
数据挖掘
（正在流行）
“下个月波士顿的销售会怎么样？为什么？”
高级算法、多处理器计算机、海量数据库
Pilot、Lockheed、IBM、SGI、其他初创公司
提供预测性的信息
表1.数据挖掘的进化历程
1.2数据挖掘的基本知识
1.2.1 数据挖掘的定义
　　数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。
与　　数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。
　　----何为知识?从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。
　　这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。
1.2.2 数据挖掘的功能
　　数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下五类功能[1]。
　　1.自动预测趋势和行为
　　数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问题，数据挖掘使用过去有关促销b的数据来寻找未来投资中回报最大的用户，其它可预测的问题包括预报破产以及认定对指定事件最可能作出反应的群体。
　　2. 关联分析
　　数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。
　　3. 聚类
　　数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统的模式识别方法和数学分类学。80年代初，Mchalski提出了概念聚类技术牞其要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术的某些片面性。
　　4.概念描述
　　概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。
　　5.偏差检测
　　数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意义的差别。
1.3数据挖掘的常用技术
1.人工神经网络[2]
　　神经网络近来越来越受到人们的关注，因为它为解决大复杂度问题提供了一种相对来说比较有效的简单方法。神经网络可以很容易的解决具有上百个参数的问题（当然实际生物体中存在的神经网络要比我们这里所说的程序模拟的神经网络要复杂的多）。神经网络常用于两类问题：分类和回归。
2.决策树
　　决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。
　　决策树很擅长处理非数值型数据，这与神经网络只能处理数值型数据比起来，就免去了很多数据预处理工作。
甚至有些决策树算法专为处理非数值型数据而设计，因此当采用此种方法建立决策树同时又要处理数值型数据时，反而要做把数值型数据映射到非数值型数据的预处理。
3.遗传算法
　　基于进化理论，并采用遗传结合、遗传变异、以及自然选择等设计方法的优化技术。
4.近邻算法
　　将数据集合中每一个记录进行分类的方法。
5.关联规则推导
　　从统计意义上对数据中的“如果-那么”规则进行寻找和推导。
　　采用上述技术的某些专门的分析工具已经发展了大约十年的历史，不过这些工具所面对的数据量通常较小。而现在这些技术已经被直接集成到许多大型的工业标准的数据仓库和联机分析系统中去了。
第二章 工具介绍――VC++数据库接口
2.1 用VC++访问数据库的优点
VC++提供了多种多样的数据库访问技术：ODBC，DAO，OLEDB，ADO等。这些技术为数据库应用程序的开发于操作带来了极大的方便。主要表现在以下几个方面[7]：
1． 简单性。VC++中提供了MFC类库、ATL模版类以及AppWizard，ClassWizard等一系列的Wizard工具用于帮助用户快速的建立自己的应用程序，大大简化了应用程序的设计。使用这些技术，可以使开发者编写很少的代码或不需要编写代码就可以开发一个数据库应用程序。
2． 灵活性。VC++提供的开发环境可以使开发者根据自己的需要设计应用程序的界面和功能，而且，VC++提供了丰富的类库和方法，可以使开发者根据自己的应用特点进行选择。
3． 访问速度快。为了解决ODBC开发的数据库应用程序访问数据库速度慢的问题，VC++提供了新的访问技术OLEDB和ADO，它们都是基于COM接口的技术。使用这种技术可以直接对数据库的驱动程序进行访问，大大提高了访问速度。
4． 可扩展性。VC++提供了OLE技术和ActiveX技术，这种技术可以增强应用程序的能力。使用OLE技术和ActiveX技术利用使开发者利用VC++中提供的各种组件、控件以及第三方开发者提供的组件来创建自己的程序，从而实现应用程序的组件化。使用这种技术可以使应用程序具有良好的可扩展性。
5． 访问不同种类的数据源。传统的ODBC技术只能访问关系数据库，在VC++中，提供了OLEDB技术，不仅可以访问关系数据库，还可以访问非关系数据库。

2.2 ODBC数据库访问接口
Microsoft 开发数据库互连（ODBC，Open Database Connectivity）是Microsoft Windows开放服务体系（WOSA）的一部分，是一个数据库访问的标准接口。使用这一标准接口，可以不关心具体的数据库管理系统的细节，而只要有相应类型的数据库的ODBC驱动程序，就可以实现对数据库的访问。ODBC的界面一致性使得它实现了最大程度的互操作性。任何一个简单的应用程序，都可以通过一套通用的代码访问不同的RDBMS平台[7]。
ODBC是一个应用广泛的数据库访问应用编程接口，使用标准的SQL作为其数据库访问语言。
ODBC编程接口提供了极大的灵活性。可以通过这一个访问接口访问不同种类是数据库。而且，通过相应的ODBC驱动程序，可以方便的实现不同数据类型之间的转换。
在计算机上安装和配置ODBC驱动程序的时候，应当使用控制面板中的ODBC数据源选项。ODBC数据源选项也可以用来注册数据源名称（DSN）。DSN是一个具有唯一命名的信息集合，ODBC驱动程序管理器通过它才能将应用程序连接到特定的ODBC数据库。DSN必须在需要使用的特定系统上进行注册，它可以保存在某个文件中（文件DSN），也可以保存在注册表中（机器DSN）。机器DSN既可以为某个特定的用户安装，也可以让这台机器的所有用户都能访问（系统DSN）。
ODBC通常是用SQL访问数据的。当某个应用程序需要从数据资源获得数据时，该应用程序将向ODBC驱动程序管理器发送SQL语句。然后，ODBC驱动程序管理器就加载ODBC驱动程序。接着，ODBC驱动程序将应用程序发送的SQL语句翻译成DBMS使用的SQL，并把它发送给数据库服务器。DBMS取回数据并通过驱动程序和驱动程序管理器把它传回给应用程序。
ODBC还提供了一个游标库，任何驱动程序，只要达到ODBC conformance的最低级别，就可以使用这个库中的滚动指针，还可以用指针在某个数据库的某几行记录之间反复滚动。
（1） ODBC数据库访问结构
通过ODBC访问数据库的结构如图2.1所示

图2.1 ODBC数据库访问结构
ODBC是通过使用驱动程序（Driver）来实现应用程序对数据库的独立性的。各个模块的功能分别是：
● ODBC应用程序通过ODBC函数向数据库发送SQL语句并处理返回结果
● ODBC驱动程序管理器负责管理和装载特定的驱动程序
● ODBC驱动程序负责处理ODBC函数调用，提交SQL请求给特定的数据源并返回结果给应用程序。
● 数据源指要存取的数据及其相关的操作系统、数据库管理系统和网络系统。
（2） VC＋＋数据库应用程序结构
典型的VC++数据库应用程序的结构如图2.2所示。

图2.2 VC++数据库应用程序结构
下面详述各个模块之间的关系：
1） 数据源与记录集
在VC＋＋的MFC类库中，提供了数据源类（CDatabase）来实现对数据源的一个连接，又提供了记录集类（CRecordset）来管理数据源中选定的记录集合。开发时要从MFC的CRecordset类继承出自己的记录集类。
数据源对象与程序中的记录集对象关联在一起，通过在程序中操纵记录集对象来实现对数据源的访问。在记录集对象中维护着数据源中被访问的当前记录，通过Move之类的函数（如CRecordset::MoveFirst，CRecordset::MoveNext）可以改变当前记录，从而实现对整个数据源的访问。
数据源与记录集之间的信息交换是通过“记录域交换”（RFX）机制来实现的，如CRecordset:: DoFieldExchange。这个信息交换操作会由打开记录集、重新检索数据源和更新数据源等操作触发（对应于CRecordset::Open、CRecordset::Requery和CRecordset::Update等函数）。
2）视图与记录集
VC的MFC类库中提供了CRecordView类，是用来快速构建数据操作界面的视图类。开发时要从MFC的CRecordView类继承出自己的视图类。
视图对象与一个记录集对象绑定在一起，通过“对话框数据交换”（DDX）机制来实现视图与记录集间的信息传递，如CRecordView:: DoDataExchange。这由CWnd::UpdateData触发。
除了视图与记录集绑定这种方式外，也可以用非绑定的方式来实现视图与记录集间的交互。即用一般的视图（如CFormView）来创建数据操作界面。这种情况也是很普遍的，如果在想在一个已有程序中添加数据库操作，但是原有程序的视图类并没有从CRecordView继承，那么用非绑定的方式就可以最小限度的修改原有程序。
构造记录集对象时要把它所连接的数据源对象作为参数传递给记录集对象的构造函数，但在绑定和非绑定这两种情况下创建记录集的方式有所不同，应当引起注意：
● 在绑定的方式下，在视图中创建了记录集，并以NULL为参数传给记录集类的构造函数。具体过程是这样的，VC自动生成了一个数据源对象，并自动根据生成记录集时定义的数据源信息（在重载的CRecordset::GetDefaultConnect函数中）来打开该数据源对象，建立到相应数据源的一个连接。
● 在非绑定的方式下，记录集要自己手动创建，所以要先创建一个数据源对象，并将其作为参数传给记录集类的构造函数。如m_pMyRecordSet=new CMyRecordSet(&m_MyDBOdbc)；。
（3） 编程技巧及注意事项
1) 在调用CRecordset::Update函数更新数据源之前，要调用CRecordset::Edit函数做好对数据源进行更新操作的准备，否则用CWnd::UpdateData触发的对记录集的更新以及直接修改记录集数据的操作将反映不到数据源中。
2) 在调用Move之类函数（如CRecordset::MoveFirst，CRecordset::MoveNext）之前，应当调用CRecordset::IsBOF和CRecordset::IsEOF来防止出现异常。CRecordset::IsBOF判断记录集是否为空，CRecordset::IsEOF判断是否越出最后一条记录。两者都是用来判断当前记录是否有效的。
3) 当手动添加或删除记录集中对应于数据源表格字段的成员变量时，不要忘了在记录集的构造函数中修改表征字段个数的成员变量（CRecordset::m_nFields）。同样，对于参数个数的改变也要相应修改成员变量CRecordset::m_nParams。
4) 由于不同的ODBC驱动程序所支持的数据库操作能力不同，所以，对于记录集类的一些操作，在执行之前要先判断该操作是否被支持。比如Requery之前，先调用CanRestart判断能否重新检索。
5) 可以在记录集重载的CRecordset::GetDefaultSQL()函数中指定默认的SQL语句。SQL语句可先用相应的数据库管理系统（如SQL SERVER,ACCESS等）生成，保证其正确性，再写入程序中。对于设定记录集的过滤和排序等成员变量时也可采取这种办法，由于不同DBMS对表现形式定义不同，这样做可以避免出现错误。
6) 在非绑定的方式下创建记录集时，要注意数据源对象的生存期问题。一般在视图对象中维护一个记录集的成员变量，并通过如下方式来生成记录集对象：
void CmyView::CreateRecordset()
{
…
m_pMyRecordset=new CMyRecordset(&m_MyDBOdbc)；
…
}
这时，由于m_pMyRecordset的作用域是整个类，而传递的数据源参数是以引用方式传递的，所以，数据源对象m_MyDBOdbc不能定义为局部变量，否则，在CreateRecordset函数之外的其它函数中使用m_pMyRecordset时，由于m_MyDBOdbc在内存中已经销毁，所以会产生异常。一般可以将m_MyDBOdbc定义为成员变量来解决此问题。
第三章 关联规则挖掘
3.1 关联规则的基本概念
关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。
设I={i1, i2,…, im}是二进制文字的集合，其中的元素称为项(item)。记D为交易(transaction)T的集合，这里交易T是项的集合，并且TÍI 。对应每一个交易有唯一的标识，如交易号，记作TID。设X是一个I中项的集合，如果XÍT，那么称交易T包含X。
一个关联规则是形如XÞY的蕴涵式，这里XÌI, YÌI，并且XÇY=F。规则XÞY在交易数据库D中的支持度（support）是交易集中包含X和Y的交易数与所有交易数之比，记为support(XÞY)，即
support(XÞY)=|{T:XÈYÍT，TÎD}|/|D|
规则XÞY在交易集中的可信度（confidence）是指包含X和Y的交易数与包含X的交易数之比，记为confidence(XÞY)，即
confidence(XÞY)=|{T: XÈYÍT，TÎD}|/|{T:XÍT，TÎD}|
给定一个交易集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度(minsupp)和最小可信度(minconf)的关联规则[8]。

2.2 关联规则的种类
我们将关联规则按不同的情况进行分类[8]：
1.    基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。
布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。
例如：性别=“女”=>职业=“秘书” ，是布尔型关联规则；性别=“女”=>avg（收入）=2300，涉及的收入是数值类型，所以是一个数值型关联规则。
2.  基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。
在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。
例如：IBM台式机=>Sony打印机，是一个细节数据上的单层关联规则；台式机=>Sony打印机，是一个较高层次和细节层次之间的多层关联规则。
3.  基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。
在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。
例如：啤酒=>尿布，这条规则只涉及到用户的购买的物品；性别=“女”=>职业=“秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。

3.3 单维布尔关联规则挖掘
这一节将要介绍最简单关联规则（单维单层布尔关联规则）的挖掘方法。下面首先要介绍Apriori算法，它是挖掘频繁项集的基本算法；3.3.2节将介绍如何根据挖掘出的频繁项集生成相应的强关联规则；3.3.3节将介绍若干Apriori算法改进以提高挖掘效率和可扩展性。
3.3.1 Apriori算法
Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；提出各种变体，如泛化的关联规则、周期关联规则等，对关联规则的应用进行推广。
就是Agrawal等在1993年设计了一个基本算法――Apriori算法，提出了挖掘关联规则的一个重要方法 — 这是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设计可以分解为两个子问题：
1)        找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频集（Frequent Itemset)。
2)        使用第1步找到的频集产生期望的规则，根据定义，这些规则必须满足最小支持度和最小可信度。。
这里的第2步相对简单一点。如给定了一个频集Y=I1I2...Ik，k32，Ij∈I，产生只包含集合{I1，I2，...，Ik}中的项的所有规则(最多k条)，其中每一条规则的右部只有一项，(即形如[Y-Ii]TIi，"1￡i￡k)，这里采用的是[4]中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。对于规则右部含两个以上项的规则，在其以后的工作中进行了研究，本文后面考虑的是这种情况。
算法Apriori使用根据候选生成的逐层迭代找出频繁项集。
输入：事务数据库D；最小支持度阈值min_sup。
输出：D中的频繁项集L
方法：
（1）     L1={ large1-itemsets }
（2）     For (k=2; Lĸ-ı ≠f;k++) do begin
（3）     Ck=Apriori-gen(Lĸ-1) //新的候选项集
（4）     For all transaction t∈D do begin
（5）     Ct=subset(Ck,t); //变量t中所包含的候选集
（6）     for all candidates c∈Ct do
（7）     C.count ++;
（8）     end
（9）     Lĸ ={C∈Ck|C.count≥ min_sup}
（10）  end
（11）  Answer=ÜLĸ
首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。
Apriori的性质：
频繁项集的所有非空子集都必须也是频繁的，根据这个性质，我们分析如何由Lĸ-ı推出Lĸ。算法分两步完成（apriori—gen 由Join和Prune完成）[1]。
（1）连接步。
为了找Lĸ，通过Lĸ-ı与自己连接产生候选K项集，该候选项集记为Cĸ。
设Lı和L2是Lĸ-ı中的项集，记号Li[j]表示Li的第j项。如果Lı[1]=L2[1]∧……∧Lı[k-2]=L2[k-2] ∧L1[k-1] < L2[k-1],则做Lĸ-ı ∞ Lĸ-ı, 连接条件是两个项的前k-2项相同，连接结果为：Lı[1] Lı[2] ….. Lı[k-1] L2[k-1]
（2 剪枝步
联结之后的结果Ck是Lĸ的超集，它的成员可能是不频繁的，这时就要从扫描数据库确定Ck中每个候选的计数，从而确定Lĸ。
确定Lĸ可用Apriori性质对Ck进行剪枝，把子集不在Lĸ-ı 中的候选K项从Ck中删除。
示例：设有事务数据库，有9个事务（见表6-1），假设事务的项按字典顺序存放。
表3-1 示例数据库

T I D 项 ID 的列表

T 100 I1,I2,I5
T 200 I2,I4
T 300 I2,I3
T 400 I1,I2,I4
T 500 I1,I3
T 600 I2,I3
T 700 I1,I3
T 800 I1,I2,I3,I5
T 900 I1,I2,I3

设最小支持度阈值为2，按算法的步骤依次求频繁项集。
（1）     求候选-项集。对每个项的出现次数记数（求记数代替概率）。见表6-2
表 6-2
C1：
项集 支持度计算
I1 6
I2 7
I3 6
I4 2
I5 2

（2）     由于最小支持度阈值为2，故频繁1项集L1=C1

（3）     为发现频繁2项集L2，算法使用L1 ∞ L1，产生候选2项集C2，C2的个数为C²|L1|。

C2：
项集 项集 支持度计数

I1,I2 （I1,I2） 4
I1,I3 （I1,I3） 4
I1,I4 （I1,I4） 1
I1,I5 对每个候选计数 （I1,I5） 2
I2,I3 （I2,I3） 4
I2,I4 （I2,I4） 2
I2,I5 （I2,I5） 2
I3,I4 （I3,I4） 0
I3,I5 （I3,I5） 1
I4,I5 （I4,I5） 0

（4）     扫描D中事务，计算C2中每个候选项集的支持计数。
（5）     求出频繁2项集L2。

项集 支持度计数
I1，I2 4
I1，I3 4
I1，I5 2
I2，I3 4
I2，I4 2
I2，I5 2
（6）     求候选3项集C3。C3=L2 ∞ L2
C3={{I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}} ∞ {{ I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}}
{{I1，I2，I3}， ①
{I1，I2，I5}， ②
{I1，I3，I5}， ③
{I2，I3，I4}， ④
{I2，I3，I5}， ⑤
{I2，I4，I5}} ⑥
求Lĸ，对C3进行剪枝。
其中①、②的子集均在L2中，故保留；
③的子集{I3，I5}ÏL2中，删除③；
④的子集{I3，I4}ÏL2中，删除④；
⑤的子集{I3，I5}ÏL2中，删除⑤；
⑥的子集{I4，I5}ÏL2中，删除⑥；
所以，C3={{I1，I2，I3}，{I1，I2，I5}}。
（7）     求L3。比较候选支持度计数与最小支持度计数得：

项集 支持度计数

I1，I2，I3 2
I1，I2，I5 2
所以 L3=C3
（8）     求C4= L3 ∞ L3={I1，I2，I3，I5}
子集{I2，I3，I5}Ï L3,故剪去；
故C4=f，算法终止。
（9） 结果为L=L1 U L2 U L3
该算法用VC++实现，运行结果如下：

设置支持度为0.1，运行得：

3.3.2关联规则的生成
可信度用下列公式表示：
Confidence(AÞB)=support_count(A U B)/support_count(A)
其中support_count(A U B)是包含项集A U B的事务数；support_count（A）是包含项集A 的事务数；
关联规则的产生方法：
（1）  对于每个频繁项集L，产生L的所有非空子集；
（2）   对于L的每个非空子集S，如果support_count(L)/support_count(L)≥minconf,则输出规则“SÞ (L-S)”。其中minconf是最小可信度阈值。
例：设频繁项集L={I1，I2，I5}，由L产生哪些关联规则：
§ 求L的非空子集：{I1,I2},{I1,I5},{I2,I5},{I1},{I2},{I5},

(支持度计数) 4 2 2 6 7 2
§ support_count(L)=2，关联规则如下：
<A> I1 ∧ I2Þ I5 Confidence=2/4=50%
<B> I1 ∧ I5 Þ I2 Confidence=2/2=100%
<C> I2 ∧ I5 Þ I1 Confidence=2/2=100%
<D> I1 Þ I2 ∧ I5 Confidence=2/6=33%
<E> I2Þ I1 ∧ I5 Confidence=2/7=29%
<F> I5Þ I1 ∧ I2 Confidence=2/2=100%
若最小可信度阈值为70%，则输出的关联规则为<B> <C> <F>。
3.3.3 Apriori算法的改进
Apriori算法的缺点
（1）  可能产生大量的候选集。例如，如果有10４个频繁1项集，则Apriori算需要产生10７个候选2项集，并累计和检查它们的频繁性；为发现长度为100的频繁模式，它必须产生多达10３０个候选。
（2） 可能需要重复的扫描数