开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> 计算机视觉编程第六章图像聚类 -> 正文阅读

[人工智能]计算机视觉编程第六章图像聚类

6.1K-means聚类

????K-means是一种将输入数据划分成k个簇的简单的聚类算法。K-means反复提炼初始评估的类中心，步骤如下：
????输入： 样本集D，簇的数目k，最大迭代次数N；
????输出： 簇划分（k个簇，使平方误差最小）；
????1、以随机或猜测的方式初始化类中心 $\pmb u_{i}$ ，i=1…k;
????2、将每个数据点归并到离它距离最近的类中心所属的类 $c_{i}$ ；
????3、对所有属于该类的数据点求平均，将平均值作为新的类中心；（注：常用的距离度量方法包括：欧几里得距离和余弦相似度。两者都是评定个体间差异的大小的。欧几里得距离度量会受指标不同单位刻度的影响，所以一般需要先进行标准化。余弦相似度倾向给出更优解。）
????4、重复步骤2和3直到收敛。
????K-means试图使类内总方差最小：
$V=\sum_{i=1}^{k}\sum_{\pmb x_{i}\in c_{i}}(\pmb x_{j}-\pmb \mu_{i})^{2}$
$\pmb x_{j}$ 是输入数据，并且是矢量。为了避免初始化类中心时没选取好类中心初值所造成的影响，该算法通常会初始化不同的类中心进行多次运算，然后选择方差V最小的结果。
????K-means算法最大的缺陷是必须预先设定聚类数k，如果选择不恰当则会导致聚类出来的结果很差。其有点是容易实现，可以并行计算，并且对于很多别的问题不需要任何调整就能直接使用。

6.1.1SciPy聚类包

????SciPy矢量量化包scipy.cluster.vq中有K-means的实现。
代码：

# -*- coding: utf-8 -*-

#导入scipy中K-means的相关工具
from scipy.cluster.vq import *

#randn是NumPy中的一个函数
from numpy import *
from pylab import *

#生成简单的二维数据:生成两类二维正态分布数据
class1 = 1.5 * randn(100,2)
class2 = randn(100,2) + array([5,5])
features = vstack((class1,class2))

#用 k=2 对这些数据进行聚类:
centroids,variance = kmeans(features,2)

"""
由于 SciPy 中实现的 K-means 会计算若干次(默认为 20 次),并为我们选择方差最
小的结果,所以这里返回的方差并不是我们真正需要的。
"""

#用 SciPy 包中的矢量量化函数对每个数据点进行归类:通过得到的 code ,我们可以检查是否有归类错误
code,distance = vq(features,centroids)

#可视化结果：画出这些数据点及最终的聚类中心：函数 where() 给出每个类的索引
figure()
ndx = where(code==0)[0]
plot(features[ndx,0],features[ndx,1],'*')
ndx = where(code==1)[0]
plot(features[ndx,0],features[ndx,1],'r.')
plot(centroids[:,0],centroids[:,1],'go')
axis('off')
show()

结果：
在这里插入图片描述
分析：
????上图显示了原数据聚完类后的结果，绿色圆点表示聚类中心，预测出的类分别标记为蓝色星号和红色点。

6.1.2图像聚类

????文件selectedfontimeages.zip包含66幅来自该字体数据集fontinages的图像（为了便于说明这些聚类簇，选择这些图像做简单概述）。利用之前计算过的前40个主成分进行投影，用投影系数作为每幅图像的向量描述符。用pickle模块载入模型文件，在主成分上对图像进行投影，然后用下面的方法聚类：
代码：

# -*- coding: utf-8 -*-
from PCV.tools import imtools
import pickle
from scipy import *
from pylab import *
from PIL import Image
from scipy.cluster.vq import *
from PCV.tools import pca

# Uses sparse pca codepath.
imlist = imtools.get_imlist(r'E:\桌面\data\selectedfontimages\a_selected_thumbs')

