文摘

针对密度山峰聚类需要手动选择集群中心,提出了一种快速新聚类方法自动选择集群中心。首先,我们的方法组每组数据和标志为核心或边界组根据其密度。其次,它决定了集群通过迭代合并两个核心群体的距离小于阈值并选择集群中心在每个集群最密集的位置。最后,它分配边界组织相对应的集群最近的聚类中心。我们的方法不需要手动选择集群中心,提高聚类效率与实验结果。

1。介绍

聚类(1- - - - - -4)是一种无监督或semisupervised学习方法。这种方法旨在将样本划分为不同的簇根据样本之间的相似性,这样尽可能相似的样本在同一集群和样品在不同的集群是尽可能不同。集群有广泛的应用,如图像分析(5),模式识别(6),数据分析(7),和无线传感器网络8]。根据广泛应用,出现了许多聚类方法,如k - means (9)和模糊c均值(FCM) (10)聚类方法,只有有效的球面数据和下等影响nonspherical数据。但density-based聚类方法(11)如密度山峰聚类(DPC) [12没有这个问题。然而,DPC仍然有一些缺陷,因此改善density-based聚类方法具有重要意义。

针对DPC的问题需要人工参与选择集群中心,弗洛雷斯et al。13)提出了一个密度山峰聚类中心gap-based自动检测方法。这种方法计算一个阈值来区分集群中心样品和noncenter样本。Lv et al。14)提出了一个密度峰值基于共享的最近邻聚类算法和自适应集群中心。该方法通过缩小搜索范围选择集群中心。然而,集群中心通过上面的方法是DPC的一样。换句话说,如果DPC不能达到好的结果在一些数据,上述方法不能达到良好的结果。

针对高时间复杂度的DPC,陆et al。15)提出了一种快速分布密度山峰聚类方法基于z值指数。该方法有效地减少了时间复杂来 ,但集群效应是显著降低,因为数据需要从多维减少到一个维度。徐et al。16)提出了一个基于备用搜索快速峰值密度聚类方法。该方法保证了集群效应,有效地降低了时间复杂度 ,但它仍然需要手动选择集群中心。虽然上面的方法提高DPC的效率,他们也有缺点。

最近,有很多方法来提高精度的DPC (17- - - - - -20.]。这些方法有更多的优势对于一些数据和相当大的噪音和复杂的结构。在[17),介绍了密集的核心代表原始数据,以减少运行时。密度阈值是用来消除干扰噪声样本。但是,它有困难处理高维数据。在[18),局部密度峰值用于构造最小生成树,避免噪音和减少运行时。然而,它不能自动确定集群的数量。在[19),当地的核心代表数据集介绍,避免噪音干扰,减少运行时只计算图像之间的距离当地的核心。然而,它需要建立一个决策图。在[20.),引入自然邻居找到当地表示,计算自适应距离当地表示有效地降低了运行时。然而,它不能自动确定集群中心。杜et al。21)提出了一个再DPC基于主成分分析的方法。它使用再计算样本密度和主成分分析处理高维数据。然而,它不是有效的在处理多方面的数据。

本文提出了一种新的密度峰聚类方法(管理总局),可以通过分组快速和autodetermine集群中心。我们的方法针对分组数据集,以确保样本类别的每组是相同的,尽量减少组织的数量。通过这种方式,我们不再需要计算所有样本之间的相似性但只有团体之间。与此同时,我们发现集群中心每个集群通常出现在最密集的地方。我们可以把每个集群分为核心和边界区域根据功能集群中心集群优势的密度逐渐降低。两个核心区域之间的距离是相当大的,这样我们才能找到集群中心。

本文的其余部分如下:在第二部分,我们回顾DPC。第三节介绍我们的方法。在第四节,我们做实验在合成数据集和真实数据集的有效性和效率。最后,本文总结并提出了进一步的挑战。

2。DPC

2.1。量

DPC需要使用样品的密度( )和样品之间的距离其最近的高密度样品( )当发现集群中心和确定样品标签。

