文章 44
浏览 11238
谱聚类再次整理

谱聚类再次整理

首先查阅相关的资料,比较谱聚类算法与传统的聚类算法 K-mean 的区别。

K-mean

K-mean 实现:

  1. 确定 K 值,随机选取 K 个点
  2. 以这 K 个点为中心质点,对原始数据集中中的每个点分别计算离哪个中心点更近
  3. 计算结束就将原始数据集分为 K 个类,对 K 个类重新计算中心质点(平均值法)
  4. 若全部 K 类新计算出的中心质点与该类上一个中心质点的距离小于一个阈值,则认为聚类操作已经收敛了,聚类结束
  5. 否则重复步骤 2-4

K-mean 的优缺点主要如下:

  • 优点:
    1. 原理简单,易于理解
    2. 聚类效果不错
  • 缺点:
    1. 需要提前确定 K 值(划分种类数)
    2. 个别噪点对于总体效果影响较大

Spectral Clustering

需要先了解:

  1. 邻接矩阵 W:衡量两个点之间关系(比如位置上接近,表示两个点关联紧密)的一个矩阵,常有很多的衡量方法。
  2. 度矩阵 D:是一个对角矩阵,对角线上每一行元素的值为邻接矩阵 W 中每行元素值的和。
  3. 拉普拉斯矩阵 L:该矩阵具有很多的性质,谱聚类算法与这些性质密切相关
    1. 拉普拉斯矩阵是一个半正定矩阵
    2. 对于任何向量 L 下列式子成立image20200630114848909.png

主要思想:

如果有 A 和 B 两个子图,两个子图间的联系是不是可以用下面这种方式来表示呢?

[公式]

我们只要使上面的式子最小化,是不是就可以保证两个子图联系最小,就可以认为这是两个不相关的部分。

但是如果单纯依靠这种方式,会导致倾向于将孤立的点切开,因为单独一个点到其他部分的权值肯定是最小的。怎么避免这种问题出现呢?有两种办法:

  • 一是将最小化目标改成如下:

    image20200630121230220.png

  • 而是将最小化目标改为:

    image20200630121326983.png

这也就引出了谱聚类的两种常用方法。

但是怎么最小化这个值呢?

我们以第一个 RdtioCut 为例。大神们发现,可以引入一个向量 h_j (1<=j<=k) ,这个向量表示的是什么呢?

image20200630121735543.png

向量 h_j中的每个值 h_{ij} (1<=i<=n) 有两种取值,表示坐标点 i 是不是属于子图 A_j|A_j| 表示子图中节点数量

对这个向量进行如下的运算:

image20200322223247236.png

我们会惊奇的发现这不就是我们最小化的目标吗?只不过现在图中的点只分为了两部分(属于A_i 和不属于)

如果我们想将图分为更多的子图,那么我们的目标就成为了:划分 K 个子图,每个子图和子图以外部分的连接权重和最小。也即使如下公式最小:

image20200630123607324.png

我们还知道向量 h_ih_j是表示点划分的两种情况,h_i表示属于A_i的点,h_j表示属于A_j的点。那么这两个向量就应该是正交的。并且 h^T h = 1 。这时我们引入瑞丽商的性质:

  • h_i^T * h_i=1
  • h_i^T L h_i等于 L 的特征值

也就意味着我们最小化的目标变为了求:H^T L H (H={h_1,h_2....h_k}) 这个式子最小的 k 个特征值,他们对应的就是划分最准确的情况。但还有一个问题,我们得到了最小的 K 个特征值和他们对应的特征向量,怎能才能利用他们聚类呢?其实,我们可以把所得特征值向量对每个样本的表示看作是一种类别编码,我们通过传统聚类的方法能够得到最终结果。

另外

对于 Ncut 稍不同于上面的 RatioCut。因为 Ncut 中,虽然也引入了一个向量h_i,但是向量定义为如下,vol(A_j) 表示的是子图中节点度的和。

image20200630125353234.png

然后步骤都类似于 RatioCut 只不过在利用瑞丽商的时候出现了问题,因为 h^T h = 1 并不成立了。所以需要采取一些办法,根据

image20200322222411822.png

m_i^T m_i=1

m_i=D^{1/2}*h_i

我们需要把现在的 h_i 变成 m_i

也即 h_i^T L h_i=m_i^T*D^{-1/2}*L*D^{-1/2}*m_i=h_i^T *D^{1/2}*D^{-1/2}*L*D^{-1/2}*D^{1/2}*h_i

此时要求特征值的矩阵变为: D^{-1/2}*L*D^{-1/2}

谱聚类实现步骤:

  1. 定义邻接矩阵 W
    • ε 近邻法
      • 只取距离小于ε的边,否则为 0
    • K 近邻法
      • 两点互为 K 近邻,否则为 0
      • 其一为 K 近邻,否则为 0
    • 全连接法
      • 常采用高斯核函数的方法,每两个点之间的权值都不为 0
  2. 度矩阵 D
    • 可根据邻接矩阵 W 得
  3. 拉普拉斯矩阵矩阵 L
    • L= D - W
  4. 正规化
    • D^{-1/2}LD^{-1/2}
  5. 计算特征向量
    • 计算 K 个最小特征值对应的特征向量h_i,特征向量组成矩阵H^{n*k}
  6. H 标准化
    • 消除奇异值带来的影响

以上是谱聚类第一大部分,降维

  1. H 使用 K-mean 进行最后的聚类
    • 得出结果

