适用于大规模文本处理的动态密度聚类算法.ppt
《适用于大规模文本处理的动态密度聚类算法.ppt》由会员分享,可在线阅读,更多相关《适用于大规模文本处理的动态密度聚类算法.ppt(19页珍藏版)》请在三一文库上搜索。
1、适用于大规模文本处理的动态密度聚类算法,李霞 广东外语外贸大学智能信息处理研究所 http:/ 2012.11.4 NLP&CC2012,报告内容,研究背景 算法介绍 实验分析 结论,1 研究背景,当前面向海量文本数据的自然语言处理和数据挖掘技术正逐渐成为新的研究热点,如: 微博情感倾向性分析研究 面向互联网新闻及评论内容的网络舆情监测及预警研究 面向海量数据的社会网络分析等。 在这些应用研究中,聚类算法被广泛使用,然而海量文本数据所具有的大规模和高维特征、类分布倾斜和不平衡问题、以及对算法的高效率要求,对传统聚类算法提出了新的要求。,1 研究背景,从聚类的角度看,文本的分布倾斜和不平衡问题可
2、以看成是数据的密度不均匀问题,传统的基于密度的优秀聚类算法可以发现不同大小和形状不同的聚类,如DBSCAN, CURE, Chameleon和SNN等算法。 然而以上算法在处理海量大规模高维文本数据时,存在一些实际应用问题: 参数输入复杂:算法的输入参数均为2个以上,且设置方法复杂对用户具有较高要求; 算法的时间复杂度高:算法在大规模高维数据集上时间复杂度为O(n2); 不能处理混合属性的数据:实际领域中很多数据具有混合属性。,2 算法介绍,应对传统聚类算法的问题,我们提出了两阶段动态密度聚类算法(A Two-Step Dynamic Density-Based Clustering Algo
3、rithm, 简称TSDDBCA),该算法具有以下特点: 能够识别密度不均匀、大小不同的空间聚类 简化了用户的输入参数 能够处理混合属性数据 时间复杂度为近似线性时间复杂度,能够处理海量文本数据,DDBCA算法,经典DBSCAN算法通过检查数据集中每个对象的eps邻域来寻找类簇,但由于半径阈值eps和密度阈值MinPts均为全局参数,因此DBSCAN无法识别密度不均匀的簇。 SNN算法改进了密度的定义方法,将对象所有k最近邻中与其共享的邻居个数总和定义为密度,该密度定义能够动态反应簇的密度变化,因此能够识别密度不均匀的簇。然而SNN算法需要三个输入参数:最近邻个数k,半径阈值eps和密度阈值M
4、inPts,虽然算法本身提供了参数设置的方法,但对普通用户要求较高,且较为繁复。,DDBCA算法,提出一种简化的密度定义方法,对某个对象p,将所有其k最近邻与其距离的和的平均值的逆定义为对象p的密度,该密度定义直观反应了密度不同的空间聚类,当k值一定时,低密度区域对象到其k个最近邻的距离和的平均值要大于高密度区域对象到其k个最近邻的距离和的平均值,所对应的逆值则前者小于后者,即低密度区域对象的密度值要低于高密度区域对象的密度值。,DDBCA算法,算法思想:为了能够自动区分密度不同的簇,对每个对象依据其密度值进行降序排序,从密度最大的对象开始建立一个新簇,并迭代地聚集从该对象直接密度可达的对象,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 适用于 大规模 文本 处理 动态 密度 算法
链接地址:https://www.31doc.com/p-3194347.html