簡單子抽樣多元雙樣本檢驗的改進方法

陳麗君， 朱永忠 ， 王方磊

(河海大學 理學院，江蘇 南京211100)

近年來，非平衡類問題成為一個新的研究領域并應用于生物科學、金融、欺詐檢測和文本挖掘等領域。這些領域中的數據分布是不均衡的，如信用卡使用中的欺詐行為通常少于正常使用行為。非平衡的多元雙樣本檢驗問題是非平衡數據研究的問題之一。隨著現代計算機的廣泛應用，檢驗方法的理論發展以及檢驗方法在其他學科中應用的增加，眾多學者對雙樣本檢驗及其檢驗效力進行了大量研究。

早在1969 年，Bickel［1］在經典K-S 檢驗的基礎上，利用混合樣本的經驗分布函數，建立了一種自由分布的多元Smirnov 檢驗。隨后Friedman［2］于1979 年利用混合樣本的最小生成樹(MST)將最大偏離檢驗等雙樣本檢驗由一元情形推廣到多元。1986 年Schilling［3］通過構造一種基于k-最近鄰分類算法(KNN)的檢驗統計量來解決多元雙樣本檢驗問題，但是隨著兩樣本不平衡度的增加，該方法的檢驗效力急劇減弱。2005 年Rosenbaum［4］提出一種基于觀測點最小距離非二分圖(MDP)的交叉匹配檢驗，該檢驗用于低維的大容量樣本時表現出極高的檢驗效力。同年Aslan［5］用觀測點在變量空間的距離作算術函數，構造了一種基于觀測點間能量的多元檢驗統計量。后兩種檢驗方法主要利用混合樣本點之間的緊密性這一性質，而只有當兩個樣本的容量相當時，才能保證檢驗結果的有效性。同時，對這些檢驗方法一致性和漸近性的研究十分依賴于兩樣本平衡這一假設條件。針對這一問題，2013年CHEN Hao［6］考慮到在多元情形中，來自不同分布的樣本點可能比來自同一分布的樣本點有更密切的聯系，從樣本內部邊緣的角度提高了相似圖形檢驗方法的檢驗效力。而CHEN Lisa 等人［7］針對非平衡雙樣本檢驗效力下降的問題改進了Schilling的k 最近鄰檢驗，提出一種簡單子抽樣的多元雙樣本檢驗方法(簡稱SSS-NN 檢驗)。SSS-NN 檢驗方法首先對大樣本采用簡單的隨機子抽樣，再進行Schilling 檢驗統計量的計算，但由于進行隨機子抽樣時丟棄了大樣本的大部分數據，導致樣本信息丟失而產生檢驗誤差。

為此，文中研究基于SSS-NN 檢驗，從平衡樣本容量和充分保留樣本信息的角度出發，采用集成子抽樣方法和加權調整方案，提高非平衡多元雙樣本檢驗的檢驗效力。

1 基于KNN 算法的簡單子抽樣多元雙樣本檢驗

KNN 算法(k-Nearest Neighbor)［8］是一種對局部性質非常敏感的惰性學習，在許多領域都有成功的應用，而且產生了各種各樣的改進算法。KNN 算法的基本思路是:搜索模式空間找出距離最接近未知樣本的k 個訓練樣本，未知樣本被分配到k 個最近鄰樣本中占百分比最多的一類，其近鄰性可以采用歐幾里得距離、馬哈拉諾比斯距離和曼哈頓距離等。

KNN 算法從混合樣本集中搜索與未知樣本最接近的k 個樣本，對每個由j 個屬性組成的樣本，基于KNN 算法的SSS-NN 檢驗方法采用屬性權值為1的歐幾里得距離來度量樣本點之間的近鄰性:

假設點x ∈A，樣本集A ?Rd，定義點x 在集合A{x}中的第k 個近鄰樣本點為NNk(x，A)。進行SSS-NN 檢驗時，對于相互排斥的集合A1和A2，首先使用如下示性函數來判斷樣本點x 與其所在集合(A1∪A2){x}上的第k 個近鄰點是否來自同一樣本:

假設Rd上的獨立隨機樣本X = {X1，X2，…，Xn}，Y = {Y1，Y2，…，Y~n}分別服從未知分布F(x)和G(x)，且F(x)與G(x)在Lebesgue 空間上絕對連續。為了分析樣本與總體之間的差異是否顯著，提出檢驗的零假設為F(x)= G(x)。SSS-NN 檢驗的統計量

