基于歐式距離的實例選擇算法研究

韓光輝

基于歐式距離的實例選擇算法研究

韓光輝

(河北大學數(shù)學與計算機學院，河北 保定 071001)

近鄰分類法在訓練分類器時需要存儲訓練集中所有的數(shù)據(jù)。這種缺點會導致程序在運行時需要大量的存儲空間和運行時間。提出了兩種新的實例選擇算法：迭代類別實例選擇算法 (ISCC) 和基于同類和異類的迭代實例選擇算法 (IISDC)。兩種算法分別提出分類能力評價函數(shù)來度量每個實例的分類能力，挑選分類能力強的實例，刪除分類能力弱的實例。經(jīng)分析得出兩個算法的時間復雜度均為O(n2)。在真實數(shù)據(jù)庫上的試驗結果表明，ICIS和IISDC算法在壓縮比、分類精度上優(yōu)于FCNN、ICF、ENN等經(jīng)典算法。

實例選擇； 噪聲； 近鄰法；ICIS；IISDC； ENN； FCNN； ICF

0 引言

多年來國內外學者已提出許多實例選擇算法。按照壓縮集中實例產生方式的不同，這些算法可分為原型法和關鍵子集法：原型法利用原始樣本產生數(shù)目較少的新實例組成壓縮集，研究的重點是新實例的產生方式。這種構造原實例集中并不存在的新實例的方法可能改變實例集的類分布結構，其合理性仍值得商榷；關鍵子集法是從原訓練集中選擇分類能力強、有代表性的實例或去除冗余實例，要求有較大的實例壓縮比，同時又不降低近鄰學習的分類準確率。

經(jīng)典算法包括基于啟發(fā)式搜索方法和基于實例特定鄰域的方法。其中，基于啟發(fā)式搜索的算法將關鍵子集的選擇看作組合最優(yōu)化問題，采用啟發(fā)式搜索策略尋優(yōu)，如蒙特卡羅隨機搜索算法[1]、遺傳算法[2，3]、Tabu搜索算法[4-6]以及蟻群搜索算法[7]。這些算法缺點是搜索效果受參數(shù)設置影響，所得壓縮集具有隨機性?；趯嵗植嫉姆椒ㄓ址譃槿悾合肼晫嵗姆椒ǎ贑NN (Condensed Nearest Neighbor Rule) 系列方法和基于實例鄰域的方法。消除噪聲的方法是通過刪除訓練集中被定義為噪聲的實例，達到減少噪聲和提高分類精度的目的?；贑NN系列算法充分考慮每個實例的分布，尋找原始訓練集的一致性壓縮集。基于實例特定鄰域的方法是通過分析每個實例的特定鄰域內實例集的類別來評價該實例在K-近鄰法正確分類中的關鍵程度，進而決定該實例是否會被選擇到壓縮集中。由于基于特定鄰域的方法與K-近鄰法均是由訓練集中實例的相關鄰域決定來決定待分類實例的類別，所以基于特定鄰域的方法一直是實例選擇算法研究的重要方向。

本文通過分析實例分布特點和分類能力之間的關系，定義了兩個新的實例分類能力評價函數(shù)，在充分考慮實例類別的前提下進行實例選擇，同時對比了FCNN、ICF、ENN等經(jīng)典算法。主要工作為：分析可達集和覆蓋集概念和分類能力之間的關系，分析了異類在實例選擇中的作用。通過上述分析，設計了兩個新的實例評價函數(shù)，并使用新的評價函數(shù)設計了兩種新的實例選擇算法——ICIS和IISDC。

1 預備知識

基于實例的學習方法有訓練代價小、假設空間廣、不會損失訓練實例中蘊含的信息、增量漸進學習等優(yōu)點，但同時也存在下列問題：分類新實例的效率低 (需要全局搜索)；特殊實例分布 (影響分類預測精度)；選擇合適的距離度量 (距離函數(shù)的選擇)等。

1.1 實例選擇的概念

近鄰分類法是Cover和Hart于1967年提出來的一種全監(jiān)督的分類方法。為了減少近鄰法的計算量和存儲量，許多學者已提出實例選擇算法來獲得原訓練集的壓縮集，其定義如下。

定義1.1 設 {X, L}={(x1, l1),(x2, l2),…,(xn, ln)} 是一個訓練集，屬性集為{xn}i

