改進型K-Means算法在腸癌病理圖像分割中的應用

,,

(浙江工業(yè)大學 計算機科學與技術學院，浙江 杭州 310023)

大腸癌的病發(fā)率呈逐年上升趨勢，大腸癌患者的平均五年存活率僅為四成左右[1].因此，大腸癌的識別對臨床診斷和治療至關重要.目前，大腸癌臨床診斷最可靠的方法是通過對患者的大腸病理切片圖像進行病理性診斷[2].在現(xiàn)階段，往往依靠病理專家的主觀經驗進行診斷，這種方法受病理專家的水平影響，且經驗豐富的病理專家集中在少數(shù)大型醫(yī)院，使許多中小醫(yī)院無法開展該項工作.隨著模式識別、人工智能和數(shù)字圖像分析技術的發(fā)展，計算機輔助技術已經越來越受到關注，利用該技術進行病變細胞識別分類也取得了一定研究成果，如胃癌[3]、肺癌[4]和肝癌[5]的識別分類等.大腸病理切片圖像分割技術是基于計算機輔助技術的大腸癌識別分類的關鍵技術，為識別難度較高的腸癌診斷奠定了一定的技術基礎.

K-Means算法是比較成熟的一種聚類分析的方法，已被廣泛應用到數(shù)據(jù)挖掘、機器學習和遙感圖像等領域.研究證明[6-7]：初始聚類中心的選取是進行聚類算法非常重要的一部分，它直接影響聚類的結果.根據(jù)大腸癌細胞判別的病理學診斷指標，對使用聚類分析法進行大腸病理切片圖像分割進行了探索，針對傳統(tǒng)聚類分析中確定初始中心的難點，提出了一種改進型K-Means大腸癌病理切片圖像分割算法，對后續(xù)的大腸病理切片圖像特征提取以及相似癌癥識別分類技術具有至關重要的意義.

1 K-Means算法

設有由n個m維數(shù)據(jù)構成的數(shù)據(jù)集X={xi|xi∈Rm,i=1,2,…,n}，將X劃分為由K個聚類集構成的集合C={ck|k=1,2,…,K}，且每個聚類集之間的數(shù)據(jù)具有較高相似性，不同聚類集之間的數(shù)據(jù)彼此相差較大.常用的聚類方法有多種，K-Means算法是應用廣泛的基于劃分的一種聚類方法，這種方法的K值確定，適合處理數(shù)據(jù)量較大的數(shù)據(jù)集，且更易發(fā)現(xiàn)球形類.

K-Means算法的核心思想是：選定K個數(shù)據(jù)作為數(shù)據(jù)集的初始中心；對于其余每個數(shù)據(jù)，根據(jù)該數(shù)據(jù)到初始中心的距離，選定距離該數(shù)據(jù)最近的類作為它的歸屬類；重新計算K個類的初始中心，重新確定每個數(shù)據(jù)的歸屬類，不斷重復這個過程，直至初始中心不再變更.

常用的計算距離主要有Minkowski distance,Euclidean distance,CityBlock distance三種方法，Minkowski distance方法的計算公式為

(1)

式中λ取任意值.Euclidean distance方法的公式對應式(1)λ取2，其計算公式為

(2)

CityBlock distance方法的公式對應式(1)λ取1，其計算公式為

(3)

使用式(1—3)進行聚類時，數(shù)據(jù)集分別以星形、圓形和菱形方式逼近中心.研究對象是以接近圓形的腺體為主，因此選用Euclidean distance方法式(2)計算距離.

使用K-Means算法時要確定類別數(shù)，研究的大腸病理切片圖像是大腸組織樣本經過蘇木精—伊紅染色法(Hematoxylin-eosin staining，HE染色法)染色之后得到的大腸病理切片圖.正常的大腸病理切片圖像中，有意義的物質主要有三類，分別是腺腔和上皮細胞、細胞核、間質.因此，聚類分析的類別數(shù)K=3.

