吴登磊+汪宇玲+吴小龙+金安安

摘要：将所学的高等工程应用数学知识与本专业内容有效的结合起来，系统全面的介绍了距离度量与相异度计算、聚类的概念及聚类步骤，K-means算法基本思想及其实现过程，最后给出一个树叶自动分类的应用示例，并使用matlab工具实现，研究分析了基于欧氏距离的K-means算法的优势与不足。

关键词：欧氏距离；聚类；K均方算法

中图分类号：TP18 文献标识码：A 文章编号：1007-9416（2017）04-0148-03

数学在科学发展过程中始终起着举足轻重的作用，它深入渗透到各个学科领域的几乎所有分支中。俗话说：“物以类聚，人以群分”，在自然科学和社会科学中，存在的大量分类问题同样可以利用数学工具进行定量分类。随着人类科学技术的发展，对分类的要求越来越高，人们逐渐把数学工具引用到了分类学中形成了数值分类学，之后又将多元分析技术引入到数值分类学形成了聚类分析。聚类分析将大量数据划分为性质相同的子类，更方便了解数据的分布情况，对识别数据的内在结构具有极其重要的作用，广泛应用于模式识别、图像处理、数据压缩、Web智能、生物信息等众多领域。

1 距离度量与相异度计算

1.1 距离与距离空间

设V是一个非空集合，V到实数集R的一个代数运算记为，如果满足：

（1）正定性，并且；（2）对称性=；（3）三角不等式。

其中是V中的任意元素，则称是V中两点为之间的距，并称V按距离成为距离空间或度量空间，记为（V，d）[1]。

显然距离是一种标量，不具有方向而仅含量。在一个n维欧氏空间点集中，它的每个点X可以表示为（x[1]，x[2]，…，x[n]），其中x[i]（i=1，2，…，n）是实数，称为X的第i个坐标，两个点A=（a[1]，a[2]，…，a[n]）和B=（b[1]，b[2]，…，b[n]）之间的距离可用来描述两点的相对位移、远近、相似性等。

常见的几种距离空间中的代数运算有欧氏距离、曼哈顿距离、明氏距离、切比雪夫距离等。欧氏距离是欧几里得n维空间中两点间的真实距离。其距离公式为：意义为两元素在欧氏空间中的集合距离，当n=2时欧氏距离就是两点之间的直线段距离。曼哈顿距离是使用在欧几里得几何度量空间的几何学用语，用以标明两点在标准坐标系上的绝对轴距总和，即

在欧几里得空间的固定直角坐标系上两点所形成的线段对轴投影的距离和。其距离公式为

。

明氏距离又称明可夫斯基距离，是欧氏空间中的一种测度，被看做是欧氏距离和曼哈顿距离的一种推广。其距离公式为：，当p=2时即为欧氏距离，而p=1时则为曼哈顿距离，当p取无穷时的极限情况下，还可以得到切比雪夫距离：

此外距离度量還可以加权，从而尽可能真实地反映不同分量的影响力大小。

1.2 相异度计算

相异度通常用来衡量两个可比较元素的差异度。例如脸与手掌的相异度明显大于手掌与脚掌的相异度，这种感观对于人是很直观的，但计算机却不具备这种直观感受能力，因此我们必须从数学的角度，形式化定量定义相异度。假如训练样本用m个特征属性来描述，则可以把每个训练样本点看作m维空间中的一点，并使用某种距离比如欧氏距离，来表示训练样本点间的相异度，可定义距离较近的点性质比较相似，从而判定两者的相异度较小，定义距离较远的点性质有较大差异，相异度较大。现在考虑元素的所有特征属性都是标量的情况，设，，X和Y是具有m个可度量特征属性的两个不同元素项，则它们的相异度可定义为：，其中R为实数域。比如计算X={1，66，3}和Y={101，2，7}的相异度，可以进一步将定义为欧氏距离，则X和Y的相异度为：=118.8。

上述这种相异度的计算方式存在一个问题：属性的取值范围越大对距离的影响越明显。上例中第一个特征属性的取值跨度就远大于第三个，这对于相异度的真实反映是非常不利的。为此，我们通常采取把每个特征属性值比例映射到相同区间，即对特征属性值规格化，从而使各个属性能平衡地影响距离。一般映射到的取值区间是[0，1]，映射公式为：

式中是所有元素项中第i个特征属性最大值，相应的为最小值。对上例，中每个元，素规，格化并映射到区间[0，1]，则X={0，1，0}，Y={1，0，1}，重新计算欧氏距离约为1.732。，

