基于Spark的大规模高效聚类算法研究与实现

来源 :南京大学 | 被引量 : 0次 | 上传用户:a692039471
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
聚类分析是数据挖掘、机器学习、模式识别等领域的基础性算法之一,也称作无监督分类,被广泛应用于计算机科学、经济学、医学、社会科学等行业,受到各行业的关注。聚类的目的是使得同一类别的数据具有较高的相似度,不同类之间的相似度尽可能低,从而挖掘出数据中潜在的类别信息。近年来,基于各种分布式平台的聚类算法相继出现。但大规模数据聚类仍存在计算开销大、迭代时间长、聚类效果不够理想等问题。例如,目前基于Spark分布式大数据处理平台的K-means聚类算法具有简单直观、易于分布式实现等优点,但最终聚类结果受初始聚类中心选择的影响较大。再而谱聚类算法能够在任意形状的样本空间上实现聚类,并收敛至全局最优解,但谱聚类算法的计算开销大,不仅需要计算任意两个样本之间的相似性,还需要计算矩阵的特征向量。作为新型聚类算法,联合聚类利用了聚类的二元性,对全局信息的两个维度同时进行聚类,能够得到较单向聚类算法更为全面的聚类结构,然而算法中涉及到的矩阵运算开销大且难以合理并行化,严重限制了其应用范围。基于上述问题背景,本文针对目前大规模聚类算法存在的主要问题,结合现有主流的大数据处理分析平台Spark,研究实现了多种数据场景下的高效并行化聚类算法。本文的主要研究工作和贡献有以下几点:(1)研究实现并行化样本特征预处理方法,为大数据聚类分析提供高效可靠的数据预处理过程。相比于目前已有的特征预处理方法,本文提出的并行化特征预处理方法具有更好的性能和扩展性,并能够进一步提升算法的聚类效果。(2)研究实现快速K-means聚类算法,主要包括密度感知的自适应聚类中心初始化方法,能够根据数据分布情况初始化聚类中心个数和位置,一定程度上降低了迭代轮数,提升了聚类效果;并采用距离计算优化措施,进一步减少每轮迭代中的计算开销。(3)研究实现并行化谱聚类算法,设计实现基于多轮迭代的样本相似度计算方法,有效解决了相似度计算的扩展性问题,避免重复计算。同时,实现基于ScaLAPACK的高效特征向量并行化算法,缩短了特征问题求解的时间。使得算法在大规模数据集下表现出良好的性能和可扩展性。(4)研究实现基于NMF的并行化联合聚类算法,通过迭代求解的方式解决了联合聚类算法中矩阵乘法运算在大规模数据集下的性能和扩展性问题。相关实验表明,该算法仅需较少的迭代轮数,就能保证结果收敛且取得良好的聚类效果。(5)在上述研究工作基础上,基于Spark平台设计实现了快速K-means聚类算法、并行谱聚类算法和并行化联合聚类算法。在保证聚类效果同时,使得算法更好地适用于大规模场景。实验表明,本文提出的聚类算法能够很好地改善大规模数据集下聚类算法的性能问题,并具有良好的数据可扩展性和节点可扩展性。本文工作所实现的快速K-means聚类算法在2017年教育部科技发展中心主办的第三届“全国高校云计算应用创新大赛”大数据技能赛全国总决赛上,以其优异的算法性能与效果,获得聚类赛题第一名的成绩。
其他文献
在我国城镇化大发展的背景下,城市建筑中钢结构建筑物比例越来越高。过去的20年里中国钢铁产量呈直线上升,现今中国钢铁总产量已排在世界前列。与其他材料相比,钢材主要优点
国家形象是国内外公众对一个国家整体性和综合性的评价,是一个国家综合国力和国际地位的反映,是主权国家的无形资产,也是国家软实力的重要体现。改革开放三十多年来,中国的经
本文通过采用随机分析理论、有限时间稳定理论、驱动响应控制和积分不等式等方法,研究了中立型神经网络系统的均方指数输入-状态稳定性、模糊惯性细胞神经网络的有限时间和固
随着现代科技的发展,机械臂已逐渐应用到人们生产和生活的诸多方面,极大地促进了工业和科技事业的快速发展。在工业生产过程中,多个机械臂组成的网络化系统与单个机械臂相比,
钢管约束混凝土具有优良的抗侵彻性能,在防护工程中应用前景广阔。本文在现有圆钢管约束混凝土抗侵彻性能和机理研究的基础上,开展了多边形钢管约束混凝土靶结构单元抗侵彻试
近些年来,随着工业化进程的推进,规模巨大、目标多样、功能综合的空间互联系统日益增加。针对具有重复运行特性的多节点空间互联系统,相关控制技术受到了学者们的广泛关注。
大气污染问题越来越受到国际社会的关注,近年来我国成为了首要的碳排放国家,政府面对着国际社会空前的温室气体减排压力。深入探究地区工业增长与二氧化碳排放的脱钩关系及其
随着我国社会经济的快速发展,城市化和城镇化已经是社会发展的必然趋势,尤其是现在小城镇的发展速度更加的突出。而小城镇的发展极大地促进了农村经济的发展和繁荣,在实现社
轮毂电机驱动电动汽车作为新能源电动汽车的重要组成部分,已经得到世界各国越来越广泛的关注,而轮毂电机驱动电动汽车由于轮毂电机置于电动轮中引起整车非簧载质量增加造成的
血管内超声(IVUS)技术扫描半径大,穿透能力强,能够精确地反映冠心病的病变性质、严重程度以及病理组成。IVUS图像中内膜和中-外膜边界对冠状动脉粥样硬化斑块的定量分析具有