一种高效的分布式相似短文本聚类算法*

原默晗　唐晋韬　王　挺

(国防科学技术大学计算机学院　长沙　410073)



一种高效的分布式相似短文本聚类算法*

原默晗唐晋韬王挺

(国防科学技术大学计算机学院长沙410073)

摘要近似重复在微博等网络短文本中十分常见,查找和消除近似重复对于网络信息的有效处理具有非常重要的意义。论文针对相似短文本聚类的特点,在改进shingling、最小哈希和局部敏感哈希算法相结合的文件相似检测方法的基础上,设计了一个高效的短文本聚类方法。该方法通过将文本表示成连续短字符串集合,并应用最小哈希将集合简化成一组由数字组成的文本签名,通过局部敏感哈希算法得到符合相似度条件的文本聚类。为了适应网络信息规模大的特点,论文进一步利用Apache Spark集群计算框架对聚类算法进行了并行化,提高了数据处理的效率,并分析了影响算法性能的因素。

关键词文本聚类; 最小哈希; 局部敏感哈希; shingling; Spark

Class NumberTP391.1

1引言

随着互联网和通信技术的快速进步,电子信息产生了爆炸性的增长。新浪自2009年8月推出微博产品以来,迅速成长为中国微博平台代表。截止2014年底,微博用户数量超5.3亿,月活跃用户数量达到1.76亿,用户每日发布微博数量超过1亿条[1],这些微博及其转发和评论信息产生了海量的短文本。

重复信息在微博短文本中很常见,发现这些重复或者相似的短文本,对于消除信息冗余,进一步开展观点挖掘、主题发现、信息过滤等处理研究,都具有十分重要的意义。……