K-means聚類算法的研究綜述-論文.pdf

《K-means聚類算法的研究綜述-論文.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、研究與開發(fā)文章編號(hào)：1007—1423(2014)23—0031～03DOI：10．3969~．issn．1007-1423．2014．23．007K—means聚類算法的研究綜述李衛(wèi)軍(北方民族大學(xué)網(wǎng)絡(luò)信息技術(shù)中心，銀川750021)摘要：K一均值聚類算法(K—means)是基于劃分的聚類算法中的典型算法，針對(duì)K—means算法初始聚類中心存在對(duì)K依賴的缺陷，提出一種新的選取K—means算法初始聚類中心的方法，該方法提高聚類結(jié)果的有效性和穩(wěn)定性；還提出一種極值選擇法，將最大距離法和最小距離法相結(jié)合，進(jìn)一步提高初始聚類中心選擇的準(zhǔn)確性。關(guān)鍵詞：K均值；聚類分析：初始聚類中心基金項(xiàng)目：北方

2、民族大學(xué)自然科學(xué)基金(No．2013XYZ028)、寧夏高等學(xué)校科學(xué)技術(shù)研究項(xiàng)目(No．NGY2012336105)0引言不再變化為止，即上：∑∑Ilxk-miIIz收斂。本算法的基聚類分析是在無(wú)監(jiān)督的情況下．將對(duì)象集自動(dòng)分=Ik=l本流程如下：組的一種分析方法．是數(shù)據(jù)挖掘的一個(gè)重要研究領(lǐng)域。輸入：簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)集。聚類分析的核心是聚類．目的是將對(duì)象組織成一個(gè)個(gè)輸出：滿足目標(biāo)的k個(gè)簇集合。的簇．使得同一簇內(nèi)的對(duì)象相似．不同簇間的對(duì)象差異①?gòu)臄?shù)據(jù)集中任意選擇k個(gè)對(duì)象作為初始的簇類很大。聚類算法有K—means、STING、CLIQUE等，文獻(xiàn)中心；『11對(duì)各種聚類算法進(jìn)行了詳

3、細(xì)的介紹②循環(huán)③到⑤，根據(jù)簇中對(duì)象的平均值，將每個(gè)對(duì)K—means算法是一種經(jīng)典的劃分聚類算法．是到象賦予最類似的簇。直到目標(biāo)函數(shù)E不再發(fā)生變化為目前為止應(yīng)用最廣泛最成熟的一種聚類分析方法K—止means算法屬于基于距離的聚類算法．具有算法簡(jiǎn)單快速、適于處理大數(shù)據(jù)集等優(yōu)點(diǎn)．目前已被廣泛應(yīng)用于科③計(jì)算更新簇的均值或者中心點(diǎn)，即∑，lGl；E￡學(xué)研究和工業(yè)應(yīng)用中k1K—means算法的介紹④計(jì)算每個(gè)對(duì)象E=∑∑Ixl：；i=1EGK—means算法屬于一種動(dòng)態(tài)聚類算法．又稱逐步⑤直至E不再明顯地變化。聚類法，目的是將n個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)簇類．每個(gè)2K—means算法分析類的對(duì)象具有高度的相似

4、性首先隨機(jī)選取k個(gè)對(duì)象作為簇的均值點(diǎn)或中心點(diǎn)．然后計(jì)算每個(gè)對(duì)象與k個(gè)K～means算法是一種基于劃分的聚類算法．目的是通過(guò)不斷的迭代計(jì)算找出使得平方誤差值最小的K簇類均值或者中心點(diǎn)的距離．并將其指派到離它最近的簇類均值或者聚類中心所在的簇中．然后更新簇的個(gè)劃分。K—means算法的主要優(yōu)點(diǎn)：運(yùn)算簡(jiǎn)單、速度快；均值或者中心點(diǎn)．如此循環(huán)往復(fù)．直至均值或者中心點(diǎn)對(duì)于大數(shù)據(jù)集效率高、可伸縮性強(qiáng)：時(shí)間復(fù)雜度接近線現(xiàn)代計(jì)算機(jī)2014．08中0性。雖然K—means算法有如上所述的諸多優(yōu)點(diǎn)．但也存現(xiàn)的。在一些不足，在應(yīng)用中面臨著許多問(wèn)題．有待解決K—針對(duì)K—means算法隨機(jī)選擇初始聚類中心的不mean

5、S算法主要有以下不足：足．一些研究人員提出了不同的改進(jìn)方法．其中孫雪等①算法需要首先指定聚類的個(gè)數(shù)k人提出了基于半監(jiān)督K一均值聚類對(duì)K值進(jìn)行全局尋②算法對(duì)初始值k的選取依賴性較大。若初始值優(yōu)算法[31．利用少量標(biāo)記數(shù)據(jù)指導(dǎo)和規(guī)劃大量無(wú)監(jiān)督數(shù)選擇不當(dāng)算法常常陷入局部極小解：若隨機(jī)選擇初始據(jù)張健沛等人提出了基于最優(yōu)劃分的K—means算法中心點(diǎn)易導(dǎo)致聚類結(jié)果不穩(wěn)定初始聚類中心選取算法．該算法利用直方圖對(duì)數(shù)據(jù)樣③K—means算法對(duì)孤立點(diǎn)數(shù)據(jù)和噪聲數(shù)據(jù)較敏本進(jìn)行最優(yōu)劃分：若K—means算法初始值選取不當(dāng)易感。造成局部最優(yōu)解的問(wèn)題，吳曉蓉、楊勝等人在文獻(xiàn)『51中④對(duì)于大數(shù)據(jù)量，算法的開銷較大。提

6、出了一種基于霍夫曼樹的改進(jìn)算法：孫士寶等人分析研究孤立點(diǎn)和噪聲數(shù)據(jù)對(duì)K—means算法影響的基礎(chǔ)3K—means算法初始簇類中心的選取與上提出了一種基于加權(quán)的K—means算法同優(yōu)化基于以上的分析研究．本文提出了對(duì)改進(jìn)算法用K—means算法的主要思想為：首先選出k個(gè)點(diǎn)作于初始中心點(diǎn)選取利用基于密度的劃分聚類算法對(duì)為簇類的均值或聚類中心．然后進(jìn)行迭代運(yùn)算更新均初始中心進(jìn)行選擇：首先該選取密度最大的一數(shù)據(jù)點(diǎn)值或簇類中心．直至準(zhǔn)則函數(shù)收斂。因此．聚類中心的作為第一個(gè)初始聚類中心P，依此計(jì)算其他數(shù)據(jù)點(diǎn)到不同選擇會(huì)導(dǎo)致不同的聚類效果．換句話也就是K—P1的距離。選取距離最大的點(diǎn)最為第二個(gè)初始聚類中

7、means算法依賴初值的選擇．初值選擇不當(dāng)可能陷入局P'，依此類推直到得到初始的k個(gè)聚類中心，該算法能部最優(yōu)解。文獻(xiàn)『21中已經(jīng)給出了一些改進(jìn)算法：將任意夠很好地提高K—means算法的準(zhǔn)確率．有效地避免陷的A個(gè)樣本看成初始聚類中心：將全部的數(shù)據(jù)分成k入局部最小值類．計(jì)算各個(gè)均值作為初始聚類中心：利用“密度法”選4結(jié)語(yǔ)擇初始中心：由k一1類聚類問(wèn)題求解k類的聚類中心問(wèn)題的。本文主要分析了K—means算法思想和算法的流聚