基于改進K-means的大數(shù)據(jù)清洗方法

林女貴， 吳元林

(1.國網(wǎng)福建省電力有限公司， 福建 福州 350001;2.國網(wǎng)信通億力科技有限責(zé)任公司， 福建 福州 350001)

0 引言

隨著智能化技術(shù)的發(fā)展，海量的網(wǎng)絡(luò)數(shù)據(jù)被采集到各個系統(tǒng)，有效地利用海量數(shù)據(jù)挖掘數(shù)據(jù)中存在的價值，最關(guān)鍵的一點是提高數(shù)據(jù)質(zhì)量[1-2]。目前的大數(shù)據(jù)中存在的低質(zhì)量數(shù)據(jù)主要包括冗余數(shù)據(jù)、缺失數(shù)據(jù)和異常數(shù)據(jù)[3]。一直以來的研究對于冗余數(shù)據(jù)和缺失數(shù)據(jù)的處理已經(jīng)比較完善，而對于大數(shù)據(jù)中異常數(shù)據(jù)的處理還處于初級階段[4]。為了提高數(shù)據(jù)質(zhì)量，達到數(shù)據(jù)清洗的目的。Hadoop平臺是有效處理大數(shù)據(jù)的軟件，利用其對數(shù)據(jù)進行清洗，可以得到高質(zhì)量的數(shù)據(jù)。

由于數(shù)據(jù)挖掘的效果受數(shù)據(jù)質(zhì)量影響較大，所以需要對大數(shù)據(jù)進行數(shù)據(jù)清洗以提高數(shù)據(jù)利用效率。目前數(shù)據(jù)的采集量越來越大，針對大數(shù)據(jù)清洗的研究也受到了人們的廣泛關(guān)注。文獻[5]對輸變電設(shè)備的異常數(shù)據(jù)進行了分類，采用一種基于時間序列分析的雙循環(huán)迭代檢驗法，對變壓器和線路的數(shù)據(jù)進行清洗，得到了較高質(zhì)量的數(shù)據(jù)。文獻[6]針對并行數(shù)據(jù)的清洗問題進行了研究，提出了基于任務(wù)合并的優(yōu)化技術(shù)，對冗余計算和同一文件進行合并，降低了系統(tǒng)的運行時間，提高了數(shù)據(jù)清洗的效率。文獻[7]采用條件合并方法把關(guān)聯(lián)數(shù)據(jù)放在一起，提出了一種自動清洗結(jié)構(gòu)，對數(shù)據(jù)進行檢測和修復(fù)，并對關(guān)聯(lián)數(shù)據(jù)的一致性和時效性進行了判斷，經(jīng)過實驗對比驗證了該方法的有效性。文獻[8]針對風(fēng)電機組采集的風(fēng)速功率數(shù)據(jù)，采用組內(nèi)方差清洗方法，對風(fēng)機的發(fā)電狀況進行判斷，該方法能夠準(zhǔn)確識別風(fēng)機功率曲線并檢測出異常工作狀態(tài)。文獻[9]分析了異常負荷數(shù)據(jù)的產(chǎn)生原因，采用基于密度的負荷數(shù)據(jù)流異常辨識方法和基于協(xié)同過濾推薦算法的負荷修復(fù)方法，將該方法在實際負荷數(shù)據(jù)上進行實驗，驗證了該方法能夠有效提高配電網(wǎng)數(shù)據(jù)質(zhì)量。文獻[10]采用棧式自編碼器方法，對輸變電設(shè)備正常及異常的數(shù)據(jù)進行學(xué)習(xí)，建立起缺失數(shù)據(jù)和設(shè)備異常的模型，實驗結(jié)果證明，該方法能夠有效過濾干擾數(shù)據(jù)。文獻[11]在采用大數(shù)據(jù)方法評估變壓器狀態(tài)的時候，針對數(shù)據(jù)中存在數(shù)據(jù)缺失和異常的問題，建立數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則模型，采用基于密度的聚類方法檢查數(shù)據(jù)的缺失值和異常點，采用小波神經(jīng)網(wǎng)絡(luò)對異常數(shù)據(jù)進行修復(fù)，提高清洗數(shù)據(jù)的質(zhì)量。