2 聚类问题

2.1 类

由于自然界事务特性纷繁复杂，用来表示样本点性质的变量也种类繁多，在对数据聚类特征属性提取的过程中有多种不同选择，使得样本点的表达形式各不相同，在不同问题域中相同称谓的类的定义也有不同，所以在对数据对象聚类前，应先给出类的定义[2]。几种类的定义形式如下：

设U是集合，Si是U中的样本元素，样本个数为k，T和V为预设的阀值，则有：

（1）如果，都有，则U称为一类；（2）如果，都有，则U称为一类；（3）如果，都有，且D（Si，Sj）≤T，则U称为一类；（4）如果，都，满足D（Si，Sj）≤T，则称U为一类。

上述几中不同的类的定义，定义1的要求是最高的，定义2次之。只要符合定义1的类，必定符合其他定义；只要符合定义2的类，同样符合定义3。无论何种定义，均是使用元素间的距离来定义，不同的是距离的限制程度。

2.2 聚类

2.2.1 聚类定义

一个问题域的数据量往往是宠大的，要对这些数据进行分类处理存在很大的难度，有时候用户也不明确要做何种分类，在这种情况下，采用监督学习方法进行分类，往往会因为已知信息不足、预处理代价大等问题使得分类效果并不令人满意。聚类方法是一种无监督或半监督的学习方法，处理此类问题有较明显的优势。

聚类是将待处理问题域的数据对象集合划分成由相似对象构成的多种不同类的过程。通常先给定一组元素的集合U，集合中每个元素有N个可观察性能，运用特定算法划分U为K个子集（类簇），每个子集内元素的相异度尽量小，不同子集间元素的相异尽量大。这是一个观察式的无监督学习过程，与分类不同，聚类前不需要明确分类数量或类别，没有可提供的先验知识。聚类形式定义如下：

令U={p1，p2，…，pn}表示一个模式（实体）集合，pi 表示第i个模式i={1，2，…，n}；Ct U，t=1，2，…，k，；有，式中下标ms表示模式所属的类，下标ir表示类中某一模式，proximity函数是距离函数，用来描述模式的相似性。假如类Ct集为聚类结果，则Ct应满足的条件如下：

（1）；（2）对于Cm，CrU，Cm≠Cr，有（仅限于刚性聚类），且

2.2.2 聚类步骤

聚类的主要步骤[3]包括样本数据准备、特征子集选择、特征提取、相异度计算、集群或分组、结果有效性评估等步骤。数据准备通常包括标准化特征属性和对样本数据的降维，从而构造出一个初始特征数据集。特征子集选择则是将初始特征数据中不相关或冗余的特征去除，选择最有效的特征存放在特征向量中，从而提高模型精确度和减少运行时间。特征提取：通过某种变换将测量空间的特征转换成新的能突出其本质功能、优势的特征，其结果通常称为特征向量。

集群或分组是基于某种距离的特征属性相异度度量的结果，距离相近的聚类，实现分组。聚类结果要求类簇内是高内聚，类簇间是低耦合。结果有效性评估依据该要求主要有内部和外部有效性评估，相关性测试评估三种评估方式。聚类结果优劣的评判标准通常包括处理不同类型数据能力，大数据处理能力，脏数据处理能力，不同排列的数据处理能力，可解释性等。

3 K均值（K-means）算法

1967 年，MacQueen 首次提出了K均值聚类算法（K-means 算法），是聚类的经典算法之一。K-means算法是非常典型的基于距离计算的聚类算法，它把距离作为相似性/相异性的度量，认为对象的相异性/相似性与距离的远/近成正比。该算法的基本思想：首先随机或有规则地选择k个对象，分别作为k个簇的中心或初始均值，对于剩下的每个对象，计算其与各个簇中心的距离，并将它分配到最近的簇中，分配完后重新计算每个簇新的中心或均值。通过迭代运算，直到最小平方误差准则收敛出最后的聚类结果。

k均值算法的计算过程非常直观[4]，具体实现伪代码如下，假定对n 个样本进行聚类：

（1）Input k，n，m；//m为可能的孤立元素个数；（2）计算样本间距离d（i，j）；Delete m个max（d（i，j））对象；（3）Center=Φ；若Max=d（i，j），则Center={i，j}；（4）for（t=2；t

4 实验结果与分析

