基于BP神經網絡的自適應偽最近鄰分類

曾 勇 舒 歡 胡江平 葛月月

?

基于BP神經網絡的自適應偽最近鄰分類

曾 勇 舒 歡*胡江平 葛月月

(電子科技大學自動化工程學院 成都 611731)

在偽最近鄰(PNN)分類算法中，待分類樣本點與每一類樣本集中各個近鄰的距離加權系數都是主觀確定的，這就使得算法得不到最優距離加權值。針對這一問題，該文提出一種基于BP神經網絡的自適應偽最近鄰分類算法。首先通過計算待分類樣本點與每一類樣本集中各個近鄰的距離值，并將其作為BP神經網絡的輸入。然后根據BP神經網絡輸入與輸出之間的映射來自適應確定相應的距離加權值。最后由BP神經網絡的輸出值判別樣本類別號。實驗結果表明，該算法能夠自適應地調節距離加權系數，同時還能有效地改善分類準確率。

偽最近鄰分類；BP神經網絡；自適應

1 引言

為了解決PNNR存在的不足，本文提出了一種新的分類方法：基于BP神經網絡的自適應偽最近鄰分類方法(Adaptive pseudo Nearest Neighbor classification based on BP neural network, BPANN)，根據同類樣本特征相似，而不同樣本特征值差異較大這一特性來計算測試樣本在每一個類別中的個近鄰點，充分利用了測試樣本在每一類原型樣本集里的多個近鄰信息，將計算出的測試樣本與各近鄰點間的距離值作為網絡輸入，并通過BP神經網絡輸入和輸出之間的映射自適應地訓練距離加權系數，使得分類器的分類精度得以提高。

本文其余部分組織如下：第2節介紹偽最近鄰分類算法；第3節將給出本文所提出的BPANN的具體算法步驟以及分類器設計；第4節是實驗及結果分析；最后是本文結論。

2 偽最近鄰分類

由文獻[17]提出的偽最近鄰規則PNNR(Pseudo Nearest Neighbor Rule)如下：一個測試樣本對給定，則偽最近鄰分類規則把測試樣本分配為其偽最近鄰所屬的類別，如果有多個偽最近鄰，則在其中隨機選擇一個，并把其對應的類別指定給測試樣本。

實驗表明偽最近鄰分類方法的分類性能優于傳統的最近鄰分類方法與傳統的近鄰分類方法，也優于傳統的距離加權的近鄰分類算法[17]，但由于其中的距離加權系數都是人為主觀確定的，并不能得到較優的距離加權值，為此本文提出了一種基于BP神經網絡的自適應偽最近鄰分類的方法。

3 基于BP神經網絡的自適應偽最近鄰分類

基于BP神經網絡的自適應偽最近鄰分類是偽最近鄰分類方法的擴展，與PNN分類算法不同的是，BP神經網絡分類器的輸入不是待分類樣本點的特征值，而是待分類樣本在每一類樣本集中的各個近鄰的距離值。并且距離加權值不需要人為確定，而是由BP神經網絡輸入和輸出之間的映射自適應確定，同時對每類原型樣本自適應的設計其相應的分類器，從有效的樣本資料中得到盡可能多的信息，使其獲得更好的分類效果。圖1顯示的是自適應偽最近鄰分類器的訓練原理圖，其中輸入數據是訓練數據集，分別各自表示屬于類的原型樣本數，表示其對應個近鄰按升序排列的與測試樣本的距離，表示個分類器的輸出值。

圖1 自適應偽最近鄰分類器訓練原理圖

3.1 BPANN模型的參數設置

BP神經網絡具有良好的容錯性、與人腦相似的高度并行性以及聯想記憶功能，容錯能力和自適應學習都較強，可以實現從輸入到輸出的非線性映射。應用于近鄰分類的BP神經網絡分類器，必須結合數據集的情況設計，并在試驗中不斷改進，才能訓練出泛化性能好的模式分類器。所以，必須選擇適當大小的網絡結構，網絡太小不能解決問題，太大則推廣能力差。本文中，BP神經網絡在樣本訓練階段通過附加動量法來調整層與層之間的權值和閾值，從而通過網絡輸入輸出之間的映射自適應的調節距離加權權值，同時針對樣本數據的數據類別自適應的設計其相應的分類器，以便選出較優的分類器。

