XEdge：Clustering Homogeneous and Heterogeneous XML Documents Using Edge Summaries

这是一篇08年发表在ACM上的，由于在看聚类方面的文章而这篇文章中有对边的处理，就简单看了一下。这篇文章中，作者提出了一种标准的将同质和异质的XML文档进行聚类处理的算法，它是通过修改距离矩阵（Distance Metric）来抽取同质和异质文档的特征，经过实验验证，该算法优于最近的聚类文章。

一、Backgroud

目前XML文档聚类有两种方向：content和structure。Content方向通过距离考虑两个文本节点的相似性，而structure方向考虑的是Element之间的结构关系。有一篇近期的论文，提出了一种紧密的等级结构（level structure），它是根据XML文档每层节点的总结。并且定义了一种适合的距离矩阵（Distance Metric）来聚类异质XML文档，他们通过应用一种水平等级的聚类算法来实现。这个方法的主要缺点是：不是一种标准的聚类框架，同时处理同质和异质的文档。为了解决这个问题，作者提出了LevelEdge，一个XML文档的结构化表示，它是依据对边的总结和一个合适的距离矩阵得出的。这篇文章的主要贡献在于：

（1）它是XML文档的紧密表示，通过对每一层独立边的总结，能够保留大部分的结构信息。

（2）根据合适的距离矩阵，同质和异质文档可以很好的区分。

（3）XML文档的有效的聚类方法的实现。

（4）每一个聚类通过一个紧密的聚类代表来表示，并且能够总结XML文档中的特征和特点。

二、LevelStructure和LevelEdge的比较

LevelStructure为每层的唯一的XML节点进行分组处理，因此每层均形成一个向量，即每层都包括一个链表（包含了一系列的唯一节点）。如下图（b），是对图（a）的LevelStructure表示。每个节点标签下面的数字代表的是节点的数字编码，他们被用来在LevelStructure中。虽然LevelStructure紧密并且size相对的比较小，它还是有缺点的，即在聚类过程中可以产生完全错误的结果，也会丢失结构化的关系（父子、祖先与后代）。

在LevelStructure中保留的是同层节点之间的结构化信息，然而，不同等级节点之间的关系却丢失了。因此，有可能同一个LevelStructure却对应两个结构不同的XML文档。如下图，两个XML文档包含了相同的唯一节点在同一层次上，但是节点之间的子孙关系确实不同的，然而这两个文档的LevelStructure的却被总结成相同的。因此，LevelStructure在聚类同质或是异质的XML文档时不是有效率的。

三、LevelEdge：总结每层的边

LevelEdge对每层的唯一边进行分组，也是生成一个等级的向量，每一个等级都是一个链表包含了各种的唯一边。每个唯一边通过两个独立节点确定。如下图c，是对图a的LevelEdge表示。例如，Poster-Author被编码为5，而Paper-Author被编码为3.因此LevelEdge只包含了两侧的信息，因为第三层没有边。通过下图我们可以对比LevelEdge和LevelStructure的不同。

LevelEdge表示的重要特征可以被应用在定义一个合适的距离矩阵，进而可以用来聚类一系列的同质和异质的XML文档。下面是定义的两个LevelEdge之间的相似测量度，其中L1和L2是两个LevelEdge表示，N1和N2分别是相应的等级，a是一个正数，用户定义的权重。m=min(N1,N2)，并且M=max(N1,N2)，ci代表的是第i层相同唯一边的个数（L1和L2），tj代表的是第j层总共的唯一节点的个数，具体如下：相似度变化是0到1，0代表是完全的结构不同，1代表的是完全的结构相似。

下图是对两个同质同质文档进行相似度计算的例子：

对于异质的两个XML文档，可能在不同的等级拥有相同的边，即对于边e，在文档1中是在等级i，在文档2中是等级j。因此，相似度需要改进，不是去测量想同等级的想同边的个数，而是去测量不同等级匹配边的个数。具体定义如下：

下图是对两个异质同质文档进行相似度计算的例子：