数据挖掘算法介绍

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