商空間粒度的可逆性研究*

陳林書，王加陽，柳媛慧，馬 慶

1.湖南科技大學 計算機科學與工程學院，湖南 湘潭 411201

2.中南大學 計算機學院，長沙 410083

3.湖南軟件職業(yè)學院 軟件與信息工程學院，湖南 湘潭 411100

1 引言

粒計算是近年來計算機科學中一個非?；钴S的研究領域，是在分析和求解問題中應用分組、分類和聚類手段的一切理論、方法、技術和工具[1-7]。具體地，粒計算是模糊集（詞計算）理論、粗糙集理論、商空間理論和云模型等粒計算模型的超集。作為最重要的粒計算模型之一，商空間理論由張鈴教授首次提出[8-9]，現(xiàn)已迅速發(fā)展成完善的理論體系并廣泛應用于模式識別[10-12]、模糊信息處理[13-16]、圖形圖像處理和復雜問題求解等領域。

商空間理論的粒化過程，其本質是利用商拓撲的概念和等價關系的粒化規(guī)則實現(xiàn)求解問題從細粒度到粗粒度的商空間構造過程，其前提是通過保假原理使得某些關鍵性質必須能夠在商空間粒度上保留下來。商空間理論的目的是利用商空間粒度上的簡單易求的足夠滿意近似解代替精確解，以加快問題求解速度和降低問題計算復雜度。

但是，商空間粒度的構造過程，是一個信息有損過程，會導致部分細節(jié)信息的丟失，一般情況下不能將求解問題從商空間（粗）粒度上無損地還原到原空間（細）粒度上，也即商空間粒度的?；^程是不可逆的，除非給其增加一些約束性條件或附加信息。

文獻[17]從拓撲理論的角度給出了逆商拓撲和飽和集的概念，這為研究商空間粒度的可逆性提供了理論支持。文獻[18]提出了逆商關系的拓撲合成來探討不同層次上拓撲空間之間的關系，但并沒有討論商空間與原空間之間的轉換與對應關系，即沒有探討商空間粒度的可逆性條件。

針對以上問題，研究商空間粒度的可逆性，其目的是為商空間粒度的互逆性計算提供形式化方法，進一步豐富和完善商空間粒度轉換理論和粒計算方法。具體研究目標和貢獻如下：

（1）提出逆商空間的概念并定義其構造方法，為商空間（粗）粒度到原空間（細）粒度的可逆轉換提供數(shù)學方法；

（2）通過分析逆商空間與原空間的一致性，討論商空間粒度的可逆性條件，保證商空間粒度在一定條件下可以實現(xiàn)無損還原。

2 研究基礎

商空間理論中的商空間粒度和拓撲學理論中的拓撲、最粗拓撲、逆商拓撲、飽和集（飽和性）等概念是文中研究商空間粒度可逆性的理論基礎，本章將分別予以介紹。

定義1（拓撲）設T是集合X上的集簇，則稱(X,T)為拓撲空間，簡稱T為拓撲，若T滿足條件：

（1）?和X在T中；

（2）T中任意子集簇的并在T中；

（3）T中任意有限子集簇的交在T中。

定義2（最粗拓撲）設T和T1是集合X上的拓撲。若T1?T，則稱T1細于T，或稱T粗于T1；若T1?T，則稱T1嚴格細于T，或稱T嚴格粗于T1；若對于X上的任意拓撲T'，存在T'?T，則稱T為X上的最粗拓撲。

定義3（商空間）[9]給定問題粒度(X,f,T)上的一個等價關系R，其中X是粒集(論域)，f是粒屬性，T是粒結構，則稱三元組([X],[f],[T])為(X,f,T)相對于R的商空間，若滿足：

（1）商論域[X]為X對應于R的商集;

（2）商屬性[f]的定義[f]:[X]→Y與具體的應用有關，其中f:X→Y為屬性函數(shù)；

（3）T是拓撲，p:X→[X]是自然投影，商結構[T]的定義為：

定義3在本質上是利用了拓撲理論中商拓撲的概念來定義商空間粒度。商拓撲是在滿射f:X→Y映射下定義的，而定義3中的等價關系R:X→[X]顯然是一個滿射函數(shù)。因此，商拓撲與商空間粒度的定義是一致性的，即具有函數(shù)映射的連續(xù)性，并且下文3.3節(jié)中關于商空間粒度的兩個可逆性條件都是在滿射條件下進行討論。

