动机
直方图先选定区域的宽度,再数有多少观测落在其中。近邻估计把问题倒过来:要收集指定数量的观测,需要多大的空间?数据密集时,所需半径小,估计密度便高。当固定宽度把密集区抹得太平,却又令稀疏区几乎没有观测时,这种做法特别自然。不过,看似简单的构造仍须指定距离、与距离相符的体积、近邻数目及边界处理方法。
密度是每单位体积的概率,只数近邻并不足够。若一个坐标以米量度,另一个以毫米量度,普通欧几里得(Euclid)球的实际意义便改变了。同样地,边界上的球可能伸入观测根本不可能出现的区域。把这部分体积也放进分母,即使样本很大,仍会造成系统误差。
本节从上述问题构造估计量,证明一个范围明确的一致性结果,并完整计算小样本的带宽比较。定理只涉及一个固定位置的密度,不是近邻分类定理,也不是所有位置的一致误差界或高维恢复保证。后三者需要各自的假设及论证。
定义
定义 24.1.1
(近邻半径与密度高度)
给定 、 及固定查询点 。采用欧几里得距离,令 为 中第 小的值。以 表示单位欧几里得球的体积,例如 、。当 时,定义
若已知支撑集 ,可改用 ,在该体积为正时定义 。
这是局部的密度高度估计,整个函数不一定积分为一。例如在一维、所有观测右方,半径为 ,因此尾部与 成比例,其积分发散。逐点估计仍可有意义,但不能自动把这个原始函数当作已归一化的概率模型来计算似然。采用归一化核函数的核估计,具有另一种全局归一化性质。
概念视角分析
以半径为带宽的核估计
由于没有距离相同的情况,恰有 个观测值落在与 距离不超过 的范围内。因此
这是以均匀球核为核函数的核估计,其带宽 随查询点和数据而变。固定带宽的核估计固定宽度,让个数变动;近邻规则则固定个数,让宽度变动。
若观测有 Lebesgue 密度,对固定查询点,距离几乎必然不为零,也没有并列,因为球面具有零 Lebesgue 测度。重复或经四舍五入的读数可能不符合这个理想化模型;应交代并列规则及量度模型,不能直接除以零。若改用另一个范数的距离,也须把 改为该范数单位球的体积。
定义 24.1.2
(多变量核带宽)
对称正定矩阵 定义高斯(Gauss)核
这里 是协方差带宽矩阵,其特征值是平滑宽度的平方。若 ,平滑宽度是 ,不是 。非零的非对角项容许沿旋转后的椭球平滑。
线性改变量度单位时,体积也要一同改变。若 ,其中 可逆,相应带宽满足 ,密度则满足 。标准化坐标中的密度图有不同的数值高度;加入 Jacobian 因子后,所代表的概率质量才保持不变。
定理与命题
定理 24.1.3
(正连续密度位置的近邻逐点一致性)
固定维数 ,设 独立同分布,在 上有共同 Lebesgue 密度 。固定一个 连续且 的位置 。整数序列 满足 、 及 。则
支撑集版本可在固定 使用,但须明确假设:对所有充分小的正 ,,而且
此版本的观测支撑于 , 表示上述局部密度极限,估计量改用 。它不要求把密度在支撑集外延为零后,仍在边界连续。
定理 24.1.4
(反射构造归一化的半直线核估计)
设 , 是实直线上的非负对称密度。对 及 ,定义
这个函数非负,在 上积分为一。若观测均匀分布于 ,且 ,则对 ,反射估计在零的期望等于一,普通未反射估计在零的期望则为 。这个精确结果消除了本例的主要边界误差,并不是一般无偏性宣称。
定理 24.1.5
(把当前观测留出的积分误差分数)
固定正定矩阵 ,设 个独立观测来自 。令
则 ,并且
因此可用完全可计算的分数比较预先列明的有限带宽网格。期望恒等式对每个固定矩阵成立;选出的最小分数不因此成为所选程序风险的无偏估计。
证明与思路
证明
(先控制概率质量,再把质量换成体积)
记 ,这是连续的距离分布函数。概率积分变换给出独立均匀变量 ,且几乎必然有 。第 顺序统计量的密度是
推导时,选出哪 个均匀变量在 下方、哪一个落在 附近的小区间、哪 个在上方,再除以区间宽度。对这个 beta 密度积分,得到
取 , 的均值趋于一,方差不超过 ,故 Chebyshev 不等式推出 依概率成立。又因 ,有 依概率成立。局部密度为正先保证充分小半径的 ,再由单调性推得每个固定 都成立。事件 蕴含 ,从而 依概率成立。
由 在 连续,
因此
支撑集版本以 取代 ,并使用已明确假设的局部平均极限。该极限亦保证小 时 ,概率质量的计算则完全相同。本证明没有给出均方速率,也没有证明所有位置上的一致收敛。
证明透视
两个近邻条件各自负责不同工作
令邻域缩小,使局部平均接近查询点的密度; 则使随机概率质量相对于 稳定。邻域可以不断缩小,却始终只含太少观测,因而密度高度仍很不稳定。下文“常见误解”中固定一个近邻的反例,正好把这种失败单独展示出来。
证明
(反射归一化与积分误差分数)
对每个非负观测,两个反射项的总积分经换元后为
最后一步使用对称性。取平均便证明归一化。在零点,箱形核的反射项令普通项加倍。均匀观测在距离零不超过 的概率为 ,所以两种期望分别为 与 。
对误差分数, 与把它留出后的估计独立,故
使用 个与 个观测的估计有相同期望。展开积分平方误差,即得期望恒等式。最后,对两个高斯核的乘积配方,可得 ;加总便得到可计算公式。固定 时高斯核有界且可积,在 下所需积分及期望均有限。
算例
例题 24.1.6
(五个观测与真正算出的边界修正)
取 ,观测为 。在 ,距离依次为 。若 ,半径是 ,高度为 。若 ,半径为 ,高度便是二。两者都由同一样本算出;高度较大不代表较小邻域估计得较准。
若已知支撑为 ,在零点取 ,半径为 。未修正高度是 ,但可用区间只有 ,因此支撑修正高度为 。加倍补回边界上不可用的半个球,并没有令有限随机估计必然等于真实均匀密度一。
另用反射箱形核估计同一样本,取 。刚好有两个观测在零点距离 内,普通 KDE 高度是 ,反射高度为一。整个反射函数在半直线归一化;若把普通 KDE 在所有位置直接加倍,整条实直线上的质量亦会加倍,并不是同一个构造。
例题 24.1.7
(正方形样本的两个完整矩阵带宽分数)
取四点 ,令 。在 ,四个高斯项相同,所以
若 ,高度为 ;若 ,则为 。行列式降低高度,而第二坐标宽度增大又改变了指数,两项影响都不能省略。
积分平方项含四个自身配对、四个有序水平配对、四个有序垂直配对及四个有序对角配对。每个留出点的其他三点,则分别为一个水平、一个垂直及一个对角近邻。因此
算得 、。这两个预先指定的候选中,第二个分数较小。分数可以为负,因为其期望已减去未知常数 。四个观测并不能证明这个带宽在总体上最优。样本在交换坐标后不变,因此旋转选择 在此给出同分。
例题 24.1.8
(改变单位而保持估计概率质量)
设 坐标的带宽为 ,量度坐标为 ,。则 。由于 ,相应位置的密度高度相同,但圆形平滑区域变成椭圆。若改用 ,则 ,高度除以 1000。数值下降反映坐标体积变大,不是概率流失。
常见误解
反例模式
只取一个最近邻,高度可以永远不稳定
人们很容易以为,既然半径随 增大而缩小,只取一个最近邻就足够。事实并非如此。设观测均匀分布于 ,固定 及 。对固定 ,当 大至 时,
因为高度大于 ,恰好等价于至少一个观测落在半径 内。取 ,极限概率为 ,但真实密度是一,所以估计不依概率收敛至一。仅有半径缩小,不能取代 。
密度高度以样本数及实际体积去除计数。 近邻分类器则比较选定近邻内的标签比例:标签 的后验估计为 ,没有球体积分母。本节密度定理既没有证明分类一致性,也没有证明把估计密度代入决策后达到最优风险。即使另一个近邻方法采用看似相近的条件,仍须分清估计目标与证明。
常见错误
(自身计数与由数据选出的带宽)
若把 改为 ,便加入随带宽缩小而增大的自身核值 ,可能奖励过度集中的尖峰。留出估计的分母是 。若带宽或缩放矩阵由同一批观测选出,它就是随机的,不能只把实现值称为固定矩阵,便重用固定 的期望证明。
常见错误
(验证数据泄漏)
评估完整拟合程序时,应先指定候选族与评分规则,保留独立外层评估数据,并把均值、尺度、支撑估计及带宽选择全部放在开发数据内。若验证程序会学习尺度,每折都须只以该折训练部分重估尺度,再把存储好的转换用于验证部分。选好程序后,在全部开发数据重拟合,最后只查看未接触的测试数据一次。已知物理支撑可预先固定;若支撑由全部观测的极值推断,便已用了验证观测。以上精确分数是透明的固定带宽比较,不是完整的选模后不确定性分析。
小结
近邻密度构造先估计小区域的概率质量,再除以相应可用体积。逐点一致性证明同时需要近邻数增加及质量比例缩小。反射给出归一化的半直线核估计,矩阵带宽则以有意义的量度单位描述多变量平滑。留出积分误差分数可以实算,但选出的最小值不是独立风险证据。
练习
快速检查
(对上述五个观测,在查询点一取两个近邻,已知支撑为 [0,1]。计算普通与支撑修正的密度高度。)
先找第二近观测,再算实际可用区间长度。
解答 · 答案
至一的距离为 ,第二近半径是 。普通高度为 ;可用区间为 ,长度 ,故修正高度是二。修正的是可用体积,不是样本波动。
快速检查
(观测均匀分布于 [0,1],查询零点,固定 k 大于一。求支撑修正高度 k/(n R) 的精确期望,并解释 k 等于一时的情况。)
半径是 n 个独立均匀变量的第 k 顺序统计量;把 beta 密度除以其自变量后积分。
解答 · 答案
半径的 beta 密度为 。当 ,beta 积分给出 ,故 。即使已修正边界体积,有限样本的均值仍向上偏。当 ,零附近的积分含 而发散。依概率收敛不能直接推出期望收敛;本节定理刻意没有作出这种宣称。
快速检查
(若积分误差分数改在每个观测处使用完整估计,而非留出估计,自身计数项有何改变?所有带宽宽度趋于零时,为何危险?)
把完整估计写成自身项加上留出估计的 (n−1)/n 倍。
解答 · 答案
令 。则 ,所以错误分数减去正确分数为 。当 ,额外的负自身项发散。特别地,若固定观测互异且 ,非对角核值趋于零,而积分平方的对角项为 。错误分数遂如 ,反而奖励任意狭窄的尖峰。
快速检查
(二维密度在 坐标的带宽为 ,改用 。求新带宽与密度高度倍数,并指出逐点近邻定理是否证明了分类一致性。)
分别变换协方差带宽及体积。
解答 · 答案
新矩阵为 。高度乘以 ,相应体积乘以六,故所表示的概率质量不变。定理只在列明的密度假设下,证明固定位置的密度一致性,没有推导分类一致性。