k均值邻近算法

2024-06-21

k均值邻近算法（精选七篇）

k均值邻近算法篇1

数据挖掘中的聚类是一种基本的工具, 集群 (cluster) 是一个数据集分成若干组或类, 使对象之间的相似性也很高, 数据对象之间的相似性, 不同类型的低。聚类是一种无监督学习模型。它起着重要的作用, 在信息检索, 模式识别, 图像处理, 电子商务等领域。信息检索系统, 用户访问信息系统的信息存储, 像某种商品的用户有什么特征, 商场的顾客类别, 可以解决这些问题是聚类分析。在信息检索, 电子商务等领域, 聚类算法可以有效地帮助实现个性化服务和分类检索结果。基于样本数据的聚类方法, 基于主要集中在K均值聚类方法的算法K法和改进的分布式K初始聚类中心的算法, 提高了计算精度和样本聚类分布的均匀性。

2 主要的聚类方法

通过几种聚类分析方法:

(1) 分类方法

对于给定的n个对象或数据线, 分为K个数据集 (部) 。每个子集是一个集群代表 (K≤n) 。也就是说, 数据被划分成k组, 该组必须满足以下要求: (一) 每一组必须至少包含一个对象; (b) 每个对象必须属于一个组。注意有些模糊划分方法的要求可以放宽。

需要所有可能的枚举得到聚类结果的全局优化。对于大多数应用程序使用一个或两种常用的启发式方法 (一) 算法和K聚类对象的聚类, 对应于每个算法; (b) K聚类算法, 聚类算法采用最近的对象。通过这些方法的分析在中小规模的数据集。

为了找出圆形或球形的簇。但对于大数据集或复杂的数据类型的分析算法, 需要扩展。

(2) 分层的方法

数据对象的聚合方法层次分解。根据层次分解形式, 可分为两种自顶向下和自底向上的分层方法。分层的自底向上的方法, 每个对象的一组 (个人) , 逐渐 (对象) 进行了合并, 和最高水平或直到满足终止条件。从所有属于一组自上而下分层的方式, 在每个周期 (集团) 为更小的组, 直到每个对象形成一个小组或满足终止条件。

(3) 基于密度的方法

大多数的分类方法是基于对象的聚类之间的距离。聚类方法只能检测聚类的圆形或球形, 发现任意形状的更难。“基于簇的概念, 实际上是增加相邻” (数据对象或点) 密度超过一定的阈值 (如聚类, 或一个给定的半径必须包含至少一个点) 。

(4) 基于网格的方法

基于数量有限的空间网格结构的组件对象的方法。以空间桁架结构聚类操作的所有的人。这种方法的主要优点是由于在数量和网格和物体空间相关的数据处理时间是独立的对象的数量, 这是比较高的。

(5) 基于模型的方法

基于该模型, 为每个群集的假设模型, 并发现每个数据对象模型。数据模型, 找到最合适的一个给定的。

3 k-means算法的一般过程

定义1:定义5.1数据对象X= (x1, x2, …, xp) 和Y= (y1, y2, …, yp) ) 之间的距离为:

k-means算法的一般过程如下:

算法输入:聚类个数k, 以及包含n个数据对象的数据样本集;

算法输出:满足方差最小标准的k个聚类:

该算法的步骤:

(1) 从任何一个数据对象的k个对象初始聚类中心:

(2) 环 (3) 至 (4) , 直到每个群集将不改变;

(3) 根据每个簇中的所有对象 (中心) , 一个样品的浓度和从对象的中心的距离计算每个对象的图像, 并根据相应的分类之间的最小距离;

(4) (变化) 的平均计算每个簇 (中心) 。

这是K的一般过程均值算法, 是一个迭代的过程。的参数k的值是预先给定的, 唯一的因素, 对初始聚类中心的聚类结果的影响。一些研究表明, K均值算法容易陷入局部最优, 不同的初始聚类中心的聚类结果, 将一些学者最后, 实验也证实了这一点。从这些局部优化, 聚类结果, 找到一个更好的是一个值得研究的问题。因此, 以下是从初始聚类中心的思想和基于分布式数据对象的改进算法。

4 基于数据样本分布选取初始聚类中心的方法

在K均值算法的初始聚类中心的选择, 可以使不同的聚类结果与不同的精度。如果对象之间的距离的相似性的相似程度, 对象之间的距离小于物体之间的距离是不一样的。在空间分布上的类似数据, 发现数据的一致性, 采取以下步骤:二二计算数据对象之间的距离;找出一组两个对象的数据, 最近, 在A1的数据对象组成的, 他们是从总的数据集和删除;每个样本计算对象A1数据你的每一个数据对象和定距, 确定你在最近的A1的数据对象, 将成为一个集A1和远离你, 数据对象的数量直至A1达到一定阈值;然后发现有两个和二二个样品的数据对象之间的距离, 将重复此过程直到K对象, 最终形成的集合, 一个对象:K的算术平均值, 对初始聚类中心的形成。

改进算法描述如下:

算法2:改进的k-means算法 (基于数据样本分布选取初始聚类中心的方法)

算法输入:聚类个数k, 包含n个数据对象的数据样本集;

算法输出:满足方差最小标准的k个聚类;

算法步骤:

