基于模糊K-Means的MBD隨機樣本分類仿真

李靜波,顧園園

(長春工業(yè)大學(xué)人文信息學(xué)院,吉林 長春 130102)

1 引言

隨著計算機技術(shù)的飛速發(fā)展,互聯(lián)網(wǎng)通信或云儲存空間內(nèi)留存的數(shù)據(jù)信息也在持續(xù)不斷增多[1]。面對信息量過載、信息分類不明確的網(wǎng)絡(luò)數(shù)據(jù)庫,用戶急切地需要一種有效的方法,以快速、準確地提取出簡潔、精練且有價值的目標信息。因此,研究人員提出將海量大數(shù)據(jù)樣本進行分類,減少用戶對目標信息的檢索時間,提高用戶對目標信息的獲取效率。

王忠震[2]等人通過噪聲樣本識別算法對樣本集中整體數(shù)據(jù)完成去噪處理,并過濾噪聲干擾強烈且無法識別的樣本數(shù)據(jù),再利用K鄰近(KNN)聚類原理將去噪后的優(yōu)化樣本集劃分成質(zhì)量相同的樣本子簇,考慮到樣本子簇的類間不平衡性,需要利用AdaBoost算法合成樣本子簇的簇心,該簇心具備類間特征屬性,可以通過決策樹分類器的訓(xùn)練,實現(xiàn)海量大數(shù)據(jù)隨機樣本的分類,但是該方法存在分類準確率低的問題。王凱亮[3]等人通過深度玻爾茲曼機(DBM)對先驗數(shù)據(jù)庫內(nèi)隨機數(shù)據(jù)進行采樣,再利用極限學(xué)校機(ELM)網(wǎng)絡(luò)對采集到的樣本集進行訓(xùn)練,獲取樣本集內(nèi)負荷曲線相關(guān)的優(yōu)化特征,將優(yōu)化特征投入到數(shù)據(jù)集分類模型中,實現(xiàn)海量大數(shù)據(jù)隨機樣本的分類。但是該方法存在分類召回率低的問題。董明剛[4]等人通過Bootstrap算法選取數(shù)據(jù)塊中小類樣本組成A類樣本合集,再利用DWES算法選取數(shù)據(jù)塊中大類樣本組成B類樣本合集,分別計算兩合集內(nèi)各數(shù)據(jù)的熵值大小以此構(gòu)建樣本特征合集,將樣本特征合集投入基分類中,實現(xiàn)樣本集內(nèi)整體數(shù)據(jù)的分類,但是該方法存在分類耗時長的問題。

為了解決上述方法中存在的問題,提出基于模糊K-Means的海量大數(shù)據(jù)隨機樣本分類仿真的方法。

2 數(shù)據(jù)降維及樣本特征提取

2.1 數(shù)據(jù)降維

數(shù)據(jù)降維[5]是指將冗余雜亂的海量高維數(shù)據(jù)根據(jù)點對點的映射原理改變成空間結(jié)構(gòu)緊湊、處理更加便捷的低維數(shù)據(jù),舉例來說,在網(wǎng)絡(luò)數(shù)據(jù)庫檢索目標信息時,數(shù)據(jù)庫內(nèi)原始樣本所具備的權(quán)重向量較為復(fù)雜,這種由于樣本權(quán)重向量復(fù)雜而導(dǎo)致用戶對目標信息檢索失敗的問題,稱為“維度災(zāi)難”,為了避免“維度災(zāi)難”干擾后續(xù)的樣本特征提取工作,需要對數(shù)據(jù)庫內(nèi)原始樣本進行降維處理。目前研究人員推出的降維方法包括線性辨別分析法、多維尺度分析法、主成分分析法和因子分析等,其中,常用于海量大數(shù)據(jù)隨機樣本分類的降維方法是因子分析法。

1)因子分析建模

設(shè)隨機選取的樣本集內(nèi)數(shù)據(jù)總量為x,觀測樣本數(shù)據(jù)的光譜維度從而建立因子分析模型,因子分析模型的表達式如下

T(x)=δ+gH+r

(1)

2)求解因子載荷矩陣的維度頻率

