数据挖掘课程实验指导
董春玲
实验课程名称: 数据挖掘技术 英 文 名 称: the Techniques of Data Mining 课 程 编 号: 4144316 学院、专业、年级: 人口˙资源与环境学院 地理信息系统专业 教师所在单位: 人口˙资源与环境学院
山东师范大学实验教学指导
内容概要
一、SQL Server 2000 Analysis Services体系结构 二、SQL Server Analysis Serivices数据挖掘方法
1. 微软决策树的基本概念 2. 微软决策树的挖掘参数 3. 微软聚类算法
三、零售业数据挖掘系统的设计
1. 零售业(超市)的数据挖掘需求分析 2. 数据挖掘流程
3.零售行业的数据挖掘系统设计 4. 数据挖掘模型设计 5.数据仓库设计
四、数据挖掘模型的建构
1. 创建和连接数据库 2. 建立多维数据集(立方体)
主要内容:在建立多维数据集的基础上,分别完成基于数据仓库(OLAP多维数据集)、关系属据库,以及分别基于微软决策树、微软聚类算法的数据挖掘模型。零售行业可以通过浏览多维数据集或者通过挖掘模型了解销售等信息,从而作出正确决策。
五、Microsoft 决策树数据挖掘模型的应用 六、Microsoft 聚类OLAP 数据挖掘模型的应用 七、客户端程序查询OLAP实现多维分析
附:决策树数据挖掘实验过程指导与分析
八、数据挖掘算法实验内容
1.关联规则算法实验 2.决策树程序实验
2
山东师范大学实验教学指导
目 录
一、SQL Server 2000 Analysis Services体系结构 ............................................................................... 4
1. Analysis Services 概述 .............................................................................................................. 4 2. Analysis Services中的数据挖掘服务 .................................................................................... 5 3. 客户机结构体系结构................................................................................................................ 6 4. PivotTable Service ................................................................................................................... 6 5. 决策支持对象DSO .................................................................................................................. 6 6. 多维表达式MDX ..................................................................................................................... 6 二、SQL Server Analysis Serivices数据挖掘方法 ............................................................................... 7
1. 微软决策树的基本概念............................................................................................................ 7 2. 微软决策树的挖掘参数............................................................................................................ 8 3. 微软聚类.................................................................................................................................. 9 三、零售业数据挖掘系统的设计 ...................................................................................................... 10
1. 零售业(超市)的数据挖掘需求分析.................................................................................. 10 2. 数据挖掘流程.......................................................................................................................... 12 3.零售行业的数据挖掘系统设计............................................................................................. 12 4. 数据挖掘模型设计................................................................................................................ 14 5.数据仓库设计......................................................................................................................... 15 四、数据挖掘模型的建构 .................................................................................................................. 16
1. 创建和连接数据库.................................................................................................................. 16 2. 建立多维数据集(立方体).................................................................................................. 17 五、Microsoft 决策树数据挖掘模型的应用 ..................................................................................... 30 六、Microsoft 聚类OLAP 数据挖掘模型的应用 ........................................................................... 34 七、客户端程序查询OLAP实现多维分析 ...................................................................................... 38 八、数据挖掘算法实验内容 .............................................................................................................. 44
1.关联规则算法实验................................................................................................................. 44 2.决策树程序实验..................................................................................................................... 47
3
山东师范大学实验教学指导
一、SQL Server 2000 Analysis Services体系结构
1. Analysis Services 概述
Microsoft SQL Server 2000 Analysis Services 包含联机分析处理 (OLAP) 和数据挖掘。Microsoft® SQL Server™ 2000 扩展并重命名了以前的 OLAP 服务组件,该组件现在称为 Analysis Services。在 SQL Server 7.0 版中引入的 OLAP 服务深受好评,而许多新的和增强的功能又极大地改进了此服务的分析能力。在此版本中,Analysis Services 引入了数据挖掘,这可以用于在 OLAP 多维数据集和关系数据库中发现信息。
Microsoft® SQL Server™ 2000 Analysis Services扩展了 OLAP 多维数据集的可伸缩性和功能。可以在多台服务器间分散多维数据集以提供更大的存储容量,创建链接的多维数据集以便在不复制多维数据集数据的情况下分散最终用户对信息的访问,创建在数据更改时实时更新的多维数据集,以及使用很多其它新特性创建可满足特定业务需要的多维数据集。
4
山东师范大学实验教学指导
2. Analysis Services中的数据挖掘服务
微软管理控制台自定义Add-inAnalysis Add-inManager用户应用程序EnterpriseManager(DTS)Analysis Manager元数据库对象模型(决策支持对象)数据源Analysis Server立方Pivot Table Service体挖掘模型客户端应用程序5
山东师范大学实验教学指导
3. 客户机结构体系结构
用于OLAP或数据挖掘的客户端应用程序Analysis Server用于OLAP的客户端应用程序扩展支持OLAP和数据挖掘的OLE DB2。5或者更新版本PivotTable Service扩展支持OLAP的OLEDB2。5或者更新版本扩展支持OLAP的ASO2。0或者更高版本本地数据挖掘模型扩展支持OLAP的ADO2。0或者更高版本立方体用于OLAP或数据挖掘的客户端应用程序用于本的数据挖掘模型的数据源用于本的立方体的数据源用于OLAP客户端应用程序 4. PivotTable Service
PivotTable Service(数据透视表服务)内置于Analysis 服务器客户机,它的作用相
当于一个多维数据集和数据挖掘操作的OLE DB提供者。它被置于服务器引擎和其他客户应用程序之间。这样,它提供了访问应用程序的OLE DB,这些应用程序需要从客户机应用程序访问多维数据和数据挖掘服务。返回的数据形式一般是表格数据,通过使用ADO记录集、Excel电子表格或FoxPro表,这些数据可以用传统方式来操纵。在数据挖掘服务和OLAP中,PivotTable Service都提供一个使用数据定义语言(DDL)的扩展SQL语法,该语言是一种允许客户快速创建于更新本地立方体或数据挖掘模型的语言。
5. 决策支持对象DSO
DSO用于按编好的程序完成管理任务,这些任务原本需要在Analysis Manager中交互
执行。整个类似于Analysis Manager的前端应用程序可以由任何懂DSO的人来编写,并能使用VB,VC++实例化COM对象。DSO还允许使用批处理来执行事务和愉悦的管理任务,例如更新立方体或者在一个数据挖掘模型中添加新的实例。
6. 多维表达式MDX
由于OLAP立方体的独特结构,SQL SERVER语言中有一个特殊子集称为多维表达式
6
山东师范大学实验教学指导
(Multidimensional expressions,MDX)专为立方体的查询而设计。尽管该查询的语法类似于标准的SQL语句,但试图进行一个任意复杂程度的查询时,其不同之处变得显而易见。可以使用这种特定的语言来表达你的查询要求,直接得到需要的数据。
二、SQL Server Analysis Serivices数据挖掘方法
1. 微软决策树的基本概念
Microsoft® 决策树算法是基于分类概念的。算法构造树,此树将基于训练集中的剩余
列预测列值。因此,树中的每个结点代表一列的特定事例。将此结点放在何处的决策由算法作出,而且与其兄弟在不同深度的结点可能代表每列不同的事例。例如下列训练数据表:
共享文件 是 是 否 是 是 否 是 使用扫描程序 是 否 否 是 是 是 否 以前曾感染病毒 否 否 是 是 否 否 是 危险度 高 高 中 低 高 低 高 对于这些训练数据,可以生成如下的决策树。
7
山东师范大学实验教学指导
需要注意:对于共享文件的用户,确定他们计算机感染病毒的危险度的最重要因素(即训练列)为是否\"以前感染过\"。对于不共享文件的用户,最重要的因素是\"使用扫描程序\"。这显示了有关决策树算法的一个关键概念:一列可用在树中多个位置,其在预测中的重要性可能因此而改变。 2. 微软决策树的挖掘参数
Microsoft 决策树算法提供程序当前支持两个挖掘参数,当用 CREATE MINING MODEL 命令创建模型时,可用这些参数更改算法的行为。参数在 MINING_PARAMETERS 架构行集中定义,下表提供了每个参数的描述。
参数 COMPLEXITY_PENALTY 描述 范围在 0 和 1 之间的浮点数。用来抑制决策树的增长,该值从 1 中减去,而且用作确定拆分可能性的一个因子。决策树的分支越深,实现拆分的可能性越小。该挖掘参数的作用取决于挖掘模型本身;可能需要做些实验和观察以精确调整数据挖掘模型。 8
山东师范大学实验教学指导
默认值基于给定模型的特性数: 对于 1 到 9 个特性,该值为 0.5。 对于 10 到 99 个特性,该值为 0.9。 对于 100 或更多个特性,该值为 0.99。 MINIMUM_LEAF_CASES 范围为 0 到 2,147,483,647 之间的非负整数。确定在决策树中生成拆分所需的叶事例的最少数量。小的值将在决策树中引起较多拆分,但增加过度臃肿的可能性。大的值减少决策树中拆分的数量,但可抑制决策树的增长。 默认值为 10。 3. 微软聚类 Microsoft 聚类算法是一种期望方法,它使用迭代完善技术将记录分组到附近区域(聚
类),以展示相似、可预测的特征。通常,这些特性可能是隐藏的或者非直观的。
例如,假定一个旅游公司希望确定人口年龄组成以推销整套度假服务。他们的数据仓库里有下列训练数据:
顾客年龄 23 45 32 47 46 34 51 28 49 29 旅游过的国家/地区 墨西哥 加拿大 加拿大 加拿大 加拿大 加拿大 加拿大 墨西哥 加拿大 墨西哥 9
山东师范大学实验教学指导
26 31
墨西哥 加拿大 绘制二维图形时,可以看到数据中有三个主要的分组:年龄在 23 和 29 岁之间的人大都去墨西哥。年龄在 30 到 51 之间的人大都去加拿大。聚类算法也显示了一个有趣的事实,但直接观察数据不易发觉:35 到 44 岁年龄段的人可能根本不旅行。换一种说法:去加拿大旅游的人员可分为两个主要聚类:年龄在 30 和 34 岁之间的人和年龄在 45 到 51 之间的人。
本示例中的数据聚类很容易观察到。对于更高维度的数据,使用该方式编制数据可能不方便,或者维度根本不容易编制。聚类算法将自动查找更高维度的数据分组。
Microsoft 聚类算法提供程序当前不支持任何附加挖掘参数。
三、零售业数据挖掘系统的设计
1. 零售业(超市)的数据挖掘需求分析
POS机(checkout scanner)最初用途是纯粹的基于操作上的方便,它的优点是可以
集中设置价格,价格改变时,不用对货架上每个商品进行修改。但是,客户对不明确标价的商品一般不买,所以最初集中设置价格的方便没有实现。然而,在增加付帐速度、精确定价、库存控制方面起到很大的作用。
POS机另外一个重要的作用,开始没有被注意到,那就是产生了大量的数据 GB/TB。面对这些数据,上万条记录的现金收据,记录着上万条各种销售记录。而现在,需要从这数据里知道诸如:上星期店中最受欢迎的商品是什么?最不受欢迎的产品是什么?超市的媒体宣传对刺激顾客的购买欲望是否有效果?媒体宣传对什么样的顾客最优效果?通过
10
山东师范大学实验教学指导
会员卡分析将顾客按照不同的购买模式分类,怎样才能找出最佳顾客?超市数据库中的所有信息足够很好地回答这些问题,但是怎样从这些海量的数据中发现能够解答问题的有用信息?
(1)信息中介
零售业刚开始明白他们收集信息的真正价值,这可以参照其他行业,比如信用卡行业。信用卡行业与零售业类似,它们收集了客户购买商品的信息,这些信息可以以其他形式卖给需要针对单个客户进行市场定位的公司。
超市收集的数据使得零售商有机会改变和品牌供应商之间的能力平衡。POS系统所收集的数据能够回答供应商(如P&G保洁, Coca Cola可口可乐, Pesi百事等)一个问题,这个问题是供应商非常希望得到回答的:谁在购买这种品牌的商品? “谁正在买什么?”这种知识使得零售商有能力成为信息中介商。
超市可以采用两种不同的方式从事信息中介,一种方式是针对匿名客户,另一种是针对注册或有忠诚卡的客户。对第一种,超市可以编写一段优待券打印程序,当一个客户购买某种商品时,打印与该商品有关商品的优待券(关联规则)。但是,一般而言,客户在购买了某种商品后,不会在很短的时间内购买相关商品。对于有忠诚卡的客户,可以分析他的购买历史,向他发放下次可能会购买的商品的优待券(序列模式)。
(2)重心从商品转换到客户
目前,超市从匿名客户,开始支持会员卡(忠诚卡)客户,即原来的POS程序记录的是匿名交易数据,现在可以记录有卡的客户的信息。如果没有客户的信息,超市将不能回答许多实际的问题。
超市发卡记录客户的行为,最初并不是用来进行数据挖掘的。传统的做法是基于统计的:对于每月花费超过400$的客户,超市提供一次免费的聚餐等。这种方法有一个缺陷,主要是不针对客户,只针对在超市固定的花费。对于客户的月花费存在三种类型,一类客户不管超市如何促销,他们的花费都不会超过400$;第二类是日常月花费总超过400$,对于这一类客户,免费的聚餐不会构成吸引;最后一类客户,是确实因为此类促销活动,使得花费超过了400$。最后一类客户才是这种策略的真正目的。解决方案是给每一个客户不同的花费目标,这一点统计不能作到,需要使用数据挖掘的技术。数据挖掘技术可以对每个客户在花费的价格和购买的商品上,度身定做相应的促销手段。例如,可以给客户免费赠送某个商品,这种商品他过去没有购买过,但是通过数据挖掘,知道他应该喜欢。
(3)零售行业的其他需求
提高客户满意度和客户保有率。实行两个方法以达到这些目标:对会员卡方案重新进
11
山东师范大学实验教学指导
行定义,以便更好地为客户提供服务并且使所提供的服务能够更加密切地满足客户的期望;创办导购杂志,将杂志送给客户群,以鼓励他们访问商店。
重新定义会员卡方案。市场部想分析当前销售事务并找出客户人口统计信息(婚姻状
况、年收入、在家子女数等)和所申请卡之间的模式。然后根据这些信息和申请会员卡的客户的特征重新定义会员卡。
定义导购杂志。市场部想将客户群划分为三个类别。事实上,市场部已有创建三个版
本的导购杂志的财政预算。市场部想对销售数据运行一些数据挖掘进程,以便识别三个组中的客户。根据三个组的特征,市场部可以选择赠券的类型,以便插入各个版本的导购杂志。市场部还将能够知道哪一类客户应该接收哪一个版本的杂志。 分析媒体宣传对于促销是否能达到预期的目的,以及什么样的顾客(教育程度、婚姻
状况、年收入、在家子女数等等)易于被媒体宣传刺激消费。
按照顾客的消费水平及购买模式分类。希望知道综合各种因素什么样的顾客在消费模
式上可分为一类。
2. 数据挖掘流程
数据挖掘流程如下图所示。
分析问题数据提取和清洗数据数据数据数据仓库创建和训练模型校验数据DLAP数据挖掘模型维护数据挖掘查询数据 3.零售行业的数据挖掘系统设计
(1)建立数据仓库
12
山东师范大学实验教学指导
1)源数据:源数据是指零售行业中各业务系统的数据和外部数据源的数据。其中业务系统包括销售系统、营业系统、进货系统、仓储系统、客户服务系统、员工管理系统等,外部数据源包括文本文件以及二进制文件等的数据。
2)数据抽取模块:数据抽取模块将原有业务系统数据库和外部数据源的数据按照数据仓库模型整合到数据仓库中去,在此过程中完成数据的导出、清晰、转换、整合、传输、加载等操作,是零售行业(超市)中决策支持系统中最为复杂的一个环节。 在数据抽取模块中主要完成以下任务:
确定抽取的数据源,主要从超市的销售系统、营业系统、仓储系统等业务系统中取得;
导出业务数据,并对数据进行压缩操作,放入临时数据库中;
对临时数据库中的数据进行清洗,合并来自不同的数据源的信息,将代码转换为完整的有实际意义的描述(定义维),并提供接口以保证抽取的整体事务性; 确定数据加载的目标数据仓库;
对数据进行加载、并确定加载的类型,批量加载或者增量更新等等,并提供安全及权限管理、元数据管理、日志记录管理。
3) 数据仓库模块
基础数据仓库:数据仓库中的数据结构按照决策支持的需求而设计成星形结构,
在设计中兼顾了系统未来发展变化和数据查询、访问的效率,在抽取的过程中,对数据进行了完整性和有效性检查,对冗余和不一致的数据进行了清洗和转换。 数据集市:数据集市是数据仓库的子集,通常是在基础数据仓库的基础上,根据
用户前端分析需求,将详尽数据聚合为汇总数据放在称为“数据集市”的数据库中,该数据库的信息在各个不同的前端决策支持工具(如微软分析服务中的DSO,Brio Enterprise)和其他业务系统中应用。 4) 应用平台
一般情况下,决策支持系统的应用平台后端连接数据仓库模块,前端使用开发工具将数据下载到本地结果集,从而进一步展示分析结果。前端分析界面的结构根据用户的要求,及数据仓库的面向主题的特征分为查询分析、主题分析、统计报表分析、客户分析、收益分析、销售单分析、销售量分析几个模块。每个模块下又具体的分析应用程序,以提供决策着不同的决策要求。
当数据量比较大,采用上述将数据下载到结果集的方式,联机分析的速度会很慢。为了提高分析速度,应用平台后端可以连接微软SQL Server服务器。此种方法的实现
13
山东师范大学实验教学指导
时将数据仓库模块中的数据转存入以多维数组组织的多维数据库中,数据以立方体(多维数据集)结构进行存储。结合关系数据库中的表结构就比较容易理解这两种多位立方体结构,它的每一个维度通常对应于数据库表中的一个字段,经常使用的纬度有时间、单位、商品类别、币种、费用等。
每个维度存若干成员,成员下面可以有子成员。维度和成员的树型结构构成了多维立方体的框架,即多维数据库的概要文件,相当于关系数据库的模型设计。
个性化分析灵活查询报表生成发布领导辅助决策WEG服务器SQL SERVERANALYSIS SERVICES前端分析工具SQL SERVEROLAP SERVER数据挖掘分析数据仓库数据集市数据抽取模块源数据源数据源数据源数据
4. 数据挖掘模型设计
OLAP数据挖掘模型的主要建构模式:
(1)先建立立方体,然后挖掘:由于建立了数据立方体,就可以在立方体的任何层次和任何部分进行数据挖掘。这就意味着在进行数据挖掘之前,必须首先选取数据和划分逻辑层次(粒度级)。例如,可以首先剪裁一个立方体,使之具有合适的大小,如“year=2004”,
14
山东师范大学实验教学指导
然后选择一个合适的层次,如商品的category(种类)层次,最后执行一个预测模型。
(2)先挖掘,然后新建立方体:即指首先对立方体进行数据挖掘,然后将获得的挖掘结果集建成一个新的立方体,以便进一步的分析。
(3)建立立方体与挖掘同时进行:结合挖掘操作和建立立方体操作的一个灵活的方式是,在立方体的多个粒度级上实施类似的挖掘,并在挖掘过程中不断调整立方体。这样,同样的挖掘就可以在立方体的的多个和不同层次上进行。
(4)挖掘回滚:为了便于交互式挖掘,应该允许一个挖掘进程返回一步或者多步到曾经处理过的数据集,以便实施其他方式的挖掘方案。
(5)比较挖掘:灵活的挖掘工具允许比较数据的挖掘,及不同的数据挖掘进程之间的比较。例如,一个数据挖掘工具可能包括许多簇分析方法,要比较这些分簇方法的质量差异,甚至在新建立方体的过程(下钻到细节层)中对它们进行比较。
5.数据仓库设计
数据挖掘模型基于的数据仓库存储模式为雪花模式(Snow Flake Schema),表间关系如下:
15
山东师范大学实验教学指导
在实际应用中,观察数据的角度是多层次的,即数据的维往往不仅仅只是一个维层次。对于维内层次复杂的维,用以一张维度表来描述会带来过多的冗余数据。为了避免冗余数据占用过大的空间,在数据仓库存储结构设计时,采用多张表来表示一个复杂维。这样就从常见的“星型模型”转变为“雪片模型”。在这种模式中,维度表存储了正规化的数据。这种结构通过减少磁盘读的数量而提高查询性能。维度表分解成与事实表直接相关量的主维表和与主维表相关联的次维度表,次维度表与事实表间接相关联。
四、数据挖掘模型的建构
1. 创建和连接数据库
(1)启动Analysis Manager,展开左边的树装视图,为将要安装的数据库选择一个
服务器。
(2)选择新建数据库后,输入数据库名称(FoodMart)和描述信息(可选)。
16
山东师范大学实验教学指导
(3)确定后即创建一个新的数据库。 (4)设置数据源:
A.在Analysis Manager树装视图中展开foodMart数据库,显示其子结点。 B.右键选择设置数据源,选择新建数据源。从而打开数据连接属性对话框。 C.设置OLE DB数据源(可在需要的情况下输入用户名和口令)。
D.确定后即完成设置,foodMart数据库及作为Analysis Services数据库的数据源。
2. 建立多维数据集(立方体)
(1)Analysis Service企业解决方案,可以将初始的产品数据库转化为一个适用于
多维分析的OLAP多维数据集。结构如下图所示:
商业用户Office 2000ProClarityCognos PowerPlayHungry DogIntelliBrowser分析平台多维数据集多维数据集多维数据集多维数据集数据中心生产数据SQL ServerAccessDB2Oracle (2)建立多维数据集
建立多维数据集有两种方法:一种是使用多维数据集向导(Cube Wizard),另一种是直接使用多维数据集编辑器(Cube Editor)。前者可以很方便的创建新的多维数据集,后者可以直接修改现有的多维数据集。下面给出使用向导创建多维数据集的步骤:
A.欢迎画面后,从数据源中选择事实表:sales_fact_1998
17
山东师范大学实验教学指导
B.选定用来定义度量的数据列:该面板中显示了事实表中所有数字类型的列。在此选择unit _sales
C. 创建维度和级别
选定Customers,Education Level,Promotion Media作为多维数据集的维度。
18
山东师范大学实验教学指导
D. 输入多维数据集名称,完成立方体的建立。
E.建立完成后即可在编辑器中看到多维数据集涉及到的维表和事实表关系。
19
山东师范大学实验教学指导
F.在处理多维数据集之前首先要选择存储模式:
G.选择聚合选项后,系统将自动提前计算聚合。这样就能在一定程度上快速完成查询。
20
山东师范大学实验教学指导
H.处理多维数据集:
I.浏览多维数据集:
建立并处理好多维数据集后,用户即可使用其中的数据,通过自由操作维度和度量的部分,用户可以在此基础上作出基本的数据分析和决策。
21
山东师范大学实验教学指导
J.为了能让用户更方便浏览数据,同时降低对客户端的要求,可使用OWC(Office 2000 Web Component) 组件,使得用户可以直接由浏览器查看多维数据集数据。
22
山东师范大学实验教学指导
(3) 以关系数据为基础建立挖掘模型
1)选择事例表
23
山东师范大学实验教学指导
选定customer,product,product_class,sale_fact_1998四张表作为事例表,期望可以从这四张表中挖掘到顾客购买模式的规则。
2) 选择微软聚类挖掘技术创建挖掘模型
3)在各维度表之间确认关联,确保维表的关联。 在此添加Product和product_class之间的对应关系。
24
山东师范大学实验教学指导
4)在“选择输入与可预测列”步骤中,选择以下列,然后用“>”按钮依次移动到“可预测列”框中:
5)在最后的步骤中,在“模型名称”框中输入“Advanced customer patterns discovery”。确保选择了“保存并立即处理”。单击“完成”按钮。
25
山东师范大学实验教学指导
(4) 以多维数据集为基础建立挖掘模型:
1)使用 Microsoft 决策树创建 OLAP 数据挖掘模型
A.打开挖掘模型向导。在“选择数据挖掘技术”步骤中的“技术”框中选择“Microsoft 决策树”。
B.在“选择事例”步骤中,在“维度”框中选择“Customer”。在“级别”框中,确保选择了“Lname”。
26
山东师范大学实验教学指导
C.在“选择被预测实体”步骤中,选择“事例级别的成员属性”。然后在“成员属性”框中选择“Member Card”。
D.
在“选择训练数据”步骤中,滚动到“Customer”维度,清除“Country”、
“State\Province”和“City”框(因为不需要在聚类级别上而只需要在单独的客户级别上确定客户模式)。在“创建维度和虚拟多维数据集(可选)”步骤中,在“维度
27
山东师范大学实验教学指导
名称”框中输入“Customer Patterns”。然后在“虚拟多维数据集名称”框中输入“Trained Cube”。在最后的步骤中,在“模型名称”字段中键入“Customer patterns discovery”。确保选择了“保存并开始处理”。单击“完成”按钮。
(5) 使用微软聚类创建 OLAP 数据挖掘模型
A.在挖掘模型向导的“选择数据挖掘技术”步骤中,在“技术”框中单击“Microsoft 聚类”。单击“下一步”按钮。
28
山东师范大学实验教学指导
B.在“选择事例”步骤中的“维度”框中,选择“Customer”。在“级别”框中,确保已经选择了“Lname”
C.在“选择训练数据”步聚中,在“Customer”维度中清除“Country”、“State Province”和“City”复选框,因为没有必要使用汇总级别划分客户群。然后,在“Measures”维度中只选择“Store Sales”。单击“下一步”按钮。在最后一个步骤中,
29
山东师范大学实验教学指导
在“模型名称”框中输入“Customer segmentation”。选择“保存,但现在不处理”。单击“完成”按钮。
以上,在建立多维数据集的基础上,分别完成基于数据仓库(OLAP多维数据集)、关系数据库,以及基于微软决策树、微软聚类的数据挖掘模型。零售行业可以通过浏览多维数据集或者通过挖掘模型了解销售等信息,从而作出正确决策。
五、Microsoft 决策树数据挖掘模型的应用
使用OLAP 挖掘模型编辑器编辑模型属性或者浏览其结果。决策树显示于右窗体中。其中包括以下窗体:
中间的“内容详情”窗体显示焦点所在的决策树的部分。
“内容选择区”窗体显示树的完整视图。该窗体可以将焦点设置到树的其它部
分。
“特性”窗体中,特性信息可以用“合计”选项卡以数值方式查看或者用“直
方图”选项卡以图形方式查看。
“结点路径”区域显示与焦点所在结点相关联的路径。
30
山东师范大学实验教学指导
(1)内容详情窗体
在“内容详情”窗体的决策树区域中,颜色代表“事例”的密度(在本事例中为:客户的密度)。颜色越深则结点中包含的事例就越多。 单击“全部”结点。该结点为黑色,因为它代表 (7632) 事例的 100%。7632 代表 1998 年活动的客户数目(即 Sales 多维数据集中有事务记录的客户)。这个数字也说明在 1998 年并非所有的客户都是活动的,因为从“Customer(消费者)”维度的“Lname”级别中所包含的 9991 个客户中只得到 7632 个事例。
(2)特性窗体
显示“全部”结点中,所有事例的 55.83%(或者说 4263 个示例)可能选择铜卡 (Bronze);11.50% 可能选择金卡 (Golden);23.32% 可能选择普通卡 (Normal);9.34% 可能选择银卡 (Silver)。如果没有显示百分比,则可以调整“特性”窗体中“合计”面板的“可能性”列的大小。
(3)如果选择了树的不同结点,此百分比将会更改。让调查一下哪些客户可能选择金卡。若要执行此操作,则需要重新画出树以便勾画出金卡的高密度区。在右下角的“树颜色基于”字段中选择“Golden”。该树显示另一种颜色模式。可以看出“Customer.Lname.Yearly Income = $150K+”结点的密度高于其它任何结点。
31
山东师范大学实验教学指导
(3)树的第一个级别由“yearly income(年收入)”属性决定。树的组织由算法决定,其基础是该属性在输出中的重要性。这意味着“yearly income”属性是最重要的因素,它将决定客户可能选择的会员卡的类型。选择“Customer.Lname.Yearly Income = $150K+”结点。该特性窗体显示收入较多的客户中,45.09% 的客户可能会选择金卡。这个百分比要比“全部”结点中的 (11.50%) 高得多。当继续在树中做进一步调查时,让调查一下这些百分比是如何演化的。双击“Customer.Lname.Yearly Income = $150K+”结点。 该树现在只显示“Customer.Lname.Yearly Income = $150K+”结点下的子树。选择“Customer.Lname.Marital Status = M”结点。在“结点路径”窗体中,可以看到包含于该结点的客户的完整的特征定义:收入高于 150000 美元且已婚的客户。该“特性”窗体现在显示:与上一级别 (45.09%) 相比,较高百分比 (81.05%) 的客户可能会选择金卡。
32
山东师范大学实验教学指导
(4)再返回到顶层,进行一种与此不同的调查,即调查可能选择普通卡的客户。若要返回顶层结点,可以单击从“Customer.Lname.Yearly Income = $150K+”结点左面伸出来的线(方法 1)或者使用“内容选择区”回到树的顶部(方法 2)。在“树颜色基于”字段中选择“Normal”。树刷新结点的颜色之后,可以看到“Customer.Lname.Yearly Income = $150K+”结点的颜色非常浅;这意味着这些客户选择普通卡的可能性非常小。另一方面,可以看到“Customer.Lname.Yearly Income = $10K $30K”结点的颜色非常深。这意味着这些客户选择普通卡的可能性非常高。“特性”窗体显示在此年收入范围内的客户中,91.92% 的客户可能会选择普通卡。树还显示已无法对此结点进行进一步调查。这意味着在树的这个分支中,年收入是决定客户选择普通卡的可能性的唯一因素。
33
山东师范大学实验教学指导
可以查看树的其它分支并调查客户选择一种卡而不选择另一种卡的可能性。市场部可以使用此信息来确定最可能选择某种类型卡的客户的特征。根据这些特征(收入、子女数、婚姻状况等等),可以重新定义会员卡服务和方案以便更好地适应其客户。
六、Microsoft 聚类OLAP 数据挖掘模型的应用
此模型将使用“Microsoft 聚类”算法将客户群划分为三个类别。请将客户设置为要调查的维度(事例维度)。然后将 Store Sales(商店销售)度量值设置为数据挖掘算法划分 Customer(消费者)维度所用信息。接下来,请选择想要在算法中表示各个客户类别特性的人口统计特征列表:婚姻状况、年收入、在家子女数、教育程度„„ ,然后训练此模型,最终使其能够浏览受训数据并从中分析三种客户类别。市场部将根据每个客户类别的人口统计属性,选择将要插入导购杂志各个版本中的赠券列表。
在建立挖掘模型的基础上,首先要读取包含在各个聚类(客户段)中的信息。 (1)打开OLAP 挖掘模型编辑器。分段树显示于右窗体中。右窗体由四个窗体组成:中间的“内容详情”窗体 (1) 显示焦点所在的分段树的部分。“内容选择区”窗体 (2) 显示树的完整视图。该窗体使您可以将焦点设置到树的其它部分。其它的两个窗体分别是“特性”窗体 (3)(特性信息可以用“合计”选项卡以数值方式查看或者用“直方图”选项卡以图形方式查看)和与焦点所在结点相关联的“结点路径”区域 (4)。
34
山东师范大学实验教学指导
(2)在“内容详情”窗体中,在分段树区域中,颜色代表事例的密度(在此事例中为客户的密度)。颜色越深则结点中包含的事例就越多。单击“全部”结点。该结点为黑色,因为它代表 100% 的事例(客户)。
(3)单击“Cluster 1”。特性窗体显示一个下拉列表和一个网格。下拉列表可用于选择特定的客户人口统计特征。网格显示以人口统计特征的各个值为基础对聚类中客户的重新分区。
(4)对于“Cluster 1”,请选择“结点特性集”框中的“Customer.Lname.Marital Status”,然后转到“特性”网格。网格显示“Cluster 1”包括 2878 个事例,对于“婚姻状况”特征,事例分布如下:21.12% 的客户已婚,其余 78.88% 单身。
35
山东师范大学实验教学指导
(5)让从另一个角度查看这些相同的 2878 个事例。在“结点特性集”框中,选择“Customer.Lname.Yearly Income”。网格中的分布显示 0% 的客户收入在 10000-30000 美元范围之内;41.62% 的客户收入在 30000-50000 美元范围之内;24.01% 的客户收入在 50000-70000 美元范围之内。结果显示该聚类的 65% 以上的客户在中等收入(年收入为 30000-70000 美元)范围之内。
36
山东师范大学实验教学指导
(6)现在可以知道“Cluster 1”主要由中等收入的客户构成而且主要由单身客户构成。在列表中选择“Customer.Lname.Num Children At Home”。结果显示该聚类中平均在家子女数为零。此项选择显示一个平均数而不是重新分区,因为源数据库的“Num of Children at Home”字段中包含连续的值。当算法发现源数据中包含不连续的值,它将显示包含这些值的重新分区。 当算法发现源数据中包含连续的值(即非预定义数字),它将计算并显示平均值。
37
山东师范大学实验教学指导
(7)在“结点特性集”框中,选择“Measures.Stores Sales”。网格显示在“Cluster 1”中对每个客户的平均销售额为 72.42 美元。
(8)市场部现在了解到“Cluster 1”主要由中等收入的客户构成,而且完全是由单身客户构成,这些客户家中没有子女,每年在 FoodMart 商店平均花费 72.42 美元。根据这种情况,市场部可以确定在周刊中插入哪种赠券了。您也可以在树中浏览以确定在“Cluster 2”和“Cluster 3”中所包含客户特征。
七、客户端程序查询OLAP实现多维分析
以上分析,已经解决了零售行业经理需要解决的大部分问题,零售行业经理还可以通过支持复杂查询的客户端程序查询OLAP来实现全面的决策支持。
38
山东师范大学实验教学指导
Analysis Service具有一个针对OLAP的OLE DB的开放标准,它可以用来查询数据库。OLAP的OLE DB建立在OLE DB技术基础上,它提供了一个与数据中心数据库的标准接口,是一种可以用来执行查询检索并以多维数据格式返回结果的产品,OLAP Services 1.0可以和市场上很多第三方客户端软件配合使用,这些软件给提供了丰富的可视化多维数据集操作工具。例如,ProClarity,Cognos PowerPlay和Hungry Dog IntelliBrowser,还有Microsoft Excel 2000,这些都是各种在不同程度上支持这一标准接口的客户端软件。因为这些第三方软件都非常昂贵,适用于大型企业解决方案。
下图中给出了第三方客户端软件Office Web Component的数据展现的基本形式:
附:决策树数据挖掘实验过程指导与分析
39
山东师范大学实验教学指导
决策树数据挖掘技术
这里的决策树数据挖掘技术是基于Microsoft决策树挖掘模型的一种数据挖掘技术: l)在 Analysis Manager窗口中,右键单击“多维数据集”文件夹中需要创建数据挖掘模型的多维数据集(比如“销售”多维数据集),选择弹出菜单中的“新建挖掘模型”命令,出现“挖掘模型向导——选择数据挖掘技术”对话框。
2)在“挖掘模型向导——选择数据挖掘技术”对话框中的“选择一种数据挖掘技术”栏中选择“Microsoft决策树”,然后单击“F一步”按钮出现“挖掘模型向导——选择事例’对话框。
3)在“挖掘模型向导——选择事例”对话框中的“维度”栏中选择“客户”;在“级别”栏中选择“Name”。然后单击“下一步”按钮,出现“挖掘模型向导——选择被预测实体”对话框。
4)在“挖掘模型向导——选择被预测实体”对话框中有三种可选项:“源多维数据集的度量值”选项可以对多维数据集的度量值迸行预测;“事例级别的成员属性”选项可以对成员属性进行预侧;“其他维度成员”选项可以对多维数据集的维度进行预测。这里选择“事例级别的成员属性”选项。单击“事例级别的成员属性”选项;并在其“成员属性”栏中选择‘Member Card”(会员卡)。然后单击“下一步”按钮,出现“挖掘模型向导——选择培训数据”对话框。
5)清除其“多维数据集结构”栏中的“客户”维度中的“Country”、“StateProvince”、“City”和“CustomerRegion_Id”复选框,注意:之所以清除其“多维数据集结构”栏中的“客户”维度中的“Country”、“StateProvince”、“City”和“Customer Region_Id”复选框,是因为我们只希望在“Name”级别中聚合数据。
6)单击“挖掘模型向导——选择培训数据”对话框中的“下一步”按钮;出现“挖掘模型向导——创建维度和虚拟多维数据集(可选)”对话框。在“挖掘模型向导——创建维度和虚拟多维数据集(可选)”对话框中的“维度名称”框中输入“客户模式”,在“虚拟多维数据集名称”框中输入“训练多维数据集”,单击“下一步”按钮,出现“挖掘模型向导——完成”对话框。
7)在“挖掘模型向导——完成”对话框中的“模型名称”栏中输入“客户模式”,并保持“保存并开始处理”按钮被选。单击“完成”按钮,系统即开始对挖掘模型进行处理。对挖掘模型成功处理后,出现“OLAP挖掘模型编辑器”。
8)关闭“OLAP挖掘模型编辑器”,即创建了Microsoft决策树挖掘模型。其实,上述过程除了创建了Microsoft决策树挖掘模型——“客户模式”外,还创建了一个虚拟多维数据集——“训练多维数据集”和一个维度——“客户模式”,因此,我们就可以像浏览一般的多维数据
40
山东师范大学实验教学指导
集和维度一样,浏览挖掘维度和多维数据集数据。
浏览挖掘维度数据:
1) 在Analysis Manager窗口中,右键单击“共享维度”文件夹中需要浏览其数据的挖掘维度(比如“客户模式”挖掘维度),选择弹出菜单中的“浏览维度数据”命令,出现“维度浏览器”。
2)最大化“维度浏览器”。
3) 展开“维度浏览器”中的“维度成员”栏中的“全部”成员,再展开其下的成员(比如,“客户.Name.Yearly Income=$30K-50K”成员),可以看到该成员下面再分为两级,另外,在“自定义成员公式”窗格中可看到该成员的MDX公式。“客户.Name.YearlyIncome=$30K-50K”的意义是年收入在30000美元到50000美元的客户,“客户.Num Children At Home<=2.5”的意义是客户在家的孩子少于等于2.5个,“客户.Num Children At Home>=2.5”的意义是客户在家的孩于大于2.5个。
4)关闭“维度浏览器”。
注意:挖掘维度是虚拟维度,故不能对其属性进行编辑
浏览挖掘多维数据集数据:
1)在Analysis Manager窗口中,右键单击“多维数据集”文件夹中需要浏览其数据的挖掘多维数据集(比如“训练多维数据集”),选择弹出菜单中的“浏览数据”命令,出现“多维数据集数据浏览器”对话框。
2)将“多维数据集数据浏览器”对话框中的“客户模式”维度拖到“Measures”维度处,以替换“Measures”维度。
3)双击“多维数据浏览器”中的数据栏中“USA”、“OR”,展开“Country”级别,展开“客户模式”维度的“全部”级别,即可看到“全部”级别的数据。
4)继续展开“Country”级别和“01级别”、“02级别”等,可以看到更多、更详细的数据。 5)关闭“多维数据集数据浏览器”。
编辑挖掘多维数据集:
与挖掘维度不可编辑不同,挖掘多维数据集可以进行编辑,
1)在 Analysis Manager窗口中右键单击“多维数据集”文件夹中需要进行编辑的挖掘多维数据集(比如“训练多维数据集”),选择弹出菜单中的“编辑”命令,出现“虚拟多维数据集
41
山东师范大学实验教学指导
编辑器”
2)在“多维数据集编辑器”中,可以对挖掘多维数据集的各种属性进行设置,比如通过挖掘多维数据集的“高级”属性选项卡中的“Enable Drill through”属性,可以设置是否在此挖掘多维数据集上启用钻取数据功能。
3)在“多维数据集编辑器”中,也可以查看挖掘多维数据集的数据。比如通过挖掘多维数据集的“客户模式”挖掘维度选择其中的成员,即可查看其数据。
编辑挖掘模型:
挖掘模型也可以进行编辑,
1)在Analysis Manager窗口中,右键单击“挖掘模型”文件夹中需要进行编揖的挖掘模型,选择弹出菜单中的“编辑”命令,出现“OLAP挖掘模型编辑器”。
2)“OLAP挖掘模型编辑器”中,不但可以通过其“属性”窗格修改各种属性,还可以再添加“客户模式”的其他维度的级别(比如.添加“时间”维度中的“年”级别)
浏览决策树:
读者可能己经看到:在“OLAP挖掘模型编辑器”的右边窗格中有一个彩色图形,这个图形称为“决策树”。其实,通过另外一个途径也可以看到这棵决策树,并且查看更为方便。这就是“数据挖掘模型浏览器”。
1)在 Analysis Manager窗口中,右键单击“挖掘模型”文件夹中需要浏览其数据的挖掘模型,选择弹出菜单中的“浏览”命令,出现“数据挖掘模型浏览器”,在“数据挖掘模型浏览器”中包括四个窗格。
“内容详情”窗格显示焦点所在的决策树的部分;“内容选择区”窗格显示树的完整视图,该窗格使用户可以将焦点设置到树的其他部分;“特性”窗格可以用“合计”选项卡以数值方式查看,或者用“直方图”选项卡以图形方式查看;“节点路径”区域窗格显示焦点所在节点相关联的路径,在“内容详情”窗格的下边,有一个彩色长条,其颜色用于提示数据的密度。颜色越深,表示数据密度越大;反之,则数据密度越小。“全部”节点的颜色最深,为黑色,这是因为它包含了100%的数据,所以数据密度最高。在“内客详情”窗格的决策树区域中,颜色代表“事例”的密度(在本事例中为客户的密度)。颜色越深则节点中包含的事例就越多。
进入“数据挖掘模型浏览器”时,在“内容详情”窗格的决策树区域中,“全部”节点被选择(旁边有粗边框)。此时,在“特性”窗格中,8736代表活动1997年和1998年中的客户数目(即“销售”多维数据集中有事务记录的客户),这个数字也说明在1997年和1998年中并非所
42
山东师范大学实验教学指导
有的客户都是活动的,因为 “Customer”维度的“Name”级别中包含有10231个客户,而在“全部”节点中只得到8736个事例。
2)调整“特性”窗格中“合计”面板的“可能性”列的大小,以便看到百分比。在 “特性”窗格显示的“全部”节点中,所有事例的 55.59%(或者说4858个示例)可能选择铜卡(Bronze); 11.54%(或者说 1008个示例)可能选择金卡(Golden); 23.53%(或者说2056个示例)可能选择普通卡(Normal);9.32%(或者说814个示例)可能选择银卡(Silver)。默认情况下,在“特性”窗格中以数字方式显示所选择的节点的情况。
3)单击“特性”窗格中的“直方图”选项卡,则以直方图方式显示所选择的节点的情况。 4)如果选择了树的不同节点,则“特性”窗格的数据将会更改。比如,单击“内容选择区”窗格中的“客户. Name.Yearly Income=$10K-$30k”(第一个)节点,则“特性”窗格的数据发生了明显的变化。我们可以调查一下哪些客户可能选择哪一种卡,比如可以看看哪些客户更喜欢选择金卡。
5)在“数据挖掘模型浏览器”右下角的“树颜色”栏中选择“Golden”。这时,决策树显示另一种颜色模式。从颜色的深浅,可以看出“客户.Name.Yearly Income=$150K+”节点的颜色最深,即其密度高于其他任何节点。也就是说,年收入高于150000美元的客户更喜欢选择金卡。注意“特性”窗格中“合计”面板的数据。
决策树的第一个级别由“yearly income”(年收入)属性决定。树的组织由算法决定,其基础是该属性在输出中的重要性。这意味着“yearly income”属性是最重要的因素,它将决定客户可能选择的会员卡的类型。
6)单击“内容选择区”窗格中的“客户.Name.Yearly Income=$150K+”节点,从 “特性”窗格中可以看出,收入较多的客户中,44.4%的客户可能会选择金卡,这个百分比要比“全部”节点中的(11.54%)高得多。可以通过决策树的子节点,调查一下这些百分比是如何演化的。
7)双击“内容选择区”窗格中的“客户.Name.Yearly Income=$150K+”节点,出现其子节点。从图可以看出,影响该节点的重要因索是“婚姻”状况。
8)单击“客户.Name.Yearly Income=$150K+”节点中的“Customer. Lname. Marital Status=M”子节点。在图中的“特性”窗格现在显示:年收入高于150000美元且已婚的客户中有81.37%的客户可能会选择金卡,而这一级别客户总体中只有44.44%的客户可能会选择金卡。这说明年收入高于150000美元的家庭中,已婚的客户比未婚的客户更喜欢选择金卡。从上面的情形可以看出,收入高于150000美元的客户选择金卡的可能性大小与结婚与否有关,那么其他年收入的客户是否选择金卡的可能性大小也与结婚与否有关呢?我们再看一个节点的情况。
43
山东师范大学实验教学指导
9)单击“数据挖掘模型浏览器”中的“内容选择区”中的顶部位置,回到决策树的顶部。除按上面的操作方法操作外,也可按下面的方法进行操作:
(l)单击从“客户.LName.Yearly Income=$150K+”节点左面伸出来的线,回到决策树的顶部。
(2)再双击“内容选择区”窗格中的“客户.Name.Yearly Income= $30K-$50K”节点,出现其子节点,从可以看出,影响该节点的重要因素是“Num Children At Home”(家中小孩的数目)。
(3)单击“内容选择区”窗格中的“客户.Name.Yearly Income=$30K-$50K”节点中的 “客户.name.num Children at home>2.5”子节点。从中可以看出,家中小孩的数目越多的客户,选择金卡的可能性越大(其百分比高达73.99%)。
另外从总体看,客户.Name.Yearly Income=$30K-$50K节点中的客户选择金卡的可能性不高(仅有13.13%),而选择“铜卡”(Bronze)的可能性更高(73.01%)。读者还可以通过查看其他的节点,以确定哪些客户喜欢哪种会员卡。
(4)关闭“数据挖掘模型浏览器”。
八、数据挖掘算法实验内容
1.关联规则算法实验
计算机技术和通信技术的迅猛发展将人类社会带入到了信息时代。在最近十几年里,数据库中存储的数据急剧增大。例如,NASA轨道卫星上的地球观测系统EOS每小时会向地面发回50GB的图像数据;世界上最大的数据仓库之一,美国零售商系统Wal-Mart每天会产生2亿左右的交易数据;人类基因组数据库项目已经搜集了数以GB计的人类基因编码数据;大型天文望远镜每年会产生不少于10TB的数据,等等。大量的信息在给人们提供方便的同时也带来了一系列问题,由于信息量过大,超出人们掌握、理解信息的能力,因而给正确运用信息带来了困难。
数据挖掘和知识发现是一个涉及多学科的研究领域。数据库技术、人工智能、机器学习、统计学、粗糙集、模糊集、神经网络、模式识别、知识库系统、高性能计算、数据可视化等均与数据挖掘相关。
近年来,KDD(即与数据库的知识发现)研究领域已经成为热点,其中关联规则数据挖掘算法尤为引人注目。关联规则反映一个事物与其他事物之间的相互依存性和关联性。
IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型,并给出求解算法AIS。随后又出现了SETM和Apriori等算法。Apriori是关联规则模型中的经典算法。 1.1相关信息 Apriori算法在发现关联规则领域具有很大影响力。算法命名源于算法使用了频繁项集性质的先验(prior)知识。在具体实验时,Apriori算法将发现关联规则的过程分为两个步骤:第一步通过迭代,检索出事务数据库中的所有频繁项集,即支持度不低于用户设定的阈值的项集;第二步利用频繁项集构造出满足用户最小信任度的规则。其中,挖掘或识别出所有频繁项集是该算法的核心,占整个计算量的大部分。
在对深度优先数据挖掘算法的研究工作中,Han等人没有采用潜在频繁项集的方法求解频繁项集,而是提出了称为频率模式增长(FP_growth)的算法。该算法通过扫描数据库创建
44
山东师范大学实验教学指导
FP_tree的根节点并标示为null,对数据库D中的每一个事务Tran,按L中的次序对Tran中的频繁项排序,设Tran中排序后的频繁项列表[p|P],这里p是第一个元素,P是保留列表。接着调用函数insert_tree([p|P],T),如果树T有一个子节点N且N.item_name=p.item_name,就将N节点计数加1;否则就创建一个新节点N,设计数为1,它的父节点连接到T,节点连接到同名的节点连接结构上。如果P是非空的,就递归调用insert_tree(P,N)。由于压缩了数据库内容,并且在将频繁项写入FP_tree结构时,保留了项集间的相连信息。求解频繁项集的问题,就转化为递归地找出最短频繁模式并连接其后缀构成长频繁模式的问题。 1.2问题重述
近年来,KDD(即与数据库的知识发现)研究领域已经成为热点,其中关联规则数据挖掘算法尤为引人注目。关联规则反映一个事物与其他事物之间的相互依存性和关联性。
IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型,并给出求解算法AIS。随后又出现了SETM和Apriori等算法。Apriori是关联规则模型中的经典算法。
1、分析Apriori算法与FP算法的优缺点 2、分别使用两种算法找出频繁项集 3、挖掘出所有的强关联规则 4、实验数据如下表:
1.3模型求解
45
山东师范大学实验教学指导
2—频繁项集的强关联
Confidence(A=>B)=P(B|A)=P(AB)/P(A)=3/4=0.75 Confidence(B=>A)=P(A|B)=P(AB)/P(B)=3/3=1 Confidence(A=>C)=P(C|A)=P(AC)/P(A)=4/4=1 Confidence(C=>A)=P(C|A)=P(AC)/P(C)=4/4=1 Confidencd(B=>C)=P(C|B)=P(BC)/P(B)=3/3=1 Confidence(C=>B)=P(B|C)=P(BC)/P(C)=3/4=0.75
在满足minconf = 80%的前提下,结果为:B=>A;A=>C;C=>A;B=>C 3—频繁项集的强关联
Confidencd(AB=>C)=P(ABC)/P(AB)=3/3=1 Confidencd(AC=>B)=P(ABC)/P(AC)=3/4=0.75 Confidence(BC=>A)=P(ABC)/P(BC)=3/3=1
在满足minconf = 80%的前提下,结果为:AB=>C;BC=>A 利用FP一树算法求频繁项集
Procedure FP_growth(Tree,a)
(1) ifTree包含一个单一路径P then
(2) for each 路径P中节点组合(记为β)
(3) 生成模式β∪α,拥有支持度为β节点中的最小支持度 (4) Else for each树的头列表节点αi{
(5) 生成模式β=αi∪β且support=ai.support (6) 构成β的条件模式基和β的条件FP_Treeβ (7) IfTreeβ≠фthen
(8) Call FP_growth(Treeβ,β);}[1]
FP-Tree算法使用频繁模式增长方法,第一次扫描与Apriori相同,它导出频繁项(1-项集)的集合,并得到它们的支持度计数(频繁性)。设最小支持度计数为2.频繁项的集合按支持度计数的递减序排序。结果集或表记作L,这样,我们有L={A:4,C:4,B:3}。
图为存放压缩的频繁模式信息的FP_tree:
1.4模型评价
46
山东师范大学实验教学指导
Apriori算法时间消耗的主要症结反映在两个方面,一是由于对海量数据库的多趟扫描,另一个是用JOIN产生潜在频繁项集。
FP-Tree结构在完备性方面,它不会打破交易中的任何模式,而且包含了挖掘序列模式所需的全部信息;在紧密性方面,它不剔除不相关信息,不包含非频繁项,按支持度降序排列,支持度高的项在FP-Tree中共享的机会也高。
性能研究显示FP-growth比Apriori快一个数量级,这是由于FP-growth不生成候选集,不用候选集测试,而且使用紧缩的数据结构,避免重复数据库扫描。
2.决策树程序实验
众所周知,数据库技术从20世纪80年代开始,已经得到广泛的普及和应用。随着数据库容量的膨胀,特别是数据仓库以及web等新型数据源的日益普及,人们面临的主要问题不再是缺乏足够的信息可以使用,而是面对浩瀚的数据海洋如何有效地利用这些数据。
从数据中生成分类器的一个特别有效的方法是生成一个决策树(Decision Tree)。决策树表示方法是应用最广泛的逻辑方法之一,它从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。决策树分类方法采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支,在决策树的叶结点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则,整棵决策树就对应着一组析取表达式规则。
决策树是应用非常广泛的分类方法,目前有多种决策树方法,如ID3、CN2、SLIQ、SPRINT等。
2.1相关信息
决策树是一个类似于流程图的树结构,其中每个内部结点表示在一个属性上的测试,每个分支代表一个测试输入,而每个树叶结点代表类或类分布。数的最顶层结点是根结点。一棵典型的决策树如图1所示。它表示概念buys_computer,它预测顾客是否可能购买计算机。内部结点用矩形表示,而树叶结点用椭圆表示。为了对未知的样本分类,样本的属性值在决策树上测试。决策树从根到叶结点的一条路径就对应着一条合取规则,因此决策树容易转化成分类规则。
图1
ID3算法:
■ 决策树中每一个非叶结点对应着一个非类别属性,树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。
■ 每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。 ■ 采用信息增益来选择能够最好地将样本分类的属性。
47
山东师范大学实验教学指导
信息增益基于信息论中熵的概念。ID3总是选择具有最高信息增益(或最大熵压缩)的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小,并反映划分的最小随机性或“不纯性”。 2.2问题重述
1、算法参见第八章分类与预测 2、目标概念为“寿险促销” 3、计算每个属性的信息增益 4、确定根节点的测试属性
2.3模型求解
构造决策树的方法是采用自上而下的递归构造,其思路是: ■ ■
以代表训练样本的单个结点开始建树(步骤1)。
如果样本都在同一类,则该结点成为树叶,并用该类标记(步骤2和3)。
■ 否则,算法使用称为信息增益的机遇熵的度量为启发信息,选择能最好地将样本分类的属性(步骤6)。该属性成为该结点的“测试”或“判定”属性(步骤7)。值得注意的是,在这类算法中,所有的属性都是分类的,即取离散值的。连续值的属性必须离散化。 ■
对测试属性的每个已知的值,创建一个分支,并据此划分样本(步骤8~10)。
■ 算法使用同样的过程,递归地形成每个划分上的样本决策树。一旦一个属性出现在一个结点上,就不必考虑该结点的任何后代(步骤13)。 ■
递归划分步骤,当下列条件之一成立时停止:
(a)给定结点的所有样本属于同一类(步骤2和3)。
48
山东师范大学实验教学指导
(b)没有剩余属性可以用来进一步划分样本(步骤4)。在此情况下,采用多数表决(步骤5)。这涉及将给定的结点转换成树叶,并用samples中的多数所在类别标记它。换一种方式,可以存放结点样本的类分布。
(c)分支test_attribute=ai 没有样本。在这种情况下,以samples中的多数类创建一个树叶(步骤12)。 算法 输入
Decision_Tree(samples,attribute_list) 由离散值属性描述的训练样本集samples; 候选属性集合attribute_list。
输出 一棵决策树。 (1) 创建节点N;
(2) If samples 都在同一类C中then
(3) 返回N作为叶节点,以类C标记; (4) If attribute_list为空then
(5) 返回N作为叶节点,以samples 中最普遍的类标记;//多数表决 (6) 选择attribute_list 中具有最高信息增益的属性test_attribute; (7) 以test_attribute 标记节点N;
(8) For each test_attribute 的已知值v //划分 samples (9) 由节点N分出一个对应test_attribute=v的分支;
(10) 令Sv为 samples中 test_attribute=v 的样本集合;//一个划分块 (11) If Sv为空 then
(12) 加上一个叶节点,以samples中最普遍的类标记;
(13) Else 加入一个由Decision_Tree(Sv,attribute_list-test_attribute)返回节点值。[1] 由题目条件,可知,以“寿险促销”为目标概念,属性“寿险促销”有2个不同的值{是,否},即c=2,C1对应“是”,C2对应“否”。则C1有9个样本,C2有6个。则:
E(S)=(-9\\15)log2(9\\15)-(6\\15)log2(6\\15)=0.971
Values(收入范围)={20-30K,30-40k,40-50K,50-60K} E(S(20-30K))= (-2\\4)log2(2\\4)- (2\\4)log2(2\\4)=1
E(S(30-40K))= (-4\\5)log2(4\\5)- (1\\5)log2(1\\5)=0.7219 E(S(40-50K))= (-1\\4)log2(1\\4)- (3\\4)log2(3\\4)=0.8113 E(S(50-60K))= (-2\\2)log2 (2\\2)- (0\\2)log2(0\\2)=0 所以
E(S,收入范围)=(4/15) E(S(20-30K)) +(5/15) E(S(30-40K)) +(4/15) E(S(40-50K)) +(2/15)
E(S(50-60K))=0.7236
Gain(S,收入范围)=0.971-0.7236=0.2474
同理:计算“保险”,“性别”,“年龄”的信息增益为: E(S)=(-9\\15)log2(9\\15)-(6\\15)log2(6\\15)=0.971 Insurance(保险)={yes, no}
E(S(yes))= (-3\\3)log2 (3\\3)- (0\\3)log2(0\\3)=0 E(S(no))= (-6\\12)log2 (6\\12)- (6\\12)log2(6\\12)=1 E(S, 保险)=(3/15) E(S(yes)) +(12/15) E(S(no)) =0.8 Gain(S, 保险)=0.971-0.8=0.171
E(S)=(-9\\15)log2(9\\15)-(6\\15)log2(6\\15)=0.971 sex(性别)={male, female}
E(S(male))= (-3\\7)log2 (3\\7)- (4\\7)log2(4\\7)=0.9852 E(S(female))= (-6\\8)log2 (6\\8)- (2\\8)log2(2\\8)=0.8113
E(S, 性别)=(7/15) E(S(male)) +(8/15) E(S(female)) =0.8925
49
山东师范大学实验教学指导
Gain(S, 性别)=0.971-0.8925=0.0785
E(S)=(-9\\15)log2(9\\15)-(6\\15)log2(6\\15)=0.971 age(年龄)={15~40,41 ~60}
E(S(15~40))= (-6\\7)log2 (6\\7)- (1\\7)log2(1\\7)=0.5917 E(S(41 ~60))= (-3\\8)log2 (3\\8)- (5\\8)log2(5\\8)=0.9544
E(S, 年龄)=(7/15) E(S(15~40)) +(8/15) E(S(41 ~60)) =0.7851 Gain(S, 年龄)=0.971-0.7851=0.1859 2.4模型评价
基于决策树的分类算法的一个最大的优点就是她在学习过程中不需要使用者了解很多背景知识(这同时也是它的最大的缺点),只要训练例子能够用属性-结论式表示出来,就能使用该算法来学习。
在ID3算法的假设空间包含所有的决策树,它是关于现有属性的有限离散值函数的一个完整空间。因为每个有限离散值函数可被表示为某个决策树,所以ID3算法避免了搜索不完整假设空间的一个主要风险:假设空间可能不包含目标函数。ID3算法只能处理离散值的属性。首先,学习到的决策树要预测的目标属性必须是离散的,其次树的决策结点的属性也必须是离散的。
50
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
51
因篇幅问题不能全部显示,请点此查看更多更全内容