基于鄰域的名詞型數據分類方法

張本文, 孫爽博，董新玲

?

基于鄰域的名詞型數據分類方法

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

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

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

決策規則；分類器；鄰域；覆蓋約簡

引言

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

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

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

將提出的方法應用于四個UCI數據集上，實驗結果表明:將鄰域的方法應用于名詞型數據分類是可行的。隨著訓練規模的逐步增大，分類精度在多數數據集上表現良好，最后可以達到90%以上，并且也有很高的穩定性。召回指標在這些數據集中的表現也較好。綜合考慮這兩個指標，F1-measure值在Zoo這個數據集上是比ID3算法優秀的，Mushroom、Wdbc和Wine這三個數據集的性能和ID3基本相當。

1 相關概念

1.1 決策系統

決策系統廣泛應用于數據挖掘和機器學習中。

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

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

1.2 不可分辯關系和弱不可分辨關系

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

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

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

顯然這個不可分辨關系就是屬性子集上的等價類。可以發現當且僅當兩個對象在上的所有屬性值均相同才能滿足。這樣的要求在許多應用領域太嚴格了，因此文獻[15]提出了弱不可分辨關系這一概念。該概念大大放寬了對象屬性值的要求，只要兩個對象在屬性子集上至少存在一個屬性取值相同即可滿足弱不可分辨關系。

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

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

由此可見不可分辨關系是弱不可分辨關系的一種特殊情況。

1.3 鄰域

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

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

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

其中

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

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

可以通過決策系統中對象的條件屬性值的異同來描述這些對象之間的關系。因此，名詞型數據鄰域的定義如下。

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

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

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

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

{:()í,?} (6)

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

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

() =(,) (7)

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

2 規則生成與分類算法

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

2.1 基于覆蓋約簡的規則生成

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

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

算法1:基于覆蓋約簡的代表生成算法(RG) 輸入:決策系統S=(U,C,g0gggggg)的一定比例的子集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) 計算θx*和nh*(x); (5) end for (6)計算決策屬性對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 基于鄰域覆蓋的分類測試算法

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

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

算法2:基于鄰域覆蓋的分類測試算法(NC) 輸入:測試對象x',代表對象集合Y及覆蓋集CR={(x,θx*)|x?Y}。 輸出:x'的預測類別值d'(x') 。 (1)初始化測試對象與代表對象的相似度θ'=0; (2)初始化測試對象符合規則的代表對象的集合X=?; (3)for (each x?Y ) do //判斷測試對象符合哪些代表的要求 (4) 計算測試對象和代表對象的相似度θ'=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}|;//預測值為滿足規則最多的類別。 (13)end if (14)返回預測類別值d'(x')。

3 實驗分析

實驗分析包含兩部分,第一部份是實驗數據的準備和設置，第二部分是實驗結果分析和性能比較。

3.1 實驗準備

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

表1 四個數據集的基本描述 DatasetFeaturesClassInstances Wine143178 Zoo178101 Wdbc312569 Mushroom2328124

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

3.2 實驗結果

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

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

圖1是權衡了Precision和Recall兩個相互制約的參數，得到F1-measure的變化圖示。隨著訓練規模的增長，整體F1-measure的值都在增長。Zoo、Mushroom和Wdbc這三個數據集最終的F1-measure值達到了90%，Wine也達到了85%，尤其在Mushroom數據集上，F1-measure的性能最好，最后達到99.8%。四個數據集的結果顯示Zoo的F1-measure值在NC算法上一直優于ID3算法，另外三個數據集上顯示兩種算法相差不大。

圖1 NC算法和ID3算法分類結果比較

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

表2 NC算法和ID3算法的分類精度比較 訓練比例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 訓練比例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算法的召回率比較 訓練比例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 訓練比例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 結論與未來的工作

本文基于名詞性對象的屬性提出相似性度量的概念，在保持正域不變的情況下構建出最大鄰域，并采用貪心策略選擇覆蓋最多論域對象的鄰域作為分類的一系列規則。在分類階段，對分類對象同時滿足多條規則的情況采取簡單投票方法對其分類。實驗結果表明這種規則學習方法在處理名詞型數據分類上是行之有效的。

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

[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。

國家自然科學基金61379089，四川省教育廳科研項目基金13ZA0136。

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

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