正文 

当前位置： 首页 > java > java教程

k均值聚类和dbscan介绍(代码片段)

sunwq06 sunwq06     2022-12-09     237

关键词：

K均值（K-means）聚类

问题定义：给定数据$\\vecx_1,\\vecx_2,\\cdots,\\vecx_n$，将它们分到不同的$K$个簇（cluster）中。定义$\\vecc=(c_1,c_2,\\cdots,c_n),\\text c_i\\in\\1,2,\\cdots,K\\$，$c_i=k$表示$\\vecx_i$被分到了第$k$个簇中。定义$\\vec\\mu_k$为第$k$个簇的中心（centroid），$k=1,2,\\cdots,K$。K-means是一种基于距离的聚类算法，它的目标函数可以写为$$argmin_\\vecc,\\vec\\mu_1,\\cdots,\\vec\\mu_K\\sum\\limits_i=1^n\\sum\\limits_k=1^KI(c_i=k)\\lVert\\vecx_i-\\vec\\mu_k\\rVert_2^2$$

求解：使用坐标下降（Coordinate Descent）方法进行求解，将待求解的参数分为两个集合：$\\vecc$以及$(\\vec\\mu_1,\\cdots,\\vec\\mu_K)$。

  1. 随机初始化$K$个簇的中心$(\\vec\\mu_1,\\cdots,\\vec\\mu_K)$
  2. 固定$(\\vec\\mu_1,\\cdots,\\vec\\mu_K)$，找到最优的$c_i,i=1,2,\\cdots,n$：$c_i=argmin_k\\in\\1,2,\\cdots,K\\\\lVert\\vecx_i-\\vec\\mu_k\\rVert_2^2$
  3. 固定$\\vecc$，找到最优的$(\\vec\\mu_1,\\cdots,\\vec\\mu_K)$：$\\vec\\mu_k=\\frac1\\sum\\limits_i=1^nI(c_i=k)\\sum\\limits_i=1^nI(c_i=k)\\vecx_i$
  4. 不断迭代第2步和第3步，直到收敛为止

由于目标函数是非凸的，因此最后的结果可能是局部最优值，实际应用时一般会运行多次上述求解过程（即对$(\\vec\\mu_1,\\cdots,\\vec\\mu_K)$进行多次随机初始化），并选择使最终目标函数最小的那个结果。

DBSCAN

DBSCAN是一种基于密度的聚类方法，它不需要预先指定簇的个数，但需要给定两个参数：MinPts以及eps，具体算法如下：

技术图片 
import numpy
def MyDBSCAN(D, eps, MinPts):
    """
    Cluster the dataset `D` using the DBSCAN algorithm.
   
    It will return a list of cluster labels. The label -1 means noise, and then
    the clusters are numbered starting from 1.
    """     
    labels = [0]*len(D) #Initially all labels are 0,  0 means the point hasn‘t been considered yet     
    C = 0 #C is the ID of the current cluster.   
    ### This outer loop is just responsible for picking new seed points--a point
    ### from which to grow a new cluster.
    for P in range(0, len(D)):
        if not (labels[P] == 0): continue
        NeighborPts = regionQuery(D, P, eps) #Find all of P‘s neighboring points.
        if len(NeighborPts) < MinPts: 
            labels[P] = -1        
        else: 
            C += 1
            labels[P] = C #the label to our seed point.
            growCluster(D, labels, P, C, eps, MinPts) #Grow the cluster from the seed point.
    return labels

def growCluster(D, labels, P, C, eps, MinPts):
    """
    Grow a new cluster with label `C` from the seed point `P`.
    
    This function searches through the dataset to find all points that belong
    to this new cluster. When this function returns, cluster `C` is complete.
    """
    ### SearchQueue is a FIFO queue of points to evaluate. It will only ever 
    ### contain points which belong to cluster C
    SearchQueue = [P]
    i = 0
    while i < len(SearchQueue):      
        P = SearchQueue[i]
        NeighborPts = regionQuery(D, P, eps) #Find all the neighbors of P
        ### If the number of neighbors is below the minimum, then 
        ### move to the next point in the queue.
        if len(NeighborPts) < MinPts:
            i += 1
            continue
        ### Otherwise, For each of the neighbors...
        for Pn in NeighborPts:
            ### If Pn was labelled NOISE, claim it as part of cluster C
            if labels[Pn] == -1:
               labels[Pn] = C #Add Pn to cluster C
            ### Otherwise, if Pn hasn‘t been considered yet, claim it as part of
            ### C and add it to the search queue.   
            elif labels[Pn] == 0:
                labels[Pn] = C #Add Pn to cluster C
                SearchQueue.append(Pn) #Add Pn to the SearchQueue
        i += 1  #Advance to the next point in the queue.               
    return 

def regionQuery(D, P, eps):
    """
    Find all points in dataset `D` within distance `eps` of point `P`.
    
    This function calculates the distance between a point P and every other 
    point in the dataset, and then returns only those points which are within a
    threshold distance `eps`.
    """
    neighbors = []  
    for Pn in range(0, len(D)):        
        if numpy.linalg.norm(D[P] - D[Pn]) < eps:
           neighbors.append(Pn)
    return neighbors
