专栏首页机器学习与python集中营深入剖析Mean Shift聚类算法原理

深入剖析Mean Shift聚类算法原理

Mean Shift(均值漂移)是基于密度的非参数聚类算法,其算法思想是假设不同簇类的数据集符合不同的概率密度分布,找到任一样本点密度增大的最快方向(最快方向的含义就是Mean Shift),样本密度高的区域对应于该分布的最大值,这些样本点最终会在局部密度最大值收敛,且收敛到相同局部最大值的点被认为是同一簇类的成员。

Mean Shift在计算机视觉领域的应用非常广,如图像分割,聚类和视频跟踪,小编曾经用Mean Shift实现目标跟踪,效果还不错。本文详细的总结了Mean Shift算法原理。

目录

1.核密度估计

2.Mean Shift算法

3.图解Mean Shift算法

4.带宽对Mean Shift算法的影响

5.图像分割

6.聚类

7.Mean Shift算法优缺点

1.核密度估计

Mean Shift算法用核函数估计样本的密度,最常用的核函数是高斯核。它的工作原理是在数据集上的每一个样本点都设置一个核函数,然后对所有的核函数相加,得到数据集的核密度估计(kernel density estimation)。

假设我们有大小为n的d维数据集

,核函数K的带宽为参数h。

数据集的核密度估计:

其中K(x)是径向对称函数(radially symmetric kernels),定义满足核函数条件的K(x)为:

其中系数

是归一化常数,使K(x)的积分等于1。

如下图,我们用高斯核估计一维数据集的密度,每个样本点都设置了以该样本点为中心的高斯分布,累加所有的高斯分布,得到该数据集的密度。

其中虚线表示每个样本点的高斯核,实线表示累加所有样本高斯核后的数据集密度。因此,我们通过高斯核来得到数据集的密度。

2.Mean Shift算法

Mean Shift算法的基本目标是将样本点向局部密度增加的方向移动,我们常常所说的均值漂移向量就是指局部密度增加最快的方向。上节介绍了通过引入高斯核可以知道数据集的密度,梯度是函数增加最快的方向,因此,数据集密度的梯度方向就是密度增加最快的方向。

由上节可知,数据集密度:

上式的梯度为:

其中

,上式的第一项为实数值,因此第二项的向量方向与梯度方向一致,第二项的表达式为:

上式的含义就是本篇文章的主题:均值漂移。由上式推导可知:均值漂移向量所指的方向是密度增加最大的方向。

因此,Mean Shift算法流程为:

(1)计算每个样本的均值漂移向量

(2)对每个样本点以

进行平移,即:

(3)重复(1)(2),直到样本点收敛,即:

(4)收敛到相同点的样本被认为是同一簇类的成员

4.带宽对Mean Shift算法的影响

Mean Shift通过带宽来调节簇类的个数,本节用核概率密度的角度去理解带宽对Mean Shift算法的影响。

如下图是一维数据集的核概率密度,其中虚线表示每个样本的核函数,实线是每个样本的核函数进行叠加,表示数据集的概率密度。该数据集的概率密度只有一个局部最大值,因此,mean shift算法的簇类个数是1。

若我们设置带宽的值接近于0,那么数据集样本的核函数类似于冲激函数,如下图:

累加每个样本的核函数,得数据集的概率密度:

如上图,当带宽的值接近于0时,数据集的概率密度有5个局部最大值,mean shift算法的簇类个数是5。因此带宽决定了数据集的概率密度,进而影响了聚类结果。

5.图像分割

mean shift通过对像素空间进行聚类,达到图像分割的目的。

我们对下图进行图像分割:

我们对上图的像素点映射为RGB三维空间:

然后运行mean shift算法,使用带宽为25的高斯核,如下gif给出每个样本收敛到局部最大核密度的过程:

每个样本点最终会移动到核概率密度的峰值,移动到相同峰值的样本点属于同一种颜色,下图给出图像分割结果:

图像分割代码请参考github:

https://github.com/mattnedrich/MeanShift_py。

6.聚类

我们构建1000例4个簇类的样本数据:

#%% 产生样本数据
from sklearn.datasets import make_blobs
from itertools import cycle
from sklearn.cluster import MeanShift, estimate_bandwidth
centers = [[1, 1], [-.75, -1], [1, -1], [-3, 2]]
X, _ = make_blobs(n_samples=10000, centers=centers, cluster_std=0.6)

利用函数estimate_bandwidth估计核函数的带宽:

bandwidth = estimate_bandwidth(X, quantile=.1,n_samples=500)

运行mean shift算法,并可视化聚类结果:

8.Mean Shift算法的优缺点

优点:

不需要设置簇类的个数;

可以处理任意形状的簇类;

算法只需设置带宽这一个参数,带宽影响数据集的核密度估计

算法结果稳定,不需要进行类似K均值的样本初始化

缺点:

聚类结果取决于带宽的设置,带宽设置的太小,收敛太慢,簇类个数过多;带宽设置的太大,一些簇类可能会丢失。

对于较大的特征空间,计算量非常大。

参考:

https://spin.atomicobject.com/2015/05/26/mean-shift-clustering/

http://efavdb.com/mean-shift/

猜您喜欢

往期精选▼

1. Python 3.8 新功能大揭秘

2. 【完结】12篇文章带你逛遍主流分割网络

3.一份超详细的计算机网络基础学习指南

4.python代码调试神器PySnooper

5.基于深度学习的图像语义分割技术精度度量标准

本文分享自微信公众号 - 机器学习与python集中营(yasuozet01)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 坑爹的Python陷阱(避坑指南)

    我个人对陷阱的定义是这样的:代码看起来可以工作,但不是以你“想当然“”的方式。如果一段代码直接出错,抛出了异常,我不认为这是陷阱。比如,Python程序员应该都...

    小草AI
  • 学习笔记:深度学习中的正则化

      泛化能力强-->验证集上的误差小,训练集上的误差不大(不必追求完美,否则可能会导致过拟合)即可。

    小草AI
  • 深度学习中常用的损失函数loss有哪些?

    这是专栏《AI初识境》的第11篇文章。所谓初识,就是对相关技术有基本了解,掌握了基本的使用方法。

    小草AI
  • 集体数据欺诈的统计检测(Databases)

    统计发散在多媒体处理中被广泛应用,其主要原因是其数据显示较有规律性和有可解释的特征。然而,在更广泛的数据领域中,这些优势可能并不突出,因此需要一种更通用的方法。...

    李欣颖6837176
  • limit_area_cirle

    <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> <style>...

    前朝楚水
  • Swift3.0 - 检测API

    酷走天涯
  • 微信小程序展开全文

    设置130为临界值,是试了3行基本不超过120rpx,4行基本大于140rpx,取了个中间值

    韦弦zhy
  • 论文 | 半监督学习下的高维图构建

    磐创AI
  • SAP-采购订单常见退货处理方式

    1、 如果原采购订单没有发票校验,在原采购订单退货,要求供应商在开发票时考虑退货部分;

    用户5495712
  • 如何正确运用异步编程技术

    4.1、既然异步可以大大提供应用程序的响应能力?那么ASP.NET MVC 如果全部用异步控制器(Async Controller),会有什么效果?会成为高吞吐...

    跟着阿笨一起玩NET

扫码关注云+社区

领取腾讯云代金券