缓解多维缩放方法中的随机一致性

Mitigating Random Consistency in Multidimensional Scaling Methods

摘要

在机器学习领域中，样本随机性及随机一致性现象广泛存在于分类、聚类等任务中。当样本有限时，由于样本随机性的存在，样本协方差矩阵的特征值分解可能会具有随机一致性，使用样本特征值与特征向量来估计总体特征值与特征向量时会存在误差。类似地，多维缩放（Multidimensional Scaling，MDS）方法中涉及内积矩阵\mathit{B}的特征值分解，结果也可能具有随机一致性，最后得到的样本低维坐标可能会存在误差，导致模型性能下降。为了提高模型的估计准确度和算法的稳定性，聚焦于研究MDS内积矩阵\mathit{B}的特征值分解中的随机一致性问题，并引入平均思想，使用平均特征向量表示总体特征向量。为了更好地拟合数据真实分布，首先对数据进行多次均匀抽样，其次分析在协方差分解过程中缓解随机一致性的意义及必要性，最后提出缓解随机一致性的多维缩放方法（Expectation-based Multiple Dimensional Scaling， EMDS）。在6个公开UCI数据集上进行分类实验验证，实验结果表明，相比于原始MDS方法，EMDS降维后的数据具有更高的分类准确率。

Abstract

In the field of machine learning, the phenomena of sample randomness and random consistency are widely encountered in tasks such as classification and clustering. When the samples are limited, due to the existence of sample randomness, the eigenvalue decomposition of the sample covariance matrix may have random consistency, and there will be an error when using the sample eigenvalues and eigenvectors to estimate the overall eigenvalues and eigenvectors. Similarly, the multiple dimensional scaling (MDS) method involves the eigenvalue decomposition of the inner product matrix \mathit{B}. The results may also have random consistency, and the final low-dimensional sample coordinates obtained may have errors, resulting in a degradation of the model performance. In order to improve the estimation accuracy of the model and the stability of the algorithm, this paper focuses on investigating the random consistency problem in the eigenvalue decomposition of the inner product matrix \mathit{B} of the MDS method, and introducing the averaging idea, using the average eigenvectors to represent the overall eigenvectors. In order to better fit the true distribution of the data, first, the data are sampled multiple times; second, the significance and necessity of mitigating the random consistency during the covariance decomposition are analyzed; and finally, the Expectation-based Multiple Dimensional Scaling (EMDS) is proposed to mitigate the random consistency. The classification experiments are validated on six public UCI datasets, and the experimental results show that the EMDS dimensionality reduction has a higher accuracy rate compared to the original MDS method.

Graphical abstract

关键词

随机一致性 / 多维缩放 / 分类

Key words

random consistency / multidimensional scaling / classification

0 引言

机器学习领域中，样本随机性及随机一致性现象广泛存在，学习算法本质上是从历史数据中进行经验归纳。历史的经验数据本身蕴含着随机性，它可看作为数据分布总体在某种意义下采样得到的样本集，学习算法作为样本到决策的函数映射，自然地延续了这种随机性。Wang等^［1］提出的随机一致性理论中，描述了数据特性和算法设计等因素导致了随机一致性存在的广泛性和必然性。随机一致性影响了学习模型的泛化能力，损害了模型的公平公正性及可解释性，不仅误导了目标优化方向，而且在测试数据集上可能欠缺延展性和泛化能力，给机器学习理论带来挑战。随机一致性也影响了学习模型的客观评价，传统一致性评判准则下，一些随机一致的情形也被赋予了一定分数。

有关特征值和特征向量的分析中，研究特征向量的分布也很重要，Shen等^［2］揭示了在样本大小和/或变量数（或维数）趋于无穷大时，在具有可区分（或不可区分）特征值的Spike模型下，在临界样本特征方向上的渐近圆锥形结构。该结论为本文引出新的思考，当样本有限时，样本特征向量以一定的角度分布在总体特征向量周围，可能存在样本特征向量与总体特征向量随机一致的情况，即样本协方差矩阵的特征值分解结果^［3］可能存在随机一致性，在利用样本特征值与特征向量估计总体特征值与特征向量时会产生误差，影响模型性能。

