快速聚类分析范文

快速聚类分析范文（精选7篇）

快速聚类分析 第1篇

上市公司的经营状况与财务状况往往通过财务指标进行识别与判断, 而上市公司因为其经营不善或是财务问题, 给银行与其他债务人造成的信贷违约风险严重影响了债务人资金的安全性, 导致债务人坏账损失的发生。因此, 对于我国商业银行系统来说, 专业审贷人员是建立在对上市公司财务指标的经验审查之上。这种基于主观判断与定性审查往往是流于形式, 使得对上市公司的信贷违约风险不具备良好的预先识别性。因此, 如果通过现有的财务指标体系, 构造一个具有科学可控、量化有效特征的上市公司信贷违约风险识别机制, 将能够最大限度地为上市公司的债权人与投资者提供有效的决策信息与建议。

我国商业银行对其借款人的信贷违约风险评级主要是传统的模式, 即基于专业人员的定性经验判断之上, 通过“5C”等评价体系对企业信贷对象进行财务状况的审查。即通过对已有的上市公司财务指标进行定量化与系统化处理, 形成对信贷违约风险的可识别机制, 将会提高对上市公司信贷违约风险的识别准确度与预警的效率。而通过对相关文献的梳理与研究发现, 不少学者已经在此领域采取了基于财务数据的模型研究, 本文正是基于这样的思路, 通过公司会计中用得最为广泛的杜邦财务指标来构建上市公司的信贷违约风险模型。实现基于企业财务指标的信贷违约风机制的建立, 使债权人与投资者能对企业债务人的财务风险进行科学的识别、分类、预警。

二、上市公司信贷违约风险评级的财务指标体系

杜邦财务指标体系在企业财务指标体系中广泛使用, 其特点是以权益报酬率为核心的基本财务指标体系, 主要包括偿债能力、营运能力、盈利能力与成长能力的企业经营过程中方方面面的内容。

在财务会计实务中, 采用杜邦财务指标体系中各个指标来衡量企业财务状况 (吴世农, 在“我国上市公司财务困境的预测模型研究”, 2001) 的某一方面或利用各个指标间数量联动关系来衡量企业财务的综合状况, 是比较普遍的财务指标分析法。对于上市公司来说, 基于财务指标的分析被称之为公司基本面分析。但是, 通过单个财务指标或是杜邦财务指标体系的简单联动运用, 难以科学地掌握到对上市公司信贷违约风险发生的核心指标, 也就难以实现对信贷违约风险进行的预测与识别。

本文基于杜邦财务指标体系构建出信贷违约风险评级指标体系, 并参考了相关文献资料, 筛选、设计出上市公司信贷违约风险的指标体系, 为进一步的建模分析提供基础与条件。

三、基于Fisher判别与快速聚类法的评级模型

信贷违约风险评级的对象是将信贷违约风险高的企业从正常经营的企业中识别出来, 即本文研究的对象分为信贷违约风险高的对象与经常经营的企业对象, 这需要利用上市公司的ST企业的警示标识。本文在对拟研究对象进行信贷违约风险评级时, 首先对研究对象进行ST类企业与非ST类企业区分, 以此作为判别分析的基础对象。

(一) Fisher判别模型

1. 从上市公司分为ST与非ST两总体中取得两组P维指标数据值之后, 利用法线产生对应投影值, 由此得到不同信贷违约风险级别的上市公司的对应财务指标特征值。

2. 利用P维指标投影值组成一元方差分析的数据, 构造出组间平方和与组内平方和:

信贷违约风险不同级别的上市公司两总体之间 (存在信贷违约风险警示企业与正常经营的企业) 的组间平方和:

式子中, 即为存在信贷违约风险警示企业的指标均值向量;即为正常经营企业的指标均值向量;为企业总体各指标均值向量。

再通过以上公式, 对两类上市公司内部分别建立平方和公式, 得到各自的组内平方和公式。即通过该步骤找到两类上市公司的财务指标的特征临界值, 对归属于不同级别信贷违约风险的上市公司进行基于财务指标特征的分类、判别。

3. 通过两类上市公司的组间平方和SSG组间, 组内平方和SSG组间构造充分大, 并由此SSG组间/ (M-K) (k-1) a'Ea得到基于上市公司P维综合指标体系判别效力的显著性参数。

(二) 快速聚类模型

聚类分析指将物理或抽象对象的集合组成为由类似的对象集合而成多个类的分析过程, 其目标就是在相似的基础上收集数据来分类。基于上市公司财务指标的Fisher判别模型, 能够充分地识别出高信贷违约风险与正常经营的上市公司的类型, 但对于债权人与投资者来说, 除了对上市公司信贷违约风险01两极的判别, 更有价值的是实现梯级分类, 即不同水平的信贷违约风险一一呈现达到为债权人甄别上市公司信贷风险、为投资者提供上市公司经营与财务问题信息的功能。

1. 聚类分析的原理。将多维财务指标构建出简单的类结构, 并通过距离函数实现类与类之间的相关性测度。

其中Rj, Sj, 分别表示第j个指标的样本均值、样本极差和样本标准差。

基于马氏距离法计算相关性:

其中, x (i) 表示矩阵行向量的转置;Σ是数据矩阵的协方差阵。

2. 适用性。聚类分析是一种基于距离函数的非参数统计分析方法。通过财务指标对象对不同类中心的距离函数进行分类, 具有对事物自然属性判别的客观性。由于, 上市公司具有不同的经营状况与财务情况, 其对应的信贷违约风险也呈现出不同的类别, 尤其是在高信贷违约风险与低信贷违约风险的上市公司之间存在着不同信贷违约风险层次。因此, 利用聚类法可实现同一信贷违约风险警度下上市公司财务指标体系的特征共性分析提供基础, 也可为不同信贷违约风险程度下上市公司财务指标体系的对比分析提供条件。

(三) 实证结果分析

本文通过SPSS18.0, 以20092011年480家ST类企业与487家非ST类企业为判类对象, 基于筛选出的五类一级财务指标, 12个二级指标 (流动比率, 速动比率, 资产负债比率等) 进行基于全局Fisher函数的二类线性判定分析。

1. 基于Fisher判别模型实证结果。

由此建立的上市公司信贷违约风险判别一般式为Z=β0+Σβixi, 其中βi即为上表判别函数系数。得到:

(1) 标准化的典则判别函数。

标准化变量的系数也即判别权重, 用来表示标准化后的各个变量对判别分类的重要性。对于信贷违约风险判类分析来看, 财务指标中的流动比率、速动比率与流动资产周转率表现出在判类分析中较大的判别权重, 说明ST类企业所指明的高信贷违约风险企业的生产经营环节不畅成为企业发生信贷违约的主要特征。

(2) 分类函数。

其中, Z0、Z1为ST类企业、非ST类企业的非标准化判别函数, 分类函数可以计算每个上市公司的判别Z得分, 并根据组质心判断上市公司的信贷违约风险程度从而对其实现分类。

(3) 判类结果。

依据上表错判矩阵可知, 交叉验证 (留一个观测值在外) 实现了86.0%的预测精度。从判类结果看, 基于11个财务指标的信贷违约判别模型对信贷违约风险低的上市公司的判别精度略高于信贷违约风险高的ST类企业 (88.9%>81.7%;88.7%>83.3%) 。

2. 基于快速聚类的信贷违约风险警度评级分析。

根据20092011年上市公司高信贷违约风险的ST类与低信贷违约风险的非ST类判别分析, 得到的判别函数Z得分值作为快速聚类变量, 两类上市公司之中分别进行类别为4类的快速聚类, 得到8类不同级别的信贷风险警度。

即通过20092011年三年的上市公司财务指标构造的信贷违约风险判别模型, 得到的判别Z得分系数, 并通过该系数的快速聚类实现了对上市公司不同信贷违约风险级别的划分。债权人与投资人即可根据对上市公司财务指标体系的信贷违约风险评级标准进行信贷或投资决策。

四、结论与进一步研究方向

