泛Kennard-Stone算法的數(shù)據(jù)集代表性度量與分塊采樣策略

武晴瀅，祝震予，吳劍鳴，徐昕

（復(fù)旦大學(xué)化學(xué)系,上海 200438）

在大數(shù)據(jù)驅(qū)動(dòng)的機(jī)器學(xué)習(xí)建模中，針對擬解決的問題，搜集或主動(dòng)采集足量（或盡可能足量）的數(shù)據(jù)樣本，以組成建模所需的數(shù)據(jù)集，是進(jìn)行機(jī)器學(xué)習(xí)不可或缺的重要環(huán)節(jié)［1］.Kennard-Stone（KS）算法（原文稱之為Computer-aided design of experiments，CADEX）于1969年由Kennard和Stone［2］提出，被證明是優(yōu)秀的數(shù)據(jù)集分割方法［3，4］，迄今仍在廣泛應(yīng)用［5～8］.為了滿足不同應(yīng)用需求，在傳統(tǒng)KS算法基礎(chǔ)上改進(jìn)的新算法不斷涌現(xiàn)，如用馬氏距離代替歐氏距離的MDKS（Kennard-Stone algorithm based on Mahalanobis distance）［9］，將因變量Y計(jì)入歐氏距離的SPXY（Sample set Partitioning based on jointX-Ydistances）［10］和考慮自變量和因變量權(quán)重的SSWD（Subset Selection based on Weightedxandyjoint Distances）［11］，進(jìn) 一 步 將 核 函 數(shù) 距 離 代 替 歐 氏 距 離 的KSPXY（Kernel distance-based Sample set Partitioning based on jointX-Ydistances）［12］、考慮因變量預(yù)測誤差分布的SPXYE（Sample set Partitioning based on jointX-Y-Edistances）［13］、考慮特征向量間余弦距離的HSPXY（Sample subset Partition method based on joint Hybrid correlation and diversityX-Ydistances）［14］，以及針對時(shí)間數(shù)據(jù)流的KSB（Kennard-Stone Balance Algorithm）［15］.在上述方法中，除KSB外，其它方法可以看作為在傳統(tǒng)KS算法的特征空間“距離”本身挖掘算法在不同應(yīng)用方面的潛力.如，在歐氏距離、馬氏距離和余弦距離之外，還可以引入切比雪夫距離、閔可夫斯基距離及半正矢距離等［15］，以期從原有數(shù)據(jù)集中獲得盡可能高代表性的子集，以適用不同的應(yīng)用需求.但這些方法采出的樣本集是否具有足夠的代表性，由于缺乏可實(shí)際量化的標(biāo)準(zhǔn)，只能依靠最終的建模效果進(jìn)行事后評價(jià).本文從建模所需數(shù)據(jù)集的完備性入手，嘗試探討采樣集的代表性，提出可定量化采樣數(shù)據(jù)集代表性的一種通用性度量.此外，由于KS算法及其變種（泛KS算法）的計(jì)算復(fù)雜度為O(K3)，限制了它們在大型數(shù)據(jù)集上采樣的效率.為此，提升算法效率有利于提高其可用性，同時(shí)采用分塊采樣策略，可以顯而易見地提升采樣效率.

1 基本概念與條件設(shè)定

1.1 數(shù)據(jù)集的完備性

當(dāng)所組建的數(shù)據(jù)集對于擬采用的機(jī)器學(xué)習(xí)模型是“足量”的，意味著它們能夠以足夠的密度分布于模型的所有特征空間，可以完整地反映模型所需的各種數(shù)據(jù)特征.假設(shè)問題可由J個(gè)線性無關(guān)的特征來表示，即這些特征構(gòu)成J維的希爾伯特空間.若完整描述某個(gè)特征維度所需的最少數(shù)據(jù)量為N（jj=1～J），將該維度劃分出Nj個(gè)空間區(qū)域，每個(gè)區(qū)域保有一個(gè)數(shù)據(jù)樣本，相鄰空間區(qū)域的樣本盡量遠(yuǎn)離，這一數(shù)據(jù)集可稱為完備集.此時(shí)，整個(gè)數(shù)據(jù)集所需的數(shù)據(jù)量至少為，同時(shí)要求每個(gè)樣本必須分屬不同的希爾伯特空間網(wǎng)格.

