基于改進GSA的數(shù)據(jù)聚類機制

張 小 慶

(武漢輕工大學數(shù)學與計算機學院 湖北 武漢 430048)

0 引 言

數(shù)據(jù)聚類是數(shù)據(jù)挖掘的主要分析手段[1]，廣泛應用于模式識別[2]、機器學習[3]、圖像分析[4]、生物信息[5]領域，主要是將原始數(shù)據(jù)對象集根據(jù)某種特征劃分為若干群組(聚類)。分類后的數(shù)據(jù)對象，同一聚類的數(shù)據(jù)對象將具有盡可能多的相似性，而不同聚類間的數(shù)據(jù)對象將盡量不同。數(shù)據(jù)聚類方法很多，但由于應用種類、數(shù)據(jù)類型、聚類目標不同，很難設計可滿足所有數(shù)據(jù)類型的聚類方法。目前，聚類方法有兩種：分層型方法和分割型方法。分層聚類方法遞歸地以凝聚模式(自底向上)或分裂模式(自頂向下)尋找數(shù)據(jù)聚類。凝聚方式從單個聚類(由單個數(shù)據(jù)對象組成的聚類)中的每個數(shù)據(jù)對象開始，逐漸將最相似的數(shù)據(jù)進行合并；分裂方式則從一個聚類(整個數(shù)據(jù)對象形成的聚類)中的所有數(shù)據(jù)對象開始，重復將聚類劃分為更小聚類。分割聚類方法同步尋找所有聚類，而無須形成層次結構。K均值方法[6]是最為經典的分割式聚類方法，應用也最廣泛。但該方法進行數(shù)據(jù)聚類時試圖最小化聚類內的數(shù)據(jù)差異，方法過分依賴初始質心狀態(tài)，比較易于陷入局部最優(yōu)。

群體智能方法是解決數(shù)據(jù)聚類的一種有效方法，如遺傳算法[7]、粒子群算法[8]、蟻群算法[9]、蜂群算法[10]等。然而，以上方法處理數(shù)據(jù)聚類時可能陷入局部最優(yōu)。引力搜索算法[11]是目前解決連續(xù)最優(yōu)化問題的較為流行的隨機種群元啟發(fā)式方法，該方法受牛頓萬有引力定理的啟發(fā)，通過種群粒子位置移動尋找最優(yōu)解，即隨著算法的迭代，粒子根據(jù)它們之間的萬有引力在搜索空間內不斷運動，直到粒子移動到最優(yōu)位置時，即找到最優(yōu)解。引力搜索算法已被證明在搜索最優(yōu)解的效率上已超過同類智能群體算法，并且已經被用于求解大數(shù)據(jù)聚類問題。文獻[12]提出基于群組引力搜索的數(shù)據(jù)聚類算法GGSA，算法利用一種特定的群組編碼模式將聚簇的相關結構轉換為引力搜索空間中的問題解。文獻[13-14]均結合K調和均值機制設計了引力搜索聚類算法IGSAKHM和G-KHM，但算法僅改進了處于邊界位置的數(shù)據(jù)對象，沒有系統(tǒng)考慮傳統(tǒng)引力搜索的粒子早熟問題。文獻[15]則僅僅結合了K均值方法與傳統(tǒng)引力搜索機制，設計了聚類算法GSA-KM，也未考慮傳統(tǒng)引力搜索的固有不足。文獻[16]為了增加種群多樣性，將蜂群算法引入引力搜索中，設計了聚類算法BFGSA。算法從初始化、鄰居粒子搜索和搜索方向三個方面進行了改進，可以有效實現(xiàn)數(shù)據(jù)聚類。與以上研究不同，本文的主要意圖是利用改進的引力搜索算法解決數(shù)據(jù)聚類問題，并針對性地解決三個基本問題：1) 數(shù)據(jù)聚類解與引力搜索中粒子表示的映射問題；2) 粒子間的距離度量與聚類間距度量的映射問題；3) 粒子速度更新改進以避免早熟。

1 數(shù)據(jù)聚類形式化描述

1) 每個聚類至少包括一個數(shù)據(jù)對象，即Ci≠?，i=1,2,…,k；

2) 不同聚類間不存在相同的數(shù)據(jù)對象，即Ci∩Cj=?,i≠j,i,j=1,2,…,k；

