一種優(yōu)勢關系粗糙集近似集動態(tài)更新算法

洪智勇　李少勇

(五邑大學計算機學院　廣東 江門 529020)

0　引　言

粗糙集理論是波蘭科學家Pawlak在1982年提出的一種有效處理不確定性問題的數學工具，能夠智能化處理不精確、不一致和不完備的數據[1]。由于不要求具備先驗知識且運算過程簡單，因而粗糙集理論成為一種日益重要的智能信息處理工具，廣泛地運用在機器學習、知識發(fā)現、數據挖掘和決策分析等研究領域[2]。然而Pawlak粗糙集不能處理具有偏好序屬性域的信息[3]，為此，Greco等[4]提出了優(yōu)勢關系粗糙集模型。優(yōu)勢關系粗糙集模型是Pawlak粗糙集的一個擴展模型，主要創(chuàng)新是用一個優(yōu)勢關系替代Pawlak粗糙集中的等價關系；在論域上構造兩種信息粒(優(yōu)勢集和劣勢集)；把決策類向上和向下聯合作為被近似的概念求其近似集。這些創(chuàng)新使粗糙集理論具有了處理偏好信息的能力[5]，因此它被廣泛地運用在與多指標決策輔助和多指標排序相關的研究領域[6]。

在優(yōu)勢粗糙集方法中，近似集是在優(yōu)勢原則具有協調性的基礎上定義的。它要求評價對象的所有指標值都不差于一個參考對象時，評價對象才能歸到不差于參考對象所在的類中。然而，少量指標的不協調會減少下近似集中的對象數量，在一定程度上損失了從較大數據集中發(fā)現有用模式的機會。Greco等在減少優(yōu)勢原則約束基礎上，提出了一種變量協調的優(yōu)勢關系粗糙集方法，允許一些不協調的對象包含到下近似集[7-9]。由于協調性測度能夠用于控制上近似集和下近似集的大小，Baszczyński等[10]基于討論對象集、屬性集和優(yōu)勢關系單調性的結果提出了一種具有單調變量協調的優(yōu)勢關系粗糙集方法。隨后，他們針對變量協調優(yōu)勢關系粗糙集方法設計了一種連續(xù)覆蓋規(guī)則歸納算法(VC-DomLEM)用于生成最小決策規(guī)則集，能夠適用于有序和非有序數據[10]。Szel?g等[11]基于變量協調優(yōu)勢關系粗糙集方法構造了一個適用于多指標排序的偏好學習模型。

由于傳統(tǒng)的優(yōu)勢關系粗糙集方法并不能直接處理動態(tài)變化的數據，本文借鑒已有的利用優(yōu)勢關系粗糙集方法處理動態(tài)數據的研究成果，給出一種基于有序等價類進行信息粒合并的快速優(yōu)勢關系粗糙集近似集動態(tài)更新方法。當動態(tài)偏好序信息系統(tǒng)的對象集發(fā)生變化時，該方法能有效地提高優(yōu)勢關系粗糙集近似集更新速度。

1　預備知識

定義1[1]S=(U,A,V,f)表示一個決策信息系統(tǒng),式中：

(1)U表示論域，即一個非空有限對象集；

(2)A表示一個非空有限屬性集，A可以拆分成C∪g0gggggg，C表示非空有限條件屬性集，d是決策屬性；

(4)f:U×A→V是信息函數，它為每個對象的任一屬性都賦予一個信息值，即?x∈U和?a∈A，?f(x,a)∈Va。

?a∈C，由于a具有一個偏好序值域，因此在論域上有一個對應的偏好關系a，即?x,y∈U，如果f(x,a)≥f(y,a)則x關于屬性a偏好y，表示為xay。如果P?C，對?a∈P都有f(x,a)≥f(y,a)，稱x在P上優(yōu)于y，記為xDPy，DP表示基于條件屬性集P的優(yōu)勢關系和分別表示x的P優(yōu)勢集和P劣勢集。優(yōu)勢關系粗糙集方法把論域中的P優(yōu)勢集和P劣勢集稱為基本知識粒度。

2　基于有序等價類計算基本知識粒的方法

本文用ε(x)={f(x,a1),f(x,a2),…,f(x,ak)}表示對象x的可利用的k個屬性的值序列。如果對象x絕對優(yōu)于對象y，則可利用的k個屬性中至少存在一個屬性a滿足f(y,a)

