基于鄰域的名詞型數(shù)據(jù)分類方法

張本文, 孫爽博，董新玲

?

基于鄰域的名詞型數(shù)據(jù)分類方法

張本文1*, 孫爽博2，董新玲2

(1.四川民族學(xué)院計(jì)算機(jī)科學(xué)系，四川康定 626001；2. 西南石油大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，四川成都 610500）

基于鄰域的分類器多用于處理數(shù)值型數(shù)據(jù)，本文提出針對名詞型數(shù)據(jù)的規(guī)則生成及分類的技術(shù)。基于屬性值定義對象的相似性度量，并由此獲得每個(gè)對象的最大鄰域；采用貪心策略依次選擇鄰域構(gòu)建覆蓋及對應(yīng)的規(guī)則集；采用投票解決規(guī)則沖突。在四個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，新方法的分類效果比ID3算法略好。

決策規(guī)則；分類器；鄰域；覆蓋約簡

引言

分類是機(jī)器學(xué)習(xí)[1][2]，數(shù)據(jù)挖掘[3]和模式識別[4]中的一個(gè)基本問題。分類即利用已知數(shù)據(jù)（訓(xùn)練集）獲得知識，并對新的數(shù)據(jù)（測試集）的類別進(jìn)行預(yù)測。分類算法有K近鄰[5]、決策樹[6]、邏輯回歸、樸素貝葉斯、神經(jīng)網(wǎng)絡(luò)等。分類算法的應(yīng)用領(lǐng)域非常廣泛，包括銀行風(fēng)險(xiǎn)評估、客戶類別分類、文本檢索和搜索引擎分類、安全領(lǐng)域中的入侵檢測的應(yīng)用等等。

基于鄰域的分類方法已獲得了國內(nèi)外學(xué)者廣泛關(guān)注。除了經(jīng)典的K近鄰[7]算法以外，還有Hu[8][9]等構(gòu)造的基于鄰域粗糙集模型的特征選擇與規(guī)則生成算法來分類。鄰域的定義有兩種方法：其一是由鄰域內(nèi)所含對象的數(shù)量而定，如經(jīng)典的K近鄰；其二是根據(jù)在某一度量上鄰域中心點(diǎn)到邊界的最大距離而定，如Yao[10]等提出的鄰域粗糙集模型。文獻(xiàn)[11][12]通過隨機(jī)化鄰域?qū)傩约s簡，搜索一組分類精度較高的屬性子集，在不同屬性子集上采用鄰域覆蓋約簡方法學(xué)習(xí)分類規(guī)則，文獻(xiàn)[13]提出了基于鄰域覆蓋的規(guī)則學(xué)習(xí)分類方法。他們的鄰域都是采用歐氏距離，比較直觀且具有物理意義。而名詞型數(shù)據(jù)的距離度量相對困難，因此未被考慮。

本文研究名詞型數(shù)據(jù)的鄰域，基于屬性值定義了對象的相似性度量，并解決相應(yīng)分類器構(gòu)建和使用中的三個(gè)關(guān)鍵技術(shù):規(guī)則生成、規(guī)則約簡和沖突解決。首先為每個(gè)對象創(chuàng)建了最大鄰域(或稱覆蓋塊)來生成規(guī)則，每個(gè)覆蓋塊對應(yīng)一條規(guī)則。這里的鄰域與訓(xùn)練集中的對象密切相關(guān)，也就是前面提到的鄰域的第二種定義。其次，通過采用貪心策略依次選擇覆蓋論域最大的覆蓋塊來約簡規(guī)則。在測試階測試階段，測試樣本完全有可能不滿足通過訓(xùn)練學(xué)習(xí)的規(guī)則，也就會有一些測試樣本無法分類，通過召回這一指標(biāo)來衡量。最后在分類階段采用簡單投票的方法解決某個(gè)對象同時(shí)滿足多條規(guī)則的情況。

