基于非度量多维缩放的聚类组合算法

文章编号:1001-9081 (2018) Sl-0067-06

ISSN 1001-9081

CODEN JYIIDU

2018-06-15

http: //www. joca. cn

基于非度量多维缩放的聚类组合算法

周文娟'赵礼峰

(南京邮电大学理学院，南京210023)(*通信作者电子邮箱493793682@ qq.com)

K-Means聚类中维数高，非度量型数据分析亟待解

决的问题，提出一种基于非度量多维缩放的聚类组合算法（NMDSCCA)。该算法通过非度量多维缩放方法对非度量 型的高维数据进行降维，利用降维后得到的主成分变量作为输入变量，以K-Means算法作为基聚类器进行聚类，解决 了 K-Means算法无法处理分类数据以及维数高的变量局限性，使其具有普适性。仿真实验表明，新算法不仅聚类效果 上均优于传统K-Means算法及基于主成分分析（PCA)的聚类组合算法，而且算法应用于大数据时具有更高的收敛速

摘要:针对单一聚类方法远不能满足实际数据分析需求，且

度。

关键词：非度量多维缩放;K-Means算法;聚类分析;聚类组合；高维数据;主成分分析 中图分类号：TP181

文献标志码:A

Clustering combination algorithm based on non-metric multidimensional scaling

ZHOU Wenjuan , ZHAO Lifeng

(College of Science, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210023, China)

non-metric and high-dimensional variables exited in K-Means algorithm, a Clustering Combination Algorithm based on Non­metric MultiDimensional Scaling (NMDSCCA) was proposed. Firstly, the non-metric multi-dimensional scaling method was used to reduce the dimension. Then, using the principal component variables obtained after dimensionality reduction as input variables, and the K-Means algorithm as a base classifier for clustering, The limitations existed in K-Means algorithm about the classification of data and high-dimensional variable were solved and the algorithm was made universal. The simulation results show that the algorithm not only has advantages over both traditional K-Means algorithm and clustering algorithm based on Principal Component Analysis ( PCA) in cluster performance experiments, but also has high convergence speed when dealing with big data.Key words： non-metric multidimensional scaling; K-Means algorithm; clustering analysis; clustering combination; high­dimensional data; Principal Component Analysis (PCA)〇引言

随着数据挖掘的应用不断发展，聚类分析已经广泛地应 用到很多领域,主要有模式识别中的语音识别和字符识别、机 器学习中的图像分割和机器视觉、图像处理中的数据压缩和 信息检索等。它是一种典型的非监督学习算法，按照一定的 规则把研究的对象分成若干类，使各个类内的对象尽可能具 有最大的相似性，类间的对象尽可能有最大的相异性，不需要 事先知道数据对象的特征，所以也成为数据预处理的重要手 段;然而，信息化时代的数据呈现日益多元复杂趋势，传统的、 单一的聚类分析方法远远不能满足实际数据分析的需求。为 了寻找更加优化的方法,2002年

Abstract: Concerning the problem about real and complex data analysis not being met by single clustering method and

集，例如Strehl等[1]提出的3种基于超图的算法，包括基于簇 的相似度划分算法、超图划分算法、元聚类算法三大组合算 法，虽说前两个在时间复杂度上较高，但对于聚类效果远不如 最后一个；Zhang等[2]提出的混合二部图模型算法，以上4种 算法都存在聚类准确性等方面的不足，需要调用图划分软件

METIS,而包中参数的设定会影响聚类效果的好坏;随后王

敏峰等[3]提出了基于非负矩阵分解的聚类组合算法（Non- negative Matrix Factorization-based Clustering Combination Algorithm, NMFCCA),采用NMF方法实现对数据对象关键特

包

征的提取，得到最终聚类。

K-Means聚类是最为经典的基于划分的聚类方法，它不

需要计算任意两个样本点之间的距离，往往用于大规模的数 据，并且比其他聚类方法的收敛速度更快;然而，传统的

Strehl等[1]首次提出了聚类