傳統(tǒng)K-Means算法確定初始中心主要使用隨機方法或平均方法，隨機方法隨機選擇某一個或某幾個數(shù)據(jù)點作為初始中心，平均方法計算數(shù)據(jù)集的平均數(shù)據(jù)點作為初始中心.傳統(tǒng)計算初始中心方法確定的初始中心并不能較好地代表數(shù)據(jù)集，具有隨機性和不確定性.而聚類初始中心對聚類過程有十分重要的影響，使用傳統(tǒng)方法確定的初始中心因其較差的代表性，使得聚類收斂過程緩慢，聚類后的結果往往不理想.

2 主成分分析

主成分分析(PCA)是常用的分析、挖掘和簡化數(shù)據(jù)技術，它的實質是對數(shù)據(jù)集進行線性變換到另一空間，在新空間下借助主成分或者少數(shù)的幾個成分概括關系復雜的數(shù)據(jù)信息量.PCA有效簡化了數(shù)據(jù)集[7]，便于分析，被廣泛地應用到了金融統(tǒng)計和神經科學等領域[8].

圖像分割是主成分分析重要的應用方向之一，主成分分析通常將一幅圖像經過線性變換到另一個空間，在變換后的空間提取特征值.對數(shù)據(jù)集進行主成分分析時，協(xié)方差矩陣和相關系數(shù)矩陣是常用的計算工具.協(xié)方差矩陣適用于單個數(shù)據(jù)指標方差大的一類數(shù)據(jù)集上，而相關系數(shù)矩陣剝離了單個數(shù)據(jù)指標的方差，適用于相關數(shù)據(jù)指標多、數(shù)據(jù)指標之間的相關程度高數(shù)據(jù)集上[8].使用主成分分析時，若數(shù)據(jù)集經過了標準化，則得到的矩陣便是協(xié)方差矩陣.使用主成分分析目的是選取具有代表性的聚類初始中心，應避免單個數(shù)據(jù)指標方差對分析產生的影響，所以使用相關系數(shù)矩陣進行主成分分析.

在一個m維空間中，設定它的中心為

(4)

將空間中的數(shù)據(jù)標準化，即將原始數(shù)據(jù)樣本處理成樣本均值為0和樣本方差為1的標準化數(shù)據(jù).現(xiàn)將位于該空間中一點投影變換到一個向量上，設定ω為m維投影向量，且滿足ωωΤ=1，得到投影變換后的方差為

(5)

ωCωΤ-λ(1-ωωΤ)

(6)

將式(6)對ω求導并使之為0，可得方差最大化的條件為

CωΤ=λωΤ

(7)

式(7)取得最大值時，λ為C的最大特征值，ω為最大特征值對應的特征向量.

上述過程實現(xiàn)了數(shù)據(jù)集的降維和簡化，以有效信息丟失最少的原則下，通過線性變換保留對應特征值最大的部分，舍棄其他無效或僅包含少量有效信息部分得到變換后的主成分.主成分分析方法得到的最大特征值對應的成分為第一主成分，第一主成分在數(shù)據(jù)空間集上的方差最大，負載的信息量最大，延伸空間最長.根據(jù)大腸病理切片圖像特點，將第一主成分平均分成三個區(qū)間，分別代表腺腔和上皮細胞、細胞核、間質三類物質，取三個區(qū)間的中間點作為聚類的初始中心.使用此方法確定的初始中心較傳統(tǒng)方法確定的初始中心更具有代表性，且在后階段聚類中提高了收斂速度.

3 改進型K-Means大腸病理切片圖像分割算法

對由大腸病理切片圖像使用PCA求取聚類初始中心，之后使用K-Means算法進行聚類，最終實現(xiàn)大腸病理切片圖像分割，假設該矩陣為

(8)

X中的每一個行向量代表一個樣本數(shù)據(jù)，但RGB空間維度相關性比較大，難以選出具有代表性的三類初始中心，同時考慮到該數(shù)據(jù)集數(shù)據(jù)量龐大，難以實現(xiàn)特征提取，根據(jù)PCA理論將其變換到另一個更適合的維度，產生新的矩陣為Y=ωX.

