一種基于粗糙集的味覺信號識別方法

孫英娟，李 彤，蒲東兵，姜 艷，范木杰

(1.長春師范大學計算機科學與技術學院，吉林 長春 130032；2.清華大學信息科學技術學院，北京 100084；3.東北師范大學計算機科學與信息技術學院，吉林 長春 130117)

一種基于粗糙集的味覺信號識別方法

孫英娟1，李 彤2，蒲東兵3，姜 艷1，范木杰1

(1.長春師范大學計算機科學與技術學院，吉林 長春 130032；2.清華大學信息科學技術學院，北京 100084；3.東北師范大學計算機科學與信息技術學院，吉林 長春 130117)

提出一種基于粗糙集的味覺信號識別方法.該算法運用粗糙集技術，在決策規則生成過程中，充分考慮數據集中各屬性的重要度，并動態對其進行更新.由于決策過程中不斷更新屬性重要度，保證了每次將重要度最高的屬性加入決策規則集，進而保證了決策系統的約簡.基于機器學習數據集UCI中的2個味覺信號數據winequality_white和winequality_red，算法采用十折交叉驗證技術，獨立進行10次實驗，并與2個經典算法進行了對比.結果表明，本文算法的味覺信號識別正確率更高、更有效.

粗糙集；味覺信號；屬性重要度；離散化；區間劃分

0 引言

近年來，由波蘭數學家Z.Pawlak提出的粗糙集理論備受廣大科研工作者和從業人員的關注.粗糙集理論是一種處理不完備和不確定性知識的數據分析理論.該理論的優點是不需要預先給定數據的某些特征或描述，僅從給定數據的各屬性出發，就可以找到屬性之間相關性，發現數據規律，最終生成決策規則.該理論的假設前提是研究的論域對象與數據或知識有關.自其問世以來，粗糙理論日趨完善，已經廣泛應用于粒度計算、機器學習、決策制定、數據挖掘、知識獲取、知識發現等眾多領域[1-4].粗糙理論已經成為一種從海量數據中挖掘潛在的、有利用價值信息的有效工具.

在計算機應用領域，特別是對機器人的研究，計算機視覺、聽覺、觸覺和力覺的研究都取得了相當多的成果，有的已達到實用水準.然而計算機味覺和嗅覺的研究進展較為緩慢，其中研制的難度及實現的復雜性是其原因之一.酸、甜、苦、辣、咸被稱為基本味，人類是靠舌頭這一器官來感知基本味和復合味的.復合味不同于復合色，一些味道間的復合并無意義，人類能夠辨識的復合味很有限，有些味道即使能夠辨識，也難于清楚地表述，只能用一些模糊詞匯來評價.因而計算機味覺的實現，除需要研制高靈敏度的味覺傳感器之外，還需要將機器學習、模式識別等方法引入，并解決味覺知識的獲取、復合味道的表示等問題.

本文提出一種基于粗糙集的味覺信號識別方法.該方法在實現過程中，充分考慮數據集中各屬性的重要度，并隨著數據集的更新，不斷更新屬性重要度.因而，最終生成的決策規則集簡約，決策能力強.基于機器學習數據集UCI中的2個味覺信號數據winequality_white和winequality_red，我們采用十折交叉驗證技術，獨立進行10次實驗.并將實驗結果與文獻[5-6]進行對比，結果表明我們的實驗效果更好，味覺信號識別準確率更高.

1 相關概念

1.1 決策表

1.2 離散化描述

粗糙集只能處理離散化的數據.因此，如果決策表中的屬性(包括條件屬性和決策屬性)值為連續數據，則在對數據進行處理前必須實施預處理，將其離散化.

在值域Va=[la，ra]上，la，ra和Va為：

(1)

(2)

(3)

1.3 不可分辨關系

不可分辨關系概念是粗糙集理論的基石，它揭示出論域知識的顆粒狀結構.不可分辨關系用來定義給定屬性之間的關系.在給定的知識表示系統中S=(U，A，{Va}，f)，對于任意的屬性集R?A，不可分辨關系定義為

(4)

其中a(x) 表示對象x的屬性值a.如果(x，y)∈IND(R)，我們說x和y關于關系R不可分辨.IND(R)是論域U上的一個等價關系.IND(R)中的每一個元素即構成一個等價類.而U/IND(R)則是由等價關系IND(R)產生的對論域U的劃分.IND(R)將U劃分為X1，X2，…，Xt，共t個等價類.對于任意的x∈U，[x]R表示IND(R)的一個包含對象x的等價類為

(5)

1.4 屬性重要度

