信息系統中的相對知識距離及其認知特征

王 濤，王寶麗*，，，韓素青，廉侃超，林國平

(1．太原師范學院 數學系，山西 晉中030619；2．運城學院 數學與信息技術學院，山西 運城044000；3．閩南師范大學 數學與統計學院，福建 漳州363000)

0 引言

波蘭數學家Zdzislaw Pawlak提出的Rough Sets理論對論域進行劃分，構成粒度求解的最基本的結構，這種劃分結構亦稱為知識[1-2]．知識的不確定性度量在知識獲取中發揮著重要的作用[3]，研究者從不同的角度出發，提出了許多不同種類的不確定性度量方式，如知識粒度、知識粗糙熵、知識條件熵、知識距離等．知識距離作為其中一種基礎性度量，能夠從數量上反應不同結構之間的量化差異．王寶麗等[4]首先提出知識距離的概念，并從內涵、構造以及多粒度應用等方面進行了深入地研究，取得了一些有意義的結果．Qian等[5-7]進一步研究了精確知識和模糊知識的知識結構、知識粒度的不變性以及知識距離對粒度的刻畫，解釋了知識距離在人類變粒度求解中的重要作用．Liang等[8]基于知識距離對粗糙集中包含度，近似精度，粗糙度等進行了距離視角的解釋．

近年來，知識距離的研究成果更加豐富．為了刻畫知識結構，Qian等[9]基于知識距離對劃分粒結構進行聚類，分析了粒結構聚類中體現的聚集性和收斂性，并對人類粒選擇的行為進行模擬仿真．Yang等[10]對集合距離與知識距離構建代數格，研究了粒結構的三個層次．為了豐富知識距離的表達形式，Chen等[11]運用Jaccard距離替代集合相似度，給出了新的知識距離的度量公式，并將信息系統中的劃分知識距離推廣到鄰域信息系統中，豐富了知識距離的含義，為知識距離在機器學習領域的應用提供了新思路[12]．在此基礎上，Yang等從物流分配優化角度證明了只要給出粒之間的距離，便可通過組合的方式構造知識距離[13-15]．Dai等討論了集值信息系統下的熵與粒度度量，從高斯核的視角研究了模糊信息系統下的不確定性度量，提出了模糊結構差異的信息度量，并研究了直覺模糊粒結構距離[16-18]．Li等[19]則進一步提出了一組區間值直覺模糊集描述下的模糊粒結構距離，證明了知識距離是直覺模糊粒結構距離的特殊形式．

值得關注的一點是，上述所有研究都只從不同的角度給出了兩個知識的絕對差異性度量，均未描述和分析任意條件下兩個知識的差異，即知識的相對差異性度量．事實上，人類認識事物總是從已有的知識出發，通過分析知識空間中知識差異性來獲取新知識，而知識的差異性應該與觀察者所擁有的先驗知識或觀察視角相關．擁有的先驗知識不同或所處的角度不同，知識的差異性也應當有所不同．楊潔等[20]提出一種帶近似描述能力的鄰域信息粒距離，用來反映不同鄰域知識空間對目標概念的刻畫能力的差異性，但這一研究仍無法描述不同認知視角對知識差異的影響．為了解決以上問題，本文在具備一定先驗知識的條件下研究兩個知識空間之間的距離及其在知識獲取方面的認知特征，從而反映知識之間的相對認知差異．

本文第1節簡要介紹相關基本概念；第2節提出了相對知識距離的概念，分析了相對知識距離的保序性、有界性及條件依賴性，并證明絕對知識距離是相對知識距離的特殊情形；為了刻畫人類多粒度認知的特性，本文在第3節以實驗方式呈現相對知識距離與絕對知識距離所具有的不同的結構信息，同時基于相對知識距離提出一種新的特征選擇算法，用以分析在不同先驗知識條件下的特征選擇所呈現的人類認知變化特性；第4節總結全文．

1 信息系統與知識距離

1．1 信息系統及知識表示

定義1：四元組S=(U，A，V，f)是一個信息系統，其中U={x1，x2，…，xn}為對象的非空有限集，稱為論域；A為屬性的非空有限集；V=∪a∈AVa是屬性值的集合，Va表示屬性a的值域；f：U×A→V表示一個信息函數．

對于每個屬性子集P?A，定義論域U上的一個二元不可分辨關系：

IND(P)={(x，y)∈U×U|?a∈P，fa(x)=fa(y)}

