【機(jī)器學(xué)習(xí)】Mean Shift原理及代碼

Mean Shift (均值漂移)是基于密度的非參數(shù)聚類(lèi)算法,其算法思想是假設(shè)不同簇類(lèi)的數(shù)據(jù)集符合不同的概率密度分布,找到任一樣本點(diǎn)密度增大的最快方向(最快方向的含義就是Mean Shift) ,樣本密度高的區(qū)域?qū)?yīng)于該分布的最大值,這些樣本點(diǎn)最終會(huì)在局部密度最大值收斂,且收斂到相同局部最大值的點(diǎn)被認(rèn)為是同一簇類(lèi)的成員。

均值漂移聚類(lèi)的目的是發(fā)現(xiàn)一個(gè)平滑密度的樣本點(diǎn)。它是一種基于質(zhì)心的算法，其工作原理是將質(zhì)心的候選點(diǎn)更新為給定區(qū)域內(nèi)的點(diǎn)的平均值。然后在后處理階段對(duì)這些候選點(diǎn)進(jìn)行過(guò)濾，以消除近似重復(fù)點(diǎn)，形成最終的一組質(zhì)心。給定一個(gè)候選質(zhì)心xi和迭代次數(shù)t，按照以下的等式進(jìn)行更新:

  其中N(xi)是在xi周?chē)o定距離內(nèi)的樣本的鄰域，m是針對(duì)指向點(diǎn)密度最大增長(zhǎng)區(qū)域的每個(gè)質(zhì)心計(jì)算的平均位移向量。使用以下公式進(jìn)行計(jì)算，能有效地更新一個(gè)質(zhì)心為其鄰域內(nèi)樣本的平均值:

Mean Shift算法的流程可被理解為：

1. 計(jì)算每個(gè)樣本的平均位移

2. 對(duì)每個(gè)樣本點(diǎn)進(jìn)行平移

3. 重復(fù)（1）（2），直到樣本收斂

4. 收斂到相同點(diǎn)的樣本可被認(rèn)為是同一簇類(lèi)的成員
   ## Mean Shift算法的優(yōu)缺點(diǎn)
   不需要設(shè)置簇的個(gè)數(shù)也可以處理任意形狀的簇類(lèi)，同時(shí)算法需要的參數(shù)較少，且結(jié)果較為穩(wěn)定不需要像K-means的樣本初始化。但同時(shí)Mean Shift對(duì)于較大的特征空間需要的計(jì)算量非常大，而且如果參數(shù)設(shè)置的不好則會(huì)較大的影響結(jié)果，如果bandwidth設(shè)置的太小收斂太慢，而如果bandwidth參數(shù)設(shè)置的過(guò)大，一部分簇則會(huì)丟失。

在Sklearn中實(shí)現(xiàn)了MeanShift算法，其算法使用方法如下：

sklearn.cluster.MeanShift(*, bandwidth=None, seeds=None, bin_seeding=False, min_bin_freq=1, cluster_all=True, n_jobs=None, max_iter=300)

其中最主要的參數(shù)是bandwidth，這個(gè)參數(shù)是用于RBF kernel中的帶寬。參數(shù)seeds是用于初始化核的種子，如果不指定則會(huì)使用sklearn.cluster.estimate_bandwidth進(jìn)行估計(jì)。
使用示例：

from sklearn.cluster import MeanShift  
import numpy as np  
X = np.array([[1, 1], [2, 1], [1, 0],  
              [4, 7], [3, 5], [3, 6]])  
clustering = MeanShift(bandwidth=2).fit(X)

# 導(dǎo)入相關(guān)模塊和導(dǎo)入數(shù)據(jù)集
import numpy as np
from sklearn.cluster import MeanShift, estimate_bandwidth
from sklearn.datasets import make_blobs
# 生成樣本數(shù)據(jù)
centers = [[1, 1], [-1, -1], [1, -1]]
X, _ = make_blobs(n_samples=10000, centers=centers, cluster_std=0.6)
es_bandwidth = estimate_bandwidth(X,quantile=0.2, n_samples= 500)
'''
estimate_bandwidth()用于生成mean-shift窗口的尺寸，
其參數(shù)的意義為：從X中隨機(jī)選取500個(gè)樣本，
計(jì)算每一對(duì)樣本的距離，然后選取這些距離的0.2分位數(shù)作為返回值
'''
MS = MeanShift(bandwidth=es_bandwidth)
MS.fit(X)
labels = MS.labels_
cluster_centers = MS.cluster_centers_
uni_labels = np.unique(labels)
n_clusters_ = len(uni_labels)
import matplotlib.pyplot as plt
from itertools import cycle
# 對(duì)算法聚類(lèi)結(jié)果進(jìn)行可視化
colors = cycle('bgrcmykbgrcmykbgrcmykbgrcmyk')
for k, col in zip(range(n_clusters_), colors):
    my_members = labels == k
    cluster_center = cluster_centers[k]
    plt.plot(X[my_members, 0], X[my_members, 1], col + '.')
    plt.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,
             markeredgecolor='k', markersize=14)
plt.show()

Mean Shift是聚類(lèi)中常見(jiàn)的算法，以下展示了該算法在實(shí)際中的部分應(yīng)用：

1. 簡(jiǎn)單聚類(lèi)

mean shift用于聚類(lèi)就有些類(lèi)似于密度聚類(lèi)，從單個(gè)樣本點(diǎn)出發(fā)，找到其對(duì)應(yīng)的概率密度局部極大點(diǎn)，并將其賦予對(duì)應(yīng)的極大點(diǎn)，從而完成聚類(lèi)的過(guò)程

2. 圖像分割

圖像分割的本質(zhì)也是聚類(lèi)，不過(guò)相對(duì)與簡(jiǎn)單聚類(lèi)，圖像分割又有其特殊性。mean shift通過(guò)對(duì)像素空間進(jìn)行聚類(lèi),達(dá)到圖像分割的目的。

3. 圖像平滑

圖像平滑和圖像分割有異曲同工之妙，同樣是對(duì)每一個(gè)像素點(diǎn)尋找其對(duì)應(yīng)的概率密度極大點(diǎn)，主要區(qū)別在于：
a. 迭代過(guò)程不用深入，通常迭代一次即可；
b. 找到概率密度極大點(diǎn)后，直接用其顏色特征覆蓋自身的顏色特征。

4. 輪廓提取

同樣，輪廓提取與圖像分割也是類(lèi)似的，或者具體地說(shuō)，輪廓提取可以基于圖像分割進(jìn)行。首先使用mean shift 算法對(duì)圖像進(jìn)行分割，然后取不同區(qū)域的邊緣即可得到簡(jiǎn)單的輪廓

- EOF -

往期精彩回顧




適合初學(xué)者入門(mén)人工智能的路線及資料下載
(圖文+視頻)機(jī)器學(xué)習(xí)入門(mén)系列下載
機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印
《統(tǒng)計(jì)學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專(zhuān)輯
機(jī)器學(xué)習(xí)交流qq群955171419，加入微信群請(qǐng)掃碼