重要性加权的文本分类特征选择方法

摘要

本发明公开了一种重要性加权的文本分类特征选择方法，包括：第一步骤：统计各候选特征在各类别中出现的数据信息，统计时特别考虑了候选特征对文本的语义代表程度，即重要性；第二步骤：使用在第一步骤得到的所述数据信息，利用相关性统计量计算公式，计算各个候选特征对各个类别的区分能力；第三步骤：汇总计算各个候选特征对所有类别的总体区分能力，并且依据各个候选特征对所有类别的总体区分能力对所有候选特征进行排序，并且输出经由排序得到的特征列表。

权利要求

1.一种重要性加权的文本分类特征选择方法，其特征在于包括：第一步骤：统计各候选特征在各类别中出现的数据信息，统计时特别考虑了候选特征对文本的语义代表程度，即重要性；

第二步骤：使用在第一步骤得到的所述数据信息，利用相关性统计量计算公式，计算各个候选特征对各个类别的区分能力；

第三步骤：汇总计算各个候选特征对所有类别的总体区分能力，并且依据各个候选特征对所有类别的总体区分能力对所有候选特征进行排序，并且输出经由排序得到的特征列表；

所述第一步骤包括：

首先，对文本进行预处理以得到包含词语、字符串、数字、符号中的一个或多个的混合序列，混合序列中的每一项记作为一个标记，而且每个标记作为一个候选特征；

然后，构建一个标记与标识符的映射表，其中为每个标记赋予以一个唯一的标识符；

此后，记录每个候选特征在各个类别样本中出现的统计数据，建立并初始化一个计数器矩阵，矩阵中的每一项对应于相应候选特征在每个类别上的统计数据；

接着，依次处理标注了类别信息的文本集合中的每个样本，统计在样本中出现的每个候选特征在该样本中的出现频次，并按照出现频次的大小进行排列；

每出现一个属于预定类别CLSi并且含有预定特征t的样本dj，就使得Ai递增α，其中α∈[0,1]，α的值表示预定特征t对预定样本dj的语义代表程度；

利用如下公式计算α：

其中|dj|表示样本dj中可能的候选特征总数，TF表示某一类别中的某一个文本的特征频数；

所述第二步骤利用如下开方检验统计量计算公式其中，Ai表示有多少包含预定特征t的样本属于预定类别CLSi；

Bi表示有多少包含预定特征t的样本不属于预定类别CLSi；

Ci表示有多少属于预定类别CLSi的样本但不包含预定特征t；

Di表示有多少样本既不属于预定类别CLSi也不包含预定特征t。

2.如权利要求1所述的重要性加权的文本分类特征选择方法，其特征在于，第二步骤也可以利用如下信息增益统计量计算公式其中

其中，Ai表示有多少包含特征t的样本属于预定类别CLSi；

Bi表示有多少包含特征t的样本不属于预定类别CLSi；

Ci表示有多少属于预定类别CLSi的样本但不包含特征t；

Di表示有多少样本既不属于预定类别CLSi也不包含特征t。

3.如权利要求1所述的重要性加权的文本分类特征选择方法，其特征在于，在第三步骤，依据各个候选特征对所有类别的总体区分能力对所有候选特征进行降序排列。

说明书

重要性加权的文本分类特征选择方法

技术领域

[0001] 本发明涉及文本挖掘与机器学习技术领域，尤其涉及一种重要性加权的文本分类特征选择方法。

背景技术

[0002] 文本分类问题是一类特殊的机器学习问题。通常的做法是，采用向量空间模型，将文本表示成多维特征空间上的点，然后再借助各种机器学习算法进行学习以及判别。在一个文本分类问题中，通常可以有成千上万的特征可用来确定这样一个语义空间。但不同特征对类别的区分能力却有很大不同，为了获得理想的分类准确率以及较高的处理效率，通常需要使用特征选择技术来从可能的候选特征集合中确定一个相对精简、更有效的一个特征子集。

[0003] 在过去几十年中，机器学习领域的专家学者提出了各种不同的特征选择方法。现有的特征选择方法大致可以分为两大类：选择法和重构法。选择法从候选特征集中确定一个子集，而重构法从候选集合转换生成一个小规模的特征集合，其中的特征通常与候选集合中的特征完全不一样。选择法因为实现简单、易于理解和解释而得到较广泛应用。在选择法中，通常采用过滤的策略，即为每个候选特征计算一个类别区分能力的统计量，然后选择取值较高的若干特征构造语义空间。常用的统计量有：信息增益、开方检验、互信息、差异率等等。

