面向不完備混合數(shù)據(jù)的矩陣增量知識(shí)維護(hù)方法研究

黃倩倩，李天瑞，楊 新，王國(guó)強(qiáng)，胡 節(jié)

1(西南交通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，成都 611756)2(西南交通大學(xué) 人工智能研究院，成都 611756)

1 引 言

1982年，波蘭學(xué)者Pawlak在經(jīng)典集合論的基礎(chǔ)之上提出了粗糙集理論(Rough Set theory)[1，2].此后，該理論逐漸成為一種定量分析處理不精確、不一致和不完整信息與知識(shí)的有效數(shù)學(xué)工具.相較于模糊集和概率論等其他不確定性理論，粗糙集最大的優(yōu)勢(shì)在于其不需要任何鄰域的先驗(yàn)知識(shí)，就能有效地刻畫(huà)和分析不確定性問(wèn)題.近30年來(lái)，粗糙集理論和方法已被廣泛應(yīng)用于機(jī)器學(xué)習(xí)與知識(shí)發(fā)現(xiàn)、數(shù)據(jù)挖掘、模式識(shí)別和圖像處理等多個(gè)領(lǐng)域[3-7].

經(jīng)典粗糙集模型通過(guò)一個(gè)等價(jià)關(guān)系(滿(mǎn)足自反性、對(duì)稱(chēng)性和傳遞性)僅適用于處理名義型數(shù)據(jù).這大大限制了粗糙集的適用范圍.大數(shù)據(jù)環(huán)境下信息的全面感知，使得所獲得的數(shù)據(jù)不再局限于某個(gè)單一的數(shù)據(jù)類(lèi)型，其中名義型和數(shù)值型類(lèi)型共存于的混合數(shù)據(jù)是最為普遍的現(xiàn)象.為了運(yùn)用粗糙集理論處理混合數(shù)據(jù)，眾多學(xué)者開(kāi)展了一系列的工作研究粗糙集的各種拓展模型.針對(duì)數(shù)值型數(shù)據(jù)，最為常見(jiàn)的做法就是將數(shù)值型數(shù)據(jù)進(jìn)行離散化處理[8，9]，這就使得某些重要信息在轉(zhuǎn)化過(guò)程中丟失.因此，Lin等通過(guò)介紹了鄰域系統(tǒng)的概念，提出了鄰域粗糙集模型[10].Li等提出了基于鄰域的決策粗糙集模型用來(lái)處理包含噪聲的數(shù)值型數(shù)據(jù)[11].隨后，Hu等通過(guò)引入異構(gòu)歐式重疊距離函數(shù)來(lái)刻畫(huà)同時(shí)具有名義屬性和數(shù)值屬性的對(duì)象之間的關(guān)系，提出了一種基于δ-鄰域關(guān)系的鄰域粗糙集模型[12].Chen等將偏序關(guān)系引入具有名義型屬性和數(shù)值型屬性的混合有序決策系統(tǒng)中，介紹了優(yōu)勢(shì)鄰域粗糙集模型，并給出了面向混合數(shù)據(jù)的并行屬性約簡(jiǎn)算法[13].近些年來(lái)，鄰域粗糙集模型已經(jīng)吸引了眾多學(xué)者的注意并被廣泛應(yīng)用于多個(gè)領(lǐng)域[14-17].

考慮到現(xiàn)實(shí)環(huán)境中數(shù)據(jù)采集過(guò)程中設(shè)備故障、存儲(chǔ)介質(zhì)損壞、傳輸媒體堵塞和人為遺漏等因素，使得所收集的數(shù)據(jù)常常包含缺失值，即信息系統(tǒng)是不完備的.因此，如何高效地利用粗糙集理論和方法處理具有缺失值的信息系統(tǒng)已然成為當(dāng)前知識(shí)發(fā)現(xiàn)領(lǐng)域中的一個(gè)研究熱點(diǎn)[18-25].在對(duì)于具有缺失名義型數(shù)據(jù)和數(shù)值型數(shù)據(jù)的混合信息系統(tǒng)的研究過(guò)程中，Jing等通過(guò)定義了新的距離函數(shù)，并結(jié)合概率的方法，提出了一種基于容差關(guān)系的變精度容差鄰域粗糙集模型[26]；Zhao等基于鄰域容差關(guān)系提出了一種擴(kuò)展的粗糙集模型，并介紹了混合特征選擇方法[27]；與此同時(shí)，姚晟等提出了一種拓的不完備鄰域粗糙集模型，并構(gòu)造了一種基于鄰域混合熵的不完備鄰域粗糙集屬性約簡(jiǎn)算法[28]；黃恒秋等通過(guò)引入一種新的不確定距離度量函數(shù)，提出了基于聯(lián)系度距離函數(shù)的雙鄰域粗糙集模型[29].此外，錢(qián)文彬等基于一種新的完備鄰域容差關(guān)系，通過(guò)改進(jìn)不可區(qū)分類(lèi)的損失函數(shù)區(qū)間值的獲取方法，構(gòu)建面向不完備混合信息系統(tǒng)的三支決策模型[30].