當(dāng)每個(gè)特征維度僅有0和1兩種可能（即二分法），則這個(gè)模型為最簡單的模型，其完備集的樣本量為2J.倘若每個(gè)特征維度都是線性的，不考慮數(shù)據(jù)本身誤差的情況，其完備集的樣本量最小為2J或3J（Nj=3是為了避免同一維度中兩點(diǎn)過于接近導(dǎo)致數(shù)值上擬合斜率誤差過大）.當(dāng)數(shù)據(jù)本身可能有一定誤差（但誤差較小的情況），且每個(gè)特征維度為線性或近似線性的，則每個(gè)特征維度通常至少需要5個(gè)點(diǎn)，則完備集的數(shù)量至少要5J.當(dāng)問題比較復(fù)雜，其特征維度不能以線性描述，尤其是無法預(yù)知其具體的非線性函數(shù)時(shí)（這也是采用非線性神經(jīng)元的神經(jīng)網(wǎng)絡(luò)模型經(jīng)常遇到的情況），要完整表示這個(gè)維度的趨勢，所需的樣本點(diǎn)數(shù)量則難以估計(jì)，急劇降低了獲取完備集的可能性.針對此情況，為了獲取盡可能完備的數(shù)據(jù)集，首先要確定每一個(gè)維度的上下界（適用范圍），然后進(jìn)行必要的網(wǎng)格劃分.原理上，網(wǎng)格的密度需與擬研究問題的模型梯度的變化量成正比.由于事實(shí)上大多情況下梯度變化量是預(yù)先不可知的，因此只能在建模初期，在可承受的范圍盡量提高網(wǎng)格密度.在初步建模擬合后，根據(jù)擬合模型中各區(qū)域的梯度變化量以及擬合誤差調(diào)整網(wǎng)格密度，實(shí)施補(bǔ)采樣，進(jìn)行再擬合，依此迭代至收斂.最終收斂得到的希爾伯特空間網(wǎng)格，暫且稱之為精細(xì)網(wǎng)格，也即只要每個(gè)精細(xì)網(wǎng)格中保有一個(gè)數(shù)據(jù)點(diǎn)，所組成的數(shù)據(jù)集為該模型所需的完備集.

1.2 數(shù)據(jù)集的可代表性

當(dāng)一個(gè)數(shù)據(jù)集覆蓋了所有的精細(xì)網(wǎng)格，即其理論上擬解決問題的完備集是該數(shù)據(jù)集的子集，則可稱此數(shù)據(jù)集是“足量”的.由前述可知，對于高特征維度的復(fù)雜模型，“足量”數(shù)據(jù)的獲取是極其艱難的任務(wù).在很多情況下，由于沒有條件實(shí)施系統(tǒng)網(wǎng)格化數(shù)據(jù)采集（如，難以確定精細(xì)網(wǎng)格，或精細(xì)網(wǎng)格數(shù)量非常龐大，或難以按擬定的特征獲取數(shù)據(jù)），只能根據(jù)實(shí)際可獲得的數(shù)據(jù)進(jìn)行建模.當(dāng)一個(gè)數(shù)據(jù)集對于擬解決問題時(shí)“足量”，意味著該數(shù)據(jù)集包含一個(gè)完備集，同時(shí)還可能存在數(shù)據(jù)冗余，即某些精細(xì)網(wǎng)格區(qū)域存在不止一個(gè)數(shù)據(jù)點(diǎn)，甚至存在兩兩相同（或極其相似/近）的數(shù)據(jù)點(diǎn).如果存在大量冗余數(shù)據(jù)，不僅增加了模型擬合的代價(jià)，冗余度不均也會給擬合模型帶來偏差.由于擬合過程中，一般的損失函數(shù)進(jìn)行誤差統(tǒng)計(jì)時(shí)，對每個(gè)樣本是同等對待的，冗余度越大的網(wǎng)格空間對最終模型的貢獻(xiàn)也就越大.最終擬合模型對冗余度大的網(wǎng)格空間內(nèi)的數(shù)據(jù)點(diǎn)的擬合精度要高于數(shù)據(jù)稀疏的區(qū)域.非系統(tǒng)性網(wǎng)格化數(shù)據(jù)采集獲得的數(shù)據(jù)集，非“足量”卻又包含大量冗余甚至重復(fù)數(shù)據(jù)是很普遍的現(xiàn)象.

