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

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

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

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

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


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



本文編號：3247316