基于用戶移動網(wǎng)絡(luò)接入位置的高效分布式相似矩陣計算方法

王源，江昊，吳明，姚冬桂，張毅，羿舒文，汪海，吳靜

（1.武漢大學(xué)電子信息學(xué)院，湖北 武漢 430072；2.武漢船舶通信研究所，湖北 武漢 430070；3.武漢技師學(xué)院，湖北 武漢 430051）

1 引言

近年來，大數(shù)據(jù)的處理和運用在各行各業(yè)逐漸占據(jù)重要位置，從大數(shù)據(jù)中獲取的海量信息為人們提供著生活體驗的全方位改善。隨著數(shù)據(jù)量的不斷增大，數(shù)據(jù)處理過程對軟硬件的需求也隨之增加，人們越來越迫切地需要找到能夠適應(yīng)大規(guī)模數(shù)據(jù)的高效處理方式。

在實際的大數(shù)據(jù)處理中，對不同的數(shù)據(jù)來源有不同的處理方式，而在眾多的數(shù)據(jù)來源中，用戶移動網(wǎng)絡(luò)接入數(shù)據(jù)是一種具有代表性的包含多維屬性的數(shù)據(jù)，其最主要的意義之一就是用于對用戶的興趣和習(xí)慣進行分析和挖掘。利用用戶移動網(wǎng)絡(luò)接入數(shù)據(jù)，可以構(gòu)建用戶網(wǎng)絡(luò)圖，根據(jù)獲得的用戶網(wǎng)絡(luò)圖可以進行社區(qū)發(fā)現(xiàn)[1]。在網(wǎng)絡(luò)中，如果兩個節(jié)點間相連，就認為它們相似——這就是社區(qū)發(fā)現(xiàn)[2]，連邊的權(quán)重則區(qū)分了用戶與用戶間不同的相似程度。隨著社交網(wǎng)絡(luò)規(guī)模的逐漸擴大，人與人之間的聯(lián)系日益密切，在這些大的網(wǎng)絡(luò)中尋找相似點間的社區(qū)和子集變成了資源密集型作業(yè)[3]。由于社區(qū)發(fā)現(xiàn)基于用戶之間相似度實現(xiàn)，過程中必然涉及相似矩陣計算，例如余弦相似度的計算中使用的矩陣乘法需要大量的 I/O開銷和內(nèi)存開銷，為整個計算流程帶來了極大的時間復(fù)雜度。

傳統(tǒng)矩陣乘法的時間復(fù)雜度是O(n3)，1969年Strassen[4]利用分治算法，將時間復(fù)雜度降至O(n2.8074)，Strassen算法的這一優(yōu)化在現(xiàn)實實踐中得到了廣泛的應(yīng)用。這些算法現(xiàn)在已經(jīng)被封裝成成熟的程序包，比如 Jampack[5]和 JAMA[6]。在此基礎(chǔ)上，近年來也有不少學(xué)者在不斷地嘗試創(chuàng)新和優(yōu)化，Duc等人[7]提出了一種基于 Strassen算法的并行化實現(xiàn)，能夠在一定程度上減少運行時間，但是卻增大了遞歸深度。Scripps等人[1]提出了一種基于Jaccard因子的社區(qū)發(fā)現(xiàn)并行算法，取得了良好的效果。然而，由于矩陣乘法本身的計算復(fù)雜性，通過對矩陣乘法過程優(yōu)化獲得運算效率提升的難度不斷增大，如果能夠結(jié)合應(yīng)用場景和數(shù)據(jù)特征對矩陣乘法的計算復(fù)雜度進行一定的優(yōu)化，則能夠在特定的場景下獲得更好的效果。

一方面，在實際的應(yīng)用場景（如習(xí)慣發(fā)現(xiàn)、協(xié)同過濾、興趣推薦）中進行社區(qū)發(fā)現(xiàn)時會有大量無關(guān)用戶之間的連邊，這些連邊在社區(qū)發(fā)現(xiàn)過程中將被剔除，但卻會在相似矩陣計算過程中給系統(tǒng)帶來不必要的資源消耗；另一方面，用戶移動網(wǎng)絡(luò)接入數(shù)據(jù)在實際使用中會根據(jù)場景需要進行篩選，只留下與研究目標關(guān)聯(lián)性較強的信息，忽略其他信息，而這些被忽略的信息也許能夠以先驗知識的形式為后期工作提供便捷。

針對以上問題，本文將對基于用戶移動網(wǎng)絡(luò)接入數(shù)據(jù)進行社區(qū)發(fā)現(xiàn)過程中的相似矩陣計算方法進行優(yōu)化，提出一種基于用戶移動網(wǎng)絡(luò)接入位置的分布式相似矩陣計算方法，利用先驗地理位置信息對用戶進行劃分，只對相近用戶進行相似度計算以減少數(shù)據(jù)冗余，從而實現(xiàn)更高效的相似矩陣計算方法，并與現(xiàn)有算法進行效率和效果比對，證明其在實際應(yīng)用中有更為出色的性能。

2 多種場景下的矩陣運算相關(guān)研究

矩陣運算在數(shù)據(jù)挖掘領(lǐng)域有著廣泛的應(yīng)用，如圖像處理、文本挖掘[8]、推薦系統(tǒng)和生物信息學(xué)等[9]。不同的應(yīng)用領(lǐng)域和應(yīng)用場景對矩陣的運算需求有所不同，其優(yōu)化方向和方式也大相徑庭。