在此種普遍情況下，從已有數(shù)據(jù)集G抽提出盡可能完備的子集G（rGr?G），即Gr占據(jù)G所分布的所有精細(xì)空間網(wǎng)格，使得Gr可以完全代表G，有利于以最小的代價(jià)建立合理的模型.假設(shè)一個(gè)數(shù)據(jù)集有K個(gè)數(shù)據(jù)點(diǎn)，第k點(diǎn)（1≤k≤K）包含了J個(gè)線性無關(guān)的特征xkj(1≤j≤J)組成的向量Xk，和對應(yīng)的預(yù)期結(jié)果Yk.每個(gè)特征分別有相應(yīng)的上界（Uj)和下界(Dj)，即xkj∈[Dj，Uj]或xkj∈(Dj，Uj).當(dāng)精細(xì)網(wǎng)格的分布是均勻的（或每個(gè)特征維度均為近線性，或已變換成近線性的），相鄰網(wǎng)格之間的距離ε是恒定的.當(dāng)ε已知，可以應(yīng)用泊松盤采樣方法［16，17］，從G抽提出G（r也可應(yīng)用KS采樣算法，并設(shè)定采樣距離r小于ε時(shí)終止采樣）.事實(shí)上，擬解決問題在被理解透徹之前，精細(xì)空間網(wǎng)格的劃分不可知，因此ε也不可知.當(dāng)無法確定合適的ε時(shí)，也就無法應(yīng)用泊松盤采樣方法獲取.當(dāng)ε越大時(shí)，即空間網(wǎng)格越大，對整個(gè)特征空間的描述就越粗線條，反之越精細(xì).因此，可以以特征空間中距離r最遠(yuǎn)的兩個(gè)數(shù)據(jù)點(diǎn)開始，不斷逐級縮小采樣距離r，同時(shí)確保所有已采樣本間的距離均不小于r，來實(shí)施采樣獲得Gr.KS算法等效地實(shí)現(xiàn)了這個(gè)過程.需要注意的是，經(jīng)典的KS算法不是以r的大小為終止采樣的判據(jù)，而往往是以設(shè)定的擬采樣數(shù)目來終止采樣.當(dāng)不選擇r為0的情況，KS算法就排除了G中所有相同的數(shù)據(jù)點(diǎn).當(dāng)兩個(gè)數(shù)據(jù)點(diǎn)距離小于ε時(shí)，這兩個(gè)數(shù)據(jù)點(diǎn)被認(rèn)為是相似或互為冗余的，設(shè)定r=ε時(shí)終止KS采樣，則可以篩除G中所有r＜ε的冗余數(shù)據(jù).因此，選擇所有兩兩之間的距離r≥ε的數(shù)據(jù)組成的Gr可以完全代表G.

2 算法與改進(jìn)

2.1 經(jīng)典KS算法

經(jīng)典KS算法提供了從一個(gè)含等構(gòu)數(shù)據(jù)的數(shù)據(jù)集G中選取預(yù)定數(shù)目樣本的方法.這個(gè)數(shù)據(jù)集要求所包含的每個(gè)數(shù)據(jù)為包含n個(gè)特征的一維向量.為了確保篩選的樣本子集分布均勻，對于包含K個(gè)樣本的數(shù)據(jù)集G，Kennard和Stone［2］設(shè)計(jì)了以下多步操作：

（1）首先計(jì)算兩兩樣本之間的歐氏距離dp，q，構(gòu)造所有數(shù)據(jù)樣本間的距離矩陣.

式中：Xp和Xq分別為樣本p和q的特征.這部分的計(jì)算復(fù)雜度為O(K2n).

為了保證計(jì)算獲得的歐氏距離在數(shù)值上的合理性，一般在進(jìn)行本步驟前，需將整個(gè)數(shù)據(jù)集的每個(gè)特征分別進(jìn)行歸一化，以確保計(jì)算歐氏距離過程中每種特征的貢獻(xiàn)一致.對于不同的KS變種，如SSWD［11］，可以根據(jù)各特征的重要性程度統(tǒng)一調(diào)整不同特征的權(quán)重大小.

（2）選出其中距離最大的兩個(gè)樣本（k=2）.

（3）對于每個(gè)剩余樣本［共(K-k)個(gè)］，確定其與已選k個(gè)樣本之間的最短距離.

然后，選擇這些最短距離中相對最長的距離rk+1=max{di，min，…，dK-k，min}所對應(yīng)的樣本，移入已采集的樣本池.

