本文關鍵詞：基于自然鄰居和最小生成樹的原型選擇算法研究

  更多相關文章： K最近鄰居 原型選擇 自然鄰居 最小生成樹 分類

【摘要】：在數(shù)據(jù)挖掘和機器學習中,K最近鄰居因其簡單有效而得到了長足的發(fā)展和廣泛的應用。然而,傳統(tǒng)的K最近鄰居有兩個主要的局限性:參數(shù)K的選擇以及在大規(guī)模數(shù)據(jù)集情況下過高的時間和空間復雜度需求。當KNN算法應用時,參數(shù)K取不同的值可能對算法的效果產(chǎn)生很大的影響。同時用于KNN分類的訓練集中通常都包含有很多的噪聲雜質和冗余的無用信息,在使用這些數(shù)據(jù)集進行KNN分類任務時,不僅會使得計算處理量巨大,而且還可能會影響算法的分類準確性。因此在處理模式識別、分類學習等相關問題時,對原始訓練集進行有效地預處理是非常有必要的。數(shù)據(jù)集預處理的一個重要手段就是數(shù)據(jù)約簡,而原型選擇就是一個常用的數(shù)據(jù)約簡方法。原型選擇是對原始數(shù)據(jù)集進行選擇性的約簡,在保證最終保留的原型集能夠不降低甚至提升分類準確率的前提下,獲取具有較高分類貢獻的,同時能夠反映原始數(shù)據(jù)集的分布狀況,具有一定代表性的原型子集。通過原型選擇算法對數(shù)據(jù)集進行約簡,不僅可以有效降低數(shù)據(jù)集的規(guī)模,提高分類算法的計算處理效率;還可以對數(shù)據(jù)集的分類準確率有所提升。雖然KNN算法應用中的時間復雜度和空間復雜度高的問題已經(jīng)被研究多年,但是在實際應用中依然沒有得到很好的解決,多數(shù)原型選擇算法獲得較低的分類準確率和較高的原型保留率。為了既能有效降低數(shù)據(jù)集的規(guī)模,同時又能保證最終保留的原型集的分類準確率不降低甚至有所提升;通過對現(xiàn)有原型選擇算法的研究與分析,本文提出了一個新的原型選擇算法,即基于自然鄰居和最小生成樹的原型選擇算法。主要研究內容如下:(1)歸納和闡述了k最近鄰居分類和原型選擇相關概念和問題,給出了原型選擇算法的不同分類方式,闡述了k最近鄰分類和原型選擇問題的關系。最后對一些經(jīng)典的原型選擇算法以及近年來新提出的原型選擇算法進行了較為詳細的介紹。(2)針對KNN應用中的參數(shù)k值選擇難問題,引入了自然鄰居的概念,并研究了在均勻分布和高斯分布等不同數(shù)據(jù)結構和不同數(shù)據(jù)規(guī)模下的自然鄰居特性。具體研究了數(shù)據(jù)集平均自然鄰居數(shù)目的穩(wěn)定性和變化趨勢,并研究構造了幾種有用的自適應自然鄰域圖。通過實驗發(fā)現(xiàn)均勻分布數(shù)據(jù)集的平均自然鄰居數(shù)目相對高斯分布更為穩(wěn)定,高斯分布數(shù)據(jù)集的值容易受離群點的影響。因此針對自然鄰居的搜索算法進行改進,引入到原型選擇中,有效去除離群點的影響。(3)針對現(xiàn)有原型選擇算法存在原型選擇約簡率不夠高和分類準確率有所下降的問題,提出了基于自然鄰居和最小生成樹的原型選擇算法(Prototype Selection based on Natural Neighbor and MST,PS2NM),算法保留了一些對分類貢獻較大的關鍵原型點,同時移除大多數(shù)對分類沒有什么貢獻的點。不同于其它原型選擇算法,我們提出的算法使用了自然鄰居這個新的鄰居概念來做數(shù)據(jù)預處理,然后基于設定的控制策略建立最小生成樹�；谧钚∩蓸�,我們保留大多數(shù)有用的邊界原型,同時生成少量具有代表性的內部原型保留下來。本文提出的算法使用自然鄰居做數(shù)據(jù)預處理,取代基于KNN的預處理操作,有效去除了參數(shù)選擇問題。通過人工數(shù)據(jù)集實驗展示了PS2NM算法能夠有效去除噪聲數(shù)據(jù)和冗余原型,保留的原型集具有跟原始訓練集相同的分布情況;通過UCI基準數(shù)據(jù)集實驗,將PS2NM同傳統(tǒng)的原型選擇算法(CNN、ENN)和最近的原型選擇算法(TRKNN、PSC、BNNT)進行比較,結果顯示本文提出的算法有效的約簡了原型的數(shù)量,算法最終選擇的原型集用于分類時,保持了與傳統(tǒng)KNN相同水平的分類準確率。而且,在分類準確率和原型保留率上,本文提出的算法與其它原型選擇算法相比還有一些優(yōu)勢。
【關鍵詞】：K最近鄰居 原型選擇 自然鄰居 最小生成樹 分類
【學位授予單位】：重慶大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP181
【目錄】：