组合的概念，聚类组合是一种通过融合多个聚类算法的优势 组合成的算法，以得到更高质量和鲁棒性的聚类结果。与单 一的聚类算法相比，聚类组合算法具有更好的稳定性、精确 性、鲁棒性、适用性、新颖性等诸多优点。目前虽然有很多的 聚类组合算法，但是并没有一个万能的方法能适用任何数据

收稿日期=2017-09-13;修回日期=2017-11-26。 硕士，主要研究方向：图论及其在通信中的应用。

K-Means聚类存在很多局限性:首先，容易受到初始聚类中心

的影响，不适用于非凸的数据集。孟子健等[4]提出了一种可 选初始聚类中心的改进算法，通过构建相异度矩阵，选取K个 于其他对象相异度较低且个数最多的数据对象作为初始聚类

基金项目：国家自然科学基金青年基金资助项目（61304169)。

作者简介:周文娟（1992 —），女，安徽安庆人，硕士研究生，主要研究方向:信息统计与数据挖掘；赵礼峰（1959—），男，安徽淮北人，教授，

68计算机应用

第38卷

中心。其次，聚类数的确定也是聚类分析中的一个非常重要 的问题，它对聚类的有效性和聚类结果的解释都有着直接的 影响。韩凌波[5]提出一种优化聚类数算法，通过构建评价函 数作为最佳聚类数的检验函数，建立相应的数学模型。另外， 维数过高会使得空间中的点变得稀疏，从而使距离失效。徐 勇等[6]为解决K-Means维数灾难问题，采用主成分分析对数 据源进行降维，设置对照实验组对降维前后聚类的时间、差异 性、迭代次数三方面进行比较等。另外聚类变量的选择也是 一个重要的问题，以上处理的都是度量型变量，对于非度量型 变量不能适用。1995年，余世孝[7]提出了非度量多维测度的 概念和算法，解决因无法获得研究对象间精确的相似性或相 异性数据，仅能得到它们之间等级关系数据的情形，在群落分 布方面已经有成功的应用。

针对上述维数高、非度量型多维变量问题，本文提出一种 新的聚类组合算法——

基于非度量多维缩放的聚类组合算法

(Non-metric Multi Dimensional Scaling-based Clustering Combination Algorithm, NMDSCCA) 01

非度量多维缩放算法

1.1相关概念

多维缩放法是一种利用客体间的相异（似）性数据去揭 示它们之间的空间关系的统计分析方法。度量多维缩放法所 需要的相异(似）性数据必须在区间量表或比率量表水平上 测量，而如果排序的目的不是在于最大限度保留对象之间的 实际距离，只是反映对象之间顺序关系，这时候非度量多维缩 放应运而生。

非度量多维缩放适用于无法获得研究对象间精确的相似 性或相异性数据，仅能得到它们之间等级关系数据的情形，其 基本特征是将对象间的相似性或相异性数据看成点间距离的 单调函数，在保持原始数据次序关系的基础上，用新的相同次 序的数据列替换原始数据进行度量型多维尺度分析。换句话 说，当资料不适合直接进行度量型多维尺度分析时，对其进行 变量变换，再采用度量型多维尺度分析，对原始资料而言，就 称之为非度量型多维尺度分析，其特点是根据样品中包含的 物种信息，以点的形式反映在多维空间上，而对不同样品间的 差异程度，则是通过点与点间的距离体现最终获得样品的空 间定位点图。1.2基本思想

非度量多维缩放是一种适用于非线性数据结构分析的复 杂迭代排序方法。它的基本思想是通过排序，使《个实体尽 可能在低维/>< n排序空间上点间的距离与实体之间的实际 相异性一致。1.3算法过程

假设有™个实体1，2,…，，实体i和y之间的相异（似）性 为〜将其列为相异对称矩阵，实体自身的相异（似）性略去，

则共有m - 1 )/2个元素;假设这m个值按序值从小到大排列：

矣…矣 = 7i(ra - 1)/2。现用

