基于密度峰值的改进K-Means文本聚类算法及其并行化

基于密度峰值的改进K-Means文本聚类算法及其并行化 An Improved K-Means Text Clustering Algorithm Based on Density Peaks and Its Parallelization first-author 袁逸铭，男，硕士生，现从事信息工程监理、文本挖掘等方面的研究。E-mail：akai_yuan@126.com 袁逸铭，男，硕士生，现从事信息工程监理、文本挖掘等方面的研究。E-mail： akai_yuan@126.com akai_yuan@126.com corresp 刘宏志, E-mail：liuhz@btbu.edu.cn 刘宏志, E-mail：liuhz@btbu.edu.cn liuhz@btbu.edu.cn 北京工商大学 计算机与信息工程学院，北京 100048 北京工商大学 计算机与信息工程学院，北京 100048 School of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048, China School of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048, China 针对K均值（K-means）聚类算法进行文本聚类时随机选取初始聚类中心点的问题，提出一种基于密度峰值进行初始聚类中心点选取的适用于文本聚类的K-means算法（DPMCSKM），为了更好地适应大规模聚类计算的要求，设计并实现了基于MapReduce的DPMCSKM并行化算法。实验结果表明，DPMCSKM算法可以有效地进行文本聚类，与K-means、基于密度峰值的快速搜索聚类算法选取初始簇中心点的K-means以及多簇球形K-means算法相比在聚类质量上均有一定的提升，在收敛速度上也有较好的表现；DPMCSKM并行化算法在可扩展性上，具有较好的加速比。 In order to solve the problem of randomly selecting initial clustering centroids for K-means text clustering, a novel Kmeans algorithm(DPMCSKM)for text clustering based on the selection of initial clustering centroids on density peaks is proposed. At the same time, to satisfy the need of large-scale calculation for clustering, the parallelization of the DPMCSKM algorithm is designed and implemented based on MapReduce. The experiment results indicate that the DPMCSKM can implement text clustering effectively. Compared with K-means, K-means based on the selection of initial clustering centroids on clustering by fast search and find of density peaks algorithm, and multi-cluster spherical K-means algorithm, the DPMCSKM algorithm has a greater clustering quality and relatively good performance in convergence speed; the parallelization of the DPMCSKM algorithm indicates a great speedup ratio for its scalability. 文本聚类 密度峰值 MapReduce K均值聚类算法 text clustering density peaks MapReduce K-means clustering algorithm 引言 1 文本聚类是文本挖掘领域的重要研究方向之一, 它通过借助统计学、机器学习等理论与方法表征文本的特征以发现文本之间的相似之处, 进而将特征相似的文本聚集成相应的类, 其目标是使不同类之间文本的相似程度尽可能低, 而同一类内文本的相似程度尽可能高 [ 1 1 ] 。根据聚类方法的不同, 文本聚类主要可分为基于层次、基于划分、基于网格、基于密度以及基于模型等方法。 K-means算法作为基于划分的经典聚类算法之一, 因其原理简单、实现容易等特点, 被广泛地应用在文本聚类领域。但K-means算法自身存在一些缺陷, 如K值需要事前由人工确定, 随机选取的初始聚类中心点可能会导致聚类结果陷入局部最优解, 对离群点较敏感以及不同的距离度量标准对聚类结果有影响, 因此对K-means算法的改进也围绕着以上方面开展 [ 2 2 ] 。如Tunali等 [ 3 3 ] 对适用于文本聚类的球面K-means(spherical K-means, SKM)算法进行了改进, 使其在满足参数限制条件的情况下将一个点同时划分给多个簇, 从而加快算法的收敛速度, 但其采取随机选取的方式确定初始聚类中心, 算法的稳定性较差; 刘颖莹等 [ 4 4 ] 提出了一种基于密度峰值的文本聚类算法, 在文献[ 5 5 ]的基础上, 将余弦相似度作为聚类的距离度量标准, 并通过实验证明了其在聚类性能以及鲁棒性上的提升, 但未给出利用决策图选取聚类中心点的具体方法。 本文在文献[ 3 3 ]的基础上, 引入密度峰值的相关概念, 提出一种基于密度峰值的改进K-means文本聚类算法(density peaks multi-cluster spherical Kmeans, DPMCSKM)。由于文本数据通常是高维的, 随着数据量的增长, 单机的处理能力将难以胜任文本聚类的计算需求, 因此本文将DPMCSKM与目前主流的大数据生态系统之一Hadoop中的MapReduce计算框架相结合, 设计了一种基于MapReduce的DPMCSKM并行化算法, 以满足文本聚类计算规模的要求。 相关概念 1 密度峰值 2 文献[ 5 5 ]提出了一种基于密度峰值的快速搜索聚类算法(clustering by fast search and find of density peaks, CFSFDP), 定义了"密度峰值点"的概念。根据该定义, 若待聚类点集中的某个点, 相对于其周围的点居于更中心的位置(称该点密度相对较大), 同时该点到比它密度更大的点的距离相对较远, 则可以将该点称作密度峰值点。 对于具有 n 个点的数据集 D 中的点 i , 有两个参数: 1) 点密度 ρ i (简称密度 ρ i ) http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465277&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465277&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465277&type=middle 其中, http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465328&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465328&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465328&type=middle 表示点 i 与点 p 之间的距离; d cut_off 表示截断距离, 由人工给定, 有文献指出截断距离可根据所有点之间的距离小于 d cut_off 所占的比例 σ 决定 [ 6 6 ] 。由(1)式可知, ρ i 在数值上表示与其距离小于 d cut_off 的点的个数。 2) 到更高密度点的最短距离 γ i (简称距离 γ i ) http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465284&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465284&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465284&type=middle 由(2)式可知, 当 ρ i 最大时, γ i 为点 i 到其他点的最远距离; 否则, γ i 为到比点 i 密度更大点的最短距离。 上述两参数可组成二元数对〈 ρ , γ 〉。以 ρ 为横坐标, γ 为纵坐标, 可以得到一个关于 D 的决策图 G , 如 图 1 图 1 所示。在 G 中选取 ρ 、 γ 值均较大的若干个点(由人工选取, 其中一种选取方案如 图 1 图 1 框内点所示)即密度峰值点作为聚类中心点, 然后将剩余的点分配到离该点最近的聚类中心点所在的簇中, 最终得到聚类结果。 文献[ 5 5 ]中的距离度量标准均为欧氏距离。 多簇球面K-Means算法 2 作为文本聚类的元素, 文本数据本身是非数值型的, 因此需要将其转换成数值型数据。向量空间模型 [ 7 7 ] 作为经典的文本表示方法之一, 将由 n 个文本构成的文本数据集 T ={ t 1 , t 2 , …, t n }映射成文本向量空间 V ={ v 1 , v 2 , …, v n }。在向量空间 V 中, 具有 m 个特征数的文本向量 v i =( w i 1 , w i 2 , …, w im )T, 其中, w ij ( j =1, 2, …, m )表示第 i 个文本向量的第 j 个特征, 其值为该特征词在文本 t i 中的权重。 根据聚类要求的不同, K-means算法的距离度量标准主要可分为欧氏距离、曼哈顿距离、余弦距离以及相关距离等 [ 8 8 ] 。王彬宇等 [ 9 9 ] 在文献中阐述了使用余弦相似度作为文本聚类的距离度量标准的合理性。文本向量 v i 与 v j 余弦相似度可以表示为: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465292&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465292&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465292&type=middle 其中 m 为 v i 与 v j 的特征数。由(3)式可知, 余弦相似度 S 〈 i , j 〉 ∈[0, 1]。因此当 S 〈 i , j 〉 越大时, 代表两个文本的相似性越高; 反之则代表两个文本的相似性越低。 而SKM算法 [ 10 10 ] 则是在K-means算法的基础上, 根据余弦相似度计算公式的特点, 预先在聚类前对每个文本向量进行了标准化:将 v i 转换成标准化向量 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465296&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465296&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465296&type=middle 其中, http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465330&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465330&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465330&type=middle 。 一方面, (3)式中的 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465332&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465332&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465332&type=middle 作为除数可以省略计算, 因此文本向量标准化后的余弦相似度 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465334&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465334&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465334&type=middle , 在一定程度上简化了对 S 〈 i , j 〉 的运算; 另一方面, 通过对文本向量的标准化, 可以减少长文本或高频词对文本相似性的计算的影响。 文献[ 3 3 ]提出的多簇球面K-means算法(multicluster spherical K-means, MCSKM)在SKM算法的基础上, 给定了两个参数MAC和SRL: 1) MAC:最大可分配簇数(maximum assignable clusters), 即一个点最多可以分配给不超过MAC个簇。MAC的参考范围为: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465300&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465300&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465300&type=middle 其中 k 表示聚类的簇数。特别地, 当MAC=1时, MCSKM算法退化成SKM算法。 2) SRL:相似性比率界限(similarity ratio limit), 对于点i, 若簇中心点 C j 满足: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465306&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465306&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465306&type=middle 其中 C best 表示与点 i 余弦相似度最高的簇中心点, 在同时满足MAC的条件下, 将 i 分配给 C j 所在的簇中。SRL的参考范围为: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465309&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465309&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465309&type=middle 综上, MCSKM算法通过MAC和SRL两个参数的给定, 在一次聚类迭代中将待聚类点同时分配给满足条件的一个或多个簇, 从而加快聚类的收敛速度。MCSKM算法的描述如下: 算法1   MCSKM算法 输入:标准化文本向量集 V , 聚类簇数 k , 最大可分配簇数MAC, 相似性比率界限SRL 输出:对 V 的文本聚类结果 过程: 1) 随机选取 k 个 V 中的文本向量作为初始簇中心点C; 2) 对于 V 中的每一个文本向量 v i : ① 计算 v i 与当前各簇中心点的余弦相似度; ② 按降序排序余弦相似度; ③ 将 v i 分配给余弦相似度最高的簇中心点 C best 所在的簇; ④ 按余弦相似度从高到低的顺序, 在满足参数MAC与SRL的情况下将 v i 分配给除 C best 外的簇中心点所在的簇; 3) 根据各簇文本向量的分配情况重新计算并确定新的簇中心点 C '; 4) 若 C '与上一次迭代确定的簇中心点保持一致, 即簇中心点在一次迭代后没有发生变化, 则结束算法, 否则, 返回到过程2)。 MapReduce 2 MapReduce是大数据生态系统Hadoop中的重要组成部分之一, 作为一种分布式计算框架, 它采取分治的思想将大规模计算任务划分成若干个更小规模的计算任务, 然后将其分发给数据分片所在的或逻辑上靠近的计算节点来完成并行化, 其中最为关键的是Map和Reduce两个计算函数。 当提交MapReduce任务时, 不同分片上的数据先转化为键值对〈key, value〉的形式, 然后通过Map函数读入这些键值对作为MapReduce的输入〈key1, value1〉, 经过Map函数的相关计算, 产生中间键值对列表List[〈key2, value2〉]输出。为了减少I/O开销, 在保持键值对形式不变的情况下, 可以应用Combine函数对Map的输出结果预先进行合并, 得到键值对列表List[〈key2, value2'〉]。接下来经过Shuffle过程, 将具有相同的key值的键值对进行分区和合并, 以在Merge之后形成键值对列表〈key2, List[value2]〉作为Reduce函数的输入。最后经过Reduce函数的相关计算, 输出结果键值对List[〈key3, value3〉]。 Hadoop中的MapReduce的工作流程 [ 11 11 ] 如 图 2 图 2 所示。 DPMCSKM算法 1 1.2节所述的MCSKM算法尽管适用于文本聚类, 同时通过设置条件参数, 加快了聚类的收敛速度, 但仍未解决初始中心点的选取问题, 算法的稳定性较差。由 图 1 图 1 可知, 决策图 G 中位于右上角的点具有点密度高、到更高密度点的最短距离的特征, 是作为密度峰值点的参考依据, 但仅通过决策图 G 并不能得到具体的选取结果, 仍然需要人工选取。 本文针对决策图 G 中密度峰值点的选取问题, 将密度 ρ 与距离 γ 相乘, 得到参数密度距离: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465315&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465315&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465315&type=middle 由(4)式可知, 密度距离 ζ 越大, 则该点密度越大, 同时与更高密度点的距离越远, 成为密度峰值点的可能性就越大。以 ζ 值从大到小的次序为序号作为横坐标, ζ 值作为纵坐标, 可以得到一个关于 V 的新决策图 G ', 如 图 3 图 3 所示。 由 图 3 图 3 可知, 随着横坐标序号的逐渐增大, ζ 值单调减少且成逐渐收敛的趋势。因此, 可以认为序号- ζ 函数的收敛过程也是样本点从密度峰值点(图 3框内点)到非密度峰值点的转变过程 [ 12 12 ] 。然而与欧氏距离不同, 余弦相似度 S ∈[0, 1], 即距离 γ ∈[0, 1]。同时, 由于余弦相似度侧重于区分两个向量在方向上的差异, 因此从数值上看 γ 的区分程度没有欧氏距离大; 而点密度 ρ ∈[1, n ], 受样本点个数 n 的影响较大, 故 图 3 图 3 所示的密度距离 ζ 会因 ρ 与 γ 在数值比例上的差异不能正确反映密度峰值点的排列情况。 因此本文先将 ρ 与 γ 进行离差标准化, 得到参数 ρ 与 γ , 然后计算 ρ 与 γ 离差标准化后的密度距离 ζ ˉ。根据密度峰值的原理, ζ 最大的点必为聚类中心点(点密度最大, 到更高密度点的距离最远), 故对于 ρ i , 有 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465318&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465318&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465318&type=middle 其中: n 为样本点的个数, q 为 ρ 值最大点的序号, ρ max 与 ρ min 为除点 q 外其余点中 ρ 的最大值与最小值。 对于 γ i , 有 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465321&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465321&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465321&type=middle 其中: p 为 γ 值最大点的序号, γ max 与 γ min 分别为除点 p 外其余点中 γ 的最大值与最小值。 对于离差标准化后的密度距离 ζ , 有 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465322&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465322&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465322&type=middle 由(5)~(7)式可知, 离差标准化可以在一定程度上消除 ρ 与 γ 在数值比例上的差异, 从而更加合理地利用密度距离选取密度峰值点。 本文选取以降序排列的前 k 个 ζ 值所对应的文本向量为密度峰值点并作为初始聚类中心点, 然后应用MCSKM算法进行文本聚类。DPMCSKM算法的描述如下: 算法2   DPMCSKM算法 输入:文本向量集 V , 截断距离参数 σ , 聚类簇数 k , 最大可分配簇数MAC, 相似性比率界限SRL 输出:对 V 的文本聚类结果 过程: 1) 将 V 中所有的文本向量标准化, 得到标准化文本向量集 V ; 2) 计算 V 中所有文本向量间的余弦相似度 S , 得到截断距离 d cut_off , 使得 S > d cut_off 占所有文本向量间余弦相似度的比例为 σ ; 3) 根据 d cut_off , 计算各文本向量的密度 ρ ; 4) 根据 ρ , 计算各文本向量的距离 γ , 由(5)和(6)式对 ρ 和 γ 分别进行离差标准化并得到密度距离 ζ , 选取以降序排列的前 k 个 ζ 值所对应的文本向量为密度峰值点并作为初始聚类簇中心点 C ; 5) 对于 V 中的每一个文本向量 v i : ① 计算 v i 与当前各簇中心点的余弦相似度; ② 按降序排序余弦相似度; ③ 将 v i 分配给余弦相似度最高的簇中心点 C best 所在的簇; ④ 按余弦相似度从高到低的顺序, 在满足参数MAC与SRL的情况下将 v i 分配给除 C best 外的簇中心点所在的簇; 6) 根据各簇文本向量的分配情况重新计算并确定新的簇中心点 C '; 7) 若 C '与上一次迭代确定的簇中心点保持一致, 即簇中心点在一次迭代后没有发生变化, 则结束算法, 否则, 返回到过程5)。 基于MapReduce的DPMCSKM并行化算法 1 一方面, 由文本数据转换成的文本向量通常是高维的, 随着文本数据规模的不断增大, 单机环境将难以满足聚类计算的需求; 另一方面, 本文提出的DPMCSKM算法在选取初始聚类中心点时需要预先计算文本向量之间的余弦相似度, 此阶段的计算开销较大。因此, 本文设计并实现了基于MapReduce的DPMCSKM并行化算法, 算法由5个MapReduce Job构成, 其流程示意图如 图 4 图 4 所示, 其中初始的文本向量集的数据分片以编号0, 1, …, M-2, M-1表示, 经过标准化处理后的文本向量集的数据分片以编号0', 1', …, M-2', M-1'表示。基于MapReduce的DPMCSKM并行化算法的描述如下。 算法3   基于MapReduce的DPMCSKM并行化算法 Job 1:文本向量集 V 的标准化。基于1.2节所述的文本向量标准化的原理, Map任务的工作节点分别将各个数据分片上的文本向量 v i 转化为文本标准向量 v i , 形成标准化文本向量集 V 。 Job 2:截断距离 d cut_off 的计算。Map任务的工作节点分别计算各个数据分片上的文本向量与 V 中向量的余弦相似度, 输出所在数据分片的以降序排列的前 n · σ %个余弦相似度, 其中 n 为 V 中文本向量的总数目; Reduce任务负责统计各Map工作节点输出的余弦相似度, 得到截断距离 d cut_off 。 Job 3:密度 ρ 的计算。Map任务的工作节点分别统计各个数据分片上的文本向量与 V 中余弦相似度大于 d cut_off 的文本向量个数, 输出得到各文本向量的密度 ρ 。 Job 4:距离 γ 、离差标准化后的密度距离 ζ 的计算以及 k 个初始聚类中心点的确定。Map任务的工作节点分别计算各个数据分片上的文本向量的距离 γ , 然后对 ρ 与 γ 进行离差标准化, 进而计算密度距离 ζ , 并输出以降序排列的前 k 个 ζ 值所对应的文本向量为密度峰值点并作为初始聚类簇中心点。 Job 5:MCSKM迭代聚类。首先Map任务的工作节点分别计算各个数据分片上的文本向量到当前各簇中心点之间的余弦相似度, 按降序排序后, 输出满足MAC与SRL的键值对〈key4, value4〉, 其中key4表示分配的簇编号, value4表示分配到簇key4的文本向量; 为了减少I/O开销, 通过Combine函数将具有相同键key4的键值对进行合并, 输出键值对和〈key4, 〈Count(value4), Sum(value4)〉〉, Count (value4)表示当前Map节点具有键key4的键值对个数, Sum (value4)表示当前Map工作节点具有相同键key4的文本向量的特征在数值上的和; Reduce任务负责合并具有相同键key4的键值对, 最终计算出新的簇中心点〈key4, value5〉。当生成的新簇中心点与上一次迭代确定的簇中心点一致时, 算法结束; 否则, 将新簇中心点作为下一次迭代的初始聚类簇中心点, 再次运行Job 5。 实验结果与分析 1 为验证本文提出的算法的有效性, 将本文提出的DPMCSKM算法与K-means、基于CFSFDP算法选取的密度峰值点作为初始簇中心点的K-means (简称DPK-Means)和MCSKM算法进行聚类质量评估和收敛速度的对比, 并进行并行化加速比评估实验。 所有实验的聚类簇数 k =6;K-means算法和MCSKM算法均运行20次, 取平均结果; MCSKM和DPMCSKM及其并行化算法的参数 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465336&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465336&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465336&type=middle , SRL=0.1;DPK-means和DPMCSKM及其并行化算法的参数 σ =6%。 实验数据集 2 本文的所有实验数据集均来自由清华大学自然语言处理实验室提供的中文文本分类数据集THUCNews [ 13 13 ] , 其根据新浪新闻2005-2011年间的历史数据筛选过滤生成, 总计包含约74万篇文档。在原始数据的基础上, THUCNews重新整合划分出财经、彩票、房产、股票等14类候选分类新闻文档。 受实验条件的限制, 本文从上述数据集中选择体育、娱乐、家居、时政、科技、财经6个类别作为实验的聚类类别, 并分别从每类中随机选取200、500、800、1 000、2 000和4 000篇新闻文档作为实验数据集 D 1 、 D 2 、 D 3 、 D 4 、 D 5 和 D 6 。在实验前, 对实验数据集中的文档进行了预处理, 包括中文分词、去停用词、文本特征选择、文本特征词权重表示和文本向量空间的建立等, 使用中科院汉语分词系统NLPIR进行中文分词, TF-IDF模型对文本进行特征表示。 实验环境 2 本文的所有实验均在由VMware虚拟机平台环境搭建的Hadoop集群上完成, Hadoop集群中各节点的类型如 表 1 表 1 所示, 其中node1为Master(主)节点, node2、node3、node4为Slave(从)节点。 编号 主机名称 IP地址 节点类型 1 node1 192. 168. 214. 201 NameNode、DataNode、NodeManager、ResourceManager 2 node2 192. 168. 214. 202 SecondaryNameNode、DataNode、NodeManager 3 node3 192. 168. 214. 203 DataNode、NodeManager 4 node4 192. 168. 214. 204 DataNode、NodeManager Hadoop集群的硬、软件配置如下:各节点分配的内存为2 GB, 分配的硬盘空间为20 GB; 虚拟机平台为VMware Workstation Pro 14.1.3 build-9474260, 操作系统为CentOS 7. 5. 1804, Hadoop版本为2. 7. 3, JDK版本为1.8. 0_65, 开发环境为Eclipse-Java-Pho-ton4.8. 0-Linux。 聚类质量评估实验 2 选取调整兰德系数(adjusted rand index, ARI)和标准化互信息(normalized mutual information, NMI)作为对聚类质量的评估标准, 两种评估指标均用于衡量聚类结果与真实类别数据之间的吻合程度, 其中ARI和NMI的取值范围分别为[-1, 1]和[0, 1] , 两者的值越高, 则代表聚类结果与真实类别数据越吻合, 聚类质量越好。本实验使用的数据集为 D 1 、 D 2 、 D 3 和 D 4 , 实验结果如 表 2 表 2 和 表 3 表 3 所示。 算法 D 1 D 2 D 3 D 4 K-Means 0. 609 0. 642 0. 692 0. 700 DPK-Means 0. 639 0. 665 0. 723 0. 744 MCSKM 0. 670 0. 691 0. 765 0. 783 DPMCSKM 0. 689 0. 712 0. 794 0. 813 算法 D 1 D 2 D 3 D 4 K-Means 0.687 0.712 0.738 0.751 DPK-Means 0.722 0.730 0.743 0.777 MCSKM 0.725 0.731 0.771 0.784 DPMCSKM 0.736 0.748 0.787 0.797 由 表 2 表 2 和 表 3 表 3 可知, 随着数据集文档数目的不断增大, 4种算法的ARI与NMI值均逐渐增大, 而本文提出的DPMCSKM算法的ARI与NMI值均大于其他3种算法, 与K-means、DPK-means和MCSKM算法相比在所使用的4个数据集( D 1 、 D 2 、 D 3 和 D 4 )下的ARI值分别平均提升了13.7%、8. 5%和3.4%;NMI值分别平均提升了6. 2%、3.2%和1.9%。本实验表明, 本文提出的DPMCSKM算法聚类所得到的结果与真实类别数据的吻合程度即聚类质量高于其余3种算法, 因此在一定程度上可以有效地进行文本聚类。 收敛速度评估实验 2 以算法收敛所需要迭代的次数作为收敛速度评价指标, 算法收敛的条件为聚类中心点不再变化。算法收敛所需要迭代的次数越少, 则说明算法的收敛速度越快。本实验使用的数据集为 D 1 、 D 2 、 D 3 和 D 4 , 实验结果如 表 4 表 4 所示。 算法 D 1 D 2 D 3 D 4 K-Means 13.45 17.95 18.9 23.15 DPK-Means 9 7 39 35 MCSKM 15.05 21.1 26.8 27.15 DPMCSKM 13 10 15 23 由 表 4 表 4 可知, DPMCSKM算法在不同的数据集下的迭代次数均小于K-means和MCSKM算法, 且在所使用的四个数据集( D 1 、 D 2 、 D 3 和 D 4 )下分别平均低17. 2%和31.4%;与DPK-Means算法相比, 迭代次数有高有低:在 D 1 、 D 2 时分别高44.4%和42. 9%, 在 D 3 、 D 4 时分别低61.5%和34.3%, 这是由于DPK-Means算法在选取初始簇中心时采取欧氏距离作为距离度量标准, 与采取余弦相似度相比对数据集更敏感。对比在数据集 D 2 和 D 4 下的实验结果可以发现, 与K-means和MCSKM算法相比, DPMCSKM算法迭代次数的增长幅度较大, 这是由于一方面截断距离参数固定, 而另一方面数据集的规模增大, 进而导致DPMCSKM算法在确定初始聚类中心点时自适应性不够强, 故在进行聚类迭代时次数增长较快。但综合来看, 4种算法中本文提出的DPMCSKM算法收敛所需的次数相对较低且变化较稳定, 因此本实验表明, DPMCSKM算法的收敛速度在一定程度上有所提升。 并行化加速比评估 2 对本文提出的基于MapReduce的DPMCSKM并行化算法在1至4个节点的Hadoop集群上的运行时间进行比较, 以并行计算的加速比作为评价指标。算法的加速比越高, 则说明算法的可扩展性与并行化性能越好。本实验使用的数据集为 D 2 、 D 4 、 D 5 和 D 6 , 实验结果如 图 5 图 5 所示。 由 图 5 图 5 可知, 随着数据集文档数目的不断增大, 不同节点下算法运行的加速比均有所提升; 当节点个数逐渐增多时, 加速比的变化率也不断增大, 并向着线性关系的趋势接近。实验表明, 本文提出的基于MapReduce的DPMCSKM并行化算法在可扩展性方面, 在一定程度上具有较好的加速比。 结语 1 本文提出了一种基于密度峰值的改进K-means文本聚类算法DPMCSKM。算法根据密度峰值的相关概念, 针对文本聚类的特点, 对点密度和到更高密度点的最短距离进行离差标准化, 重新定义并计算了密度距离以选取密度峰值点和初始聚类中心点, 在一定程度上避免了K-means算法随机选取初始聚类中心点的缺陷。同时, 为了更好地适应文本聚类的计算要求, 设计并实现了一种基于MapReduce的DPMCSKM并行化算法。实验结果表明, 本文提出的DPMCSKM算法在聚类质量和收敛速度上均有所提升, DPMCSKM并行化算法具有良好的加速比, 因此可以有效地进行文本聚类。在接下来的工作中, 将继续对密度峰值在文本聚类中的应用进行研究, 如聚类簇数和截断距离参数的确定等, 以进一步提升算法的聚类质量和自适应性。 参考文献 曹晓.文本聚类研究综述[J].情报探索, 2016(1): 131-134. CAO X. Review of researches on text clustering[J]. Information Research , 2016(1):131-134(Ch). 丛思安, 王星星.K-means算法研究综述[J].电子技术与软件工程, 2018(17):155-156. CONG S A, WANG X X. A survey of K-means algorithm research[J]. Electronic Technology & Software Engineering , 2018(17):155-156(Ch). TUNALI V, BILGIN T, CAMURCU A. An improved clus-tering algorithm for text mining:Multi-cluster spherical K-means[J]. International Arab Journal of Information Technology , 2016, 13(1):12-19. 刘颖莹, 刘培玉, 王智昊, 等.一种基于密度峰值发现的文本聚类算法[J].山东大学学报(理学版), 2016, 51(1): 65-70. LIU Y Y, LIU P Y, WANG Z H, et al . A text clustering algorithm based on find of density peaks[J]. Journal of Shandong University ( Natural Science ), 2016, 51(1):65-70(Ch). RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science , 2014, 344:1492-1496. 张嘉琪, 张红云.拐点估计的改进谱聚类算法[J].小型微型计算机系统, 2017, 38(5):1049-1053. ZHANG J Q, ZHANG H Y. Improved spectral clustering based on inflexion point estimate[J]. Journal of Chinese Computer Systems , 2017, 38(5):1049-1053(Ch). SALTON G, WONG A, YANG C S. A vector space model for automatic indexing[J]. Communications of the ACM , 1975, 18(1):613-620. DOI:10.1145/361219. 361220. 林滨.K-means聚类的多种距离计算方法的文本实验比较[J].福建工程学院学报, 2016, 14(1):80-85. LIN B. Experimental comparison of K-means text clustering by varied distance calculation methods[J]. Journal of Fujian University of Technology , 2016, 14(1):80-85 (Ch). 王彬宇, 刘文芬, 胡学先, 等.基于余弦距离选取初始簇中心的文本聚类研究[J].计算机工程与应用, 2018, 54 (10):11-18. WANG B Y, LIU W F, HU X X, et al . Research on text clustering for selecting initial cluster center based on Cosine distance[J]. Computer Engineering and Applications , 2018, 54(10):11-18(Ch). DHILLON I S, MODHA D S. Concept decompositions for large sparse text data using clustering[J]. Machine Learning , 2001, 42(1-2):143-175. 夏靖波, 韦泽鲲, 付凯, 等.云计算中Hadoop技术研究与应用综述[J].计算机科学, 2016, 43(11):6-11+48. XIA J B, WEI Z K, FU K, et al . Review of research and application on Hadoop cloud computing[J]. Computer Science , 2016, 43(11):6-11(Ch). 兰旭.基于密度峰值的一种文本聚类优化算法的研究与实现[D].长沙: 国防科学技术大学, 2016. LAN XU. The Research and Implementation of a Novel Text Clustering Algorithm Based on Density Peak [D]. Changsha: National University of Defense Technology, 2016(Ch). 孙茂松, 李景阳, 郭志芃, 等.THUCTC: 一个高效的中文文本分类工具包[EB/OL].[2018-10-20] . http :// thuctc . thunlp . org / http://thuctc.thunlp.org/ . SUN M S, LI J Y, GUO Z P, etal. THUCTC: An Efficient Chinese Text Classifier[EB/OL].[2018-10-20] . http :// thuctc . thunlp . org / http://thuctc.thunlp.org/ (Ch). 10.14188/j.1671-8836.2019.05.006 TP301.6 whdxxblxb-65-5-457 国家自然科学基金（61877002）；北京市自然科学基金（4162019） 2018-12-12 2019-10-24 2020-12-10 版权所有© 2019 《武汉大学学报(理学版)》编辑部 Copyright © 2019 Journal of Wuhan University(Natural Science Edition). All rights reserved. 2019 武汉大学学报(理学版) 5 65