局部线性嵌入算法详细推导流程

时间: 2023-05-28 20:01:38 浏览: 81
局部线性嵌入算法(Locally Linear Embedding,LLE)是一种非线性降维算法,其基本思想是通过保留高维数据的局部线性特征来实现降维。下面通过详细的推导流程来理解LLE算法的实现过程。 1.定义问题 给定一个高维数据集$X=\{x_1,x_2,...,x_N\}$,其中每个样本$x_i$都是$d$维向量。该数据集需要被降维到一个低维空间中,使得样本间的关系在新的低维空间中得到保持。 2.选择邻域 定义邻域$L_i$为x_i的k个最近邻的集合。其中k是LLE算法的一个超参数,需要根据具体应用场景来调整。如下图所示: ![image.png](attachment:image.png) 3.构建权重矩阵 对于每个样本$x_i$,LLE算法的第一步是找出它在$k$个最近邻中的权重。权重矩阵$W$可以通过以下公式获得: $$W=\begin{bmatrix}\omega_{1,1} & \omega_{1,2} & \cdots & \omega_{1,N}\\\omega_{2,1} & \omega_{2,2} & \cdots & \omega_{2,N}\\\vdots & \vdots & \ddots & \vdots\\\omega_{N,1} & \omega_{N,2} & \cdots &\omega_{N,N} \end{bmatrix}$$ 其中,$\omega_{i,j}$是样本$x_i$和$x_j$之间的权重。它用于量化目标样本$i$与其邻域内样本$j$之间的线性关系。 权重需要满足以下三个条件: - 非负性:权重必须非负,因为它代表了两个样本之间的相似度。 - 归一性:权重必须归一化,也就是说每个样本的权重之和必须等于1。 - 局部线性保持:权重必须保持目标样本和邻域内样本之间的局部线性关系。 4.求解局部重构权重 定义重构误差为$\epsilon(w_{i,j})$表示样本i可以被邻域样本的线性组合以$\epsilon(w_{i,j})$的误差重构,即: $$\epsilon(w_{i,j})=\|\ x_i-\sum_{j\in L_i} w_{i,j} x_j\ \|^2$$ 为了最小化$\epsilon(w_{i,j})$,需要求解权重$w_{i,j}$,使得其满足三个条件: - 归一化条件: $\sum_{j\in L_i} w_{i,j}=1$ - 局部线性关系条件:$x_i=\sum_{j\in L_i} w_{i,j} x_j$ - 最小化重构误差:$\epsilon(w_{i,j})=\|\ x_i-\sum_{j\in L_i} w_{i,j} x_j\ \|^2$ 为了求解权重,定义矩阵$Z$表示$x_i$向每个邻域点的向量,即: $$Z = \begin{bmatrix}x_{i_1}-x_i & x_{i_2}-x_i & \cdots & x_{i_K}-x_i\end{bmatrix}$$ 其中,$x_{i_j}$表示第$j$个邻域点。 可得到如下公式,用来计算样本$x_i$与邻域内其他点的距离平方和: $$\epsilon(w_{i,j}) = (x_i-\sum_{j\in L_i} w_{i,j}x_j)^T(x_i-\sum_{j\in L_i} w_{i,j}x_j)$$ 通过求导,可以得到权重$w_{i,j}$的解析解为: $$w_i =\frac{(Z^TZ)^{-1}\vec{1}}{(\vec{1}^T(Z^TZ)^{-1}\vec{1})}$$ 其中,$\vec{1}$表示全1的向量。 5.构建中心化权重矩阵 定义矩阵$M$为$L_i$中所有权重向量的拼接,它是一个$k \times N$的矩阵,即: $$M = \begin{bmatrix}w_{1,1} & w_{1,2} & \cdots & w_{1,N}\\w_{2,1} & w_{2,2} & \cdots & w_{2,N}\\\vdots & \vdots & \ddots & \vdots\\w_{N,1} & w_{N,2} & \cdots & w_{N,N} \end{bmatrix}$$ 权重矩阵$W$可以通过矩阵$M$中心化得到,即: $$W = (I-M)^T(I-M)$$ 其中,$I$为单位矩阵。 6.求解新的低维表示 定义矩阵$Y$为新的低维表示,它是一个$N \times d'$的矩阵,其中$d'$表示降维后的维度。矩阵$Y$的每一行$y_i$表示对应样本$x_i$的低维表示,且满足L2范数为1。 通过求解下列优化问题,可以得到新的低维表示$Y$: $$\min_{Y} \sum_{i=1}^{N}\|\ y_i-\sum_{j=1}^{N} W_{i,j}y_j\ \|^2$$ 其中,$W_{i,j}$是已经求解得到的权重矩阵,表示样本$x_i$和$x_j$之间的权重。 可以将上面这个问题转换为求矩阵$Y$的特征值和特征向量。先计算矩阵$L=(I-W)^T(I-W)$的$d'+1$个最小特征值对应的特征向量,然后将特征向量按照对应的特征值的大小逆序排列,去除第一个特征向量(所有元素都相等的特征向量),然后将剩余的$d'$个特征向量构成矩阵$Y$。 值得注意的是,由于特征值问题通常比较容易受到数据噪声的干扰,因此LLE算法通常需要进行一些后处理,如移除无效的嵌入向量,或者通过局部判别分析(Locality Discriminant Embedding,LDE)进行过滤。 7.总结 LLE算法的核心思想是通过保留高维数据的局部线性特征来实现降维,具体步骤如下: - 选择邻域:对于每个样本,找到它的k个最近邻。 - 构建权重矩阵:根据邻域点之间的线性关系计算权重矩阵。 - 求解局部重构权重:通过最小化重构误差计算样本和其邻域内其他点之间的权重。 - 构建中心化权重矩阵:通过中心化权重矩阵来编码邻域点之间的关系。 - 求解新的低维表示:通过求解矩阵$Y$的特征向量,将高维数据降维到低维空间中。 LLE算法的优点是能够保留局部线性结构,缺点是计算复杂度较高,不太适合用于大规模数据集。

