实习聚类的技术路线

思维导图

数据聚类和引例

基于图论的聚类算法

算法流程

1构造数据

导入库

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn import datasets
from sklearn.preprocessing import StandardScaler
from scipy.linalg import sqrtm as sqrtm

会生成两个圆环，factor会设置两个圆的相对比例，noise设置噪点的比例

np.random.seed(0)n_samples = 500;
# 样本数据的数量
#factor会设置圆的半径，
dataset = datasets.make_circles(n_samples=n_samples, factor=.5,noise=.05)
# 生成环形数据X, y = dataset
# X 特征数据，y 标签数据
X = StandardScaler().fit_transform(X)
# 标准化数据集

# 可视化散点
fig, ax = plt.subplots(figsize = (6,6))plt.scatter(X[:,0],X[:,1])
ax.set_aspect('equal', adjustable='box')
# plt.savefig('散点图.svg')

构造距离矩阵

成对距离矩阵

# 计算成对距离矩阵
D = np.linalg.norm(X[:, np.newaxis, :] - X, axis=2)
# 请尝试使用
# scipy.spatial.distance_matrix()
# sklearn.metrics.pairwise_distances()

这段代码是计算数据集中的点之间的成对距离矩阵。让我们逐步解析这段代码：

1. np.linalg.norm()：这是 numpy 中的一个函数，用于计算矩阵（或向量）的范数。在这里，我们使用它来计算两点之间的距离。

2. X[:, np.newaxis, :] - X：这是创建一个扩展的 X 矩阵，使其具有与 X 相同的形状，只是维度增加了。np.newaxis 用于在给定的维度上增加一个轴。例如，如果 X 的形状是 (n_samples, n_features)，那么 X[:, np.newaxis, :] 的形状将变为 (n_samples, 1, n_features)。
   X现在的shape是(500,2)

3. axis=2：这是 np.linalg.norm() 函数的参数，用于指定计算范数时沿轴的计算。在这里，我们使用 axis=2 因为我们要计算的是两点之间的距离，所以我们需要沿第三个轴（即特征轴）计算范数。

所以，这段代码的目的是计算数据集中每个点与其他所有点之间的成对距离。结果 D 是一个二维矩阵，其中每个元素都是两个点之间的距离。

例如，如果 X 的形状是 (n_samples, n_features)，那么 D 的形状将是 (n_samples, n_samples)。

如果两个数组维度不一致，但是后缘维度的轴长相符，则可以广播
如果两个数组维度数量一致（比如都是三维），其中有一个轴为1，则含有1的这个数组会沿着1这个轴进行广播

一个示例:

array(
[[[1, 2]],
[[3, 4]],
[[5, 6]]])

re =X1 - X

array([[[ 0, 0],
[-2, -2],
[-4, -4]],
[[ 2, 2],
[ 0, 0],
[-2, -2]],
[[ 4, 4],
[ 2, 2],
[ 0, 0]]])

中间那个维度的数据是计算结果，使用二维欧氏距离平方和来计算。
示例数据的结果

