《数据仓库与数据挖掘技术》第6章数据挖掘基本算法课件

第6章数据挖掘基本算法本章内容：6.1分类规则挖掘6.2预测分析与趋势分析规则6.3数据挖掘的关联算法6.4数据挖掘的聚类算法6.5数据挖掘的统计分析算法6.6数据挖掘的品种优化算法6.7数据挖掘的进化算法6.1分类规则挖掘6.1.1分类与估值1分类为了理解事物特征并做出预测使用历史数据建立一个分类模型（即分类器）的过程。应用于信用卡系统中的信用分级、市场调查、疗效诊断、寻找店址等实践应用参照课本6.1分类规则挖掘

6.1.1分类与估值2估值估值（estimation）与分类类似，不同之处在于，分类描述的是离散型变量的输出，而估值处理连续值的输出；分类的类别是确定的数目，估值的量是不确定的。

3分类方法与步骤

方法：决策树归纳、贝叶斯分类、贝叶斯网络、神经网络。还有K-最临近分类、基于案例的推理、遗传算法、粗糙集和模糊集方法。步骤：模型创建、模型使用6.1分类规则挖掘6.1.1分类与估值4评估分类方法要考虑的指标：预测准确率、速度、创建速度、使用速度、鲁棒性、处理噪声和丢失值、伸缩性、对磁盘驻留数据的处理能力、可解释性、对模型的可理解程度、规则好坏的评价、决策树的大小和分类规则的简明性。6.1分类规则挖掘6.1.2决策树父节点子节点子节点叶节点子节点子节点子节点根节点图6.1一般决策树结构叶节点父节点6.1分类规则挖掘6.1.2决策树1．决策树的构造过程ID3算法应用如下：信息量计算公式：I(s1,s2,…sm)=-（6.1）其中，pi为si占整个类别的概率利用属性A划分当前样本集合所需要的信息（熵）的计算公式为：E（A）=(6.2)信息增益公式：Gain（A）=I(s1,s2,…sm)-E（A）（6.3）例如：一个销售的顾客数据库（训练样本集合）,对购买计算机的人员进行分类：字段为：（年龄（取值：<30,30~40,>40>）；收入(高，中，低)；学生否（Y，N）；信用（一般，很好）；购买计算机否（Y，N））记录为14个，具体数据如下：X1=(<30,高,N,一般,N)；X2=(<30,高,N,很好,N)X3=(30~40,高,N,一般,Y)；X4=(>40,中,N,一般,Y)X5=(>40,低,Y,一般,Y)；X6=(>40,低,Y,很好,N)X7=(<30-40,低,Y,高,Y)；X8=(<30,中,N,一般,N)X9=(<30,低,Y,一般,Y)；X10=(>40,中,Y, 一般,Y)X11=(<30,中,Y,很好,Y)；X12=(30~40,中,N,很好,Y)X13=(30~40,高,Y,一般,Y)；X14=(>40,中,N,很好,N)6.1分类规则挖掘

6.1.2决策树1．决策树的构造过程决策树的构造算法：

决策树的构造算法可通过训练集T完成，其中T={<x,cj>}，而x=(a1,a2,…,an)为一个训练实例，它有n个属性，分别列于属性表(A1,A2,…,An)中，其中ai表示属性Ai的取值。Cj∈C={C1,C2,…,Cm}为x的分类结果。从属性表中选择属性Ai作为分类属性；若属性Ai的取值有ki个，则将T划分为ki个子集，T1,…,Tki，其中Tij={<x,C>|<x,C>}∈T，且x的属性取值A为第i个值；接下来从属性表中删除属性Ai；对于每一个Tij(1≤j≤K1)，令T=Tij；如果属性表非空，返回第1步，否则输出。6.1分类规则挖掘

6.1.2决策树2．分类器定义：输入的数据含有千万个记录，每个记录又有很多个属性，其中有一个特别的属性叫做类（例如信用程度的高，中，低）。具体步骤：1）树的建立。2）树的修剪,SLIQ采用了MDL（最小叙述长度）的方法来修剪树。

