基于粗糙集的增強(qiáng)學(xué)習(xí)型分類器

鄭 周，嵇春梅，趙 斌，劉解放

1.鹽城工學(xué)院 信息工程學(xué)院, 江蘇 鹽城 224051； 2.鹽城工業(yè)職業(yè)技術(shù)學(xué)院 機(jī)電工程學(xué)院，江蘇 鹽城 224051； 3.北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,北京 100022

基于粗糙集的增強(qiáng)學(xué)習(xí)型分類器

鄭 周1，嵇春梅2，趙 斌3，劉解放1

1.鹽城工學(xué)院 信息工程學(xué)院, 江蘇 鹽城 224051； 2.鹽城工業(yè)職業(yè)技術(shù)學(xué)院 機(jī)電工程學(xué)院，江蘇 鹽城 224051； 3.北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,北京 100022

為了提高分類的精確度，提出一種基于粗糙集理論的增強(qiáng)學(xué)習(xí)型分類器。采用分割算法對(duì)訓(xùn)練數(shù)據(jù)集中連續(xù)的屬性進(jìn)行離散處理；利用粗糙集理論獲取約簡(jiǎn)集，從中選擇一個(gè)能提供最高分類精確度的約簡(jiǎn)。對(duì)于不同的測(cè)試數(shù)據(jù)，由于離散屬性值的變化，相同的約簡(jiǎn)可能達(dá)不到最高的分類精確度。為克服此問(wèn)題，改進(jìn)了Q學(xué)習(xí)算法，使其全面系統(tǒng)地解決離散化和特征選擇問(wèn)題，因此不同的屬性可以學(xué)習(xí)到最佳的分割值，使相應(yīng)的約簡(jiǎn)產(chǎn)生最大分類精確度。實(shí)驗(yàn)結(jié)果表明，該分類器能達(dá)到98%的精確度，與其它分類器相比，表現(xiàn)出較好的性能。

粗糙集；增強(qiáng)學(xué)習(xí)；屬性約簡(jiǎn)；離散化；特征選擇

分類問(wèn)題是數(shù)據(jù)挖掘領(lǐng)域中應(yīng)用和研究最為廣泛的技術(shù)之一。如何更精確、高效地分類一直是廣大科研人員的目標(biāo)[1]。目前監(jiān)督和無(wú)監(jiān)督學(xué)習(xí)[2-4]作為分類技術(shù)已得到廣泛的應(yīng)用,支持向量機(jī)、決策樹(shù)、K-近鄰、人工神經(jīng)網(wǎng)絡(luò)和聚類技術(shù)等機(jī)器學(xué)習(xí)方法被應(yīng)用于分類器。有監(jiān)督學(xué)習(xí)，標(biāo)記訓(xùn)練數(shù)據(jù)十分耗時(shí)；而無(wú)監(jiān)督學(xué)習(xí)，由于沒(méi)有足夠的先驗(yàn)領(lǐng)域知識(shí)，恰當(dāng)?shù)臄?shù)據(jù)劃分變得困難。而且沒(méi)有技術(shù)能夠很好地適應(yīng)實(shí)時(shí)動(dòng)態(tài)數(shù)據(jù)分類。

增強(qiáng)學(xué)習(xí)常用于序列預(yù)測(cè)和構(gòu)建分類器。文獻(xiàn)[5]提到為了應(yīng)用增強(qiáng)學(xué)習(xí)，必須有充足的樣本數(shù)據(jù)用于學(xué)習(xí)環(huán)境，但是，大樣本空間使學(xué)習(xí)過(guò)程變慢，導(dǎo)致該方法不適合實(shí)時(shí)應(yīng)用；Q學(xué)習(xí)是一種增強(qiáng)學(xué)習(xí)技術(shù)[6-8]，在一個(gè)特定狀態(tài)且未知環(huán)境中，利用經(jīng)歷的動(dòng)作序列執(zhí)行最優(yōu)動(dòng)作。文獻(xiàn)[9]提出分布式增強(qiáng)學(xué)習(xí)，它以分層的方式工作，每層通過(guò)中心代理向更高層發(fā)送數(shù)據(jù)，不過(guò)計(jì)算量大，且不具有健壯性。