在推薦系統(tǒng)、用戶興趣和習(xí)慣發(fā)現(xiàn)領(lǐng)域，矩陣運算普遍應(yīng)用于根據(jù)用戶屬性矩陣挖掘用戶的相似度，其中包括皮爾遜相似度、余弦相似度在內(nèi)的相似度度量方法均涉及矩陣乘法。在圖像處理領(lǐng)域，圖像本身就是由像素組成的矩陣，在去噪、模糊圖像處理等過程中更無可避免地使用到矩陣乘法等。在圖像處理、文本挖掘等領(lǐng)域，已有許多研究工作者嘗試將新的技術(shù)應(yīng)用到矩陣乘法中，以提升其在各自領(lǐng)域的效率。Reza等人[10]將輸入矩陣分割并將它們存儲在獨立的數(shù)據(jù)節(jié)點并觸發(fā)各節(jié)點上的CUDA核，以提升整體計算效率。Malysiak 等人[11]提出了一種在多個裝有GPU的節(jié)點上進行分布式矩陣乘法的方法。Giza-Belciug等人[12]針對本體映射的相似矩陣乘法提出了一種并行優(yōu)化算法。然而，在用戶興趣和習(xí)慣發(fā)現(xiàn)領(lǐng)域，卻尚未提出有針對性的矩陣乘法計算策略優(yōu)化方案。

與此同時，隨著數(shù)據(jù)量的增大，單節(jié)點的硬件資源已無法高效地滿足數(shù)據(jù)處理需求，大量分布式解決方案也被提出，其中最有代表性的就是Apache的開源項目Hadoop。Hadoop在數(shù)據(jù)挖掘領(lǐng)域有著廣泛的應(yīng)用價值，包括用戶聚類和社區(qū)發(fā)現(xiàn)領(lǐng)域，Zhang等人[13]、Mann等人[14]和Shahrivari等人[15]都嘗試將 Hadoop應(yīng)用于K-means算法中，Lu 等人[16]和Song等人[17]則將Hadoop應(yīng)用于KNN（K-nearest neighbor）算法中。針對目前高維數(shù)據(jù)矩陣乘法中所存在的問題，孫遠帥等人[9]介紹了兩種利用Hadoop進行并行矩陣乘法計算的方法：一種是內(nèi)積法；另一種是外積法。內(nèi)積法充分利用了MapReduce的并行性，但同時也大大增加了 Shuffle傳輸?shù)闹虚g數(shù)據(jù)量[9]。外積法比內(nèi)積法的 MapReduce 實現(xiàn)少了很多中間數(shù)據(jù)，但損失了并行粒度[9]。針對上述問題，筆者提出了一種新的分塊計算方法，能夠通過調(diào)整子塊的維度實現(xiàn)較好的性能表現(xiàn)。

上述解決方案較原始的矩陣處理方法而言都有一定的性能提升，在各個領(lǐng)域也都有不錯的表現(xiàn)，但都著眼于改進矩陣乘法的過程以提升其性能，而均未考慮到應(yīng)用中數(shù)據(jù)本身的特殊性及其所包含的信息。如在用戶興趣和習(xí)慣發(fā)現(xiàn)領(lǐng)域，計算用戶相似矩陣時，如果對所有數(shù)據(jù)進行計算，所消耗的資源會隨著用戶量或特征維度的增加不斷增加。而事實上，用戶行為數(shù)據(jù)中包含大量時間和空間信息，如果能夠?qū)@些信息加以適當?shù)睦?，就有可能為計算帶來一定的幫助?/p>

綜上，在實際的應(yīng)用中，不同應(yīng)用場景對矩陣運算提出了不同的需求，如果可以根據(jù)不同的背景和需求進行有針對性的矩陣運算方法設(shè)計，將能夠為其性能和效果帶來更進一步的提升。

3 基于用戶移動網(wǎng)絡(luò)接入位置的相似矩陣計算方法

3.1 用戶訪問行為分析

用戶行為中存在一定的長尾特性和指數(shù)分布特性，現(xiàn)有的許多工作都對這些特性進行了分析和證明[18-21]。在移動網(wǎng)絡(luò)的訪問過程中，用戶的訪問行為存在一定的隨機性[22]，本文對用戶訪問的位置和內(nèi)容進行了統(tǒng)計，統(tǒng)計出了用戶訪問過的內(nèi)容數(shù)和位置數(shù)，具體如圖1所示。

圖1 用戶訪問的內(nèi)容數(shù)和位置數(shù)統(tǒng)計

從圖1中可以看出，大部分用戶的訪問內(nèi)容和位置都在5個左右，且絕大部分用戶訪問的位置和內(nèi)容都在10個以內(nèi)。值得一提的是，用戶訪問的位置與內(nèi)容相比具有更強的局限性?；谶@種特性，可以認為用戶在訪問過程中位置相對固定，內(nèi)容也相對固定，那么距離較遠的用戶產(chǎn)生關(guān)聯(lián)的可能性也就越小，也就是相似度越小。

為了說明用戶訪問位置和用戶訪問內(nèi)容之間的相關(guān)性，本文以用戶間的 JS散度（Jensen-Shannon divergence）作為用戶訪問行為相似程度的度量，JS散度定義如式（1）所示：

其中，JS(?)對于所有PA、PB有JS( ?)∈ ( 0,1)，KL(?)表示KL散度（Kullback-Leibler divergence），其定義如式（2）所示：

