? ? ? ?聲明：代碼的運(yùn)行環(huán)境為Python3。Python3與Python2在一些細(xì)節(jié)上會(huì)有所不同，希望廣大讀者注意。本博客以代碼為主，代碼中會(huì)有詳細(xì)的注釋。相關(guān)文章將會(huì)發(fā)布在我的個(gè)人博客專欄《Python從入門到深度學(xué)習(xí)》，歡迎大家關(guān)注~

---

? ? ? ?在K-Means算法中，聚類的類別個(gè)數(shù)需要提前指定，對(duì)于類別個(gè)數(shù)未知的數(shù)據(jù)集，K-Means算法和K-Means++算法將很難對(duì)其進(jìn)行求解，所以需要一些能夠處理未知類別個(gè)數(shù)的算法來(lái)處理此類問(wèn)題。Mean Shift算法，又稱作均值漂移算法，它跟K-Means算法一樣，都是基于聚類中心的聚類算法，不同的是，它不需要提前指定聚類中心的個(gè)數(shù)，聚類中心是通過(guò)在給定區(qū)域中樣本的均值來(lái)確定的，通過(guò)不斷更新聚類中心，直至聚類中心不再改變?yōu)橹埂?

一、Mean Shift向量與核函數(shù)

1、Mean Shift向量

? ? ? ?對(duì)于給定的n維空間 中的m個(gè)樣本點(diǎn) ，對(duì)于其中的一個(gè)樣本X，其Mean Shift的向量為：

? ? ? ?其中， 指的是一個(gè)半徑為h的高維球區(qū)域， 定義為：

2、核函數(shù)

? ? ? ?通過(guò)上述方式求出的Mean Shift向量時(shí)存在問(wèn)題的，即在 區(qū)域內(nèi)每一個(gè) 對(duì)樣本X的貢獻(xiàn)是一樣的，然而實(shí)際上，每一個(gè)樣本 對(duì)樣本X的貢獻(xiàn)是不一樣的，我們可以通過(guò)核函數(shù)對(duì)每一個(gè)樣本的貢獻(xiàn)進(jìn)行度量。

? ? ? ?核函數(shù)的定義如下：

? ? ? ?設(shè)Z是輸入空間，H是特征空間，如果存在一個(gè)Z到H的映射： 使得所有 ，函數(shù) 滿足條件： ，則稱 為核函數(shù)， 為映射函數(shù)。

? ? ? ?我們?cè)贛ean Shift算法中使用的是高斯核函數(shù)，這也是最常用的核函數(shù)之一，高斯核函數(shù)的表達(dá)式為：

? ? ? ?其中，h為帶寬，當(dāng)帶寬一定時(shí)，樣本點(diǎn)之間的距離越近，核函數(shù)的值越大；當(dāng)樣本點(diǎn)距離一定時(shí)，帶寬越大，核函數(shù)的值越小。

? ? ? ?下面我們使用Python代碼實(shí)現(xiàn)高斯核函數(shù)：

            
              import numpy as np
import math

def gs_kernel(dist, h):
    '''
    高斯核函數(shù)
    :param dist: 歐氏距離
    :param h: 帶寬
    :return: 返回高斯核函數(shù)的值
    '''
    m = np.shape(dist)[0]  # 樣本個(gè)數(shù)
    one = 1 / (h * math.sqrt(2 * math.pi))
    two = np.mat(np.zeros((m, 1)))
    for i in range(m):
        two[i, 0] = (-0.5 * dist[i] * dist[i].T) / (h * h)
        two[i, 0] = np.exp(two[i, 0])
    
    gs_val = one * two
    return gs_val
            
          

二、Mean Shift原理

? ? ? ?在Mean Shift中通過(guò)迭代的方式找到最終的聚類中心，即對(duì)每一個(gè)樣本點(diǎn)計(jì)算其漂移均值，以計(jì)算出來(lái)的漂移均值點(diǎn)作為新的起始點(diǎn)重復(fù)上述步驟，直到滿足終止條件，得到的最終的漂移均值點(diǎn)即為最終的聚類中心。

? ? ? ?Mean Shift算法實(shí)現(xiàn)過(guò)程如下：

            
              def mean_shift(points, h=2, MIN_DISTANCE=0.000001):
    '''
    訓(xùn)練Mean Shift模型
    :param points: 特征點(diǎn)
    :param h: 帶寬
    :param MIN_DISTANCE: 最小誤差
    :return: 返回特征點(diǎn)、均值漂移點(diǎn)、類別
    '''
    mean_shift_points = np.mat(points)
    max_min_dist = 1
    iteration = 0  # 迭代的次數(shù)
    m = np.shape(mean_shift_points)[0]  # 樣本的個(gè)數(shù)
    need_shift = [True] * m  # 標(biāo)記是否需要漂移

    # 計(jì)算均值漂移向量
    while max_min_dist > MIN_DISTANCE:
        max_min_dist = 0
        iteration += 1
        print("iteration : " + str(iteration))
        for i in range(0, m):
            if not need_shift[i]:  # 判斷每一個(gè)樣本點(diǎn)是否需要計(jì)算偏移均值
                continue
            point_new = mean_shift_points[i]
            point_new_start = point_new
            point_new  = shift_point(point_new, points, h)  # 對(duì)樣本點(diǎn)進(jìn)行漂移計(jì)算
            dist = distince(point_new, point_new_start)  # 計(jì)算該點(diǎn)與漂移后的點(diǎn)之間的距離
            
            if dist > max_min_dist:
                max_min_dist = dist
            if dist < MIN_DISTANCE:
                need_shift[i] = False
            
            mean_shift_points[i] = point_new
    # 計(jì)算最終的類別
    lb = lb_points(mean_shift_points)  # 計(jì)算所屬的類別
    return np.mat(points), mean_shift_points, lb
            
          

