基于频繁关联标签序列的XML结构相似度度量方法

摘要

本发明公开了一种基于频繁关联标签序列的XML结构相似度度量方法，解析XML文档集C得到标签序列数据库TSDB；从TSDB中挖掘所有的频繁标签序列集合FTS；从中选出极大频繁标签序列集MFTS；转化得到新的数据库TSDB’；从中挖掘闭频繁关联标签序列集合；将TSDB’中的任意一个文档表示为其所包含的闭频繁关联标签序列集合，从而计算文档集合C中任意两个文档之间的结构相似度。本发明可以提高聚类结果的准确率。

主权项

1.一种基于频繁关联标签序列的XML结构相似度度量方法，其特征在于包括下述步骤：1)预处理：解析XML文档集C中所有的XML文档，将每个XML文档的结构建模为一棵有序标签树，树中的每个节点表示文档中的一个元素，节点使用元素名来标记，称作标签；从所有文档中抽取的所有标签构成的集合称为标签集；将XML文档的结构都表示为标签序列的集合，得到标签序列数据库TSDB；所述的标签序列是指由标签集中的多个标签构成的有序列表，标签的顺序为XML文档对应的标签树中从根节点到叶子节点的路径所经过的顺序，标签序列α可形式化地表示为：<a₁，a₂，L，a_n>，其中a_i为标签集中的一个标签，其中所包含的标签的个数称为标签序列的长度，长度为l的标签序列称为l-标签序列；2)挖掘频繁标签序列：从TSDB中使用频繁序列模式挖掘算法挖掘所有的频繁标签序列集合FTS；所述的频繁标签序列是指对于给定的最小支持度阈值δ，如果标签序列α在TSDB中的支持度大于等于δ，则称α在TSDB中是频繁标签序列，0＜δ≤1；所述的标签序列α在TSDB中的支持度是指在TSDB中支持α的文档的数目与TSDB中所有文档数的比率，记为support(α)；所述的支持α的文档是指在该文档中存在一个标签序列β，使得β包含α；所述的标签序列β：<b₁，b₂，L，b_n>包含标签序列α：<a₁，a₂，L，a_m>是指存在整数序列i₁＜i₂＜L＜i_m，使得L，记作也称α是β的子标签序列，或β是α的超标签序列；3)极大化：从FTS中选出极大频繁标签序列，得到极大频繁标签序列集MFTS；所述的极大频繁标签序列是指对于标签序列α，在TSDB中不存在它的超标签序列也是频繁的；4)转换数据库：对于TSDB中的每一个文档中的每一个标签序列α，如果MFTS中存在它的一个子标签序列，则将α用该子标签序列代替，如果不存在，则删除α，全部处理完后即可得到新的数据库TSDB’；5)挖掘闭频繁关联标签序列：从TSDB’中使用闭频繁项集挖掘算法挖掘所有的闭频繁关联标签序列构成的集合FATS；所述的关联标签序列是指标签序列的集合，对于该集合中的任意标签序列α，集合中都不存在另外一个标签序列β，使得β包含α或者α包含β；所述的频繁关联标签序列是指对于给定的最小支持度阈值δ，如果关联标签序列γ在TSDB’中的支持度大于等于δ，则称关联标签序列γ在TSDB’中是频繁关联标签序列；0＜δ≤1；所述的关联标签序列γ在TSDB’中的支持度是指TSDB’中支持γ的文档的数目与TSDB’中所有文档数的比率，记为support(γ)；所述的支持关联标签序列γ的文档是指对于γ中的任意标签序列α，该文档支持α；所述的闭频繁关联标签序列γ是指γ在TSDB’中是频繁的，且不存在它的真超集η，使得它们在TSDB’中支持度相同；6)文档表示：对于TSDB’中的任意一个文档d_i，将其表示为其所包含的闭频繁关联标签序列的集合，即d_i＝{fats|fats∈FATS∧d_i supports fats}；7)结构相似度计算：利用公式$\mathrm{sim}(d_i,d_j)=\frac{|d_i\cap d_j|+\left|p_j^i\right|+\left|p_i^j\right|}{|d_i\cup d_j|}$计算文档集合C中任意两个文档d_i和d_j之间的结构相似度sim(d_i，d_j)，其中：