基于以上的研究工作，我們發(fā)現(xiàn)現(xiàn)今的不完備混合信息系統(tǒng)中缺失值的含義僅僅局限于某一種語(yǔ)義解釋?zhuān)⒉贿m合處理“不關(guān)心值”和“丟失值”共存的不完備混合信息系統(tǒng).因此，本文將定義兩種新的鄰域關(guān)系，即鄰域特征關(guān)系和量化鄰域特征關(guān)系，并基于這兩種關(guān)系構(gòu)建拓展的鄰域粗糙集模型，從而有效地處理不完備混合信息系統(tǒng).此外，利用相關(guān)的矩陣和運(yùn)算，介紹粗糙鄰域近似知識(shí)的矩陣計(jì)算方法.最后，當(dāng)不完備混合信息系統(tǒng)中屬性隨著時(shí)間發(fā)生變化時(shí)，提出基于矩陣的增量知識(shí)維護(hù)機(jī)理和方法，這對(duì)豐富動(dòng)態(tài)知識(shí)更新和知識(shí)獲取理論有著重要的意義.

2 相關(guān)知識(shí)

2.1 不完備信息系統(tǒng)

傳統(tǒng)粗糙集理論中，設(shè)四元組S=(U,A,V,f)是一個(gè)信息系統(tǒng)，其中，U={u1，u2，…，un}和A={a1，a2，…，al}分別表示非空有限的對(duì)象集合和屬性集合;V=∪a∈AVa為所有屬性值的集合，Va表示屬性a的值域;f:U×A→V為一個(gè)信息函數(shù)，即:對(duì)于任意u∈U和a∈A有f(u，a)∈Va.特別地，若A=C∪D，其中C和D分別為條件屬性集和決策屬性集，那么信息系統(tǒng)稱(chēng)之為決策表.

定義1[1].給定一個(gè)信息系統(tǒng)S，對(duì)于任意子集Q?C，論域上關(guān)于Q的不可區(qū)分關(guān)系定義為：

RQ={(u，v)∈U2|?a∈Q，f(u，a)=f(v，a)}

(1)

顯然，不可區(qū)分關(guān)系RQ滿(mǎn)足自反性，對(duì)稱(chēng)性和傳遞性，因此是一個(gè)等價(jià)關(guān)系.若存在a∈C和u∈U使得f(u，a)=*或f(u，a)=?，那么信息系統(tǒng)S被稱(chēng)為不完備信息系統(tǒng)，其中“*” 和 “?” 分別表示 “不關(guān)心值” 和 “丟失值”.等價(jià)關(guān)系因其自身的局限性，并不能有效的處理不完備信息系統(tǒng).因此，Grzymala-Busse提出了特征關(guān)系[23]，其可被視為容差關(guān)系[18]和相似關(guān)系[20]的一種泛化表現(xiàn)形式.

定義2[23].設(shè)S為不完備信息系統(tǒng)，對(duì)于任意子集Q?C，論域上關(guān)于Q的特征關(guān)系定義為：

KQ={(u，v)∈U2|?a∈Q，f(u，a)=?∨(f(u，a)=

f(v，a)∨f(u，a)=*∨f(v，a)=*)}

(2)

由上述定義可知，特征關(guān)系KQ僅僅滿(mǎn)足自反性，不一定滿(mǎn)足對(duì)稱(chēng)性和傳遞性.對(duì)于任意一個(gè)對(duì)象u∈U，令KQ(u)表示u基于特征關(guān)系KQ的特征類(lèi)，即KQ(u)={v∈U|(u，v)∈KQ}.

定義3[23].設(shè)S為不完備信息系統(tǒng)，?X?U，Q?C.則X基于特征關(guān)系KQ的上、下近似集分別定義為：

(3)

2.2 鄰域粗糙集

通過(guò)從拓?fù)淇臻g中引入鄰域概念，Hu等提出了一個(gè)鄰域關(guān)系處理名義屬性和數(shù)值屬性共存的混合信息系統(tǒng)[12].給定一個(gè)信息系統(tǒng)S和一個(gè)閾值δ，?Q?C.對(duì)于任意一個(gè)對(duì)象u∈U，δQ(u)表示u關(guān)于Q的鄰域，即：

