1、1数据挖掘技术第二部分 分类预测、聚类、关联规则2数据挖掘提纲数据挖掘提纲p 第一部分- 概述概述- 相关概念相关概念- 数据挖掘技术数据挖掘技术p第二部分第二部分-分类-聚类-关联规则p 第三部分- Web 挖掘挖掘- 空间数据挖掘空间数据挖掘- 时序数据挖掘时序数据挖掘3分类分类p分类问题概述p分类技术- 基于统计的算法基于统计的算法- 基于距离的算法基于距离的算法- 基于决策树的算法基于决策树的算法- 基于规则的算法基于规则的算法- 基于神经网络的算法基于神经网络的算法- 支持向量机支持向量机4分类问题分类问题p给定一个由元组组成的数据库（数据集） D=t1,t2,tn 和一个类别集合
2、C=C1,Cm, 分分类问题类问题 是指定义一个映射 f:DgC ，其中每个元组 ti 被分配到一个类中.p预测预测 是一种特殊的分类, 连续时可看成无限多类，离散时就是分类了.5分类举例分类举例p老师根据分数将学生分类为 A, B, C, D, 和 F. p识别蘑菇是否有毒.p预测何时何地会发洪水.p识别个人的信用风险. p语音识别p模式识别6等级分类等级分类px = 90 等级 =A.p80=x90 等级 =B.p70=x80 等级 =C.p60=x70 等级 =D.px=90=80=70=6050 xCD7字母识别字母识别一个字母由五个组成部分组成:Letter CLetter ELet
3、ter ALetter DLetter FLetter B8分类方法分类方法p步骤步骤:1. 通过对训练集进行计算产生一个特定通过对训练集进行计算产生一个特定的模型。训练数据作为输入，以计算的模型。训练数据作为输入，以计算得到的模型作为输出得到的模型作为输出2. 将产生的模型应用于目标数据库中对将产生的模型应用于目标数据库中对元组进行分类元组进行分类.p类别必须预先定义类别必须预先定义p最常用的算法包括决策树，神经网络，及基最常用的算法包括决策树，神经网络，及基于距离，统计等算法于距离，统计等算法.9定义类别定义类别分割分割基于距离基于距离10分类中的问题分类中的问题p缺失数据- 忽略忽略-
4、利用假定值来替换利用假定值来替换p性能度量- 分类精度分类精度- 混淆矩阵混淆矩阵- ROC 曲线曲线11身高数据例子身高数据例子Nam e Gender Height Output1 Output2 Kristina F 1.6m Short Medium Jim M 2m Tall Medium Maggie F 1.9m Medium Tall Martha F 1.88m Medium Tall Stephanie F 1.7m Short Medium Bob M 1.85m Medium Medium Kathy F 1.6m Short Medium Dave M 1.7m Sh
5、ort Medium W orth M 2.2m Tall Tall Steven M 2.1m Tall Tall Debbie F 1.8m Medium Medium Todd M 1.95m Medium Medium Kim F 1.9m Medium Tall Amy F 1.8m Medium Medium W ynette F 1.75m Medium Medium 12分类表现：分类表现：混淆矩阵混淆矩阵真正例真反例假正例假反例13ROC 曲线曲线14回归回归p根据输入值估计一个输出值p确定最佳的 回归系数回归系数 c0,c1,cn.p假设出一个误差: y = c0+c1x1
6、+cnxn+ep可以利用均方差函数估计线性回归模型拟合实际数据的精度:15线性拟合误差线性拟合误差16回归用于分类回归用于分类p分割分割: 利用回归函数，将空间划分成一些区域，每一个类对应一个区域. p预测预测: 通过回归，产生一个可以用于预测类别值的线性公示17分割分割18预测预测19基于距离法的分类基于距离法的分类p将更接近或更相似的成员映射到同一个类别当中去p必须确定项之间或者类之间的距离 .p类别描述-质心: 中心值中心值.-中心点: 代表点代表点.- 各个元组各个元组p算法: KNN20K最近邻 (KNN):p训练集包括了类别标签.p进一步考虑训练集中K个与新元组相距最近的元组.p新
7、元组将被分配到一个包含了K个最近元组中最多元组的那一类.pO(q) 是该问题的时间复杂度. (q 训练集中元组的个数.)21KNN22KNN 算法算法23基于决策树的算法基于决策树的算法p基于区域划分基于区域划分: 将搜索空间划分为一些矩形区域.p根据元组落入的区域对元组进行分类.p大部分研究集中在如果有效的构建树: 决策树归纳决策树归纳p内部结点标记为一个属性，属性值为弧p算法: ID3, C4.5, CART24决策树决策树给定: - D = t1, , tn ，其中，其中 ti= - 数据库模式包含下列属性数据库模式包含下列属性 A1, A2, , Ah- 类别集合类别集合 C=C1,
8、., Cm决策树或分类数决策树或分类数 是具有下列属性的树- 每个内部结点都标记一个属性每个内部结点都标记一个属性, Ai- 每个弧都被标记一个谓词，这个谓词可应用于相应的父每个弧都被标记一个谓词，这个谓词可应用于相应的父结点的属性结点的属性- 每个叶结点都被标记一个类每个叶结点都被标记一个类, Cj25DT 算法算法26决策树划分区域决策树划分区域 GenderHeightMF27决策树对比决策树对比平衡树深的树28决策树的问题决策树的问题p选择分裂属性p分裂属性次序p分裂p树的结构p停止准则p训练数据p剪枝29决策树往往基于信息论构建决策树往往基于信息论构建So 30信息信息31信息信息/
9、熵熵p给定概率 p1, p2, ., ps ，之和为 1, 熵的定义为:p熵是数据不确定性、突发性或随机性程度的度量.p分类的目标- 没有不确定性没有不确定性- 熵为熵为 032熵熵log (1/p)H(p,1-p)33ID3p基于信息论构建决策树的ID3技术试图使比较的期望数最小化。pID3 利用最高信息增益属性作为分裂属性:34ID3 例子例子p 初始集合的熵:4/15 log(15/4) + 8/15 log(15/8) + 3/15 log(15/3) = 0.4384p 性别作为分裂属性的信息增益:- 女女: 3/9 log(9/3)+6/9 log(9/6)=0.2764- 男男:
10、 1/6 (log 6/1) + 2/6 log(6/2) + 3/6 log(6/3) = 0.4392- 加权和加权和: (9/15)(0.2764) + (6/15)(0.4392) = 0.34152- 增益增益: 0.4384 0.34152 = 0.09688p 身高作为分裂属性的信息增益:0.4384 (2/15)(0.301) = 0.3983p 选择身高作为第一个分裂属性35C4.5pID3 偏袒具有较多值的属性p ID3的改进版本:- 缺失数据缺失数据- 连续数据连续数据- 剪枝剪枝- 规则规则- 分裂分裂:36基于神经网络的算法基于神经网络的算法p传统神经网络算法用于分类
11、:- 对每个类别都有一个输出结点对每个类别都有一个输出结点- 输出值表示相应的输入元组属于某类的概率输出值表示相应的输入元组属于某类的概率p有指导的学习 p训练集中的每个元组输入后，由图中得到的分类与实际比较，基于预测精度改变图中的各种标记值(权值). p算法: 传播, 反传播, 梯度下降37神经网络分类需要考虑的问题神经网络分类需要考虑的问题 p属性（源结点数目）p隐含层的数目，隐含结点的数目p训练数据p汇结点的数目p连接p权值p激活函数p学习技术p停止准则38决策树和神经网络对比决策树和神经网络对比39传播传播Tuple InputOutput 40NN 传播算法传播算法41传播例子传播例
12、子 Prentie Hall42神经网络有指导学习神经网络有指导学习p调整弧的权值的过程.p有指导学习有指导学习: 期望的输出是已知的.p无指导学习无指导学习: 不知道输出情况下的学习.p本章内容是有指导的学习43神经网络的有指导学习神经网络的有指导学习44有指导学习有指导学习p假设结点i 输出为yi，而实际的输出应该为di:p基于输出值是否正确这一信息，来改变输入弧上的权值45NN 反向传播反向传播p反向传播是一种调整神经网络权值的学习技术.pDelta 准则准则: r wij= c xij (dj yj)p梯度下降梯度下降: 网络调整权值的技术.46反向传播反向传播Error47反向传播算
13、法反向传播算法48梯度下降梯度下降49梯度下降算法梯度下降算法50输出层学习输出层学习51隐藏层学习隐藏层学习52径向基函数网络径向基函数网络pRBF 具有高斯函数的形状pRBF 网络- 三层三层- 隐藏层隐藏层 高斯激励函数高斯激励函数- 输出层输出层 线性激励函数线性激励函数53径向基函数网络径向基函数网络54感知器感知器p感知器是最简单的神经网络.p没有隐藏层.55感知器例子感知器例子p假设:- S=3x1+2x2-6- 激励函数激励函数: if S0 then 1 else 056支持向量机支持向量机pSVM：线性可分57SVM：线性可分：线性可分p最优分类超平面问题可以表示成约束优化
14、问题优分类超平面问题可以表示成约束优化问题- Minimize- Subject top定义定义Lagrange函数函数211( )()22() 1,1,.,iiwww wyw xbilliiiibwxywbwL1221) 1)(),(58SVM：线性可分：线性可分aminmjijTijijimiiaxxyyaaaaL1,121)(miayaimiii , 1, 0, 01s.t p 对偶问题对偶问题标准的二次优化问题，在不等式约束条件下进行二次函数寻优。存在唯一解 。*p决策函数决策函数)(sgn()(1miiiibxxyxf引入核函数引入核函数可解决非线性可解决非线性可分问题可分问题),(
15、jixxK 线性不可分？线性不可分？59SVM: 非线性非线性核函数：从低维空间映射到高维空间60基于规则的分类算法基于规则的分类算法p使用 If-Then 规则执行分类p分类准则分类准则: r = 前件前件, 后件后件p可以由其他技术生成规则 (DT, NN) 或者直接生成.p算法: Gen, RX, 1R, PRISM61从决策树生成规则从决策树生成规则62例子例子63从神经网络生成规则从神经网络生成规则641R 算法算法基于一个属性产生规则基于一个属性产生规则651R 例子例子66决策树决策树 vs. 规则规则 p树中有隐含的次序，按照次序产生分枝.p树是基于考虑所有类别产生的.p规则没
16、有次序.p一次仅需要考虑一个类别.67聚类聚类p聚类问题概述p聚类技术- 层次算法层次算法- 划分算法划分算法- 遗传算法遗传算法- 大型数据库聚类大型数据库聚类68聚类例子聚类例子p基于客户数据库的相似性采购模式.p基于相似特征城市住宅类别划分.p植物新品种鉴定p找出类似网络应用69聚类举例聚类举例70住房聚类住房聚类Geographic Distance Based71分类分类 vs聚类聚类p没有预先知道的知识- 类别的数目类别的数目- 类别的含义类别的含义p无指导的学习72聚类问题聚类问题p异常点的处理p动态数据p结果的解释p结果评价p分类数目p所需的数据p最优结果73异常点异常点74聚
17、类问题聚类问题p给定数据库 D=t1,t2,tn 和整数值 k, 那么聚类聚类问题问题 被定义为：定义一个映射 f:Dg1,.,k ，其中 ti 被映射到 Kj中p一个簇 ，Kj 由被映射到该簇中的元组组成.p与分类问题不同，聚类一般没有先验知识.75聚类方法分类聚类方法分类 p层次方法层次方法 产生一个嵌套的聚集.p划分方法划分方法 利用算法构造一个簇集，簇的数目由用户指定或系统指定.p增量模式增量模式 每个成员由算法一个个的依次处理.p同时处理模式同时处理模式 所有成员由算法一同处理.p重叠簇重叠簇/非重叠簇非重叠簇76聚类算法的分类聚类算法的分类聚类层次划分的类别的大型数据库凝聚分裂抽样
18、压缩77相似性和距离度量相似性和距离度量78簇之间距离簇之间距离p单连接单连接: 一个簇中所有成员与另一个簇中的所有成员之间的最短距离p全连接全连接: 一个簇中所有成员与另一个簇中的所有成员之间的最大距离p平均平均: 簇间所有成员之间的平均距离p质心质心: 两个簇之间的质心的距离79层次算法层次算法p层次聚类算法实际上产生嵌套的簇集.p凝聚算法凝聚算法- 最初，每个成员都组成一个单独的簇最初，每个成员都组成一个单独的簇- 再把相互邻近的簇合并成一个簇再把相互邻近的簇合并成一个簇- 自底向上自底向上p分裂算法分裂算法- 最初，所有元组都属于同一个簇最初，所有元组都属于同一个簇- 将上层的簇重复地
19、分裂为两个下层簇将上层的簇重复地分裂为两个下层簇- 自上而下自上而下80谱系图谱系图p谱系图谱系图: 利用树形数据结构来表示层次聚类技术以及不同的簇集.p每个层次都表示某个簇所在的等级.- 叶结点叶结点 每个个体单独成每个个体单独成簇簇- 根结点根结点 一个簇一个簇p中间结点是由其子结点合并而成的新的簇815个聚类层次个聚类层次82凝聚例子凝聚例子ABCDEA01223B10243C22015D24103E33530BAECD4阀值 2 351A B CDE83最小生成树最小生成树ABCDEA01223B10243C22015D24103E33530BAECD84凝聚算法凝聚算法85单连接技术
20、单连接技术p查看所有项的连接 (距离).p发现最大的连通子图.p容易至少存在一条连接两个簇的边，并且两点之间的最短距离小于或等于给定的阈值，则合并这两个簇.p在每个级别使用阈值.p可以是凝聚，可以是分化.86最小生成树单连接算法最小生成树单连接算法87谱系图谱系图88划分算法划分算法p没有等级p一步中就产生所有的簇，而不需要几个步骤.p由于仅有一个簇集作为输出,所以用户必须输入期望得到的簇的数目 k.p通常处理静态数据.89划分算法划分算法p最小生成树p平方误差聚类算法pK-均值聚类p最近邻算法pPAM算法p给定能量算法p遗传算法90最小生成树最小生成树91平方误差度量平方误差度量p最小平方误
21、差92平方误差聚类算法平方误差聚类算法93K-均值聚类均值聚类p初始值是任意分配的.p迭代过程中不断地移动簇集中的成员直至得到理想的簇集为止.p成员间的相似度很高.p给定簇 Ki=ti1,ti2,tim, 其均值等义为：其均值等义为： mi = (1/m)(ti1 + + tim)94K-均值聚类例子均值聚类例子p给定: 2,4,10,12,3,20,30,11,25, k=2p随机两个数值作为簇的均值: m1=2,m2=4pK1=2,3, K2=4,10,12,20,30,11,25, m1=2.5,m2=16pK1=2,3,4,K2=10,12,20,30,11,25, m1=3,m2=1
22、8pK1=2,3,4,10,K2=12,20,30,11,25, m1=4.75,m2=19.6pK1=2,3,4,10,11,12,K2=20,30,25, m1=7,m2=25p簇的成员一直不再变化，迭代停止.95K-均值聚类算法均值聚类算法96最近邻算法最近邻算法p随着算法的迭代，成员依次被合并到离自身最近的簇中.p增量p阈值, t, 来判断成员是否将被加入到已经存在的簇中或产生一个新的簇.97最近邻算法最近邻算法98PAMp围绕中心点划分围绕中心点划分 (PAM) (K-中心点算法中心点算法)p很好的处理异常点.p没有很好的扩展性.p利用中心点来代表一个簇.p初始时，随机的k个成员设置
23、为中心点的集合.99PAM100PAM 距离代价计算距离代价计算p在算法每一步，不停的交换中心点，如果交换中心点可以改善聚类效果，则进行交换.pCjih 中心点ti 与非中心点th 交换后，元组tj 到中心点的距离代价的变化.101PAM 算法算法102遗传算法例子遗传算法例子pA,B,C,D,E,F,G,Hp随机选择初始状态:A,C,E B,F D,G,H10101000, 01000100, 00010011103遗传算法遗传算法104大型数据库聚类大型数据库聚类p大多算法都假设有足够内存用于存储聚类的数据及相应的数据结构.p大多算法假设数据一次提供，对动态数据库不适用.p算法- BIRC
24、H- DBSCAN- CURE105DBSCANp以最小规模和密度产生簇p异常点不影响簇的创建.p输入- MinPts 在任何簇中的点的最小数目在任何簇中的点的最小数目- Eps 对于在簇中的每个点，必须存在簇外另外一个对于在簇中的每个点，必须存在簇外另外一个点，它们之间的距离小于一个输入阈值点，它们之间的距离小于一个输入阈值.106DBSCAN 直接密度可达直接密度可达pEps-邻域邻域: 离该点 Eps 所有点的集合.p核心点核心点: Eps-邻域有足够密度的(MinPts)p直接密度可达直接密度可达: 点 p 和点 q 距离小于 (Eps) 并且q为核心点.p密度可达密度可达: 两个点之
25、间存在一条链，链中只包含一个核心点（从该点直接密度可达）.107例子例子108DBSCAN 算法算法109CUREp利用代表点进行聚类p利用多个代表点替代单个点（中心点或质心）p利用代表性点，簇的形状可以更好的被表示出来110CURE 例子例子111CURE 算法算法112CURE 算法概括算法概括p对数据库抽样得到样本.p将样本划分为p个分区.p对每个分区进行聚类，利用层次算法.p删除异常点.（两种方法）p利用凝聚算法将所有簇进行分类，输入只包括簇的代表性点p使用c个点代表每个簇，对磁盘整个数据库进行聚类113聚类技术对比聚类技术对比114关联规则关联规则目标目标: 提供一个关联规则的概述并
26、介绍几种常见关联规则的算法p 关联规则概述- 大项目集大项目集p 关联规则算法- Apriori算法算法- 抽样算法抽样算法- 划分算法划分算法- 并行和分布式算法并行和分布式算法p 方法比较p 增量规则p 高级关联规则技术115例子：超市数据例子：超市数据p商品常常被一起购买:买包花生酱p用途:- 场地布置场地布置 - 广告宣传广告宣传- 市场营销市场营销- 库存控制库存控制p目标: 增加收入，减少成本116关联规则定义关联规则定义p项集合项集合: I=I1,I2,Imp事务数据库事务数据库: D=t1,t2, , tn, tj Ip事务事务: Ii1,Ii2, , Iik Ip支持项集支持
27、项集: 某一事务包含了所研究的项集.p频繁频繁项集项集: 项集的支持度大于阈值.117关联规则例子关联规则例子I = 啤酒,面包, 果冻, 牛奶, 花生酱Bread,PeanutButter 占的比例 60%118相关的定义相关的定义p关联规则关联规则 (AR): 表示为表示为X Y ，当 X,Y I ，并且 X Y =;p支持度支持度 (s) X Y: 数据库中包含X Y的事务占库中所有事务的百分比p置信度置信度 ( ) X Y: 包含 X Y 事务数与包含 X的事务数的比值119例子（续）例子（续）120关联规则问题关联规则问题p给定一组项 I=I1,I2,Im 和一个事务数据库 D=t1
28、,t2, , tn ，其中 ti=Ii1,Ii2, , Iik 并且 Iij I, 关联规则关联规则 是找出满足最小支持度和最小置信度的所有关联规则 X Y.121关联规则技术关联规则技术1.发现频繁项集.2.从频繁项集生成关联规则.122关联规则算法关联规则算法123Apriori算法算法p频繁项集性质项集性质:频繁项集的任何一个子集也一定是频繁项集.p逆否命题:如果一个项集是频繁的如果一个项集是频繁的, 那么他的任何超集都是频繁的那么他的任何超集都是频繁的.124大项目集的性质大项目集的性质125Apriori 例子（续）例子（续）s=30% = 50%126Apriori 算法算法1.C
29、1 = 单个项的项集和集合;2. 找出大小为1的所有频繁项集, L1;3. i = 1;4. Repeat5. i = i + 1;6. Ci = Apriori-Gen(Li-1);7. 通过 Ci 确定 Li;8. 直到没有频繁项集再出现;127Apriori-Gen算法算法p通过大小为 i的频繁项集生成 大小为i+1的候选项集.p常用方法: 如果大小是i-1的项集为频繁项集，则将包含此项集的大小为i的项集作为候选项集 p可以对候选项集进行修剪，避免过大.128例例129例（续）例（续）130Apriori 优缺点优缺点p优点优点:- 利用大项目集特性利用大项目集特性.- 容易并行容易并行
30、- 方便使用方便使用.p缺点缺点:- 假定数据库驻留在内存当中假定数据库驻留在内存当中.- 扫描次数可能很高扫描次数可能很高.131划分划分p将数据库划分为p个分区， D1,D2,Dpp在每个分区中运用 Apriori 算法p任何项集必须至少在一个分组中是频繁的.132划分算法划分算法1.划分 D 为p个分区 D1,D2,Dp;2.For I = 1 to p do3. Li = Apriori(Di);4.C = L1 Lp;5.把 C 运用到 D 产生最终的 L;133划分算法例子划分算法例子D1D2S=10%L1 =L2 =134划分算法优缺点划分算法优缺点p优点优点:- 更好地适应内存
31、的限制更好地适应内存的限制- 容易构造并行算法容易构造并行算法- 最大扫描次数为最大扫描次数为2.p缺点缺点:- 分布不均匀导致错误的候选的比例很大分布不均匀导致错误的候选的比例很大.- 第二次扫描的时候，候选项集的集合很大第二次扫描的时候，候选项集的集合很大.135数据并行数据并行p基于 Apriorip不同的技术:- 数据并行化数据并行化- 候选并行化候选并行化p数据并行- 数据分割数据分割- 计数分配算法（计数分配算法（CDA）p任务并行- 数据和候选分割数据和候选分割- 数据分配算法（数据分配算法（DDA）136 (CDA)1.将事务数据库划分成多个分区.2.在每个分区并行技术3. C
32、1 = 大小为1的单个项集集合;4. 计数 C1;5. 将计数传播到其他处理器上;6. 计算大小为1的全局频繁项集, L1;7. i = 1; 8. Repeat9. i = i + 1;10. Ci = Apriori-Gen(Li-1);11. Count Ci;12.将计数传播到其他处理器上;13. 计算大小为i的全局频繁项集, Li;14. until 直到没有新的候选项目集出现;137CDA Example138(DDA)1.将数据划分为p个区域.2.在每个分区并行处理3. 计算当前数据分区中大小为 1 的本地候选项集计数;4. 将本地数据分区发送到其他处理器上;5. 确定大小为 1
33、 本地候选项集在全局数据库上的计数;6. 确定大小为1的本地频繁项集; 7. 将频繁项集发送到所有分区;8. 确定 L1;9. i = 1; 10. Repeat11. i = i + 1;12. Ci = Apriori-Gen(Li-1);13. 确定大小为 i 本地候选项集在全局数据库上的计数;14. 找出并发送 Li;15. until 直到没有新的频繁项集出现;139DDA Example140方法比较方法比较p目标p类型p数据类型p数据源p技术p项目集策略和数据结构p事务策略和数据结构p优化p架构p并行策略141关联规则算法比较关联规则算法比较142增量规则增量规则p为动态数据库创
34、建关联规则.p问题: 当今所有算法都假定使用静态数据库p目标: - 已知数据库已知数据库 D的大数据集的大数据集- 找出数据库找出数据库 D D D D的大数据集的大数据集p必须在一个数据库中为大数据集 D or D Dp保存 Li和他的计数143关联规则概要关联规则概要p关联规则在非购物篮领域中使用- 预测预测 (短信路由事故短信路由事故)- Web 挖掘挖掘p关联规则有着很多不用的类型- 时序关联时序关联- 空间关联空间关联- 因果关联因果关联144高级关联规则技术高级关联规则技术p泛化关联规则p多层次关联规则p数量关联规则p使用多个最小支持度p相关规则145度量规则的质量度量规则的质量p支持度p置信度p兴趣度p信任度p卡方检验
