Text Classification Model Based on Multiconlitron
-
摘要:
针对文本分类问题，从分片线性学习的角度出发，提出了一种文本分类的组合凸线性感知器模型.首先，对文本样本集进行预处理，包括特征选择、特征项赋权等；然后，分别利用生长支持组合凸线性感知器算法（growing support multiconlitron algorithm，GSMA）和支持组合凸线性感知器算法（support multiconlitron algorithm，SMA）构造组合凸线性感知器，对样本集进行分类.该模型基于支持向量机的最大间隔思想，通过集成线性分类器，实现了对2类数据的划分，具有计算简单、适应能力强的优点.在标准文本数据集上的实验结果表明：该模型所构造的分类器具有良好的文本分类性能，与其他典型文本分类方法的对比也说明了该方法的有效性.
Abstract:To deal with the problem of text classification, a text categorization method was proposed based on multiconlitron from the perspective of piecewise learning. First,text sample preprocessing including feature selection and feature weighting was performed. Then, the multiconlitron was constructed by using growing support multiconlitron algorithm (GSMA) and support multiconlitron algorithm (SMA) respectively for text classification. Inspired by the idea of maximum interval of support vector machine, the classification of two kinds of data by integrating the linear classifier was achieved by this model, which had the advantages of small computation cost and strong adaptive ability. Experiments on standard text data sets show that the proposed method has a good performance on text classification and the comparison results with some other typical text classification methods also verifies the effectiveness of the proposed method.
-
Keywords:
- piecewise linear classifier /
- multiconlitron /
- text classification
-
文本分类是指在给定分类体系下，使用计算机自动地标记文本类别的过程. 它在信息检索、数据挖掘和舆情分析等领域中具有重要应用，已经成为现代信息处理的研究热点之一. 其中涉及文本表示、特征选择、分类模型和评价方法等关键技术[1]. 目前，比较成熟的文本分类器有K-最近邻(K-nearest neighbor，KNN)、朴素贝叶斯(naive Bayes，NB)、支持向量机(support vector machine，SVM)、神经网络[2]等. KNN性能较稳定，但时空效率较低；NB分类速度最快，但分类精度最低；神经网络能充分逼近复杂的非线性关系，但需要大量的参数，学习时间过长；SVM分类精度最高，在解决小样本、非线性及高维模式识别中表现出许多特有的优势[3]，已经成为文本分类领域的研究热点.
支持向量机的基本思想是假定2类数据线性可分，通过寻找最大间隔分类超平面，使其能够正确地划分2类数据. 现有的支持向量机又可分为线性支持向量机和非线性支持向量机. 前者用于解决线性可分的情况，但是只能产生线性分类面，不足以处理比较复杂的线性不可分样本的分类问题. 后者使用核技巧可以解决非线性可分情况，但是核函数的选择缺乏指导，并且计算资源需求较大，不利于求解大规模数据.
分片线性分类器(piecewise linear classifier，PLC)是一种特殊的非线性分类器. 它可以直接在原输入空间构造，分开任意复杂的2类数据，避免核函数的选取困难. 同时，由于分类器的决策面是由若干个超平面构成的，与一般超曲面相比，不仅简单，易于实现，计算量小，又能逼近各种形状的超曲面，具有很强的适应能力[4].
目前，分片线性分类器已经引起人们广泛的关注，许多设计分片线性分类器的方法被提出，如线性规划方法[5]、局部训练方法[6]、决策树方法[7]，甚至经典的KNN算法也可看作一种简单的分片线性分类器. 然而，绝大多数分片线性分类器是基于经验并富有试探性的，缺乏统一的理论框架，而且对数据的空间分布结构依赖性较大，训练时间很长，分类器性能较差，甚至一些方法需要预先指定超平面的数量，描述线性函数如何组织，这些缺点限制了其在文本分类领域的应用.
针对上述情况，本文从分片线性学习的角度出发，提出了文本分类的组合凸线性感知器模型. 组合凸线性感知器[8]是Li等在凸可分、叠可分和凸线性感知器的概念基础上提出的构造分片线性分类器的一个通用理论框架. 该框架吸收了SVM的优点，并且采用了SVM的最大间隔思想，但无需使用核函数，避免了核函数的选取困难. 它是线性支持向量机和非线性支持向量机的一种折中处理，所构造的分片线性分类器性能一般介于二者之间.
为将组合凸线性感知器(multiple convex linear perceptron，multiconlitron)应用于文本分类领域，研究并评测其性能，本文首先将文本用向量的形式表示，然后用主成分分析方法对文本向量进行降维，其次构造组合凸线性感知器，完成分类过程，最后评测组合凸线性感知器在文本分类领域的性能. 为叙述简洁，在下文中，将凸线性感知器(convex linear perceptron，conlitron)简称为凸线器，组合凸线性感知器简称为组合凸线器.
1. 组合凸线器的基本概念
组合凸线器框架是以凸可分、凸线器等概念为基础的. 因此，本节将从数据集凸包和可分性的关系出发，详细阐述凸线器、组合凸线器等核心概念，下面首先给出凸包的定义[8]：
定义1 对于 ${{\mathbb{R}}^{n}}$ 上的任意一个有限集X，它的凸包定义为
$$ \begin{array}{*{20}{c}} {{\rm{CH}}\left( \mathit{\boldsymbol{X}} \right) = \left\{ {\mathit{\boldsymbol{x}}\left| {\mathit{\boldsymbol{x}} = } \right.} \right.}\\ {\left. {\sum\limits_{1 \le i \le \left| \mathit{\boldsymbol{X}} \right|} {{\alpha _i}{\mathit{\boldsymbol{x}}_i}} ,\sum\limits_{1 \le i \le \left| \mathit{\boldsymbol{X}} \right|} {{\alpha _i} = 1,{\mathit{\boldsymbol{x}}_i} \in \mathit{\boldsymbol{X}},{\alpha _i} \ge 0} } \right\}} \end{array} $$ 下面给出3个可分性定义.
定义2 线性可分(linearly separable)：对于2个有限集X, Y⊆ ${{\mathbb{R}}^{n}}$ ，如果X、Y的凸包不相交，即CH(X)∩CH(Y)=∅，则称它们是线性可分的.
定义3 凸可分(convexly separable)：对于2个有限集X, Y⊆ ${{\mathbb{R}}^{n}}$ ，如果∀y∈Y, y∉CH(X)，则称X相对Y是凸可分的. 如果X相对Y是凸可分的，或者Y相对X是凸可分的，则称X与Y是凸可分的.
定义4 叠可分(commonly separable)：对于2个有限集X, Y⊆ ${{\mathbb{R}}^{n}}$ ，如果X∩Y=∅，即二者之间无重合样本，则称它们是叠可分的.
图 1分别给出了3种可分情况的示例.
线性判别函数可表示为f(x)=w·x+b，并且对于正类的任意一个样本，f(x)>0；对于负类的任意一个样本，f(x)＜0；特别地，f(x)=0为一个超平面.
凸线性感知器是指一组线性函数的集合，它可以正确分开2类凸可分数据集，当训练方为X到Y时，可表示为
$$ \begin{array}{*{20}{c}} {{\rm{CLP}} = \left\{ {{f_l}\left( \mathit{\boldsymbol{x}} \right) = } \right.} \\ {\left. {{\mathit{\boldsymbol{w}}_l} \cdot \mathit{\boldsymbol{x}} + {\mathit{\boldsymbol{b}}_l},\left( {{\mathit{\boldsymbol{w}}_l},{\mathit{\boldsymbol{b}}_l}} \right) \in {\mathbb{R}^n} \times \mathbb{R},1 \leqslant l \leqslant L} \right\}} \end{array} $$ 满足以下条件：
$$ \left\{ \begin{array}{l} \forall \mathit{\boldsymbol{x}} \in \mathit{\boldsymbol{X}},\forall 1 \le l \le L,{f_l}\left( \mathit{\boldsymbol{x}} \right) = {\mathit{\boldsymbol{w}}_l} \cdot \mathit{\boldsymbol{x}} + {\mathit{\boldsymbol{b}}_l} \ge 0\\ \forall \mathit{\boldsymbol{y}} \in \mathit{\boldsymbol{Y}},\exists 1 \le l \le L,{f_l}\left( \mathit{\boldsymbol{y}} \right) = {\mathit{\boldsymbol{w}}_l} \cdot \mathit{\boldsymbol{y}} + {\mathit{\boldsymbol{b}}_l} < 0 \end{array} \right. $$ (1) 决策函数定义为
$$ {\rm{CLP}}\left( \mathit{\boldsymbol{x}} \right) = \left\{ \begin{array}{l} + 1,\forall 1 \le l \le L,{f_l}\left( \mathit{\boldsymbol{x}} \right) > 0\\ - 1,\exists 1 \le l \le L,{f_l}\left( \mathit{\boldsymbol{x}} \right) < 0 \end{array} \right. $$ (2) 其中L是指线性函数的个数. 凸线器具有2个特点：第一是局部分类间隔最大特性，这是由于凸线器的每一个片段对应硬间隔SVMs. 第二是方向性，当X对Y是凸可分时，可以构造从X到Y的凸线器，反之，当Y对X是凸可分时，可以得到从Y到X的凸线器，只是这2个凸线器的结构不同.
组合凸线性感知器是指一组凸线器的集合，它可以将2类叠可分数据集正确分开，可表示为
$$ {\rm{MCLP}} = \left\{ {{\rm{CL}}{{\rm{P}}_k},1 \le k \le K} \right\} $$ 满足以下条件：
$$ \left\{ \begin{array}{l} \forall \mathit{\boldsymbol{x}} \in \mathit{\boldsymbol{X}},\exists 1 \le k \le K,{\rm{CL}}{{\rm{P}}_k}\left( \mathit{\boldsymbol{x}} \right) = + 1\\ \forall \mathit{\boldsymbol{y}} \in \mathit{\boldsymbol{Y}},\forall 1 \le k \le K,{\rm{CL}}{{\rm{P}}_k}\left( \mathit{\boldsymbol{y}} \right) = - 1 \end{array} \right. $$ (3) 决策函数定义为
$$ {\rm{MCLP}}\left( \mathit{\boldsymbol{x}} \right) = \left\{ \begin{array}{l} + 1,\exists 1 \le k \le K,{\rm{CL}}{{\rm{P}}_k}\left( \mathit{\boldsymbol{x}} \right) = + 1\\ - 1,\forall 1 \le k \le K,{\rm{CL}}{{\rm{P}}_k}\left( \mathit{\boldsymbol{y}} \right) = - 1 \end{array} \right. $$ (4) 式中K是指线性函数的个数. 组合凸线器也具有局部最大间隔特性和方向性2个特点. 从不同方向构造的2个组合凸线器具有不同的结构，并以包含更少线性函数的组合凸线器为最终的分类模型. 凸线器和组合凸线器的示例见图 2.
2. 组合凸线器的构造方法
组合凸线器的构造方法包括基本构造方法和生长构造方法. 其中，前者提出了构造3类分类器的相应算法，后者则进一步提高了分类精度.
2.1 基本构造方法
对于线性可分的2类样本X和Y，其分类超平面可以等价为求解它们凸包之间的最近点对问题，也就是求解其硬间隔SVM，优化目标具体可表示为[9]
$$ \min \left\| {\mathit{\boldsymbol{x}} - \mathit{\boldsymbol{y}}} \right\|{\rm{s}}{\rm{.t}}{\rm{.}}\;\mathit{\boldsymbol{x}} \in {\rm{CH}}\left( \mathit{\boldsymbol{X}} \right),\mathit{\boldsymbol{y}} \in {\rm{CH}}\left( \mathit{\boldsymbol{Y}} \right) $$ (5) 如果(x*, y*)是经式(5)得到的最近点对，则Y和Y的分类超平面可表示为(x*, y*)的垂直平分面
$$ f\left( \mathit{\boldsymbol{x}} \right) = {\mathit{\boldsymbol{w}}^ * } \cdot \mathit{\boldsymbol{x}} + {\mathit{\boldsymbol{b}}^ * } $$ (6) 式中：w*=x*－y*；b*=(‖y*‖2－‖x*‖2)/2. 交叉距离最小化算法(cross distance minimization algorithm，CDMA)算法是以式(1)为优化目标的典型凸包间最近点求解算法，图 3给出了CDMA中找最近点对x*、y*的几何释义. 如果x1∈CH(X)不是CH(Y)到CH(X)的最近点，那么必然存在点z*∈CH(X)，使距离差值小于精度参数，即d(x1－y1)－d(x*－y*)＜ε成立. 若λ≥1，则z*=x2；若0＜λ＜1，则z*=x1+λ(x2－x1)，且z*是y*到线段CH{x1, x2}的垂点.
CDMA(X, Y, ε)表示以2个有限集X、Y，精度ε为输入，得到的X和Y的硬间隔支持向量机f(x)=w*·x+b*.
对于X, Y⊆ ${{\mathbb{R}}^{n}}$ ，如果X相对Y是凸可分的，可使用支持凸线性感知器算法[8](support conlitron algorithm，SCA)构造一个方向从X到Y的凸线器将X和Y正确分开. 如图 4所示，SCA算法首先从集合Y选择一个距离CH(X)最近的点yp，利用CDMA算法构造一个线性函数f1(x)=CDMA(X, {yp}, ε)，作为凸线器的第1个组件，切掉数据集Y所有满足f1(y)≤f1(yp)的点后，再从新的Y集合中，找到距离CH(X)另一个最近点yq，再计算得到第2个线性函数f2(x)=CDMA(X, {yq}, ε)，切掉Y中满足f2(y)≤f2(yq)的点，不断重复此过程直至Y=∅. 最终得到一个X相对Y的凸线器. 当精度参数为ε时，可表示为SCA(X, Y, ε).
对于叠可分的2类样本X和Y，X中的每一个点xi相对Y都是凸可分的，可使用支持组合凸线性感知器算法[8](support multiconlitron algorithm，SMA)构造一个组合凸线器将X、Y正确分开. 如图 5所示，SMA算法首先从集合X中选择距离Y最近的一个点xp，构造第 1个支持凸线器CLP1=SCA({xp}, Y, ε)，它切掉了X中满足条件CLP1(x)=+1的点，剩余的点仍记为X. 然后，再从X中找到距离Y的另一个最近点xq，计算得到第2个支持凸线器CLP2=SCA({xq}, Y, ε)，又切掉了X中满足条件CLP1(x)=+1的点. 重复此过程，直到X=∅.
最终，得到由若干个凸线器组成的一个组合凸线器MCLP. 当算法精度参数为ε时，该组合凸线器可表示为SMA(X, Y, ε).
2.2 生长构造方法
组合凸线器的生长构造方法是构造组合凸线器的一种新方法，能够有效提高分类精度并简化分类模型. 该方法由挤压(SQUEEZE)和膨胀(INFLATE)两个基本操作组成，对于凸可分情况，使用挤压操作将初始训练得到的分类边界推向内部凸区域，使其能够更好地拟合数据分布；对于叠可分情况，使用膨胀操作调整初始训练得到的分类边界，使其移动到更加合理的位置.
假设由SCA训练得到初始凸线器CLP={fl(x)=wl·x+b, 1≤l≤L}，将集合Y分成L个相互重叠的子集，即
$$ \mathit{\boldsymbol{Y}} = \cup {\mathit{\boldsymbol{Y}}_l},\mathit{\Omega = }\left\{ {{\mathit{\boldsymbol{Y}}_l},1 \le l \le L} \right\} $$ (7) 式中，Yl={y|fl(y)＜0, y∈Y}, fl∈CLP，是指Y中所有能够被fl(x)正确分类的样本点集合. 显然，存在i≠j使得Yi和Yj重叠，即Yi∩Yj≠∅.
如图 6所示，挤压操作每次均从Y中选择包含样本数量最多的子集Yp，通过CDMA训练得到线性函数gi(x)，切掉Ω中所有能够被它正确分类的子集，重复此过程，直到Ω=∅. 描述如下：
操作2：膨胀操作INFLATE(MCLP, X, Y, ε, T) 输入：初始组合凸线器MCLP={CLPk, 1≤k≤K}, X={xi, 1≤i≤N}, Y={yj, 1≤j≤M}, 精度参数ε, 挤压次数T 1.Xk={x|CLPk(x)=+1, x∈X}, CLPk∈MCLP 2.k←1, ψ←{Xi, 1≤i≤|MCLP|=K} 3.p=arg maxi{|Xi|, Xi∈ψ} 4.CLP′k=GSCA(Xp, Y, ε, T) 5.ψ={Xi|Xi∈ψ－{Xp}, ∃x∈Xi, CLP′k(x)=－1} 6.如果ψ≠∅，那么k←k+1，并转到步骤3 返回：MCLP={CLP′i, 1≤i≤k} 采用挤压操作进行凸线器生长的算法称为生长支持凸线性感知器算法[10](growing support conlitron algorithm，GSCA). 它能够产生更加合理的分类边界，有效减少凸线器中线性函数数量，一定程度上防止了过拟合情况的发生. GSCA中挤压次数可以设定为多次，GSCA(Xp, Y, ε, T)表示输入为2个有限集X、Y和精度参数ε构造的X相对Y挤压T次的凸线器CLP. 由于往往初次挤压能够有效调整分类边界，本文建议进行1次挤压即可.
假设由SMA训练得到的初始组合凸线器为MCLP={CLPk(x), 1≤k≤K}，此组合凸线器包含K个凸线器，将集合X分成K个相互重叠的子集，即
$$ \mathit{\boldsymbol{X}} = \cup {\mathit{\boldsymbol{X}}_l},\psi \mathit{ = }\left\{ {{\mathit{\boldsymbol{X}}_k},1 \le k \le K} \right\} $$ (8) 式中：Xk={x|CLPk(x)=+1, x∈X}， 为X中所有能够被CLPk(x)正确分类的样本点集合， CLPk∈MCLP；ψ为被不同凸线器划分的X中点子集的集合. 显然，存在i≠j使得Xi和Xj是重叠的，具体示例如图 7(a)所示.
膨胀操作每次均从ψ中选择包含样本数量最多的子集，在该子集与Y间通过GSCA训练得到凸线器，切掉ψ所有能够被它正确分类的子集，重复此过程，直至ψ=∅. 操作如下：
操作2：膨胀操作INFLATE(MCLP, X, Y, ε, T) 输入：初始组合凸线器MCLP={CLPk, 1≤k≤K}, X={xi, 1≤i≤N}, Y={yj, 1≤j≤M}, 精度参数ε, 挤压次数T 1.Xk={x|CLPk(x)=+1, x∈X}, CLPk∈MCLP 2.k←1, ψ←{Xi, 1≤i≤|MCLP|=K} 3.p=arg maxi{|Xi|, Xi∈ψ} 4.CLP′k=GSCA(Xp, Y, ε, T) 5.ψ={Xi|Xi∈ψ－{Xp}, ∃x∈Xi, CLP′k(x)=－1} 6.如果ψ≠∅，那么k←k+1，并转到步骤3 返回：MCLP={CLP′i, 1≤i≤k} 如图 7(b)所示，经过膨胀后原2个凸线器合并成1个，且整体分类边界向外扩张. 显然，膨胀操作也可进行多次，并且当调用GSCA算法时，如果其中挤压次数设置不为0，则意味着膨胀中包含挤压，此时膨胀不仅单纯地从内部向外扩张，还会受到外部挤压的作用，将分类边界最终定位于2个作用相对均衡的位置. 生长支持组合凸线性感知器算法[10](growing support multiconlitron algorithm，GSMA)采用膨胀操作，实现了组合凸线器的生长，能够得到更加合理的分类边界，并且简化凸线器的数量，在一定程度上提升分类器的泛化能力.
3. 文本预处理
为了将组合凸线器应用于文本分类中，首先需要用空间向量模型(vector space model，VSM)对文本进行统一表示，具体过程涉及文本的特征提取和特征赋权，然后进行组合凸线器的构造与应用. 本节主要介绍文本预处理过程，具体包括特征提取、特征项赋权方法及主成分分析(principal component analysis，PCA)降维.
3.1 特征提取
特征提取是指从预处理后的文本特征集合中，选择能够代表文本主要特征的特征子集的过程. 这些经过选择得到的特征子集，往往能够很好地区分文本的类别，同时也能较好地突出本类别的特性. 目前，常用的特征提取方法有基于文本频率DF、基于卡方检测(chi-square test，CHI)统计、信息增益等. 本节采用的是基于CHI统计的的文本特征提取方法.
CHI统计首先通过假设特征词t和文本类别ci之间符合一维自由度的χ2分布，获取特征项t对于ci的CHI值，然后将CHI值从大到小排序，选取前n个特征项构成最终的特征子集合. 其中，t对于ci的CHI值计算公式为
$$ {\chi ^2}\left( {t,{c_i}} \right) = \frac{{N \times {{\left( {AD - BC} \right)}^2}}}{{\left( {A + C} \right)\left( {B + D} \right)\left( {A + B} \right)\left( {C + D} \right)}} $$ (9) 式中：N为训练语料中的文档总数；ci为某一特定类别；t为特定的词项；A为属于ci类且包含t的文档频数；B为不属于ci类但是包含t的文档频数；C为属于ci类但是不包含t的文档频数；D为既不属于ci也不包含t的文档频数.
CHI统计考虑了特征项与类别的正相关和特征项与类别的反相关对特征项重要性的影响. 如果特征项t和类别ci正相关，说明含有特征项t的文档属于ci的概率更大；如果特征项t和类别ci反相关，说明含有特征项t的文档不属于ci的概率更大.
3.2 特征项赋权
对文本进行分类之前，需要将文本表示成统一格式以便于计算机处理. 本文采用空间向量模型[11]表示文本，它是目前使用频率最多且效果较好的常用模型之一. 在该模型中，每个文档被表示成一个权值向量，若选择了n个特征项tk，那么就有相应的n个特征权值ωk，文本d可表示为向量d=(ω1, ω2，…，ωn).
本文中特征项权值的计算采用TF·RF方法，它是一种综合分类效果较好的特征赋权方法. 其中：TF表示词频(term frequency)；RF表示相关频率[12]. 对于词项tk，令文本d关于tk的权值为tk，产生文本d的向量表示d=(ω1, ω2，…, ωn)，权值ωk的计算公式为
$$ {\omega _k} = {\rm{T}}{{\rm{F}}_k} \cdot {\rm{R}}{{\rm{F}}_k} $$ (10) 式中：TFk表示词项tk在文档d中的出现频率；RFk值的计算公式为
$$ {\rm{R}}{{\rm{F}}_k} = {\log _2}\left( {2 + \frac{{{a_k}}}{{\max \left( {1,{c_k}} \right)}}} \right) $$ (11) 式中：ak为含TFk的正类文本总数；ck为含TFk的负类文本总数.
3.3 PCA降维
在实际文本分类应用中，无需区分数据集的可分性，因为线性分类器和凸线器都是为组合凸线器服务，充当组合凸线器的主要功能模块. 因此，在本文提出的文本分类的组合凸线器模型中，只需要分别使用SMA、GSMA算法构造组合凸线器进行实验. 只是组合凸线器处理大规模数据时，参数寻优时间过长，若直接对原始文本进行处理，时间性能较差，因此，本文在利用组合凸线器进行文本分类之前，采用主成分分析(principal component analysis，PCA)[13]的方法对所有文本数据进行降维. PCA降维是一个成熟通用的降维模型，能有效控制信息损失，提取文本特征，大量地研究也表明PCA降维效果好、实用性能强[14]. 此外，针对组合凸线器在文本分类中的应用，本文只考虑了2类文本分类问题，显然，多类问题在理论上也可以做类似处理.
4. 实验结果
为了更好地研究组合凸线器在文本分类中的性能，分别将其与基于传统的K近邻方法、支持向量机方法进行了对比实验. 在实验过程中，本文通过一对多方法(one-versus-rest)将数据集中多类文本转换成2类文本进行处理，也就是每次分类时，指定一类样本为正类，其余所有类为负类. 分类的性能主要采用正确率A、准确率P、召回率R和F1作为评价指标. 正确率是指分类器正确分类的样本与总样本数之比. 准确率是指分类器正确分类的正样本数与分类器分为正类的总样本数之比. 召回率是指分类器正确分类的正样本数与实际样本数之比. F1是准确率与召回率之间的综合指标，定义如下：
$$ {F_1} = \frac{{2 \times P \times R}}{{P + R}} $$ (12) 此外，还将利用训练时间(training time)、测试时间(testing time)等作为指标，对有关分类器的时间性能进行评价.
4.1 实验数据集简介
本节的实验采用Reuters-21578[15]和RCV1_4[16]作为数据集. Reuters作为常用的文本数据集，选取其文本数目最多的前10类进行实验. RCV1_4则是文本数据集RCV1[16]语料库的一个子集，包含4类文本(CCAT、ECAT、GCAT、MCAT)，每类文本维度高达29 992维. 实验数据的详细描述见表 1.
表 1 实验数据集描述Table 1. Descriptions of data sets used in the experimentsle数据集 训练集样本数 测试集
样本数特征
维数正类 负类 Reuters Acq 1 488 5 086 2 534 2 084 Corn 159 6 415 818 Crude 349 6 225 1 621 Earn 2 709 3 865 1 658 Grain 394 6 180 1 472 Interest 289 6 285 1 057 Money-fx 460 6 114 1 540 Ship 191 6 383 1 040 Trade 337 6 237 1 634 Wheat 198 6 376 920 RCV1_4 CCAT 1 516 5 701 2 408 29 992 ECAT 1 558 5 669 GCAT 1 175 5 042 MCAT 1 978 5 239 4.2 实验结果
本文的实验平台是一台联想微机，处理器I5-2400 (3.10 GHz)，内存4 G，操作系统为32位Windows. 实验内容包括2部分：第一部分是在Reuters数据集上SMA与KNN的对比实验；第二部分是在RCV1_4上GSMA、SMA与KNN、SVMs的对比实验. 实验过程中，SMA、GSMA算法的所有精度参数设置为ε=10-3，KNN的K值通过十折交叉验证从{2, 3, …, 20}中选取，SVM使用2种类型，带参数C的线性SVM(SVM.lin)和带参数(C, γ)的高斯核SVM(SVM.rbf)，并分别使用LIBLINEAR[17]和LIBSVM[18]来执行测试. 在实验中，对于带参数C的线性SVM，因为LIBLINEAR对C值并不敏感，直接设置参数C为默认值. 而对于带参数(C，g)的高斯核SVM，LIBSVM参数的值通过十折交叉验证来选取，C和g的候选集均为{10i|i=-6, -5, …, 5, 6}.
4.2.1 SMA与SVM的对比实验
首先，将Reuters数据集上的所有数据利用PCA降维，选定25维进行实验，然后，分别利用SMA和KNN进行实验. 其中，KNN无需训练分类器，可以直接对文本进行分类，而SMA需要训练分类模型. 实验记录了KNN和SMA分类过程(训练时间与测试时间)的耗时. 实验结果见表 2.
表 2 SMA(KNN) 在Reuters上的实验结果Table 2. Experimental results of SMA (KNN) on Reuters正类 A P R F1 t/s Acq 0.926 6(0.926 2) 0.947 0(0.913 6) 0.955 1(0.995 2) 0.951 0(0.952 7) 330.30(546) Corn 0.958 6(0.981 1) 0.987 3(0.981 1) 0.970 2(1.000 0) 0.978 7(0.990 4) 39.440(530) Crude 0.970 0(0.953 4) 0.989 8(0.953 7) 0.978 1(0.998 7) 0.983 9(0.975 7) 69.831(534) Earn 0.951 5(0.654 7) 0.974 3(0.782 4) 0.942 3(0.571 8) 0.958 0(0.660 7) 342.70(516) Grain 0.942 0(0.948 3) 0.991 7(0.955 4) 0.946 7(0.991 7) 0.968 7(0.973 2) 104.09(522) Interest 0.962 1(0.960 9) 0.985 9(0.962 4) 0.974 5(0.998 4) 0.980 2(0.980 0) 54.125(530) Money-fx 0.954 2(0.950 3) 0.986 8(0.951 1) 0.964 5(0.998 7) 0.975 5(0.974 3) 80.056(581) Ship 0.969 2(0.538 3) 0.988 9(0.996 1) 0.979 2(0.524 3) 0.984 0(0.687 0) 54.962(543) Trade 0.965 3(0.901 3) 0.985 4(0.984 8) 0.978 1(0.910 8) 0.981 8(0.946 4) 78.950(525) Wheat 0.959 4(0.97 4) 0.994 6(0.974 0) 0.963 5(1.000 0) 0.978 8(0.986 8) 37.078(556) 平均值 0.955 1(0.878 9) 0.983 2(0.945 5) 0.965 2(0.899 0) 0.974 1(0.912 7) 119.154(538.3) 由表 2可以看出，SMA的平均分类正确率、平均分类准确率、平均分类召回率和平均F1值均明显高于KNN，且SMA进行文本分类所需的总时间也远远少于KNN. 因此，相比KNN，SMA花费更少的计算时间，得到了性能更好的分类模型.
4.2.2 GSMA与SMA、SVMs、KNN的对比实验
通过RCV1_4评估组合凸线器生长构造方法GSMA的性能，以SVM、KNN和原有算法SMA为基准. GSMA-T1-T2表示通过GSMA构造生长组合凸线器过程中使用了T1(取值1~4)次膨胀，每次膨胀包含T2(取值为1)次挤压. 实验过程中，该数据集上所有数据降维至20维，并且记录了所有算法的训练时间与测试时间，具体实验结果见表 3~8.
表 3 GSMA和SMA、SVM.lin、SVM.rbf、KNN在分类正确率上的对比Table 3. Comparison of GSMA, SMA, SVM.lin, SVM.rbf，KNN on classification accuracies正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 0.980 1 0.985 5 0.985 5 0.984 2 0.981 7 0.951 0 0.983 8 0.976 7 ECAT 0.964 7 0.964 7 0.971 3 0.964 7 0.960 1 0.874 2 0.964 7 0.961 3 GCAT 0.971 3 0.975 1 0.976 7 0.978 4 0.975 1 0.966 0 0.978 8 0.966 3 MCAT 0.973 4 0.975 1 0.975 1 0.970 9 0.976 7 0.912 4 0.975 9 0.968 9 表 4 GSMA和SMA、SVM.lin、SVM.rbf、KNN在分类准确率上的对比Table 4. Comparison of GSMA, SMA, SVM.lin, SVM.rbf, KNN on classification precision正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 0.954 4 0.975 8 0.981 6 0.981 5 0.965 7 0.884 9 0.975 6 0.976 7 ECAT 0.921 7 0.921 7 0.931 1 0.931 1 0.932 6 0.680 8 0.942 5 0.981 9 GCAT 0.941 0 0.946 4 0.952 7 0.959 1 0.942 0 0.937 5 0.964 2 0.936 2 MCAT 0.954 3 0.967 5 0.972 5 0.974 4 0.972 5 0.797 4 0.957 4 0.939 3 表 5 GSMA和SMA、SVM.lin、SVM.rbf、KNN在分类召回率上的对比Table 5. Comparison of GSMA, SMA, SVM.lin, SVM.rbf, KNN on classification recall正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 0.950 6 0.954 5 0.943 6 0.942 6 0.946 6 0.881 4 0.946 6 0.911 1 ECAT 0.912 8 0.912 8 0.924 4 0.946 4 0.934 4 0.777 1 0.889 5 0.899 2 GCAT 0.965 6 0.972 5 0.971 1 0.969 7 0.974 3 0.950 4 0.965 6 0.971 1 MCAT 0.948 5 0.939 4 0.947 6 0.948 0 0.947 6 0.912 1 0.954 5 0.938 0 表 6 GSMA和SMA、SVM.lin、SVM.rbf、KNN在分类F1上的对比Table 6. Comparison of GSMA, SMA, SVM.lin, SVM.rbf, KNN on classification F1正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 0.952 5 0.965 0 0.962 2 0.961 7 0.958 1 0.883 2 0.960 9 0.942 7 ECAT 0.917 2 0.917 2 0.927 7 0.938 8 0.943 9 0.725 8 0.915 3 0.908 9 GCAT 0.953 1 0.959 2 0.961 8 0.964 4 0.957 9 0.943 9 0.964 9 0.953 3 MCAT 0.951 4 0.953 3 0.959 9 0.961 0 0.959 9 0.850 8 0.956 0 0.938 6 表 7 GSMA和SMA、SVM.lin、SVM.rbf、KNN在训练时间上的对比Table 7. Comparison of GSMA, SMA, SVM.lin, SVM.rbf, KNN on training times 正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 29.418 879.262 5 543.701 13 585.21 28 667.6 0.20 2 785.95 — ECAT 46.815 1 409.900 8 542.900 20 846.80 48 389.7 0.18 3 147.67 — GCAT 40.989 1 249.430 7 569.682 18 448.60 27 432.4 0.21 3 146.66 — MCAT 56.794 1 077.446 6 724.300 13 371.70 24 231.3 0.19 3 368.20 — 表 8 GSMA和SMA、SVM.lin、SVM.rbf、KNN在测试时间上的对比Table 8. Comparison of GSMA, SMA, SVM.lin, SVM.rbf，KNN on testing times 正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 0.265 0.160 0.135 0.110 0.086 0.28 0.32 538 ECAT 0.383 0.297 0.221 0.172 0.133 0.10 0.42 557 GCAT 0.265 0.189 0.169 0.156 0.092 0.09 0.27 575 MCAT 0.468 0.333 0.278 0.234 0.148 0.09 0.31 581 由表 3~8可知，GSMA 四个指标的表现整体高于SMA，甚至部分指标超过高斯核SVM，同时，SMA的4个指标明显高于线性SVM，甚至召回率高出高斯核SVM 1.7%，其余3个指标则非常接近高斯核SVM. 另外，GSMA、SMA的全部指标均高于KNN. 需要注意的是，当GSMA的膨胀次数T1=1时，挤压次数T2=1，GSMA在数据上表现出比较显著的性能提升，达到了高斯核SVM的分类性能，且整体花费的时间也远远低于高斯核SVM，只是随着膨胀次数T1的增加，测试时间有所降低，训练时间花费更长.
5. 结论
1) 本文提出基于组合凸线器的文本分类模型. 该模型分别利用SMA、GSMA算法构造组合凸线器对文本进行分类，并通过标准文本数据集上的实验，验证了本文提出的分类模型的有效性.
2) 与利用KNN进行文本分类的方法相比，利用GSMA、SMA构造组合凸线器进行文本分类的方法，在总体分类性能上具有明显优势.
3) 相对于SVM文本分类方法，GSMA、SMA的分类正确率和运行时间基本上介于线性SVM与高斯核SVM之间. 此外，GSMA、SMA无需参数寻优，应用比高斯核SVM简单，甚至GSMA在部分数据集上的分类性能超过高斯核SVM.
-
表 1 实验数据集描述
Table 1 Descriptions of data sets used in the experimentsle
数据集 训练集样本数 测试集
样本数特征
维数正类 负类 Reuters Acq 1 488 5 086 2 534 2 084 Corn 159 6 415 818 Crude 349 6 225 1 621 Earn 2 709 3 865 1 658 Grain 394 6 180 1 472 Interest 289 6 285 1 057 Money-fx 460 6 114 1 540 Ship 191 6 383 1 040 Trade 337 6 237 1 634 Wheat 198 6 376 920 RCV1_4 CCAT 1 516 5 701 2 408 29 992 ECAT 1 558 5 669 GCAT 1 175 5 042 MCAT 1 978 5 239 
下载: 导出CSV
表 2 SMA(KNN) 在Reuters上的实验结果
Table 2 Experimental results of SMA (KNN) on Reuters
正类 A P R F1 t/s Acq 0.926 6(0.926 2) 0.947 0(0.913 6) 0.955 1(0.995 2) 0.951 0(0.952 7) 330.30(546) Corn 0.958 6(0.981 1) 0.987 3(0.981 1) 0.970 2(1.000 0) 0.978 7(0.990 4) 39.440(530) Crude 0.970 0(0.953 4) 0.989 8(0.953 7) 0.978 1(0.998 7) 0.983 9(0.975 7) 69.831(534) Earn 0.951 5(0.654 7) 0.974 3(0.782 4) 0.942 3(0.571 8) 0.958 0(0.660 7) 342.70(516) Grain 0.942 0(0.948 3) 0.991 7(0.955 4) 0.946 7(0.991 7) 0.968 7(0.973 2) 104.09(522) Interest 0.962 1(0.960 9) 0.985 9(0.962 4) 0.974 5(0.998 4) 0.980 2(0.980 0) 54.125(530) Money-fx 0.954 2(0.950 3) 0.986 8(0.951 1) 0.964 5(0.998 7) 0.975 5(0.974 3) 80.056(581) Ship 0.969 2(0.538 3) 0.988 9(0.996 1) 0.979 2(0.524 3) 0.984 0(0.687 0) 54.962(543) Trade 0.965 3(0.901 3) 0.985 4(0.984 8) 0.978 1(0.910 8) 0.981 8(0.946 4) 78.950(525) Wheat 0.959 4(0.97 4) 0.994 6(0.974 0) 0.963 5(1.000 0) 0.978 8(0.986 8) 37.078(556) 平均值 0.955 1(0.878 9) 0.983 2(0.945 5) 0.965 2(0.899 0) 0.974 1(0.912 7) 119.154(538.3)
下载: 导出CSV
表 3 GSMA和SMA、SVM.lin、SVM.rbf、KNN在分类正确率上的对比
Table 3 Comparison of GSMA, SMA, SVM.lin, SVM.rbf，KNN on classification accuracies
正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 0.980 1 0.985 5 0.985 5 0.984 2 0.981 7 0.951 0 0.983 8 0.976 7 ECAT 0.964 7 0.964 7 0.971 3 0.964 7 0.960 1 0.874 2 0.964 7 0.961 3 GCAT 0.971 3 0.975 1 0.976 7 0.978 4 0.975 1 0.966 0 0.978 8 0.966 3 MCAT 0.973 4 0.975 1 0.975 1 0.970 9 0.976 7 0.912 4 0.975 9 0.968 9
下载: 导出CSV
表 4 GSMA和SMA、SVM.lin、SVM.rbf、KNN在分类准确率上的对比
Table 4 Comparison of GSMA, SMA, SVM.lin, SVM.rbf, KNN on classification precision
正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 0.954 4 0.975 8 0.981 6 0.981 5 0.965 7 0.884 9 0.975 6 0.976 7 ECAT 0.921 7 0.921 7 0.931 1 0.931 1 0.932 6 0.680 8 0.942 5 0.981 9 GCAT 0.941 0 0.946 4 0.952 7 0.959 1 0.942 0 0.937 5 0.964 2 0.936 2 MCAT 0.954 3 0.967 5 0.972 5 0.974 4 0.972 5 0.797 4 0.957 4 0.939 3
下载: 导出CSV
表 5 GSMA和SMA、SVM.lin、SVM.rbf、KNN在分类召回率上的对比
Table 5 Comparison of GSMA, SMA, SVM.lin, SVM.rbf, KNN on classification recall
正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 0.950 6 0.954 5 0.943 6 0.942 6 0.946 6 0.881 4 0.946 6 0.911 1 ECAT 0.912 8 0.912 8 0.924 4 0.946 4 0.934 4 0.777 1 0.889 5 0.899 2 GCAT 0.965 6 0.972 5 0.971 1 0.969 7 0.974 3 0.950 4 0.965 6 0.971 1 MCAT 0.948 5 0.939 4 0.947 6 0.948 0 0.947 6 0.912 1 0.954 5 0.938 0
下载: 导出CSV
表 6 GSMA和SMA、SVM.lin、SVM.rbf、KNN在分类F1上的对比
Table 6 Comparison of GSMA, SMA, SVM.lin, SVM.rbf, KNN on classification F1
正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 0.952 5 0.965 0 0.962 2 0.961 7 0.958 1 0.883 2 0.960 9 0.942 7 ECAT 0.917 2 0.917 2 0.927 7 0.938 8 0.943 9 0.725 8 0.915 3 0.908 9 GCAT 0.953 1 0.959 2 0.961 8 0.964 4 0.957 9 0.943 9 0.964 9 0.953 3 MCAT 0.951 4 0.953 3 0.959 9 0.961 0 0.959 9 0.850 8 0.956 0 0.938 6
下载: 导出CSV
表 7 GSMA和SMA、SVM.lin、SVM.rbf、KNN在训练时间上的对比
Table 7 Comparison of GSMA, SMA, SVM.lin, SVM.rbf, KNN on training time
s 正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 29.418 879.262 5 543.701 13 585.21 28 667.6 0.20 2 785.95 — ECAT 46.815 1 409.900 8 542.900 20 846.80 48 389.7 0.18 3 147.67 — GCAT 40.989 1 249.430 7 569.682 18 448.60 27 432.4 0.21 3 146.66 — MCAT 56.794 1 077.446 6 724.300 13 371.70 24 231.3 0.19 3 368.20 —
下载: 导出CSV
表 8 GSMA和SMA、SVM.lin、SVM.rbf、KNN在测试时间上的对比
Table 8 Comparison of GSMA, SMA, SVM.lin, SVM.rbf，KNN on testing time
s 正类 SMA GSMA-1-1 GSMA-2-1 GSMA-3-1 GSMA-4-1 SVM.lin SVM.rbf KNN CCAT 0.265 0.160 0.135 0.110 0.086 0.28 0.32 538 ECAT 0.383 0.297 0.221 0.172 0.133 0.10 0.42 557 GCAT 0.265 0.189 0.169 0.156 0.092 0.09 0.27 575 MCAT 0.468 0.333 0.278 0.234 0.148 0.09 0.31 581
下载: 导出CSV
-
[1] DEVASENA C L, HEMALATHA M. Automatic text categorization and summarization using rule reduction[C]//Proc. of IEEE Conference Advances in Engineering, Science and Management (ICAESM). New York:IEEE Computer Society, 2012:594-598.
[2] SEBASTIANI F. Machine learning in automated text categorization[J]. ACM Computing Surveys, 2002, 34(1):1-47. doi: 10.1145/505282.505283
[3] VAPNIK V N. Statistical learning theory[J]. Encyclopedia of the Sciences of Learning, 2010, 41(4):3185-3188. http://d.wanfangdata.com.cn/Periodical/zdhxb201701003
[4] WEBB D. Efficient piecewise linear classifiers and applications[J]. Data Classification, 2011, 28(2):215-216. http://d.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0212847354/
[5] HERMAN G T, YEUNG K T D. On piecewise linear classifi cation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(7):782-786. doi: 10.1109/34.142914
[6] TENMOTO H, KUDO M, SHIMBO M. Piecewise linear classifiers with an appropriate number of hyper planes[J]. Pattern Recognition, 1998, 31(11):1627-1634. doi: 10.1016/S0031-3203(98)00016-8
[7] KOSTIN A. A simple and fast multi-class piecewise linear pattern classifier[J]. Pattern Recognition, 2006, 39(11):1949-1962. doi: 10.1016/j.patcog.2006.04.022
[8] LI Y J, LIU B, YANG X W, et al. Multiconlitron:a general piecewise linear classifier[J]. IEEE Transactions on Neural Networks, 2011, 22(2):276-289. doi: 10.1109/TNN.2010.2094624
[9] KEERTHI S S, SHEVADE S K, BHATTACHARYYA C, et al. A fast iterative nearest point algorithm for support vector machine classifier design[J]. IEEE Transactions on Neural Networks, 2000, 11(1):124-136. doi: 10.1109/72.822516
[10] LI Y, LENG Q, FU Y, et al. Growing construction of conlitron and multiconlitron[J]. Knowledge-Based Systems, 2014, 65:12-20. doi: 10.1016/j.knosys.2014.03.024
[11] SALTON G, MCGILL M J. Introduction to modern information retrieval[M]. New York:McDraw-Hill Co., 1983:30-42.
[12] MAN L, CHEW LIM T, JIAN S, et al. Supervised and traditional term weighting methods for automatic text categorization.[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2008, 31(4):721-735. http://d.wanfangdata.com.cn/OAPaper/oai_doaj-articles_b4d4eb71584a419f7ac2b97430ce908c
[13] JOLLIFFE I T. Principal component analysis and factor analysis[M]//Principal Component Analysis. New York:Springer, 1986:115-128.
[14] WANG L W. Is two-dimensional PCA a new technique[J]. AAS, 2005, 31(5):782-787. http://d.wanfangdata.com.cn/OAPaper/oai_doaj-articles_504bcb5ec0aedbb10003c92f626d6bcb
[15] BACHE K, LICHMAN M. UCI machine learning repository[EB/OL].[2013-04-20]. http://archive.ics.uci.edu/ml/datasets.html.
[16] LEWIS D D, YANG Y, ROSET, et al. RCV1:a new benchmark collection for text categorization research[J]. Journal of Machine Learning Research Archire, 2004, 5:361-397. http://www.citeulike.org/group/346/article/989279
[17] FAN R E, CHANG K W, HSIEH C J, et al. LIBLINEAR:a library for large linear classification[J]. Journal of Machine Learning Research, 2010, 9(12):1871-1874. http://d.wanfangdata.com.cn/OAPaper/oai_doaj-articles_803105e2ef1e9ccdc3615c7985129835
[18] CHANG C C, LIN C J. LIBSVM:a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3):27-1-27-27. http://d.wanfangdata.com.cn/OAPaper/oai_doaj-articles_1044534034490931739894b46e3576a1
-
期刊类型引用(0)
其他类型引用(1)
计量
- 文章访问数: 0
- HTML全文浏览量: 0
- PDF下载量: 0
- 被引次数: 1
