聚类分析 PPT课件

1 数据的分类 聚类分析 2 在商业上 聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来 并且概括出每一类消费者的消费习惯 它作为数据挖掘中的一个模块 可以作为一个单独的工具来发现数据库中分布的一些深层的信息 并且概括出每一类的特点 或者把注意力放在某一个特定的类上做进一步的分析 聚类分析的算法可以分为划分法 层次法 基于密度的方法 基于网格的方法 基于模型的方法 其中 最广泛使用的聚类算法k means算法属于划分法 聚类算法 3 给定一个有N个元组或者纪录的数据集 划分法将构造K个分组 每一个分组就代表一个聚类 K N 而且这K个分组满足下列条件 1 每一个分组至少包含一个数据纪录 2 每一个数据纪录属于且仅属于一个分组 某些模糊聚类算法中该条件可以放宽 对于给定的K 算法首先给出一个初始的分组方法 以后通过反复迭代的方法改变分组 使得每一次改进之后的分组方案都较前一次好 而所谓好的标准就是 同一分组中的记录越近越好 而不同分组中的纪录越远越好 划分法 4 k means算法 也被称为k 均值或k 平均 该算法首先随机地选择k个对象作为初始的k个簇的质心 然后对剩余的每个对象 根据其与各个质心的距离 将它赋给最近的簇 然后重新计算每个簇的质心 这个过程不断重复 直到准则函数收敛 通常采用的准则函数为平方误差和准则函数 即SSE sumofthesquarederror 其定义如下 SSE是数据库中所有对象的平方误差总和 p为数据对象 mi是簇Ci的平均值 这个准则函数使生成的结果尽可能的紧凑和独立 k means算法 5 饮料数据 drink txt 16种饮料的热量 咖啡因 钠及价格四种变量 6 如何根据以上数据对16种饮料进行分类呢 对数据进行分类就需要知道距离 你知道那些距离 7 如何度量距离远近 如果想要对100个学生进行分类 而仅知道他们的数学成绩 则只好按照数学成绩分类 这些成绩在直线上形成100个点 这样就可以把接近的点放到一类 如果还知道他们的物理成绩 这样数学和物理成绩就形成二维平面上的100个点 也可以按照距离远近来分类 三维或者更高维的情况也是类似 只不过三维以上的图形无法直观地画出来而已 在饮料数据中 每种饮料都有四个变量值 这就是四维空间点的问题了 8 两个距离概念 按照远近程度来聚类需要明确两个概念 一个是点和点之间的距离 一个是类和类之间的距离 点间距离有很多定义方式 最简单的是歐氏距离 当然还有一些和距离相反但起同样作用的概念 比如相似性等 两点越相似度越大 就相当于距离越短 9 两个距离概念 由一个点组成的类是最基本的类 如果每一类都由一个点组成 那么点间的距离就是类间距离 但是如果某一类包含不止一个点 那么就要确定类间距离 类间距离是基于点间距离定义的 比如两类之间最近点之间的距离可以作为这两类之间的距离 也可以用两类中最远点之间的距离或各类的中心之间的距离来作为类间距离 在计算时 各种点间距离和类间距离的选择是通过统计软件的选项实现的 不同的选择的结果会不同 但一般不会差太多 10 向量x x1 xp 与y y1 yp 之间的距离或相似系数 欧氏距离 Euclidean 平方欧氏距离 SquaredEuclidean 夹角余弦 相似系数1 cosine Pearsoncorrelation 相似系数2 Chebychev Maxi xi yi Block 绝对距离 Si xi yi Minkowski 当变量的测量值相差悬殊时 要先进行标准化 如R为极差 s为标准差 则标准化的数据为每个观测值减去均值后再除以R或s 当观测值大于0时 有人采用Lance和Williams的距离 11 类Gp与类Gq之间的距离Dpq d xi xj 表示点xi Gp和xj Gq之间的距离 最短距离法 最长距离法 重心法 离差平方和 Wald 类平均法 中间距离 可变平均法 可变法等可参考各书 在用欧氏距离时 有统一的递推公式 12 最短距离 NearestNeighbor 13 最长距离 FurthestNeighbor 14 组间平均连接 Between groupLinkage 15 组内平均连接法 Within groupLinkage 16 重心法 Centroidclustering 均值点的距离 17 离差平方和法连接 2 4 1 5 6 5 18 红绿 2 4 6 5 8 75离差平方和增加8 75 2 5 6 25黄绿 6 5 1 5 14 75离差平方和增加14 75 8 5 6 25黄红 2 4 1 5 10 10 0故按该方法的连接和黄红首先连接 19 有了上面的点间距离和类间距离的概念 就可以介绍聚类的方法了 这里介绍两个简单的方法 20 系统聚类法 系统聚类法 hierarchicalclusteringmethod 是聚类分析中用的最多的一种 基本思想 开始将n个样本各自作为一类 并规定样本之间的距离与类之间的距离 然后将距离最近的两类合并成一个新类 并计算新类与其他类之间的距离 重复进行两个最近类的合并 每次减少一类 直至所有的样本合并为一类 当然我们可以选择以上距离的任意一种进行聚类 21 动态聚类法 K均值聚类 前面说过 聚类可以走着瞧 不一定事先确定有多少类 但是这里的k 均值聚类 k meanscluster 也叫快速聚类 quickcluster 却要求你先说好要分多少类 看起来有些主观 是吧 假定你说分3类 这个方法还进一步要求你事先确定3个点为 聚类种子 SPSS软件自动为你选种子 也就是说 把这3个点作为三类中每一类的基石 22 然后 根据和这三个点的距离远近 把所有点分成三类 再把这三类的中心 均值 作为新的基石或种子 原来 种子 就没用了 再重新按照距离分类 如此叠代下去 直到达到停止叠代的要求 比如 各类最后变化不大了 或者叠代次数太多了 显然 前面的聚类种子的选择并不必太认真 它们很可能最后还会分到同一类中呢 下面用饮料例的数据来做k 均值聚类 23 例1续动态聚类的函数为kmeans idx kmeans X k Name Value 24 聚类要注意的问题 聚类结果主要受所选择的变量影响 如果去掉一些变量 或者增加一些变量 结果会很不同 相比之下 聚类方法的选择则不那么重要了 因此 聚类之前一定要目标明确 另外就分成多少类来说 也要有道理 只要你高兴 从分层聚类的计算机结果可以得到任何可能数量的类 但是 聚类的目的是要使各类之间的距离尽可能地远 而类中点的距离尽可能的近 并且分类结果还要有令人信服的解释 这一点就不是数学可以解决的了 2020 4 11 25 主成分分析 2020 4 11 26 一 什么是主成分分析及基本思想 1 什么是主成分分析 主成分概念首先由Karlparson在1901年引进 不过当时只对非随机变量来讨论的 1933年Hotelling将这个概念推广到随机向量 在实际问题中 研究多指标 变量 问题是经常遇到的 然而在多数情况下 不同指标之间是有一定相关性 由于指标较多再加上指标之间有一定的相关性 势必增加了分析问题的复杂性 主成分分析就是设法将原来指标重新组合成一组新的互相无关的几个综合指标来代替原来指标 同时根据实际需要从中可取几个较少的综合指标尽可能多地反映原来指标的信息 这种将多个 2020 4 11 27 指标化为少数互相无关的综合指标的统计方法叫做主成分分析或称主分量分析 也是数学上处理降准的一种方法 例如 某人要做一件上衣要测量很多尺寸 如身长 袖长 胸围 腰围 肩宽 肩厚等十几项指标 但某服装厂要生产一批新型服装绝不可能把尺寸的型号分得过多 而是从多种指标中综合成几个少数的综合指标 做为分类的型号 利用主成分分析将十几项指标综合成3项指标 一项是反映长度的指标 一项是反映胖瘦的指标 一项是反映特体的指标 在商业经济中用主成分分析可将复杂的一些数据综合成几个商业指数形式 如物价指数 生活费用指数 商业活动指数等等 主成分分析除了可以单独用来处理上面所讨论的这一类问题外 还可以与其它方法结合起来使用 例如与回归分析结合起来就是主成分回归 它可以克服回归问题中由于自变量之间的高度相关而产生的分析困难 2020 4 11 28 2基本思想 主成分分析就是设法将原来众多具有一定相关性的指标 比如p个指标 重新组合成一组新的相互无关的综合指标来代替原来指标 通常数学上的处理就是将原来p个指标作线性组合 作为新的综合指标 但是这种线性组合 如果不加限制 则可以有很多 我们应该如何去选取呢 如果将选取的第一个线性组合即第一个综合指标记F1 自然希望F1尽可能多的反映原来指标的信息 这里的 信息 用什么来表达 最经典的方法就是用F1的方差来表达 即Var F1 越大 表示F1包含的信息越多 因此在所有的线性组合中所选取的F1应该是方差最大的 故称F1为第一主成分 如果第一主成分不足以代表原来p个指标的信息 再考虑选取F2即选第二个线性组合 为了有效地反映原来信息 F1已有的信息就不需要再出现在F2中 用数学 2020 4 11 29 语言表达就是要求Cov F1 F2 0 称F2为第二主成分 依此类推可以造出第三 四 第p个主成分 不难想像这些主成分之间不仅不相关 而且它们的方差依次递减 因此在实际工作中 就挑选前几个最大主成分 虽然这样做会损失一部分信息 但是由于它使我们抓住了主要矛盾 并从原始数据中进一步提取了某些新的信息 因而在某些实际问题的研究中得益比损失大 这种既减少了变量的数目又抓住了主要矛盾的做法有利于问题的分析和处理 2 主成分分析的数学模型及几何解释 1 数学模型 设有n个样品 每个样品观测p项指标 变量 X1 X2 Xp 得到原始数据资料阵 2020 4 11 30 其中 用数据矩阵X的p个向量 即p个指标向量 X1 Xp作线性组合 即综合指标向量 为 2020 4 11 31 简写成 注意 Xi是n维向量 所以Fi也是n维向量 上述方程组要求 2020 4 11 32 的一切线性组合中方差最大的 如何求满足上述要求的方程组的系数aij呢 下一节将会看到每个方程式中的系数向量 不是别的而恰好是X的协差阵 所对应的特征向量 也就是说 数学上可以证明使Var F1 达到最大 这个最大值是在的第一个特征值所对应特征向量处达到 依此类推使Var Fp 达到最大值是在的 的特征值 2020 4 11 33 第p个特征值所对应特征向量处达到 这里要说明两点 一个是数学模型中为什么作线性组合 基于两种原因 数学上容易处理 在实践中效果很好 另一个要说明的是每次主成分的选取使Var Fi 最大 如果不加限制就可使Var Fi 则就无意义了 而常用的限制是要求 2 主成分的几何意义 从代数学观点看主成分就是p个变量X1 Xp的一些特殊的线性组合 而在几何上这些线性组合正是把X1 Xp构成的坐标系旋转产生的新坐标系 新坐标轴使之通过样品变差最大的方向 或说具有最大的样品方差 下面以最简单的二元正态变量来说明主成分的几何意义 34 主成分分析的几何解释 平移 旋转坐标轴 35 主成分分析的几何解释 平移 旋转坐标轴 36 主成分分析的几何解释 平移 旋转坐标轴 37 主成分分析的几何解释 平移 旋转坐标轴 2020 4 11 38 设有n个样本 每个样本有p个变量记为X1 Xp 它们的综合变量记为F1 F2 Fp 当p 2时 原变量是X1 X2 设它们有下图的相关关系 对于二元正态分布变量 n个点的散布大致为一个椭园 若在椭园长轴方向取坐标轴F1 在短轴方向取F2 这相当于在平面上作一个坐标变换 即按逆时针方向旋转角度 根据旋轴变换公式新老坐标之间有关系 2020 4 11 39 我们看到F1 F2是原变量X1和X2的线性组合 用矩阵表示是 显然 且是正交矩阵 即 从上图还容易看出二维平面上的n个点的波动 可用方差表示 大部分可以归结为在F1轴上的波动 而在F2轴上的波动是较小的 如果上图的椭园是相当扁平的 那么我们可以只考虑F1方向上的波动 忽略F2方向的波动 这样一来 二维可以降为一维了 只取第一个综合变量F1即可 而F1是椭园的长轴 2020 4 11 40 一般情况 p个变量组成p维空间 n个样本就是p维空间的n个点 对p元正态分布变量来说 找主成分的问题就是找p维空间中椭球体的主轴问题 3主成分的推导及性质 在下面推导过程中 要用到线性代数中的两个定理先作一下复习 定理一若矩阵A是p阶实对称阵 则一定可以找到正交阵 定理二若上述矩阵A的特征根所对应的单位特征向量 2020 4 11 41 则实对称A属于不同特征根所对应的特征向量是正交的即 l主成分的推导 设 其中 求主成分就是寻找X的线性函数a X使相应的方差尽可能地大即使 2020 4 11 42 达到最大值 且 设协差阵的特征根为 单位特征向量为 相应的 2020 4 11 43 由前面线性代数定理可知 且 因此 所以 2020 4 11 44 达到最大值 且 而且 同理 2020 4 11 45 上述推导表明 X1 X2 Xp的主成分就是以 的特征向量为系数的线性组合 它们互不相关 其方差为 的特征根 由于 的特征根 了解这一点也就可以明白为什么主成分的名次是按特征根取值大小的顺序排列的 所以有 VarF1 VarF2 VarFp o 在解决实际问题时 一般不是取p个主成分 而是根据累计贡献率的大小取前几个 定义称第一主成分的贡献率为 主成分的贡献率就是主成分的方差在全部方差中的比值 因此第一 2020 4 11 46 个值越大 表明第一主成分综合X1 Xp信息 的能力越强 前两个主成分的累计贡献率定义为 前两个主成分的累计贡献率定义为 前k个主成分的贡献率达到85 表明取前是个主成分基本包含了全部测量指标所具有的信息 这样既减少了变量的个数又便于对实际问题的分析和研究 如果 值得指出的是 当协差阵 未知时 可用其估计值S 样本协差阵 来代替 设原始资料阵为 2020 4 11 47 则 其中 而相关系数阵 其中 2020 4 11 48 显然当原始变量Xl Xp标准化后 则 实际应用时 往往指标的量纲不同 所以在计算之前先消除量纲的影响 而将原始数据标准化 这样一来S和R相同 因此一般求R的特征根和特征向量 并且不妨取R X X 因为这时的R与 不变 它并不影响求主成分 只差一个系数 显然 与 的特征根相差n倍 但它们的特征向量 2 主成分的主要性质 性质1F的协差阵为对角阵A 2020 4 11 49 证明 记 显然 性质2 证明 性质3 2020 4 11 50 证明 其中 为单位向量 第i个分量为1 其余为0 所以 2020 4 11 51 4计算步骤及实例 设有n个样品 每个样品观测p个指标 将原始数据写成矩 1 将原始数据标准化 这里不妨设上边矩阵已标准化了 2 建立变量的相关系数阵 不妨设 2020 4 11 52 3 求特征根 及相应的 单位特征向量 4 写出主成分 例对全国30个省市自治区经济发展基本情况的八项指标作主成分分析 原始数据如下 2020 4 11 53 2020 4 11 54 2020 4 11 55 2020 4 11 56 第一步将原始数据标准化 第二步建立指标之间的相关系数阵R如下 2020 4 11 57 第三步求R的特征值和特征向量 2020 4 11 58 从上表看 前3个特征值累计贡献率已达89 564 说明前3个主成分基本包含了全部指标具有的信息 我们取前3个特征值 并计算出相应的特征向量 2020 4 11 59 因而前三个主成分为 第一主成分 第二主成分 F2 0 107995X1 0 258512X2 0 287536X3 0 100931X4 0 40431X5 0 498801X6 0 48868X7 0 167392X8 2020 4 11 60 第三主成分 在第一主成分的表达式中第一 二 三项指标的系数较大 这三个指标起主要作用 我们可以把第一王成分看成是由国内生产总值 固定资产投资和居民消费水平所该划的反映经济发展状况的综合指标 在第二主成分中 第四 五 六 七项指标的影响大 且第六 七项指标的影响尤其大 可将之看成是反映物价指数 职工工资和货物周转量的综合指标 在第三主成分中 第八项指数影响最大 远超过其它指标的影响 可单独看成是工业总产值的影响 2020 4 11 61 5附注 1 从 和从R出发计算主成分一般是不同的 当变量取值范围彼此相差很大或度量单位不同时 应该考虑标准化 以便使计算结果有合理的解释 避免出现误解 如果没有上述度量单位和数量级的差异 从 和从R出发计算的结果对主成分的解释或计算贡献时 在一般情况下是不会发生矛盾的 2 主成分是原始变量的线性组合 它不能简单地解释为单变量的属性作用 因而不能直接说明单个原始变量属性对主成分的作用 而应该同时看一些起主要作用的原始变量的综合作用 依此给主成分一个合理解释 3 从主成分的数学推导 不难看出主成分仅依赖于X1 X2 Xp的协差阵 或相关系数阵 并不要求分布 2020 4 11 62 是多元正态的 即未对总体分布提出什么特定的要求 4 主成分个数的确定 一种方法在前边计算过程中已提到即根据实际问题的需要由累计贡献率的大小来确定 因此一般就选前二 三个主成分代替原来p个变量的信息 而不会损失很多信息 另一种方法是作如下的假设检验 如果不作检验就没必要有这个限制 因为特征根相等意味着数据在相应的p一q维空间上有各向同性的散布 若接受H0则在q的基础上 再增加任何主成分就得把剩下的全部包括进去 因为后p一q个主成分含有相同的信息量 在H0成立下可得Bartlet近似检验统计量 2020 4 11 63 其中 算术平均 几何平均 若拒绝H0即应增加主成分的个数 若接受H0 说明在已给检验水平下取q个主成分已能描述数据 5 主成分分析用于系统评估 系统评估是指对系统营运状态做出评估 而评估一个系统的营运状态往往需要综合考察许多营运的指标 2020 4 11 64 例如对某一类企业经济效益作评占 影响企业经济效益就有许多指标 很难直接比较其优劣 听以解决评估问题的焦点就是希望科学 客观地将一个多指标问题综合成一个单指标的形式 也就是说只有在一维空间中才能使排序评估成为可能 因此产生了许许多多评估方法 鉴于系统评估在社会 经济等许多领域中有着广泛而重要的应用 下面介绍三种方法 第一种方法 利用主成分F1 Fp做线性组合 并以每个主成分Fi的方差贡献率作为权数构造一个综合评价函数 也称y为评估指数 依据对每个系统计算出的y值大小进行排序比较或分类划级 2020 4 11 65 这一方法目前在一些专业文献中都有介绍 但在实践中经常看到它的应用效果并不理想 主要原因是产生主成分的特征向量的各分量符号不一致 很难进行排序评估 因此有下面的改进方法 第二种方法 只用第一个主成分作评估指数即Y F1 理由是 第一主成分与原始变量X1 Xp综合相关度最强即 从这个意义上看 如果想以一个综合变量来代替原来所有原始变量 则最佳选择应该是F1 另一方面由于第一主成分F1对应于数据变异最大的方向也就是使数据信息损失最小 精度最高的一维综合变量 但值得指出的是使用这种方法是有前提条件的即要求所有评估指标变量都是正相关 2020 4 11 66 的 也就是说对听有变量均有同增 同减的趋势 这个前提条件是基于代数中的Frobinius定理 定理若相关系数阵 中的每