基于加權(quán)變異免疫算法的微鈣化點(diǎn)特征選擇

（華南理工大學(xué) a.計(jì)算機(jī)科學(xué)與工程學(xué)院; b.生物力學(xué)研究所， 廣州 510641）



摘要：給出了一種乳腺X線照片微鈣化點(diǎn)的特征選擇方法，該方法運(yùn)用基于加權(quán)變異算子的免疫算法進(jìn)行特征優(yōu)選。加權(quán)變異算子能夠動(dòng)態(tài)調(diào)整抗體各部位的變異率，在高親和力抗體的鄰近小范圍搜索，在低親和力抗體的周圍跳躍式搜索；為了與支持向量機(jī)的分類準(zhǔn)則保持一致性，該免疫算法在特征空間中通過核函數(shù)計(jì)算親和力。實(shí)驗(yàn)使用該方法對微鈣化點(diǎn)的20種常用特征進(jìn)行選擇，其結(jié)果與經(jīng)驗(yàn)特征集基本相符但更精簡，提高了計(jì)算效率，是一種可行的特征選擇方法。

關(guān)鍵詞：免疫算法； 加權(quán)變異； 微鈣化點(diǎn)； 特征選擇； 乳房X線照片

中圖分類號：TP391文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)11-3302-03



Micro-calcification feature selectionbased on weighted mutation-immune algorithm



YANG Tie-juna，b， WU Xiao-mingb



(a.College of Computer Science Engineering; b.Biomechanics Institute， South China University of Technology， Guangzhou 510641， China)



Abstract:This paper proposed a feature selection method of micro-calcification (MC) in mammograms， which used weighted mutation based immune algorithm. The weighted mutation operator could dynamically adjust the mutation rates of different parts of antibodies， making searching nearby the high-affinity antibodies and around the low-affinity ones. Also， according to the classification principal of support vector machine classifier， computed the affinity in the feature space by kernel functions. Experiments show that the result feature set selected by the proposed method among the 20 commonly used features is consis-tent with the empirical one and smaller， which can lead to better performance. It is proved to be a feasible feature selection method.

Key words：immune algorithm; weighted mutating; micro-calcification; feature selection; mammogram



0引言

乳腺癌是現(xiàn)代婦女最為常見的惡性腫瘤病變之一，特別是近年來一些大中城市的婦女患乳腺癌的比例逐年增加，越來越受到相關(guān)研究人員的高度重視。由于目前尚不清楚其發(fā)病原因，只能依靠現(xiàn)有的技術(shù)手段早發(fā)現(xiàn)早治療，發(fā)現(xiàn)得越早，其成活率也就越高。乳腺X線攝影是進(jìn)行乳腺癌早期診斷的常用方法，而微鈣化點(diǎn)（micro-calcification，MC）是乳腺癌早期診斷的重要標(biāo)志之一。有經(jīng)驗(yàn)的放射科醫(yī)師通常可以根據(jù)X照片中MC的大小、形狀、分布和數(shù)量等特征對病變進(jìn)行良惡性診斷。

