基于ALCIF描述逻辑的Web页面聚类

富豪，邓立国

（沈阳师范大学数学与系统科学学院，沈阳 110034）

在Web 页面聚类过程中为了能有效处理标签内容以及标签内容之间的联系，选用ALCIF 描述逻辑表示方法来对Web 页面信息进行抽取与存储，并对抽取到的知识内容进行约减，从而实现对Web 文档的降维，以此节约聚类时间。最后用实验证明这种知识表示方法对于Web 页面聚类的有效性。

Web 页面聚类；ALCIF 描述逻辑；K-means

0 引言

国外描述逻辑的发展由描述逻辑工作组进行推进，最近两年从描述逻辑工作组的特邀报告及其所展示的成果来看，描述逻辑的重点始终在本体研究和语义网上面。总的来看描述逻辑的大部分研究还处在理论方面，Renata Wassermann 博士使用描述逻辑在OWL上进行实践，拉近了描述逻辑理论和实践的距离。国内对于描述逻辑的研究有申宇铭教授的文献[8]，提出了ℰℒ⇁模型关系并给出表达定理，提高了描述逻辑的表达能力。除此之外张富博士在文献[9]中实现了一个原型工具，能够自动将XML 转化成本体，然后利用这些本体进行XML 知识的推理。

随着十几年来互联网的快速发展，网页数量也开始激增，根据我国最新的《41 次中国互联网络发展状况统计报告》来看，我国的网站数量已经达到了533 万个[1]，如何快速又准确地返回搜索结果给搜索引擎带来不小挑战。

描述逻辑是知识表示语言的一种统称，具体有多种形式，其中ALC 是最基本也是最简单的描述逻辑形式。ALC 有很多的变型，包括，ALCF、ALCN、ALCIF、ALCIQ 等，其具体推理复杂性可参考文献[2]。另外SROIQ、ℰℒ、DL-Lite 等也属于描述逻辑，其中W3C 所推荐的OWL2 的直接语义是根据SROIQ 扩展而来。目前由于本体语言（Ontology Language）的发展和Web本体语言（OWL）的广泛使用，描述逻辑及其各种推理算法也得以快速发展和广泛使用。本文根据Web 页面数据的半结构化特点采用ALCIF 描述逻辑对数据知识进行表示。

Web 页面内容虽然包含多种多样的数据，如声音、文字、视频等，但是具有一定的标签结构，标签里面含有结构信息，而且两个对应的段落标签之间含有文本内容信息，传统的聚类技术大多采用抽取标签里的数据信息进行聚类，例如DOM 解析树的方法和SAX 方法都忽略了段落标签里面的文本内容信息，在这种方法下进行文档相似度度量显然存在一定问题。本文提出的基于ALCIF 描述逻辑的Web 页面信息表示方法能够全面考虑HTML 标签结构信息和文档内容信息，对于保留各项细节方面有很大优势。

本文提出的基于描述逻辑的Web 页面聚类方式，在保证速度的同时，由于使用了描述逻辑使得聚类结果也更加准确，同时聚类结果的可解释性也得到提高。

1 描述逻辑

1.1 描述逻辑概念及应用

描述逻辑是基于概念的知识表示方法，是一阶谓词逻辑的一个可判定子集，与一阶谓词相比，描述逻辑可读性更好[3]。Attributive Language with Complements（简称ALC）是基本的描述逻辑，本文采用的ALCIF 描述逻辑在ALC 的基础上增加了角色反（Role Inverse）和功能角色（Functionality Role）。

描述逻辑广泛应用于知识表示、语义网（Semantic Web）、推理机以及人工智能等领域。

1.2 ALCIF描述逻辑知识库

为了便于知识表示和理解，以及考虑到XML 在Web 中扮演的关键角色，采用XML Schema 表示方法对Web 页面进行结构和内容表示。这一过程所使用的描述逻辑定理如下：

（1）（ℛ-）I={＜x，y ＞|＜y，x ＞ ∈ ℛI} （角色反）

（2）（C⊓D）I=CI∩DI（交）

（3）（C⊔D）I=CI∪DI（并）

（4）（¬C）I=ΔICI（否）

（5）（∃ℛ.C）I={a|∃b.＜a，b ＞∈ℛI并且b∈CI} （存在限定）

