基于機(jī)器學(xué)習(xí)的迭代式數(shù)據(jù)均衡分區(qū)算法研究

張鏑, 吳宇強(qiáng)

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

0 引言

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

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

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

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

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

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

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

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

將過采樣權(quán)重引入數(shù)據(jù)集成的過程,即將多數(shù)樣本數(shù)據(jù)、少數(shù)樣本數(shù)據(jù)和數(shù)據(jù)誤分率相乘,得到過采樣權(quán)重系數(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)得到的過采樣權(quán)重系數(shù),可以實(shí)現(xiàn)對不同樣本數(shù)據(jù)的分簇處理,但是在分簇過程中會受到無關(guān)數(shù)據(jù)的影響,造成分簇結(jié)果有所偏差,因此需要引入少數(shù)類子簇概率分布控制方法,實(shí)現(xiàn)不同類數(shù)據(jù)之間的平衡。在少數(shù)類子簇中,假設(shè)r為構(gòu)成子簇Bmin的概率分布樣本,則少數(shù)類子簇概率分布結(jié)果可以通過式(2)得到:

(2)

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

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

以1.1節(jié)得到的數(shù)據(jù)集成結(jié)果為樣本數(shù)據(jù),對其進(jìn)行特征提取。傳統(tǒng)的主成分分析方法是當(dāng)前數(shù)據(jù)特征提取最常用的方法之一,然而該方法主要針對線性問題的處理,對于非線性問題往往不能發(fā)揮其作用。為此,以主成分分析為基礎(chǔ),將核方法應(yīng)用其中,構(gòu)成核主成分分析方法,以實(shí)現(xiàn)有效精準(zhǔ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ù)在高維特征空間中的坐標(biāo)。

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

(4)

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

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

RF=ZRQZT

(5)

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

(6)

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

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

(7)

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

(8)

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

1.3 構(gòu)建分類器模型

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

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

(9)

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

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

(10)

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

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

(11)

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

(12)

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

(13)

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

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

2 實(shí)驗(yàn)分析

2.1 數(shù)據(jù)集和實(shí)驗(yàn)指標(biāo)

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

表1 平臺配置

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

(14)

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

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

(15)

式(15)中,FP表示錯(cuò)標(biāo)為正樣本的負(fù)樣本數(shù)。

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

2.2 實(shí)驗(yàn)結(jié)果

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

圖2 不同算法的查全率對比結(jié)果

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

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

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

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

3 總結(jié)

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