本文提出一種全面的學(xué)習(xí)方法，該方法集成了粗糙集理論和增強(qiáng)學(xué)習(xí)(Q學(xué)習(xí))算法，具有較高的分類精確度。粗糙集理論僅能用于離散數(shù)據(jù)，需要分割連續(xù)條件屬性,它的不可辨別性概念用來(lái)選擇最重要的屬性集——約簡(jiǎn)，以代表原始數(shù)據(jù)集。對(duì)于不同的測(cè)試數(shù)據(jù)，采用相同的分割值可能產(chǎn)生不同的約簡(jiǎn)，因此要選擇提供最高分類精確度的約簡(jiǎn)來(lái)構(gòu)建分類器。本分類器中，我們改進(jìn)了Q學(xué)習(xí)算法，使其為每個(gè)條件屬性學(xué)習(xí)不同的分割值；通過(guò)評(píng)估相應(yīng)約簡(jiǎn)和精確度形成回報(bào)矩陣。改進(jìn)的Q矩陣為每個(gè)屬性選擇最佳分割值，以達(dá)到最高的分類精確度。

1 粗糙集理論的屬性約簡(jiǎn)

粗糙集理論(RST)是一種處理模糊、不精確分類問(wèn)題的數(shù)學(xué)工具，它提供了一套比較成熟的方法，能夠在樣本數(shù)據(jù)集中發(fā)現(xiàn)數(shù)據(jù)屬性間的關(guān)系,其中知識(shí)約簡(jiǎn)是RST的核心問(wèn)題之一[10]。

1.1 約簡(jiǎn)

信息系統(tǒng)是一張二維數(shù)據(jù)表。它可以形式化為一個(gè)四元組IS=(U,A,V,f),U是一個(gè)非空對(duì)象集,即論域，A是一個(gè)非空屬性集，A=C∪D且C∩D=φ,C為條件屬性，D為決策屬性，Va表示a∈A的值域，f:U×A→V是一個(gè)信息函數(shù)。條件屬性集表示對(duì)象的特征，而決策屬性集表示對(duì)象的類別標(biāo)簽。為了從表中消除冗余的和不重要的屬性，RST中約簡(jiǎn)概念應(yīng)運(yùn)而生。約簡(jiǎn)是一個(gè)最小的條件屬性子集，它足以表示整個(gè)數(shù)據(jù)表。約簡(jiǎn)不是唯一的，因此發(fā)現(xiàn)所有的約簡(jiǎn)是NP問(wèn)題。為了尋找近似約簡(jiǎn)，數(shù)據(jù)挖掘領(lǐng)域開(kāi)發(fā)了很多新的算法[11-14]。Skrowron[15]引入了差別矩陣的概念，基于差別矩陣的約簡(jiǎn)由差別函數(shù)產(chǎn)生。差別函數(shù)利用吸收和擴(kuò)展律刪除冗余屬性，生成約簡(jiǎn)。

1.2 差別矩陣

差別矩陣定義：給定一個(gè)決策系統(tǒng)DS=(U,C,D)，U是論域，C為條件屬性，D為決策屬性。全集U={x1,x2,…,xn}，而差別矩陣M=(mij)是一個(gè)|U|×|U|的矩陣，其中元素mij是對(duì)象對(duì)xi和xj通過(guò)公式(1)得到。

(1)

mij為差別矩陣元素，也是條件屬性子集，它是第i個(gè)個(gè)體xi與第j個(gè)個(gè)體xj屬性值不相等的那些屬性構(gòu)成的集合，或說(shuō)mij是所有能區(qū)分開(kāi)個(gè)體xi和xj的屬性構(gòu)成的集合。因此如果mij≠φ，對(duì)象xi和xj能被區(qū)分。當(dāng)i=j時(shí)，顯然mii=φ，因?yàn)椴淮嬖诎褬颖緓i與自身區(qū)分開(kāi)的屬性。一個(gè)差別矩陣M是對(duì)稱的，即mij=mji，mii≠φ。因此，只考慮下三角或上三角矩陣。

表1為信息系統(tǒng)，它包括10個(gè)對(duì)象，5個(gè)條件屬性a、b、c、d、e和1個(gè)決策屬性f。 表2為該信息系統(tǒng)的差別矩陣。f(s)為差別函數(shù)，它是由表2中所有非空元素構(gòu)成的合取范式。

通過(guò)移除等價(jià)項(xiàng)，差別函數(shù)可表示如下：

