鞠恒榮，丁衛(wèi)平*，尹 濤，范 哲，劉久兵

（1.南通大學 信息科學技術學院，江蘇 南通 226019；2.南通大學 經(jīng)濟與管理學院，江蘇 南通 226019；3.汕頭大學 商學院，廣東 汕頭 515063）

20 世紀80 年代初，波蘭數(shù)學家Z.Pawlak[1-2]教授提出了一種新穎的，能夠處理不精確、不確定性問題的數(shù)學工具——粗糙集理論。該理論定義了一對精確的近似集合，即上近似集合和下近似集合，對目標進行逼近，從而得到一個近似描述。近年來，粗糙集理論得到了進一步的發(fā)展。為了賦予粗糙集正域、邊界域和負域一定的語義解釋，Yao[3]將Bayes風險決策方法引入粗糙集理論模型中，提出了決策理論粗糙集模型。該模型通過分析各種決策的風險代價，找出最小風險代價的決策，以此作為把對象劃分到正域、負域和邊界區(qū)域的依據(jù)，形成了接受決策、拒絕決策和延遲決策的3 支決策語義[3-5]。另一方面，傳統(tǒng)的粗糙集模型僅能處理名義型數(shù)據(jù)，對于連續(xù)型數(shù)據(jù)則需通過離散化方式對數(shù)據(jù)進行預處理。在實際應用中，離散化處理方法改變了原數(shù)據(jù)的分布，使其丟失了很多重要的信息。為了實現(xiàn)對連續(xù)型數(shù)據(jù)的直接處理，Lin[6]將鄰域系統(tǒng)與粗糙集理論相結合提出了鄰域粗糙集的基本模型。其他學者從混合數(shù)據(jù)粒度計算的角度重新定義和解釋了鄰域粗糙集模型并取得了豐富的研究成果[7-8]。

在鄰域粗糙集模型的基礎上，Hu 等[9]提出了鄰域分類器。與k 近鄰分類方法用閾值k 確定鄰域內的樣本數(shù)不同，鄰域分類器通過鄰域半徑來確定樣本鄰域空間所包含的樣本數(shù)。鄰域分類器以其簡單易操作及靈活的尺度，受到了眾多學者的關注[10-14]。然而值得注意的是，鄰域分類器在分類過程中仍然采用的是多數(shù)投票機制（majority voting），即待測樣本的類別標簽由鄰域中多數(shù)樣本的類別標簽決定。這一策略雖簡單，但忽略了數(shù)據(jù)的分布，極易造成錯誤分類。如圖1 所示，樣本x 為待測樣本，δ 為x的鄰域空間，根據(jù)多數(shù)投票策略，不難給出樣本x 的類別標簽為“+”；然而，從數(shù)據(jù)分布看，在鄰域樣本空間中標記為“Δ”的樣本與x 更緊密，將x 的類別標記為“Δ”更合理。

圖1 多數(shù)投票策略Fig.1 Majority voting strategy

為解決這一問題，研究人員采用樣本或屬性加權方式對鄰域分類方法進行改進，例如：Biswas 等[14]提出一種參數(shù)無關的模糊加權k 近鄰算法；李峰等[15]根據(jù)特征含有標簽分類知識量的大小，提出一種基于互信息的?；卣骷訖喽鄻撕瀸W習k 近鄰算法。在上述研究中，權重如何設定是一重要問題，Dempster-Shafer（D-S）證據(jù)理論為解決這一問題提供了新的思路。證據(jù)理論是一種對不確定性問題和知識進行表示和處理的有力工具。目前，關于證據(jù)理論在機器學習和模式識別中的應用主要集中于兩個方面：1）集成學習中基于證據(jù)理論的分類和聚類信息融合；2）直接應用到單個分類器的分類問題中。Denoeux[16]率先將D-S 證據(jù)理論應用到k 近鄰分類學習中；Zhang 等[17]在Denoeux 的研究基礎上，提出了基于證據(jù)理論的k 近鄰集成分類方法?；谧C據(jù)理論的粗糙分類方法少見研究?；谝陨嫌懻?，本文系統(tǒng)研究粗糙集理論視角下基于證據(jù)理論的鄰域分類方法。首先，采用基于鄰域決策錯誤的屬性約簡方法刪除原始信息系統(tǒng)中的冗余屬性；然后，以鄰域粗糙集模型為指引，構建基于D-S 證據(jù)理論的鄰域分類預測方法；最后，通過4 組UCI 的數(shù)據(jù)對本文所提方法進行了對比分析。

