基于最近共享邻居节点的K_means聚类算法

1、，（）计算机工程与应用基于最近共享邻居节点的聚类算法单世民，于红，张业嘉诚，刘馨月，大连理工大学软件学院，辽宁大连，：，（）：，：，（），（）（），：；摘要：聚类分析是一种重要的数据挖掘方法。聚类算法在数据挖掘领域具有非常重要的应用价值。针对需要人工设定聚类个数并且易陷入局部极优的缺陷，提出了一种基于最近共享邻近节点的聚类算法（）。在数据集中搜索中心点，依据中心点查找数据集个数，为聚类提供参数。从而克服了需要人工设定聚类个数的问题，同时具有较好的全局收敛性。实验证明算法比、粒子群（）以及多中心聚类算法（）有更好的聚类效果。关键词：聚类分析；最近共享邻居文章编号：（）文献标识码：中图分类号：的聚

2、类算法（）。基于最近共享邻居节点聚类算法（）是等提出的利用节点间最近共享邻居节点个数作为相似度标准的聚类算法。的优点是在数据空间中建立节点间的自然链接关系。但需要设定每个节点的搜索半径，影响了算法的执行效率。利用在空间中查找最近共享邻居节点的方法找出局部中心点。中心点的确定可以自动地在数据集中初步确定簇集合和簇的个数，为聚类提供参数。避免了参数选择不当而引起的聚类结果不准确的问题。与、以及等聚类算法的比较实验证明，无需用户设定聚类个数，并且避免了及其改进算法易陷入局部收敛的问题。因此对算法进行改进是十分有效的。第章介绍最近共享邻居节点算法。算法的基本思想及其实现细节将在第章进行说明。第章针对值

3、选取、执行效率以及全局收敛性方面进行对比实验。最后一章总结全文。引言聚类分析广泛地应用于文本搜索、模式识别、人工智能和常用聚类方法包括统计方法、机器学习方互联网搜索等领域。法、神经网络方法和面向数据库的方法。算法在聚类分析中具有非常重要的应用价值。但随着应用领域的拓展和首先，随机选取的新的问题需求，存在一定的局限性。初始值可能会导致不同的聚类结果，甚至会造成无解。其次，该算法是典型的爬山搜索方法，因此不可避免地陷入局部最优。周涓等利用最大最小距离法改进算法（），选取聚类种子，提高了聚类性能。利用算子来代为替遗传算子中的交叉算子，提出了一种混合遗传聚类算法。了提高遗传聚类算法的搜索效率，采用了聚

4、类中心的浮点编码方式，并设计了浮点数交叉和变异算法对遗传聚类算法进行改进。针对算法存在局部收敛和早熟的现象，刘靖明等提出了一种利用粒子群优化算法的聚类算法提高了的全局寻优能力，同时还具备局部寻（）。优能力。经典及其改进算法需要用户设定聚类个数。参数设定必然导致算法准确性降低，并且在局部范围内对算法的影响很大。爬山搜索方法易陷入局部最优解，必然降低了算法的准确性。因此提出了一种新的聚类算法基于最近共享邻近节点收稿日期：修回日期：最近共享邻居节点算法最近共享邻居节点聚类算法（）是利用节点间的最近共享邻居节点个数作为相似度。替代了传统的距离向量作为算法的相似度。由数据集中两点的最近共享邻居节点来决单

5、世民，于红，张业嘉诚，等：基于最近共享邻居节点的聚类算法，（）定。如果数据集中两点接近，并且它们都接近数据集，那么和的相似度由数据集中的节点个数来决定。最近共享邻居节点算法首先由提出。也采用了相似的方法进行计算。类提供参数。这样就避免了人工设定参数影响结果的准确性，而且能够达到很好的全局收敛能力。将剩余点归簇后，基本簇便形成。数学描述+利用相似矩阵建立了一个共享邻居节点（）图。当且仅当和在彼此的最近邻居表内，则在节点和间建立一条链接。和之间的关系表示如下：（）（）!（）（）!其中，（）和（）分别表示和的邻居节点。节点间关系的建立有利于划分数据集，这样可以对数据集进行中心点的选取。查找数据集中任

