数据挖掘模型-Models-of-DMPPT格式课件下载.ppt
《数据挖掘模型-Models-of-DMPPT格式课件下载.ppt》由会员分享,可在线阅读,更多相关《数据挖掘模型-Models-of-DMPPT格式课件下载.ppt(178页珍藏版)》请在冰点文库上搜索。
那么这个分割的Gini就是提供最小Ginisplit就被选择作为分割的标准.,21,过拟合问题,剪枝,避免过拟合决策树泛化,22,PruningTree,目的:
消除决策树的过拟合(OverFitting)问题实质:
消除训练集中的异常和噪声两种方法:
先剪枝法(Public算法)后剪枝法(Sprint算法),23,误分类率,24,决策树算法的可伸缩性,ID3、C4.5等算法对规模较小,可以一次放入内存的训练样本集很有效,但实际上数以百万计样本的超大型训练集是常见的,大多数情况下无法把训练样本集全部放入内存,导致这些算法的有效性降低。
因此需要增加可伸缩的方法以节省空间。
IBM的研究人员运用一些特殊数据结构,例如属性表和类表,在1996年提出了一种快速的、可伸缩的SLIQ算法,可以处理离散属性和连续属性。
SLIQ算法首先把训练样本集划分成若干子集,使每一个子样本集都能放入内存,然后对每个子样本集分别构造一棵决策树,再把这些决策树综合,得到最终决策树。
SLIQ算法可以处理大规模的训练样本集,具有较好的伸缩性。
与传统决策树算法相比,减少了运行时间。
SLIQ算法在执行过程中需要随时修改类表,类表常驻内存,而类表的大小会随着训练样本集的增大而增大,因此SLIQ算法对内存容量有一定的要求。
25,常用的决策树算法,ID3,C4.5,C5.0CARTCHAID,26,CART算法,CART算法采用一种二分递归分割的方法,每次都把当前样本集分割为两个子样本集,使生成的决策树的非叶结点都有两个分枝,因此CART算法生成的决策树是结构简单的二叉树。
这种算法选择分枝属性A的判别函数如下:
式中pL和pR分别是属性A的左右分枝的样本数占总体的比例,p(iL)和p(iR)分别表示属性A的左右分枝中样本子集属于类别i的比例,m为分类类别数。
使(A)最大的属性A作为分枝的属性,因为这需要满足下面的条件:
左右分枝样本的数量差不多。
左右分枝的样本集尽量不要属于同一类。
此外,CART算法也使用后剪枝。
在决策树生成过程中,考虑到多展开一层就会有更多信息被发现,CART算法运行到不能再长出分枝为止,从而得到一棵最大的决策树。
然后CART对生成的决策树进行剪枝。
剪枝算法使用独立于训练样本集的测试样本集对子树的分类错误进行计算,找出分类错误最小的子树作为最终的分类模型。
27,神经网络,28,神经网络的组成,神经网络是由许多人工神经元通过一定的互联方式组成。
这些神经元的结构比较简单,但它们复杂的连接(拓扑结构)会形成功能很强的网络。
如下图所示,神经元一般有多个输入x1,xn,这些输入通过组合函数加权求和,然后再利用神经元的激活函数f产生输出y。
神经元之间的连接强度用权值w表示。
神经元的输入和输出之间的关系用函数表示:
其中是神经元的偏置,在网络初始化时赋予小的随机数。
激活函数(activationfunction)常用Sigmoid函数(还有线性函数和双曲正切函数等)。
29,典型的多层前馈神经网络,不同层次神经元之间的连接强度用相应的权wij、wjk表示,这些权在网络初始化时被赋予很小的随机数,例如-0.5到0.5或-1.0到1.0之间的值。
整个信息的处理是单向的,网络没有环形结构。
输入xi直接提供给输入层的神经元,对于输入层的神经元i,它的输出Oi等于输入Ii:
Oi=Ii。
这些神经元的加权和同时提供隐层的神经元,隐层神经元的输出构成输出层神经元的输入,输出层的神经元给定样本的分类或预测。
隐层神经元j的输入是其输入的线性组合:
用激活函数Sigmoid函数作用于隐层的神经元j,j的输出Oj用下式计算:
输出层神经元的输入和输出与隐层神经元的情况类似。
隐层和输出层的非线性激活关系使神经网络可以近似任何函数。
30,BP神经网络的训练
(1),分析业务问题。
选择训练样本集,对其输入值和输出值进行预处理。
依靠经验确定网络的拓扑结构,并对神经元的权值和偏置进行初始化。
利用反向传播等算法训练网络,不断调整网络权值减少预测误差,获得网络的最佳权。
用测试集检验网络的分类或预测质量。
预测未知样本的分类。
BP神经网络是一种监督学习方法,使用反向传播的学习算法:
通过迭代处理一组训练样本,把每个样本的网络输出值Tk与实际值Ok比较,然后按一定的方式调整网络权和神经元的偏置,使得实际值和网络输出值之间的误差平方和最小:
式中sample为样本集。
这种网络权的调整“后向”进行,即由输出层,经由隐层,多次重复训练,直到满足误差要求。
31,BP神经网络的训练
(2),为使ERR最小,可以利用最优化理论的梯度下降法更新网络权值。
通常有两种方法更新权和偏置:
一种是每训练一个样本就更新权和偏置,另一种是在处理训练集中的所有样本之后再更新权和偏置。
这实际上是以wij和wjk为变量的多元函数ERR的最小化问题。
利用梯度下降法,权的更新方式如下:
式中,是学习率,,这个参数可避免陷入局部最小。
学习率太小,会使网络学习速度慢,而太大的学习率可能使学习过程振荡。
通常在网络训练的初期学习率设置大一些,随着训练误差的减少,学习率可逐渐变小。
32,神经网络的应用
(1),在财务方面,神经网络可用来协助投资公司预测普通股的表现、公司的债券等级或公司破产的可能性。
VISA国际公司用神经网络来帮助侦测信用卡欺诈,它监控所有VISA交易并且注意持卡人消费形态的改变。
33,神经网络的应用
(2),股票拐点趋势预测:
利用历史价格数据预测中短期(从2到10或15天)的价格走势。
34,贝叶斯分类器,35,贝叶斯定理,假设X和Y在分类中可以分别表示样本的属性集和类别。
P(X,Y)表示它们的联合概率,p(X|Y)和p(Y|X)表示条件概率,其中是后验概率,而称为Y的先验概率。
X和Y的联合概率和条件概率满足下列关系:
变换后得到,36,朴素贝叶斯分类器,对于属性集,如果之间相互独立,即,有朴素贝叶斯分类器:
其中是常数,先验概率可以通过训练集中每类样本所占的比例估计。
给定,如果要估计测试样本X的分类,由朴素贝叶斯分类器得到y类的后验概率:
只要找出使最大的类别y即可。
37,贝叶斯分类器在供电电容生产中的应用
(1),假设某段时期内某电脑主板制造商所用的供电电容是由三家电容生产厂提供的。
对制造商在这段时期内的业务数据进行抽样,得到下表。
因为三家电容工厂的供电电容在电脑主板生产商的仓库中是均匀混合的,并无明显的区别标志。
现在电脑主板生产商想通过对数据进行分析,解决下面两个问题:
(1)随机地从仓库中取一只供电电容是次品的概率。
(2)从仓库中随机地取一只供电电容,若已知取到的是一只次品,想分析此次品来自哪家工厂的可能性最大。
38,贝叶斯分类器在供电电容生产中的应用
(2),39,贝叶斯分类器在垃圾邮件处理中的应用,贝叶斯分类器是对邮件的内容进行分析,不仅考虑关键词在垃圾邮件中出现的概率,也考虑关键词在正常邮件中的概率。
当一封新的邮件到达时,这封邮件的内容将被分解成字串。
依据数据库中这些词的概率通过公式进行计算,用贝叶斯定理计算出的垃圾邮件可能性高于某个阈值时就判定这封邮件是垃圾邮件。
贝叶斯过滤防范有一定的智能性,通过一定的学习方法可以对数据库词的概率进行更新,可以适应垃圾邮件的变化情况。
40,K-最近邻分类遗传算法粗糙集理论模糊理论,其他分类方法,41,聚类Clustering,42,聚类,-DefinitionofclusteringClusteringisaprocessofpartitioningasetofobjectssuchascustomersintogroupsinwhichtheobjectsinthesamegrouparesimilartoeachotherandtheobjectsindifferentgroupsaredissimilar,accordingtosomesimilaritymeasure.-聚类就是把整个数据分成不同的组,并使组与组之间的差距尽可能大,组内数据的差异尽可能小。
-Clusteringisoftencalledunsupervisedclassification-Clusteringisusedforcustomersegmentation,聚类分析,簇(Cluster):
一个数据对象的集合聚类分析把一个给定的数据对象集合分成不同的簇;
聚类是一种无监督分类法:
没有预先指定的类别;
典型的应用作为一个独立的分析工具,用于了解数据的分布;
作为其它算法的一个数据预处理步骤;
44,CustomerSegmentation,-Customersegmentationisaprocesstodividecustomersintogroupsorsegments.Customersinthesamesegmenthavesimilarneedsorbehaviorssothatsimilarmarketingstrategiesorservicepoliciescanbeappliedtothem.-SegmentationaccordingtosomevariablesE.g.,usecustomertypevariabletodividecustomersintocorporatecustomersandindividualcustomers-SegmentationusingadataminingtechniquesE.g.,aclusteringalgorithmordecisiontreealgorithm,45,发现客户的特征,客户分割(segmentation)是一种发现用户特性的方法。
数据驱动的分割将一个基于数据的客户信息的自然客户分组:
从而给你一个客户信息的概况,这可以直接转化为增加客户的经营策略。
46,与分类的区别,与分类不同,在开始聚集之前用户并不知道要把数据分成几组,也不知分组的具体标准,聚类分析时数据集合的特征是未知的。
聚类根据一定的聚类规则,将具有某种相同特征的数据聚在一起也称为无监督学习。
分类用户则知道数据可分为几类,将要处理的数据按照分类分入不同的类别,也称为有监督学习。
47,聚类问题的数学描述,给定数据集合V,根据数据对象间的相似程度将数据集合分成组,并满足:
则该过程称为聚类。
Ci称为簇。
48,基本概念,ClustercenterClustersizeClusterdensityClusterdescriptions一个好的聚类方法要能产生高质量的聚类结果簇,这些簇要具备以下两个特点:
高的簇内相似性低的簇间相似性,49,聚类需求,可伸缩性能够处理不同类型的属性能发现任意形状的簇在决定输入参数的时候,尽量不需要特定的领域知识;
能够处理噪声和异常对输入数据对象的顺序不敏感能处理高维数据能产生一个好的、能满足用户指定约束的聚类结果结果是可解释的、可理解的和可用的,50,计算对象之间的相异度,通常使用距离来衡量两个对象之间的相异度。
常用的距离度量方法有:
明考斯基距离(Minkowskidistance):
其中i=(xi1,xi2,xip)和j=(xj1,xj2,xjp)是两个p维的数据对象,q是一个正整数。
当q=1时,d称为曼哈坦距离(Manhattandistance),51,SimilarityandDissimilarity,当q=2时,d就成为欧几里德距离:
距离函数有如下特性:
d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)可以根据每个变量的重要性赋予一个权重,52,二元变量,二元变量的可能性表其中每个对象有p个变量,且p=a+b+c+d,Objecti,Objectj,53,二元变量,对称的如果一个二元变量的两个状态是同等价值的,具有相同的权重。
即可以任取其中一种状态编码为1或者0。
对于对称的二元变量,采用简单匹配系数来评价两个对象之间的相异度,54,二元变量,非对称的如果变量的两个状态不是同样重要的,则称该变量是不对称的。
将比较重要通常也是出现概率比较小的状态编码为1,将另一种状态编码为0。
对于非对称的二元变量,采用Jaccard系数来评价两个对象之间的相异度,55,二元变量的相异度计算,gender是一个对称的二元变量其它的都是非对称的二元变量将值Y和P编码为1,值N编码为0,根据Jaccard系数计算得:
56,标称变量(NominalVariables),标称变量是二元变量的推广,它可以具有多于两个的状态,比如变量map_color可以有red,yellow,blue,green四种状态。
有两种计算相异度的方法:
方法1:
简单匹配方法m是匹配的数目,p是全部变量的数目方法2:
使用二元变量为每一个状态创建一个新的二元变量,可以用非对称的二元变量来编码标称变量。
57,序数型变量,一个序数型变量可以是离散的也可以是连续的离散的序数型变量类似于标称变量,除了它的M个状态是以有意义的序列排序的,比如职称。
连续的序数型变量类似于区间标度变量,但是它没有单位,值的相对顺序是必要的,而其实际大小并不重要。
58,聚类算法,K-meansalgorithmsKohonenneuralnetwork(self-organizingmap)Hierarchicalclusteringmethods其他,59,K-均值算法
(1),InputAsetofnumericrecordsAnintegerk1(numberofclusterstobefound).,OutputApartitionofrecordsintokclusters.Eachrecordisidentifiedasoneofthekclusters.,x11,x121x21,x222xn1,xn21,60,K-均值算法过程,61,1.Selectkdistinctrecordsasinitialmeans,eachrepresentingacluster.2.Foreachrecordindata,calculatethesquaredEuclideandistancesbetweenitandthemeans.Assigntherecordtotheclusterwhosemeanisthenearesttotherecord.3.Afterallrecordsareassignedacluster,calculatethenewmeanforeachclusterastheaverageofallrecordsinthecluster.4.Ifthenewmeansequaltothepreviousmeans,stop,otherwise,gotoStep2.,K-均值算法
(2),给定k,从n个对象中任意选择k个对象作为初始聚类中心;
repeat计算每个对象与聚类中心的距离,把它们划到不同的簇;
重新计算每个簇的聚类中心;
until聚类中心不再发生变化,62,实例,63,K-均值算法性质,EfficientinclusteringlargedataSolutiondependsoninitialmeansSensitivetooutliersSphericalclustersNumericdata,64,K-均值算法局限,非球形的簇,65,K-means算法在中药种植区域划分中的应用,无论是种植业还是养殖业,生产都与当地的气候条件关系密切,尤其是中药种植。
中药材的生长发育、产量和品质都与气候息息相关。
以中药材当归为例,对A地区的气候资料进行分析,并参照当归产地B地区的气候资料划分A地区的当归适宜种植区和不适宜种植区,以供引种参考。
当归喜冷凉阴湿气候,怕暑热高温,要求土壤质地疏松,有机质含量高,适宜在高寒阴湿区种植。
据此选择下列因素作为聚类的气候变量:
x1:
年平均气温,x2:
年降水量,x3:
0积温,x4:
7月平均气温,x5:
8月平均气温。
下表给出了B地区所属各气象站多年(1971年至1990年)平均气候资料。
66,B地区气象资料,67,聚类结果,68,k-means算法在安全检测中的应用,应用k-means聚类算法,分析入侵检测模型数据库,自动地分析原有数据,从中挖掘出潜在的模式,预测用户的行为。
下表以目标端口与当前连接相同次数和目标主机不同连接所占百分比作为特征,列出了20条网络访问数据。
其中坐标轴横轴x1为目标端口与当前连接相同的连接次数,纵轴x2表示目标主机不同连接所占百分比。
69,网络访问记录,70,聚类结果,原始数据,聚类结果,71,基于IBMDB2IntelligentMiner的数据聚类,顾客数据,聚类结果,72,k-modes算法,k-modes算法把k-means算法扩展到可分类数据,定义了新的度量可分类数据相异度的距离公式,并给出相应的更新聚类中心的方式,能够迅速处理可分类型数据。
k-modes算法根据可分类属性值出现的频率更新聚类中心,聚类中出现频率最高的属性值被选为聚类中心,即modes(类模式)。
k-modes算法改变了k-means算法的相异度测量方法,用一个简单的相异度测量对数据进行聚类。
假设X,Y是数据集中的两个对象,它们用m维属性描述,则这两个对象之间的相异度为:
73,k-modes算法过程,k-modes算法不断更新modes,使得所有对象与其最近modes的相异度总和最小:
首先计算每一簇在某一属性值的对象所占百分数。
然后,取每个簇中频率最大的一个属性值作为类模式Q。
分别对每个属性进行上述计算,最后得到类模式Q,即初始聚类中心。
k-modes算法与k-means的步骤类似:
预先定义好k类,确定各个类的初始类模式Q。
根据类模式Q把每个对象赋给最近邻的类,然后更新类模式Q。
不断重复,直到不再发生变化为止。
74,k-prototypes算法,在实际应用中,数据可能是数值型的,同时也有可分类型的。
k-prototypes算法综合了k-means和k-modes算法,采用新的距离度量方法,能够快速处理混合类型数据集的聚类问题。
k-prototypes算法的聚类中心由数值型数据的聚类中心和可分类数据的聚类中心两部分加权组成,其中数值型属性的聚类中心和k-means算法类似,通过计算数值型属性的平均值得到。
而可分类型属性的中心采用类似k-modes算法聚类中心的更新方式,通过计算可分类属性值出现的频率确定。
75,其他聚类方法,除了以上基于划分的聚类算法外,还有基于层次的聚类算法。
层次聚类(hierarchicalclustering)方法把数据组织成若干簇,并形成一个相应的树状图进行聚类。
基于划分的聚类和基于层次的聚类还有其他实现方法,例如基于密度的聚类、基于网格的聚类、基于模型的聚类以及模糊聚类等,每种方法都有各自的优缺点,适用范围也有限。
选择哪种聚类方法,需要考虑实际的应用需求、簇的类型与特征、数据的特性、数据质量、数据集的规模(样本个数、样本属性个数)等因素。
76,基于密度的聚类,基于密度的聚类方法与k-means算法使用簇的中心不同,它使用密度的概念。
这种聚类方法根据样本点周围的密度不断增长聚类,这就克服了基于距离的算法只能发现凸形分布数据聚类的缺点。
基于密度的聚类方法首先计算一个区域中的点的密度,如果大于某个阈值就把它添加到相近的聚类中去,主要算法包括DBSCAN