因素空間中屬性約簡的區分函數

曲國華，李春華，張強

粗糙集[1]、形式概念分析[2]和因素空間[3]是在1982年同時誕生的3個數學流派。3種理論都明確地把知識與思維過程作為數學描述的對象，可被視為智能數學的代表。其中，在數據庫中最早付諸實踐的是粗糙集。其領軍人物Polkowski和Skowron[4]在1989發表的《粗糙集與知識發現》一文引領了第十屆國際人工智能大會上所提出的KDD(數據庫知識發現)的新潮流。粗糙集用屬性所構建的信息系統來描寫事物，用各種細化的熵指標來實現信息的標度，為數據知識挖掘提供了理論基礎。相比之下，Wille的形式概念分析就沒有那么明確的實際背景。他的理論是在被埋沒了12年之后，才被人們發現的。他的《形式概念分析》一書圍繞概念格提取這一主題而展開，數學嚴謹。集合論向世人強調了任何概念的外延都是一個集合。但若反過來問：任何集合都一定是概念的外延嗎？就不好回答了。Wille明確地回答：No！他第一次明確地從數學上提出了內涵與外延之間的對合性條件，只有滿足對合性的集合和屬性對才能形成概念。這是他的重要貢獻。在這一點上粗糙集的用詞就顯得太粗糙了。它把由任一映射所形成的劃分都叫做知識，那么，任一集合都可以由其特征函數形成一個劃分。由此可推得：任一集合必是某概念的外延，這就與Wille的理論產生了矛盾。人工智能要運用概念進行識別與搜索，內涵是我們識別事物的依據，外延是我們實現搜尋的結果，如果內涵與外延不相一致，那么人工智能就不具備實踐的前提。這不能不說是粗糙集在用詞上的一個疏忽。

在對屬性的稱呼上也存在著矛盾。例如，顏色有紅、黃、藍 ·· ···· 之分，是把顏色叫做一個屬性，還是把紅、黃、藍等都叫做屬性？屬性的英文是Attribute。Wille曾以科教片《生物與水》為例來區分說：魚和水草都是“在水中生活”而狗和豆卻是“在陸地上生活”。他把“在水中生活”與“在陸地上生活”這兩個詞視為兩個不同的attribute[16]?？梢?，Attribute是指屬性的狀態，而不是指“生物棲性”這一屬性名稱。但是，粗糙集則把汽車按顏色、車長、車重、馬力、里程等屬性來分類，在那里，Attribute指的是顏色、車長、車重，它們都是屬性的名稱而不是屬性值[15]。這兩種不同的用法一直被國人懵懂地引用著。細心的學者把Wille的Attribute譯成屬性值而把粗糙集中的Attribute譯成屬性名，這是十分明智的。

以上矛盾并沒有影響粗糙集與形式概念的融合，二者求同存異，彼此互補，都得到了良好的發展[5-6]。Wille的形式背景表以屬性值來分列，而粗糙集的信息系統表以屬性名來分列，前者的應用效率是比不上后者的。所以，粗糙集在應用鄰域一直先行。在跨世紀的年代里，粗糙集在屬性約簡方面一度在機器學習的應用鄰域走紅，當時，特征提取仍然是人工智能的瓶頸，特征要靠專家的經驗來提取，這就必須限定識別空間的維數。在高維度數據面前，如何降低維度是最大的關鍵。于是，粗糙集的屬性約簡方法被人們視為新的希望。出現了大量應用屬性約簡來提取特征的研究[7-9]。尤其是支持向量機與屬性約簡相結合[10]，更使人注目。遺憾的是，這個時期不太長久，屬性約簡目前已經減弱了。因為屬性約簡要用到一個概念工具，叫做區分矩陣（或差異矩陣）。正是由于這個概念的奇特性影響了事態發展。為了說明這件事情，需要回顧一下有關定義。

1 粗糙集信息系統

在粗糙集中，一個信息系統（或稱知識表達系統）被描述成一個四元組S=(U, A, V, f)，其中U是對象的非空集合，A是屬性名的集合，V是屬性值的集合，f是從對象x就著屬性A向V所作的映射。為了便于理解，我們對以下所引用的定義符號都略有改變。

定義1[11]矩陣叫做S上的一個區分矩陣（discernibility matrix），其中

定義2[11]區分函數Δ的定義為