將式(8)中X中每個元素減去對應每列均值得到標準化后矩陣Z，得到相關系數(shù)矩陣為

(9)

計算得到Cx特征值，并將特征值按遞減排序，對應特征向量矩陣為υ∈R3×3.變換后的新矩陣為Y=υZ∈RN×3，第一列稱為主維度，第一列向量為主向量.Vmax和Vmin分別表示主向量中最大與最小值，將主向量分為K段，每段長度為

(10)

第i段的范圍區(qū)間為

[d=Vmax+(i-1)d,Vmin+id) 1≤i≤K

(11)

對于Y中的每一個樣本數(shù)據(jù)，根據(jù)其主維度值歸類到對應列.對于每個類，求出其均值中心，得到由K個類的中心構成的矩陣為M.

將M變換至原坐標得到K個初始聚類中心構成的矩陣為

(12)

確定初始中心之后，將樣本數(shù)據(jù)進行K-Means聚類分析，其中計算距離時使用式(2)Euclidean distance公式.具體的算法步驟為：

1) 根據(jù)上述算法確定初始中心為Z1(0),Z2(0),…,ZK(0)，括號中的值表示迭代次數(shù).

2) 對于第T次迭代，對于除聚類中心之外的數(shù)據(jù)，根據(jù)該點到初始中心的距離確定該點屬于的類.

3) 利用均值的方法確定第T+1次迭代的初始中心為Z1(T+1),Z2(T+1),…,ZK(T+1).

4) 如果聚類中心與原聚類中心重合，即Zj(T)=Zj(T+1)，且在一定次數(shù)內收斂，則完成聚類，停止；否則，跳至第(2)步重復.

4 實驗結果與分析

為充分驗證提出算法的有效性，選取一張具有代表性的大腸病理切片圖像進行分割處理，同時將算法與Lab聚類算法處理結果進行對比.

圖1為一張正常的大腸病理切片圖.本實驗的圖像樣本是將大腸組織經過蘇木精—伊紅染色法染色獲取的圖像，圖中形狀近似圓形、輪廓清晰且排列有序的是大腸腺體，腺腔和上皮細胞分布于其中，間質分布于其間，而細胞核分布于腺體邊緣和其間.正常的大腸病理切片圖中細胞分布均勻、排列有序且細胞核與上皮細胞明顯.而癌變的大腸病理切片圖中細胞分布散亂、排列無序且細胞核與上皮細胞均消失.

圖1 大腸病理切片原圖

使用聚類算法處理圖1所示大腸病理切片原圖，得到聚類結果.聚類圖中藍色代表腺腔和上皮細胞，紅色代表細胞核，綠色代表間質.圖2(a)為使用提出的改進型K-Means聚類算法對原圖進行處理得到的實驗結果.Lab聚類算法是一種常用的聚類分割算法，該算法將彩色圖像變換至Lab色彩空間，并去除代表亮度的L空間信息，再對變換后的結果進行K-Means聚類算法處理.作為對比，使用Lab聚類算法對圖1所示原圖進行聚類，得到實驗結果如圖2(b)所示.

圖2 聚類處理后的結果圖

由實驗對比結果可看出:Lab聚類算法處理結果丟失了大腸病理切片圖中存在于大腸腺體中的腺腔和上皮細胞、間質的信息，這是大腸癌病理識別診斷中最關鍵的特征之一.同時，Lab聚類算法處理破壞了大腸病理切片圖中大腸腺體的形狀特征，出現(xiàn)了腺體重疊、輪廓不清晰等問題，因此Lab聚類算法造成了過分割的結果.改進型K-Means算法處理結果保留了正常大腸病理切片圖中細胞分布均勻、排列有序且細胞核與上皮細胞明顯的特征，同時腺體輪廓清晰，沒有出現(xiàn)腺體重疊的現(xiàn)象.

