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

技术领域

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

背景技术

模糊C均值聚类(Fuzz C-Means Clustering,FCM)算法是一种柔性 聚类算法，该算法结合模糊理论原理可以对数据集进行柔性划分能够 有效处理模糊数据，在大数据分析、数据挖掘等领域有着广泛应用。

FCM算法对于聚类中心的初始值选择较为敏感、聚类时间较长、 类别数需要进行指定等，由于初始值选择不合理会导致算法陷入局部 最优解等问题。针对以上问题国内外的研究学者做了大量的研究工作。

现有技术针对FCM做出的改进中，多采用MapReduce编程框架执 行计算，但是MapReduce编程框架由于在执行过程中需要进行大量的 读写和网络通信操作，因此会消耗大量的额外时间。

发明内容

为解决上述技术问题，本发明提供了一种并行非监督文本分类方 法，该并行非监督文本分类方法通过中心点计算前置的方式，能有效 降低FCM执行计算过程中的读写和通信操作量，从而大幅降低计算时 间的消耗。

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

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

计算中心点：采用层次聚类算法或密度聚类算法，计算向量化文 本数据的中心点；

切分计算：基于模糊聚类算法，以每一中心点的计算为一路，采 用多路并行的方式进行隶属度计算；

输出结果：将隶属度计算的结果作为输出结果返回。

所述步骤计算中心点中，采用Canopy算法计算。

所述步骤切分计算中，基于模糊C均值聚类算法进行计算。

所述采用Canopy算法计算过程中，以最大点密度值点作为聚类中 心点。

所述采用Canopy算法计算过程中，以最大权重值点作为聚类中心 点，最大权重值基于样本点的周围点数量、紧密度和簇相似度计算。

所述最大权重值以如下公式进行计算：

其中：ρ

采用最大点密度值点作为第一聚类中心点，除第一聚类中心点所 在簇之外其他点的最大权重值点作为第二聚类中心点。

所述多路并行的方式通过Spark环境实现。

本发明的有益效果在于：通过中心点计算前置的方式，能有效降 低FCM执行计算过程中的读写和通信操作量，从而大幅降低计算时间 的消耗。

附图说明

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

具体实施方式

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

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

计算中心点：采用层次聚类算法或密度聚类算法，计算向量化文 本数据的中心点；

切分计算：基于模糊聚类算法，以每一中心点的计算为一路，采 用多路并行的方式进行隶属度计算；

输出结果：将隶属度计算的结果作为输出结果返回。

步骤计算中心点中，采用Canopy算法计算。

步骤切分计算中，基于模糊C均值聚类算法进行计算。

采用Canopy算法计算过程中，以最大点密度值点作为聚类中心点。

采用Canopy算法计算过程中，以最大权重值点作为聚类中心点， 最大权重值基于样本点的周围点数量、紧密度和簇相似度计算。

最大权重值以如下公式进行计算：

其中：ρ

采用最大点密度值点作为第一聚类中心点，除第一聚类中心点所 在簇之外其他点的最大权重值点作为第二聚类中心点。

多路并行的方式通过Spark环境实现。

Canopy算法前置的主要原理在于：

虽然Canopy可以快速对数据集进行预分类，但是该算法对于阈值 参数T

设数据集D＝{x

定义1数据集D中所有样本点的平均距离：

定义2数据集D中样本点x

其中，

定义3从公式(2)中可以看出，密度值ρ

定义4类簇距离s

定义5数据集D被划分为k个类别，而c

其中，x

定义6由密度产生密度权重：

其中，ρ

优选的，本发明改进的Canopy算法：

输入：待聚类数据集

输出：聚类中心

设数据集D＝{x

Step1根据式算出数据集D中所有样本的密度值，选择最大的点 密度值c

Step2将所有样本点与第一个聚类中心点之间的距离小于 AvgDis(D)的从数据集合中删除；

Step3计算数据集D中剩余样本点的ρ

Step4同样计算剩余样本点到第二个聚类中心c

Step5如果数据集D不为空，则重复执行Step3到Step4；

改进的Canopy算法可以减少随机选择聚类中心带来的聚类不稳 定以及对于阈值参数T

FCM分类算法在对文本数据进行分类时，需要进行大量的距离计 算。而距离的计算需要重复迭代会消耗大量的时间和资源，因此通过 将算法并行化来提高算法的运行时间和减少资源的消耗。利用 MapReduce可以实现算法的并行化，但时MapReduce在运行过程是需 要进行大量的读写和网络通信，这使得集群的I/O开销较大。而Spark 内存计算框架在并行化时将中间的运行结果全部保存在内存中，减少 了大量的I/O操作提升了算法的运行效率，因此采用Spark框架将改进 算法并行化。

实施例1

采用上述方案，如图1所示共分为三个阶段：

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

阶段二，改进Canopy算法并行分类，该阶段主要任务是根据样本 点的最大权值找出数据集的聚类中心点以及分类的类别数。

阶段三，FCM并行化，使用阶段二产生的初始聚类中心，计算各 样本点到聚类中心的距离。如果当前中心点与前次中心点相比小于给 定的阈值，则认为算法收敛停止执行，否则以当前中心点为中心，继 续重复执行。

阶段二的过程为：

Step1，使用前期预处理的数据D″创建RDD数据集

Step2，执行Map过程：

计算RDD中所有样本点的密度值，选择密度值最大的点c

然后，计算所有样本点与选出的聚类中心c

计算RDD中剩余样本点的ρ

计算剩余样本点到聚类中心c

Step3，执行Reduce过程：判断RDD是否为空，如果不为空则重 复执行至Step2。

阶段三的过程为：

Step1，使用前期预处理的数据D″创建RDD数据集；

Step2，执行Map操作：计算RDD中每个样本点到初始聚类中心 的距离，即样本点x

Step3，执行Map操作：判断本次聚类中点与上次聚类中心的变化 是否小于某个阈值，如果小于则停止算法，得到聚类结果；否则重复 执行至Step2。

使用Spark的RDD可以大大提高算法的迭代运行，同时减少了I/O 操作时间，使得算法的整体运行效率得到提升。

以同样的数据集，对直接采用FCM聚类算法的方案和直接采用基 于Canopy的FCM算法的方案和该实施例的方案进行对比，准确率P

表1性能指标对比