基于划分聚类法的文献综述聚类分析是一种重要的无监替学习方法，作为数据分析的工具，其重要性在各个领域都得到了广泛的认可.聚类分析的目的是寻找数据集中的“口然分组”，即所谓的“簇”.通俗地讲，簇是指相似元素的集合，聚类分析就是一个在数据集中寻找相似元素集合的无监督学习过程.來〔1不同应用领域的数据集具有不同的特点，人们对数据进行聚类分析的目的也不尽相同，聚类分析的方法因数据集而异，因使用目的而异.当前，聚类分析的新方法层岀不穷，纵观各种聚类算法，它们使用的技术互不相同，其理论背景乂彼此交义、重蒂，很难找到一个统一的标准对其进行归类。
聚类分析的方法可分为基于层次的聚类方法、基于划分的聚类方法、基于图论的聚类方法、基于密度和网格的方法等.这些方法虽然从不同角度使用不同的理论方法研究聚类分析，但对于不同的实际问题，聚类分析中的一些基本内容始终是人们关注的焦点。
其中，划分法通常是指给定数据库，其中有N个元素，采用分裂法将其构造为K个组，每一个分组就代表一个聚类，K<No而且这K个分组满足下列条件:(1)每一个分组至少包含一个数据纪录；(2)每一个数据纪录属于且仅屈于一个分组;对于给定的K,算法首先给出一个初始的分组方法，以通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好。
我们通常使用的K-MEANS算法、K-MODES算法、CLARANS算法基本上都采用这中思想。
本文在对聚类分析方法进行简要回顾，对聚类分析研究的应用以及聚类分析的方法进行概述和总结，这对于进一步研究聚类分析具有重要意义。
2算法k-modes »法是在数据挖掘中对分类属性型数据的采用的聚类算法O k-modes 算法是对k-means算法的扩展。
k-means算法是在数据挖掘领域中普遍应用的聚类算法，它只能处理数值型数据，而不能处理分类属性型数据。
例如表示人的属性有：姓需、性别、年龄、家庭住址等属性。
而k-modes算法就能够处理分类属性型数据。
k-modes算法采用差异度來代替k-means算法中的距离。
k-modes算法中差异度越小，则表示距离越小。
一个样本和一个聚类中心的差异度就是它们各个属性不相同的个数，不相同则记为一，最后计算一的总和。
这个和就是某个样本到某个聚类中心的差异度。
该样本属于差异度最小的聚类中心。
k-means算法接受输入量k ；然后将1】个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。
聚类相似度是利用齐聚类中对象的均值所获得一个”中心对象”(引力中心)来进行计算的。
k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度(距离)，分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值)；不断重复这一过程直到标准测度函数开始收敛为止。
一般都采用均方差作为标准测度函数。
k个聚类具有以下特点:各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
2.1经典K中心聚类算法设11= {x x,x2, X』是1】个对象构成的集合。
对象Xi = {x il,x i2, ,Xim}是由m个属性或特征A={a x,a2，……川小}描述。
K中心聚类算法。
通过最小化一个带约束条件的非凸函数F来获得一个由k个类构成的对U的划分。
该优化问题可以被描述如下：F(W,Z)=》崔1 球gi d(xi,zi) (2-1-1) 需满足Ou E {0,1},lSlSRlSiSn(= 1,1 < i n, (2-1-2)0 < Sl^l COH < 71,1 M 1M k其中• w =[OB]是一个kxn{o,l}矩阵，Ji是一个二元变量，表示对象Xi与第1 类的隶属关系。
如果Xi属于第1类，WH=1,否则等于0;• Z= {z lf z2,……Zk}和Zj = {z n,Zi2,……,Z]m}是第L类的中心，它由m个分彊构成；• d(x i,z1) = Sj=i^(x b z1),是用于度量对象Xi，和类中心可之间的相异测度, g(Xi，Z|)表示对象Xi利类中心Z]在属性丐上的差异值.如果丐是数值型属性，那么2g (Xi ，Zi )= |隔 一 Zijll(2-1-3)如果丐是分类型属性，那么 如果所有属性都是数值型的，此时，d 变成了欧式距离测度，K 中心聚类算 法被叫做K-Meaiis,如果所有属性都是分类型的，此时，d 变成了简单匹配相异 测度，K 中心聚类算法被叫做K-Modeso最小化带着约束条件(2-1-2)的目标函数F 问题是一种带约束的非凸优化问 题，它的解是未知的。
常用的方法是通过迭代方法获得其局部最优。
在这个方法 中，首先固定变量Z 去最小化目标函数F 从而获得肌 进一步，固定变最W,通 过最小化目标函数F 从而获得乙通过不断重复上述过程，从而获得一个局部最 优结果。
这也就意味着，上述优化问题能被解决通过迭代解决下面两个最小化的 子问题：・问题Pp 固定z = z,最小化F (W ,2)；•问题P2：固定w = W,最小化F (W,Z )； 问题Pl 能被解决通过如下公式：对于1 < i < n, 1 < 1 < k问题P2能被解决通过如下公式:如果丐是数值型的，那么刀 _£壯丄帝11呦如果丐是分类型的，那么 (2-1-7)其中(2-1-8) 对于 1 < 1 < k, 1 < j < m, V a . = {aJD,a$),……，彳"}是可的值域,nj 表示可的属性值个数.K 中心聚类算法(KM)能被形式化描述如下：Stepl.初始化Z ⑴ 6 R 11*.获得W (D 最小化F (W,Z (】)).Sett=l.Step 2.获得Z (t+D 最小化F(W^),Z (t+】)).如果F (W (t),Z (t+1)) = F (W (气Z (。
),那 么算法结束;否则，转到Step 3.Step 3.获得 W (z )最小化 F (W (t+D,Z (t+D)如果：F (w (t+D,Z (t+D))= F (W (t ), Z (t+1))=1,如果 =.0,否则(2-1-5) (2-1-6)1 < t < II,xij =甲,Ji = 1J|，那么算法结束；否则，设t=t+l且转到Step 2o该算法的时间复杂度是O(nknit)它在决定对象对类的归属时，对待所有属性是等权的。
当数据中包含着大星的稀疏或冗余属性时，这样做是不可行的。
一个类往往存在于一个子空间中而非整个特征空间中，其余特征的岀现常常会掩盖类的发现。
2.2快速全局K-Means聚类算法全局K-Meaiis聚类算法是由Likas等人提出的。
该算法并不像其他全局搜索算法开始于随机初始点。
它是采用增量方式在每一次迭代过程中试图发现一个最优的数据点做为下一个类的开始点，并利用K-Means聚类算法进行局部搜索.接下来，将给出算法的详细介绍。
当给定2时，根据公式(2-2-5),可计算得一个W最小化函数F(W,Z)0因此K-Means 聚类算法的目标函数F能被重新表达成为：F(Z) = min w F(W, Z)=niin ZieZ||Xj 一z】||2(2-2-1) 全局K-Means聚类算法(GKM)的聚类过程为：Step 1•计算z, = 其中n二表示数据集X所包含的对象数.设置Z； = {zi}和h = 1.Step2.设置h = h +1,若h>k,算法结束.Step 3.对F每一个对象XjGX,假设其作为第h类的初始点，应用K-Means 聚类算法以U {xj为初始点集聚类数据集X,并通过迭代获得一个局部最优结果(W,Zh(i)),其中Zh(i) = {zi(i),Z2(i) .......................................................... 冷①}.Step 4.若Zh(T)能够满足F(Z h(r)) = niin F(Z h (i))I— 1 ・・・H我们设置Z］； = Z h(r)且转至Step 2.然而，该算法是非常耗时的，因为其时间复杂度为O(n2nik2t).因此，若干个改进算法被提出去减少其计算成本.Likas等人提出了一个快速的全局K-Means 聚类算法(FGKM):Step 1.计算勾=211沧/口，其中二表示数据集x所包含的对象数.设置ZJ = (zj和h=l.Step 2.设置h = h + 1若h>k，算法结束.Step3.对于每一个对象Xj.X,计算比=乂max(0,叫一闻一旳『) 其中dj = m% e Zh-JIzj -XjV Step 4.若设置Xq满足设置Z = Zh_i U {xq}.Step 5.应用K-Means聚类算法以Z为初始点集聚类数据集X,并通过迭代获得一个同部最优结果(W,Z；),并保存乙:和计算血为每一个对象Xj €X.算法转至Step 2.相比全丿』K-Means聚类算法，快速全局K-Means聚类算法不盂要在Step 3 中为每一个对象执行一次K-Means聚类.它仅仅需要计算F的一个上界，即F(V h(i))<F(Vi)-li这样做使得计算复杂度变成了0(n2mk+ nmk2t)o无数的实验结果也展示了快速全局K-Meaiis聚类算法能够获得F的一个全局或近似全局最优解。
.3应用3.1聚类分析在市场营销客户细分中的应用市场营销业利用数据挖掘技术进行市场定位和消费分析，辅助制定营销方案。
通过对客户数据库不同消费者消费同一类商品或服务的众多不同数据进行聚类分析，争取潜在的客户，制定有利于市场运行的策略。
目前企业都己经意识到“客户就是上帝”，在这种经营理念的指引下，对现有客户和潜在客户的培养和挖掘正成为企业的关键。
例如，客户的需求倾向一般有内因和外因共同局决定的，内因一般包括对某种产品的需要，认知，而影响外因的元素相对较多，比如文化，社会，小群体，参考群体等等。
把这些因素作为分析变最，把所有潜在客户的每一个分析变量的指标值量化出来，用聚类分析法进行分类。
除此之外，客户满意度和重复购买的机率都可以作为属性进行分类。
根据这些分析得到的归类，可以为企业制定市场运营决策提供参考和保障。
3.2聚类分析在金融领域中的应用随着世界经济的快速发展，金融业面临的考验与口俱增。
在分析市场和预测发展、各类客户的归类、银行及各类担保公司的担保和信用评估等工作上需要收集和处理大量的数据，这些数据不可能通过人工或简单•的数据处理软件可以完成的。