当前位置: 首页 > >

CTM与SVM相结合的文本分类方法

发布时间:

第 36 卷 Vol.36

第 22 期 No.22

计 算 机 工 程 Computer Engineering
文章编号:1000—3428(2010)22—0203—03 文献标识码:A

2010 年 11 月 November 2010
中图分类号:TP18

·人工智能及识别技术·

CTM 与 SVM 相结合的文本分类方法
王燕霞,邓 伟
(苏州大学计算机科学与技术学院,江苏 苏州 215006) 摘 要:研究一种相关主题模型(CTM)与支持向量机(SVM)相结合的文本分类方法。该方法用 CTM 对数据集建模以降低数据的维度,用 SVM 对简化后的文本数据进行分类。为使 CTM 模型能够较好地对数据集进行建模,在该方法中用 DBSCAN 聚类方法对数据进行聚类, 根据聚类所得到的聚类中心点数目确定 CTM 模型的主题参数。实验结果表明,该方法可以加快分类速度并提高分类精度。 关键词:文本分类;相关主题模型;聚类;支持向量机

Text Classification Method Combining CTM and SVM
WANG Yan-xia, DENG Wei
(School of Computer Science and Technology, Soochow University, Suzhou 215006, China) 【Abstract】A text classification method combining Correlated Topic Model(CTM) and Support Vector Machine(SVM) is proposed. In order to reduce the corpus’s dimension, this method models the corpus, and classifies the simplified text date with SVM. With the aim of making the CTM model the corpus better, DBSCAN clustering method is used and chooses the cluster number as the model topic parameter of CTM. Experimental result shows that the method can accelerate the classification speed and improve the classification accuracy. 【Key words】text classification; Correlated Topic Model(CTM); clustering; SVM

1

随着信息技术的发展,大量以文本形式存在的信息涌现 到互联网上,文本分类作为信息检索与数据挖掘领域的研究 热点与核心技术,近年来得到了广泛关注和快速发展 [1] 。为 了得到更好的分类效果,文本表示成了文本分类研究中的一 个很重要的部分。长期以来文本表示的主要方法是直接采用 向量空间模型(Vector Space Model, VSM)。 近年来以隐含狄利 克雷分配(Latent Dirichlet Allocation, LDA)为代表的主题模 型作为一种新的文本表示方法得到了深入的研究与应用 [2]。 该模型主要应用在文本分类、信息提取、电子邮件分类、图 像聚类、字符分类等方面。 LDA 模型假设主题之间是相互独立的,然而,这种假设 与真实数据集中的实际很不符合。为了克服这个缺陷,Blei 在 2006 年 提 出 了 相 关 主 题 模 型 (Correlated Topic Model, CTM)[3],该模型从 Logistic Normal 分布中提取主题,克服了 LDA 模型不能提取文本间相关信息的缺陷。这一模型一经提 出便在提取科学主题和图像提取中得到了成功的应用。 SVM 是近几年来在机器学习领域中出现的新的研究热 点,它是由 Vapnik 领导的 AT&TBell 实验室研究小组提出的 一种新的非常有潜力的分类技术 [4]。它以统计学习理论为基 础,在基于结构风险最小化原则上,有效地避免经典学习方 法中过学习、维数灾难、局部极小等传统分类存在的问题, 在小样本条件下仍然具有良好的泛化能力,已经成功地应用 在垃圾邮件过滤领域 [5]。 本文将 CTM 与 SVM 相结合提出一种文本分类方法。

概述

S

ηd
?

Z d,n

Wdn

? K

N

图1

CTM 的图模型表示

其中,图 1 中空心点表示隐含变量;实心点表示可观察 值;矩形表示重复过程。大矩形表示从 Logistic Normal 分布 小矩形表 中为文档集中的每个文档 d 反复抽取主题分布 η d ; 示从主题分布中反复抽样产生文档 d 的词( {w1, w2, , wN} )。 给定一个文档集合 D ,包含 M 个文档和 V 个不同的词。 每个文档 d 包含一个词序列 {w1, w2, , wN} 。在集合 D 对应的 CTM 模型中,假设主题数目固定为 k ,则一个文档 d 的产生 可以表示为以下 2 个过程: (1)从 Logistic Normal 分布 p(η / ?, ∑ ) 中随机选择一个
k 维的向量 ηd ,表示文档 d 中的主题混合比例。

(2)根据特定的主题比例对文档 d 中的词进行反复抽样, 得到 p ( wn / η d , β ) 。其中, ? 是 k 维的均值向量, ∑ 是 K × K 的协方差矩阵。 主题数 k 值对模型推断出的主题分配比例影响很大。根 据聚类中的簇和主题模型中的主题的相似性,对数据集中的 特征词用 DBSCAN[6]方法进行聚类,根据得到的聚类中心点 数目确定主题 k 值。
作者简介:王燕霞(1982-),女,硕士研究生,主研方向:智能化信 息处理;邓 伟,副教授、博士 收稿日期:2010-04-11 E-mail:20074227065064@suda.edu.cn

2

