基于聚類的超鏈路預(yù)測

齊鵬飛，周麗華，杜國王，黃 皓，黃 通

（云南大學(xué)信息學(xué)院，昆明650091）

0 引言

現(xiàn)實世界中許多復(fù)雜的交互系統(tǒng)都可以自然地被描述為信息網(wǎng)絡(luò)［1］，比如社會網(wǎng)絡(luò)、協(xié)作網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、生物神經(jīng)網(wǎng)絡(luò)和蛋白質(zhì)相互作用網(wǎng)絡(luò)。鏈路預(yù)測能夠利用網(wǎng)絡(luò)中已經(jīng)觀測到的網(wǎng)絡(luò)結(jié)構(gòu)或者節(jié)點的屬性信息來復(fù)現(xiàn)網(wǎng)絡(luò)中缺失的鏈路，受到了來自生物學(xué)、信息學(xué)等多學(xué)科學(xué)者的關(guān)注，成為橫跨多個學(xué)科的核心科學(xué)問題［2］。

傳統(tǒng)鏈路預(yù)測是對兩個節(jié)點之間是否存在鏈接進行預(yù)測。但是在現(xiàn)實網(wǎng)絡(luò)中，鏈接關(guān)系可能存在于多個節(jié)點之間，比如DBLP網(wǎng)絡(luò)中論文的發(fā)表包含了作者-論文-期刊/會議等不同類型節(jié)點之間的關(guān)系［3］。為了便于描述多個節(jié)點之間的復(fù)雜關(guān)系，Zhang 等［4］提出了超鏈路概念：即一組包含有任意數(shù)量的同種或不同類型的節(jié)點，這些節(jié)點在一起形成一個多路徑關(guān)系。超鏈路不再局限于只有兩個節(jié)點組成鏈路的限制，允許任意數(shù)量的同型或不同類型的節(jié)點共同形成超鏈路，保留了網(wǎng)絡(luò)中豐富多元的信息。

現(xiàn)有超鏈路預(yù)測算法大多是基于所有超鏈路觀察樣本的相似性來進行預(yù)測，若某一類超鏈路樣本數(shù)量較多或者某類超鏈路中節(jié)點之間的聯(lián)系較其他類節(jié)點之間的關(guān)系更加密切，掩蓋了其他類超鏈路的信息，那么訓(xùn)練樣本數(shù)目較少的超鏈路可能預(yù)測不出來，導(dǎo)致預(yù)測結(jié)果覆蓋面不全。比如在圖1 中相同線型的線連接的節(jié)點組成一條超鏈路，實線代表預(yù)測出來的超鏈路。原始網(wǎng)絡(luò)中B-A-E 和G-H 這兩條超鏈路是缺失的。圖1（a）是對整個網(wǎng)絡(luò)使用超鏈路預(yù)測算法CMM（Coordinated Matrix Minimization）［4］的預(yù)測結(jié)果，僅僅預(yù)測出超鏈路B-A-E，而超鏈路G-H 沒有被預(yù)測出來；圖1（b）先對整個網(wǎng)絡(luò)的超鏈路進行聚類，得到簇1、簇2，然后分別基于簇1 和簇2 進行預(yù)測，從圖1（b）中可以看出，超鏈路B-A-E 和超鏈路G-H均被預(yù)測出來了。

本文提出的基于聚類的超鏈路預(yù)測算法C-CMM（Clusterd-based CMM）首先將觀察到的超鏈路聚類成簇，然后對每個簇分別建立超鏈路預(yù)測模型，這樣每個簇中所蘊含的信息能夠得到充分利用，保證預(yù)測結(jié)果覆蓋所有類別，能克服預(yù)測結(jié)果種類不全的缺陷；此外，經(jīng)過聚類處理后，每個簇包含的超鏈路數(shù)目遠遠小于整個網(wǎng)絡(luò)中所包含超鏈路數(shù)目，預(yù)測時間將大幅度縮減。