# 可视化成对距离矩阵
plt.figure(figsize=(8,8))
sns.heatmap(D, square = True, cmap = 'Blues', # annot=True, fmt=".3f",xticklabels = [], yticklabels = [])
# plt.savefig('成对距离矩阵_heatmap.svg')

书上的解释

相似度

高斯核函数：距离到相似度

$$s_{i,j}=\exp \left(-{\left(\frac{d_{i,j}}{\sigma }\right)}^2\right)$$
这个公式的意义在于把一个距离给非线性归一化到（0，1）之间，参数的意义

σ（sigma）是一个重要的参数，它被称为带宽（bandwidth）或尺度参数（scale parameter）。

1. 控制相似度衰减速率：σ控制着相似度随距离增加而衰减的速率。较大的σ值会导致相似度随距离增加而缓慢衰减，而较小的σ值会导致相似度急剧衰减。
2. 定义"邻近"的范围：σ实际上定义了什么被认为是"邻近的"。大约在距离d = σ时，相似度下降到exp(-1) ≈ 0.368。
3. 平滑参数：在某些应用中，σ被视为平滑参数。较大的σ会产生更平滑的相似度分布。
4. 特征尺度：σ反映了特征空间的特征尺度。它应该与数据点之间的典型距离相匹配。
5. 影响模型的复杂性：在机器学习应用中（如支持向量机），σ影响模型的复杂性。较小的σ可能导致过拟合，而较大的σ可能导致欠拟合。
   选择适当的σ值对于许多应用来说是至关重要的。通常，σ的选择可以通过交叉验证或其他模型选择技术来优化。

相似度矩阵

代码：

# 自定义高斯核函数
def gaussian_kernel(distance, sigma=1.0):return np.exp(- (distance ** 2) / (2 * sigma ** 2))
#调用计算
S = gaussian_kernel(D,3)
# 参数sigma设为3# 可视化亲近度矩阵
plt.figure(figsize=(8,8))
sns.heatmap(S, square = True, cmap = 'viridis', vmin = 0, vmax = 1,# annot=True, fmt=".3f",xticklabels = [], yticklabels = [])
# plt.savefig('亲近度矩阵_heatmap.svg')

生成的500的加annot的无法可视化（效果不好）

创建图

代码：

创建图的代码

# 创建无向图
S_copy = np.copy(S)
#填充到对角矩阵，把对角线的值设置为0
np.fill_diagonal(S_copy, 0)
#使用NetworkX库中的Graph类创建了一个图对象G，点的类型是整型，
#此处边直接根据邻接非零元素进行了创建
G = nx.Graph(S_copy, nodetype=int)
# 用邻接矩阵创建无向图# 添加节点位置
for i in range(len(X)):G.add_node(i, pos=(X[i, 0], X[i, 1]))  
#如果希望手动添加边需要调用
#G.add_edge()# 取出节点位置
pos = nx.get_node_attributes(G, 'pos')# 增加节点属性
node_labels = {i: chr(ord('a') + i) for i in range(len(G.nodes))} 
#返回字母 'a' 的ASCII码值，添加后，在转变回字符
edge_weights = [G[i][j]['weight'] for i, j in G.edges]
#边的权重通过上面的方式直接访问

可视化图

# 可视化图
fig, ax = plt.subplots(figsize = (6,6))
nx.draw_networkx(G, pos, with_labels=False, node_size=38, node_color='blue', font_color='black', edge_cmap=plt.cm.viridis,edge_color=edge_weights,width=1, alpha=0.5)ax.set_aspect('equal', adjustable='box')
ax.axis('off')
# plt.savefig('成对距离矩阵_无向图.svg')

G 是一个networkx图对象，包含了节点和边。
pos 是一个字典，定义了每个节点的位置。
with_labels=False 表示不显示节点标签。
node_size=38 设置节点的大小。
node_color=‘blue’ 设置节点的颜色为蓝色。
font_color=‘black’ 设置节点标签的颜色为黑色（这里没有显示节点标签，所以这行代码实际上没有效果）。
edge_cmap=plt.cm.viridis 设置边的颜色映射为viridis颜色映射。
edge_color=edge_weights 设置边的颜色为edge_weights变量中的值，这通常是一个包含边权重的列表或数组。
width=1 设置边的宽度。
alpha=0.5 设置边的透明度。
用途：
这段代码的用途是可视化一个图，其中节点用蓝色表示，边的颜色根据edge_weights变量中的值进行映射，边是半透明的。这种可视化方法常用于展示网络结构，例如社交网络、交通网络等

拉普拉斯矩阵

先看度矩阵。

在构造拉普拉斯矩阵之前我们要先构造度矩阵，拉普拉斯矩阵有三种。
此处介绍一下拉普拉斯矩阵：
拉普拉斯矩阵是图论中用于分析图结构的重要工具。根据应用场景和图的类型，有三种常见的拉普拉斯矩阵，它们在图的研究中扮演不同的角色：

先总结一下用途：

• 标准拉普拉斯矩阵：用于无向图，常用于分析图的连通性和谱分解。
• 归一化拉普拉斯矩阵：适用于有权图或节点度数差异较大的图，特别是在谱聚类、图嵌入等领域。
• 无标度拉普拉斯矩阵：主要用于特定的图特性分析，与正负权图的研究有关。

拉普拉斯矩阵L的计算一般围绕度矩阵D和邻接矩阵A展开

标准拉普拉斯矩阵(Combinatorial Laplacian)

标准拉普拉斯矩阵是图的基本拉普拉斯矩阵，定义如下：

定义：
对于一个无向图 𝐺 ，其标准拉普拉斯矩阵 𝐿 定义为：
$$L=D-A$$

示例：

归一化拉普拉斯矩阵 (Normalized Laplacian)

归一化拉普拉斯矩阵是对标准拉普拉斯矩阵进行标准化处理后的矩阵，常用于谱图理论的分析，特别是在处理有权图时。

计算度矩阵的逆平方根（适用于对称归一化拉普拉斯矩阵）
假设 𝐷是一个度矩阵，计算其逆平方根矩阵的方法是对度矩阵的每个非零对角线元素求平方根的倒数。

import numpy as np# 假设这是度矩阵 D
D = np.diag([4, 3, 2, 1])# 计算 D 的逆平方根矩阵
D_inv_sqrt = np.diag(1.0 / np.sqrt(np.diag(D)))print("D 的逆平方根矩阵：")
print(D_inv_sqrt)

度矩阵的逆（适用于随机游走拉普拉斯矩阵）
度矩阵的逆也是对每个非零对角线元素求倒数。

import numpy as np# 假设这是度矩阵 D
D = np.diag([4, 3, 2, 1])# 计算 D 的逆矩阵
D_inv = np.diag(1.0 / np.diag(D))print("D 的逆矩阵：")
print(D_inv)

无标度拉普拉斯矩阵 (Signless Laplacian)

拉普拉斯矩阵与标准拉普拉斯矩阵的定义相似，但它是通过邻接矩阵和度矩阵的相加而不是相减来定义的。
定义：

$$L^{+}=D+A$$
特征
签名拉普拉斯矩阵的特征值常用于分析图的某些特殊性质，特别是与图的有向性和正负权值相关的问题。
它在图的特征分解和某些类型的优化问题中具有独特的应用。

归一化对称拉普拉斯矩阵

$$L_s=G^{-1/2}\left(G-S\right)G^{-1/2}$$


代码：

#计算逆平方根
G_inv_sqr = sqrtm(np.linalg.inv(G))
#计算拉普拉斯矩阵
L_s = G_inv_sqr @ (G - S) @ G_inv_sqr

可视化

# 可视化拉普拉斯矩阵
plt.figure(figsize=(8,8))
sns.heatmap(L_s, square = True, cmap = 'plasma', # annot=True, fmt=".3f",xticklabels = [], yticklabels = [])
# plt.savefig('拉普拉斯矩阵_heatmap.svg')

度矩阵

为了计算拉普拉斯矩阵，要首先计算度矩阵，度矩阵G是一个对角矩阵。
G 的对角线元素是对应相似度矩阵 S 对应列元素之和
$$G_{i,i}=\sum _{j=1}^n{S}_{i,j}$$

可以知道我们计算的是列和

G = np.diag(S.sum(axis = 1))

# 可视化度矩阵
plt.figure(figsize=(8,8))
sns.heatmap(G, square = True, cmap = 'viridis', # linecolor = 'k',# linewidths = 0.05,mask = 1-np.identity(len(G)),vmin = S.sum(axis = 1).min(),vmax = S.sum(axis = 1).max(),# annot=True, fmt=".3f",xticklabels = [], yticklabels = [])
# plt.savefig('度矩阵_heatmap.svg')

特征分解拉普拉斯矩阵

#EIGH这个函数适用于对称或者埃尔米特矩阵
#不是对称或埃尔米特矩阵，应该使用 np.linalg.eig 函数进行特征值分解
eigenValues_s, eigenVectors_s = np.linalg.eigh(L_s)
# 特征值分解# 按特征值从小到大排序
#返回特征值从小到大的序列
idx_s = eigenValues_s.argsort() # [::-1]   
eigenValues_s = eigenValues_s[idx_s]
eigenVectors_s = eigenVectors_s[:,idx_s]

fig, ax = plt.subplots(figsize = (6,6))
plt.plot(range(1,51),eigenValues_s[0:50])
ax.set_xlim(1,50)
ax.set_ylim(0,1)
# plt.savefig('特征值.svg')

# 前两个特征向量的散点图
fig, ax = plt.subplots(figsize = (6,6))plt.scatter(eigenVectors_s[:,0], eigenVectors_s[:,1])
# plt.savefig('散点图，投影后.svg')

拉普拉斯矩阵的几何意义

拉普拉斯矩阵在图论和网络分析中具有深刻的几何意义。它不仅描述了图的结构，还反映了节点之间的相互关系以及图的连通性。

度量节点之间的局部差异性

能量和平滑性

连通性和零特征值

随机游走的动力学解释

谱嵌入（Spectral Embedding）与低维表示

为什么可以进行分离呢？

将环形数据（如同心圆）分割成线性分布的数据，这在某些数据分析和机器学习任务中（例如分类问题）是通过特征变换或映射技术来实现的。这个过程的本质是对数据进行非线性映射，使得原本复杂的结构（如环形或其他非线性结构）在高维空间中变得线性，从而能够使用线性模型进行分割。这种现象的背后有几个主要原因：

1. 非线性映射与高维空间

在处理环形或其他复杂分布数据时，直接使用线性模型（如线性回归或线性分类器）通常无法得到理想的结果，因为数据在原空间是非线性的。例如，两个同心圆的数据无法被简单的直线分开。

为了处理这种非线性结构，我们可以使用非线性映射将数据从原始空间映射到高维空间，使得数据在高维空间中变得更加“可分”。在这个新空间中，原本复杂的结构可能变得接近线性或更加简单。

例子：同心圆数据

假设我们有两组同心圆数据：

• 内圈的数据属于类别 A。
• 外圈的数据属于类别 B。

如果尝试使用一条直线在二维平面中分割它们，显然这是不可能的，因为圆形的结构无法被一条直线分隔开。然而，通过特征映射，我们可以将这些圆形数据转换成一种新的分布方式，使得线性分割变得可能。

常见的映射方法：

一种简单的映射是使用极坐标，将数据从笛卡尔坐标转换为极坐标。假设原始数据为二维坐标系中的 (x,y)，我们可以进行以下变换：

$$\begin{gathered} r=\sqrt{x^2+y^2} \\ \theta =\arctan 2(y,x) \end{gathered}$$

2. 核方法（Kernel Methods）

核方法 是将数据映射到高维空间的另一种强大工具，特别是在支持向量机（SVM）等模型中得到了广泛应用。核方法可以处理非线性数据，将数据从原始空间通过隐式映射提升到更高的维度，使得线性分割成为可能。

核技巧：

• RBF核（径向基核）：RBF核通过计算两个数据点之间的距离，将非线性数据点映射到高维空间中。在这个高维空间中，原本环形的数据可以通过简单的平面或超平面分开。RBF核特别适用于处理环形数据，因为它能将复杂的结构线性化。

  RBF核的形式为：
  $$K(x_i,x_j)=\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)$$

  在使用 RBF 核时，我们不需要显式地进行数据的特征变换，因为 RBF 核通过计算点之间的相似性，隐式地完成了这个变换。

3. 主成分分析（PCA）等降维技术

有时，通过对数据进行降维处理，例如主成分分析（PCA），也可以将复杂的非线性分布转化为一种较为简单的线性形式。虽然 PCA 是一种线性降维技术，但它可以帮助我们找到数据中重要的方向，使得原本复杂的分布在某些主成分方向上变得更加线性。

4. 谱方法（Spectral Methods）

谱聚类和其他基于拉普拉斯矩阵的谱方法通过使用拉普拉斯矩阵的特征向量，能够将复杂的、非线性的数据结构（例如环形结构）转换为线性结构。这种方法的思想是利用图论中的拉普拉斯矩阵来捕捉数据的连通性信息，然后通过特征值分解，将数据映射到一个低维空间中，在这个低维空间中，原本复杂的数据分布变得更加简单，并且可以使用线性模型进行分割。

5. 深度学习与自编码器

自编码器（Autoencoder） 是一种神经网络结构，它可以对数据进行非线性编码和解码。通过训练自编码器，可以学习到一种紧凑的、潜在的线性表示，帮助我们将原本复杂的非线性数据转化为线性可分的数据。深度学习中这种非线性变换的能力，使得复杂的结构能够通过网络的层层变换变得线性。

总结

将环形数据或其他复杂的非线性分布转化为线性可分布结构背后的核心原理是通过非线性映射（如极坐标变换、核方法、深度学习等），将数据嵌入到高维空间中。在新的特征空间中，原本复杂的结构（如环形）可能会展现出简单的线性结构，从而使得线性模型能够对数据进行有效分割。

从方法上看使用了高斯核函数和拉普拉斯矩阵。
使用高斯核函数，我们构造出了非线性的超平面，或者说数据变得线性可分。
我们可以认为拉普拉斯矩阵把数据进行了某种坐标变换。其数据的特征向量，显现出两种线性的分布趋势，使得分割有效。