一種基于近鄰樣本評(píng)估的動(dòng)態(tài)選擇性集成預(yù)測(cè)算法

曲文龍 李一漪 陳笑屹 曲嘉一

摘要：針對(duì)現(xiàn)有的動(dòng)態(tài)選擇策略局限于尋找待測(cè)樣本的局部相似樣本，未充分考慮樣本特征之間的重要性程度，從而對(duì)預(yù)測(cè)精度造成影響的問(wèn)題，該文提出一種基于近鄰樣本評(píng)估的動(dòng)態(tài)選擇性集成預(yù)測(cè)算法。算法基于誤差擾動(dòng)度量出特征的重要性權(quán)值，并在此基礎(chǔ)上進(jìn)行樣本近鄰的相似性度量。根據(jù)不同的待測(cè)樣本特點(diǎn)自動(dòng)適應(yīng)近鄰數(shù)目，找到最佳近鄰。通過(guò)最佳近鄰對(duì)具有不同預(yù)測(cè)精度的學(xué)習(xí)器的性能評(píng)估，擇優(yōu)篩選出精度較高的學(xué)習(xí)器進(jìn)行選擇性集成預(yù)測(cè)。實(shí)驗(yàn)結(jié)果表明，相比原有集成學(xué)習(xí)算法和普通選擇性集成算法，該算法預(yù)測(cè)精度得到進(jìn)一步提升，表現(xiàn)出良好的預(yù)測(cè)效果和較強(qiáng)的預(yù)測(cè)性能。

關(guān)鍵詞：動(dòng)態(tài)選擇性集成;回歸預(yù)測(cè);近鄰樣本;相似度量

中圖分類(lèi)號(hào)：TP181

DOI：10.16152/j.cnki.xdxbzr.2020-05-014

A dynamic selective ensemble prediction algorithm basedon evaluation of neighborhood sample

QU Wenlong1，LI Yiyi1，CHEN Xiaoyi1，QU Jiayi2

（1.School of Information Engineering， Hebei GEO University， Shijiazhuang 050031， China；

2.School of Science， Hebei University of Science and Technology， Shijiazhuang 050018， China）

Abstract： Aiming at the problem that the existing dynamic selection strategy is limited to finding locally similar samples of the test sample and does not fully consider the importance of the sample features， thus affecting the prediction accuracy，? a dynamic selective ensemble prediction algorithm based on evaluation of neighborhood sample is proposed. Based on the importance weight of the feature measured by the error perturbation， the similarity of neighborhood sample is measured. According to the characteristics of different samples to be measured， the number of nearest neighbor is automatically adapted to find the best nearest neighbor. By evaluating the performance of learners with different prediction accuracy， the learner subset with high accuracy is selected for selective ensemble prediction. The experimental results show that， compared with the original ensemble learning algorithm and the common selective ensemble algorithm， the prediction accuracy of this algorithm is further improved， showing that it has good effect of prediction and strong performance.

Key words： dynamic selective ensemble; regression prediction; nearest neighbor sample; similarity measure

回歸預(yù)測(cè)是根據(jù)自變量和因變量之間的相關(guān)關(guān)系進(jìn)行建模預(yù)測(cè)的方法。集成學(xué)習(xí)是由Hansen和Salamon提出的一種將互為差異性的基模型使用某種策略組成起來(lái)，整合為一個(gè)更強(qiáng)大模型的方法［1］。其目的是訓(xùn)練出一個(gè)穩(wěn)定且可靠的強(qiáng)學(xué)習(xí)器，以獲得比單一學(xué)習(xí)器更好的泛化性能。目前，集成學(xué)習(xí)在許多領(lǐng)域都有了廣泛應(yīng)用，在數(shù)據(jù)預(yù)測(cè)方面也有所涉及［2-3］。然而在集成的過(guò)程中，容易引入一些預(yù)測(cè)精度低，性能不佳的基模型而影響最終模型的泛化能力，還會(huì)大大增加所需的存儲(chǔ)空間。

2002年，南京大學(xué)周志華等人首次提出了選擇性集成（selective ensemble），它基于一定的評(píng)估標(biāo)準(zhǔn)將作用不大的基學(xué)習(xí)器拋棄，只保留部分表現(xiàn)較好的作為最終集合器來(lái)構(gòu)建集成模型。通過(guò)實(shí)驗(yàn)驗(yàn)證和理論分析，選擇性集成的預(yù)測(cè)效果明顯優(yōu)于傳統(tǒng)集成方法［4］。2011年，張春霞等人從不同的評(píng)價(jià)準(zhǔn)則角度詳細(xì)綜述了選擇性集成算法，總結(jié)了對(duì)于分類(lèi)和回歸的相應(yīng)研究［5］。早期的選擇性集成通常使用靜態(tài)選擇策略，對(duì)所有待測(cè)樣本均同等對(duì)待，導(dǎo)致篩選出的學(xué)習(xí)器不一定為最優(yōu)集合。