p(p

维欧氏空间n个点来表示这n个实体，而且点间的欧

氏距离大小：^ ^ (不,-)2 ,其顺序与n个实体相异

值顺序相一致。

算法步骤归纳如下：

1) 已知欧氏矩阵D =(、），并将非对角线元素由小到大排列起来：

矣‘2矣…矣 <丄，肌=几U - 1)/2乂 <

2) 设是

p

维拟合构造点，相应的距离阵= (^),

令S2(z) = min

玄（< -')2/玄'2,其中1称为^对

j> i

j>i

丨、丨的最小二乘单调回归。

3)

若

P

固定，且能存在一个无，使得S(无）=

mXin}>S(i

) =S;,,则称无为p维最佳拟合构造点。

4)

由于S;,(也称压力指数）是p的单调下降序列，取P使

^适当小，一般取；>=2。求解可用梯度法进行迭代。

当^為20%，那么这种吻合较差；如果为10%莓S;, < 20%，吻合一般;如果为5% < & < 10%,吻合较好;若&矣 5%，吻合极好。

2

基于非度量多维缩放的聚类组合算法

2.1

基本思想

NMMDSCCA算法首先利用非度量多维缩放算法对数据

源进行降维，再对降维后得到主成分变量的对象进行K-Means 聚类:确定聚类个数，选定初始聚类中心，通过多次反复迭代 运算最终得到稳定的聚类成员，使聚类成员之间具有一定的 差异性，类内成员尽可能相似。2.2理论依据

徐勇等提出基于主成分（Principal Component Analysis,

PCA)降维的K-Means聚类方法，PCA方法对数据源进行降

维，通过设置实验对照组证明该方法在计算时间、差异性、迭 代次数3个方面的优越性,但是数据对象是度量型变量。受 此启发本文针对维数高，针对非度量型的数据提出一种新的 聚类组合算法。

定义1

距离矩阵。一个矩阵〇 =(七），若满足

£>T =£>,<4 = o，ds 彡 o(€,y = 1,2,…，ray _y),则称d

为距

离矩阵。

定义2

多维标度解。对于距离阵D = (4.),多维标度法

的目的是要寻找P和Rp中的个点A

，*2，…，*„，用4表示X;

和'的欧氏距离j = (4)，使得d和■0在某种意义下相近。 在实际运用中，常取P = 1，2,3。将寻找到的71个点

，…，

、，写

成

矩

阵

形

式

，…,x„)T,则称X为D的一个

解（或叫多维标度解），但是多维标度法的解不唯一。

定义3 欧氏距离。若存在某个正整数及维空间R;> 中的A，x2，…，*„个点，使得：

df = (Xi - h - Xj) •，i，j = 1，2,…，n

则、2成为欧氏型距离。

如何判断一个距离是不是欧氏型的?如何求得欧氏型距 离阵所相应的《个点呢?这是先要解决的问题。

令：A =(〜）；〜=-《/2,忍=

=

/„ -

定理1 一个的距离阵

D

是欧氏型的充要条件是

B ^0〇

增刊1

周文娟等:基于非度量多维缩放的聚类组合算法

69

设X是一个u饤矩阵，令C =

= U

TAi，C

的特征根记作心> A2 >…為为简单起见，设心，^，…，

>0,可知，也为B 的非零特征根。

由于ffl：的行是X行的中心化，因此其中的元素可表示为：

6-. = (x, -x

-)T(x- -x

.)

记V⑴TV⑴==

1,2,...，；)），其中v⑴为5对应于Ai 的特征向量，此时令V⑴=(v⑴，v⑵，…,v(;〇)

'),则称(v^v:,…,')为X的；)维主坐标。由定理1可知,/> 在；> 维实数空间中拟合构造点的古典解是X的P维主坐标。

定义4古典解。求解步骤如下：

