密度峰值聚类(DPC)算法的介绍

这篇具有很好参考价值的文章主要介绍了密度峰值聚类(DPC)算法的介绍。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

DPC算法

密度峰值聚类算法(Density Peak Clustering Algorithm)是一种无监督的聚类算法,它能够自动发现数据中的密度峰值点,并根据这些峰值点将数据进行聚类。该算法由Alex Rodriguez和Alessandro Laio于2014年提出,其原理相对简单但非常有效。

密度峰值聚类算法基于两个重要的概念

  1. 局部密度():局部密度指的是一个数据点周围一定半径范围内的数据点数量,可以用来描述该点的密集程度。对于每个数据点,需要计算它的局部密度。

  2. 相对距离():相对距离指的是一个数据点与比它密度(ρ)更大的点之间的相对距离。一般采用欧式距离。

具体实现

有了这两个概念后,我们需要计算出所有数据点的局部密度与相对距离,当与都大时,我们即将该点定义为密度峰值(类簇中心),然后将将剩余数据点分配给密度比它高的最近数据点所在类簇。

  与  的计算

局部密度()表示一个数据点周围一定半径范围内的数据点数量,用来描述该点的密集程度。在密度峰值聚类算法中,局部密度的计算方法如下:

                                                        

其中,是一个核函数,用来衡量数据点i和j之间的距离dist(i, j)的影响。常见的核函数有高斯核函数(Gaussian kernel)、截断核函数(Truncated kernel)、Epanechnikov核函数等。这里可以根据具体需求选择合适的核函数。

采用不同的核函数后局部密度()可表示为:

  • 高斯核函数(Gaussian kernel)

            ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​
  • 截断核函数(Truncated kernel)

                                   

一般来说对于较大规模的数据集,截断核函数的聚类效果较好

而对于小规模数据集,高斯核函数的聚类效果更好

相对距离()

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

代码实现

import numpy as np
import matplotlib.pyplot as plt

def distance(x, y):
    return np.linalg.norm(x-y)

def getDistanceMatrix(data):
    # 计算距离矩阵
    N, D = data.shape
    dists = np.zeros([N, N])
    for i in range(N):
        for j in range(N):
            dists[i, j] = distance(data[i,:], data[j,:])
    return dists

def select_dc(dists):
    # 计算dc,也可以手动输入,此处没有实现手动输入
    # 不使用np.percentile(),是因为dists有部分重复值、0值
    N, D = dists.shape
    dists_flat = np.reshape(dists, N*N)
    dists_sort = np.sort(dists_flat)
    position = int(N*(N-1)*0.02)
    # 将距离矩阵排序后取第2%个,可以调整该百分比使聚类效果更加
    dc = dists_sort[position+N]
    return dc

def calculate_rho(dists, dc, method=None):
    """
    计算ρ
    :param method:
    选择方法,默认为截断核
    传入任意参数,即可选择高斯核
    建议小规模数据选择高斯核,因为该方法计算出来带小数,比较更准确
       大规模数据选择截断核,效率更高
    """
    N = dists.shape[0]
    rho = np.zeros(N)
    # 截断核:(适合大规模数据)在dc区域内有多少个点
    if method == None:
        for i in range(N):
            for j in range(N):
                if dists[i, j] < dc:
                    rho[i] += 1
            rho[i] -= 1
        rho = np.sum(dists < dc, axis=1) - 1
        # 以上可以用向量化代替,效率更高
        # rho[i] = np.where(dists[i,:]<dc)[0].shape[0]-1

    # 高斯核:(适合小规模数据)
    else:
        for i in range(N):
            rho[i] = np.sum(np.exp(-(dists[i, :] / dc) ** 2)) - 1
    return rho


def calculate_deltas(dists, rho):
    # 计算δ
    N = dists.shape[0]
    deltas = np.zeros(N)
    nerghbers = np.zeros(N)         # 密度更高,且距离最近的 点的 索引
    for i in range(N):
        deltas[i] = dists[i, 0]     # 相当于中间值(可用一个大值代替,但不严谨)
        for j in range(N):
            # 要求满足, ρ更大 且 距离最近
            if rho[j] > rho[i] and dists[i, j] < deltas[i]:
                deltas[i] = dists[i, j]
                nerghbers[i] = j
    return deltas, nerghbers

