import numpy as np import torch import umap import matplotlib.pyplot as plt from run import * # 固定随机数种子，生成100个二维数据点 # torch.manual_seed(99) def para(data,num_nodes,num_class): similarity_threshold = 0.4 # 相似度阈值 num_anchors = num_class*2# 锚点数量 # num_anchors =26 distances = cosineSimilartydis(data, data) # 排除对角线上的自身距离（0）的平均值 mean_distance = distances[~torch.eye(distances.size(0), dtype=torch.bool)].mean() coverage_radius=mean_distance*0.3 # 贪心覆盖算法中的覆盖半径 #到时候写一个对齐数据少于锚点数量error的提示 if num_nodes < 100: # 小图 num_walks,walk_length = 20,3 elif num_nodes < 1000: # 中型图 num_walks,walk_length = 10,5 elif num_nodes < 10000: # 大型图 num_walks,walk_length = 5,10 else: # 超大图 num_walks,walk_length = 3,20 return num_walks,walk_length,similarity_threshold,num_anchors,coverage_radius def cosineSimilarty(A,B): A=A/(torch.norm(A,dim=1,p=2,keepdim=True)+0.000001) # A2 = A / (torch.norm(A, dim=0, p=2, keepdim=True) + 0.000001) B=B/(torch.norm(B,dim=1,p=2,keepdim=True)+0.000001) # B2 = B / (torch.norm(B, dim=0, p=2, keepdim=True) + 0.000001) W=torch.mm(A,B.t()) max_values,_ = torch.max(W, axis=0) min_values,_ = torch.min(W, axis=0) normalized_matrix = (W - min_values) / (max_values - min_values) normalized_matrix = torch.nan_to_num(normalized_matrix, nan=0.0001) return normalized_matrix def cosineSimilartydis(A,B): A=A/(torch.norm(A,dim=1,p=2,keepdim=True)+0.000001) B=B/(torch.norm(B,dim=1,p=2,keepdim=True)+0.000001) W=torch.mm(A,B.t()) max_values, _ = torch.max(W, axis=0) min_values, _ = torch.min(W, axis=0) normalized_matrix = (W - min_values) / (max_values - min_values) normalized_matrix = torch.nan_to_num(normalized_matrix, nan=0.0001) return 1-normalized_matrix # # 随机游走参数 # # # Step 1: 初始化完全图的转移概率矩阵 # distances = torch.cdist(data, data, p=2) # 计算所有点之间的欧几里得距离 # adj_matrix = torch.exp(-distances) # 高斯权重：距离越小权重越高 # def visit(data): # adj_matrix=cosineSimilarty(data,data) # print(np.shape(adj_matrix)) # adj_matrix.fill_diagonal_(0) # 去掉自身连接 # transition_matrix = adj_matrix / adj_matrix.sum(dim=1, keepdim=True) # 归一化为转移概率 # return transition_matrix def visit(data, alpha=0.5): """ 根据给定的节点特征矩阵data和参数alpha计算转移矩阵。 使用余弦相似度矩阵作为转移的相似度度量。 计算公式：r_mu(x_i) = (x_i / mu_i) ^ -alpha """ num_nodes = data.size(0) # 计算节点间的余弦相似度矩阵 adj_matrix = cosineSimilarty(data, data) # 归一化每一行，确保每行相似度和为1 adj_matrix.fill_diagonal_(0) # 去掉自身连接 adj_matrix = torch.nan_to_num(adj_matrix, nan=0.0001) # 防止NaN值 # 归一化为转移概率，确保每行的和为1 row_sums = adj_matrix.sum(dim=1, keepdim=True) + 0.000001 # 防止除以零 adj_matrix = adj_matrix / row_sums # 归一化为转移概率 # 防止出现概率为零的行（所有相似度为零时） adj_matrix = torch.nan_to_num(adj_matrix, nan=0.0001) # 替换NaN为小值 adj_matrix = torch.clamp(adj_matrix, min=0.0001) # 防止小于0的概率值 # 根据 alpha 修改相似度矩阵 transition_matrix = adj_matrix ** (-alpha) # 应用公式 r_mu(x_i) = (x_i / mu_i) ^ -alpha # 再次归一化转移矩阵，使得每行的和为1 transition_matrix = transition_matrix / (transition_matrix.sum(dim=1, keepdim=True) + 0.000001) # 检查是否有行的和仍然为0，若有则设置为均匀分布 zero_rows = (transition_matrix.sum(dim=1) == 0) if zero_rows.any(): transition_matrix[zero_rows] = 1.0 / num_nodes # 对于零行，设置均匀分布 return transition_matrix # 优化方法 def random_walk_batch_paths(transition_matrix, num_walks, walk_length): """ 批量化生成随机游走路径，并统计访问频次。 """ num_nodes = transition_matrix.size(0) visit_matrix = torch.zeros_like(transition_matrix,device='cuda') # 初始化访问频率矩阵 for start_node in range(num_nodes): # 遍历每个起始节点 # 初始化起点 paths = torch.full((num_walks, walk_length + 1), start_node, dtype=torch.long,device='cuda') # 每行一条路径 for step in range(walk_length): # 生成完整路径 probs = transition_matrix[paths[:, step]] # 当前步节点的转移概率 next_nodes = torch.multinomial(probs, 1).squeeze() # 采样下一个节点 paths[:, step + 1] = next_nodes # 累计所有路径的访问频率 for path in paths: visit_matrix[start_node].index_add_(0, path, torch.ones_like(path, dtype=torch.float,device='cuda')) visit_matrix -= torch.diag(torch.full((num_nodes,), num_walks, dtype=visit_matrix.dtype,device='cuda')) return visit_matrix # visit_matrix = random_walk_batch_paths(transition_matrix, num_walks, walk_length) # # # visit_matrix = random_walk_parallel(transition_matrix, num_walks, walk_length) # # Step 3: 归一化访问频率为相似度,构建基于阈值的 kNN 图 def thresholded_knn(visit_matrix,similarity_threshold): similarity_matrix = visit_matrix / visit_matrix.max() thresholded_adj = (similarity_matrix > similarity_threshold).float() # 保留相似度大于阈值的边 return thresholded_adj # # Step 5: 贪心覆盖算法选择锚点 def greedy_cover_with_importance(data, importance_scores, r, num_anchors): """ 贪心覆盖算法用于选择锚点 :param data: 数据点，形状为 (n_samples, n_features) :param importance_scores: 每个点的重要性分数 (随机游走访问频率) :param r: 覆盖半径 :param num_anchors: 需要选择的锚点数量 :return: 锚点索引 """ distances = cosineSimilartydis(data,data) # 计算点对点距离 selected = [] # 选择的锚点索引 covered = torch.zeros(data.size(0), dtype=torch.bool,device='cuda') # 覆盖标志位 sorted_indices = torch.argsort(importance_scores, descending=True) # 按重要性排序 cluster_selected = torch.zeros(data.size(0), dtype=torch.bool, device='cuda') # 集群是否被选中锚点标记 while len(selected) < num_anchors: # prev_covered_sum = covered.sum().item() # 上一次覆盖点的数量 for idx in sorted_indices: if len(selected) >= num_anchors: break if not covered[idx] and not cluster_selected[idx]: # 如果当前点未被覆盖，且所属集群未选过锚点 selected.append(idx) # 选择锚点 cluster_selected[idx] = 1 # 标记所属集群已选锚点 # 将当前锚点覆盖范围内的点标记为已覆盖 covered |= distances[idx] <= r covered[idx] = 1#调了半天，锚点自己没有被覆盖 selected_anchors = set(selected) # 当前已选择的锚点集合 selected_anchors_tensor = torch.tensor(list(selected_anchors), device='cuda') # 检查是否所有集群都已被选过锚点 if covered.sum().item() == data.size(0): print("所有点已被覆盖，重置覆盖状态") # 记录已选的锚点，重置覆盖标志 covered[:] = 0 covered[selected_anchors_tensor] = 1 # 恢复已选锚点的覆盖状态 print(len(selected)) # elif covered.sum().item() == prev_covered_sum: # print("没有新的点被覆盖，终止选择锚点") # break # 如果没有新点被覆盖，跳出循环 return torch.tensor(selected,device='cuda') # 计算节点的重要性（访问频率的总和） # node_importance = visit_matrix.sum(dim=1) # # # 使用贪心覆盖算法选择锚点 # anchor_indices = greedy_cover_with_importance(data, node_importance, coverage_radius, num_anchors) # anchors = data[anchor_indices] # 提取锚点 # # Step 6: 可视化结果 # # from sklearn.decomposition import PCA # # import matplotlib.pyplot as plt # # # # # 假设 data 和 anchors 是 5维张量 # # pca = PCA(n_components=2, random_state=42) # # # # # 降维到 2D # # data_2d = pca.fit_transform(data.detach().cpu().numpy()) # # anchors_2d = pca.transform(anchors.detach().cpu().numpy()) # # # # # 绘制统一显示的散点图 # # plt.figure(figsize=(8, 8)) # # plt.scatter(data_2d[:, 0], data_2d[:, 1], c='blue', label="Data Points", alpha=0.5, s=30) # # plt.scatter(anchors_2d[:, 0], anchors_2d[:, 1], color="red", label="Anchor Points", s=100, edgecolor='black') # # plt.title("Unified Visualization with PCA") # # plt.legend() # # plt.show() # # # # # 使用 UMAP 降维 # reducer = umap.UMAP(n_components=2) # data_2d = reducer.fit_transform(data.detach().cpu().numpy()) # anchors_2d = reducer.transform(anchors.detach().cpu().numpy()) # # # 绘制统一显示图 # plt.figure(figsize=(8, 8)) # plt.scatter(data_2d[:, 0], data_2d[:, 1], c='blue', label="Data Points", alpha=0.5, s=30) # plt.scatter(anchors_2d[:, 0], anchors_2d[:, 1], color="red", label="Anchor Points", s=20, edgecolor='black') # plt.title("Unified Visualization with UMAP") # plt.legend() # plt.show()