目前缓解维数灾难的途径之一是降维，多维缩放（Multidimensional Scaling MDS）^［4］是常见的降维方式，同时较好保持数据点之间的距离关系。MDS算法使用内积矩阵的特征值与特征向量的变换表示低维数据，每一行是一个样本的低维坐标。

Z={\tilde{\mathit{\Lambda }}}^{\mathrm{1}/\mathrm{2}}{\tilde{\mathit{V}}}^{\mathrm{T}}\in R^{d^{\mathrm{\text{'}}}\times m}。（1）

由于现实中仅需降维后的距离与原始空间中的距离尽可能接近，不必严格相等，可取d^{\mathrm{\text{'}}}\ll d，\tilde{\mathit{\Lambda }}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}({\lambda }_{\mathrm{1}},{\lambda }_{\mathrm{2}},\dots ,{\lambda }_{d^{\mathrm{\text{'}}}})为非零特征值构成的对角矩阵，\tilde{\mathit{V}}为相应的特征向量矩阵。

根据MDS公式（1），发现存在内积矩阵的特征值分解，可能会存在样本特征向量与总体特征向量随机一致的情况。根据以上描述，MDS过程存在随机一致性，从而导致特征值、特征向量估计存在较大误差，导致估计低维坐标不准确或模型计算误差的累积。为了提高机器学习算法的稳定性，本文从随机一致性角度考虑内积矩阵的特征值和特征向量的估计问题，聚焦于缓解多维缩放方法中的随机一致性。

为了提高算法鲁棒性和可解释性，以及对总体特征向量的估计，本文提出缓解多维缩放方法中的随机一致性方法（Expectation-based Multiple Dimensional Scaling，EMDS），使用平均特征向量表示内积矩阵的特征向量，并将EMDS和MDS降维后的数据进行分类，比较实验结果验证方法有效性。

本文主要有以下贡献：

1.当样本有限时，由于样本随机性存在，样本协方差矩阵的特征值分解结果具有随机一致性；

2.从随机一致性角度考虑样本协方差矩阵的特征值、特征向量的估计问题，提出缓解随机一致性的多维缩放方法EMDS；

3.在多个传统数据集上进行实验，将降维后的数据分别进行K最邻近算法（K-NearestNeighbor，KNN）分类，准确率显著提高，验证了该方法的有效性。

本文的组织结构如下：第1节主要介绍相关工作和知识；第2节阐述缓解多维缩放方法中的随机一致性方法；第3节对数据进行实验验证与结果分析。最后总结全文并展望未来。

1 相关工作

从随机一致性角度出发，王婕婷等^［5］提出消除随机一致性的支持向量机分类方法（Pure Accuracy Support Vector Machine，PASVM），主要思想是：以准确度为准则的学习体系无法识别随机一致性，影响学习系统的泛化性能，并给出了随机准确度和纯准确度定义。

针对平均概念的研究，de Carvalho^［6］回顾了柯尔莫戈罗夫关于均值的公理观点，它统一了所有这些均值的概念。对于正则平均数，以及正则方差和标准差的概念，作为统一的概念进行讨论，举例说明其主要思想。Johnstone^［7］研究稀疏正态均值向量的极小估计问题，推测在高斯分布中，偶尔会受到加性噪声的污染，则具有最少Fisher信息的分布具有（双侧）几何污染。文章提供了极大极小风险的部分渐近扩展。虽然这个猜想似乎不太可能完全适用于有限\epsilon，但以渐近的方式验证了它，直到达到展开式的准确性。

根据以上概述，本文从随机一致性角度出发，将平均思想融入特征值分解，进一步提高算法的稳定性和鲁棒性。

为了更好地拟合数据分布，本文对数据进行多次均匀抽样。Blaser等^［8］指出在球坐标中选择两个随机角度的简单方法生成相同起始向量的7 000个随机旋转，可以观察到两个极点附近的不良旋转点浓度是清晰可见的，如图1所示。

用均匀分布随机数采样任意分布样本，一个特别重要的随机变量是典型的均匀随机变量，可以使用伪随机数生成器^［9］。现在常用的均匀分布随机数发生器有线性同余法^［10］、反馈位寄存器法^［11］以及随机数发生器的组合^［12］，而且在高维空间中，拒绝采样^［13］和重要性采样^［14］很难寻找到合适参考分布，而且采样的效率较低，这时可以选择马尔可夫蒙特卡洛（Markov Chain Monte Carlo，MCMC）采样法^［15-18］。

另一个近似解法如下公式（2），给出了每个点的坐标，表示3维下的球体表面上均匀分布点，展示了一种称为斐波那契晶格（也称为斐波那契螺旋）^［19-21］的方法，在3D坐标中，用公式生成7 000个点的效果如图2所示，符合对均匀分布的预期，通常大多数的数据集是高维的，因此还需要将该采样方法扩展到d维。

\begin{array}{c}{P}_i=\theta i,\\ T_i=\sqrt[]{\mathrm{1}-Z_i^{\mathrm{2}}},\\ Z_i=(\mathrm{1}-\frac{\mathrm{1}}{N})(\mathrm{1}-\frac{\mathrm{2}i}{N-\mathrm{1}}),\end{array}（2）

其中N为数据点的数量，P_i表示角度，T_i是从中心开始的半径，Z_i是为N个样本给出一个介于-1和+1之间的均匀分布的数。

假设100个原始数据，按索引离散均匀抽样50个数据如图3（a）所示，其中灰色点为未抽到的原始数据点，蓝色点为已抽到的原始数据点。按斐波那契螺旋生成100个均匀分布点，之后均匀抽样50个数据如图3（b）所示，其中灰色点为未抽到的原始数据点，淡蓝色点为均匀生成点，蓝色点为已抽到的原始数据点。如图3所示，斐波那契螺旋均匀采样方法抽样的数据点近似均匀，更有助于后续计算平均向量。

2 缓解MDS方法中的随机一致性

机器学习简单介绍了MDS方法的原理，主要涉及内积矩阵\mathit{B}的特征值和特征向量，将其变换作为低维坐标。对于有限样本，样本协方差矩阵及特征值分解结果具有样本随机性^［5］。不同的抽样得到的样本协方差矩阵的特征值、特征向量有较大差距，并且以一定的角度分布在总体特征向量周围。若能消除或者缓解协方差矩阵分解时随机一致性，算法的稳定性将会被提高。如果用多个样本特征向量的平均估计总体特征向量，会更准确地逼近总体特征向量，从而使得到的低维坐标更准确。

为了使得内积矩阵\mathit{B}的平均样本特征向量更准确，本文对数据进行k次均匀采样，得到k次采样的数据，根据k个距离矩阵计算k个内积矩阵和特征值与特征向量，并计算平均特征值和平均特征向量。然后使用平均特征值与特征向量估计内积矩阵的总体特征值与特征向量，将平均特征值排序后，选择前m个特征值，对应的平均特征值与特征向量进行变换作为低维坐标，实现数据降维，最后对降维后数据进行分类验证。本文方法的框架图如图4所示，主要分为两部分，第一部分为均匀抽样数据，第二部分是EMDS部分。

多维缩放方法是利用数据在原始空间的距离矩阵，目标是获得样本在d^{\mathrm{\text{'}}}维空间的表示Z\in R^{d^{\mathrm{\text{'}}}\times m}。正确的特征值与特征向量有助于找到相对正确的低维坐标。本文的EMDS方法，主要特点是修改内积矩阵\mathit{B}的特征值、特征向量的表示形式，为了更好地估计它们，将由多个内积矩阵的样本特征值、样本特征向量所计算出的平均特征值、平均特征向量来代替内积矩阵的总体特征值、总体特征向量。这将有利于提高MDS性能和分类模型的准确度。基于以上描述，本文提出的EMDS算法的描述如算法1所示，计算内积矩阵算法如算法2所示。EMDS算法中特征分解及计算平均特征向量时需要循环i和j，复杂度为O(d\times k)，因此提高算法效率也是本文未来改进的方向。

算法1 EMDS算法

输入：数据，X(x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_d)\in R^{n\times d}；均匀分布点的个数n；选择特征值个数m；

输出：降维数据X^{\mathrm{\text{'}}}(x_{\mathrm{1}}^{\mathrm{\text{'}}},x_{\mathrm{2}}^{\mathrm{\text{'}}},\dots ,x_m^{\mathrm{\text{'}}})\in R^{n\times m}