將提出的方法應(yīng)用于四個(gè)UCI數(shù)據(jù)集上，實(shí)驗(yàn)結(jié)果表明:將鄰域的方法應(yīng)用于名詞型數(shù)據(jù)分類是可行的。隨著訓(xùn)練規(guī)模的逐步增大，分類精度在多數(shù)數(shù)據(jù)集上表現(xiàn)良好，最后可以達(dá)到90%以上，并且也有很高的穩(wěn)定性。召回指標(biāo)在這些數(shù)據(jù)集中的表現(xiàn)也較好。綜合考慮這兩個(gè)指標(biāo)，F(xiàn)1-measure值在Zoo這個(gè)數(shù)據(jù)集上是比ID3算法優(yōu)秀的，Mushroom、Wdbc和Wine這三個(gè)數(shù)據(jù)集的性能和ID3基本相當(dāng)。

1 相關(guān)概念

1.1 決策系統(tǒng)

決策系統(tǒng)廣泛應(yīng)用于數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)中。

定義1(決策系統(tǒng))[14]:決策系統(tǒng)是一個(gè)三元組{,,}。這里是對象的非空有限集合，也叫做論域，是條件屬性的集合，是決策屬性的集合。

只討論單一決策屬性的名詞型值的決策系統(tǒng)。這樣也就記為{,,}{a, a,…, a}是條件屬性，是唯一的決策屬性。

1.2 不可分辯關(guān)系和弱不可分辨關(guān)系

在決策系統(tǒng)里，論域中的對象可以被任意的條件屬性集劃分成不同的子集。這些子集中的對象在該條件屬性子集上的值是相同的，也就是說從該屬性集上看，同一子集中的對象是無法區(qū)分的。因此可以通過條件屬性值來描述決策系統(tǒng)中對象的這種不可分辨關(guān)系。

定義2(不可分辨關(guān)系)[15]:設(shè)為名詞型值的決策系統(tǒng)，"í",?,那么屬性子集上的不可分辨關(guān)系()定義如下:

(){()?′:() =(),"?} (1)

顯然這個(gè)不可分辨關(guān)系就是屬性子集上的等價(jià)類?？梢园l(fā)現(xiàn)當(dāng)且僅當(dāng)兩個(gè)對象在上的所有屬性值均相同才能滿足。這樣的要求在許多應(yīng)用領(lǐng)域太嚴(yán)格了，因此文獻(xiàn)[15]提出了弱不可分辨關(guān)系這一概念。該概念大大放寬了對象屬性值的要求，只要兩個(gè)對象在屬性子集上至少存在一個(gè)屬性取值相同即可滿足弱不可分辨關(guān)系。

定義3(弱不可分辨關(guān)系)[15]:設(shè)為名詞型值的決策系統(tǒng)，"í"?，那么屬性子集上的弱不可分辨關(guān)系定義如下：

{()?:()()$?} (2)

由此可見不可分辨關(guān)系是弱不可分辨關(guān)系的一種特殊情況。

1.3 鄰域

不可分辨關(guān)系和弱不可分辨關(guān)系之間存在很多等級差別，為了量化這種等級差別，Zhao[15]提出了一個(gè)參數(shù)來表示這種不同級別的不可分辨關(guān)系。據(jù)此，本文提出名詞型屬性相似度的概念如下。

定義4(相似度):設(shè){,,}為名詞型決策系統(tǒng),屬性子集í，論域中任意兩個(gè)對象，的相似度是:

()=(,,)/||(3)

其中

()|{?:()=()}| (4)

簡記(,)(,,)。實(shí)際上，相似度這個(gè)概念和量化的不可分辨關(guān)系是一致的。本文暫不考慮屬性約簡[16]和測試代價(jià)[17]問題，即任意兩個(gè)對象的相似度就是這兩個(gè)對象屬性值相同個(gè)數(shù)和所有屬性數(shù)的一個(gè)比值，顯然(,)?[0,1]。當(dāng)(,)1，那么對象，就是等價(jià)的；當(dāng)(,)9，說明這兩個(gè)對象的屬性值完全不同。

可以通過決策系統(tǒng)中對象的條件屬性值的異同來描述這些對象之間的關(guān)系。因此，名詞型數(shù)據(jù)鄰域的定義如下。

定義5(鄰域):設(shè)?，那么對象用相似度來描述的鄰域是:

(,)={?:(,)≥}(5)

這里的參數(shù)是用戶給定的。顯然(,)隨著的減少會逐漸擴(kuò)大，其鄰域中的對象也會逐漸增加。當(dāng)=1時(shí)，對象的鄰域也就是的等價(jià)對象集合;當(dāng)= 0時(shí)所有對象都是的鄰域。因此一般不取0。在一個(gè)決策系統(tǒng)里面，更感興趣的是每一個(gè)對象最小可能的值。

定義6(最小相似度):設(shè){,,}為名詞型決策系統(tǒng),í,={/||:?{,,..., ||}}，={,,...,},/{}={X,X,...,X}，那么任意?的最小可能的值為:

{:()í,?} (6)

取決于決策系統(tǒng)和對象自身。相應(yīng)地，*的確定也就意味著對象的最大鄰域的確立。

定義7(最大鄰域):對于任意?,其最大鄰域如下:

() =(,) (7)

即的最大鄰域是指通過來度量的論域空間中包含和具有相同的決策屬性值的對象集合。

2 規(guī)則生成與分類算法

給定一個(gè)決策表{,,}，條件屬性集為{a, a,…, a}，論域中的對象為{12, ... ,x}。每一個(gè)對象根據(jù)其屬性的取值情況，即相似度，可以得到若干等價(jià)對象，逐步減少考慮的屬性數(shù)量，保持引入鄰域的對象要保持一致的決策屬性。這樣每一個(gè)對象都存在一個(gè)鄰域，貪心選擇覆蓋正域?qū)ο髷?shù)量最多的鄰域。測試對象與這些選擇出來的代表對象進(jìn)行比較，采取投票的策略得到測試樣本的類標(biāo)號。

2.1 基于覆蓋約簡的規(guī)則生成

本文中規(guī)則生成的目的是獲得一些代表對象及其最大相似度，它們構(gòu)成的鄰域里包含的對象具有相同的決策屬性。首先消除矛盾對象，得到新的論域。其次為每一個(gè)里的對象計(jì)算其最大相似度和最大鄰域。然后從這些鄰域中貪心選擇覆蓋正域最大的鄰域?qū)ο髽?gòu)成代表集合Y。對于另外的決策屬性值的情況，采用完全相同的策略。所有的Y構(gòu)成了能夠覆蓋整個(gè)論域空間的代表對象集合。最后，Y中的每一個(gè)對象都包含其自身的最大相似度，這樣就構(gòu)成了分類規(guī)則。

如算法1所示，(1)行將存儲對象的一系列集合初始化，第(2)行消除矛盾對象得到新的論域空間。(3)-(5)行為每一個(gè)對象計(jì)算它的最小相似度和最大鄰域。(6)行對內(nèi)的對象按決策屬性做出劃分。(7)-(14)行針對每一個(gè)決策屬性值求出它們的覆蓋約簡。這里有兩重循環(huán)，外重For循環(huán)是由論域里對象的決策屬性值的種類來決定的。(8)行將每一個(gè)X'賦給一個(gè)空集合。內(nèi)循環(huán)從X'中每次選擇一個(gè)對象使得它的鄰域能夠覆蓋最多的對象，然后將選擇出來的這個(gè)對象加入集合Y，并且要從中去除已選對象的鄰域。(15)行是循環(huán)結(jié)束后得到的覆蓋塊的集合,也就是約簡后的規(guī)則。

算法1:基于覆蓋約簡的代表生成算法(RG) 輸入:決策系統(tǒng)S=(U,C,j5i0abt0b)的一定比例的子集TrainingSet。 輸出:代表對象集合Y及覆蓋集CR={(x, θx*)|x?Y}。 約束:YíU并且èCR=POSC(d)。 (1)初始化Y,CR,U',X'均為空; (2)消除矛盾對象,得到新集合U'= POSC(d) ; (3)for (each x?U') do (4) 計(jì)算θx*和nh*(x); (5) end for (6)計(jì)算決策屬性對U'的劃分: U'/d={X'1,X'2, … ,X'|vd|}; (7)for (i =1 to |vd|) do //代表及其覆蓋塊的選擇 (8) X'= X'i; (9) while X'1? do (10) 選擇x?(U'? X'i )使得|nh*(x)?X'|最大; (11) Yi= Yiè{x}; (12) X'= X'- nh*(x); (13) end while (14)end for (15)CR={(x, θx*)|x?Y}; (16)返回Y和CR。

2.2 基于鄰域覆蓋的分類測試算法

基于鄰域覆蓋的分類測試的重點(diǎn)在于測試對象符合多條規(guī)則的要求的情況下如何處理的問題。首先要計(jì)算測試對象和每一個(gè)代表對象的相似度。其次，并入符合相似度條件的代表到集合中。然后，測試對象與所有的代表對象比較完畢后，檢測集合的情況，如果為空集說明沒有該測試對象不符合任何規(guī)則的要求，則不給出預(yù)測值。最后將預(yù)測值給出集合X中對象數(shù)量最多的那一類別。

如算法2所示，(1)(2)兩行初始化和符合規(guī)則的代表對象集合。(3)至(8)行將每條規(guī)則的代表對象和測試對象的屬性值進(jìn)行比較，得到相似度。將和這條規(guī)則的比較，如果符合要求則將該代表對象并入集合中。(9)至(13)行首先判斷集合是否為空，如果為空，說明沒有測試對象不符合任何規(guī)則的要求，不需要為其做出預(yù)測值。否則，(12)行則對其做出簡單投票的預(yù)測。使其預(yù)測值為集合中數(shù)量最多的那一類別的決策屬性值。

算法2:基于鄰域覆蓋的分類測試算法(NC) 輸入:測試對象x',代表對象集合Y及覆蓋集CR={(x,θx*)|x?Y}。 輸出:x'的預(yù)測類別值d'(x') 。 (1)初始化測試對象與代表對象的相似度θ'=0; (2)初始化測試對象符合規(guī)則的代表對象的集合X=?; (3)for (each x?Y ) do //判斷測試對象符合哪些代表的要求 (4) 計(jì)算測試對象和代表對象的相似度θ'=sim(x',x); (5) if (θ' 3θx*) then (6) X=Xè{x}; (7) end if (8)end for (9)if (X=? ) then; (10) d'(x')=null; (11)else (12) d'(x')=argmax1￡i￡|vd||{x?X|d(x)=i}|;//預(yù)測值為滿足規(guī)則最多的類別。 (13)end if (14)返回預(yù)測類別值d'(x')。

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)分析包含兩部分,第一部份是實(shí)驗(yàn)數(shù)據(jù)的準(zhǔn)備和設(shè)置，第二部分是實(shí)驗(yàn)結(jié)果分析和性能比較。

3.1 實(shí)驗(yàn)準(zhǔn)備

首先,從UCI數(shù)據(jù)集上下載了4個(gè)數(shù)據(jù)集，分別是Zoo、Mushroom、Wdbc和Wine,數(shù)據(jù)描述如表1所示，每一個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)方案都是一致的。其中后面兩個(gè)數(shù)據(jù)集的數(shù)據(jù)類型并不是名詞型數(shù)據(jù),均對其作了離散化處理。為了體現(xiàn)不同的訓(xùn)練集和測試集數(shù)據(jù)比例，隨機(jī)地將離散化后的數(shù)據(jù)集劃分成兩部份。訓(xùn)練比例分別從0.1到0.6，相應(yīng)的剩余部份就作為測試集數(shù)據(jù)。Mushroom數(shù)據(jù)集的對象較多，并且訓(xùn)練樣本較多之后的分類精度基本沒有太大差異，因此將該數(shù)據(jù)集的訓(xùn)練比例調(diào)整為從0.02到0.12。由于是隨機(jī)選擇，對每一種分類比例，均做了十次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果取其平均值和相應(yīng)的標(biāo)準(zhǔn)差與Weka中的ID3算法作比較。

表1 四個(gè)數(shù)據(jù)集的基本描述 DatasetFeaturesClassInstances Wine143178 Zoo178101 Wdbc312569 Mushroom2328124

其次，由于訓(xùn)練和測試是相對獨(dú)立的兩部分?jǐn)?shù)據(jù)。生成的規(guī)則用于測試的時(shí)候完全有可能有對象不滿足任何規(guī)則。因此，需要采用三個(gè)流行的指標(biāo)的恒量分類器的性能。一是分類精度(Precision，正確分類預(yù)測樣本總數(shù)/做出分類預(yù)測的樣本總數(shù)總數(shù)) ，二是召回(Recall，做出分類預(yù)測的樣本總數(shù)/測試樣本總數(shù)) ，最后一個(gè)指標(biāo)是F-measure,這里采用流行的F1指標(biāo),也即（）。

3.2 實(shí)驗(yàn)結(jié)果

表2顯示兩種算法在四個(gè)數(shù)據(jù)集的不同訓(xùn)練規(guī)模上的Precision的變化。分類精度在四個(gè)數(shù)據(jù)集上隨著訓(xùn)練規(guī)模的增長都在提高，最終所有數(shù)據(jù)集的分類精度都達(dá)到90%以上，且Mushroom的分類精度很高達(dá)到99%以上;后三個(gè)數(shù)據(jù)集幾乎每一種比例NC算法的分類精度都要高于ID3算法，有個(gè)別情況略低，比如Wdbc和Wine訓(xùn)練比例在0.3的時(shí)候以及Zoo的訓(xùn)練比例達(dá)到0.6的時(shí)候，但差距不是很大。表2顯示的另一個(gè)標(biāo)準(zhǔn)差說明伴隨訓(xùn)練比例的增長，Precision的穩(wěn)定性逐步提高，Mushroom數(shù)據(jù)集的分類穩(wěn)定性最高，但是NC算法的穩(wěn)定性要小于ID3算法。

表3顯示兩種算法在四個(gè)數(shù)據(jù)集上不同訓(xùn)練規(guī)模上的Recall的變化。隨著訓(xùn)練規(guī)模的增長，Recall值也在逐步增加，并且穩(wěn)定性也逐步提高。NC算法在Zoo數(shù)據(jù)集上的Recall值都要高于ID3算法，在Mushroom、Wdbc和Wine這三個(gè)數(shù)據(jù)集上多數(shù)訓(xùn)練比例NC算法都稍弱于ID3算法，只有極個(gè)別訓(xùn)練比例NC算法的結(jié)果要稍強(qiáng)于ID3算法，但是整體而言差距不是很大。

圖1是權(quán)衡了Precision和Recall兩個(gè)相互制約的參數(shù)，得到F1-measure的變化圖示。隨著訓(xùn)練規(guī)模的增長，整體F1-measure的值都在增長。Zoo、Mushroom和Wdbc這三個(gè)數(shù)據(jù)集最終的F1-measure值達(dá)到了90%，Wine也達(dá)到了85%，尤其在Mushroom數(shù)據(jù)集上，F(xiàn)1-measure的性能最好，最后達(dá)到99.8%。四個(gè)數(shù)據(jù)集的結(jié)果顯示Zoo的F1-measure值在NC算法上一直優(yōu)于ID3算法，另外三個(gè)數(shù)據(jù)集上顯示兩種算法相差不大。

圖1 NC算法和ID3算法分類結(jié)果比較

(a)Zoo, (b)Mushroom, (c)Wdbc, (d)Wine.

表2 NC算法和ID3算法的分類精度比較 訓(xùn)練比例0.020.040.060.080.100.12 Mushroom(NC)97.58±0.3299.08±0.2499.08±0.1999.49±0.1299.64±0.0999.79±0.08 Mushroom(ID3)97.59±0.3199.28±0.2299.48±0.1599.73±0.1199.75±0.0899.75±0.07 訓(xùn)練比例0.10.20.30.40.50.6 Zoo(NC)81.12±3.3987.50±2.9492.77±2.8194.54±2.6595.24±2.5994.74±2.59 Zoo(ID3)75.00±3.4273.08±3.1876.47±1.9075.00±1.8385.71±2.1294.87±1.67 Wdbc(NC)91.42±1.8292.77±1.2693.89±1.5194.04±0.9394.80±0.8495.52±0.79 Wdbc(ID3)89.96±1.3190.74±0.9594.09±0.7191.69±0.6491.07±0.4492.44±0.57 Wine(NC)80.14±4.1285.97±2.8782.62±1.9489.22±1.8390.74±1.7890.64±1.69 Wine(ID3)78.03±3.8574.22±2.2982.92±1.1990.22±1.5790.24±0.8588.06±1.51 表3 NC算法和ID3算法的召回率比較 訓(xùn)練比例0.020.040.060.080.100.12 Mushroom(NC)99.34±0.2799.48±0.1899.51±0.1599.64±0.1399.78±0.0899.90±0.07 Mushroom(ID3)99.50±0.2599.59±0.1999.79±0.1299.84±0.0999.86±0.0699.86±0.05 訓(xùn)練比例0.10.20.30.40.50.6 Zoo(NC)86.04±2.4188.27±2.3793.10±2.1993.28±1.8794.71±1.7494.88±1.75 Zoo(ID3)69.78±3.0577.04±3.0183.80±1.9385.08±1.6987.25±1.6590.73±1.63 Wdbc(NC)84.48±1.3785.68±1.1786.07±0.9488.04±0.8987.82±0.9189.65±0.84 Wdbc(ID3)87.78±1.5288.93±1.2189.10±0.9789.92±0.9191.86±0.9491.62±0.79 Wine(NC)61.06±4.1371.96±3.8869.12±3.1774.77±2.1280.34±1.9679.31±1.36 Wine(ID3)58.63±3.7971.26±3.6779.68±2.9681.96±2.4382.36±1.8385.28±1.53

4 結(jié)論與未來的工作

本文基于名詞性對象的屬性提出相似性度量的概念，在保持正域不變的情況下構(gòu)建出最大鄰域，并采用貪心策略選擇覆蓋最多論域?qū)ο蟮泥徲蜃鳛榉诸惖囊幌盗幸?guī)則。在分類階段，對分類對象同時(shí)滿足多條規(guī)則的情況采取簡單投票方法對其分類。實(shí)驗(yàn)結(jié)果表明這種規(guī)則學(xué)習(xí)方法在處理名詞型數(shù)據(jù)分類上是行之有效的。

未來將基于鄰域覆蓋這一模型，考慮不同的相似度度量方法來比較分類精度和穩(wěn)定性，例如Eskin，Goodall 和Burnaby等學(xué)者提出的相似度度量方法以及與屬性值發(fā)生頻率有關(guān)的兩種(Occurrence Frequency，Inverse Occurrence Frequency)。進(jìn)而解決新模型下的屬性選擇問題。

[1] Freitag D. Machine learning for information extraction in informal domains [J]. Machine learning, 2000, 39(2-3): 169-202.

[2] Gruber S, Logan R W, Jarrín I, et al. Ensemble learning of inverse probability weights for marginal structural modeling in large observational datasets [J]. Statistics in medicine, 2015, 34(1): 106-117.

[3] Fayyad U, Piatetsky-Shapiro G, Smyth P. From data mining to knowledge discovery in databases [J]. AI magazine 1996,17(3) 37-54.

