鄂 旭，韓 芳，侯 建，畢佳娜，張龍昌

(1.渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院，遼寧錦州121001;2.中國產(chǎn)業(yè)安全研究中心，北京100084;3.遼寧工業(yè)大學(xué)電子與信息工程學(xué)院，遼寧錦州121001)

0 引言

食品安全評價問題是研究食品安全的一項(xiàng)重要內(nèi)容，也是一個熱點(diǎn)和難點(diǎn)問題［1-4］。目前比較流行的方法是主成分分析方法、模糊數(shù)學(xué)等。但這些方法都無法較客觀地確定各個評價指標(biāo)的重要程度。

粗糙集理論是一種研究不完整、不確定性知識的數(shù)學(xué)工具［5-7］，其主要思想是直接從給定問題的描述集合出發(fā)，在保持分類能力不變的前提下，通過知識約簡，導(dǎo)出概念的分類規(guī)則，屬性約簡方法是粗糙集理論的核心內(nèi)容之一。Ziarko等［8］已經(jīng)證明找出一個決策表的最小約簡是NP-hard問題。目前求解屬性約簡的方法主要缺點(diǎn)是計(jì)算復(fù)雜度高，只能處理小數(shù)據(jù)集［9-11］。

筆者引入了粗糙集的粗糙度這一概念，采用遞歸的處理方法，定義了一種基于粗糙集的粗糙度的屬性約簡方法。該方法能降低計(jì)算復(fù)雜度。

1 粗糙集的相關(guān)定義

定義1 知識和知識庫:給定一組數(shù)據(jù)集合U和等價關(guān)系集合R，在R下對U的劃分稱為知識，記為U/R。U上的一簇劃分(對U的劃分)稱為關(guān)于U的知識庫。

設(shè)U是個論域，R是U上的一個等價關(guān)系。U/R表示U上由R導(dǎo)出的所有等價類。［x］R表示包含元素x的R的等價類，x∈U。

定義2 信息系統(tǒng)［6］:一個知識表達(dá)系統(tǒng)是個四元有序組S=(U，A，V，f)，其中U是論域，是對象的非空有限集合;A是屬性集合是屬性值的集合，Va是屬性a的值域;f:U×A→V是信息函數(shù)，它為每個對象的每個屬性賦予一個信息值，即?a∈A，x∈U，f(x，a)∈Va。

知識表達(dá)系統(tǒng)也稱為信息系統(tǒng)，通常表示為S=(U，A)，代替S=(U，A，V，f)。

定義3 不可分辨關(guān)系［6］:信息系統(tǒng)S=(U，A，V，f)，對于每個屬性子集B?A，定義一個不可分辨的二元關(guān)系IND(B)是一個等價關(guān)系，且

定義4 集合的上下近似集［7］:給定知識庫S=(U，R)，對于每個子集X?U和一個等價關(guān)系R∈IND(S)。R-X=∪{Y∈U/R∧Y?X}和R-X=∪{Y∈U/R∧Y∩X≠φ}分別稱其為X的R下近似集和R上近似集。

定義5 約簡:設(shè)U為一個論域，P和Q為U上的兩個等價關(guān)系簇，若P的Q獨(dú)立子集S?P有POSS(Q)=POSP(Q)，則稱S為P的Q約簡?？捎汸的所有Q約簡關(guān)系簇為RedQ(P)。

設(shè)U為一個論域，P和Q為定義在U上的兩個等價關(guān)系簇，RedQ(P)為P的所有Q約簡關(guān)系簇，COREQ(P)為P的Q核，則COREQ(P)=∩RedQ(P)。

定義6 設(shè)U為一個論域，P和Q為定義在U上的兩個等價關(guān)系簇，Q的P正域記為POSP(Q)，定義為

正域:POSB(X)=B-(X)。根據(jù)知識B，即U中一定能歸入集合X的對象構(gòu)成的集合。

定義7 決策信息系統(tǒng):(DS:Decision Information System)是一種信息系統(tǒng)，其屬性A被分成條件屬性c和決策屬性d(c∪d=A，c∩d=φ)兩個不同的集合。

相容決策信息系統(tǒng):對于一個相容的決策信息系統(tǒng)SD=(U，A，V，f)，A=c∪d，如果兩個樣本的決策值不相同，則存在這兩個樣本的一個或多個條件屬性也不相同。即:若?m，n∈U，d(x)≠d(y)，則存在c∈A，使 c(x)≠c(y)。

定義8 假定集合X是論域U上的一個關(guān)于知識B的粗糙集，定義其B的精度為dB(X)=其中X≠A;如果X=A，可定義由此可見，粗糙集X的精度是個在區(qū)間［0，1］上的實(shí)數(shù)，它定義了粗糙集X的可定義程度，即集合X的確定度。

