当前位置：文档库 › 高维数据的低维表示综述

高维数据的低维表示综述

一、研究背景

在科学研究中，我们经常要对数据进行处理。而这些数据通常都位于维数较高的空间，例如，当我们处理200个256*256的图片序列时，通常我们将图片拉成一个向量，这样，我们得到了65536*200的数据，如果直接对这些数据进行处理，会有以下问题：首先，会出现所谓的“位数灾难”问题，巨大的计算量将使我们无法忍受；其次，这些数据通常没有反映出数据的本质特征，如果直接对他们进行处理，不会得到理想的结果。所以，通常我们需要首先对数据进行降维，然后对降维后的数据进行处理。

降维的基本原理是把数据样本从高维输入空间通过线性或非线性映射投影到一个低维空间，从而找出隐藏在高维观测数据中有意义的低维结构。（8）

之所以能对高维数据进行降维，是因为数据的原始表示常常包含大量冗余： · 有些变量的变化比测量引入的噪声还要小，因此可以看作是无关的 · 有些变量和其他的变量有很强的相关性(例如是其他变量的线性组合或是其他函数依赖关系)，可以找到一组新的不相关的变量。（3）

从几何的观点来看，降维可以看成是挖掘嵌入在高维数据中的低维线性或非线性流形。这种嵌入保留了原始数据的几何特性，即在高维空间中靠近的点在嵌入空间中也相互靠近。（12）

数据降维是以牺牲一部分信息为代价的，把高维数据通过投影映射到低维空间中，势必会造成一些原始信息的损失。所以在对高维数据实施降维的过程中如何在最优的保持原始数据的本质的前提下，实现高维数据的低维表示，是研究的重点。（8）

二、降维问题

1．定义

定义1.1降维问题的模型为(,)X F ，其中D 维数据空间集合{}1N

l l X x ==

（一

般为D R 的一个子集），映射F

:F X Y →(),x y F x →=

是d 空间集合（一般是d R ，d

<<）的一个子集，我们称F 是数据集X

（到Y ）的降维。

若F 为X 的线性函数，则称F 为线性降维；否则，称为非线性降维。定义1.2 称映射1F -

Y X -→1

()

y xF

y -→

为嵌入映射。（8） 2．分类

针对降维问题的目的和待处理数据集合表象维数的多少，对其进行初步的、粗略的分类如下：

·硬降维问题：数据维数从几千到几万甚至几十万的变化，此时需要对数据集进行“严厉”的降维，以至于达到便于处理的大小，如图像识别、分类问题以及语音识别问题等。

·软降维问题：此时数据集合的维数不是太高，降维的需求不是非常的迫切。如社会科学、心理学以及多元统计分析领域皆属于此类。

·可视化问题：此时数据集合的绝对维数不是很高，但为了便于利用人们的直观洞察力，即为了可视化，我们将其降到2或3维。虽然我们可以可视化更高维数的数据，但是它们通常难于理解，不能产生数据空间的合理形态。

若我们还考虑时间变量的话可以对降维问题进行更加进一步的分类，静态降维问题和动态降维问题。后者对于时间序列来讲是有用的，如视频序列、连续语音信号等的处理。（4） 3．方法介绍

如何将高维数据表示在低维空间中，并由此发现其内在结构是高维信息处理研究的关键问题之一。

实际处理中，由于线性方法具有简单性、易解释性、可延展性等优点，使得线性降维在高维数据处理中是一个主要研究方向。已有的线性维数约简方法，主要包括主成分分析(Principal Component Analysis ，PCA)[16]、独立成分分析(Independent Component Analysis ，ICA)、线性判别分析inear discriminant analysis(LDA) [17]、Fisher 判别分析(Fisher Discriminant Analysis ，FDA)、主曲

线(Principal Curves)、投影寻踪(Projection Pursuit, PP)、多维尺度方法(Multidimensional Scaling，MDS)等。这些方法实际是在不同优化准则之下，寻求最佳线性模型，这也是线性维数约简方法的共性。（10）

通过消除数据建模过程中的全局线性假设，Sammon提出了一种非线性映射，即Sammon映射(SM)，该算法能够保持输入样本之间的相关距离；Hastie 提出了principal curves(PC)，其定义为通过概率分布或数据中间的光滑曲线；Kohonen基于自组织神经网络提出了self-organizing map(SOM)用来保存数据空间的拓扑属性；Scholkopf等应用Mercer核将PCA扩展为Kernel PCA(KPCA)，该算法在高维空间中计算主分量，而该高维空间由输入空间经某种非线性映射得到。Mika等采用相同的思想来非线性扩展LDA，从而提出了kernel LDA （KLDA）；然而，基于核的方法其难点在于如何选择一个合适的核函数，一个好的核函数可以使数据在特征空间上线性可分或者近似线性可分，但并不是所选核函数对于每一种数据都适用。核函数的选择反映了人们对问题的先验知识，在实际的应用中往往是经验地选择某种核函数，比如径向基函数(Radial Basis Function，RBF)。同时，在使用核函数时不必知道具体的特征空间，使得核函数方法缺乏物理直观性，这也是核函数方法的一个缺点。（10）

最近兴起的流形学习算法也是用来维数约减的非线性方法，并且依靠它们在探测嵌入在高维空间中低维流形的能力和灵活性而被广泛应用。

具有代表性的流形学习算法包括等距映射(Isometric Mapping，Isomap)、局部线性嵌入方法(Locally Linear Embedding，LLE)、Laplacian 特征映射(Laplacian Eigenmap，LE)、局部切空间排列方法( Local Tangent Space Alignment，LTSA)、Hessian等距映射(Hessian eigenmaps，HLLE)和最大方差展开(maximum variance unfolding，MVU)。其中，LLE运用线性系数，来表达局部几何，该系数能够重建一个给定的样本点利用其近邻点，然后寻找一个低维空间，在该空间中这些线性系数仍然可以用来重建相应的点；ISOMAP作为MDS的变种，能够保存点对之间的全局的测地线距离；LE通过对一个描述了点对之间邻域关系的无向图的操作，来保持数据之间的近邻关系。HLLE先通过估计邻域上的Hessian而构建一矩阵，然后在此矩阵上运用特征值分解而得到最终的低维坐标。LTSA运用局部切信息作为局部几何的表达，然后将这些切信息在全局中排列从而得到最终的

全局坐标。MVU不是一个绝对的局部方法而是一个介于局部和全局之间的方法，因为MVU不仅保存近邻点之间的几何关系而且在它的目标函数中考虑了全局点对之间的距离。除了基于谱分析的流形学习的算法，基于概率参数模型，Rowels 提出了global coordination(GC)；Teh和Roweis开发了locally linear coordination(LLC)；Brand提出了manifold charting(Charting)。这些方法也属于流形学习的重要范畴。

然而，这些非线性的算法却不能够为样本提供一个外在的映射，也就是说，它们很难被应用于识别问题。但是，一些基于谱分析的算法由于其具有特殊的特征分解机制而能够较为容易的扩展为线性算法，其线性化可以通过在解决优化的过程中施加线性逼近来实现。Locality preserving projection(LPP)作为LE的线性化是其中最早提出的算法。后来提出的还包括neighborhood preserving embedding(NPE)，LLE的线性化扩展，和orthogonal neighborhood preserving projections(ONPP)，LLE的正交线性化扩展。这种线性化扩展使流形学习的思想更能够应用到现实世界中。图1.1给出了以上所提提及的降维算法的分类图。

在谱方法的线性化扩展中，LPP可以被看作为基于图结构的最具代表性的算法，在接下来的几年中，又不断地有这种基于图的算法被提出，从而进一步完善了这种基于图的框架。Cai等对LPP算法分别对监督设置和非监督设置两种情况作了系统的分析，并且将LDA用这种基于图的框架重新公式化。Yan等提出了一种一般性的框架即“图嵌入”，来统一各种各样的降维算法。基于此种框架，一种新的线性算法，marginal fisher analysis（MFA）将开发出来。MFA不同于LPP 其只用一个图来描述数据的几何结构，该算法采用了两个图，其中一个为固有图（intrinsic graph），它用来刻画数据的类内紧凑性；而另一个图为惩罚图（penalty graph），用来描述数据类间的分离性。因此，MFA比LPP更具有判别性。Chen 等同时提出的local discriminant embedding（LDE）算法在本质上与MFA的思想是相同的。（5）

非线性降维方法与线性降维方法相比的一个显著特点是，分析中的局部性(数据集合经常满足的一个简单假设)。原因在于对数据集合的内蕴结构而言，有下列特性：

·由泰勒定理，任何可微函数在一点的充分小的邻域之内满足线性性。形象

的来讲，相当于认为曲面流形可由大小不一的局部线性块拼接而成；

·数据流形经常是由许多可分割的子流形所组成；

·数据流形的本征维数沿着流形不断的发生变化，只有局部性才能抓住其根本特性。（4）

三、常见降维方法

（一）线性

1.主成分分析(Principal Component Aanlysis PCA) [1]

PCA将方差的大小作为衡量信息量多少的标准，认为方差越大提供的信息越多，反之提供的信息就越少。它是在损失很少的信息的前提下把多个指标转化为几个综合指标的一种多元统计方法。它具有概念简单，计算方便以及最优线性重构误差等优良的特性。

