一種改進的可適應(yīng)變寬核密度估計器

金會賞，何玉林，常秀穎，王曉蘭，蔣 捷

1)滄州職業(yè)技術(shù)學(xué)院信息工程系，河北滄州 061001；2)深圳大學(xué)計算機與軟件學(xué)院大數(shù)據(jù)所，廣東深圳 518060；3)深圳大學(xué)大數(shù)據(jù)系統(tǒng)計算技術(shù)國家工程實驗室，廣東深圳 518060

概率密度估計[1-2]是統(tǒng)計模式識別領(lǐng)域的一個重要研究方向，如何基于已有的數(shù)據(jù)集獲得其未知的概率分布對于眾多有監(jiān)督機器學(xué)習(xí)算法的訓(xùn)練有至關(guān)重要的作用，例如貝葉斯分類器[3]、概率神經(jīng)網(wǎng)絡(luò)[4]和改型決策樹[5]等．帕爾森窗口法[6]是一種經(jīng)典的概率密度估計方法，又稱核密度估計法．它是利用多個正態(tài)分布的疊加平均去擬合未知的概率分布，其中正態(tài)分布的均值為已知的數(shù)據(jù)點，方差為窗口寬度．窗口寬度對于概率密度估計的效果起著至關(guān)重要的作用：較小的窗口寬度將導(dǎo)致“過粗糙”的估計，較大的窗口寬度將引起“較平滑”的估計[7]．

如何確定最優(yōu)窗口寬度成為概率密度估計研究的關(guān)鍵點．當(dāng)前的研究主要集中在以整個數(shù)據(jù)集為估計對象，即最優(yōu)窗口寬度是針對整個數(shù)據(jù)集的．最優(yōu)窗口寬度要使得真實概率密度函數(shù)和估計概率密度函數(shù)之間的均方差(mean square error, MSE)或者均積分方差(mean integrated square error, MISE)達到最小[7]．常見的基于整個數(shù)據(jù)集進行概率密度估計的核密度估計器，包括靴樣核密度估計器[8]、無偏交叉驗證核密度估計器[9]和有偏交叉驗證核密度估計器等[10-11]．

除上述介紹的以整個數(shù)據(jù)集為估計對象的概率密度估計方法之外，還有一類以單個數(shù)據(jù)點為研究對象的概率密度估計方法，最優(yōu)窗口寬度就是針對單個數(shù)據(jù)點的．KATKOVNIK等[12]提出的可適應(yīng)變寬核密度估計器(kernel density estimator with adaptive varying bandwidth, KDE-AVB)正是這樣一種專門針對單個數(shù)據(jù)點的概率密度估計方法．KDE-AVB為單個數(shù)據(jù)點尋找最為適合的核密度估計器窗口寬度，使得該點能夠獲得最為精確的概率密度估計值．為了尋找最優(yōu)的窗口寬度，KDE-AVB使用了置信區(qū)間交叉(intersection of confidence intervals, ICI)法則[13]，將置信區(qū)間上下界對應(yīng)的最小值和最大值發(fā)生交叉的窗口寬度作為最優(yōu)窗口寬度．

本研究為加快KDE-AVB對最優(yōu)窗口寬度的尋找，提出一種改進的可適應(yīng)變寬核密度估計器(improved kernel density estimator with adaptive varying bandwidth, IKDE-AVB)，主要體現(xiàn)在引入了一種可變的標(biāo)準(zhǔn)差項因子去確定置信區(qū)間的上下邊界．可變標(biāo)準(zhǔn)差項因子的引入不僅加快了KDE-AVB 搜索最優(yōu)窗口寬度的速度，而且在一定程度上降低了“過平滑”概率密度估計現(xiàn)象發(fā)生的風(fēng)險．仿真實驗的結(jié)果證實了IKDE-AVB的可行性和有效性．相比于經(jīng)典的KDE-AVB，IKDE-AVB不僅獲得了更快的訓(xùn)練速度，同時提升了概率密度的估計精度．

1 核密度估計法

簡便起見，僅以一維數(shù)據(jù)集為例展開研究．假設(shè)由隨機變量X的N個觀察值構(gòu)成的數(shù)據(jù)集為D={x1,x2, …,xN}，xn∈R，n=1, 2, …,N． 隨機變量X真實的概率密度函數(shù)記作p(x)， 其值未知．核密度估計法采用式(1)得到隨機變量X的估計概率密度函數(shù)，即

