劃分序乘積空間：基于劃分的粒計(jì)算模型

徐 怡 姚一豫

1(計(jì)算智能與信號處理教育部重點(diǎn)實(shí)驗(yàn)室(安徽大學(xué)) 合肥 230039)2(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 合肥 230601)3 (里賈納大學(xué)計(jì)算機(jī)科學(xué)系 加拿大里賈納 S4S0A2)

粒計(jì)算(granular computing)是用系統(tǒng)的、結(jié)構(gòu)化的理解和方法來解決復(fù)雜問題的新理論、新技術(shù)和新方法[1-5]，被用于很多領(lǐng)域[6-10].粒計(jì)算的基本思想是在問題求解過程中通過構(gòu)造信息粒，形成粒結(jié)構(gòu)，基于粒結(jié)構(gòu)從不同角度、不同層次上對現(xiàn)實(shí)問題進(jìn)行描述、推理與求解[2,11-12].對復(fù)雜問題的全面理解通常是多視角的，從每一個視角著眼的理解又是多層次的，它的結(jié)果表現(xiàn)為一個多視角、多層次的粒結(jié)構(gòu).多層次強(qiáng)調(diào)對問題多個粒度層次的理解和描述.根據(jù)具體問題，不同的層次體現(xiàn)為不同的尺度、不同的復(fù)雜度、不同的抽象、不同的控制、不同的細(xì)節(jié).多視角強(qiáng)調(diào)從多個不同的角度對問題進(jìn)行描述和處理.從人類問題求解的角度看，對于同一個問題，不同的人會有不同的觀點(diǎn).人腦對于同一個問題有著不同的理解和處理方式.因此單視角對問題理解具有一定的局限性，需要多視角從全局的角度理解問題.多視角有2個優(yōu)點(diǎn)：1)通過對問題的多樣性描述，我們可以尋找解決問題的可能存在的最優(yōu)化方法；2)多視角的組合可以給出任何一個單視角得不到的結(jié)果.粒計(jì)算的核心任務(wù)之一是通過信息?；?，構(gòu)建多層次、多視角的粒結(jié)構(gòu)[13].

粒、層和多層次是粒結(jié)構(gòu)中的3個基本要素.粒是整體的一部分，可視為我們當(dāng)前感興趣的焦點(diǎn)，或者用于描述和表示的元素、概念、觀念等，例如論域的子集、問題的子問題、系統(tǒng)的子系統(tǒng)等.一個層由一簇粒構(gòu)成，層是?；慕Y(jié)果.?；钱a(chǎn)生具有不同粒度層的過程，是建立粒結(jié)構(gòu)的基礎(chǔ).粒化的程度通過粒度來刻畫，表示層對問題觀察或描述的抽象程度.多個層按照線性序關(guān)系組織起來構(gòu)成了多層次.

對于不同的實(shí)際問題，信息?；姆椒ǘ喾N多樣.劃分是一種常用的信息粒化方法.基于劃分，姚一豫[13]提出了基于劃分的粒計(jì)算模型.Pawlak[14]提出的粗糙集模型，張鈴和張鈸[15-16]提出的商空間模型都是基于劃分的粒計(jì)算模型.但是現(xiàn)有對?；椒ǖ难芯浚饕欠謩e基于多層次的?；椒ê突诙嘁暯堑牧；椒ǎ瑳]有將多層次?；椒ê投嘁暯橇；椒ńY(jié)合起來.基于多層次的粒化方法，粒化結(jié)果是一個多層次，多個層之間具有線性序關(guān)系.基于多視角的粒化方法，?；Y(jié)果是多個視角，但是每個視角僅有一個層.所以在本文中，為了更全面地理解和描述問題，從而可以更有效和合理地解決問題，給定一個論域，我們使用劃分作為?；椒?，將多層次的?；椒ê投嘁暯堑牧；椒ㄏ嘟Y(jié)合，定義劃分序乘積空間.首先，使用論域上的一個劃分定義一個層.其次，使用一個嵌套的劃分序定義一個多層次，表示為一個視角，層和層之間具有線性序關(guān)系.最后，給定多個視角，則定義了多個線性序關(guān)系，基于多個線性序關(guān)系的乘積，定義劃分序乘積空間.劃分序乘積空間給出了一種基于劃分的粒計(jì)算模型.

