基于對(duì)稱矩陣的云計(jì)算和信息共享預(yù)測(cè)分類器

王 騰，高秋生，王立瑋

(國(guó)網(wǎng)河北省電力公司信息通信分公司，河北 石家莊 050021)

0 引 言

大數(shù)據(jù)應(yīng)用和研究的主要目標(biāo)就是從海量大數(shù)據(jù)中提取有效信息或分析數(shù)據(jù)并預(yù)測(cè)未來(lái)發(fā)展趨勢(shì)[1]。目前主要以并行計(jì)算方式進(jìn)行大數(shù)據(jù)的分析，而云計(jì)算環(huán)境已經(jīng)成為大數(shù)據(jù)分析常用的并行分布式計(jì)算系統(tǒng)。為提高云計(jì)算環(huán)境中的安全性和信息隱私，文獻(xiàn)[2]使用異構(gòu)自動(dòng)復(fù)雜演化定理進(jìn)行大數(shù)據(jù)挖掘，并利用Flex Analytics方法增強(qiáng)數(shù)據(jù)傳輸寬帶[3]。上述兩種方法都沒(méi)有解決空間和時(shí)間復(fù)雜度問(wèn)題，使得大數(shù)據(jù)挖掘的效率較低，無(wú)法直接應(yīng)用在實(shí)際數(shù)據(jù)挖掘中。本文提出一種PSM-PBC方法，對(duì)云環(huán)境下的大數(shù)據(jù)進(jìn)行計(jì)算和信息共享[4]。該方法主要包括3個(gè)過(guò)程。首先，以并行方式對(duì)分布式大數(shù)據(jù)構(gòu)建三角對(duì)稱矩陣，該步驟通過(guò)Householder變換可以提高云環(huán)境下數(shù)據(jù)的提取和共享速率。其次，利用交叉驗(yàn)證貝葉斯分類器對(duì)用戶請(qǐng)求的實(shí)值對(duì)角數(shù)據(jù)查詢結(jié)果進(jìn)行評(píng)估，該步驟可以提高預(yù)測(cè)率。最后，利用貝葉斯類改進(jìn)的MapReduce函數(shù)提高數(shù)據(jù)的預(yù)測(cè)分析，從而更好地計(jì)算和信息共享[5,6]。

1 基于并行對(duì)稱矩陣的貝葉斯預(yù)測(cè)分類器

本文提出PSM-PBC模型用來(lái)在云計(jì)算環(huán)境中對(duì)大數(shù)據(jù)進(jìn)行高效的計(jì)算和信息共享。在PSM-PBC模型中，利用三角對(duì)稱矩陣更快的提取數(shù)據(jù)和信息共享，同時(shí)提高搜索精度。而交叉驗(yàn)證貝葉斯分類器對(duì)用戶請(qǐng)求的結(jié)果進(jìn)行評(píng)估，以提高預(yù)測(cè)率[7]。PSM-PBC模型中的MapReduce用于減少大數(shù)據(jù)的空間和計(jì)算復(fù)雜度。PSM-PBC模型如圖1所示。

圖1 PSM-PBC模型結(jié)構(gòu)

1.1 三角對(duì)稱矩陣的構(gòu)造

現(xiàn)有的傳統(tǒng)方法無(wú)法對(duì)用戶收集的原始數(shù)據(jù)進(jìn)行模式和相關(guān)性識(shí)別，而這種模式和關(guān)系在外貿(mào)企業(yè)、政府等機(jī)構(gòu)的決策中有很大的幫助作用。PSM-PBC模型對(duì)分布式大數(shù)據(jù)進(jìn)行并行對(duì)稱矩陣運(yùn)算提高數(shù)據(jù)提取的計(jì)算率。假定在云環(huán)境中并行分布有CNi個(gè)云節(jié)點(diǎn)，并且云節(jié)點(diǎn)間的計(jì)算時(shí)間由M×N矩陣形式表示，其中CTij表示云節(jié)點(diǎn)i和云節(jié)點(diǎn)j之間的計(jì)算時(shí)間[8]。根據(jù)對(duì)稱矩陣的性質(zhì)，有CTij=CTji，即

(1)

