一種基于互信息的實時特征提取算法

王 妍,李 俊,曾 輝,楊冰清,宋寶燕

(遼寧大學 信息學院,沈陽 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),采用互信息作為評價準則來選取主成分,克服了傳統算法難以衡量特征之間非線性關系的難點;并通過引入滑動窗口大大減少了算法運行時間,在保留了大部分信息的同時,完成了工業大數據的降維.