其中，PA、PB分別為用戶A和用戶B的訪問內(nèi)容分布。本文定義，且有 JS D∈ ( 0,1 0 0)，計算了兩兩用戶間的內(nèi)容分布JSD值，并繪制所有用戶中的JSD值分布和使用本文用戶劃分方法劃分后的一個用戶分塊中的JSD值分布，具體如圖2所示。

圖2 用戶間JSD值分布

由圖2中可以看出，圖2（a）中的峰值出現(xiàn)在JSD值為30左右時，而圖2（b）中的峰值出現(xiàn)在JSD值為100時，根據(jù)JSD的定義可知，越大的JSD值意味著越強的相似度，顯然，圖2（b）中的用戶相較于圖2（a）中的用戶展現(xiàn)出更強的相似性，故經(jīng)過劃分后的用戶塊中的用戶在訪問的內(nèi)容分布上有更強的相似性，而從全局的角度來看，大部分用戶之間的訪問內(nèi)容分布相似度較低。

在社區(qū)發(fā)現(xiàn)的過程中，相似度過低的用戶之間的連邊屬于無效連邊，即這條連邊的存在與否對最終結(jié)果幾乎沒有影響，反而會降低運算效率。于是，本文基于用戶訪問位置相對固定的特性，根據(jù)用戶的位置對用戶進行預(yù)先劃分，并依據(jù)劃分結(jié)果對相鄰的用戶進行相似度的計算，以提升計算效率。

3.2 方法架構(gòu)

為提升相似矩陣的計算效率，同時有效利用系統(tǒng)中的計算資源，本文基于分布式計算框架對相似網(wǎng)絡(luò)計算方法進行了設(shè)計，其架構(gòu)如圖3所示。

圖3 基于用戶移動網(wǎng)絡(luò)接入位置的相似矩陣計算方法架構(gòu)

整個架構(gòu)和工作流程分為4個部分，分別是HBase數(shù)據(jù)存儲、基于坐標的快速分塊、HDFS數(shù)據(jù)存儲和MapReduce計算框架。HBase中存儲原始用戶移動網(wǎng)絡(luò)接入數(shù)據(jù)和基站經(jīng)緯度數(shù)據(jù)。原始用戶移動網(wǎng)絡(luò)接入數(shù)據(jù)以用戶的每一條移動網(wǎng)絡(luò)接入記錄為數(shù)據(jù)庫中的一行，列包括用戶ID、記錄開始時間、記錄結(jié)束時間，所訪問基站的LACID和cellID、所訪問基站的坐標以及所訪問的內(nèi)容URL。其中，所訪問基站的坐標由基站的經(jīng)緯度換算得來。基站經(jīng)緯度數(shù)據(jù)則以每一個基站為一行，列包括基站的LACID和cellID、基站的經(jīng)緯度信息，開始計算之前將會根據(jù)基站經(jīng)緯度數(shù)據(jù)計算出基站的直角坐標。

基于坐標的快速分塊策略是根據(jù)計算得到的基站直角坐標對基站進行塊劃分，具體劃分方法見第3.3.1節(jié)，劃分后得到基站分塊，然后根據(jù)用戶對不同塊中基站的訪問時長，將用戶劃分至訪問時長最長的塊中，得到用戶分塊。

HDFS上存儲的是基于坐標的快速分塊策略得到的用戶分塊結(jié)果文件，存儲形式為三元組，即用（x,y,n）來表示第x行第y列的值為n。為了提升存儲和傳輸效率，HDFS只存儲矩陣中不為0的元素，對于稀疏矩陣而言，能夠大大減少存儲所需的空間和傳輸帶寬。

計算時首先進行數(shù)據(jù)預(yù)處理，將基站的經(jīng)緯度信息轉(zhuǎn)換成直角坐標。接著對格式化的用戶訪問矩陣進行基于坐標的快速分塊，即先將基站根據(jù)坐標分塊，然后依此對用戶進行分塊。分塊后得到的用戶特征矩陣以三元組的形式存儲在 HDFS上。最后根據(jù)劃分結(jié)果進行基于MapReduce的用戶相似矩陣計算，得到最終的相似度矩陣。

3.3 關(guān)鍵技術(shù)

3.3.1 基于坐標的快速分塊策略

基于坐標的快速分塊策略基本步驟如圖4所示。首先根據(jù)基站的位置將基站劃分入不同的網(wǎng)格中，如圖4（a）所示，其中圓點表示基站，具體先根據(jù)基站所屬行政區(qū)面積及所需的分塊大小決定分塊個數(shù)，并確定基站集合：{b1,b2,…,bn}，然后根據(jù)坐標值的范圍結(jié)合所需分塊個數(shù)確定劃分節(jié)點，根據(jù)劃分節(jié)點對基站直角坐標進行截取或轉(zhuǎn)換，生成其所在塊編號，具有相同編號的基站屬于同一塊，否則屬于不同塊。而屬于不同塊的基站編號之間的差值即可反映兩基站所屬塊的鄰近關(guān)系，不同的差值表示不同的方位上的距離。例如本文中基站直角坐標范圍為（9 700 172.203 65，8 738 234.211 33）到（9 806 113.083 42，8 884 126.448 06），所需劃分塊個數(shù)為600個，故將坐標截短為（9 700, 9 806）到（8 738, 8 884），對x、y坐標以5為間隔劃分，若x＜9 705，則x被劃分到9 700，若9 705≤x＜9 710，則x被劃分到9 705，以此類推，同樣地，若y＜8 743，則y被劃分為8 738，若8 743≤y＜8 748，則y被劃分為 8 743，以此類推，則總共可劃分的塊數(shù)為。最后將x和y的劃分結(jié)果合并生成基站的塊編號，如基站（9 705,8 738），則其塊編號為97058738，至此，所有基站擁有其塊編號，塊編號本身同時表征著基站之間的位置關(guān)系，得到劃分塊集合：{c1,c2,…,cm}。