def clusters(dists, rho, deltas, nerghbers, k = 0):
    """
    找出中心点并进行聚类,可分步
    :param k: 默认为0,代表自动确定中心点
              若传入值则确定多少个k中心点
    """
    N, D = dists.shape
    labels = np.full(N, -1)
    cluster = 0

    if k==0:
        # 自动确定中心点,并对中心点进行聚类
        # 设置聚类参数,可以使用np.percentile()函数取中位数
        rho_threshold = (np.min(rho)+np.max(rho))/2
        deltas_threshold = (np.min(deltas)+np.max(deltas))/2
        # rho_threshold = np.percentile(rho, 50)
        # delta_threshold = np.percentile(deltas, 50)
        for i in range(N):
            if rho[i] > rho_threshold and deltas[i] > deltas_threshold:
                labels[i] = cluster
                cluster += 1
                # 画中心点
                # plt.scatter(data[i,0], data[i,1], color="k", marker="+", s = 200)

    else:
        # 手动输入聚类数k,选择ρ*δ最大的k个,作为中心点,并聚类
        rho_deltas = rho*deltas
        center = np.argsort(-rho_deltas)
        for i in range(k):
            labels[center[i]] = i
            # 画中心点
            # plt.scatter(data[center[i], 0], data[center[i], 1], color="k", marker="+", s=250)

    # 对非中心点进行聚类
    # 从密度最高开始,将他们分给比它们密度更高且距离最近的点的类
    rho_sort = np.argsort(-rho)
    for i in rho_sort:
        if labels[i] == -1:
            labels[i] = labels[int(nerghbers[i])]
    return labels

def DPC(data,k):
    dists = getDistanceMatrix(data)
    dc = select_dc(dists)
    rho = calculate_rho(dists, dc, "gasstion")
    deltas, nerghbers = calculate_deltas(dists, rho)
    labels = clusters(dists, rho, deltas, nerghbers, k)

    # 画出rho与deltas
    for i in range(np.shape(data)[0]):
        plt.scatter(rho[i], deltas[i], s=16., color=(0, 0, 0))
        plt.annotate(str(i), xy=(rho[i], deltas[i]), xytext=(rho[i], deltas[i]))
        plt.xlabel("rho")
        plt.ylabel("deltas")
    plt.show()
    return labels

导入数据

data = np.loadtxt(r"data\data.txt")
labels = DPC(data,7)

画出  与  图像:

dpc聚类,算法,聚类,机器学习

 我们取最大的k个点作为类簇中心,再将剩下的点进行分类

聚类结果

dpc聚类,算法,聚类,机器学习

 聚类结果十分完美

其它数据聚类结果展示:

dpc聚类,算法,聚类,机器学习

 

算法改进

  1. 参数选择的自动化:密度峰值聚类算法中需要选择一些参数,例如半径参数ε和截断参数c。改进的方法可以通过自动化的方式来选择这些参数,例如使用基于数据特征的方法或通过优化算法来寻找最优参数。

  2. 聚类中心选择策略:原始的密度峰值聚类算法选择密度峰值点作为聚类中心,但在某些情况下可能存在一些峰值点不适合作为聚类中心的情况。改进的方法可以考虑引入其他策略来选择聚类中心,例如根据密度和距离的综合考虑来选择最具代表性的数据点作为聚类中心。

  3. 密度估计方法改进:原始的密度峰值聚类算法使用核函数方法来估计局部密度,但核函数的选择和参数设定可能对聚类结果产生影响。改进的方法可以尝试其他密度估计方法,例如基于距离的方法或基于概率模型的方法,以提高密度估计的准确性。

  4. 噪声处理策略:密度峰值聚类算法对于噪声点比较敏感,噪声点可能会干扰聚类结果。改进的方法可以引入噪声处理策略,例如通过设置密度阈值或使用噪声剔除算法来过滤掉噪声点,以提高聚类的准确性和鲁棒性。

  5. 并行化加速:密度峰值聚类算法的计算量较大,可以考虑使用并行计算来加速算法的执行,提高算法的效率和可扩展性。

这些是一些对密度峰值聚类算法进行改进的可能方向。具体的改进方法可以根据具体需求和数据特点来选择和调整。改进后的算法可以更好地适应不同类型的数据集,并提供更准确和稳定的聚类结果。文章来源地址https://www.toymoban.com/news/detail-751391.html