PCA是一种全局算法，它可以较好地揭示具有线性结构的高维数据集的全

局分布。然而对于嵌入在高维空间中具有非线性流形结构的数据，PCA 很难学习出隐含在数据集中的低维流形结构。

PCA 假设数据之间的关系是线性的。它在保存原始高维数据协方差结构的基础上计算低维表达，也就是最大化总体方差。它的目标函数可以写为：

1=arg m ax

arg m ax

()arg m ax ()..P C A P C A

P C A

P C A i U i N

T P C A i P C A T P C A P C A

P C A

U U i U y y

U x x tr U S U s t U

I ==-=-==∑

∑

其中，

y N

=∑

，

x N

∑

，且

S 为总体离散矩阵：

i=1

=()()

T i i S x x x x --∑。对转换矩阵做尺度约束d =T

P C A

P C A U U I ，其中d I 为d d

?单

位矩阵。则目标函数可以写为：

arg m ax ()

P C A

P C A T P C A U tr U S U ，..T

P C A

P C A d

s t U U I =

上式问题可以转化为T S 的标准的特征值问题：PCA 的最优转换矩阵为T S 的d 个最大的特征值所对应的d 个m 维特征向量。

2.线性判别法(Linear Discriminant Analysis LDA) [2]

其基本思想是投影，首先找出特征向量，把这些数据投影到一个低维的方向，使得投影后不同的组之间尽可能的分开，而同一组内的的样本比较靠拢，然后在新空间中对样本进行分类。

通过最小化类内离散矩阵W S 的秩而最大化类间离散矩阵B S 的秩，来寻找一个子空间来区分不同的类别。W S 和B S 分别定义如下：

()()

()

i=1

=()()

N C

i i i i T

W j

j S x

x m

=--∑

∑

()

()()C

i i T

B i i S N m

m m

m ==

--∑

其中，i N 是第i 个类中样本的个数；()i j x 是第i 个样本中第j 个样本。()i m 为第i 个类的质心；m 用来表示所有样本的质心，C 为样本的类别数。LDA 则有以下的优化准则：

arg m ax

()()

T L D A B L D A T L D A

W L D A

tr U S U tr U

S U

..T

L D A L D A d

s t U U I =

上述的优化可以转化为求解一个广义的特征分解问题：

B W S S αλα

且最优的解为d 个特征向量其对应于d 个最大的非零特征值。

3.投影寻踪(Projection Pursuit PP) [3]

基本思想主要来源人们对低维空间几何图形的直观理解，它包含俩个方面的含义：其一是投影(Projection)，把高维空间中数据投影到低维空间；其二是寻踪(Pursuit)，利用低维空间投影数据的几何分布形念，发现人们感兴趣的数据内在特征和相应的投影方向，同时排除与数据结构和特征无关的或关系比较小的变量干扰。

4. 多维尺度分析(Multidimensional Scalar ，MDS) [4]

主要思想是：根据数据点间的欧氏距离，构造关系矩阵，为了尽可能地保持每对观测数据点之间的欧氏距离，只需对此关系矩阵进行特征分解，从而获得每个数据在低维空间中的低维坐标。

算法步骤：

1计算观测空间中任意两点欧式距离，构造n 阶平方欧式距离矩阵A 2将矩阵A 进行双中心化计算，即计算12

B H A H

。

若设n n ?阶矩阵=e /T

H I

e n

-（常称之为中心化矩阵），将矩阵H 左乘和右

乘A 的两边（常称之为双中心化）。

3计算低维坐标Y 。即将B 奇异值分解，设B 的最大的d 个特征值

1d =diag ()

λλΛ ，，对应特征向量1[,]d U

v v = ，则

维坐标为T

=。

（二）非线性

流形学习旨在发现高维数据集分布的内在规律性，其基本思想是：高维观测空间中的点由少数独立变量的共同作用在观测空间张成一个流形，如果能有效地展开观测空间卷曲的流形或发现内在的主要变量，就可以对该数据集进行降维。

现在形式化地概括流形学习这一维数约简过程：假设数据是均匀采样于一个高维欧氏空间中的低维流形，流形学习就是从高维采样数据中恢复低维流形结

构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现维数约简或者数据可视化。它是从观测到的现象中去寻找事物的本质，找到产生数据的内在规律。

用数学语言可以这样描述，令d

?且

f Y R

→是一个光滑的嵌套，

D d

>，流形学习的目标是基于D R 上的一个给定被观测数据集合{}i x 去恢复Y 和

，在Y 中隐藏的数据{}i y 被随机地产生，然后被

映射到观测空间，使得

{}()i

i x f y =。（12）

1.局部线性嵌入方法 LLE (Locally Linear Embedding) [5]

LLE 在保存原始高维数据邻域线性结构的基础上计算低维表达。（5）是一种局部方法，它试图保持数据的局部几何特征，就本质上来说，它是将流形上的近邻点映射到低维空间的近邻。（9）

图2 非线性降维实例 B 是从 A 中提取的样本点（三维），通过非线性降维算法 LLE 将数据映射到二维空间中（C ），从C 图中的颜色可以看出通过 LLE 算法处理后的数据能很好的保持原有数据的邻域特性(引用文献[6])

主要思想：对一组具有嵌套(流形)的数据集，在嵌套空问与内在低维空间局

部邻域问的关系应该不变，即在嵌套空间中每个采样点可以用它的近邻点线性表示，在低维空间中保持每个邻域中的权值不变，重构原数据点，使重构误差最小。(8)

LLE 的实现过程

步骤：LLE 方法可以归结为三步： (1) 寻找每个样本点的k 个近邻点；

把相对于所求样本点距离最近的k 个样本点规定为所求样本点的k 个邻近点。k 是一个预先给定值。距离的计算既可采用欧式距离也可采用Dijkstra 距离。Dijkstra 距离是一种测地距离，它能够保持样本点之间的曲面特性。

(2)由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；这里定义一个成本函数，如下式，来测量重建误差：

()i ij j

w x w x ε=-

∑

解得1

i i

ij jk

w G G --=

∑

，1,j ij x N

w ∈=∑

j x N

?时0

w =

其中()()

i jk

i j i k G x x ηη=--，j η和k η是i x 的近邻点；

为了使重建误差最小化，权重ij w 服从一种重要的对称性，即对所有特定数据点

来说，它们和它们邻居点之间经过旋转、重排、转换等变换后，它们之间的对称性是不变的。由此可见重建权重能够描述每个邻居本质的几何特性。因此可以认为原始数据空间内的局部几何特征同在流形局部块上的几何特征是完全等效的。

（3）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。映射条件满足如下成本函数：

()i ij j

Y Y w Y γ=

∑

要使低维重构误差最小，计算得出，Y 等价于求M 的特征向量，其中

()()

M I W I W =--在处理过程中，将M 的特征值从小到大排列，第一个特征

值几乎接近于零，那么舍去第一个特征值。通常取第2到m+l 之间的特征值所对应的特征向量作为输出结果。

优点：LLE 算法可以学习任意维的局部线性的低维流形，就是用局部性——用局部的的线性来逼近全局的非线性，保持局部的几何结构不变，通过相互重叠的局部邻域来提供整体的信息，从而保持整体的几何性质。LLE 既有非线性的特点又具有线性方法的优点。（8）同时由重构成本函数最小化得到的最优权值遵循对称特性，每个点的近邻权值在平移、旋转、伸缩变换下是保持不变的LLE 算法有解析的全局最优解，不需迭代，低维嵌入的计算归结为稀疏矩阵特征值的计算，这样计算复杂度相对较小。

缺点：LLE 算法要求所学习的流形只能是不闭合的且在局部是线性的，还要求样本在流形上是稠密采样的。另外，该算法的参数选择不确定，对样本中的噪音很敏感。（12）此外，(1)对于一个新样本点。没有显式的方法把该点嵌入到低维空间中，这在检索应用中不适用。(2)新空间的维数没有显式准则进行确定，只有通过经验的方法。(3)LLE 没有利用数据点的类信息。在分类问题中，对于有类标号的样本数据，LLE 无能为力。

SLLE 算法[7]

Dick 和Robert 提出一种针对有监督的 LLE 算法，即Supervised linear locally embedding (SLLE)传统的LLE 算法在第一步时是根据样本点间的欧氏距离来寻找k 个近邻点，而SLLE 在处理这一步时增加了样本点的类别信息，SLLE 算法的其余步骤同LLE 算法是一致的。

SLLE 算法在计算点与点之间的距离时有两种方法。

SLLE1：第一种方法是采用下式来修正点与点之间的距离公式如下所示

m ax()D D D α'=+?

其中：D '是计算后的距离D 是最初采用的距离；max(D)是表示类与类之间的最大距离；?取0或者1，当两点属于同类时，?取为0，否则取1；α是控制点集之间的距离参数，[0,1]α

∈，是一个经验参数。当α

取为零时，此时的SLLE

和 LLE 算法相同。这个方法引入了一个参数α，它是一种经验参数，对实验的结果有很大的影响，下面介绍一种非参数的方法。