(1)輸入與輸出層節點數確定：BP網絡的輸入、輸出層維數需要根據實際要求而定，本實驗中，若樣本預處理時采用的是近鄰，那么輸入層的維數就為；而輸出層輸出的則是樣本的相似度即新的距離加權和，因此輸出層的維數為1。

(2)隱層層數的選擇及隱層節點數：根據戈爾莫戈羅夫(Kolmogorov)定理，一個3層的BP網絡足以完成任何從輸入到輸出的連續映射，因此，我們采用具有一個隱層的3層BP神經網絡。隱節點數目的選擇是一個比較復雜的問題，目前確定隱節點數的方法有很多種，主要有修剪方法、復雜性調整方法、增益方法、進化方法、自適應方法[18]等。在大量實驗的基礎上，這里選擇式(4)作為參考。

(3)激活函數的選擇：神經元的激活函數一般選用Sigmoid函數，經過大量實驗對比，最終我們選取式(5)所示logistic函數作為激活函數。

(4)初始權值的選?。阂蛳到y的非線性性使初始權值對學習是否收斂關系很大，故而希望初始權值在輸入累加時使每個神經元的狀態值接近于零。一般，初始權值取隨機數，而且權的值要求比較小。

(5)學習率以及沖量項的選擇：原則上，只要學習率足夠小以保證收斂，但實際上學習率可以影響到最后的網絡性能。而沖量項的目的在于：允許當誤差曲面中存在平坦區時，網絡可以以更快的速度學習，增加了學習過程的穩定性。對于我們所用的Sigmoid型網絡，可以首先將學習率設為0.2，沖量項設為0.9，然后可以在學習過程中適當的改動。

3.2 BPANN分類方法的實現

基于BP神經網絡的自適應偽最近鄰分類方法實現的流程圖如圖2所示。

由于在實際應用中用于訓練的樣本各元素之間取值范圍不可能完全一致，這就給網絡的訓練帶來很大不便，不僅加大了逼近函數的波動性，使網絡訓練速度下降，而且容易造成網絡訓練失敗。因此先對數據進行適當的預處理是非常重要的，這在一定程度上可以加速訓練，提高訓練的成功率。樣本集經過預處理后，便將其送入BP神經網絡中進行網絡訓練。對于一個數據集中個可得的訓練樣本，令分別表示對應于屬于類的訓練樣本數。

圖2 基于BP神經網絡的自適應偽最近鄰分類方法實現流程

BPANN的具體步驟如下：

步驟1 將樣本數據集(data)分為訓練集(trainsam)和測試集(testsam)，進行數據預處理。計算每個訓練樣本點在每一類訓練樣本中的個近鄰，以及到各個近鄰的距離，并將其按升序排列為，對每一類樣本數據經過歸一化處理后計算對應的正例、反例，類的正例、反例個數分別為，其中正例指在類內尋找的樣本點，反例指從類間尋找的樣本。將每一類的正例、反例作為BP神經網絡的輸入，表示為，并且數據集中每一類樣本分別對應一個BP網絡分類器，類共對應個分類器。

{

初始化BP神經網絡，即設定網絡參數。其中輸入層到隱含層與隱含層到輸出層的權值和偏置分別表示為，將它們分別取隨機數。

完成步驟3-步驟5。

}

步驟3 預處理后的數據送入網絡中進行訓練，得到新的權值以及偏置。

本文采用附加動量法來作為權值和偏置的學習算法，其權值學習公式為

式中是網絡輸出的誤差，用于權值和偏置的修正，是網絡隱含層的輸出，,

