基于Spark的證據(jù)鄰域粗糙并行分類高效算法

李 銘,丁衛(wèi)平,鞠恒榮,孫 穎,秦廷楨,黃嘉爽

(南通大學(xué) 信息科學(xué)技術(shù)學(xué)院,江蘇 南通 226019)

近年來,隨著現(xiàn)代化信息技術(shù)的蓬勃發(fā)展,數(shù)據(jù)的指數(shù)式增長給傳統(tǒng)的數(shù)據(jù)挖掘和分析技術(shù)帶來了嚴(yán)峻挑戰(zhàn),也給各行各業(yè)的發(fā)展帶來了寶貴機(jī)遇。大數(shù)據(jù)不同于傳統(tǒng)數(shù)據(jù),其具有潛在價(jià)值高和數(shù)據(jù)密度低等特點(diǎn)[1],大數(shù)據(jù)的挖掘?yàn)楸姸嘌芯咳藛T提供了許多寶貴的機(jī)遇。傳統(tǒng)的大數(shù)據(jù)處理技術(shù)主要通過云計(jì)算平臺(tái)[2]利用云計(jì)算、分布式計(jì)算以及并行計(jì)算將大規(guī)模數(shù)據(jù)切分成多個(gè)數(shù)據(jù)子集,降低數(shù)據(jù)規(guī)模,使其可計(jì)算,但無法刪除數(shù)據(jù)中的冗余屬性,減少數(shù)據(jù)間的不確定性。

粒計(jì)算逐漸發(fā)展成人工智能領(lǐng)域的一個(gè)新分支,它的核心思想是對(duì)信息和知識(shí)進(jìn)行?；?、層次化,通過不同的粒度結(jié)構(gòu)來處理問題。粗糙集理論[3]是主要的粒計(jì)算模型之一,它能夠處理和分析決策過程中的不確定性信息。在粗糙集中,屬性約簡算法[4]是一個(gè)重要的概念,通過刪除冗余數(shù)據(jù)和屬性來減少數(shù)據(jù)的復(fù)雜性和不確定性。如何利用粗糙集理論從大規(guī)模數(shù)據(jù)中挖掘出巨大的潛在價(jià)值早已成為眾多學(xué)者研究的課題之一。針對(duì)大規(guī)模數(shù)據(jù)的“5V”特性,梁吉業(yè)等[5]和Li等[6]詳細(xì)地分析了粒計(jì)算模型處理大規(guī)模數(shù)據(jù)的可計(jì)算性、有效性和時(shí)效性。Qian等[7,8]通過深入研究MapReduce編程框架中的Map操作和Reduce操作,通過Map操作計(jì)算等價(jià)類,再通過Reduce操作對(duì)相同鍵值的等價(jià)類進(jìn)行聚合,提出了基于MapReduce的并行知識(shí)約簡算法。為解決大規(guī)模數(shù)據(jù)的實(shí)時(shí)性和不完備性問題,張鈞波等[9]和Hamed等[10]基于不同的粗糙集擴(kuò)展模型實(shí)現(xiàn)了基于MapReduce的并行近似計(jì)算和并行屬性約簡算法。在上述研究中,眾多研究人員解決了經(jīng)典粗糙集模型無法處理大規(guī)模數(shù)據(jù)集的局限性問題,同時(shí)也利用粗糙集屬性約簡算法刪除大規(guī)模數(shù)據(jù)中的冗余屬性并提高計(jì)算效率。但是,上述研究并沒有解決經(jīng)典粗糙集無法直接處理數(shù)值型數(shù)據(jù)以及Hadoop MapReduce在讀寫過程中產(chǎn)生多余損耗和迭代計(jì)算性能差等問題。

為了避免數(shù)據(jù)離散化過程中造成部分信息丟失,Hu等[11]基于鄰域關(guān)系提出了鄰域粗糙集模型,它能夠直接處理數(shù)值型數(shù)據(jù)。在鄰域粗糙集模型中,可以根據(jù)不同的鄰域半徑得到不同的鄰域空間樣本,從不同的粒度來刻畫整體樣本空間。

