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

《基于划分聚类法的文献综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、很难找到一个统一的标准对其进行归类。聚类分析的方法可分为基于层次的聚类方法、基于划分的聚类方法、基于图论的聚类方法、基于密度和网格的方法等.这些方法虽然从不同角度使用不同的理论方法研究聚类分析，但对于不同的实际问题，聚类分析中的一些基本内容始终是人们关注的焦点。其中，划分法通常是指给定数据库，其中有N个元素，采用分裂法将其构造为K个组，每一个分组就代表一个聚类，K

3、给出一个初始的分组方法，以通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好。我们通常使用的K-MEANS算法、K-MODES算法、CLARANS算法基本上都采用这中思想。本文在对聚类分析方法进行简要冋顾，对聚类分析研究的应用以及聚类分析的方法进行概述和总结，这对于进一步研究聚类分析具冇重要意义。2算法k-modes算法是在数据挖掘屮对分类属性型数据的采用的聚类算法ok-modes算法是对k-means算法的扩展。k-means算法是在数据挖掘领域中普遍应用的聚类算法，它只能处理

4、数值型数据，而不能处理分类属性型数据。例如表示人的属性有：姓名、性别、年龄、家庭住址等属性。而k-modes算法就能够处理分类属性型数据。k-modes算法釆用并界度來代替k-means算法中的距离。k-modes算法中菲异度越小，则表示距离越小。一个样本和一个聚类中心的差异度就是它们各个属性不相同的个数，不相同则记为一，最后计算一的总和。这个和就是某个样本到某个聚类中心的并异度。该样木属于并异度最小的聚类中心。k-means算法接受输入量k；然后将n个数据对彖划分为k个聚类以便使得所获得的聚类满

5、足：同一聚类屮的对象相似度较高；而不同聚类屮的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个”中心对象”（引力中心）来进行计算的。k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的和似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类;然后再计算每个所获新聚类的聚类屮心（该聚类屮所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。k个聚类

6、具有以下特点:各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。2.1经典K中心聚类算法设U={xx,x2,……xj是n个对象构成的集合。对象Xi=（xil,xi2,,Xim}是由m个属性或特征A={a1,a2/am}描述。K中心聚类算法。通过最小化一个带约朿条件的非凸函数F来获得一个由k个类构成的对U的划分。该优化问题可以被描述如下：F（W,Z）=S^iSUcoiid（xi,z1）（2-1-1）需满足(2-1-2)coH6{0,1}/l

7、1<1

8、）表示对象Xi和类屮心Z]在属性可上的差异值.如果丐是数值型属性，那么®j(Xi，Z])=Ikij-Z]j『(2-1-3)如果3j是分类型屈性，那么6aj

9、(x”Z

10、)｛；；；[：：(2-1-4)如果所有属性都是数值型的，此吋，d变成了欧式距离测度，K中心聚类算法被叫做K-Means,如果所有属性都是分类型的，此吋，d变成了简单匹配相异测度，K屮心聚类算法被叫做K-Modeso最小化带着约束条件（2-1-2）的廿标函数F问题是一种带约束的非凸优化问题，它的解是未知的。常用的方法是通过迭代方法获得其局部最优。在这个方法屮，首先固定变量Z去最小化口标函数F从而获得肌进一步，固定变量W,通过最小化廿标函数F从而获得Z.通过不断重复上述过程，