基于凸邊界的學(xué)習(xí)樣本抽取方法

顧依依 談詢滔 袁玉波

摘 要：?學(xué)習(xí)樣本的質(zhì)量和數(shù)量對(duì)于智能數(shù)據(jù)分類系統(tǒng)至關(guān)重要，但在數(shù)據(jù)分類系統(tǒng)中沒有一個(gè)通用的良好方法用于發(fā)現(xiàn)有意義的樣本。以此為動(dòng)機(jī)，提出數(shù)據(jù)集合凸邊界的概念，給出了快速發(fā)現(xiàn)有意義樣本集合的方法。首先，利用箱型函數(shù)對(duì)學(xué)習(xí)樣本集合中的異常和特征不全樣本進(jìn)行清洗;接著，提出數(shù)據(jù)錐的概念，對(duì)歸一化的學(xué)習(xí)樣本進(jìn)行錐形分割;最后，對(duì)每個(gè)錐形樣本子集進(jìn)行中心化，以凸邊界為基礎(chǔ)提取距離凸邊界差異極小的樣本構(gòu)成凸邊界樣本集合。實(shí)驗(yàn)在12個(gè)UCI數(shù)據(jù)集上進(jìn)行，并與高斯樸素貝葉斯（GNB）、決策樹（CART）、線性判別分析（LDA）、提升算法（AdaBoost）、隨機(jī)森林（RF）和邏輯回歸（LR）這六種經(jīng)典的數(shù)據(jù)分類算法進(jìn)行對(duì)比。結(jié)果表明，各個(gè)算法在凸邊界樣本集合的訓(xùn)練時(shí)間顯著縮短，同時(shí)保持了分類性能。特別地，對(duì)包含噪聲數(shù)據(jù)較多的數(shù)據(jù)集，如剖腹產(chǎn)、電網(wǎng)穩(wěn)定性、汽車評(píng)估等數(shù)據(jù)集，凸邊界樣本集合能使分類性能得到提升。為了更好地評(píng)價(jià)凸邊界樣本集合的效率，以樣本變化率和分類性能變化率的比值定義了樣本清洗效率，并用該指標(biāo)來客觀評(píng)價(jià)凸邊界樣本的意義。清洗效率大于1時(shí)說明方法有效，且數(shù)值越高效果越好。在脈沖星數(shù)據(jù)集合上，所提方法對(duì)GNB算法的清洗效率超過68，說明所提方法性能優(yōu)越。

關(guān)鍵詞：機(jī)器學(xué)習(xí);數(shù)據(jù)分類;樣本選擇;凸錐;邊界樣本

中圖分類號(hào)：?TP311.1

文獻(xiàn)標(biāo)志碼：A

Learning sample extraction method based on convex boundary

GU Yiyi， TAN Xuntao， YUAN Yubo*

School of Information Science and Engineering， East China University of Science and Technology， Shanghai 200237， China

Abstract：?The quality and quantity of learning samples are very important for intelligent data classification systems. But there is no general good method for finding meaningful samples in data classification systems. For this reason， the concept of convex boundary of dataset was proposed， and a fast method of discovering meaningful sample set was given. Firstly， abnormal and incomplete samples in the learning sample set were cleaned by box-plot function. Secondly， the concept of data cone was proposed to divide the normalized learning samples into cones. Finally， each cone of sample subset was centralized， and based on convex boundary， samples with very small difference from convex boundary were extracted to form convex boundary sample set. In the experiments， 6 classical data classification algorithms， including Gaussian Naive Bayes （GNB）， Classification And Regression Tree （CART）， Linear Discriminant Analysis （LDA）， Adaptive Boosting （AdaBoost）， Random Forest （RF） and Logistic Regression （LR）， were tested on 12 UCI datasets. The results show that convex boundary sample sets can significantly shorten the training time of each algorithm while maintaining the classification performance. In particular， for datasets with many noise data such as caesarian section， electrical grid， car evaluation datasets， convex boundary sample set can improve the classification performance. In order to better evaluate the efficiency of convex boundary sample set， the sample cleaning efficiency was defined as the quotient of sample size change rate and classification performance change rate. With this index， the significance of convex boundary samples was evaluated objectively. Cleaning efficiency greater than 1 proves that the method is effective. The higher the numerical value， the better the effect of using convex boundary samples as learning samples. For example， on the dataset of HTRU2， the cleaning efficiency of the proposed method for GNB algorithm is over 68， which proves the strong performance of this method.

Key words：?machine learning; data classification; sample selection; convex cone; boundary sample

0 引言

隨著社會(huì)的進(jìn)步，尤其是服務(wù)業(yè)的蓬勃發(fā)展，從數(shù)據(jù)中獲取有用信息的需求急劇增長。而數(shù)據(jù)分類是一個(gè)重要的挑戰(zhàn)，一個(gè)好的分類系統(tǒng)對(duì)該行業(yè)的發(fā)展至關(guān)重要。例如，餐飲業(yè)可以根據(jù)歷史消費(fèi)記錄對(duì)顧客進(jìn)行分類，給不同類別的顧客相應(yīng)的優(yōu)惠待遇，并推薦合適的菜肴;保險(xiǎn)公司可以根據(jù)家庭基本信息對(duì)家庭情況進(jìn)行分類，從而推薦合適的保險(xiǎn)，既能滿足用戶的自身需求，又能提高公司的效益。分類系統(tǒng)的核心是分類模型的選擇和構(gòu)建，訓(xùn)練集將參與到具體分類模型的構(gòu)建過程中。因此，訓(xùn)練集的質(zhì)量將很大程度上影響模型的預(yù)測效果，訓(xùn)練樣本對(duì)分類系統(tǒng)非常重要。

基于真實(shí)世界中海量數(shù)據(jù)的原因，如果系統(tǒng)直接將某行業(yè)內(nèi)產(chǎn)生的所有數(shù)據(jù)作為訓(xùn)練集，將會(huì)導(dǎo)致工作負(fù)載超重、資源浪費(fèi)、處理速度慢等狀況;并且來源于真實(shí)世界中的數(shù)據(jù)集通常包含缺失數(shù)據(jù)、異常數(shù)據(jù)和大量冗余數(shù)據(jù)，這將會(huì)降低訓(xùn)練集的質(zhì)量，從而降低數(shù)據(jù)分類的效率。為了提高訓(xùn)練集的質(zhì)量，需要一種樣本選擇方法來選擇具有代表性的樣本，這些選擇到的樣本可以代表原始數(shù)據(jù)集所包含的信息及其數(shù)據(jù)分布特征。并且，使用所選的代表性樣本作為訓(xùn)練集可以減小內(nèi)存開銷和降低分類模型的復(fù)雜度，從而加快建模速度。用于發(fā)現(xiàn)具有代表性樣本的樣本選擇方法

可以很好地處理因社會(huì)快速發(fā)展而產(chǎn)生的海量數(shù)據(jù)。