# 获取图像列表和他们的尺寸
im = array(Image.open(imlist[0]))  # open one image to get the size
m, n = im.shape[:2]  # get the size of the images
imnbr = len(imlist)  # get the number of images
print("The number of images is %d" % imnbr)

# Create matrix to store all flattened images
immatrix = array([array(Image.open(imname)).flatten() for imname in imlist], 'f')

# PCA降维
V, S, immean = pca.pca(immatrix)

# 保存均值和主成分
f = open(r'E:\桌面\data\selectedfontimages\font_pca_modes.pkl', 'wb')
pickle.dump(immean, f)
pickle.dump(V, f)
f.close()

# 获取 selected-fontimages 文件下图像文件名，并保存在列表中
imlist = imtools.get_imlist(r'E:\桌面\data\selectedfontimages\a_selected_thumbs')
imnbr = len(imlist)

# 载入模型文件
with open(r'E:\桌面\data\selectedfontimages\font_pca_modes.pkl', 'rb') as f:
    immean = pickle.load(f)
    V = pickle.load(f)
# 创建矩阵，存储所有拉成一组形式后的图像
immatrix = array([array(Image.open(im)).flatten() for im in imlist], 'f')

# 投影到前 40 个主成分上
immean = immean.flatten()
projected = array([dot(V[:40], immatrix[i] - immean) for i in range(imnbr)])

# 进行 k-means 聚类
projected = whiten(projected)
centroids, distortion = kmeans(projected, 4)
code, distance = vq(projected, centroids)

# 绘制聚类簇
for k in range(4):
    ind = where(code == k)[0]
    figure()
    gray()
    for i in range(minimum(len(ind), 40)):
        subplot(4, 10, i + 1)
        imshow(immatrix[ind[i]].reshape((25, 25)))
        axis('off')
show()

结果：
在这里插入图片描述
分析：
????程序中设定的聚类数k=4。我们可以试着改变其中的参数，比如主成分数目和k，观察聚类结果有何变化。

6.1.3在主成分上可视化图像

????为了便于观察上面是如何利用主成分进行聚类的，我们可以在一对主成分方向的坐标上可视化这些图像。一种方法是将图像投影到两个主成分上，改变投影为：projected = array([dot(V[[0,2]],immatrix[i]-immean) for i in range(imnbr)])。以得到相应的坐标（在这里 V[[0,2]] 分别是第一个和第三个主成分）。当然，也可以将其投影到所有成分上，之后挑选出需要的列。
代码：

# -*- coding: utf-8 -*-
from PCV.tools import imtools, pca
from PIL import Image, ImageDraw
from pylab import *
from PCV.clustering import hcluster

imlist = imtools.get_imlist(r'E:\桌面\data\selectedfontimages\a_selected_thumbs')
imnbr = len(imlist)

# Load images, run PCA.
immatrix = array([array(Image.open(im)).flatten() for im in imlist], 'f')
V, S, immean = pca.pca(immatrix)

# Project on 2 PCs.
#projected = array([dot(V[[0, 1]], immatrix[i] - immean) for i in range(imnbr)])
projected = array([dot(V[[1, 2]], immatrix[i] - immean) for i in range(imnbr)])

# 高和宽
h, w = 1200, 1200

# 创建一幅白色背景图
img = Image.new('RGB', (w, h), (255, 255, 255))
draw = ImageDraw.Draw(img)

# 绘制坐标轴
draw.line((0, h / 2, w, h / 2), fill=(255, 0, 0))
draw.line((w / 2, 0, w / 2, h), fill=(255, 0, 0))

# 缩放以适应坐标系
scale = abs(projected).max(0)
scaled = floor(array([(p / scale) * (w / 2 - 20, h / 2 - 20) + (w / 2, h / 2)
                      for p in projected])).astype(int)

