結合高斯混合模型的關聯分類離散化算法研究

吳辰文,郭叔瑾,李晨陽

(蘭州交通大學 電子與信息工程學院,蘭州 730070) E-mail:2356162345@qq.com

1 引 言

運用規則歸納算法提取的規則可以用于分類,這被稱為以規則為基礎的分類.在以規則為基礎的分類器中使用簡單的if-then規則,可以提高分類過程的解釋性,并幫助領域專家了解將某一觀測值分到某一類別背后的邏輯[1,2].在醫療領域,基于規則的分類器特別重要,它們可以被用于設計臨床決策支持系統以提高醫療診斷[3-5].醫生可以使用提取的規則來驗證分類結果并降低錯誤分類的可能[6].

雖然它們有優勢,但大多數以規則為基礎的分類只能處理分類數據,不能直接應用于連續數據[7].然而,大多數數據中包括連續變量,如腫瘤大小,身體質量指數等.因此,需要一個預處理步驟將連續變量轉換成離散格式.此預處理步驟被稱為離散化,并涉及到使用一組分割點,將連續變量劃分為不同的區間.最佳的分類性能,必須選擇這樣的分割點,即在離散化的數據集上保持原始數據集的模式不變.因此,離散化算法應考慮到多峰分布的連續變量,以保持原始模式.然而,大多數離散化算法的結果并不能反映原來多模態分布的連續變量.它是改變了原來數據的分布且降低了生成規則可靠性的規則歸納算法[8].此外,目前大多數的離散化算法要么集中在最小化間隔數,要么最大化分類準確度.然而,這兩個準則都和生成的規則數不直接相關.生成的規則數是基于規則分類器系統的一個重要性能指標,但是目前基于規則分類器的離散化算法忽略了生成規則數目的重要性.

高斯混合模型已被證明是一種有效的工具,用于估計多模態密度的連續變量[9].考慮到這一事實和現有離散化方法的局限性,我們提出了一種有監督離散化算法,稱作基于高斯混合模型的離散化算法DAGMM(Discretization Algorithm based on Gaussian Mixture Model).DAGMM算法運用每一個特征的多模態分類密度來確認分割點.運用高斯混合模型捕獲多模態密度,高斯分量數由貝葉斯信息準則(Bayesian Information Criterion,BIC)確定.

我們通過DAGMM算法的離散化結果來測試該算法的性能.實驗結果表明,已訓練的關聯分類器的性能在少量規則的生成和高分類精度之間達到了平衡.此外,和6個靜態離散化算法的比較表明,DAGMM算法優于其他離散化算法.

2 相關理論

2.1 離散化方法

離散化是將連續特征F映射到m個區間U={[d0,d1],…,[dm-1,dm]}的過程.在本文中,將6個靜態離散化算法和DAGMM算法進行比較.這6個算法包括等寬(Equal Width,EW)算法,等頻(Equal Frequency,EF)算法,1R算法,類-屬性相依系數離散化(Class-Attribute Contingency Coefficient discretization,CACC)算法,基于有效信息比率的離散化算法(EIRDC)和正則化高斯混合模型離散化(Regularized Gaussian Mixture Model discretization,RGMM)算法.在EW算法中,每個區間長度是固定的,而EF算法每個區間的頻數是固定的.1R離散化算法對每一個區間和值,都是基于最優分類概念的有監督離散化方法[7].CACC算法使用變量之間的相互依存離散化連續數據[8],EIRDC算法在信息熵的基礎上,定義了離散化區間上的有效信息比率[10],RGMM使最優高斯混合模型符合數據集,并根據最大概率準則給每一個高斯混合分量分配一個新樣本[11].

2.2 高斯混合模型及其在離散化算法中的應用

高斯混合模型(Gaussian Mixture Model,GMM)是連續型隨機變量參數的概率分布,其中密度函數被定義為多個高斯密度加權和[9].在GMM中,高斯函數的離散集合提供更好的建模能力.GMM的數學公式在方程1中被提供[12]

(1)

(2)

其中D是χ的維數.

估計GMM的參數最常用的一種方式是最大似然估計(Expectation Maximization,EM)[13].通過優化方程3中定義的對數似然函數的參數,來找到最大似然的迭代方法.

(3)

優化處理包括初始化Θ值(通常是隨機的)和迭代更新Θ直到收斂.循環變量j,GMM的參數Θ更新如下:

(4)

(5)

(6)

(7)