針對(duì)上述問(wèn)題，相關(guān)學(xué)者開(kāi)始了對(duì)動(dòng)態(tài)選擇策略的研究［6］。動(dòng)態(tài)選擇策略考慮到每個(gè)樣本存在的差異性，根據(jù)樣本的不同特點(diǎn)，動(dòng)態(tài)挑選最適合待測(cè)樣本的基學(xué)習(xí)器進(jìn)行預(yù)測(cè)，其優(yōu)勢(shì)在于利用更加靈活的方式減少學(xué)習(xí)器之間的冗余［7-8］。它的主要策略有KNORA（K-nearest-oracles），DCES（dynamic classifier ensemble selection）等［9］，并已應(yīng)用在很多方面，例如人工排水區(qū)域預(yù)測(cè)［10］、客戶流失預(yù)測(cè)［11］等。Oliveira等人以邊緣平衡作為切入點(diǎn)改進(jìn)了KNORA，提出了KNORA-B和KNORA-BI技術(shù)用于提高分類(lèi)器的性能［12］。Luca Didaci等人利用合適的距離度量來(lái)定義鄰域，并通過(guò)鄰域大小的自適應(yīng)來(lái)估計(jì)局部分類(lèi)器的精度進(jìn)行動(dòng)態(tài)集成［13］。為了減弱噪聲對(duì)學(xué)習(xí)器動(dòng)態(tài)選擇的影響，Cruz Rafael提出一種增強(qiáng)的FIRE-DES++方法［14］。目前關(guān)于動(dòng)態(tài)選擇策略的研究主要集中在尋找待測(cè)樣本的局部相似樣本，通常采用歐氏距離作為近鄰相似度的定義，而未充分考慮樣本特征的重要性。鑒于此，本文引入特征重要度進(jìn)行近鄰樣本的相似性度量，根據(jù)最佳近鄰對(duì)各學(xué)習(xí)器的預(yù)測(cè)性能評(píng)估進(jìn)行選擇性集成。

綜上所述，本文提出一種基于近鄰樣本評(píng)估的動(dòng)態(tài)選擇性集成預(yù)測(cè)算法DSERP-KNN（dynamic selective ensemble regression prediction approach based on K-nearest neighbors），該算法首先基于誤差擾動(dòng)的方式度量出特征權(quán)值，并將其作為權(quán)重引入到樣本近鄰的相似性度量中;然后根據(jù)每個(gè)待測(cè)樣本的特點(diǎn)自適應(yīng)近鄰數(shù)目，尋找其最佳近鄰樣本并評(píng)估各學(xué)習(xí)器的預(yù)測(cè)性能。最后在所有基學(xué)習(xí)器中擇優(yōu)挑選出精度較高的學(xué)習(xí)器，進(jìn)行選擇性集成預(yù)測(cè)。相比于原有集成學(xué)習(xí)算法和普通選擇性集成算法，該算法考慮了樣本的特征重要度，有效提高了預(yù)測(cè)精度，加強(qiáng)了預(yù)測(cè)性能。

1 相關(guān)理論

1.1 集成學(xué)習(xí)

集成學(xué)習(xí)是一種通過(guò)結(jié)合多個(gè)較弱學(xué)習(xí)器來(lái)構(gòu)建一個(gè)強(qiáng)學(xué)習(xí)器的方法，主要分為Boosting，Bagging以及Stacking［15］。其中，由Brieman提出的隨機(jī)森林（random forest，RF）是Bagging的代表算法，適用于解決回歸和分類(lèi)問(wèn)題［16］。它是由多棵沒(méi)有剪枝的決策樹(shù)組成，對(duì)于每棵樹(shù)均利用自助法重采樣技術(shù)，有放回地從原始數(shù)據(jù)中抽取樣本組成訓(xùn)練集，建立決策樹(shù)，并最終全部集成來(lái)構(gòu)建出一個(gè)“森林”。它的隨機(jī)性體現(xiàn)在采樣和特征選擇均隨機(jī)，因此，可以降低模型過(guò)擬合的風(fēng)險(xiǎn)［17］。

盡管不易產(chǎn)生過(guò)擬合問(wèn)題，但由于有放回地采樣，使得約1／3的樣本在抽取過(guò)程中始終未被取到，而剩下的樣本中有些會(huì)被多次抽取，因此，參與每棵決策樹(shù)的訓(xùn)練集只包含原始數(shù)據(jù)的2／3。這些未被抽取到的樣本稱(chēng)為袋外數(shù)據(jù)（out of bag data，OOB），它是產(chǎn)生泛化誤差的主要原因［18-19］。

隨機(jī)森林算法的優(yōu)勢(shì)體現(xiàn)在它將多個(gè)弱學(xué)習(xí)器進(jìn)行全集成，使得總體性能得到最大發(fā)揮，且樹(shù)與樹(shù)之間相互獨(dú)立，所以易于并行化的方法來(lái)加快訓(xùn)練速度。當(dāng)處于異常值較多的情況下隨機(jī)森林算法依然能夠保持較高的精度。然而，隨機(jī)森林中含有決策樹(shù)的棵樹(shù)、樹(shù)的深度以及節(jié)點(diǎn)分裂時(shí)的特征個(gè)數(shù)等大量超參數(shù)，它們會(huì)對(duì)算法性能產(chǎn)生較大影響，因此，關(guān)于超參數(shù)的取值是它的研究難點(diǎn)。

1.2 選擇性集成

原有集成學(xué)習(xí)是將創(chuàng)建的所有弱學(xué)習(xí)器融合得到一個(gè)強(qiáng)學(xué)習(xí)器的過(guò)程。盡管它避免了早期機(jī)器學(xué)習(xí)單一的問(wèn)題，但是在學(xué)習(xí)過(guò)程中會(huì)大大增加計(jì)算復(fù)雜度，并且無(wú)法差別對(duì)待不同的學(xué)習(xí)器。為了改善這一問(wèn)題，選擇性集成在前者基礎(chǔ)上增加了學(xué)習(xí)器的篩選階段，通過(guò)對(duì)影響模型整體預(yù)測(cè)效果的學(xué)習(xí)器進(jìn)行剪枝，只集成最具代表性的部分學(xué)習(xí)器，來(lái)提高模型性能。由于學(xué)習(xí)器個(gè)數(shù)的減少，不僅可以提高模型預(yù)測(cè)效果，整體預(yù)測(cè)速度也優(yōu)于全部集成。

