[發(fā)明專利]基于密度的聚類計(jì)算方法、裝置、設(shè)備和存儲介質(zhì)

在審

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

1.一種基于密度的聚類計(jì)算方法，其特征在于，所述方法把參數(shù)相似的數(shù)據(jù)分成不同的組別，基于數(shù)據(jù)的密度進(jìn)行聚類，是研究樣品或指標(biāo)分類問題的一種統(tǒng)計(jì)分析方法，其應(yīng)用于數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)，具體包括以下步驟：

將數(shù)據(jù)點(diǎn)所在的一維或多維空間依據(jù)距離閾值切分成多個(gè)網(wǎng)格，每個(gè)所述網(wǎng)格的空間大小相同，包括：采用集中對一維或多維空間內(nèi)所有的數(shù)據(jù)點(diǎn)確定其所在的網(wǎng)格編號，以便為后續(xù)查找數(shù)據(jù)點(diǎn)的網(wǎng)格編號及其對應(yīng)的周圍網(wǎng)格編號提供準(zhǔn)確的數(shù)據(jù)；

根據(jù)一維或多維空間內(nèi)的數(shù)據(jù)點(diǎn)的個(gè)數(shù)，確定開啟的線程的個(gè)數(shù)，以確保一個(gè)數(shù)據(jù)點(diǎn)對應(yīng)有一條線程為其服務(wù)，進(jìn)行距離的計(jì)算及近似點(diǎn)的判斷；

利用多條所述線程同時(shí)運(yùn)行，計(jì)算對應(yīng)的所述數(shù)據(jù)點(diǎn)與所述數(shù)據(jù)點(diǎn)周圍網(wǎng)格內(nèi)其他數(shù)據(jù)點(diǎn)之間的距離，包括：通過數(shù)據(jù)點(diǎn)的坐標(biāo)確定網(wǎng)格編號，通過網(wǎng)格編號及編碼順序規(guī)則，確定所述數(shù)據(jù)點(diǎn)周圍的網(wǎng)格編號，只計(jì)算所述數(shù)據(jù)點(diǎn)與周圍網(wǎng)格編號內(nèi)的其他數(shù)據(jù)點(diǎn)之間的距離，且采用單條線程服務(wù)單個(gè)數(shù)據(jù)點(diǎn)的方式，確保一維或多維空間內(nèi)的所有數(shù)據(jù)點(diǎn)同時(shí)進(jìn)行距離計(jì)算；

利用多條所述線程同時(shí)運(yùn)行，判斷兩個(gè)所述數(shù)據(jù)點(diǎn)之間的距離是否小于預(yù)設(shè)的距離閾值，若是，則一個(gè)所述數(shù)據(jù)點(diǎn)是另一個(gè)所述數(shù)據(jù)點(diǎn)的近鄰點(diǎn)，以便為最終的聚類算法提供直接可靠的數(shù)據(jù)。

2.根據(jù)權(quán)利要求1所述的基于密度的聚類計(jì)算方法，其特征在于，所述將數(shù)據(jù)點(diǎn)所在的一維或多維空間切分成多個(gè)網(wǎng)格，每個(gè)所述網(wǎng)格的空間大小相同，包括：

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

獲取預(yù)設(shè)的編號順序規(guī)則，根據(jù)所述編號順序規(guī)則對已切分的多個(gè)網(wǎng)格進(jìn)行編號。

3.根據(jù)權(quán)利要求2所述的基于密度的聚類計(jì)算方法，其特征在于，所述獲取預(yù)設(shè)的編號順序規(guī)則，根據(jù)所述編號順序規(guī)則對已切分的多個(gè)網(wǎng)格進(jìn)行編號后，還包括：

獲取所有的數(shù)據(jù)點(diǎn)在所述一維或多維空間內(nèi)的坐標(biāo)，對所有的坐標(biāo)進(jìn)行排序；

以排序的順序，依次獲取數(shù)據(jù)點(diǎn)的坐標(biāo)，根據(jù)所述網(wǎng)格的空間大小，及所述編號順序規(guī)則，確定所述數(shù)據(jù)點(diǎn)在所述一維或多維空間內(nèi)被切分后的網(wǎng)格編號，并記錄所述網(wǎng)格編號與所述坐標(biāo)的對應(yīng)關(guān)系；

遍歷所有的數(shù)據(jù)點(diǎn)的坐標(biāo)，得到每個(gè)被切分后的網(wǎng)格編號及對應(yīng)的所述坐標(biāo)的對應(yīng)關(guān)系。

4.根據(jù)權(quán)利要求2或3所述的基于密度的聚類計(jì)算方法，其特征在于，所述利用多條所述線程同時(shí)運(yùn)行，計(jì)算對應(yīng)的所述數(shù)據(jù)點(diǎn)與所述數(shù)據(jù)點(diǎn)周圍網(wǎng)格內(nèi)其他數(shù)據(jù)點(diǎn)之間的距離，包括：

獲取數(shù)據(jù)點(diǎn)在所述一維或多維空間內(nèi)的坐標(biāo)，確定所述數(shù)據(jù)點(diǎn)在所述一維或多維空間內(nèi)被切分后的網(wǎng)格編號；

根據(jù)所述網(wǎng)格編號及所述編號順序規(guī)則，確定所述數(shù)據(jù)點(diǎn)周圍的網(wǎng)格編號；

分別計(jì)算所述數(shù)據(jù)點(diǎn)與周圍的網(wǎng)格編號內(nèi)的其他數(shù)據(jù)點(diǎn)之間的距離，所述距離的計(jì)算公式如下：

其中，D為距離，所述數(shù)據(jù)點(diǎn)在一維或多維空間內(nèi)的坐標(biāo)為(a₁，a₂，...，a_n)，周圍的的網(wǎng)格編號內(nèi)的其他數(shù)據(jù)點(diǎn)在一維或多維空間內(nèi)的坐標(biāo)為(b₁，b₂，...，b_n)，n為一維或多維空間的維數(shù)。

5.一種基于密度的聚類計(jì)算裝置，其特征在于，所述裝置包括：

切分網(wǎng)格模塊，用于將數(shù)據(jù)點(diǎn)所在的一維或多維空間切分成多個(gè)網(wǎng)格，每個(gè)所述網(wǎng)格的空間大小相同；

確定線程模塊，用于開啟多個(gè)線程，所述線程的數(shù)量與所述數(shù)據(jù)點(diǎn)的數(shù)量相同，一條所述線程對應(yīng)一個(gè)所述數(shù)據(jù)點(diǎn)；

計(jì)算距離模塊，用于利用多條所述線程同時(shí)運(yùn)行，計(jì)算對應(yīng)的所述數(shù)據(jù)點(diǎn)與所述數(shù)據(jù)點(diǎn)周圍網(wǎng)格內(nèi)其他數(shù)據(jù)點(diǎn)之間的距離；

確定近鄰點(diǎn)模塊，用于利用多條所述線程同時(shí)運(yùn)行，判斷兩個(gè)所述數(shù)據(jù)點(diǎn)之間的距離是否小于預(yù)設(shè)的距離閾值，若是，則一個(gè)所述數(shù)據(jù)點(diǎn)是另一個(gè)所述數(shù)據(jù)點(diǎn)的近鄰點(diǎn)。