论文部分内容阅读
随着计算机技术在社会各领域的深入渗透,数据正在加速迅猛累积。如何从这些海量数据中挖掘出潜在的有价值信息是现在面临的重要挑战。大规模数据的一个重要体现就是描述数据的特征维度极高,但是这些特征的很大一部分都是冗余或噪声特征。这些冗余和噪声不但将造成存储资源的大量浪费,而且还会降低挖掘学习算法的运行效率。更严重的是,它们还会将真正有价值的信息湮没从而恶化学习算法的性能。特征选择正是在这种情况下应运而生。特征选择就是尽量保持本质信息不受损或少受损的前提下,从纷繁芜杂的原始特征集合中选出一个较为精简的子集。 本文分别将会从信息论和稀疏诱导的角度,围绕从原始数据中祛除冗余噪声特征选择精简特征子集这一目标,开展一系列具体而深入的特征选择的研究工作。本文的主要贡献和创新如下: 1.从信息论的基本概念出发,发现了Fano不等式之外另一种全新的Bayes错误率和关于特征与类别的互信息量的关系。为现有的由不同启发式准则发展出的基于信息论的算法建立了一个统一的理论框架。在此框架内,受Occam剃刀原理启发提出一种新的基于信息论的特征选择算法。该算法还可以通过嵌入一个插件用于辨别冗余和噪声特征以更好地进行特征选择。该算法的有效性在实验中得到了充分的验证。 2.受稀疏表示和支持向量机的启发,提出了一种基于不等式约束的l2,p范数(0<p≤1)最小化的特征选择算法。该算法模型在多步精巧的转换后可以通过迭代的加权最小二乘求解。通过严格理论证明,该优化算法可以保证收敛且收敛点满足KKT条件。该算法及其优化技术的有效性在实验中得到了充分的验证。 3.提出一种建立在l2,r范数(0<r≤2)型损失和l2,p范数(0<p≤1)型正则之上的一般性特征选择算法。提出了一个新的迭代的权重调整最小二乘的优化方法来求解该算法模型。从理论上证明了该优化方法将会收敛且收敛点是到驻点,而收敛阶是min(2-r,2-p)。该算法及其优化技术的有效性在实验中得到了充分的验证。 4.提出了一种建立在新的合页损失和l2,p范数(0<p≤1)型正则之上的特征选择算法。提出了一种新的加速近邻映射梯度下降法来优化新提出的算法模型。理论分析表明该优化方法将会收敛,而且当模型是凸的情况下,收敛速度将达到O(1/k2)(k为迭代次数),这是光滑优化问题的最佳收敛速度。该算法及其优化技术的有效性在实验中得到了充分的验证。