基于局部核心点的聚类算法与度量研究

摘要

数据挖掘是从大量的数据中发现新颖的、潜在的、有用的知识。聚类分析是数据挖掘的主要任务。其主要目标是将数据对象按照相似度划分成不同的簇，使得在相同簇中的数据对象彼此相似，而不同簇中的数据对象彼此不同。通过聚类分析，能够更容易发现数据集中隐含的特征。聚类分析被广泛地应用于模式识别、图像处理和人工智能、医学、基因科学、地质学、管理学等领域。近年来，随着信息技术的发展，数据规模越来越大，数据结构越来越复杂，给聚类分析的研究带来新的挑战。本文通过对聚类分析的基础理论和算法进行分析，针对复杂流形数据集的聚类问题进行了研究，主要的工作和取得的成果包括以下几个方面： （1）提出了基于自然邻居的局部核心点的概念。当需要对大量数据进行聚类的时候，传统的聚类算法需要大量的时间。为了解决该问题，考虑从数据集中选出代表点，然后将剩余的数据对象划分到其代表所属的簇中。基于自然邻居的局部核心点首先利用自然邻居自适应得到每个数据对象的局部邻域，即分布于密集区域的数据对象具有较多的邻居，而分布于稀疏区域的数据对象具有较少的邻居，然后选择局部邻域中具有最大密度的数据对象作为局部核心点。剩余的数据对象划分到其代表所属的簇中，使得原始数据集被划分成多个子簇，这为复杂流形数据集的聚类分析问题提供了方便。通过将局部核心点应用到DP算法、层次聚类算法和最小生成树聚类算法中，降低了算法的时间复杂度，并且也充分说明了使用局部核心点作为数据集代表点的有效性。 （2）提出了新的基于局部核心点的DP聚类算法DPLORE。为了更好地表示流形簇中数据对象之间的关系，研究者提出使用测地距离来度量数据对象之间的不相似度。由于先验知识的缺失，准确的测地距离无法得到，因此使用最短路径长度近似计算测地距离。但是计算所有数据对象之间的最短路径具有较高的时间复杂度。因此，考虑使用局部核心点代替原始数据集进行计算。DPLORE算法首先找到局部核心点，然后引入自适应距离度量局部核心点之间的距离，最后利用DP算法对局部核心进行聚类。由于引入自然邻和自适应距离，算法不需要设置参数且能够很好地发现复杂流形簇。实验表明该算法与已有的算法相比，DPLORE在发现复杂流形簇方面更具优势。 （3）提出了基于局部核心点的层次聚类算法HCLORE。当人们从复杂的结构中进行模式识别的时候，往往会先去识别位于密集区域的比较明显的结构，然后处理位于稀疏区域边界上的数据对象，从而排除噪声点的干扰。受此启发，提出了混合层次聚类算法HCLORE。HCLORE算法是融合了“自顶向下”和“自底向上”的两种策略。与其他混合的层次聚类算法不同的是，不需要通过不断地迭代直到满足某些终止条件，而是通过寻找局部核心点对数据集进行划分。然后，根据密度递增曲线确定密度阈值，排除低密度数据对象的影响，同时，使簇与簇之间的边界更加清晰。然后，重新定义簇与簇之间的相似度，用于将划分得到的子簇进行合并，并使算法能够适用于复杂的流形数据集。通过人工数据集和真实数据集上的实验，表明了HCLORE算法在对复杂流形聚类方面，与其他算法相比更具优势。 （4）提出了基于局部核心点的最小生成树聚类算法MSTLORE。现有的基于最小生成树的聚类算法，在原始数据集上构造最小生成树，不仅具有较高的时间复杂度，而且容易受到噪声点的影响。局部核心点在保留原始数据集的分布结构的同时，排除了噪声点，因此，将局部核心点与最小生成树聚类算法相结合，提出了MSTLORE算法。定义了一种新的基于局部核心点的共享近邻的距离，用于度量局部核心点之间的不相似度。MSTLORE算法根据基于共享近邻的距离，在局部核心点上而不是原始数据集上构造最小生成树进行聚类，从而减少了算法的运行时间，并在一定程度上排除了噪声点的干扰。重新定义局部核心点之间的距离使得算法能够发现复杂结构的簇。通过人工数据集和真实数据集上的实验表明，MSTLORE算法在识别复杂结构的簇方面与其他算法更具竞争性。 （5）提出了一种基于局部核心点的聚类度量指标LCCV。针对现有的内部度量指标无法评估复杂流形簇的问题，提出使用最短路径度量局部核心点之间的不相似度，然后评估每个局部核心点的紧凑度和分离度，从而确定其聚类质量，最后将每个局部核心点的平均聚类质量作为LCCV指标。由于使用最短路径度量局部核心点之间的不相似度，LCCV能够有效地评估复杂流形簇。将LCCV指标与基于局部核心点的层次聚类算法HCLORE算法相结合，去验证LCCV的有效性。通过实验表明，与其他的聚类度量相比，LCCV在度量复杂流形簇方面更具优势。

目录

第一个书签之前