基于文化算法的K均值聚類混合算法研究

賈麗麗

聚類分析廣泛應用于數(shù)據(jù)挖掘領域，許多專家學者已經提出了大量經典的和流行的聚類算法。傳統(tǒng)聚類分析大致分五類，其中，基于劃分聚類算法是算法研究中的一個熱門的研究領域之一。而K均值法又是劃分聚類分析算法中最經典的一類方案，能夠歸屬到爬山法的范疇。該類算法具備的優(yōu)勢為原理實現(xiàn)簡便，操作運行高效。只是該類算法也不可回避地存在極大的缺陷：第一，對于選定的初始值極其敏感。當其選用的初始值存在變化的時候，所得到的聚類結果也將呈現(xiàn)很大的差別；第二，局部極值的缺陷。該項算法是順延能量遞減的方向完成搜索操作，因此很容易深陷局部極值而難以獲得最優(yōu)解。

本文基于文化算法所具有的雙層結構特性提出文化-K均值混合算法，該算法是把文化算法中知識空間（信仰空間）比較優(yōu)的信息保留下，使其可以依靠保留優(yōu)等經驗的方式幫助更好地實現(xiàn)問題處理，實現(xiàn)全局尋優(yōu)的功能目標，避免了對初始值選取敏感的問題，能有效地克服傳統(tǒng)的K均值算法的兩大缺點。因此，通過對文化算法的K均值聚類混合算法進行深入研究，呈現(xiàn)出良好的理論分析意義。

1 文化算法框架

通常，文化算法能夠實現(xiàn)最新復雜度相對較高的全局尋優(yōu)處理，其是一種基于知識的雙層演化系統(tǒng)，包含兩個演化空間：一層是通過群體之間的演化及其評價迭代搜索最優(yōu)解，該空間由具體個體組成的群體空間（種群空間）；另一層是在群體演化過程中經驗知識組成的知識空間（信仰空間）。圖1闡述了文化算法的基本框架[1]。

在圖1 中，accept() 表征的是接受函數(shù)，influence()表征的是影響函數(shù)。在雙層空間性質的通信協(xié)議構建期間，接受函數(shù)能夠完成群體內選定個體相應經驗知識的搜集整理，并且經由更新函數(shù)update()的支持實現(xiàn)信仰空間的調整處理；此時，影響函數(shù)能夠依靠信仰空間內存在的各類知識經驗，積極指引群體空間優(yōu)化升級。

圖1 文化算法基本框架

2 基于文化算法的K 均值聚類混合算法研究

2.1 K 均值聚類法

該聚類方法是實現(xiàn)聚類分析期間最經典的一種方法，具有原理簡單、算法高效的優(yōu)點。下面給出具體算法流程[2]：

Step2 隨機選取K 個樣本作為聚類中心并初始化；

Step3 計算各樣本與各類中心的距離（采用歐式距離）；

Step4 把各樣本趨近到類中心點，運算獲得各自的均值，充當最新的類中心；

Step5 判定：當類中心不呈現(xiàn)改變或是滿足迭代次數(shù)，算法停止；反之，繼續(xù)執(zhí)行3。

2.2 基于文化算法的K 均值聚類混合算法

K均值聚類算法的兩個缺點：一個是可能會導致不同的聚類結果，主要是由于初始值選取的敏感性；另一個是該算法很容易陷入局部優(yōu)化，主要原因是該算法是沿著能量減少的方向搜索。這兩個缺點，限制了該算法的范圍。為了克服K均值聚類算法初始化敏感性和容易陷入局部優(yōu)化兩大缺點，引入文化算法加以改進，以文化算法為框架，K均值算法為聚類模型的混合聚類算法，針對聚類問題建立文化算法的雙層空間進化模型，構建適合于聚類問題的信仰空間、種群空間、接受函數(shù)和影響函數(shù)，并運用各種知識加以指導，讓問題可以在經驗知識的指引下更好地實施求解分析，進而獲得全局最優(yōu)效果，在聚類中起到了良好的指導作用，從而具有較好的全局尋優(yōu)性能，能夠有效地克服K均值算法的兩大缺點。適用于求解海量數(shù)據(jù)分析中的聚類問題。

