数据挖掘算法介绍幻灯片.ppt

数据挖掘算法介绍数据挖掘算法介绍第1页，共52页，编辑于2022年，星期六数据挖掘十大经典算法数据挖掘十大经典算法K-MEANSC4.5SVMEMKnn贝叶斯CARTAdaboostPagerankApriori第2页，共52页，编辑于2022年，星期六聚类算法聚类算法 层次聚类 K-means聚类 基于密度的聚类(DBSCAN)模糊聚类（FCM）两步聚类 Kohonen网络聚类平衡数据平衡数据SMOTESMOTE算法算法分类算法分类算法 KNN算法 决策树（C5.0,CART）人工神经网络 随机森林 支持向量机（SVM）第3页，共52页，编辑于2022年，星期六基于密度的聚类基于密度的聚类DBSCAN基于高密度连通区域的聚类OPTICS通过点排序识别聚类结构DENCLUE基于密度分布函数的聚类第4页，共52页，编辑于2022年，星期六DBSCANDBSCAN聚类聚类DBSCAN聚类认为，在整个样本空间中，目标类簇是由一群稠密样本点构成，这些稠密样本点被低密度区域（噪声）分割，而算法的目的就是要过滤低密度区域，发现稠密样本点。DBSCAN是一种基于高密度联通区域的聚类算法，它将类簇定义为高密度相连点的最大集合。它本身对噪声不敏感，并且能发现任意形状的类簇。Clusters第5页，共52页，编辑于2022年，星期六DBSCANDBSCAN特点特点发现任意形状的聚类处理噪音一遍扫描需要密度参数作为终止条件第6页，共52页，编辑于2022年，星期六基本概念基本概念（1）E邻域：给定对象半径为E内的区域称为该对象的E邻域（2）核对象：如果一个对象E邻域内的样本点数大于等于事先给定的最小样本点数MinPts，则称该对象为核对象（3）直接密度可达：给定一个对象集合D，如果p在q的E邻域内，而q是一个核心对象，则称对象p从对象q出发时是直接密度可达。第7页，共52页，编辑于2022年，星期六基本概念基本概念（4）密度可达：如果存在一个对象链 对于 是从 关于Eps和MinPts直接密度可达的，则对象p是从对象q关于Eps和MinPts密度可达的(density-reachable)。（5）密度相连：如果存在对象OD，使对象p和q都是从O关于Eps和MinPts密度可达的，那么对象p到q是关于Eps和MinPts密度相连的第8页，共52页，编辑于2022年，星期六算法算法（1）对数据集中的任一点p找到它的所有直接密度可达，标记p为核心点或边缘点或噪声点（2）重复上述步骤，标记出所有点。（3）聚类：剔除噪声点依据密度可达或密度相连，将距离小于eps的核心点连接成一个类将所有边缘点依次分派到相应核心点的类中第9页，共52页，编辑于2022年，星期六两步聚类两步聚类两两 步步 聚聚 类类：ChiuChiu，20012001年年 在在BIRCHBIRCH（Balanced Balanced Iterative Iterative Reducing Reducing and and Clustering using HierarchiesClustering using Hierarchies）算法基础上提出的一种改进算法。）算法基础上提出的一种改进算法。特点：特点：算法尤其适合于大型数据集的聚类研究算法尤其适合于大型数据集的聚类研究 通过两步实现数据聚类通过两步实现数据聚类 同时处理数值型聚类变量和分类型聚类变量同时处理数值型聚类变量和分类型聚类变量 根据一定准则确定聚类数目根据一定准则确定聚类数目 诊断样本中的离群点和噪声数据诊断样本中的离群点和噪声数据 数值型数值型欧式距离欧式距离 数值型数值型+分类型分类型对数似然距离对数似然距离第10页，共52页，编辑于2022年，星期六两步聚类两步聚类预聚类预聚类一个聚类特征CF是一个三元组（N,LS,SS）,N是簇中的点的数目，LS是N个点的线性和，SS是N个点的平方和。第11页，共52页，编辑于2022年，星期六两步聚类两步聚类预聚类预聚类预聚类过程预聚类过程:建立建立CFCF树树 (1)(1)视所有数据为大类，统计量存在根结点中视所有数据为大类，统计量存在根结点中 (2)(2)读入一个样本点，从读入一个样本点，从CFCF树的根结点开始，利用结点的树的根结点开始，利用结点的 统计量，计算数据与中间结点的对数似然距离。沿对数统计量，计算数据与中间结点的对数似然距离。沿对数 似然距离最小的中间结点依次向下选择路径直到叶结点似然距离最小的中间结点依次向下选择路径直到叶结点 (3)(3)计算与子树中所有叶结点（子类）的对数似然距离，计算与子树中所有叶结点（子类）的对数似然距离，找到距离最近的叶结点找到距离最近的叶结点第12页，共52页，编辑于2022年，星期六两步聚类两步聚类预聚类预聚类预聚类过程预聚类过程 (1)(1)如果最近距离小于一定阈值，则该数据被相应的叶结如果最近距离小于一定阈值，则该数据被相应的叶结 点点“吸收吸收”；否则，该数据将；否则，该数据将“开辟开辟”一个新的叶结点。一个新的叶结点。重新计算叶结点和相应所有父结点的汇总统计量重新计算叶结点和相应所有父结点的汇总统计量 (2)(2)叶结点足够大时应再分裂成两个叶结点叶结点足够大时应再分裂成两个叶结点 (3)(3)叶结点个数达到允许的最大聚类数目时，应适当增加叶结点个数达到允许的最大聚类数目时，应适当增加 阈值重新建树，以得到一棵较小的阈值重新建树，以得到一棵较小的CFCF树树 (4)(4)重复上述过程，直到所有数据均被分配到某个叶结点重复上述过程，直到所有数据均被分配到某个叶结点 （子类）为止（子类）为止第13页，共52页，编辑于2022年，星期六两步聚类两步聚类聚类聚类(1)(1)聚类过程：分析对象是预聚类所形成的稠密区域聚类过程：分析对象是预聚类所形成的稠密区域(2)(2)方法：层次聚类法方法：层次聚类法(3)(3)逐逐步步将将较较多多的的小小类类合合并并为为较较少少的的大大类类，再再将将较较少少的的大大类类合合并并成成更更少少的的更更大大类类，最最终终将将更更大大类类的的合合并并成成一一个个大大类类，是是一一个个类类不不断断“凝聚凝聚”的过程的过程第14页，共52页，编辑于2022年，星期六两步聚类两步聚类聚类数目的确定聚类数目的确定第一阶段：依据第一阶段：依据BICBIC，确定粗略的聚类数，确定粗略的聚类数找到找到R1(J)R1(J)取最小值取最小值（ModelerModeler规定规定R1(J)R1(J)应小于应小于0.040.04）的的J J为聚类数目的为聚类数目的“粗略粗略”估计，即估计，即BICBIC减小幅减小幅度最小的度最小的J J第15页，共52页，编辑于2022年，星期六两步聚类两步聚类聚类数目的确定聚类数目的确定第二阶段：对第二阶段：对“粗略粗略”估计值估计值J J的修正的修正2,3,4,J2,3,4,J中选择。仅依据类间对数似然距离，不考虑模型复杂度中选择。仅依据类间对数似然距离，不考虑模型复杂度J J类时的最小类时的最小对数似然距离对数似然距离d(4)d(3)d(2)d(5)计算计算R R2 2(J-1)(J-1)、R R2 2(J-2)(J-2)到到R R2 2(2)(2)，反映，反映J-1J-1类的类内差是类的类内差是J J类的倍数。类的倍数。ModelerModeler找到最大值找到最大值,若最大值是次大若最大值是次大值的值的1.151.15倍以上，则最大值对应的倍以上，则最大值对应的J J为为最终聚类数最终聚类数R R2 2(J)J)是聚类合并过程中类间差异最是聚类合并过程中类间差异最小值变化的相对指标小值变化的相对指标第16页，共52页，编辑于2022年，星期六模糊聚类模糊聚类FCMFCMFCM与HCM的主要区别在于FCM用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U允许有取值在(0,1)间的元素，满足第17页，共52页，编辑于2022年，星期六目标函数：SSE=(2)拉格朗日乘数法这里j，j=1到n，是(1)式的n个约束式的拉格朗日乘子。其中，m1，+)是一个加权指数，为第I个聚类中心与第j个数据间的欧几里德距离。第18页，共52页，编辑于2022年，星期六对所有输入参量求导，使式(2)达到最小。得到解为：（4）（5）其中，m1，+)是一个加权指数，为第I个聚类中心与第j个数据间的欧几里德距离。模糊质心的定义类似于传统的质心定义，不同之处在于所有点都考虑，并且每个点对质心的贡献要根据它的隶属度加权。第19页，共52页，编辑于2022年，星期六FCMFCM算法实现算法实现 step1：初始化聚类中心，用值在0，1间的随机数初始化 隶属矩阵U，使其满足式(1)中的约束条件。step2：用式(4)计算k个聚类中心 ki，i=1,k。step3：根据式(2)计算目标函数。如果它小于某个确定 的阈值，或它相对上次目标函数值的改变量小于某个阈 值，则算法停止。step4：用（5）计算新的U矩阵。返回步骤2。FCM算法需要设置两个参数：一个是聚类数目k，一个是参数m。第20页，共52页，编辑于2022年，星期六KohonenKohonen网络聚类网络聚类概述概述聚类中的主要问题：如何测度数据点之间的“亲疏程度”怎样的方式实施聚类Kohonen网络的基本策略是：第一：采用欧氏距离作为数据“亲疏程度”的测度 第二：模拟人脑神经细胞的机理通过竞争“获胜”实现聚类过程 第21页，共52页，编辑于2022年，星期六KohonenKohonen网络聚类网络聚类拓扑结构拓扑结构Kohonen网络两层、前馈式、全连接的拓扑结构两层、前馈式、全连接的拓扑结构输入节点的个数取决于聚类变量的个数输入节点的个数取决于聚类变量的个数输出节点的个数即为聚类数目输出节点的个数即为聚类数目第22页，共52页，编辑于2022年，星期六KohonenKohonen网络聚类网络聚类聚类过程聚类过程(鸢尾花为例鸢尾花为例)输入层输入层输出层输出层欧欧式式距距离离需提前确定聚类数目需提前确定聚类数目输入变量个数输入变量个数第23页，共52页，编辑于2022年，星期六KohonenKohonen网络聚类网络聚类聚类过程聚类过程输入层输入层输出层输出层第24页，共52页，编辑于2022年，星期六KohonenKohonen网络聚类网络聚类聚类过程聚类过程输入层输入层输出层输出层拉动多少？拉动多少？第25页，共52页，编辑于2022年，星期六KohonenKohonen网络聚类网络聚类聚类过程聚类过程输入层输入层输出层输出层将谁推向远方？将谁推向远方？第26页，共52页，编辑于2022年，星期六KohonenKohonen网络聚类网络聚类聚类过程聚类过程拉动多少？对获胜节点 的权值调整为：式中，为t时刻的学习率。将谁推向远方？将获胜节点的邻接点推向远方 邻接点：与 的距离在指定范围内的输出节点都视为邻接点。对邻接点 的权值调整的计算方法是：式中 为核函数，反映的是t时刻邻接节点 与 之间距离的侧度。clementine中采用的是切比雪夫距离，即：即以单个维的距离最大值作为距离的测度。第27页，共52页，编辑于2022年，星期六平衡数据平衡数据基于基于SMOTESMOTE算法算法欠抽样：通过去除训练数据多数分类中的样本数从而达到平衡数据的目的。过抽样：形成新的少量分类样本从而达到平衡数据的目的。SMOTE算法主要思想是：通过在一些位置相近的少数类样本中插入新样本以期达到平衡样本的目的。SMOTE算法的特点是不按照随机过抽样方法简单的复制样本，而是增加新的并不存在的样本，因此在一定程度上可以避免过度拟合。第28页，共52页，编辑于2022年，星期六 假设有少数类样本，每一个样本x，搜索其K个少数类最近邻样本，在k个最近邻样本中随机选择N个样本，记为y1,y2,y3,.yn。在少数类样本x与yj之间进行随机线性插值，构造新的少数类样本pj。其中，rand(0,1)表示区间（0，1）内的一个随机数。第29页，共52页，编辑于2022年，星期六KNNKNN算法算法基本原理：对一个待分类的数据对象x，从训练数据集中找出与之空间距离（欧式距离）最近的k个点，取这k个点的众数类作为该数据点的类赋给这个新对象。问题：（1）如何选取k？k=1?k=n?（2）维度灾难？第30页，共52页，编辑于2022年，星期六k的选取（1）误差平衡法：选定测试集，将k由小变大逐渐递增，计算测试误差，制作k与测试误差的曲线图，从中确定使测试误差最小且适中的k值。（2）交叉验证：小数据集维度灾难增加变量的维度，会使数据变得越来越稀疏，这会导致每一点附近的真实密度估计出现较大偏差。所以KNN更适用于低维问题。第31页，共52页，编辑于2022年，星期六决策树决策树C5.0C5.0根节点根节点叶节点叶节点中间节点中间节点2 2叉树和多叉叉树和多叉树树第32页，共52页，编辑于2022年，星期六决策树决策树C5.0C5.0 x1x225854第33页，共52页，编辑于2022年，星期六决策树决策树C5.0C5.0决策树生长决策树生长差异显著下降：分组样本中输出变量取值的差异性是否随决策树的生长而显著减少。第一，如何从众多的输入变量中选择一个当前最佳的分组变量？第二，如何从分组变量的众多取值中找到一个最佳的分割点？决策树剪枝决策树剪枝预修剪：预修剪：1：预先指定决策树生长的最大深度2：预先指定样本量的最小值后修剪：后修剪：允许决策树充分生长，计算决策子树的预测误差，当误差高于某预定误差则应停止修建，否则可继续修剪。第34页，共52页，编辑于2022年，星期六决策树决策树C5.0C5.0C5.0用于建立多叉的分类树，要求输入变量是分类型或数值型，输出变量是分类型。以信息增益率为标准确定决策树分支准则，寻找最佳分组变量和分割点。CART既可以建立分类数也可以建立回归树，但是CART只能建立二叉树，采用GINI系数和方差作为确定最佳分组变量和分割点的依据。CHAID的输入变量和输出变量可以是分类型也可以是数值型，CHAID能够建立多叉树。从统计显著性检验角度确定当前最佳分组变量和分割点。QUEST的输入变量可以是分类型也可以是数值型，输出变量为分类型变量，只能建立二叉树。第35页，共52页，编辑于2022年，星期六C5.0C5.0如何从众多的输入变量中选择一个当前最佳的分组变量？如何从众多的输入变量中选择一个当前最佳的分组变量？信息熵：信息量的数学期望，是信源发出信息前的平均不确定性，也称先验熵。后验熵：已知信号U的概率分布P(U)且收到信号V=vj，发出信号的概率分布为P(U|vj)，信源的平均不确定性：信息增益：信息消除随机不确定性的程度信息增益率：P(ui)P(ui)差别越小，信息熵越大，平均不确定性越大差别越小，信息熵越大，平均不确定性越大第36页，共52页，编辑于2022年，星期六C5.0C5.0如何从分组变量的众多取值中找到最佳的分割点？如何从分组变量的众多取值中找到最佳的分割点？分分类类型型分分组组变变量量：有有k个个类类别别，将将样样本本分分成成k组组，形形成成树树的的k个分支个分支数数值值型型分分组组变变量量：以以MDLPMDLP分分箱箱所所得得的的最最小小组组限限值值为为界界，将将小小于于组组限限的的样样本本划划为为一一组组，大大于于的的划划为为另另一一组组，形形成成两两个个分叉分叉第37页，共52页，编辑于2022年，星期六人工神经网络人工神经网络人工神经网络（ANN）是一种人脑的抽象计算模型，是一种模拟人脑思维的计算机建模方式。与人脑类似，人工神经网络由相互连接的神经元，也称处理单元组成。如果将人工神经网络看作一张图，处理单元成为节点。节点之间的连接称为边，反映了各节点之间的关联性，关联性的强弱体现在边的权值上。神经元神经元连接连接wi:权值权值第38页，共52页，编辑于2022年，星期六人工神经网络的划分人工神经网络的划分拓扑结构 1：两层神经网络 2：三层神经网络 3：多层神经网络连接方式 1：前馈式神经网络 单向连接，上层节点的输出是下层节点的输入。2：反馈式神经网络 除单向连接外，输出节点的输出又作为输入节点的输入。第39页，共52页，编辑于2022年，星期六人工神经网络人工神经网络节点节点第40页，共52页，编辑于2022年，星期六加法器：对自身输入的线性组合加法器：对自身输入的线性组合激活函数：激活函数：把加法器的结果映射到一定的取值范围内把加法器的结果映射到一定的取值范围内第41页，共52页，编辑于2022年，星期六人工神经网络的建模步骤人工神经网络的建模步骤数据准备网络结构的确定确定网络权值第42页，共52页，编辑于2022年，星期六数据准备数据准备1 1：数值型变量的标准化处理：数值型变量的标准化处理 00，11，极差法，极差法2 2：分类型变量：分类型变量n采用哑变量，对应输入节点采用哑变量，对应输入节点n克服哑变量使输入节点过多的问题：对类别的克服哑变量使输入节点过多的问题：对类别的二进制编码二进制编码例：有例：有4 4、5 5、6 6、7 7个个类别的分类变量只需类别的分类变量只需3 3个变量即可个变量即可 第43页，共52页，编辑于2022年，星期六网络结构的确定网络结构的确定隐层层数和各隐层中隐结点的个数决定复杂度隐层层数和各隐层中隐结点的个数决定复杂度网络结构不一定在模型建立之前就完全确定网络结构不一定在模型建立之前就完全确定 经验值法经验值法动态调整法动态调整法第44页，共52页，编辑于2022年，星期六网络权值的确定步骤网络权值的确定步骤初始化网络权值：初始化网络权值：-0.5,0.5-0.5,0.5计算各节点加法器和激活函数，得到分类预测值计算各节点加法器和激活函数，得到分类预测值比较预测值与实际值，根据误差值重新调整各网络权值比较预测值与实际值，根据误差值重新调整各网络权值回回第第二二步步，直直到到预预测测误误差差小小于于指指定定，或或达达到到指指定定迭迭代代次次数数，或或达达到到指指定定的的运运行行时时间间，或或参参数数的的最最大大变变化化值值小小于于指指定值定值第45页，共52页，编辑于2022年，星期六随机森林随机森林算法思想：每次随机选取一些特征，独立建立树，重复这个过程，保证每次建立树时变量选取的可能性一致，如此建立许多彼此独立的树，最终的分类结果由产生的这些树共同决定。误差：预测误差取决于森林中每棵树的分类效果，树之间的相关性和强度。相关性越大，预测误差可能越大，相关性越小，预测误差上界越小；强度越大，预测误差越小。为使组合分类器达到好的泛化效果，应尽量增大单棵树的效果，减少分类树之间的相关性。第46页，共52页，编辑于2022年，星期六随机森林随机森林Forest-RI(random input)F=1和F=2甚至更高的F效果差不多(F为子树变量个数)Forest-RC(random combination)为减少子树见得相关性，考虑用一些新变量替换原始变量产生子树。每次生成子树前，确定衍生变量由L个原始变量线性组合生成，随机选择L个组合变量，随机分配-1，1中选出的权重系数，产生一个新的组合变量，如此选出F个线性组合变量，从F个变量中按照信息缩减最快的原则每次选择出最优的一个作为分裂变量进行拆分。经验指出：Forest-RI中一般取F=1或F=2；对组合Forest-RC，可以取稍大的F，但一般也不必过大第47页，共52页，编辑于2022年，星期六支持向量机支持向量机(SVM)(SVM)支持向量分类机（SVC）用于研究输入变量与二分类型输出变量的关系及预测。支持向量回归机(SVR)用于研究输入变量与数值型输出变量的关系及预测。第48页，共52页，编辑于2022年，星期六支持向量机支持向量机第49页，共52页，编辑于2022年，星期六支持向量机支持向量机max支持向量分类的思想：找到两个互相平行且间距最大，并能将属于不用类别的样本点正确分开的边界，位于两边界中间位置并与之平行的超平面，成为最大边界超平面，即为最终解。第50页，共52页，编辑于2022年，星期六支持向量机支持向量机第51页，共52页，编辑于2022年，星期六非线性非线性SVMSVM第52页，共52页，编辑于2022年，星期六