對(duì)于現(xiàn)有的選擇性集成算法，它們的區(qū)別主要在于評(píng)測(cè)方法的不同。評(píng)測(cè)方法是一種選擇策略，選擇性集成是基于某種選擇策略來(lái)完成篩選過(guò)程。這些方法可以分為以下4類(lèi)：基于聚類(lèi)的方法、基于排序的方法、基于優(yōu)化的方法以及基于選擇的方法［5］。其中，基于選擇的方法又分為靜態(tài)選擇和動(dòng)態(tài)選擇，靜態(tài)選擇法的主要思想為對(duì)待任意一個(gè)待測(cè)樣本均根據(jù)已篩選好的學(xué)習(xí)器集合來(lái)進(jìn)行預(yù)測(cè)。動(dòng)態(tài)選擇法是本文的研究重點(diǎn)，它是根據(jù)不同待測(cè)樣本的特點(diǎn)，從已有基學(xué)習(xí)器中動(dòng)態(tài)挑選學(xué)習(xí)器進(jìn)行預(yù)測(cè)，每個(gè)待測(cè)樣本對(duì)應(yīng)的學(xué)習(xí)器集合一般是不同的［20］。選擇性集成預(yù)測(cè)算法的具體過(guò)程在算法1中給出。

算法1 選擇性集成預(yù)測(cè)算法

輸入： 訓(xùn)練集Xtrain，測(cè)試集Xtest，基學(xué)習(xí)器個(gè)數(shù)T，評(píng)測(cè)方法M

輸出： 篩選出的學(xué)習(xí)器集合Tt

Step 1 初始化T=Φ

Step 2 for t=1 to T do

Step 2.1 采用抽樣方法從訓(xùn)練集Xtrain中抽取樣本數(shù)據(jù)得到新的訓(xùn)練集X′train

Step 2.2 訓(xùn)練X′train得到基學(xué)習(xí)器，并將其加入到基學(xué)習(xí)器集合T中得到T=｛T1，T2，…，Tt｝

Step 3 end for

Step 4 在測(cè)試集Xtest上對(duì)每個(gè)基學(xué)習(xí)器進(jìn)行預(yù)測(cè)誤差測(cè)試，得到Err′

Step 5 根據(jù)得到的Err′利用評(píng)測(cè)方法M評(píng)價(jià)基學(xué)習(xí)器集合T中的每個(gè)子集，篩選出符合條件的學(xué)習(xí)器集合Tt

Step 6 采用結(jié)合策略集成學(xué)習(xí)器集合Tt，構(gòu)建選擇性集成預(yù)測(cè)模型

2 基于近鄰的動(dòng)態(tài)選擇性集成算法DSERP-KNN

本文利用選擇性集成具有更好的泛化能力和更低的預(yù)測(cè)開(kāi)銷(xiāo)等優(yōu)勢(shì)，提出一種基于近鄰的動(dòng)態(tài)選擇性集成預(yù)測(cè)算法DSERP-KNN。該算法在傳統(tǒng)動(dòng)態(tài)選擇策略的基礎(chǔ)上，考慮了樣本特征的重要性對(duì)預(yù)測(cè)結(jié)果的影響，引入特征重要度作為近鄰的相似性度量，以此找到待測(cè)樣本的最佳近鄰。通過(guò)近鄰樣本對(duì)不同學(xué)習(xí)器的性能評(píng)估進(jìn)行選擇性集成，可以有效提高預(yù)測(cè)精度。

2.1 基于誤差擾動(dòng)的特征權(quán)值度量

特征權(quán)值度量是指樣本特征之間的權(quán)值重要性度量，它是樣本中所有特征重要程度的體現(xiàn)。依據(jù)自助法重采樣會(huì)產(chǎn)生1／3始終未被抽取到的樣本數(shù)據(jù)的特點(diǎn)，通過(guò)計(jì)算這些數(shù)據(jù)的誤差可以得到相應(yīng)特征的重要性權(quán)值度量，即加入輕微干擾后的精度與加入干擾前精度的平均減少量［21］?；谡`差擾動(dòng)的特征權(quán)值度量算法的基本原理為若給某個(gè)特征引入噪聲干擾后導(dǎo)致誤差大幅增加，則說(shuō)明該特征對(duì)于預(yù)測(cè)結(jié)果影響較大，重要程度較高，因此需保留。反之誤差若無(wú)明顯變化則說(shuō)明該特征重要程度較低可考慮剔除。因此，算法首先要使用自助法重采樣抽取到樣本集，然后標(biāo)記始終未抽取到的樣本并計(jì)算誤差，之后加入噪聲干擾并再次計(jì)算誤差，最后利用兩次的誤差結(jié)果計(jì)算出特征的權(quán)值度量?；谡`差擾動(dòng)的特征權(quán)值度量算法的詳細(xì)過(guò)程見(jiàn)算法2。

算法2 基于誤差擾動(dòng)的特征權(quán)值度量算法

輸入： 自助重采樣到的樣本s=1，2，…，S（S為樣本個(gè)數(shù)）

輸出： 特征Xi的權(quán)值度量

