基本k近鄰算法通過搜索數(shù)據(jù)集中相似度最高的k個樣本來實現(xiàn)分類或者回歸,其沒有顯式的學(xué)習(xí)過程,天然的具有簡單、離線學(xué)習(xí)、適用于多分類等優(yōu)點。由于該算法需要計算每個結(jié)點到其他所有結(jié)點的距離,所以也被稱為全搜索算法(FSA,full search algorithm),因其獲得最優(yōu)k值需要O(N²)的時間復(fù)雜度,所以計算代價比較高。目前主要有兩種加速的算法,一種是結(jié)合樹索引的精確近鄰查找算法,這種算法雖然可以通過樹索引結(jié)構(gòu)減少距離的計算,但在高維數(shù)據(jù)中,其時間復(fù)雜度依然接近于FSA。另一種是近似近鄰查找算法,它相較于精確近鄰查找算法而言,雖然在查找近鄰時略有偏差,但卻在時間復(fù)雜度上有明顯的優(yōu)勢,故而被廣泛研究。在近似k近鄰算法中,優(yōu)先搜索k-means樹算法是針對高維數(shù)據(jù)搜索查找的一種高效的近似近鄰查找算法,其使用k-means聚類來構(gòu)建樹模型。由于k-means聚類本身的時間復(fù)雜度較低,且算法采用特定策略來對樹進行近鄰搜索,故而算法的效率很高。然而,高維數(shù)據(jù)中可能存在的屬性噪聲會直接影響該算法中k-means樹的構(gòu)建。針對這一問題,本文在基于優(yōu)先搜索k-means樹的...

【文章頁數(shù)】：61 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
abstract
第1章 緒論
    1.1 研究背景及意義
    1.2 國內(nèi)外研究現(xiàn)狀
        1.2.1 近鄰查找
        1.2.2 并行計算
    1.3 論文主要工作
    1.4 論文組織結(jié)構(gòu)
第2章 相關(guān)研究
    2.1 近鄰查找算法
        2.1.1 精確近鄰查找
        2.1.2 近似近鄰查找
        2.1.3 評價指標
    2.2 Bagging
        2.2.1 算法原理
        2.2.2 算法描述
    2.3 MPI并行化
        2.3.1 相關(guān)概念
        2.3.2 MPI并行設(shè)計方法
        2.3.3 并行性能評價指標
    2.4 本章小結(jié)
第3章 高效近鄰分類算法
    3.1 k-means森林分類算法
        3.1.1 概述
        3.1.2 算法描述
        3.1.3 算法時間復(fù)雜度分析
    3.2 基于MPI的并行k-means森林
        3.2.1 并行性分析
        3.2.2 并行結(jié)構(gòu)
    3.3 粒球近鄰分類算法
        3.3.1 概述
        3.3.2 相關(guān)定義
        3.3.3 算法描述
        3.3.4 算法時間復(fù)雜度分析
    3.4 本章小結(jié)
第4章 實驗結(jié)果與分析
    4.1 實驗環(huán)境
    4.2 實驗數(shù)據(jù)集
    4.3 串行實驗
        4.3.1 k-means森林實驗
        4.3.2 粒球近鄰實驗
    4.4 并行實驗
    4.5 本章小結(jié)
第5章 總結(jié)與展望
參考文獻
致謝
攻讀碩士學(xué)位期間從事的科研工作及取得的成果



本文編號：3832598