（6）（∀ℛ.C）I={a|∀a.＜a，b ＞∈ℛI并且b∈CI} （全称限定）

描述逻辑为概念和角色的结合，两者由构造子经简单的概念和角色来构造复杂的概念和角色，概念对应于逻辑中的一元谓词，角色对应于二元谓词，构造子决定语言的表达能力，表达能力越强，相应对的构造子越复杂。在描述逻辑中，每个句子对应一个逻辑表达式。

Web 页面也称为HTML 页面，其包含内容丰富，因此具有一定复杂性。为了将HTML 的结构和内容都保留下来，在数据抽取的时候使用了XML 格式文件的XSD（XML Schema Definition）文件定义思想。通过XSD 这一结构来组织HTML 页面内容。一个.xsd 文件截图如图1 所示。

图1 XML Schema代码片段截图

使用描述逻辑进行推理所基于的知识库里包含两种子库，一种是TBox，包含了HTML 的各种术语即标签名称，另一种是ABox，所包含HTML 的具体属性断言。知识库表示为К=＜TBox，ABox＞。TBox 是一个有限集合，TBox 通过概念描述的定义构造，里面包含术语知识TBox 通常由具有有限个包含关系的数学结构集合表示。

代码1：HTML 的TBox。

将图1中的HTML代码与所对应的ABox 模型里面包含的是扩展知识是这样的，这种扩展知识通常也称作断言知识如代码2：一个HTML 的ABox 模型S'（与代码1 对应）。

知识库К被表示为ABox 集合（代码2）和TBox 集合（代码1）两种形式，需要注意的是这里的ABox 和TBox 集合里面的元素未被全部列举出。

2 基于知识库模型的数据抽取

HTML 标签知识库通过ABox 模型S'建立，并在描述逻辑知识库中存储了模式表示的实例，现在就可以使用描述逻辑推理来对XML 模式表示进行推断。下面将HTML 对应到知识库过程进行正确性验证，如图2 所示。在这一过程中知识库被不断扩展，以适应XML Schema 带来的数据增量式拓展。

使用Python 工具对HTML 数据内容进行抽取，抽取的内容包含页面名称、标签名称还有其它标签里的文本内容，如title 标签、字号标签里的内容以及段落标签p 里的全部内容，尤其段落标签p 可能包含了大段的文本内容。再用描述逻辑知识库对大段的文本内容进行缩减形成若干个属性，通过XML Schema 将标签数据联系起来。

根据HTML 文件知识库的表示方法，将HTML 文档内容按照ABox 进行组织。组织后的HTML 文档中P 标签里面的文本内容由TBox 验证其中的包含关系将文本内容进行缩减。然后将抽取文本保存在文本文件中。将文本内容映射到知识库中时，得到一个文档的特征概念集合T={t1，t2，t3，…，tn}，经过TBox 包含关系处理后得到的是一个简化的概念集合T’，这一过程会极大地降低文本数据维度。在第4 部分直接对这些HTML 文件进行相似度计算。

在HTML 网页中title 标签和某些文本内容相互联系，可能是和文件内的，也可能和其他文件有所关联，尝试着使用描述逻辑找出其中的关系。例如大学里Jon Damon Reese 教授的个人主页，尝试找出里面J D Reese 教课的课程名，然后有哪些学生选了J D Reese的课，从而建立一种关联关系并在聚类中考虑到这种关系。

3 文档向量与相似度计算

在第3 部分进行了HTML 文档内容提取，并将抽取的数据内容保存在知识库中。通过特征项与知识库进行匹配化简，得到一个新的向量T’{t1，t2，t3，…，tm}（m≤n）。

传统的VSM 模型将文本空间看做一个有一组正交词条表示对的向量空间，其中每个文本表示的规范化特征向量V（d）=（t1，w1（d）;t2，w2（d）;…tn，wn（d）），tn为词条项，wn（d）是tn在d 中的权重。TF-IDF 是一种常用的词条权重确定方法。这里不考虑同一文件中词出现的先后顺序和频率，即要求同一ti不重复出现，这时可以把t1，t2，…，tn看作一个具有n 维的坐标系，将权重wn（d）看作坐标值，这样一个文档就被表示为一个n 维的坐标向量。V（d）=（w1，w2，…，wn）称作文本d 的向量空间模型。其中每个词条的权重计算如下：

