王 妍,李 俊,曾 辉,杨冰清,宋宝燕

(辽宁大学 信息学院,沈阳 110031)

1 引 言

近两年,美国,德国和中国相继提出了《先进制造合作伙伴》报告2.0、《工业4.0研发白皮书》、《中国制造2025》,这拉开了制造业向智能制造转型的序幕.与此同时,工业大数据这一新的概念也出现在人们的面前.随着智能化转型战略的相继实施,工业大数据日益成为全球制造业挖掘价值,推动变革的主要动力.工业大数据分析是智能制造的基础,也是支撑未来制造智能化的方向[1].

工业大数据应用的最大价值就在于对企业生产制造和业务管理流程智能优化.它利用工业生产过程中收集的各种变量参数,对生产过程进行严格监控,并通过对生产数据的分析,改进生产工艺流程,优化生产过程,降低能源消耗.但是在工业生产过程中,生产控制参数众多,并且参数之间相互影响,紧密关联,导致工业大数据维度很高,且数据之间呈现非线性关系.而由于“维灾”的影响,数据挖掘算法很难对工业大数据进行充分挖掘.为解决该问题,许多学者通过降维算法对原始高维数据进行降维,降低数据挖掘的难度.但是在面对工业大数据时,传统的线性降维算法难以在降低维度的同时保留数据蕴含的大部分信息.而且由于生产线时刻在高速运转,数据采集频率很高,传统算法无法满足特征提取的实时性要求.因此,为了充分地挖掘隐藏在工业大数据中的信息,提高数据挖掘的效率和性能,就必须解决“维灾”的影响,针对工业大数据的特点进行快速降维.

针对上述问题,本文提出一种基于互信息的实时特征提取算法(Feature Extraction Algorithm Based On Mutual Information,MIFE);该算法以互信息作为相关系数进行主成分分析,解决了传统主成分分析算法中相关系数无法衡量数据间非线性关系的缺点;采用自适应的滑动窗口动态更新数据,将历史数据与新增窗口数据结合完成对整体数据的特征提取,极大地提高算算法运行效率.实验结果表明,该方法可以有效对工业大数据进行实时的特征提取,并以多种分类器验证了算法的精确性.

2 相关工作

特征提取是一种常用的降维方法,它将原高维空间按照某种变换规则,变化到维数较低的空间中,从而降低原始数据的维数.特征提取[2]与特征选择[3]是降维方法的两大类[4].与特征选择侧重点在于选取出蕴含信息量大的属性不同,特征提取所得到的特征是由原始特征集中的多种特征组合而得,因此往往不再属于原特征集.特征选择可以看作是特征提取的一种特殊形式.

工业生产中大部分数据并不是全局线性的,它们往往服从一定的形式的非线性分布规律,而传统的一些线性降维算法如主成分分析(Principal Components Analysis,PCA)[5],Fisher判别分析[6]对于非线性数据的降维效果很差.基于研究非线性分布数据的需要,众多研究者提出了许多非线性特征提取算法.目前针对非线性数据的降维算法主要分为两类:一种是在线性降维算法的基础上,通过核函数对其进行扩展;另一种是采用流形学习的方法,将高维数据看作是低维流形在高维空间的嵌入,通过提取低维流形实现数据降维.

文献[7]提出的基于核的主成分分析方法(Kernel Principal Component Analysis,KPCA),是目前国际上比较流行的一种特征提取方法,它是利用核变换将具有非线性结构的数据投影到核空间,使核空间线性可分.它是对主成分分析法进行的一种非线性扩展,但是具体核函数的选取和参数的设定是一个难点,多数情况下需要经验指导.

在文献[8]中,Roweis 等人提出了局部线性嵌入算法(Local Linear Embedding,LLE),该算法通过将非线性数据转换成局部线性的数据,同时保持数据间距离对应关系相等,使其拓扑关系不发生变化.该算法泛化能力较弱,缺乏处理新增数据的能力.