（1）： 计算余弦距离矩阵\mathit{L}\in R^{n\times n}

（2）： 将余弦距离矩阵\mathit{L}按列从大到小排序，得到相应的索引矩阵\mathit{F}\in R^{n\times n}

（3）： for i\to \mathrm{1} to k do k次遍历索引矩阵\mathit{F}

按行取k次索引矩阵，每次获得均匀采样数据的索引，根据索引映射得到k个数据集合T_i\in R^{n\times d}

（4）： end for

（5）： for i\to \mathrm{1} to k do 计算内积矩阵\mathit{B}

B_i\in R^{n\times n}

（6）： end for

（7）： for i\to \mathrm{1} to d，j\to \mathrm{1} to k do 特征值分解

B_j\to {\lambda }_{ij},e_{ij}

（8）： end for

（9）： for i\to \mathrm{1} to d，j\to \mathrm{1} to k do 计算平均特征值与特征向量

\overline{{\lambda }_i}=\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}({\lambda }_{ij})\to \overline{\mathit{\Lambda }}，\overline{\mathit{\Lambda }}为特征值构成的对角矩阵

\overline{e_i}=\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}(e_{ij})\to \overline{\mathit{V}}

（10）： end for

（11）： for i\to \mathrm{1} to d do 近似估计内积矩阵\mathit{B}的特征值与特征向量