基于鄰域粗糙集模型,Hu等[12]提出了鄰域分類器。不同于傳統(tǒng)的K鄰近(K-nearest neighbor,KNN)模型中選取最近的k個(gè)樣本,鄰域分類器是在某個(gè)鄰域半徑下通過未分類樣本的鄰域空間內(nèi)所有樣本來近似刻畫此樣本。鄰域分類器因其良好的分類性能在分類問題中得到廣泛應(yīng)用。然而,鄰域分類器在決策過程中采用的是多數(shù)投票機(jī)制,根據(jù)未分類樣本鄰域空間中數(shù)據(jù)對(duì)象的類別標(biāo)簽進(jìn)行預(yù)測(cè)。多數(shù)投票機(jī)制沒有考慮到鄰域樣本之間的空間差異性[13]和鄰域樣本標(biāo)簽的不確定性[14,15]。為解決多數(shù)投票機(jī)制的兩個(gè)不足之處,Denoeux[14]將其提出的D-S證據(jù)理論應(yīng)用到KNN分類器中,利用所有鄰域空間樣本的融合證據(jù)支持信息預(yù)測(cè)樣本標(biāo)簽,提高了分類精度;Zhang等[15]將D-S證據(jù)理論引入KNN分類器后,再將其與集成學(xué)習(xí)機(jī)制結(jié)合,提出了D-S驅(qū)動(dòng)的KNN集成分類器。目前,將D-S證據(jù)理論用于融合粗糙集理論決策過程中證據(jù)支持信息的研究較少。

相較于Hadoop MapReduce,Spark是基于內(nèi)存的類Hadoop MapReduce分布式計(jì)算框架。Spark框架會(huì)將中間數(shù)據(jù)存儲(chǔ)到內(nèi)存中,不會(huì)因多次讀寫而產(chǎn)生多余的損耗。同時(shí),Spark的迭代計(jì)算的性能遠(yuǎn)優(yōu)于Hadoop MapReduce。Chelly等[16]針對(duì)大規(guī)模數(shù)據(jù)預(yù)處理,基于Spark框架提出了分布式粗糙集擴(kuò)展模型,在Spark計(jì)算過程中將數(shù)據(jù)緩存于內(nèi)存中減少了不必要的時(shí)間損耗;Zhou等[17]分別介紹了基于MapReduce和Spark的粗糙集擴(kuò)展模型研究現(xiàn)狀,并分析兩種擴(kuò)展模型之間的差異性。然而,大規(guī)模數(shù)據(jù)中不僅存在名義型數(shù)據(jù),還存在數(shù)值型數(shù)據(jù)。上述研究中,大多數(shù)的粗糙集并行擴(kuò)展模型只適用于名義型數(shù)據(jù),無法直接處理大規(guī)模數(shù)值型數(shù)據(jù)。

基于以上討論,本文提出基于Spark的證據(jù)鄰域粗糙并行分類高效算法(Efficient algorithm of evidences neighborhood rough parallel classification based on spark framework,SENRPC)。此算法主要分為兩部分:首先針對(duì)大規(guī)模數(shù)值型數(shù)據(jù),本文實(shí)現(xiàn)了基于Spark的鄰域決策錯(cuò)誤率并行屬性約簡算法,刪除數(shù)據(jù)中的冗余屬性并減少數(shù)據(jù)間的不確定性;然后針對(duì)多數(shù)投票機(jī)制的不足之處,本文實(shí)現(xiàn)了基于Spark的鄰域證據(jù)并行分類算法,能夠并行融合鄰域中類內(nèi)樣本和類間樣本的證據(jù)支持信息,提高對(duì)未分類樣本的分類準(zhǔn)確率。

本文主要工作如下:

(1)為了解決Hadoop MapReduce框架存在多余的時(shí)間損耗和迭代性能差的問題,本文基于Spark框架實(shí)現(xiàn)了并行屬性約簡算法和并行分類算法;