n

=1，類標為{ln}i

n=1。找到一個最小的集合{X',L'}?{X, L}，使得任意一個{x, l}∈{X, L},在使用分離器進行分類時滿足l= Classifier(x,{X',L'}),Classifier(x,{X',L'})表示在{X', L'}使用分離器對x進行分類。

1.2 實例選擇的前提

實例選擇必須滿足以下三個前提：

(1) 訓練集的實例個數(shù)必須大于測試集的實例個數(shù)；

(2) 經(jīng)算法處理后得到的壓縮集應滿足以下條件：測試集的實例數(shù)目大于壓縮集實例數(shù)目；(3) 測試方法：目前大部分算法的測試方法采用K-NN方法。

1.3 實例選擇的評價標準

隨著實例選擇研究的不斷深入，實例選擇算法的評價標準也越來越多，綜合起來可以分為以下幾個：

(1) 壓縮比 (compression ratio)

compression ratio=|SC|/|ST|，|SC|表示壓縮集樣本個數(shù)，|ST|表示訓練集樣本個數(shù)；

(2) 泛化能力

壓縮集對訓練集的泛化能力表示壓縮集和訓練集的相似程度，表示的是壓縮集和測試集的相似程度。通常，對于某種分類器而言，相似程度越高，壓縮集泛化能力越強；

(3) 對噪聲和異常點的敏感程度 噪聲和異常點的存在會對分類器分類產生誤導作用，如果壓縮集中過多地存在噪聲和異常點，勢必會影響分類精度，因此，實例選擇算法應能夠避免挑選此類實例；

(4) 算法時間復雜度 實例選擇花費的時間應盡可能少，通常其時間復雜度應該低于O( n2)。

1.4 實例選擇算法研究方向

隨著實例選擇研究的深入，研究方向也進一步分類，具體的可以分為下面幾類：增量、刪除、混合、批量處理、投票和搜索。

1.5 實例選擇算法分類

多年來眾多學者對實例選擇進行了深入的研究，設計了很多實例選擇算法，根據(jù)選擇策略的不同，可以分為以下四類：

表1 四類實例選擇算法Tab. 1 Four classes for instance selection algorithm

2 新的實例選擇算法

在實例選擇算法中，挑選壓縮集的依據(jù)是每個實例在正確分類它的近鄰實例時所做的貢獻大小。依據(jù)近鄰法分類思想，每個實例的分類結果由它的近鄰實例確定，所以根據(jù)可達集和覆蓋集概念分別計算每個實例對其同類實例正確分類的貢獻，依據(jù)結果進行實例選擇。然而，此類算法在實例選擇過程中忽略了類別因素，特別是在實例分布分散或類別之間相互重疊時，易導致：(1) 實例個數(shù)較少的類別被忽略，沒有被挑選到壓縮集中；(2) 每個類別中起關鍵分類作用的實例沒有被挑選到壓縮集中。針對此類問題，本文提出

了三種新的實例選擇算法：(1) 迭代類別實例選擇算法 (Iterative Class Instance Selection：ICIS)；(2) 基于同類和異類的迭代實例選擇算法 (Iterator Instance Selection based on Same and Different Classes：IISDC)。

2.1 可達集和覆蓋集概念

目前，許多實例選擇算法通過特定鄰域來判斷實例的分類能力，但只是簡單地考慮特定鄰域，并不能取得良好的效果。這是因為這種方式忽視了訓練集局部實例分布疏密程度對實例選擇壓縮集的影響。因此，很多算法將特定鄰域限定為實例P 的同類近鄰所組成的區(qū)域，這些同類近鄰實例位于一個超球體內，超球體半徑為實例P 到P 的最近異類實例之間距離。P 的特定鄰域中實例個數(shù)會隨著P 的最近異類實例位置和訓練集疏密程度而變化。對實例P 的選擇，算法可通過P 的同類近鄰實例集和以P 為同類近鄰的實例集來計算P 在正確分類同類實例中的貢獻。

Brighton等人于1999年提出了迭代實例過濾算法(Iterative Case Filtering)。該算法提出了兩個基于Adaptable[27]概念的定義：可達集 (Reachable) 和覆蓋集 (Coverage)。