為生成約簡(jiǎn)，在f(s)上首先應(yīng)用吸收律。該吸收律規(guī)定：如果一項(xiàng)是另一個(gè)項(xiàng)的子集，并且兩項(xiàng)采用“合取”聯(lián)結(jié)詞相連，則保留具有變量個(gè)數(shù)最少的項(xiàng)。通過(guò)運(yùn)用吸收律，差別函數(shù)可化簡(jiǎn)為f(s)=(e)∧(a∨c)∧(a∨b∨d)。

表1 信息系統(tǒng)

其次應(yīng)用擴(kuò)展律，它用來(lái)保留那些更頻繁地出現(xiàn)在析取項(xiàng)中的條件屬性。在具有最高頻率的屬性上應(yīng)用“合取”，因?yàn)樗鼈冊(cè)诜诸愔邪l(fā)揮著重要的作用；在出現(xiàn)頻率較少的條件屬性上應(yīng)用“析取”，因?yàn)榭紤]所有的條件屬性不但不能提高分類精度，反而增加計(jì)算復(fù)雜度；最后，在每個(gè)由“析取”連接的項(xiàng)(析取式)上應(yīng)用“合取”，所以它們?nèi)魏我粋€(gè)都可能屬于不同的約簡(jiǎn)。

* 擴(kuò)展律算法描述：

(1)尋找出現(xiàn)最頻繁的屬性(至少兩次)；

(2)在這樣屬性上運(yùn)用“合取”，余下的運(yùn)用“析取”運(yùn)算；

(3)運(yùn)用“合取”連接所有析取式，如果一個(gè)項(xiàng)包含(1)中的屬性，則消除；

(4)使用“合取”連接由(2)和(3)得到的項(xiàng)。

舉例,假如出現(xiàn)最頻繁的屬性是a，基于擴(kuò)展律可得：

(1)：a(2)：a∧e

(3)：c∧(b∨d)

(4)：(a∧e)∧(c∧(b∨d))

所以：

因此，約簡(jiǎn)是{a,e,c,b}和{a,e,c,d}

2 改進(jìn)的Q學(xué)習(xí)算法

本文改進(jìn)了Q學(xué)習(xí)算法，并且在NSL-KDD數(shù)據(jù)集上進(jìn)行了分類測(cè)試。

表2 信息系統(tǒng)(表1)的差異矩陣

2.1Q學(xué)習(xí)算法

Q學(xué)習(xí)算法[5]是一種廣泛使用的增強(qiáng)學(xué)習(xí)算法?；貓?bào)矩陣(R)是Q矩陣的組成部分，它把狀態(tài)映射為行，動(dòng)作映射為列。學(xué)習(xí)算法在一個(gè)特定的狀態(tài)下執(zhí)行最可能的動(dòng)作，來(lái)達(dá)到代理指定目標(biāo)狀態(tài)。算法的訓(xùn)練是通過(guò)“試錯(cuò)法”到達(dá)目標(biāo)狀態(tài)來(lái)學(xué)習(xí)環(huán)境。

增強(qiáng)學(xué)習(xí)算法有3個(gè)主要組成部分，即環(huán)境、增強(qiáng)函數(shù)和價(jià)值函數(shù)。根據(jù)環(huán)境中狀態(tài)(s)和動(dòng)作(a)，估計(jì)狀態(tài)-動(dòng)作對(duì)(s,a)的值來(lái)構(gòu)建回報(bào)矩陣。通過(guò)公式(2)描述的狀態(tài)-動(dòng)作對(duì)(si,a)的Q值，回報(bào)矩陣來(lái)構(gòu)造Q矩陣。Q值決定代理在特定的狀態(tài)si可能采取的動(dòng)作，以便下一個(gè)狀態(tài)si+1接近目標(biāo)狀態(tài)。回報(bào)矩陣形成以后，Q矩陣是通過(guò)使用一個(gè)學(xué)習(xí)參數(shù)γ，經(jīng)過(guò)有限次的迭代而獲得。通過(guò)考慮在一個(gè)特定的狀態(tài)下的所有動(dòng)作，計(jì)算得到Q的最大值。

(2)

2.2 回報(bào)矩陣的形成