到了这里,关于密度峰值聚类(DPC)算法的介绍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • dpc++(oneAPI)调用nvidiaGPU配置与验证

    1.安装Intel® oneAPI Toolkits https://software.intel.com/content/www/us/en/develop/documentation/installation-guide-for-intel-oneapi-toolkits-linux/top.html 下载安装Base版,注意版本,尽量安装新版本 2.安装GPU驱动与CUDA https://developer.nvidia.com/cuda-downloads 建议为11.8及以上版本 nvidia-smi能出现cuda版本 Ubuntu Red Hat

    2024年02月15日
    浏览(36)
  • 电脑蓝屏解决方案:DPC WATCHDOG VIOLATION

    电脑型号:thinkbook16p 系统:win11 终止代码:DPC WATCHDOG VIOLATION 解决方案:由于每个的电脑的蓝屏问题都不一样,所以你上网参考被人的做法,99%解决不了你电脑的蓝屏问题,这里提供一种方法,进行解决。 下面是我出错的界面:   1.下载winDbg Preview  2.打开这个软件,如果你最

    2024年02月09日
    浏览(51)
  • DPC_WATCHDOG_VIOLATION蓝屏问题分析(一)

    在Windows 10之下,引入了 DPC_WATCHDOG_VIOLATION 蓝屏错误,这个错误引入的原因是为了防止内核代码处于错误状态在DPC以及以上级别执行太久,影响系统的稳定性。 对于 DPC_WATCHDOG_VIOLATION 这个蓝屏错误码,存在两种类型(使用第一个参数来区分): 第一个参数为0表示单个DPC例程执

    2024年02月04日
    浏览(45)
  • 【求助大佬】WinServer2016蓝屏DPC_WATCHDOG_VIOLATION

    最近戴尔的塔式服务器的winserver2016总是蓝屏,硬件灯显示正常。 蓝屏内容是DPC_WATCHDOG_VIOLATION  通过蓝屏分析,内容如下: Microsoft (R) Windows Debugger Version 10.0.25200.1003 AMD64 Copyright (c) Microsoft Corporation. All rights reserved. Loading Dump File [C:Users11119DownloadsMEMORY.DMP] Kernel Bitmap Dump Fil

    2024年02月07日
    浏览(44)
  • 密度聚类算法(DBSCAN)实验案例

    DBSCAN是一种强大的基于密度的聚类算法,从直观效果上看,DBSCAN算法可以找到样本点的全部密集区域,并把这些密集区域当做一个一个的聚类簇。DBSCAN的一个巨大优势是可以对任意形状的数据集进行聚类。 本任务的主要内容: 1、 环形数据集聚类 2、 新月形数据集聚类 3、

    2024年02月08日
    浏览(45)
  • 基于密度的聚类算法(1)——DBSCAN详解

    基于密度的聚类算法(1)——DBSCAN详解 基于密度的聚类算法(2)——OPTICS详解 基于密度的聚类算法(3)——DPC详解 1. DBSCAN简介 DBSCAN(Density-Based Spatial Clustering of Applications with Noise, 具有噪声的基于密度的聚类方法 )是一种典型的基于密度的空间聚类算法。和K-Means,BIR

    2024年01月24日
    浏览(45)
  • 聚类分析 | MATLAB实现基于DBSCAD密度聚类算法可视化

    效果一览 基本介绍 基于DBSCAD密度聚类算法可视化,MATLAB程序。 使用带有KD树加速的dbscan_with_kdtree函数进行密度聚类。然后,我们根据每个簇的编号使用hsv色彩映射为每个簇分配不同的颜色,并用散点图进行可视化展示。同时,我们用黑色的\\\"x\\\"标记表示噪声点。请注意,DBSC

    2024年02月11日
    浏览(38)
  • 【机器学习】机器学习上机作业聚类算法

    自编代码实现C均值聚类和FCM聚类,在“IRIS数据集(鸢尾花数据集)”上进行实验,验证所编代码是否正确,并计算准确率。 Iris鸢尾花数|据集:包含花萼长度、花萼宽度、花瓣长度、花瓣宽度四个属性,用于预测鸢尾花种类,标签0、1、2分别表示山鸢尾、变色鸢尾、维吉尼亚鸢

    2024年01月22日
    浏览(43)
  • 机器学习-10 聚类算法

    机器学习有两种学习类型: 有监督学习:即数据点有已知的结果。 无监督学习:即数据点没有已知的结果,利用无标签的数据学习数据的分布或数据与数据之间的关系被称作无监督学习。 注: ①有监督学习和无监督学习的最大区别在于数据是否有标签。 ②无监督学习最常

    2024年02月04日
    浏览(38)
  • 【机器学习】聚类算法(二)

    五、基于密度的算法 5.1 DBSCAN 算法 输出: 5.2 OPTICS算法 OPTICS 聚类算法演示 这段代码的目的是使用 OPTICS 算法对六个簇的数据进行聚类分析,并与不同的 epsilon 值的 DBSCAN 聚类进行比较。代码的主要步骤如下: 导入所需的模块,包括 matplotlib 用于绘图,numpy 用于数值计算,

    2024年02月02日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包