Adaptable(c', c)表示c'可以被c正確分類 (最近鄰)。通常來說，如果c'可以被c正確分類，則c'可以被刪除，c可以被挑選到壓縮集中。

圖1 (a)實例的Reachable (可達集)(b)實例的Coverage (覆蓋集) Reachable(A)={A}, Reachable(B)={A,B},Coverage(A)={A,B,C}, Coverage(B)={B,C}, Reachable(C)={A,B,C}Coverage(C)={C}Fig.1 (a) Reachable Set (b) Coverage Set Reachable(A)={A}, Reachable(B)={A,B},Coverage(A)={A,B,C}, Coverage(B)={B,C}, Reachable(C)={A,B,C}Coverage(C)={C}

可達集是當前實例NUN (最近異類實例) 距離之內的實例集，覆蓋集是把當前實例作為可達集實例的實例集。對于一個實例，可達集是這個實例同類近鄰實例集，覆蓋集是以這個實例為同類近鄰的實例集。

圖1中，空心點表示正類實例，實心點表示負類實例。虛線圓圈中的點表示各實例的可達集。實線圓圈中的點表示各實例的覆蓋集。

如圖1，A、B、C三個實例對正確分類同類實例的貢獻大小不同。對于一個實例P而言，它對正確分類Coverage(P)中實例有貢獻，所以Coverage(A)={A,B,C}表示A對分類A、B、C實例正確分類都有貢獻。但是這種貢獻大小是不同的：A的可達集中只有A自身，而B和C的可達集則為{A,B}和{A,B,C}。若A沒有被選入壓縮集，則使用壓縮集對訓練集中實例進行分類時，A被錯誤分類，B和C還可由其可達集中其它實例正確分類。據(jù)此，A對正確分類A自身的貢獻最大，對正確分類C的貢獻最小。這種分類貢獻的大小可理解為：一個實例的可達集越大，則其可達集中每個近鄰實例對它分類結果的作用就越小；反之，其對近鄰實例分類貢獻越大。

2.2 ICIS算法

2.2.1 ICIS算法思想

ICIS算法主要包含兩部分：(1) 實例分類貢獻函數(shù)的設計；(2) 按照類別進行實例選擇。

(1) 實例分類貢獻函數(shù)的設計

可達集和覆蓋集的計算可以看作是一個投票的過程。每個實例的可達集中包含的實例個數(shù)即為其可達集的值，每個實例的覆蓋集中的實例個數(shù)即為其覆蓋集的值。

從分類貢獻的角度來看，一個實例的可達集越小，則可達集中每個實例對它分類結果的貢獻就越小。因此，該實例對它自身和最近異類距離之內的實例分類的貢獻也就越大；反之，貢獻越小。一個實例的覆蓋集越大，則該實例對覆蓋集中每個近鄰實例分類都有貢獻，因而其分類貢獻越大；反之，分類貢獻越小。因此，對每個實例， 覆蓋集越大，可達集越小，其分類能力越強；反之越弱。所以，對一個實例X，其分類能力評價函數(shù)可定義如下：

|Coverage(X)|表示實例x覆蓋集包含的實例個數(shù)；|Reachable(X)|表示實例X可達集包含的實例個數(shù)；當Reachable值為0時，分類評價函數(shù)值為負無窮。

一個實例的分類能力評價函數(shù)值越大，表示其分類能力越強；分類評價函數(shù)值越小，表示其分類能力越弱。

實例選擇算法是為分類選擇做出前期處理的算法，其目的是找到一組能夠體現(xiàn)分類決策面的實例，保證其分類精度。上述分類能力評價函數(shù)恰好體現(xiàn)了此目標。如圖1所示，一個實例的覆蓋集越大，表示它距離決策面越近；一個實例的可達集越小，表示它距離決策面越近，因此一個實例的分類能力評價函數(shù)越大，表示其距離決策面越近；分類能力評價函數(shù)越小，表示其距離決策面越遠。對于實例A，B，C而言，可以分別計算它們的分類能力評價函數(shù)，其值分別為2，0，-2，因此，A的分類能力最強，B其次，C的分類能力最弱。實例A將被挑選到壓縮集中，B、C則被刪除，這樣能夠保證A，B，C均可用1-NN分類。

(2) 按照類別進行實例選擇

1) 實例選擇過程中，每次從一個類別中選擇一個分類貢獻最大的函數(shù)添加到壓縮集中，刪除其能正確分類的實例即其可達集中的樣本，考慮到所有類別后停止；