在改進(jìn)的Q學(xué)習(xí)算法中，回報(bào)矩陣分2個(gè)階段形成：初始化回報(bào)矩陣和最終回報(bào)矩陣。首先在數(shù)據(jù)集的所有屬性上應(yīng)用一個(gè)特定的分割，把連續(xù)屬性集離散化，并使用基于RST的差別矩陣概念，生成約簡(jiǎn)。分類規(guī)則來(lái)自每個(gè)約簡(jiǎn)，通過(guò)設(shè)計(jì)一個(gè)基于規(guī)則的分類器來(lái)計(jì)算相應(yīng)約簡(jiǎn)的精確度。選擇提供最高精確度的約簡(jiǎn)，在特定的狀態(tài)或分割中表示為最佳動(dòng)作。運(yùn)用不同的分割，約簡(jiǎn)相繼生成，并估計(jì)其精確度，直到兩次連續(xù)的分割提供相同的精確度或單調(diào)遞減。精確度是一個(gè)閾值，由它確定rij的值。

(3)

redi是分割i提供的最高精確度，初始回報(bào)矩陣表示如下：

從R中可以發(fā)現(xiàn)算法采取的動(dòng)作僅基于最重要的屬性(約簡(jiǎn))，而其它的屬性不起作用，在矩陣R中，用NR表示。

最終的回報(bào)矩陣RF是通過(guò)刪除R中所有行都是NR值的列，此時(shí)，RF矩陣的維度才能確定，它少于R。如果一個(gè)特定的屬性(列)不屬于約簡(jiǎn)，而RF把它作為自身一個(gè)特定的分割(行)成員，則設(shè)其值為-1，表明不重要的屬性。

* 初始回報(bào)矩陣R的算法：

* 最終回報(bào)矩陣RF算法：

輸入：初始回報(bào)矩陣R(n×m)

輸出：最終回報(bào)矩陣RF(n×p),p≤m

Step1：對(duì)于每一個(gè)m，確定所有的rij是否為NR。

a=0;

forj=1 tom

Counter=0;

Fori=1 ton

ifrij=NR

Counter++

End for

if counter==行數(shù)

Deleted-columna++=j;/*a是一個(gè)刪除列的索引，用來(lái)記錄應(yīng)刪除的列*/

End for

Step2：刪除c∈Deleted-column[] //c是應(yīng)該刪除的列，其所有行都為NR。

p=0;

Forj=1 tom

flag=0;

Fork=1 toa

Ifj==Deleted-column[k]

Set flag=1;

End for

if flag==0

Begin fori=1 ton

rip=rij;

End for

p+=1;

End for

Step3：用-1替換R矩陣中其余NR元素。

Fori=1ton

Forj=1top

Ifrip==NR;

rip=-1;

Endfor

Endfor

2.3 改進(jìn)的Q學(xué)習(xí)算法

從最終回報(bào)矩陣形成了矩陣Q，最后1行的所有元素(不包括最后1行都是由零組成)，表示最大分類精度將達(dá)到的目標(biāo)狀態(tài)。改進(jìn)學(xué)習(xí)過(guò)程包含若干個(gè)步驟，通過(guò)步驟6的迭代，直到改進(jìn)Q矩陣的所有元素都大于0，表示精確度可接受。

*Q矩陣算法：

輸入：最終的回報(bào)矩陣RF(n×p)

Step1：初始化Q矩陣QM(n×p)，及其所有元素為零。

Step2：給QM的第n個(gè)狀態(tài)(目標(biāo)狀態(tài))賦值。

For(j=1top)

QM[n,j]=RF[n,j];

End

Step3：從RF(n×p)導(dǎo)出稀疏矩陣SM(r×3)，用來(lái)記錄RF中rij的i(i=1,2,…,n)，j(j=1,2,…,p)和值0/1。

Step4：記錄無(wú)動(dòng)作的i(i=1,2,…,n)。

no-action-size=0;

Fori=1 ton

Flag2=0;

Forj=1 top

if RF[i,j]≥0

Flag2=1;

End for

if Flag2=0

no-action[no-action-size++]=i;

End for

Step5：初始化Flag[]，并賦值為零。

Step6：?jiǎn)?dòng)運(yùn)行事件。

Do

Count=0;

/*從i=0(開(kāi)始狀態(tài))開(kāi)始運(yùn)行，直到i=n(目標(biāo)狀態(tài))結(jié)束*/

While SM[count,0]!=(n-1)

State=SM[count,0];

If (SM[count,2]==0)and(Flag[state]==0)

action-nmber=SM[count,1];