度量數(shù)據(jù)聚類質量的目標函數(shù)為均方量化誤差之和，定義為：

(1)

式中：k表示數(shù)據(jù)聚類數(shù)量;‖Oi-Zl‖2表示數(shù)據(jù)對象Oi與聚類l的質心Zl間的歐氏距離。聚類Cl的質心Zl定義為：

(2)

式中：|Cl|表示聚類Cl中的數(shù)據(jù)對象個數(shù)。

數(shù)據(jù)聚類最優(yōu)化目標是通過最小化目標函數(shù)尋找k個聚類質心，使得聚類內的數(shù)據(jù)對象到達其質心的距離之和最小。

2 基于改進引力搜索的數(shù)據(jù)聚類算法

2.1 引力搜索算法GSA

引力搜索算法是受牛頓萬有引力啟發(fā)形成的一種多維解空間中求解連續(xù)優(yōu)化問題的有效方法。假定多個粒子在多維空間中移動，每個粒子代表問題的一個解，粒子擁有的引力質量越大，其性能越好，這是由于質量更大的粒子對其他粒子具有更大的吸引力。在引力搜索算法的執(zhí)行過程中，每個粒子將根據(jù)引力調整位置，并向著種群中最優(yōu)的K個粒子方向移動。

設系統(tǒng)有N個粒子在n維空間移動，粒子i的位置為：

(3)

(4)

(5)

式中：mi(t)為迭代t時粒子i的適應度比重；Mi(t)為迭代t時粒子i的質量;fiti(t)為迭代t時粒子i的適應度，由目標函數(shù)定義;worst(t)為迭代t時所有粒子中的最差適應度;best(t)為迭代t時所有粒子中的最優(yōu)適應度。

(6)

(7)

根據(jù)萬有引力定理，計算粒子加速度需要計算粒子受到的引力總和。迭代t時，維度d上粒子j對i的引力為：

(8)

式中：Mj為吸引方粒子j的質量;Mi為被吸引方粒子i的質量;G(t)為迭代t時引力系數(shù);ε為極小常量;Dij為粒子i與粒子j間的歐氏距離。

Dij(t)=‖Xi(t),Xj(t)‖2

(9)

粒子i在維度d上受到的總引力以所受引力權值表示為：

(10)

式中：randj為[0,1]間的隨機數(shù);kbest為擁有最優(yōu)適應度和最大粒子質量的第一批k個粒子的集合，k的取值表示為時間的函數(shù)，算法開始時其初值為kini，然后隨時間遞減至1。

根據(jù)萬有引力，迭代t時，粒子i在維度d上的加速度為：

(11)

粒子移動過程中，其速度與位置的更新公式為：

(12)

(13)

2.2 聚類解的編碼表示

圖1 候選解編碼

2.3 基于漢明距離的聚類間距表示

引力搜索算法通過在問題解空間中的粒子位置移動搜索問題的最優(yōu)解，由粒子位置更新公式可知，新的粒子位置由舊的粒子位置與粒子的移動長度之和構成，粒子的移動長度即為粒子的速度。由粒子速度更新公式可知，新的粒子速度由兩部分構成。一部分為當前迭代時的速度，該部分與其他粒子的移動速度無關；另一部分為粒子的加速度，該部分需要考慮kbest集合中所有粒子成員位置對該粒子的影響。而由加速度計算公式可知，加速度由kbest集合中粒子的位置、粒子間的線性距離、粒子間的歐氏距離、kbest集合中粒子的質量以及引力系數(shù)共同決定。

(14)

(15)

(16)

(17)

2.4 粒子速度更新改進

