Spectral?clustering譜聚類算法的實現(xiàn)代碼

更新時間：2022年04月12日 11:04:19 作者：ZHW_AI課題組

譜聚類是從圖論中演化出來的算法，它的主要思想是把所有的數(shù)據(jù)看做空間中的點，這些點之間可以用邊連接起來，今天通過本文給大家介紹Spectral?clustering譜聚類算法的實現(xiàn)，感興趣的朋友一起看看吧

1.作者介紹

劉然，女，西安工程大學電子信息學院，2021級研究生
研究方向：圖像處理
電子郵件：1654790996@qq.com

劉帥波，男，西安工程大學電子信息學院，2021級研究生，張宏偉人工智能課題組
研究方向：機器視覺與人工智能
電子郵件：1461004501@qq.com

2.關(guān)于譜聚類的介紹

2.1 譜聚類概述

譜聚類是從圖論中演化出來的算法，它的主要思想是把所有的數(shù)據(jù)看做空間中的點，這些點之間可以用邊連接起來。距離較遠的兩個點之間的邊權(quán)重值較低，而距離較近的兩個點之間的邊權(quán)重值較高，通過對所有數(shù)據(jù)點組成的圖進行切圖，讓切圖后不同的子圖間邊權(quán)重和盡可能的低，而子圖內(nèi)的邊權(quán)重和盡可能的高，從而達到聚類的目的。

2.2 無向權(quán)重圖

對于一個圖G，我們一般用點的集合V和邊的集合E來描述。即為G(V,E)。其中V即為我們數(shù)據(jù)集里面所有的點(v1,v2,…vn)。對于V中的任意兩個點，點vi和點vj，我們定義權(quán)重wij為二者之間的權(quán)重。由于是無向圖，所以wij=wji。

2.3 鄰接矩陣

鄰接矩陣(Adjacency Matrix):是表示頂點之間相鄰關(guān)系的矩陣。在如圖2-1所示的權(quán)重圖當中（假設(shè)各權(quán)重為1），其鄰接矩陣可表示為圖2-2所示。

在這里插入圖片描述

2.4 相似矩陣

在譜聚類中，我們只有數(shù)據(jù)點的定義，并沒有直接給出這個鄰接矩陣，所以我們可以通過樣本點距離度量的相似矩陣S來獲得鄰接矩陣W。

2.5 度矩陣

度矩陣是對角陣，對角上的元素為各個頂點的度。圖2-1的度矩陣為圖2-3所示。

在這里插入圖片描述

2.6 拉普拉斯矩陣

拉普拉斯矩陣L=D-W，其中D為度矩陣，W為鄰接矩陣。圖2-1的拉普拉斯矩陣為圖2-4所示。

在這里插入圖片描述

用拉普拉斯矩陣求解特征值，通過確定特征值（特征值要遵循從小到大的排列方式）的個數(shù)來確定對應特征向量的個數(shù)，從而實現(xiàn)降維，然后再用kmeans將特征向量進行聚類。

2.7 K-Means

K-Means是聚類算法中的最常用的一種，算法最大的特點是簡單，好理解，運算速度快，但是只能應用于連續(xù)型的數(shù)據(jù)，并且一定要在聚類前需要手工指定要分成幾類。
下面，我們描述一下K-means算法的過程，為了盡量不用數(shù)學符號，所以描述的不是很嚴謹，大概就是這個意思，“物以類聚、人以群分”：
1.首先輸入k的值，即我們希望將數(shù)據(jù)集經(jīng)過聚類得到k個分組。
2.從數(shù)據(jù)集中隨機選擇k個數(shù)據(jù)點作為初始大哥（質(zhì)心，Centroid）
3.對集合中每一個小弟，計算與每一個大哥的距離（距離的含義后面會講），離哪個大哥距離近，就跟定哪個大哥。
4.這時每一個大哥手下都聚集了一票小弟，這時候召開人民代表大會，每一群選出新的大哥（其實是通過算法選出新的質(zhì)心）。
5.如果新大哥和老大哥之間的距離小于某一個設(shè)置的閾值（表示重新計算的質(zhì)心的位置變化不大，趨于穩(wěn)定，或者說收斂），可以認為我們進行的聚類已經(jīng)達到期望的結(jié)果，算法終止。
6.如果新大哥和老大哥距離變化很大，需要迭代3~5步驟。

3.Spectral clustering（譜聚類）算法實現(xiàn)

3.1 數(shù)據(jù)集

本實驗中使用到的數(shù)據(jù)集均由sklearn.datasets中提供的方法生成，本實驗中用到了make_circles，make_moons，make_blobs等函數(shù)。make_circles生成數(shù)據(jù)集，形成一個二維的大圓，包含一個小圓，如圖3-1所示；make_moons生成數(shù)據(jù)集，形成兩個彎月，如圖3-2所示；make_blobs為聚類生成符合正態(tài)分布的數(shù)據(jù)集，如圖3-3所示。

在這里插入圖片描述

3.2 導入所需要的包

#導入需要的包
import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_moons#生成數(shù)據(jù)集，形成兩個彎月。
from sklearn.datasets import make_circles#生成數(shù)據(jù)集，形成一個二維的大圓，包含一個小圓
from sklearn.datasets import make_blobs#為聚類生成符合正態(tài)分布的數(shù)據(jù)集，產(chǎn)生一個數(shù)據(jù)集和相應的標簽
import matplotlib.pyplot as plt