SLLE2：求解点与点之间的距离，目的在于是寻找样本点的近邻点。SLLE2的方法在寻找近邻点时，不是在全局样本中寻找近邻点，而是在每个点所在类的样本中寻找近邻点，也就是说，在类内中寻找样本点的近邻点。这个方法固然没有采用参数的方法，但是如果某一类的样本个数小于k ，那么这种方法必将失败，则每个类的样本个数在相当多的情况下可以采用这种方法。

RLLE 算法[8]

当在做聚类分析且采用LLE 算法对数据进行降维时，如果数据中存在着许多离异点的情况，那么降维后的结果将会发生变异，通常是第一维或者是第二维的数据发生跳跃式的变化，或者分布在某几条直线上，这将会给聚类带来很大的麻烦，其实当离异点超过LLE 算法中的k 值时，这种现象将会发生。

A.Hadid 和M.Pietik?inen 提出一种 Robust Locally Linear Embedding (RLLE)方法。它是针对存在有离异点的情况下，对样本的一种无监督的非线性降维方法。

邻域保持嵌入算法NPE 算法[9]

NPE 从本质上说是局部线性嵌入(local linear embedding ，LLE)的线性逼近。给定数据集X ，采用与LLE 相同的方法构建数据集上的近邻图。NPE 针对LLE 算法的out-of-sample 问题提出的，该算法通过最小化局部相似离散度寻找投影方向，有效的保持了数据间的相似几何结构，取得了不错效果，已被广泛地应用到文档分析、机器学习和模拟识别等领域。NPE 假定每个局部近邻都是线性的。

算法步骤：

1近邻选择，构造邻接图G 2计算近邻重建权W

3计算投影向量：

a 求低维坐标对应近邻重建的目标函数最小化，即

11..:n k i ij ij Y i j T

M in y W y S t YY I

==?

?-??=?∑∑

b 代入线性变换T

y x α=,得

11x ..:n k T T

i ij ij i j T T

M in W x S t X X I

αααα==?

?-??=?∑∑

..:T T

T T

M in X M X S t X X I

ααααα???

=??

其中()()

I W I W =--

d 求解下列广义特征方程的d 个最小特征值对应的特征向量作为d 个投影向量：

X M X X X αλα

故由上述特征方程的d 个最小特征值12d ,,,λλλ 对应特征向量

12d ,,,ααα ，构成保持近邻重建特性的线性变换矩阵。

缺点：NPE 在保持数据空间的局部相似信息时，不能较有效地保持差异信息，特别是高维非线性数据间的差异信息。如在人脸识别应用中，人脸图像的识别容易受光照、表情等非理想条件变化的影响，这些非理想情况会使得同一个人的不同图像之间的差异大于不同人图像之间的差异，从而导致识别错误。

NPE 算法通过式T

i i

x y A x →=实现了数据到新空间的线性变换。显然，这

种线性变换实现的数据变换是一种显式形式，这样就解决了LLE 算法没有显式映射函数的问题。

LLE 算法是非监督的学习方法，没有充分利用类别信息，为了提高算法的识别能力，于是有了LLE 的正交线性化扩展，orthogonal neighborhood preserving projections(ONPP)[10][ 11]。

张长水等人[12]在LLE 的基础上提出一种从低维嵌入空间向高维空间映射

的方法，并在多姿态人脸图像的重构实验中得到有效的验证，进一步完善了非线性降维方法。

2. 等距映射法 ISOMAP (Isometric Map) [13]

ISOMAP 认为当数据集具有嵌入流形结构时，可以根据保距映射来获得观测空间数据集在低维结构的对应描述。

基本思想：ISOMAP 通过测地线距离来描述各点之间的相互关系，在全局意义下，通过寻找各点在图意义下的最短路径来获得点与点之间的距离，然后利用经典的MDS 算法得到低维的嵌入坐标。因此．ISOMAP 可认为是MDS 算法的变种。（5）

图3 ISOMAP 算法示意图

使用前提条件：高维数据所在的低维流形与欧氏空间的一个子集是整体等距的；与数据所在的流形等距的欧氏空问的子集是一个凸集。

主要步骤：

(1)构造局部邻域。首先对数据集{}

12,,,n X

x x x = ，计算任意两个样本向量

x 和j x 的欧式距离(,)x i j d x x ，将每一个点与所有的点进行比较，当两点之间的距

离小于固定的半径ε（或i 是j 的K-邻域）时，我们就认为它们是相邻的，将其连接起来，该边的长度(,)x i j d x x ,则得到邻域图G 。

(2)计算最短距离。在图G 中，设任意两个样本向量i x 和j x 之间的最短距离为(,)G i j d x x 。若i x 和j x 之间存在连线，(,)G i j d x x 的初始值为(,)x i j d x x ，否则令

(,)G i j d x x =∞

。对所有的k=1,2,…,n

(,)m in{(,),(,)(,)}G i j G i j G i k G k j d x x d x x d x x d x x =+

这样得到矩阵{(,)}G G i j D d x x =，它是图

G 中所有点对的最短路径组成的。

(3)构造d 维嵌入。用MDS 方法构造一个保持本征几何结构的d 维嵌入到空间Y 。

*()*()2

G G H D H

D τ=-

H 是与G D 同阶的单位矩阵，对()G D τ进行特征分解，取最大的前d 个特征值12,,,d λλλ 和对应的特征向量12,,,d V V V ，令i p V 为第p 个特征向量的第i 个成分，则对应的数据低维表示为1/2

p p

y V λ=。

优点：适用于学习内部平坦的低维流形，ISOMAP 结合了线性算法(如PCA 和MDS)的主要特征——计算的有效性、全局的优化性和渐进收敛性等。这种用测地距离来代替传统的欧氏距离的方法，可更有效的在低维空间来表达高维空间的数据，减少降维后损失的数据信息。

缺点：不适于学习有较大内在曲率的流形。在噪声干扰下，Isomap 用于可视化会有不稳定现象，取较大的邻域会产生短路现象，即低维流形中不同邻域部分的点投影后出现明显的混杂现象。选取较小的邻域，虽然能够保证整体结构的稳定，但低维投影结果会产生大量“空洞”，或使最短路径算法重构的图不连通。降维维数的确定通常是在本质维数未知的情况下进行的，经多次实验绘制残差曲线观察得到。Isomap 算法计算图上2点间的最短距离可采用Dijkstra 算法，但执行起来仍然比较慢。（12）

(l)当与高维流形等距的欧氏空间的子集不是凸型时，即当高维空间存在“空洞”时，要计算高维观测空间上任意样本点之间的距离很有可能发生弯曲异常，如果这样就会影响低维嵌入结果的表示。

(2)等距特征映射算法在数据拓扑空间有可能是不稳定的。因为如果选择的邻域过小，就会导致邻域图不连通，如果选择的邻域太大，又可能导致短路。

(3)使用Isomap 算法恢复非线性流形的几何结构的时候，所需的计算时间比较多，这主要是花在计算样本点之间的最短路径上。

由于已有的流形学习算法对噪音和算法参数都比较敏感，詹德川、周志华[14]针对Isomap 算法，提出了一种新方法，通过引入集成学习技术，扩大了可以产

生有效可视化结果的输入参数范围，并且降低了对噪音的敏感性。另外，赵连伟[15]等人完善了Isomap的理论基础，给出了连续流形与其低维参数空间等距映射的存在性证明，并区分了嵌入空间维数、高维数据的固有维数与流形维数这些容易混淆的概念，证明如果高维数据空间存在环状流形，流形维数则要小于嵌入空间维数．他们还给出一种有效的环状流形发现算法，以得到正确的低维参数空间。特别地，周志华等[16]提出了一种方法，可以从放大因子和延伸方向两方面显示出观测空间的高维数据与降维后的低维数据之间的联系，并实验比较了2种著名流形学习算法(Isomap和LLE)的性能。

文献[17]中，作者提出了一种基于Isomap的监督算法Weightedlso。在分类问题中，理想情况下属于同一类的样本在测量空间中应离得近一些，反之，不同类的样本则离得远一些。因此，作者在基本Isomap算法的第一步，计算各样本点间的欧氏距离时引进了一个常量参数，用来重新度量同一类样本间的距离，使它们离得更近。

Weightedlso算法虽然在一定程度上克服了流形学习方法分类效果较差的缺点，但在引入常量参数重新度量同类样本的距离时，由于噪声的影响，破坏了样本间的本质结构，使其可视化应用效果下降。在分类问题中，权值w在很大程度上影响着分类的结果，如何选取w值得进一步研究。

由于Weightedlso的不足，Xin Geng,De Chuan Zhan等[18]提出了另一种基于Isomap的监督算法SIsomap。该方法同样是修改了Isomap算法的第一步，用已知的样本所属类别信息重新定义了样本间的距离。

3．局部切空间排列算法LTSA (local tangent space alignment)[19] LTSA是一种基于切空间的流形学习方法，它通过逼近每一样本点的切空间来构建低维流形的局部几何，然后利用局部切空间排列求出整体低维嵌入坐标。

主要思想：找出每个数据点的近邻点，用邻域中低维切空间的坐标近似表示局部的非线性几何特征，再通过变换矩阵将各数据点邻域切空间的局部坐标映射到一个同一的全局坐标上，从而实现高维数据降维，即从n维数据中得到一个全局的d维坐标。(8)

算法步骤：

第一步：构造邻域。对于每个数据点

x，找出它的包括它自身在内的k个邻