(1)

顯然，IND(P)是一個等價關系，因此IND(P)可誘導得到論域U的一個劃分，記為U/IND(P)，簡記為U/P．從粒計算的觀點來看，U/P中的每個等價類都可以視為一個知識顆粒，表示為U/P={[xi]P|xi∈U}．在粗糙集理論中，將知識粒的集合U/P稱為論域U的一個知識，為了方便分析與說明，下文中將其稱為知識P．

在論域U上的所有知識構成的知識庫中，恒等關系ω對應最細的知識，全域關系δ對應最粗的知識．

定義2[4]：設U為非空有限論域，P和Q為U上的兩個知識，若對?xi∈U，滿足[xi]P?[xi]Q，則稱知識P比知識Q更精細，記為P?Q．

1．2 知識距離

定義3[5-6]：設U為非空有限論域，P和Q為U上的兩個知識，P與Q之間的知識距離定義為

(2)

其中[xi]p⊕[xi]q=([xi]p∪[xi]q)-([xi]p∩[xi]q)．

例1：給定論域U={x1，x2，x3，x4，x5，x6}上的兩個知識，P={{x1，x3}，{x2，x6}，{x4，x5}}，Q={{x1，x3，x5，x6}，{x2，x4}}．知識P與Q之間的知識距離為d(P，Q)=4/9．

以上的知識距離度量反映了兩個知識之間的絕對差異，但與觀察者所擁有的先驗知識或所處的角度無關，不能反映在先驗知識或條件認知下的知識之間相對認知差異．因此本文提出了基于不同認知視角或認知條件下的相對知識距離，進而反映人類多粒度相對認知的特點．為與下文給出的距離定義相區別，將第1．2節中所述的知識距離稱為絕對知識距離．

2 相對知識距離

本節提出相對知識距離的概念并分析其性質．

定義4：U為非空有限論域，R為U上的先驗知識或條件認知，知識P和Q在R下的相對知識距離定義為

(3)

該定義將對先驗知識或條件認知R的相對描述融入到已有的知識距離公式中，以反映在不同認知視角下任意兩個知識P和Q的相對差異性．定義4也稱為P和Q關于R的相對知識距離．

下面分析相對知識距離D(P，Q|R)所具有的性質．

性質1：設U是一個非空有限論域，P1，P2，P3為U上的知識，R為U上的先驗知識或條件認知，則相對知識距離D滿足：

(1)非負性D(P1，P2|R)≥0；

(2)對稱性D(P1，P2|R)=D(P2，P1|R)；

(3)三角不等式D(P1，P2|R)+D(P2，P3|R)≥D(P1，P3|R)．

證明：性質(1)(2)顯然成立，下證(3)成立．

欲證知識P1，P2，P3關于R的相對知識距離滿足三角不等式，根據定義，只需證|([xi]P1∩[xi]R)⊕([xi]P3∩[xi]R)|≤|([xi]P1∩[xi]R)⊕([xi]P2∩[xi]R)|+|([xi]P2∩[xi]R)⊕([xi]P3∩[xi]R)|，即證|([xi]P1⊕[xi]P3)∩[xi]R|≤|([xi]P1⊕[xi]P2)∩[xi]R|+|([xi]P2⊕[xi]P3)∩[xi]R|．

