面向列的混合式數據篩選算法

鄭月鋒，李文倩

(吉林師范大學 數學與計算機學院，吉林 四平 136000)

采集來的數據存在冗余性[1-2]、不便于進行數據分析和對數據做進一步處理操作，因此需要對采集來的數據進行去重和去冗余等數據清洗操作[3].常用的數據清洗方法有眾包方法[4]和ETL方法[5]等，這些方法主要是針對數據中的記錄或者屬性來清洗.本文提出的MRMCPSO算法是在不改變行數據的情況下，對列數據進行篩選，進而達到消除冗余數據的目的.由于沒有對行數據進行篩選，因此，本算法適合數據記錄不多，而適合屬性數據眾多的數據集.

1 MRMCPSO算法描述

1.1 MRMC過濾算法

本文提出的MRMCPSO算法是把過濾算法和包裹算法混合在一起，進而發揮兩種算法的優勢.在過濾算法中用肯德爾等級相關系數(Kendall Rank)[6]來衡量標簽和特征之間的相關性，用歐式距離(Correlation Distance)[7]來衡量特征之間的冗余性.采用最大相關最大冗余算法(MRMR)[8]中相關性和冗余性等比率結合的策略，把兩者結合起來形成最大秩系數最小距離(MRMC)算法.MRMC算法的偽代碼見算法1.

算法1 MRMC算法偽代碼

(1)輸入參數：數據集，最終特征集合：LasetF={}，變量i初值為0，dsF表示數據集，Fi表示被選中的第i個特征；

(2)輸出：特征的排序；

(3)根據特征與標簽之間的最大秩系數，從數據集dsF中選出一個特征存放在LasetF中(LasetF={Fi}i=1)；

(4)數據集中減掉已經被選中的特征，dsF=dsF-{F1}；

(5)根據特征與標簽之間的最大秩系數和特征之間的最小距離，從數據集dsF中挑選出第二個特征(Fi，i=2)放在LasetF中(LasetF={F1，F2})；

(6)數據集中減掉已經被選中的特征，dsF=dsF-{F2}；

(7)當數據集dsF不為空時，進入循環；

(8)根據特征與標簽之間的最大秩系數和特征與特征集之間的最小距離，從數據集dsF中挑選出第i(i>2)個特征(Fi)放在LasetF中(LasetF={Fk，k=1，2，…，i})；

(9)dsF= dsF-{Fi}；

(10)i=i+1；

(11)循環結束.

1.2 MRMCPSO算法

粒子群算法[9-12](PSO)是群智能優化算法中最典型的算法.它能夠通過群體智能的特點在搜索空間中找到滿足條件的最優解.通過模擬小球落地時的彈跳軌跡[13-15]，把MRMC算法和PSO算法結合起來，形成MRMCPSO算法.模擬小球落地后彈起軌跡的公式為

y=|「6cosx+8sinx+5rand()?|.

(1)

其中：y表示彈起的離地距離，x表示時間，rand表示隨機數，cos和sin分別表示余弦函數和正弦函數，“||”表示取絕對值，“「?”表示向上取整.x的范圍是[1，100]，y的值為1～15之間的正整數.

在MRMCPSO算法中，MRMC算法只執行1次，PSO算法執行的次數與迭代次數相同.在PSO算法中，種群的初始化采用隨機化方法，數據集由MRMC算法執行后的前K個列組成，K的值由公式(2)確定：

(2)

其中：符號“?」”表示向下取整，Fnum表示數據集中列的數量，Rrownum表示數據集中行的數量，rand()是隨機數在(0，1)的小數，randnumber是10倍的隨機數并且取整，是1～10之間的正整數.MRMCPSO算法流程圖見圖1.

流程圖中涉及一些參數，現解釋如下.t表示迭代的次數，gbesttimes表示獲得最大值的次數，best表示算法每次迭代獲得的最優值，bestnest表示取得best值時挑選的列，i是Nochange數組的下標表示次數，Nochange數組存放公式(1)計算獲得的前10個數據，gbest表示算法最終獲得最優值，gbestnest表示取得gbest值時挑選的列.

圖1 MRMCPSO算法流程圖

2 實驗結果與分析

2.1 實驗數據

本實驗選擇西安交通大學雷亞國[16]提供的軸承數據集并對下載后的數據集進行了處理.選擇前2種工況下的所有原始數據集(10個)，每個原始數據集根據行和列分成2個初始數據集(總計20個).每個初始數據集以數據量(行的數量)為基礎，前取10%為合格數據并添加標簽“1”，后取5%為損壞數據并添加標簽“0”.初始數據集提取15%的數據量后形成的數據集作為實驗使用的數據集.為擴大數據范圍，對初始數據集獲取的數量翻倍，10%改為20%，5%改為10%，標簽添加方式不變，又形成20個數據集.實驗用的40個數據集的信息見表1.

表1 實驗用數據集信息

2.2 實驗結果

分別用MRMR+PSO算法(最大相關最小相冗粒子群優化算法)、MRMR+GA算法(最大相關最小相冗遺傳優化算法)、MRMR+BBA算法(最大相關最小相冗二進制蝙蝠優化算法)、MRMR+ GWO算法(最大相關最小相冗灰狼優化算法)與本文提出來的MRMCPSO算法進行比較.實驗參數設置與文獻[17]基本相同.

5種算法在每個數據集上運行10次.選擇每個算法在每個數據集上的平均分類準確率和平均特征子集長度，形成表2.

表2 5種算法在40個數據集上ACC平均值和LEN平均值

從表2中可以看出，5種算法對數據集中的列篩選出100列以內.但是，與其他4種算法相比，MRMCPSO算法的分類準確率在38個數據集上是最高的.在40個數據集中，有35個數據集的分類準確率達到了100%，有3個數據集的準確率達到了90%以上，只有2個數據集的分類準確率達到了65%.因此，與其他算法相比，所提出的算法能夠獲得較高的分類準確率，為進一步篩選數據列奠定基礎.

圖2顯示了5種算法在40個數據集上篩選出來的列的長度.可以看出綠顏色曲線基本上在其他顏色曲線的下面，這說明MRMCPSO算法篩選出列的數量是最少的.而且從表2中可以看出，MRMCPSO算法獲得列的數量是原數據集的列數量的6‰～12‰之間.從數值上看，MRMCPSO算法篩選出列的數量有28個數據集是一位數，其他4種沒有篩選出列的長度為一位數的數據集.在綠色曲線上有3個點即不在最下面，也不在最上面，其對應的數據集編號分別是30、31、40.這3個點表明MRMRPSO算法篩選出列的數量不是最多的.從整體上看，與其他算法相比，所提出的算法在能夠獲得較高分類準確率的情況下，篩選出了長度較短的列.

圖2 5種算法在40個數據集上篩選列的長度

MRMRPSO算法與其他4種算法相比，從結構上采用了小球彈跳軌跡的思想，把MRMC算法和PSO算法混合起來，實現了對MRMC算法的多次調用，達到了突破局部最優的效果.MRMRPSO算法最終獲得分類準確率較高，篩選出了長度較短的列，為數據的進一步處理奠定了基礎.

3 結語

為消除采集數據中存在冗余數據，本文提出了MRMC算法，通過引入小球彈跳軌跡的思想，把MRMC算法和PSO算法混合起來，形成了MRMCPSO算法.通過在40個數據集上的實驗結果表明，與其他4種算法相比，MRMCPSO算法在獲得較高準確率的情況下，能夠在實驗數據集上篩選出長度較短的列，列的長度達到原來的6‰～12‰.