0 引言

文本分类是有效组织和处理信息的基础, 为了能够对文本进行正确分类, 常见的处理方法是将非结构化的文本数据转换成易于分析和计算的结构化文档数据, 结合文本语义和结构特点对文本进行分析和分类。一部分学者以特征项支持度作为权重, 构建空间向量模型, 如彭京等^[1]提出的基于词向量空间模型的文本分类方法, 构建词-类别支持度矩阵来计算文本与类别的相似度；由郝水龙等^[2]考虑用户兴趣随时间变化的特点, 提出的一种基于层次向量空间模型(Vector Space Model, VSM)的用户兴趣模型表示及更新处理机制, 首先基于特征项形成兴趣主题, 再由兴趣主题形成用户兴趣, 由此建立层次型用户兴趣模型；肖雪等^[3]提出的基于向量空间模型的二重特征选择方法FDS(Feature Dual-Selection)以及层次分类算法HTC(Hierarchical Text Classification)。这些研究在一定程度上能够对文本进行正确分类, 但是这些算法都是以支持度为权重, 结合空间向量模型, 获取的特征项精度低, 特征向量高维, 而且没有结合特征项语义分析, 导致分类精度偏低、抗干扰能力差。另外, 还有一些基于语义分析的文本分类方法, 如林伟等^[4]提出的基于概念特征的语义文本分类模型, 克服了特征向量空间的高维性和稀疏性；由宋胜利等^[5]结合词语上下文语境和语义背景信息, 提出的文本语义图模型, 较大程度地保留文本间信息, 强化了词语间语义内涵, 但是忽略了特征项的支持度和结构等特点。这些基于简单语义分析的文本分类算法, 并不能有效地体现文本的主题, 算法分类效率偏低。也有一些人利用本体语义块相似性的特点, 提出了基于本体语义块相似性的文本分类算法, 如陈继文等^[6]采用采用编辑距离法计算概念语义块单词序列中对应单词的相似度, 加权求和得概念语义相似度。后来, 有人将显露模式(Emerging Pattern, EP)应用到文本分类中, 如段磊等^[7]结合类内文档频率特征提取方法和EP对文本进行分析并归类, 大幅降低了特征空间的维数, 提高了分类效果, 但是没有结合语义分析, 且没有有效利用特征项支持度, 导致分类算法适应能力较弱。

不难看出, 这些文本分类算法大多是基于层次分类树模型^[8-10], 因此不可避免地涉及到分类路径的阻塞问题^[11], 一种做法是增加更多的分类通道, 文献[12]中每个分类器考虑两个候选类别, 将文本分类到具有最大和次大概率值的两个类别中。文献[13]通过设置一个最低的可接受阈值, 将文本分配到计算得分值大于给定阈值的所有类别来减少阻塞问题。但是这些方法中阈值或者相关概率选取直接影响到分类的精度和算法效率。Yao^[14]提出的决策粗糙集模型是一种基于最小期望风险的Bayes决策理论, 它考虑了采取某种决策后的风险代价问题, 能较好地解决阈值选取问题。

结合文献[15-16]中提出的阈值获取方法和决策粗糙集模型理论, 提出了一种阈值优化的文本语义分类算法TSCTO(Text Semantic Classification with Threshold Optimization), 首先由经过预处理的文本获取文档特征项频率分布表, 然后构建粗糙集联合决策分布密度矩阵, 根据密度矩阵, 计算最小阈值^[15], 从而提取满足最小阈值的高频词；然后由语义分析与逆向文档频率方法获得基于语义类内文档频率的高频词, 再由基本显露模式(essential Emerging Pattern, eEP)分类方法训练最简模式分类器, 最后根据相似性公式计算文本相似性得分, 结合决策粗糙集理论对文本进行分类。实验中本文研究了阈值的选取对分类精度的影响, 并且通过优化阈值的选取在一定程度上减少了路径阻塞, 提高了TSCTO算法文本分类性能。

1 基本概念

