大数据的密度统计合并算法

来源：软件学报杂志2015年第11期北京时间：

作者：刘贝贝,马儒宁,丁军娣

单位：刘贝贝，南京航空航天大学 理学院, 江苏 南京 21110011,马儒宁，南京航空航天大学 理学院, 江苏 南京 21110002,丁军娣，南京理工大学 计算机科学与技术学院, 江苏 南京 21009403

摘要：针对处理大数据时传统聚类算法失效或效果不理想的问题,提出了一种大数据的密度统计合并算法(density-based statistical merging algorithm for large data sets,简称DSML).该算法将数据点的每个特征看作一组独立随机变量,并根据独立有限差分不等式获得统计合并判定准则.首先,使用统计合并判定准则对Leaders算法做出改进,获得代表点集;随后,结合代表点的密度和邻域信息,再次使用统计合并判定准则完成对整个数据集的聚类.理论分析和实验结果表明,DSML算法具有近似线性的时间复杂度,能处理任意形状的数据集,且对噪声具有良好的鲁棒性,非常有利于处理大规模数据集.

关键词：聚类;抽样;代表点;密度;大数据

基金资助：国家自然科学基金(61103058, 61233011)