基于分层抽样的k近邻分类加速算法

• 作者: 宋云胜 梁吉业
• 来源期刊: 数据采集与处理
• 学科: 工学
• 关键词: 分层抽样 数据划分 近邻 分类精度 运行时间
• 年，卷（期）: 2017,（6）
• 页码范围: 1153-1162
• 页数: 10页
• 分类号: TP181
• 字数: 6590字
• 语种: 中文
• DOI: 10.16337/j.1004-9037.2017.06.010

摘要

k近邻(k nearest neighbor,kNN)分类作为数据挖掘中最典型的算法之一,以较高的泛化性能以及充足的理论基础被广泛应用.然而kNN在测试时需要计算待识别实例与所有训练实例之间的距离,以至于在面对大规模数据时需要大量的时间.为此,提出一种基于分层抽样的kN N加速算法(KNN based on stratified sampling,SS-kNN).首先将训练实例所在的空间划分为若干个实例个数相等的区域,然后从每个区域内抽取实例,最后判定待识别实例落入划分区域中的哪一个,并从此区域以及相邻区域抽取的实例中寻找其k个近邻.与原始kN N算法以及基于随机抽样的kN N算法相比,SS-kN N算法可以获得与其相近分类精度,但将其运行速度分别提高大约399倍和16倍.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	梁吉业	山西大学计算机与信息技术学院	114	1486	21.0	34.0
5	宋云胜	山西大学计算机与信息技术学院	7	16	1.0	4.0