基于改進GSA的數據聚類機制

張 小 慶

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

0 引 言

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

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

1 數據聚類形式化描述

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

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

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

(1)

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

(2)

式中：|Cl|表示聚類Cl中的數據對象個數。

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

2 基于改進引力搜索的數據聚類算法

2.1 引力搜索算法GSA

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

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

(3)

(4)

(5)

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

(6)

(7)

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

(8)

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

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

(9)

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

(10)

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

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

(11)

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

(12)

(13)

2.2 聚類解的編碼表示

圖1 候選解編碼

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

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

(14)

(15)

(16)

(17)

2.4 粒子速度更新改進

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

圖2 粒子慢速移動

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

(18)

(19)

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

圖3 新的速度更新規則下的粒子移動

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

圖4 加速因子的取值規則

2.5 算法步驟

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

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

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

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

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

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

3 實驗分析

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

表1 引力搜索算法相關參數

表2 測試基準數據集的相關參數

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

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

表3 聚類失誤率 %

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

圖5 數據對象成員與質心的平均距離

4 結 語

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