劉合富，劉 蓉，趙 強(qiáng)

（1.華中師范大學(xué)a.信息化辦公室；b.物理科學(xué)與技術(shù)學(xué)院，武漢 430079；2.武漢理工大學(xué) 經(jīng)濟(jì)學(xué)院，武漢 430070）

0 引言

聚簇劃分被廣泛應(yīng)用于人與人、人與事物之間的社會(huì)關(guān)系的劃分上。研究社區(qū)的聚簇劃分對(duì)于社區(qū)拓?fù)浣Y(jié)構(gòu)、變動(dòng)規(guī)律、事件預(yù)測(cè)等具有重要的理論意義和現(xiàn)實(shí)價(jià)值。聚簇劃分的首要任務(wù)是社區(qū)網(wǎng)絡(luò)關(guān)系的發(fā)現(xiàn)?，F(xiàn)實(shí)社區(qū)活動(dòng)通過(guò)用戶與事件的互動(dòng)，往往會(huì)產(chǎn)生一些社區(qū)網(wǎng)絡(luò)關(guān)系，例如商場(chǎng)商品銷售、銀企信貸關(guān)系、社交網(wǎng)絡(luò)活動(dòng)等，都可以通過(guò)用戶活動(dòng)構(gòu)成事件之間的強(qiáng)弱關(guān)系[1—3]。將事件關(guān)聯(lián)點(diǎn)當(dāng)作網(wǎng)絡(luò)空間節(jié)點(diǎn)，將用戶的轉(zhuǎn)移需求作為邊，將需求的有向關(guān)系作為邊的方向，將需求強(qiáng)弱程度看作網(wǎng)絡(luò)的邊權(quán)，于是上述活動(dòng)事件節(jié)點(diǎn)之間能構(gòu)成一種基于有向加權(quán)網(wǎng)絡(luò)的社交關(guān)系。將加權(quán)網(wǎng)絡(luò)關(guān)系圖引入事件需求分析，既能清晰地展示事件之間是否存在關(guān)聯(lián)，又能直接明了地表示關(guān)聯(lián)程度的強(qiáng)弱，對(duì)個(gè)性化推薦、社群劃分、社區(qū)發(fā)現(xiàn)等應(yīng)用性研究具有重要意義[4]。許多學(xué)者進(jìn)行了社區(qū)聚簇劃分和聚類分析研究，付立東等（2019）[5]將無(wú)向網(wǎng)絡(luò)圖轉(zhuǎn)換為星形鄰域網(wǎng)絡(luò)，建立相似度模型，節(jié)點(diǎn)相似度值以共鄰節(jié)點(diǎn)數(shù)占鄰居節(jié)點(diǎn)總數(shù)的比重來(lái)計(jì)算，用于復(fù)雜網(wǎng)絡(luò)社區(qū)劃分；邱德紅等（2012）[6]提出了一種基于邊權(quán)值和方向的有向圖相似度算法用于聚類發(fā)掘；馬鐵民等（2019）[7]提出了基于用戶相似度的Si-user Walker 算法,以無(wú)向圖節(jié)點(diǎn)發(fā)生事件次數(shù)和類別數(shù)為指標(biāo)構(gòu)造相似度模型，用于解決網(wǎng)絡(luò)社交事件推薦問(wèn)題；任淑霞等（2019）[8]采用馬爾科夫鏈多步轉(zhuǎn)移概率矩陣作為相似度矩陣，完成節(jié)點(diǎn)相似圖的重構(gòu)，采用譜聚類實(shí)現(xiàn)社區(qū)劃分。以上相似度計(jì)算方法雖然用在社區(qū)劃分中取得了一定成果，但仍存在一些不足：（1）網(wǎng)絡(luò)圖中節(jié)點(diǎn)間直連信息被忽略，僅考慮到鄰域節(jié)點(diǎn)連接關(guān)系；（2）圖中節(jié)點(diǎn)與鄰居節(jié)點(diǎn)在邊方向、邊權(quán)等方面的雙向連接關(guān)系未充分體現(xiàn)；（3）無(wú)法呈現(xiàn)節(jié)點(diǎn)間事件發(fā)生的主被動(dòng)、信息傳遞的正逆向、雙向邊權(quán)的對(duì)稱強(qiáng)度等特征信息變化的問(wèn)題。以此構(gòu)建成的網(wǎng)絡(luò)圖，其節(jié)點(diǎn)相似性度量不夠全面，導(dǎo)致聚簇劃分精度不夠高。