设选取训练样本数据集TDB, 其中包含N个样本{TDB₁, TDB₂, …, TDB_N}, 每个样本都有所属的类别；待测数据样本集WDB, 其中包含Y个样本{WDB₁, WDB₂, …, WDB_Y}, 若被正确分类的样本有X个, 则分类算法正确率为X/Y, 分类正确率是衡量一个文本分类算法优劣的重要指标。

文本分类时, 大多数采用层次树模型, 因此涉及到子树分类器、路径阻塞等概念。

定义1^[14]  假设c₁, c₂, …, c_n为文档d_j从根节点对应类别c₁分配到叶子节点对应类别c_n时经过的一条分类路径, 把经过这条路径涉及到的分类器称为子树分类器。如果文档d_j被该路径中某个分类器错误分类时, 说明该文档最终分类结果将被错误拒绝, 称为路径阻塞。

为了构建基于文本分类的粗糙集分布密度矩阵, 本文把以空间向量模型为基础获取的高频词看成是条件属性特征O, 高频词出现的频率看成是该属性的特征值V, 所属文档的类别看成是决策属性D, 因此可以将高频词和相应文档转换为粗糙集联合决策分布密度矩阵。

定义2  假设训练文档集为{f₁, f₂, …, f_M}, 测试文档集中出现的高频词为{O₁, O₂, …, O_N}, 则高频词和相应文档对应的粗糙集联合决策分布密度矩阵可定义如下：

$\begin{matrix} {} & \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} {} & {{O}_{1}} \\ \end{matrix} & \begin{matrix} {} & {} \\ \end{matrix} \\ \end{matrix} & {{O}_{2}} \\ \end{matrix} & {} \\ \end{matrix} & \cdots \\ \end{matrix} & {} & {{O}_{N}} & {} \\ \end{matrix} \\ \boldsymbol{OoD}=\begin{matrix} {{f}_{1}} \\ {{f}_{2}} \\ \vdots \\ {{f}_{M}} \\ \end{matrix} & \left[\begin{matrix} D({{f}_{1}}/{{O}_{1}}) & D({{f}_{1}}/{{O}_{2}}) & \cdots & D({{f}_{1}}/{{O}_{N}}) \\ D({{f}_{2}}/{{O}_{1}}) & D({{f}_{2}}/{{O}_{2}}) & \cdots & D({{f}_{2}}/{{O}_{N}}) \\ \vdots & \vdots & \cdots & \vdots \\ D({{f}_{M}}/{{O}_{1}}) & D({{f}_{M}}/{{O}_{2}}) & \cdots & D({{f}_{M}}/{{O}_{N}}) \\ \end{matrix} \right] \\ \end{matrix}$

(1)

其中:D(f_i/O_k)=f_i∩O_k/O_k, O_k表示高频词O_k出现的频数, 如果O_k=0, 记D(f_i/O_k)=0；f_i∩O_k指文档集中获取的高频词在不同文档类别标签中频数。

根据粗糙集理论, 样本的分类一般可以划分到正域POS, 边界域BND, 负域NEG。确定性分类来源于正域POS, 但是实践表明边界域中隐含了潜在的有价值信息。如何从边界域中提取知识, 文献[16]也进行了相关研究。

风险决策理论, 就是基于接受正域POS, 否定负域NEG, 模糊处理边界域BND方法, 使得风险期望最小。简单地说, 对给定行为集A=(a_P, a_B, a_N), 其中a_P, a_B, a_N分别表示将对象f分类到a_P, a_B, a_N正域POS(f)、边界域BND(f)、负域NEG(f)的三种行为。不同的决策行为对应不同的风险值, λ_PP、λ_BP、λ_NP表示在对象属于f的状态下分别采取行为集A=(a_P, a_B, a_N)时的风险值；类似地, λ_PN、λ_BN、λ_NN表示在对象不属于~f的状态下分别采取行为集A时的风险值。易知, 作出正确决策产生的风险要小于作出错误决策产生的风险, 故有λ_PP≤λ_BP≤λ_NP且λ_PN≥λ_BN≥λ_NN。

因此, 通过联合决策分布密度矩阵和风险值可以定义下面的采取行为集A时的风险期望值：

