论文部分内容阅读
随着信息技术的高速发展,数据的规模呈现爆炸式增长。从错综复杂的数据中挖掘出有价值的信息具有巨大的实际意义。聚类算法作为数据挖掘领域中的一类重要方法,被广泛应用于数据分析与挖掘中。DBSCAN算法是一种典型的聚类算法,以数据密度为度量,可以识别数据集中任意形状的类及噪音点。本论文以DBSCAN算法为研究对象,针对其对数据参数Eps和MinPts敏感、在处理非均匀密度数据集时效果不理想等问题进行研究,提出了改进方法,并给出了一种适合于大规模数据的聚类方法。论文的研究工作得到了国家自然科学基金项目(No.61172072、61271308)、北京市自然科学基金项目(No.4112045)和高等学校博士学科点专项科研基金(No.20100009110002)的支持。论文的主要工作如下:首先,为了提高DBSCAN算法对非均匀密度数据集聚类的准确性,本文提出了自适应的非均匀密度聚类算法(Adaptive Varied-Density-Based Spatial Clustering ofApplications with Noise,AV-DBSCAN)。该算法改变了 DBSCAN 算法的邻域及类的定义,将DBSCAN算法中的Eps-邻域改为MinPts-邻域;并通过M-近邻有向图间接得到全局密度参数Eps和MinPts的值,减少了人为选择密度参数的困难。算法将一个类定义为类核心集与类边界集的组合。在聚类中引入有向图的最大连通分量思想,用以识别数据集中的类核心集;再利用有向图的弱连通性识别剩余数据集中的类边界集。与DBSCAN算法相比,该算法在保持相同时间复杂度的前提下,不仅提高了对非均匀密度数据聚类的准确性,也降低了对密度参数的敏感性。然后,为了适应当今数据集规模不断加大,本文提出了基于平衡迭代归约的自适应非均匀密度聚类算法(Balanced Iterative Reducing-Adaptive Varied-Density-Based Spatial Clustering of Applications with Noise,BIRAV-DBSCAN)。该算法综合了 BIRCH算法简单高效与AV-DBSCAN算法准确性高的优势。它可以利用有限的内存资源及较少I/O消耗,以较小的误差对大规模的非均匀密度数据集进行高效率聚类,并且可以识别数据集中任意形状的类和异常点。由于该算法扩展性较好,如果将该算法与并行化技术结合可以增大对大规模数据集的处理能力。最后,为了评估AV-DBSCAN和BIRAV-DBSCAN算法的有效性及可靠性,本文采用两个仿真数据集及一个新闻数据集进行实验。实验结果验证了 AV-DBSCAN算法在对非均匀密度数据集聚类时具有较高准确性;BIRAV-DBSCAN算法在有限的精度损失下,聚类的效率更高,并且其运行时间随着数据集规模的增长呈线性增长趋势。因此BIRAV-DBSCAN算法更为适宜较大规模数据集的聚类问题。