Step 1 選擇樣本數(shù)據(jù)s=1，2，…，S作為樣本集S

Step 2 在樣本集S上創(chuàng)建決策樹(shù)Ts，并將始終未被取到的數(shù)據(jù)標(biāo)記為L(zhǎng)s

Step 3 對(duì)于每顆決策樹(shù)Ts，選擇相應(yīng)Ls計(jì)算誤差，記作Err1

Step 4 隨機(jī)對(duì)Ls數(shù)據(jù)中的所有樣本的特征Xi，i=1，2，…，N（N為未被抽取到的數(shù)據(jù)總個(gè)數(shù)）加入噪聲擾動(dòng)，再次計(jì)算誤差，記作Err2

Step 5 計(jì)算特征Xi的權(quán)值度量，

=1T∑（Err2-Err1）。（1）

2.2 樣本近鄰相似度量

2.2.1 主成分分析 主成分分析（principal component analysis，PCA）是一種以較少的特征為代表對(duì)樣本進(jìn)行描述來(lái)降低維度的方法［22］。它的原理是將一個(gè)高維向量Xm×n通過(guò)一個(gè)特殊矩陣投影到低維空間中，最大限度地保留原始高維向量所包含的信息。它的主要方法為通過(guò)對(duì)協(xié)方差特征分解來(lái)提取主成分。

PCA的具體計(jì)算步驟分為4步［23］。首先，求出樣本均值，

=∑ni=1in。（2）

然后，計(jì)算Xm×n的協(xié)方差矩陣Q，

Q=∑mi=1（xi-m）（xi-m）T。? （3）

接著，計(jì)算協(xié)方差矩陣Q的特征值λ和特征向量μ，并將特征值從小到大進(jìn)行排序，

λ=（λ1，λ2，…，λn），λ1≥λ2≥…≥λn，（4）

μ=（μ1，μ2，…，μn）。（5）

最后，計(jì)算特征向量在每一維上的投影矩陣αik，該投影矩陣則為該樣本空間的主成分。

αik=μkT（xi-m）。（6）

2.2.2 特征重要度加權(quán)相似度量 K近鄰算法（K-nearest neighbor，KNN）是一種經(jīng)典的懶惰型學(xué)習(xí)，它省略了訓(xùn)練過(guò)程，因此具有精度高，對(duì)異常值不敏感等優(yōu)勢(shì)，目前在分類(lèi)、回歸等問(wèn)題中有較為成熟的應(yīng)用［24］。其算法原理為基于某種相似性度量找出訓(xùn)練集中與給定待測(cè)樣本最接近的k個(gè)近鄰樣本，并根據(jù)近鄰的信息做出預(yù)測(cè)［25］。當(dāng)KNN算法用于回歸預(yù)測(cè)時(shí)，它將k個(gè)近鄰樣本的預(yù)測(cè)結(jié)果的平均值作為最終結(jié)果。

特征空間中樣本點(diǎn)之間的距離反映了其相似程度，而不同的相似度量方式會(huì)確定不同的近鄰點(diǎn)，從而影響預(yù)測(cè)準(zhǔn)確性。相似性度量可以通過(guò)樣本間距離計(jì)算來(lái)實(shí)現(xiàn)，常用的距離度量方式有歐氏距離、馬氏距離等。然而這些傳統(tǒng)的距離度量往往存在對(duì)樣本的不同特征之間的差別等同對(duì)待的問(wèn)題，并且傳統(tǒng)的空間變換方法如PCA、線性判別分析（LDA）也會(huì)忽視貢獻(xiàn)率小但含有樣本差異的重要信息的特征，從而產(chǎn)生不合理的相似性度量。為了篩選出對(duì)預(yù)測(cè)幫助最大的學(xué)習(xí)器集合，需要首先對(duì)樣本間的相似性做出合理度量，尋找到一個(gè)合適的近鄰，最終根據(jù)最佳近鄰選擇優(yōu)秀的基學(xué)習(xí)器進(jìn)行預(yù)測(cè)。本文以經(jīng)典歐氏距離為基礎(chǔ)，依據(jù)特征重要度計(jì)算特征對(duì)預(yù)測(cè)的貢獻(xiàn)程度的權(quán)值，并賦予權(quán)重w，構(gòu)建新的樣本近鄰相似度量函數(shù)，使其體現(xiàn)出相關(guān)特征的重要性。

n維空間中，樣本點(diǎn)a（xa1，xa2，…，xan）與點(diǎn)b（xb1，xb2，…，xbn）間的歐氏距離公式如式（7）所示，

dab=

（xa1-xb1）2+（xa2-xb2）2+…+（xan-xbn）2=

∑nk=1（xak-xbk）2。（7）

將式（1）中的特征權(quán)值作為權(quán)重w引入式（7）中，根據(jù)特征重要性對(duì)k個(gè)近鄰的貢獻(xiàn)進(jìn)行加權(quán)，定義基于特征重要度加權(quán)的近鄰相似度量d′ab，

d′ab=

w1（xa1-xb1）2+w2（xa2-xb2）2+…+wn（xan-xbn）2=

∑nk=1wk（xak-xbk）2。（8）

其中，wk為權(quán)重，滿足

∑nk=1wk=1。（9）

2.3 基于樣本近鄰預(yù)測(cè)精度評(píng)估的動(dòng)態(tài)選擇性集成預(yù)測(cè)

