一种在MapReduce下实现的KNN改进算法

潘俊辉 王 辉 张 强 王浩畅

(东北石油大学 计算机与信息技术学院， 黑龙江 大庆 163318)

数据挖掘中的文本分类就是按照文本的主题(属性)对文本进行分类，以方便管理与分析海量的文本数据。Apache基金会开发的分布式系统基础架构Hadoop，作为云计算平台，提供了分布式文件系统组件HDFS和编程模型MapReduce，利用此组件和模型的特点可实现对文本分类的并行化处理。有关研究目前已经取得了许多成果[1-4]。本次研究，我们针对最近邻分类算法(K-Nearest Neighbor，简称“KNN”)存在的不足，提出一种在Hadoop平台MapReduce下进行子类划分的分类算法(简称“ZKNN”)，通过在训练阶段构造初级分类器，减少训练阶段的计算量，从而提高分类效率。

1 文本分类基础

文本分类是通过使用分类算法将需要分析的若干文本归入指定的某个或某几个类别的过程。用数学公式表示，即f：D→C，D={d1，d2，…，dm}，C={c1，c2，…，cn}，D为语料库中的文本集合，C为类别集合，m和n分别表示文本个数和类别个数。

Hadoop平台的MapReduce，可把并行计算过程最终抽象到map和reduce函数上。MapReduce在对大数据集进行处理时会首先将其分成很多个小数据集，把具有相同键值的数据集分到一个分区，并按键值大小排序；然后由Reduce函数取出数据和计算数据，并将结果存入HDFS中[5]。

2 对KNN算法的改进

按KNN算法进行文本分类，首先要对训练集中的文本进行预处理，并用虚拟交换矩阵(VSM)表示。如对新文本d进行测试，先要对其进行向量化的处理，然后利用距离计算公式得到d与不同文本类的距离，从中选择出距离最小的K个文本，依据它们的类别对d进行归类[6]。归类时，可以按照类别的不同对K个文本进行分组，并按式(1)计算得到距离和，然后将d归入最小距离和所对应的类别中。

(1)

式中：dis(d，di)表示文本d与di之间的距离。如果文档di属于类别ci，则y(di，ci)=1；否则，y(di，ci)=0。

在训练集中，每类文本会按照不同的主题进行划分，同一主题下又可按照侧重点的不同进一步进行划分。因此，可将不同的类别均划分成S个子类。另一方面，将文本用VSM表示后，可将其看作特征空间的一个节点(node)，这样就可根据节点的密集程度划分子类，同一子类的节点相对密集，不同子类的节点间则相对稀疏。由此，我们可以首先在类的特征空间选择分散的z个节点作为初始子类，然后采用类似聚类的方法，将该类中的节点按照距离最近的原则，把初始的z个节点划分到不同的子类中。与聚类方法不同的是，这样划分子类不需进行迭代操作，经过一次操作即可得到z个子类。划分子类的流程如下：

Step 1：按照式(2)计算类中心，然后从ci中找出距类中心最远的一个node，将其并入S中。

(2)

Step 2：计算S中所有node距类别ci中剩余node的最小距离值L，从所有最小距离node中选择出距离最大的node，将其并入S中。

Step 3：当S中的node数量达到z时，停止Step 2的执行。

Step 4：将S中的z个node看作子类，按照距离最近原则，将ci中的node归入z个不同子类中。

Step 5：计算z个子类的类中心向量。

对z的取值，一般是在类别个数n和训练集中最小类别的文本个数min|ci|之间确定某个值。

3 在MapReduce下实现分类

3.1 子类划分

基于MapReduce进行并行分类时，采用ZKNN算法实现子类的划分。为提高执行效率，我们可以通过2个job来实现：job A负责划分子类；job B用于进行中心向量的计算。具体实现过程如图1所示。

图1 划分子类的MapReduce过程

(1) 将 作为job A中map函数的输入，得到相应的class类别。利用分区函数将同一class归入到一个reduce中去执行，reduce函数的输入为 。这样，同类别的文本被归入到reduce中。接着划分子类，为reduce函数的输出。job A的map阶段和reduce阶段的伪代码分别为：

map(key，value)

{ class=GetClass (key);

Write(class，file+TFIDF);

}

reduce(key，values)

{ subSet=Huafensub(values);

for sub in subSet

for docID in sub

Write(sub+file，TFIDF);

}

(2) 将 作为job B中map函数的输入，其工作为去掉key中的file。然后，进入reduce执行。reduce会根据输入值sub计算得到InVec类中心向量，即 。job B的map和reduce的伪代码分别为：

map(key，value)

{ sub=getSub (key);

Write(sub，value);

}

reduce(key，values)

{ InVec=Compute(values)

Write(key，InVec);

}

3.2 文本分类

划分子类之后，利用ZKNN实现文本分类，由一个MapReduce完成。其中， 为map的输入，这个阶段的工作是找出距离最近的K个子类，并得到最邻近的K个文本。map的输出为 ，其中distance指文本间的距离。将map的输出作为reduce的输入，计算得到testfile的类别newcategory。因此， 为reduce的输出。下面给出该MapReduce的伪代码，实现文本分类的MapReduce过程如图2所示。

map(key，value)

{ adjacentFiles=ZKNN(key);

for file in adjacentFiles

Write(testfile，file+distance);

}

reduce(key，values)

{ newcategory=gainNew(values);

Write(key，newcategory);

}

图2 实现分类的MapReduce过程

4 实验及分类结果比较

实验使用的语料库来自复旦大学的分类语料库。选取其训练语料库中的C31-Environment(环境)、C32-Agriculture(农业)、C19-Computer(计算机)、C3-Art(艺术)、C34-Economy(经济)等5个类别，作为训练语料库。测试语料库同样选取相同的5个类别，每个类别选取700个测试文本。

采用3台同构的计算机搭建Hadoop集群。其中，使用1台机器作为集群中的主节点，剩下的2台机器用作从节点。分别采用ZKNN和经典KNN算法，比较其分类精度和所用时间。实验分别在节点个数为1、2、3的情况下进行。

在数据集和特征值个数均相同的情况下，ZKNN算法在查准率、召回率2项指标上和经典KNN算法差不多，只有少数类别的指标值会有轻微波动(见表1)。由此可见，ZKNN算法在对文本进行分类时不会影响到文本的分类性能。同时，在不影响分类精度的情况下，与经典KNN算法相比，基于MapReduce的ZKNN算法则能够有效减少文本分类所需时间(见表2)。

表1 分类性能对比

表2 完成分类所需的执行时间

5 结 语

经典的分类算法KNN具有实现简单、稳定等优点，但在处理海量数据时分类速度较慢，需要花费较多的时间。另外，KNN算法在文本预处理后就不作处理，缺少训练阶段，这也会导致计算的复杂度增加，从而影响分类效率。为了提升文本分类效率，对KNN算法进行改进，主要是通过在训练阶段构造初级分类器以减少训练阶段的计算量，并在MapReduce下予以实现。实验结果表明，面对大数据进行文本分类，改进后的算法可以在保证分类精度的情况下节省运行时间，比经典KNN算法所需的运行时间少很多。