1) 根据距离矩阵0 =(〜）构造矩阵A = (%),%- d\\/l'2) 令B = (b&)，使得b厂〜-〜- a.』- a .;3) 求5的特征根A

i為A2為…為Ara,若无负特征根，明5^0,从而0是欧氏型的;若有负特征根，/> 一定不是欧氏

型的。令：

a^p = X

X

I

, \":1

\":1

(1)

■a2,i( = Xi = 1 a^2/iX = 1

a^2式(1)中两个量相当于主成分分析中的累积贡献率，一

般不要太大，而aliP和…，

表示B的对应于Ai，A2，…，A„的正交化特征向量，使

得冬;厂^,)=人;〇 = 1，2^._，；)），通常还要求人；1>0,若/^< 〇,要缩小P的值。

4) 令f = (^⑴，七2)，…，Sw)，则^■的行向量，…， 即为欲求的古典解。定理2 的P维主坐标是将X中心化后》个样本的前p

个主成分的值。

2.3

NMDSCCA算法过程

NMDSCCA聚类组合算法大致可以分为两个阶段:第一

阶段在原始数据集= 1^，；，…,X„1上进行非度量多维

缩放分析，得到降维后的两大主成分变量。第二阶段把两大主 成分变量值作为输人，对

n

个样本点进行K-Means聚类，得到

X

个聚类成员C。

输入；

)(p矣n)维欧氏空间ra个点& ,X2,…,AT„,ra个实

体的相异值、；

输出聚类成员C = |C⑴，C(2),…,cwl

。

2.3.1

NMDSCCA算法的第一阶段

非度量多维缩放是基于主成分分析的思想，这时^ =^ 是&的拟合，〜为误差项，但二者之间存在以下关

系：

dg = f(Aj + es) (2)式(2)/为未知的单增函数，能唯一利用的信息是丨〜丨 的秩，将其按照从小到大的顺序排列：

dhh ( dhh （tni，= A71 _ W/2y)所对应的、在上面的排列中的顺序（从小到大）

称为（(，y)或者〜的秩。目标是找到一个拟合构造点。使后者与前者相互之间的顺序一样，即U

矣…矣七„。

这种模型经常出现在相似系数矩阵的场合，因为相似系 数强调的是物品之间的相似，而非距离。

求这个模型的解有一些方法,其中以Shepard-Kmskal算 法最为流行，具体算法如下：

输

入

矣

ra)

维欧氏空间ra个点，…，个实

体的相异值、；

输出两维主坐标,度量初始排序点拟合好坏的压力系 数乂

1) 基于原始数据，给出《个实体两两之间的相异（似）值 、，总共有 m = ra(ra - 1)/2 个；2)

随机或人为地确定p维欧氏空间上的《个初始排序点

^

c2，…，x„，对数据加以标准化，并计算n个点间的欧氏距离

4；

3) 以欧氏距离&为纵轴，相异值、为横轴，画出™个有

序数对的二维图形；

4) 确定出m个新的排序点（<，、），它们满足:d,Ui•矣

.矣…莓的条件值的确定是根据相异值〜以及

点间距离^，通过一个较为复杂逐步回归过程而得出；

5)

找到最佳拟合构造点，得到两维主坐标以及胁强系数

S〇

2.3.2 NMMDSCC算法的第二阶段

输入两维主坐标；

输出聚类成员C=|c(1)，c⑵，…，Cwl

。

1) 利用R语言中NbClust包中的NbClust函数确定聚类

成员数

2) 将两大主成分变量作为输人数据，从中随机或者人为 选定K个初始聚类中心；

3)

进行K-Means聚类:分别计算剩下的各个点到X个聚

类中心的距离，根据距离的大小将它们分配给其最相似的中 心所在的类别；

4) 采用K-Means算法重新计算每个新类的聚类中心；5) 与上一次聚类中心比较是否发生变化，若有变化，重 复步骤2) ~4)，反之跳转步骤6);

6)

本点的分类不再改变或类中心不再改变，结束，输出X

个聚类结果。

3实验仿真

为了检验基于降维方法的算法优劣，以及不同数据特征

的数据集对降维聚类结果的影响，所以本文重点讨论新算法 在数据集上的聚类效果优势。