運用EM算法從訓練集中估計GMM的參數,已成功地應用于各個方面,如在計算視覺中的目標跟蹤,在音頻處理中說話者的識別和在生物識別技術中的個人身份驗證.考慮到高斯混合模型的繼承性,將數據分為不同的組,GMM是理想的離散化過程.RGMM適合基于熵和信息損失的最優高斯混合模型,并根據最大概率準則給每一個高斯混合分量分配一個新樣本.RGMM是無監督離散化算法,在離散化過程中不考慮類標簽.無監督算法的性質限制了它的分類能力,所以進行有監督學習是必要的.因此,為了運用算法RGMM離散化一個新的數據點,對所有已確定高斯分量的新數據點計算其條件概率,并選擇高斯分量結果標簽中的最大概率值作為新的離散值.這種離散化新值的方法難以解決沒有提供用于追蹤離散化過程中實際間隔的問題.本文提出的DAGMM算法解決了此限制.

圖1 DAGMM算法的5個步驟Fig.1 Five steps of DAGMM algorithm

3 DAGMM算法

3.1 基于高斯混合模型的離散化DAGMM

DAGMM算法包括5個步驟,如圖1所示.

步驟1.以類標簽C為基礎,將數據集分割成不同的子集.

步驟2.運用EM算法,得到符合每一個子集特征的高斯混合模型.這一步需要的兩個主要參數包括迭代次數和高斯分量數.迭代次數依經驗來定義,高斯分量數由BIC準則來確定的.用一個簡單的迭代搜索來識別分量具有最小BIC值的個數.最小BIC準則根據4.3部分的實驗測試結果來選擇.采用最小BIC有助于避免GMM的過擬合,DAGMM算法平衡了復雜性的降低和信息的損失.

步驟3.在步驟2中使用適當的高斯分量確定每個特征的初始間隔.對于每個高斯分量,定義區間為|μ-3σ,μ+3σ|,其中μ和σ表示相應的高斯分量均值和標準差.初始區間可能包含一些重疊,這些重疊在DAGMM算法接下來的步驟中被移除.

圖2 重疊部分的兩個處理步驟Fig.2 Two processing steps for overlapping parts

步驟4.使用類比率(Class Ratio,CR)刪除初始區間的重疊.CR的定義如下:

(8)

其中Ne是屬于類e的觀測總量,N是數據集中的觀測總量.

階段1.如果一個區間完全在另一個區間內,并且它們屬于同一類,刪除位于其它區間有限范圍內的區間.如果它們屬于不同的類,檢查相應的高斯分量的權重,刪除屬于高斯分量較小的區間(權重×CR)(見圖2).

階段2.運用下列規則刪除確定間隔之間剩余的重疊部分:

1)如果兩個區間屬于同一類.通過設置前區間的上限到處理區間的上限(Upper Limit,UL)來合并兩個區間.

2)如果兩個區間屬于不同的類,檢查相應的高斯分量的權重.如果處理區間的(weight×CR)大于前區間的(weight×CR),則前區間的上限UL等于處理區間下限(Lower Limit,LL).如果處理區間的(weight×CR)小于前區間的(weight×CR),則處理區間的下限等于前區間的上限(如圖2).刪除所有間隔之間的重疊后,給每一個區間分配一個唯一的標識符.

步驟5.運用下列步驟離散化一個新值:

1)如果數據點在任何區間的邊界內,則將該區間的標識符作為該數據點的新值.

2)如果數據點在任意區間的邊界外,計算所有區間從質心((UL+LL)/2)到數據點的距離,并指定最近的標識符作為數據點的新值.例如,圖1中的步驟5中的數據點不屬于任何區間.因此,從三個剩余區間的質心計算距離.考慮到距離值(d1>d2>d3),3被分配作為該數據點的新值.

3.2 關聯分類

圖3 基于簡單多數投票的關聯分類器Fig.3 Association classifier based on simple majority voting

關聯分類是結合關聯規則挖掘和分類的一種新的分類方法[14].本文運用一個基于簡單多數投票的關聯分類器[15]來測試DAGMM算法的性能.簡單的關聯分類器(如圖3)由以下三部分組成:

步驟1.基于每個觀測值的類標簽,將離散的輸入分割成多個子集.對于二進制類標簽的數據,分割的結果是兩個子數據集.