6.1分类规则挖掘

6.1.2决策树3．决策树的可扩展性4．基于决策树方法的数据挖掘工具

KnowledgSEEKER

6.1分类规则挖掘

6.1.3贝叶斯分类1．贝叶斯信任网络如何工作边缘主区域手机呼叫服务区域noyes外界图6.3简单的贝叶斯网图6.1分类规则挖掘6.1.3贝叶斯分类2．贝叶斯定理与朴素贝叶斯分类贝叶斯定理:P(H|X)=P(X|H)P(H)/P(X)其中，P(H|X)表示条件X下H的概率，也称为条件概率或称为后验概率(posterioriprobabilities)。朴素贝叶斯分类：假定有m个类C1,…Cm,对于数据样本X,分类法将预测X属于类Ci,当且仅当P(Ci|X)>P(Cj|X),6.2预测分析与趋势分析规则6.2.1预言的基本方法预言（prediction）是一门掌握对象变化动态的科学，它是对对象变动趋势的预见、分析和判断，也是一种动态分析方法。预测的基本步骤：确定预测目标，包括预测对象、目的、对象范围；收集分析内部和外部资料；数据的处理及模型的选择；预测模型的分析、修正；确定预测值。6.2预测分析与趋势分析规则6.2.2定量分析预测时间序列法回归预测非线性模型灰色预测模型GM（1，1）组合预测6.2预测分析与趋势分析规则6.2.3预测的结果分析预测的结果分析要考虑到的因素：相反的预测结果胜出裕度成本收益分析6.2预测分析与趋势分析规则6.2.4趋势分析挖掘分析时间序列数据需要注意以下方面：长时间的走向周期的走向与周期的变化季节性的走向与变化不规则的随机走向6.3数据挖掘的关联算法6.3.1关联规则的概念及分类1．关联规则的概念定义1设I={i1、i2、i3，…,im}是由m个不同的数据项目组成的集合，其中的元素称为项(item)，项的集合称为项集，包含k个项的项集称为k项集,给定一个事务（交易）D，即交易数据库，其中的每一个事务（交易）T是数据项I的一个子集，即，T有一个惟一的标积符TID；当且仅当时，称交易T包含项集X；那么关联规则就形如“X=>Y”的蕴涵式；其中，，，Ф，即表示满足X中条件的记录也一定满足Y。关联规则X=>Y在交易数据库中成立,具有支持度s和具有置信度c。这也就是交易数据集D中具有支持度s，即D中至少有s%的事务包含,描述为：support(X=>Y)=比如Support(X=>Y)=同时购买商品X和Y的交易数总交易数同时交易数据集D中具有置信度c，即D中包含X的事务至少有c%同时也包含Y,描述为：confidence(X=>Y)=比如购买了商品X，同时购买商品Y可信度，confidence(X=>Y)=同时购买商品X和Y的交易数购买了商品X的交易数一般称满足一定要求的规则为强规则。通常称满足最小支持度和最小置信度的关联规则为强关联规则（strong）。一般将最小支持度简记为minsup和最小置信度简记为minconf。6.3数据挖掘的关联算法6.3.1关联规则的概念及分类2关联规则的分类6.3数据挖掘的关联算法6.3.2简单形式的关联规则算法（单维、单层和布尔关联规则）1．简单形式的关联规则的核心算法找到所有支持度大于最小支持度的项集,即频集,有k个数据频集称为k项频集.找出所有的频集由apriori算法实现。Apriori性质具有一个频集的任一非空子集都是频集。使用第1步找到的频集产生期望的规则