定義3是商空間理論中關于商空間粒度的定義，它實際上是根據(jù)?；?guī)則(等價關系)R將求解問題從原空間(X,f,T)轉換到商空間([X],[f],[T])的一個?；^程，實現(xiàn)了問題從細粒度到粗粒度的轉換過程。

定義4（逆商拓撲）[17]設X是一個集合，(Y,TY)是一個拓撲空間，f:X→Y是一個函數(shù)，則稱TX為TY的逆商拓撲，若滿足：

定義4給出了構造逆商拓撲的數(shù)學方法，這為研究商空間粒度的可逆性提供了理論支持。

定義5（飽和集）[17]設X和Y是兩個集合，映射f:X→Y是滿映射。若對?U?X，有f-1(f(U))=U，則稱U關于f是飽和的（具有飽和性）。

當f單射時，U中每一個元素至多為一個自變元的函數(shù)值(無多值映射點)，這時充分有f-1(f(V))=V成立，即X的每個子集都是飽和集。

當f滿射時，?V?Y，f(f-1(V))=V，則f-1(f(f-1(V)))=f-1(V)，根據(jù)上述飽和集的定義，則f-1(V)為飽和集。因此，X中所有可作為映射f的逆象的子集都是飽和的，其他子集均不飽和。X中的飽和子集與其像具有一對一性。在商映射下，若f-1(V)是開集，則V?Y是開集，f-1(V)具有飽和性。

3 商空間粒度的可逆性

本章重點從以下三方面討論商空間粒度的可逆性：首先，指出商空間粒度的可逆性研究的必要性，即在一般情況下求解問題的原拓撲與其商拓撲的逆商拓撲是不一致的；然后，提出逆商空間的構造方法；最后，通過構造逆商空間與原空間的一致性條件，討論商空間粒度的可逆性條件。

因為粒屬性f的應用相關性[9]，在商空間理論模型(X,f,T)中，商屬性映射[f]:[X]→Y沒有一個普適性的定義方法。于是，文中暫且不討論粒屬性f，則一個具有拓撲粒結構的問題(對象)粒度可簡化表示為一個二元(X,T)，其中X是粒集(論域)，T是粒結構，具體為一個拓撲。

3.1 問題描述

從粒結構上來分析商空間粒度的?；^程。給定粒度(X,T)上的一個等價關系R，則根據(jù)定義3可獲得商結構[T]和商空間([X],[T])，且商論域映射X→[X]顯然是一個滿射，則根據(jù)定義4，可獲得[T]逆商拓撲TX。但是，一般情況下，上述逆商拓撲TX和原拓撲T是不一致的，且有TX?T。

以上說明，在等價關系R下，粒度(X,T)的?；^程是一個信息有損過程，在結構上不能進行無損還原。下面舉例說明。

例1設T、T1、T2分別是集合X上的拓撲，f:X→Y是滿射函數(shù)。其中f如表1所示，T、T1、T2分別如下：

Table 1 Mapping of Xand Yin Example 1表1 例1中X與Y的映射關系

由表1可知，f:X→Y是一個滿射函數(shù)也是一個等價關系，則由定義3可獲得原拓撲T的商拓撲TY={?,,Y}，再由定義4可獲得商拓撲TY的逆商拓撲TX={?,{3},X}。顯然，有TX?T。

類似地，由定義3可獲得T1、T2的商拓撲為：

再由定義4可獲得T1Y、T2Y的逆商拓撲為：

顯然，由上可知T1X=T1和T2X?T2，這與上述結論TX?T仍然是一致的。

上述例1表明，逆商空間與原空間不一定是一致的。原拓撲通過商映射誘導出商拓撲時存在著部分信息的丟失，而逆商拓撲是由商拓撲誘導出的，其開集與商拓撲中的開集一一對應，從而導致了逆商拓撲與原拓撲不一致的情況。

以上說明，商空間粒度的構造過程，是一個信息有損過程，會導致粒結構上的部分細節(jié)信息丟失，一般情況下不能將求解問題從商空間（粗）粒度上無損地還原到原空間（細）粒度上，即商空間粒度的?；^程是不可逆的，除非給其增加一些約束性條件或附加信息。