圖1 超鏈路預(yù)測Fig.1 Hyperlink prediction

本文主要工作如下：

1）提出了對超鏈路進行基于非負矩陣分解（Nonnegative Matrix Factorization，NMF）的聚類算法。該算法基于非負矩陣分解學(xué)習(xí)超鏈路的表達，然后對超鏈路進行聚類得到不同的簇，使簇內(nèi)的超鏈路盡可能相似，不同簇間的超鏈路盡可能相異。

2）提出了基于聚類的超鏈路預(yù)測算法C-CMM。C-CMM對聚類獲得的每個簇分別建立超鏈路預(yù)測模型，從而充分利用各個簇的觀察樣本所蘊含的信息，保證預(yù)測結(jié)果覆蓋所有類別，克服預(yù)測結(jié)果可能種類單一的不足。

3）使用三個真實數(shù)據(jù)集對所提算法進行了實驗驗證，從預(yù)測的準(zhǔn)確性、預(yù)測結(jié)果覆蓋種類的全面性和算法的執(zhí)行效率三個方面考察了基于聚類的超鏈路預(yù)測算法的效果和效率，并與其他超鏈路預(yù)測算法的結(jié)果進行了比較，結(jié)果表明C-CMM算法具有較好的性能。

1 相關(guān)工作

1.1 鏈路預(yù)測算法

鏈路預(yù)測［5］是數(shù)據(jù)挖掘領(lǐng)域的一個研究方向，在網(wǎng)絡(luò)研究領(lǐng)域已經(jīng)有多年的研究歷史［6-9］。早期的研究主要使用馬爾可夫鏈和機器學(xué)習(xí)的方法來對鏈路預(yù)測進行研究，近年來研究者主要基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)進行預(yù)測。根據(jù)網(wǎng)絡(luò)拓撲結(jié)構(gòu)的鏈路預(yù)測方法可以分為基于相似性的鏈路預(yù)測、基于似然分析的鏈路預(yù)測和基于元路徑的鏈路預(yù)測［10］等。其中基于相似性的鏈路預(yù)測方法中最具代表性的指標(biāo)是CN（Common Neighbors）［5］指標(biāo)，即節(jié)點之間擁有越多的共同節(jié)點則越容易形 成 鏈 路。Katz［11］提 出 的Katz 指 標(biāo) 結(jié) 合 了CN 指 標(biāo) 和LP（Local Path）［2］指標(biāo)，考慮了節(jié)點對之間所有的鏈路，對短路徑賦予較小的權(quán)重，而長路徑則相反。近年來許多研究者嘗試基于表達學(xué)習(xí)進行鏈路預(yù)測［12-16］，這些方法從網(wǎng)絡(luò)結(jié)構(gòu)或/和節(jié)點屬性學(xué)習(xí)每個節(jié)點的向量表示，然后實現(xiàn)鏈路預(yù)測。由于學(xué)到的節(jié)點向量表示揭示了節(jié)點非線性的隱特征，因此基于表達學(xué)習(xí)的鏈路預(yù)測的性能得到了極大提高。

1.2 超鏈路預(yù)測

超鏈路預(yù)測通過給定一個不完整的網(wǎng)絡(luò)和一個潛在超鏈路的候選集，來找到候選集中所有最有可能是網(wǎng)絡(luò)中缺失的超鏈路或者網(wǎng)絡(luò)將會形成的超鏈路［4］。Xu 等［17］提出了一個使用熵評分為特征的監(jiān)督HPLSF（Hyperlink Prediction using Latent Social Features）框架來預(yù)測社交網(wǎng)絡(luò)中的超鏈路；Neville 等［18］利用潛在的社會特征來預(yù)測網(wǎng)絡(luò)中超鏈路的存在；Chen 等［6］提出了利用超鏈路正則化的半監(jiān)督超圖頂點分類算法，利用節(jié)點的超鏈路關(guān)系來提高節(jié)點的學(xué)習(xí)性能；Zhang 等［4］提出了CMM 算法，在網(wǎng)絡(luò)的頂點鄰接空間中交替執(zhí)行非負矩陣分解和最小二乘匹配，以推斷最適合整個觀測到的網(wǎng)絡(luò)的超鏈路。目前關(guān)于超鏈路預(yù)測的研究成果還不多，研究空間還很大。

