电子商务智能推荐系统中关联算法设计论文.doc

江苏大学学士学位论文
目 录
目 录 1
摘 要 2
第一章 引 言 4
1.1 电子商务智能推荐系统简介 4
1.2 电子商务智能推荐系统的作用 5
1.3 电子商务智能推荐系统的一般框架图 5
1.4 电子商务智能推荐系统实现的关键技术 7
1.4.1 Bayesian网络(Bayesian Network) 7
1.4.2 关联规则 7
1.4.3 聚类技术 7
1.4.4 Horting图(Horting Graph) 7
1.4.5 协同过滤技术 7
1.5 课题研究内容和意义 7
第二章 开发工具介绍 9
2.1 .NET概述【5】【6】 9
2.2 C#简介 11
2.2.1 C#概述 11
2.2.2 C#的简单数据库访问【5】【7】 13
第三章 关联分析 15
3.1 关联规则概述【3】【4】 15
3.2 关联规则的一般形式 15
3.3 关联规则分类 16
3.4 多层关联挖掘 16
3.5 关联规则挖掘的一般过程 17
3.6 常见的关联规则挖掘算法 18
3.6.1 经典的Apriori方法 18
3.6.2 Apriori方法的变形优化方法 18
3.6.3 不产生候选挖掘频繁项集的FP-Growth算法 19
第四章 多层关联算法的设计与实现 21
4.1 问题描述与分析 21
4.2 数据预处理 23
4.3 算法描述 23
4.3.1 频繁模式树的构造 24
4.3.2 频繁模式增长 25
4.4 运行实例 27
第五章 结束语 30
参考文献 31
致谢 32
附录：部分程序清单 33

摘 要
与传统商业经销方式不同,电子商务交易双方是不谋面的,商家不能直观地了解客户,能获得的只是大量的相关数据(如用户注册信息、历史购买记录等),这样通过对数据的分析来尽可能地揣摩客户,在恰当的时间向恰当的客户推荐恰当的商品或服务就显得尤为重要。电子商务智能推荐系统就是向客户推荐商品或提供信息来引导客户购买什么商品的一种推荐系统。
电子商务智能推荐系统中，常利用数据挖掘技术来对收集到的数据进行分析，建立一定的推荐模型。本文主要讨论电子商务智能推荐系统中，基于关联规则推荐技术的实现。对于许多实际的应用，由于多维数据空间数据的稀疏性，在低层或原始层的数据项之间很难找出强关联规则，因此，需要在较高的概念层发现更具普遍意义的知识，反之，有时需要进一步在较低概念层上挖掘则更为具体和丰富的知识，因而本文主要研究基于概念层次的多层关联挖掘实现。
文中，首先报告电子商务智能的现状，描述实现电子商务智能推荐系统的关键技术，接着着重讨论并实现了基于FP_Tree的多层关联规则挖掘算法，最后做出总结和展望。
关键字：电子商务智能推荐系统 概念层次 多层关联规则 FP-Tree
Abstract
Contrary to the traditional commercial sell fashion, The seller cannot face customer directly, just can get many relative datas(such as user register information, history purchase record),by analyzing the data ,get useful information about user, at the right time remmend the right goods to the right customer is important. The electric business intellective recommendation system is a system that commend goods to customer or offer what to buy about customer.
In the system, usually user data mine technology to analyse the gathered data, establish some commend model. This context mainly discuss the electric business intellective recommendation system, according to the realization of relevance order commend technology .To many practical application, because of the scanty of multi-dimension data ,it is hard to find strong relevance order between the low layer and the primitive layer. Hence, need to find common meaning knowledge in the higher concept layer. Or need mine concrete and abundant knowledge in the lower concept layer. So this context mainly study the realization of multi-layer relevance mine in the concept layer.
First report the present condition of electric business. describe the key technology that realize the electric business intellective recommendation system. Then emphasize discuss and realize mine algorithm of FP_tree multi-layer relevance order. Finally make conclusion and prospect。
Key words: the electric business intellective recommendation system
the concept layer the realization of multi-layer FP-Tree
第一章 引 言
随着企业信息化的不断深化，企业日常业务生成了大量的数据。但是，大部分用户对现有数据除了做一些简单的、局部的和浅层次的查询外，还缺少对这些数据的全面分析。统计资料显示，目前中国企业数据被有效利用的还不足7%。
今天，电子商务让赛场上的选手都回到了同一起跑线。所有的公司、顾客和研究机构在网络经济时代都有着同样的机会。智能驱动型的商务战略将是竞争中获胜的关键，能够把握这个机会的人将成为明天市场的领先者。”全球领先的商务智能（BI）解决方案供应商——Business Objects公司高级副总裁William Gibson日前在为其新产品做市场推广时这样说道。那么，什么是商务智能呢？被称为“法国的比尔·盖茨”的商务智能（BI）大师利奥托德曾作过简单的描述:商务智能是指将存储于各种商业信息系统中的数据转换成有用信息的技术。它允许用户查询和分析数据库，可以得出影响商业活动的关键因素，最终帮助用户做出更好、更合理的决策。
“在今天这样的信息分析时代，我们面对的已经不是缺少信息，我们的问题是如何得到正确的信息以帮助我们制定决策。”利奥托德曾这样评价。那么，商务智能能为我们做么?William Gibson指出，“商务智能带来的是有效的决策，这将使得企业能够增加收入、降低成本并改善顾客满意度。具体来讲，在一个企业，对于销售和营销管理，商务智能可以告诉我们哪些产品带来最大的利润；对于业务管理，商务智能可以直观地反映哪些用户付款不及时；对于财务来说，商务智能可以简单地显示出哪个部门的加权差旅费最高；在人力资源方面，商务智能可以告诉我们哪些因素影响了员工的保有率；在生产方面，商务智能则可以显示出哪些供应商的原料质量最好。而这些还只是商务智能的十分微小的用处。”
电子商务智能推荐系统是商务智能应用的一个具体实例。
1.1 电子商务智能推荐系统简介
根据文献【1】【2】，我们对电子商务智能推荐系统作一个概述。与传统商业经销方式不同,电子商务交易双方是不谋面的,商家不能直观地了解客户,能获得的只是大量的相关数据(如用户注册信息、历史购买记录等),这样通过对数据的分析来尽可能地揣摩客户,在恰当的时间向恰当的客户推荐恰当的商品或服务就显得尤为重要。由于电子商务涉及的数据量大、类型多、模型复杂,以及应用系统的分布性和异构性都使得对这些数据的分析相当困难,而数据挖掘技术恰恰就是从具有上述特征的数据中发现规律,这样把数据挖掘技术应用于推荐系统的开发是很自然的。
推荐系统可以是根据其他客户的信息或是此客户的信息,根据该顾客以往的购买行为预测未来的购买行为,模拟销售人员帮助客户完成购买过程,为客户提供个性化服务。推荐的形式包括向客户推荐商品,提供个性化的商品信息、及其他客户的喜恶等。广义而言,推荐技术使得网站更具个性化(网站会调整某些信息来迎合不同的客户)。
1.2 电子商务智能推荐系统的作用
一般来说，电子商务智能推荐系统具有以下三方面的作用：
1. 将电子商务网站的浏览者转变为购买者(Converting Browsers into Buyers)：有时人们只是看看网站的内容而没有购买的意思。推荐系统可以帮客户找到他们感兴趣的、愿意买的商品。
2. 提高电子商务网站的交叉销售能力(Cross-Sell)：基于用户已经购买的商品,推荐客户购买一些相关的商品。
3. 提高客户对电子商务网站的忠诚度(Building Loyalty)：客户往往愿意到那些最能满足自己需求的网站购物。
1.3 电子商务智能推荐系统的一般框架图
客户购物信息
服务器日志信息
数据预处理
数据库、
数据仓库
数据挖掘
规则(关联、分类聚类等)
筛选
客户模型、档案
商品模型
推荐引擎
Web服务器
客户浏览器
Browing
Similar Item
Email
Text Comments
客户注册信息
离 线 处 理
在 线 处 理

图1-1 电子商务智能推荐系统结构框架图

电子商务智能推荐系统的框架结构图如图1-1所示。总体来看，推荐系统分为离线处理和在线处理两部分。

