[發明專利]一種新型密度聚類方法

有效

• 申請號: 202011165194.2
• 申請日: 2020-10-27
• 公開（公告）號: CN112183664B
• 公開（公告）日: 2022-11-29
• 發明（設計）人: 梁少軍
• 申請（專利權）人: 中國人民解放軍陸軍工程大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 武漢宇晨專利事務所(普通合伙) 42001
• 代理人: 李鵬;王敏鋒

本發明公開了一種新型密度聚類方法，對飛行數據矩陣進行歸一化處理和降維處理；計算距離矩陣；計算近鄰向量；篩選核心點飛行數據、離群點飛行數據及待定點飛行數據；獲得所有核心點飛行數據對應的聚類類標；獲得所有待定點飛行數據的聚類類標；剔除飛行數據矩陣中離群點飛行數據，最終聚類結果。本發明可有效提高算法的效率。有效降低了計算開銷。

技術領域

本方法屬于數據挖掘領域，具體涉及一種新型密度聚類方法。

背景技術

聚類分析是根據數據間的內在關系將數據分成不同簇的方法，在眾多的聚類分析算法中，考慮噪聲基于密度的空間聚類算法(Density-Based Spatial Clustering ofApplications with Noise,DBSCAN)是一種具有噪聲處理能力的劃分式、互斥式、部分聚類算法。該算法通過把高密度點連成一片，進而生成各種簇，具有自動刪除離群點，能處理任意形狀和大小的數據，自主推定聚類簇個數，對噪聲具有較強的魯棒性等諸多有點，目前已廣泛應用于多個領域，如光譜分析、遙感測繪、生物醫學等多個領域。

傳統的DBSCAN算法需要提前指定近鄰個數Minpts和鄰域半徑ε兩個變量。定義Ds(d_i)為距離數據d_i的ε鄰域半徑內數據的量，若Ds(d_i)≥Minpts，則d_i為核心點數據；若Ds(d_i)＜Minpts且d_i在至少一個核心數據的ε鄰域內，則d_i為邊界點數據；若d_i既非邊界點又非核心點，則d_i為離群點數據；傳統DBSCAN算法隨機選擇一個數據作為分析對象，若該數據是核心點數據，則查找該數據ε鄰域半徑內所有數據并將其放在一個簇中。之后將此數據ε鄰域半徑內其他數據分別作為分析對象重復以上過程。所有數據被處理完畢后，密度相連的核心點和邊界點形成各個簇，離群數據被拋棄。

但是，傳統的DBSCAN算法只能在算法結束后才能獲取最終聚類結果，不能輸出階段性成果，不能獲取模糊聚類結果，且計算開銷較大。

發明內容

發明所要解決的技術問題是克服現有技術的缺陷，提供一種新型密度聚類方法，本發明基于傳統DBSCAN算法思想，在深入分析數據分布規律基礎上提出了新的密度聚類方法。該算法將各數據距其第Minpts+1個近鄰的距離與鄰域半徑ε進行比對，進而將數據分為核心點、離群點和待定點三類。之后采用不同策略對各類數據分別處理：核心點可以直接做傳統聚類分析以獲取模糊聚類結果；離群點可以直接剔除，以減少計算開銷；待定點可以在合理設計邏輯規則基礎上基于前期算法運算結果和遍歷查找操作判斷聚類類標。算法遵循傳統DBSCAN思想，但另辟蹊徑，利用了數據分布規律及分組策略，達到了與傳統DBSCAN算法相同聚類效果。

本發明的上述技術問題主要是通過下述技術方案得以解決的：

一種新型密度聚類方法，包括以下步驟：

步驟1、對飛行數據矩陣X進行歸一化處理和降維處理獲得飛行數據矩陣

步驟2、根據飛行數據矩陣計算距離矩陣D；

步驟3、根據距離矩陣D計算飛行數據矩陣的Minpts近鄰向量

步驟4、根據Minpts近鄰向量篩選核心點飛行數據、離群點飛行數據及待定點飛行數據，獲得核心點飛行數據索引集合C、待定點飛行數據索引集合U、以及離群點飛行數據索引集合O；

步驟5，按照核心點飛行數據索引集合C從飛行數據矩陣中取出核心點飛行數據矩陣對核心點飛行數據矩陣進行聚類，并獲得所有核心點飛行數據對應的聚類類標；

步驟6、根據待定點飛行數據索引集合U從飛行數據矩陣中取出待定點飛行數據矩陣判斷待定點飛行數據的聚類類標；