样品的密度是其他样本的数量在其截止距离( )的范围内。样品的密度被定义为 在哪里样本之间的距离吗和样本 ,和 如果 ;否则, 。

样品之间的距离和它最近的高密度样品被定义为

为样例最高的密度, 。

2.2。相似度矩阵

在计算和并确定样品标签,样本之间的距离计算很多次。为了提高效率,DPC只计算样本之间的距离一次并保存。它不再需要重新计算时再次使用。相似矩阵的定义是 在哪里样本之间的距离吗和样本 。 是样品的数量。

2.3。过程

后计算和使用上面的方法,我们使用作为横坐标,作为纵坐标决定画一个图,如图1。图1(一)显示样本的分布。图1 (b)是相应的决策图。我们可以发现决策图的右上角显示集群中心。

选择集群中心之后,剩余的标签样品是一样的,最近的高密度样品。

2.4。时间复杂度

的时间复杂度DPC有三个主要部分:(一)计算需要时间复杂度;(b)计算需要复杂性;和(c)确定标签noncenter样本的要求时间复杂度,是数据集的大小。基于上述三个部分,DPC的时间复杂度 。

3所示。该方法

解决人工干预选择集群中心DPC的DPC和高时间复杂度,我们提出管理总局。在管理总局,我们隔离不同集群的核心地区找到集群中心和使用分组方法来减少计算量。

3.1。分组

的情况下确保每组样本标签是相同的,团体的数量越少,效率越高我们的方法。

我们定义未分组的样本之间的距离第一个样本组作为 。我们把样品进组如果 。如果没有组使 ,我们创建一个新组。样本是第一个样品在这个组。算法1详细解释了分组方法。

这些群体有以下特点:(1) :第一次样品和其他样品之间的距离小于 。(2) :相同的样本中不存在两个不同的组。(3) ,在哪里是集群和第一组样本吗 。所有样品在同一组属于同一集群。

区分是否集团是一个核心小组或边界组,我们需要使用群体密度,是指哪一个

定义1。(零密度组)。只有一个样本。如果集团是零密度, 。
通过经验,我们先删除组与零密度,然后安排其余组密度在降序排列。最后,如果组织的密度大于或等于密度阈值( ),集团被定义为核心小组;否则,它被定义为边界。密度阈值被定义为 在哪里非零的数量密度组和吗的密度吗 - - - - - -th组后降序排序。
如表所示1,有7零密度组。密度阈值计算方程(5)是 , 。因为组织的密度0,1,2,3,4,5是大于或等于 ,他们是核心组。的密度组6、7小于 ,所以这是一个边界。组7的密度 ,所以这是一个零密度组。

3.2。选择聚类中心和确定核心组样品标签

当我们确定核心集团集时,我们需要找到每个集群通过其空间关系的核心地区。然后,我们可以选择每个集群的集群中心密度是最密集的地方。

我们建议以下定义。

定义2。(关键样本)。每组的第一个示例。

定义3。(传递性)。如果任何样品组之间的距离和样本组的关键小于 , 可以达到通过传递性。
两组和传递性满足以下方程: 在哪里任何样品组之间的距离吗和样本组的关键 。我们可以结合核心组(加入同一个集群)通过方程(6)。
图2,因为 ,因此,通过传递1组可以达到2组。因此,也有群体之间的传递性和 。通过传递性,我们可以连接组 ,集团 ,和组 ,所以他们属于同一集群。
假设组织的密度最高的组吗 , ,和 ,和组已经在集群 ,而组和不是在任何集群。因为有团体之间的传递性和( ),和组在集群 。所以它可以被视为组之间的传递性和集群( )。后组添加到集群 ,集团和集群也有传递性,所以组可以添加到集群 。
算法2显示了具体步骤,样本之间的距离吗在集群核心和任何样品 。 组中的所有样本的集合的第一个样品吗 。 是第一个样本在当前核心。首先,我们选择第一个示例的核心集作为初始聚类中心。其次,连接通过传递相应的组与其他核心团体。下面的独立样本的核心是选为集群中心当更多核心组不能连接。重复以上步骤,直到所有的核心团体被指定集群。