2) 當其中一類或幾類無實例時即不再考慮此類；3) 循環(huán)執(zhí)行此過程。

2.2.2 ICIS的算法

文獻[25]提出噪聲對此類基于歐式距離算法的測試精度有影響，通常它們的測試精度都不高，因此，為了消除噪聲對實例挑選算法測試精度的影響，所有算法在執(zhí)行實例選擇時首先使用了近鄰剪輯算法Wilson Editing過濾噪聲。文獻[28]中通過試驗指出Wilson Editing近鄰數(shù)設為3時除噪效果最佳。整個ICIS算法共分兩步：(1) Wilson Editing去除噪聲；(2) 通過分類能力評價函數(shù)進行實例選擇。ICIS算法每次從一個類中找到一個分類貢獻函數(shù)值最大的實例，刪除其能正確分類的實例即可達集中的實例。分類貢獻函數(shù)的設定，保證了該算法能夠得到一個擬合分類邊界的壓縮集。當一個實例的可達集為0時，該實例的的分類貢獻被設定為負無窮，不會產生溢出錯誤。整個分類貢獻值被設定為一個上三角矩陣。

2.2.3 ICIS算法優(yōu)缺點

ICIS算法優(yōu)點如下：(1) 算法主體無需設定參數(shù)；(2) 求解壓縮集具有確定性；(3)ICIS算法的分類貢獻函數(shù)能夠體現(xiàn)分類邊界；(4) 不受訓練集實例輸入順序影響。

ICIS算法缺點是：整體算法需要兩階段求解。

2.2.4 ICIS算法時間復雜度

ICIS算法求解包括兩個部分: (1) Wilson Editing噪聲過濾時，每個實例查找k個近鄰的時間復雜度為O(n)，總體時間復雜度為O(n2)，而刪除帶標記噪聲實例的時間復雜度為O(n)，因此，第1部分整體時間復雜度為O(n2); (2) 進行實例選擇時，計算可達集和覆蓋集的時間復雜度為O(n2)，查找實例最大分類貢獻值的時間復雜度為O(n)，刪除可達集中實例的時間復雜度為O(n);同時，外層類別迭代為有限次，因此，第2部分的時間復雜度為O(n2);整體ICIS算法的時間復雜度為O(n2)。

2.3 IISDC算法

2.3.1 IISDC算法思想

基于距離的實例選擇算法，都是以同類實例近鄰作為特定鄰域的算法。此類算法從一定程度上考慮了原始訓練集局部疏密程度對壓縮集選擇的影響，但在計算實例的分類重要性時側重分析該實例對正確分類同類實例的貢獻，忽視了它對正確分類異類實例的貢獻。

由ICIS算法可知，實例在計算其在同類實例選擇中的貢獻使用的是基于覆蓋集和可達集概念的分類能力評價函數(shù)Contribution，但是此分類貢獻函數(shù)忽略了異類在實例選擇中做出的貢獻。因此，引入兩個基于Reachable和Coverage的概念：DiffReachable和DiffCoverage

DNS()P表示樣本P近異類樣本。

圖2 (a) 異類可達集; (b) 異類覆蓋集Fig.2 (a) DiffReachable Set; (b) DiffCoverage Set

實例的異類可達集越小表示它對異類的重要程度越大，如圖2，A決定了C、D的分類決策面，因此，A對于正確分類C和D起到了決定性的作用。實例的覆蓋集越大，表示其局部重要性越大，全局分類能力越強。

和同類分類能力評價函數(shù)相似，實例的異類分類能力評價函數(shù)值越大，表示該實例分類能力越強；評價函數(shù)值越小，表示其分類能力越弱。

對于一個實例X，新的分類能力評價函數(shù)被定義為

|DiffCoverage()|x表示實例X異類覆蓋集包含的實例個數(shù)；|DiffReachable()|X表示實例X異類可達集包含的實例個數(shù)；

在IISDC算法原有分類貢獻函數(shù)的基礎上進一步更改實例評價函數(shù)后，新的評價函數(shù)不但考慮同類實例的分布特點，同時考慮了異類樣本的分布特點，能夠更好地挑選分布在分類邊界的實例，得到一組體現(xiàn)分類決策面的壓縮集。

