一種基于模糊數(shù)學(xué)思想的K均值算法

張昌明

摘要：隨著云計算、移動計算等互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，海量數(shù)據(jù)分析已成為企業(yè)戰(zhàn)略決策、營銷推廣的基礎(chǔ)，海量數(shù)據(jù)挖掘愈顯重要。傳統(tǒng)的K均值算法作為一種硬聚類算法存在諸多問題，例如數(shù)據(jù)劃分武斷、準(zhǔn)確率較低等。引入模糊數(shù)學(xué)思想，提出了一種模糊K均值算法，基于隸屬度關(guān)系對數(shù)據(jù)進(jìn)行了有效的聚類分析，以提高數(shù)據(jù)挖掘的準(zhǔn)確度。

關(guān)鍵詞：模糊數(shù)學(xué)；K均值；硬聚類；隸屬度

DOIDOI：10.11907/rjdk.161041

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2016）005-0041-03

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，多媒體圖像、Web文檔、影像視頻等海量數(shù)據(jù)大量涌現(xiàn)，在豐富人們生活的同時，也給檢索帶來了巨大的工作量。采用自動化、智能化、模式化的聚類分析方法，已經(jīng)成為海量數(shù)據(jù)應(yīng)用研究的熱點(diǎn)。K均值作為一種聚類算法，其思想和應(yīng)用執(zhí)行過程較為方便，一直以來受到互聯(lián)網(wǎng)企業(yè)青睞，在入侵檢測、圖像處理、視頻聚類、文本數(shù)據(jù)挖掘、電子商務(wù)推薦、遙感信息識別、軟件聚類等領(lǐng)域得到了廣泛應(yīng)用，取得了較好的效果[1-3]。隨著對K均值算法研究的深入，算法得到了極大的改進(jìn)。

王敞等[4]分析了K均值聚類算法存在中心設(shè)置容易陷入局部最優(yōu)化等問題，提出了一種基于遺傳算法的K均值聚類算法，能夠有效結(jié)合遺傳算法尋找全局最優(yōu)。在自適應(yīng)交叉和變異操作中引入K均值操作，克服了傳統(tǒng)K均值算法的局部性和敏感性，能夠?qū)崿F(xiàn)較好的聚類效果。陳宗海等[5]分析了聚類算法強(qiáng)化學(xué)習(xí)過程中，連續(xù)狀態(tài)空間對自適應(yīng)劃分方法存在的缺點(diǎn)，提出了一種基于節(jié)點(diǎn)生長的K均值聚類算法，分別給出了離散動作和連續(xù)動作下強(qiáng)化學(xué)習(xí)方法的執(zhí)行步驟，實(shí)驗(yàn)結(jié)果顯示，該方法可以自動調(diào)整劃分的精確度、優(yōu)化學(xué)習(xí)最佳策略。高瀅等[6]提出了一種半監(jiān)督K均值多關(guān)系數(shù)據(jù)聚類算法，該算法在K均值算法的基礎(chǔ)上，改進(jìn)了類簇的選擇方法和數(shù)據(jù)對象之間的相似性度量方法，將其應(yīng)用于多關(guān)系的半監(jiān)督學(xué)習(xí)過程中，充分利用標(biāo)記數(shù)據(jù)、對象屬性，提高了K均值算法的準(zhǔn)確度。陶新民等[7]詳細(xì)地分析了K均值算法存在的缺點(diǎn)，提出了一種改進(jìn)的粒子群優(yōu)化的K均值混合聚類算法。該算法引入小概率隨機(jī)變異操作，以便能夠增強(qiáng)種群的多樣性，提高混合聚類算法的全局搜索能力；根據(jù)群體適應(yīng)度方差確定K均值算法操作的時機(jī)，增強(qiáng)局部精確搜索能力，縮短算法的收斂時間。王莉等[8]分析了粗k均值聚類算法易受隨機(jī)初始聚類中心和離群點(diǎn)的影響，導(dǎo)致出現(xiàn)一致性和無法收斂的問題，提出了一種改進(jìn)的粗K均值聚類算法。該算法能夠選擇潛能最大的K個對象作為聚類中心，基于其它數(shù)據(jù)對象和中心之間的距離判定數(shù)據(jù)歸屬類簇，提高了算法準(zhǔn)確度，克服了離群點(diǎn)的不利影響。胡偉等[9]分析了K均值算法隨機(jī)指定不同的聚類個數(shù)而導(dǎo)致聚類錯誤率較高的問題，集合層次劃分算法，提出了一種改進(jìn)的層次K均值聚類算法，能夠自底向上聚類分析，形成一棵樹型結(jié)構(gòu)，并且在樹形結(jié)構(gòu)上自動選擇聚類。實(shí)驗(yàn)結(jié)果表明，該聚類提高了數(shù)據(jù)分析的準(zhǔn)確度。趙冬玲等[10]整合網(wǎng)格聚類和K均值聚類算法優(yōu)勢，提出一種基于網(wǎng)格的K均值聚類算法，改進(jìn)了算法中計算密度閾值的函數(shù)，可以有效降低算法的低凝聚度，提高數(shù)據(jù)聚類分析效率。

傳統(tǒng)聚類算法對初始化的聚類中心比較敏感，并且隨著初始化聚類中心的不同，具有不同的聚類結(jié)果，因此需要根據(jù)經(jīng)驗(yàn)設(shè)置聚類中心，很容易陷入局部最優(yōu)化。另外，傳統(tǒng)的K均值算法屬于硬劃分，每個對象都?xì)w屬于一個具體的類簇，降低了算法的準(zhǔn)確度。為了解決上述問題，本文引入模糊聚類思想，提出一種模糊K均值聚類算法。實(shí)驗(yàn)結(jié)果表明，該算法能夠有效提高聚類的準(zhǔn)確度。