(1)

其中，K(u)為高斯核函數(shù)，

(2)

h>0為窗口寬度，取值滿足

(3)

由式(1)可知，核密度估計法采用N個基正態(tài)分布

n=1,2,…,N

(4)

的疊加平均去擬合未知的概率密度函數(shù)p(x)[14]． 以下將通過具體實例來證實該結(jié)論．

首先，隨機生成如表1的20個服從標(biāo)準(zhǔn)正態(tài)分布的數(shù)據(jù)點；然后，采用式(1)估計概率密度函數(shù)，如圖1．由圖1可見，數(shù)據(jù)點密集區(qū)域?qū)?yīng)的估計概率密度函數(shù)呈上凸趨勢，而數(shù)據(jù)點稀疏區(qū)域?qū)?yīng)的估計概率密度函數(shù)呈下凹趨勢．這表明估計概率密度函數(shù)是由20個如式(4)的基于正態(tài)分布的疊加平均擬合而成的．值得注意的是，估計的概率密度函數(shù)與真實概率密度函數(shù)之間存在較大差異，這與窗口寬度的選取有關(guān)．為了清晰展示疊加平均擬合的思想，在此并未使用最優(yōu)窗口寬度．

表1 核密度估計法(h=0.2)

圖1 核密度估計法效果圖(h=0.2)Fig.1 Kernel density estimation method (h=0.2)

2 KDE-AVB

KDE-AVB[12]是一種專門針對單個數(shù)據(jù)點的概率密度估計方法．不同于針對整個數(shù)據(jù)集的窗口寬度選取方法，KDE-AVB為單個數(shù)據(jù)點尋找最為適合的核密度估計器窗口寬度，使得該點能夠獲得最精確的概率密度估計值．

對于數(shù)據(jù)集D中的任意數(shù)據(jù)點xn， 其中，n∈{1, 2, …,N}， KDE-AVB采用如下流程來確定僅針對xn的最優(yōu)窗口h(n)：

首先，生成一個窗口寬度集合H={h1,h2,…,hM}，hm>0，m=1, 2, …,M，且h1

接著，計算每個窗口寬度對應(yīng)的密度估計置信區(qū)間Im=[Lm,Um]． 其中，Im的下邊界為

(5)

置信區(qū)間Im的上邊界為

(6)

密度估計的標(biāo)準(zhǔn)差為

(7)

3 IKDE-AVB

通過分析KDE-AVB的執(zhí)行流程可知，對于含有N個數(shù)據(jù)點的數(shù)據(jù)集D， 和M個窗口寬度值的窗口寬度集合H， 針對D中的所有數(shù)據(jù)點進行概率密度估計的時間復(fù)雜度為O(NM)． 當(dāng)數(shù)據(jù)集的規(guī)模較大時，KDE-AVB需大量的計算時間來為數(shù)據(jù)集中的數(shù)據(jù)點尋找最優(yōu)窗口寬度．本研究給出一種改進的可適應(yīng)變寬核密度估計器IKDE-AVB，來加速對數(shù)據(jù)點最優(yōu)窗口寬度的選?。?/p>

(8)

圖2 基正態(tài)分布隨窗口寬度增加的變化Fig.2 Variation of base normal distribution with increase of bandwidth

隨著h逐漸增大，則a呈單調(diào)上升或單調(diào)下降趨勢．圖2展示了f(x0;xn,h),n∈{1,2,…,N}隨著h增大變化時的兩種情況(紅色曲線對應(yīng)的窗口寬度大于黑色曲線對應(yīng)的窗口寬度)．

1)當(dāng)a呈單調(diào)上升趨勢時，假設(shè)L和U存在如圖3(a)的變化趨勢，可以發(fā)現(xiàn)，若讓下邊界L對應(yīng)的藍線沿著箭頭指示的方向移動到紅線位置，則對應(yīng)的數(shù)據(jù)點x0的最優(yōu)窗口將從hm變?yōu)閔l， 其中， 任意的l,m∈{1, 2, …,M}． 由于hl

