[發明專利]一種基于決定路徑權重的不確定圖分割方法及系統

在審

• 申請號: 201510046765.3
• 申請日: 2015-01-29
• 公開（公告）號: CN104573730A
• 公開（公告）日: 2015-04-29
• 發明（設計）人: 李紅娜;劉志超;寧立;張涌
• 申請（專利權）人: 中國科學院深圳先進技術研究院
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 深圳中一專利商標事務所 44237
• 代理人: 張全文

1.一種基于決定路徑權重的不確定圖分割方法，其特征在于，所述方法包括：

建立不確定加權圖；

以鄰接矩陣的形式對所述不確定加權圖進行存儲；

計算存儲后的所述不確定加權圖中各節點之間的決定路徑權重；

基于所述決定路徑權重，利用k-means算法對所述不確定加權圖中的節點進行劃分，獲得多個節點子集。

2.如權利要求1所述的方法，其特征在于，所述計算存儲后的所述不確定加權圖中各節點之間的決定路徑權重包括：

計算各個節點之間的距離并且循環更新各個節點之間的距離，直到所述距離達到最小，各節點之間的最小距離即為所述決定路徑權重；具體包括：

步驟1：從所述不確定加權圖中選擇任意兩節點u、v；

步驟2：初始化，令所述節點u到節點v的決定路徑權重為零；

步驟3：訪問節點u的每一個鄰居節點，以節點u到鄰居節點的距離乘以鄰居節點到節點v的距離；

步驟4：取最小的乘積作為節點u到節點v的距離；

步驟5：重復步驟3和4，直到計算的距離不再發生變化時，將該距離作為節點u到節點v的最小距離。

3.如權利要求2所述的方法，其特征在于，所述方法還包括：

為每個節點設置標記字段mark＝0，對每一個被訪問過的鄰居節點更改標記字段mark＝1。

4.如權利要求1所述的方法，其特征在于，所述基于所述決定路徑權重，利用k-means算法對所述不確定加權圖中的節點進行劃分，獲得多個節點子集包括：

步驟1：初始化，令所述不確定加權圖中每個節點的標簽值都為空；

步驟2：從所述不確定加權圖中隨機選擇k個節點作為k個子集的中心節點，分別為k個中心節點標簽值賦值1,2,3…k,所述k為大于零的整數；

步驟3：對于除中心節點之外的每個節點，計算該節點到每個中心節點的距離，選擇距離最小的一個中心節點所屬的子集，并將該節點的標簽值更新為該子集的標簽值；

步驟4，重新選擇中心節點，并重復步驟3，直到所有節點的標簽值，以及該節點到各個子集的中心節點的距離不再發生變化。

5.如權利要求4所述的方法，其特征在于，所述計算該節點到每個中心節點的距離包括：

在該節點的鄰居節點中查找屬于目標子集且距離所述目標子集的中心點最近的鄰居節點，若不存在該鄰居節點，則跳過該目標子集；若存在該鄰居節點，則該節點到所述目標子集的中心節點的距離等于該節點到該鄰居節點的距離乘以該鄰居節點到所述目標子集的中心點的距離。

6.一種基于決定路徑權重的不確定圖分割系統，其特征在于，所述系統包括：

不確定圖建立單元，用于建立不確定加權圖；

存儲單元，用于以鄰接矩陣的形式對所述不確定加權圖進行存儲；

決定路徑權重計算單元，用于計算存儲后的所述不確定加權圖中各節點之間的決定路徑權重；

聚類單元，用于基于所述決定路徑權重，利用k-means算法對所述不確定加權圖中的節點進行劃分，獲得多個節點子集。

7.如權利要求6所述的系統，其特征在于，所述決定路徑權重計算單元具體用于，計算各個節點之間的距離并且循環更新各個節點之間的距離，直到所述距離達到最小，各節點之間的最小距離即為所述決定路徑權重；所述決定路徑權重計算單元包括：

選擇模塊，用于從所述不確定加權圖中選擇任意兩節點u、v；

初始化模塊，用于初始化，令所述節點u到節點v的決定路徑權重為零；

計算模塊，用于訪問節點u的每一個鄰居節點，以節點u到鄰居節點的距離乘以鄰居節點到節點v的距離；

確定模塊，用于取最小的乘積作為節點u到節點v的距離；

控制模塊，用于控制所述計算模塊以及確定模塊的執行，直到計算的距離不再發生變化時，將該距離作為節點u到節點v的最小距離。

8.如權利要求7所述的系統，其特征在于，所述決定路徑權重計算單元還包括：

標記字段更改模塊，用于為每個節點設置標記字段mark＝0，對每一個被訪問過的鄰居節點更改標記字段mark＝1。