域点，构成矩阵1

[,,]k

i i i X x x = 。

第二步：局部线性投影。对于每个样本点的邻域

X ，计算中心化矩阵

(/)T

i X I ee k -的最大

d 个奇异值对应的左奇异向量，并将这d 个左奇异向量组成

矩阵i Q 。 1由(/)T

i X I

ee k U V

-=∑计算得出左奇异向量U ，取出U 的前d 列构成矩阵i

Q （i Q 即为i x 点的切空间的近似）；

2计算各个邻域点在该切空间i Q 的投影：

()

1(/)[,,]T

i i i i i k Q X I ee k θθΦ=-=

()()j

i T

j i i i Q x x θ

第三步：局部坐标系统的排列。对每个邻域的局部切空间坐标

()

12(,,,)(1,2,,)

i i i i k i N θθθθ== ，构造转换矩阵d d

i L R

θ+?=∈。通过最小化

(/)T

i i i

T I ee k L θ--∑

的求解，最后化解可通过计算一个矩阵从第2小到第d+1

小的特征值所对应的特征向量。其中i θ+是θ的广义Moor-Penrose 逆。

优缺点：LTSA 能够有效地学习体现数据集低维流形结构的整体嵌入坐标，但它也存在两方面的不足：一方面算法中用于特征值分解的矩阵的阶数等于样本数，样本集较大时将无法处理；另一方面算法不能有效处理新来的样本点。（12）对此，提出了一些相应的改进算法。

但LTSA 也面临着同HLLE 类似的一些问题：LTSA 所反映的局部结构是它的局部d 维坐标系统，因此，由于噪声等因素的影响，当数据集的局部低维特征不明显或者不是d 维的时候，它的局部邻域到局部切空间的投影距离往往并不小。此时，构造的重建误差也不会小，这样LTSA 可能就无法得到理想的嵌入结果。此外，LTSA 对样本点的密度和曲率的变化的影响比较敏感，样本点的密度和曲率的变化使得样本点到流形局部切空间的投影产生偏差，而LTSA 构造排列矩阵的模型并没有将这种偏差计入考虑范围。这使得对于样本点密度和曲率变化较大的流形，LTSA 的嵌入结果可能会出现扭曲现象。

线性局部切空问排列(LLTSA)

针对LTSA 算法不能为新的测试样本提供一个明确的从高维到低维的映射，也就是所谓的“Out of Sample ”问题。提出了一个新的线性算法，线性局部切空问排列(LLTSA)[20]。该算法运用切信息作为数据的局部表达，然后将这些局部信息在可以用线性跌射得到的低维空间中排列。它先将每一个样本点邻域的切空间表示为流形的局部几何，再经线性映射实现样本数据从高维空间降维到低维空间，最终将整体嵌入坐标的求解问题转化为矩阵的广义特征值的求解问题。

算法步骤：

1近邻选择，构造邻接图G 2计算局部切坐标Θ 3计算投影向量：

a 求低维坐标对应近邻重建的目标函数最小化，即

i 2

,..:i i k i i L T i T

M in Y H L S t Y Y I

-Θ???=?∑

k H 是k 阶中心化矩阵且/T

k H I ee k =-。

b 代入线性变换i ()T

i Y X H α=，且由2

=得

i 2

,()..:i T

i k i i L T i T T

M in X H L S t X X I

ααα?-Θ???=?∑

..:T T

T T

M in X H B H X S t X H X I

ααααα???

=??

其中T

B SW W S

=,近邻选择矩阵

1i [,,,,]n S S S S = 使得i i

Y S Y =，并且12(,,,)n W diag W W W = ,且i ()k i i W H I +

=-ΘΘ。

d 求解下列广义特征方程的d 个最小特征值对应的特征向量作为d 个投影向量：

X H B H X X H X αλα

故由上述特征方程的d 个最小特征值12d ,,,λλλ 对应特征向量12d ,,,ααα ，

构成保持近邻重建特性的线性变换矩阵。

数据样本的类别信息对于入脸识别是非常重要的资源，但是LLTSA算法是非监督的学习方法，没有充分利用类别信息。为了提高算法的识别能力，需要对LLTSA算法的目标函数进行修改，以增加有关判别信息的限定，使原来无监督的学习方法发展为有监督的学习方法。而且为了提高数据的重建能力，算法应将解出的人脸子空间正交化，可称这种流形学习算法为正交判别的线性局部切空间排列(orthogonal discriminant linear local tangent space alignment，ODLLTSA)。[21] 由于用于特征值分解的矩阵的阶数等于样本点数，因此，当样本点集较大时将无法处理，此外，该方法不能有效处理新来的样本点。一种基于划分的局部切空间排列方法（partitional local tangent space alignment ,PLTSA）[22]被提出以改善这些缺点，它建立在主成分分析算法和LTSA方法的基础上，解决了主成分分析算法不能求出整体低维坐标和LTSA 中大规模矩阵的特征值分解问题，能够有效处理新来的样本点。

PLTSA是一种非监督的流形学习方法，不能充分利用数据的类别信息，而在人脸识别中数据样本的类别信息是非常重要的资源。为了提高算法的识别能力，需要对PLTSA算法进行改进，以增加判别信息的限定，使无监督的学习方法发展为有监督的学习方法。因此提出了一种基于划分的有监督局部切空间排列法（partitional supervised local tangent space alignment PSLTSA）[23]。

4.拉普拉斯特征映射法LE (Laplacian Eigenmap) [24]

LE方法将微分流形、谱图论的知识应用于降维之中，使人们对降维过程的认识产生了又一个新的飞跃，拓展了实际中降维方法的应用。

基本思想是：在高维空间中距离相隔很近的点投影到低维空间中像也应该相距很近，最终求解归结到求拉普拉斯算子的广义特征值问题。（8）实际上是使用有权图的Laplace矩阵来逼近D

R空间中的Laplace Beltrami 算子，以期达到最优投影的降维算法

算法步骤：

第一步，构造近邻图G。在数据集X中，计算每个样本点

x同其余样本点

之间的欧式距离，构造近邻图。寻找相对于每个样本点

x的欧式距离最近的k个

样本点规定为所求点的近邻点，若数据点i x 与j x 是邻接的，则图中点i x 与j x 之间存在一条边。

第二步，选择权值，构造权值矩阵W 。在近邻图中，为每一条边选择一个权值,i j w ，构造权值矩阵W 。权值的选择有两种选择方式：

1）若点i x 与j x 是邻接的，则设边的权值为2

,ex p (||||/)i j

i j w x x t =--，否则设

,i j w =0；t

是一个比例参数。

2）若点i x 与j x 是邻接的，则设变得权值为,i j w =1，否则设,i j w =0。在方法1）中，需要选择比例参数t ，方法2）不用选择比例参数t ，比较简单。

第三步，进行特征映射，计算d 维嵌入。对数据集X 构造的近邻图G ，映射到一条直线，用y 表示，使得邻接的点尽可能的靠近。设12(,,,)

N y

y y y = 是

一个未知的投影，可以通过在一定约束下，使得下面的目标函数达到最小来求解。

()i j ij ij

y y w -∑

用D 表示对一个对角矩阵，它的每个对角元素为权值矩阵W 的每行所有元素的和，即,,i i

i j

D w =

∑

，L=D-W 是邻接图的Laplacian 矩阵。对任意的y 有

()(2)2T

i j ij i

j i j ij ij

y y w y

y y y w y L y

+-=∑

∑

给定约束条件T y D y =1，以消除坐标尺度对映射y 的影响，最小化上式的和函数，利用矩阵迹的性质和拉格朗日乘子法，即可求解。相当于利用下式计算特征值和特征向量的问题L y

D y

λ=

上述特征方程的最小的d 个非零特征值对应的特征向量12,,,d y y y ，则数据X 的低维嵌入表示为12[,,,]

d Y

y y y =

LE 是局部的非线性方法，其突出特点是与谱图理论有着很紧密的联系。从算法描述中可以看到，拉普拉斯映射和LLE 算法类似，待定参数相同，求解的是稀疏矩阵的广义特征值问题，它能使输入空间中离得很近的点在低维空间也离

得很近，故可用于聚类。（12）缺点类似LLE 。

LPP 局部保留投影（Locality preserving projection ，LPP ）

LPP 局部保留投影（Locality preserving projection ，LPP ）作为LE 的线性化是其中最早提出的算法。[25]

LPP 算法的主要问题在于建立k 近邻域图，使它能很好地表现数据流形的局部结构。然后，根据建立的k 邻图来获得图像的投影，最终在投影得到的子空问中进行特征识别。

算法把非线性变换转换成了近似的线性形式。所以，一个测试样本要转换到新空间中去，只要乘以从训练集计算得到的线性矩阵即可。这解决了LLE 、LE 等算法不能显式表示的问题，实际上这种显式转换是非线性流行空间的一种线性回归和近似。与前述全局最优算法相比，这些算法保持了局部信息，同时给出了简便的变换形式，可以说是全局最优和局部最优间的折衷。

算法步骤：

1近邻选择，构造邻接图G 2计算近邻相似度W 3计算投影向量：

a 求低维坐标对应近邻重建的目标函数最小化，即

,1()2..:i j ij

i j

T M in y y W S t YY I

?-??

