張鏑, 吳宇強

(1.長春醫(yī)學高等?？茖W校,思想政治理論教研部(公共學科), 吉林, 長春 130031;2.哈爾濱工業(yè)大學, 計算學部, 黑龍江, 哈爾濱 150000)

0 引言

隨著互聯(lián)網(wǎng)技術的發(fā)展,數(shù)據(jù)量呈現(xiàn)井噴式增長[1-2],面對龐大的數(shù)據(jù),如何快速、準確而全面地從中挖掘出有價值的信息,已經(jīng)成為各個領域和行業(yè)共同面臨的一大難題[3-4]。MapReduce并行計算框架是一種非常高效和熱門的計算工具,數(shù)據(jù)分區(qū)是其中一個重要環(huán)節(jié)。由于數(shù)據(jù)類型復雜、數(shù)據(jù)量大,數(shù)據(jù)分區(qū)規(guī)律通常難以獲取,從而對價值信息的精準挖掘造成了困擾。因此,數(shù)據(jù)分區(qū)成為MapReduce框架順利運行的一個難點,傳統(tǒng)的數(shù)據(jù)分區(qū)方法難以達到均衡。

為此,國內(nèi)外相關專家進行了長期的探索和研究,提出了許多分區(qū)算法。文獻[5]基于數(shù)據(jù)分區(qū)研究高維數(shù)據(jù)均衡分流問題,主要依靠數(shù)據(jù)分布特征分析、分區(qū)維度計算以及邊界計算實現(xiàn),為后續(xù)研究提供了一種新的數(shù)據(jù)分區(qū)思路。文獻[6]提出了一種基于自動分區(qū)的數(shù)據(jù)計算框架,通過元數(shù)據(jù)處理完成自動分區(qū)算法設計,該算法在特定領域中計算速率得到了很大提升。文獻[7]提出了一種基于數(shù)據(jù)分區(qū)的不平衡大數(shù)據(jù)混合抽樣方法,將所有數(shù)據(jù)樣本劃分到不同的數(shù)據(jù)區(qū)域,對不同區(qū)域的數(shù)據(jù)樣本進行噪聲濾除等處理,然后作為過采樣種子生成合成樣本,該文數(shù)據(jù)分區(qū)及處理為抽樣提供了有效的基礎。文獻[8]提出了一種新的數(shù)據(jù)分區(qū)方法來提高現(xiàn)代高性能計算系統(tǒng)中異構并行應用程序的性能。文獻[9]方法基于數(shù)據(jù)集的有效分區(qū)收集相關記錄數(shù)據(jù),通過數(shù)據(jù)分區(qū)過程的向低維特征空間移動,獲取了穩(wěn)健的分析結果,但分區(qū)準確率不高。

針對上述數(shù)據(jù)均衡分區(qū)算法現(xiàn)狀,本文在機器學習的基礎上提出迭代式數(shù)據(jù)均衡分區(qū)算法,并通過實驗驗證了所提算法性能。本文主要貢獻點如下:①采用中心數(shù)據(jù)倉庫技術對異構數(shù)據(jù)進行集成,以此提高分區(qū)速度,提升數(shù)據(jù)分區(qū)效率,并為數(shù)據(jù)特征提取奠定基礎;②引入機器學習,通過決策樹算法構建分類器模型,辨別數(shù)據(jù)屬性與區(qū)域之間的關系,提高數(shù)據(jù)分區(qū)效果;③通過實驗分析驗證本文算法性能,結果表明,與傳統(tǒng)方法相比,所提算法有了極大的提高。

1 基于機器學習的迭代式數(shù)據(jù)均衡分區(qū)算法

數(shù)據(jù)均衡分區(qū)能夠幫助用戶快速完成數(shù)據(jù)挖掘,為此提出基于機器學習的迭代式數(shù)據(jù)均衡分區(qū)算法。迭代式數(shù)據(jù)均衡分區(qū)總體框架如圖1所示。

圖1 基于機器學習的迭代式數(shù)據(jù)均衡分區(qū)總體框架

1.1 數(shù)據(jù)集成與處理

考慮到數(shù)據(jù)來源和格式的差異性,為提高數(shù)據(jù)分區(qū)速率,需要在分區(qū)之前采用中心數(shù)據(jù)倉庫技術對異構數(shù)據(jù)進行集成。具體過程如下:

將過采樣權重引入數(shù)據(jù)集成的過程,即將多數(shù)樣本數(shù)據(jù)、少數(shù)樣本數(shù)據(jù)和數(shù)據(jù)誤分率相乘,得到過采樣權重系數(shù)為

(1)

式(1)中,Smin表示原始樣本數(shù)據(jù)中的少數(shù)樣本數(shù)據(jù),Smax表示原始樣本數(shù)據(jù)中的多數(shù)樣本數(shù)據(jù),α表示數(shù)據(jù)過采樣率,其取值范圍為[0,1],Bmin表示少數(shù)類子簇,Cmax表示多數(shù)類子簇,n表示多數(shù)類子簇的樣本量,m表示少數(shù)類子簇的樣本量,E(·)表示誤差率。

根據(jù)式(1)得到的過采樣權重系數(shù),可以實現(xiàn)對不同樣本數(shù)據(jù)的分簇處理,但是在分簇過程中會受到無關數(shù)據(jù)的影響,造成分簇結果有所偏差,因此需要引入少數(shù)類子簇概率分布控制方法,實現(xiàn)不同類數(shù)據(jù)之間的平衡。在少數(shù)類子簇中,假設r為構成子簇Bmin的概率分布樣本,則少數(shù)類子簇概率分布結果可以通過式(2)得到:

(2)

式(2)中,K表示相鄰樣本數(shù)據(jù),φ表示過采樣前的樣本權值,Wijk表示樣本數(shù)據(jù)的分簇結果,ri表示第i個少數(shù)類子簇的概率分布樣本。綜上,實現(xiàn)數(shù)據(jù)集成處理,為后續(xù)操作奠定基礎,以有效提高數(shù)據(jù)分區(qū)速率。

1.2 數(shù)據(jù)特征提取

以1.1節(jié)得到的數(shù)據(jù)集成結果為樣本數(shù)據(jù),對其進行特征提取。傳統(tǒng)的主成分分析方法是當前數(shù)據(jù)特征提取最常用的方法之一,然而該方法主要針對線性問題的處理,對于非線性問題往往不能發(fā)揮其作用。為此,以主成分分析為基礎,將核方法應用其中,構成核主成分分析方法,以實現(xiàn)有效精準的數(shù)據(jù)特征提取,為后續(xù)的數(shù)據(jù)分區(qū)提供可靠的支撐。先將待分析的一組數(shù)據(jù)利用多層傳感器核函數(shù)映射到合適的高維特征空間中,表示為

O(xi,yi)=tanh[b(xi,yi)+c]

(3)

式(3)中,b、c表示參數(shù),且b、c>0,tanh表示激活函數(shù),O(xi,yi)表示非線性映射后數(shù)據(jù)在高維特征空間中的坐標。

然后在這一空間中根據(jù)非線性映射規(guī)則,利用線性學習器進行數(shù)據(jù)處理和分析,具體過程為

(4)

式(4)中,T(xi,yi)表示線性處理后的數(shù)據(jù)坐標,k表示空間維數(shù),ζ表示非線性映射規(guī)則,即映射函數(shù)。

根據(jù)處理后的數(shù)據(jù),構建特征集Q和F,二者之間的線性變換為F=ZQ,其中Z表示線性變換矩陣。對其進行矩陣轉(zhuǎn)置可以得到:

RF=ZRQZT

(5)

式(5)中,RF和RQ分別表示向量Q和F的自相關矩陣,其中RQ可以通過Q的M個樣本估計得到,其計算公式為

(6)

式(6)中,xj表示第j個數(shù)據(jù)樣本,當T為正交矩陣時,RF有i個正實特征根pi,i=1,2,…,n,即主分量(數(shù)據(jù)特征值),由它們共同組成的矩陣RF為

RF=[pi],p1>p2>…>pn

(7)

此時,可選擇f個最大特征值對應的特征矢量構成維數(shù)子空間,其中分量與數(shù)據(jù)特征值的比值能夠反映正實特征根集合Y中第i個分量yi整體方差的貢獻,其貢獻越大,該分量越重,計算公式為

(8)

根據(jù)式(8)提取出貢獻較大的分量,將其作為數(shù)據(jù)特征,完成數(shù)據(jù)特征的提取處理。

1.3 構建分類器模型

以上述數(shù)據(jù)特征提取結果為基礎構建分類器模型,實現(xiàn)迭代式數(shù)據(jù)的均衡分區(qū),以機器學習中的決策樹為依據(jù)構建分類器模型,從而精準、高效地實現(xiàn)迭代式數(shù)據(jù)均衡分區(qū)。

首先,提取決策樹中的信息熵來反映迭代式樣本數(shù)據(jù)的不確定性:

(9)

式(9)中,o表示所提取的特征樣本數(shù)據(jù)量,P(i)表示數(shù)據(jù)集中屬于類別i的樣本占總樣本數(shù)量的比例。

根據(jù)數(shù)據(jù)的時空特性,給出迭代式數(shù)據(jù)的時空距離公式:

(10)

式(10)中,Dis(i,j)表示第i個數(shù)據(jù)時間點在序列x和第j個數(shù)據(jù)時間點在序列y之間的時空距離,d(x(i),y(j))表示在時空位置(i,j)的特征點x(i)和y(j)之間的距離,min(d(i-1,j),d(i,j-1),d(i-1,j-1))表示到達位置(i,j)的3種可能路徑中的最小距離。

根據(jù)迭代式數(shù)據(jù)的時空距離公式,可得到迭代式數(shù)據(jù)間的相似度公式如下:

(11)

假設t表示數(shù)據(jù)采樣周期,每隔周期t進行1次數(shù)據(jù)均衡分區(qū)操作。在建立數(shù)據(jù)分區(qū)規(guī)則過程中,假設Load(OSDm)表示樣本數(shù)據(jù)當前的分區(qū)情況,若分區(qū)節(jié)點OSDm的I/Q(即數(shù)據(jù)屬性與區(qū)域)任務列表Qm中的數(shù)據(jù)任務數(shù)為R,則:

(12)

分類器模型分區(qū)均衡度的計算公式如下:

(13)

式(13)中,r0表示分類器的整體分區(qū)水平,r0越大,分類器分區(qū)水平越高,Cm表示節(jié)點OSDm的負載水平。依據(jù)決策樹構建分類器,尋找數(shù)據(jù)屬性與區(qū)域之間的關系,即分辨出數(shù)據(jù)屬于哪一個分區(qū),從而實現(xiàn)數(shù)據(jù)的準確分類。

綜上所述,在數(shù)據(jù)集成與數(shù)據(jù)特征提取的基礎上實現(xiàn)對迭代式數(shù)據(jù)的均衡分區(qū)。

2 實驗分析

2.1 數(shù)據(jù)集和實驗指標

為測試基于機器學習的迭代式數(shù)據(jù)均衡分區(qū)算法的有效性,使用公共數(shù)據(jù)集KDD99作為實驗數(shù)據(jù)集,該數(shù)據(jù)集包含網(wǎng)絡連接的相關信息,主要涉及網(wǎng)絡連接的特征和類別標簽。特征包括連接的網(wǎng)絡通信協(xié)議及傳輸協(xié)議類型,具體包括源IP地址、目標IP地址、目標端口號、連接時長等通信信息。在該數(shù)據(jù)集中隨機選取400 000個數(shù)據(jù),分別構建訓練集和測試集。對于測試數(shù)據(jù)集,其數(shù)據(jù)量為200 000,使用學習率0.001進行運算,周期為20個;對于訓練數(shù)據(jù)集,其數(shù)據(jù)量為200 000,使用學習率0.0001進行運算,周期為80個。在多次訓練測試過程中,不斷優(yōu)化參數(shù),提高分類器模型性能,使其在處理大數(shù)據(jù)樣本時可更好地實現(xiàn)迭代式數(shù)據(jù)均衡分區(qū)。測試相關平臺配置如表1所示。

表1 平臺配置

考慮數(shù)據(jù)分區(qū)后,數(shù)據(jù)實現(xiàn)均衡分布,將查全率、查準率和數(shù)據(jù)分區(qū)均衡性作為評價指標。其中,查全率能夠反映算法分區(qū)結果的全面性,查全率越高,檢測和識別少數(shù)類別樣本的效果越好,即表示本文算法性能越好。計算公式為

(14)

式(14)中,TP表示數(shù)據(jù)正確分區(qū)數(shù)量,FN表示數(shù)據(jù)錯誤分區(qū)數(shù)量。

查準率是衡量算法分區(qū)結果的準確率,指的是將某一類別樣本分為真正屬于該類別樣本中的比例。查準率越高,表示本文算法在分辨不同類別上具有較高的準確性和可靠性。其計算公式為

(15)

式(15)中,FP表示錯標為正樣本的負樣本數(shù)。

數(shù)據(jù)分區(qū)均衡性是相關數(shù)據(jù)分區(qū)方法的重要衡量標準,其值越大,說明分區(qū)水平越高,主要由分類器的整體分區(qū)水平?jīng)Q定,故其計算公式見式(13)。

2.2 實驗結果

從圖2可以看出,利用本文算法對數(shù)據(jù)樣本進行迭代式均衡分區(qū),查全率呈現(xiàn)持續(xù)增長的趨勢,高于90%,而文獻[5]和文獻[7]方法的最高查全率在70%左右,文獻[6]、文獻[8]和文獻[9]方法的最高查全率在50%左右。與其他文獻方法相比,本文算法的查全率增長幅度較為明顯,因此本文提出的基于機器學習的迭代式數(shù)據(jù)均衡分區(qū)算法性能更優(yōu)越。

圖2 不同算法的查全率對比結果

分析圖3可知,隨著檢測時間的增加,6種方法的數(shù)據(jù)查準率均有所下降,但是本文算法的平均查準率明顯高于其他文獻方法。雖然在8～12 s的區(qū)間里,本文算法的查準率有所下降,但是在實驗后期又有所提高,并持續(xù)保持平穩(wěn),平均查準率在 85%以上。相比較之下,其他文獻方法只在實驗開始階段保持較高的查準率,隨著檢測時間的增加,查準率呈極度下降的趨勢,尤其是文獻[5]和文獻[8]方法,文獻[6]和文獻[9]方法次之,文獻[7]方法的查準率相對較高,但對比本文算法差距仍較大。根據(jù)上述分析可知,本文算法在查準率方面具有明顯的優(yōu)勢,可以在對迭代式數(shù)據(jù)進行均衡分區(qū)中保持良好的準確性,確保分區(qū)結果的可靠性。

圖3 不同方法的數(shù)據(jù)查準率比較結果

分析圖4可知,文獻[5]和文獻[6]方法的均衡性存在波動現(xiàn)象,說明這2種方法的數(shù)據(jù)分區(qū)均衡性較差,文獻[8]和文獻[9]方法的波動性雖然較小,但均衡性數(shù)值低,文獻[7]方法的波動性小且均衡性相對較高,但仍舊低于本文算法。較其他方法,本文算法的均衡性數(shù)值較高,均值在6左右,且波動幅度較小,說明本文算法不僅能夠完成對迭代式數(shù)據(jù)的均衡分區(qū),并且分區(qū)過程較為穩(wěn)定。這是由于所提算法在中心數(shù)據(jù)庫的輔助下對數(shù)據(jù)進行集成,該數(shù)據(jù)庫最大優(yōu)點是能夠?qū)μ崛〉降臄?shù)據(jù)進行最大控制,能夠有效解決數(shù)據(jù)分散性、多元性和冗余性等問題,從而提高了數(shù)據(jù)分區(qū)的均衡性。

圖4 不同方法的數(shù)據(jù)分區(qū)均衡性比較結果

3 總結

本文針對傳統(tǒng)方法存在的數(shù)據(jù)查準率、查全率較低和均衡性較差的問題,在機器學習的基礎上,對數(shù)據(jù)進行迭代式數(shù)據(jù)均衡分區(qū)研究,提高了數(shù)據(jù)分區(qū)的查全率和查準率,并且本文算法在數(shù)據(jù)分區(qū)均衡性方面均優(yōu)于傳統(tǒng)方法,能夠為數(shù)據(jù)分區(qū)工作提供參考,提高工作效率。未來會將研究重點放在抗干擾方面,以期進一步提高數(shù)據(jù)采集的準確性,提升數(shù)據(jù)查全率,從而提升迭代式數(shù)據(jù)均衡分區(qū)效果。