显然, 本文通过对上市公司信贷违约风险的评价建模发现, 财务指标体系注重上市公司的经营状况, 其与信贷违约风险相关的杜邦财务指标体系指标 (如资产负债情况, 周转情况) 与公司的经营状况密切相关。由此, 通过反映上市经营状况的财务指标能够识别出企业因经营不善或是流动性不足等问题造成的信贷违约风险, 即通过全局Fisher判别可将高信贷违约风险的ST类上市公司与低信贷违约风险的非ST类上市公司进行精度为86.0%的区分, 实现了对上市公司信贷违约风险的判别。进一步来说, 要对上市公司的信贷违约风险精度再进行区分, 就要利用快速聚类进行不同信贷违约风险的聚类;而利用的划分依据则是基于Fisher判别分析得到的Z函数, 即根据典则判别系数得到的Z得分函数进行信贷违约风险的划分。

财务指标体系是良好的信贷违约风险判别指标, 但存在多个单变量之间的多重共线性, 本文并未单独讨论指标之间的多重共线性问题, 而是容忍多重共线性的存在, 虽然对于模型自身的一致性没有影响, 这对模型的预测精度与评级质心的存在一定的影响。因此本文将继续通过对实证方法的深度挖掘和使用实现进一步的信贷违约风险研究, 以对上市公司的信息使用者提供更为精确的投资判断的信息。

参考文献

[1].周泓, 邱月.交叉熵算法在企业违约风险评估中的应用研究[J].计算机工程与应用, 2008, 44 (20) :13-16

[2].汪冬华.我国上市公司行业分析方法及违约风险预警模型研究[D].华中科技大学, 2004

[3].张智梅, 章仁俊.KMV模型的改进及对上市公司信用风险的度量[J].统计与决策, 2006 (18) :157-160

[4].黄卉.关于我国上市公司违约风险评价效率的研究[J].中国总会计师, 2011 (6) :86-87

[5].蔡薇.KMV模型的修正及对我国上市公司信用风险评估的实证研究[D].对外经济贸易大学, 2010

快速聚类分析 第2篇

关键词：预测,聚类分析,航空分担率,新建机场客运量

0 引 言

在我国,机场业务量的预测受到越来越多的重视,这是由于机场的规划、建设与经营管理都需要以机场航空业务量作为参考依据。新建机场航空业务量预测的最大问题是没有历史航空数据,传统的做法是采用统计调查和相似类比。由于在统计调查和相似对象的选择中,只进行了定性的比较,没有进行深入的定量聚类分析,容易掺杂人为因素的影响,致使调查预测结果与实际出入较大。因此,在新建机场的预测阶段需要选择一种有效的预测方法,这种方法要能够合理、有效地降低预测中的人为因素随意性。

笔者针对我国新建机场航空业务量预测中存在的问题及快速聚类分析的特点,提出了以快速聚类分析为基础的,适用于新建机场航空运输的预测方法.本文从选择交通方式的角度来考虑,利用与新建机场相似的机场的航空分担率,来进行新建机场业务量预测。这种方法考虑到交通方式之间的竞争与协作关系,在一定程度上可以限制机场业务量预测过程中的随意性和人为影响,提高了预测的可靠性。

1 聚类分析

聚类分析实质是一种建立分类的方法,它能够将一批样本数据(或变量)按照他们在性质上的亲疏远近,在没有先验知识的情况下自动进行分类。聚类分析又称群分析,它是研究分类问题的一种多元统计方法,适用于多指标体系的分类。常用的一些方法有系统聚类和快速聚类,本文采用快速聚类分析法进行聚类分析。

快速聚类法又称动态聚类法,它是目前国内常使用的分类方法。且在大样本的情况下,采用快速聚类分析方法比层次聚类分析的计算速度快,结果也比较简洁易懂,因而受到广泛的使用。快速聚类法是根据实际问题的意义先粗略地分一下类,然后再按照某种原则进行修正,直至分类比较合理为止[1]。而在聚类的过程中所分的类数是不变的,即为初始分类的个数。

1.1 多元样品数据矩阵

在多元数据矩阵(如表1所列)中,共有n个样品 (行向),p 个指标(列向)。聚类分析有2种类型:按样品聚类和按变量(指标)聚类。在本文的具体应用中,样品(行向) 代表所选地区,指标(列向) 代表影响航空业务量的因素(如人口密度、地区GDP、人均GDP等),数据元素 代表地区 的指标 的数值。

1.2 样品间的相似性度量距离

设有n个样品的多元观测数据:x1=(xi1,xi2,,xip),i=1,2,,n,这时,每个样品可看成p维空间Rp的一个点,n个样品组成p维空间Rp的n个点。用各点之间的距离来衡量各样品之间的相似性程度(靠近程度)。

设dij是样品xi及xj之间的距离,一般要求它满足下列条件:

1) dij≥0,且dij=0,当且仅当xi=xj时。

2) dij=dji。

3) dijdik+dij。

在聚类分析中,有些距离不满足式(3),在广义的角度上仍称为它距离。定义闵科夫斯基(Minkovski)距离为

当q=2时,dij(2)成为欧式距离:

1.3 快速聚类分析的实施

在构建的多元样品数据矩阵的基础上实施快速聚类分析,具体步骤如下:

1) 指定希望聚成的几类,如:希望聚成K类。

2) 选择初始凝聚点。有2种方法:①用户自行设定,此时用户要对样品有全面的了解;②由SPSS自动指定,系统根据数据样本选择有代表性的样本作为初始类中心。由于对样本了解有限,本文采用第2种方法。

3) 根据最短距离(欧氏距离)原则,将每个样本归类,完成一次迭代。

4) 重新计算类的凝聚点,将类的均值作为新的凝聚点。

5) 重复步骤3)和4),直至指定的迭代次数或达到终止迭代的判断要求为止。

判断是否结束迭代过程的标准有2个,满足其中之一即可结束快速聚类分析过程[2]。它们是:

1)迭代次数等于指定的迭代次数。

2)迭代收敛标准。本次迭代产生的新的类的中心点距上次迭代后确定的类的凝聚点的最大距离小于0.02。

2 实例应用与分析

针对国家拟在内蒙古阿拉善盟地区建设新机场的实际情况,对其进行机场航空业务量预测。从出行选择交通方式的角度来考虑,建立基于聚类分析的航空分担率模型,预测新建机场的航空业务量。

预测时,首先分析、计算出该机场所在地区的航空分担率值,再综合进行交通量预测,应用如下公式可以计算出该地区机场业务量:

机场业务量 =综合交通运输量航空分担率 (3)

在上式中,新建机场的航空分担率,可以通过聚类分析得到相似地区的机场的航空分担率,并对其航空分担率进行统计分析加以修正得到。综合交通运量可以采用运输部门提供的数据,具有一定的权威性和准确性。

2.1 相似机场多元数据矩阵选取

结合阿拉善盟地区的综合情况,将其新建机场定位为支线机场。从国内的同类型机场中(支线机场)选定29个小型支线机场如表2所列,作为聚类对比分析的研究对象。

根据航空运输的影响因素分析,确定机场聚类分析的评价指标体系,选定的定量指标可以依据各城市历年的经济统计数据得到。本文选取人口密度、地区GDP、人均GDP、综合交通运输量和地区交通发展程度5个指标作为聚类分析的评价指标体系,其中综合交通量和地区交通发展程度指标反映了其他交通方式与民航运输的竞争程度。采用2005年的各市地区相关数据进行聚类分析,如表3所列。

资料来源:《中国城市统计年鉴》(2005)。

2.2 相似机场聚类

利用SPSS软件对选定的支线机场进行快速聚类分析。下面是利用SPSS软件进行快速聚类分析结果,如表4所列,分别是样品聚成6类、7类、8类和9类时,阿拉善盟所属类的具体情况。从表4中可以看出阿拉善盟地区与乌海地区的指标状况最为接近,且当聚成9类时两者同属一类。

在ANOVA方差分析表(见表5所列)中,其中有3个变量在所分的类中都出现了明显的差异,所以3个变量在聚类分析中发挥了明显的作用。由于相伴概率F值并没有均大于显著性水平0.05,所以拒绝单因素方差分析的零假设,认为聚类效果理想。