? ? ? ?其中，shift_point()方法目的在于計(jì)算漂移量，lb_points()方法的目的在于計(jì)算最終所屬分類，distance()方法用于計(jì)算歐氏距離，三個(gè)方法的實(shí)現(xiàn)過(guò)程分別如下：

（1）shift_point()方法

            
              def shift_point(point, points, h):
    '''
    計(jì)算漂移向量
    :param point: 需要計(jì)算的點(diǎn)
    :param points: 所有的樣本點(diǎn)
    :param h: 帶寬
    :return: 返回漂移后的點(diǎn)
    '''
    points = np.mat(points)
    m = np.shape(points)[0]  # 樣本的個(gè)數(shù)
    # 計(jì)算距離
    point_dist = np.mat(np.zeros((m, 1)))
    for i in range(m):
        point_dist[i, 0] = distince(point, points[i])

    # 計(jì)算高斯核函數(shù)
    point_weights = gs_kernel(point_dist, h)

    # 計(jì)算分母
    all_sum = 0.0
    for i in range(m):
        all_sum += point_weights[i, 0]

    # 計(jì)算均值偏移
    point_shifted = point_weights.T * points / all_sum
    return point_shifted
            
          

（2）lb_points()

            
              def lb_points(mean_shift_points):
    '''
    計(jì)算所屬類別
    :param mean_shift_points: 漂移向量
    :return: 返回所屬的類別
    '''
    lb_list = []
    m, n = np.shape(mean_shift_points)
    index = 0
    index_dict = {}
    for i in range(m):
        item = []
        for j in range(n):
            item.append(str(("%5.2f" % mean_shift_points[i, j])))

        item_1 = "_".join(item)
        if item_1 not in index_dict:
            index_dict[item_1] = index
            index += 1

    for i in range(m):
        item = []
        for j in range(n):
            item.append(str(("%5.2f" % mean_shift_points[i, j])))

        item_1 = "_".join(item)
        lb_list.append(index_dict[item_1])
    return lb_list
            
          

（3）distince()方法

            
              def distince(pointA, pointB):
    '''
    計(jì)算歐氏距離
    :param pointA: A點(diǎn)坐標(biāo)
    :param pointB: B點(diǎn)坐標(biāo)
    :return: 返回得到的歐氏距離
    '''
    return math.sqrt((pointA - pointB) * (pointA - pointB).T)
            
          

三、Mean Shift算法舉例

1、數(shù)據(jù)集：數(shù)據(jù)集含有兩個(gè)特征，如下圖所示：

2、加載數(shù)據(jù)集

? ? ? ?我們此處使用如下方法加載數(shù)據(jù)集，也可使用其他的方式進(jìn)行加載，此處可以參考我的另外一篇文章《Python兩種方式加載文件內(nèi)容》。加載文件內(nèi)容代碼如下：

            
              def load_data(path, feature_num=2):
    '''
    導(dǎo)入數(shù)據(jù)
    :param path: 路徑
    :param feature_num: 特行總數(shù)
    :return: 返回?cái)?shù)據(jù)特征
    '''
    f = open(path)
    data = []
    for line in f.readlines():
        lines = line.strip().split("\t")
        data_tmp = []
        if len(lines) != feature_num:  # 判斷特征的個(gè)數(shù)是否正確，把不符合特征數(shù)的數(shù)據(jù)去除
            continue
        for i in range(feature_num):
            data_tmp.append(float(lines[i]))
        data.append(data_tmp)
    f.close()
    return data
            
          

3、保存聚類結(jié)果

? ? ? ?通過(guò)Mean Shift聚類后，我們使用一下方法進(jìn)行聚類結(jié)果的保存

            
              def save_result(file_name, data):
    '''
    保存聚類結(jié)果
    :param file_name: 保存的文件名
    :param data: 需要保存的文件
    :return:
    '''
    f = open(file_name, "w")
    m, n = np.shape(data)
    for i in range(m):
        tmp = []
        for j in range(n):
            tmp.append(str(data[i, j]))
        f.write("\t".join(tmp) + "\n")
    f.close()
            
          

4、調(diào)用Mean Shift算法

            
              if __name__ == "__main__":
    data = load_data("F://data", 2)
    points, shift_points, cluster = mean_shift(data, 2)
    save_result("sub", np.mat(cluster))
    save_result("center", shift_points)
            
          

5、結(jié)果展示

? ? ? ?得到的聚類結(jié)果如下所示：

? ? ? ? 你們?cè)诖诉^(guò)程中遇到了什么問(wèn)題，歡迎留言，讓我看看你們都遇到了哪些問(wèn)題。