\overline{\mathit{\Lambda }}\to {\mathrm{\Lambda }}^{total}

\overline{\mathit{V}}\to V^{total}

（12）： end for

（13）： for i\to \mathrm{1} to m do 特征值排序

选择前m个特征值和对应的特征向量\overline{{\lambda }_i},\overline{e_i}\to \tilde{\mathit{\Lambda }},\tilde{\mathit{V}}

（14）： end for

（15）： 得到降维数据X^{\mathrm{\text{'}}}=\tilde{\mathit{V}}{\tilde{\mathit{\Lambda }}}^{\mathrm{1}/\mathrm{2}}

算法2 计算内积矩阵\mathit{B}

输入：数据X(x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_d)\in R^{n\times d}

输出：内积矩阵\mathit{B}

（1）： 样本在原始空间的距离矩阵

\mathit{D}=\{d_{ij}\}\in R^{n\times n},d_{ij}=\parallel x_i-x_j{\parallel }_{\mathrm{2}}^{\mathrm{2}}

（2）： for i\to \mathrm{1} to n，j\to \mathrm{1} to n do 计算内积矩阵\mathit{B}

\begin{array}{c}{b}_{ij}=\frac{\mathrm{1}}{\mathrm{2}}(b_{ii}+b_{jj}+b_{ij})=\\ \frac{\mathrm{1}}{\mathrm{2}}(\frac{\mathrm{1}}{n}{\displaystyle \sum _{i=\mathrm{1}}^n}{d}_{ij}^{\mathrm{2}}+\frac{\mathrm{1}}{n}{\displaystyle \sum _{j=\mathrm{1}}^n}{d}_{ij}^{\mathrm{2}}-\frac{\mathrm{1}}{n^{\mathrm{2}}}{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{j=\mathrm{1}}^n}{d}_{ij}^{\mathrm{2}}-d_{ij}^{\mathrm{2}})\end{array}

3 实验

3.1　数据集

本文选取6个UCI数据集，详细信息如表1所列。

3.2　实验结果

选择6个UCI数据集进行实验，将数据集以3∶7比例划分为训练集与测试集。本文选择KNN算法^［22］对经过降维后的数据进行分类预测，通过对比算法的准确度验证方法的有效性。

本文将其与两种MDS实现进行对比：一种是按思想自行实现的MDS，另一种是基于 Sklearn库的MDS。相对于MDS方法和MDS-sklearn方法，EMDS方法准确率显著提高。Heart、Wine、Iris、Dermatology四个数据集选择两个维度进行实验，实验结果如图5所示。各个数据集KNN分类准确率结果如表2所列，结果表明EMDS方法降维数据的分类准确率相对于MDS和MDS-sklearn有明显提升，Iris数据集下，EMDS方法略低于MDS方法，但优于MDS-sklearn，可能由于数据数量较少或者距离计算方式略有影响，因此探究MDS的适用条件和改进距离计算也是未来改进的方向。

此外，为探究在统计意义上EMDS与MDS是否有显著差异，本文选择Kruskal-Wallis检验进行显著性检验分析，将EMDS与MDS和MDS-sklearn分别进行显著性分析计算，结果如表3所列，设置阈值为0.05，在大部分数据集中，P值小于阈值，验证了EMDS方法显著优于MDS和MDS-sklearn方法。

4 结论

样本随机性的存在，会影响算法的有效性和稳定性，从机器学习算法中消除随机一致性对提高算法能力具有较大的潜力。MDS作为低维嵌入的一种经典降维方法，内积矩阵B的特征值分解也存在随机一致性。为了获得更准确的低维坐标，本文从随机一致性角度出发，提出改进多维缩放方法（EMDS），通过使用平均特征值与特征向量估计内积矩阵\mathit{B}的特征值与特征向量，缓解了传统MDS方法中的随机一致性问题。在6个基准数据集上进行实验，实验结果表明了EMDS方法的有效性，可以极大地提高模型分类性能。未来的研究主要聚焦于以下问题：对于样本协方差矩阵中存在随机一致性相关工作的扩展；相关理论的完善；提高算法效率以及研究MDS的应用场景或适用条件；研究是否适用于超高维数据及性能，并做出进一步改进。

参考文献

[1] WANG J T, QIAN Y H, LI F J. Learning with Mitigating Random Consistency from the Accuracy Measure[J]. Mach Lang, 2020, 109(12): 2247-2281. DOI: 10.1007/s10994-020-05914-3 .

[2] SHEN D, SHEN H P, ZHU H T, et al. The Statistics and Mathematics of High Dimension Low Sample Size Asymptotics[J]. Stat Sin, 2016, 26(4): 1747-1770. DOI: 10.5705/ss.202015.0088 .

[3] JOHNSON R A, WICHERN D W. 实用多元统计分析[M]. 北京: 清华大学出版社有限公司, 2001: 52-113.

[4] JOHNSON R A, WICHERN D W. Practical Multivariate Statistical Analysis[M]. Beijing: Tsinghua University Press, 2001: 52-113.

[5] 周志华. 机器学习[M]. 北京: 清华大学出版社, 2016.

[6] ZHOU Z H. Machine learning[M]. Beijing: Tsinghua University Press, 2016.

[7] 王婕婷, 钱宇华, 李飞江, 等. 消除随机一致性的支持向量机分类方法[J]. 计算机研究与发展, 2020, 57(8): 1581-1593. DOI: 10.7544/issn1000-1239.2020.20200127 .

[8] WANG J T, QIAN Y H, LI F J, et al. Support Vector Machine with Eliminating the Random Consistency[J]. J Comput Res Dev, 2020, 57(8): 1581-1593. DOI: 10.7544/issn1000-1239.2020.20200127 .

[9] DE CARVALHO M. Mean, What Do You Mean?[J]. Am Stat, 2016, 70(3): 270-274. DOI: 10.1080/00031305.2016.1148632 .

[10] JOHNSTONE I M. On Minimax Estimation of a Sparse Normal Mean Vector[J]. Ann Statist, 1994, 22(1): 271-289. DOI: 10.1214/aos/1176325368 .

[11] BLASER R, FRYZLEWICZ P. Random Rotation Ensembles[J]. J Mach Learn Res, 2016, 17(4): 1-26.

[12] WICHMANN B A, HILL I D. Algorithm AS 183: An Efficient and Portable Pseudo-Eandom Number Generator[J]. J R Stat Soc Series C Appl Stat, 1982, 31(2): 188-190. DOI: 10.2307/2347988 .

[13] FAURE E, FEDOROV E, MYRONETS I, et al. Method For Generating Pseudorandom Sequence of Permutations Based on Linear Congruential Generator[C/OL]//2022 International Workshop on Computer Modeling and Intelligent Systems(CMIS). CEUR Workshop Proceedings, Vol-3137. 2022: 175-185.

[14] TSUNEDA A, MORIKAWA K. A Study on Random Bit Sequences with Prescribed Auto-correlations by Post-processing Using Linear Feedback Shift Registers[C]//2013 European Conference on Circuit Theory and Design (ECCTD). New York: IEEE, 2013: 1-4.

[15] DENG L Y, GUO R, LIN D K J, et al. Improving Random Number Generators in the Monte Carlo Simulations via Twisting and Combining[J]. Comput Phys Commun, 2008, 178(6): 401-408. DOI: 10.1016/j.cpc.2007.10.002 .

[16] Naesseth C, Ruiz F, Linderman S, et al. Reparameterization Gradients Through Acceptance-Rejection Sampling Algorithms[C]//Artificial Intelligence and Statistics. New York: PMLR, 2017: 489-498.

[17] BUGALLO M F, ELVIRA V, MARTINO L, et al. Adaptive Importance Sampling: The Past, the Present, and the Future[J]. IEEE Signal Process Mag, 2017, 34(4): 60-79. DOI: 10.1109/MSP.2017.2699226 .

[18] LEMIEUX C. Quasi–Monte Carlo Constructions[M]// Monte Carlo and Quasi-Monte Carlo Sampling. New York: Springer, 2009: 1-61.10.1007/978-0-387-78165-5_5

[19] GLASSERMAN P. Monte Carlo Methods in Financial Engineering[M]. New York: Springer, 2004.

[20] FRISCH D, HANEBECK U D. Deterministic Von Mises-Fisher Sampling on the Sphere Using Fibonacci Lattices[C]//2023 IEEE Symposium Sensor Data Fusion and International Conference on Multisensor Fusion and Integration (SDF-MFI). New York: IEEE, 2023: 1-8. DOI: 10.1109/SDF-MFI59545.2023.10361396 .

[21] FRISCH D, HANEBECK U D. Rejection Sampling from Arbitrary Multivariate Distributions Using Generalized Fibonacci Lattices[C]//2022 25th International Conference on Information Fusion (FUSION). New York: IEEE, 2022: 1-7.

[22] FRISCH D, HANEBECK U D. Deterministic Gaussian Sampling with Generalized Fibonacci Grids[C]//2021 IEEE 24th International Conference on Information Fusion (FUSION). New York: IEEE, 2021: 1-8.

[23] ALEXA M. Super-Fibonacci Spirals: Fast, Low-discrepancy Sampling of SO(3)[C]//2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). New York: IEEE, 2022: 8281-8290. DOI: 10.1109/CVPR52688.2022.00811 .

[24] MARQUES R, BOUVILLE C, BOUATOUCH K, et al. Extensible Spherical Fibonacci Grids[J]. IEEE Trans Vis Comput Graph, 2021, 27(4): 2341-2354. DOI: 10.1109/TVCG.2019.2952131 .

[25] UKEY N, YANG Z, LI B, et al. Survey on Exact kNN Queries over High-dimensional Data Space[J]. Sensors, 2023, 23(2): 629. DOI: 10.3390/s23020629 .

基金资助

国家自然科学基金青年基金(62106132)

国家自然科学基金青年基金(62306170)

山西省科技重大专项(202201020101006)

山西省基础研究计划(20210302124271)

山西省基础研究计划(202103021223026)

山西省科技创新人才团队专项资助(202304051001001)