2.3 阿拉善盟地区航空业务量预测

由于阿拉善地区没有航空运输资料可供参考,需借助类似地区的航空分担率。由前面的聚类分析可知,阿拉善盟地区与乌海地区相类似,且乌海机场也是近期新建机场,又同属于一个区域,情况更加与阿拉善盟地区的相似。然后在确定了航空分担率的基础上,利用航空分担率模型来对阿拉善盟地区的航空业务量做出预测。

先要对乌海机场的航空分担率进行验证。乌海机场与嘉峪关机场是相类似地区的机场,查阅民航统计资料,得到2001～2007年嘉峪关机场的航空分担率如表7所列。通过SPSS软件的曲线拟合见图1,找到合适的曲线模型进行预测。通过计算发现幂模型(power)的R2统计量最大,即拟合效果最好。用幂模型进行预测,预测结果如表6所列。

分析嘉峪关机场航空分担率,在修正异常值1.24后,可知实际值与预测值的相对误差绝对值小于8%,预测的精度比较高。同时从上图可以看出,此类地区的机场航空分担率的变化规律,在机场的开始使用时期航空分担率处于快速增长阶段。

乌海机场是2003年12月投入使用,所以采用从2004年起的数据进行研究。2004～2007年乌海机场的航空分担率分别为0.17%,0.35%,0.67%,0.89%。将其与嘉峪关机场的预测值进行比较,可知符合本地区的航空分担率发展趋势。

阿拉善盟地区的机场航空分担率预测值的选取,可以参照此类地区的嘉峪关机场的航空分担率预测值。考虑到航空运输和事业的快速发展,选取该新建机场的航空分担率时,可在嘉峪关机场航空分担率预测值的基础上上浮6%。再结合官方提供的综合交通量数据,利用航空分担率模型预测阿拉善盟地区的航空业务量结果如表7所列。

3 结 语

本文通过航空分担率模型结合聚类分析的相关知识,有效地对未来阿拉善盟地区的新建机场进行航空业务量预测。航空分担率模型充分地考虑各种交通方式之间的协作与竞争,能够更加合理地反应交通需求实际情况。因此,基于聚类分析的航空分担率预测方法是一种有效的预测方法, 从而为机场规划、设计与建设的定量分析提供了很有价值的理论依据。

参考文献

[1]吴翊,李永乐,胡庆军.应用数理统计[M].长沙:国防科技大学出版社,2005

[2]薛薇.统计分析与SPSS的应用[M].北京:中国人民大学出版社,2003

[3]都业富.航空运输管理预测[M].北京:中国民航出版社,2001

[4]中国民用航空总局规划发展财务司.2006从统计看民航[M].北京:中国民航出版社,2006

[5]范潇允.快速聚类分析算法在CRM中客户定位的应用[J].北京:温州职业技术学院学报,2006(9):30-32

快速聚类分析 第3篇

随着医学图像的发展与医生对于人体不同疾病的诊断需求, 医学图像分割技术受到了越来越多的关注和应用。其中模糊聚类技术可以更好地保留图像中的细节信息, 因而在医学图像分割中受到了越来越多的关注。

二、模糊C均值聚类算法FCM

1973年Dunn[1]提出了一种称之为模糊ISODATA的算法, 即模糊度m为2的模糊C均值 (FCM) 聚类算法。1980年, Bezdek[2]对该算法进行一般性归纳, 把它扩展到了模糊度m>1的一般情况, 从而得到了标准的FCM算法。算法的目标函数为:

其中m为FCM算法的模糊度, m>1;c为类别数;n为像素的个数;, xj表示第j个像素, vi为第i个聚类中心, dij表示两者之间的距离;uij为隶属度函数, 表示xj对vi的隶属度, 0uij1。

三、模糊聚类的快速算法HFFCM

3.1利用高斯函数得到初始聚类中心

本文利用高斯函数来对图像的直方图峰值进行多分辨率检测, 以得到的峰值横坐标来作为算法的初始聚类中心, 具体处理过程如下: (1) 得到图像的直方图, 设置模板的初始尺寸为3; (2) 得到规定尺寸的高斯函数模板。把直方图和高斯模板进行卷积, 以实现对直方图信号的平滑滤波; (3) 对卷积后的直方图的峰值进行检测, 如果其个数与所要求的聚类中心个数相等, 则算法停止迭代;否则模板尺寸增加2, 然后算法转入第 (2) 步; (4) 以得到的直方图峰值的横坐标作为快速算法的初始聚类中心。

3.2HFFCM算法

HFFCM算法的目标函数[3]为:

其中L为图像的灰度级;h (k) 为图像的直方图统计;k为灰度值, 其取值范围为0到L-1。使用Lagrange乘子法对算法进行求解, 得:

四、基于自适应理论的快速算法AMFFCM

4.1AMFFCM算法的提出

传统的FCM算法对噪声图像的分割结果质量较差, Zhang[4]等人通过在算法中引入空间信息来对其进行改进, 提出了一种邻域距离约束的DFCM算法, 其目标函数为:

本文利用了DFCM算法的原理, 使用自适应中值滤波理论来加强算法的抗噪性, 同时使用模糊聚类的快速算法HFFCM的处理结果来对算法进行初始化操作, 提出了一种基于自适应理论的快速模糊聚类算法。AMFFCM算法的目标函数如下:

xamj为对像素xj进行自适应中值滤波后得到的像素;α为调节系数, 它的大小决定了算法对滤波项的利用度。使用Lagrange乘子法对算法进行求解, 得:

AMFFCM算法采用快速算法HFFCM的运行结果来对聚类中心进行初始化操作, 使其尽可能地接近最终收敛值, 以此来减少算法的迭代次数, 提高其收敛速度。

(a) 原图像; (b) 叠加了6%高斯噪声的图像; (c) FCM算法分割结果; (d) DFCM算法分割结果; (e) AMFFCM算法分割结果

4.2AMFFCM算法对图像的分割

AMFFCM算法对图像的处理流程如下: (1) 指定初始参数:模糊度m, 聚类数c, 终止参数ε, 调节系数α, 邻域大小Nr; (2) 使用HFFCM算法结果中聚类中心的值来作为AMFFCM算法的初始聚类中心; (3) 对图像进行自适应中值滤波, 其结果以行向量的形式进行排列, 得到xamj; (4) 利用式 (7) 和 (8) 分别计算隶属度矩阵uij和聚类中心vi; (5) 如果条件‖Vt+1-Vt‖<ε成立, 则算法停止迭代;否则重复 (4) 和 (5) , 直到聚类中心V收敛为止; (6) 对得到的隶属度矩阵进行二值化变换, 从而实现对图像的分割。

五、实验

实验所用的脑MR图像来自Brainweb网站的模拟数据库, 尺寸为217*181。算法初始参数为模糊度m=2, 聚类数c=4, 收敛参数ε=0.001, 调节系数α=20, 邻域尺寸Nr=81。图像叠加6%的高斯噪声, 其均值为0, 方差为0.0036。

本文所用分割质量评估参数[5]中, 使用RII, Vpc, Vpe对算法进行聚类有效性评估, 当RII, Vpc取得最大, 而Vpe取得最小时, 该算法就是聚类有效性较好的算法;另外使用误分率对算法进行分割质量评估, 使用分割时间t对算法进行运行效率评估。

图1为FCM、DFCM和AMFFCM算法分别对含6%高斯噪声图像的分割结果。由图看出, FCM算法对噪声基本没有滤除效果, 分割结果质量较差;DFCM算法对噪声的滤除效果较好, 但是图像中区域边缘处有细节信息的损失, 不同区域之间的对比度也比较小。

AMFFCM算法对噪声的滤除效果较好, 同时与DFCM算法相比, 图像边缘处的细节信息损失较少。而且不同区域间的对比度较大, 有助于观察者对不同组织的辨别。、

