龔健虎，張躍進(jìn)

(1.廣東培正學(xué)院 數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院，廣東 廣州 510830；2.華東交通大學(xué) 信息工程學(xué)院，江西 南昌 330013)

0 引 言

目前，大數(shù)據(jù)領(lǐng)域主要面臨著收集并處理大量數(shù)據(jù)的挑戰(zhàn)和優(yōu)勢，但對于大多數(shù)高級數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)工具來說，從大數(shù)據(jù)中提取信息特征且時(shí)間精準(zhǔn)分類較為困難[1,2]。

為此，國內(nèi)外學(xué)者進(jìn)行了大量研究。文獻(xiàn)[3]使用基于圖形的體系結(jié)構(gòu)和內(nèi)存大數(shù)據(jù)工具降低了輸入/輸出成本，但其運(yùn)行效率較低。文獻(xiàn)[4,5]利用并行粒子群優(yōu)化反向傳播神經(jīng)網(wǎng)絡(luò)，改善了社交媒體用戶的分類，但其分類精度較低。文獻(xiàn)[6]提出了一種基于半監(jiān)督支持向量機(jī)的分類算法，降低了環(huán)境變化導(dǎo)致的計(jì)算復(fù)雜度，但其魯棒性有待提高。

為了解決魯棒性問題，文獻(xiàn)[7]利用隨機(jī)森林分類器結(jié)合數(shù)據(jù)集屬性對數(shù)據(jù)進(jìn)行分類，提高了分類精度，但耗時(shí)較長。文獻(xiàn)[8,9]中采用基于橫斷面的研究方法和多級框架最大化填補(bǔ)方法均提高了數(shù)據(jù)分類準(zhǔn)確性，但面臨昂貴的成本問題。此外，對于分類效率的研究，也有大量有效的方法提出，例如Dirichlet分類方法[10]、分布式KNN分類方法[11]和迭代式數(shù)據(jù)均衡分區(qū)方法[12]，但其分類精度仍有待提高。

由此，可看出在云計(jì)算大數(shù)據(jù)分類領(lǐng)域中，目前還沒能有一種算法能夠在保證較高的大數(shù)據(jù)分類精度的同時(shí)還能具有較高的大數(shù)據(jù)分類效率[13,14]。針對上述問題，提出了深度屬性加權(quán)貝葉斯(attribute weighted Bayesian，AWB)算法結(jié)合改進(jìn)差別信息樹(differential information tree，DIT)的高效云計(jì)算大數(shù)據(jù)模糊分類方法，主要?jiǎng)?chuàng)新點(diǎn)總結(jié)如下：

(1)許多現(xiàn)有的大數(shù)據(jù)分類方法通常過度依賴分類器，而提出的分類方法利用深度ABW算法[15]進(jìn)行屬性加權(quán)，構(gòu)建基于語言模糊屬性的冠狀模糊MapReduce框架(language fuzzy attributes based canopy fuzzy MapReduce，LFA-CFM)，將云計(jì)算大數(shù)據(jù)分類為獨(dú)立塊，提高了云計(jì)算大數(shù)據(jù)分類的精度；

(2)現(xiàn)有的大多數(shù)方法較少注重大數(shù)據(jù)分類的效率，而提出的方法利用改進(jìn)DIT[16]實(shí)現(xiàn)模糊粗糙集屬性約簡，將大數(shù)據(jù)屬性的數(shù)量設(shè)置為單獨(dú)的目標(biāo)函數(shù)，有利于提高大數(shù)據(jù)分類的效率；

(3)現(xiàn)有的大數(shù)據(jù)分類方法常常難以同時(shí)提高分類的精確度和效率，而提出的方法將深度AWB算法和改進(jìn)DIT相結(jié)合，在提高大數(shù)據(jù)分類精確度的同時(shí)還提高了大數(shù)據(jù)分類的效率。

1 提出的大數(shù)據(jù)分類方法

1.1 改進(jìn)屬性加權(quán)算法

