一種基于模糊數學思想的K均值算法

張昌明

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

關鍵詞：模糊數學；K均值；硬聚類；隸屬度

DOIDOI：10.11907/rjdk.161041

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2016）005-0041-03

0 引言

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

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

傳統聚類算法對初始化的聚類中心比較敏感，并且隨著初始化聚類中心的不同，具有不同的聚類結果，因此需要根據經驗設置聚類中心，很容易陷入局部最優化。另外，傳統的K均值算法屬于硬劃分，每個對象都歸屬于一個具體的類簇，降低了算法的準確度。為了解決上述問題，本文引入模糊聚類思想，提出一種模糊K均值聚類算法。實驗結果表明，該算法能夠有效提高聚類的準確度。

1 背景理論

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

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

算法輸出：K個簇。

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

3 實驗與結果分析

3.1 實驗數據與環境

系統實驗工具為Matlab2012程序處理平臺，實驗環境采用的服務器為一臺酷睿雙核PC，CPU型號為i3-2310M，其主頻為2.10GHz，內存為4G，操作系統為Win7。

算法實驗數據采用Lang收集的20-NG數據集，使用BoW工具對數據集進行預處理，從中選擇4 500篇文檔，將這些文檔分成9個子數據集，每個數據集包含的文章數量為500篇，具體如下：數據集Binary_1、Binary_2、Binary_3分別包含2個檔類別，分別是talk.politics.mideast和talk.politics.misc，每個類別包含250篇文檔；數據集Multi5_1、Multi5_2、Multi5_3分別包含5個文檔類別，分別是comp.graphics、rec.motorcycle、rec.sport.baseball、sci.space和talk.politics.mideast，每個類別包含100篇文檔；數據集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 結語

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

參考文獻：

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

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

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

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

[5]陳宗海， 文鋒， 聶建斌，等. 基于節點生長k-均值聚類算法的強化學習方法[J]. 計算機研究與發展， 2006 （4）：661-666.

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

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

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

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

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

（責任編輯：杜能鋼）