表1为三种算法分别对含6%高斯噪声图像的分割结果性能参数。FCM算法在图像被噪声污染的情况下, 其误分率较高, 分割质量较差。DFCM算法和本文提出的AMFFCM算法的误分率都较低, 它们的分割结果图像质量较好;对于参数RII, Vpc, Vpe, FCM算法和AMFFCM算法的聚类有效性与分离性较好, 说明结果中不同区域的对比度较大。而DFCM算法的聚类有效性与分离性较差, 结果中不同区域的对比度较小;对于时间参数t, FCM算法和AMFFCM算法耗时较短, 算法的效率较高, 分割速度较快。而DFCM算法的耗时较长, 算法的效率较低, 分割速度较慢。

六、结论

针对传统FCM算法对噪声图像不能进行有效分割的情况, 本文引入自适应中值理论对算法进行抗噪性改进, 同时使用快速算法HFFCM的运行结果来对其进行初始化操作, 提出了一种基于自适应理论的快速模糊聚类 (AMFFCM) 算法。实验结果表明, 该算法对噪声图像的分割效果要优于传统的聚类算法, 同时其分割速度相对于其他抗噪算法也有了一定的提高。

参考文献

[1]J.C.Dunn.A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J].Journal of Cybernetics, 1974, 3 (3) :32-57

[2]J.C.BEZDEK.A Convergence Theorem for The Fuzzy ISODATA Clustering Algorithm[J].IEEE Transactionson Pattern Analysis and Machine Intelligence, 1980, 2 (1) :1-8

[3]李志梅, 肖德贵.快速模糊C均值聚类的图像分割方法[J].计算机工程与应用, 2009, 45 (12) :187-189

快速聚类分析 第4篇

雷达信号分选是从截获到的密集雷达脉冲信号流中分离出属于不同雷达辐射源的脉冲, 是电子支援系统和电子侦察系统的核心组成部分[1], 是电子侦察设备发挥良好性能的重要基础。

传统的多参数雷达信号分选技术是利用脉冲到达方向DOA、脉宽PW、重频PRF、脉冲幅度PA及扫描方式等信息对雷达全脉冲序列进行去交织[2], 而在现代电子战环境中, 随着新体制雷达的不断出现, 出现了高脉冲密度和大量复杂形式脉冲交叠的情况, 传统分选方法效率较低, 容易产生增批和漏批现象。基于此, 文献[3⁃5]提出了基于不同机理的聚类分选方法, 这些方法一定程度上改善了雷达信号分选效果, 但算法复杂度较高, 仍然无法高效满足分选实时性和准确性。本文在研究聚类算法的基础上, 提出了一种联合熵表征聚类因子的锥面映射支持向量聚类雷达信号分选方法, 一定程度上同时确保了雷达信号分选的实时性和准确性。仿真试验结果证明了该方法的有效性。

1 联合熵表征聚类因子的锥面映射支持向量聚类方法

1.1 支持向量聚类

支持向量聚类算法是由Ben⁃Hur等人提出的, 支持向量聚类以支持向量机为工具进行聚类, 其基本思想是:首先通过非线性变换将数据样本从属性空间变换到一个高维特征空间, 再在新空间中求取最优超球面。通过非线性变换增加了数据点线性可分的概率, 能更好地分辨、提取并放大有用特征, 实现更好的聚类。

设雷达脉冲描述向量vi的数据空间V⊆R3, 数据集{v}i⊆V, i=1, 2, ⋯, N。由于脉冲参数分布复杂性, 聚类集合的边界可能非常复杂。选择一个非线性变换Φ, 把数据从V空间映射到高维特征空间, 以使数据点集聚类特征变得更加明显。在特征空间可以得到一个中心为a, 半径为R的最优闭凸球, 半径满足以下约束条件:

式中, a为球心;Φ (v) 是数据空间中数据点v在特征空间中的映像;表示Euclidean范数;ξj为松弛量, 可以使聚类集合变紧。

上述问题的拉格朗日算式为:

式中:C为惩罚因子;βj, μj为拉格朗日算子;为惩罚项。

式 (2) Wolfe对偶形式为:

式中:

引入高斯核函数, q为高斯核的宽度参数。

式 (3) 可以改写成:

对于任何数据向量v, 其映射到特征空间中的像到球心的距离表示为:

满足条件的点组成等高面, 为支持向量 (SV) 。SV位于等高面上, 它确定了属于同一类雷达辐射源参数的聚类边界。

根据KKT条件, 可得出以下结论:

(1) 当满足βi=C处的特征空间的点Φ (vi) 位于最优超球体的外面, 称这样的向量vi为干扰向量或野值向量, 它位于聚类的边界以外。

(2) 在满足0<βi

(3) 其余的点处于聚类边界的内部。

1.2 锥面映射支持向量聚类信号分选

等高面值还不足以很好定义聚类, 为此, 文献[4]提出了SVG聚类分配算法, 文献[5]中的GD算法对其进行了改进。但这些算法分选过程耗时较长, 仍不能很好满足复杂电磁环境中实时快速分选雷达信号的要求。锥面映射支持向量聚类的思想是找出包含支持向量映射Φ (gj) 且覆盖超球体关键部分的锥面, 此锥面对应于数据空间的一个集合超球体, 数据映射点Φ (vi) 的原像vi位于超球体内, 原像点具有较强的类内聚集性, 且满足:

超球体的集合形成一个数据空间等高面的近似覆盖。得到数据空间近似覆盖后, 先对所有支持向量进行聚类, 再根据近似覆盖将聚为同一类的支持向量所对应的其余数据点聚为一类, 完成后续分类。

若定义, 则锥面聚类算法可描述为:

(1) 计算Z;

(2) 计算支持向量对之间的欧氏距离D, 若D<2Z, 把这两个支持向量归为一类;

(3) 重复步骤 (2) , 至所有支持向量完成聚类;

(4) 计算剩余数据点vi与支持向量之间的距离d, 将vi归入距离d最小的类中;

(5) 重复步骤 (4) , 完成所有聚类。

1.3 利用熵表征的聚类因子评判聚类效果

将ESM系统面临的雷达全脉冲环境看做信源, 脉冲环境的复杂度可用信源的不确定度来表示。一般情况下, 信源可用一概论空间来描述, 信源的不确定程度用对应概论空间中可能状态数目及其概率描述[6]。同一辐射信号源具有周期性, 自相似性较强, 而不同辐射信号源相似性则弱。聚类的目的尽量使同一辐射信号源聚为一类。定义联合类内熵为, 联合类间熵为, 其中, n为聚类个数。

定义聚类因子为:

聚类后, 期望类内相似性尽可能大, 即单个类内熵H (Ck) 越小;类间相似性尽可能小, 即类间熵H (Cl, k) 越大。所以, Hcomp (C) 值越小, Hsep (C) 值越大, A值越小, 聚类效果越好。反之, Hcomp (C) 越大, Hsep (C) 越小, 即A越大, 聚类效果越差。

用不同的q值进行锥面映射支持向量聚类, 得到的不同聚类数目为n, n∈[2, N-1]。

因此聚类因子A可以对V划分为n类后的类内相似性和类间分离性有效描述, 可以作为衡量聚类效果优劣的指标。

2 算法实现

联合聚类因子评判进行锥面映射向量聚类雷达信号分选, 流程图如图1所示, 具体步骤为:

(1) 对脉冲描述字采取实时分段处理方法提取子集V;

(2) 对V归一化后进行锥面映射支持向量聚类预分选, 并根据聚类因子A, 调整聚类参数q;

(3) 根据最优聚类参数实现最终聚类分选, 并再次用聚类因子A对聚类效果评判, 动态更新聚类库。

3 仿真结果分析

为了验证该分选方法的实时性和有效性, 本文仿真一系列雷达脉冲数据并对其进行预处理, 处理后试验数据如表1所示。将熵表征的聚类因子A与DB指标[7]和PS指标[8]对聚类的有效性情况进行了比较, 结果见表2。