本文提出了邊界樣本的概念。事實(shí)上，它們是構(gòu)建分類模型的關(guān)鍵樣本，起著決定性的作用。對(duì)于分類任務(wù)，決策邊界附近的樣本最容易被誤分類，它們是最模糊的、有歧義的;但它們往往也包含更豐富的信息。本文提到的邊界樣本就是具有這種特性的樣本。本文通過數(shù)據(jù)錐的概念來發(fā)現(xiàn)它們，從而替代通過決策邊界找到這些樣本的方法。更具體地說，邊界樣本類似于支持向量機(jī)（Support Vector Machine， SVM）[1]中的支持向量。因此，本文所設(shè)計(jì)的方法是選擇邊界樣本。

本文主要工作有：1）提出了邊界樣本的概念，這些樣本對(duì)分類模型的構(gòu)建起著決定性的作用;2）采用數(shù)據(jù)錐的概念對(duì)子集進(jìn)行劃分，選擇邊界樣本;3）給出了效率分析公式，使用訓(xùn)練樣本集大小的比值與其對(duì)應(yīng)分類準(zhǔn)確率的比值來綜合分析該方法的可行性。

1 相關(guān)工作

對(duì)于分類性能的提升，一是針對(duì)訓(xùn)練集進(jìn)行處理，二是對(duì)分類模型進(jìn)行設(shè)計(jì)或改進(jìn)其性能。如今，已經(jīng)有非常多的流行技術(shù)，也不斷涌現(xiàn)出各種新興技術(shù)。

隨著數(shù)據(jù)量的急劇增長，并且時(shí)間和人工越來越寶貴，許多研究開始關(guān)注于樣本冗余和去重。它們的目標(biāo)是減少計(jì)算量及人工標(biāo)記開銷，并且盡可能地提高機(jī)器學(xué)習(xí)的準(zhǔn)確率。對(duì)于訓(xùn)練集的處理，主要有兩方面：樣本約簡和維度約簡。樣本約簡，即樣本選擇，通常分為數(shù)據(jù)壓縮和積極學(xué)習(xí)兩大類，其中可以使用有監(jiān)督、半監(jiān)督、無監(jiān)督策略。

有監(jiān)督和無監(jiān)督依賴于專家人工完成樣本選擇和去重的工作;而半監(jiān)督，如積極學(xué)習(xí)，可以減少人工標(biāo)注的開銷。

現(xiàn)在已經(jīng)有許多有效的樣本選擇和去重方法：如文獻(xiàn)[2]中提出了一種遺傳編程的方法來刪除重復(fù)記錄，它結(jié)合了從數(shù)據(jù)中提出的幾個(gè)不同的片段，以此為依據(jù)在庫中識(shí)別兩個(gè)條目是否為重復(fù)數(shù)據(jù);

文獻(xiàn)[3]中提出了一種新的框架FS-Dedup（Framework for Signature-based Deduplication），其技術(shù)核心是基于簽名的重復(fù)數(shù)據(jù)刪除，

在去重的工作中減輕了人工開銷，僅需標(biāo)記一個(gè)小的匹配對(duì)子集;文獻(xiàn)[4]在文獻(xiàn)[3]的基礎(chǔ)上進(jìn)行了改進(jìn)，提出了一種兩階段抽樣選擇策略T3S（two-stage sampling selection），在第二階段中迭代地進(jìn)行主動(dòng)選擇，從而去除第一階段中所得到的子集的中的冗余數(shù)據(jù)。以上幾種研究都是通用的樣本去重方法，不針對(duì)特定分類模型，在文獻(xiàn)[5-8] 中所提出的樣本選擇方法主要針對(duì)決策樹、神經(jīng)網(wǎng)絡(luò)及支持向量機(jī)。文獻(xiàn)[5]中提出了一種在模糊決策樹中根據(jù)最大歧義性來選擇樣本的方法。文獻(xiàn)[6]中將K-最近鄰分類算法中的數(shù)據(jù)約簡技術(shù)應(yīng)用于神經(jīng)網(wǎng)絡(luò)和支持向量機(jī)之前的預(yù)處理步驟。

數(shù)據(jù)約簡技術(shù)就是試圖通過選擇一些現(xiàn)有實(shí)例或生成新的訓(xùn)練實(shí)例來減小訓(xùn)練集的大小。支持向量機(jī)對(duì)于小樣本的分類任務(wù)效果出眾，但當(dāng)樣本量增加，達(dá)到數(shù)十萬的中等問題規(guī)模時(shí)，訓(xùn)練的時(shí)間和內(nèi)存需求激增。針對(duì)這一問題，文獻(xiàn)[7]中基于聚類的SVM模型進(jìn)一步探究每個(gè)聚成的簇里的聚集點(diǎn)和離散點(diǎn)，其中，聚集點(diǎn)被認(rèn)為不含支持向量從而被去除，保留包含支持向量的離散點(diǎn)。并且文獻(xiàn)[7]中利用Fisher判別比來確定每一個(gè)簇里聚集點(diǎn)和離散點(diǎn)之間的邊距，邊界的確定是基于計(jì)算數(shù)據(jù)點(diǎn)到簇中心的距離。

本文所設(shè)計(jì)的樣本選擇方法則希望可以應(yīng)用于多種分類器，不受分類器種類不同的影響，在加快訓(xùn)練速度和減少內(nèi)存開銷的同時(shí)，保持準(zhǔn)確率的不變或小幅下降。

文獻(xiàn)[8]中介紹了一種針對(duì)SVM處理大規(guī)模數(shù)據(jù)集時(shí)間長、泛化能力下降等問題的邊界樣本選擇方法，通過K均值聚類后，在每個(gè)簇中通過K近鄰算法剔除非邊界樣本以得到邊界樣本集。但此方法先要進(jìn)行K均值聚類，對(duì)于K的選擇有很大的不確定性;并且需要再通過一個(gè)K近鄰算法剔除非邊界樣本，增加了方法的復(fù)雜度;而且只針對(duì)于SVM分類器。而本文選擇的凸邊界樣本集無需調(diào)用其他算法，且設(shè)計(jì)目標(biāo)是適用于多種分類模型。

提升分類性能的預(yù)處理過程中，還有另一項(xiàng)重要的工作——維度約簡，即特征選擇。數(shù)據(jù)集維數(shù)急劇增加，特征選擇成為機(jī)器學(xué)習(xí)的必要步驟。

文獻(xiàn)[9]在分類任務(wù)的背景下，從理論和實(shí)驗(yàn)的角度研究了現(xiàn)有特征選擇技術(shù)之間的相似性，并且當(dāng)多個(gè)特征選擇方法組合時(shí)，對(duì)于所考慮的任務(wù)目標(biāo)能夠給出不同或互補(bǔ)的表示時(shí)才是有益的。

文獻(xiàn)[10]提出了一種基于類可分性策略和數(shù)據(jù)包絡(luò)分析的特征選擇方法，將類標(biāo)簽作為單獨(dú)的變量，在每個(gè)類標(biāo)簽上處理相關(guān)性和冗余;并使用超效率數(shù)據(jù)包絡(luò)分析計(jì)算特征在類標(biāo)簽上的得分，選擇最大得分的特征加入下一輪迭代的條件集中，不斷迭代地選擇最終的特征。本文的樣本選擇方法也采取了在每個(gè)類標(biāo)簽上處理數(shù)據(jù)的方法，從而進(jìn)行邊界樣本的選擇。文獻(xiàn)[11]使用了集成的思想進(jìn)行特征選擇能獲得更好的分類性能。

