一种并行监督式文本分类方法

技术领域

本发明涉及一种并行监督式文本分类方法。

背景技术

文本分类在信息检索、数据挖掘、大数据分析等领域有着广泛用途，同时也是数据处理领域的关键技术。现阶段常用的文本分类算法主要有：决策树、贝叶斯、人工神经网络、K-近邻(K-NearestNeighbor, KNN)、支持向量机和基于关联规则的分类等；另外还有用于组合单一分类方法的集成学习算法，如Bagging和Boosting等。K-近邻算法有运算速度快、分类准确率高、数学原理简单等优点，在文本分类中使用较为广泛。随着移动互联网的快速发展，使得微博、网站等文本数量呈几何数量增长，因此如何从这些海量数据是发现其内部规律和潜在价值成为当前文本数据挖掘的研究热点之一。

常用的文本分类算法在处理少量数据时，可以得到较好的分类效果。但是当面对海量数文本数据时，文本分类算法在处理速度和分类准确率已经无法满足使用要求。随着大数据和云计算技术的快速发展，研究学者发现可以使用分布式方式来对海量文本数据进行并行处理，其中最为著名并行处理算法为Google公司提出的Map-Reduce编程模型，该模型将复杂的、运行于大规模集群上的并行计算过程高度抽象为两个函数:Map和Reduce，这两个函数及其核心思路都源自函数式编程语言。Map-Reduce编程模型主要适用于大规模海量数据且对数据处理实时性要求不高的离线数据分析，但是该模型存在如下问题：

(1)表达能力有限。任何计算都必须转换为Map和Reduce两个操作，但这并不适合所有的情况，难以描述复杂的数据处理过程；

(2)磁盘IO开销大。在使用Map-Reduce编程模型处理数据时，每次都需要从磁盘读取数据，同时还需要将中间结果存入磁盘，使得 IO开销较大；

(3)延迟高。Map-Reduce编程模型在计算过程中会分解成多个 Map和Reduce任务，当前一个任务没有完成时，其他的任务无法开始。同时需要对磁盘频繁的读写，将产生较高的延迟。

发明内容

为解决上述技术问题，本发明提供了一种并行监督式文本分类方法，该并行监督式文本分类方法能有效显著提升处理效率，降低磁盘 IO开销，产生较低延迟，同时准确率几乎不受影响。

本发明通过以下技术方案得以实现。

本发明提供的一种并行监督式文本分类方法，包括如下步骤：

数据降维：对向量化的文本数据，采用聚类算法和/或决策树算法，进行文本数据的裁剪和/或降维；

并行分类：以Map-Reduce过程对文本数据进行分类。

所述步骤并行分类中，采用KNN分类模型。

所述聚类算法为K-modes算法。

所述决策树算法为C4.5算法。

采用聚类算法进行文本数据的裁剪。

采用决策树算法进行文本数据的降维。

所述Map-Reduce过程在Spark环境下执行。

所述Map-Reduce过程中，Map过程计算数据点距离，Reduce过程判断是否收敛。

本发明的有益效果在于：能有效显著提升处理效率，降低磁盘IO 开销，产生较低延迟，同时准确率几乎不受影响。

附图说明

图1是本发明的流程示意图。

具体实施方式

下面进一步描述本发明的技术方案，但要求保护的范围并不局限于所述。

如图1所示的一种并行监督式文本分类方法，包括如下步骤：

数据降维：对向量化的文本数据，采用聚类算法和/或决策树算法，进行文本数据的裁剪和/或降维；

并行分类：以Map-Reduce过程对文本数据进行分类。

步骤并行分类中，采用KNN分类模型。

聚类算法为K-modes算法。

决策树算法为C4.5算法。

采用聚类算法进行文本数据的裁剪。

采用决策树算法进行文本数据的降维。

Map-Reduce过程在Spark环境下执行。

Map-Reduce过程中，Map过程计算数据点距离，Reduce过程判断是否收敛。

实施例1

采用上述方案，如图1所示，具体采用三阶段的方式：

一、文本向量化阶段：该阶段主要是对文本数据进行前期数据清洗，数据清洗后使用汉语分词系统(例如中科院开发的 NLPIR-ICTCLAS)将文本数据向量化。

二、数据集裁剪和降维阶段：对向量化后的文本数据通过K-modes 算法对样本数据集进行裁剪减少了后期各个样本之间相似度的计算量；裁剪完成后使用C4.5算法对数据集进行特征降维，通过降维使得在后期的分类中能够有更快的速度。