6、意两点间最近共享邻居节点的过程称为最近邻居节点检索。在图中，两点间的链接权值（相似度）通过求解两点间的最近共享邻居节点个数得到。设两点和，则和之间的相似度定义表示如下：（，）（）（）（）相似性（，）由和的最近共享邻居节点个数表示。再利用设定的阀值将数据集中小于阀值的节点间链接去除，那么具有链接关系的节点集就构成簇。此相似度的引入是用来判断数据集中节点间关系。比距离向量提供了更健壮的相似度计算方法。+（，）!（，；）!（，）.其中，。聚类要找到一个划分，。为个组成的基本簇。将原有的数学表达式分解为由多个基本簇构成的形式。其中为第个聚类的中心。此表达式充分描述了的离散度。（）的寻优能力由各类样本到

7、对应聚类中心的距离总和决定。通过实验对比较证明，具有更好的全局寻优能力。算法描述算法算法（）（，）（，$）；输入样本数据集，参数和$。获得初始化。数据集个数，数据集节点的最近共享领导节点值集合（）（，）（）；标注节点集，获得中心点集合，归属点集合和剩余点集合（）（，）（，）；实现过程利用最近共享邻居节点的思想对数据集分类，针对不同类型的数据集分别进行处理。这样可以避免数据节点的重复查询。再利用最近共最近享邻居节点建立的数据集间的关系引入聚类算法。的相关定义定义数据集中两点和之间的关联性满足：获得基本簇个数和簇集合（）（，）；进行聚类，获得基本簇集合（）（）；验证，获得真实聚类结果算法对进行了完

8、整描述。其中初始化部分（）要进行数据集预处理，并计算节点间的值。得到集合（），为之后进行的节点分类提供基础。图是数据集的分类过程示例。对数据集进行处理获得了图中（）和（）所示中心点与非中心点的数据集。应用算法作为相似度标准。首先，建立了数据集的最近邻居节点图（）。利用公式（）优化图形，查找到数据集中最近共享邻，%（，）$，关联（）（，）$，不关联其中，$为设定参数。，是查找中心点的依据。这样就可以建立数据集间的完整关系。定义为数据集中任意节点（&），（为数据集）。如果，且!，那么节点为中心点。其中，为与中心点链接的节点个数，!为设定参数。选择中心点的目的为确定基本簇提供基础，并将基本簇

9、个数作为算法的参数。定义为数据集中任意节点（&），（为数据集）。如果，且!，那么节点为归属点。利用最近共享邻近节点的目的是查找数据集中节点间的自然链接关系。将数据点归入到与其具有最大共享邻居节点个数的中心点所在的簇中。利用中心点和归属点确定簇的个数。定义为数据集中任意节点（&），（为数据集）。如果，且!，那么节点为剩余点。当，簇。数据集分类的目的在于确定基本簇的个数，为聚，（）计算机工程与应用为剩余点（的平均时间复杂度为），其中数量，为基本簇个数，为样本维数。所以算法时间复杂度为（）。只对数据集进行一次查找过程。因此算法的空间复杂度为（）。居节点图（）。再计算每个节点所链接边的

10、数量。设定阀值，边的数量不小于阀值的点为中心点、中心点就是与其它节点具有高度联系的数据点。此时将数据集划分为类，中心点，归属点和剩余点。利用中心点和归属点确定簇的个数，为提供参数。利用最终形成基本簇。基本簇的确定中引入算法来查找最近邻居节点。（）。基本簇的确定过程中核心部分的时间复杂度为是查找中心点。这一步利用对数据集进行一次查找，时间复杂度为（）。算法中簇的求解过程（）描述如下：实验分析可以解决聚类需要人工设定聚类个数的问题，使自动完成聚类。利用公共数据集和人工数据集对的聚类过程进行验证。与、和算法的比较证明具有很好收敛能力，且执行效率更高。其中将聚类个数分别给定和微粒群算法。微粒群算法的群

