基于最短路径策略的分层聚类方法研究

发布时间：2020-07-24 18:08

【摘要】：聚类是数据分析的一种基础操作。聚类算法由于聚类过程和结果形式的不同,分为划分聚类和分层聚类两大类。因为分层聚类算法使用树型结构表示结果,其包含的信息量更大,并且不需要用户提供任何参数,由此可见分层聚类算法具有一定的优势。但在实际应用中,由于分层聚类算法的过程是确定的,如果在算法执行过程中某一合并或分裂操作不当,就会导致错误的聚类结果,从而影响聚类的准确性。近几年,计算机界出现了一种解题的新思路,将目标问题转换为最短路径问题,再借助求解最短路径问题的思路求解目标问题。因此,本文借鉴了求解最短路径问题的思路对分层聚类算法进行了深入的研究。首先,分析现有的聚类算法,通过对分层聚类算法与划分聚类算法进行比较,剖析了分层聚类算法的优势和不足之处;并研究现有的路径搜索算法,分析搜索算法的优缺点。其次,为了解决分层聚类算法中不能回溯的问题,提出了一种基于最短路径策略的分层聚类算法(Shortest path hierarchical clustering algorithm,简称SPC)。其基本思想是首先将分层聚类问题转换为一个最短路径问题,然后通过A~*(A-Star,简称A~*)算法的搜索策略来求解该最短路径问题,进而达到对分层聚类问题的求解。通过理论分析和模拟实验,验证了SPC算法相对于DNA简约算法(DNA parsimony program,简称DNAPARS)在运行效率和准确性上都有提高,说明SPC算法具有一定的优越性。再次,由于当数据量较大时,SPC算法所需的运行时间比较长,针对此问题,提出了一种基于CUDA(Compute Unified Device Architecture,简称CUDA)加速的SPC算法(Shortest path hierarchical clustering algorithm based on CUDA accelerated,简称cudaSPC)。其主要的工作是利用GPU(Graphics Processing Unit,简称GPU)硬件并行地扩展多个节点。在模拟实验中,通过与SPC算法进行比较,结果表明cudaSPC算法在准确性不变的情况下,提高了算法的执行效率。最后,对全文进行了概括,并对将来的研究工作进行了展望。
【学位授予单位】：中国民航大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13

【参考文献】