（4）重復(fù)步驟（3），直至所采出的樣本個(gè)數(shù)達(dá)到事先確定的數(shù)目為止.

步驟（2）～（4）的計(jì)算復(fù)雜度為O(K3).KS采樣的結(jié)果與數(shù)據(jù)集的樣本順序無關(guān).

除了KS算法及其各種改進(jìn)版本外，還有許多方法用以從樣本庫中選擇具有代表性的子集，如隨機(jī)抽樣（RS）.基于能量距離最小的支持點(diǎn)（Support Point）的SPlit［18］、PVLOO（Posterior Variance of Leave-One-Out cross-validation）［19］、Kohonen自 組 織 映 射［20］、D-optimum［21］、OptiSim（Optimizable K-Dissimilarity Selection）［22］、IOS（Isolation forest Outlier detection and Subset selection）［23］和GDBSCAN（Generalized Density Based Spatial Clustering of Applications with Noise）［24］等.RS憑借著其簡單易用性，無人為偏差，被廣泛應(yīng)用于樣本分割.當(dāng)數(shù)據(jù)集G的均勻性和冗余度很高時(shí)，通過RS采集出的GRS具備包含Gr的可能性.在數(shù)據(jù)分布均勻的情況下，冗余度越高，可能性越大.然而GRS不能保證對G的代表性，尤其存在數(shù)據(jù)密度分布不均衡（如部分重要網(wǎng)格區(qū)域數(shù)據(jù)點(diǎn)稀疏）的情況.當(dāng)選出的數(shù)據(jù)集不包含部分邊界上的樣本，很可能導(dǎo)致非線性模型在邊界區(qū)域產(chǎn)生巨大的偏差，使得適用范圍受到壓縮且未能提前預(yù)知.泛KS算法是除RS以外最為常用的一類采樣算法，它們在機(jī)制上首先保證了數(shù)據(jù)集特征定義域邊界上的樣本被優(yōu)先采集，已采集樣本相互間盡可能遠(yuǎn)離，從而達(dá)到均勻篩選樣本的目的，在諸多應(yīng)用中被證明在樣本分割方面具有優(yōu)勢［3，4，7］.

2.2 采樣集代表性度量

由經(jīng)典KS采樣算法可知，首先選擇的2個(gè)距離最大的樣本間的距離r2=rmax.第k個(gè)樣本被選中時(shí)，其與已選擇的數(shù)據(jù)集中所有k－1個(gè)數(shù)據(jù)點(diǎn)的最小距離為rk.按此定義，不存在r1.當(dāng)rk=0，則余下的K－k個(gè)數(shù)據(jù)點(diǎn)均為重復(fù)的數(shù)據(jù).因此，對于一個(gè)給定的數(shù)據(jù)集G，令為一個(gè)常數(shù).

當(dāng)上述精細(xì)網(wǎng)格不可知，且數(shù)據(jù)集G中不存在絕對等價(jià)的數(shù)據(jù)樣本（即rK＞0）時(shí)，經(jīng)KS算法采出的k個(gè)樣本組成的數(shù)據(jù)集Gk對于G的代表性的判定，TK提供了一個(gè)度量，令Pk=TkTK×100%，則Pk可以作為一種可定量化的度量來表示Gk對于G的代表程度.由上述可知，當(dāng)rk=0時(shí)，Tk=TK，即Gk為G完備的子集，可以完整地代表G，此時(shí)Pk=100%.當(dāng)Tk＜TK，即rk＞0時(shí)，Pk＜100%.若rk＞ε，此時(shí)，Gk不是G完備的子集，只能部分代表G，其代表性可用Pk來近似表示.對于給定的數(shù)據(jù)集G，當(dāng)P=0和P=100%時(shí)是精確的.從中選取Gk子集，其Pk值的大小可以反映數(shù)據(jù)集代表程度的高低.盡管P不滿足加和性，但對于一個(gè)給定的數(shù)據(jù)集，P的相對大小具有可比性.從定義而言，由于上述提到的“距離”并不限于歐氏距離，因此，P值不僅可以用于傳統(tǒng)的KS算法，也同樣適用于各種不同距離的泛KS算法.

為了測試P值大小的實(shí)際效果，選取簡正振動(dòng)采樣的5400個(gè)甲烷分子結(jié)構(gòu)［25］中的所有21600個(gè)碳?xì)滏I組成的數(shù)據(jù)集為例.為了方便，每個(gè)碳?xì)滏I僅用2個(gè)特征來描述，第1個(gè)特征f1為每個(gè)碳?xì)滏I鍵長的倒數(shù)，以原子單位表示，即a-10；第2個(gè)特征f2為該鍵的鍵環(huán)境，為考慮其它化學(xué)鍵對該鍵的影響，以其中，i=1，2，3分別為其它3個(gè)碳?xì)滏I，θi為該鍵分別與它們的夾角）表示.進(jìn)行KS采樣前，分別將兩個(gè)特征歸一化至0～1區(qū)間，數(shù)據(jù)分布如圖1（A）所示.

在這個(gè)數(shù)據(jù)集所有21600個(gè)碳?xì)滏I中，僅有2個(gè)樣本間歐氏距離為0（小于10-6），冗余度極低，同時(shí)，也表明不存在兩個(gè)完全等價(jià)的甲烷分子結(jié)構(gòu).當(dāng)設(shè)ε=10-6，如要求Pk=100%，則采樣數(shù)至少為21599.按照KS算法，從頭開始選擇距離最大的點(diǎn)，直到最后將所有的點(diǎn)選出，即k=K.將rk對k作圖得到圖2.

Fig.1 Feature distribution(2D)maps of the methane-based C—H bond dataset

當(dāng)P=10%時(shí)，KS選出61個(gè)點(diǎn).如表S1（見本文支持信息）中最右列的散點(diǎn)圖顯示，這部分點(diǎn)均勻分布在圖的各個(gè)區(qū)域，鄰近的兩點(diǎn)間距也較均勻，同時(shí)保留了圖1（A）中散點(diǎn)的大致邊界，此時(shí)，rk=0.09462.而根據(jù)RS采樣，同樣采出61個(gè)點(diǎn)，鄰近的兩點(diǎn)間距大小不均，無法看出整體邊界.當(dāng)P=20%時(shí)，KS選出285個(gè)點(diǎn)，鄰近的兩點(diǎn)間距仍較均勻，且r明顯更小(rk=0.03858).而RS采出的285個(gè)點(diǎn)組成的圖與原圖［圖1（A）］對比，可以看出，它著重采出原圖密度較大的區(qū)域.隨著采樣點(diǎn)逐步增加，P值相應(yīng)升高，上述趨勢表現(xiàn)一致.KS采樣過程的采樣距離從大到小選取樣本，事實(shí)上，將優(yōu)先選中處于最遠(yuǎn)離中心的邊界樣本，在采樣樣本數(shù)較小的情況下，已能還原數(shù)據(jù)集的輪廓與范圍，并表現(xiàn)出均勻的數(shù)據(jù)分布.在采樣距離逐步縮小的過程，在維持均勻的數(shù)據(jù)分布的同時(shí)，逐步加大樣本分布的密度.而RS采樣隨著采樣的樣本量增加，逐步反映著原數(shù)據(jù)集的密度分布，無法確保顧及數(shù)據(jù)集的邊界，以及樣本相對稀疏的區(qū)域.當(dāng)P=50%時(shí)，KS選出2431個(gè)點(diǎn)所組成的圖［圖1（C）］很好地還原了數(shù)據(jù)集的完整邊界與內(nèi)部細(xì)節(jié)，此時(shí)rk=0.01041，實(shí)際采樣比例僅為11.25%，顯示出非常高的采樣效果，相比RS以同樣采樣數(shù)采出的圖［圖1（B）］，其具有更高的還原度與可識別度.從P=60%起至P=90%，rk分別為0.00754，0.00545，0.00387和0.00249.因此，對于具體采樣問題，也可以根據(jù)rk的大小來判斷采樣是否充分.由數(shù)據(jù)集的精細(xì)網(wǎng)格尺寸ε可知，當(dāng)rk≤ε，可以認(rèn)定采樣集的代表性為100%，則特別地，當(dāng)數(shù)據(jù)集存在冗余數(shù)據(jù)，則冗余部分的樣本在P=100%之前，不會被選取，因此，可以根據(jù)P值或rk的數(shù)值來剔除冗余度.從這個(gè)意義上，P值或rk都可用來確定所需采樣數(shù)k.

2.3 KS采樣算法效率的提高

