蔣莉芳，蘇一丹，覃　華

(廣西大學(xué)計算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

?

基于CUDA的并行譜聚類社區(qū)挖掘算法*

蔣莉芳，蘇一丹，覃華

(廣西大學(xué)計算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

摘要：社會網(wǎng)絡(luò)和社交媒體數(shù)據(jù)具有大規(guī)模、高維度的特性，社區(qū)挖掘算法的計算效率是一個值得研究的問題。針對此問題，本文利用CUDA并行計算架構(gòu)，提出一種并行的譜聚類社區(qū)挖掘算法，首先對高維的社會網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行降維，再用CUDA的并行計算能力提高譜聚類算法的計算效率。實驗表明，本文所提算法能有效地提高社區(qū)挖掘算法的計算速度，并行計算效率較常規(guī)算法有5～8倍的提高，為社區(qū)挖掘計算提出一種新的思路。

關(guān)鍵詞：社區(qū)挖掘；CUDA；并行計算；譜聚類；大規(guī)模網(wǎng)絡(luò)

1概述

快速增長的社交媒體，形成了很多規(guī)模巨大和維數(shù)眾多的網(wǎng)絡(luò)，社區(qū)發(fā)現(xiàn)成為了理解網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的重要技術(shù)[1，2]。

目前的社區(qū)發(fā)現(xiàn)算法中，大多數(shù)算法的性能其實都很優(yōu)越，如Luxburg提出的譜聚類算法(Spectral Clustering，SC)[3]，通過求解圖分割問題獲得網(wǎng)絡(luò)劃分。Newman提出了Modularity算法[4]，考慮節(jié)點度的分布情況，用兩點間的實際作用和期望值之差，定義社區(qū)效應(yīng)強(qiáng)度，通過最大化效應(yīng)強(qiáng)度，獲得最佳的社區(qū)劃分。再比如郭進(jìn)時等[5]提出的聯(lián)合拓?fù)渑c屬性的社區(qū)模糊劃分算法，用完全相異距離指數(shù)將拓?fù)浣Y(jié)構(gòu)與屬性相結(jié)合，以此作為隸屬關(guān)系建立模糊等價關(guān)系矩陣，再選擇合適的聚類對網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。這些算法都能在一定程度上達(dá)到社區(qū)發(fā)現(xiàn)的效果，但這些算法的計算量都很大。在大數(shù)據(jù)時代，網(wǎng)絡(luò)社區(qū)規(guī)模越來越大，時間復(fù)雜性的弊端，也就顯得尤為突出，特別是還要進(jìn)行多維處理時，因此需要進(jìn)一步改進(jìn)。并行和分布式計算是降低總體運(yùn)行時間的有效途徑，已經(jīng)有學(xué)者在Mapreduce上面進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)的探索，但是總體而言，社區(qū)發(fā)現(xiàn)的并行計算研究文獻(xiàn)還較少[6，11，12]。本文研究的主要目標(biāo)是利用并行計算的思想，解決社區(qū)挖掘算法中的時間需求過大問題。

CUDA(Compute Unified Device Architecture)是NVidia公司設(shè)計開發(fā)的一種在GPU上進(jìn)行通用、并行計算的編程體系結(jié)構(gòu)[7，8]。本文利用CUDA平臺實現(xiàn)對多維數(shù)據(jù)集的并行譜聚類算法(Multi-Dimension Spectral Clustering，SpectralDim)，并用于社區(qū)挖掘算法。譜聚類算法對于社區(qū)網(wǎng)絡(luò)數(shù)據(jù)的高維問題，采用拉普拉斯特征向量方式進(jìn)行降維，最后再用聚類算法進(jìn)行社區(qū)挖掘。其本身自帶的降維功能，使得其自身時間復(fù)雜度比其他社區(qū)挖掘算法低。本文利用CUDA并行譜聚類算法挖掘社區(qū)信息，提高了挖掘算法對大規(guī)模社區(qū)數(shù)據(jù)的適用能力。本文實驗使用文獻(xiàn)[9]的數(shù)據(jù)，并將SpectralDim_CPU(不用并行)、SpectralDim_GPU(CUDA并行)與文獻(xiàn)[9]中的SocioDim比較，實驗結(jié)果表明：本文所提算法的計算準(zhǔn)確率與SocioDim相當(dāng)，但是計算速度較SocioDim算法快5～8倍，更適合于大規(guī)模社區(qū)挖掘。

2基于譜聚類的社區(qū)發(fā)現(xiàn)算法

