目录
- 1、作者介绍
- 2、LPP算法简介
- 2.1 基本概念及原理
- 2.2 算法流程
- 3、LPP算法实现
- 3.1 数据集简介
- 3.2 代码实现
- 3.2.1 完整代码
- 3.2.2 运行结果
- 4、参考链接
1、作者介绍
刘晨雨,男,西安工程大学电子信息学院,2022级研究生
研究方向:医学图像分割
电子邮件:1422231109@qq.com
陈梦丹,女,西安工程大学电子信息学院,2022级硕士研究生,张宏伟人工智能课题组
研究方向:机器视觉与人工智能
电子邮件:1169738496@qq.com
2、LPP算法简介
2.1 基本概念及原理
LPP(Locality Preserving Projection),即局部保留投影算法,是一种常用的降维算法,通过线性近似LE算法(拉普拉斯特征映射)来保留局部信息,可以被看做是PCA的替代。
LPP算法通过构建空间中各样本对之间的远近亲疏关系,并在降维投影中尽可能地去保留这样的亲疏关系,从而保留数据的局部结构。
2.2 算法流程
LPP算法的核心思想是通过线性映射将高维数据投影到低维空间,使得样本的局部关系在低维空间中得以保持。
算法的具体步骤如下:
- 构建邻近图:首先,根据数据之间欧氏距离,计算每个样本与其最近邻样本之间的距离,并构建一个邻近图。
- 构建权重矩阵:根据邻近图,计算每个样本与其最近邻样本之间的权重。常用的权重计算方法是通过径向基函数计算权重,距离较近的样本具有较高的权重。
- 构建重构误差矩阵:对于每个样本,通过将其与其最近邻样本的线性组合重构出来,计算重构误差。重构误差表示通过低维空间的投影无法完美重构原始样本。
- 构建目标函数:LPP算法的目标是最小化重构误差,同时保持样本之间的局部关系。因此,构建目标函数,使得重构误差最小化。目标函数通常可以表示为矩阵形式,并通过对该矩阵进行特征值分解,得到最优的投影矩阵。
- 降维:根据得到的最优投影矩阵,将高维数据映射到低维空间中,完成降维过程。
3、LPP算法实现
3.1 数据集简介
手写数字数据集(digits)是常用的sklearn库中自带的数据集,直接调用即可;digits所包含的主要数据分为images 、data、target、target_names。其中:
- imgaes 是一个三维矩阵1797 张8 * 8的图片;
- data是具体数据包含1797个样本,每个样本包括8 × 8像素的图像,其实就是将8 × 8的images按行展开;
- target 指明每张图片的标签,也就是每张图片代表的数字;
- target_names数据集中所有标签[0,1,2,3,4,5,6,7,8,9] 。
3.2 代码实现
3.2.1 完整代码
# 导入包
import numpy as np
import matplotlib.pyplot as plt
from sklearn.decomposition import PCA
from sklearn.datasets import load_digits
# 求欧氏距离
# X维度[N,D]
def cal_pairwise_dist(X):
N,D = np.shape(X)
# 数据扩展
tile_xi = np.tile(np.expand_dims(X,1),[1,N,1])
tile_xj = np.tile(np.expand_dims(X,axis=0),[N,1,1])
# 欧式距离公式
dist = np.sum((tile_xi-tile_xj)**2,axis=-1)
# 返回任意两个点之间距离
return dist
# 求取rbf径向基函数
def rbf(dist, t = 1.0):
return np.exp(-(dist/t))
# 求取两两点的位置关系矩阵W
def cal_rbf_dist(data, n_neighbors = 10, t = 1):
# 根据输入的data数据调用欧式距离公式计算两两点之间的距离
dist = cal_pairwise_dist(data)
# 如果距离小于0则直接为0
dist[dist < 0] = 0
# 样本点的数目N为距离的第一个维度
N = dist.shape[0]
# 径向基
rbf_dist = rbf(dist, t)
# 初始矩阵N*N
W = np.zeros([N, N])
# 逐行遍历
for i in range(N):
# 按照欧氏距离从小到大进行排序,取n个最近的样本点
index_ = np.argsort(dist[i])[1:1 + n_neighbors]
# 径向基算出这些点的距离
W[i, index_] = rbf_dist[i, index_]
W[index_, i] = rbf_dist[index_, i]
return W
# X为输入维度 格式 [N,D];n_neighbors为K近邻的数目; t为距离计算的参数
def lpp(X,n_dims = 2,n_neighbors = 30, t = 1.0):
N = X.shape[0]
W = cal_rbf_dist(X, n_neighbors, t)
D = np.zeros_like(W)
# 计算对角线矩阵D
for i in range(N):
D[i,i] = np.sum(W[i])
L = D - W
XDXT = np.dot(np.dot(X.T, D), X)
XLXT = np.dot(np.dot(X.T, L), X)
# 求上述式子的特征值和特征向量
eig_val, eig_vec = np.linalg.eig(np.dot(np.linalg.pinv(XDXT), XLXT))
# 返回一个由小到大的排序后的序号
sort_index_ = np.argsort(np.abs(eig_val))
# 特征值根据序号重新排列
eig_val = eig_val[sort_index_]
# 输出前十个特征值
print("输出前十个特征值:", eig_val[:10])
# 判断特征值太小的舍去
j = 0
while eig_val[j] < 1e-6:
j+=1
# 最终选择一个j出来
print("\nj: ", j)
# 最终取n_dims个比较小的特征值的序号
sort_index_ = sort_index_[j:j+n_dims]
# 选取的特征值
eig_val_picked = eig_val[j:j+n_dims]
print("选取的特征值:", eig_val_picked)
# 得到转换矩阵A:特征值所对应的特征向量
A = eig_vec[:, sort_index_]
# 求取的那个公式
Y = np.dot(X, A)
return Y
if __name__ == '__main__':
# 测试 load_digits 数据
X = load_digits().data
Y = load_digits().target
n_neighbors = 5
dist = cal_pairwise_dist(X)
max_dist = np.max(dist)
data_2d_LPP = lpp(X, n_neighbors = n_neighbors, t = 0.01*max_dist)
data_2d_PCA = PCA(n_components=2).fit_transform(X)
# 画图
plt.figure(figsize=(12,6))
plt.subplot(121)
plt.title("LPP")
plt.scatter(data_2d_LPP[:, 0], data_2d_LPP[:, 1], c = Y)
plt.subplot(122)
plt.title("PCA")
plt.scatter(data_2d_PCA[:, 0], data_2d_PCA[:, 1], c = Y)
plt.show()
3.2.2 运行结果
4、参考链接
[1] 局部保留投影算法解析参考:https://zhuanlan.zhihu.com/p/340121889
[2] LPP算法实现代码参考:https://github.com/heucoder/dimensionality_reduction_alo_codes/blob/master/codes/LPP/LPP.py