[4] Mu Y, Ding W, Tao D C. Local discriminative distance metrics ensemble learning [j]. Pattern Recognition. 2013, 46(8):2337-2349

[5] Denoeux T. A k-nearest neighbor classification rule based on Dempster-Shafer theory [J]. Systems, Man and Cybernetics, IEEE Transactions on, 1995, 25(5): 804-813.

[6] Li H X, Zhou X Z. Risk decision making based on decision-theoretic rough set: a three-way view decision model [J]. International Journal of Computational Intelligence Systems.2011, 4(1) 1–11.

[7] Zhang M L, Zhou Z H. ML-KNN: A lazy learning approach to multi-label learning [J]. Pattern recognition, 2007, 40(7): 2038-2048.

[8] Hu Q H, Yu D R, Xie Z X. Numerical attribute reduction based on neighborhood granulation and rough approximation [J]. Journal of Software. 2008, 19(3): 640-649.

[9] Hu Q H, Yu D R, Xie Z X., Neighborhood classifiers [J]. Expert Systems with Applications, 2008, 34(2):866-876.

[10] Yao Y Y, Yao B X. Covering based rough set approximations [J]. Information Sciences 2012, 200: 91–107.

[11] Zhu P F, Hu Q H, Yu D R. Ensemble Learning Based on Randomized Attribute Selection and Neighborhood Covering Reduction [J]. Acta Electronica Sinica . 2012, 40(2):273-279.

[12] Hu Q H, Yu D R, Liu J, et al. Neighborhood rough set based heterogeneous feature subset selection [J]. Information sciences, 2008, 178(18): 3577-3594.

[13] Du, Y., Hu, Q.H., Zhu, P.F. Rule learning for classification based on neighborhood covering reduction [J], Information Sciences, 2011, 181(24): 5457–5467.

[14] Yao Y Y. A partition model of granular computing [M]. Transactions on Rough Sets I. Springer Berlin Heidelberg, 2004: 232–253.

[15] Zhao Y, Yao Y Y, Luo F. Data analysis based on discernibility and indiscernibility [J]. Information Sciences, 2007, 177(22): 4959-4976.

[16] Min F, Zhu W. Attribute reduction of data with error ranges and test costs [J]. Information Sciences, 2012, 211: 48–67.

Neighborhood-based Classification for Nominal Data

ZHANG Benwen1*, SUN Shuangbo2, DONG Xinling2

(1. Department of Computer Science, Sichuan University for Nationalities, Kangding 626001, China 2. School of Computer Science, Southwest Petroleum University, Chengdu 610500, China)

Neighborhood-based approaches are popular in classifier building. However, existing approaches are more often designed for numeric data. In this paper, we propose rule synthesis algorithm with three techniques corresponding to rule generation, rule reduction, and conflict resolving. First, based on the similarity of instances, the maximal neighborhood of each instance is built. Each neighborhood corresponds to a decision rule. Second, since these neighborhoods form a covering of the universe, a covering reduction technique is proposed for rule reduction. The key to this technique is the greedy selection of the block covering the biggest number of uncovered instances. Third, a simply voting technique is developed for conflict resolving in the classification stage. Experimental results on four UCI datasets show that our algorithm is slightly better than the ID3 algorithm.

decision rule; classifier; neighborhood; covering reduction

1672-9129(2016)01-00038-06

TP 3

A

2016-07-04;

2016-07-22。

國家自然科學(xué)基金61379089，四川省教育廳科研項(xiàng)目基金13ZA0136。

張本文(1978-)，男，四川雅安，講師，主要研究方向：代價(jià)敏感，數(shù)據(jù)挖掘，粗糙集；孫爽博（1993-），男，湖北隨州，碩士研究生，主要研究方向：代價(jià)敏感，推薦系統(tǒng)；董新玲（1991-），女，山東德州，碩士研究生，主要研究方向：推薦系統(tǒng)，關(guān)聯(lián)規(guī)則等。

(*通信作者電子郵箱：zhbwin@163.com)