(2)為了解決經(jīng)典粗糙集模型無法處理數(shù)值型數(shù)據(jù)的問題,本文在Spark框架下引入基于鄰域決策錯(cuò)誤率的鄰域粗糙集模型,并通過并行屬性約簡算法去除冗余屬性;

(3)為了解決多數(shù)投票機(jī)制沒有考慮到鄰域樣本之間的空間差異性和標(biāo)簽的不確定性的問題,本文在Spark框架下引入D-S證據(jù)理論并行融合分類決策過程中的證據(jù)支持信息,提高了模型分類精度。

為更好地體現(xiàn)本文算法的有效性,本文通過不平衡數(shù)據(jù)[18]實(shí)驗(yàn)來評(píng)估算法的分類性能。

1 基礎(chǔ)知識(shí)

1.1 鄰域粗糙集

Lin等[19]根據(jù)距離度量將樣本空間中不同的樣本劃分成多個(gè)模糊信息粒簇,提出了模糊鄰域系統(tǒng),并將鄰域系統(tǒng)引入粗糙集模型中提出了鄰域粗糙集的原始模型。Hu等[11]從數(shù)值空間鄰域?；慕嵌戎匦露x和詮釋了鄰域粗糙集模型。

δB(xi)={xj|xj∈U,disB(xi,xj)}

(1)

(2)

(3)

定義3[11]在決策信息系統(tǒng)S=〈U,C∪D,V,f〉中,有B?C,那么決策屬性D相對(duì)于條件屬性子集B的依賴度定義如下

(4)

式中:|·|表示集合中的元素個(gè)數(shù)。

考慮到依賴性度量主要是根據(jù)正域來評(píng)估信息表的一致性,忽略了邊界域中模糊信息對(duì)決策過程的影響。Hu等[11]認(rèn)為并非所有落入邊界域的樣本都會(huì)存在誤分類情況,只有少數(shù)樣本不能被識(shí)別,并針對(duì)依賴性度量無法反映出邊界域樣本分類的真實(shí)情況,提出了鄰域決策錯(cuò)誤率用于評(píng)估屬性子集的性能。

(5)

可得鄰域決策錯(cuò)誤率(Neighborhood decision error rate,NDER)的定義如下

(6)

式中:M表示樣本數(shù)。

1.2 D-S證據(jù)理論

D-S證據(jù)理論[14]是基于信任函數(shù)的證據(jù)融合理論,是概率論中貝葉斯理論的擴(kuò)展。在傳統(tǒng)的貝葉斯概率理論中,一個(gè)問題的答案是所有可能答案中可能性最大的答案;而在D-S證據(jù)理論中,一個(gè)問題的答案是所有可能答案對(duì)問題支持信息融合得到的最終答案。

定義5[14]在辨識(shí)框架Ω下,可將樣本空間劃分成多個(gè)子集集合Ω={X1,X2,…,Xd},其中任意子集Xs對(duì)應(yīng)于一個(gè)數(shù)M∈[0,1],可稱M為冪集2Ω在區(qū)間[0,1]上的基本概率分配函數(shù),并且此函數(shù)滿足

M(φ)=0

(7)

(8)

式中:不可能事件的基本概率置信度為0,M({Xs})為Xs的基本概率函數(shù)。

若對(duì)于任意的Xs?Ω且M({Xs})>0,則可稱A為M的一個(gè)焦元,即對(duì)Xs的支持信任度量。

定義6[14]由基本概率分配函數(shù)可知,信任函數(shù)Bel和似然函數(shù)Pl的定義如下

(9)

(10)

式中:Bel({Xs})為Xs中全部子集基本置信度之和,Pl({Xs})為對(duì)Xs的非否信任度,即對(duì)Xs似乎可能成立的不確定性度量。

1.3 Spark框架