Calculate MAX[QM(next-state,all-actions)]

Update the Q矩陣

QM[state,action-nubmer]=RF[state,action-number]+(γ*Max);

Update 稀疏矩陣SM(r×3)

重新初始化Flag[]數(shù)組，賦值為零。

/*檢查QM[][]的所有值是否已更新*/

Flag-end=0;

Fork=1 toa

if SM[k,2]==0

Flag-end=1;

End for

Loop until Flag-end==1

Step7：輸出Q矩陣Q(n×p)。

初始回報(bào)矩陣R、最終回報(bào)矩陣RF和Q矩陣如下所示。表3給出了數(shù)據(jù)集信息系統(tǒng)的部分對(duì)象。

表3 NSL-KDD數(shù)據(jù)集信息系統(tǒng)的部分對(duì)象

應(yīng)用改進(jìn)的Q學(xué)習(xí)算法后，Q矩陣被更新形成最終的Q矩陣(Qfinal)其中對(duì)于每個(gè)j，標(biāo)出最高的qij值，表示對(duì)于屬性j，i是最佳的分割值。在Qfinal中，1.64是第1列中最大值，對(duì)應(yīng)于屬性CA2；它出現(xiàn)在第2行，對(duì)應(yīng)于分割值5。因此，當(dāng)對(duì)表3進(jìn)行分類時(shí)，達(dá)到最高的精度應(yīng)是在屬性CA2采用分割值為5。

初始回報(bào)矩陣R：

CA2CA3CA4

初始Q矩陣：

CA2CA3CA4

最終Q矩陣Qfinal：

CA2CA3CA4

3 合成數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

通過(guò)評(píng)估皮爾遜相關(guān)系數(shù)對(duì)數(shù)據(jù)集間的相關(guān)性進(jìn)行研究，定義如下：

其中x和y是兩個(gè)變量，n表示樣品的，r的值域?yàn)閇-1,1]。如果x和y有很強(qiáng)的線性正相關(guān)，r接近1；如果x和y有很強(qiáng)的線性負(fù)相關(guān)，r接近-1；如果它們不存在相關(guān)性，r為0。

我們?cè)诖诉x取了合成數(shù)據(jù)集作為測(cè)試數(shù)據(jù)，其中包括緊密相關(guān)的、中度相關(guān)和不相關(guān)的使用本文設(shè)計(jì)的分類器對(duì)其進(jìn)行分類，并計(jì)算其精確度。數(shù)據(jù)集的相關(guān)性和精確度在表4中列出。從中可以發(fā)現(xiàn)當(dāng)相關(guān)性趨于0時(shí)，精確度下降，因此，我們的分類器能夠分類不同數(shù)據(jù)集。

表4 不同數(shù)據(jù)集的相關(guān)性和精確度

4 性能驗(yàn)證

本文使用NSL-KDD數(shù)據(jù)集[16]用于學(xué)習(xí)環(huán)境，它包含42個(gè)屬性，其中41個(gè)是條件屬性，1個(gè)是決策屬性。41個(gè)條件屬性中，34個(gè)是連續(xù)的，7個(gè)是離散的。將最初相同的分割值應(yīng)用到所有連續(xù)條件屬性上，在每個(gè)情況下生成約簡(jiǎn)。例如，考慮200個(gè)對(duì)象作為訓(xùn)練數(shù)據(jù)集，應(yīng)用分割值2，生成4個(gè)約簡(jiǎn)。采取100個(gè)對(duì)象作為測(cè)試數(shù)來(lái)計(jì)算約簡(jiǎn)的精確度，如表5所示。由于所有約簡(jiǎn)都顯示相同的分類精確度，所以可采用約簡(jiǎn)R0構(gòu)造初始回報(bào)矩陣。

表5 約簡(jiǎn)與精確度

圖1 分割值與精確度Fig.1 Partition value and accuracy

重復(fù)同樣的步驟對(duì)所有連續(xù)屬性施加分割3～9，選擇最高分類精確度的約簡(jiǎn)構(gòu)造初始回報(bào)矩陣。回報(bào)矩陣分割或行的個(gè)數(shù)是由分割產(chǎn)生過(guò)程的終止條件確定。圖1分割值與精確度顯示了對(duì)應(yīng)分割9，10，11的精確度單調(diào)遞減，所以初始回報(bào)矩陣的行數(shù)確定為8，定義目標(biāo)狀態(tài)相應(yīng)的分割為9。例如，應(yīng)用分割3，選擇約簡(jiǎn)R2={2,3,9,21,22,29,35}，它可達(dá)到最高分類精度96.4%。

