目录
正文内容
前言
东北大学本科毕业论文
快速的局部方向中心性聚类算法(FCDC)
摘 要
随着大数据时代的来临，数据挖掘和机器学习在许多领域中都发挥着越来越重要的作用。聚类分析是机器学习和数据挖掘领域的重要分支，它的研究和发展推动了相关领域的学术进步和创新。聚类分析作为数据挖掘中的一种重要技术，旨在将数据集划分为若干个簇，使得同一簇内的数据尽可能相似，不同簇的数据尽可能不同，进而帮助人们从大规模和复杂的数据中发现模式、提取信息并做出决策，对于数据驱动的决策和智能化处理具有重要的意义。
近年来，基于局部方向中心性聚类算法—CDC（Clustering algorithm using the local Direction Centrality）引起了广泛的关注。CDC 算法利用k近邻点分布的均匀程度来区分数据集中的簇结构，相比传统的基于密度的聚类方法，该算法在处理存在异构密度和弱连接问题的数据集上表现更为出色，具有更高的聚类准确性和稳定性。然而，该算法在处理大规模数据集时存在致命的缺陷，处理大规模数据集时所花费的时间代价过大。因此本文在CDC算法的基础上提出了一种快速局部方向中心性聚类算法（Fast Clustering algorithm using the local Direction Centrality, FCDC）。
FCDC算法的设计思路主要包括四个方面。（1）提出了用于加速k近邻计算的基于Z值空间填充曲线的Zoom算法，其核心思想是利用 Z阶空间填充曲线划分保持数据局部空间性的特点，缩小对于求k近邻点的计算范围，同时通过储存中间结果，减少浮点数平方开方运算；（2）提出了基于k近邻点的可达距离的RDK优化算法，即减少计算欧式距离的次数，通过缩小可达距离的计算范围实现的，具体而言，在计算可达距离时，仅针对k近邻点，而非全局数据点；（3）提出了基于并查集的CU算法，它是通过减少同簇内部点合并操作的运算时间进而优化聚类过程；（4）引入分布式运算，通过基于Spark的分布式并行计算，将大型数据集划分为多个部分，并将这些部分分配到不同的计算节点上并行处理，从而缩短计算时间。
实验结果表明，FCDC算法在多个方面都表现出色。在准确性方面，FCDC算法能够更精准地识别数据集中的模式和群体；在执行效率方面，FCDC算法与CDC算法相比显著缩短了处理时间。总体而言，FCDC算法在处理大规模数据集时展示了其优越性和实用性。
关键词：聚类算法；Z阶填充曲线；分布式
ABSTRACT
With the advent of the era of big data, data mining and machine learning are playing an increasingly important role in many fields. Clustering algorithms are important branches in fields such as machine learning and data mining. Their research and development have promoted academic progress and innovation in related fields. Cluster analysis, as an important technology in data mining, aims to divide data sets into several clusters so that the data in the same cluster are as similar as possible, while the data in different clusters are as different as possible, helping people to discover patterns, extract information and make decisions from large-scale and complex data. It is of great significance for data-driven decision-making and intelligent processing.
In recent years, the Clustering algorithm using the local Direction Centrality (CDC) has attracted widespread attention. The CDC algorithm distinguishes the cluster structure in the data set based on the local direction centrality measure (DCM) of the relative k-nearest neighbor points. Compared with the traditional density-based clustering method, the CDC algorithm performs better in dealing with heterogeneous density and weak connection problems of clustering algorithms, and has higher clustering accuracy and stability. However, the CDC algorithm still has certain challenges when processing large-scale data sets, mainly in the k-nearest neighbor operation, the reachable distance operation and the clustering process. The time consumption is too large, which is not friendly to large data sets. Therefore, this thesis proposes a Fast Clustering algorithm using the local Direction Centrality (FCDC) based on the CDC algorithm.
The design ideas of the FCDC algorithm mainly include four aspects. (1) The Zoom optimization algorithm of k-nearest neighbor based on the Z-value space filling curve. Its core idea is to use the technology of Z-value space filling curve partitioning to project the data of high-dimensional space into one-dimensional space, maintain the spatial locality of the data, reduce the calculation range for finding k-nearest neighbor points, and reduce the square/root operation of floating point numbers by storing intermediate results; (2) The RDK optimization algorithm based on the reachable distance of k-nearest neighbor points only calculates the reachable distance for k-nearest neighbor points instead of global data points, reducing the number of operations; (3) The clustering optimization CU algorithm based on union-find sets reduces the operation time of merging points within the same cluster; (4) Introducing distributed computing, through distributed parallel computing based on Spark, large data sets are divided into multiple parts, and these parts are assigned to different computing nodes for parallel processing, thereby shortening the computing time.
Experimental results show that the FCDC algorithm performs well in many aspects. In terms of accuracy, the FCDC algorithm can more accurately identify patterns and groups in the data set; in terms of execution efficiency, the FCDC algorithm significantly shortens the processing time compared with the CDC algorithm. Overall, the FCDC algorithm demonstrates its superiority and practicality when processing large-scale data sets.
Keywords: Clustering algorithm; Z-order filling curve; Distribut
目 录
1 绪论
聚类算法是一类重要的数据分析技术，其核心思想是将数据集划分为若干个组（称为簇），使得同一个簇中的数据点在某种意义上具有较高的相似性，而不同簇中的数据点则具有较大的差异性。
1.1 研究背景
进入大数据时代，数据挖掘[1] 和机器学习[3] 的应用日益广泛，覆盖了许多不同的领域。聚类算法是这些应用中的关键技术之一，通过将数据集划分为若干个簇，研究人员和企业可以从海量数据中提取有价值的模式和信息，进而支持智能决策和优化处理。这些算法在市场营销、生物学、医学和经济学等领域都有着广泛的应用，发挥了至关重要的作用。
市场营销中，聚类算法用于市场细分和目标客户群体的识别，通过分析消费者行为和特征，将市场划分为不同的群体,帮助企业更好地了解客户需求和偏好，制定更加精准的营销策略和产品定位, 提高用户满意度和忠诚度。在生物学中，聚类算法用于基因表达数据的分析，识别基因功能和疾病关联, 例如，通过聚类分析，研究人员可以发现某些基因在特定条件下的表达模式，进而推测其生物功能。在图像处理领域，聚类算法常用于图像分割。通过将图像像素聚类为若干区域，实现图像压缩和目标识别。例如，在医疗影像分析中，聚类算法可以帮助分割MRI或CT图像中的不同组织区域，辅助医生进行诊断和治疗。聚类算法在社交网络分析中应用广泛。通过分析社交网络中的用户群体，可以识别社区结构和用户兴趣群体。例如，社交媒体平台可以利用聚类算法识别用户的兴趣群体，推荐相关内容和好友，增强用户体验。聚类算法在文本挖掘中也有广泛应用。通过将文档聚类为不同主题，可以提高信息检索和主题建模的效果。例如，新闻聚合平台可以利用聚类算法将内容相似的新闻归类到同一个主题，提高用户的阅读体验。而在经济学中，聚类算法用于分类和比较经济指标，为区域经济发展提供参考。在社交网络分析中，通过分析社交网络中的用户群体，可以识别社区结构和用户兴趣群体。例如，社交媒体平台可以利用聚类算法识别用户的兴趣群体，推荐相关内容和好友，增强用户体验。
然而，随着数据量的急剧增长和数据结构的复杂化，传统的聚类算法在处理大规模和复杂数据时面临着诸多挑战。现有的算法，如K-means[5] 和DBSCAN[6] ，在处理异构密度数据和弱连接数据时，通常表现出性能不足的问题。这些算法在处理高维数据和非均匀分布数据时，容易出现簇划分不准确的情况。CDC算法的思想对于异质密度和弱连接问题表现很好，但随着数据规模的扩大，传统算法也都在计算效率上面临瓶颈，难以满足海量数据、快速处理的实际需求。
为了解决这些问题，本文研究提出了一种快速的局部方向中心性聚类算法。该算法通过引入方向中心性的概念，有效应对异构密度和弱连接数据的问题。方向中心性通过度量每个数据点的k最近邻（knn）分布均匀性，能够准确区分内部点和边界点，从而提高聚类的精度和稳定性，算法采用空间填充曲线划分和分布式计算技术，大幅提升了处理大规模数据的效率。
这种新型聚类算法在多个领域中展现出广阔的应用前景。例如，它可以为市场营销中的细分市场分析提供更精准的结果，在生物学中更有效地分析基因数据，在地球科学中更准确地进行环境监测和地质分析，以及在经济学中更细致地分类和比较经济指标。尽管该算法目前还处于实验阶段，但初步实验结果显示出其在多个方面的应用潜力。例如，初步实验显示该算法在处理大数据集时表现出色，计算效率显著提升。在处理各类数据时聚类的精度也非常高，能够更好地识别数据中的复杂结构，提供更精细的聚类结果。
综上所述，快速的局部方向中心性聚类算法的设计与实现，在理论上具有重要的研究价值，并在实际应用中展现出显著的潜力。随着进一步的研究和开发，该算法有望为大数据时代的数据挖掘和机器学习提供一种高效、可靠的工具，推动相关领域的持续发展和创新。
1.2 研究现状
聚类算法是数据挖掘和机器学习领域的重要分支，其研究在国内外都受到了广泛的关注。以下是对聚类算法研究现状的简要概述。
1.2.1 聚类的分类体系
国内主流聚类算法根据聚类思想可以总结为以下5种类型：基于划分方法的聚类算法[5][7-8]，基于层次的聚类算法[9-11][13] ，基于密度的方法的聚类算法[6] [12-15]，基于模型的聚类算法[16-17]还有基于网格的聚类算法[18-20]。以下是这5类算法的简单介绍。
(1)基于划分方法的聚类算法划分方法通过直接将数据集分为若干个互斥的簇。每个簇由一个中心点（质心）表示，常见算法包括K-Means[5]和K-Medoids[7]。K-Means算法的主要步骤包括随机选择K个初始质心，将数据点分配到最近的质心所在的簇中，并不断更新质心直至收敛。尽管计算简单且适用于大规模数据集，但该方法需要预先指定簇的数量，并且对初始质心的选择较为敏感，容易陷入局部最优。与K-Means类似，但使用实际的点作为质心，对噪声和异常值的鲁棒性更好，但计算量更大。
(2)基于层次的聚类算法通过构建层次树表示数据的聚类过程，分为凝聚层次聚类和分裂层次聚类两类。凝聚层次聚类从每个数据点开始，逐步将最近的两个簇合并，直至所有数据点合并成一个簇；分裂层次聚类则从一个簇开始，不断将最不相似的簇拆分，直到每个数据点成为单独的簇。层次方法的优点是不需要预先指定簇的数量，能够揭示数据的多层次结构，但其计算复杂度较高，不适合大规模数据集。
(3)基于密度聚类算法通过识别数据点的高密度区域形成簇，代表算法有DBSCAN[6]和OPTICS[11]。DBSCAN通过设定距离阈值和最小点数定义簇的密度，能够发现任意形状的簇，并有效处理噪声数据。然而，该方法对参数选择较为敏感，不适合处理不同密度的簇。OPTICS通过计算每个点的核心距离和可达距离。按照可达距离进行排序，形成聚类，能够发现不同密度的簇，克服了DBSCAN对参数选择的敏感性，但是算法的计算量较大。
(4)基于模型的聚类算法假设数据由某种概率模型生成，通过估计模型参数进行聚类。高斯混合模型（GMM）[15] 是典型代表，通过期望最大化（EM）算法[17] 估计参数，适用于处理不同形状和大小的簇。尽管具有较强的数学理论基础，但该方法计算复杂度高，对初始参数敏感。
(5)基于网格的聚类算法将数据空间划分为有限数量的单元格，通过单元格的密度进行聚类。首先，将数据空间划分为层次性的网格结构，然后为每个网格单元计算统计信息，之后根据网格单元的统计信息进行聚类。该类方法计算效率高，适用于大规模数据集，但对网格划分方式较为敏感，可能导致信息丢失。
同时随着大数据技术的发展，国内外研究者也开始关注大规模数据的聚类算法，如基于MapReduce的并行聚类算法、基于分布式系统的聚类算法等。这些算法在处理超大规模数据集时表现出较好的性能。
1.2.2 经典聚类算法
以下是5种经典的聚类算法的具体介绍。
（1）DBSCAN[6] ：DBSCAN是一种基于高密度连通区域的聚类算法，旨在识别核心对象，即其邻域内密度较高的对象。该算法将核心对象及其邻域连接起来，最终形成密集区域作为簇。对象的邻域是以对象为中心、半径为r的空间，邻域密度通过邻域内对象的数量来衡量。DBSCAN能够识别任意形状的簇，并能区分噪声数据点，增强了抗噪声能力。然而，该算法在处理密度差异较大的簇时，可能无法准确识别，因为它将数据对象简单地分为噪声点、核心点和边缘点。
（2）EM[15]（期望最大化）算法通过迭代过程优化簇的分配。首先，给定当前簇中心，然后将每个对象分配到离它最近的簇中心。在每次迭代中，算法会调整簇中心，使得分配到该簇的对象与中心的距离之和最小化，即最大化簇内对象的相似度。EM算法是一种框架，用于逼近统计模型参数的最大似然或最大后验估计。它通常假设数据符合特定的概率分布，如高斯混合模型，这限制了其适用范围。
（3）DPC[13]：密度峰值聚类算法（DPC）通过计算每个点的密度（ρ）和到最近的密度更大点的距离（δ），来识别密度峰值。然后，通过将点分配给密度更大且最近的点来完成聚类。DPC继承了基于密度算法的优点，能识别任意形状的簇，并且可以自动计算簇的数量。与DBSCAN不同，DPC不需要设置距离阈值。然而，DPC的时间复杂度为O(n²)，对大数据集处理不友好，并且在处理密度差异较大的簇时效果不佳。
（4）PKMeans[21]：PKMeans利用MapReduce的并行处理能力，在多个计算节点上执行K-Means算法，对大型数据集进行高效聚类。通过在不同节点间分配工作负载和中间结果，PKMeans增强了传统K-Means算法在大数据应用中的可扩展性和性能。
（5）PDBSCAN[22]：PDBSCAN是DBSCAN在分布式环境下的实现，使用dR*-tree作为分布式空间索引结构。数据分布在多台计算机上，每台计算机上都有数据索引的副本。
其中PKmeans和PDBSCAN都是通过结合MapReduce编程框架，利用分布式计算加速算法运行速度，适应大数据处理需求。然而，由于Hadoop平台的读写瓶颈以及传统聚类算法本身的一些缺陷，在处理结构复杂的大数据时，其有效性和高效性仍有提升空间。
1.3 本文研究内容
当前选题重点关注了聚类算法中存在的两个问题：异质密度与弱连接性。在聚类过程中，异构密度和弱连通性问题显著影响聚类质量。异质密度是指密度不均匀的聚类容易被分割成多个部分，稀疏的聚类容易被误识别为噪声，而数据集的弱连通性可能导致彼此聚类较近的簇难以分离，识别为同一个簇。
本毕业设计主要通过基于方向中心性的聚类思想解决传统聚类算法中出现的异构密度问题，弱连接问题的问题，并通过Z阶空间填充曲线[13]和基于Spark的分布式并行运算提升算法运行效率，在此基础上提出了快速的局部方向中心性聚类算法FCDC。采用Z阶填充曲线优化算法-Zoom(Z-Order for KNN with Distance Map)计算出每个点的k近邻点。在k近邻点的基础上计算每个点的DCM，排序并确定阈值TDCM，将各点的DCM排序中前TDCM中划分为边界点，剩余的点划分为内部点。在内部点之间寻找两点欧式距离之和小于等于两点可达距离的内部点，将其划入同一类。之后将边界点划分到离自己最近的簇中。
最后通过对于FCDC算法与CDC算法[7]在相同数据集上得到的聚簇结果进行分析，通过性能指标分析FCDC算法相对于CDC算法的性能提升。具体的评价性能程序运行时间，计算所用的资源内存资源，表示聚类算法的效率差异。之后扩展到分布式环境的下的FCDC将大型数据集划分为多个部分，并将这些部分分配到不同的计算节点上同时并行处理，从而缩短计算时间，提升聚类算法的运行效率。主要在求k近邻时，基于Spark计算框架并行执行Zoom算法，提高运算效率。
FCDC旨在高效地处理大规模数据集并准确划分内部点和边界点。具体的优化思路包括几个关键步骤。
(1)Z-Order填充曲线映射：将二维平面的点映射到一维坐标轴上，利用Z-Order填充曲线的方法，可以将相对距离较近的点集中在一起。这样在寻找某个点的k近邻时，只需要在映射后的坐标轴上一段较小的范围内进行查询，避免了全局范围的遍历，大幅降低计算量。
(2)基于Spark的分布式运算：借助Spark的分布式计算框架，进一步提升运算效率。Spark的分布式特性使得大规模数据处理变得更加高效和可扩展。 在并行计算过程中，每个点的k近邻集合被存储起来，避免重复计算，提高计算效率。
(3)可达距离的计算：在内部点和边界点的k近邻中寻找可达距离/索引，在的k近邻集合中优先寻找连接点。在获取可达距离之后，首先对同簇的内部点进行连接，之后将已经找到簇的边界点划分到对应的簇中，完成所有点的聚类划分。
1.4 全文组织架构
在第1章中主要介绍了聚类算法的研究背景和应用前景，讨论了当前国内外的研究现状，本文提出了一种快速的局部方向中心性聚类算法（FCDC），通过引入方向中心性概念，解决异构密度和弱连接性问题，利用Z阶空间填充曲线和分布式计算技术提升大规模数据处理效率。
在第2章相关工作中，首先介绍了基于局部方向中心性的CDC聚类算法，并指出CDC算法的一些局限性。引出本文的所要介绍的研究内容—基于Spark的FCDC分布式聚类算法。之后介绍了有关Z阶填充曲线的相关内容，通过Z阶填充曲线将多维数据映射到一维空间同时保持数据点局域性的特点，缩小求k近邻点的范围。
在第3章FCDC算法的设计中，介绍了FCDC聚类算法对于CDC聚类算法的具体优化的设计。（1）实现了数据分片处理，将每一个数据切片放到不同的节点下并行运行；（2）利用计算k近邻点的Zoom算法，将求k近邻点的时间复杂度从降为了级别；（3）在k近邻点中计算可达距离/索引的RDK算法，将时间复杂度降为了级别，（4）利用基于并查集完成的CU聚类算法将同簇内部点的合并操作的时间复杂度从降为了级别。
在第4章中，介绍了FCDC算法的具体实现，包括介绍Spark并行环境下的数据集的划分的实现，在各个节点上Zoom算法，RDK算法的实现以及CU聚类算法实现。
在第5章中，进行了实验性能的分析。进行了FCDC与CDC算法的性能对比测试。实验结果表明，在表现最好的数据集上Zoom算法实现了距离的计算次数为原来的，性能提升到了489%；RDK实现了对于可达距离计算的性能提升，在距离的计算次数为原来的，性能提升到了1633%；CU算法实现了对于聚类过程的性能提升, 在最大的数据集上仅使用了3分34秒完成了原来算法45分钟无法实现的聚类过程。在Spark运算框架下，FCDC算法的运算性能最高实现了170%的提升。
在第6章中总结和展望，针对全文进行了总结，并针对一些具体存在的问题阐述了下一步的解决思路和展望。
2 相关工作
在相关工作中，主要介绍介绍CDC聚类算法与Z阶填充曲线技术。两项技术是FCDC算法的基础，FCDC算法采用了CDC算法的局部方向中心性度量(DCM)来实现内部点与边界点的划分，采用了Z阶填充曲线实现了快速查找k近邻点。
2.1 CDC算法
异构密度是指聚类中存在着密度不均匀的情况，这种情况下容易出现聚类被分割成多个部分的情况，因为密度不均匀导致某些区域的密度较高，而某些区域的密度较低。稀疏的聚类则容易被错误地识别为噪声，因为它们的密度较低，可能与周围的数据点没有明显的连接关系。如图2.1所示，原本的环形聚簇被识别成了多个聚簇。另外，如果聚类之间的连接性较弱，也会导致附近的聚类难以分离，因为它们之间缺乏明显的边界。如图2.2所示，原本的两个聚簇被识别成相同的聚簇。
为了解决聚类中出现的弱连通性和异构密度问题。有学者提出了一种使用局部方向中心性(Direction Centrality Metric, DCM)的聚类算法CDC。它采用基于k近邻(k-nearest neighbors, knn)分布的密度无关度量DCM来区分内部点和边界点。边界点形成封闭的笼子来约束内部点的连接，从而防止跨簇连接，分离弱连接簇。实验数据证明CDC算法在解决弱连接和异质密度的问题方面有着显著的优势。
2.1.1 算法的总体思想
CDC算法的总体思想是首先利用DCM划分聚类的边界点，然后将周围边界点生成的封闭笼内的内部点连接起来。具体来说，簇的内部点在各个方向上都倾向于被它的knn包围，而边界点只包括一定方向范围内的邻近点。利用这种差异，通过计算knn的方向均匀性来衡量局部中心性，以区分内部点和边界点。因此，CDC可以有效地避免跨簇连接，分离弱连接的簇。同时，利用knn搜索与点密度无关的邻近点，可以保持稀疏簇的完备性。
在许多实际应用中，特征空间中的数据分布往往是异构的和复杂的。仅基于密度或物理距离接近度的关联规则难以有效稳定地识别聚类。本章利用局部中心性来区分内部点和边界点。确定的边界点生成封闭的笼，防止内部点的跨簇连接，实现簇形的准确提取。在生成笼的约束下，弱连接簇可以被分离。此外，局部中心性取决于knn的方向均匀性，而不是中心点的密度。因此，CDC能够识别低密度的稀疏聚类。
CDC对异构分布和算法参数具有较强的鲁棒性。在处理形状清晰、密度均匀的聚类时，可以准确地检测到边界点。实际上，非均匀密度会导致内部点和边界点的错误划分。但是，如果确定的边界点足以完成对于内部点的分割，并且只有少数内部点被错误识别，则不会切断簇内连接，从而不影响整个聚簇的准确性。
下面以DS2数据集为示例，演示FCDC算法的聚类过程。图2.3.a是根据DS2数据集的二维坐标和真实标签生成的散点图，其中每一种颜色的点代表一种聚簇。
CDC算法首先会对于每一个点计算k近邻点，然后通过k近邻点计算其DCM值，之后，根据每个点的DCM值与阈值的大小关系，将数据点区分为内部点和边界点两类，结果如图2.3.b所示，其中红色点代表内部点，蓝色点代表边界点，可以观察到边界点完成了整个数据集的分割。接下来通过内部点的可达距离实现内部点之间的聚簇。然后通过可达距离的关系，确认两个内部点是否属于同一个聚簇，聚簇划分的结果如图2.3.c所示，浅色点代表边界点，其他颜色的点代表内部点形成的聚簇。 最后将剩下的边界点指派到最近的簇即完成聚类，得到最后的聚簇结果如图2.9所示。可以观察CDC的聚类结果与原数据集的真实标签达到了高度的一致。
下面是对于计算每个点的DCM值的具体过程的描述。DCM是用来度量数据点k近邻空间分布中心性。如图2.3所示，中心点与其k近邻点形成了k个近邻角，内部点的理想情况下，k近邻点会出现在比较多的方向上，整体的分布更加均匀，而近邻角之间的差距就会很小，理想条件是完美的均匀分布，邻角之为0，相反的极端情况是中心点与其他点位于一条直线上，导致邻角，剩下的。为此，定义方向中心性度量(Direction Centrality Metric, DCM)表示中心点的k近邻分布均匀程度，其值为近邻角的平方差，值越大说明每个角之间的差距越大，近邻点分布的越集中，越有可能是边界点，值越小说明，近邻点分布的越均匀，越有可能内部点。通过具体的参数调整确定DCM的阈值,通过划分出来的边界线分割整个数据集，内部点通过彼此之间的距离与距离自己最近的与可达距离之间的关系完成聚簇，然后将边界点指派到已经划分好的聚簇中。下面介绍DCM的公式推导过程。
首先求关于源点 (, ) 与k邻点(, )求相对X轴正方向的夹角，如图2.5所示。如图2.6所示，实际所求的近邻角是近邻点与中心点连线所成的夹角，所以实际的近邻角是相近的之差，即，具体计算过程时对排序，通过公式2.5算出，而对于则需要公式2.6单独计算。在此基础上计算DCM，具体的如公式2.7所示。考虑DCM最小时—当且仅当时,DCM最小值为： = 0。考虑DCM最大时—当其中一个角等于，其余角为0时，DCM的最大值为：=。之后根据最大值和最小值,将整个DCM归化到[0,1]范围内，具体计算过程如公式2.8，公式2.9所示。
其中, 为近邻点与中心点的X轴，Y轴方向的差值。
其中是根据反三角函数，基于,计算出的夹角, 因为可能出现负角度，所以需要进行相应的调整得到夹角，具体的调整方法，当时，直接加，将所有的夹角统一到[0, ]。
其中指相邻的k近邻点和中心连线形成的夹角，源点 (, ) 与k邻点(, )求相对X轴正方向的夹角。
其中DCM表示本地方向中心性度量，𝑘表示距离最近的邻居的数量, 指相邻的k近邻点和中心连线形成的夹角。
其中表示归化到[0,1]范围之内的DCM,而此时表示未被归化的值，表示DCM的最小值，表示DCM的最大值。
CDC算法的核心思想在于采用基于k近邻分布的密度无关度量DCM来区分内部点和边界点，利用边界点形成的锁链来约束内部点的连接。因为采用的DCM是密度无关的度量，对于解决聚类算法中出现的异质密度与弱连接问题有优异的效果。
2.1.2 面临挑战
随着数据点数量的增加，CDC的计算开销也随之增加。这是因为计算k近邻点，和聚类，涉及到大量的欧式距离计算，这导致了CDC计算量的繁重。大量的计算使得集中式的CDC算法解决方案对于聚类大量数据点是不切实际的。
为了应对这一挑战，本文提出了基于Spark分布式计算框架的FCDC分布式聚类算法，将计算分布到多个服务器上，通过并行运算提升整体的效率。同时针对于全局数据计算所有点的k近邻点时间复杂度仍然是O()，本文提出一种计算代价更小k近邻的Zoom算法，将时间复杂度降为了O()。在计算可达距离时采取仅针对于k近邻点可达距离计算的RDK算法将时间复杂度降为了级别，并采用基于并查集的聚类算法CU算法将同簇内部点的合并操作的时间复杂度从降为了级别。通过上述的优化算法，有效地提升了算法的性能。在保证聚类准确性的前提下，合理运算分配资源，优化计算流程成功解决了CDC算法面对较大规模数据集时运算时间过长的问题。
2.2 Z阶填充曲线
Z阶曲线是一种空间填充曲线，它可以将多维数据映射到一维空间，同时保持数据点相对于原来的空间分布相对集中的特性。
2.2.1 基本原理
图2.7a显示了二维空间下的Z阶填充曲线中点的空间位置与相对顺序。等效来看，就是将等点映射到Z轴之上，因坐标变化获得一个Z值。
为了将多维数据点映射到z顺序曲线，首先需要将数据点的坐标转换为二进制形式。给定一个维数据点，每个维度用一个m位二进制数表示，即设为点的Z值（Z值是多维点映射到z阶曲线的坐标），则定义为：
其中表示的是Z值，表示的是二进制的位数，表示数据点的维度，表示的是的第维的第位的二进制值数值。
图2.7b显示了将二维空间中的点(2,3)映射到一维空z轴(13)的过程。图3.1a中各点的z值在一维空间(z轴)的分布如图2.7c所示。我们可以看到，z值的计算是高效且简单的，因为它只需要简单的位移操作。由的表达式可知，计算z值的时间复杂度为。与Hilbert曲线等其他填充空间曲线相比，z阶曲线在分布式FCDC聚类算法中具有优势。首先，与希尔伯特曲线相比，z阶曲线获得精确的结果所需的时间和空间更少，因为它获得精确的最近邻的代价更小。其次，使用比特洗牌操作可以很容易地计算出z值，这比希尔伯特曲线更有效。
2.2.2 Z值转化过程
Z值转化过程如下图所示：首先是将浮点型坐标转为整型（java语言的int型的取值范围：，同时也是FCDC算法的坐标有效实际识别精度）。然后将坐标以偏移二进制编码的形式表示，进行比特洗牌来计算Z值。
值得注意的是由于在计算机语言中数字的编码方式为补码，若采用补码形式，在跨越坐标轴的点之间的实际距离很小，但Z值差异却十分巨大，失去了数据点的局部性。如 对应的， 对应的12297829382473034410。这是因为在补码(Two's Complement)中1表示为0x00000001，-1表示为：0xFFFFFFFF，因此需要对编码进行一些调整，采用32位的偏移二进制编码(Offset Binary)的形式，-1表示为：0x7FFFFFFF，1表示为：0x80000001保留了编码的相对关系。就整体效果而言，编码调整的效果就是将整个有效范围实现了平移。这样的编码调整方便在后面的调整中保留数据点局部分布性特征，具体的平移效果如图2.9所示。
具体的伪代码描述如表2.1所示。
表2.1 Z-Order算法伪代码描述
2.3 Spark分布式计算架构
Spark最初在2009年由加州大学伯克利分校的AMP实验室开发，并于2010年成为Apache的开源项目之一，如今正在逐渐替代MapReduce成为Hadoop平台之上非常重要的计算框架，具有高吞吐、低延时、通用易扩展、高容错的特点。
Spark并不是一个单一的计算框架，它集成了适合批处理的Spark Core、结构化数据处理的Spark SQL、实时流处理的Spark Streaming、机器学习组件Spark MLlib以及图计算的Spark GraphX多种组件，它不止在计算速度上有了质的飞跃，更加统一多种功能，做到了通用性的实现。Spark的提出主要解决MapReduce实现的一些弱点：首先是难以支持复杂应用场景，如机器学习、流式计算、图计算等，然后是迭代式计算的效率低下等问题。下面介绍Spark的主要特点。
（1）计算高效性
主要体现在3个方面：①对比MapReduce过程当中非常多的内存磁盘数据交互、性能比较低，而Spark计算全部在内存当中完成，不同结点直接数据传输全部通过网络完成，所以速度上比MapReduce更加高效；②基于有向无环图DAG的优化优化任务流程，支持迭代式计算，利用自身的DAG引擎，减少中间计算结果写入HDFS的开销。③利用自身的多线程池模型，极大的减少了任务启动时的开销，避免了很多的排序以及IO操作。
（2）通用性强
主要体现在以下3方面：①多种组件支持批处理，流处理，交互式计算，机器学习等多种开发场景，真正做到通用易用。②提供Local、Standalone、YARN/Mesos等多种运行模式。③丰富的API支持，如Scala、Java、Python等。
基于这些优势，Spark比MapReduce更加适用于以下场景：机器学习和图应用中常用的迭代算法（每一步对数据执行相似的函数）以及交互式数据挖掘工具。
2.3.1 基本原理
Spark 框架的核心是一个计算引擎，整体来说，它采用了标准 master-slave 的结构。如下图2.10所示，它展示了一个 Spark 执行时的基本结构,在Spark 程序执行架构中，Driver表示 master，负责管理整个集群中的作业任务调度，Executor 则是 slave，负责实际执行任务。
在程序运行的时候，首先会运行Driver，Driver相当于是整个任务的管理程序，负责对任务进行解析、分发、监控等。Driver中包含的SparkContext是Spark的运行环境。Driver运行起来之后，会向ClusterManager主节点去申请资源，申请到的资源是在WorkerNode上封装好的Executor容器，容器包含了程序运行的CPU、内存等资源。然后Driver会将Task分发到这些Executor中进行执行，执行过程中，会时刻监控这些Task的运行情况，并做实时的管理和调度。
并且Spark 支持多种运行模式，包括 Local、Standalone 和 YARN等模式。Local 模式是在本地机器上运行 Spark，适用于开发、测试和调试，不需要集群，易于设置和管理，非常适合处理小规模数据集和开发环境。
Standalone 模式是 Spark 自带的集群管理模式，可以独立运行，不依赖于其他资源管理器，易于配置和管理，适合中小型集群，是需要独立管理 Spark 集群的理想选择。Standalone模式是将Spark程序运行在Spark的独立集群中。这种情况下Driver在WorkNode节点运行，Master只负责集群管理，ZooKeeper负责Master HA 避免单点故障 ，然后Task被分发到Worker节点的Executor容器中运行。运行结构如图2.11所示。
YARN模式则是集成在Hadoop生态系统中的资源管理器，允许Spark与Hadoop 生态系统的其他工具（如HDFS）紧密结合，利用现有的 Hadoop 基础设施，提供良好的扩展性和资源管理，非常适合大型数据处理任务，特别是在已有 Hadoop 集群的环境中。这种模式根据Driver的位置不同，又细分为Client和Cluster两种模式。Cluster模式是生产中常见的运行模式，这种模式是由ApplicationMaster来进行资源的申请，然后作业的解析和管控由Driver来执行，此时ApplicationMaster和Driver是在一起的，并运行在NodeManager上。而Client模式则是Driver运行在了Client端，Application运行在NodeManager上负责资源的申请，这样的好处是Driver可以实时的将作业的信息显示在控制台上，便于作业的监控和调优。
2.3.2 程序执行流程
提交了Spark应用程序之后，首先要在Driver中把Spark程序转化成对应的逻辑查询计划，之后根据生成的逻辑查询计划，生成计算机可真正识别的物理查询计划，此时，相当于有了我们细分的各个具体任务，最后再把这些任务进行分发调度。Executor拿到分发的这些个任务，开始任务的真正执行。具体流程如图2.13所示。
逻辑查询计划的生成基本上就是所写的计算逻辑，根据RDD之间的流程关系等，生成对应的逻辑查询计划。物理查询计算依赖于逻辑查询计划。首先根据RDD的种类以及对应的宽窄依赖关系，生成多个Stage，每个Stage之间也会有对应的逻辑关系，如图所示。最后由多个Stage，组成最后的DAG。
实际上的Spark计算框架就是基于RDD的转换过程。弹性分布式数据集—RDD（Resilient Distributed Datesets）是Spark特有的数据处理模型，Spark当中的计算都是通过操作RDD来完成的；同时也是Spark的基本计算单元，是对分布式内存的抽象使用，实现了以操作本地集合的方式来操作分布式数据集的抽象实现。它表示弹性的，可分区，不可变的并能够被并行操作的数据集合，不同的数据集格式对应不同的RDD实现。
RDD的弹性（Resilient）体现在4个方面：（1）存储的弹性：内存与磁盘的自动切换；（2）容错的弹性：数据丢失可以自动恢复；（3）计算的弹性：计算出错重试机制；（4） 分片的弹性：可根据需要重新分片。
RDD的分布式（Distributed）体现在：数据存储在大数据集群不同节点上。如下图2.14所示：RDD由多个Partition组成,存储在不同节点的内存或者磁盘中。
RDD中只是封存了计算逻辑，并存存储数据，并且不可改变。若想要改变，只能基于已有的RDD创建新的RDD，并在其中封存新的计算逻辑。实际的Spark计算过程实质就是RDD之间的转换过程。由于RDD可以cache到内存中，每次对RDD数据集的操作之后的结果，都可以存放到内存中，下一个操作可以直接从内存中输入，省去了MapReduce大量的磁盘IO操作。在实际的计算过程中，不同节点的计算可能需要使用到其他节点的数据，为了不同节点之间的通信，RDD必须是可序列化的。因为RDD的创建操作只能是基于稳定的数据集或者已有的RDD，因此整个Job任务在计算过程中如果出现错误，可以通过这一系列的转换、算子追述到之前的操作，自动重构从而保证计算的正确性。同时RDD对应用完全透明，开发人员在编写代码时，只需要对于RDD进行操作即可，不需要其他的处理。
以数据预处理重复点中的统计重复点的数量为例，其实际的执行流程：首先获得HDFS中的某一个数据集，并把它封装成一个RDD。之后，对这个RDD执行了flatMap来对数据进行分割压平，Map把每个分割后的数据转换成键值对的形式，并对每个键值对的Value赋值为1，最后对这些相同Key的键值对进行整合累加，来完成之前已经用MapReduce实现过一次的Count。值得注意的是对数据集的操作是以对RDD操作的形式完成的，flatMap和map都是Transformation算子，并没有真正触发执行，仅仅只是逻辑操作而已，而之后的reduceByKey算子，统计数据集中元素个数，此时才会真正执行操作。
2.4本章小结
本章首先介绍了CDC算法通过划分边界点和内部点来有效分离弱连接簇，处理异构密度分布的数据并指出了CDC算法的一些局限性。引出本文的所要介绍的研究内容。然后介绍了Z阶填充曲线的相关内容，通过它将多维数据映射到一维空间，同时保持数据点的局域性，进而在缩小求k近邻点的范围,并阐述了具体的实现过程包括使用偏移二进制编码方式，通过对交换比特位的比特洗牌技术计算z值。之后系统地介绍了Spark分布式计算框架，程序的执行过程和RDD之间的转换和依赖关系。
3 FCDC算法的设计
本章在针对CDC算法在面对大规模数据集的效率问题，选择在Spark分布式架构的上将数据集上的点首先进行分片，然后交给Spark集群的不同节点进行并行计算。针对FCDC的计算过程，提出了具体的3个优化算法：(1)基于Z值索引的k近邻优化算法Zoom；（2）基于k近邻点的可达距离优化算法RDK；（3）利基于并查集完成的聚类优化算法CU。
3.1 基本流程框架
FCDC算法的基本流程如图3.1所示，首先对数据集上的点进行分片，然后交给Spark集群的不同节点进行并行计算，因为每个节点计算所需要的数据点都已经分派完毕，每个节点完全并行计算即可。之后在每个节点上，根据Zoom算法计算每个点的可达距离。然后在每个节点上根据k近邻点分布计算可达距离。将每个节点的信息收集到主程序上，使用基于并查集CU聚类算法，完成聚类。
FCDC算法的核心思想是通过DCM来区分内部点和边界点。利用边界点形成的锁链来切割整个数据集，完成内部点之间的合并连接，将边界点指派到最近的聚簇中。完成聚类过程。首先计算DCM的数值，并根据DCM划分内部点和边界点，在计算DCM的过程中，使用了基于Z阶填充曲线的Zoom优化算法的k近邻优化算法；之后根据可达距离完成内部点的连接和外部点的指派，在完成内部点聚类的过程中，使用了基于k近邻的可达距离优化算法和基于并查集数据结构的CU聚类优化算法。
针对于FCDC算法的伪代码描述如下。首先利用Zoom算法计算k近邻点，之后根据近邻点计算DCM值，将数据点分为内部点和边界点，根据RDK算法计算每个点的可达距离/索引，根据CU聚类算法完成内部点的连接和边界点的指派。具体的伪代码描述如表3.1所示。
表3.1 FCDC聚类算法伪代码描述
表3.1 FCDC聚类算法伪代码描述（续）
3.2 基于Spark的数据分片
数据分片是指将数据集分割成多个小块，每个小块可以独立处理，从而提高并行处理能力和系统的整体性能。
3.2.1 基本原理
在Spark中，分片是指RDD（弹性分布式数据集）或DataFrame/Dataset中的一个逻辑片段。每个分片包含一个数据子集，并且可以由一个计算节点独立处理。Spark的分片使得数据处理可以并行进行，从而提高处理速度和效率。一般来讲分片的创建有两种方式,一种是当默认分片，加载数据到RDD或DataFrame中时，Spark会根据数据源的类型和存储位置自动决定分片的数量。例如，从HDFS加载文件时，默认的分片数量是基于HDFS块的大小。另外一种是在创建RDD或DataFrame时显式指定分片的数量。例如，在使用sc.textFile(path, numPartitions)方法读取文本文件时，可以指定numPartitions参数来设置分片数。分片的分布也存在两种分片机制。
默认情况下，Spark使用哈希分片机制，将数据通过哈希函数分配到不同的分片中。对于需要按顺序处理的数据，范围分片是合适的选择。Spark可以根据数据的范围将其分配到不同的分片中，这在排序操作中尤其有用。
对于本文而言，数据分片的意义在于将并行运算中可能用到的点直接分配给节点，保证程序并行执行，分片的主要依据是Z值的范围（对应数据点实际二维距离尽可能近），因此采用范围划分且指定分片数量。
3.2.2 过程描述
对于实际的操作而言，首先读取数据并创建有DataPoint类的dataRDD，每一个DataPoint类对象包含了数据点的坐标，编号，标签和对应的Z值索引。之后首先对dataRDD的Z值索引进行排序，之后进行预划分，之后通过近似半径的确定出预划分的分片实际的划分范围，将重叠的点以通信的方式传递到对应的节点上，保证在后续查找k近邻时所需要的数据都已经划分到了相对应的节点而不需要再进行跨节点通信。
其中Z值的转化过程与第2章一致。如图3.2所示，对于Z阶填充曲线而言，实际空间中位于左下点的Z值必然比位于右上点的Z值小。因此只需要确定k近邻点的最远距离，然后对于求出位于右上的最大边界点和位于左下的最小边界点，之后确定他们的Z值索引，就能得到k近邻点的Z值索引范围。而对于如何实现求出k近邻的最远距离，可以采用扩大范围的方式。具体的做法如下：首先对于Z值已经排好已经的数据集上，找到所要求的p点的索引，然后分别向前向后搜索k个距离，选择最小的距离作为近似半径，此时的半径必然大于等于k近邻点，因此可以由此确定下边界点和上边界点的坐标，并确定出Z值范围。
采取相同的方法获取原分片的数据点的Z值索引的范围，然后通过复制的方式实现不同节点数据点的转移，保证每一个节点所需要的数据都在本节点之中。保证并行计算的顺利进行。
- 3基于Z值索引的k近邻优化算法Zoom
Zoom算法的核心思想是通过Z阶填充曲线将二维的数据点映射到一维的坐标轴中同时保持相对的空间位置的相对集中，进而只需要通过在部分数据点中搜索源点的k近邻点。
3.3.1 基本原理
如下图3.3所示，易知处于点右上方的点（）的Z值必然大于，处于点左下方的点（）的Z值必然小于，但反之并不一定。因此在Z值大于且位于点右上方的点选取前k项（ & ），计算到点的距离,同时在Z值小于且位于点左下方的点选取前k项（ & ），计算到 点的距离,将这些距离排序选取第k大的距离作为近似半径(Approximate Distance Radius)，并找到Z值下边界点对应的坐标：,将这个坐标点转换为Z值得到，同理获取Z值上边界点对应的坐标：,对应的Z值 。因为近似半径必然大等于k近邻点的距离 ，因此 的k近邻点对应的Z值必然处于之间，由此缩小了k近邻点的计算范围，使得算法的时间复度从 降为了级别。同时保存中间过程中欧式距离的计算结果，减少浮点数的平方与开方计算，以空间换时间来提升算法的效率。
3.3.2 算法描述
具体的做法如图3.4所示。首先在源点所对应的Z值索引附近2k范围之内搜寻近似距离半径,通过和的坐标计算出Z值下边界点和上边界点，在Z值处于和之间的点中搜寻k近邻点，并在搜寻近似半径过程中计算到个点的距离和最终确定的k近邻点的关系储存下来，在下一次的计算中直接使用已经计算过的距离而不用再次进行计算。具体的计算公式如下所示。
以上公式中的，代表的X轴坐标与Y轴坐标，，代表下边界点的X轴坐标与Y轴坐标，，代表上边界点的的X轴坐标与Y轴坐标。
具体的伪代码描述如表3.2所示。首先初始化k近邻索引，计算出近似半径，在近似半径的基础上计算k近邻点的Z值范围，在相应的范围内搜索k近邻点。在计算距离的过程中首先访问k近邻点中，储存距离索引等信息，避免重复计算。
表3.2 Zoom算法的伪代码描述
3.4 基于k近邻可达距离的优化算法RDK
在CDC算法计算可达距离的过程中，对于求内部点的可达距离的定义为与距离最近的边界点之间的欧式距离，计算内部点的可达距离需要遍历整个的边界点B计算每个点与的距离，将其中最小距离作为可达距离，求边界点的可达距离也是如此。设内部点的数量为,边界点的数量为,那么求整个数据集的可达距离的时间复杂度即为，又因为，由基本不等式可知，FCDC算法在计算可达距离时采用RDK(Reachable Distance of KNN）算法，将时间复杂度从降为了。
3.4.1 基本原理
实际上因为所有的点和自己的k近邻点形成了一个有关的局部的分布情况，构成可达距离的点只可能在这个k近邻的集合中或者在这个k近邻的集合之外。还是以求内部点的可达距离为例，设其k近邻点的集合为K,那么若存在且,那么的可达点必然在U中，若K中不存在边界点，则说明这些点都在所在的聚簇中，直接与距离最远的点视为可达距离即可，就能保证K中的点都能划为同一个聚簇，对于这种中不存在边界点的情况，实际上就是深处于聚簇内部的情况，可以通过内部点之间构成的k近邻点集合之间的传递性使得，所有的内部点划分为同一聚簇。
如图3.5所示，对于边界点而言，它本身所处于的位置就是聚类的边缘，在边界点和内部点之间的划分比例比较理想的情况下，边界点应该处于整个图像外围的薄层，边界点的k近邻中大概率存在着内部点，而比例划分失衡的情况下，边界点的周围也可能不存在内部点。在第一种含有内部点的清下，直接寻找距离最近的内部点，将该点的索引j记为可达索引（Reachable Index），在之后的指派边界点的过程中直接将该点划入其可达索引所在的聚簇之中。若是边界点的周围也不存在内部点，那么将最远的边界点的索引记为这个点的可达索引。在指派边界点的过程中，将指派到其可达索引所在的聚簇之中。后面聚类过程中采用的并查集的思想，两个类可以直接通过这个索引建立连接关系。
3.4.2 算法描述
如下图3.6所示，根据内部点和外部点所处的实际情况，求所对应的可达距离/索引。若内部点的k近邻中有边界点，则与最近边界点的距离就是该点的可达距离，若没有边界点则与最远的内部点之间的距离就是可达距离。若边界点的k近邻中有内部点点，则与最近内部点的索引就是可达索引，若没有边界点则与最远的边界点的索引就是可达索引。
具体的伪代码描述如表3.3所示，首先计算内部点的可达距离，计算过程是计算好所有的k近邻距离，若该内部点的k近邻中存在着边界点，那么选取与边界点的最近距离作为可达距离，否则选择与最远的内部点的距离作为可达距离。之后计算边界点的可达距离，若该边界点的k近邻点中存在内部点，则选择距离最近的内部点的索引作为可达索引。否则选距离最远的点作为可达索引。
表3.3 RDK算法的伪代码描述
3.5 基于并查集的聚簇优化算法CU
为避免该步骤的聚类过程与整个算法的聚类过程混淆，该步骤的聚类统称为聚簇，含义为将一类的数据点划分到一个簇中。
CDC算法具体的聚簇流程：首先初始化数组，每个点的初始编号为0，之后的聚簇过程分为两步：第一步，对于内部点的聚类，选择一个点,然后另外从内部点中选取一个点，计算两点之间的距离，若，则说明，属于同一聚簇，应该设置为相同的编号，但是需要分为两种情况，一种情况是没有被划分到任何的聚类，此时只需要修改值为即完成了划分，属于将点划分到一个集合中，另外一种情况就是已经被划分到了另外一个聚簇中，此时就需要将编号相同的点的编号都修改为，属于两个集合的合并。第二步就是对于边界点的聚类，将该点编号设为其可达索引对应点的聚类编号。
开始只是使用较小的数据集，程序的响应时间和运行状况都比较正常，而后面在进行较大的数据集（大约26万样本时）的内部点聚簇时，遇到了第一次的内存溢出和多次的程序运行时间异常。在经过再三的确认后发现是当时采取的简单暴力算法的实现，使得整个的程序的时间复杂度趋于，随着数据集的增大，运行时间陡然剧增导致了程序的长时间无法响应。
内部点聚类的主要问题出现在同一聚簇的合并上，特别是两个集合的合并，由于不确定同一聚簇的索引所在，最开始的做法是通过暴力遍历内部点的方式搜索具有相同聚簇编号的数据点，因为相同聚簇编号的数据点可能分布在数据集的任何位置，每次合并都需要遍历一遍，而需要合并的情况非常常见，导致时间复杂度到达了。最初的优化想法是通过空间来换取时间，将具有相同聚类编号的索引放在一个集合中，Set利用封装好的函数,来实现集合的合并。并及时清除中间产生的中间变量，来保证内存不会发生溢出。方法的底层逻辑都是通过迭代指定集合，并将每个元素逐个添加到目标集合中。在Java中，Set接口的方法用于将指定集合中的所有元素添加到调用该方法的集合中，具体的存储和插入逻辑则依赖于具体的Set实现类，无论是还是的底层逻辑都是通过迭代指定集合，并将每个元素逐个添加到目标集合中，而反复的申请和清除临时的Set集合同样也是导致操作系统频繁进行内存分配，特别是在JVM虚拟机中，内存清除机制是程序员无法决定的。
进一步的优化过程中，采用了处理不相交集合的合并及查询问题的并查集，并查集的核心思想是使用一个数组来记录每个元素的父节点，通过路径压缩和按秩合并来优化这两种操作的效率，使得每个操作的平均时间复杂度接近常数时间，其中α是反阿克曼函数，增长极其缓慢，在实际应用中可以认为是常数。使得上述合并聚簇的过程由降为了。
3.5.1 基本原理
如图3.7所示，CU聚簇算法通过并查集中的父节点数组构造出不交集森林，其中每一棵树代表一个聚簇集合。例如0号节点的父节点数组对应的值parent[0]为0，即0号节点，因此号节点单独作为一个聚簇。同理，1,2,3,4,5号节点构成一个聚簇，6,7,8构成一个聚簇。寻找该点的聚簇，只需寻找对应树的根节点即可，实际上就是按照父节点的索引，找到第一个父节点数组的索引为自身值的节点，而对于上文提到的合并的问题，只需要将的父节点设置为i的根节点，即可完成两个聚簇的合并。
3.5.2 算法描述
聚簇过程如图3.8所示，首先构造UnionFind类的对象，将父节点坐标设置为自己（每个点自己构成一个聚簇）。之后先对内部点进行聚簇，遍历内部点判断判断两个点是否满足内部连接关系，如果是则需要合并聚簇，合并聚簇无需以第一种方式遍历数据节点，也不需要在创建临时的集合，只需要修改根节点的父节点索引即可完成聚簇的合并。然后边界点通过自身的可达索引，加入到已经分好的聚簇之中。
具体伪代码描述如表3.4所示。定义并查集内部类，用于查找根节点的find()方法和用于将聚簇合并的Union（）方法，初始化聚簇数组，此时数组的每个点作为一个单独的类，先进行内部点的合并，对于满足连接条件的点使用并查集合并，具体的做法是将其中一个点的根节点设为另外一个点根节点的父节点，使得逻辑上的两棵树合并为一棵树。
表3.4 CU算法的伪代码描述
表3.4 CU算法的伪代码描述（续）
3.6 本章小结
本章主要介绍了FCDC聚类算法对于CDC聚类算法的具体优化的设计，首先实现了数据分片处理，将每一个数据切片放到不同的节点下并行运行，之后利用计算k近邻点的Zoom算法，将求k近邻点的时间复杂度从降为了级别；在k近邻点中计算可达距离/索引的RDK算法，将时间复杂度降为了级别，利用并查集完成的CU聚类算法，将时间复杂度从降为了级别。有效提升了FCDC算法的整体性能。
4 FCDC算法的实现
在本章FCDC算法的实现中主要介绍Spark并行环境下的数据集的划分，在各个节点上Zoom算法，RDK算法的实现，之后将数据结果收集到Driver程序上，完成基于并查集的CU聚类算法实现。
4.1 数据分片的实现
对于实际的操作而言，首先在主类Spark_FCDC中设置SparkConf类设置Spark的相关内部的配置和管理 Spark 应用程序的各种参数和设置。之后使用getDataPoint（）函数，读取数据集根据每一个数据点创建DataPoint类的对象，每一个DataPoint类对象包含了数据点的坐标，编号，标签和对应的Z值索引等信息。然后将这个对象数组封装弹性分布式数据集dataRDD。之后首先对dataRDD的Z值索引进行排序得到sortedDataRDD，之后通过repartition()函数进行预划分，之后通过近似半径的确定出预划分的分片实际的划分范围，将重叠的点以通信的方式传递到对应的节点上，保证在后续查找k近邻时所需要的数据都已经划分到了相对应的节点而不需要再进行跨节点通信。
核心代码描述如表4.1所示，包括1个主要数据结构和4个重要函数。
（1）DataPoint类用于实现数据点的封装，各类属性值来描述一个数据点的具体信息，重写的toString()方法来方便实现这个类的序列化和反序列化。
（2）getDataPoint（）实现通过主程序中设置好的Spark环境和文件路径，重文件中获得序列化的信息，然后利用构造函数反序列生成对应的对象。并将对象储存在分布式弹性数据集RDD上，这一步实际上实现的是预划分，即仍有数据集需要进行调整。
（3）PointToZValue（）函数实现的是对于坐标值到Z值索引的转化，首先需要对于浮点型坐标转为整型，然后经整数坐标通过偏移二进制编码的形式表示出来。然后通过比特洗牌技术，交换二进制数位上的值得到Z值索引，此时分布式的节点当中已经储存了一定数量的数据点及相关信息。
（4）dataRDD.sortBy（）操作实现对于所有的数据点来实现针对Z值索引的排序，之后通过repartition()再次进行一次划分，使得每个节点重新获取Z值索引处于一定范围内的数据点。
（5）DataPartitioning()该函数主要实现的是对于各个节点下一步运算所需要的数据点的补充，具体的做法是，计算每个点k近邻点的近似半径从而实现Z值范围的查询，然后实现对于该节点所需要的数据点范围的汇总，确定该节点所需要的范围进而实现将所需要的数据点复制并传入到相关的节点之中，方便相关节点进行并行运算时，不需要与其他节点进行通信处理。
表4.1 数据划分的核心代码
4.2 Zoom算法的实现
在数据分片的基础上，每个节点已经获得后续计算所需要的数据点，因此可以并行展开计算。Zoom算法的核心思想是通过Z阶填充曲线将二维的数据点映射到一维的坐标轴中同时保持相对的空间位置的相对集中，进而只需要通过在部分数据点中搜索源点的k近邻点。
具体的运算逻辑是首先针对每个点求出近似半径之后，然后根据近似半径来实现计算k近邻点的Z值索引上边界点和Z值索引下边界点的坐标并计算Z值的取值范围。然后在这个范围内利用distance()函数计算源点与每个点的距离，排序之后选择距离最小的k个点作为k近邻点。
核心代码如表5.2所示，主要包括1个数据集和4个重要函数。
表4.2 Zoom算法的实现
（1）knnPairRDD保存着所有节点k近邻点的信息（源点的信息，对应k近邻点的信息）的分布式数据集，该数据集是Zoom算法的最终输出，也是下一步计算可达距离RDK算法的输入。
（2）calculateKNNPairRDD（）在每个节点计算k近邻点的主函数。其主要执行过程是针对每一个点提取出计算k近邻相关的数据（坐标，Z值），利用这些信息作为输入，执行calculateKNNIndexes（）函数计算每个点的k近邻点
（3）使用mapToPair（）操作将sortedDataRDDWithIndex转换为knnPairRDD的转换，具体的实现操作是将每个元素转换为一个键值对，构建DataPointWithIndex对象，获取相关信息，然后将计算好的k近邻信息也以DataPointWithIndex对象的形式封装到knnPairRDD中。
（4）calculateKNNIndexes（）是针对每个点具体求k近邻点的函数。首先近邻点的取值半径，然后计算k近邻点的边界点，Z值索引的边界值，在对应的范围内并行计算k近邻点。
（5）distance()实现具体两个数据点之间欧式距离的实现,计算每个维度坐标之差的平方和之后进行开方操作获取距离。
4.3 RDK算法的实现
在通过Zoom算法得到了每个点的k近邻之后，继续通过k近邻点获取每个点的局部方向中心性度量，然后对DCM值进行排序并通过程序输入的比例来获得划分内部点和边界点的DCM阈值，然后根据每个点的具体DCM值划分内部点和边界点。对于每个点计算可达距离。RDK算法的核心思想就是针对于k近邻点计算可达距离，对于内部点而言，分为两种情况，一种是k近邻点中存在边界点，另外一种是k近邻点中不存在边界点，对于存在边界点的情况直接使用与最近边界点的距离作为可达距离，否则选取距离最远的内部点之间的距离作为可达距离。同时对于边界点也是若k近邻点中存在内部点，则选择最近的内部点最为可达索引，否则则选择最远的边界点作为可达索引。
具体的代码逻辑是根据knnPairRDD在分布式环境下计算每个点的DCM值将DCM值和数据点信息封装起来生成分布式数据集dcmRDD，然后对DCM值进行排序，并按照比率划分为边界点和内部点，得到TypeRDD。然后通过针对同一个数据点（根据Z值索引）的合并获得combinedRDD，其中已经包含了计算可达距离的所有信息，可以在对应的节点上并行计算可达距离了，将所需要的参数计算可达距离的函数中，计算每个点的可达距离，将最后的结果封装到reachableDistancesRDD这个分布式数据集中。核心代码如表4.3所示，包括3个重要的分布式数据集和4个重要的函数
（1）dcmRDD表示的是封装数据点和对应得DCM值的分布式数据集，它是通过之前的knnknnPairRDD计算得来的，并且是转换为TypeRDD的基础，即通过具体数据点的DCM值来划分内部点和边界点。
（2）TypeRDD表示的是封装数据点信息和对应的类型的分布式数据集，它是通过之前的dcmRDD计算得来的，并且是转换为reachableDistancesRDD的基础，即通过具体数据点的类型和k近邻计算可达距离。
（3）reachableDistancesRDD表示的是封装数据点信息和对应的可达距离的分布式数据集，它是通过之前的knnPairRDD和TypeRDD联合计算得来的，作为RDK算法的输出，并作为CU聚类算法的输入。
（4） calculateDcmRDD（）函数的作用是计算具体数据点的DCM值，实际上就是通过计算源点与k近邻点形成的近邻角的方差，这个方差表示的就是该点k近邻点的分布情况，该值越小说明该点的k近邻分布越均匀，该点就越有可能是中心点，同时若该点的DCM值越小说明该点越有可能是边界点。
（5）getTypeRDD（）通过程序输入的比例和数据集中每个点的DCM值来确定内部点和边界点划分的DCM阈值，若该点的DCM值小于阈值，则划为内部点，若该点的DCM值大于阈值则划为边界点。
（6）updatedCombinedRDD（）该函数的意义是更新前面分布式数据集中每个数据点的类型，包括每个节点对应k近邻点的类型，方便下一步计算可达距离。
（7）calReachableDistancesRDD（）该函数表示的是实际计算可达距离的逻辑，在不同的节点实现可达距离的并行计算，对于内部点而言，选择与最近的边界点的距离或者是最远的内部点距离做为可达距离，对于边界点选择距离最近的内部点或者距离最远的边界作为可达距离。
表4.3 RDK算法的核心代码
4.4 CU算法的实现
在完成可达距离的计算之后，就要针对于内部点和边界点进行聚类了。首先对每个节点中的信息进行收集到Driver程序中，然后在Driver程序上处理聚类过程。具体的聚类过程是，首先接受每个节点上计算的各类信息，包括每个点的信息和所对应的可达距离和数据点类型。按照可达距离的关系，若是两个内部点之间的距离小于等于两个点的可达距离，则说明这两个点属于同一聚簇，需要执行合并操作，CU算法的核心思想在于使用并查集完成聚簇划分，只需要查找到聚簇的根节点，然后修改根节点的父节点值，实现两个棵聚簇树的合并。
核心代码如表4.4所示，主要包括1个并查集内部类的实现和3个聚类步骤。
（1）并查集是通过父节点数组来实现构建聚簇树，每个节点的对应的父节点值表示的是该节点及其子节点都属于父节点这个聚簇，父节点数组值等于其本身节点值就是该聚簇树的根节点。在初始化父节点数组时，为每一个节点赋值该节点索引，构建出每棵聚簇树只含有本身节点的数组。然后实现两个操作，一个是find（）操作用于查找该聚簇上的根节点，一个是union（），实现两个节点的合并，即用1个节点的父节点值赋值给另一个节点父节点值。对于两个集合的合并，只需要将其中一个聚簇的根节点作为另一个聚簇的根节点的父节点值就可以完成聚簇树的合并。
（2）内部点的聚类连接过程，就是搜索整个内部点，对于两个内部点满足聚类连接条件并且两个点不处于同一聚簇树的情况，需要修改其中一个聚簇的根节点对应的父节点值，完成两个聚簇树的合并。
（3）根据内部点聚类的结果，更新聚簇数组的聚簇编号，就是将每个聚簇树的根节点编号做为聚簇编号，然后将这个编号更新到聚簇数组中。
（4）接下来就是边界点的指派过程，对于边界点而言只需要将其指派到最近的聚簇中即可完成边界点的指派，在之前计算可达距离的过程中，已经储存了距离边界点最近的内部点索引，此时只需要将聚类数组中的边界点的聚类编号设置为可达索引所属于聚簇的聚类编号就完成了内部点的指派过程。
（5）calculateDistance（）函数实现了内部点之间欧式距离的计算。即在m维空间中两个点之间的真实距离。
表4.4 CU聚类算法的核心代码
表4.4 CU聚类算法的核心代码（续）
4.5 本章小结
本章主要介绍FCDC算法的编码实现。主要介绍基于Spark并行环境下的数据集的划分的实现，在各个节点上使用Zoom算法计算k近邻点的实现，使用RDK算法计算可达距离的实现，基于并查集的CU聚类算法实现。通过代码逻辑和核心代码展示这4个部分的具体实现细节。
5 实验与性能分析
本章所设计的实验主要集中在测试4个方面（1）测试Zoom算法对于k近邻的计算，（2）RDK算法对于可达距离计算，（3）CU算法对于聚类过程的性能提升；（4）FCDC算法在Spark架构下的Local模式的运行情况。实验做的测试均使用如下的软硬件环境见表5.1。
表5.1 测试使用的软硬件环境
首先设计实验对于FCDC算法的稳定性和准确性进行验证，为方便成快速获取实验结果和进行参数吊证，使用的是数据量较小的合成数据集DS1-DS6，数据集信息如表5.2所示。真实标签与聚类结果的散点图如图5.1所示，具体的实验参数指标如表5.3所示。
表5.2 合成数据集DS的相关信息
图5.1 DS1-6数据集的真实标签与聚类结果
其中第一行的图片是数据集真实标签的散点图，第二行图片是聚类结果的散点图。
表5.3 数据集DS1-6的实验结果
其中k值，Ratio值是FCDC算法的中的重要参数，k值表示近邻点集的数量，Ratio值表示内部点占所有数据点的比例。ACC表示聚类结果的准确率，范围[0,1]，值越大表示聚类算法的性能越好；ARI为调整兰德指数，范围[-1,1]，值越高表示两个聚类结果越相似，值为0表示结果与随机聚类的相似性相当；NMI，范围[0,1]，值越大表示两个分布越相似，1表示完全一致，0表示独立无关。
5.1 Zoom算法的性能分析
设计实验证明Zoom算法对于FCDC算法的性能提升。通过在相同数据集下的全局搜索算法与Zoom算法的运行时间和欧式距离的计算次数的对比，体现二者性能差异。
表5.4 真实数据集相关信息
具体的数据集信息如表5.4所示。该表中数据集均属于真实数据集，具有实际含义且维度大于2且经过降维处理，所有的数据集都是关于细胞基因表达的数据集
相关实验数据表明，Zoom算法有效的减少了重复的欧式距离运算次数，但是由于Zoom算法的多了对于计算Z值，排序等过程中，会有额外的性能消耗，在数据集样本数比较小的情况下性能可能会差于全局搜索算法，在数据样本达到7551时，Zoom算法性能全面超越了全局搜索算法。并且随着样本数量的增多，优化程度逐渐提升。
其中横坐标代表的是具体数据集，纵坐标表示程序运行时间/ms，可以看到到随着数据量的增加，全局遍历算法逐渐拉大与Zoom算法所用的时间的差值，性能优化逐渐提升。而性能表现最好的Levine数据集表现如上图所示，性能提升到了489%
Zoom算法的对于计算量的提升效果如图5.3所示。其中横坐标代表的是具体数据集，纵坐标表示欧式距离计算次数对2取对数的数值。同样随着数据量的增加，全局遍历算法欧式距离计算次数与Zoom算法的差值逐渐拉大的差值逐渐拉大，性能优化逐渐提升。表现最好的数据集，Zoom算法的计算量仅为全局搜索算法的。
原始实验数据如表5.3所示，其中k值，Ratio值是FCDC算法的中的重要参数，k值表示近邻点集的数量，Ratio值表示内部点占所有数据点的比例。其中黑体的指标是优胜指标。
表5.3 Zoom优化算法实验结果
5.2 RDK算法的性能分析
设计实验证RDK算法对于FCDC算法的性能提升。通过在相同数据集下的全局搜索算法与RDK算法的运行时间和欧式距离的计算次数的对比，体现二者的性能差异。与Zoom需要有额外的计算开销不同，RDK算法通过直接缩小范围实现对于可达距离/索引的计算范围，因此在较小的数据集上依然能够有比较好的表现。同样RDK算法对于性能的提升会随着数据量的增加而增加。
其中横坐标代表的是具体数据集，纵坐标表示程序运行时间/ms。可以看到观察到随着数据量的增加，全局遍历算法RDK算法所用的时间的差值逐渐拉大与，性能优化逐渐提升。表现最好的数据集Levine数据集，性能提升到了1633%。
其中横坐标代表的是具体数据集，纵坐标表示欧式距离计算次数对2取对数的数值。同样随着数据量的增加，全局遍历算法与RDK算法欧式距离计算次数的差值逐渐拉大，性能优化逐渐提升。在样本数据量为264155的Levine数据集上，欧式距离的计算次数仅仅为原来的。
原始实验数据如表5.4所示，其中k值，Ratio值是FCDC算法的中的重要参数，k值表示近邻点集的数量，Ratio值表示内部点占所有数据点的比例。其中黑体的指标是优胜指标。
表5.4 RDK优化算法实验结果
5.3 CU算法的性能分析
设计实验证CU算法对于FCDC算法的性能提升。通过在相同数据集下的全局搜索算法与CU算法的运行时间和平均连接时间的对比，体现二者的性能差异。CU算法通过并查集数据结构能高效完成不相交集合的构建，在较小的数据集同样有效。同样RDK算法对于性能的提升会随着数据量的增加而增加。在样本数据量达到在数据集达到264155时，全局搜索聚类算法的运行时间已经超过了响应时间（达到了45分钟以上），而CU算法仅仅使用了3分34秒。具体实验结果如图5.6所示。
其中，横坐标表示的是数据集，竖坐标表示的是聚类过程的程序运行时间，由图5.7可知，随着数据量的增加，CU算法的性能逐步提升，尤其是平均的合并操作对比，如下图所示，最高加速比达到了117倍。
原始实验数据如表5.5所示，其中k值，Ratio值是FCDC算法的中的重要参数，k值表示近邻点集的数量，Ratio值表示内部点占所有数据点的比例。其中黑体的指标是优胜指标。
表5.5 CU优化算法实验结果
5.4 Spark环境的性能分析
设计实验FCDC算法在Spark分布式计算框架的性能表现。通过相同数据集在Local模式不同并行度下程序的运行时间时间，探究Spark架构的影响因。实验结果如图5.8所示。对于当前的所有数据集，在并行度由1提升到3时的效能明显提升，但当并行度提升为5时，效率的提升并不十分明显，在通过查找资料，实验测试得知，Spark架构的自动优化会根据程序的数据量，能调动的资源进行自行的分区，调度，任务优化。而直接显示修改相关参数的效果可能会适得其反。需要进一步的研究。
其中横坐标代表的是数据集，纵坐标代表的是程序运行时间，而对于Spark会在程序运行时进行自动调优工作，会对并行度的设置有一定干扰，本实验对于并行度的设置为设置 弹性分布式数据集默认分区数量，每个执行器可以使用的CPU核心数以及指定进行并行处理的线程数量。
值得一提的是，Spark同时会使用有向无环图DAG进行计算过程的优化，对于某些结果惰性执行，保留其运算逻辑，只有当action操作时才会实际执行计算过程。具体来说将RDD的转换操作分解成窄依赖和宽依赖。窄依赖可以在同一个节点上完成，而宽依赖需要在不同节点之间进行shuffle操作。DAG Scheduler基于宽依赖的边界将作业划分为多个阶段，每个阶段包含多个并行的任务。在每个阶段内，DAG Scheduler将任务分配给Task Scheduler。Task Scheduler负责在集群节点之间分配和执行这些任务。
原始数据数据如表5.6所示。
表5.6 Spark环境下的实验结果
5.5 本章小结
本章主要针对FCDC算法的性能，设计相关实验进行测试测。首先在合成数据集DS对FCDC算法的准确性和稳定性进行测试，测试指标为ACC，ARI，NMI。之后在真实数据集上测试三种优化算法的性能提升。Zoom算法有效提升了k近邻点的计算效率，相较于全局搜索算法的优化，在表现最好的数据集上Zoom算法实现了距离的计算次数为原来的，性能提升到了489%，RDK实现了对于可达距离计算的性能提升，在距离的计算次数为原来的，性能提升到了1633%；CU算法实现了对于聚类过程的性能提升, 在最大的数据集上仅使用了3分34秒完成了原来算法45分钟都未曾实现的聚类过程。在Spark运算框架下，FCDC算法通过提高并行度，使得运算性能最高实现了170%的提升。
6 总结与展望
针对于CDC算法在处理大规模数据集时仍然存在的挑战，本文在基于方向中心性的CDC聚类算法的基础上在CDC提出了一种快速局部方向中心性聚类算法—FCDC。
6.1 内容总结
FCDC算法主要通过基于方向中心性的聚类思想解决传统聚类算法中出现的异构密度问题，弱连接问题的问题。核心思想在于DCM是用来度量数据点k近邻空间分布中心性。表示中心点的k近邻分布均匀程度，其数学表达式表示为近邻角的平方差，值越大说明每个角之间的差距越大，近邻点分布的越集中，越有可能是边界点，值越小说明，近邻点分布的越均匀，越有可能是内部点。通过具体的参数调整确定DCM的阈值，将数据点分为内部点和外部点。通过外部点连接划分出来的边界线分割整个数据集完成聚簇。内部点通过彼此之间的距离与距离自己最近的与可达距离之间的关系完成聚簇，然后将边界点指派到已经划分好的聚簇中。
具体的优化过程分为4个部分。（1）通过Zoom算法提升求k近邻点的计算效率。其核心思想在于利用Z阶填充曲线，将二维坐标生成Z值作为Z轴上的索引，保证在二维空间上相近的点在Z轴上依然保持着比较近的距离，之后通过近似k近邻半径缩小整个的搜索范围，并在求k近邻的过程中，大多数点的k近邻关系是相互的，记录下每个点的k近邻点距离，避免重复进行浮点数的平方和开方运算。（2）通过RDK算法提升计算可达距离的效率。其核心思想是避免在全局范围内寻找每个点的可达距离和可达索引，而只是在在k近邻点中搜索即可。（3）使用基于并查集完成的CU聚簇算法，提升聚簇过程的效率。其核心思想在于利用使用并查集构造不相交森林，完成聚簇（4）基于Spark并行运算框架提升算法运行效率，其核心思想在于构建弹性分布式数据集RDD，采用并行运算的方式提高程序的运行效率。
实验数据表明在表现最好的数据集上Zoom算法实现了距离的计算次数为原来的，性能提升到了489%；RDK实现了对于可达距离计算的性能提升，在距离的计算次数为原来的，性能提升到了1633%；CU算法实现了对于聚类过程的性能提升, 在最大的数据集上仅使用了3分34秒完成了原来算法45分钟都未曾实现的聚类过程。在Spark运算框架下，FCDC算法的运算性能最高实现了170%的提升。
6.2 未来展望
对于FCDC算法的有两个方面的展望。一是提高聚类算法的准确性，二是继续提升FCDC算法的效率。
对于提高准确性，首先FCDC算法对于高维数据的的处理还有待补充。在下一步的研究中可以通过合适的数据降维操或通过DCM度量在高维数据中的定义来实现，从而提高在高维数据集上的准确性。然后，对于具体的内部点和边界点的比例计算还有待补充，可以通过不规则三角网（TIN）划分算法并过滤跨域三角形，确定阈值，进一步提高聚类算法的准确度。另外，由于DCM是密度无关的度量，而实际情况中，密度对于识别内部点和边界点依然具有很重要的影响，可以考虑增加相应的k近邻密度指标，来提升内部点和边界点的识别精度。
对于提高运算效率，主要是针对Spark分布式环境而言。本文所实现基于Spark分布式算法在并行处理完数据后依然需要将处理之后的数据收集到驱动程序，再将数据集作为全局变量提供给不同的节点来实现后序的处理，在面对较大的数据集时候，可能会出现内存溢出的情况。为了解决这个问题，可以通过局部抽样的方式用局部数据点的聚类分布情况，来合成出整体的聚类分布情况，比如通过确定聚类中心，聚簇半径将重合度较高的聚簇合并，从而实现整体的聚类。这样做的好处在于能够实现计算完全在一个节点之内，不需要节点之间的数据交互，个节点处理一部分的数据，绘制出聚类结果，然后交给驱动程序单独做合并提升效率。之后集群的配置性能和具体调优算法也是两个重要的影响因素，值得进一步的探索。
参考文献
Gorunescu F. Data Mining Concept Model and Techniques[M]. Springer Science & Business Media, 2011.
梁吉业,高文.数据挖掘中的聚类方法[J].计算机科学, 2000, 27(4): 42-45.
陈小燕. 机器学习算法在数据挖掘中的应用[J]. 现代电子技术, 2015, 38(20): 11-14.
夏金凤, 田文耕. 大数据时代人工智能在计算机网络技术中的应用研究[J]. 电子通信与计算机科学, 2024, 6(2): 99-101.
Krishna K, Murty M N. Genetic K-means algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1999, 29(3): 433-439.
Schubert E, Sander J, Ester M, et al. DBSCAN revisited, revisited: why and how you should (still) use DBSCAN[J]. ACM Transactions on Database Systems (TODS), 2017, 42(3): 1-21.
Peng D, Gui Z, Wang D, et al. Clustering by measuring local direction centrality for data with heterogeneous density and weak connectivity[J]. Nature communications, 2022, 13(1): 5455.
Li Z, Hu J, Stojmenovic M, et al. Revisiting Spectral Clustering for Near-convex Decomposition of 2d Shape[J]. Pattern Recognition, 2020, 105(107371).
陈黎飞, 姜青山, 王声瑞. 基于层次划分的最佳聚类数确定方法[J]. 软件学报, 2008, 19(1): 62-72.杨杰,王国胤,庞紫玲.目睹等职聚类相关问题的研究[J].南京大学学报：自然科学版, 2017, 53(4): 791-801.
甄彤. 基于层次与划分方法的聚类算法研究[J]. 计算机工程与应用, 2006, 42(8): 178-180.
Deng Z, Hu Y, Zhu M, et al. A scalable and fast OPTICS for clustering trajectory big data[J]. Cluster Computing, 2015, 18: 549-562.
Chunhao Z , Bin X , Yiran Z .Reverse-Nearest-Neighbor-Based Clustering by Fast Search and Find of Density Peaks[J].Chinese Journal of Electronics,2023, 32(6):1341-1354.
Lu J, Zhao Y, Tan K L, et al. Distributed density peaks clustering revisited[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 34(8): 3714-3726.
董晓君,程春玲.基于核密度估计的K-CFSFDP聚类算法[J].计算机科学, 2018,45(11):5.
Xie H, Li P. A Density-based Evolutionary Clustering Algorithm for Intelligent Development[J]. Engineering Applications of Artificial Intelligence, 2021, 104(104396).
Xuan G, Zhang W, Chai P. EM algorithms of Gaussian mixture model and hidden Markov model[C]//Proceedings 2001 international conference on image processing (Cat. No. 01CH37205). IEEE, 2001, 1: 145-148.
岳佳, 王士同. 高斯混合模型聚类中 EM 算法及初始化的研究[J]. 微计算机信息, 2006 (11X): 244-246.
田启明, 王丽珍, 尹群. 基于网格距离的聚类算法的设计, 实现和应用[J]. 计算机应用, 2005, 25(2): 294-296.
Gui Z , Peng D , Wu H ,et al.MSGC: Multi-scale grid clustering by fusing analytical granularity and visual cognition for detecting hierarchical spatial patterns[J].Future Generation Computer Systems, 2020, 112:1038-1056.
Wu Q, Hao J K. A review on algorithms for maximum clique problems[J]. European Journal of Operational Research, 2015, 242(3): 693-709.
Du Z, Wang Y, Ji Z. PK-means: A new algorithm for gene clustering[J]. Computational biology and chemistry, 2008, 32(4): 243-247.
Jiang H, Li J, Yi S, et al. A new hybrid method based on partitioning-based DBSCAN and ant clustering[J]. Expert Systems with Applications, 2011, 38(8): 9373-9381.