由于人工閱片的方式受到各種條件的限制，如閱片經(jīng)驗(yàn)，成像質(zhì)量等，即使是經(jīng)驗(yàn)豐富的醫(yī)師也難免會(huì)忽略一些肉眼很難發(fā)現(xiàn)的細(xì)節(jié)。有必要開展乳腺癌早期診斷CAD系統(tǒng)的研究。其中對MC的診斷研究尤為重要。MC在X線乳腺照片上一般表現(xiàn)為白色的亮點(diǎn)，它的尺寸很小，長度大約為0.1~1.0 mm，甚至更小，很難用肉眼發(fā)現(xiàn)。對MC的診斷分析一般包括以下幾個(gè)過程：a)定位可疑的鈣化灶；b)分割出微鈣化點(diǎn)；c)計(jì)算微鈣化點(diǎn)特征；d)將計(jì)算出的特征輸入到分類器進(jìn)行良惡性分析。上面的幾個(gè)過程又可以簡單地概括為預(yù)處理、特征提取和分類三個(gè)階段。其中，特征提取是指以預(yù)處理得到的目標(biāo)對象為輸入，計(jì)算目標(biāo)對象的形狀、紋理和頻域等各種特征，進(jìn)而作為分類階段的輸入。研究證明，特征提取的種類和數(shù)量并非越多越好。因?yàn)椋篴)并非所有特征或特征子集都是分類所必需的，有些特征是分類不相關(guān)的；b)特征的計(jì)算需要耗費(fèi)大量的時(shí)間；c)一般地，分類器的性能與特征向量的維數(shù)成反比。例如，J.C. Fu等人^[1]將MC特征分為三類，即紋理特征、空域特征和頻域特征，并對提取的61種特征使用序貫向前尋優(yōu)算法（SFS）進(jìn)行優(yōu)選，證明了優(yōu)選后的特征子集比沒有優(yōu)選的特征集具有更高的分類性能。P. Zhang等人^[2]提出了一種基于神經(jīng)網(wǎng)絡(luò)—遺傳算法的特征選擇方法，把14種常用特征進(jìn)行染色體編碼，進(jìn)化過程中根據(jù)染色體的分類率計(jì)算其親和力，進(jìn)化完成后也就得到了優(yōu)化的特征子集。王瑞平等人^[3]也提出了一種采用類內(nèi)－類間距離判據(jù)作為類別可分離判據(jù)，以遺傳算法求解最優(yōu)化的特征子集的選擇方法，從33種特征選擇出17種作為分類器輸入向量，取得了更高的分類性能（Az=0.881 4）。A. Papadopoulos等人^[4]根據(jù)每個(gè)特征的Az值大小來進(jìn)行選擇，Az值越大選擇該特征的概率也就越高。這些算法都是在原始空間中計(jì)算特征的分類水平值，而沒有考慮分類器的種類，因而特征選擇受到了在原始空間最有效的限制。針對這種情況，本文給出了一種基于加權(quán)變異免疫算法，在分類器支持向量機(jī)（SVM）的特征空間中計(jì)算分類水平值的MC特征選擇方法。

1加權(quán)變異免疫算法

免疫算法是模擬生物免疫系統(tǒng)抵抗外來抗原的生命規(guī)律來解決實(shí)際問題的一種進(jìn)化算法，具有自學(xué)習(xí)、識別自體/非自體和免疫記憶等特點(diǎn)，其主要應(yīng)用于非線性優(yōu)化問題，如模式識別、多模態(tài)函數(shù)優(yōu)化和異常檢測等，并且具有高效率、全局快速收斂和并行等優(yōu)點(diǎn)。

11免疫系統(tǒng)變異原理

免疫系統(tǒng)的演進(jìn)生命周期主要包括三個(gè)關(guān)鍵階段，即選擇、親和力成熟和免疫記憶。變異發(fā)生在親和力成熟階段，可以分為遺傳變異、隨機(jī)變異和高頻變異。遺傳變異是生物進(jìn)化的主要手段之一，其特點(diǎn)是生殖細(xì)胞的遺傳基因以極小的概率發(fā)生突變，在繁殖過程中遺傳給下一代。產(chǎn)生的新個(gè)體可能優(yōu)于父類，也有可能要發(fā)生退化，但是個(gè)體的決定性的穩(wěn)定基因一般是不會(huì)發(fā)生變異的；隨機(jī)變異是隨機(jī)選擇免疫細(xì)胞基因的位置發(fā)生變異；而高頻變異是指在與抗原結(jié)合后以非常大的變異率進(jìn)行分化擴(kuò)增，即抗體可變區(qū)的高頻變化。但是，該變化并不完全是隨機(jī)的，而是存在一些變異熱點(diǎn)。

抗體的穩(wěn)定部位是在不斷進(jìn)化過程中逐步形成的，該穩(wěn)定部位一般決定了免疫細(xì)胞具有對特定抗原的高親和力（特異性免疫）。

12加權(quán)變異算子