[0004] 作为一类特殊的机器学习问题，文本分类有其独特性，如特征在文本中的重要性差别很大。有些特征或词汇对确定文本的语义很重要，而另外一些却无足轻重，完全可以忽略。在计算特征类别区分能力的统计量时，现有的方法对每个特征对所在样本的代表能力(即重要性)不做区分。这在解决其他类型数据的分类问题中通常是可行的，但对于文本数据来说，却存在很大缺陷。

[0005] 因此，本发明致力于开发一种特别针对文本数据的、能够更准确地确定每个特征的类别区分能力的特征选择方法。

发明内容

[0006] 有鉴于现有技术的上述缺陷，本发明所要解决的技术问题是提供一种重要性加权的文本分类特征选择方法，改进了多种统计量的计算，可以更准确地确定每个特征的类别区分能力。

[0007] 为实现上述目的，本发明提供了一种重要性加权的文本分类特征选择方法，包括：

[0008] 第一步骤：统计各候选特征在各类别中出现的数据信息，统计时特别考虑了候选特征对文本的语义代表程度，即重要性；

[0009] 第二步骤：使用在第一步骤得到的所述数据信息，利用相关性统计量计算公式，计算各个候选特征对各个类别的区分能力；

[0010] 第三步骤：汇总计算各个候选特征对所有类别的总体区分能力，并且依据各个候选特征对所有类别的总体区分能力对所有候选特征进行排序，并且输出经由排序得到的特征列表。

[0011] 优选地，第二步骤利用如下开方检验统计量计算公式

[0012]

[0013] 其中，Ai表示有多少包含预定特征t的样本属于预定类别CLSi；

[0014] Bi表示有多少包含预定特征t的样本不属于预定类别CLSi；

[0015] Ci表示有多少属于预定类别CLSi的样本但不包含预定特征t；

[0016] Di表示有多少样本既不属于预定类别CLSi也不包含预定特征t。

[0017] 优选地，第二步骤也可以利用如下信息增益统计量计算公式

[0018]

[0019] 其中

[0020] 其中，Ai表示有多少包含特征t的样本属于预定类别CLSi；

[0021] Bi表示有多少包含特征t的样本不属于预定类别CLSi；

[0022] Ci表示有多少属于预定类别CLSi的样本但不包含特征t；

[0023] Di表示有多少样本既不属于预定类别CLSi也不包含特征t。

[0024] 优选地，第一步骤包括：

[0025] 首先，对文本进行预处理以得到包含词语、字符串、数字、符号中的一个或多个的混合序列，混合序列中的每一项记作为一个标记，而且每个标记作为一个候选特征。

[0026] 然后，构建一个标记与标识符的映射表，其中为每个标记赋予以一个唯一的标识符；

[0027] 此后，记录每个候选特征在各个类别样本中出现的统计数据，建立并初始化一个计数器矩阵，矩阵中的每一项对应于相应候选特征在每个类别上的统计数据；

[0028] 接着，依次处理标注了类别信息的文本集合中的每个样本，统计在样本中出现的每个候选特征在该样本中的出现频次，并按照出现频次的大小进行排列。

[0029] 优选地，每出现一个属于预定类别CLSi并且含有预定特征t的样本dj，就使得Ai递增α，其中α∈[0,1]，α的值表示预定特征t对预定样本dj的语义代表程度。

[0030] 优选地，利用如下公式计算α：

[0031] 其中|dj|表示样本dj中可能的候选特征总数，TF表示特征频数。

[0032] 优选地，在第三步骤，依据各个候选特征对所有类别的总体区分能力对所有候选特征进行降序排列。

[0033] 以下将结合附图对本发明的构思、具体结构及产生的技术效果作进一步说明，以充分地解释说明本发明的目的、特征和效果。

附图说明

[0034] 结合附图，并通过参考下面的详细描述，将会更容易地对本发明有更完整的理解并且更容易地理解其伴随的优点和特征，其中：

[0035] 图1是根据本发明优选实施例的基于统计量的特征选择基本流程示意图。

[0036] 图2A示出了在20Newsgroup数据集上使用信息增益(IG)做特征选择的系统性能。

[0037] 图2B示出了在20Newsgroup数据集上使用开方检验(CHI)做特征选择的系统性能。

[0038] 图3A示出了在Sector数据集上使用信息增益(IG)做特征选择的系统性能。