步驟4 將預處理后的測試樣本送入已經訓練好的網絡中進行分類，找出網絡輸出值中的最大值，也就是新的偽最近鄰，并將測試樣本分到最大值對應的的索引類。

4 實驗結果及分析

實驗是在MATLAB7.11.0環境下實現，采用了機器學習庫UCI[19]上的9個數據集。所使用的數據介紹見表1。數據集Letter, Pen, Thyroid, Optdigits, Landsat-Satellite和Image-Segmentation，其訓練樣本集與測試樣本集已被預先指定。而其余的3個數據集，通過5倍交叉驗證來選擇訓練集與測試集，其中對于數據集采用的距離度量是歐幾里得距離。

現在用BPANN與PNN以及傳統的KNN一起對機器學習庫UCI[19]上的9個數據集進行分類，其中PNN1, PNN2, PNN3, PNN4分別是距離逆加權、指數衰減距離加權、線性距離逆加權、倒數距離加權的偽最近鄰分類，分類結果見表2。對每一個數據集，幾種分類方法中最好的分類結果用黑體表示。

從表2可以看到，對數據集Letter, Pen, Optdigits, Image-Segmentation, Landsat-Satellite以及Wine，基于BP神經網絡的自適應偽最近鄰分類的分類性能明顯好于傳統的近鄰分類以及偽最近鄰分類。而在數據集Thyroid上，BPANN也取得了較好的分類效果。對于數據集Iris和Glass，最終的分類效果沒有得到明顯改善，這是由于它們屬于小樣本數據集，先前沒有分出訓練集和測試集。而BPANN分類算法在分類器設計階段，是通過5倍交叉驗證來選擇訓練集與測試集，交叉分組的訓練數據每次的變化會對權值優化產生較大影響，進而影響分類結果。并且該算法在小樣本數據集上的誤差率是5次分類結果的平均值，避免了實驗結果由于訓練集與測試集選擇的隨機性引起的偶然性。

表3為表2中幾種算法取得相應分類結果的分類時間(因為KNN直接計算測試樣本與訓練樣本之間的距離，不需要進行訓練，因此實驗中記錄的是各個算法的測試時間，即分類時間)，表中時間單位均為秒，幾種分類算法分別在每個數據集上最少的分類時間用黑體表示。

表1所使用數據集的一些特征

仿真所使用的數據集特征維數樣本數類數誤差估計 Letter1616000個訓練樣本26測試樣本4000個 Pen167494個訓練樣本10測試樣本3498個 Thyroid213772個訓練樣本 3測試樣本3428個 Optdigits643823個訓練樣本10測試樣本1797個 Landsat-Satellite364435個訓練樣本 3測試樣本2000個 Image-Segmentation19210個訓練樣本 7測試樣本2100個 Iris 4150 35CV Glass 9214 65CV Wine13178 35CV

表2在9個數據集上的分類誤差(%)

數據集KNNPNN1PNN2PNN3PNN4BPANN Letter4.12 k=3 3.80 3.75 4.30 3.93 3.67 Pen2.12 k=4 1.94 2.26 2.26 1.97 1.92 Thyroid6.33 k=5 6.65 6.42 8.02 6.42 6.33 Optdigits2.00 k=1 1.67 1.84 2.00 1.67 1.56 Landsat-Satellite10.6010.5510.3510.55 9.90 8.90 Image-Segmentation12.3312.3312.3312.3312.3312.14 Wine30.7228.5727.4728.6028.0125.73 Iris 2.67 2.67 2.67 3.33 2.67 3.33 Glass35.0537.1737.6137.2036.2835.27 平均誤差率11.7711.7111.6312.3611.3810.98

表3 不同算法在各數據集上的分類時間(s)

