基于划分聚类法的文献综述

1 引言

聚类分析是一种重要的无监督学习方法, 作为数据分析的工具, 其重要性在各个领域都得到了广泛的认可. 聚类分析的目的是寻找数据集中的“自然分组”,即所谓的“簇”. 通俗地讲, 簇是指相似元素的集合, 聚类分析就是一个在数据集中寻找相似元素集合的无监督学习过程. 来自不同应用领域的数据集具有不同的特点, 人们对数据进行聚类分析的目的也不尽相同, 聚类分析的方法因数据集而异, 因使用目的而异.当前, 聚类分析的新方法层出不穷, 纵观各种聚类算法, 它们使用的技术互不相同, 其理论背景又彼此交叉、重叠, 很难找到一个统一的标准对其进行归类。

聚类分析的方法可分为基于层次的聚类方法、基于划分的聚类方法、基于图论的聚类方法、基于密度和网格的方法等. 这些方法虽然从不同角度使用不同的理论方法研究聚类分析，但对于不同的实际问题，聚类分析中的一些基本内容始终是人们关注的焦点。其中，划分法通常是指给定数据库，其中有N个元素，采用法将其构造为K个组，每一个分组就代表一个聚类，K本文在对聚类分析方法进行简要回顾，对聚类分析研究的应用以及聚类分析的方法进行概述和总结，这对于进一步研究聚类分析具有重要意义。

2 算法

k-modes算法是在数据挖掘中对分类属性型数据的采用的聚类算法。k-modes算法是对k-means算法的扩展。k-means算法是在数据挖掘领域中普遍应用的聚类算法，它只能处理数值型数据，而不能处理分类属性型数据。例如表示人的属性有：姓名、性别、年龄、家庭住址等属性。而k-modes算法就能够处理分类属性型数据。

k-modes算法采用差异度来代替k-means算法中的距离。k-modes算法中差异度越小，则表示距离越小。一个样本和一个聚类中心的差异度就是它们各个属性不相同的个数，不相同则记为一，最后计算一的总和。这个和就是某个样本到某个聚类中心的差异度。该样本属于差异度最小的聚类中心。

k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个"中心对象"(引力中心)来进行计算的。

k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度(距离)，分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值)；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。 k个聚类具有以下特点:各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

2.1 经典K中心聚类算法       

设U是n个对象构成的集合。对象是由m个属性或特征A=描述。K中心聚类算法。通过最小化一个带约束条件的非凸函数F来获得一个由k个类构成的对U的划分。该优化问题可以被描述如下：    

                                (2-1-1)

需满足

                                  (2-1-2)

其中    

●W =[]是一个k {0,1}矩阵，是一个二元变量，表示对象与第l类的隶属关系。如果属于第l类， =1，否则等于0；

●Z和是第L类的中心，它由m个分量构成;    

●是用于度量对象和类中心之间的相异测度，

表示对象和类中心在属性上的差异值.如果是数值型属性，那么

                                        (2-1-3)如果是分类型属性，那么

                                         (2-1-4)

如果所有属性都是数值型的，此时，d变成了欧式距离测度，K中心聚类算法被叫做K-Means，如果所有属性都是分类型的，此时，d变成了简单匹配相异测度，K中心聚类算法被叫做K-Modes。

    最小化带着约束条件(2-1-2)的目标函数F问题是一种带约束的非凸优化问题，它的解是未知的。常用的方法是通过迭代方法获得其局部最优。在这个方法中，首先固定变量Z去最小化目标函数F从而获得W。进一步，固定变量W，通过最小化目标函数F从而获得Z.通过不断重复上述过程，从而获得一个局部最优结果。这也就意味着，上述优化问题能被解决通过迭代解决下面两个最小化的子问题:

·问题：固定,最小化；

·问题：固定,最小化；

问题能被解决通过如下公式:

                  (2-1-5)

对于, .

问题能被解决通过如下公式:如果是数值型的，那么

                                            (2-1-6)  如果是分类型的，那么

                                             (2-1-7)

其中

   ，                                  (2-1-8) 

对于是的值域, 表示的属性值个数.

K中心聚类算法(KM)能被形式化描述如下：

Step 1.初始化.获得最小化.Set t=1.

Step 2.获得最小化.如果,那么算法结束；否则，转到Step 3. 

Step 3.获得最小化如果：

)= 

