基于CUDA的并行譜聚類(lèi)社區(qū)挖掘算法*
2016-07-23 08:52:02蔣莉芳蘇一丹
山西電子技術(shù) 2016年2期
蔣莉芳，蘇一丹，覃 華
(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)
?
基于CUDA的并行譜聚類(lèi)社區(qū)挖掘算法*
蔣莉芳，蘇一丹，覃華
(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)
摘要：社會(huì)網(wǎng)絡(luò)和社交媒體數(shù)據(jù)具有大規(guī)模、高維度的特性，社區(qū)挖掘算法的計(jì)算效率是一個(gè)值得研究的問(wèn)題。針對(duì)此問(wèn)題，本文利用CUDA并行計(jì)算架構(gòu)，提出一種并行的譜聚類(lèi)社區(qū)挖掘算法，首先對(duì)高維的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行降維，再用CUDA的并行計(jì)算能力提高譜聚類(lèi)算法的計(jì)算效率。實(shí)驗(yàn)表明，本文所提算法能有效地提高社區(qū)挖掘算法的計(jì)算速度，并行計(jì)算效率較常規(guī)算法有5～8倍的提高，為社區(qū)挖掘計(jì)算提出一種新的思路。
關(guān)鍵詞：社區(qū)挖掘；CUDA；并行計(jì)算；譜聚類(lèi)；大規(guī)模網(wǎng)絡(luò)
1概述
快速增長(zhǎng)的社交媒體，形成了很多規(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ù)算法的性能其實(shí)都很優(yōu)越，如Luxburg提出的譜聚類(lèi)算法(Spectral Clustering，SC)[3]，通過(guò)求解圖分割問(wèn)題獲得網(wǎng)絡(luò)劃分。Newman提出了Modularity算法[4]，考慮節(jié)點(diǎn)度的分布情況，用兩點(diǎn)間的實(shí)際作用和期望值之差，定義社區(qū)效應(yīng)強(qiáng)度，通過(guò)最大化效應(yīng)強(qiáng)度，獲得最佳的社區(qū)劃分。再比如郭進(jìn)時(shí)等[5]提出的聯(lián)合拓?fù)渑c屬性的社區(qū)模糊劃分算法，用完全相異距離指數(shù)將拓?fù)浣Y(jié)構(gòu)與屬性相結(jié)合，以此作為隸屬關(guān)系建立模糊等價(jià)關(guān)系矩陣，再選擇合適的聚類(lèi)對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。這些算法都能在一定程度上達(dá)到社區(qū)發(fā)現(xiàn)的效果，但這些算法的計(jì)算量都很大。在大數(shù)據(jù)時(shí)代，網(wǎng)絡(luò)社區(qū)規(guī)模越來(lái)越大，時(shí)間復(fù)雜性的弊端，也就顯得尤為突出，特別是還要進(jìn)行多維處理時(shí)，因此需要進(jìn)一步改進(jìn)。并行和分布式計(jì)算是降低總體運(yùn)行時(shí)間的有效途徑，已經(jīng)有學(xué)者在Mapreduce上面進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)的探索，但是總體而言，社區(qū)發(fā)現(xiàn)的并行計(jì)算研究文獻(xiàn)還較少[6，11，12]。本文研究的主要目標(biāo)是利用并行計(jì)算的思想，解決社區(qū)挖掘算法中的時(shí)間需求過(guò)大問(wèn)題。
CUDA(Compute Unified Device Architecture)是NVidia公司設(shè)計(jì)開(kāi)發(fā)的一種在GPU上進(jìn)行通用、并行計(jì)算的編程體系結(jié)構(gòu)[7，8]。本文利用CUDA平臺(tái)實(shí)現(xiàn)對(duì)多維數(shù)據(jù)集的并行譜聚類(lèi)算法(Multi-Dimension Spectral Clustering，SpectralDim)，并用于社區(qū)挖掘算法。譜聚類(lèi)算法對(duì)于社區(qū)網(wǎng)絡(luò)數(shù)據(jù)的高維問(wèn)題，采用拉普拉斯特征向量方式進(jìn)行降維，最后再用聚類(lèi)算法進(jìn)行社區(qū)挖掘。其本身自帶的降維功能，使得其自身時(shí)間復(fù)雜度比其他社區(qū)挖掘算法低。本文利用CUDA并行譜聚類(lèi)算法挖掘社區(qū)信息，提高了挖掘算法對(duì)大規(guī)模社區(qū)數(shù)據(jù)的適用能力。本文實(shí)驗(yàn)使用文獻(xiàn)[9]的數(shù)據(jù)，并將SpectralDim_CPU(不用并行)、SpectralDim_GPU(CUDA并行)與文獻(xiàn)[9]中的SocioDim比較，實(shí)驗(yàn)結(jié)果表明：本文所提算法的計(jì)算準(zhǔn)確率與SocioDim相當(dāng)，但是計(jì)算速度較SocioDim算法快5～8倍，更適合于大規(guī)模社區(qū)挖掘。
2基于譜聚類(lèi)的社區(qū)發(fā)現(xiàn)算法
譜聚類(lèi)算法利用譜分析技術(shù)可將高維數(shù)據(jù)投射到低維子空間，達(dá)到降維的效果。而當(dāng)數(shù)據(jù)擁有多維(Multi-Dimension)特征時(shí)，需要先對(duì)數(shù)據(jù)進(jìn)行效用集成才能進(jìn)行譜聚類(lèi)，文獻(xiàn)[8]采用平均效用法進(jìn)行數(shù)據(jù)集成，并采用譜分析技術(shù)對(duì)數(shù)據(jù)進(jìn)行降維，最后用SVM對(duì)降維后的數(shù)據(jù)進(jìn)行社區(qū)劃分。
從降維和圖分割理論對(duì)譜聚類(lèi)進(jìn)行理解，規(guī)范化拉普拉斯聚類(lèi)算法的目標(biāo)函數(shù)為：
(1)
(2)
則目標(biāo)函數(shù)可轉(zhuǎn)換為如下跡函數(shù)的求解：
(3)
一般的譜聚類(lèi)算法流程如下所示：
輸入:原數(shù)據(jù)集,聚類(lèi)數(shù)目k1、求矩陣的相似性矩陣A以及度矩陣D2、計(jì)算拉普拉斯矩陣L=D-A3、求取L的前k個(gè)最小特征向量4、對(duì)特征向量進(jìn)行聚類(lèi)得到C輸出:聚類(lèi)結(jié)果C
如若數(shù)據(jù)集有多模特征，則在相似度矩陣的計(jì)算過(guò)程中，采用效用集成或者網(wǎng)絡(luò)集成的方式進(jìn)行維度集成，再計(jì)算相似度。
3基于CUDA的并行社區(qū)挖掘算法
接下來(lái)對(duì)本文中運(yùn)用到的譜聚類(lèi)CUDA化的關(guān)鍵技術(shù)以及并行化過(guò)程中所涉及的地方進(jìn)行討論。分析譜聚類(lèi)的算法流程可知，可進(jìn)行并行化分析的是1、3、4步驟，其中第一步屬于矩陣計(jì)算，第三步涉及特征值求解的計(jì)算，第四步涉及K-means聚類(lèi)的計(jì)算。從后面實(shí)驗(yàn)部分三個(gè)核函數(shù)的運(yùn)算時(shí)間對(duì)比可知，這三個(gè)部分占了算法總體運(yùn)行時(shí)間的大部分，且特征值求解過(guò)程是最費(fèi)時(shí)間的，具體的并行過(guò)程下面一一述之：
3.1矩陣的并行計(jì)算
數(shù)據(jù)挖掘算法多半涉及大量的矩陣操作，社區(qū)挖掘也不例外。本文使用cuBLAS程序庫(kù)實(shí)現(xiàn)矩陣的并行計(jì)算操作，采用CUSP支持庫(kù)實(shí)現(xiàn)對(duì)稀疏矩陣的并行計(jì)算。cuBLAS利用GPU加速向量、矩陣的線性運(yùn)算，比如說(shuō)cublasSgemm用來(lái)處理單精度矩陣，也就是float型的乘法運(yùn)算。cublasSasum()用來(lái)實(shí)現(xiàn)矩陣的加法運(yùn)算。比如說(shuō)拉普拉斯矩陣的計(jì)算過(guò)程中，即是用cublasSasum()函數(shù)求得。
3.2特征值求解的并行計(jì)算
在對(duì)拉普拉斯矩陣進(jìn)行特征值分解的過(guò)程中，由于矩陣是對(duì)稱(chēng)半正定的，故本文用Lanczos法將對(duì)稱(chēng)矩陣通過(guò)正交相似變換成三對(duì)角矩陣 ，即：
則L的特征值和特征向量，可通過(guò)T求解出[10]。再通過(guò)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=
從算法流程可知，上述算法主要也是由矩陣運(yùn)算組成。而拉普拉斯矩陣在大規(guī)模的數(shù)據(jù)集中，也是有稀疏性的，因此Lanczos-QR算法的并行計(jì)算也主要通過(guò)cuBLAS和CUSP組合實(shí)現(xiàn)。
4實(shí)驗(yàn)
4.1實(shí)驗(yàn)環(huán)境和實(shí)驗(yà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。
測(cè)試數(shù)據(jù)集取自文獻(xiàn)[8]的BlogCatalog社交網(wǎng)站數(shù)據(jù)，數(shù)據(jù)集的相關(guān)參數(shù)。BlogCatalog數(shù)據(jù)集采集了10 312個(gè)用戶(hù)在39個(gè)博文分類(lèi)目錄下的交互，如轉(zhuǎn)發(fā)等，每個(gè)用戶(hù)平均發(fā)布1.6個(gè)類(lèi)別的博文。
4.2算法效率對(duì)比
本文分別實(shí)現(xiàn)了串行和并行的社區(qū)發(fā)現(xiàn)算法，用于進(jìn)行并行算法的性能對(duì)比。本文共實(shí)現(xiàn)了三個(gè)核函數(shù)：Laplace_CU<<
圖1 BlogCatalog上各部分運(yùn)行時(shí)間隨數(shù)據(jù)集大小的變化
從圖1中可以看出，總體而言本文提出的并行算法的各部分執(zhí)行時(shí)間都有明顯的減少。隨著數(shù)據(jù)集的變大Lanczos_QR求取特征值的計(jì)算可以得到3-10倍的加速，而Laplace的求取和K_means的計(jì)算過(guò)程中，時(shí)間變化并不大，但是CUDA并行基本上也有2倍左右的加速。
不過(guò)K_means在并行的過(guò)程中，由于受到聚類(lèi)個(gè)數(shù)K值和迭代次數(shù)的影響，運(yùn)行時(shí)間不太穩(wěn)定。本文的下一步工作之一就是探索迭代算法中迭代次數(shù)可由程序改變的時(shí)候，并行迭代算法的網(wǎng)格和線程設(shè)計(jì)，以及并行迭代算法的衡量。
對(duì)比圖1的縱軸，發(fā)現(xiàn)Lanczos_QR和K_means占了整個(gè)算法運(yùn)行時(shí)間的85%以上，也就是說(shuō)特征向量的并行化和聚類(lèi)的并行化是整個(gè)算法改進(jìn)的重點(diǎn)，探索特征向量求取更快速的算法和更深程度的并行化是我們下一步研究?jī)?nèi)容。
上述三部分的時(shí)間比較，已經(jīng)考慮了各步驟中CPU和GPU的通信時(shí)間，整個(gè)算法的時(shí)間加速比如下圖所示。
圖2 SpectralDim隨數(shù)據(jù)集變化的運(yùn)行時(shí)間
圖3 SpectralDim的加速比變化
可以看到隨著數(shù)據(jù)集大小變大，GPU上面的運(yùn)行時(shí)間基本上沒(méi)有發(fā)生變化，從圖3可以看出整個(gè)算法的加速比在6～8之間。
實(shí)驗(yàn)1是對(duì)本文算法內(nèi)部的縱向比較，為了了解本文算法的整體性能，筆者進(jìn)行了實(shí)驗(yàn)2。實(shí)驗(yàn)2用整個(gè)BlogCatalog數(shù)據(jù)集分別測(cè)試本文算法_CPU、本文算法_GPU、SocioDim算法的運(yùn)行時(shí)間和算法性能。
圖4 算法運(yùn)算時(shí)間比
圖4表明，SpectralDim_GPU的運(yùn)算速度比其余兩者都高，而SocioDim的運(yùn)算速度比SpectralDim_CPU略高。由于兩者的差別只在于最后聚類(lèi)部分，本文采用K_means算法，而SocioDim采用LIBSVM。這個(gè)表現(xiàn)和K_means和SVM的時(shí)間復(fù)雜度不太相符，本文猜測(cè)是SVM中強(qiáng)制定義了迭代次數(shù)，而本文的K_means是尋找最優(yōu)聚類(lèi)而導(dǎo)致的。
為了衡量算法的社區(qū)發(fā)現(xiàn)效果，本文采用F1、accuracy來(lái)衡量算法性能。
下圖表示隨著訓(xùn)練集百分比(訓(xùn)練集占整個(gè)數(shù)據(jù)集的百分比)的增加，算法性能的變化。
圖5 Accuracy對(duì)比 圖6 F1-measure對(duì)比
從圖中可以看出，隨著訓(xùn)練集所占比重的增加，三種算法的準(zhǔn)確率也隨著增加。不過(guò)總體上SocioDim的accuracy略高于本文所設(shè)計(jì)的算法，但是F1的變化和訓(xùn)練集比重關(guān)系不大，三種算法的F1均有高有低。
總的來(lái)說(shuō)，通過(guò)實(shí)驗(yàn)1和實(shí)驗(yàn)2，我們可以得出這樣的結(jié)論：基于CUDA平臺(tái)設(shè)計(jì)的并行SpectralDim算法，能有效處理高維數(shù)據(jù)，在社區(qū)發(fā)現(xiàn)準(zhǔn)確性的前提下，能有效提高運(yùn)行速度，一定程度上能解決社區(qū)發(fā)現(xiàn)算法受制于大規(guī)模數(shù)據(jù)集的問(wèn)題。
5結(jié)束語(yǔ)
本文在CUDA架構(gòu)下設(shè)計(jì)并實(shí)現(xiàn)了并行社區(qū)發(fā)現(xiàn)算。實(shí)驗(yà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)時(shí)，湯紅波，葛國(guó)棟.一種聯(lián)合拓?fù)渑c屬性的社區(qū)模糊劃分算法[J].計(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
基金項(xiàng)目：國(guó)家自然科學(xué)基金(61363027)
作者簡(jiǎn)介：蔣莉芳(1991- )，女，碩士研究生，主研方向：數(shù)據(jù)挖掘、輿情分析。
文章編號(hào)：1674- 4578(2016)02- 0046- 04
中圖分類(lèi)號(hào)：TP311.13
文獻(xiàn)標(biāo)識(shí)碼：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
