改进算法的思想是首先采用随机抽样的办法,从数据集中选取多个样本,
对每个样本应用 FCM 算法,将得到的结果作为初始群体,然后再利用遗传算
法对聚类结果进行优化,选取其中的最优解做为问题的输出,由于采样技术
显著的压缩了问题的规模,而遗传又可以对结果进行全局最优化处理,因此
在时间性能和聚类质量上都能获得较满意的结果。
遗传算法是美国 Michigon 大学的 John Holland 研究机器学习时创立的
一种新型的优化算法,它的主要优点是:遗传算法是从一系列点的群体开始
搜索而不是从单个样本点进行搜索,遗传算法利用适应值的相关信息,无需
连续可导或其他辅助信息,遗传算法利用转移概率规则,而非确定性规则进
行迭代,遗传算法搜索过程中,以对群体进行分化以实现并行运算,遗传算
法经过遗传变异和杂交算子的作用,以保证算法以概率 1 收敛到全局最优解
—具有较好的全局特性,其次遗传算法占用计算机的内存小,尤其适用计算
复杂的非线性问题。
遗传算法的设计部分
(1) 种群中个体的确定
聚类的关键问题是聚类中心的确定,因此可以选取聚类中心作为种
群的个体,由于共有 C 个聚类中心,而每个聚类中心是一个 S 维的实数
向量,因此每个个体的初始值是一个 c*s 维的市属向量。
(2) 编码
常用的编码方式有二进制与实数编码,由于二进制编码的方式搜索
能力最强,且交叉变异操作简单高效,因此采用二进制的编码方式,同
时防止在进行交叉操作时对优良个体造成较大的破坏,在二进制编码的
方式中采用格雷码的编码形式。
每个染色体含 c*s 个基因链,每个基因链代表一维的数据,由于原
始数据中各个属性的取值可能相差很大,因此需首先对数据进行交换以
统一基因链的长度,可以有以下两种变换方式。
1 扫描整个数据集,确定每维数据的取值范围,然后将其变换到同
一量级,在保留一定有效位的基础上取整,根据有效位的个数动态的计
算出基因链的长度。
2 对数据进行正规化处理,即将各维数据都变换到相同的区间,可
以算出此时的基因链长度为 10。
(3) 适应度函数
由于在算法中只使用了聚类中心 V,而未使用虑属矩阵 u,因此需要
对 FCM 聚 类 算 法 的 目 标 函 数 进 行 改 进 , 以 适 用 算 法 的 要 求 ,
和目标函数是等价的,由于遗传算法的
适用度一般取值极大,因此可取上式的倒数作为算法的使用度函数。
(4) 初始种群的确定
初始种群的一般个体由通过采样后运行 FCM 算法得到的结果给出,
另外的一般个体通过随机指定的方法给出,这样既保证了遗传算法在运
算之初就利用背景知识对初始群体的个体进行了优化,使算法能在一个
较好的基础上进行,又使得个体不至于过分集中在某一取值空间,保证
了种群的多样性。