文摘

密度山峰聚类(DPC)是一种先进的集群技术由于其有效地确定聚类中心的多个优点,更少的参数,没有迭代,没有边界噪声,等等。然而,它确实患有以下缺陷:(1)难以确定一个合适的值的关键截止距离参数,(2)当地的密度指标过于简单找出适当的中心(s)的稀疏集群(s),和(3)并不健壮的部分知名远程密度峰值。本文提出了改进的密度峰值集群基于自然邻居扩大集团(DPC-NNEG)。的核心算法包含两个部分:(1)定义自然的邻居扩大(向)和自然的邻居扩大集团(NNEG)和(2)将所有NNEGs划分为一个目标数量的集作为最终聚类结果,根据NNEGs的亲密程度。与此同时,本文提供了亲密度的测量。我们比较艺术的状态与我们的建议在公共数据集,包括一些复杂而真实的数据集。实验表明该算法的有效性和鲁棒性。

1。介绍

聚类算法,通常是无监督学习,是一种机器学习的基本技术(1]。它的目标是将数据集划分为若干子集,也称为类别、集群、团体等,根据相似性,不同,或样品的距离。因此,与监督学习(2- - - - - -18),聚类方法实现分类任务没有任何先验知识,并应用于图像处理、模式识别、数据挖掘、生物信息学,物联网等领域。

由于灵活性和有效性,提出了各种聚类算法。耆那教的这些方法分为partitioning-based、基于模型hierarchical-based,基于网格和density-based方法(19]。分区方法目标进行分组数据集到一定数量的集群通过一个迭代的过程。K——(20.,21)和模糊c——(22,23)是两个著名的partitioning-based集群。尽管他们是容易理解和容易实现,K则是极其敏感异常值和初始聚类中心的选择;此外,模糊c方法受初始分区则依赖(1]。基于模型的聚类方法需要一个或多个适当的概率模型来代表数据集和经常使用的采用方法最大化似然函数(24]。Hierarchical-based方法(25- - - - - -28]数据集分割成几类使用两个相反的方法:自顶向下或自底向上方法(23]。第一个考虑作为集群整个数据集分割成合适subclusters的数量。另一个认为每个样本作为一个簇,然后合并这些原子簇为越来越多的大规模集群。然而,层次聚类算法的有效性取决于距离测量的类型选择的集群。基于网格的(29日]和density-based [30.,31日)使用合适的方法自动确定类别的数量和预设参数ε等min-pts或其他人。而需要采取的质量参数的调整来获得最优聚类结果,这两种算法在集群边界产生噪音。

为了克服上述缺点,最近,密度山峰聚类(32]提出了基于假设集群中心相对密度和相互远离。截止距离使用一个合适的值(即,DPC)的唯一参数,这种方法手动选择适当的决策图的每个集群中心。然后分配每个剩余的元素到最近的密集的点(NDP)最近的一个邻居拥有更大的密度比分配样本。它有许多优点,包括更高的效率在寻找集群中心,更少的参数,周围没有迭代,没有噪音集群边界。然而,该算法仍然是受以下缺陷:(1)它是具有挑战性的决定合适的直流。它还必须提到原始DPC算法不涉及一个可靠的和具体的方法,以确保适当的直流。除此之外,这是在几项研究[33,34DPC的敏感参数,即使被标准化的或使用的相对比例方法,一个小变化在华盛顿仍将导致结果明显的波动。(2)当地密度是太简单的公式来找出合适的中心(s)的稀疏集群(s)和仅用于数据集与平衡密度(33]。如图1(一)耆那教的数据集有两个集群:上一个是稀疏和下一个密度。然而,DPC俯瞰集群上的中心,而不是突出集群密度的峰值低。(3)它的分配策略是不健壮35]。每个点分配给它的民主党,结果在一些知名密度峰值(PDP),在密度和相对更大 值而不是集群中心错误地归因于密集的上级,但彼此远离。因此,incorrect-assigned PDP的下属是按一个不正确的组。图1 (b)显示我们手动修改集群中心的密度最大的点上。然而,突出当地峰值最高的集群是分配给其民主党属于集群越低,从而导致错误的下属的任务。有一个不同的作业路径之间的差距。

