基于自適應(yīng)PSO的改進K-m eans算法及其在電子病歷聚類分析應(yīng)用*

沐燕舟 丁衛(wèi)平 高 峰 余利國 張 瓊

（南通大學(xué)計算機科學(xué)與技術(shù)學(xué)院 南通 226019）

1 引言

PSO是一種模擬自然界的生物活動以及群體智能的全局搜索算法，由Eberhart和Kennedy于1995年提出，該算法即具有進化算法的特點又與遺傳算法有相似的搜索及優(yōu)化能力［1］。由于其自身的原理簡單、可調(diào)參數(shù)相對較少、編碼易于實現(xiàn)且應(yīng)用效果明顯等特性，被廣泛地用于各類非線性問題的優(yōu)化。但是PSO對于離散問題的優(yōu)化則表現(xiàn)的不盡人意，往往會陷入局部最優(yōu)解。如：黃太安等［2］提出了一種蛙跳簡化粒子群算法，將粒子群分多組同時收索，每組粒子進行多次迭代后在分組，從而保證了粒子間的差異性，避免了算法的早熟收斂問題。倪慶劍等［3］提出了動態(tài)可變拓撲策略來協(xié)調(diào)PSO的勘測能力，避免了算法陷入局部最優(yōu)等。

聚類分析是將龐大的數(shù)據(jù)劃分為有意義的組，而在聚類分析的眾多方法中，K-means是最經(jīng)典最常用的一種聚類算法［4］。K-means聚類是一種矢量量化的方法，最初來自信號處理，由于其處理數(shù)據(jù)相對簡單、快速，已經(jīng)成為數(shù)據(jù)挖掘中的聚類分析的流行方法。然而，由于K-means算法本身對初始聚類中心較為敏感往往很容易陷入局部最優(yōu)解［5］。針對這類問題，符保龍等［6］提出了一種基于均值密度中心估計的K-means聚類算法，Bandyopadhyay S等［7］介紹了一種利用K-means算法原理的基于遺傳算法的高效聚類技術(shù)，文獻結(jié)合了K-means和遺傳算法的優(yōu)點，避免了陷入局部最優(yōu)解。傅濤等［8］將PSO和K-means算法結(jié)合在一起用于網(wǎng)絡(luò)入侵檢測分析，其誤報率大大降低。

綜上所述，我們不難看出上述算法都在一定程度上緩和了原始PSO或K-means存在的一些問題，但是由于醫(yī)療病歷數(shù)據(jù)具有明顯的異構(gòu)性、數(shù)字表征不明顯、數(shù)據(jù)本身的多樣性等特點［9］，這兩類算法并不能夠很好地處理分析復(fù)雜多樣的醫(yī)療數(shù)據(jù)。因此，本文提出了一種基于自適應(yīng)PSO的K-means算法，該算法設(shè)計了一種自適應(yīng)慣性權(quán)重函數(shù)對PSO進行動態(tài)調(diào)整，然后與K-means算法融合，使K-means的各個初始聚類中心能自適應(yīng)生成，具有了更好的全局尋優(yōu)能力。該算法融合了以上兩種算法的優(yōu)點具有更高的電子病歷病癥聚類準確率和執(zhí)行效率。

2 改進的自適應(yīng)PSO

2.1 標準PSO

算法中每個粒子的速度向量定義為vi=（v1i，v2i，…，viD），位置向量定義為 xi=（x1i，xi2，…，xD），將每個粒子在迭代中的歷史最優(yōu)pBest設(shè)為

i當前位置，群體中最優(yōu)的個體作為當前的pBest。在每次迭代過程中，分別計算每個粒子的適應(yīng)度函數(shù)值。若粒子當前適應(yīng)度函數(shù)值優(yōu)于歷史最優(yōu)值，則將歷史最優(yōu)pBest更新為當前位置。當該粒子的歷史最優(yōu)比全局要好，則該粒子的歷史最優(yōu)替代全局最優(yōu)pBest。

粒子i的第d維的速度和位置更新公式［10］如下：

其中i代表粒子編號，d為求解問題維數(shù)，c1和c2代表非負常數(shù)學(xué)習(xí)因子，rand1d和rand2d表示區(qū)間［0，1］上的隨機數(shù)，ω為慣性權(quán)重，一般初始化為0.9。

2.2 自適應(yīng)PSO

本文提出了自適應(yīng)慣性權(quán)重ω，更新公式如下：

其中N表示粒子總數(shù)，n表示集合中粒子的個數(shù)，φ表示平衡系數(shù)，ρ表示粒子密度，表示最大慣性權(quán)重，表示最小慣性權(quán)重，t表示迭代次數(shù)。由式（4）可知，，則

