K均值改进聚类.ppt

基于取样思想的改进C均值聚类 目录 C 均值算法的缺陷分析改进C均值算法的分析matlab编程所用到函数介绍matlab算法程序介绍结果分析结论 一 C 均值算法的缺陷分析 1 聚类个数C需要预先给定有的算法是通过类的自动合并和分裂 得到较为合理的类型数目C 例如用ISODATA算法 得到初始的聚类数目C 然后运用C均值算法进行聚类分析 聚类数目C值的确定也可根据方差分析理论 F统计量来确定最佳分类数 并应用模糊划分嫡来验证最佳分类数的正确性 一 C 均值算法的缺陷分析 2 算法对初值敏感在C means算法中 首先需要根据初始聚类中心来确定一个初始划分 然后对初始划分进行优化 这个初始聚类中心的选择对聚类结果有较大的影响 一旦初始值选择的不好 可能无法得到有效的聚类结果 这也成为C means算法的一个主要问题 对于该问题的解决 许多算法采用遗传算法进行初始化 以内部聚类准则作为评价指标 一 C 均值算法的缺陷分析 3 局部极小解的问题聚类问题本质是一个优化问题的 这就是通过一种迭代运算使得系统的目标函数达到一个极小值 但是这个目标函数在状态空间中不是一个非凸函数 它有许多极小值 其中只有一个是全局极小值 而其他的都是局部极小值 求解的目标是得到全局最小值 而不是其它的局部极小值 这也是目前一些聚类算法 经常会遇到的总是 常会在求解过程中陷入局部最优 而得不到全局最优 二 改进C均值算法的分析 在K均值算法中 选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率 此方法就是如何找到与数据在空间分布上尽可能一致的初始聚类中心 对数据进行划分 最根本的目的是使一个聚类中的对象是相似的 而不同聚类中的对象是不相似的 如果用距离表示对象之间的相似性程度 相似对象之间的距离比不相似对象之间的距离要小 如果能够寻找到K个初始中心 它们分别代表了相似程度较大的数据集合 那么就找到了与数据在空间分布上相一致的初始聚类中心 二 改进C均值算法的分析 目前 初始聚类中心选取的方法有很多种 在此仅介绍两种 1 基于最小距离的初始聚类中心选取法 1 计算数据对象两两之间的距离 2 找出距离最近的两个数据对象 形成一个数据对象集合A1 并将它们从总的数据集合U中删除 3 计算A1中每一个数据对象与数据对象集合U中每一个样本的距离 找出在U中与A1中最近的数据对象 将它并入集合A1并从U中删除 直到A1中的数据对象个数到达一定阈值 4 再从U中找到样本两两间距离最近的两个数据对象构成A2 重复上面的过程 直到形成k个对象集合 5 最后对k个对象集合分别进行算术平均 形成k个初始聚类中心 二 改进C均值算法的分析 2 基于取样思想的改进C均值算法基于以上对C均值算法的分析 我提出自己的改进算法 首先采用对所给的样本数据进行K means算法进行聚类 产生一组聚类中心 然后将这组聚类中心作为初始聚类中心 在采用n次K means算法进行聚类 然后判断两次聚类得到的中心是否一致 直到一致则结束聚类 在此 也可以在第一步中 对样本数据采用K means算法进行n次聚类运算 每次产生一组聚类中心 对n组聚类中心进行算术平均 从而得到c组初始聚类中心 三 matlab编程所用到函数介绍 1 IDX C kmeans data k IDX 聚类结果C 聚类中心k 分类个数data 要聚类的数据集合 每一行为一个样本 三 matlab编程所用到函数介绍 mean函数函数原型 mean A dim 参数 A待求解均值的矩阵dim默认dim 1 就会求每一列的均值 当dim 2时 就会求每一行的均值 四 matlab算法程序介绍 程序主要包括两部分 一个聚类中心的提取 另一个是重新进行聚类划分 计算初始聚类中心clc clear 使用c 均值得到初始分类functionyy Kmeans2 data xlsread E 模式识别数据 data 载入数据 IDX C kmeans data 4 Cy 1 59 z data IDX x z y 初始聚类中心的提取 kmeans初始算得的聚类中心在矩阵C中x1 x2 x3 x4 fori 1 59 四 matlab算法程序介绍 ifx 4 i 1x1 x1 x i elseifx 4 i 2x2 x2 x i elseifx 4 i 3x3 x3 x i elsex 4 i 4x4 x4 x i endendformatshortgx1 C 1 x2 C 2 x3 C 3 x4 C 4 四 matlab算法程序介绍 x x 1 3 x 5 xx mean x1 2 mean x2 2 mean x3 2 mean x4 2 xxx ones 3 4 j 0 whilexx xxxxx xxx 迭代求解聚类中心d1 d2 d3 d4 fori 1 size z 2 d1 d1 round 1000 sum x 1 3 i mean x1 2 2 1000 d2 d2 round 1000 sum x 1 3 i mean x2 2 2 1000 d3 d3 round 1000 sum x 1 3 i mean x3 2 2 1000 d4 d4 round 1000 sum x 1 3 i mean x4 2 2 1000 endd1 d2 d3 d4 d1 d2 d3 d4 这四组数据分别存储了49个点分别与四个聚类中心的距离 四 matlab算法程序介绍 ww1 ww2 ww3 ww4 取与聚类中心最近的那个点 并将其归入相应类fori 1 size z 2 ifmin d1 i d2 i d3 i d4 i d1 i ww1 ww1 x i elseifmin d1 i d2 i d3 i d4 i d2 i ww2 ww2 x i elseifmin d1 i d2 i d3 i d4 i d3 i ww3 ww3 x i elseww4 ww4 x i endendx1 ww1 1 3 x2 ww2 1 3 x3 ww3 1 3 四 matlab算法程序介绍 x4 ww4 1 3 xxx mean x1 2 mean x2 2 mean x3 2 mean x4 2 yyy xxx endww1ww2ww3ww4plot3 ww1 1 ww1 2 ww1 3 s ww2 1 ww2 2 ww2 3 ww3 1 ww3 2 ww3 3 o ww4 1 ww4 2 ww4 3 绘制三维图grid 五 结果分析 C 1 0e 03 1 21061 87802 95792 33273 07891 07590 30103 22282 25021 73321 73561 9762ww1 1至6列864 45877 881418 81449 6867 811494 61647 32031 71775 91641 62334 72072 62665 93071 22772 93405 12535 12550 546162532397至10列1243 11495 21125 21269 11814 11957 41594 41910 73441 134982937 7270242535456 五 结果分析 ww2 1至6列2352 12297 32092 62205 42949 22802 925573340 13177 23243 73244 43017 11411 5535 62584 321202 7662 421985814151819227至12列2063 523752271 92336 32144 52201 93199 8334734832640 32501 63196 21257 2975 31946 71599 6591 51935 5324353643454913列2232 43077 91298 950 五 结果分析 ww3 1至6列373 3222 85401 3363 34104 8499 853087 13059 53259 93477 93389 83305 82429 52002 321512462 92421 82196 22591012137至12列172 78341 59291 02237 63460 69198 833084 53076 63095 73077 83274 83250 42328 72438 62088 9225221732445 123272829343813至16列354426 31343 0724 223300 13105 33271 73447 32373 62057 82036 9214544464855 五 结果分析 ww4 1至6列1739 91756 81803 61571 21845 61692 61675 216521583 117311918 81867 5239615152163 11735 32226 521091371117207至12列1680 71651 51702 81877 91831 51783 61575 81713 31639 818611713 115981725 11570 42068 71975 31604 72261 321263031333713至18列15971598 91507 11580 11962 41802 11921 51921 11556 91752 115951725 82126 81623 31