文献[9]提出了一种局部切空间排列算法(Local Tangent Space Alignment,LTSA),其特点是构造出数据样本的局部切空间,并将这样的切空间数据用对应的邻域表来表示,进而将这些切空间数据嵌入到这样的邻域表,进而完成了高维数据的降维,其不足之处在于不能处理大数据高曲率样本,泛化能力差.

文献[10]提出了等距映射算法(Isometric Mapping,ISOMAP),该算法首先需要计算出数据间的最短距离,用临近路径二维表表示,然后将最短距离转化为测地线距离,进而将高维数据降为低维数据,但该算法对数据结构有特殊要求.文献[11,12]提出了拉普拉斯特征映射(Laplacian Eigenmap,LE),该算法用图来表示数据间的关系,通过构造数据间的邻接表来表示数据,数据表示图的一个顶点,同时邻近表中重复的数据用图的相似度来表示,其缺点是对噪声敏感,健壮性较差.

部分学者采用信息论的知识对非线性数据进行降维.在文献[13]中,范雪莉等人提出了一种基于互信息的主成分分析特征选择算法(MIPCA).该算法利用互信息对数据类型不敏感的特点将其作为衡量特征间相关程度的度量,以互信息矩阵的特征值作为评价准则确定主成分的个数.实验证明,该算法能对非线性数据进行特征提取,但是当其处理增量数据时,其运行效率会大大降低;文献[14]中提出了一种基于互信息的无监督特征选择算法,该算法同时适用于数值型和非数值型特征,实验表明该算法可以达到传统算法的性能甚至更好,但是处理速度有所欠缺.

上述算法均有不足之处,基于核函数的方法难以选择合适的核方法,而基于流形学习的方法泛化能力差,基于互信息的方法运行效率低下,难以满足工业大数据的需求.针对上述问题,本文提出的算法在保持高效的同时,对数据进行降维,保留了原始数据的大部分信息.

3 相关定义

3.1 信息熵

信息熵是C.E.Shannon在1948年提出[15]的,被用来衡量一个随机信号中所含信息量的大小,从而去掉冗余的信息,减少算法在处理过程中的复杂度.信息熵可以很好的刻画一个系统内部的信息量,因此在多个领域得到了应用.

在信息论中,信息量表示为:

I=-logp

(1)

在式(1)中,p代表一个消息出现的概率,p越大,其所含的信息量越小.但是信息量只是针对单个的信息进行计算,无法衡量整个系统的信息量,所以引入了信息熵,其公式表达为:

(2)

式(2)中,H(x)表示一个信息源在整体特征上的一个信息量.H(x)越大,表示其内部元素越混乱,所蕴含的信息越多;与之相反,H(x)越小,其所蕴含的信息也就越少.

3.2 互信息

互信息是一种衡量两个随机变量之间相互依赖强弱程度的准则,由信息论中的熵延伸而来.两个随机变量之间的互信息越大,则两者之间的相关性越强.

给定两个随机变量X和Y,若其边缘分布概率和联合分布概率分别为p(x),p(y)和p(x,y)则其互信息可表示为:

(3)

根据文献[16]可知:

I(X;Y)=H(X)+H(Y)-H(X,Y)

(4)

I(X;Y)=I(Y;X)

(5)

(6)

互信息属于信息度量的范畴,主要利用信息熵等量化特征相对于分类类别的不确定性程度来判定其包含的类别信息.它是一种无参的、非线性的标准,因此其不仅能度量变量之间的线性关系,还能评估变量的非线性关系.因此,采用互信息作为相关系数可以充分反映数据特征之间的非线性关系.

3.3 滑动窗口

滑动窗口技术是处理数据流的一种重要方法,因其所需内存较小,并且处理速度很快而受到了广泛的使用.滑动窗口会随数据的流入不断向前滑动,更适应于处理最新时间段内的数据.滑动窗口的更新方式有两种:连续更新和周期更新.连续更新适合低速且均匀到达的数据流,当数据流的流速在不断变化的情况下,该方式对窗口的更新效果很差.周期更新的滑动窗口首先定义一个缓冲区,最近到达的数据先进入缓冲区,当到达更新周期时,将缓冲区内的数据集送入滑动窗口实现数据的更新操作.