2 基于聚類的超鏈路預(yù)測算法C-CMM

2.1 超鏈路聚類

信息網(wǎng)絡(luò)中存在大量的超鏈路，且節(jié)點數(shù)目可變。直接采用傳統(tǒng)聚類算法在處理數(shù)據(jù)量小、維度低的數(shù)據(jù)時，通常能取得較好的效果，但隨著數(shù)據(jù)量增大、維度升高，聚類性能將逐漸下降。如K-means 聚類算法在低維數(shù)據(jù)上聚類效果較好，但是受“維度災(zāi)難”的影響，在高維數(shù)據(jù)上不能取得較好的聚類效果。非負矩陣分解（NMF）［19］是一種有效的降維方式，能夠獲得高維數(shù)據(jù)樣本的低維特征，使用傳統(tǒng)的聚類算法對低維表征進行聚類，可以獲得更好的效果。

非負矩陣分解算法為關(guān)聯(lián)矩陣S 找到合適的非負基矩陣Wm×k∈?+和非負系數(shù)矩陣H k×n ∈?+，使得它們的乘積近似于原始關(guān)聯(lián)矩陣S，即：

其中：k ?min(m，n)，W 的列向量可以表示為對S 中所有超鏈路的加權(quán)和，而系數(shù)矩陣H 可以看作是關(guān)聯(lián)矩陣S 的低維表達。H的第l列表示第l條超鏈路在W的矢量構(gòu)成的空間中投影的特征表達?；谠撎卣鞅磉_，通過傳統(tǒng)的聚類算法（比如K-means）對矩陣H 進行聚類，可以將n 條超鏈路聚集成簇。為了找到S ≈WH的近似分解，NMF最小化如下目標(biāo)函數(shù)：

s.t.W ≥0，H ≥0

其中，‖ · ‖F(xiàn)表示矩陣的F 范數(shù)。對于式（2）的優(yōu)化，本文采用乘子更新法進行迭代更新，H 和W 更新規(guī)則如式（3）和（4）所示。

獲得H 后，可以使用聚類算法完成聚類。聚類算法可以使 用K-means、DBSCAN（Density-Based Spatial Clustering of Applications with Noise）等算法。H 中的每一列對應(yīng)超鏈路的低維表達，對這些低維表達的聚類就相當(dāng)于對超鏈路的聚類?；诜秦摼仃嚪纸獾木垲愃惴ㄈ缢惴?所示。

算法1 超鏈路聚類（Hyperlink Cluster，HC）。

輸入 超鏈路關(guān)聯(lián)矩陣S，簇個數(shù)k，誤差閾值ε；

輸出 k個簇S1，S2，…，Sk。

1）初始化W，H

2）Repeat

3） 固定W，通過式（3）更新H

4） 固定H，通過式（4）更新W

5）Until||S-WH||2＜ε

6）使用K-means算法對H聚類得到S1，S2，…，Sk

比如，圖1（a）所示待預(yù)測的信息網(wǎng)絡(luò)的關(guān)聯(lián)矩陣如下所示，其中行代表了A 到H 這8 個節(jié)點，每一列分別代表e1～e6這6條超鏈路。

對上述關(guān)聯(lián)矩陣S進行非負矩陣分解得到H如下：

使用K-means 算法對矩陣H 進行聚類，得到兩個簇：e1、e2、e3、e4為一個簇，e5、e6為一個簇。

2.2 C-CMM超鏈路預(yù)測算法