三、并行化计算阶段：该阶段又分为训练分类阶段和测试分类阶段，而每个子阶段都要经过Map和Reduce两个过程，在训练集分类 Map过程会计算数据集中每一个样本到簇心的距离，同时将距离近的样本划分到该簇中并对簇中心进行更新。在测试分类阶段Map过程会计算待分类样本与训练集数据相似度。Reduce过程会根据中间缓存结果来判断算法是否收敛。

其中：

①数据集裁剪过程，采用如下算法：

输入：训练数据集D；

输出：裁剪后的训练数据集D；

Step1 K-modes聚类初始点选择

将训练数据集D划分为k个质心；

随机选取质心C

Step2计算质心C

Step3将样本点划入距离质心距离最短的类簇中；

Step4重复执行Step2,Step3，直到各个簇中样本到各簇质心的距离之和不在降低；

Step5输出裁剪后的训练数据集D。

②数据特征降维过程，采用如下算法：

输入：已分类的训练数据集D

输出：降维后的训练数据集D

设训练数据集D的样本属性特征集为A

Step1计算A中各特征对数据集D的信息增益率

a)选择信息增益率最大的特征A

b)对A

Step2对非空子集D

③训练分类阶段，采用如下过程：

输入：处理后的训练数据集D″、分类数k

输出：k个聚类

Step1从HDFS或数据库中读取训练数据集D并进行执行裁剪算法D'；

Step2对裁剪后的数据集进行降维算法得到数据集D″；

Step3使用D″创建RDD数据集；

Step3创建存储对象；

Step4执行Map过程；

读取对应分区数据；

根据给定的分类个数k，并随机选取类簇中心点O

根据加权KNN算法分别计算每个样本点到簇心的相似度并进行划分，同时簇中心进行优化；

Step5执行Reduce过程；通过判断函数来检测簇心是否发生变化，如果不在发生变化则停止运行k个簇、类簇中心点和类簇内的样本点数目，否则重复执行Step4～Step5进行簇类优化。

④测试分类阶段，采用如下过程：

输入：已经分类训练集S、测试集T

输出：分类文本数

Step1读取已经分类训练集S并创建RDD数据集；

Step2创建存储对象；

Step3将创建的RDD数据集与测试集T作为map-reduce过程的输入，通过加权KNN分类算法求出测试集中每个样本到k类簇的相似度，将进行类别划分；

Step4输出测试集中样本划分到k个类簇中数量最多的类别输出。

文本分类过程中存在大量的重复计算，而Spark的底层使用RDD 使得产生的中间结果缓存在内存中大大减少了磁盘的I/O操作，提高了算法的运行效率。

KNN算法在进行分类时，需要计算每个类别到所有样本的距离，因此算法的时间复杂度会随着样本数量的增加而增加。同时计算样本的距离也与样本的维度有关；而网络文本数据维度都比较大，因此 KNN文本分类算法处理大批量文本数据时时间复杂度会明显增加。本发明采用数据集裁剪过程，能有效降低时间复杂度。

通过剪裁后，能够降低训练数据集相似度运算；同时训练数据集的维度也导致相似度运算时间复杂度的增加，因此需要利用降维算法去掉训练集中对算法分类准确率不高的属性，以达到降低数据集维度的目的。常用的数据降维方法有主成分分析(PrincipalComponent Analysis,PCA)、线性判别分析(Linear Discriminant Analysis,LDA)以及基于信息增益的ID3算法

基于信息增益的ID3算法虽然能够有效利用已有信息，但是ID3 算法没有剪枝策略且容易出现过拟合问题；信息增益准则对可取值数目较多的特征有所偏好；只能用于处理离散分布的特征；没有考虑的缺失值问题；针对ID3算法的存在的问题，使用ID3算法的改进算法 C4.5，该算法可以在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能经会使决策树过拟合；能够对不完整数据进行处理；用信息增益率来进行属性的度量。

信息增益表示使用特征A对数据集D进行分类的不确定性减少的程度。而信息增益偏向于选择取值较多的特征进行划分，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。使用信息增益率可以对这一问题进行校正。

对比例1

采用上述方案，以同样的数据集，对比现有技术中KNN分类算法和加权KNN算法，对比性能指标包括准确率P

采用的数据集如下表1所示：

表1测试数据集

结果如表2所示：

表2各算法性能指标对比

Table 2 Comparison of performance indexes of each algorithm

可见，本发明的方案，在处理效率上有显著提升，同时准确率不受影响。