隨著信息技術(shù)的不斷發(fā)展,各種各樣的數(shù)據(jù)信息不斷豐富著人們的精神和物資生活,人們也越來(lái)越關(guān)注如何使用數(shù)據(jù)挖掘算法從數(shù)據(jù)中提取有效的信息。其中k最近鄰算法（kNN算法）是數(shù)據(jù)挖掘領(lǐng)域中經(jīng)典算法之一,其作為一種高效的非參數(shù)化技術(shù)已經(jīng)廣泛應(yīng)用于科學(xué)和工程領(lǐng)域。由于kNN算法需要遍歷數(shù)據(jù)集的每個(gè)對(duì)象,具有較多的冗余計(jì)算,這導(dǎo)致該算法在處理數(shù)據(jù)時(shí)需要消耗大量的計(jì)算資源,因此如何降低k最近鄰算法中的計(jì)算量已經(jīng)成為一個(gè)熱門(mén)的研究?jī)?nèi)容。為了解決上述問(wèn)題,很多當(dāng)前的研究工作都將注意力集中在數(shù)據(jù)的預(yù)處理上,即在kNN查詢(xún)之前構(gòu)建數(shù)據(jù)集的索引結(jié)構(gòu),其目的是通過(guò)計(jì)算數(shù)據(jù)集的一部分便可找到查詢(xún)對(duì)象的k個(gè)最近鄰對(duì)象。在空間數(shù)據(jù)查詢(xún)中,本文提出了一種新的聚類(lèi)算法（SCA算法）用于kNN的查詢(xún)。SCA算法根據(jù)固定路線(xiàn)的位置將其劃分為多個(gè)路段,并將路段模型化為一個(gè)帶權(quán)有向圖,然后根據(jù)移動(dòng)對(duì)象的速度將路段聚類(lèi)成多個(gè)子路段。SCAkNN算法在這些劃分子路段的基礎(chǔ)上進(jìn)行kNN查詢(xún)。首先SCA算法對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,然后SCAkNN在SCA算法預(yù)處理的基礎(chǔ)上進(jìn)行的k最近鄰查詢(xún)。SCAkNN算法能夠快速確定包含k個(gè)最近鄰的區(qū)域,并且... 

【文章來(lái)源】：廣東工業(yè)大學(xué)廣東省

【文章頁(yè)數(shù)】：68 頁(yè)

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

【文章目錄】：
摘要
ABSTRACT
第一章 緒論
    1.1 研究背景及意義
        1.1.1 研究背景
        1.1.2 研究意義
    1.2 國(guó)內(nèi)外研究現(xiàn)狀
        1.2.1 近似索引算法
        1.2.2 精確索引算法
    1.3 主要研究?jī)?nèi)容和貢獻(xiàn)點(diǎn)
    1.4 論文結(jié)構(gòu)
第二章 預(yù)備知識(shí)與相關(guān)技術(shù)
    2.1 kNN算法
    2.2 聚類(lèi)算法
    2.3 自由空間中的相關(guān)索引結(jié)構(gòu)
        2.3.1 Tree-Based indexes
        2.3.2 Flat-Based Indexes
    2.4 空間數(shù)據(jù)中的相關(guān)索引結(jié)構(gòu)
第三章 固定路線(xiàn)中基于速度聚類(lèi)的kNN查詢(xún)算法
    3.1 引言
    3.2 建立索引結(jié)構(gòu)
        3.2.1 模型轉(zhuǎn)化
        3.2.2 固定路線(xiàn)中基于速度的聚類(lèi)算法(SCA算法)
        3.2.3 索引結(jié)構(gòu)的更新
    3.3 基于速度聚類(lèi)的kNN查詢(xún)算法
        3.3.1 SCAkNN算法
        3.3.2 算法的時(shí)間復(fù)雜度
    3.4 實(shí)驗(yàn)結(jié)果與分析
        3.4.1 數(shù)據(jù)集
        3.4.2 距離計(jì)算公式
        3.4.3 算法評(píng)判標(biāo)準(zhǔn)
        3.4.4 不同p值對(duì)SCA算法的影響
        3.4.5 算法的性能分析
    3.5 本章總結(jié)
第四章 基于對(duì)象數(shù)量的寬度加權(quán)聚類(lèi)kNN算法
    4.1 引言
    4.2 固定寬度聚類(lèi)算法(FWC算法)
    4.3 基于對(duì)象數(shù)量的寬度加權(quán)聚類(lèi)算法
        4.3.1 寬度計(jì)算
        4.3.2 聚類(lèi)過(guò)程
        4.3.3 算法的時(shí)間復(fù)雜度分析
        4.3.4 kNN查詢(xún)過(guò)程
    4.4 實(shí)驗(yàn)數(shù)據(jù)集與參數(shù)
        4.4.1 數(shù)據(jù)集介紹
        4.4.2 參數(shù)選擇
    4.5 結(jié)果分析
        4.5.1 建模時(shí)間
        4.5.2 查詢(xún)時(shí)間加速率
    4.6 本章總結(jié)
總結(jié)與展望
參考文獻(xiàn)
攻讀學(xué)位期間發(fā)表的成果
致謝


【參考文獻(xiàn)】：
期刊論文
[1]基于改進(jìn)SVM與輔助信息的數(shù)據(jù)分類(lèi)研究[J]. 王艷潔,楊琳,金樺.  電視技術(shù). 2019(02)
[2]基于改進(jìn)KNN算法的交通流異常數(shù)據(jù)修復(fù)方法[J]. 秦一菲,馬明輝,王巖松,郭輝,張亮.  計(jì)算機(jī)測(cè)量與控制. 2018(12)
[3]基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)分類(lèi)預(yù)測(cè)與實(shí)現(xiàn)[J]. 常強(qiáng),趙偉,趙仰杰.  軟件. 2018(12)
[4]基于Spark平臺(tái)的并行KNN異常檢測(cè)算法[J]. 馮貴蘭,周文剛.  計(jì)算機(jī)科學(xué). 2018(S2)
[5]基于對(duì)象數(shù)量的寬度加權(quán)聚類(lèi)kNN算法[J]. 陳輝,關(guān)凱勝,李嘉興.  計(jì)算機(jī)工程與應(yīng)用. 2018(19)
[6]外包空間數(shù)據(jù)庫(kù)中的反向k最遠(yuǎn)鄰居查詢(xún)驗(yàn)證技術(shù)[J]. 王海霞,谷峪,于戈.  計(jì)算機(jī)學(xué)報(bào). 2018(08)
[7]基于HBase的路網(wǎng)移動(dòng)對(duì)象時(shí)空索引方法[J]. 馮鈞,李頂圣,陸佳民,張立霞.  計(jì)算機(jī)應(yīng)用. 2018(06)
[8]基于粗糙集的加權(quán)KNN數(shù)據(jù)分類(lèi)算法[J]. 劉繼宇,王強(qiáng),羅朝暉,宋浩,張綠云.  計(jì)算機(jī)科學(xué). 2015(10)
[9]卷積神經(jīng)網(wǎng)絡(luò)分類(lèi)模型在模式識(shí)別中的新進(jìn)展[J]. 胡正平,陳俊嶺,王蒙,趙淑歡.  燕山大學(xué)學(xué)報(bào). 2015(04)
[10]道路網(wǎng)中基于RRN-Tree的CKNN查詢(xún)[J]. 孫海龍,王霓虹.  計(jì)算機(jī)工程. 2014(06)



本文編號(hào)：3247316