本文針對Hadoop平臺下的大數(shù)據(jù)進行異常數(shù)據(jù)清洗的研究，以保障數(shù)據(jù)清洗的有效性。采用基于損失函數(shù)的Logsf方法對高維數(shù)據(jù)進行降維處理，采用Canopy方法對K-means進行改進，并采用改進的K-means方法對異常數(shù)據(jù)進行清洗。

1 Hadoop平臺下數(shù)據(jù)清洗方法

在對數(shù)據(jù)分析之前，會對數(shù)據(jù)進行清洗，以查找數(shù)據(jù)中存在的“低質(zhì)”數(shù)據(jù)[12]。清洗過后的數(shù)據(jù)需要數(shù)據(jù)質(zhì)量評價，數(shù)據(jù)質(zhì)量的評價主要包含2個元素：定量元素和非電量元素。定量元素主要是從如下方面對數(shù)據(jù)清洗結(jié)果進行評價：清洗數(shù)據(jù)的完整性;清洗數(shù)據(jù)的一致性;數(shù)據(jù)的唯一性;數(shù)據(jù)的準(zhǔn)確性;數(shù)據(jù)的有效性;數(shù)據(jù)的時間性。非定量元素主要包括數(shù)據(jù)處理的目的，數(shù)據(jù)集的用途和數(shù)據(jù)集從采集到處理的過程描述。本文采用定量元素方法評價清洗過后的質(zhì)量，并采用Hadoop平臺，對處理后的數(shù)據(jù)的查全率和可擴展性進行分析。

數(shù)據(jù)清洗的過程如圖1所示。

圖1 數(shù)據(jù)清洗流程圖

原始數(shù)據(jù)是指數(shù)據(jù)倉庫中存儲的數(shù)據(jù)信息；數(shù)據(jù)預(yù)處理指的是對原始數(shù)據(jù)進行簡單的約束處理；特征選擇指的是提取數(shù)據(jù)特征，剔除冗余信息；數(shù)據(jù)清洗指的是根據(jù)實際應(yīng)用情況，清洗臟數(shù)據(jù)；清洗結(jié)果檢查指的是根據(jù)清洗標(biāo)準(zhǔn)檢驗數(shù)據(jù)質(zhì)量。

由于Hadoop在處理大數(shù)據(jù)上的優(yōu)越性，采用Hadoop的分布式數(shù)據(jù)清洗方法，可以有效提高大數(shù)據(jù)清洗的效率。采用Hadoop方法清洗數(shù)據(jù)的時候，將數(shù)據(jù)分為存儲層和清洗計算層。采用HDFS進行數(shù)據(jù)存儲，在HDFS上層采用Hive數(shù)據(jù)倉庫實現(xiàn)數(shù)據(jù)的轉(zhuǎn)存，然后將數(shù)據(jù)庫的數(shù)據(jù)按照指定格式進行處理，實現(xiàn)數(shù)據(jù)清洗前期的準(zhǔn)備工作。本文采用MapReduce方法實現(xiàn)異常數(shù)據(jù)的分布式清洗，提高數(shù)據(jù)清洗的效率和準(zhǔn)確性。Hadoop平臺的異常數(shù)據(jù)清洗流程如圖2所示。

圖2 分布式異常數(shù)據(jù)清洗流程

具體的分布式數(shù)據(jù)清洗流程如下所述。

(1) 數(shù)據(jù)源加載。采用Sqoop和Hive對采集的數(shù)據(jù)進行加載和轉(zhuǎn)存。

(2) 數(shù)據(jù)預(yù)處理。根據(jù)數(shù)據(jù)需求進行綜合分析，以確保數(shù)據(jù)分析時數(shù)據(jù)的可用性。

(3) 特征選擇。選擇出影響數(shù)據(jù)質(zhì)量的主要特征，剔除冗余特征，實現(xiàn)大數(shù)據(jù)的降維處理。

(4) 識別異常數(shù)據(jù)。采用改進的K-means算法，將距離相差越大異常性越強的數(shù)據(jù)，采用MapReduce方法實現(xiàn)并行化計算。

(5) 清洗結(jié)果檢驗。對清洗后的數(shù)據(jù)進行數(shù)據(jù)質(zhì)量檢查，確保數(shù)據(jù)質(zhì)量。

2 基于改進K-means的異常數(shù)據(jù)清洗方法

2.1 基于Logsf的特征選擇方法

Logsf可以描述為假設(shè)訓(xùn)練樣本集R={M,N}={mi,ni}。其中，mi為第i個訓(xùn)練樣本；ni為第i個樣本的標(biāo)記[13]。每個樣本包含d維矢量，mi={mi1,mi2,mid}∈Rd。樣本mi的損失函數(shù)定義為式(1)。

L(β,mi)=log(1+exp(-βTFi))

(1)

Logsf算法的評價函數(shù)可以表示為式(2)。

(2)

式中,K表示樣本特征數(shù)量；e(β)是所有特征樣本損失函數(shù)之和。如何確定最優(yōu)的β′求取最小的損失函數(shù)，是需要研究的問題，本文采用梯度下降方法求取最優(yōu)權(quán)重。

設(shè)步長為α，梯度下降法的迭代算式表示為式(3)。

(3)

將式(1)帶入式(3),則可得到式(4)。

(4)

簡化后可得到式(5)。

(5)

通過上述方法可以得到最優(yōu)權(quán)重，但是在Logsf中存在著最鄰近思想，確定特征樣本相似度的方法為式(6)。

(6)

2.2 基于改進K-means算法的數(shù)據(jù)清洗方法

數(shù)據(jù)中存在著與主體數(shù)據(jù)不相符的數(shù)據(jù)，被稱為異常數(shù)據(jù)。K-means算法的步驟[14-15]如下所述。

從訓(xùn)練樣本{x1,…,xm},xi∈Rn，隨機取k個中心點。

Step1：從{x1,…,xm}隨機取k個樣本，記作初始聚類中心μ1,μ2,…,μk∈Rn。

Step2：求取其他數(shù)據(jù)與該中心樣本的距離，數(shù)據(jù)樣本根據(jù)距離劃分類別,如式(7)。

(7)

Step3：對每個類j，求取平均值確定中心點,如式(8)。

(8)

式中，每個樣本含d個屬性，第j類共m個數(shù)據(jù)，其中樣本xi屬于第j類，屬于第j類的樣本xi的第D個特征求和，再求平均值，即為第D個特征的質(zhì)心。

Step4：若目標(biāo)函數(shù)收斂，終止程序；否則轉(zhuǎn)到Step2。

Canopy的思想：在數(shù)據(jù)集中隨機點A，計算其余樣本與A的距離，根據(jù)距離的大小劃分類別。例如，小于T1的作為一類，[T1,T2]之間的為另一類。

采用Canopy算法優(yōu)化K-means算法的過程如下。

(1) 原始數(shù)據(jù)存入數(shù)據(jù)集D中。

(2) 隨機確定中心點，放入canopy centerlist，將該數(shù)據(jù)從D里刪除。

(3) 計算其他數(shù)據(jù)與canopy centerlist的距離。Dist[i]

(4) 通過歸類后得到了k個canopy。

(5) 計算k個聚類中心點。

(6) 計算每個數(shù)據(jù)與中心點的距離。將數(shù)據(jù)歸類為Dist[i]最小的類。

(7) 將各類的平均值作為新的中心點。

(8) 再計算新中心點與canopy中心點的距離，按照(3)分類。

(9) 若達到收斂條件，停止循環(huán)；否則繼續(xù)(6)—(8)。

具體流程圖如圖3所示。

圖3 Canopy-K-means算法流程圖

為了有效地對大數(shù)據(jù)進行降維和數(shù)據(jù)清洗，采用MapReduce方法，分別進行降維和數(shù)據(jù)清洗。在數(shù)據(jù)降維的時候，先采用梯度下降法求取最優(yōu)權(quán)重值，采用Map函數(shù)根據(jù)權(quán)重大小將樣本按照〈key,value〉存儲。key為特征編號;value為數(shù)據(jù)編號。再采用Reduce函數(shù)將特征編號相同的樣本放在一起存儲到HDFS中。改進的K-means算法得到的異常數(shù)據(jù)，采用MapReduce方法處理也采用同樣的方法處理。

3 算例仿真

3.1 特征提取

為了驗證本文所提方法的有效性和可靠性，選取某企業(yè)的3種傳感器采集的信息進行仿真實驗。選擇其中10萬條數(shù)據(jù)(100MB)作為訓(xùn)練集，另外分別選擇40萬條數(shù)據(jù)(200MB)和80萬條數(shù)據(jù)(800MB)作為測試集。采用改進的Logsf和Logsf方法進行實驗對比。各對比結(jié)果如圖4-圖7所示。

圖4 準(zhǔn)確率對比曲線

圖5 訓(xùn)練集的加速比曲線

圖6 測試集1的加速比曲線

圖7 測試集2加速比曲線

3.2 數(shù)據(jù)清洗

選取經(jīng)過改進后的Logsf算法降維的數(shù)據(jù)，采用本文所提的改進K-means算法進行異常數(shù)據(jù)清洗。分別對其準(zhǔn)確率、運行時間和加速比進行分析。準(zhǔn)確率的對比結(jié)果如表1所示。

表1 兩種方法準(zhǔn)確性對比

加速對比曲線如圖8-圖10所示。

圖8 10萬條數(shù)據(jù)加速比

圖9 40萬條數(shù)據(jù)加速比

圖10 80萬條數(shù)據(jù)加速比

3.3 結(jié)果分析

從圖4可以看出，隨著樣本數(shù)量的增加，改進的Logsf比傳統(tǒng)的Logsf方法準(zhǔn)確性有了很大提升。雖然數(shù)據(jù)量較小的時候，改進的Logsf低于Logsf的準(zhǔn)確性，但是本文處理的是大數(shù)據(jù)，所以圖4驗證了改進后的算法更適用于大數(shù)據(jù)的特征提取。從圖5-圖7的對比曲線可以看出改進的Logsf的加速明顯高于Logsf。以上實驗說明了改進后的Logsf算法的有效性。

從表1可以看出，在對異常數(shù)據(jù)進行清洗的時候，傳統(tǒng)的K-means算法準(zhǔn)確率明顯低于改進的K-means算法，從圖8-圖10的加速對比曲線可以看出，在處理相同數(shù)量級的數(shù)據(jù)時，改進的K-means算法比K-means算法的加速比更快，驗證了本文所提方法的有效性。

4 總結(jié)

針對大數(shù)據(jù)中含有的異常數(shù)據(jù)清洗問題，本文提出了改進的Logsf方法，選擇特征，并進行數(shù)據(jù)降維處理，獲得約簡后的數(shù)據(jù)。采用Canopy方法對傳統(tǒng)的K-means算法進行改進。然后采用MapReduce方法實現(xiàn)算法并行化。實驗結(jié)果驗證了改進的Logsf方法比傳統(tǒng)的Logsf方法具有更高的特征提取準(zhǔn)確度，改進的K-means算法比傳統(tǒng)的K-means算法清洗數(shù)據(jù)后，具有更高的準(zhǔn)確度和更快的處理速度,驗證了本文所提方法的可靠性。