粗糙拟阵及其在高维数据降维中的应用研究

《粗糙拟阵及其在高维数据降维中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、电子科技大学UNIVERSITYOFELECTRONICSCIENCEANDTECHNOLOGYOFCHINA博士学位论文DOCTORALDISSERTATION论文题目粗糙拟阵及其在高维数据降维中的应用研究学科专业计算机软件与理论学号201111060305作者姓名王石平指导教师朱清新万方数据分类号密级UDC注1学位论文粗糙拟阵及其在高维数据降维中的应用研究（题名和副题名）王石平（作者姓名）指导教师朱清新、教授、电子科技大学祝峰、教授、闽南师范大学WitoldPedrycz、教授、加拿大阿尔伯塔大学（

2、姓名、职称、单位名称）申请学位级别博士学科专业计算机软件与理论提交论文日期2014年9月15日论文答辩日期2014年12月06日学位授予单位和日期电子科技大学2014年12月25日答辩委员会主席评阅人注1：注明《国际十进分类法UDC》的类号。万方数据Roughmatroidanditsapplicationtodimensionalityreductioninhigh-dimensionaldataADoctorDissertationSubmittedtoUniversityofElectronicS

3、cienceandTechnologyofChinaMajor:ComputerSoftwareandTheoryAuthor:ShipingWangAdvisor:Prof.QingxinZhuSchool:SchoolofComputerScienceandEngineering万方数据独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构

4、的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。作者签名：日期：年月日论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后应遵守此规定）作者签名：导师签名：日期：年月日万方数据摘要摘要随着大数据时代

5、的来临，大规模的非结构化和半结构化的数据存在于每个行业和每个领域，这就迫切要求人类对海量数据进行挖掘和规则提取。数据量大、数据类型繁多、价格密度低和速度快时效高是大数据的四个重要特征，这就意味着传统的方法和技术已无法应对目前的大数据时代。正因为如此，数据的降维显得尤为重要，这一方面可以缓解甚至解决“维数灾难”，降低计算成本，减少过拟合风险，另一方面可以更好地认识和理解数据特征间的联系。本文相对系统地研究了各类数据类型的特征选择，尤其是建立了离散型和连续型的特征选择的专门模型和算法。特别地，本文还提出了次

6、模函数的贪婪算法的评价体系，这对建立高效的贪婪算法有着重要的指导意义。同时，我们还将稀疏表示、核函数和非负矩阵分解等技巧运用到特征选择中，设计了多个高效的特征选择算法。具体的创新性研究成果主要体现在如下四个方面：(1)引入拟阵次模性来评估基于贪婪策略的特征选择算法。很多高效的算法都是建立在连续平滑的目标优化函数之上的，而对于离散型数据的特征选择问题，这些算法往往是无效的，从而几乎所有的离散型数据的特征选择算法都是基于贪婪策略。众所周知的是，贪婪算法得到的解往往不是整体最优解，而是近似解或满意解。这就造成

7、了满意解和整体最优解之间的“灰色地带”，而如何度量这种“灰色地带”，即满意解和最优解之间的差异，是一个非常困难但非常重要的问题。为此，本文首先建立了粗糙集的拟阵结构，再次借助拟阵次模性来刻画贪婪算法对最优解的逼近程度。特别地，本文还给出了几类特殊的目标优化函数的的贪婪算法的紧凑边界。(2)提出线性结构保持的特征选择算法。如何衡量数据的线性结构一直是很困难的问题，而对于特征间具有良好相关性的数据，这一问题显得异常重要。本文借助稀疏编码来刻画数据的线性相关性。进一步地，考虑到稀疏表示过程中利用L1-范数来调

8、节表示系数的稀疏性程度，这导致了目标优化函数的非平滑性。为此，本文通过给定系数矩范数的上界，将这类非平滑的优化目标函数转变为平滑的优化目标函数。特别地，本文还通过邻域来刻画数据的局部线性保持性，将稀疏编码过程和特征选择过程融入到一个框架中，提出邻域嵌入的特征选择算法。(3)引入特征选择算法的核函数技巧。核函数是一种重要的处理非线性数据的技巧，其基本思想是将原数据映射到高维乃至无穷维空间中进行处理，而这一过程并不需要非线性变换函数的表达式和参