(一)
(一)
(b)
(b)
图1
聚类结果DPC的耆那教的数据集。不同的颜色呈现不同的集群,集群和星星标志着中心和著名的当地的山峰。(一)在耆那教的DPC的聚类结果。(b)与修改中心DPC的聚类结果。

提高DPC的性能和灵感来自自然的邻居的想法(NN) [36),我们提出了一种改进的密度峰集群基于自然邻居扩大后的集团。的主要创新和改进我们的算法如下:(1)定义自然的邻居扩大和自然的邻居扩大集团基于众所周知的K最近邻居法和最优版本命名为自然的邻居。自然的邻居的概念扩大吸收这些近邻被忽视的神经网络方法。和NNEG能够克服PDP的远程作业的缺点和我的潜在结构数据。(2)提供一个基于向密度指标公式。向的帮助下,新测量的自适应计算每个样本的局部密度不带任何参数,与最初的DPC之一。(3)提出测量NNEGs的亲密程度,基于共同和成对邻居NNEGs属于不同。由于其应用程序,所有NNEGs分为目标数量的集作为最终聚类结果。(4)时间复杂度是 ,在哪里 是一个常数,而所有的优化算法的时间复杂度和DPC吗 (34]。

本文的其余部分由四个部分组成。部分2描述了相关的工作。部分3代表了DPC,神经网络方法,算法的细节。部分4介绍了聚类结果我们的建议和相关的工作。节5的,我们有一个总结本文的贡献和特点。

改善DPC算法的性能,学者们提出了许多优化方法,如图2。谢等人修改密度度量公式使用K最近的邻居(资讯),使用最近的邻居的数量来取代直流。除此之外,他们设计了一个全新的基于模糊加权分配方案K最近的邻居(FKNN-DPC) [33]。此外,这种方法更容易确定合适的参数值。Lotfi等人提出了一种叫做IDPC [37]。算法类样本利用当地中心的密度,然后入账的标签资讯开发集群核心。最后,IDPC实现一个特定的传播策略与标签附加其余点。郭等人利用线性回归方法适合DPC的决定值与预设的合适的直流要求(DPC-LRA),然后选择上面的实例拟合函数作为中心(38]。丁等人提出了一个算法基于广义极值分布(GEV)适合DPC决策值的降序排列(DPC-GVE)。降低时间复杂度,也代表了代换法用切比雪夫不等式(DPC-CI) [39]。Ni等人提出了密度差异和密度的定义路径,以及一个新的阈值(35]。DPC的决策图,而是适当的直流值是由人工观察总结图将计算出的密度差异不同。方法,名叫PPC,能够明显降低阈值确定的困难。江等人提供了一个新颖的基于密度山峰聚类算法K最近的邻居(DPC-KNN)克服分配的问题(40]。在这种方法中,每个样本有两套 :第一个是 ,这是由样品吗 和它的资讯,而第二个 ,涵盖数据点密度具有高于样品吗 在整个数据集。集群中心通过DPC的决策图,确定DPC-KNN分配每个剩余样品的成分 ,谁有最小距离的成员吗 任何成员的 。Lotfi等人使用密度提高DPC骨干和模糊邻域(DPC-DBFN)。他们使用一个模糊的内核为提高集群的可分性。DPC-DBFN使用density-based资讯图标签骨干和有效分配正确分类标签样本在组织边界有效集群数据与各种形状和密度(34]。


图2
DPC的改进方法。

然而,FKNN-DPC IDPC DPC-KNN, PPC, DPC-DBFN需要手动操作。和一个预设直流DPC-LRA是必要的,DPC-GVE, DPC-CI。此外,DPC和这些算法需要的时间复杂度 (34]。

3所示。方法

本节旨在呈现短版本的原始的DPC算法和神经网络方法和显示我们的方法的详细描述。

3.1。最初的DPC算法

DPC集群中心的基础是相对密度和相互远离。对于一个给定的数据集 ,在哪里 ,集群中心手动选择的决策图,这是二维的 为纵坐标和当地的密度为横坐标。局部密度是衡量你的邻居每个样本在其社区的数量和距离,这是一个至关重要的DPC的概念。纵坐标的 样本之间的距离吗 和它最近的密集的点。自中心相对啤酒密度,每个人必须远离他们的民主党,也就是说,有一个巨大的价值 。在二维坐标系中,集群中心同时拥有大的值 和当地的密度和出现在右上角的图。测量每个元素的局部密度,作者提供了两个公式表示为方程(1)和(2)。 通过方程计算(3): 在哪里 两两元素之间的距离吗 和 , 是截止距离,DPC的惟一的参数。因此,DPC算法继承了一个缺陷,高斯核函数带宽敏感:

如方程所示(3), 元素之间的最小距离吗 和 谁的密度高于 。为 最高的密度,它 之间的最大距离是吗 和 。集群中心被发现后,每个剩余点分配给相同的集群的最近邻密度更高。

3.2。自然的邻居法

K最近的邻居是一个流行的方法在机器学习来完成的任务分类和聚类。然而,至关重要的参数K是手动预设。和自然的邻居是一个自适应方法找到每个样本的相对近的邻居。神经网络的基本思想是,样本密集的地区有更多的邻居;数据点的稀疏区域相对较少的邻居;离群值只有很少或根本没有自然的邻居。

在数据集 ,作者认为 是两个点之间的相似性 和 。的帮助下比较相似,让 表示资讯搜索返回的函数 最近邻的点 , 是的一个子集 ,它的定义如下:

定义1。(自然的邻居)。自然的邻居 被定义为

定义2。(自然的邻居特征值)。当算法达到稳定的搜索状态,自然邻居特征值(NaNE)λ等于搜索圆的 :

3.3。该方法

在本节中,改进的密度峰集群扩大后的集团提出了基于自然的邻居。我们的方法包括三个主要步骤,包括(1)计算每个样本的局部密度根据提出的公式,(2)确定自然邻居扩大组织,和(3)分组NNEGs分成几集作为最终聚类结果。描述这些步骤的细节在本节的其余部分。实现上面的处理,我们定义自然的邻居的概念扩展,然后提供一个简单但有用的局部密度公式。此外,自然的邻居的定义扩大集团是揭示数据集的结构,将数据集划分为几个地方组织。对于确保NNEGs准确性的分组,我们提出一个亲密度的测量。和更多的细节在本节的其余内容。

3.3.1。基本概念

神经网络方法只考虑共同邻居的关系,忽略了样本之间的距离的影响。适合密度指标和密度的峰值的搜索,我们提出的概念自然邻居扩大。