步驟2.運用Apriori算法從每個子集中提取關聯規則.Apriori算法是最受歡迎的關聯規則挖掘算法之一,它有兩個主要步驟.第一步叫做自連接,滿足最小支持度閾值的k-項集需要自連接產生(k+1)-項集[16].第二步叫做剪枝,基于最小支持度準則剪枝(k+1)-項集.使用最小置信度閾值進行過濾,Apriori算法迭代的最終結果項集稱為關聯規則.

步驟3.一個簡單的無加權投票的方法,即多數投票,用于分類一個新的觀測值.在投票方案中,一個新的觀察值不能測試提取的所有關聯規則,把滿足規則的多數類標簽作為新數據點的類標簽.

4 實驗及分析

實驗平臺采用64位的Windows7操作系統,處理器為Intel(R)Core(TM)i5-3210M,內存為4G.實驗數據來自UCI機器學習庫.實驗在MATLAB R2014a平臺中實現.

4.1 數據集

在實驗中使用四個醫療數據集作為研究對象(如表1 所示).這些數據集包括連續和分類的特征.連續特征歸一化到[0,1]范圍,把含有缺失值的觀測值從數據集中刪除.這項研究中數據集中的大多數變量服從非正態分布.

4.2 DAGMM算法性能評價

使用在第三部分引入的關聯分類來評價DAGMM離散化算法的性能.關聯分類的最小支持度和最小置信度分別設置為0.3和0.9.設置高支持度和置信度閾值,以確保從數據集的頻繁模式中提取規則,而不是由罕見的模式所造成的異常提取.在醫療領域設置高支持度和置信度是特別重要的,因為想提取可靠的規則,更廣泛地應用于患者.提取具有高支持度和置信度的規則,需要在連續數據集中保持原始模式,是一個很好的評價離散化算法的指標.

運用5折交叉驗證評價關聯分類性能.在5折交叉驗證方法中,數據集被等分成5組.接下來,4組用于訓練集,剩下的1組作為測試集.此過程被重復5次直到每組都被選作為測試集.整體性能,即分類準確度和規則數目,計算5次迭代過程中所有記錄性能的平均值作為整體性能.一種排序方法用于簡化結果的比較.排序工作是通過分配從一到最佳性能(最大分類準確度或最少規則數)的排序,并逐步增加排名,直到達到最壞的性能.N/A表示關聯分類情況下沒有產生任何結果,最后給出了最大排名.整體的排名是計算分類準確度平均排名的數目和產生規則的數目.應當指出的是,區間數量只供參考,并沒有用于整體排名的計算.原因是,我們的研究結果和以前的研究結果表明,確定的區間數目和分類性能之間沒有直接的關系.

表1 UCI中的四個醫療數據集
Table 1 Four medical data sets in UCI

數據集樣本數(正/負)特征數連續特征數帕金森氏癥195(48/147)2222乳腺癌569(357/212)3030糖尿病768(268/500)82肝臟病583(167/461)105

4.3 敏感性分析

DAGMM算法的一個關鍵參數是高斯分量數.選擇大量的高斯分量可能導致過擬合,而少量的高斯分量可能不足以捕捉到數據的多模態密度.可以使用統計選擇模型選擇高斯分量的數目.兩大統計選擇模型包括赤池信息準則(Akaike Information Criterion,AIC)和BIC.AIC和BIC通過引入一個懲罰項來平衡復雜性和模型的擬合優度[17].

表2 五折交叉驗證的結果
Table 2 Result of 5-CV

模型選擇標準數據集帕金森氏癥乳腺癌糖尿病肝臟病平均排名總體排名分類準確度min(AIC+BIC)/279.7561.12N/A57.503.438.25min(AIC)N/A64.98N/AN/A6.6113.08min(BIC)84.1168.1673.1262.081.496.26min(AIC*BIC)N/A61.8250.0351.857.0111.51min(AIC+BIC+(AIC*BIC))N/A60.7750.0351.857.1811.51產生規則的平均值min(AIC+BIC)/231.8877.62N/A21.824.84min(AIC)N/A59.02N/AN/A6.51min(BIC)33.2189.8813.0222.614.84min(AIC*BIC)N/A16.6217.0116.454.33min(AIC+BIC+(AIC*BIC))N/A17.2517.0116.454.50區間總數min(AIC+BIC)/2152205N/A804.33min(AIC)N/A263N/AN/A7.35min(BIC)13717859601.16min(AIC*BIC)N/A78051907.00min(AIC+BIC+(AIC*BIC))N/A76751906.82

