２０１４年第２３卷第３期 ｈｔｃｐ：／／ｗｗｗ．ｃ—Ｓ—ａ．ｏｒｇ．Ｃｒｌ 计算机系统应用 基于粒子群的近邻传播算法① 谢文斌，童楠，王忠秋，贾官洪，陈维奇，符强 （宁波大学科学技术学院，宁波３１５２１２） 摘要：针对近邻传播（ＡＰ）算法中偏向参数与收敛系数对ＡＰ算法的聚类效果的局限性的问题，提出了一种基于 粒子群的近邻传播算法（ｐｓｏ．ＡＰ算法）．通过将ＡＰ算法中的偏向参数与收敛系数作为粒子，然后使用粒子群算法 来对其进行智能地调整，进而提高ＡＰ算法的聚类效果．实验结果表明，该算法能有效地解决偏向参数与收敛系 数对ＡＰ算法的聚类效果局限性，提高了聚类效果与收敛精度． 关键词：近邻传播聚类；粒子群优化算法；偏向参数；收敛系数 Ａｆｉｎｉｔｙ ｆＰｒｏｐａｇａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ ＸＩＥ Ｗｅｎ—Ｂｉｎ，ＴＯＮＧ Ｎａｎ，ＷＡＮＧ Ｚｈｏｎｇ—Ｑｉｕ，ＪＩＡ Ｇｕａｎ－Ｈｏｎｇ，ＣＨＥＮ Ｗｅｉ—Ｑｉ，ＦＵ Ｑｉａｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｎｉｎｇｂｏ Ｕｎｉｖｅｒｓｉｔｙ，Ｎｉｎｇｂｏ ３ １ ５２ １２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ ａｔ ｔｈｅ ｐｒｏｂｌｅｍ ｔｈａｔ ｔｈｅ ｐｒｅｆｅｒｅｎｃｅ ｐａｒａｍｅｔｅｒ ａｎｄ ｄａｍｐｉｎｇ ｐａｒａｍｅｔｅｒ ｉｎ ａｆｉｎｉｆｔｙ ｐｒｏｐａｇａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｈａｖｅ ｌｉｍｉｔａｔｉｏｎｓ ｔｏ ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｃｌｕｓｔｅｒｉｎｇ，ｔｈｉｓ ｐａｐｅｒ ｐｕｔｓ ｆｏｒｗａｒｄ ａｎ ａｆｉｎｉｆｔｙ ｐｒｏｐａｇａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈ ｂａｓｅｄ ｏｎ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ－ＡＰ）．Ｂｙ ｔａｋｉｎｇ ｔｈｅ ｔｗｏ ｐａｒａｍｅｔｅｒｓ ｉｎ ａｌｇｏｒｉｔｈｍ ａｓ ａ ｐａｒｔｉｃｌｅ，ｔｈｅｎ ａｄｊｕｓｔ ｉｔ Ｉｎｔｅｌｌｉｇｅｎｔｌｙ ｂｙ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ（ｐｓｏ）ａｌｇｏｒｉｔｈｍ，ａｎｄ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｃｌｕｓｔｅｒｉｎｇ．Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｅｘｐｅｒｉｍｅｎｔ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ｅｆｆｅｃｔｉｖｅｌｙ ｓｏｌｖｅｄ ｔｈｅ ｐｒｏｂｌｅｍ，ｉｍｐｒｏｖｅｄ ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ａｎｄ ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｄａｍｐｉｎｇ． Ｋｅｙ ｗｏｒｄｓ：ａｆｉｎｉｔｙ ｐｒｏｐａｇａｔｉｆｏｎ；ＰＳＯ；ｐｒｅｆｅｒｅｎｃｅ ｐａｒａｍｅｔｅｒｓ；ｄａｍｐｉｎｇ ｐａｒａｍｅｔｅｒ 近邻传播（Ａｆｉｎｉｆｔｙ Ｐｒｏｐａｇａｔｉｏｎ简称ＡＰ）聚类算法【 】 是由Ｆｒｅｙ等人在Ｓｃｉｅｎｃｅ上提出的一种新的快速与有效 别进行调试取值，不但过程复杂，而且难于获得最佳参 数值，在很大程度上局限了ＡＰ算法的聚类效果． 本文针对上述问题提出了基于粒子群的近邻传播 的消息传递聚类算法．近邻传播算法的优势如下：第一， 该算法可以对较大的数据集进行较好较快的聚类；第 算法，通过粒子群算法的全局寻优能力来智能调整偏 向参数与收敛系数的值，使ＡＰ算法实现全局最优聚 类效果．利用新方法对各种类型的数据进行了聚类实 验分析，实验结果验证了算法的有效性． 二，该算法把每个数据样本作为待聚类的数据中心，这 使其不受初始中心；第三，该算法对相似度矩阵的 对称性没有要求，这扩展了该算法的应用范围．由于近 邻传播算法的种种优点，该算法被广泛的应用于人脸 识别、手写体字符识别、基因识别、最优航空路线确定 等问题上． １近邻传播聚类 与Ｋ ｍｅａｎｓ、模糊Ｃ等聚类算法相比较，ＡＰ聚类 算法不需要初始中心，它将每个数据点作为候选的聚 类中心，通过数据点之间的吸引与归属关系进行聚类． ＡＰ算法是根据建立的相似度（Ｓｉｍｉｌａｒｉｔｙ）矩阵进行 该算法中有两个重要的参数【 ：偏向参数与收敛系 数．这两个参数对聚类结果都有很大的影响：偏向参数 主要影响最后的聚类数目，收敛系数主要影响算法的 收敛速度与精度，但这两个参数往往需要通过实验分 聚类的．相似度矩阵Ｓ按（１）式建立，其的非对角线元 ①基金项目：浙江省教育厅科研项目（Ｙ２０１３２６７７０）；宁波大学科研基金项目（ＸＹＬ１２００９）；浙江省教育厅科研项目（Ｙ２０１３２６８７２） 浙江省教育科学规划课题（ＳＣＧ０９０１ 收稿时间：２０１３－０７．２３；收到修改稿时间：２０１３．０９．２２ Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ软件技术・算法１ ０３ 计算机系统应用 ｈｔｔｐ：／／ｗｗｗ．Ｃ—Ｓ・ａ．ｏｒｇ．ｃｎ ２０１４年第２３卷第３期 素ｓ（ｉ．ｋ１为点Ｘｌ与点Ｘｋ之间的关系，对角线元素 ｓ（ｋ，ｋ）为偏￣（Ｐｒｅｆｅｒｅｎｃｅ）参数Ｐ（ｋ），Ｐ（ｋ）的初始值一 般取相同的值，为相似度矩阵中所有非对角线元素最 小值或均值，其的初始大小对最后的聚类数有较大的 影响，Ｐ越大产生的聚类个数越多，反之亦然． （ｆ， ）：ａ（ｉ，ｋ）＝ｍｉｎ｛０，ｒ（尼，ｋ）＋∑ｍａｘ｛０，ｒ（ｉ ， ）｝｝ （４） ，７ ｆ， ｝ ａ（ｋ， ）＝∑ｍａｘ｛０，ｒ（ｉ ，ｊ．｝）） “７ ． （５） （６） ａ．ｅｗ（ｉ，ｋ）＝ Ｘａｏｌｄ（ｆ，ｋ）＋（１一 ）×ａ（ｉ，ｋ） 其中下标为ｏｌｄ的代表上一次的结果，ｎｅｗ代表本次更 ｊ—ＩＩ 一 ＩＩ ≠ｋ （１） 新后结果． 为收敛系数（ ）ｆ０，１））， 越大消除振荡 ＩＰ ｉ＝ ＡＰ算法的核心为数据点之间相互的信息传递，ＡＰ 算法有两种信息［３］，它们分别为吸引度（Ｒｅｓｐｏｎｓｉｂｉｌｉｔｙ） 与归属度（Ａｖａｉｌａｂｉｌｉｔｙ），建立过程如图１、图２所示． ｎ 数据点ｘ 、 图１吸引度的建立 由 数据点 图２归属度的建立 算法开始吸引度ｒ（ｆ， ）与归属度ａ（ｉ，ｋ）的初值都 为０，表示开始时数据之间没有任何聚类关系。它们按 （２）到（６）式更新．ｒ（ｉ，ｋ）为由点Ｘ 传到候选聚类中心点 Ｘ 的信息，它反映候选聚类中心点Ｘｋ作为点Ｘｌ的聚类 中心的适应程度．ａ（ｉ，ｋ１为由候选聚类中心点Ｘｋ传到 其所有潜在聚类成员点Ｘｉ，它反映点Ｘｉ作为点 的聚 类成员的适应程度．其中ｒ（ｋ，ｋ）与ａ（ｋ，ｋ）为点Ｘｋ的自 吸引度与自归属度这两个值越大说明其越适合作为聚 类中心［ ，一般把ｒ（ ，尼）与口（ ，ｋ）之和大于０的点就认 为其是一个较好的聚类中心． ｒ（ｉ，ｋ）：ｓ（ｉ，ｋ）一ｍａｘ２） ．，｛ａ（ｉ，ｋ ）＋ｓ（ｉ， ）｝ （．．．ｒ （ｆ，ｋ）＝ Ｘ ｒｏ （ｆ，ｋ）＋（１一 ）Ｘｒ（ｉ，ｋ） （３） １ ０４软件技术・算法Ｓｏｆｌｗ￣ｅ Ｔｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ 的效果越好，但收敛速度也越慢，反之亦然． 迭代的终止条件为：迭代次数超过最大值或者当 聚类中心连续多少次不发生改变时终止迭代． 最后根据得到的中心结合相似度矩阵对数据点进 行分类． ２实验数据集与指标 本实验中采用了ＢＷＰ指标ｌ５１对聚类结果进行评价 ＢＷＰ指标是基于样本的聚类距离和聚类离差距离提 出的． ＢＷＰ指标适用于衡量聚类数大于１的数据集，该 指标值的范围在．１到１之间，该值越大说明聚类结果 越好．之所以选用ＢＷＰ指标，是因为该指标可以有效 地反应类内紧密性与类间分离性，并且能对聚类结果 进行一个有效的评估． 本文选用了表１所示的５个数据集作为测试数据 集对本文提出算法进行验证和比较．其中选用的每个 数据集均为聚类分析中常用的数据集，而且各具特点， 有利于对聚类算法进行一个全面的分析 表１数据集特点 数据 数据 数据集 数据个数 数据类型 维数 类数 Ａｇｇｒｅｇａｔｉｏｎ１ ７８８ ２ ７ 混合 Ａｇｇｒｅｇａｔｉｏｎ２ ｌ９５ ２ ２ 紧密、环形 不完全分离、紧 Ａｇｇｒｅｇａｔｉｏｎ３ ３０７ ２ ２ 密 不完全分离、松 Ａｇｇｒｅｇａｔｉｏｎ４ ２３２ ２ ２ 散 Ａｇｇｒｅｇａｔｉｏｎ５ １４３ ２ ６ 完全分离、松散 ３ ＡＰ算法参数分析 为证明参数调整的必要性，以及通过参数调整优 化算法的可行性．本实验通过传统的方法对ＡＰ算法 的参数进行了分析． ３．１收敛系数 分析 在传统ＡＰ算法中收敛系数一般为固定值，但收敛 计算机系统应用 ｈｔｔｐ：／／ｗｗｗ．ｃ－ｓ—ａ．ｏｒｇ．ｃｎ ２０１４年第２３卷第３期 （１１详细的信息反馈机制． ２百度百科．ＬｅａｐＦＴＰ （２）可靠的传输保证机制（断点续传）． １１９５８０，ｈｔｍ，２０１３—３—１３， （３）操作简单，便捷． ３百度百科．ＦｌａｓｈＦＸＰ 介绍．ｈｔｔｐ：／／ｂａｉｋｅ．ｂａｉｄｕ．ｃｏｒｎ／ｖｉｅｗ／ （４１完善的曰志记录，易于排错． １７７８９０．ｈｔｍ．２０１３—３—１３． 由于目前大多数企业的文件传输使用的是操作系 ４百度百科．Ｓｅｒｖ．Ｕ 介绍．ｈｔｔｐ：／／ｂａｉｋｅ．ｂａｉｄｕ．ｃｏｒｎ／ｖｉｅｗ／ 统自带的ＦＴＰ功能，配置复杂，ＦＴＰ较为分散且不利于 ５３７９３３．ｈｔｍ．２Ｏ１３—３—１３． 管理，也没有断点续传功能．由于大多数企业数据还 ５王 ，罗万明，阎保平．并行下载最优机制．软件学报， 没有达到一定规模，商业的文件传输系统并没有得到 ２００９，２０（８）． 企业的重视，商用文件传输系统还没有实际应用的环 ６邓湘，吴迪．基于Ｐ２Ｐ的文件并行上载机制研究．ｈｔｔｐ：／／ｗｗｗ． 境，但随着企业不断发展，数据量不断增大，大数据 ｄｏｃ８８．ｃｏｍ／ｐ一９９５５３２３６９４９９．ｈｔｍ１．２０１３－３—１５． 时代的逐渐来临，商业文件传输，作为客户端与服务 ７志良的技术博客．深入探析ｃ撑Ｓｏｃｋｅｔ．ｈｔｔｐ：／／ｗｗｗ．ｃｎｂｌｏｇｓ． 端的数据传输工具，极大地方便了工作，提升了工作 ｃｏｍ／ｔｉａｎｚｈｉｌｉａｎ￣，ａｒｃｈｉｖｅ／２０１０／０９／０８／１８２１６２３．ｈｔｍ１．２０１３－３—１ 效率．如果在此基础上对系统进行进一步完善，构建 ５． 成复杂大型的文件传输引擎，将会产生极大的商业价 ８ Ｐａｌｍｅｒ Ｇ康博译．Ｃ≠｝程序员参考手册．北京：清华大学出版 值和经济效益． 社．２００２． ９周存杰．Ｖｉｓｕａｌ Ｃ≠｝．ＮＥＴ网络核心编程 Ｅ京：清华大学出版 参考文献 社，２００２． １百度百科．ＣｕｔｅＦＴＰ介绍．ｈｔｔｐ：／／ｂａｉｋｅ．ｂａｉｄｕ．ｃｏｍ／ｖｉｅｗ／ １Ｏ曾强聪．软件工程－ｊＥ京：高等教育出版社，２００４． １７７８７９．ｈｔｍ．２０ｌ３－３—１３． （上接第１０７页） 集，聚类起来相对容易，均能获取较好的聚类效果．但 ｄａｔａ ｐｏｉｎｔｓ．Ｓｃｉｅｎｃｅ，２００７，３ １ ５：９７２—９７６． 对比Ａｇｇｒｅｇａｔｉｏｎ １、Ａｇｇｒｅｇａｔｉｏｎ２、Ａｇｇｒｅｇａｔｉｏｎ３这三 ２王开军，张军英等．自适应仿射传播聚类．自动化学报， 个较难的数据集来说粒子群算法的聚类精度就明显不 ２００７，３３（１２）：１２４２—１２４６． 如ＰＳＯ．ＡＰ算法．总的来说ＰＳＯ．ＡＰ算法在对数据集的 ３刘胜字，刘家锋等．基于改进ＡＰ聚类算法的人脸标注技术 适应度与聚类精度上都要优于粒子群算法与普通的ＡＰ 研究．智能计算机与应用学报，２０１ １，１（１）：３５—３８． 算法． ４杨传慧，吉根林等．ＡＰ算法在图像聚类中的应用研究．计算 机与数字工程学报，２０１２，４０（１０）：１１９—１２１． ５ 结语 ５周世斌，徐振源等．一种基于近邻传播算法的最佳聚类数确 本文针对近邻传播（ＡＰ）算法中偏向参数与收敛系 定方法．控制与决策学报，２０１１，２６（８）：１１４７—１１５７． 数对ＡＰ算法的聚类效果的局限性的问题进行了分析 ６肖宇。于剑．基于近邻传播算法的半监督聚类．软件学报， 研究．首先，本文通过实验分别对偏向参数与收敛系 ２００８，１９（１ １）：２８０３－２８１３． 数进行调试取值，研究了偏向参数与收敛系数的特性． ７邢艳，周勇．基于互近邻一致性的近邻传播算法．计算机应用 然后，结合偏向参数与收敛系数的特性，提出了通过 技术．２０１２，２９（７）：２５２４—２５２６． 粒子群算法搜寻最优的偏向参数与收敛系数的方法， ８刘靖明，韩丽川Ｉ等．基于粒子群的Ｋ均值聚类算法．系统工程 使近邻传播算法达到一个最佳的聚类结果．最后，通 理论与实践，２００５，６：５４—５８． 过实验证明了ＰＳＯ．ＡＰ算法的有效性，且在聚类精度 ９陶新民，徐晶等．一种改进的粒子群和Ｋ均值混合聚类算法． 与适应性上要优于普通的ＡＰ算法与粒子群算法． 电子与信息学报，２０１０，３２（１）：５４—５８． 参考文献 １ Ｆｒｅｙ ＢＪ，Ｄｕｅｃｋ Ｄ．Ｃｌｕｓｔｅｒｉｎｇ ｂｙ ｐａｓｓｉｎｇ ｍｅｓｓａｇｅｓ ｂｅｔｗｅｅｎ ７６系统建设Ｓｙｓｔｅｍ Ｃｏｎｓｔｒｕｃｔｉｏｎ