選擇性集成較普通集成相比，具有預(yù)測(cè)精度高、算法性能強(qiáng)等優(yōu)勢(shì)，因此，為了從已生成的學(xué)習(xí)器集合中選擇出最適合待測(cè)樣本的子集，設(shè)計(jì)一種基于近鄰的動(dòng)態(tài)選擇性集成算法進(jìn)行預(yù)測(cè)。該算法基于之前定義好的近鄰相似性度量，運(yùn)用k的自適應(yīng)得到待測(cè)樣本的最佳近鄰，并以此評(píng)估具有預(yù)測(cè)精度差異的各學(xué)習(xí)器性能，擇優(yōu)篩選出精度較高的學(xué)習(xí)器。通過(guò)近鄰樣本選中的學(xué)習(xí)器進(jìn)行選擇性集成預(yù)測(cè)，可以有效克服全集成產(chǎn)生的計(jì)算量過(guò)大的問(wèn)題，并能針對(duì)待測(cè)樣本的差異性動(dòng)態(tài)選擇其適合的基學(xué)習(xí)器，既可以提高預(yù)測(cè)精度，又可以滿足預(yù)測(cè)性能的要求。

該算法的主要思想是利用樣本近鄰預(yù)測(cè)精度評(píng)估選擇基學(xué)習(xí)器。首先，使用訓(xùn)練集Xtrain生成一定數(shù)量的CART樹(shù)作為基學(xué)習(xí)器集合，之后依據(jù)引入特征權(quán)值后定義的樣本近鄰相似度量，對(duì)每個(gè)待測(cè)樣本分別在k值的不同選取下尋找它的近鄰樣本，并對(duì)每個(gè)近鄰樣本均測(cè)試出所有CART樹(shù)的預(yù)測(cè)誤差集合;然后，對(duì)樹(shù)的預(yù)測(cè)精度設(shè)定一個(gè)容忍度閾值θ，剔除預(yù)測(cè)誤差小于θ的子CART樹(shù)，篩選余下的預(yù)測(cè)性能較好的子CART樹(shù)集合作為待測(cè)樣本的CART樹(shù)子集，并將選中的閾值范圍內(nèi)的CART樹(shù)子集做并集，再使用學(xué)習(xí)法結(jié)合策略集成選出的子CART樹(shù)進(jìn)行選擇性集成，并計(jì)算MSE;最后，比較k取不同值的預(yù)測(cè)精度評(píng)估情況，選擇MSE最小的k值作為最佳近鄰，并利用此近鄰對(duì)應(yīng)的集合學(xué)習(xí)器對(duì)待測(cè)樣本進(jìn)行預(yù)測(cè)，得到最終結(jié)果。基于樣本近鄰預(yù)測(cè)精度評(píng)估的動(dòng)態(tài)選擇性集成預(yù)測(cè)算法詳細(xì)過(guò)程見(jiàn)算法3。

算法3 基于樣本近鄰預(yù)測(cè)精度評(píng)估的動(dòng)態(tài)選擇性集成預(yù)測(cè)算法

輸入：訓(xùn)練集Xtrain，待測(cè)樣本集Xpred，基學(xué)習(xí)器集合T=｛T1，T2，…，Tt｝，近鄰K，容忍度閾值θ∈［0，1］，基于特征重要度加權(quán)的樣本近鄰相似性度量d′ab

輸出：最佳近鄰k，待測(cè)樣本的預(yù)測(cè)值集合Φ=｛yi｝Xtesti=1

Step 1 利用訓(xùn)練集Xtrain生成基學(xué)習(xí)器集合T

Step 2 初始化近鄰K

Step 3 k=K

Step 4 while k

Step 4.1 在待測(cè)樣本集Xpred上，針對(duì)待測(cè)樣本點(diǎn)xi，利用d′ab尋找它的近鄰樣本集Xknn

Step 4.2 初始化選擇出的基學(xué)習(xí)器Tt

Step 4.3 for T=T1 to Tt do

Step 4.3.1 對(duì)每個(gè)近鄰樣本均測(cè)試出所有學(xué)習(xí)器的預(yù)測(cè)誤差，記作mse′

Step 4.3.2 得到測(cè)試出預(yù)測(cè)精度的基學(xué)習(xí)器，記作Tmse

Step 4.3.3 if mse′>θ，Tt=Tt∪Tmse

Step 4.3.4 else

break

Step 4.4 end for

Step 4.5 使用學(xué)習(xí)法結(jié)合策略集成選擇出的基學(xué)習(xí)器Tt，并計(jì)算集合學(xué)習(xí)器的MSE

Step 4.6 k=k+1

Step 5 end while

Step 6 比較k取不同值的預(yù)測(cè)精度評(píng)估情況，選擇使得MSE最小的最佳近鄰k

Step 7 利用最佳近鄰k對(duì)應(yīng)的集合學(xué)習(xí)器對(duì)待測(cè)樣本集Xpred進(jìn)行預(yù)測(cè)，得到預(yù)測(cè)值集合Φ