在多層次?；椒ㄖ校ǔ；谇短椎膶傩孕蛄谢蛘咔短椎膶傩灾敌蛄衼順?gòu)建嵌套的劃分序，即多層次.Marek和Rasiowa[17]基于遞減的等價關(guān)系序列研究了集合的漸進(jìn)近似.Pomykala[18]使用容差關(guān)系序列構(gòu)建多層次.姚一豫[19]提出基于一個嵌套的等價關(guān)系序列誘導(dǎo)出多層次粒結(jié)構(gòu)和層次粗糙集近似.粗糙集的屬性約簡，也是從一個嵌套的屬性序列中找出一個最小的屬性子集，使其分類能力和屬性全集的分類能力相同，本質(zhì)上也是一種多層次?；椒╗14,20].Hong等人[21]基于粗糙集，提出了從具有層次屬性值的數(shù)據(jù)中學(xué)習(xí)多層次確定規(guī)則和可能規(guī)則的算法.Feng等人[22]研究了具有層次屬性值的層次信息系統(tǒng)，提出了從不同的屬性概念層自上而下的策略挖掘?qū)哟螞Q策規(guī)則.Wu等人[23-24]從粒計(jì)算的角度研究了多尺度決策表，每個對象在每個屬性下的屬性值表示為具有不同粒度的多個尺度值.Ye等人[25]基于屬性概念層次樹，提出了多層次粗糙集模型.基于多層次粒結(jié)構(gòu)，姚一豫[26]提出的序貫三支決策是一種有效且快速的決策策略.

基于多視角的粒化方法主要有以下研究工作.Qian等人[27-28]用一簇等價關(guān)系取代一個等價關(guān)系對論域進(jìn)行分類和近似未知概念，提出了多粒度粗糙集模型.由于這一簇等價關(guān)系之間不存在線性序關(guān)系，所以這些等價關(guān)系不能構(gòu)成多層次，因此多粒度粗糙集模型本質(zhì)上是基于多視角的?；椒?，每個粒度對應(yīng)一個視角.姚一豫等人[6]對已有的多粒度研究進(jìn)行分類比較，提出了多粒度空間中粗糙集近似的統(tǒng)一框架，討論了4種不同類型的粗糙集近似.Xu等人[29]基于支持特征函數(shù)和信息層，研究了廣義多粒度粗糙集的上下近似集，給出了如何在廣義多粒度粗糙集中選擇最優(yōu)粒度層的方法.利用多源近似空間表示多粒度空間，Khan和Banerjee[30]提出了強(qiáng)和弱上下近似集的概念.Sang等人[31]提出了基于多源決策系統(tǒng)的決策粗糙集模型，每個信息源對應(yīng)問題的一個視角.Chen等人[32]基于多種形式的數(shù)據(jù)操作，提出了智能數(shù)據(jù)分析的多視角框架.

1 劃分和劃分序

劃分是一種常用的信息粒化方法，劃分通?？梢杂傻葍r關(guān)系誘導(dǎo)得出.本節(jié)介紹和劃分相關(guān)的基本概念[1-5].

定義2. 細(xì)化.給定一個論域U，π1和π2是定義在U上的2個劃分，π1={A1,A2,…,Ak}，π2={B1,B2,…,Bt},如果?Bi∈π2,?Aj∈π1,滿足Bi?Aj，則稱π2比π1細(xì)，或反之π1比π2粗，記為π2?π1.如果π2?π1并且π2≠π1,則稱π2比π1真細(xì)，記為π2π1.

定義3. 劃分序.給定一個論域U，P是定義在U上的一簇劃分，P={π1,π2,…,πn}，如果其滿足πn?πn-1?…?π1，則稱P為一個嵌套的劃分序.

劃分可以由等價關(guān)系誘導(dǎo)得出.等價關(guān)系定義如下：

定義4. 等價關(guān)系.給定一個論域U，E?U×U是U上的一個等價關(guān)系，如果E是自反、對稱且傳遞的.其中U×U表示U和U的笛卡兒積.[x]E={y∈U|(x,y)∈E}表示對象x∈U在等價關(guān)系E下的等價類，簡記為[x].

定理1. 給定一個論域U，E是U上的一個等價關(guān)系，則E可以誘導(dǎo)出U上的一個劃分π，記為π=UE={[x]E|x∈U}.