# 粘贴每幅图像的缩略图到白色背景图片
for i in range(imnbr):
    nodeim = Image.open(imlist[i])
    nodeim.thumbnail((25, 25))
    ns = nodeim.size
    box = (scaled[i][0] - ns[0] // 2, scaled[i][1] - ns[1] // 2,
           scaled[i][0] + ns[0] // 2 + 1, scaled[i][1] + ns[1] // 2 + 1)
    img.paste(nodeim, box)

#这是生成聚类树
#tree = hcluster.hcluster(projected)
#hcluster.draw_dendrogram(tree, imlist, filename='fonts.png')

figure()
imshow(img)
axis('off')
img.save('D:\\CV\\pca_font.png')
show()

结果：
在这里插入图片描述
分析：
????左图用的是第一个和第二个主成分，右图用的是第二个和第三个成分。
????这里，我们用到了整数或 floor 向下取整除法运算符 //，通过移去小数点后面的部分，可以返回各个缩略图在白色背景中对应的整数坐标位置。可以很清楚地看到，二维投影后相似的字体图像距离较近。

6.1.4像素聚类

????将图像区域或像素合并成有意义的部分称为图像分割。单纯在像素水平上应用 K-means可以用于一些简单图像的图像分割，但是对于复杂图像得出的结果往往是毫无意义的。要产生有意义的结果，往往需要更复杂的类模型而非平均像素色彩或空间一致性。
????下面在RGB三通道的像素值上运用K-means进行聚类：
代码：

# -*- coding: utf-8 -*-

from scipy.cluster.vq import *
#from scipy.misc import imresize
from PCV.tools.imtools import imresize
from pylab import *
from PIL import Image

# 添加中文字体支持
from matplotlib.font_manager import FontProperties

font = FontProperties(fname=r"c:\windows\fonts\SimSun.ttc", size=14)


def clusterpixels(infile, k, steps):
    im = array(Image.open(infile))
    #dx = im.shape[0] / steps
    #dy = im.shape[1] / steps
    dx = im.shape[0] // steps
    dy = im.shape[1] // steps
    # compute color features for each region
    features = []
    for x in range(steps):
        for y in range(steps):
            #R = mean(im[x * dx:(x + 1) * dx, y * dy:(y + 1) * dy, 0])
            #G = mean(im[x * dx:(x + 1) * dx, y * dy:(y + 1) * dy, 1])
            #B = mean(im[x * dx:(x + 1) * dx, y * dy:(y + 1) * dy, 2])
            R = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 0])
            G = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 1])
            B = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 2])
            features.append([R, G, B])
    features = array(features, 'f')  # make into array
    # 聚类， k是聚类数目
    centroids, variance = kmeans(features, k)
    code, distance = vq(features, centroids)
    # create image with cluster labels
    codeim = code.reshape(steps, steps)
    #codeim = imresize(codeim, im.shape[:2], 'nearest')
    codeim = imresize(codeim, im.shape[:2])
    #codeim = skimage.transform.resize(codeim, im.shape[:2], 'nearest')
    return codeim


k = 3
infile_empire = 'D:\\CV\\empire.jpg'
im_empire = array(Image.open(infile_empire))
infile_boy_on_hill = 'D:\\CV\\boy_on_hill.jpg'
im_boy_on_hill = array(Image.open(infile_boy_on_hill))
steps = (50, 100)  # image is divided in steps*steps region
print(steps[0], steps[-1])

# 显示原图empire.jpg
figure()
subplot(231)
title(u'原图', fontproperties=font)
axis('off')
imshow(im_empire)

# 用50*50的块对empire.jpg的像素进行聚类
codeim = clusterpixels(infile_empire, k, steps[0])
subplot(232)
title(u'k=3,steps=50', fontproperties=font)
# ax1.set_title('Image')
axis('off')
imshow(codeim)

# 用100*100的块对empire.jpg的像素进行聚类
codeim = clusterpixels(infile_empire, k, steps[-1])
ax1 = subplot(233)
title(u'k=3,steps=100', fontproperties=font)
# ax1.set_title('Image')
axis('off')
imshow(codeim)