δQ(u)={v∈U|ΔQ(u，v)≤δ}

(4)

其中，Δ是一個(gè)距離函數(shù)(滿(mǎn)足正則性，對(duì)稱(chēng)性和三角不等性).目前，Minkowski距離，作為一個(gè)重要的度量函數(shù)，已被廣泛應(yīng)用于機(jī)器學(xué)習(xí)和模式識(shí)別領(lǐng)域，其定義如下：

(5)

當(dāng)p=1時(shí)，稱(chēng)為Manhattan距離；當(dāng)p=2時(shí)，稱(chēng)為Euclidean距離；當(dāng)p=時(shí)，稱(chēng)為Chebychev距離.

定義4[12].設(shè)S為一個(gè)信息系統(tǒng)，對(duì)任意子集Q=QC∪QS?C，其中QC和QS分別是名義型屬性集和數(shù)值型屬性集，論域上關(guān)于Q的鄰域關(guān)系定義為：

NQ={(u，v)∈U2|ΔQC(u，v)=0∧ΔQS(u，v)≤δ}

(6)

顯然，鄰域關(guān)系僅滿(mǎn)足自反性和對(duì)稱(chēng)性，不一定滿(mǎn)足傳遞性.因此，對(duì)于任意對(duì)象子集X?U，X基于鄰域關(guān)系NQ的上、下近似集定義為：

(7)

2.3 不完備混合信息系統(tǒng)

定義5.設(shè)S=(U，A，V，f)是不完備混合信息系統(tǒng)，其中：

1)U={u1，u2，…，un}是非空有限的對(duì)象集合，稱(chēng)為論域；

2)A=AC∪AS(AC∩AS=?)是非空有限的屬性集合，AC和AS分別為名義型屬性集和數(shù)值型屬性集；

3)V=∪a∈AVa，Va表示屬性a的值域；

4)f：U×A→V為一個(gè)信息函數(shù)，使得?a∈A，u∈U有f(u，a)∈Va；

5)存在某個(gè)屬性a∈A，使得f(u，a)=*或f(u，a)=?.

表1 一個(gè)不完備混合決策系統(tǒng)
Table 1 An incomplete hybrid decision system

Ua1a2a3a4du1210.52.0Nu2110.71.8Yu3?00.51.5Yu41?0.92.1Nu510?1.9Yu62?0.2?N

3 不完備混合信息系統(tǒng)中鄰域粗糙集模型

接下來(lái)，將介紹兩種新的鄰域關(guān)系(鄰域特征關(guān)系和量化鄰域容忍關(guān)系)來(lái)處理本文所提出的不完備混合信息系統(tǒng).

3.1 鄰域特征關(guān)系

定義6.設(shè)S是一個(gè)不完備混合信息系統(tǒng)，對(duì)任意屬性子集Q=QC∪QS?A，論域上關(guān)于Q的鄰域特征關(guān)系的定義為：

(8)

其中，δ為一個(gè)給定的閾值.

(9)

(10)

證明：

同理可證其余情況.

粗糙集理論中，近似分類(lèi)精度是一個(gè)非常重要的評(píng)價(jià)指標(biāo)，用于描述近似分類(lèi)的不確定性度量.

(11)

同理可證其余情況.

3.2 量化鄰域特征關(guān)系

受到數(shù)據(jù)驅(qū)動(dòng)數(shù)據(jù)挖掘思想的啟發(fā)，Wang等提出數(shù)據(jù)驅(qū)動(dòng)量化容忍關(guān)系處理由名義型數(shù)據(jù)組成的不完備信息系統(tǒng)[31].顯然，這種關(guān)系并不適合用來(lái)處理本文介紹的不完備混合信息系統(tǒng).因此，基于數(shù)據(jù)驅(qū)動(dòng)的思想，針對(duì)名義型數(shù)據(jù)和數(shù)值型數(shù)據(jù)，我們引入兩個(gè)新的度量函數(shù)，從而提出一個(gè)新的鄰域關(guān)系.

定義10.設(shè)S是一個(gè)不完備混合信息系統(tǒng)，A=AC∪AS.令ρC：U2×AC→和ρS：U2×AS→分別是關(guān)于AC和AS的兩個(gè)度量函數(shù)，具體定義如下：

(12)

和：

(13)

其中，λ1和λ1是閾值，且0≤λ1，λ2≤1.