这是谱聚类的第二大部分,聚类

NCut 推导细节

image20200322223222295.png

RadioCut 推导细节

image20200322223247236.png

谱聚类优势

  • 效果好
  • 由于采用了降维的思想,处理高维数据时有优势

实现代码

  1# coding=utf-8
  2import math
  3import random
  4
  5import matplotlib.pyplot as plt
  6import numpy as np
  7import PIL.Image as image
  8import scipy.io as sio
  9from sklearn.cluster import KMeans
 10
 11
 12def loadIMG(filePath):
 13    img = image.open(filePath)  # 返回图片的像素值
 14
 15    img = img.convert("RGB")
 16    m, n = img.size  # 返回图片的大小
 17
 18    img_vector = np.array(img)
 19
 20    pixel_vector = []
 21
 22    for i in range(n):
 23        for j in range(m):
 24            if(img_vector[i][j][0] < 150 and img_vector[i][j][1] < 150 and img_vector[i][j][2] < 150):
 25
 26                pixel_vector.append(np.array([j, i]))
 27
 28    return pixel_vector
 29
 30
 31def loaddata():
 32    # 读取数据
 33    file = 'GaussianData.mat'
 34    # 文件名
 35    file = 'ringData.mat'
 36    data = sio.loadmat(file)
 37    matrix = np.array(data['Dataset'])
 38    return matrix
 39
 40
 41def distanceRgb(p1, p2):
 42    r1, g1, b1 = p1[0], p2[1], p2[2]
 43    r2, g2, b2 = p2[0], p2[1], p2[2]
 44    rmean = (r1+r2)/2
 45    r = r1-r2
 46    g = g1-g2
 47    b = b1-b2
 48    return math.sqrt((2+rmean)*(r**2)+4*(g**2)+(2+(255/256-rmean))*(b**2))
 49
 50
 51def distance(p1, p2):
 52    # 欧式距离
 53    return np.linalg.norm(p1-p2)
 54
 55
 56def getWbyKNN(data, k):
 57    # data:点阵坐标信息
 58    points_num = len(data)
 59    # 点数量:300
 60    dis_matrix = np.zeros((points_num, points_num))
 61    # 创建矩阵300*300
 62    W = np.zeros((points_num, points_num))
 63    # 创建矩阵300*300
 64    for i in range(points_num):
 65        for j in range(i+1, points_num):
 66            dis_matrix[i][j] = dis_matrix[j][i] = distance(data[i], data[j])
 67    # 将每个点与其他点的相似度表示成矩阵
 68    for idx, each in enumerate(dis_matrix):
 69        index_array = np.argsort(each)
 70        # 排序
 71        W[idx][index_array[1:k+1]] = 1
 72        # 找出距离第idx个点距离最近的k个点
 73        # 距离最短的是自己,所以取1到k+1
 74    tmp_W = np.transpose(W)
 75    # 转置
 76    W = (tmp_W+W)/2
 77    # 转置相加除以2是为了让矩阵对称
 78    return W
 79
 80
 81def getD(W):
 82    # 获得度矩阵
 83    points_num = len(W)
 84    D = np.diag(np.zeros(points_num))
 85    # 转换成对角阵
 86    for i in range(points_num):
 87
 88        D[i][i] = sum(W[i])
 89    return D
 90
 91
 92def getEigVec(L, cluster_num):
 93    # 从拉普拉斯矩阵获得特征矩阵
 94    eigval, eigvec = np.linalg.eig(L)
 95    # 特征值、特征向量
 96    lenght = len(eigval)
 97    dictEigval = dict(zip(eigval, range(0, lenght)))
 98    kEig = np.sort(eigval)[0:cluster_num]
 99    # 排序
100    ix = [dictEigval[k] for k in kEig]
101
102    return eigval[ix], eigvec[:, ix]
103    # 取特征值和对应的列向量
104
105
106def randRGB():
107    # 添加颜色,便于区分
108    return (random.randint(0, 255)/255.0,
109            random.randint(0, 255)/255.0,
110            random.randint(0, 255)/255.0)
111
112
113def plot(matrix, C, k):
114    colors = []
115    for i in range(k):
116        colors.append(randRGB())
117    for idx, value in enumerate(C):
118        try:
119            plt.plot(matrix[idx][0], matrix[idx][1],
120                     'o', color=colors[int(C[idx])])
121        except:
122            pass
123    plt.show()
124
125
126if __name__ == '__main__':
127    pixel_vector = loadIMG("./test.jpg")
128    # print(pixel_vector)
129    cluster_num = 2
130    KNN_k = 15
131    data = loaddata()
132    W = getWbyKNN(pixel_vector, KNN_k)
133    # 相似度矩阵
134    D = getD(W)
135    # 度矩阵
136    L = D-W
137    # 拉普拉斯矩阵
138    eigval, eigvec = getEigVec(L, cluster_num)
139
140    clf = KMeans(n_clusters=cluster_num)
141    # 新建类对象
142    print(eigvec.real)
143    s = clf.fit(eigvec.real)
144    # 开始聚类
145    plot(pixel_vector, s.labels_, cluster_num)
146
效果

原图:
92f0bd474713926fb6342748f60070d8.jpg

聚类后:

Figure1.png


标题:谱聚类再次整理
作者:Hanmengnan
地址:https://www.wendau.com/articles/2019/12/22/1584887780279.html