聚类准则研究

2024-07-23

聚类准则研究（精选6篇）

聚类准则研究篇1

0 引言

随着通信和计算机等信息技术的发展,许多应用领域如金融市场、网络监控、电信数据管理、传感器网络等产生的数据属于流数据(data stream)类型,。流数据是由Henzinger等人于1998年在论文“Computing on Data Streams”中首次提出[1]。流数据快速、连续无限和动态的特性,加上数据收集时间和分析处理速度的限制,使得传统的数据管理和分析技术无效或需要改进,流数据已经成了一个新的研究领域和热点[2,3]。

国外在流数据挖掘方面有两个比较有影响的研究小组:Stanford大学R.Motwani教授领导的研究小组以及UIUC的由C.Aggarwal和J.Han教授领导的研究小组。前者的研究侧重于流数据管理、流数据的连续查询和流数据的聚类方面,提出了不同于传统DBMS的DSMS概念,他们的研究得到了美国国家自然科学基金的资助;后者的研究侧重于流数据分析方面,对于流数据的在线分析,从聚类、分类、频繁项集挖掘以及可视化等角度做了大量研究工作,他们的研究得到了美国军方和国家自然科基金的资助。目前国内对流数据挖掘的研究还比较少。而流数据聚类研究是数据流挖掘的一个重要方向。

1 流数据和传统数据的比较

1.1 逐层优化的区域合并改进算法介绍

一个流数据是实时、连续、有序、时变、无限的元组序列。与传统的数据集相比,流数据具有以下一些鲜明的特点:

(1)有序性。流数据中的元组按时间有序生成,序号隐含于到来的时刻或直接以时间戳记录。

(2)不可再现性。流数据中的数据一旦流过处理节点就不会再次出现,除非进行特殊的保存。

(3)高速性。流数据数据高速地生成,即产生元组的速率较高。

(4)无限性。流数据数据一直连续不断地产生,往往是无限量的。

(5)高维性。流数据往往包含大量的属性,即描述数据流的维数较高。

(6)动态性。产生流数据的概率分布模型是时变的,且变化的速率无法控制。

2 统一流聚类表示模型[4]

设2条轨迹分别为:

轨迹M{M1,M2,…,Mi…,Mn},

轨迹N{N1,N2,…,Ni…,Nn}

定义1设S为轨迹集合,设M,N为集合中任意2条轨迹,定义操作Transform(M,N),其返回值为变换后轨迹对(M,N)的真实差异。

用Transform(S)表示对集合S的转换操作,返回一个n×n集合为S’,元素为对应轨迹对的最小差异,n为轨迹的数量。

定义2单流可形式化描述为:数据…Xi-1XiXi+1…分别在…Ti-1TiTi+1…时刻到达,Xt为d维数据,记为Xt=(x1,x2,…,xd),(d≥1)。

统一流模型:表示为流集合{Sj}(j=l,2,…,n)和维数为d的公共属性维集,Sj为定义2的单流。其中,n≥l,d≥1。

n=l,d=l:一维数据单流模型;

n=l,d>l:多维数据单流模型;

n>l,d=l:一维数据多流模型;

n>l,d>l:多维数据多流模型。

定义3窗口W为保存最近到达的W个数据点集合,每次更新数据块大小B;Pji表示第j(j=l,2,…,n)只数据流在时刻ti到达的数据。

定义4考虑演化数据流,定义时间衰减函数:

其中,t0为数据到达时刻;t为当前时刻。当c=l时,演化流蜕化为非演化流,即流中的各数据不论其何时到达都具有相同的权重。

统一流聚类表示模型:数据窗口W作用于集合{Sj}(j=1,2,…,n)产生数据集,生成数据个数为n(数据的维数为窗口大小W)或W(数据维数为d)的集合,每收到B(B≤W)个数据则更新一次数据集,根据n和d值进行Transform(S,n,d)操作,聚类过程中按如下公式计算权重:f(ti)·pji(j=l,2,…,n)再结合权重计算相似性。参数n,W,d,B,以及衰减参数c的不同取值组合可表示出不同的数据流模型及其聚类处理框架。

流聚类框架如下所示:

3 流数据的聚类算法研究

3.1 经典聚类算法综述

第一个以流数据为分析对象的聚类算法是由Sudipto Guha等提出的STREAM算法。这种算法根据分治原理,使用一个不断迭代的过程实现有限空间对数据流进行K-means聚类,但该算法无法处理演化的数据流。

Aggarwal在总结上述方法本质缺陷的基础上提出了一个数据流聚类框架Clustream[5],其核心思想是将聚类过程分为在线和离线两个阶段。在线部分的任务是存储数据流的汇总结果,生成一种称为微聚类的信息存储结构,并按金字塔式时间结构将中间结果进行保存。离线部分既是根据用户指定的观察时段及聚类数量,快速生成聚类结果的过程。Clu Stream不足之处在于需要用户指定聚类簇数k,要求强行输入固定的聚类簇数必然影响真实的聚类形态分布。同时,算法是以K-means算法为基础,对非凸形状聚类效果不好,无法发现任意形状的聚类,且当噪声数据增多时,聚类质量急骤下降。