[0039] 图3B示出了在Sector数据集上使用开方检验(CHI)做特征选择的系统性能。

[0040] 图4A示出了在Nlpcc2014数据集上使用信息增益(IG)做特征选择的系统性能。

[0041] 图4B示出了在Nlpcc2014数据集上使用开方检验(CHI)做特征选择的系统性能。

[0042] 需要说明的是，附图用于说明本发明，而非限制本发明。注意，表示结构的附图可能并非按比例绘制。并且，附图中，相同或者类似的元件标有相同或者类似的标号。

具体实施方式

[0043] 在计算用于特征选择的统计量时，现有的方法通常忽略了各个候选特征在文本中的重要程度的差异，而把它们一视同仁，这样就不可避免地引入一些噪音，影响到准确测定每个候选特征的类别区分能力。本发明针对这一问题，提出了一种重要性加权的文本分类特征选择策略，在多个文本分类问题上的实验表明：与以往不考虑特征重要性的方法相比，本发明的策略能有效提高各种统计量对特征类别区分能力的测定，进而进一步提高特征选择的有效性。

[0044] 下面将具体描述本发明的原理以及优选实施例。

[0045] 为计算一个特征t对某个类别CLSi的区分能力，通常需要统计以下四个量：

[0046] Ai:有多少包含特征t的样本属于类别CLSi；

[0047] Bi:有多少包含特征t的样本不属于类别CLSi；

[0048] Ci:有多少属于类别CLSi的样本但不包含特征t；

[0049] Di:有多少样本既不属于类别CLSi也不包含特征t。

[0050] 有了以上四个量，开方检验(Chi-Square)统计量可以采用下面公式(1)计算得到：

[0051]

[0052] 其中，M表示需要考虑的类别总数。

[0053] 类似地，信息增益(information gain)统计量可以由公式(2)、(3)、(4)计算得到：

[0054]

[0055]

[0056] 其中

[0057] 用现有方法计算特征选择统计量(如信息增益和开方检验)时，通常采用二元策略来统计Ai、Bi、Ci及Di的值。例如，依次读取各个样本，每出现一个属于类别CLSi并且含有特征t的样本dj，就使得Ai递增1。而在本发明提出的重要性加权的特征选择策略中，不是为Ai加1，而是为Ai递增α∈[0,1]，这个α的值表示特征t在样本dj中的重要程度，即对样本dj的语义代表程度。α值的计算可以有不同的公式，一种简单的计算方式如下：

[0058]

[0059] 其中|dj|表示样本dj中可能的候选特征总数，TF表示特征频数。公式(5)中分母部分计算候选特征的最大特征频数，即出现次数最多的特征的出现个数。公式(5)实际计算了特征t在样本dj中的相对频数。一般来说，可以认为出现频繁的特征相对更重要。

[0060] 当特征t在样本dj中出现时，可以用公式(5)计算Ai和Bi，但当特征t不在样本dj中出现时，对于如何计算Ci与Di，可以采用以下三种策略：

[0061] 最小重要性MIN:用样本dj中所有特征的最小重要性值做α；

[0062] 平均重要性AVG:用样本dj中所有特征的平均重要性值做α；

[0063] 最大重要性MAX:用样本dj中所有特征的最大重要性值做α(＝1)。

[0064] 参照图1，下面给出使用重要性加权的文本分类特征选择策略的具体实施步骤。

[0065] 图1是根据本发明优选实施例的基于统计量的特征选择基本流程示意图。

[0066] 如图1所示，根据本发明优选实施例的重要性加权的文本分类特征选择方法包括：

[0067] 第一步骤101：统计各候选特征在各类别中出现的数据信息，统计时特别考虑了候选特征对文本的语义代表程度，即重要性；也就是说，统计采用了候选特征对文本的语义代表程度，即重要性；

[0068] 具体地，对于第一步骤，可以执行下述步骤：

[0069] 首先，对文本进行预处理，例如分词、标记化(tokenization)等，得到词语、字符串、数字、符号等的混合序列，混合序列中的每一项记作为一个标记(token)，而且每个标记作为一个候选特征。

[0070] 然后，构建一个标记与标识符的映射表，其中为每个标记赋予以一个唯一的标识符。

[0071] 此后，记录每个候选特征在各个类别样本中出现的统计数据，建立并初始化一个计数器矩阵，矩阵中的每一项对应于相应候选特征在每个类别上的统计数据(矩阵中的所有项的初值设置为0)。

