数据挖掘算法介绍资料

职业教育

em

KNN贝叶斯阴极射线管

Adaboost Pagerank Apriori聚类算法分层聚类k均值聚类

基于密度的聚类(DBSCAN )模糊聚类(FCM )。两阶段聚类Kohonen网络聚类平衡数据——SMOTE算法分类算法KNN算法

决策树(C5.0，CART ) )。人工神经网络随机森林

支持向量机(SVM )基于密度的聚类

基于 DBSCAN——高密度连通区的聚类 OPTICS——通过点排序识别簇结构基于 DENCLUE——密度分布函数的聚类DBSCAN聚类 DBSCAN聚类认为，在整个样本空间中，目标类聚类是一组密集的样本点于是，这些稠密采样点被低密度区域(噪声)划分，算法的目的是是过滤低密度区域，发现密集的样点。 DBSCAN是一种基于高密度连通区域的聚类算法，将聚类定义为高密度度连接的点的最大集合。 它本身对噪声不敏感，可以是任意形式的集群。DBSCAN的特征找到任意形式的聚类处理噪音

一次扫描

密度参数作为结束条件是必要的基本概念

(1) e近邻)给定对象的半径在e内的区域称为该对象的e近邻(2)核对象：一个对象e附近内的样本点数在事以上时先给定的最小样本点数MinPts将该对象称为核心对象)3)直接密度可达)给定某个对象集合d，p在q的e附近时其中，在q为中心对象的情况下，对象p在从对象q出发时直接紧密达到目的。基本概念

)4)密度可达)存在对象链时

对于Eps和MinPts可以直接达到密度

在一些情况下，对象p可以从对象q获得关于Eps和MinPts的密度(可感知)。

)5)存在密度相连的)对象od时，将对象p和q都从o中闭合在能够达成Eps和MinPts的密度的情况下，对象p到q为Eps和MinPts密度相连演算法

)1)发现可以对数据集中的任意点p实现其所有直接密度，p是中心点或边缘点或噪声点)重复上述步骤，标记所有的点。(3)聚类：消除噪声点

根据能否达到密度或密度连接，使距离小于eps的核心点连在一个班将所有边缘点依次分配给对应的核心点类两阶段聚类两阶段聚类： Chiu，2001年birch (均衡性

reducingandclusteringusinghierarchies (基于算法提出是改善算法。特点：

算法特别适合于大数据集的聚类研究实现两级数据聚类同时处理数值型聚类变量和分型聚类变量根据一定准则确定聚类数诊断样本中的离群点和噪声数据数值型——欧元距离数值分类类型——对数似然距离二阶段聚类——预聚类

一个聚类特征CF是一个三元组(n，LS，SS )，n是聚类中的点的数量，LS是n个点线性和，SS是n个点的平方和。二阶段聚类——预聚类创建聚类过程：树

(1)将所有数据视为大分类，统计量存在于根节点2 )读取一个采样点，从CF树的根节点开始，读取节点的统计量计算数据和中间节点的对数似然距离。 沿着对数从似然距离最小的中间节点开始依次向下选择到叶节点的路径(3)计算与部分树的所有叶节点)子类)的对数似然距离，找到最近的叶节点二阶段聚类——预聚类预聚类过程

)1)如果最近的距离小于某个阈值，则用对应的叶子连接数据点击“吸收”； 否则，该数据将“开辟”新的叶节点。重新计算叶节点和所有对应父节点的聚集统计量)叶节点足够大时，再分裂为两个叶节点)3)当叶节点数达到允许的最大聚类数时，适当增加重建阈值，得到小的CF树

)4)重复上述过程，直到所有数据都被分配给某个叶节点子类(最多两阶段聚类——聚类

(1)聚类过程：分析对象是通过先验聚类形成的紧密区域(2)方法：分层聚类法

)3)分阶段将许多小分类合并为较少的大分类，再合并较少的大分类变成更少更大的范畴，最终将更大的范畴合并成一个大范畴，成为一个整体个人不断“凝聚”的过程两阶段簇——簇数的确定