CMM 算法［4］是一種優(yōu)秀的超鏈路預(yù)測方法，它在網(wǎng)路的鄰接空間中交替執(zhí)行非負矩陣分解和最小二乘匹配，以推斷與觀測到的超鏈路最吻合的超鏈路。本文將聚類信息融入CMM 模型，提出基于聚類的超鏈路預(yù)測算法C-CMM。假定U是一個超鏈路的候選集，其中包含了網(wǎng)絡(luò)Hyper中缺失的超鏈路，超鏈路預(yù)測C-CMM 的目標(biāo)就是找到集合U 中最有可能是網(wǎng)絡(luò)Hyper 中缺失的超鏈路。在2.1 節(jié)中，已經(jīng)對關(guān)聯(lián)矩陣S進行了聚類，即將一個網(wǎng)絡(luò)Hyper劃分成簇S1，S2，…，Sk。這k個簇相當(dāng)于網(wǎng)絡(luò)Hyper 的k 個子網(wǎng)絡(luò)，由于網(wǎng)絡(luò)Hyper 是不完整的，所以每個子網(wǎng)絡(luò)也可能是不完整的。本文隨機生成k個網(wǎng)絡(luò)，模擬不存在的超鏈路，將它們分別與簇S1，S2，…，Sk結(jié)合，構(gòu)造出候選集Ui(i=1，2，…，k)，并假定該簇缺失的超鏈路均包含在U i 中。因此，基于聚類的超鏈路預(yù)測算法C-CMM 將分別從各自的候選集U i 中找到最有可能是該簇缺失的超鏈路。基于聚類的超鏈路預(yù)測算法如算法2所示。

算法2 基于聚類的超鏈路預(yù)測算法C-CMM。

輸入 觀測到的超鏈路矩陣S；

輸出 預(yù)測到的超鏈路矩陣ΔS。

1）ΔS起始為空

2）對S 調(diào)用超鏈路聚類算法HC 進行聚類，得到k 個簇S1，S2，…，Sk，并將其與隨機生成的網(wǎng)絡(luò)結(jié)合起來分別構(gòu)造出各自的超鏈路候選集U1，U2，…，U k

3）For i=1 to k

5）End for

6）ΔS=ΔSi∪…∪ΔSk

2.3 計算復(fù)雜性分析

設(shè)k 是簇的數(shù)目。對鄰接矩陣Sm×n的分解，每進行一次迭代要進行4kmn+k2m+k2n+km+kn次乘法計算，km+kn次除法計算和4kmn+k2m+k2n 次加法計算。因為乘子更新法能在I次迭代內(nèi)得到H以及k ?min(m，n)，所以矩陣分解的時間復(fù)雜度為O(Imnk)。從文獻［5］可知，CMM 算法的時間復(fù)雜度為O(n3)。對于每一個簇，都需要使用CMM 進行一次預(yù)測，因此C-CMM算法的時間復(fù)雜度為O(Imnk+kn3)。

3 實驗與分析

3.1 實驗數(shù)據(jù)集與評價指標(biāo)

本文使用了雞尾酒、傳統(tǒng)中國菜食譜和DBLP 三個真實數(shù)據(jù)集進行實驗。雞尾酒是一種混合飲品，由兩種或兩種以上的酒或飲料、水果等其他輔助材料混合而成。根據(jù)基酒的不同，雞尾酒可以分為不同的類別。雞尾酒數(shù)據(jù)集從drink8.cn上下載，收集到了朗姆、白蘭地、龍舌蘭、伏特加和利口5種類型的雞尾酒。例如“波本雞尾酒”包含“威士忌、橙汁、薄荷”三種配料；“蘋果白蘭地雞尾酒”包含“蘋果汁、白蘭地”兩種配料。這5種類型中，每種類型均包含40種不同的雞尾酒配方，共200條雞尾酒配方，其中配料一共有82種，故雞尾酒配方轉(zhuǎn)化為82×200 的0-1 矩陣（矩陣中值為0 的元素表示列配方不包含行配料，值為1 表示包含）。傳統(tǒng)中國菜食譜數(shù)據(jù)集來自meishi.net。該數(shù)據(jù)集有882種食譜，包含439種不同的食材，構(gòu)成439×882 的0-1 矩陣。DBLP 數(shù)據(jù)集選擇了數(shù)據(jù)挖掘領(lǐng)域的20 個會議、8 000 篇文章、3 910 個作者，以及6 917 個期刊。以每篇論文的發(fā)表事件作為一個超鏈路，這條超鏈路包括了發(fā)表這篇論文的全部作者和收錄論文的會議和期刊，最終整理為10 847×8 000的0-1矩陣。