$R({{a}_{\bullet }}|{{f}_{i}})=\sum\limits_{k=1}^{M}{{{\lambda }_{\bullet p}}D({{f}_{i}}|[{{O}_{k}}]+{{\lambda }_{\bullet N}}D(\tilde{\ }{{f}_{i}}|[{{O}_{k}}])}$

(2)

其中a_·表示a_P, a_B, a_N。

根据Bayes最小风险决策原则, 可以进行如下分类：

若R(a_P|f_i)≤R(a_N|f_i)并且R(a_P|f_i)≤R(a_B|f_i), 则判定文档f_i属于正域, 即正确分类；类似地, 若R(a_N|f_i)≤R(a_P|f_i)并且R(a_N|f_i)≤R(a_B|f_i), 则判定文档f_i属于负域, 即不相关文档；若R(a_B|f_i)≤R(a_P|f_i)并且R(a_B|f_i)≤R(a_N|f_i), 则判定文档f_i属于边界域, 即文档分类结果需要进一步确定。

本文部分阈值的设置采用了文献[15]中相关结论。限于篇幅, 请参考文献[15]。

其他相关定义如下。

定义3  设D是训练样本数据集TDB的子集, 项集X在D上的支持度sup_D(X)=count_D(X)/|D|, 其中, count_D(X)是数据集D中包含X的样本个数, 而|D|是D中样本的总数。

定义4  ^[7]设D和D′是训练样本数据集TDB的子集, 项集X从D′到D的增长率gr_D′→D(X)定义如下：

$g{{r}_{{D}'\to D}}(X)=\left\{ \begin{align} & 0, \ \ \ \ \ \ \ \ \ \ \ \ su{{p}_{{{D}'}}}(X)=su{{p}_{D}}(X)=0 \\ & \infty, \ \ \ \ \ \ \ \ \ \ \ su{{p}_{{{D}'}}}(X)=0, su{{p}_{D}}(X)\ne 0 \\ & \frac{su{{p}_{D}}\left( X \right)}{su{{p}_{{{D}'}}}\left( X \right)}其他 \\ \end{align} \right.$

(3)

如果把数据集D和D′分别看成是c_i类和c_i类样本的集合, 则gr_D′→D(X)可简记为gr_D(X), 它是项集X从c_i类到c_i类频率变化显著程度的度量, 其中c_i类表示除c_i类外的其他类集合。

定义5^[7]   设增长率阈值ρ>1, 如果项集X是从D′到D的增长率gr_D′→D(X)≥ρ, 则称X是从D′到D的EP, 或者简称X是D的EP。项集X是D的eEP当且仅当条件：1)X是D的EP；2)X在D中的支持度不小于预先指定的最小支持度阈值ξ；3)X的任何真子集都不满足条件1)和2)。

如果不进行进一步转化, 直接将分类文档高频词和文档分类信息转化为粗糙集联合决策分布密度矩阵, 则矩阵空间太大。因此本文基于语义角度, 进一步提取基于语义类内文档频率的高频词, 以压缩存储空间。

2 基于语义类内文档频率的特征提取

本文采用Ansj中文分词方法^[17]进行文本分词, 该分词方法是中国科学院的ictclas中文分词算法, 它具有准确、高效和自由地进行中文分词等优点, 分词处理之后, 文本变成由词和标点符号组成的集合, 建立过滤表(说明：本文实验中建立的停用词表StopWords共31页, 907行停用词)移除标点符号和一些非核心词, 如“我们”“的”“既然”等, 经过过滤之后, 减少了文本的长度, 留下的词在某种程度上具有一定的意义, 对相同的词进行合并计数, 得到一组词-词频序列, 根据词的词频, 利用快速排序的方法由高到低进行排序, 排在词-词频序列前端的都是高频词或者核心词。通常情况下, 文本的主题由核心词义构成, 核心词的数量由文本的长度决定, 所以, 提取词-词频序列的前n%个词作为文本的初步特征项, 其中n%为初步高频词频率阈值a, 由实验结果得知, 阈值a取50%比较合理。