实例本数据来源于《中国统计年鉴》2006年全国20个 地区的平均薪资。选择其中9个主要的单位作为指标变量， 这些指标都是尽可能考虑到影响工资水平的各个方面，并适 合所采用的的分析方法，变量取值有3个等级，分别为:1、2、 3。级别为1的表示工资水平较高，级别为2的表示中等工资 水平,级别为1的表示工资水平较低。

第一步非度量多维缩放分析实验。利用画

DSCCA算法第一阶段，进行非度量多维缩放分

析得到主成分如表1。

=

表

70

计算机应用

第38卷

表1非度量多维缩放分析后的二维主坐标

地区第一维第二维第一维第二维主坐标

主坐标

地区主坐标

主坐标

北京69(W1.5719337.20山东-5992.53-10674.34河北-9192.63-3639.05湖北-11418.623738.88山西-10236.09-848.24湖南-8269.08-702.92内蒙古-9028.311965.42广西-8174.582366.00辽宁-3926.095677.86重庆-1276.161611.85吉林-9528.777722.74

四川-8560.491728.89上海49068.31-um.4〇贵州-12154.15435.85江苏4960.36-2518.33云南-7267.401985.98浙江17204.35-22957.95陕西

-8880.08-484.24江西

-16383.32

-189.41

(=T南

-9986.30

10348.20

由图1可以大致了解我国各地区的工资水平情况:北京、 上海、浙江跟其他地区的差异非常大;山东、江苏处在上升地

位，其他地区之间的差异相对要小一些。图2是在低维空间 中找到若干个点，线性拟合效果达到了 99.7%。

2-

1-m 丨

I-H

, 部 游!：戋n-：,w

..........1 1

酿

-1 -Lij^ ；

m

-2-

丨

---------------1-

雛

--------------1---------------1---------------r

0

2 4 6

第一主成分/1〇4

图1各地区平均薪资空间的二维点图

Observed Dissimilarity/104

图2各地区平均薪资线性拟合效果

第二步K-Means聚类实验。

1)聚类数的确定。

K-Means聚类需要事先确定要提取的聚类个数，本文选 择《R语言实战》中的Nbchist包，定义了几十个评估指标，聚 类数目从2遍历到8 (自己设定），然后通过这些指标看分别 在聚类数为多少时达到最优，最后选择指标支持数最多的聚 类数目就是最佳聚类数目。通过拟合效果的好坏选取合适的 聚类数，根据20个样本聚类数标准确定，2 ~ 8类为最佳范 围，对应的拟合效果如表2。

表2结果显示:当聚类数为5时，拟合效果为92.1%，拟 合效果良好，且聚类数大于5之后拟合效果并没有明显地提 高太多，聚类数小于5之前拟合效果呈现指数增长之势，因

此，判定5为当前最佳聚类数。

表2

不同聚类数下得到的拟合结果

聚类数

拟合效果/%

聚类数

拟合效果/%

244.9693.3382.5794.5488.38

94.9

5

92.1

2)聚类成员的确定。

表3

聚为5类时的各项判定指标

类号

大小

聚类向量

类内平方和

132,8,110.733 7235,6,200.1884327,9

1.49774113,4,10,12,13,14,15,16,17,18,190.57455

1

1

0.0000

从表3的聚类结果来看，20个样本聚成5类是类的个数 分别为3、3、2、11、1，同时可以看到5个类的中心坐标以及每 个样本所属的类别，这些样本的聚类可解释程度为92.1%，整 体聚类效果是比较理想的。因此基于非度量多维缩放的聚类 组合算法是有效的。

实例数据是建立在数据预处理的基础上的理想化数据， 然而现实生活中的数据更多的是比较粗糙的，需要加工预处 理，所以为了验证本算法的有效性，引进以下数据集。

3.1数据描述

本文主要研究的是非度量型变量的降维问题，自然会想 到选择U

CI中属性变量为有序类别的Car Evaluation数据集。

该数据集有1 728个案例，6个属性变量；另外

Varespec、

varechem™

是

R

语言中进行非度量多维缩放分析程序包

vegan自带的数据集，是非度量多维缩放的经典使用数据。 Varespec数据集有24行和44列，列被估计为24个物种占地

属性的变量值。属性名称由在varespec数据集上做出巨大贡 献科学家的名字组成，任何熟悉植被类型的人都耳熟能详。

varechem数据集有24行和14列，是描述土壤特性的变量，和 Varespec类似，这

些变量的化学测量有明显的名称，由

Baresoil给出了裸表估计值和腐殖质层的厚度。

3.2实验过程及结果

3.2.1非度量多维缩放过程

首先对两类数据集进行清洗、去噪声、标准化处理，然后 将两类数据集合进行排序索引，选择合适的样本间相异性的 度量方法，从而得到一个标准数据集，再计算样本之间的相异 性，得到一个下三角相异矩阵，最后进行非度量多维缩放分 析，分析结果如下：

考虑到本文主要目的是讨论基于非度量多维变量的降维 效果，本实验分两方面证明本算法的优越性:一方面，将降维 后的拟合效果与基于PCA的

K-Means聚类分析比较，采用

Varespec数据集进行分析;另一方面，比较执行效率,即时间

开销，基于Car Evaluation数据集开展讨论。

先利用排序索引函数mnkindex进行距离方式的选择，利 用上述样本数据显示结果如表4。

增刊1

周文娟等:基于非度量多维缩放的聚类组合算法

71

表4

不同距离方法的度量效果

测距方法

度量值

测距方法

度量值

euc0.2396bra0.283 8man0.273 5kul

0.2840

gow

0.228 8

结果显示kul最优，bm指数也还不错，择优选择kul作为 计算样本相异性的度量方法。

再利用isoMDS函数进行非度量多维缩放分析，分析结果 如下:降维后维数为2,压力值为0.1843196，迭代次数为20。

从以上结果可以看出：总的迭代次数为20次，从迭代效 率上看，比较优;模型的应力值为〇. 184 319 6，根据拟合好坏 程度的评判标准，降维后模型的吻合程度一般;从模型的拟合 度可以看出（如图3)，非度量多维缩放拟合程度高达99% , 线性拟合也有94.1%，因此可认为非度量多维缩放算法降维 :欢果良好。

