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

洪智勇　李少勇

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

0　引　言

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

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

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

1　預備知識

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

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

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

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

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

根據(jù)定義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)更新目的是為了更新近似集。本文的實驗設(shè)計思想是把動態(tài)更新知識粒的方法嵌入到原始的優(yōu)勢關(guān)系粗糙集方法近似集計算過程中，驗證該方法能否有效改善優(yōu)勢關(guān)系粗糙集近似集計算效率。

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

表3　實驗數(shù)據(jù)集基本信息

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

4.1　添加對象實驗

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

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

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

4.2　刪除對象實驗

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

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

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

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

5　結(jié)　語

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

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

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

[2] 于洪,王國胤,姚一豫.決策粗糙集理論研究現(xiàn)狀與展望[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.