# 显示原图empire.jpg
subplot(234)
title(u'原图', fontproperties=font)
axis('off')
imshow(im_boy_on_hill)

# 用50*50的窗口对empire.jpg的像素进行聚类
codeim = clusterpixels(infile_boy_on_hill, k, steps[0])
subplot(235)
title(u'k=3,steps=50', fontproperties=font)
# ax1.set_title('Image')
axis('off')
imshow(codeim)

# 用100*100的窗口对empire.jpg的像素进行聚类
codeim = clusterpixels(infile_boy_on_hill, k, steps[-1])
subplot(236)
title(u'k=3，steps=100', fontproperties=font)
axis('off')
imshow(codeim)

show()

结果：
在这里插入图片描述

分析：
????K-means 的输入是一个有 steps×steps 行的数组，数组的每一行有 3 列，各列分别为区域块 R、G、B 三个通道的像素平均值。为可视化最后的结果 , 用 SciPy 的 imresize() 函数在原图像坐标中显示这幅 steps×steps 的图像。参数 interp 指定插值方法；采用最近邻插值法，以便在类间进行变换时不需要引入新的像素值。K-means 标签的次序是任意的（在这里的标签指最终结果中图像的颜色）。正如看到的，尽管利用窗口对它进行了下采样，但结果仍然是有噪声的。如果图像某些区域没有空间一致性，则很难将它们分开，如图中小男孩和草坪的图。
????实验过程中报错1：ImportError: cannot import name ‘imresize’ from ‘scipy.misc’
在这里插入图片描述
通过查找资料发现这是由于Scipy.misc这个工具包已经在版本1.2.0以后停止使用了，使用PCV.tools.imtools中的imresize()函数来替代。

注意：PCV.tools.imtools中的imresize()函数只有两个参数，因此需要删除参数interp：
在这里插入图片描述
????报错2：TypeError: slice indices must be integers or None or have an index method

这是因为存在带除法的操作，“/”会生成浮点数，当“ []”中的数据变成了浮点数，不能作为数组下标。需要将除法符号 “/”更改成“//” 或者将数据 强制转换为int整型类型。
在这里插入图片描述

6.2层次聚类

????层次聚类（或凝聚式聚类）是另一种简单但有效的聚类算法，其思想是基于样本间成对距离建立一个简相似性树。该算法首先将特征向量距离最近的两个样本归并为一组，并在树中建立一个”平均“节点，将这两个距离最近的样本作为该”平均“节点下的子节点；然后再剩下的包含任意平均节点的样本中寻找下一个最近的对，重复进行前面的操作。在每一个节点处保存了两个子节点之间的距离。遍历整个树，通过设定的阈值，遍历过程可以在比阈值大的节点位置终止，从而提取出聚类簇。
????层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。分裂层次聚类采用的就是"自顶而下"的思想，先将所有的样本都看作是同一个簇，然后通过迭代将簇划分为更小的簇，直到达到某个终结条件(簇数目或者簇距离达到阈值)。凝聚层次聚类采用的是"自底向上"的思想，先将每一个样本都看成是一个不同的簇，通过重复将最近的一对簇进行合并，直到所有的对象满足簇数目。
????在凝聚层次聚类中，判定簇间距离的两个标准方法就是单连接(single linkage)和全连接(complete linkage)。单连接，是计算每一对簇中最相似两个样本的距离，并合并距离最近的两个样本所属簇。全连接，通过比较找到分布于两个簇中最不相似的样本(距离最远)，从而来完成簇的合并。还可以通过平均连接(average linkage)。使用平均连接时，合并两个簇所有成员间平均距离最小的两个簇。优势是可以通过绘制树状图(dendrogram)，帮助我们使用可视化的方式来解释聚类结果。并且不需要事先指定簇的数量。

举例：基于全连接的凝聚层次聚类
????1、主要包括下面几个步骤：
????2、获取所有样本的距离矩阵
????3、将每个数据点作为一个单独的簇
????4、基于最不相似(距离最远)样本的距离，合并两个最接近的簇
????5、更新样本的距离矩阵
????6、重复2到4，直到所有样本都属于同一个簇为止。