滑动窗口的思想是对计算对象进行调整,计算对象不再是当前的整个数据集,而是数据集的子集,因此可以对最新的数据进行处理,由于其存储的是数据集的子集,因此所需的内存大大减小.

3.4 多级联动缓冲区机制

在工业数据采集过程中有可能出现瞬时数据流量特别大的情况.例如,在矿井监测中,如出现瓦斯泄漏等情况,有毒气体监测器会在短时间内频繁的上传数据.传统的基于周期更新的滑动窗口在面对瞬时数据量过大时,更新效果很差,甚至在缓冲区内的数据会溢出.因此,本文采用多级联动缓冲区机制.

设置每个缓冲区大小为B(MB),初始缓冲区编号为1,当前数据传输速率为v(kb/s),当瞬时速率大于一定阈值θ时,即v>θ,并且持续一定时间后t后,就动态的新增缓冲区,并为该缓冲区编号,其值为前一缓冲区编号加1.缓冲区之间以指针链接,相邻两级缓冲区首尾相连.为防止缓冲区个数无限制增加,导致内存溢出,将缓冲区个数上限设置为8.当窗口内的数据处理完毕后,再从编号最小的缓冲区内取出数据,当缓冲区中没有数据时回收该缓冲区.

4 基于互信息的实时特征提取策略

4.1 互信息的不足及改进

信息熵最初用来衡量通信领域中信源所有可能发生情况的平均不确定性,当需要计算信息熵和互信息时,只需统计每个信号出现的频率即可估算出整个信源所拥有的信息.但是直接将该方法应用于工业大数据却有些缺陷,其不足之处在于当样本分布由均匀向分布不均变化时,由频率计算得到的熵值可能不会发生变化.在该种情况下,信息熵并不能切实反映一个随机变量内部蕴含的信息大小.直接将互信息作为相关系数,也无法准确地衡量两个变量的相关性.

针对传统互信息的不足与缺点,本文从特征取值本身出发,采用个体占整体比重求互信息可以有效地消除样本分布不均带来的影响,准确地衡量两变量之间的相关性.

假设特征空间Rm×n上的样本数据集X,每一个数据Xi由n维特征向量组成,即(xi1,xi2,xi3,…xin).

(7)

在式(7)中xij表示第i个样本的第j个特征的值,p(xi)表示第第i个样本在第j个特征上的值占第j个特征整体值的比重.

采用改进的熵值计算方法可以在样本分布不均时最大程度地反映出整个系统蕴含的信息,较之传统计算方式,其适应范围更广,可以更加准确地衡量随机变量之间的相关程度.

4.2 基于改进互信息的主成分分析

传统的PCA算法采用协方差作为相关系数标准,无法衡量非线性数据之间的相关性,本文引入改进互信息作为度量标准,有效解决了这个问题.基于改进互信息的PCA过程如下.

根据式(2)与式(7)计算每个特征的信息熵H(xj),然后再根据式(4)计算每个特征间的互信息,组成互信息矩阵ΣIxy.

(8)

在式(8)中,对角线元素表示变量的自信息,即变量的信息熵,非对角线元素表示两个变量的之间的互信息.而且,无论是信息熵还是互信息皆为实数,当两个变量不相关时,互信息为0,否者为正数,因此ΣΙxy为非负实数矩阵,并且由公式(5)可知:

I(X;Y)=I(Y;X)

因此可以判定ΣΙxy是非负实对称矩阵,其特征值为实数,特征值对应的特征向量两两正交,并且矩阵可分解为如下形式:

ΣIxy=B′ΛB

(9)

其中,Λ为ΣIxy的特征值(μ1,μ2,…μn)组成的对角阵,特征值从大到小排列.B是各个特征值对应的特征向量(β1,β2,…βn)组成的矩阵.通过贡献率来判断主成分的维数.主成分的贡献率σk为单一主成分占总体主成分信息量的比重.