對于引力搜索算法而言，搜索空間的探索和局部空間的開發(fā)具有同等重要性。為了得到最優(yōu)解，搜索過程必須協(xié)調兩者的關系。引力搜索算法中的引力系數(shù)的初始值通常設置為較大值，這會導致搜索粒子的較快移動。為了在搜索晚期開發(fā)出較好的解，引力系數(shù)會隨著迭代次數(shù)增加而降低。而引力系數(shù)的降低會顯著影響引力強度，進而可能導致搜索粒子的慢速移動。這種慢速移動會影響問題求解的收斂速度和增加局部早熟的可能。圖2為一種在迭代晚期可能出現(xiàn)的粒子慢速移動現(xiàn)象。圖中，三個粒子試圖尋找全局最優(yōu)解，三個粒子在萬有引力的作用下產生了相互吸引力。在迭代t時，粒子M3距離最優(yōu)解最近，且擁有最大的質量。在迭代t+1時，三個粒子向著其他粒子聚焦的中心位置移動，而沒有向著全局最優(yōu)解的方向移動。由于粒子M3向著全局最優(yōu)解的反方向移動，其適應度值出現(xiàn)下降；粒子M1和M2在向著全局最優(yōu)解的正確方向上移動，適應度有所增加。然而，由于巨大的萬有引力的影響，粒子M1和M2無法越過M3而得到最優(yōu)解或接近最優(yōu)解。主要原因就是搜索粒子的慢速移動導致了局部的收斂，使得在迭代t+2時，所有搜索粒子收斂在局部位置而遠離全局最優(yōu)解。

圖2 粒子慢速移動

引力系數(shù)G(t)度量了搜索空間中粒子位置改變的速度，較大的G(t)使得粒子移動的迭代初期產生更大的引力和更快的移動速度，不利用局部解的開發(fā)。本文將改進粒子速度更新公式，利用當前種群中的最優(yōu)粒子的位置來加快局部開發(fā)過程，加速粒子向著最優(yōu)粒子移動，有助于在下一迭代中使其超越當前的最優(yōu)粒子，引入加速因子至粒子速度更新中，將新的粒子速度更新定義為：

(18)

(19)

根據(jù)新的粒子速度更新規(guī)則可以看到，粒子速度更新包括三個部分，前兩個部分與引力搜索算法中的速度更新相同，僅在加速度前加了加速因子α，該部分主要針對加強粒子搜索過程中的開發(fā)能力，第三部分則引入了當前的最優(yōu)粒子，可以使得粒子可向著當前最優(yōu)粒子的方向加快移動。圖3為在新的速度更新規(guī)則下，與圖2相同場景下粒子的搜索過程。由于當前最優(yōu)粒子的加入和較好的加速因子的取值可以增加在迭代晚期搜索粒子的加速度，使粒子能夠脫離局部早熟。因此，在迭代t+1時，M1由于在更大的引力和加速度的作用下，可以穿越當前的最優(yōu)粒子M3。粒子M2也逐漸接近最優(yōu)解，M3則暫時遠離最優(yōu)位置。在迭代t+2時，M3則由于相同的原因又穿越至M1的位置而達到更加接近全局最優(yōu)解的位置，M1和M2也更加接近全局最優(yōu)解。換言之，三個搜索粒子均在向著全局最優(yōu)解的方向同步移動。

圖3 新的速度更新規(guī)則下的粒子移動

式(18)加速因子α和β的取值可通過自適應的方式進行調整，避免粒子速度更新時降低搜索能力，取值規(guī)則如圖4所示。降低α和增加β可使粒子在開發(fā)階段向著當前最優(yōu)粒子方向加速移動。加速因子的自適應調整可以使粒子進化在探索和開發(fā)兩個階段間逐漸轉換，使迭代初期的粒子具有更強的搜索能力，而迭代晚期的粒子具有更強的開發(fā)能力。

圖4 加速因子的取值規(guī)則

2.5 算法步驟

步驟2粒子適應度評估和最優(yōu)粒子求解。根據(jù)目標函數(shù)計算所有粒子的目標函數(shù)值，保留目標函數(shù)值最小的粒子作為最優(yōu)粒子，并將其作為下一個候選的聚類解。尋找所有粒子中的最差粒子(目標函數(shù)最大)用于計算粒子個體的質量。具體表示為式(6)和式(7)。

步驟3計算引力系數(shù)。根據(jù)式(19)計算每次迭代中粒子的引力系數(shù)。

步驟4計算粒子引力質量。根據(jù)適應度函數(shù)計算粒子質量：

步驟5計算粒子吸力和加速度。根據(jù)式(8)和式(11)計算粒子引力和粒子加速度。

步驟6計算粒子速度和位置。根據(jù)式(13)和式(18)更新粒子速度和粒子位置。

