优化K均值随机初始中点的改进算法.pdf

《优化K均值随机初始中点的改进算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、化工自动化及仪表第39卷优化K均值随机初始中点的改进算法王秀芳1‘2王岩二f1．北京邮电大学信息与通信工程学院，北京】00876；2．东北石油大学电气信息工程学院，黑龙江大庆163318)摘要针对传统K均值随机产生的初始聚类中心的方式提出最近邻K均值、极远邻K均值和自适应K均值3种优化算法。最近邻K均值是通过寻找多维空问下欧氏伊邻近点的方式确定K群；而极远邻K均值是极远盯邻判定确定法；自适应K均值是将数据集确定到矩阵中，对矩阵做归一化、二元化处理后，计算各向量间的相异度来修正确定初始中心点的加权欧氏距离。3种优化算法改善了原始K均值

2、算法，提高了算法的稳定性和精确度，而且它们各自适用于不同的应用空间。关键词最近邻K均值扳远邻K均值自适应K均值欧氏距离初始聚类中心中图分类号TH701文献标识码A文章编号1000-3932(2012)10—1302-03由聚类生成的簇是一组数据对象的集合，在同类中的对象之间具有较高的相似度，异类间的对象差别较大。聚类分析是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程，它是发现事物自然分类的一种方法，也是机器学习和模式识别的重要研究领域⋯。K—means聚类算法是处理大数据的经典算法，当簇群密集、簇间距明显时，该算法效

3、果较好。其主要研究方向包括：计算量繁杂的大型数据集；集群初始化一个先验；局部极小搜索问题。然而传统K—means算法随机选择初始聚类中心L2：，却对初值的依赖性极强，初值选取得不同往往会导致聚类结果的不稳定；其次，由于搜索方向的偏置会造成挖掘算法的迭代增加和算法效率很低，时间复杂度增加，因此采用合理的初始聚类中心，以此逐渐弥补K—raeans的缺陷显得尤为重要i3。1K-means聚类算法K-means聚类分析算法的工作原理是先随机从数据集中选取K点作为初始聚类中心H1，计算各样本到聚类中心的距离，把样本归到离它最近的聚类中心类。该

4、算法采用误差平方和准则函数作为聚类准则函数评价聚类性能"’6-。给定数据集x，确定x的初始聚类中点为{c，，c：，⋯，c；}，首次聚类完成后各类子集为{x。，x：，⋯，甄}，其中c。∈X。(i=1，2，⋯，k)。各个聚类子集中的样本数量分剐为挖．，珏：，⋯，n。；各个聚类子集的均值分别为；m-，，m：，⋯，m。}，与初始聚类中点jr；，c。，⋯。c；}比较，若两次比较无变化，聚类中心不变；否则进行下次迭代。误差平方和准则函数公式可表示^为：E=∑∑lip—c．酽。2IpE^．23种改进的K初始聚类中心算法针对K．means随机确定初

5、始K值的缺陷，在此总结了N2-K—means∞3、F2-K—means和SA—K—means改进初始聚类中心的算法来改善原算法，减小时问复杂度，提高算法效率。2．1N2．K．meansN2．K．means(Nearest2．K．means)即最近邻二点K初始值选取算法，目的是找到与数据集合在空间分布上相似程度较大的类集合。首先计算数据对象两两间的欧式距离，找出最近邻的两点，形成数据集合x；，并将它们从总集合u中删除；计算x．中每个数据对象与集合u中各样本的距离，找出在u中与x，最近邻的数据对象，将其并入X。内且从扩中删除，直至X。的

6、数据点达到阈值盯；再从U内找到最近邻两点形成夏：，重复上面的搜索过程，直至形成K集合为止；最后对各对象集合分别进行算术平均，形成K初始聚类中心。此时得到的K中心点更符合实际样本的分布状况，缩减了后期的迭代次数和计算量，提高运行效率，从而达到更好的聚类效果，但该算法容易收稿日期：2012-05-31(修改稿)基金项目：黑龙江省教育厅科学技术重点项目(125lIz002)第10期秀艿等．优化K均值随机}JJ始t}J点的改进斡：f2：l303忽略边缘聚类群，因而易忽略潜信息量多n价值大的规则，，2．2F2．K．meansF2．K-mean

7、s(Farest2一K—means)即极远邻二点K初始值选取算法，其目的亦是找到与数据集合在空问分布I二卡H似程度人的集合．汁算数据对象问的欧式距离后找出圾远邻的J从j点v，、』：，形成各自集合x，、!，并将其从集合U内删除；汁锋，Y。的数据对象x。与u内各样本的距离，找出最近邻数据对象并将其并入工。内，同时从集合f／中删除．直至x．的数据点满足阈值盯1．‘Y，做如x，的相同处理直至满足or，为止，接着再从集合￡，内找到最远邻形成x。L，重复I：叫的搜索过穆，直至找到K数据集合为止；最后对各对象集合进行算术平均，形成K初始聚类中心．

8、此时得到的K初始聚类点能明显地区分各样本点的分布状况，同样缩减了迭代次数和计算话．囊括了边缘聚类群；但该算法把离异点计算在内对规则形成r偏差，噪声影响过大：2．3SA．K．meansSA—K．Ineans(Self-adaptiveK