那么，在什么條件下商空間粒度的?；^程是可逆的呢？又如何來定義其可逆過程呢？接下來將予以詳細討論。

3.2 逆商空間的構造方法

上一節(jié)通過實例說明，一般地，逆商拓撲是比原拓撲更粗的拓撲。事實上，這一結果具有普適性，下面以定理的形式予以證明，這將是接下來定義逆商空間的構造方法并探討商空間粒度的可逆性條件的重要理論依據(jù)。

定理1設X是一個集合，(Y,TY)是一個拓撲空間，f:X→Y是一個函數(shù)，TX是TY的逆商拓撲，則TX是使f連續(xù)的最粗拓撲。

證明（1）先證TX是一個拓撲。

根據(jù)拓撲空間的定義來證明。①顯然，易證?,X∈TX；②若A,B∈TX，則根據(jù)定義4式（2）有A∩B=f-1(AY)∩f-1(BY)=f-1(AY∩BY)，又AY∈TY，BY∈TY，則有AY∩BY∈TY，因此有A∩B∈TX；③若TX1?TX，則有，又因為AY∈TY，則有，于是有。

（2）再證明TX使f連續(xù)。

根據(jù)函數(shù)連續(xù)的定義，如果Y中的每一個開集V的原像f(V)是X中的一個開集，則稱映射f是連續(xù)的。根據(jù)定義4中式（2），逆商拓撲TX就是根據(jù)拓撲TY的原像構造的，因此TX使f連續(xù)。

（3）再證明TX是使f連續(xù)的最粗拓撲。

根據(jù)函數(shù)連續(xù)的定義，若TX'使f連續(xù)，則TX'中包含{U?X|U=f-1(V),V∈TY}中的所有元素，則由（2）可得，TX?TX′，因此TX是使f連續(xù)的最粗拓撲。 □

定理1說明，經(jīng)過逆商拓撲運算，可更精簡原空間的拓撲結構，剔除那些無法通過f-1操作獲得的子集，也就形成最精簡的能體現(xiàn)規(guī)則f的拓撲，也就是一個拓撲的商拓撲及這個商拓撲對應的逆商拓撲，也即逆商拓撲是商拓撲在原空間中的最精確的一種對應關系。

有了定義4中的逆商拓撲概念和定理1的結論，則可以定義逆商空間的構造方法。

定義6（逆商空間）設R是問題原空間(X,T)上的等價關系，([X],[T])是(X,T)的商空間，其中f:X→[X]是對應于R的一個自然投影，則稱(X,TX)為([X],[T])相對于f的逆商空間，若滿足：

定義6給出了構造逆商空間的數(shù)學方法，這為商空間粒度的可逆性研究提供了形式化支持。

當粒度(X,T)根據(jù)等價關系R?；酱至６鹊纳炭臻g([X],[T])上之后，定義6給出了根據(jù)等價關系R由粗粒度的商空間([X],[T])到細粒度的逆商空間(X,TX)的可逆性轉換的數(shù)學方法。

3.3 商空間粒度的可逆性條件

定理1說明，在一般情況下，逆商拓撲TX和原拓撲T是不一致的。定義6給出了逆商空間的構造方法。那么，在什么情況下原空間(X,T)與逆商空間(X,TX)一致呢？本節(jié)將探討逆商空間與原空間的一致性條件，也即商空間粒度的可逆性條件。

下面討論商空間粒度可逆的第一個條件，即若f是雙射函數(shù)，則逆商空間與原空間是一致性的。接下來以定理的形式給出并予以證明，再結合例題進行分析。

定理2設f:X→Y是粒度空間(X,T)上的滿映射，(Y,TY)是(X,T)相對于f的商空間，(X,TX)是(Y,TY)相對于f的逆商空間。則若f是雙射函數(shù)，有TX=T。

證明（1）先證TX?T。對?V∈TX，由定義6有V=f-1(U)，U∈TY，又 ?U∈TY，則有f-1(U)∈T，即V∈T，則有TX?T。

（2）再證T?TX。對 ?V∈T，令f-1(V)=U，因為f是雙射函數(shù)，則有f-1(f-1(V))=f-1(U)=V∈T，于是有U∈TY；根據(jù)定義6，若U∈TY，則f-1(U)=V?TX，則有f-1(U)=V∈X，則有T?TX。