表2 相關(guān)符號(hào)說(shuō)明
Table 2 Description of related symbols

符號(hào)含 義a∈AC一個(gè)名義型屬性b∈AS一個(gè)數(shù)值型屬性Via(1≤i≤m1)關(guān)于屬性a的第i個(gè)已知屬性值Vjb(1≤j≤m2)關(guān)于屬性b的第j個(gè)已知屬性值Ha屬性a下所有屬性值為已知值的對(duì)象集合Hb屬性b下所有屬性值為已知值的對(duì)象集合sia集合{u∈U|f(u,a)=Via}的基數(shù)njb集合{u∈U|u∈Hb→|f(u,b)-Vjb|≤δ}的基數(shù)

定義10中所涉及的相關(guān)符號(hào)的具體含義可見(jiàn)表2.注意，?a∈AC，?b∈AS，函數(shù)ρC和ρS具有如下性質(zhì)：

1.滿(mǎn)足正則性；

2.不一定滿(mǎn)足對(duì)稱(chēng)性，如ρC(u1，u4，a2)≠ρC(u4，u1，a2)；

3.不一定滿(mǎn)足三角不等性，如令λ1=0.5，有ρC(u1，u6，a2)=ρC(u6，u4，a2)=0和ρC(u1，u4，a2)=，則ρC(u1，u4，a2)>ρC(u1，u6，a2)+ρC(u6，u4，a2).

因此，ρC和ρS被稱(chēng)為偽度量函數(shù).

定義11.設(shè)S是一個(gè)不完備混合信息系統(tǒng)，對(duì)任意屬性子集Q=QC∪QS?A，論域上關(guān)于Q的量化鄰域特征關(guān)系的定義為:

(14)

證明：證明過(guò)程與性質(zhì)1的證明相似，故省略.

(15)

(16)

(17)

3.2 鄰域特征關(guān)系和量化鄰域特征關(guān)系之間的關(guān)系

基于上述兩種新的鄰域關(guān)系的定義，我們可以得到以下定理.

證明：

例2.表1給出了一個(gè)不完備混合決策系統(tǒng)，令δ=0.3和λ1=λ2=0.5.首先，基于決策屬性D，可得U/D={D1，D2}，D1={u1，u4，u6}和D2={u2，u3，u5}.其次，根據(jù)定義6有:

則可得關(guān)于D1和D2的一對(duì)近似集：

由定義8可得:

4 不完備混合信息系統(tǒng)中基于矩陣的近似集計(jì)算方法

通過(guò)引入決策矩陣、關(guān)系矩陣和相關(guān)的誘導(dǎo)矩陣，我們將介紹不完備混合信息系統(tǒng)中計(jì)算近似集的矩陣方法.

定義15.設(shè)U={u1，u2，…，un}為所有對(duì)象形成的集合，?X?U，則稱(chēng)為X的特征向量，其中:

(18)

(19)

1)DM=[G(D1)，G(D2)，…，G(Dm)]；

證明：根據(jù)定義15和定義16，易知結(jié)論成立，故此省略證明過(guò)程.

(20)

ΩQ=ΛQ·(MQ·DM)

(21)

(22)

?φi>0

(23)

基于以上對(duì)不完備混合信息系統(tǒng)中基于矩陣運(yùn)算的近似集構(gòu)造方法的討論和分析，我們?cè)O(shè)計(jì)了一種計(jì)算近似集的靜態(tài)算法，即算法1.

算法1.不完備混合信息決策系統(tǒng)中基于矩陣的近似集靜態(tài)計(jì)算算法.

Step 1.fori= 1 ton/*構(gòu)造決策矩陣DM的元素*/

forj=1 tom

if (ui∈Dj) then

dij=1；

else

dij=0；

end for

end for

Step 2.fori= 1 ton/*構(gòu)建矩陣MQ和ΛQ*/

λi=0；

forj=1 ton

mij=1；

λi=λi+mij；

else

mij=0；

end for

end for

Step 3.fori= 1 ton

φi=0；

forj=1 tomdo

ωij=σij/λi；/*計(jì)算中間矩陣ΩQ*/

φi=max(φi，ωij)；/*計(jì)算基本向量ΦQ*/

end for

end for

ori= 1 ton

if (φi>0) then

if(φi==1)then

end for

例3.由表1所示，可知D1={u1，u4，u6}，D2={u2，u3，u5}，根據(jù)定義16有：

基于定義18，有：

因此，根據(jù)推論2可計(jì)算D1和D2的上、下近似集為：

根據(jù)定理2，可知:

5 屬性集變化時(shí)不完備混合信息系統(tǒng)中基于矩陣的近似集增量更新方法

5.1 屬性集增加的情形

(24)

(25)

其中，“⊕”表示異或運(yùn)算.

(26)

根據(jù)上述已給出的相關(guān)理論分析，我們?cè)O(shè)計(jì)了增加屬性集時(shí)基于矩陣的近似集增量更新算法，即算法2.

算法2.不完備混合決策系統(tǒng)中屬性動(dòng)態(tài)增加時(shí)基于矩陣的近似集增量更新算法.

forj= 1 ton

if (mij==1) then

mij=0；

λi=λi-1；

fork=1 tom

σik=σik-dik；

end for

else

mij=1；

end for

end for

Step 2.fori= 1 ton

φi=0；

forj= 1 tomdo

end for

end for

fori= 1 ton

if(φi>0) then

if(φi==1) then

end for

根據(jù)推論2，計(jì)算D1和D2的近似集為:

表3 屬性增加時(shí)不完備混合決策系統(tǒng)
Table 3 Incomplete hybrid decision system
with adding attribute

Ua1a2a3a4a5a6du1210.52.001.9Nu2110.71.82?Yu3?00.51.511.6Yu41?0.92.11?Nu510?1.921.5Yu62?0.2?01.6N

5.2 屬性集刪除的情形

(27)

證明：證明過(guò)程與定理3的證明過(guò)程類(lèi)似，故略.

(28)

(29)

根據(jù)上述已給出的相關(guān)理論分析，我們?cè)O(shè)計(jì)了刪除屬性集時(shí)基于矩陣的近似集增量更新算法，即算法3.

算法3.不完備混合決策系統(tǒng)中屬性動(dòng)態(tài)刪除時(shí)基于矩陣的近似集增量更新算法.

forj= 1 ton

if (mij==0) then

mij=1；

λi=λi+1；

fork=1 tom

σik=σik+dik；

end for

else

mij=0；

end for

end for

Step 2.fori= 1 ton

φi=0；

forj= 1 tomdo

end for

end for

fori= 1 ton

if (φi>0) then

if (φi==1) then

end for

基于推論7，由關(guān)系矩陣誘導(dǎo)的對(duì)角矩陣被更新為：

再結(jié)合推論8和推論9，中間矩陣被更新為：

由推論2，可計(jì)算D1和D2的上、下近似集：

表4 屬性刪除時(shí)不完備混合決策系統(tǒng)
Table 4 Incomplete hybrid decision system
with deleting attributes

Ua2a3a4du110.52.0Nu210.71.8Yu300.51.5Yu4?0.92.1Nu50?1.9Yu6?0.2?N

6 結(jié) 論

本文以具有缺失名義型數(shù)據(jù)和數(shù)值型數(shù)據(jù)的不完備混合信息系統(tǒng)為研究對(duì)象，通過(guò)整合鄰域關(guān)系和特征關(guān)系的特點(diǎn)，提出了鄰域特征關(guān)系.與此同時(shí)，通過(guò)引入數(shù)據(jù)驅(qū)動(dòng)數(shù)據(jù)挖掘的思想，進(jìn)一步推廣了鄰域特征關(guān)系，定義了量化鄰域特征關(guān)系.基于這兩種關(guān)系介紹了兩種拓展鄰域粗糙集模型，并研究了其相關(guān)性質(zhì)，豐富了鄰域粗糙集理論框架.此外，通過(guò)引入決策矩陣、關(guān)系矩陣等相關(guān)矩陣，介紹了基于矩陣的粗糙鄰域近似知識(shí)的計(jì)算方法.

隨著信息技術(shù)的快速發(fā)展，實(shí)際環(huán)境中所收集的數(shù)據(jù)總是呈現(xiàn)出動(dòng)態(tài)性變化，如何利用已有的結(jié)果高效、及時(shí)地獲取知識(shí)已然成為亟待解決的問(wèn)題.因此，針對(duì)不完備混合信息系統(tǒng)中屬性集的增加和刪除，提出了基于矩陣的增量知識(shí)維護(hù)機(jī)制，并通過(guò)具體的實(shí)例展現(xiàn)了所提出方法的有效性.在未來(lái)的工作中，利用UCI數(shù)據(jù)集測(cè)試增量更新方法的性能，以及通過(guò)運(yùn)用云計(jì)算等并行技術(shù)來(lái)提高不完備混合信息系統(tǒng)中動(dòng)態(tài)知識(shí)獲取方法的效率將是我們研究的重點(diǎn).