盡管，與RS相比，KS采樣算法可以以較小比例的采樣數(shù)獲取較高代表性的采樣集Gk.但是，KS采樣算法的計(jì)算復(fù)雜度不是線性的.它的第一個(gè)主要步驟（1），需要計(jì)算所有樣本的兩兩間距離（不限于歐氏距離、馬氏距離和其它距離），計(jì)算復(fù)雜度為O(K2n).對于一個(gè)給定的等構(gòu)的數(shù)據(jù)集，特征數(shù)量n是固定的，n融入前置因子，計(jì)算復(fù)雜度為O′(K2).當(dāng)數(shù)據(jù)集樣本量K很大時(shí)，尤其是大數(shù)據(jù)時(shí)代的數(shù)據(jù)集往往很大，導(dǎo)致此步驟的計(jì)算量特別龐大.該步驟中的距離計(jì)算相互沒有關(guān)聯(lián)，容易分布式并行實(shí)現(xiàn).而接下來的篩選過程［第二步驟：（2）～（4）］，需要根據(jù)rk從大到小依次采樣，而且rk的數(shù)值需要等第k-1個(gè)樣本確定后才能確定，因此不能對樣本量K實(shí)施并行算法，只能在每個(gè)具體樣本的篩選過程中進(jìn)行局部算法并行化，降低了算法的并行效率.此外，數(shù)據(jù)集樣本量的大小在加劇算法計(jì)算量的同時(shí)也加大了對內(nèi)存的需求.當(dāng)內(nèi)存不足以存放所有樣本的兩兩距離矩陣時(shí)，算法的效率還將受磁盤讀寫速度的瓶頸影響而急劇降低，乃至失去可用價(jià)值.

注意到篩選過程中存在重復(fù)比較大小的過程.對于某個(gè)已選樣本i，與(K-k)個(gè)剩余樣本間的最短距離di，min在上一個(gè)采樣（第k個(gè)）循環(huán)中已經(jīng)比較過{di，1，…，di，k}中的大小.因此，在內(nèi)存許可的情況下，對該距離向量進(jìn)行動(dòng)態(tài)維護(hù)，實(shí)際只需對上一循環(huán)的di，min與di，(k+1)進(jìn)行比較，往往可以在每個(gè)循環(huán)中減少O(K)量級的求最小值的計(jì)算量，使計(jì)算復(fù)雜度由O(K3)降至O(K2).最近，在空間填充設(shè)計(jì)（Space-filling design）領(lǐng)域的算法中，也報(bào)道了運(yùn)用動(dòng)態(tài)規(guī)劃避免重復(fù)比較大小的類似做法［26］.結(jié)果使KS采樣算法的前后兩個(gè)步驟的計(jì)算復(fù)雜度均為O′(K2).

此外，對于超大樣本量數(shù)據(jù)集，O′(K2)仍為難以承受的情況，可以采取分別處理的折中做法，即，將整個(gè)數(shù)據(jù)集G切分成較小的S個(gè)子集Gs(s=1，2，…，S)，每個(gè)子集分別實(shí)施KS采樣，再將采樣后的數(shù)據(jù)集匯總.這不僅降低了計(jì)算兩兩距離的復(fù)雜度O′(K2)中的K，同時(shí)，也減少了后續(xù)的從最短距離中取最大值的比較過程［2.1節(jié)步驟（3）和（4）］中的K.由于實(shí)際每個(gè)子集的樣本量最大值受到計(jì)算資源的限制，以及計(jì)算效率的考慮，要求K/S有限.因此，隨著K增大，子集數(shù)量S必然相應(yīng)增大以確保K/S有限，最終總的實(shí)際計(jì)算復(fù)雜度為