定義9 假定集合X是論域U上的一個關(guān)于知識B的粗糙集，定義其B的粗糙度為PB(X)=1-dB(X)。X的粗糙度與精度恰恰相反，表示集合X知識的不完全程度［6］。

2 相關(guān)定理

在一個決策信息系統(tǒng)中，條件屬性是c，決策屬性是d。如果在不可分辨集合中相應(yīng)的條件屬性ci的決策值d相同，則該決策系統(tǒng)是相容的;否則，該決策系統(tǒng)不相容。

定理1 假設(shè)在一個決策信息系統(tǒng)SD=(U，A，V，f)中，A=c∪d是相容的，則有POSc(d)=U成立。

證明 假設(shè)POSc(d)≠U，即樣本的決策值d相同時，至少有兩個樣本的條件屬性c是完全一致的，則這兩個完全一致的條件屬性必是可分辨集合。這與前面的論述:在一個決策信息系統(tǒng)中，條件屬性是c，決策屬性是d，如果在不可分辨集合中相應(yīng)的條件屬性ci的決策值d是相同的，則該決策系統(tǒng)就是相容的，是矛盾的。所以假設(shè)不成立，有POSc(d)=U。

定理2 在一個相容決策信息系統(tǒng) SD=(U，A，V，f)，A=c∪d中，如果R是個約簡集，R?C，a∈C-R，則在其下近似集R-(X)上添加一個屬性a后不影響R的正域POSR(X)。即POSR(X)成立。

證明 在相容決策信息系統(tǒng)中，若R是個約簡集，R?C，a∈C-R，則說明a在此系統(tǒng)中是不必要的，因?yàn)椴槐匾年P(guān)系在知識庫中是多余的，如果將其從知識庫中去掉，不會改變該知識庫的分類能力，所以正域POSR(X)不會受到影響，即成立。

定理3 設(shè)集合簇 F={X1，X2，…，Xn}是定義在論域 U上的知識，B是個屬性子集。若有i∈{1，2，…，n}，使 B-(Xi)≠φ，則對任意 j(j≠i，j∈{1，2，…，n})都有 B-(Xj)≠U。

證明 如果存在i∈{1，2，…，n}，使B-(Xi)≠φ 成立，則會存在x(x∈Xi)使［x］B?B-(Xi)成立。然而，當(dāng) B-(Xi)?Xi時，對任意的 j(j≠i，j∈{1，2，…，n})，［x］B∩Xj=φ 都成立。所以，存在 x使 x?B-(Xj)成立，也就是B-(Xj)≠U。

定理 4 設(shè)集合簇 F={X1，X2，…，Xn}是論域 U上定義的知識，B是屬性子集。若存在i∈{1，2，…，n}，使 B-(Xi)≠U，則對任意 j(j≠i，j∈{1，2，…，n})都有 B-(Xj)=φ。

證明 根據(jù)定理3可以知道，當(dāng)B-(Xi)=U時，對任意的x都應(yīng)有［x］B∩Xi≠φ成立。然而對任意的 j(j≠i，j∈{1，2，…，n})，Xi∩Xj=φ 都成立，即［x］B?Xj成立，這說明x?B-(Xj)，即 B-(Xj)中沒有任何的元素，所以B-(Xj)=φ成立。

3 算法描述

粗糙集的不可定義性(不確定性)是由于粗糙集X的邊界不確定引起的。集合X的邊界區(qū)域越大，其確定性程度越小。可用集合X的精度和粗糙度描述粗糙集X的不確定性程度。

由dB(X)的公式可知，粗糙度公式為所以PB(X)越小，dB(X)越大，B的精度也越大，集合X的確定性也越大，這樣得到的集合X的邊界區(qū)域越小。顯然，邊界區(qū)域越小，表明條件屬性集B區(qū)分決策屬性集D的能力越強(qiáng)。

輸入 一個相容的決策信息系統(tǒng)SD=(U，A，V，f)，A=c∪d。

輸出 決策信息系統(tǒng)的屬性約簡。

初始化 Red←φ，c←c-Red。

步驟1 計(jì)算每個條件屬性相對于決策屬性的上下近似值;

步驟2 計(jì)算每個條件屬性對應(yīng)的PB(X)，將每個屬性c的所有值排列，選擇值最小的條件屬性ci，如果存在多個屬性列具有相同的值，則隨機(jī)選擇一個屬性作為約簡屬性;

步驟4 如果U=φ，轉(zhuǎn)到步驟7，否則轉(zhuǎn)到步驟5;

