基于层次的K均值聚类

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于层次的K均值聚类范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：介绍一种基于层次的K均值聚类算法(HKMA)。在统计力学的基础上，对传统K均值聚类划分矩阵里的元素(“隶属”概率)做了形式上的改变，并引入一个调控实际聚类数目的因子。这样，在对同一组数据集进行聚类时，调控因子值不同，结果得到的类数目就不同。用一组二维正态分布的数据集和一组用来测试聚类算法的标准数据集(Iris数)进行测试，结果表明该算法具有层次聚类的性质和较满意的聚类精度。

关键词：聚类；代价函数；层次；K均值聚类

中图分类号：TP391 文献标识码：B 文章编号：1004373X(2008)1616303

KMeans Clustering Based on Hiberarchy

ZHANG Shuaiqin,ZHANG Botao

(Institute of Sciences,Information Engineering University,Zhengzhou,450001,China)

Abstract：A Kmeans clustering arithmetic based on hiberarchy is presented.On basis of statistical mechanics,partition matrix element (membership probability) in traditional Kmeans clustering is changed and a lagrange multiplier controlling the clusters number is introduced.Thus,for a given dataset,the result gives different clusters number when the lagrange multiplier is not the same.The method is tested on one synthetic and one real datasets.The result demonstrates hiberarchy feature and precision of arithmetic as expected.

Keywords：clustering;cost function;hiberarchy;Kmeans clustering

1 引 言

聚类是数据分析中的一项重要技术，是众多科学领域和工程技术中的一项基础性工作。这种技术被广泛应用于生物学、天体物理学、模式识别、数据挖掘、计算机图像处理、最优化问题等。Ь劾嗍前d维特征空间中的n个数据点分成k个不同的类，使类内数据点的相似度高、不同类间的数据点的相似度低［14］。这里的相似在特征空间中表现为距离近，所以距离可以用来对2个数据点进行相似性测度。

K均值聚类是在各个领域用得最多的聚类算法之一。它的主要特点是：对给定的数据集可能存在的类数目需要作出假设；对用来代表某类的类中心需要在迭代计算前做初始化；迭代计算出的类中心容易陷入某些满足局部最优的值中。可以看出，设定恰当的类数目和初始化合适的类中心是K均值聚类算法中的关键。文献［5］中用基于模糊K均值的分裂算法(FBSA)来确定类数目，文献［6］中用聚类中心初始化算法(CCIA)来确定初始的类中心，它们都不同程度地提高了聚类精度。这里介绍一种基于层次的K均值聚类(HKMA)。在该算法中，对传统K均值聚类中划分矩阵里的元素(“隶属”概率)做了形式上的改变，同时引入一个调控因子。这里希望通过调控因子来决定聚类结果中的类中心和实际类数目。

2 传统K均值聚类

2.1 K均值聚类

K均值聚类的首要目标是迭代计算出类中心［7］。这些类中心是通过最小化下面的代价函数得到的。ИИcost f(P,U)=∑ni=1∑cj=1pijxi-uj.2(1)И 这里n是给定数据集的数据点的总个数；c是潜在的类数目；X={x1，x2,…,xn}是特征数据集；U= {u1,u2,…,uc}是类中心集；P=(pij)n×c是一个划分矩阵(“隶属”概率集)，其中元素pij是数据点xi属于由类中心uj代表的类j的成员的概率，对任意的i=1,2,…,n满足∑cj=1pij=1，对任意的i=1,2,…,n和j=1,2,…,c满足pij≥0。

最小化代价函数cost f(P,U)可以得到划分矩阵和代表各个类的类中心的迭代表达式：ИИ pij=1 xi-uj.2≤xi-uk.2

0else(2)

uj=∑ni=1pijxi/∑ni=1pij(3)И K均值聚类在迭代过程中，c个类中心会不断移动，以使得代价函数cost f达到最小值。其中迭代的每一步，一个数据点都是确定性地属于某一类，这由式(2)可以看出。这只是判定一个点属于某一类的一种方式。事实上，在以距离度量两点相似性的聚类算法中，一个点属于某一类是一个随该点与该类中心距离衰减的函数。基于此，完全可以用模糊划分矩阵来代替一般划分矩阵，使一个点以一定概率属于某一类。这就是模糊K均值聚类。