本文算法包含聚類和預(yù)測兩個步驟，聚類結(jié)果使用輪廓系數(shù)［20］作為評價指標(biāo)，超鏈路預(yù)測使用受試者工作特征曲線下面積（Area Under the receiver operating characteristic Curve，AUC）和召回率作為評價指標(biāo)。

輪廓系數(shù)（Silhouette Coefficient）是評價聚類效果好壞的度量指標(biāo)，它結(jié)合內(nèi)聚度和分離度兩種因素。使用輪廓系數(shù)評價聚類結(jié)果時不用知道數(shù)據(jù)的類別，而且還能評價劃分后的簇是否在內(nèi)部盡可能相似，簇之間是否盡可能不相似。它主要分為個體輪廓系數(shù)和全局輪廓系數(shù)。個體輪廓系數(shù)的定義如式（5）所示。

其中：ai表示超鏈路i與同簇內(nèi)其他超鏈路之間的平均距離；bi表示超鏈路i 與其他簇中超鏈路平均距離的最小值，即bi=min{bi1，bi2，…，bik}，bik是超鏈路i 與第k 簇中超鏈路間的平均距離。ai稱為超鏈路i 的簇內(nèi)不相似度，bi為超鏈路i 的簇間不相似度。si∈[-1，1]，si接近1，說明超鏈路i的聚類合理；若si接近-1，說明超鏈路i的聚類不合理，應(yīng)當(dāng)劃分到其他簇內(nèi)。對所有超鏈路的個體輪廓系數(shù)計算平均值，得到全局輪廓系數(shù)，如式（6）所示：

AUC 是一種常用的評價模型分類/預(yù)測效果好壞的度量指標(biāo)，AUC=1 表示分類/預(yù)測效果完美；0.5 ＜AUC ＜1 表示分類/預(yù)測效果優(yōu)于隨機猜測；AUC=0.5 表示分類/預(yù)測效果與隨機猜測一樣。假設(shè)模型的輸出結(jié)果是一個分數(shù)值，表示一條超鏈路真實存在的概率，則隨機選取一對（存在，不存在）的超鏈路，利用模型對兩條超鏈路進行預(yù)測，AUC的值表示模型對存在超鏈路的輸出值大于對不存在超鏈路的輸出的概率。隨機抽取n 對（存在，不存在）的超鏈路進行預(yù)測，假設(shè)有n'次預(yù)測中存在超鏈路的分數(shù)值大于不存在超鏈路的分數(shù)值，有n″次預(yù)測中兩個的分數(shù)值相等，則AUC的定義如（7）所示。

召回率（Recall）主要用于評價模型預(yù)測的覆蓋范圍，即真正存在的超鏈路有多少被預(yù)測出來。假設(shè)有N條真實存在但未觀察到的超鏈路，模型預(yù)測的top-N 條超鏈路中有n 條是真實存在的，則n 稱為召回條數(shù)，召回條數(shù)與N 的比值稱為召回率，其定義如式（8）所示。

召回率越高，模型預(yù)測的覆蓋面越廣。與AUC 相比，召回率側(cè)重于預(yù)測結(jié)果中排名靠前的超鏈路。

3.2 基準(zhǔn)算法

