袁璐 鄭策 山東工程職業(yè)技術(shù)大學(xué)

在大數(shù)據(jù)時(shí)代下，聚類這種不用監(jiān)督的學(xué)習(xí)算法占有非常重要的地位。隨著科技的不斷發(fā)展，聚類算法的研究也取得了非常大的進(jìn)步。而本文主要對(duì)圖聚類的算法進(jìn)行分析和研究，并在劃分的圖聚類中，對(duì)點(diǎn)和點(diǎn)之間距離的計(jì)算方法重點(diǎn)進(jìn)行比較同時(shí)也比較其對(duì)聚類結(jié)果的硬性。還有因社會(huì)關(guān)系網(wǎng)絡(luò)圖中的點(diǎn)是沒(méi)有坐標(biāo)值的，因此無(wú)法使用曼哈坦距離和歐幾里得距離，但可以使用K-medoids 聚類算法。在使用此聚類算法時(shí)，可以使用隨機(jī)漫步距離算法和最短距離算法，社會(huì)關(guān)系網(wǎng)絡(luò)圖通過(guò)DBLP 數(shù)據(jù)集構(gòu)成各個(gè)子圖，并結(jié)合相關(guān)實(shí)驗(yàn)數(shù)據(jù)對(duì)兩種算法的優(yōu)缺點(diǎn)進(jìn)行驗(yàn)證，從而進(jìn)一步得到最短距離算法獲得的聚類效果最佳。

一、聚類、圖聚類以及社會(huì)網(wǎng)絡(luò)綜述

聚類指的是把數(shù)據(jù)集分成若干類或簇的過(guò)程，從而使不同類數(shù)據(jù)對(duì)象的相似度較低的讓同時(shí)使同類數(shù)據(jù)對(duì)象的相似度較高。而目前的聚類算法有：層次聚類算法、網(wǎng)格聚類算法、劃分聚類算法、密度聚類算法以及模型聚類算法等。

在對(duì)聚類進(jìn)行分析時(shí)，其變體是一項(xiàng)非常有挑戰(zhàn)的研究課題，即圖聚類。而其主要指的是把圖中相關(guān)的邊分以及相對(duì)連接緊密的結(jié)點(diǎn)組成一個(gè)可以用一個(gè)抽象結(jié)點(diǎn)來(lái)表示的子圖。其子圖內(nèi)各結(jié)點(diǎn)的相似性比較高，但子圖之間的結(jié)點(diǎn)只有較低的相似性。另外圖聚類有許多不同的方式，突出的有基于密度的聚類、Markov 聚類以及譜聚類等。

社會(huì)網(wǎng)絡(luò)分析在20 世紀(jì)30 年代被提出，并成為一種相對(duì)比較重要的社會(huì)定量研究方法。其主要指社會(huì)成員以及社會(huì)成員之間關(guān)系的集合，并用來(lái)表示成員間各種社會(huì)關(guān)系的邊以及各成員的節(jié)點(diǎn)，從而組成圖結(jié)構(gòu)，進(jìn)而對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行描述[2]。另外，社會(huì)關(guān)系有很多種表現(xiàn)形式，例如：上下級(jí)之間的關(guān)系、文章合著關(guān)系、朋友之間的關(guān)系以及科研合作關(guān)系等。還有社會(huì)網(wǎng)絡(luò)關(guān)系的圖聚類算法主要有：Kernighan-lin 算法、G-N 算法、Newman 算法、過(guò)濾算法以及譜平分算法等。

二、圖聚類的算法

1、最短路徑距離算法

在圖論研究中比較經(jīng)典的一個(gè)算法問(wèn)題就是最短路徑問(wèn)題，而最短路徑問(wèn)題時(shí)在圖中的兩個(gè)點(diǎn)之間找一個(gè)最短的路。最短路徑距離算法也叫作Dijkstra 算法，其思想是：設(shè)G=（V,E,W）的帶權(quán)有向圖。也就是說(shuō)先把圖中的頂點(diǎn)幾何V 組成兩組，一組是對(duì)最短路徑的頂點(diǎn)集合（S）已求出，另一組是對(duì)其余最短路徑的頂點(diǎn)集合（U）未求出，然后把未求出最短路徑的頂點(diǎn)根據(jù)最短路徑長(zhǎng)度的增長(zhǎng)順序依次加入到已求出最短路徑的頂點(diǎn)集合中去。

2、隨機(jī)漫步距離算法

若P 是一個(gè)由多個(gè)（N）頂點(diǎn)組成的圖GN×N 轉(zhuǎn)移概率矩陣，那么此矩陣的第i 行第j 列的元素為第i 個(gè)頂點(diǎn)一步跳轉(zhuǎn)到第j 個(gè)頂點(diǎn)的概率值；若 是隨機(jī)漫步從第i 個(gè)頂點(diǎn)到第j 個(gè)頂點(diǎn)走的最大步長(zhǎng)，并假設(shè)隨機(jī)漫步起始概率為c ∈（0,1），那么隨機(jī)漫步的第i 個(gè)頂點(diǎn)到第j 個(gè)頂點(diǎn)距離的定義為：其中T 指的是第i 個(gè)頂點(diǎn)到第j 個(gè)頂點(diǎn)的一條路徑，步長(zhǎng)使lengh（T），對(duì)應(yīng)的轉(zhuǎn)移概率是P（T）。而隨機(jī)漫步距離矩陣指的是各頂點(diǎn)之間的隨機(jī)漫步距離組成的矩陣，其公示為：，其中，P 是圖G 的轉(zhuǎn)移概率，Ri是l 步內(nèi)可達(dá)到的隨機(jī)漫步距離矩陣。