為提高有向網(wǎng)絡(luò)圖節(jié)點(diǎn)相似度計(jì)算的準(zhǔn)確度，本文基于網(wǎng)絡(luò)社區(qū)用戶活動(dòng)特征，充分考慮節(jié)點(diǎn)間連接強(qiáng)度、共鄰節(jié)點(diǎn)相似性、邊方向作用、邊權(quán)值對(duì)稱性等對(duì)相似度的影響，提出雙向度量相似度BDMS（Bi-Directional Measurement Similarity）算法。算法首先建立符合社區(qū)活動(dòng)事務(wù)特征的馬爾科夫鏈矩陣；然后，構(gòu)建有向加權(quán)圖，其中節(jié)點(diǎn)間的相似度主要包含共鄰相似度和直連相似度兩個(gè)部分，并將影響相似度度量的節(jié)點(diǎn)直連強(qiáng)度、相鄰節(jié)點(diǎn)數(shù)、邊方向、邊權(quán)值等要素納入計(jì)算，形成相似度鄰接矩陣；最后，結(jié)合譜聚類無(wú)向圖切圖方式尋找矩陣的相關(guān)特征向量進(jìn)行聚簇劃分。為了驗(yàn)證BDMS算法的合理性和有效性，以更清晰地獲得聚類分析效果，本文基于真實(shí)的高校學(xué)生生活和學(xué)習(xí)數(shù)據(jù)對(duì)其進(jìn)行驗(yàn)證。

1 有向加權(quán)圖構(gòu)建

社區(qū)網(wǎng)絡(luò)空間節(jié)點(diǎn)的事件發(fā)生關(guān)系通常采用圖的結(jié)構(gòu)表示，圖是在分析具有連接關(guān)系的科學(xué)和工程問(wèn)題時(shí)常用的一種數(shù)據(jù)結(jié)構(gòu)[9]。將空間位置或事件看作圖的節(jié)點(diǎn)，節(jié)點(diǎn)之間的關(guān)系表示成圖的邊，包含節(jié)點(diǎn)間動(dòng)態(tài)轉(zhuǎn)移事件數(shù)量的權(quán)重、方向等相互關(guān)聯(lián)的特征信息，形成一張有向加權(quán)圖。圖中節(jié)點(diǎn)關(guān)系的生成，重點(diǎn)在于圖邊的定義、權(quán)值計(jì)算以及邊方向的確定。考慮到事件發(fā)生過(guò)程中節(jié)點(diǎn)關(guān)系的復(fù)雜性，多數(shù)相似度算法采用無(wú)向加權(quán)圖來(lái)表示節(jié)點(diǎn)間的事件連接關(guān)系，但是無(wú)向加權(quán)圖忽略了很多節(jié)點(diǎn)間主被動(dòng)關(guān)系、互轉(zhuǎn)強(qiáng)度對(duì)稱性、信息流動(dòng)方向性等特征信息，難以較為全面地呈現(xiàn)節(jié)點(diǎn)之間相似關(guān)系的實(shí)質(zhì)。例如：將高校學(xué)生網(wǎng)上選修公選課事件視為一項(xiàng)社區(qū)網(wǎng)絡(luò)活動(dòng)，公選課之間的選課人流量轉(zhuǎn)移關(guān)系是雙向的，隨著教學(xué)管理和培養(yǎng)計(jì)劃的變化，學(xué)校提供不同課程的優(yōu)化策略，課程之間因熱度或需求不同可能出現(xiàn)學(xué)生選課次數(shù)互轉(zhuǎn)現(xiàn)象，該現(xiàn)象若以有向加權(quán)圖表示能更清晰地勾畫(huà)出強(qiáng)弱不同的雙向轉(zhuǎn)移關(guān)系。因此，用有向加權(quán)圖表示節(jié)點(diǎn)事件所發(fā)生的關(guān)系和特征，具有更好的代表性和呈現(xiàn)性。

本文基于具有馬爾科夫特征的社區(qū)活動(dòng)事件的轉(zhuǎn)移關(guān)系，采用有向加權(quán)圖的方式表示。將空間位置節(jié)點(diǎn)間發(fā)生的事件數(shù)量轉(zhuǎn)移看作是一個(gè)馬爾科夫過(guò)程，具有n個(gè)節(jié)點(diǎn)的狀態(tài)空間M={1，2，…，n}，以P來(lái)表示空間M中節(jié)點(diǎn)的事件狀態(tài)轉(zhuǎn)移概率矩陣，如式（1）所示。

將公式（1）抽象為一個(gè)由空間節(jié)點(diǎn)、有向邊及邊權(quán)組成的有向加權(quán)圖，記為:

其中，V={v1，v2，…，vn}是馬爾科夫鏈節(jié)點(diǎn)的集合；是代表現(xiàn)實(shí)世界中兩個(gè)實(shí)體間的轉(zhuǎn)移關(guān)系的雙向邊的集合；W={W11，W12，…，Wnn}是→中邊權(quán)的集合，當(dāng)i≠j時(shí)，Wij為馬爾科夫鏈轉(zhuǎn)移概率Pij；(vi，vj)表示由節(jié)點(diǎn)vi指向節(jié)點(diǎn)vj的邊；W對(duì)應(yīng)于有向邊(vi，vj)的權(quán)Wij記為轉(zhuǎn)移概率Pij，若Wij=0，則表示節(jié)點(diǎn)vi到vj無(wú)連接邊。

式（2）實(shí)現(xiàn)了從馬爾科夫鏈的轉(zhuǎn)移概率矩陣向有向加權(quán)圖的轉(zhuǎn)換，具有方向性和關(guān)聯(lián)關(guān)系強(qiáng)度的轉(zhuǎn)移概率的值越大，表示節(jié)點(diǎn)間的關(guān)系越重要或聯(lián)系越頻繁[10]。式（2）中以節(jié)點(diǎn)間的轉(zhuǎn)移概率來(lái)表示的圖中的邊連接權(quán)重具有方向性且可能具有不對(duì)稱性，所涉及的節(jié)點(diǎn)關(guān)系、邊方向、邊權(quán)重等屬性具備明顯的事件變化特征。將轉(zhuǎn)移概率矩陣P轉(zhuǎn)化為有向加權(quán)圖，主要是為了滿足社區(qū)網(wǎng)絡(luò)節(jié)點(diǎn)在聚類分析中的聚簇劃分需要，能更好地了解社區(qū)結(jié)構(gòu)、功能以及預(yù)測(cè)節(jié)點(diǎn)分布的行為特征。因此，以馬爾科夫鏈形成的事件轉(zhuǎn)移過(guò)程可以抽象為一張有向加權(quán)圖。

2 有向加權(quán)圖的節(jié)點(diǎn)相似度

2.1 相似度算法分析

計(jì)算圖節(jié)點(diǎn)相似度是進(jìn)行聚類分析的基礎(chǔ)，在社區(qū)劃分、協(xié)同過(guò)濾、信息檢索、人際關(guān)系網(wǎng)絡(luò)分析等領(lǐng)域有廣泛的應(yīng)用[11]。傳統(tǒng)的相似度算法采用局部網(wǎng)絡(luò)連接信息方法，通過(guò)比較鄰域節(jié)點(diǎn)的向量角度關(guān)系、距離大小或圖拓?fù)浣Y(jié)構(gòu)特點(diǎn)來(lái)確定節(jié)點(diǎn)間的相似性，以反映兩個(gè)節(jié)點(diǎn)的相似程度。常見(jiàn)的算法有余弦相似度[12]、Jaccard 相似度[13]、SimRank 相似度[14]等。其中，余弦相似度衡量節(jié)點(diǎn)間的相似性是通過(guò)相鄰節(jié)點(diǎn)向量的夾角余弦值來(lái)確定，結(jié)果與向量的權(quán)重大小無(wú)關(guān)，僅與向量的方向相關(guān)；Jaccard相似度認(rèn)為節(jié)點(diǎn)間的共同鄰居數(shù)越多，在與兩個(gè)節(jié)點(diǎn)相連的全部節(jié)點(diǎn)總數(shù)中占比越高，相似度就越高；SimRank 相似度認(rèn)為如果有共鄰節(jié)點(diǎn)與兩個(gè)節(jié)點(diǎn)相連，共鄰節(jié)點(diǎn)之間相似度越高，兩個(gè)節(jié)點(diǎn)相似度也越高。以上算法僅考慮了共鄰節(jié)點(diǎn)的相關(guān)信息，但在節(jié)點(diǎn)間存在雙向轉(zhuǎn)移事件關(guān)系時(shí)，至少存在以下不足：（1）未考慮到共鄰節(jié)點(diǎn)做貢獻(xiàn)時(shí)具有雙向性，并且方向不同、大小不同，貢獻(xiàn)可能存在差異。（2）當(dāng)兩個(gè)節(jié)點(diǎn)直接相連時(shí)，產(chǎn)生的親密性作用被忽略，假如不存在共鄰節(jié)點(diǎn)，則其相似度為0，與現(xiàn)實(shí)不符。（3）采用聚類分析進(jìn)行聚簇劃分的準(zhǔn)確率不高。從兩個(gè)節(jié)點(diǎn)之間的相似關(guān)聯(lián)程度來(lái)看，共鄰節(jié)點(diǎn)對(duì)節(jié)點(diǎn)間相似關(guān)系確實(shí)存在雙向強(qiáng)弱不同的影響，但是兩個(gè)節(jié)點(diǎn)之間的直接互動(dòng)強(qiáng)度也在一定程度上反映了兩者的相似關(guān)聯(lián)性。因此，計(jì)算節(jié)點(diǎn)相似度時(shí)僅考慮共鄰節(jié)點(diǎn)的貢獻(xiàn)是不夠全面的。

