内容发布更新时间 : 2024/11/13 4:03:49星期一 下面是文章的全部内容请认真阅读。

k-means聚类算法的研究

1．k-means算法简介

1.1 k-means算法描述

给定n个对象的数据集D和要生成的簇数目k，划分算法将对象组织划分为k个簇（k<=n），这些簇的形成旨在优化一个目标准则。例如，基于距离的差异性函数，使得根据数据集的属性，在同一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”。划分聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数收敛时，得到最终聚类结果。这类方法分为基于质心的（Centroid-based）划分方法和基于中心的（Medoid-based）划分方法，而基于质心的划分方法是研究最多的算法，其中k-means算法是最具代表和知名的。

k-means算法是1967年由MacQueen首次提出的一种经典算法，经常用于数据挖掘和模式识别中，是一种无监督式的学习算法，其使用目的是对几何进行等价类的划分，即对一组具有相同数据结构的记录按某种分类准则进行分类，以获取若干个同类记录集。k-means聚类是近年来数据挖掘学科的一个研究热点和重点，这主要是因为它广泛应用于地球科学、信息技术、决策科学、医学、行为学和商业智能等领域。迄今为止，很多聚类任务都选择该算法。k-means算法是应用最为广泛的聚类算法。该算法以类中各样本的加权均值（成为质心）代表该类，只用于数字属性数据的聚类，算法有很清晰的几何和统计意义，但抗干扰性较差。通常以各种样本与其质心欧几里德距离总和作为目标函数，也可将目标函数修改为各类中任意两点间欧几里德距离总和，这样既考虑了类的分散度也考虑了类的紧致度。k-means算法是聚类分析中基于原型的划分聚类的应用算法。如果将目标函数看成分布归一化混合模型的似然率对数，k-means算法就可以看成概率模型算法的推广。

k-means算法基本思想：

（1） 随机的选K个点作为聚类中心； （2） 划分剩余的点；

（3） 迭代过程需要一个收敛准则，此次采用平均误差准则。 （4） 求质心（作为中心）；

（5） 不断求质心，直到不再发生变化时，就得到最终的聚类结果。

k-means聚类算法是一种广泛应用的聚类算法，计算速度快，资源消耗少，但是k-means算法与初始选择有关系，初始聚类中心选择的随机性决定了算法的有效性和聚

类的精度，初始选择不一样，结果也不一样。其缺陷是会陷于局部最优。 1.2 k-means算法实现步骤

k-means聚类算法的处理流程如下：首先，随机选择k个对象，每个对象代表一个簇的初始均值或中心；对剩余的每个对象，根据其与各簇中心的距离，将它指派到最近（或最相似）的簇，然后计算每个簇的新均值，得到更新后的簇中心；不断重复，直到准则函数收敛。通常，采用平方误差准则，即对于每个簇中的每个对象，求对象到其中心距离的平方和，这个准则试图生成的k个结果簇尽可能地紧凑和独立。 1.2.1 k-means聚类算法的形式化描述 算法：k-means

输入：聚类个数k，以及包含n个数据对象的数据库D 输出：满足方差最小标准的k个聚类 处理流程：

Step1 从n个数据对象任意选择k个对象作为初始聚类中心； Step2 根据簇中对象的平均值，将每个对象重新赋给最类似的簇； Step3 更新簇的平均值，即计算每个簇中对象的平均值； Step4 循环Step2到Step3直到每个聚类不再发生变化为止。 1.2.2 k-means聚类算法的具体步骤 1) Function k-means（）

2) 输入：包含n个对象的数据集及簇的数目 3) 输出：k个簇的集合

4) 初始化k个簇中心{w1，w2，…，wk}，其中wj= il，j ∈{1,2，…，k}，l ∈{1,2，…，

n}

5) 使每一个聚类Cj与簇中心wj中相对应 6) repeat

7) for每一个输入向量il，其中l ∈{1,2，…，n } do 8) 将il分配给最近的簇中心wj*所属的聚类Cj*

（即|il—wj*|≦|il—wj|），j ∈（1,2，…，k））

9) for 每一个聚类Cj，其中j ∈{1,2，…，k}

10) 将簇中心更新为当前的Cj中所有样本的中心点，即wj11) 计算准则函数E

??il?cjil|Cj|

12) Until E不再明显地改变或者聚类的成员不再变化 1.2.3 相关定义

（1）两个数据对象间的距离： ①明氏距离（Minkowski Distance）

d(xi,xj)?(?|xik-xjk|q)1/q （公式1）

k?1p这里的xi=( xi1，xi2，…，xip)和xj=( xj1，xj2，…，xjp)是两个p维的数据对象并且 i≠j。 ②欧式距离（Euclidean Distance）

当明氏距离中q=2时，公式1即欧式距离。

d(xi,xj)?(?|xik-xjk|2)1/2 （公式2）

k?1p③马氏距离（Mahalanobis Distance）

??(?ij)p?p （公式3）

1n(xki-xi)(xkj-xj)，i，j=1，2…，p。如果∑-1存在，则马氏距离为 其中?ij??n-1k?1

2dM(xi,xj)?(xi,xj)T??1(xi,xj) （公式4）

④兰式距离（Canberra Distance）：

1p|xik-xjk|dL(xi,xj)?? （公式5）

pk?1xik?xjk（2）准则函数E

对于K-means算法，通常使用准则函数E，也就是误差平方和（Sum of Squared Error，SSE）作为度量聚类质量的目标函数。

E???d2(Ci,x) （公式6）

i?1x?Cik其中，d( )表示两个对象之间的距离，可以利用明氏、欧式、马氏或兰氏距离求得。 对于相同的k值，更小的SSE说明簇中对象越集中。对于不同的k值，越大的k值应该越小的SSE。

2．k-means算法应用实例

k-means聚类广泛应用于地球科学、信息技术、决策科学、医学、行为学和商业智