步驟7終止條件。若達到最大迭代次數(shù)，保留種群中擁有最小目標函數(shù)值的粒子作為最終的數(shù)據(jù)聚類解，并停止迭代；否則，轉步驟2-步驟7繼續(xù)執(zhí)行。

3 實驗分析

在MATLAB中利用UCI數(shù)據(jù)庫的基準數(shù)據(jù)集評估聚類算法性能，硬件環(huán)境為Inter Core i3-3120M CPU@2.5 GHz+4 GB內存。與GSA相關的參數(shù)取值如表1所示。選取13個基準數(shù)據(jù)集作為數(shù)據(jù)測試源，基準數(shù)據(jù)集涵蓋低、中和高維度數(shù)據(jù)，均是機器學習的經典測試用例，其特征如表2所示，包括數(shù)據(jù)對象個數(shù)、訓練數(shù)據(jù)量、測試數(shù)據(jù)量、特征數(shù)量和分類數(shù)量。對于每一個基準數(shù)據(jù)集，隨機選取75%的數(shù)據(jù)作為訓練數(shù)據(jù)集，剩余25%的數(shù)據(jù)則作為算法的測試數(shù)據(jù)集。

表1 引力搜索算法相關參數(shù)

表2 測試基準數(shù)據(jù)集的相關參數(shù)

選取傳統(tǒng)GSA、GGSA、IGSAKHM、GSA-KM和BFGSA作為基準算法。對于測試的數(shù)據(jù)集，利用聚類失誤率CEP[12,16]衡量算法性能，CEP表示數(shù)據(jù)集中未完成聚類的數(shù)據(jù)占總體數(shù)據(jù)量的比例，即：

表3統(tǒng)計了在測試數(shù)據(jù)集中各算法的聚類失誤率情況?？梢钥闯?，本文算法在多數(shù)測試數(shù)據(jù)集中均擁有最小的聚類失誤率，除了E.Coli、Heart兩種數(shù)據(jù)集，其聚類失誤率要略大于BFGSA。傳統(tǒng)GSA得到的聚類失誤率是所有算法中最高的，這是由于該算法在初始種群生成以及聚類解的表達上均未作出任何優(yōu)化，無法準確識別數(shù)據(jù)特征。基于群組的數(shù)據(jù)聚類算法GGSA則通過一種特定的群組編碼模式將聚簇的相關結構轉換為引力搜索空間中的問題解，降低了一些聚類失誤率。K調和均值數(shù)據(jù)聚類算法IGSAKHM則解決了K均值數(shù)據(jù)聚類算法GSA-KM過分依賴于初始質心選擇的問題，結合改進的GSA之后可以更好地實現(xiàn)數(shù)據(jù)聚類。BFGSA則進一步通過蜂群算法增加了引力搜索中種群粒子的多樣性，同時在粒子初始化、鄰居粒子搜索和搜索方向三個方面進行了改進，更加有效地實現(xiàn)數(shù)據(jù)聚類。

表3 聚類失誤率 %

圖5是不同聚類算法所形成的聚類中數(shù)據(jù)對象成員與相應質心的平均距離。聚類失誤率越低，相應反映了更多的數(shù)據(jù)對象可以選擇加入到與質心距離更短的聚類中，而未進行正確聚類的數(shù)據(jù)對象將隨機選擇聚類并計算與質心的間距，從而導致數(shù)據(jù)對象成員與質心的平均間距不是最小。本文算法在聚類編碼、聚類距離度量、粒子速度更新機制上的改進使得最終形成的數(shù)據(jù)聚類解可以得到更小的平均距離。

圖5 數(shù)據(jù)對象成員與質心的平均距離

4 結 語

本文提出基于改進引力搜索機制的數(shù)據(jù)聚類算法。定義了引力搜索進化聚類解編碼方式，并設計了基于漢明距離的引力搜索粒子距離度量方法，可以有效衡量數(shù)據(jù)對象在各維度屬性上的不同。在粒子速度更新上，引入加速因子到粒子速度更新中，利用最優(yōu)粒子位置代表的聚類解來加速局部開發(fā)過程，加速粒子向最優(yōu)粒子移動，有效均衡局部開發(fā)與全局搜索間的平衡。實驗結果證明了算法在降低聚類失誤率上的優(yōu)勢。