·1416· 北京科技大学学报 第36卷 二分K-means随机选择二分簇中心的问题，提出用 Ma即：〈t@d,f〉→t,〈d,tf》 “互为最小相似度文本”作为二分簇中心，因此本文 Reduce:〈t,count(Kd:,f))→〈t,V>, 和文献5]是分别针对不同的聚类策略研究如何 〈@d,f〉→t@d,wg〉 选择初始簇中心的问题 (4)整理获取每个文本的特征表示.以获取的 每个文本d:含有的每个特征词t的TFDF权值 3基于MapReduce的并行文本聚类模型 〈，@d,心；)作为该任务的输入，Ma即将其转换成 尽管改进的算法相比原始二分聚类有可能提高 〈d,〈，w》;Reduce将每个文本d:的所有特征词 聚类效率，但是通过聚类算法本身的改进获得的计 及其权重合并一起，即<d,Lit,w,》·MapRe- 算效率的提高远无法适应面向云计算实际应用中大 duce过程可表示为： 规模海量文本聚类挖掘需要，因此利用云计算环境 Map:〈t@d:,w>→(d:,〈，0g》 中的MapReduce框架对文本聚类过程进行并行化 Reduce:〈d:,〈马，wg》→(d,Lit,og》 处理，将进一步大幅提高文本聚类效率 其中，上述四个MapReduce任务中：count表示 在文本聚类过程中，两个重要的步骤分别是文 计数，sum表示求和，Li⊕表示含有某种元素的集 本特征提取和聚类过程.因此，本文分别针对这两 合，下文同理 个步骤设计了并行化的MapReduce任务框架. 3.2基于MapReduce任务的并行文本聚类过程 3.1基于MapReduce任务的并行文本特征提取 在文本聚类过程中，本文设计三个MapReduce 可以通过以下四个MapReduce任务提取每个 任务进行分布式并行计算，负责搜索“互为最小相 文本的特征，即获取每个文本包括的所有特征词及 似度文本对”、分配文本到两个簇及最终的K-means 对应的TFDF权值. 文本聚类过程. (1)统计每个文本中每个特征词出现的次数. (1)根据“互为最小相似度文本对”寻找初始 Map对含有具体内容的每个文本〈d,contedt进行 文本簇中心.Ma即选取一个文本d,根据定义2计 预处理，输出每个文本d,中的每个特征词，且标记 算选定的簇S中其余文本与d的相似度，并搜索与 次数为1，即<t,@d,D;Reduce对具有相同key(同 d,具有最小相似度的文本d,并搜索与d,具有最小 一文本d,中的同一特征词：t@d,)的value进行统 相似度的文本d;Reduce将d,赋值给d.,d赋值给 计求和，即(t,@d,n>.MapReduce过程可表示为： d,重新利用Map搜索d的最小相似度文本，直到 Map:〈d,contedt→Kt,@d:,2 找到“互为最小相似度文本对”〈d,d,）,由定理1 Reduce:〈t,@d:,count(1))→Kt@d:,ng〉 可知该过程收敛.MapReduce过程可表示为： (2)统计每个文本中含有的所有特征词的总 Map:〈d.,Lif,og》,〈Snm,List d》→ 数.Map将输入〈t@d,ng)中的文本和特征词分 <d,&d,,SIM(d,,d,)> 离，以文本d:为key转换成〈d:,〈t,ng》:Reduce Repeat 统计具有相同key值(d:)的value(ng)进行统计求 Map:〈d,Lift,0,》,〈Sm,Li4dm》→ 和，得到每个文本d:所有特征词出现的总数n:,即 〈d,&d,SM(d,d）〉 〈d,n:》:并根据上一个过程的结果计算每个文本 Reduce:drd,d,←dk d:含有的每个特征词t的频率〈t@d:,ng/n:),即 End until d =dg or SIM (d,d,)=SIM(d,,d,) (t@d,圹).MapReduce过程可表示为： (2)分配待分裂簇中所有文本到两个簇中 Map:〈t@d,ng)→(d:,〈t,ng》 Ma即根据搜索的初始簇中心d,d,按照定义2计 Reduce:〈d:,sum(Kt,ng)))→(d:,n:）, 算簇S中所有文本与簇中心d,d,的相似度，并按 〈t@d,n〉→Kt@d,tf〉 相似度最大原则分配到两个簇S,和S,中，〈S,List (3)统计每个特征词在不同文本中出现的次 〈d:,Litt,w:》(Sk=S或S,).Reduce按照定 数.Map将输入〈t,@d:,f:)中的文本和特征词分 义3计算两个簇的质心向量d和文本相似度均方 离，以特征词t为key转换成，〈d,f》:Reduce MS(S),即<Sk,dt,MS(S)>.MapReduce过程可 统计每一个特征词在不同文本中出现的总次数 表示为： N,即〈t,N),再读取总文本数V根据式(1)计算每 Map:〈Sm,List d〉，d.,d,〉→Sk,Litd:》 个文本d:含有的每个特征词的TFDF权值0，即 Reduce:〈Sk,Litd:》→(Sk,d4,MS(S)> 〈t,@d,w,>.MapReduce过程可表示为： 上述两个MapReduce任务将重复进行直到簇北 京 科 技 大 学 学 报 第 36 卷 二分 K-means 随机选择二分簇中心的问题，提出用 “互为最小相似度文本”作为二分簇中心，因此本文 和文献［15］是分别针对不同的聚类策略研究如何 选择初始簇中心的问题． 3 基于 MapＲeduce 的并行文本聚类模型 尽管改进的算法相比原始二分聚类有可能提高 聚类效率，但是通过聚类算法本身的改进获得的计 算效率的提高远无法适应面向云计算实际应用中大 规模海量文本聚类挖掘需要，因此利用云计算环境 中的 MapＲeduce 框架对文本聚类过程进行并行化 处理，将进一步大幅提高文本聚类效率． 在文本聚类过程中，两个重要的步骤分别是文 本特征提取和聚类过程． 因此，本文分别针对这两 个步骤设计了并行化的 MapＲeduce 任务框架． 3. 1 基于 MapＲeduce 任务的并行文本特征提取 可以通过以下四个 MapＲeduce 任务提取每个 文本的特征，即获取每个文本包括的所有特征词及 对应的 TF-IDF 权值． ( 1) 统计每个文本中每个特征词出现的次数． Map 对含有具体内容的每个文本? di，content? 进行 预处理，输出每个文本 di中的每个特征词 tj ，且标记 次数为 1，即?tj @ di，1? ; Ｒeduce 对具有相同 key( 同 一文本 di中的同一特征词 tj : tj@ di ) 的 value 进行统 计求和，即?tj @ di，nij?． MapＲeduce 过程可表示为: Map: ?di，content ? →?tj @ di，1? Ｒeduce: ?tj @ di，count( 1) ?→?tj @ di，nij? ( 2) 统计每个文本中含有的所有特征词的总 数． Map 将输入? tj @ di，nij ? 中的文本和特征词分 离，以文本 di为 key 转换成? di，? tj ，nij ?? ; Ｒeduce 统计具有相同 key 值( di ) 的 value( nij) 进行统计求 和，得到每个文本 di所有特征词出现的总数 ni，即 ?di，ni?; 并根据上一个过程的结果计算每个文本 di含有的每个特征词 tj 的频率? tj @ di，nij / ni ?，即 ?tj @ di，tfij?． MapＲeduce 过程可表示为: Map: ?tj @ di，nij?→?di，?tj ，nij?? Ｒeduce: ? di，sum ( ? tj ，nij ?) ? → ? di，ni ?， ?tj @ di，nij?→?tj @ di，tfij? ( 3) 统计每个特征词在不同文本中出现的次 数． Map 将输入? tj @ di，tfij? 中的文本和特征词分 离，以特征词 tj为 key 转换成?tj ，?di，tfij?? ; Ｒeduce 统计每一个特征词 tj 在不同文本中出现的总次数 Nj ，即?tj ，Nj ?，再读取总文本数 N 根据式( 1) 计算每 个文本 di含有的每个特征词 tj的 TF-IDF 权值 wij，即 ?tj @ di，wij?． MapＲeduce 过程可表示为: Map: ?tj @ di，tfij?→?tj ，?di，tfij?? Ｒeduce: ? tj ，count ( ? di，tfij ?) ? → ? tj ，Nj ?， ?tj @ di，tfij?→?tj @ di，wij? ( 4) 整理获取每个文本的特征表示． 以获取的 每个文本 di 含有的每个特征词 tj 的 TF-IDF 权值 ?tj @ di，wij?作为该任务的输入，Map 将其转换成 ?di，?tj ，wij?? ; Ｒeduce 将每个文本 di的所有特征词 及其权重合并一起，即? di，List? tj ，wij ?? ． MapＲe￾duce 过程可表示为: Map: ?tj @ di，wij?→?di，?tj ，wij?? Ｒeduce: ?di，?tj ，wij?? →?di，List ? tj ，wij?? 其中，上述四个 MapＲeduce 任务中: count 表示 计数，sum 表示求和，List ?? 表示含有某种元素的集 合，下文同理． 3. 2 基于 MapＲeduce 任务的并行文本聚类过程 在文本聚类过程中，本文设计三个 MapＲeduce 任务进行分布式并行计算，负责搜索“互为最小相 似度文本对”、分配文本到两个簇及最终的 K-means 文本聚类过程． ( 1) 根据“互为最小相似度文本对”寻找初始 文本簇中心． Map 选取一个文本 dx，根据定义 2 计 算选定的簇 Sm中其余文本与 dx的相似度，并搜索与 dx具有最小相似度的文本 dy，并搜索与 dy具有最小 相似度的文本 dk ; Ｒeduce 将 dy赋值给 dx，dk赋值给 dy，重新利用 Map 搜索 dy的最小相似度文本，直到 找到“互为最小相似度文本对”? dx，dy?，由定理 1 可知该过程收敛． MapＲeduce 过程可表示为: Map: ? dx，List? tj ，wxj ?? ，? Sm，List? dmi ?? → ?dx＆dy，SIM( dx，dy ) ? Ｒepeat Map: ?dy，List? tj ，wyj ?? ，? Sm，List? dmi ?? → ?dy＆dk，SIM( dk，dy ) ? Ｒeduce: dx←dy，dy←dk End until dk = dk or SIM( dk，dy ) = SIM( dx，dy ) ( 2) 分配待分裂簇中所有文本到两个簇中． Map 根据搜索的初始簇中心 dx，dy，按照定义 2 计 算簇 Sm中所有文本与簇中心 dx，dy的相似度，并按 相似度最大原则分配到两个簇 Sx和 Sy中，? Sk，List ?di，List ? tj ，wij??? ( Sk = Sx或 Sy ) ． Ｒeduce 按照定 义 3 计算两个簇的质心向量 dek和文本相似度均方 MS( Sk ) ，即?Sk，dek，MS( Sk ) ?． MapＲeduce 过程可 表示为: Map: ?Sm，List ? dmi?，dx，dy?→?Sk，List ? di?? Ｒeduce: ?Sk，List ? di?? →?Sk，dek，MS( Sk ) ? 上述两个 MapＲeduce 任务将重复进行直到簇 · 6141 ·