没有合适的资源?快使用搜索试试~ 我知道了~
模糊C均值聚类算法的C++实现代码.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 47 浏览量
2022-11-04
10:03:10
上传
评论
收藏 701KB PDF 举报
温馨提示
试读
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,或者叫定义在论域 X={x}上的模糊子集
A
。对于有限个对
~
象 x
1
,x
2
,……,x
n
模糊集合
A
可以表示为:
~
A {(
A
(x
i
), x
i
) | x
i
X }
(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 个向量 x
i
(i=1,2,…,n)分为 c 个模糊组,并求每组的聚类中心,
使得非相似性指标的价值函数达到最小。FCM 与 HCM 的主要区别在于 FCM 用模糊
划分,使得每个给定数据点用值在 0,1 间的隶属度来确定其属于各个组的程度。
与引入模糊划分相适应,隶属矩阵 U 允许有取值在 0,1 间的元素。不过,加上
归一化规定,一个数据集的隶属度的和总等于 1:
u
i1
c
ij
1,j 1,..., n
(6.9)
那么,FCM 的价值函数(或目标函数)就是式(6.2)的一般化形式:
m 2
J (U , c
1
,..., c
c
)
J
i
u
ij
d
ij
, (6.10)
i1 i1 j
c c n
这里 u
ij
介于 0,1 间;c
i
为模糊组 I 的聚类中心,d
ij
=||c
i
-x
j
||为第 I 个聚类中
心与第 j 个数据点间的欧几里德距离;且
m
1,
是一个加权指数。
构造如下新的目标函数,可求得使(6.10)式达到最小值的必要条件:
J (U , c
1
,..., c
c
,
1
,...,
n
) J (U , c
1
,..., c
c
)
j1
j
(
u
ij
1)
i1
m 2
u
ij
d
ij
j
(
u
ij
1)
i1 j j1 i1
c n n c
n
c
(6.11)
这里
j
,j=1 到 n,是(6.9)式的 n 个约束式的拉格朗日乘子。对所有输入参量
求导,使式(6.10)达到最小的必要条件为:
u
c
i
j1
n
j1
n
m
ij
x
j
(6.12)
m
u
ij
和
d
ij
k 1
d
kj
由上述两个必要条件,模糊 C 均值聚类算法是一个简单的迭代过程。在批处理方
式运行时,FCM 用下列步骤确定聚类中心 c
i
和隶属矩阵 U[1]:
步骤 1:用值在 0,1 间的随机数初始化隶属矩阵 U,使其满足式(6.9)中
的约束条件
步骤 2:用式(6.12)计算 c 个聚类中心 c
i
,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):
c
u
ij
1
2 /(m1)
(6.13)
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 算法得到的结果给出,
另外的一般个体通过随机指定的方法给出,这样既保证了遗传算法在运
算之初就利用背景知识对初始群体的个体进行了优化,使算法能在一个
较好的基础上进行,又使得个体不至于过分集中在某一取值空间,保证
了种群的多样性。
剩余20页未读,继续阅读
资源评论
G11176593
- 粉丝: 6646
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功