根據(jù)免疫系統(tǒng)的變異原理，選擇變異率時(shí)應(yīng)區(qū)分抗體的穩(wěn)定部位和非穩(wěn)定部位，即穩(wěn)定部位的變異率低，非穩(wěn)定部位的變異率高，而傳統(tǒng)的變異算法不作區(qū)分，均采用隨機(jī)變異。本算法在傳統(tǒng)免疫算法的基礎(chǔ)上，采用加權(quán)變異算子（weighted mutation operator）代替?zhèn)鹘y(tǒng)的隨機(jī)變異算子，通過識別抗體的穩(wěn)定/非穩(wěn)定部位來動(dòng)態(tài)調(diào)節(jié)變異率權(quán)值。加權(quán)變異算子的實(shí)質(zhì)是在高親和力抗體近鄰小范圍搜索，在低親和力抗體周圍大范圍跳躍搜索。

根據(jù)Perelson的形態(tài)空間理論，抗體和抗原均可以看做是L維形態(tài)空間S中的一個(gè)點(diǎn)，并用編碼串m來表示：

m=〈m1，m2，…，mL〉，m∈SL(1)

其中：mi表示形態(tài)空間中的第i個(gè)屬性，這里代表MC的第i個(gè)特征。這里抗體編碼采用二進(jìn)制方式，即mi=0表示第i個(gè)特征沒有被選擇，mi=1則表示被選擇。

抗體穩(wěn)定/非穩(wěn)定部位的識別在選擇階段進(jìn)行。選擇算子根據(jù)抗體的親和力從初始種群中挑選出高親和力的n個(gè)抗體組成優(yōu)選集E，則抗體第i個(gè)屬性的穩(wěn)定性與其在E中出現(xiàn)的概率pi成正比，其變異率ri與pi成反比。因此ri可以定義如下：

ri=k（Pe/pi）， pi=(∑nj=1Abj(mi))/n(2)

其中：Pe是經(jīng)驗(yàn)變異率；k是加權(quán)系數(shù)；Abj∈E，Abj(mi)表示第j個(gè)抗體的mi值。

13親和力計(jì)算公式

一般地，計(jì)算親和力只是在抗體的原始空間中進(jìn)行，即抗體的各個(gè)屬性所屬的定義域x。考慮分類階段采用SVM分類器的情況，SVM在求解最優(yōu)分類超平面時(shí)是在屬性的特征空間(x)中進(jìn)行，因此，這里親和力也將在屬性的特征空間中進(jìn)行計(jì)算。首先，定義特征空間中的類內(nèi)/類間歐氏距離。

定義 1特征空間的類內(nèi)歐氏距離(dij)和類間歐氏距離(Dij)是指同類和異類的兩個(gè)樣本xi、xj在其特征空間中的歐氏距離。其定義如下：

dijDij=((xi)-(xj))2=

K(xi，xi)-2K(xi，xj)+K(xj，xj) ，K(x，y)=(x)×(y)(3)

其中:K(·，·)是核函數(shù)，常見的有多項(xiàng)式和高斯徑向基等類型，分別參見式（4）和（5）。當(dāng)xi、xj是同類時(shí)，dij表示它們在空間的類內(nèi)歐氏距離；當(dāng)不同類時(shí)，Dij表示空間的類間歐氏距離。由式（3）可知，通過核函數(shù)的轉(zhuǎn)換，樣本間的歐氏距離只與它們在空間的內(nèi)積有關(guān)。

K（x，y)=(xTy+1)p；p＞0(4)

K(x，y)=exp(-‖x-y‖2/2σ2)；σ＞0(5)

親和力的計(jì)算根據(jù)dij、Dij確定。一般地，類內(nèi)距離越小，表明該類分布越緊湊，分類也越容易；而類間距離越大時(shí)，表示兩類的分界面越明顯。所以，親和力計(jì)算公式定義如下：

f=Dij/dij(6)

14WM-IA算法描述

根據(jù)上面的分析，將使用了加權(quán)變異算子的免疫算法稱為加權(quán)變異免疫算法（weighted mutation-immune algorithm，WM-IA）。該算法描述如下：

