数据挖掘、机器学习领域普遍存在数据维度很高但同时样本数量偏少的情形，经典的分类、回归算法在对这种数据进行分析处理时往往计算代价过高甚至完全失效。一般的做法是在数据分析与处理之前对数据集进行特征提取或特征选择，抽取样本最相关特征，消除不相关特征与噪声特征，以利于后续工作。本文在深入分析与研究常用特征提取与特征选择方法基础上，提出了一些克服小样本与高计算复杂度问题的有效算法，主要内容如下：1、提出了一种基于K-近邻局部间隔的判别映射方法。首先，将假设间隔概念应用于样本数据的局部分析并加以扩展，在样本分布空间要求局部邻域内同类样本与非同类样本能够尽可能判别；其次，鉴于对未知样本特征提取的需要，将局部邻域结构投影于一个较低维度的子空间内，要求在子空间内局部邻域仍然保持与同类样本距离和与非同类样本距离差异极大，即局部间隔极大化。考虑到求解局部最近邻步骤包含了矩阵求逆运算，基于投影定理使用Gram-Schmidt正交化降低时间复杂度。最后，探讨了基于局部间隔的判别映射方法与局部线性嵌入算法（Local Linear Embedding，LLE）之间的关系，发现基于局部间隔的判别映射方法可以视为LLE算法在有指导学习情形下的线性扩展。2、为进一步提高基于局部间隔的特征提取能力，引入无标记样本，由非同类样本估计局部样本的判别性质，由较多的未标记近邻样本估计局部几何结构。将样本局部分布投影于较低维度的子空间，则算法具有了判别不同子流形的能力。在可视化实验中发现，这种基于局部间隔的半监督判别嵌入算法能够发现不同子流形，同时能够得到较高的分类精度。3、谱聚类是被证明效果较好的无指导学习方法。研究发现，Laplacian矩阵的特征向量指示了样本的类别信息，本文证明了Laplacian矩阵的若干小特征值表现了簇结构的显著性，即特征值趋于零说明聚类效果会比较好。将这一定理作为衡量原始特征重要度的准则，提出了基于无监督技术的特征选择算法，即重要特征能够保证簇结构的显著性，而不相关特征不能保证簇结构的显著性甚至破坏簇结构。由于每选择一个特征都需要对Laplacian矩阵的特征分解步骤，为此使用Nystr m方法逼近半正定矩阵特征值以降低计算复杂度。4、将流形学习的思想应用到特征排序，通过对特征赋予权重的方法计算特征的相关度。主要思想是相关特征在加权特征空间邻域保持同类样本仍然为近邻，而对于非同类近邻则应尽量远离。提出了两种评价特征相关度的标准：商准则与差准则，由于避免了特征分解步骤，计算表明两种准则下算法的时间复杂度为样本维度的线性函数，或样本数量的二次函数，与RELIEF-F算法相当。另外，通过对商准则的进一步研究，提出了基于局部学习的半监督特征加权与排序框架，将无标记样本引入，要求在加权空间相关特征不仅能够更好的判别样本，还能够保持样本的局部光滑性质。半监督特征排序框架同样不需要特征分解步骤，因此具有较低的计算复杂度。从此框架导出两种半监督特征排序算法：基于线性判别分析的特征排序与基于局部判别嵌入分析的特征排序，前者适于线性可分问题的特征排序，后者适于非线性可分问题的特征排序。