基于遗传算法的动态聚类方法

1、 1999年 10月 系统工程理论与实践 第 10期基于遗传算法的动态聚类方法 戴晓晖 , 李敏强 , 寇纪淞(天津大学系统工程研究所 , 天津 300072摘要 : 针对常规动态聚类方法对初始聚类中心的敏感性以及聚类结果与样本输入次序有关等问题 , 本文另辟蹊径 , 提出了一种基于 GA 的动态聚类方法 , 并将它应用到数据库的数据分析中 . 计算结果表明 , 该方法是一个具有全局最优解的动态聚类方法 , 其结果明显好于 K 2均值聚类算法 .关键词 : 遗传算法 ; 动态聚类 ; 全局优化 ; 数据分析A D ynam ic C lustering M ethod Based on Gen

2、etic A lgo rithm s DA I X iao 2hu i , L IM in 2qiang , KOU J i 2song(In stitu te of System s Engineering , T ian jin U n iversity , T ian jin 300072Abstract : To so lve the p rob lem of sen sitivity w ith the o riginal clu stering cen ter andclu stering resu lts depended on the o rder of the inpu t

3、examp le in common dynam icclu stering algo rithm , a new dynam ic clu stering m ethod based on genetic algo rithm s isp resen ted in th is paper and is app lied to data analysis in databases . Compu ting resu ltsindicate that the m ethod is a dynam ic clu stering algo rithm w ith global op ti m iza

4、ti on andis superi o r to K 2m ean s algo rithm .Keywords : genetic algo rithm s ; dynam ic clu stering ; global op ti m izati on ; data analysis1引言聚类分析就是通过无监督训练将样本按相似性分类 , 把相似性大的样本归为一类 , 占据特征空间的一 个局部区域 , 而每个局部区域的聚合中心又起着相应类型的代表的作用 . 聚类分析一方面可以作为一种有 效的信息压缩与提取手段 , 另一方面又往往是其它模式识别的基础 . 在各类聚类分析中 , 动态聚类方法是

5、 较普遍采用的方法 . 现有的各种动态聚类方法都是先根据一定的经验准则选取某些聚类参数 , 诸如希望的 聚类数 、 最小标准差 、 初始聚类中心 、 聚类中心间的最小距离等 , 然后根据距离最近的原则对各样本进行依 次训练调节 , 直至目标函数即各样本到相应聚类中心距离平方和收敛到最小为止 . 这些算法的计算结果与 这些参数的设置是否得当至关重要 , 因此在设置这些参数之前往往需要对样本数据进行必要的分析研究 . 这在数据量较大 , 特别是在高维情况下 , 要得到合理的参数尤为困难 , 只能通过多次实验 1. 由于在聚类算 法中自变量 (待聚类点的坐标值 与目标函数都是离散量 , 存在着许多局

6、部极值 , 而通常的方法又没有相应 接受劣解的机制 , 因此初始聚类中心和样本输入次序对最终结果有着很大的影响 . 经常采用的对策是用若 干不同的初始中心分别进行聚类 , 然后选择最满意的一个作为最终聚类结果 . 这种方法应用在大型数据库 的数据分析中 , 不仅工作量巨大 , 而且不能保证聚类结果的最优性 .遗传算法 (Genetic A lgo rithm GA 是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模 型 , 它是由美国 M ich igan 大学的 Ho lland 教授于 1975年首次提出的 2, 这是一种新的全局优化搜索算法 , 其简单通用 , 鲁棒性强 , 适于并行

7、处理 , 已经广泛地应用在计算机科学 3、 优化调度 4、 运输问题 5、 组合优收稿日期 :1997210226资助项目 :国家自然科学基金资助项目 (79400013, 69574022化 6等领域 . 针对动态聚类算法的离散性及局部极值特征 , 本文运用 GA 来解决动态聚类的全局优化问 题 .2 GA 动态聚类方法2. 1聚类分析的数学模型设目标函数 J =m in6Pr =16m ri =1 X(r i-C r 2其中 :聚类中心 C r =mr 6m ri =1X(r i (i =1, 2, , m r , ; r =1, 2, , P 6Pr =1m r =Nm r 为属于 r

8、类的样本 (记录 个数 ; X (r i表示样本 X i 属于第 r 类 ; N 为样本 (记录 数 ; P 为聚类中心数 (2P N -1 .2. 2染色体的构造通过对模型的分析 , 我们采用自然数编码 , 具体如下 :用 X =(S 1, S 2, , S N 表示 GA 的染色体结构 , X 为 1×N 维行向量 , S l 为第 l 位的基因 , 则染色体 要求如下 :S l 1,2, , P , l =1, 2, , N2. 3适应度的选择选择 f =C m ax -m in 6Pr =16m ri =1 X(r i-C r 2作为适应度函数 , 其中 , C m ax =

9、6N i =16Nj =1 X i -X j 2, 把求最小极值问题转化为求最大极值问题 , 这样在选择规则中就可以使用赌轮策略 .2. 4遗传算子遗传算子包括选择 、 交叉 、 变异和进化逆转等过程 . 1 选择规则按照 2. 3选定的适应度函数 , 使用赌轮策略进行选择 , 并且保留上一代 M 个较优的个体做为下一代的 样本 , 来保证算法的收敛 .2 交叉规则交叉按照 OX 规则进行 3. 3 变异规则由于在选择机制中采用了保留最佳样本方式 , 以及引入了 “进化逆转” 操作技术 , 为保持群体内个体的 多样性 , 我们采用连续多次对换的变异技术 , 使可行解有较大顺序排列上的变化 ,

10、以抑制 “进化逆转” 的同 化作用 . 若发生变异 , 则用随机方法产生交换次数 K , 对所需变异操作的染色体进行 K 次对换 (对换的两 码位也是随机产生的 .4 “进化逆转” 规则引进 “进化逆转” 操作的主要目的是改善遗传算法的局部搜索能力 . 在遗传算法中 , “逆转” 是一种常见 的 “变异” 技术 . 我们使用的 “进化逆转” 是一种单方向的 (朝着改进的方向 和连续多次的 “逆转” 操作 , 即对 于给定的串 , 若 “逆转” 使串 (可行解 的适应度提高 , 则执行逆转操作 , 如此反复 , 直至不存在这样的逆转操 作为止 . 这一操作实际上使给定的串改良到它的局部极点 ,

11、这种局部爬山能力与基本遗传算法的全局搜索 能力相结合在实验中显示了良好的效果 .2. 5基于 GA 的动态聚类方法的具体迭代步骤1 输入 P , pop size , P c , P m 及 gen 2m ax ;2 置 G =0(G 为代数 ;901第 10期 基于遗传算法的动态聚类方法3 生成初始群体 ;4 评价各初始母体的适应度 ;5 选择母体 , 进行交叉 、 变异 、 进化逆转等操作 , 生成新一代母体群 ;6 计算新的聚类中心和累积类内距离平方和 ;7 评价新一代母体群的适应度 ;8 若迭代次数已达最大迭代次数 , 则输出结果 ; 否则 G =G +1转入第 5 步 .输入的控制参

12、数 :聚类中心数 P 、 群体规模 pop size 、 交叉概率 P c 、 变异概率 P m 和最大迭代次数 gen 2 m ax .3数据聚类研究为了验证上述算法的有效性 , 我们以某一数据库中的记录 (记录值为 :(0, 1 、 (1, 0 、 (1, 1 、 (2, 2 、 (2, 3 、 (3, 2 、 (5, 6 、 (6, 5 、 (6, 6 、 (7, 7 、 (7, 8 、 (8, 7 等 12个记录 为例 , 采用 K 2均值聚类算法 (以前 4个样 本为初始聚类中心 和遗传算法分别进行计算 , 计算结果如表 1:表 1K 2均值聚类算法 基于 GA 的动态聚类算法样本样

13、本 类别 样本 类别 样本 类别 样本 类别117411732284218332943193431044210453114521146312462124目标函数 :12. 833目标函数 :5. 333遗传算法的运行设置参数如下 :P =4, pop size =30, P c =0. 7, P m =0. 001和 gen 2m ax =1000. 运行 50次 , 平均收敛代数为 156代 .由仿真结果表明 , 常规聚类方法因不能有效地处理局部极值问题 , 因此当初始聚类中心在整个样本空 间不平衡时 , 它很难将这种不平衡纠正过来 , 从而导致聚类结果对初始聚类中心的选取有着很大的敏感 性

14、 ; 而基于 GA 的动态聚类方法因具有很好的处理局部极值能力 , 因此对初始聚类中心的选取以及样本的 输入次序没有任何要求 . 另一方面 , 从它们各自的收敛速度上来看 , 基于 GA 的动态聚类方法的收敛速度 较慢 , 但是这显然比用常规方法对不同初始聚类中心进行聚类来获取全局最优解要有效的多 .4结论本文提出了一种基于 GA 的动态聚类方法 , 它可以得到全局最优解 , 从而很好地解决了其它动态聚类 方法中普遍存在的初始聚类中心敏感性以及聚类结果与样本的输入次序有关等问题 , 为聚类分析提供了 一个新的思路 . 计算结果表明 , 该方法不仅可以用于分析大型数据库中的数据 , 而且可以辅助

15、指导决策 . 对于如何提高 GA 的收敛效率等问题尚需进一步研究 .参考文献 :1黄振华 , 吴成一 . 模式识别原理 . 杭州 :浙江大学出版社 . 1989.2 Ho lland T H . A dap tati on in natu ral and artificial system . A nn A rbo r :T he U n iversity of M ich igan P ress , 1975. (下转第 116页 011系统工程理论与实践 1999年 10月A 1 A 2 A mZ T = Z 11Z 21 Z m 1 Z 12Z 22 Z m 2Z 1k Z 2k Z m

16、 S 1 S 2 S k因 S i 为效益型指标 , 对每一个属性 S i (i =1, 2, , k , A j (j =1, 2, , m 可按其大小排序 : 1 2 mA 11A 12 A 1m A 21A 22 A 2m A k 1A k 2 A S 1 S 2 S k其中 S i :A i 1, A i 2, , A i m , A ij A (i =1, 2, , k ; j =1, 2, , m 是按第 i 个属性对 m 个方案的排序 . 如果把 S i 看成 E i (i =1, 2, , k , 即 k 个专家 , 并且再假设 E i 有序 (可按 S i (i =1, 2,

17、 , k 的重要性决 定 , 这样就转化为前文中的排序矩阵 EA , 于是可以利用 n 维足码选择定位法解决多目标决策问题 .6结束语本文给出了一种专家数据信息后处理的群排序方法 3, 具有简洁 、 易于操作等特点 . 它避开了确定专 家权重的困难 , 采用了较为容易的确定专家顺序的方法 , 具有客观实用性 . 对于专家和方案均较多的情形 , 可以利用计算机进行排序 .参考文献 :1陈明琴 , 何湘藩 . 二维足码选择定位法 . 系统工程理论与实践 , 1997, 17(2 :8387.2王应明 , 傅国伟 . 关于专家最优综合评价模型的改进和完善 . 系统工程 , 1992, (6 :515

18、7.3张四维 , 刘进生 . 专家数据信息后处理的群排序方法 . 系统工程理论与实践 , 1995, 15(2 :4650. 4 H e X iangfan , Chen M ingqin . A new m ethod of group o rdering :info rm ati on flow ed m ethod . M CDM : T heo ry and A pp licati on , SC I 2T ECH Info rm ati on Services , A ugu st , 1995:203205.(上接第 110页 3 Go ldberg D E . Genetic algo rithm s in search , op ti m izati on and m ach ine learn ing .