Spark是基于內(nèi)存存儲(chǔ)的大規(guī)模快速并行計(jì)算框架。相較于Hadoop MapReduce而言,Spark具有計(jì)算速度快、易用性好和通用性高等特點(diǎn)[20]。Spark框架在計(jì)算過程將中間數(shù)據(jù)存儲(chǔ)到內(nèi)存中,當(dāng)內(nèi)存溢出時(shí),可將數(shù)據(jù)存儲(chǔ)到磁盤上。Spark框架在Map和Reduce算子的基礎(chǔ)上,衍生出轉(zhuǎn)換和行動(dòng)兩類彈性分布式數(shù)據(jù)集(Resilient distributed dataset,RDD)算子,并提供4種編程語言的API。同時(shí),眾多開發(fā)者基于Spark框架推出了Spark SQL、Spark Streaming、MLLib和GraphX等一系列組件[21],形成了一個(gè)大規(guī)模數(shù)據(jù)處理的云計(jì)算平臺(tái)。

Spark任務(wù)執(zhí)行過程主要分為兩個(gè)階段[20,21]:第一個(gè)階段從Hadoop分布式文件系統(tǒng)(Hadoop distributed file system,HDFS)上讀取數(shù)據(jù)生成RDD對(duì)象,并根據(jù)RDD之間的依賴關(guān)系構(gòu)建有向無環(huán)圖(Directed acyclic graph,DAG),將不同的RDD算子操作劃分成不同的任務(wù);第二階段通過集群管理器將不同的任務(wù)分配給不同的子節(jié)點(diǎn)執(zhí)行。Spark任務(wù)運(yùn)行流程如圖1所示。

行常規(guī)西藥治療，即：①選用劑量為0.5 g的多索茶喊和250 mL的9%生理鹽水進(jìn)行靜滴治療（1次/d）；②除了使用多索茶喊外還可以服用布地奈德（0.1 mg/次，2次/d）。

圖1 Spark任務(wù)運(yùn)行流程圖

2 基于Spark的證據(jù)鄰域粗糙并行分類高效算法

基于以上討論,為解決上述不足之處,本文提出了基于Spark的證據(jù)鄰域粗糙并行分類高效算法。此算法在Spark框架下分別實(shí)現(xiàn)了并行屬性約簡算法和并行分類算法,提高了模型的計(jì)算效率和分類精度。

如圖2所示,SENRPC算法數(shù)據(jù)處理的過程如下:

圖2 基于Spark的證據(jù)鄰域粗糙并行分類高效算法的數(shù)據(jù)處理過程

(1)將數(shù)據(jù)集劃分成訓(xùn)練集和測(cè)試集,對(duì)訓(xùn)練集進(jìn)行并行欠采樣降低訓(xùn)練集的不平衡率,并得到多個(gè)訓(xùn)練子集;

(2)在子節(jié)點(diǎn)上對(duì)于相應(yīng)的訓(xùn)練子集,基于鄰域決策錯(cuò)誤率評(píng)估出每個(gè)條件屬性的屬性重要度,并且根據(jù)屬性約簡的停止準(zhǔn)則得到滿足條件的屬性約簡子集;

(3)根據(jù)屬性約簡子集集合對(duì)訓(xùn)練子集集合和測(cè)試集進(jìn)行更新,分別形成新的數(shù)據(jù)集,在子節(jié)點(diǎn)上利用D-S證據(jù)理論驅(qū)動(dòng)的鄰域分類器對(duì)測(cè)數(shù)據(jù)集進(jìn)行分類,將得到的預(yù)測(cè)類別標(biāo)簽集合發(fā)送到主節(jié)點(diǎn)上,然后根據(jù)多數(shù)投票機(jī)制得到最大概率的類別標(biāo)簽。

2.1 不平衡數(shù)據(jù)的并行隨機(jī)欠采樣預(yù)處理

本文通過基于Spark的并行欠采樣算法來降低數(shù)據(jù)的不平衡率(Imbalance rate,IR)和擴(kuò)充數(shù)據(jù)集規(guī)模。首先,從正類樣本數(shù)據(jù)中隨機(jī)并行抽取與負(fù)類樣本相同規(guī)模的數(shù)據(jù);然后,將其與負(fù)類樣本數(shù)據(jù)重構(gòu),生成多個(gè)新的數(shù)據(jù)子集。

