殷櫻　張玉冰　劉家誠(chéng)　高昆

摘要：多數(shù)傳統(tǒng)的屬性聚類算法不能直接處理連續(xù)型屬性，為了避免連續(xù)數(shù)據(jù)離散化處理時(shí)造成的信息損失，降低樣本屬性鄰域求解的復(fù)雜度，提高特征基因提取的效率。文中提出一種將鄰域互信息用于屬性聚類的特征基因選擇方法，用于在海量的基因表達(dá)譜數(shù)據(jù)中挖掘出少量的具有分類識(shí)別能力且冗余度較小的特征基因。

關(guān)鍵詞：粒計(jì)算；鄰域互信息；屬性聚類；基因選擇

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）04-0821-03

1 概述

基于屬性約簡(jiǎn)算法的特征基因選擇是為了獲得一組基因數(shù)量盡可能小而分類能力卻盡可能強(qiáng)的特征基因子集。對(duì)于傳統(tǒng)的屬性聚類算法[1]，依據(jù)信息熵作為相關(guān)度，將屬性分成不同的簇，然而，多數(shù)聚類算法不能直接處理連續(xù)型屬性。當(dāng)需要處理連續(xù)型屬性時(shí)，通常的做法是將連續(xù)數(shù)據(jù)離散化[2]，而離散化會(huì)導(dǎo)致信息丟失，使選出的特征基因子集的分類準(zhǔn)確率較其他方法不高。

基于粒計(jì)算的特征基因提取方法是在鄰域互信息和聚類的基礎(chǔ)上提出的，結(jié)合最小冗余度，最大相關(guān)的方法，進(jìn)行屬性約簡(jiǎn)。對(duì)樣本基因進(jìn)行K均值聚類，聚成十類，形成十個(gè)簇。利用鄰域互信息作為相關(guān)性度量，選擇出每一個(gè)簇的模式，用于進(jìn)一步基因選擇。鄰域互信息的方法不需要對(duì)連續(xù)數(shù)據(jù)進(jìn)行離散化處理，避免了信息損失，同時(shí)，提高了特征基因子集提取的效率。

2 鄰域互信息和K均值方法

2.1 鄰域互信息

定義2.1 對(duì)于任何一個(gè)樣本，其[δ]鄰域?yàn)閇3]：

[δ（xi）=x|x∈Gene，Δ（x，xi）≤δ] （1）

定義2.2 第[i]樣本的鄰域互信息[NMIδ（R；S）]為[4]：

[NMIδ（R；S）=-1ni=1nlog||δR（xi）||?||δS（xi）||n||δS?R（xi）||] （2）

其中[δR（xi）]，[δS（xi）]分別是[xi]在屬性集合[R]與[S]上的[δ]鄰域，[δR?S（xi）]是[xi]在屬性集合[R?S]上的鄰域，‖X‖是集合[X]的基。

算法1：鄰域互信息

Step1：對(duì)整個(gè)基因組數(shù)據(jù)[Gene=x1，x2，…xn]，[xi]表示第[i]個(gè)樣本[（i=1…n）]，[n]表示樣本個(gè)數(shù)；

Step2：[Fj]表示屬性集合[（j=1，…，9217），][R]表示第[i]個(gè)樣本的所有屬性，[S]表示整個(gè)的所有屬性，根據(jù)式子得到第[i]樣本的鄰域互信息[NMIδ（R；S）]；

Step3：對(duì)第[i]樣本的鄰域互信息[NMIδ（R；S）]進(jìn)行歸一化處理，得到歸一化之后的數(shù)據(jù)[NMIδ]。

2.2 K均值算法描述

給定一個(gè)包含[n]個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)，以及要生成簇的數(shù)目[k]，隨機(jī)選取[k]個(gè)對(duì)象作為初始的[k]個(gè)聚類中心；然后計(jì)算剩余各個(gè)樣本到每一個(gè)聚類中心的距離，把該樣本歸到離它最近的聚類中心所在的類，對(duì)調(diào)整后的新類使用平均值的方法計(jì)算新的聚類中心；如果相鄰兩次的聚類中心沒(méi)有任何變化，說(shuō)明樣本調(diào)整結(jié)束且聚類平均誤差準(zhǔn)則函數(shù)已經(jīng)收斂[5][6]。