改進(jìn)屬性加權(quán)算法由多個(gè)不同步驟組成。圖1顯示了改進(jìn)屬性加權(quán)算法的詳細(xì)執(zhí)行流程。

圖1 改進(jìn)屬性加權(quán)算法的執(zhí)行流程

改進(jìn)屬性加權(quán)算法首先從數(shù)據(jù)庫中建立多個(gè)數(shù)據(jù)塊，然后，對數(shù)據(jù)塊進(jìn)行樣本測試和樣本訓(xùn)練，緊接著，對其施加深度屬性加權(quán)貝葉斯算法[17]，然后設(shè)置分類正確率權(quán)重，并建立自適應(yīng)集成策略，而后則是優(yōu)化集成和組合投票策略[18]，設(shè)置置信度權(quán)重，并得到預(yù)測分類結(jié)果。

在n個(gè)云服務(wù)上以并行方式執(zhí)行改進(jìn)屬性加權(quán)算法，使用如圖1所示的執(zhí)行流程，在屬性加權(quán)算法中還需3個(gè)隱含操作。第一個(gè)操作是由每個(gè)云用戶以并行方式部署的映射函數(shù)(具有更多數(shù)量的映射器)，而不與其它云用戶節(jié)點(diǎn)一起傳輸任何數(shù)據(jù)或信息。第二個(gè)操作是通過跨所有其它云用戶節(jié)點(diǎn)的映射函數(shù)處理數(shù)據(jù)或信息，而第三個(gè)操作是由每個(gè)云用戶以并行方式通過劃分?jǐn)?shù)據(jù)或信息部署的。第三個(gè)操作和最后一步是在云環(huán)境中進(jìn)行大數(shù)據(jù)分類。

1.2 利用改進(jìn)差別信息樹的粗糙集屬性約簡

為了約簡基于改進(jìn)差別樹信息集的粗糙集屬，首先需要設(shè)計(jì)LFA-CFM框架，LFA-CFM的功能是將原始大數(shù)據(jù)集分段，因此需要將其分類為獨(dú)立塊，并使用語言模糊屬性自動(dòng)地將獨(dú)立塊傳送到不同的處理單元(云服務(wù)器)。而設(shè)計(jì)LFA-CFM框架的第一步是構(gòu)建大數(shù)據(jù)集的模糊KB，其由數(shù)據(jù)庫(DB)中的模糊集信息、屬性和推理系統(tǒng)所組成[19]。在LFA-CFM中，數(shù)據(jù)庫中的信息是通過三角隸屬函數(shù)臨時(shí)獲得的，通過使用來自輸入示例的學(xué)習(xí)過程以提取屬性，提取過程如下：

屬性Rulei：

那么，分類結(jié)果Classi屬于Rsulti。

其中，屬性Rulei指定第i個(gè)屬性的標(biāo)簽Assei，其中Asse=(Asse1,Asse2,…,Assen)是具有屬性權(quán)重Rsulti的類標(biāo)簽Classi的前端模糊集合Packet1的維度向量。LFA-CFM框架中的屬性權(quán)重采用啟發(fā)式方法獲得，表示如下

(1)

式中：μPacketi(Assep)為(Assep)的隸屬函數(shù)，Classi為屬性i確定的類。根據(jù)屬性和屬性權(quán)重，在LFA-CFM中部署了大數(shù)據(jù)集的模糊KB。

在傳統(tǒng)的粗糙集屬性約簡中，映射函數(shù)以鍵/值對的形式處理輸入，而鍵/值對又通過洗牌操作生成中級鍵/值對[20]。而粗糙集約簡算法的主要思想是云用戶在其可用數(shù)據(jù)上獨(dú)立操作每個(gè)處理單元，以在云環(huán)境中建立相關(guān)KB(關(guān)聯(lián)模糊屬性Ri)進(jìn)行模糊屬性分類，并且利用執(zhí)行洗牌減少云用戶之間映射的運(yùn)行時(shí)間。