在具體的分類任務(wù)中，經(jīng)常會(huì)遇到不平衡分類數(shù)據(jù)的問題，即分類結(jié)果會(huì)傾向于多數(shù)群體，使得少數(shù)類被誤分。因此，現(xiàn)有許多研究都在致力于解決不平衡數(shù)據(jù)分類問題，提高分類模型的精度。文獻(xiàn)[12]中提出了一種改進(jìn)基于先驗(yàn)的綜合過采樣方法來提高不平衡數(shù)據(jù)集的分類靈敏度。分類模型的估計(jì)不僅受類分布的傾斜影響，而且由于數(shù)據(jù)的稀缺性導(dǎo)致對(duì)模型精度的估計(jì)較差。文獻(xiàn)[13]基于平滑自助重采樣技術(shù)，提出了一個(gè)統(tǒng)一的系統(tǒng)框架來處理類分布的傾斜影響和數(shù)據(jù)的稀缺性。

通常，K折驗(yàn)證技術(shù)可使不同分區(qū)的結(jié)果具有一定程度的獨(dú)立性，但每個(gè)折疊上的隨機(jī)劃分會(huì)導(dǎo)致訓(xùn)練子集和測試子集之間具有不同的數(shù)據(jù)分布導(dǎo)致數(shù)據(jù)位移的問題，尤其是在不平衡分類數(shù)據(jù)集中更加嚴(yán)重，從而導(dǎo)致對(duì)實(shí)際分類邊界的錯(cuò)誤學(xué)習(xí)，使少數(shù)類實(shí)例被誤分。文獻(xiàn)[14]中提出了分布最佳平衡分層交叉驗(yàn)證的方法，

首先使用一種特定的技術(shù)對(duì)數(shù)據(jù)進(jìn)行分區(qū)，并通過在不同的交叉驗(yàn)證折疊上設(shè)置每個(gè)分區(qū)上數(shù)量相近的樣本，以避免隨機(jī)劃分所產(chǎn)生的不平衡分類的影響。

除了以上幾種方法以外，文獻(xiàn)[15]提出了一種模糊神經(jīng)算法，目的是最大化它的泛化能力，即最大化受試者工作特征曲線（Receiver Operating characteristic Curve， ROC）下的面積和F-度量，其中運(yùn)用了高斯混合模型和正交前向子空間選擇方法。支持向量機(jī)在類之間數(shù)據(jù)不平衡的情況下表現(xiàn)不佳，特別是在目標(biāo)類的表示不足的情況下。

文獻(xiàn)[16]通過轉(zhuǎn)移決策邊界和使用不相等的正則化代價(jià)兩種思想，來解決在近貝葉斯支持向量機(jī)中的不平衡分類問題，方法的具體實(shí)施過程中選擇每個(gè)類別中的一小部分樣本代表每個(gè)類別，以實(shí)現(xiàn)邊界的轉(zhuǎn)移和不等的正則化代價(jià)。

文獻(xiàn)[17]中通過對(duì)向正、負(fù)類樣本施加不同的懲罰因子并在約束條件中增加參數(shù)來處理不平衡樣本的分類問題。本文則通過對(duì)每個(gè)類標(biāo)簽的數(shù)據(jù)進(jìn)行分別處理，盡量在每個(gè)類中選擇相近個(gè)數(shù)的邊界樣本，以解決不平衡數(shù)據(jù)集所產(chǎn)生的誤分問題。

2 數(shù)據(jù)錐及凸邊界樣本的定義

本文針對(duì)數(shù)據(jù)分類任務(wù)，提出了一種基于凸邊界的樣本選擇方法。在本文方法的研究初期，需要對(duì)此方法思想進(jìn)行保護(hù)，因此申請了專利[18]，并在本文中對(duì)方法的理論環(huán)節(jié)進(jìn)行了深入，在方法的具體實(shí)施步驟中進(jìn)行了改進(jìn)和細(xì)化。方法的理論如下：

首先，將給定的數(shù)據(jù)集 D 分為訓(xùn)練集 D 1和測試集 D 2：

D = D 1∪ D 2

（1）

在訓(xùn)練集 D 1中，本文方法將在每個(gè)類標(biāo)簽上選擇邊界樣本，

D 1= D 11∪ D 12∪…∪ D 1i; i=1，2，…，M

（2）

其中，M為類標(biāo)簽的個(gè)數(shù)，即本文方法在每個(gè) D 1i中選擇邊界樣本。

在先前的工作[18]中，未對(duì)凸集合的思想如何應(yīng)用在方法中進(jìn)行說明，也未對(duì)選擇邊界樣本的選擇空間進(jìn)行定義，僅簡單地在坐標(biāo)系的每個(gè)象限中進(jìn)行邊界樣本的選擇。在本文的研究工作中則提出了數(shù)據(jù)錐的概念，邊界樣本在每個(gè)數(shù)據(jù)錐中進(jìn)行選擇。數(shù)據(jù)錐是基于凸錐的思想而提出的定義，凸錐屬于錐形，也是一種特殊的凸集，具有著凸集合的性質(zhì)。因此，可以應(yīng)用關(guān)于凸集的最經(jīng)典的凸優(yōu)化問題的解決思路。即本文基于凸集合的邊界樣本選擇方法，實(shí)際上是解決一個(gè)凸優(yōu)化問題，即可行域是一個(gè)凸集，目標(biāo)是一個(gè)凸函數(shù)。本文方法所要實(shí)現(xiàn)的就是在數(shù)據(jù)錐中選擇最少的樣本作為訓(xùn)練集，加快建模速度、減小內(nèi)存開銷，而保持分類準(zhǔn)確率不變，甚至提升，從而提升數(shù)據(jù)分類的性能。

本文方法在每個(gè) D 1i子集中根據(jù)訓(xùn)練集 D 1的維度構(gòu)建多個(gè)數(shù)據(jù)錐，在每個(gè)數(shù)據(jù)錐中選擇邊界樣本。數(shù)據(jù)錐的定義如下：

C ={ x ∈ R n |x ∈ C ，λ>0，λ x ∈ C }

（3）

式（3）表示：對(duì)于數(shù)據(jù)錐中的任一點(diǎn) x ，在通過放大系數(shù)λ放大后，仍屬于這個(gè)數(shù)據(jù)錐中的一個(gè)元素。之后，本文方法要在所構(gòu)造的每個(gè)數(shù)據(jù)錐中基于凸邊界的概念選擇樣本。為更好地理解凸邊界的概念，先給出邊界的定義：

B （ I ）= { x ∈ I ?| ε>0， x ′， x ″∈N（ x ，ε）， x ′∈ I ， x ″∈ I ?}

（4）

N （ x ，ε）={ y ∈ R n | ‖ y - x ‖<ε}

（5）

I ?= R n/ I

（6）

式（4）～（6）表示：對(duì)于邊界中的一點(diǎn) x ，對(duì)任一ε，以 x 為圓心，ε為半徑作一鄰域 N ， N 中存在兩點(diǎn) x ′和 x ″，其中， x ′屬于邊界 I 中， x ″是邊界 I 外的一點(diǎn)。由這樣的 x 構(gòu)成的集合即為邊界集 B （ I ）。

已有邊界的定義以后，即可給出凸邊界的定義：

