基于信息熵的高维稀疏大数据降维算法研究
何兴高;李蝉娟;王瑞锦;邓伏虎;刘行
期末考试动员【摘 要】数据降维是从高维数据中挖掘有效信息的必要步骤.传统的主成分分析(PCA)算法应用于超高维稀疏数据降维时,存在着无法将所有数据特征一次性读入内存以进行分析计算的问题,而之后提出的分块处理PCA算法由于耗时太长,并不能满足实际需求.本文引入信息熵的思想对PCA算法进行改进,提出E-PCA算法,先利用信息熵对数据进行特征筛选,剔除大部分无用特征,再使用PCA算法对处理后的超高维稀疏数据进行降维.通过实验结果表明,在保留相同比例原数据信息的情况下,本文提出的基于信息熵的E-PCA算法在内存占用、运行时间以及降维结果都优于分块处理PCA算法.%Data dimensionality reduction is a necessary step in mining effective information from high-dimensional data. When applying the traditional principal component analysis (PCA) algorithm to high-dimensional spar data dimensionality reduction, there is a problem that unable to read all data features at once into memory for analysis and calculation, furthermore, the improved block processing PCA algorithm also can not meet the actual requirements becau of the time consuming. In this paper, we pro
po the E-PCA algorithm by introducing the concept of information entropy to improve the PCA algorithm. First, the uless features are eliminated through feature lection bad on information entropy, and then PCA algorithm is ud to reduce the dimensionality of large, high-dimensional spar data. The experimental results show that in the ca of keeping the same proportion of raw data, the information entropy-bad E-PCA algorithm propod in this paper is superior to block processing PCA algorithm in terms of memory usage, run time and the results of dimension reduction.
【期刊名称】《电子科技大学学报》
【年(卷),期】2018(047)002
【总页数】7页(P235-241)
【关键词】分块处理;降维处理;高维稀疏大数据;信息熵;主成分分析
【作 者】何兴高;李蝉娟;王瑞锦;邓伏虎;刘行
necps
【作者单位】电子科技大学信息与软件工程学院 成都 610054;电子科技大学信息与软件工程学院 成都 610054;电子科技大学信息与软件工程学院 成都 610054;电子科技大学信息与软件工程学院 成都 610054;电子科技大学信息与软件工程学院 成都 610054
【正文语种】中 文
似是而非【中图分类】TP309
随着大数据产业的快速发展，人们关注的数据对象日渐复杂，业界对数据分析、处理技术的需求更为迫切，特别是对高维数据的分析与处理技术。直接处理高维数据会面临以下困难[1-6]：维数灾难、空空间、不适定及算法失效等。为解决以上问题，一种有效的方法就是对高维数据进行降维，分为特征选择和特征变换两种方式[2]。按不同划分标准，算法可分为线性与非线性、监督与非监督、全局与局部等，如PCA、ICA、LDA、LLE、ISOMAP、LTSA、KPCA等。PCA适用于数值型数据，先将数据转换为矩阵形式，再进行相关计算，算法无参数限制，但在某些情况下运行效率不佳。如在处理用户访问网站记录数据时，网站数目庞大，用户能访问的网站数目甚少。这类数据特征维高，有用信息少，即高维稀疏大数据。本文就PCA在处理高维稀疏数据时存在的受内存限制、处理时间长的
问题，给出了改进的解决方法。实验结果显示，改进算法能够保留相同比例原数据信息的情况下降低时间成本。新生代表发言稿
1 相关研究
1901年，统计学领域首先提出主成分分析(principal component analysis, PCA)[7]概念。1923年，文献[8]认为它是比方差分析更适合于相应数据的模型分析。1933年，文献[9]将其推广到随机变量，成为数据挖掘界熟知的一种无监督、线性学习方法。它关注事物的主要性质，将原始变量通过线性变换进行线性组合，从n维特征映射到k维上(k<n)，这k维数据是重新构造出来的正交特征，被称为主成分。PCA算法简单，具有无线性误差、无参数限制等优点[10-12]。但存储空间大，计算复杂度高，采用的线性映射方法也会影响最后的效果，同时协方差矩阵的大小与样本点的维数成正比，导致计算高维数据的特征向量困难。
针对PCA的局限性，如无明确准则来确定主成分，且存在着诸如高斯假设、线性假设及未考虑数据序列相关性等局限，学者给出了多种改进算法，如动态PCA、非线性PCA、多尺度PCA等。文献[13]探讨对分子数据的降维，为解决传统PCA易受噪声影响的问题，提出
了NFPCA(noi free PCA)，在PCs的计算步骤基础上增加一个惩罚项来控制噪声。文献[14]针对基因组单核苷酸多态性数据特征急剧增长，经典PCA处理非常耗时的问题，提出了基于随机算法的高性能PCA的实现方法flash PCA。文献[15]针对大型数据集不能存到随机存储器的问题，采用分块Lanczos方法的随机版本进行处理，迭代次数很少，结果几乎最优，参数l越大，计算复杂度越高，但l的选择没有确定的方法。文献[16]针对人脸识别中存在的图像特征维数高、样本小、耗时长及内存消耗大等问题，基于人脸识别特征和图像特性的考虑，采用分块处理，提出分块PCA。在表情和光照变化的时候，可以捕捉人脸局部特征，并将小样本问题大样本化，在识别性能和识别率上明显优于PCA。六级阅读满分多少
disappoint本文针对PCA算法内存消耗大、耗时长，数据特征维高时，处理时间不能满足应用需求的问题，提出基于信息熵的高维稀疏大数据降维算法(E-PCA)。该算法引入信息熵，首先进行特征筛选，降低特征数量，将大型稀疏矩阵稠密化后再做降维处理。
2 基于信息熵的E-PCA算法
2.1 特征值与特征向量
lycra在信息处理上[17]，针对对称矩阵A，可以求得正交特征向量，把A所代表的空间进行正交分解，使得A中的向量可表示为它在各个特征向量上的投影长度，这个投影长度即为对应的特征值。据此，可求出投影前特征值为k的那些分量，丢弃剩下分量，尽最大可能保存矩阵包含的信息，同时能够降低矩阵维度，即降维。在下文的算法中会用此思想来确定具体的k值。
2.2 信息熵
成人用英语怎么说对于信源要考虑所有可能发生情况的平均不确定性。如果信源发出的信号有n种取值，，对应的概率为，并且满足此时，信源的平均不确定性应为单个符号的不确定性−logpi 的统计平均值，称为信息熵，为：
式中，对数以2为底，单位为比特(bit)；以e为底，单位为奈特(Nat)；以10为底，单位为迪特(Det)。
从系统有序性上考虑[18]，一个系统越有序，信息熵就越低；反之，一个系统越混乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个度量。信息熵应用于特征时[
19-21]，在信息量表达上也可以这样解释，如果一个特征的信息熵越大，说明其包含的数据信息量越大，能提供更多的信息，在降维时，应该保留该特征；反之，信息熵越小，说明其包含的数据信息量越小，能提供的信息有限，在做特征提取或者降维时，该特征不列入备选项，也就是应该被剔除或者不保留的特征。以信息熵阈值δ来界定特征是被剔除或者保留，δ可由以下两种方案确定：1)根据特征对应用分析的重要性判断，适用于有用特征和无用特征信息熵值有明显的分界点；2)利用表达式计算选择的特征在原始数据中的比重：
图1所示为Arcene数据集(来自UCI机器学习库)前50个属性的信息熵值曲线图，如应用需要保留至少45个属性，δ不能大于0。calm是什么意思
2.3 E-PCA降维算法
文献[16]中的方法，可能由于分块不随机，原始数据分布不均匀等情况，导致整体数据的某些主成分在分块中相对占比少而被丢弃；而某些成分虽算不上主成分，但在分块中占比很高，却被算作主成分而被保留，导致最后的结果不够完美。基于以上局限性，本文从全局的角度去考虑主成分占比，提出一种基于信息熵的E-PCA算法，用于超高维稀疏数据的降维，处理流程如图2所示，其中δ代表信息熵阈值。screaming
图1 Arcene数据集前50个属性的信息熵值
图2 基于信息熵的降维处理流程
基于信息熵的PCA降维算法(E-PCA)原理和PCA一样，区别仅在于E-PCA在应用PCA算法对数据做降维以前做了一次特征筛选：设置信息熵阈值δ，过滤掉那些几乎无用的原始数据信息的属性(特征)，E-PCA算法的具体步骤如下所示。
输入：数据矩阵Un×m，其中m代表样本个数，n代表属性(特征)个数；信息熵阈值δ；贡献率 f。
