基于保守自适应K-最近邻算法的维数约简

Dimensional Reduction Based on Conservative Adaptive K-Nearest Neighbor Algorithm

针对传统的k-最近邻算法存在不能根据样本密度进行自适应选择近邻点数目的缺陷,提出一种改进型的保守自适应k-最近邻算法。该算法首先对每个样本点选择m个近邻点,m取一个比较小的正整数,以保证不存在某个样本点无近邻点;其次把每个样本点的第m+1个最小的欧式距离作为最小值,最小值的α倍作为寻找近邻点的阈值;最后应用经典MDS算法计算。swiss-roll数据集上的降维实验结果表明,降维后的数据能很好地保持原有数据的邻域特性,能有效快捷地寻找近邻点。

An improved conservative and adaptive k-nearest neighbor algorithm is brought forward because the traditional k-nearest neighbor algorithm has a defect that can not select neighbor points adaptively based on the sample density.In this algorithm,m neighbor points,m a relatively small positive integer,are selected for each sample point to ensure that every sample point has its neighbor points,and the No.m＋1 smallest Euclidean distance is taken as the minimum value for each sample point and α times of the minimum value as the threshold for searching neighbor points,then the classical MDS algorithm is used to calculate.The dimensional reduction experimental results on swiss-roll dataset show that it is an efficient way to find neighbor points and keep the neighborhood characteristics of the original data well.