為了驗證基于聚類的超鏈路預(yù)測算法的有效性，本文選擇了如下6種算法作為基準(zhǔn)算法，分別為Katz［11］、CN［5］、BS［21］、HPLSF［12］、Random（隨機）和CMM［4］以及它們的變種。每種算法都將在超鏈路聚類后的簇上運行，得到的預(yù)測結(jié)果將與算法直接在整個超網(wǎng)絡(luò)上預(yù)測的結(jié)果進行比較。為了便于區(qū)分，用“C-算法名”表示該算法在聚類后的簇上預(yù)測的版本，如C-Katz。

本文基于雞尾酒數(shù)據(jù)、食譜數(shù)據(jù)和DBLP 數(shù)據(jù)進行雞尾酒配方預(yù)測、食譜預(yù)測和論文發(fā)表事件預(yù)測。

1）雞尾酒配方預(yù)測。給定一系列雞尾酒配料和配方，預(yù)測給定的配料是否還能搭配出哪些給定配方外的其他配方。

2）食譜預(yù)測。給定一系列的食材和菜譜，預(yù)測給定的食材是否還能搭配出哪些給定菜譜外的其他菜譜。

3）論文發(fā)表事件預(yù)測。由給定的論文發(fā)表事件和作者、期刊和會議，預(yù)測還會有哪些作者會合作，以及這些作者合著的論文會被哪些期刊/會議錄用。

3.3 預(yù)測結(jié)果

本實驗在使用矩陣分解獲取低維表達時，雞尾酒、食譜和DBLP 數(shù)據(jù)集的基矩陣的秩分別設(shè)定為r=4，15，50，在使用K-means 算法對雞尾酒、食譜和DBLP 數(shù)據(jù)聚類時簇的數(shù)目分別設(shè)定為k=5，11，37（此時，聚類結(jié)果的輪廓系數(shù)最大，見3.4節(jié)），在每個簇中隨機選取50%的超鏈路作為訓(xùn)練集，剩余50%的超鏈路作為測試集。隨機生成的超鏈路數(shù)目與測試集中的超鏈路數(shù)目相等。測試集中的超鏈路與隨機生成的超鏈路合并構(gòu)成候選集。每種算法分別在原始數(shù)據(jù)和聚類獲得的簇上進行預(yù)測，計算各種算法的召回率和AUC。使用CMM 算法對三個數(shù)據(jù)集的原始數(shù)據(jù)進行矩陣分解時，雞尾酒、食譜和DBLP 數(shù)據(jù)集的基矩陣的秩分別設(shè)置為10、30、80；使用C-CMM 算法對三個數(shù)據(jù)集的各個簇進行矩陣分解時，各個簇的矩陣的秩分別設(shè)為5、10、30。表1 展示了所有算法對于三種數(shù)據(jù)集的預(yù)測結(jié)果，最好的實驗結(jié)果用粗體進行表示。

表1 三個數(shù)據(jù)集上的召回率和AUCTab.1 Recall and AUC on three datasets

從表1 可以看出，基于聚類的鏈路預(yù)測算法在召回條數(shù)和AUC 上普遍優(yōu)于基準(zhǔn)算法，這表明超鏈路預(yù)測時提前對超鏈路聚類能夠獲得更好的性能。此外，在所有的超鏈路預(yù)測算法中，C-CMM 算法得到的預(yù)測性能最好，比基準(zhǔn)算法CMM性能有大幅度提升，說明基于聚類的超鏈路預(yù)測算法C-CMM是有效的。

3.4 結(jié)果可視化

本節(jié)將可視化預(yù)測到的真實存在的top-5 個雞尾酒配方和top-10 個食譜配方及非真實存在的top-3 個雞尾酒配方和食譜配方。DBLP 數(shù)據(jù)集上的預(yù)測結(jié)果與雞尾酒和食譜數(shù)據(jù)集的預(yù)測結(jié)果類似，限于篇幅不再展示。

