一种基于信息熵的超高维数据降维算法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN106407363A(43)申请公布日2017.02.15(21)申请号201610810509.1(22)申请日2016.09.08(71)申请人电子科技大学地址611731四川省成都市高新西区西源大道2006号(72)发明人何兴高李蝉娟张效藩(51)Int.Cl.G06F17/30(2006.01)权利要求书2页说明书2页附图2页(54)发明名称一种基于信息熵的超高维数据降维算法(57)摘要本发明提出了一种基于信息熵的高维数据降维算法。属于高维数据预处理领域。本发明旨在解决传统PCA算法在实际的应用中存在的问：当数据维数(特征)足够高的时候，无法将所有数据特征读一次性入内存以进行分析计算，实验在不借助云平台、分布式计算平台的情况下，使用了分块处理的方法，但是此方法处理耗时太长，不能满足实际应用需求。在此基础上，引入信息熵的思想，对PCA算法进行了改进，使得改进后的算法能够用于处理超高维数据降维，实验结果表明在保证保留相同比例原始数据信息的情况下，后者运行耗时相较于分块处理算法缩减了60倍。CN106407363ACN106407363A权利要求书1/2页1.信息熵可以度量信息量大小，高维数据降维是解决直接处理高维数据面临的四大难题的有效方法，对超高维数据进行分析计算，更要进行降维处理，一种基于信息熵的超高维数据降维算法由以下特征构成：//Input(输入)需要降维的数据矩阵Un×m(或者非矩阵形式rdata)，信息熵阈值et，特征值贡献率f//Output(输出)原始数据降维后的结果Yk×m/*getMatrix函数，将原始数据rdata转换为矩阵形式，记录含有的属性置为1，没有的属性为0，输出n×m的0、1矩阵，某些原始数据非矩阵形式的时候使用*/Matrix＝getMatrix(rdata)/*getEntropy函数，计算属性αi的信息熵值*/H(i)＝getEntropy(αi)/*randomSplit函数，将转换为矩阵的数据Matrix按比随机抽取相应的记录作为训练集，剩下的为检验集*/[B,C]＝randomSplit(Matrix)/*eig函数，计算矩阵的特征值和特征向量*/[eigenVe,eigenVa]＝eig(Cov)/*变量f，计算特征值贡献率，表征主成分占原始数据信息的比例*/。2.综合权利要求1的各项特征，对超高维数据的降维过程由文件testepca.m表达：/*testepca.m，降维的主程序，对信息熵处理后的数据进行pca降维处理，输出降维结果*/1)Matrix＝getMatrix(rdata)2)计算信息熵，做筛选3)分割数据矩阵2CN106407363A权利要求书2/2页[B,C]＝randomSplit(Matrix)//B为训练集,C为检验集4)样本B矩阵中心化：即每一维度减去该维度的均值X＝B–repmat(mean(B,2),1,m1)5)计算不同维度之间的协方差，构成协方差矩阵：C＝(X*XT)/size(X,2)6)计算协方差矩阵的特征向量eigenVector和特征值eigenValue[eigenVector,eigenValue]＝eig(Cov)7)选择最大的k个特征值对应的k特征向量分别作为列向量组成特征向量矩阵Vn×k，k由f计算。8)计算降维结果：Y＝VT*X9)对矩阵C中心化，得X010)计算结果：Y0＝VT*X0以上降维结果Y和Y0可用于后续分析计算。3CN106407363A说明书1/2页一种基于信息熵的超高维数据降维算法技术领域[0001]本发明属于高维数据预处理领域，更为具体地讲，是一种基于信息熵改进的超高维数据降维算法。背景技术[0002]随着信息科学技术的飞速发展，信息的表示越来越全面，人们获取数据越来越容易、关注的数据对象日渐复杂，业界对数据分析、处理技术的需求最为迫切，特别是对高维数据的分析与处理技术。直接处理高维数据会面临以下困难：维数灾难、空空间、不适定、算法失效。本发明针对数据特征维太高，内存受限，不能一次性读入内存分析计算的问题，采用分块处理方法，处理流程如图1所示。但结果显示，运行耗时太长，不能满足应用需求，在此基础上，引入信息熵，首先做特征筛选，大大降低了特征数量，再做降维处理，具体流程如图2所示，具体算法如图3所示，整个过程运行耗时减少数倍，降维结果保留了大部分主成分，依然能满足应用需求。发明内容[0003]本发明的最终目的是对原始超高维数据进行降维处理，使得降维后的数据可以在较低内存，用时较少的情况下得以继续分析处理。本发明对主要利用了信息熵在信息处理上的意义，对PCA算法进行了改进。所谓的数据维数就是每条记录数据的属性个数。[0004]为实现