K均值聚类法（精选7篇）
K均值聚类法 篇1
0 引言
大米是人类赖以生存的主要粮食之一。影响大米品质的主要因素有淀粉、蛋白质以及各种微量元素等,其中铜、铁、锰、锌、硒、碘等微量元素的含量越高,大米的营养价值就越高[1]。大米中所含的化学成分很大程度上来源于其所生长的自然环境,不同地区生产的大米往往具有不同的品质特征。我国的大米产区很多,其中东北地区生产的大米由于其品质优良,为日、韩等国消费者所青睐,具有较大的出口潜力[2]。市场环境下,一些不法商贩为了牟取暴利,往往以次充好,严重损害了消费者和大米生产厂商的利益。为了减少或杜绝此类欺骗事情的发生,有必要研究一种行之有效的方法(技术)对大米的产地进行鉴别,不仅能够保护广大消费者和生产厂家的利益,而且对提高大米品质、推动我国大米出口业都将具有重要的现实意义。
目前,对大米产地的鉴别和检验通常由肉眼根据外观来进行,准确率和效率极为低下。国内有研究人员使用近红外光谱分析技术对大米品种进行鉴别[3],但近红外光谱分析技术是一种“黑箱”技术,不容易对鉴别结果提出可靠的理论解释。因此,这一方法不能作为一种标准方法被国家质检部门所采用。电感耦合等离子体原子发射光谱(ICP-AES ,Inductively Coupled Plasma Atomic Emission Spectrometry)具有检测限低、精度高和线性范围宽等优点,可同时测定多种微量元素,目前已被广泛应用于食品和农产品中进行多种样品与多种微量元素的测定[4,5,6,7]。1997年,日本的Shindoh K等[8]已经使用电感耦合等离子体发射光谱法对大米样品中的K,Mg,Ca,Zn,Mn和Fe等多种微量元素的含量进行了测定,并根据不同大米样品中的微量元素含量对大米样品进行产地的鉴别和分类。2000年,他们[9]又使用该方法测定多种微量元素含量,并结合主成分分析和聚类分析的化学计量学方法对糙米的产地进行了鉴别,取得了满意的效果。
响水大米是东北大米中的珍品,由于其生长的自然环境优越而富含矿物质等营养元素[10]。为了研究不同产区大米品质特征的不同,本文选取了响水地区生产的大米样品和一些其他地区所生产的大米样品,使用等离子体发射光谱仪对样品进行了金属微量元素的测定,并根据这些微量元素含量的数据,使用化学计量学的方法对大米的产地进行了鉴别。
1 材料与方法
1.1 实验仪器及参数
本实验中,用于测定大米样品中微量元素含量的仪器为VISTA-MPX等离子光谱仪,试剂有盐酸(分析纯)和超纯水。仪器工作参数如下:
功率/kW:1.2
观察高度/mm:10
积分时间/s:10
冷却气流量/ L·min-1:12.5
载气压力/kPa:200
辅助气/ L·min-1:1.25
实验温度为20℃,湿度为50%。其它仪器有石英炬管、高盐雾化器及蠕动泵进样。
1.2 样品及样品处理
本文所使用的19个响水大米样品由黑龙江省宁安市质量技术监督局提供,10个非响水大米样品则购自本地超市(包括浠水望天湖香米、兴唐贡米、营东香米、天津小站米、太湖珍珠米和盘锦大米等)。 样品预处理:将不同批次大米用玛瑙研钵粉碎后,常温真空干燥24h。称取样品0.500g于瓷坩埚中,放入马弗炉中,低温升至500℃,保持4h灰化完全,取出冷却,加1 mol/L的HCl 5mL,提取定容至25 mL,上机测定。
2 数据处理方法和软件
使用SPSS 16.0数据处理软件对响水大米和非响水大米样品进行分析,比较了不同方法对样品聚类的结果,使用的化学计量学方法为K-Means聚类法和Hierarchical聚类法。
3 微量元素数据
使用等离子体光谱的方法对响水和非响水大米样品中的P,B,Zn,Fe,Cu,Mn,Na,K,Mg和Ca等微量元素含量进行了测定。结果发现,响水和非响水大米样品中所含各微量元素的浓度范围以及平均值差别并不太大,如响水样品的P含量浓度范围为798～1 066μg/g,非响水大米样品的P含量为768～1 025μg/g,且平均值分别为939.856μg/g和904.166μg/g;响水样品中Mn含量为8.66～16.9μg/g,而非响水样品中的Mn含量则为7.37～13.6μg/g,且平均值分别为12.909μg/g和10.000μg/g。但非响水大米样品的各微量元素含量标准偏差普遍较大,如响水样品P含量的标准偏差为74.374μg/g,非响水样品的P含量标准偏差则高达91.826μg/g,亦即非响水大米样品的各微量元素含量差异较大。这可能是由于所选择的非响水大米样品的产地各不相同所致。同时,由于响水和非响水大米样品的微量元素含量范围的重叠,无法直接使用单个或某几个微量元素含量对大米样品的产地进行鉴别,因此使用化学计量学中的K-Means聚类法和Hierarchical聚类法对样品中所含微量元素同时进行分析,从微量元素角度寻找不同产地大米所表现出的不同品质特征,从而将它们鉴别开来。
4 结果与讨论
4.1 K-Means聚类法
K-Means聚类法又称K均值聚类法,是一种典型的距离聚类分析算法。该方法选取某种距离作为判别指标(如欧氏距离或马氏距离等),并选取各类的聚类中心,形成初始分类,然后按照选取的距离指标最近原则不断更改不合理分类,直到合理为止。该方法认为,两个样品的距离越近,则越相似。在本文中,两个样品的距离越近,说明两样品的微量元素含量特征越相近。
本研究中样品包含响水和非响水大米两类,因此在本方法中按两类聚合来确定初始类中心,并在迭代过程中使用K-Means算法不断更换类中心,将样品分配到欧氏距离与之最近的以类中心为标志的类中去。所选取的变量为大米中的P,B,Zn,Fe,Cu,Mn,Na,K,Mg和Ca等10种微量元素含量,迭代次数为10次,收敛判据为0。
图1为使用K-Means聚类法对大米产地进行分类的欧氏距离图。图1中,响水和非响水大米样品分别使用“○”和“□”来表示。由图1可见,大部分响水大米样品(15个)和一部分非响水样品(6个被分为第2类,剩余样品(4个响水大米样品和4个非响水大米样品)被分为第1类,各类样品到所属类的欧氏距离均远小于到另一类的欧氏距离。从这一结果可以看出,根据微量元素含量,响水和非响水大米样品分别有聚类的趋势,但聚类效果不太好,这可能是由于样品量较小,或者所选择的非响水大米样品品质好,与响水大米样品之间确实具有较为相似的特征所致。
4.2 Hierarchical
Hierarchical 聚类法又称为系统聚类法或分层聚类法。使用这一方法对样品进行聚类时,不能对样品类别数量进行规定。首先,将每个样品视为一类;然后,将具有最小距离的样品合并,计算新类与其他类之间的距离;再将距离最小的类进行合并,一直到最终将所有样品均合并在一起。在本方法中,选择了使两类之间平均距离(欧氏距离)最小的聚类方法。图2为使用Hierarchical聚类法对响水和非响水大米样品进行聚类的树形图。从图2中可以看出,样品大致可以分为两类:第1类包括除去13号样品的响水大米样品以及非响水大米的4,5,6,7,8,10号样品,剩下的样品为第2类。响水大米样品的11,17,19,20和28号以及12,16,23,24,25,26,27,29号样品分别聚为小类,说明样品间的微量元素含量特征较为相似;而非响水样品的5,6,10号聚为一小类,其含量特征较为相似。观察本方法所得的结果,聚类效果仍然不特别好,但两类样品中均有部分样品显示出较为强烈的聚类趋势。
4.3 讨论与展望
本文使用了等离子体原子发射光谱的方法,测定所响水和非响水大米样品中的P,B,Zn,Fe,Cu,Mn,Na,K,Mg,Ca等10种微量元素含量,并结合K-Means聚类法和Hierarchical聚类法对大米样品进行了聚类分析。结果发现,K-Means和Hierarchical聚类法对于样品的聚类效果不太好,但两种样品有较明显的聚类趋势。使用两种方法得到的聚类结果不太好的原因可能如下:
1)本实验选取的响水和非响水样品量较小,尤其是非响水样品量较小,同时这些非响水大米样品分别来自不同的产地(天津小站、江苏太湖和辽宁盘锦等),彼此之间具有不甚统一的品质特征;
2)K-Means和Hierarchical聚类法均为无监督学习下的聚类分析,分析方法本身并不关心样品的真实分类,而只是通过方法的分析将样品分为特征不同的几类,使同一类样品的特征最为相似,不同类样品的特征相差较大。
基于此,在后续的研究中,应尽量增加两种样品尤其是非响水样品的样品量,同时尽量选择产地较为统一的非响水大米样品进行分析研究,并在深入研究中尽量扩充样品的产地类型,以使所建立的模型具有较强的扩展性。在分类方法方面,应继续尝试有监督学习模式识别分类方法,对分类结果进行比较,以寻找出较佳的分类方法。本研究为广大的厂家、商家与质检部门提供了一种新的大米产地鉴别方法和技术,为开发新型大米产地鉴别设备和仪器打下了一定的理论基础。
摘要：大米称誉为“五谷之首”,是我国的主要粮食作物。大米产地鉴别方法的研究对于保护广大消费者和生产厂家的利益、推动我国大米出口业的发展等都具有重要意义。为此,选取了19个响水大米样品和10个非响水大米样品,使用等离子体原子发射光谱的方法测定了样品中P,B,Zn,Fe,Cu,Mn,Na,K,Mg和Ca等10种微量元素的含量,并利用样品中的微量元素含量数据,使用K-Means聚类法和Hierarchical聚类法对大米样品进行了聚类分析。结果表明,K-Means和Hierarchical聚类法对于样品有聚类趋势。研究结果能够为大米生产厂商与质检部门鉴别大米产地提供参考和借鉴。
关键词：大米,等离子体原子发射光谱,K-Means聚类法,Hierarchical聚类法
参考文献
[1]高杨,范必威.大米品质的评价及其主要影响因素[J].广东微量元素科学,2005,12(12):12-16.
[2]刘文玫.浅析我国大米出口的贸易状况[J].天津农业科学,2009,15(2):17-19.
[3]周子力,张瑜,何勇,等.基于近红外光谱技术的大米品种快速鉴别方法[J].农业工程学报,2009,25(8):131-135.
[4]Jung MC,Yun ST,Lee JS,et al.Baseline study on essentialand trace elements in polished rice from South Korea[J].Environmental Geochemistry and Health,2005,27(5-6):455-464.
[5]谭小宁.ICP-AES测定米中多种微量元素[J].光谱实验室,2005,22(5):1079-1082.
[6]Manjusha R,Dash K,Karunasagar D,et al.Determinationof trace elements in Indian rice by ETAAS and ICP-AES[J].Atomic Spectroscopy,2008,29(2):51-55.
[7]曾亚文,汪禄祥,孙正海,等.ICP-AES法测定粳稻近等基因系群体间糙米的矿质元素[J].光谱学与光谱分析,2008,28(12):2966-2969.
[8]Shindoh K,Yasui A.Determination of mineral contents in asingle grain of rice by ICP-AES[J].Bunseki Kagaku,1997,46(10):813-818.
[9]Yasui A,Shindoh K.Determination of the geographic originof brown-rice with trace-element composition[J].BunsekiKagaku,2000,49(6):405-410.
[10]郑纳新.米中精品响水大米[J].中国食品,1999(23):33.
基于K均值的学生聚类 篇2
appraisement
industry
point
实行学分制使得因材施教成为可能, 为学生的个性化发展提供了基础, 同时, 也给学校的学生日常管理工作带来了巨大的挑战。为了更好地管理学生, 文中使用K均值对学生进行聚类, 给出了具体的聚类方法和实行过程, 在实验中采用三种不同的距离计算方法对学生进行聚类, 表明了该方法是有效的。
随着高等教育教学改革的不断深化, 各地高校为适应高等教育大众化、阶段多样化的要求, 都积极探索并实施学分制的管理模式。实行学分制给学生的个性培养和教学的因材施教提供了良好的发展空间, 但从学校方面来说, 学分制下的学生管理突破了原有的学生管理体制, 对学生管理提出了严峻的考验。
在学分制下, 虽然每一个学生的自由度加大, 但是整个学校里所有的学生在长期会有一些相同或相似的情况, 即所谓的“物以类聚, 人以群分”, 如果能根据长期以来的学生的表现对学生进行聚类, 使得同一类的学生有更多的共同点, 不同类的学生有较大的不同, 然后可以针对不同类型的学生采用不同的方法进行管理, 不仅可以提高管理的针对性, 而且可以更好的研究不同类型的学生的具体情况, 为以后的学生选课、就业等方面提供一些有益的建议。
聚类是将数据分类到不同的类或者簇这样的一个过程, 所以同一个簇中的对象有很大的相似性, 而不同簇间的对象有很大的相异性。K均值聚类算法是一种有效的聚类技术, 具有对大型数据集进行高效分类的特点, 因此, 本文采用该方法对学生进行聚类。
K均值聚类
k均值聚类是最著名的划分聚类算法, 由于简洁和高效使得其成为所有聚类算法中最广泛使用的。具体的计算过程如图1所示。
基于K均值的学生聚类
聚类不仅可以降低学生管理的难度, 而且使得学生管理具有针对性和高效性的优点;K均值是一种有效的聚类算法, 因此本文其应用于学生管理。由于学生的身高、性别、年龄等这些因素对于学生管理的意义不大, 而性格虽然重要, 但是数据很难收集, 而学生在学校的首要根本任务是学习, 而且学完课程都会有一个考试来检验学习的效果, 因此, 成绩数据不仅数据量大, 而且可以指导学生此后的选课及教学计划的制定, 因此, 文中使用学习成绩对学生进行聚类。具体的流程如图2所示。
(1) 数据预处理
由于描述成绩的数据可能是数值或者是等级这样的模糊值, 为了计算的方便, 需要对模糊数据进行数值化, 在本文中, 根据图3的对应关系进行数值化。
(2) 缺失值的处理
由于在收集数据的过程中各种因素导致的数据缺失是不可避免的, 因此, 需要对项目中存在的缺失值进行处理。常用的缺失值处理方法有删除存在缺失值的个案和缺失值插补。删除法是对缺失值进行处理的最原始方法, 它将存在缺失值的个案删除。由于成绩数据缺失的情况现有发生, 因此, 本文使用该方法对缺失值进行处理。
(3) K均值聚类
对成绩进行处理以后就可以聚类了, 首先确定将成绩聚为几类, 并确定相应的聚类中心;然后分别使用欧氏距离、余弦距离和相关度三种方法计算每一个同学的成绩与各个聚类中心的距离进行聚类;最后, 根据聚类结果重新计算聚类中心, 重复该过程直到收敛。
实验
本文以某校计算机专业的一个班一年的成绩为例进行实验, 使用前文的模糊数值和缺失值的处理方法进行数据预处理, 然后使用matlab对其进行聚类, 三种距离计算方法的聚类结果如图4, 5, 6所示。
结束语
一种并行的加速k-均值聚类方法 篇3
聚类作为一种典型的数据挖掘方法,目前已在图像识别、股票分析等领域得到成功应用[3,4]。其任务是从大规模数据集中发现相似的类别,将样本划分为多个不重合的子集。在聚类结果中,相同类内样本应具有较大相似性,不同类间样本具有较大相异性。目前,常见的聚类模型包括:划分聚类[5]、层次聚类[6]、密度聚类[7]、网格聚类[8]、概率聚类[9]和谱聚类[10]等。
在这些聚类方法中,k-均值聚类是一种最为经典使用最为广泛的划分聚类方法[11,12]。k-均值聚类方法以各类样本的质量中心代表该类进行迭代,从而通过不断地动态调整各类中心进行聚类。但是,k-均值聚类算法复杂度高,对大规模数据无法进行有效聚类。因此,如何采用k-均值聚类方法解决大规模数据的聚类问题一直是聚类分析领域的一个研究热点。
随着数据挖掘领域处理样本规模的日趋增大,要求研究人员能够提出高效的挖掘算法来处理海量数据问题。并行计算作为一种定量、精细、高效的方法在海量数据挖掘中得到了成功的应用[13]。狭义上的并行计算是指在并行/分布式计算机上所做的计算,从广义上讲,将多个问题同时求解的过程都可以看做是并行计算的过程。尽管目前已经有学者提出了一些基于并行计算的聚类技术以改进传统的聚类方法[14,15],但是,这些技术效率还不足够高,对于大规模数据的聚类问题的处理能力依然有限。因此,如何结合并行计算技术进一步提高k-均值聚类方法处理海量数据的能力依然是一个值得探讨的问题。
针对传统k-均值聚类方法不能有效处理海量数据聚类的问题,该文提出一种基于并行计算的加速k-均值聚类方法。该方法首先将聚类样本随机划分为多个独立同分布的聚类工作集,并在每个工作集上并行进行传统k-均值聚类,对聚类后的每个类计算其中心和半径,通过衡量不同工作集聚成的子类的中心和半径,对不同工作集的子类进行快速合并,并对子类中的少数特殊数据进行二次归并以校正聚类结果,从而有效处理海量数据的聚类问题。
1 基于并行计算的加速k-均值聚类算法
1.1 k-均值聚类方法
设数据集X={x1,∙∙∙,xi,∙∙∙xn}且xi∈Rd,其中n为样本个数,d为样本维度,k为聚类之前指定的聚类个数。传统k-均值聚类算法首先随机选择k个样本作为初始聚类中心C={c1,∙∙∙,cj,∙∙∙,ck},然后计算每个样本xi∈X到聚类中心cj∈C的距离d(xi,cj),根据每个样本到聚类中心的距离将样本划分到与之最近类中,并计算更新后每个类的中心C,如此循环迭代直到更新后的类中心与更新前一致时停止。
由于传统k-均值聚类方法由于在每次迭代聚类时都需要衡量所有样本到每个类中心的距离,因此算法复杂度为O(nkq),其中,q为聚类迭代次数。当数据规模较大时,算法往往需要很多次迭代才能结束,运行效率较低,不能够有效处理海量数据的聚类。
1.2 并行的加速k-均值聚类方法
针对传统k-均值聚类方法不能有效处理大规模数据聚类的问题,该文结合并行计算思想,提出一种基于并行计算的加速k-均值聚类方法(Pk-means)。该方法首先将聚类样本集X随机划分为多个独立同分布的聚类工作集,即X→{X1,∙∙∙,Xj,∙∙∙,Xm},并在每个工作集Xj上并行进行传统k-均值聚类,得到聚类结果Xj→{Xj1,∙∙∙,Xjp,∙∙∙,Xjk}。然后,对于每个聚类后得到的类Xjp(共mk个),求解其类中心cjp和类半径rjp,然后通过衡量不同工作集中类中心之间的相似度,将相似度最高的合并为一个类,类中心(两个不同样本)相似度的求法如下:
与第i个工作集中第p个类合并的第j个工作集中类别确定方法为:
将每个工作集的聚类结果均按照上述规则进行合并,最后得到一个划分,即X→{X1,∙∙∙,Xt,∙∙∙,Xk},并计算其新的中心C={c1,∙∙∙,ct,∙∙∙,ck}及半径R={r1,∙∙∙,rt,∙∙∙,rk}。然后判断聚类结果是否需要更新,若rt<=range,则不更新,否则对子集Xt中符合条件(3)的样本按照式(4)进行更新。
基于并行计算思想的k-均值方法由于将样本划分为n k的大小,且并行执行传统k-均值聚类方法,所以初始复杂度为O(nq'),其中q'为每个工作集进行传统k-均值聚类的最大迭代次数,且易得到q'<
基于并行计算的k-均值方法具体如下:
初始化:设数据集为X={x1,∙∙∙,xi,∙∙∙xn}(其中xi∈Rd),随机划分工作子集参数为m,工作子集聚类参数为k,聚类结果更新参数为range。
Step1:将样本集X随机划分为m个工作子集,即得到划分模式X→{X1,∙∙∙,Xj,∙∙∙,Xm}。
Step2:对每个工作子集Xj进行k-均值聚类,得到每个工作子集的聚类模式Xj→{Xj1,∙∙∙,Xjp,∙∙∙,Xjk}。具体方法如下:
Step2.1:在每个工作子集Xj随机选择k个样本作为初始聚类中心;
Step1.2:根据式(5)计算每个样本xjq与所有不同类Classjp之间的相似度,并将xjq归为与其最相似的类中心所属的类;
Step1.3:根据式(6)计算样本重新分配后的第每个类的中心Cj={cjp}kp=1
Step1.4:若类中心有更新,则返回Step1.2继续聚类,直到类中心不发生更新时迭代停止,得到每个工作子集Xj的聚类结果Xj→{Xj1,∙∙∙,Xjp,∙∙∙,Xjk}。
Step3:根据式(1)计算不同工作子集中的类之间的相似度,并根据式(2)合并工作子集的聚类结果,从而生成对整个数据集X实现k类的划分,即X→{X1,∙∙∙,Xi,∙∙∙,Xk}。
Step4:根据式(3)和式(4)对聚类结果进行更新调整,从而得到更为优秀的聚类结果X→{X1opt,∙∙∙,Xiopt,∙∙∙,Xkopt}。
算法结束。
2 实验结果及分析
为验证基于并行计算的k-均值方法聚类方法处理大规模数据聚类的有效性,该文在一个人工构造的模拟的社会网络社团结构数据集上进行了实验,并将聚类结果与经典k-均值聚类方法所得到的结果进行了比较。实验在1台PC机(2.66Ghz CPU,1G内存)上进行,实验平台是Matlab2008。
为充分反应本文提出的并行加速k-均值聚类方法的有效性,实验构造了两组数据集。第一组数据集中,人工模拟的网络社团机构数据集包含100个顶点,它们被划分成相同大小的4个社团结构,每个社团结构包含25个顶点,且所有顶点的度均符合如下条件:
其中zin为每个顶点随机指向落在相同社团中顶点的有向边数目,zout为每个顶点随机指向落在不同社团中顶点的有向边数目。网络中100个顶点在zin=12,zout=3时被划分成4个社团结构时的示意图如图1所示,第二组实验数据与第一组构造方法一致,但数据规模扩大了20倍。
本文从两个方面衡量了算法的性能,即聚类结果的抱团性和聚类时间。。聚类抱团性的定义如下:
为充分反应本文提出的基于并行计算的加速k-均值聚类方法的性能,实验中与传统k-均值聚类方法进行了对比。两组实验中子集划分参数m分别取5和10,聚类个数参数均为4,聚类结果更新参数为range取当前类的1.2倍数值,所得实验结果见表1。
从以上实验结果可以看出,在构造的网络社团结构数据集上,当样本规模为100时,该文提出的基于并行计算的k-均值聚类方法的J值较高,样本的抱团性较差,聚类时间与传统k-均值聚类方法有一些提高;但是,当样本规模增加到2000时,该文提出的基于并行计算的k-均值聚类方法的J值接近于传统k-均值聚类方法的J值,而聚类的时间则只有传统k-均值聚类方法的25%左右。
综上可看出,由于本文提出的Pk_means聚类方法采用了并行计算的模式,并且采用了独立同分布的样本初始工作集划分方法,因此能够以较高的训练效率处理大规模数据的聚类问题,同时保证了聚类结果的抱团性能。
3 结论
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
在电力系统负荷中,感应电动机是其中重要的、也是最主要的组成部分。感应电动机的运行情况在很大程度上影响着系统的运行与控制[1,2]。感应电动机数量庞大,对系统进行分析计算时,采用详细的动态模型对其进行刻画往往是不现实的,因此,在负荷建模工作中,为了降低负荷模型的阶数,通常采用统计综合法。
对统计综合法而言,合理地聚合感应电动机群是其核心工作,在该领域已有一定的研究基础[3,4,5,6,7,8,9]。基于容量加权法,文献[3]以近似特征值对感应电动机进行分群。考虑电动机稳态时的等效电路,文献[4]将得到感应电动机的3阻抗并联模型,进一步并联相同母线下所有电动机的阻抗,依次作为该母线下等值电动机的参数。文献[5,6]分别考虑空载、堵转这2种电动机的极端情况,并采用这2种情况下的近似等效电路对等值电动机的参数进行计算。文献[7]考虑了电动机负载率和临界滑差对容量加权法的影响。文献[8,9]对电动机分群时采用了基于统计思想的聚类算法。在电力系统遭受的干扰很大或很小时(也即系统处于稳定状态或失稳时),以上方法聚合得到的等值模型都可以较为准确地描述电动机群负荷的动态特性。然而,当系统在临界情况下这些方法得到的结果均存在保守或冒进的问题。
本文首先研究了感应电动机各参数的轨迹灵敏度,并以此作为聚类算法的特征权值对电动机进行分群,然后与基于空转-堵转的等值电动机参数计算方法相结合进行感应电动机群聚合计算。最后利用数值仿真,分析比较了本文方法与传统方法得到的聚合电动机在不同故障切除时间下的系统稳定性,结果表明了本文所提电动机聚合方法的正确性和有效性。
1 利用特征权值的聚类算法进行电动机分群
目前,在负荷建模的研究工作中广泛采用的即为本文中提到的考虑机电暂态的三阶动态模型来描述感应电动机的动态特性,图1为其等值电路。该模型可以准确地描述感应电动机负荷在不同程度扰动下的动态行为。本文以该模型为基础,研究了感应电动机群动态模型的聚合降阶。
感应电动机数学模型为:
其中,X=X2+Xm;X'=X1+X2//Xm;T'=(X2+Xm)/R2。
机械转矩Tm和电磁转矩Te分别为
式中:R1为定子电阻;X1为定子电抗;Xm为励磁电抗;R2为转子电阻;X2为转子电抗;T1为惯性时间常数;A,C为机械转矩系数;Re为取实算子;s为电动机转差;E'为暂态电势;s0为初始转差:T'为暂态时间常数;p为微分算子。
当多台感应电动机接入同一母线上时,可以通过聚合算法将其等值为1台电动机。然而,当这些电动机参数或运行特性差异较大时,仅用1台等值电动机很难正确反映多台感应电动机的总体特性。因此,合理地对多台电动机进行分群,并将每个群用1台电动机等值,可以提高电动机聚合的精度。
1.1 考虑特征权值的K-均值聚类算法
聚类分析是基于基础数据源,并将其按照相似性划分为不同的若干个类别的算法。划分后的类别具有以下性质:1)相同类别中元素之间的相似性尽可能大;2)不同类别中元素之间的相似性尽可能小K-均值算法是一种经典聚类算法,它用欧几里德距离的倒数度量相似度。
K-均值算法将n个向量xj(j=1,…,n)分成c个类Gi(i=1,…,c),以均值的思想求取各类别的聚类中心,使得与非相似性指标相关所构建的目标函数最小。当选择欧几里德距离作为度量向量xk与某类别中心的距离,此时目标函数见式(3)。
式(3)通过欧几里德距离进行度量,目标函数中包含了向量xk的所有维度分量(xk的所有属性),且认为xk的每一维度分量在计算距离时具有相同的权重
然而,在实际问题中,xk的不同属性往往对类别划分具有不同的相关性程度。在聚类时如果不加区分地平等对待每一个属性,那么相关性低的属性则会引起“维数陷阱”[10,11,12]误导,影响聚类的结果。因此,在聚类时应对xk的每一个维度分量赋予与之相对应的特征权系数,用以区分不同属性的重要程度。从欧几里德空间上讲,较小的权系数代表了相关度低的分量所对应的轴被缩短,较大的权系数说明相关度高的分量所对应的轴被拉长。那么将式(3)改写为:
式中:wl为特征权值;m为特征数;xkl和和Gil分別为考虑特征权值后的向量和聚类中心。
1.2 基于轨迹灵敏度求取特征权值
基于轨迹灵敏度的概念,通过计算各参数的轨迹灵敏度来确定聚类算法中的特征权值。
轨迹灵敏度反映系统中某一参数、结构发生变化时系统动态轨迹的变化程度,可反映系统轨迹与参数、结构的相互关系[13]。通过计算感应电动机模型中各个参数的灵敏度,可以量化各个参数对系统轨迹的影响,并以此来确定特征权值。
目前,计算轨迹灵敏度的方法主要有解析法、数值差分法(摄动法)、伴随方程法及卷积法等。这些方法各有优缺点,其应用范围也各不相同。本文采用参数摄动法来求解各参数的轨迹灵敏度。
某个参数的轨迹灵敏度定义如下:
式中:yi为系统中第i个变量的轨迹,θj(j=1,…,m)为系统的参数;tk(k=1,…,N)代表第k个时刻。
考虑到参数正负2个方向变化对灵敏度的影响,可以利用中值法来计算导数,即分别用参数正向变化和负向变化来计算第k个时刻的轨迹
并据此计算第k个时刻的轨迹灵敏度
这样,就得到了1条反映参数θj对输出变量yi影响程度的曲线,可以通过式(7)的方式比较各参数的灵敏度:对求取的每个时刻的轨迹灵敏度取绝对值并求和,就可得到参数θj对系统响应yi的影响:
应用上述方法对参数不同的感应电动机数学模型分别进行轨迹灵敏度分析。表1给出了3台典型电动机的参数,其中L为电动机负载率。
本文采用电力系统典型故障(电压小干扰带阻尼震荡以及经历故障切除的暂态电压曲线)下感应电动机的等值阻抗轨迹作为式(7)中的yi来计算各参数的灵敏度均值。结果如表2所示
由表2可以看出,R1,X1,X2,R2和L的灵敏度均值一般较大,这表明其对模型的响应影响较大,而其余的参数Xm,A,C和T1的灵敏度均值都很小,表明其对于模型的响应影响较小。且当电动机参数变化时,各参数的灵敏度均值变化相对较小。因此可将表2中不同电动机各参数灵敏度均值的算术平均值作为各参数的特征权值。结果如表3所示。
在得到各电动机参数的特征权值后,可利用1.1节中考虑特征权值的K-均值聚类算法进行电动机分群计算。
2 基于空转-堵转的等值电动机参数计算
2.1 等值电动机电气参数
在完成多台电动机的分群后,将每个群内的电动机聚合为1台等值电动机(等值机)。在文献[5,6]的基础上,本文提出了一种基于空转一堵转的等值电动机参数计算方法。
在感应电动机空转时,可以认为转差s=0,而当感应电动机堵转时,可认为s=1。这样,就可根据这2种特殊状态来计算等值电动机的参数。
下面以2台电动机为例,说明等值电动机参数的计算方法。2台电动机的等值电路如图2所示,其参数已经归算至同一基准之下。
当电动机堵转时,即s=1,由于Xm远大于X2与R2,可近似认为励磁回路开路。所以2台电动机的等值阻抗可以简化为:
当电动机空转时,即s=0,可近似认为转子回路开路。所以2台电动机的等值阻抗可以简化为:
由式(8)、式(9)可以求出等值机的和,对于等值机定子和转子电抗以及励磁电抗,还需要1个方程。
可近似认为等值机的励磁电抗等于参与聚合的n台机的励磁电抗并联而成。即
由式(8)～式(10)联立即可求得等值机的电气参数。
2.2 等值电动机初始运行滑差
对于等值机的初始运行转差,可由参与聚合的n台电动机的总功率PΣ、负荷节点初始电压V以及前文中计算得到的等值机参数来进行计算。令等值机的功率等于参加聚合的n台电动机功率之和P∑,即可求得等值机的初始运行转差。
其中,
2.3 等值电动机惯性时间常数及机械转矩系数
对于等值机的惯性时间常数及机械转矩系数,可采用式(13)进行计算(以惯性时间常数TJ为例)。
式中:Si为第i台电动机的容量。
其中,
3 算例分析
本文采用Anderson 3机9节点系统对本文提出的方法进行仿真,该系统见图3。对于母线5上的负荷,算例采用恒阻抗负荷与动态负荷相结合的模型。对于母线6和8,其负荷采用恒阻抗模型。
假设母线5上的动态负荷包括了6台感应电动机。其中,居民负荷占42%;工业负荷占58%。各电动机参数如表4所示。
昏先应用基于近似特征值的电动机分群方法对6台电动机进行聚合计算。
各电动机的近似特征值可通过计算-1/(R2TJ)得到[3],结果分别为-33.69,-1 6.23,-3.03,-2.96,-39.68,-37.04。通过分析,可以将它们分为2群,电动机1,5和6分为一个群;2,3和4分为一个群。各群的等值电动机参数如表5所示。
下面用本文提出的方法对6台电动机进行分群,并求取等值电动机参数。
为了便于比较,将6台电动机分为2类(c=2),利用考虑特征权值的K-均值聚类算法对电动机群进行分群计算。得到的各电动机隶属度和各群的聚类中心Ci如表6和表7所示。
由表6可以看出,电动机1,2,3和4属于第一类,电动机5,6属于第二类。这样可以把前4台电动机聚合为1台等值机,后2台电动机聚合为1台等值机。
然后利用第2节中等值机参数计算方法得到各等值机参数如表8所示。
下面分别将传统方法与本文方法得到的等值电动机参数代入系统中进行暂态仿真,并与实际系统的暂态仿真结果进行比较,以此检验聚合方法的正确性与精度。
假设故障是仿真时间为1s发生在线路5-7靠近母线7处,故障类型为三相接地短路。故障清除方式为断开线路5-7。
假设在仿真时间为110 ms时对故障进行清除,发电机1号～3号之间的功角摇摆曲线和母线3的电压曲线见图4、图5。
从图4和图5可以看出,与原6机系统相比,以本文提出的方法对电动机群进行分群和等值后进行仿真,系统的发电机功角与电压的差别较小,相对于根据近似特征值进行分群和综合的计算结果有着明显的改善。
将故障清除时间延长至113 ms后进行仿真,发电机1号～3号之间的功角摇摆曲线和母线3的电压曲线见图6、图7。
将故障清除时间延长为118 ms,发电机1号～3号之间的功角摇摆曲线和母线3的电压曲线见图8、图9。
通过算例可以看出,根据近似特征值进行感应电动机分群的方法在某些情况下并不能区分特性相差较大的电动机,会对电动机聚合效果产生不利影响,尤其是当系统运行在临界情况下时,该方法的误差非常大。从图6可以看出,该方法在113 ms清除故障情况下其仿真结果仍是稳定的,而该情况下精确模型的仿真结果已经出现失稳的情况。当故障清除时间为118 ms时,该方法得到的仿真结果才会出现失稳的情况。
通过考虑特征权值的聚类分析来进行电动机分群,可以有效地消除某些相差较大但又对系统动态响应影响较小的参数对分群效果产生的负面影响,提高了感应电动机群的聚合精度。从仿真结果可以看出,在不同的故障清除时间下,本文方法的仿真结果都有着较好的精度。另外,表9还给出了2种聚合方法与精确模型下的极限切除时间,由表9可以看出本文提出的方法,即在故障下保持系统稳定运行的最大切除时间与精确模型下一致,而传统方法的极限切除时间发生了偏差。因此,本文提出的方法在反映系统临界状态时的动态行为是准确的。
4 结语
本文提出了一种新的电动机聚合方法,通过对电动机动态模型进行轨迹灵敏度分析并求其均值来得到各参数的特征权值,再利用考虑特征权值的K-均值聚类算法来优化电动机分群,并结合基于空转-堵转的等值电动机参数计算方法得到等值电动机的电气和机械参数。
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
关键词：朴素贝叶斯分类器,k-均值聚类,数据挖掘
1 引言
数据挖掘[1]是从大型数据集中将隐含在其中的、人们事先不知道的、对决策有用的知识获取的完整过程。分类是数据挖掘和机器学习中一个重要的研究课题, 它旨在生成一个分类函数或分类模型, 由该模型把数据库中的数据项映射到某一给定类别中, 从而实现对数据的分类。朴素贝叶斯分类器[2] (naive Bayesian classifiers) 是以概率密度函数为基础, 描述分类系统中条件属性和分类属性之间的映射关系。贝叶斯分类器的优点是出错率较小, 但实际上在使用过程中主要存在两个方面的限制:一是先验概率定义困难;二是类别条件独立问题:即独立性假设经常是不满足的。并且独立性假设在一定程度上限制了朴素贝叶斯分类器的适用性, 当处理的数据维数较多, 且数据量较大时, 朴素贝叶斯分类器的效率是偏低的, 且其准确率也有待提高。
针对上述限制, 提出结合k-均值聚类与贝叶斯方法进行分类知识挖掘的解决方案和实现方法。该方法先在数据预处理过程中采用k-均值算法, 得到相互独立的核心属性, 后进行贝叶斯方法的分类知识挖掘。由于k-均值聚类理论的引入, 改善了贝叶斯方法中属性独立性的限制, 提高了分类的准确率。并且由于k-均值算法的引入, 扩大了朴素贝叶斯分类器的应用领域。
2 k-均值聚类算法
2.1 聚类分析
聚类是一个将数据集划分为若干组或类的过程, 并使得同一个组内的数据对象具有较高的相似度;而不同组中的数据对象是不相似的。相似或不相似的描述是基于数据描述属性的取值来确定的。为了实现属性聚类, 通常将一块数据区域A描述成一张表, 在表中有n个对象, 主要是用来存放所有n个对象彼此之间所形成的差异。有矩阵
其中d (i, j) 表示对象i和j对象之间的差异 (或不相似程度) 。通常d (i, j) 为一个非负数;当对象i和j对象非常相似或彼此“接近”时, 该数值接近0;该数值越大, 就表示对象i和对象j越不相似。由于d (i, j) =d (j, i) 且d (i, i) =0, 因此就有上式所示矩阵。
2.2 k-均值算法
k-均值算法以要生成的簇的数目k为输入参数, 把n个对象划分成k个组 (k≤n) , 每个组表示一个簇。首先, 随机地选择k个对象作为初始聚类中心, 而对于所剩下其它对象, 则根据它们与这些聚类中心的相似度 (距离) , 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类;然后再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) ;不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数, 具体定义如下:
其中E为数据库中所有对象的均方差之和;p为代表对象的空间中的一个点;mi为聚类Ci的均值。
k-均值算法试图找到使平方误差准则函数最小的簇。当潜在的簇形状是凸面的, 簇与簇之间区别较明显, 且簇大小相近时, 其聚类结果较理想。该算法复杂度为O (nkt) , 其中n为所有对象的数目, k为簇数, t是迭代的次数, 通常k<<n, t<<n。因此, 对处理大数据集合, 该算法非常高效, 伸缩性好。
3 朴素贝叶斯分类器
每个数据样本均是由为一个n维特征向量, X={x1, x2, …, xn}来描述其n个属性 (A1, A2, …, An) 的具体取值;假设共有m个不同类别, C1, C2, …, Cm。给定一个未知类别的数据样本X, 分类器在已知X情况下, 预测X属于事后概率最大的那个类别。也就是说, 朴素贝叶斯分类器将未知类别的样本X归属到类别Ci, 当且仅当:P (Ci|X) >P (Cj|X) , 对于1≤j≤m, j≠i。根据贝叶斯定理:
由于P (X) 对于所有类为常数, 最大化后验概率P (Ci|X) 可转化为最大化先验概率P (X|Ci) P (Ci) 。若数据集有许多属性和元组, 直接计算P (Ci|X) 的运算量是非常大的。为此, 通常都假设各属性的取值是相互独立的。对于特定的类别且其各属性相互独立, 就会有:, 可以根据数据样本估算P (x1|Ci) , P (x2|Ci) , …, P (xn|Ci) 的值。
根据此方法, 对一个未知类别的样本X, 可以先分别计算出X属于每一个类别Ci的概率P (X|Ci) P (Ci) , 然后选择其中概率最大的类别作为其类别。即朴素贝叶斯分类模型为
4 基于均值的朴素贝叶斯分类算法
基于k-均值算法的朴素贝叶斯分类技术就是利用k-均值算法来研究各列属性之间存在的隐含的依赖关系, 将列属性值进行融合, 达到数据预处理目的, 最后再基于朴素贝叶斯方法进行分类。其处理步骤如下:
1.数据预处理:
(1) 随机地选择k个对象作为初始聚类中心, 而对于所剩下其它对象, 则根据它们与这些聚类中心的相似度 (距离) , 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类
(2) 再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) ;
(3) 不断重复 (1) 、 (2) 直到标准测度函数
通过满足方差最小标准的k个聚类, 将其中相关系数较大的属性合并成一个综合属性。这样随后进行的贝叶斯分类中的各个属性间就能尽可能达到属性独立。
2.基于朴素贝叶斯分类算法进行分类挖掘
通过k-均值算法, 改善了条件属性独立性的限制, 符合朴素贝叶斯分类器的要求。由此可得到改进后的基于k-均值的朴素贝叶斯分类算法:先根据互不相关的核心属性集, 求取类的先验概率P (Ci) ;再由类条件独立的假定, 计算;最后通过上述分类器计算式, 得出分类结果。
5 实验结果及分析
本文中使用NBC表示朴素贝叶斯分类器, KMBC表示基于k-均值算法的朴素贝叶斯分类器。为了测试算法KMBC的效果, 选用了UCI机器学习数据库中的7个典型数据库实例, 数据集的基本信息见表1。实验在WINDOWS XP, J2SDK的平台下完成, 首先补齐决策表, 离散化处理, 在测试过程中同样采用交叉验证法;最后将得到的两种结果进行比较, 结果见表1.
由实验过程及实验结果分析发现, 实验所用的数据实例中, KMBC的分类准确率优于NBC。在算法运行时间上, KMBC略高于NBC, 两者之间运行时间的差别并不明显。
6 结束语
针对朴素贝叶斯分类器的条件独立性假设的限制, 本文提出了一种基于k-均值的朴素贝叶斯算法, 先利用k-均值算法对数据进行预处理, 通过属性合并改善条件属性间的依赖性, 找到一组最近似独立的属性结果, 以符合朴素分类器的算法要求。实验结果表明, 改进后的算法可以达到更精确的分类效果。并且当数据量很大, 而各维属性之间又存在隐含关系是, 改进后的算法是处理这些问题行之有效的方法。
参考文献
[1]han j w.数据挖掘概念与技术[M].北京:机械工业出版社, 2001