第31卷第4期 江苏科技大学学报（自然科学版） Vd

.31 N

〇.4

2017 年 8

月

Journal

of

Jiangsu

University

of

Science

and

Technology

( Natural

Science

Edition

) Aug

. 2017

DOI

：10.3969/j.issn. 1673 -4807.2017.04.019

一种近似的K

最近邻图算法

邹蕾

(

吉林警察学院信息工程系，长春130000)

摘要：针对K

最近邻（KNN)

图方法在数据挖掘和机器学习方面的问题，文中提出一种高效的基于K

最近邻图的近似算

法.

首先随机生成一个KNN

图近似值;

对空间进行随意层次划分，构建一个近似近邻图,

然后与KNN

图近似值合并生成一

个更准确的图;

最后对生成的更准确的图进行近邻传播，进一步提高准确度.通过采用各种真实数据集和高维度合成数据

进行实验研究，证实文中提出的算法性能优于先进的KNN

图构造方法.

关键词：K

最近邻图;

多重随机划分;

近似算法；近邻传播方法

中图分类号:TP393

文献标志码:A

文章编号= 1673 -4807(2017)04 -0513 -06

Approximate algorithm based on k-nearest neighbor graph

ZHOU Lei

(Department

of

Information

Engineering,JiLin

Police

College,

Changchun 130000,

China)

Abstract

： In view of the k-nearest neighbor ( KNN) graph problems in data mining and machine learning, an ef­

ficient approximate algorithm is proposed based on the k-nearest neighbor graph. First, a random graph KNN ap­

proximation is generated; the space is divided at random level to construct an approximate nearest neighbor

graph, and then approximate KNN value map they are combined to build a more accurate map; finally, neighbor

propagation of the more accurate nearest neighbor graph further improves the accuracy. Experiments are per­

formed by using real data sets and high-dimensional synthetic data, and the result shows that the proposed algo­

rithm has better performance than the advanced KNN method.

Key

words

： k-nearest neighbor graph, multiple random division, approximate algorithm, neighbor propagation

method

能否有效构建大数据集的

K最近邻图（一个

节点连接到其

K个最近邻居）是协同过滤、网络搜

索引擎方面近似最近邻搜索以及查询有关应用领

域的关键[14. KNN

图是一个关键的完成多降维

聚类以及其他机器学习任务的数据结构[44].

KNN

图最初级方法是通过时间成本0(

如2)

构建，其中„是数据集点数^是维数.但是这种方

法对大规模数据集的应用显得不实际.大量研究工

作已经投入到开发构建KNN

图的有效算法的工作

中.但是，目前已有的方法不能处理高复杂的计算，

也不能处理好高固有维数的数据集，即无法测得相似性.

构建近似

KNN图的方法之一就是应用近似最

近邻搜索方法.数据集的每个点被当成是一个查询

点，采用最近邻搜索算法可以检索到它的

K个最

近邻居.但是，现有方法大体都无法在搜索结构复

杂性和查询检索准确性之间实现平衡.

一种简单有效的方法就是近邻传播，它基于这

样的直觉意识，邻居的邻居也可能就是邻居，这一

思想已出现在诸多文献中.文献[7]中提出近邻传

播算法，已证实该算法通常表现良好，其方法的经

验复杂度是〇(。14)，表明算法效率非常高.不过，

收稿日期：2016 -04 -18

作者简介：邹蕾（1975—），女，讲师,研究方向为计算机应用技术.

E-

mail:290578678@

qq.

com

引文格式：邹蕾.一种近似的

K最近邻图算法[

J].江苏科技大学学报（自然科学版），2017,31(4) :513 -518.

DOI:10.3969/

j.

issn. 1673 -

4807.2017.04.019.514

江苏科技大学学报（自然科学版)2017 年

该算法适合应用在固有维数在20左右的数据集上

面，且随着维数增加，算法逐渐失去效果.

于是，如何构造高效的

KNN图仍是一个比较

困难的问题.在此建议用一种新方法来构建通用相

似性检测所需的高质量近似

KNN图，并考虑它的

效率.首先随机生成一个

KNN图近似值

G/;然后，

创建一个分区树来构建一个近似

KNN图，再将

其与^合并，形成一个更准确的图.分区这一

步首先要随机选择

s个有代表性的对象，它们相互