apriori算法的详细介绍见课本。6.3数据挖掘的关联算法6.3.2简单形式的关联规则算法（单维、单层和布尔关联规则）2频集算法的几种优化方法基于划分的方法基于hash的方法基于采样的方法减少交易的个数6.3数据挖掘的关联算法6.3.2简单形式的关联规则算法（单维、单层和布尔关联规则）3其他的频集挖掘方法FP-growth方法min_hashing(MH)和locality_sensitive_hashing(LSH)6.3数据挖掘的关联算法6.3.3多层和多维关联规则的挖掘多层关联规则多维关联规则关联规则价值衡量的方法6.3.4货篮子分析存在的问题详见课本6.3数据挖掘的关联算法6.3.5关联分析的其他算法发现关联的更好方法统计相关以外的理解关联有效可行的市场篮子分析6.3.6挖掘序列模式序列模式的概念及定义

序列模式挖掘的主要算法

GSP算法描述PrefixSpan算法关联规则挖掘—一个例子最小值尺度50%最小可信度50%对于A

C：support=support({A、C})=50%confidence=support({A、C})/support({A})=66.6%Apriori的基本思想:频繁项集的任何子集也一定是频繁的关键步骤：挖掘频繁集频繁集:是指满足最小支持度的项目集合频繁集的子集也一定是频繁的如,如果{AB}是频繁集，则{A}{B}也一定是频繁集从1到k（k-频繁集）递归查找频繁集用得到的频繁集生成关联规则Apriori算法连接:用Lk-1自连接得到Ck修剪:一个k-项集，如果他的一个k-1项集（他的子集）不是频繁的，那他本身也不可能是频繁的。伪代码:Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for

(k=1;Lk!=;k++)dobegin

Ck+1=candidatesgeneratedfromLk;

foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedint

Lk+1=candidatesinCk+1withmin_support

endreturn

k

Lk;Apriori算法—例子数据库D扫描DC1L1L2C2C2扫描DC3L3扫描D如何生成候选集假定Lk-1中的项按顺序排列第一步:自连接Lk-1

insertinto

Ckselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1<q.itemk-1第二步:修剪forallitemsetscinCk

doforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk如何计算候选集的支持度计算支持度为什么会成为一个问题？候选集的个数非常巨大一笔交易可能包含多个候选集方法:用hash-tree存放候选集树的叶子节点

of存放项集的列表和支持度内部节点是一个hash表Subset函数:找到包含在一笔交易中的所有候选集生成候选集的例子L3={abc,abd,acd,ace,bcd}自连接:L3*L3abc和abd得到abcdacd和ace得到acde修剪:ade不在L3中，删除acdeC4={abcd}提高Apriori效率的方法基于Hash的项集计数:如果一个k-项集在hash-tree的路径上的一个计数值低于阈值，那他本身也不可能是频繁的。减少交易记录:不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集分割:一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个分割上是频繁的。采样:在给定数据的子集上挖掘，使用小的支持度+完整性验证方法动态项集计数:在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的。Apriori够快了吗?—性能瓶颈Apriori算法的核心:用频繁的(k–1)-项集生成候选的频繁k-项集用数据库扫描和模式匹配计算候选集的支持度Apriori的瓶颈:候选集生成巨大的候选集:104个频繁1-项集要生成107个候选2-项集要找尺寸为100的频繁模式，如{a1,a2,…,a100},你必须先产生21001030个候选集多次扫描数据库：如果最长的模式是n的话，则需要(n+1)次数据库扫描6.4数据挖掘的聚类算法6.4.1聚类分析的概念与分类聚类分析概念聚类分析方法的分类6.4数据挖掘的聚类算法6.4.2聚类分析中两个对象之间的相异度计算方法区间标度变量计算方法

二元变量计算方法标称型、序数型和比例标度型变量计算方法混合类型的变量计算方法6.4数据挖掘的聚类算法6.4.3划分方法典型的划分方法：k-平均和k-中心点

基于簇的重心技术：k-平均方法基于有代表性的对象的技术：k-中心点方法大型数据库中的划分方法：基于选择的K-中心点CLARANS方法6.4数据挖掘的聚类算法6.4.4层次方法凝聚的和分裂的层次聚类

凝聚层次聚类方法AGNES分裂层次聚类方法DIANA利用层次方法的平衡迭代归约和聚类综合的层次聚类方法B