CTM 模型是 LDA 模型的一种改进模型,它从 Logistic Normal 分布中提取隐含主题。 CTM 的图形表示如图 1 所示。

CTM 模型

—203—

3

SVM 的主要思想是针对 2 类分类问题, 通过学习算法可 以自动寻找那些对分类有较大区分能力的支持向量,由此构 造出分类器,可以将类与类之间的间隔最大化,以保证最小 的分类错误率。因此,有较好的推广性和较高的分类准确率。 支持向量机最初仅解决线性分类问题。硬间隔线性支持向量 机如图 2 所示。

支持向量机

当最优分类面不能把两类点完全分开时,如果希望在经 验风险和推广能力之间求得某种均衡,可以通过引入松弛因 子 ξ i 允许错分样本的存在,则二分类支持向量机问题表示形 式为:
n 1 2 ? ? min : 2 w + C i∑ ξi =1 ? ?s.t. : y w T x + b ≥ 1 ? ξ , ξ ≥ 0 i i i i ?

(

)

i = 1, 2,

,n

该分类问题是一个凸二次规划问题,引入 Lagrange 函数 后,问题可以转化为下面的对偶问题:
n 1 n n ? T ? max i∑ ai ? 2 i∑ ∑1 ai a j yi y j xi x j ? =1 =1 j = ? n ?s.t. : ∑ a y = 0 C ≥ a ≥ 0, i = 1, 2, i i i ? i =1 ?

,n

图2

硬间隔线性支持向量机

假设给定一个样本点集合( x1 , y1 ),( x2 , y2 ),…,( xn , yn ),
xi ∈ R n , yi ∈ {+1, ?1} ,分隔平面 w T x + b = 0 将正负 2 类样本点

线性不可分情况的约束最优化问题中权值 w 和阈值 b 的 最优值的计算都和线性可分情况中的过程相同。 当训练样本集不能线性可分,支持向量机能允许分类错 误出现时,通过在目标函数中引入惩罚因子 C 来控制误差带 来的影响。

w b 分开, 为超平面的垂直方向, / w 为原点到超平面的距离。 设 l + 和 l ? 为分隔平面与最近的正负类样本点的距离,支持向 2 量机寻找能最大化 l 和 l 的分隔平面。 类样本点满足条件:
+ ?

4

? w T xi + b ≥ 1 for yi = 1 ? ? yi w T xi + b ? T ? w xi + b ≤ ?1 for yi = ?1 ?

(

) ≥1

(1) (2)

l+ = l? =

1 w

从复旦大学的 Tancorp-12 语料集的财经和地域 2 类中随 机选取 100 篇文档组成新的语料集进行实验。实验硬件平台 为 P4 3 GHz,512 MB 内存的 PC 机。实验 1 用来说明本文提 出的分类方法中 CTM 模型建模的效果。实验 2 用来验证本 文所提出的分类方法的有效性。 实验 1 将选取的语料集整理成一个词典,并对其中的每个词给 定一个序号,每篇文档表示成以下形式: 4.1
[M] [term_1]: [count_N] [count_1] [term_2]: [count_2] … [term_N]:

实验结果及其说明

该分类问题可以描述成为一个二次规划问题:
? min : w 2 ? ? T ?s.t. : yi w xi + b ?

(

) ≥1

i = 1, 2,

,n

(3)

求解该问题得到判别函数:
f ( x) = w x + b
T

(4) (5)

测试集的分类函数形式为:
Label ( x ) = sgn( w T x + b)

该 2 次规划含有较多的未知变量,转化为对偶形式更便 于求解,其对偶问题为:
n 1 n n ? T ? max : Q ( a ) = i∑ ai ? 2 i∑ ∑1 ai a j yi y j xi x j ? =1 =1 j = ? n ?s.t. : ∑ a y = 0 ai ≥ 0, i = 1, 2, , n i i ? i =1 ?

其中,M 表示一篇文档中包含的各不相同的特征词的数目; term_i 表示该特征词 i 的序号; count_i 表示特征词 i 在该文档 中出现的次数。 用 语 言 模 型 中 标 准 的 评 判 准 则 困 惑 度 (perplexity)评 价 CTM 模型的性能,值越低,说明性能越好。
perplexity ( D test ) = exp{ ?
d =1 M

∑ p (dd )
d =1

M

∑ Nd

}

(6)

由于二次规划非约束项的拉格朗日乘子不为零,用非零 乘子和其对应的训练样本即可得出 w、b。
w = ∑ ai yi xi , i = 1, 2,
i =1 n

新文档集通过 DBSCAN 聚类后得到的聚类中心点数是 4, 选取与该数相近的数作为主题数进行 CTM 建模对比实验, 实验结果如图 4 所示。

,n

(7) (8)

b = y j ? ∑ yi ai xi T x j
i =1

n

对于非线性可分问题,如图 3 所示。

图4

不同的主题数对应的困惑度

由图 4 可见,当主题数为 4 时困惑度值最小,从而证明 了加入聚类后的 CTM 模型选取方法是有效的。 实验 2 先对语料进行预处理,去除一些对分类没有多大意义的 词,比如说稀有词、停用词等。然后在 Java 中编程对选取的 4.2

