Hello！ 非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～  ଘ(੭ˊᵕˋ)੭ 昵称：海轰 标签：程序猿｜C++选手｜学生 简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研 学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！   唯有努力💪  【每日一读】每天浅读一篇论文，了解专业前沿知识，培养阅读习惯（阅读记录 仅供参考）

会议：SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of Data （CCF A类）

年度：2017年5月9日

局部线性嵌入 (LLE) 是一种流行的降维方法，因为它可以有效地表示高维数据的非线性结构

对于降维，它从给定的数据集中计算最近邻图，其中通过应用拉格朗日乘数法获得边权重，然后计算 LLE 内核的特征向量，其中边权重用于获得内核

虽然 LLE 在许多应用中都有使用，但它的计算成本非常高

这是因为，在获得边权重时，其计算成本是每个数据点的边数的三次方 此外，获得 LLE 内核的特征向量的计算成本在数据点的数量上是三次方的

我们的方法 Ripple 基于两个想法：

实验表明，通过保证相同的降维结果，Ripple 明显快于 LLE 的原始方法

我们已经进入了大数据时代[28,29,35]。由于数据库技术的飞速发展，海量数据已经在很多应用中变得普遍，与数据相关的技术也变得比以往任何时候都更加重要。由于现实世界的数据通常表现出高维[11,12,14]，因此通过以紧凑的方式表示内在结构以分析大数据，发现隐藏在高维中的内在属性非常重要。此外，必须自动提取表示，因为我们通常对存储在数据库中的数据没有先验知识。

降维是数据挖掘中处理高维数据的一项基本技术。它的目标是通过消除不重要或嘈杂的因素来获得给定数据集的紧凑表示，这对于高级分析（如分类和异常值检测）至关重要。通过抑制被称为维度灾难的问题[25]，成功的数据挖掘需要降维。如果数据集具有高维，这个问题会降低数据挖掘的效率。在降维中，重要的是保留原始高维空间的结构和关系。主成分分析（PCA）是一种著名的线性降维方法[25]。如果数据占据线性空间，它可以发现低维结构。然而，在许多现实世界的数据中，隐藏在高维数据中的低维结构是非线性的；线性降维在映射此类高维数据时无效。因此，PCA 在大数据的数据挖掘中可能会产生不令人满意的性能。

提出了局部线性嵌入（LLE）来克服线性降维的问题；它可以以无监督的方式执行非线性降维[32]。 LLE 的基本思想是通过其邻居以回归的形式逼近每个数据点，并找到每个数据点的低维嵌入。 LLE 解决了两个优化问题，以最小化重建成本和嵌入成本。通过寻找重建和嵌入成本的全局最小值，它可以有效地保留低维空间中高维数据的局部结构。此外，优化不需要随机初始化或学习率。因此，LLE 在降维方面是有效的，在各个领域的许多应用中都有使用。

不幸的是，LLE 有一个缺点。它的计算成本非常高。如果 K 是每个数据点的边数，则 LLE 的原始算法为每个大小为 K × K 的数据点计算一个 Gram 矩阵，并从 Gram 矩阵的逆矩阵计算边权重，其中 Lagrange 乘子法用于约束边缘权重的总和[32]。由于计算逆矩阵的成本是每个数据点的边数的三次方，因此计算边权重需要 O(N K3 ) 时间，其中 N 是数据点的数量。此外，为了获得每个数据点的低维嵌入，原始算法计算从边缘权重获得的 LLE 内核的特征向量。由于 LLE 内核的大小为 N × N ，因此计算特征向量需要 O(N 3) 时间；特征向量的计算成本是数据点数量的三次方。此外，这种计算特征向量的过程意味着原始算法需要很高的内存消耗；计算特征向量需要 O(N 2) 空间。因此，将 LLE 的原始算法用于大规模数据集是不切实际的，尽管它可以有效地逼近非线性结构。

如果 M 是维数，则高维数据集表示为 N × M 的矩阵 X。此外，ifm 是低维数据的维数，其中 m # M ，matrixX 的低维嵌入表示为 N × m 大小的矩阵 Y。在本文中，我们解决了以下问题，通过使用 LLE 有效地将数据集的维度从 M 减少到 m：