定義7對(duì)于一個(gè)決策信息表S=〈U,C∪D,V,f〉,其中U={x1,x2,…,xM},假設(shè)正類樣本集合UP={y1,y2,…,yP},負(fù)類樣本集合UN={z1,z2,…,zN},且P+N=M。通過并行欠采樣得到新的決策信息子表集合{S1,S2,…,Sm}的定義如下

Si=〈Ui,C∪D,V,f〉

(11)

基于如上討論,本文設(shè)計(jì)如下算法1:不平衡數(shù)據(jù)的并行隨機(jī)欠采樣處理(Imbalance data parallelize random undersampling,IDPRUS),降低數(shù)據(jù)集的不平衡率,同時(shí)通過并行機(jī)制對(duì)數(shù)據(jù)集進(jìn)行重構(gòu)和擴(kuò)充,擴(kuò)大數(shù)據(jù)集規(guī)模。

算法1不平衡數(shù)據(jù)的并行欠采樣IDPRUS算法

輸入:決策信息表S=〈U,C∪D,V,f〉;

輸出:決策信息子表集合{S1,S2,…,Sm};

1: 在主節(jié)點(diǎn)上,從本地讀取數(shù)據(jù)集,創(chuàng)建SparkSession對(duì)象,并將數(shù)據(jù)類型轉(zhuǎn)換成Dataframe類型;

2: 根據(jù)類別標(biāo)簽篩選出正類樣本集UP和負(fù)類樣本集UN;

3: 對(duì)于所有的子節(jié)點(diǎn)slavei(i∈{1,2,…,m});

4: 將UN廣播到所有子節(jié)點(diǎn)上;

7: 返回新的決策信息子表集合{S1,S2,…,Sm}。

2.2 基于Spark的鄰域決策錯(cuò)誤率并行屬性約簡

為解決Hadoop MapReduce框架的不足之處,本文在MapReduce框架的基礎(chǔ)上利用Spark開發(fā)平臺(tái)實(shí)現(xiàn)了可編譯性和易用性更高的并行屬性約簡算法。本文率先引入基于鄰域決策錯(cuò)誤率的屬性約簡算法,并實(shí)現(xiàn)了基于Spark的鄰域決策錯(cuò)誤率并行屬性約簡,篩選出不同數(shù)據(jù)子集中的冗余屬性,降低數(shù)據(jù)規(guī)模和計(jì)算時(shí)間,提高計(jì)算效率。

(12)

(13)

式中:2N表示決策信息子表Si中的樣本數(shù)。

定義10[11]在決策信息子表Si中,有Ri?C,若Ri為Si基于鄰域決策錯(cuò)誤率的屬性約簡子集,則Ri需要滿足:

(1)NDERiRi≤NDERiC;

根據(jù)上述屬性約簡過程,對(duì)候選屬性的屬性重要度定義如下。

SIG(a,Ri,D)=NDERiRi(D)-NDERiRi∪{a}(D)

(14)

基于以上定義,本文設(shè)計(jì)如下算法2:基于Spark的鄰域決策錯(cuò)誤率并行屬性約簡(Neighborhood decision error rate parallelize attribute reduction based on spark,NDER-PARS)算法。算法2首先將決策信息子表集合{S1,S2,…,Si,…,Sm}發(fā)送到相應(yīng)的子節(jié)點(diǎn)slavei上;然后計(jì)算決策信息子表Si中每個(gè)條件屬性的屬性重要度,將屬性重要度值最大的條件屬性添加到屬性約簡子集Ri中;然后計(jì)算屬性約簡子集Ri的鄰域決策錯(cuò)誤率,直到滿足NDERiRi≤NDERiC;最后,輸出屬性約簡子集集合{R1,R2,…,Rm}。

算法2基于Spark的鄰域決策錯(cuò)誤率并行屬性約簡(NDER-PARS)算法

輸入:決策信息子表集合{S1,S2,…,Sm},鄰域半徑δ;

輸出:屬性約簡子集集合{R1,R2,…,Rm};

1: ?→{R1,R2,…,Rm};

