[發明專利]一種基于支持向量機的鏈路預測方法

有效

• 申請號: 202110292562.8
• 申請日: 2021-03-18
• 公開（公告）號: CN112862082B
• 公開（公告）日: 2023-09-29
• 發明（設計）人: 陳偉倫;周銀座;韓筱璞
• 申請（專利權）人: 杭州師范大學
• 主分類號: G06F18/2411
• 分類號: G06F18/2411;G06N20/10
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 朱月芬

1.一種基于支持向量機的鏈路預測方法，其特征在于包括如下步驟：

步驟1、讀取數據，并劃分數據集，構建復雜網絡結構；

步驟2、構建特征工程；

首先需要確定網絡中的正負樣本，采用負樣本采樣的策略，使得正負樣本均衡；確定正負樣本之后，對所有樣本進行特征的提取；

步驟3、使用支持向量機進行分類器訓練；

使用的支持向量機采用的核函數為高斯核函數,在訓練時，針對不同的數據集以及不同的數據集的劃分情況進行超參數的調整，得到訓練好的支持向量機模型；

步驟4、使用鏈路預測中AUC指標對模型進行評估；

將測試集中的正樣本和負樣本輸入到訓練好的支持向量機模型中，得到每個樣本的分類預測結果和分類概率值，使用AUC對模型進行評價；

步驟5、對于同一個數據集，使用相似性指標進行鏈路預測任務，計算相對應的AUC數值后進行對比；

步驟2具體實現如下：

21.確定正負樣本，并給定標簽；

將鏈路預測作為一個基于有監督學習的二分類任務；將實際網絡中存在的邊標記為正樣本，標簽賦值為1；不存在的邊為負樣本，標簽賦值為0；

使用負采樣策略，從不存在的連邊的節點對列表中選取與訓練集的正樣本等大的連邊集合作為訓練集中的負樣本；針對測試集，采取同樣的負樣本策略，使得測試集中正樣本和負樣本的數量比例為1:1；

22.提取特征向量：

定義：為連接節點v_x和v_y的路徑中長度為l的路徑數目；α為可調參數，用于控制各階路徑的貢獻，通常取α＝10^-2或α＝10^-3；

使用訓練網絡進行所有樣本的特征向量的提取，提取方式如下：

每一個樣本由節點對v_x-v_y組成，特征向量定義如下：

步驟3具體實現如下：

31.調節超參數；

將特征向量確定為二維，將訓練集中的正負樣本提取到的二維特征向量以及對應的標簽送入支持向量機模型進行訓練；

支持向量機的核函數選擇高斯核函數作為內核；高斯核函數在考慮數據點之間的距離時，采用如下公式進行計算；

其中，γ是用來控制RBF內核寬度的參數；

在使用網格搜索尋找當前數據集適用的最佳超參數時，使用鏈路預測中的AUC指標對模型進行評估；

32.確定特征向量的維數；

將特征向量增加為三維；重復將訓練集中的正負樣本提取到的二維特征向量以及對應的標簽送入支持向量機模型進行訓練，記錄下三維特征向量所取得的最佳AUC。

2.根據權利要求1所述的一種基于支持向量機的鏈路預測方法，其特征在于步驟1具體實現如下：

11.讀取公開數據集；

首先需要讀取數據集的節點和連邊信息，使用數據集中的節點和連邊的信息建立一個與數據集對應的復雜網絡模型結構G(V,E),其中V代表網絡中的節點，E代表網絡中的連邊；

12.劃分數據集為訓練集和測試集；

將已知的網絡數據連邊集合E分成訓練集E^T、測試集E^P，訓練集E^T用于實驗時觀察的網絡信息，用于計算節點的相似性得分；測試集E^P作為實驗時要預測的網絡信息，用于對比實驗預測的結果；這里E＝E^T∪E^P，令U為N(N-1)/2個節點對組成的全集，那么將屬于U但不屬于E的邊稱為不存在的邊，屬于U但不屬于E^T的邊稱為未知邊；

采用隨機抽樣策略，隨機選取網絡中10％的連邊作為測試集E^P的連邊，將這10％的邊從完整網絡中刪除，網絡結構中剩余90％的邊作為訓練集E^T。

3.根據權利要求2所述的一種基于支持向量機的鏈路預測方法，其特征在于所述的公開數據集，選擇3種實際的網絡數據集，且選取的網絡均為無權無向網絡結構，包括1)線蟲的神經網絡；2)佛羅里達州食物鏈網絡；3)空手道俱樂部網絡。

4.根據權利要求3所述的一種基于支持向量機的鏈路預測方法，其特征在于特征向量維數設定的最大值為6，因此需要遍歷特征向量維數從2維到6維的情況，統計不同的特征向量維數的情況下所能取得的最佳的AUC；對比不同維數的特征向量對應的最佳AUC，將其中最大的AUC值對應的特征向量的維數確定為當前數據集所適合的最佳的特征向量維數。