發(fā)布時(shí)間：2020-08-08 18:48

【摘要】：K-means算法是一種經(jīng)典的聚類算法。該算法操作簡單,往往可以得到比較好的聚類效果。但是,該算法也存在一些不足:首先,聚類數(shù)K必須預(yù)先設(shè)定;其次,受初始聚類中心極影響大,如果選擇的初始聚類中心不夠分散,則不能很好的反映原始數(shù)據(jù)集的分布;最后,算法時(shí)間復(fù)雜度過高。為了減少K-means算法對(duì)初值的依賴性,提高算法的有效性,本文探討了K-means算法初始聚類中心的優(yōu)化選擇問題,主要研究內(nèi)容如下:1)在原始數(shù)據(jù)集上運(yùn)用均勻抽樣技術(shù)。在選擇每一個(gè)聚類中心之前,K-means算法都要對(duì)數(shù)據(jù)庫進(jìn)行一遍掃描,這樣會(huì)造成非常大的計(jì)算量,因此本文選擇首先對(duì)原始數(shù)據(jù)集進(jìn)行抽樣,這樣既起到對(duì)原始數(shù)據(jù)的預(yù)處理作用,而且能夠?qū)-means算法的優(yōu)越性發(fā)揮出來。2)在聚類的開始階段,傳統(tǒng)的UPGMA算法能夠很好地發(fā)現(xiàn)密集區(qū)域,但不易發(fā)現(xiàn)聚類形成的次序,導(dǎo)致選擇的初始聚類中心點(diǎn)不能代表實(shí)際數(shù)據(jù)集的分布狀況,因此設(shè)置了聚類條件和篩選條件,以保證初始聚類中心候選點(diǎn)將全部來自高密度區(qū)域,同時(shí)避免邊緣數(shù)據(jù)和噪聲數(shù)據(jù)。但是改進(jìn)的UPGMA算法也有缺點(diǎn),即在聚類條件和篩選條件的控制上,如果設(shè)置不當(dāng),則無法避免選擇的初始聚類中心點(diǎn)過于密集。如果在Canopy算法中加入最大最小距離算法,就能很好的彌補(bǔ)改進(jìn)UPGMA算法的不足之處,保證得到的初始聚類中心不會(huì)過于密集,從而能夠準(zhǔn)確地體現(xiàn)出實(shí)際數(shù)據(jù)集的分布情況。3)設(shè)計(jì)出CMU-kmeans算法(K-means Algorithm based on Canopy with Min-Max Algorithm and UPGMA Algorithm)。該算法既能夠自適應(yīng)地判斷出聚類數(shù)目k,又可以有效獲得優(yōu)化的初始聚類中心,因此在很大程度上保證了初值選擇的科學(xué)性。4)使用改進(jìn)的算法對(duì)地質(zhì)災(zāi)害監(jiān)測系統(tǒng)降雨量歷史數(shù)據(jù)集進(jìn)行聚類分析,通過實(shí)驗(yàn),有效驗(yàn)證了改進(jìn)算法有效性和適用性。
【學(xué)位授予單位】：西安工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：P694;TP311.13
【圖文】：

西安工業(yè)大學(xué)碩士學(xué)位論文 K-means 算法進(jìn)行之前的數(shù)據(jù)預(yù)處理階段。首先，對(duì)待研究的機(jī)抽樣，這樣可以保證獲得的數(shù)據(jù)集具有代表性，能夠充分反映而且綜合了 K-means 算法的各個(gè)優(yōu)點(diǎn)，從而獲得一組最佳的開始中心能夠很真實(shí)的反映真實(shí)數(shù)據(jù)。然而，該抽樣也有一些缺點(diǎn)：夠取得很大規(guī)模的數(shù)據(jù)集，且有比較高的正確率，但是容易產(chǎn)生其次，雖然該抽樣方法效率是比較高的，但是無法避免抽取的據(jù)分布之間存在偏差，從而得不到高的正確性�；诖�，對(duì)于抽進(jìn)行合適的把握。

3 一種改進(jìn)的 CMU-kmeans 算法如下圖 3.4 所示，CMU-kmeans 算法主要包括三個(gè)部心的優(yōu)化，該算法運(yùn)行于對(duì)原始數(shù)據(jù)集的抽取樣本些最佳的初始聚類種子及初始聚類個(gè)數(shù)，這些聚類種始數(shù)據(jù)集分布，這是 CMU-kmeans 算法最為核心的類算法對(duì)樣本數(shù)據(jù)對(duì)象集進(jìn)行聚類，這是本改進(jìn)算驗(yàn)以及對(duì)實(shí)驗(yàn)的評(píng)估，以驗(yàn)證本文提出的 CMU-km

圖 4.1 Glass 數(shù)據(jù)集中 m%取值對(duì)準(zhǔn)確率的影響中都包含不相關(guān)數(shù)據(jù)和孤立點(diǎn)數(shù)據(jù)，只是這些數(shù)據(jù)一般比據(jù)分布的子樹數(shù)出現(xiàn)的可能性不大，所以將 p 設(shè)置為 90常量，本次實(shí)驗(yàn)用 0.5 來取值。價(jià)標(biāo)準(zhǔn)-means算法、改進(jìn)的Canopy算法和本論文中提出的CM行評(píng)價(jià)的標(biāo)準(zhǔn)有很多，這里選擇平均召回率（recall）兩個(gè)標(biāo)準(zhǔn)的定義分別如式 4.1 和 4.2 所示。P（i, j）= precision(i, j) = Ni,j/ NiR（i, j）= recall(i, j) = Ni,j/ Nj類 i中包含的樣本數(shù)據(jù)個(gè)數(shù)；Ni,j代表類別 j 中的分類 i象的個(gè)數(shù)。

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 孟海東;任敬佩;;基于云計(jì)算平臺(tái)的聚類算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2015年11期

2 武霞;董增壽;孟曉燕;;基于大數(shù)據(jù)平臺(tái)hadoop的聚類算法K值優(yōu)化研究[J];太原科技大學(xué)學(xué)報(bào);2015年02期

3 譚躍生;楊寶光;王靜宇;張亞楠;;Hadoop云平臺(tái)下的聚類算法研究[J];計(jì)算機(jī)工程與設(shè)計(jì);2014年05期

4 趙慶;;基于Hadoop平臺(tái)下的Canopy-Kmeans高效算法[J];電子科技;2014年02期

5 周麗娟;王慧;王文伯;張寧;;面向海量數(shù)據(jù)的并行KMeans算法[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年S1期

6 毛典輝;;基于MapReduce的Canopy-Kmeans改進(jìn)算法[J];計(jì)算機(jī)工程與應(yīng)用;2012年27期

7 牛瑞卿;韓舸;;利用數(shù)據(jù)挖掘的滑坡監(jiān)測數(shù)據(jù)處理流程[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2012年07期

8 趙衛(wèi)中;馬慧芳;傅燕翔;史忠植;;基于云計(jì)算平臺(tái)Hadoop的并行k-means聚類算法設(shè)計(jì)研究[J];計(jì)算機(jī)科學(xué);2011年10期

9 劉文軍;游興中;;一種改進(jìn)的凝聚層次聚類法[J];吉首大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年04期

10 孫雪;李昆侖;胡夕坤;趙瑞;;基于半監(jiān)督K-means的K值全局尋優(yōu)算法[J];北京交通大學(xué)學(xué)報(bào);2009年06期

相關(guān)碩士學(xué)位論文 前1條

1 張鑫;層次聚類算法的研究與應(yīng)用[D];江西理工大學(xué);2009年

本文編號(hào)：2785967