式中：CTi用于表示云節(jié)點(diǎn)i和云節(jié)點(diǎn)j之間的計(jì)算時(shí)間矢量V。隨著數(shù)據(jù)量的快速增長(zhǎng)，影響數(shù)據(jù)應(yīng)用的因素主要是時(shí)間復(fù)雜度(如完成算法所需的時(shí)間量)和空間復(fù)雜度(如算法運(yùn)行所需的存儲(chǔ)量)。PSM-PBC模型利用對(duì)稱矩陣對(duì)大數(shù)據(jù)進(jìn)行實(shí)值對(duì)角搜索，并使之并行分布在整個(gè)云空間[9]。圖2給出了利用Householder變換構(gòu)建三角對(duì)稱矩陣的過(guò)程。

圖2 三對(duì)角矩陣的構(gòu)造過(guò)程

從圖2可以看出Householder變換利用實(shí)值對(duì)角搜索算法將M×N矩陣變換為三對(duì)角模型。PSM-PBC模型中的Householder變換矩陣如下

HT=1-2V×VT

(2)

而HT2可以通過(guò)如下計(jì)算得到

HT2=(1-2V×VT)×(1-2V×VT)=
(1)-(4V×VT)+4V×(V×VT)×VT=
(1)-(4V×VT)+(4V×VT)=1

(3)

在PSM-PBC模型中使用Householder變換的主要目標(biāo)是對(duì)大數(shù)據(jù)執(zhí)行多種學(xué)習(xí)策略，提高搜索精度，并減少時(shí)間和空間復(fù)雜性。PSM-PBC模型中的矩陣對(duì)角搜索的二Householder變換的數(shù)學(xué)表述如下

(4)

式中：左上角的單位矩陣保證了三對(duì)角化。由于Householder變換矩陣插入了一個(gè)額外的行和列，因此，通過(guò)三對(duì)角搜索可以加快分布式大數(shù)據(jù)對(duì)稱矩陣的計(jì)算速度。

1.2 交叉驗(yàn)證貝葉斯分類器模型的設(shè)計(jì)

PSM-PBC模型中的第2步操作就是利用貝葉斯模型對(duì)用戶請(qǐng)求進(jìn)行實(shí)值對(duì)角搜索，并對(duì)結(jié)果進(jìn)行有效分類[10]。假定考慮幾個(gè)用戶請(qǐng)求，那么類隸屬函數(shù)或隸屬函數(shù)的后驗(yàn)概率如下

(5)

(6)

在云平臺(tái)下，PSM-PBC模型在迭代“i”中選擇的用戶請(qǐng)求集由向量“vi”表示。PSM-PBC模型適用于全局和局部與云平臺(tái)的交叉學(xué)習(xí)策略，用于驗(yàn)證貝葉斯分類器。從式(7)，選擇最佳值，通過(guò)交叉驗(yàn)證大數(shù)據(jù)的情況下，下面的數(shù)學(xué)公式，然后進(jìn)行驗(yàn)證

(7)

1.3 基于貝葉斯類的MapReduce函數(shù)

PSM-PBC模型最后是對(duì)MapReduce函數(shù)的應(yīng)用，該方法已經(jīng)用來(lái)為商業(yè)社區(qū)和政府組織提供大數(shù)據(jù)預(yù)測(cè)分析，可以實(shí)現(xiàn)有效的計(jì)算和信息共享[11-13]。本文中利用MapReduce函數(shù)來(lái)分析貝葉斯分類器對(duì)用戶請(qǐng)求關(guān)鍵字進(jìn)行分類。在PSM-PBC模型設(shè)計(jì)的最后階段是MapReduce函數(shù)的應(yīng)用。MapReduce函數(shù)法應(yīng)用于從搜索數(shù)據(jù)的貝葉斯類。這種方法是由企業(yè)界和政府機(jī)構(gòu)提供預(yù)測(cè)分析的大數(shù)據(jù)，并進(jìn)行有效計(jì)算和信息共享化。在PSM-PBC貝葉斯類模型運(yùn)用假定某些特征的存在或不存在的指示。在我們的PSM-PBC模型，貝葉斯分類fiER的百分比用戶討論分類是使用MapReduce函數(shù)。