2: 對(duì)于所有子節(jié)點(diǎn)slavei上的決策信息子表Si(i=1,2,…,m);

4: 選取最大屬性重要度及其對(duì)應(yīng)的屬性ak;

5: 如果候選屬性ak的屬性重要度SIG(ak,Ri,D)大于0,那么

6: 將屬性ak添加到屬性約簡子集Ri中;

9: 得到屬性約簡子集Ri;

10:輸出屬性約簡子集集合{R1,R2,…,Rm}。

2.3 基于Spark的鄰域證據(jù)并行分類算法

在屬性約簡子集集合{R1,R2,…,Rm}上,對(duì)決策信息子表集合{S1,S2,…,Sm}進(jìn)行更新,得到新的決策信息子表集合{S′1,S′2,…,S′m},其中S′i=〈Ui,Ri∪D,Va,f〉。

(15)

Mt,j(πi)=1-β

(16)

式中:0<β0<1,γq>0。

(dis(xt,xj))2})

(17)

(dis(xt,xj))2})

(18)

q=1,2,…,d

(19)

(20)

式中:K為歸一化因子,其定義如下[14]

(21)

(22)

(23)

(24)

在決策信息子表集合{S′1,S′2,…,S′m}中,可得未分類樣本xt的預(yù)測(cè)類別標(biāo)簽集合為{ω1t,ω2t,…,ωmt}。根據(jù)投票策略,可得未分類樣本xt在決策信息表S下的預(yù)測(cè)類別標(biāo)簽定義如下

(25)

基于以上討論,本文設(shè)計(jì)如下算法3:基于Spark的鄰域證據(jù)并行分類(Parallelize neighbor-hood D-S evidence classifiers based on spark,PNDSCS)算法。在鄰域粗糙并行分類算法的決策過程中,并行融合整個(gè)鄰域空間內(nèi)的證據(jù)支持信息。本文在不同屬性約簡子集上從多個(gè)粒度結(jié)構(gòu)并行計(jì)算鄰域中類內(nèi)樣本和類間樣本之間的證據(jù)支持信息。該算法在分類決策過程中充分地考慮了鄰域樣本數(shù)據(jù)分布的緊密性,提高了分類過程的計(jì)算效率和分類準(zhǔn)確度。

算法3基于Spark的鄰域證據(jù)并行分類(PNDSCS)算法

輸入:決策信息表S=〈U,C∪D,Va,f〉,鄰域半徑δ,未分類樣本xt;

輸出:xt的預(yù)測(cè)類別標(biāo)簽ωt;

1: 根據(jù)算法1進(jìn)行不平衡數(shù)據(jù)并行隨機(jī)欠采樣處理,得到?jīng)Q策信息子表集合{S1,S2,…,Sm};

2: 根據(jù)算法2進(jìn)行并行屬性約簡,得到屬性約簡子集集合{R1,R2,…,Rm};

3: 對(duì)于所有的子節(jié)點(diǎn)slavei上的決策信息子表Si進(jìn)行更新得到新的決策信息子表S′i(i=1,2,…,m);

4: 計(jì)算決策類劃分πi和待測(cè)樣本xt的鄰域空間δRi(xt);

7: 根據(jù)式(24)計(jì)算在決策信息子表S′i下的預(yù)測(cè)類別標(biāo)簽ωti,并發(fā)送到主節(jié)點(diǎn)master上;

8: 在主節(jié)點(diǎn)master上得到未分類樣本xt在決策信息子表集合{S1,S2,…,Sm}下的預(yù)測(cè)類別標(biāo)簽集合{ω1t,ω2t,…,ωmt};

9: 在主節(jié)點(diǎn)上根據(jù)式(25)進(jìn)行聚合操作得到未分類樣本xt的最終預(yù)測(cè)類別標(biāo)簽ωt;

10:輸出未分類樣本xt的預(yù)測(cè)類別標(biāo)簽ωt。

3 實(shí)驗(yàn)和結(jié)果分析