由（1）和（2）可知，TX=T，定理得證。 □

定理2說明，若給定粒度(X,T)上的一個滿射函數(shù)f，則根據(jù)雙射f可獲得商空間(Y,TY)，進而獲得逆商空間(X,TX)，此時逆商空間(X,TX)與原空間(X,T)是一致的。

例2設(X,T1),(X,T2)是集合X上的拓撲空間，f:X→Y是雙射函數(shù)，其中f如表2所示，T1、T2分別如下：

Table 2 Mapping of Xand Yin Example 2表2 例2中X與Y的映射關系

由定義3，可分別求得商空間(Y,T1Y),(Y,T2Y)，其中T1Y、T2Y分別為：

再由定義6，可分別求得逆商空間(X,T1X),(X,T2X)，其中T1X、T2X是：

由上可知，有T1X=T1,T2X=T2。

定理2和例2說明，若給定粒度上的一個雙射函數(shù)，對粒度求商空間再求逆商空間之后，原空間與逆商空間是一致性。

但是，上述可逆性條件中，因為商空間與原空間同胚，不具有粘合性，也即商空間與原空間在粒度粗細上是一樣，由原空間到商空間的?；^程本質上并沒有簡化問題求解規(guī)模，所以在商空間求解問題時并不具有太大的實際意義。

于是，根據(jù)定義5中飽和集的概念可獲得第二個可逆性條件，即若原拓撲T中的任意開集都是飽和的，則逆商空間與原空間是一致性的。下面以定理的形式給出并予以證明。

定理3設f:X→Y是粒度空間(X,T)上的滿映射，(Y,TY)是(X,T)相對于f的商空間，(X,TX)是(Y,TY)相對于f的逆商空間。若?V∈T，有f-1(f(V))=V，即T中任意開集V關于f是飽和的，則有TX=T。

證明（1）先證TX?T。對?U∈TX，由定義6有U=f-1(V)，V∈TY，又 ?V∈TY，則有f-1(V)∈T，即U∈T，則有TX?T。

（2）再證T?TX。因為T中任意開集V關于f是飽和的，即對?V∈T，有f-1(V)=U，則有f-1(f-1(V))=f-1(U)=V∈T，于是有U∈TY；根據(jù)定義6，若U∈TY，則f-1(U)=V?TX，則有f-1(U)=V∈X，則有T?TX。

由（1）和（2）可知，TX=T，定理得證。 □

定理3說明，若粒度(X,T)上的任意開集都是關于f飽和的，即?V∈T，有f-1(f(V))=V，則根據(jù)滿射f獲得商空間(Y,TY)，進而獲得逆商空間(X,TX)后，其逆商空間(X,TX)與原空間(X,T)是一致的。下面再舉例進一步說明定理3的結論。

例3設(X,T1),(X,T2)是集合X上的拓撲空間，f:X→Y是滿射函數(shù)，其中f如表3所示，T1、T2分別如下：

Table 3 Mapping of Xand Yin Example 3表3 例3中X與Y的映射關系

由定義3，可求得(X,T1),(X,T2)的商空間(Y,T1Y),(Y,T2Y)，其中：

再由定義6可得(Y,T1Y),(Y,T2Y)的逆商空間(X,T1X),(X,T2X)，其中：

顯然有T1X=T1，即逆商空間(X,T1X)與原空間(X,T1)是一致的。

再根據(jù)定理3，也可以得出相同的結論T1X=T1，因為對?V∈T1，都有f-1(f(V))=V，即T中任意開集為X關于f的飽和開集。

但是，T2X≠T2，即逆商空間(X,T2X)與原空間(X,T2)是不相同的。

再根據(jù)定理3，也可以得出相同的結論T2X≠T2，因為根據(jù)飽和集的定義，拓撲T2中的開集{3}、{1,2}、{1,2,3}關于f是飽和的，而開集{1}、{2}、{1,3}、{2,3}關于f是不飽和的。

定理3和例3說明，若原空間中的開集都具有飽和性，其導出商空間后再求出的逆商空間與原空間是一致的；若原空間中既包含關于映射f的飽和開集也包含非飽和的開集，則在導出商空間過程中非飽和開集就已經(jīng)被剔除了，再對其進行求逆商的運算之后得到的逆商拓撲只包含了原空間中關于映射f的飽和集部分，此時逆商空間包含于原空間，是一個比原空間更粗的拓撲空間。