以光譜維度為基礎(chǔ)獲取的因子載荷矩陣無論是在維度平衡方面還是在數(shù)據(jù)光譜細節(jié)方面都表現(xiàn)出極高的穩(wěn)定性,為下一步樣本集內(nèi)整體數(shù)據(jù)的降維做好充足準備。根據(jù)精度原理推導(dǎo)因子載荷矩陣的維度平衡向量,精度奠定原理的表達式如下

(2)

式中,π表示維度平衡常數(shù);i∈[0,1]表示精度演算區(qū)間;dα-dβ表示鄰近樣本數(shù)據(jù)的權(quán)重差值。

根據(jù)協(xié)同方差計算公式獲取因子載荷矩陣的數(shù)據(jù)光譜細節(jié),協(xié)同方差計算公式的表達式如下

(3)

式中,β表示協(xié)方差系數(shù);ΔE表示光譜突出的細節(jié)位點。

已知因子載荷矩陣的維度平衡向量和數(shù)據(jù)光譜細節(jié),利用正交近似分解算法求解因子載荷矩陣的維度頻率,正交近似分解算法的表達式如下

(4)

其中

(5)

3)因子載荷矩陣的旋轉(zhuǎn)

因子載荷矩陣的旋轉(zhuǎn)建立在因子載荷矩陣維度頻率求解成功的基礎(chǔ)上,其目的在于旋轉(zhuǎn)樣本集中每個單位向量數(shù)據(jù),使數(shù)據(jù)本身的維度頻率盡可能靠近1或靠近0,以此實現(xiàn)樣本集內(nèi)整體數(shù)據(jù)的兩極分離,進而突出每個單位向量數(shù)據(jù)與公共維度因子之間的關(guān)系,即單位向量數(shù)據(jù)的維度頻率與公共維度因子的差值越大,說明該樣本表現(xiàn)為高維正畸數(shù)據(jù)的概率越大,單位向量數(shù)據(jù)的維度頻率與公共維度因子的差值越小,說明該樣本表現(xiàn)為高維異常數(shù)據(jù)的概率越大。將兩組數(shù)據(jù)歸類,利用元素平方的相對差求和公式過濾高維異常數(shù)據(jù),避免數(shù)據(jù)加權(quán)時,高維異常數(shù)據(jù)中心化對整體降維的影響。因子載荷矩陣的旋轉(zhuǎn)過程依靠最大分量旋轉(zhuǎn)法,旋轉(zhuǎn)后的因子載荷矩陣表示為:

其中,ε表示矩陣旋轉(zhuǎn)中心的因子參數(shù);表示旋轉(zhuǎn)角度。

元素平方的相對差求和公式如下

(6)

4)基于加權(quán)最小二乘法的樣本集內(nèi)數(shù)據(jù)降維

以優(yōu)化后保留高維正畸數(shù)據(jù)的樣本集為基礎(chǔ),利用加權(quán)最小二乘法對各數(shù)據(jù)進行降維,加權(quán)最小二乘法的表達式如下

(7)

2.2 基于信息熵和相關(guān)度的低維數(shù)據(jù)特征提取

經(jīng)過數(shù)據(jù)降維的樣本集不僅降低了算法復(fù)雜度,還過濾掉了特征信息量較少且鄰近特征信息冗余度過密的樣本數(shù)據(jù),使樣本集內(nèi)數(shù)據(jù)特征處于提取的最優(yōu)階段,基于信息熵[6]和相關(guān)度提取樣本特征的操作步驟如下:首先利用wrapper方法計算樣本集內(nèi)各數(shù)據(jù)信息熵,規(guī)定信息熵閾值為c<1,若不滿足閾值條件,則淘汰數(shù)據(jù),反之,將滿足閾值條件的數(shù)據(jù)整合為特征集,以特征集為基礎(chǔ),通過姿態(tài)特征選擇算法檢測內(nèi)部數(shù)據(jù)相關(guān)性,若兩數(shù)據(jù)相關(guān)性趨近于1,表示兩者特征內(nèi)容重合度高,需要利用異常檢測算法[7]保留兩者間特征信息量多的一方,并淘汰特征信息量少的一方。若兩數(shù)據(jù)相關(guān)性趨近于0,表示兩者特征內(nèi)容重合度低,可以省略檢測算法,同時保留雙方數(shù)據(jù)。Wrapper方法的表達式如下

