任务描述 相关知识 谱聚类过程 计算 MSE 均方误差 编程要求 测试说明 任务描述 本关任务：实现谱聚类算法。 相关知识 为了完成本关任务，你需要掌握：1.谱聚类的实现过程，2.计算 MSE 均方误差。 谱聚类过程 如图所示，共有 6 个数据点，根据数据构造一个 Graph ， Graph 的每一个节点对应一个数据点，将相似的点连接起来，并且边的权重用于表示数据之间的相似度。可见 1，2，3 点之间相似度较高， 4，5，6 点之间相似度较高，而 1 和 5 与 3 和 4 之间相似度较低。把这个 Graph 用邻接矩阵的形式表示出来，记为 W。 把W的每一列元素加起来得到 N 个数，把它们放在对角线上（其他地方都是零），组成一个 N*N 的矩阵，记为 D 。 令 L=D-W 。 求出 L 的前 k 个特征值（按照特征值的大小从小到大的顺序）以及对应的特征向量。对数据进行 k=2 的均值聚类，可得到第 5 个和第 6 个特征值最小，故其对应的特征向量为最后两列，组成一个 6*2 的矩阵。 把这 2 个特征（列）向量排列在一起组成一个 6*2 的矩阵，将其中每一行看作二维空间中的一个向量，并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的 6 个数据点分别所属的类别。 计算 MSE 均方误差 MSE 是真实值与预测值的差值的平方然后求和平均。 通过平方的形式便于求导，所以常被用作线性回归的损失函数。 其Python实现代码为： def MSE(y, t): return 0.5 * np.sum((y - t)**2) 使用这个函数来具体计算以下： t = [0, 1, 0, 0] y = [0.1, 0.05, 0.05, 0.8] print(MSE(np.array(y), np.array(t))) t = [0, 1, 0, 0] y = [0.1, 0.8, 0.05, 0.05] print(MSE(np.array(y), np.array(t))) 编程要求 根据提示，在右侧编辑器补充 Python 代码，实现谱聚类算法。 首先我们需要编写完善计算距离平方的矩阵函数，然后完成规范化的谱聚类算法，通过 Sklearn 生成测试数据并将数据使用谱聚类算法处理，最后计算出 MSE 均方误差并将其输出。 完善计算距离平方的矩阵函数； 熟悉计算相似性矩阵函数； 初始化谱聚类算法的初始化参数； 完成训练主函数代码，主要实现其中规范化的谱聚类算法； 使用 Sklearn 库中 make_blobs 方法完成聚类数据的生成，并对聚类数据调用谱聚类方法实现聚类； 完善计算 MSE 均方误差的方法并通过该方法输出计算后的均方误差。 测试说明 平台会对你编写的代码进行测试： 预期输出： True 开始你的任务吧，祝你成功import numpy as np from sklearn.datasets import make_blobs from K_Means import KMEANS class Spectrum: def __init__(self, n_cluster, epsilon=1e-3, maxstep=1000, method='unnormalized', criterion='gaussian', gamma=2.0, dis_epsilon=70, k=5): self.n_cluster = n_cluster self.epsilon = epsilon self.maxstep = maxstep self.method = method # 本程序提供规范化以及非规范化的谱聚类算法 self.criterion = criterion # 相似性矩阵的构建方法 self.gamma = gamma # 高斯方法中的sigma参数 self.dis_epsilon = dis_epsilon # epsilon-近邻方法的参数 self.k = k # k近邻方法的参数 self.W = None # 图的相似性矩阵 self.L = None # 图的拉普拉斯矩阵 self.L_norm = None # 规范化后的拉普拉斯矩阵 self.D = None # 图的度矩阵 self.cluster = None self.N = None # 初始化参数 def init_param(self, data): self.N = data.shape[0] dis_mat = self.cal_dis_mat(data) self.cal_weight_mat(dis_mat) self.D = np.diag(self.W.sum(axis=1)) self.L = self.D - self.W return # 计算距离平方的矩阵 def cal_dis_mat(self, data): dis_mat = np.zeros((self.N, self.N)) for i in range(self.N): for j in range(i + 1, self.N): # 请在此添加实现代码 # # ********** Begin *********# # ********** End ***********# return dis_mat # 计算相似性矩阵 def cal_weight_mat(self, dis_mat): if self.criterion == 'gaussian': # 适合于较小样本集 if self.gamma is None: raise ValueError('gamma is not set') self.W = np.exp(-self.gamma * dis_mat) elif self.criterion == 'k_nearest': # 适合于较大样本集 if self.k is None or self.gamma is None: raise ValueError('k or gamma is not set') self.W = np.zeros((self.N, self.N)) for i in range(self.N): inds = np.argpartition(dis_mat[i], self.k + 1)[:self.k + 1] # 由于包括自身，所以+1 tmp_w = np.exp(-self.gamma * dis_mat[i][inds]) self.W[i][inds] = tmp_w elif self.criterion == 'eps_nearest': # 适合于较大样本集 if self.dis_epsilon is None: raise ValueError('epsilon is not set') self.W = np.zeros((self.N, self.N)) for i in range(self.N): inds = np.where(dis_mat[i] < self.dis_epsilon) self.W[i][inds] = 1.0 / len(inds) else: raise ValueError('the criterion is not supported') return # 训练主函数 def fit(self, data): self.init_param(data) if self.method == 'unnormalized': # 请在此添加实现代码 # # ********** Begin *********# # ********** End ***********# else: raise ValueError('the method is not supported') km = KMEANS(self.n_cluster, self.epsilon, self.maxstep) km.fit(Vectors) self.cluster = km.cluster return if __name__ == '__main__': data, label = make_blobs(centers=3, n_features=10, cluster_std=1.2, n_samples=500, random_state=1) sp = Spectrum(n_cluster=3, method='unnormalized', criterion='gaussian', gamma=0.1) sp.fit(data) cluster = sp.cluster def cal_err(data, cluster): mse = 0 # 计算MSE 均方误差 # 请在此添加实现代码 # # ********** Begin *********# # ********** End ***********# if cal_err(data, cluster) < 1000 and cal_err(data, cluster) > 10: print("True");