LFA-CFM框架設(shè)計(jì)的第二步是設(shè)計(jì)用于構(gòu)建模糊KB的冠狀模糊MapReduce算法。為了處理云環(huán)境中的大數(shù)據(jù)分類和信息共享，LFA-CFM使用粗糙集屬性約簡實(shí)現(xiàn)快速搬運(yùn)，而該約簡方法包含語言模糊屬性，使用模糊集同化和融合屬性庫。

設(shè)定評估兩個(gè)先行模糊集KB和KBi之間的差異Diff，先初始化兩個(gè)映射閾值因子Thrd1和Thrd2，然后將其與冠狀中心獲得的距離相比較，以減少最小化過程所需的時(shí)間，表述如下

(2)

LFA-CFM框架設(shè)計(jì)的最后是從相關(guān)的模糊屬性Rulei中去除冗余屬性，并在不同結(jié)果下，僅保留具有最高屬性權(quán)重Rsulti的屬性。在此基礎(chǔ)上，組合所有由映射過程計(jì)算得到的Rulei值以獲得最終分類，并減小屬性集的大小。其中洗牌算法[21]的具體執(zhí)行過程如圖2所示。

圖2 洗牌算法的執(zhí)行流程

洗牌算法的具體執(zhí)行流程闡述如下：

輸入數(shù)據(jù)集、映射閾值因子Thrd1和Thrd2、云服務(wù)器TC=TC1,TC2,…,TCn、云主節(jié)點(diǎn)YZmn和云工作節(jié)點(diǎn)Ywn。

步驟1 對于距離為KB和KBi的每個(gè)數(shù)據(jù)集和每個(gè)云主節(jié)點(diǎn)YZmn、云工作節(jié)點(diǎn)Ywn，初始化映射閾值因子Thrd1和Thrd2；

步驟2 使用式(1)執(zhí)行屬性提取，使用式(2)測量屬性權(quán)重；

步驟3 測量KB和KBi之間的距離，執(zhí)行洗牌。如果Diff

從圖3中可看出，洗牌過程是平行進(jìn)行的。由于該算法允許多個(gè)云用戶同時(shí)執(zhí)行，因此能夠減少云用戶之間映射的執(zhí)行時(shí)間。洗牌算法的基本過程分為兩部分：第一部分是獲得輸入映射閾值因子Thrd1，以及通過洗牌操作去除冠狀中心；第二部分是根據(jù)得到的測量距離，利用大數(shù)據(jù)計(jì)算進(jìn)行分類，以減少執(zhí)行時(shí)間，很大程度上提高了大數(shù)據(jù)分類的效率。

圖3 大數(shù)據(jù)混合模糊分類框架

1.3 大數(shù)據(jù)混合模糊分類模型

利用深度屬性加權(quán)貝葉斯算法模糊KB和改進(jìn)差別信息樹模糊粗糙集屬性算法，給出了云環(huán)境下大數(shù)據(jù)和信息共享的混合分類系統(tǒng)。利用數(shù)據(jù)約簡的模糊粗糙屬性算法，再利用基于模糊屬性的分類來以較少的迭代次數(shù)對大數(shù)據(jù)進(jìn)行分類。圖3顯示了大數(shù)據(jù)的混合模糊分類模型。因?yàn)檩斎雽傩詭焓嵌喾N多樣的，因此該模型產(chǎn)生不同的分類評估。

在最后一步中，洗牌算法的計(jì)算結(jié)果作為計(jì)算過程的輸出。最后，把大數(shù)據(jù)分類集的不同示例的類聚合在一起，附加每個(gè)映射任務(wù)提供的結(jié)果。

2 實(shí)驗(yàn)設(shè)置與性能評估

2.1 實(shí)驗(yàn)環(huán)境

使用CloudSim仿真器對提出的算法進(jìn)行了模擬，對提到的LFA-CFM框架的效率進(jìn)行測量和評估。為測量LFA-CFM框架的性能，實(shí)驗(yàn)采用Java語言進(jìn)行編程，對Amazon EC2 Cloud Stanford大型網(wǎng)絡(luò)數(shù)據(jù)集集合進(jìn)行實(shí)驗(yàn)。