2.2 有向加權(quán)圖的BDMS算法

為了更好地評(píng)價(jià)空間節(jié)點(diǎn)的相似性，本文采用BDMS算法來(lái)計(jì)算相似度，算法的基本流程如下：

步驟1：輸入由初始數(shù)據(jù)集形成的馬爾科夫鏈狀態(tài)轉(zhuǎn)移概率矩陣P（見(jiàn)式（1））。

步驟2：參照式（2），構(gòu)建有向加權(quán)圖G'=(V，→，W)。

步驟3：根據(jù)有向加權(quán)圖G'的節(jié)點(diǎn)間矢量信息完成節(jié)點(diǎn)間的相似度分解。

步驟4：根據(jù)節(jié)點(diǎn)邊權(quán)值、邊方向、出度和入度相似度的對(duì)稱性等信息，計(jì)算節(jié)點(diǎn)的相似度。

步驟5：輸出相似度鄰接矩陣。為下一步利用該矩陣進(jìn)行聚類分析實(shí)現(xiàn)聚簇劃分做準(zhǔn)備。

2.2.1 節(jié)點(diǎn)之間的相似度分解

馬爾科夫鏈的一個(gè)節(jié)點(diǎn)向其他節(jié)點(diǎn)轉(zhuǎn)出數(shù)量時(shí)，也可能接收其他節(jié)點(diǎn)轉(zhuǎn)入的數(shù)量，整個(gè)過(guò)程可以建立節(jié)點(diǎn)間的雙向局部連接關(guān)系，依照式（2）形成一個(gè)有向加權(quán)圖，然后通過(guò)節(jié)點(diǎn)間的雙向矢量關(guān)聯(lián)信息來(lái)計(jì)算相似度。如果將節(jié)點(diǎn)v3看作是v1、v2的共鄰節(jié)點(diǎn)，根據(jù)關(guān)聯(lián)矢量方向可以分解為：v3對(duì)v1和v2的轉(zhuǎn)移強(qiáng)度存在正反兩個(gè)方向，如圖1中（a）、（b）所示；v1和v2之間的互轉(zhuǎn)強(qiáng)度存在正反兩個(gè)方向，如圖1中（c）所示。

圖1 節(jié)點(diǎn)間關(guān)聯(lián)矢量分解示意圖

于是可以理解有向加權(quán)圖的兩個(gè)空間事件節(jié)點(diǎn)的相似度由以下三個(gè)部分組成：Sin——入度相似度；Sout——出度相似度；LT——兩個(gè)節(jié)點(diǎn)直接相連的親密度，即直連相似度。其中，入度相似度、出度相似度分別參照余弦相似度的計(jì)算方法,從單一方向上與傳統(tǒng)方法保持一致，計(jì)算公式分別如式（3）、式（4）所示。

其中，N+(i)、N-(i)、N+(j)、N-(j)分別表示節(jié)點(diǎn)i和j的入度和出度的鄰居節(jié)點(diǎn)集合，N+(i)∩N+(j)和N-(i)∩N-(j)分別表節(jié)點(diǎn)i和j的入度和出度的共鄰節(jié)點(diǎn)集合，Pki和Pkj表示共鄰節(jié)點(diǎn)k對(duì)節(jié)點(diǎn)i和j的入度轉(zhuǎn)移強(qiáng)度，Pik和Pjk表示節(jié)點(diǎn)i和j對(duì)共鄰節(jié)點(diǎn)k的出度轉(zhuǎn)移強(qiáng)度。

2.2.2 算法過(guò)程描述和實(shí)現(xiàn)