第一阶段：基于BIC，确定大致聚类数

DBIC(j ) DBIC(j ) BIC ) j1 ) )。(1) ) ) )。（）（）1

数据库

dBIC JR J=找到r1(j )并取最小值

(模型规定r1(j )小于0.04 )j是簇数的“粗略”估计，即，BIC减少幅度最小的j两阶段簇——簇数的确定第二阶段：“粗略”估计j的修正

在2、3、4、…、j中选择。 只基于类间对数似然距离，不考虑模式类型复杂度（）（）（）

最小1号闵2=jj德c德cR J

j类时的最小对数似然距离d (4 )4) ) )。d (3 )3) )。d (

2 ) d (5 ) ) )。

计算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个约束式的拉格朗日乘数。这里，m[1，]是加权指数，是第I个聚类中心和第j个数据欧几里得距离。 |k|ij i jd=x

导出所有的输入参数，使公式(2)达到最小。解如下。(4) ) )。(5) ) )。

这里，m[1，]是加权指数，是第I个聚类中心和第j个数据欧几里得距离。 |k|ij i jd=x

质心的定义类似于传统质心的定义，不同之处在于考虑了所有方面各点对重心的贡献要根据隶属度加权。FCM算法的实现

• step1)初始化集群中心，用值为0，1之间的随机数进行初始化属于矩阵u，满足式(1)的限制条件。

• step2)使用公式(4)计算k个集群中心ki，i=1，k。根据• step3(式)2)计算目标函数。

职教mooc

群集中的主要问题：

如何衡量数据点之间的“亲疏度”用什么方法实施聚类

Kohonen网络的基本战略如下。第一，采用欧氏距离作为数据“亲疏度”的测度第二：模拟人脑神经细胞机制

基于竞争“赢”的聚类过程实现Kohonen网络集群——拓扑结构

Kohonen网络双层、前馈式、全连接的拓扑结构输入节点的数量取决于集群变量的数量输出节点的数量为簇数

Kohonen网络群集——群集过程(爱丽丝示例) )。输入等级输出图层(，) )

i i1 i 2 i3 i 4x x x x x欧仪式距离离开

需要事先确定簇数输入变量的数量

Kohonen网络聚类——聚类过程输入等级输出图层(，) )

i i1 i 2 i3 i 4x x x x x

(，) w1=w1 1 w1 2 w1 3 w1 4 w11 w12w13w14Kohonen网络聚类——聚类过程输入等级输出图层(，) )

i i1 i 2 i3 i 4x x x x x

(，) w1=w1 1 w1 2 w1 3 w1 4 w11w12w13 w14扣多少？Kohonen网络聚类——聚类过程输入等级

输出图层(，) )

i i1 i 2 i3 i 4x x x x xw11w12w13 w14把谁推向远方？Kohonen网络聚类——聚类过程扣多少？

胜利者节点的权重调整如下。式中，是时刻t的学习率。把谁推向远方？ ——将胜利节点的邻点推向远方

相邻节点：与之间的距离在指定范围内的所有输出节点均被视为相邻节点。针对相邻点的权重调整的计算方法如下。

式中为核心函数，反映了时刻t与相邻节点之间的距离的侧面。在clementine中，切比雪夫距离：也就是说，将各个维度的距离的最大值作为距离的测度。w(t1 ) w ) t ) t ) [x ) t ) w ) t]C

=CC

是w(t )C

(t ) ) )。是w(t )C是w(t )j

w(t1 ) w ) t ) h ) t ) [x ) t ) w ) t]j=jJCj

是h(t )

我是JCw(t )我是jw(t )C

h(t ) max ) w ) t ) w ) t ) )日本铁路公司=

i j i c

平衡数据——基于SMOTE算法