2)當(dāng)a呈單調(diào)下降趨勢時，假設(shè)L和U存在如圖3(b)的變化趨勢，可以發(fā)現(xiàn)，若讓上邊界U對應(yīng)的藍線沿著箭頭指示的方向移動到紅線位置，則對應(yīng)數(shù)據(jù)點x0的最優(yōu)窗口將從hm變?yōu)閔l， 其中， 任意的l,m∈{1, 2, …,M}． 由于hl

圖3 置信區(qū)間下邊界和上邊界調(diào)整Fig.3 Adjustment of lower boundary and upper boundary of confidence interval

通過上述分析可知，調(diào)整概率密度估計的置信區(qū)間的上下邊界，能減少KDE-AVB搜索最優(yōu)窗口寬度的次數(shù)．IKDE-AVB通過縮小標(biāo)準(zhǔn)差項因子Г來提升KDE-AVB搜索最優(yōu)窗口寬度的速度．IKDE-AVB采用式(9)調(diào)整置信區(qū)間上下邊界．

(9)

圖4 區(qū)間效用的圖形化表示Fig.4 Illustration of interval utility

定義1區(qū)間效用區(qū)間[L,U]的效用被定義為S=|L|×|U|．

由定義1可得執(zhí)行區(qū)間[a-Г×b,a+Г×b]和[a-ΘГ×b,a+ΘГ×b)的效用分別為

(10)

(11)

(12)

其中， ΔS為區(qū)間[ΘГ×b, Г×b)的效用， ΔS=(ΘГ×b)×(Г×b)=Θ(Г×b)2． 將式(10)和式(11)代入式(12)，化簡后可得

Θ2+Θ=1

(13)

由于Θ∈(0, 1)， 取正數(shù)根Θ≈0.618， 即為GSR．事實上，很多學(xué)者已對GSR在實際應(yīng)用中的優(yōu)越性給予論證，如HE等[15]研究了基于GSR的目標(biāo)追蹤算法，KLEIDER等[16]利用GSR抽樣處理麥克風(fēng)陣列的數(shù)據(jù)挖掘問題，ZONG等[17]利用GSR設(shè)計了用于處理不平衡分類問題的加權(quán)極限學(xué)習(xí)機等，在此不一一贅述．

4 實驗結(jié)果與分析

本研究在5種不同的概率分布數(shù)據(jù)集上，對KDE-AVB和IKDE-AVB的性能進行比較測試．這5種數(shù)據(jù)集包括正態(tài)分布(normal)、指數(shù)分布(exponential)、瑞利分布(Rayleigh)、貝塔分布(beta)和伽瑪分布(gamma)數(shù)據(jù)集，對應(yīng)的概率密度函數(shù)分別為

x∈(-∞, +∞)

(14)

(15)

x∈[0, +∞)

(16)

(17)

(18)

每種分布選用100個數(shù)據(jù)點(x1,x2, …,x100)作為訓(xùn)練集，選用20個數(shù)據(jù)點(y1,y2, …,y20)作為測試集．為保證實驗的可重復(fù)性，詳情請掃描論文末頁右下角二維碼，查看補充材料中的表S1—表S10所列具體的訓(xùn)練集和測試集．服從5種不同分布的數(shù)據(jù)集的可視化展示見圖5—圖9．

圖5 正態(tài)分布數(shù)據(jù)集 (見補充材料表S1和S2)Fig.5 Data sets obeying normal distribution (see Tables S1 and S2 of the supplementary material)

圖6 指數(shù)分布數(shù)據(jù)集 (見補充材料表S3和S4)Fig.6 Data sets obeying exponential distribution (see Tables S3 and S4 of the supplementary material)

圖7 瑞利分布數(shù)據(jù)集 (見補充材料表S5和S6)Fig.7 Data sets obeying Rayleigh distribution (see Tables S5 and S6 of the supplementary material)

圖8 貝塔分布數(shù)據(jù)集 (見補充材料表S7和S8)Fig.8 Data sets obeying beta distribution (see Tables S7 and S8 of the supplementary material)

圖9 伽瑪分布數(shù)據(jù)集 (見補充材料表S9和S10)Fig.9 Data sets obeying gamma distribution (see Tables S9 and S10 of the supplementary material)