其中数据集1, 数据集2为雷达脉冲数据子集, 依次选取为1~150, 150~300个样本。文献[7⁃8]分别指出DB和PS值越小时, 聚类最优。而从表中可看出数据集1, PS指标最小时, 聚类结果为3类信号源, 而实际信号源为2类。数据集2, DB值最小时, 对应的为3类信号源, 而实际信号源为4类。二者都没有很好地确定聚类数目和最佳q值, 而本文提出的熵表征聚类因子A可准确地进行最优聚类效果评判。

表3列出了聚类因子指标下, 本文方法与SVG、GD和SVC[6]分选方法的正确率和耗时对比。其中正确率= (总脉冲数-漏选脉冲-错选脉冲) 总脉冲数100%。

4 结论

为满足雷达电子对抗的实时性、准确性要求, 准确快速实现雷达信号分选, 本文将锥面映射支持向量聚类算法应用到复杂电磁环境下的雷达信号分选当中, 同时利用基于熵表征的聚类因子进行聚类有效性调整验证。仿真结果表明, 该方法在保证信号分选正确性的同时, 能很大程度地减少信号分选过程中消耗的时间, 提高分选实时性。

参考文献

[1]WILEY R G.ELINT:the interception and analysis of radar sig nals[M].Second Edition.Boston:Artech House, 2006:317356.

[2]MILOJEVIC D J, POPOVIC B M.Improved algorithm for the deinterleaving of radar pulses[J].IEE Proc, F:Comm, Radar and Signal Processing, 1992, 139 (1) :98-104.

[3]祝正威.雷达信号的聚类分选方法[J].电子对抗, 2005 (6) :6-10.

[4]BEN HUR A, HORN D, SIEGELMANN H T, et al.Support vector clustering[J].Journal of Machine Learning Research, 2001 (2) :125-137.

[5]LEE J, LEE D.An improved cluster labeling method for sup port vector clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 2005, 27 (3) :461-464.

[6]国强, 王长虹, 李峥.支持向量聚类联合类型熵识别的雷达信号分选方法[J].西安交通大学学报, 2010, 44 (8) :63-67.

[7]DUNN J C.Well separated clusters and optimal fuzzy partitions[J].Journal of Cybernetics, 1974 (4) :95-104.

快速聚类分析 第5篇

机器人视觉技术是近年研究最热门的课题之一, 为了提高采摘机器人的果实识别性能,越来越多的采摘机器人开始采用双目视觉系统对果实进行定位。 机器人双目视觉系统人眼观察物体的方式很相似,利用两台相隔一定距离的两台摄像机所获取的图像的差异,运用三角测距原理得到果实的有关位置的三维信息,这就是所谓的双目视觉系统。但是,由于双目视觉系统得到的视频数据较大,如果单纯对果实视频图像进行提取,得到的果实彩色图像数据量较大,并且包含噪声也比较多,不利于果实信息的提取。基于此,需要通过处理算法对图像进行量化,提高图像的处理速度,从而提高机器人对果实的定位速度。

1总体设计

视频对象提取快速定位果实采摘机器人的数据主要包括机器视觉系统、机械手执行末端、手腕等关键和行走机构。其中,机器视觉系统主要由彩色摄像头和图像处理卡组成,可以识别成熟的果实; 机械手执行末端主要是使用胶手指和气动吸嘴,腕关节可以把果实摘取而不损伤果实; 行走机构可以保证机器人在田间自由行走,其总体设计如图1所示。

设计原理: 使用视频采集技术采集果实的视频, 然后利用聚类算法对视频图像进行色彩聚类,得到果实的质心位置,并建立一个位置识别数据库; 最后对各个位置参考点发出动作指令,使用PC机对执行末端进行变频调速。其中,位置识别数据库的建立流程如图2所示。

在机器人进行定位时,利用RSSI定位技术对果实的位置进行预测,将得到的位置矢量和数据库中的位置进行比较,从而得到最佳的匹配结果。

2结构和控制算法设计

为了实现果实采摘机器人的快速定位,需要对果实采摘机器人的视觉系统进行改进,将2个摄像头安装于末端执行器上,组成定位系统,机器视觉系统如图3所示。

机器视觉系统的改进在于使用一种视频对象处理方法,可以实时地实现视频对象的提取,高效地完成果实的定位。其中,摄像头A安置在机械手的正下方,摄像头B安置在机械手的侧端,两个摄像头使用CMOS摄像头; 其分辨率为1 024 × 680,可以拍摄视频的范围为1 760mm × 1 320mm。图4为机器人的定位过程示意图。

其以作业面向垄面建立笛卡尔坐标系,垄面向右方为X轴正方向,垄面的下方为Y轴正方向,垄面的垂直方向为Z轴正方向; 在Z方向上,目标与爪钳根部的坐标差值,即为末端执行器与目标的距离D。机器人定位过程中,首先利用双摄像头获得果实视频信息,然后从视频中提取果实对象图像,从而确定其在平面内的位置和姿态,并利用图像信息调整机器人的位置和姿态,使机器人接近果实; 然后利用不断的定位过程对果实进行追踪,从而完成果实的采摘。机器人的位置和姿态控制主要有两种方案,一是利用正运动学,二是逆运动学。对于果实目标的锁定,需要根据双摄像头得到的视频来提取果实对象,在提取果实对象前需要对视频进行处理,得到降低图像的色彩数便于提取。目前,色彩控制主要使用的是RGB、HSL、 YUV和Lab,与人眼视觉特征比较匹配的是Lab色彩空间。其中,L表示色彩的亮度,其取值范围为[0, 100]; a表示色彩的红绿程度,其取值范围为[- 128, 127]; b表示色彩的黄蓝程度,其取值范围为[- 128, 127 ]; Lab空间是基于XYZ空间的,从XYZ空间到Lab空间的变换为

当Y/Yn>0.008 856时,有

当Y/Yn≤0.008 856时,有

其中,f(t)=7.781t+16/156,Xn、Yn、Zn是对应的D65中的白光。在Lab空间内,两个颜色的欧式距离可以表示为

当 ΔS > 5时,颜色间是存在区别的。对图像进行滤波后,可以利用聚类算法对色彩进行聚类,其中质心的表达式可以表示为

其中,x( n) 表示像素点,失真度的表达式为

根据Fisher判断准则,对于每个点x0( n) 都可以得到的m( n) 值,假设

每个像素点的权重可以表示为

则质心的表达式可以改进为

将失真度也引入权重的概念,表达式改为

根据质心位置可以对果实图像进行定位,机器人可以通过位置和姿态的调整来实现机器人作业轨迹和图像轨迹的重合。为了实现位置和姿态调整,将输出力矩、输出精度、规格重量、供电电压、等各方面规格进行综合考虑,选用了松下公司的交流伺服电机, 如图5所示。

图5中,主要考虑的参数包括电池容量、输出功率和转矩、最大转矩、额定和最大电流以及最高转速,其参数的具体选择如表1所示。

为了满足定位执行末端伺服电机的需要,通过计算对伺服电机的性能参数进行了设计,变速箱的设计如图6所示。

伺服电机在工作时,需要实现低转速大力矩的输出,因此减速箱的设计也需要配合这一力学性能,根据机器人结构和力学性能进行综合考虑,选择了HMK型减速箱。

3果实采摘机器人测试

为了验证设计的视频对象提取快速定位机器人的有效性和可靠性,对机器人的性能进行了测试,测试项目包括图像处理和果实定位。机器人果实采摘测试的场景如图7所示。

在机器人上装有机器视觉系统,在头部安装有高清摄像头,在机身部位安装了图像处理系统,可以有效地实现聚类算法的视频对象提取。通过对象提取和聚类中心计算,得到了如图8所示的果实定位图像。

对苹果图像进行编码,利用不同的编码可以实现果实的自动轨迹跟踪。为了验证聚类算法的优越性, 对不使用聚类算法和使用聚类算法的RSSI定位进行测试,得到了如图9所示的结果对比曲线。

由图9可以看出: 随着作业时间的增加,定位追踪轨迹逐渐和图像轨迹靠拢,定位精度逐渐增加,而聚类算法的定位精度要明显比不使用聚类算法的好。