在這里設A={a1, a2, ···, am}，這里便設置了m個布爾變量。于是便被指定成括號中所包含的布爾變量的析取，設那幾個變量是, 所指定的這個布爾變量便具有布爾表達式。由于這個布爾表達式中只含析取運算，叫做析取式。而在式（2）中，由于Δ是由布爾變量先組成析取式而后再進行合取，這種表達形式叫做合取范式。布爾代數中有方法把Δ從合取范式改寫為析取范式∑，∏意思是把析取與合取的運算次序顛倒一下。就叫做析取范式。再把析取的這些析取式一一甄別，去掉被蘊含的項，剩下的表達式就叫做極小析取范式。文獻[12]的核心論斷是：區分函數的極小析取范式中的每一個合取項就是S的一個屬性約簡，反之亦然。以上就是粗糙集關于屬性約簡的基本論述。

對于上述內容，應用工作者多看不懂，數學工作者則想不明。有一連串問題：對于屬性a為什么要指定一個布爾變量，指定后的運算意義和根據是什么不太明確。布爾變量的析取（∨或∑）合?。ā幕颉牵τ趯傩詠碚f究竟是什么意思？若不存在將對象x與y分開的屬性名，為什么對a(x, y)指定布爾變量1而不是0？為什么區分函數的極小析取范式中的所有合取項就是S的全部屬性約簡粗糙集？如此等等都阻礙了人們的理解和應用。

最關鍵的問題是，粗糙集從未定義過屬性名之間的運算，而區分矩陣這一工具所要操作的就是屬性名運算。這就形成一種理解障礙。人們曾想通過實際經驗來越過障礙，但是，粗糙集中的屬性指的是屬性名而不是屬性值。我們都有屬性值之間的運算經驗，要把“頭發金黃”與“身材高大”這兩個屬性值進行“且”的運算，我們能理解這種運算結果就是屬性值“頭發金黃而且身材高大”。可是，要把“身材”與“發色”這兩個屬性名來加以或、且、非的運算，我們便無從想象了。

其實，這里只差一步，就是應當對屬性名稱定義運算，給這些運算以合理解釋，這個理解障礙就能克服。屬性約簡的方法就能繼續向前發展，降溫的應用領域就能重新熱起來。而這方面的工作，因素空間早就做了。因素就是粗糙集中所說的屬性名。因素空間特地定義了因素之間的運算。本文就是要用因素空間的理論來解釋區分矩陣。并給屬性約簡提供新的發展思路。

2 因素空間中分辨過程的因素約簡

因素空間是汪培莊[12]在1982年提出的以智能描述為主題的數學理論，曾在知識表示和人工智能領域發揮過重要作用，近年來，又以數據科學為重點，為大數據處理提供堅實的數學基礎[13-15]。

因素f是串領屬性的關鍵詞。紅，黃，藍，百，黑· · ····，是一串屬性值，由顏色二字來串領，顏色f就叫因素，它所串出的屬性值的集合叫做f的（屬性）狀態空間，記作X(f)={紅，黃，藍，百，黑， · ··}，它形成一個維度，一種廣義的坐標軸，因素是抽象坐標的維度名稱。因素是分析，把對象映射稱為定性值，分析以后再綜合，就形成一個廣義的坐標架，事物就被描述成為其中的點。因素空間企圖為事物描述及認知過程提供一個普適的坐標架。因素空間中的因素就是粗糙集中所說的屬性名。因素空間中所說的屬性，就是粗糙集中的屬性值。

定義3[10]稱集合族為U上的一個因素空間，如果滿足公理：

2) X(0)={}；

F叫做因素集，其最大、最小元1和0分別叫做全因素和零因素，X(f)叫做f-性態空間。

所謂一個因素空間就是以因素為指標集的一族屬性狀態空間，而這些因素之間有運算，構成一個布爾代數F=(F, ∨, ∧,c)。運算符∧、∨分別表示因素的分解與綜合，其中難以理解的是分解。這要通過因素在粗細上所形成的序關系來說明。因素的考量維度有多寡之分。考慮的維度少，對象就朦朧難分，考慮的維度多，對象才能彼此分離。越大越細，越小越抽。如果因素f所作的劃分比因素g的劃分更細的話，我們就稱f比g大，記作f≥g。f比g大當且僅當對任意u, v∈U, 若f(u)=f(v)則g(u)=g(v)(或者，若 g(u)≠g(v)則 f(u)≠f(v))。