2.3.2 IISDC算法

由于異類可達集和覆蓋集已經(jīng)體現(xiàn)了實例類別間的關系，所以IISDC算法在設計過程中不再考慮類別。

2.3.3 IISDC算法優(yōu)缺點和時間復雜度

IISDC算法除了擁有ICIS算法的優(yōu)點外，由于使用的分類能力評價函數(shù)能夠隱含體現(xiàn)每個實例和異類實例之間的關系，故可以進一步減少類別在實例選擇中的影響，加快算法執(zhí)行效率。但由于訓練集中的類別是有限的，所以IISDC算法執(zhí)行時間復雜度同樣為O(n2)。

3 試驗分析與結論

3.1 試驗設定

為了檢驗本文提出的兩個算法的有效性，選擇7個UCI[29]數(shù)據(jù)庫，2個HBU[30]數(shù)據(jù)庫，1個 Statlog[31]數(shù)據(jù)庫比較了ICIS、IISDC算法與FCNN算法、ENN算法、ICF算法以及訓練集(測試精度和壓縮集大小)。

所有試驗均采用如下的設定：每個數(shù)據(jù)庫采用10倍次的10-fold交叉驗證，所得試驗結果中的每個數(shù)據(jù)均是100次試驗結果的均值，分類方法采用最近鄰算法 (1NN)，距離采用歐幾里得距離，公式如下

3.2 試驗數(shù)據(jù)說明

表1所示的是10個真實數(shù)據(jù)庫的試驗結果。為了使試驗數(shù)據(jù)更加完整，對數(shù)據(jù)屬性缺失采用平均值填補。同時，消除了數(shù)據(jù)庫中不一致性數(shù)據(jù)，即所有屬性值均相同而類別不相同的數(shù)據(jù)。

表1 試驗結果Tab.1The results of test

文獻[32]特別指出訓練集類別數(shù)較多時，通過近鄰分類算法不能得到很好的效果，所以本文中的試驗數(shù)據(jù)均采用類別數(shù)較少的數(shù)據(jù)庫。

為了使試驗更加合理，更能充分展現(xiàn)兩個算法的有效性，試驗中使用了兩組交叉驗證數(shù)據(jù)分別驗證ICIS、IISDC算法，即每個數(shù)據(jù)庫均生成兩組10倍次的10-fold交叉驗證數(shù)據(jù)，每組100個訓練集和測試集，每個算法選擇一組數(shù)據(jù)。同樣， FCNN算法、ENN算法、ICF算法會對兩組數(shù)據(jù)均驗證，考察這三個算法的穩(wěn)定性。

下面分別說明2個HBU數(shù)據(jù)庫。頭部圖像數(shù)據(jù)庫(Dcd), Dcd是對X光照片提取11個特征信息，判別是否發(fā)生病變，結果被分為兩類：病變和沒有病變，即0和1?！叭恕?、“入”兩個字提取特征信息得到的數(shù)據(jù)庫 (RenRu)，RenRu是采集各種字體的“人”和“入”，進行32個屬性的特征分析，分為兩類：“人”和“入”，即0和1。

3.3 試驗結果及分析

為了驗證本文提出的算法的有效性，將ICIS、IISDC算法與FCNN算法、ENN算法、ICF算法以及訓練集進行了比較，通過試驗結果驗證算法設計的合理性。ICIS算法試驗比較結果如表2所示。

表 2. ICIS算法與ICF、FCNN、ENN、原訓練集(T)在存儲比(Storage)、分類準確率(Acc.)比較結果Tab.2 The comparison of Storage Rate (Storage) and classification accuracy(Acc.) between ICF，F(xiàn)CNN，ENN，Train Set and ICIS

在比較ICIS算法與FCNN算法之前，先觀察ENN噪聲過濾操作對ICF算法和ICIS算法的影響。ICF和ICIS算法均是經(jīng)過ENN除噪，然后進行實例選擇。ICIS算法在絕大多數(shù)數(shù)據(jù)庫上的測試精度均高于ICF，8個數(shù)據(jù)庫上高于ENN；ICF算法的測試精度普遍低于ENN算法。ICIS算法同樣在8個數(shù)據(jù)庫上比FCNN的測試精度更高。從幾個算法的平均測試精度中可以看出ICIS算法的測試精度最高，比其它幾種算法高出大約3 %，其次，測試精度較高的算法是ENN算法。FCNN和ICF算法的測試精度很接近于訓練集測試精度。