定义3。(自然的邻居扩展)。自然的邻居扩大被定义为以下方程: 我们假设的数量在哪里 的 是 和 是 。因此, 。如图3样本1神经网络样本8,因为它不属于 。然而,样本1接近示例8比14。因此,计算密度更完全,准确地说,我们扩大的自然社区样本8包括样品1、2和7。
自然的邻居是近邻的集合。不过,见方程(2),地方密度公式措施不仅距离样本的近邻 小于直流也是整个数据集的其他样本。在后期,距离样本 近似直流和相应的样本的密度也影响 。因此, 方程(7)是覆盖更多secondary-adjacent样本在近邻的旁边。和新的基于向显示为当地密度公式 在哪里 , ,和 组的距离吗 所有的元素 。灵感来自著名的K方法,则方程(8)认为每个点为核心,并计算其向距离的总和。距离之和越小,越有可能是当地的中心。
方程(2)地图的距离使用高斯内核和相似性计算相似性的积累和链接 作为 。因此,方程(2基于高斯内核可以抵御异常值的干扰,它拥有巨大的距离 。然而,方程涉及太多微不足道的样本,样本的距离 密度大于直流,因为他们的贡献很小通过高斯核函数的映射。此外,它将原来的DPC的时间复杂度 。
相比之下,我们的公式只考虑向。,因此,也摆脱了被动异常值的影响,因为他们通常都是遥远的从其最近的点并不是在任何向(s)其他(s),同时,降低计算复杂度。与高斯内核映射不同,方程(8)保留了原始信息的数据,不需要任何参数,并避免造成的敏感性。


图3
部分的原理图及其样品 = 6。样本1有6个神经网络,包括样品2,3,4,5,6,7;示例8有六个神经网络,包括样品9、10、11、12、13、14所示。

定义4。(自然的邻居扩大集团)。自然的邻居扩大集团由一个著名的密度峰值和其下属。
在我们的方法中,每个点分配给最近的密集的点向。作业过程是存储在一个列表:索引数字代表样品在给定的数据集,分别;每个单元存储索引号的上级,如果一个样本的密度大于所有的民主党,相关单位节省了0。即零样本是突出的密度峰值。赋值将数据集划分为几个NNEGs,自适应。
从本质上讲,NNEGs揭示潜在的数据集的结构分析和相对紧缩subcluster和当地组织集群中的地面真理。由于NNEG的应用,每个样品只指向一个邻居,我们的方法可以避免PDP的远距离作业。
如图4NNEGs决心后,我们的方法只需要将这样的当地团体合并到目标数量的集群,因此从决定删除操作中心的选择图表,它克服了提到DPC的密度指标问题。澄清NNEGs之间的密切关系,提出了相邻组的概念图。


图4
NNEGs耆那教的数据集。不同的颜色呈现不同的NNEGs,星星标志着零样本。

定义5。(相邻组图表)。 ,在哪里 是一组NNEGs, ,和 是一组相关的边缘NNEGs吗 和 ,并受 相邻的组织图通常是油印,因为可能有多个 之间的 和 。和更多的边缘,两组接近。显然,在图4,没有边缘上部和下部之间的集群。此外,亲密的程度(DC)的邻近成对NNEGs计算 在哪里 和 。如方程所示(10),亲密度的公式是用两个部分构成:重量和归一化的相似之处。它是基于一个假设,更紧凑的端点和各自NNEGs,更可靠的边缘。 表示样本之间的紧密度 和组 ,即,更大数量的分割的元素 和 意味着他们之间的关系是冻融。以确保 ,分割的元素的数量除以 。

3.3.2。具体的处理

输入:数据集X目标数量的集群。输出:聚类的结果。步骤1:创建一个k- - - - - -d树。为每个示例使用搜索向k- - - - - -d树。步骤2:计算局部密度根据方程(8)。步骤3:确定NNEG根据定义4。第四步:生成邻组图形的定义5,并找到所有边的每一个成对NNEGs方程(9)。第五步:计算亲密的程度,根据方程(10)。第六步:原始集群包含所有NNEGs分解成目标集的数量,根据亲密程度。

澄清详细步骤6,我们提出在表的一个示例1。如表所示1(一个),有五个NNEGs数据集。和相邻的亲密度成对NNEGs记录。假设我们的目标数量是2。我们的方法考虑了整个数据集作为一个集群, 。我们强迫最低 如表所示1(B),这意味着这些NNEGs分成两部分: 和 ,即。,split is a for-loop operation which let the minimum 直到集群数量等于目标之一。

表1
步骤6的一个例子。

和更多的细节是伪代码所示。在6th线,gg是一个矩阵每一行和每一列对应于NNEGs之一。在16th线,灵感来自于自上而下的分层聚类,我们认为整个数据集作为一个集群包含所有NNEGs和打破最弱 在gg,直到集群数量等于目标,对应于过程,表1(A)和(B)。

3.3.3。时间复杂度分析

本部分旨在分析我们的方法的计算复杂度,并假设总样本数据集的数量 ,NNEG等于的数量 ,目标数量的集群 ,新民主党的样本 是 邻居,和最大的 = 。(算法1)。

需要:数据集 ,目标数量的集群G
确保聚类的结果:
(1) 创建一个k- - - - - -d树;
(2) 搜索k- - - - - -d树;
(3) 确定神经网络根据(34),并记录 ,这意味着 确定;
(4) 计算局部密度 根据方程(8)。;
(5) 每个点分配给其民主党向生成几个NNEGs;
(6) 创建一个矩阵gg = ( , );
(7) 为我= 1:n做
(8) 为t= 1: 做
(9) 如果t向和样本我属于不同的NNEGs做
(10) 计算这条边的亲密程度,指的是方程(10);
(11) 加上这条边的直流gg的相应单位;
(12) 如果
(13) 结束了
(14) 结束了
(15) 而集群的数量不等于G做
(16) 零存储在单元的最小值大于零;
(17) 计算集群的数量;
(18) 结束时
算法1
DPC-NNEG。

创建一个k d树的时间复杂度 (41]。它是所有样品还需要证明,确定神经网络的成本 (36]。寻找向,我们可以记录的 处理的神经网络搜索。因此,样本只需要搜索向 次搜索操作,所有样品小于整体的复杂性 。我们当地的密度指标是基于向,没有必要,只需要生成一个距离矩阵 * +操作对于每个样本。因此,它需要最多 时间成本来计算局部密度的所有实例。对于每一个样品,需要的方法 搜索其民主党通过k d树轮 ,和 。每个NNEG在生成的过程中,我们商店的标签,著名的密度的峰值列表第一单元是任何未分配的实例,和结束是一个分配一个或突出密度峰值。和存储的操作标签的样本只需要的时间成本 。和所需的成本 将数据集划分为上 NNEGs。在方程(9)和(10), 通过搜索请求并确定每个样本的向找到邻居有不同的标签。因此,对于所有的边缘,它等于 多少次的级执行搜索操作。此外,分组的时间复杂度必须不到最后一步 。总的来说,我们可以得出结论,整个算法的时间复杂度 。

4所示。结果

在本节中,几个数据集被用来评估我们的方法的性能相比,一些先进的技术,如DPC-DBFN [34],DPC-KNN [40],IDPC [37],FKNN-DPC [33]。实验与Windows电脑上执行10,英特尔(R) (TM)核心i7 - 8750 h, 16 GB的内存和Matlab 2016 b。表示测量结果几个性能指标,包括归一化互信息(敝中断)42),兰德指数(RI) (43),调整兰德指数(ARI) (44]。在本节中,点之间的相似性是使用欧氏距离度量来衡量。

