Spectral clustering譜聚類演演算法的實現程式碼

2022-04-12 13:00:35

1.作者介紹

劉然，女，西安工程大學電子資訊學院，2021級研究生
研究方向：影象處理
電子郵件：1654790996@qq.com

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

2.關於譜聚類的介紹

2.1 譜聚類概述

譜聚類是從圖論中演化出來的演演算法，它的主要思想是把所有的資料看做空間中的點，這些點之間可以用邊連線起來。距離較遠的兩個點之間的邊權重值較低，而距離較近的兩個點之間的邊權重值較高，通過對所有資料點組成的圖進行切圖，讓切圖後不同的子圖間邊權重和儘可能的低，而子圖內的邊權重和儘可能的高，從而達到聚類的目的。

2.2 無向權重圖

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

2.3 鄰接矩陣

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

2.4 相似矩陣

在譜聚類中，我們只有資料點的定義，並沒有直接給出這個鄰接矩陣，所以我們可以通過樣本點距離度量的相似矩陣S來獲得鄰接矩陣W。

2.5 度矩陣

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

2.6 拉普拉斯矩陣

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

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

2.7 K-Means

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

3.Spectral clustering（譜聚類）演演算法實現

3.1 資料集

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

3.2 匯入所需要的包

#匯入需要的包
import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_moons#生成資料集，形成兩個彎月。
from sklearn.datasets import make_circles#生成資料集，形成一個二維的大圓，包含一個小圓
from sklearn.datasets import make_blobs#為聚類生成符合正態分佈的資料集，產生一個資料集和相應的標籤
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函數返回的是陣列值從小到大的索引值
    U = np.zeros((L.shape[0], num_clusters))
    U = eigenvectors[:, best_eigenvalues]#將這些特徵取出 構成新矩陣
    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#生成資料集，形成兩個彎月。
from sklearn.datasets import make_circles#生成資料集，形成一個二維的大圓，包含一個小圓
from sklearn.datasets import make_blobs#為聚類生成符合正態分佈的資料集，產生一個資料集和相應的標籤
import matplotlib.pyplot as plt

#定義高斯核函數
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函數返回的是陣列值從小到大的索引值
    U = np.zeros((L.shape[0], num_clusters))
    U = eigenvectors[:, best_eigenvalues]#將這些特徵取出 構成新矩陣
    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):
    """
    結果可似化
    : data:  樣本集
    : clusterResult: 聚類結果
    : clusterNum: 聚類個數
    :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__':
# # #月牙形資料集,sigma=0.1
# #     # cluster_num = 2
# #     # data, target = make_moons()
# #     # label = cluster(data, cluster_num)
# #     # print(label)
# #     # plotRes(data, label, cluster_num)
# #
#     # 圓形資料集,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)
# #    #  # 正態資料集
# #    # # n_samples是待生成的樣本的總數。
# #    #  # n_features是每個樣本的特徵數。
# #    #  # centers表示類別數。
# #    #  # cluster_std表示每個類別的方差，例如我們希望生成2類資料，其中一類比另一類具有更大的方差，可以將cluster_std設定為[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()