Step 8 return k，Φ

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證DSERP-KNN算法的性能，本文選取6個(gè)具有代表性的UCI回歸數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，并將隨機(jī)森林（random forest）、靜態(tài)選擇性集成算法、動(dòng)態(tài)選擇性集成算法作為對(duì)比方法。實(shí)驗(yàn)對(duì)每個(gè)數(shù)據(jù)集均采用十折交叉驗(yàn)證法來(lái)測(cè)試算法的準(zhǔn)確性，將80％的數(shù)據(jù)集作為訓(xùn)練集，剩余20％作為測(cè)試集，重復(fù)10次實(shí)驗(yàn)過(guò)程，取其平均值作為最終結(jié)果。

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文實(shí)驗(yàn)所用PC配置環(huán)境為Windows7 64位操作系統(tǒng)，Intel Core i7-3770HQ@3.40GHz CPU，8GB內(nèi)存，編碼環(huán)境為Python 3.5。所用到的UCI回歸數(shù)據(jù)集為：Boston，Air Quality，Bike Sharing，F(xiàn)orest Fires，SkillCraft1，Wine Quality。其中，Bike Sharing選用的是每小時(shí)租賃的自行車(chē)數(shù)量數(shù)據(jù)集，Wine Quality選用的是白葡萄酒質(zhì)量數(shù)據(jù)集。各個(gè)數(shù)據(jù)集的相關(guān)屬性如表1所示。

3.2 評(píng)價(jià)指標(biāo)

本文采用回歸任務(wù)中常用的3個(gè)評(píng)價(jià)指標(biāo)MSE，MAPE和R2來(lái)評(píng)估模型效果，它們的定義公式如下：

1）均方誤差函數(shù)（MSE）

MSE=1n∑ni=1（yi-i）2。（10）

2）平均絕對(duì)百分比誤差函數(shù)（MAPE）

MAPE=1n∑ni=1|yi-iyi|×100％。（11）

3）判定系數(shù)（R2）

R2（y，i）=1-∑ni=1（yi-i）2∑ni=1（yi-i）2。（12）

其中：n表示樣本個(gè)數(shù)；yi為真實(shí)值；yi為預(yù)測(cè)值；i表示真實(shí)值的均值。MSE和MAPE的值越小表明真實(shí)值與預(yù)測(cè)值的誤差越小，模型預(yù)測(cè)越準(zhǔn)確，R2的正常取值范圍為［0，1］，越趨于1，表明模型的擬合效果越好。

3.3 不同算法對(duì)預(yù)測(cè)精度的影響

通過(guò)與其他3個(gè)方法的預(yù)測(cè)精度對(duì)比分析實(shí)驗(yàn)，評(píng)價(jià)本文提出的DSERP-KNN算法。表2為DSERP-KNN算法與其他方法分別在6個(gè)數(shù)據(jù)集上R2值的對(duì)比結(jié)果，表3和表4為相應(yīng)的MSE和MAPE值的對(duì)比結(jié)果。

實(shí)驗(yàn)中首先針對(duì)不同數(shù)據(jù)集樣本特點(diǎn)訓(xùn)練生成T個(gè)基學(xué)習(xí)器，然后按照DSERP-KNN算法流程依次尋找到每個(gè)待測(cè)樣本的前k個(gè)近鄰樣本，并在每個(gè)近鄰樣本上均測(cè)試各學(xué)習(xí)器的MSE值，選擇在容忍度閾值范圍內(nèi)的學(xué)習(xí)器子集進(jìn)行待測(cè)樣本的選擇性集成預(yù)測(cè)。為了進(jìn)一步驗(yàn)證DSERP-KNN算法的有效性，將隨機(jī)森林算法、靜態(tài)選擇法以及動(dòng)態(tài)選擇法作為對(duì)比算法進(jìn)行實(shí)驗(yàn)分析。

從表2中可以明顯地看出，隨機(jī)森林算法在各數(shù)據(jù)集上的表現(xiàn)較差，而選擇后的集成學(xué)習(xí)效果均要優(yōu)于全集成學(xué)習(xí)。靜態(tài)選擇性集成在各數(shù)據(jù)集上的精度都要低于動(dòng)態(tài)選擇性集成，DSERP-KNN算法在各數(shù)據(jù)集上的結(jié)果均優(yōu)于全集成學(xué)習(xí)算法和普通選擇性集成算法，R2值均有所提高。其中，在Wine Quality數(shù)據(jù)集上的提升效果最佳，約為5.0％。

此外，根據(jù)表3和表4的實(shí)驗(yàn)結(jié)果表明，隨機(jī)森林算法在各數(shù)據(jù)集上的表現(xiàn)基本處于較低水平，而DSERP-KNN算法的MSE和MAPE值最低，具有良好的預(yù)測(cè)效果。其中，Bike Sharing數(shù)據(jù)集與其余數(shù)據(jù)集MSE值相差較大是因?yàn)槊總€(gè)數(shù)據(jù)集之間的方差大小存在較大差異性，因此，導(dǎo)致MSE的值也相差較大。通過(guò)表2、表3和表4分析可知，引入樣本近鄰相似度量后的動(dòng)態(tài)選擇性集成算法能夠有效提高預(yù)測(cè)精度。

3.4 不同近鄰數(shù)目k對(duì)預(yù)測(cè)精度的影響

由于本文所提出的DSERP-KNN算法性能與k值的選擇密切相關(guān)，k值的變化會(huì)影響算法的預(yù)測(cè)效果。因此，本文詳細(xì)分析了在不同數(shù)據(jù)集上不同近鄰數(shù)目k對(duì)預(yù)測(cè)精度的影響，如圖1所示。