1 相關知識介紹

1.1 鄰域粗糙集與分類機制

不失一般性，決策信息系統(tǒng)可被定義為1 個二元組S=＜U，AT∪D＞，其中U 表示所有對象的集合，稱為論域；AT 表示所有條件屬性的集合，D 為決策屬性集合。

對于?a∈AT∪D，定義映射：U →Va，Va表示屬性a 的值域，即a（x）∈Va（?x∈U）。

定義1[7]令S 為一決策系統(tǒng)，對于?xi∈U，B?AT，對象xi基于屬性子空間B 的鄰域則可定義為

其中ΔB為基于屬性子空間B 上對象xi和xj之間的距離函數(shù)，且Δ 滿足如下性質：

1）Δ（xi，xj）≥0；

2）Δ（xi，xj）=0 當且僅當xi=xj；

3）Δ（xi，xj）=Δ（xj，xi）；

4）Δ（xi，xk）≤（xi，xj）+Δ（xj，xk）。

機器學習和數(shù)據(jù)挖掘領域中存在多種距離計算方法，其中徑向基函數(shù)核距離被廣泛應用。與歐式距離不同，徑向基函數(shù)核又稱為高斯核，是一種常用的核函數(shù)。對于任意的對象xi和xj，徑向基函數(shù)核距離為

其中σ 為一個自由參數(shù)。因為徑問基函數(shù)核的值隨距離縮短而減小，并介于0（極限）和1 之間，所以徑向基函數(shù)核距離是一種現(xiàn)成的相似性度量表示法。基于徑向基函數(shù)核距離函數(shù)可定義鄰域粗糙集為

定義2[7]令S 為一決策系統(tǒng)，對于?X?U，B?AT，對象xi基于屬性子空間B 的鄰域表示為δ（B）（xi），那么基于鄰域的下、上近似集則可定義為

假設δB（xi）為待測樣本xi的鄰域，xj為鄰域內的樣本，其類別標記可表示為ωj，那么根據(jù)Hu 等[9]人提出的鄰域分類器中的多數(shù)投票策略，xi的類別標記可表示為

其中I（·）為指示函數(shù)，·為真時其取值為1，否則取值為0。

1.2 Dempster-Shafer 證據(jù)理論

D-S 證據(jù)理論是由Dempster 首先提出并由學生Shafer 進一步發(fā)展為一種完備的不確定性推理理論。假設Ω 是變量x 的所有可能值的窮舉集合，且Ω 中的各元素是相互排斥的。證據(jù)理論中將Ω 稱之為辨別框架。

定義3[16]令A 為辨別框架Ω 的任意子集，其對應于一個數(shù)M∈[0，1]并且滿足

則稱M 為2Ω上的基本概率分配函數(shù)，M（A）為A 的基本概率數(shù)。

上述定義中，若對于任意的A?Ω，且M（A）≠0，那么則稱A 是M 的一個焦元。

根據(jù)基本概率分配函數(shù)，可定義命題的信任函數(shù)Bel 和似然函數(shù)Pl 為

其中：Bel（A）表示對A 的總體信任；Pl（A）表示不否定A 的信任程度。

2 分類學習方法

2.1 屬性約簡

在粗糙集屬性約簡方法中，近似質量經(jīng)常作為度量屬性分類能力的重要指標之一。文獻[18-19]認為樣本落入粗糙集邊界域中并不表示其一定會被錯分，只有邊界域中的少數(shù)類樣本存在被錯分的可能。為此Hu 等[18]人基于鄰域粗糙集模型，從樣本錯誤分類角度提出了鄰域決策錯誤率，并將其作為提取屬性子空間的指標。