(8)

式中,Qm表示任意數(shù)據(jù)m的信息熵;?表示wrapper系數(shù)。

姿態(tài)特征選擇算法的表達式如下

(9)

式中,XiYj表示數(shù)據(jù)i和數(shù)據(jù)j的相關(guān)性,當q趨近于1時,數(shù)據(jù)i和數(shù)據(jù)j的特征內(nèi)容重合率滿足ωi;當q趨近于0時,數(shù)據(jù)i和數(shù)據(jù)j的特征內(nèi)容重合率滿足ωj。

異常檢測算法的表達式如下

(10)

其中

(11)

式中,B表示異常檢測算法的準確率;n3表示異常檢測算法的誤檢率。

經(jīng)過信息熵閾值限定和相關(guān)度檢測的樣本數(shù)據(jù)在快速收斂函數(shù)[8]內(nèi)完成多次迭代,實現(xiàn)樣本特征的提取?？焖偈諗亢瘮?shù)的表達式如下

(12)

式中,υ表示快速收斂函數(shù)的常數(shù);m表示迭代次數(shù);ΔK表示樣本特征矩陣。

3 基于模糊K-Means聚類算法的樣本特征分類

模糊K-Means聚類算法是以樣本特征為基礎(chǔ)的一種簇族式分類方法,其具體操作為:首先利用初始聚類算法獲取樣本集內(nèi)多個聚類中心[9],各樣本特征值與聚類中心之間的距離被稱為歐氏距離,視聚類中心為圓點中心,將歐氏距離不超過Lk的樣本特征劃分為一簇,以簇為單位,利用模糊K-Means聚類算法[10]獲取各簇族的類別系數(shù),根據(jù)最優(yōu)聚類標準將類別系數(shù)相同的簇族進行歸一化處理,得到基于模糊K-Means聚類算法的特征樣本分類矩陣。模糊K-Means聚類算法流程如下圖1所示。

圖1 模糊K-Means聚類算法流程

設(shè)待分類的樣本特征集為k,且每個樣本特征都與矩陣中的低維樣本數(shù)據(jù)一一對應(yīng)。將樣本特征集輸入初始聚類算法中獲取該特征集的多個聚類中心[11]。初始聚類算法的表達式如下

(13)

式中,q表示初始聚類系數(shù);k,l∈[0,1]表示聚類中心閾值;R(k·l)表示滿足聚類中心限制條件的樣本特征數(shù)[12,13]。

在成功獲取樣本特征集多個聚類中心后,觀察各樣本特征值與聚類中心之間的歐氏距離,完成樣本特征簇族單位的劃分,并以此為基礎(chǔ),加入模糊K-Means聚類算法獲取各簇族的類別系數(shù)。模糊K-Means聚類算法的表達式如下

(14)

最優(yōu)聚類標準的表達式如下

(15)

式中,f(x)表示最優(yōu)聚類系數(shù);f(y)表示類別系數(shù)歸一化參數(shù)[14,15];Sc表示特征樣本分類矩陣。根據(jù)特征樣本分類矩陣實現(xiàn)海量大數(shù)據(jù)隨機樣本的分類。

4 實驗與分析

為了驗證基于模糊K-Means的海量大數(shù)據(jù)隨機樣本分類仿真的整體有效性,需要對其進行測試。

選擇1000篇新聞稿件組成樣本數(shù)據(jù)集A,稿件主題涉及時政、經(jīng)濟、娛樂、新媒體等30多個類別;選擇3000篇語言類稿件組成樣本數(shù)據(jù)集B,稿件語言涉及英文、俄文、日文等20多個類別;選擇5000篇說明書類稿件組成樣本數(shù)據(jù)集C,稿件內(nèi)容涉及機械、計算機、工業(yè)機器等10多個類別,上述三組樣本集內(nèi)各數(shù)據(jù)信息的關(guān)鍵詞、樣本特征、類別屬性均無序且混亂,分別采用不同方法對三組樣本數(shù)據(jù)集進行分類,測試指標為準確率、召回率、F1值以及分類時間。準確率、召回率、F1值的計算式如下

