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

在審

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

1.一種基于樣本密度的全局優化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；

其中m為所述迭代次數的最大迭代次數且為預設值，t表示當前的迭代次數，2(3φσ×Ra)的值根據標準正態分布函數查表得出；

S5、將每個子簇的質心W_i作為新的聚類中心，分別判斷每個新的聚類中心所在的子簇中是否存在實際密度值F_i,c小于預估計密度值F_i,t的樣本點，如果不存在，跳轉到S10；如果存在，跳轉到S6；

S6、獲取實際密度值F_i,c與預估計密度值F_i,t的差值絕對值最大的樣本點所在的子簇；

S7、在S6得到的子簇中，隨機獲取若干個樣本點，并分別計算所述若干個樣本點的實際密度值F_i,c；

S8、判斷所述若干個個樣本點中是否存在實際密度值F_i,c大于預估計密度值F_i,t的樣本點；如果存在，則跳轉到S10；否則跳轉到S9；

S9、將實際密度值F_i,c與預估計密度值F_i,t差值絕對值最大的樣本點作為新的聚類中心，然后執行步驟S10；

S10、判斷聚類中心W_i是否不再改變，若滿足則跳轉到S11；否則迭代次數t更新為t+1，將新的聚類中心作為新的初始聚類中心，跳轉到S3；

S11、輸出聚類結果。

2.根據權利要求1所述一種基于樣本密度的全局優化K均值聚類方法，其特征在于，所述實際密度值F_i,c根據公式來計算，其中d_ij為W_i到第i個子簇中第j個樣本點n_ij的歐氏距離，S_i表示第i個子簇中樣本點的個數，j為第j個樣本點，c∈[1,c_max]，c_max為預設的最大偏移次數，r＝R×Ra；R為任一子簇中聚類中心離所在子簇中樣本點的最遠距離。