從壓縮比的角度來看，ICIS算法的壓縮比最大，為ICF算法的2/3，F(xiàn)CNN算法的2/5，ENN算法的1/6。我們在比較壓縮比的同時，還應該考慮這幾種算法設計思想：ENN算法專注于去除噪聲數(shù)據(jù)，F(xiàn)CNN算法主要求解一致性壓縮集，所以壓縮比通常較大，ICF和本文提出的ICIS算法專注于搜尋分類邊界上的實例，通常壓縮比較小。

IISDC算法和ICIS算法相似，區(qū)別在于IISDC算法隱含的考慮了異類實例對于每個實例的貢獻，在實例選擇過程中可以不再考慮異類實例作用。ICIS算法試驗比較結果如表3所示。

表3 IISDC、算法與ICF、FCNN、ENN、原訓練集(T)在存儲比(Storage)、分類準確率(Acc.)比較結果Tab.3 The comparison of Storage Rate (Storage) and classification accuracy(Acc.) between ICF，F(xiàn)CNN，ENN，Train Set and IISDC

IISDC算法在9個數(shù)據(jù)庫上的測試精度均高于ICF，9個數(shù)據(jù)庫上高于ENN；ICF算法的在7個數(shù)據(jù)庫上的測試精度低于ENN算法。IISDC算法同樣在9個數(shù)據(jù)庫上比FCNN的測試精度更高。從幾個算法的平均測試精度中可以看出IISDC算法的測試精度最高，比其它幾種算法高出大約4%，其次測試精度較高的算法是ENN算法。FCNN和ICF算法的測試精度均接近于訓練集測試精度。從壓縮比的角度來看，ICIS算法的壓縮比最大。綜上所述，本文提出的兩個新的實例挑選算法在測試精度和壓縮比上均優(yōu)于ENN、ICF、FCNN算法。有待于改進之處：(1) 不能處理屬性缺失的數(shù)據(jù)，(2) 類別缺失也不能處理，即處理半監(jiān)督問題。

[1] SKALAK D B. Prototype and feature selection by sampling and random mutation hill climbing algorithms [C]// Proc. of 11th International Conference on Machine Learning, New Brunswick, NJ. Los Alamitos, CA: Morgan Kaufmann, 1994: 293-301.

[2] LI K. Editing for the k-nearest neighbors rule by a genetic algorithm [J]. Pattern Recognition Letters, Special Issue on Genetic Algorithms, 1995(16): 809-814.

[3] FEDERICO J, FUENTES O. Instance selection and feature weighting using evolutionary algorithms[C]// IEEE Proceedings of the 15th International Conference on Computing, Mexico, November 2006: 73-79.

[4] VICENTE C, FRANCESC J F. Another move toward the minimum consistent subset: a tabu search approach to the condensed nearest neighbor rule [J]. IEEE Transactions on Systems, Man, and Cybernetics—part B: Cybernetics, 2001, 31(3): 408-413.

[5] ZHANG H B, SUN G Y. Optimal selection of reference subset for nearest neighbor classification [J]. Acta Electronica Sinica, 2000, 28(11): 16-21. [6] CERVERóN V, FUERTES A. Parallel random search and tabu search for the minimal consistent subset selection problem[J]. Lecture Notes in Computer Science, 1998, 1518: 248-259.

[7] LEGUIZAMON,G, MICHALEWICZ Z. A new version of ant system for subset problems[C]//Proceedings of the Congress on Evolutionary Computation, Washington, DC, USA, 1999:1459-1464.

[8] HART P E. The Condensed Nearest Neighbor Rule [J]. IEEE Transactions on Information Theory, 1968, 3: 515-516.

[9] GATES G. The Reduced nearest Neighbor rule [J]. IEEE Transactions on Information Theory. 1972, 18(3): 431-433.

[10] GOWDA KC, KRISHNA G. The condensed nearest neighbor rule using the concept of mutual nearest neighborhood[J]. IEEE Trans. Information Theory, 1979, IT-25,(4): 488-490.

[11] KIBLER D, AHA D W. Learning representative exemplars of concepts: an initial case study[C]//Proceedings of the Fourth International Workshop on Machine Learning, California, 1987: 24-30.