其中混合樣本

SSS-NN 檢驗的逐點統計量如式(4)，其衡量的是樣本點Zi在集合X ∪Y 上的k 個最相鄰的樣本點中，與樣本點Zi屬于同一樣本的點所占百分比。

由文獻［3］知，在H1下檢驗統計量Sk，m是連續的，即

其中兩樣本容量比q = ~n/n 為樣本非平衡度，f(x)，g(x)是分布F(x)，G(x)對應的密度函數。然而，當q 逐漸增大時，~Δ(q)的一致性非常弱，即當q →∞，~Δ(q)= o(1/q)。另外，若用以下效用系數ˉη(q)表示Sk，m的漸近性，則當q →∞時，ˉη(q)→0。因此當樣本非平衡度趨于無窮時，Sk，m的漸近能力趨于零，也就是說，當樣本非平衡度趨于無窮時，SSS-NN 方法的檢驗效力趨于零。

2 簡單子抽樣多元雙樣本檢驗的改進方法

2.1 集成子抽樣方法

目前解決數據非均衡問題的方法大致分為兩類［9］:數據水平方法和算法水平方法。均衡樣本集可以考慮采用以下數據水平方法，一種是對大樣本進行欠抽樣，隨機抽取一個樣本容量與小樣本容量相當的子集，另一種是對小樣本實例進行過抽樣。使用欠抽樣方法和過抽樣方法均可以減小兩樣本的非平衡程度。但這兩種方法存在一些弊端，如欠抽樣常常會丟失一些有用的多數類實例信息，過抽樣則會增加許多重復的數據，并且這些數據不是獨立同分布的，容易增大過分擬合的可能性。

近十余年來，集成方法［10］被廣泛應用于回歸問題和分類問題中。集成方法的核心思想是:對于一系列適合用于處理原始數據的簡單模型，通過特定的算法或操作把它們組合成一個預測穩定性和準確度更高的新模型。集成子抽樣方法貫徹這一思想，通過組合應用在不同混合樣本的最近鄰計算過程，從數據水平層面減小樣本非平衡度，具體過程如下:對于每一個混合樣本點Zi(i = 1，…，m)，若Zi∈X，則從大樣本Y 中隨機抽取一個容量為ns的子樣本Si;若Zi∈Y，則從樣本Y{Zi}中隨機抽取一個容量為ns－1 的子樣本Si，并將樣本點Zi放入集合Si中，最后得到m 個容量為n + ns的混合樣本X ∪Si。利用每一個混合樣本點和相應的混合樣本進行KNN 計算。

與僅對大樣本進行一次簡單子抽樣的樣本均衡方法相比，集成子抽樣對混合樣本的每一個點獨立地從大樣本中進行一次隨機子抽樣，充分保留了所有樣本點的實例信息，同時事先對樣本進行約簡，能快速得出待判樣本點是否屬于同一樣本。進行樣本動態變化的KNN 計算，提高了逐點統計量的計算效率和準確性。

2.2 基于集成子抽樣的改進SSS-NN 檢驗

當兩個樣本非平衡度很大時，即n ?~n 時，隨著樣本非平衡度的增大，SSS-NN 檢驗方法的檢驗性能急劇減弱。這種現象同樣存在于游程檢驗［11］和交叉檢驗［12］中，都是由大樣本的主導性影響所引起的。簡單地說，當大樣本占混合樣本的大多數時，無論在H0下還是在H1下，小樣本X 上的被加數

較小，大樣本Y 上的被加數

較大，增大了KNN 計算的誤判率，從而導致SSS-NN方法在檢驗兩個未知分布的差異時性能減弱。第1節的式(5)、式(6)從理論上解釋了這一現象的本質。

文中提出集成子抽樣方法從數據層面均衡兩樣本容量，以改善樣本容量不平衡帶來的問題。進行集成子抽樣時，選擇隨機抽取容量為n 的子樣本，為的是使檢驗的兩個樣本容量相當，從數據水平層面減小大樣本的主導性影響。另一方面，當ns≠n時，還要考慮不同樣本點共享同一近鄰點這一問題，此時計算檢驗統計量的漸近方差十分困難。從而明智的選擇是令ns= n。