4 結束語

先提出了逆商空間的概念并定義了其構造方法，為商空間（粗）粒度到原空間（細）粒度的可逆轉換提供了形式化的數(shù)學方法；然后論證并實例分析了商空間粒度的兩個可逆性條件——定義原空間上的雙射函數(shù)或保證原空間上所有開集的飽和性，從而保證商空間粒度在一定條件下可以實現(xiàn)無損還原。

但是，還需進一步探討是否存在商空間粒度可逆的其他條件，例如對映射條件的約束，是否可以通過多個滿射函數(shù)進行轉換，使得逆商空間與原空間具有一致性。同時，張鈴教授提出的商空間理論指定粒結構為特定的拓撲空間，若能從代數(shù)運算、偏序和圖等粒結構上擴展研究商空間理論，將有利于商空間理論的應用推廣。文獻[19-21]提出了代數(shù)粒計算模型及其理論體系，接下來還將繼續(xù)深入研究粒度轉換和粒計算理論及其應用。

《計算機工程與應用》投稿須知

中國科學引文數(shù)據(jù)庫（CSCD）來源期刊、北大中文核心期刊、中國科技核心期刊、RCCSE中國核心學術期刊、《中國學術期刊文摘》首批收錄源期刊、《中國學術期刊綜合評價數(shù)據(jù)庫》來源期刊，被收錄在《中國期刊網(wǎng)》、《中國學術期刊（光盤版）》、英國《科學文摘》（SA/INSPEC）、俄羅斯《文摘雜志》（AJ）、美國《劍橋科學文摘》（CSA）、美國《烏利希期刊指南》（Ulrich’s PD）、《日本科學技術振興機構中國文獻數(shù)據(jù)庫》（JST）、波蘭《哥白尼索引》（IC），中國計算機學會會刊

《計算機工程與應用》是由中國電子科技集團公司主管，華北計算技術研究所主辦的面向計算機全行業(yè)的綜合性學術刊物。

辦刊方針堅持走學術與實踐相結合的道路，注重理論的先進性和實用技術的廣泛性，在促進學術交流的同時，推進科技成果的轉化。覆蓋面寬、信息量大、報道及時是本刊的服務宗旨。

報導范圍行業(yè)最新研究成果與學術領域最新發(fā)展動態(tài)；具有先進性和推廣價值的工程方案；有獨立和創(chuàng)新見解的學術報告；先進、廣泛、實用的開發(fā)成果。

主要欄目理論與研發(fā)，大數(shù)據(jù)與云計算，網(wǎng)絡、通信與安全，模式識別與人工智能，圖形圖像處理，工程與應用，以及其他熱門專欄。

注意事項為保護知識產(chǎn)權和國家機密，在校學生投稿必須事先征得導師的同意，所有稿件應保證不涉及侵犯他人知識產(chǎn)權和泄密問題，否則由此引起的一切后果應由作者本人負責。

論文要求學術研究：報道最新研究成果，以及國家重點攻關項目和基礎理論研究報告。要求觀點新穎，創(chuàng)新明確，論據(jù)充實。技術報告：有獨立和創(chuàng)新學術見解的學術報告或先進實用的開發(fā)成果，要求有方法、觀點、比較和實驗分析。工程應用：方案采用的技術應具有先進性和推廣價值，對科研成果轉化為生產(chǎn)力有較大的推動作用。

投稿格式1.采用學術論文標準格式書寫，要求文筆簡練、流暢，文章結構嚴謹完整、層次清晰（包括標題、作者、單位、摘要、關鍵詞、基金資助情況、所有作者簡介（含通訊作者電子信箱）、中圖分類號、正文、參考文獻等，其中前6項應有中、英文）。中文標題必須限制在20字內(nèi)（可采用副標題形式）。正文中的圖、表必須附有圖題、表題，公式要求用MathType編排。論文字數(shù)根據(jù)論文內(nèi)容需要，不做嚴格限制，對于一般論文建議7 500字以上為宜。2.請通過網(wǎng)站（http://www.ceaj.org）“作者投稿系統(tǒng)”一欄投稿（首次投稿須注冊）。