在決策表中，條件屬性與決策屬性之間的關聯程度反映了條件屬性的重要性.

從定義可以看出，在一個決策系統中，Ma的值越大，說明a屬性的決策能力越強.

2 基于粗糙集的味覺信號識別算法

2.1 算法的主要思想

在一個決策表中，決策規則與重要度高的條件屬性的相關性更高.基于粗糙集的味覺信號識別方法在規則生成過程中充分考慮已經加入決策規則的條件屬性，每次將剩余條件屬性中擁有最高重要度的條件屬性加入決策規則表.由于味覺信號數據是連續數據，需要首先對屬性進行離散化，然后生成決策規則.因此，離散化算法對于分類質量至關重要.本文的離散化算法在對條件屬性離散化過程中，首先考慮已經離散化的屬性；其次，離散化要基于分類目標；再次，每添加一個決策屬性后，由于未離散化的屬性集已發生變化，算法重新離散化該屬性集，并重新計算屬性重要度.

2.2 味覺信號離散化算法

算法1 味覺信號離散化算法

輸入：決策表S=(U，C∪D，V，f)；

決策規則表 Rule=(U1，C1∪D1，V1，f1)；

輸出：決策表S′=(U′，C′∪D′，V′，f′).

1S→S′；

2C-C1→C2；//C1?C為S中已經完成離散化的條件屬性，C2為待離散化的條件屬性；

3 for each continuous attributeaofC2inS′；

4 Section=Φ；//Section存儲已劃分的屬性區間；

5 for eachX∈U′/IND(C2)；

6 for eachY∈U′/IND(D′)；

7 ifX∩Y≠Φ；

8 找到X∩Y中最大屬性值t1和最小的屬性值t0；

9 生成區間t=[t0*0.99，t1*1.01)；

10 end if

11 end for

12 將所有的區間t合并入Section；//算法2；

13 end for

14 整理Section并且生成屬性a的離散屬性值；//2.3 區間合并；

15 end for

2.3 區間合并

當將所有的2.2節中的t區間并入到Section時，應該產生盡可能少的區間量.這樣最終離散系統擁有最少的屬性值，從而簡化決策規則.首先將所有t區間按起始端點值由小到大排序，然后再依次將其并入Section.算法的主要思想是產生盡可能多的純凈區間(區間中所有數據具有相同的決策屬性值)，盡可能少的混合區間(區間中的數據具有不同的決策屬性值).

算法2 區間合并

Input：Tj// 算法1中排序后的t集合；

Output：Section；

1 for eachtj=[tjk，tj(k+1))∈Tj//按j值從小到大選取；

3 select case do //初始值flag(Sec)=0；

5 if flag(Sec)=0；

6 flag(Sec)=1；

7 else

9 end if

11 if flag(Sec)=0；

12 flag(Sec)=1；

13 Secp+1=tjk；

14 else

15 Secp+2=tjk；

16 end if

17 end case

21endif

22endfor

23 將Section中區間，按起始端點值從小到大排序；

24endfor

25endfor.

2.4 基于粗糙集的味覺信號識別算法

伴隨著決策規則產生決策表中的數據在不斷地減少.而伴隨著數據庫的變化，屬性的重要度也會隨之改變.基于以上思想，我們提出一種基于粗糙集的味覺信號識別算法.算法充分考慮在規則產生過程中條件屬性重要度的改變.每將一個條件屬性加入規則后，重新計算重要度，再將重要度高的屬性加入規則集，直到數據庫為空或者所有的條件屬性都已加入決策規則.

算法3 基于粗糙集的味覺信號識別算法

Input：決策表S=(U，C∪D，V，f)；

Output：決策規則集Rule=(U′，C′，D′，V′，f′)；

1 S→S0；Φ→Rule；Φ→S′；

2 將S中的所有屬性離散化后，獲得離散的決策表Dtable，S不變；//算法 1；

3repeat；

4 計算Dtable中各屬性重要度； //定義1；

5 選擇Dtable中屬性重要度最高的屬性a；

6Dtable(：，a)→S′(：，a)；

7 刪除S′中所有一致性數據并將其賦值給Rule；

8 刪除S中的相應對象使S和S′ 具有相同的對象；

9 S′(：，a)→S(：，a)；

10 將S中的所有屬性離散化后，獲得離散的決策表Dtable，S不變；//算法 1；

11untilSisnullorallattributeshavebeenaddedintoRule；

12 刪除Rule中重復行.

3 算例

3.1 實驗數據

為了驗證算法的可行性和有效性，選取UCI機器學習標準數據集中的味覺信號數據winequality_white和winequality_red作為測試數據.數據集的特征如表1所示.