為了降低算法復(fù)雜度，在有向加權(quán)圖的相似性度量定義中，主要綜合考慮影響節(jié)點(diǎn)相似性的各個(gè)因素的作用。算法過(guò)程如下：定義兩個(gè)節(jié)點(diǎn)的相似度S(i，j)由共鄰相似度ST(i，j)和直連相似度LT(i，j)組成。其中，ST(i，j)由共鄰節(jié)點(diǎn)對(duì)兩個(gè)節(jié)點(diǎn)在雙向連接邊權(quán)值上的貢獻(xiàn)決定，并由入度相似度Sin(i，j)和出度相似度Sout(i，j)計(jì)算得出，算法計(jì)算時(shí)，針對(duì)不同方向，若兩個(gè)節(jié)點(diǎn)與共鄰節(jié)點(diǎn)之間有一個(gè)方向不直接相連，則該方向的相似度為0；否則，取其共鄰節(jié)點(diǎn)的邊權(quán)值納入計(jì)算；直連相似度LT(i，j)由兩個(gè)節(jié)點(diǎn)之間在雙向連接邊權(quán)值上的貢獻(xiàn)決定，算法計(jì)算時(shí)，若兩個(gè)節(jié)點(diǎn)之間有一個(gè)方向連接斷開(kāi)，則兩者的直連相似度為0，否則取其雙向邊的權(quán)值納入計(jì)算。算法主要步驟如下：

步驟1：計(jì)算兩個(gè)節(jié)點(diǎn)的共鄰相似度ST(i，j)，如式(5)所示。

其中，Sin(i，j)、Sout(i，j)分別由式（3）、式（4）計(jì)算所得。式（5）的算法有兩個(gè)主要優(yōu)點(diǎn)：（1）Sin(i，j)和Sout(i，j)的值越大，ST(i，j)越大；（2）Sin(i，j)和Sout(i，j)的值越接近對(duì)稱，ST(i，j)遞增速度越快。式（5）利用共鄰節(jié)點(diǎn)的入度和出度相似度影響節(jié)點(diǎn)間的相似關(guān)聯(lián)程度，入度和出度相似度越大并且越具有對(duì)稱性，節(jié)點(diǎn)間相似性越強(qiáng)。為了計(jì)算方便，將ST(i，j)的取值范圍歸一化為[0,1]，取值變化如圖2（a）所示。假如簡(jiǎn)單照搬余弦相似度算法，ST(i，j)會(huì)考慮取值為Sin(i，j)、Sout(i，j)中的任意一項(xiàng)，或者不考慮邊權(quán)方向而直接相加后納入計(jì)算，算法會(huì)忽略邊對(duì)稱性、方向性等因素所產(chǎn)生的作用，導(dǎo)致計(jì)算結(jié)果準(zhǔn)確度不高，共鄰節(jié)點(diǎn)對(duì)相似度的貢獻(xiàn)差異不能充分地表現(xiàn)出來(lái)，以此來(lái)評(píng)估相似度會(huì)降低計(jì)算結(jié)果的有效性。

圖2 共鄰相似度與直連相似度的取值變化趨勢(shì)

步驟2：計(jì)算兩個(gè)節(jié)點(diǎn)的直連相似度LT(i，j)，沿用步驟1的算法思路，如式（6）所示。

其中，Wij和Wji分別為節(jié)點(diǎn)對(duì)之間直連兩個(gè)方向的邊權(quán)值，兩者乘積反映LT(i，j)的直連相似度。兩個(gè)邊權(quán)值越不對(duì)稱，LT(i，j)值變化幅度越大，越接近于0，其取值變化如圖2（b）所示。如果依據(jù)其他常用的相似度計(jì)算方法，LT(i，j)直接被認(rèn)為等于0，忽略了其對(duì)節(jié)點(diǎn)相似度的影響。

步驟3：計(jì)算兩個(gè)節(jié)點(diǎn)之間的相似度S(i，j)，直接采用ST(i，j)和LT(i，j)兩者的平方平均數(shù)求得，如式（7）所示。

上述公式具有以下特點(diǎn)：

（1）對(duì)于有向加權(quán)圖，S(i，j)能較好地反映相鄰節(jié)點(diǎn)個(gè)數(shù)、不同方向的相似度、節(jié)點(diǎn)間直連相似度、邊權(quán)對(duì)稱性等因素對(duì)兩個(gè)節(jié)點(diǎn)相似度的綜合影響。

（2）當(dāng)兩個(gè)節(jié)點(diǎn)不存在直接雙向相連的包含節(jié)點(diǎn)間僅有單向連接的情況，即LT(i，j)=0 時(shí)，兩個(gè)節(jié)點(diǎn)的相似度為，由共鄰節(jié)點(diǎn)對(duì)兩個(gè)節(jié)點(diǎn)在雙向連接邊權(quán)值的出度和入度相似度計(jì)算得出，通過(guò)比較與共鄰節(jié)點(diǎn)的關(guān)系來(lái)確定相似性，與大多數(shù)文獻(xiàn)提出的相似度算法思路一致。

