基于自然鄰居和最小生成樹的原型選擇算法研究.pdf

1、在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)中，K最近鄰居因其簡(jiǎn)單有效而得到了長(zhǎng)足的發(fā)展和廣泛的應(yīng)用。然而，傳統(tǒng)的K最近鄰居有兩個(gè)主要的局限性：參數(shù)K的選擇以及在大規(guī)模數(shù)據(jù)集情況下過高的時(shí)間和空間復(fù)雜度需求。當(dāng)KNN算法應(yīng)用時(shí)，參數(shù)K取不同的值可能對(duì)算法的效果產(chǎn)生很大的影響。同時(shí)用于KNN分類的訓(xùn)練集中通常都包含有很多的噪聲雜質(zhì)和冗余的無用信息，在使用這些數(shù)據(jù)集進(jìn)行KNN分類任務(wù)時(shí)，不僅會(huì)使得計(jì)算處理量巨大，而且還可能會(huì)影響算法的分類準(zhǔn)確性。因此在處理模式識(shí)別

2、、分類學(xué)習(xí)等相關(guān)問題時(shí)，對(duì)原始訓(xùn)練集進(jìn)行有效地預(yù)處理是非常有必要的。數(shù)據(jù)集預(yù)處理的一個(gè)重要手段就是數(shù)據(jù)約簡(jiǎn)，而原型選擇就是一個(gè)常用的數(shù)據(jù)約簡(jiǎn)方法。原型選擇是對(duì)原始數(shù)據(jù)集進(jìn)行選擇性的約簡(jiǎn)，在保證最終保留的原型集能夠不降低甚至提升分類準(zhǔn)確率的前提下，獲取具有較高分類貢獻(xiàn)的，同時(shí)能夠反映原始數(shù)據(jù)集的分布狀況，具有一定代表性的原型子集。通過原型選擇算法對(duì)數(shù)據(jù)集進(jìn)行約簡(jiǎn)，不僅可以有效降低數(shù)據(jù)集的規(guī)模，提高分類算法的計(jì)算處理效率；還可以對(duì)數(shù)據(jù)集的分

3、類準(zhǔn)確率有所提升。
　　雖然 KNN算法應(yīng)用中的時(shí)間復(fù)雜度和空間復(fù)雜度高的問題已經(jīng)被研究多年，但是在實(shí)際應(yīng)用中依然沒有得到很好的解決，多數(shù)原型選擇算法獲得較低的分類準(zhǔn)確率和較高的原型保留率。為了既能有效降低數(shù)據(jù)集的規(guī)模，同時(shí)又能保證最終保留的原型集的分類準(zhǔn)確率不降低甚至有所提升；通過對(duì)現(xiàn)有原型選擇算法的研究與分析，本文提出了一個(gè)新的原型選擇算法，即基于自然鄰居和最小生成樹的原型選擇算法。主要研究?jī)?nèi)容如下：
　?、贇w納和闡述了

4、k最近鄰居分類和原型選擇相關(guān)概念和問題，給出了原型選擇算法的不同分類方式，闡述了 k最近鄰分類和原型選擇問題的關(guān)系。最后對(duì)一些經(jīng)典的原型選擇算法以及近年來新提出的原型選擇算法進(jìn)行了較為詳細(xì)的介紹。
　?、卺槍?duì)KNN應(yīng)用中的參數(shù)k值選擇難問題，引入了自然鄰居的概念，并研究了在均勻分布和高斯分布等不同數(shù)據(jù)結(jié)構(gòu)和不同數(shù)據(jù)規(guī)模下的自然鄰居特性。具體研究了數(shù)據(jù)集平均自然鄰居數(shù)目supk的穩(wěn)定性和變化趨勢(shì)，并研究構(gòu)造了幾種有用的自適應(yīng)自然鄰域

5、圖。通過實(shí)驗(yàn)發(fā)現(xiàn)均勻分布數(shù)據(jù)集的平均自然鄰居數(shù)目相對(duì)高斯分布更為穩(wěn)定，高斯分布數(shù)據(jù)集的supk值容易受離群點(diǎn)的影響。因此針對(duì)自然鄰居的搜索算法進(jìn)行改進(jìn)，引入到原型選擇中，有效去除離群點(diǎn)的影響。
　?、坩槍?duì)現(xiàn)有原型選擇算法存在原型選擇約簡(jiǎn)率不夠高和分類準(zhǔn)確率有所下降的問題，提出了基于自然鄰居和最小生成樹的原型選擇算法（Prototype Selection based on Natural Neighbor and MST，PS2N

6、M），算法保留了一些對(duì)分類貢獻(xiàn)較大的關(guān)鍵原型點(diǎn)，同時(shí)移除大多數(shù)對(duì)分類沒有什么貢獻(xiàn)的點(diǎn)。不同于其它原型選擇算法，我們提出的算法使用了自然鄰居這個(gè)新的鄰居概念來做數(shù)據(jù)預(yù)處理，然后基于設(shè)定的控制策略建立最小生成樹?；谧钚∩蓸?，我們保留大多數(shù)有用的邊界原型，同時(shí)生成少量具有代表性的內(nèi)部原型保留下來。本文提出的算法使用自然鄰居做數(shù)據(jù)預(yù)處理，取代基于 KNN的預(yù)處理操作，有效去除了參數(shù)選擇問題。通過人工數(shù)據(jù)集實(shí)驗(yàn)展示了PS2NM算法能夠有效去除