基于改进k-medoids算法的XML文档聚类

冯少荣，潘炜炜，林子雨

(厦门大学信息科学与技术学院，福建厦门361005)

1 概述

XML由于其具有通用性、可扩展性、易用性、自描述性、异构性和开发性等特点［1-2］，已成为Web上通用的数据表示和交换格式。随着XML文档数量呈现出爆炸式的增长，人们迫切地需要从这些文档中获取相应的信息知识。XML文档的自动聚类，不仅可以增强网络中XML文档的组织性，同时还能从海量的XML文档中发现未知、隐含的知识和文档间的联系［3-5］，具有重要的研究意义。由于XML文档除了一些文本内容之外，还具有元素父亲节点、子孙节点嵌套等结构特征，因此传统文档聚类算法并不适合于XML文档的聚类。目前对XML文档的聚类，主要有 k-means(均值)［6］和 k-medoids(中心点)［7］2种基于划分的方法。由于XML文档数据集包含一个个离散的对象，而k-means的均值并不能真正反映整个簇的实际情况，也没有实际的意义。同时k-means算法对孤立点十分敏感，相比之下，kmedoids采用某一个具体对象作为聚类中心，很好地解决了k-means对孤立点敏感这一问题。同时，k-medoids算法具有划分简单、执行时间快的特点，其操作也适合于XML文档聚类。因此，k-medoids在XML文档聚类中得到了广泛的应用。

在基于划分的文档聚类中，一个最基本的问题是要确定聚类的个数k。这样对算法的使用造成了很大的不便，且无法通过样本的特征自动地确定聚类个数。此外，基于划分的聚类、初始中心点或者质心的选择，对整个聚类过程和聚类结果也有较大的影响，不合理的初始中心点选择容易使得算法得出局部最优解。……