基于對稱矩陣的云計算和信息共享預測分類器

王 騰，高秋生，王立瑋

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

0 引 言

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

1 基于并行對稱矩陣的貝葉斯預測分類器

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

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

1.1 三角對稱矩陣的構造

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

(1)

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

圖2 三對角矩陣的構造過程

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

HT=1-2V×VT

(2)

而HT2可以通過如下計算得到

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

(3)

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

(4)

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

1.2 交叉驗證貝葉斯分類器模型的設計

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

(5)

(6)

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

(7)

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

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

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

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

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

Map(x)→(Key,Value)

(8)

(Key)→(Class,Attributes)

(9)

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

圖3 MapReduce過程框架

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

初始化：關鍵字→貝葉斯類

輸出：約束功能

步驟1 Begin

步驟2 For 每類

步驟3 將該類分為n塊

步驟4 將n塊同時并行處理

步驟5 End for

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

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

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

步驟9 聚合相似的類

步驟10 End for

步驟11 For 每個reducer

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

步驟13 End for

步驟14 End

2 結(jié)果與討論

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

2.1 搜索精度的影響

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

(10)

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

表1 搜索精度

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

圖4 搜索精度對比

2.2 預測率的影響

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

(11)

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

表2 預測率

圖5 預測率對比

2.3 計算時間的影響

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

CT=Time(Map(n))

(12)

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

表3 計算時間

圖6 時間復雜度對比

2.4 空間復雜度的影響

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

表4 空間復雜度

圖7 空間復雜度對比

3 結(jié)束語

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