《模式识别导论》PPT课件.ppt

1 第六章聚类分析 6 1分类与聚类的区别分类 用已知类别的样本训练集来设计分类器 监督学习 聚类 集群 用事先不知样本的类别 而利用样本的先验知识来构造分类器 无监督学习 2 6 2系统聚类 系统聚类 先把每个样本作为一类 然后根据它们间的相似性和相邻性聚合 相似性 相邻性一般用距离表示 1 两类间的距离1 最短距离 两类中相距最近的两样品间的距离 3 2 最长距离 两类中相距最远的两个样本间的距离 3 中间距离 最短距离和最长距离都有片面性 因此有时用中间距离 设 1类和 23类间的最短距离为d12 最长距离为d13 23类的长度为d23 则中间距离为 上式推广为一般情况 4 4 重心距离 均值间的距离5 类平均距离 两类中各个元素两两之间的距离平方相加后取平均值 5 6 离差平方和 设N个样品原分q类 则定义第i类的离差平方和为 离差平方和增量 设样本已分成 p q两类 若把 p q合为 r类 则定义离差平方 6 2 系统聚类的算法设参加聚类的样本共N个 先选定样本间距离和类间距离的计算公式 再按以下步骤聚类 1 假定N个样本各成一类 记作 1 2 N 2 作距离矩阵D 0 因D 0 矩阵是对称的N N矩阵 我们只计算下三角部分 第i行第j列处的元素dij用i和j两样本的距离平方表示 7 3 求D 0 的最小元素dpq mindijp q因此 p和 q是目前最近的两类 4 把 p与 q合并成新的类 并求新类与原有其它各类间的距离 5 作下一距离矩阵D 1 6 若分的类数已满足预先要求或全部样本已合成一类 则算法结束 否则 重复以上步骤 8 例 有六个样本X x1 x2 x3 x4 x5 x6 其分布如下图所示 1 设全部样本分为6类 2 作距离矩阵D 0 9 3 求最小元素 4 把 1 3合并 7 1 3 4 6合并 8 4 6 5 作距离矩阵D 1 10 6 若合并的类数没有达到要求 转3 否则停止 3 求最小元素 4 8 5 2合并 9 2 5 4 6 11 6 2分解聚类 分解聚类 把全部样本作为一类 然后根据相似性 相邻性分解 目标函数两类均值方差 N 总样本数 1类样本数 2类样本数 12 分解聚类框图 13 对分算法 1 选取目标函数 把全体样品分成两类2 分别计算把x1 x2 xN并入G2类时的E值 设当xi并入G2时的E值最大 则把它并入G2得 3 再分别计算把x1 xi 1 xi 1 xN并入G2的E值 若当xj并入G2时E最大 则并入G2得 14 4 若E k 1 E k 则重复上述步骤 直到某个E K 达到最大值为止 这时最好的分类是G1 k 共有n k个样品 G2 k 有k个样品 每次分类后都要重新计算之值 可用以下递推公式 15 例 已知21个样本 每个样本取二个特征 原始资料矩阵如下表 16 解 第一次分类时计算所有样本 分别划到G2时的E值 找出最大的 1 开始时 目标函数 2 分别计算当x1 x2 x21划入G2时的E值 把x1划入G2时有 利用递推公式 17 然后再把x2 x21划入G2时对应的E值 计算出来进行比较 找出一个最大的E值 即把x21划为G2的E值最大 再继续进行第二 第三次迭代 计算出E 2 E 3 如下表 18 19 第10次迭代x1划入G2时 E最大 于是分成以下两类 20 作业 样本123456780215656702133445用对分法编程上机 分成两类画出图形 21 6 3动态聚类 兼顾系统聚类和分解聚类 一 动态聚类的方法概要 先选定某种距离作为样本间的相似性的度量 确定评价聚类结果的准则函数 给出某种初始分类 用迭代法找出使准则函数取极值的最好的聚类结果 22 动态聚类框图 二 代表点的选取方法代表点就是初始分类的聚类中心数k 凭经验选代表点 根据问题的性质 数据分布 从直观上看来较合理的代表点k 将全部样本随机分成k类 计算每类重心 把这些重心作为每类的代表点 23 按密度大小选代表点 以每个样本作为球心 以d为半径做球形 落在球内的样本数称为该点的密度 并按密度大小排序 首先选密度最大的作为第一个代表点 即第一个聚类中心 再考虑第二大密度点 若第二大密度点距第一代表点的距离大于d1 人为规定的正数 则把第二大密度点作为第二代表点 否则不能作为代表点 这样按密度大小考察下去 所选代表点间的距离都大于d1 d1太小 代表点太多 d1太大 代表点太小 一般选d1 2d 对代表点内的密度一般要求大于T T 0为规定的一个正数 用前k个样本点作为代表点 24 三 初始分类和调整 选一批代表点后 代表点就是聚类中心 计算其它样本到聚类中心的距离 把所有样本归于最近的聚类中心点 形成初始分类 再重新计算各聚类中心 称为成批处理法 选一批代表点后 依次计算其它样本的归类 当计算完第一个样本时 把它归于最近的一类 形成新的分类 再计算新的聚类中心 再计算第二个样本到新的聚类中心的距离 对第二个样本归类 即每个样本的归类都改变一次聚类中心 此法称为逐个处理法 直接用样本进行初始分类 先规定距离d 把第一个样品作为第一类的聚类中心 考察第二个样本 若第二个样本距第一个聚类中心距离小于d 就把第二个样本归于第一类 否则第二个样本就成为第二类的聚类中心 再考虑其它样本 根据样本到聚类中心距离大于还是小于d 决定分裂还是合并 25 最佳初始分类初始分类数k的确定有时是不准确的 假设k是逐渐增加的 如图所示 准则函数下降很快 经过拐点A后 下降很慢 说明拐点附近对应的k 比较接近最佳的初始分类 就是最佳初始分类 26 四 K次平均算法 这是一种常用的动态聚类方法 修改聚类中心的准则函数为 所有样本到聚类中心的距离平方和相加 其中Gj是第j个聚类 Nj是第j个聚类中的样本数 Zj为第j个聚类的聚类中心 K均值算法的聚类准则是 聚类中心Zj的选择应使准则函数的Jj值最小 因此 令 27 上式表明 Gj类的聚类中心应选在该类样本的均值第一步 任选k个初始聚类中心Z1 l Z2 l Zk l 第二步 计算每个样本到k个聚类中心的距离 并按最近规则归类 其中Gj k 为聚类中心Zj k 的样本聚类 在第k次迭代 分配各个样本x到k个聚类中心 28 第三步 从第二步的结果 计算新的聚类中心 上面已经证明 该新聚类中心可以使准则函数的Jj值最小 第四步 若新聚类中心与前一个聚类中心相等 即Zj k 1 Zj k j 1 2 k则算法收敛 聚类结束 否则 转第二步 29 例 已知有20个样本 每个样本有2个特征 数据分布如下图 第一步 令K 2 选初始聚类中心为 30 31 32 33 第三步 根据新分成的两类建立新的聚类中心 第四步 转第二步 第二步 重新计算到z1 2 z2 2 的距离 把它们归为最近聚类中心 重新分为两类 34 第三步 更新聚类中心 35 第四步 第二步 第三步 更新聚类中心 36 上机作业 已知十个样本 每个样本2个特征 数据如下 用K次平均算法和ISODATA算法分成3类 编程上机 并画出分类图 37 五 ISODATA算法 迭代自组织数据分析算法 ISODATA算法与K均值算法有相似之处 即聚类中心根据样本的均值来修改 不同的是 这种算法进行的过程中聚类中心的数目不是固定不变而是反复进行修改 聚类既有合并也有分裂 合并与分裂是在一组预先选定的参数指导下进行的 此外 一些经验结果也包含在算法中 ISODATA算法共分十四步 其中第一步到第六步是预选参数 进行初始分类 并为合并和分裂准备必要的数据 第七步决定下一步是进行合并还是进行分裂 第八步到第十步是分裂算法 第十一步到第十三步是合并算法 第十四步决定算法是否结束 算法的具体步骤如下 38 设有N个样本模式X1 X2 XN第一步 预选NC个聚类中心Z1 Z2 ZNC NC不要求等于希望的聚类数目 NC个聚类中心也可在N个样本中选择 然后预选下列指标 K K是希望的聚类中心的数目 N 每个聚类中最少的样本数 若某聚类中的样本少 N 则该聚类不能作为一个独立的聚类 应删去 S 一个聚类中样本的标准偏差参数 要求每一个聚类内标准偏差向量的所有分量中的最大分量小于 S 否则该类应分裂为两类 标准偏差向量的每一分量等于每个样本的分量与聚类中心对应分量差的平方和平均值 C 两聚类中心之间的最小距离 若两类中心之间距离小于 C 则这两类合并为一类 L 在一次迭代中允许合并的聚类中心的最大对数 I 允许迭代的次数 39 第二步 把N个样本按最近邻规则分配到Nc个聚类中 第三步 若Sj中的样本数Nj N 则取消该类 并且NC 1 第四步 修正各聚类中心 第五步 计算聚类Sj中各样本到该类聚类中心的平均距离 用表示 40 第六步 计算全部样本到其所在类聚类中心距离的平均距离 即计算全部样本的总体平均距离 用表示 第七步 判决是进行分裂还是进行合并 决定迭代步骤等 1 如迭代已达I次 即最后一次迭代 置QC 0 跳到第十一步 41 2 若NC K 2 聚类中心小于或等于希望数的一半 进入第八步 将已有的聚类分裂 3 如果迭代的次数是偶数 或NC 2K 聚类中心数目大于或等于希望数的两倍 则跳到第十一步 进行合并 否则进入第八步进行分裂 第八步 计算每个聚类的标准偏差向量 第Sj类的标准偏差向量为 式中 xij是Sj类样本X的第i个分量 zij是Zj的第i个分量 所以 ij是X的第i个分量的标准差 X是n维模式向量 42 第九步 求每个标准差向量的最大分量 j的最大分量记为 jmax j 1 2 NC 第十步 在最大分量集 jmax j 1 2 NC 中 如有 jmax S 即Sj类样本在 jmax对应方向上的标准偏差大于允许的值 同时又满足以下两条之一 1 和Nj 2 N 1 即类内平均距离大于总体平均距离 并且Sj类中样本数很大 2 NC K 2 即聚类数小于或等于希望数目的一半 本步完成后 跳回第二步 且迭代次数加1 43 第十一步 计算所有聚类中心之间的距离 Si类和Sj类中心间的距离为第十二步 比较所有Dij与 C的值 将小于 C的Dij按升序排列 Di1j1 Di2j2 DiLjL 其中 Di1j1 Di2j2 DiLjL L为允许每次合并的聚类中心的最大对数 第十三步 如将距离为Diljl的两类合并 得到新的聚类中心为 每合并一对 NC减1 44 第十四步 若是最后一次迭代 即迭代次数为I 算法结束 若需修改参数 则跳到第一步 然后重复上述算法 否则 跳到第二步 继续进行迭代运算 在本步运算里 迭代运算的次数加1 45 例 设有N 8个样本模式 它们分别为X1 0 0 tX2 1 1 tX3 2 2 tX4 3 4 tX5 3 5 tX6 4 4 tX7 4 5 tX8 5 6 t用ISODATA算法对这些样本进行分类 第一步 选NC 1 Z1 X1 0 0 t 各参数预选为 K 2 N 1 S 1 C 4 L 0 I 4 第二步 只有一个聚类中心Z1 故S1 X1 X2 X8 N1 8第三步 因N1 N故无聚类可删除 46 第四步 修改聚类中心 第五步 计算第六步 计算 因只有一类 故第七步 因不是最后一次迭代 且NC K 2 故进入第八步进行分裂运算 47 第八步 求S1的标准偏差向量 1 得 1 1 99 1 56 t第九步 1的最大分量是1 99 因此 1max 1 99第十步 因 1max S且NC K 2 可将Z1分裂为两个新的聚类中心 因 1max是 1的第一个分量 即S1中样本分布在X的第一个分量方向上较分散 故分裂应在Z1的第一个分量方向上进行 分裂系数k选为0 5 得 48 为了方便 令 这一步之后 NC加1 迭代次数加1 即下面进行第2次迭代运算 跳回到第二步 第二步 按最近邻规则对所有样本聚类 得到两个聚类分别为S1 X4 X5 X6 X7 X8 S2 X1 X2 X3 N1 5 N2 3第三步 因N1和N2都大于 N 无聚类可以删除 第四步 修改聚类中心 得 49 第五步 计算和 得第六步 计算 得第七步 因这是偶数次迭代 符合第七步的第 3 条 故进入第十一步 第十一步 计算聚类之间距离 得 50 第十二步 比较D12与 C 这里D12 C 第十三步 根据第十二步的结果 聚类中心不能发生合并 第十四步 因为不是最后一次迭代 需要判断是否要修改给定的参数 但前面的迭代运算结果已得到希望的聚类数目 聚类之间分散程度大于类内样本的标准差 每一聚类中样本数目都具有样本总数的足够大的百分比 且两类样本数相差不大 故可不必修改参数 因此 回到第二步 且迭代次数加1 第二步到第六步 与前一次迭代运算的结果相同 第七步 没有一种情况被满足 继续执行第八步 51 第八步 计算S1和S2的标准偏差向量 1和 2 这时S1和S2仍为S1 X4 X5 X6 X7 X8 S2 X1 X2 X3 计算结果为 1 0 75 0 75 t 2 0 82 0 82 t第九步 1max 0 75 2max 0 82第十步 分裂条件不满足 故继续执行第十一步 52