3、K-medoids 算法

K-medoids 算法的工作過(guò)程為：先隨機(jī)從n 個(gè)數(shù)據(jù)對(duì)象中挑選k 個(gè)對(duì)象當(dāng)作初始聚類的中心，而剩下的其他對(duì)象就按照他們和這些聚類中心的距離依次分配到和其最相似的聚類；其次，對(duì)各個(gè)聚類的新聚類中心進(jìn)行再次計(jì)算時(shí)，可選擇此聚類中距離均值點(diǎn)最近的真實(shí)點(diǎn)，并不斷對(duì)這個(gè)過(guò)程進(jìn)行重復(fù)，從而使各個(gè)點(diǎn)的分配不在出現(xiàn)變化的同時(shí)也能得到滿足。在這個(gè)算法中，初始聚以K 個(gè)對(duì)象為中心點(diǎn)，之后以局部最佳結(jié)束，但這個(gè)方法對(duì)孤立點(diǎn)非常敏感。因此，在對(duì)這個(gè)算法進(jìn)行改進(jìn)時(shí)，初始聚類的中心點(diǎn)先隨機(jī)選取一個(gè)來(lái)當(dāng)做對(duì)象；其次，對(duì)第二個(gè)聚類中心點(diǎn)進(jìn)行選取時(shí)，其和初始聚類的中心點(diǎn)的距離要最遠(yuǎn)；然后到選取去第三個(gè)聚類中心點(diǎn)時(shí)，和第二個(gè)聚類中心點(diǎn)的挑取一樣，并依次類推，直到第k 個(gè)聚類中心點(diǎn)為止。

三、實(shí)驗(yàn)

1、衡量指標(biāo)

衡量指標(biāo)用density 來(lái)表示，若圖是無(wú)向圖，那么就先要對(duì)整個(gè)大圖進(jìn)行統(tǒng)計(jì)，而圖在沒(méi)有進(jìn)行分割之前，總共有n 條邊，然后依次計(jì)算k 類的每類包含的點(diǎn)之間的邊數(shù)，假如分別是n1,n2,...,nk,那么最后的計(jì)算就是density=（n1+n2+...+nk）/n。

當(dāng)用程序?qū)⑦@個(gè)算法進(jìn)行實(shí)現(xiàn)后，其運(yùn)行程序收集數(shù)據(jù)，指在每個(gè)K 值的情況下，需要進(jìn)行10 次分類，之后取10 次分類比率的比均值當(dāng)做前k 值下的最后比率density，通過(guò)兩個(gè)算法的density 值比較出優(yōu)劣，其中，最短距離算法得到的比率用density1 表示，隨機(jī)漫步距離算法得到的比率用density2 表示，對(duì)比如圖1 所示。

圖1 隨機(jī)漫步距離和最短距離的比率圖

從圖中可以看出，隨著分的類逐漸增多，類和類之間的邊也就增多，相反類內(nèi)部的邊就越少，因此density 呈現(xiàn)下降趨勢(shì)；還有最短距離算法和隨機(jī)漫步距離算法相比，最短距離算法獲得的density 較高。

2、聚類效果

使用最短距離算法，把大小數(shù)據(jù)劃分成15 小類，每類數(shù)據(jù)是相同領(lǐng)域合著關(guān)系比較緊密的作者編號(hào)，通過(guò)實(shí)驗(yàn)證明，分類成效非常理想。結(jié)合每個(gè)作者之間合著文章的論文數(shù)量，畫出分類之前的分布圖（如圖2），經(jīng)過(guò)重復(fù)迭代，最后分成15 小類，而這時(shí)的分布圖如圖3.最后實(shí)驗(yàn)情況和實(shí)際情況相同，分類結(jié)果比較理想。

圖2 分類前的點(diǎn)分布圖

圖3 分類后的點(diǎn)分布圖

四、結(jié)束語(yǔ)

在圖聚類進(jìn)行研究時(shí)，使用隨機(jī)漫步算法和最短距離算法這兩種不同的距離算法來(lái)衡量各個(gè)點(diǎn)之間的相異度。而DBLP 數(shù)據(jù)集建立的合作關(guān)系社會(huì)網(wǎng)絡(luò)圖，使用K-medoids 聚類算法，把大圖分為K 類，使相同領(lǐng)域合著關(guān)系比較緊密的劃分在同一類當(dāng)中，最后通過(guò)實(shí)驗(yàn)數(shù)據(jù)得出，最短距離算法獲得的聚類效果比較理想。