假設δB（xi）為樣本xi的鄰域，P1，2，…，c）為δB（xi）在類別ωj下的類別概率。根據(jù)類別概率可分配樣本xi的類別標記。若，則樣本xi的類別標記為ωl，表示為ND（xi）=ωl。顯然，ND（xi）=ω（xi）表示樣本xi的預測類別標記與真實類別標記相同?；诖耍琀u等[18]人給出樣本誤分類的損失函數(shù)

由此可得鄰域錯誤率為

其中n 表示樣本數(shù)。

利用鄰域決策錯誤率，Hu 等[18]進一步提出了基于鄰域決策錯誤率的屬性約簡準則，定義為

定義4[18-19]令S 為一決策信息系統(tǒng)，對于?A?AT，A 為決策信息系統(tǒng)的一個鄰域決策錯誤率約簡當且僅當：

1）NDERA≤NDERAT；

2）對于任意的A′?A，都有NDERA′＞NDERA。

如上定義的約簡集合不僅能夠刪除決策信息系統(tǒng)中的冗余屬性，而且能夠使得原決策系統(tǒng)的鄰域決策錯誤率盡可能的小。即在決策信息系統(tǒng)中，基于鄰域決策錯誤率的約簡屬性子空間能夠完全替代原屬性集合。

根據(jù)鄰域決策錯誤率約簡的定義，對于任意的B?AT，a∈AT -B，屬性a 相對于屬性子集B 的重要度為

根據(jù)屬性重要度，可設計全局和局部屬性子空間求解算法如算法1 所示。

算法1基于鄰域決策錯誤率的屬性約簡

輸入：鄰域決策系統(tǒng)S=＜U，AT∪D＞，鄰域半徑δ。

輸出：約簡屬性集Breduct。

1.→Breduct

2.Do

3.?ai∈AT-Breduct，計算重要度SIG（ai，Breduct，D）

4.選取最大的重要度及對應的屬性aj

5.If SIG（aj，B，D），那么Breduct=Breduct∪{ai}

End If

8.輸出約簡集合Breduct。

2.2 D-S 鄰域粗糙分類

Hu 等[9]人提出的鄰域分類方法采用的是多數(shù)投票策略，該策略忽略了不同數(shù)據(jù)的分布情況。本部分將在鄰域分類框架下，改變多數(shù)投票策略，采用證據(jù)理論這一不確定性推理方法，提出基于D-S證據(jù)理論的鄰域粗糙分類方法。將證據(jù)理論應用到分類問題的關鍵是如何根據(jù)樣本的相似性判斷其屬于同一類別。Denoeux[16]提出用證據(jù)表示類別與鄰域樣本之間的關系。

對于一個待測樣本xt，假定π={X1，X2，…，Xd}為論域U 在決策屬性D 上的劃分，d 為類別數(shù)。ωi={1，2，…，d}表示樣本的類別標記。對于鄰域中任意對象xi，其類別標記為ωi=q，那么（xi，Xq）可作為一個獨立的支持對xt進行分類的證據(jù)。其所包含的證據(jù)信息可定義為

其中：0 ＜α0＜1；γq＞0；Δ 表示徑向基函數(shù)核距離。

待測樣本xt的鄰域中往往有多個樣本，多個樣本對xt的證據(jù)支持則需通過證據(jù)組合方式進行信息融合。令表示樣本xt鄰域中類別標記為q的樣本。根據(jù)D-S 證據(jù)理論，該樣本集對xt的證據(jù)支持可表示為，即

其中K 為歸一化因子，

據(jù)此，可得樣本xt對某一類Xq的信任函數(shù)和似然函數(shù)

假設δB（xi）為待測樣本xi的鄰域，xj為鄰域內的樣本，其類別標記可表示為ωj，那么根據(jù)D-S 證據(jù)理論，xi的類別標記可表示為

根據(jù)以上討論，可設計D-S 證據(jù)理論驅動的鄰域粗糙分類的求解過程如算法2 所示。

算法2D-S 證據(jù)理論驅動的鄰域粗糙分類器

輸入：鄰域決策系統(tǒng)S=＜U，AT∪D＞，鄰域半徑δ，待測樣本xt；