3.3。确定边界组样品标签

当选择集群中心,我们两个传递核心团体标记为相同的集群。通过这种方式,我们可以确定核心组样本的标签同时在选择集群中心。

发现集群中心后,我们计算边界之间的距离组和核心组样本。如果组之间的距离和核心集团样本小于 ,所有样本组有相同的标签样品吗 ,组之间的距离在哪里和样本关键样品组之间的距离吗和样本 。在那之后,我们需要确定其余边界组的标签样本。我们计算关键样本之间的距离在每个非零密度边界组和每个集群中心。我们将非零密度边界组划分为相对应的集群最近的聚类中心和零密度边界组样本标记为噪声样本。

3.4。过程

我们的方法(算法3)由以下五个主要步骤:(1)组数据集使用 ;(2)选择集群中心和确定核心组样品标签通过传递;(3)计算边界之间的距离组和核心组样本并确定边界距离小于组标签 ;(4)计算剩余的非零密度边界组之间的距离和集群中心,并确定剩下的非零密度边界组的标签;和(5)剩下的零密度组样本标记为噪声样本。

3.5。例子

在本节中,我们通过一个例子介绍我们的方法的过程,如图3和表2。(1)组数据:计算样本之间的距离和现有的组。由于没有组,创建一个新组 ,并添加样本组 。计算样本之间的距离和现有的集团( )。因为 ,创建一个新组并添加样本组 。计算样本之间的距离和现有的集团( , )。因为 和 ,所以添加样本组 。重复以上步骤,直到所有的样本都添加到组中。计算每组的密度由方程(4)。分组结果和密度如表所示2。(2)区分核心或边界组织:首先,我们组的降序排列密度,和结果 。其次,我们删除零密度组和计算密度阈值是1从方程(5)( ),第四组在哪里 ,和它的密度是1。所以组织 是核心的团体和组织 是边界组。(3)确定核心小组标签:选择样本的关键组作为第一个聚类中心,并创建一个新的集群添加组集群 。自 ,添加组集群 。因为团体之间的距离 和集群大于 ,带的关键样品组作为第二个集群中心,创建一个新的集群 ,并添加组集群 。自 和 ,添加组集群 。自 和 ,添加组集群 。自 和 ,添加组集群 。(4)确定边界组标签:因为 和 ,集团暂时不处理。因为 和 ,集团暂时不处理。自 ,添加组集群 。接下来,我们将非零边界组划分为一个集群对应于最近的聚类中心。在这个例子中,没有非零密度边界,所以这一步结束。(5)确定噪声样本:在前面的步骤中,零密度边界组织不是分为集群被认为是噪声样本。在这个例子中,样本和在组和被标记为噪声样本。

完成上述步骤后,聚类过程结束。聚类结果如表所示3。这个示例中生成两个集群,集群包括10个样本 ,10个样本在集群 ,和2噪声样本。

3.6。时间复杂度

我们的方法的时间复杂度有四个主要部分:

假设数据集样品分为核心组织和边界组。(一)分组要求 时间复杂度(b)排序核心组密度需求 时间复杂度(c)发现集群中心和确定核心小组需要样品标签 时间复杂度(d)确定noncenter样本的标签要求 时间复杂度

基于上面的四个部分中,我们的方法的时间复杂度 ,在哪里 。因此,我们的方法的时间复杂度小于 。

4所示。实验评价

