0 引言

文本聚类是文本挖掘领域的重要研究方向之一, 它通过借助统计学、机器学习等理论与方法表征文本的特征以发现文本之间的相似之处, 进而将特征相似的文本聚集成相应的类, 其目标是使不同类之间文本的相似程度尽可能低, 而同一类内文本的相似程度尽可能高^[1]。根据聚类方法的不同, 文本聚类主要可分为基于层次、基于划分、基于网格、基于密度以及基于模型等方法。

K-means算法作为基于划分的经典聚类算法之一, 因其原理简单、实现容易等特点, 被广泛地应用在文本聚类领域。但K-means算法自身存在一些缺陷, 如K值需要事前由人工确定, 随机选取的初始聚类中心点可能会导致聚类结果陷入局部最优解, 对离群点较敏感以及不同的距离度量标准对聚类结果有影响, 因此对K-means算法的改进也围绕着以上方面开展^[2]。如Tunali等^[3]对适用于文本聚类的球面K-means(spherical K-means, SKM)算法进行了改进, 使其在满足参数限制条件的情况下将一个点同时划分给多个簇, 从而加快算法的收敛速度, 但其采取随机选取的方式确定初始聚类中心, 算法的稳定性较差; 刘颖莹等^[4]提出了一种基于密度峰值的文本聚类算法, 在文献[5]的基础上, 将余弦相似度作为聚类的距离度量标准, 并通过实验证明了其在聚类性能以及鲁棒性上的提升, 但未给出利用决策图选取聚类中心点的具体方法。

本文在文献[3]的基础上, 引入密度峰值的相关概念, 提出一种基于密度峰值的改进K-means文本聚类算法(density peaks multi-cluster spherical Kmeans, DPMCSKM)。由于文本数据通常是高维的, 随着数据量的增长, 单机的处理能力将难以胜任文本聚类的计算需求, 因此本文将DPMCSKM与目前主流的大数据生态系统之一Hadoop中的MapReduce计算框架相结合, 设计了一种基于MapReduce的DPMCSKM并行化算法, 以满足文本聚类计算规模的要求。

1 相关概念 1.1 密度峰值

文献[5]提出了一种基于密度峰值的快速搜索聚类算法(clustering by fast search and find of density peaks, CFSFDP), 定义了"密度峰值点"的概念。根据该定义, 若待聚类点集中的某个点, 相对于其周围的点居于更中心的位置(称该点密度相对较大), 同时该点到比它密度更大的点的距离相对较远, 则可以将该点称作密度峰值点。

对于具有n个点的数据集D中的点i, 有两个参数:

1) 点密度ρ_i(简称密度ρ_i)

(1)

其中, 表示点i与点p之间的距离; d_{cut_off}表示截断距离, 由人工给定, 有文献指出截断距离可根据所有点之间的距离小于d_{cut_off}所占的比例σ决定^[6]。由(1)式可知, ρ_i在数值上表示与其距离小于d_{cut_off}的点的个数。

2) 到更高密度点的最短距离γ_i(简称距离γ_i)

(2)

由(2)式可知, 当ρ_i最大时, γ_i为点i到其他点的最远距离; 否则, γ_i为到比点i密度更大点的最短距离。

上述两参数可组成二元数对〈ρ, γ〉。以ρ为横坐标, γ为纵坐标, 可以得到一个关于D的决策图G, 如图 1所示。在G中选取ρ、γ值均较大的若干个点(由人工选取, 其中一种选取方案如图 1框内点所示)即密度峰值点作为聚类中心点, 然后将剩余的点分配到离该点最近的聚类中心点所在的簇中, 最终得到聚类结果。

文献[5]中的距离度量标准均为欧氏距离。

1.2 多簇球面K-Means算法

作为文本聚类的元素, 文本数据本身是非数值型的, 因此需要将其转换成数值型数据。向量空间模型^[7]作为经典的文本表示方法之一, 将由n个文本构成的文本数据集T={ t₁, t₂, …, t_n }映射成文本向量空间V={ v₁, v₂, …, v_n }。在向量空间V中, 具有m个特征数的文本向量v_i=(w_i1, w_i2, …, w_im)T, 其中, w_ij (j=1, 2, …, m)表示第i个文本向量的第j个特征, 其值为该特征词在文本t_i中的权重。

根据聚类要求的不同, K-means算法的距离度量标准主要可分为欧氏距离、曼哈顿距离、余弦距离以及相关距离等^[8]。王彬宇等^[9]在文献中阐述了使用余弦相似度作为文本聚类的距离度量标准的合理性。文本向量v_i与v_j余弦相似度可以表示为:

(3)

其中m为v_i与v_j的特征数。由(3)式可知, 余弦相似度S_{〈i, j〉} ∈[0, 1]。因此当S_{〈i, j〉}越大时, 代表两个文本的相似性越高; 反之则代表两个文本的相似性越低。

而SKM算法^[10]则是在K-means算法的基础上, 根据余弦相似度计算公式的特点, 预先在聚类前对每个文本向量进行了标准化:将v_i转换成标准化向量