经过以上过程得到初步处理后的特征项, 其处理方法原理是基于词频的特征提取方法, 虽然能够有效减小文本长度、提取文本核心词, 但是, 获取的高支持度特征项可能存在频繁语义模式, 不具有良好区分能力。为了解决上述问题, 许红涛等^[19]提出了基于类内文档频率的特征提取方法, 对经过上述处理之后的特征项进行再次筛选, 设类个数阈值, 提取在众类中是特征项且类个数不超过给定阈值的特征项, 即基于类内文档频率的特征项, 其在某些类中以较高频率出现, 但又不是在许多类中都高频出现, 显然具有一定的区分能力, 但是该方法仅仅基于特征项重复出现的角度考虑, 并没有结合语义相似情况, 如“喜欢”与“好感”, 这两个词在语义上非常相似, 它们之间不具有良好的区分能力, 上述的方法将这两个特征项视作相异, 这将会降低计算结果的准确性。结合语义分析法将有助于相似词的发现, 提高算法分类精度, 常用的方法有基于《知网》和WordNet等。

本文主要利用《知网》方法, 利用文献[20]中给出的“概念”和“义原”相关方法, 通过计算义原之间相似度^[20]来度量语义之间的相似度, 并对那些语义相似度极高且出现在多数类的特征项进行过滤, 例如：假设有10个类, 其中一个类中有词“喜欢”, 在其他9个类中有7个以上都出现“喜欢”“好感”“钟爱”等相似词, 显然“喜欢”一词的意思在众类中都出现, 不具有区分类的功能, 需要过滤, 这样可以进一步减少特征项的数量, 改进提取方法, 使得获取的分类器中的类与类之间更加具有区分性。

3 基于eEP的文本语义分类算法

经上述特征提取后, 词频转换成了相应的支持度, 训练文本和待测文本被表示成特征项与支持度的集合。

3.1 获取eEP

eEP具有最短且最具表达能力的特点, 非常适合用于构造文本分类器。设X是C类的eEP, 若X在C类中的频率是其在C类中频率的gr(X)倍, 则称X在C类中的增长率为gr_C(X)。对于分类来说, 增长率度量了对象归类的可能性, 如X属于C类的可能性是X属于C类的gr_C(X)倍。其挖掘步骤如下：

1) 取定最小支持度阈值ξ和最小增长率阈值ρ^[17]；

2) 将训练数据集分为c_i类和c_i类；分别挖掘c_i类和c_i类的eEP, 其中i∈{1, 2, …, N}。

3.2 分类器构造

为每种类型的文本进行上述训练, 得到足够能够表达该文本核心思想的eEP集合, 每个eEP都有相应的支持度, 这些eEP构成了一个代表该类型文本的类, 这样如果10种类型的文本参与训练分类器, 则分类器由这10种类型文本的eEP集合构成的10个类组成, 如图 1所示, 表示类i分类器构造过程。

3.3 相似度得分计算及其风险决策

分类器和待分类文本都是由特征项与支持度(词频)组成, 支持度即为特征项在文本中权重, 反映了特征项对文本主题表达的贡献率, 设X为文本T的特征项, 其支持度为sup_T(X), 则X以sup_T(X)的概率决定了该文本的主题。

设X是C类的eEP, 若X在待分类文本T中出现或者相似出现, 则认为X以$\frac{g{{r}_{C}}\left( X \right)}{g{{r}_{C}}\left( X \right)+1}\times su{{p}_{T}}\left( X \right)\times {{S}_{X}}$的概率判定T属于C类, 而以$\frac{1}{g{{r}_{C}}\left( X \right)+1}\times su{{p}_{T}}\left( X \right)\times {{S}_{X}}$的概率判定T属于C类, 其中S_X为X与待分类文本中相同或相似特征项之间的语义相似度, 当X在待分类文本T中出现时, S_X=1, 否则, 0≤S_X < 1。当1 < gr_C(X) < ∞时, S_X=S_X′, X′表示出现在C类中的X。

