機器學習--聚類算法之mean shift

聚類算法之mean shift

• 1. mean shift的概念
• 2. 算法解析
• • 2.1 算法流程
  • 2.2 算法公式
• 3.mean shift的應用場景
• 4.執行個體分析

1. mean shift的概念

相對于k-mean和k-mean++算法，mean shift（均值偏移）算法，都是基于聚類中心的聚類算法。但是，mean shift的優勢在于不需要事先制定類别個數k（無監督學習）。

mean shift的基本概念：沿着密度上升方向尋找聚簇點。

2. 算法解析

2.1 算法流程

設想在一個有N個樣本點的特征空間，利用mean shift算法對資料進行分類

1. 初始确定一個中心點center，計算在設定的半斤為D的圓形空間内所有的點與中心點center 的向量
2. 計算整個圓形空間内所有向量的平均值，得到一個偏移均值
3. 将中心點center移動到偏移均值位置

4. 重複移動，直到滿足一定條件結束

   圖一所示，綠色圈的中心以偏移向量的方向移動，一步一步移動，直到移動到紅色圈的中心位置（此處是密度最大的地方）

   

   圖二：先算出目前點的偏移均值，将該點移動到此偏移均值，然後以此為新的起始點，繼續移動，直到滿足最終的條件。

   

2.2 算法公式

偏移均值的公式：

Sh:以x為中心點，半徑為h的高維球區域； k:包含在Sh範圍内點的個數； xi:包含在Sh範圍内的點

中心更新：（将中心點朝向偏移均值的矢量方向移動）

Mt為t狀态下求得的偏移均值; xt為t狀态下的中心

後來，Yizong Cheng對mean shift進行補充，主要提出了兩點的改進：定義了核函數，增加了權重系數。核函數的定義使得偏移值對偏移向量的貢獻随之樣本與被偏移點的距離的不同而不同。權重系數使得不同樣本的權重不同。

引入核函數的mean shift公式：

核函數：隻是用來計算映射到高維空間之後的内積的一種簡便方法，目的為讓低維的不可分資料變成高維可分。利用核函數，可以忽略映射關系，直接在低維空間中完成計算（引用核函數的優勢：能夠使計算中距離中心的點具有更大的權值，反映距離越短，權值越大的特性）。

其中，x為中心點；xi為帶寬範圍内的點；n為帶寬範圍内的點的數量；g(x)為對核函數的導數求負

3.mean shift的應用場景

Mean Shift算法在很多領域都有成功應用，例如圖像平滑、圖像分割、物體跟蹤等，這些屬于人工智能裡面模式識别或計算機視覺的部分；另外也包括正常的聚類應用。

• 圖像平滑：圖像最大品質下的像素壓縮；
• 圖像分割：跟圖像平滑類似的應用，但最終是将可以平滑的圖像進行分離已達到前後景或固定實體分割的目的；
• 目标跟蹤：例如針對監控視訊中某個人物的動态跟蹤；
• 正常聚類，如使用者聚類等

4.執行個體分析

基于均值漂移的分類：

• 在未被分類的資料點中随機選擇一個點作為中心點；
• 找出離中心點距離在帶寬之内的所有點，記做集合M，認為這些點屬于簇c
• 計算從中心點開始到集合M中每個元素的向量，将這些向量相加，得到偏移向量
• 中心點沿着shift的方向移動，移動距離是偏移向量的模
• 重複步驟2、3、4，直到偏移向量的大小滿足設定的門檻值要求，記住此時的中心點
• 重複1、2、3、4、5直到所有的點都被歸類
• 分類：根據每個類，對每個點的通路頻率，取通路頻率最大的那個類，作為目前點集的所屬類。

參考連結：

1. https://www.biaodianfu.com/mean-shift.html
2. https://blog.csdn.net/qwerasdf_1_2/article/details/54577336