定義2T={?,E}是一個有序等價類表，其中，E={E1,E2,…,En}是一組有序等價類,?={ε(1),ε(2),…,ε(n)}是有序條件屬性值序列集。?i∈{1,2,…,n}，ε(i)={f(y,a1),f(y,a2),…,f(y,ak)}是等價類Ei中任意對象y的k個條件屬性值。如果?r,s∈{1,2,…,n}且等價類Es優(yōu)于等價類Er，則ε(r)<ε(s)。如果rf(y2,aj)的屬性，那么f(y1,a)≤f(y2,a)，其中，y1∈Er，y2∈Es，a=a1,a2,…,aj-1。

例1表1是一個決策信息系統(tǒng)，P={q1,q2}是條件屬性集，d是決策屬性。

表1　決策信息系統(tǒng)

根據定義2，表2是基于表1的一個有序等價類表。

表2　有序等價類表

從定義2可知，如果ε(r)<ε(s)那么等價類Es優(yōu)于等價類Er，也就是說，等價類Es中任意對象的優(yōu)勢集包含等價類Er中所有對象。因此，等價類Es中任意對象優(yōu)勢集和劣勢集的定義可以改寫如下：

例2(繼續(xù)例1)計算論域U中每個對象的P優(yōu)勢集和P劣勢集。

3　基于有序等價類的知識粒動態(tài)更新

3.1　有序等價類的動態(tài)更新算法

輸入：新添加的對象集合X+及已有有序等價類表記為T。

輸出：更新后的有序等價類表記為T′。

(2) 比較E和E+中每個元素的ε；

(5) 得到更新后的有序等價類表T′。

算法1中第1步是計算有序等價類的增量，其復雜度為O(|X+|2|P|)。第2～4步是更新原有等價類，其復雜度為O(|E+||E|)。由于O(|X+|2|P|+|E+||E|)=O(|X+|2|P|)，因此更新算法復雜度遠小于從又開始計算有序等價類表的復雜度O(|U+X+|2|P|)。

五是輪養(yǎng)。該魚養(yǎng)殖具有廣泛的適應性，不論是單一養(yǎng)殖或者多品種立體混養(yǎng)，都可以采用輪捕輪放，分批上市，捕大留小，提高養(yǎng)殖效益。

3.2　基本知識粒的動態(tài)更新

4　實驗評估

基本知識粒的動態(tài)更新目的是為了更新近似集。本文的實驗設計思想是把動態(tài)更新知識粒的方法嵌入到原始的優(yōu)勢關系粗糙集方法近似集計算過程中，驗證該方法能否有效改善優(yōu)勢關系粗糙集近似集計算效率。

為了保證實驗的有效性，本文實驗數據集采用UCI中四個不同數據集car、glass、iris和wine。這4個數據集的基本信息見表3。

表3　實驗數據集基本信息

實驗平臺為一臺個人計算機(PC)，其配置為Inter(R)P6100 2.0 GHz，RAM2.0 GB和Windows 7。

4.1　添加對象實驗

分別把表3中4個數據集分成相等的兩個部分：測試數據集和備份數據集。首先計算出測試數據集的近似集，然后從每個備份數據集中隨機抽選出30、40、50、60和70個對象添加到測試數據集中，分別用動態(tài)和靜態(tài)算法計算基于它們的優(yōu)勢關系粗糙集近似集。基于靜態(tài)算法和動態(tài)算法的耗時，計算動態(tài)算法相對于靜態(tài)算法的加速比，結果見表4。

表4　插入多個對象時近似集更新加速比表

從表4中數據可看出，在四個不同的數據集上插入多個對象時，動態(tài)算法相對于靜態(tài)算法的加速比都超過了20，最高達94.068 7。同時，隨著插入對象數量的增加，加速比也隨之增大。表4中的加速比指標反映出動態(tài)方法具有明顯的性能優(yōu)勢，隨著插入對象數量的增加，優(yōu)勢越明顯。

4.2　刪除對象實驗

與添加對象實驗不同，直接把表3中4個數據集作為測試數據集計算近似集。然后從測試數據集中隨機刪除10、20、30、40和50個對象，分別用動態(tài)和靜態(tài)算法計算基于它們的優(yōu)勢關系粗糙集近似集。基于靜態(tài)算法和動態(tài)算法的耗時，計算動態(tài)算法相對于靜態(tài)算法的加速比，結果見表5。

表5　刪除多個對象時近似集更新加速比表