譜聚類算法利用譜分析技術(shù)可將高維數(shù)據(jù)投射到低維子空間，達(dá)到降維的效果。而當(dāng)數(shù)據(jù)擁有多維(Multi-Dimension)特征時，需要先對數(shù)據(jù)進(jìn)行效用集成才能進(jìn)行譜聚類，文獻(xiàn)[8]采用平均效用法進(jìn)行數(shù)據(jù)集成，并采用譜分析技術(shù)對數(shù)據(jù)進(jìn)行降維，最后用SVM對降維后的數(shù)據(jù)進(jìn)行社區(qū)劃分。

從降維和圖分割理論對譜聚類進(jìn)行理解，規(guī)范化拉普拉斯聚類算法的目標(biāo)函數(shù)為：

(1)

(2)

則目標(biāo)函數(shù)可轉(zhuǎn)換為如下跡函數(shù)的求解：

(3)

一般的譜聚類算法流程如下所示：

輸入:原數(shù)據(jù)集,聚類數(shù)目k1、求矩陣的相似性矩陣A以及度矩陣D2、計算拉普拉斯矩陣L=D-A3、求取L的前k個最小特征向量4、對特征向量進(jìn)行聚類得到C輸出:聚類結(jié)果C

如若數(shù)據(jù)集有多模特征，則在相似度矩陣的計算過程中，采用效用集成或者網(wǎng)絡(luò)集成的方式進(jìn)行維度集成，再計算相似度。

3基于CUDA的并行社區(qū)挖掘算法

接下來對本文中運(yùn)用到的譜聚類CUDA化的關(guān)鍵技術(shù)以及并行化過程中所涉及的地方進(jìn)行討論。分析譜聚類的算法流程可知，可進(jìn)行并行化分析的是1、3、4步驟，其中第一步屬于矩陣計算，第三步涉及特征值求解的計算，第四步涉及K-means聚類的計算。從后面實驗部分三個核函數(shù)的運(yùn)算時間對比可知，這三個部分占了算法總體運(yùn)行時間的大部分，且特征值求解過程是最費時間的，具體的并行過程下面一一述之：

3.1矩陣的并行計算

數(shù)據(jù)挖掘算法多半涉及大量的矩陣操作，社區(qū)挖掘也不例外。本文使用cuBLAS程序庫實現(xiàn)矩陣的并行計算操作，采用CUSP支持庫實現(xiàn)對稀疏矩陣的并行計算。cuBLAS利用GPU加速向量、矩陣的線性運(yùn)算，比如說cublasSgemm用來處理單精度矩陣，也就是float型的乘法運(yùn)算。cublasSasum()用來實現(xiàn)矩陣的加法運(yùn)算。比如說拉普拉斯矩陣的計算過程中，即是用cublasSasum()函數(shù)求得。

3.2特征值求解的并行計算

在對拉普拉斯矩陣進(jìn)行特征值分解的過程中，由于矩陣是對稱半正定的，故本文用Lanczos法將對稱矩陣通過正交相似變換成三對角矩陣 ，即：

則L的特征值和特征向量，可通過T求解出[10]。再通過QR方法求解出T的特征值和特征向量[13]。因此，本文用Lanczos和QR相結(jié)合的辦法求取矩陣的特征值，Lanczos-QR法的算法流程如下：

輸入:拉普拉斯矩陣L單位向量;v1(n*m),v0=0,β1=01、For=1,2,…,m wj=Lvj-βjvj-1 αj= wj=wj-αjvj βj=‖wj‖ vj+1=wj/βj+1輸出:T2、QR:forK=1,2,…Tk=QKRKTk+1=QTKTKQK輸出:L的特征值和特征向量

從算法流程可知，上述算法主要也是由矩陣運(yùn)算組成。而拉普拉斯矩陣在大規(guī)模的數(shù)據(jù)集中，也是有稀疏性的，因此Lanczos-QR算法的并行計算也主要通過cuBLAS和CUSP組合實現(xiàn)。

4實驗

4.1實驗環(huán)境和實驗數(shù)據(jù)

本文的PC機(jī)硬件為：CPU，Intel Pentium G640(雙核)，主頻2.80 GHz，內(nèi)存2 GB；nVIDIA顯卡，GeForce GT730，1 GB顯存。軟件環(huán)境為：Windows XP sp3，Visual C++ 2010，CUDA 6.5。

