模式識別問題中特征提取和特征選擇是一個重要問題。基于向量的幾何代數表示方法,提出了一種新的幾何代數片積系數特征提取方法,并對其中存在的維數升高問題進行了研究,提出了改進的微分進化特征選擇方法。本文分類器采用線性判別分析,以公開的乳腺癌生物醫學數據集進行10折交叉驗證(10 CV),得到的分類結果超過了96%,優于原始特征和傳統特征提取方法下的分類性能。
引用本文： 李靜, 洪文學. 乳腺癌數據的幾何代數特征提取和微分進化特征選擇研究. 生物醫學工程學雜志, 2014, 31(6): 1218-1222,1228. doi: 10.7507/1001-5515.20140231 復制
引言
近年來乳腺癌的發病率一直處于增長態勢，隨著診斷和治療手段的進步，乳腺癌患者的長期存活率一直在提高[1]。影響預后的關鍵問題是乳腺癌的早期檢測和正確診斷。毫無疑問，癌癥患者的醫學數據和專家決策是癌癥診斷中最重要的因素，因此特征提取和分類是醫療診斷系統中的研究重點。事實上，基于醫學數據和計算機模式識別技術可以幫助疲勞的專家或者經驗不足的醫生在更短時間內做出決策，并盡可能減少決策錯誤[2-3]。
眾所周知，對原始數據或提取特征進行分類是一個通用方法。但是目前特征提取方法對變量間高階關聯闡述不清楚。我們發表的論文利用高維數據的兩個變量間的關聯特征，如面積或重心，在某些真實數據集的最佳分類性能優于或相當于國際報道的分類性能最優值[4-5]。基于幾何代數理論[6-7]，研究者認為高維數據的兩個變量間的面積或重心特征是幾何代數多重向量表示中的階數(grade)為2的片積(blade)系數，是幾何代數子空間中變量間組合信息，體現了變量間高階關聯和幾何直觀性。本文提出了高維數據的幾何代數特征提取和微分進化(differential evolution,DE)特征選擇方法。首先將高維數據特征經過二次映射方法升維到幾何代數子空間[4-5]，在幾何代數子空間利用微分進化方法進行最優特征選擇。實際上這是一個先提取、后選擇的過程。經過升維變換后，原始數據的1階向量特征擴展為幾何代數子空間中的多級高階幾何特征，這樣可以充分利用原始數據變量間的高階關聯信息。分類器采用簡單的線性判別分析。以乳腺癌生物醫學數據集驗證的實驗結果表明，基于本文新方法的分類性能優于原始特征和傳統特征提取的分類性能。
1 幾何代數特征提取方法
幾何代數(又叫Clifford代數)是一種描述幾何對象并可進行幾何計算的統一性語言。幾何代數是復代數和四元數代數的超集。幾何代數通過多重向量(multi-vector)和幾何積(geometrical product)兩個核心概念可以進行子空間的表示和幾何計算[8]。幾何代數的運算對象和運算結果都具有明顯的幾何含義，表示多維數據的各級子空間。
1.1 幾何代數多重向量表示
首先，建立高維數據向量表示和幾何代數多重向量表示之間的映射關系模型。映射關系是由三個域--向量表示域、映射域和幾何代數多重向量表示域以及4個變換器--向量變換器、映射器、幾何代數多重向量變換器和逆映射器組成。向量變換器是在向量表示域間實現向量到向量的變換，如數據的預處理和特征提取等。映射器功能是將向量表示映射到幾何代數多重向量表示。幾何代數多重向量變換器功能是實現幾何代數多重向量之間的變換。逆映射器功能是將幾何代數多重向量表示映射到向量表示。
以三維向量空間為例，若其標準正交基為{e1,e2,e3}，則其幾何代數G(E3)為一個8維的向量空間，其基為{1,e1,e2,e3,e1e2,e2e3,e3e1,e1e2e3}，其中1為0階片積(標量)，e1,e2,e3為1階片積，e1e2,e2e3,e3e1為2階片積，e1e2e3為3階片積。例如三維向量xi=[xi1,xi2,xi3]T可表示為xiC=s+xi1e1+xi2e2+xi3e3+xi12e12+xi13e13+xi23e23+xi123e123幾何代數多重向量形式，其中s=1，xi1,xi2,xi3等于原來值，其它片積系數待定。k-階片積相當于k級子空間，具有明顯的幾何含義，例如2階片積相當于一個有向的面元，3階片積相當于一個有向的體元。
1.2 幾何代數特征提取原理
利用幾何代數可提取高維數據的高階幾何特征。線性無關的d個向量a1,…,ad(d≤n)具有的最高階次片積為d-片積。d-片積的線性組合表示為
| $\sum\limits_{I\in {{\Phi }_{d}}}{{{w}_{I}}{{e}_{I}}},{{\Phi }_{d}}=\{{{i}_{1}},{{i}_{2}},\ldots ,{{d}_{d}}|1\le {{i}_{1}}＜\ldots ＜{{i}_{d}}\le n\}$ |
d個向量的幾何積為
| ${{a}_{1}}\ldots {{a}_{d}}\in \left\{ \begin{align} & {{\Omega }_{n}}^{1}\oplus \ldots \oplus {{\Omega }_{n}}^{d-2}{{\oplus }^{\wedge d}}{{R}^{n}}(odd~d) \\ & {{\Omega }_{n}}^{0}\oplus \ldots \oplus {{\Omega }_{n}}^{d-2}{{\oplus }^{\wedge d}}{{R}^{n}}(even~d) \\ \end{align} \right.$ |
假定現有一組空間向量ξ={pl∈Rn,l=1,…,m}，特征提取方法如下：
令n′=min{n,m}，對于d=1,…,n′
| $\begin{align} & {{f}_{d}}(\xi )=\{＜{{p}_{l}}\ldots {{p}_{l+k-1}}{{e}_{l}}^{-1}＞,I\in {{\Phi }_{d}},l=1,\ldots ,n-d+1\} \\ & \in {{R}^{\left( m-d+1 \right)|{{\Phi }_{d}}|}}, \\ \end{align}$ |
其中<·>表示選擇標量運算。|Φd|為從n個元素中選擇d個元素的組合數目。eI-1為eI逆。
1.3 幾何代數片積的特征提取方法
設d維向量空間標準正交基為e1,e2,…,ed，則這d個基向量張成了幾何代數d階片積子空間。可以看出1階片積系數是原始特征，那么2階片積系數可以是對應的1階片積的幾何積系數，高階片積系數類似。因此高階片積系數是樣本變量間高階關聯的體現。
樣本的向量表示可以映射為幾何代數空間的多重向量，多重向量直接分類困難，因此把幾何代數多重向量的各階片積的系數組成向量表示，然后進行分類。
0 階片積系數假設為1，1階片積系數是原始特征，那么轉化為高階( 假設d=4，那么D=1+4+6+4+1=16；假設d=8，那么D=1+8+28+56+70+56+28+8+1=256。通過對原始特征提取幾何代數片積的高階關聯信息，我們發現D=2d，樣本維數呈指數增長。因此有必要對向量進行特征選擇。即使只采用1階和2階片積系數，不使用標量和高階片積系數，假設d=9，那么D=9+36=45，也需要進行特征選擇。
2 微分進化特征選擇
2.1 微分進化
微分進化算法是一種新的進化計算方法，由Storn等[9]于1995年提出的，是目前優化領域的研究熱點。微分進化算法可以分為以下幾個步驟：第一步，生成初始種群；第二步，變異操作，交叉操作，選擇操作；第三步，得到下一代種群，如果沒有達到最優目標，返回第二步。
微分進化參數設置對算法性能具有很大的影響。微分進化算法的控制參數主要有：種群大小、變異因子、交叉因子、最大進化代數和終止條件。這些參數的設置因具體問題的不同而不盡相同，但也有一些固定的規則和經驗，下面將一一進行總結。
(1)種群大小(NP)： 它表示一代種群中包含的個體數。根據經驗，NP值應與個體向量的維度D有關，一般選擇NP值在5~10 D之內，以確保微分進化算法具有足夠的變異向量。N越大，種群多樣性越強，獲得最優解概率越大，但是計算時間也更長。
(2)變異因子(F)： F∈[0, 2]，是一個實常數因子，它決定差向量的放大比例。學者們在研究中發現，F的初始值選擇在0.4~1之內較好，建議初始值選擇0.5，并根據實際問題進行調整[9]。F控制種群多樣性和收斂性。F越大，算法更容易逃出局部極小點，更容易收斂到全局最優點，但是當F＞1時，收斂速度將變慢。
(3)交叉因子(CR)： CR∈[0, 1]，是一個實常數因子，它控制著試驗向量基因來自于變異向量的概率。比較好的選擇應在0.3左右。CR控制個體參數的各維對交叉的參與程度，以及全局與局部搜索能力的平衡。CR越大，收斂速度越快，但易發生早熟現象。
(4)最大進化代數： 它表示算法運行結束條件的一個參數，算法運行到指定的進化代數之后就停止運行，并將當前種群中的最佳個體作為所求問題的最優解輸出。
(5)終止條件： 常用的終止條件除最大進化代數外，還有其他準則。可以設定目標函數的閾值，當計算結果超過閾值時程序終止。
2.2 微分進化相關擴展模式
上面闡述的是最基本的微分進化操作程序，實際應用中還發展了微分進化的擴展模式[9]，并用DE/x/y/z表示，式中x表示限定當前被變異的向量是在當前種群中隨機選取的或最佳的；y表示是變異操作所利用的差向量的個數；z表示交叉操作的模式，上面敘述的交叉操作表示為“bin”。下面列出一些主要模式：模式1是DE/RAND/1/bin(標準微分進化算法)、模式2是DE/BEST/1/bin、模式3是DE/RAND_to_BEST/1/bin、模式4是DE/BEST/2/bin、模式5是DE/RAND/2/bin。
針對以上幾種擴展模式，研究者通過大量的函數測試，發現各種模式的微分進化算法效果有一定的差別，其中以模式1和模式4的微分進化算法效果最好，但是采用模式1的微分進化算法最為簡單，因此后面仿真實驗采用了標準微分進化算法。
2.3 改進的微分進化特征選擇
微分進化算法最初主要用于解決連續空間的優化問題，采用實數編碼方式，但是實際問題中存在許多離散空間的優化問題，采用實數編碼反而降低了算法的易用性。在應用于特征選擇問題時，微分進化算法采用了二進制思想，對每一維特征進行二進制編碼，具體描述如下：對于某一特征子集選擇問題，假設初始樣本有D個特征，特征選擇的目的是從這初始的D個特征中選擇一個子集來表示該樣本。在種群初始化時，將產生許多個體，每一個個體表示一個特征子集，個體向量的維數為樣本總特征數D，個體向量的某一維為“1”意味該特征被選擇，為“0”意味該特征不被選擇，如圖 1所示。
圖1
微分進化算法二進制思想
Figure1.
Schematic diagram of binary idea of DE algorithms
在變異、交叉、選擇操作中，特征子集都是以二進制的個體向量形式表示的。在分類器計算每個個體的適應度值時(以封裝法為例)，將目標向量的二進制數轉換為對應的特征子集，即選出二進制數中值為“1”的那些維對應的特征，組成特征子集，計算分類錯誤率，作為選擇操作中取舍該候選解的依據。在后面的仿真實驗中，就利用了微分進化算法的二進制思想解決特征選擇問題，并取得了較好的實驗結果。
3 實驗結果與分析
實驗數據是從加州大學歐文分校 (University of California Irvine,UCI) 機器學習數據庫下載的乳腺癌生物醫學數據，樣本數683，特征數9維，類別數2，常用于文獻中各種模式識別任務性能比較。經過2階片積系數的幾何代數面積特征提取后，乳腺癌樣本的特征數為45，即特征向量的維數為45。采用封裝法將微分進化算法與分類器結合搜索特征子集。分類器采用簡單的線性判別分析，沒有使用復雜分類器。分類器錯誤率的估計采用10折交叉驗證(10-fold cross validation,10 CV)，取20次獨立實驗的平均結果。微分進化特征選擇參數設置如下，采用標準微分進化算法，NP取固定值30，經過實驗和比較，設置F取0.7，CR取0.3。停止條件為設定的最大進化代數。
3.1 特征子集為6維的分類結果與分析
若設定特征子集中的特征數為6，即選擇45維特征的6個特征子集作為搜索結果。一次10 CV得到的特征子集選擇結果如表 1所示。表中還列出了相應的訓練組和測試組的分類正確率，以及10折的訓練組和測試組的均值正確率分別為96.958%和96.046%。
表1
Breast Cancer Data子集特征數為6的某次特征選擇結果
Table1.
Feature selection with 6 dimension subset features of Breast Cancer Data
經過20次10 CV，將產生20組如表 1所示的均值數據。20次10 CV的訓練組和測試組分類均值正確率分別為96.925%和96.051%。
經過20次10 CV后，將產生200個最優特征子集。對數據的每一維出現在最優特征子集中的次數做統計，并繪制柱狀圖，結果如圖 2所示。從圖 2中可以看到，第1維和第6維特征在最優特征子集中出現的次數最多。最優特征子集中也不一定要包含第1維和第6維，因為僅選取最優特征子集中次數多的特征組成的子集不一定具有最優分類能力。
圖2
Breast Cancer Data子集特征數為6時各維度200次統計結果
Figure2.
Statistical results of each dimension for 200 times under 6 dimension subset features of Breast Cancer Data
3.2 不同特征子集的分類結果與分析
實驗對乳腺癌生物醫學數據選擇的特征子集包含的不同特征數進行了仿真，分別設定了子集中包含的特征數為6、8、10、12、14、16、18、20，共8種情況，均如上述過程進行10 CV，并重復進行20次。8種特征子集選擇結果在此不一一列出，只針對分類正確率的均值和方差進行分析。訓練組和測試組數據的分類正確率均值及標準差如圖 3所示。結果較好地體現了微分進化算法在搜索特征子集上的優越性能，但其正確率的標準差較大，說明算法在面對新數據時并不是十分穩定，對于如何改善分類結果有待進一步分析和研究。當特征數為20時，最高分類正確率達到96.4%，優于原始數據特征96.0%的正確率，也優于主成分分析特征的95.3%的正確率(原始數據特征和主成分分析特征的正確率經編程和實驗得到)。
針對乳腺癌生物醫學數據樣本可以看出，微分進化算法在保證較高的分類正確率的情況下，有效地壓縮了數據特征的維數，使原始數據維數為45的樣本壓縮到特征數為6時，仍能取得平均96.05%以上的正確率。
圖3
Breast Cancer Data訓練組(左)和測試組(右)不同特征子集時的分類正確率及標準差
Figure3.
Classification accuracy and deviation for training (left) and testing (right) data of Breast Cancer Data under different feature subsets
3.3 結果討論
本文將微分進化算法應用于解決特征選擇問題，通過設計仿真實驗得到了較好的實驗結果。對實驗數據的分析和總結表明，該算法在解決特征選擇問題上具有良好的性能：第一，針對不同類型的數據，微分進化算法不需要問題的具體信息，能夠直接進行特征子集的搜索，具有較好的通用性；第二，能夠保證在分類正確率較高的前提下較快地搜索特征子集，起到剔除無關和冗余特征，壓縮數據維度，節約存儲空間的作用；第三，由于算法結構相對簡單，程序運行速度較快，達到了減少分類器的訓練時間，節約系統時間開銷的目的。
本次仿真實驗中得到的數據結果也表明，標準微分進化算法還存在一些不盡人意的地方，如算法的穩定性不是很高，這就需要對算法的基本操作和參數設置進行更加深入的研究，在實驗的基礎上對算法操作和參數設置做出改進，以改善微分進化算法在解決特征選擇問題上的性能。
國內外研究者針對乳腺癌的計算機輔助診斷進行了大量研究。Stoean等[10]提出基于進化算法的特征選擇和支持向量機分類結合的方法，實驗正確率為96%左右；Chang等[11]提出基于特征加權和粒子群優化的方法，實驗平均正確率為97.4%；Chen等[12]提出基于遺傳算法和人工神經網絡結合的方法，實驗平均正確率為96.9%；Chen等[13]提出基于粗集特征選擇和支持向量機結合的方法，實驗平均正確率為96.11%；Li等[14]提出基于粗集特征選擇和支持向量機結合的方法，實驗最大正確率為95.12%。本文作者[4-5]過去提出的基于遺傳算法特征選擇和分類器結合的平均正確率為96.8%，而基于遺傳算法雷達圖特征排序和分類器結合的平均正確率為98.3%。文獻[15]給出了多種數據的基準分類結果。這些方法的特征選擇、特征提取和分類器都比較復雜，而本文算法理論基礎數學化，可解釋性強。本文算法優于原始特征和主成分分析等特征提取方法的分類性能。如需進一步提高本文算法正確率，還可嘗試選擇其它分類器。
4 結論
本研究對乳腺癌數據分類的創新有以下兩點：一是基于高維數據的幾何代數表示，提出了幾何代數片積的特征提取方法，即外積特征或高階關聯特征。這有別于傳統的高維數據特征提取方法；二是提出了基于改進的微分進化特征選擇方法。新方法對于傳統微分進化算法有三個主要修正：個體設計，適應度函數以及提出修補操作。分類器僅使用簡單的線性判別分析分類器，乳腺癌數據分類性能達到96%以上。未來的工作包括進一步研究階數為3及以上的片積系數的特征提取方法，它更能體現變量間的高階關聯和幾何關系。
引言
近年來乳腺癌的發病率一直處于增長態勢，隨著診斷和治療手段的進步，乳腺癌患者的長期存活率一直在提高[1]。影響預后的關鍵問題是乳腺癌的早期檢測和正確診斷。毫無疑問，癌癥患者的醫學數據和專家決策是癌癥診斷中最重要的因素，因此特征提取和分類是醫療診斷系統中的研究重點。事實上，基于醫學數據和計算機模式識別技術可以幫助疲勞的專家或者經驗不足的醫生在更短時間內做出決策，并盡可能減少決策錯誤[2-3]。
眾所周知，對原始數據或提取特征進行分類是一個通用方法。但是目前特征提取方法對變量間高階關聯闡述不清楚。我們發表的論文利用高維數據的兩個變量間的關聯特征，如面積或重心，在某些真實數據集的最佳分類性能優于或相當于國際報道的分類性能最優值[4-5]。基于幾何代數理論[6-7]，研究者認為高維數據的兩個變量間的面積或重心特征是幾何代數多重向量表示中的階數(grade)為2的片積(blade)系數，是幾何代數子空間中變量間組合信息，體現了變量間高階關聯和幾何直觀性。本文提出了高維數據的幾何代數特征提取和微分進化(differential evolution,DE)特征選擇方法。首先將高維數據特征經過二次映射方法升維到幾何代數子空間[4-5]，在幾何代數子空間利用微分進化方法進行最優特征選擇。實際上這是一個先提取、后選擇的過程。經過升維變換后，原始數據的1階向量特征擴展為幾何代數子空間中的多級高階幾何特征，這樣可以充分利用原始數據變量間的高階關聯信息。分類器采用簡單的線性判別分析。以乳腺癌生物醫學數據集驗證的實驗結果表明，基于本文新方法的分類性能優于原始特征和傳統特征提取的分類性能。
1 幾何代數特征提取方法
幾何代數(又叫Clifford代數)是一種描述幾何對象并可進行幾何計算的統一性語言。幾何代數是復代數和四元數代數的超集。幾何代數通過多重向量(multi-vector)和幾何積(geometrical product)兩個核心概念可以進行子空間的表示和幾何計算[8]。幾何代數的運算對象和運算結果都具有明顯的幾何含義，表示多維數據的各級子空間。
1.1 幾何代數多重向量表示
首先，建立高維數據向量表示和幾何代數多重向量表示之間的映射關系模型。映射關系是由三個域--向量表示域、映射域和幾何代數多重向量表示域以及4個變換器--向量變換器、映射器、幾何代數多重向量變換器和逆映射器組成。向量變換器是在向量表示域間實現向量到向量的變換，如數據的預處理和特征提取等。映射器功能是將向量表示映射到幾何代數多重向量表示。幾何代數多重向量變換器功能是實現幾何代數多重向量之間的變換。逆映射器功能是將幾何代數多重向量表示映射到向量表示。
以三維向量空間為例，若其標準正交基為{e1,e2,e3}，則其幾何代數G(E3)為一個8維的向量空間，其基為{1,e1,e2,e3,e1e2,e2e3,e3e1,e1e2e3}，其中1為0階片積(標量)，e1,e2,e3為1階片積，e1e2,e2e3,e3e1為2階片積，e1e2e3為3階片積。例如三維向量xi=[xi1,xi2,xi3]T可表示為xiC=s+xi1e1+xi2e2+xi3e3+xi12e12+xi13e13+xi23e23+xi123e123幾何代數多重向量形式，其中s=1，xi1,xi2,xi3等于原來值，其它片積系數待定。k-階片積相當于k級子空間，具有明顯的幾何含義，例如2階片積相當于一個有向的面元，3階片積相當于一個有向的體元。
1.2 幾何代數特征提取原理
利用幾何代數可提取高維數據的高階幾何特征。線性無關的d個向量a1,…,ad(d≤n)具有的最高階次片積為d-片積。d-片積的線性組合表示為
| $\sum\limits_{I\in {{\Phi }_{d}}}{{{w}_{I}}{{e}_{I}}},{{\Phi }_{d}}=\{{{i}_{1}},{{i}_{2}},\ldots ,{{d}_{d}}|1\le {{i}_{1}}＜\ldots ＜{{i}_{d}}\le n\}$ |
d個向量的幾何積為
| ${{a}_{1}}\ldots {{a}_{d}}\in \left\{ \begin{align} & {{\Omega }_{n}}^{1}\oplus \ldots \oplus {{\Omega }_{n}}^{d-2}{{\oplus }^{\wedge d}}{{R}^{n}}(odd~d) \\ & {{\Omega }_{n}}^{0}\oplus \ldots \oplus {{\Omega }_{n}}^{d-2}{{\oplus }^{\wedge d}}{{R}^{n}}(even~d) \\ \end{align} \right.$ |
假定現有一組空間向量ξ={pl∈Rn,l=1,…,m}，特征提取方法如下：
令n′=min{n,m}，對于d=1,…,n′
| $\begin{align} & {{f}_{d}}(\xi )=\{＜{{p}_{l}}\ldots {{p}_{l+k-1}}{{e}_{l}}^{-1}＞,I\in {{\Phi }_{d}},l=1,\ldots ,n-d+1\} \\ & \in {{R}^{\left( m-d+1 \right)|{{\Phi }_{d}}|}}, \\ \end{align}$ |
其中<·>表示選擇標量運算。|Φd|為從n個元素中選擇d個元素的組合數目。eI-1為eI逆。
1.3 幾何代數片積的特征提取方法
設d維向量空間標準正交基為e1,e2,…,ed，則這d個基向量張成了幾何代數d階片積子空間。可以看出1階片積系數是原始特征，那么2階片積系數可以是對應的1階片積的幾何積系數，高階片積系數類似。因此高階片積系數是樣本變量間高階關聯的體現。
樣本的向量表示可以映射為幾何代數空間的多重向量，多重向量直接分類困難，因此把幾何代數多重向量的各階片積的系數組成向量表示，然后進行分類。
0 階片積系數假設為1，1階片積系數是原始特征，那么轉化為高階( 假設d=4，那么D=1+4+6+4+1=16；假設d=8，那么D=1+8+28+56+70+56+28+8+1=256。通過對原始特征提取幾何代數片積的高階關聯信息，我們發現D=2d，樣本維數呈指數增長。因此有必要對向量進行特征選擇。即使只采用1階和2階片積系數，不使用標量和高階片積系數，假設d=9，那么D=9+36=45，也需要進行特征選擇。
2 微分進化特征選擇
2.1 微分進化
微分進化算法是一種新的進化計算方法，由Storn等[9]于1995年提出的，是目前優化領域的研究熱點。微分進化算法可以分為以下幾個步驟：第一步，生成初始種群；第二步，變異操作，交叉操作，選擇操作；第三步，得到下一代種群，如果沒有達到最優目標，返回第二步。
微分進化參數設置對算法性能具有很大的影響。微分進化算法的控制參數主要有：種群大小、變異因子、交叉因子、最大進化代數和終止條件。這些參數的設置因具體問題的不同而不盡相同，但也有一些固定的規則和經驗，下面將一一進行總結。
(1)種群大小(NP)： 它表示一代種群中包含的個體數。根據經驗，NP值應與個體向量的維度D有關，一般選擇NP值在5~10 D之內，以確保微分進化算法具有足夠的變異向量。N越大，種群多樣性越強，獲得最優解概率越大，但是計算時間也更長。
(2)變異因子(F)： F∈[0, 2]，是一個實常數因子，它決定差向量的放大比例。學者們在研究中發現，F的初始值選擇在0.4~1之內較好，建議初始值選擇0.5，并根據實際問題進行調整[9]。F控制種群多樣性和收斂性。F越大，算法更容易逃出局部極小點，更容易收斂到全局最優點，但是當F＞1時，收斂速度將變慢。
(3)交叉因子(CR)： CR∈[0, 1]，是一個實常數因子，它控制著試驗向量基因來自于變異向量的概率。比較好的選擇應在0.3左右。CR控制個體參數的各維對交叉的參與程度，以及全局與局部搜索能力的平衡。CR越大，收斂速度越快，但易發生早熟現象。
(4)最大進化代數： 它表示算法運行結束條件的一個參數，算法運行到指定的進化代數之后就停止運行，并將當前種群中的最佳個體作為所求問題的最優解輸出。
(5)終止條件： 常用的終止條件除最大進化代數外，還有其他準則。可以設定目標函數的閾值，當計算結果超過閾值時程序終止。
2.2 微分進化相關擴展模式
上面闡述的是最基本的微分進化操作程序，實際應用中還發展了微分進化的擴展模式[9]，并用DE/x/y/z表示，式中x表示限定當前被變異的向量是在當前種群中隨機選取的或最佳的；y表示是變異操作所利用的差向量的個數；z表示交叉操作的模式，上面敘述的交叉操作表示為“bin”。下面列出一些主要模式：模式1是DE/RAND/1/bin(標準微分進化算法)、模式2是DE/BEST/1/bin、模式3是DE/RAND_to_BEST/1/bin、模式4是DE/BEST/2/bin、模式5是DE/RAND/2/bin。
針對以上幾種擴展模式，研究者通過大量的函數測試，發現各種模式的微分進化算法效果有一定的差別，其中以模式1和模式4的微分進化算法效果最好，但是采用模式1的微分進化算法最為簡單，因此后面仿真實驗采用了標準微分進化算法。
2.3 改進的微分進化特征選擇
微分進化算法最初主要用于解決連續空間的優化問題，采用實數編碼方式，但是實際問題中存在許多離散空間的優化問題，采用實數編碼反而降低了算法的易用性。在應用于特征選擇問題時，微分進化算法采用了二進制思想，對每一維特征進行二進制編碼，具體描述如下：對于某一特征子集選擇問題，假設初始樣本有D個特征，特征選擇的目的是從這初始的D個特征中選擇一個子集來表示該樣本。在種群初始化時，將產生許多個體，每一個個體表示一個特征子集，個體向量的維數為樣本總特征數D，個體向量的某一維為“1”意味該特征被選擇，為“0”意味該特征不被選擇，如圖 1所示。
圖1
微分進化算法二進制思想
Figure1.
Schematic diagram of binary idea of DE algorithms
在變異、交叉、選擇操作中，特征子集都是以二進制的個體向量形式表示的。在分類器計算每個個體的適應度值時(以封裝法為例)，將目標向量的二進制數轉換為對應的特征子集，即選出二進制數中值為“1”的那些維對應的特征，組成特征子集，計算分類錯誤率，作為選擇操作中取舍該候選解的依據。在后面的仿真實驗中，就利用了微分進化算法的二進制思想解決特征選擇問題，并取得了較好的實驗結果。
3 實驗結果與分析
實驗數據是從加州大學歐文分校 (University of California Irvine,UCI) 機器學習數據庫下載的乳腺癌生物醫學數據，樣本數683，特征數9維，類別數2，常用于文獻中各種模式識別任務性能比較。經過2階片積系數的幾何代數面積特征提取后，乳腺癌樣本的特征數為45，即特征向量的維數為45。采用封裝法將微分進化算法與分類器結合搜索特征子集。分類器采用簡單的線性判別分析，沒有使用復雜分類器。分類器錯誤率的估計采用10折交叉驗證(10-fold cross validation,10 CV)，取20次獨立實驗的平均結果。微分進化特征選擇參數設置如下，采用標準微分進化算法，NP取固定值30，經過實驗和比較，設置F取0.7，CR取0.3。停止條件為設定的最大進化代數。
3.1 特征子集為6維的分類結果與分析
若設定特征子集中的特征數為6，即選擇45維特征的6個特征子集作為搜索結果。一次10 CV得到的特征子集選擇結果如表 1所示。表中還列出了相應的訓練組和測試組的分類正確率，以及10折的訓練組和測試組的均值正確率分別為96.958%和96.046%。
表1
Breast Cancer Data子集特征數為6的某次特征選擇結果
Table1.
Feature selection with 6 dimension subset features of Breast Cancer Data
經過20次10 CV，將產生20組如表 1所示的均值數據。20次10 CV的訓練組和測試組分類均值正確率分別為96.925%和96.051%。
經過20次10 CV后，將產生200個最優特征子集。對數據的每一維出現在最優特征子集中的次數做統計，并繪制柱狀圖，結果如圖 2所示。從圖 2中可以看到，第1維和第6維特征在最優特征子集中出現的次數最多。最優特征子集中也不一定要包含第1維和第6維，因為僅選取最優特征子集中次數多的特征組成的子集不一定具有最優分類能力。
圖2
Breast Cancer Data子集特征數為6時各維度200次統計結果
Figure2.
Statistical results of each dimension for 200 times under 6 dimension subset features of Breast Cancer Data
3.2 不同特征子集的分類結果與分析
實驗對乳腺癌生物醫學數據選擇的特征子集包含的不同特征數進行了仿真，分別設定了子集中包含的特征數為6、8、10、12、14、16、18、20，共8種情況，均如上述過程進行10 CV，并重復進行20次。8種特征子集選擇結果在此不一一列出，只針對分類正確率的均值和方差進行分析。訓練組和測試組數據的分類正確率均值及標準差如圖 3所示。結果較好地體現了微分進化算法在搜索特征子集上的優越性能，但其正確率的標準差較大，說明算法在面對新數據時并不是十分穩定，對于如何改善分類結果有待進一步分析和研究。當特征數為20時，最高分類正確率達到96.4%，優于原始數據特征96.0%的正確率，也優于主成分分析特征的95.3%的正確率(原始數據特征和主成分分析特征的正確率經編程和實驗得到)。
針對乳腺癌生物醫學數據樣本可以看出，微分進化算法在保證較高的分類正確率的情況下，有效地壓縮了數據特征的維數，使原始數據維數為45的樣本壓縮到特征數為6時，仍能取得平均96.05%以上的正確率。
圖3
Breast Cancer Data訓練組(左)和測試組(右)不同特征子集時的分類正確率及標準差
Figure3.
Classification accuracy and deviation for training (left) and testing (right) data of Breast Cancer Data under different feature subsets
3.3 結果討論
本文將微分進化算法應用于解決特征選擇問題，通過設計仿真實驗得到了較好的實驗結果。對實驗數據的分析和總結表明，該算法在解決特征選擇問題上具有良好的性能：第一，針對不同類型的數據，微分進化算法不需要問題的具體信息，能夠直接進行特征子集的搜索，具有較好的通用性；第二，能夠保證在分類正確率較高的前提下較快地搜索特征子集，起到剔除無關和冗余特征，壓縮數據維度，節約存儲空間的作用；第三，由于算法結構相對簡單，程序運行速度較快，達到了減少分類器的訓練時間，節約系統時間開銷的目的。
本次仿真實驗中得到的數據結果也表明，標準微分進化算法還存在一些不盡人意的地方，如算法的穩定性不是很高，這就需要對算法的基本操作和參數設置進行更加深入的研究，在實驗的基礎上對算法操作和參數設置做出改進，以改善微分進化算法在解決特征選擇問題上的性能。
國內外研究者針對乳腺癌的計算機輔助診斷進行了大量研究。Stoean等[10]提出基于進化算法的特征選擇和支持向量機分類結合的方法，實驗正確率為96%左右；Chang等[11]提出基于特征加權和粒子群優化的方法，實驗平均正確率為97.4%；Chen等[12]提出基于遺傳算法和人工神經網絡結合的方法，實驗平均正確率為96.9%；Chen等[13]提出基于粗集特征選擇和支持向量機結合的方法，實驗平均正確率為96.11%；Li等[14]提出基于粗集特征選擇和支持向量機結合的方法，實驗最大正確率為95.12%。本文作者[4-5]過去提出的基于遺傳算法特征選擇和分類器結合的平均正確率為96.8%，而基于遺傳算法雷達圖特征排序和分類器結合的平均正確率為98.3%。文獻[15]給出了多種數據的基準分類結果。這些方法的特征選擇、特征提取和分類器都比較復雜，而本文算法理論基礎數學化，可解釋性強。本文算法優于原始特征和主成分分析等特征提取方法的分類性能。如需進一步提高本文算法正確率，還可嘗試選擇其它分類器。
4 結論
本研究對乳腺癌數據分類的創新有以下兩點：一是基于高維數據的幾何代數表示，提出了幾何代數片積的特征提取方法，即外積特征或高階關聯特征。這有別于傳統的高維數據特征提取方法；二是提出了基于改進的微分進化特征選擇方法。新方法對于傳統微分進化算法有三個主要修正：個體設計，適應度函數以及提出修補操作。分類器僅使用簡單的線性判別分析分類器，乳腺癌數據分類性能達到96%以上。未來的工作包括進一步研究階數為3及以上的片積系數的特征提取方法，它更能體現變量間的高階關聯和幾何關系。