欠采样：通过去除训练数据的许多分类中的样本数量而变平平衡数据的目的。

过采样：形成新的少量分类样本，达到平衡数据的目的。SMOTE算法的主要思想是在几个位置相近的少数类样本中插入新样品以平衡样品。 SMOTE算法的特点是不存在添加新的代替用随机过采样法简单复制样本的情况的样品，所以可以在一定程度上避免过度拟合。假设有少数类的样本。 对于每个示例x，查找其k个少数类的最近邻示例。从k个最近邻样本中随机选择n个样本，表示为y1、y2、y3、 yn。 在少数班级里在样本x和yj之间进行随机线性插值，构造新的少数类样本pj。pj=xr and (0，1 ) * ) yjx )，j=1，2，n此处，rand [ 0，1 ]表示区间[ 0，1 ]内的一个随机数。I

x4x3x2x1x1x2x

3x4x

KNN算法

基本原理：针对要分类的数据对象x，从训练数据集中找到对于最接近空间距离(欧式距离)的k个点，取该k个点的最频值类将作为此数据点的类分配给此新对象。问题：

)1)你怎么选择k？ k=1？ k=n？)2)维度灾害？选择k

(1)误差平衡法)选定测试集，k从小到大逐渐增加计算测试误差，绘制k和测试误差图表，从中确定测试错误差异最小且适度的k值。)2)交叉验证)小数据集维灾难

增加变量的维度会导致数据稀疏，从而导致所有估计点附近的真实密度有很大的偏差。 所以KNN适合低维问题。决策树——C5.0根节点

叶节点

中间节点2叉树和多叉子树决策树——C5.0x1x2

2 5 854

决策树——C5.0决策树长大

差异显著减少：在分组样本中输出变量取值差异是否随决策树的生长而显著减少。

人力资源属于什么学科门类

决策树剪枝预裁剪：

1 :预先指定决策树生长的最大深度2 )预先指定样本量的最小值后裁剪：

使决策树充分生长，计算决策树的预测误差，如果误差高于预定值如果不好的话，就必须停止建设。 否则可以继续修剪。决策树——C5.0 C5.0用于创建多个叉的分类树，输入变量必须是分类型或数值类型，输出变量类型不同。 以信息收益率为基准决定决策树划分寻找分支准则、最佳分组变量和分割点。CART可以创建分类数和回归树，但可以创建CART建立二叉树，采用GINI系数和方差来确定最佳分组变量和分切点的根据。 CHAID的输入变量和输出变量可以是分型也可以是数值型，CHAID可以做多叉树。 从统计显着性检验的角度决定现在的最佳性对变量和分割点进行分组。 QUEST的输入变量可以是分型也可以是数值型，输出变量是类型变量只能创建二叉树。

C5.0——如何从众多输入变量中选择当前最佳的组变量？信息熵：信息量的数学期望是信源发布信息之前的平均不确定性性也称为先验熵。后验熵：信号u的概率分布p(u )是已知的，并且接收信号V=vj并发出信号的概率分布为p(u|VJ )，源的平均不确定性：信息增益：信息消除随机不确定性的程度信息收益率：

(log ) ) )。（）1

() ) log 2 2 iIIII

P u P u普uentu=pu=

p(UI )差越小，信息熵越大，平均不确定性越大| ) log(|) ) ) ) ) ) )。(|) )。1

(|)|) log 2 2 i jIi jIj

j i j

P u v P u v普华永道entuv=puv=

gains(u，v )=Ent(U ) u ) ent ) u|v ) ) ) ) ) ) ) ) ) gains(u，v ) ) ) ) ) ) ) ) ) ) ) gains(u，v ) )gainsr(u，v )=Gain(U ) u，v )/Ent(V ) v ) ) ) ) )。C5.0——如何从分组变量的许多值中找到最佳分割点？类型分组变量：有k个类别，将样本分成k组，形成树k个分支