2.2 模糊K均值聚类

模糊K均值聚类的首要目标也是迭代计算出类中心［7］。这些类中心通过最小化下面的代价函数得到。ИИcost fb(P,U)=∑ni=1∑cj=1p.bijxi-uj.2(4)И 这里概率上的指数b叫模糊度，是一个用来控制不同类别的混合程度的自由参数。

最小化代价函数Costfb(P,U)可以得到模糊划分矩阵和各个类中心的迭代表达式：Иpij=∑ck=1xi-ujxi-uk.2b-1.-1ifxi-uk>0

1ifxi-uj=0

0ifxi-uk=0(5)

uj=∑ni=1p.bijxi/∑Ni=1p.bij(6)И 模糊K均值聚类与K均值聚类相比有2点不同：一是引入了模糊“隶属”关系，使一个样本点以一定概率属于某一类别，这样更接近一个事实，即K均值聚类是一种基于距离的聚类方法；二是引入了隶属度这个自由参数，可以控制不同类别的混合程度，使聚类达到更好的结果。当取b=1,且使P中每一个样本点属于某类别的n个概率值中，最大者置为1，其他置为0时，模糊K均值聚类就过渡到了K均值聚类。K均值聚类是模糊K均值聚类的一种近似，一个特例，这也正是模糊K均值比K均值的聚类精度更高的原因。

3 基于层次的K均值聚类(HKMA)

对一个给定类构型的数据集，该类构型的平均总代价(平均总能量)可表示为：И\=∑ni=1∑cj=1pijEijИ其中: Eij=xi-uj.2(7)

数据集类构型的信息熵可表示为：ИH=-∑ni=1∑cj=1pijlog2 pijИ 这里n是给定数据集的数据点的总个数，c是潜在的类数目；X={x1，x2,…,xn}是特征数据集，U= {u1,u2,…,uc}是类中心集，P=(pij)n×c 是一个模糊划分矩阵(模糊“隶属”概率集)，其中元素pij是数据点xi属于由类中心uj代表的类j的成员概率，对任意的i=1,2,…,n满足∑cj=1pij=1，对任意的i=1,2,…,n和j=1,2,…,c满足pij≥0，E=(Eij)n×c是对应于P的代价(能量)矩阵，Eij是数据点xi以概率pij属于类j的成员时的代价(能量)。

在平均总代价(平均总能量)不变的约束下，为得到信息熵的最大值，对熵函数求导可得吉布斯概率分布：Иpij=exp(-βEij)Zi(8)И其中Zi是数据点xi的配分函数，表达式为：ИИZi=∑ck=1exp(-βEik)(9)И 这里的β是拉格朗日乘子，其值由约束公式(平均总代价不变)来确定。

对一个给定类构型的数据集，可以认为不同的数据点“隶属”于自己的类的概率是独立的。这样总的配分函数可表示为：ИZ=∏ni=1ZiИ 由总配分函数可以得到该方法所需要的代价函数(自由能)：

F=-1βln Z

=-1β∑ni=1ln∑cj=1exp-βxi-uj.2(10)

由式(7)~(8)知模糊划分矩阵：Иpij=exp(-βxi-uj.2)∑ck=1exp(-βxi-uk.2)(11)И 为了使代价函数(自由能)最小，对代价函数求导，得到类中心表达式：Иuj=∑ni=1xipij/∑ni=1pij(12)И 基于层次的K均值聚类算法(HKMA)与传统的K均值聚类算法相比较，有两点不同。一是划分矩阵中元素(“隶属”概率)的形式发生了变化。数据点间的相似性从原来直接由点到类中心的距离倒数1/dij(或者能量倒数1/Eij)来度量，变为现在的以指数形式exp(-β dij)(或者exp(-βEij))来度量。这样，“隶属”概率成为距离的缓变(光滑)函数，使得聚类结果对初始化类中心不再像原来那么敏感，有利于提高聚类精度。二是增加了一项用来调节“隶属”概率模糊度的调控因子β。当β增大时，“隶属”概率模糊度降低。事实上，β=0时，各个“隶属”概率值相同，每个点都等概率地属于每一类；而当β∞时，一个点以概率1属于离自己最近的类中心所代表的那个类，基于层次的K均值聚类退化为传统的K均值聚类。