文中在SSS-NN 檢驗的基礎上，將集成子抽樣與權重調整相結合提出改進的SSS-NN 檢驗——集成子抽樣多元雙樣本檢驗(以下簡稱MESS-NN 檢驗)。具體步驟如下:

1)對問題提出檢驗假設，并預先選定顯著性水平。通常情況下取α = 0.01 或0.05。

2)對待檢驗的兩個樣本進行集成子抽樣。

3)進行集成子抽樣后，采用基于歐幾里得距離的k-最近鄰算法進行逐點統計，即對每一個混合樣本點Zi，計算與其屬于同一樣本的近鄰樣本點數量在混合樣本X ∪Si中所占的比例:

該步驟是對SSS-NN 檢驗的逐點統計過程的一次改進，每一個混合樣本點進行最近鄰計算的樣本空間都是不同的。

4)計算檢驗統計量的樣本觀察值Tk，n。

利用m 個逐點統計量構造新的統計量時，權值的選擇是一個很有意義的研究內容。由于進行逐點統計的混合樣本點或者來自樣本X，或者來自樣本Y。上文提到過無論在零假設下還是備擇假設下，最近鄰計算的結果都受到大樣本的主導性影響，因此使用權重分別調整兩個待檢驗樣本對檢驗結果的影響，確切地說，在使用逐點統計量構造檢驗統計量時，對屬于樣本的每一個混合樣本點，通過賦予較小的權值調整相應統計量的權重，從而減小大樣本的主導性對檢驗統計量的影響。根據樣本非平衡度，選取點Zn+1，…，Zm的逐點統計量的權重為

綜合上述集成子抽樣方法和權值調整方案，提出一種受樣本非平衡度影響較小的集成子抽樣多元雙樣本檢驗統計量。于是，得到MESS-NN 檢驗統計量如下:

由于樣本集X 與樣本集Y 的檢驗是非對稱的，因此要單獨考慮下列情形:(1)樣本集X 中的點互為近鄰，即

(2)樣本集Y 中的點互為近鄰，即

(3)樣本集X 中的點與樣本集Y 中的點有相同的近鄰，即

在H0下，MESS-NN 檢驗統計量的漸近零分布是以下正態分布:

其中

這里

5)重復步驟2 ～4 N 次，并對N 次統計量的計算結果取平均值，一般來說，重復的次數越多，檢驗結果越準確。

6)根據所提出的顯著水平，確定臨界值和拒絕域，并做出檢驗決策。

3 仿真實驗與實證分析

3.1 仿真實驗

在假設同一樣本數據服從以下6 組隨機選取的正態分布模型的前提下，用Monte-Carlo 方法分別生成1維和5 維的隨機樣本進行仿真實驗，運用SSS-NN 方法和MESS-NN 方法對隨機樣本進行雙樣本檢驗，利用Matlab 軟件編程并繪制相應的檢驗效力圖。

1)方差相同的正態分布。每一個模型隨機選取兩個樣本方差相同而樣本均值不同的正態分布。兩組分布的參數分別為

模型1.1

模型1.2

2)均值相同的正態分布。每個模型的兩個分布都有相同的樣本均值向量μLd，不同的樣本協方差矩陣σ2Id，其中Ld為d 維單位向量，Id為d 階單位陣。分布的參數分別為

模型2.1

模型2.2

3)方差、均值都不相同的正態分布。每個模型的兩個分布的樣本均值向量μLd和樣本協方差矩陣σ2Id均不同。分布的參數分別為

模型3.1

模型3.2

使用SSS-NN 方法或MESS-NN 方法進行400 次雙樣本檢驗，用拒絕H0的次數占檢驗總次數的百分率來衡量檢驗效力。在實驗中分別選擇1 維和5 維的正態分布數據作為實驗對象，對于每一個1 維或5維的正態分布模型，均從第1 個正態分布中隨機抽取一個容量為100 的小樣本，再從第2 個正態分布中隨機抽取容量分別為100，400，1 600，6 400 的大樣本;在顯著性水平α = 0.05 下使用SSS-NN、MESS-NN 方法進行檢驗，并做出檢驗決策，最后計算檢驗效力。以KNN 計算過程中k 的取值為橫坐標，以檢驗效力為縱坐標，得到樣本非平衡度為q =1，4，16，64 時的檢驗效力如圖1，2 所示。由于每個模型中的兩個正態分布均不相同，因此越是檢驗效力強的檢驗方法，越應該以大概率拒絕H0。