Non-metric fit,i?2=0.99

Linear fit,fi2=0.941

0.0-0.2

0.4 0.6 0.8

1.0

Observed Dissimilarity

图3微生物植被拟合效果

由于本文算法在维数中选择了二维，图4是空间上的二 维点图，可以看出24个样本空间的大致位置,所以用二维平 面比较直观反映各个地质的位置：第一维度是气候因素,

Hylosple、Rhodtome、Betupube为主要特征变量;第二维度为地

形因素，Nepharct、Icmaeric、Cladphy 1为主要特征变量。

0.5-

念

毎州u塒

-

1.0

-0.5

0.0

0.5

1.0

第一主成分

图4

各属性的空间二维图

3.2.2

K-Means聚类过程

K-Means聚类事先利用NbClust包的NbClust函数决定聚

类的个数，由于随机选择K个初始聚类中心点，在每次调用函 数时可能获得不同的方案，因此使用随机种子函数set. seed保 证结果可复制，算法实现过程及结果如表5所示。

当聚成5类时，组内平方和不再有明显的下降趋势，并

且分类比较均匀，所以确定聚类个数为5类。

表5

不同聚类数下得到的拟合结果

聚类数

拟合效果/%

聚类数

拟合效果/%

235.9690.1366.8790.64

74.78

90.9

5

89.4

don

-0.25

-0.4 -0.2 0.0 0.2 0.4

第一主成分

图5

两主成分形成的散点图

从图5可以看出，样本总体分布比较均匀，没有扎堆现 象，即24个土地样本之间在地形特征和气候特征上没有绝对 优势，种植被各有千秋，只需根据土质特征种植合适的植物即 可。

为了验证新算法的优良性与可行性，以下分别采用传统