离线部分
离线部分是客户档案的分析生成过程,利用数据挖掘技术发现客户数据中的规则和模式,为推荐系统做准备。该部分主要包括以下主要功能模块：
1. 数据收集、预处理模块
系统的数据来自不同数据源,包括客户购买信息,个人信息及浏览信息(应用服务器层日志),在进入数据仓库前必须清洗、集成和转换。例如:在这个阶段,可以收集客户对商品的评价(客户对已购物的文字或优劣等级评价)。
2. 数据分析模块
数据分析模块主要是采用数据挖掘的方法对收集到的各类客户数据进行分析，建立客户行为模型,最终形成一定的客户档案。这个阶段是非常耗时,是离线对用户行为进行建模,同时提供ＧＵＩ接口,引入商业决策人员的干预,对所得的知识进行评价,筛选。譬如:通过设定恰当的关联规则置信度和支持度,可以大大减少可提取的规则数目,提高效率和建模的准确度。客户档案包括两部分:一部分是客户的个人信息;一部分是客户的行为模式,按推荐算法的需要,这些模式可以是客户的分类或聚类情况,也可以是一些关联规则。这种模式应该能回答诸如:高消费客户有什么样的特征、客户的喜恶、购买习惯等问题。
在线部分
在线部分主要是根据客户的浏览情况并结合已形成的客户模型和档案，生成及时的推荐。常用的推荐技术包括：
1. 基于内容的推荐
即基于商品信息,根据商品之间的相关性和客户的喜恶来向其推荐。基于属性:推荐主要基于产品的属性特征模型。例如,对在购物车以往记录中或有多张打折ＣＤ的客户就可以向其推荐一些打折ＣＤ。基于商品间的关联性:根据客户感兴趣的产品推荐相关的产品。例如,服装的搭配,商品的系列或配套件。其弊端在于不能为新客户形成合适的推荐,因为客户还没有购物经历,纯基于内容的推荐系统就得不到参考输入。
2. 基于协同过滤的推荐
这种推荐是根据客户与其他已经购买了商品的客户之间的相关性进行推荐,这种相关性是由客户对商品的评价的相似程度来决定的,实际上考虑的是与客户有相似品位的其他客户的作用。例如对于某电影,我可以问朋友的意见,根据与自己兴趣爱好相似的人的意见来决定看不看。同样,纯协同过滤也有弊端,新商品出现时,没有任何客户对其做出评价,系统也就不可能考虑,所以在很长时间内不会被推荐,产生延迟;另外,如果客户没有对某些商品表示过感兴趣,那么系统就决不会提供此类商品,没有开拓能力。
推荐的形式通常分为：Browing：客户提出对特定商品的查询要求，推荐系统根据查询要求返回高质量的推荐；Similar Item：推荐系统根据客户购物篮中的商品和客户可能感兴趣的商品推荐类似的商品；Email：推荐系统通过电子邮件方式通知客户可能感兴趣的商品信息；Text Comments：推荐系统向客户提供其他客户对相应产品的评论信息。
1.4 电子商务智能推荐系统实现的关键技术
1.4.1 Bayesian网络(Bayesian Network)
贝叶斯网络技术利用训练集创建相应的模型,模型用决策树表示,节点和边表示客户信息。模型的建立可以离线进行,一般需要数小时或数天,得到的模型非常小,对模型的使用非常快,这种方法适合客户的兴趣爱好变化比较慢的场合,推荐精度和最近邻技术差不多。
1.4.2 关联规则
关联规则既可用来分析商品间的参考模式,也可以向客户推荐商品,提高交叉销售能力。关联规则的发现可以离线进行,随着商品数目的增加,规则的数量呈指数增加,但通过决策者对支持度和置信度的选择,感兴趣模式以及算法的选取,也可以高效实现。推荐精度比最近邻技术略差。
1.4.3 聚类技术
聚类技术将具有相似爱好、购物兴趣的客户分配到相同的族中,聚类产生之后,根据该族中其他客户对某商品的评价就可以得到系统对该商品的评价,聚类过程可以离线进行,聚类产生之后,性能比较好,但如果某客户处于一个聚类的边缘,则对该客户的推荐精度比较低,推荐精度比最近邻技术略差。
1.4.4 Horting图(Horting Graph)
Horting图技术是一种基于图的方法，节点代表客户，边代表两个客户之间的相似度。在图中寻找近邻节点，然后综合近邻节点的观点形成最后的推荐。Horting图技术可以跳过中间节点寻找最近邻居，考虑了节点之间的传递相似关系。推荐精度优于最近邻技术。
1.4.5 协同过滤技术
协同过滤技术一般采用最近邻技术，利用客户的历史喜好信息计算客户之间的距离，目标客户对特定商品的喜好程度由其最近邻居对商品评价的加权平均值来计算。可以处理客户数据变化比较快的情况。在大型数据库中搜索最近邻居非常耗时，实时性不好。
1.5 课题研究内容和意义
随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。
本文主要研究电子商务智能推荐系统中多层关联规则的设计和实现。对事务数据库中已经收集到的大量数据中进行关联分析，产生关联规则，进而生成电子商务智能推荐系统，向客户推荐商品或提供信息来引导客户购买什么商品。将浏览者转变为购买者。有时人们只是看看网站的内容而没有购买的意思。推荐系统可以帮客户找到他们感兴趣的、愿意买的商品；增加交叉销售。基于用户已经购买的商品,推荐客户购买一些相关的商品；建立忠诚度。客户往往愿意到那些最能满足自己需求的网站购物。
第二章 开发工具介绍
2.1 .NET概述【5】【6】
Microsoft.NET战略基于一组开放的互联网协议，推出了一系列的产品、技术和服务，吹响了一次互联网技术变革的号角。毫无疑问，开发人员处于这个变革的核心。使用微软开发技术的开发者们一直习惯了使用ASP进行Web编程，使VB,VC++进行Win32编程，基于COM/DCOM技术设计自己的应用程序，那么他们在.NET战略中需要面对什么样的挑战，如何利用.NET的开发技术和工具构建下一代的互联网应用呢？
首先，让我们对Microsoft.NET开发框架有一个整体的认识，见图2-1。
从图2-1我们可以简要地了解.NET开发框架的几个组成部分：首先是整个开发框架的基础，即公共语言运行时(Common Language Runtime,CLR)以及它所提供的一组基础类库；在开发技术方面，.NET提供了全新的数据库访问技术ADO.NET,以及网络应用开发技术ASP.NET和Windows编程技术Win Forms；在开发语言方面，.NET提供了VB,VC++,C#,Jscript等多种语言支持；而Visual Studio.NET则是全面支持.NET的开发工具。
VB
C++
C#
JScript
其他语言
通用语言规范(CLS)
ASP.NET
网络
服务
网络
表单

