模糊聚类:遗传算法

2024-10-01

模糊聚类:遗传算法（精选9篇）

模糊聚类:遗传算法篇1

模糊聚类以Zadeh提出的模糊集理论[1]为基础,描述了样本在性态和类属方面存在着不确定性,能够客观地反映现实世界,已经成为聚类分析研究的热点。在众多基于目标函数的模糊聚类算法中,模糊C-均值聚类算法[2]理论最完善、应用最为广泛。模糊C-均值聚类算法采用一种迭代的爬山技术来寻找最优解的局部搜索算法,它对初始化值非常敏感而容易陷入局部极小值,对于这一缺点学者们提出了一些改进方法[3,4]。

遗传算法[5]是一种模拟自然进化过程搜索最优解的全局优化方法,是一种与求解问题无关的算法模式,能够有效解决模糊C-均值聚类算法对初始值敏感的问题。文献[6]提出用模糊C-均值聚类算法代替遗传算法的交叉操作,从而实现遗传模糊聚类算法,但由于每次都要运行模糊C-均值聚类算法,且没有对遗传算法做其他改变,所以运行时间和聚类效果不佳。文献[7]也是在遗传算法中引入了模糊C-均值聚类算法,在遗传操作之后,用模糊C-均值聚类算法局部寻优,并使用最短距离法进行整体交叉的操作,提高了算法的全局搜索能力,聚类效果进步不少,但是难以改变时间消耗的问题。本文在这些研究的基础上对遗传算法进行了改进,使得聚类在运行效率和聚类质量上都有一定的提高。

1 遗传模糊聚类

模糊C-均值聚类算法因对初始值非常敏感而容易陷入局部最优,在迭代过程中由于保证不了向着全局最优的方向搜索,所以也就不能保证收敛到全局最优。算法是否能够收敛到全局最优值,这在一定程度上依赖初始值的选择,如此重要的选择让那些学者们在初始化数据时总是想方设法地使用一些更好的办法。

遗传算法是一种最受关注的全局优化算法之一,通过模拟生物进化和遗传过程中个体的选择、交叉和变异机理,来完成搜索问题最优解的过程。它以群体搜索技术进行操作,用遗传算子交换个体间的信息,经过对种群中的个体适应度的评价,使得群体中的个体一代一代地不断进化,并渐渐逼近最优解。它以决策变量的编码作为运算对象,以目标函数值作为搜索信息,从多个点同时搜索,并且使用概率搜索技术,使得该算法有很强的寻优能力,即使是在很复杂的解空间中,也很快就能找到良好的解。遗传算法正是具有这些优点,才能够有效解决模糊C-均值聚类算法易陷入局部极小值的问题。模糊C-均值聚类算法是局部寻优,遗传算法是全局寻优,两者结合起来使用,可以同时体现两个算法的寻优能力,提高了收敛速度,能更好地解决聚类问题。

2 遗传模糊聚类改进策略

目前对遗传算法应用到聚类中已经有许多研究[6,7,8,9],但遗传算法仍然存在局部搜索能力差、容易早熟、效率不高[10]等缺陷,针对这些问题提出一种基于改进遗传算法的模糊C-均值聚类算法,该算法使用遗传算法对初始聚类中心进行优化,而后执行模糊C-均值聚类算法。

2.1 主、副种群隔离机制

传统的遗传算法将个体进化过程放在一个种群内反复进行,这样做使得种群内基因交流畅通,个体很难向着各自的方向发展,从而导致种群多样性的不足。另一个原因是采用比例选择算子有缺陷,当种群中有个别个体的适应度值远远大于种群的平均适应度值时,这些个体将迅速扩张,从而使种群中个体相似度降低,破坏种群多样性。遗传算法全局搜索能力不强的主要原因是种群多样性不足,而小生境技术的引入可以解决这一问题。

种群依据离最优种子的距离动态地分成主种群和副种群两部分,对主、副种群隔离进化,提高算法效率,缩短遗传算法的运行时间。通过设定一个自适应的距离,该距离能够隔离出一个随当前最优种子变化的小生境。针对小生境外部,用较大变异概率的方法实现种群的多样性,而对于小生境内部,主要选择以交叉为主的方法来稳定选择压力,如此划分的目的是使种群的多样性和选择压力达到一种平衡状态[11]。

2.2 实数编码机制

遗传算法主要通过遗传操作对种群中的个体进行重新组成,通过不断优化种群中的个体,渐渐逼近问题的最优解,直至最后达到搜索到最优个体的目的。对于一些高维、高精度要求的优化问题,使用二进制编码将会带来计算误差、编码空间Hamming 悬崖等诸多问题[12,13],为了克服这些不足,提出了实数编码的方法。实数编码是每个个体向量被编码成一个与解向量相同长度的实数向量。遗传操作过程中,遗传空间就是问题空间,个体直接反映了问题的规律与特性。

在遗传算法编码中采用了把聚类中心作为个体的实数编码方式,这种表示方法使用决策变量的真实值来编码,达到较高精度要求,并且个体搜索空间比较大,利于全局搜索。

2.3 双精英参与机制

为了防止己经得到的最优种子不被淘汰掉,所以经常使用精英保留策略来保证算法的收敛性。除此之外,精英种子还能够引导种群向最优值搜索。然而,保留的精英种子和引导搜索的精英种子可能不是同一个种子;若发现某精英种子是已经搜索到的局部极小值时,则需要把它作为己经获得的最优值保存起来,而不能让它再引导种群搜索。因此,为了划分出精英保存策略的功能,提出了双精英种子参与机制,一个是保存起来的己经获得历史局部极小值的精英种子,一个则是作为前最优值引导搜索的精英种子。为此,第一步是采用精英保存策略保存精英种子,而下一代的交叉、变异操作需要引进当前精英个体,使其引导种群向全局最优解逼近;第二步是依照个体适应度值,采用轮盘赌选择策略把当前群体中的个体选出来,并对主、副种群进行相应策略的交叉、变异操作,以提高种群的平均适应度和增加种群的多样性。

3 算法描述

设N为种群总规模,N1为主种群的种子个数,N2为副种群的种子个数,初始化时N1和N2约为种群总规模N的二分之一。种群在主副种群距离界限值不断减小的情况下逐步进化,进化中主种群进化比较快,副种群进化相对比较慢,究其原因是主种群里保持比较大的选择压力,而副种群里因变异概率和交叉概率比较大选择压力比较小。

算法步骤如下:

(1)初始化参数,生成初始种群;

(2)计算各个个体适应度值;

(3)判断是否满足停止准则,满足则执行(4),否则执行(9);

(4)求出N1,N2,其中N1=INT(N×0.5) ,N2=N—N1;

(5)求出当前最优种子,并计算各种子到当前最优种子的欧氏距离;

(6)计算主副种群的距离界限值L,L为最大距离×0.5和排序后距离向量的中位数,二者中的最小值。根据L划分主副种群并计算N1、N2,设D为个体与当前最优种子的距离,ε为一个设定的极小值,则:

如果 L>ε, N1={D≤L的个体},N2={D>L的个体};

否则,N1={D>L的个体和当前最优种子},N2=空集。

(7)对主种群和副种群里的种子按各自策略分别进化;

(8)将进化后的主种群和副种群混合生成新种群,令T=T+1,T为遗传代数,返回(2);

(9)求出最优个体;

(10)执行模糊C-均值聚类算法,输出聚类结果。

4 实验仿真及应用

4.1 仿真结果

本文应用改进的遗传模糊聚类算法(简称为IGAFCM)对标准IRIS数据集进行了仿真实验,并与模糊C-均值聚类算法(FCM)、遗传模糊混合算法(HGFA)相比较,三种算法的比较结果如图1和表1。

图1中T表示进化代数,J表示目标函数值,其定义为: $J = \sum_{i = 1}^{c} \sum_{j = 1}^{n} μ_{i j}^{m} ∥ x_{j} - v_{i} ∥^{2}$ ,c代表聚类中心数,n代表样本总数,m为模糊因子(取值一般为2),U=[μij]c×n表示划分矩阵,‖xj-vi‖表示样本xj到聚类中心vi的欧式距离,其中,

图1中J-T曲线是目标函数值J跟随进化代数T的变化趋势。不难看出,随着进化的不断进行,三种算法都能达到相应的目标函数值。曲线变化表明,本文提出的改进算法在达到目标函数值的时候所用的迭代次数最少,即收敛速度要比其他两个算法快,充分体现该算法在收敛速度方面的优势。

三种算法从进化代数、误分数、误分率方面来比较。误分是指本属于某类的样本被错误地划分到其他类的样本,所有类中被错误划分的样本个数之和称为误分数。误分率定义为:

误分率 $= \frac{误分数}{样本总个数} \times 100 %$ 。

表1中数据显示,本文算法在进化次数上最少,误分数最少,误分率最低,即在聚类精度上有一定的提高,从而保证了聚类的质量。

4.2 算法应用

为了进一步验证该算法的有效性并加以利用,取一组实际数据作为测试用例,数据集来自某次学生考试成绩库,试卷包括五个大题,每题20分。实验中抽取总得分为70—80的100位考生的考试数据进行模糊聚类分析。聚类结果如图2所示。

经过大量实验得出聚类结果可有效地分为五个类别,并将聚类后的数据作均值化处理,结果发现五个类别中有一类是各题得分比较均匀,其他四类中总有某一个题目得分比较低,这就给我们提供了聚类的依据,能够充分挖掘、分析试卷数据。

显然,基于本文算法的试卷分析和传统的试卷分析都是把学生成绩作为分析对象,但传统的试卷分析只是考虑了学生的成绩排名情况,所以基于本文算法的试卷分析要比传统的试卷分析有内涵。按照传统的试卷分析方法来看,本文所列举的100位考生应属于一个类别,而基于本文算法的试卷分析将学生依据题目得分高低划分为有意义的若干类别,可以更加深刻和准确地发现这些学生对知识点的理解程度有所不同,掌握知识点的能力不尽相同,这也为以后的教学工作提供了改进的思路和方法,具有一定的现实意义。

5 结语

由于模糊C-均值聚类算法强烈依赖于参数初始化的优劣,而一个靠近最优解的初始化方法将以更少的迭代步骤收敛到全局最优解,所以采用遗传算法初始化聚类中心,并提出了改进的遗传模糊聚类。仿真实验结果体现了改进算法的优越性,并将该算法应用到试卷数据聚类分析中,深层次的挖掘出隐含的信息,有目的、针对性地指导个性化教学。虽然改进后的算法提高了聚类质量,但还遗留许多问题丞待解决,例如在处理数据的维度高、量大时收敛速度比较慢,消耗时间比较多;增加动态聚类分析方法的研究,以便处理数据动态增加的情况;复杂类型数据集聚类分析的研究,寻求新的度量方法,以便处理复杂的数据集等等。