由集合的性質知([xi]P1⊕[xi]P3)?[([xi]P1⊕[xi]P2)∪([xi]P2⊕[xi]P3)]，因此(([xi]P1⊕[xi]P3)∩[xi]R?[(([xi]P1⊕[xi]P2)∩[xi]R)∪(([xi]P2⊕[xi]P3)∩[xi]R)]，進而|([xi]P1⊕[xi]P3)∩[xi]R|≤|([xi]P1⊕[xi]P2)∩[xi]R|+|([xi]P1⊕[xi]P3)∩[xi]R|．故D(P1，P2|R)+D(P2，P3|R)≥D(P1，P3|R)．

性質1表明，論域U的條件知識關于相對知識距離D(P，Q|R)構成一個度量空間．

例2：給定論域U={x1，x2，x3，x4，x5，x6}上兩個需區分的知識P={{x1，x3}，{x2，x6}，{x4，x5}}，Q={{x1，x3，x5，x6}，{x2，x4}}，在先驗知識R1={{x3，x6}，{x1，x2，x4，x5}}，R2={{x1，x2，x5}，{x3，x4，x6}}下，知識P和Q的相對知識距離為：D(P，Q|R1)=1/36×(1+1+1+2+2+1)=2/9，D(P，Q|R2)=1/36×(1+0+1+0+1+1)=1/9．

從例1和例2可知，知識P和Q在不同的先驗知識或條件認知下的相對知識距離是不同的，相比于例1中計算出的知識P和Q之間的絕對知識距離，例2中計算出的相對知識距離更?。?/p>

性質2：設U是一個非空有限論域，P1，P2，P3為U上的知識，R為U上的先驗知識或條件認知，若序關系P1?P2?P3成立，則

D(P1，P2|R)+D(P2，P3|R)=D(P1，P3|R)

(4)

證明：欲證具有序關系的三個知識P1，P2，P3在先驗知識或條件認知R下的距離三角等式成立，需證|([xi]P1∩[xi]R)⊕([xi]P3∩[xi]R)|=|([xi]P1∩[xi]R)⊕([xi]P2∩[xi]R)|+|([xi]P2∩[xi]R)⊕([xi]P3∩[xi]R)|，根據條件所給出的序關系P1?P2?P3，可得[xi]P1?[xi]P2?[xi]P3，因此只需證|([xi]P3-[xi]P1)∩[xi]R|-|([xi]P2-[xi]P1)∩[xi]R|=|([xi]P3-[xi]P2)∩[xi]R|．

故D(P1，P2|R)+D(P2，P3|R)=D(P1，P3|R)．

性質2體現了在相同先驗知識或條件認知下，相對知識距離保持了序關系下等式成立的性質．

性質3：設U是一個非空有限論域，P和Q為U上的知識，R1和R2為U上的先驗知識或條件認知，若知識R1和R2滿足序關系R1?R2，則

D(P，Q|R1)≤D(P，Q|R2)

(5)

證明：欲證當先驗知識或條件認知R1和R2存在序關系時相對知識距離具有保序性，只需證 |([xi]P∩[xi]R1)⊕([xi]Q∩[xi]R1)|≤|([xi]P∩[xi]R2)⊕([xi]Q∩[xi]R2)|，根據集合的運算性質，需證|([xi]P⊕[xi]Q)∩[xi]R1|≤|([xi]P⊕[xi]Q)∩[xi]R2|，即(([xi]P⊕[xi]Q)∩[xi]R1)?(([xi]P⊕[xi]Q)∩[xi]R2)．

設任意對象xi∈([xi]P⊕[xi]Q)∩[xi]R1，則有xi∈[xi]R1且xi∈([xi]P⊕[xi]Q)，又[xi]R1?[xi]R2，所以xi∈[xi]R2，進而xi∈([xi]P⊕[xi]Q)∩[xi]R2，(([xi]P⊕[xi]Q)∩[xi]R1)?(([xi]P⊕[xi]Q)∩[xi]R2)．由此知D(P，Q|R1)≤D(P，Q|R2)成立．

從性質3可以看出，隨著先驗知識或條件認知的不斷細化，知識之間的相對知識距離在單調下降．這一規律反映了在漸進認知過程中，隨著已有認知水平的不斷提高，可以逐漸降低兩個知識之間的相對認知難度，體現了人類多粒度漸進認知的特性．

推論1：設U是一個非空有限論域，當R是U上最粗的知識δ時，有D(P，Q|δ)=d(P，Q)．

證明：根據公式(3)，有

推論1說明了絕對知識距離是兩個知識之間在沒有任何認知前提下的差異性度量，因此絕對知識距離是相對知識距離的一個特例．

推論2：設U是一個非空有限論域，當R是U上最細的知識ω時，知識P與Q之間的相對知識距離D(P，Q|R)達到最小值0．

證明：若先驗知識或條件認知R是U上最細的知識，即R=ω，則P與Q之間的相對知識距離為

根據性質3，對于U上的任意知識R，若滿足序關系ω?R?δ，則不等式D(P，Q|ω)≤D(P，Q|R)≤D(P，Q|δ)成立，即相對知識距離滿足：0≤D(P，Q)≤d(P，Q)．

例3：給定論域U={x1，x2，x3，x4，x5，x6}上的知識P={{x1，x3}，{x2，x6}，{x4，x5}}，Q={{x3，x4，x5}，{x1}，{x2}，{x6}}，U上的先驗知識為R={{x3，x6}，{x1，x2，x4，x5}}，知識P和Q關于知識R的相對知識距離為D(P，Q|R)=1/36×(0+0+0+0+0+0)=0．

例3表明，R=ω僅僅是D(P，Q|R)=0成立的充分條件，但非必要條件．

性質4：設U是一個非空有限論域，U上的知識P和Q之間存在如下條件依賴關系：

D(P，Q|P)+D(P，Q|Q)=d(P，Q)

(6)

證明：

性質4說明了P與Q之間的絕對知識距離可以分解為不同方向的單向相對知識距離之和，即從P到Q的認知難度與從Q到P的認知難度之和，進而從理論上解釋了相對知識距離與絕對知識距離的辯證統一性．

3 數據實驗

本小節將從實驗上分析相對知識距離與絕對知識距離在實際問題的結構差異；此外，通過設計基于相對知識距離的特征選擇算法，研究相對知識距離在知識獲取與發現中的認知特征．

3．1 絕對知識距離與相對知識距離的結構差異性

對于給定的對象集，不同的距離計算方法，可以得到不同的分層結構．譜系聚類法是一種基于對象集上的距離矩陣，通過定義類與類之間的距離，依次將最近的類進行合并形成分層遞階結構的聚類方法[21]．這里運用相同的譜系聚類算法得到不同的聚類結構來顯示本文所提距離與經典絕對知識距離的差異，進一步證實相對知識距離可以為知識獲取提供與絕對知識距離不一樣的視角．實驗流程如下：

已知在信息系統S=(U，A，V，f)中，A={a1，a2，…，am}為S中的條件屬性集，對于條件屬性集A中的每個屬性進行如下的計算：

(1)對?ak∈A，k={1，2，…，m}，通過等價關系可得ak誘導的知識Pk，并將其作為先驗知識或條件認知Rk；

(2)計算由其余屬性誘導的知識在Rk作為條件認知的相對知識距離Dij(Pi，Pj|Rk)和絕對知識距離dij(Pi，Pj)，并得到相對知識距離矩陣M=(Dij)和絕對知識距離矩陣N=(dij)；

(3)基于兩個距離矩陣M和N，分別用譜系聚類法對數據集的屬性子集進行聚類，得到不同的聚類結構；

(4)分別以知識粒度[6]之差ΔGK(X)和知識距離d(P，Q)作為度量標準，計算聚類結果的差異性．其中，

(7)

下面以UCI數據庫中的Zoo數據集和Las Vegas Trip Advisor Reviews(簡稱Las Vegas)數據集為例，并分別以數據集中的屬性a1和屬性a5誘導的知識作為條件知識R，構造相對知識距離和絕對知識距離矩陣，進行屬性集聚類，聚類結果見圖1和圖2．(圖中Rel-a1表示以a1作為條件屬性的相對知識距離的聚類，Abs-a1表示去掉a1以后基于絕對知識距離的聚類)

(a)Abs-a1

(b)Rel-a1

(c)Abs-a5

(d)Rel-a5

(a)Abs-a1

(b)Rel-a1

(c)Abs-a5

(d)Rel-a5

為了更直觀地描述聚類結果的差異，本文計算了在不同的分類個數下，基于絕對知識距離的譜系聚類和基于相對知識距離的譜系聚類的數值差異，結果見圖3和圖4．

圖3 Zoo數據集中相對知識距離和絕對知識距離關于不同類別數的聚類差異

圖4 Las Vegas數據集中相對知識距離和絕對知識距離關于不同類別數的聚類差異

以上實驗對比結果表明，基于相對知識距離的譜系聚類和基于絕對知識距離的譜系聚類在不同的分類個數下具有明顯差異，具體表現為：

(1)當相同屬性作為條件屬性時，基于相對知識距離和基于絕對知識距離的譜系聚類結構是有差異的；

(2)當不同屬性作為條件屬性時，基于相對知識距離和基于絕對知識距離的譜系聚類結構的差異是不同的；

(3)在不同的類別數下且條件屬性不同時，基于相對知識距離和基于絕對知識距離的譜系聚類結構的差異是不同的．

因此，相對知識距離與絕對知識距離在實際應用中存在著明顯的差異，相對知識距離具有更為豐富的信息特性，可以對人類不同認知視角認知事物結構進行有效建模．

3．2 基于相對知識距離的特征選擇算法

特征選擇是一類重要的數據預處理方法，目的是從數據集的特征集合中選出對學習任務有用的相關特征子集[24]．在特征選擇過程中，是否存在先驗知識所選出的特征子集可能有所不同．

例如，考慮立方體對象，若已有特征為底面長l、底面寬w、底面積S、高h、密度ρ和顏色c等6個特征，在執行描述立方體質量的特征選擇任務時，若從先驗特征S出發，則選出的特征子集是S，h，ρ，而沒有先驗特征時，選出的特征子集可以是l，w，h，ρ．因此，有必要根據不同的機制，分析先驗特征對特征選擇結果的影響．

本節設計了過濾式的特征選擇方法，并以相對知識距離作為評價函數．算法求解思想如下：

在子集搜索過程中，依照前向搜索策略，將特征集合{a1，a2，…，am}中的每個特征作為候選單特征子集，根據定義4中的相對知識距離，依次加入到候選子集中，直到滿足停止條件；

在子集評價過程中，將候選子集中與原來系統中相對于知識R的距離為0的特征剔除，最終得到系統的特征子集．

算法1：基于相對知識距離的特征選擇算法

輸入：信息系統S=(U，A，V，f)，初始狀態的知識R

輸出：特征子集I

Step1 初始化候選子集F=?，I=?，

對?a∈A，IfD(A{a}，A|R)≠0

ThenF=F∪{a}；

Step2 令I′=F；

Step3 IfD(I′，A|R)=0轉到Step7，否則執行Step4；

Step4 ?a∈AI′，計算D(I′∪{a}，A|R)，選擇使D(I′∪{a}，A|R)最大的屬性a′；

Step5I′=I′∪{a′}；

Step6 WhileI′≠A，返回Step3；

Step7 對?a∈I′，ifD(I′{a}，A|R)=0

ThenI=I′{a}；

Step8 輸出信息系統S的特征子集I，算法結束．

實驗分析

本節將基于相對知識距離的特征選擇算法與基于絕對知識距離的特征選擇算法進行比較，以進一步說明不同的距離度量對信息系統的認知差異．實驗選用UCI數據庫中的6個數據集，以相對知識距離作為評價準則進行特征選擇，并將在3．1節的實驗中聚類差異最大的特征所誘導的劃分知識作為先驗知識或條件知識，實驗結果見表1．

表1 基于兩類距離算法在6類數據集下的特征選擇結果

實驗結果表明，對信息系統采用不同的知識距離得到的特征選擇結果具有一定的差異．這種差異來源于不同的度量機制，由于將系統中的部分特征作為先驗知識或條件知識，導致對系統的認知路徑發生改變，因此獲得了不同的特征選擇結果．

此外，分析兩種特征選擇算法中特征個數的變化，我們可以得到以下結論：

(1)當先驗特征有利于描述信息系統整體性能時，對系統的認知能力有所增強，較少的特征就能達到信息系統全部特征所具備的分類能力，因此本文算法輸出的特征個數少于對比算法中的特征個數；

(2)當先驗特征所蘊含的信息量較少、對信息系統的認知能力有所減弱時，需要較多的特征才能刻畫系統的分類能力，因此本文算法輸出的特征個數多于對比算法中的特征個數；

(3)當先驗特征對描述信息系統整體性能無影響時，保持了對信息系統的認知能力，因此本文算法輸出的特征個數與對比算法中的特征個數相等．

4 結論

本文從相對認知視角出發研究了知識空間的相對性差異．具體地，提出相對知識距離的概念，分析了相對知識距離具有的認知特性，通過屬性聚類實驗說明了相對知識距離較于絕對知識距離所具有的不同的結構特性．此外，基于相對知識距離的特征選擇算法也對人類條件漸進認知增強、保持與減弱特性進行了模擬與仿真．本文主要結論有：

(1)相對知識距離反映了不同視角下任意兩個知識之間的相對差異性，體現了人類多粒度相對認知的特性；

(2)相對知識距離比絕對知識距離更具有一般性，在已知先驗知識或條件認知的前提下，相對知識距離可以降低兩個知識之間的認知難度，符合一般的認知規律；

(3)相對知識距離與絕對知識距離具有不同的拓撲結構，且由于度量機制的不同，對系統的認知路徑也會有所改變，可以為人類多視角認知提供有效參考．

本研究進一步豐富了粒計算的不確定性度量理論，為現實信息系統的認識刻畫提供了新的視角．相對知識距離在鄰域、模糊信息系統以及各類決策系統中的應用將是我們下一步的研究方向．