基于GT4的聚类分析算法研究

　　摘要：本论文的研究视角是当前比较热门的两个问题：网格技术和数据挖掘技术。将网格计算和数据挖掘技术结合起来，开发基于网格的数据系统，借鉴传统聚类分析算法CLUQ和K_平均值算法，设计基于网格的全局和局部算法的Web Service形式。

　　1.引言

　　计算机网络技术的普及与应用给人们的生活带来了翻天覆地的变化，同时在网络上产生了大量杂乱无章的数据。而网格技术、Web技术的发展，为人们从分布的网络资源中寻找有价值的信息提供了新的技术支持，同时也产生了许多基于网格的数据挖掘系统。而数据挖掘算法又是决定一个数据挖掘系统性能的主要衡量指标。任何软件系统的设计都离不开算法，数据挖掘技术的执行效率也与数据挖掘算法有关，随着数据库技术与数据挖掘技术的成熟与发展，像分类、聚类、决策树、关联等等数据挖掘算法已相当成熟，可以研究借鉴现有数据挖掘方法、数据挖掘模式、数据挖掘流程，建立一个基于网格的数据挖掘系统。笔者以众多数据挖掘算法中的聚类分析算法为例，介绍基于GT4（Globus Tookit 4.0的简称，GT4的开发工具包（Java Web Service Core））的数据挖掘算法的设计过程。

　　聚类分析（Clustering Analysis）是一个应用比较广泛的数据挖掘算法，算法的理论研究与实践应用都已经很成熟，把这一成熟的理论应用于基于网格的分布式系统中，会大大提高数据挖掘的效率。本文主要研究如何将聚类分析的CURE（Cluster Using Representation）算法和K-平均方法算法应用于基于GT4数据挖掘系统中。

　　2.系统结构设计

　　基于GT4数据挖掘系统的数据源是分布式数据源，分布式数据源是指在物理上分布而逻辑上集中的数据源系统。在该系统中，处在这个网格中的每台计算机就是这个网格的一个节点，称之为网格节点。在众多的节点中，要有一个网格节点来控制和管理其他的节点，这个节点就叫做网格中心控制节点，决策支持都是由网格中心控制节点完成的。如果要完成某个数据挖掘任务，则可以由空闲的网格节点先按挖掘需求来完成本节点的挖掘任务，再由网格中心控制节点来汇总每个节点的数据挖掘情况。局部网格节点管理的信息具有局限性，涉及的范围较小，主要完成单个节点数据的管理，对局部的数据挖掘结果进行汇总分析，但是这些局部节点的数据与全局节点的数据又是有一定关联的。根据以上的分析可知，网格平台下的数据挖掘任务由全局数据挖掘与局部数据挖掘共同完成。

　　3.算法的Web Service设计

　　3.1 全局聚类算法的Web Service设计

　　网格环境下的全局控制网格节点与局部网格节点间的关系我们可以理解为上下层的关系，这样就可以借鉴基于层次的聚类分析算法，按照层次的自底向上的聚类方式，把全局控制节点当成是层次聚类的顶层。本课题全局聚类算法借鉴传统的利用代表点聚类算法CURE.

　　CURE算法将层次方法与划分方法结合到一起，选用有代表性的、固定数目的空间点来表示一个聚类。算法在开始时，每个点都是一个簇，然后将距离近的簇结合，一直到簇的个数为要求的K.首先把每个数据点即局部网格节点看成一个聚类，然后再以一个特定的收缩因子向中心收缩它们。

　　CURE算法的主要执行步骤如下：

　　（1）从数据源样本对象中随机抽取样本集，生成一个样本集合S;

　　（2）将样本集合S分割为一组划分，每个划分大小为S/p;

　　（3）对每个划分部分进行局部聚类；

　　（4）通过随机采样剔除聚类增长太慢的异常数据；

　　（5）对局部聚类进行聚类，落在每个新形成的聚类中的代表性点，则根据用户定义的收缩因子收缩或移向聚类中心；

　　（6）用相应的标记对聚类中的数据标上聚类号。

　　有了数据挖掘算法，就可以完成数据挖掘任务了。全局聚类算法的主要功能是响应用户的数据挖掘请求，将对应的请求发送给局部网格节点，将局部网格节点的挖掘结果整理输出。全局聚类算法Web Service资源的结构包括算法Web Service接口、算法资源属性文档、算法功能实现和算法功能发布四个部分。

　　利用传统的聚类算法完成全局的数据的并行挖掘重要的一步就是将全局聚类算法部署到GT4中，完成全局聚类算法的Web Service设计要经过过以下几步：

　　步：用WSDL（Web Service描述语言，是Web Service提供的XLM语言）来描述数据挖掘服务接口，该服务接口可以用Java来定义，利用Java-to-WSDL工具把Java定义的接口转为WSDL文件。

　　第二步：用Java编写全局聚类算法（CURE）代码；

　　第三步：用WSDD配置文件和JNDI（GT4自带文件）部署文件；

　　第四步：用Ant工具打包上面的所有文件，生成一个GAR文件；

　　第五步：向Web Service容器部署全局数据挖掘服务。

　　3.2 局部聚类算法的Web Service设计

　　局部聚类算法的主要功能是完成局部网格节点的数据挖掘任务，并把数据挖掘结果上传到全局控制节点。局部网格节点的数据挖掘任务与传统的单机数据挖掘任务类似，本课题局部聚类算法使用传统的聚类算法K-平均方法，以K为参数，把N个对象分为K个簇，簇内具有较高的相似度，而簇间的相似度较低[34].本论文的数据挖掘任务主要是由局部网格节点实现的，下面就详细的介绍K-平均算法的主要执行过程如下：

　　（1）从数据集中任意选择K个对象作为各个簇的初始中心。

　　（2）根据现有的簇中心情况，利用距离公式计算其他对象到各个簇中心的距离。（可选的距离公式有：欧几里、行德公式、距离公式、曼哈坦距离公式、明考斯基距离公式）。

　　（3）根据所得各个对象的距离值，将对象分配给距离近的中心所对应的簇。

　　（4）重新生成各个簇的中心。

　　（5）判断是否收敛。如果收敛，即簇不在发生变化，那么停止划分，否则，重复（2）到（5）。

　　K-平均算法是一个经典的聚类算法，将K-平均算法部署到GT4中，完成局部聚类算法的Web Service设计，部署方法与全局算法相似。

　　4.结论

　　基于GT4的数据挖掘系统中的数据挖掘服务资源有网格的中心控制节点（即全局节点）进行统一的管理，在局部网格节点挖掘过程中，根据其处理能力分配的数据集给局部节点，从而使整个系统的计算负载相对均衡。其数据挖掘系统的规模可随着服务的多少动态伸缩。当系统要增加新的局部挖掘节点时，只需部署局部Web Service资源即可。将网格应用到分布式数据挖掘系统中，建立一个基于网格的数据挖掘系统，必将使其在各个领域都得到广泛的应用。（作者：吕亚娟，王帅）