根據(jù)樣本數(shù)量及特征的不同，近鄰的范圍為1～40。通過(guò)具體分析可知，圖1（a），1（c），1（e）中近鄰k對(duì)MSE的影響波動(dòng)總體較小，在達(dá)到MSE最小值之前曲線呈穩(wěn)步下降趨勢(shì)，說(shuō)明此時(shí)較少的近鄰樣本無(wú)法滿足預(yù)測(cè)的需要。隨著k取值的增大，DSERP-KNN算法精度迅速提高，分別在k=6，k=18以及k=11時(shí)，MSE達(dá)到最低值，此時(shí)預(yù)測(cè)效果最佳。當(dāng)算法找到最佳近鄰后MSE值持續(xù)上升，說(shuō)明近鄰樣本數(shù)目達(dá)到一定的值之后，再加入的近鄰會(huì)對(duì)算法預(yù)測(cè)性能造成干擾。因此，對(duì)于Boston，Bike Sharing和SkillCraft1數(shù)據(jù)集，k=6，k=18和k=11分別為它們的最佳近鄰。圖1（b），1（d），1（f）中，近鄰k對(duì)MSE的影響波動(dòng)總體較大，在達(dá)到MSE最小值之前，曲線基本處于波動(dòng)式下降趨勢(shì)，然后分別在k=13，k=7和k=7時(shí)MSE降到最低。之后圖1（b）基本呈現(xiàn)平穩(wěn)上升，僅在k=23以后有一個(gè)短暫的波動(dòng)。然而圖1（d）和1（f）的MSE值均出現(xiàn)較大波動(dòng)，這可能是因?yàn)殡S著近鄰數(shù)目的上升引入了一些無(wú)關(guān)近鄰，從而影響到了算法的預(yù)測(cè)效果。因此，對(duì)于Air Quality，F(xiàn)orest Fires和Wine Quality數(shù)據(jù)集，它們的最佳近鄰分別為k=13， k=7以及k=7。圖1中的實(shí)驗(yàn)結(jié)果在一定程度上說(shuō)明了針對(duì)不同特點(diǎn)的數(shù)據(jù)集，合適的近鄰數(shù)目k是通過(guò)自適應(yīng)來(lái)選擇的。

3.5 不同近鄰相似度量對(duì)預(yù)測(cè)精度的影響

為了驗(yàn)證本文算法中的相似度量方法的有效性，即基于特征重要度加權(quán)的相似度量（記作w-similarity measure），將歐氏距離度量（euclidean distance）、PCA度量作為對(duì)比方法，在各數(shù)據(jù)集上進(jìn)行預(yù)測(cè)精度實(shí)驗(yàn)分析。為了更加直觀地看出模型效果，采用R2作為評(píng)價(jià)指標(biāo)，結(jié)果如圖2所示。

由圖2可以看到，歐式距離的表現(xiàn)有所欠缺，基本處于較低水平，在SkillCraft1數(shù)據(jù)集和Wine Quality數(shù)據(jù)集上尤為明顯。PCA度量對(duì)精度的影響要略?xún)?yōu)于歐式距離度量，說(shuō)明維度的縮減可以降低數(shù)據(jù)復(fù)雜度，但也可能會(huì)損失掉有用信息?；谔卣髦匾燃訖?quán)的相似度量在6個(gè)數(shù)據(jù)集上的R2值均有小幅度提升，其中，Air Quality數(shù)據(jù)集的提升效果最為明顯。這說(shuō)明了該相似度量方法具有更好的針對(duì)性，能充分考慮樣本特征的重要性程度，驗(yàn)證了本文所采用的相似度量方式是有效的。

綜合以上3個(gè)實(shí)驗(yàn)可以看出，本文提出的DSERP-KNN算法在回歸評(píng)價(jià)指標(biāo)中均為最好，且達(dá)到了針對(duì)不同待測(cè)樣本，根據(jù)其近鄰樣本對(duì)各學(xué)習(xí)器的預(yù)測(cè)精度評(píng)估來(lái)動(dòng)態(tài)篩選學(xué)習(xí)器的目的。同時(shí)還驗(yàn)證了k的自適應(yīng)性以及基于特征重要度加權(quán)的樣本近鄰相似度量方式的有效性，體現(xiàn)出算法具有較高的精度和較好的性能。

4 結(jié) 語(yǔ)

為了改善動(dòng)態(tài)選擇策略中未充分考慮樣本特征的重要性，從而影響預(yù)測(cè)結(jié)果準(zhǔn)確性的問(wèn)題，提出了一種基于近鄰的動(dòng)態(tài)選擇性集成預(yù)測(cè)算法。該算法基于特征重要度加權(quán)的樣本近鄰相似性度量，尋找待測(cè)樣本的最佳近鄰樣本，并根據(jù)樣本近鄰對(duì)學(xué)習(xí)器的預(yù)測(cè)精度評(píng)估篩選基學(xué)習(xí)器，進(jìn)行選擇性集成預(yù)測(cè)。通過(guò)6個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該算法相較于原有集成學(xué)習(xí)和常規(guī)選擇性集成，具有更好的預(yù)測(cè)效果和預(yù)測(cè)性能，這也為今后選擇策略的研究提供了一種新的思路。

另外，研究過(guò)程中也發(fā)現(xiàn)，盡管算法提高了預(yù)測(cè)精度，但是運(yùn)行效率不夠理想，因此，下一階段的研究目標(biāo)是進(jìn)一步優(yōu)化基學(xué)習(xí)器的選擇策略。

參考文獻(xiàn)：

［1］ HANSEN L K， SALAMON P. Neural network ensembles［J］. IEEE Transactions on Pattern Analysis ＆ Machine Intelligence， 2002， 12（10）：993-1001.

［2］ WANG T J， ZHANG Z W， JING X Y， et al. Multiple kernel ensemble learning for software defect prediction［J］. Automated Software Engineering， 2016， 23（4）：569-590.

［3］ CHEN P， HU S S， ZHANG J， et al. A sequence-based dynamic ensemble learning system for protein ligand-binding site prediction［J］.Transactions on Computational Biology and Bioinformatics， 2016， 13（5）：901-912.

［4］ ZHOU Z H， WU J X， TANG W. Ensembling neural networks： Many could be better than all ［J］.Artificial Intelligence， 2002， 137（1）：239-263.

［5］ 張春霞， 張講社. 選擇性集成學(xué)習(xí)算法綜述 ［J］.計(jì)算機(jī)學(xué)報(bào)， 2011， 34（8）：1399-1410.

ZHANG C X，ZHANG J S. A survey of selective ensemble learning algorithms［J］.Chinese Journal of Computers， 2011， 34（8）：1399-1410.

［6］ ABRAHMS B， WELCH H， BRODIE S， et al. Dynamic ensemble models to predict distributions and anthropogenic risk exposure for highly mobile species［J］. Diversity and Distributions， 2019， 25（8）：1182-1193.

［7］MARKATOPOULOU F， TSOUMAKAS G， VLAHAVAS I.Dynamic ensemble pruning based on multi-label classification［J］.Neurocomputing， 2015， 150：501-512.

［8］ MENG J， ZHANG J， LUAN Y S， et al. Parallel gene selection and dynamic ensemble pruning based on affinity propagation［J］.Computers in Biology and Medicine， 2017， 87（8）：8-21.

［9］ 李瑞. 基于聚類(lèi)的動(dòng)態(tài)集成選擇算法［J］.計(jì)算機(jī)應(yīng)用與軟件， 2014， 31（8）：317-323.

LI R. Dynamic ensemble selection algorithm based on clustering［J］.Computer Applications and Software， 2014， 31（8）：317-323.

［10］XIAO J， XIAO Y， HUANG A Q， et al. Feature-selection-based dynamic transfer ensemble model for customer churn prediction［J］. Knowledge and? Information Systems， 2015， 43（1）：29-51.

［11］MLLER A B，BEUCHER A， IVERSEN B V， et al. Predicting artificially drained areas by means of a selective model ensemble［J］. Geoderma， 2018， 320：30-42.

［12］OLIVERA D V R， CAVALCANTI G D C， PORPIONO T N，et al. K-nearest oracles borderline dynamic classifier ensemble selection［C］∥2018 International Joint Conference on Neural Networks（IJCNN）.Rio de Janeiro：IEEE，2018：1-8.

［13］DIDACI L， GIACINTO G.Dynamic classifier selection by adaptive k-nearest-neighbourhood rule［J］.Multiple Classifier Systems， 2004：174-183.

［14］CRUZ R M O， OLIVEIRA D V R， CAVALCANTI G D C， et al. FIRE-DES++：Enhanced online pruning of base classifiers for dynamic ensemble selection［J］.Pattern Recognition， 2019， 85：149-160.

［15］徐繼偉， 楊云. 集成學(xué)習(xí)方法：研究綜述［J］.云南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2018， 40（6）：1082-1092.

XU J W， YANG Y. A survey of ensemble learning approaches［J］.Journal of Yunnan University（Natural Science Edition）， 2018， 40（6）：1082-1092.

［16］BREIMAN L.Random forests［J］.Machine Learning， 2001， 45（1）：5-32.

［17］WANG H Z， YANG F， LUO Z Y. An experimental study of the intrinsic stability of random forest variable importance measures［J］.BMC Bioinformatics， 2016， 17（1）：1-18.

［18］ZHANG T L， XIA D H， TANG H S， et al. Classification of steel samples by laser-induced breakdown spectroscopy and random forest［J］.Chemometrics and Intelligent Laboratory Systems， 2016， 157：196-201.

［19］SHENG L W， ZHANG T L， NIU G H， et al. Classification of iron ores by laser-induced breakdown spectroscopy （LIBS） combined with random forest （RF）［J］.Journal of Analytical Atomic Spectrometry，2015， 30（2）：453-458.

［20］LIN C， CHEN W Q， QIU C， et al. LibD3C： Ensemble classifiers with a clustering and dynamic selection strategy［J］.Neurocomputing， 2014，123：424-435.

［21］VERIKAS A， GELZINIS A， BACAUSKIENE M. Mining data with random forests： A survey and results of new tests［J］.Pattern Recognition， 2011， 44（2）：330-349.

［22］ZHANG Q， PENG C， LU Y M， et al. Airborne electromagnetic data levelling using principal component analysis based on flight line difference［J］.Journal of Applied Geophysics， 2018， 151：290-297.

［23］李遠(yuǎn)博， 曹菡. 基于PCA降維的協(xié)同過(guò)濾推薦算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展， 2016， 26（2）：26-30.

LI Y B， CAO H. Collaborative filtering recommendation algorithm based on PCA dimension reduction［J］.Computer Technolocy and Development， 2016， 26（2）：26-30.

［24］劉鵬， 杜佳芝， 呂偉剛， 等. 面向不平衡數(shù)據(jù)集的一種改進(jìn)的k-近鄰分類(lèi)器［J］.東北大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2019， 40（7）：932-936.

LIU P， DU J Z， LYU W G， et al. A modified KNN classifier for unbalanced dataset［J］.Journal of Northeastern University（Natural Science Edition）， 2019， 40（7）：932-936.

［25］LI C G， QIU Z Y， LIU C T. An Improved Weighted K-Nearest Neighbor Algorithm for Indoor Positioning［J］.Wireless Personal Communications， 2017， 96（2）：2239-2251.

（編 輯 李 靜）