原则上，改变设定的类数目，就会改变类中心的个数。然而，当β一定时，却存在某个类数目临界值c0，使得c>c0时，结果只能得到c0个不同的类中心，而剩下的c-c0个类中心都重叠在c0个类中心上。这说明β决定着聚类结果中的类中心和实际类数目。在下面的仿真试验中将会看到这一点。

4 试 验

4.1 二维正态分布随机数据集

用正态随机数产生器产生一个数据集。该数据集由4个子数据集组成，子数据集分别是以(1，1.5)，(1，2.5)，(5，2)和(7，2)为中心的正态分布数。每一个子数据集有160个数据样本构成。下图是该数据集在c=6，β分别等于0，0.25，0.95，2.90情况下的聚类结果。其中每一个方框标示一个类中心，代表聚类结果中的一个类。当β=0时，每个数据点都以相同的概率隶属于每一个类，由公式(8)知道所有类中心相互重叠，都处在数据集的质心上，结果只有一个类(见图1(a))。当β=0.25时，“隶属”概率模糊度降低，对距离的依赖加强，原来的一个大类分裂成两个小类(见图1(b))。β继续增加，“隶属”概率模糊度进一步降低，新的小类分裂成更小的类(见图1(c)，图1(d))。这种过程一直进行下去，直到β足够大(如β ∞)时分裂成设定的类数目c。

4.2 Iris数

Iris数据集共有3类，分别代表鸢尾属植物(Iris flowers)的3个不同种类：Iris setosa,Iris versicolor和Iris virginica。每一类有50个样本，总共有150个样本。每一个样本通过萼片长度(sepal length)、萼片宽度(sepal width)、花瓣长度(petal length)和花瓣宽度(petal width)四个属性描述。

用HKMA对Iris数进行聚类，β值不同时结果类数目不同，显示层次聚类的性质。图2中上半图是Iris数的3个种类在第一维和第四维上的投影，在此作为参照图；下半图是在β=0.75的情况下对Iris数聚类所得结果在第一维和第四维上的投影。两图对照可以看出，150个样本中只有15个样本分类错误。

图1 聚类结果图示 图2 Iris数在β=0.75时的聚类结果5 结 语

基于层次的K均值聚类(HKMA)，是在统计力学基础上，借鉴传统K均值聚类算法改进而来的。该算法配分矩阵元素(“隶属”概率)的形式提高了聚类的精度，它所特有的调控因子使其具有层次聚类的特性。结果不再像以前那样由设定的类数目确定类中心，而是由得到的类中心确定实际的类数目。

参 考 文 献

［1］Domany E.Superparamagnetic Clustering of DataThe Definitive Solution of an IllPosed Problem.Physica A,1999,263:158169.

［2］Blatt M,Wiseman S,Domany E.Superparamagnetic Clustering of Data.Physical Review Letters,1996,76:3 2513 255.

［3］Blatt M,Wiseman S,Domany E.Clustering Data through an Analogy to the Potts Model.Advances in Neural Information Processing System,MIT Press,1996.

［4］Blatt M,Wiseman S,Domany E.Data Clustering Using a Model Granular Magnet\.Neural Computation,1997(9):1 8051 842.

［5］Haojun Sun,Shengrui Wang,Qingshan Jiang.FCMbased Model Selection Algorithms for Determining the Number of Clusters.Pattern Recognition,2004,37:2 0272 037.

［6］Shehroz S Khan,Amir Ahmad.Cluster Center Initialization Algorithm for Kmeans Clustering.Pattern Recognition Letters,2004,25:1 2931 302.

［7］\ 迪达.模式分类\.Duda R O,李宏东,等译.2版.北京:机械工业出版社,2003.

作者简介 张帅钦 男，1983年出生，信息工程大学硕士研究生。研究方向为统计识别与聚类分析。

张波涛 教授。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文