相关推荐

最新推荐

Python实现的线性回归算法示例【附csv文件下载】

主要介绍了Python实现的线性回归算法,涉及Python使用最小二乘法、梯度下降算法实现线性回归相关算法操作与使用技巧,需要的朋友可以参考下

《算法设计与分析》实验报告:实验二(线性选择问题)

在快速排序算法基础上,进一步完成线性时间选择算法,并且用不同数据量进行实验对比分析,要求分析算法的时间复杂性并且形成分析报告

水声声呐线性调频信号(LFM)脉冲压缩原理及matlab算法

水声探测中浅地层剖面仪工作原理,依靠线性调频信号脉冲压缩技术来进行所目标识别,文档包含了工作原理,公式推导,附图和matalb代码

基于Jupyter完成(自行推导公式)多元线性回归的编程

自行推导公式多元线性回归的编程一、导入文本店铺面积和营业额的关系图车站距离和营业额的关系图二、计算下图三、计算R² 一、导入文本 import pandas as pd import numpy as np import matplotlib.pyplot as plt ...

快速横向滤波器算法更新详细推导过程

后向线性预测滤波器bM(n)的推导;丁玉美的研究生 数字信号处理 时域离散随机信号处理,纠正了课本中的很多错误。

stc12c5a60s2 例程

stc12c5a60s2 单片机的所有功能的实例,包括SPI、AD、串口、UCOS-II操作系统的应用。

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire

【迁移学习在车牌识别中的应用优势与局限】: 讨论迁移学习在车牌识别中的应用优势和局限

![【迁移学习在车牌识别中的应用优势与局限】: 讨论迁移学习在车牌识别中的应用优势和局限](https://img-blog.csdnimg.cn/direct/916e743fde554bcaaaf13800d2f0ac25.png) # 1. 介绍迁移学习在车牌识别中的背景 在当今人工智能技术迅速发展的时代,迁移学习作为一种强大的技术手段,在车牌识别领域展现出了巨大的潜力和优势。通过迁移学习,我们能够将在一个领域中学习到的知识和模型迁移到另一个相关领域,从而减少对大量标注数据的需求,提高模型训练效率,加快模型收敛速度。这种方法不仅能够增强模型的泛化能力,提升识别的准确率,还能有效应对数据

margin-top: 50%;

margin-top: 50%; 是一种CSS样式代码,用于设置元素的上边距(即与上方元素或父级元素之间的距离)为其父元素高度的50%。 这意味着元素的上边距将等于其父元素高度的50%。例如,如果父元素的高度为100px,则该元素的上边距将为50px。 请注意,这个值只在父元素具有明确的高度(非auto)时才有效。如果父元素的高度是auto,则无法确定元素的上边距。 希望这个解释对你有帮助!如果你还有其他问题,请随时提问。

Android通过全局变量传递数据

在Activity之间数据传递中还有一种比较实用的方式 就是全局对象 实用J2EE的读者来说都知道Java Web的四个作用域 这四个作用域从小到大分别是Page Request Session和Application 其中Application域在应用程序的任何地方都可以使用和访问 除非是Web服务器停止 Android中的全局对象非常类似于Java Web中的Application域 除非是Android应用程序清除内存 否则全局对象将一直可以访问 1 定义一个类继承Application public class MyApp extends Application 2 在AndroidMainfest xml中加入全局变量 android:name " MyApp" 3 在传数据类中获取全局变量Application对象并设置数据 myApp MyApp getApplication ; myApp setName "jack" ; 修改之后的名称 4 在收数据类中接收Application对象 myApp MyApp getApplication ;">在Activity之间数据传递中还有一种比较实用的方式 就是全局对象 实用J2EE的读者来说都知道Java Web的四个作用域 这四个作用域从小到大分别是Page Request Session和Application 其中Application域在应用程序的任何地方都可以使用和 [更多]