基于改进FCM聚类的复杂网络节点重要性评估方法(6)
时间:2017-05-22 20:05 来源:毕业论文 作者:毕业论文 点击:次
该算法最早从硬聚类目标函数的优化中导出，为了借助目标函数求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dunn[11]首先将其推广到加权WGSS函数，后来由Bezdek[11]扩展到加权WGSS的无限族，形成了FCM聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已形成庞大的体系。 3.3.2 FCM算法介绍 通过引入隶属度函数来表示每个数据属于不同类别的程度,对数据进行软划分,首先估计聚类的中心,其次反复调整聚类中心,使数据集中的每个点距离每个中心的距离之和达到最小或满足终止条件。 设n个数据样本集合为 ，xi = { xi1, xi2,…, xid }T (∈Rd)，为样本xi的特征向量，xi∈X是表示单个数据节点i的矢量。c（ ）是要将数据样本分成的类别数目；第i类的聚类原型为 ，则 构成聚类矩阵原型； 是隶属度矩阵，其中 表示样本 对于聚类原型 的隶属程度，且满足以下条件，并在下列情况下模糊K均值方法能够使得簇内离差平方和达到最小值： 它是由下面的目标函数定义的： (4) 根据距离的选择的定义 是 和 之间的平方距离，这对于简化通过d2ik的进一步表示, 为范数，同 一样，都是表示两者相似度。m是模糊指数，范围是（1， ）。它决定了最终解决方案的模糊度数，即组之间的重叠度。m=1时，解决方案是一个硬划分。当m接近于无穷大，解决方案就会接近于最高的模糊度，聚类效果较差，一般取值范围为 。目标函数J提供的最小化方法提供了隶属函数的解决方式： 算法步骤 模糊C-均值聚类算法时一种逐步迭代的算法，每步迭代都沿着目标函数减小的方向进行。首先，需要对一些数据进行初始化： 1) 待聚类数据总个数n; 2) 聚类类别数c, ; 3) 迭代停止阈值 ； 4) 聚类原型模式 ， ； 5) 迭代计数器 ， ； 6) 加权指数m, m一般情况选择2； 初始化成功后，开始实现具体算法： 1. 随机初始化隶属矩阵U; 2. 根据公式（6）算出每个聚类中心的坐标; 3 .更新隶属矩阵; 在此是聚类中心 和点i的欧氏距离，欧式距离计算公式 用公式（5）进行更新 4 .如果隶属矩阵每个元素更新前后基本不变，则终止算法，否则转到2。对于每个点它属于对应隶属度最大的聚类中心。 3．4 FCM聚类算法存在的弱点 聚类算法的性能和数据集的结构是密切相关的，没有普遍适用的万能的聚类算法，因此不断有新的聚类算法被提出或者改进。由虽然 FCM 聚类算法是目前为止研究最广泛、理论最成熟的模糊聚类算法，但该类方法也还存在着弱点。由于该算法是通过极小化目标函数而求得最优解的，该算法随机选取 C（C为聚类数)个点作为初始聚类中心，通过一个迭代过程完成聚类。该算法也有它固有的不足：算法在进行聚类以前要求知道C值，这对于没有经验的用户来说很困难；初始聚类中心的选择对于最后的聚类结果有很大的影响,如果初始聚类中心选择不当，目标函数有可能得不到全局最优，而陷入局部极小值。 （1）FCM 类型的聚类分析是一种划分的方法，不管数据集在特征空间中是否存在自然结构，给定一个分类数 C，就输出数据集的 C 划分。显然，算法存在一个不合理的假设：待分析的数据集是可聚的。这一不合理的假设的存在使得现有 FCM 类型的算法不分析数据集的可聚性，而硬性对数据施加一定的隶属关系。这样造成了即使数据在特征空间中是均匀分别的，不存在任何聚类结构，FCM 算法也毫无道理地对数据集进行模糊C 划分，从而使得对聚类结果分析和解释困难。 (责任编辑：qin) |