第10期 武森等：基于MapReduce的大规模文本聚类并行化 ·1415· 综上，算法必在有限的n步(n≤nc,nc为文本 循环需要计算新分裂的两个簇包含的所有文本与相 簇C中文本的数量)之内收敛. 应簇中心的相似度平方，假设每一步划分均匀，则复 证毕 杂度为O(N2):第三步对第一步产生的另一簇分 2.3基于“互为最小相似度文本对”搜索的文本聚 割，复杂度为O(N2),直到第K-1步为(N/2-1) 类算法 或(N2-2).因此，总体复杂度T,≤0(K-1)N), 根据提出的初始簇中心选择方法，结合二分 K为类个数 K-means.算法思想，给出文本聚类算法步骤如下. (2)步骤3中，最差的情况下需要计算任意两 算法2基于“互为最小相似度文本对”搜索的 个文本的相似度，即时间复杂度T2=O(Nm)≤ 文本聚类算法 O(NW),m为搜索次数. 输入：文本集合D={d,d2,…,d,…,d}. (3)步骤4的时间复杂和步骤2类似，需要计 参数：聚类的簇数K 算每次分割簇中所有文本与两个簇中心的相似度， 输出：文本集合D的簇划分S={S1,S2,…, 时间复杂度T3≤0(2(K-1)N),并且步骤4和步骤 S4,…,Sx}; 2都需计算分割簇中所有文本与簇中心的相似度， 算法步骤： 因此只需计算一次存储即可，步骤2和步骤4的总 步骤1初始化.将所有文本组成的集合D作 体时间复杂度T,+T3=T3≤0(2(K-1)N). 为初始簇：S={S,},S。←-D (4)步骤6为标准的K-Means算法，复杂度 步骤2根据式(4)从S中选择文本相似度均 T,=O(tKN),t为迭代次数 方MS最小的簇S作为待分裂簇. 因此整个算法的时间复杂度T≤O(NW)+ 步骤3运用提出的算法1寻找待分裂簇S的 O(2(K-1)N)+O(tKN)≈O(NW),聚类个数K和 初始二分簇中心文本对d,d 迭代次数t均远小于文本总数N.与原始的二分 步骤4将待分类簇的所有文本S.={d1, K-means:算法相比，本文的算法主要通过步骤4提高 dn2,…,d,…,dnm}按照相似度最大原则分配到簇 了效率，原始的算法需要多次迭代进行文本划分，时 S和S中： 间复杂度为T:≤O(2t(K-1)N) rdnm∈Sx,SlM(dm,d）≥sim(dm,d,）; 值得一提的是，文献5]提出的基于最小相似 dS,,SIM (dd)<sim(d'd,) 度的文本聚类中心选取方法和本文提出的根据“互 将S,和S,添加到簇划分S中，并将S.从S中 为最小相似度文本对”选择初始二分聚类簇中心的 删除 过程并不相同.首先，从概念定义上，文献5]定义 步骤5如果S中文本簇个数小于K,返回步骤 的“最小相似度文本”指整个数据中相似度最小的 2:如果S中文本簇个数等于K,转向步骤6 两个文本，本文提出的“互为最小相似度文本对”指 步骤6以S中K个簇的质心为初始簇中心对 某个己经形成的文本簇中互为对方最小相似度的文 所有文本利用球面K-means聚类得到文本簇划分 本对，即文献5]中寻找“最小相似度文本”对应的 S,其中聚类过程中采用定义2的文本相似度计算 文本相似度为整个数据集中任意两个文本相似度的 方法. 最小值：本文中，簇的“互为最小相似度文本”对应 步骤7结束 的相似度不一定是为任意两个文本相似度的最小 由算法2过程可知，本文提出的文本聚类算法 值，即前者为全局最小值，后者为局部极小值.因此 在搜索到初始二分簇中心后一次分配所有对象（步 从搜索的时间复杂度上看，文献5]搜索“最小相 骤4)，得到簇的划分，并无原始二分K-means算法 似度文本”时间复杂度为O(NW)(全局最小，N为文 中重复的迭代寻优过程，因此将有可能提高文本聚 本数)：本文的时间复杂度O(Nm)≤O(NW),m为 类的效率 搜索次数，最差为O(NW).其次，从确定类中心过 2.4算法分析比较 程上，文献15]针对K-means划分聚类寻找初始簇 首先，分析算法2的时间复杂度.具体地，各步 中心的问题，选择相似度最小的两个文本作为其中 的时间复杂度如下 两个初始中心，然后将这两个文本从文本集合中删 (1)步骤2中首先计算每个簇的相似度均方. 除，根据与己确定类中心之间相似度和最小的原则 第一次循环中需计算每个文本与相应簇中心的相似 从其余文本中选择其他类的中心，直到选出指定类 度平方，因此复杂度为O(N),N为文本数：第二次 别数目的中心点个数为止：本文提出的方法是针对第 10 期 武 森等: 基于 MapＲeduce 的大规模文本聚类并行化 综上，算法必在有限的 n 步( n≤nC，nC为文本 簇 C 中文本的数量) 之内收敛． 证毕． 2. 3 基于“互为最小相似度文本对”搜索的文本聚 类算法 根据提出的初始簇中心选择方法，结合二分 K-means算法思想，给出文本聚类算法步骤如下． 算法 2 基于“互为最小相似度文本对”搜索的 文本聚类算法． 输入: 文本集合 D = { d1，d2，…，di，…，dN} ． 参数: 聚类的簇数 K． 输出: 文本集合 D 的簇划分 S = { S1，S2，…， Sk，…，SK } ; 算法步骤: 步骤 1 初始化． 将所有文本组成的集合 D 作 为初始簇: S = { S0 } ，S0←D． 步骤 2 根据式( 4) 从 S 中选择文本相似度均 方 MS 最小的簇 Sm作为待分裂簇． 步骤 3 运用提出的算法 1 寻找待分裂簇 Sm的 初始二分簇中心文本对 dx，dy ． 步骤 4 将待分类簇的所有文本 Sm = { dm1， dm2，…，dmi，…，dmn } 按照相似度最大原则分配到簇 Sx和 Sy中: dmi∈Sx，SIM( dmi，dx ) ≥sim( dmi，dy ) ; dmi∈Sy，SIM( dmi，dx ) ＜ sim( dmi，dy { ) ． 将 Sx和 Sy 添加到簇划分 S 中，并将 Sm从 S 中 删除． 步骤 5 如果 S 中文本簇个数小于 K，返回步骤 2; 如果 S 中文本簇个数等于 K，转向步骤 6． 步骤 6 以 S 中 K 个簇的质心为初始簇中心对 所有文本利用球面 K-means 聚类得到文本簇划分 S，其中聚类过程中采用定义 2 的文本相似度计算 方法． 步骤 7 结束． 由算法 2 过程可知，本文提出的文本聚类算法 在搜索到初始二分簇中心后一次分配所有对象( 步 骤 4) ，得到簇的划分，并无原始二分 K-means 算法 中重复的迭代寻优过程，因此将有可能提高文本聚 类的效率． 2. 4 算法分析比较 首先，分析算法 2 的时间复杂度． 具体地，各步 的时间复杂度如下． ( 1) 步骤 2 中首先计算每个簇的相似度均方． 第一次循环中需计算每个文本与相应簇中心的相似 度平方，因此复杂度为 O( N) ，N 为文本数; 第二次 循环需要计算新分裂的两个簇包含的所有文本与相 应簇中心的相似度平方，假设每一步划分均匀，则复 杂度为 O( N /2) ; 第三步对第一步产生的另一簇分 割，复杂度为 O( N /2) ，直到第 K － 1 步为( N /2K － 1 ) 或( N /2K － 2 ) ． 因此，总体复杂度 T1≤O( ( K － 1) N) ， K 为类个数． ( 2) 步骤 3 中，最差的情况下需要计算任意两 个文本的 相 似 度，即 时 间 复 杂 度 T2 = O ( Nm) ≤ O( NN) ，m 为搜索次数． ( 3) 步骤 4 的时间复杂和步骤 2 类似，需要计 算每次分割簇中所有文本与两个簇中心的相似度， 时间复杂度 T3≤O( 2( K － 1) N) ，并且步骤 4 和步骤 2 都需计算分割簇中所有文本与簇中心的相似度， 因此只需计算一次存储即可，步骤 2 和步骤 4 的总 体时间复杂度 T1 + T3 = T3≤O( 2( K － 1) N) ． ( 4) 步骤 6 为标准的 K-Means 算法，复杂度 T4 = O( tKN) ，t 为迭代次数． 因此整个算法的时间复杂度 T≤O( NN) + O( 2( K － 1) N) + O( tKN) ≈O( NN) ，聚类个数 K 和 迭代次数 t 均远小于文本总数 N． 与原始的二分 K-means算法相比，本文的算法主要通过步骤 4 提高 了效率，原始的算法需要多次迭代进行文本划分，时 间复杂度为 T'3≤O( 2t( K － 1) N) ． 值得一提的是，文献［15］提出的基于最小相似 度的文本聚类中心选取方法和本文提出的根据“互 为最小相似度文本对”选择初始二分聚类簇中心的 过程并不相同． 首先，从概念定义上，文献［15］定义 的“最小相似度文本”指整个数据中相似度最小的 两个文本，本文提出的“互为最小相似度文本对”指 某个已经形成的文本簇中互为对方最小相似度的文 本对，即文献［15］中寻找“最小相似度文本”对应的 文本相似度为整个数据集中任意两个文本相似度的 最小值; 本文中，簇的“互为最小相似度文本”对应 的相似度不一定是为任意两个文本相似度的最小 值，即前者为全局最小值，后者为局部极小值． 因此 从搜索的时间复杂度上看，文献［15］搜索“最小相 似度文本”时间复杂度为 O( NN) ( 全局最小，N 为文 本数) ; 本文的时间复杂度 O( Nm) ≤O( NN) ，m 为 搜索次数，最差为 O( NN) ． 其次，从确定类中心过 程上，文献［15］针对 K-means 划分聚类寻找初始簇 中心的问题，选择相似度最小的两个文本作为其中 两个初始中心，然后将这两个文本从文本集合中删 除，根据与已确定类中心之间相似度和最小的原则 从其余文本中选择其他类的中心，直到选出指定类 别数目的中心点个数为止; 本文提出的方法是针对 · 5141 ·