(10)

其中μk表示第k大的特征值.累计贡献率δk为前k个主成分的贡献率之和.

(11)

选择贡献率之和在85%-95%的前k个特征值对应的特征向量(β1,β2,…βl) 作为主成分决策矩阵Bl

原始矩阵降维后为:

Z=BlX

(12)

改进互信息可以衡量非线性数据之间的相关性,并且在样本分布不均时也有较好的效果,但是其处理速度却有一定缺陷,无法处理源源不断的增量数据.针对此问题,本文提出了一种增量数据的实时特征提取算法.

4.3 增量数据的实时特征提取

在工业生产过程中,由于生产线时刻运转,数据采集设备源源不断的采集新的数据,传统的特征提取算法无法对增量数据进行快速处理,如果只是单纯地处理新增数据,不考虑历史数据对其影响,算法就无法从全局的角度进行特征提取,所提取的数据蕴含的信息也会大大降低.针对此问题,本文将历史数据和新增数据相结合,采用自适应滑动窗口动态地对增量数据进行处理.

采用文献[17]的思想,考虑原始窗口数据与增量窗口数据可分别用矩阵表示为X1=[x1,x2,…，xm],X2=[xm+1,…，xm+r],所有数据可表示为X=[X1,X2].所有样本的互信息矩阵为S,原始窗口数据的互信息矩阵为S1,新增窗口数据的互信息矩阵是S2,由互信息定义可知:

(13)

利用S1的特征分解将S1对角化为单位阵,即

(14)

然后将S2投影到由H1张成的空间,即可令

(15)

将式(13)和式(14)相加可以得到:

(16)

(17)

将式(17)带入式(16)可得:

(18)

由式(13)和(18)即可求得S即所有样本的特征分解.

由式(14)可知:

(19)

式(19)中,Bi∈Rn×k是原始数据的主成分决策矩阵,Λ1∈Rm×k是选取的前k个特征值组成的矩阵;

根据式(17)求出S2的特征值Λ2=[μ1,μ2,…,μn]和特征向量P2=[β1,β2,…,βn].和对应的特征向量,根据这k个特征值和特征向量可以求出S的特征值:

(20)

其中,m和r分别是历史数据和新增数据的样本数量.

特征向量:

P=H1βi

(21)

并组成主成分决策阵.将数据映射到主成分决策阵上即实现了降维,后续的窗口重复此过程.

5 基于互信息的实时特征提取算法

针对传统特征提取算法不适用于非线性数据,且无法满足工业大数据实时性等问题,本文提出了一种基于互信息的实时特征提取算法,其算法伪代码如算法1所示,算法2是求互信息矩阵并进行特征值分解.算法所示如下:

算法1.MIFE算法

输入:原始数据集

输出:降维后的数据集

1.将原始数据集按一定速率输入缓冲区buffer,当速率超过一定值时,动态增加缓冲区.

2. 滑动窗口从编号最小的缓冲区中读取数据;

3. int id=1;/*缓冲区编号初始为1*/

4. While(buffer[id]!=null)do

5. Read Matrixi;

6. if(Matrixi.Id==1)then

7. MIandEigDesposition(Matrixi);

8. unitedMatrix=UnitedMatrix(Matrixi);

9. Output Matrixi* eigVecMatrix

10. else

11. compute MIMatrix;

12. projection MIMatrix on unitedMatrix

13. proMatrix=PorjectMatrix(MIMatrix);

14. MIandEigDesposition(proMatrix);

15. Output MIMatrix*eigVecMatrix

16.end if

17.id=id+1;

18.end while

其中Matrix为窗口内的数据矩阵,用二维数组实现,UnitedMatrix()函数用来求单位化矩阵,而ProjectMatrix()函数用来求投影后的矩阵.

