冷泳林;张清辰;赵亮;鲁富宇
【摘 要】K-means算法以其简单、快速的特点在现实生活中得到广泛应用。然而传统K-means算法容易受到噪声的影响,导致聚类结果不稳定,聚类精度不高。针对这个问题,提出一种基于离群点检测的K-means算法,首先检测出数据集中的离群点,在选择初始种子的时候,避免选择离群点作为初始种子。然后在对非离群点进行聚类完成后,根据离群点到各个聚类的距离,将离群点划分到相应的聚类中。算法有效降低离群点对K-means算法的影响,提高聚类结果的准确率。实验表明,在聚类类别数给定的前提下,在标准数据集UCI上该算法有效降低离群点对K-means算法的影响,提高了聚类的精确率和稳定性。%K-means algorithm is widely used in real life for its simple and rapid characteristics .However , traditional K-means algorithm is affected by outliers , leading to the instability of the clustering results and low accuracy of the clustering .For this problem , the paper proposes a novel K -means algorithm based on outliers detection .The presented algorithm firstly detects outliers from the given dataset , which can avoid selecting outli-ers as the initial seed .After clustering all the objects which are not outliers , the algorithm allocates every outlier to the corresponding cluster according to distance between the outlier and different clusters .The presented algo-rithm reduces the impact of outliers on traditional K -means algorithm and improves the clustering accuracy .For the given number of categories of the clusters and in the standard UCI data sets ,the experimental results indicate that the
algorithm is effective , reduces the influence of outlier on the K -means algorithm , improving the accura-cy and stability of the cluster . 【期刊名称】《渤海大学学报(自然科学版)》 【年(卷),期】2014(000)001 【总页数】6页(P34-38,48)
【关键词】聚类;K-means算法;离群点;UCI数据集 【作 者】冷泳林;张清辰;赵亮;鲁富宇
【作者单位】渤海大学 高职学院,辽宁 锦州 121001; 大连理工大学 软件学院,辽宁 大连 116621;大连理工大学 软件学院,辽宁 大连 116621;大连理工大学 软件学院,辽宁 大连 116621;渤海大学 高职学院,辽宁 锦州 121001 【正文语种】中 文 【中图分类】TP311 0 引言
聚类是将物理或抽象对象的集合分成由类似的对象组成多个类的过程,即“物以类聚,人以群分”.聚类是数据挖掘中的一类重要技术,是分析数据并从中发现有用信息的一种有效手段.它将数据对象分组成为多个类或簇,使得同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别很大〔1〕.聚类已经广泛应用于模式识别、空间数据分析、经济学等领域.聚类分析既可以作为单独的工具发现数据集中隐含的相关知识,又可以作为其他数据挖掘分析方法的预处理过程,其已经成为数据挖掘领域的一个重要的研究方向.
目前常用的聚类算法包括划分法、层次法、基于密度的方法、基于网格的方法和基于模型的方法等.其中,基于划分方法思想的K-means算法以其简单、快速并有效处理大规模数据等诸多特点,成为现实应用最为广泛的聚类算法.
K-means算法〔2,3〕适合聚类大型数据集,特别是当样本分布呈现类内团聚状时,可以达到很好的聚类结果.但是,在有噪声数据影响时,K-means聚类算法结果易受初始聚类中心影响,导致聚类结果不稳定.K-means算法过度依赖初始条件的缺点影响了该算法的聚类效果并制约了其应用范围.当前许多学者致力于改进K-means算法的聚类中心选取方法,如基于均值-标准差选取方法〔4〕,基于近邻密度选取方法〔5〕, 基于密度参数的选取方法〔6〕等,然而这些算法没有充分考虑离群点对聚类的影响,导致最后聚类精度提高不明显.针对这个问题,本文提出一种基于离群点检测的K-means算法,算法将离群点检测引入传统K-means算法,首先检测出数据集中的离群点,在选择初始种子的时候,避免选择离群点作为初始种子.在对非离群点进行聚类完成后,根据离群点到各个聚类的距离,将离群点划分到相应的聚类中.算法有效降低离群点对K-means算法的影响,提高聚类结果的准确率.实验表明,在聚类类别数给定的前提下,通过标准UCI数据库进行实验比较,在保留噪声数据的同时,该算法有效提高聚类精度. 1 相关理论和技术 1.1 基于距离的离群点检测
离群点是指明显偏离数据集中其他数据对象的数据点,人们怀疑这些点是由不同机制产生的〔7〕.离群点检测是数据挖掘领域中的一项重要挖掘技术.它可以发现数据集中小部分偏离了大多数数据行为或数据模型的异常数据.目前常用的离群点检测方法包括基于统计分布、基于距离、基于密度和基于偏差等方法〔8〕.其中,基于距离的离群点检测方法无需了解数据集的分布模型,适用于任何可以计算对象间距离的数据集,而且计算简单,因此本文采用该算法检测离群点.
如果对象o在数据集S〔9〕中有大于p部分的对象与它的距离都大于d,那么就将对象o称为数据集S上的DB(p,d)离群点.基于距离的离群点的定义适用于任意维度的数据集,其中参数p表明与离群点的距离大于d的对象所占数据集的最小比例〔10〕.
基于距离的离群点检测方法可以简便的定制对象间的距离函数,欧氏距离计算函数就是其中的一种.欧氏距离的定义如下:
其中m为数据对象的维(属性)数,xij表示第i个对象的第j属性的值. 基于距离的离群点检测算法主要步骤如下: 1.随机选取一个数据对象.
2.计算其他数据对象与选取的数据对象间的欧氏距离,如果与之距离大于d的数据对象的比例大于p,则判定该数据对象为离群点. 3.选取下一个不重复数据对象. 4.重复2,直到所有数据对象都被选到. 1.2 传统K-means算法
传统K-means算法的基本思想是〔11〕:随机地选择k个对象,每个对象初始代表了一个聚类中心;对剩余的每个对象根据其与各个聚类中心的距离,将它赋给最近的聚类;然后重新计算每个聚类的平均值,作为新的聚类中心.不断重复这个过程,直到准则函数收敛.收敛函数E定义为:
其中:E是数据集所有对象与它所在的聚类中心的平方误差的总和,E越大说明对象与聚类中心的距离越大,聚类内的相似度越低,反之E越小说明聚类内的相似性越高. 为聚类内的一个数据对象;是聚类Ci的聚类中心,k是聚类个数,Ci是第i个聚类.
K-means算法步骤如下:
1.随机选择k个数据对象,每个对象作为初始聚类中心.
2.计算每个数据对象与聚类中心的距离,根据距离将对象划分到距离最近的聚类. 3.重复计算每个聚类中对象的平均值,更新聚类中心. 4.重复2和3,直到准则函数E收敛. 2 基于离群点检测的K-means算法
基于离群点检测的K-means算法的基本思想是:首先利用基于距离的离群点检测方法检测数据集的离群点,然后在非离群点中随机选择k个数据点作为聚类的初始种子,利用传统K-means算法对非离群点进行聚类,最后将离群点划分到相应到聚类中.算法的思想如图1所示. 图1 基于离群点检测的K-means算法 算法具体步骤如下: 1.随机选取一个数据对象.
2.计算其他数据对象与选取的数据对象间的欧氏距离,如果与之距离大于d的数据对象的比例大于p,则判定该数据对象为离群点.
3.选取下一个不重复数据对象.重复2,直到将所有离群点检测出为止. 4.在非离群点中随机选取k个数据对象作为初始聚类种子.
5.计算每个非离群点数据对象与聚类中心的距离,根据距离将对象划分到距离最近的聚类.
6.重复计算每个聚类中对象的平均值,更新聚类中心. 7.重复5和6,直到准则函数E收敛.
8.计算每个离群点数据对象与聚类中心的距离,根据距离将其划分到最近的聚类. 算法描述如下:
输入:n个数据对象集S 和聚类数k;
输出:k个聚类中心Zj及k个聚类数据对象集合Cj; Begin
for r=1 to n //取数据集S中的各个数据对象 begin count=0;
for any q!=r //数据集中除了当前对象的其他对象 begin end
//离群点集A={a1,a2,...,ai};
M=S-A; //在S中去除数据集A中的数据对象,生成数据集M; k_means( M , k ); //执行传统的K_means算法; for r=1 to i do begin for q=1 to j End. 3 结果与分析
本文将传统的K-means算法和基于离群点检测的K-means算法进行实验对比.为了测试本文算法的有效性,实验选择专用于测试聚类算法性能的UCI数据库中的Iris数据集,Diabetes数据集和Wine数据集作为实验数据集.分别用传统聚类算法与本文提出的算法对3组数据集进行测试.本文实验环境为:CPU为E4500(2.20 GHz)、内存为1.99 GB、操作系统为Windows XP,编程语言为Java.
实验结果一:随机选择一批数据分别利用传统K-means聚类算法与本文改进的K-means算法对其进行聚类,结果示意图如图2所示. 图2 聚类结果示意图
由图2可知,传统K-means算法没有充分考虑离群点的影响,导致最后聚类结果不精确.本文在选择初始聚类中心时,避免选择离群点作为初始聚类中心,首先对非离群点进行聚类,最后根据离群点到与各个聚类的距离将其分配到相应的聚类中.本文有效避免离群点对聚类结果的影响,聚类精度高于传统K-means算法. 实验结果二:利用传统K-means算法与本文改进的K-means算法分别对3组数据进行6次实验,对实验结果进行统计,平均准确率如表1所示.
表1 传统K-means算法与本文算法聚类平均精度比较IrisDiabetesWine传统k-means算法0.79530.61880.9563本文算法0.83090.64840.9671 6次实验准确率统计曲线如图3所示.
Iris聚类结果曲线 Diabetes聚类结果曲线 Wine聚类结果曲线图3 实验结果统计曲线
从表1与图3可以看出,传统K-means算法的最高准确率与本文算法的平均准确率接近,但平均准确率明显低于本文改进的K-means算法.另外,传统K-means算法容易受到噪声影响,导致聚类结果不稳定,当不选择离群点作为初始种子时,聚类结果较好,否则聚类效果很差.本文避免选择离群点作为初始种子,因此聚类效果稳定,聚类精度高于传统K-means聚类算法. 4 结论
聚类分析是数据挖掘领域中常用的数据分析方法,目前聚类分析的主流方法有很多,其中基于划分的K- means算法以其简单、快速并有效处理大规模数据等诸多优点,成为最经典并应用最广泛的聚类方法之一.然而传统K-means算法容易受到离群点
的影响,导致聚类结果不稳定、聚类精度低,影响了该算法的聚类效果并制约了其应用范围.本文针对这个问题提出基于离群点检测的K-means算法,将离群点检测引入传统K-means算法,避免选择离群点作为初始聚类中心.在对非离群点进行聚类之后,根据离群点到各个聚类的距离,将其分配到相应的聚类之中.实验结果表明,算法在聚类精度上明显高于传统K-means算法. 参考文献:
【相关文献】
〔1〕Stalling W. Operating systems: internals and design principles(4th Edition)〔M〕.New Jersey, Prentice-Hall, 2001.
〔2〕MacQueen J. Some methods for classification and analysis of multivariate observations〔C〕. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley: University of California Press, 1967.
〔3〕张玉芳,毛嘉莉,熊忠阳. 一种改进的K-means算法〔J〕. 计算机应用, 2003,8(23):31-34. 〔4〕张文君,顾行发,陈良富,等. 基于均值-标准差的K均值初始聚类中心选取方法〔J〕. 遥感学报,2006,10(5):715-721.
〔5〕Shehroz S Khan, Amir Ahmad. Cluster center initialization algorithm for K-Means clustering〔J〕. Pattern Recogintion Letters(S0167-8655),2004,25(11):1293-1320. 〔6〕韩凌波,王强,蒋正锋,等. 一种基于改进的K-means初始聚类中心选取算法〔J〕. 计算机工程与应用,2010,46(17):150-153.
〔7〕Elio L, Edgar A. Parallel algorithms for distance-based and density-based outliers〔C〕.Proc of International Conference on IEEE. 2005: 767-776.
〔8〕Kriegel H P, Schubert M, Zimek A. Angle-based outlier detection in high-dimensional data〔C〕. Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining. ACM,2008:444-452.
〔9〕张秀梅,王涛.模糊聚类分析方法在学生成绩评价中的应用〔J〕. 渤海大学学报:自然科学版,2007,28(2):169-172.
因篇幅问题不能全部显示,请点此查看更多更全内容