[發(fā)明專利]一種基于樣本密度的全局優(yōu)化K均值聚類方法及系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 201810525709.1
• 申請(qǐng)日: 2018-05-28
• 公開（公告）號(hào): CN108985318A
• 公開（公告）日: 2018-12-11
• 發(fā)明（設(shè)計(jì)）人: 許鴻文;薛印璽;陳雯;李羚;殷蔚明;謝靖
• 申請(qǐng)（專利權(quán)）人: 中國地質(zhì)大學(xué)（武漢）
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 武漢知產(chǎn)時(shí)代知識(shí)產(chǎn)權(quán)代理有限公司 42238
• 代理人: 郝明琴

1.一種基于樣本密度的全局優(yōu)化K均值聚類方法，其特征在于，包含以下步驟：

S1、獲取包含N個(gè)樣本點(diǎn)的原始數(shù)據(jù)集X、子簇個(gè)數(shù)K及比例參數(shù)Ra，其中N大于1；

S2、在所述原始數(shù)據(jù)集X中隨機(jī)選取K個(gè)樣本點(diǎn)作為初始聚類中心，記為w_i,其中i＝1,2,3,…,K；

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

S4、分別將所有子簇的質(zhì)心記為W_i，根據(jù)公式計(jì)算W_i的預(yù)估計(jì)密度值F_i,t，并計(jì)算W_i實(shí)際密度值F_i,c；

其中m為所述迭代次數(shù)的最大迭代次數(shù)且為預(yù)設(shè)值，t表示當(dāng)前的迭代次數(shù)，2(3φσ×Ra)的值根據(jù)標(biāo)準(zhǔn)正態(tài)分布函數(shù)查表得出；

S5、將每個(gè)子簇的質(zhì)心W_i作為新的聚類中心，分別判斷每個(gè)新的聚類中心所在的子簇中是否存在實(shí)際密度值F_i,c小于預(yù)估計(jì)密度值F_i,t的樣本點(diǎn)，如果不存在，跳轉(zhuǎn)到S10；如果存在，跳轉(zhuǎn)到S6；

S6、獲取實(shí)際密度值F_i,c與預(yù)估計(jì)密度值F_i,t的差值絕對(duì)值最大的樣本點(diǎn)所在的子簇；

S7、在S6得到的子簇中，隨機(jī)獲取若干個(gè)樣本點(diǎn)，并分別計(jì)算所述若干個(gè)樣本點(diǎn)的實(shí)際密度值F_i,c；

S8、判斷所述若干個(gè)個(gè)樣本點(diǎn)中是否存在實(shí)際密度值F_i,c大于預(yù)估計(jì)密度值F_i,t的樣本點(diǎn)；如果存在，則跳轉(zhuǎn)到S10；否則跳轉(zhuǎn)到S9；

S9、將實(shí)際密度值F_i,c與預(yù)估計(jì)密度值F_i,t差值絕對(duì)值最大的樣本點(diǎn)作為新的聚類中心，然后執(zhí)行步驟S10；

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

S11、輸出聚類結(jié)果。

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