基于改進(jìn)K均值算法的X光片圖像聚類研究

徐秀芳+徐森+徐靜+安晶

摘 要：提出了一種改進(jìn)的K均值算法用于X光片圖像聚類。首先對X光片圖像進(jìn)行預(yù)處理，獲取數(shù)據(jù)，然后將每個點的灰度值存儲在灰度值矩陣中，最后用改進(jìn)的K均值算法對灰度值矩陣進(jìn)行聚類。對比實驗結(jié)果表明，改進(jìn)的K均值算法獲得了更加優(yōu)越的聚類結(jié)果。

關(guān)鍵詞：X光片；K均值；聚類分析；簇中心；灰度

DOIDOI：10.11907/rjdk.162084

中圖分類號：TP317.4

文獻(xiàn)標(biāo)識碼：A文章編號：1672-7800（2016）012-0156-03

0 引言

隨著科技在醫(yī)學(xué)領(lǐng)域的應(yīng)用，傳統(tǒng)的放射診斷學(xué)成為醫(yī)學(xué)影像的重要部分。X線攝影是臨床最常用的醫(yī)學(xué)檢查方法，幾乎適用于人體任何部位，它具有空間分辨率高、圖像清晰、層析分明的特點，常用作醫(yī)學(xué)診斷的輔助工具[1-3]。然而，由于在X光片成像時三維人體被顯示為二維圖像，所以人體器官顯示會出現(xiàn)重疊和失真現(xiàn)象。通過將聚類分析技術(shù)應(yīng)用于X光片數(shù)據(jù)，可為觀察者提供更多信息，降低重疊和失真帶來的影響[4]。

本文提出一種快速有效的X光片圖像聚類算法，通過改進(jìn)K均值算法的初始值選取方法，有效提高了聚類效果。對比實驗表明，本文算法獲得的聚類結(jié)果明顯優(yōu)于傳統(tǒng)的K均值算法。

1 改進(jìn)的K均值算法

X光片具有數(shù)據(jù)量巨大、數(shù)據(jù)點分布稀疏、存在大量近似點（灰度相同的點）的特性，所以并不是所有聚類方法都會產(chǎn)生比較好的結(jié)果。X光片圖像數(shù)據(jù)存在大量數(shù)據(jù)點，導(dǎo)致進(jìn)行聚類分析的算法時間復(fù)雜度和空間復(fù)雜度不能太高，否則消耗的時間和占用的內(nèi)存會難以承受。

1.1 K均值聚類

在所有聚類算法中，K均值算法適應(yīng)范圍廣泛，針對X光片圖像數(shù)據(jù)而言，類與類之間區(qū)別明顯，在處理大數(shù)據(jù)集時，算法時間和空間復(fù)雜度都表現(xiàn)良好。K均值用質(zhì)心定義原型，一般情況下數(shù)據(jù)點屬性的平均值被定義為質(zhì)心。大部分情況下，一個簇中不僅包含一個數(shù)據(jù)點，中心點是一組點中最具代表性的點[1]。K均值聚類可以用于各種數(shù)據(jù)類型，因為只需要對象之間的鄰近性度量。

K均值算法執(zhí)行前，需要指定K值，K值表示希望從對象中得到簇的個數(shù)。算法開始執(zhí)行時首先需要將每個點劃分到距離最近的簇中。將所有點劃分完后，計算每個簇的簇中心。重復(fù)劃分所有點到最近的簇，并計算簇中心位置，直到簇不再變化。具體算法如下：①指定K個點作為初始質(zhì)心；②Repeat；③將每個點指派到最近的質(zhì)心，形成K個簇；④重新計算每個簇的質(zhì)心；⑤Until；⑥質(zhì)心不再變化。

其中，K均值算法中的第③步如下，流程如圖1所示：

①Repeat；②比較數(shù)據(jù)點到每個簇中心的距離；③將數(shù)據(jù)點劃分到距離其最近的數(shù)據(jù)中心；④Until；⑤每個數(shù)據(jù)點都被劃分到了最近的簇中。

K均值算法中的第④步如下，流程如圖2所示：

①Repeat；②數(shù)據(jù)點所在簇的簇內(nèi)點數(shù)量加1；③數(shù)據(jù)點所在簇的總灰度=總灰度+數(shù)據(jù)點的灰度；④Until；⑤所有的數(shù)據(jù)點都被計算；⑥將每個簇的總灰度除以簇內(nèi)點的數(shù)量得到簇的平均灰度。

K均值算法優(yōu)點是適用范圍廣，當(dāng)簇與簇之間聚類較遠(yuǎn)差異較大時，數(shù)據(jù)維度較低的數(shù)據(jù)點分布相對密集，效果要好些。對于處理大數(shù)據(jù)集，這個算法較高效。

計算的時間復(fù)雜度為O（NKt），其中N是數(shù)據(jù)對象數(shù)目，t是迭代次數(shù)。一般來說，K≤N，t≤N。K均值算法的空間復(fù)雜度需求不高，只需要存放數(shù)據(jù)點和質(zhì)心。具體所需要的存儲空間為O（（m+k）n），其中m是對象數(shù)量，n是屬性數(shù)。

