[發(fā)明專利]空間密度相似性度量K?means聚類方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710022745.1
• 申請(qǐng)日: 2017-01-12
• 公開(kāi)（公告）號(hào): CN106778909A
• 公開(kāi)（公告）日: 2017-05-31
• 發(fā)明（設(shè)計(jì)）人: 薛衛(wèi);楊榮麗;趙南;徐煥良;任守綱
• 申請(qǐng)（專利權(quán)）人: 南京農(nóng)業(yè)大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 南京天華專利代理有限責(zé)任公司32218
• 代理人: 劉暢,徐冬濤

技術(shù)領(lǐng)域

本發(fā)明涉及機(jī)器學(xué)習(xí)領(lǐng)域，尤其是使用聚類分析方法將任意形狀分布的復(fù)雜數(shù)據(jù)集分成特定類別的一種有效的聚類方法，具體是一種空間密度相似性度量K-means聚類方法。

背景技術(shù)

在傳統(tǒng)及改進(jìn)K-means方法中通常采用歐氏距離直接表達(dá)樣本間的相似性距離，但歐氏距離往往不能較為準(zhǔn)確地表達(dá)各種流形數(shù)據(jù)點(diǎn)間的相似性，本發(fā)明提出的是通過(guò)采用空間密度的相似性距離彌補(bǔ)這一缺陷，并加上新的K-means方法類中心的迭代模型，能反映各種數(shù)據(jù)集的真實(shí)分布規(guī)律，得到準(zhǔn)確穩(wěn)定的聚類效果。

K-means方法是應(yīng)用最廣泛的聚類方法之一，傳統(tǒng)的K-means方法存在初始聚類中心不穩(wěn)定，聚類效果和迭代次數(shù)對(duì)初始聚類中心過(guò)于依賴，易陷入局部最優(yōu)等問(wèn)題。為改善以上缺陷，國(guó)內(nèi)外學(xué)者從不同角度對(duì)K-means方法提出了一系列的優(yōu)化方法。如Huang等提出一種基于自動(dòng)計(jì)算權(quán)值的K-means方法，改進(jìn)聚類中變量的選擇問(wèn)題。Dhillon等為提高方法性能調(diào)整K-means迭代過(guò)程中計(jì)算聚類中心的方法。Redmond等將k-d樹(shù)和Katsavounidis提出的方法相結(jié)合，在基于密度選擇初始聚類中心時(shí)能盡可能分散選擇，使初始聚類中心的選擇更加合理化。Sarafis將遺傳方法應(yīng)用在K-means的目標(biāo)函數(shù)構(gòu)建中，并在此基礎(chǔ)上提出新的聚類方法RBCGA，取得較好效果。

在傳統(tǒng)和改進(jìn)K-means方法中，通常采用歐氏距離計(jì)算在m維空間中兩個(gè)樣本之間的距離。然而，在任意形狀分布的復(fù)雜數(shù)據(jù)集上，K-means方法通過(guò)歐式距離來(lái)衡量樣本間的相似性距離，往往達(dá)不到預(yù)期效果。如圖1中，樣本集中分布的A、B、C三點(diǎn)，歐式距離計(jì)算可得A點(diǎn)和C點(diǎn)的距離大于A點(diǎn)和B點(diǎn)的距離，而實(shí)際期望是通過(guò)某種距離計(jì)算得到，A點(diǎn)和C點(diǎn)的距離小于A點(diǎn)和B點(diǎn)的距離。

同時(shí)在迭代過(guò)程中，K-means新一輪聚類中心的產(chǎn)生規(guī)則取所有本簇樣本中每一維的平均值。而在像圖1中類似的非簇型數(shù)據(jù)集中使用平均值選擇聚類中心時(shí)，聚類中心極有可能出現(xiàn)在本簇區(qū)域以外，甚至存在和另一簇中心相重合的情況。

發(fā)明內(nèi)容

針對(duì)背景技術(shù)中存在的兩個(gè)顯著問(wèn)題，本發(fā)明改進(jìn)單一的歐氏距離測(cè)量方法和K-means的迭代規(guī)則，設(shè)計(jì)出更加有效合理的距離測(cè)量方法和迭代規(guī)則，使分類效果明顯改善。

本發(fā)明公開(kāi)了一種空間密度相似性度量K-means聚類方法，該方法包括以下步驟：

(1)對(duì)數(shù)據(jù)集樣本D進(jìn)行歸一化的數(shù)據(jù)預(yù)處理；

(2)初始化聚類中心：

1)根據(jù)樣本間的空間密度的相似性距離得出樣本空間Space和每一個(gè)樣本的密集度Density(x_i)；

2)選擇最大密集度樣本作為初始聚類中心的第一個(gè)聚類中心；

3)選擇其次大的密集度樣本，并且此樣本與之前選擇的聚類中心的距離大于一定的值，該值記為控制迭代值distrol，添加此樣本進(jìn)入初始聚類中心；

4)循環(huán)執(zhí)行3)，直至選擇出K個(gè)初始聚類中心C⁰；

步驟3)中所述之前是指：在初次循環(huán)時(shí)，為步驟2)中第一個(gè)聚類中心；在后續(xù)循環(huán)執(zhí)行時(shí)，為前面循環(huán)中選擇的所有初始聚類中心；

(3)在第t次循環(huán)中，根據(jù)聚類中心C^t-1和數(shù)據(jù)集樣本D的空間密度的相似性距離重新劃分類得到D^t；

(4)通過(guò)類中心迭代模型計(jì)算得到新一輪的聚類中心C^t，

(5)循環(huán)執(zhí)行(3)和(4)，直至滿足目標(biāo)函數(shù)E的值達(dá)到最優(yōu)即不再變化時(shí)結(jié)束，

x_j表示第j個(gè)樣本，c_i表示第i個(gè)聚類中心，DistF(x_j,c_i)表示二者空間密度的相似性距離。

優(yōu)選的，步驟(2)中計(jì)算的Space和Density(x_i)具體包括以下步驟：

(A).首先計(jì)算數(shù)據(jù)集樣本D中任意兩個(gè)樣本距離的伸縮系數(shù)A為：