定理2. 給定一個論域U，E1和E2是定義在U上的2個等價關(guān)系，由E1和E2誘導(dǎo)出的2個劃分記為π1和π2，其中，π1=UE1={[x]E1|x∈U}，π2=UE2={[x]E2|x∈U}.如果E2?E1，則π2?π1，且?x∈U，[x]E2?[x]E1.

定理2說明等價關(guān)系之間的包含關(guān)系對應(yīng)于劃分之間的細(xì)化關(guān)系，基于一個細(xì)的等價關(guān)系產(chǎn)生的等價類比基于一個粗的等價關(guān)系產(chǎn)生的等價類小.

定義5. 等價關(guān)系序.給定一個論域U，R是定義在U上的一簇等價關(guān)系，R={E1,E2,…,En}，如果其滿足En?En-1?…?E1，則稱R為一個嵌套的等價關(guān)系序.

定理3. 給定一個論域U，R是定義在U上的一個嵌套的等價關(guān)系序，R={E1,E2,…,En}，滿足En?En-1?…?E1，則由R可以誘導(dǎo)出U上的一個嵌套的劃分序P={π1,π2,…,πn}，滿足πn?πn-1?…?π1.

從定理3可以看出，一個嵌套的等價關(guān)系序可以誘導(dǎo)出一個嵌套的劃分序.

注意：由于劃分和等價關(guān)系是一一對應(yīng)的，所以我們在本文中不加區(qū)分的使用這2個概念.

2 基于劃分序乘積空間的粒計(jì)算模型

信息?；墙⒘＝Y(jié)構(gòu)的基礎(chǔ).但是現(xiàn)有對?；椒ǖ难芯浚饕欠謩e基于多層次的?；椒ê突诙嘁暯堑牧；椒?，沒有將多層次粒化方法和多視角?；椒ńY(jié)合起來.所以在本文中，為了更全面地理解和描述問題，從而可以更有效和合理地解決問題，給定一個論域，我們使用劃分作為粒化方法，將多層次的?；椒ê投嘁暯堑牧；椒ㄏ嘟Y(jié)合，定義劃分序乘積空間.劃分序乘積空間給出一種基于劃分的粒計(jì)算模型.

2.1 粒結(jié)構(gòu)的3要素

粒、層和多層次是粒結(jié)構(gòu)的3個基本要素.粒是整體的一部分，可視為我們當(dāng)前感興趣的焦點(diǎn)，或者用于描述和表示的元素、概念、觀念等.一個層由一簇粒構(gòu)成，每個層通過具有相似粒度的一簇粒對問題進(jìn)行理解和表示.多個層按照線性序關(guān)系組織起來構(gòu)成了多層次，即視角.在較粗的粒度層，我們通過忽略一些細(xì)節(jié)，對問題的表示較抽象和簡潔，因此對問題的求解速度較快，但是精度較低.在較細(xì)的粒度層，我們對問題的表示較具體和詳細(xì)，因此對問題的求解速度較慢，但是精度較高.

在粒結(jié)構(gòu)的3要素中，層起到承上啟下的作用.層是?；慕Y(jié)果.對于不同的實(shí)際問題，?；姆椒ǘ喾N多樣.常用的粒化方法有基于劃分或等價關(guān)系的?；椒?、基于覆蓋的?；椒?、基于二元關(guān)系的粒化方法、基于模糊劃分的?；椒ǖ?

但是現(xiàn)有的這些?；椒?，都是從多層次的角度和多視角的角度分別進(jìn)行?；磳Χ鄬哟蔚牧；椒ê投嘁暯堑牧；椒ǚ謩e進(jìn)行研究，沒有將二者結(jié)合起來.基于多層次的粒化方法，通常使用一個多層次來描述和解決問題，每個層對應(yīng)論域的一個?；Y(jié)果，多個層之間具有線性序關(guān)系.基于多視角的?；椒ǎǔＪ褂枚鄠€視角來描述和解決問題，但是每個視角僅有一個層.因此導(dǎo)致現(xiàn)有的粒結(jié)構(gòu)不能從多層次和多角度2個方面更全面系統(tǒng)地理解和描述問題，從而不能有效合理地解決問題.

2.2 基于劃分的粒結(jié)構(gòu)