數據集KNNPNN1PNN2PNN3PNN4BPANN Letter35.996538.146644.469945.701341.694623.9958 Pen14.346518.077514.724513.459912.5943 8.0977 Thyroid16.984113.574811.909811.427311.0418 3.6130 Optdigits14.939418.948114.324816.629913.9480 4.1931 Landsat-Satellite13.491213.356611.012811.674111.7278 2.7176 Image-Segmentation 3.9030 4.0412 4.0186 3.3453 3.7430 3.3353 Wine 0.0163 0.0090 0.0296 0.0091 0.0085 0.0234 Iris 0.0119 0.0216 0.0342 0.0378 0.0269 0.0187 Glass 0.0091 0.0100 0.0126 0.0190 0.0257 0.0344

由表3可得，BPANN算法在數據集Letter, Pen, Thyroid, Optdigits, Landsat-Satellite以及Image- Segmentation上的分類時間明顯的小于PNN以及KNN，從算法原理可對此作出解釋，PNN是通過計算距離加權和來分類，而 BPANN是由神經網絡輸入與輸出間的映射來調節權值并分類，使得分類時間相對較少。對于小樣本數據集Wine, Iris和Glass, BPANN在分類時間上沒有取得明顯改善，這是由于為了避免實驗的偶然性，其分類時間計算的是交叉驗證次數的平均值。

5 結論

針對PNN算法中距離加權系數的確定問題，本文提出了一種新的偽最近鄰方法：基于BP神經網絡的自適應偽最近鄰分類方法。在該分類方法中，BP神經網絡的輸入不是待分類樣本點的特征值，而是待分類樣本在每一類樣本集中的各個近鄰的距離值，同時距離加權值不需要人為確定，而是由BP神經網絡輸入和輸出之間的映射自適應確定，并且對每一個數據集自適應的設計其相應分類器。因此在整個分類過程中進一步減少了主觀因素的參與成分，這使得分類器性能具有更好的穩定性和推廣性。在多個UCI數據集上的實驗結果表明，該算法與傳統的KNN算法以及PNN算法相比，取得了更好的分類性能。

[1] WU Xindong, KUMAR V, QUINLAN J R,Top 10 algorithms in data mining[J]., 2008, 14(1): 1-37. doi: 10.1007/s10115-007-0114-2.

[2] MATEI O, POP P C, and V?LEAN H. Optical character recognition in real environments using neural networks and k-nearest neighbor[J]., 2013, 39(4): 739-748. doi: 10.1107/s10489-013-0456-2.

[3] WAN C H, LEE L H, RAJKUMAR R,. A hybrid text classi?cation approach with low dependency on parameter by integrating-nearest neighbor and support vector machine[J]., 2012, 39(15): 11880-11888. doi: 10.1016/j.eswa.2012.02.068.

[4] CARAWAY N M, MCCREIGHT J L, and RAJAGOPALAN B.Multisite stochastic weather generation using cluster analysis and k-nearest neighbor time series resampling[J]., 2014, 508: 197-213. doi: 10.1016/ j.jhydrol.2013.10.054.

[5] RAHMAN S A, HUANG Y, CLAASSEN J,Combining Fourier and lagged-nearest neighbor imputation for biomedical time series data[J]., 2015, 58: 198-207. doi: 10.1016/j.jbi.2015.10. 004.

[6] GONZáLEZ Mabel, BERGMEIR Christoph, TRIGUERO Isaac,. On the stopping criteria for-Nearest Neighbor in positive unlabeled time series classi?cation problems[J]., 2016, 328: 42-59. doi: 10.1016/j.ins. 2015.07.061.

[7] WANG A, AN N, CHEN G,. Accelerating wrapper- based feature selection with-nearest-neighbor[J]., 2015, 83: 81-91.doi: 10.1016/ j.knosys.2015.03.009.

[8] CHEN C H, HUANG W T, Tan T H,. Using K-nearest neighbor classification to diagnose abnormal lung sounds[J]., 2015, 15(6): 13132-13158. doi: 10.3390/s150613132.

[9] HAN Y, PARK K, HONG J,. Distance-constraint k-nearest neighbor searching in mobile sensor networks[J]., 2015, 15(8): 18209-18228.doi: 10.3390/s150818209.

