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

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

1 引言

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

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

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

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

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

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

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

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

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

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

綜上，在實(shí)際的應(yīng)用中，不同應(yīng)用場景對矩陣運(yùn)算提出了不同的需求，如果可以根據(jù)不同的背景和需求進(jìn)行有針對性的矩陣運(yùn)算方法設(shè)計(jì)，將能夠?yàn)槠湫阅芎托Ч麕砀M(jìn)一步的提升。

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

3.1 用戶訪問行為分析

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

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

從圖1中可以看出，大部分用戶的訪問內(nèi)容和位置都在5個(gè)左右，且絕大部分用戶訪問的位置和內(nèi)容都在10個(gè)以內(nèi)。值得一提的是，用戶訪問的位置與內(nèi)容相比具有更強(qiáng)的局限性?；谶@種特性，可以認(rèn)為用戶在訪問過程中位置相對固定，內(nèi)容也相對固定，那么距離較遠(yuǎn)的用戶產(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)，計(jì)算了兩兩用戶間的內(nèi)容分布JSD值，并繪制所有用戶中的JSD值分布和使用本文用戶劃分方法劃分后的一個(gè)用戶分塊中的JSD值分布，具體如圖2所示。

圖2 用戶間JSD值分布

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

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

3.2 方法架構(gòu)

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

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

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

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

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

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

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

3.3.1 基于坐標(biāo)的快速分塊策略

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

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

圖4 基于坐標(biāo)的快速分塊策略基本步驟

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

3.3.2 分塊相似矩陣計(jì)算方法

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

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

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

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

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

3.3.3 高效存儲(chǔ)及傳輸策略

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

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

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

表1 HBase表存儲(chǔ)方式

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

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

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

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

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

計(jì)算P×Q時(shí)將在map階段對P、Q分別做如下劃分：

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

而在點(diǎn)式輸出方式中，則會(huì)對P、Q中的每一個(gè)元素進(jìn)行劃分，如下所示：

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

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

4.2 實(shí)驗(yàn)配置及流程

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

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

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

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

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

4.4 對比實(shí)驗(yàn)設(shè)計(jì)

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

4.5 性能指標(biāo)

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

參考文獻(xiàn)：

[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]孫遠(yuǎn)帥, 陳垚, 官新均, 等.基于Hadoop的大矩陣乘法處理方法[J].計(jì)算機(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ì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.