4.1。数据集

本文包括三个低维数据集和测试数据集五高维数据集,这是公众和UCI。二维数据集分布有不同数量的样本和不同的目标。DMI512数据集包含1024个元素与512 -维特性,属于16高斯集群抽样从高斯分布,常被用来测试算法在高维空间的表现。四个数据集的实验,包括Statlog(航天飞机),鲍鱼,葡萄酒的质量,和天秤座的人运动,是我们方法的应用物理(散热器的定位在航天飞机),人口生物学模型酒首选项,分别和手的运动识别。和更多的细节展示在表2。

表2
对测试数据集的详细信息。

减少维度权重的影响,确保实验的有效性比较,我们每个数据集和规范化处理所有数据集进行测试。归一化公式如下: 在哪里 是 的特征值 样品, 和 代表的最大和最小值 特性,分别。

4.2。评价措施

我们测试了我们的算法和几个相关工作上面的数据集。直观的比较,我们选择了国际扶轮,阿里,敝中断来衡量聚类结果。

国际扶轮公式所示 TP表明真阳性,TN表明真正的负面,分母 在数据集的样本总数对组成的吗n样本。

ARI公式所示 在哪里 代表国际扶轮的期望。

敝中断公式所示 在哪里 , , 代表的期望 ,和 表示为 在哪里 , , , ,和 。 和 代表数据集包含两种分配方法n元素, 和 是集群。在实验验证,让 和 是原来的标签和一个算法的聚类结果,分别。如果聚类结果一样真正的标签,这三个指标的值为1,如果聚类结果完全不同的标签,就等于0的值。

4.3。结果

本节旨在展示详细的聚类结果和评估不同的聚类算法的性能在不同的数据集。表3- - - - - -5比较我们的方法的性能和DPC-DBFN, DPC-KNN, IDPC,和FKNN-DPC敝中断,RI,分别和阿里的措施。所有这些方法都使用资讯的方法,和最近的邻居的数量(K)可以从1到设置n。在这些表,括号中的数字的值K,相应的算法获得的结果代表和黑体是最好的结果。

表3
聚类结果衡量敝中断。
表4
聚类结果衡量RI。
表5
聚类结果衡量阿里。

耆那教的数据集有373点和两个集群:上一个和下一个。如图5,DPC-NNEG将数据集划分为19 NNEGs然后成功和有效地组织成两组,因为没有两个集群之间的边缘。类似地,如图6,我们的算法将螺旋数据集划分为几个当地团体和随后合并所有NNEGs准确的目标集群。