隨著數(shù)百萬(wàn)數(shù)量級(jí)用戶的產(chǎn)生，由于速度和可擴(kuò)展性，傳統(tǒng)的分類技術(shù)無(wú)法應(yīng)用。為了解決這一問(wèn)題的空間復(fù)雜性，大數(shù)據(jù)的并行編程模型中使用的PSM-PBC模型顯著提高了運(yùn)算速度和降低空間復(fù)雜度。在PSM-PBC模型Map-Reduce函數(shù)以并行方式處理大數(shù)據(jù)。最初從用戶請(qǐng)求獲得的原始數(shù)據(jù)被饋送到map函數(shù)中。map函數(shù)以鍵值對(duì)作為輸入，輸出中間鍵值對(duì)。工作分配到一個(gè)精確的數(shù)字地圖的任務(wù)是使用Apache Hadoop框架進(jìn)行。

所有的云節(jié)點(diǎn)執(zhí)行類似的計(jì)算，在地圖設(shè)計(jì)中，廣泛使用地方的數(shù)據(jù)，以減少空間的復(fù)雜性。成功地完成映射后，從幾個(gè)云節(jié)點(diǎn)獲得的中間結(jié)果最小化，以產(chǎn)生所得到的輸出。該P(yáng)SM-PBC模型使用Apache Hadoop框架依靠MapReduce函數(shù)和Hadoop分布式文件系統(tǒng)進(jìn)行數(shù)據(jù)處理。

隨著數(shù)據(jù)種類的增多，空間復(fù)雜度增大，傳統(tǒng)的技術(shù)由于速度和可擴(kuò)展性的落后而逐漸被遺棄。為了解決空間復(fù)雜度問(wèn)題，PSM-PBC模型采用并行大數(shù)據(jù)編程模式來(lái)提高處理速度以及減少時(shí)間復(fù)雜度。對(duì)于MapReduce過(guò)程，首先將得到的用戶請(qǐng)求數(shù)據(jù)饋送到映射函數(shù)中，映射函數(shù)使用鍵值對(duì)作為輸入，并輸出中間鍵值對(duì)。本文任務(wù)在Apache Hadoop框架下執(zhí)行，所有云節(jié)點(diǎn)的映射設(shè)計(jì)都廣泛采用類似計(jì)算以降低空間復(fù)雜度。然后將云節(jié)點(diǎn)的中間結(jié)果最小化后作為結(jié)果輸出。Apache Hadoop框架就是由MapReduce函數(shù)和Hadoop分布式文件系統(tǒng)(HDFS)進(jìn)行數(shù)據(jù)處理[13]。映射(Map)的主要目的就是將從貝葉斯類得到的類、屬性和值等作為輸入轉(zhuǎn)換為鍵值對(duì)，其流程如下所示

Map(x)→(Key,Value)

(8)

(Key)→(Class,Attributes)

(9)

Map操作將訓(xùn)練集中的關(guān)鍵字進(jìn)行標(biāo)記，并把類和對(duì)應(yīng)的關(guān)鍵字作為鍵值對(duì)輸出。規(guī)約(reduce)操作把鍵值進(jìn)行合并，最終以單鍵值對(duì)輸出，其中鍵是唯一的關(guān)鍵字組合[14]。通過(guò)分析用戶請(qǐng)求來(lái)分類關(guān)鍵字的MapReduce函數(shù)的框架，如圖3所示，描述了用于分類用戶請(qǐng)求的MapReduce函數(shù)，關(guān)鍵字最初被分成塊。然后，對(duì)關(guān)鍵字塊與包含用戶共享文件信息的每個(gè)函數(shù)進(jìn)行映射。最后文件在多個(gè)云節(jié)點(diǎn)進(jìn)行并行處理，這比在單云節(jié)點(diǎn)上進(jìn)行仿真實(shí)驗(yàn)效果更好。

圖3 MapReduce過(guò)程框架

下面給出描述了貝葉斯類的MapReduce算法的偽代碼。

初始化：關(guān)鍵字→貝葉斯類

輸出：約束功能

步驟1 Begin

步驟2 For 每類

步驟3 將該類分為n塊

步驟4 將n塊同時(shí)并行處理

