生物信息处理技术与方法

　　《北京理工大学教育基金会·教授文库：生物信息处理技术与方法》：　　（2）空空间现象　　以正态分布的数据为例，一个正态分布可以用期望值L和标准差R来表示。数据点与期望值之间的距离服从高斯分布，但与期望点的相对方位是随机选取的。应该注意的是，相对于一个点的可能的方向的数目，也是随着维数的增大而呈指数级增长。这样一来，数据空间中的其他数据与中心点之间的距离虽然仍然服从同样的分布，但数据点之间的距离也还会随着维数的增大而增加。如果考虑数据集的密度，就会发现，虽然可能没有一个点离中心点的距离很近，但在中心点还是会出现一个*大值。这种在高维空间中，在空区域中，点的密度可能会很高的现象即被称为“空空间现象”。　　（3）维灾　　Bellman**次提出了“维灾”这一术语。它*初的含义是，不可能在一个离散的多维网格上用蛮力搜索去优化一个有着很多变量的函数。这是因为网格的数目会随着维数也就是变量数目的增长呈指数级增长。随着时间的推移，“维灾”这一术语也用来泛指在数据分析中遇到的由于变量（属性）过多而引起的所有问题。这些问题在信息检索领域主要表现在两个方面：一方面，随着维数的升高，索引结构的修剪效率迅速下降，当维数增加到一定数量时，采用索引结构还不如顺序扫描；另一方面，在高维空间中，由于查询点到其*近邻和*远邻在很多情况下几乎是等距离的，*邻近的概念常常会失去意义。　　针对高维数据的特点，主要从以下几个方面对高维数据进行分析：　　（1）高维空间中的距离函数或相似性度量函数　　距离函数和相似性度量函数在很多数据挖掘算法中扮演着非常重要的角色，常常用来衡量对象之间的差异程度和相似程度。由于“维灾”与传统方法中采用Lk范数作为距离函数有关，因此，通过重新定义合适的距离函数或相似性度量函数可以避开“维灾”的影响。　　（2）高效的高维数据相似性搜索算法　　目前，绝大多数的高维索引结构和相似性搜索算法都是基于数值型数据，并且这些索引结构在应用于数据挖掘时都存在着不同程度的局限性。因此，需要设计更为高效的相似性搜索算法，包括两部分内容：一是对未设计或研究较少的其他类型高维数据相似性搜索方法的研究；二是对现有高维索引结构或搜索算法性能的改进。　　（3）高效的高维数据挖掘算法　　针对在高维空间中，多数数据挖掘算法效率下降的问题，需要设计更为高效的高维数据挖掘算法。如在高维索引结构失效的情况下，在聚类算法或异常检测算法中采用并行算法、增量算法以及采样技术等，提高算法的效率。根据高维数据的特点，设计新颖的频繁模式挖掘算法，提高算法的执行效率。　　（4）在高维空间中对失效问题的处理　　如前所述，在高维情况下，*近邻的概念失去了意义，进而导致基于距离的聚类问题和异常检测问题失去意义。这些问题在高维情况下需要重新进行定义，并设计出相应的挖掘算法。　　（5）选维和降维　　通过选维和降维，可以将高维数据转换为低维数据，然后采用低维数据的方法进行处理。因此，研究有效的选维和降维技术也是解决高维问题的重要手段之一。如在分类算法中，通过选维和降维可以减少冗余属性以及噪声对分类模式造成的影响。　　……