測試數(shù)據(jù)集取自文獻(xiàn)[8]的BlogCatalog社交網(wǎng)站數(shù)據(jù)，數(shù)據(jù)集的相關(guān)參數(shù)。BlogCatalog數(shù)據(jù)集采集了10 312個用戶在39個博文分類目錄下的交互，如轉(zhuǎn)發(fā)等，每個用戶平均發(fā)布1.6個類別的博文。

4.2算法效率對比

本文分別實現(xiàn)了串行和并行的社區(qū)發(fā)現(xiàn)算法，用于進(jìn)行并行算法的性能對比。本文共實現(xiàn)了三個核函數(shù)：Laplace_CU<<>>,Lanczos_QR<<>>,K_means<<>>，上述式子中m,n分別是拉普拉斯矩陣L的行數(shù)和列數(shù)，K為前K小特征向量個數(shù)和聚類個數(shù)。為測試算法的并行效率，實驗1分別選取BlogCatalog數(shù)據(jù)集中選取1000、2000、3000、4000、5000個節(jié)點進(jìn)行測試，并設(shè)定挖掘的社團(tuán)個數(shù)為50，測試結(jié)果如圖1所示。

圖1　BlogCatalog上各部分運(yùn)行時間隨數(shù)據(jù)集大小的變化

從圖1中可以看出，總體而言本文提出的并行算法的各部分執(zhí)行時間都有明顯的減少。隨著數(shù)據(jù)集的變大Lanczos_QR求取特征值的計算可以得到3-10倍的加速，而Laplace的求取和K_means的計算過程中，時間變化并不大，但是CUDA并行基本上也有2倍左右的加速。

不過K_means在并行的過程中，由于受到聚類個數(shù)K值和迭代次數(shù)的影響，運(yùn)行時間不太穩(wěn)定。本文的下一步工作之一就是探索迭代算法中迭代次數(shù)可由程序改變的時候，并行迭代算法的網(wǎng)格和線程設(shè)計，以及并行迭代算法的衡量。

對比圖1的縱軸，發(fā)現(xiàn)Lanczos_QR和K_means占了整個算法運(yùn)行時間的85%以上，也就是說特征向量的并行化和聚類的并行化是整個算法改進(jìn)的重點，探索特征向量求取更快速的算法和更深程度的并行化是我們下一步研究內(nèi)容。

上述三部分的時間比較，已經(jīng)考慮了各步驟中CPU和GPU的通信時間，整個算法的時間加速比如下圖所示。

圖2　SpectralDim隨數(shù)據(jù)集變化的運(yùn)行時間

圖3　SpectralDim的加速比變化

可以看到隨著數(shù)據(jù)集大小變大，GPU上面的運(yùn)行時間基本上沒有發(fā)生變化，從圖3可以看出整個算法的加速比在6～8之間。

實驗1是對本文算法內(nèi)部的縱向比較，為了了解本文算法的整體性能，筆者進(jìn)行了實驗2。實驗2用整個BlogCatalog數(shù)據(jù)集分別測試本文算法_CPU、本文算法_GPU、SocioDim算法的運(yùn)行時間和算法性能。

圖4　算法運(yùn)算時間比

圖4表明，SpectralDim_GPU的運(yùn)算速度比其余兩者都高，而SocioDim的運(yùn)算速度比SpectralDim_CPU略高。由于兩者的差別只在于最后聚類部分，本文采用K_means算法，而SocioDim采用LIBSVM。這個表現(xiàn)和K_means和SVM的時間復(fù)雜度不太相符，本文猜測是SVM中強(qiáng)制定義了迭代次數(shù)，而本文的K_means是尋找最優(yōu)聚類而導(dǎo)致的。

為了衡量算法的社區(qū)發(fā)現(xiàn)效果，本文采用F1、accuracy來衡量算法性能。

下圖表示隨著訓(xùn)練集百分比(訓(xùn)練集占整個數(shù)據(jù)集的百分比)的增加，算法性能的變化。

圖5　Accuracy對比　　　　　圖6　F1-measure對比

從圖中可以看出，隨著訓(xùn)練集所占比重的增加，三種算法的準(zhǔn)確率也隨著增加。不過總體上SocioDim的accuracy略高于本文所設(shè)計的算法，但是F1的變化和訓(xùn)練集比重關(guān)系不大，三種算法的F1均有高有低。

總的來說，通過實驗1和實驗2，我們可以得出這樣的結(jié)論：基于CUDA平臺設(shè)計的并行SpectralDim算法，能有效處理高維數(shù)據(jù)，在社區(qū)發(fā)現(xiàn)準(zhǔn)確性的前提下，能有效提高運(yùn)行速度，一定程度上能解決社區(qū)發(fā)現(xiàn)算法受制于大規(guī)模數(shù)據(jù)集的問題。