接著根據(jù)用戶對不同基站的訪問時長，將用戶劃分至訪問總時長最多的塊，如圖4（b）所示，其中圓點表示基站，它們分別屬于不同的塊，用戶與基站的連線表示用戶對基站的訪問，連線的粗細程度表示用戶在該基站的訪問總時長，連線越粗表明用戶對該基站的總訪問時長越長。本文對用戶的移動數(shù)據(jù)接入記錄數(shù)據(jù)進行匯總整理，生成用戶訪問矩陣，在本文提出的相似矩陣計算方法中，強調(diào)用戶的位置序列，故生成用戶訪問矩陣時對同一用戶不同時段的訪問情況進行無序疊加，得到用戶xi訪問基站時長的序列為{t1,t2,…,tk}，其中tj表示用戶訪問第j個基站的總時長，基站劃分完畢后，根據(jù)用戶所訪問基站所在的塊，計算每個塊中的訪問時長，并據(jù)此將用戶定位到訪問時長最長的塊中。假設(shè)基站b1,b2,b3,b4,b5∈ci，那么用戶xj對塊ci的訪問總時長則為：Ti=t1+t2+t3+t4+t5，依次獲得用戶對所有m個塊的訪問集合{T1,T2,…,Tm}，從中找出時長最長的塊c，即用戶所處的塊。如圖4（b）所示，用戶訪問次數(shù)最多的塊是陰影部分，故將該用戶劃分到陰影塊。

圖4 基于坐標的快速分塊策略基本步驟

最終生成用戶的塊劃分結(jié)果如圖4（c）所示，將用戶定位到各個塊中后，計算時只計算用戶與其所在塊及其周邊8個塊內(nèi)用戶之間的相似度。

3.3.2 分塊相似矩陣計算方法

本文使用MapReduce框架作為相似矩陣計算的實現(xiàn)框架，其流程為：在map階段將矩陣數(shù)據(jù)進行整理，根據(jù)規(guī)則將所需計算的用戶及其周邊8個塊內(nèi)的用戶數(shù)據(jù)輸入同一個reduce中，而在reduce中則對這些用戶兩兩計算相似度，并輸出最后的結(jié)果，算法偽代碼如下。

輸入：劃分后用戶完整訪問矩陣，用戶分塊信息。

在map階段輸入劃分后的用戶完整訪問矩陣和分塊信息，首先處理分塊信息，將分塊信息作為靜態(tài)變量，保存在一個HashMap數(shù)據(jù)結(jié)構(gòu)中，其中將塊的編號 BlockNum作為HashMap中的鍵，其對應(yīng)的值為該塊中的所有用戶UserNum，然后處理用戶訪問矩陣，矩陣中的每一行即相似矩陣計算時的特征向量，其中還包含了該用戶所在的塊和該用戶的編號。由于每一個用戶需要和他所在塊周圍的8個塊中的所有用戶計算相似度，所以為了在 reduce階段能夠讓需要計算相似度的用戶特征向量分到同一個reducer中，每一個用戶的特征向量會為所有需要與其計算相似度的用戶輸出一次。例如用戶x有n個需要計算相似度的用戶，那么對于用戶x的map階段將會產(chǎn)生n個輸出，每一個輸出的key為用戶x的編號加上需要與x計算相似度的用戶的編號組成的復(fù)合鍵，value則為用戶x的訪問向量。

由于map在處理不同的用戶訪問記錄時，輸出key值的順序是不同的，例如，假設(shè)用戶x和y之間需要計算相似度，那么在處理用戶x的訪問記錄時，針對y的輸出key值是（y，x），而在處理用戶y的訪問記錄時，針對x的輸出key 值是（x，y），故本文重新設(shè)計了 MapReduce中的key值比較算法，讓map階段key為（x，y）和（y，x）的輸出能夠被放入同一個reducer中。

在reduce階段將完成對用戶相似度的計算，其中每一個reducer處理的是兩個用戶的相似度計算。用HashMap暫存其中一個用戶的特征向量，另一個用戶則直接從HashMap中取相對應(yīng)的值進行相似度計算即可。

3.3.3 高效存儲及傳輸策略

本文中的數(shù)據(jù)存儲策略分為原始數(shù)據(jù)存儲和中間數(shù)據(jù)存儲策略。原始數(shù)據(jù)存儲策略將數(shù)據(jù)存儲在分布式數(shù)據(jù)庫HBase中，通過針對性的表存儲結(jié)構(gòu)設(shè)計實現(xiàn)數(shù)據(jù)的高效存?。恢虚g數(shù)據(jù)存儲則采用 Hadoop分布式文件系統(tǒng)（HDFS），通過設(shè)計文件中數(shù)據(jù)的存放方式及文件的備份機制，實現(xiàn)中間數(shù)據(jù)讀寫的低 I/O開銷。