CB （ I ）= { x ， y ∈ B （ I ） | λ∈[0，1]，λ x +（1-λ） y ∈ CB （ I ）}

（7）

式（7）表明：在邊界集 B （ I ）中的兩點(diǎn)的連線屬于凸邊界 CB （ I ）。最終，本文方法將在凸邊界 CB （ I ）中選擇代表性樣本。

最后，本文方法的目的是最小化訓(xùn)練集的樣本個(gè)數(shù)，但分類準(zhǔn)確率與原始訓(xùn)練集 D 1相近或小幅下降，從而提升分類器性能。即：

| p（Α（ CB （ I ）， D 2））-p（Α（ D 1， D 2）） | <ε

（8）

其中：Α是一個(gè)學(xué)習(xí)算法，p（Α（ D 1， D 2））表示以 D 2為測試集， D 1為訓(xùn)練集，在算法Α上得到的分類精度;ε為允許的最大的分類準(zhǔn)確率差異，超過這個(gè)設(shè)定的值，則可認(rèn)為樣本選擇方法無效。本文設(shè)定ε的值為10個(gè)百分點(diǎn)。

3 算法偽代碼

本文邊界樣本選擇方法的具體實(shí)現(xiàn)分為兩部分：首先，對(duì)用戶給出的數(shù)據(jù)集進(jìn)行預(yù)處理，根據(jù)類標(biāo)簽進(jìn)行子集的劃分;然后，在每個(gè)子集中建立多個(gè)數(shù)據(jù)錐，并在每個(gè)數(shù)據(jù)錐中選擇邊界樣本。

算法中的符號(hào)含義如下： T 表示原始訓(xùn)練集， T 1表示刪除含缺失值樣本后的數(shù)據(jù)集， T 2表示刪除含異常值樣本后的數(shù)據(jù)集， T 3表示歸一化后的數(shù)據(jù)集， T 3k表示分割后的子集， T 4k表示坐標(biāo)變換后的結(jié)果， BS （Boundary Samples）表示原始訓(xùn)練集的邊界樣本， BS i表示第i個(gè)子集的邊界樣本。

3.1 數(shù)據(jù)集的預(yù)分割

算法1：數(shù)據(jù)集的預(yù)分割。

程序前

輸入原始訓(xùn)練集 T

刪除包含缺失值的樣本后，得到 T 1

if? ?T 1中存在數(shù)值全部相同的特征 then

刪除此特征

end if

判斷特征之間的相關(guān)性，刪除冗余特征

提取 T 1中的類別標(biāo)識(shí) C ，及標(biāo)識(shí)個(gè)數(shù)C_N

fo r i=1：C_N do

從 T 1中提取屬于第i個(gè)類別的所有樣本，得到 S i

在 S i的每個(gè)特征中，使用箱型圖檢測異常值，并刪除包含這些異常值的樣本

end for

如果存在某特征上的數(shù)值全部相同，恢復(fù)對(duì)此特征上去除的異常樣本

得到刪除異常樣本后的數(shù)據(jù)集 T 2

對(duì) T 2進(jìn)行歸一化，得到 T 3

fo r i=1：C_N do

在 T 3中提取第i個(gè)類標(biāo)識(shí)的樣本子集 T 3i

end for

輸出多個(gè)子集 T 3k

程序后

在數(shù)據(jù)集的預(yù)處理過程中，對(duì)先前工作[18]進(jìn)行了細(xì)化及改進(jìn)。改進(jìn)如下：在進(jìn)行異常樣本檢測前增加了對(duì)于無用特征及冗余特征的判別和刪除操作。當(dāng)存在無用特征或冗余特征時(shí)，會(huì)影響數(shù)據(jù)錐的構(gòu)建及增加邊界樣本的個(gè)數(shù)，且會(huì)增加方法的執(zhí)行時(shí)間。在異常樣本刪除后，增加了檢測特征值是否相同的操作，其目的是保證異常樣本刪除后特征不會(huì)變成對(duì)于數(shù)據(jù)分類任務(wù)的無用屬性，且不會(huì)對(duì)后續(xù)的歸一化操作造成影響。

3.2 構(gòu)建數(shù)據(jù)錐及提取邊界樣本

算法2：構(gòu)建數(shù)據(jù)錐并提取邊界樣本。

程序前

輸入多個(gè)預(yù)處理后的子集 T 3k

fo r i=1：C_N do

選取第i個(gè)子集 T 3i

if? 子集 T 3i中只包含一個(gè)樣本 then

選擇此樣本作為一個(gè)邊界樣本

el se

計(jì)算 T 3i的中心點(diǎn) center i

將 T 3i的原始坐標(biāo)系變換成以 center i為原點(diǎn)的新坐標(biāo)系，得到新的子集 T 4i

對(duì) T 4i的中的每個(gè)樣本添加一個(gè)索引，以標(biāo)識(shí)它所屬的數(shù)據(jù)錐

統(tǒng)計(jì)現(xiàn)已存在的數(shù)據(jù)錐，得到 Cone ，并計(jì)算數(shù)據(jù)錐的個(gè)數(shù)Cone_N

fo r j=1：Cone_N do

在 T 4i中，根據(jù)索引提取屬于第j個(gè)數(shù)據(jù)錐的所有樣本 CS

if? ?CS 只包含一條樣本 then

從原始數(shù)據(jù)集 T 選擇這條樣本，作為 b j

el se

計(jì)算 CS 中每個(gè)樣本到坐標(biāo)系原點(diǎn)的距離，得到 distance

end if

end for

得到第i個(gè)子集的邊界樣本 BS i：

BS i= b 1∪ b 2∪…∪ b Cone_N

end if

end for

得到原始訓(xùn)練集 T 的邊界樣本集 BS ：

BS = BS 1∪ BS 2∪…∪ BS C_N

程序后

在邊界樣本的選擇過程中，對(duì)先前工作[18]的改進(jìn)如下： 1）針對(duì)每個(gè)子集中包含的不同樣本數(shù)作相應(yīng)處理，以加快方法的執(zhí)行速度;

2）明確了凸集合在本文方法中的應(yīng)用，通過對(duì)每個(gè)子集構(gòu)造多個(gè)數(shù)據(jù)錐后，應(yīng)用凸集合的性質(zhì)，而不是簡單地將變換后的坐標(biāo)系空間作為一個(gè)凸集合，對(duì)邊界樣本的選擇更加明確，只選擇每個(gè)數(shù)據(jù)錐中的邊界樣本，即對(duì)分類任務(wù)起決定作用的樣本，能更好地維持原始訓(xùn)練集的分類準(zhǔn)確率。最后，不使用哈希表記錄每個(gè)樣本所屬象限，因?yàn)楫?dāng)特征數(shù)多時(shí)，象限數(shù)會(huì)急劇增加，相應(yīng)的哈希表會(huì)增大，而哈希表非常大時(shí)將會(huì)消耗較大的內(nèi)存。在本文方法中通過對(duì)樣本的簡單標(biāo)識(shí)，可區(qū)分屬于哪個(gè)數(shù)據(jù)錐中即可，從而減少內(nèi)存的開銷;而且通過遍歷數(shù)據(jù)錐而不是每個(gè)象限能加快方法的執(zhí)行速度。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 數(shù)據(jù)集