Windows
应用
ADO.NET
基础类库(Base Class Library)
公用语言运行时(CLR)
Visual Studio.NET
操作系统

图 2-1 Microsoft.NET开发框架
Microsoft.NET将把计算和通信带入一个丰富、合作和交互的环境中，远远胜过目前广泛应用的单向网络。由新型高级软件支持的Microsoft.NET将利用一系列的应用程序、服务程序和相关设备来创造一种个性化的数字体验，它能够不断地按照用户的需要自动调整。这意味着用户将能够通过一整套由新型软件开发技术构成的一个整体服务程序来管理自己的生活和工作。
正如微软公司首席执行官鲍尔默所说：“Microsoft.NET代表了一个集合、一个环境、一个可以作为平台支持下一代Internet的可编程结构。”Microsoft.NET的策略是把Internet本身作为构建新一代操作系统的基础，将Internet和操作系统的设计思想合理延伸。这样，开发人员必将创建出摆脱设备硬件束缚的应用程序，以便轻松地连接Internet..NET的运行界面如图2-2所示。

图2-2.NET运行界面
虽然C#是.NET力推的语言，但是开发.NET应用的语言不一定是C#。事实上，Microsoft.NET的程序开发语言核心是公用语言运行环境(Common Language Runtime,CLR)。CLR和Java虚拟机一样，也是一个运行环境，它负责资源管理(内存分配和垃圾收集)，并保证应用和底层操作系统之间必要的分离；不一样的是Java虚拟机仅仅可以运行Java，然而CLR可以运行Visual Basic.NET、Visual C++.NET、Visual C#.NET等几十种语言。为了提高平台的可靠性，并达到面向事务的电子商务应用所要求的稳定性级别，CLR还要负责其他一些任务，比如监视程序的运行。按.NET的说法，在CLR监视之下运行的程序属于“托管的”(Managed)代码，而不在CLR监视之下且直接在裸机上运行的应用或者组件属于“非托管的”(Unmanaged)代码。CLR将监视形形色色的常见编程错误，许多年来这些错误一直是软件故障的主要根源，其中包括访问数组元素越界，访问未分配的内存空间，由于数据体积过大而导致内存溢出等。
CLR语言运行环境由以下几个部分组成：
l 面向对象的编程模式(继承、多态和异常处理等)。
l 统一标准的类型系统。
l 所有类型运行时刻的元数据支持。
l 全面的.NET Framework类，覆盖了绝大多数的Win32 API和其他一些技术，比如：数据库访问、XML解析等。
l 高级的调试、发布支持。
l 托管的代码执行环境和高级内存管理机制。
l 系统范围内的垃圾回收器负责所有托管内存的生命期控制，
l 公开的安全模型。
2.2 C#简介
2.2.1 C#概述
C#是由Microsoft开发的一种新型编程语言，是微软公司为它的Microsoft.NET计划推出的核心编程语言。由于它是从C和C++中派生出来的，因此具有C++的功能。同时，由于是Microsoft公司的产品，它又同VB一样简单。对于Web开发而言，C#像Java，同时具有Delphi的一些优点。Microsoft宣称：C#是开发.NET框架应用程序的最好语言。
C#是一种现代的面向对象语言，它是程序员可以快速便捷地创建基于Microsoft.NET平台的解决方案。这种框架使C#组件可以方便地转化为XML网络服务，从而使任何平台的应用程序都可以通过Internet调用它。C#增加了开发者的效率，同时也致力于消除编程中可能导致严重结果的错误。C#使C/C++程序员可以快速进行网络开发，同时也保持了开发者所需要的强大性和灵活性。
C#不仅继承了Visual Basic、Visual C++语言的特点，还几乎综合了目前所有编程语言的优点，并结合Internet发展的需要，增加了丰富的新特性并增强了功能。C#语言面向实体的设计，可以用来构建服务于高水平的商务目标的组件。C#语言的组成部分使用简单的C#语言结构体，并且能被转换成Web服务，允许人们通过Internet调用在任何操作系统上的运行的任何语言。C#作为一种编程语言，具有以下几个重要的特点：
l 兼容性
l 灵活性
l 简单性
l 现代性
l 面向组件
l 面向对象
l 类型安全
l 可以进行版本控制
1.C#和C++的比较
1) 继承性：一个类只能从一个基础类继承执行。同时，一个类或者界面可以执行多个界面。
2) 数组：声明C#数组的语法不同于在C++中声明数组。令牌“[]”在C#的数组类型后出现。
3) bool类型：在bool类型和其他类型之间不能进行转换(特别是int)。
4) struct类型：在C#中，类和结构体在语义上是不同的。struct是一种值的类型，而class是一种引用类型。
5) switch语句：不同于C++中的switch语句，C#不支持从一种情况标记转换为另一种。
6) delegate类型：delegate类似于C++中的指针功能，但是，delegate是类型安全的。
7) 从派生类中调用被覆盖的基础类成员。
8) 使用new修改器来明确隐藏继承成员。
9) 声明覆盖方法需要override关键字。
10) 预处理程序指令用于条件编译。在C#中没有标题文件。
11) 例外操作：使用finally语句。
12) C#操作符：C#支持附加操作符，如is和typeof。它还引入了一些逻辑操作符的不同功能。
13) 使用extren关键字。
14) 使用static关键字。
15) 用于创建基础类的一种可选C++初始化列表方法。
16) C#程序的通常结构：名字空间、类、结构体、代表和记数。
17) Main方法的声明不同于C++中的main函数。同时，可以比较这两种语言命令行参数值在使用方面的差异。
18) Method参数：C#支持ref和out参数，她们通过引用而在传递参数过程中代替指针。
19) C#中允许使用指针，但是只能在非安全模式下使用。
20) 超载操作符在C#中的执行与在C++中不同。
21) 字符串：C#字符串不同于C++字符串。
2. C#和Java
1) 二者编译成跨平台、跨语言的代码，并且代码只能在一个受控制的环境中运行。
2) 自动回收垃圾内存，并且消除了指针(在C#中可以使用指针，不过必须注明unsafe关键字)。
3) 都不需要头文件，所有的代码都被“包(package)”限制在某个范围内，并且因为没有头文件，所以消除了类定义的循环依赖。
4) 所有的类都是从对象派生出来，并且必须使用New关键字分配内存。
5) 用对象加锁的方式来支持多线程。
6) 都具有接口(interface)的概念
7) 都具有内部类。
8) 继承类的时候不会以某种特定的访问权限来继承。
9) 没有全局函数或者常量，一切必须属于类。
10) 数组或者字符串都自带长度计算和边界检查。
11) 只使用“.”操作符，没有“->”和“::”。
12) null，boolean和bool成了关键字。
13) 任何变量均在使用前进行初始化。
14) 不能使用整数来返回到if条件语句中，必须使用布尔值。
15) try模块后可以有finally。
2.2.2 C#的简单数据库访问【5】【7】
1. .NET数据提供者
数据提供者包含许多针对数据源的组件，这些组件允许我们连接到单独的数据源上,并与之通信。每一个数据提供者都位于System.Data名称空间内自己的名称空间中。
l 用于SQL Server的数据提供者。它位于System.Data.SqlClient名称空间，用于连接到SQL Server 7.0或更高版本以及MSDE数据库(MSDE是SQL Server的减缩版本)。SQL Server提供者作为.NET Framework的一部分安装。如果需要连接到SQL Server6.5或更早的数据库版本，就需要使用OLE DB提供者。
l 用于OLE DB的数据提供者。它用于通过OLE DB连接到数据源，位于System.Data.OleDb名称空间。如同SQL Server提供者一样，它也随.NET Framework安装。OLE DB提供者不用于通过ODBC驱动程序连接到数据库。
l 用于ODBC的数据提供者。ODBC提供者可以用于连接到具有ODBC驱动程序的数据库。ODBC数据提供者的名称空间是System.Data.Odbc。
在C#代码中使用ADO.NET的第一步是引用System.Data名称空间，其中含有所有的ADO.NET类。将下面的using指令放置在使用ADO.NET的程序的开端：
using System.Data
我们使用SQL Server2000，使用SQL Server专用的.NET数据提供者可以获得最好的性能和对基础性的功能的最直接的访问，按如下方式使用using指令可以引用SQL Server专用的.NET数据提供者：
using System.Data.SqlClient
2.读取数据
我们可以通过两种方式来读去数据：
l 使用DataSet
DataSet类似内存中的数据库，包含多个数据表(DataTable)、数据表关联(DataRelation)、限制(Constraint)等相关对象。要使用DataSet来建立数据表、初始化数据表，可以使用DataAdapter对象来达到这个目的。DataAdapter对象提供了Fill方法，可将数据填到DataSet的DataTable中去，并提供将异动的数据更新到数据源的能力。
当从数据库将数据取回放入DataTable后，就可以使用DataView来定义要显示的数据。
l 使用DataReader
使用DataReader的优点是占用少量内存，缺点是其产生的记录集“向前、只读”。
第三章 关联分析
3.1 关联规则概述【3】【4】
考察一些涉及许多物品的事务：事务1 中出现了物品甲，事务2 中出现了物品乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙在事务中的出现相互之间是否有规律可循呢？在数据库的数据挖掘中，关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大的影响。
现实中，这样的例子很多。例如超级市场利用前端收款机收集存储了大量的售货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处理时间，顾客购买的物品、物品的数量及金额等。这些数据中常常隐含形式如下的关联规则：在购买铁锤的顾客当中，有70 ％的人同时购买了铁钉。这些关联规则很有价值，商场管理人员可以根据这些关联规则更好地规划商场，如把铁锤和铁钉这样的商品摆放在一起，能够促进销售。
有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合，但稍微转换一下思考角度，仍然可以像售货数据一样处理。比如人寿保险，一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。通过分析这些数据，可以得到类似以下这样的关联规则：年龄在40 岁以上，工作在A 区的投保人当中，有45 ％的人曾经向保险公司索赔过。在这条规则中，“年龄在40 岁以上”是物品甲，“工作在A 区”是物品乙，“向保险公司索赔过”则是物品丙。可以看出来，A 区可能污染比较严重，环境比较差，导致工作在该区的人健康状况不好，索赔率也相对比较高。
3.2 关联规则的一般形式
设I = {i1，i2，...，im}是一组物品集(一个商场的物品可能有上万种)，D是一组事务集(称之为事务数据库)。D中的每个事务T是一组物品，显然满足TÍI。称事务T支持物品集X，如果XÍT。关联规则是如下形式的一种蕴含:X→Y，其中XÍI，YÍI，且X∩Y= f。
(1) 称物品集X具有大小为s的支持度，如果D中有s%的事务支持物品集X;
(2) 称关联规则X→Y在事务数据库D中具有大小为s的支持度，如果物品集X∪Y的支持度为s;
(3) 称规则X→Y在事务数据库D中具有大小为c的可信度，如果D中支持物品集X的事务中有c%的事务同时也支持物品集Y。
如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷多的关联规则。事实上，人们一般只对满足一定的支持度和可信度的关联规则感兴趣。一般称满足一定要求的(如较大的支持度和可信度)的规则为强规则。因此，为了发现出有意义的关联规则，需要给定两个阈值:最小支持度和最小可信度。前者即用户规定的关联规则必须满足的最小支持度，它表示了一组物品集在统计意义上的需满足的最低程度;后者即用户规定的关联规则必须满足的最小可信度，它反应了关联规则的最低可靠度。
3.3 关联规则分类
对于关联规则，可按不同的情况进行分类：
1. 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。
布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。
例如：性别=“女”=>职业=“秘书” ，是布尔型关联规则；性别=“女”=>avg（收入）=2300，涉及的收入是数值类型，所以是一个数值型关联规则。
2. 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。
在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。
3. 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。
在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。
比如用户购买的物品，用多维数据库的语言就是单维或者叫维内的关联规则，这些规则一般都是在交易数据库中挖掘的。但是对于多维数据库而言，还有一类多维的关联规则。例如：
年龄（X，“20...30”）Ù职业（X,“学生”）==> 购买(X，“笔记本电脑”)
在这里我们就涉及到三个维上的数据：年龄、职业、购买。
根据是否允许同一个维重复出现，可以又细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。
年龄（X，“20...30”）Ù购买(X，“笔记本电脑”) ==> 购买(X，“打印机”)
这个规则就是混合维关联规则。
因为本文主要讨论基于概念分层的多层关联挖掘，因此，以下着重介绍多层关联规则的相关概念。
3.4 多层关联挖掘
多层关联规则是基于概念分层的，首先介绍一下概念分层的概念。
概念分层用来定义一个映射序列，将低层概念映射到更一般的高层概念。概念分层最常用的两种类型是模式分层和集合分组分层。概念分层在模式级上通过定义反映数据库属性之间联系的全序或偏序关系而形成时称为模式分层（schema hierarchy）。例如，属性门牌号、街道、城市、省份、国家形成这样一个模式分层：门牌号街道城市省份国家，并且，沿模式自左向右是泛化（或概化），自右向左是特化。概念分层也可以通过将给定维或属性的值离散化或分组来定义，产生集合分组分层，可以在值组间定义全序或偏序。
对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。当我们引入概念层次后，就可以在较高的层次上进行挖掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。
多层关联规则的分类：根据规则中涉及到的层次，多层关联规则可以分为同层关联规则和层间关联规则。
多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。不过，在支持度设置的问题上有一些要考虑的东西。
同层关联规则可以采用两种支持度策略：
1) 统一的最小支持度。对于不同的层次，都使用同一个最小支持度。这样对于用户和算法实现来说都比较的容易，但是弊端也是显然的。
2) 递减的最小支持度。每个层次都有不同的最小支持度，较低层次的最小支持度相对较小。同时还可以利用上层挖掘得到的信息进行一些过滤的工作。
层间关联规则考虑最小支持度的时候，应该根据较低层次的最小支持度来定。
例如：IBM台式机=>Sony打印机，是一个细节数据上的单层关联规则；台式机=>Sony打印机，是一个较高层次和细节层次之间的多层关联规则。
3.5 关联规则挖掘的一般过程
D

搜索频繁项
生成关联规则
R

图3－1 关联规则挖掘的一般过程
图3－1给出关联规则的一般挖掘过程。从图中可以看出，挖掘的过程有以下两个主要步骤：
⒈ 找出事务数据库中的频繁项集；当项目集的支持度（包含项集的事务占整个事务数据库D的百分比）大于用户设定的最小支持度minsup时，我们称这样的项目集为频繁项目集。
⒉ 利用频繁项目集生成强关联规则。其一般思想是：对每一个频繁项目集l，找到l的所有非空子集s，对于每个s，如果support(l)/support(s)minconf，则规则成立。
在以上两步中，发现和识别频繁项目集是核心步骤，它决定了挖掘关联规则的总体性能。
3.