降维(数据库)

时间：2022-12-30 06:30:01 | 来源：信息时代

时间：2022-12-30 06:30:01 来源：信息时代

    降维 : 将高维多媒体数据的特征向量映射到一维或者低维空间的过程。在高维特征数据库中,高维数据存在数据冗余。由于索引结构的性能随着维数的增大而迅速降低,在维数大于10以后,性能还不如顺序扫描,形成维数灾难(dimensional curse)。降维后,应用成熟的低维索引技术,以提高性能。降维技术可以有效地解决维数灾难问题,但是,在降维过程中也可能引起信息丢失,从而影响查询精度,这是采用降维技术时必须关注的问题。降维技术是高维数据管理领域的研究热点之一,开始于20世纪90年代中期,除以下介绍的属于特征抽取的降维方法外,还有空间填充曲线(space filling curve)、奇异值分解(SVD)、距离映射算法(distance-mapping algorithm)、FastMap算法、pyramid算法等。
1.基于低维投影的降维方法
(1)主成分分析(principal component analysis,PCA): 是使用最为广泛的线性降维方法之一,它先将数据投影到某一个主成分上,然后丢掉具有较小方差的那些维的信息,寻找具有最大方差的线性特征集,达到降维的目的。该方法的概念简单、计算方便,但是,没有统一的标准来确定主成分及其数量。
(2)投影法(projection pursuit,PP):其基本思想是将高维数据投影到低维(一般是1～3维)子空间上,通过分析和研究投影数据以达到了解原始数据的目的。该方法最早产生于20世纪70年代初,Kruskal将数据投影到低维空间,通过极大化某个指标,以发现数据的聚类结构。聚类效果取决于索引函数的选择和优化算法。该方法可有效排除噪声数据的干扰,但是,计算量大,不适用于高度非线性数据。
2.基于神经网络的降维方法
(1) 自动编码神经网络法(auto-encoder networks):是一种前向反馈网络。该网络把高维空间的输入向量映射到具有最少神经元的一层的激励所表示的低维空间中,而具有最少神经元的一层的下一层再把低维表示映射到D维空间。
(2) 自组织映射法(self-organizing mapping):对每个聚类都赋予降维后的空间中的固定位置,并根据该位置用邻居函数来评价聚类之间的近似度。邻居函数的值越大聚类之间的接近程度越高。根据邻居函数值,高维数据被映射到最优聚类的位置,实现高维数据的降维。该方法能很好地用于高维数据可视化。
(3)生成建模法(generative modelling): 是基于混合密度估计的,所有的聚类都用高斯混合密度表示。
3. 基于数据间相关度的降维方法
(1)多维比例法(multi-dimensional scaling): 是寻找保留了数据主要特征的低维空间,在该空间里的数据点不仅和高维空间中的原数据对应,并且保持原数据点之间的欧式距离的差异度。适用于原始数据的距离矩阵已知的情况。
(2) 随机邻居嵌入法(stochastic neighbor embedding): 不直接使用数据间的差异,而是用它们定义转换矩阵,该矩阵的每一行都包含了与一个数据点相关联的分布,该矩阵则定义了数据点集上的随机遍历。
(3)等容积法(isometric mapping): 是对多维比例法的扩展,区别在于采用测地距离表示两点的差异。
(4)局部线性嵌入法(locally linear embedding):是非线性降维方法,其中高维空间由许多描述它的本质属性并且相互邻接的局部线性块组成。该方法有效地获取高维数据的本质特征,计算方法简单、直观。
(5) 拉普拉斯特征映射法(Laplacian eigen maps):拉普拉斯特征映射法首先将数据点与其最近邻居连接起来以构建一个邻居图,然后给图的每条边均赋予相应的权值,最后寻求数据集的嵌入坐标表示,并保证嵌入点之间的平方距离最小,从而得到降维空间中的最优低维表示向量。
4.基于分形的降维方法
如果一个数据集的部分分布结构或属性与整体分布相似,则称该数据集是分形的。基于分形的降维方法首先要比较准确地估计出数据的本征维,包括分数维,进而进行降维处理。