算法2：劃分并計(jì)算基于簇中對(duì)象的平均值[7]

輸入：簇的數(shù)目[k]和包含[n]個(gè)對(duì)象的數(shù)據(jù)庫(kù)

輸出：平方誤差總和最小條件下的[k]簇

Step1：選擇[k]個(gè)樣本作為初始凝聚點(diǎn)（聚類種子），或者將所有樣本分成[k]個(gè)初始類，然后將[k]個(gè)類的重心（均值）作為初始凝聚點(diǎn)；

Step2：對(duì)除凝聚點(diǎn)之外的所有樣品逐個(gè)歸類，將每個(gè)樣品歸入離它最近的凝聚點(diǎn)所在的類，該類的凝聚點(diǎn)更新為這一類目前的均值，直至所有樣品都?xì)w了類；

Step3：重復(fù)步驟2；

Step4：直至所有的樣品不能再分配為止。

[K]均值算法的工作過(guò)程說(shuō)明如下[8]：首先從[n]個(gè)數(shù)據(jù)對(duì)象任意選擇[k]個(gè)對(duì)象作為初始聚類中心；而對(duì)于所剩下其它對(duì)象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后再計(jì)算每個(gè)所獲新聚類的聚類中心（該聚類中所有對(duì)象的均值）；不斷重復(fù)這一過(guò)程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開(kāi)始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù)。[k]個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開(kāi)。

3 屬性相關(guān)度的聚類算法

定義3.1 設(shè)某個(gè)樣本的單個(gè)屬性為[Fj]，[Fk]與[Fh]，[h≠k≠j]，[j，k，h∈（1，...，9217）]。在第[i]個(gè)樣本里[Fj]表示[j]個(gè)屬性，[Fk]表示第[k]個(gè)屬性，[Fh]表示第[h]個(gè)屬性，則[Fj]與[Fk]相關(guān)度為：

[NRδ（Fj；Fk）=NMIδ（Fj；Fk）NHδ（Fj，F(xiàn)k）] （3）

其中，[NMIδ（Fj；Fk）]為屬性[Fj]與[Fk]的鄰域互信息，[NHδ（Fj，F(xiàn)k）]為屬性[Fj]與[Fk]的聯(lián)合鄰域信息熵。

[NMIδ（Fj；Fk）]度量了已知[Fk]對(duì)于了解[Fj]不確定性的平均減少量。如果[NMIδ（Fj；Fk）>NMIδ（Fj；Fh）]，則[Fj]與[Fk]的相關(guān)度要大于[Fj]與[Fh]的相關(guān)度。當(dāng)[NHδ（Fj，F(xiàn)k）=1]時(shí)，[Fj]與[Fk]嚴(yán)格相關(guān)；當(dāng)[NHδ（Fj，F(xiàn)k）=0]時(shí)，則[Fj]與[Fk]在統(tǒng)計(jì)上獨(dú)立。而當(dāng)[0

定義3.2 設(shè)屬性[Fj]在簇[C=Fj|1，…，9217]中，則[Fj]對(duì)于簇[C]的顯著多元相關(guān)度定義為：

[MNRδ（Fj）=j=1pNRδ（Fj；Fk）] （4）

其中，[NRδ（Fj；Fk）]為屬性[Fj]與[Fk]的相關(guān)度。

定義3.3 設(shè)屬性[Fj]在簇[C=Fk|1，…，9217]中，如果[MNRδ（Fj）≥MNRδ（Fk）]，[k∈1，…，9217]，則簇[C]的模式[η（C）]為[Fj]。

可見(jiàn)，簇[C]的模式[η（C）]是簇中顯著多元相關(guān)度最大的屬性?；卩徲蚧バ畔⒌奶卣骰蚓垲愃惴ň褪抢绵徲蚧バ畔⒆鳛橄嚓P(guān)性度量，結(jié)合[K]均值算法，將各屬性聚類成簇，選擇出簇的模式，用于進(jìn)一步基因選擇。

算法3：屬性相關(guān)度

Step1：對(duì)第[i]樣本基因的[NMIδ]進(jìn)行[K]均值聚類算法，聚成10類，每個(gè)類是一個(gè)簇，[Cii（ii=1，…，10）]表示第[i]個(gè)樣本的第[ii]個(gè)簇；

Step2：[Cii]中有[m]個(gè)屬性，得到[η（Cii）]，則[η（C）]表示第[i]個(gè)樣本的第[ii]個(gè)簇的模式。

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證該算法的有效性，該文采用了UCI數(shù)據(jù)庫(kù)中3個(gè)常用的標(biāo)準(zhǔn)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)（如表1所示）。

