K均值聚类（共8篇）
K均值聚类 篇1
link
appraisement
industry
point
实行学分制使得因材施教成为可能, 为学生的个性化发展提供了基础, 同时, 也给学校的学生日常管理工作带来了巨大的挑战。为了更好地管理学生, 文中使用K均值对学生进行聚类, 给出了具体的聚类方法和实行过程, 在实验中采用三种不同的距离计算方法对学生进行聚类, 表明了该方法是有效的。
随着高等教育教学改革的不断深化, 各地高校为适应高等教育大众化、阶段多样化的要求, 都积极探索并实施学分制的管理模式。实行学分制给学生的个性培养和教学的因材施教提供了良好的发展空间, 但从学校方面来说, 学分制下的学生管理突破了原有的学生管理体制, 对学生管理提出了严峻的考验。
在学分制下, 虽然每一个学生的自由度加大, 但是整个学校里所有的学生在长期会有一些相同或相似的情况, 即所谓的“物以类聚, 人以群分”, 如果能根据长期以来的学生的表现对学生进行聚类, 使得同一类的学生有更多的共同点, 不同类的学生有较大的不同, 然后可以针对不同类型的学生采用不同的方法进行管理, 不仅可以提高管理的针对性, 而且可以更好的研究不同类型的学生的具体情况, 为以后的学生选课、就业等方面提供一些有益的建议。
聚类是将数据分类到不同的类或者簇这样的一个过程, 所以同一个簇中的对象有很大的相似性, 而不同簇间的对象有很大的相异性。K均值聚类算法是一种有效的聚类技术, 具有对大型数据集进行高效分类的特点, 因此, 本文采用该方法对学生进行聚类。
K均值聚类
k均值聚类是最著名的划分聚类算法, 由于简洁和高效使得其成为所有聚类算法中最广泛使用的。具体的计算过程如图1所示。
基于K均值的学生聚类
聚类不仅可以降低学生管理的难度, 而且使得学生管理具有针对性和高效性的优点;K均值是一种有效的聚类算法, 因此本文其应用于学生管理。由于学生的身高、性别、年龄等这些因素对于学生管理的意义不大, 而性格虽然重要, 但是数据很难收集, 而学生在学校的首要根本任务是学习, 而且学完课程都会有一个考试来检验学习的效果, 因此, 成绩数据不仅数据量大, 而且可以指导学生此后的选课及教学计划的制定, 因此, 文中使用学习成绩对学生进行聚类。具体的流程如图2所示。
(1) 数据预处理
由于描述成绩的数据可能是数值或者是等级这样的模糊值, 为了计算的方便, 需要对模糊数据进行数值化, 在本文中, 根据图3的对应关系进行数值化。
(2) 缺失值的处理
由于在收集数据的过程中各种因素导致的数据缺失是不可避免的, 因此, 需要对项目中存在的缺失值进行处理。常用的缺失值处理方法有删除存在缺失值的个案和缺失值插补。删除法是对缺失值进行处理的最原始方法, 它将存在缺失值的个案删除。由于成绩数据缺失的情况现有发生, 因此, 本文使用该方法对缺失值进行处理。
(3) K均值聚类
对成绩进行处理以后就可以聚类了, 首先确定将成绩聚为几类, 并确定相应的聚类中心;然后分别使用欧氏距离、余弦距离和相关度三种方法计算每一个同学的成绩与各个聚类中心的距离进行聚类;最后, 根据聚类结果重新计算聚类中心, 重复该过程直到收敛。
实验
本文以某校计算机专业的一个班一年的成绩为例进行实验, 使用前文的模糊数值和缺失值的处理方法进行数据预处理, 然后使用matlab对其进行聚类, 三种距离计算方法的聚类结果如图4, 5, 6所示。
结束语
本文探讨了在学分制下的学生管理工作, 并采用K均值方法对学生进行聚类, 并给出将K均值聚类算法应用于学生聚类的步骤和具体实施过程, 表明了该方法的有效性。
K均值聚类 篇2
摘要：基于93个土壤表层样品重金属Cu、Zn、Cr、Cd、Pb和Hg全量浓度分析数据,应用模糊分类方法结合地统计学手段,对南京市边缘带梅山钢铁厂附近总面积约14 km2样区内的土壤重金属污染状况进行了空间预测.结果显示,样区北部及东北角区域的土壤遭受重金属元素Cu、Zn、Cr、Cd的轻微污染,样区西侧沿长江呈带状分布的土壤由于其重金属环境容量较低,存在潜在污染风险,样区其它区域的`土壤未发现由上述重金属元素导致的污染现象.样区东北角土壤Pb、Hg污染严重,并与Cu、Zn、Cr、Cd污染在空间上重叠,是土壤重金属污染控制与土壤修复的重点区域.样区的东部和东北部区域土壤受Pb、Hg中度污染,在梅山集团的北部土壤轻微污染.研究表明,与直接对重金属浓度分析数据实施插值分析的常规克里格方法相比,模糊c-均值聚类结合地统计学方法获得的空间预测结果蕴含信息更加丰富,而模糊集理论及其相关算法在土壤学诸多领域中也具有极大的应用潜力.作 者：檀满枝 陈杰 郑海龙 张学雷 TAN Manzhi CHEN Jie ZHENG Hailong ZHANG Xuelei 作者单位：檀满枝,TAN Manzhi(中国科学院南京土壤研究所土壤与农业可持续发展国家重点实验室,南京,210008;中国科学院研究生院,北京,100039)
陈杰,张学雷,CHEN Jie,ZHANG Xuelei(中国科学院南京土壤研究所土壤与农业可持续发展国家重点实验室,南京,210008)
郑海龙,ZHENG Hailong(香港中文大学地理与资源管理系)
一种改进的k-均值聚类算法 篇3
k-均值算法属于聚类技术中一种基本的划分方法,具有简单、快速的优点。其基本思想[1]是选取k个数据对象作为初始聚类中心,通过迭代把数据对象划分到不同的簇中,使簇内部对象之间的相似度很大,而簇之间对象的相似度很小。算法中参数k的值是事先给定的,并在数据对象集中随机选取k个数据对象作为初始聚类中心。一些研究[2,3,4,5]指出,如果初始聚类中心选取不当,k-均值算法的聚类结果可能会陷入局部最优解,从而得不到较好的聚类效果,本文的实验也证实了这一点。怎样从这些局部最优中找到一个较好的聚类结果是一个值得研究的问题。
本文对k-均值算法的初始聚类中心选择方法进行了改进,提出了一种从数据对象分布出发动态寻找并确定初始聚类中心的思路以及基于这种思路的改进算法。实验表明,与传统随机选取初始聚类中心的方法相比,改进后的方法有效改善了它的分类性能,并取得了较高的分类准确率。
1 k-均值算法
算法1 k-均值算法
输入:聚类个数k,以及包含n个数据对象的数据样本集;
输出:满足方差最小标准的k个聚类;
步骤:
(1) 从n个数据对象中任意选择k个对象作为初始聚类中心;
(2) 循环执行(3)到(4),直到每个聚类不再发生变化为止;
(3) 根据每个聚类中所有对象的均值(中心对象),计算样本集中每个对象与这些中心对象的距离,并根据最小距离重新对相应对象进行划分;
(4) 重新计算每个(有变化)聚类的均值(中心对象)。
由以上算法可知,k-均值算法的初始聚类中心是随机选定的,其聚类结果受初始聚类中心的选择影响较大。
2 k-均值改进算法的思想
在k-均值算法中,选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率,本文研究的目的就是如何找到与数据在空间分布上尽可能相一致的初始聚类中心。对数据进行划分,最根本的目的是使得一个聚类中的对象是相似的,而不同聚类中的对象是不相似的。如果用距离表示对象之间的相似性程度,相似对象之间的距离比不相似对象之间的距离要小。如果能够寻找到k个初始中心,它们分别代表了相似程度较大的数据集合,那么就找到了与数据在空间分布上相一致的初始聚类中心。
为了找到与数据在空间分布上相一致且相似程度较大的数据集合,采取下列步骤:
(1) 计算数据对象两两之间的距离;
(2) 找出距离最近的两个数据对象,形成一个数据对象集合A1,并将它们从总的数据集合U中删除;
(3) 计算A1中每一个数据对象与数据对象集合U中每一个样本的距离,找出在U中与A1中最近的数据对象,将它并入集合A1并从U中删除,直到A1中的数据对象个数到达一定阈值;
(4) 再从U中找到样本两两间距离最近的两个数据对象构成A2,重复上面的过程,直到形成k个对象集合;
(5) 最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。
假设有一个2维数据集,包含有12个对象,其分布如图1所示。
假设要把它们划分为2类,按照上面的思想寻找初始聚类中心。a、b之间的距离最近,那么选择a、b构成一个数据对象集合A1,并将它们从总的集合U中删除。U中与A1相邻最近的对象是c,这样便将c加入A1集合并将它从U中删除。如果规定每个数据集合中所包含对象最大个数为4,则A1中将会再添加对象d。然后在U中再找出相互之间距离最近的两个对象g、h构成A2并将它们从U中删除。U中与A2相邻最近的对象是i,这样便将i加入A2并将它从U中删除,同样j也会并入A2。最后,将这两个对象集合分别进行算术平均,形成两个初始聚类中心。这样得到的初始聚类中心与实际样本的分布更加相符,从而可以得到更好的聚类效果。
3 基本概念
为便于说明问题,给出如下定义:
定义1 数据对象x=(x1,x2,…,xp)和y=(y1,y2,…,yp)之间的距离为:
定义2 一个数据对象x与一个数据对象集合V之间的距离,定义为这个数据对象与这个数据对象集合中所有数据对象当中最近的距离:
d(x,V)=min(d(x,y),y∈V)
定义3 两个对象集合S和V之间的距离,定义为两个集合S和V中最近的两个数据对象x和y之间的距离:
d(S,V)=min(d(x,y),x∈S,y∈V)
4 改进的初始聚类中心选择算法算法2 初始聚类中心选择算法
假设数据对象集合U有n个数据对象,要将其聚为k类,m的初值为1。算法描述如下:
输入:聚类个数k,包含n个数据对象的数据样本集;
输出:满足方差最小标准的k个聚类;
步骤:
(1) 计算任意两个数据对象间的距离d(x,y),找到集合U中距离最近的两个数据对象,形成集合Am(1≤m≤k),并从集合U中删除这两个对象;
(2) 在U中找到距离集合Am最近的数据对象,将其加入集合Am,并从集合U中删除该对象;
(3) 重复(2)直到集合中的数据对象个数大于等于 a*n/k ( 0<a≤1);
(4) 如果m<k,则m←m+1,再从集合U中找到距离最近的两个数据对象,形成新的集合Am,(1≤m≤k),并从集合U中删除这两个数据对象,返回(2)执行;
(5) 将最终形成的k个集合中的数据对象分别进行算术平均,从而形成k个初始聚类中心。
从这k个初始聚类中心出发,应用k-均值聚类算法形成最终聚类。
5 实验分析
实验环境:P4 CPU,512MB内存,80GB硬盘,Windows 2000操作系统,VC++6.0编程语言。
实验数据:选自UCI数据库中的Iris数据集、Wine数据集和我们自己收集的Web用户数据集HWU1和HWU2。
实验方法:首先采用算法2寻找并确定初始聚类中心;在此基础上再应用算法1形成最终聚类结果。
实验结果:改进算法与随机选取初始聚类中心方法的比较如表1所示。
从表1可以看出:
(1) 随机选取初始聚类中心的方法从不同的初始中心出发会得到不同的聚类结果,聚类准确率有很大的差别,很不稳定,难以确定其是否可用。例如,对Iris数据集,多次随机选择聚类中心,最高准确率可以达到89.33%,最低仅为52.00%;对于HWU2数据集,多次随机选择聚类中心,最高准确率可以达到60.78%,最低仅为50.98%。产生这样结果的原因就是随机选择聚类中心的方法没有考虑到数据的分布情况,而只是给出了一个算法可以运行的必要条件(有初始聚类中心)。
(2) 改进后的算法能够得到较高且稳定的准确率。针对数据集Wine、HWU1可以得到最高准确率的聚类结果,针对数据集Iris、HWU2可以得到接近最高准确率的聚类结果。产生这样结果的原因就是改进后的算法首先根据启发式算法来寻找数据,因而产生的初始聚类中心比较符合数据实际分布,也就更适用于对实际数据的聚类。
6 结束语
本文首先给出了k-均值算法的一般过程,并分析了该算法随机选取初始聚类中心对聚类结果的影响,然后提出了一种从数据对象分布出发寻找初始聚类中心的思想以及基于这种思想的算法过程,并通过实验分析得出改进后的算法能够得到较高且稳定的准确率,更适用于对实际数据的聚类。
参考文献
[1]朱明.数据挖掘[M].合肥:中国科学技术大学出版社,2002.
[2]Kurniawan A,Benech N,Tao Yufei.Towards High-dimensional Cluste-ring[J].COMP,November 1999:1-2.
[3]MacQueen J.Some Methods for Classification and Analysis of Multivari-ate Observations[J].In:Proceedings of 5th Berkeley Symp.Math.Statist,Prob.,1967,1:281-297.
[4]Jolla L.Alternatives to the k-means algorithm that find better clustering[J].In:Proceeding of ACMSIGMOD,1992:192-195.
K均值聚类 篇4
关键词：聚类分析,差分进化,K-均值聚类算法,Laplace分布,Logistic混沌搜索
K-均值算法是由Mac Queen[1]提出的一种经典的聚类分析算法,它具有算法简单且收敛速度快的优点,但是算法的聚类结果易受初始聚类中心影响,且容易陷入局部最优。近年来许多学者利用各种常用智能优化算法(如遗传算法[2,3]、微粒群优化[4]等)对K-均值算法进行改进,并取得了不错的效果。
由Storn和Price提出的差分进化(Differential Evolution,DE)算法[5]是一种基于群体进化的启发式算法。该算法从原始种群开始,通过变异(Mutation)、交叉(Crossover)和选择(Selection)操作来生成新种群,通过计算每个个体的适应度值,来确定个体的保留或淘汰,然后通过不断迭代运算,引导搜索过程向最优解逼近。文献[6-7]利用差分进化对K-均值算法进行改进,结果表明,与基于传统遗传、微粒群优化等常用进化算法的K-均值改进算法比较,基于差分进化的K-均值改进算法能获得更好性能。但是,传统差分进化算法也存在算法收敛速度与全局寻优能力之间的矛盾,进化后期易出现早熟、停滞现象,通过改变控制参数虽然可以提高算法收敛速度,但是也会造成其全局寻优能力的下降,从而使得基于传统差分进化的K-均值改进算法的性能受到一定影响。
针对上述问题,该文提出一种基于改进差分进化的K-均值聚类算法,基本思想是:在差分进化算法中通过引入Laplace变异算子来提高算法收敛速度和全局寻优能力,同时通过引入Logistic变尺度混沌搜索,以克服传统差分进化算法进化后期可能出现的早熟、进化停滞现象;然后将其用来改进K-均值算法。实验结果证明,该算法具有较好的全局寻优能力,且收敛速度较快。
1 聚类的基本数学模型
设样本集合为X={X1,X2,⋯,Xn},其中Xi={xi1,xi2,⋯,xid}为d维特征向量,聚类问题的目的就是要找到一个划分C={C1,C2,⋯,CK},使得最终的聚类结果满足:
且使得聚类准则函数JC取得极小值,JC为各样本到对应聚类中心距离的总和:
其中Zj为第j个聚类中心,d(Xi,Zj)为样本到对应聚类中心点的欧式空间距离。
2 改进差分进化算法
2.1 传统差分进化算法
传统差分进化算法通过种群内个体间的合作与竞争,保存优良个体,淘汰劣质个体,以实现对全局最优解的搜索,其演化过程包括变异、交叉和选择三种基本操作。
假设初始种群为PG={Xi,G|i=1⋯NP},其中Xi,G={xji,G|j=1⋯D}为第G代种群中的第i个个体,D为优化问题的维数,NP为种群规模。
1)变异操作
随机从种群中选择一个个体作为父代基向量,选择另外不同的个体作为父代差分向量,生成变异个体Vi,G,即
其中a≠b≠c≠i∈[1,NP],NP为种群规模,G为当前种群的代数,F为缩放因子。
2)交叉操作
利用式(4)对种群中第i个个体Xi,G和其对应的变异个体Vi,G实施交叉操作,生成新个体Xi,G。
其中Xi,G为均匀分布概率,CR为交叉概率,Xi,G为随机选取的整数。
3)选择操作
将原种群的个体Xi,G和新个体Ui,G代入式(5)进行选择,适应度更优的个体进入下一代。
其中Xi,G+1为下一代的第i个个体,f为适应度函数。
2.2 Laplace变异算子
由文献[8]可知,基于柯西分布的变异算子能使算法的寻优能力得到很好地提高,而基于高斯分布的变异算子又能够较好地加快算法的收敛速度。
三种分布的密度函数曲线如图1所示,其中Laplace分布的密度函数同高斯分布相似,区别在于高斯分布概率密度用相对于均值的平方差表示,而Laplace分布概率密度用相对于均值的差的绝对值表示,其密度函数如下:
图中Laplace分布的尾部平滑度介于高斯和柯西变异算子之间,故可知Laplace变异算子既可以较好地保持种群的多样性,又可以使算法的收敛速度得到提高。
2.3 Logistic变尺度混沌搜索
为了克服DE算法在进化后期可能出现的早熟、进化停滞问题,使算法更好地收敛到全局最优解,该文在进化过程中引入了Logistic变尺度混沌搜索。
首先采用Logistic方程产生混沌序列,并按以下方式进行[0,1]中混沌序列和解空间中点列变换:
1)在[0,1]空间上随机产生一个N维变量z1=(z11,z12,⋯,z1N),其中
z1i≠0.25,0.5,0.75;i=1,2,⋯N,然后根据Logistic映射产生M个混沌序列zk,k=1,2,⋯,M
2)使用如下公式,将zk映射到解空间上M个点列xk=(xk1,xk2,⋯,xk N):
3)同理,根据下式将解空间的某个解xk映射到[0,1]区间进行混沌变换:
为使算法初期可以尽可能扩大搜索范围,而后期又可以尽量进行局部细搜索,改进算法采用了变尺度的混沌搜索。则式(7)变换为:
其中σ为尺度系数,G为当前迭代次数,Gmax为最大迭代次数。
3 基于改进差分进化的K-均值聚类算法
3.1 个体编码
改进算法个体采用基于聚类中心的实数编码方式,假设要求把数据分成k类,数据维数为d,每个个体是有k个聚类中心组成的向量,且每个聚类中心是d维的向量,所以每个个体是k×d维向量
Xi(c11,c12,⋯,c1d,c21,c22,⋯,c2d,⋯,ck1,ck2,⋯,ckd)
其中i=1,2,…,N,N为个体的数量;cj表示第j个聚类中心,cjl是代表第j个聚类中心的第l维的值。
3.2 早熟判断
在差分进化算法中,适应度函数用于判断种群进化过程中个体所在位置的好坏。衡量聚类效果的好坏,取决于Jc的结果,Jc越小聚类效果越好。所以,该文定义适应度函数如下:f(Xi)=Jc,同时引入早熟判断规则如公式(11)所示。
其中fi为当前个体适应度,fworst为当前最差个体适应度,fbest为当前最好个体适应度,pi随着迭代的进行将逐渐减小。该文设定一阈值,如果低于该阈值且不满足终止条件时,则认为该个体处于停滞状态。
3.3 算法步骤
步骤1:设定个体数N,最大迭代次数Gmax。
步骤2:种群的初始化:随机选取样本作为聚类中心,并计算当前位置适应度值。
步骤3:对于个体Xi,G按3.2描述产生变异算子F。
步骤4:分别根据式(3)执行变异操作,根据式(4)执行交叉操作,生成试验向量Uki,G,根据式(5)执行选择操作。
步骤5:根据个体的聚类中心编码,按照最近邻法则重新划分样本的归属类别。
步骤6:重新计算新的聚类中心,以替代原值。
步骤7:由式(11)判断是否陷入局部最优,若是,则对该个体变尺度混沌搜索,以利于跳出局部最优,转到步骤3。
步骤8:如不满足所设的终止条件,则转到步骤3,同时G的值自增1;否则输出最好个体值Xbest及最好适应度值f(Xbest),算法结束。
4 实验及效果评价
实验分别采用Iris、Wine和Zoo这3个知名数据集作为测试样本集,参数设置如下:种群规模为数据集维数的10倍,最大迭代次数Gmax为50次。其中DE-kmeans算法[6,7]中缩放因子F为0.5,交叉概率CR为0.1;本文算法中缩放因子F为Laplace随机数,交叉概率CR为0.1,阈值σ为0.8。对三种算法单独运行50次,根据适应度函数分别计算出最小值、最大值、平均值以及收敛到最优值所需要的时间。运行结果如表1所示。
从表1可以看出,K-均值算法虽然收敛速度最快,但因初始聚类中心的不同产生的最小适应度值和最大适应度值的差距较大且寻优精度最差;DE-kmeans的适应度相对稳定,但其收敛所消耗的时间较长;而本文所提算法的结果更加稳定,寻优精度更好,且收敛速度也较快。
5 结束语
本文首先在传统差分进化算法中引入Laplace变异算子和Logistic变尺度混沌搜索以提高其性能,然后将改进的差分进化算法应用于K-均值算法。实验结果表明:该文算法较好地克服了传统K-均值算法的缺点,具有较强的全局搜索能力,且收敛速度较快。
参考文献
[1]MacQueen J.Some methods for classification and analysis of multi-variate observations[C]//Proc.of the 5th Berkeley Symposium onMathematics Statistic Problem,1967,1:281-297.
[2]王家耀,张雪萍,周海燕.一个用于空间聚类分析的遗传K-均值算法[J].计算机工程,2006,32(3):188-190.
[3]Michael Laszlo,Sumitra Mukherjee.A genetic algorithm that exchanges neighboring centers for k-means clustering[J].Pattern Recogni tion Letters,2007,28(16):2359-2366.
[4]Omran M G H,Engelbrecht A P,Salman A.Dynamic clustering using particle swarm optimization with application in unsupervisedimage classification[J].Proceedings of World Academy of Science,Engineering and Technology,2005,9(11):199-204.
[5]Storn R,Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Journal ofGlobal Optimization,1997,11(4):341-359.
[6]Paterlini S,Krink T.High performance clustering with differential evolution[C]//Proc.of Congress on Evolutionary Computation,2004,2:2004-2011.
[7]Sudhakar G.Effective image clustering with differential evolution technique[J].International Journal of Computer and CommunicationTechnology,2010,2(1):11-19.
[8]Kuo-Tong Lan,Chun-Hsiung Lan.Notes on the distinction of Gaussian and Cauchy mutations[C]//Proc.of Eighth International Con ference on Intelligent Systems Design and Applications,2008:272-277.
[9]刘兴阳,毛力.基于Laplace分布变异的改进差分进化算法[J].计算机应用,2011,29(10):2719-2722.
[10]沈明明,毛力.融合K-调和均值的混沌粒子群聚类算法[J].计算机工程与应用,2011,47(27):144-146.
[11]张济强,高玉良.遗传模拟退火算法在k-means聚类中的应用[J].电脑知识与技术,2012,8(7):1611-1613.
K均值聚类 篇5
关键词：车牌识别,车牌定位,K-均值,聚类,字符识别
机动车号牌识别系统主要功能是通过图像采集和图像识别的手段识别机动车的身份。对车牌识别领域的研究最初起源于二十世纪九十年代的发达国家, 而国内的研究起源于二十世纪末。号牌识别的最主要的步骤是:车牌定位、字符分割和字符识别。而后两者现在基本已经达成共识, 字符分割采用对二值化图片进行垂直投影和水平投影, 字符识别使用模板匹配方法或者SVM方式。最重要而且方案最多样化的步骤还是在车牌定位上。
车牌定位基本可以分为三种大的研究方向:对灰度图像进行边缘检测、对灰度图像进行角点检测和对彩色图像进行颜色模型处理。边缘特征是人类视觉感知的重要来源, 文献将边缘检测理论、形态学填充、腐蚀开运算后得到车牌待选区域, 最后分析获取车牌位置, 边缘检测作为研究范围最广和目前大多数产品使用的技术, 的确具有速度快、准确率较高的特点, 尽管现有的边缘检测算子十分成熟, 但是没有一种适应于任何图像质量、任何图形环境的边缘提取方法, 而且为了得到高识别率, 对于每幅图像要选用合适的边缘检测算子。文献将彩色图像转换到HSV颜色空间中对色彩进行分层处理是车牌定位彩色图像处理方向较新颖的方法, 但是这类方法的缺点也是很明显的, 当车身颜色与牌照颜色相近时, 辨识就变的几乎不可能了。文献提出了角点检测法, 因为角点代表的特征像素点占图像像素总数的百分之一, 却构成物体大部分的外形要素, 由于牌照的字符部分角点数较多, 所以作者使用Harris算法获取整幅图像的所有角点, 然后使用一个固定大小的滑窗去遍历图中的角点以得到牌照待选区域。通过角点获取牌照区域受干扰小, 识别的效率也比较高, 是应该深入研究的方向。
1 车牌标准分析
现行的《中华人民共和国公共安全行业标准——中华人民共和国机动车号牌》 (GA36-2007) , 于2007年9月28日发布, 同年11月1日实施, 用来代替原来的国标GA36-1992。按照GA36-2007的标准, 为了我们计算机识别的方便, 我重新整理从号牌行数和号牌特征着手归纳, 见表1。
经过归类并简化后, 很大程度上避免了排列方式对识别算法的干扰, 在字符分割阶段对车牌进行横向投影分析号牌分类是单行牌照还是双行牌照, 并根据上表优化算法, 可以达到快速准确的目的, 见图1。
下面从典型的单行牌照, 分析其字符规律。牌照中的字符分为三段:第一个字符是省、自治区或者直辖市的简称, 确定为汉字字符;第二个字符是发牌机关代号, 是大写的英文字母;第三至第七个字符为序号, 通常为大写英文字符和阿拉伯数字字符的排列, 对于特别号段的车辆会在末位字符出现“警”“领”“学”“临”“试”“港”“澳”等汉字字符。
典型的双行牌照, 见图2。双行牌照第一行就是单行牌照分割点前的两个字符, 第二行是单行牌照的第三位到第七位。双行牌照和单行牌照相比, 长宽比更小。
从颜色方面看, 无论是单行的牌照还是双行的牌照, 都有多种颜色的排列组合。但是归纳来说, 牌照背景颜色和牌照字体颜色的组合一共是四种, 分别是:黄底黑字、蓝底白字、黑底白字、白底黑字。特殊分类的字符颜色为红色, 而且特殊字符不会出现在蓝底背景的牌照上面。
2 原始K-均值算法
用Harris角点检测算法运算后的图像, 通过观察可以发现“牌照区域肯定是角点聚集的区域, 但是角点聚集的区域不一定是牌照所在区域”, 需要使用一个聚类分析方法来找到若干个角点聚集区域, 然后通过对区域特征的筛选, 最终决定牌照位置。K-均值算法是一种得到了广泛使用的基于划分的聚类算法, 算法把n个数据点按照目标函数分为k个簇, 以使簇内数据点具有较高的相似度, 而这个目标函数可以是欧氏距离。K-均值算法满足了希望把n个角点以欧氏距离分为k个号牌待选区域的思想, 而且它的时间复杂度是O (tkn) , t是迭代次数, 所以对图3 (a) 上由Harris算法得到的角点执行K-均值算法, 经t次迭代得到k个簇, 见图3。
3 改进K-均值算法
使用原始K-均值算法并不能在每次收敛后都得到牌照正确的区域 (见图4) , 因为其算法本身是用于数据挖掘的, 算法中初始点是随机决定的, 目标函数使用的是欧氏距离, 为适应号牌识别的效率和识别率双重的要求, 需要对其修改。在这个过程中, 参考了文献, 但是考虑到文中AP算法的时间复杂度高, 所以还是用K-均值算法。
首先从算法的随机取初始点着手, 通过实验发现初始随机点选择的结果不同, 收敛后的簇是可能不一致的, 所以尽量要选择一种既能接近最终收敛簇的形心, 又能是一种快速稳定的初始点提取算法。研究后决定用分冶思想把图像分成若干个矩形区域, 算法1的步骤如下:
步骤2, 遍历Ci, 2这张存放了角点的二维表, , 1/ij=C×M W, k Ci, 2N/H=×, Aj, kAj, k1=+。
步骤3, 设值max, 遍历Aj, k, 当Aj-1, k, Aj+1, k, Aj, k-1, Aj, k+1均未被访问过时, max=Aj, k, 并标记Aj, k为已访问过。
步骤4, 循环到步骤3, 所有的初始点都选出为止。
第二点的改进是传统的K-均值聚类时使用的欧氏距离, 而牌照的规格不是圆, 需要使用标准化的欧氏距离公式。两个n维向量a (x11, x12, ..., x1n) 与
b (x21, x22, ..., x2n) 间的标准化欧氏距离公式为:
其中ks是分量的标准差, 对于最常见的440mm×140mm的机动车牌照上二维的角点数据, 公式可以推导为
于是整个号牌定位的算法可以这样描述:
步骤1, 使用FAST角点算法获取图中角点。
步骤2, 使用算法1提取K-均值的初始点。
步骤3, 以计算出的中心点执行K-均值算法。
步骤4, 修改K-均值算法使用公式1。
步骤5, 在聚类后获取的簇所组成的矩形中, 根据车牌标准, 删除以下情况:高要比宽大;宽大于高的3.5倍;宽小于高的2倍;号牌颜色面积小于总面积50%。
执行上述算法后得到图5, 其中左边一张是通过上述算法得到的初始点, 右图是通过初始点再调用K-均值算法得到最终的角点分类后各个区域的中心, 从中可以发现初始点已经很接近最终的收敛结果, 所以这种算法可以大大的加快K-均值算法迭代的速度, 而且使得K-均值算法的执行速度是快速的, 结果是稳定的。
4 算法效率实验
测试数据集的描述:本文采用从网上随机选取的二十七张车辆正面图片作为样本来验证改进后的算法的效率。通过FAST角点检测, 其中每张图产生一千个以下的角点。
算法对比:分别用传统K-均值算法、滑窗定位法和改进过的K-均值算法分别对样本图片的角点进行聚类, 分别从平均识别速度和平均识别率两个方面进行对比, 见表2。
表2是对三种不同聚类算法的实验结果的汇总, 给出了具体量化的数据, 通过表2可看出传统K-均值算法由于迭代次数多而收敛速度慢, 并且识别率低。而改进后的K-均值算法虽然算法复杂但是由于迭代过程的改进使得识别速度和平均识别率都得到了很好的平衡。
5 车牌字符分割算法研究
本章节将讨论车牌字符分割问题。车牌字符的分割是车辆号牌识别流程中承上启下的环节, 主要是继续前章车牌定位的工作结果, 主要任务是从一张车牌图像中准确可靠的分割得到各个字符并完成归一化的工作, 提供给下面字符识别环节来进行分析。
由于机动车牌照存在单行车牌和双行车牌, 所以进行列分割之前要首先进行判断。通过分析车牌区域的水平投影图的形态就可以知道, 见图7。
因为车牌尺寸不同, 必须对它进行归一操作:将牌照灰度图缩放到100×50像素, 计算各行中段约25%~75%的区域, 在这个区域中搜索灰度值最小点, 若该点在接近1/3处, 该号牌就是双行车牌, 否则是单行车牌。下面介绍用列分割方法把单行车牌进行字符分割。首先对车牌定位后的图像进行二值化操作 (临界灰度值是160) , 这样得到的二值化图像减少了光照不均的影响。然后对单行车牌区域的二值化图像做垂直投影, 见图8。
然后通过下列的步骤实现字符分割, 其中投影图为P。
步骤1:令max P=MAX (P) , 得到投影图中的最值。
步骤2:寻找N中的0值点, 以0值点将N分为若干块:recti, i=1, 2, 3, ...。
步骤4:各块宽度为width=imax (recti) -min (recti) 。宽度中值为media Width。将widthi<media Width×1.2的块就近合并。
步骤5:若recti的宽度大于两倍中值宽度, 按中点将其分拆成两块。
步骤6:重复步骤4和5, 直到无合并或拆分操作为止。
步骤7:如果块宽度小于各块平均宽度, 以该块中心左右往外media Width2作为分割点;否则以该块左右边界为分割点。
步骤8:按照分割点分割图像, 按照各分割块的左右次序对其编号。
步骤9:分析各块底色 (二值化图像为0的点) 的平均色度值, 将其和车牌区域底色比较, 删除误差超过50%的块。
这样就把字符从定位好的牌照图像中分离出来了, 见图9。
6 车牌字符分割识别研究
支持向量机来识别号牌字符, 利用其良好的分类能力, 可以用来对字符进行分类, 有很高的字符识别率。
1992年开始在统计学习理论领域发展了一种称为支持向量机 (Support Vector Machine, SVM) 的新的模式识别方法, 在解决小样本、非线性及高维模式识别的问题中表现出很好的性能。由于同时神经网络遇到了网络结构固定、过学习和欠学习问题, 所以支持向量机方法成了机器学习领域内新的热点。
SVM方法从线性可分的最优分类面 (Optimal Hyper-plane) 提出了二类分类技术。它通过构造最优超平面使得不同样本类的距离最大化。
yi[ (wixi) +b]-1≥0, i=1, 2, ..., n就得到了最优的分类面。表述成约束优化问题就是在 (l) d的条件下, 求方程
对w和b偏微分并使之等于0, 得到对偶问题
在线性不可分情况下, 增加了松弛项ξi≥0, 分类条件方程变成:
所谓SVM的训练, 就是通过已有的样本, 求得支撑最优分类面的样本向量。由于SVM自身的特点, 相对于识别的样本, 只需要少量样本进行训练。这一点就满足车牌字符识别系统的要求。同时, 如果把整个字符作为输入数据, 输入样本就具有高维度的特征, 这要求分类器能够进行高效的高维度数据分类能力, 这也是SVM的优势所在。鉴于以上这些原因, 构造了用于车牌字符识别的支持向量机, 并使用大量实际数据效验所设计方法的有效性。训练中从100多张尺寸为800×600的各类机动车照片中分割出700多张字符照片, 其中某种字符的照片数是大于1的, 按照字符分类, 每种字符抽取一张, 一共71张字符照片, 手动选定字符系统自动对其进行缩放操作, 统一成32×16像素的图片, 然后再进行灰度化操作和二值化操作 (通过实验二值化的阀值定为灰度值160) , 这样每个字符照片所包含的信息量是相同的。实验中使用的支持向量机是由台湾林智仁教授开发的libsvm, 由于Objective-C是向下支持C语言的, 所以libsvm (C语言版) 是可以直接用于Objective-C开发的, 见图10。使用svm_train来进行训练。
识别的步骤和训练的步骤是相似的。对于从字符分割后的字母/数字图片, 首先进行灰度化和二值化处理 (二值化的阀值定为灰度值160) , 这样把产生的二进制数值作为一个svm节点, 加载SVM自识别系统在磁盘上的识别模型, 返回识别的结果。
7 号牌识别应用
最后在一台联想Think Pad T430上, 安装了Mac OS Mountain Lion (10.8.5) X64位操作系统和Xcode编程开发软件, 并把APP运行在一台i Phone 4 (操作系统IOS7.1.2) 上实现了号牌识别的全部功能, 见图11。
经过号牌定位、字符分割和字符识别三大步骤后, 实验在真机上的运行效果如图10所示。
8 结语
针对车牌定位这个难点问题, 本文将K-均值算法用于号牌识别的算法并进行了优化, 首先提出用分冶思想用于K-均值算法的初始点选取;然后对K-均值算法得到的结果, 也就是号牌候选区域进行筛选, 结合形状和颜色等因素来最后精确定位车牌, 这样既提高了算法的收敛速度, 又增加了算法的准确性。经IOS平台上实现的整个号牌识别程序实验结果, 证明改进后的号牌定位算法提高了识别率, 成效显著。
参考文献
[1]王晓雪, 苏杏丽.数字图像处理在车牌识别中的应用[J].自动化仪表, 2010, 31 (7) :22.
[2]迟晓君.一种基于支持向量机的车牌字符识别方法[J].信息技术与信息化, 2007, (6) :
K均值聚类 篇6
聚类分析是一种广泛使用的数据分析方法,一直被应用于多个领域,特别是在机器学习、数据挖掘、模式识别、图像处理等领域应用十分广泛。在所有的聚类分析算法中,K-means是最经典且使用最为广泛的一种算法,它是基于划分的原理,且算法过程简单快捷,容易实现。但是K-means算法也有两个主要的缺陷,对初始聚类中心的敏感以及容易陷入局部最优解。因此,针对上述缺陷很多文献不断提出改进方法,由Zhang[1]提出的K-调和均值KHM(K-harmonic means)算法能够有效解决对初始值敏感的问题。
由于KHM与K-均值仍然具有陷入局部最优的问题,一些启发式进化算法被用于与其组合而获得新的混合算法,以充分利用其全局搜索能力,现已成为对KHM的研究工作中最常用的方法。目前,融合粒子群算法PSO的PSOKHM[2]是较为经典的混合算法。随后,结合蚁群优化算法[3]、变邻域搜索算法[4]以及其改进版本[5]、候选组搜索算法[6]、帝国主义竞争算法[7]等相继被提出,然而它们并未直接与PSOKHM进行对比,并依据相应的实验结果可将它们看作为相近的研究工作。近来,由Bouyer等[8]提出一种结合改进PSO的混合算法KHM-MPSO能够获得比PSOKHM更准确且更具鲁棒性的聚类结果,其中利用了布谷鸟搜索算法的levy飞行策略进一步提高全局搜索能力。然而,这些混合聚类算法结合启发式算法进行搜索的策略均增加了时间复杂度,从而影响了计算效率,在这方面的改进值得进一步研究。此外,一些学者将模糊策略引入到KHM进行改进,使其具有软划分性能,如基于模糊KHM的谱聚类算法[9]以及其在单词-文档中的应用[10]。近来,Wu等[11]利用概率C均值的原理提出一种新颖的混合模糊K调和均值HFKHM(hybrid fuzzy K-harmonic means)聚类算法,能够有效解决对噪声敏感的问题。在上述的各种KHM算法中,均将数据的所有属性看作相等的作用进行距离度量,具有一定的局限性。由Huang等[12]提出一种自动变量加权型的W-k-means算法,它能够在聚类过程中度量不同属性的重要性,从而自动调整其权重使得更重要的属性具有相对较大的权重值。目前,基于属性加权的聚类算法已得到十分广泛的关注,被用于对各种算法进行改进[13,14,15,16,17],而尚未有关结合KHM的相关研究。
本文中首次将属性权重引入到KHM算法的距离度量中提出一种加权K-调和均值聚类算法WKHM(weight K-harmonic means),考虑不同属性对聚类的影响,并且在算法迭代过程中自动更新其权重。此外,为了进行更全面的分析,将WKHM与PSO相结合获得混合加权聚类算法PSOWKHM,并且与PSOKHM不同的是其将属性权重与类中心坐标相结合来表示每个粒子群个体。实验结果表明,本文算法能够有效提高聚类精度,具有较高的稳定性。
1 算法基本原理
1.1 K-调和均值聚类及其改进算法
K-调和均值算法的原理基本上与K均值是相似的,不同的是其使用调和均值HM(harmonic means)代替算术均值来计算目标函数。由于HM具有最小化群体内的偏差以及最大化群体间的偏差的特性,因此KHM能够有效克服对初始中心点敏感的问题。若数据集X=(x1,…,x2,…,xn),xi=(x1i,…,xqi)为空间Rq上的N个数据,将其划分为k个聚类簇,且每个聚类的中心用cj表示。根据文献,K-调和均值的目标函数为[1]:
这里采用欧氏距离计算数据xi到聚类中心的cj的距离,即dij=‖xi-cj‖,p是一个输入参数,对算法的性能具有重要的影响,研究发现当p≥2时聚类的效果比较好[1]。聚类过程通过迭代使得目标函数值不断减小并保持稳定,直至结束运行。每次迭代中,各个聚类簇的中心点cj(j=1,2,…,k)的更新如下所示:
其中,成员函数和权重函数wKHM(xi)的定义分别为式(3)和式(4),以最大的mKHM值确定每个数据的所属类别。
在上文提到KHM具有易陷于局部最优的缺陷,因此融入群智能算法能够有效改善其性能,考虑到相关的改进算法较为相近,这里仅介绍最具有代表性的PSOKHM。由于PSO是一种被广泛研究的群智能优化算法,对于其具体原理本文不再详细介绍,可参考文献[2,8]了解。若k为聚类数,m为数据的维数,则一个粒子可表示为一个k×m列的一维实数向量,如图1所示。并且,PSOKHM的适应度函数即为KHM的目标函数。
PSOKHM的具体过程如下所示[2]:
1)设置算法的基本参数,包括最大迭代次数Iter Count,种群规模Psize,PSO的惯性权重因子w以及加速度因子c1和c2。
2)初始化Psize个粒子的位置,并设置迭代次数Gen1=0。
3)执行PSO算法进行搜索,迭代运行Gen2次后输出当前最优解,进入下一步操作。
4)以当前最优粒子的位置作为聚类中心执行KHM算法,迭代运行Gen3次,获得新的聚类中心作为粒子的位置。
5)Gen1=Gen1+1,若Gen1<Iter Count,则转到步骤(3)继续执行,否则停止迭代得出聚类结果。
其中,文献[2]给出步骤2和步骤3中迭代次数Gen2和Gen3的取值分别分别为8和4,且文献[8]的KHM–MPSO中采用了同样的取值。然而,原文中均未给出确定这些迭代数的细节,可认为其为作者结合实验选用的值,能够满足绝大多数情况。
1.2 自动加权K均值
W-K-means算法是对K-means的拓展,将加权相异性度量引入到目标函数中,用wq(q=1,2,…,d)表示各维属性权重并通过指数参数β进一步控制其重要性,改进的目标函数为[12]:
每次迭代过程中,属性权重的更新如下所示:
其中,且h为Dq≠0的个数。
2 自动属性加权的K-调和均值聚类
2.1 属性加权K-调和均值算法
根据式(5)可见,属性权重引入了一个新的指数参数β,其对算法的性能具有比较重要的影响,对于不同数据集的最佳β值难以确定。考虑到KHM的距离度量已具有指数参数p,本文算法中未直接采用W-K-means的属性加权方式,而是采用加权欧氏距离dij(w)计算样本与类中心的距离。各属性权重同样用wq(q=1,2,…,m)表示,则WKHM算法的目标函数如下式所示:
其中,
由于聚类过程是通过最小化目标函数进行,可将WKHM视为一种优化问题,即为:
式(8)可通过格朗日乘法求解,函数表达式L可以表示为:
其中λ为拉格朗日系数。
算法中包含聚类中心和属性权重这两个决策变量,需推导出它们的更新公式使得L始终能够收敛到一个局部最小值。首先求出L关于类中心cj(j=1,2,…,K)的偏导并使其为0:
由于
求出L关于wq(q=1,2,…,m)的偏导并使其为0,进而获得关于属性权重的计算式,如下所示:
结合式(12)以及式(8)中属性权重的约束条件即可求出λ的计算式,然后再代入到式(12)中即可获得属性权重最终的更新公式为:
此外,为了防止在属性权重计算时出现分母为0的情况,这里引入一个很小的常数ε,将式(13)中的距离计算改为D'iq=Diq+ε,本文中ε的取值为0.001,且其值远小于相应的距离,不会影响算法的收敛性能。
综上可得,WKHM聚类算法的具体流程为:
Step1初始化算法的基本参数,随机选取样本点并作较小的扰动作为初始的聚类中心。
Step2根据式(8)计算目标函数的值。
Step3根据式(3)和式(4)以及加权欧氏距离dij(w)计算成员函数和权重函数wKHM(xi)。
Step4根据式(2)计算新的聚类中心。
Step5根据式(13)计算新的属性权重。
Step6若达到最大迭代次数或者目标函数不发生明显变化则停止;否则,转Step2继续迭代运行。
Step7以的最大值将数据xi分配到聚类j中。
2.2 融合粒子群算法的属性加权K-调和均值聚类
尽管通过引入属性加权改进的距离度量能够在一定程度上提高算法的性能,但其仍然存在易陷于局部最优的问题,因此本文同样将PSO融入WKHM中提出与PSOKHM相对应的混合聚类算法PSOWKHM。需要注意的是,由于不同的粒子代表不同的聚类中心和属性权重,这里用一个(k+1)×m列的一维实数向量来表示一个粒子,表示形式与图1相似,只不过在最后增加了m列,即前k×m列为k个类中心的坐标,最后m列为属性权重的值。PSOWKHM的过程与PSOKHM基本一致,相关的参数设置均与其保持一致,这里不再作具体介绍,它们的主要不同之处包括两点:①在PSOKHM的步骤2中增加了每个属性权重的初始化,且初始时每个属性的取值相等,即(q=1,2,…,m);②在步骤4中迭代运行Gen3次WKHM算法更新聚类中心以作为新的粒子位置。
上述聚类算法在迭代过程中的时间复杂度主要依赖于距离的计算,且dij和dij(w)的计算复杂度均为O(knm),其中相应变量的含义均与上文相同。因此,KHM与WKHM的时间复杂度均为O(Gen3·knm),即混合聚类算法步骤4的时间复杂度,步骤3的时间复杂度为O(Gen2·Psize·knm),由于Gen3<Gen2·Psize,故两种混合聚类算法的时间复杂度主要依赖于步骤4,均为O(Iter Count·Gen2·Psize·knm)。
3 实验与分析
3.1 实验数据以及评估标准
为了验证本文算法的有效性和可行性,选取了UCI数据库中比较常用的6个数据集对各算法的聚类性能进行测试,它们的具体特性如表1所示。
本文中通过两个常用的度量指标RI(rand index)和NMI(normalized mutual information)对聚类结果进行评估和比较分析。假定数据集真实的聚类为T,算法获得的聚类结果为C。令a、b、c、d分别表示同时属于T和C的相同类,属于T的相同类但是属于C的不同类,属于C的相同类但是属于T的不同类,以及同时属于T和C的不同类的数据的个数。则RI的计算公式如下所示:
NMI指标采用信息论中的熵计算每个真实的类与每个聚类结果的簇之间的平均互信息,若ni为类i中数据点的个数,nj为簇j中数据点的个数,nij为同时在类i和簇j中的数据点得个数,则NMI的计算公式为:
它们的值均在0到1之间,且越大则表明聚类结果越好。此外,由于距离度量中属性加权的作用,WKHM目标函数的值相比KHM小很多,这里不对其进行比较。
3.2 实验结果与分析
为了分析算法的聚类性能,本文分别对KHM、WKHM、PSOKHM以及WPSOKHM进行对比分析。实验通过MAT-LAB2010b编程运行,计算机的硬件配置为:Intel Core P7450、CPU 2.13 GHz、2 GB RAM。各算法的参数设置为:KHM和WKHM的最大迭代次数Maxgen=100;PSOKHM的参数采用文献[3]中的Psize=18,w=0.7298,c1=c2=1.496,总迭代次数Iter Count=5,且Gen1=8,需要注意文献[2]中数据集的复杂度相对较低,Gen2=4已无法满足求解要求,因此本文中为Gen2=10。分别取p=2.5、3、3.5时对聚类结果进行比较,每种算法独立运行20次,计算RI、NMI和运行时间的平均值,且为了进一步分析算法的稳定性,计算出RI和NMI的标准差记录至括号内,实验结果分别为表2至表4中所示。
首先,根据表2至表4可以看出,在大多数情况下WKHM算法相对于KHM具有明显的提升,验证了采用加权欧氏距离对算法进行改进的可行性。尽管NMI指标的趋势与RI指标基本一致,但仍存在少数不一致的情况,比如在表3中PSOWKHM的RI值高于KHM,NMI值低于KHM,这表明采用多个指标进行对比分析的必要性。为进一步分析,以p=2.5时为例,根据表2中各算法的RI指标可见,WKHM算法对6种数据集分别提升了6.93%、4.06%、9.83%、26.88%、4.24%、2.67%。而PSOKHM算法对数据集Iris、Ionosphere、Australian的RI值均与KHM相同且标准差为0;对数据集WDBC的RI值取得了微弱的提升;仅对于数据集Vehicle和Satellite的RI值获得了相对较明显的提升,分别比KHM提高了1.79%、1.70%,但仍低于WKHM算法的改善效果。因此,可以看出现有的相关文献主要关注于将智能优化算法融入KHM中以克服局部最优的问题而忽略了对算法原理的进一步改进,具有一定的局限性,无法获得更好的聚类性能。并且,本文中同样将PSO融入WKHM算法中,以同时利用了属性权重的改进和智能算法全局搜索的优势。其中,对于数据集Iris、Ionosphere和Vehicle,PSOWKHM的RI值相对于WKHM没有明显变化,而对于数据集WDBC、Australian和Satellite提高了1.93%、3.58%、1.18%,可见算法性能得到了进一步的提高。此外,值得注意的是表2中除数据集Satellite,KHM算法对其他数据的聚类指标值的标准差均为0,有效验证了其对初始聚类中心不敏感。由于KHM算法中p(通常p≥2)的选取对其性能具有一定的影响,本文中分别选取大多数文献中采用的2.5、3.0和3.5进行分析。可见,KHM对于数据集Iris、Ionosphere和Australian而言,p的选取对算法的性能的影响不是很明显,而对于数据集WDBC、Vehicle和Satellite则相对较为明显。WKHM同样存在对参数p敏感的问题,在某种程度上可能更明显,比如WKHM对于WDBC和Vehicle在2.5和p=3.0时的性能均优于KHM,而在3.5时比后者更差。为了更直观分析,图2给出WKHM以及PSOWKHM取不同p值时对各数据集的RI指标值,其中横坐标的1~6分别表示数据集Iris、Ionosphere、WDBC、Australian、Vehicle、Satallite。由图中可见,WKHM和PSOWKHM在p=2.5和p=3.0时对各数据集的性能均较为接近,而在p=3.5时对一些数据集出现了明显的下降。此外,图2中(a)显示WKHM对于Vehicle在p=3.5出现骤降,而(b)显示PSOWKHM对于Vehicle在p=3.5并没有明显下降,表明融入PSO后有效抑制了陷入局部最优的问题。综合分析,本文取p值在[2,3]内可使得改进算法对各数据集能获得比较满意的结果,并且由(b)中可见PSOWKHM在p=2.5时相对于p=3.0时具有较小程度的优势。
由表2-表4中各算法的平均运行时间可见,WKHM较KHM的时间有较小的增加,这是由于增加了属性权重的计算过程,其中WKHM对Satellite的运行时间更短是由于其提前终止使总迭代次数更小。两种混合聚类算法较原算法的平均运行时间均具有较大的增加,特别是对样本数较大的Satellite数据集的运行时间比较长,这是由于PSO执行全局搜索需要较大的时间开销。然而,在步骤2中若PSO始终执行Gen2次迭代可能会增加不必要的计算开销,因此这里采用一个较小的阈值ε=10^(-4)判断是否终止。在PSO优化过程中,计算第t次迭代最优解的适应度值fbest(t)与前一次迭代最优解的适应度值fbest(t-1)的差值,当满足fbest(t)-fbest(t-1)<ε时停止PSO迭代,输出当前最优解并继续执行步骤3。这里以较大的数据集Satellite进行分析,采用阈值ε判断终止的实验结果如表5所示。可见,设定阈值后PSOWKHM对Satellite的性能并没有下降,而运行时间减少了很多,从而有效提高了算法的运行效率。
尽管如此,融入PSO的混合聚类算法在时间性能方面仍处于劣势,因此对于WKHM和PSOWKHM可根据具体问题进行选取。考虑到WKHM较后者的聚类性能并没有较明显的降低而在时间效率方面具有明显的优势,一般情况下可优先采用,若对于聚类准确度要求较高时则可选用PSOWKHM,以降低算法陷入局部最优的可能性。
4 结语
由于KHM算法在聚类过程中将所有权重的作用视为相等而具有一定的局限性,本文利用属性加权欧氏距离提出一种改进的WKHM算法,且在聚类过程中自动更新属性权重。并且,为了进一步提高算法的聚类性能,将其与PSO相结合获得新的混合聚类算法。实验结果有效验证了改进算法的可行性,对各数据集的性能均具有较为明显的改善。考虑到不同属性对不同类的聚类作用也存在差异,而若将向量加权欧氏距离改为矩阵加权欧氏距离则会增加算法推导的复杂性,后续将继续研究将软子空间的原理引入到KHM中,以期进一步提升算法的性能。
摘要：针对K-调和均值算法中距离度量将所有属性视为相等重要而存在的不足,提出一种利用自动属性加权的改进聚类算法。在算法的目标函数中,用加权欧氏距离替代传统的欧氏距离,并证明了使得算法能够收敛的属性权重更新机制。为进一步提高聚类性能,将粒子群算法融入到改进的属性加权聚类算法中以抑制其陷于局部最优,其中采用聚类中心和属性权重的值同时表示粒子的位置进行寻优。在UCI数据集的测试结果表明,该算法的聚类指标平均提高了约9个百分点,具有更高的聚类准确性和稳定性。
K均值聚类 篇7
聚类分析[1]是模式识别和数据压缩领域中一种重要的非监督学习过程,其目的是将若干特征相似的特征模式划分到一个集合,每个集合的特征模式之间按照某种度量来衡量相似程度,使得同一个集合内的数据对象具有较高的相似度,而不同集合中的数据对象间的相似度尽可能小,数据对象间特性差异的大小通常是借助于某一距离空间中的距离概念来刻划的。在现有的聚类算法中,K-均值算法以其简单和高效占有重要地位[2]。但因K-均值算法在寻找聚类中心的过程中采用了启发式方法,使得该算法对初始聚类中心的选择较为敏感,易于陷入局部最优解。尤其在大矢量空间中,这种算法的性能会变得更差[3,4]。美国Holland教授于1975年提出了一种全局优化自适应概率搜索算法—遗传算法(GA)[5,6]。该算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法,具有较强的鲁棒性和全局寻优的能力,但基于遗传的K均值算法(GA-K均值算法)存在前期过早收敛而后期收敛慢的缺点[7]。本文借助免疫机制的优点[8],将免疫原理的选择操作机制引入遗传算法中,提出基于改进遗传算法的K-均值聚类算法。该算法结合K-均值算法的高效性和局部搜索能力,以及改进遗传算法的全局优化能力,达到了较好的聚类效果。
1 基于改进遗传算法的K-均值聚类算法
遗传算法在解决实际问题时,目标函数和约束条件作为抗原输入,随机产生初始抗体群,并通过一系列遗传操作及个体浓度的计算,在保持抗体多样性的情况下找出针对该抗原的抗体。本研究借助免疫机制来调整选择概率,以优化初始聚类中心,同时,在种群进化过程中,自适应动态调节交叉概率和变异概率,避免了早熟现象的发生。具体步骤如下:
1.1 染色体编码及种群初始化
染色体编码有很多方式,聚类分析中常用的是基于聚类中心的浮点数编码和基于聚类划分的整数编码。根据聚类样本的高维性和数量大的特点,本文采用浮点数编码。初始种群的产生采用随机生成,方法为:假设随机从样本空间中选K个样本作为聚类中心,其它样本随机分到这K个聚类中,并计算各个聚类的聚类中心作为初始个体的染色体编码,最后增加一位该个体所对应的适应度,即1条染色体可以用长度为(K+1)个基因位组成的浮点码串S=Z1Z2…Zkf表示,重复进行psize次(psize为种群大小),得到初始种群。
1.2 染色体适应度的选取
根据染色体的构成,采用的适应度函数为
上式中:k为聚类类别数;是簇内距离;是簇间距离。,计算公式分别为
上式中:xi表示类簇Ij中的样本;cj表示类簇j的中心。这样定义考虑了簇内聚类最小的原则。
上式中:ci,cj分别为簇i,j的中心。这样定义考虑了簇间距离最大的原则。
适应度函数受3个因素影响,即1/k,E1/Ek及。第一个因素减少的时候,另外两个因素随着k的增加而增加,所以这个适应度函数表达的内涵是在所分类别数尽可能小的情况下提高聚类的紧凑度和分离程度。
1.3 选择操作
针对基于遗传算法的聚类算法在算法开始前期收敛速度快,而后期由于各条染色体的个体差异变小使收敛速度变得很慢,本研究采用一种基于免疫原理[6]的选择操作和比例适应度分配方法相结合的混合选择算子计算个体被选中的概率以克服上述缺点。
定义1 个体浓度:
找出群体中个体浓度最大的m个个体,设为1,2,…,m,则这m个个体的个体浓度概率为
设某一个个体的适应度为fi,该个体被选中的概率为pfi,则
式中:i=1,2,…,psize。
此种选择策略有两个优点:一是个体适应度越大,则选中的概率越大,加速了算法的收敛;二是个体浓度越大则被选择的概率越小,起到抑制作用,保证了进化群体中个体的多样性,避免过早收敛。
1.4 交叉操作
标准遗传算法由于在进化过程中采用固定的交叉概率和变异概率,已经被证明无法收敛到问题的全局最优解,容易出现早熟现象,后期还会因为个体差异的减小出现收敛速度缓慢的现象。鉴于此,本研究按照一定的交叉概率采用最邻近法则进行交叉操作。首先对交叉概率和变异概率做出如下约定:当群体适应度比较集中时,使得交叉概率Pc和变异概率Pm增大;当群体适应度比较分散时,使得交叉概率Pc和变异概率Pm适当减小。这样约定能使算法在迭代过程中根据个体的适应度来改变其交叉概率Pc和变异概率Pm,从而在能保护最优个体的同时加速较差个体的淘汰速度,增强了算法的全局搜索能力。其数学模型为:
式中:K1,K2,K3,K4是小于0的常数;fmax为群体的最大适应度;favg为群体的平均适应度;f′为交叉产生的2个新个体中适应度较大的那个个体的适应度;f为变异个体的适应度值。
采用最邻近法则的基因匹配交叉操作:设待交叉的2条染色体为S1=Z
,选择S2中与Z
1.5 变异操作
变异操作是一种局部随机搜索,与选择、交叉算子结合可以保证算法的有效性。本研究中采用按基因位(一个基因即为一个聚类中心)的维向量来进行,每个基因位的每维向量(一个浮点数)按变异概率Pm来发生随机变异。在整个算法开始之前,先求出每维向量的最大值和最小值,分别保存在向量
1.6 算法终止条件
只要满足以下2个条件中的任意一个条件则算法终止:
(1)算法迭代次数超过设定一个最大的迭代次数maxGen;
(2)运行过程中得到相同的最优结果次数连续超过某一阀值。
本文采用第2个条件作为结束条件。
2 算法描述
给定样本数据集合
(1)确定要生成的类簇数目k、种群规模为psize个个体及算法结束条件。
(2)先随机选择k个初始聚类中心组成一个个体
(3)对数据集中的每一个样本数据di,依次计算它与各个聚类中心的相似度;将样本数据di合并到与其具有最大相似度的类簇中。
(4)按照相似度公式计算新的类簇的中心,组成一个个体,并计算新个体的适应度;
(5)对所有的个体实施遗传算子,得到下一代的群体;
(6)得到优化后的个体。如果所有聚类中心均达到稳定,则结束;否则,t=t+1,转(3)。
3 试验结果及分析
分别采用 k-均值算法、遗传K-均值算法(GA-K均值算法)和本文算法在VC++和MatlAB环境下进行仿真实验。遗传算法的交叉概率和变异概率初始值分别取为0.75,0.09,群体规模为100,迭代次数为100次,当运行过程中得到最优结果次数连续10次以上时算法结束。实验采用数据是Fisher的Iris 3种植物150样本个数据[9]进行10次试验,每个样本均为四维向量,代表植物的4种属性。三种算法分别单独运行10次,计算出簇内距离Ek与簇间距离Dk的最大值,最小值及平均值。实验结果见表1。
注:以上数据为单个算法运行10次的平均值。
聚类算法的理想结果是同时获得最小的簇内距离和最大的簇间距离。从表1中的数据可以看出,标准的K-均值算法由于对初始中心选取敏感性很大,在初始中心选择不当的情况下易陷入局部最优,出现过早收敛;GA-K均值算法由于个体的多样性不足而常出现早熟现象;本研究提出的算法在全局搜索能力方面优于K-均值和GA-K均值算法,所获得的聚类结果具有更强的稳定性,对于随机分布的数据聚类有明显的优越性;同时从达到最优解迭代次数看,本文提出的算法达到最优解的平均迭代次数要远少于K-均值和GA-K均值算法,所以本文提出的算法收敛速度更快。
4 结束语
本文对遗传算法和K-均值聚类算法进行了研究,针对K-均值聚类效果易受初始聚类中心影响的不足,为克服遗传算法引入K-均值算法所带来的易出现局部早熟的缺点,将免疫机制的选择操作引入遗传算法,使个体浓度和适应度同时对个体的选择操作产生作用,改变以往单纯以适应度来作为个体选择的依据,对算法进行改进,然后将改进的遗传算法引入K-均值算法中以优化聚类中心,提出一种基于改进遗传算法的K-均值聚类算法。试验结果表明,本研究的算法与传统的K-均值算法和GA-K均值算法比较,在全局搜索能力方面优于K-均值和GA-K均值算法,所获得的聚类结果具有更强的稳定性,能够有效改善聚类质量。
参考文献
[1]Jiawei Han,Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社,2005:185-218
[2]Bandyopadhyay S,Maulik U.An evolutionary technique based on k-means algorithm for optional clustering in rn[J].Information Sciences,2002,(146):221-237
[3]Ahmadyfard Alireza,Modares Hamidreza.Combining PSO and k-means to enhance data clustering[A].IST2008International Symposium[C].Tehran:IEEE Press,2008.
[4]Hai-xiang Guo,Ke-jun Zhu,Si-wei Gao,et al.Animproved genetic k-means algorithm for optimal clustering[A].Sixth IEEE International Conference[C].Leipzig:IEEE Press,2006.
[5]李茂军,罗安.单亲遗传算法的机理分析[J].长沙理工大学学报(自然科学版),2004,1(1):76-79
[6]贺志民,方美娥.基于遗传算法的特征值问题求解[J].长沙电力学院学报(自然科学版),2003,18(1)12-14
[7]赖玉霞,刘建平,杨国兴.基于遗传算法的K-均值聚类分析[J].计算机工程2008,34(20):200-202
[8]王磊,潘进,焦李成.免疫算法[J].电子学报2000,28(7):74-78
K均值聚类 篇8
目前图像分割的算法主要有阈值分割法、边缘提取法、区域分割法、分水岭分割法等[1],这些分割算法各有优缺点。近年来,许多研究人员提出用聚类算法来分割图像[2],并取得了较好的实验结果。但如何初始划分(分类)样本以及选择代表点将直接影响分割的效果。在以往的研究中,基于K均值聚类及其改进算法的图像分割技术受到了广泛关注。K均值聚类是聚类方法中一种无监督动态算法,具有一定的自适应性,但聚类结果易受初始聚类中心的影响。基于传统K均值聚类的图像分割算法存在如下缺陷:(1)直接针对像素样本集进行聚类,运算代价太大,耗时长;(2)使用欧氏距离来度量各个特征向量之间的差异,这种度量方法要求样本数据在特征空间呈球形或椭球形分布,然而样本数据在特征空间的结构多样,不一定能满足这种特殊要求,从而会对聚类结果产生影响。
在以上研究的基础上,本文提出了一种改进的K均值聚类图像分割方法。首先根据Ohta等人提出的彩色图像分析方法,选取彩色图像的彩色特征集中的第一个分量作为图像像素的一维特征向量,用来替代传统K均值聚类图像分割中的灰度。再基于粗糙集理论,求出初始聚类的个数与均值。选用对特征空间结构没有特殊要求的特征距离代替欧氏距离,从而减少特征空间结构对聚类结果的影响。最后利用改进的K均值聚类算法对样本数据进行聚类,实现对彩色图像的快速自动分割。实验结果表明,该图像分割方法可有效提高彩色图像分类的精度和准确度,并且运算代价小,收敛速度快。
1 初始聚类中心与个数的确定
1967年,Mac Quen首次提出K均值聚类算法[3],该算法是解决聚类问题的一种经典算法。K均值算法的基本思想是:对于给定的聚类数目k,首先随机选择k个对象,每个对象初始地代表一个聚类的平均值或中心。对剩余的每个对象,根据其与各个聚类中心的距离,将它赋给最近的聚类。然后重新计算每个聚类的平均值,对数据库中的每个对象与每个聚类的平均值相比较,把对象赋给最相似的某个聚类。重复执行该过程,直到准则函数收敛使平方误差函数值最小。
K均值聚类算法中重要的一步是初始聚类中心的选取,一般是随机选取待聚类样本集的k个样本,聚类的性能与初始聚类中心的选取有关,聚类的结果与样本的位置有极大的相关性。若这k个样本选取不合理,将会增加运算的复杂程度,误导聚类过程,得到不合理的聚类结果。为提高聚类的效率和分类的精度,我们根据粗糙集理论来确定K均值聚类所需要的初始类的个数和均值[4]。
令知识系统K=(U,R)表示图像信息,R表示图像中的等价关系。利用不可分辨关系计算图像像素的灰度值,计算规则是定义的等价关系R,从而求出初始聚类中心和个数。对于有M×N个像素组成的图像U,其直方图一般呈谷峰状分布,同一区域内像素的灰度值比较接近,且不同区域内像素数不相等。灰度值相近的像素可归为一类,这样可将图像分为几类。假设灰度值xi为集合U的一个对象,φ(xi)(i=1,2,…,255)表示灰度值为xi的像素的个数。定义像素的灰度值差为条件属性,等价关系R定义为:如果两个像素灰度值差小于定间距d,则两个像素是相关的,属于等价类,可用下式表示:
具体方法为:首先确定间距阈值d,通过直方图可求出灰度值分布范围,根据灰度值范围可以求出灰度级数L;对于每一个灰度级而言,将该灰度级范围内象素个数最多的灰度值定义为中心点。计算L个中心点之间的两两间距,若最小距离小于阈值d,则将相应中心点合并,并将两点的算术均值作为该中心点的值;重复以上过程,直到所有中心点的两两间距均大于d。最终所求得的中心点的个数和数值就是K均值聚类所需要的初始聚类中心和个数。
2基于改进的K均值聚类彩色图像分割
以往的一些K均值聚类和模糊K均值聚类图像分割算法直接针对图像的像素集合进行聚类,聚类规模很大,随之而来的是巨大的计算量以及大量的时间消耗。为了解决这一问题,人们提出将灰度图像像素空间映射到其灰度直方图特征空间中,从而把针对像素集合进行的聚类映射成针对灰度级集合进行的聚类,大大提高了对灰度图像的分割速度。在实际应用中,许多图像处理的对象都是彩色图像,表征彩色像素需要RGB三个分量,不能直接应用K均值或模糊K均值聚类图像分割算法来处理彩色图像。日本学者Ohta等人[5]通过对大量的彩色图像区域分割实验,得到一个适合进行彩色图像分割的彩色特征集
实验证明,仅使用I1分量就可有效进行彩色图像分割。
2.1特征距离
传统K均值聚类算法常使用欧氏距离来度量待分类对象与各类具有代表性的典型对象间的差异,但这种距离测度要求样本数据在特征空间呈球形或椭球形分布,然而样本数据在特征空间的结构是多样的,且真实数据中很少有紧致、界限清晰、比例均匀的类群。这就需要一种对向量空间结构没有严格限制的向量距离度量方法,而特征距离[6]能满足这一要求,并具有较强的普适能力,其定义如下:
2.2改进的K均值聚类算法
根据Ohta等人的研究成果,本文使用I1分量作为彩色图像像素的一维特征量,用I1分量代替K均值聚类图像分割中的灰度。用T表示像素点的数目,I1p∈{0,1,…,Lmax-1}(p=1,2,…,T),I1p为集合Ai(j)中像素的灰度值。Lmax为I1的亮度级数,λi(j)为第j次迭代后第i类的均值,Ai(j)表示第j次迭代后第i类的像素集合。本文提出的改进的K均值聚类算法步骤如下:
1)根据I1分量,应用粗糙集理论选取K均值聚类所需要的初始聚类个数k和均值λi(0)(i=1,2,…,k)。
2)对于每个像素,保存它与第j-1次迭代时的聚类均值的距离Di(j-1)(i=1,2,…,k);在第j次迭代时,考察每个像素,首先计算它与上次聚类更新后(即第j-1次)均值的距离,得到新的距离Di(j),其中,。如果Di(j)≤Di(j-1),则像素点i仍然保留在原来的聚类中,无须计算它与其它聚类均值的距离[7]。这里的距离指的是2.1节定义的特征距离。
3)对于i=1,2,…,k,计算新的聚类中心,按照下式更新类均值:
式中,x∈Ai(j)表示集合Ai(j)中任意像素x,Nj表示集合Ai(j)中的像素个数。求误差平方和准则E(j)为:
3 图像分割实验
为了验证本文所提出的彩色图像分割算法的有效性和可行性,从选用不同的距离测度、聚类算法运行时间及图像分割效果三个方面来进行实验。
1)选用欧氏距离与特征距离的实验结果比较:图1(a)为原彩色图像,根据文献[5]中的方法,我们选用I1分量作为彩色图像像素的一维特征量,用I1分量代替K均值聚类图像分割中的灰度。选取间距阈值d=30,亮度级个数Lmax=11,各亮度级对应的中心点为{36,50,84,112,121,135,146,188,217,240},通过粗糙集理论可求得K均值聚类初始聚类个数为5,各类初始均值为{43,84,136,203,240}。图1为实验结果。图1(b)为当选用欧氏距离,使用本文算法的分割结果;图1(c)为当选用特征距离,使用本文算法的图像分割结果。从图中可看出,图1(b)的图像分割细节明显好于图1(c)。可见,选用特征距离的图像分割效果明显好于选用欧氏距离的图像分割效果。
2)选用传统K均值聚类图像分割算法和本文算法图像分割效果比较:与(1)中的方法类似,根据原始图像图2(a)和粗糙集理论,可求得初始聚类个数为5。图2(b)给出了选用传统K均值聚类图像分割方法的分割效果,图2(c)给出了选用本文算法时的图像分割效果。与图2(b)相比,图2(c)的图像边缘更清晰,分割结果既突出了目标,又保留了细节信息,达到了比较理想的分割效果。因此,本文分割算法要优于基于传统K均值聚类的分割算法。
3)选用不同图像分割算法时的分割速度比较:分别选用传统K均值聚类算法、快速模糊K均值聚类算法和本文算法进行图像分割实验,图3为三幅不同像素的原始图像。表1所示为对各图像进行分割的相关数据,表中k表示聚类方法最终确定的聚类数目,t表示对图像分割所需要的时间。图4是三种图像分割算法所需要的运行时间曲线图,图中,“”表示使用传统K均值聚类算法所需要的时间,“”表示使用快速模糊K均值聚类算法所需要的时间,“”表示使用本文算法所需要的时间。从表1中各算法所需要的处理时间和图4的时间曲线可看出,本文提出图像分割算法聚类速度快,明显优于其它两种方法。
5 结论
K均值聚类方法是一种无监督动态算法。K均值聚类的结果易受聚类中心的个数及初始聚类中心的影响,同时也受样本的几何形状的影响。针对以上问题,本文提出了一种改进的K均值聚类算法,基于粗糙集理论确定K均值聚类的初始类个数与类中心;利用Ohta等人的研究成果,选取能有效表示彩色像素特征的彩色特征集中的第一个分量作为图像像素的一维特征向量,用来替代经典K均值聚类图像分割中的灰度,大大降低了运算量;K均值聚类的距离测度选用特征距离,提高了算法的适用性和准确性。实验表明,本文提出的图像分割算法可有效提高图像分类的精度和准确度,并且运算代价小,收敛速度快。
摘要：提出了一种改进的K均值聚类图像分割方法。针对彩色图像的像素特征,利用Ohta等人的研究成果,选取能有效表示彩色像素特征的彩色特征集中的第一个分量作为图像像素的一维特征向量,用来替代经典K均值聚类图像分割中的灰度,大大降低了运算量。基于粗糙集理论的算法,求出初始聚类个数与均值。选用对特征空间结构没有特殊要求的特征距离代替欧氏距离,应用改进的K均值聚类算法对样本数据进行聚类,从而实现对彩色图像的快速自动分割。实验表明,该图像分割算法可有效提高图像分类的精度和准确度,并且运算代价小,收敛速度快。
关键词：图像分割,粗糙集,K均值聚类,特征向量
参考文献
[1]Pal N R,Pal S K.A review on image segmentation techniques[J].Pat-tern Recognition,1993,26(9):1277-1294.
[2]Cheng H D,Jiang X H,Sun Y,et al.Color image segmentation:Ad-vance and Prospects[J].Pattern Recognition,2001,34(12):2259-2281.
[3]MacQueen J B.Some methods for classification and analysis of multi-variate observations[C].The5th Berkeley Symposium on Mathematical Statistics and Probability,Berkeley,USA:University of California Press,1967:281-297.
[4]邵锐,巫兆聪,钟世明.基于粗糙集的K-均值聚类算法在遥感影像分割中的应用[J].现代测绘,2005,28(2):3-5.
[5]Ohta Y,Kanade T,Sakai T.Color information for region segmentation.Computer Graphics and Image Processing,1980,13(3):222-241.
[6]张新明,沈兰荪,沈波.基于特征距离的阈值法及其在眼科图象分割中的应用[J].中国图象图形学报,2001,6(2):159-163.