特征选择是指在文本预处理之后,在最大程度保留文本信息的基础上,为提高文本类别的区分度和删除噪音的一种降维过程^{[ 14]}。因此特征选择应该选取那些包含语义信息较多、对文本主题内容表示较强的词汇作为文本的特征词,以便提高特征选择的精度。

由于人类语言是一个典型的具有小世界特性的复杂网络^{[ 15]},因此可以利用复杂网络的特性研究语言结构,语言网络通常以字或词作为节点,以它们之间的关系作为连接边,相应的连接关系包括共现关系、概念同义、句法关系等^{[ 16]}。如果将词语间关系的强弱表示为边的权重,此时的网络转变为加权复杂网络,下面给出其重要的统计特性:

(1)加权度^{[ 17]}

节点的度表示该节点与其他节点的连接数目。将其连接边赋予权重后,节点的加权度WD_i则可以表示为:

WD_i= w_ij (1)

w_ij表示节点n_i与其连接节点n_j的边的权值。节点加权度反映了该节点与其他节点的连接强度,体现出节点的中心性。

(2)加权聚集系数^{[ 17]}

在加权复杂网络中,用加权聚集系数可以更加准确地描述节点的聚集情况,节点的加权聚集系数WC_i可表示为:

WC_i=

(2)

其中,WK_i为节点n_i邻接节点间边的权重和,称为节点n_i的加权聚集度,k_i表示节点n_i的度数。加权聚集系数可以反映节点的连接强度和密度。

(3)介数^{[ 18]}

节点介数P_i可以反映节点n_i在网络全局的影响力,即网络中用来衡量任意两节点间最短路径通过该节点的比例,它可以定量表示为:

P_i=

(3)

n_jk表示连接任意节点的最短路径的数量,n_jk(i)表示最短路径经过节点n_i的数量。

由于文本中的词语之间不是随意组合的,离散的字、词语正是通过一定的语义相关关系组合在一起,才得以形成文本。特别在中文中,丰富的词语语义关系组成了语义丰富的句子、段落、文本等,进而通过文本传递信息。传统的特征选择方法大多基于词频、文档频率等统计信息,而忽略了文本中重要的词语间的语义相关关系。本文提出的基于复杂网络的特征选择方法与传统的特征选择方法最大的不同在于,它在特征选择过程中考虑词语间语义相关关系及上下文结构因素。本文以词语间的词同现关系为基础构建文本加权复杂网络,结合文本网络的小世界特性,利用节点的综合特性进行文本特征选择。首先构建以文本特征词为节点,以特征词间语义相关关系为边,边的权重用相关关系强弱来表示的文本加权复杂网络。为了准确、全面地衡量节点的特性及其对文本主题内容的影响,本文构建了针对中文文本复杂网络的特征评估函数来衡量节点综合特性,然后利用节点综合特性提取反映文本主题的关键词作为文本的特征词。

在进行基于复杂网络的中文文本特征选择之前,需要将文本表示成复杂网络的形式。首先对中文文本进行分词、去停用词等预处理后,得到原始特征集合。

输入:文本集合D={d₁,d₂,…,d_n}。

输出:原始特征项集合T={T₁,T₂,…,T_i,…,T_n},T_i是文本d_i被表示成特征词的集合,即T_i={t_1i,t_2i,…,t_mi}。

将原始特征集合转化为复杂网络的形式,本文中的文本复杂网络被表示为加权无向图的形式,将其形式化表示为G=(N,E,W),它们分别对应网络的节点、连接边、边的权重。

输入:文本d_i对应的特征集合T_i={t_1i,t_2i,…,t_mi},以及对应特征词的词频统计信息。

输出:文本复杂网络G_i={[n₁,n₂,e₁₂,w₁₂],[n₁,n₃,e₁₃,w₁₃],…,[n_i,n_j,e_ij,w_ij],…}。

由此可以得到以特征词为节点,以特征词间相关关系为连接边,以其关系强弱为权重的文本加权复杂网络表示模型。

具体的构建方法如下:

(1)在文本预处理的过程中进行句子识别,即以标点符号作为语句的间隔,同时统计相应的词频信息,本文规定共现窗口单元为句子。

(2)为了保留文本的结构信息,同时减少无关干扰信息,本文中特征词在共现窗口的跨度最大值设为2^{[ 19]}。对于文本d对应的特征集合T={t₁,t₂,…,t_m}中的任意两个特征词t_i,t_j,如果它们同时出现在一个句子中且跨度不大于2,则将其用边连接起来,将对应特征词对转化成[n_i,n_j,e_ij,w_ij]。

(3)本文中节点连接边表示特征词间的语义相关关系,为了衡量其语义相关程度,受共现度^{[ 20]}计算方法启示,将w_ij定义为如下形式:

w_ij=

(4)

其中,fre(t_i,t_j)表示特征词t_i和t_j在文本d_i同一句子中跨度不大于2时共现的次数,fre(t_i)、fre(t_j)则表示特征词t_i和t_j在文本d_i中出现的总次数。连接边权重w_ij越大,则特征词间的语义相关关系越密切。