（3）當(dāng)兩個(gè)節(jié)點(diǎn)存在雙向相連并且無(wú)共鄰節(jié)點(diǎn)時(shí)，ST(i，j)=0，兩個(gè)節(jié)點(diǎn)的相似度減弱為。此時(shí)節(jié)點(diǎn)相似度由直連相似度決定，僅受兩個(gè)節(jié)點(diǎn)直連邊權(quán)值影響。

（4）當(dāng)兩個(gè)節(jié)點(diǎn)存在雙向相連并且有共鄰節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)相似度由共鄰相似度和直連相似度共同貢獻(xiàn)所得。特別地，當(dāng)兩個(gè)節(jié)點(diǎn)間雙向直連權(quán)值越不對(duì)稱時(shí)，LT(i，j)遞減變化幅度越大，對(duì)S(i，j)產(chǎn)生的影響程度越小，此時(shí)ST(i，j)起主導(dǎo)作用。

步驟4：基于上述算法設(shè)計(jì)，遍歷所有空間位置節(jié)點(diǎn)，最終形成有向加權(quán)圖的相似度鄰接矩陣，如式（8）所示。

上述矩陣具有對(duì)稱性，S(i，j)=S(j，i)，對(duì)角線元素全為0，非對(duì)角線元素表示節(jié)點(diǎn)對(duì)的相似強(qiáng)度。

3 基于相似度鄰接矩陣的聚類分析

基于相似特性的鄰接矩陣S進(jìn)行譜聚類分析，算法步驟如下：

步驟1：按照式（9）獲得標(biāo)準(zhǔn)化的拉普拉斯矩陣N。

步驟2：獲取矩陣N的特征值和特征向量?；诰仃嘚計(jì)算出以行向量存放的一維特征值矩陣λ和以列存放的特征向量矩陣F，F(xiàn)的每一列fi（i=1，2，…，n）代表一個(gè)特征向量。

步驟4：聚簇劃分。將F''中的每一行作為一個(gè)k維的樣本，共n個(gè)樣本，聚類維數(shù)為k，對(duì)這些新生成的樣本點(diǎn)進(jìn)行K-means聚類，聚成k類，最后輸出聚類結(jié)果，得到不同聚簇劃分。

4 實(shí)例驗(yàn)證

為了驗(yàn)證本文相似度算法的有效性和合理性，本文以真實(shí)的高校學(xué)生生活和學(xué)習(xí)數(shù)據(jù)集作為實(shí)驗(yàn)對(duì)象，按照上文的相似度算法構(gòu)建鄰接矩陣，采取譜聚類后從節(jié)點(diǎn)聚集模塊度、輪廓系數(shù)等方面進(jìn)行對(duì)比分析。

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

數(shù)據(jù)集1：高校學(xué)生消費(fèi)群體由各類人群構(gòu)成，群體中成員具有不同的飲食習(xí)慣，對(duì)不同商戶的消費(fèi)物品產(chǎn)生不同程度的偏好，消費(fèi)物品在質(zhì)量、服務(wù)、價(jià)格、口味等方面各異，吸引不同人群在商戶之間進(jìn)行選擇性消費(fèi)，消費(fèi)者在商戶之間發(fā)生馬爾科夫鏈轉(zhuǎn)移現(xiàn)象。學(xué)校以此來(lái)探詢各商戶分布結(jié)果是否具有更優(yōu)的合理性，并預(yù)測(cè)相似經(jīng)營(yíng)商戶間的關(guān)聯(lián)程度，為學(xué)校優(yōu)化餐飲質(zhì)量提供決策參考。本實(shí)驗(yàn)采用華中師范大學(xué)一卡通系統(tǒng)的刷卡消費(fèi)數(shù)據(jù)集，涉及校園卡用戶數(shù)量為54243個(gè)，其中，2022年3月至6月消費(fèi)流水總記錄為93951622條，每條記錄選取學(xué)生學(xué)號(hào)、商戶標(biāo)識(shí)、消費(fèi)物品名、消費(fèi)時(shí)間等作為實(shí)驗(yàn)數(shù)據(jù)參考點(diǎn)，其中消費(fèi)物品名與商戶標(biāo)識(shí)綁定。為了減少消費(fèi)量極小的商戶對(duì)分析結(jié)果產(chǎn)生干擾，流水記錄總數(shù)低于1000條的商戶被過(guò)濾掉，最后進(jìn)入分析的有效商戶數(shù)量有167個(gè)。消費(fèi)流水總記錄100萬(wàn)次以上的商戶占11.98%，50萬(wàn)～100萬(wàn)次的商戶占34.13%，10萬(wàn)～50萬(wàn)次的商戶占43.11%，10萬(wàn)次以下的商戶占10.78%，能在最大程度上反映出用戶對(duì)商戶形成的選擇性消費(fèi)趨勢(shì)。將上述商戶標(biāo)識(shí)用vi（i=1，2，…，167）表示，得到有167 個(gè)節(jié)點(diǎn)的狀態(tài)空間。依據(jù)式（2）將商戶間的消費(fèi)活動(dòng)關(guān)系轉(zhuǎn)化為有向加權(quán)圖，圖中每一條方向線表明當(dāng)前商戶vi的消費(fèi)群體向另一個(gè)商戶vj轉(zhuǎn)出的概率Pij。狀態(tài)空間的商戶間轉(zhuǎn)移次數(shù)越多，轉(zhuǎn)移關(guān)系權(quán)重就越大。

