[發明專利]一種量子行走的空間聚類方法

有效

• 申請號: 201710351832.1
• 申請日: 2017-05-18
• 公開（公告）號: CN107194421B
• 公開（公告）日: 2021-06-04
• 發明（設計）人: 董玉民;肖淑芬
• 申請（專利權）人: 青島理工大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 濟南圣達知識產權代理有限公司 37221
• 代理人: 趙敏玲

本發明公開了一種量子行走的空間聚類方法，包括：步驟一，初始化n維空間，n為數據點的維度，并將數據點自然映射到空間上；定義一個距離函數；步驟二，檢查包括數據點的空間數目λ與聚類數目θ之間的關系，如果λ＞θ，找出潛在的孤立點空間，并分別計算含有數據點的空間中所含數據點數量最少的空間V_min相對于含有數據點的鄰域中每個空間的總收益；若λ＝θ，則執行步驟六；步驟三，空間合并與坍縮，合并坍縮后跳回步驟二；步驟四，當包含數據點的空間數量達到聚類數時，如果空間不相鄰，則結束，得到相應的聚類結果。

技術領域

本發明涉及一種量子行走的空間聚類方法。

背景技術

文獻“量子隨機行走的基本性質及應用研究”“Models of cooperation based onthe prisoner’s Dilemma and the Snowdrift game”“Five Rules for the Evolutionof Cooperation”等提出了一個基于圖的量子博弈聚類算法，該算法將數據點看作參與博弈的人。在博弈過程中，參與人都希望自己的利益最大化。文獻“基于網格的量子博弈聚類算法”提出一種基于網格的量子博弈聚類算法，算法將數據點看作是博弈的參與人，通過在收益矩陣中內嵌距離函數，使相似的數據點能夠獲得更大的收益，從而形成聚類。這些方法聚類效果還不是很令人滿意，得到最終結果的過程比較長，不能迅速的得到聚類結果。

發明內容

本發明的目的就是為了解決上述問題，提供一種量子行走的空間聚類方法，能夠快速得到聚類結果，能更快更好地解決問題。

為了實現上述目的，本發明采用如下技術方案：

一種量子行走的空間聚類方法，包括：

步驟一，初始化n維空間，n為數據點的維度，并將數據點自然映射到空間上；定義一個距離函數；

步驟二，檢查包括數據點的空間數目λ與聚類數目θ之間的關系，如果λ＞θ，找出潛在的孤立點空間，并分別計算含有數據點的空間中所含數據點數量最少的空間V_min相對于含有數據點的鄰域中每個空間的總收益；若λ＝θ，則執行步驟六；

步驟三，空間合并與坍縮，合并坍縮后跳回步驟二；

步驟四，當包含數據點的空間數量達到聚類數時，如果空間不相鄰，則結束，得到相應的聚類結果。

所述步驟一中，為了使任意空間中的數據點具有相同的行走環境，對于3維的情況，設定量子行走空間的上下、左右、前后邊界相連。

所述步驟一中的距離函數滿足兩個點之間的距離越靠近時，函數值就越小。

所述步驟二中，孤立點空間的尋找方法為：

查找含有數據點的空間中所含數據點數量最少的空間，記為V_min；若其鄰域沒有數據點，則將其鄰域都并入V_min；如果合并后的V_min所占體積達到總體積設定，則該空間即為潛在的孤立點空間。

所述步驟二中總收益的計算方法為，

查找含有數據點的空間中所含數據點數量最少的空間，記為V_min，如果V_min的鄰域中有數據點，則V_min中的所有數據點分別與鄰域內的所有數據點進行一次收益比較，然后分別計算出V_min中數據點相對鄰域中每個空間的總收益。

所述步驟三中的具體方法為，計算V_min中的每個數據點相對于含有數據點的鄰域內的所有數據點的收益，根據計算出的收益決定新的歸屬，整個空間按照少數服從多數的原則合并到某個鄰域空間中；合并后的空間體積并不擴大，而是坍縮到一個空間的大小。