近年来许多学者围绕Clustream框架进行了大量研究。Aggarwal等后续提出了专门针对高维连续属性数据流的HPStream算法,该算法引入了子空间聚类,并提出了具有遗忘特性的聚类结构,使用高维投影技术和衰减结构来处理高维数据流,HPStream算法对高维数据流具有很好的健壮性。但算法中需要用户来指定平均聚类维数,用户一般并不具备这种领域知识,成为该算法的瓶颈。Cao等人提出了基于密度的两阶段聚类方法,即Den Stream算法,该算法仍然沿用Clu Stream算法中的双层结构,创造性的引入了潜在微聚类簇和孤立点微聚类簇结构,具备对孤立点的分析能力,即随着数据流不断进化,算法可以识别在某一时间段有可能演变成聚类簇的孤立点或“潜在聚类”,从而更加准确的捕获真实的聚类形态。但由于算法中采用全局一致的绝对密度作为参数,使得聚类结果对参数十分敏感,而且它不支持指定的时间窗口内实时数据流的演化分析。

3.2 最新公布的算法

在最近的数据流聚类研究中,有将多种原有技术进行结合使用,也有很多新颖的方法不断出现,其中受到广泛关注的3类方法是基于网格的数据流聚类技术[6,7,8,9]、子空间聚类技术[7,8,9]、混合属性数据流聚类[10],代表了当前数据流聚类研究的主流方向。

(1)D-Stream算法

D-Stream是一个典型的数据流网格聚类算法[6]。该算法通过设定密度阀值将网格分为密集、稀疏以及过渡期3类,算法在线维护一个存放非空网格的哈希表grid_list,每读入一个数据点,确保其所属网格在哈希表中,同时更新该网格的特征向量,并且通过理论证明出密集网格与稀疏网格相互转变所需的最短时间,以该时间的最小值gap为周期扫描哈希表,删除表中的稀疏网格。聚类请求到来时,将相邻的密集网格合并形成聚类(内部网格必须是密集的,外部网格可以是密集或者过渡期网格)。该算法有很多优点:(1)避免了将距离作为相似性度量标准,支持任意形状、任意大小的簇;(2)计算结果与数据输入顺序无关;(3)只需进行网格映射,避免了大量的距离和权值的计算,使得算法计算量与数据流量无直接关系。该算法的不足之处是当数据流维度较高时,会产生大量的网格,算法运行效率急剧下降。

(2)GSCDS算法

最近的研究中,子空间聚类技术也被借鉴到数据流模型,最近公布的GSCDS算法[8]就是一个代表。子空间聚类算法是一类在数据空间的所有子空间搜寻聚类的方法,根据搜索策略的不同一般分为自底向上的模式和自顶向下的模式。GSCDS算法充分利用自底向上网格方法的压缩能力和自顶向下网格方法处理高维数据的能力,将它们结合起来应用于实时数据流。

该算法的优点在于:(1)计算精度高;(2)能很好地识别和恢复网格中被划分面切割的聚类;(3)能够发现隐藏在任意子空间中的聚类。但是由于高维空间的子空间数量很多,使得算法的运算量较大,且该算法不能支持数据流的演化分析。

CAStream算法[7]也是最近公布的一个子空间聚类算法,算法借鉴Lossy Counting思想近似估计网格单元,采用改进的金字塔时间框架分割数据流,算法支持高维数据流、任意聚类形状及演化分析。

(3)HClu Stream算法

真实数据流一般具有混合属性,全连续或全离散属性的数据流在现实中几乎不存在,而目前大多的算法仅局限于处理连续属性,对离散属性采取简单的舍弃办法。为了使算法有效处理真实数据流,Yang等人提出一种基于混和属性的数据流聚类算法Hclu Stream[10]。

其它最新公布的算法还有提出纳伪和拒真两种聚类特征指数直方图,来分别支持纳伪和拒真误差窗口的Clu Win算法[11]、通过图形处理器来实现高速处理实时数据流聚类的算法[12]以及采用核方法聚类的算法[13]。

4 结束语

本文从流数据特点,研究现状及聚类算法等方面进行了总结。流数据的数据挖掘和知识发现已成为目前国际数据挖掘领域的新兴研究热点。其未来的研究将会主要集中在以下几个方面:(1)基于资源约束的自适应实时数据流聚类。这一概念最早由Gaber[14]等人提出,主要针对无线传感网络等资源约束环境进行数据流聚类;(2)高维度实时数据流的聚类。大多数真实数据流都具有高维特性,高维空间中对象分布稀疏,噪声不易识别,是一个较难解决的问题;(3)分布式环境下的多数据流实时聚类。

摘要：流数据挖掘技术是数据挖掘领域的新研究方向之一,而聚类研究又是其重要的内容。本文介绍了流数据基本特点,在统一流聚类表示模型的基础上,对现有流数据聚类算法进行了总结,并进一步提出了流数据聚类技术的研究方向和前景。

关键词：流数据,聚类,表示模型

聚类算法的改进的研究篇2

Web文本挖掘作为Web数据挖掘的一个重要分支,可以对文档集合的内容进行分类、聚类、关联分析等。聚类是知识发现的重要工具,它是一种无指导的学习,能够从海量的数据中分析并挖掘出人们需要的东西,已经被广泛应用到信息管理、搜索引擎、推荐系统等多个领域。

1 类间距离

聚类就是按照对象的类间距离将距离近的放在一类,距离远的放在一类。聚类时常用的类间距离公式如下:

Single linkage(单连通):

Complete linkage(完全连通):

Average group(平均连通):

Centroid distance(质心距离):

2 层次聚类算法

2.1 传统层次凝聚算法

根据结果的生成顺序,层次聚类可以分为两类:分裂的层次聚类、凝聚的层次聚类。大部分层次聚类都属于后者,它先把每个对象看做一个类,然后将距离最近的两个类合并,直到所有对象都在一个类中,或者达到预定的停止条件。