3.4.1 真實存在的top-k個雞尾酒配方和菜譜

圖2 和圖3 展示了用C-CMM 和CMM 算法預(yù)測得到的top-5個真實存在的雞尾酒配方和top-10個真實存在的菜譜。

從圖2 可以看出，CMM 算法得到的結(jié)果僅僅只有3 種類型，而C-CMM算法得到的結(jié)果包含了5種類型。

從圖3 可以看出，CMM 預(yù)測到的10 種菜口味偏重、偏辣，而且菜式重復(fù)，如水煮千張、水煮牛肉、麻辣豆腐魚的做法基本一致，這些菜雖然真實存在，但是種類太少，口味單一。而C-CMM 預(yù)測到的菜譜有六種和CMM 一致，是真實存在的，而且菜品的種類增多了，如酸甜口味的菠蘿咕咾肉、苦味的苦瓜雞片、甜品木瓜燉奶酪，還有清爽的火龍果蝦球；做法類似的菜品也減少，水煮千張、水煮牛肉和麻辣豆腐魚這三種菜只剩下水煮牛肉，這是因為聚類后，每一種類別與其他類別都有較大的差異。這表明基于聚類的超鏈路預(yù)測模型能夠更好地利用每個簇中的信息，使預(yù)測結(jié)果更加全面。

3.4.2 非真實存在的top-k個雞尾酒方和菜譜

圖4和圖5展示了用C-CMM 和CMM 算法預(yù)測得到的top-3個非真實存在的雞尾酒和菜譜。

由圖4 可見，C-CMM 算法預(yù)測出來的雞尾酒只包含一種基酒，可以進行調(diào)酒，但是CMM 算法預(yù)測出來一種雞尾酒，包含了三種不同類型的酒，這種組合不能進行調(diào)酒；此外，CMM算法預(yù)測的雞尾酒比C-CMM算法預(yù)測的類型少。

由圖5可以看出，CMM算法預(yù)測的菜譜用料較單一重復(fù)，甚至有的食材不適于做成菜，比如牛肉和雞肉一般不會放在一起做菜；而C-CMM預(yù)測的菜譜用料豐富，而且食材之間的組合也更加合理一些，均可以做出可口的菜，比如南瓜羹、麻辣土豆魚和菠菜肚絲湯，與CMM算法相比沒有出現(xiàn)奇怪的組合。

圖2 C-CMM和CMM預(yù)測到的top-5個真實存在的雞尾酒Fig.2 Top-5 real cocktails predicted by C-CMM and CMM

圖3 C-CMM和CMM預(yù)測到的top-10個真實存在的菜譜Fig.3 Top-10 real menus predicted by C-CMM and CMM

圖4 C-CMM和CMM預(yù)測到的top-3個非真實存在的雞尾酒Fig.4 Top-3 non-real cocktails predicted by C-CMM and CMM

3.5 參數(shù)影響

本節(jié)考察了簇數(shù)目、基矩陣的秩和訓(xùn)練樣本數(shù)目這三個參數(shù)對預(yù)測結(jié)果的影響。

3.5.1 真實存在的top-k個雞尾酒配方和菜譜

圖6 展示了設(shè)定不同簇數(shù)目時K-means 算法聚類結(jié)果的輪廓系數(shù)，其中橫坐標(biāo)表示簇數(shù)，縱坐標(biāo)表示輪廓系數(shù)。從圖6可以看出，K-means算法對雞尾酒數(shù)據(jù)、食譜數(shù)據(jù)和DBLP 數(shù)據(jù)在k=5，11，37時有較高的輪廓系數(shù)。

3.5.2 不同秩對預(yù)測結(jié)果的影響

C-CMM 算法在進行矩陣分解時，需要設(shè)定基矩陣的秩r（超鏈路低維表達的維度）。圖7展示了設(shè)定不同秩時C-CMM算法預(yù)測結(jié)果的召回條數(shù)，其中橫坐標(biāo)表示秩，縱坐標(biāo)表示召回條數(shù)。從圖7可見，C-CMM算法對雞尾酒數(shù)據(jù)、食譜數(shù)據(jù)和DBLP數(shù)據(jù)在r=4，15，50時有較高的召回率。