因此,我們為確定最佳模型選擇標準進行了敏感性分析,即在DAGMM算法中確定高斯分量的數量.每個候選標準被用來確定在DAGMM算法中分量的數量.接下來,關聯分類被應用到離散化的數據集.表2提供了運用5折交叉驗證方法產生的詳細結果.根據整體排名,min(BIC)提供最好的結果,因此被用來在DAGMM算法中確定高斯分量數.其中,N/A表示在支持度和置信度分別設置為0.3和0.9時關聯分類器無法提取任何規則.

4.4 DAGMM算法的性能

把六個靜態離散化算法與DAGMM算法進行比較.離散化算法的參數根據經驗或根據現有的文獻進行設置.將1R算法的每個區間數據點的最小數目設置為6.EW算法儲存數量和EF算法每一個箱中儲存的數據點設置為5.最后,用30個分量的最大值設置迭代45000次,得到DAGMM算法和RGMM算法的EM參數.圖4和表3展示了把關聯分類應用于離散化數據集得到的詳細結果.

從圖4可以看出,DAGMM算法在生成較少的規則時,就可以達到較高的分類準確度.同一種疾病中的空白間隔代表未生成規則.根據總體排名,和其他靜態離散化算法相比,DAGMM算法產生了更好的結果.此外,只有四個離散化算法(DAGMM,1R,EW,EIRDC)能夠以高支持度和置信度在測試集上提取規則.以高支持度和置信度值提取規則意味著這四種算法都能保持原始連續數據集的最頻繁模式,而其它兩種方法(CACC,EF)是無法保持此模式的.

圖4 DAGMM算法和六個靜態離散化算法在四個數據集上執行結果的比較Fig.4 Comparison of the results of the DAGMM algorithm and six static discretization algorithms on four datasets

表3 離散化數據集得到的詳細結果
Table 3 Results obtained by a discreting datasets

離散化方法分類準確度平均排名產生規則的平均值平均排名區間總數平均排名總體排名DAGMM1.162.493.003.65RGMM4.674.672.679.33EF5.515.165.5010.671R3.331.504.174.83EIRDC3.084.764.197.52CACC3.174.604.337.67EW4.003.502.167.50

實驗結果表明,所測試數據集的基本分布不影響DAGMM算法的性能,而它對其他測試離散化算法的性能有顯著影響.特別是,EIRDC 算法和CACC算法的性能相差不大,但CACC算法在含有很多異常值的數據集中不能很好地執行.通過運用關聯分類器產生大量的規則來看,1R算法執行的很好.然而,對不平衡數據集的分類準確度不好.在EF算法中,兩種觀測得到的同一個值可能被分到不同的區間,這會導致數據集的原始分布發生相當大的改變.初始分布的變化改變了連續數據集的模式和,并使關聯分類器的性能變差.RGMM算法適合基于熵和信息損失的最優高斯混合模型,并根據最大概率準則分配給每一個高斯混合分量一個新的樣本.RGMM算法利用信息理論擬合最優高斯混合模型,而DAGMM算法使用BIC準則確定最優的高斯混合模型.RGMM算法和DAGMM算法之間的另一個主要區別是,RGMM是無監督離散化方法而DAGMM是有監督的離散化方法.根據等式(1-7),用∑i|C代替∑i,其中C指類標簽.因此,DAGMM算法考慮在離散化過程中的類標簽信息.然而,運用∑i|C也意味著每一個變量必須符合C高斯混合模型,這就增加了DAGMM算法的計算時間.最后,RGMM和DAGMM之間的其他區別是新數據點的離散方式不同.更具體地說,RGMM算法的新數據點xt被分配到高斯分量Gi,其滿足arg maxip(xt|Gi).而在DAGMM算法中,新數據點被分配到最近的間隔arg minint‖χt-γint‖,在每個區間(int)對應[μ-3σ,μ+3σ]適合于高斯混合模型分量,γ代表每個區間的中點值.因此,DAGMM算法比RGMM算法更容易理解.

5 結 論

離散化是現代專家系統設計不可分割的一部分,也是從大量的數據中提取邏輯規則必不可少的.可在臨床專家系統中運用DAGMM算法,有潛力提高以規則為基礎的分類器的性能.DAGMM算法的潛在應用是設計臨床決策支持系統,為醫生提供可解釋的結果.本文提出的DAGMM算法,它考慮了原始連續變量的多模態分類密度.DAGMM算法使用統計模型選擇準則平衡離散化過程中的信息損失和復雜性的降低,從而轉化為更高的分類精度,和更低的以規則為基礎分類的規則數目.高斯混合模型的局限性之一是確定高斯分量的最佳數量.在本文中,使用了一個啟發式方法,適合不同數量分量的高斯混合模型,并根據BIC準則選擇最好的分量數目.然而,這種方法的計算是耗時的,我們仍然需要為高斯分量的最大數量提供一個上限.假設最佳分量數是已知的,使用EM算法擬合高斯混合模型的計算仍然是耗時的.因此,需要進一步分析確定DAGMM算法的復雜性和提高計算效率.最后,DAGMM算法沒有考慮到在離散化過程中變量之間的相互關系,而是考慮了數據集中獨立變量之間的相互關系,可以提高離散化算法的性能,并在離散化過程中提供新的見解.針對DAGMM算法的不足,需在未來對其復雜度和計算時間方面進一步進行研究.

[1] Kononenko I.Machine learning for medical diagnosis:history,state of the art and perspective[J].Artificial Intelligence in Medicine,2001,23(1):89-109.

[2] Zhou Zhi-hua,Jiang Yuan.Medical diagnosis with C4.5 Rule preceded by artificial neural network ensemble[J].Information Technology in Biomedicine,IEEE Transactions on,2003,7(1):37-42.

[3] Nura Esfandiari,Mohammad Reza Babavalian,Amir-Masoud Eftekhari Moghadam,et al.Knowledge discovery in medicine:current issue and future trend[J].Expert Systems with Applications,2014,41(9):4434-4463.

[4] Peter B Jensen,Lars J Jensen,S?ren Brunak.Mining electronic health records:towards better research applications and clinical care[J].Nature Reviews Genetics,2012,13(6):395-405.

[5] Maslove,David M,Podchiyska,et al.Discretization of continuous features in clinical datasets[J].Journal of the American Medical Informatics Association,2013,20(3):544-553.

[6] Paul R,Harper.A review and comparison of classification algorithms for medical decision making[J].Health Policy,2005,71(3):315-331.

[7] Huan Liu,Farhad Hussain,Chew Lim Tan,et al.Discretization:an enabling technique[J].Data Mining and Knowledge Discovery,2002,6(4):393-423.

[8] Cheng-Jung Tsaia,Chien-I.Leeb,Wei-Pang Yangc.A discretization algorithm based on class-attribute contingency coefficient[J].Information Sciences,2008,178(3):714-731.[9] Reynolds D.Gaussian mixture models[J].Encyclopedia of Biometrics,2009,3(4):93-105.

[10] Zhu Wen-zhi,Wang Jing-cheng,Zhang Yan-bin,et al.Discretization algorithm based on effective information ratio[J].Xi′an Jiaotong University Xuebao,2011,45(4):12-18.

[11] Cai Rui-chu,Hao Zhi-feng,et al.Regularized gaussian mixture model based discretization for gene expression data association mining[J].Applied Intelligence,2013,39(3):607-613.

[12] Xu Lei,Jordan.On convergence properties of the EM algorithm for gaussian mixtures[J].Neural Computation,1996,8(1):129-151.

[13] Qiao Shao-jie,Jin Kun,Han Nan,et al.Trajectory prediction algorithm based on gaussian mixture model[J].Journal of Software,2015,26(5):1048-1063.

[14] Sun Yan-min,Andrew K C Wong,Yang Wang.An overview of associative classifiers[C].International Conference on Data Mining,2006.

[15] Pan Xiao-chuan,Sidky,et al.Advanced signal processing handbook:theory and implementation for radar,sonar,and medical imaging real-time systems[J].Medical Physics,2003,30(5):234-240.

[16] Wang Wei-ping,Zhou Zhong-mei,Zheng Yi-feng,An improved associative classification approach based on support and enhancement ratio[J].Computer Engineering&Science,2016,30(2):370-375.

[17] Byram G M,Nelson,et al.Multimodel inference:understanding AIC and BIC in model selection[J].International Journal of Wildland Fire,2012,21(2):261-304.

附中文參考文獻：

[10] 諸文智,王靖程,張彥斌,等.應用有效信息比率的離散化算法[J].西安交通大學學報,2011,45(4):12-18.

[13] 喬少杰,金 琨,韓 楠,等.一種基于高斯混合模型的軌跡預測算法[J].軟件學報,2015,26(5):1048-1063.

[16] 王衛平,周忠眉,鄭藝峰.基于支持度和增比率的改進關聯分類算法[J].計算機工程與科學,2016,30(2):370-375.