a)初始化抗體群A。設(shè)初始化種群規(guī)模為N，記憶池中的抗體數(shù)為m，那么隨機(jī)產(chǎn)生的抗體數(shù)為（N-m），進(jìn)化迭代次數(shù)g=1時(shí)，m=0。

b)選擇高親和力的抗體。根據(jù)式（6）分別計(jì)算每個(gè)抗體的親和力，選擇親和力最高的n個(gè)抗體組成優(yōu)選集E1；然后根據(jù)式（2）計(jì)算E1中抗體不同部位的變異率。

c)克隆擴(kuò)增。對E1中的每一個(gè)抗體進(jìn)行克隆擴(kuò)增，得到新的抗體集E2。

d)加權(quán)變異。根據(jù)b)計(jì)算得到的變異率，對E2的每個(gè)抗體進(jìn)行加權(quán)變異操作，得到變異后的抗體集E3。

e)免疫記憶。計(jì)算E3中抗體的親和力，取出親和力最高的M個(gè)互不相同的抗體（保持多樣性），與記憶池的抗體比較，將具有更高親和力的抗體加入到記憶池中。記憶池規(guī)模設(shè)為M，如果有新抗體加入記憶池，意味著記憶池中親和力相對較小的抗體將被淘汰。當(dāng)g=1時(shí)，記憶池為空。

f)重復(fù)a)~e)，直到滿足收斂條件。

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

21實(shí)驗(yàn)數(shù)據(jù)及預(yù)處理

實(shí)驗(yàn)使用的乳腺X線照片數(shù)據(jù)庫均來自廣州市腫瘤醫(yī)院放療中心乳腺科，共選取了12名患者的正位（簡稱CC位）和斜位（簡稱MLO位）乳腺X線照片。照片大小為1 375×1 858像素，灰度級別為256階。這些照片已經(jīng)由有經(jīng)驗(yàn)的醫(yī)師進(jìn)行了閱片并給出了相應(yīng)的診斷報(bào)告，還指出了MC的大概位置。

首先對這些照片進(jìn)行預(yù)處理，分割出含有MC的感興趣區(qū)域（ROI）。分割方法是：a)原始照片50%以上是背景信息，所以先用閾值法分割出目標(biāo)輪廓；b)分別使用對比度增強(qiáng)濾波器和Butterworth高通濾波器，進(jìn)一步過濾目標(biāo)輪廓中的背景；c)使用閾值法初步分割出MC；d)使用形態(tài)閉操作填充目標(biāo)空洞，形態(tài)開操作消除噪聲，最終得到MC的分割結(jié)果。共分割出80個(gè)ROIs。其中14個(gè)良性，66個(gè)惡性。圖1分別列出了其中一部分良性和惡性MC的ROIs（為了便于觀察，均有不同程度的放大）。

22MC特征集

選擇MC的初始特征集。診斷MC是良性或惡性的主要特征依據(jù)有：良性的MC數(shù)量較少，分布分散，形狀規(guī)整（顆粒狀、圓形、橢圓），形狀大小均勻，呈珍珠狀；惡性的MC數(shù)量多，分布集中，形狀不規(guī)則（桿狀、針尖狀或叉狀），形狀大小各異，呈泥沙狀。一般將MC特征分為紋理特征、空域特征和頻域特征等三種類型，人工閱片主要依靠的是空域特征，其次是紋理特征。結(jié)合人工閱片參考的MC特征和各種CAD系統(tǒng)中使用的MC特征，選取了20種常用特征組成初始MC特征集（表1）。其中：編號f1~f10的特征為空域特征^[1，5]；f11~f18為基于空間灰度共生矩陣的紋理特征^[6]；f19~f20為基于離散余弦變換（DCT）的頻域特征^[7]。