由于问题的普遍性和实用性，我们的方法可用于如下所示的各种应用中。阿尔茨海默氏症分类。阿尔茨海默病是一种进行性脑部疾病，会慢慢破坏记忆力和思维能力。随着世界人口老龄化，将需要大量资源来照顾阿尔茨海默病患者。有效的干预措施可以降低阿尔茨海默病的患病率，提高患者的生活质量，并减少提供医疗保健所需的资源。虽然 MRI 现在用于检测阿尔茨海默病，但由于 MRI 特征的高维性，它通常无法发现脑组织损失的微妙模式。因此，传统方法（例如基于线性回归的预测）无法可靠地检测阿尔茨海默病 [4]。卡萨诺瓦等人。提出了一种通过使用 LLE [27] 将 MRI 特征转换为低维空间来检测阿尔茨海默病的方法。他们表明，他们的方法比传统方法提供了更好的分类准确性。此外，他们通过 LLE 将患者映射到一个二维空间中，根据疾病进展分为 4 类； (1) 正常，(2) 稳定损伤，(3) 阿尔茨海默病损伤，和 (4) 阿尔茨海默病。他们的方法的映射表明，正常和阿尔茨海默病这两个不同的患者群。此外，分配稳定损伤的患者看起来更接近正常患者，而分配给阿尔茨海默病的患者更接近阿尔茨海默病患者。这一结果表明，LLE 可用于识别受损患者，这些患者后来将死于阿尔茨海默病，以及那些将保持稳定的患者。

节点本地化。在传感器网络领域，节点定位是估计每个传感器的物理位置的任务，而无需使用额外的硬件来获取位置信息，例如 GPS。近年来，全集成、低功耗和低成本通信设备的发展导致了用于监测、控制和跟踪应用的无线传感器网络的发展。由于传感器节点通常在没有先验位置知识的情况下部署，因此节点定位是估计其位置的重要技术。节点定位的经典方法是基于多维缩放（MDS）[33]。从理论上讲，它是基于传感器之间的距离信息可以建模为用高斯噪声模糊的真实距离的假设。然而，由于实际的传感器网络通常以非高斯范围误差为特征，因此这种方法在估计每个传感器的位置时没有用处。耆那教等人。提出了一种基于 LLE 的方法，提高了节点定位的有效性 [20]。与 MDS 相比，该方法不假设距离与范围线性相关。相反，它假设包含传感器及其相邻传感器的小局部区域具有线性。基于这个假设，它学习了传感器网络的全局结构。他们表明，基于 LLE 的方法将位置估计的错误率从基于 MDS 的方法的 22.5% 降低到 12.6%。

银河分析。哈勃说：“星云（星系）如此之多，无法单独研究。因此，有必要知道是否可以从最显眼的物体中组装出公平的样本，如果可以，所需样本的大小” [18]。虽然这一论点在河外天文学开始时就出现了，但它表明有必要分析星系。由于现代天文技术的发展，我们正在收集大量的光谱数据。虽然这些数据促成了许多新的科学，但我们面临的问题是如何从大规模数据中以物理上有意义的方式分析星系。处理天文数据的难点来自于数据的高维性。PCA 是一种流行的线性降维方法[40]。然而，PCA 的线性在星系分析中有一个潜在的弱点。很难简洁地表达数据中固有的非线性关系，例如灰尘遮蔽或谱线宽度的变化。 Vanderplas 等人的基于 LLE 的方法。可以通过降维成功地对星系进行分类[41]。通过分析光谱数据，该方法揭示了低维空间中存在几种不同类型的星系：准星体、发射线星系和连续星系。低维空间中的星团位置反映了星系的特性；分析结果与目前的天文学知识是一致的。此外，结果表明基于 LLE 的方法可以揭示天文学文献中未描述的新发现。

在本文中，我们提出了 Ripple，一种可以有效应用 LLE 来降低维度的新方法。为了提高效率，我们在计算边权重时通过参考最近邻的逆矩阵来增量更新 Gram 矩阵的逆矩阵。此外，我们使用基于 LU 分解的逆幂方法来有效地计算 LLE 内核的特征向量以获得低维嵌入。所提出的方法具有以下吸引人的特点：

尽管 PCA 是最流行的降维方法，但它在将数据点投影到低维空间时可能无效，因为高维数据在许多实际应用中是非线性的。 LLE 被提出来克服线性方法的这一缺点，但存在计算成本高的问题。与以前的工作不同，所提出的方法的贡献是在不牺牲降维准确性的情况下显着提高 LLE 的效率。所提出的方法将提高许多应用的实用性，例如阿尔茨海默病分类、节点定位和星系分析。因此，我们的方法将有助于有效地执行基于大数据的复杂分析，从而显着改善决策、最大限度地降低风险并挖掘各个领域的宝贵见解。在阿尔茨海默病分类的情况下，它甚至可以实现阿尔茨海默病发病和进展的微小延迟；我们可以显着减轻这种疾病的全球负担，以提供足够的机构和家庭医疗保健。