数值型分组变量：以将MDLP分为箱子得到的最小分组限制值为界，将小于组限制的样本分成一组，大的分成另一组，形成两个个枝人工神经网络

人工神经网络(ANN )是人脑的抽象计算模型，一般由是模拟人脑思维的计算机建模方式。

和人脑一样，人工神经网络通过相互连接的神经元，也称为场所整理单元结构。 如果把人工神经网络看作一个图，处理单元就会成为节点。 节点之间的连接称为边缘，表示各节点之间的关联性、关联性的强弱体现在边的权重上。神经元连接

wi:权重

人工神经网络的划分拓扑结构

1:2层神经网络2 :三层神经网络3 )多层神经网络连接方式1 )前馈式神经网络

单向连接，上级节点的输出是下级节点的输入。2 )反馈式神经网络除单向连接外，输出节点的输出是输入节点的输入。人工神经网络——节点加法器：输入到自身的线性组合激活函数：

将加法器结果映射到一定取值范围的jnI

U j=Wij X i=1（）j

U jY=f

0(0) )。1(0) )。（）=jjjuu

自由贸易协定

1(0) )。1(0) )。（）

=jjjuu

自由贸易协定U jje富=11

（）j

juujee富=11

（）

人工神经网络的建模步骤数据准备网络结构的决定确定网络权重数据准备

1 )数值型变量的标准化处理[ 0，1 ]是一种极差的方法2 :类型变量采用虚拟变量，对应输入节点

克服虚拟变量过多输入节点的问题：类另一个二进制码log(1) n=2

K

例如4、5、6、7个类别的分类变更量只需要三个变量好的网络结构的决定

根据隐藏层的数量和各隐藏层中隐藏节点的数量来决定复杂度网络结构在模型建立之前不一定完全确定。经验值法动态调整法

网络权重的确定过程

初始化网络权重： [-0.5，0.5 ]计算各节点加法器和激活函数，得到分类预测值

将预测值与实际值进行比较，根据误差值重新调整各网络的权重返回步骤2，直到预测误差小于指定的或达到指定的重复次数为止数量，达到指定的运行时，或者参数的最大变化值小于指一定的值随机森林

算法思想：每次随机选取几个特征，独立建树，反复个进程确保每次创建树时变量选择的可能性都是一致的制作许多独立的树，最终的分类结果由这些树制作共同决定。错误：

预测误差取决于森林中每棵树的分类效果、树之间的相关性性和强度。 相关越大，预测误差越大，相关可能越小，预测误差上限越小，强度越大，预测误差越小。 为了分组类器要达到较好的泛化效果，应尽量加大单树效应，减少点数类树之间的关联性。* 2 2

PE(1s )/S随机森林原始输入(ri ) )。

F=1和F=2以上的f的效果大致相同。随机合并(forest-RC ) )。

为了减少在子树中看到的依赖关系，考虑用几个新的变量替换原来的变量来生成子树。 每次在生成子树之前，确定派生变量由l个原始变量的线性组合生成，随机选择l个组联合变量随机分配在[-1，1 ]中选择的权重系数，生成新的组合变量。这样选择f个线性组合变量，从f个变量中按照信息削减最快的原则每次进行选择选择最佳的作为分裂变量进行分割。根据经验，在Forest-RI中一般设F=1或F=2； 在组合ForestRC中，可以取稍大的f，但一般不需要太大支持向量机(SVM )

支持矢量分类机(SVC )

用于研究输入变量和二分型输出变量的关系和预测。支持向量回归机(SVR )用于研究输入变量和数值型输出变量的关系和预测。支持向量机支持向量机

支持向量分类的思路：找出相互平行、间隔最大、属于不使用类别的两个的采样点正确分离的边界位于两边界的中间位置，与之平行的超平面最大边界超平面是最终解。支持向量机2

1 1 z x=非线性SVM2

2 2 z x=