岁虚山

行有不得，反求诸己

0%

Meanshift 聚类算法

发表于 更新于 分类于 >

简介

聚类分析，又称群分析，指对样本数据的一种划分与归类的一种方法。聚类算法以相似性为基础，将样本数据中按照相似度不同分成不同的族群（类别）中。同一族群中，样本相似性相差小；不同族群中，样本相似性差异较大。

Meanshift，又称均值漂移算法，是一种基于核密度的估计算法，将每个族群的中心点移动到该族群的密度最大的位置，来对样本进行分类。

相较于其他分类算法，$Meanshift$ 不需要指定分类的族群数量，而是根据样本特性自动生成不同类别的族群。其广泛应用于聚类、图像平滑、分割、跟踪等方面。

本文以聚类为例，探讨 $Meanshift$ 的原理及实现。

推导

假设在给定的 $d$ 维空间中 $N$ 个样本数据点集 $X$，那么对于空间中的任意点 $x$ 的 $mean shift$ 向量的基本形式可以表示为：

其中， $S_k$ 为数据集中的点 $x_i$ 到点 $x$ 的距离小于 $d$ 维球半径的 $r$ 的数据点，既：

而漂移的过程，就是不断计算漂移向量，然后更新球心位置，更新公式为：

简例

我们以二维平面上的点为例（空间维度 $d = 2$）：

如上图所示，平面上散布着 $200$ 个点，以半径 $r = 0.3$ 进行更新漂移量 $M$ 的值，其过程如下：

原理其实十分简单：

1、在散点中随机选取一点，作为中心点；

2、遍历所有的点，将距离中心点距离小于半径 $r$ 的点记录到一个集合中；

3、计算上一步所得到的集合中的所有点与原中心点的位置偏差的平均值；

4、将中心点加上上一步中计算出的平均偏移量，更新为新的中心点；

5、重复2 - 4步，直到新的中心点与旧的中心点的位置距离小于某个阈值（位置更新幅度极小）；

简单来看，就是不断更新类别的中心的位置，使得其不断朝向密度更高的地方移动，直到移动幅度达到某个很小的阈值，则认为最终的位置就是类别的中心点（密度最大的地方）。

接下来，让我们实现 $Meanshift$ 算法的代码。

引用 Python 相关依赖库：

1
2
3
4
5
6
7
import matplotlib
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np
import random
import math
from sklearn.datasets import make_blobs

计算两点之间的欧氏距离：

1
2
def Distance(sample1, sample2):
    return math.sqrt(pow(sample1[0] - sample2[0], 2) + pow(sample1[1] - sample2[1], 2))

创建样本数据集：

1
2
sampleCenters = [[0, 0]]    #生成样本数据的中心点
samples, _ = make_blobs(n_samples = 200, centers = sampleCenters, cluster_std = 0.5)

$Meanshift$ 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def Meanshift(samples, r):
    clusterCenter = samples[random.randint(0, len(samples) - 1)] 
    #随机选择样本中的一个数据点作为样本中心点

    while True:
        meanshiftVector = [0, 0]    #中心点的移动向量
        counts = 0

        for i in range(len(samples)):
            if Distance(clusterCenter, samples[i]) < r:          #遍历样本点，寻找在中心点半径为 r 的范围内的点
                meanshiftVector += samples[i] - clusterCenter    #计算该点相对于中心点的偏移量
                counts += 1

        clusterCenter += meanshiftVector / counts       #更新中心点的位置

        if Distance(meanshiftVector, [0, 0]) < 1e-5:    #判断偏移量的大小，当偏移量小于一定阈值后，结束循环
            break

    return clusterCenter

以上就是最简单的能够展示 $Meanshift$ 原理的代码。

$Meanshift$ 示例

在上面简单的例子中，我们已经实现了 $Meanshift$ 的基本原理的代码示例。但是，以上的示例只是作为演示 $Meanshift$ 算法的思想，真正的 $Meanshift$ 算法要比上述例子稍微复杂一点。

其原理如下：

1、遍历样本点，选择一点 $S_i \ (Sample \ \ i)$ 作为中心点 $C_i \ (Center \ \ i)$ ，将其单独作为一个类别 $Clu_i \ \ (Cluster \ \ i)$；

2、遍历剩余的样本点，将所有距离中心点距离小于半径 $r$ 的记录到一个临时的集合 $Set_{tmp}$ 中；

3、通过临时集合中的样本点计算 $meanshift$ 漂移向量 $V_{m}$，将漂移向量加到中心点上：

4、重复 2 - 3 步的过程，当 $meanshift$ 漂移向量 $V_m$ 小于阈值，或者中心点偏移后与第 1 步中选择的样本点的距离大于半径 $r$ 即：

时结束重复，并将此时第 2 步中得到的临时样本点集合 $Set_{tmp}$ 添加到类别 $Clu_i$ 中。

5、遍历样本类别集合 $Set{clu}$ ，判断新的到的 $Clu_i$ 与 $Set{clu}$ 中的各类别是否存在相等或者包含关系，若存在包含关系，则根据包含关系对相应的类别进行更新，若不存在相等或者包含关系，则将 $Clui$ 添加到 $Set{clu}$ 中；

6、重复第1～5步，直到遍历完成所有样本点；

7、以上进行的分类中，或许有样本点被包含在多个类别中，因此还需遍历样本点，并针对该样本点，找到所有包含此样本点的类别，将该样本点划分至距离最近的类别中。

下面是仍以二维平面上的点为例（空间维度 $d = 2$），进行代码的实现：

创建相关的数据结构：

1
2
3
4
5
6
7
8
9
10
11
#创建样本点数据结构体
class Sample():
    def __init__(self, tag, data):
        self.tag = tag      #样本标签
        self.data = data    #样本数据(2维数据)

#创建分类结构体
class Cluster():
    def __init__(self):
        self.data = []    #该类别的数据(2维数据)
        self.tagSet = []

计算两点之间的欧式距离：

1
2
def Distance(sample1, sample2):
    return math.sqrt(pow(sample1[0] - sample2[0], 2) + pow(sample1[1] - sample2[1], 2))

创建样本数据集：

1
2
3
4
5
6
sampleCenters = [[0, 0], [1, 3], [-2, 4], [-2, 3]]
sampleDatas, _ = make_blobs(n_samples = 2000, centers = sampleCenters, cluster_std = 0.5)

samples = []
for i in range(len(sampleDatas)):
    samples.append(Sample(i, sampleDatas[i]))

Meanshift：

1
a = 10

X 表示一个d维的欧式空间，x 是该空间中的一个点$x = {x_1,x_2,x_3\cdots ,x_d}$，其中，x的模$| x |^2=xx^T$，R表示实数域，如果一个函数K:X→R存在一个剖面函数k:[0,∞]→R，即

并且满足：

  • k是非负的
  • k是非增的
  • k是分段连续的

那么，函数K(x)就称为核函数。

-------------本文结束 感谢阅读-------------
打赏一包辣条