[發明專利]基于密度的聚類計算方法、裝置、設備和存儲介質

在審

• 申請號: 202210918798.2
• 申請日: 2019-08-30
• 公開（公告）號: CN115310527A
• 公開（公告）日: 2022-11-08
• 發明（設計）人: 吳昆臨;許秋子
• 申請（專利權）人: 深圳市瑞立視多媒體科技有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 深圳市鼎泰正和知識產權代理事務所(普通合伙) 44555
• 代理人: 繆太清

本發明涉及智能決策技術領域，尤其涉及一種基于密度的聚類計算方法、裝置、設備和存儲介質。本發明通過將一維或多維空間切分成多個網格，開啟多個線程，一條線程對應一個數據點，利用多條線程同時運行，計算對應的數據點與數據點周圍網格內其他數據點之間的距離，并判斷兩個數據點之間的距離是否小于預設的距離閾值，來確定兩個數據的是否是近鄰點。本發明通過限定只需計算某數據點所在的網格對應的周圍網格內的數據點與該數據點之間的距離是否在距離閾值范圍內，每條線程同時對單個數據點計算與其他數據點的距離，從而大大縮小了整個聚類計算的計算量，大大增加了聚類計算的效率。

技術領域

本發明涉及智能決策技術領域，尤其涉及一種基于密度的聚類計算方法、裝置、設備和存儲介質。

背景技術

聚類分析又稱群分析，它是研究樣品或指標分類問題的一種統計分析方法，同時也是數據挖掘的一個重要算法。聚類分析是把參數相似的數據分成不同的組別，其應用非常廣泛，例如應用于數據挖掘、機器學習等。

聚類分析的算法有很多種，有一些基于數據的密度進行聚類，例如DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法和OPTICS(Ordering Point To Idenfy the Cluster Stucture)算法等。當前技術中，基于密度的聚類算法的最大缺點在于步驟非常耗時，假設有一組數據，它們是1000個二維空間的點，在基于密度的聚類算法中，要確定每一個點有哪些近鄰點，與該點之間的距離小于一個定義的閾值ε的點為近鄰點，需要計算每一個點和其他999個點的距離，所以總共計算1000×999＝999,000次，顯然該計算量過大。

發明內容

本發明的主要目的在于提供一種基于密度的聚類計算方法、裝置、設備及計算機可讀存儲介質，旨在解決目前的基于數據的密度進行聚類算法計算量過大造成非常耗時的技術問題。

為實現上述目的，本發明提供一種基于密度的聚類計算方法，所述方法包括以下步驟：

將數據點所在的一維或多維空間切分成多個網格，每個所述網格的空間大小相同；

開啟多個線程，所述線程的數量與所述數據點的數量相同，一條所述線程對應一個所述數據點；

利用多條所述線程同時運行，計算對應的所述數據點與所述數據點周圍網格內其他數據點之間的距離；

利用多條所述線程同時運行，判斷兩個所述數據點之間的距離是否小于預設的距離閾值，若是，則一個所述數據點是另一個所述數據點的近鄰點。

可選地，所述將數據點所在的一維或多維空間切分成多個網格，每個所述網格的空間大小相同，包括：

獲取預設的距離閾值，根據所述距離閾值，對所述一維或多維空間切分成多個空間大小相同的網格，若設距離閾值為ε，則每個網格的空間范圍均為0.5ε-1.5ε之間；

獲取預設的編號順序規則，根據所述編號順序規則對已切分的多個網格進行編號。

可選地，所述獲取預設的編號順序規則，根據所述編號順序規則對已切分的多個網格進行編號后，還包括：

獲取所有的數據點在所述一維或多維空間內的坐標，對所有的坐標進行排序；

以排序的順序，依次獲取數據點的坐標，根據所述網格的空間大小，及所述編號順序規則，確定所述數據點在所述一維或多維空間內被切分后的網格編號，并記錄所述網格編號與所述坐標的對應關系；

遍歷所有的數據點的坐標，得到每個被切分后的網格編號及對應的所述坐標的對應關系。

可選地，所述利用多條所述線程同時運行，計算對應的所述數據點與所述數據點周圍網格內其他數據點之間的距離，包括：