改進型K-Means算法在具備有效性的前提下，由于使用PCA方法確定初始中心，相比于使用RANDOM方法確定初始中心的傳統(tǒng)K-Means算法，具有收斂速度快的優(yōu)勢.傳統(tǒng)K-Means選定初始中心使用隨機選取的方法，確定的初始中心不能很好代表數(shù)據(jù)集，并有可能對收斂過程造成不良影響，這體現(xiàn)在使用RANDOM方法的傳統(tǒng)聚類算法比使用PCA方法的算法的收斂時間更長.

為比較收斂時間，選取20，50，100幅大小為351×351的彩色大腸病理切片圖像，分別使用提出的PCA方法與傳統(tǒng)RANDOM方法進行收斂時間對比.

本實驗在Intel(R) Core(TM) i7-4650U 1.70 ～2.30 GHz的PC機上實現(xiàn)，實驗結果如表1所示.

表1 PCA方法與RANDOM方法收斂時間對比結果

綜上所述，使用提出的改進型K-Means大腸病理圖像分割算法有效地提取并突出了大腸病理切片中的腺腔和上皮細胞、細胞核、間質的顏色特征，同時對比于傳統(tǒng)RANDOM方法具有收斂速度快的特點.

5 結 論

基于PCA和K-Means算法的大腸病理切片圖像分割算法，將大腸病理切片圖像中的腺腔和上皮細胞、細胞核、間質進行分類.通過使用基于相關系數(shù)矩陣的主成分分析法降低了數(shù)據(jù)復雜度，確定了具有代表性的聚類初始中心，再使用K-Means算法，將病理切片圖像中的數(shù)據(jù)聚分成三類.與Lab聚類算法相比，改進型K-Means算法更準確地將大腸病理切片圖像分割，而且使用PCA方法確定初始中心在收斂速度上優(yōu)于RANDOM方法.改進型K-Means算法實現(xiàn)高效簡單，為后續(xù)的特征提取奠定了良好的基礎.

參考文獻：

[1] SIEGEL R, NAISHADHAM D, JEMAL A. Cancer statistics[J]. A Cancer Journal for Clinicians,2013,63(1):11-30.

[2] SADANANDAM A, LYSSIOTIS C A, HOMICSKO K, et al. A colorectal cancer classification system that associates cellular phenotype and responses to therapy[J]. Nature Medicine,2013,19(5):619-625.

[3] CHANG K H, MILLER N, KHEIRELSEID E A H, et al. MicroRNA signature analysis in colorectal cancer:identification of expression profiles in stage II tumors associated with aggressive disease[J]. International Journal of Colorectal Disease,2011,26(11):1415-1422.

[4] SUN S, BAUER C, BEICHEL R. Automated 3-D segmentation of lungs with lung cancer in CT data using a novel robust active shape model approach[J]. Medical Imaging, IEEE TransActions on,2012,31(2):449-460.

[5] 凌華強,龍勝春,項鵬遠.主動形體模型法在肝臟CT圖像分割中的應用[J].浙江工業(yè)大學學報,2012,40(4):450-453.

[6] ALRABEA A, SENTHILKUMAR A V, AL-SHALABI H, et al. Enhancing k-means algorithm with initial cluster centers derived from data partitioning along the data axis with PCA[J]. Journal of Advances in Computer Networks,2013,1(2):137-142.

[7] 古輝,王益義.一種基于模板匹配的船銘牌字符分割方法[J].浙江工業(yè)大學學報,2010，38(1):33-35.

[8] 朱永忠,姚燁,張艷.基于主成分分析和Logistic回歸的上市公司財務困境預警模型的研究[J].浙江工業(yè)大學學報,2012,40(6):692-694.

[9] CAMPBELL M C, MARKHAM J, FLORES H, et al. Principal component analysis of PiB distribution in parkinson and alzheimer diseases[J]. Neurology,2013,81(6):520-527.

[10] NUMPACHAROEN K, ATSAWARUNGRUANGKIT A. Generating correlation matrices based on the boundaries of their coefficients[J]. PloS One,2012,7(11):e48902.