不難證明，（F, ≥）是一個偏序集。而且布爾代數的運算就是依托這個序關系而建立起來的：f∨g=sup(f, g)；f∧g=inf(f, g)。若把序關系形象地說成是上下級關系，f∨g就是f與g的最小公共上司，f∧g就是f與g的最大公共下級。所以，我們把因素的（∨，∧）運算不做析取–合取運算，而是反過來叫做綜合–分解運算。因素是分析與綜合的工具。分解∧是將因素由大變?。ㄓ纱肿兗殻┑倪^程，而綜合∨是使因素由小變大（由細變粗）的反過程。F=(F, ∨, ∧,c)形成一個布爾代數，因素是其中的布爾變量。最大、最小元1和0分別叫做全因素與零因素。一個因素不能分解成除自己與零因素之外的下級因素（簡稱因子）叫做質因素或原子因素。對于區分事物來說，因素合得越大，區分的能力就越強，這是一條最基本的原則。

因素空間中的因素就是粗糙集中所說的屬性名。因素空間中所說的屬性，就是粗糙集中的屬性值。因素空間對區分矩陣的詮釋，是從對事物的分辨開始的。

粗糙集的區分矩陣是對對象兩兩分辨的因素集為元素的矩陣。由于因素本身就是布爾變量，就無需再作什么指定。因素之間早就定義了綜合與分解的運算，并且約定，一組相對簡單的因素可以通過綜合而形成一個復雜因素。所以，區分矩陣更可以理解成是以兩兩分辨因素為元素的矩陣。矩陣中的元素是一個復雜因素(用一個復雜因素去取代因素的集合)。

命題2 若f能分辨A，且BA，則f能分辨B。

證明顯然成立。

定義5 稱因素空間是正則的，如果能保證：f∧g能分辨A，只要f與g都能分辨A。

雖不能證明所有因素空間都是正則的，但正則性卻是普遍地近似的存在著。

命題3 在正則因素空間里，若f1能分辨A1, A2, ···,fn能分辨An, 則能 分辨。

證明由命題2知，對任意j=1, 2, ···, n, fj能分辨由于正則性知本命題真。證畢。

f(u, v)是能區分u與v的因素的最大下級公共因素。這樣的因素越少，公共下級因素就越大，當沒有這樣的因素時，公共下級因素就取最大。全因素應當能區分所有的對象。對角線上的元素全是1。這也解釋了定義中的約定為什么是合理的。

注意，這里的區分函數就是定義2中所說的區分函數，只不過把析取與合取的符號互相顛倒罷了。

命題4 在正則的因素空間中，若區分矩陣中不出現最小元0，A的因素區分函數就是能分辨A的最小因素。

證明 在正則的因素空間中，由命題2.3知f(u,v)能分辨u與v。因，所以根據命題2.1，對任意u, v∈A，d(A)都能分辨u與v，亦即。這就說明d(A)能分辨A。

設g能分辨A，則對任意u, v∈A, u≠v, 都有g(u)≠g(v)。于是，。所以 f(u, v)≤g。由于這個不等式對任意 u, v∈A（u≠v）都成立，便有d(A)≤g，故d(A)是能分辨A的最小因素。

證畢。

注意，粗糙集用區分矩陣提取的是極小屬性約簡，本文提出的是最小因素。這看起來是一大進步，但是，命題4中要求區分矩陣不出現0分解，這是一個太強的約束，現實意義不大。

定義 8 設因素 f、g都能分辨 A，且 f＜g，則稱在分辨A上f是對g的約簡因素，從f到g，叫做是一次因素約簡。固定A=U，g=全因素1，1的約簡因素就叫約簡因素。因素約簡問題就是要找出約簡因素，越小越好。因素空間對此提供了另一種現實的因素約簡的途徑，一是概念劃分中以分辨度來實現的因素約簡算法，一是決策表以決定度來實現的因素約簡算法，其復雜度為O(m2n)，這里m、n分別表示對象和因素的個數。

3 結束語

因素空間中所說的因素是事物生成與思維描述的第一要素。它與粗糙集的屬性名相通，但卻有更深刻的涵義，它是事物的質根，是廣義的基因，它不是被動地描述事物，而是引領著人們的思考，出點子，想辦法，都指的是因素，抓注意矛盾，也抓的是因素。運用因素之間的運算，除了能說清楚什么是區分矩陣以外，還能在屬性約簡的實際算法上作貢獻。用區分函數來約簡屬性是一種理想的方式，其算法很難實現，粗糙集用區分矩陣求極小屬性存在著N-hard困境，有的文獻要用到整值規劃，后者的復雜性已被證明是指數型的，不存在多項式算法。因素空間可以提供簡捷的算法。

