[發明專利]粗糙集擴展模型中近似集動態更新方法

無效

• 申請號: 201110261884.2
• 申請日: 2011-09-06
• 公開（公告）號: CN102279839A
• 公開（公告）日: 2011-12-14
• 發明（設計）人: 崔剛;劉永文;付忠傳;王秀峰;暴建民;朱東杰;莫毓昌;郝亮;張必英;張策
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: G06F17/00
• 分類號: G06F17/00
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 楊立超

1.一種粗糙集擴展模型中近似集動態更新方法，所述方法是基于以下定義來實現的：

定義1：一個信息系統以四元組S＝(U，A，V，f)表示，其中，U：U＝{x₁，x₂，...，x_n}為對象的非空有限集合，稱為論域；A＝{α|α∈A}稱為屬性集；是信息函數f的值域，而V_α表示值域；表示信息系統的信息函數，f_α為屬性α的信息函數；

定義2：設U是一有限非空論域，C是U上的一個子集族，若且∪C＝U，則稱C為論域U的一個覆蓋，稱元組<U，C>為覆蓋近似空間；

定義3：設<U，C>為覆蓋近似空間，x∈U，則定義x關于<U，C>的最小描述為：

定義4：設<U，C>為覆蓋近似空間，對任意x∈U，N(x)＝∩{K∈C；x∈K}稱為x的鄰域；

結合定義3和定義4，容易得到N(x)＝∩md(x)；

定義3：設<U，C>為覆蓋近似空間，x∈U，則定義x關于<U，C>的最小描述為：

定義4：設<U，C>為覆蓋近似空間，對任意x∈U，N(x)＝∩{K∈C；x∈K}稱為x的鄰域；

結合定義3和定義4，容易得到N(x)＝∩md(x)；

定義5：設U是一有限非空論域，C是U上的一個子覆蓋，對于任意的X關于覆蓋近似空間<U，C>的下近似C(X)和上近似分別定義為：

C‾(X)={x∈U|∩md(x)⊆X},]]>

X關于近似空間<U，C>的正域pos_C(X)，負域neg_C(X)和邊界域bn_C(X)分別定義為：pos_C(X)＝C(X)，

negC(X)=~C‾(X),]]>

bnC(X)=C‾(X)-C‾(X);]]>

即覆蓋粗糙集模型是Pawlak粗糙集模型的推廣；

當時，稱X關于近似空間<U，C>可定義的，否則稱為粗糙的；

定義6：設覆蓋近似空間<U，C>，U是一有限非空論域，C是由屬性集B生成的覆蓋元所構成的U上的一個子覆蓋，對于任意的x∈X關于屬性集B的鄰域為：

N_B(x)＝∩{K∈C；x∈K}

定義7：設覆蓋近似空間<U，C>，U是一有限非空論域，C是由屬性集B生成的覆蓋元所構成的U上的一個子覆蓋，對于任意的X關于屬性集B的下近似集、上近似集、下邊界和上邊界分別定義為：

CB‾(X)={x∈U|NB(x)⊆X},]]>

Δ‾CB(X)=X-CB‾(X),]]>Δ‾CB(X)=C‾B(X)-X]]>

X關于屬性集B的正域負域和邊界域分別定義為：

posCB(X)=CB‾(X),]]>negCB(X)=~CB‾(X),]]>bnCB(X)=CB‾(X)-CB‾(X);]]>

其特征在于：所述方法的具體過程為：

步驟A、屬性集變化時近似集的性質分析過程為：

在覆蓋粗糙集中，一個覆蓋表示知識庫中的某種知識，覆蓋元代表知識粒，由覆蓋生成的集合逼近則代表基于知識庫對某事物的刻畫和描述；在信息系統中，根據對象的屬性值生成覆蓋元，所有的屬性生成的覆蓋元放在一起，構成論域U上的一個覆蓋，屬性集元素個數越多，則覆蓋元個數越多，由覆蓋生成的集合逼近則對某事物的刻畫和描述越精確；當屬性集變化時，由屬性構成的覆蓋發生變化，近而影響對給定的集合的上、下近似集及邊界域的變化；下面當屬性集變化時對近似集性質進行分析：