那么算法结束；否则，设t=t+1且转到Step 2。

该算法的时间复杂度是它在决定对象对类的归属时，对待所有属性是等权的。当数据中包含着大量的稀疏或冗余属性时，这样做是不可行的。一个类往往存在于一个子空间中而非整个特征空间中，其余特征的出现常常会掩盖类的发现。

2.2快速全局K-Means聚类算法

全局K-Means聚类算法是由Likas等人提出的。该算法并不像其他全局搜索算法开始于随机初始点。它是采用增量方式在每一次迭代过程中试图发现一个最优的数据点做为下一个类的开始点，并利用K-Means聚类算法进行局部搜索.接下来，将给出算法的详细介绍。

当给定时，根据公式(2-2-5)，可计算得一个W最小化函数F(W, )。因此，K-Means聚类算法的目标函数F能被重新表达成为：

                      (2-2-1)

全局K-Means聚类算法(GKM)的聚类过程为： 

Step 1.计算,其中n二表示数据集X所包含的对象数.设置和.

Step 2.设置,若，算法结束.

Step 3.对于每一个对象，假设其作为第h类的初始点，应用K-Means

聚类算法以为初始点集聚类数据集X，并通过迭代获得一个局部最优结果，其中.

Step 4.若能够满足

我们设置且转至Step 2.

然而，该算法是非常耗时的，因为其时间复杂度为.因此，若干个改进算法被提出去减少其计算成本.Likas等人提出了一个快速的全局K-Means聚类算法(FGKM):

    Step 1.计算，其中二表示数据集X所包含的对象数.设置和h=1.

Step 2.设置若，算法结束.

Step 3.对于每一个对象，计算

其中

Step 4.若设置满足 

设置.

Step 5.应用K-Means聚类算法以Z为初始点集聚类数据集X，并通过迭代获

得一个局部最优结果，并保存和计算为每一个对象.算法转至Step 2.

相比全局K-Means聚类算法，快速全局K-Means聚类算法不需要在Step 3中为每一个对象执行一次K-Means聚类.它仅仅需要计算𝔽的一个上界，即           

这样做使得计算复杂度变成了。无数的实验结果也展示了快速全局K-Means聚类算法能够获得F的一个全局或近似全局最优解。.

3 应用

3.1聚类分析在市场营销客户细分中的应用

市场营销业利用数据挖掘技术进行市场定位和消费分析，辅助制定营销方案。通过对客户数据库不同消费者消费同一类商品或服务的众多不同数据进行聚类分析，争取潜在的客户，制定有利于市场运行的策略。目前企业都己经意识到“客户就是上帝”，在这种经营理念的指引下，对现有客户和潜在客户的培养和挖掘正成为企业的关键。

例如，客户的需求倾向一般有内因和外因共同局决定的，内因一般包括对某种产品的需要，认知，而影响外因的元素相对较多，比如文化，社会，小群体，参考群体等等。把这些因素作为分析变量，把所有潜在客户的每一个分析变量的指标值量化出来，用聚类分析法进行分类。除此之外，客户满意度和重复购买的机率都可以作为属性进行分类。根据这些分析得到的归类，可以为企业制定市场运营决策提供参考和保障。

3.2聚类分析在金融领域中的应用

随着世界经济的快速发展，金融业面临的考验与日俱增。在分析市场和预测发展、各类客户的归类、银行及各类担保公司的担保和信用评估等工作上需要收集和处理大量的数据，这些数据不可能通过人工或简单的数据处理软件可以完成的。可以采用模糊聚类分析法对客户进行分类，预防产生不良账户，防范金融诈骗。潜在良好信用客户的挖掘，设计和制定更符合客户要求的金融产品，分析、观测金融市场的发展趋势起到重要的作用。

3.3聚类分析在检验医学方面的应用

检验医学包括很多项目，随着技术的不断提高，其中的生化检验项目自动化分析迅速普及，常规的检查项目不断地在增多，新项目的归类和合理的配置已经成为一项新的课题。聚类分析试分析项目组合用之有效的工具，避免医疗资源的浪费，合理配置了检验项目。在医药研究中，中药的指纹图谱要求考察的是同一品种药材的相似性，而不是某一药材个体的特性，强调的是能够准确识别出某一品种，不是要考察辨认药材之间是否相同。这些要求恰好符合了模糊聚类分析的特征，因此，采用模糊聚类的方法了解中药指纹图谱的相关信息，有助于指纹图谱的建立并实现指纹图谱的自动化识。