原始數(shù)據(jù)存儲采用分布式數(shù)據(jù)庫 HBase。HBase是Hadoop生態(tài)系統(tǒng)中的一個高可靠、高性能、列式存儲、可伸縮的分布式數(shù)據(jù)庫[23]。相較于傳統(tǒng)數(shù)據(jù)庫而言，HBase對于超大規(guī)模數(shù)據(jù)集有更為優(yōu)良的存儲表現(xiàn)和讀寫性能，特別是對于不強調(diào)數(shù)據(jù)間關(guān)系、對聯(lián)合查詢等沒有需求的格式化數(shù)據(jù)存儲有非常明顯的優(yōu)勢。

用戶移動網(wǎng)絡(luò)接入數(shù)據(jù)是一種格式化數(shù)據(jù)，本文針對其特征設(shè)計存儲格式，將數(shù)據(jù)存儲到HBase中。存儲方式見表1，為提升HBase性能，數(shù)據(jù)采用單列族存儲方式，列族中列名即字段名稱。值得一提的是，HBase數(shù)據(jù)表中的 RowKey（行鍵）設(shè)計，由于本文數(shù)據(jù)處理部分將對屬于同一用戶的網(wǎng)絡(luò)接入數(shù)據(jù)進行合并處理，故RowKey以用戶UID開頭，后加上數(shù)據(jù)起始時間，以實現(xiàn)同一用戶的數(shù)據(jù)存儲在同一個RegionServer上，并按時間排序。

表1 HBase表存儲方式

相較于傳統(tǒng)文本數(shù)據(jù)輸入方式而言，在數(shù)據(jù)處理時，直接從HBase中取出相應(yīng)的字段輸入而無需再次對數(shù)據(jù)進行分解，極大提升了程序效率。同時，使用本文的RowKey設(shè)計方式，可以有效地利用HBase的高效RowKey查詢性能，提升程序運行過程中的數(shù)據(jù)訪問效率。

考慮到MapReduce的適配性，中間數(shù)據(jù)存儲采用 HDFS，將輸出文件以 block的形式直接存放在HDFS的各個DataNode節(jié)點上，考慮到節(jié)點間數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)時延，結(jié)合DataNode節(jié)點的資源負載情況，將生成的中間數(shù)據(jù)以多副本形式存儲，根據(jù)節(jié)點數(shù)量，對n個節(jié)點的集群將副本數(shù)設(shè)為n，在進行新一輪數(shù)據(jù)處理時，各DataNode節(jié)點可高效拉取本地備份的副本數(shù)據(jù)，降低網(wǎng)絡(luò)開銷，提升運行效率。

在實際應(yīng)用中，用戶的訪問情況呈明顯的聚集性，單個用戶的訪問范圍有限，故在相似矩陣計算過程中產(chǎn)生的中間數(shù)據(jù)多為稀疏矩陣，針對此特性，本文將中間數(shù)據(jù)以三元組[24]的形式存儲，將矩陣中的非零值以其行號和列號為標識存儲，即以(x,y,n)表示第x行第y列的值為n，顯然以這種存儲方式存儲稀疏矩陣可以極大地節(jié)省存儲資源。

現(xiàn)有的基于MapReduce的分布式矩陣乘法算法中，基本采用兩種map輸出方式，一種為行（列）式輸出，另一種則為點式輸出。

在行（列）式輸出方式中，對于矩陣P、Q：

計算P×Q時將在map階段對P、Q分別做如下劃分：

將P的每一行和Q的每一列作為map的輸出，在reduce中，則將行與列相乘得到結(jié)果矩陣中的對應(yīng)元素。

而在點式輸出方式中，則會對P、Q中的每一個元素進行劃分，如下所示：

將P、Q中的每一個元素作為map的輸出，而在reduce中依然將輸出結(jié)果所對應(yīng)的P中行的所有元素和Q中列的所有元素放到一起計算出最終結(jié)果，與行（列）式輸出方式不同的是，點式輸出方式在數(shù)據(jù)傳輸?shù)絩educe階段時，已經(jīng)包含了矩陣乘法中元素與元素間的對應(yīng)關(guān)系，即已經(jīng)知道p11與q11相乘、p12與q12相乘等，而無需再做判斷。

點式輸出的優(yōu)勢在于 reduce階段的工作量小，因為在map輸出數(shù)據(jù)中已經(jīng)包含了其數(shù)據(jù)計算的對應(yīng)關(guān)系，在reduce階段只需根據(jù)這種關(guān)系進行計算即可；而行（列）式輸出的優(yōu)勢則在于map的輸出次數(shù)少，I/O開銷小。在實際應(yīng)用中，由于矩陣乘法并不涉及大量串行計算而只需簡單的并行數(shù)乘，其主要開銷集中于數(shù)據(jù)獲取階段和結(jié)果生成階段的數(shù)據(jù)傳輸，數(shù)據(jù)傳輸時產(chǎn)生的I/O開銷將會對效率產(chǎn)生更大的影響，故本文選用行（列）式輸出以更好地提升其效率。

4 實驗分析

4.1 數(shù)據(jù)集

本文采用浙江省金華市2014年11月21日—12月13日的用戶UDR（usage detail record）數(shù)據(jù)作為原始數(shù)據(jù)集，為消除實驗結(jié)果中的不確定因素和隨機性，本文篩選了上網(wǎng)記錄數(shù)較多的用戶，分別是上網(wǎng)記錄100條以上的70 099個用戶、150條以上的49 031個用戶、200條以上的20 846個用戶、300條以上的18 479個用戶、350條以上的14 566個用戶、400條以上的11 827個用戶和500條以上的3 468個用戶。