其中, 。

一方面, (3)式中的作为除数可以省略计算, 因此文本向量标准化后的余弦相似度, 在一定程度上简化了对S_{〈i, j〉}的运算; 另一方面, 通过对文本向量的标准化, 可以减少长文本或高频词对文本相似性的计算的影响。

文献[3]提出的多簇球面K-means算法(multicluster spherical K-means, MCSKM)在SKM算法的基础上, 给定了两个参数MAC和SRL:

1) MAC:最大可分配簇数(maximum assignable clusters), 即一个点最多可以分配给不超过MAC个簇。MAC的参考范围为:

其中k表示聚类的簇数。特别地, 当MAC=1时, MCSKM算法退化成SKM算法。

2) SRL:相似性比率界限(similarity ratio limit), 对于点i, 若簇中心点C_j满足:

其中C_best表示与点i余弦相似度最高的簇中心点, 在同时满足MAC的条件下, 将i分配给C_j所在的簇中。SRL的参考范围为:

综上, 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)。

1.3 MapReduce

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]如图 2所示。

2 DPMCSKM算法

1.2节所述的MCSKM算法尽管适用于文本聚类, 同时通过设置条件参数, 加快了聚类的收敛速度, 但仍未解决初始中心点的选取问题, 算法的稳定性较差。由图 1可知, 决策图G中位于右上角的点具有点密度高、到更高密度点的最短距离的特征, 是作为密度峰值点的参考依据, 但仅通过决策图G并不能得到具体的选取结果, 仍然需要人工选取。

本文针对决策图G中密度峰值点的选取问题, 将密度ρ与距离γ相乘, 得到参数密度距离:

(4)

由(4)式可知, 密度距离ζ越大, 则该点密度越大, 同时与更高密度点的距离越远, 成为密度峰值点的可能性就越大。以ζ值从大到小的次序为序号作为横坐标, ζ值作为纵坐标, 可以得到一个关于V的新决策图G', 如图 3所示。

由图 3可知, 随着横坐标序号的逐渐增大, ζ值单调减少且成逐渐收敛的趋势。因此, 可以认为序号-ζ函数的收敛过程也是样本点从密度峰值点(图 3框内点)到非密度峰值点的转变过程^[12]。然而与欧氏距离不同, 余弦相似度S ∈[0, 1], 即距离γ ∈[0, 1]。同时, 由于余弦相似度侧重于区分两个向量在方向上的差异, 因此从数值上看γ的区分程度没有欧氏距离大; 而点密度ρ ∈[1, n], 受样本点个数n的影响较大, 故图 3所示的密度距离ζ会因ρ与γ在数值比例上的差异不能正确反映密度峰值点的排列情况。

因此本文先将ρ与γ进行离差标准化, 得到参数ρ与γ, 然后计算ρ与γ离差标准化后的密度距离ζˉ。根据密度峰值的原理, ζ最大的点必为聚类中心点(点密度最大, 到更高密度点的距离最远), 故对于ρ_i, 有

(5)

其中:n为样本点的个数, q为ρ值最大点的序号, ρ_max与ρ_min为除点q外其余点中ρ的最大值与最小值。

对于γ_i, 有

(6)

其中:p为γ值最大点的序号, γ_max与γ_min分别为除点p外其余点中γ的最大值与最小值。

对于离差标准化后的密度距离ζ, 有

(7)

由(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)。

3 基于MapReduce的DPMCSKM并行化算法

一方面, 由文本数据转换成的文本向量通常是高维的, 随着文本数据规模的不断增大, 单机环境将难以满足聚类计算的需求; 另一方面, 本文提出的DPMCSKM算法在选取初始聚类中心点时需要预先计算文本向量之间的余弦相似度, 此阶段的计算开销较大。因此, 本文设计并实现了基于MapReduce的DPMCSKM并行化算法, 算法由5个MapReduce Job构成, 其流程示意图如图 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。

4 实验结果与分析

为验证本文提出的算法的有效性, 将本文提出的DPMCSKM算法与K-means、基于CFSFDP算法选取的密度峰值点作为初始簇中心点的K-means (简称DPK-Means)和MCSKM算法进行聚类质量评估和收敛速度的对比, 并进行并行化加速比评估实验。

所有实验的聚类簇数k=6;K-means算法和MCSKM算法均运行20次, 取平均结果; MCSKM和DPMCSKM及其并行化算法的参数, SRL=0.1;DPK-means和DPMCSKM及其并行化算法的参数σ=6%。

4.1 实验数据集

本文的所有实验数据集均来自由清华大学自然语言处理实验室提供的中文文本分类数据集THUCNews^[13], 其根据新浪新闻2005-2011年间的历史数据筛选过滤生成, 总计包含约74万篇文档。在原始数据的基础上, THUCNews重新整合划分出财经、彩票、房产、股票等14类候选分类新闻文档。

