工具之家 > 软件导刊 > 基于DBSCAN算法的文本聚类研究

基于DBSCAN算法的文本聚类研究

发布时间:2018-10-11 02:16:00 文章来源:工具之家    

 推荐工具:金融理财app工具实用工具

邹艳春

摘 要:提出使用文本相似度算法与DBSCAN聚类算法相结合的方法对文本进行聚类,实现对文本的管理。首先对文本进行特征提取和分词操作,在分词过程中会产生大量的特征词汇,而有些特征词汇对文本特征的表达并无实际意义。因此,在文本特征提取过程中根据特征词汇对文本特征表达的贡献度进行取舍,以提高文本聚类的效率和准确性。利用TF-IDF方法对特征词汇进行加权,并且对文本进行相似度计算,将相似度低于阈值的文本作为孤立点进行处理。利用DBSCAN算法对文本进行聚类,将相似的文本聚为一类。

关键词关键词:文本聚类;DBSCAN聚类;文本相似度;文本处理

DOIDOI:10.11907/rjdk.161915

中图分类号:TP312

文献标识码:A 文章编号:1672-7800(2016)008-0036-03

0 引言

互联网作为开放共享的信息平台,蕴含着海量的文本信息资源,而这些海量文本信息资源通常在互联网上是无序存放的,存在着各种各种冗余的信息,因此需要采用相关技术来组织和管理这些文本信息。文本分类和聚类是文本信息管理的重要方法,文本聚类是文本挖掘的重要组成部分,越来越受到关注。文本聚类广泛应用于文档自动整理、组织管理等,可以对搜索引擎搜索结果分类进行优化。此外,也可以应用于推荐系统中,根据用户所感兴趣的文档进行聚类,发现用户的兴趣模式,从而挖掘出用户新的感兴趣的资源。本文利用DBSCAN算法来对文本进行聚类,DBSCAN算法是一种基于密度的聚类算法,该算法通过过滤低密度的区域,发现稠密的区域[1]。本文文本处理的模型如图1所示,在文本预处理阶段,需要对文本表示方式转换为数值数据的表达形式,通过对文本进行分词和特征项提取,使用TF-IDF对特征词汇进行加权,利用DBSCAN聚类算法将相似的文本聚为一类。

1 文本预处理

1.1 中文文档分词处理

文本预处理首先需要对文本进行分词操作,中文文档使用词典和砌词的方式进行分词,分词过程由计算机自动实现。由于文档中存在一些无用的词汇或符号等,需要在分词过程中去除这些无用的词语及符号,比如文档中的标点符号、结构助词等,这些词汇对文本特征表示并无太大的关联,因此需要过滤掉。同时,中文词汇中存在同义词问题,需要对同义词进行合并操作,比如“歌唱”和“歌颂”属于同义词,可以合并为“歌唱”。

1.2 文本特征提取

文本经过分词处理后会出现大量的特征词汇,特征词汇可以是词组,也可以是词条。这些特征词汇中相当部分对文本特征表示并无太大贡献,因此需要对这些特征词汇进行取舍,以提高聚类的效率和准确性。特征词汇的提取依据主要是由文本特征表达的贡献度来决定,特征词汇的贡献度越高,说明这个特征词汇就越能表达文本特征。特征词汇的贡献度受多个因素影响,主要影响因素是特征词汇出现的频率、文本的主题和特征增量。

2 DBSCAN聚类算法分析与实现

2.1 DBSCAN聚类算法分析

文本聚类是按照聚类假设:同类文档相似度大,对于不是同类的文档,它们的相似度小[3]。作为一种无监督的机器学习方法,聚类由于不需要训练样本的过程,不需要预先对文档手工标注类别,因此具有一定的灵活性和较高的自动化处理能力,已经成为对文本信息进行有效组织、摘要和导航的重要手段[4]。DBSCAN算法是一种基于密度的聚类算法,其主要目的是过滤低密度的样本区域,从而发现稠密的样本区域。与传统的基于层次聚类和划分聚类的凸形聚类簇不同,该算法可以发现任意形状的聚类簇[5]。与K-means相比较,不必输入划分的聚类个数,聚类簇的形状可以是任意形状的空间聚类,可以在需要时输入过滤噪声的参数,DBSCAN中的定义如下:

输出:所有生成的簇,达到密度要求。

算法1:Repeat。

算法2:从数据集S中取出一个没有处理过的对象。

算法3:IF取出的对象是核心对象 THEN 寻找全部从该对象密度可达的对象,形成一个簇。

算法4:ELSE 取出的对象不是核心对象,跳出本次循环,继续寻找下一个对象。

算法5:UNTIL 所有的对象都被处理。

2.2 DBSCAN聚类算法对文本聚类的实现

从文档集中抽取一篇未被处理的文档p(p代表从文档集抽出的一篇文档),并标示文档p为已处理,先对文档p进行分词和特征提取。在特征提取过程中需要对特征词汇进行去噪处理,从而得到特征词汇集合。利用TF-IDF方法对文档集中的文档(包括文档p)分别对这些特征词汇集合进行加权操作,得到一个数据矩阵。利用文本相似度算法计算文档p与文档集中其它文档的相似度,如果与文档p相似度大于或等于设定阈值,就存放到文档p的领域中,直到数据矩阵全部数据处理完毕。判断p的领域中文档数量是否大于设定的MinPts值,如果大于设定的MinPts值,则称p为核心对象并继续向下执行,否则返回上层重新从文档集中抽取一篇未被处理的文档开始处理。判断文档p是否已经属于某一个簇中,如果文档p没有所属的簇,就新建一个簇并且将文档p放到这个簇中。从文档p的领域中抽取一篇未处理的文档(r代表从p的领领域中抽出的一篇文档)r,并标记文档r已处理,对文档r得到领域的方法和文档p处理一样,判断r的领域中文档数量,如果文档数据大于设定的MinPts值,就把文档r领域中的文档存放到文档p所属的簇中,直到p的领域中的文档处理完毕。最后直到文档集中的文档都处理完毕之后算法结束,算法流程图如图2所示。

3 实验与结果分析

3.1 实验过程

从网络中摘取1 028篇关于Java教程内容的文档进行实验,其中关于Struts的文档有22篇,Hibernate文檔有37篇,Spring文档有38篇,Java多线程文档有135篇。对每个类别的文档分别进行聚类,一共进行4次聚类操作,聚类结果如表1所示。

3.2 实验结果分析

从聚类结果分析,有些文档并没有与其它文档聚为一类,成为孤立的噪点,还有些文档并没有准确聚到相应的簇中。出现这种情况的原因有很多,比如文档的特征词汇不能很好地反映文档的特征,特征词汇对文档之间的区分度反应不明显。但从总体来看,DBSCAN算法能够有效将相似的文本聚为一类,从而对文本进行组织管理。

4 结语

本文综合利用DBSCAN聚类算法与文本相似度算法对文本进行聚类,把相似的文本聚为一类,实现对文本的管理。实验过程中也发现一些不足,比如一些文档由于特征不明显会被当作孤立点处理或不能聚到正确的类别中,这就需要对文本特征的提取和算法的优化作进行一步研究。但从实验数据分析来看,DBSCAN聚类算法能有效对大部分的文本进行有效的聚类,实验结果表明这种方法是有效的。

参考文献:

[1]许芳芳.基于DBSCAN优化算法的Web文本聚类研究[D].上海:华东师范大学,2011.

[2]PANG-NING TAN,MICHAEL STEINBACH,VIPIN KUMAR.Introduction to data min[M].北京:人民邮电出版社,2006(1):32-45.

[3]刘远超,王晓龙,刘秉权,等.信息检索中的聚类分析技术[J].电子与信息学报, 2006(4):29-32.

[4]王伟.文本自动聚类技术研究[J].情报杂志,2009(2):94-97.

[5]傅华忠,茅剑.基于DBSCAN聚类算法的Web文本挖掘[J].科技信息,2007(1): 55-56.

(责任编辑:陈福时)

软件导刊 2016年8期

软件导刊的其它文章 翻转课堂教学模式应用研究 基于生态和谐理念的网络学习空间建设及应用 基于云的高校协作学习方案设计 基于MOOC的混合教学方法研究 以计算思维培养为导向的《C语言程序设计》课程教学改革 高校编程类课程云端仿真实验教学平台创新设计与应用
转载请注明来源。原文地址:https://www.5420.com.cn/view/2018/1011/5315/
 与本篇相关的热门内容: