差轉計算算法在連續型因素上的改進與應用

趙 靜，包研科

（1.黔南民族師范學院a.數學與統計學院；b.黔南州工業自動化與機器視覺重點實驗室，貴州 都勻 558000；2.遼寧工程技術大學理學院，遼寧 阜新 123000）

0 引言

因素空間（Factor Space）理論是統一描述隨機性和模糊性本質規律的數學理論，與認知科學交互，成為數據科學與智能科學的基礎理論和概念與知識表達的普適性框架。汪培莊等（2014）[1]發起并主導了因素空間在數據科學中的應用問題的討論。其間，包研科等（2014）[2]為將因素空間的思想與原理應用于多因素決策，克服經典的決策樹算法采用“貪心策略”導致的分類節點不可回溯、某些樹枝對應知識的支持度相對較小、知識的可靠性較低、很有可能使推理出來的知識存在系統誤差的問題[3,4]，提出了一種被稱為差轉計算（The Set Subtraction and Rotation Calculation，S&R）的多因素決策算法。該算法的決策機制建立在人腦解決分類問題的認知原理之上，在定性因素的多因素分類問題中取得了很好的實測效果。隨后包研科和茹慧英（2017）[5]在差轉計算算法原理的基礎上，修正了定量因素的決定度計算方法，拓展了差轉計算算法的應用場景。

自差轉計算算法被提出以來，其原理和方法得到了其他學者的關注。劉海濤等（2017）[6]對差轉計算算法進行了簡要介紹；汪培莊（2018）[7]較完整地介紹了差轉計算算法原理；劉海濤等（2017）[8]、曲國華等（2017）[9]對因素空間中因素分析法、差轉計算算法、模糊推理和粗糙集推理的異同進行了討論；茹慧英和包研科（2017）[10]、曾繁慧和李藝（2017）[11]討論了差轉計算算法在因素約簡問題中的應用。部分學者在分析故障概率和影響因素之間的關系問題時，借鑒了差轉計算算法的基本概念與原理，提出相應的知識挖掘算法[12—14]。趙夢輝（2016）[15]和李順鑫等（2018）[16]在安全系統評價問題的研究中，在分類算法相關研究中，對差轉計算算法的算法原理和過程進行了較為具體的驗證。呂子鋒（2018）[17]在基于擇近原則的圖像識別方法研究中對差轉計算算法的概念與思想亦有所借鑒。

差轉計算算法是一種基于認知本體論的數據挖掘算法，已有研究[4,5,10]表明，該算法在定性變量樣本集上對推理知識的挖掘和泛化性能要優于在定量變量的樣本數據集上的性能。本文在文獻[4,5]的基礎上，針對差轉計算算法在利用連續型因素進行決策時知識的可靠性低、泛化效果差和泛化過程存在一定判別風險的問題，在概率論與數理統計、因素空間理論背景下，結合差轉計算算法原理，提出適用于差轉計算算法的連續型數據離散化方法，同時定義了累積決定度、相對貢獻度用于描述推理知識的可信賴程度，并將本文所提離散化方法與差轉計算算法結合后應用于惡性腫瘤智能輔助診斷中。

1 差轉計算算法基本概念和原理以及離散化策略的提出

1.1 基本概念與原理

為方便理解，現對涉及的基本概念進行說明。

問題研究過程中所有研究對象構成的可列集合稱為研究論域，簡稱論域，記為，其中，ui為第i個研究對象。稱描述論域中研究對象ui的某一特征或表現的指標為因素，記為f。根據因素空間理論，論域U與因素f之間具有如下關系：

定義1：?ui?U(i=1,2,…,n)，存在特征di，使得di=f(ui)，若記由di構成的集合為If={di|?ui?U,di=f(ui)}，則稱If為因素f的相空間。

因素f是論域U到相空間If的滿映射，且特征di在應用過程中存在空置（di為缺失值）的可能，因素空間理論中的缺失值是一種特殊值，對其的處理過程參閱文獻[10]。

S&R算法以監督數據集為操作對象，稱監督數據中標簽數據對應的指標為結果因素，一般記為g；稱除結果因素外的其他指標為條件因素。S&R 算法以因素為認知工具，推理知識的提取由條件因素與結果因素在論域內形成的等價類確定，這個等價類由如下定義描述：定義2：設存在映射，滿足，則稱為因素f的回?溯。

其中，[d]f是對象ui經f在論域中構成的等價類；U/f是以[d]f為元素的商集。若設If={d1,d2,…,ds},s≤n，則有回溯是因素的廣義逆映射[5]。

定義3：設i為U中第i個對象ui的順序號，集合K={}i為U的秩序集。A是U中任意的含有s個對象的一般等價類，記K(A)={i1,i2,…,is}為A的秩序子集，并稱為A的表征，記為Rf(A) 。

注意，在定義3中，一般等價類A?U/f，因此f(A) 可能是多值的。僅當A?U/f時，f(A) 是單值的。

在處理多因素決策問題形成推理知識的過程中，下面幾個概念發揮著關鍵的作用。

定義4：設f、g是定義在論域U上的因素，稱為等價類[s]g在f上的蹤影。

蹤影的概念描述的是將結果因素g的分類信息投射到條件因素f上的結果。

下面以圖示的方法直觀說明前述定義所描述的概念及關系，假定對因素f的相態排序后形成圖1。

圖1 概念關系示意圖

決策討論的是論域中對象的歸屬問題，因素表征決策信息，提供決策參考，基于因素特征回到論域中進行討論是S&R算法的基本思想。因此，圖1中決策的本體關系是，而推理知識的形成以因素f為工具，知識表達蘊含在集合包含關系中，由此可誘導出決策推理知識為：若因素f的相態為t，則其結果為i。

基于前述內容，總結S&R算法的知識挖掘步驟，如圖2所示。

圖2 S&R算法流程圖

由此可以發現，S&R算法能反復使用條件因素進行知識挖掘，這與決策樹知識挖掘過程有較大不同；同時，S&R算法收斂以刪空數據集或最大決定度為0 為準則。但S&R算法存在兩個問題：一是連續型因素泛化效果差。根據文獻[18]中指出的“適度概括”原理，離散型因素適度概括性優，具有較高決策能力，因此知識泛化性好；連續型因素的測量存在不可逾越的截斷效應，其相態本質上是一個模糊截集表征數，概括性劣，信息“粒度”小，導致知識泛化性差。二是推理知識存在風險。由圖1可知，由包含關系誘導出的知識并未囊括結果出現的唯一性，易導致知識泛化過程存在一定的判別風險。但包含關系誘導出的決策準則（定義6）和知識是基于統計信息得到的結論，具有一定程度的可靠性。

針對問題一，本文給出一種全新的數據離散化方法；針對問題二，本文在定義7、定義8中給出統計背景下的知識蘊含因素可信賴程度計算方法。

定義7：設優勢因素f對訓練集共計操作m次，稱為因素f的累積決定度。其中，ni為因素f第i次操作時刪除的訓練集樣本數，N為訓練集樣本總數。

定義7描述了在整個知識挖掘過程中，因素f對知識集產生的貢獻，累積決定度越大，說明因素對知識集的貢獻越大。S&R 算法知識形成過程以因素f為操作工具，利用包含關系挖掘知識，并表述為“iff=t,theng=i”語句形式，在應用中，關系的發生是一種概率事件。根據這個思想和算法步驟，則推理知識“iff=t,th eng=i”的可信賴程度可由定義8描述。

定義8：設優勢因素f對訓練集共計操作m次，稱為相對貢獻度（簡稱貢獻度）。其中，為因素f在第j次操作中刪除對應因素g相態為p時的樣本數，nj為因素f第j次操作時刪除的樣本數。這個概念描述了知識“iff=*,theng=p”（*代表相態待定）的可信賴程度。

1.2 連續型因素離散化算法的提出

針對前述問題一，根據連續型因素的本質和“適度概括”原理[18]，以增加因素概括程度為目標，提出如下連續型因素的相空間的離散化方法。離散化的基本思想是將結果因素的信息反向作用到條件因素上，用結果因素在條件因素上的蹤影重構條件因素的相態值。

設D為論域U上的一個容量為n的多因素樣本數據集，其中，f是一個連續型條件因素，g是結果因素。不失一般性，記Ig={1,2,…,s}，則If的離散化過程如下：

（1）在數據集D上，按因素f的相態值升序（降序）擴展排序；

（2）記i(k)為因素g的相態i因f的排序形成的第k個聚集子塊，求i(k)在f上的蹤影；

（4）f相態離散化重標記規則由導出?？傻秒x散化知識為：若，則x=k。其中，。特別地，當k=1 時，；當k+1=N時，。

上述離散化方法結果是對If的切割，形成的是對Ig的細分，若依文獻[4]或文獻[5]的決策準則，則αf→g≡1，不能提供有效的決策信息。為此，本文修正了決策準則，見定義6。

2 實證分析

2.1 數據來源及數據特征說明

本文數據來源于UCI 共享數據庫中兩個較為經典的惡性腫瘤數據集：Wisconsin Breast Cancer Database 和Breast Tissue，分別簡記為WBCD 和BT。數據集WBCD 共有699個樣本，包含9類條件因素，條件因素簡稱、類型及值態范圍見表1。

表1 數據集WBCD的條件因素

數據集WBCD 有1 個結果因素，包含2 個相態benign和malignant，各有458和241個樣本。

文獻[19]和文獻[20]分別采用多曲面分割模式識別算法、概念相似性描述方法對該數據集進行模式識別，兩種方法均有較高的準確率，但未形成條件因素對結果因素之間的可解釋表達模型。本文認為在智能輔助診斷應用研究中，更具價值的模型知識是因果結構的，也就是說，條件因素對結果因素有解釋能力。文獻[21]利用主成分分析法、逐步線性回歸對該數據集因素間的關聯性和條件因素對結果因素的解釋能力進行了分析，發現UCSH和UCS是最大載荷因素，即這兩個因素能夠對benign和malignant的識別提供重要的診斷信息。同文獻[19]和文獻[20]相比，文獻[21]提供了更多的輔助診斷知識。

數據集BT共有106個樣本，包含9類條件因素和6類結果因素，其條件因素簡稱、類型及值態范圍見下頁表2，數據集BT包含的結果因素簡稱及樣本數見下頁表3。

數據集BT 原始數據源自文獻[22]，文獻[22]利用阻抗譜系統測定了64名接受乳房手術患者的切除組織樣本在9 個因素下的120 個光譜特征，基于光譜特征數據對組織樣本的阻抗特性進行了分析。相比文獻[22]，文獻[23]采用線性判別方法對數據集BT 進行模式識別，對惡性腫瘤的有效識別率約達92%，發現因素I0、MAXIP和ADA在診斷惡性腫瘤上能夠提供較高價值的輔助診斷信息。

2.2 數據預處理及評估方法說明

（1）數據預處理說明

對WBCD 數據集中的缺失值，本文按文獻[10]中的觀點和方法對之進行了處理；對WBCD數據集存在的所有條件因素相態一樣、但結果因素相態不一樣的樣本，由于其不蘊含推理知識，因此本文剔除此類樣本。

對S&R 算法的知識挖掘過程，因數據集WBCD 和BT中樣本數較少，本文對數據集的劃分采用如下方法：設訓練集與測試集樣本數之比為m:n，劃分時按該比例對結果因素相態按種類數進行隨機分層抽樣以劃歸到訓練集與測試集中，本文試驗中m:n=6:4,7:3,8:2,9:1。

（2）診斷的效果評估方法

為評估模型的診斷效果，本文采用分類準確率[24]、F1度量[24]、泛化時間[25]、累積決定度和相對貢獻度5個重要指標進行衡量，并以同為產生式推理算法的決策樹（C4.5）作為對比算法。針對前述的每一種分割比例，重復100次試驗，獲取5個評價指標的觀測結果，并報告均值化結果。

本文數據處理平臺為MATLAB 2016b，S&R 算法為自定義代碼，決策樹算法代碼源自文獻[26]。