步驟5 End for

步驟6 For 每個(gè)Map函數(shù)

步驟7 將每個(gè)Map函數(shù)分為n塊

步驟8 運(yùn)行Map函數(shù)

步驟9 聚合相似的類

步驟10 End for

步驟11 For 每個(gè)reducer

步驟12 結(jié)合Map函數(shù)和關(guān)鍵字作為輸出

步驟13 End for

步驟14 End

2 結(jié)果與討論

本文實(shí)驗(yàn)是在HDFS兩層命名空間進(jìn)行，HDFS為虛擬機(jī)實(shí)例分配不同的資源，其中每個(gè)虛擬機(jī)實(shí)例配置了特定數(shù)量的內(nèi)存、CPU和本地存儲(chǔ)器。PSM-PBC模型配有兩個(gè)雙核2.33-2.66 GHz Xeon處理器，7 GB RAM以及160 GB本地磁盤存儲(chǔ)器。PSM-PBC模型使用HDFS層命名空間來(lái)降低運(yùn)算的復(fù)雜度和計(jì)算成本。云計(jì)算服務(wù)首先識(shí)別出用戶的請(qǐng)求信息共享，然后做出最佳決策的數(shù)據(jù)和信息傳遞給其他的用戶，這樣信息沒(méi)有冗余。利用JAVA語(yǔ)言實(shí)現(xiàn)PSM-PBC模型，并從搜索精度、預(yù)測(cè)率、計(jì)算時(shí)間和空間復(fù)雜度4個(gè)方面進(jìn)行對(duì)比研究。

2.1 搜索精度的影響

表1中對(duì)PSM-PBC方法的搜索精度做了評(píng)估同時(shí)與DM-BD[2]和FlexAnalytics[3]兩個(gè)方法做了對(duì)比。為了說(shuō)明實(shí)驗(yàn)的有效性，本文數(shù)據(jù)的大小從200 GB到1400 GB范圍變化，其中，大數(shù)據(jù)的搜索精度用下式表示

(10)

式(10)中說(shuō)明，大數(shù)據(jù)的搜索精度SA由正確識(shí)別模式的百分比來(lái)體現(xiàn)。從表1數(shù)據(jù)可以看出，搜索精度隨大數(shù)據(jù)的增大而增加，且當(dāng)數(shù)據(jù)大小達(dá)到800 GB時(shí)，大數(shù)據(jù)的搜索精度趨于飽和狀態(tài)。

表1 搜索精度

圖4相應(yīng)給出了大數(shù)據(jù)搜索精度的折線表示，更直觀的說(shuō)明本文PSM-PBC模型優(yōu)于DM-BD和FlexAnalytics方法。其主要原因是本文模型使用三對(duì)角對(duì)稱矩陣識(shí)別重要模式和其相關(guān)性。相比之下，PSM-PBC搜索精度比DM-BD提高了13.42%，搜索準(zhǔn)確率比FlexAnalytics提高了17.68%。

圖4 搜索精度對(duì)比

2.2 預(yù)測(cè)率的影響

PSM-PBC模型通過(guò)考慮當(dāng)前數(shù)據(jù)和歷史預(yù)測(cè)用戶請(qǐng)求來(lái)最大化預(yù)測(cè)率。所謂預(yù)測(cè)就是從現(xiàn)有的用戶請(qǐng)求中提取信息，以便與其他用戶分享并預(yù)測(cè)未來(lái)的結(jié)果和趨勢(shì)，其數(shù)學(xué)公式如下

(11)

式(11)中，預(yù)測(cè)率PR通過(guò)結(jié)合當(dāng)前數(shù)據(jù)和歷史因素來(lái)體現(xiàn)。本實(shí)驗(yàn)中，數(shù)據(jù)大小從200 GB到1400 GB變化，見(jiàn)表2。本文對(duì)PSM-PBC的預(yù)測(cè)率同前面所提兩類方法進(jìn)行對(duì)比，表2數(shù)據(jù)說(shuō)明PSM-PBC模型優(yōu)于DM-BD和FlexAnalytics方法，主要原因是本文方法應(yīng)用了交叉驗(yàn)證的貝葉斯分類器，可以根據(jù)用戶的請(qǐng)求進(jìn)行分類。同樣地，從圖5中可以看出，本文預(yù)測(cè)率相比DM-DB提高了7.27%，比FlexAnalytics提高了13.83%。