用戶接入數(shù)據(jù)和基站位置字段含義見表2，實驗中使用uid作為用戶的標識，lacID和cellID作為用戶訪問矩陣中不同基站的標識，同時根據(jù)數(shù)據(jù)流起止時間計算用戶的上網(wǎng)時長，url為截短后的訪問內(nèi)容地址，以此區(qū)分用戶對不同內(nèi)容的訪問次數(shù)。而在基站信息表格中，基站由 lacID和cellID唯一標識，根據(jù)基站所在位置經(jīng)緯度換算成直角坐標，對基站進行分塊。

表2 用戶接入數(shù)據(jù)和基站位置字段含義

本文選取用戶訪問內(nèi)容特征作為相似矩陣計算特征，從理論角度來看，內(nèi)容特征與位置特征本身存在一定的聯(lián)系，例如人們在家里經(jīng)常訪問娛樂相關(guān)的內(nèi)容，而在辦公區(qū)域則主要瀏覽工作相關(guān)的內(nèi)容；同時，如圖 2所示，有相同位置特征的用戶在訪問內(nèi)容分布上也呈現(xiàn)出一定的規(guī)律性，例如，在同一間辦公室的職員會互相分享有價值的內(nèi)容，故這些職員的訪問內(nèi)容分布會呈現(xiàn)出相似性。從實際應(yīng)用角度來看，內(nèi)容特征反映了用戶之間的興趣維度，在用戶的訪問行為研究和應(yīng)用中，該特征被廣泛地應(yīng)用于各種場景，如興趣發(fā)現(xiàn)、推薦系統(tǒng)、D2D[25]、流量卸載、邊緣緩存和計算[26]等，故對用戶內(nèi)容特征相似度計算的研究對實際的應(yīng)用有極大的價值。

4.2 實驗配置及流程

所有的實驗均在由 4臺服務(wù)器搭建的Hadoop集群上完成，其中一臺服務(wù)器作為Hadoop集群的NameNode，裝有64位CentOS 6.5操作系統(tǒng)，磁盤容量為1 TB，內(nèi)存為48 GB，配有雙核CPU6；另3臺服務(wù)器作為Hadoop集群的DataNode，裝有64位CentOS 7.0操作系統(tǒng)，磁盤容量為3.6 TB，內(nèi)存為128 GB，配有雙核CPU8。

實驗中，本文所提出的算法將首先對用戶進行劃分，對于劃分過的用戶，只計算用戶及其相鄰塊（包括自己所在的塊）中用戶之間的相似度。而對比實驗中不對用戶進行劃分，計算所有用戶兩兩間的相似度，相似矩陣計算過程則借用參考文獻[9]中所提出方法的思想，實現(xiàn)方案在第 4.4節(jié)介紹。相似度矩陣計算完成后，將兩種實驗結(jié)果應(yīng)用于Louvain社區(qū)發(fā)現(xiàn)算法，實驗結(jié)果將在第4.6節(jié)介紹。

4.3 參數(shù)選擇對效果的影響

經(jīng)分析發(fā)現(xiàn)，移動網(wǎng)絡(luò)用戶的活動范圍多在10 km左右，而其訪問基站的個數(shù)也大多集中在5個左右，故選取10 km作為實驗中塊劃分的距離。

考慮到分塊的大小為 10 km，且計算時用戶將與周邊8個塊內(nèi)的用戶計算相似度，實際的計算范圍為 30 km，遠大于用戶的活動半徑，本文采用以訪問總時長最長的塊作為用戶所在的塊的劃分方式，可以在不影響計算準確性的前提下提升計算效率。

4.4 對比實驗設(shè)計

為保證公平性，本文實驗中的所有算法均使用MapReduce框架在分布式環(huán)境下實現(xiàn)。本文對比實驗設(shè)計參考文獻[9]中所提到的方法，由于本文介紹的基于地理位置的分布式相似矩陣計算方法采用行（列）式輸出方式，故對比實驗采用第3.3.3節(jié)介紹的點式輸出方式，同時在70 099個用戶的實驗中，由于用戶數(shù)據(jù)量過大，故采用分塊矩陣乘法以遵循對比實驗所采用方案的設(shè)計思想，達到對比效果。

4.5 性能指標

本文以用戶訪問矩陣作為輸入，用戶相似矩陣作為輸出，以從輸入到輸出的程序運行時長作為實驗的效率對比標準。在一致性方面，將兩種計算方法生成的相似矩陣輸入 Louvain社區(qū)發(fā)現(xiàn)算法，對比兩種社區(qū)發(fā)現(xiàn)結(jié)果，定義未將用戶進行分塊的社區(qū)發(fā)現(xiàn)結(jié)果為劃分前社區(qū)發(fā)現(xiàn)結(jié)果，用戶分塊后的社區(qū)發(fā)現(xiàn)結(jié)果為劃分后社區(qū)發(fā)現(xiàn)結(jié)果。將劃分前社區(qū)發(fā)現(xiàn)結(jié)果中，在同一社區(qū)內(nèi)的兩位用戶之間的連邊作為社區(qū)內(nèi)邊數(shù)記錄，而將劃分后社區(qū)發(fā)現(xiàn)結(jié)果中的社區(qū)內(nèi)連邊和劃分前社區(qū)發(fā)現(xiàn)結(jié)果中的社區(qū)內(nèi)連邊的交集作為“好邊”記錄，以“好邊”相連的用戶則作為正確用戶記錄，若無“好邊”與之相連則為錯誤用戶。

