聚类算法Mean Shift

Mean Shift算法,一般是指一个迭代的步骤,即先算出当前点的偏移均值,然后以此为新的起始点,继续移动,直到满足一定的结束条件。

Mean Shift算法是一种无参密度估计算法或称核密度估计算法,Mean shift是一个向量,它的方向指向当前点上概率密度梯度的方向。

所谓的核密度评估算法,指的是根据数据概率密度不断移动其均值质心(也就是算法的名称Mean Shift的含义)直到满足一定条件。

mean-shift11

上图诠释了Mean Shift算法的基本工作原理,那么如何找到数据概率密度最大的区域?

数据最密集的地方,对应于概率密度最大的地方。我们可以对概率密度求梯度,梯度的方向就是概率密度增加最大的方向,从而也就是数据最密集的方向。

Mean Shift算法最常用于目标跟踪,它通过计算候选目标与目标模板之间相似度的概率密度分布,然后利用概率密度梯度下降的方向来获取匹配搜索的最佳路径,加速运动目标的定位和降低搜索的时间,因此在目标实时跟踪领域有着很高的应用价值。其优点是:

  • 由于采用了统计特征,因此对噪声有很强的鲁棒性;
  • 由于是一个单参数算法,容易作为一个模块和别的算法集成;
  • 采用核函数直方图建模,对边缘阻挡、目标的旋转、变形以及背景运动都不敏感;
  • 算法构造了一个可以用Mean Shift算法进行寻优的相似度函数。由于Mean Shift本质上是最陡下降法,因此其寻优过程收敛速度快,使得该算法具有很好的实时性。
    同时,MeanShift算法也存在着一些缺点:

  • 缺乏必要的模板更新;
  • 跟踪过程中由于窗口宽度大小保持不变,当目标尺度有所变化时,跟踪就会失败;
  • 当目标速度较快时,跟踪效果不好;
  • 直方图特征在目标颜色特征描述方面略显匮乏,缺少空间信息.

 

Mean Shift的应用

Mean Shift算法在很多领域都有成功应用,例如图像平滑、图像分割、物体跟踪等,这些属于人工智能里面模式识别或计算机视觉的部分;另外也包括常规的聚类应用。

  • 图像平滑:图像最大质量下的像素压缩;
  • 图像分割:跟图像平滑类似的应用,但最终是将可以平滑的图像进行分离已达到前后景或固定物理分割的目的;
  • 目标跟踪:例如针对监控视频中某个人物的动态跟踪;
  • 常规聚类,如用户聚类等。

下面基于Python的机器学习库SKlearn中的MeanShift演示Mean Shift算法应用。

  1. #coding:utf-8   
  2.   
  3. import numpy as np   
  4. from sklearn.cluster import MeanShift, estimate_bandwidth   
  5. from sklearn.datasets.samples_generator import make_blobs   
  6.   
  7.   
  8. # 生成样本点   
  9. centers = [[1, 1], [-1, -1], [1, -1]]   
  10. X, _ = make_blobs(n_samples=10000, centers=centers, cluster_std=0.6)   
  11.   
  12.   
  13. # 通过下列代码可自动检测bandwidth值   
  14. bandwidth = estimate_bandwidth(X, quantile=0.2, n_samples=500)   
  15.   
  16. ms = MeanShift(bandwidth=bandwidth, bin_seeding=True)   
  17. ms.fit(X)   
  18. labels = ms.labels_   
  19. cluster_centers = ms.cluster_centers_   
  20.   
  21. labels_unique = np.unique(labels)   
  22. n_clusters_ = len(labels_unique)   
  23. new_X = np.column_stack((X, labels))   
  24.   
  25. print("number of estimated clusters : %d" % n_clusters_)   
  26. print("Top 10 samples:",new_X[:10])   
  27.   
  28. # 图像输出   
  29. import matplotlib.pyplot as plt   
  30. from itertools import cycle   
  31.   
  32. plt.figure(1)   
  33. plt.clf()   
  34.   
  35. colors = cycle('bgrcmykbgrcmykbgrcmykbgrcmyk')   
  36. for k, col in zip(range(n_clusters_), colors):   
  37.     my_members = labels == k   
  38.     cluster_center = cluster_centers[k]   
  39.     plt.plot(X[my_members, 0], X[my_members, 1], col + '.')   
  40.     plt.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,   
  41.              markeredgecolor='k', markersize=14)   
  42. plt.title('Estimated number of clusters: %d' % n_clusters_)   
  43. plt.show()   


 