(一)
(一)
(b)
(b)
(c)
(c)
图5
耆那教的数据集的聚类结果。不同的颜色呈现不同的NNEGs和集群,星星标志着零样本。(一)NNEGs耆那教的。(b) DPC-NNEG耆那教的。(c)地面真理。
(一)
(一)
(b)
(b)
(c)
(c)
图6
螺旋数据集的聚类结果。不同的颜色呈现不同的NNEGs,星星标志着零样本。(一)NNEGs螺旋。(b) DPC-NNEG螺旋。(c)地面真理。

不像Jain和螺旋,如图7火焰数据集包含240数据点没有明确的两个相邻簇之间的差距。因此,它更敏感的价值直流直流的DPC算法因为一个微小的改变会导致被分配到另一个集群的边界点。然而,我们的方法不仅分区所有样品成八NNEGs还措施准确不同群体之间的紧张,意识到这些地方组织的正确的分组。和图7表明,火焰由DPC-NNEG辅音的聚类结果与地面真理。

(一)
(一)
(b)
(b)
(c)
(c)
图7
数据集的聚类结果火焰。不同的颜色呈现不同的NNEGs,星星标志着零样本。(一)NNEGs火焰。(b) DPC-NNEG螺旋。(c)地面真理。

如表所示3- - - - - -5没有区别,表现在我们的算法,DPC-DBFN, DPC-KNN IDPC, FKNN-DPC三维数据集。然而,如表所示2更复杂的高维数据集的聚类结果显示我们的方法的表现:DPC-NNEG收益最好的标志由敝中断在所有的数据集。例如,结果的DPC-NNEG Statlog(航天飞机),鲍鱼,葡萄酒的质量,DIM512,和天秤座的人运动数据集是0.6101,0.1852,0.0935,1.0000,和0.5855,分别。此外,其改善第二好的方法(%)为Statlog(航天飞机),鲍鱼,葡萄酒的质量,和天秤座的人运动数据集分别为11.13,0.32,33.38和0.12。

表4和5显示类似的结果,分别测量了由国际扶轮和阿里。这些结果也表明该方法,在大多数情况下,获得最大的价值敝中断除了葡萄酒质量的数据集。因此,根据这些结果,可以得出结论,DPC-NNEG给了集群的整体性能优良。

5。结论和未来的工作

提出了一种有效的聚类算法称为DPC-NNEG,可以轻松地将数据集分为地方组织,然后将这些组织合并到目标的集群各种密度、形状和大小。该方法的目的是集群数据通过三个主要步骤:计算每个样本的局部密度,确定自然邻居扩大组织,这些组织和合并到集群。第一步利用当地的自然邻居法计算密度。是完全不同的从最初的DPC的公式,可以避免大纲窗口的影响,减少直流的敏感性。在第二步中,是我用来定义的向潜在的数据结构,这有助于将数据集划分为几个相对更紧凑的当地组织称为NNEGs。和最后一步组织所有NNEGs目标数量的集群使用该公式的亲密程度的地方组织。和应用程序的第二个和第三个步骤不仅克服了远程作业的问题突出密度峰值也删除原始DPC中心选择的步骤。验证了提出的方法的有效性在几个数据集。结果表明,我们的方法是更有效的针对DPC的相关改进算法。在未来的工作中,我们将对发展的概念向secondary-adjacent样品,找到一个更合适的方法,而不是给定的和固定参数 在方程(7)。模糊理论是我正确的技术相对邻近样本,其中NNE是用于构造亲密的隶属函数,然后推断secondary-adjacent样品的功能和远程样本。

数据可用性

所有在UCI数据集摘要可用。

的利益冲突

作者宣称他们没有利益冲突的报告对于本研究。

确认

这项研究是由中国国家自然科学基金(61972056,61972056,61972056,61981340416),湖南省自然科学基金(2020 jj4623),湖南省教育科学研究基金部门(a007 17、19 c0028和19 b005),长沙科技计划(KQ1703018, KQ1706064、KQ1703018-01 KQ1703018-04),长沙青年教师发展项目工程科技大学(2019 qjcz011),“双一流”国际合作与发展长沙科技大学的科研项目(2019 ic34),实际的创新和创业能力改进计划的专业学位研究生长沙科技大学(SJCX202072),湖南省研究生培养创新基地建设项目(2019-248-51和2019-248-51),湖南省教育部门和北斗微项目(XJT (2020) No.149)。