3.5.3 不同訓(xùn)練樣本數(shù)目對預(yù)測結(jié)果的影響

為了驗證不同訓(xùn)練樣本數(shù)目對預(yù)測結(jié)果的影響，對雞尾酒、食譜、DBLP 數(shù)據(jù)集分別隨機刪除10 到80，50 到400，500到4 000 條超鏈路，然后使用刪除的超鏈路作為測試集，剩下的數(shù)據(jù)集作為訓(xùn)練集。圖8～10 分別展示了三個數(shù)據(jù)集在不同訓(xùn)練樣本數(shù)目下，所有算法的召回條數(shù)，其中橫坐標(biāo)表示刪除條數(shù)，縱坐標(biāo)表示召回條數(shù)。召回條數(shù)越多，說明預(yù)測效果越好。從圖8～10 中可以看出，在不同訓(xùn)練樣本數(shù)目下，基于聚類的超鏈路預(yù)測算法的召回條數(shù)普遍高于未使用聚類的超鏈路預(yù)測算法的召回條數(shù)，表明基于聚類的超鏈路預(yù)測模型擁有更好的魯棒性。

圖7 C-CMM算法設(shè)定不同秩時的召回條數(shù)Fig.7 Recalls under different number of ranks of C-CMM algorithm

圖8 六種算法分別隨機刪除10～80條超鏈路后的召回條數(shù)對比Fig.8 Comparison of the number of recalls after randomly deleteing 10 to 80 hyperlinks by six algorithms

圖9 六種算法分別隨機刪除50～400條超鏈路后的召回條數(shù)對比Fig.9 Comparison of the number of recalls after randomly deleteing 50 to 400 hyperlinks by six algorithms

3.6 算法效率

C-CMM 算法與基準(zhǔn)算法在雞尾酒和食譜數(shù)據(jù)集上運行時間的比較如表2 所示，可見，C-CMM 算法的效率比BS、HPLSF、Random、Katz、CN 高，但是比CMM 低。這是因為BS、HPLSF、Random、Katz、CN 是非迭代算法，程序只需運行一次即可得出結(jié)果；雖然C-CMM 調(diào)用了CMM 算法，但是聚類后每個簇的關(guān)聯(lián)矩陣要比原始矩陣小，矩陣分解的時間少于對原始矩陣的分解時間，并且各個簇的分解可以并行處理，所以C-CMM的效率比CMM高。

圖10 六種算法分別隨機刪除500～4 000條超鏈路后的召回條數(shù)對比Fig.10 Comparison of the number of recalls after randomly deleteing 500 to 4 000 hyperlinks by six algorithms

表2 運行時間比較 單位：sTab.2 Comparison of running time unit：s

4 結(jié)語

信息網(wǎng)絡(luò)中的超鏈路預(yù)測問題的研究十分重要并且有實際應(yīng)用價值，但是如何利用觀察樣本數(shù)量不足的超鏈路蘊含的信息，使預(yù)測出來的超鏈路覆蓋的種類全面、有效體現(xiàn)出網(wǎng)絡(luò)的全貌是人們需要解決的問題。本文針對現(xiàn)有超鏈路預(yù)測算法的不足，提出了基于聚類的超鏈路預(yù)測算法。該算法首先對觀察到的超鏈路進行聚類，然后對每一個簇分別建立超鏈路預(yù)測模型。實驗結(jié)果表明基于聚類的超鏈路預(yù)測算法在預(yù)測的準(zhǔn)確度和預(yù)測到的種類上均優(yōu)于未聚類的超鏈路預(yù)測算法，因此，將聚類算法應(yīng)用到超鏈路預(yù)測當(dāng)中是有效的。