表2 預(yù)測(cè)率

圖5 預(yù)測(cè)率對(duì)比

2.3 計(jì)算時(shí)間的影響

本文所提計(jì)算時(shí)間指在云環(huán)境中構(gòu)建一個(gè)有效計(jì)算和信息共享的貝葉斯MapReduce函數(shù)所需的時(shí)間，以毫秒(ms)計(jì)，數(shù)學(xué)表示如下

CT=Time(Map(n))

(12)

表3顯示了計(jì)算時(shí)間與放置實(shí)例數(shù)的關(guān)系，其中實(shí)例從5到35個(gè)。從表3數(shù)據(jù)可看出，PSM-PBC的計(jì)算時(shí)間明顯少。圖6給出了3類方法計(jì)算時(shí)間的折線圖對(duì)比。其中，PSM-PBC優(yōu)于FlexAnalytics方法的主要原因是MpaReduce函數(shù)的使用。具體的，PSM-PBC比DM-BD減小了31.48%的計(jì)算時(shí)間，由于Map函數(shù)的使用，計(jì)算時(shí)間比FlexAnalystics降低了50.39%。

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

圖6 時(shí)間復(fù)雜度對(duì)比

2.4 空間復(fù)雜度的影響

所謂空間復(fù)雜度指算法運(yùn)行所需的內(nèi)存單元數(shù)目，需要內(nèi)存空間越小，說(shuō)明算法就越有效。表4和圖7顯示了PSM-PBC模型空間復(fù)雜度的評(píng)價(jià)。本文實(shí)驗(yàn)采用不同數(shù)量的實(shí)例數(shù)來(lái)測(cè)量PSM-PBC的復(fù)雜度。相比DM-BD和FlexAnalystics方法，本文方法相同數(shù)量實(shí)例條件下所需空間復(fù)雜度更小。雖然3個(gè)方法的空間復(fù)雜度都隨實(shí)例數(shù)的增加而增加，但PSM-PBC增加的幅度較小。具體的，使用PSM-PBC模型的空間復(fù)雜度相比DM-BD和FlexAnalytics方法分別減少了19.7%和32.5%。

表4 空間復(fù)雜度

圖7 空間復(fù)雜度對(duì)比

3 結(jié)束語(yǔ)

本文在云計(jì)算環(huán)境下提出PSM-PBC模型，旨在提高云計(jì)算環(huán)境中大數(shù)據(jù)計(jì)算和信息共享的效率。該P(yáng)SM-PBC模型使用三對(duì)角對(duì)稱矩陣對(duì)云環(huán)境中的分布式大數(shù)據(jù)共享，提高了大數(shù)據(jù)搜索精度。同時(shí)使用Householder變換提高大數(shù)據(jù)的搜索精度，計(jì)算時(shí)間和空間復(fù)雜度。然后，交叉驗(yàn)證貝葉斯分類器模型用于評(píng)估從每個(gè)用戶請(qǐng)求獲得的相應(yīng)查詢結(jié)果的實(shí)值對(duì)角搜索數(shù)據(jù)，從而提高了預(yù)測(cè)率。因此，該P(yáng)SM-PBC模型擁有了相當(dāng)好的性能，利用Householder變換和平行跨分布式云空間以提高搜索精度。然后，交叉驗(yàn)證的貝葉斯分類器的模型，來(lái)評(píng)估從每個(gè)用戶請(qǐng)求獲得真正價(jià)值對(duì)角線搜索數(shù)據(jù)相應(yīng)的查詢結(jié)果。這有助于提高預(yù)測(cè)率。本文使用國(guó)家電網(wǎng)大數(shù)據(jù)集進(jìn)行了一系列實(shí)驗(yàn)，以分析搜索精度、預(yù)測(cè)率、計(jì)算時(shí)間和空間復(fù)雜性，以便測(cè)量PSM-PBC模型對(duì)大數(shù)據(jù)的有效性。相比之下，本文方法較DM-BD和FlexAnalytics效果更優(yōu)。