接下來，需要考慮這種分塊采樣策略能否保證最終采樣集的代表性.由于G切分成若干個(gè)子集Gs，不同子集間的樣本，其特征空間大概率存在交錯(cuò).可以預(yù)見在此情況下，從一個(gè)子集Gs中采出的，與相鄰特征空間的另一個(gè)子集Gs′中采出的Gsk′，存在樣本間特征距離小于各子集采樣時(shí)的最小rk.基于此，可按數(shù)據(jù)特征空間劃分子集，或簡單地將數(shù)據(jù)集G按照某一主要特征維度排序后再切分，以避免子集間的特征空間交錯(cuò).但仍存在相鄰子集的特征空間相互接壤，由于子集采樣過程中，特征空間邊界的數(shù)據(jù)點(diǎn)往往被優(yōu)先采集，使得處于特征空間相鄰的子集中采樣點(diǎn)存在彼此距離較近的情況.在實(shí)際應(yīng)用過程中，即使存在少量rk較小的數(shù)據(jù)，僅略微提高了數(shù)據(jù)冗余度，對模型建立的影響較小，甚至可以忽略.從更嚴(yán)格的要求上，如果在合并后的Gk集基礎(chǔ)上再做一輪KS采樣，足以排除合并導(dǎo)致的部分?jǐn)?shù)據(jù)間存在rk較小的情況，但仍需面對合并后的Gk集進(jìn)行再采樣的計(jì)算消耗.另外，要對大型數(shù)據(jù)集按特征空間實(shí)施系統(tǒng)性切分，所需要的排序過程也是非常耗時(shí)的.因此隨機(jī)劃分，或直接按已有的順序切分成多個(gè)子集，再分別進(jìn)行KS采樣，較為現(xiàn)實(shí).

3 實(shí)驗(yàn)部分

為了驗(yàn)證以這種方式進(jìn)行分塊KS采樣的有效性，基于文獻(xiàn)［10，12，14］中常用的柴油近紅外光譜數(shù)據(jù)集［27］，采用偏最小二乘（Partial least-squares，PLS）回歸方法［28］構(gòu)建通過近紅外光譜預(yù)測柴油質(zhì)量特性的模型，用于檢驗(yàn)對比.在該數(shù)據(jù)集中，近紅外光譜采集范圍為750～1550 nm，狹縫寬度為2 nm，則每個(gè)數(shù)據(jù)樣本包含401個(gè)光譜特征.選擇每種柴油的50%餾出溫度（bp50）、15℃時(shí)的密度（d4052）和總芳烴含量質(zhì)量百分比（Total）3個(gè)質(zhì)量特性作為測試對象.在篩除所有空缺或不完整的數(shù)據(jù)點(diǎn)后，數(shù)據(jù)集的基礎(chǔ)統(tǒng)計(jì)信息列于表1.

Table 1 Dataset statistics of three diesel fuel propertiesa

針對這個(gè)PLS回歸實(shí)驗(yàn)，應(yīng)用KS算法的目的是將數(shù)據(jù)集劃分為校準(zhǔn)集和預(yù)測集兩個(gè)子集.通過調(diào)整校準(zhǔn)集占總數(shù)據(jù)集的比例，來檢驗(yàn)不同代表性的數(shù)據(jù)集的建模能力.其中校準(zhǔn)集用于估計(jì)其潛在變量的最佳數(shù)量，來確定偏最小二乘模型的復(fù)雜度，并建立校準(zhǔn)模型.預(yù)測集用于評估所構(gòu)建校準(zhǔn)模型的預(yù)測能力，采用擬合優(yōu)度（R2）來評估模型的預(yù)測效果.

為了對比不同數(shù)據(jù)集分塊方案的效果，以總數(shù)據(jù)集直接KS采樣的建模結(jié)果為基準(zhǔn)，采取按原始數(shù)據(jù)順序劃分子集和隨機(jī)順序劃分子集兩種模式，為了避免隨機(jī)算法的偶然性，平行做A，B，C 3次隨機(jī)分集.基于樣本總數(shù)量為385～392之間，每個(gè)分塊子集最多60個(gè)樣本.

從表2可知，由于PKS為按KS算法全采樣后，特征距離rk從大到小排列所加和獲得的Tk值與總TK值的比，因此，PKS必定大于等于其它方式所選集的P值.此外，由于Sequential是按原特征既定順序排列的，避免了子集間數(shù)據(jù)點(diǎn)的特征空間交錯(cuò)，因此，所得P值要大于等于隨機(jī)排序后再分塊（Random-A/B/C）的情況.從最終的各模型擬合優(yōu)度R2可見，大小趨勢也與P值基本正相關(guān)，進(jìn)一步反映了P值設(shè)計(jì)的合理性.分塊采樣后，各擬合模型的擬合優(yōu)度R2sequential和R2ramdom-A/B/C，與整體KS篩選得到的樣本構(gòu)造出的PLS回歸模型擬合優(yōu)度R2差值大致保持在0.01以內(nèi).結(jié)果表明，分塊篩選的方式可以在提高篩選效率的同時(shí)，合理地采出具有合理代表性的樣本集.從具象化的結(jié)果，以及PLS回歸測試的結(jié)果，均能反映出P值的定量化效果.但它也存在不足，即，P值盡管在0和100%是精確的，中間數(shù)值僅對單個(gè)數(shù)據(jù)集的KS采樣結(jié)果有相對意義，而不具備數(shù)學(xué)意義上的加和性.關(guān)于數(shù)據(jù)集“代表性”度量的提法，基于分類目的的算法關(guān)注其數(shù)據(jù)點(diǎn)在聚類區(qū)間的分布量［29］，而本文更關(guān)注回歸算法所需的數(shù)據(jù)集的完備性.

