logo资料库

模糊c均值聚类+FCM算法的c++代码.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.25M 资料格式：doc 举报 版权申诉
第1页 / 共21页
第2页 / 共21页
第3页 / 共21页
第4页 / 共21页
第5页 / 共21页
第6页 / 共21页
第7页 / 共21页
第8页 / 共21页
资料共21页，剩余部分请下载后查看
    模糊 C 均值聚类算法的实现 研究背景 聚类分析是多元统计分析的一种，也是无监督模式识别的一个重要分支，在 模式分类 图像处理和模糊规则处理等众多领域中获得最广泛的应用。它把一个 没有类别标记的样本按照某种准则划分为若干子集，使相似的样本尽可能归于一 类，而把不相似的样本划分到不同的类中。硬聚类把每个待识别的对象严格的划 分某类中，具有非此即彼的性质，而模糊聚类建立了样本对类别的不确定描述， 更能客观的反应客观世界，从而成为聚类分析的主流。 模糊聚类算法是一种基于函数最优方法的聚类算法，使用微积分计算技术求 最优代价函数，在基于概率算法的聚类方法中将使用概率密度函数，为此要假定 合适的模型，模糊聚类算法的向量可以同时属于多个聚类，从而摆脱上述问题。 模糊聚类分析算法大致可分为三类 1）分类数不定，根据不同要求对事物进行动态聚类，此类方法是基于模糊等价 矩阵聚类的，称为模糊等价矩阵动态聚类分析法。 2）分类数给定，寻找出对事物的最佳分析方案，此类方法是基于目标函数聚类 的，称为模糊 C 均值聚类。 3）在摄动有意义的情况下，根据模糊相似矩阵聚类，此类方法称为基于摄动的 模糊聚类分析法 我所学习的是模糊 C 均值聚类算法，要学习模糊 C 均值聚类算法要先了解虑 属度的含义，隶属度函数是表示一个对象 x 隶属于集合 A 的程度的函数，通常记 做μA(x)，其自变量范围是所有可能属于集合 A 的对象（即集合 A 所在空间中的 所有点），取值范围是[0,1]，即 0<=μA(x)<=1。μA(x)=1 表示 x 完全隶属于集合 A，相当于传统集合概念上的 x∈A。一个定义在空间 X={x}上的隶属度函数就定 A 。对于有限个对 ~ 义了一个模糊集合 A，或者叫定义在论域 X={x}上的模糊子集 象 x1，x2，……，xn 模糊集合 A 可以表示为： ~   A {( ( x i ), x i |) x i  X } A ~ (6.1) 有了模糊集合的概念，一个元素隶属于模糊集合就不是硬性的了，在聚类的 问题中，可以把聚类生成的簇看成模糊集合，因此，每个样本点隶属于簇的隶属 度就是[0，1]区间里面的值。 FCM 算法需要两个参数一个是聚类数目 C，另一个是参数 m。一般来讲 C 要 远远小于聚类样本的总个数，同时要保证 C>1。对于 m，它是一个控制算法的柔 性的参数，如果 m 过大，则聚类效果会很次，而如果 m 过小则算法会接近 HCM 聚类算法。 算法的输出是 C 个聚类中心点向量和 C*N 的一个模糊划分矩阵，这个矩阵表 示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最 大隶属原则就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均 特征，可以认为是这个类的代表点。 从算法的推导过程中我们不难看出，算法对于满足正态分布的数据聚类效果会很
    好，另外，算法对孤立点是敏感的。 聚类算法是一种比较新的技术，基于曾次的聚类算法文献中最早出现的 Single-Linkage 层次聚类算法是 1957 年在 Lloyd 的文章中最早出现的，之后 MacQueen 独立提出了经典的模糊 C 均值聚类算法，FCM 算法中模糊划分的概念最 早起源于 Ruspini 的文章中，但关于 FCM 的算法的详细的分析与改进则是由 Dunn 和 Bezdek 完成的。 模糊 c 均值聚类算法因算法简单收敛速度快且能处理大数据集，解决问题范 围广，易于应用计算机实现等特点受到了越来越多人的关注，并应用于各个领域。 算法描述 模糊 C 均值聚类算法的步骤还是比较简单的，模糊 C 均值聚类（FCM），即众 所周知的模糊 ISODATA，是用隶属度确定每个数据点属于某个聚类的程度的一种 聚类算法。1973 年，Bezdek 提出了该算法，作为早期硬 C 均值聚类（HCM）方法 的一种改进。 FCM 把 n 个向量 xi（i=1,2,…,n）分为 c 个模糊组，并求每组的聚类中心， 使得非相似性指标的价值函数达到最小。FCM 与 HCM 的主要区别在于 FCM 用模糊 划分，使得每个给定数据点用值在 0，1 间的隶属度来确定其属于各个组的程度。 与引入模糊划分相适应，隶属矩阵 U 允许有取值在 0，1 间的元素。不过，加上 归一化规定，一个数据集的隶属度的和总等于 1： c  i 1  u ij  ,1 j ,...,1 n (6.9) 那么，FCM 的价值函数（或目标函数）就是式（6.2）的一般化形式： , ( cUJ 1 ,..., c c )  c  i 1  J i  c  n j i 1  m du ij 2 ij ， (6.10) 这里 uij 介于 0，1 间；ci 为模糊组 I 的聚类中心，dij=||ci-xj||为第 I 个聚类中 心与第 j 个数据点间的欧几里德距离；且  是一个加权指数。  ,1m 构造如下新的目标函数，可求得使（6.10）式达到最小值的必要条件： , ( cUJ 1 ,..., c c ,  1 n ,..., )  , ( cUJ 1 ,..., c c )   n j 1   j ( c  i 1  u ij  )1 (6.11)  c  n j i 1  m du ij 2 ij  c n    j ( j 1  i 1  u ij  )1 这里j，j=1 到 n，是（6.9）式的 n 个约束式的拉格朗日乘子。对所有输入参量 求导，使式（6.10）达到最小的必要条件为： c i 和 n  1 j  n  j 1  m xu ij u m ij j (6.12)
    u ij  c  k 1  d d     1     ij kj /(2 m )1  (6.13) 由上述两个必要条件，模糊 C 均值聚类算法是一个简单的迭代过程。在批处理方 式运行时，FCM 用下列步骤确定聚类中心 ci 和隶属矩阵 U[1]： 步骤 1：用值在 0，1 间的随机数初始化隶属矩阵 U，使其满足式（6.9）中 的约束条件 步骤 2：用式（6.12）计算 c 个聚类中心 ci，i=1,…,c。 步骤 3：根据式（6.10）计算价值函数。如果它小于某个确定的阀值，或它 相对上次价值函数值的改变量小于某个阀值，则算法停止。 步骤 4：用（6.13）计算新的 U 矩阵。返回步骤 2。 上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保 FCM 收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另外的 快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次 运行 FCM。 模糊 c 均值聚类算法如下： Reapeat for l=1 2 3…….. Step 1:compute the cluseter prototypes(means): Step 2:compete the distance: Step 3:Update the partition matrix:
    算法改进 1） 在模糊聚类的目标函数中 Bezdek 引入了加权指数 m，使 Dum 的聚类 准则变成 m=2 时候的特例，从数学上说 m 的出现不自然且没有必要， 但如果不给以虑属度乘以权值，那么从硬聚类准则函数到软聚类目标 函数的推广准则是无效的，参数 m 又称为平滑因子，控制着模式早模 糊类间的分享程度，因此，要实现模糊 c 聚类就要选择一适合的 m， 然而最佳的 m 的选取目前还缺乏理论，监管存在一些经验值或经验范 围，但没有面向问题的优选方法，也缺少参数 m 的有效性评价准则 2） 尽管模糊聚类是一种无监督的分类，但现在的聚类算法却=需要应用 聚类原型的先验条件，否则算法会产生误导，从未破坏算法的无监督 性和自动化。 3） 因为模糊聚类目标是非凸的，而模糊 C 均值聚类算法的计算过程又是 迭代爬山，一次很容易陷入局部极值点，从而得不到最优解或满意解， 同时，大数据量下算法耗时也是困扰人们的一大难题，这 2 个问题目 前还不能得到全面的解决。 4） FCM 类型的聚类算法属于划份方法，对于 1 组给定的样本集，不管数 据中有无聚类结构，也不问分类结果是否有效，总把数据划分到 C 个 子类中，换言之，现有的聚类分析与聚类趋势，以及有效分析是隔离 的分离得。 5） FCM 的聚类算法是针对特征空间中的点集设计的，对于特殊类型的数 据，比如在样本每维特征的赋值不是一个数，而是一个区间。集合和 模糊数时，FCM 类型的算法无法直接处理 模糊 C 均值聚类算法存在上述缺点，改进的算法正确率能达到更高。Fcm 算法在处理小数据集的时候是有效的，但随着数据容量和维数的增加，迭代 步骤会显著增加，而且在迭代的每一步都要对整个数据集进行操作，无法满 足数据挖掘时的需要。 改进算法的思想是首先采用随机抽样的办法，从数据集中选取多个样本， 对每个样本应用 FCM 算法，将得到的结果作为初始群体，然后再利用遗传算 法对聚类结果进行优化，选取其中的最优解做为问题的输出，由于采样技术 显著的压缩了问题的规模，而遗传又可以对结果进行全局最优化处理，因此 在时间性能和聚类质量上都能获得较满意的结果。 遗传算法是美国 Michigon 大学的 John Holland 研究机器学习时创立的 一种新型的优化算法，它的主要优点是：遗传算法是从一系列点的群体开始 搜索而不是从单个样本点进行搜索，遗传算法利用适应值的相关信息，无需 连续可导或其他辅助信息，遗传算法利用转移概率规则，而非确定性规则进 行迭代，遗传算法搜索过程中，以对群体进行分化以实现并行运算，遗传算 法经过遗传变异和杂交算子的作用，以保证算法以概率 1 收敛到全局最优解 —具有较好的全局特性，其次遗传算法占用计算机的内存小，尤其适用计算 复杂的非线性问题。 遗传算法的设计部分
    （1） 种群中个体的确定 聚类的关键问题是聚类中心的确定，因此可以选取聚类中心作为种 群的个体，由于共有 C 个聚类中心，而每个聚类中心是一个 S 维的实数 向量，因此每个个体的初始值是一个 c*s 维的市属向量。 （2） 编码 常用的编码方式有二进制与实数编码，由于二进制编码的方式搜索 能力最强，且交叉变异操作简单高效，因此采用二进制的编码方式，同 时防止在进行交叉操作时对优良个体造成较大的破坏，在二进制编码的 方式中采用格雷码的编码形式。 每个染色体含 c*s 个基因链，每个基因链代表一维的数据，由于原 始数据中各个属性的取值可能相差很大，因此需首先对数据进行交换以 统一基因链的长度，可以有以下两种变换方式。 1 扫描整个数据集，确定每维数据的取值范围，然后将其变换到同 一量级，在保留一定有效位的基础上取整，根据有效位的个数动态的计 算出基因链的长度。 2 对数据进行正规化处理，即将各维数据都变换到相同的区间，可 以算出此时的基因链长度为 10。 （3） 适应度函数 由于在算法中只使用了聚类中心 V，而未使用虑属矩阵 u,因此需要 对 FCM 聚 类 算 法 的 目 标 函 数 进 行 改 进 ， 以 适 用 算 法 的 要 求 ， 和目标函数是等价的，由于遗传算法的 适用度一般取值极大，因此可取上式的倒数作为算法的使用度函数。 （4） 初始种群的确定 初始种群的一般个体由通过采样后运行 FCM 算法得到的结果给出， 另外的一般个体通过随机指定的方法给出，这样既保证了遗传算法在运 算之初就利用背景知识对初始群体的个体进行了优化，使算法能在一个 较好的基础上进行，又使得个体不至于过分集中在某一取值空间，保证 了种群的多样性。 （5） 遗传操作 选择操作采用保持最优的锦标赛法，锦标赛规模为 2，即每次随机取 2 个个体，比较其适应度，较大的作为父个体，并保留每代的最优个体 作为下一代，交叉方式一般采用单点交叉或多点交叉法进行，经过试验 表明单点交叉效果较好，因此采用单点交叉法，同时在交叉操作中，应 该对每维数据分开进行，以保证较大的搜索空间和结果的有效性，变异 操作采用基本位变异法。 （6） 终止条件的确定 遗传算法在以下二种情况下终止 a 最佳个体保持不变的代数达到设定的阈值 b 遗传操作以到达给定的最大世代数 算法具体步骤如下 1 确定参数，如聚类个数 样本集大小 种群规模 最大世代数 交叉概率 和变异概率等。
    2 对数据集进行多次采样并运行 FCM 算法，得到初始种群的一般个体， 通过随机制定产生另一半个体。 3 对数据集进行正规化处理并编码。 4 计算初始种群中个体的适应度。 5 对种群进行遗传操作产生下一代，在操作的过程中，应该排除产生的 无效个体。 6 计算个体的适应度，如果满足终止条件，则算法结束，否则转到 5 继 续 在理论上讲进行遗传操作的样本容量越大，聚类的误差越小，由 于采样技术显著压缩了问题规模，而遗传算法又可以对全局进行最优化 处理，因此改进的算法在时间与性能上都能获得较满意的结果，此算法 利用采样技术来提高算法的运行速度，利用遗传算法对聚类进行优化， 避免陷入局部最优解，在性能上相比于传统的模糊 C 均值聚类算法获得 较大提高。 算法实现 ·采用 VC++进行编写 文档的读取 #include "data.h" //函数定义 double **DataRead(char*name,int row,int col) { double **p=new double* [row]; ifstream infile; infile.open(name,ios::in); for(int i=0;i>p[i][j]; } } infile.close(); cout<<"成功读取数据文件:"<
    //释放内存 for(i=0;i
    double* b=new double[col]; double* c=new double[row]; //矩阵每列的最小值 //矩阵列元素 for(i=0;ia[i]) { a[i]=c[j]; } //取出该列的最小值 if(c[j]
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料