以下是代码执行结果

  1. number of estimated clusters : 3   
  2. ('Top 10 samples:', array(   
  3.       [[ 1.8141499 , -1.45580736,  0.        ],   
  4.        [-0.66658907, -0.29515074,  2.        ],   
  5.        [-1.49755338, -0.96610942,  2.        ],   
  6.        [ 0.34816411, -0.69885676,  0.        ],   
  7.        [ 1.80841958,  2.14678071,  1.        ],   
  8.        [ 1.02185502, -0.9430071 ,  0.        ],   
  9.        [ 1.58717372, -0.85057434,  0.        ],   
  10.        [ 2.25539903, -0.22049871,  0.        ],   
  11.        [ 0.30516472, -1.6391161 ,  0.        ],   
  12.        [ 0.49500464, -0.76833638,  0.        ]]))   


QQ截图2015052017195511
 

MeanShift可配置的参数,其中重点是bandwidth值的设置。

  1. class sklearn.cluster.MeanShift(bandwidth=None, seeds=None, bin_seeding=False, min_bin_freq=1, cluster_all=True)  


 

 


 

尾巴

在上述实现算法中,我们强调了MeanShift具有很好的实时计算性,但由于Python中的该算法中默认情况下会使用sklearn.cluster.estimate_bandwidth函数进行自动计算bandwidth值,而klearn.cluster.estimate_bandwidth的可扩展性将会成为MeanShift在大量数据集下应用实时性的瓶颈。当然,解决方法是不使用其默认的bandwidth计算函数,而自己指定一个数值,这就要求操作人员对原始数据集、算法和应用场景有比较好的先验经验,一定程度上提高的应用要求。


====================【好书推荐,我为自己代言】====================

《Python数据分析与数据化运营》第二版上市啦!

50+数据流工作知识点
14个数据分析与挖掘主题
8个综合性运营分析案例
涵盖会员、商品、流量、内容4大主题
360°把脉运营问题并贴合数据场景落地


本书主要基于Python实现,其中主要用到的计算库是numpy、pandas和sklearn,其他相关库还包括:
  • 标准库:re、time、datetime、json、 base64、os、sys、cPickle、tarfile
  • Python调用R的rpy2
  • 统计分析:Statsmodels
  • 中文处理:结巴分词
  • 文本挖掘:Gensim
  • 数据挖掘和算法:XGboost、gplearn、TPOT
  • 爬虫和解析:requests、Beautiful Soup、xml
  • 图像处理:OpenCV和PIL/Pollow
  • 数据读取:xlrd、pymongo、pymysql
  • 数据预处理:imblearn
  • 展示美化类:Matplotlib、pyecharts、graphviz、prettytable、wordcloud、mpl_toolkits、pydotplus
如果你对以下内容感兴趣,那么本书将值得一看:
  • KMeans聚类的自动K均值的确立方法
  • 基于软方法的多分类模型组合评估模型的应用
  • 基于自动下探(下钻、细分)的应用
  • 基于增量学习的多项式贝叶斯分类
  • pipeline管道技术的应用
  • 基于超参数的自动参数值的优化方法
  • 特征自动选择
  • 文本分类、文本主题挖掘
  • 基于自动时间序列ARIMA的P、D、Q的调整
  • python决策树规则输出
  • 基于自定义图像的文本标签云
  • 非结构化数据,例如图像、音频、文本等处理
  • 对象持久化处理
  • 如何使用Python调用R实现数据挖掘
  • 自动化学习:增加了对于自动化数据挖掘与机器学习的理论、流程、知识和应用库介绍,并基于TPOT做自动化回归和分类学习案例演示
有关这本书的写作感受、详细内容介绍、附件(含数据和代)下载、关键知识和方法以及完整书稿目录,请访问《Python数据分析与数据化运营》第二版出版了!要购买此书,可以去京东当当天猫等查看。

发表评论

电子邮件地址不会被公开。 必填项已用*标注