论文部分内容阅读
数据编码问题一直是数据挖掘、机器学习、模式识别等领域的关键问题。随着在线应用的蓬勃发展,如在线购物,在线社交网络等,在线数据规模日渐庞大,在线数据格式也多种多样,如文本、视频、图像等。对复杂的在线数据进行合理地编码表示,对于在线数据挖掘起着关键作用。数据编码的基通常分特征空间或训练数据集构成的字典。当数据编码的基为特征空间,根据对编码系数的不同约束,编码问题可转换为特征选择问题和主成分分析问题。特征选择问题相当于通过对编码系数进行离散约束,去除原始特征空间中冗余特征和不相关特征,得到一个最优的特征表示子集;主成分分析问题则通过优化函数得到一个连续值的编码系数,获得反映数据本质结构的编码表示,最为著名的问题是得到复杂数据中的低秩结构表示的主成分分析问题。当数据表示的基为训练数据集构成的字典,则编码问题为通过字典对目标数据进行线性表示问题,近年来最为热点的为稀疏编码。因此,基于数据编码方向,本文所研究的具体问题为特征选择问题、主成分分析问题以及稀疏编码问题。虽然这些问题研究至今,已涌现出大量有效的相应的算法,但是针对在线应用环境带来的更多挑战,如庞大的特征空间,复杂的数据类型,已有算法存在一定的不足。更具体而言,特征选择问题中的全局特征空间难以获得,特征抽取代价高昂,高维特征空间的处理对服务器产生巨大压力,而已有的特征选择方法不能兼顾在线环境和特征之间的语义关联;主成分分析问题最为常用的方法为优化核范数约束的目标函数,得到低秩的真实数据编码表示,然而,核范数约束仅为秩函数一个凸的近似问题,并不能保证得到的解是真正的低秩;稀疏编码问题常用的方法是对编码系数进行C1范数约束,然而在线环境下训练字典结构复杂多样,一味采用稀疏约束,会导致编码结果的不稳定性。因此,为了解决以上实际问题,本文提出了以下解决方案,可总结为:1) 针对在线环境下,数据特征空间的动态性以及超高维问题,本文研究了在线特征选择问题,提出了在线组特征选择方法。在线特征选择,即已知全局的样本空间,动态抽取特征的过程,而非依赖全局的特征空间。已有的在线特征选择算法可进行动态特征选择,却没有考虑动态特征之间的关联性,而特征之间的关联性具有丰富的语义信息,对于特征选择有重要的作用。因此,本文认为特征之间具有组相关性,组内特征具有完整的语义,如图片的纹理特征,而特征组之间亦具有组间相关性。因此,本文针对此问题,提出在线组特征选择算法(Online Group Feature Selection, OGFS),具体包括在线组内特征选择和在线组间特征选择。在线组内特征选择根据组内语义相关性,选择具有强判别性的“好”特征;在线组间特征选择直接采用稀疏的线性回归模型Lasso,从不同特征组中选择最优的特征子集。在图像分类,人脸验证等实际应用中的实验,验证了OGFS算法优于已有的在线特征选择算法;2) 针对在线环境下,观测到的数据通常具有复杂多变的结构,在很多计算机视觉等应用中,真实数据通常可由低秩结构表示,噪音等其他部分可由稀疏结构表示的特点,本文研究了主成分分析问题,提出了一种Schatten-p范数和lq范数联合约束的主成分分析模型,p,q-主成分分析模型,具有广泛的实际应用场景,如视频监控中的背景(低秩结构)和移动目标(稀疏结构),人像图片中的人脸(低秩结构)和阴影(稀疏结构)。解决此问题的常用方法为鲁棒主成分分析法(RPCA),即用核范数对秩函数进行估计,用l1范数对l0范数进行估计,但是并不能保证得到真正低秩和稀疏的编码表示。因此,本文为了更好的解决此问题,提出用Schatten-p范数约束估计秩函数,用lq范数估计l0范数。由于此目标函数非凸,为了解决此问题,本文提出了一种最近迭代加权算法(Proximal Iteratively Reweighted Algorithm, PIRA),将低秩矩阵和稀疏矩阵的求解转化为两个子问题,迭代交互求解。在每次迭代过程中,目标子问题都拥有闭式解,因此,此算法具有高效性,并能满足在线环境下的实时性要求。同时,实验验证了目标函数值随迭代次数逐渐收敛;相比较于常用的核范数和l1范数约束,更能逼近原始主成分问题的解。在实际应用场景,如图像去噪,物体识别,人脸阴影/光斑去除,验证了此模型的优越性,以及算法的有效性。3) 针对在线环境下,在线数据具有不稳定性,增加了分类任务的难度,本文研究了提出了一种自适应的稀疏编码模型,并基于此模型构建分类器(Adaptive Sparse Representation based Classifier)。稀疏编码模型采用对编码系数进行l1范数的稀疏性约束,有利于获取极具判别性的编码表示。但是,当字典中训练样本相关性较强,即不同目标的样本差异性较小时,稀疏编码会导致不稳定的结果,从而影响分类等数据挖掘任务的效果。此时,基于l2范数约束的协作编码模型,考虑了样本关联性,更具优势。因此,本文同时考虑了字典样本间的相关性和编码系数的判别性,提出一种自适应的编码模型,即当训练样本相对独立,自适应稀疏编码模型的效果类似于稀疏编码模型;当训练样本具有强关联性,自适应稀疏表示模型类似于协作编码。一般情况下,自适应编码系数的稀疏性介于稀疏编码和协作编码之间。基于此编码模型,本文提出了一种基于自适应稀疏表示的分类模型,对于多样复杂的字典结构具有自适应性。通过人脸识别等应用,验证了此算法明显优于稀疏编码分类模型和协作编码模型。