如果X以一定的概率判定待分类文本T属于C类, 说明X在待分类文本T中出现即正确接受(正确标记为1, 预测为1)或者相似出现即可能错误接受(正确标记为0, 但预测为1)；反之, 如果X以一定的概率判定待分类文本T不属于C类, 即可能把应该属于文本T的错误地拒绝了，导致阻塞的产生, 即错误拒绝(正确标记为1, 预测为0)的风险, 因此可以根据风险决策理论。本文提出了减少阻塞可能性的文档相似性得分计算方法, 定义如下：

$\begin{align} & score\left( T, {{C}_{i}} \right)=\sum\limits_{X\in PS(T, {{C}_{i}})}{\frac{g{{r}_{i}}\left( X \right)}{g{{r}_{i}}\left( X \right)+1}\times su{{p}_{T}}\left( X \right)\times {{S}_{X}}} \\ & +\sum\limits_{X\in NS(T, {{C}_{i}})}{\left( \frac{1}{g{{r}_{i}}\left( X \right)+1}\times su{{p}_{T}}\left( X \right)\times {{S}_{X}} \right)} \\ \end{align}$

(4)

其中:i∈{1, 2, …, N}, N为分类器类的个数, PS(T, c_i)={X|X是c_i类的eEP, 且X在T中出现或者相似出现}, NS(T, c_i)={X|X是c_i类的eEP, 且X在T中出现或者相似出现}。S_X表示X与待测文本中相同或者相似特征项的语义相似度, 相似出现是指它们之间语义相似度大于文本分数语义相似度阈值λ。当X∈NS(T, c_i)时, 若1 < gr_i(X) < ∞, S_X=S_X′, X′表示出现在c_i类中的X；若gr_i(X)→∞, 则$\sum\limits_{X\in NS(T, {{C}_{i}})}{\left( \frac{1}{g{{r}_{i}}\left( X \right)+1}\times su{{p}_{T}}\left( X \right)\times {{S}_{X}} \right)}=0$；gr_i(X)≤1与条件不符。

在构造完分类器之后, 需要利用分类器对待分类的文本进行分类, 在分析特征项相似度时, 本文规定, 若特征项在分类器与待分类样本中相同出现, 则认为该特征项的相似度为1；否则, 若语义相似度大于文本分数语义相似度阈值λ, 则认为是相似出现, 语义相似度即为特征项相似度。阈值λ的取值因文本的不同而异, 实验表明, 取λ=0.8比较合理。

TSCTO算法将C类和C类的每个eEP进行分析判断, 根据计算T属于C类的得分score(T, C)来判断T所属的类, 流程如图 2所示, 具体分类步骤如下：

1) 对待分类文本T进行切词、过滤等预处理；

2) 对待分类文本中的特征项计算支持度；

3) 对分类器中每个类的eEP与待分类文本中的特征项计算语义相似度；

4) 利用式(4), 计算文档相似性得分；

5) 根据计算结果, 将T归为相似性分数最高的类或多数类。

4 实验结果与分析

实验测试运行环境为Windows XP操作系统, 2.9 GHz的CPU, 2 GB的内存, 编程工具为MyEclipse。本实验的文本分类语料库由搜狗实验室^[18]提供, 该数据集(SogouC.reduced)由汽车、财经、IT、健康、体育、旅游、教育、招聘、文化和军事等10个主题组成, 数据量48.24 MB, 共1 990×9个中文文本文档。实验中每个类随机选取1 000个文本, 其中700个用于训练分类器, 300个用于测试分类性能, 在分析阈值对分类性能的影响时, 将3 000个测试文本随机均分成Data1和Data2。根据文献[19], 类个数阈值φ取K/3比较合适, 其中K是总类数, 下面分析其他阈值对分类性能的影响。

4.1 分析阈值α, β, γ和λ对分类性能的影响

对实验中选取的文本进行分词、过滤和词频累计等预处理, 获得文档特征项频率分布表, 然后构建粗糙集联合决策分布密度矩阵, 利用密度矩阵, 分析和计算最小阈值, 阈值的选取直接影响到分类性能。