表2表示使用聚类算法和不使用聚类算法机器人每次定位用时结果对比曲线。由表2可以看出: 使用聚类算法后,机器人定位的时间明显缩短,从而提高了机器人的作业效率。

s

4结论

1) 依据聚类算法和视频提取技术,对果实采摘机器人的视觉系统进行了改进,并在视频对象提取过程中引入了Lab色彩空间的聚类算法,在图像滤波后可以有效地计算果实质心的位置,完成果实的定位,提高了机器人的定位速度和定位精度。

快速聚类分析 第6篇

聚类用来发现数据内在结构,将数据对象集合划分成多个簇,使得在同一个簇中的对象之间具有较高的相似性,而在不同簇中的对象之间具有最大程度的总体差异性(Han et al,2001)。聚类技术无需先验知识进行样本训练,就能够从数据中获取有价值的信息。聚类广泛应用于模式识别、遥感数据分析、图像处理和市场研究等领域。例如商业上,市场分析人员运用聚类发现客户资料库中的各种客户群及其购买模式,以支持准确而有针对性的营销策略制定。经典聚类算法可分为:划分技术(基于初始随机划分进行迭代求精的算法)[7],混合模型方法(与密度估计相关的算法)(McLachlan & Basford,1988),层次聚类(利用数据间层次关系的算法)(Hartigan,1975;Holschneider & Tchamitchian,1990;Kaiser,1994;Kaufman & Rosseeuw,1990;Kohonen,1988)等。

PAM是一种常用的基于k-中心点的聚类算法。其优势为:对噪声点/孤立点不敏感,具有较强的数据鲁棒性;聚类结果与数据对象点输入顺序无关;聚类结果具有数据对象平移和正交变换的不变性等。但是,该算法缺陷在于聚类过程的高耗时性。

对于大数据集,PAM聚类过程缓慢的主要原因在于:通过迭代来寻找最佳的聚类中心点集时,需要反复地在非中心点对象与中心点对象之间进行最近邻搜索,从而产生大量非必需的重复计算。

基于矢量量化码字搜索中的一些思想,可以用来降低K-Medoid算法计算复杂性。比如:码字搜索算法中的部分距离搜索,先前中心点标号,和三角不等式消除准则等。文献[1]提出一种在CLARANS算法上应用这些混合搜索策略的有效算法,极大地提高聚类效率。但是,这些码字搜索算法尚未被应用到PAM算法以此提高算法效率。

本文提出的快速PAM聚类算法,通过混合利用部分距离搜索(PDS),先前中心点标号(PMI)和三角不等式消除(TIE)准则等搜索策略来降低计算复杂性,极大地改善了PAM算法的性能。实验结果表明,与基本PAM聚类算法相比,本算法的优势在于:在保持聚类效果的情况下,能够减少70%～90%的乘法计算量,并可节省约1/3以上的计算时间。

1 PAM算法思想分析

1.1 PAM算法基本思想

PAM算法是一种基于划分方法的经典聚类算法。该算法的目的在于对n个数据对象给出k个划分。

为了找出k个最佳中心点,PAM算法反复地用一个非中心点对象Oh替换一个中心点对象Oi,以试图提高聚类质量(聚类质量由各个对象与所属簇的中心点之间的平均相异度度量)。

PAM算法分四种情况计算Oh替代Oi时各个非中心点数据对象Oj的相应代价Cjih(假设Oj2是另一个中心点数据对象):

1) 若Oj属于Oi代表的簇,并且因为d(Oj,Oj2)d(Oj,Oh),而分入Oj2所代表的簇,则:Cjih=d(Oj,Oj2)–d(Oj,Oi);

2) 若Oj属于Oi代表的簇,并且因为d(Oj,Oh)<d(Oj,Oj2),而分入Oh代表的簇,则:Cjih=d(Oj,Oh)–d(Oj,Oi);

3) 若Oj不属于Oi代表的簇,而属于Oj2所代表的簇,并且因为d(Oj,Oj2)d(Oj,Oh),而分入Oj2所代表的簇,则:Cjih=0;

4) 若Oj不属于Oi代表的簇,而属于Oj2所代表的簇,并且因为d(Oj,Oh)<d(Oj,Oj2),而分入Oh所代表的类,则:Cjih=d(Oj,Oh)–d(Oj,Oj2)。

上述4种情况如图1所示。

并计算替换所产生的总代价TCih:

${\rm T}C{}_{ih}={\displaystyle \sum _{j=1}^{n-k}C}{}_{jih}(1)$

若TCih<0,则表明执行该替换可以改善聚类质量。算法利用Oh替代Oi成为新中心点,然后重新聚类。

1.2 PAM算法过程描述

1) 从n个输入数据对象中随机选择k个对象作为初始中心点;

2) 为每一组数据对象交换对Oi(中心点),Oh(非中心点)计算总代价TCih;

3) 找出所有交换总代价TCih中的最小值minTCih;若minTCih<0,则用Oh替换Oi,形成新的中心点集,然后转2,继续迭代;

4) 最后对(n-k)个非中心点数据对象进行聚类分配,给出正确的划分结果。算法停止。

分析步骤2可知,对于每次迭代需要确定出k(n-k)组数据对象交换对,而对于每组交换对计算总代价TCih时,需要计算(n-k)个非中心点数据对象Oj的相应代价Cjih;因此每次迭代总的时间复杂度为O(k(n-k)2)。算法迭代的总次数可能很大,由此可知,当n和k的值较大时,PAM算法的计算代价相当高。基于距离计算次数考量,PAM计算复杂性为O((1+β)k2(n-k)2),其中β为数据对象交换的成功次数。

2 基于PDS/PMI/TIE的快速PAM算法

为了降低PAM算法计算复杂性,本文提出的快速算法利用基于矢量量化(VQ-based)码字搜索思想来提高算法效率,包括:部分距离搜索(PDS),先前中心点标号(PMI)和三角不等式消除(TIE)准则等。

采用欧氏距离,对于d维的非中心点数据对象Oj={Oj1,Oj2,,Ojd}和中心点数据对象Oi={Oi1,Oi2,,Oid}与Oh={Oh1,Oh2,,Ohd}有:

2.1 部分距离搜索(PDS)

对于距离值:

$D{}_{\min }=D({\rm O}{}_j,{\rm O}{}_i)={\displaystyle \sum _{t=1}^d(}{\rm O}{}_{jt}-{\rm O}{}_{it}){}^2(2)$

如果存在1kd,满足:

${\displaystyle \sum _{t=1}^k(}{\rm O}{}_{jt}-{\rm O}{}_{ht}){}^2\ge D{}_{\min }(3)$

则: D(Oj,Oh)≥D(Oj,Oi) (4)

PDS算法[4]是一种简单有效的码字搜索思想。该算法在部分和超过当前最小值时,就立即停止对象间的差异度计算,从而减少重复计算。此时,在额外h次比较运算之下,可节省(d-k)次乘法运算和2(d-k)次加法运算。

2.2 三角不等式消除(TIE)准则

已知距离满足不等式:

D(Oj,Oi)+D(Oj,Oh)≥D(Oi,Oh) (5)

如果有: D(Oi,Oh)≥2D(Oj,Oi) (6)

则: D(Oj,Oh)≥D(Oj,Oi) (7)

该推论表明TIE准则[5]:如果非中心点Oj到某个中心点Oi距离值小于等于Oi与另一个中心点Oh之间距离值的一半,那么Oj离中心点Oi更近一些。

为了利用TIE准则,本文算法首先计算并保存各中心点之间的距离值表。在聚类过程中,对于非中心点Oj,如果满足式(6),则直接分配到Oi所在簇,而不必计算Oj与Oh之间的距离,从而减少大量重复计算。

2.3 先前中心点标号(PMI)

PAM算法通过重复检验并交换中心点与非中心点,以改善聚类质量。认真分析该交换过程可知,在实际应用中,当非中心点Oh替换当前中心点Oi时,仅有少量数据对象的结果簇会改变,而大多数数据对象并不受影响。

