[發明專利]一種利用GPU加速密度峰聚類的方法

有效

• 申請號: 202010811897.1
• 申請日: 2020-08-13
• 公開（公告）號: CN112052879B
• 公開（公告）日: 2023-06-13
• 發明（設計）人: 蘇雨萱;張巖峰;宛長義;于戈
• 申請（專利權）人: 東北大學
• 主分類號: G06F18/23
• 分類號: G06F18/23;G06F9/50;G06F18/2431;G06F18/2321
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 戴風友;梅洪玉

1.一種利用GPU加速密度峰聚類的方法，其特征在于，步驟如下：

步驟1：在GPU上構建制高點樹VP-Tree（vantage?point?tree）的索引結構；

步驟1.1：從上到下選出制高點樹每層的制高點；先從所有數據點隨機選出一個點，然后計算出距離該點最遠的點最為制高點樹的根節點；

步驟1.2：計算每個點與制高點的距離，按照距離的大小排序后等分成兩部分，距離的中值M作為根節點對應的查詢半徑；

步驟1.3：分別選擇左右子樹的最后一個點，即距離上一層制高點最遠的點，做為下一層的制高點；

步驟1.4：重復步驟1.2和1.3，直到當前分支內點的數量不大于32個，把這些點的序號儲存到同一個數組內作為葉子節點；

步驟2：利用步驟1中的制高點樹索引計算每個數據點的密度值；

步驟2.1：給GPU每個warp分配一個點進行并行處理，構建棧結構來儲存待訪問節點，把制高點樹的根節點入棧，給定的dc值作為查詢半徑；其中warp為32個線程一組；

步驟2.2：彈出棧頂元素，如果是分支節點，則計算待查詢點與當前制高點的距離r，如果r-dc≤M，則把左子樹根節點入棧；如果r+dc≥M,?則把右子樹根節點入棧；如果是葉子節點，則加入待篩選的點集；

步驟2.3：重復步驟2.2，直到棧空；

步驟2.4：計算待篩選點集中與當前點距離不超過dc的點數量作為該點的密度；

步驟3：利用步驟2中的每個數據點的密度值和制高點樹索引計算每個數據點的斥群值；

步驟3.1：利用步驟2中得到每個點的密度值，選出每個點P的待篩選點集中密度比該點大且距離最近的點；若存在，則這個點作為點P的依賴點，距離值作為點P的斥群值；若不存在，則把點P加入到未找到依賴點的集合中；

步驟3.2：根據每個點的密度值對所有點進行從大到小排序；

步驟3.3：根據密度值對未找到依賴點集合中的點進行從大到小排序；其中，密度值最大的點選擇數據集中距離自己最遠的點作為依賴點，距離值作為斥群值；其他點在步驟3.2中得到的序列中，找到密度值比自己大，且距離最近的點作為依賴點，距離值作為斥群值；

步驟4：利用每個數據點的密度值和斥群值，構建決策圖后由用戶根據聚類中心的密度值和斥群值同時較大的原則選出聚類中心點；

步驟5：利用步驟3中得到每個點的依賴點，構建被依賴關系，然后從步驟4中用戶選出的聚類中心點開始分配每個點所屬的聚類。