其中D 是HTML 文档集，d 表示任意一个HTML文档，t 为一个文档中的词，tf（d，t）为词t 在文档d 中出现的频率，|D|为文档集的总数，tf（t）为词t 在HTML 文档集中出现的次数，那么tfidf（d，t）就表示词t 在文档d中的权重。

由于需要匹配知识库，从而判断包含关系，进而缩减一个文档的维度。因此会得到一个新的权重计算公式：

其中nwi为概念c 在表示文档di时的权重，twk为匹配知识库前根据TF-IDF 计算得到的权重，其中r 为：

通过新的权重计算公式可以得到一个文本的语义表示模型，每一个HTML 文本可以表示成V（d）=（nw1，nw2，…，nwn），若存在包含关系则V（d）=（nw1，nw2，…，nwm）。

向量计算公式参数设置如下：

tfidf_vectorizer = TfidfVectorizer（max_df=0.7，max_features=200000，

min_df=0.1，stop_words='english'，

use_idf=True，tokenizer=tokenize_and_stem，ngram_range=（1，3））

4 K-means算法

使用传统的K-means 算法需要先确定聚类点的数目，虽然不符合聚类的不确定性特点，而且K-means 算法初始簇中心点的选择具有较大随机性，但是由于K-means 算法的易用性以及可在大数据级上应用而被广泛接受。K-means 算法的随机性可能导致最终的聚类结果不稳定，两次运行结果存在差异，针对这一点指定同一个聚类初始簇中心即可完美解决。王勇等在聚类之前对数据进行分层以此来获得聚类数量的上限，快速确定聚类范围解决了K-means 聚类算法无法确定最佳聚类数目的问题[5]。邵伦等通过将样本数据映射多维网格中，然后将样本数最多的网格作为聚类过程中的初始网格然后进行K-means 聚类，这种方法很大程度上解决了容易陷入最优解的问题[6]。本文则选用K-means++算法在初始簇聚类中心点的选择上给与了优化。

4.1 算法的基本思路

K-means++算法在簇中心点的初始化过程中的基本原则是各个簇中心点间的相互距离尽可能远，这样能在一定程度上解决聚类过程中随机初始各个簇中心点所带来的弊端。算法首先随机选取一个数据（n=1）点作为第一个聚类初始点，其次选取距离前n 个数据点较远的数据点为第n+1 个初始簇中心点，计算样本与聚类中心点距离为[7]：

4.2 算法流程

输入：数据集T，簇数量K。

输出：划分为k 个簇的数据集T。

算法过程描述：

（1）从T 中随机选择一个数据点作为第一个簇中心点；

（2）选择样本与簇中心点距离较远的点作为下一个簇中心点；

（3）重复（2）直到K 个簇初始中心点都被确定；

（4）使用K-means 算法计算调整簇中心点的位置；

（5）输出具有K 个簇的数据集T。

5 实验环境及结果

实验硬件条件是处理器是英特尔酷睿i5-4200U，硬盘用的东芝5400 转的500G 机械硬盘，内存为海力士4+8G 的DDR3L，内存频率为1600MHZ。软件上使用Python 3.6 版本，数据集采用的是WebKB。

聚类之前使用Tidy 对数据集进行了规范化处理，提取XML 的XSD，然后根据谓词逻辑中包含思想用Gensim 的Word2Vec 训练词向量，对标签关系进行学习，形成特定的模型。之后使用算法结合得到的模型对WebKB 数据集进行聚类，聚类时也能更好地解释Web 页面聚类结果，当K=8 时聚类结果如图3 所示。

图3 Python实验截图

6 结语

本文提出的在Web 页面聚类中使用ALCIF 描述逻辑的方法对HTML 标签结构关系进行联系，根据TBox 文本知识表示方法可以降低HTML 的数据维度，通过实验证明将描述逻辑用于Web 文档的知识表示从而精简文档构造语义联系并发现其中的关联关系是合理且有效的。未来的工作是考虑将运算规则引入到描述逻辑关系中，使得P 标签内的大量文本一些复杂的逻辑能够进行约减，从而帮助Web 数据降低维度，节省聚类时间。