２０１７年１２月 舰船电子对抗 ＳＨＩＰＢＯＡＲＤ ＥＬＥＣＴＲＯＮＩＣ Ｃ０ＵＮＴＥＲＭＥＡＳＵＲＥ Ｄｅｃ．２０１７ Ｖｏ１．４０ Ｎｏ．６ 第４Ｏ卷第６期 改进Ｋ均值聚类算法 杨 娟，屈传慧 （西安电子科技大学，陕西西安７１００７１） 摘要：Ｋ均值聚类算法因需给定聚类中心数，使得聚类结果受初始化中心数的影响很大。介绍了Ｋ均值聚类法的 概念，并引入层次聚类的概念，采用先分解后合并的思想对Ｋ均值法进行了改进，对改进后算法进行了仿真验证。 关键词：Ｋ均值；聚类算法；分解合并 中图分类号：ＴＮ９１１．７ 文献标识码：Ａ 文章编号：ＣＮ３２—１４１３（２０１７）０６—００９１—０３ ＤＯＩ：１０．１６４２６／ｊ．ｃｎｋｉ．ｊｃｄｚｄｋ．２０１７．０６。０２０ Ｉｍｐｒｏｖｅｄ Ｋ ｍｅａｎｓ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ ＹＡＮＧ Ｊ ｕａｎ，ＱＵ Ｃｈｕａｎ－ｈｕｉ （Ｘｉｄｉａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ＇ａｎ ７１００７１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｂｅｃａｕｓｅ ｔｈｅ Ｋ—ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｎｅｅｄ ｔｏ ｇｉｖｅ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｅｒ ｎｕｍｂｅｒ，ｔｈｅ ｉｎｆｌｕｅｎｃｅ ｏｆ ｉｎｉｔｉａｌ ｃｅｎｔｅｒ ｎｕｍｂｅｒ ｏｎ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔ ｉｓ ｇｒｅａｔ．Ｔｈｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｃｏｎｃｅｐｔ ｏｆ Ｋ—ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｎｄｕｃｔｓ ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ ｃｏｎｃｅｐｔ，ａｄｏｐｔｓ ｔｈｅ ｉｄｅａ ｏｆ ｄｅｃｏｍ— ｐｏｓｉｔｉｏｎ ｂｅｆｏｒｅ ｃｏｍｂｉｎａｔｉｏｎ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ，ｓｉｍｕｌａｔｅｓ ａｎｄ ｖａｌｉｄａｔｅｓ ｔｈｅ ｉｍ— ｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：Ｋ—ｍｅａｎｓ；ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ；ｄｅｃｏｍｐｏｓｉｔｉｏｎ ａｎｄ ｃｏｍｂｉｎａｔｉｏｎ ０ 引 言 聚类，就是将样本分配到不同类的过程Ｅｌｉ。聚 过某个阈值，就把它加到与之相近的聚类中去，其代 表算法有ＤＢＳＣＡＮ算法、ＯＰＴＩＣＳ算法等［５］。在众 多的聚类方法中，Ｋ均值方法是一种最经典的也是 应用最广泛的聚类方法［６ ］，该方法对超球形和凸 状数据有很好的聚类效果。但是，由于经典Ｋ均值 算法必须在聚类前就设置聚类的个数Ｋ，最后所得 到的聚类结果会受到初始选择的聚类个数的影响。 若聚类个数选择得过小，可能导致同一类内的有些 样本差别过大，若聚类个数选择得过多，可能导致不 同类间的样本差别过小，都达不到有效聚类的目的。 因此，如何选择合适的聚类个数一直是聚类问题中 讨论的热点问题Ｌ８］。 本文基于Ｋ均值法，引入层次聚类的思想，对 类的基础为样本之间的相异性，聚类即寻找样本之 间的相似度对样本进行划分。 目前，常用的聚类方法包括：划分聚类、层次聚 类、密度聚类等。划分聚类就是对给定的数据集，采 用分裂法构造Ｋ个分组，每个分组就代表一个聚 类，且每一个分组至少包含一个数据纪录，每个分组 互不相交，即每一个数据纪录属于且仅属于一个分 组，常见的算法如Ｋ均值算法、ＣＬＡＲＡＮＳ算法 等［２］。层次聚类就是对给定的数据集进行层次分解 或者合并，直到所有的记录组成１个分组或者某个 条件满足为止，具体又可分为合并（自底向上）和分 解（自顶向下）２种方案，常见的算法有ＢＩＲＣＨ算 法、ＣＵＲＥ算法等［３ ］。密度聚类基于密度，它克服 了基于距离的算法只能发现超球形聚类的缺点，该 方法的基本思想就是只要一个区域中的点的密度大 收稿日期：２０１７一Ｏ６—２３ Ｋ均值法进行了改进，改善了Ｋ值的取值矛盾问 题，使得改进后的算法受初始聚类个数的影响变小， 有助于得到更好的聚类效果，且相比其它层次Ｋ均 值聚类算法，本算法实现简单。 ９２ 舰船电子对抗 第４Ｏ卷 １ 经典Ｋ一均值聚类 Ｋ均值算法能够使聚类域中的所有样品到聚 类中心距离平方和最小。其原理为：先取Ｋ个初始 聚类中心，计算每个样品到这Ｋ个中心的距离，找 出最小距离，把样品归入最近的聚类中心，修改中心 个聚类结果数据数的比值，当比值大于门限时．合并 第ｉ个聚类结果和第Ｊ个聚类结果，作为新的聚类 结果；当比值小于门限时，不合并，此文档中的门限 值取为定值０．５，即当２个聚类结果有一半以上数 据交叠时，将两者合并归为一类。 改进后的Ｋ均值算法流程如图１所示。 点的值为本类所有样品的均值，再计算各个样品到 新的聚类中心的距离，重新归类，修改新的中心点， 直到新的聚类中心和上一次聚类中心差距很小时结 束。此算法结果受到聚类中心的个数和聚类中心初 次选择影响，也受到样品的几个性质及排列次序的 影响。如果样品的几何性质表明它们能形成几块孤 立的区域，则算法一般可以收敛。 ２ 改进Ｋ均值聚类 Ｋ均值算法需设置聚类数，改进的Ｋ均值算法 初始化Ｋ值时，设置比较大的Ｋ值，此处Ｋ值具体 的设置需根据所聚类对象来设置，若无法判断，则只 罔１改进Ｋ均值聚类流程 ３ 仿真分析 一 为了比较传统的Ｋ均值法和改进后的Ｋ均值 法的效果差异，本文给出了Ｋ均值法的聚类结果和 改进Ｋ均值法的结果。仿真数据为二维３组高斯 数据，３组数据的均值不同，协方差相同，３组数据的 均值分别为： Ｊｆ１一Ｅｏ，ｏｌ， 们一［１．２５。１．２５３． 一需将其设置很大即可，但此时的计算量也将增大。 改进的Ｋ均值法采用先分后和的思想，即先将整个 数据根据Ｋ均值法聚类成设置的Ｋ个集合，再利用 各集合中心与其相对应的最大聚类半径确定的圆与 其它圆的交叠的比例来确定是否合并，当交叠比例 超过门限时，２个聚类结果合并，更新合并后的聚类 ．Ｔｉ，。＝Ｅ－１．２５，１．２５］，方差矩阵为：［。０－ 。（］１］， 结果，如此往复。直至所有的聚类结果不满足合并 条件，此时的结果作为最终的聚类结果。 聚类初始化个数为７。仿真结果如图２～图４所示。 交叠比例的计算方法为：计算第ｉ个聚类结果 中的每个元素与第 个聚类中心的欧氏距离，欧氏 距离的计算方法： ｄ． 一 式中： 为第ｉ个聚类结果中的第Ｐ个元素与第Ｊ 为第ｉ类聚类结果中的第Ｐ个 ２聚类前腺始数据 个聚类中心的欧氏距离，其中Ｐ为第ｉ个聚类结果 中的数据编号； 数据；．２－ 为第 个聚类中心； 为数据样本的维度， 本文中，ｎ一２。 第 个聚类结果的聚类半径ｒ 的计算方法为： ，ｒ ———————————一、 图２为聚类前的数据二维平面图，图３为Ｋ均 值法的聚类结果图。图４为改进后的Ｋ均值法的聚 类结果图。由仿真结果可得：改进后的算法对Ｋ均 值聚类分离的７类结果进行了相似合并，最终聚类 结果为３类，聚类效果较好。 ｒ 一ｍａｘ（ ／∑Ｉ 一 ，ｌ。） ｔ＝１ 式中：ｉ—ｌ，２，…，Ｋ；Ｐ一１，２，…，ｎ； 一１，２，…，Ｋ， 圭 。 当该距离小于第 个聚类半径，即ｄ ≥ｒｊ时， 交叠值加一；否则，不加一。最终计算交叠值与第ｉ 第６期 ， 杨娟等：改进Ｋ均值聚类算法 …９３ 加馅 Ｈ 的琢 ●，Ｊ＾Ｈ●ｕ”Ｊ… 黼 …击Ｉ｝ｉ …，Ｉ、．日笛津 ……一 ） 恂信笛 ’Ｊ Ｌｔ＾７Ｔ．１“，’Ｊ２ １ ５ 一・：再一 １ ． ＋々 ＋ … ．一 荔 ＿＿＿＿＿＿＿＿＿＿＿＿。●…； Ｌ ∞舳∞∞加∞舳∞∞ 实现简单，并对改进后的算法进行了仿真验证，该聚 Ｏ Ｏ ０ Ｏ ０ Ｏ Ｏ ０ Ｏ ０ Ｏ 辐 类算法可用于各种无监督聚类应用中，也可以用于 Ｊ’０ ５ 一 ０ ．鼋 －＿＿＿＿＿＿－ 一 鬯峨毛 ： 电子侦察中的信号分选模块。 参考文献 ［１］贺玲吴玲达，蔡益朝．数据挖掘中的聚类算法综述 ，—０ ５ 一ｌ ｝ 。・ ・ ・ ［Ｊ］．计算机应用研究，２００７，２４（１）：１０—１３． ［２］谢崇宝・袁宏源．最优分类的模糊划分聚类改进方法 ＥＪ］．系统工程，１９９７．１５（１）：５８—６３． １ ｃ ～－－２＿ －２－ｌ・５－‘－。 网３ Ｋ均值法聚类结果 １ ［３］Ｃｌｌ ＩＢＲＡＳＩ Ｒ Ｉ ，ＶＩＴＡＮＹＩ Ｐ Ｍ Ｂ．Ａ ｆａｓｔ ｑｕａｒｔｅｔ ｔｒｅｅ ｈｅｕｒｉｓｔｉｃ ｆｏｒ ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ［－ｊ］．Ｐａｔｔｅｒｎ Ｒｅｃｏｇ一 ｊ ２ １．５ １ ｏ ・』旌 ● ．［４］李凯，王兰．层次聚类的簇集成方法研究［Ｊ］．计算机工 ：：ｂ ［５］武佳薇，李雄飞，孙涛，等．邻域平衡密度聚类算法［Ｊ］． 程与应用，２Ｏ１０，４６（２７）：１２Ｏ一１２３． ｎｉｔｉｏｎ，２Ｏｌ１，４４（３）：６６２—６７７． ‘ ＋’＇ ●■ ¨ Ｊ’０．５ ０ ０．５ —潮 ｒｆ 篷 ～． ・ 计算机研究与发展，２０１０，４７（６）：１０４４—１０５２． 《墨 ｌ・５ ２ ２ ５ ［６］ ＫＡＮＵＮＧＯ Ｔ，ＭＯＵＮＴ Ｄ Ｍ．Ａ ｌｏｃａｌ ｓｅａｒｃｈ ａｐｐｒｏｘｉ— ｍａｒｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｋ—ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ［Ｊ］．Ｃｏｍｐｕｔａ— ｔｉｏｎａｌ Ｇｅｏｍｅｔｒｙ，２００４．２８（２，／３）：８９一ｌ１２． １ －ｔ －５－２－ｌ ５・・０・５ ０。ｔ ５ ［７］Ｅ１ ＫＡＮ Ｃ．Ｕｓｉｎｇ ｔｈｅ ｔｒｉａｎｇｌｅ ｉｎｅｑｕａｌｉｔｙ ｔｏ ａｃｃｅ１ｅｒａｔｅ Ｋ—ｍｅａｎｓ［ｃ］／／Ｐｒ。ｃｅｅｄｉｎｇｓ。ｆ Ｔｈｅ ２“ｄ ｌ“ ｅｍ ｉ。 ｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｉ ｅａｒｎｉｎｇ．Ｍｅｎｌｏ Ｐａｒｋ：ＡＡＡＩ 图４ 改进Ｋ均值聚类结果 ４ 结束语本文对Ｋ均值聚类算法进行了改进，改进后的 Ｐｒｅｓｓ，２００３：１４７—１５３． ［８］ 胡伟．改进的层次Ｋ均值聚类算法［Ｊ］．计算机应用研 究，２０１３，４９（２）：１５７—１５９． （上接第８２页） ４ 结束语 本文结合了线性调频连续波雷达和脉冲体制雷 达的传统信号处理方法，将其应用于连续波体制搜 甚鲢 罂 索雷达慢速小目标的检测。通过仿真结果分析和实 际工程应用，这一系列检测方法可有效检测出噪声 Ｊ… ．． －ｌＪ．一ｉ ＾ 和地物杂波背景下慢速小目标，而对于海杂波等背 景下慢速小目标的检测则需要进一步探索和研究。 『訇６ ＦＦＴ等相关处理后的结果 ２ １ １ １ ｌ ； 参考文献 ［１］ 杨帆．Ｉ．ＦＭＣＷ雷达信号处理算法研究及实现［Ｄ］．西 安：西安电子科技大学 ２００７． Ｉ ［２］ 张琳．线性调频连续波雷达信号处理技术［Ｄ］．西安： 西安电子科技大学．２００３． 譬－ Ｅ３］李鲜武．数字调频连续波测距雷达方程［Ｊ］．雷达科学 与技术，２００９．７（５）：３２９—３３２． ［４］ＳＫ（）Ｉ ＮＩＫ Ｍ Ｉ＿雷达系统导论［Ｍ］．林茂庸，程云明， 毛二可，等译．北京：国防工业出版社，１ ９９２． 罔７ ＣＦＡＲ处理后的结果