=?∑

b 代入线性变换T

y x α=,得

2,1()2..:T T

i j ij

i j

T T M in x x W S t X X I αααα?-??

∑

..:T T

T T

M in X L X S t X X I

ααααα???

=??

其中L=D-W,而对角矩阵D 的对角线元素ii

D W =

∑

d 求解下列广义特征方程的d 个最小特征值对应的特征向量作为d 个投影向量：

聚类分析K-means算法综述

聚类分析K-means算法综述摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤（1）从n个数据对象任意选择k 个对象作为初始聚类中心（2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分（3）重新计算每个（有变化）聚类的均值（中心对象）（4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2）形式化描述输入：数据集D，划分簇的个数k 输出：k个簇的集合（1）从数据集D中任意选择k个对象作为初始簇的中心；（2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离（5）将对象P指派到与其最近（距离最短）的簇；

（6）End For （7）计算每个簇中对象的均值，作为新的簇的中心；（8）Until k个簇的簇中心不再发生变化对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。

高维数据降维方法研究

·博士论坛· 高维数据降维方法研究余肖生,周　宁 (武汉大学信息资源研究中心,湖北武汉430072) 摘　要:本文介绍了MDS 、Isomap 等三种主要的高维数据降维方法,同时对这些降维方法的作用进行了探讨。关键词:高维数据;降维;MDS ;Isomap ;LLE 中图分类号:G354 文献标识码:A 文章编号:1007-7634(2007)08-1248-04 Research on Methods of Dimensionality Reduction in High -dimensional Data YU Xiao -s heng ,ZH OU Ning (Research Center for Information Resourc es of Wuhan University ,W uhan 430072,China ) A bstract :In the paper the authors introduce three ke y methods of dimensionality r eduction in high -dimen -sional dataset ,such as MDS ,Isomap .At the same time the authors discuss applications of those methods .Key words :high -dimensional data ;dimensionality reduction ;MDS ;Isomap ;LLE 收稿日期:2006-12-20 基金项目:国家自科基金资助项目(70473068) 作者简介:余肖生(1973-),男,湖北监利人,博士研究生,从事信息管理与电子商务研究;周　宁(1943-),男, 湖北钟祥人,教授,博士生导师,从事信息组织与检索、信息系统工程、电子商务与电子政务研究. 1　引言随着计算机技术、多媒体技术的发展,在实际应用中经常会碰到高维数据,如文档词频数据、交易数据及多媒体数据等。随着数据维数的升高,高维索引结构的性能迅速下降,在低维空间中,我们经常采用Lp 距离(当p =1时,Lp 距离称为Man -hattan 距离;当p =2时,Lp 距离称为Euclidean 距离)作为数据之间的相似性度量,在高维空间中很多情况下这种相似性的概念不复存在,这就给基于高维数据的知识挖掘带来了严峻的考验【1】。而这些高维数据通常包含许多冗余,其本质维往往比原始的数据维要小得多,因此高维数据的处理问题可以归结为通过相关的降维方法减少一些不太相关的数据而降低它的维数,然后用低维数据的处理办法进行处理【2-3】。高维数据成功处理的关键在于降维方法的选择,因此笔者拟先介绍三种主要降维方法, 接着讨论高维数据降维方法的一些应用。 2　高维数据的主要降维方法高维数据的降维方法有多种,本文主要讨论有代表性的几种方法。 2.1　MDS (multidimensional scaling )方法 MDS 是数据分析技术的集合,不仅在这个空间上忠实地表达数据之间联系,而且还要降低数据集的维数,以便人们对数据集的观察。这种方法实质是一种加入矩阵转换的统计模式,它将多维信息通过矩阵运算转换到低维空间中,并保持原始信息之间的相互关系【4】。每个对象或事件在多维空间上都可以通过一个点表示。在这个空间上点与点之间的距离和对象与对象之间的相似性密切相关。即两个相似的对象通过空间临近的两个点来表示,且两个不相似的对象第25卷第8期2007年8月情　报　科　学 Vol .25,No .8 August ,2007

模型降阶方法综述

模型降阶方法综述大系统模型降阶是一个活跃的研究领域，比较成熟的经典降阶方法主要有：Pade逼近法，时间矩法，连分式法，Routh逼近法及棍合法等。本文综述了这一领域的现有文献，介绍了每种降阶方法的基本思想、优缺点和适用范围，特别指出了一些新的经典模型降阶方法的进展。文中最后提出了模型降阶方法的可能研究方向。一、Pade逼近法 Pade逼近法是大系统模型简化中最早出现的一种经典降阶方法。到目前为止，人们仍然公认它是一种行之有效的传递函数降阶法。Pade逼近法是泰勒级数展开理论的应用，适用于传递函数可表示成有理多项式分式(或传递函数阵为有理分式阵)的场合。降阶方法简单，易于编制上机程序，低频(稳态)拟合性能好。但是，Pade逼近法的高频(动态)拟合性能较差且不能保证降阶模型的稳定性。因而在模型降阶方法中，很少单独使用Pade逼近法。为了弥补Pade逼近法的不足，Brown等引入了使降阶模型稳定的补充性能准则，但却提高了降阶模型的阶次；Rossen等把造成降阶模型不稳定的极点隔离开来，并用任意稳定极点取代，可以防止降阶模型不稳定，但加大了计算量；Chuang和Shamash先后提出在0 s=和s=∞附近交替展成Pade近似式，可获得有较好动态拟合性能的降阶模型；Shih等采用线性变换方法将() G s中不稳定的极点映射到另一平面，以扩大Pade展开式的收敛域，并由此选出稳定的降阶模型。

为了克服泰勒级数收敛慢的弱点，Calfe等提出了切比雪夫多项式模型降阶方法，可获得稳定的降阶模型；Bistritz等提出了广义切比雪夫一Pade逼近法，即Darlington多项式展开法。这两种降阶方法均可使降阶模型在预定的区间上既稳定又具有最小相位，但计算量大，仅适用于单变量系统。二、时间矩法时间矩法首先由Paynter提出，采用与Pade逼近法类似的方法，把高阶系统和降阶模型都展成多项式，再令时间矩对应项相等，可以求得降阶模型的各系数。因此，时间矩法本质上仍是Pade遏近法，其优缺点也相似。有的学者从时间矩或马尔可夫参数组成的Hankel阵出发，提出了相应的模型降阶方法，但本质上仍属于时间矩法的范畴。三、连分式法连分式是函数论中研究得比较深入的课题。1974年左右，开始应用连分式进行模型降阶，5年后，又推广于多变量系统降阶。连分式降阶法的基本出发点是：将真有理传递函数G(s)在0 s 附近展成连分式，然后截取前面起主要作用的若干项(也称偏系数)构成降阶模型。由于连分式比其他多项式或幂级数展开式收敛快，少量偏系数就能反映原系统的主要信息，所以连分式法是一种很有效的频域模型降阶方法，至今仍被广泛应用。在降阶过程中，常用的连分式有：Cauer一I型，Cauer一II型，Cauer一III型，修正Cauer型和Jordan型等。在现代频域降阶法中，

高维数据的低维表示综述

高维数据的低维表示综述一、研究背景在科学研究中，我们经常要对数据进行处理。而这些数据通常都位于维数较高的空间，例如，当我们处理200个256*256的图片序列时，通常我们将图片拉成一个向量，这样，我们得到了65536*200的数据，如果直接对这些数据进行处理，会有以下问题：首先，会出现所谓的“位数灾难”问题，巨大的计算量将使我们无法忍受；其次，这些数据通常没有反映出数据的本质特征，如果直接对他们进行处理，不会得到理想的结果。所以，通常我们需要首先对数据进行降维，然后对降维后的数据进行处理。降维的基本原理是把数据样本从高维输入空间通过线性或非线性映射投影到一个低维空间，从而找出隐藏在高维观测数据中有意义的低维结构。（8）之所以能对高维数据进行降维，是因为数据的原始表示常常包含大量冗余： · 有些变量的变化比测量引入的噪声还要小，因此可以看作是无关的 · 有些变量和其他的变量有很强的相关性(例如是其他变量的线性组合或是其他函数依赖关系)，可以找到一组新的不相关的变量。（3）从几何的观点来看，降维可以看成是挖掘嵌入在高维数据中的低维线性或非线性流形。这种嵌入保留了原始数据的几何特性，即在高维空间中靠近的点在嵌入空间中也相互靠近。（12）数据降维是以牺牲一部分信息为代价的，把高维数据通过投影映射到低维空间中，势必会造成一些原始信息的损失。所以在对高维数据实施降维的过程中如何在最优的保持原始数据的本质的前提下，实现高维数据的低维表示，是研究的重点。（8）二、降维问题 1．定义定义1.1降维问题的模型为(,)X F ，其中D 维数据空间集合{}1N l l X x ==（一般为D R 的一个子集），映射F :F X Y →(),x y F x →=

基于聚类的图像分割方法综述