，其中當?shù)螖?shù)t（t＞0）增加時，由數(shù)學(xué)關(guān)系可以推導(dǎo)出逐漸增大而ω逐漸減小，結(jié)合式（1）就實現(xiàn)了PSO快速收斂，但又不會陷入局部最優(yōu)的目的。在實際操作的時候，粒子群可以依靠這種關(guān)系來實現(xiàn)對ω值的調(diào)整，使得慣性權(quán)重始終在一個范圍內(nèi)變化，更好地尋找全局最優(yōu)解。即當粒子密度 ρ值大的時候，說明多數(shù)粒子靠近最優(yōu)解，ρt2值隨之增大，由式（4）可知，ω值在逐漸減小，再結(jié)合式（1）就可以得到更精確的解。反之，當粒子密度ρ值變小，ω值在逐漸增大，從而進一步避免了早熟收斂情況的發(fā)生。這樣有效地調(diào)節(jié)v值的方式，讓式（4）達到了一種自適應(yīng)的狀態(tài)，對于提高整個PSO算法的全局尋優(yōu)能力有了很大的幫助。

3 基于自適應(yīng)PSO的K-m eans算法

K-means算法的優(yōu)點就在于它的簡單，所以在處理大量數(shù)據(jù)集的時候就意味著它要比其他的聚類算法執(zhí)行的更快更有效。但是K-means算法也由于其對初始聚類中心點選擇的敏感性的問題，會造成聚類結(jié)果隨著輸入初始值的不同而波動，影響聚類的準確性。針對上述PSO算法和K-means算法的不足，本文設(shè)計了基于自適應(yīng)PSO的K-means算法，其流程圖如圖1所示。

該算法具體子步驟描述如下：

輸入：待聚類數(shù)據(jù)集N，聚類數(shù)目k，粒子群的種群規(guī)模m，最大迭代次數(shù)IterMax；

輸出：聚類數(shù)據(jù)集的聚類中心不再變化的k個聚類劃分。

Step 1：初始化PSO；

1）從數(shù)據(jù)集N中隨機選擇k個中心點，將其作為粒子位置xi的初始值；

2）初始化粒子速度vi、個體最優(yōu)位置 pBesti以及對應(yīng)的個體極值f（pBesti）、群體最優(yōu)位置gBesti及其對應(yīng)的全局極值f（gBesti）；

3）Repeat m次；

Step 2：執(zhí)行PSO；

1）按照適應(yīng)度函數(shù)求得每個粒子的適應(yīng)度值f（xi）；

2）對于每個粒子，如果粒子的適應(yīng)度值f（xi）小于個體極值f（pBesti），則更新粒子的個體極值f（pBesti）以及個體最優(yōu)位置pBesti；

3）如果所有粒子的個體極值f（pBesti）的最小值f（pBestimin）小于粒子群的全局極值f（gBesti），則更新粒子群的全局極值f（pBesti）以及群體最優(yōu)位置gBesti；

4）根據(jù)式（4）動態(tài)調(diào)整慣性權(quán)重，并根據(jù)式（1）和式（2）分別進行更新每個粒子的速度和位置；

5）Until到達最大迭代次數(shù)IterMax；

Step 3：將Step2中得到的k個初始聚類中心作為K-means算法的初始值；

Step 4：將數(shù)據(jù)集中的點指派到距離最近的質(zhì)點，更新每個簇的質(zhì)心；

Step 5：重復(fù)Step4直到質(zhì)心不在發(fā)生變化，算法結(jié)束。

通過對PSO慣性權(quán)重ω的自適應(yīng)處理，有效地緩解了標準PSO算法中存在的早熟收斂及局部尋優(yōu)能力較差的問題，提升了PSO算法全局尋優(yōu)的能力，并將兩種算法的優(yōu)勢進行互補以達到更好的聚類效果。

4 電子病歷聚類分析應(yīng)用

隨著信息技術(shù)在各領(lǐng)域的廣泛應(yīng)用，醫(yī)院也紛紛采取了電子病歷的方式管理醫(yī)療數(shù)據(jù)，與傳統(tǒng)的紙質(zhì)病歷相比，電子病歷更以規(guī)范、方便、高效著稱［11］。隨著電子病歷數(shù)據(jù)持續(xù)的海量增長，基于電子病歷數(shù)據(jù)的聚類應(yīng)用也應(yīng)運而生。然而電子病歷數(shù)據(jù)聚類時很難達到預(yù)期效果，一方面，是由于其數(shù)據(jù)的海量性和主觀性，另一方面，更是異構(gòu)性和數(shù)字表征不明顯的特性所致，所以傳統(tǒng)的聚類方法很難處理這類結(jié)構(gòu)復(fù)雜的醫(yī)學(xué)數(shù)據(jù)［12～15］。

為了進一步驗證本文提出的基于自適應(yīng)PSO的改進K-means算法在實際數(shù)據(jù)應(yīng)用的效率，本文開展了電子病歷數(shù)據(jù)聚類分析實驗。實驗的環(huán)境：操作系統(tǒng) W indows 7，處理器 Intel（R）Core（TM）i7-6567U CPU@3.30GHz，電腦內(nèi)存 10GB，編程語言 Java，編程軟件 eclipse Mars.2Release（4.5.2），電子病歷系統(tǒng)相關(guān)頁面如圖2所示。