独立且统一;然后分配给最近的有代表性的对象;

接着在子空间重复这个过程，直到每个空间的要素

都在阀值以下.一些类似的空间分区方法基于超平

面，或者是根据聚类来进行，与此明显不同，我们采

用有代表性的对象来划分空间.

随机分区法效率很高，可用来检测通用相似

性.首先对每个子集应用

BF(

Brute

Force)方法来

生成子图，因为同一子集里的数据点成为相邻点的

概率极高.然后，这些子图与^合并生成一个更准

确的图接着，对图应用近邻传播，进一步提

高准确率;解输出为^图；最后，对空间的随机层

次划分过程和近邻传播重复进行几次，直到获取一

个合理解决方案.文中迭代建立一个序列的解决方

案，从而得到更理想的解决方案.实验结果证明文

中的方法是高效率的.

1

相关工作

关于如何准确构建

KNN图已有广泛探讨，并

且提出了多种方法来避免时间复杂度〇(&2)问

题.文献[8]中提到一种更有效的算法来构建准确

的

KNN图，结果证实对低、高维数据，其时间复杂

性都是

OUlog^、）.尽管先后有大量方法被提出，

但它们的时间复杂度主要随着维数呈指数式增长，

或者随着数据量超线性膨胀.所以研究重心转向近

似近邻图的构建方面.

K丽搜索问题与

K丽图构建密切相关

.KNN

图的构建是对每个对象执行

KNN查询.通常在前

处理阶段，对一些指定的点创建搜索树来应对最近

邻搜索问题.已经提出了各种树结构，具有代表性

的就是基于分区树的方法，如

KD树以及相关衍生

法和层次

K均值树法.另外就是基于哈希的算法，

如局部敏感哈希法.这些方法也得以广泛使用，但

这些方法都无法在搜索结构复杂度与查询检索准

确度之间达到很好的平衡.

依据分而治之的方法论，提出了构建近似

KNN图的一■些方法.从递归角度

，Lanczos

Bisection利用兰索斯流程以递归方式对数据集进行重叠划

分.文献[9]中将数据分成两个不重叠的子集，剩

余样本归为第3个子集.提前定义好重叠比，并将

重叠比设得足够大，以获取到较高准确率.上述方

法无法在时间复杂度和准确率之间维持平衡.文献

[10 -11 ]中提到几种划分树，但都限定在距离.

还有其他一些近邻图的方法.文献[12]中利

用空间填充曲线来限制各个对象周边的搜索范围，

这是一种基于莫顿排序的快速并行算法，但只对低

维度数据效果有效.文献[8]中的基于抽样的有效

方法经证实，拥有较低的复杂度〇(。14)，可以在

现有图和网络分析方面处理大规模数据集，并且不

需要有明确的图结构.但是这种方法不能用在高固

有维数的数据集方面.

2

文中提出的方法

K最近邻图是一个定向图.根据用户特定的度

量，从数据集里选出每个点的

K最近邻居.这一问题

的界定，如定义1.几个重要的注释和定义，如表1.

定义1 :设数据集=丨^，…，

JE以，

K近邻图

G = (

T，£)是一个有向图，其中7 =

1，五是一个

IxZ子集，并且('，、.）设/

Vfc〇t，

G)在图形

G上是

x/

s的

K近邻•

表1文中使用的符号和定义

Table 1 Symbols and definitions used in the paper

符号描述和定义

1= bl，nl

数据点

n

大量数据jxi

d

维度数据

k

最近邻居数

p

〇，y)*,y

相似性

G = (V,E)G:A-

近邻图，F

:顶点集边集

Nk(x,G)

g

图上;r

的尺近邻图

^k(x,G)G

图上Z

的相邻的顶点集

s

随机分层分区选取代表点

M

迭代次数

T

最大数量的访问点

r

终止准则（更新率）

2.1本文算法

算法1给出了计算近似

KNN图的框架.主要

有4个考虑因素

:GeneratelnitialGraph (初始最近邻

居

），RandomHierarchicalPartioning (随机层次划分

法）、

NeighborhoodPropagation(近邻传播）及

Termi-

nationCriterion(终止准则）•对于每个数据点

x

e

X，

GeneratelnitialGraph随机、独立、均衡地从

Z里挑

选出

K

个点作为初始最近邻居.