在表1中，乳腺癌數(shù)據(jù)集Breast[16]有84個(gè)樣本和9216個(gè)基因表達(dá)數(shù)據(jù)。Golub等人公布的急性白血病數(shù)據(jù)集Leukemia[17]共有72個(gè)急性白血病樣本，每個(gè)樣本均含7129個(gè)基因的表達(dá)數(shù)據(jù)。結(jié)腸癌數(shù)據(jù)集Colon[18]是在1999年由Alon描述和在網(wǎng)上提供下載，該數(shù)據(jù)集共有62個(gè)樣本和2000個(gè)基因表達(dá)數(shù)據(jù)。

根據(jù)以上算法，通過(guò)篩選得到的聚類劃分圖像如圖1所示：

在聚類劃分的圖像中，縱坐標(biāo)表示劃分的十個(gè)簇的序號(hào)，橫坐標(biāo)表示數(shù)據(jù)歸一化之后屬性的數(shù)值分布，以0為界限，如果屬性分布接近于1，則劃分比較完善。否則，需要通過(guò)修改劃分的簇?cái)?shù)目（分類精度）來(lái)調(diào)整聚類劃分的良好性。

同時(shí)，我們選擇基因數(shù)據(jù)集中的前兩組基因樣本，利用鄰域互信息和聚類的方法進(jìn)行逐一篩選，并求出每個(gè)篩選結(jié)果的相關(guān)度，統(tǒng)計(jì)得到的數(shù)據(jù)表格如表2所示：

5 結(jié)束語(yǔ)

本文在基于鄰域互信息和屬性聚類劃分的基礎(chǔ)上，提出了在K均值中的鄰域求解方法，該方法通過(guò)鄰域相關(guān)度、分類精度、冗余度等特征值選擇出具有代表性的特征基因，此方法不僅降低了樣本屬性鄰域求解的復(fù)雜度，還提高了特征基因提取的效率。

參考文獻(xiàn)：

[1] 胡清華，趙輝，于仁達(dá).基于鄰域粗糙集的符號(hào)與數(shù)值屬性快速約簡(jiǎn)算法[J].模式識(shí)別與人工智能，2008，21（6）：732-738.

[2] 胡清華，于仁達(dá)，謝宗霞.基于鄰域?；痛植诒平臄?shù)值屬性約簡(jiǎn)[J].軟件學(xué)報(bào)，2008，19（3）.

[3] 秦奇?zhèn)?，梁吉業(yè)，錢宇華.一種基于鄰域距離的聚類特征選擇方法[J].計(jì)算機(jī)科學(xué)，2012（1）.

[4] 謝娟英，李楠，喬子芮.基于鄰域粗糙集的不完整決策系統(tǒng)特征選擇算法[J].南京大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（4）.

[5] 謝娟英，郭文娟，謝維信.基于鄰域的K中心點(diǎn)聚類算法[J].陜西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2012（4）.

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

[7] 劉靖明，韓麗川，侯立文.一種新的聚類算法——粒子群聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2005（20）.

[8] 周才英，黃龍軍.模糊K-Prototype聚類算法初始點(diǎn)選取方法的改進(jìn)[C]//2010國(guó)際信息技術(shù)與應(yīng)用論壇論文集，2010.