模糊聚类:遗传算法篇2

基于遗传算法的航空发动机模糊优化控制

为适应航空发动机非线性的控制要求,采用基于多个修正因子的模糊控制方法对航空发动机的控制器进行设计,利用改进的遗传算法对模糊控制器的多个修正因子进行参数优化,并对航空发动机数学模型进行仿真试验.从仿真的结果看,改进遗传算法的收敛性比较强,收敛速度快;仿真优化后的修正因子取值在满足一定范围时,控制系统能达到比较好的`控制效果.基于遗传算法参数优化的模糊控制器表现出比较好的控制性能.

作者：张世英胡宇朱杰堂作者单位：第二炮兵工程学院,西安,710025刊名：弹箭与制导学报 PKU英文刊名：JOURNAL OF PROJECTILES, ROCKETS, MISSILES AND GUIDANCE年，卷(期)：201030(2)分类号：V233.7关键词：遗传算法模糊控制修正因子航空发动机参数优化隶属度函数 genetic algorithm fuzzy control correction factor aeroengine parameter optimization membership function

模糊聚类:遗传算法篇3

关键词：交通流；模糊控制；遗传算法；信息融合；模式识别



中图分类号：F49文献标识码：A文章编号：16723198（2007）11005903

1模糊控制和遗传算法

人工智能技术可划分为传统人工智能技术（即专家系统）和处理数值计算的新人工智能技术，例如模糊逻辑，遗传算法和人工神经网络等。

1.1模糊控制原理

(1)模糊集合的运算。模糊集合理论的基本思想是把普通集合中的绝对隶属关系灵活化, 使元素对集合的隶属度从原来只能取{0,1}（正确或错误）中的值扩充到［0,1］区间中的任一数值。模糊集合是由隶属函数来刻画的。论域中的模糊子集是以隶属函数表征的集合。即由映射

μA∶U→［0，1］

u→μA(u)

确定论域的一个模糊子集A。μA称为模糊子集A的隶属函数，隶属度μA(u)说明u隶属于A的程度。常用的模糊集合运算主要有并、交以及补运算。

(2)模糊化，模糊推理及解模糊化。模糊控制系统主要包括三个过程:输入的模糊化、模糊推理和输出解模糊化。

①模糊化(fuzzification)。模糊化是将模糊控制器输入量的确定值转换为相应模糊语言变量值的过程，此相应语言变量值均由对应的隶属度来定义。本文选择三角形隶属函数，其曲线如图1所示。

图1三角形隶属函数曲线

其对应表达式为：

μx=1,如果x=B(x-A)/(B-A),如果B>x>A（C-x）/(C-B),如果C>x>B0,如果x≥C或者x≤A（1）

其中A、B和C为三角形隶属函数参数。

②模糊推理(fuzzy inference)。模糊推理是根据事先制定好的一组模糊条件语句构成的模糊控制规则，运用模糊数学理论对模糊控制规则进行计算推理，即根据模糊规则对输入的一系列条件进行综合评估，以得到一个定性的语言表示量。模糊控制规则采用“if…then…”形式，if部分是规则的前提，then部分是规则的结论。

③解模糊化(defuzzification)。模糊控制器经过模糊推理得出的模糊输出量必须经过精确化处理，将模糊量转换为清晰的数字量才能去控制对象，这就涉及到推理结果的解模糊化问题。解模糊化的方法主要有以下几种：最大隶属法、系数加权平均法、重心法以及隶属度限幅元素平均法。

常用的模糊推断过程如图2所示。图中 “V1”和“V2”分别代表两个输入变量，“O”代表输出变量, “Min”和“Max”分别表示合成和析取。图2采用三角形隶属函数，用去模糊化的方法从输出模糊集C'中提取输出函数的代表值。

1.2遗传算法简介

(1)选择、变异和交叉。

①选择。在本文中，选择根据每一染色体编码串评价指标的高低成比例的决定其选择概率。

②变异算子。基于构造支撑树的顺序编码，若采用简单的一点或多点交叉策略，必然以极大的概率产生不可行的染色体，因此本文采用与部分匹配交叉比较类似的交叉方法，方法如下：

a.随机在串中选择一个交配区域，如两父串及交叉区域选定为：A= 1 2︱3 4 5 6︱7 8 9B= 9 8︱7 6 5 4︱3 2 1

b.将B的交配区域加到A的前面或后面，A的交配区域加到B前面或后面得到：A＇=7 6 5 4︱1 2 3 4 5 6 7 8 9B＇=3 4 5 6︱9 8 7 6 5 4 3 2 1

c.在A＇和B＇中自交配区域后依次删除与交配区相同的城市码，得到最终的两子串：A″=7 6 5 4 1 2 3 8 9B″=3 4 5 6 9 8 7 2 1

③交叉算子。为了维持群体内的多样化，本文采用随机连续多次对换的变异技术，使可行解在顺序上有了较大的变化，以抑制交叉中有可能产生的同化作用。例如对于串A：

A=1 2︱3 4 5 6︱7 8 9

如果随机产生的交换点是2和7，则串中的第2点和第7点将对换，对换后，串A变为：A＇=1 7︱3 4 5 6︱2 8 9

由于经过一次对换后，A＇仍然有可能与A表示为同一个网络结构，所以本文采取连续多次的对换操作，来增强变异的效果。

(2)编码方式。由于遗传算法的进化过程是建立在编码机制基础上的，编码对于算法的性能如搜索能力和种群多样性等的影响很大。常见的遗传算法编码方式有二进制编码与实数编码两种。就二进制编码和实数编码比较而言，一般实数编码比二进制编码在变异操作上能够保持更好的种群多样性，但操作比较复杂，二进制编码比实数编码搜索能力强。本问题优化参数较少，故采用二进制编码。

2交通事件自动检测算法设计

2.1数据来源

受我国高速公路基础设施以及人力、物力的限制，现在国内还缺乏完整的实测数据，故本文采用VISSIM软件模拟的数据对模糊-遗传融合自动事件检测算法进行测试。模拟中，选择一段2.0km的单向两车道高速公路区段作为模拟目标路段，分别对不同交通条件下的交通流状况进行了160次模拟，包括60次非事件状态和100次事件状态。其中50 次事件数据用来构成训练样本值，其余的50次事件数据作为测试样本值。为研究事件和非事件条件下的交通流特性，在事件检测区位置上游150m处、300m处、400m处以及事件检测区位置下游150m处、300m处、400m处按车道和路宽分别设置车辆检测器，采集周期为20秒，采集的交通数据包括占有率和流量。把交通数据带入到模糊-遗传融合自动事件检测算法中，每组数据向量可得到一个模糊输出结果。最终的模糊输出被转化为两种输出状态，即状态0和1，它们分别代表非事件状态和事件状态。

图3基于模糊控制的事件检测算法的系统结构图

2.2模糊控制在事件检测中的应用

道路交通流, 特别是在事件发生的情况下, 是高度非线性、时变和不能精确建模或实时定量表示的, 许多交通概念具有重要但不精确的含义, 例如“拥挤”、“高占有率”、“服务水平”等。因此, 使用固定的“门槛值(临界值)”来检测事件, 显然并不能很好地适合交通状态所具有的动态不确定性, 而模糊集合理论恰好弥补了这一点。

基于模糊控制的事件检测算法的系统结构如图3所示。在本文的控制器设计过程中，算法的输入参数包括上下游不同周期的交通流量和占有率，基于模糊控制的事件检测算法的流程图如图4所示，此流程图的输出包括0（无事件）和1（事件）。

图4事件检测算法流程图

(1)模糊过程。每个模糊决策表包括两个输入，其中一个数值来自上游，另一个数据是同一周期的下游数据。每个输入被模糊化为下列七个不同模糊语言集中的一个，这七个模糊语言变量包括：“零（ZO）”、“很小（VS）”、“小（S）”、“中等（M）”、“中大（MB）”、“大（B）”和“很大（VB）”。该模糊控制器的控制规则最多应该有7 * 7=49条，由于变量论域被划分为7等级，则论域为{0，1，2，3，4，5，6}。输入变量由当前周期t和前两个周期(t-1和t-2)内在每个车道的上下游检测到的数据构成。利用重心法解模糊化，采用例如图2所示的糊推断过程。

(2)隶属函数和决策表。在模糊算法中, 确定各个模糊集的隶属函数是一项至关重要的工作, 隶属函数合适与否直接影响到检测率和误报率。在实数域上的模糊集可以选用各种分布, 主要有矩形分布、梯形分布、正态分布和岭形分布等。为简单起见, 此算法采用了三角形隶属函数以及高斯隶属函数。控制规则是模糊控制器的核心。将控制策略分析归纳后给出输入、输出变量的模糊状态描述就得到控制规则。在模糊控制器设计过程中，一般将所有的控制规则汇总成模糊控制规则表。本算法所设计的控制规则表如表1所示，这里 “US”及“DS”分别代表检测区域的上下游。本文共采用了9个类似的控制规则表。通过遗传算法把每个模糊决策表中的49个值进行优化得到一个接近于最优的设计。

ZOVSSMMBBVB

VSSMMBBVB

ZOVSVSMBBVBVB

ZOZOVSVSMBBVB

ZOZOZOVSSMBB

ZOZOZOZOVSSS

ZOZOZOZOZOVSVS

ZOZOZOZOZOZOVS

ZOZOZOZOZOZOZO

(3)多层设计。此模糊算法类似与一个多重通道设计，并且被划分为3个不同层数，模仿一个具有一个输入层、一个隐藏层以及一个输出层的神经网络结构。首先把12个输入数据模糊化并把它们输入到第一个模糊层，然后把第一层的输出作为第二层的输入带入到隐藏层，依次进行直到通过最后一层。模糊过程的黑箱技术图如5所示。

图5模糊过程的黑箱技术图

2.3遗传算法优化事件模糊控制器

针对交通流发生变化时，原有的模糊控制器不能达到较理想的检测效果，本文采用遗传算法来优化前面所设计的模糊控制器的隶属函数参数，以取得较优的控制效果。

在模糊化过程中共产生491个未知的模糊参数，其中441个参数属于这9个决策表，其余的50个参数包括模糊化和反模糊化过程中隶属函数的重心以及三角形隶属函数的参数。为了简化过程，使遗传算法集中，通过手动调整这441个参数。在这491个未知参数中，某些参数使用一个基因，而有些使用两个基因。由于使用二进制编码所占用的搜索空间较大，故此过程未采用二进制编码。由于变量选用了7个模糊状态，因此基因值的变化范围为0到6。

(1)遗传算法训练。在此算法中，染色体的基因由一台随机数发生器产生，因此有统一的偏差。这些基因被输入到一个解码算法中得到模糊参数，把模糊参数带入到模糊集方程得到自动事件检测的结果，这个过程就叫做遗传算法的在线训练，即在线遗传算法。算法依次进行直到设定的最大迭代次数，例如100。当获得最优的染色体时，基因被储放到另一个文件中，然后把它们输入到另一个算法（即离线遗传算法）得到期望的最优结果。优化模糊控制的在线遗传算法流程图如图6所示。

3仿真结果

通常用于评价事件检测算法的性能指标有检测率（Detection Rate，DR）、误报率（False Alarm Rate，FAR）和平均检测时间（Mean Time to Detection，MTTD）。本文用C语言编程实现了上述该算法，采用一系列模拟数据对此自动事件检测算法进行了测试，并与几种传统的事件检测算法在检测率、误报率、平均检测时间等多项指标进行比较, 其结果见表2。从仿真评价结果对比表可以看出本文所采用的算法整体效果较好，优于传统的算法。

表2仿真评价结果对比

算法

评价指标

检测率（%）误报率（%）平均检测时间（s.）

模糊-遗传算法73.71.104240

加利福尼亚算法8490.571255

人工神经网络781.503269

McMaster算法372.075260

图6遗传算法优化模糊控制流程图

参考文献

［1］汪海渊,朱彦东,杨东援.数据融合技术及其在交通领域中的应用［J］.交通与计算机,2001(增刊)，(19):4245.

［2］李秀平,刘智勇,尹征琦,吴今培.多传感器信息融合的智能交通控制系统研究［J］.信息与控制,2001,30(5):460464.

［3］李存军,杨儒贵,靳蕃.基于神经网络的交通信息融合预测方法［J］.系统工程,2004,22(3):8083.

［4］王晓薇, 王慧.基于GA 的交叉路口自适应模糊控制器设计［J］.吉林大学学报(信息科学版),2004,22(4):346351.

［5］韩峻峰, 李玉惠.模糊控制技术［M］.重庆:重庆大学出版社,2003.

［6］戴红.基于模糊模式识别的城市道路交通状态检测算法［J］.吉林工程技术师范学院学报,2005,21(3):4145.

模糊聚类:遗传算法篇4

在对图像的研究和应用中,人们往往仅对图像中的某些部分感兴趣。这些部分常称为目标,其他部分称为背景,它们一般对应图像中特定的、具有独特性质的区域。为了辨识和分割目标,需要提取并分离这些区域,在此基础上才有可能对目标进一步利用。图像分割是指把图像分成各具特征的区域,并提取出感兴趣目标的技术和过程[1]。

图像分割在实际中已经得到广泛的应用,例如工业自动化、在线产品检验、生产过程控制、文档图像处理、遥感和生物医学图像分析、保安监视以及军事、体育、农业工程等方面[2]。总的来说,在各种图像应用中,只要需要对图像目标进行提取、测量之处都离不开图像分割。图像分割技术的发展与许多其他学科和领域密切相关。近年来,随着各学科许多新理论和新方法的出现,人们也提出了许多新的图像分割技术。例如不断涌现出利用马尔可夫随机场、专家系统、Gibbs随机场、Bayesian理论、小波模极大值、分形、布朗链、模拟退火、聚类算法和遗传算法等新的分割算法[3,4]。

1 模糊C均值(FCM)聚类算法

聚类分析方法大致可以分为四种类型:谱系聚类法、基于等价关系的聚类法、图论聚类法和基于目标函数的聚类方法。前三种方法由于各种原因实际应用不够广泛,普遍受欢迎的是第四种方法,即基于目标函数的聚类方法。该方法把聚类分析归结成一个带约束的非线性规划问题,通过优化求解获得数据集的最优模糊划分和聚类。该方法设计简单,解决问题范围广,FCM算法就属于这种方法。

给定数据集X={x1,x2,…,xn}⊂R为模式空间中n个模式的一组有限观测的样本集,对给定样本集的X聚类分析就是要产生X的聚类类别数c(2≤c≤n)划分[5]。硬聚类算法将每个辨识对象严格地划分为属于某一类。不过在实际中一些对象并不具有严格的属性,它们可能位于两类之间,这时采用模糊聚类可以获得更好的效果。FCM算法是由隶属度确定每个数据点属于某个聚类程度的一种聚类算法[6],准备将给定数据集X分为c类,设X中的任意样本xk对第i类的隶属度为μik(0≤μik≤1);该分类结果可以用一个c×n阶矩阵U来表示,该矩阵称为模糊划分矩阵。

FCM的一般描述为:

式中:m称为加权指数,又称作平滑参数;Mfc为X的模糊c划分空间:

上述目标函数中,样本xk与第i类聚类原型pi之间距离度量的一般表达式定义为:

式中:A为s×s阶的对称正定矩阵,当A取单位矩阵I时,上式对应于欧氏距离。

聚类的准则是求取Jm(U,P)的极小值min{Jm(U,P)}[4]。

由于矩阵U中各列都是独立的,因此:

考虑到dik可能为0,应分两种情况加以讨论。对于∀k,定义集合Ik和 $\bar{Ι_{k}}$ 为:

使得Jm(U,P)为最小的μik值为:

用类似方法可获得Jm(U,P)为最小值时pi的值:

若数据集X、聚类类别数c和加权指数m值已知,就能确定最佳模糊分类矩阵和聚类中心。

2 基于模糊聚类的遗传算法

传统基于目标函数法的聚类算法本质上是一种局部搜索方法,它们采用的是迭代爬山技术来寻找最优解,存在的致命问题是容易陷入局部最优解。在一定的条件下,利用遗传算法(GA)可以在搜索空间中收敛到全局最优解。

遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机全局搜索和优化方法。其本质是一种高效、并行、全局搜索方法。它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程,以求得最优解[7]。

采用遗传算法可以做到对可行解表示广泛、群体搜索性强、不需要辅助信息、内在启发式随机搜索特性,具有固有的并行性和并行计算能力,可扩展性强,易于与别的技术混合等。因此遗传算法不易陷入局部最优解,并能快速可靠地解决求解非常困难的问题[8]。用遗传算法求解聚类问题,首先要解决以下两个问题:

(1) 如何将聚类问题的解编码到基因串中。对于聚类问题的编码,有两种方式:第一种是对硬划分矩阵U进行编码,设n个样本要分成c类,用基因串a={α1,α2,…,αi,…αn}来表示某一类的分类结果,其中:αi∈{1,2,…,c};i=1,2,…,n;第二种是采用对聚类原型P进行编码,把c组表示聚类原型的参数连接起来,根据各自的取值范围,将其量化值(用二进制串表示)编码成基因串b={β1,β2,…,βk,βk+1…,β2k,…,βck},其中每个聚类原型Pi都有一组参数与之相对应。b中的前k个表示的是第一个k维聚类原型,第k+1到第2k表示的是第二个k维聚类原型,同理,共c个聚类原型。第二种方法的搜索空间只与原型参数数目和类别数有关,与数据量无关,搜索空间往往比第一种方法小的多,所以在此采用第二种编码方法。

(2) 如何构造适应度函数来度量每条基因串对聚类问题的适应程度,该方法可以这样判别:如果某条基因串的编码代表着良好的聚类结果,则其适应度就高,反之则低。

对于基于目标函数的模糊聚类问题,其最优聚类结果对应目标函数的极小值,即聚类效果越好,则目标函数越小,而此时适应度越大,因此可以借助目标函数Jm(U,P)来定义GA的适应度函数:

基于模糊聚类遗传算法的实现步骤:

① 设定种群数目N,对聚类原型pi进行二进制编码,并产生初始种群;

② 对初始种群进行解码,并用式(8)计算每条基因串的适应度值;

③ 将适应度大的个体复制到下一代种群中,然后对父代进行选择、交叉、变异等遗传算子运算,产生下一代种群的其他基因串;

④ 如果达到了设定的繁衍代数,返回最优的基因串并解码,否则,返回到步骤③进行下一代的繁衍。

3 图像分割实验结果与分析

在 $Ρ e n t i u m^{\begin{array}{l} ○ \\ R \end{array}} 4 C Ρ U 2.66 G Η z + 1 024 Μ B D D R 400 +$ Windows XP Professional平台上,利用 Matlab 6.5编程,用简单遗传算法、传统FCM算法以及该文描述的基于模糊聚类的遗传算法实现对原始图像Lena(灰度图像,像素为256×256)和人造图像(灰度图像,像素为64×64)的分割。实验结果图以及实验分析如图1,图2所示。

这里取基于模糊聚类的遗传算法种群数目N=30,聚类数C=2,搜索代数为200代,交叉率前期为0.6,后期为0.75,变异率为0.02。

从分割图1(d)中可以看出,该算法实现了图像的有效分割,人物轮廓清晰,物体的受光面和阴影面区别明显。在分割图2(a)中,由于添加了高斯噪声,对原图的污染比较严重,但从分割图2(d)上可明显看出,采用基于模糊聚类遗传算法,其分割结果明显优于前两种方法。根据分割评价中的定性实验性准则可知[9],如果算法分割的结果大致相同,那么对预/后处理要求低的算法的相对性能要更优越一些,聚类算法对预处理的要求比较高,对初始点的选择很敏感,所以可能使分割效果不太理想,如图2(c)所示;在引入遗传算法后,利用遗传算法的全局搜索特点,可以解决FCM对初始化敏感的问题,增强了算法的抗噪性,所以图2(d)的分割效果最好。在分割速度方面,传统FCM算法的运行速度较慢,遗传算法自身具有隐并行性的特点,比盲目的搜索效率要高。用遗传算法和聚类相结合的方法,既解决了对初始化敏感的问题,又能在一定程度上提高程序的运行速度。表1列出了对图1、图2进行分割的时间列表。

4 结语

在此,采用基于模糊聚类遗传算法的图像分割。实验表明,比传统FCM算法和简单遗传算法有了较大的改进。在保持聚类算法良好的分割效果的同时,降低了对初始化的要求,并在一定程度上提高了运行速度,验证了本文方法的有效性。遗传算法与FCM算法的结合正是近年来研究的热点之一。

参考文献

[1]章毓晋.图像分割[M].北京:科学出版社,2001.

[2]章毓晋.图像处理和分析基础[M].北京:高等教育出版社,2002.

[3]IM J,Jensen J R,Tullis J A.Object-based Change DetectionUsing Correlation Image Analysis and Image Segmentation[J].International Journal of Remote Sensing,2008,29(2):399-423.

[4]Wu Yi-Ta,Shih,Frank Y,et al.A Top-down Region Divid-ing Approach for Image Segmentation[J].Pattern Recogni-tion,2008,41(6):1 948-1 960.

[5]高新波.模糊聚类分析及其应用[M].西安:西安电子科技大学出版社,2003.

[6]匡泰,朱清新,孙跃.FCM算法用于灰度图像分割的初始化方法的研究[J].计算机应用,2006,26(4):784-786.

[7]雷英杰.Matlab遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005.

[8]李敏强.遗传算法的基本理论与应用[M].北京:科学出版社,2004.

[9]狄宇春,邓雁萍.关于图像分割性能评估的评述[J].中国图像图形学报,1999(3):183-187.

模糊聚类:遗传算法篇5

医疗诊断具有复杂性,具体表现在一种病症有多种症状,同一种病症也可能有不同的症状,而且一种症状可能是多种病症的体现。另外病症特征会随人体适应性不同而因人而异,从而导致信息的不确定性。运用模糊理论的方法可以有效地处理不确定问题和复杂性问题,通过模糊聚类方法对人体症状进行诊断分类。M.Ayoubi等[1]提出了一种把Fuzzy推理应用到诊断中的方法,考虑医疗诊断的复杂性与不确定性。

遗传算法(GA)是模拟生物的自然选择和优胜劣汰的进化论和遗传学思想而产生的,它是对多组解同时进行操作(具有隐并行性),具有全局搜索功能。最早由美国Michigan大学的Holland教授在20世纪70年代提出[2]。目前广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科学领域,适用于解决复杂的非线性和多维空间寻优问题。本研究将基于遗传算法的模糊聚类应用到医疗诊断中,探讨对常见腹痛症状的临床决策分析。

1 关键技术

1.1 模糊C均值算法

模糊聚类算法中应用最广泛的是模糊C均值(FCM,Fuzzy C-Means)算法[3]。该算法通过优化模糊目标函数得到每个样本点相对类中心的隶属度,并以此为依据决定样本点的归属。

FCM算法的迭代过程如下:(1)初始化:给定聚类数目;设定迭代停止阈值,初始化聚类中心,并设置迭代计数器;(2)计算类间的相似度建立相似关系矩阵;(3)更新各类范围,重新划分聚类中心;(4)根据迭代条件输出分类矩阵和聚类中心,否则继续迭代。

结合内科常见症状--腹痛疾病的临床实际情况,以医疗领域知识和专家在腹痛疾病的诊断经验为依据,将常见腹痛进行了归纳整理,其病因可分为急性阑尾炎、急性胆囊炎、胆囊结石、胆管结石、急性胆管炎、胃癌、胃十二指肠溃疡穿孔、急性肠梗阻、急性弥漫性腹膜炎、肝脓肿、原发性肝癌,急性胰腺炎等。

将一组病人样本数据预处理后,组成21个特征向量,每个特征向量代表与疾病相关症状的相对参数。对有效样本数据进行统计分析,可以发现所有样本的特征值均围绕数值1波动,最大的特征值为1.82,最小的特征值为0.254。根据模糊等价关系聚类的步骤[4],首先对样本的特征向量数据进行标准化处理,并采用极值标准化公式将标准化数据压缩到区间。具体的数据处理公式如下所示:

利用标准化的样本特征向量计算样本间的相似性统计量[5],建立样本的模糊相似关系矩阵r=(rij)n×n,0≤rij≤1,i,j=0,1,...n,rij表示样本与样本的相似程度。计算相似度数学表达式为:

对抽取的样本,采用夹角余弦公式处理得到相似关系矩阵如下所示:

用相似性统计量的方法处理样本,获得模糊相似矩阵[6],再用传递闭包变换将模糊相似矩阵改造为模糊等价矩阵。然后将模糊等价矩阵中互不相同的rij按从小到大的顺序排列,根据不同的阈值对模糊等价矩阵进行划分聚类,即得到类别结果。

样本特征向量选择21维,采用几何平均最小值方法处理样本数据。经过传递闭包变换获得样本的模糊等价矩阵,再将模糊等价矩阵中互不相同的元素按从小到大的顺序排列,λ阈值依次取该组数值,进行动态分类。

对于几何平均最小法,样本数为20时,其λ阈值取值范围:[0.57,0.88]。

当λ=0.88时,20个样本各成一类:{x1},{x2},…{x20};;

当λ=0.79时,20个样本分为五类:

当λ=0.71时,20个样本分为四类:

当λ=0.66时,20个样本分为二类:

当λ=0.57时,20个样本分为一类:{x1,x2,…x20}

不同的特征向量对分类结果有不同的影响。在样本的相似性处理运算时,21维的特征向量全部用于计算样本的相似度,可能降低了各个特征向量对样本间相似度的影响。从采用21维特征向量进行初步聚类分析的结果可以得到[7],值过大时总是可以对"胆囊结石""肝脓肿"方面的病症分类,而"腹膜炎""阑尾炎"方面的病症却得不到分类。这表示21维特征向量聚类分析时,可以突出各个脏器的病理特性,但是淹没了一般现象的病理特性。

1.2 遗传算法

遗传算法(GA)是模拟生物的自然选择和优胜劣汰的进化论和遗传学思想而产生的。GA算法的基本思想是:初始化一代种群,通过其选择、交叉、变异机制得到下一代种群,再进行选择、交叉、变异,……,以得到最优的个体,即所求问题的解。经典遗传算法的计算流程如图1所示。

GA-FCM算法是将基本GA算法应用于FCM算法,该算法由两个阶段组成,即GA和FCM。第一阶段利用GA算法的全局搜索性能,用于优化FCM算法的初始聚类原型;第二阶段以第一阶段得到的聚类原型作为初始聚类原型利用FCM算法精确求得最优聚类。GA-FCM算法的流程图如图2所示:

对于染色体的编码,采用基于聚类原型的二进制编码方式,每一个聚类原型的每一个分量对应于一个由l位组成的位串,又因为数据样本的维数为m,每个染色体由c个聚类原型组成。所以染色体是由L=c×m×l位的位串组成。此外,每个染色体还有一个适应度,计算公式如下:

其中,K是一个正常数,J0是一个较小的正常数;一般地,可取K=1.0,J0=0.01。聚类原型越好,目标函数值越小,则该个体的适应度越大。

2 GA-FCM聚类结果分析

根据有效性函数对分类数的评选以及聚类输出的结果比较,可以得到对于诊断系统的样本分类相对较好的结果。以下根据样本的专家诊断结果,对GA-FCM聚类的结果进行综合分析。

聚类样本的数据含有21个特征量,那么对于参与FCM聚类的20个样本数据就组成了一个21维的特征向量空间。在聚类过程中,距离函数是确定样本之间相似程度的依据。当样本数据含多个特征量,则用于计算目标函数的欧式距离是也多维的空间距离。聚类输出的聚类中心是一个表征21维空间的矩阵,每一列元素表征了聚类中心在一维坐标上的坐标。因此21维样本点与21维的聚类中心只能以抽象的空间概念表示,难以直观的用图形表示聚类效果。对于高维的数据空间,只能在二维投影平面或三维的投影空间上观察数据的投影分布。聚类树切割成3类的样本分布如图3所示。用该方法所得结果相对孤立点较少,且能容易的对分层聚类树切割出最佳的聚类树,取得了较好的效果。

3 结论

为了进一步有效地对计算机临床诊断方法的探讨,减少大量不同病症的样本对诊断方法研究的影响,运用基于遗传算法的模糊聚类对病例样本进行诊断分类,其输出的模糊分类,可以为模糊专家系统的建立提供相应的推理规则,为临床决策分析智能系统深入研究开拓了新的途径。

摘要：模糊聚类通过样本类属的不确定程度,表达样本类属的中介性。基于遗传算法的模糊聚类,通过遗传算法的全局搜索性能,优化模糊聚类算法的初始聚类原型,再在初始聚类原型基础上利用模糊聚类算法精确求得最优聚类。将其应用于内科腹痛医疗诊断,可有效提高诊断准确率。

关键词：遗传算法,模糊聚类,医疗诊断,决策分析

参考文献

[1]M Ayoubi,R Isermann.Neuro-fuzzy system for diagnosis[J].Fuzzy sets and Systems,1997.89(3).

[2]J.H.Holland,(Adaptation in Natural and Artificial System),Ann Ar-bor:The University of Michigan Press,1975.

[3]梁静国、张亚光、戈华,CRM中的模糊C均值FCM客户聚类算法研究,哈尔滨工程大学学报,2004.25(2).

[4]宫改云、高新波、伍忠东,FCM聚类算法中模糊加权指数m的优选方法,模糊系统与数学,2005.19(1).

[5]钮永莉、陈水利,模糊C均值算法的改进,模糊系统与数学,2004.

[6]Bezdekc JC.Ehrlich R,Full W.FCM:Fuzzy C-menas algorithm[J].Computers and Geoscience,1984,23:16-20.

模糊聚类:遗传算法篇6

聚类分析[1]是模式识别和数据压缩领域中一种重要的非监督学习过程,其目的是将若干特征相似的特征模式划分到一个集合,每个集合的特征模式之间按照某种度量来衡量相似程度,使得同一个集合内的数据对象具有较高的相似度,而不同集合中的数据对象间的相似度尽可能小,数据对象间特性差异的大小通常是借助于某一距离空间中的距离概念来刻划的。在现有的聚类算法中,K-均值算法以其简单和高效占有重要地位[2]。但因K-均值算法在寻找聚类中心的过程中采用了启发式方法,使得该算法对初始聚类中心的选择较为敏感,易于陷入局部最优解。尤其在大矢量空间中,这种算法的性能会变得更差[3,4]。美国Holland教授于1975年提出了一种全局优化自适应概率搜索算法—遗传算法(GA)[5,6]。该算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法,具有较强的鲁棒性和全局寻优的能力,但基于遗传的K均值算法(GA-K均值算法)存在前期过早收敛而后期收敛慢的缺点[7]。本文借助免疫机制的优点[8],将免疫原理的选择操作机制引入遗传算法中,提出基于改进遗传算法的K-均值聚类算法。该算法结合K-均值算法的高效性和局部搜索能力,以及改进遗传算法的全局优化能力,达到了较好的聚类效果。

1 基于改进遗传算法的K-均值聚类算法

遗传算法在解决实际问题时,目标函数和约束条件作为抗原输入,随机产生初始抗体群,并通过一系列遗传操作及个体浓度的计算,在保持抗体多样性的情况下找出针对该抗原的抗体。本研究借助免疫机制来调整选择概率,以优化初始聚类中心,同时,在种群进化过程中,自适应动态调节交叉概率和变异概率,避免了早熟现象的发生。具体步骤如下:

1.1 染色体编码及种群初始化

染色体编码有很多方式,聚类分析中常用的是基于聚类中心的浮点数编码和基于聚类划分的整数编码。根据聚类样本的高维性和数量大的特点,本文采用浮点数编码。初始种群的产生采用随机生成,方法为:假设随机从样本空间中选K个样本作为聚类中心,其它样本随机分到这K个聚类中,并计算各个聚类的聚类中心作为初始个体的染色体编码,最后增加一位该个体所对应的适应度,即1条染色体可以用长度为(K+1)个基因位组成的浮点码串S=Z1Z2…Zkf表示,重复进行psize次(psize为种群大小),得到初始种群。

1.2 染色体适应度的选取

根据染色体的构成,采用的适应度函数为

$f = \frac{1}{k} \times \frac{E_{1}}{E_{k}} \times D_{k}$

上式中:k为聚类类别数;是簇内距离;是簇间距离。,计算公式分别为

$E_{k} = \sum_{j = 1}^{k} \sum_{x_{i} \in Ι_{j}} ∥ x_{i} - c_{j} ∥^{2}$

上式中:xi表示类簇Ij中的样本;cj表示类簇j的中心。这样定义考虑了簇内聚类最小的原则。

$D_{k} = {m a x}_{i ‚ j = 1}^{k} ∥ c_{i} - c_{j} ∥$

上式中:ci,cj分别为簇i,j的中心。这样定义考虑了簇间距离最大的原则。

适应度函数受3个因素影响,即1/k,E1/Ek及。第一个因素减少的时候,另外两个因素随着k的增加而增加,所以这个适应度函数表达的内涵是在所分类别数尽可能小的情况下提高聚类的紧凑度和分离程度。

1.3 选择操作

针对基于遗传算法的聚类算法在算法开始前期收敛速度快,而后期由于各条染色体的个体差异变小使收敛速度变得很慢,本研究采用一种基于免疫原理[6]的选择操作和比例适应度分配方法相结合的混合选择算子计算个体被选中的概率以克服上述缺点。

定义1 个体浓度:

$d = \frac{群体中相同个体的数目 (m)}{群体大小 (p_{s i z e})}$

找出群体中个体浓度最大的m个个体,设为1,2,…,m,则这m个个体的个体浓度概率为 $p_{d} = \frac{(1 - d)}{p_{s i z e}}$ ,其余的个体浓度概率为,所有个体的浓度概率之和为1。

设某一个个体的适应度为fi,该个体被选中的概率为pfi,则

$p_{f_{i}} = \frac{f_{i}}{p_{d} \times \sum_{j = 1}^{p_{s i z e}} f_{i}}$

式中:i=1,2,…,psize。

此种选择策略有两个优点:一是个体适应度越大,则选中的概率越大,加速了算法的收敛;二是个体浓度越大则被选择的概率越小,起到抑制作用,保证了进化群体中个体的多样性,避免过早收敛。

1.4 交叉操作

标准遗传算法由于在进化过程中采用固定的交叉概率和变异概率,已经被证明无法收敛到问题的全局最优解,容易出现早熟现象,后期还会因为个体差异的减小出现收敛速度缓慢的现象。鉴于此,本研究按照一定的交叉概率采用最邻近法则进行交叉操作。首先对交叉概率和变异概率做出如下约定:当群体适应度比较集中时,使得交叉概率Pc和变异概率Pm增大;当群体适应度比较分散时,使得交叉概率Pc和变异概率Pm适当减小。这样约定能使算法在迭代过程中根据个体的适应度来改变其交叉概率Pc和变异概率Pm,从而在能保护最优个体的同时加速较差个体的淘汰速度,增强了算法的全局搜索能力。其数学模型为:

$Ρ_{c} = {\begin{cases} Κ_{1} \times \frac{f_{m a x} - f^{'}}{f_{m a x} - f_{a v g}} f^{'} \geq f_{a v g} \\ Ρ_{c} = Κ_{2} f^{'} ＜ f_{a v g} \end{cases}$

$Ρ_{m} = {\begin{cases} Κ_{3} \times \frac{f_{m a x} - f}{f_{m a x} - f_{a v g}} f \geq f_{a v g} \\ Ρ_{m} = Κ_{4} f ＜ f_{a v g} \end{cases}$

式中:K1,K2,K3,K4是小于0的常数;fmax为群体的最大适应度;favg为群体的平均适应度;f′为交叉产生的2个新个体中适应度较大的那个个体的适应度;f为变异个体的适应度值。

采用最邻近法则的基因匹配交叉操作:设待交叉的2条染色体为S1=Z $_{1}^{(1)}$ Z $_{2}^{(1)}$ …Z $_{k}^{(1)}$ 和S2=Z $_{1}^{(2)}$ Z $_{2}^{(2)}$ …Z $_{k}^{(2)}$ 。对染色体S1的每个基因Z $_{i}^{(1)}$

,选择S2中与Z $_{i}^{(1)}$ 距离最近的基因Z $_{j}^{(1)}$ 配对,已经配对的基因不再参加后续的基因配对。再将S2按基因配对的顺序重新排列,得到S*2。最后随机选择交叉点进行单点交叉得到下一代个体S′1和S′2。

1.5 变异操作

变异操作是一种局部随机搜索,与选择、交叉算子结合可以保证算法的有效性。本研究中采用按基因位(一个基因即为一个聚类中心)的维向量来进行,每个基因位的每维向量(一个浮点数)按变异概率Pm来发生随机变异。在整个算法开始之前,先求出每维向量的最大值和最小值,分别保存在向量 $v e c Μ a x [p]$ 与 $v e c Μ i n [p]$ (p为样本数据维数)中,可知所有最优聚类中心的第i(0〈i≤P)维向量的值一定介于 $v e c Μ i n [i]$ 与 $v e c Μ a x [i]$ 之间。同时约定随机变异的值应在 $v e c Μ i n [i]$ 与 $v e c Μ a x [i]$ 之间。这样既保证了群体的多样性,又可以避免盲目搜索,大大提高了搜索的速度和效率。

1.6 算法终止条件

只要满足以下2个条件中的任意一个条件则算法终止:

(1)算法迭代次数超过设定一个最大的迭代次数maxGen;

(2)运行过程中得到相同的最优结果次数连续超过某一阀值。

本文采用第2个条件作为结束条件。

2 算法描述

给定样本数据集合 $D = {d_{1} ‚ d_{2} ‚ \dots ‚ d_{i} ‚ \dots ‚ d_{n}}$ ,基于改进遗传算法的K-均值聚类算法具体过程描述为

(1)确定要生成的类簇数目k、种群规模为psize个个体及算法结束条件。

(2)先随机选择k个初始聚类中心组成一个个体 $C = {c_{1} ‚ c_{2} ‚ \dots ‚ c_{i} ‚ \dots ‚ c_{k}}$ ,对个体进行染色体编码,总共进行psize次,得到群体为psize个个体,设置初始迭代次数t=0。

(3)对数据集中的每一个样本数据di,依次计算它与各个聚类中心的相似度;将样本数据di合并到与其具有最大相似度的类簇中。

(4)按照相似度公式计算新的类簇的中心,组成一个个体,并计算新个体的适应度;

(5)对所有的个体实施遗传算子,得到下一代的群体;

(6)得到优化后的个体。如果所有聚类中心均达到稳定,则结束;否则,t=t+1,转(3)。

3 试验结果及分析

分别采用 k-均值算法、遗传K-均值算法(GA-K均值算法)和本文算法在VC++和MatlAB环境下进行仿真实验。遗传算法的交叉概率和变异概率初始值分别取为0.75,0.09,群体规模为100,迭代次数为100次,当运行过程中得到最优结果次数连续10次以上时算法结束。实验采用数据是Fisher的Iris 3种植物150样本个数据[9]进行10次试验,每个样本均为四维向量,代表植物的4种属性。三种算法分别单独运行10次,计算出簇内距离Ek与簇间距离Dk的最大值,最小值及平均值。实验结果见表1。

注:以上数据为单个算法运行10次的平均值。

聚类算法的理想结果是同时获得最小的簇内距离和最大的簇间距离。从表1中的数据可以看出,标准的K-均值算法由于对初始中心选取敏感性很大,在初始中心选择不当的情况下易陷入局部最优,出现过早收敛;GA-K均值算法由于个体的多样性不足而常出现早熟现象;本研究提出的算法在全局搜索能力方面优于K-均值和GA-K均值算法,所获得的聚类结果具有更强的稳定性,对于随机分布的数据聚类有明显的优越性;同时从达到最优解迭代次数看,本文提出的算法达到最优解的平均迭代次数要远少于K-均值和GA-K均值算法,所以本文提出的算法收敛速度更快。

4 结束语

本文对遗传算法和K-均值聚类算法进行了研究,针对K-均值聚类效果易受初始聚类中心影响的不足,为克服遗传算法引入K-均值算法所带来的易出现局部早熟的缺点,将免疫机制的选择操作引入遗传算法,使个体浓度和适应度同时对个体的选择操作产生作用,改变以往单纯以适应度来作为个体选择的依据,对算法进行改进,然后将改进的遗传算法引入K-均值算法中以优化聚类中心,提出一种基于改进遗传算法的K-均值聚类算法。试验结果表明,本研究的算法与传统的K-均值算法和GA-K均值算法比较,在全局搜索能力方面优于K-均值和GA-K均值算法,所获得的聚类结果具有更强的稳定性,能够有效改善聚类质量。

参考文献

[1]Jiawei Han,Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社,2005:185-218

[2]Bandyopadhyay S,Maulik U.An evolutionary technique based on k-means algorithm for optional clustering in rn[J].Information Sciences,2002,(146):221-237

[3]Ahmadyfard Alireza,Modares Hamidreza.Combining PSO and k-means to enhance data clustering[A].IST2008International Symposium[C].Tehran:IEEE Press,2008.

[4]Hai-xiang Guo,Ke-jun Zhu,Si-wei Gao,et al.Animproved genetic k-means algorithm for optimal clustering[A].Sixth IEEE International Conference[C].Leipzig:IEEE Press,2006.

[5]李茂军,罗安.单亲遗传算法的机理分析[J].长沙理工大学学报(自然科学版),2004,1(1):76-79

[6]贺志民,方美娥.基于遗传算法的特征值问题求解[J].长沙电力学院学报(自然科学版),2003,18(1)12-14

[7]赖玉霞,刘建平,杨国兴.基于遗传算法的K-均值聚类分析[J].计算机工程2008,34(20):200-202

[8]王磊,潘进,焦李成.免疫算法[J].电子学报2000,28(7):74-78

基于密度函数的模糊聚类算法篇7

聚类方法是指把待分类的对象按照一定的属性严格地划分到某个类中, 分类的结果集中具有明显的非此即彼的特性, 这是一种无监督的划分。相对于传统的硬聚类算法, 模糊聚类算法运用数学上的处理模糊和不确定性知识的数学工具, 对待分类对象进行了更准确的软划分[1], 使得分类结果更加准确。

由Dunn提出、Bezdek加以推广的模糊C- 均值聚类算法是目前使用最多的模糊聚类算法[2]。文献[3]采用非欧几里德关系数据的竞争凝聚算法来确定聚类数;文献[4]则提出了一种符号数据集的模糊聚类算法;文献[5]提出了考虑类中心之间的距离, 将全局优化方法中的模拟退火算法用于聚类分析;文献[6]改进模糊聚类算法, 将粒子群优化算法与模糊C- 均值聚类算法融合, 提高了算法正确率。

以上算法虽然在一定程度上提高了聚类的准确率, 但是仍存在不足之处, 如对初始值敏感、聚类数目难以确定、迭代容易陷入局部极值而达不到全局最优等问题。鉴于此, 本文提出基于密度函数的模糊聚类算法, 即在聚类中心的选取和优化中利用数学计算, 既保证了聚类的特性, 又准确地对待分类对象进行计算, 同时也可有效避免迭代陷入局部极小的问题。

2 FCM算法改进

2.1聚类有效性判定

对于聚类结果的有效性判定目前有很多种方法, 本文选用聚类有效性准则函数作为判定依据, 计算两个聚类集之间的重叠度和分离度。重叠度越小, 分离度越大, 则说明聚类效果最好。

2.1.1定义重叠度

定义两个模糊集和之间的重复度为:

2.1.2定义分离度

两个模糊集和之间的相似度为:, 则的值介于0和1之间。定义两个模糊集和之间的分离度为:

2.1.3有效性判定

模糊集之间的重叠度可以表示为:;模糊集之间的分离度可以表示为:。此时, 有效定判定函数可以表示为:。其中, 权重因子和是用来补偿重叠度和分离度的度量差别, 满足条件:+=1。根据不同粒度空间, 为取值变化范围较大的一方赋予较小的权重。以聚类结果更加清晰为原则, 取=0.6, =0.4, 因此代表了最佳的聚类结果, 此时与之对应的聚类类别数C即为最佳聚类数目。

2.2改进的FCM算法实现

步骤1设定模糊系数m=2, 迭代停止阈值, 聚类次数N=0;

步骤2运用密度函数法确定最初的剧烈数目, 此时N=1;

步骤3更新模糊聚类中心和隶属度矩阵, 如果满足, 则停止迭代;否则, 进行步骤2;

步骤4对满足迭代条件的聚类进行聚类有效性判定, 确定;

步骤5通过计算和判断确定, 对应的隶属度矩阵作为最佳聚类结果, 对应的聚类数目即为最终的聚类数目。

3实验结果

本文采用加州大学欧文分校数据库归档中的知识发现提供的2D15数据库来进行仿真实现, 取模糊系数m=2。2D15数据集市包含5 000条二维数据的数据集, 其中分为15类。为了充分验证新算法的性能, 只取其中的6类约2 000条数据来进行实验。表1给出了改进的FCM和传统的FCM算法在2D15数据集上的实验效果。

由以上实验结果可知, 表1中传统的FCM没有有效性函数作为判断的依据, 因此必须通过不断的迭代计算, 直到出现满足迭代停止的条件来确定最佳的聚类类别数为6。在改进的FCM中, 通过上表可以看到, 当值最小为0.5504的时候, 其对应的聚类类别数为6, 与传统的FCM得到的结果一致。除此之外, 改进FCM的平均迭代次数整体上小于传统的FCM, 说明新算法在整体性能上优于传统的FCM。究其原因, 主要是改进的FCM算法在前期对原始初始聚类使用函数密度法进行了有目的性的聚类, 从而减少了迭代次数, 提高了算法性能。另外, 对比实验的平均准确率, 改进算法的准确率明显高于传统的FCM算法。

4结语

本文在传统的模糊聚类算法基础上, 针对传统的算法需要提前设定初始聚类中心和聚类类别数的问题进行改进, 提出了改进的FCM算法, 从而有效解决了问题。通过实验表明, 改进的算法能够有效减少迭代次数, 提高算法性能, 具有较高的聚类平均准确率。试验中发现, 当处理的数据量达到一定程度时, 改进的算法效率会受到一些影响, 因此如何在处理大量数据时仍保持改进算法的效率将是今后的研究方向。

参考文献

[1]Lei Z, Ren-Hou L.Designing of Classifiers Based on Immune Principles and Fuzzy Rules[J].Information Sciences, 2008 (7) :1836-1847.

[2]leski J.Towards a Robust Fuzzy Clustering[J].Fuzzy Sets and Systems, 2003 (2) :215-233.

[3]李家福, 张亚非, 陆建江.模糊聚类算法在汉语文本聚类中的应用[J].计算机工程, 2002 (4) :15-16.

[4]De Carvalho FAT.Fuzzy c-means Clustering Methods for Symbolic Interval Data[J].Pattern Recognition Letters, 2007 (4) :423-437.

[5]Rose K, Gurewitz E, Fox G C.Constrained Clustering As An Optimization Method[J].Pattern Analysis and Machine Intelligence, 1993 (8) :785-794.

基于生长树聚类的改进型遗传算法篇8

目前, 遗传算法具有的大范围广域搜索能力已得到确认, 其明显的不足主要是不成熟收敛和收敛速度慢的问题, 要避免不成熟收敛的问题通常从保持种群多样性入手。已提出了各种群体多样化机制来维护在搜索中的多样化群体, 其中使用聚类方法将初始解分成若干个子种群, 在各个子种群中搜索最优解的基于聚类思想的遗传算法已得到广泛研究。

基于聚类思想的遗传算法与以往的并行模型 (主—从模型、孤岛模型、细粒度模型) 有很大差异:在以往的并行模型中, 核心思想是将种群分解成许多子种群, 让各子群体在不同的处理器上并行执行, 但各子群体之间的通信问题很难解决。文献[1]提出的Family clustering GA算法是基于聚类的思想, 根据适配值对种群进行划分, 并采用家庭选择算子, 可以同时兼顾收敛速度和种群多样性;但在解空间中适应度值相邻的两个个体之间在空间中可能并不相邻, 则基于适应度排序的方式划分成的类也就不能保持群体原有的空间分布特性。文献[2]虽采用聚类的方法将种群划分为若干个子空间, 但其交叉操作只在同一类中进行, 这种方法限制了遗传算法向其它未知区域探索的能力, 虽可以维持群体的多样性, 却难以产生新的群体多样性。文献[3]提出的基于最小生长树的聚类思想对于形状复杂且非重叠的样本聚类问题效果理想。

本文提出的基于生长树聚类的改进型遗传算法是一种基于生长树聚类的家族遗传算法, 采用混合编码方式, 将初始个体用基于生长树的聚类方法聚成K个家族;然后采用新的族间交叉算子和改进的族内交叉及变异算子使算法在快速收敛的同时保持种群的多样性。

1 算法的思想

基于生长树聚类的改进型遗传算法ACGA (An Advanced Genetic Algorithm Based on Clustering) , 首先采用生长树聚类方法将整个初始种群分成K个家族。然后在不同家族之间选择适应度值大的个体进行交叉繁衍, 在同一家族内随机选择个体交叉繁衍, 从而在快速收敛的同时保持种群中个体的多样性, 为提高算法的收敛速度, 在变异前采用了精英保留策略。此算法的关键是利用生长树聚类处理种群, 利用特殊的家族交叉算子即保留了优秀个体的模式, 又保证了种群的多样性。

1.1 基于生长树思想的聚类

本文根据基于生长树[9]的原理聚类, 其基本思想是在待聚类的初始种群中, 随机选择k个样本点作为种子点, 从种子点开始依据其最邻近距离寻找最邻近点, 一旦作为种子点的最邻近点, 其自身也就变成种子点。所有的种子点均有机会寻找最邻近点, 但是最邻近距离最小的种子点才被赋予优先权。每一个种子点在满足它的最邻近距离最小条件下, 可以重复选择不同的最邻近点, 直到所有的待聚类样本点变为种子点为止。其算法描述如下:

1) 随机选择各子生长树的初始种子点。

2) 各子生长树初始种子点在公平的环境下, 以最邻近距离最小的初始种子点被赋予优先权去寻找自己的最邻近点, 找到的最邻近点变成该子生长树上新的种子点, 它也有机会去寻找自己的最邻近点。

3) 所有的种子点再次重新选择自己的最邻近点, 在条件满足的情况下种子点可以重复寻找自己的最邻近点。

4) 如果所有的聚类样本点变成种子点, 则完成样本的划分。否则转向3) 。每个子生长树对应聚类的一个簇。

由于待聚类的种群作为样本在特征空间上分布的密度不尽相同, 各子生长树的生长速度也就不同, 最后所聚成的类的大小和形状也就随之不同, 从而使这种基本生长树的遗传聚类算法可以处理任意形状的聚类。这种基于生长树聚类的方法形成的家族的所有个体在解空间上的距离是邻近的, 在家族内再根据适应度值进行排序, 进而选择交叉和变异算子。

1.2 编码方式

本文采用混合参数编码方式:

$C h r o m = {\begin{cases} b i n a r y s t r i n g 1 x 1 k (x 1) f (x 1) \\ b i n a r y s t r i n g 2 x 2 k (x 2) f (x 2) \\ ⋮ ⋮ ⋮ ⋮ \\ b i n a r y s t r i n g n x n k (x n) f (x n) \end{cases}}$

其中:binarystringn代表实数所对应的二进制;f (x) 代表实数X所对应的适应度值, k (x) 代表X所在的类即家族。这种混合编码方式不仅可以在编码中体现个体的适应度值及顺序, 还可同时体现其所在族的信息;同时编码中的二进制串也便于交叉和变异操作。

1.3 生成初始种群

给出初出种群的个体数n, 随机生成第一代初始种群的二进制代码部分:Xn1= (binarystring1, binarystring2, …, binarystringn) T;计算种群中各个个体所对应的实数值X11 , X21 , X31, …, Xn1;随机选择K个个体作为聚类中心, 由基于生长树的聚类算法对初始种群中的个体分类, 把个体所在的类别添加到代码中;最后计算每个个体的适应度值并按其所在类及适应度大小排序。

1.4 选择算子

1) 族内选择算子

为减小选择压力和保持种群多样性, 采用基于排序的父代子代同时参与竞争的选择算子。即家庭最优选择算子:对父代子代个体按适应度函数值进行排序, 从中选择适应度值最大的两个个体保留在家族中。

2) 族间选择算子

两个父代和通过交叉算子产生的两个子代进行比较, 从这四个个体中选出适应度值最大的两个个体作为交叉的结果, 适应度值最大的替换适应度值大的父个体, 适应度值次大的个体替换另一个父个体。

1.5 交叉算子

族间交叉算子:随机选择两个不同的家族, 选择每个家族中的最优个体与另一家族的最优个体作交叉操作。这种族间交叉方式在不同家族间选择个体进行交叉, 实际上控制了交叉个体的海明距离, 可避免近亲繁殖。同时有助于保持种群的多样性, 提高了进化效率。其具体步骤表达如下:

1) 现有第t代种群Xnt, 其中n为个体数, 即Xnt= (X1t , X2t , X3t, …, Xnt) , 将这n个个体按生长树聚类方式聚类成K个家族, Xnt={Z1t∪Z2t∪…∪Zkt }, Zit为第t代第i个家族 (1≤i≤k) 。

2) 将K个家族内的个体分别在族内按适应值大小排, 得到K个新的有序家族, 如第K个家族中的个体为Z k t= (z (k, 1) t, z (k, 2) t, …, z (k, j) t) 且f (z (k, i) t) ≥f (z (k.i+1) t) , 其中f (x) 为适应度函数值。

3) 在各家族间采用族间交叉算子。随机选择两个不同家族, 选择其最优秀个体进行交叉操作, 按族间选择算子保留相应个体到相应的家族中。如随机选择了第i个和第j个家族, 且f (z (i, 1) t) ≥f (z (j, 1) t) , 则个体z (i, 1) t与个体z (j, 1) t作交叉操作得到子个体z′ (j, 1) t和z′ (i, 1) t, 比较这四个个体的适应度值, 将适应度值最大的个体复制到i家族, 适应度值次大的个体复制到j家族中。

4) 在各家族内采用族内交叉算子。在各族内随机选择两个个体作交叉操作, 其父代子代个体根据族内选择算子保留相应的个体在各自家族内。

2 ACGA算法描述

Step1 随机生成初始种群P={A1, A2, …, An}, 其中n为种群个体的初始数目。

Step2 每隔若干代, 采用基于生长树聚类的方法将种群聚成K类, 每一类看成是一个家族。

Step3 计算各家族内个体的数目, 计算适应度函数值并排序。

Step4 族间交叉, 从不同家族中选择适应度值高的个体进行族间交叉, 由族间选择算子分别替换其父个体保留在原家族中。

Step5 族内交叉, 从同一类中选择个体进行族内交叉, 将交叉后生成的个体经家庭选择算子选择替换其父个体保留在原家族中。

Step6 变异, 对种群中的个体进行变异操作, 比较变异后生成的新个体与父个体的适应度值, 选择二者中的优秀个体替换父个体保留在原家族中;在变异前采用精英保留策略, 保留每一代种群中最优的二个个体不参加变异。

Step7 若满足终止条件, 算法结束;否则转到Step2。

3 仿真

3.1 测试函数

1) f1是经典的遗传算法优化函数, 只有一个极小值点, 理论最小值为f (0, 0, …, 0) =0。对于种群的大小不敏感:

$\min f_{1} (x) = \sum_{i = 1}^{n} x_{i}^{2}$

2) f2是最常用来测试遗传算法的一个典型函数, 是Rastrigin函数, 有许多局部最小值, 但只有一个全局最小值0。使用标准的、基于梯度的查找全局最小的方法都十分困难:

$\min f_{2} (x) = \sum_{i = 1}^{n} (x_{i}^{2} - 10 (\cos 2 π x_{i}) + 10)$

x∈[-5.12, 5.12]

3) f3是测试优化策略的求解精度, 是Griewank函数, 其极小值点为f (0, …, 0) =0。唯一极值点被无数局部极值点所包围, 是多模函数:

$f_{3} (x) = \frac{1}{4000} \sum_{i = 1}^{n} x_{i}^{2} - \prod_{i = 1}^{n} \cos (x_{i} / \sqrt{i}) + 1$

4) f4函数最小值在x≈ (420.9687, ….420.9687) 点fmin≈-12569.5:

$f_{4} (x) = \sum_{i = 1}^{n} x_{i} \sin (\sqrt{| x_{i} |}) x \in [- 500, 500]$

5) f5用于测试未成熟收敛性, 是Rosenbrock函数, 其二维函数虽然是连续单峰, 但却是病态的且极难极小化, 全局最小值为0:

$f_{5} (x) = \sum_{i = 1}^{n - 1} 1 00 (x_{i + 1} - x_{i}^{2})^{2} + (x_{i} - 1)^{2}$

6) f6函数在空间[-4, 4]时是一个分布不均的多峰函数, 对于遗传算法有一定难度:

minf6 (x1, x2) = (x $_{1}^{2}$ +x2-11) 2+ (x1+x $_{2}^{2}$ -7) 2

x∈[-10, 10]

7) f7用于测试算法可靠性、摆脱局部极值点及对多模函数优化问题的求解能力, 是一个Schaffer多峰函数, 全局最优值为0。但在最优值周围有无数个局部极小值, 是典型的一极值点多模函数:

$f_{7} (x_{1}, x_{2}) = 0.5 + \frac{\sin^{2} \sqrt{x_{1}^{2} + x_{2}^{2}} - 0.5}{[1.0 + 0.001 (x_{1}^{2} + x_{2}^{2})]^{2}}$

x∈[-5.12, 5.12]

为检验算法的有效性设计了三组实验。第一组实验:检验ACGA对于低维小定义域函数f1, f2, f3, f4, f5优化的性能。第二组实验:检验ACGA对于高维大定义域函数f1, f2, f3, f5优化的性能。因为对同一个函数来说, 高维和扩大的定义域使得探索空间范围扩大, 为遗传算法的搜索带来一定的难度。第三组实验:检验ACGA对多峰函数f6, f7优化的性能。

3.2 参数设置

分别对7个函数进行30次运算, 取最好的作为结果。各函数均采用混合编码方式;种群规模为50;双点交叉, 交叉概率为0.7;离散变异, 变异概率为0.01;运行100代。设定聚类数为8, 每隔3代对种群聚类一次;其中函数f1分别选择n=3, x∈[-3, 3]和n=30, x∈[-100, 100];函数f2分别选择n=2和n=30, x∈[-5.12, 5.12];函数f3选择n=2, x∈[-10, 10]和n=30, x∈[-600, 600];函数f5选择n=2, x∈[-2.048, 2.048]和n=30, x∈[-30, 30]。

3.3 仿真结果与分析

1) 图形分析

下列各图表中的算法分别是:SGA为经典遗传算法; FCGA是文献[1]提出的Family clustering GA算法, 是基于家庭聚类思想的遗传算法, 将个体按适合度排序后两两组成家庭进行交叉操作并使用了改进的变异算子;BFCGA是有族间交叉的FCGA[1]算法, 并采用了保留精英策略的变异算子, 是对FCGA[1]算法的一种改进;MSEP是文献[7]中提出的使用混合变异策略的演化算法, 算法中混合了Gaussian、Cauchy、Levy 和单点变异算子, 其MSEP数据取自文献[7]:f1运行1000代, f2运行5000代, f5和f3运行1500代, f4运行2000代;改进的GA是文献[11]提出的改进选择算子的遗传算法, 种群规模为50, 最大运行代数为2000;NCE-GA是文献[12]提出的一种具有自然血亲排斥的遗传算法, 其种群规模为100, 最大运行代数为2000; ACGA是本文提出的算法。下面以函数f1:n=30, x∈[-100, 100]和f4:n=30, x∈[-500, 500]时为例给出各算法的最佳适应度的关系 (如图1-图2所示) 。

从图中可以看出ACGA算法在收敛精度和收敛速度上都有较大优势, 在运行相同代数的情况下, ACGA算法求得的结果精度更高些。其原因是算法中的族间交叉操作使得种群在多个不同的区域同时进化;变异算子使算法更快地找到最优解。于是算法在保持种群多样性的同时提高了收敛速度。

2) 数据分析

为进一步分析其性能, 下面以最优适应度和平均适应度二个指标对各算法优化各函数的情况做详细比较。表1是对各函数取低维数小定义域各算法的结果对比;表2是对各函数高维数大定义域算法结果的对比;表3是对多峰函数实验结果的对比。

从表1和表3中可以看出算法ACGA和BFCGA都能够快速地找到函数的最优解, 甚至可以找到精确解, 这说明族间交叉算子和精英保留策略的变异算子使算法在进化过程中能快速收敛到最优解;其中ACGA在平均适应度值指标上较BFCGA更优一些;同时ACGA在运行100代即可找到最优解, NCE-GA虽然对f1也找到了最优解, 但其运行代数为2000, 收敛速度低于本文算法;在表2中各算法运行的代数与MSEP[7]中的运行代数一致以便于结果的对比, 但事实上ACGA算法在运行100代时同样可以找到最优解, 这说明算法的收敛速度是相当快的, 但此时它的平均适应度值较大;对于函数f4的优化结果可以看出, 优化结果-12596极其接近其近似值-12596.5, 说明ACGA对于最小值不是0的函数优化同样有效, 也说明ACGA在其它最小值为0的函数优化中找到最优解0不是偶然的。

4 结论

本文创新点是将生长树聚类的思想应用于遗传算法中, 并采用了新的遗传算子。通过对种群采用基于最小生成树的聚类方法聚类生成若干族, 再采用相应的族间交叉算子和族内交叉算子及采用精英保留策略后的变异算子, 即利用了聚类保持了种群多样性, 又能达到快速收敛的效果。实验已证明了算法的有效性。在实验过程中我们发现:在解空间是一维的情况下, 基于最小生成树的聚类方式与基于适应度的聚类方式结果是相同的;在理论上, ACGA算法对于有聚类特征的问题求解也应有较好的精度。这些还需实验进一步改进和证明。

参考文献

[1]徐立鸿, 沈于晴.一种基于家庭聚类思想的遗传算法[J].信息与控制, 2004, 33 (5) :527-530.

[2]Martin Pelikan, David E Goldberg.Genetic algorithms, clustering, andthe braking of symmetry University of Illinois[C].Tech Rep:2000013, 2000.

[3]厍向阳, 薛惠锋, 高新波.基于生长树的遗传聚类算法研究[J].计算机应用研究, 2006 (7) :62-64.

[4]Marra M A, Walcott B L.Stability and Optimality in Genetic AlgorithmControllers[C]//Dearborn:Proceedings of the 1996 IEEE InternationalSymposium on Intelligent Control MI-September:15-18, 1996:492-496.

[5]Petra Kudova.Clustering Genetic Algorithm[C]//18thInternationalWorkshop on Database and Expert Systems Applications, 1529-4188/07 DOI 10.1109/DEXA.2007.65, Computer Society:138-142.

[6]Norikazu IKOMA, Hiroshi MAEDA.Adaptive Order Selection with Aidof Genetic Algorithm[C]//Seoul, Korea:1999 IEEE InternationalFuzzy Systems Conference Proceedings August:22-25, 1999, 0-7803-5406-0/99 1999 IEEE (Ⅲ) :1785-1789.

[7]Hongbin Dong, Jun He, Houkuan Huang, Wei Hou.Evolutionary pro-gramming using a mixed mutation strategy[J].Information Sciences, 2007, 177:312-327.

[8]Swagatam Das, Ajith Abraham, Amit Konar.Automatic Clustering Usingan Improved Differential Evolution Algorithm[C]//IEEE Transactionson Systems, Man, and Cybernetics-Part A:Systems And Humans, 2008, 38 (1) :218-237.

[9]郑金华, 史忠植, 谢勇.基于聚类的快速多目标遗传算法[J].计算机研究与发展, 2004, 41 (7) :1081-1087.

[10]陆林花, 王波.一种改进的遗传聚类算法[J].计算机工程与应用, 2007, 43 (21) :170-172.

[11]陈有青, 徐蔡星, 钟文亮, 等.一种改进选择算子的遗传算法[J].计算机工程与应用, 2008, 44 (2) :44-50.

模糊聚类:遗传算法篇9

关键词：遗传算法,聚类分析,交叉概率,变异概率

0 引言

遗传算法(简称GA)作为一种自适应全局优化概率搜索方法,它最早由美国Michigan大学的Holland教授提出。该算法具有很好的鲁棒性、随机性、全局性,现已被人们广泛地应用于以下主要应用领域[1]:自动控制、图像处理、机器学习、数据挖掘。聚类分析[2]是模式识别理论的一个重要方法,聚类分析通常是基于距离的,通过构造一个m维空间的距离函数,利用这个距离函数来进行聚类。传统的基于聚类准则的聚类算法本质上是一种局部搜索算法,它们采用了一种迭代的爬山技术来寻找最优值。因此,存在两个问题:一是处理大数据量费时,二是容易陷入局部极小值。

利用遗传算法可以降低传统聚类算法对初始化的要求。例如傅景广[3]等人提出了一种基于遗传算法的聚类分析方法,该算法采用二进制编码方式对聚类的中心进行编码,用特征量与相应聚类中心的欧氏距离之和来判断聚类划分的质量;张伟[4]等人也提出了一种改进的遗传算法,并用来解决聚类问题;国外也有Krishna K等人于1999年在IEEE上发表的文章《Genetic K-means Algorithm》[5],也是一种遗传K-means聚类算法。本文在总结多位专家学者的研究后,改进了传统GA算法应用于聚类分析中的交叉概率和变异概率,引入了一种与进化代数相关联的交叉概率和与个体适应度相关联的变异概率,它们具有的自适应性质能够较好地改进算法的全局性能。将该改进算法应用到图像聚类实验,并且和k-均值算法进行了比较,结果表明了其准确率明显优越于k-均值算法。

1 改进的遗传算法

1.1 传统的GA

人们习惯上把1975年提出的GA称为传统的GA,它的主要步骤如下。

编码:GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据,这些串结构数据的不同组合便构成了不同的点。

初始群体的生成:随机产生n个初始串结构数据,每个串结构数据称为一个个体, n个个体构成了一个群体。GA以这n个串结构数据作为初始点开始迭代。

适应度评估检测:根据实际标准计算个体的适应度,适应性函数表明个体或解的优劣性。不同的问题,适应性函数的定义方式也不同。

选择:选择的目的是为了从当前群体中选出优良的个体,使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想,进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。

交叉:交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体,新个体组合了其父辈个体的特性。交换体现了信息交换的思想。

变异:变异首先在群体中随机选择一个个体,对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样,GA中变异发生的概率很低,通常取值在0.001～0.01之间。变异为新个体的产生提供了机会。

经典遗传算法的一次执行过程如图1所示,该图给出了第n代群体经过选择、交叉、变异生成第n+1代群体的过程。

1.2 自适应交叉概率pc与变异概率pm的设计

遗传算法中交叉概率控制着交叉算子使用的频率,交叉率越高,群体中结构的引入就越快,已获得的优良基因结果的丢失速度也相应提高了,而交叉概率太低则可能导致搜索阻滞。变异操作是保持群体多样性的手段,变异概率太小,可能使某些基因位过早地丢失信息无法恢复;而变异概率过高,则遗传算法将变成随机搜索。在传统GA算法中,pc和pm值在整个遗传优化过程中采用固定值,这就使得遗传算法在应用过程中出现一些问题(如收敛速度过慢、局部极值,很容易出现成熟收敛)。目前,国内外专家学者们认识到:如果pc、pm值能随着遗传进程而自适应地变化,那么这种有自组织性能的遗传算法将具有更高的鲁棒性、全局最优性和更快的收敛速度。

文献[6]中设计了与进化代数相关的交叉概率:

mtmp=pc,Max×2(-t/TGen) (1)

$p_{c} (t) = {\begin{cases} m_{t m p} i f (m_{t m p} ＞ p_{c, Μ i n}) \\ p_{c, Μ i n} e l s e \end{cases} (2)$

式中,mtmp是一个中间计算变量;TGen为预设的最大进化代数,t为当前进化代数(0≤t≤TGen);pc,Max是预设置的最大交叉概率;pc,Min是预设置的最小交叉概率;pc(t)是当前种群(第t代)的交叉概率。

在此基础上,本文利用Gauss函数和sigmoid函数构造与进化代数相关的交叉概率计算公式:

pc(t)=(pc,max-pc,min)·f(t)+pc,min (3)

f(t)=e-A(TGen-2t)+(1+e-B(TGen-2t))-1 (4)

式(4)中,A、B都为形状参数。该公式有利于加强GA算法在优化初期对新个体的开发和后期保护算法的稳定性。

同一代种群中各个个体的变异概率应该随个体优劣变化而变化。为了保证算法的稳定性,变异概率的取值应该是随进化过程而逐渐减小,从而使群体能够迅速集中。基于此,给出一种具有自适应的变异概率pm。

$\begin{array}{l} p_{m} (t) = \exp (\frac{f_{\max} - f (X_{i})}{f_{\max}}) (p_{m, \max} - p_{m, \min}) \cdot \\ f (t) + p_{m, \min} (5) \end{array}$

式(5)中, f(t)为式(4),f(Xi)为待变异个体的适应度值,fmax为第t代群体中的最优个体适应度值。pm,max为预设置的最大变异概率;pm,min为预设置的最小变异概率;pm(t)为第t代种群中个体的变异概率。

2 算法设计描述

综上所述,结合传统的GA算法,改进的自适应遗传算法步骤如下。

Step 1:初始化相关参数

初始化种群总数PopSize,初始代数T=0,预设的最大进化代数TGen,预设置的最大交叉概率pc,max,预设置的最小交叉概率Pm,min,为预设置的最大变异概pm,max;预设置的最小变异概率pm,min,选取参数A、B的值。

Step 2:产生初始种群

产生PopSize个满足约束条件的初始染色体xn,xi,min≤xi≤xi,max,k=1,2,…,PopSize,xi,min和xi,max分别为第i个染色体的约束条件,并计算每个染色体的评估值Value。

Step 3:适应值与评估值计算

对这个群体以Value值排序,求出序号index,根据index计算适应度值f(index),记录当前群体中最优和最差个体。建立适应度数组cfitness[PopSize],cfitness[i]的值为从第1个个体到第i个个体适应度值之和与所有个体适应值总和的比例。

Step 4:遗传运算

①选择运算

采用比例选择法执行选择操作,形成种群规模为PopSize的父代。

②交叉运算

对选择出的每一个染色体计算根据公式(3)、(4),以求得当前的,每个个体对按交叉概率pc经过杂交(即互换串中部分代码)产生两个新的子个体。

③变异运算

在群体中随机地选择一个个体,对于选中的个体以当前变异概率pm(由公式(4)、(5)求出)改变字符串中某位上的字符的值,以得到新的个体。

Step 5:停机判断

当前群体的进化代数是否大于最大迭代次数或是否达到最优解,否则转到Step 3继续执行。

3 实验仿真

目前国内外学者多用数据集进行聚类仿真并分析结果,本文现给出改进的自适应遗传算法在图像聚类方面的应用。通常在所给出的一幅图像中同时含有多个物体,在图像中进行聚类分析时需要对不同的物体分割标识。将改进的自适应遗传算法应用于图像聚类分析的重点是寻找这些物体特征的相似性。分别对三幅不同的二值图像分别应用本文算法和k-均值聚类算法进么图像聚类划分。要想对图像中的物体进行归类,则必须先找到各个物体,让计算机能够识别它们,因此,首先要确定物体是否是独立的目标物体,此处,图像中物体的标识依据图像的8点连通域判别方法。

图2(a)、图2(b)、图2(c)图分别为标准体数字的二值图、包含不同大小的几何图形物体的二值图、手写体数字的二值图。分别对三幅图用本文算法和k-均值聚类算法进么图像聚类划分,k-均值算法的迭代次数都设为100,物品间的距离计算公式采用欧式距离法。本文算法参数选取为:TGen=100,pc,min=0.1,pc,max=1,pm,min=0.01,pm,max=0.1,A=0.2,B=6.0。结果如图3所示(在进行聚类划分时,通过观察,可分别为图2(a)、图2(b)、图2(c)图标记类中心数目为4、3、4,)。

图3的各子图中,图3(a)-图3(c)图为应用k-均值聚类算法划分结果;图3(d)-图3(f)为应用本文算法划分结果。各子图内每个物体(数字或几何图形)的右下标即为类号,例如(d)图中,数字“4”的右下标都为1,说明被划分到“第1类”;数字“1”的右下标都为2,说明被划分到“第2类”;数字“2”的右下标都为3,说明被划分到“第3类”;数字“3”的右下标都为4,说明被划分到“第4类”。

为了比较两种算法,此处,定义识别率为ψ,令

$ψ = \frac{n}{Ν} (6)$

其中,n为当前被正确识别的物体数目,即既不存在同类物品归入不同类中,也不存在不同类物品归入同类中。N为总的识别物体数目,计算图3各子图中的识别率,统计得到表1。

由表1可知,本文算法对3幅图像中的物品均达到了准确的聚类划分,没有误差,而k-均值算法对3幅图像的物品的聚类划分都没有“成功”,效果不佳。实验表明,对比于k均值聚类算法,本文算法具有较好的聚类划分效果。

4 结束语

文中提出的一种改进的自适应遗传算法的聚类分类,在保证全局寻优能力和收敛速度的前提下,进一步提高了在聚类分析上的准确性,并通过实验仿真对比说明这一方法的可行性。但是,当图像内含物体(样品)数量多,物体(样品)本身有较高复杂性等情况时,用本文算法还是难以达到很高的准确率。因此还有许多工作有待进行更深一步的细致研究。

参考文献

[1]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2000.

[2]Han J,Kambr M.Data mining:Concepts and techniques[M].Be-jing Higher Education Press,2001.

[3]傅景广,许蹦,王裕目.基于遗传算法的聚类分析[J].计算机工程,2004.

[4]张伟,廖晓峰,吴中福.一种基于遗传算法的聚类新方法[J].计算机科学,2002,29(6):114-116.

[5]Krishna K,Muay MN.Genetic K-means Algorithm[J].IEEE Trans.on System,Man,and Cybernetics,Part B,1999,29(3):433-439.

【模糊聚类:遗传算法】推荐阅读：

遗传聚类08-28

模糊数学聚类07-08

遗传基因算法08-21

遗传禁忌算法09-01

遗传算法研究概述07-19