圖2 電子病歷系統(tǒng)頁面

該算法中的相關(guān)參數(shù)設(shè)置：學(xué)習(xí)因子 c1和c2取2.0，和?。?，1］區(qū)間的隨機數(shù)，ω∈［0.2，1.0］，聚類數(shù)目k初始化為16，粒子群的種群規(guī)模m為20，最大迭代次數(shù)IterMax設(shè)為100次。實驗數(shù)據(jù)是南通某醫(yī)院電子病歷中肝功能檢查數(shù)據(jù)，共有203254條的數(shù)據(jù)樣本，為了方便算法實施，經(jīng)過數(shù)據(jù)預(yù)處理去掉了一些臟數(shù)據(jù)后得到以下6個屬性，具體數(shù)據(jù)格式如表1所示。

表1 電子病歷實驗數(shù)據(jù)表

實驗將標準K-means算法、PSO-based K-means算法和基于自適應(yīng)PSO的K-means算法進行對比，實驗中采用將每種算法分別執(zhí)行30次，并將測試的結(jié)果數(shù)據(jù)進行平均值運算（小數(shù)點后面取兩位）的方法來盡可能降低非算法和數(shù)據(jù)因素所導(dǎo)致的人為誤差。選取的部分數(shù)據(jù)集進行算法聚類準確率和執(zhí)行時間對比結(jié)果如表2和表3所示。

表2 電子病歷肝病病癥的聚類準確率比較（%）

表3 電子病歷肝病病癥執(zhí)行時間比較（ms）

由表2可以看出，針對4組不同規(guī)模的數(shù)據(jù)集，標準K-means算法和PSO-based K-means算法的聚類準確率都隨著電子病歷肝病數(shù)據(jù)量的增大逐漸下降，并且數(shù)據(jù)量越大下降幅度越大，原因就是K-means算法在初始聚類中心選取的敏感性問題上沒有得到很好地處理，由于聚類中心初值的過于隨機，影響了算法的執(zhí)行準確率。而PSO-based K-means算法則是沒有考慮到電子病歷數(shù)據(jù)的特性，致使對肝病數(shù)據(jù)處理起來效率不高。本文算法在標準PSO算法的基礎(chǔ)上，通過對原始公式中參數(shù)慣性權(quán)重v的調(diào)整，使其有效地減小了粒子的早熟收斂，從而充分利用了PSO的全局尋優(yōu)能力，并針對電子病歷數(shù)據(jù)的特點做了多模式數(shù)據(jù)源組合和數(shù)據(jù)變換的特殊處理，使其克服了電子病歷數(shù)據(jù)的復(fù)雜特性，因此能篩選出更合理的初始聚類中心。由表3和圖3可以看出，在數(shù)據(jù)量不大的時候，三種算法在處理數(shù)據(jù)的速度上差距不大，但是當數(shù)據(jù)量達到上萬條時，本文算法表現(xiàn)出了更優(yōu)越的處理能力，直觀地反映在了處理數(shù)據(jù)消耗的時間上。

圖3 電子病歷肝病病癥聚類分析速率比較圖

5 結(jié)語

傳統(tǒng)的K-means聚類結(jié)果不穩(wěn)定主要是算法初始聚類中心的隨機選擇所致，聚類結(jié)果隨著初始聚類中心的變化而變化，本文提出的基于自適應(yīng)PSO的K-means算法，通過調(diào)整PSO的慣性權(quán)重v以求達到自適應(yīng)，使得PSO充分的發(fā)揮了全局最優(yōu)的特性，通過其優(yōu)化生成K-means的初始聚類中心，從而避免了聚類結(jié)果陷入局部最優(yōu)，最終訓(xùn)練出可靠健壯的模型。本文算法應(yīng)用于電子病歷數(shù)據(jù)的聚類分析，結(jié)果表明本文提出的基于自適應(yīng)PSO的K-means算法在電子病歷數(shù)據(jù)聚類分析上的聚類準確率和效率明顯高于標準K-means算法和PSO-based K-means算法，這將有助于改善電子病歷數(shù)據(jù)的聚類質(zhì)量，提高聚類算法在大數(shù)據(jù)醫(yī)療方面的挖掘效率。

傳統(tǒng)的數(shù)據(jù)挖掘算法如決策樹算法、神經(jīng)網(wǎng)絡(luò)算法以及關(guān)聯(lián)分析算法在面對數(shù)據(jù)復(fù)雜多樣的電子病歷醫(yī)療數(shù)據(jù)時常常出現(xiàn)數(shù)據(jù)過擬合影響模型預(yù)測性能，訓(xùn)練數(shù)據(jù)特征缺失影響模型訓(xùn)練等一系列問題。在今后的研究工作中我們進一步將本文提出改進的基于自適應(yīng)PSO的K-means算法應(yīng)用到電子病歷其他病癥數(shù)據(jù)分析中，對不同病例開展分類和預(yù)測研究，進一步提高算法在處理醫(yī)療數(shù)據(jù)時的應(yīng)用效率和范圍。