快速PAM算法结合该事实,利用上一次聚类结果的中心点信息,来减少大量不必要的重复计算。算法首先计算非中心点与先前中心点之间的距离值,由于数据对象聚类结果簇保持不变的可能性很高,因此该距离值相对较小。此时可进一步利用PDS和TIE算法来降低距离计算量,提高效率。

2.4 快速PAM算法过程

综合利用上述的PDS/TIE/PMI搜索策略,本文的快速PAM算法主要步骤描述如下:

(1) 初始化

1) 随机选择k个数据对象作为初始中心点集;

2) 计算并保存各中心点之间的距离值表TM;

(2) 迭代求解最佳中心点替换方案

为每一组数据交换对Oi(中心点),Oh(非中心点)执行:

1) 对于每个非中心点数据对象Oj:

a) 计算Oj与先前中心点之间的距离值Dmin;

b) 利用Dmin值,TM表,PDS和TIE,求出离Oj最近的两个中心点;

2) 计算本交换对对应的总代价TCih;

(3) 执行最佳替换方案

选择具有MinOi,Oh(TCih)值的数据对象交换对。若minTCih<0,则:

1) 以Oh替换Oi成为新中心点;

2) 更新距离值表TM;

3) 转步骤2,继续迭代;

(4) 最后对(n-k)个非中心点数据对象进行聚类分配,以给出正确的划分结果。

算法停止。

3 实验结果

3.1 数据集及性能评价指标

实验在PC机(1.7G CPU,512M RAM)上进行;选用UCI数据集Iris,Wine,Ionosphere和LetterRecognition;实验时以基本PAM算法为参照,并在算法收敛时,考察每次迭代过程所需的平均乘法次数和平均运行时间。

3.2 实验结果及分析

分两组进行实验:首先考察快速算法对Iris,Ionosphere,Wine数据集聚类性能改善情况,验证算法有效性;第二组实验从LetterRecognition随机抽样形成不同子集,用于考察新算法在各种不同的N(数据集规模),d(数据对象维数),k(聚类数)值时聚类效率提高程度。

第一组实验:取k=3,对Iris,Ionosphere,Wine数据集,分别运行快速PAM算法和传统PAM算法各50趟。并分别统计算法收敛时所需平均乘法次数(乘法计算量),平均运行时间(计算时间),进行性能评估。统计结果如表1和图2所示。

从表1和图2可知,相对于传统PAM算法,快速PAM算法能够大幅降低算法所需“乘法计算量”与“计算时间”,表明该快速算法的有效性。

第二组实验,按照下列几种情况进行:

(1) 从LetterRecognition随机抽样形成样本数目为500,600,700,800,900,1000,1100,1200的不同规模的数据子集。然后取K=3,分别运行快速PAM算法和传统PAM算法各50趟,并分别求出算法的“乘法计算量”和“计算时间”作为算法性能指标。实验结果表明,快速PAM算法分别节省了92%,92%,92.3%,92.1%,92.2%,92.1%,92%,92.1%的乘法计算量,如图3(a)所示。计算时间的效率提高程度如表2(a)所示。

(2) 从LetterRecognition随机抽样并降维后形成样本数目为1200、维数分别为4,6,8,10,12,14,16的子集。然后取K=3,分别运行快速PAM算法和传统PAM算法各50趟,并分别求出算法的“乘法计算量”和“计算时间”作为算法性能指标。实验结果表明,快速PAM算法分别节省了73.5%,81.6%,85.9%,88.6%,90%,90.9%,92%的乘法计算量,如图3(b)所示。计算时间的效率提高程度,如表2(b)所示。

(3) 从LetterRecognition随机抽样形成样本数目为1200的子集。然后分别取K=3,5,7,9,11,13,15,17,分别运行快速PAM算法和传统PAM算法各50趟,并分别求出算法的“乘法计算量”和“计算时间”作为算法性能指标。实验结果表明,快速PAM算法分别节省了92%,93%,93.3%,93.5%,93.6%,93.6%,93.7%,93.7%的乘法计算量,如图3(c)所示。计算时间的效率提高程度,如表2(c)所示。

从表2和图3可知,对于各种不同的N(数据集规模),d(数据对象维数),k(聚类数)值,本文提出的快速PAM算法能够很好地提高算法效率:在节省“乘法计算量”约70%～90%的同时,可节省约40%～90%的“计算时间”。

3.3 快速PAM算法的性能优势

C.Elkan[2]提出了一种利用TIE准则来加速k-means的聚类算法;该算法报告的乘法计算效率提高程度如表3所示。

Q.P.Zhang等[3]提出利用一种成为CLATIN的PAM改进算法。该算法通过构造中心点集的三角剖分网络(TIN),来避免重复计算量,进而实现提高效率,实验结果如表4所示:

通过比较实验数据可知,本文的快速算法对乘法计算量的效率提高程度与C.Elkan提出的加速k-means算法相当;而对运行时间的效率提高程度,则明显优于Q.P.Zhang等提出的CLATIN算法。

因此新算法具有更大的实用价值,可用于各种聚类场合以提高速度,比如在语音码书识别应用中提取语音码书等。

4 结 论

提出一种有效的快速PAM聚类算法。该算法通过综合使用PDS,TIE,PMI等搜索策略,对基本PAM算法中心点替换过程中的最近邻搜索进行有益的改进,很大程度地弥补了该算法的高耗时性缺陷。实验结果表明本算法在性能上取得了很大提高。本文所提出的快速PAM算法能够减少70%～90%的乘法计算量。并可节省约1/3的计算时间。今后进一步研究方法来降低本文提出的快速PAM算法可能需要的条件控制开销。

摘要：PAM(Partitioning Around Medoids)是一种基于k-中心点的聚类算法,在处理数据集聚类时,具有较强的鲁棒性和准确性。但是,PAM算法的主要缺点是确定聚类中心点集所需的计算代价太高。对于大数据集,PAM聚类过程缓慢。提出一种利用部分距离搜索(PDS),先前中心点标号(PMI),以及三角不等式消除(TIE)准则等搜索策略来降低中心点迭代所需计算复杂性,实现快速PAM聚类的新算法。实验结果表明,相对于基本PAM聚类算法,在保持相同聚类效果的情况下,快速PAM聚类新算法能够减少70%～90%的乘法计算量,并可节省约1/3以上的计算时间。

关键词：聚类方法,PAM算法,搜索策略(PDS/PMI/TIE),计算复杂度

参考文献

[1]Chu S C,Roddick J F,Pan J S.An Efficient K-Medoids-Based Algo-rithm Using Previous Medoid Index,Triangular Inequality Elimination Criteria,And Partial Distance Search.DaWak2002,LNCS2454,2002:63-72.

[2]Elkan C.Using The Triangle Inequality To Accelerate K-Means.Pro-ceedings of the Twentieth International Conference on Machine Learn-ing,Washington DC,2003.

[3] Zhang Q P,Couloigner I.A New And Efficient K-Medoid Algorithm For Spatial Clustering.ICCSA 2005,LNCS 3482,2005:181-189.

[4]Bei C D,Gray R M.An Improvement of the Minimum Distortion Enco-ding Algorithm For Vector Quantization.IEEE Transactions on Commu-nication,1985,33(10):1132-1133.

[5]Chen S H,Pan J S.Fast Search Algorithm For VQ-Based Recognition Of Isolated Word.Communications,Speech and Vision,IEE Proceed-ings I,1989,136(6):391-396.

[6]Ng R T,Han J W.CLARANS:A Method For Clustering Objects For Spatial Data Mining.IEEE Transactions on Knowledge and Data Engi-neering,2002,14(5):1003-1016.

[7] Kaufman L,Rousseeuw P J.Finding Groups In Data:An Introduction To Cluster Analysis.John Wilsy & Sons,1990.

聚类分析综述 第7篇

关键词：数据挖掘,无监督学习,聚类分析,电子病历

0 引言