應(yīng)用于云環(huán)境的CloudSim仿真器為多個(gè)虛擬機(jī)提供了不同的資源配置。在模擬時(shí)，為提出的LFA-CFM框架配備兩個(gè)四核2.33-2.66 GHz xeon處理器(總共8個(gè)核心)，7 GB RAM和4096 GB本地磁盤存儲。大數(shù)據(jù)的大小在1 GB到200 GB之間變化，并且所采用的實(shí)例數(shù)量在1到5的范圍內(nèi)。通過模擬可以說明不同大小的大數(shù)據(jù)的參數(shù)即：運(yùn)行時(shí)間、分類時(shí)間、分類準(zhǔn)確性和輸入/輸出成本帶來的影響。

LFA-CFM框架利用CloudSim仿真器在Java中實(shí)現(xiàn)云用戶和云服務(wù)器之間大數(shù)據(jù)分類。在云計(jì)算環(huán)境中識別云用戶和云服務(wù)器，以在云計(jì)算環(huán)境中進(jìn)行大數(shù)據(jù)分類?？梢酝ㄟ^運(yùn)行時(shí)間、分類時(shí)間、分類準(zhǔn)確度和輸入/輸出成本來測量LFA-CFM框架的性能。

2.2 實(shí)驗(yàn)參數(shù)定義

(1)運(yùn)行時(shí)間

生成屬性所花費(fèi)的時(shí)間的度量是運(yùn)行時(shí)間，包括獲得屬性權(quán)重所花費(fèi)的測量時(shí)間。隨著生成屬性的增加，最小運(yùn)行時(shí)間得不到保證。運(yùn)行時(shí)的性能以毫秒(ms)為單位進(jìn)行測量，并以式(3)表示

Trun(ms)=T(Rulei)+T(Rsulti)

(3)

從上式中可以看出，使用屬性Rulei和屬性權(quán)重Rsulti獲得運(yùn)行時(shí)間。當(dāng)運(yùn)行時(shí)間較小時(shí)，該方法更有效。

(2)分類時(shí)間

在云環(huán)境下的大數(shù)據(jù)集中，分類時(shí)間測量訓(xùn)練集中的所有實(shí)例所需的時(shí)間。為了最小化分類時(shí)間，LFA-CFM框架在云環(huán)境中對訓(xùn)練集的所有實(shí)例進(jìn)行分類?？梢员硎緸?/p>

Tclass(ms)=DSi×tclass

(4)

從上式中看出，分類時(shí)間Tclass是針對不同實(shí)例的訓(xùn)練集DSi以毫秒為單位測量的。當(dāng)分類時(shí)間較短時(shí)，該方法更有效。

(3)分類準(zhǔn)確度

在分類的訓(xùn)練數(shù)據(jù)集中正確分類的全體大數(shù)據(jù)實(shí)例數(shù)就是分類的準(zhǔn)確度。訓(xùn)練數(shù)據(jù)集i中單個(gè)實(shí)例的分類準(zhǔn)確度Accuracyi是由正確分類的數(shù)據(jù)的數(shù)量決定的，并用百分比(%)來衡量，并由式(5)中的公式進(jìn)行評估

(5)

其中，Dataright表示正確分類的數(shù)據(jù)數(shù)量，Ntotal是考慮用于評估和測量分類準(zhǔn)確度的數(shù)據(jù)總數(shù)。當(dāng)分類精度更高時(shí)，該方法更有效。

(4)成本

LFA-CFM框架中，在更高分類準(zhǔn)確度的條件下，輸入/輸出成本測量的是云用戶之間共享信息所花費(fèi)的時(shí)間。輸入/輸出成本的單位為毫秒，當(dāng)輸入/輸出成本較低時(shí)，該方法更有效。

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

(1)運(yùn)行時(shí)間

