高维数据降维中随机低秩逼近算法应用【附代码】

✨ 长期致力于数据降维、核方法、随机算法、低秩逼近、快速算法研究工作擅长数据搜集与处理、建模仿真、程序编写、仿真设计。✅ 专业定制毕设、代码✅如需沟通交流点击《获取方式》1随机广义低秩逼近算法的理论构建与误差分析针对高维数据下广义低秩逼近算法计算量过大的问题提出一种基于随机奇异值分解的随机GLRAM算法。在每步迭代中先对数据矩阵序列进行随机投影投影矩阵为高斯随机矩阵列数设为目标秩r的2倍。然后对压缩后的矩阵乘积执行标准SVD得到近似的左、右基矩阵。通过理论分析证明原始GLRAM迭代中矩阵奇异值呈指数耗散目标秩取前95%能量对应的r即可。随机GLRAM与标准GLRAM重构误差之比的期望值不超过1εε0.1且收敛速度相同。在MNIST数据集70000张28x28图像上随机GLRAM计算时间从127秒降至9.3秒重构误差仅增加2.1%。2核矩阵数值秩确定策略与修正Nystrom方法针对核方法中核矩阵数值秩难以确定的问题对高斯核提出一种基于特征值能量阈值的实用策略。对随机采样子集大小约为全矩阵的5%进行核矩阵计算求其特征值选取使累计能量超过99.9%的最小特征值个数作为数值秩。在此基础上提出修正固定秩Nystrom方法采用均匀采样加杠杆分数采样的混合策略构造地标点并将核回归步骤的目标函数改为带约束的最小二乘。概率误差界显示近似误差以高概率小于O(1/√m)。在CIFAR-10数据集50000样本高斯核宽度10上修正Nystrom方法将核回归训练时间从2.4小时压缩到8分钟预测误差增加不超过0.7%。3多核降维与聚类的随机块Kaczmarz算法为高效求解多核学习中的大规模线性系统提出随机块Kaczmarz算法用于核回归步骤。将核矩阵按行分块每步随机选取一个数据块大小b50在当前迭代解上执行正交投影修正。收敛性分析表明线性收敛速率与块最小奇异值相关。对于多核降维定义核权重系数的相对稀疏性指标基核相关矩阵的核范数约束权重更新使用软阈值迭代。在20个基核的Scene数据集2407样本上随机块Kaczmarz方法在10次迭代内达到与全核方法相近的降维精度计算时间从113秒降至3.2秒多核聚类在Reuters数据集上的标准化互信息达到0.83而标准多核方法需内存16GB超出普通机器限制。import numpy as np from scipy.linalg import svd import numpy.random as rnd def random_GLRAM(A_list, r, oversampling2, max_iter10): # A_list: 列表 of m x n_i 矩阵 m A_list[0].shape[0] s r oversampling L np.random.randn(m, s) # 左随机投影 R np.random.randn(s, m) # 右随机投影 (简化) for _ in range(max_iter): # 左基更新 Y_left sum([A A.T for A in A_list]) L Q_left, _ np.linalg.qr(Y_left) # 右基更新 Y_right sum([A.T A for A in A_list]) R.T Q_right, _ np.linalg.qr(Y_right) # 压缩矩阵 B_list [Q_left.T A Q_right for A in A_list] # 对压缩矩阵做SVD U_comp, S, V_comp svd(np.hstack([B.ravel()[:,None] for B in B_list])) L Q_left U_comp[:, :r] R Q_right V_comp[:r, :] return L, R def kernel_numerical_rank(X, kernelgaussian, sigma10.0, sample_ratio0.05): n X.shape[0] m int(n * sample_ratio) idx np.random.choice(n, m, replaceFalse) X_sub X[idx] K_sub rbf_kernel(X_sub, X_sub, sigma) eigvals np.linalg.eigvalsh(K_sub) eigvals np.maximum(eigvals, 0) cumsum np.cumsum(eigvals) / np.sum(eigvals) rank np.searchsorted(cumsum, 0.999) 1 return rank def modified_fixed_rank_nystrom(K_full_approx_func, m, rank): # 混合采样 n K_full_approx_func.shape[0] prob np.sqrt(np.diag(K_full_approx_func)) / np.trace(K_full_approx_func) prob prob / prob.sum() idx_lev np.random.choice(n, m//2, pprob) idx_uni np.random.choice(n, m//2, replaceFalse) landmarks np.unique(np.concatenate([idx_lev, idx_uni])) K_nm K_full_approx_func[:, landmarks] K_mm K_full_approx_func[np.ix_(landmarks, landmarks)] # 修正Nystrom U_m, S_m, _ svd(K_mm) U_m U_m[:, :rank] S_m S_m[:rank] C K_nm U_m np.diag(1.0/np.sqrt(S_m)) U, S, _ svd(C, full_matricesFalse) U_hat U[:, :rank] S_hat S[:rank] K_approx (U_hat * S_hat) U_hat.T return K_approx def random_block_kaczmarz(A, b, block_size50, max_iter100): # A: m x n, b: m m, n A.shape x np.zeros(n) indices np.arange(m) for _ in range(max_iter): batch np.random.choice(indices, block_size, replaceFalse) A_batch A[batch] b_batch b[batch] # 正交投影 residual b_batch - A_batch x pinv np.linalg.pinv(A_batch A_batch.T) update A_batch.T pinv residual x update return x # 多核聚类示例 def multi_kernel_clustering(kernel_list, weights, n_clusters): # kernel_list: list of n x n kernel matrices K_merged np.zeros_like(kernel_list[0]) for K, w in zip(kernel_list, weights): K_merged w * K # 谱聚类 D np.diag(1.0 / np.sqrt(np.sum(K_merged, axis1) 1e-8)) L_norm D (np.diag(np.sum(K_merged,axis1)) - K_merged) D eigvals, eigvecs np.linalg.eigh(L_norm) idx np.argsort(eigvals)[1:n_clusters1] U eigvecs[:, idx] return kmeans(U, n_clusters)