屬性動態更新的一種三支決策模型

徐 怡，孫小軍

(安徽大學 計算機智能與信號處理教育部重點實驗室，合肥 230601)

(安徽大學 計算機科學與技術學院，合肥 230601)

1 引 言

三支決策理論最初由Yao教授提出的[3]，是近些年來出現的新的決策分析理論，可以用于處理不完整、不精確信息.三支決策模型作為傳統二支決策模型的重要擴展，考慮了決策過程中的諸多不確定性因素，在處理過程中，當信息不足以決定接受或拒絕時，將延遲決策作為的第三種決策行為.目前，三支決策理論已被廣泛應用于人臉識別[4]、醫療診斷[18]、推薦系統[5]等多個領域中.

粗糙集和決策粗糙集理論[1]是三支決策研究的起源，三支決策的正域、邊界域和負域可以通過通過粗糙集的上下近似集給出一定的語義解釋.在粗糙集理論模型中，Yao引入了 Bayes風險決策方法，依據最低風險代價，把對象劃分到正域、負域和邊界區域，從而形成了三支決策的接受決策、拒絕決策和延遲決策的三支決策語義[2].近年來，許多學者研究了將樸素決策理論轉化為理論體系、信息處理模型或計算方法的問題，已取得顯著進展的三支決策模型及其應，例如三支聚類分析[6，7]，過濾垃圾郵件[8]，三支決策空間[12]，代價敏感三支決策[9，11]，三支決策概念分析[13，14]等.許多關于三支決策理論的研究都是基于相應的決策背景及其應用.例如，Li和Zhou[15]結合決策者不同的風險偏好，提出了一種基于決策理論粗糙集的新決策模型.Yang和Yao[16]提出了一種多級代理三支決策模型，描述了當不同的用戶根據自己的標準給出不同的決策集時，如何制定一個全面一致的決策標準.Yang和Li[20]提出一種基于三支粒計算的混合數據融合的方法.Luo[17]提出一種基于多源信息系統構建三支決策的方法以及在系統中的應用.

然而，對于接受區域內的對象數量固定且實時劃分對象的情況，在目前研究領域中很少有人提出相關的三支決策的模型和理論.當論域U是排序的屬性值時，Zhang[10]等提出了一種基于標準差構建最佳偏差以及動態的更新屬性值的三支決策模型，但Zhang沒有考慮屬性值更新前后的關聯性以及重要程度.本文考慮屬性值更新過程中的聯系以及重要程度，提出一種基于基尼系數來構建離散度偏差，動態更新屬性，動態的計算一對閾值來構建三支決策，是一種基于屬性更新的動態決策模型.

在一些在線實時評判系統中，需要實時的篩選出一批對象，評判的數據不是一次性都到達，而是隨著時間逐漸獲取，且需要在每個時刻都要選出一批對象，現已如下場景為例：

假設需要實時考核，選拔k個優秀學生，通過成績從高到低排序，每次考核選出部分學生和淘汰部分學生.運用三支決策分類算法，每次將一批學生分類到三個不相交的區域：POS、BND和NEG，其中POS區域中是選中的學生，NEG區域中是淘汰的學生，而BND區域中是不能確定結果的學生，需要繼續考核.通過t次考核，從N個學生中選擇k個 “最優” 的學生作為最佳的分類(N>k).

對于這種實時多次的考核，如果運用二支決策思想，直接在某次考核中把前k個最高成績的同學當作最佳分類，如果有的學生本次考核不良，即使下次考核表現優異，但也錯失分類成優秀學生的機會.顯然這種二支決策的方法過于直接和武斷.容錯性較差，缺乏處理不確信性的能力.

而本文所提出的基于基尼系數構建離散度的三支決策模型能很好的解決該問題，克服二支決策的問題，提高容錯性和處理不確定性的能力，能夠處理實時數據的劃分問題，同時解決屬性值更新過程中的關聯性和重要程度問題.本文第一節簡要介紹了粗糙集和三支決策理論；第二節介紹了基于基尼系數構建離散度的三支決策模型及相關定義.第三節通過對比基于標準差的三支決策算法(FEAOAV)[15]的實驗驗證了算法的可行性和有效性.最后總結全文.

2 粗糙集與三支決策理論

定義1.序信息系統S=(U,AT,V,f)被定義為一個四元組，其中，論域U為非空有限的對象集合；AT為非空有限的屬性集合，?a∈AT；V是全體屬性的值域集合，即V=VAT=∪a∈ATVa；f表示信息函數，?x∈U，定義f(x,a)表示x在屬性a上的取值，則有f(x,a)∈Va，且滿足序關系(f(x,a),≥).

定義2[1].序信息系統S=(U,AT,V,f)，?a∈AT，?X?U，概念X的下、上近似集合分別定義為：

其中[x]a表示x在a上的等價類.

定義 3[10].根據子集X的下、上近似集合，可將論域劃分為3個互不相交的區域：正域POS(X)、邊界域BND(X)和負域NEG(X)，將其分別定義如下：

由正域中元素導出的規則表示確定屬于X的規則，由負域中元素導出的規則表示確定不屬于X的規則，而由邊界域導出的規則表示可能屬于X的規則，這體現了“三支決策” 的基本思想.

3 基于基尼系數的動態三支決策模型

對于后續出現的對象集，如無特別說明，則默認為：對象集U={x1,x2,…,xn}表示本次要劃分的重新降序排列后的對象集合，不包括“上次”已經劃分到正域POS和負域NEG中的對象.對象的屬性值都為數值型.

3.1 屬性的動態更新

文獻[10]敘述屬性動態更新的三支決策劃分過程，現簡要介紹：

有對象集U={x1,x2,…,xn}，Zi={z1,z2,…,zm}為U中對象xi的m個屬性值的集合，現需要選出k個“優秀”的對象.在第j次決策(j

·將確定為“優秀”的對象直接劃分到POS接受區域中，然后完成所有屬性值的更新.

·那些可能是“優秀”的對象被放入BND延遲區域，然后再次更新它們的屬性值，之后再對它們進行劃分.

·不是“優秀”的對象直接放入NEG拒絕區域.重復上述過程，直至POS接受區域的對象的數量等于k.

在實際操作中，如果最終更新后的對象的數量沒有達到k，直接從前面BND延遲區域(不足，則繼續從拒絕區域NEG)選擇一部分擁有更高的屬性值的對象納入到對象的POS接受區域，使POS接受區域數量等于k.

在上面的決策過程，更新的屬性值的重要程度不同且有一定的關聯性，在“理想”的決策過程中，一個對象是否是“優秀”的對象，不能直觀地知道.在一個連續的決策過程中，決策是一個價值更新的動態過程.當固定接受區域內的對象個數和對象的屬性逐個獲取，本文將給出基于基尼系數的三支決策模型，利用基尼系數動態計算閾值，動態的劃分出“優秀”的對象.

定義 4.序信息系統S=(U,AT,V,f)，設U={x1,x2,…,xn}是第t次更新后對象集，V={v1,v2,…,vn}是U中對象的第t個屬性的值域的集合，則xi在第t次更新后(第t個屬性)的值域定義如下：

(1)

給予對象xi在每次更新后的值一個權重b，能夠體現每次更新的重要程度，同時定義4將每次更新的值關聯起來.

定義 5.(屬性比)序信息系統S=(U,AT,V,f)，令U={x1,x2,…,xn}是對象集，其中a∈AT，a(xi)表示m在屬性a下的值，對于一個屬性a的值為數值型，對象xi的屬性比定義如下：

(2)

從屬性比的定義可以得出以下兩個結論:

·如果兩個對象屬于一個等價類，則它們具有相同屬性比.(如果兩個對象xi和xj的屬性a的值相等，則認為在a屬性下xi和xj屬于同一個等價類，即[xi]a=[xj]a.

·對象同一屬性下值域越高，對應的屬性比越高.

定義 6.(基于屬性比的三支決策模型)序信息系統S=(U,AT,V,f).對于X?U，帶有一對閾值(α,β)，(0≤β≤α≤1) 的上下近似集定義分別為：

(3)

(4)

U可以分為三個互不相交的區域，即接受區域、延遲區域和拒絕區域，如下所示.

(5)

(6)

(7)

接受區域內的所有對象都是“優秀”對象，拒絕區域內的所有對象都是“淘汰”對象，在當前條件下，延遲區域內的對象都不容易清晰判斷，需要進一步觀察.

在定義6中，當α和β的閾值確定，所有的對象可以劃分到接受區域，延遲區域，或拒絕區域.在動態決策的整個過程中，對象的屬性值和接受區域內所需的對象數量都可能發生變化.因此，相應的自適應閾值α和β需要改變.因此，本文研究的下一個目標是在給定可接受區域內的對象數量和屬性值時，尋找一對自適應閾值.

3.2 自適應閾值的計算

為了確定閾值α和β，必須選擇一個適當的特征提取方法.因此，本節根據離散集的數學特征提出一種新的偏差概念定義如下

定義 7[19].(基于基尼系數的偏差)定義U={x1,x2,…,xn}是對象集，Vn={v1,v2,…,vn}是U中對象在屬性a下值域的集合，U滿足序關系f(xi,a)≥f(xi-1,a)，即vi≥vi-1，則，

dn=Gn-Gn-1是對象xn的偏差.

(8)

Vn-1比Vn少一個元素vn，當Vn-1中加入一個元素vn時，即Vn-1變成Vn時，Vn-1的離散度可能會變化，這種變化的程度可以歸結為增加了一個元素在其中，偏差的概念反應這一動作的影響程度.

·當dn>0時，我們說元素vn的加入對集合Vn-1有一個負的影響；

·當dn<0時，我們說元素vn的加入對集合Vn-1具有正影響；

·當dn=0時，我們說元素vn的加入對集合Vn-1沒有影響.

例1.假設有兩個集合V3和V4，按值降序排序，其中V3={2,3,5}和V4={2,3,5,10}，計算d4.

第1步.計算兩個集合的和：

第2步.計算G3：

第3步.計算G4：

第4步.計算出d4=G4-G3=0.125.

在上述數學分析的基礎上，提出一種基于基尼系數的對象屬性值偏差的算法(FEBOG)，用于實際的優化選擇過程.該算法的基本目的在一次決策中，得到一組對象的偏差值.

算法 1.計算一組更新后屬性值集合的偏差值.

輸入：更新后屬性值域的降序集合Vn={v1,v2,…,vn}；

輸出：偏差值集合D={d1,d2,d3,…,dn}.

Step 1.利用Sn集合構造序列集合

V1={v1}；V2={v1,v2}；V3={v1,v2,v3}…Vn={v1,v2,v3,…,vn}.

Step 2.計算每個集合的基尼系數.

G0=0；G1=0；

…

Step 3.計算對象偏差序列

d1=G1-G0；d2=G2-G1;
d3=G3-G2;…dn=Gn-Gn-1

Step 4.得到離散度偏差集Dn={d1,d2,d3,…,dn}.

上述算法步驟表明，對象的特征(對象的偏差值)基于集合的基尼系數計算.對象的偏差值可以反映對象加入集合后對集合離散度的影響.因此，決策模型中對象的偏差值的意義可以重新解釋如下：

讓Xj-1={x1,x2,x3,…,xj-1}表示“優秀”對象集.另一個對象集Xj={x1,x2,x3,…,xj-1,xj}，通過FEBOG算法算得對象的屬性值特性dj.

·dj>0代表的元素xj有一個負面影響，這降低了Xj-1整體的優秀程度；

·dj<0代表的元素xj有一個積極的效果，提高了Xj-1整體的優秀程度；

·dj=0代表的元素xj沒有效果，對Xj-1整體的優秀程度沒影響.

對于屬性值動態更新，文獻[10]提出一條規則：對象的屬性值越低(高)，其增量就越大(低).并且進一步闡述了：如果xi和xj是兩個在a屬性下具有最大偏差的對象，則xi和xj可以作為論域U的兩個分類點，最合適的決策閾值α和β能夠被xi和xj的屬性比獲得，論域U可以被分為三個不想交的區域POS，BND，NEG.

一次決策過程是，根據屬性值由高到低的順序，依次將對象添加到“優”對象集中.當一個屬性值較低的對象被添加到一個“優”對象集中時，“優”對象集的離散度降低.顯然，通過FEBOG算法可以得到集合離散度的變化，即每個對象的偏差值表示其在這個過程中的影響程度.如果一個對象的影響程度高于添加到“優秀”對象集中的任何其他對象的影響程度，這意味著在添加此對象之前，“優秀”對象集已經是穩定且集中的.因此，根據每個對象的最優偏差，可以將域分為三個相對穩定且集中的對象集，分別為接受區域、延遲區域和拒絕區域.

圖1 一次三支決策形成的區域Fig.1 Region formed by one time three-way decision

因此，在一次決策過程中，自適應分類方法可以描述為:域的三個區域如圖1所示，其中k表示給定的被接受區域內的對象數量，U={x1,x2,x3,…,xn}表示根據屬性值由高到低設置的對象集.應用FEAOAV可獲得各目標的最優偏差.

首先，k是U的一個分類點；U分為兩個不相交子集X1={x1,x2,…,xk}和X2={xk+1,xk+2,…,xn}.然后，假設1≤i≤k和k+1

POS(α,β)(X)={x1,x2,…,xi-1}
BND(α,β)(X)={xi,xi+1,…,xj-1}
NEG(α,β)(X)={xj,xj+1,…,xn}

(9)

因此，閾值α,β能夠通過以上分析得出：

(10)

(11)

3.3 劃分異常情況的解決

該算法會出現以下幾種情況：

1)前m次(m

假設要在t次分類中選出k個對象，令在前0.5t次分類中，如果劃分到POS正域中的個數m大于0.5k個，則每次只選出前a′個對象到POS正域，其中a′=0.5m，(0.5m

圖2 劃分次數過少的解決辦法Fig.2 Solutions for too small division times

如圖2所示，在第M次的分類點為xa和xb，但a>k，通過調整后分類點為xa′和xb，a′

2)在規定的t次分類中選出來的對象個數m小于k，此時可以在BND邊界域中選擇前k-m個具有最大值的對象作為需要的對象，如果邊界域對象個數不足，則繼續從負域中選擇相應的具有最大值的對象作為需要的對象.

圖3 接受區域對象個數不足的解決辦法Fig.3 Solution to the insufficient number of objects in the receiving area

如圖3所示，在第t次分類后的分類點為xa和xb，但a

算法 2.接受區域劃分k個對象的三支決策算法.

輸入：信息系統S=(U,AT,V,f)，需要選出的對象個數k，預計劃分次數t；

輸出：集合POSt的k個對象.

1)初始化，POSt=?，U={x1,x2,…,xn}，已選出的對象個數m=0，已劃分次數h=1，權重b=t-1；

2)對于(|POSt|

(2)根據算法1計算出Dn={d1,d2,…,dn}，找出兩個最大的值di和dj，對應的對象為xi，xj；

(4)根據定義6計算出：

POS(X)={x1,x2,…,xi-1}；
BND(X)={xi,xi+1,…,xj-1}；
NEG(X)={xj,xj+1,…,xn}.

(5)If |POS(X)|>0.5 &&h<0.5:

POS(X)取前0.5|POS(X)|個對象；

POSt=POSt∪POS(X)；
Else:POSt=POSt∪POS(X)；

(6)h=h+1，U=BND(X)；

3)If(|POSt|

4)輸出:POSt集合.

4 仿真實驗

4.1 模型的評估

文獻[10]中對具有屬性動態更新的三支決策模型給出了評估方法，分別衡量模型的精度性能，最優率，與“最優”分類結果的相似度.

代表三支決策分類結果與“最優”分類結果的相似度，越大越好，其中POS*(X)代表最優分類的對象集，是所有更新操作完成后，前k個最大屬性值的對象組成的集合.

代表三支決策分類的對象的屬性值總和與二支決策分類的對象的屬性值總和之差，衡量提出的模型的精度性能，其中POS(X)O表示二支決策模型接受區域的對象集.

代表最優率，也就是說，根據搜索“最優”分類結果過程中需要更新的對象數量，在三支決策過程中減少了更新的對象數量，其中，|NEGi(X)|代表第i層決策分到拒絕區域的對象個數，N代表決策對象的總數.

4.2 實驗分析

為了驗證本文算法的有效性，將其與文獻[10]中的FEAOAV算法進行比較.算法的仿真實驗環境為：Windows7操作系統，配置為Intel(R)Core(TM)i3-4170CPU@3.70GHz，內存為8GB，使用java語言實現算法.算法測試使用的4個數據集均來自UCI數據庫.在進行實驗之前，首先對數據進行處理，需要的數據的屬性是數值類型且值域范圍較大，所以選取數據集的部分數值類型屬性并改造屬性值，使得新屬性值為原屬性值加上0-g之間的隨機數(g為數據集的對象數)，改造后的數據集1的屬性數由23變為5，數據集2的屬性數由16變為5，數據集3的屬性數由15變為8，數據集4的屬性數由16變為8.如表1所示.

表1 實驗中使用的UCI數據集Table 1 UCI dataset used in the experiment

表2-表5為本文算法(FEBOG)和FEAOAV算法在不同數據集上的對比實驗結果，t為劃分次數，即為改造后的屬性數，N為總的對象數量，k為正域POS需要的對象個數，λ，μ，ν

表2 Anneal 數據集Table 2 Anneal dataset

表3 Zoo 數據集Table 3 Zoo dataset

表4 Credit 數據集Table 4 Credit dataset

表5 Letter 數據集Table 5 Letter dataset

為3個評估指標.其中，表2設置t=5，N=693，表3設置t=5，N=101，表4設置t=8，N=690，表5設置t=8，N=1544.為了確保數據的客觀性，實驗結果為運行50次后取的平均值.從表2-表5中可以看出所有數據集上，在不同的k值上，本文算法大部分的λ，μ，ν指標值大于FEAOAV算法，且隨著k的增大，λ，μ，ν值的增幅大于FEAOAV算法，說明本文算法在劃分性能優于FEAOAV算法.λ能達到0.9714，說明本文模型有較高的可行性.ν的值在0.3632-0.3632之間，說明對比“最優”分類結果，本文算法能夠減少0.3632-0.3632的對象的更新，表明具有較高的效率.所有的μ都大于0，表明在許多的動態決策問題上本文算法優于二支決策模型.

5 結 論

在接受區域的對象個數固定的這種情形時，人們通常采用二支決策的方法來解決問題的最優解.但是，由于更新過程中忽略了不確定性和成本，結果往往不合理，同時相應的三支決策模型沒有考慮屬性更新前后的關聯性和重要程度，且很多情況下需要實時多次的劃分，評判的數據隨著時間逐漸到來.為了解決這些問題，首先，提出屬性動態更新規則，建立更新前后的屬性的聯系和重要程度，然后根據對象的價值特征(偏差)和二支決策模型的不足，建立了一個動態的三支決策模型.然后，在給定目標屬性值排序的條件下，提出了一種基于基尼系數的屬性值特征提取算法FEBOG.并在此基礎上，提出了一種自適應劃分方法，并確定了一對閾值的計算方法，做到動態實時劃分.針對兩種分類異常情況，提出了解決方法.該模型可以在動態決策過程的最后獲得二支分類結果.最后進行了仿真實驗，實驗結果表明，基于FEBOG算法的三支決策模型在λ，μ，ν指標上部分優于基于FEAOAV算法的模型.本文模型適用于非監督學習，可以應用在一些選拔比賽中，每輪比賽選出和淘汰一批選手,直到若干輪后選出合適數量的選手.本文模型還可以應用在一些在線學習中，及時動態的處理到來的數據.