MIFE算法通过逐个扫描每个窗口,先判断当前窗口是否为第一个窗口,如果是,则求出当前窗口的互信息矩阵,然后进行特征分解,选出主成分决策矩阵,然后将原始矩阵映射到决策矩阵上,实现降维;否则,求出本窗口的互信息矩阵,然后将其投影在上个窗口的单位化矩阵上,然后根据式(15)和式(16)求出特征值和特征向量,并组成主成分决策阵,实现降维.

算法2.MIandEigDeposition(Matrix)

输入:参数矩阵

输出:互信息矩阵的特征值矩阵

1.TransMatrix=Matrix.Transpose();

2.j=1;k=1;

3. For(j to n)do

4. For(k to n)do

5. MIMtatrix[j][k]=MI(TransMatrix[j],

6. TransMatrix[k]);

7. end for

8. end for

9.Decomposition the MIMatrix;

10.Sort(eigValue);

11.Output eigValueMatrix,eigVecMatrix;

令Matrix为参数矩阵,用二维数组实现,MI()函数用来求取两个数组间的互信息,transpose()函数用来对矩阵进行转置,Sort()用来对数组进行排序.

MIFE算法的主要计算量集中在求取互信息矩阵和对矩阵进行特征分解;在计算互信息矩阵时,其时间复杂度为O(md2),特征分解的时间复杂度为O(d3),其整体复杂度为O(md2+d3),其中m为窗口的大小,d为数据维度,当数据集大小不断增加时,其时间是线性增加的,可以满足大数据量的处理.

6 实验结果与分析

实验环境是Intel奔腾3.0GHz的CPU,4GB内存,操作系统是Windows 7,本实验采用Python编写程序.经多次实验,当窗口宽度为500,算法的性能和效率能达到最佳.实验数据采用Iris,Energy Efficiency这2个来自UCI数据集中的公共数据集,某炼钢生产中采集到的真实数据集Iron和某炼油过程采集的数据Oil,进行实验分析对比.表1是对数据集的描述.

表1 实验中使用的数据集
Table 1 Data set used in the experiment

数据集名称实例数属性数类别数线性Iris15043是Energy Efficiency76882否Oil948558710否Iron114210458否

Iris鸢尾花数据集是数据挖掘中常用的数据集,它的每一条数据包含4个特征:花瓣长度、花瓣宽度、花萼长度和花萼宽度,分为setosa,versicolor和virginica 3类,第一类和其他两类线性可分,后两类无法线性可分;Energy Efficiency数据集是关于建筑冷热负荷的数据集,其内部数据之间呈现出非线性关系;Iron数据集是源自炼钢过程中采集的真实数据,内部各特征之间呈现复杂非线性关系,Oil数据集是炼油过程中采集的部分数据,其维度高,并且样本分布不均,内部呈现复杂非线性状态.

整个实验分为三大部分,一是测试窗口大小对算法效率的影响,二是测试3种算法在不同数据集上的运行时间,三是测试3种算法在线性和非线性数据集上的分类精度.

6.1 窗口大小

在该部分实验中,采用Iron数据集进行实验,在不同窗口大小下测试对本文算法效率的影响,每次实验重复十次,取其平均值作为实验结果的估计值,实验结果图1所示.

图1 窗口大小对算法运行时间的影响Fig.1 Effect of window size on the running time of the algorithm

由图1可以看出,当窗口逐渐增大时,算法运行时间整体呈下降趋势,当大于500时,运行时间又逐渐增大.这是因为当窗口太小时,会频繁从缓冲区取数据,会占用许多时间.而当窗口过大时,特征分解的时间会大大增加,因此当窗口大小处于一定大小时,算法效率达到最佳.

6.2 运行时间

在对算法运行时间的测试中,在各种数据集分别进行实验,记录PCA,MIPCA和MIFE算法的消耗时间,每种算法分别重复10次,然后取平均值作为各算法的处理时间,实验结果如表2所示.

