五种常见的聚类算法总结

一、关于聚类的基础描述

1.1 聚类与分类的区别

1.2 聚类的概念

1.3 聚类的步骤

二、几种常见的聚类算法

2.1 K-means聚类算法

1) K-means算法的流程：

2）K-means算法的优缺点及算法复杂度

3）K-means算法的调优与改进

4）K-means算法的python代码实现

2.2 GMM高斯混合模型聚类算法

2.3 Mean shift聚类算法

1）单点mean shift算法基本流程

2）整个数据集的meanshift聚类流程

3）meanshift聚类算法的优缺点及算法复杂度

4）meanshift在图像分割和目标跟踪领域的应用

5）单点meanshift的python代码实现

2.4 基于密度的DBSCAN聚类算法

1）DBSCAN算法的基本概念

2）DBSCAN的基本流程

3）DBSCAN的优缺点及算法复杂度

4）DBSCAN的代码实现

2.5谱聚类spectral clustering

1.1 聚类与分类的区别

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:37bb5950-1f08-4a1c-84e8-af3e6eec18eb

1.2 聚类的概念

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:16d79d8d-dff5-4807-84f1-bca2680f09ab

1.3 聚类的步骤

1.数据准备 ： 特征标准化（白化）

2.特征选择 ： 特征降维，选择最有效的特征

3.特征提取： 对选择的特征进行转换，提取出更有代表性的特征

4.聚类： 基于特定的度量函数进行相似度度量，使得同一类数据的相似度尽可能的贴近，不同类的数据尽可能分离，得到各个类的中心以及每个样本的类标签。

5.评估： 分析聚类结果，如距离误差和误差平方和（SSE）等

2.1 K-means聚类算法

1.随机选取K个中心点

2.遍历数据集里面的每个点，看距离哪个中心点最近就分为哪一类，遍历完一共K类

3.把属于一类的点取平均值，得到的平均值作为新的中心点

4.然后不断重复步骤2，3，直到达到结束条件为止。（当中心点不再变动或变动很小，当达到最大迭代次数）

优点：

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:5fc452c1-bbc0-4c87-bf75-1dc34be8b406

缺点：

k值未知，需要人为设定

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b947af38-8eef-4758-861f-78478cc1474a

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:42e92895-de46-445b-ab95-d1c69448bc0f

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:294a0f34-2f6e-41c8-9424-e2f3f7a415ad

k-means 有一个重要特征，它要求这些簇的模型必须是圆形：k-means 算法没有内置的方法
来实现椭圆形的簇

算法复杂度：

O(tkn*d) t是迭代次数，k是类数，n是数据点个数，d是数据维度

k值的选取问题，K-means++，或者先使用谱聚类或层次聚类对样本进行聚类，得到K

，或使用手肘法，遍历可能的K值，画出该点下Loss的大小，选择曲线的拐点处的K值

对于数据量大的情况，可以选择mini-batch的方法，不过准确度会下降

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:806d28b5-2889-44c7-8a8c-6ec718ac7de0

噪声影响问题，K-medoids，将步骤3改为，求一个类里面，每个点到类内其他点距离和最小的，选择它作为我们下一步的中心点，这样就有效缓解了噪声问题

import numpy as np
import random

def cal_distance(node,centor):
    return np.sqrt(np.sum(np.square(node-centor)))
def random_centor(data,k):
    data=list(data)
    return random.sample(data,k)
def random_centor1(data,k):
    n=len(data[0])#n维
    centor=np.array([[0]*n for _ in range(k)])#一定要将列表转换为数组
    for j in range(n):
        min_j=np.min(data[:,j])
        max_j=np.max(data[:,j])
        centor[:,j]=np.random.rand(k)*(max_j-min_j)+min_j
    return centor
def get_cluster(data,centor):
    cluster_dict=dict()
    k=len(centor)
    for node in data:
        cluster_class = -1
        min_distance = float('inf')
        for i in range(k):
            dist=cal_distance(node,centor[i])
            if dist0.1:
        centor=get_centor(cluster_dict,k)
        cluster_dict=get_cluster(data,centor)
        old_varience=new_varience
        new_varience=cal_varience(cluster_dict,centor)
    return cluster_dict,centor

data=np.array([[1,1,1],[2,2,2],[1,2,1],[9,8,7],[7,8,9],[8,9,7]])
a,b=k_means(data,2)
print(a,b)

2.2 GMM高斯混合模型聚类算法

2.3 Mean shift聚类算法

mean shift的本质就是中心点向着密度越来越大的地方进行偏移，最终收敛到样本密度最大的地方。它的参数R往往靠经验选取

1.随机选择一个点作为球心，半径选为R

2.以球心为起点，球内样本点为终点，将他们的向量相加后求平均，得到meanshift值

3.球心+mean shift值得到更新后的球心。

_4.不断重复23_直到球心不再移动或移动微小

1.在未被标记的数据点中随机选择一个点作为原始中心点

2.找出以中心点为球心，半径为R的球体中所有数据点，认为他们为聚类C，同时在C类中记录这些数据点出现的次数+1

3.以球心为起点，球内样本点为终点，将他们的向量相加后求平均，得到meanshift值

4.球心+meanshift的值，得到更新后的球心

5.重复234直到meanshift很小或者不移动，记录下此时的中心点，注意迭代过程中遇到的点都应该归类到C

6.判断收敛时的C类中心点与其他已经存在的类的中心点距离是否小于阈值，如果小于就把他们合并，数据点出现的次数也应该合并，如果大于，就把C当作一个新的聚类

7.重复123456直到所有点都被标记为已访问

8.对每个点，哪个类访问次数最多，就归属于哪个类。

优点：可以自动确定类的个数