4.6 實驗結(jié)果分析

實驗分別對兩種方法的性能和結(jié)果一致性進行了對比。如圖 5所示為不同用戶數(shù)劃分前后相似矩陣計算耗時，顯然，劃分前的計算耗時隨著用戶數(shù)的增加呈指數(shù)形式增長，而劃分后的計算耗時隨著用戶數(shù)的增加呈線性增長。例如在3 468個用戶的實驗中，未劃分時相似矩陣計算耗時106 s，劃分后相似矩陣計算耗時42 s；在20 846個用戶的實驗中，未劃分時相似矩陣計算耗時約30 min，劃分后用時約8 min；在70 099個用戶的實驗中，未劃分時相似矩陣計算耗時約360 min，劃分后用時約14 min，兩者相差達25倍之多。不妨以方陣為例對這個現(xiàn)象進行分析，普通矩陣乘法的復(fù)雜度為O(n3)，而對于進行了劃分之后的相似矩陣計算，假設(shè)劃分為m個塊，每個塊和周圍8塊之間計算相似度，那么計算復(fù)雜度為，令，那么復(fù)雜度可化簡為，其中k≥1，由于m可以隨著n值變化而調(diào)整，令k為常量，故劃分后的相似矩陣計算耗時關(guān)于n呈線性增長。值得一提的是，在70 099個用戶的相似矩陣計算過程中加入了矩陣分塊處理步驟，而實驗表明，在如此大規(guī)模的矩陣計算中，即使進行了矩陣分塊，由于分塊帶來的巨大傳輸需求對分布式集群的資源消耗巨大，導(dǎo)致最終的計算成本依然居高不下。顯然，在相似度矩陣的計算效率上，本文所提出的方案有明顯的優(yōu)勢，不難看出，隨著用戶數(shù)的增大，數(shù)據(jù)量不斷增長，本文所提出的方案的優(yōu)勢也更加顯著。

圖5 不同用戶數(shù)劃分前后相似矩陣計算耗時

劃分前后的社區(qū)發(fā)現(xiàn)結(jié)果準確度對比見表 3和表4，本文選取3 468個用戶和20 846個用戶的社區(qū)發(fā)現(xiàn)結(jié)果進行對比。

表3 20 846個用戶劃分前后社區(qū)發(fā)現(xiàn)效果對比

表4 3 468個用戶劃分前后社區(qū)發(fā)現(xiàn)效果對比

可以看出，無論是在20 846個用戶還是3 468個用戶的對比實驗中，劃分后的社區(qū)內(nèi)連邊數(shù)較劃分前的社區(qū)內(nèi)連邊數(shù)都減少了近一半，而用戶正確率均在95%以上，在20 846個用戶的實驗中，正確率甚至高達 99.9%。顯然，本文所提出的相似矩陣計算方法相較于原始計算方法而言，在社區(qū)發(fā)現(xiàn)結(jié)果上幾乎沒有性能和效果的影響。

圖6繪制了不同用戶社區(qū)訪問內(nèi)容分布的熱力圖，可以看出，基于本文所提出的相似矩陣計算方法所獲得的用戶社區(qū)在訪問內(nèi)容分布上有明顯的差異，說明該方法能夠?qū)τ脩魞?nèi)容特征實現(xiàn)良好的區(qū)分。

圖6 不同用戶社區(qū)訪問內(nèi)容分布

5 結(jié)束語

本文針對目前用戶移動網(wǎng)絡(luò)接入數(shù)據(jù)分析中最為常用的一種分析需求（社區(qū)發(fā)現(xiàn)）在面對大規(guī)模數(shù)據(jù)計算時出現(xiàn)的效率低下問題進行了研究，針對其主要的性能瓶頸（相似矩陣計算）進行了優(yōu)化設(shè)計，提出了一種基于地理位置的分布式相似矩陣計算方法。方法利用用戶移動網(wǎng)絡(luò)接入數(shù)據(jù)中具有的先驗位置信息，對用戶進行基于地理位置的劃分，并根據(jù)劃分的結(jié)果，對用戶間進行有選擇性的相似度計算。相較于傳統(tǒng)的相似度計算方法，本方法在效率上有了極大的提升，而在社區(qū)發(fā)現(xiàn)結(jié)果上與劃分前相比達到了99.9%的一致性，整體上表現(xiàn)出了較為出色的性能。

根據(jù)不同數(shù)據(jù)類型的特點，有針對性地利用數(shù)據(jù)的先驗知識對數(shù)據(jù)進行簡單的預(yù)處理將能夠為數(shù)據(jù)的后續(xù)處理帶來極大的效率提升，如何將這種思想應(yīng)用到更為廣泛的領(lǐng)域中是未來需要思考的問題。

參考文獻：

[1]SCRIPPS J, TREFFTZ C.Parallelizing an algorithm to find communities using the Jaccard metric[C]//IEEE International Conference on Electro/Information Technology, June 8-12,2015, London, UK.Piscataway： IEEE Press, 2015.

[2]HURLEY N, DURIAKOVA E.Reformulations of the map equation for community finding and blockmodelling [C]//IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, August 25-28, 2015, Paris,France.Piscataway： IEEE Press, 2015.

[3]RESTREPO A, SOLANO A, SCRIPPS J, et al.High-performance implementations of a clustering algorithm for finding network communities[C]//IEEE International Conference on Electro/Information Technology, May 6-8, 2012, Indianapolis, USA.Piscataway： IEEE Press, 2012.

