面向列的混合式數(shù)據(jù)篩選算法

鄭月鋒，李文倩

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

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

1 MRMCPSO算法描述

1.1 MRMC過濾算法

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

算法1 MRMC算法偽代碼

(1)輸入?yún)?shù)：數(shù)據(jù)集，最終特征集合：LasetF={}，變量i初值為0，dsF表示數(shù)據(jù)集，F(xiàn)i表示被選中的第i個特征；

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

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

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

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

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

(7)當(dāng)數(shù)據(jù)集dsF不為空時，進入循環(huán)；

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

(9)dsF= dsF-{Fi}；

(10)i=i+1；

(11)循環(huán)結(jié)束.

1.2 MRMCPSO算法

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

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

(1)

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

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

(2)

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

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

圖1 MRMCPSO算法流程圖

2 實驗結(jié)果與分析

2.1 實驗數(shù)據(jù)

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

表1 實驗用數(shù)據(jù)集信息

2.2 實驗結(jié)果

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

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

表2 5種算法在40個數(shù)據(jù)集上ACC平均值和LEN平均值

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

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

圖2 5種算法在40個數(shù)據(jù)集上篩選列的長度

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

3 結(jié)語

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