下面通过代码来实现上面的操作：
1、获取样本
????随机产生6个样本，每个样本包含3个特征(x，y，z)。

import pandas as pd
import numpy as np

if __name__ == "__main__":
    np.random.seed(1)
    # 设置特征的名称
    variables = ["x", "y", "z"]
    # 设置编号
    labels = ["s1", "s2", "s3", "s4", "s5", "s6"]
    # 产生一个(6,3)的数组
    data = np.random.random_sample([6, 3]) * 10
    # 通过pandas将数组转换成一个DataFrame
    df = pd.DataFrame(data, columns=variables, index=labels)
    # 查看数据
    print(df)

在这里插入图片描述
2、获取所有样本的距离矩阵
????通过SciPy来计算距离矩阵，计算每个样本间两两的欧式距离，将矩阵矩阵用一个DataFrame进行保存，方便查看。

from scipy.spatial.distance import pdist,squareform
#获取距离矩阵
'''
pdist:计算两两样本间的欧式距离,返回的是一个一维数组
squareform：将数组转成一个对称矩阵
'''
dist_matrix = pd.DataFrame(squareform(pdist(df,metric="euclidean")),
                columns=labels,index=labels)
print(dist_matrix)

在这里插入图片描述
3、获取全连接矩阵的关联矩阵
????通过scipy的linkage函数，获取一个以全连接作为距离判定标准的关联矩阵。

from scipy.cluster.hierarchy import linkage

# 以全连接作为距离判断标准，获取一个关联矩阵
row_clusters = linkage(dist_matrix.values, method="complete", metric="euclidean")
# 将关联矩阵转换成为一个DataFrame
clusters = pd.DataFrame(row_clusters, columns=["label 1", "label 2", "distance", "sample size"],
                        index=["cluster %d" % (i + 1) for i in range(row_clusters.shape[0])])
print(clusters)

在这里插入图片描述
4、绘制树状图
????通过关联矩阵绘制树状图，使用scipy的dendrogram来绘制树状图。

from scipy.cluster.hierarchy import dendrogram
import matplotlib.pyplot as plt

row_dendr = dendrogram(row_clusters, labels=labels)
plt.tight_layout()
plt.ylabel("欧式距离")
plt.show()

在这里插入图片描述
????通过上面的树状图，可以看到，首先是s1和s5合并，s4和s6合并，s2和s3合并，然后s2、s3、s4、s6合并，最后再和s1、s5合并。

图像聚类

????接下来完成一个基于图像颜色信息对图像进行聚类的例子。
创建文件hcluster.py，将下面代码添加进去：

from itertools import combinations
from pylab import *

class ClusterNode(object):
    def __init__(self,vec,left,right,distance=0.0,count=1):
        self.left = left
        self.right = right
        self.vec = vec
        self.distance = distance
        self.count = count

    def extract_clusters(self, dist):
        """从层次聚类树中提取距离小于dist的子树簇群列表"""
        if self.distance < dist:
            return [self]
        return self.left.extract_clusters(dist) + self.right.extract_clusters(dist)

    def get_cluster_elements(self):
        """在聚类子树中返回元素的id"""
        return self.left.get_cluster_elements() + self.right.get_cluster_elements()

    def get_height(self):
        """返回节点的高度，高度是各分支的和"""
        return self.left.get_height() + self.right.get_height()

    def get_depth(self):
        """返回节点的深度，深度是每个子节点取最大再加上它的自身距离"""
        return max(self.left.get_depth(), self.right.get_depth()) + self.distance