(1) 的任何两个数据对象之间的距离D (X, Y, 根据公式) , 最近发现, U盘从两个数据对象, 形成一组 (1

(2) 找到最近的距离数据对象设置 (公式3.1) , 将其添加到集合点, 并从您的收藏中删除对象;

(3) 数据对象, 如重复频率大于或等于指定的阈值。

(4) 如果M

(5) K的数据集将最终形成的算术平均值, K初始聚类中心的形成; (6) :从初始聚类中心点的K, K均值算法形成最终聚类中的应用。

5 对算法2的改进

算法2中在形成数据对象Am (1

定义2:一个数据对象X与一个数据对象集合V之间的距离, 定义为这个数据对象与这个数据对象集合中所有数据对象的距离的平均值, 即:

其中: 是利用公式3.1计算X到数据对象集合V中的Y的距离, m为集合V中的数据对象个数。

算法2改进后的具体步骤如下:

使用两个数据对象数据对象3.1公式二二的距离;距离最近发现, 形成在A1的一组数据对象, 他们将你从总的数据;A1每个样品在每个数据对象和数据对象计算在美国的距离来找到你, 由对象式5.1A1数据最近, 将成为一个集A1和远离你, 数据对象的数量直至A1达到一定阈值;然后离你最近的A2二二二数据对象和样本之间的距离, 并重复该过程, 直到K组, 对象的形式:在对象的k集合的末尾是算术平均值, 形成初始聚类中心。

改进后的算法描述如下:

算法3:

算法的输入:聚类数k, n包含一个数据对象的数据集;

输出:K聚类算法满足最小方差准则;

该算法的步骤:

(1) 的任何两个数据对象之间的距离D (X, Y, 根据公式) , 最近发现, U盘从两个数据对象, 形成一组 (1

(2) :找到最近的距离数据对象设置 (公式5.1) , 将其添加到集合点, 并从您的收藏中删除对象;

(3) :数据对象, 如重复频率大于或等于指定的阈值。

(4) :如果M

(5) :K的数据集将最终形成的算术平均值, K初始聚类中心的形成; (6) :从初始聚类中心点的K, K均值算法形成最终聚类中的应用。

6 实验

实验数据:选自本校电子图书馆中的数据HUH和自己收集的Web用户数据集YHU

实验结果:改进算法与随机选取初始聚类中心方法的比较如下表所示。

从表中可以看出, 随机选取初始聚类中心的方法从不同的初始中心出发会得到不同的聚类结果, 聚类准确率有很大的差别, 很不稳定, 难以确定其是否可用。改进后的算法2算法3都能够得到较高且稳定的准确率。算法3和算法2相比准确率稍高, 但相差不多, 这也和理论结果相符。改进后的算法首先根据启发式算法来寻找数据, 因而产生的初始聚类中心比较符合数据实际分布, 也就更适用于对实际数据的聚类。

7 小结

由于数据挖掘的应用越来越广泛, 数据挖掘聚类的基本方法已被广大学者的关注。在本文中, K均值聚类方法, 并分析了其缺点, K均值算法, 提出了一种改进算法, 该改进算法具有更高的精度和更好的均匀性分析实验表明。

参考文献

[1]邓爱林, 朱扬勇, 施白乐.基于项目预测评分的协同过滤推荐算法[J].软件学报, 2002, 13 (4) :1一8.

[2]Tomoharu I, Kazumi S, Takeshi Y.Modeling user behavior in recommender systems based on maximum entropy//Proeeedings of the 16th International Conference on World Wide Web.Banff, Alberta, Canada, 2007:1281-1282

[3]SARWAR B M, KARYPIS G, KONSTAN J A, et al.Analysis of recommendation algorithms for ecommerce[A].Proceedings of the ACM EC’00 Conference[C].Minneapolis, MN., 2000.158-167.

[4]纪良浩, 王国胤.基于资源的协作过滤推荐算法研究[J].计算机工程与应用, 2008, 44 (8) :1981-1985.

[5]A.Kurniawan, N.Benech, Tao Yufei.Towards High-dimensional Clustering[J].COMP, November 1999, 1-2.

改进的二分K均值聚类算法篇2

随着大数据及云计算浪潮的推动,数据挖掘在信息产业领域显得越来越重要。人们急于想从大量数据中抽取有用信息,进而帮助决策者预测未来可能发生的行为。数据挖掘从数据集合中自动抽取隐藏在数据中的那些有用信息的非平凡过程[1],聚类是数据挖掘中最重要的技术之一[2]。聚类分析仅根据在技术中发现的描述对象及其关系的信息,将数据对象划分成簇,常见的簇类型有: 明显分离型、基于原型、基于图、基于密度和概念簇等[3]。

K均值是一种基于原型的聚类技术,在众多聚类方法中,K均值算法也是最经典的,应用最广泛的聚类方法[4]。K均值用质心定义原型,其中质心是一组点的均值,通常K均值聚类用于n维连续对象[5~7]。K均值聚类以各样本的质心为代表不断迭代,可用于许多类型的数据,如文档和时间序列等[8]。

二分K均值聚类算法是对基本的K均值算法的一个扩充,为了得到K个簇,他将所有点分成两个簇,从这些簇中选取一个继续分裂,直到产生K个簇[9,10]。

但二分K均值算法和经典的K均值算法一样,在聚类前随机选择K个初始质心( 即K个聚类中心) ,最后得到聚类的结果往往受到聚类个数的影响,最后得到的簇的质量往往很差。并且,二分K均值算法可能会产生分簇过细的问题。

1 相关研究

近年来,对K均值聚类算法改进也有一些研究但对二分K均值算法的改进却很少。文献[5]用K均值聚类算法和二分K均值算法对文档聚类,结果表明二分K均值聚类算法效果高于K均值聚类算法; 文献[6]提出了内核K均值算法,并进行整合,高效地减少了非线性支持向量机的训练样本,在保持较高的测试精度的同时大大减少了采样时间复杂度; 文献[7]采用数据并行的思想和均匀划分的策略,对算法进行并行化处理; 文献[8]将二分K均值聚类和SVM决策树结合在一起,提出一种可适用于高维数据聚类的自适应方法,在保证分类精度的前提下,减少了分类时间。文献[9]就效率、效果及可扩展性三个方面全面地比较了三层次方法( 单链,全链,平均组) ,二分K均值,K均值,和后缀树聚类,并通过实验证明,二分K均值算法通常优于其他聚类算法,需要最小的时间复杂度; 文献[10]通过实验证明二分K均值算法的计算效率比顺序执行多次K均值算法的更高。

以上文件均说明二分K均值算法的有效且时间复杂度相对较低,本文结合层次结构,对二分K均值聚类过程进行了改进,使其能够自动的选择聚类个数,并结合Chameleon算法,使用接近性和互连性概念及簇的局部建模来合并一些划分过细的簇。

2 二分 K 均值聚类算法

设X = { x1,x2,…xi,…,xn} 为n个Rd空间的数据,在开始聚类前,指定K为聚类个数。为了得到K个簇,将所有点的集合分裂成两个簇,放到簇表S中。从簇表中选取一个簇Ci,用基本的K均值聚类算法对选定的簇Ci进行二分聚类。从二分实验中选择具有最小总SSE得两个簇,将这两个簇添加到簇表S中,更新簇表。如此下去,直到产生K个簇。在二分K均值算法中,使用结果簇的质心作为基本K均值的初始质心。使用误差平方和SSE作为度量聚类质量的目标函数,也称SSE为散度。对于多次运行K均值产生的簇集,选择误差平方和最小的那个,使得聚类的质心可以更好地代表簇中的点。其中SSE的定义如式( 1) 。其中ci为簇Ci的聚类中心,x为该簇中的一个样本。

二分K均值算法受初始化问题的影响较小,因为它执行了多次二分试验并选择具有最小SSE的试验结果,且每步只有两个质心。但仍然受用户指定聚类个数K的影响。

3 改进的二分 K 均值算法

3. 1 算法的初步改进

二分K均值算法比K均值算法更有效,但需要采用多次K均值聚类的方法进行聚类,选择具有最小SSE的簇集作为二分聚类结果,大大增加了时间复杂度。针对这一问题,本文结合二分K均值二分的特点,对二分K均值算法进行了改进,不需要指定聚类个数,只进行一次二分聚类就动态的获取具有最小SSE的簇集,从而取得优秀的聚类结果。

具体过程如下:

首先假设簇Ci中的样本为{ xi1,xi2,…,xin} ,ci为其类中心。定义一个标准聚类测度函数,其形式为:

步骤1选择包含n个数据对象的样本集X = { x1,x2,…,xi,…,xn} 。迭代次数t初始化为1,为了确保能进行二次划分簇,J的初始值置为0. 01。在数据样本集中随机选择一个初始聚类中心,将该聚类中心加入到簇表中。

步骤2在簇表中选定一个SSE最大的簇,在该簇中找出与该簇中心最远的一个样本xi,及与样本xi最远的样本xj。以这两个点作为新的初始聚类中心,将该簇中的所有点指派到最近的初始质心,重新计算所得两个新簇的聚类中心。得到两个新的聚类中心X1、X2。

步骤3将新的聚类中心加入到簇表中,删除被分裂的聚类中心。并将迭代次数加1。并计算当前聚类测度函数值Jt。

改进的算法流程图如图1所示。

3. 2 算法的优化

上文通过对二分K均值算法进行了改进,能够设定ε的值自动地选择聚类个数,但仍然可能存在一些不合理的簇。如图2所示,很明显,图中左边四个簇应该合并成一个簇。

本文结合Chameleon算法对改进的二分K均值算法进行改进,力求合并这样一对簇,合并后产生的簇,用接近性和相似性度量,与原来的一对簇最相似。

相对接近度的数学表达式为:

其中,mi和mj分别是簇Ci和Cj的大小; SEC( Ci,Cj) 是连接簇C和Cj的( K-最近邻图的) 边的平均权值; SEC( Ci) 是二分簇Ci的边的平均权值; SEC( Cj) 是二分簇Cj的边的平均权值; EC表示割边。

相对互连度是被簇的内部互连度规范化的两个簇的绝对互连度。如果结果簇中的点之间的连接几乎与原来的每个簇一样强,两个簇合并。其数学表达式为:

EC( Cj,Ci) 是连接簇Ci和Cj( K-最近邻图的) 的边之和;EC( Ci) 是二分簇Ci的割边的最小和; EC( Cj) 是而分簇Cj的割边的最小和。

设R表示两个簇之间的相似度,R = RI( Ci,Cj) ×RC( Ci,Cj)α,α是用户指定的参数,通常大于1。

改进步骤如下:

步骤1将改进的二分K均值算法的聚类结果中的每个簇看成是一个对象,计算最近两个簇之间的相似度,得到簇间的相似度矩阵;

步骤2基于得到的相似度矩阵构造K-最近邻图( 即两个的边之和) ;

步骤3使用多层图划分算法划分K-最近邻图;

步骤4合并对于相似度而言,具有最大的值的簇;

步骤5重复步骤4,直至不能合并为止,得到N0个簇。改进流程如图3所示。

4 实验结果及分析

为了检验改进后的二分K均值聚类算法中聚类个数选择效果,本文将改进后的算法与基于随机选择聚类个数的二分K均值算法的有效性进行比较,本文在三个标准数据集( 如表1所示) 上进行了实验,并与传统的随机选择初始聚类中心的K-means方法做了比较,实验数据可在UCI数据集网站上下载,其中ASL( Australian sign Language sings) 是澳大利亚手语数据集,Banana是一种香蕉型标准数据集,Breast Cancer是乳腺癌数据集。实验在1台PC机( 2. 0 GHz CPU,1 GB内存) 上进行测试,实验平台是Matlab 7. 8。

图4给出了以上三个数据集在不同的聚类个数下,传统K均值聚类算法得到的聚类结果所计算的聚类测度值的变化示意图。

由图4可以看出,二分K均值算法,在数据集ALS、Banana、Breast_cancer聚类个数分别达到30、20、25后,聚类测度函数值的减小变得比较平缓,因此对于上面三种数据集来说,聚类个数分别为30、20、25。采用本文改进的方法可以自动地获取聚类个数,不受初始质心选择的影响,最终在三个数据集上得到的聚类个数分别为27、22、23,与传统K均值算法多次实验结果比较得到的最优聚类个数是一致的。改进算法聚类个数与设定的ε的值有关,当聚类测度差值在给定范围内时,聚类效果较好。由于算法优化中将一些划分不合理的簇合并了,所以用改进后的的算法所得的聚类个数要比用二分K均值算法得到的聚类个数少。

实验采用了抱团性和分离性[4]来衡量这两种算法的有效性。抱团性是指聚类结果中任意最远的两个点的距离的最大值; 分离性是指任意两个聚类中心的距离中的最小值。设K是聚类后得到的最优聚类个数。

抱团性:

分离性:

由表2可以看出本文提出的方法与传统的二分K均值聚类算法相比,三个数据集的抱团性略小于传统K均值算法,分离性略大于二分K均值算法。由于文中用了Chameleon算法对初步改进后的结果进行了优化,所以改进后的算法在抱团性和分离性上都优于二分K均值算法。因此本文提出的改进方法聚类效果更好。

传统二分K均值聚类算法的时间复杂度为Ο( n·K·d·T) ,其中,n为数据点个数,K为聚类个数,d为数据属性个数,T为迭代次数。在改进的算法中,算法初步改进后时间复杂度为Ο( nlogn) ,算法优化时间复杂度为Ο( K2) ,由于K < n,对于大规模的数据集通常有K <槡n,算法优化时间复杂度低于初步改进的时间复杂度,整个算法的时间复杂度主要由初步改进的时间复杂度决定。所以改进后的算法时间复杂比二分K均值算法时间复杂度低。文献[6]中时间复杂度为O( τ2n) 其中τ为为最大簇的阈值,文献中设定τ = 2槡n,因此其时间复杂度为O( 4n2) 。由此可看出改进后的算法时间复杂度低于文献[6]。

5 结语

K均值聚类算法是一种常用的聚类算法。二分K均值是K均值聚类算法的变种,比K均值算法的计算效率更高。本文针对二分K均值算法中需要随机选取聚类个数而导致的结果不理想,以及分类结果出现的不合理问题,利用层次结构及Chameleon算法对二分K均值聚类算法进行改进,该方法不需要定义初始聚类个数,自动得到最佳聚类个数,并且能够自动合并划分过细的簇。仿真实验证明,改进算法的抱团性和分离性优于二分K均值算法。

摘要：K均值算法是一种常用的基于原型的聚类算法。但该算法要求用户随机选择初始质心,使得K均值算法受初始化影响较大。二分K均值算法虽然改善了这个问题,但仍然要求用户指定聚类个数,影响了聚类效果。用层次聚类对二分法进行改进,解决了二分K均值算法受用户指定的聚类个数的影响的问题。并结合Chameleon算法,合并划分过细簇,优化聚类结果。仿真实验证明改进的聚类算法的抱团性和分离性优于二分K均值聚类算法。

k均值邻近算法篇3

关键词：二分K均值,优化,并行,Hadoop,加速比

0 引言

聚类是将对象集合按照有关特性进行分组的过程, 聚类划分的每一组数据称为类或簇。聚类的目的是使簇中的对象相似, 簇之间的对象差异尽可能的大。常见的簇类型有:明显分离的簇、基于原型的簇、基于密度的簇、基于图的簇以及基于概念的簇等。K均值算法是一种基于原型的聚类技术, 具有快速、简单的优点, 可以处理大规模数据, 在诸多领域得到了广泛的应用。它的缺点是很容易受聚类算法的初始化条件影响, 如簇的个数、初始聚类质心点的位置等。二分K均值是K均值算法的变种, 与K均值相比, 它的优点是不受初始聚类质心选择的影响。但是传统的二分K均值方法在二分过程中采用随机选择的方法选择初始质心, 大大影响了算法的运行速度。因此, 本文对二分K均值算法进行了改进, 在二分初始点的选择过程中, 采用一次选择极大值点来作为初始质心, 提高算法的运行速度。当数据集中存在离群点时, 该算法在选择极大值点时往往会选择到离群点, 这将大大影响聚类的准确率, 因而本文在选择极大值点时采用点抽样的方法, 从而避免将离群点作为极大值点, 以提高算法的准确性。

当聚类处理的对象是高维或海量的数据时, 单机的串行方法很难对其进行处理, 解决的方法是采用并行计算的思想, 将数据分布到不同的计算节点进行计算, 这些计算节点组成了一个分布式集群。本文采用Hadoop分布式框架搭建分布式集群, 设计基于Map/Reduce模式的并行计算方法, 以解决海量数据的计算问题。

1 相关研究

文献[1]将二分K均值算法与K均值算法分别对文档进行聚类, 结果显示二分K均值算法效果优于K均值算法。文献[2]提出了核二分K均值算法, 有效地减少了SVM的训练样本, 在保持了测试精度的同时缩短了训练时间。文献[3]对二分K均值算法进行并行化处理, 结果表明, 在面对海量数据时并行算法的时间复杂度要低于串行算法。文献[4]将SVM决策树和二分K均值算法结合起来, 提出一种可适用于高维数据的聚类方法, 在保证分类准确率的前提下, 有效的降低了分类时间。文献[5]比较了二分K均值、K均值以及后缀树聚类这三种算法, 结果表明, 二分K均值算法通常优于其他聚类算法。文献[6]通过实验表明二分K均值算法比多次顺序执行K均值算法的效率要高。

2 二分K均值聚类算法

二分K均值算法的主要思想是:首先将所有点作为一个簇S, 将簇S放入簇集C中。然后循环的从簇集C中找出误差平方和SSE最小的簇, 采用基本的K均值算法, 对该簇进行二分聚类, 这个过程重复N次[7]。选择其中使得总SSE最小的两个簇作为最终的划分结果, 将这两个簇加入簇集C中。如此往复, 直到簇的个数达到K为止。其中, SSE的定义如下:

二分K均值算法受初始化问题的影响较小, 在二分时, 使用多次K均值算法找到使SSE最小的聚类结果, 但这是局部最优, 不是全局最优。为了使全局最优, 可以在最后使用结果质心作为K均值的初始质心, 进行全局优化。

3 优化的二分K均值聚类算法

从上述二分K均值算法可以看到, 在二分时, 质心是随机选取的。因此, 为了保证聚类的效果, 算法通过重复多次二分K均值聚类, 把使得总SSE最小的簇集作为结果簇[8]。虽然这种做法保证了一定的准确度, 但是却大大提高了算法的时间复杂度, 尤其是在面对海量、高维数据时。本文针对这种情况, 对算法进行改进, 只需要一次二分聚类就可以找到具有最小SSE的簇集。具体的改进算法如下:

输入:数据集S, 簇的数目K。

输出:簇集C{S1, S2, ……Sk}。

初始化:C={S}。

步骤一:从簇集C中选择SSE最大的簇V。

步骤二:在簇V中随机选择一个数据点, 找到与该数据点距离最远的点x1, 再找到与x1距离最远的点x2。

步骤三:把x1、x2作为聚类质心, 对簇V进行二分聚类, 得到簇V1、V2, 将V1、V2加入簇集C中, 同时计算V1、V2的簇质心。

重复以上三个步骤, 直到簇集中包含K个簇。

以上算法就是改进后的二分K均值算法, 这个改进算法虽然大大降低了时间复杂度, 但是在步骤二中, 由于取的是距离最大值点, 而离群点距离数据集中其他点相对较远, 从而很有可能取到离群点, 这将大大影响算法的准确性。因此, 本文对算法做进一步的改进。

在步骤二中, 采用点抽样的方法从簇V中随机抽取一些数据点形成数据集C1, 在C1中随机选择一个数据点, 然后在C1中找到与该数据点距离最远的点x1和与x1距离最远的点x2, 步骤一和步骤三不作修改。由于离群点相对于整个数据集来说只是极少数, 所以在点抽样时不太容易被选中, 因此可以避免选择离群点作为二分时的质心, 提高了算法的准确性和健壮性。图一所示为算法的处理流程图。

4 基于Ma p/Re duce模型的二分K均值算法

4.1 并行计算思想

二分K均值算法的主要思想是将数据集不断的进行二分, 最终得到簇集, 每次二分过程采用的是基本的K均值算法。这个算法可以交给不同的机器去独立的完成, 从而实现并行计算。但是二分K均值算法是要对全局数据进行计算才能得到准确结果 (质心) , 而将数据分布到各个节点后, 我们需要将所有节点计算后的质心汇总, 然后得到全局的质心, 再将其发送到各个节点, 重新计算。

4.2 Map Reduce编程模型

Map Reduce是一种编程模型, 用于大规模数据集的并行运算[9]。它的编程思想是将数据处理过程抽象成Map和Reduce两个过程。在Map阶段, Map Reduce框架将输入数据分解成一组<K, V>键值对作为输入, 通过计算得到中间结果, 中间结果也是一组键值对。在Reduce阶段, 获取Map阶段得到的中间结果, 对结果进行统计[10]。

4.3 二分K均值算法的Map Reduce实现

根据并行化的思想, 我们可以把数据分成若干部分, 每一部分的计算在Hadoop分布式框架中并行执行, 最后, 对各个节点的结果进行汇总, 得到最终的结果。把整个执行过程分为两个阶段, 具体内容如下:

阶段一:在Map阶段, 各个节点上分别独立的进行二分K均值的计算, 分别得到K个聚类质心, 接着进入Reduce阶段, 对各个节点得到的K个聚类质心进行K均值计算, 最终得到K个聚类质心, 即作为全局聚类质心, 输出到HDFS中, 进入第二个阶段。

阶段二:各个节点获取HDFS上的全局聚类质心, 进入Map阶段, 在各个节点上, 对数据集中的每条数据, 找到离它最近的聚类质心, 形成键值对<聚类质心标号, 数据>, 输出每一条键值对至HDFS中。图二所示为并行算法的处理流程图。

具体设计如下:

阶段一:

(1) Map函数的设计

Map函数从文本中获得数据, 数据输入的格式为<key, value>, 其中, key为输入数据的偏移量;value为当前样本的各维坐标值组成的向量。对数据集进行传统二分K均值的计算。得到K个聚类质心, 之后输出<1, value’>, 其中value’是该聚类质心的向量。

(2) Reduce函数的设计

Reduce函数的输入数据为<1, value’>对, 即Map函数的输出。从value中解析出各个向量, 对这些向量进行K均值的聚类操作, 最终得到K个聚类质心, 即全局聚类质心。输出为<key”, value”>。其中key”是聚类质心的标号, value”是聚类质心的值。最后, 将输出数据保存到文本中, 以用于下一个作业。

阶段二:

(1) Map函数的设计

Map函数的输入有两类, 一是上一个作业的输出, 即全局聚类质心;二是存储在该节点上的数据。计算每一个点到各个聚类质心点的距离, 选择最小距离的聚类质心 (簇质心) 作为该点所属的簇, 输出<key, value>, 其中key是聚类质心 (簇) 的标号, value是表示该点的数据, 输出结果保存在HDFS中。

5 实验结果与分析

5.1 二分K均值的优化实验

为了检验改进后二分K均值的效果, 将改进后二分K均值的效果与原二分K均值的效果进行比较, 实验采用人工数据, 构造4组数据, 大小分别为1.5M、3M、6M、12M。实验在一台PC机 (2.0 GHZ CPU, 1 GB内存) 上进行。为了使实验结果更加可靠, 对每一组实验重复20次, 取其平均值作为最终结果。

表一给出了四组数据集分别在两种二分K均值算法 (改进前和改进后) 下的运行时间, 而图三给出了其时间趋势曲线。通过观察可以看出, 对于任何一组数据, 改进后算法的运行时间明显小于改进前, 且随着数据量的增加, 两种算法运行时间的差值也在增加。因此得出以下结论: (1) 改进后算法节省更多时间, 提高了算法的效率。 (2) 随着数据量的增加, 算法在节省时间方面的效果更加明显。 (3) 随着数据量的增加, 算法的运行时间基本呈线性增长, 说明算法具有好的扩展性。

5.2 Hadoop集群的并行实验

在该实验中将检测并行算法的运行时间及加速比。实验采用人工数据, 构造大小为130M数据, 实验在搭建的Hadoop平台下进行, 平台由多台PC机 (2.0 GHZ CPU, 1 GB内存) 组成。加速比是检验并行算法性能的一个重要指标, 为了得到加速比, 实验测试了算法在不同节点下的运行时间。实验结果如表二所示。

表二给出了数据集在不同节点下的运行时间, 图四给出了算法的运行时间曲线。可以看出, 随着节点个数的逐渐增加, 算法的运行时间在逐渐减少。当节点数从1变为2, 曲线的下降坡度最大, 加速比大于节点数;随着节点数的增加, 曲线下降坡度逐渐变小, 加速比小于节点数。出现这种情况的原因是, 随着节点个数的增加, 节点之间的通信时间也在增加, 导致节点的加速比小于节点个数。但总体来说, 该算法在Hadooop平台下具有良好的加速比。

6 结束语

在传统的二分K均值算法的二分过程中, 选择出理想的初始质心时间较长, 本文对初始质心的选择方法进行改进, 降低其质心的选择时间, 从而大大降低了算法整体的运行时间。同时为应对大数据时代带来的海量数据的计算问题, 本文在Hadoop平台下对算法进行了并行化设计。实验结果表明, 改进的算法具有更高的时间效率, 并行算法具备可行性且有良好的加速比。由于在Hadoop平台下, 节点I/O处理时间、节点之间的通信影响了并行算法整体的性能, 因此如何进一步提高并行算法的效率将是今后要研究的问题。

参考文献

[1]Krishna B S Vamsi, P Satheesh, Suneel Kumar R.Comparative Study of K-means and Bisecting K-means Techniques in Wordnet Based Document Clustering[J].International Journal of Engineering and Advanced Technology (IJEAT) , 2012, 1 (06) :229-234.

[2]Liu Xiaozhang, Feng Guocan.Kernel bisecting k-means clustering for SVM training sample reduction[A].International Conference on Pattern Recognitio[C].2008.

[3]张军伟, 王念滨, 黄少滨, 等.二分K均值聚类算法优化及并行化研究[J].计算机工程, 2011, 37 (17) :23-25.

[4]裘国永, 张娇.基于二分K-均值的SVM决策树自适应分类方法[J].计算机应用研究, 2012, 29 (10) :3685-3687.

[5]Yoo IIIhoi, Hu Xiao Hua.A comprehensive comparison study of document clustering for a biomedical digital library MEDLINE[C].Proceedings of the 6th ACM/IEEE-CS Joint Conference on Digital Libraries (JCDL`06) , 2006.

[6]Silva J D A, Hruschka E R.Extending k-Means-Based Algorithms for Evolving Data Streams with Variable Number of Clusters[A].International Conference on Machine Learning and Applications and Workshops[C].2011.

[7]胡伟.改进的层次K均值聚类算法[J].计算机工程与应用, 2013, 49 (02) :157-159.

[8]张春凯, 王丽君.基于遗传算法的一种改进的K-均值聚类算法[J].计算机工程与应用, 2012, 48 (26) :144-147.

[9]Zhou Ping, Lei Jingsheng, Ye Wenjun.Large-scale data sets clustering based on Map Reduce and hadoop[J].Journal of Computational Information Systems, 2011, 7 (16) :5956-5963.

K均值算法影响因素的可视化分析篇4

本文研究建立在前期完成的可视化软件基础上, 该软件基于平行坐标法思想, 平行坐标法是一种基于几何的可视化方法, 该理论最早由法国数学家Ocane在1885年提出[4], 平行坐标法将n维数据空间中的一个点表示成二维平面中的一条折线, 无限个相互独立的变量表示在一个图形中, 可获得给定问题的独特、简洁表达[5]。

1 K均值算法的基本原理

算法输入:具有m个数据点的n维数据集E;聚类的个数k;

算法输出:满足方差最小标准的k个聚类;

算法流程:

(1) 从数据集E中任意挑选k个数据点作为初始聚类中心;

(2) 计算数据集E中每个数据到各聚类中心的距离;并找出各数据与哪一聚类中心距离最小, 将其归入以此聚类中心为簇中心的聚簇中;

(3) 重新计算k个聚类中心, 聚类中心的值为各簇中所有数据点的算术平均值;

(4) 依据公式 (1) 计算平方误差e;

(5) 对比前后两次计算中得到的平方误差值, 若满足|et+1-et|≤ε, 则聚类过程结束, 若不满足, 则返回重复步骤 (2) 、步骤 (3) 、步骤 (4) , ε为一个常数, 编程中, 用户可依据自己对精度的需求自行设定。

公式 (1)

其中b为各个聚簇中的数据;ai为聚类Ci的平均值。

2 基于平行坐标法的可视化软件

基于平行坐标法的可视化软件是前期的研究成果, 该软件在MATLAB中实现, 集成了颜色比例法、视图缩放、坐标轴交换、聚簇分类着色等可视化技术。软件基本实现了K均值算法数据挖掘过程的可视化, 并在同类可视化软件基础上有所改进, 增加了两个中间因素的可视化:聚类中心和收敛函数值, 聚类中心可视化将数据挖掘过程中聚类中心的变化趋势进行了反映, 而收敛函数值的可视化能够反映聚类过程算法迭代运行的次数和收敛函数的收敛速度, 增强了可视化效果, 图1为软件的效果图。

3 影响因素的可视化分析

3.1 数据集描述和分析方案制定

实验选取IRIS数据集作为测试数据集, 选取该数据是基于两个方面的考虑:一方面, IRIS数据集作为一个标准测试数据集, 具有丰富的前期研究成果, 特定条件下的最优聚类方案已如科学定理一般, 在本领域得到普遍认同, 公认的最优聚类方案相当于为聚类结果的评价提供了一种成熟评价方法——外部准则, 减少了聚类结果评价的复杂性, 增强说服力;另一方面, K均值算法适于处理连续型数据, IRIS数据集正好与这一要求相符合。

IRIS数据集又称鸢尾花特征数据集, 该数据集可从UCI (University of California Irvine) 的机器学习数据库中获得。IRIS数据集总共包含150个数据点, 是对Setosa、Versicolour、Virginca三种鸢尾花在既定的属性上各采集50个数据点而得到, 该数据集可用表1中所列举的五个属性进行描述。

具体分析方案:在多个影响因素中, 一次仅对其中一个进行分析, 其它因素保持不变, 完成K均值算法的聚类过程后, 通过对最终聚类结果可视化图形、文本形式的聚类结果以及收敛准则变化趋势图的对比, 完成对该影响因素的分析。

3.2 数据预处理因素的可视化分析

数据预处理的目的在于去除噪声、查漏补缺、剔除冗余、转换数据类型等, 它能够改善数据质量、提高挖掘精度, 能够改善最终聚类结果。根据文献[6]所做研究, IRIS数据集需进行中心化、标准化变换, 中心化保证数据集各属性的值具有相同基点, 变换之后各属性的均值为零;标准化保证各属性的变化范围相同。

(1) 实验初始条件

聚类个数为3;

初始聚类中为数据集的第1、2、3行数据;

算法结束条件|et+1-et|≤ε, 其中ε=0;

聚簇颜色方案:‘R’、‘G’、‘B’三色。

(2) 实验结果

基于上述初始条件设置, 利用可视化软件对IRIS数据集进行两次聚类, 两次聚类仅有一点不同:第一次聚类不涉及数据集的预处理, 第二次聚类前则进行数据的预处理, 将两次运算得到的聚类结果可视化图形和平方误差变化趋势图进行对比展示, 如图2、3、4、5所示。

(3) 结果分析

图2、图3中, 红、绿、蓝三色分别代表聚类结果中的三个聚簇, 对比两个图形可以看出, 图2中, 在最右侧的属性轴区间中, 红、绿两种颜色所表示的两个聚簇存在交叉, 借助软件信息列表所反映的信息可知:未经过数据预处理的这次运算, 虽然每个聚簇中都包含50个数据点, 但本应归为第二类 (图2中的绿色区域) 的编号为78的数据点, 却归入了第一类 (图2中的红色区域) ;编号为107的数据点, 本应归为第一类, 却归入了第二类, 表现在图2中即为红、绿两种颜色聚簇的交叉。而图3中不存在这种情况, 三个聚簇很好地区分开来, 和IRIS数据集现存的最优聚簇方案相吻合。

图4、图5为算法收敛准则函数值的变化趋势图, 该图形反映了算法的迭代次数和算法的收敛速度, 通过两幅图形的对比可以看出:未经数据预处理所进行的运算, 算法收敛前需进行8次迭代 (迭代次数为曲线上的点个数) , 而经过数据预处理之后, 算法的运行次数明显减少, 仅需6次迭代, 算法迭代次数是算法运行速度的直观反映, 数据预处理之后所进行的运算, 算法运行速度加快。

(4) 总结

通过上述分析, 可以得出结论:数据预处理能够明显提高K均值算法的挖掘精度, 改善K均值算法的挖掘效果, 而且在一定程度上能够提高算法的挖掘速度, 结论与现有理论相吻合。

3.3 初始聚类中心因素的可视化分析

K均值算法, 运行之前需给定初始条件, 如聚类个数、初始聚类中心等, 本次实验针对初始聚类中心这一因素进行。对于K均值算法, 不同的初始聚类中心会产生不同的聚类结果, 甚至会出现错误的结果。

(1) 实验初始条件

聚类个数为3;

算法结束条件|et+1-et|≤ε, 其中ε=0;

聚簇颜色方案:‘R’、‘G’、‘B’三色;

数据集在算法运行之前进行规范化预处理。

(2) 实验结果

基于给定的实验条件, 通过多次改变初始聚类中心的选择, 试验中, 从数据集中任意选取三行数据作为初始聚类中心, 这样即可得到多个不同聚类结果, 将不同聚类结果的可视化图形进行对比, 如图6、7、8所示。

(3) 结果分析

图6、7、8为三种不同的初始聚类中心方案下, 算法最终运算结果的可视化图形, 通过图形之间的对比可以看出, 图6、图8两种情况下, K均值算法能够利用给定的初始聚类中心得到正确、合理、与既定最优聚类相符合的聚类结果;而图7所示的这种情况, 由于初始聚类中心设置不当, 导致局部最小值的出现, 最终运算结果是不合理、错误的。

(4) 总结

通过对图6、7、8三幅图形的对比分析, 可以看出, 对于K均值算法, 初始聚类中心的选择至关重要, 不同的初始聚类中心会得到不同的聚类结果, 更有甚者, 初始聚类中心选择不当导致错误运算结果出现, 验证了现存理论的正确性。

4 结论

本文借助平行坐标可视化软件和IRIS数据集, 对影响K均值算法挖掘效果的其中两个因素———数据预处理、初始聚类中心的选择进行了可视化分析。可视化分析方案, 直观、简洁, 将晦涩难懂的理论以一种全新的方式进行阐释, 使初涉新领域的研究人员能够更好、更快地理解本领域知识。可视化分析方案, 丰富了科学理论的表述方式, 同时, 该实验的成功对于其它成熟理论的验证和阐释也具有一定指导意义。

参考文献

[1]熊忠阳, 陈若田, 张玉芳.一种有效的K-means聚类中心初始化方法[J].计算机应用研究, 2011, 28 (11) :4188-4190.

[2]张文明, 吴江, 袁小蛟.基于密度和最近邻的K-means文本聚类算法[J].计算机应用, 2010, 30 (7) :933-1934.

[3]周爱武, 于亚飞.K-Means聚类算法的研究[J].计算机技术与发展, 2011, 21 (2) :62-65.

[4]徐永红, 高直, 金海龙, 等.平行坐标原理与研究现状综述[J].燕山大学学报, 2008, 32 (5) :389-392.

[5]Fiorini P, Inselberg.A Configuration Space Representationin Parallel Coordinates[C].International Conference on-Robotics and Automation, CA, USA:Jet Propulsion Lab, 1989.

k均值邻近算法篇5

关键词：半监督聚类,改进的K均值算法,质心优化,粒子群算法,动态管理种群

0 引言

半监督聚类是近几年提出的一种新型聚类方法, 它综合了无监督学习和有监督学习的特点, 是数据挖掘机器学习和模式识别领域的重要研究方向之一。半监督聚类的优越性主要在于针对无标签样本进行聚类时, 可利用少量有监督的样本信息作为指导。因此, 如何在聚类算法中更好地利用有标签样本所包含的领域知识, 指导聚类过程, 是进一步提高聚类质量的关键问题之一。本文提出了一种基于动态粒子群算法的半监督K均值聚类算法PSO-Kmeans。该算法采用动态粒子群算法的搜索空间模拟所有聚类样本的欧氏空间, 用每个粒子的位置代表一组聚类质心, 分别用K均值算法聚类, 然后计算适应函数, 不断迭代搜索, 通过质心优化来获得较好的聚类效果。并根据半监督聚类的特点, 定义了一个欧氏距离和监督信息相结合的新的聚类质量评价函数, 从而将K均值算法很好地应用于半监督聚类问题。改进后的算法通过在UCI多个常用数据集上测试都取得了较优的聚类结果。

1 基于遗传算法及K均值算法的半监督聚类

半监督聚类是在大量无标签数据中加入少量的有监督信息, 以帮助聚类算法获得更好的聚类效果。在实际应用中, 有监督样本信息表现形式为两类。第一类是已知部分待聚类样本的标签, 在聚类时就需要尽量把相同标签划分至同一个簇, 而不同标签尽量不在同一个簇;第二类是已知部分样本的must-linked或cannot-linked点对信息, 在聚类时就要求尽可能将受must-linked约束的点对划分至相同的簇, 而将受cannot-linked约束的点对划分至不同的簇。聚类质量评价指标是聚类分析的核心研究内容之一, 传统上主要采用聚类的类内紧致度及类间离散度来度量。而对半监督聚类质量的评价, 除了考虑上述问题外, 还需要考虑对有监督信息的满足程度。

文献[1]提出了一种基于遗传算法的K均值聚类算法。其中, 每个染色体编码对应于传统K均值算法中的一组聚类中心, 对于每组中心采用K均值算法聚类, 然后计算每条染色体的适应度。实验结果表明该算法可获得较高的聚类质量, 但仍有一些需改进的问题。

首先, 对于每个染色体所代表的聚类中心, 采用传统的K均值算法聚类, 这意味着对有标签数据的划分仍然遵循欧氏距离最小原则, 而忽视其标签信息所隐含的约束条件。如图1所示, 在一个二维聚类空间中, 三角形和菱形分别代表具有不同类标签的数据, 圆形代表无标签的数据, 根据欧氏距离, 样本a应该划分到B中, 因为与簇A的欧氏距离稍大于B;然而由于簇中大部分是与a相同标签的数据 (即三角形) , 根据领域知识a应该划分到A中。

其次, 在应用遗传算法时, 染色体编码表示聚类初始质心向量, 产生下一代染色体的方法是交叉变异。交叉实际上是原有基因的重新组合, 变异是随机突变。当问题的解空间有限和离散时, 遗传算法可以通过基因重组和适当的变异搜索到较优的解。但对于搜索聚类的最优初始中心向量这样的连续问题, 交叉操作实际上进行的是多组初始中心向量的组合交换, 并未生成新的初始中心向量或者向较优的初始中心向量移动。这使得获得新的更优的初始中心向量的重任主要由变异来实现, 这就大大降低了获得更好的初始中心向量的概率。

针对上述问题, 可从如下方面进行改进。首先, 在决定把一个样本划入哪个簇时, 对于无标签数据, 可根据其与质心距离来决定;而对于带标签数据, 则需要综合考虑距离和类别标签信息来确定。其次, 由于粒子群算法在搜索连续空间最优解方面具有天然的优势, 可以考虑采样粒子群优化 (PSO) 算法代替遗传算法进行聚类初始中心向量的寻优。

2 动态粒子群优化算法

粒子群优化 (PSO) 算法是一种进化计算技术, 源于对鸟群捕食的行为的模拟。搜索空间中每个粒子代表一个可能解, 粒子在解空间中移动的过程就是搜寻最优值的过程。所有的粒子都有一个表示当前在解空间中位置的属性Xi= (xi1, xi2, …, xin) , 根据粒子当前位置会产生一个粒子适应度以反映粒子位置即解的优劣。每个粒子还有一个速度向量Vi= (vi1, vi2, …, vin) 决定其运动的方向和运动的快慢。首先粒子群初始化为一群随机粒子 (随机解) , 然后通过迭代来寻找最优解。在每一轮的迭代中, 粒子通过速度更新当前位置, 并通过适应值函数计算出其适应度, 然后根据式 (1) 更新其当前速度:

Vi=ωVi+c1×rand () × (Pbesti-xi) +

c2×rand () × (Gbest-xi) (1)

接着按照式 (2) 更新粒子位置Xi:

Xi=Xi+Vi (2)

其中Pbesti表示粒子i的个体最优值, Gbest表示整个粒子群的全局最优值。PSO粒子变化为连续值, 因此较适合于求解连续值域上的数值优化问题。

粒子群算法的时空复杂度主要与粒子的数目有关。在PSO算法的某一次迭代中, 如果有部分粒子位置不佳, 致使其Pbesti连续多次没有更新, 这些粒子当前所在位置较差, 并不能为Gbest的更新做出贡献, 为提高算法搜索效率, 可以把这些粒子删除。相反, 如果Gbest连续多次没有被更新, 此时粒子群体可能陷入局部最优, 需要增加粒子来增加启发信息, 加快Gbest的更新。因此, 提出动态种群管理策略, 具体描述如下:

1) 当Gbest连续s次没有改变, 说明现有种群需要新的粒子来提供启发信息, 则动态添加一个粒子, 并用个体最优Pbesti更新最频繁的两个粒子的位置组合成初始位置, 以全部粒子的平均速度作为初始速度;

2) 当Gbest连续s次改变, 说明现有种群启发信息已经有充足, 为提高算法运行效率, 则动态删除Pbesti更新最不频繁的粒子。

加入动态管理种群后的粒子群算法, 删除了无用粒子, 节省了运行时间, 增加了新的粒子提高搜索能力, 避免陷入局部最优。

3 动态管理种群与K均值结合算法——PSO-Kmeans

针对以上分析, 提出粒子群算法与K均值算法相结合的半监督聚类算法——PSO-Kmeans。

3.1 改进的样本划分判定函数

由上部分的分析可知, 当样本是有标签数据时, 把样本划分到与质心欧氏距离最近的簇中时, 需要综合考虑质心距离和簇中已有标签数据的类别以及数量情况。则采用欧式距离和标签数据作用的线性组合来作为判定函数。对于有标签数据Xi以及某个样本集合Cj, 构造函数Semi (Xi, Cj) :

Semi (Xi, Cj) =Cannot_linked (Xi, Cj) +Different (Xi, Cj) -

(Must_linked (Xi, Cj) +Same (Xi, Cj) ) (3)

其中, cannot-linked (Xi, Cj) 表示集合Cj中, 与Xi有Cannot_linked 关系的样本个数;Different (Xi, Cj) 表示集合Cj中, 与Xi有具有不同类别标签的样本个数;Must-linked (Xi, Cj) 表示集合Cj中, 与Xi有Must_linked 关系的样本个数;Same (Xi, Cj) 表示集合Cj中, 与Xi有相同类别标签的样本个数。此外, 若Xi是无标签数据, 则Semi函数的值为0;改进后的算法, 则把样本Xi归入使得函数 (4) 值最小的簇Ck中。

$\sum_{j = 1}^{m} (X_{i j} - C_{k j})^{2} + λ \times S e m i (X_{i} ‚ C_{k})$ (4)

式 (4) 是空间距离和标签数据个数的线性组合, 其中λ取值按下式计算:

$λ = \frac{\sum_{k = 1}^{Κ} \sum_{j = 1}^{m} (X_{i j} - C_{k j})^{2}}{Ν_{s e m i}}$ (5)

其中Nsemi是所有具有监督信息的样本个数, $\sum_{k = 1}^{Κ} \sum_{j = 1}^{m} (X_{i j} - C_{k j})^{2}$ 是样本Xi到所有质心的欧氏距离和。

对比传统欧氏距离判定方法, 新的判定函数加入了半监督的信息λ×Semi (Xi, Ck) , 这样就平衡了距离和类别的冲突, 实现样本的正确划分。

3.2 定义聚类目标函数

可以用聚类离散度和聚类不纯度的线性组合作为优化的目标函数:

α×cluster_dispersion () +β×cluster_impurity ()

其中可以用欧氏距离之和代表作为离散度度量, 用基尼指数作为不纯度度量, 优化的目标函数成为:

fun () =α× (∑Kk=1∑nkik∑mj=1 (Xikj-Ckj) 2+

λk×semik () ) +β×Gini () (6)

其中, $\sum_{k = 1}^{Κ} \sum_{i k}^{n k} \sum_{j = 1}^{m} (X_{i k j} - C_{k j})^{2}$ 为所有样本到其质心的欧氏距离和, λk是第k个簇中样本到质心欧氏距离的平均值, Semik () 是第k个簇的监督信息数。

3.3 粒子设计

为了发挥粒子群算法的优势, 使得搜索空间和聚类空间匹配更自然, 即用每个粒子代表一组K个质心, 相应的数据结构为含有K个元素的向量, 其中每个元素代表一个欧氏空间的点, 粒子通过向全局最优移动, 聚类的质心也不断优化。

3.4 粒子适应度函数

粒子适应度定义为fit () =-fun () , 即使用聚类结果的评价指标作为粒子适应度。fun () 值越小, fit () 越大, 聚类结果越好, 相应地, 粒子适应度越高。

3.5 PSO-Kmeans算法流程

PSO-Kmeans (D, N, K, Pn, MAX, MIN, s)

输入:数据集D, 最大迭代次数N, 类的个数K, 初始粒子数目Pn, 粒子数目上限MAX, 粒子数目下限MIN, 粒子动态管理敏感指数s。

输出:具有类标签的数据集D以及聚类准确率。

算法步骤:

步骤1 初始化粒子群随机生成K个聚类初始质心, 用K个点的位置组成的数组初始化为一个粒子的初始位置, 循环往复, 形成Pn个粒子的初始位置及初始速度。

步骤2K均值聚类对于每个粒子所代表的一组质心, 把每个样本按照式 (4) 划入到最近的簇中, 然后计算每个粒子的fit () 。

步骤3 根据粒子适应度更新个体最优Pi及全局最Pg。

步骤4 粒子移动由式 (1) 更新粒子速度;由式 (2) 更新粒子位置。

步骤5 动态管理种群 ①当Gbest连续s次改变, 且Pn>MIN, 则动态删除Pbesti更新最不频繁的粒子。

②当Gbest连续s次没有改变, 且Pn<MAX, 则增加一个粒子, 用Pbesti更新最频繁的两个粒子的位置组合成初始位置, 以全部粒子的平均速度作为初始速度。

③当Gbest连续s次没有改变, 且Pn=MAX, 则删除Pbesti更新最不频繁非全局最优粒子, 然后动态添加一个新的粒子, 并用Pbesti频繁被更新的两个粒子的位置组合成初始位置, 以全部粒子的平均速度作为初始速度。

步骤6 判断是否达到最大迭代次数N, 若达到则输出聚类准确率, 否则返回步骤2) 继续迭代。

相比与文献[1]提到的GA-Kmeans算法, PSO-Kmeans算法把粒子群算法搜索空间与聚类空间对应的更加自然, 用每个粒子的位置代表初始质心的位置。于粒子速度是根据当前位置变化的, 所以当远离较优质心时候, 粒子速度较快, 当靠近质心时, 速度减慢, 不会出现GA算法中的质心抖动现象, 能够连续向最优质心方向移动, 所以很快找到较优质心。根据式 (4) 将欧氏距离和监督信息结合起来, 用来选择所要划分的簇, 很好地平衡了欧氏距离和标签属性的冲突, 所以算法具有更好的聚类准确率。

4 实验结果以及分析

4.1 实验数据及实验环境

实验采用多个UCI 数据集进行了验证。本研究的所有实验在配置为Intel 奔腾D2.8G CPU 、2G内存的计算机上进行, 算法用C++编程实现。

4.2 实验方案

采用三种不同聚类算法在相同数据集上运行, 得到如图1的结果。其中, GA-Kmeans 为文献[1]提出的用遗传算法优化K均值算法;PSO-Kmeans为改进算法; Kmeans算法与PSO-Kmeans算法使用相同的归类函数 (式 (4) ) 以及目标函数 (式 (6) ) , 但并没有结合粒子群优化质心。

4.3 实验参数设置

分别随机设置所有数据10%作为已有标签数据和实例限制数据为监督信息。为了消除设置监督信息的随机性, 针对每个实验数据集, 生成5组不同的监督信息集合, 对于每组监督信息集合, 每种算法运行10次计算聚类准确度平均值。PSO-Kmeans中, 开始粒子个数为3, 粒子个数上限为30;s设置为2, 即连续两次没有变化或者连续两次变化则进行种群管理。

4.4 实验结果汇总

4.5 实验结果分析

由表1中多个数据集上的聚类结果可以看出:

1) PSO-Kmeans相比于用传统传统算法Kmeans, 由于质心优化, 改进后的算法聚类准确度有了很大提高。

2) 与GA-Kmeans相比, 由于粒子群空间与欧氏空间耦合度更高, 并且在样本归类时加入了半监督信息, 聚类结果PSO-Kmeans普遍更优。

3) 图2测试了标签数据占数据集不同百分比 (从5%到40%) 时各种算法的聚类精度, 从结果可以看出, 当有标签数据所占百分比较少时, 两种算法聚类结果精度差别并不大, 逐渐增加百分比, GA-Kmeans聚类精度不再增加, 与PSO-Kmeans差距越来越大。这说明, 在聚类过程中用加入监督信息的新的邻近度量计算函数, 即式 (4) , 比单纯欧氏空间距离能更好地利用监督信息, 得到更好的聚类精度。

5 结论

本文提出了一种将用粒子群算法优化K均值半监督聚类的新算法。在聚类过程中, 充分挖掘有标签数据的监督聚类作用, 即利用欧氏距离与监督信息的线性组合函数来决定每个样本划分到哪个簇中。同时采用粒子群算法优化聚类质心弥补了K均值对于初始质心敏感的缺陷, 并采用动态管理种群的方法, 提高了粒子寻优效率。通过在UCI多个数据集上与其他聚类算法运行结果对比表明, 新算法是具有较高的聚类准确率。但是, 新算法对需要聚类的数据集有一定要求, 对于没有标签数据或者在不同属性维度上取值有不同量纲的数据集, 算法并不能展示很好的效果, 相关问题需要进一步研究。

参考文献

[1]Ayhan Demriz K P, Bennett M J.Embrechts Semi-Supvised ClusteringUsing Genetic Algorithm[J].IEEE Communications Magazine, 1999.

[2]Ian Davidson, Davis, Sugato Basu.A Survey of Clustering with InstanceLevel Constraints[J].ACMTransactions on Knowledge Discovery fromData, 2008:1-41.

[3]赖玉霞, 刘建平, 杨国兴.基于遗传算法的K均值聚类分析[J].计算机工程, 2008, 10, 34 (20) :54-56.

[4]傅景广, 许刚, 王裕国.基于遗传算法的聚类分析[J].计算机工程, 2004, 30 (4) :122-124.

[5]Jiawei Han, Micheline Kamber, 著.数据挖掘概念与技术[M].范明, 孟小峰, 译.机械工业出版社, 2007.

[6]Yu Liu, Zheng Qin, Zenglin Xu.Feature Selection with Particle Swarms, Computational and Information[J].Science:First International Sympo-sium, CIS 2005, Shanghai, China, December 16-18, Proceedings, LNCS3314, 2004:425-430.

[7]Ling Wang, Jinshou Yu.Fault Feature Selection Based on Modified Bi-nary PSO with Mutation and Its Application in Chemical Process FaultDiagnosis[M].ICNC, LNCS3612, 2005:832-840.

k均值邻近算法篇6

遥感影像的非监督分类,是指人们事先对分类过程不施加任何的先验知识,仅凭据遥感影像的光谱特性的分布规律,顺其自然地进行盲目分类。它的主要优点表现在:①不需要对所要分类的区域有广泛的了解和熟悉;②人为误差的机会减少;③独特的、覆盖面小的类别均能够被识别[1]。

K均值算法是一种常用的非监督分类方法[2],该算法的结果往往受到初始聚类中心选择和聚类中心的个数等因素的影响。

为了使初始样本之间的光谱特征差异尽可能大,本研究在VC++2005开发环境下采用最大最小距离选心法,实现初始样本的确定,然后根据初试类别中心,通过不断的迭代实现遥感图像的自动分类。考虑到遥感图像数据量比较大,本研究采用VC2005作为程序实验平台。VC2005可以方便地控制内存的分配,大大提高程序的处理速度。同时,使用VC2005能够开发出可自行调整程序控制参数的对话框以便用户操作。

1 实验所采用遥感图像的说明

本实验采用的遥感图像格式是ENVI标准格式,该格式由文本文件部分和数据部分两个文件组成。数据部分只记录图像的数据内容,不包含有其他内容;而文本文件部分则是对该图像数据部分的组成和其他一些波段信息进行说明。如果没有文本文件的说明,数据部分是无法读取的。文本文件中记录了该图像包含的波段数、数据部分中每个像素的存储类型、每个波段的图像包含的行数和列数、每个波段图像像素的排列方式和每个波段图像所对应的波长等信息。

2 K均值算法的步骤和主要的VC实现

由于进行图像分类的过程中会用到大量的内存空间,为了提高处理速度,采用VirtualAlloc()函数来分配虚拟内存,而且保证每次分配的内存大小都是64的倍数,每次对文件进行读操作时寻址都是64的整数倍。

2.1 基本初始参数的确定

为了使分类过程能够快速准确地进行,对K均值算法的控制参数进行设定,参数录入界面,如图1所示。这些参数包括分类完成后的类别数numclass,最大迭代次数NI,分类完成后输出图像路径以及参加分类运算作为特征向量的波段的选择。对于参加分类运算的波段的选择,是根据每个波段对应的波长信息进行选择的。这些参加运算的波段构成了计算类别之间距离的多维向量。

2.2 初始类别中心的选择

目前比较常用的初始类别中心的确定方法有像素光谱特征比较法,最大最小选心法和总体直方图均匀定心法。采用最大最小选心法是因为该选心法与光谱特征比较法相比,具有不受阈值T选定影响的好处,而与总体直方图均匀定心法相比,又具有更接近实际各类集群分布位置状况的优点[3]。

最大最小选心法就是先从N个抽样像素中任选一个作为第1个初始类别中心,然后计算其他抽样像素与该抽样点的距离,取距离最远的那个抽样像素作为为第2个初始类别中心,接着计算剩余抽样点到已有各初始类别中心的距离,并取其中最小距离作为该点的代表距离,在此基础上,从剩余样本集中选出代表距离最大的作为下一个初始类别中心,重复上述步骤,直到初始类别的个数达到需要的个数为止[4,5]。

为了使初始类别中心之间的距离尽可能地大,实验以32个像素点为间距获取(图像高度×图像宽度)/32个抽样像素。

int chushiyanben=(img.width*img.height)/32;//获得初始样本的个数

temp=(INT16*)VirtualAlloc(NULL,chushiyanben*weishu*sizeof(short),MEM_RESERVE|MEM_COMMIT,PAGE_READWRITE);//动态分配内存用于保存所有抽样像素的weishu维的向量,weishu为向量的维数即参加运算的波段的数目.

获得抽样样本后,通过最大最小选心法的计算步骤就可确定numclass个初始类别中心。

2.3 分类

计算图像中每个像素与初始类别中心的距离,并将与该像素距离最小的初始类别中心的序号作为该类的标志输出到输出文件中。为了提高程序的速度,每次读取以64×64个像素为一块进行处理。

2.4 计算新的聚类中心

计算新的聚类中心的做法是:将输出分类图的文件与原始图像的文件同时打开,读取分类输出图上像素的值来确定与该像素对应的原始文件中的像素属于哪一类,然后将所有属于该类的原始图像像素的一个波段(该波段是参加分类运算的波段)的所有灰度值相加,然后除以属于该类像素的个数作为该类新的聚集中心某一维的分量。

3 应用效果与结论分析

为了对该算法进行实验,取一副ENVI标准格式的原始图像,该图像包含80个波段,像素存储类型为SHORT,行数和列数为201×151,像素的排列方式为BSQ,并且每个波段都包含所对应的波长,范围从417.399 994 nm到854.400 024 nm。取参加分类运算的波段为第8波段、第35波段和第65波段,合成图像,如图2所示。类别个数的选择对于图像的分类结果也有很大的影响,但是目前关于如何获得最优分类个数的方法研究还没有重大的成果,因此笔者通过目视统一取类别数为7,研究迭代次数对分类结果的影响。

为了了解迭代次数对分类结果的影响,保持以上参数不变,取迭代次数为1,2,5,15,和30,如图3～图7所示。

比较图2和图3可知,图3上的类之间的边界信息比较明显,几乎把图2上可以看出的边界信息都反映出来了。这主要是由于采用最大最小选心法,获得的初始类别中心是相互之间差距最大的类别中心。因此,进行1次分类迭代获得的分类图像差别效果很明显。但是,同时图3将在图1上存在有差别的类也归结于同一个类的情况,这还是由于分类时类别中心的影响,在分类时它们与同一个初始类别中心的距离最小。

从图3开始到图7迭代次数依次变大,看出原先的类有的范围在扩大,有的范围在缩小,这是由于每进行一次迭代,分类聚类中心进行次调整。在这个不断调整的过程中,聚类中心由第1次迭代时相互之间差别最大的类的聚类中心渐渐调整为图像上所占像素比较多的类的聚类中心。

同时,一些反映边界信息的类如果在原图中所占的像素比较少就被并入别的类,从而看不出有些类之间的边界。

图6和图7之间相差15次迭代,但是这两副图之间的差别不是很大;而图4和图5迭代次数相差3,但是图像变化很大,原因在于刚开始分类时,每次迭代后聚类中心的改变比较大,因此分类得到的图像差别较大。但是,随着迭代次数的增加聚类中心的改变越来越小,因而每次分类得到的图像之间的差别也不大。随着迭代次数的不断增加,最后会达到前一次迭代和后一次迭代的聚类中心相同。

4 结束语

本研究采用最大最小选心法,在确定分类总数的条件下,研究了K均值算法中迭代次数对遥感影像的非监督分类的影响,随着迭代次数的增加,类别中心会从相互之间差距最大的聚类中心调整为图像上所占像素比较多的类的聚类中心。反映到分类图上就是从开始表现图像边界的图转向表现图像占像素比较多的类组成的图。

由于K均值算法需要先给定类别数,而这在很多情况下都是凭主观臆测获得。另外,K均值算法只采用均值作为一个类的代表点,这只有当类的自然分布为球体或接近球体时,即各类中各分量的方差接近相等时才可能有较好的分类效果[6]。因此,该方法还有待于进一步完善。

参考文献

[1]张良培.高光谱遥感[M].武汉:武汉大学出版社,2005.

[2]汤国安.遥感数字图象处理[M].北京.科学出版社,2002.

[3]BEZDEK J C.Pattern Recognition with Fuzzy Objective Func-tion Algorithms[M].New York:Plenum Press,1981.

[4]KRUGLINSKI D J.Visual C++技术内幕:第4版[M].北京:清华大学出版社,1998.

[5]PROSISE J.MFC Windows程序设计:第2版[M].北京:清华大学出版社,1996.

k均值邻近算法篇7

图像分割是一种基本的计算机视觉技术,是图像分析和模式识别需要解决的首要问题和基本问题,是从图像处理到图像分析的关键步骤,图像分割结果的好坏直接影响对图像的识别和理解。

K-MEANS聚类法在图像分割中得到广泛应用[1,2]。基于K-MEANS聚类法进行图像分割是通过找到特征空间中像素值的空间聚类,并把每一个像素划分到不同的聚类中来实现图像的分割。K-MEANS 算法需要首先给定聚类数K,然后将n个对象划分为 K个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高,而不同聚类中的对象相似度较小。作为一种经典的聚类算法,K-MEANS算法有其优越性,当然也有其局限性,如聚类数K值必须依据先验知识提前设定、最初的类中心是随机选取的(这常常导致每次聚类产生不同的分类结果)、聚类效果的好坏依赖于距离判定公式、图像特征值等条件的选取。在K-MEANS算法中,常规的优化算法主要针对聚类数和聚类中心的选取[3,4,5],即通过一些检测聚类有效性的函数计算最佳聚类数kopt,并在此基础上优化分割效果。近年的一些研究[6,7]表明,融合多种图像特征更有利于获得较好的分割效果,文献[7]的研究表明,在对自然彩色图像进行分割时,考虑了像素的空间特征,(与仅考虑颜色特征相比)算法有更好的鲁棒性。

本文基于K-MEANS聚类法进行彩色图像分割,选择颜色、纹理和空间特征进行聚类分析,针对K-MEANS聚类算法存在的过分割问题,提出一种改进算法。

1 图像特征提取

1.1 颜色特征的提取

颜色特征是在图像分割中应用最为广泛的视觉特征,在本文的彩色图像分割算法中,我们采用了Lab色彩模型。Lab色彩模型中L表示照度(Luminance),a表示从红色至绿色的范围,b表示从蓝色至黄色的范围。在Lab模式下,图像的亮度信息和色彩信息被分开保存,调整颜色通道时亮度通道将保持不变。这样L通道可以看作是一影像的灰度版,其中保存了图像的细节信息,因此利用L通道可容易区分自然图像中的明暗细节。此外Lab模型具有宽阔的色域,不仅包含了RGB的所有色域,而且弥补了RGB色彩模型色彩分布不均的问题。

1.2 纹理特征的提取

纹理通常指在图像中反复出现的局部模式和它们的排列规则,具有不依赖于颜色或照度并可以反映图像中同质现象的特点,是一种非常有效的图像特征,本文基于图像的灰度共生矩阵提取图像的纹理特征。灰度共生矩阵反映了图像灰度关于方向、相邻间隔、变化幅度的综合信息,是分析图像的局部特征和排列规律的基础。根据共生矩阵,可以计算熵、对比度、能量、相关、方差等 16 种用于提取图像中纹理信息的特征统计量。本文选择了对比度、能量、相关性、同质性描述图像的纹理特征[8]。特征提取步骤如下:

(1) 将彩色图像降为低阶灰度图像,灰度级取为8。

(2) 设置半径为d大小为(2d+1)×(2d+1)的窗口矩阵,通过遍历图像的方式计算出窗口内灰度共生矩阵,并将其映射到窗口中心所代表的像素上。

(3) 基于灰度共生矩阵,利用式(1)-式(4)计算对比度、能量、相关性和同质性四个纹理特征,并将值返还至对应的像素中心。

$f = C Ο Ν = \sum_{n = 0}^{G - 1} n^{2} [\sum_{i = 1}^{g} \sum_{j = 1}^{G} p (i, j)] | i - j | = n (1)$

$f = E Ν G = \sum_{i = 1}^{G} \sum_{j = 1}^{G} p^{2} (i, j) (2)$

$f = C Ο R = [\frac{\sum_{i = 1}^{G} \sum_{j = 1}^{G} (i \cdot j) p (i, j) - μ_{x} μ_{y}]}{σ_{x} σ_{y}} (3)$

$f = Η Ο Μ = \sum_{i = 1}^{G} \sum_{j = 1}^{G} \frac{p (i, j)}{1 + | i - j |} (4)$

对比度(CON)可理解为图像的清晰度;能量(ENG)是图像灰度分布均匀性的度量,图像呈现较粗的纹理,能量的取值相应较大;相关度(COR)是灰度线形关系的度量,反映某种灰度值沿某方向的延伸长度;同质性(HOM)是图像局部灰度均匀性的度量,如果图像局部的灰度均匀,同质性的取值就较大。

此外,针对在图像边缘无法获取完整的窗口信息而得不到纹理特征值的问题,考虑到特征值同参与计算的像素之间的联系,本文采取了区域均值的算法,具体计算过程如图1所示。以半径d=3的窗口矩阵为例,边缘像素X的值近似的表示为与其相关的所有纹理特征值之平均值。即:

X=mean $(\sum_{i = i - d}^{i + d} \sum_{j = j - d}^{j + d} p (i, j)) (5)$

其中(i, j)为X的空间坐标。

2 基于K-均值聚类的图像分割算法

2.1 K-均值聚类算法简介

假设有一组包含K个聚类的数据,其中第k个聚类可以用集合Gk来表示,假设Gk包含nk个资料 (x1,x1,…,xnk),此聚类中心为yk,则该聚类的平方差ek可以定义为:

$e_{k} = \sum_{i}^{n_{k}} (x_{i} - y_{k})^{2} (6)$

其中xi是属于第 k 类的资料点。而这K个聚类的总和平方差E便是每个聚类的平方差总和: $E = \sum_{k = 1}^{Κ} e_{k}$ 。K-MEANS聚类算法通过迭代的方式,设法降低E的值,以使得各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。其算法步骤如下:

(1) 从n个数据对象任意选择K个对象作为初始聚类中心;

(2) 根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;

(3) 计算每个(有变化)聚类的均值(中心对象);

(4) 循环(2)到(3)直到每个聚类不再发生变化为止。

值得注意的是,经典K-MEANS虽然在一系列迭代和反复运算后各聚类将趋于一致,函数收敛,但由于初始聚类中心随机设定,可能导致每次聚类结果不同。

2.2 距离测度

距离测度的选择对K-均值聚类效果的影响很大,针对不同类型图片,本文提出以下三种距离测度:

(1) 欧氏距离

在n维空间中欧氏距离的公式是:

$D = (\sum_{i = 1}^{n} (x_{i} - y_{i})^{2})^{1 / 2} (7)$

(2) 曼哈顿距离

曼哈顿距离又称为城市区块距离,也就是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。距离的公式如下:

D=|xi1-xj1|+|xi2-xj2|+…+|xip-xjp| (8)

(3) 马氏距离

马氏距离是由印度统计学家马哈拉诺比斯(P. C. Mahalanobis)提出的,表示数据的协方差距离。与欧式距离不同的是它考虑到各种特性之间的联系,并且是尺度无关的,即独立于测量尺度。对于一个均值为μ=(μ1,μ2,…,μp),协方差矩阵为Σ的多变量向量x=(x1,x2,…,xp),其马氏距离为:

$D_{Μ} (x) = \sqrt{(x - μ)^{Τ \sum - 1} (x - μ)} (9)$

3 K-均值聚类算法的研究与改进

首先研究了不同的距离测度(欧氏距离、曼哈顿距离和马氏距离)对分割结果的影响。在K-MEANS聚类中,特征向量分量选择了像素的颜色和纹理特征。结果表明马氏距离能得出比较符合人类视觉的分割的效果。而欧氏距离和曼哈顿距离由于相似性判定的局限,对于自然景物中大范围色块的分割处理较好,对于局部细节的分割则显得不尽人意。

比较图2中三组距离分割结果可知,欧氏距离、曼哈顿距离和马氏距离对图像整体的分割能力都比较接近,但在细节部分表现出了差异。可以看出其中欧氏距离和曼哈顿距离在分割屋顶与树丛这类纹理丰富的区域时产生了大量斑点,而用马氏距离分割时则有较大改善。

其次,我们还研究了像素的空间特征对分割效果的影响,图5给出了部分实验结果,其中图(b)为使用7维特征向量进行聚类的结果,7个分量分别为颜色3维(L、a、b)、纹理4维(对比度、能量、相关性、同质性)。图(c)的实验使用了9维特征向量,又增加了2维空间特征(x、y)。

由图3可以看出,像素的空间特征即坐标向量对分割结果的影响非常明显,这主要表现在对大范围区域的分割上。对于大范围区域而言,在考虑了空间特征后可能产生断裂情况,但这种断裂不影响图像的边缘分割。另一方面,考虑空间特征可得到更多细节信息。

实验表明,聚类数目K的选择对K-MEANS算法分类结果影响很大:若K取小了就会有的区域不能分割出来,若K取大了就会出现过分割。所以在分割图像前,K值的大小一般都由先验知识判断得出,当需要处理大量图像时,由人为判断给出K值是不现实的。为此,我们提出一种自适应选取K值的方法,其核心思想是将K值转换成只与色彩、纹理差异有关的阈值C,通过调控C的大小自适应选择聚类数K,从而改善分割效果。

算法流程如下:

(1) 设定初始聚类数K。K值可任取,但应当大于待处理图像本征K值;

(2) 按照经典K-MEANS聚类方法对图像聚类(包含空间、纹理和颜色特征);

(3) 对分割后图像中各独立区块编号;

(4) 寻找所有相连的区块,以编号对的方式记录;

(5) 剔除空间特征,计算每对相连区块的聚类中心的距离,找出距离最小的一对;

(6) 如果距离小于预先设定的阈值C则合并二者;

(7) 重复4-6,直到相连的区块距离均高于阈值C时结束。

在对图像进行处理时,常因自然图像存在细微的明暗变化而使分割后的图像出现斑点和空洞。为解决这一问题,我们在上述流程(5)中引入加权函数修正距离公式,以使小区块能被优先合并。设i和j分别为相互连接的一对区域内像素点数,引入修正函数z=f(i,j),使其满足在点(i,j)趋向于i轴或j轴时,函数值趋于0,在i、j的值增大过程中,函数值以指数形式迅速趋于1,本文使用了如下修正函数:

$f (x, y) = (1 - e^{- \frac{x}{C}}) (1 - e^{- \frac{y}{C}}) (10)$

式中C为常数。调节其大小可改变指数增长的速度,从而适用于不同大小的噪点。

4 实验结果与分析

图4中给出了部分实验结果。其中图(b)是基于空间、颜色和纹理特征进行聚类分割的结果,图(d)是在(b)基础上合并相似度高于设定阈值C的相邻的聚类所形成的分割图像和聚类数K,(e)是增加修正函数并进行再合并的结果。

作为对比,我们还采用文献[3]的方法进行了实验,即先用文献[3]提出的方法确定最佳聚类数Kopt,再基于Kopt进行传统的K均值聚类,实验结果如图4(c)所示。(f)中的人工分割结果是以一定的分割期望为限定的手工分割,本文以此为参照对本文实验结果进行了评估。由图4的实验结果可知,通过本文提出的聚类合并处理,K值由之前所设定的较大值,下降到与图像最佳聚类数比较接近的数值,并在引入修正函数后,分割结果有了显著提高。这表明引入修正函数可较好地解决自然图像中因场景明暗变化而产生的过分割问题,这一点在后面的表1的数据中更清楚地反映出来。此外,我们还将本算法用于分割纹理较突出的图像,从图5的实验结果我们也可以看出,本文提出的聚类算法对这类图像的分割效果优于基于Kopt聚类的分割效果。图中的综合特征指色彩、纹理和空间特征。

表1列出了部分实验数据,表中的第二栏初始设定的聚类类别数一般可任意选取,但必须大于图像本征K值,需要说明的是K值不能选得太小,否则不能反映局部区域图像细节,当然K值选择大了也将产生过分割,但这种过分割问题可以通过进一步的合并较好地解决。第四栏的合并后聚类类别数是按照本文提出的改进算法流程,即在去除空间坐标后通过比较相连区块之间颜色或纹理特征相似度,并以阈值C为合并条件而得出的。第五栏是采取“图像分割+加权合并”后得到的独立的区域数量。最后,为评价本文算法的性能,将本算法的分割结果与人工分割结果进行了对比。同时也将采用文献[3]方法分割的结果列于其中。从这些数据看,本文提出的方法明显优于文献[3]的基于Kopt聚类分割算法。

5 结论

K均值聚类算法在图像分割中有着广泛的应用,本文主要针对K均值算法存在的过分割问题和聚类数目K难以确定的问题开展了研究,同时还分析了图像的空间特征和距离测度对分割效果的影响。实验结果表明采用马氏距离分割图像能得出比较符合人类视觉的分割效果;特征向量中加入空间特征可以更好地表达细节信息。在抑制过分割方面,采取了先分割后合并的方法,并在类合并时通过引入修正函数和类中心间距离参数C控制分割效果。因此本文提出的算法对图像分割效果有较明显的提高,较好地抑制了图像中因场景明暗变化而产生的过分割斑点。

参考文献

[1]Clausi D A.K-means Iterative Fisher(KIF)unsupervised clusteringalgorithm applied to image texture segmentation[J].Pattern Recogni-tion,2002,35(9):1959-1972.

[2]Krista Rizman Zalik.An efficient k-means clustering algorithm[J].Pat-tern Recognition Letters,2008,29(9):1385-1391.

[3]杨善林,李永森,胡笑旋,等.K-means算法中k值优化问题研究[J].系统工程理论与实践,2006,26(2):97-101.

[4]于剑,程乾生.模糊聚类方法中的最佳聚类数的搜索范围[J].中国科学(E辑),2002,32(2):274-280.

[5]Tse Wei Chen,Yi Ling Chen,Shao Yi Chien,Fast Image SegmentationBased on K-MeansClustering with Histograms in HSV Color Space[C].Multimedia Signal Processing,IEEE 10th Workshop,Oct.2008:322-325.

[6]Dana Elena Ilea and Paul F.Whelan,Color image segmentation using aspatial k-means clustering algorithm[C].10th International MachineVision and Image Processing Conference,30 August-1 September,2006,Dublin,Ireland.

[7]Fan J,David K,Yau Y,Ahmed.K.Elmagarmid,Walid G Aref.Auto-matic Image Segmentation by Integrating Color-Edge Extraction andSeeded Region Growing[J].IEEE Transaction on Image Processing,2001,10(10):1454-1466.

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【k均值邻近算法】相关文章：

K+均值06-11

东海及邻近地区岩石圈三维结构研究06-06

邻近既有线路基施工安全作业指导书04-11

均值不等式05-07

求平均值06-05