圖1(a)和圖2(a)分別展示SSS-NN、MESS-NN方法應用于隨機模型1.1 的檢驗效力，圖1(b)和圖2(b)是模型2.1 的檢驗結果，圖1(c)和圖2(c)是模型3.1 的檢驗結果等。觀察圖1(a)～1(f)可知，當小樣本容量固定時，隨著非平衡度q 的增大，SSS-NN 方法的檢驗效力急劇減弱，在多元情形下，樣本比為16 或64 時檢驗效力不高于20%，甚至無法檢驗兩個樣本之間的差異，如圖1(b)、圖1(e)、圖(f)所示。相比之下，觀察圖2(a)～2(f)可知，MESS-NN 受比值q 的影響較小，樣本不平衡下檢驗效力甚至高達80%，說明MESS-NN 方法在檢驗非平衡的多元雙樣本問題時比SSS-NN 方法更優越。

3.2 實例分析

收集、整理了淮河流域2007 年1 月至2011 年12月和白水河流域2010 年1 月至2011 年12 月的歷史測量數據，對于個別缺測的氣象數據，利用鄰近站點資料進行相關插補。隨后分別使用SSS-NN 檢驗和MESS-NN 檢驗分析這兩個流域在逐日平均流量、逐日降水量、逐日水面蒸發量這3 個方面是否存在顯著差異。

數據預處理首先采用算術平均法將流域內的各站點降水轉換成面平均降水，其中原始數據有淮河流域的大坡嶺站、黃岡站等13 個氣象站點，白水河有七鄰站、葉氏祠站等12 個氣象站點。處理得到的逐日降水量與對應日期的逐日平均流量、逐日水面蒸發量構成1 個三維向量，得到淮河流域1 825 個樣本點，白水河流域730 個樣本點，樣本容量比q =2.5。將SSS-NN 方法和MESS-NN 方法應用于這兩個樣本，取顯著性水平α = 0.05，所得檢驗效力比較結果如表1 所示。

圖1 SSS-NN 方法在q = 1，4，16，64 時的檢驗效力實驗結果Fig.1 Simulation results comparing the power of the SSS-NN for q = 1，4，16，64

圖2 MESS-NN 方法在q = 1，4，16，64 時的檢驗效力實驗結果Fig.2 Simulation results comparing the power of the MESS-NN for q = 1，4，16，64

表1 原始SSS-NN 方法和改進SSS-NN 方法的檢驗效力結果比較Tab.1 Power value for comparing the original SSS-NN and the improved SSS-NN method

由表1 可知z ＞zα/2，即統計量的值落在了拒絕域，因此拒絕H0，認為這兩個樣本存在顯著差異。圖3(a)、圖3(b)分別是兩個流域樣本的平均水面蒸發量分布圖，特別地，圖3(b)相對于圖3(a)而言呈現“長尾”狀，顯然淮河流域樣本和白水河流域樣本存在顯著差異。因此對于SSS-NN 檢驗方法而言，MESS-NN 檢驗方法能以更高的檢驗效力體現出這兩個樣本的顯著差異。

圖3 淮河流域、白水河流域平均水面蒸發量分布Fig.3 Histograms of Huaihe River and Baihe River in precipitation

事實上由于河流的平均流量、降水量、水面蒸發量受地理位置、地形、氣候、植被、水利調控等因素的影響［13-15］，所以該檢驗結果符合實際情況，是合理的。

4 結 語

為了解決非平衡多元雙樣本的檢驗問題，將集成子抽樣方法應用于基于KNN 算法的簡單子抽樣多元雙樣本檢驗中，由于進行集成子抽樣，極大地保留了樣本數據的信息，因此有效地達到了平衡樣本容量的目的。同時由于構造檢驗統計量時采用了加權運算，減弱了大樣本對KNN 計算結果帶來的主導性影響，提高了檢驗效力。最后，多次重復檢驗，減小了混合樣本隨機性帶來的影響，進一步提高了檢驗結果的準確率。仿真實驗表明，集成子抽樣多元雙樣本檢驗有效地改善了簡單子抽樣多元雙樣本檢驗在檢驗非平衡多元雙樣本時檢驗效力下降的問題。

