the_xml文档自动聚类研究guide_download

第 2 5 卷第 2期 2 0 0 6年 4月 情报 学报 V o 1 2 5 2 A p r i l ， 2 0 0 6 XML文档 自动聚类研究 潘有能 ( 浙江大学信息资源管理系 ，杭州 3 1 0 0 2 8 ) 摘 要 本文在文本聚类的基础上对 X M L 文档 自 动聚类进行 了研究， 对划分聚类法和层次聚类法进行了改进， 使之适合于 X M L文档聚类 ； 给 出了元素 比较法 、 边集 比较法和编辑距离法等三种计算文档间相似度 的方法 ， 并利用 实 际数据进行了测试和分析。 关 键词 数据挖掘文本聚类X M L Re s e a r c h o n XM L Do c u me n t s Cl u s t e r P a n Yo u n e n g ( D e p a t f m e n t o fI n f o r m a t i o n R e s o u r c e s M a n a g e m e n t ， Z h e j i a n g U n i i t y ， H t 咖u 3 1 0 0 2 8 ) Ab s t r a c t O n t h e b a s i s o f t e x t c I u s t e r t h e a u t h o r m a k e s a J l e x p l o r a t o r y r e s e a r c h o n X ML d o c u m e n t s c l u s t e r ， t h o u # t h e i mp r o v e me n t o n p a r t i t i o n c l u s t e r a n d l a y e r c l u s t e r ， ma k e s the m c a n U S e o n XML d ocu me n ts c l u s t e r Th e n， the a u tho r d i s c us s e s 8 0 me me tho d a b o u t XML d ocume n ts s i mi l a r i t y c Mc a fi o n Ke y wor d s d a t a mi n i n g ， t e x t c l u s t e r ， XML 1 前 言 X M L ( E x t e n s i b l e M a r k u p L a n g u a g e ， 可扩展标记语 言) 是近几年新发展起来的基于 I n t e r n e t 的元数据置 标语言， 自发布之 日起 ， X ML就 以其 良好 的可扩展 性受到业界的普遍欢迎和支持， 逐渐成为 we b上的 通用语言， 在数据交换 、 We b服务 、 内容管理 、 We b 集 成等方面得到了重要应用。 文本 聚类是数据挖掘 中的一项重要 内容， 它不 但可以提高信息检索系统 的查准率 和查全率， 还可 以用于组织搜索引擎返 回的结果， 自动 产生文本的 层次簇或类 ， 并利用这些簇或类来对新 文档进行归 类 。 X ML文本聚类的 目标和普通的文本聚类一样， 就 是将 X ML文 档集组 成不 同 的类 ， 使得 类 内文 档之 间的相似性尽量大， 而类 间的相似性尽量小。但是 由于 X M L文档和一般 的非结构化文档有着很大差 别 ， 我们需要在普通的文本聚类的基础上进行更深 层次 的研 究 。 2 X ML文本聚类技术 目前文本 聚类的方法主要有划分聚类法 、 层次 聚类法、 自组织映射法、 基于遗传算法的文本聚类法 等， 由于 X M L文档是一种结构化 的文本 ， 其语义信 息可以通过文档结构得 以描述 ， 主要是通过对 X ML 文档结构的分析 比较进行聚类 ， 所 以并不是所有的 文本聚类算法都适合于 X M L文本聚类， 在 自组织映 射法中， 主要是利用 自组织特征 映射法 ( S O M) 方法 收稿 日期 ： 2 0 0 5年 4月 2 9日 作者简介 ：潘有能， 男 ， 1 9 7 7年生， 博士 ， 讲师 ， 主要研究方 向为数据挖掘 、 信息 自动处理等。 1 ) 本文为浙江大学“ 曙光” 青 年项 目“ 基于 X ML的 We b日志挖掘研究” ( N o ： 2 0 5 0 0 0 - 3 6 2 2 2 1 ) 研究成 果。 维普资讯 2 1 6 情报学报 2 5 卷 生成词汇 聚类地图( Wo r d C l u s t e r M a p ) 和文本 聚类地 图( D o c u m e n t C l u s t e r M a p ) 。S O M算法可 以使词汇被 组织成有序的节点 ， 在概念上相近或相关的词汇会 落人 同一个或邻近的地图节点中。这种算法无法考 虑到 X M L文档的元素之间的关系， X M L文档的特征 向量不能简单地用其中所包含 的词汇来表示 ， 所 以 自组织映射 法不适合于应 用到 X ML文本 聚类 中。 基于遗传算法的聚类法主要用于可能解的数 目过多 以至于不能在可行的时间内通过确定的传统划分算 法验 证 的情况 ， 它采用 随机 方法 寻找最 优解 ， 在 变量 多 ， 取值范围大或无给定范围时 ， 难以精确确定最优 解的位置 ， 且其参数选择尚未有定量方法 ， 目前尚未 在文本聚类领域得到广泛应用 ， 所 以也不适合于应 用到 X M L文本聚类 中。下面我们 主要考虑划分聚 类法和层次聚类法。 1 )划分 聚类法 划分聚类法通过一个评估函数将文档集水平地 分割为若干个类。对于给定 的文档集 D= d ， ， d 2 ， ，d ， 划分聚类法的具体处理流程如下 ： ( 1 )确定要生成的类 的数 目 k ； ( 2 )按照某种原则( 可随机) 生成 k 个 聚类中心 作为聚类的初始中心点 S= 8 ， ， s 2 ， ， 8 ； ( 3 )对文档集 中的每个文档 d i ， 依次计算它与 各个中心点 S j 的相似度 s i m( d ； ， S j ) ； 并选取具有最大 的相似度的中心点 a r g n 础 s i m( d i ， 8 j ) ， 将 d i 归人 以 其为聚类 中心的类 C ； ， 从而得到 D的一个聚类 C= C l ， ， C k ； ( 4 )重新计算每个类的中心点 ； ( 5 )重复执行步骤( 3 ) 、 ( 4 ) 、 ( 5 ) ， 直至类 中心点 不再改变 ， 得到稳定的聚类结果。 在 X M L文本聚类 中， 可 以选择 X M L文档作 为 中心点， 这样计算 X M L文档和中心点之间的相似度 实际上就是计算两个 X ML文档之间的相似度。计 算 X M L文档之间的相似度的方法有多种， 因为在划 分聚类法和层次聚类法中都要用到 ， 所 以将在后面 专门介绍。每次将全部 X M L文档划分 到相应类别 中后， 都要重新计算每个聚类的中心点， 也就是要重 新挑选代表聚类中心点的 X ML文档 ， 假设 C： d ， ， ，d 是已划分的一个 X M L文档聚类 ， 我们可以通 过计算文档之间距离的平方和来挑选 出聚类 中心 点， 具体的计算公式为： 假设 d ； C ， d C ， O( d i ， d ) 为 d i 与 d 之间的 距离 ， 则有 S ( d i ， C )： O ( d ， d ) ( 公式 1 ) 对 C中所有文档进行计算后 ， 挑选出 S最小的 那个文档 M i n ( S ( d i ， c ) ) ， d i C ， 作为新 的聚类中心 点 。 划分聚类法的运行速度较快 ， 但必须事先确定 k的取值和初始 中心点， 而且初始 中心点的选择对 最终的聚类结果有较大影响。 2 ) 层 次 聚类法 层次聚类法是指对给定的文档集进行多层次的 分解 ， 直到满足某种条件为止。层次聚类法具体分 为 两 种 ：聚 合 聚 类 ( A g g l o m e r a t i v e )和 分 裂 聚 类 ( S p l i t t i n g ) ， 聚合聚类采取“ 自底向上” 的处理办法 ， 开始时 ， 每一个文本都组成一个单独的类 ， 在随后的 迭代过程中， 把那些相互邻近的类合并成一个类 ， 直 到所有 的文本组成一个类或者满足某个条件为止。 分裂 聚类 采取 “ 自顶 向下 ” 的处理 办法 ， 开始 时 ， 所有 的文本组成一个类 ， 在 以后的迭代过程 中， 再把一个 类分裂成几个更小的类 ， 直到每个文本都在单独的 一 个类中或者满足某个条件为止。 聚合聚类在文本 聚类中较为常用 ， 是一种主要 的文本聚类方法。对 于给定 的文档集 D= d “， d 一， d ) ， 聚合聚类法的具体过程如下 ： ( 1 )将 D中的每个文 档 d i 看作是一个具有单 个成员的类 C i = d i ， 这些类构成了 D的一个聚类 C= C l ， ， C i ， ， C ； ( 2 )计 算 C中每对 类 ( C ； ， C j ) 之 间 的相似 度 s i m( C i ， C j ) ； ( 3 )选取具有 最大 相似度 的类 对 a r g n s i m ( C i ， C i ) ， 并将 C 和 C i 合并 为一个新 的类 C =C i U C i ， 从而构成 D的一个新的聚类 C= C 一， C 一 ， l ； ( 4 )重复步骤 ( 2 ) 、 ( 3 ) ， 直到 C中只剩下一个类 或者达到一个终止条件为止。 该过程构造出一个树状结构 ， 其 中包含 了类的 层次信息以及所有类 内和类间的相似度 ， 聚合聚类 法是最为常用的聚类方法， 它能够 生成层次化的嵌 套类 ， 准确度也较高。但是在每次合并 出新的类时 都要比较所有类之间的相似度 ， 时间耗费比较大 。 类对之间相似度的计算可以分为两步， 首先计 算单个文档和类之间的相似度 ， 再计算总的相似度。 假设( C i ， C j ) 为一个类对， C i = d ； ， ， d ) ， C i = d i ， ，d ， S ( d i ， d i ) 为文档 d i 和 d i 之间 的相似度 ， 则 有 ： 维普资讯 2期 X ML文档自动聚类研究 2 l 7 S i m ( C i ， C j ) =S 2 ( d 。 ， d ) ( 公 式2 ) i = 1 = 1 3 相似度的计算 在前面介绍 的划分聚类 法和层次聚类法中， 都 需要计算文档之间的相似度 ， 对 于 X ML文档来说 ， 计算相似度的方法主要有元素 比较法 、 边集 比较法 和编辑 距离法 。 ( 1 )元素比较法 元素 比较法是指通过计算两个 X M L文档中共 有元素的数量占这两个文档中所有元素数量的比例 来反映文档之间的相似度。因为在 X ML文档中， 层 次高的元素( 离根元素更近的元素) 往往比层次低 的 元素( 离根元素较远的元素) 更能反映文档 的结构信 息 ， 在计算相似度时必须把元素所处 的层次考虑在 内。假设 T=( v ， T l ， T 2 ， ， T ) 是一棵文档树 ， 则 T的层次计算公式如下 ： ， f l + m - L e v e l ( )T =( V ， T - ， T 2 ， T n ) l 0 T ：( v ) ( 公 式 3 ) 在文档树中， 树的层次是指从根元素到最底层 的叶元素中最长的路径所具有的元 素的个数 ， 根元 素是树的开端 ， 根元素的层次等于树的层次 ， 其余元 素的层次依次递减。定义 z =L e v e l ( ) 为树 T的层 次 ， R为一个层次的元素和它下一个层次的元素 之 间的级差系数， T的层次权重为 R ， 其后代元素的层 次权 重 以 R 的 级 差 递 减 ， 第 层 的 层 次 权 重 为 R 卜 ， R的值越大 ， 就表示元素层次的影响在相似度 计算中越重要 ， 层次高的元素和层次低的元素相 比 较， 具有更大的影响。一般 可以取值 R=2 ， 表示上 ( TI ) 层的元素和下层的元素相比有加倍 的影响。 假设 E ( T ) = e 一 ， e 一 ， e ) 表示文档树 T中 包含 的所有元素 ， 给定两棵文档树 T ， ， 1 “ 2 ， C ( T 。 ， T 2 ) = C ， ， ， C 一， C ) 表示 T ， 和 T 2 共有元素的集合 ， 其中 C i =e l =e 2 k ， L e v e l C( c i ) =Ma x ( L e v e l ( e 1 j ) ， L e v e l ( ( e 2 ) ) ， C ( T ) = C 一， C 一， C ) 表示文档树 T 。 ， T 2 中非共有元素的集合 ， 则有计算文档树 T 。 ， T 2 之 间相似度的公式如下 ： S i m( T ， 1 “2 )= L e v e l C ( c ) i = 1 L e v e l ( c 。 ) +L e v e l C ( c i ) i = 1 i = I ( 公式 4 ) 图 1 是两棵文档树 T 。 ， T 2 ： 根据公式 4 ， 图 1中两棵文档树之 间的相似度 如 下 ： ， n S i m( T 1 ， 1 “2 ) = L e v e l C ( c ) i = 1 L e v e l ( c ) +L e v e l C ( c i ) i = I ：； 5 6 ： 0 7 3 7 ， 0 ( 2 )边 集 比较法 边集 比较法是指通过计算两个 X ML文档树 中 相等的有向边的数量占这两个文档中所有有向边数 量的比例来反映文档之间的相似度。 有向边 给定一个文档树 T ， v 。 和 v 是其 中有 父子关系的两个节点 ， 则将 v ， 和 v 之间关系称作有 向边 ， 记为 v 一 v 2 。 边集 边集是指文档树中所有有向边的集合 ， 记 为 R ( T ) 。 假 如有 两组有 向边 v l v 2和 v 3 一 v 4 ， 且 v l =v 3 ， v2 =v4 ，则称 v 1 一v 2 和 v 3 一v 4是相等的。 围 1 文档树 相似 度计算 ( T2 ) 维普资讯 2 l 8 情报 学报 2 5卷 对于 图 l ， R ( T I ) = R e s u n l e N a m e ， R e s u m e P h o n e ， P h o n e Ho me， P h o n e Mo b i l e， Re s u me - - Ad d r e s s ， Re s u me- - E d u c a t i o n E d u c a t i o n S c h o o l ，E d u c a t i o n Ma j o r ， R e s u m e - - E m a i l ； R ( T 2 ) = R e s u m e N a m e ， R e s u m e S e x ， R e s u m e - C o n t a c t l n f o， Co n t a c t l n f o - - P h o n e， P h o n e Ho me， P h o n e Mo b i l e，C o n t a c t l n f o Ema i l ，Re s u me E d u c a t i o n， E d u c a t i o n - - S c h o o l ， E d u c a t i o n - - Ma j o r ； 显而易见 ， 两个 文档树中的相同有 向边在这两 个文档的边集中所 占的 比例越大 ， 这两个 文档树的 相 似度就 越 大 ， 文档 之 间的相似度 的计 算公 式如 下 ： s i m ( T I , T z )= ( 公 其中， T I 和 T 2 表示两个文档树 ， R ( T 。 ) 和 R ( T 2 ) 是这两个文档树的边集 ， R ( T 。 ) n R ( T 2 ) 为两个边集 中相 等 的有 向边 的集合 ， I R ( T I ) n R( T ： ) I 为两 个边 集 中相等 的有 向边 的 数 目。R( T I ) U R( T ： ) 为两 个 边集 中所有 的有 向边 的集合 ， I R ( T 。 ) UR ( T 2 ) I 为两 个 边 集 中所有 的有 向边 的数 目。 按照这个公式， 可以计算 出图 l中两个 文档树 相 互之 间 的相似度 ： s i mc T 2 ) = ：一6： O 4 6 2 1 3 。 ( 3 )编辑距 离法 编 辑距离法 是指 利用 编辑距 离来 衡量 两棵树之 间的相似度 ， 其基本思想是将两棵树之 间的距离定 义为利用编辑操作实现一棵树到另一棵树所需的代 价， 显然， 距离和相似度之间成反 比关系 ， 树之间的 距离越小 ， 则相似度越大。树之间的编辑操作主要 有 三种 ： 插入 将一个 子树 插入 到 目标 树 中， 表示 为 I n s e r t ( A， T 。 ) ， T=( v ， T 。 ， ， T 一， T n ) 为 目标树 ， A为待插入的子树， i 表示将 A插入到 T的子树 T ： 的后面 ， 插入后生成的新树为 T =( v ， T 一， ， I 1 i ， A， + 。 ， ， T J ) ； 删除 在 目标 树 中 删 除指 定 子 树， 表示 为 D e l e t e T ( T i ) ， T=( v ， T I ， ， ， ， 1 r n ) 为 目标树 ， 为待删除的子树 ， 删除后生成的新树为 T =( v ， T I ， ，T i l ，T 。 + l ， ， T J ) ； 更新将 目标树 中指定节点的标签进行更新， 节点下面的子树保留原状 ， 更新表示为 R e l a b l e ( U ) ， T=( v ， T l ， ， T i ， ， T 。 ) 为 目标树 ， U为新的标签， 更新后生成的新树为 T=( U ， T I ， ， ， ， 1 r n ) ； 每个编辑操作都有一个代价， 令 为一个代价 函数， 它为每个编辑操作赋予一个非负整数作为代 价值， 记为 ( U ) ， 其 中 U为一个编辑操作 ， T I ， T 2 是 两棵 X M L文档树 ， s为从 T I 到 T 2的编辑操作 的序 列 ， S = S ， ， s 一， S ) ， 则 s的代价是这些编辑操 作的代价的总和 ， 即： t l ( S )= ( s ； ) ( 公式 6 ) 从文档树 T I 到文档树 T 2 可能有多个能够实现 转换的编辑操作的序列， 定义编辑距离为将 T I 转换 成 T 2 的最小的操作序列的代价 ， 记 为 E D( T 。 ， T 2 ) ， 即 ： n E D ( T I ， T 2 ) =M i n ( ( S ) ) =M i n ( ： ( s ) ) ( 公 式 7 ) 在编辑操作中， 插入和删除的对象都是子树 ， 最 简单的子树就是没有任何子元素的单个节点 ， 复杂 的子树可能有子元素 ， 其子元素可能还有子元素， 为 了对此类操作进行规范， 插入和删除操作必须遵循 两 个原 则 ： ( a )待插入 的子树必须是 来源树的子树 ， 即 cT ( S ) ， 其中 为待插入的子树 ， T ( s ) 为来源树 ； 待 删除的子树必须是 目标树 的子树 ， 即 T i cT ( D) ， 其 中 为待删除的子树 ， T ( D ) 为 目标树。 ( b )待插入的子树及其后代树在此次插入操作 前不能有其他的编辑操作， 同样 ， 待删除的子树及其 后代树在此 次删除操作前也 不能有其他 的编辑操 作 。 原则( a ) 规定插入 和删除操作的处理对象必须 包含在来源树或 目标树 中， 这样 才能保证来 源树 到 目标树的正常转换 ； 原则( b ) 防止 了重复的编辑操 作 ， 保证了单个子树中编辑操作 的代价最小。 4 实验结果与分析 为了验证 X ML文档 自动聚类的准确性 ， 对不同 的相似度计算方法进行 比较 ， 作者用C + +实现 了上 述三种计算相似度的方法： 元素比较法 、 边集比较法 和编辑距离法。在聚类算法方 面， 作者采用了划分 聚类 法。实 验 硬 件 平 台： C P U A M D 2 8 0 0+， 内 存 维普资讯 2 期 X ML文档 自动 聚类研究 2 1 9 表 1 聚类准确性测试结果元素 比较法 、类别( D 1 1 ) ) 文档数 、 P r o c e e d i n g s - P a g e d t d P l a y d t d O r d i n a r y l s s u e - P age d t d S i g r a o d - R e c o r d di d 聚类结果 l 3 2 5 2 9 1 9 已知文档数 l 6 2 5 2 7 1 8 聚类准确率 8 1 3 1 0 0 9 3 1 9 4 7 聚类准确率( 总计 ) 9 6 5 表 2 聚类准确性测试结果 边集 比较法 、类别( D T D ) 文 档 数、 P ro c e e d i n g s - P ag e d td P la y d t d O r d in a r y l s s u e P ag e d td S ig m o d - R e c o rd di d 聚类 结果 1 4 2 5 2 9 1 8 已知文档数 1 6 2 5 2 7 1 8 聚类准确率 8 7 5 l 0 0 9 3 1 l 0 0 聚类准确率 ( 总计 ) 9 7 7 表 3聚类准确性测试结果编辑距离法 0 ( D T D ) 文 档 数、 P r o c e e d in g s - P ag e d t d P la y d t d O rd in a ry l s s u e - P ag e di d S ig ra o d - R e c o rd di d 聚类结果 l 6 2 5 2 7 l 8 已知文档数 1 6 2 5 2 7 1 8 聚类准确率 1 0 0 1 0 0 1 0 0 1 0 0 聚类准确 率( 总计) 1 0 0 D D R 4 0 0 5 1 2 M， 操作系统 Wi n d o w s 2 0 0 0 S e r v e r 。实验 分 3组 ， 第 1 组采用元素比较法计算 X ML文档之间 的相似度 ， 第 2组 和第 3组分别采用边集 比较法和 编辑距 离法计算相似度。实验数据来 自于 S i g m o d X ML 数据集 和莎士 比亚戏剧 X ML数据集 引， 在 实验中， 已知 X M L数据 集中的文档分属于 4类 ( 根 据 D T D确定) ， 每一类中的文档数 目也已计算出来 。 实验参数及结果如表 1 至表 3所示。 从表 1 到表 3的测试结果可 以看 出， 这 3种计 算相似度的方法准确性都是比较高的。作者对表 1 和表 2中的错误聚类文档进行了进一步的调查 ， 发 现主要原因在于将某些会议论文聚类到期刊论文的 类别中， 因为这些会议论文的著录项不全 ， 没有会议 名称或会议时间等。 5 结束语 X M L文档 自动聚类是 当前文本 挖掘研究 中的 一 个全新领域 ， 由于其处理对象是结构化的 X ML文 档 ， 所以具体的聚类方法和一般 的文本聚类有着较 大差别。特别是 X M L文档的语 义信息 可以通过文 档结构得以描述 ， 因此可以将 X ML文档的结构和 内 容相结合， 增加文档 间相 似度 比较 的准度 和精度 。 目前 ， 国内外关于这方面的研究还不多 ， 相信在不久 的将来 ， 随着 X ML应用的不断增多和数据挖掘研究 的不断深入： X ML文档 自动聚类研究能够得到更大 的发 展。 参考文 献 1 Ri c h i Na y a kRe b e c c a W i u& An t o n To n e vDa m Mi mn g a n d Xml Do c u me n t s Pr o c e e din g s o f t he 2 O O2 I n t e r na t i o n a l 维普资讯 2 2 0 情报学报 2 5卷 2 3 4 5 6 7 Co n f e r e n c e o n I n t e me t Co mp u t i n g，2 0 0 2 An d r e w N i e r ma n H V J a g a d i s h E v a l u a t i n g S tr u c t u r a l Si mi l a r i t y i n XML Do c u me n t s We bDB 2 0 0 2 El i s a B e r t i n o，Gi o v a n n a Gu e r r i n i ，Ma r c o Me s i t i ，Lu i g i To s e t t oEv o l v i n g a S e t o f DT Ds Ac c o r d i n g t o a Dy n a mi c S e t of XML Do c u me n t sEDBT Wo r ks h o p s，2 0 0 2 E l i s a B e r t i n o，G i o v a n n a Gu e r r i n i ，Ma r c o Me s i t i Ma t c h i n g a ll XML Docu me n t a g a i n s t a Se t of DTDs I S MI S，2 0 0 2 Ka i z h o n g Zh a n g，Ri c k S t a t ma n，De n n i s S h a s h aS i mp l e Fa s t Al g o rit h ms f o r the E d i tin g Di s t a nc e Be t we e n Tr e e s a n d Re l a t e d P r o b l e m s S I A M J o u r n al o n C o m p u ti n g ， 1 9 8 9 ， 1 8 ( 6 ) ： 1 2 4 5 l 2 62 Yu a n Wang ，D a v i d J D e Wi t t ，J i nY i C a i XDi ff ：An Eff e c ti v e Ch ang e De t e c ti o n Al g o r i thm f o r XML Doc u me n tsI n th e I n t e rna ti o n al C o n f e