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

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

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

DOIDOI：10.11907/rjdk.162084

中圖分類號(hào)：TP317.4

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

0 引言

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

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

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

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

1.1 K均值聚類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)

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

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

3 結(jié)語

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

參考文獻(xiàn)：

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

[2] 王彥明，錢建忠，潘晨.基于SVM-2DPCA的X光胸片異常篩查[J].計(jì)算機(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é)報(bào)， 2008，19（1）：48-61.

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