在2.1節(jié)中我們給出了粒結(jié)構(gòu)的一般描述，指出粒、層和多層次是粒結(jié)構(gòu)的3個基本要素，?；墙⒘＝Y(jié)構(gòu)的基礎(chǔ).但是沒有考慮?；木唧w實(shí)現(xiàn)方法，因此粒、層和多層次缺乏具體的意義和解釋.

如第1節(jié)所述，給定一個論域，劃分和等價關(guān)系可以作為?；椒▽φ撚蜻M(jìn)行粒化.一個對論域的劃分對應(yīng)一個層，一個嵌套的劃分序?qū)?yīng)一個多層次，層和層之間的線性序關(guān)系可以解釋為嵌套的劃分序之間的細(xì)化關(guān)系.

因此，本節(jié)采用劃分作為?；椒ǎx基于劃分的粒結(jié)構(gòu).給出粒結(jié)構(gòu)中構(gòu)造粒、層和多層次的具體實(shí)現(xiàn)方法，從而賦予粒、層和多層次具體的意義和解釋.

在基于劃分的粒結(jié)構(gòu)中，其3個要素具體描述為：

1) 粒.一個劃分塊(等價類)表示一個粒，記為[x]，x∈U.

2) 層.一個對論域的劃分對應(yīng)一個層，記為π={[x]|x∈U}.

3) 多層次.一個嵌套的劃分序(一個嵌套的等價關(guān)系序),對應(yīng)一個多層次，表示一個視角，記為P={π1,π2,…,πn}.

一般粒結(jié)構(gòu)中的3要素和基于劃分的粒結(jié)構(gòu)中的3要素之間的對應(yīng)關(guān)系如圖1所示：

在基于劃分的粒結(jié)構(gòu)中，多層次對應(yīng)的線性序關(guān)系是基于劃分定義的細(xì)化關(guān)系，或者是基于等價關(guān)系定義的集合包含關(guān)系.

2.3 劃分序乘積空間

為了更全面地理解和描述問題，從而可以更有效和合理地解決問題，給定一個論域，我們使用劃分作為粒化方法，將多層次的?；椒ê投嘁暯堑牧；椒ㄏ嘟Y(jié)合，定義劃分序乘積空間.

首先，使用論域上的一個劃分定義一個層.其次，使用一個嵌套的劃分序定義一個多層次，表示為一個視角，層和層之間具有線性序關(guān)系.最后，給定多個視角，則定義了多個線性序關(guān)系，基于多個線性序關(guān)系的乘積，定義劃分序乘積空間.劃分序乘積空間給出了一種基于劃分的粒計(jì)算模型.

為了簡單起見，我們首先定義包含2個視角的劃分序乘積空間，然后再定義包含多個視角的劃分序乘積空間.

在定義6中，2個嵌套的劃分序P1和P2，定義了2個視角V1與V2，我們將其表示為2個全序集，全序集中的元素是層，全序關(guān)系是層和層之間的粗化細(xì)化關(guān)系.2個視角的劃分序乘積，定義了包含2個視角的劃分序乘積空間.

POPSm由m個視角的乘積構(gòu)成，不同視角提供了對問題不同角度的理解和描述.每個視角又可以從多個粒度層次上對問題進(jìn)行理解和描述.因此劃分序乘積空間提供了對問題多層次多視角的理解和描述.

定理4. 劃分序乘積空間POPSm=(×Pi,?P)是一個格結(jié)構(gòu).

證明. 基于定義7，?P是一個偏序關(guān)系，其滿足自反性、反對稱性和傳遞性.因此，POPSm是一個偏序集.為了進(jìn)一步證明POPSm是一個格結(jié)構(gòu)，我們只需要證明對于POPSm中任意2個元素，它們有上確界和下確界.

證畢.

在劃分序乘積空間中，其問題求解空間為一個格結(jié)構(gòu)，格中的每一個節(jié)點(diǎn)對應(yīng)一個問題求解層，定義如下:

每個問題求解層，一方面通過多視角給出了對問題的多樣性描述，另一方面基于每個視角，我們可以得到一個問題求解結(jié)果.因此，基于每個問題求解層，在實(shí)際求解問題時有3種處理策略：

1) 首先融合多個視角對問題的描述，然后基于融合后的描述結(jié)果進(jìn)行最終的問題求解，我們稱之為多視角問題描述的融合.

2) 首先分別基于單個視角對問題進(jìn)行求解，然后融合多個視角對問題求解的結(jié)果進(jìn)行最終的問題求解，我們稱之為多視角問題求解結(jié)果的融合.