令式(13)中的Г=5(沿用文獻[12]中的參數(shù)設(shè)置)．本研究采用“拇指原則”[18]確定啟發(fā)窗口寬度的大小，即

(19)

其中，N為訓(xùn)練集中包含數(shù)據(jù)點的個數(shù)；σ為訓(xùn)練集的標(biāo)準(zhǔn)差．令H={0.001, 0.002, …, 5.000}， 共5 000個備選的窗口寬度值．

表2至表6分別給出了兩種核密度估計器KDE-AVB和IKDE-AVB在5種不同概率分布數(shù)據(jù)集上的比較結(jié)果．

表2 當(dāng)Г=5時KDE-AVB與IKDE-AVB在正態(tài)分布數(shù)據(jù)集上的對比結(jié)果

表3 當(dāng)Г=5時KDE-AVB與IKDE-AVB在指數(shù)分布數(shù)據(jù)集上的對比結(jié)果

由表2至表6可見，IKDE-AVB的最優(yōu)窗口寬度搜索次數(shù)以及估計誤差(真實密度值和估計密度值之差的絕對值)都小于KDE-AVB：

1)在正態(tài)分布數(shù)據(jù)集上，IKDE-AVB的最優(yōu)窗口寬度平均搜索次數(shù)為7，比KDE-AVB降低約25%，同時IKDE-AVB的估計誤差為0.056，比KDE-AVB降低了約63%；

2)在指數(shù)分布數(shù)據(jù)集上，IKDE-AVB的最優(yōu)窗口寬度平均搜索次數(shù)為16，比KDE-AVB降低約50%，同時IKDE-AVB的估計誤差為0.056，比KDE-AVB降低了約59%；

表4 當(dāng)Г=5時KDE-AVB與IKDE-AVB在瑞利分布數(shù)據(jù)集上的對比結(jié)果

3)在瑞利分布數(shù)據(jù)集上，IKDE-AVB的最優(yōu)窗口寬度平均搜索次數(shù)為21，比KDE-AVB降低約50%，同時IKDE-AVB的估計誤差為0.056，比KDE-AVB降低了約55%；

4)在貝塔分布數(shù)據(jù)集上，IKDE-AVB的最優(yōu)窗口寬度平均搜索次數(shù)為123，比KDE-AVB降低約64%，同時IKDE-AVB的估計誤差為0.056，比KDE-AVB降低了約40%；

表5 當(dāng)Г=5時KDE-AVB與IKDE-AVB在貝塔分布數(shù)據(jù)集上的對比結(jié)果

5)在伽瑪分布數(shù)據(jù)集上，IKDE-AVB的最優(yōu)窗口寬度平均搜索次數(shù)為18，比KDE-AVB降低約33%，同時IKDE-AVB的估計誤差為0.056，比KDE-AVB降低了約55%．

以上實驗結(jié)果證實了IKDE-AVB的可行性和有效性．相比經(jīng)典的KDE-AVB，IKDE-AVB具有更快的訓(xùn)練速度和更低的估計誤差．此外，由于IKDE-AVB減少了最優(yōu)窗口寬度的搜索次數(shù)，因此更傾向于選擇較小的窗口寬度，這在一定程度上降低了“過平滑”概率密度估計現(xiàn)象發(fā)生的風(fēng)險．

表6 當(dāng)Г=5時KDE-AVB與IKDE-AVB在伽瑪分布數(shù)據(jù)集上的對比結(jié)果

結(jié) 語

本研究通過引入了一種可變的標(biāo)準(zhǔn)差項因子確定置信區(qū)間的上下邊界，提出了一種改進的可適應(yīng)變寬核密度估計器．相比經(jīng)典的可適應(yīng)變寬核密度估計器，改進的可適應(yīng)變寬核密度估計器不僅具有更快的訓(xùn)練速度，同時提高了概率密度估計的精度．未來，我們將試圖將改進的可適應(yīng)變寬核密度估計器IKDE-AVB推廣到具體的實際應(yīng)用中[19-20]，尤其是以隨機樣本劃分(random sample partition, RSP)數(shù)據(jù)模型[21-23]為基礎(chǔ)的大數(shù)據(jù)管理與分析中．