的K-Means聚类算法、基于PCA降维后的改进算法以及本文 所提出的新的聚类组合算法进行K-Means聚类分析，得到的 三种聚类结果如表6。

表6

各分类算法聚类效果对比

~并広

各类成员数

Irt~类间平方12345平方和和占比/%

K-Means53655174.5968.4PCA-K-Means1212725.1288.9NMDSCCA

5

2

6

9

2

4.48

90.2

以上结果表明：

1) 当选择传统K-Means聚类时，24个样本聚成5类是类

的个数分别为5，3，6，5，6，类内距离平方和分别为34. 069 5， 33.2630，44.0555，18.5996，44.6034，类间距离平方和占比为 68.4%。

2)

选择PCA-K-Means算法,聚类结果显示:24个样本聚

成5类，各类的个数分别为1，2，12,7,2，有明显的扎堆现象，

第一类、第二类、第五类聚类成员数很小，集中在第三类、第四 类，类内距离平方和分别为〇,〇. 072 5,3. 212 5,1. 812 5, 0• 0184，类间距离平方和占比为88.9%。

3)

选择本文NMDSCCA算法，从以上的聚类结果来看,24

个样本聚成5类，各类的个数分别为5, 2, 6, 9, 2,同时可以 看到5个类的坐标以及每个样本所属的类别，这些样本的聚 类可解释程度为90.2 %，整体聚类效果是比较理想的。从三 种聚类算法比较可知:从拟合效果来看，后两种算法拟合效果 要远远优于传统;但基于PCA的

K-Means算法有明显的扎堆

72计算机应用第38卷

现象，根据空间二维图分布可知，扎堆现象与本数据聚类效果 不符，所以综合判断本文所提出的NMDSCCA算法有明显的 优势。

敛速度;且新算法是K-Means算法的扩展，使其具有普适性。 但是基于非度量多维缩放的聚类组合算法在初始化种群时,本文为随机或者人为给定，不同的初始聚类中心可能会存在微小的差距，因此对于初始聚类中心以及迭代算法的优化问 题尚需要进一步完善和探讨。参考文献：

[1]

STREHL A, GHOSH J. Cluster ensembles : a knowledge reuse framework for combining multiple partitions [ J] • Journal of Machine Learning Research, 2002, 3(3): 583 -617.

[2]

ZHANG X L, BRODLEY C E. Solving cluster ensemble problems by bipartite graph partitioning [ C]// Proceedings of the 21st Inter- national Conference on Machine Learning. New York: ACM, 2004: 9-15.

[3] 王敏峰，朱敏琛.一种新的聚类组合算法[J].福州大学学报（自

3.2.3

集群性能实验

本实验是基于Hadoop平台在4台计算机组成的集群上 运行，其中1台作为主要节点，另外3台是从节点。为了能对 比几种算法的运行速度，本文对传统的K-Means算法、基于

PCA的K-Means算法、NMDSCCA算法的运行速度进行比较。

为了体现本文算法在处理海量高维非度量型数据的高性 能，在数据集Car Evaluation的基础上构造更大规模数据集， 数据规模达到1.18 GB,其结果如图6所示。当节点数为1, 传统算法远劣于改进算法，两改进算法差别不大;但随着节点 数的增加，本文算法运行收敛速度优势逐渐突出，因此，本文 算法应用于大数据时具有更高的收敛速度。

然科学版)，2010,38(6): 819 - 823.

[4] 孟子健，马江洪.一种可选初始聚类中心的改进K均值算法[J].

统计决策,2014(12): 12-14.

s

=T

0/w1-l忘

[5] 韩凌波.K-均值算法个数优化问题研究[J].四川理工学院学报

(自然科学版），2012,25 (2): 77 - 84.[6] 徐勇，陈亮.一种基于降维思想的K均值聚类算法[J].湖南城市

学院学报（自然科学版)，2017,26( 1): 54 - 61.

[7] 余世孝.非度量多维测度及其在群落分类中的应用[J].植物生