• 中文摘要3-5
• 英文摘要5-10
• 1 緒論10-15
• 1.1 研究背景及意義10-11
• 1.2 國內外研究現(xiàn)狀11-13
• 1.3 本文研究的主要內容13
• 1.4 組織結構13-15
• 2 基于k最近鄰分類的原型選擇概述15-25
• 2.1 K最近鄰分類15
• 2.2 原型選擇基礎15-16
• 2.3 原型選擇相關概念16-17
• 2.4 原型選擇評價標準17
• 2.5 原型選擇算法的分類17-19
• 2.5.1 搜索方向17-19
• 2.5.2 選擇類型19
• 2.6 基于k最近鄰分類的原型選擇19-24
• 2.6.1 CNN算法19-20
• 2.6.2 ENN算法20-21
• 2.6.3 TRKNN算法21-22
• 2.6.4 PSC算法22-23
• 2.6.5 BNNT算法23-24
• 2.7 本章小結24-25
• 3 自然鄰居25-33
• 3.1 自然鄰居的形成25-26
• 3.2 自然鄰居的定義26
• 3.3 自然鄰居相關特性26-31
• 3.3.1 值的穩(wěn)定性26-29
• 3.3.2 自然鄰域圖29-31
• 3.4 本章小結31-33
• 4 基于自然鄰居和最小生成樹的原型選擇算法33-50
• 4.1 數(shù)據(jù)預處理33-35
• 4.2 最小生成樹的建立35-38
• 4.3 原型選擇38-39
• 4.4 算法時間復雜度分析39-40
• 4.5 實驗及分析40-48
• 4.5.1 人工數(shù)據(jù)集實驗40-41
• 4.5.2 UCI數(shù)據(jù)集實驗41-48
• 4.6 本章小結48-50
• 5 總結與展望50-53
• 5.1 總結50-51
• 5.2 展望51-53
• 致謝53-54
• 參考文獻54-57
• 附錄57
• A. 作者在攻讀學位期間發(fā)表的論文目錄57
• B. 作者在攻讀學位期間參與的科研項目目錄57

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 薛春艷;;最小生成樹在城市高速公路問題中的應用[J];電腦編程技巧與維護;2009年06期

2 胡紅;;最小生成樹的應用及拓展探討[J];洛陽師范學院學報;2012年02期

3 毛華;史田敏;高瑞;;求最小生成樹的矩陣算法[J];鄭州大學學報(理學版);2013年04期

4 楊國慧,周春光,黃艷新,呂慧英;最小生成樹用于基因表示數(shù)據(jù)的聚類算法[J];計算機研究與發(fā)展;2003年10期

5 楊旭;;求最小生成樹的另一算法及其與其它算法的比較[J];重慶電力高等�？茖W校學報;2003年02期

6 周玉林;最小生成樹與次小生成樹上的算法分析與設計[J];上饒師范學院學報(自然科學版);2005年03期

7 陳國龍;郭文忠;涂雪珠;陳火旺;;求解多目標最小生成樹問題的改進算法[J];軟件學報;2006年03期

8 歐陽浩;肖建華;;基于網(wǎng)格的最小生成樹聚類算法[J];計算機與現(xiàn)代化;2006年12期

9 閻少宏;王秋麗;楊愛民;;最小生成樹問題的分析與研究[J];商場現(xiàn)代化;2007年11期

10 余榮祖;王宇平;;求解多目標最小生成樹的一種改進的非支配排序遺傳算法[J];電子科技;2007年06期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 黃宜真;張世R，

本文編號：847168