基于欧氏距离的K均方聚类算法研究与应用

摘要：将所学的高等工程应用数学知识与本专业内容有效的结合起来，系统全面的介绍了距离度量与相异度计算、聚类的概念及聚类步骤，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 年，MacQuจeen 首次提出了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>n>>k>>mrows>>ncols；//其中n为样本数，k为分类数，mrows为行像素，ncols为列像素

for （i=1；i