[12] AHA D W, KIBLER D，ALBERT M K. Instance-based learning algorithms [J]. Machine Learning, 1991, 6: 37-66.

[13] FABRIZIO A . Fast condensed nearest neighbor rule[C]//Proceedings of the 22nd International Conference on Machine Learning, Bonn, Germany, 2005, 119: 25-32.

[14] FABRIZIO A. Fast nearest neighbor condensation for large data sets classification[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19, (11):1450-1464.

[15] BRIGHTON H，MELLISH C. Advances in instance selection for instance-based learning algorithms[J]. Data Mining and Knowledge Discovery, 2002, 6(2): 153-172.

[16] SMYTH B, KEANE M T. Remembering to forget. In IJCAI-95[C]//Proceedings of the Fourteenth International Conference on Artificial Intelligence. C.S. Mellish (Ed.), 1995, 1: 377-382.

[17] RITTER G L,LOWRY S R,ISENHOUR T L. An algorithm for a selective nearest neighbour rule[J]. IEEE Trans. Inform. Theory, 1975 , IT11-IT21: 665-669.

[18] BARANDELA R, FERRI F J, SáNCHEZ J S. Decision boundary preserving prototype selection for nearest neighbor classification [J]. International Journal of Pattern Recognition and Artificial Intelligence, 2005, 19(6): 787-806.

[19] DASARATHYBV. Minimal consistent set (MCS) identification for optimal nearest neighbor decision systems design [J ] . IEEE Transactions on Systems, Man, and Cybernetics. 1994, 24 (3):511-517.

[20] WILSOND R , MARTINEZ T R. Instance pruning techniques. in machine learning[C]//Proceedings of the Fourteenth International Conference, D. Fisher (Ed.). San Francisco, CA. 1997: 404-411.

[21] TOMEK. Two modifications of CNN[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1976, SMC-6(11):769-772.

[22] XIANG L G, GONG J Y. Data condensed techniques in classification processes[J]. Journal of Computer Research and Development. 2007, 44(5):837-844.

[23] CHANG C L. Finding prototypes for nearest neighbor classifiers [J]. IEEE Trans. Computers, 1974,C-23, (11):1179-1184.

[24] DEVI F, MURTY M. An incremental prototype set building technique [J]. Pattern Recognition, 2002 (35): 505-513.

[25] KOHONEN T, KANGAS J, TORKOLLA K.LVQ-PAK, The learning vector quantization program package[C]//Helsinki University of Technooty, Faculty of Information Technology, Laboratory of Computer and Information Science, Report A30, 1996.

[26] SMYTH B， KEANE M T. Remembering to forget. In IJCAI-95[C]//Proceedings of the Fourteenth International Conference on Artificial Intelligence. C.S. Mellish (Ed.), 1995, 1: 377-382.

[27]BRIGHTON H, MELLISH C. On the consistency of information filters for lazy learning algorithms[C]// Principles of Data Mining and KnowledgeDiscovery, 3rd European Conference, Prague, Czech Republic, J.M. Zytkowand J. Rauch (Eds.), 1999:283-288.

A Study of Instance Selection Algorithm Based on Euclidean Distance

HAN Guang-hui
(College of Mathematics & Computer Science , Hebei University, Baoding 071001,Hebei Province, P.R. China)

The basic nearest neighbor classifiers suffer from the common problem that the instances used to train the classifier are all stored indiscriminately, and as a result, the required memory storage is huge and response time becomes slow. In this paper, a new Instances Selection algorithm based on Classification Contribution Function shortly named ISCC and IISDC are presented. Meanwhile，two functions are introduced to evaluate the classification ability of the instances. Then an instance with the highest value of Classification Contribution Function is added to the condensed subset. The time complexity of ISCC and IISDC are O(n2). Compared to traditional methods, such as FCNN，ICF and ENN, the condensed sets obtained by ISCC and IISDC are superior in storage rate and classification accuracy.

instance selection; noise ; nearest neighbour rule ; ICIS ; IISDC; ENN; FCNN; ICF

TP 311.13

A

1001-4543(2010)03-0188-09

2010-05-02;

2010-06-13

韓光輝（1979－），男，講師，主要研究方向為不確定信息處理，電子郵件：sxhanguanghui@hebau.edu.cn