表1給出了運(yùn)行時(shí)間的模擬結(jié)果，當(dāng)數(shù)據(jù)容量為1 GB時(shí)，運(yùn)行時(shí)間約為10.6 ms，當(dāng)數(shù)據(jù)容量為10 GB時(shí)，運(yùn)行時(shí)間約為50.2 ms，當(dāng)數(shù)據(jù)容量為50 GB時(shí)，運(yùn)行時(shí)間約為124.3 ms，當(dāng)數(shù)據(jù)容量為100 GB時(shí)，運(yùn)行時(shí)間約為256.5 ms，當(dāng)數(shù)據(jù)容量為200 GB時(shí)，運(yùn)行時(shí)間約為521.6 ms，可以看出，隨著數(shù)據(jù)容量的不斷增加，提出算法的運(yùn)行時(shí)間也會與之相應(yīng)地增加。

表1 運(yùn)行時(shí)間的列表

由于隨著數(shù)據(jù)容量的增加，運(yùn)行時(shí)間也會增加，因此，該算法在進(jìn)行較小容量數(shù)據(jù)分類時(shí)具有更高的時(shí)間效率。

(2)分類時(shí)間

表2給出了不同數(shù)據(jù)容量下，提出算法的分類時(shí)間。當(dāng)數(shù)據(jù)容量為1 GB時(shí)，分類時(shí)間最少，僅有6.7 ms；當(dāng)數(shù)據(jù)容量為10 GB時(shí)，分類時(shí)間約為42.3 ms；當(dāng)數(shù)據(jù)容量為50 GB時(shí)，分類時(shí)間約為98.8 ms；當(dāng)數(shù)據(jù)容量為100 GB時(shí)，分類時(shí)間約為192.4 ms；當(dāng)數(shù)據(jù)容量為200 GB時(shí)，分類時(shí)間約為429.2 ms。

表2 分類時(shí)間的列表

從表2中可以看出，當(dāng)容量為1 GB時(shí)，分類時(shí)間最短，隨著數(shù)據(jù)容量的增加，分類時(shí)間會隨之增加。

(3)分類準(zhǔn)確度

表3給出了不同數(shù)據(jù)容量下，提出算法的分類準(zhǔn)確度。當(dāng)數(shù)據(jù)容量為1 GB時(shí)，數(shù)據(jù)分類的準(zhǔn)確度最高，可達(dá)99.93%；當(dāng)數(shù)據(jù)容量為10 GB時(shí)，數(shù)據(jù)分類準(zhǔn)確度約為99.12%；當(dāng)數(shù)據(jù)容量為50 GB時(shí)，數(shù)據(jù)分類準(zhǔn)確度約為91.23%；當(dāng)數(shù)據(jù)容量為100 GB時(shí)，數(shù)據(jù)分類準(zhǔn)確度約為85.34%；當(dāng)數(shù)據(jù)容量為200 GB時(shí)，數(shù)據(jù)分類準(zhǔn)確度約為79.52%。

表3 分類準(zhǔn)確度的列表

從表3中可以看出，當(dāng)容量為1 GB時(shí)，分類準(zhǔn)確度最高，最高可達(dá)99.93%，隨著數(shù)據(jù)容量的增加，分類準(zhǔn)確度會隨之降低。

(4)成本

表4給出了在不同數(shù)據(jù)容量下，提出算法中云用戶之間共享信息所花費(fèi)的時(shí)間。

表4 云用戶之間共享信息所花費(fèi)的時(shí)間

當(dāng)數(shù)據(jù)容量為1 GB時(shí)，云用戶間共享信息所花費(fèi)的時(shí)間最少，為5.4 ms；當(dāng)數(shù)據(jù)容量為10 GB時(shí)，云用戶間共享信息所花費(fèi)的時(shí)間為39.1 ms；當(dāng)數(shù)據(jù)容量為50 GB時(shí)，云用戶間共享信息所花費(fèi)的時(shí)間為97.6 ms；當(dāng)數(shù)據(jù)容量為100 GB時(shí)，云用戶間共享信息所花費(fèi)的時(shí)間為185.9 ms；當(dāng)數(shù)據(jù)容量為200 GB時(shí)，云用戶間共享信息所花費(fèi)的時(shí)間為407.2 ms。從表4中可以看出，隨著容量的增大，云用戶共享信號的時(shí)間越多。

2.4 與其它方法的對比和分析

