随着大数据时代的来临,大规模的非结构化和半结构化的数据存在于每个行业和每个领域,这就迫切要求人类对海量数据进行挖掘和规则提取。数据量大、数据类型繁多、价格密度低和速度快时效高是大数据的四个重要特征,这就意味着传统的方法和技术已无法应对目前的大数据时代。正因为如此,数据的降维显得尤为重要,这一方面可以缓解甚至解决“维数灾难”,降低计算成本,减少过拟合风险,另一方面可以更好地认识和理解数据特征间的联系。本文相对系统地研究了各类数据类型的特征选择,尤其是建立了离散型和连续型的特征选择的专门模型和算法。特别地,本文还提出了次模函数的贪婪算法的评价体系,这对建立高效的贪婪算法有着重要的指导意义。同时,我们还将稀疏表示、核函数和非负矩阵分解等技巧运用到特征选择中,设计了多个高效的特征选择算法。具体的创新性研究成果主要体现在如下四个方面:(1)引入拟阵次模性来评估基于贪婪策略的特征选择算法。很多高效的算法都是建立在连续平滑的目标优化函数之上的,而对于离散型数据的特征选择问题,这些算法往往是无效的,从而几乎所有的离散型数据的特征选择算法都是基于贪婪策略。众所周知的是,贪婪算法得到的解往往不是整体最优解,而是近似解或满意解。这就造成了满意解和整体最优解之间的“灰色地带”,而如何度量这种“灰色地带”,即满意解和最优解之间的差异,是一个非常困难但非常重要的问题。为此,本文首先建立了粗糙集的拟阵结构,再次借助拟阵次模性来刻画贪婪算法对最优解的逼近程度。特别地,本文还给出了几类特殊的目标优化函数的的贪婪算法的紧凑边界。(2)提出线性结构保持的特征选择算法。如何衡量数据的线性结构一直是很困难的问题,而对于特征间具有良好相关性的数据,这一问题显得异常重要。本文借助稀疏编码来刻画数据的线性相关性。进一步地,考虑到稀疏表示过程中利用L1-范数来调节表示系数的稀疏性程度,这导致了目标优化函数的非平滑性。为此,本文通过给定系数矩范数的上界,将这类非平滑的优化目标函数转变为平滑的优化目标函数。特别地,本文还通过邻域来刻画数据的局部线性保持性,将稀疏编码过程和特征选择过程融入到一个框架中,提出邻域嵌入的特征选择算法。(3)引入特征选择算法的核函数技巧。核函数是一种重要的处理非线性数据的技巧,其基本思想是将原数据映射到高维乃至无穷维空间中进行处理,而这一过程并不需要非线性变换函数的表达式和参数,从而有效地避免了“维数灾难”。也正是因为非线性变换函数是未知的,很多模型并不能嵌入核技巧。本文利用投影矩阵将特征选择问题表示为矩阵分解问题,再利用核技巧实现对数据的非线性处理。(4)提出一种高阶矩阵分解问题的近似算法。数据的高维性是大数据的一个重要特征。通过矩阵分解,可以实现对高维数据的降维、压缩和归类。然而,大部分的现存的矩阵分解方面的研究成果都是局限于二阶的优化问题,而实际生活中的众多优化问题往往可以形式化为高于二阶简称高阶的矩阵分解问题,如聚类问题和含有正交约束的各类优化问题。本文将特征选择问题形式化为四阶的目标优化问题,继而通过惩罚矩阵提出一套解决高阶矩阵分解问题的近似算法并证明了其收敛性。综上所述,本文从离散数据的特征选择问题出发,建立了拟阵和粗糙集之间的联系,定义了评价贪婪算法的度量,引入了特征选择的核技巧,提出了数据线性结构保持的度量,并给出了高阶矩阵分解的近似算法。这些研究成果进一步丰富了数据降维技巧体系,也为后续研究工作奠定了重要基础。