下面举个例子来理解一下层次聚类算法的执行过程。假设有8个对象,每个对象有两个(也可以是多个)属性1x、2x:A(1,1)、B(3,4)、C(1.5,1.5)、D(2,3)、E(4,4)、F(3,3.5)、G(5,5)、H(5,3.5)。我们选用欧几里得距离计算对象之间的初始化距离矩阵,结果如表1所示。

我们选用公式1,找到距离的最小值dB→F=0.50,然后将B、F归为一类(B,F),重新计算距离矩阵。经过一系列地合并、计算距离矩阵,最后我们得到聚类的层次为((((((B,F),E),D),H),G),(A,C)),如图1所示。

分析上面的计算过程,第一次合并的是距离最小的两个类,重新计算该类与其他类之间的距离时我们选择的是公式1,例如:d((B,F),E)→D=min(dBD,dFD,dED),其中dBD、dFD和dED都是从初始距离矩阵中得到的,即新的距离矩阵的值都来源于初始距离矩阵。第二次迭代时是从新的距离矩阵中取的最小值,那么这个最小值应该是初始距离矩阵中的次小值。依此类推,直到所有的对象合并完为止。

2.2 改进后的层次聚类算法

在上面的例子中可以看出,合并过程中每次迭代都要重新计算类间距离,比较浪费时间,我们发现合并是按照初始距离矩阵从小到大的顺序进行的,如果我们把初始距离矩阵中的元素用线性结构存储起来,对其进行从小到大的排序,那么合并类时只要顺序遍历线性结构就行了,这样就提高了层次聚类的速度。具体描述如下:

(1)将给定数据中的每个对象看做一类,计算各个类之间的距离dij,将距离存储在一维数组中。

(2)对一维数组进行升序排列。

(3)对于数组中的当前元素dij(即对象ix与xj之间的距离),可以分为三种情况:(1)如果xi∈Cm,xj∈Cn,则Ck=Cm∪Cn。(2)如果xi∈Cm,xj没有合并到类中,则Cm=Cm∪xj。(3)如果ix、xj都没有合并到类中,则

(4)重复步骤(3),直到数组中所有的元素处理完毕。

文献证明了改进后的层次聚类算法的运行速度提高了近3倍,而聚类的结果不受影响。

3 k-means算法

3.1 传统k-means聚类算法

k-means算法是一种应用最广泛的划分算法,它的聚类结果是平面的,一般用不相交的集合来表示。k-means聚类算法的基本思想:给定n个数据,随机地选择k个对象作为初始聚类中心,计算各个对象到聚类中心的聚类,将剩下的对象分配到聚类最近的类中,然后重新计算聚类中心,不断重复这个过程,直到所有的聚类不再发生变化为止。

下面举个例子来理解一下k-means算法的执行过程。假设有6个对象,每个对象有两个(也可以是多个)属性1x、2x:A(1,1)、B(2,1)、C(3,4)、D(4,3)、E(2,2)、F(5,4),我们的目标是将它们归为两类即K=2。选用A、B作为初始聚类中心,则C1=(1,1),C2=(2,1),选用欧几里得距离计算距离矩阵,如表2所示。

我们根据公式1,将对象划分到距离最近的那个类中,即,然后重新计算聚类中心,采用各个对象的平均值作为新的聚类中心,则再计算各个对象到新的聚类中心的距离。经过一系列地划分、计算聚类中心,最后得到的聚类结果为:C1=(A,B,E),C2=(C,D,F),如图2所示。

在k-means算法执行过程中,每次迭代都把数据分配到距离最近的类中,新的分类产生后,需要计算新的聚类中心,这个过程的时间复杂度为O(nd),则该算法总的时间复杂度为O(nkd),其中d是对象的维数,k是指定的聚类个数,n是数据对象的总个数。当数据量比较大时,算法的时间开销是非常大的。

3.2 改进后的k-means算法

在计算对象到聚类中心的距离时,我们采用的是欧几里得距离,该种计算方法具有4种性质(文档与自身的距离为0、非负性、对称性、三角不等式),其中三角不等式即从对象i到对象j的直接距离小于等于途径其他对象的距离。k-means算法每次迭代都要计算对象到每个聚类中心的距离,通过比较将对象分配到距离最近的聚类中,这些不必要的比较和距离计算比较浪费时间,我们可以利用三角不等式来减少每次迭代的计算次数,这样就可以处理大数据量时的时间开支问题。

具体流程为:

(1)任意选择k个对象作为初始聚类中心。

(2)计算每两个聚类中心的距离d(C i,Cj),其中i,j=1,2,k。

(3)对于每个对象ix,设它当前属于类ξi,ξi类的中心为iC,计算ix与iC的距离d(x i,C i)。如果d(C i,Cj)≥2d(x i,C i),则ix所在的类不变,否则,计算d(x i,Cj);如果d(x i,Cj)

(4)重复(2)、(3)步,直到所有聚类都不变化。

文献证明了该改进算法获得了很好的聚类效果,提高了算法的效率。

4 混合文本聚类算法

凝聚型层次聚类算法能够生成层次化的嵌套簇,准确度较高,但时间复杂性较高,运行速度较慢,在进行合并之后无法回溯。k-means聚类算法的运行速度较快,但是必须事先确定k的取值,对初始聚类中心的依赖性比较强,不适合发现非凸形状的聚类,虽然可以保证局部最小,但不能保证全局最小。

