[發明專利]一種基于決策樹分類器的跳數矩陣恢復方法

有效

• 申請號: 202110278022.4
• 申請日: 2021-03-15
• 公開（公告）號: CN112884067B
• 公開（公告）日: 2023-08-01
• 發明（設計）人: 劉星成;趙瑩瑩
• 申請（專利權）人: 中山大學
• 主分類號: G06F18/214
• 分類號: G06F18/214;G06F17/16;G06F18/2431
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 劉俊

1.一種基于決策樹分類器的跳數矩陣恢復方法，其特征在于：所述的方法包括步驟如下：

S1：通過泛洪過程，獲取的跳數矩陣中含有缺失項；

S2：根據跳數矩陣中部分被觀測到的跳數之間的關系構建訓練集，將跳數矩陣中觀測到的跳數值建模為訓練集的標簽，最大跳數值表示為類別數；

S3：根據步驟S2得到的訓練樣本集合訓練決策樹分類器；

S4：為沒有觀測到的跳數值構造特征，得到未知樣本；將未知樣本輸入到訓練好的決策樹分類器，得到未知樣本的類別，即得到矩陣中對應位置的缺失的跳數值，從而恢復出完整的跳數矩陣H；

步驟S4，具體地，

S401：若跳數矩陣中某個位置的跳數值沒有被觀測到，則進行下一步；否則遍歷跳數矩陣中下一個值；

S402：跳數缺失的兩個節點分別用節點i和節點j表示，相對于網絡中其他所有的節點k,k＝1,2,…,n，計算節點i到節點k的跳數值和節點k到節點j的跳數值的跳數之和的最小值，作為未知樣本的第一個特征；

S403：計算節點i的鄰居節點到節點j的跳數，和節點j的鄰居節點到節點i的跳數的平均值，作為未知樣本的第二個特征；

S404：將構造的未知樣本的第一個特征、第二個特征組成一個未知樣本，輸入到訓練好的決策樹分類器，得到未知樣本的類別，即得到該位置的跳數值；

S405：若沒有完成對跳數矩陣的遍歷，則遍歷矩陣中下一個值，并返回步驟S401；若遍歷完跳數矩陣得到恢復后的跳數矩陣；

構建所述的未知樣本，表達如下：

其中，表示節點i到節點k的跳數值和節點k到節點j的跳數值之和的最小值。

2.根據權利要求1所述的基于決策樹分類器的跳數矩陣恢復方法，其特征在于：構造建立任意節點i的跳數向量：h_i＝{h_i1,h_i2,…,h_in}，其中，h_ij表示節點i和節點j之間的跳數值；i＝1,…,n；j＝1,…,n；

所述的缺失的跳數矩陣表示為式(2)：

其中，⊙表示Hadamard乘積；Ω＝[ω_ij]_n*n是一個二元矩陣；ω_ij表示跳數矩陣對應位置是否缺失，表示為：

3.根據權利要求2所述的基于決策樹分類器的跳數矩陣恢復方法，其特征在于：在步驟S1之后，步驟S2之前，如果缺失的跳數的對稱位置被觀測到，使用對稱位置跳數將其補齊。

4.根據權利要求3所述的基于決策樹分類器的跳數矩陣恢復方法，其特征在于：步驟S2，具體的步驟如下：

S201：對跳數矩陣進行遍歷，若某個位置跳數值被觀測到，則進行下一步；否則遍歷跳數矩陣中下一個值；

S202：跳數缺失的兩個節點分別用節點i和節點j表示，相對于網絡中其他所有的節點k,k＝1,2,…,n，計算節點i到節點k的之間跳數值和節點k到節點j之間的跳數值的跳數和的最小值，作為訓練樣本的第一個特征；

S203：計算節點i的鄰居節點到節點j的跳數，和節點j的鄰居節點到節點i的跳數的平均值，作為訓練樣本的第二個特征；

S204：將被觀測到的跳數作為類別，加上構造的樣本的第一個特征和第二個特征形成一個訓練樣本，加入到訓練樣本集合中；

S205：遍歷整個跳數矩陣遍歷結束后，得到訓練樣本集合。

5.根據權利要求4所述的基于決策樹分類器的跳數矩陣恢復方法，其特征在于：步驟S203，具體的，初始化兩個鄰居列表L_i和L_j，根據跳數向量選擇節點i的鄰居，根據跳數向量選擇節點j的鄰居；節點i的鄰居節點的索引和節點j的鄰居節點的索引分別存儲在對應的鄰居列表L_i和L_j中；變量n_i表示節點i的可用鄰居節點數，變量n_j表示節點j的可用鄰居節點數；如果觀察到鄰居節點L_i(k)與節點j之間的跳數則可用鄰居節點n_i加1；

其中，訓練樣本的第二個特征的計算方式如式(4)：

（4）。