面向食品安全評(píng)價(jià)的屬性約簡(jiǎn)方法研究

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 相關(guān)定理

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

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

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

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

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

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

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

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

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

3 算法描述

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

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

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

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

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

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

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

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

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

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

步驟7 輸出得到的約簡(jiǎn)屬性集Red。

4 實(shí)例

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

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

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

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

2)決策屬性d為P的情況。條件屬性為c1時(shí)，上近似集和下近似集個(gè)數(shù)分別用mP1和nP1表示，且mP1=18，nP1=6;條件屬性為c2時(shí)，上近似集和下近似集個(gè)數(shù)分別用mP2和nP2表示，且mP2=18，nP2=0;條件屬性為c3時(shí)，上近似集和下近似集個(gè)數(shù)分別用mP3和nP3表示，且mP3=18，nP2=0;條件屬性為c4時(shí)，上近似集和下近似集個(gè)數(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作為屬性約簡(jiǎn)集，并將其放入約簡(jiǎn)集Red中，即:Red←{c1}，c←c-Red，A={c2，c3，c4}，然后根據(jù)U←U-POSRedj5i0abt0b，對(duì)整個(gè)論域 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個(gè)條件屬性c2，c3和c4分別進(jìn)行組合，對(duì)于每組條件屬性，分別計(jì)算每組條件屬性的上近似集和下近似集。

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

4)決策屬性d為P的情況。條件屬性為c1c2時(shí)，上下近似集個(gè)數(shù)分別用mP12和nP12表示，且mP12=12，nP12=1;條件屬性為c1c3時(shí)，上下近似集個(gè)數(shù)分別用mP13和nP13表示，且mP13=9，nP13=3;條件屬性為c1c4時(shí)，上下近似集個(gè)數(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作為屬性約簡(jiǎn)集，并將其放入約簡(jiǎn)集Red中，即Red←{c1，c3}，c←c-Red，c={c2，c4}，然后根據(jù)U←U-POSRedj5i0abt0b，對(duì)新的論域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í)，上下近似集個(gè)數(shù)分別用mN123和nN123表示，且mN123=6，nN123=0;條件屬性為 c1c3c4時(shí)，上下近似集個(gè)數(shù)分別用 mN134和 nN134表示，且mN134=3，nN134=3。

2)決策屬性d為P的情況。條件屬性為c1c2c3時(shí)，上下近似集個(gè)數(shù)分別用mP123和nP123表示，且mP123=6，nP123=0;條件屬性為 c1c3c4時(shí)，上下近似集個(gè)數(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作為屬性約簡(jiǎn)集，并將其放入約簡(jiǎn)集Red中，即Red←{c1，c3，c4}，然后根據(jù)U←U-POSRedj5i0abt0b，對(duì)整個(gè)論域U進(jìn)行計(jì)算，可得U=φ，所以此決策表的屬性約簡(jiǎn)集是{c1，c3，c4}。

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

為說(shuō)明改進(jìn)算法的約簡(jiǎn)效果，采用機(jī)器學(xué)習(xí)通用的UCI(Union Cycliste Internationale)數(shù)據(jù)庫(kù)進(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)的屬性約簡(jiǎn)算法對(duì)樣本的約簡(jiǎn)具有較好的效果，尤其是對(duì)大樣本的數(shù)據(jù)集，可大量減少樣本對(duì)象的數(shù)目，也可快速有效地選擇一個(gè)好的屬性約簡(jiǎn)子集。

6 結(jié)語(yǔ)

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

［1］周乃元，潘家榮，汪明.食品安全綜合評(píng)估數(shù)學(xué)模型的研究［J］.中國(guó)食品衛(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］王國(guó)胤.Rough Set理論與知識(shí)獲?。跰］.西安:西安交通大學(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.