根据映射原始高维数据点的特征，降维可以分为线性或非线性。

线性降维假设两个数据点的不相似性由它们之间的欧几里德距离定义，而相似性由它们的内积给出。最著名的线性降维技术 PCA [25] 使用特征向量来表示高维数据。 MDS 是另一种流行的线性方法 [17]。它使用数据点的相似性来找到接近给定相似性的配置。最近的线性降维方法见调查论文[9]；本文从有效性和效率方面评估每种方法。在数据库界，很多研究人员提出了线性降维方案，基于欧式距离对高维数据进行相似度搜索；示例包括 DFT、SVD、DCT、DWT、PAA、APCA、SAX 和 IPLA [3、5、6、7、10、21、23、26]。这些方法具有下界的特性。下界属性的主要好处是允许我们找到完全相同的高维数据[34]。已经提出了非线性降维方法来克服线性方法的一个关键弱点；它们通常无法保留高维空间中存在的数据结构。虽然 LLE 是最流行的方法，但 Isomap 是另一种著名的非线性降维方案 [39]。它计算数据上的图形度量，该数据近似于底层结构的测地线度量，并应用 MDS 来找到保留图形度量的低维表示。最大方差展开 (MVU) 通过保留每个数据点的所有邻居对之间的局部距离和角度从相似性中学习数据，这与仅保留测地距离的 Isomap 不同 [44]。公园等人。提出了局部线性潜变量模型[30]。与其他不定义数据分布的方法不同，该模型可以通过体现局部几何在流形坐标和高维观察之间线性映射的中心概念来执行非线性流形发现。为了提高非线性降维方法的效率，例如 Isomap 和 Laplacian Eigenmaps，Talwalkar 等人。提出使用 Nystr ̈om 方法和列采样方法来近似计算稀疏亲和矩阵的特征分解 [37, 38]。他们表明，通过利用真实图像数据集，Nystr ̈om 方法比列采样方法更有效。为了提高特征分解的逼近质量，Vladymyrov 等人。提出了局部线性地标（LLL）[42]。这种方法使用数据点的子集、地标来近似计算特征分解。具体来说，它计算一个小的地标矩阵，其中所有数据点通过使用它们最近的地标的局部线性函数来投影，其中局部线性函数是从数据矩阵 X 获得的。这种方法比 Nystr ̈om 方法产生更好的近似值，计算量更少时间。在随后的论文中，Vladymyrov 等人。提出了变分 Nystr ̈om (VN)；它以与局部线性地标相同的方式使用地标来近似稀疏亲和力矩阵的特征分解[43]。这种方法只需要一个小矩阵即可通过使用与地标相对应的稀疏亲和矩阵的列来计算特征分解。与局部线性地标不同，它在计算所有数据点的投影时不需要数据矩阵 X。

为了提高 LLE 的效率，Hui 等人。提出了基于聚类的局部线性嵌入（CLLE）[19]。它通过k-means聚类将给定的数据分成簇。然后它从集群中计算 LLE 内核的最近邻和特征向量。由于它不计算连接集群之间数据点的边及其权重，因此它可以有效地获得最近的邻居。此外，由于 LLE 内核具有块结构，它可以有效地从小块矩阵中计算特征向量。随着集群数量的增加，他们的方法提高了 LLE 的效率。但是，它有一个缺点；其降维的结果与原来的方法不同。这是因为，在他们的方法中，只有集群内边缘具有非零权重，尽管在原始方法中跨集群边缘可能具有非零权重。这表明 CLLE 牺牲了 LLE 的降维质量来提高效率。事实上，与线性投影方法相比，LLE 被提出来提高降维的有效性。 Kouropteva 等人。为 LLE [24] 提出了一种增量方法。这种方法的一个关键假设是新数据以在线方式到达。基于这个假设，这种方法增量计算特征向量。但是，在本文中，我们假设按照 LLE 的原始论文以批处理方式进行降维。据我们所知，本文提出的方法是第一个在保证降维准确性的情况下提高 LLE 效率的方法。

略…

在本文中，我们解决了有效计算 LLE 降维的问题

为了提高效率，所提出的方法通过利用 Woodbury 公式增量更新边缘权重，并通过利用基于 LU 分解的逆幂方法有效地计算特征向量

实验表明，所提出的方法可以实现比现有方法更高的效率

在执行 LLE 降维时，所提出的方法对于研究界来说是一个有吸引力的选择

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正