View Code

代码部分主要参考了文章DBSCAN Clustering Tutorial。若最终有数据点未被分到任何簇中（噪音点），则可将这些点视为异常点。下图分别是K均值算法以及DBSCAN算法对一个数据集的聚类结果，可以看出相比于K均值算法，DBSCAN算法可以有任意形状的簇，并且找到了数据中的异常点（右图中的空心点）。在实际应用中应对MinPts以及eps这两个参数仔细加以调试，特别是eps在不同的数据集中变化较大，具有较大的调试难度。

 技术图片

DBSCAN的一个改进算法为HDBSCAN，它也是一种基于密度的聚类方法，主要有两个参数$k$(也可记为$min\\_samples$)以及$min\\_cluster\\_size$。DBSCAN通过一个数据点$\\vecx$的半径为eps的邻域内是否有至少MinPts个点来判定该点是局地稠密还是稀疏的；而HDBSCAN通过一个数据点$\\vecx$距它的第$k$个近邻点的距离$core_k(\\vecx)$来定量表征该点的局地密度，显然距离越大局地密度越小，在此基础上定义两个数据点之间的距离为：$$d(\\vecx_1,\\vecx_2)=\\max(core_k(\\vecx_1),core_k(\\vecx_2),\\lVert\\vecx_1-\\vecx_2\\rVert_2)$$

  • 以该距离为基础，建立如下面左图所示的Dendrogram树状结构图。该图等价于层次聚类中的single-linkage，即两个簇$X$和$Y$之间的距离可以表示为$d(X,Y)=\\min\\limits_\\vecx\\inX,\\text \\vecy\\inYd(\\vecx,\\vecy)$。
  • 为了得到更稳健的聚类结果，HDBSCAN规定若每次分裂分出的两个新簇中有一个簇中的数据点个数小于$min\\_cluster\\_size$，则不进行这次分裂，只是将不满足要求的新簇中的点从之前的簇中移出，直到分裂出的两个新簇中的数据点个数均大于$min\\_cluster\\_size$再进行分裂，得到的结果如下图中的右图所示（簇的宽度表示簇中数据点的个数，簇的长度表征簇的存在周期。纵坐标$\\lambda$定义为距离的倒数，即$\\frac1distance$）。

技术图片

  • 对任一个簇，将该簇的重要性定义为该簇在右图中所占面积。定义$\\lambda_birth$为该簇生成时对应的$\\lambda$，$\\lambda_p$为该簇中的点$p$最后停留在该簇（即分裂到新簇之前或者被移出去之前）时对应的$\\lambda$，则该簇的重要性用数学公式可表示为$\\sum\\limits_p\\incluster(\\lambda_p-\\lambda_birth)$。
  • 接下来还剩最后一个要解决的问题，即如何从右图的树状结构中选择最终的簇（右图中圈出的簇为最终选择的簇）。选择最终的簇的过程类似于决策树中的剪枝过程，从最底端开始，若两个子簇的重要性之和大于它们上一级的簇的重要性，则用这两个子簇以及它们的重要性之和代替它们上一级的簇以及上一级簇的重要性，否则删除这两个子簇，重复此过程直到最顶层，最终剩下的簇即为算法最终选择的簇。
  • 同DBSCAN类似，最终未被分配到任何簇中的点可视为数据集中的异常点。HDBSCAN算法的主页为The HDBSCAN Clustering Library，一个较为详细的介绍视频链接为HDBSCAN, Fast Density Based Clustering, the How and the Why。

kmeans和dbscans将相邻的轮廓聚类(代码片段)

...矩形框里的矩形框消失。 ​聚类算法： K-Means算法k均值聚类算法（k-meansclusteringalgorithm）是一种迭代求解的聚类分析算法，其步骤是，预将数据分为K组，则随机选取K个 查看详情

dbscan与kmeans，optics区别？

参考技术ADBSCAN和Kmeans的区别：1)K均值和DBSCAN都是将每个对象指派到单个簇的划分聚类算法，但是K均值一般聚类所有对象，而DBSCAN丢弃被它识别为噪声的对象。2)K均值使用簇的基于原型的概念，而DBSCAN使用基于密度的概念。3)K均... 查看详情

人工智能|k-means聚类算法均值偏移聚类算法dbscan聚类算法使用高斯混合模型（gmm）的期望最大化（em）聚类合成聚类

5种流行的聚类算法以及它们的优缺点。本文参考AiTechYunK-MEANS聚类算法K-Means聚类算法可能是大家最熟悉的聚类算法。它出现在很多介绍性的数据科学和机器学习课程中。在代码中很容易理解和实现！请看下面的图表。K-Means聚... 查看详情

python，opencv中的k均值聚类——k-meanscluster(代码片段)

Python，OpenCV中的K均值聚类1.效果图2.原理2.1什么是K均值聚类？2.2K均值聚类过程2.3cv2.kmeans(z,2,None,criteria,10,flags)3.源码3.1抽样生成点后聚类3.2单特征聚类、多特征聚类、颜色量化参考这篇博客将介绍什么是K-Means聚类以及如... 查看详情