在人类历史上, 计算机的出现使人类的生产工具发生了极大的变革, 这是因为计算机的运算速度和数据存储能力都远远超过人类的大脑。现代信息化的社会中, 每天产生极大的数据量, 这些数据有些是有用的, 有些是无用的, 如何从海量的数据中提取有用的信息是计算机科学家一直以来探索的难题。数据挖掘就是一种从海量的数据中通过某种算法找到隐藏于其中的信息的技术, 它通常与计算机科学有关, 通过统计、机器学习、模式识别、在线分析处理、情报检索等多种方法来达到挖掘信息的目的[1]。

将挖掘出的信息用于计算机推理、学习, 使计算机能够像人类一样进行学习, 就是机器学习的领域。机器学习[2]就是计算机利用已有的数据, 得出某种模型, 并利用模型来预测未来的一种方法, 这种方法很类似于人的思考方法。随着计算机技术的高速发展, 机器学习已经变成人工智能研究的一个重要领域。机器学习有很多种方法, 包括有监督学习、无监督学习、半监督学习和强化学习。无监督学习事先没有任何训练样本, 需要直接对数据进行建模, 计算机自己发现数据中存在的内在关系。看起来无监督学习非常困难, 因为这是一个计算机自己摸索的过程, 但事实上并不是所有的训练样本的输入都分类正确, 因此会出现问题, 会导致过适合 (over-fitting) , 这个时候无监督学习就是适合的算法, 也因此无监督学习在数据挖掘中具有相比其他方法更为广阔的应用前景[3]。

无监督学习主要有两种方法, 关联规则与聚类分析。聚类分析是无监督学习中的更常用的形式。本文围绕无监督学习的聚类分析进行综述, 首先介绍聚类分析的定义, 之后围绕聚类分析的算法介绍它的具体步骤和算法以及应用现状。

1 聚类分析的定义

所谓聚类分析, 就是根据待分类模式特征的相似或相异程度将数据样本进行分组, 从而使同一组的数据尽可能相似, 不同组的数据尽可能相异[3,4]。它的目的是用于知识发现而不是用于预测。评判聚类结果的标准就是:组内部的数据相似度越大, 组与组之间数据的差异度越大, 那么聚类效果就越好[5]。聚类分析在计算机科学方面的应用范围非常多, 包括模式识别、数据分析、文本挖掘等[6]。

2 聚类分析的算法

已知的聚类分析算法有很多种[7], 同时各种聚类方法也在被科学家不断地提出和改进, 在实际应用中聚类算法的选择取决于待评判数据的类型和聚类的目的, 不同的算法适合于不同类型的数据。根据近年来出现的各种聚类方法的特点, 常用的聚类算法可用被分成四种:基于划分的聚类算法[8]、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法等[9,10]。

2.1 基于划分的聚类算法

基于划分的聚类算法是在机器学习中应用最多的。它的原理是:假设聚类算法所使用的目标函数都是可微的, 先对数据样本进行初步的分组, 再将此划分结果作为初始值进行迭代, 在迭代过程中根据样本点到各组的距离反复调整, 重新分组, 最终得到一个最优的目标函数。最终的聚类结果出现在目标函数收敛的情况下[3]。

K-means算法是基于划分的聚类算法中的经典算法之一。它的步骤可概括如下:

(1) 任意选择k个样本点作为初始的组中心;

(2) repeat;

(3) 根据组中样本点的平均值, 将每个样本点 (重新) 赋予距离最近的组;

(4) 更新样本点的平均值, 即计算每个组中样本点的平均值;

(5) until不再发生变化[11]。

K-means算法之所以成为经典算法, 是它具有的优势决定的: (1) 时间复杂度与数据集大小呈线性关系, (2) 它收敛于局部最优解。没有一种算法是完美的, K-means算法也具有它自身的确定: (1) 传统的K-means使用欧氏距离, 仅适用于球形数据, (2) 对噪声和孤立点较为敏感。

除了K-means算法之外, 常用的基于划分的聚类算法还有K-medoid[12]、K-modes和K-prototypes[13]等算法。

2.2 基于层次的聚类算法

基于层次的聚类算法也是一种非常常用的算法, 它使用数据的联接规则, 通过层次式的架构方式, 不断地将数据进行聚合或分裂, 用来形成一个层次序列的聚类问题的解[14]。在层次聚类中, 组间距离的度量方法选择很重要, 广泛使用的组间距离度量方法包括:最小距离、最大距离、平均值的距离、平均距离。

按照层次分解的两种顺序, 自顶向下和自底向上, 层次聚类算法可以被分为两类, 一类是凝聚的层次聚类算法另一类是分裂的层次聚类算法[15]。目前, 凝聚的层次聚类算法有Karypis等[16]提出的CHAMELEON、Guha等提出的ROCK[17]和CURE[18]等;分裂层次聚类算法有Steinbach等[19]提出的bisectingK-means、Boley等[20]提出的PDDP等。

基于层次的聚类算法是一种很优秀的算法, 它的优势在于用户不用预先指定聚类分组的数目, 而且能够清晰的表达组与组之间的层次关系。同样, 它也有自身的缺点, 包括两个方面, 一个是在层次聚类过程中, 上一层次的组形成后, 不能在后续的聚类过程中对其进行调整, 即不能回溯[21]:第二点是大多数层次聚类算法的计算复杂度至少为O (N2) (其中N是数据点的数量) , 这导致层次聚类算法在处理大规模数据时十分低效。

2.3 基于密度的聚类算法

基于密度的聚类算法, 是用密度取代数据的相似性, 按照数据样本点的分布密度差异, 将样本点密度足够大的区域联结在一起, 以期能发现任意形状的组[6]。这类算法的优点在于能发现任意形状的组, 还能有效地消除噪声[3]。基于密度算法常用的有包括DBSCAN[22], OPTICS, DENCLUE等。

2.4 基于网格的聚类算法

基于网格的聚类算法, 它的原理是把量化的网格空间进行聚类法, 这个算法一般与数据集的大小没有关系, 计算时间复杂度只取决于网格单元的数量。基于网格的聚类算法的优点在于它可以大幅提高计算效率;而缺点在于它很难检测到斜侧边界的聚类, 只能针对垂直或水平的聚类。常见的基于网格的聚类算法有STING[23]、Wave Cluster[24]、CLIQUE[25]等。

3 无监督学习在电子病历挖掘中的应用现状

电子病历是指医务人员在整个病人的诊疗过程中, 使用专门的医院信息系统产生的针对每一个患者个体的数字化的诊疗记录[26]。通过计算机手段对电子病历中的信息进行提取和分析, 从中得到有助于构建临床决策支持系统和个性化医疗服务的数据在医疗大数据的时代有重要意义[27]。目前针对电子病历主流的挖掘方法是基于词典的方法和基于有监督学习的方法, 前者过于依赖词典后者需要人工标注语料作为训练数据, 而无监督学习克服了上述两种问题, 因此基于无监督学习-聚类分析的电子病历挖掘得到了广泛的应用。

自动分词是分析和挖掘中文电子病历的关键基础, 张立邦等[28]提出了一种基于无监督学习的中文电子病历分词方法, 在3000份电子病历上面的实验结果证明了该方法的有效性。史柏语等[29]运用无监督学习的方法, 对甲状腺肿瘤的手术情况进行了建模, 分析得出手术范围随病灶淋巴结转移而扩大, 但不受病灶本身大小的影响。丁卫平等[30]提出了一种基于约束关系的改进核聚类算法, 用来解决电子病历中图像切割的问题, 该算法通过引入约束关系在图像分割前进行修正, 提高图像分割效果。栗伟等[31]提出了一种自适应的文本聚类方法, 用来解决电子病历中疾病诊断文本同义词识别和命名标准化问题, 该算法能够自动确定类簇个数, 并且提升了聚类的准确性。张焕君等[32]提出了一种模糊聚类分析方法, 用来解决医疗信息的复杂性和不确定性, 对电子病历数据进行综合处理分析。他采用了减法聚类产生初始聚类中心, 再进行模糊C均值聚类算法, 以实现模糊C均值聚类过程中的聚类中心。

4 总结