在實(shí)驗(yàn)評(píng)估部分，本文選擇了12個(gè)主要用于分類任務(wù)的UCI數(shù)據(jù)集（可在http：//archive.ics.uci.edu/ml/獲取）來測試基于凸邊界的樣本選擇方法。由于數(shù)據(jù)集的詳細(xì)屬性較多，這里只展示對(duì)本文起關(guān)鍵性作用的幾個(gè)描述（其中數(shù)據(jù)集英文名稱過長的僅保留前2～3個(gè)單詞），具體如表1所示。

通過表1“實(shí)例數(shù)”數(shù)值可知，實(shí)驗(yàn)既選取了較少的僅有80條樣本的剖腹產(chǎn)分類數(shù)據(jù)集，也選擇包含58509條樣本的無傳感器驅(qū)動(dòng)診斷數(shù)據(jù)集，其中“（）”中的值表示包含的缺失值的個(gè)數(shù)。“維數(shù)”表示實(shí)際輸入到算法中的特征的個(gè)數(shù)，本實(shí)驗(yàn)選擇了從較少的4個(gè)特征到較多的48個(gè)特征的數(shù)據(jù)集。由實(shí)例數(shù)與維數(shù)這兩列數(shù)值可知，本實(shí)驗(yàn)數(shù)據(jù)集的選取較為全面。“類數(shù)”是方法中子集分割的關(guān)鍵因素，其中包括6個(gè)二分類數(shù)據(jù)集和6個(gè)多分類數(shù)據(jù)集，最多的一個(gè)無傳感器驅(qū)動(dòng)診斷數(shù)據(jù)集包含11個(gè)類別。與先前工作[18]的實(shí)驗(yàn)環(huán)節(jié)相比較，本文重新選擇了多個(gè)近五年的新數(shù)據(jù)集，且增大了數(shù)據(jù)集的實(shí)例數(shù)。

4.2 實(shí)驗(yàn)設(shè)置

由于基于凸邊界的樣本選擇方法主要針對(duì)分類任務(wù)的數(shù)據(jù)集的預(yù)處理，因此本文在Python的scikit-learn包中選取了6個(gè)常用的分類器來驗(yàn)證該方法的可行性和有效性。這6個(gè)分類器分別是：高斯樸素貝葉斯（Gaussian Naive Bayes， GNB）、決策樹（Classification And Regression Tree， CART）、線性判別分析（Linear Discriminant Analysis， LDA）、提升算法（Adaptive Boosting， AdaBoost）、隨機(jī)森林（Random Forest， RF）和邏輯回歸（Logistic Regression， LR）。與先前工作[18]的實(shí)驗(yàn)環(huán)節(jié)相比，本文選擇了當(dāng)下流行的python中的sklearn包中的六種經(jīng)典的分類器，增加了分類器選擇的多樣性，從而驗(yàn)證本文方法是否具有普適性。對(duì)于分類任務(wù)的評(píng)估，通常選擇分類準(zhǔn)確率作為其主要性能指標(biāo)。因此，本文采用了分類準(zhǔn)確率作為實(shí)驗(yàn)結(jié)果的展示。

實(shí)驗(yàn)中使用的12個(gè)UCI數(shù)據(jù)集，在各類別中按照2∶ 1的比例將樣本劃分為兩部分，以保證用于分類任務(wù)的數(shù)據(jù)集在劃分前后的類別占比一致，保持了原數(shù)據(jù)集中的類別分布結(jié)構(gòu)。即訓(xùn)練集 D 1占樣本總數(shù)的2/3，測試集 D 2包含剩余的樣本。之后，將訓(xùn)練集 D 1輸入到本文提出的樣本選擇方法中得到邊界樣本集 BS 。將訓(xùn)練集 D 1和邊界樣本集 BS 分別作為6個(gè)分類器中訓(xùn)練集的輸入，測試集的輸入為 D 2，對(duì)比原訓(xùn)練集與邊界樣本集的分類準(zhǔn)確率，從而驗(yàn)證本文方法的可行性。為了進(jìn)一步驗(yàn)證本文方法的性能，通過樣本量之比和分類準(zhǔn)確率之比，給出了樣本選擇的效率分析公式，將在4.4節(jié)中詳細(xì)介紹此內(nèi)容。

4.3 實(shí)驗(yàn)結(jié)果

原始訓(xùn)練集 D 1和邊界樣本集 BS 之間樣本量的比較如表2所示。 為了更清楚地觀察樣本量的差異，表2的最后一列中給出了樣本量的百分比。對(duì)表2中的“百分比”表示 BS 的樣本量與 BS 和 D 1樣本量之和的比值。例如，糖尿病數(shù)據(jù)集，原始訓(xùn)練集和邊界樣本集共1014條樣本，其中 D 1約占1014條的75.6%，共767條， BS 包含247條樣本，約占24.4%。

依據(jù)表2的結(jié)果展示，與原始訓(xùn)練集 D 1的樣本量相比，邊界樣本集 BS 的樣本量顯著減少。銀行認(rèn)證、頁面塊分類、汽車評(píng)估和脈沖星數(shù)據(jù)集的樣本減少量相當(dāng)大，其中脈沖星數(shù)據(jù)集的 BS 的樣本量較 D 1減少了約98.6%，初步顯示了本文提出的樣本選擇方法可有效減少用于訓(xùn)練的樣本量。而剖腹產(chǎn)和電網(wǎng)穩(wěn)定性數(shù)據(jù)集的減少量相對(duì)較小，各減少了37.7%和33%。這是因?yàn)檫吔鐦颖镜倪x擇主要取決于處理 訓(xùn)練集 D 1時(shí)所構(gòu)造的數(shù)據(jù)錐，數(shù)據(jù)錐的數(shù)量越多，選擇到的邊界樣本就越多，而數(shù)據(jù)錐的數(shù)量主要取決于數(shù)據(jù)集的維數(shù)、類數(shù)和數(shù)據(jù)自身的分布結(jié)構(gòu)。

其次，為了驗(yàn)證本文方法在減少樣本量的同時(shí)仍可保持原始訓(xùn)練集的分類性能，分別在6個(gè)分類器上進(jìn)行了12個(gè)UCI數(shù)據(jù)集的分類實(shí)驗(yàn)，比較了原始訓(xùn)練集 D 1和邊界樣本集 BS 分別作為訓(xùn)練集時(shí)的分類準(zhǔn)確率，結(jié)果見表3。結(jié)果中加粗字體部分表示用邊界樣本集 BS 作為訓(xùn)練集的分類準(zhǔn)確率高于或等于原始訓(xùn)練集。可通過數(shù)據(jù)的直觀對(duì)比分析本文方法的可行性和有效性。

4.3.1 高斯樸素貝葉斯

高斯樸素貝葉斯（GNB）是一種用于處理連續(xù)的特征變量的樸素貝葉斯分類器。樸素貝葉斯分類器是基于貝葉斯定理的一種非常簡單的概率分類器，具有穩(wěn)定的分類效率，且分布獨(dú)立假設(shè)成立的情況下效果最佳，因此，本文選擇它作為實(shí)驗(yàn)的分類器之一。

