[發明專利]一種基于密度核心的最小生成樹聚類算法及系統

在審

• 申請號: 202011110208.0
• 申請日: 2020-10-16
• 公開（公告）號: CN112364887A
• 公開（公告）日: 2021-02-12
• 發明（設計）人: 高強;高琴琴;熊忠陽;張玉芳
• 申請（專利權）人: 重慶大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06F16/2458
• 代理公司: 重慶雙馬智翔專利代理事務所(普通合伙) 50241
• 代理人: 顧曉玲

1.一種基于密度核心的最小生成樹聚類算法，其特征在于，包括以下步驟：

S1，初始化參數，為數據集構建一顆KD樹；

S2，遍歷數據集，采用自然鄰居法獲取數據點的逆近鄰信息和自然特征值，統計每個數據點的逆近鄰數目；

S3，將逆近鄰數目不小于自然特征值的數據點作為密度核心點，這些密度核心點組成密度核心點集合RCore；

S4，根據密度核心集合RCore建立最小生成樹，得到最小生成樹中各個邊的權值的集合；

S5，根據最小生成樹中各個邊的權值的集合計算切邊閾值，并根據該閾值切除最小生成樹中連接不同簇的邊，得到各個子簇最小生成子樹；

S6，根據得到的子簇最小生成子樹聚類密度核心；

S7,將非密度核心點分配到距離其最近的密度核心的簇中，完成聚類。

2.根據權利要求1所述的基于密度核心的最小生成樹聚類算法，其特征在于，所述步驟S2具體為：

S2-1，在kd樹中遍歷數據集，搜索每一個數據點的k近鄰并更新每一個數據點的k近鄰集合以及其k近鄰數量，k的初始值為M，M為正整數；

S2-2、對于數據點p和數據點q，若p是q的k近鄰，同時q也是p的k近鄰，那么數據點p和q互為自然鄰居；如果數據點p在數據點q的k近鄰集合中，稱數據點q為數據點p的逆k近鄰，搜索自然鄰居，統計更新每個數據點的逆k近鄰集合；

S2-3、如果存在有數據點沒有逆k近鄰或無逆k近鄰的數據點的數量發生了變化，則k值加1并執行步驟S2-1；如果數據集中的每一個數據點都有逆k近鄰或者無k逆近鄰的數據點的數量不再發生變化時，此時數據集中的狀態就達到了自然穩定狀態，k值不再遞增，此時的k值即為自然特征值，執行步驟S2-4；

S2-4，根據每個數據點的逆k近鄰集合統計其逆近鄰數目。

3.根據權利要求1所述的基于密度核心的最小生成樹聚類算法，其特征在于，所述步驟S5具體為：

切邊閾值cutθ＝mean(Edge)+w*std(Edge)，其中，mean(Edge)表示最小生成樹中所有邊權值的均值，std(Edge)表示最小生成樹中所有邊權值的標準差，w是常數；

遍歷最小生成樹的邊集，將大于切邊閾值的邊進行切除，此時密度核心點集合分割成各個獨立的子簇最小生成子樹。

4.根據權利要求1所述的基于密度核心的最小生成樹聚類算法，其特征在于，所述步驟S6具體為：

在切除最小生成樹中大于切邊閾值的邊后，得到了各個子簇最小生成子樹，根據各個子簇中最小生成子樹的樹結構分配簇標簽：根據分離后的各個簇的密度核心點保留的最小生成子樹結構，將各個密度核心進行聚類，即將同一子簇最小生成樹上的點分配至同一簇中。

5.根據權利要求4所述的基于密度核心的最小生成樹聚類算法，其特征在于，將密度核心聚類得到簇標簽后，將其中小于總密度核心點數2％的密度核心簇作為噪聲簇進行剝離。

6.一種基于權利要求1-5任一項所述最小生成樹聚類算法的系統，其特征在于，包括存儲器和處理器，所述處理器和所述存儲器相互通信連接，所述存儲器存儲有可被所述處理器執行的程序指令，所述處理器調用所述程序指令執行如權利要求1至5任一所述的算法。