將所提方法與文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中方法在運(yùn)行時(shí)間、分類時(shí)間、分類準(zhǔn)確度和歸一化成本這4個(gè)方面進(jìn)行對比分析。

(1)運(yùn)行時(shí)間

所提分類方法與文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中方法的運(yùn)行時(shí)間比較如圖4所示。

圖4 運(yùn)行時(shí)間對比

從上圖中可以看出，所提分類算法的運(yùn)行時(shí)間相比于文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]的算法，整體上的運(yùn)行時(shí)間更少，但在數(shù)據(jù)容量為1 GB和10 GB時(shí)，提出算法的運(yùn)行時(shí)間會稍高于文獻(xiàn)[5]中提出算法的運(yùn)行時(shí)間。當(dāng)數(shù)據(jù)容量為50 GB、100 GB和200 GB時(shí)，提出算法的運(yùn)行時(shí)間明顯低于文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中的運(yùn)行時(shí)間。

(2)分類時(shí)間

提出算法的分類時(shí)間與文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中算法的分類時(shí)間的對比結(jié)果如圖5所示。

圖5 分類時(shí)間的對比

從上圖中可以看出，所提出分類算法的運(yùn)行時(shí)間相比于文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]的算法，整體上的分類時(shí)間更少。當(dāng)數(shù)據(jù)容量較小時(shí)，提出的算法和文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中的算法的分類時(shí)間也較小，以1 GB為例，所提方法與文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中算法的分類時(shí)間依次是6.7 ms、8.2 ms、8.9 ms和25.1 ms。當(dāng)數(shù)據(jù)容量較大時(shí)，提出的算法和文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中的算法的分類時(shí)間會隨之增大，即分類時(shí)間均會隨著所需要分類數(shù)據(jù)的容量的增加而增加，但所提方法分類時(shí)間增長得相對較少。

(3)分類準(zhǔn)確度

所提算法與文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中算法的準(zhǔn)確度對比如圖6所示。

圖6 分類準(zhǔn)確度的對比

從上圖中可以看出，隨著數(shù)據(jù)容量的增加，4種算法的分類準(zhǔn)確度均會逐漸降低，但是，相比于文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中的算法，提出的算法整體上的大數(shù)據(jù)分類準(zhǔn)確度更高，即使容量到200 GB，其分類準(zhǔn)確度不低于80%，而其它算法已接近60%。

(4)成本

提出算法與文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中的算法的歸一化成本對比如圖7所示。

圖7 歸一化成本的對比

從圖7中可以看出，當(dāng)需要分類的數(shù)據(jù)容量越小時(shí)，所花費(fèi)的成本就越小，歸一化成本會隨著云計(jì)算大數(shù)據(jù)的容量的增加而增加。但在提出算法、文獻(xiàn)[3]、文獻(xiàn)[5]和文獻(xiàn)[7]中的算法中，提出的算法的歸一化成本更低，當(dāng)容量為1 GB時(shí)，其歸一化成本僅為0.05，當(dāng)容量為200 GB時(shí)，其歸一化成本為1.0，均低于其它算法，更加利于實(shí)際應(yīng)用。

3 結(jié)束語

提出了一種深度屬性加權(quán)貝葉斯算法結(jié)合改進(jìn)差別信息樹模糊粗糙集屬性約簡的高效云計(jì)算大數(shù)據(jù)模糊分類方法，研究了云計(jì)算大數(shù)據(jù)準(zhǔn)確、高效分類的問題。提出的算法提高了云計(jì)算大數(shù)據(jù)分類的準(zhǔn)確性，降低了大數(shù)據(jù)分類的計(jì)算時(shí)間，提高了分類效率，降低了大數(shù)據(jù)分類的成本。

下一步的研究重點(diǎn)包括兩點(diǎn)：一是通過研究適合于更大規(guī)模大數(shù)據(jù)分類的智能算法；二是進(jìn)一步提高云計(jì)算大數(shù)據(jù)在數(shù)據(jù)分類上所花銷的時(shí)間和成本，提高大數(shù)據(jù)分類的效率和效益。