受实验条件的限制, 本文从上述数据集中选择体育、娱乐、家居、时政、科技、财经6个类别作为实验的聚类类别, 并分别从每类中随机选取200、500、800、1 000、2 000和4 000篇新闻文档作为实验数据集D₁、D₂、D₃、D₄、D₅和D₆。在实验前, 对实验数据集中的文档进行了预处理, 包括中文分词、去停用词、文本特征选择、文本特征词权重表示和文本向量空间的建立等, 使用中科院汉语分词系统NLPIR进行中文分词, TF-IDF模型对文本进行特征表示。

4.2 实验环境

本文的所有实验均在由VMware虚拟机平台环境搭建的Hadoop集群上完成, Hadoop集群中各节点的类型如表 1所示, 其中node1为Master(主)节点, node2、node3、node4为Slave(从)节点。

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。

4.3 聚类质量评估实验

选取调整兰德系数(adjusted rand index, ARI)和标准化互信息(normalized mutual information, NMI)作为对聚类质量的评估标准, 两种评估指标均用于衡量聚类结果与真实类别数据之间的吻合程度, 其中ARI和NMI的取值范围分别为[-1, 1]和[0, 1], 两者的值越高, 则代表聚类结果与真实类别数据越吻合, 聚类质量越好。本实验使用的数据集为D₁、D₂、D₃和D₄, 实验结果如表 2和表 3所示。

由表 2和表 3可知, 随着数据集文档数目的不断增大, 4种算法的ARI与NMI值均逐渐增大, 而本文提出的DPMCSKM算法的ARI与NMI值均大于其他3种算法, 与K-means、DPK-means和MCSKM算法相比在所使用的4个数据集(D₁、D₂、D₃和D₄)下的ARI值分别平均提升了13.7%、8. 5%和3.4%;NMI值分别平均提升了6. 2%、3.2%和1.9%。本实验表明, 本文提出的DPMCSKM算法聚类所得到的结果与真实类别数据的吻合程度即聚类质量高于其余3种算法, 因此在一定程度上可以有效地进行文本聚类。

4.4 收敛速度评估实验

以算法收敛所需要迭代的次数作为收敛速度评价指标, 算法收敛的条件为聚类中心点不再变化。算法收敛所需要迭代的次数越少, 则说明算法的收敛速度越快。本实验使用的数据集为D₁、D₂、D₃和D₄, 实验结果如表 4所示。

由表 4可知, DPMCSKM算法在不同的数据集下的迭代次数均小于K-means和MCSKM算法, 且在所使用的四个数据集(D₁、D₂、D₃和D₄)下分别平均低17. 2%和31.4%;与DPK-Means算法相比, 迭代次数有高有低:在D₁、D₂时分别高44.4%和42. 9%, 在D₃、D₄时分别低61.5%和34.3%, 这是由于DPK-Means算法在选取初始簇中心时采取欧氏距离作为距离度量标准, 与采取余弦相似度相比对数据集更敏感。对比在数据集D₂和D₄下的实验结果可以发现, 与K-means和MCSKM算法相比, DPMCSKM算法迭代次数的增长幅度较大, 这是由于一方面截断距离参数固定, 而另一方面数据集的规模增大, 进而导致DPMCSKM算法在确定初始聚类中心点时自适应性不够强, 故在进行聚类迭代时次数增长较快。但综合来看, 4种算法中本文提出的DPMCSKM算法收敛所需的次数相对较低且变化较稳定, 因此本实验表明, DPMCSKM算法的收敛速度在一定程度上有所提升。

4.5 并行化加速比评估

对本文提出的基于MapReduce的DPMCSKM并行化算法在1至4个节点的Hadoop集群上的运行时间进行比较, 以并行计算的加速比作为评价指标。算法的加速比越高, 则说明算法的可扩展性与并行化性能越好。本实验使用的数据集为D₂、D₄、D₅和D₆, 实验结果如图 5所示。

由图 5可知, 随着数据集文档数目的不断增大, 不同节点下算法运行的加速比均有所提升; 当节点个数逐渐增多时, 加速比的变化率也不断增大, 并向着线性关系的趋势接近。实验表明, 本文提出的基于MapReduce的DPMCSKM并行化算法在可扩展性方面, 在一定程度上具有较好的加速比。

5 结语

本文提出了一种基于密度峰值的改进K-means文本聚类算法DPMCSKM。算法根据密度峰值的相关概念, 针对文本聚类的特点, 对点密度和到更高密度点的最短距离进行离差标准化, 重新定义并计算了密度距离以选取密度峰值点和初始聚类中心点, 在一定程度上避免了K-means算法随机选取初始聚类中心点的缺陷。同时, 为了更好地适应文本聚类的计算要求, 设计并实现了一种基于MapReduce的DPMCSKM并行化算法。实验结果表明, 本文提出的DPMCSKM算法在聚类质量和收敛速度上均有所提升, DPMCSKM并行化算法具有良好的加速比, 因此可以有效地进行文本聚类。在接下来的工作中, 将继续对密度峰值在文本聚类中的应用进行研究, 如聚类簇数和截断距离参数的确定等, 以进一步提升算法的聚类质量和自适应性。