通過比較表3中GNB分類準(zhǔn)確率結(jié)果可以看出，用邊界樣本集 BS 作為訓(xùn)練集在GNB分類器上進(jìn)行分類預(yù)測，其分類準(zhǔn)確率結(jié)果與原始訓(xùn)練集 D 1的準(zhǔn)確率相差不大。其中剖腹產(chǎn)、網(wǎng)購者意向、無傳感器診斷、糖尿病這4個(gè)數(shù)據(jù)集在使用邊界樣本集 BS 后的分類準(zhǔn)確率得到了提高。邊界樣本集 BS 較原始訓(xùn)練集 D 1的分類準(zhǔn)確率下降的最大程度僅為8.9個(gè)百分點(diǎn)，為汽車評(píng)估，但其邊界樣本數(shù)與 D 1的樣本數(shù)相比減少了85.3%。由于訓(xùn)練樣本大量減少而出現(xiàn)的分類準(zhǔn)確率小幅下降的情況，在預(yù)期的可接受范圍內(nèi)。因?yàn)闇p少構(gòu)建分類模型的樣本量，可以大大減少建模的時(shí)間和內(nèi)存消耗;并且對(duì)于絕大多數(shù)數(shù)據(jù)集而言，利用邊界樣本 BS 作為GNB分類器的訓(xùn)練集，得到的結(jié)果都很好，表明本文提出的方法具有一定的可行性。

4.3.2 決策樹

CART決策樹是一種典型的二叉決策樹，既可用作回歸也可用于分類，當(dāng)作為分類樹時(shí)采用基尼指數(shù)來選擇最優(yōu)的切分特征，并且分類規(guī)則易于理解。

在CART決策樹的結(jié)果中，剖腹產(chǎn)數(shù)據(jù)集在使用邊界樣本集 BS 后的分類準(zhǔn)確率有所提高，提升了3.9個(gè)百分點(diǎn);而審計(jì)數(shù)據(jù)和電網(wǎng)穩(wěn)定性這兩個(gè)數(shù)據(jù)集的分類準(zhǔn)確率在訓(xùn)練樣本減少后仍保持不變。然而有2個(gè)數(shù)據(jù)集的結(jié)果較不理想，其中頁面塊分類數(shù)據(jù)集在使用邊界樣本后的分類準(zhǔn)確率較原始訓(xùn)練集 D 1下降了9.8個(gè)百分點(diǎn)，脈沖星數(shù)據(jù)集的分類準(zhǔn)確率則下降了9.1個(gè)百分點(diǎn)，但分析樣本對(duì)比量后可知，邊界樣本集 BS 較原始訓(xùn)練集 D 1的樣本數(shù)大量減少，導(dǎo)致了分類準(zhǔn)確率下降的情況。但多數(shù)邊界樣本集 BS 的分類準(zhǔn)確率下降約在5個(gè)百分點(diǎn)以內(nèi)。總體結(jié)果表明，利用邊界樣本訓(xùn)練分類器達(dá)到了預(yù)期的目的。

4.3.3 線性判別分析

線性判別分析（LDA）也稱Fisher線性判別，其基本思想是將高維空間中的樣本投影到最佳鑒別矢量空間，以達(dá)到抽取分類信息的效果，保證在該空間中有最佳可分離性。

據(jù)表3中的結(jié)果顯示，有2個(gè)數(shù)據(jù)集的分類準(zhǔn)確率的結(jié)果在使用邊界樣本集 BS 作為訓(xùn)練集后保持不變，分別是無線室內(nèi)定位和用戶知識(shí)模型，而在此分類器上沒有準(zhǔn)確率得到提升的數(shù)據(jù)集。除糖尿病數(shù)據(jù)集較原始訓(xùn)練集 D 1的分類準(zhǔn)確率下降了7.5個(gè)百分點(diǎn)外，其他數(shù)據(jù)集準(zhǔn)確率的下降幅度大約都在4個(gè)百分點(diǎn)以內(nèi)。在表3的LDA結(jié)果比對(duì)中，大部分?jǐn)?shù)據(jù)集的分類準(zhǔn)確率都相差不大，并且用于訓(xùn)練的樣本數(shù)量的大幅減少，可以說明本文的樣本抽取方法對(duì)數(shù)據(jù)集的預(yù)處理工作有所成效。

4.3.4 提升算法（AdaBoost）

提升算法（Adaboost）是一種迭代算法，它運(yùn)用集成的思想，將由同一訓(xùn)練集訓(xùn)練的多個(gè)不同的弱分類器組合成一個(gè)強(qiáng)分類器。在本實(shí)驗(yàn)中，弱分類器使用了默認(rèn)的CART決策樹，AdaBoost的算法選擇了SAMME，它將對(duì)樣本集的分類效果作為弱分類器的權(quán)重。

根據(jù)AdaBoost的分類準(zhǔn)確率結(jié)果可知，剖腹產(chǎn)數(shù)據(jù)集的分類準(zhǔn)確率提升了11.5個(gè)百分點(diǎn)，其原因是在選擇邊界樣本的過程中剔除了噪聲樣本。審計(jì)數(shù)據(jù)和電網(wǎng)穩(wěn)定性數(shù)據(jù)集的準(zhǔn)確率較原始訓(xùn)練集 D 1未發(fā)生改變。其中，頁面塊分類數(shù)據(jù)集在使用邊界樣本后結(jié)果較差，下降了9.6個(gè)百分點(diǎn)。其他的數(shù)據(jù)集在使用邊界樣本訓(xùn)練得到的分類準(zhǔn)確率與使用原始訓(xùn)練集 D 1的準(zhǔn)確率相差不大。但結(jié)合訓(xùn)練樣本數(shù)減少的綜合分析，這些結(jié)果依舊可以表明用邊界樣本集 BS 作為訓(xùn)練集的方法是可行的。

4.3.5 隨機(jī)森林

隨機(jī)森林是一種集成算法，它包含多個(gè)決策樹，并且其輸出類別由個(gè)別樹輸出類別的眾數(shù)決定，即通過投票的方式?jīng)Q定最終的分類結(jié)果。其中每棵樹在構(gòu)建的過程中隨機(jī)選取特征，保證隨機(jī)森林的多樣性和隨機(jī)性。

在表3中RF的結(jié)果顯示，剖腹產(chǎn)和電網(wǎng)穩(wěn)定性數(shù)據(jù)庥的分類準(zhǔn)確率得到了改善，其中電網(wǎng)穩(wěn)定數(shù)據(jù)集在適用邊界樣本進(jìn)行訓(xùn)練后的準(zhǔn)確率達(dá)到了100%，即選擇得到的邊界樣本集 BS 中不含噪聲數(shù)據(jù)。審計(jì)數(shù)據(jù)集的分類準(zhǔn)確率在使用邊界樣本進(jìn)行訓(xùn)練后保持了分類準(zhǔn)確率不變。

用戶知識(shí)模型（準(zhǔn)確率結(jié)果加下劃線顯示）數(shù)據(jù)集的準(zhǔn)確率下降了13.3個(gè)百分點(diǎn)，超過了本文設(shè)定的10個(gè)百分點(diǎn)的限制。根據(jù)表2中的樣本量對(duì)比可知，邊界樣本數(shù)較原始訓(xùn)練集減少了64.2%，選擇到的96條邊界樣本可能無法滿足使用隨機(jī)森林分類器時(shí)所需的全部信息，因此出現(xiàn)了大幅下降的情況。隨機(jī)森林分類器對(duì)于小數(shù)據(jù)或低維數(shù)據(jù)來說，不能產(chǎn)生很好的分類效果，因此由于邊界樣本數(shù)過少導(dǎo)致了此情況的發(fā)生。但根據(jù)其他數(shù)據(jù)集的結(jié)果仍可認(rèn)為本文提出的樣本選擇方法是可行的。