2.2.1 文化-K 均值聚類混合算法框架

圖2 文化-K均值聚類混合算法框架

2.2.2 種群空間（群體空間）的編碼與適應度函數(shù)

在種群空間內，個體編碼選定聚類中心內的實值編碼充當，個體則選定K個聚類中心組建得到。如果d是模式向量維數(shù)，那么個體長度對應就是K×d實值碼串。由文化算法是面向最小化問題，因此適應度函數(shù)采用類間誤差平方和最小，即達到最小，d ij表示樣本歐式距離。

2.2.3 信仰空間（知識空間）結構

信仰空間的結構采用文獻[3]中的 〈S,N〉結構，即對應即為形勢知識，屬于最優(yōu)個體構成的集合，m表征具備的最優(yōu)個體及數(shù)量，表征第t代種群內對應著的第i個最優(yōu)個體；表征規(guī)范知識，Xi表示為 〈I,L,U〉,n為變量數(shù)目。，初始化上限u和下限l經由樣本具有的模式向量相關的下限以及上限得到；L j與Uj對應表征變量j所在的下限以及上限相關的適應值，經由初始化控制為+∞。

2.2.4 accept()接受函數(shù)

該函數(shù)能夠實現(xiàn)會對現(xiàn)下信仰空間帶來影響作用的知識經驗個體相關的選擇控制，并且種群空間內選定β比例完成最優(yōu)個體的選擇處理。

2.2.5 信仰空間的更新

在信仰空間實施的調整工作中，需要借以更新函數(shù)update()完成。其定義[4]情況是：選用最優(yōu)個體實現(xiàn)知識空間內的更新處理，即，其中表示第 代最優(yōu)個體。

規(guī)范知識N根據(jù)以下規(guī)則更新[5]：

2.2.6 influence()影響函數(shù)

該類函數(shù)能夠借由規(guī)范知識的方式對變量步長情況進行有效的調整控制，而借由形勢知識實現(xiàn)變化方向的調整控制。相關定義[4]對應是：

此處，N(01)，對應表征滿足標準正態(tài)分布要求的隨機數(shù)，對應表征知識空間內變量i能夠調整控制的區(qū)間長度，λ對應表征的是步長收縮因子情況。

2.3 算法實現(xiàn)步驟

Step1 種群空間初始化控制。隨機選定K個樣本充當分析的聚類中心，并實施編碼；

Step2 經由適應度函數(shù)實現(xiàn)空間內相關個體的評價分析；

Step3 在已有待選解的基礎上，參照知識空間結構獲得相應的初始知識空間；

Step4 參照影響函數(shù)帶給種群空間內各父代個體的變異影響，獲得需要的p 個個體；

Step5 針對父子個體構建的2p 種群空間內的各個個體，隨機選定c 個個體展開對比分析。若是該個體相較對比個體而言更優(yōu)，則視其為勝利，并且把個體具備的勝利次數(shù)做好記錄；

Step6 選定前p 個勝利次數(shù)最高的個體充當下代父體；

Step7 借助接受函數(shù)accept 實現(xiàn)信仰空間的更新處理；

Step8 若是與終止條件不相符，則繼續(xù)Step4；否則，停止運行。

3 文化-K 均值聚類混合算法算例分析

算例[6]：給出2 個數(shù)據(jù)集。

表1 數(shù)據(jù)集說明

在數(shù)據(jù)集上實施五十次運算分析后，本文算法與初始K 均值算法的結果情況，參見表2。

表2 兩種算法在Iris數(shù)據(jù)集上比較

實驗結果表明，K均值算法實現(xiàn)收斂的速度更快，只是更易出現(xiàn)局部最優(yōu)的問題，而且會對選定的初始聚類中心更為敏感，而本文文化-K均值聚類混合算法的收斂速度雖慢一些，但能夠獲得全局最優(yōu)值，且克服了初始聚類中心的敏感性。