3) 在多視角問題求解過程中，同時對問題描述和求解結(jié)果進(jìn)行融合，我們稱之為多視角問題求解過程的融合.

例如在劃分序乘積空間中，我們可以對每一個視角從頂層到底層按照粒度遞減的順序來尋找一個合適的層進(jìn)行問題求解，然后融合多個視角下各個層的求解結(jié)果進(jìn)行最終的問題求解，即為多視角問題求解結(jié)果的融合.在多粒度粗糙集模型中，Qian等人[27-28]提出了基于求同存異的樂觀融合策略和求同排異的悲觀融合策略，張明等人[33-34]提出了基于可變多粒度的融合策略，都屬于多視角問題求解結(jié)果的融合.

注意：當(dāng)劃分序乘積空間中視角的個數(shù)為1時，劃分序乘積空間退化為現(xiàn)有的多層次的粒結(jié)構(gòu).當(dāng)劃分序乘積空間中每個視角的層數(shù)為1時，劃分序乘積空間退化為現(xiàn)有的多視角的粒結(jié)構(gòu).

劃分序乘積空間采用劃分作為?；椒?當(dāng)我們采用其他?；椒〞r，可以得到各種類型的序乘積空間，如覆蓋序乘積空間、鄰域序乘積空間、模糊序乘積空間等.

2.4 實(shí) 例

本節(jié)中我們通過一個例子來說明劃分序乘積空間在實(shí)際應(yīng)用中的優(yōu)越性.

Table 1 Information of Patients表1 病人信息表

Note: N means normal; AN means abnormal.

對于V1，其2個層描述為

對于V2，其3個層描述為

對于V3，其2個層描述為

由3個視角構(gòu)成的劃分序乘積空間POPSm=(×Pi,?P)構(gòu)成的格結(jié)構(gòu)如圖2所示：

Fig. 2 Partition order product space with three views圖2 由3個視角構(gòu)成的劃分序乘積空間

通過圖2可以看出，劃分序乘積空間同時考慮了多層次的?；椒ê投嘁暯堑牧；椒?，共有12個問題求解層.因此，醫(yī)生在實(shí)際診斷病人時，不僅可以從多個層次上處理問題，還可以從多個角度處理問題，根據(jù)實(shí)際問題求解的需要，可以在不同視角和同一視角的不同層次之間靈活選擇和變換，從而使得對疾病的診斷更加有效和合理.在實(shí)際問題求解中，如何在劃分序乘積空間中找到合適的問題求解層，將是一個值得研究的方向.

3 結(jié) 論

粒計(jì)算研究有效的粒結(jié)構(gòu)用于問題求解和信息處理，多層次和多視角是其2個重要的?；瓌t.但是現(xiàn)有對粒結(jié)構(gòu)中?；椒ǖ难芯浚饕欠謩e基于多層次的?；椒ê突诙嘁暯堑牧；椒?，沒有將兩者結(jié)合起來.所以在本文中，為了更全面地理解和描述問題，從而可以更有效和合理地解決問題，給定一個論域，我們使用劃分作為粒化方法，將多層次的?；椒ê投嘁暯堑牧；椒ㄏ嘟Y(jié)合，定義劃分序乘積空間.首先，使用論域上的一個劃分定義一個層.其次，使用一個嵌套的劃分序定義一個多層次，表示為一個視角，層和層之間具有線性序關(guān)系.最后，給定多個視角，則定義了多個線性序關(guān)系，基于多個線性序關(guān)系的乘積，定義劃分序乘積空間.證明了劃分序乘積空間是一個格結(jié)構(gòu).已有的基于多層次的?；椒ǖ玫降牧＝Y(jié)構(gòu)和基于多視角的?；椒ǖ玫降牧＝Y(jié)構(gòu)是劃分序乘積空間的特殊情況.

劃分序乘積空間給出了一種新的粒計(jì)算模型，在此基礎(chǔ)上，我們可以研究基于劃分序乘積空間的三支決策模型、基于劃分序乘積空間的粗糙集模型、基于劃分序乘積空間的概念格模型等，從而給出各種多層次多視角的問題求解策略和方法.在以后的工作中，我們將進(jìn)一步研究劃分序乘積空間的拓?fù)浣Y(jié)構(gòu)和相關(guān)性質(zhì).