[發明專利]一種構建公平的鏈接預測評估系統的方法

有效

• 申請號: 201810812169.5
• 申請日: 2018-07-23
• 公開（公告）號: CN109086373B
• 公開（公告）日: 2021-01-12
• 發明（設計）人: 汪鵬;肖君彥;孟越
• 申請（專利權）人: 東南大學
• 主分類號: G06F16/35
• 分類號: G06F16/35;G06F16/635;G06Q50/00
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 蔣昱

1.一種構建公平的鏈接預測評估系統的方法，具體步驟如下，其特征在于：

1）收集原始數據集的方法：評測系統用以評估不同鏈接預測方法的測試數據集應是公開、被廣泛接受的數據集，使用爬蟲程序抓取互聯網公開數據集倉庫相應網頁，并構造網頁對應HTML代碼的DOM樹，依據該DOM樹中下載標簽對應的超鏈接爬取滿足該要求的數據集，并根據其應用場景將收集得到的數據集分為若干類別；

2）計算每一類別應選數據集數量：有效的評測系統應保證數據集冗余度較小，因此需對每一類別中應選出的作為評測數據集的數據集數量加以限制，每一類別對應的科研文獻數量越多，則可說明該類別的研究熱度越高，所以該類別所選出的評測數據集數量應比研究熱度小的類別所選出的數量要多，以滿足有效評估該類別中過往和將來提出的鏈接預測方法的需求，使用交叉熵來衡量應選數據集數量在類別上的分布與科研文獻在類別上的分布之間的相似程度，并以該相似程度為目標函數，使用最優化算法計算得到最優的應選數據集數量在類別上的分布；

3）基于層次聚類的數據集二叉聚類樹構建算法：自每一類別選出的評測數據集應具有代表性，亦即選出的評測數據集應與盡可能多的同類數據集相似，為衡量同類數據集間的相似度，采用層次聚類的思想，自頂向下根據同類數據集的數據集特性和網絡拓撲屬性對同類數據集進行劃分進而構建二叉聚類樹，其中數據集特性，指網絡數據集是否為有向圖、是否為時序網絡、是否為有權重網絡，其中網絡拓撲屬性，指依據網絡拓撲計算出了若干度量的值，其中度量的值包括圖的最大度和圖的基尼系數；

4）基于最深葉節點優先的數據集選擇算法：構建完二叉聚類樹后，需根據每一類別對應的聚類樹空間結構，從中選取出代表該類別的若干數據集，選擇過程自聚類樹根節點的較大子節點開始，遞歸地對每一非葉節點選擇代表該非葉節點的數據集，直到已選擇出2）中所計算出的該類別應選數據集數量的數據集為止；

5）基于最優子集回歸的數據集難度系數度量：設定數據集的難度系數值與其網絡拓撲結構的若干不同度量值線性相關，其中度量的值包括圖的最大度和圖的基尼系數，從1）中收集出的所有數據集中簡單抽樣出若干數據集，并利用若干經典的鏈接預測方法在這些數據集上的實驗表現，使用最優子集回歸法建立數據集難度系數值與網絡拓撲結構度量值之間的線性關系，將得到的難度系數值進行0-1標準化，并將0-1區間劃分為5個部分，分別為難、中難、中等、中易、易，對4）中選擇出的數據集進行難度標定；

6）生成測試數據集：由于所有評測數據集均為公開獲取的，為保證公平性，需對評測數據集進行變換，以生成供評估新鏈接預測方法的測試數據集；

變換方法如下：首先使用一對一隨機映射將評測數據集中的頂點標號進行替換，然后打亂替換后的數據集中每一條邊的記錄，最后按照7-2-1原則對數據集進行劃分，得到供訓練的訓練集、驗證集和供評估的測試集，此變換保證了無法根據提供的訓練集和驗證集和網上公開的原始數據集推測出測試集，并且變換前后不影響預測結果；

7）操作數據集：提供了三個操作數據集的API：1. 網絡連通性：提供了自動獲取最大連通分量的API；2. 節點度：提供了根據節點度獲得子圖的API；3. 聚集系數：提供了根據節點聚集系數獲得子圖的API；

8）結果評估：在各類別中滿足需評估的鏈接預測方法要求的測試數據集上運行該鏈接預測方法，使用AUC和準確率作為實驗結果度量，結合各評測數據集的難度系數，給出最終的結果評估，根據鏈接預測方法在各類別測試數據集上的表現差異，評估預測方法的通用性。

2.根據權利要求1所述的一種構建公平的鏈接預測評估系統的方法，其特征在于：所述步驟2）中的最優化算法，在數據集類數10且每一類應選數據集的數量變化區間長度8的情況下，直接使用網格搜索法獲得全局最優解，如果復雜度高于上述情況，則可使用遺傳算法作為最優化算法進行求解。

3.根據權利要求1所述的一種構建公平的鏈接預測評估系統的方法，其特征在于：步驟3）中的層次聚類，根據網絡拓撲屬性對節點進行劃分時，利用的是基于歐幾里得距離的2-mean聚類算法。

4.根據權利要求1所述的一種構建公平的鏈接預測評估系統的方法，其特征在于：步驟5）中的難度系數，其絕對數值無直接意義，但不同數據集的難度系數值之間的相對數量關系可用來反映不同數據集之間的難度差異。

5.根據權利要求1所述的一種構建公平的鏈接預測評估系統的方法，其特征在于：步驟8）中的AUC，指的是ROC曲線下的面積，ROC曲線是描述真正例率和假正例率之間數量關系的曲線。