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

有效

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

本發明屬于大數據處理領域，涉及一種利用GPU加速密度峰聚類的方法。本發明通過設計新的索引結構來減少距離矩陣的計算量，并利用GPU來加速索引的構建和近鄰搜索，提高密度峰聚類算法中每個點的密度值和斥群值計算效率。本發明通過在GPU上構建制高點樹索引，并行地計算每個數據點的密度值和斥群值，在用戶選擇完聚類中心后可以并行分配每個點所屬的聚類，有效地減少了距離矩陣的計算量且節省儲存空間。相較于傳統的聚類方法，使用GPU加速的密度峰聚類方法能夠更高效地完成聚類任務。

技術領域

本發明屬于大數據處理領域，涉及一種利用GPU加速密度峰聚類的方法。

背景技術

聚類分析是大數據處理中數據挖掘領域中的一類任務，主要研究的是如何將數據點劃分成為多個簇，使得每個簇至少包含一個對象，讓同一個類別內的個體之間具有較高的相似度，不同類別之間具有較大的差異性。數據聚類中有許多高效且新穎的算法，其中密度峰算法理論簡單復雜度低是一種十分有效的方法，不像傳統的K-Means方法一樣需要輸入參數。但是密度峰算法有個缺點，在實現密度峰算法時需要距離矩陣的構建，這意味著它在處理大數據量時需要更高的計算性能和儲存量。高性能計算是計算科學的一個分支，研究并行算法和相關軟件，致力于研發高性能計算機滿足科學計算、工程計算、海量數據處理等需求。在高性能計算領域，GPU(圖像處理單元)相比于CPU具有更強大的計算能力，這吸引著用戶設計新的并行算法采用GPU加速來提高執行效率。

發明內容

針對于上述問題，本發明提出來基于GPU加速密度峰聚類的算法。本發明旨在通過設計新的索引結構來減少距離矩陣的計算量，并利用GPU來加速索引的構建和近鄰搜索，提高密度峰聚類算法中每個點的密度值和斥群值計算效率。

本發明的技術方案是：

一種利用GPU加速密度峰聚類的方法，步驟如下：

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

制高點樹是度量空間中一種基于距離的的索引結構。其基本思想是將二分查找用于只有距離信息的多維度量空間中，采用特征空間的目標點集的點與制高點之間的距離信息對特征空間進行劃分，再利用三角不等式進行查詢。制高點樹的構建的復雜度低,且對高維數據仍然適用，查詢近鄰點的搜索復雜度低。樹結構的左右自平衡的特點適合GPU的內存訪問特性和線程執行方式。

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

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

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

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

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

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

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

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

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

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