基于分位数概要的KNN算法研究

摘要：文章简述了分位数概要的相关概念及特点，针对KNN（K最近邻居）的算法特性及应用进行了深入的研究，并在此基础上提出了基于分位数的多值对象的KNN研究问题，为今后的算法研究奠定了基础。

关键词：分位数；KNN

分位数是大数据集和数据流上计算经常使用的一种统计方法，通过分位数查询能够获得统计信息以便为决策层提供数据支持。如果给出在d维空间的一组包含N个点集P及一个连续函数F且φ∈[0，1]，分位数查询检索在P中最小的第φN个F目标值。例如，中位数对应于0.5-分位数，而最大值是1分位数。分位数提供了数据分布的一个简洁的概要，主要应用于在线决策支持、数据挖掘、选择性估计、查询优化等。

1 分位数

分位数又称次序统计量，中位数是一个特例，分位数是关于数据分布的一个重要统计量。数据项完全有序数据集D的φ-quantile，就是使D中的秩（秩为数据集合的元素的个数）为φ|D|的那个元素，其中0

定义1.1（φ-分位数）：一个包含N个数据元素的有序序列的φ-分位数（φ∈（0，1]）就是秩为的元素「φN。分位数查询的结果就是具有给定秩的数据元素。

例如，在图1中显示了一个数据流产生数据的样本序列，其中每个数据元素由一个数据值表示，数据元素到达的顺序为从左至右，在序列中数据元素的数量是16，序列排序后的顺序为1，2，3，4，5，6，7，8，9，10，10，10，11，11，11，12。所以0.5分位数返回的是秩为8（=0.5*16）的元素，就是8；0.75分位数返回的是序列中秩为12的数据元素10。

2 KNN分析

最初的近邻法是由cover和Hart于1968年提出的，随后得到理论上深入的分析，是非参数法中最重要的方法之一。近邻法的一个严重问题是需要存储全部训练样本，以及繁重的距离计算量。

K最近邻（K-Nearest Neighbor，knn）是最近邻法的扩展，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一，是一种基于距离度量的分类方法。KNN在早期的研究策略中已被应用于文本分类。当K=1时的一种特定的NN（Nearest Neighbor），NN强调的是最近点的重要性，而KNN则从整体考虑，是一种更为普遍的方法。K最近邻居（KNN）查询在计算机科学中是一个古典问题。KNN查询目标是在数据集中找到距离查询点q最近的K个目标点。现有的算法主要是基于R树索引的查询算法，本文所采用的KNN算法主要是在一个AR树（聚合R树）中进行的。

在N∞的条件下，K-近邻法的错误率低于最近邻法，同时最近邻法和K-近邻法的错误率上下界都是在贝叶斯决策方法的1～2倍之间错误率的范围内。

KNN基本规则是：在所有N个样本中找到与测试样本的K个最近邻者，其中各类别所占个数表示成与ki，i=1，2，……，c。定义判别函数为：gi（x）=ki，其中i=1，2，……，c。决策规则为：argmaxgi（x），i=1，2，……，c。与投票表决一样，K近邻一般采用K为奇数，这样可以避免因2种票数相等而难以决策。

KNN方法的思路是：如果一个样本在特征空间中的K个最相似（即特征空间中最近邻）的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。

KNN算法也可应用于回归。通过在样本中找到的K个最近邻居，将这K个邻居的属性的平均值赋给该样本，就可以得到该样本的属性。同时更有效的方法是将距离不同的邻居对该样本产生的影响给定不同的权值（weight），例如权值与距离成正比。

定义1.2（K-最近邻居）：给定一个曲面散乱点集P={Pi（xi，yi，zi），i=1，2，…n}，设某个点为V（xv，yv，zv），则称P中距离点V最近的K个点为点V的m邻域点集，记为：MNB|V|=（P1，P2，…，Pm），称为点V的K-近邻，它反映了该点V的局部信息。K近邻中的每个点称为点V的邻近点。

K最近邻查找有很多应用，包括数据挖掘、多媒体、图像处理和监测移动对象。考虑一个移动电话公司已经进行的一项调查是关于客户对最喜欢的服务计划的选择。例如在图2中，2个维度捕捉了一个月内计划的2个属性（例如，价格和air-time数量）。每个白点表示客户对这些属性的选择，假设公司计划启动一项新的计划对应于黑点q，为了评价q的潜在的市场流行度，管理者想要的是在q和客户选择之间的相似点的分布。为了这个目的，F可能由在q和白点之间的欧几里德距离定义，同时检索不同φ值的分位数。作为另一个空间形式的例子，假设在2中的点q是一个比萨店，而白点对应的是住宅建筑，对于商店的拥有者来说这个住宅建筑距离中位数的非常有用的，它可以为比萨外卖计划配备充足数量的员工。在图2中的查询是一个单源查询，因为数据点集的排序只取决于一个源。

3 多值对象的KNN研究展望

最近邻居（NN）查询和K最近邻居（KNN）查询在数据库研究中是非常重要的查询类型。在不同的背景环境下，多种形式的KNN查找被研究，包括道路网络、移动对象、连续查询等。传统KNN的只有一个查询结点，实际应用中可以有多个查询结点，由于查询点的数目以及它们在数据库空间中分布的任意性，使得多值对象KNN查询比只有一个查询点的KNN查询复杂得多，因此基于分位数概要的多值对象KNN是进一步研究的问题。

在许多应用中，像分析经济数据，通常被看作为多值对象。例如，为了对比在几个城市之间的家庭收入，经常从一个城市随机收集一组家庭集合的收入作为样本，那么城市即对比为样本集。在这个案例中，每一个城市都被表示为一个多值对象，每个值被看作是一个范例或是一个样本。再比如，对研究小组的评价其中每个研究小组都是一个多值对象，每个员工的教学与研究绩效评价都对应一个范例。由于各种因素，像在不同城市中样本有效性的不同，每个城市样本的数量是不同的。类似的，根据范例的含义，2个研究小组的大小也可能是不同的，如，家庭的大小和员工的职位，这些范例可能有不同的权重。同样，上述的体育实例中，每个球员都被视为一个多值对象的球员，其中球员每场比赛的统计（得分、助攻、篮板）都被视为具有相同权重的一个实例（其被标准化）。

上述实例包含了在一维空间的多值对象和单值点的查询，研究覆盖的数据对象是由在d维空间的多范例组成的，查询对象也可以由在d维空间的多范例组成。例如，在NBA中，通过对球员的统计（得分、助攻、篮板、抢断、盖帽）来衡量每场比赛的球员的成绩，都可以被看作是球员的一个范例，因此，每个球员都是一组范例。假设某个球队想和球员A签订一个合同，想找出球员A的市场价值，针对球员最近比赛的成绩，球队可能想找出top-k与A“相似”的且具有存在合同的NBA球员。然后，球队可以使用这K个球员的薪资信息来预测计划A的薪资等级。

4 结语

本文具体分析了分位数概要数据结构的主要特点，针对K-最近邻居算法特性及特点进行了详细的分析，展望了多值对象的KNN问题的主要应用，并给出了实际的案例。