[4]GUNTHER J H, HOFFMAN K H.Numerische mathematik [M].Berlin： Springer, 1991.

[5]STEWART G W.Jampack： a Java package for matrix computations[EB].2017.

[6]JOE H, CLEVE M, PETER W.JAMA： a Java matrix package[EB].2017.

[7]NGUYEN D K, LAVALLEE I, BUI M, et al.A general scalable parallelizing of strassen’s algorithm for matrix multiplication on distributed memory computers[C]//ACIS International Conference on Computer and Information Science, July 14-16, 2005, Washington, DC, USA.Piscataway： IEEE Press, 2005.

[8]LIN C, HUANG Z H, YANG F, et al.Identify content quality in online social networks[J].IET Communications, 2012, 6(12)：1618-1624.

[9]孫遠帥, 陳垚, 官新均, 等.基于Hadoop的大矩陣乘法處理方法[J].計算機應(yīng)用, 2013, 33(12)： 3339-3344.SUN Y S, CHEN Y, GUAN X J, et al.Approach of large matrix multiplication based on Hadoop[J].Journal of Computer Applications, 2013, 33(12)： 3339-3344.

[10]REZA M, SINHA A, NAG R, et al.CUDA-enabled Hadoop cluster for sparse matrix vector multiplication[C]//IEEE International Conference on Recent Trends in Information Systems, July 9-11, 2015, Kolkata, India.Piscataway： IEEE Press,2015.

[11]MALYSIAK D, KOPINSKI T.A generic and adaptive approach for workload distribution in multi-tier cluster systems with an application to distributed matrix multiplication[C]//IEEE International Symposium on Computational Intelligence and Informatics, November 19-21, 2015, Budapest, Hungary.Piscataway： IEEE Press, 2015.

[12]GIZA-BELCIUG F, PENTIUC S G.Parallelization of similarity matrix calculus in ontology mapping systems[C]//Roedunet International Conference-Networking in Education and Research,September 24-26, 2015, Craiova, Romania.Piscataway： IEEE Press, 2015.

[13]ZHANG R, WANG Y.An enhanced agglomerative fuzzyk-means clustering method with MapReduce implementation on Hadoop platform[C]//International Conference on Progress in Informatics and Computing, May 16-18, 2014, Shanghai, China.Piscataway： IEEE Press, 2014.

[14]MANN K S, KAUR N.Cloud-deployable health data mining using secured framework for clinical decision support system[C]//International Conference and Workshop on Computing and Communication, October 15-17, 2015, Vancouver, BC,Canada.Piscataway： IEEE Press, 2015.

[15]SHAHRIVARI S, JALILI S.Single-pass and linear-timek-means clustering based on MapReduce[J].Information Systems, 2016(60)： 1-12.

[16]LU S, TONG W, CHEN Z.Implementation of theKNN algorithm based on Hadoop[C]//International Conference on Smart and Sustainable City and Big Data, July 26-27, 2015, Shanghai,China.Birmingham： IET Press, 2015.

[17]SONG G, ROCHAS J, BEZE L, et al.Knearest neighbour joins for big data on MapReduce： a theoretical and experimental analysis[J].IEEE Transactions on Knowledge & Data Engineering, 2016, 28(9)： 2376-2392.

[18]MIEGHEM P V, BLENN N, DOERR C.Lognormal distribution in the digg online social network[J].European Physical Journal B, 2011, 83(2)： 251-261.

[19]MAHANTI A, CARLSSON N, MAHANTI A, et al.A tale of the tails： power-laws in internet measurements[J].IEEE Network, 2013, 27(1)： 59-64.

[20]ZHOU C, JIANG H, CHEN Y, et al.TCB： a feature transformation method based central behavior for user interest prediction on mobile big data[J].International Journal of Distributed Sensor Networks, 2016, 12(9).

[21]WU L, JIANG H, ZHENG H, et al.Long tail and small world characteristic of mobile internet traffic dynamics[C]//IEEE International Conference on Systems, Man and Cybernetics, October 5-8, 2014, San Diego, CA, USA.Piscataway： IEEE Press, 2014.

[22]WU L, LI Y, ZHOU C, et al.Statistic analysis of data access behavior in the mobile internet[C]//IEEE/CIC International Conference on Communications in China, August 12-14, 2013,Xi’an, China.Piscataway： IEEE Press, 2013.

[23]ZHANG N, ZHENG G, CHEN H, et al.HBaseSpatial： a scalable spatial data storage based on HBase[C]//IEEE International Conference on Trust, Security and Privacy in Computing and Communications, September 24-26, 2014, Beijing, China.Piscataway： IEEE Press, 2014.

[24]王榮.基于三元組表表示的稀疏矩陣的快速轉(zhuǎn)置算法及其改進[J].現(xiàn)代電子技術(shù), 2008, 31(22)： 78-79.WANG R.Improvement on fast transposition algorithm to sparse matrix expressed by triple list [J].Modern Electronics Technique, 2008, 31(22)： 78-79.

[25]AFSHANG M, DHILLON H S, CHONG P H J.Fundamentals of cluster-centric content placement in cache-enabled device-to-device networks[J].IEEE Transactions on Communications, 2015, 64(6)： 2511-2526.

[26]ZHOU B, CUI Y, TAO M.Stochastic content-centric multicast scheduling for cache-enabled heterogeneous cellular networks[J].IEEE Transactions on Wireless Communications,2016, 15(9)： 6284-6297.