信息疼术2018年第6期文章编号=1009 -2552 (2018)06 -0092 -03 DOI：10.13274/https://www.wendangku.net/doc/8c12306786.html,ki.hdzj.2018. 06.019 基于聚类的图像分割方法综述赵祥宇\陈沫涵2 (1.上海理工大学光电信息与计算机学院，上海200093; 2.上海西南位育中学，上海200093) 摘要：图像分割是图像识别和机器视觉领域中关键的预处理操作。分割理论算法众多，文中具体介绍基于聚类的分割算法的思想和原理，并将包含的典型算法的优缺点进行介绍和分析。经过比较后，归纳了在具体应用中如何对图像分割算法的抉择问题。近年来传统分割算法不断被科研工作者优化和组合，相信会有更多的分割新算法井喷而出。关键词：聚类算法；图像分割；分类中图分类号：TP391.41 文献标识码：A A survey of image segmentation based on clustering ZHAO Xiang-yu1，CHEN Mo-han2 (1.School of Optical Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai200093，China；2.Shanghai Southwest Weiyu Middle School，Shanghai200093，China) Abstract:Image segmentation is a key preprocessing operation in image recognition and machine vision. There are many existing theoretical methods,and this paper introduces the working principle ol image segmentation algorithm based on clustering.Firstly,the advantages and disadvantages ol several typical algorithms are introduced and analyzed.Alter comparison,the paper summarizes the problem ol the selection ol image segmentation algorithm in practical work.In recent years,the traditional segmentation algorithms were improved and combined by the researchers,it believes that more new algorithms are blown out. Key words:clustering algorithm；image segmentation；classilication 0引百近年来科学技术的不断发展，计算机视觉和图像识别发挥着至关重要的作用。在实际应用和科学研究中图像处理必不可少,进行图像处理必然用到图像分割方法,根据检测图像中像素不重叠子区域，将感兴趣目标区域分离出来。传统的图像分割方法:阈值法[1]、区域法[2]、边缘法[3]等。近年来传统分割算法不断被研究人员改进和结合，出现了基于超像素的分割方法[4]，本文主要介绍超像素方法中基于聚类的经典方法，如Mean Shift算法、K-m eans 算法、Fuzzy C-mean算法、Medoidshilt算法、Turbopixels算法和 SLIC 算法。简要分析各算法的基本思想和分割效果。 1聚类算法 1.1 Mean Shil't算法 1975年,Fukunaga[5]提出一种快速统计迭代算法，即Mean Shilt算法（均值漂移算法）。直到1995 年,Cheng[6]对其进行改进，定义了核函数和权值系数，在全局优化和聚类等方面的应用，扩大了 Mean shil't算法适用范围。1997至2003年间，Co-maniciu[7-9]提出了基于核密度梯度估计的迭代式搜索算法,并将该方法应用在图像平滑、分割和视频跟踪等领域。均值漂移算法的基本思想是通过反复迭代计算当前点的偏移均值，并挪动被计算点，经过反复迭代计算和多次挪动，循环判断是否满足条件, 达到后则终止迭代过程[10]。Mean shil't的基本形式为：收稿日期：2017-06 -13 基金项目：国家自然科学基金资助项目（81101116) 作者简介：赵祥宇（1992-)，男，硕士研究生，研究方向为数字图像处理。 —92 —

较大规模数据应用PCA降维的一种方法

计算机工程应用技术本栏目责任编辑：梁书较大规模数据应用PCA 降维的一种方法赵桂儒（中国地震台网中心，北京100045）摘要：PCA 是一种常用的线性降维方法，但在实际应用中，当数据规模比较大时无法将样本数据全部读入内存进行分析计算。文章提出了一种针对较大规模数据应用PCA 进行降维的方法，该方法在不借助Hadoop 云计算平台的条件下解决了较大规模数据不能直接降维的问题，实际证明该方法具有很好的应用效果。关键词：主成分分析；降维；大数据中图分类号：TP311 文献标识码：A 文章编号：1009-3044(2014)08-1835-03 A Method of Dimensionality Reduction for Large Scale Data Using PCA ZHAO Gui-ru (China Earthquake Networks Center,Beijing 100045,China) Abstract:PCA is a general method of linear dimensionality reduction.It is unable to read all the sample data into the memory to do analysis when the data scale becomes large.A method of dimensionality reduction for large scale data using PCA without Ha?doop is proposed in this paper.This method solves the problem that it can ’t do dimensionality reduction directly on large scale data.Practice proves that this method has a good application effect.Key words:PCA;dimensionality reduction;large scale data 现实生活中人们往往需要用多变量描述大量的复杂事物和现象，这些变量抽象出来就是高维数据。高维数据提供了有关客观现象极其丰富、详细的信息，但另一方面，数据维数的大幅度提高给随后的数据处理工作带来了前所未有的困难。因此数据降维在许多领域起着越来越重要的作用，通过数据降维可以减轻维数灾难和高维空间中其他不相关属性。所谓数据降维是指通过线性或非线性映射将样本从高维空间映射到低维空间，从而获得高维数据的一个有意义的低维表示的过程。主成分分析（Principal Component Analysis ，PCA ）是通过对原始变量的相关矩阵或协方差矩阵内部结构的研究，将多个变量转换为少数几个综合变量即主成分，从而达到降维目的的一种常用的线性降维方法。这些主成分能够反映原始变量的绝大部分信息，它们通常表示为原始变量的线性组合。在实际应用中当数据规模超过计算机内存容量(例如16G)时就无法将样本数据全部读入内存来分析原始变量的内部结构，这成为PCA 在实际应用中存在的一个问题。该文从描述PCA 变换的基本步骤出发，提出了一种不需要Hadoop 等云计算平台即可对较大规模数据进行降维的一种方法，实际证明该方法具有很好的应用效果。 1PCA 变换的基本步骤 PCA 是对数据进行分析的一种技术，主要用于数据降维，方法是利用投影矩阵将高维数据投影到较低维空间。PCA 降维的一般步骤是求取样本矩阵的协方差矩阵，计算协方差矩阵的特征值及其对应的特征向量，由选择出的特征向量构成这个投影矩阵。 ?è???????? ÷÷÷÷÷÷cov(x 1,x 1),cov(x 1,x 2),cov(x 1,x 3),?,cov(x 1,x N )cov(x 2,x 1),cov(x 2,x 2),cov(x 2,x 3),?,cov(x 2,x N ) ?cov(x N ,x 1),cov(x N ,x 2),cov(x N ,x 3),?,cov(x N ,x N )（1）假设X M ×N 是一个M ×N (M >N ),用PCA 对X M ×N 进行降维分析，其步骤为：1)将矩阵X M ×N 特征中心化，计算矩阵X M ×N 的样本的协方差矩阵C N ×N ，计算出的协方差矩阵如式(1)所示，式中x i 代表X M ×N 特征中心化后的第i 列； 2)计算协方差矩阵C N ×N 的特征向量e 1,e 2...e N 和对应的特征值λ1,λ2...λN ，将特征值按从大到小排序； 3)根据特征值大小计算协方差矩阵的贡献率及累计贡献率，计算公式为： θi =λi ∑n =1 N λn i =1,2,...,N （2）收稿日期：2014-01-20基金项目：国家留学基金资助项目（201204190040）作者简介：赵桂儒（1983-），男，山东聊城人，工程师，硕士，迈阿密大学访问学者，主要研究方向为多媒体信息处理。 1835

多组分分析方法综述

重金属多组分分析的研究现状近年来，随着科技的进步，单组分重金属的检测技术已经非常成熟，但是在实际污染体系中重金属离子种类繁多，且它们之间往往存在相互干扰，传统的化学分析方法和化学分析仪器难以一次性精确的检测出各个重金属离子的浓度，需要对共存组分进行同时测定。对共存组分进行同时测定，传统的化学分析方法是首先通过加入各种掩蔽剂进行组分的预分离，然后采用单组分重金属检测技术进行分析检测。这种方法的分离过程往往冗长繁琐，实验条件苛刻，费时费力，而且检测精度低，无法应用于污染现场的检测。随着计算机科学技术、光谱学和化学信息学的发展，复杂体系的多组分分析已成为当今光谱技术的研究热点，应用范围涉及环境监测、石油化工、高分子化工、食品工业和制药工业等领域，而且需求日益显著。由于多重金属离子共存时会产生重金属离子间的相互作用，因此在用化学分析仪器检测时会产生相干数据干扰，对实验结果产生影响，为了使测试结果更加准确，需要在实验的基础上建立数学模型，用于数据处理，消除各重金属离子共存时产生的相干数据干扰。近年来，引入化学计量学手段，用“数学分离”部分代替复杂的“化学分离”，从而达到重金属离子的快速、简便分析测定[1]。化学计量学是一门通过统计学或数学方法将对化学体系的测量值与体系的状态之间建立联系的学科，它应用数学、统计学和其他方法和手段（包括计算机）选择最优试验设计和测量方法，并通过对测量数据的处理和解析，最大限度地获取有关物质系统的成分、结构及其他相关信息。目前，已有许多化学计量学方法从不同程度和不同方面解决了分析化学中多组分同时测定的问题，如偏最小二乘法（PLS）、主成分回归法（PCR）、Kalman滤波法、多元线性回归（MLR）等，这些方法减少了分离的麻烦，并使试验更加科学合理。 (1) 光谱预处理技术这些方法用来降噪、消除无关信息。 ①主成分分析法在处理多元样本数据时，假设总体为X=（x1,x1,x3…xn），其中每个xi （i=1,2,3,…n）为要考察的数量指标，在实践中常常遇到的情况是这n个指标之间存在着相关关系。如果能从这n个指标中构造出k个互不相关的所谓综合指标（k

