基于用戶移動網絡接入位置的高效分布式相似矩陣計算方法

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

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

1 引言

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

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

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

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

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

2 多種場景下的矩陣運算相關研究

矩陣運算在數據挖掘領域有著廣泛的應用，如圖像處理、文本挖掘[8]、推薦系統和生物信息學等[9]。不同的應用領域和應用場景對矩陣的運算需求有所不同，其優化方向和方式也大相徑庭。

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

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

上述解決方案較原始的矩陣處理方法而言都有一定的性能提升，在各個領域也都有不錯的表現，但都著眼于改進矩陣乘法的過程以提升其性能，而均未考慮到應用中數據本身的特殊性及其所包含的信息。如在用戶興趣和習慣發現領域，計算用戶相似矩陣時，如果對所有數據進行計算，所消耗的資源會隨著用戶量或特征維度的增加不斷增加。而事實上，用戶行為數據中包含大量時間和空間信息，如果能夠對這些信息加以適當的利用，就有可能為計算帶來一定的幫助。

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

3 基于用戶移動網絡接入位置的相似矩陣計算方法

3.1 用戶訪問行為分析

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

圖1 用戶訪問的內容數和位置數統計

從圖1中可以看出，大部分用戶的訪問內容和位置都在5個左右，且絕大部分用戶訪問的位置和內容都在10個以內。值得一提的是，用戶訪問的位置與內容相比具有更強的局限性。基于這種特性，可以認為用戶在訪問過程中位置相對固定，內容也相對固定，那么距離較遠的用戶產生關聯的可能性也就越小，也就是相似度越小。

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

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

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

圖2 用戶間JSD值分布

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

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

3.2 方法架構

為提升相似矩陣的計算效率，同時有效利用系統中的計算資源，本文基于分布式計算框架對相似網絡計算方法進行了設計，其架構如圖3所示。

圖3 基于用戶移動網絡接入位置的相似矩陣計算方法架構

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

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

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

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

3.3 關鍵技術

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

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

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

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

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

3.3.2 分塊相似矩陣計算方法

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

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

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

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

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

3.3.3 高效存儲及傳輸策略

本文中的數據存儲策略分為原始數據存儲和中間數據存儲策略。原始數據存儲策略將數據存儲在分布式數據庫HBase中，通過針對性的表存儲結構設計實現數據的高效存取；中間數據存儲則采用 Hadoop分布式文件系統（HDFS），通過設計文件中數據的存放方式及文件的備份機制，實現中間數據讀寫的低 I/O開銷。

原始數據存儲采用分布式數據庫 HBase。HBase是Hadoop生態系統中的一個高可靠、高性能、列式存儲、可伸縮的分布式數據庫[23]。相較于傳統數據庫而言，HBase對于超大規模數據集有更為優良的存儲表現和讀寫性能，特別是對于不強調數據間關系、對聯合查詢等沒有需求的格式化數據存儲有非常明顯的優勢。

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

表1 HBase表存儲方式

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

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

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

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

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

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

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

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

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

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

4 實驗分析

4.1 數據集

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

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

表2 用戶接入數據和基站位置字段含義

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

4.2 實驗配置及流程

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

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

4.3 參數選擇對效果的影響

經分析發現，移動網絡用戶的活動范圍多在10 km左右，而其訪問基站的個數也大多集中在5個左右，故選取10 km作為實驗中塊劃分的距離。

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

4.4 對比實驗設計

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

4.5 性能指標

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

4.6 實驗結果分析

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

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

劃分前后的社區發現結果準確度對比見表 3和表4，本文選取3 468個用戶和20 846個用戶的社區發現結果進行對比。

表3 20 846個用戶劃分前后社區發現效果對比

表4 3 468個用戶劃分前后社區發現效果對比

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

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

圖6 不同用戶社區訪問內容分布

5 結束語

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

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

參考文獻：

[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].計算機應用, 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]王榮.基于三元組表表示的稀疏矩陣的快速轉置算法及其改進[J].現代電子技術, 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.