發(fā)布時間：2021-06-24 15:00

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

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

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

【學位級別】：碩士

【文章目錄】：
摘要
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)
第二章 預備知識與相關技術
    2.1 kNN算法
    2.2 聚類算法
    2.3 自由空間中的相關索引結(jié)構(gòu)
        2.3.1 Tree-Based indexes
        2.3.2 Flat-Based Indexes
    2.4 空間數(shù)據(jù)中的相關索引結(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 算法的時間復雜度
    3.4 實驗結(jié)果與分析
        3.4.1 數(shù)據(jù)集
        3.4.2 距離計算公式
        3.4.3 算法評判標準
        3.4.4 不同p值對SCA算法的影響
        3.4.5 算法的性能分析
    3.5 本章總結(jié)
第四章 基于對象數(shù)量的寬度加權聚類kNN算法
    4.1 引言
    4.2 固定寬度聚類算法(FWC算法)
    4.3 基于對象數(shù)量的寬度加權聚類算法
        4.3.1 寬度計算
        4.3.2 聚類過程
        4.3.3 算法的時間復雜度分析
        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é)與展望
參考文獻
攻讀學位期間發(fā)表的成果
致謝


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



本文編號：3247316