dbscan聚类算法的实现(代码片段)

DBSCAN聚类算法的实现1.作者介绍2.关于理论方面的知识介绍2.1DBSCAN算法介绍2.2鸢尾花数据集介绍3．实验过程3.1实验代码3.2实现过程3.3实验结果4．参考文献1.作者介绍刘鹏程，男，西安工程大学电子信息学院，202... 查看详情

k均值聚类(代码片段)

目录一.k均值简介二.应用简介三.算法四.选择合适的K五.具体实例   一.k均值简介　　K均值聚类是一种无监督学习，对未标记的数据（即没有定义类别或组的数据）进行分类。 该算法的目标是在数据中找到由变量K... 查看详情

聚类--k均值算法(代码片段)

聚类--K均值算法：自主实现与sklearn.cluster.KMeans调用  1.用python实现K均值算法K-means是一个反复迭代的过程，算法分为四个步骤:（x,k,y)importnumpyasnpx=np.random.randint(1,50,[20,1])y=np.zeros(20)k=3#选取数据空间中的K个对象作为初始中心... 查看详情

机器学习---聚类算法(代码片段)

...合聚类BIRCH聚类DBSCAN【本人的毕业设计系统中有用到】K-均值高斯混合模型【写在最后】【写在前面】sklearn和scikit-learn：scikit-learn是下载下来的工具，sklearn是在python调用包时候的缩写。聚类的定义：是在特征空间的输... 查看详情

⭐k-means和dbscan聚类算法——理论结合代码的实现(代码片段)

文章目录一、基本概念二、K-Means2.1基本步骤与流程2.2代码实现2.2.1手写python代码实现2.2.2算法优化2.2.2.1多次随机初始化2.2.2.2使用肘部法则确定k2.2.3sklean中的kmeans2.2.3.1肘部法则优化k2.2.3.2轮廓系数2.2.4MiniBatchKMeans三、DBSCAN（基... 查看详情

⭐k-means和dbscan聚类算法——理论结合代码的实现(代码片段)

文章目录一、基本概念二、K-Means2.1基本步骤与流程2.2代码实现2.2.1手写python代码实现2.2.2算法优化2.2.2.1多次随机初始化2.2.2.2使用肘部法则确定k2.2.3sklean中的kmeans2.2.3.1肘部法则优化k2.2.3.2轮廓系数2.2.4MiniBatchKMeans三、DBSCAN（基... 查看详情

聚类--k均值算法(代码片段)

 1.用python实现K均值算法K-means是一个反复迭代的过程，算法分为四个步骤：importnumpyasnpx=np.random.randint(1,50,[20,1])y=np.zeros(20)k=3#1）选取数据空间中的K个对象作为初始中心，每个对象代表一个聚类中心；definitcen(x,k):returnx[:k]#2）... 查看详情

聚类--k均值算法(代码片段)

importnumpyasnpfromsklearn.datasetsimportload_irisiris=load_iris()x=iris.data[:,1]y=np.zeros(150)definitcenter(x,k):#初始聚类中心数组returnx[0:k].reshape(k)defnearest(kc,i):#数组中的值，与聚类中心最小距离所在类别的索引号d=(abs(kc-i 查看详情

k-均值聚类算法(代码片段)

一．k均值聚类算法对于样本集。"k均值"算法就是针对聚类划分最小化平方误差： 其中是簇Ci的均值向量。从上述公式中可以看出，该公式刻画了簇内样本围绕簇均值向量的紧密程度，E值越小簇内样本的相似度越高。 k-mea... 查看详情

关于聚类模型的一些理解和总结(代码片段)

...09;，导入Excel的数据→点击“分析”→分类→点击“K-均值聚类”（SPSS里的K-均值聚类默认就是K-means++算法） 查看详情

聚类算法（k-means&agnes&dbscan）(代码片段)

一、聚类算法基本概念1.定义：聚类就是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大。即聚类后同一类的数据尽可能聚集到一起，不同数据尽量分... 查看详情

备战数学建模44-聚类模型(攻坚站8)(代码片段)

“物以类聚，人以群分”，所谓的聚类，就是将样本划分为由类似的对象组成的多个类的过程。聚类后，我们可以更加准确的在每个类中单独使用统计模型进行估计、分析或预测；也可以探究不同类之间的相... 查看详情

05_无监督学习--聚类模型--k均值(代码片段)

无监督学习--聚类模型--K均值0.引入依赖1.数据的加载和预处理2.算法实现3.测试无监督学习--聚类模型--K均值0.引入依赖import numpy as npimport matplotlib.pyplot as plt# 这里直接 sklearn 里的数据集from skl... 查看详情

R中DBSCAN的聚类中心平均值？

】R中DBSCAN的聚类中心平均值？【英文标题】：ClustercentermeanofDBSCANinR?【发布时间】：2011-12-2318:55:51【问题描述】：在包fpc中使用dbscan我可以获得以下输出：dbscanPts=322MinPts=20eps=0.00501seed0233border872total87235但我需要找到聚类中心（具... 查看详情