现有n片不同种类的树叶，已知的树叶种类为k种，下面采用基于K-means算法的方法来完成对它们的自动分类。此问题K-means算法的处理过程如下：按照某种规则选择k片树叶（此例采用随机选择方式），则k片树叶代表了对应的k个簇中心。对剩余的树叶，计算其与各个簇中心的距离，并将其分配到最近的簇，分配完后重新计算各个簇新的中心。不断重复这个过程，直到树叶的划分不再发生变化。

整个分类算法的伪代码：

cin>>n>>k>>mrows>>ncols；//其中n为样本数，k为分类数，mrows为行像素，ncols为列像素

for （i=1；i

读取图片i；

改变图片i的像素数为mrows*ncols；

将真彩图像转换为灰度图；

将像素矩阵转换为行向量leafs（i）； }

调用K-means算法对leafs矩阵进行自动聚类；

返回聚类结果。

现给定实验样本（n=12，k=5）：

分类结果，共5类：

由实验结果可见，分类效果令人满意。事实证明欧氏距离算法的实践效果是最优的，基于欧氏距离的K-means聚类算法速度很快，性能良好，在各种聚类算法中应用最为广泛。虽然K-means简单、高效，但它也有不足之处：

（1）可看到该算法只针对数字类型特征属性，对于其他类型则转换成合适的数值度量的方式。（2）k值（即类的数量）是事先人为选定的，然而在对数据不甚了解的情况下，事先很难估计给定的数据集应该分成多少个类别才最合适，即很难给出合理的k值，而确定不恰当的k值将使得分类效果较差；有一种结合全协方差矩阵的K-means算法，把只包含少量训练数据的类逐步删除，这是一种典型的分割聚类方法[5]，聚类结果可以用层次聚类方法做验证，层次聚类方法具有自底向上、逐步聚类的优点，两者相结合可取得更满意的聚类结果。（3）初始中心点需要使用随机种子点来获取，然而这个随机种子点非常重要，不同的随机种子点有时会得到完全不同的结果，倘若选择到了较孤立的点，会对聚类的效果产生非常大的影响，即K-means算法对于孤立点数据或噪声数据是敏感的，少量的该类数据能够对平均值产生较大的影响。因此常常需要使用其他的算法来配合进行初始化，比如Canopy算法，以确定簇数以及初始簇心。（4）同样是因为随机种子点，可能会使K-means算法产生收敛到局部最优解而难以发现全局最优解[6]。传统K-means算法常常会在获，得一个局部最，优值后终止，所以只适合对类簇为凸形的数值型数据集聚类。这种问题可以采用具有全局寻优能力的模拟退火算法与K-means算法结合来解决，也可以采用遗传算法进行初始化，以内部聚类准则为评价指标，在遗传算子作用下，最终接近全局最优解。 ，

5 结语

本文给出了距离度量与相异度计算、聚类的概念及聚类过程，K-means算法基本思想及其实现过程，聚类分析过程中用到了距离度量方法，距离矩阵会用到矩阵变换等矩阵知识，K-means算法是较典型的逐点修改迭代的动态硬聚类算法，其要点是以误差平方和为准则函数。实际应用中聚类算法的计算结果是不能完全预知的，不同种类的数据适合不同的聚类算法，需根据实际情况进行选择。要使聚类分析行之有效，需要斟酌考虑以下几个方面。对于一个实际问题要根据分类目的来选取特征属性，特征属性选取的不同，分类结果一般也不同；样品间距离定义方式的不同，聚类结果一般也不同；聚类方法的不同，聚類结果一般也不同（尤其是样品特别多的时候）；最好能通过各种方法找出共性；特征量纲差别太大会导致聚类结果不合理；聚类分析的结果有可能并不令人满意，因为聚类过程实际是一个数学的处理过程，对于结果我们要能给予一个合理的解释。

参考文献

[1]姜健飞.清华大学出版社[M].现代应用数学方法，2009.

[2]Fang Kaimi，Pan Enpei. Clustering analysis[M].Geological publishing house，Beijing.1982.

[3]Sambasivam S， Theodosopoulos N. Advanced data clustering methods of mining Web documents. Issues in Informing Science and Information Technology[J].2006（3）：563-579.

[4]Marques JP，著.吴逸飞，译.模式识别--原理、方法及应用[M].清华大学出版社，2002.

[5]顾洪博.基于k-means算法的k值优化的研究与应用[J].海南大学学报自然科学版，2009（4）：386-389.

[6]孙吉贵，刘杰，赵连宇.聚类算法研究[J].Journal of Software，2008（1）：48-61.