class ClusterLeafNode(object):
    def __init__(self,vec,id):
        self.vec = vec
        self.id = id

    def extract_clusters(self, dist):
        return [self]

    def get_cluster_elements(self):
        return [self.id]

    def get_height(self):
        return 1

    def get_depth(self):
        return 0

    def L2dist(v1,v2):
        return sqrt(sum((v1-v2)**2))

    def L1dist(v1,v2):
        return sum(abs(v1-v2))

    def hcluster(features,distfcn=L2dist):
        """用层次聚类对行特征进行聚类"""
        # 用于保存计算出的距离
        distances = {}

        # 每行初始化为一个簇
        node = [(ClusterLeafNode(array(f), id=i) for i, f in enumerate(features))]

        while len(node) > 1:
            closet = float('Inf')

            # 遍历每对，寻找最小距离
            for ni, nj in combinations(node, 2):
                if (ni, nj) not in distances:
                    distances[ni, nj] = distfcn(ni.vec, nj.vec)

                d = distances[ni, nj]
                if d < closet:
                    closet = d
                    lowestpair = (ni, nj)
                ni, nj = lowestpair

                # 对两个簇求平均
                new_vec = (ni.vec + nj.vec) / 2.0

                # 创建新的节点
                new_node = ClusterNode(new_vec, left=ni, right=nj, distance=closet)
                node.remove(ni)
                node.remove(nj)
                node.append(new_node)
        return node[0]

????可以通过PCV.clustering来导入hcluster模块，也可以直接导入我们上面创建的hcluster.py。
完整代码：

# -*- coding: utf-8 -*-
import os
from PCV.clustering import hcluster
from matplotlib.pyplot import *
from numpy import *
from PIL import Image

# 创建图像列表
path = 'E:\\桌面\data\sunsets\\flickr-sunsets-small\\'
imlist = [os.path.join(path, f) for f in os.listdir(path) if f.endswith('.jpg')]
# 提取特征向量，每个颜色通道量化成 8 个小区间
features = zeros([len(imlist), 512])
for i, f in enumerate(imlist):
    im = array(Image.open(f))
    # 多维直方图
    h, edges = histogramdd(im.reshape(-1, 3), 8, normed=True, range=[(0, 255), (0, 255), (0, 255)])
    features[i] = h.flatten()
tree = hcluster.hcluster(features)

# 设置一些（任意的）阈值以可视化聚类簇
clusters = tree.extract_clusters(0.23 * tree.distance)
# 绘制聚类簇中元素超过 3 个的那些图像
for c in clusters:
    elements = c.get_cluster_elements()
    nbr_elements = len(elements)
    if nbr_elements > 3:
        figure()
        for p in range(minimum(nbr_elements, 20)):
            subplot(4, 5, p + 1)
            im = array(Image.open(imlist[elements[p]]))
            imshow(im)
            axis('off')
show()

hcluster.draw_dendrogram(tree, imlist, filename='sunset.pdf')

结果：
用100 幅日落图像进行层次聚类的示例聚类簇：
在这里插入图片描述

日落图像聚类后的树状图：

分析：
????树状图的高和子部分由距离决定，随着坐标向下传递到下一级，会递归绘制出这些节点，上述代码用 20×20 像素绘制叶节点的缩略图，使用 get_height() 和 get_depth() 这两个辅助函数可以获得树的高和宽。最后展示了日落图像层次聚类后的树状图。可以看到，树中挨的相近的图像具有相似的颜色分布。
????同样可以对前面的字体创建一个树状图：

tree = hcluster.hcluster(projected)
hcluster.draw_dendrogram(tree, imlist, filename=‘fonts.png’)

在这里插入图片描述

6.3谱聚类