初步高频词频率阈值α左右着初步提取特征项的数量, 如图 3所示, α如果取值太小, 那么提取的特征项过少, 特征项信息不足, 导致分类性能偏低；α如果取值过大, 特征项过多, 包含大量不能代表文本主题的特征项, 影响分类性能。实验表明, α大约在50%左右是一个比较合适的选择。算法中考虑风险代价问题, α主要取基于粗糙集分布矩阵中的最小阈值, 从而获得满足最小阈值的高频词。

训练分类器语义相似度阈值β是训练分类器时, 判断两个特征项是否为相似关系的关键因素, 一般情况, 语义相似度只有在极高的情况下才能判断特征项为相似关系, 但过高又会降低相似特征项的发现, 如图 4所示, 经实验分析, β取90%(或0.9)比较合适。

语义类内文档频率阈值γ直接影响着分类器特征项的数量, 如果γ太大, 所提取的特征项过多, 分类器类与类之间区分能力不强；如果γ过小, 所提取的特征项过少, 表达类主题的特征项不足, 导致分类性能降低。如图 5所示, 实验结果表明, γ取20%比较合适。

文本分数语义相似度阈值λ决定了参与文本相似度计算的特征项数量：如果λ太小, 那么相似度很低的特征项都会参与计算, 特征项太多, 导致分类性能下降；如果λ过大, 将减少相似特征项的发现。如图 6所示, λ取80%(或0.8)比较合适。

4.2 与其他算法的比较

经过实验对比分析, 得到各类阈值的最优值(α=50%, β=90%, φ=K/3, γ=20%, λ=80%), 在特征提取之后, 大幅降低了特征项的数量, 所提取的有效特征项具有良好的区分能力, TSCTO算法取得了很好的分类性能。

表 1列举了各类算法在数据集上的性能, 其中TCEP(Text Categorization by EP)是郑州大学许红涛提出的算法结果, SVM-PKU(Support Vector Machine-PeKing University)是使用北大计算语言研究所的支持向量机的中文文本自动分类(Automatic Text Categorization of Support Vector Machine, ATCSVM)算法得到的结果, kNN(k-Nearest Neighbor)是k最近邻算法的结果, NB(Naive Bayes)是朴素Bayes分类算法的结果。准确率是指待测文本被正确分类的比例, 精度指C类待测文本在预测为C类的样本中所占的比例, 召回率是指C类待测文本被正确分类的比例^[10], F-measure用如下公式计算：

$ F-measure=2\times \frac{Rrecision\times Recall}{Rrecision+Recall} $

为了进一步验证本文给出方法的性能, 从语料中选取五类包括IT、教育、健康、文化、体育, 共300篇文本进行实验, 分别采用基于传统的词频方法, 记为TCBWF；基于一般语义方法, 记为TCBWS；以及文中基于风险决策的TSCTO方法来做文本分类比较。对于分类效果分别用准确率(P)和时间(T)来进行比较, 实验结果如表 2所示。

由于本文提出的TSCTO算法将错误拒绝类的风险考虑到文本相似性得分计算当中, 通过基于最小期望风险的Bayes决策理论将文档按照一定的阈值分类到多路径通路中, 减少了阻塞问题, 同时, 结合语义分析方法, 采用eEP最简模式改进了传统文本分类方法, TSCTO算法优势明显。实验结果表明, 本文算法在分类性能的各项指标上都优于其他分类算法, 但由于引入风险矩阵计算等方法, 时间效果不是很好(说明：分类准确率是指算法在总体上的分类性能, 宏平均是指算法在单类上的分类性能)。

5 结语

本文针对众多文本分类方法中存在的一些问题进行了研究, 分析了基于类内文档频率特征提取方法的优缺点, 结合决策粗糙理论, 通过构造文档类别与文档特征词的分布密度矩阵, 提出一种阈值获取的语义类内文档频率特征提取方法。最后通过阈值选取的优化, 在一定程度上减少了路径阻塞问题, 提高了TSCTO算法文本分类性能。下一步将在文献[15]的基础上, 进一步考虑阈值自动获取的文本分类算法以及语料库本身对结果的影响。