3.3 獲取特征值和特征向量

def get_eigen(L, num_clusters):#獲取特征
    eigenvalues, eigenvectors = np.linalg.eigh(L)#獲取特征值  特征向量
    best_eigenvalues = np.argsort(eigenvalues)[0:num_clusters]#argsort函數(shù)返回的是數(shù)組值從小到大的索引值
    U = np.zeros((L.shape[0], num_clusters))
    U = eigenvectors[:, best_eigenvalues]#將這些特征取出 構(gòu)成新矩陣
    return U

3.4 利用K-Means聚類

#K-Means聚類
def cluster(data, num_clusters):
    data = np.array(data)
    W = affinity_matrix(data)
    D = getD(W)
    L = getL(D, W)
    eigenvectors = get_eigen(L, num_clusters)
    clf = KMeans(n_clusters=num_clusters)
    s = clf.fit(eigenvectors)  # 聚類
    label = s.labels_
    return label

3.5 完整代碼

#導入需要的包
import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_moons#生成數(shù)據(jù)集，形成兩個彎月。
from sklearn.datasets import make_circles#生成數(shù)據(jù)集，形成一個二維的大圓，包含一個小圓
from sklearn.datasets import make_blobs#為聚類生成符合正態(tài)分布的數(shù)據(jù)集，產(chǎn)生一個數(shù)據(jù)集和相應的標簽
import matplotlib.pyplot as plt

#定義高斯核函數(shù)
def kernel(x1, x2, sigma_sq=0.05):
    return np.exp(-(np.linalg.norm(x1 - x2) ** 2) / (2 * sigma_sq ** 2))

#定義相似度矩陣
def affinity_matrix(X):
    A = np.zeros((len(X), len(X)))#零矩陣
    for i in range(len(X) - 1):#長度為len(x) 但是從0開始
        for j in range(i + 1, len(X)):#從1開始，到len(x) 是方陣 為啥下角標取值的初始值不同？？？
            A[i, j] = A[j, i] = kernel(X[i], X[j])
    return A#通過高斯核的計算 給矩陣賦予新值    10*10

# 計算度矩陣
def getD(A):
    D = np.zeros(A.shape)
    for i in range(A.shape[0]):
        D[i, i] = np.sum(A[i, :])
    return D

#計算拉普拉斯矩陣
def getL(D, A):
    L = D - A
    return L


def get_eigen(L, num_clusters):#獲取特征
    eigenvalues, eigenvectors = np.linalg.eigh(L)#獲取特征值  特征向量
    best_eigenvalues = np.argsort(eigenvalues)[0:num_clusters]#argsort函數(shù)返回的是數(shù)組值從小到大的索引值
    U = np.zeros((L.shape[0], num_clusters))
    U = eigenvectors[:, best_eigenvalues]#將這些特征取出 構(gòu)成新矩陣
    return U

#K-Means聚類
def cluster(data, num_clusters):
    data = np.array(data)
    W = affinity_matrix(data)
    D = getD(W)
    L = getL(D, W)
    eigenvectors = get_eigen(L, num_clusters)
    clf = KMeans(n_clusters=num_clusters)
    s = clf.fit(eigenvectors)  # 聚類
    label = s.labels_
    return label


def plotRes(data, clusterResult, clusterNum):
    """
    結(jié)果可似化
    : data:  樣本集
    : clusterResult: 聚類結(jié)果
    : clusterNum: 聚類個數(shù)
    :return:
    n = len(data)
    scatterColors = ['black', 'blue', 'red', 'yellow', 'green', 'purple', 'orange']
    for i in range(clusterNum):
        color = scatterColors[i % len(scatterColors)]
        x1 = []
        y1 = []
        for j in range(n):
            if clusterResult[j] == i:
                x1.append(data[j, 0])
                y1.append(data[j, 1])
        plt.scatter(x1, y1, c=color, marker='+')


if __name__ == '__main__':
# # #月牙形數(shù)據(jù)集,sigma=0.1
# #     # cluster_num = 2
# #     # data, target = make_moons()
# #     # label = cluster(data, cluster_num)
# #     # print(label)
# #     # plotRes(data, label, cluster_num)
# #
#     # 圓形數(shù)據(jù)集,sigma=0.05
    cluster_num = 2
    data, target = make_circles(n_samples=1000, shuffle=True, noise=0.05, factor=0.5)
    label = cluster(data, cluster_num)
    print(label)
    plotRes(data, label, cluster_num)
# #    #  # 正態(tài)數(shù)據(jù)集
# #    # # n_samples是待生成的樣本的總數(shù)。
# #    #  # n_features是每個樣本的特征數(shù)。
# #    #  # centers表示類別數(shù)。
# #    #  # cluster_std表示每個類別的方差，例如我們希望生成2類數(shù)據(jù)，其中一類比另一類具有更大的方差，可以將cluster_std設(shè)置為[1.0, 3.0]。
# #    #  cluster_num = 2
# #    #  data, target = make_blobs(n_samples=1500, n_features=2, centers=4, random_state=24)
# #    #  label = cluster(data, cluster_num)
# #    #  print(label)
# #    #  plt.subplot(121)
# #    #  plotRes(data, target, cluster_num)
# #    #  plt.subplot(122)
# #    #  plotRes(data, label, cluster_num)
plt.show()