本节进行了精度和效率实验,暴露了我们的方法的源代码和合成数据(下载URL = [https://github.com/yongbiaoLi/GDPC.git分别])。

4.1。精密的实验

以下4.4.1。合成数据集

在本节中,我们使用k - means, FCM, DPC,和管理总局ThreeCircles实验,Lineblobs,螺旋,化合物(22合成数据集)。表4显示特定的数据集的信息。

从数据4,5,6,7,集群中心得到的k - means和FCM不一定是样本的数据,但这些DPC和管理总局获得的样本。nonspherical数据等数据4和6,k - means和FCM不能获得正确的集群中心和结果。等数据的数据5和7结合球形和nonspherical数据,k - means和FCM只能获得部分正确的集群中心和结果。DPC可以获得一些聚类中心和数据,如数据的结果5和7因为nonspherical DPC不仅是有效的数据,也为球面数据。然而,从数据4,5,6,7,因为在分发nonspherical DPC是严格的数据,是不可能获得正确的集群中心和结果。我们的方法不受这些分布的影响。

4.1.2。真实数据集

在本节中,我们使用动物园[23)、甲状腺(23],Ecoli [24)、机(23),由这些[23],sobar - 72 [25,段23],Pendigits [23真实数据(细节如表所示5)尝试k - means, FCM, DPC,我们的算法。

从表6,我们可以看到,阿里26,27,敝中断28),和同质性29日管理总局的都高于k - means, FCM, DPC动物园和甲状腺的数据集。机,sobar - 72和sobar - 72数据集管理总局有两个指标高于k - means, FCM和DPC。Ecoli,段和Pendigits数据,只有管理总局是最好的指标之一。括号内的值是参数 。

实验结果表明,尽管管理总局不如k - means, FCM, DPC在一些数据集和度量标准,其性能优于一般。

4.2。效率实验

4.2.1。准备合成数据集

在本节中,我们使用卫星数据集测试效率的DPC和我们的方法,。卫星数据集的分布如图8。从图9我们可以看到,越来越多的数据,DPC显著增加,所需的时间和我们的方法比DPC,它变得越来越明显。

4.2.2。真实数据集

在本节中,我们使用DPC的真实数据集的测试效率和方法。如表所示7,我们的方法总是比DPC更有效率。越大 ,我们的方法是越快。重要的数据量越多,我们的方法和DPC之间的差距就越大。

4.3。参数的影响

在本节中,我们使用卫星数据集测试参数的影响的聚类结果。如表所示8,= 0.05,0.2,0.25,和0.3不能使聚类结果完全正确。作为从0.05增加到0.3,运行时间从277.5秒减少到1.34375秒。

的影响聚类结果主要有两个方面。(一)效率:越大 ,分组后组的数量越少,聚类的速度越快。(b)精度:太小了会导致分组错误,这将降低精度。太小了会导致太多的噪声样本。结合上述两个方面,我们选择最大确保所有样品在每组属于同一集群中。

根据合成数据实验中,通常是一半的之间的距离最近的两个集群的核心区域。因为无法观察到高维的真实数据,它是具有挑战性的选择真实的数据。如何获得的价值在真实数据也是一个该方法的局限性。

5。结论

本文提出了一种新的方法来提高DPC。我们把数据分成小组每组同时确保样品标签是相同的,所以我们只需要计算组减少之间的相似性计算。同时,我们隔离不同集群的核心地区,这使得它容易找到集群中心密集的位置。在许多方法来提高DPC效率,不解决集群中心的自动选择。我们的方法不仅提高了DPC效率,还解决了集群中心的自动选择的问题。

管理总局有很好的影响一些球形和nonspherical数据,但它不执行与噪声样本在一些复杂的数据。因为管理总局只使用一个在一个数据,很难达到良好的分组结果在一些复杂的数据,从而导致不满意的聚类结果和效率。此外,如何获得的价值在真实数据也是一个该方法的局限性。这也是我们需要改进的地方。

density-based nonspherical数据的聚类方法的优点是难以取代。在未来,我们还需要考虑下如何提高效率减少参数。

6。应用程序

集群可以应用到无线传感器数据注释。我们应用活动数据的聚类方法30.老年人的四个州的老年人:(a)坐在床上;(b)坐在椅子上;(c)说谎;和(d)走动。得到的数据通过battery-free可穿戴传感器托雷斯等人。如图10,实验结果表明,该方法具有一定的优势在无线传感器数据注释。

数据可用性

之前报道的数据被用来支持这项研究和可用http://archive.ics.uci.edu/ml。这些之前的研究都是在相关地方引用文本中引用。

的利益冲突

作者宣称没有利益冲突。

确认

中国的国家自然基金项目:研究视网膜图像分割和基于深度学习的辅助诊断技术(61962054)支持这项研究。