从表2可以看出,PCA和MIPCA这两种算法在各个数据集上的处理时间不相上下,这是因为PCA和MIPCA算法的主要不同在于采用不同的评价准则,而其他的处理过程并无太大不同,因此处理时间差别不大,而MIFE算法随着数据量数据维度的增大,明显地比另外两种算法的处理时间少.由此可见,MIFE算法不仅在公开数据集上有较好的效率,而且在真实的工业数据集上也有很好的性能,可以满足工业大数据实时降维的需求.

表2 三种算法在不同数据集上的运行时间
Table 2 Running time of three algorithms on different data sets

数据集PCAMIPCAMIFE运行时间(ms)运行时间(ms)运行时间(ms)Iris75.3172.3468.45Energy Efficiency125.63122.7097.54Oil1278.781225.36316.79Iron1453.201438.73475.87

6.3 分类准确率

由于PCA、MIPCA和MIFE都是无监督学习算法,无法直接测试算法的准确性,因此用朴素贝叶斯分类器(NBC)、最近邻分类器(KNN)、决策树C4.5和支持向量机SVM这四种分类器对三种算法降维后的数据进行分类测验,本实验采用10次交叉验证获得算法的平均分类准确率,即将降维后的数据分成10份,轮流将其中九份作为训练数据生产分类模型,剩下的一份作为测试数据集进行测试,然后将10次分类性能的平均值作为最终的结果.分别用四种分类器进行实验,其结果如表3所示.

从表3中可以看出,在Iris和Wine Quality这两个线性数据集上,三种算法在每种分类器上的分类准确率都在85%左右,MIFE算法的准确率比其他两种要高,分析可知MIFE算法较大程度上保留了原始数据的内在信息,总体分类准确性也优于传统算法,在线性数据集上同样表现良好.而在非线性数据集Energy Efficiency上,MIFE和MIPCA算法的准确率较PCA算法提升了15%左右,结果表明PCA算法对非线性数据降维效果不是很好,会丢失大部分信息.而MIFE和MIPCA算法针对非线性数据能够有效地对其降维,并保留原始数据的大部分信息.另外,在真实工业数据集Iron和Oil中,MIFE算法比MIPCA算法的准确率也有了较大提升,主要是由于MIPCA算法对于样本分布均匀的数据有较好的降维效果,而当样本分布不均时,其降维效果会受到较大影响,而MIFE算法弥补了这一缺点.无论数据分布是否均匀,MIFE算法均能对其进行有效地降维,并保留原始数据大部分信息.

表3 三种算法在四种分类器上的准确率
Table 3 Accuracy of the three algorithms on four classifiers

数据集NBCKNNC4.5SVM准确率(%)准确率(%)准确率(%)准确率(%)PCAMIPCAMIFEPCAMIPCAMIFEPCAMIPCAMIFEPCAMIPCAMIFEIris85.5385.8286.7483.4784.3684.4481.3682.1484.2988.7490.2792.27Energy Efficiency72.1583.4585.5171.3782.8584.8669.7179.8482.5873.6488.9289.21Oil63.7575.9287.4862.5273.7484.2664.8372.5983.8464.5879.2591.44Iron67.4488.4792.5165.7386.5393.4665.2879.8187.2370.5191.5894.52

MIFE算法和MIPCA均采用互信息作为度量标准,但是MIPCA算法是一种批处理算法,当数据集新增数据时,其处理时间会大大增加,并且当样本分布不均时,其降维效果会受到很大的影响.本文提出MIFE算法通过滑动窗口对MIPCA进行改进,并通过对互信息进行改进使其能处理非均匀分布数据.通过以上两种实验表明,无论是在线性还是非线性数据集上,MIFE的运行时间都大大缩短,满足了增量数据实时处理的需求,同时还保证了优于MIPCA算法的准确率.

7 总 结

本文针对传统特征提取算法无法处理工业大数据的数据多样化,无法实时处理等问题,提出了一种基于互信息的实时特征提取算法(MIFE),采用互信息作为评价准则来选取主成分,克服了传统算法难以衡量特征之间非线性关系的难点;并通过引入滑动窗口大大减少了算法运行时间,在保留了大部分信息的同时,完成了工业大数据的降维.