[發明專利]一種基于樣本密度的全局優化K均值聚類方法及系統

在審

• 申請號: 201810525709.1
• 申請日: 2018-05-28
• 公開（公告）號: CN108985318A
• 公開（公告）日: 2018-12-11
• 發明（設計）人: 許鴻文;薛印璽;陳雯;李羚;殷蔚明;謝靖
• 申請（專利權）人: 中國地質大學（武漢）
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 武漢知產時代知識產權代理有限公司 42238
• 代理人: 郝明琴

本發明針對傳統K均值聚類方法中存在的聚類結果依賴于初始聚類中心極易陷入局部最優的問題，提出一種基于樣本密度的全局優化K均值聚類KMS?GOSD方法及系統。在迭代過程中，KMS?GOSD方法首先通過高斯模型得到所有聚類中心的預估計密度值，然后將實際密度值低于預估計密度值最大的聚類中心進行偏移操作。通過優化聚類中心位置，KMS?GOSD方法不僅能提升全局探索能力，而且可以克服對聚類初始中心點的依賴性。采用標準的UCI數據集進行本發明對比，發現改進后的方法相比傳統的方法有較高的準確率和穩定性。

技術領域

本發明涉及機器學習中的快速密度峰值聚類領域，尤其涉及到一種基于樣本密度的全局優化K均值聚類方法及系統。

背景技術

傳統K-均值聚類方法具有簡單有效、收斂速度快、便于處理大型數據集等優點，目前已經被廣泛適用于科學研究和工業運用等許多領域。但復雜數據集中存在的全局探索能力弱、易陷入局部最優等問題，仍然是改進K均值研究中的重難點問題。

利用密度峰值聚類方法的核心思想，國內外學者對K均值方法進行以不同角度的分析及改進。國內如邢長征提出一種基于平均密度優化初始聚類中心的方法。采用在聚類之前分析數據對象的屬性及結構，選取合適的初始聚類中心，代替傳統K均值隨機初始中心點，而保持傳統K均值的迭代過程不變。國外學者提出在迭代過程通過核函數、自適應神經網絡方法、差分進化方法等方法輔助K均值在全局范圍內尋找密度高的樣本點的方法。如文獻《Approximate Normalized Cuts without Eigen-decomposition InformationSciences》中提出的通過使用近似加權核函數優化目標函數。

由于傳統K均值對聚類中心敏感，從而聚類中心的選取將直接影響聚類準確率的高低。文獻《K-means算法的初始聚類中心的優化》《一種基于局部密度的分布式聚類挖掘算法》指出聚類中心應處于團簇中樣本密度相對較高的點。文獻《一種改進的k-means初始聚類中心選取算法》《一種新的k-means聚類中心選取算法》《最小方差優化聚類中心的K-means算法》通過對理論分析及本發明效果表明：當聚類中心位于樣本密度較高的點時，聚類準確率可以明顯提升。

發明內容

針對傳統K均值聚類方法中存在的聚類結果依賴于初始聚類中心極易陷入局部最優的問題，為避免對無用數據對象的過多分析及加快方法全局探索的速度，本發明提出基于樣本密度的全局優化K均值聚類方法(Global Optimized K-means ClusteringAlgorithm based on Sample Density，簡稱KMS-GOSD)。在傳統K均值聚類方法迭代的過程中，KMS-GOSD方法通過將實際密度值低于預估計密度值最大的一個聚類中心偏移到該類中大于預估計密度值的點，實現避免陷入局部最優，進而克服聚類結果對初始聚類中心的依賴性。同時在偏移前，加入與迭代次數成反比的衰減因子使預估計密度值逐漸降低，進而降低聚類中心的偏移概率。這樣可以保證KMS-GOSD方法前期具有較強的全局探索能力，后期也具有較強的穩定性。

所述一種基于樣本密度的全局優化K均值聚類方法包含以下步驟：

S1、獲取包含N個樣本點的原始數據集X、子簇個數K及比例參數Ra，其中N大于1；

S2、在所述原始數據集X中隨機選取K個樣本點作為初始聚類中心，記為w_i,其中i＝1,2,3,…,K；

S3、分別計算原始數據集中初始聚類中心以外的所有樣本點距離每一個初始聚類中心w_i的距離，并將所述原始數據集中初始聚類中心以外的所有樣本點分配到距離其最近的初始聚類中心形成K個子簇；

S4、分別將所有子簇的質心記為W_i，根據公式計算W_i的預估計密度值F_i,t，并計算W_i實際密度值F_i,c；