設<U，C>是一個覆蓋近似空間，即U是一個非空有限集合。A是U的屬性集，對于∀x∈U,]]>P={α1,α2,...,αn}⊆A,]]>則CP={Kα11,Kα12,...,Kα1m1,...Kαi2,...,Kαimi,...,Kαn1,Kαn2,...,...,Kαnmn}]]>構成的U一個覆蓋，向屬性集P添加一個屬性a，C_{a}＝{K_a1，K_a2，…，K_as}，則C_P∪{a}＝C_P∪C_{a}仍是U的一個覆蓋，此時有，且有N_P∪{a}(x)＝N_P(x)∩N_{a}(x)。相反，若從P中刪除一個屬性，則覆蓋元減少，NP(x)⊆NP-{a}(x);]]>

設屬性a∈A，P⊆A,]]>a∉P,]]>則CP‾(X)⊆CP∪{a}‾(X),]]>CP‾(X)⊇CP∪{a}‾(X);]]>

證明對于屬性集P，其構成的覆蓋為C_P，對于屬性集P∪{a}，其構成的覆蓋為C_P∪{a}＝C_P∪C_{a}，且CP⊆CP∪{a}.]]>設∀x∈CP‾(X),]]>則有NP(x)⊆X.]]>由引理1知，NP(x)⊇NP∪{a}(x),]]>則有NP∪{a}(x)⊆X,]]>即x∈C_P∪{a}(X)，所以有CP‾(X)⊆CP∪{a}‾(X);]]>

設∀x∈CP∪{a}‾(X),]]>則有NP(x)⊇NP∪{a}(x),]]>則即x∈CP‾(X);]]>所以有CP‾(X)⊇CP∪{a}‾(X);]]>

設屬性a∈A，P⊆A,]]>a∉P,]]>則Δ‾CP(X)⊇Δ‾CP∪{a}(X);]]>

設屬性a∈A，P⊆A,]]>a∉P,]]>則Δ‾CP(X)⊇Δ‾CP∪{a}(X);]]>

設屬性a∈A，P⊆A,]]>a∉P,]]>則bnCP(X)⊇bnCP∪{a}(X);]]>

設屬性集P⊆A,]]>a∈P，則CP‾(X)⊇CP-{a}‾(X),]]>CP‾(X)⊆CP-{a}‾(X);]]>

設屬性集P⊆A,]]>a∈P，則Δ‾CP(X)⊆Δ‾CP-{a}(X);]]>

設屬性集P⊆A,]]>a∈P，則Δ‾CP(X)⊆Δ‾CP-{a}(X);]]>

設屬性集P⊆A,]]>a∈P，則bnCP(X)⊆bnCP-{a}(X);]]>

步驟B、屬性集變化時近似集增量更新方法過程：

設覆蓋近似空間<U，C>，通過下面的定理來實現X的上、下近似的更新

設屬性a∈A，則

C_P∪{a}(X)＝C_P(X)∪C_{a}(X)∪Y

其中

設屬性集a∈P，則

CP-{a}‾(X)=CP‾(X)-Δ‾CP-{a}(X)]]>

設屬性a∈A，則

CP∪{a}‾(X)=CP‾(X)-Z]]>

其中

設屬性集a∈P，則

CP-{a}‾(X)=CP‾(X)∪Δ‾CP-{a}(X);]]>

步驟C、具體過程描述為：

當屬性增加時，信息系統關于新增屬性會形成新的覆蓋元，這些覆蓋元構成論域的一個覆蓋，那么新增屬性所形成的覆蓋元與原來屬性所形成的覆蓋元合并在一起也構成論域的一族覆蓋。對于近似集的更新，如果是采用靜態增量更新方法，那么，系統會把所有的覆蓋元合并在一起從新計算給定集合的上近似集、下近似集，會花費很多時間和空間去重復計算，為了節省時間和空間，以便更及時地去更新信息，則宜采用動態的更新方法，因為在屬性增加時，增加了新的覆蓋元，根據上近似集、下近似的定義及求解原理知，上近似集、下近似是所包含對象的最小描述的交集，那么所包含對象的最小描述的交集即對象的鄰域。屬性增加，對于給定集合中所包含的對象的鄰域的并集形成一種分解，如果增加屬性后集合X所包含的對象集的鄰域的并集大小沒有改變，那么說明添加的屬性對集合X的上近似集、下近似集沒有影響，即集合X的上近似集、下近似集大小不變；如果增加屬性后集合X所包含的對象集的鄰域的并集發生了變化，則說明添加屬性后對集合X的上近似集、下近集產生了影響，即集合X的上近似集、下近似集發生了變化，此時根據對象的鄰域與近似集的關系，利用動態增量更新方法對近似集進行增量更新效率更高。當某一屬性刪除時，由刪除該屬性后所形成的覆蓋元隨之減少，分析屬性刪除后，集合X所包含的對象集的鄰域的并集是否發生了變化，如果對象的鄰域的并集保持原大小，則說明屬性刪除對集合X的上近似集、下近似集并沒有產生影響，則集合X的上近似集、下近似集的大小保持不變；如果刪除某一屬性后對于給定集合中所包含的對象的鄰域變大，此時，可以利用對象的鄰域、集合的邊界域與近似集的關系，利用近似集動態增量更新算法進行更新；