最后，使用屬性4,5,9,22,28,29,31,32,33,34,35形成最終的回報(bào)矩陣的列，如表6所示。因此，最終的回報(bào)矩陣有8行11列。通過(guò)應(yīng)用改進(jìn)Q學(xué)習(xí)算法，得到最終Q矩陣，如表7所示。最終Q矩陣中，不同屬性的分割來(lái)自其對(duì)應(yīng)的最高精確度，例如，屬性4對(duì)應(yīng)分割9，屬性5對(duì)應(yīng)分割6等被選擇為最佳分割值，并應(yīng)用在新的數(shù)據(jù)集上，可提供分類精確度高達(dá)98.2%。

通過(guò)工具WEKA運(yùn)用10倍交叉驗(yàn)證模型比較本文設(shè)計(jì)的分類器和其它分類器的分類精確度，結(jié)果如表8所示。

表6 最終回報(bào)矩陣

表7 最終Q矩陣(最佳分割值生成)

表8 分類精確度

此外，為了評(píng)估分類器的魯棒性，我們?cè)贜SL-KDD數(shù)據(jù)集上選定了一些未知攻擊，進(jìn)行同樣的實(shí)驗(yàn),表9給出了實(shí)驗(yàn)結(jié)果。從表9中可以得出，分類器具有較高的檢測(cè)率、低的誤報(bào)率和低的漏報(bào)率。F1測(cè)度為0.97，這證實(shí)了該分類器檢測(cè)精度高，并證明其良好的性能。

總之，該分類器能夠很好的檢測(cè)到新型的攻擊，具有非常高的F1測(cè)度(0.97)和低誤報(bào)率。

表9 性能情況

5 結(jié)語(yǔ)

本文采用粗糙集理論和增強(qiáng)學(xué)習(xí)技術(shù)，通過(guò)改進(jìn)Q學(xué)習(xí)算法實(shí)現(xiàn)了一種新的分類器，它能更好地處理離散化、特征選擇和精確度計(jì)算，從而降低計(jì)算成本，實(shí)現(xiàn)了更全面地構(gòu)建分類器。我們發(fā)現(xiàn)對(duì)于連續(xù)屬性的離散化，如果所有屬性采用相同的分割，即使連續(xù)的兩個(gè)分割值，分類精確度差別很大，但不同屬性的不同分割的結(jié)合卻產(chǎn)生了最好的分類精確度。采用不同的相關(guān)數(shù)據(jù)集測(cè)試了我們的方法，表明了該分類器的有效性。實(shí)驗(yàn)結(jié)果表明，該分類方法實(shí)現(xiàn)了較高的分類精確度達(dá)80%；具有較高的召回率和F1測(cè)度。

本文進(jìn)一步的工作是繼續(xù)優(yōu)化算法，將其應(yīng)用于大數(shù)據(jù)集并提高處理大數(shù)據(jù)的效率。對(duì)算法進(jìn)行個(gè)性化持續(xù)改進(jìn)。

[1] 姚亞夫,邢留濤.決策樹(shù)C4.5連續(xù)屬性分割閥值算法改進(jìn)及其應(yīng)用[J].中南大學(xué)學(xué)報(bào):自然科學(xué)版,2011,42(12):3 772-3 776.

[2] Garla V, Taylor C, Brandt C. Semi-supervised clinical text classification with Laplacian SVMs: An application to cancer case management[J].Journal of Biomedical Informatics, 2013,46(5):869-875.

[3] 舒振球,趙春霞,張浩峰.基于監(jiān)督學(xué)習(xí)的稀疏編碼及在數(shù)據(jù)表示中的應(yīng)用[J].控制與決策,2014,29(6):1 115- 1 119.

[4] Bavdekar V, Shah S. Computing point estimates from a non-Gaussian posterior distribution using a probabilistick-means clustering approach[J].Journal of Process Control, 2014,24(2):487-497.

[5] Lazaric A, Ghavamzadeh M. Bayesian multi-task reinforcement learning[C].proceedings of the 27th Annual Int Conf on Machine Learning. New York: ACM, 2010:599-606.

