第10期 武森等：基于MapReduce的大规模文本聚类并行化 ·1413· 效率. 在并行聚类研究方面，MapReduce框架的出现 ",=〔×i通=lg(++1 (1) ni 使得大规模文本数据的并行聚类研究逐渐发展，研 式中，f,指特征词t在文本d,中出现的频率，ng为文 究者基于MapReduce框架进行的并行聚类研究包 本d:中特征词t出现的次数，n:为文本d,含有的所有 括：基于MapReduce的并行K-means聚类；基于 特征词出现的总数：id出指特征词t在整个文本集中 MapReduce的快速K-center和K-median聚类：基 的逆向文档频率，用来衡量特征词的出现范围，N为 于MapReduce的大规模多维数据聚类：基于 文本集合中总文本数量，V表示含有特征词t,的不 MapReduce的分布式文本聚类Pa.这些研究针对不 同文本数量.显然，某个特征词在特定的文档中出 同的聚类算法，通过定义不同的Ma即和Reduce任 现的频率越高，该特征词在区分该文本内容属性方 务实现大规模数据的并行聚类，获得了大规模数据 面的能力越强(T℉)；在文本集中出现的范围越广， 聚类挖掘效率的提高及良好的扩展性 其区分文本内容的属性越低(DF). 本文针对目前具有较好文本聚类效果的二分 定义2文本相似度.给定文本d,d,TA(d:, K-means算法的不足，在保证文本聚类效果的前提 d）={t1,t2,…,tu,…,th}表示d,d所含特征 下，从如何提高二分K-means聚类效率及大规模文 词的并集，h为并集中特征词的数目；TS(d:,d,)= 本挖掘问题入手，对文本聚类算法及其并行化进行 {t1,ta,…,t…,tu}表示d,d所含特征词的交 了研究.首先，利用向量空间模型提出一种文本相 集，l为交集中特征词的数目.文本d,d,在TS中的 似度计算方法.其次，提出了基于“互为最小相似度 每个特征词t4上的相似度sim(d:,d,t)定义为 文本对”搜索算法的初始二分聚类簇中心选择方 sim(dd)=min() (2) 法，并对算法搜索的收敛性进行了证明.然后，结合 max (w,) 二分K-means算法的步骤和思想，给出一次划分实 文本d,d的相似度SM(d,d)定义为 现簇中心寻优的高效二分聚类过程及完整的文本聚 ∑sim(d:,d,tt) 类算法.此外，在针对提高大规模文本聚类的效率 SIM(d.,d)= 一，(3) I TA(d,d)I 方面，本文借鉴基于MapReduce的并行聚类研 即两文本在所有共同特征词上的相似度之和与两文 究-，利用MapReduce框架设计了面向云计算应 本包含的所有特征词的个数之比.式(3)与经典的 用的分布式并行二分K-means文本聚类模型.最 余弦相似度(W:·W/(IW:1*1W1)计算方法相 后，在Hadoop平台的真实数据实验验证了算法在保 比，都首先利用了两个文本所包含的共同特征词计 证聚类效果的前提下相比原始二分K-means算法的 算公式的分子项，其次分母项均利用了除了共同特 效率优势及并行聚类在不同数据规模和计算节点上 征之外其余各自本文的特征词.不同的是，本文提 的扩展性 出的式(3)分别精确地计算了每个共同特征词的相 似程度，而不是在夹角余弦中直接通过向量内积计 2基于初始簇中心的文本聚类算法 算总体相似度. 本文首先采用文本特征表示模型提出了文本相 定义3文本簇相似度均方.包括c个文本的 似度计算模型，并提出了基于“互为最小相似度文 文本簇C={d,d2,…,d,…,d}的簇相似度均方 本对”搜索的初始二分簇中心选择方法，在此基础 MS(C)定义为所有文本与簇质心相似度平方的 上给出结合二分K-means的文本聚类算法 均值： 2.1文本特征表示及相似度模型 ∑sIM(d,d.)2 定义1文本特征表示模型.给定文本集合 MS(C)= (4) nc D={d,d2,,d,…,dw},d代表每个文本向量， 其中，d为簇质心文本特征向量，即d。=(〈t1,w）, 采用向量空间模型可表示为d:=（l1,wa),〈2， 〈t2,02）,…,〈t,0g）,…,〈tm,0em>）, 02〉，…，〈，0g〉，…，〈tm,0m）.其中：T={t1, 2,…,,…,tm}表示文本集中所有文本包含的所 有特征词的集合，W:=(wa,02,…,0…,0m）表 We (5) nc 示文本d,在所有特征词上对应的权重向量.采用 2.2初始二分簇中心选择方法 TFDF计算方法网： 原始的二分K-means方法在选择一个簇进行分第 10 期 武 森等: 基于 MapＲeduce 的大规模文本聚类并行化 效率． 在并行聚类研究方面，MapＲeduce 框架的出现 使得大规模文本数据的并行聚类研究逐渐发展，研 究者基于 MapＲeduce 框架进行的并行聚类研究包 括: 基于 MapＲeduce 的并行 K-means 聚类［23］; 基于 MapＲeduce 的快速 K-center 和 K-median 聚类［24］; 基 于 MapＲeduce 的 大规模多维数据聚类［25］; 基 于 MapＲeduce的分布式文本聚类［26］． 这些研究针对不 同的聚类算法，通过定义不同的 Map 和 Ｒeduce 任 务实现大规模数据的并行聚类，获得了大规模数据 聚类挖掘效率的提高及良好的扩展性． 本文针对目前具有较好文本聚类效果的二分 K-means 算法的不足，在保证文本聚类效果的前提 下，从如何提高二分 K-means 聚类效率及大规模文 本挖掘问题入手，对文本聚类算法及其并行化进行 了研究． 首先，利用向量空间模型提出一种文本相 似度计算方法． 其次，提出了基于“互为最小相似度 文本对”搜索算法的初始二分聚类簇中心选择方 法，并对算法搜索的收敛性进行了证明． 然后，结合 二分 K-means 算法的步骤和思想，给出一次划分实 现簇中心寻优的高效二分聚类过程及完整的文本聚 类算法． 此外，在针对提高大规模文本聚类的效率 方面，本 文 借 鉴 基 于 MapＲeduce 的 并 行 聚 类 研 究［23--25］，利用 MapＲeduce 框架设计了面向云计算应 用的分布式并行二分 K-means 文本聚类模型． 最 后，在 Hadoop 平台的真实数据实验验证了算法在保 证聚类效果的前提下相比原始二分 K-means 算法的 效率优势及并行聚类在不同数据规模和计算节点上 的扩展性． 2 基于初始簇中心的文本聚类算法 本文首先采用文本特征表示模型提出了文本相 似度计算模型，并提出了基于“互为最小相似度文 本对”搜索的初始二分簇中心选择方法，在此基础 上给出结合二分 K-means 的文本聚类算法． 2. 1 文本特征表示及相似度模型 定义 1 文本特征表示模型． 给定文本集合 D = { d1，d2，…，di，…，dN} ，di代表每个文本向量， 采用向量空间模型可表示为 di = ( ? t1，wi1 ?，? t2， wi2 ?，…，?tj ，wij ?，…，? tm，wim ?) ． 其中: T = { t1， t2，…，tj ，…，tm } 表示文本集中所有文本包含的所 有特征词的集合，Wi = ( wi1，wi2，…，wij，…，wim ) 表 示文本 di 在所有特征词上对应的权重向量． 采用 TF-IDF 计算方法［8］: wij = tfi × idfj = nij ni ·log2 ( N Nj + 1 + 1 ) ． ( 1) 式中，tfij指特征词 tj在文本 di中出现的频率，nij为文 本 di中特征词 tj出现的次数，ni为文本 di含有的所有 特征词出现的总数; idfj指特征词 tj在整个文本集中 的逆向文档频率，用来衡量特征词的出现范围，N 为 文本集合中总文本数量，Nj表示含有特征词 tj的不 同文本数量． 显然，某个特征词在特定的文档中出 现的频率越高，该特征词在区分该文本内容属性方 面的能力越强( TF) ; 在文本集中出现的范围越广， 其区分文本内容的属性越低( IDF) ． 定义 2 文本相似度． 给定文本 di，dj ，TA( di， dj ) = { ta1，ta2，…，tat，…，tah } 表示 di，dj所含特征 词的并集，h 为并集中特征词的数目; TS( di，dj) = { ts1，ts2，…，tsk，…，tsl} 表示 di，dj所含特征词的交 集，l 为交集中特征词的数目． 文本 di，dj在 TS 中的 每个特征词 tsk上的相似度 sim( di，dj ，tsk ) 定义为 sim( di，dj ，tsk ) = min( wisk，wjsk ) max( wisk，wjsk ) ， ( 2) 文本 di，dj的相似度 SIM( di，dj ) 定义为 SIM( di，dj ) = t ∑sk∈TS( di ，dj ) sim( di，dj ，tsk ) | TA( di，dj ) | ， ( 3) 即两文本在所有共同特征词上的相似度之和与两文 本包含的所有特征词的个数之比． 式( 3) 与经典的 余弦相似度( Wi ·Wj / ( | Wi | * | Wj | ) ) 计算方法相 比，都首先利用了两个文本所包含的共同特征词计 算公式的分子项，其次分母项均利用了除了共同特 征之外其余各自本文的特征词． 不同的是，本文提 出的式( 3) 分别精确地计算了每个共同特征词的相 似程度，而不是在夹角余弦中直接通过向量内积计 算总体相似度． 定义 3 文本簇相似度均方． 包括 nC个文本的 文本簇 C = { d1，d2，…，di，…，dnC } 的簇相似度均方 MS( C) 定义为所有文本与簇质心相似度平方的 均值: MS( C) = ∑di∈C SIM( di，de ) 2 nC ． ( 4) 其中，de为簇质心文本特征向量，即 de = ( ?t1，we1 ?， ?t2，we2 ?，…，?tj ，wej ?，…，?tm，wem ?) ， wej = ∑ n i = 1 wij nC ． ( 5) 2. 2 初始二分簇中心选择方法 原始的二分 K-means 方法在选择一个簇进行分 · 3141 ·