????谱：方阵作为线性算子，它的所有特征值的全体统称为方阵的谱。方阵的谱半径为最大的特征值。矩阵 $\pmb A$ 的谱半径是矩阵 $\pmb A^{T}\pmb A$
的最大特征值。
????谱聚类： 是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的谱。谱聚类可以理解为将高维空间的数据映射到低维，然后在低维空间用其它聚类算法（如K-Means）进行聚类。
????谱聚类的过程： 给定一个n×n的相似性矩阵 $\pmb S$ ， $s_{ij}$ 为相似性分数，可以创建一个矩阵，称为拉普拉斯矩阵：
$\pmb L=\pmb I-\pmb D^{-1/2}\pmb S\pmb D^{-1/2}$
其中， $\pmb I$ 是单位矩阵， $\pmb D$ 是对角矩阵，对角线上的元素是 $\pmb S$ 对应行元素之和， $D=diag(d_{i}),d_{i}=\sum_{j}s_{ij}$ 。拉普拉斯矩阵中的 $\pmb D^{-1/2}$ 为：
$\pmb D^{-1/2}=\begin{bmatrix} \frac{1}{\sqrt{d_{1}}} & & & \\ & \frac{1}{\sqrt{d_{2}}} & & \\ & & \ddots & \\ & & & \frac{1}{\sqrt{d_{n}}} \end{bmatrix}$
????为了使表述更简洁，对于相似性矩阵中的元素 $s_{ij}$ ，使用较小的值并且要求 $s_{ij}≥0$ （在这种情况下，距离矩阵可能更合适）。
????计算 $\pmb L$ 的特征向量，并使用k个最大特征值对应的k个特征向量，构建出一个特征向量集，从而可以找到聚类簇。创建一个矩阵，该矩阵的各列是由之前求出的k个特征向量构成，每一行可以看作一个新的特征向量，长度为k。本质上，谱聚类算法是将原始空间中的数据转换成更容易聚类的新特征向量。

谱聚类的优点：
????1、仅仅需要输入相似性矩阵，并且可以采用所想到的任何度量方式构建该相似性矩阵。正如，K-means和层次聚类需要计算特征向量求平均；而对于谱聚类，特征向量没类别限制，只要有一个“距离”或者“相似性”的概念即可。
????2、当聚类的类别个数较小的时候，谱聚类的效果会很好，但是当聚类的类别个数较大的时候，则不建议使用谱聚类；
????3、谱聚类算法使用了降维的技术，所以更加适用于高维数据的聚类；
????4、谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解。

谱聚类的缺点：
????1、谱聚类对相似度图的改变和聚类参数的选择非常的敏感；
????2、谱聚类适用于均衡分类问题，即各簇之间点的个数相差不大，对于簇之间点个数相差悬殊的聚类问题，谱聚类则不适用。

下面使用拉普拉斯矩阵的特征向量对字体图像进行谱聚类：
代码：

# -*- coding: utf-8 -*-
from PCV.tools import imtools, pca
from PIL import Image
from pylab import *
from scipy.cluster.vq import *

imlist = imtools.get_imlist(r'E:\桌面\data\fontimages\a_thumbs')
imnbr = len(imlist)

# Load images, run PCA.
immatrix = array([array(Image.open(im)).flatten() for im in imlist], 'f')
V, S, immean = pca.pca(immatrix)

# Project on 2 PCs.
projected = array([dot(V[[0, 1]], immatrix[i] - immean) for i in range(imnbr)])

n = len(projected)
# 计算距离矩阵
S = array([[sqrt(sum((projected[i] - projected[j]) ** 2))
            for i in range(n)] for j in range(n)], 'f')
# 创建拉普拉斯矩阵
rowsum = sum(S, axis=0)
D = diag(1 / sqrt(rowsum))
I = identity(n)
L = I - dot(D, dot(S, D))
# 计算矩阵 L 的特征向量
U, sigma, V = linalg.svd(L)
k = 5
# 从矩阵 L 的前k个特征向量（eigenvector）中创建特征向量（feature vector） # 叠加特征向量作为数组的列
features = array(V[:k]).T
# k-means 聚类
features = whiten(features)
centroids, distortion = kmeans(features, k)
code, distance = vq(features, centroids)
# 绘制聚类簇
for c in range(k):
    ind = where(code == c)[0]
    figure()
    gray()
    for i in range(minimum(len(ind), 39)):
        im = Image.open(imlist[ind[i]])
        subplot(4, 10, i + 1)
        imshow(array(im))
        axis('equal')
        axis('off')
show()