優(yōu)化K均值隨機(jī)初始中點(diǎn)的改進(jìn)算法.pdf

《優(yōu)化K均值隨機(jī)初始中點(diǎn)的改進(jìn)算法.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、化工自動(dòng)化及儀表第39卷優(yōu)化K均值隨機(jī)初始中點(diǎn)的改進(jìn)算法王秀芳1‘2王巖二f1．北京郵電大學(xué)信息與通信工程學(xué)院，北京】00876；2．東北石油大學(xué)電氣信息工程學(xué)院，黑龍江大慶163318)摘要針對傳統(tǒng)K均值隨機(jī)產(chǎn)生的初始聚類中心的方式提出最近鄰K均值、極遠(yuǎn)鄰K均值和自適應(yīng)K均值3種優(yōu)化算法。最近鄰K均值是通過尋找多維空問下歐氏伊鄰近點(diǎn)的方式確定K群；而極遠(yuǎn)鄰K均值是極遠(yuǎn)盯鄰判定確定法；自適應(yīng)K均值是將數(shù)據(jù)集確定到矩陣中，對矩陣做歸一化、二元化處理后，計(jì)算各向量間的相異度來修正確定初始中心點(diǎn)的加權(quán)歐氏距離。3種優(yōu)化算法改善了原始K均值

2、算法，提高了算法的穩(wěn)定性和精確度，而且它們各自適用于不同的應(yīng)用空間。關(guān)鍵詞最近鄰K均值扳遠(yuǎn)鄰K均值自適應(yīng)K均值歐氏距離初始聚類中心中圖分類號(hào)TH701文獻(xiàn)標(biāo)識(shí)碼A文章編號(hào)1000-3932(2012)10—1302-03由聚類生成的簇是一組數(shù)據(jù)對象的集合，在同類中的對象之間具有較高的相似度，異類間的對象差別較大。聚類分析是將物理或抽象對象的集合分組成為由類似的對象組成的多個(gè)類的過程，它是發(fā)現(xiàn)事物自然分類的一種方法，也是機(jī)器學(xué)習(xí)和模式識(shí)別的重要研究領(lǐng)域?。K—means聚類算法是處理大數(shù)據(jù)的經(jīng)典算法，當(dāng)簇群密集、簇間距明顯時(shí)，該算法效

3、果較好。其主要研究方向包括：計(jì)算量繁雜的大型數(shù)據(jù)集；集群初始化一個(gè)先驗(yàn)；局部極小搜索問題。然而傳統(tǒng)K—means算法隨機(jī)選擇初始聚類中心L2：，卻對初值的依賴性極強(qiáng)，初值選取得不同往往會(huì)導(dǎo)致聚類結(jié)果的不穩(wěn)定；其次，由于搜索方向的偏置會(huì)造成挖掘算法的迭代增加和算法效率很低，時(shí)間復(fù)雜度增加，因此采用合理的初始聚類中心，以此逐漸彌補(bǔ)K—raeans的缺陷顯得尤為重要i3。1K-means聚類算法K-means聚類分析算法的工作原理是先隨機(jī)從數(shù)據(jù)集中選取K點(diǎn)作為初始聚類中心H1，計(jì)算各樣本到聚類中心的距離，把樣本歸到離它最近的聚類中心類。該

4、算法采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)評價(jià)聚類性能"’6-。給定數(shù)據(jù)集x，確定x的初始聚類中點(diǎn)為{c，，c：，?，c；}，首次聚類完成后各類子集為{x。，x：，?，甄}，其中c?！蔢。(i=1，2，?，k)。各個(gè)聚類子集中的樣本數(shù)量分剮為挖．，玨：，?，n。；各個(gè)聚類子集的均值分別為；m-，，m：，?，m。}，與初始聚類中點(diǎn)jr；，c。，?。c；}比較，若兩次比較無變化，聚類中心不變；否則進(jìn)行下次迭代。誤差平方和準(zhǔn)則函數(shù)公式可表示^為：E=∑∑lip—c．釅。2IpE^．23種改進(jìn)的K初始聚類中心算法針對K．means隨機(jī)確定初

5、始K值的缺陷，在此總結(jié)了N2-K—means∞3、F2-K—means和SA—K—means改進(jìn)初始聚類中心的算法來改善原算法，減小時(shí)問復(fù)雜度，提高算法效率。2．1N2．K．meansN2．K．means(Nearest2．K．means)即最近鄰二點(diǎn)K初始值選取算法，目的是找到與數(shù)據(jù)集合在空間分布上相似程度較大的類集合。首先計(jì)算數(shù)據(jù)對象兩兩間的歐式距離，找出最近鄰的兩點(diǎn)，形成數(shù)據(jù)集合x；，并將它們從總集合u中刪除；計(jì)算x．中每個(gè)數(shù)據(jù)對象與集合u中各樣本的距離，找出在u中與x，最近鄰的數(shù)據(jù)對象，將其并入X。內(nèi)且從擴(kuò)中刪除，直至X。的

6、數(shù)據(jù)點(diǎn)達(dá)到閾值盯；再從U內(nèi)找到最近鄰兩點(diǎn)形成夏：，重復(fù)上面的搜索過程，直至形成K集合為止；最后對各對象集合分別進(jìn)行算術(shù)平均，形成K初始聚類中心。此時(shí)得到的K中心點(diǎn)更符合實(shí)際樣本的分布狀況，縮減了后期的迭代次數(shù)和計(jì)算量，提高運(yùn)行效率，從而達(dá)到更好的聚類效果，但該算法容易收稿日期：2012-05-31(修改稿)基金項(xiàng)目：黑龍江省教育廳科學(xué)技術(shù)重點(diǎn)項(xiàng)目(125lIz002)第10期秀艿等．優(yōu)化K均值隨機(jī)}JJ始t}J點(diǎn)的改進(jìn)斡：f2：l303忽略邊緣聚類群，因而易忽略潛信息量多n價(jià)值大的規(guī)則，，2．2F2．K．meansF2．K-mean

7、s(Farest2一K—means)即極遠(yuǎn)鄰二點(diǎn)K初始值選取算法，其目的亦是找到與數(shù)據(jù)集合在空問分布I二卡H似程度人的集合．汁算數(shù)據(jù)對象問的歐式距離后找出圾遠(yuǎn)鄰的J從j點(diǎn)v，、』：，形成各自集合x，、!，并將其從集合U內(nèi)刪除；汁鋒，Y。的數(shù)據(jù)對象x。與u內(nèi)各樣本的距離，找出最近鄰數(shù)據(jù)對象并將其并入工。內(nèi)，同時(shí)從集合f／中刪除．直至x．的數(shù)據(jù)點(diǎn)滿足閾值盯1．‘Y，做如x，的相同處理直至滿足or，為止，接著再從集合￡，內(nèi)找到最遠(yuǎn)鄰形成x。L，重復(fù)I：叫的搜索過穆，直至找到K數(shù)據(jù)集合為止；最后對各對象集合進(jìn)行算術(shù)平均，形成K初始聚類中心．

8、此時(shí)得到的K初始聚類點(diǎn)能明顯地區(qū)分各樣本點(diǎn)的分布狀況，同樣縮減了迭代次數(shù)和計(jì)算話．囊括了邊緣聚類群；但該算法把離異點(diǎn)計(jì)算在內(nèi)對規(guī)則形成r偏差，噪聲影響過大：2．3SA．K．meansSA—K．Ineans(Self-adaptiveK