使用WM-IA算法對MC初始特征集進(jìn)行優(yōu)化。其中：L=20，mi是表1中第fi個(gè)特征，N=100，M=5，n=10，Pe=0.008，k=1，K(·，·）分別使用多項(xiàng)式（p=3）和高斯徑向基函數(shù)（σ=2.5），收斂條件為g=100或者連續(xù)三次迭代過程中記憶池的抗體無變化。

23結(jié)果與分析

經(jīng)過多次反復(fù)實(shí)驗(yàn)，產(chǎn)生的部分抗體結(jié)果如表2所示，單個(gè)特征的選擇概率分布如圖2所示。

表2中的前三組是使用式（4）時(shí)產(chǎn)生的部分抗體，后兩組是使用式（5）產(chǎn)生的部分抗體。當(dāng)使用不同的K（·，·)時(shí)，其特征選擇的結(jié)果不盡相同，如f2，f11，f12等均被選擇，f1，f5，f10，f13，f16，f17，f19等均未被選擇，而其他特征的選擇結(jié)果不一致。使用式（4）計(jì)算時(shí)，前三組抗體的親和力明顯大于后兩組；使用式（5）計(jì)算時(shí)，前三組的親和力遠(yuǎn)小于后兩組，說明特征選擇與K（·，·）相關(guān)。由圖2可知，具有高分類水平的特征主要有： f2，f3，f4，f6，f7，f11，f12，f14，f15，f18，f20。該結(jié)果與文獻(xiàn)[1， 3]的結(jié)果部分相同，但結(jié)果集更小，更有利于計(jì)算。

3結(jié)束語

本文運(yùn)用生物變異原理設(shè)計(jì)了一種加權(quán)變異免疫算法，并使用該算法對MC的特征集進(jìn)行優(yōu)化，優(yōu)化后的結(jié)果與經(jīng)驗(yàn)特征集部分重合，同時(shí)也選擇了一些經(jīng)驗(yàn)特征，使得特征集更加精簡、有效。該算法考慮到傳統(tǒng)隨機(jī)變異的局限性，引入變異率權(quán)值并根據(jù)抗體穩(wěn)定/非穩(wěn)定部位動(dòng)態(tài)調(diào)節(jié)，有效地增強(qiáng)了搜索目的性。此外，借鑒了SVM在特征空間中求取分類超平面的思想，抗體的親和力在其特征空間中進(jìn)行計(jì)算，并通過核函數(shù)實(shí)現(xiàn)。該特征選擇方法利用了免疫算法的并行、全局快速收斂等特點(diǎn)，是一種可靠的特征選擇方法。進(jìn)一步的工作需要使用更多的乳腺X線照片數(shù)據(jù)庫進(jìn)行實(shí)驗(yàn)，也可以從算法的通用性方面加以改進(jìn)。

參考文獻(xiàn)：

［1］FU J C， LEE S K， WONG S T C， et al. Image segmentation feature selection and pattern classification for mammographic microcalcifications[J].Computerized Medical Imaging and Graphics，2005，29(6):419-429.

[2]ZHANG P， VERMA B， KUMAR K. Neural vs. statistical classifier in conjunction with genetic algorithm based feature selection[J].Pattern Recognition Letters， 2005，26(7):909-919.

[3]王瑞平， 萬柏坤， 高上凱. 使用遺傳算法的乳腺微鈣化點(diǎn)特征優(yōu)化[J]. 電子科技大學(xué)學(xué)報(bào)， 2007，36(1):137-139，153.

[4]PAPADOPOULOS A， FOTIADIS D I， LIKAS A. Characterization of clustered microcalcifications in digitized mammograms using neural networks and support vector machines[J].Artificial Intelligence in Medicine，2005，34(2):141-150.

[5]YANG Y S， LING G. A CAD system for the automatic detection of clustered microcalcifications in digitized mammogram films[J]. IEEE Trans on Medical Imaging，2000，19(2):115-126.

[6]HARALICK R M， SHANMUGAN K， DINSTEIN I. Textural features for image classification[J].IEEE Trans on Systems， Man and Cybernetics， 1973，3(6):610-621.

[7]MESTER R， FRANKE U. Spectral entropy-activity classification in adaptive transform coding[J]. IEEE Journal on Selected Areas in Communications， 1992，10(5): 913-917.