數(shù)據(jù)集2：高校學(xué)生選修公選課時(shí)因課程熱度或個(gè)人需求不同出現(xiàn)選課次數(shù)互轉(zhuǎn)現(xiàn)象，采用以此形成的選修課聚簇分布來(lái)評(píng)估課程間的相關(guān)性、緊密性及相似熱度，方便學(xué)校教務(wù)部門及時(shí)了解公選課開(kāi)設(shè)情況，并且要求評(píng)估的算法要具備比較高的準(zhǔn)確度。實(shí)驗(yàn)數(shù)據(jù)來(lái)源于華中師范大學(xué)2014—2023年的學(xué)生選課系統(tǒng)數(shù)據(jù)集，有效的選課記錄有2283226條，參與分析的課程有294門，參與選課的學(xué)生有44548位，在選課記錄中選取學(xué)生學(xué)號(hào)、課程代碼、學(xué)期標(biāo)識(shí)、選課時(shí)間等參與分析。將上述學(xué)生選課活動(dòng)的課程標(biāo)識(shí)記為vi（i=1，2，…，294），共有294 個(gè)節(jié)點(diǎn)的狀態(tài)空間。依據(jù)式（2）將選課活動(dòng)關(guān)系轉(zhuǎn)化為有向加權(quán)圖，圖中每一條方向線表明選修課程vi的學(xué)生群體向另一門課程vj轉(zhuǎn)出的概率Pij。

4.2 聚類模塊度對(duì)比

為了評(píng)價(jià)本文算法對(duì)實(shí)例數(shù)據(jù)集節(jié)點(diǎn)的劃分質(zhì)量，引入聚類模塊度進(jìn)行分析。一般來(lái)說(shuō)，聚類模塊度值越大，則對(duì)應(yīng)的社區(qū)聚類個(gè)數(shù)越準(zhǔn)確，并且更加接近真實(shí)的社區(qū)結(jié)構(gòu)分布情況。以數(shù)據(jù)集1和2為例，分別選取BDMS、文獻(xiàn)[6]相似度、余弦相似度，按照本文譜聚類分析步驟進(jìn)行實(shí)驗(yàn)對(duì)比，聚類模塊度比較結(jié)果如表1和表2所示。經(jīng)過(guò)多次對(duì)商戶節(jié)點(diǎn)進(jìn)行聚類合并后，當(dāng)數(shù)據(jù)集1和2的聚類數(shù)量分別被劃分為2～5 個(gè)和2～7 個(gè)時(shí)，BDMS 結(jié)合譜聚類分析獲得的聚類模塊度值大于0.3，且高于對(duì)比算法。在聚類個(gè)數(shù)為3～10 個(gè)時(shí)，文獻(xiàn)[6]相似度和余弦相似度的聚類模塊度值都明顯低于本文算法的計(jì)算結(jié)果。綜上所述，BDMS 結(jié)合本文譜聚類算法在相似性度量及聚簇劃分上優(yōu)于對(duì)比算法，具有發(fā)現(xiàn)潛在的學(xué)生活動(dòng)社區(qū)網(wǎng)絡(luò)節(jié)點(diǎn)的分布的能力。

表1 數(shù)據(jù)集1相關(guān)算法聚類模塊度比較

表2 數(shù)據(jù)集2相關(guān)算法聚類模塊度比較

4.3 聚類結(jié)果輪廓系數(shù)對(duì)比