2.3 差轉計算的知識挖掘與泛化性能

2.3.1 差轉計算在數據集BT上的知識挖掘與泛化性能

由于泛化性能會隨數據分割比例的上升而提高，因此本文僅報告9:1 數據劃分比例下的算法知識。在數據集BT上算法挖掘的知識如表4所示。

表4 差轉計算在數據集BT上挖掘的知識

以表4中第1、2條知識為例，說明知識的意義：第1條規則為“ifIP?[1563.8,2896.58],theng=Car”；若不滿足第1條規則，則順次比較第2 條規則“ifIPA500?[0.2006,0.36],theng=Fad”，以此類推。

由表4 可知，S&R 算法與決策樹最大的不同之處在于，在知識挖掘過程中，S&R算法直接對知識進行剪枝處理，知識結構表現為層間有序、層內無序的排列圖，結構較決策樹簡單。表4 的知識同文獻[22]相比，S&R 算法的知識更為明確。但對于S&R算法在數據集BT上得到的知識的實用性，還需要乳腺癌診治專業領域更多的實證研究。

S&R 算法與決策樹在數據集BT 上不同劃分比例下100次實驗的分類準確率、泛化時間和F1度量均值化結果對比見圖3。

圖3 數據集BT上S&R算法與決策樹泛化性能對比

由圖3（c）可知，S&R算法與決策樹綜合性能持平，由圖3（a）、圖3（b）可知，S&R算法分類準確率和泛化時間要優于決策樹，同時對比結果表明決策樹性能與劃分比例的關系不大，而S&R算法受到劃分比例影響，推理知識泛化性能與訓練集的結構有較大相關性。

在數據集BT 上及不同劃分比例下，經過100 次重復實驗挖掘出的知識集，其各因素的累積決定度如圖4 所示。

圖4 數據集BT上的推理知識中各因素累積決定度帕累托圖

由定義7和圖4可知，因素I0、P及PA500 的累積決定度的累積占比超過80%，其中，在4個比例下，因素I0的累積決定度最高，在0.338 附近波動，決策效用基本穩定；因素P累積決定度隨訓練集樣本量增加而增加，決策效用逐漸增大；因素PA500累積決定度隨訓練集樣本量增加而有所降低。根據帕累托圖解讀規則，因素I0、P及PA500構成識別惡性腫瘤（Car、Fad、Mas）的主要影響因素，對S&R 算法在該數據集上形成推理知識有較高的貢獻。

為更深入分析推理知識在識別惡性腫瘤過程中的可信賴程度，本文統計了數據集BT在不同劃分比例下的100次重復試驗所挖掘出的知識中各因素的相對貢獻度均值結果，見圖5。

圖5 數據集BT上的推理知識中各因素相對貢獻度帕累托圖

分析發現，I0、PA500 和P 是S&R 算法在不同比例下挖掘的用于識別惡性腫瘤推理知識的重要組成因素。在4個比例下，3個因素的累積相對貢獻度在50%以上，即可認為以上述3 個因素為組成部分的推理知識在識別惡性腫瘤過程中的可信賴程度為50%。其中：I0的相對貢獻度值最高，在20%左右；但隨劃分比例的上升，因素PA500和P 的相對貢獻度遞增，且因素P 增加幅度較因素PA500 更大，說明因素P 在識別惡性腫瘤過程中的效用逐漸增強。因此，有理由認為因素I0、PA500 和P 是識別惡性腫瘤的高價值參考因素。這個結論與文獻[22]稍有出入，但S&R算法知識更具可解釋性，關于診斷惡性腫瘤的主要參考因素還需腫瘤診治領域更多的實證研究。

2.3.2 差轉計算在數據集WBCD上的知識挖掘與泛化性能

在數據集WBCD上算法挖掘的知識如表5所示。

表5 差轉計算算法在數據集WBCD上挖掘的知識

S&R 算法與決策樹在數據集WBCD 上不同劃分比例下100次重復實驗的分類準確率、泛化時間和F1度量均值化結果對比見圖6。

