分段文档分类：问题与解决方案

# 分段文档分类：问题与解决方案 ## 1. 引言 文本分类问题是人工智能领域的重要问题之一。近年来，机器学习技术发展迅速，被广泛用于解决该问题。许多自动分类器，如朴素贝叶斯、决策树、基于规则的分类器、基于实例的分类器和支持向量机等，在处理普通文本文件时已被证明是有效的。这些分类器通常将文档视为词袋。 随着互联网资源的蓬勃发展，像 XML 文件这样的结构化文档在万维网上发挥着重要作用。其中，很多文档结构简单，可将其分割成不同部分，例如一篇论文文档可分为标题、摘要、引言和正文等。我们将这类文档称为分段文档，它们在许多网站上被广泛用作在线资源（如新闻、服务、产品、书籍等）的描述性元数据。 虽然可以将分段文档视为普通文本，使用传统模型进行分类，但这种方法忽略了文档中某些文本在分类时应具有更高权重这一重要事实。例如，论文标题中的文本通常更为重要，有时专家仅通过标题就能对论文进行分类。因此，利用这种结构信息可以提高分类器的性能。 为了解决如何充分利用分段文档的结构信息来提高分类精度和召回率，同时避免额外训练新分类器的问题，我们设计了两种算法：IN MIX 和 OUT MIX。这两种算法基于分治法的思想，旨在强调文档中更重要的部分。 ## 2. 问题描述 ### 2.1 分段文档相关定义 - 分段文档集 $D$ 与预定义模板 $S$ 相关联，模板 $S$ 由命名属性 $s_1, s_2, \cdots, s_n$ 组成。 - 存在值函数 $\theta : D \times S \to T$，若 $\theta(d, s_i) = t_i$（$d \in D$），则表示文档 $d$ 的属性 $s_i$ 的值为 $t_i$，$t_i$ 是 $d$ 的一个分段。 - 属性的“重要性”由属性权重函数 $WET: S \to [0, 1]$ 衡量。通常，$S$ 由内容提供者定义，$WET$ 是一个经验函数，可根据不同的 $S$ 进行修改。 ### 2.2 分段文本分类任务 给定类别集 $C$，分段文本分类（STC）的任务是近似未知目标函数 $\Phi : D \times C \to \{T, F\}$，其中 $T$ 表示真，$F$ 表示假。对于普通文本分类问题，目标函数是 $\varphi : T \times C \to \{T, F\}$。在训练和测试阶段之前，文档通常被索引为特征向量，索引函数 $\sigma$ 定义为 $T \to V$（$V$ 是特征向量集），分类函数 $\lambda$ 定义为 $V \times C \to \{T, F\}$，且 $\varphi = \sigma \cdot \lambda$。 ### 2.3 假设条件 - 分段 $t_i$ 是普通文本，本文不考虑具有嵌套结构的文档。 - $t_i$ 对分类结果有一定影响，因为互联网上的大多数结构化文本文件在分类时通常存在一些未使用的属性，这些属性应在分类前去除。 - 若 $i \neq j$，则 $t_i$ 和 $t_j$ 是语义不同的分段，它们对分类的影响应该不同。 ## 3. 解决方案 ### 3.1 IN MIX 算法 - **思路**：将属性值合并作为分类器的输入。直观上可以“重复”重要的词，但词只能被“重复”整数次，因此我们合并词向量。 - **步骤**： 1. 计算所有 $t_i$ 的 TFIDF 向量。 2. 初始化属性权重函数 $WET$，若 $s_i$ 比 $s_j$ 更重要，则 $WET(s_i) > WET(s_j)$。 3. 使用 MERGE V 算法合并 TFIDF 向量： ```plaintext Input: (s1, v1), (s2, v2), ..., (s|S|, v|S|); WET: S →[0, 1]; S /*the size of vi is the same as that of document feature vector V*/ Output: v: vector of float number /* TFIDF vector*/ BEGIN FOR all si in S IF (min value>WET(si)) /* find the least important attribute*/ min=i min value=WET(si) END IF END FOR FOR all vi vi = vi × (WET (Si)/WET (Smin)) /* re-evaluate the TFIDF vector*/ v=v+vi /* v and vi are of the same size, v(j) = v(j) + vi(j)*/ END FOR output v END ``` 4. 将 MERGE V 的输出作为分段文档的词向量，由训练好的普通文本分类器进行标记。 - **时间复杂度**：与传统分类算法相比，额外成本是 MERGE V，其时间复杂度为 $O(|S|)$。对于大多数流行的分类算法，复杂度至少为 $O(|V| * |C|)$，其中 $V$ 是文档特征向量，通常远大于 $S$。因此，MERGE V 的成本可以忽略不计，IN MIX 的成本几乎与传统分类算法相同。 ### 3.2 OUT MIX 算法 - **思路**：合并不同属性的分类预测结果。该算法的优点是仅使用普通文本分类器的输出，不关心文档索引和降维过程，因此可用于“封装”的分类器。 - **步骤**：使用 MERGE P 算法合并部分分类预测结果，基本思想是投票。若文档的一个分段被分类到某个类别，该类别将获得一张“票”。若某个类别获得超过一半的票，则整个文档将与该类别关联。若无法做出决策，则计算每个预测的“置信度”并选择最高的一个。 ```plaintext Input: (S1, P1), (S2, P2), ..., (S|S|, P|S|); WET: S →[0, 1] Output: P vector of float number; /* |P | = |Pi| = |C|, here |P | means the size of P*/ BEGIN VAR other,max: vector of float number; isI=0, notI=0, index=0: int; VAR P :vector of float number; FOR all i < |P | FOR all Pj IF Pj(i) is the largest one in Pj isI=isI+1 /* attribute j vote for catego ```