数据降维方法分析与研究_吴晓婷

收稿日期:2008211226;修回日期:2009201224 基金项目:国家自然科学基金资助项目(60372071);中国科学院自动化研究所复杂系统与智能科学重点实验室开放课题基金资助项目(20070101);辽宁省教育厅高等学校科学研究基金资助项目(2004C031) 作者简介:吴晓婷(19852),女(蒙古族),内蒙古呼伦贝尔人,硕士研究生,主要研究方向为数据降维、模式识别等(xiaoting wu85@hot m ail . com );闫德勤(19622),男,博士,主要研究方向为模式识别、数字水印和数据挖掘等. 数据降维方法分析与研究 3 吴晓婷,闫德勤 (辽宁师范大学计算机与信息技术学院,辽宁大连116081) 摘　要:全面总结现有的数据降维方法,对具有代表性的降维方法进行了系统分类,详细地阐述了典型的降维方法,并从算法的时间复杂度和优缺点两方面对这些算法进行了深入的分析和比较。最后提出了数据降维中仍待解决的问题。关键词:数据降维;主成分分析;局部线性嵌入;等度规映射;计算复杂度中图分类号:TP301 文献标志码:A 文章编号:100123695(2009)0822832204 doi:10.3969/j .jssn .100123695.2009.08.008 Analysis and research on method of data dimensi onality reducti on WU Xiao 2ting,Y AN De 2qin (School of Co m puter &Infor m ation Technology,L iaoning N or m al U niversity,D alian L iaoning 116081,China ) Abstract:This paper gave a comp rehensive su mmarizati on of existing di m ensi onality reducti on methods,as well as made a classificati on t o the rep resentative methods systematically and described s ome typ ical methods in detail.Further more,it deep ly analyzed and compared these methods by their computati onal comp lexity and their advantages and disadvantages .Finally,it p r oposed the crucial p r oble m s which needed t o be res olved in future work in data di m ensi onality reducti on . Key words:data di m ensi onality reducti on;p rinci pal component analysis (PCA );l ocally linear e mbedding (LLE );is ometric mapp ing;computati onal comp lexity 近年来,数据降维在许多领域起着越来越重要的作用。通过数据降维可以减轻维数灾难和高维空间中其他不相关属性,从而促进高维数据的分类、可视化及压缩。所谓数据降维是指通过线性或非线性映射将样本从高维空间映射到低维空间,从而获得高维数据的一个有意义的低维表示的过程。数据降维的数学描述如下:a )X ={x i }N i =1是D 维空间中的一个样本集, Y ={y i }N i =1是d (d <

数据挖掘中的聚类算法综述

收稿日期:2006201204;修返日期:2006203219基金项目:国家自然科学基金资助项目(60473117) 数据挖掘中的聚类算法综述 3 贺　玲,吴玲达,蔡益朝 (国防科学技术大学信息系统与管理学院,湖南长沙410073) 摘　要:聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。全面总结了数据挖掘中聚类算法的研究现状,分析比较了它们的性能差异和各自存在的优点及问题,并结合多媒体领域的应用需求指出了其今后的发展趋势。关键词:数据挖掘;聚类;聚类算法中图法分类号:TP391 文献标识码:A 文章编号:100123695(2007)0120010204 Survey of Clustering A lgorith m s in Data M ining HE L ing,WU L ing 2da,CA I Yi 2chao (College of Infor m ation Syste m &M anage m ent,N ational U niversity of D efense Technology,Changsha Hunan 410073,China ) Abstract:Clustering is an i m portant technique in Data M ining (DM )f or the discovery of data distributi on and latent data pattern .This paper p r ovides a detailed survey of current clustering algorith m s in DM at first,then it makes a comparis on a mong the m,illustrates the merits existing in the m,and identifies the p r oblem s t o be s olved and the ne w directi ons in the fu 2ture according t o the app licati on require ments in multi m edia domain .Key works:Data M ining;Clustering;Clustering A lgorith m 1　引言随着信息技术和计算机技术的迅猛发展,人们面临着越来越多的文本、图像、视频以及音频数据,为帮助用户从这些大量数据中分析出其间所蕴涵的有价值的知识,数据挖掘(Data M ining,DM )技术应运而生。所谓数据挖掘,就是从大量无序的数据中发现隐含的、有效的、有价值的、可理解的模式,进而发现有用的知识,并得出时间的趋向和关联,为用户提供问题求解层次的决策支持能力。与此同时,聚类作为数据挖掘的主要方法之一,也越来越引起人们的关注。本文比较了数据挖掘中现有聚类算法的性能,分析了它们各自的优缺点并指出了其今后的发展趋势。 2　DM 中现有的聚类算法聚类是一种常见的数据分析工具,其目的是把大量数据点的集合分成若干类,使得每个类中的数据之间最大程度地相似,而不同类中的数据最大程度地不同。在多媒体信息检索及数据挖掘的过程中,聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。本文以聚类算法所采用的基本思想为依据将它们分为五类,即层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法以及用于高维数据的聚类算法,如图1所示。聚类层次聚类算法聚合聚类:Single 2L ink,Comp lete 2L ink,Average 2L ink 分解聚类分割聚类算法基于密度的聚类基于网格的聚类基于图论的聚类基于平方误差的迭代重分配聚类:概率聚类、最近邻聚类、K 2medoids 、K 2means 基于约束的聚类算法机器学习中的聚类算法人工神经网络方法基于进化理论的方法:模拟退火、遗传算法用于高维数据的聚类算法子空间聚类联合聚类图1　聚类算法分类示意图 211　层次聚类算法层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类,它又可以分为两类,即自底向上的聚合层次聚类和自顶向下的分解层次聚类。聚合聚类的策略是先将每个对象各自作为一个原子聚类,然后对这些原子聚类逐层进行聚合,直至满足一定的终止条件;后者则与前者相反,它先将所有的对象都看成一个聚类,然后将其不断分解直至满足终止条件。对于聚合聚类算法来讲,根据度量两个子类的相似度时所依据的距离不同,又可将其分为基于Single 2L ink,Comp lete 2L ink 和Average 2L ink 的聚合聚类。Single 2L ink 在这三者中应用最为广泛,它根据两个聚类中相隔最近的两个点之间的距离来评价这两个类之间的相似程度,而后两者则分别依据两类中数据点之间的最远距离和平均距离来进行相似度评价。 CURE,ROCK 和CHAME LE ON 算法是聚合聚类中最具代表性的三个方法。 Guha 等人在1998年提出了C URE 算法 [1] 。该方法不用单个中心或对象来代表一个聚类,而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类,这样就可以

高维面板数据降维与变量选择方法研究

高维面板数据降维与变量选择方法研究张波方国斌 2012-12-14 14:35:56 来源：《统计与信息论坛》(西安)2012年6期第21～28页内容提要：从介绍高维面板数据的一般特征入手，在总结高维面板数据在实际应用中所表现出的各种不同类型及其研究理论与方法的同时，主要介绍高维面板数据因子模型和混合效应模型；对混合效应模型随机效应和边际效应中的高维协方差矩阵以及经济数据中出现的多指标大维数据的研究进展进行述评；针对高维面板数据未来的发展方向、理论与应用中尚待解决的一些关键问题进行分析与展望。关键词：高维面板数据降维变量选择作者简介：张波，中国人民大学统计学院（北京100872）；方国斌，中国人民大学统计学院，安徽财经大学统计与应用数学学院（安徽蚌埠233030）。一、引言在社会现象观测和科学实验过程中经常会产生面板数据。这类数据通过对多个个体在不同时间点上进行重复测度，得到每个个体在不同样本点上的多重观测值，形成时间序列和横截面相结合的数据，也就是所谓的“面板数据”。由于应用背景的不同，面板数据有时也称作纵向数据（longitudinal data）。面板数据广泛产生于经济学、管理学、生物学、心理学、健康科学等诸多领域。

随着信息技术的高速发展，数据采集、存储和处理能力不断提高，所谓的高维数据分析问题不断涌现。对于多元统计分析而言，高维问题一般指如下两种情形：一种是变量个数p较大而样本量n相对较小，例如药物试验中有成千上万个观测指标而可用于实验观测的病人个数较少；另一种是变量个数户不大但是样本个数n较多，例如一项全国调查牵涉到大量的调查对象，而观测指标个数相对较少。面板数据高维问题较多元（时序）高维问题更为复杂，因为面板数据至少包括两个维度：时间和横截面。在实际应用中，不同个体在不同时间进行观测时可以获得多个指标值。为了以下论述的方便，用p表示指标个数，T表示观测期长度，N表示个体（individual）或主题（subject）个数。数理统计中所提到的高维（大维）问题，通常是指个体数N、时期长度T或指标个数p这三个变量中的一个或多个可以趋向于无穷。具体应用中，只要N、T和p中有一个或多个大于某个给定的临界值，都称为高维问题。本文主要研究两种基本类型的高维面板问题：一类为面板数据分析中解释变量个数p非常多，超过个体数N和时期数T，比如零售商业网点成千上万种商品扫描数据，央行和国家统计部门得到的多个指标在不同个体宏观经济观测数据等；另一类是混合效应模型中随机效应和固定效应设定时方差协方差矩阵所需确定的参数个数较多，某些参数的值趋向于零，要对方差协方差矩阵进行变量选择，此时针对固定效应和随机效应可以采用不同的变量选择策略。二、高维面板数据因子模型大型数据集构成的社会经济面板的特点是具有成百上千个观测指标，也就是具有所谓的高维特征。由于这种特征的存在，采用经典统计计量分析方法很难进行处理。因子模型（factor model）不仅可以有效降低数据的维度，而且可以充

聚类算法研究综述

电脑知识与技术本栏目责任编辑：闻翔军数据库及信息管理１引言数据挖掘是指从从大量无序的数据中提取隐含的、有效的、可理解的、对决策有潜在价值的知识和规则，为用户提供问题求解层次的决策支持能力。数据挖掘主要的算法有分类模式、关联规则、决策树、序列模式、聚类模式分析、神经网络算法等等。聚类算法是一种有效的非监督机器学习算法，是数据挖掘中的一个非常重要的研究课题。当人们使用数据挖掘工具对数据中的模型和关系进行辨识的时候，通常第一个步骤就是聚类，其目的就是将集中的数据人为地划分成若干类，使簇内相似度尽可能大、簇间相似度尽可能小，以揭示这些数据分布的真实情况。但任何聚类算法都对数据集本身有一定的预先假设，根据文献［１］的理论，如果数据集本身的分布并不符合预先的假设，则算法的结果将毫无意义。因此，面对特定的应用问题，如何选择合适的聚类算法是聚类分析研究中的一个重要课题。本文比较了数据挖掘中现有聚类算法的性能，分析了它们各自的优缺点，并指出了其今后的发展趋势。２聚类算法分类研究聚类的目的是把大量数据点的集合分成若干类，使得每个类中的数据之间最大程度地相似，而不同类中的数据最大程度地不同。通常聚类算法可以分为层次聚类、分割聚类、密度型聚类、网格型聚类和其他聚类等几种。２．１层次聚类层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类，它又可以分为两类，即自底向上的聚合层次聚类和自顶向下的分裂层次聚类。聚结型算法采用自底向上的策略，首先把每个对象单独作为一个聚类，然后根据一定的规则合并成为越来越大的聚类，直到最后所有的对象都归入到一个聚类中。大多数层次聚类算法都属于聚结型算法，它们之间的区别在于类间相似度的定义不同。与聚结型算法相反，分裂型算法采用自顶向下的方法，它先将所有的对象都看成一个聚类，然后将其不断分解直至每个对象都独自归入一个聚类。一般情况下不使用分裂型方法，因为在较高的层次很难进行正确的拆分。纯粹的层次聚类算法的缺点在于一旦进行合并或分裂之后，就无法再进行调整。现在的一些研究侧重于层次聚类算法与循环的重新分配方法的结合。主要的层次聚类算法有ＢＩＲＣＨ，ＣＵＲＥ，ＲＯＣＫ，ＣＨＡＭＥＬＥＯＮ，ＡＭＯＥＢＡ，ＣＯＢＷＥＢ，ＣｌｕｓｔｅｒｉｎｇｗｉｔｈＲａｎｄｏｍＷａｌｋｓ算法等。ＣＵＲＥ算法［２］不用单个中心或对象来代表一个聚类，而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类，这样就可以识别具有复杂形状和不同大小的聚类，从而能很好地过滤孤立点。ＲＯＣＫ算法［３］是对ＣＵＲＥ的改进，除了具有ＣＵＲＥ算法的一些优良特性之外，它还适用于类别属性的数据。ＣＨＡＭＥＬＥＯＮ算法［４］是Ｋａｒｙｐｉｓ等人于１９９９年提出来的，它在聚合聚类的过程中利用了动态建模的技术。２．２分割聚类分割聚类算法是另外一种重要的聚类方法。它先将数据点集分为ｋ个划分，每个划分作为一个聚类，然后从这ｋ个初始划分开始，通过重复的控制策略，使某个准则最优化，而每个聚类由其质心来代表（ｋ－ｍｅａｎｓ算法），或者由该聚类中最靠近中心的一个对象来代表（ｋ－ｍｅｄｏｉｄｓ算法），以达到最终的结果。分割聚类算法收敛速度快，缺点在于它倾向于识别凸形分布大小相近、密度相近的聚类，不能发现分布形状比较复杂的聚类，它要求类别数目ｋ可以合理地估计，并且初始中心的选择和噪声会对聚类结果产生很大影响。这类方法又可分为基于密度的聚类、基于网格的聚类等。很多算法中都使用距离来描述数据之间的相似性，但是，对于非凸数据集，只用距离来描述是不够的。对于这种情况，要用密度来取代相似性，这就是基于密度的聚类算法。基于密度的算法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可以发现任意形状的类。此类算法除了可以发现任意形状的类，还能够有效去除噪声。基于网格的聚类算法，把空间量化为有限个单元（即长方体或超长方体），然后对量化后的空间进行聚类。此类算法具有很快的处理速度。缺点是只能发现边界是水平或垂直的聚类，而不能检测到斜边界。此类算法具有很快的处理速度。时间复杂度一般由网格单元的数目决定，而与数据集的大小无关。此外，聚类的精度取决于网格单元的大小。此类算法不适用于高维情况，因为网格单元的数目随着维数的增加而呈指数增长。所有基于网格的聚类算法都存在下列问题：一是如何选择合适的单元大小和数目；二是怎样对每个单元中对象的信息进行汇总。主要的分割聚类算法有ｋ－ｍｅａｎｓ，ＥＭ，ｋ－ｍｅｄｏｉｄｓ，收稿日期：２００７－０６－１０作者简介：项冰冰（１９８０－），女，安徽合肥人，安徽大学助教，工学学士，研究方向：数据挖掘，人工智能；钱光超（１９８２－），男，安徽安徽无为人，安徽大学计算机科学与技术学院０５级研究生，工学学士。聚类算法研究综述项冰冰１，钱光超２（１．安徽大学数学与计算科学学院安徽合肥２３０３９；２．安徽大学计算机科学与技术学院安徽合肥２３００３９）摘要：聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。阐述了聚类算法基本原理，总结了聚类算法的研究现状，按照聚类算法的分类，分析比较了几种典型聚类的性能差异和各自存在的优点及问题，并结合应用需求指出了其今后的发展趋势。关键词：数据挖掘；聚类分析；聚类算法中图分类号：ＴＰ３０１．６文献标识码：Ａ文章编号：１００９－３０４４（２００７）１２－２１５００－０２ＴｈｅＲｅｓｅａｒｃｈｏｆＣｌｕｓｔｅｒｉｎｇＡｌｇｏｒｉｔｈｍｓＸＩＡＮＧＢｉｎｇ－ｂｉｎｇ１，ＱＩＡＮＧｕａｎｇ－ｃｈａｏ２（１．ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔａｔｉｏｎａｌＳｃｉｅｎｃｅ，ＡｎｈｕｉＵｎｉｖｅｒｓｉｔｙ，Ｈｅｆｅｉ，ＡｎｈｕｉＰｒｏｖｉｎｃｅ２３００３９，Ｃｈｉｎａ；２．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＡｎｈｕｉＵｎｉｖｅｒｓｉｔｙ，Ｈｅｆｅｉ，ＡｎｈｕｉＰｒｏｖｉｎｃｅ２３００３９，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒｉｎｇｉｓａｎｉｍｐｏｒｔａｎｔｔｅｃｈｎｉｑｕｅｉｎｄａｔａｍｉｎｉｎｇ．Ｉｔ’ ｓｕｓｅｄｔｏｄｉｓｃｏｖｅｒｔｈｅｄａｔａｄｉｓｔｒｉｂｕｔｉｏｎａｎｄｃｏｎｃｅａｌｅｄｐａｔｔｅｒｎｓ．Ｔｈｅｐａｐｅｒｅｌｕｃｉｄａｔｅｔｈｅｂａｓｉｃｐｒｉｎｃｉｐｌｅｏｆｔｈｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓａｎｄｓｕｍｕｐｔｈｅｃｏｎｔｅｍｐｏｒａｒｙｒｅｓｅａｒｃｈｏｆｔｈｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓ．Ｉｔａｌｓｏａｎａｌｙｚｅａｆｅｗｒｅｐｒｅｓｅｎｔａｔｉｖｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓａｎｄｃｏｍｐａｒｅｔｈｅｉｒｄｉｆｆｅｒｅｎｃｅｓ，ａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓ．Ａｔｌａｓｔ，ｔｈｅｐａｐｅｒｉｎｄｉｃａｔｅｔｈｅｄｅｖｅｌｏｐｍｅｎｔｔｒｅｎｄｏｆｃｌｕｓｔｅｒｉｎｇｉｎｔｅｇｒａｔｉｎｇｔｈｅａｐｐｌｉｃａｔｉｏｎｄｅｍａｎｄ．Ｋｅｙｗｏｒｄ：Ｄａｔａｍｉｎｉｎｇ；ＣｌｕｓｔｅｒｉｎｇＡｎａｌｙｓｉｓ；ＣｌｕｓｔｅｒｉｎｇＡｌｇｏｒｉｔｈｍｓ１５００