Table 2 Performance tests of different slicing KS sampling strategies

此外，由于KS類算法的計(jì)算復(fù)雜度為O(K3)，與其樣本總數(shù)K緊密相關(guān)，進(jìn)行超大數(shù)據(jù)樣本量的篩選時(shí)，其算法效率限制了其應(yīng)用.針對此問題，對KS采樣的篩選過程施行動(dòng)態(tài)規(guī)劃，可將原本的計(jì)算復(fù)雜度從O(K3)降至O′(K2)；提出分塊采樣的解決方案，進(jìn)一步將計(jì)算復(fù)雜度從O′(K2)降至O′′(K)，并通過PLS回歸測試，達(dá)到了預(yù)期效果，在提高篩選效率的同時(shí)，合理采出具有合理代表性的樣本集.

4 結(jié) 論

在大數(shù)據(jù)驅(qū)動(dòng)的機(jī)器學(xué)習(xí)建模過程中，由于特征空間維度J往往不是一個(gè)很小的數(shù)，實(shí)際數(shù)據(jù)集要覆蓋所有特征空間精細(xì)網(wǎng)格幾乎是不可能完成的任務(wù).從實(shí)際盡可能匯集到的數(shù)據(jù)集中篩選出能夠代表該數(shù)據(jù)集的訓(xùn)練集（或校準(zhǔn)集），是機(jī)器學(xué)習(xí)建模成功的關(guān)鍵基礎(chǔ).傳統(tǒng)的KS采樣算法，及用各種定義的“距離”替代原有的歐氏距離的改進(jìn)版本，為不同應(yīng)用領(lǐng)域的樣本篩選提供了強(qiáng)有力的算法基礎(chǔ).這些方法原理上均可以篩除數(shù)據(jù)集中的重復(fù)樣本，當(dāng)可以定義精細(xì)網(wǎng)格間距ε時(shí)，設(shè)定最小采樣距離rk≥ε可以篩除冗余樣本，以提高建模效率，并降低數(shù)據(jù)密度分布不均帶來的偏差.由于數(shù)據(jù)集代表性迄今仍未有一個(gè)定量化的度量，無法在建模前判斷采樣是否充分，本文提出了以實(shí)際采出的訓(xùn)練集（或校準(zhǔn)集）中每個(gè)樣本的采樣距離的和（或積分值）Tk與所有樣本的TK的比值P，來定量化表示泛KS算法抽提出的訓(xùn)練集所能代表總數(shù)據(jù)集的程度.針對KS復(fù)雜度問題，對KS采樣的篩選過程施行動(dòng)態(tài)規(guī)劃，并提出分塊采樣的解決方案，將計(jì)算復(fù)雜度從O(K3)降至O′′(K)，在提高篩選效率的同時(shí)，采出具有合理代表性的樣本集.同時(shí)，事先對數(shù)據(jù)集中至少一個(gè)特征維度進(jìn)行排序再分集，可有效避免各子集的特征空間交錯(cuò)導(dǎo)致采樣效果（匯總后的訓(xùn)練集的均衡度）降低.特別當(dāng)數(shù)據(jù)集中樣本分布極度不均衡的情況下，如大部分特征空間區(qū)域樣本稀疏，而極小部分特征空間存在大量冗余樣本時(shí)，預(yù)先按關(guān)鍵特征維度排序后再分集采樣，有助于保障分塊采樣策略的效果.如有必要，在計(jì)算資源許可的情況下（匯總的采樣集樣本數(shù)K不太大），對匯總的采樣集再實(shí)行一次KS采樣，可以獲得嚴(yán)格的采樣集.

支持信息見http://www.cjcu.jlu.edu.cn/CN/10.7503/cjcu20220397.