本文通過6組UCI不平衡數(shù)據(jù)的分類實(shí)驗(yàn),檢驗(yàn)了SENRPC算法的性能。本文采用的實(shí)驗(yàn)平臺(tái)為PC(Intel(R)Core(TM)i7-10875H CPU@2.30 GHz,RAM 16 GB),Windows10家庭中文版操作系統(tǒng),開發(fā)工具為JetBrains PyCharm,使用Python語言實(shí)現(xiàn)實(shí)驗(yàn)中相關(guān)算法。本文在Windows10系統(tǒng)上搭建MapReduce Hadoop-2.7.1和Spark-3.0.0-preview的模擬環(huán)境平臺(tái),集群運(yùn)行模式采用本地模式“l(fā)ocal”。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中選擇了6個(gè)不平衡數(shù)據(jù)集,相關(guān)統(tǒng)計(jì)信息如表1所示。

表1 數(shù)據(jù)集描述

本文利用留出法(hold-out)按照4∶1的比例將原始數(shù)據(jù)集切分為訓(xùn)練集和測(cè)試集。通過算法1降低數(shù)據(jù)的IR為1,并利用Spark的并行計(jì)算機(jī)制將數(shù)據(jù)規(guī)模擴(kuò)充為15個(gè)數(shù)據(jù)子集。經(jīng)過預(yù)處理后的數(shù)據(jù)集相關(guān)統(tǒng)計(jì)信息如表2所示。

表2 經(jīng)過預(yù)處理后的數(shù)據(jù)集描述

3.2 實(shí)驗(yàn)評(píng)估指標(biāo)

在分類問題中,最常用的評(píng)價(jià)指標(biāo)為準(zhǔn)確度(Accuracy),但是該指標(biāo)無法反映出分類模型對(duì)不平衡數(shù)據(jù)中負(fù)類數(shù)據(jù)的學(xué)習(xí)能力。本文在混淆矩陣的基礎(chǔ)上采用查準(zhǔn)度(Precision)、特異度(Specificity)和G-均值(G-mean)指標(biāo)評(píng)估分類器對(duì)不平衡數(shù)據(jù)中正類數(shù)據(jù)和負(fù)類數(shù)據(jù)的學(xué)習(xí)能力,同時(shí)根據(jù)實(shí)驗(yàn)的運(yùn)行時(shí)間倆評(píng)估算法的計(jì)算性能。

查準(zhǔn)率的計(jì)算公式定義為

(26)

特異度的計(jì)算公式定義為

(27)

G均值的計(jì)算公式定義為

(28)

式(26～28)中:TP是真正例,TN是真反例,FP是假正例,FN是假反例。

3.3 實(shí)驗(yàn)結(jié)果與分析

為了檢驗(yàn)SENRPC算法在計(jì)算時(shí)間和分類方面的性能,本文基于6組UCI不平衡數(shù)據(jù)進(jìn)行了計(jì)算時(shí)間和分類性能方面的對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)中對(duì)比算法選取鄰域分類算法(Neighborhood classifier,NEC)[12]、證據(jù)鄰域分類算法(Evidence neighborhood classifier,ENEC)[14]、Spark框架下的鄰域并行分類算法(Parallel neighborhood classifier based on spark,SPNEC)。表3給出在相同數(shù)據(jù)規(guī)模下4種算法的計(jì)算時(shí)間值。

表3 計(jì)算時(shí)間 s

從表3可以看出,基于Spark框架的SPNEC和SENRPC兩種算法的計(jì)算時(shí)間遠(yuǎn)小于另外兩種傳統(tǒng)算法NEC和ENEC,而且在一定范圍內(nèi)隨著數(shù)據(jù)規(guī)模的增大,減少的計(jì)算時(shí)間也越大。這表明通過Spark并行計(jì)算機(jī)制可以有效地提高NEC和ENEC兩種算法的計(jì)算效率,減少其計(jì)算時(shí)間。因?yàn)镋NEC算法在分類過程中需要計(jì)算鄰域樣本之間的融合證據(jù)支持信息,所以其計(jì)算時(shí)間會(huì)比NEC算法多一些。同時(shí),SENRPC算法并行融合鄰域空間內(nèi)的證據(jù)支持信息的時(shí)間少于ENEC算法,這表明SENRPC算法減少了計(jì)算證據(jù)支持信息的時(shí)間。