如果将凝聚型层次聚类算法与k-means算法结合起来,利用凝聚型层次聚类算法来产生k-means算法所需要的k值和初始聚类中心,可以有效的克服k-means算法的不足。

为了能更准确的发现用户的兴趣所在,本算法将2.2节改进的凝聚型层次聚类算法和3.2节改进的k-means聚类算法结合起来。

具体流程如下:

(1)计算给定的文档集合D={d 1,di,dn}中各个数据间的距离dij,将距离存放在一维数组中。

(2)对一维数组进行升序排列。

(3)将文档集合D看成是一个聚类C={c 1,ci,cn},其中ci={d i}。

(4)设定一阈值ξm,如果数组中的当前元素dij≤ξm,则分为三种情况:(1)如果di∈cm,dj∈cn,则ck=cm∪cn。(2)如果di∈cm,dj没有合并到类中,则cm=cm∪dj。(3)如果di、dj都没有合并到类中,则ck=di∪dj。重复步骤(4),直到数组中所有元素处理完。否则如果dij>ξm,凝聚算法结束,得到含有k个子类的聚类C={c 1,ci,ck}。

(5)将C={c 1,ci,ck}作为k-means算法的初始聚类中心。

(6)计算每两个聚类中心的距离d(c i,c j)。

(7)对于D中的每个文档di,设它当前属于类ξi,ξi类的中心为ic,计算di与ic的距离d(d i,c i)。如果d(c i,c j)≥2d(d i,c i),则di所在的类不变,否则,计算d(d i,c j);如果d(d i,c j)

(8)重复步骤(6)、(7),直到所有聚类都不再变化。

5 结论

本文提出的混合文本聚类算法的难点就是阈值的确定,要通过相关领域知识来选定阈值,才能得到满意的聚类结果。笔者将该算法用到了一个小型的个性化搜索引擎中,通过试验将阈值定义为5.0,对用户的浏览记录进行聚类,较好的挖掘出了用户感兴趣的内容。

随着Web技术的发展以及用户的需求和行为日益多元化,如何从海量的数据中分析并挖掘出人们需要的内容,个性化的搜索引擎已经成为人们研究的热点,聚类的研究也将成为人们研究的热点。

参考文献

[1]段明秀,杨路明.对层次聚类算法的改进[J].湖南理工学院学报(自然科学版).2008.

[2]王会芬.基于Web的网页聚类系统的研究与实现[D].天津大学硕士学位论文.2005.

[3]严华.一种改进的k-means算法[J].计算机与现代化.2009.

[4]易珺.改进的k-means算法在客户细分中的应用研究[J].微型机与应用.2005.

聚类准则研究篇3

本文分析了常用模糊聚类算法的缺陷，提出了解决这些缺陷的一种组合式模糊聚类算法，并通过相关实验分析证明其合理性。

1 常用模糊聚类算法分析

目前比较常用的模糊聚类算法有：基于模糊等价关系的传递闭包方法；基于模糊图论的最大树方法，以及在传统的均值聚类基础上演变而来的、基于目标函数的FCM（模糊C均值）方法。