改進后的簡單子抽樣多元雙樣本檢驗還有很多局限，如KNN 算法的計算時間過長。另外，對于兩個樣本容量都較小且樣本非平衡的情形，過少的觀測點導致MESS-NN 方法的檢驗效果不理想，因此尋找適用于這種情形的檢驗方法也是一個值得研究的方向。

［1］Bickel P J. A distribution free version of the Smirnov two sample test in the p-variate case［J］. The Annals of Mathematical Statistics，1969，40(1):1-23.

［2］Friedman J H，Rafsky L C. Multivariate generalizations of the wald wolfowitz and smirnov two-sample tests［J］. The Annals of Statistics，1979，7(4):697-717.

［3］Schilling M F. Multivariate two-sample tests based on nearest neighbors［J］. Journal of the American Statistical Association，1986，81(395):799-806.

［4］Rosenbaum P R.An exact distribution-free test comparing two multivariate distributions based on adjacency［J］. Journal of the Royal Statistical Society:Series B:Statistical Methodology，2005，67(4):515-530.

［5］Aslan B，Zech G. New test for the multivariate two-sample problem based on the concept of minimum energy［J］. Journal of Statistical Computation and Simulation，2005，75(2):109-119.

［6］CHEN H，Friedman J H. New graph-based two-sample tests for multivariate distributions［BE/OL］.2013-07-15. http://arxiv.org/abs/1307.629.

［7］CHEN L，DOU W W，QIAO Z.Ensemble subsampling for imbalanced multivariate two-sample tests［J］.Journal of the American Statistical Association，2013，108(504):1308-1323.

［8］王永吉，楊慧中.基于K-近鄰的支持向量機多模型建模［J］.江南大學學報:自然科學版，2010，9(1):7-10.

WANG Yongji，YANG Huizhong，Compositional support vector machine model based on improved k-kearest neighbor algorithm［J］.Journal of Jiangnan University:Natural Science Edition，2010，9(1):7-10.(in Chinese)

［9］孫曉燕，張化祥，計華.用于不均衡數據集分類的KNN 算法［J］.計算機工程與應用，2011，47(28):143-145.

SUN Xiaoyan，ZHANG Huaxiang，JI Hua. Improved KNN algorithm in classification of imbalanced data set［J］. Computer Engineering and Applications，2011，47(28):143-145.(in Chinese)

［10］石靜，邱立坤，王菲，等.相似詞獲取的集成方法［C］//孫茂松，陳群秀. 中國計算語言學研究前沿進展(2009-2011)，北京:清華大學出版社，2011:277-283.

［11］滕云龍，師奕兵.GPS 載波相位測量數據的時間序列分析建模研究［J］.電子測量與儀器學報，2009，29(9):18-22.

TENG Yunlong，SHI Yibing.Study on modeling of time series analysis for GPS carrier phase measurement data［J］. Journal of Electronic Measurement and Instrument，2009，23(9):18-22.(in Chinese)

［12］張毅，劉毅堅，羅元.一種基于參數優化C-SVM 的腦電信號分類方法及應用［J］.重慶郵電大學學報:自然科學版，2014，26(1):131-136.

ZHANG Yi，LIU Yijian，LUO Yuan. A parameter optimized C-SVM approach for EEG classification and its application［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2014，26(1):131-136.(in Chinese)

［13］王國慶，張建云，劉九夫，等.中國不同氣候區河川徑流對氣候變化的敏感性［J］.水科學進展，2011，22(3):307-314.

WANG Guoqing，ZHANG Jianyun，LIU Jiutian，et al. The sensitivity of runoff to climate change in different climatic regions in China［J］.Advances in Water Science，2011，22(3):307-314.(in Chinese)

［14］袁飛.考慮植被影響的水文過程模擬研究［D］.南京:河海大學，2006.

［15］曹宇峰，劉高峰，王慧敏.基于Mann-Kendall 方法的淮河流域降雨量趨勢特征研究［J］.安徽師范大學學報:自然科學版，2014，37(5):477-480.

CAO Yufeng，LIU Gaofeng，WANG Huimin. Huaihe river basin rainfall trend characteristics research based on Mann-Kendall method［J］.Journal of Anhui Normal University:Natural Science，2014，37(5):477-480.(in Chinese)