1 背景理論

在聚類算法執(zhí)行過程中，可以對公式（9）和公式（10）進(jìn)行迭代執(zhí)行，得到一個具體的模糊K均值聚類算法，在實(shí)際的數(shù)據(jù)集劃分過程中使用。

本文基于模糊思想的K均值聚類算法描述如下：算法輸入：簇數(shù)目K，參數(shù)b，包含N個數(shù)據(jù)對象的數(shù)據(jù)集。

算法輸出：K個簇。

算法步驟：①采用隨機(jī)初始法為數(shù)據(jù)集設(shè)定K個簇，并指定每個簇的中心為mi；②計算數(shù)據(jù)集中每個數(shù)據(jù)對象的隸屬函數(shù)，計算方法為公式（10）；③基于步驟②的隸屬度函數(shù)，計算各個簇的中心值mi，計算簇中心采用公式（9）；④遍歷數(shù)據(jù)集中每個數(shù)據(jù)對象，當(dāng)隸屬度不再發(fā)生變化時，算法終止；否則返回步驟②。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

系統(tǒng)實(shí)驗(yàn)工具為Matlab2012程序處理平臺，實(shí)驗(yàn)環(huán)境采用的服務(wù)器為一臺酷睿雙核PC，CPU型號為i3-2310M，其主頻為2.10GHz，內(nèi)存為4G，操作系統(tǒng)為Win7。

算法實(shí)驗(yàn)數(shù)據(jù)采用Lang收集的20-NG數(shù)據(jù)集，使用BoW工具對數(shù)據(jù)集進(jìn)行預(yù)處理，從中選擇4 500篇文檔，將這些文檔分成9個子數(shù)據(jù)集，每個數(shù)據(jù)集包含的文章數(shù)量為500篇，具體如下：數(shù)據(jù)集Binary_1、Binary_2、Binary_3分別包含2個檔類別，分別是talk.politics.mideast和talk.politics.misc，每個類別包含250篇文檔；數(shù)據(jù)集Multi5_1、Multi5_2、Multi5_3分別包含5個文檔類別，分別是comp.graphics、rec.motorcycle、rec.sport.baseball、sci.space和talk.politics.mideast，每個類別包含100篇文檔；數(shù)據(jù)集Multi10_1、Multi10_2、Multi10_3分別包含10個文檔類別，分別是sci.electronics、comp.sys.mac.hardware、rec.sport.hockey、misc.forsale、alt.atheism、talk.politics.guns、rec.autos、sci.crypt、sci.med和sci.space，每個類別包含50篇文檔。

4 結(jié)語

傳統(tǒng)K均值算法屬于硬劃分，并且算法的初始中心節(jié)點(diǎn)需要人為指定，容易降低算法的執(zhí)行效率及準(zhǔn)確度。本文基于模糊聚類思想提出了一種新的K均值聚類算法，將每個數(shù)據(jù)對象按照隸屬度劃分到真實(shí)的類別中，提升了算法的準(zhǔn)確度。未來工作的方向主要是：①改進(jìn)模糊聚類隸屬度函數(shù)，以便能更有效地提高算法準(zhǔn)確度；②基于遺傳算法、粒子群算法、模擬退火算法等，改進(jìn)K均值初始中心的設(shè)置，提高初始設(shè)置的準(zhǔn)確度，進(jìn)一步改進(jìn)算法劃分效果。

參考文獻(xiàn)：

[1]胡艷維， 秦拯， 張忠志. 基于模擬退火與K均值聚類的入侵檢測算法[J]. 計算機(jī)科學(xué)， 2010， 37（6）：122-124.

[2]吳永芳， 楊鑫， 徐敏，等. 基于K均值聚類的醫(yī)學(xué)圖像分割算法[J]. 計算機(jī)工程， 2011， 37（5）：232-234.

[3]楊宏宇， 常媛. 基于K均值多重主成分分析的App-DDoS檢測方法[J]. 通信學(xué)報， 2014， 35（5）：16-23.

[4]王敞， 陳增強(qiáng)， 袁著祉. 基于遺傳算法的K均值聚類分析[J]. 計算機(jī)科學(xué)， 2003， 30（2）：163-164.

[5]陳宗海， 文鋒， 聶建斌，等. 基于節(jié)點(diǎn)生長k-均值聚類算法的強(qiáng)化學(xué)習(xí)方法[J]. 計算機(jī)研究與發(fā)展， 2006 （4）：661-666.

[6]高瀅， 劉大有， 齊紅，等. 一種半監(jiān)督K均值多關(guān)系數(shù)據(jù)聚類算法[J]. 軟件學(xué)報， 2008，19 （11）：2814-2819.

[7]陶新民， 徐晶， 楊立標(biāo)，等. 一種改進(jìn)的粒子群和K均值混合聚類算法[J]. 電子與信息學(xué)報， 2010， 32（1）：92-97.

[8]王莉， 周獻(xiàn)中， 沈捷. 一種改進(jìn)的粗K均值聚類算法[J]. 控制與決策， 2012，27 （11）：1711-1714.

[9]胡偉. 改進(jìn)的層次K均值聚類算法[J]. 計算機(jī)工程與應(yīng)用， 2013，49 （2）：157-159.

[10]趙冬玲， 馮艷若， 潘正運(yùn). 基于網(wǎng)格的K-均值聚類分析算法研究[J]. 科技通報， 2014， 30（7）：175-179.

（責(zé)任編輯：杜能鋼）