设聚类样本空间为X=(x1,x2,…,xn），对应的模糊相似矩阵为R=(rij）。其中，rij∈[0,1],rij表示对象xi和xj的相似度，相似度的计算可采用相似系数法、距离法以及主观评分法等，本文中选择欧氏距离法。

1.1 传递闭包法和最大树法

(1）传递闭包法

根据模糊数学理论，模糊等价矩阵能进行等价的分类，而模糊相似矩阵仅仅满足自反性和对称性，并不满足传递性，因此采用求R的传递闭包t(R)形成模糊等价矩阵是最自然的想法。当生成传递闭包后，取某一实数λ∈[0,1]，生成λ-截集矩阵，便可得到不同的分类，从而形成一种动态聚类图。

传递闭包是包含R的最小传递矩阵，通常采用逐步平方法求R的传递闭包，即R→R2→R4→Rg→…→R2k经有限次运算后，一定有R2k=R2k+1，于是t(R)=R2k。

算法分析：采用传递闭包法进行分类，虽然从原理上看很自然，但在面向全体教师的教学评价中，其对应的模糊相似矩阵阶数较高，计算量很大，因此应用受到一定的限制。可根据传递闭包自反性、对称性特点，其对对角线元素永远为1，且可只计算上三角或下三角,这样可以适度减少计算量。

(2）最大树法

传递闭包法是基于等价矩阵进行分类的，而最大树法是直接使用相似矩阵进行分类，其基本思想是：以被分类元素为顶点，以模糊相似矩阵R中的元素为权重的一棵最大的生成树。

最大树模糊聚类算法的主要步骤为：

(1)提取待聚类对象的特征，建立模糊相似关系，得出模糊相似矩阵；

(2)根据模糊相似矩阵，按Prim方法或Cruskal求出最大树；

(3)确定相应的阈值λ，将最大树中权重小于该阈值的边去掉，使其成为一个不连通的图，该图对应有若干个连通分枝，各连通分枝中的结点即聚为一类。

算法分析：事实上，如果将最大树中连接两个结点i和结点j所在边的权作为rij构造矩阵，则该矩阵其实就是R的一个传递闭包[1]。因此最大树法聚类本质上与传递闭包法的聚类是一样的，且在解决低维的小样本集分类时更为直观。但也存在着这样的情况：彼此差异很大的模糊相似矩阵有可能生成相同的传递闭包，而用相同的模糊等价传递闭包来进行分类，就可能出现不合理现象，这是这一类模糊聚类算法的缺陷。

1.2 传统FCM算法

由Bezdek提出的模糊C均值聚类（FCM），属于一种目标函数法，是模糊聚类算法中运用最广的算法。

(1）算法步骤

假设要将样本空间X分为k个簇，簇中心集合为C=(c1,c2,…,ck），使(1)式所示的目标函数Jm最小(该目标函数是基于类内距离和的)，且满足（2）式的约束条件。

其中：U=(μi,j)为模糊隶属矩阵，每个矩阵元素μi,j表示数据xi隶属于中心为Cj的类的隶属度值。m为模糊加权参数，也称为平滑因子，控制模式在模糊类间的分享程度，经验取值范围为[1,5]。

应用拉格朗日乘数法，基于上述约束条件求目标函数的极小值，可得(3)式和(4)式。

其中，Dij是Xi到第j类中心Cj的欧氏距离||Xi-Cj||。

FCM算法的步骤如下：

(1)设定初始参数：m,k,迭代次数s，算法终止误差ε；

(2)设置初值：初始聚类中心C0(c1,c2,…,ck),t=0;

(3)计算隶属度矩阵：根据（3）式计算Us;

(4)计算（4）式计算下一次的簇中心Cs+1;

(5)若||Us+1-Us||<ε，算法结束，否则s=s+1,返回(3)直至迭代结束。

(2）算法缺陷及目前研究

从上述的FCM算法步骤可知，FCM算法本质上是一个反复修改聚类中心和隶属度矩阵的过程，必须事先确定欲聚类的个数、设置初始的聚类中心以及模糊加权参数这些初值。然而，在实际应用中，聚类个数往往很难事先确定；聚类结果对初值过于敏感；FCM是一种迭代优化算法，初值设置不当很容易产生局部而非全局最优解的情况。针对这些问题，许多研究者不断探索改进方法：如基于模拟退火的FCM算法[2]；运用人工免疫细胞模型来改进的模糊聚类[3]；运用数据加权策略的模糊均值聚类[4]等等。然而上述这些方法，或者因为所设计的目标改进函数过于复杂、收敛速度太慢，或者因改进算法本身需重新设定新的参数初值，或者因为改进算法需有特定的条件等因素，在实际应用中仍受到种种限制。因此许多学者将算法改进的重点放在如何更好地设置合适的参数初值方面。其中，运用分阶段思想的FCM聚类算法尤其受到重视。

本文提出的基于F统计量层次聚类与FCM聚类的组合算法，属于两阶段式FCM聚类算法。该算法无需事先设定聚类个数及中心初值，且仍保持FCM聚类算法的简单性。

2 组合式模糊聚类算法

(1）算法基本思路

该算法分成两个阶段：初值处理阶段和FCM处理阶段。

(1)初值处理阶段：采用基于F-统计量的层次聚类法。

首先用欧氏距离距离法，生成相应的模糊相似矩阵；

然后运用自下而上的层次聚类思想，逐步生成不同聚类个数（建议在2～之间）下的分层聚类树及临时聚类结果；

计算不同结果下的F统计量，获得最大F统计量对应的分类结果，即作为下一阶段的初值（聚类个数及聚类中心初值）。

(2)FCM处理阶段：调用FCM聚类算法。

(2）算法描述

【输入】样本数据集;模糊加权参数m,迭代终止条件ε

【输出】模糊聚类中心;模糊划分矩阵U

【算法】

生成模糊相似矩阵;

循环：while k<t do

计算任意二个簇之间的距离；（初始时每一样本为单独的簇）

合并距离最近的二个簇Ci和Cj，生成新簇Cx;

计算F-统计量（记为Ft):

在所有的F-统计量中，求得最大值（设为Fk）及对应的簇（设为C);

调用FCM算法；

算法结束。

说明：的距离，表示第j类中样本中心，F-统计量遵从自由度为（t-1,n-t）的F-分布，公式中的分子表示类与类间的距离，分母表示了类内样本间的距离，因此F-统计量值越大，类划分的结果越恰当。采用基于F-统计量的层次聚类法获得了聚类数和聚类结果，避免下一步模糊聚类初值的随意性，并能起到快速迭代、提高收敛的效果。

3 实验及分析

为分析基于F统计量层次聚类与FCM聚类组合算法在教学质量评价中的效果，以我院某一年度教师教学整体设计为实验数据库，从中抽取50名教师的平均评价数据为样本集X（见表1）。由于教学评价的数据其量纲和数量级相同，故数据的标准化不必经过标准差变换而直接进行极差变换即可。算法运用MAT-LAB软件实现。

(1）组合式模糊聚类算法测试

设参数m=2；ε=0.000001，则通过基于F统计量层次聚类，可得该样本集生成6个类，聚类中心是C00.6970 0.7955 0.8030 0.7803 0.7121 0.6818 0.81820.5583 0.4778 0.4417 0.4250 0.3917 0.4417 0.49170.1333 0.0667 0.0667 0.1167 0.0667 0 0.13330.6667 0.6667 1.0000 0.3333 0.6667 0 0.33330 0.6667 1.0000 0.3333 0.6667 1.0000 1.00000 0.5000 0.6667 0 0.6667 0 0

以此为初始参数，调用FCM算法，可得6个聚类：

经考察，组合式模糊聚类生成的6类，其对应教师综合评价分布如下：C3类和C2类分别对应[40,50]和[50,60]两个区间；C5对应[68,70]区间（无61-67的得分）；C4对应[70,78]区间；C6对应[78,86]区间；C1对应[89,93]区间（无高于93的评价）。

值得注意的是，三位相同综合评价（均为70分）的教师分属于两个不同的类，其中，有第2名教师与与第50名同属C5类，第27名教师属C4类，主要原因是这两类中权重最大的教学内容设计（占30%）差别较大。

(2)FCM算法测试

显然，当初始参数的设定与组合式模糊聚类预处理生成的结果相同时，算法的结果应该是完全相同的。下面分别以相同的初始聚类中心、不同的聚类个数设置来进行相应的测试（m=2；ε=0.0001）。

(1)聚类个数初值K=4:

在该聚类中，C2类对应的综合评价区间是[40,50];C1类对应的综合评价区间是[50,70];C4类对应的综合评价区间是[70,86];C3类对应的综合评价区间是[85,93]。

很显然，设定聚类初值为4不太合理，部分聚类中的数据与现实评价的正常划分不相吻合。

(2)聚类个数初值K=8:

在该聚类中，C3类对应的综合评价区间是[40,50];C2类对应的综合评价区间是[50,60];C4类对应的综合评价区间是[68,70]（无61-67的得分）；C8类对应的综合评价区间是[70,74];C5类对应的综合评价区间是[76,82];C7类对应的综合评价区间是[82,84];C1类对应的综合评价区间是[90,92];C6类对应的综合评价区间是[85,93]。

显然，当聚类个数为8时，聚类结果与现实评价的划分呈现出或者过于紧致，或者过于疏松的现象，且存在较大的交叉区间（如C1类与C6类）。

(3）聚类效果对比分析

以本文中的教师教学整体设计测试数据样本为例，从聚类结果与综合评价的常规划分对应关系来看，采用基于F统计量层次聚类生成聚类个数及聚类中心的组合式模糊聚类效果明显优于FCM算法的效果。下面再通过聚类有效性指标函数的对比来分析。

聚类有效性指标主要有两类：一是有效性指标仅包含了数据集中数据成员的隶属度，如Bezdek的划分系数和划分熵；二是有效性指标不仅包含了数据成员的隶属度，而且还包含了数据集本身，如Xie-Beni指标和Fukuyama-Sugeno指标。本文采用Xie-Beni指标。

设样本集为X，最终生成的聚类个数为K，聚类中心为C，隶属度矩阵为U，则聚类有效性判别函数值V可用如下的公式计算：

其中，分子用来衡量类内的紧密度，值越小越紧密。分母表示类间的分离度，值越大越好。因此函数值V越小聚类效果越好。组合式模糊聚类与传统FCM聚类的Xie-Beni指标对比值见表2。Xie-Beni指标是一个紧致的、分离的模糊聚类有效性函数，最佳的聚类数对应着最小函数值。

4 结束语

本文针对FCM聚类算法中聚类类别数及初始聚类中心需事先给定这一不足之处，提出基于F统计量层次聚类的组合式模糊聚类方法，并以学院课程教学设计评价为测试数据样本，进行聚类效果测试与分析。实验证明，这种改进的组合式算法其聚类效果要比传统的FCM聚类算法更优。

参考文献

[1]骆洪青,吴小俊.模糊聚类分析的一种新方法研究[J].华东船舶工业学院学报,2000,14(3):24-27.

[2]段林珊,刘培玉,谢方方基于模拟退火的样本加权FCM算法[J].计算机工程与设计,2013,34(6):2004-2008.

[3]王伟,王磊,李玉祥.基于人工免疫细胞模型的模糊聚类算法[J].计算机工程,2011,37(5):13-15.

模糊聚类分析及其应用研究篇4

模糊聚类分析技术是智能信息处理中的一个重要研究方向, 是用模糊数学方法研究聚类问题, 模糊聚类算法[1,2]由于具有良好的聚类性能与数据表达能力, 已经成为近年来研究的热点, 广泛的应用在分析和解决实际问题当中, 包括工程、计算机科学、生命和医学科学、社会科学、经济学、无导师的学习、类型学分析或划分。这是由于实际问题中, 一组事物是否属于某一类常常带有模糊性, 也就是问题的界限不是十分清晰。我们不能明确回答是或否, 而只能在某种程度上回答是。聚类分析研究已经有几十年的历史, 它的重要性及与其他研究方向的交叉特性均已得到人们的肯定, 其中模糊聚类是数据挖掘、模式识别等研究方向的重要研究内容之一, 在天气形势分类、建筑的水泥适应性、汉字职别等方面具有极其重要的作用。本文将模糊聚类分析原理与实际问题结合起来, 重点研究模糊聚类分析的过程和步骤, 特别是聚类过程中参数的客主观处理方法。

1 基本概念与定理

定义1设R= (rij) n×n是n阶模糊方阵, I是n阶单位方阵, 若R满足自反性 (I≤R) , 对称性 (RT=R) , 传递性 (R 2≤R) , 则称R为模糊等价矩阵。

定义2设R= (rij) n×n是n阶模糊方阵, I是n阶单位方阵, 若R满足自反性 (I≤R) , 对称性 (RT=R) , 则称R为模糊相似矩阵。

定理1 R是n阶模糊等价矩阵λ∈[0, 1], Rλ是等价的布尔矩阵。

定理2设R是n阶模糊等价矩阵, 则0≤λ<μ≤1, Rμ所决定的分类中的每一个类是Rλ所决定的分类中的某个子类。

定理2表明, 当λ <μ时, Rμ的分类是Rλ分类的加细, 当λ由1变到0时, Rλ的分类由细变粗, 形成一个动态的聚类过程。

定理3设R是n阶模糊相似矩阵, 则存在一个最小的自然数k (k≤n) , 使得Rk 为模糊等价矩阵, 且对一切大于k的自然数l , 恒有Rl=RK。

2 模糊聚类方法与步骤

模糊聚类分析的实质一般是指根据研究对象本身的属性来构造模糊矩阵, 并在此基础上根据一定的隶属度来确定聚类关系, 即用模糊数学方法把样本之间的模糊关系定量的确定, 从而客观且准确地进行聚类。但大多数对象并没有严格的类属性和隶属关系, 它们在属性等方面存在着重叠性和交叉性, 具有亦此亦被的性质。

(1) 建立数据矩阵

设论域U={x1, x2, , xn }为被分类对象, 每个对象又由m个指标表示其性状:

则得到原始数据矩阵为

在实际问题中, 不同的数据一般有不同的量纲, 为了使观察的特征值具有相对意义, 使各特征值取值限定在[0, 1]上, 需进行规格化处理, 方法很多。

(2) 建立X上的模糊相似矩阵

鉴别X中xi与xJ的接近程度, 用[0, 1]中的数riJ表示xi与xJ的相似程度, 得到相似矩阵 (riJ) n×m , 对其求等价闭包或等价类, 就可对X中的元素进行分类。这里需要指出的是相似系数矩阵必须符合自反性、对称性要求, 可根据实际情况选择数量积法、夹角余选法、相关指数、指数相似系数法等。

谱聚类算法及其研究进展篇5

谱聚类算法是以图论当中的谱图理论为基础,重点在于设计合适的距离度量,计算待聚类的数据点之间的距离或相似性,构造邻接图,最后将聚类任务转化为邻接有向图的最优划分问题。本文旨在从基础理论、代表算法、比较分析等方面向读者介绍这种新型的聚类算法。

1 谱聚类算法研究进展

谱聚类的诞生可以追溯到1973年,Donath和Hoffman首次基于邻接矩阵构造了图的划分[7]。在同一年,Fieldler发现图的二划分与Laplacian图的第二小特征向量有密切关系,并且建议使用该特征向量进行图的划分[8]。从此以后,许多研究者加入到谱聚类方法的研究队伍中,例如,Pothen,Simon,and Liou[9]、Bolla[10]、Hagen and Kahng[11]、Hendrickson and Leland[12]、Van Driessche and Roose[13]和Guattery and Miller[14]等。

谱聚类逐渐成为流行的聚类方法[1,2,3,4,5,6]。在算法扩展和理论分析方面涌现了大量的研究成果。Dhillon等人将谱聚类应用于联合聚类问题[14],并分析了谱聚类与加权k-means的关系[19]。Bach等人利用谱聚类辅助学习相似性函数[9]。Kempe等人分析了再分布式环境下的谱聚类[21]。Perez等人提出了稀疏核谱聚类并应用于大尺度数据集[17]。Jia等人将集成学习方法应用于谱聚类[22]。Zhang等人设计了基于边界的多路谱聚类方法[14]。最近,王春腾等分析了维数约简与谱聚类的关系,提出了基于维数约简的谱聚类方法:基于非负约束的谱聚类算法(NMFSC)[15]和基于独立成分分析的谱聚类(ICASC)[16]。

特别地,聚类方法在图像分割任务的应用中,传统的做法提取各像素点的特征向量,利用k-means等聚类方法对像素点进行聚类。这类方法固有的缺陷是对样本点的分布假设,例如k-means方法假定样本点的分布服从高斯分布。然而,在现实应用中该假设未必成立。谱聚类方法的优势在于不需要事先假定样本服从某种特定的分布,计算像素点样本之间的相似性,构造相似性矩阵,通过对相似性矩阵的谱图划分达到划分样本空间的目的,从而避免了对样本空间分布假设的依赖,使得谱聚类方法在理论上能够适应任意分布形状的样本空间。

2 理论基础

2.1 相似图

为说明谱聚类的基本理论,本节首先引入有关的基本记号和相似图概念。已知一个给定的数据集,根据已设计的距离公式可计算出样本点两两之间相似度,构造出相似性矩阵。以每个数据点为顶点,顶点与连通,给其连接边赋予非负权值,即数据点与之间的相似性。此时,基于相似性矩阵构造出无向图,其中,是顶点集合,是边集合。聚类的直接目标是将相似的点尽量放在同一簇中,而不相似的点尽量归入到不同簇中。至此,聚类问题可以转化为该无向图上的划分问题,找到图的某个分割,使得同一簇中点点间的边权值之和最大,而不同簇之间的点点间边权值之和最小。

无向图称为给定数据集的相似图,其中,顶点集,边集。在边上赋予权值,构成无向加权图,顶点与之间赋予非负权值,则有加权邻接矩阵,。特别地,当,表示两顶点间不连通。

2.2 谱图划分理论

谱聚类算法的思想来源于谱图划分理论[19]。无向加权图构造完成后,就可以寻找图的最优划分,需要建立图的最优划分准则。图论中常用的划分准则有M-cut,Mbmax-cut,N-cut,Average-cut,Ratio-cut等。限于篇幅,本文仅对常用的划分准则——规范割集准则(Normalized-cut或N-cut)作简要介绍。

N-cut是由Shi和Malik提出的,其目标函数的公式如下:

其中。以Ncut函数作为最小化目标函数,称为规范割集准则。从该准则的目标函数可以看出,不仅可以度量同簇样本间的相似性,还可以度量不同簇间样本的相异性。Shi和Malik对上述目标函数进行了拓展,提出规范关联目标函数(Nassoc):

其中,与分别是在子图,内各自所有顶点间连接权值的总和。该准则衡量了同一簇内的样本间的紧凑程度。进一步的推导,可以得出Ncut函数与Nassoc函数之间的线性关系:。所以,最小化Ncut函数与最大化Nassoc函数是等价的,两个目标函数可以任选其一。在实际应用中,Ncut函数更常用。

3 谱聚类算法

选用不同的划分准则,可以构造出不同的谱聚类算法,大致可以将谱聚类算法分为两类:迭代谱聚类和多路谱聚类。

就迭代谱聚类而言,Peron与Freeman合作提出PF算法,其主要思想是构造样本集的相似图,计算相似性矩阵的最大特征值及其对应的特征向量,以特征向量中零元素对应的数据点为中心生成一个簇类,其余点生成另外一个类,由此迭代,得到最终聚类结果[25]。其他具有代表性的迭代谱聚类算法有SM算法[1]、SLH算法[6]和KVV[26]算法等。

就多路谱聚类而言,Ng和Jordan等人提出NJW算法,其基本思想是计算相似性矩阵的拉普拉斯矩阵,寻找该矩阵的前个最大特征值及其对应的特征向量,将原数据点投影到k个特征向量构造的新的特征空间中,最后在新的k维空间中实施kmeans,得到最终聚类结果[2]。Meila对NJW算法进行的拓展,将NJW中的k维特征空间再实施了一个线性旋转,构造出新的投影空间,然后在该空间中实施聚类[28]。

不管是上述哪一类方法,谱聚类算法的步骤大致可以归纳为如下三步:

Step1:构造无向图,其中,顶点集,边集。根据样本点与之间的相似性,赋予边权值,得到加权邻接矩阵,。此时,将聚类问题转化为图的最优划分问题。最优划分准则的选取直接影响谱聚类算法的效果,也是谱聚类算法研究的集中关注点。谱聚类算法改进大多集中在相似性度量函数和最优划分目标函数的设计上。

Step2:计算相似性矩阵W的前k个特征值及其对应的特征向量,构造新的k维特征空间,将原始样本点投影到新的k维空间中。

Step3:在新的k维特征空间中实施传统的聚类算法,例如k-means等。

4 结论

谱聚类在理论和应用上都具有突出优势,近年来在学术界得到越来越多的重视,使聚类分析的研究得到延伸,适应更多的现实应用问题,已成为聚类分析中一个重要的新兴分支。本文从谱聚类的产生、发展、基本理论和代表算法等方面比较系统的总结了谱聚类算法及其研究进展,可望使读者对谱聚类形成基本的初步认识,由此将该方法应用到科学研究与工程应用的各种实际问题中。

摘要：谱聚类具有良好的理论基础,被广泛应用于科学研究与工程应用的各个领域,成为聚类分析领域重要的新兴分支,受到越来越多的研究者的重视。然而,国内相关文献较少,该文从谱聚类算法的产生、研究进展、基础理论及代表算法等方面对谱聚类算法作简要综述,有望使读者对该领域形成初步认识。

聚类分析对学生成绩的研究篇6

据30个学生的各科成绩及平均成绩, 对学生的成绩情况对学生进行简单的分类, 以便根据学生的成绩情况和所属类别进行有针对性的教学管理。基本数据变量包括“一元微积分”、“多元微积分”、“线性代数”、“概率统计”、“平均成绩”五项成绩。

本次实验选择系统聚类分析, 主要根据学生在各科成绩的接近水平来描述学生成绩之间的距离, 进而通过距离描述学生间的相似程度, 并将距离小的学生分为一类, 通过合理的分类方便进行针对性的教学管理。具体数据见“聚类分析.asv”。以下是分析过程和结果分析:

表1中第一列表示聚类的步骤号, 共30个样本, 聚类了3次, 第二列和第三列标示每步聚类中参与的样本数据原始编号或者是参与聚类的类别号, 如第一次聚类是第10和第17两个样本进行合并, 第四列两个样本 (原始类) 间的距离为聚类系数0.034, 第五列和第六列表示进行合并的类号, 如果为0, 表示为原始数据, 否则代表已经有的类号;第六列表示本次合并完成后, 接下来将参与的聚类步骤, 如第10和第17两个样本进行第一次合并后形成新类, 这个新类将在第14步参与下一次合并, 即与样本8进行合并成新类。

2 分析结果

图2聚类分析树状图形象地显示了聚类的过程, 可以通过“纵切截断法”来确定不同分类数时各个类中包含的样本值。由图7和图8可以看出, 当将全部样本分为三类时, 第一类中样本成员有:1、8、10、15、17、21、22、24、26、29十个;第二类中样本包括2、5、9、11、12、16、19、27、28、30;第三类中样本包括3、4、6、7、13、14、18、20、23、25。

参考文献

[1]吴喜之.统计学:从数据到结论[M].中国统计出版社.2006年10月第二版.

[2]李仲来.系统聚类分析中应注意的两类问题[J].数理统计与管理.12卷6期.

【聚类准则研究】推荐阅读：

国际会计准则------第157号公允价值准则05-26

关联准则05-22