從圖3和圖4可以看出,在大部分?jǐn)?shù)據(jù)集上,SENRPC算法的查準(zhǔn)率和特異度指標(biāo)性能遠(yuǎn)優(yōu)于傳統(tǒng)的NEC和ENEC兩種算法,Precision值基本在80%以上且最終趨向于穩(wěn)定,Specificity值基本在60%以上且最終趨向于穩(wěn)定。這表明了SENRPC算法加強(qiáng)了模型對(duì)負(fù)類樣本的學(xué)習(xí)能力,提高了模型對(duì)負(fù)類樣本的分類性能。

圖3 分類查準(zhǔn)率比較

圖4 分類特異度比較

從圖4可以看出,在WPBC和ILP這兩個(gè)數(shù)據(jù)集上,傳統(tǒng)的兩種算法NEC和ENEC的特異度性能隨著鄰域半徑的增大最終趨向于0,這表明NEC和ENEC兩種算法對(duì)負(fù)類樣本的學(xué)習(xí)能力減弱,無法對(duì)負(fù)類樣本準(zhǔn)確分類;在DRD數(shù)據(jù)集上,隨著鄰域半徑的增大,鄰域空間內(nèi)的正類樣本增多,NEC算法的分類精度降低,而ENEC算法的分類精度不斷提高并趨向于穩(wěn)定。

從圖5可以看出,針對(duì)大部分?jǐn)?shù)據(jù)集SENRPC算法在G-均值指標(biāo)上的性能遠(yuǎn)優(yōu)于其余的3種算法,G-mean值基本在60%以上且最終趨向于穩(wěn)定。這表明SENRPC算法對(duì)于數(shù)據(jù)樣本中正、負(fù)類樣本的綜合分類性能是4種算法中最優(yōu)。

圖5 分類G均值比較

綜上可知,本文SENRPC算法可以刪除大規(guī)模數(shù)據(jù)中的冗余屬性,降低數(shù)據(jù)規(guī)模和計(jì)算時(shí)間,提高計(jì)算效率。同時(shí),本文SENRPC算法對(duì)不平衡數(shù)據(jù)的分類性能良好,可以提高模型對(duì)不平衡數(shù)據(jù)整體分布的學(xué)習(xí)能力和分類性能。

4 結(jié)束語

本文首先針對(duì)大規(guī)模數(shù)值型數(shù)據(jù),將Spark并行計(jì)算機(jī)制與基于鄰域決策錯(cuò)誤率的屬性約簡算法進(jìn)行結(jié)合,實(shí)現(xiàn)了并行鄰域?qū)傩约s簡算法,降低屬性約簡的計(jì)算時(shí)間。然后,針對(duì)多數(shù)投票機(jī)制的不足之處,將證據(jù)理論引入鄰域分類器,實(shí)現(xiàn)了基于Spark的鄰域證據(jù)并行分類算法并行融合決策過程中的證據(jù)支持信息。最后,在主節(jié)點(diǎn)上通過Reduce操作聚合所有子節(jié)點(diǎn)的預(yù)測(cè)類別標(biāo)簽得到最終的預(yù)測(cè)類別標(biāo)簽。本文提出的SENRPC算法能夠刪除大規(guī)模數(shù)據(jù)中的冗余屬性,降低數(shù)據(jù)規(guī)模,減少數(shù)據(jù)之間的不確定性;在分類過程中,并行融合鄰域空間中類內(nèi)樣本和類間樣本之間的證據(jù)支持信息,得到更精確的分類結(jié)果。但是,在部分?jǐn)?shù)據(jù)集上,現(xiàn)有的D-S證據(jù)理論組合方式對(duì)分類精度提升不多,如何通過更好的D-S證據(jù)理論組合方式融合整個(gè)鄰域空間的證據(jù)支持信息提高模型的分類精度是本文接下來需要深入研究的問題。