從表5中數據可看出，在四個不同的數據集上刪除多個對象時，動態(tài)算法相對于靜態(tài)算法的加速比都超過了8，最高達60.095 5。隨著刪除對象數量的增加，加速比也隨之減小。表5中的加速比指標反映出動態(tài)方法具有明顯的性能優(yōu)勢，隨著刪除對象數量的增加，優(yōu)勢下降。

總之，從實驗結果來看，不論是添加對象還是刪除對象，動態(tài)算法計算性能總是優(yōu)于靜態(tài)算法。

5　結　語

動態(tài)數據環(huán)境下的知識更新是大數據時代的知識發(fā)現研究的熱點問題之一，對合理、高效地利用數據進行輔助決策有重要意義。本文以優(yōu)勢關系粗糙集方法為研究對象，首次提出了一些能用于多對象添加或刪

除時優(yōu)勢關系粗糙集近似集更新的動態(tài)策略及其相應的算法。實驗驗證了動態(tài)方法是一種高效的優(yōu)勢關系粗糙集近似集更新方法，能夠用于少量對象頻繁更新的動態(tài)信息系統(tǒng)中。在以后的研究中，我們將進一步討論對象集、屬性集和屬性值同時變化的情況下優(yōu)勢關系粗糙集近似集的更新。

[1] Pawlak Z.Rough sets[J].International Journal of Computer & Information Sciences,1982,11(5):341-356.

[2] 于洪,王國胤,姚一豫.決策粗糙集理論研究現狀與展望[J].計算機學報,2015(8):1628-1639.

[3] Slowinski R.Rough Set Learning of Preferential Attitude in Multi-Criteria Decision Making[C]//International Symposium on Methodologies for Intelligent Systems.Springer-Verlag,1993:642-651.

[4] Greco S,Matarazzo B,Slowinski R.Rough sets theory for multicriteria decision analysis[J].European Journal of Operational Research,2001,129(1):1-47.

[5] Chakhar S,Ishizaka A,Labib A,et al.Dominance-based rough set approach for group decisions[J].European Journal of Operational Research,2016,251(1):206-224.

[6] Rawat S,Patel A,Celestino J,et al.A dominance based rough set classification system for fault diagnosis in electrical smart grid environments[J].Artificial Intelligence Review,2016,46(3):389-411.

[7] Greco S,Matarazzo B,Slowinski R,et al.Variable Consistency Model of Dominance-Based Rough Sets Approach[C]//Revised Papers from the Second International Conference on Rough Sets and Current Trends in Computing.Springer-Verlag,2000:170-181.

[8] Greco S,Matarazzo B,Slowinski R,et al.An Algorithm for Induction of Decision Rules Consistent with the Dominance Principle[C]//Rough Sets and Current Trends in Computing,Second International Conference,RSCTC 2000 Banff,Canada,October 16-19,2000,Revised Papers.DBLP,2000:304-313.

[11] Szel?g M,Greco S,Sowiński R.Variable consistency dominance-based rough set approach to preference learning in multicriteria ranking[J].Information Sciences,2014,277(2):525-552.

[14] Jia X,Shang L,Ji Y,et al.An Incremental Updating Algorithm for Core Computing in Dominance-Based Rough Set Model[C]//International Conference on Rough Sets,Fuzzy Sets,Data Mining and Granular Computing.Springer-Verlag,2009:403-410.

[15] Xiuyi Jia,Lin Shang,Jiajun Chen,et al.Incremental Versus Non-incremental:Data and Algorithms Based on Ordering Relations[J].International Journal of Computational Intelligence Systems,2011,4(1):112-122.

[16] Chen H,Li T,Da R.Maintenance of approximations in incomplete ordered decision systems while attribute values coarsening or refining[J].Knowledge-Based Systems,2012,31(7):140-161.

[17] Luo C,Li T,Chen H,et al.Incremental approaches for updating approximations in set-valued ordered information systems[J].Knowledge-Based Systems,2013,50(50):218-233.

[18] Luo C,Li T,Chen H,et al.Fast algorithms for computing rough approximations in set-valued decision systems while updating criteria values[J].Information Sciences,2015,299(C):221-242.

[19] Luo C,Li T,Chen H.Dynamic maintenance of approximations in set-valued ordered decision systems under the attribute generalization[J].Information Sciences,2014,257(2):210-228.

[20] Wang S,Li T,Luo C,et al.Efficient updating rough approximations with multi-dimensional variation of ordered data[J].Information Sciences,2016,372:690-708.