表1 實驗數據集

3.2 實驗測試

采用十折交叉驗證技術，分別在2個數據集上獨立運行10次.10次運行的平均識別精度如表2所示.其中，第2列和第3列分別為文獻[5]和[6]提出的識別算法.從實驗結果看，本文提出的基于粗糙集的味覺信號識別算法的識別精度高于其他2個算法.尤其是對于winequality_white數據集，本文的識別精度高于其他2個算法20%以上.

表2 識別精度比較 %

4 結論

本文提出一種基于粗糙集的味覺信號識別方法.該方法在決策規則生成過程中，充分考慮數據集中各屬性的重要度，依次將重要度高的屬性加入決策規則集.由于規則生成過程中，數據集會不斷變化，從而各屬性的重要度也會有所不同.基于此思想，算法在規則生成過程中，不斷重新計算重要度，進而保證了決策規則的有效性.從實驗結果看，本文算法在winequality_white和winequality_red 2個味覺信號數據集的識別效果良好.與文獻[5]和[6]的算法比較，在識別精度上有很大提高.

[1] PAWLAK Z.Rough sets [J].International Journal of Information and Computer Science，1982，11(5)：341-356.

[2] SUN BINGZHEN，MA WEIMIN，ZHAO HAIYAN.Decision-theoretic rough fuzzy set model and application[J].Information Sciences，2014，283(5)：180-196.

[3] 楊明.決策表中基于條件信息熵的近似約簡[J].電子學報，2007，35(11)：2156-2160.

[4] ZHANG JUNBO，LI TIANRUI，CHEN HONGMEI.Composite rough sets for dynamic data mining [J].Information Sciences，2014，257(2)：81-100.

[5] RODRIGO C B，MRCIO P B，ANDRé C P L F D C，et al.A hyper-heuristic evolutionary algorithm for automatically designing decision-tree algorithms[C]//GECCO12 Proceedings of the 14th annual conference on Genetic and evolutionary computation，New York：ACM，2012：1237-1244.

[7] XIUYI JIA，ZHENMIN TANG，WENHE LIAO，et al.On an optimization representation of decision-theoretic rough set model[J].International Journal of Approximate Reasoning，2014，55(1)：156-166.

[8] 張旭，郭晨.基于免疫原理的粗糙集屬性約簡[J].計算機工程，2007，33(23)：51-53.

[9] SHI ZHICAI，XIA YONGXIANG，WU FEI，et al.The discretization algorithm for rough data and its application to intrusion detection[J].Journal of Networks，2014，9(6)：265-269.

[10] SUN YINGJUAN，PU DONGBING，SUN YINGHUI，et al.Rough-set classifier based on discretization for breast cancer diagnosis[J].Journal of Computational Information Systems，2014，10(22)：9469-9478.

(責任編輯：石紹慶)

A recognition method of taste signals based on rough set

SUN Ying-juan1，LI Tong2，PU Dong-bing3，JIANG Yan1，FAN Mu-jie1

(1.College of Computer Science and Technology，Changchun Normal University，Changchun 130032，China；2.College of Information Science and Technology，Tsinghua University，Beijing 100084，China；3.College of Computer Science and Information Technology，Northeast Normal University，Changchun 130117，China)

This is a recognition method of taste signals based on rough set.For the realization of computer taste，the identification of taste signals is also very important except developing taste sensor with high sensitivity.The algorithm of this paper bases on rough set technology.It fully considers attribute significances and updates them dynamically during the process of decision making.Because of constantly updating attribute significances，it ensures to add the attribute with highest significance to the rule set.So，the decision system is simple.Based on two machine learning data set UCI，winequality-white and winequality-red，the proposed algorithm adopts ten-fold cross validation technology to run ten times independently.And comparing with the two other classical algorithms，results show that the proposed algorithm is better and more effective than them on taste signal recognition rate.

rough set；recognition of taste signals；attribute significance；discretization；region division

1000-1832(2016)04-0052-05

10.16163/j.cnki.22-1123/n.2016.04.012

2016-07-17

國家留學基金資助項目(201408220056)；吉林省發展和改革委員會工業技術研究和發展計劃項目(2014Y101)；吉林省教育廳科技計劃基金資助項目(2014249，2015367，2013250).

孫英娟(1972—)，女，博士，教授，主要從事Agent、人工智能、機器學習研究；通信作者：蒲東兵(1970—)，男，博士，副教授，主要從事模式識別、智能控制與嵌入式系統及物聯網等領域研究.

TP 18 [學科代碼] 520·20

A