K均值算法缺點主要有：①算法執(zhí)行前需要人為設(shè)定簇的個數(shù)，但是簇的個數(shù)常常難以估計；②在K均值算法中每一次對數(shù)據(jù)點進(jìn)行劃分都是由上一次劃分得到的簇中心決定的，所以K均值算法的最終結(jié)果是由最初選取的簇中心決定的。選擇不適當(dāng)?shù)臄?shù)據(jù)點作為初始的簇中心（比如彼此靠得很近的數(shù)據(jù)點），就可能導(dǎo)致最后結(jié)果偏差。因此初始值的選取成為K均值算法無法回避的問題。目前為止，還沒有發(fā)現(xiàn)一個適應(yīng)范圍很廣的初始值選取方法；③K均值算法需要在一次次迭代中不斷修改簇中心，每次修改后都需要將所有點重新劃分。當(dāng)數(shù)據(jù)量很大時，這樣的操作十分消耗時間。所以，在面對海量數(shù)據(jù)計算時需要改進(jìn)算法，以降低時間復(fù)雜度；④K均值算法的聚類劃分特性，決定了它在處理非球狀簇、不同尺寸、不同密度簇時，結(jié)果令人不滿意，而且K均值算法受離群點和噪聲的影響較大。

1.2 改進(jìn)的K均值算法

本文首先對X光片進(jìn)行預(yù)處理，然后從圖片中獲取數(shù)據(jù)，獲得圖像中每個點的灰度值，存儲在灰度值矩陣G中。Gij表示圖像中第i行、第j列點的灰度。對數(shù)據(jù)點進(jìn)行聚類后，可以將處于同一個簇的點用同一種顏色在圖片上標(biāo)出，從而進(jìn)行直觀判斷。

由于K均值算法的聚類結(jié)果受初始簇中心影響極大，簇中心選取錯誤會導(dǎo)致很差的集成結(jié)果，所以k個初始簇中心選取至關(guān)重要。本文改進(jìn)了傳統(tǒng)K均值算法，流程如圖3所示，主要步驟如下：①隨機選取1個簇中心；②Repeat；③再隨機選取1個簇中心；④比較選取的簇中心和之前選取的簇中心灰度值是否相同；⑤若相同則重新選取并回到步驟④；⑥Until；⑦簇中心的個數(shù)達(dá)到k個；⑧Repeat；⑨計算每個點到各個簇中心的距離；⑩找出每個點到各個簇中心的最短距離；B11將點劃分到相應(yīng)簇中，并修改Lij的值；B12重新計算每個簇的中心；B13Until；B14每個簇的中心都不再變化。

在k個初始簇中心選取比較理想的情況下，k個聚類中心均勻地分布在圖像的數(shù)據(jù)點中，此情況下獲得的聚類結(jié)果會比較理想。此時，K均值算法和改進(jìn)的K均值算法獲得的聚類結(jié)果基本一致。

在k個初始簇中心選取較差的情況下，K均值算法會得到“空簇”，產(chǎn)生較差的聚類結(jié)果，而改進(jìn)的K均值算法不會遇到這種問題。當(dāng)出現(xiàn)相同灰度值的簇，這個簇中心會被重新選取，從而使得每個簇中都會有一定數(shù)量的數(shù)據(jù)點，保證了迭代能正常進(jìn)行。

2 實驗

選取一張X光片作為原始數(shù)據(jù)，如圖4所示。使用改進(jìn)的K均值算法得到的結(jié)果如圖5所示。原始的K均值算法聚類結(jié)果受初始值影響較大，時好時壞，在初始簇中心選取到灰度值相同的點時就會出現(xiàn)如圖6所示的情況，有比較多的空簇。如圖7所示的聚類結(jié)果僅在初始簇中心選擇較好，沒有發(fā)生簇中心重疊的情況下才會出現(xiàn)。

改進(jìn)的K均值算法雖然在k個初始簇中心選取上作了改進(jìn)，使彼此不會有相同的灰度值，但這并不保證k個點會均勻地分布在所有數(shù)據(jù)點中，如果k個點彼此聚類比較近，仍會對簇的結(jié)果造成影響。

3 結(jié)語

本文提出了一種快速有效的X光片圖像聚類算法，通過改進(jìn)K均值算法的初始質(zhì)心選取，有效提高了聚類效果。對比實驗顯示，本文提出的算法獲得的聚類結(jié)果明顯優(yōu)于傳統(tǒng)的K均值算法，驗證了算法的有效性。

參考文獻(xiàn)：

[1] 史盛君，宋立新，趙陽.基于神經(jīng)網(wǎng)絡(luò)的乳腺X光片中腫塊檢測法[J].哈爾濱理工大學(xué)學(xué)報，2008，13（6）：101-104.

[2] 王彥明，錢建忠，潘晨.基于SVM-2DPCA的X光胸片異常篩查[J].計算機工程， 2009， 35（18）：170-172.

[3] 董亮，朱磊，苗鳳娟，等.基于DM642的X光片醫(yī)學(xué)輔助診斷系統(tǒng)[J].電子技術(shù)應(yīng)用， 2012， 37（7）：129-131.

[4] PANG NING TAN，MICHALE STEINBACH.數(shù)據(jù)挖掘?qū)д揫M].北京：人民郵電出版社，2011.

[5] 孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報， 2008，19（1）：48-61.

（責(zé)任編輯：杜能鋼）