殷櫻　張玉冰　劉家誠　高昆

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）04-0821-03

1 概述

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

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

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

2.1 鄰域互信息

定義2.1 對于任何一個樣本，其[δ]鄰域為[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：對整個基因組數(shù)據(jù)[Gene=x1，x2，…xn]，[xi]表示第[i]個樣本[（i=1…n）]，[n]表示樣本個數(shù)；

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

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

2.2 K均值算法描述

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

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

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

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

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

Step2：對除凝聚點之外的所有樣品逐個歸類，將每個樣品歸入離它最近的凝聚點所在的類，該類的凝聚點更新為這一類目前的均值，直至所有樣品都歸了類；

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

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

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

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

定義3.1 設(shè)某個樣本的單個屬性為[Fj]，[Fk]與[Fh]，[h≠k≠j]，[j，k，h∈（1，...，9217）]。在第[i]個樣本里[Fj]表示[j]個屬性，[Fk]表示第[k]個屬性，[Fh]表示第[h]個屬性，則[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]對于了解[Fj]不確定性的平均減少量。如果[NMIδ（Fj；Fk）>NMIδ（Fj；Fh）]，則[Fj]與[Fk]的相關(guān)度要大于[Fj]與[Fh]的相關(guān)度。當[NHδ（Fj，F(xiàn)k）=1]時，[Fj]與[Fk]嚴格相關(guān)；當[NHδ（Fj，F(xiàn)k）=0]時，則[Fj]與[Fk]在統(tǒng)計上獨立。而當[0

定義3.2 設(shè)屬性[Fj]在簇[C=Fj|1，…，9217]中，則[Fj]對于簇[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]。

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

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

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

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

4 實驗結(jié)果與分析

為了驗證該算法的有效性，該文采用了UCI數(shù)據(jù)庫中3個常用的標準數(shù)據(jù)集作為實驗數(shù)據(jù)（如表1所示）。

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

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

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

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

5 結(jié)束語

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

參考文獻：

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

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

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

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

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

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

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

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