圖6 數據集WBCD上S&R算法與決策樹泛化性能對比

在數據集WBCD 上，由圖6（a）可知，S&R 算法在分類準確率上的表現較決策樹更好，在泛化時間上不如決策樹，但隨訓練數據量增加，S&R算法泛化時間逐漸遞減，而決策樹泛化時間有增加趨勢；從綜合性能指標F1 度量來看，S&R 算法與決策樹綜合性能相當。綜合圖6 來看，兩個算法均受到了數據集劃分比例的影響。

在數據集WBCD上不同劃分比例下，經過100次重復實驗挖掘出的知識集中，各因素的累積決定度如圖7 所示。

圖7 數據集WBCD上各因素的累積決定度帕累托圖

根據圖7，在S&R算法在數據集WBCD上形成推理知識的過程中，不同因素的知識貢獻度存在波動，貢獻較為穩定的因素有USC、CT、BN和BC，其累積決定度波動均值及波動大小見表6。

由上述結果可知，4個因素對知識的貢獻度在75%左右。其中：因素CT累積決定度隨訓練數據量增加而遞增，因素UCS、BN對知識的貢獻更為穩定，因受到劃分比例影響，BC 的信息具有較小的參考價值；此外，貢獻度較大的因素還有MA 及UCSH，但這兩個因素受分割比例影響較大，貢獻極其不穩定。根據帕累托圖的解讀規則，本文認為因素USC、CT、BN、BC 和UCSH 對S&R 算法在數據集WBCD上形成推理知識有較高的貢獻。

S&R 算法在數據集WBCD 上的推理知識受不同劃分比例的影響較大，關注推理知識對識別benign的可信賴程度，圖8統計了數據集WBCD在不同劃分比例下的100次重復試驗所挖掘出的知識中各因素的相對貢獻度均值結果。

圖8 數據集WBCD上各因素相對貢獻度帕累托圖

由圖8 可知，在對形成推理知識有較大貢獻的因素USC、CT、BN、BC 和UCSH 中，包含因素CT、UCS、UCSH 的推理知識對識別benign 的相對貢獻度分別約為2.3%、3.7%、8.1%，說明因素CT、USC 和UCSH 對識別數據集WBCD的結果因素相態malignant更具優勢，在診斷中可用于對惡性腫瘤癥狀的排除。

表7反映了在能識別benign的推理知識中，具有較大相對貢獻度的因素的相對貢獻度占總相對貢獻度的比例。

表7 BN、NN、BC及MA的相對貢獻度占比

由前述圖表可知，因素NN 的相對貢獻度占比最大，且隨訓練集樣本量的增加，包含該因素的推理知識識別benign 的可信賴程度逐漸提升；而隨著訓練數據量的增加，包含因素BN、MA和BC的推理知識識別benign的可信賴程度逐漸下降。此外，因素SECZ 對識別兩類結果因素相態不具備突出貢獻。綜上，根據帕累托圖的解讀規則，本文認為在數據集WBCD 包含的9 個因素中，除SECZ 外的其他因素是區分benign和malignant的主導性因素，此結論與文獻[19]和文獻[20]中所描述的“沒有單獨的特征指標來區分benign、malignant”存在差異；與文獻[21]的研究結論有較大差別。

S&R 算法與決策樹和文獻[21]中的模型相比，使用更便捷，知識更具可解釋性。

3 結論

為解決S&R算法在連續型數據下挖掘出的推理知識可靠性低、知識泛化效果差和泛化過程存在一定判別風險的問題，本文提出了連續型數據的離散化方法，并構造累積決定度、相對貢獻度用于度量推理知識的可信賴程度。將離散化方法同S&R算法融合，以決策樹作為對比算法，在UCI 共享數據庫中兩個較為經典的惡性腫瘤數據集上進行實證分析，結果顯示：本文所提離散化方法是有效的，融合后的模型能提升知識泛化效果，綜合性能與決策樹相當，但知識結構更為簡單；根據構造的累積決定度指標能發現知識形成過程中貢獻較大的因素，根據相對貢獻度能度量推理知識的可信賴程度。