輸出：xt的類別標記。

1.計算論域在決策屬性上的劃分π={X1，X2，…，Xd}；

2.根據(jù)算法1 進行屬性約簡，得到屬性子集B；

3.對任意的xi∈U，計算其與待測樣本之間的距離ΔB（xi，xt）；

4.根據(jù)距離得到xt的鄰域δB（xt）；

5.對任意的Xq∈π，分別計算和

6.計算Mt（{Xq}）和Mt（π）并得到Belt（{Xq}）；

8.輸出xt的類別標記。

算法2 的時間消耗主要是計算待測樣本與訓練樣本之間的距離。證據(jù)信息的計算是基于距離得到的。根據(jù)以上討論可知算法2 的時間復雜度為在鄰域類分類方法中，確定鄰域閾值也是關鍵之一。在本文討論的模型中共有兩個鄰域閾值，即δ 和δ′。雖同為鄰域閾值，但其二者作用并不相同。δ 存在于鄰域粗糙集的構建中而δ′用以預測測試樣本的標記。換言之，δ 為內部鄰域閾值，δ′為外部閾值，且

3 實驗分析

為了驗證本文所提方法的優(yōu)勢，本節(jié)從美國加州大學歐文分校機器學習測試數(shù)據(jù)庫[20]中選取了4組數(shù)據(jù)Glass、Ionosphere、Libras 和Wdbc 對本文所提方法進行測試。Glass 數(shù)據(jù)集包含214 個樣本，10個屬性，決策數(shù)據(jù)被劃分為7 類，表示不同的玻璃類型；Ionosphere 數(shù)據(jù)集包含1 941 個樣本，34 個屬性，所有屬性均為連續(xù)型數(shù)據(jù)，該數(shù)據(jù)集被劃分為2類，分別表示“good”和“bad”；Libras（libras movement）數(shù)據(jù)集包含360 個樣本，91 個屬性，決策屬性被劃分為15 類；Wdbc（diagnostic Wisconsin breast cancer）數(shù)據(jù)集為20 世紀90 年代美國威斯康星州乳腺癌診斷得到的數(shù)據(jù)集，包含596 個樣本，30 個屬性，該數(shù)據(jù)集被劃分為2 類，分別表示“惡性（malignant）”和“良性（benign）”。

本文采用5 折交叉驗證方法，將數(shù)據(jù)集分割成兩部分，即訓練集和測試集。訓練集用以學習鄰域粗糙集模型和分類預測器；測試集用以評估分類預測的性能。為了驗證所提方法的有效性，圖2 從分類精度角度對比了本文所提方法（DSNEC）和Hu 等提出的鄰域分類方法（NEC）[9]。從圖中可以看出，在多數(shù)w 值下，本文所提方法的分類精度優(yōu)于文獻[9]中的鄰域分類方法。特別需要指出的是，當閾值w=0 時，兩種算法的分類效果均相同。這是由于根據(jù)式（21）得到的鄰域里只包含離測試樣本最近的一個樣本或多個距離相等的樣本。在此情況下Hu 等提出的鄰域分類器和本文提出的D-S 鄰域分類方法均退化為最近鄰分類方法。

圖2 不同數(shù)據(jù)集下分類精度比較曲線圖Fig.2 Comparison graphs of classification accuracieswith different data sets

4 結論

為了進一步豐富和發(fā)展鄰域分類方法的研究，本文將D-S 證據(jù)理論引入鄰域粗糙集和鄰域分類方法中。首先在啟發(fā)式求解約簡過程中引入鄰域決策錯誤率的概念構建屬性約簡方法，該方法通過降低分類過程中發(fā)生錯誤判斷的程度來提升分類的性能；其次，在獲取重要屬性之后考慮數(shù)據(jù)集中樣本分布的緊密程度，提出了基于證據(jù)信息的鄰域分類方法。實驗結果表明，本文所提方法不僅可以獲取分類所需要的重要屬性，而且在提升分類精度方面性能顯著。在本文工作基礎上，筆者將在后續(xù)工作中就更高效的分類方法進行深入研究。