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

(1.長(zhǎng)春師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長(zhǎng)春 130032；2.清華大學(xué)信息科學(xué)技術(shù)學(xué)院，北京 100084；3.東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林 長(zhǎng)春 130117)

一種基于粗糙集的味覺信號(hào)識(shí)別方法

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

(1.長(zhǎng)春師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長(zhǎng)春 130032；2.清華大學(xué)信息科學(xué)技術(shù)學(xué)院，北京 100084；3.東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林 長(zhǎng)春 130117)

提出一種基于粗糙集的味覺信號(hào)識(shí)別方法.該算法運(yùn)用粗糙集技術(shù)，在決策規(guī)則生成過程中，充分考慮數(shù)據(jù)集中各屬性的重要度，并動(dòng)態(tài)對(duì)其進(jìn)行更新.由于決策過程中不斷更新屬性重要度，保證了每次將重要度最高的屬性加入決策規(guī)則集，進(jìn)而保證了決策系統(tǒng)的約簡(jiǎn).基于機(jī)器學(xué)習(xí)數(shù)據(jù)集UCI中的2個(gè)味覺信號(hào)數(shù)據(jù)winequality_white和winequality_red，算法采用十折交叉驗(yàn)證技術(shù)，獨(dú)立進(jìn)行10次實(shí)驗(yàn)，并與2個(gè)經(jīng)典算法進(jìn)行了對(duì)比.結(jié)果表明，本文算法的味覺信號(hào)識(shí)別正確率更高、更有效.

粗糙集；味覺信號(hào)；屬性重要度；離散化；區(qū)間劃分

0 引言

近年來，由波蘭數(shù)學(xué)家Z.Pawlak提出的粗糙集理論備受廣大科研工作者和從業(yè)人員的關(guān)注.粗糙集理論是一種處理不完備和不確定性知識(shí)的數(shù)據(jù)分析理論.該理論的優(yōu)點(diǎn)是不需要預(yù)先給定數(shù)據(jù)的某些特征或描述，僅從給定數(shù)據(jù)的各屬性出發(fā)，就可以找到屬性之間相關(guān)性，發(fā)現(xiàn)數(shù)據(jù)規(guī)律，最終生成決策規(guī)則.該理論的假設(shè)前提是研究的論域?qū)ο笈c數(shù)據(jù)或知識(shí)有關(guān).自其問世以來，粗糙理論日趨完善，已經(jīng)廣泛應(yīng)用于粒度計(jì)算、機(jī)器學(xué)習(xí)、決策制定、數(shù)據(jù)挖掘、知識(shí)獲取、知識(shí)發(fā)現(xiàn)等眾多領(lǐng)域[1-4].粗糙理論已經(jīng)成為一種從海量數(shù)據(jù)中挖掘潛在的、有利用價(jià)值信息的有效工具.

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

本文提出一種基于粗糙集的味覺信號(hào)識(shí)別方法.該方法在實(shí)現(xiàn)過程中，充分考慮數(shù)據(jù)集中各屬性的重要度，并隨著數(shù)據(jù)集的更新，不斷更新屬性重要度.因而，最終生成的決策規(guī)則集簡(jiǎn)約，決策能力強(qiáng).基于機(jī)器學(xué)習(xí)數(shù)據(jù)集UCI中的2個(gè)味覺信號(hào)數(shù)據(jù)winequality_white和winequality_red，我們采用十折交叉驗(yàn)證技術(shù)，獨(dú)立進(jìn)行10次實(shí)驗(yàn).并將實(shí)驗(yàn)結(jié)果與文獻(xiàn)[5-6]進(jìn)行對(duì)比，結(jié)果表明我們的實(shí)驗(yàn)效果更好，味覺信號(hào)識(shí)別準(zhǔn)確率更高.

1 相關(guān)概念

1.1 決策表

1.2 離散化描述

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

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

(1)

(2)

(3)

1.3 不可分辨關(guān)系

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

(4)

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

(5)

1.4 屬性重要度

在決策表中，條件屬性與決策屬性之間的關(guān)聯(lián)程度反映了條件屬性的重要性.

從定義可以看出，在一個(gè)決策系統(tǒng)中，Ma的值越大，說明a屬性的決策能力越強(qiáng).

2 基于粗糙集的味覺信號(hào)識(shí)別算法

2.1 算法的主要思想

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

2.2 味覺信號(hào)離散化算法

算法1 味覺信號(hào)離散化算法

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

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

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

1S→S′；

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

3 for each continuous attributeaofC2inS′；

4 Section=Φ；//Section存儲(chǔ)已劃分的屬性區(qū)間；

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

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

7 ifX∩Y≠Φ；

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

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

10 end if

11 end for

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

13 end for

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

15 end for

2.3 區(qū)間合并

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

算法2 區(qū)間合并

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中區(qū)間，按起始端點(diǎn)值從小到大排序；

24endfor

25endfor.

2.4 基于粗糙集的味覺信號(hào)識(shí)別算法

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

算法3 基于粗糙集的味覺信號(hào)識(shí)別算法

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

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

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

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

3repeat；

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

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

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

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

8 刪除S中的相應(yīng)對(duì)象使S和S′ 具有相同的對(duì)象；

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

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

11untilSisnullorallattributeshavebeenaddedintoRule；

12 刪除Rule中重復(fù)行.

3 算例

3.1 實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證算法的可行性和有效性，選取UCI機(jī)器學(xué)習(xí)標(biāo)準(zhǔn)數(shù)據(jù)集中的味覺信號(hào)數(shù)據(jù)winequality_white和winequality_red作為測(cè)試數(shù)據(jù).數(shù)據(jù)集的特征如表1所示.

表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2 實(shí)驗(yàn)測(cè)試

采用十折交叉驗(yàn)證技術(shù)，分別在2個(gè)數(shù)據(jù)集上獨(dú)立運(yùn)行10次.10次運(yùn)行的平均識(shí)別精度如表2所示.其中，第2列和第3列分別為文獻(xiàn)[5]和[6]提出的識(shí)別算法.從實(shí)驗(yàn)結(jié)果看，本文提出的基于粗糙集的味覺信號(hào)識(shí)別算法的識(shí)別精度高于其他2個(gè)算法.尤其是對(duì)于winequality_white數(shù)據(jù)集，本文的識(shí)別精度高于其他2個(gè)算法20%以上.

表2 識(shí)別精度比較 %

4 結(jié)論

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

[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] 楊明.決策表中基于條件信息熵的近似約簡(jiǎn)[J].電子學(xué)報(bào)，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] 張旭，郭晨.基于免疫原理的粗糙集屬性約簡(jiǎn)[J].計(jì)算機(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.

(責(zé)任編輯：石紹慶)

A recognition method of taste signals based on rough set

SUN Ying-juan1，LI Tong2，PU Dong-bing3，JIANG Yan1，F(xiàn)AN 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

國(guó)家留學(xué)基金資助項(xiàng)目(201408220056)；吉林省發(fā)展和改革委員會(huì)工業(yè)技術(shù)研究和發(fā)展計(jì)劃項(xiàng)目(2014Y101)；吉林省教育廳科技計(jì)劃基金資助項(xiàng)目(2014249，2015367，2013250).

孫英娟(1972—)，女，博士，教授，主要從事Agent、人工智能、機(jī)器學(xué)習(xí)研究；通信作者：蒲東兵(1970—)，男，博士，副教授，主要從事模式識(shí)別、智能控制與嵌入式系統(tǒng)及物聯(lián)網(wǎng)等領(lǐng)域研究.

TP 18 [學(xué)科代碼] 520·20

A