4.3.6 邏輯回歸

邏輯回歸模型是一個(gè)非線性模型，使用sigmoid函數(shù)，又稱邏輯回歸函數(shù)，但它本質(zhì)上又是一個(gè)線性回歸模型，且常用于二分類問題，可擴(kuò)展至多分類。

在表3邏輯回歸分類器的結(jié)果中，網(wǎng)購者意向、無線室內(nèi)定位、汽車評(píng)估、無線傳感器診斷這4個(gè)數(shù)據(jù)集的分類準(zhǔn)確率有所提升。與隨機(jī)森林分類器中出現(xiàn)的情況一樣，用戶知識(shí)模型數(shù)據(jù)集使用邊界樣本集 BS 作為訓(xùn)練集后的分類準(zhǔn)確率下降了21.5個(gè)百分點(diǎn)，遠(yuǎn)遠(yuǎn)超出了本文設(shè)定的10個(gè)百分點(diǎn)的要求。結(jié)合LR分類器的特性與訓(xùn)練樣本數(shù)的減少情況分析，LR要求訓(xùn)練集中的樣本線性可分，由于訓(xùn)練樣本較少，且本文提出的樣本選擇方法選出的樣本都是具有歧義性的、最模糊的、易分錯(cuò)的樣本，因此無法很好地滿足LR分類器的要求，導(dǎo)致了分類準(zhǔn)確率大幅下降的情況出現(xiàn)。因此，雖有此情況的出現(xiàn)，由其他數(shù)據(jù)集的結(jié)果中可知，本文方法仍是有效的。

綜合五個(gè)分類器的實(shí)驗(yàn)結(jié)果和樣本量的對(duì)比，可得出一些結(jié)論：

在這12個(gè)數(shù)據(jù)集中，絕大部分?jǐn)?shù)據(jù)集經(jīng)過本文方法選擇得到的邊界樣本集 BS 的樣本量較原始訓(xùn)練集 D 1有著明顯的減少。這是由于邊界樣本集 BS 的樣本數(shù)量與數(shù)據(jù)集中類數(shù)和維數(shù)（即數(shù)據(jù)集的固有特征）有關(guān)。類標(biāo)識(shí)和屬性的個(gè)數(shù)越多，數(shù)據(jù)分布得越均勻，經(jīng)本文方法選擇到的邊界樣本的數(shù)量就越多。

其次，從表3的實(shí)驗(yàn)結(jié)果中可以看出，使用邊界樣本集 BS 對(duì)不同的分類器進(jìn)行訓(xùn)練后得到的模型的分類準(zhǔn)確率大致相同。因此，可知使用邊界樣本進(jìn)行訓(xùn)練的結(jié)果并不受分類器種類不同的影響，即基于凸邊界的樣本選擇方法適用于多種分類模型。表3的具體結(jié)果表明，以邊界樣本 BS 為訓(xùn)練集，可以提高6個(gè)分類器中部分?jǐn)?shù)據(jù)集的分類準(zhǔn)確率。剖腹產(chǎn)數(shù)據(jù)集在4個(gè)分類器上的分類準(zhǔn)確率都有所提升，說明本文方法去除了影響這些分類器分類性能的噪聲數(shù)據(jù)。而由于用于訓(xùn)練的樣本數(shù)量的減少，與原始訓(xùn)練集 D 1的結(jié)果相比，單個(gè)數(shù)據(jù)集的準(zhǔn)確率降低幾乎都在10個(gè)百分點(diǎn)以內(nèi)，并且大多數(shù)數(shù)據(jù)集的準(zhǔn)確率降低都小于5個(gè)百分點(diǎn)，跟原始訓(xùn)練集 D 1的結(jié)果相差不大。因訓(xùn)練樣本數(shù)量大幅度減少，準(zhǔn)確率的小幅下降是不可避免的。但其中頁面塊分類和用戶知識(shí)模型在使用邊界樣本集后分類效果較差，頁面塊邊界樣本量較原始訓(xùn)練集 D 1減少了93.4%，用戶知識(shí)模型減少了64.2%，會(huì)出現(xiàn)邊界樣本因樣本數(shù)過少而導(dǎo)致信息包含不全的情況，但也因此換來了訓(xùn)練時(shí)間的大量減少。而大部分?jǐn)?shù)據(jù)集在6個(gè)分類器上的表現(xiàn)很出色，因此，本文的實(shí)驗(yàn)結(jié)果是可以接受的，并達(dá)到了本文方法的預(yù)期效果，說明提出用邊界樣本集 BS 作為訓(xùn)練集是可行的。并且，利用邊界樣本可以加快分類器的建模速度，降低內(nèi)存開銷，在分類準(zhǔn)確率降低很小的情況下，能從整體上提高分類器的性能。

4.4 效率分析

4.3節(jié)中，在使用邊界樣本集 BS 之后，每個(gè)數(shù)據(jù)集用于訓(xùn)練的樣本量大量減少，從而加快了機(jī)器學(xué)習(xí)的速度。然而，由于某些數(shù)據(jù)集的準(zhǔn)確率降低，需要一個(gè)標(biāo)準(zhǔn)來衡量本文提出的方法是否對(duì)數(shù)據(jù)分類任務(wù)有效。因此，本文提出了一個(gè)新的概念，即清洗效率，來判斷該方法的有效性。

4.4.1 清洗效率定義

樣本量的減少率：

P1=N0/N1

（9）

其中：N0是原始訓(xùn)練集 D 1的樣本個(gè)數(shù)，N1是經(jīng)本文方法選擇得到的邊界樣本集 BS 的樣本個(gè)數(shù)。

準(zhǔn)確率的減少率：

P2=T0/T1

（10）

其中：T0是由原始訓(xùn)練集 D 1得到的分類準(zhǔn)確率，T1是由邊界樣本集 BS 得到的分類準(zhǔn)確率

因此，清洗效率被定義為：

P=P1/P2

（11）

其中：P1代表提取的邊界樣本數(shù)量相對(duì)于原始訓(xùn)練樣本數(shù)量的縮減程度，P1的值越大，表明在此度量上使用本文方法選擇的邊界樣本集 BS 作為訓(xùn)練集時(shí)的效果越好;P2代表使用邊界樣本集 BS 的分類準(zhǔn)確率較原始訓(xùn)練集 D 1的準(zhǔn)確率差的程度，P2的值越小，表明本文方法的效果越好。因此，綜合這兩個(gè)指標(biāo)的比值可知，P的值越大，使用邊界樣本集 BS 進(jìn)行數(shù)據(jù)分類任務(wù)的效率就越高。

4.4.2 清洗效率結(jié)果

根據(jù)清洗效率公式的定義，將6個(gè)分類器上12個(gè)數(shù)據(jù)集的效率分析結(jié)果匯總在表4中（表4中將AdaBoost縮寫為Ada）。