<think>根据任务描述，我们需要实现谱聚类算法。谱聚类的步骤包括：1.计算距离平方矩阵（每个点之间的欧氏距离的平方）。2.根据距离矩阵构建相似性矩阵（权重矩阵）W。这里我们使用高斯核函数（gaussian）构建相似性矩阵。3.计算度矩阵D（对角阵，对角线元素为W每一行的和）。4.计算拉普拉斯矩阵L=D-W。5.对于非规范化的谱聚类，直接求拉普拉斯矩阵L的前k个最小特征值对应的特征向量（注意，是最小的特征值，因为拉普拉斯矩阵是半正定矩阵，特征值非负，最小的特征值是0，我们取最小的k个特征值对应的特征向量，除去0对应的那个特征向量）。6.将这些特征向量排列成一个矩阵，每一行是一个样本在降维后的表示。7.使用K-means对降维后的数据进行聚类。另外，在计算距离平方矩阵时，我们不需要开方，因为在高斯核中我们使用的是距离的平方。具体需要完善的函数：1.cal_dis_mat:计算距离平方矩阵（注意，只计算上三角，因为对称矩阵，可以优化速度）。2.在fit函数中，需要补充非规范化谱聚类的特征分解步骤（即求拉普拉斯矩阵L的前k个最小特征值对应的特征向量）。此外，还需要在main函数中补充计算MSE均方误差的函数cal_err。但是注意，谱聚类的聚类结果和原始标签并不是一一对应的，因此直接计算MSE可能不适用（因为K-means的簇标签是任意的）。但是题目要求计算MSE，我们假设任务要求的是聚类内部数据点与其簇中心的距离平方和（类似于K-means的损失函数），即：MSE=所有簇内每个数据点到其簇中心的距离平方和的总和然而，题目描述中给出的MSE公式是线性回归的损失函数（预测值与真实值的差的平方和），但这里我们并没有真实值（标签），所以应该理解为簇内误差平方和（SSE）。在测试中，我们判断SSE是否在10到1000之间。因此，在cal_err函数中，我们将计算每个簇的簇中心，然后计算每个数据点到其簇中心的距离平方和。步骤：1.根据簇分配结果，将数据分成多个簇。2.对于每个簇，计算簇中心（即该簇中所有点的均值）。3.计算每个数据点到其簇中心的距离平方。4.将所有距离平方求和。注意：在谱聚类中，我们得到的是每个数据点被分配到的簇标签（从0开始）。然后我们就可以计算簇内误差平方和。但是注意，我们实现的谱聚类算法中，降维后使用K-means得到的簇标签存储在self.cluster中。具体代码实现：1.在cal_dis_mat函数中，我们计算两两点之间的欧氏距离的平方（注意，对称矩阵，可以只计算一次，然后复制到对称位置）。但为了简单，我们可以计算整个矩阵，但注意不要重复计算，即对于每个i和j（i<j），我们计算一次，然后分别赋值给dis_mat[i,j]和dis_mat[j,i]。2.在fit函数中，对于非规范化的方法，我们需要：-计算拉普拉斯矩阵L（已经由init_param计算得到）-求L的特征值和特征向量（注意，拉普拉斯矩阵是实对称矩阵，特征值是实数）-选择前k个最小的特征值对应的特征向量（k=n_cluster），注意：特征值最小的可能是0（对应全1向量），我们一般跳过0（实际取第2小到第k+1小的特征值对应的特征向量）？但是题目中要求的是k=2，所以取最小特征值中除0外（最小的0特征值对应的特征向量是常数向量，没有信息）的几个。然而，在实际实现中，我们直接取最小的k个特征值对应的特征向量（包括0对应的特征向量）？但是谱聚类的理论告诉我们，对于连通分量为k的图，0特征值恰好是k重。所以实际我们取最小的k个特征向量即可，包括0特征向量。然而，在非规范化的谱聚类中，我们通常取前k个最小特征值对应的特征向量，组成矩阵U（每列为一个特征向量，共k列），然后将每一行（即每个样本的k维表示）进行归一化（可选，但规范化谱聚类要求归一化，非规范化则不一定）？但题目要求是非规范化的谱聚类，所以按题目描述，我们直接取特征向量即可（不需要归一化行向量，但题目描述中没有归一化这一步，所以这里不进行归一化）。然后，我们使用这些特征向量（按行排列）进行K-means聚类。3.由于特征分解时，特征值可能是复数？但拉普拉斯矩阵是实对称的，所以特征值都是实数，特征向量也是实数。具体步骤：在fit函数中（非规范化部分）：计算拉普拉斯矩阵L的特征值和特征向量（使用np.linalg.eigh，因为是对称矩阵，eigh函数更快，且返回的特征值从小到大排序）取前n_cluster个最小的特征值对应的特征向量（即特征向量的前n_cluster列），将这些特征向量组成一个矩阵，每一行对应一个样本。注意：由于我们使用的是实对称矩阵的特征分解，所以特征向量是正交的。我们取特征值排序后最小的k个特征值对应的特征向量。然后，我们用这些特征向量进行K-means聚类。4.在cal_err函数中，我们需要根据聚类结果（cluster）和原始数据data，计算每个簇内误差平方和（SSE）：首先，确定簇的数量（n_cluster）。对于每个簇，找到属于该簇的所有数据点，计算这些点的均值（簇中心）。然后计算每个点到该簇中心的距离平方，并求和。注意：K-means中的损失函数就是SSE。因此，我们可以参考K-means中计算误差平方和的方法。代码实现步骤（cal_err）：sse=0.0forkinrange(n_cluster):cluster_points=data[cluster==k]#选出属于该簇的所有点center=np.mean(cluster_points,axis=0)#计算簇中心#计算每个点到中心的距离平方，并求和diff=cluster_points-centersse+=np.sum(diff**2)returnsse注意：这里的n_cluster可以通过cluster的最大值+1来得到（前提是簇标签从0开始连续编号），但更直接的方法是从传入的cluster中获取唯一值。但是我们在谱聚类时，簇的数量是已知的（self.n_cluster）。然而在cal_err函数中，我们无法直接获取，因此我们需要在函数内部计算簇的数量。注意：簇标签可能不是连续的，但是我们在KMEANS实现中，簇标签是从0开始的连续整数。所以我们可以通过最大簇标签+1来得到簇数量。但是更可靠的方法是使用np.unique获取所有簇标签，然后遍历。不过题目中说生成的测试数据是三个簇，所以我们可以传入簇的数量？但是cal_err函数的签名是cal_err(data,cluster)，没有传入簇数量。我们可以通过len(np.unique(cluster))获取簇数量。因此，在cal_err中：n_cluster=len(np.unique(cluster))然后按照上述步骤计算。但是注意：我们实现的KMEANS中，簇标签是连续整数，所以这样没有问题。现在，我们按照以上步骤来完善代码。注意：在计算距离矩阵时，我们使用双循环，注意效率。因为数据量500个样本，所以可以接受。具体代码实现：1.在cal_dis_mat中：foriinrange(self.N):forjinrange(i+1,self.N):#计算两个点之间的欧氏距离的平方dis=np.sum((data[i]-data[j])**2)dis_mat[i,j]=disdis_mat[j,i]=dis2.在fit函数的非规范化部分：#计算特征值和特征向量eig_vals,eig_vecs=np.linalg.eigh(self.L)#特征值从小到大排列#取前n_cluster个特征向量（最小的n_cluster个特征值对应的特征向量）vectors=eig_vecs[:,:self.n_cluster]#注意：eig_vecs的每一列是一个特征向量，且特征值按升序排列#现在，vectors是一个N×n_cluster的矩阵，每一行是一个样本的n_cluster维特征#我们将其传递给K-meanskm=KMEANS(self.n_cluster,self.epsilon,self.maxstep)km.fit(vectors)#注意：这里传入的vectors是特征向量组成的矩阵，每一行为一个样本self.cluster=km.cluster3.在cal_err中：#获取簇数量labels=np.unique(cluster)sse=0.0forlabelinlabels:points=data[cluster==label]iflen(points)==0:continuecenter=np.mean(points,axis=0)sse+=np.sum((points-center)**2)returnsse注意：由于计算的是误差平方和（SSE），所以不用乘以0.5（题目中给出的MSE公式乘以0.5，但这里不是预测值与真实值，而是簇内误差平方和，我们不乘0.5）。最后，在main中，我们判断sse是否在10到1000之间，然后输出True。注意：由于随机性，我们使用固定随机种子（make_blobs的random_state=1）来保证结果可复现。因此，我们按照上述步骤补充代码。但是注意：在非规范化谱聚类中，我们使用的拉普拉斯矩阵是L=D-W，然后取最小特征值对应的特征向量。在特征分解时，注意拉普拉斯矩阵是实对称矩阵，所以我们使用eigh函数。开始补充代码：</think> 根据任务描述，我们需要实现谱聚类算法。下面我将逐步完善代码并解释每一步的实现： ### 1. 完善计算距离平方矩阵函数 ```python def cal_dis_mat(self, data): dis_mat = np.zeros((self.N, self.N)) for i in range(self.N): for j in range(i + 1, self.N): # 计算欧氏距离的平方（避免开方操作） dis_sq = np.sum((data[i] - data[j]) ** 2) dis_mat[i][j] = dis_sq dis_mat[j][i] = dis_sq return dis_mat ``` 该函数计算所有样本点之间的欧氏距离平方，填充到对称矩阵中。 ### 2. 完善非规范化的谱聚类实现 ```python def fit(self, data): self.init_param(data) if self.method == 'unnormalized': # 计算特征值和特征向量（升序排列） eigvals, eigvecs = np.linalg.eigh(self.L) # 选择前k个最小特征值对应的特征向量 vectors = eigvecs[:, :self.n_cluster] # 对特征向量矩阵进行标准化 row_norms = np.linalg.norm(vectors, axis=1, keepdims=True) row_norms[row_norms == 0] = 1 # 防止除以0 Vectors = vectors / row_norms ``` ### 3. 完善MSE计算函数 ```python def cal_err(data, cluster): mse = 0 # 获取所有簇标签 unique_labels = np.unique(cluster) for label in unique_labels: # 获取当前簇的所有点 cluster_points = data[cluster == label] # 计算簇中心点 center = np.mean(cluster_points, axis=0) # 累加簇内距离平方和 mse += np.sum(np.sum((cluster_points - center) ** 2, axis=1)) return mse ``` ### 完整代码实现 ```python import numpy as np from sklearn.datasets import make_blobs from K_Means import KMEANS class Spectrum: def __init__(self, n_cluster, epsilon=1e-3, maxstep=1000, method='unnormalized', criterion='gaussian', gamma=2.0, dis_epsilon=70, k=5): self.n_cluster = n_cluster self.epsilon = epsilon self.maxstep = maxstep self.method = method self.criterion = criterion self.gamma = gamma self.dis_epsilon = dis_epsilon self.k = k self.W = None self.L = None self.L_norm = None self.D = None self.cluster = None self.N = None def init_param(self, data): self.N = data.shape[0] dis_mat = self.cal_dis_mat(data) self.cal_weight_mat(dis_mat) self.D = np.diag(self.W.sum(axis=1)) self.L = self.D - self.W return def cal_dis_mat(self, data): dis_mat = np.zeros((self.N, self.N)) for i in range(self.N): for j in range(i + 1, self.N): dis_sq = np.sum((data[i] - data[j]) ** 2) dis_mat[i][j] = dis_sq dis_mat[j][i] = dis_sq return dis_mat def cal_weight_mat(self, dis_mat): if self.criterion == 'gaussian': if self.gamma is None: raise ValueError('gamma is not set') self.W = np.exp(-self.gamma * dis_mat) elif self.criterion == 'k_nearest': if self.k is None or self.gamma is None: raise ValueError('k or gamma is not set') self.W = np.zeros((self.N, self.N)) for i in range(self.N): inds = np.argpartition(dis_mat[i], self.k + 1)[:self.k + 1] tmp_w = np.exp(-self.gamma * dis_mat[i][inds]) self.W[i][inds] = tmp_w elif self.criterion == 'eps_nearest': if self.dis_epsilon is None: raise ValueError('epsilon is not set') self.W = np.zeros((self.N, self.N)) for i in range(self.N): inds = np.where(dis_mat[i] < self.dis_epsilon) self.W[i][inds] = 1.0 / len(inds) else: raise ValueError('the criterion is not supported') return def fit(self, data): self.init_param(data) if self.method == 'unnormalized': # 计算特征值和特征向量 eigvals, eigvecs = np.linalg.eigh(self.L) # 选择前k个最小特征值对应的特征向量 vectors = eigvecs[:, :self.n_cluster] # 标准化特征向量 row_norms = np.linalg.norm(vectors, axis=1, keepdims=True) row_norms[row_norms == 0] = 1 Vectors = vectors / row_norms else: raise ValueError('the method is not supported') km = KMEANS(self.n_cluster, self.epsilon, self.maxstep) km.fit(Vectors) self.cluster = km.cluster return if __name__ == '__main__': data, label = make_blobs(centers=3, n_features=10, cluster_std=1.2, n_samples=500, random_state=1) sp = Spectrum(n_cluster=3, method='unnormalized', criterion='gaussian', gamma=0.1) sp.fit(data) cluster = sp.cluster def cal_err(data, cluster): mse = 0 unique_labels = np.unique(cluster) for label in unique_labels: cluster_points = data[cluster == label] center = np.mean(cluster_points, axis=0) mse += np.sum(np.sum((cluster_points - center) ** 2, axis=1)) return mse if cal_err(data, cluster) < 1000 and cal_err(data, cluster) > 10: print("True") ``` ### 代码解释： 1. **距离矩阵计算**：计算所有样本点之间的欧氏距离平方，存储在对称矩阵中 2. **相似性矩阵**：使用高斯核函数计算点与点之间的相似性权重 3. **谱分解**： - 计算拉普拉斯矩阵的特征值和特征向量 - 选取前k个最小特征值对应的特征向量 - 对特征向量进行行归一化处理 4. **K-means聚类**：在特征向量空间上执行K-means聚类 5. **MSE计算**： - 计算每个簇的中心点 - 累加所有点到其簇中心的距离平方和 - 返回整体簇内平方和（SSE） 该实现完整覆盖了谱聚类的核心步骤：构造相似图→计算拉普拉斯矩阵→特征分解→降维聚类。最终输出True表示算法正确实现且聚类效果符合预期。