一种改进的聚类算法

一种改进的聚类算法

随着数据处理研究领域技术的发展，分组算法作为本文创业的主要方法之一越来越受到重视。在众多的聚类算法中,k均值聚类算法的应用领域非常广泛,包括图像及语音数据压缩,使用径向基函数网络进行系统建模的数据预处理,以及异构神经网络结构中的任务分解,因此研究k均值算法的优化是很有必要的。原k均值算法对孤立点很敏感,少量的这些孤立点会对聚类结果产生较大的影响,本文从减小孤立点对聚类结果的影响这一点出发对其加以改进。1原始k-mean算法1.1聚类算法聚类最常用的基于划分的聚类算法是k-means算法,该算法不断计算每个聚类Si的中心,也就是聚类Si中对象的平均值,作为新的聚类种子。k-means聚类算法的步骤为:1)随机选取k个不同的数据对象作为k个类的代表;2)将数据对象分配给距离最近的某个类代表所属的类,形成k个类,计算聚类准则函数;3)计算各个类的重心,将这些重心作为各个类的代表,若这些代表与划分前的代表相同或两轮聚类准则函数的值之差小于一定的数则终止,否则转2)。1.2k-meas算法原k-means算法仅能处理数字属性;需要预先设定初始中心,还需要预先知道类的数目,只能得到次优解。当结果簇密集并且各簇之间的区别明显时,采用k-means算法的效果较好。k-means算法对于数据集中孤立点很敏感,少量的这类数据将对聚类结果产生较大的影响。为此,提出了一种改进的k均值算法,改进后的k均值算法能很好地处理数据中存在孤立点的问题。2聚类分离的计算方法用k均值算法进行数据聚类时,可以看出结果的稳定性还存在很大的问题,有时聚类的效果非常好(当数据分布呈凸形或球形的时候聚类的效果会非常好),而有时聚类结果会出现明显的偏差和错误,这种偏差和错误产生的原因在于数据的分散性。聚类的数据不可避免地会出现孤立点,即少量数据远离高密度的数据密集区的情况,但我们在进行k均值聚类计算时,是将聚类均值点(类中所有数据的几何中心点)作为新的聚类种子进行新一轮聚类计算,在这种情况下,新的聚类种子可能偏离真正的数据密集区,从而导致聚类结果出现偏差。由此可以看出,k均值算法处理孤立点数据时有很大的局限性。采用聚类均值点与聚类种子相分离的思想,在改进算法中,对原算法中的步骤3按如下方式计算,当进行第k轮聚类种子的计算时,采用簇中那些与第k-l轮聚类种子相似度较大的数据,计算它们的均值点作为第k轮聚类的种子,相当于把孤立点排除在外,孤立点不参加聚类中心的计算,这样聚类中心就不会因为孤立点的原因而明显偏离数据集中的地方,而导致了聚类结果出现不应有的问题。这种聚类均值点和聚类种子相分离的思想,最主要的就是做到在计算新一轮的聚类中心的时候,尽量不把对聚类结果有影响的孤立点计算在内。因此在计算聚类中心的时候,要用一定的算法把孤立点排除在用来计算均值点的那些数据之外。可以用的计算方法有很多,对聚类过程和结果的影响是不同的,改进算法采用以下两种计算方法。第一种计算步骤如下:1)对于第k-1轮聚类获得的类,计算类中数据与该类聚类种子相似度最小的相似度simmin和数据中与该类聚类种子相似度最大的相似度simmax;2)选择类中与聚类种子相似度大于(simmax+simmin)/2的数据组成每个类的一个子集;3)计算子集中数据的均值点,作为第k轮聚类的聚类种子。这样每一轮参加聚类种子计算的数据都是与前一轮的聚类种子相似度大的数据,如果存在孤立点,就会因为孤立点不参与聚类种子的计算而有效地避免其对聚类结果的影响。采用(simmax+simmin)/2计算,当类中有明显的孤立点时,即simmax和simmin差别较大时较好,但是如果某个类中的数据都比较密集,没有明显的孤立点时,即simmax和simmin的差别并不大时,在每一次计算聚类中心时采用这个式子就会排除很多不是孤立点的数据,聚类中心在从初始值到最终值的移近过程中就会移近很慢,因此聚类的迭代次数会增加。为解决此问题,在数据本身就较集中时让更多的数据参与到聚类中心的计算中去,由此采用第二种计算方法。第二种计算方法步骤如下:1)对于第k-1轮聚类获得的类,计算该类中所有数据与该类聚类中心的平均距离S2;2)选择类中与聚类种子相似度大于2×S2的数据组成每个类的一个子集;3)计算子集中数据的均值点,作为第k轮聚类的聚类种子。采用这种计算方法,当类中有明显的孤立点的时候,平均距离S2会比较大,但它与类中相似度最小的相似度值相比还有很大差距,这样2倍的平均距离就基本能包括大多数的数据,从而排除孤立点。而当类中数据较集中,没有明显的孤立点时,平均距离S2和类中相似度最小的相似度值之差会比较小,这样2倍的平均距离能包括几乎所有的数据,就在一定程度上解决了采用第一种计算方法带来的由于排除点过多而导致的迭代次数增加等问题,也能获得很好的聚类结果。3tp数据的聚类分析实验采用的数据是二维的数值数据,总共150个数据,数据分为两类,第一类没有明显的孤立点,数据较为集中,第二类相对来说较分散,而且有明显的孤立点。3.1关于聚类数据的聚类聚类进行了四次迭代,分类结果因为孤立点的影响有明显的错误,本该在第二类中的〈4.5,4.5〉,〈4.0,5.0〉,〈4.3,4.7〉和〈4.4,4.8〉这4个数据被分到了第一类中,这是因为受到第二类中的5个明显的孤立点的影响,使第二类的中心点最后明显偏离了数据集中的区域,从而导致了聚类结果出现明显的错误,出错的那4个点离第一类的中心较近,而离第二类的中心较远了。3.2算法的增加和迭代次数改进后的程序纠正了源程序所犯的错误,〈4.5,4.5〉,〈4.0,5.0〉,〈4.3,4.7〉和〈4.4,4.8〉这4个数据分到了正确的类中,但是聚类过程的迭代次数却达到了7次,比原算法增加了3次。这是因为采用(simmax+simmin)/2这个式子排除孤立点是比较粗糙的,当类中有明显的孤立点时,如第二类,很好地排除了6个孤立点,而其他数据都参与到了聚类中心的计算中,但是当类中数据较集中,没有明显的孤立点时,在计算聚类中心时,很多数据都被排除在外了,这就导致了虽然分类的结果在第三次迭代后就没改变,但是聚类中心还在不断地改变,迭代还要不断进行下去,因此就增加了聚类过程的迭代次数。不过聚类中心已经明显地移向了数据集中的区域。聚类的质量和效率都是很重要的,分析第一种改进算法所带来的问题,进一步改进算法。3.3聚类中心的计算方法采用2×S2这个式子,获得了完全正确的聚类结果,并且迭代次数不但没有增加,而且较原算法还减少了一次。这是因为当类中有孤立点时,类中数据与聚类中心距离的最大值和类中数据与聚类中心距离的平均值相差较大,所以用在2倍平均值范围内的数据来计算新一轮的聚类中心时,它能包括大多数的数据并排除掉孤立点,让聚类中心不受孤立点的影响。而当类中数据较集中,没有明显的孤立点时,类中数据与聚类中心距离的最大值和类中数据与聚类中心距离的平均值相差会较小,所以2倍平均值范围内的数据几乎就包括了该类中所有的数据。这样就比较好地解决了原k均值算法和采用第一种计算方法进行改进的k均值算法所产生的问题。实验结果表明,改进后的k均值算法获得了好的聚类结果,