态学报，1995,19(2) = 128 -136.

1

2

3

4

[8]

RIVAS M N, BURTON 0 T, WISE P, et al. A microbiota signature associated with experimental food allergy promotes allergic sensitiza­tion and anaphylaxis [ J]. Journal of Allergy and Clinical Immunolo-

图

6

节点数

算法运行速度对比

4结语

K-Means算法作为经典的聚类算法，对数据集是紧凑的

gym, 2013, 131(1): 201 -212.

[9]王 斌会.多元统计分析及R语言建樹M].广州：暨南大学出版

并且簇与簇之间明显分离的情况聚类效果较好，但是它无法 处理分类数据以及维数高的变量。本文首先运用非度量多维 缩放的基本思想对有序分类的多维变量进行降维，克服

社，2011:267 - 279.

[1〇]

张学工.模式识别[M].北京：清华大学出版社,2015: 173 -

177.

K-Means算法的存在的局限性，然后提出一种新的基于非度量

多维缩放的聚类组合算法。实验结果表明，改进的算法能进 行有效的分类，并且较其他两种算法在大数据上有较高的收

[11] [12]

周爱武陈宝楼，王玻

,.K-Means算法的研究与改班J].计算机

[D].延边:

技术与发展,2012,22( 10): 101 -104.

宋媛聚类分析中确定最佳聚类数的若干问题研究

.

延边大学,2013:11 -27.

(上接第47页）[6] 沈浩,陈德宏，徐舒.一种战场声目标识别的多特征提取算法

[J].安徽工业大学学报（自然科学版)，2017,34( 2): 164 - m.[7] 李虹，徐小力,吴国新，等.基于MFCC的语音情感特征提取研究

[J].电子测量与仪器学报，2〇1入叫3):448 _453.

[8] 吕艳新.被动声目标识别理论研究[D].南京:南京理工大学，

2011:25 -28.

[9] 赵拓.基于频谱动态特征和ELM的挖掘设备识别方法研究

[14] 孙国强，樊新海石文雷.基于MFCC和支持向量机的装甲车辆

,

识别研究[J]国外电子测量技术，2017,36( 10): 31 -35.

[15] 钟浩，鲍鸿，张晶.一种改进的语音动态组合特征参数提取方法

[J] 电脑与信息技术，201入25(3): 4 _7.

[16]

CHAPELLE 0, VAPNIK V, B0USQUET 0, et al. Choosing multiple parameters for support vector machines [ J]. Machine Learning, 2002, 46(1/2/3): 131 -159.

[17]

YANG X S, DEB S. Cuckoo search via L6vy flights [C]// Proceedings of the 2009 World Conference on Nature & Biologically

.

■

[10]

[D] ■杭州:杭州电子科技大学，2016: 38 - 39.

VAPNIK V. The nature of statistical learning theory [C]// Proceedings of the

1995 Conference on Artificial Intelligence. New Inspired Computing. Hscataway, NJ: IEEE, 2009: 210-214.

[18] YANG X S, DEB S. Engineering optimisation by cuckoo seeirch York: Springer-Verlag, 1995: 480 -486.

[J ]. International Journal of Mathematical Modelling and [11] 张松兰.支持向量机的算法及应用综述[J].江苏理工学院学

报，2016,22(2):14-17.Numerical Optimisation, 2010, 1(4): 330 -343.

[12] 祝龙石，庄志洪，张清泰，等.战场声目标噪声特性分析[J].现 [19] 马伟.布谷鸟搜索算法优化特征和分类器参数的人体行为识别

代引信，1996(2): 57 -61.[J].微电子学与计算机，2〇16,33(5): 1〇2 - 105.

[13] 吕霄云,王宏霞.基于MFCC和短时能量混合的异常声音识别 [20] 刘思思，谭建平，易子馗.基于MFCC和SVM的车窗电机异常

噪声辨识方法研究[J].振动与冲击,2017, 36(5): 102 -107.算法研究[J].计算机应用,2010,30( 3): 796 - 798.