每篇一句：

Time is always too short for those who need it, but for those who love, it lasts forever. —Dracula Untold

近鄰聚類法：

近鄰聚類法同樣是一種基于距離閾值的聚類算法。

• 問題：

  有N個待分類的模式{X1,X2,...,Xn}，要求按距離閾值T分類到以Z1,Z2,...為聚類中心的模式類中。（T_threshold）

• 算法描述：

  1. 任取樣本Xi作為第一個聚類中心的初始值，如令Z1 = X1。
  2. 計算樣本X2到Z1的歐式距離D21= ||X2 - Z1||，若D21>T，定義一新的聚類中心Z2 = X2；否則X2 ∈以Z1為中心的聚類。
  3. 假設(shè)已有聚類中心Z1,Z2，計算D31=||X3 - Z1||和D32=||X3 - Z2||，若D31>T且D32>T，則建立第三個聚類中心Z3 = X3；否則X3∈離Z1和Z2中最近著（最近鄰的聚類中心）。
  4. ......以此類推，直到將所有的N個樣本都進(jìn)行分類。

• 算法特點：

1. 局限性：很大程度上依賴于第一個聚類中心的位置選擇、待分類模式樣本的排列次序、距離閾值T的大小以及樣本分布的幾何性質(zhì)等。
2. 優(yōu)點：計算簡單。（一種雖粗糙但快速的方法）

• 算法討論：

用先驗知識指導(dǎo)閾值T和起始點Z1的選擇，可獲得合理的聚類結(jié)果。否則只能選擇不同的初值重復(fù)試探，并對聚類結(jié)果進(jìn)行驗算，根據(jù)一定的評價標(biāo)準(zhǔn)，得出合理的聚類結(jié)果。

對聚類結(jié)果進(jìn)行修改

Python實現(xiàn)：

• 解釋說明見代碼中注釋。

# coding=utf-8

# 近鄰聚類算法的Python實現(xiàn)
# 數(shù)據(jù)集形式data=[[],[],...,[]]
# 聚類結(jié)果形式result=[[[],[],...],[[],[],...],...]
# 其中[]為一個模式樣本，[[],[],...]為一個聚類

from Max_Min_Cluster import get_distance, classify


def knn_cluster(data, t):

    # data：數(shù)據(jù)集，t：距離閾值
    # 算法描述中的介紹的是在尋找聚類中心的同時進(jìn)行聚類，本次實現(xiàn)中并未采取這種方式，
    # 原因是同時進(jìn)行的話要既要考慮聚類中心，又要考慮某個類，實現(xiàn)較為麻煩，
    # 此次采取與上次最大最小距離算法相同的方式，先尋找聚類中心，再根據(jù)最近鄰原則分類，
    # 兩種方式實現(xiàn)效果是相同的，同時又可以直接利用最大最小距離聚類算法中寫好的classify()分類方法

    zs = [data[0]]  # 聚類中心集，選取第一個模式樣本作為第一個聚類中心Z1
    # 計算聚類中心
    get_clusters(data, zs, t)
    # 分類
    result = classify(data, zs, t)
    return result


def get_clusters(data, zs, t):
    for aData in data:
        min_distance = get_distance(aData, zs[0])
        for i in range(0, len(zs)):
            distance = get_distance(aData, zs[i])
            if distance < min_distance:
                min_distance = distance
        if min_distance > t:
            zs.append(aData)


# data = [[0, 0], [3, 8], [1, 1], [2, 2], [5, 3], [4, 8], [6, 3], [5, 4], [6, 4], [7, 5]]
# t = 4.5
# result = knn_cluster(data, t)
# for i in range(len(result)):
#     print "----------第" + str(i+1) + "個聚類----------"
#     print result[i]

# 打印結(jié)果：
# ----------第1個聚類----------
# [[0, 0], [1, 1], [2, 2]]
# ----------第2個聚類----------
# [[3, 8], [4, 8]]
# ----------第3個聚類----------
# [[5, 3], [6, 3], [5, 4], [6, 4], [7, 5]]

注：算法描述中的介紹的是在尋找聚類中心的同時進(jìn)行聚類，本次實現(xiàn)中并未采取這種方式，原因是若同時進(jìn)行的話要既要考慮聚類中心集合的表現(xiàn)形式，又要考慮某個聚類的表現(xiàn)形式，總體來說，數(shù)據(jù)表示形式較為麻煩。此次實現(xiàn)采取與上次最大最小距離聚類算法相同的方式：先尋找聚類中心，再根據(jù)最近鄰原則分類，兩種方式實現(xiàn)效果是相同的，同時又可以直接利用最大最小距離聚類算法中寫好的classify()分類方法。

最后：

本文簡單的介紹了 聚類算法 —— 近鄰聚類算法 的相關(guān)內(nèi)容，以及相應(yīng)的代碼實現(xiàn)，如果有錯誤的或者可以改進(jìn)的地方，歡迎大家指出。

代碼地址：聚類算法——近鄰聚類算法（碼云）

原文地址：聚類算法——近鄰聚類算法，也是本人的CSDN賬號，歡迎關(guān)注，博客會第一時間在CSDN更新。