步驟5 分別計(jì)算每個新屬性列對應(yīng)的PB(X)值，并按照值的大小進(jìn)行排序，選擇值最小的屬性cj，如果存在多個屬性列具有相同的值，則隨機(jī)選擇一個屬性作為約簡屬性，Red←Red∪{cj}，c←c-Red，U←U-POSReddx5vz5t;

步驟6 若U=φ，轉(zhuǎn)到步驟7，否則轉(zhuǎn)到步驟5;

步驟7 輸出得到的約簡屬性集Red。

4 實(shí)例

為進(jìn)一步描述算法過程，下面用一個具體實(shí)例說明，信息表如表1所示。

根據(jù)表1所提供的一個關(guān)于食品安全評價指標(biāo)系統(tǒng)說明如何用上述改進(jìn)的算法獲得約簡的屬性子集。在表1中，c1，c2，c3，c4是條件屬性，分別代表食品衛(wèi)生總體合格率、化學(xué)殘留合格率、微生物污染合格率和食品安全關(guān)注度。d是決策屬性，論域U={x1，x2，…，x18}。對于每個條件屬性c1，c2，c3和c4，先分別計(jì)算每個條件屬性的上近似集和下近似集的值。

1)決策屬性d為N的情況。條件屬性為c1時，上近似集和下近似集個數(shù)分別用mN1和nN1表示，且mN1=12，nN1=0;條件屬性為c2時，上近似集和下近似集個數(shù)分別用mN2和nN2表示，且mN2=18，nN2=0;條件屬性為c3時，上近似集和下近似集個數(shù)分別用mN3和nN3表示，且mN3=18，nN3=0;條件屬性為c4時，上近似集和下近似集個數(shù)分別用mN4和nN4表示，且mN4=18，nN4=0。

表1 食品信息表Tab.1 The food information table

2)決策屬性d為P的情況。條件屬性為c1時，上近似集和下近似集個數(shù)分別用mP1和nP1表示，且mP1=18，nP1=6;條件屬性為c2時，上近似集和下近似集個數(shù)分別用mP2和nP2表示，且mP2=18，nP2=0;條件屬性為c3時，上近似集和下近似集個數(shù)分別用mP3和nP3表示，且mP3=18，nP2=0;條件屬性為c4時，上近似集和下近似集個數(shù)分別用mP4和nP4表示，且mP4=18，nP4=0。

再利用上述提出的關(guān)于粗糙度的公式計(jì)算PB(X)值，得到相應(yīng)的值分別是4/5、1、1和1。由此可以得出c1具有最小的PB(X)值，如表2所示。所以應(yīng)該選擇c1作為屬性約簡集，并將其放入約簡集Red中，即:Red←{c1}，c←c-Red，A={c2，c3，c4}，然后根據(jù)U←U-POSRedbxvnxrt，對整個論域 U進(jìn)行計(jì)算，可得到縮減的新論域 U={1，2，4，5，6，8，9，10，11，14，16，17}。

表2 不可分辨集合關(guān)系1Tab.2 The indiscernible relationship 1

將c1與另外3個條件屬性c2，c3和c4分別進(jìn)行組合，對于每組條件屬性，分別計(jì)算每組條件屬性的上近似集和下近似集。

3)決策屬性d為N的情況下。條件屬性為c1c2時，上下近似集個數(shù)分別用mN12和nN12表示，且mN12=11，nN12=0;條件屬性為c1c3時，上下近似集個數(shù)分別用mN13和nN13表示，且mN13=9，nN13=3;條件屬性為c1c4時，上下近似集個數(shù)分別為mN14和nN14表示，且mN14=9，nN14=3。

4)決策屬性d為P的情況。條件屬性為c1c2時，上下近似集個數(shù)分別用mP12和nP12表示，且mP12=12，nP12=1;條件屬性為c1c3時，上下近似集個數(shù)分別用mP13和nP13表示，且mP13=9，nP13=3;條件屬性為c1c4時，上下近似集個數(shù)分別用mP14和nP14表示，且mP14=9，nP14=3。

再采用粗糙度公式計(jì)算PB(X)的值，得到相應(yīng)的值分別是22/23，2/3和2/3(見表3)。由此可知c1，c3和c1，c4的PB(X)是一樣的，且比c1，c2的粗糙度小，所以隨機(jī)選擇c3作為屬性約簡集，并將其放入約簡集Red中，即Red←{c1，c3}，c←c-Red，c={c2，c4}，然后根據(jù)U←U-POSRedjdp5ndv，對新的論域U進(jìn)行計(jì)算，又可得到縮減的新論域 U={4，5，6，10，14，17}。

表3 不可分辨集合關(guān)系2Tab.3 The indiscernible relationship 2

下面分別計(jì)算條件屬性組合c1，c3，c2和c1，c3，c4的上近似集和下近似集。