本文提出的基于复杂网络的中文文本特征选择算法首先通过构建文本加权复杂网络,将文本转化为加权无向图的形式,然后对文本网络中的节点特性进行分析,寻找网络中关键词节点及对文本主题类别贡献大的节点。在加权文本网络的节点特性中,节点的加权度不仅反映出该特征词的连接状况,还可以反映出该词与其他词的连接强度。加权聚集系数反映了特征词在局部的连接密度,体现了其在局部文本中的中心作用。节点介数在一定程度反映了节点在全局的枢纽作用,体现出特征词在整个文本中的连接重要性。为了衡量特征词的综合特性,本文通过构造评估函数来综合考虑加权度、加权聚集系数、节点介数等因素,并选取具有较大函数值的关键词节点作为文本的特征词。

基于复杂网络的特征选择算法流程如图1所示:

图1

	Figure Option ViewDownloadNew Window
	图1 基于复杂网络的中文文本特征选择算法流程

具体的步骤如下:

(1)对待特征选择的文档d进行预处理,包括句子识别、分词、去停用词等。

对于中文文本,文本预处理是特征选择的基础,经过分词、去停用词可以得到原始的特征集合,但是自然语言的不断变化,尤其是中文不断有新词涌现,分词软件有限的词库使得未登录词大量出现^{[ 21]},为此,本文将维基百科中的词条加入词库,使切分结果更加准确。

(2)将原始特征集合转化为文本加权复杂网络的形式,以特征词为节点、将每个句子中跨度为1、2的词语对作为节点对建立连接边,在遍历各个语句的同时,合并相同节点和连接边,并利用公式(4)计算连接边的权重,去掉网络中的孤立节点。

(3)计算节点的综合特性值以反映特征词的重要性及对主题类别的贡献率,本文构造评估函数CF,以此来衡量节点n_i综合特性:

CF_i=β₁WD_i+β₂WC_i+β₃P_i (5)

其中,WD_i、WC_i、P_i分别为节点n_i的加权度、加权聚集系数及节点介数,在计算CF_i之前,先分别进行归一化处理,β₁+β₂+β₃=1,β_i(1≤i≤3)是可调节的参数,表示相应部分的权重。

(4)利用评估函数对文本复杂网络中的节点进行计算后,可以得到每个特征词对应的函数值。按照函数值大小,将评估函数值CF_i进行排序,根据需要,选取CF_i值较大的前m个节点对应的特征词作为特征选择的结果。

由于特征选择的效果直接影响文本分类的效果,所以通过对文本分类的效果进行评价来验证本文提出的特征选择方法,使用宏平均F₁值^{[ 22]}来评价分类效果。

本文的实验语料全部来自新华网、凤凰网等抓取的新闻,包括财经类、娱乐类、教育类、体育类、科技类、军事类各500篇,实验中采用5折交叉验证法,将3 000篇文本平均分为5份,1份为测试集,4份为训练集,每份轮流作为测试集循环测试,共5次,取平均值为测试结果。具体的实验过程如下:

实验共分为4组,4组中的特征选择算法分别采用本文提出的基于复杂网络的方法、信息增益法(IG)、文档频率法(DF)及开方检验法(CHI)。每组实验过程中,首先使用中国科学院计算技术研究所的ICTCLAS进行分词,并将维基百科中的词条加入词库,然后进行去停用词处理。

在第一组基于复杂网络的特征选择方法中,利用3.2节所述的方法将文本表示成复杂网络的形式,之后用本文提出的特征选择算法进行特征选择,由于公式(5)中的β_i(1≤i≤3)在实验初始时无法确定,因此需要给定初值,通过反复实验才能够确定实验效果较好的参数取值。通过多次实验对比发现,公式(5)中β₁取0.4,β₂取0.3,β₃取0.3时分类效果较好。其他三组分别采用信息增益法、文档频率法及开方检验法进行特征选择。特征选择后,将文本表示成向量的形式。

本文统一采用KNN分类算法进行分类,其中文本相似度计算采用夹角余弦法^{[ 23]}。为了得到最佳的实验效果, 经过反复实验,KNN分类算法中的K取15。实验结果如表1所示:

表1

表1

表1 文本分类结果对比 特征维数 选择方法 300 500 700 900 1 100 1 300 1 500 复杂网络 76.96 79.12 80.63 81.79 82.13 82.54 82.36 IG 75.16 77.02 78.47 79.51 80.78 80.69 81.22 DF 69.78 71.62 73.45 74.89 76.14 76.83 77.03 CHI 74.68 76.39 77.93 78.65 80.23 80.54 81.46

表1 文本分类结果对比

将对比结果绘制成折线图,如图2所示:

图2

	Figure Option ViewDownloadNew Window
	图2 不同维数文本分类效果对比

由表1、图2可知,本文提出的基于复杂网络的中文文本特征选择算法在分类性能上比传统的信息增益、文档频率及开方检验有所提高。且在特征维数小于1 100时,分类效果随特征维数增大而增长较快,当特征维数大于1 100时,分类效果增长较慢,甚至会随着特征维数的增大,分类效果可能略有下降,这是由于随着特征维数的增大,有更多的噪音及干扰项存在的缘故。

此外β_i(1≤i≤3)的确定虽然是多次实验取得的经验数值,其确定有一定的局限性,但是β_i全都不为0,表明综合考虑节点加权度、加权聚集系数、节点介数计算节点特性,利用节点综合特性提取反映文本主题的关键词作为文本的特征词可以得到更好的效果。