[6] 趙鳳飛,覃征.一種多動(dòng)機(jī)強(qiáng)化學(xué)習(xí)框架[J].計(jì)算機(jī)研究與發(fā)展,2013,50(2):240-247.

[7] Tong Z, Xiao Z, Li K, et al. Proactive scheduling in distributed computing—Areinforcement learning approach[J].Journal of Parallel and Distributed Computing, 2014,74(7):2 662-2 672.

[8] Jaksch T, Ortner R, Peter A. Near-optimal regret bounds for reinforcement learning[J].Journal of Machine Learning Research,2010,99(8):1 563-1 600.

[9] Servin A. Kudenko D. Multi-agent reinforcement learning for intrusion detection[C]. Proceedings of the 6th German Conference on Multiagent System Technologies, Berlin:Springer Verlag Berlin Heidelberg, 2008.

[10] 石洪波,柳亞琴.一種基于屬性分割的產(chǎn)生式/判別式混合分類器[J].計(jì)算機(jī)應(yīng)用研究,2012,29(5):1 654- 1 658.

[11] Kumar D A, Sil J. An efficient classifier design integrating rough set and set oriented database operations[J].Applied Soft Computing, 2011,11(2):2 279-2 285.

[12] 劉解放,趙斌,周寧.基于有效載荷的多級(jí)實(shí)時(shí)入侵檢測(cè)系統(tǒng)框架[J].計(jì)算機(jī)科學(xué),2014,41(4):126-133.

[13] Liu D, Li T R, Liang D C. Incorporating logistic regression to decision-theoretic rough sets for classifications[J].International Journal of Approximate Reasoning, 2014,55(1):197-210.

[14] 衷錦儀,葉東毅.基于模糊數(shù)風(fēng)險(xiǎn)最小化的拓展決策粗糙集模型[J].計(jì)算機(jī)科學(xué),2014,41(3):50-54,75.

[15] Skowron A, Rauszer C. The discernibility matrices and functions in information systems[M]∥Huang Shi-Yu (Ed.). Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory. Springer Netherlands, 1991：331-362.

[16] ISCX. The NSL-KDD Data Set[EB/OL].(2012-08-02)[2014-04-20].http://iscx.ca/ NSL- KDD.

(責(zé)任編輯：李華云)

啟 事

本刊已入編《中國(guó)學(xué)術(shù)期刊(光盤版)》、“中國(guó)期刊網(wǎng)”、“萬(wàn)方數(shù)據(jù)——數(shù)字化期刊群”、《中國(guó)科技期刊數(shù)據(jù)庫(kù)》和《CEPS華藝中文電子期刊》，作者著作權(quán)使用費(fèi)在本刊稿酬中一并給付(另有約定者除外)。對(duì)此不同意者，請(qǐng)?jiān)趤?lái)稿時(shí)說(shuō)明。

Reinforcement Learning Classifier Based on Rough Set

ZHENG Zhou1，JI Chunmei2，ZHAO Bin3,LIU Jiefang1

1.School of Information Engineering, Yancheng Institute of Technology, Yancheng Jiangsu 224051, China； 2.College of Electromechanic Engineering, Yancheng Industry Professional Technology Institute, Yancheng Jiangsu 224051, China; 3.School of Computer Science, Beijing University of Technology University, Beijing 100022, China

In order to improve the accuracy of classification, a reinforcement learning classifier based on rough set theory is proposed. First, the continuous attributes in the training data set are discretized by using segmentation algorithm. Second, reducts are obtained by using the rough set theory and finally, one of the reducts providing the highest classification accuracy is chosen. But for the different test data, the same reducts may not reach the highest accuracy of classification because of the changes of discrete attributes value. To overcome this problem, Q-learning algorithm of the reinforcement learning is modified and it can comprehensively and systematically solve the problem of the discretization and feature selection and make different attributes to learn to the best cut value so that the corresponding reducts can produce the maximum accuracy of classification. Experimental results verify that the classifier achieves the accuracy of 98% and exhibits excellent performance compared with other classifiers.

rough sets; reinforcement learning; attribute reducts; discretization; feature selection

2014-06-11

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272500)

鄭周(1984-),男，江蘇徐州人，講師，碩士，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、網(wǎng)絡(luò)安全、物聯(lián)網(wǎng)技術(shù)。

TP393

A

1671-5322(2014)04-0047-08