基于人工免疫粒子群优化算法的动态聚类分析

３９０　西安理工大学学报Ｊｏｕｒｎａｌ　ｏｆ　Ｘｉ’ａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ（２００８）Ｖｏ１．２４　Ｎｏ．４　文章编号：１００６－４７１０【２００８）０４－０３９０－０５　基于人工免疫粒子群优化算法的动态聚类分析　王磊，吉欢，徐庆征　（西安理工大学计算机科学与工程学院，陕西西安７１００４８）　摘要：模糊ｃ　均值聚类算法受初始化影响较大，在迭代时容易陷入局部极小值。将粒子群优化算　法与模糊Ｇ．均值聚类算法相结合，提出一种新颖的动态聚类算法。该算法利用人工免疫思想改进　粒子群优化过程，在很大程度上避免了粒子群算法和聚类算法早熟现象的发生，全局搜索能力和局　部搜索能力优于同类算法。利用聚类理论中的经验规则ｋ　≤√ｎ来确定聚类数ｋ的搜索范围，在　最优粒子基础上进化新一级种群，该方案可有效提高算法的收敛速度。两组数据的仿真实验表明，　新算法优于传统模糊ｃ．均值聚类算法，具有收敛速度快和解的精度高的特点。　关键词：人工免疫系统；粒子群优化算法；动态聚类；收敛性　中图分类号：ＴＰ３０１　文献标识码：Ａ　Ａ　Ｄｙｎａｍｉｃ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｎａｌｙｓｉｓ　Ｂａｓｅｄ　ｏｎ　Ａｒｔｉｆｉｃｉａｌ　Ｉｍｍｕｎｅ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｉｍｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ＷＡＮＧ　Ｌｅｉ，ＪＩ　Ｈｕａｎ，ＸＵ　Ｑｉｎｇ—ｚｈｅｎｇ　（Ｆａｃｕｌｔｙ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉ’ａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，ｘｉｉ’ａｎ　７１００４８，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｆｕｚｚｙ　Ｃ—ｍｅａｎｓ（ＦＣＭ）ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｓｅｎｓｉｔｉｖｅ　ｔｏ　ｔｈｅ　ｓｉｔｕａｔｉｏｎ　ｏｆ　ｔｈｅ　ｉｎｉｔｉａｌｉｚａｔｉｏｎ　ａｎｄ　ｅａｓｙ　ｔｏ　ｆａｌｌ　ｉｎｔｏ　ｔｈｅ　ｌｏｃａｌ　ｍｉｎｉｍｕｍ　ｗｈｅｎ　ｉｔｅｒａｔｉｎｇ．Ａ　ｎｏｖｅｌ　ｄｙｎａｍｉｃ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｃｏｍｂｉｎａｔｉｏｎ　ｏｆ　ＦＣＭ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｉｎ　ｔｈｉｓ　ｐａ－　ｐｅｒ．Ｔｈｅ　ａｒｔｉｆｉｃｉａｌ　ｉｍｍｕｎｅ　ｍｅｃｈａｎｉｓｍ　ｉｓ　ｉｎｔｒｏｄｕｃｅｄ　ｉｎ　ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａ—　ｔｉｏｎ，ＳＯ　ｔｈａｔ　ｔｈｅ　ｐｒｅｍａｔｕｒｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｏｆ　ＰＳＯ　ａｎｄ　ＦＣＭ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｖｏｉｄｅｄ，ｗｈｉｃｈ　ｍａｋｅｓ　ｔｈｅ　ａｌｇｏ・　ｒｉｔｈｍ’Ｓ　ｇｌｏｂａｌ　ｓｅａｒｃｈ　ａｎｄ　ｌｏｃａｌ　ｓｅａｒｃｈ　ｃａｐａｂｉｌｉｔｙ　ａｐｐｅａｒ　ｂｅｔｔｅｒ　ｔｈａｎ　ｎｏｒｍａｌ　ｏｎｅｓ．Ｔｈｅ　ｓｅａｒｃｈ　ｒａｎｇｅ　ｉｓ　ｄｅ—　ｔｅｒｍｉｎｅｄ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｅｘｐｅｒｉｅｎｔｉａｌ　ｒｕｌｅ后　≤√　ａｎｄ　ｔｈｅ　ｎｅｗ　ｐｏｐｕｌａｔｉｏｎ　ｉｓ　ｅｖｏｌｖｅｄ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｏｐｔｉ—　ｍａｌ　ｐａｒｔｉｃｌｅｓ，ｗｈｉｃｈ　ｍａｋｅｓ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｓｐｅｅｄ　ｉｎｃｒｅａｓｅｄ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｏｎ　ｔｗｏ　ｄａｔａ　ｓｅｔｓ　ｓｈｏｗ　ｔｈａｔ　ｗｈｅｎ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ｃｌａｓｓｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ，ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｃａｐａｂｌｅ　ｏｆ　ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｃｌｕｓｔｅ－　ｉｒｎｇ　ｐｅｒｆｏｒｍａｎｃｅ　ｓｉｇｎｉｆｉｃａｎｔｌｙ　ｉｎ　ｃｏｎｖｅｒｇｅｎｃｅ　ａｂｉｌｉｔｙ　ａｎｄ　ｓｏｌｕｔｉｏｎ　ｐｒｅｃｉｓｉｏｎ．　Ｋｅｙ　ｗｏｒｄｓ：ａｒｔｉｉｆｃｉａｌ　ｉｍｍｕｎｅ　ｓｙｓｔｅｍ；ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ；ｄｙｎａｍｉｃ　ｃｌｕｓｔｅｒｉｎｇ；ｃｏｎ－　ｖｅｒｇｅｎｃｅ　聚类分析是数据挖掘的重要内容，是非监督机　类中心会产生不同的聚类结果，甚至出现无解现象。　器学习的重要方法，已经被广泛应用于数据分析、模　受鸟群捕食行为规律的启发，Ｋｅｎｎｅｄｙ和Ｅｂｅｒｈａｒｔ　式识别、图象处理等方面…。目前模糊Ｃ一均值　提出粒子群优化算法（Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ，　（ＦＣＭ）聚类算法是最成熟的聚类算法之一，它用模　简称ＰＳＯ）　Ｊ。每个粒子都遵循简单的行为规则，　糊聚类的概念真实客观地反映现实，有效解决大多　通过粒子之间的协同作业来寻找最优解，具有较强　数事物没有严格属性、事物之间没有明确界限的问　的全局并行搜索能力，在函数优化、神经网络训练、　题。由于ＦＣＭ是基于梯度下降的寻优算法，算法往　模糊系统控制等领域得到普遍应用。但是，局部搜　往会陷入局部最优解，同时它受初始聚类中心影响　索能力较弱和易产生“早熟”现象是ＰＳＯ算法的两　较大，特别是在聚类数较大的情况下，不同的初始聚　个明显缺点。　收稿日期：２００８－０６—１６　基金项目：国家自然科学基金资助项目（６０６０３０２６）。　作者简介：王磊（１９７２．），男，陕西渭南人，教授，博导，博士，研究方向为人工免疫理论、智能计算、普适计算等。　Ｅ－ｍａｉｌ：ｌｅｉｗａｎｇ＠ｘａｕｔ．ｅｄｕ．ａｎ。　王磊等：基于人工免疫粒子群优化算法的动态聚类分析　３９１　近年来，人们受生物免疫系统及其功能的启发，　初始化为一群随机粒子（随机解），然后通过迭代找　开展人工免疫系统和算法的研究，并成功应用于聚　类、异常检测、计算机安全、函数优化和组合优化等　工程问题中　’４　Ｊ。聚类分析需要实现特征提取、识　别和学习等过程，而这些正是人工免疫算法所具有　的特征，目前已取得丰富的研究成果　。鉴于　到最优解；在每次迭代中，粒子通过跟踪两个极值来　更新自己，一个是粒子本身所找到的最优解：个体极　值Ｐ　，另一个是整个种群目前找到的最优解：全局　极值Ｇｈｅｓ　。　ＦＣＭ和ＰＳＯ算法存在的不足，以及人们往往不能事　先确定聚类数目的事实，本文通过引入免疫机制，提　假设在一个Ｄ维的搜索空间中，总粒子数为　ｍ，第　个粒子的位置表示为向量Ｘｉ＝（　¨　，　…，　），第ｉ个粒子的“飞翔”速度表示为向量　出一种基于人工免疫粒子群优化算法的混合动态聚　类算法（Ａｒｔｉｉｆｃｉａｌ　Ｉｍｍｕｎｅ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ＦＣＭ，即ＡＩＰＳＯ．ＦＣＭ）。该算法将ＦＣＭ和免疫粒子　群优化算法有机结合，初始聚类数遵循经验规则　ｋ　≤　（ｎ为空间粒子数），在此基础上逐级递减寻　找最优划分，在每一级划分中都采用免疫思想调整　粒子群优化过程。　ｌ　Ｃ－均值聚类算法　给定空间　，考虑ｎ个样本的数据集Ｘ＝　，　，…，　｝，按照它们之间的相似／相异性将　其划分为Ｋ类，通过迭代的方法寻找最优分类，直　到准则函数收敛。准则函数如式（１）所示。　Ｅ＝∑∑…　—ｍ　Ｊ　（１）　其中，Ｅ是数据集中所有对象的平方误差总和，　是　空间中的点，ｍ　是簇Ｃ　的平均值。　一般情况下，ｃ．均值聚类算法的基本流程如　下　：　步骤１从数据集｛　。，　，…，　｝中任意选择　ｋ个对象ｃ　，ｃ　，…，　作为初始簇中心；　步骤２根据簇中对象的平均值，将每个对象　赋给最类似的簇：如果ｄ（　，ｃ　）＜ｄ（　，ｃ　），　，　，　ｍ：１，２，…，ｋ，且　≠ｍ，则将　划分到Ｃ　中；　步骤３更新簇的平均值，即计算每个簇中对　，　象的平均值ｃ　，ｃ：　，…，ｃ　，其中ｃ　＝∑＾０∈ｂｉ　，／／Ｉ　　Ｇ　Ｉ，　ｉ＝１，２，…，ｋ，其中『Ｇ　ｆ为Ｇ　中点的个数；　步骤４计算平方误差函数Ｅ；　步骤５重复步骤２～４，直到结果不再发生明　显变化。　２基于人工免疫粒子群的动态聚类算法　２．１粒子群优化算法　粒子群优化算法采用速度一位置搜索模型　，　每个粒子都代表搜索空间中的潜在解，解的优劣程　度由适应度函数－厂决定。具体寻优过程如下：ＰＳＯ　Ｖｉ＝（　，…，／３　），Ｐ　为第　个粒子的历史最　优解，Ｇ　为所有粒子Ｐ　（　＝１，２，…，ｍ）的最优　解，每个粒子根据以下公式更新其速度和位置　］：　（ｔ＋１）＝ｔｏＵ　＋ｃ１　ｒｌ（ｔ）（Ｐ　（ｔ）一　（ｔ））＋　ｃ２ｒ２（ｔ）（　（ｔ）一Ｋｉｄ（ｔ））　（２）　（ｔ＋１）＝　（ｔ）＋　（ｆ＋１）　１≤ｉ≤ｎ，１≤ｄ≤Ｄ　（３）　个体极值和全局极值的更新依据为：　（ｔ＋１）＝ｐ　（ｔ）　ｌ如果　（￡＋１））＜ｔｉｐ　（ｔ）），　ｌＰｉａ（ｔ＋１）＝　（ｔ＋１）　（４）　【女日果　（ｔ＋１））≥　＾（ｐ　（ｔ））　ｇ（ｔ＋１）＝ｐ　（ｔ＋１）　如果ｔｉｐ　（ｔ＋１））＞￣ｆ（Ｐｊｄ（ｔ＋１）），ｉ≤ｍ√≤ｍ　（５）　其中∞＞１０，称为惯性因子，较大的　适于大范围探　查，较小的∞适于小范围开挖；ｃ　和ｃ　是正常数，称　为加速因子，一般取ｃ。＝ｃ　；ｒ　（ｔ）和ｒ２（ｔ）是［０，１］　之间的随机数。为防止粒子飞行速度过大而导致算　法过早收敛到局部最优解，一般根据实际问题人为　设定常数　＞０，限定　∈［一　，　］，较大的　保证粒子群的全局搜索能力，较小的　ｍａ　可以使　粒子在小区域精细搜索，它与ｔｏ的作用都是用来维　护全局和局部搜索能力的平衡。粒子群初始位置和　速度随机产生，然后根据式（２）和（３）进行迭代，在　解空间中不断跟踪个体极值和全局极值进行搜索，　直至达到规定的迭代次数或满足规定的标准误差为　止。　２．２编码策略和适应度函数　假设Ｄ维空间的样本集Ｎ＝｛Ⅳ　，　＝１，２，　…，ｎ｝包含ｎ个数据对象，在基于粒子群算法的聚　类分析中，粒子均由ｋ个聚类中心组成，每个粒子对　应一种聚类方式，即粒子　＝｛口　口　，…，口　｝，其　中口　代表第　个粒子的第　项，也就是第　种聚类方　式的第　个聚类中心。粒子群由多种侯选方案构　成，我们根据适应度的大小来评判方案的优劣。本　３９２　西安理工大学学报（２００８）第２４卷第４期　文适应度函数定义如下：　／１　ｋ　）＝１／÷∑Ｒ　Ｉ＝ｌ　（６）　（７）　步骤５若新的粒子群产生性能代价函数值更　低的粒子，则停止迭代，转至步骤２；否则继续迭代　直至产生更优粒子或达到预定迭代次数。　这种在最优粒子基础上产生新种群的方法，可　Ｉ　Ｒ　：‘　１，…，　√≠　ｍａｘ　ｄ　以使每一级的粒子优化都获得更优的初始侯选解，　提高算法的整体效率。　２．４免疫信息进化处理机制　其中，ｄ　＝１　—ａｔ　Ｉｌ表示两个聚类中心之间的距离，　Ａ　表示第ｉ类，Ｉ　Ａ　ｌ表示第ｉ类中包含的数据个　数，ｏ　表示第ｉ类所对应的聚类中心，Ｓ　＝（∑ｆｆＮ　ＶＥ＾　／　一口　ＩＩ）／Ｉ　ｌ表示口　对应分类的类内平均距　，　离＿９］。这样，可以使分类方案同时满足类内距离极　小和类间距离极大的要求，粒子的ｆ（　）值越大，代　表它所对应的分类方案越优，此粒子的生命周期也　越长。　２．３动态聚类的实现　常见聚类算法在聚类之前需要事先给定聚类数　目ｋ，但多数情况下聚类数目ｋ无法确定，因此需要　对最佳聚类数ｋ进行优化处理。为了达到动态聚类　的目的，本文首先利用经验规则　≤　确定ｋ的　搜索范围¨　，随后逐级递减ｋ值，在比较前后ｋ值　对应的不同粒子群中粒子性能优与差的基础上，动　态调整ｋ值，最终找到最佳ｋ值。这里我们定义一　个性能代价函数：　ｋ　ｋ　ｇ（　）＝∑Ｉ‘＝１　　ｓ　—ｓ　ｌ＋∑∑１Ｉ＝１　ＥＡｉ　Ⅳ一ｓｉ　１（８）　其中ｓ为全样本的均值，ｓ　为簇　所含样本的均值，　』、ｒ为任意样本数据。　）用于比较同一ｋ值下不同　分类方案的优劣，而ｇ（　）用于比较不同ｋ值下分类　方案的优劣。ｇ（　）以高内聚、低耦合为宗旨，综合　考虑到类内距离和类间距离对整体分类性能的影　响，ｇ（　）值越小，代表它所对应的分类方案性能越　好，分类代价越低。实验证明：性能代价函数能有效　指导算法寻找最优ｋ值，加快算法收敛速度。　每确定一次ｋ值，就需要重新初始化粒子种群，　具体实现步骤如下：　步骤１设定初始聚类数ｋ＝　，随机产生初　始粒子种群Ｍｏ；　步骤２　找出七对应的粒子群中性能代价函数　值最低的粒子，合并最相近的两个因子（即距离最　相近的聚类中心）；　步骤３　ｋ＝ｋ一１；　步骤４以缩减后的ｋ个聚类中心为中心点，　在空间中随机生成以它们为中心的若干点，再依照　排列组合原理随机组合生成若干粒子，组成新的粒　子种群；　ＰＳＯ算法初始为均匀分布在解空间中的若干可　能解，但由于其自身固有的缺点，在进化过程中不可　避免地产生种群退化现象。本文将人工免疫系统的　免疫信息进化处理机制引入到ＰＳＯ算法中，形成人　工免疫粒子群优化算法。免疫信息进化处理机制的　目的就是在复杂的问题中通过局部的特征信息找到　最佳的解决方案，即用局部的信息在一定程度上去　干扰全局的搜索过程，从而避免进化过程中的退化　现象，提高群体的适应度　。算法充分利用免疫系　统记忆、学习等特性，指导粒子群更快、更准地收敛　到最优解，在随后用于数据聚类的仿真实验中，得到　良好的聚类结果，体现出极大的优越性。算法涉及　的免疫模型如图１所示。　图１　免疫信息进化处理模型　Ｆｉｇ．１　Ｉｍｍｕｎｅ　ｅｖｏｌｕｔｉｏｎ　ｍｏｄｅｌ　２．４．１选择操作　在生物自然进化过程中，对生存环境适应度较　高的物种将有更多的机会遗传到下一代。模仿这个　过程，ＡＩＰＳＯ．ＦＣＭ算法采用精英选择和轮赌盘选择　相结合的选择策略对粒子群中的粒子进行优胜劣汰　操作。首先，我们选择其中５０％的优秀个体直接进　王磊等：基于人工免疫粒子群优化算法的动态聚类分析　３９３　人下一代群体；然后对所有粒子按适应度值由高到　低进行排列，计算剩余粒子的选择概率，按照轮盘赌　选择方法继续进行筛选。　假设Ｄ维搜索空间中的总粒子数为ｍ，粒子适　应度为．厂（　），则选择概率表示为：　，　ｍ　并其中最相近的两个因子（即距离最相近的聚类中　心）；　步骤４　ｋ＝ｋ—ｌ，初始化粒子种群　，粒子个　数取ｍ，根据式（６）计算所有粒子的适应度．厂（　）；　步骤５计算粒子的个体最优与全局最优，把　适应度较高的粒子作为免疫记忆细胞保存到记忆　库，若算法满足终止条件，停止迭代，所有粒子的性　能代价函数ｇ（　），若出现低于ｋ＋１级所有粒子性　ｐ（ｘｉ）＝厂（　ｉ）／∑　）　（９）　从中我们可以清晰看出，对粒子群进行以上两　步选择，就能保证下一代群体中的最佳个体绝对优　于上一代群体的最佳个体。　２．４．２变异操作　传统免疫理论中免疫系统主要通过变异来保证　细胞的多样性　。在此理论基础上，我们把筛选出　粒子的每一项作为免疫细胞，引入一种自适应变异　算子：　＝　＋Ｎｍ　×Ｎ（０，１）　（１０）　其中，Ｎ（Ｏ，１）是一个服从标准高斯分布的随机数，　Ｎｍ　是免疫细胞的变异率，遵循如下公式：　，，　、　Ｎｍ　Ｐ×　Ｊ而＼￣ｉ／　（　）　其中，Ｐ为变异因子，用来调整变异强度，与搜索的空　间大小和样本规模有关　（　）是筛选出的免疫细胞　的适应度值。显然，细胞的变异率与其适应度成反　比，适应度越高变异率越小，细胞在每次迭代过程中　根据适应度自适应的调整变异步长，在保留最佳个体　的同时改进较差个体，有效提高算法的收敛速度。　２．４．３免疫记忆　免疫记忆是指免疫系统将与入侵抗原反应的抗　体作为记忆细胞保存下来，当同类抗原再次人侵时，　记忆细胞被激活并迅速扩增分化大量抗体，杀死抗　原，执行高效而持久的免疫功能。在ＡＩＰＳＯ—ＦＣＭ算　法中，这种思想被用来保存优秀粒子，即将每次迭代　过程中产生的优秀粒子看作记忆细胞，用来替代后　代中适应度相对较低的粒子，从而保证下一代群体　的整体适应度明显高于上一代群体，加快算法优化　速度。　２．５　ＡＩＰＳＯ—ＦＣＭ算法基本流程　将免疫的思想融人粒子群优化算法实现动态聚　类，算法的基本流程如下：　步骤１设定初始聚类数ｋ＝　；　步骤２确定相关参数：聚类样本数／ｔ＇，群体规　模Ⅳ，惯性因子∞，加速因子ｃ。，Ｃ　，最大进化数　Ｄ…；　步骤３利用式（８）计算性能代价函数值，找出　ｋ对应的粒子群中性能代价函数值最低的粒子，合　能代价函数值的粒子，最佳聚类数为ｋ，否则为ｋ＋　１；否则，进入步骤６；　步骤６通过式（２）和（３）对粒子状态进行更　新，包括速度和位置向量；　步骤７利用式（９）和（１０）对这ｍ个粒子进行　选择、变异操作，形成新的粒子群　，并将其中适应　度较差的若干粒子用记忆库中的免疫记忆粒子替换；　步骤８　计算当前群体中所有粒子的适应度　）和性能代价函数ｇ（　），若出现低于ｋ＋１级所有　粒子性能代价函数值的粒子，则停止迭代，转至步骤　３；否则，舍弃适应度低的粒子，复制部分适应度较高　的粒子，保证群体中粒子总数为ｍ，转至步骤５。　３仿真实验　为了验证ＡＩＰＳＯ—ＦＣＭ算法的可行性与高效性，　本文通过两组数据来比较基于免疫粒子群优化算法　的聚类和传统ｃ－均值聚类的性能。实验开发环境　为：Ｐ４　２．０　ＧＢ　ＣＰＵ，ＤＤＲ５１２　ＭＢ内存，Ｗｉｎｄｏｗｓ　ＸＰ　操作系统，ＭＡＴＬＡＢ　６．０开发语言。　第一组实验数据集包括１００名学生的学习成绩　数据，每个数据包含３个属性，分别代表学生的语文、　数学、英语成绩。由经验规则可以得到ｋ的初始值为　ｋ＝　１０ｏ＝１０，实验中有关参数设定如下：粒子个数　ｍ＝１００，惯性因子　＝０．６，加速因子ｃ。＝ｃ２＝２，速　度阈值　＝２．３，最大迭代次数Ｄ　＝２００。采用　多次实验取最优结果的方法，最终由ＡＩＰＳＯ—ＦＣＭ算　法得到数据集划分的最优聚类数目　＝３，即依据三　科成绩把学生分为优、中、差三组。为了比较方便，表　１列出了ｋ＝３时ＡＩＰＳＯ—ＦＣＭ算法和经典ＦＣＭ算法　的适应度值，图２显示了数据集的最终聚类效果，其　中“▲”代表各组的聚类中心。　Ｔａｂ．１表１　Ｔｈｅ　ｃｏｍｐａｒｉ　ＡＩＰＳＯ－ＦＣＭ算法与ＦＣＭ算法适应度值比较　ｓｏｎ　ｏｆ　ｉｆｔｎｅｓｓ　ｂｅｔｗｅｅｎ　ＡＩＰＳＯ—ＦＣＭ　ａｎｄ　ＦＣＭ　３９４　唿　图２　ＡＩＰＳＯ—ＦＣＭ算法聚类结果　Ｆｉｇ．２　Ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｒｅｓｕｌｔ　ｏｆ　ｔｈｅ　ＡＩＰＳＯ—ＦＣＭ　ａｌｇｏｒｉｔｈｍ　第二组数据为Ｉｒｉｓ蔫尾花实际数据集¨　，包含　１５０种蔫尾花的信息，分为３类，每个样本数据包含　４种属性，分别是尊片长度、曹片宽度、花瓣长度和　花瓣宽度，参数设置与第一组数据相同。表２为两　种算法的实验结果。　表２　ＡＩＰＳＯ—ＦＣＭ算法与ＦＣＭ算法比较结果　Ｔａｂ．２　Ｔｈｅ　ｃｏｍｐａｒｉｓｏｎ　ｂｅｔｗｅｅｎ　ＡＩＰＳＯ－ＦＣＭ　ａｎｄ　ＦＣＭ　从实验结果可以看出，基于人工免疫粒子群优　化算法的聚类收敛精度明显高于传统模糊ｃ一均值　聚类算法，大大提高了获得全局最优解的概率。　４结论　在分析传统聚类算法和粒子群算法的不足之处　的基础上，我们提出ＡＩＰＳＯ－ＦＣＭ算法。选择和变异　算子保证算法始终以优秀粒子为主要的优化对象，　免疫记忆机制能够及时为粒子群补充优秀粒子，确　保粒子种群的多样性，算法还利用聚类经验规则　。　≤　来控制ｋ的搜索范围，在比较前后ｋ值对应　的粒子群中粒子性能代价函数值大小的基础上，动　态调整ｋ值，解除传统聚类算法必须事先明确聚类　数目的约束，提高算法的适应性。实验表明，该算法　大大提高获得全局最优解的概率，正确率明显高于　经典聚类算法ＦＣＭ，在收敛精度方面体现出极大的　优越性。　通常，基于免疫机制聚类算法的收敛精度较一　般算法要高，但是其收敛速度却稍慢，因此下一步将　重点研究提高收敛速度的措施和方法。另外，算法　有待接受更多实际问题的检验，特别是存在噪声数　据情况下的检验。　西安理工大学学报（２００８）第２４卷第４期　参考文献：　［１］Ｈａｎ　Ｊ　Ｗ，Ｋａｍｂｅｒ　Ｍ．Ｄａｔａ　Ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ　ａｎｄ　Ｔｅｃｈ－　ｎｉｑｕｅｓ［Ｍ］．Ｓａｎ　Ｆｒａｎｓｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ，　２００１．　［２］Ｋｅｎｎｅｄｙ　Ｊ，Ｅｂｅｒｈａｒｔ　Ｒ　Ｃ，Ｓｈｉ　Ｙ．Ｓｗａｒｍ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　［Ｍ］．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎ　Ｐｕｂｌｉｓｈｅｒ，２００１．　［３］Ｋｌａｒｒｅｉｃｈ　Ｅ．Ｉｎｓｐｉｒｅｄ　ｂｙ　ｉｍｍｕｎｉｔｙ［Ｊ］．Ｎａｔｕｒｅ，２００２，　４１５（３１）：４６８－４７０．　［４］Ｈａｒｔ　Ｅ，Ｔｉｍｍｉｓ　Ｊ．Ａｐｐｌｉｃａｔｉｏｎ　ａｒｅａｓ　ｏｆ　ＡＩＳ：Ｔｈｅ　ｐａｓｔ，ｔｈｅ　ｐｒｅｓｅｎｔ　ａｎｄ　ｔｈｅ　ｆｕｔｕｒｅ［Ｊ］．Ａｐｐｌｉｅｄ　Ｓｏｆｔ　Ｃｏｍｐｕｔｉｎｇ，２００８，　８（１）：１９１—２０１．　［５］Ｄｅ　Ｃａｓｔｒｏ　Ｌ　Ｎ，Ｖｏｎ　Ｚｕｂｅｎ　Ｆ　Ｊ．Ａｎ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｉｍｍｕｎｅ　ｎｅｔｗｏｒｋ　ｆｏｒ　ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｂｒａｚｉｌｉａｎ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ａｒｔｉｉｆｃｉａｌ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ，Ｒｉｏ　ｄｅ　Ｊａｎｅｉｒｏ，Ｂｒａｚｉｌ，２０００：８４—８９．　『６］Ｎｅａｌ　Ｍ．Ｍｅｔａ．ｓｔａｂｌｅ　ｍｅｍｏｒｙ　ｉｎ　ａｎ　ａｒｔｉｉｆｃｉａｌ　ｉｍｍｕｎｅ　ｎｅｔ．　ｗｏｒｋ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　Ｓｅｃｏｎｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　Ａｒｔｉｆｉｃｉａｌ　Ｉｍｍｕｎｅ　Ｓｙｓｔｅｍｓ，Ｅｄｉｎｂｕｒｇｈ，ＵＫ，２００３：１６８一　ｌ８１．　［７］Ｊａｉｎ　Ａ　Ｋ，Ｍｕｒｔｙ　Ｍ　Ｎ，Ｆｌｙｎｎ　Ｐ　Ｊ．Ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ：Ａ　ｒｅ—　ｖｉｅｗ［Ｊ］．ＡＣＭ　Ｃｏｍｐｕｔｅｒ　Ｓｕｒｖｅｙ，１９９９，３１（３）：２６４—　３２３．　［８］Ｅｂｅｒｈａｒｔ　Ｒ　Ｃ，Ｓｈｉ　Ｙ．Ｃｏｍｐａｒｉｎｇ　ｉｎｅｔｒｉａ　ｗｅｉｇｈｔｓ　ａｎｄ　ｃｏｎ—　ｓｔｒｉｃｔｉｏｎ　ｆａｃｔｏｒｓ　ｉｎ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］∥Ｐｒｏ—　ｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　２０００　Ｃｏｎｇｒｅｓｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，　Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ，２０００：８４－８８．　［９］Ｚｈａｎｇ　Ｄ　Ｘ，Ｌｉｕ　Ｘ　ｚ，Ｇｕａｎ　ｚ　Ｈ．Ａ　ｄｙｎａｍｉｃ　ｃｌｕｓｔｅｒｉｎｇ　ａｌ—　ｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｐｓｏ　ａｎｄ　ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　ｆｕｚｚｙ　ｉｄｅｎｔｉｉｆｃａｔｉｏｎ　［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｈｉｄｉｎｇ　ａｎｄ　Ｍｕｌｔｉｍｅｄｉａ　Ｓｉｇｎａｌ　Ｐｒｏ—　ｃｅｓｓｉｎｇ，Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ，２００６：２３２—２３５．　［１Ｏ］杨善林，李永森，胡笑旋，等（Ｙａｎｇ　Ｓｈａｎ－ｌｉｎ，Ｌｉ　Ｙｏｎｇ—　ｓｕｎ，Ｈｕ　Ｘｉａｏ－ｘｕａｎ，ｅｔ　ａ１）．Ｋ－ｍｅａｎｓ算法中的　值优化　问题研究（Ｏｐｔｉｍｉｚａｔｉｏｎ　ｓｔｕｄｙ　ｏｎ　ｋ　ｖａｌｕｅ　ｏｆ　Ｋ－ｍｅａｎｓ　ａｌｇｏ・　ｒｉｔｈｍ）［Ｊ］．系统工程理论与实践（Ｓｙｓｔｅｍｓ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｔｈｅｏｒｙ　ａｎｄ　Ｐｒａｃｔｉｃｅ），２００６，２６（２）：９７一１０１．　［１　１］Ｗａｎｇ　Ｌ，Ｃｏｕｒａｎｔ　Ｍ．Ｍｕｈｉｕｓｅｒ　ｄｅｔｅｃｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｉｍ—　ｍｕｎｅ　ｓｔｒａｔｅｇｙ　ＲＢＦ　ｎｅｔｗｏｒｋ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　９ｔｈ　Ｉｎ—　ｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｎｅｕｒｌａ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ，　Ｈａｖａｎａ，Ｃｕｂａ，２００２：１４８５—１４８９．　［１２］焦李成，杜海峰（Ｊｉａｏ　Ｌｉ—ｃｈｅｎｇ，Ｄｕ　Ｈａｉ—ｆｅｎｇ）．人工免　疫系统进展与展望（Ｄｅｖｅｌｏｐｍｅｎｔ　ａｎｄ　ｐｒｏｓｐｅｃｔ　ｏｆ　ｔｈｅ　ａｒｔｉ—　ｉｆｅｉａｌ　ｉｍｍｕｎｅ　ｓｙｓｔｅｍ）［Ｊ］．电子学报（Ａｃｔａ　Ｅｌｅｃｔｒｏｎｉｃａ　Ｓｉｎｉｃａ），２００３，３１（１０）：１５４０—１５４８．　［１３］ＵＣＩ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ［ＥＢ／ＯＬ］．［２００８—１２－０１］．ｈｔｔｐ：　７ｆ　ｎ　．ｉｃｓ　ｕｃｉ　ｅｄｕ／～ｍｌｅａｍ／．　（责任编辑杨小丽）