图3

软间隔线性支持向量机

—204—

这些语料进行词频统计,计算出一共有多少个不同的词,并 分别计算出每个不同的词在每篇文档中出现的次数。然后将 得到的文本集分成 2 个部分:80 篇作为训练集,剩下的作为 测试集。 采用实验 1 中的模型选择方法分别选择并训练 CTM 模型,并用从模型中推出的主题参数作为文本特征表示每篇 文档,达到降低数据维度的目的。最后用支持向量机作为分 类器进行分类。 本实验研究单值分类的情况,正确率的计算方法为 p = n / N ,其中, n 表示正确分类的文档数; N 表示输入分 类器的文档总数。 为了便于比较该分类方法的性能,表 1 用 3 组实验来做 对比验证:VSM+SVM, LDA+SVM, CTM+SVM。每一种实验 做了 10 次交叉验证,实验得到的结果如表 1 和图 5 所示。
表1
方法 1 2 3 4 5 6 7 8 9 10 平均

从表 1 可以看出,CTM+SVM 得到的平均分类正确率是 最高的,它比 LDA 模型的分类正确率高出 1.5 个百分点,达 到了 91.5%。图 3 展示了 3 种分类方法每次分类正确率的折 线,CTM+SVM 方法明显优于另外 2 种方法,从而也验证了 该方法的有效性。

5

3 种方法的分类正确率
LDA+SVM 90 95 80 95 90 90 90 95 90 90 90 85 85 80 90 85 80 85 90 85 85 85

(%)
90 95 90 95 90 90 90 95 90 90 91.5

VSM+SVM

CTM+SVM

本文研究一种 CTM 和 SVM 相结合的文本分类方法。采 用 DBSCAN 聚类方法确定 CTM 模型的主题数,将得到的 CTM 模型对待分类的数据集建模以降低数据维度, 并用 SVM 对简化后的文本数据进行分类。该方法将 CTM 模型较好的 文本表示能力和 SVM 强大的分类能力结合起来以求能够提 高文本分类的效果。实验结果表明,该方法可以在降低数据 维度的条件下提高分类的正确率。 然而, 该方法中的 CTM 模 型只能提取 2 个主题之间的相关性信息,而在真实的数据集 中,多个主题之间很可能还会存在着相关性。因此,在以后 的工作中有待研究或改进得到能够提取多个主题之间相关性 的主题模型来更好地表示文本。 参考文献
[1] Aas K, Eikvil L. Text Categorization: A Survey[R]. Norway, Oslo: Norwegian Computing Center, Tech. Rep.: 114, 1999. [2] Blei D M. Latent Dirichlet Dirichlet[J]. Journal of Machine Learning Research, 2003, (3): 993-1022. [3] Lafferty J B D. Correlated Topic Models[C]//Proc. of Neural Information Processing Systems Conference. Cambridge, MA, USA: MIT Press, 2006. [4] Cristianini N. 支持向量机导论[M]. 李国正, 王 译. 北京: 电子工业出版社, 2004. [5] 王祖辉, 姜 维. 基于支持向量机的垃圾邮件过滤方法[J]. 计算 机工程, 2009, 35(13): 188-189. [6] Ester M, Kriegel H P, Sander J, et al. A Density Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]// Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland, USA: AAAI Press, 1996. 猛, 曾华军, 等,

结束语

图5

3 种方法的分类正确率

编辑

索书志

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(上接第 202 页) 参考文献
[1] 郭安哲, 马 莉. 一种基于多尺度局部分形维轮廓不规则特征 提取算法[J]. 计算机系统应用, 2009, 18(2): 110-115. [2] Ng V, Coldman A. Diagnosis of Melanoma with Fractal Dimensions[C]//Proc. of IEEE TENCON’93. [S. 1.]: IEEE Press, 1993: 514-517. [3] Tanaka T, Yamada R, Tanaka M, et al. A Study on the Image Diagnosis of Melanoma[C]//Proc. of the 26th IEEE Annual International Conference on MBES’04. [S. 1.]: IEEE Press, 2004: 1597-1600. [4] Lee T K. Measuring Border Irregularity and Shape of Cutaneous Melanocytic Lesions[D]. Vancouver, Canada: Simon Fraser

University, 2001. [5] Ma Li, Xu Weidong, Zhu L. Description of Boundary Irregularity on Multi-scale Local FD for Melanomas[C]//Proc. of the 3rd IEEE International Conference on Bioinformatics and Biomedical Engineering. [S. 1.]: IEEE Press, 2009: 1-4. [6] 钱文光, 林小竹. 图像轮廓曲率计算与角点提取[J]. 仪器仪表学 报, 2007, 28(4): 63-68. [7] Lin Kwan-Ho, Guo Baofeng, Lam Kin-Man, et al. Human Face Recognition Using a Spatially Weighted Modified Hausdorff Distance[C]//Proc. of 2001 International Symposia Intelligent Multimedia, Video Speech Processing. New York, USA: [s. n.], 2001: 477-480.

编辑

索书志

—205—




友情链接: