基于機器學習的迭代式數據均衡分區算法研究

張鏑, 吳宇強

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

0 引言

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

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

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

1 基于機器學習的迭代式數據均衡分區算法

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

圖1 基于機器學習的迭代式數據均衡分區總體框架

1.1 數據集成與處理

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

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

(1)

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

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

(2)

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

1.2 數據特征提取

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

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

(3)

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

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

(4)

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

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

RF=ZRQZT

(5)

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

(6)

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

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

(7)

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

(8)

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

1.3 構建分類器模型

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

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

(9)

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

根據數據的時空特性,給出迭代式數據的時空距離公式:

(10)

式(10)中,Dis(i,j)表示第i個數據時間點在序列x和第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種可能路徑中的最小距離。

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

(11)

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

(12)

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

(13)

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

綜上所述,在數據集成與數據特征提取的基礎上實現對迭代式數據的均衡分區。

2 實驗分析

2.1 數據集和實驗指標

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

表1 平臺配置

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

(14)

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

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

(15)

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

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

2.2 實驗結果

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

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

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

圖3 不同方法的數據查準率比較結果

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

圖4 不同方法的數據分區均衡性比較結果

3 總結

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