对噪声比较强壮

参数简单

缺点：容易陷入局部最优

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e4eef45f-fadd-46eb-a0f2-c27d75c9496d

算法复杂度：

O(Tnlog(n)) T是迭代中选取的中心点数。

这里首先说一下，在之前的meanshift里面我们都没有讨论核函数，因为是学习基础概念，所以没必要搞太复杂，但是实际应用中，在球体内，离的远的点和离得进的点对于球心的影响权重是一样的，这显然不合理。所以引入了核函数和权重系数。核函数也叫窗口函数，在核估计中起到平滑的作用。常用的核函数有：Uniform，Epannechnikov，Gaussian等。同时在图像的处理中，一般不是球体，而是矩形。

meanshift在图像分割中的步骤：

1.将图像表示为空间中的点，一种简单的方法就是使用红绿蓝像素值，将每个像素映射到三维RGB空间中的一个点

2.对获取的点集进行meanshift聚合，一般使用高斯核函数。

3.不同的集合就构成了图像分割

meanshift在目标追踪中的步骤：

1.用运动检测算法将物体与背景分割开来

2.提取运动物体的轮廓，并从原图中获取运动图像信息

3.对这个信息进行反向投影，获取反向投影图

4.根据反向投影图和输入的方框进行meanshift迭代，迭代中会向反向投影图中概率大的地方移动，所以始终会移动到目标上

5.下一帧的图像时用上一帧输出的方框来迭代即可。

meanshift用于视频目标追踪，其实就是采用目标的颜色直方图作为搜索特征，将目标区域转化成HSV颜色空间，然后得到H的分布直方图，有了它之后，我们就是要在下一帧里面得到相同的它，这时我们采用相似函数来表述他们的相似性，让方框在最新一帧中向着相似度最大的区域移动。

meanshift在目标追踪中的优点：

1.算法计算量不大，在目标区域已知的情况下效果很好

2.采用核函数直方图模型，对边缘遮挡，目标旋转等不是很敏感

缺点：

1.目标速度太快效果不好

2.如果运动中目标被遮挡，跟踪就会失败。

import numpy as np

def load_data():
    #dtype如果不设置默认为float，comments是指如果该行以'#'开头，那么就跳过，usecols是指只使用0，2两列。unpack如果为True，则把0，2两列单独输出，skiprows是指跳过第一行
    data=np.loadtxt('data/meanshift.txt', dtype=int, comments='#', delimiter=None, skiprows=1, usecols=(0,2), unpack=False)
    return np.array(data)

class MeanShift:
    def __init__(self,mean,radius):
        self.mean=mean
        self.radius=radius

    def compute_distance(self,data):
        return np.sqrt(np.sum(np.square(data-self.mean),axis=1))

    def in_ball(self,data):
        distance=self.compute_distance(data)
        inball_index=np.argwhere(distance

2.4 基于密度的DBSCAN聚类算法

DBSCAN是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇，并可以在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

参数：半径和min_point

选择技巧：一般先选一个点，计算它与其他所有点的距离，然后排序，找到前后变化很大的一处，然后R就选则突变点即可。这个选的太大，簇就少，选的太小，簇就多，可以适当调整

min_point一般这个值都偏小，可以多次尝试一下。

1.把所有点标记为未见

2.随机在数据集中选择一个未标记点P，找到它的邻域R

3.判断R里面包含的样本点个数是否大于min_point,如果小于，则为噪声点，标记为已见，如果大于，则P为核心点，创建一个类C，邻域R里面的点都属于类C，如果邻域R内除了P还有其他核心点。则他们邻域里面的点也属于类C，一直迭代，直到核心点邻域里只有它自己为核心点才停止。

4.从数据集中移除C类，重复执行234，直到所有的点都是已标记为止。

优点：

1.可以自动决定类的数量。不需要人为假设。

2.可以发现任意形状的簇类，而不像K-means那样只能发现圆形簇

3.可以识别噪声点，抗噪声能力较强

缺点：

1.不能很好的应用在高维数据中

2.如果样本集的密度不均匀，效果就不好

算法复杂度：

O(nlog(n))n是数据点个数

import numpy as np
#如果是列表这里就不能这样计算，data1-data2是不合法的
def cal_distance(data1,data2):
    data1=np.array(data1)
    data2=np.array(data2)
    return np.sqrt(np.sum(np.square(data1-data2)))
#pop()按照索引删除，del也是按照索引删除，remove是按照值删除,
def DBSCAN(data,r,min_point):
    #第一步将数据中的核心点找出来放入q
    q=[]
    for i in range(len(data)):
        count=0
        for j in range(len(data)):
            if cal_distance(data[i],data[j]) < r:
                count+=1
        if count>=min_point:
            q.append(data[i])
    c=[[] for _ in range(len(q))]
    #对整个数据集进行分类，属于哪个关键点就分配进去，最终data里面不为0的就是噪声点
    for i in range(len(q)):
        for j in range(len(data)):
            if data[j]!=0 and cal_distance(q[i],data[j])=len(q):
            break
        q=q[i:]
        d.append(c[:i])
        c=c[i:]
    d.append(c[:i])
    return d,noise

class_res,noise=DBSCAN([[1,2,3],[4,5,6],[7,8,9]],1,1)
print(class_res,noise)
import numpy
#
a=[1,2,3]
print(a!=0)只返回一个True或False
a=numpy.array([1,2,3])
print(a!=0)返回n个True或False
#如果要计算两个点之间的欧式距离，一定要将列表转为array再计算。因为列表不支持a-b

2.5谱聚类spectral clustering

Original: https://blog.csdn.net/slamer111/article/details/126545264
Author: CVplayer111
Title: 五种常见的聚类算法总结