(16)

式中,N表示樣本數(shù)據(jù)的總數(shù);accuracy表示準確率;recall表示召回率。

1)準確率

對比所提方法、文獻[2]方法和文獻[3]方法的分類準確率,進而評估不同方法的分類性能。不同方法的準確率對比如圖2所示。

由圖2可見,所提方法在三組樣本數(shù)據(jù)集中的分類準確率均不低于95%,說明所提方法在面對任意樣本數(shù)據(jù)集時均能表現(xiàn)出精確度較高的分類能力,這是因為所提方法利用因子分析法對樣本數(shù)據(jù)集進行降維,從而得到運算簡便的低維數(shù)據(jù),低維數(shù)據(jù)的獲取不僅提高了樣本特征的分類準確度,還加快了樣本數(shù)據(jù)集的分類速度,大大提升了用戶獲取目標信息的效率。文獻[2]方法和文獻[3]方法在三組樣本數(shù)據(jù)集中的分類準確率分別不超過70%和50%,兩者均與所提方法存在一定差距,說明文獻[2]方法和文獻[3]方法的分類精確度較低。經(jīng)上述對比可知,所提方法的分類準確率高。

2)召回率

為了進一步驗證不同方法的分類性能,對比提方法、文獻[2]方法和文獻[3]方法的召回率,對比結(jié)果如下圖3所示。

圖3 不同方法的召回率對比

由上圖3可見,所提方法在三組樣本數(shù)據(jù)集中的召回率均接近100%,說明所提方法具備良好的分類能力和穩(wěn)定性。文獻[2]方法和文獻[3]方法在三組樣本數(shù)據(jù)集的召回率分別低于60%和50%,說明文獻[2]方法和文獻[3]方法的分類能力較差,與所提方法存在較大差距。經(jīng)上述對比,進一步驗證了所提方法的分類性能更強。

3)F1值

通過F1對精度和召回率進行整體評價,以突出所提方法的性能優(yōu)勢。不同方法的F1值對比如下圖4所示。

圖4 不同方法的F1值對比

由上圖4可見,所提方法在三組樣本數(shù)據(jù)集中的F1值均不低于90%,而文獻[2]方法和文獻[3]方法在三組樣本數(shù)據(jù)集中的F1值分別低于75%和65%,可見所提方法在分類能力上明顯優(yōu)于傳統(tǒng)方法。

4)分類時間

采用不同方法對樣本數(shù)據(jù)集進行分類所消耗的時間與該方法的分類效率成反比,觀察所提方法、文獻[3]方法和文獻[4]方法對三組樣本數(shù)據(jù)集進行分類所消耗的時間,為避免統(tǒng)計學(xué)誤差,同時計算三組樣本數(shù)據(jù)集的平均分類時間。不同方法的分類時間對比如下表1所示。

表1 不同方法的分類時間對比

由上表1可知,所提方法在三組樣本數(shù)據(jù)集中的分類時間及平均分類時間均低于1s,說明所提方法能夠快速實現(xiàn)海量數(shù)據(jù)的分類,適用于發(fā)展迅速的大數(shù)據(jù)網(wǎng)絡(luò)時代。文獻[3]方法和文獻[4]方法在三組樣本數(shù)據(jù)集的分類時間及平均分類時間分別超過1.19s和2.26s,兩者與所提方法存在一定差距。經(jīng)上述對比可知,所提方法的分類耗時短,分類效率高。

5 結(jié)束語

在科技快速發(fā)展的現(xiàn)代社會,大數(shù)據(jù)儼然成為互聯(lián)網(wǎng)熱頻詞匯,如何處理大數(shù)據(jù)規(guī)模下的冗余雜亂的信息,使用戶能夠在數(shù)萬億Web搜索內(nèi)容中鎖定目標信息,已成為研究人員需要重點解決的問題。如何在引入模糊K-Means聚類算法的基礎(chǔ)上,查明樣本分類過程中數(shù)據(jù)流拓撲并行化的機制是研究人員下一步工作的重點。