1)決策屬性d為N的情況。條件屬性為c1c2c3時，上下近似集個數(shù)分別用mN123和nN123表示，且mN123=6，nN123=0;條件屬性為 c1c3c4時，上下近似集個數(shù)分別用 mN134和 nN134表示，且mN134=3，nN134=3。

2)決策屬性d為P的情況。條件屬性為c1c2c3時，上下近似集個數(shù)分別用mP123和nP123表示，且mP123=6，nP123=0;條件屬性為 c1c3c4時，上下近似集個數(shù)分別用 mP134和 nP134表示，且 mP134=3，nP134=3。

再采用粗糙度公式計(jì)算各自的PB(X)的值，得到相應(yīng)的值分別是1和0(見表4)。

表4 不可分辨集合關(guān)系3Tab.4 The indiscernible relationship 3

由此可知c1，c3，c4的粗糙度小于c1，c3，c2的粗糙度，所以選擇c4作為屬性約簡集，并將其放入約簡集Red中，即Red←{c1，c3，c4}，然后根據(jù)U←U-POSRedz5f5z5r，對整個論域U進(jìn)行計(jì)算，可得U=φ，所以此決策表的屬性約簡集是{c1，c3，c4}。

5 實(shí)驗(yàn)結(jié)果與結(jié)論

為說明改進(jìn)算法的約簡效果，采用機(jī)器學(xué)習(xí)通用的UCI(Union Cycliste Internationale)數(shù)據(jù)庫進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果如表5所示。

表5 實(shí)驗(yàn)結(jié)果Tab.5 The experiment results

實(shí)驗(yàn)結(jié)果表明，采用改進(jìn)的屬性約簡算法對樣本的約簡具有較好的效果，尤其是對大樣本的數(shù)據(jù)集，可大量減少樣本對象的數(shù)目，也可快速有效地選擇一個好的屬性約簡子集。

6 結(jié)語

食品安全評價是食品安全管理中的一項(xiàng)重要研究內(nèi)容。筆者針對現(xiàn)有食品安全評價指標(biāo)約簡方法進(jìn)行了分析，提出了基于粗糙度的屬性約簡方法。利用粗糙度作為條件屬性的選擇標(biāo)準(zhǔn)，并用遞歸的處理方法簡化屬性的搜索空間，逐步縮小問題論域，提高了屬性約簡的計(jì)算效率。實(shí)驗(yàn)證明該方法是正確和有效的。

［1］周乃元，潘家榮，汪明.食品安全綜合評估數(shù)學(xué)模型的研究［J］.中國食品衛(wèi)生雜志，2009，21(3):198-202.ZHOU Nai-yuan，PAN Jia-rong，WANG Ming.Study on the Mathematical Model for Food Safety Comprehensive Evaluation［J］.Chinese Journal of Food Hygiene，2009，21(3):198-202.

［2］MERRILL R A.Food Safety Regulation:Reforming the Delaney Clause［J］.Annu Rev Public Health，1997，18(1):313-340.

［3］CASWELL J A.Valuing the Benefits and Costs of Improved Food Safety and Nutrition ［J］.The Australian Journal of Agricultural and Resource Economics，1998，42(4):409-424.

［4］RIPPEL B.International Food Standard Organization Faces Challenges ［J］.Consumers'Research Magazine，2001，84(4):34-35.

［5］PAWLAK Z.Rough Set［J］.International Journal of Computer and Information Science，1982，1(11):341-356.

［6］王國胤.Rough Set理論與知識獲取［M］.西安:西安交通大學(xué)出版社，2001.WANG Guo-yin.Rough Set Theory and Knowledge Acquisition［M］.Xi'an:Xi'an Jiaotong University Press，2001.

［7］張文修，吳偉志.粗糙集理論與方法［M］.北京:科學(xué)出版社，2001.ZHANG Wen-xiu，WU Wei-zhi.Theory and Method of Rough Set［M］.Beijing:Science Press，2001.

［8］ZIARKO W，CERCONE N，HU X.Rule Discovery from Databases with Decision Matrices［C］∥9thInt Symposium on Foundation of Intelligent Systems.Zakopane，Poland:［s.n.］，1996:653-662.

［9］KRYSIKIEWICZ M.Rough Set Approach to Incomplete Information System ［J］.Information Sciences，1998，112(6):39-49.

［10］E Xu，SHAO Liang-shan，YE Bai-qing，et al.Algorithm for Rule Extraction Based on Rough Set［J］.Journal of Harbin Institute of Technology，2007，14(A):34-37.

［11］E Xu，YANG Yu-qiang，REN Yong-chang.A New Method of Attribute Reduction Based on Information Quantity in an Incomplete System［J］.Journal of Software，2012，7(8):1881-1888.