[0072] 接着，依次处理标注了类别信息的文本集合中的每个样本，统计在样本中出现的每个候选特征在该样本中的出现频次，并按照出现频次的大小进行排列。具体地，样本的类别信息是知道的，这样就可以调整在样本中出现的每个候选特征在各类别中出现的统计数据；例如，递增的增加量由下面公式计算得到：

[0073]

[0074] 上面的公式实际计算了某个候选特征t在样本dj中的相对频数。在此认为出现频繁的特征相对更重要。

[0075] 为了后期计算的方便性，通常还保留有某个样本中所有候选特征的平均重要性、最小重要性、最大重要性的取值以及求和的结果。

[0076] 第二步骤102：使用在第一步骤得到的所述数据信息，利用相关性统计量计算公式，计算各个候选特征对各个类别的区分能力；

[0077] 特征与类别的相关性可以有多种方式进行计算，比较常见的两种是：开方检验和信息增益。

[0078] 开方检验(Chi-Square)统计量可以采用下面公式计算得到：

[0079]

[0080] 其中，M表示需要考虑的类别总数。

[0081] 类似地，信息增益(information gain)统计量可以由下面的公式计算得到：

[0082]

[0083] 而函数e(x,y)的计算方法如下：

[0084]

[0085] 由此，在本步骤中，利用第一步骤101得到的统计数据再套入上面相关性统计量计算公式得到各个候选特征对各个类别的区分能力。

[0086] 第三步骤103：汇总计算各个候选特征对所有类别的总体区分能力，并且依据各个候选特征对所有类别的总体区分能力对所有候选特征进行排序(例如，降序排列)，并且输出经由排序得到的特征列表。

[0087] 其中，对于汇总计算各个候选特征对所有类别的总体区分能力，一个文本分类问题通常是一个多类别的问题，即需要考虑的类别数量是多于一个的。与此同时，一个候选特征对不同类别的区分能力是不同的。因此，需要汇总计算各个候选特征对所有类别的总体区分能力。常用的有最大法和求和法(亦即平均法)，这里使用性能较好的求和法。

[0088] 本发明在以下3个数据集合上实验比较了本发明提出的策略与已有方法的性能差异：

[0089] ·20Newsgroups：20个类别，11293个训练样本，7528个测试样本，共有73712个候选特征；

[0090] ·Sector：105个类别，6412个训练样本，3207个测试样本，共有48988个候选特征；

[0091] ·Nlpcc2014：247个类别，11385个训练样本，11577个测试样本，共有425488个候选特征。

[0092] 这3个数据集合在类别分布均衡性上差别很大：20Newsgroups数据集合是均衡的，Sector数据集有一定的不均衡性，而Nlpcc2014数据集有相当高的类别分布不均衡性。

[0093] 实验时，使用Liblinear算法做分类，使用Stanford切分程序做分词。使用Micro-Averaging F1和Macro-Averaging F1做评价指标，分别选取值最高的前100、200、300、…、10000特征做训练与分类。分别比较了原始信息增益(IG)以及重要性加权的信息增益(IWIG)特征选择方法和原始开方检验(CHI)以及重要性加权的开方检验(IWCHI)特征选择方法在3个数据集合上的分类性能。

[0094] 尝试了MIN、AVG以及MAX三种不同的策略计算Ci与Di的值，得到了基本一致的实验结果。为节省篇幅，在下面的叙述中只给出使用MAX这种最简单的计算策略得到的实验结果。

[0095] 图2A和图2B、图3A和图3B、图4A和图4B分别给出了在3个数据集合上的实验结果。总体而言，从图2A和图2B、图3A和图3B、图4A和图4B中可以看出，本发明提出的重要性加权的文本分类特征选择策略能有效提高传统的开方检验以及信息增益特征选择方法的有效性。在类别不均衡数据集合上，使用较少特征时本发明提出的策略的优越性更明显。

[0096] 上述说明示出并描述了本发明的优选实施例，如前所述，应当理解本发明并非局限于本文所披露的形式，不应看作是对其他实施例的排除，而可用于各种其他组合、修改和环境，并能够在本文所述发明构想范围内，通过上述教导或相关领域的技术或知识进行改动，如用于改进除开方检验和信息增益的其他基于统计量Ai、Bi、Ci及Di计算的特征选择方法。而本领域人员所进行的改动和变化不脱离本发明的精神和范围，则都应在本发明所附权利要求的保护范围内。