kNN查询中面向索引结构的聚类算法研究
发布时间：2021-06-24 15:00
随着信息技术的不断发展,各种各样的数据信息不断丰富着人们的精神和物资生活,人们也越来越关注如何使用数据挖掘算法从数据中提取有效的信息。其中k最近邻算法（kNN算法）是数据挖掘领域中经典算法之一,其作为一种高效的非参数化技术已经广泛应用于科学和工程领域。由于kNN算法需要遍历数据集的每个对象,具有较多的冗余计算,这导致该算法在处理数据时需要消耗大量的计算资源,因此如何降低k最近邻算法中的计算量已经成为一个热门的研究内容。为了解决上述问题,很多当前的研究工作都将注意力集中在数据的预处理上,即在kNN查询之前构建数据集的索引结构,其目的是通过计算数据集的一部分便可找到查询对象的k个最近邻对象。在空间数据查询中,本文提出了一种新的聚类算法（SCA算法）用于kNN的查询。SCA算法根据固定路线的位置将其划分为多个路段,并将路段模型化为一个带权有向图,然后根据移动对象的速度将路段聚类成多个子路段。SCAkNN算法在这些划分子路段的基础上进行kNN查询。首先SCA算法对数据进行预处理,然后SCAkNN在SCA算法预处理的基础上进行的k最近邻查询。SCAkNN算法能够快速确定包含k个最近邻的区域,并且...
【文章来源】：广东工业大学广东省
【文章页数】：68 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第一章 绪论
1.1 研究背景及意义
1.1.1 研究背景
1.1.2 研究意义
1.2 国内外研究现状
1.2.1 近似索引算法
1.2.2 精确索引算法
1.3 主要研究内容和贡献点
1.4 论文结构
第二章 预备知识与相关技术
2.1 kNN算法
2.2 聚类算法
2.3 自由空间中的相关索引结构
2.3.1 Tree-Based indexes
2.3.2 Flat-Based Indexes
2.4 空间数据中的相关索引结构
第三章 固定路线中基于速度聚类的kNN查询算法
3.1 引言
3.2 建立索引结构
3.2.1 模型转化
3.2.2 固定路线中基于速度的聚类算法(SCA算法)
3.2.3 索引结构的更新
3.3 基于速度聚类的kNN查询算法
3.3.1 SCAkNN算法
3.3.2 算法的时间复杂度
3.4 实验结果与分析
3.4.1 数据集
3.4.2 距离计算公式
3.4.3 算法评判标准
3.4.4 不同p值对SCA算法的影响
3.4.5 算法的性能分析
3.5 本章总结
第四章 基于对象数量的宽度加权聚类kNN算法
4.1 引言
4.2 固定宽度聚类算法(FWC算法)
4.3 基于对象数量的宽度加权聚类算法
4.3.1 宽度计算
4.3.2 聚类过程
4.3.3 算法的时间复杂度分析
4.3.4 kNN查询过程
4.4 实验数据集与参数
4.4.1 数据集介绍
4.4.2 参数选择
4.5 结果分析
4.5.1 建模时间
4.5.2 查询时间加速率
4.6 本章总结
总结与展望
参考文献
攻读学位期间发表的成果
致谢
【参考文献】：
期刊论文
[1]基于改进SVM与辅助信息的数据分类研究[J]. 王艳洁,杨琳,金桦. 电视技术. 2019(02)
[2]基于改进KNN算法的交通流异常数据修复方法[J]. 秦一菲,马明辉,王岩松,郭辉,张亮. 计算机测量与控制. 2018(12)
[3]基于神经网络的数据分类预测与实现[J]. 常强,赵伟,赵仰杰. 软件. 2018(12)
[4]基于Spark平台的并行KNN异常检测算法[J]. 冯贵兰,周文刚. 计算机科学. 2018(S2)
[5]基于对象数量的宽度加权聚类kNN算法[J]. 陈辉,关凯胜,李嘉兴. 计算机工程与应用. 2018(19)
[6]外包空间数据库中的反向k最远邻居查询验证技术[J]. 王海霞,谷峪,于戈. 计算机学报. 2018(08)
[7]基于HBase的路网移动对象时空索引方法[J]. 冯钧,李顶圣,陆佳民,张立霞. 计算机应用. 2018(06)
[8]基于粗糙集的加权KNN数据分类算法[J]. 刘继宇,王强,罗朝晖,宋浩,张绿云. 计算机科学. 2015(10)
[9]卷积神经网络分类模型在模式识别中的新进展[J]. 胡正平,陈俊岭,王蒙,赵淑欢. 燕山大学学报. 2015(04)
[10]道路网中基于RRN-Tree的CKNN查询[J]. 孙海龙,王霓虹. 计算机工程. 2014(06)
本文编号：3247316
【文章来源】：广东工业大学广东省
【文章页数】：68 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第一章 绪论
1.1 研究背景及意义
1.1.1 研究背景
1.1.2 研究意义
1.2 国内外研究现状
1.2.1 近似索引算法
1.2.2 精确索引算法
1.3 主要研究内容和贡献点
1.4 论文结构
第二章 预备知识与相关技术
2.1 kNN算法
2.2 聚类算法
2.3 自由空间中的相关索引结构
2.3.1 Tree-Based indexes
2.3.2 Flat-Based Indexes
2.4 空间数据中的相关索引结构
第三章 固定路线中基于速度聚类的kNN查询算法
3.1 引言
3.2 建立索引结构
3.2.1 模型转化
3.2.2 固定路线中基于速度的聚类算法(SCA算法)
3.2.3 索引结构的更新
3.3 基于速度聚类的kNN查询算法
3.3.1 SCAkNN算法
3.3.2 算法的时间复杂度
3.4 实验结果与分析
3.4.1 数据集
3.4.2 距离计算公式
3.4.3 算法评判标准
3.4.4 不同p值对SCA算法的影响
3.4.5 算法的性能分析
3.5 本章总结
第四章 基于对象数量的宽度加权聚类kNN算法
4.1 引言
4.2 固定宽度聚类算法(FWC算法)
4.3 基于对象数量的宽度加权聚类算法
4.3.1 宽度计算
4.3.2 聚类过程
4.3.3 算法的时间复杂度分析
4.3.4 kNN查询过程
4.4 实验数据集与参数
4.4.1 数据集介绍
4.4.2 参数选择
4.5 结果分析
4.5.1 建模时间
4.5.2 查询时间加速率
4.6 本章总结
总结与展望
参考文献
攻读学位期间发表的成果
致谢
【参考文献】：
期刊论文
[1]基于改进SVM与辅助信息的数据分类研究[J]. 王艳洁,杨琳,金桦. 电视技术. 2019(02)
[2]基于改进KNN算法的交通流异常数据修复方法[J]. 秦一菲,马明辉,王岩松,郭辉,张亮. 计算机测量与控制. 2018(12)
[3]基于神经网络的数据分类预测与实现[J]. 常强,赵伟,赵仰杰. 软件. 2018(12)
[4]基于Spark平台的并行KNN异常检测算法[J]. 冯贵兰,周文刚. 计算机科学. 2018(S2)
[5]基于对象数量的宽度加权聚类kNN算法[J]. 陈辉,关凯胜,李嘉兴. 计算机工程与应用. 2018(19)
[6]外包空间数据库中的反向k最远邻居查询验证技术[J]. 王海霞,谷峪,于戈. 计算机学报. 2018(08)
[7]基于HBase的路网移动对象时空索引方法[J]. 冯钧,李顶圣,陆佳民,张立霞. 计算机应用. 2018(06)
[8]基于粗糙集的加权KNN数据分类算法[J]. 刘继宇,王强,罗朝晖,宋浩,张绿云. 计算机科学. 2015(10)
[9]卷积神经网络分类模型在模式识别中的新进展[J]. 胡正平,陈俊岭,王蒙,赵淑欢. 燕山大学学报. 2015(04)
[10]道路网中基于RRN-Tree的CKNN查询[J]. 孙海龙,王霓虹. 计算机工程. 2014(06)
本文编号：3247316
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3247316.html