3.4聚类分析在图像处理中的应用

计算机是现代生活和工作的重要工具。图像处理是计算机视觉功能的重要组成部分。人眼视觉具有主观性，所以处理图像比较适合采用模糊手段，另一方面也解决了样本图像的匾乏与无监督分析的要求，它己成为图像处理中一个重要的研究分析工具。模糊聚类在图像处理中的一个最广泛的应用是图像分割，它实质上就是研究象素的无监督分类，Coleman和Andrews在1979年，就提出用聚类算法进行图像分割，陆续人们经过实践与学习，提出了多种基于模糊聚类的灰度图像分割新方法，该方法在分割纹理图像、序列图像、遥感图像等方面获得了很大的成果。Stewart等人应用模糊聚类分析对雷达目标的识别和归类进行了研究。

四  总结

聚类分析是数据挖掘领域的研究热点之一，主要用于发现数据之间的分布信

息及内在结构，聚类分析既可以作为一个的分析数据的技术，又可以为其他数据挖掘算法完成数据预处理的步骤。因此，聚类分析是一项在实际应用中十分重要的研究课题。

本课题在介绍了聚类算法的相关内容，概述了两种简单的聚类分析算法及相

关的算法步骤，阐述了K-均值聚类算法的基本思想及算法流程，给出了目前对于聚类分析算法的一些应用领域。

这两类聚类算法在一定程度上还存在一定的缺陷，可以尝试把算法应用到具体的实际问题中，扩展应用领域，来检验算法的可行性。同时意识到各个学科之间的联系及其重要性，每个学科都与生活存在密切的联系，在做项目时，首先需要联系实际生活，切合实际，然后将所学知识运用到生活，在生活中实现其价值。

参考文献

[1] 朱建宇．K均值算法研究及其应用[D]．大连：大连理工大学计算机软件与理论，2013．

[2] 许丽利．聚类分析的算法其应用[D]．长春：吉林大学应用数学，2010．

[3] 唐东明．聚类分析及其应用研究[D]．成都：电子科技大学计算机应用技术，2006．

[4] 高滢．多关系聚类分析方法研究[D]．长春：吉林大学计算机应用技术，2008．

[5] 刘丽．聚类算法研究与应用[D]．无锡：江南大学计算机应用技术，2013．

[6] 陈衡岳．聚类分析及聚类结果评估算法研究[D]．沈阳：东北大学计算机应用技术，2006．

[7] 高茂庭．文本聚类分析若干问题研究[D]．天津：天津大学管理科学与工程，2006．

[8] 王俊，王士同，邓赵红．聚类分析研究中的若干问题[J]．软件学报，2012，27(3)：1–6．

[9] 吴文亮．聚类分析中K-中心点算法的研究[D]．广州：华南理工大学自动化科学与工程学院，2011．

[10] 肖宇．聚类分析及其在图像处理中的应用[D]．北京：北京交通大学计算机科学与技术，2012．

[11] 白亮．聚类学习的理论分析与高校算法研究[D]．山西：山西大学计算机应用技术，2012．

[12] 蒋帅．K-均值聚类算法研究[D]．陕西：陕西师范大学计算机软件与理论，2008．

[13] 丁泽进，于剑．聚类分析技术综述．见：王压，周志华，周傲英主编.机器学习及其应用．[M].北京：清华大学出版社，2006．

[14] 于剑．论模糊C均值算法的模糊指数[J] ．计算机学报，2003, 26 (8) ：968-973．

[15] 肖宇，于剑．基于近邻传播算法的半监督聚类团.软件学报，2008, 19(11): 2803-2813．    

[16] 胡伟．改进的层次K均值聚类算法[J] ．计算机工程与应用，2011, 23 (1) :131-133.

[17] 贺玲，吴玲达，蔡益超．数据挖掘中的聚类算法综述[J] ．计算机应用研究，2007, 24 (1) :  10-13. 

[18] Everitt B, Landau S, Leese M. Cluster Analysis(Fourth Edition)[M]. London: Arnold, 2001.    

[19] Xu R, Donald C Wunsch II. Clustering [M].IEEE Press, 2009.

[20] Likas A Vlassis M, Verbeek J. The global k-means clustering algorithm.Pattern Recog-nition, 2003, 35(2): 451-461.