《数据仓库与数据挖掘》实验二 聚类分实验报告8.docVIP

实验二、聚类分析 通过计算机编程实现并验证谱系聚类法 1）用Matlab实现谱系聚类算法，并对给定的样本集进行分类； 2）通过改变实验参数，观察和分析影响谱系聚类算法的分类结果与收敛速度的因素；人类认识世界往往首先将被认识的对象进行分类，聚类分析是研究分类问题的多元数据分析方法，是数值分类学中的一支。多元数据形成数据矩阵，见下表1。在数据矩阵中，共有n个样品 x1，x2，…，xn（列向），p个指标（行向）。聚类分析有两种类型：按样品聚类或按变量（指标）聚类。 表1 数据矩阵 样品 指标 聚类分析的基本思想是在样品之间定义距离，在变量之间定义相似系数，距离或相似系数代表样品或变量之间的相似程度。按相似程度的大小，将样品（或变量）逐一归类，关系密切的类聚到一个小的分类单位，然后逐步扩大，使得关系疏远的聚合到一个大的分类单位，直到所有的样品（或变量）都聚集完毕，形成一个表示亲疏关系的谱系图，依次按照某些要求对样品（或变量）进行分类。 分类统计量----距离与相似系数 样品间的相似性度量----距离 用样品点之间的距离来衡量各样品之间的相似性程度（或靠近程度）。设是样品 之间的距离，一般要求它满足下列条件： 在聚类分析中，有些距离不满足3），我们在广义的角度上仍称它为距离。 欧氏距离 绝对距离 Minkowski 距离 Chebyshev距离 方差加权距离 其中 马氏距离 其中 S 是由样品算得的协方差矩阵： 样品聚类通常称为Q型聚类，其出发点是距离矩阵。 变量间的相似性度量----相似系数 当对p个指标变量进行聚类时，用相似系数来衡量变量之间的相似程度（或关联程度）。一般地，若 表示变量之间的相似系数，应满足： 的绝对值越接近于1，说明变量 的关联越大。 相似系数中最常用的是相关系数与夹角余弦。 相关系数 变量之间的相关系数定义为： 事实上，是变量的观测值 之间的相关系数。 夹角余弦 变量的观测值 ，其夹角余弦定义为： 变量聚类通常称为 R 型聚类。在 R 型聚类中，相似系数矩阵 C 是出发点，相似系数矩阵可以是相关矩阵，也可以是夹角余弦矩阵。 谱系聚类法 类间距离定义 为简单起见，以i，j分别表示样品，以dij简记i，j之间的距离。Gp，Gq分别表示两个类，设它们分别含有np，nq个样品。若类Gp中有样品，则其均值 称为类 Gp 的重心。类Gp与Gq之间的距离记为 Dpq，有多种多样定义方式。 最短距离 最长距离 类平均距离 重心距离 离差平方和距离 类间距离的递推公式 按照谱系聚类法的思想，先将样品聚合成小类，在逐步扩大为大类。设类 Gr由类Gp、Gq合并所得，则Gr包含nr=np+nq个样品。 问题：由Gp，Gq与其它类Gk(k≠p,q)的距离计算Gr与Gk（k≠p,q）的距离，即建立类间距离的递推公式。 最短距离 最长距离 类平均距离 重心距离 离差平方和距离 谱系聚类法的步骤 谱系聚类法的步骤如下： Step1 n 个样品开始时作为 n 个类，计算两两之间的距离，构成一个对称距离矩阵： 此时，Dpq=dpq； Step2 选择 D(0)中的非对角线上的最小元素，设这个最小元素是 Dpq。此时，Gp={xp}，Gq={xq}。将Gp，Gq合并成一个新类Gr={Gp，Gq}。在 D(0)中消去Gp和Gq所对应的行与列，并加入有新类Gr与剩下的其它未聚合的类间的距离所组成的一行和一列，得到一个新的距离矩阵D(1)，它是n-1阶方阵； Step3 从 D(1)出发重复 Step2 的作法得 D(2)，再由D(2)出发重复上述步骤，直到n个样品聚为1个大类为止； 注意：?在合并过程中要记下合并样品的编号及两类合并时的水平（即距离）并绘制聚类谱系图。谱系聚类法的统计量 用谱系聚类法聚类时，聚多少类合适，这是一个实际的问题。一个较好的聚类应该在类内阁样品尽可能相似的前提下，使得类的个数尽可能少。这里需要考虑谱系距离用到的统计量，利用它们，可以在一定程度上判别聚多少类为合适。 R2统计量 设谱系得第 G 层共有G个类，定义 其中 为Gk的重心，Sk越小，说明Gk中各样品越相似。 定义 R2 统计量如下： R2总是随着分类数目的减少而减小，可以从R2值的变化看n个样品分成几类最合适。比如，分为5类以前各类的R2减小较缓慢；假定分为5类时，R2=0.85，而下一次合并，即分为4类时R2减小较快，如R2=0.35，则认为分为5类较合适。 半偏相关统计量 这一统计量与离差平方和距离有关。设类 Gp，Gq的离差平方和分别是 将 Gp，Gq合并成Gr后的离差平方和为 合并后的离差平方和增量为 定义半偏相关统计量为： SPRSQ是上一步R2值与该步R2值的差值，当SPRSQ值越大时，说明上一次合并效果越好。 伪F统计量 伪F