聚類結(jié)果的輪廓系數(shù)是聚類的密集與分散程度的評(píng)價(jià)指標(biāo)[19]。從輪廓系數(shù)評(píng)價(jià)算法原理可知，其取值范圍為（-1，1），且其值越接近于1，代表聚簇內(nèi)聚集度和聚簇間分離度效果越優(yōu)。通過(guò)評(píng)價(jià)指標(biāo)不僅可以評(píng)估相似度計(jì)算針對(duì)不同聚類算法的有效性,而且還可以很好地了解給定有向加權(quán)圖的節(jié)點(diǎn)動(dòng)態(tài)關(guān)系。針對(duì)數(shù)據(jù)集1 和2，將BDMS譜聚類與BDMS、余弦相似度、文獻(xiàn)[6]及文獻(xiàn)[7]相似度等進(jìn)行K-means聚類對(duì)比實(shí)驗(yàn)，同時(shí)檢驗(yàn)BDMS算法采用傳統(tǒng)聚類分析的效果。聚類數(shù)k在2～30 取值，計(jì)算過(guò)程獲取一系列聚類的輪廓系數(shù)參與比較，結(jié)果見(jiàn)圖3。

圖3 不同相似度算法聚類結(jié)果的輪廓系數(shù)對(duì)比

從圖3 中可以看出，本文BDMS 聚類結(jié)果的輪廓系數(shù)在最優(yōu)時(shí)分別達(dá)到0.9534、0.7380，并且從整體上來(lái)看，不同聚類數(shù)的輪廓系數(shù)也明顯高于其他四種計(jì)算方式（不含余弦相似度+譜聚類），結(jié)果顯示，采用BDMS 結(jié)合譜聚類分析時(shí)對(duì)社區(qū)聚簇劃分具有較大優(yōu)勢(shì)。

進(jìn)行K-means 聚類時(shí)，相比于余弦相似度、文獻(xiàn)[6]和文獻(xiàn)[7]提出的相似度算法，BDMS算法得到的輪廓系數(shù)從整體上看平穩(wěn)性相對(duì)較好。雖然文獻(xiàn)[6]考慮到有向加權(quán)圖的邊權(quán)和邊方向信息，文獻(xiàn)[7]提出以用戶參與同一事件次數(shù)越多和參與事件類別越多為條件，分別建立無(wú)向圖相似度模型，但當(dāng)處于不同聚類數(shù)時(shí)，聚類結(jié)果的輪廓系數(shù)相對(duì)偏小。另外，針對(duì)余弦相似度采用譜聚類分析，根據(jù)圖3（a）和（b）的結(jié)果，其輪廓系數(shù)分布比較接近采用BDMS進(jìn)行譜聚類分析的計(jì)算結(jié)果，但是與表1和表2中的聚類模塊度相比，兩者聚類劃分的評(píng)估結(jié)果差別較大，表明該方法不推薦在譜聚類中使用，而B(niǎo)DMS卻能很好地適應(yīng)譜聚類和傳統(tǒng)K-means聚類的分析。

5 結(jié)論

本文以社區(qū)活動(dòng)形成的有向加權(quán)圖為研究對(duì)象，設(shè)計(jì)了一種雙向度量相似度的計(jì)算方法，并采用譜聚類無(wú)向切圖實(shí)現(xiàn)社區(qū)聚簇的最優(yōu)劃分，將有向加權(quán)圖節(jié)點(diǎn)劃分問(wèn)題轉(zhuǎn)化為無(wú)向加權(quán)圖聚類問(wèn)題。通過(guò)理論和實(shí)例分析，得出如下結(jié)論：

（1）BDMS算法思路簡(jiǎn)單。依托馬爾科夫鏈現(xiàn)象存在的節(jié)點(diǎn)轉(zhuǎn)移關(guān)系，算法提取較少的樣本信息即可構(gòu)建有向加權(quán)圖，比較容易實(shí)現(xiàn)。

（2）BDMS算法能在很大程度上真實(shí)體現(xiàn)節(jié)點(diǎn)間的相似關(guān)系。算法綜合考慮了影響計(jì)算結(jié)果的諸多因素，并將各種因素的合理性在計(jì)算中體現(xiàn)出來(lái)，節(jié)點(diǎn)間關(guān)系的表示與實(shí)際接近。

（3）相比文中其他相似度算法，BDMS 算法結(jié)合譜聚類無(wú)向切圖，在聚類分析時(shí)輸出結(jié)果準(zhǔn)確度高，能夠更好地發(fā)現(xiàn)潛在的社區(qū)結(jié)構(gòu)，同時(shí)在譜聚類和傳統(tǒng)K-means聚類分析中表現(xiàn)出很好的適應(yīng)性，并且在高校學(xué)生數(shù)據(jù)集的實(shí)例驗(yàn)證中驗(yàn)證了其有效性。為更充分地利用節(jié)點(diǎn)相似度進(jìn)行快速聚簇劃分，后續(xù)還可在子圖內(nèi)節(jié)點(diǎn)聚集質(zhì)量和進(jìn)一步優(yōu)化算法方面開(kāi)展工作。