[11] CHOI Sangil, YOUN Ik-hyun, LEMAY Richelle,.Biometric gait recognition based on wireless acceleration sensor using-nearest neighbor classification[C]. 2014 IEEE International Conference on Computing, Networking and Communications (ICNC), Honolulu, HI, 2014: 1091-1095.doi: 10.1109/ICCNC.2014.6785491.

[12] DUDANI S A. The distance-weighted-nearest-neighbor rule[J].,,, 1976, 6(4): 325-327. doi: 10. 1109/TSMC. 1976.5408784.

[13] GOU Jianping, XIONG Taisong, and KUANG Yin. A novel weighted voting for k-nearest neighbor rule[J]., 2011, 6(5): 833-840. doi: 10.4304/jcp.6.5.833- 840.

[14] GOU Jianping, DU Lan, ZHANG Yuhong,A new distance-weighted-nearest neighbor classier[J].&, 2012, 9(6): 1429-1436.

[15] BAILY T and JAIN A K. A note on distance-weighted- nearest neighbor rules[J].,,, 1978, 8(4): 311-313. doi: 10.1109/ TSMC.1978.4309958.

[16] MORIN R L and RAESIDE B E. A reappraisal of distance- weighted-nearest-neighbor classification for pattern recognition with missing data[J].,,, 1981, 11(3): 241-243. doi: 10.1109/TSMC.1981.4308660.

[17] ZENG Yong, YANG Yupu, and ZHAO Liang. Pseudo nearest neighbor rule for pattern classification[J]., 2009, 36: 3587-3595. doi: 10.1016/j.eswa. 2008.02.003.

[18] 楊凡, 趙建民, 朱信忠. 一種基于BP神經網絡的車牌字符分類識別方法[J]. 計算機科學, 2005, 32(8): 192-195.

YANG Fan, ZHAO Jianmin, and ZHU Xinzhong. A new method of license plate characters classified recognition based on BP neural networks[J]., 2005, 32(8): 192-195.

[19] BACHE K and LICHMAN M.UCI repository of machine learning databases[OL].http://www.ics.uci.edu/~mlearn/ MLRepository.html. 2014.

Adaptive Pseudo Nearest Neighbor Classification Based on BP Neural Network

ZENG Yong SHU Huan HU Jiangping GE Yueyue

(,,611731,)

Distance-weighted coefficients between unlabeled sample point and its nearest neighbors belonging to same sample set are determined subjectively in the Pseudo Nearest Neighbor (PNN) classification algorithm, which makes it difficult to obtain optimal distance-weighted value. In this paper, an adaptive pseudo neighbor classification algorithm based on BP neural network is proposed. Firstly, the distance-weighted values between unlabeled sample point and its neighbors lying in the same sample set are regarded as the input of BP neural network. Secondly, the corresponding distance-weighted values are adaptively determined according to the mapping between the inputs and outputs of BP neural network. Finally, the classification of unlabeled sample point is judged by the outputs of BP neural network. Experimental results show that the proposed approach adaptively adjusts the distance-weighted coefficients. Moreover, the classification accuracy can be effectively improved.

Pseudo Nearest Neighbor (PNN) classification; BP neural network; Adaptive

TP181

A

1009-5896(2016)11-2774-06

10.11999/JEIT160133

2016-01-29；改回日期：2016-06-17；

2016-09-08

舒歡 shuhuan163@163.com

國家自然科學基金(61104104, 61473061)，四川省信號與信息重點實驗室基金(SZJJ2009-002)

The National Natural Science Foundation of China (61104104, 61473061), The Fund of Sichuan Provincial Key Laboratory of Signal and Information Processing (SZJJ2009-002)

曾 勇： 男，1968年生，博士，副教授，研究方向為智能信息處理、智能控制理論與應用、計算機視覺與模式識別.

舒 歡： 女，1991年生，碩士生，研究方向為模式識別.

胡江平： 男，1977年生，教授，博士生導師，研究方向為多智能系統建模與控制、傳感器網絡信息融合、智能飛行控制等.