5結(jié)束語

本文在CUDA架構(gòu)下設(shè)計并實現(xiàn)了并行社區(qū)發(fā)現(xiàn)算。實驗表明，本文算法保證準(zhǔn)確性的前提下，能有效提高運(yùn)算速度，可加速5～8倍左右，提高了社區(qū)挖掘算法處理大規(guī)模數(shù)據(jù)集的能力，但后續(xù)工作仍需要處理內(nèi)存占用率等。

參考文獻(xiàn)

[1]Wu F,Huberman B A.Finding Communities in Linear Time:A Physics Approach[J].The European Physical Journal B-Condensed Matter and Complex Systems,2004,38(2):331-338.

[2]Newman M E J,Girvan M.Finding and Evaluating Community Structure in Networks[J].Physical Review E,2004,69(2):026113.

[3]Von Luxburg U.A Tutorial on Spectral Clustering[J].Statistics and Computing,2007,17(4):395-416.

[4]Newman M E J.Finding Community Structure in Networks Using the Eigenvectors of Matrices[J].Physical Review E,2006,74(3):036104.

[5]郭進(jìn)時，湯紅波，葛國棟.一種聯(lián)合拓?fù)渑c屬性的社區(qū)模糊劃分算法[J].計算機(jī)工程,2013(11):35-40.

[6]Seunghyeon Moon,Jae-Gil Lee,Minseo Kang.Scalable Community Detection From Networks by Computing Edge Betweenness on MapReduce[C]//Big Data and Smart Computing (BIGCOMP),2014 International Conference on,vol.,no.,145,148,15-17 Jan. 2014.

[7]Garland M,Le Grand S,Nickolls J,et al.Parallel Computing Experiences with CUDA[J].IEEE Micro,2008(4):13-27.

[8]Kirk D.NVIDIACUDA Software and GPU Parallel Computing Architecture[C]//ISMM,2007,7:103-104.

[9]Tang L,Liu H.Leveraging Social Media Networks for classification[J].Data Mining and Knowledge Discovery,2011,23(3):447-478.

[10]Matam K K,Kothapalli K.GPU Accelerated Lanczos Algorithm with Applications[C]// Advanced Information Networking and Applications (WAINA),2011 IEEE Workshops of International Conference on , vol., no., pp.71,76, 22-25 March 2011.

[11]Varamesh A,Akbari M K,Fereiduni M,et al.Distributed Clique Percolation Based Community Detection on Social Networks Using MapReduce,[C]// Information and Knowledge Technology (IKT), 2013 5th Conference on , vol., no., pp.478,483, 28-30 May 2013.

[12]Lunagariya D C,Somayajulu D V L N,Krishna P R.SE-CDA:A Scalable and Efficient Community Detection Algorithm[C]//ta (Big Data), 2014 IEEE International Conference on , vol., no., pp.877,882, 27-30 Oct. 2014.

[13]Zhou K X,Roumeliotis S.A Sparsity-aware QR Decomposition Algorithm for Efficient Cooperative Localization[C]//Robotics and Automation (ICRA),2012 IEEE International Conference on. IEEE, 2012:799-806.

收稿日期：2015-12-07

基金項目：國家自然科學(xué)基金(61363027)

作者簡介：蔣莉芳(1991- )，女，碩士研究生，主研方向：數(shù)據(jù)挖掘、輿情分析。

文章編號：1674- 4578(2016)02- 0046- 04

中圖分類號：TP311.13

文獻(xiàn)標(biāo)識碼：A

Parallel Spectral-cluster Algorithm for Social Community Mining Based on CUDA

Jiang Lifang, Su Yidan, Qin Hua

(SchoolofComputerandElectronicInformation,GuangxiUniversity,NanningGuangxi530004,China)

Abstract:It is a problem for computing efficiency when mining towards social networks and social media because of the feature of magnitude and high-dimensionality. To solve this problem, the paper uses CUDA parallel architecture to propose a parallel spectral-cluster algorithm for community-mining. It firstly reduces the high-dimensional social network data sets and then improves the efficiency of spectral-cluster algorithm with parallel computing capabilities of CUDA. The experiments show that the algorithm can do effective improvement to the speed of community-discovering and has an increase of 5～8 times for the efficiency of parallel computing compared with conventional algorithm, it presents a new thinking for community-mining computing.

Key words:community mining; CUDA; parallel computing; spectral-cluster; large-scale data