根據(jù)清洗效率公式的定義：當(dāng)P>1時(shí)，即可認(rèn)為該方法提高了數(shù)據(jù)分類的效率，數(shù)值越大，提升效率越高，即此方法在這個(gè)數(shù)據(jù)集上的表現(xiàn)越好;如果P<1，說明該方法降低了數(shù)據(jù)分類的效率，則可認(rèn)為無法用此方法選擇到的邊界樣本集 BS 作為訓(xùn)練集進(jìn)行數(shù)據(jù)分類任務(wù)。

從表4可以看出，清洗效率的所有值都大于1，說明本文方法是有效的。銀行認(rèn)證、頁面塊分類和脈沖星這三個(gè)數(shù)據(jù)集的清洗效率結(jié)果都大于10（名稱及清洗效率結(jié)果加粗顯示），其中脈沖星的效率高達(dá)68以上，是效果最顯著的一個(gè)數(shù)據(jù)集。結(jié)合表2進(jìn)行分析，這3個(gè)數(shù)據(jù)集的邊界樣本數(shù)較原始訓(xùn)練集 D 1的樣本數(shù)大量減少，因此在效率公式中P1的值較大，且使用邊界樣本集 BS 的分類準(zhǔn)確率的下降程度較小，從而清洗效率P值更大。并且脈沖星數(shù)據(jù)集的原始訓(xùn)練集 D 1包含的樣本數(shù)也較大，可以說明原始數(shù)據(jù)集樣本量越大，本文方法的效果越好，數(shù)據(jù)分類效率越高。這一結(jié)論對(duì)本文方法在大規(guī)模數(shù)據(jù)集中的應(yīng)用具有積極的肯定意義。

5 結(jié)語

本文提出了一種基于凸邊界的樣本抽取方法，針對(duì)數(shù)據(jù)分類任務(wù)，從樣本約簡的角度來提升機(jī)器學(xué)習(xí)的性能;在實(shí)驗(yàn)環(huán)節(jié)中，通過樣本量對(duì)比、分類準(zhǔn)確率對(duì)比和效率分析，驗(yàn)證了本文方法的可行性及有效性，并得出了本文方法適用于大多數(shù)分類器的結(jié)論。但實(shí)驗(yàn)中“用戶知識(shí)模型數(shù)據(jù)集”的分類準(zhǔn)確率結(jié)果因樣本量的大幅減少及分類器自身的建模方式，降低了20個(gè)百分點(diǎn)左右。在后續(xù)研究中，我們將針對(duì)此類問題進(jìn)行探究，探尋擴(kuò)展到其他機(jī)器學(xué)習(xí)任務(wù)中的樣本選擇方法，從而提出一種通用且高效的樣本預(yù)處理方法。

參考文獻(xiàn)

[1]?劉艷，鐘萍，陳靜，等.用于處理不平衡樣本的改進(jìn)近似支持向量機(jī)新算法[J].計(jì)算機(jī)應(yīng)用，2014，34（6）：1618-1621. （LIU Y， ZHONG P， CHEN J， et al. Modified proximal support vector machine algorithm for dealing with unbalanced samples [J]. Journal of Computer Applications， 2014， 34（6）： 1618-1621.）

[2]?de CARVALHO M G， LAENDER A H F， GONCALVES M A， et al. A genetic programming approach to record deduplication [J]. IEEE Transactions on Knowledge and Data Engineering， 2012， 24（3）： 399-412.

[3]?dal BIANCO G， GALANTE R， HEUSER C A， et al. Tuning large scale deduplication with reduced effort [C]// Proceedings of the 25th International Conference on Scientific and Statistical Database Management. New York： ACM， 2013： No.18.

[4]?dal BIANCO G， GALANTE R， GONALVES M A， et al. A practical and effective sampling selection strategy for large scale deduplication [J]. IEEE Transactions on Knowledge and Data Engineering， 2015， 27（9）： 2305-2319.

[5]?WANG X， DONG L， YAN J. Maximum ambiguity-based sample selection in fuzzy decision tree induction [J]. IEEE Transactions on Knowledge and Data Engineering， 2012， 24（8）： 1491-1505.

[6]?OUGIAROGLOU S， DIAMANTARAS K I， EVANGELIDIS G. Exploring the effect of data reduction on neural network and support vector machine classification [J]. Neurocomputing， 2018， 280： 101-110.

[7]?SHEN X， MU L， LI Z， et al. Large-scale support vector machine classification with redundant data reduction [J]. Neurocomputing， 2016， 172：189-197.

[8]?胡小生，鐘勇.基于邊界樣本選擇的支持向量機(jī)加速算法[J].計(jì)算機(jī)工程與應(yīng)用， 2017， 53（3）： 169-173. （HU X S， ZHONG Y. SVM accelerated training algorithm based on border sample selection [J]. Computer Engineering and Applications， 2017， 53（3）： 169-173.）

[9]?DESSì N， PES B. Similarity of feature selection methods： An empirical study across data intensive classification tasks [J]. Expert Systems with Applications， 2015， 42（10）： 4632-4642.

[10]?ZHANG Y， YANG C， YANG A， et al. Feature selection for classification with class-separability strategy and data envelopment analysis [J]. Neurocomputing， 2015， 166： 172-184.

[11]??BOLN-CANEDO V， SNCHEZ-MAROO N， ALONSO-BETANZOS A. Data classification using an ensemble of filters [J]. Neurocomputing， 2014， 135： 13-20.

[12]??RIVERA W A， XANTHOPOULOS P. A priori synthetic over-sampling methods for increasing classification sensitivity in imbalanced data sets [J]. Expert Systems with Applications， 2016， 66： 124-135.

[13]?MENARDI G， TORELLI N. Training and assessing classification rules with imbalanced data[J]. Data Mining and Knowledge Discovery， 2014， 28（1）： 92-122.

[14]?LóPEZ V， FERNáNDEZ A， HERRERA F. On the importance of the validation technique for classification with imbalanced datasets： addressing covariate shift when data is skewed [J]. Information Sciences， 2014， 257（2）： 1-13.

[15]?GAO M， HONG X， HARRIS C J. Construction of neurofuzzy models for imbalanced data classification [J]. IEEE Transactions on Fuzzy Systems， 2014， 22（6）： 1472-1488.

[16]?DATTA S， DAS S. Near-Bayesian support vector machines for imbalanced data classification with equal or unequal misclassification costs [J]. Neural Networks， 2015， 70： 39-52.

[17]?劉艷，鐘萍，陳靜，等.用于處理不平衡樣本的改進(jìn)近似支持向量機(jī)新算法[J].計(jì)算機(jī)應(yīng)用，2014，34（6）：1618-1621. （LIU Y， ZHONG P， CHEN J， et al. Modified proximal support vector machine algorithm for dealing with unbalanced samples [J]. Journal of Computer Applications， 2014， 34（6）： 1618-1621.）

[18]??袁玉波，顧依依，談詢滔，等.一種基于凸邊界的學(xué)習(xí)樣本抽取方法： CN201711314980.2[P]. 2018-05-18. （YUAN Y B， GU Y Y， TAN X T， et al. A learning sample extraction method based on convex boundary： CN201711314980.2 [P]. 2018-05-18.）