聚类算法的改进的研究

薄文彦 付文兰 张凤英

1山西大同大学教育科学与技术学院 山西 037009 2内蒙古工业大学信息工程学院 内蒙古 010051

0 引言

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 初始化距离矩阵

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

图1 凝聚层次聚类算法结果

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

2.2 改进后的层次聚类算法

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

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

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

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

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

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

3 k-means算法

3.1 传统k-means聚类算法

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

下面举个例子来理解一下k-means算法的执行过程。假设有6个对象，每个对象有两个(也可以是多个)属性x1、x2：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所示。

表2 第一次迭代时的距离矩阵

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

图2 k-means聚类算法结果

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

3.2 改进后的k-means算法

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

具体流程为：

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

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

(3) 对于每个对象xi，设它当前属于类ξi，ξi类的中心为Ci，计算xi与Ci的 距离d(xi,Ci) 。如果d(Ci,Cj) ≥ 2d(xi,Ci)，则xi所在的类不变，否则，计算d(xi,Cj) ；如果d(xi,Cj) ＜d(xi,Ci)，则暂时将xi分配到ξi中，否则，xi所在的类不变。重复步骤(3)，直到所有i d处理完。

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

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

4 混合文本聚类算法

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

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

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

具体流程如下：

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

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

(3) 将文档集合 D 看成是一个聚类C= {c1, …ci, …cn} ，其中ci= {di}。

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

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

(6) 计算每两个聚类中心的距离d(ci,cj) 。

(7) 对于D中的每个文档di，设它当前属于类ξi，ξi类的中 心为ci，计 算di与ci的 距离d(di,ci) 。如果d(ci,cj) ≥ 2d(di,ci)，则di所 在的类不变，否则，计算d(di,cj) ；如果d(di,cj) ＜d(di,ci)，则暂时将di分配到ξj中，否则，di所在的类不变。重复执行步骤(7)，直到所有di处理完。

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

5 结论

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

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

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

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

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

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

[5]段小斌,陈基漓,张沫等.个性化推荐服务中用户兴趣模型研究[J].计算机与信息技术.2006.