Mean-shift又稱均值遷移算法，它是指在數(shù)據(jù)集中選定一個(gè)點(diǎn)，然后以這個(gè)點(diǎn)為圓心，為半徑，畫一個(gè)圓(二維下是圓)，求出這個(gè)圓內(nèi)圓心到其他點(diǎn)的向量的平均值，而圓心與向量均值的和為新的圓心，然后迭代此過程，直到滿足一點(diǎn)的條件結(jié)束。

Mean-shift向量計(jì)算公式為：

其中多維圓定義：

圖解過程：

    基本形式中隱含了在有效區(qū)域中對(duì)所有的樣本點(diǎn)一視同仁的假設(shè)，但這通常是不成立，最常見的就是隨著距離的增加，作用就越小，因此，就有了如下的改進(jìn)形式：

其中

    核密度估計(jì)首先是密度估計(jì)，如果要估計(jì)一個(gè)點(diǎn) x 對(duì)應(yīng)的概率密度，那么在 x 附近劃定一個(gè)體積 d， 數(shù)一下在 d 里面的點(diǎn)的個(gè)數(shù) n，n/d 就是 x 的密度 f(x) 的一個(gè)估計(jì)。但這樣只利用到 d 體積內(nèi)的點(diǎn)，如果我們把 d 內(nèi)的點(diǎn)的個(gè)數(shù) n 的計(jì)數(shù)方法改變一下，比如，我們認(rèn)為：離 x 越近，越應(yīng)該計(jì)入在 d 空間內(nèi)，于是我們用一個(gè)函數(shù) K(xi-x)來衡量應(yīng)不應(yīng)該計(jì)入的概率。顯然 xi = x 的時(shí)候應(yīng)該計(jì)入，xi - x 無(wú)窮大的時(shí)候不應(yīng)該計(jì)入。那我們選擇一種 K (比如高斯函數(shù))，就一種核密度估計(jì)的方法 （高斯核密度估計(jì)）。

    概率密度估計(jì)中，常用的方法有直方圖估計(jì)、K近鄰估計(jì)、核函數(shù)估計(jì)，其中核函數(shù)估計(jì)的表示如下

其中

令

其亦是核函數(shù)，進(jìn)一步分解，有如下表示：

可以看出，其中第二項(xiàng)也是一種概率密度的核函數(shù)估計(jì)，將其表示為，第三項(xiàng)則為上文中的mean shift的改進(jìn)形式，因此，可以改寫為：

接下來是兩種解釋，首先，求解概率密度局部極大值，令

    這表示mean shift的本質(zhì)是在求解概率密度局部極大值，即偏移均值向量讓目標(biāo)點(diǎn)始終向概率密度極大點(diǎn)處移動(dòng)。但當(dāng)數(shù)據(jù)量非常大時(shí)，一次遍歷所有樣本點(diǎn)顯然不合適，故常選取目標(biāo)點(diǎn) x 附近的一個(gè)區(qū)域，進(jìn)行貪心迭代，逐步收斂于概率密度極大值處；另一種更合理的解釋是，通過在核函數(shù)G() 中融合進(jìn)一個(gè)均勻核函數(shù)來表示選取的有效區(qū)域，然后迭代直至收斂。

再者，從梯度上升的優(yōu)化角度來講，有如下表示：

    即偏移均值向量的作用等價(jià)于以概率密度為目標(biāo)的具有自適應(yīng)步長(zhǎng)的梯度上升優(yōu)化，其在概率密度較小的位置步長(zhǎng)較大，當(dāng)逼近局部極大點(diǎn)時(shí)，概率密度較大，因此步長(zhǎng)較小，符合梯度優(yōu)化中步長(zhǎng)變化的需要。由此，便對(duì)mean shift的含義及其合理性進(jìn)行了解釋，也就不難理解為何mean shift具有強(qiáng)大的效果及適用性了。

3.1 參數(shù)

• bandwidth：浮點(diǎn)數(shù)，默認(rèn)=無(wú)

  RBF 內(nèi)核中使用的帶寬。

  如果未給出，則使用 sklearn.cluster.estimate_bandwidth 估計(jì)帶寬；有關(guān)可伸縮性的提示，請(qǐng)參閱該函數(shù)的文檔(另請(qǐng)參閱下面的注釋)。

• seeds：array-like of shape (n_samples, n_features), default=None

  用于初始化內(nèi)核的種子。如果未設(shè)置，則通過聚類計(jì)算種子。get_bin_seeds 以帶寬為網(wǎng)格大小，其他參數(shù)為默認(rèn)值。

• bin_seeding：布爾，默認(rèn)=假

  如果為真，則初始內(nèi)核位置不是所有點(diǎn)的位置，而是點(diǎn)的離散版本的位置，其中點(diǎn)被分箱到粗糙度對(duì)應(yīng)于帶寬的網(wǎng)格上。將此選項(xiàng)設(shè)置為 True 將加速算法，因?yàn)閷⒊跏蓟俚姆N子。默認(rèn)值為假。如果種子參數(shù)不是無(wú)，則忽略。

• min_bin_freq：整數(shù)，默認(rèn)=1

  為了加快算法速度，只接受那些至少有 min_bin_freq 點(diǎn)的 bin 作為種子。

• cluster_all：布爾，默認(rèn)=真

  如果為真，那么所有點(diǎn)都會(huì)被聚集，即使是那些不在任何內(nèi)核中的孤點(diǎn)也是如此。孤點(diǎn)被分配給最近的內(nèi)核。如果為 false，則給孤點(diǎn)集群標(biāo)簽 -1。

• n_jobs：整數(shù)，默認(rèn)=無(wú)

  用于計(jì)算的作業(yè)數(shù)。這是通過計(jì)算每個(gè) n_init 并行運(yùn)行來實(shí)現(xiàn)的。

  None 表示 1，除非在 joblib.parallel_backend 上下文中。 -1 表示使用所有處理器。有關(guān)詳細(xì)信息，請(qǐng)參閱詞匯表。

• max_iter：整數(shù)，默認(rèn)=300

  如果尚未收斂，則在聚類操作終止(對(duì)于該種子點(diǎn))之前每個(gè)種子點(diǎn)的最大迭代次數(shù)。

3.2 屬性

• cluster_centers_：ndarray 形狀(n_clusters，n_features)

  聚類中心的坐標(biāo)。

• labels_：ndarray 形狀 (n_samples,)

  每個(gè)點(diǎn)的標(biāo)簽。

• n_iter_：int

  對(duì)每個(gè)種子執(zhí)行的最大迭代次數(shù)。

• n_features_in_：int

  擬合期間看到的特征數(shù)。

• feature_names_in_：ndarray 形狀(n_features_in_，)

  擬合期間看到的特征名稱。僅當(dāng) X 具有全為字符串的函數(shù)名稱時(shí)才定義。

注意：

可擴(kuò)展性：

因?yàn)檫@個(gè)實(shí)現(xiàn)使用扁平內(nèi)核和球樹來查找每個(gè)內(nèi)核的成員，所以復(fù)雜度將趨向于 O(T*n*log(n)) 在較低維度上，其中 n 是樣本數(shù)，T 是點(diǎn)。在更高維度上，復(fù)雜度將趨向于 O(T*n^2)。

可通過使用更少的種子來提高可擴(kuò)展性，例如在get_bin_seeds 函數(shù)中使用較高的min_bin_freq 值。

請(qǐng)注意，estimate_bandwidth 函數(shù)的可擴(kuò)展性遠(yuǎn)低于均值偏移算法，如果使用它將成為瓶頸。

3.3 示例

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