11、体规模和迭代数分别设定为和。将具有链接关系的中心点归并为同一个簇。在中，中心点由算法确定。中心点是在高密度区域中产生。所以中心点在局部数据区域的内部。若两个中心点具有链接关系，可以证明它们是在同一个数据区域。假设它们不在同一数据区域内，则证明它们在数据区域边缘。这与聚类算法的基本定义相违背。所以相邻中心点在同一数据区域内，属于同一个簇。中参数、%和!通过和的实验数据获得，分别设定为、和，。对实验数据集的分析如表。表数据集数据集分析维数聚类个数节点数量人工数据将归属点聚类到与其具有最多邻居节点个数的中心点。若归属点与多个中心点具有最多邻居节点个数，则归并到任意一个中心点所在簇中。最大邻接关系就是

12、具有最多最近共享邻居节点数量。最近共享邻居节点数量越大证明两节点间的关系越紧密。由高密度数据集分布规则知道，中心节点在数据区域内部。所以要将有链接关系的非中心节点（归属点）聚类到关系最紧密的簇中。通过以上两步就确定了簇集合。簇集合确定后，就可以利用所获得的信息为聚类提供参数，进行的聚类过程（）。（）中获得的剩余中的聚类是将点集合聚类到所形成的簇集合中，最终形成基本簇。基本簇与实际的聚类结果是有区别的。为了得到真实的聚类结果，需要进行一次验证。在算法的（）中，将关系紧密的基本簇合并为同一个簇。人工实验数据集收敛能力是聚类算法非常重要的指标。因此设计一个维个点的数据集来验证的收敛能力，并进行执行效

13、率的比较。表是、和算法收敛能力的比较结果。其中收敛能力由决定。图是与和执行效率的比较。表收敛能力比较获得基本簇后，有可能将原本属于同一个簇的数据集分割开了。因此利用簇间关系将这些原本同簇的数据集进行设两个合并。在同一个簇中，中心区域节点间的关系是紧密的。基本簇，将它们的剩余点集合分别设定为，。设剩余点，。剩余点与所属基本簇间的关系相对中心区域的节点间关系来说是弱关联的。假设这两个簇进行合并。那么必须满足，#（，）（），（#），（）（#由表可以证明具有很好的收敛能力，所以生产了更好的聚类效果。、和的收敛能力较差。图证明了的执行效率高于和。其中和为，中有相互链接关系的节点，。（，）%（，）%（）（

14、）公共实验数据集为了验证的聚类准确性，在此利用一个二维的如果两个基本簇要合并，它们各自的剩余点间的关系一定要紧密。合并后的部分应该是中心区域或靠近中心区域，那么它们的关系相对于合并后簇的边缘节点间的关系更紧密。簇的最基本条件是内部链接一定大于外部链接。实验证明，有效地克服了算法及其改进算法所存在的问题，能。（）。，步骤个节点的公共数。图是与经典、和的聚类结果的比较实验。其聚类结果为个簇，将此参数提供给其它算法。进行自动聚类。有一部分高密度数据区域对聚类结果的影响很大。由所以聚类结果。图中（）和（）看出和聚类单世民，于红，张业嘉诚，等：基于最近共享邻居节点的聚类算法，（）实验表明，在未给定聚类个

15、数的前提下，利用最近共享邻居节点算法，能够为聚类提供参数，自动生成正确聚类结果。通过聚类指数的比较证明，算法对初始值敏感且陷入局部最小值。算法虽然能够克服陷入局部参数设定影响了最小值的问题，但仍然需要给定聚类个数。算法的准确性。在聚类准确性和收敛能力方面有一定的缺陷。通过收敛能力的比较实验证明，具有很好的全局寻优能力。结论聚类分析是数据挖掘中令人关注的热点。经典需要用户设定聚类个数，并且需要随机产生初始解。因此易陷入局部收敛，影响了算法的准确性。因此提出了一种基于最近共享邻居节点的聚类算法（）。利用最近结果有较大偏差。由图（）得到在未给定聚类个数的情况下，（）为在高密度区域未能找到正确聚类结果。图的聚类结果。可以证明能将数据区域进行有效的分割，得到正确聚类结果。利用公共数据集对这些算法进行误差率比较。由图得到的误差率很小。、和的误差率比共享邻居节点（）查找基本簇个数和初始簇，为聚类提供参数。避免了参数选择不当而引起的聚类结果不准确的问题。实验证明比经典、以及算法具有更好的聚类效果和执行效率。参考文献：，：（）：，：，都有一定的提高。由数据集和证明算法的准