[1]PAWLAK Z. Rough sets[J]. International journal of computer and information sciences, 1982, 11(5): 341–356.

[2]WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]. Ordered sets. Springer. 1982:445-470.

[3]汪培莊, SUGENO M. 因素場與模糊集的背景結構[J]. 模糊數學, 1992(2): 45–54.WANG Peizhuang, SUGENO M. The factors field and background structure for fuzzy subsets[J]. Fuzzy mathematics, 1992(2): 45–54.

[4]POLKOWSKI S L, SKOWRON S A. Rough sets in knowledge discovery 2 [M]. Physica-Verlag HD, 1989.

[5]葉東毅, 陳昭炯. 一個新的差別矩陣及其求核方法[J]. 電子學報, 2002, 30(7): 1086–1088.YE Dongyi, CHEN Zhaojiong. A new discernibiligy maatrix and the computation of a core[J]. Acta electornica sinica,2002, 30(7): 1086–1088.

[6]王昊, 朱惠, 鄧三鴻. 基于形式概念分析的學科術語層次關系構建研究[J]. 情報學報, 2015(6): 616–627.WANG Hao, ZHU Hui, DENG Sanhong. Study on construction of hierarchy relationship of subject terms based on formal concept analysis[J]. Journal of the China society for scientific andtechnical information, 2015(6): 616–627.

[7]李元誠, 方廷健. 一種基于粗糙集理論的SVM短期負荷預測方法[J]. 系統工程與電子技術, 2004, 26(2): 187–190.LI Yuanchen, FANG Tingjian. Approach to forecast shortterm load of SVM based on rough sets[J]. Systems engineering and electronics, 2004, 26(2): 187–190.

[8]張騰飛, 肖健梅, 王錫淮. 粗糙集理論中屬性相對約簡算法[J]. 電子學報, 2005, 33(11): 2080–2083.ZHANG Tengfei, XIAO Jianmei, WANG Xihuai, et al. Algorithms of attribute relative reduction in rough set theory[J]. Acta electornica sinica, 2005, 33(11): 2080–2083.

[9]戎曉霞, 劉家壯, 馬英紅. 基于Rough集的決策表屬性最小約簡的整數規劃算法[J]. 計算機工程與應用, 2004,40(11): 24–25.RONG Xiaoxia, LIU Jiazhuang, MA Yinghong. Integer programming algorithm for finding minimal reduction in decision table based on rough set[J]. Computer engineering and application, 2004, 40(11): 24–25.

[10]XU Y, WANG L. Fault diagnosis system based on rough set theory and support vector machine[C]//Proceedings of the Fuzzy Systems and Knowledge Discovery, Second International Conference. Changsha, China.2005.

[11]張文修. 粗糙集理論與方法 [M]. 北京：科學出版社,2001.ZHANG Wenxiu. Theory and method of rough set[M].Beijing: Science Press, 2001.

[12]汪培莊, 李洪興. 知識表示的數學理論 [M]. 天津:天津科學技術出版社, 1994.WANG Peizhuang, LI Hongxing. A mathematical theory on knowledge representation[M]. Tianjin: Tianjin Scientific and Technical Press, 1994.

[13]汪培莊. 因素空間與因素庫[J]. 遼寧工程技術大學學報:自然科學版, 2013, 32(10): 1–8.WANG Peizhuang. Factor spaces and factor data-bases[J].Journal of Liaoning technical university: natural science,2013, 32(10): 1–8.

[14]汪培莊, 郭嗣琮, 包研科, 等. 因素空間中的因素分析法[J]. 遼寧工程技術大學學報: 自然科學版, 2014, 33(7):865–870.WANG Peizhuang, GUO Sicong, BAO Yanke, et al.Factorial analysis in factor space[J]. Journal of Liaoning technical university: natural science, 2014, 33(7): 865–870.

[15]劉海濤, 郭嗣琮. 因素分析法的推理模型[J]. 遼寧工程技術大學學報, 2015, 34(1): 124–128.LIU Haitao, GUO Sicong. The reasoning model for factorial analysis[J]. Journal of Liaoning engineering technical university, 2015, 34(1): 124–128.