步驟C1、屬性增加時近似集增量更新算法：

1.靜態新增屬性算法描述：

輸入：S＝(U，A，V，f)，X；

輸出：

具體步驟：

步驟1、計算由屬性集中單個屬性形成的覆蓋元，構成U的一個覆蓋C_P；

步驟2、對于x_i∈U，計算N(x_i)；

步驟3、若x_i∈U，且則將對象x_i加入到對象子集X的下近似集中，即{xi}⇒Cp(x)‾;]]>

步驟4、若x_i∈U，且則將對象x_i加入到對象子集X的上近似集中，即{xi}⇒CP‾(X);]]>

步驟6、增加一個新的屬性a產生新的覆蓋元，合并原來的覆蓋構成一個新的覆蓋

步驟7、重復步驟2、3、4，輸出算法結束；

2.動態增量更新算法描述：

輸入：S＝(U，A，V，f)，X；

輸出：

具體步驟：

步驟1、計算由屬性集中單個屬性形成的覆蓋元，構成U的一個覆蓋；

步驟2、對于x_i∈U，計算N(x_i)；

步驟3、若x_i∈X，且則將對象x_i加入到對象子集X的下近似集中，即{xi}⇒Cp(x)‾;]]>

步驟4、若x_i∈U，且則將對象x_i加入到對象子集X的上近似集中，即{xi}⇒CP‾(X);]]>

步驟5、增加一個新的屬性a產生新的覆蓋元，構成一個新的覆蓋，計算N_{a}(x)；

步驟6、如果∪x∈X(NP(x)∩N{a}(x))=∪x∈XNP(x),]]>則轉向第8步；

步驟7、如果∪x∈X(NP(x)∩N{a}(x))⋐∪x∈XNP(x),]]>如果NP(x)∩N{a}(x)⊆X,]]>則如果則

步驟8、輸出算法結束；

步驟C2、屬性減少時近似集動態增量更新算法：

1.靜態刪除屬性算法描述：

輸入：S＝(U，A，V，f)，X；

輸出：C_P(X)，

具體步驟為：

步驟1、計算由屬性集中單個屬性形成的覆蓋元，構成U的一個覆蓋C_P；

步驟2、對于x_i∈U，計算N(x_i)；

步驟3、計算X的上、下近似C_P(X)，

步驟4、刪除一個屬性a，構成一個新的覆蓋

步驟5、重復步驟1、2、3，輸出算法結束；

2.動態刪除屬性增量更新算法：

輸入：S＝(U，A，V，f)，X；

輸出：C_P(X)，

具體步驟：

步驟1、計算由屬性集中單個屬性形成的覆蓋元，構成U的一個覆蓋C_P；

步驟2、計算N_P(x)；

步驟3、計算X的上、下近似C_P(X)，

步驟4、刪除一個屬性a，構成一個新的覆蓋

步驟5、計算N_P-{a}(x)，若∪x∈XNP-{a}(x)=∪x∈XNP(x),]]>則CP^‾(X)=Cp(x)‾,]]>CP^‾(X)=CP‾(X),]]>轉向步驟7；

步驟6、若∪x∈XNP-{a}(x)⊃∪x∈XNP(x),]]>則CP-{a}^‾(X)={x∈NP-{a}(x)|NP-{a}(x)⊆X},]]>

步驟7、輸出算法結束。