聚类与最近邻方法只依赖一个输入:两个观测值相距多远,或有多相似。质心方法需要平方欧氏距离(Euclidean distance),层次聚类需要所有点对之间的距离,k 近邻分类则按距离为训练样本排序。距离或特征尺度一变,这些方法给出的答案可以完全不同,所以选择必须明确交代并有所依据。本节列出标准的度量、其中哪些是真正的度量,以及使数值特征可以互相比较的预处理。
度量与常用量度
定义 14.1.1
(度量与 Minkowski 族)
集合 上的函数 是度量,若对所有 :; 当且仅当 ;;以及 (三角不等式)。对 定义
它们分别是曼哈顿距离(Manhattan distance)、欧氏距离与切比雪夫(Chebyshev)距离。
定理 14.1.2
(三种距离都是度量)
、 与 都是 上的度量。
证明
(证明)
非负性、对称性,以及“ 只在每个坐标都相等时成立”,都可直接由公式看出。至于 与 的三角不等式,对每个坐标使用 ,再求和或取最大值;和的最大值不超过最大值的和。对 ,令 ,。由柯西–施瓦茨(Cauchy–Schwarz)不等式 ,得 。两边开方即得 。
证明透视
柯西–施瓦茨在欧氏三角不等式中的位置
只有三角不等式需要想法,而对 来说,想法就是取平方。令 、,要证的就是 。两边都非负,所以它等价于 。展开后只剩一个交叉项 ,而柯西–施瓦茨是唯一不属常规的一步:它把该项限制在 以内。当 与 是同一向量的非负倍数时等号成立,也就是 落在 到 的线段上。
最后的开方,才把平方后的不等式还原为 的不等式。对 ,同样的展开需要 ,即 ;在共线的点 上,、,这并不成立。
平方欧氏距离不是度量:数轴上的点 有 。然而 k-means 目标用的正是这个量。
概念视角几何
三种单位球
从几何上看,三种距离的区别在于“与中心的距离不超过一”的点集形状。在平面上,这个单位球对 是菱形,对 是圆盘,对 是边与坐标轴平行的正方形。由于 逐点成立,菱形包含于圆盘之内,圆盘又包含于正方形之内。以 为中心时,点 的三个距离分别是 、 和 :它在菱形的边界上,却远在正方形之内。
定义 14.1.3
(余弦相似度、Jaccard 相似度与 Hamming 距离)
对非零的 ,余弦相似度为 ,余弦相异度为 。对不同时为空的有限集合 ,Jaccard 相似度为 ,Jaccard 距离为 。对两个等长字符串,Hamming 距离是它们不同位置的个数。
余弦相似度不理会向量长度,适合比较长度不同的文档的词数向量: 与 的余弦相似度为 ,但欧氏距离为 。
命题 14.1.4
(单位向量上的余弦与欧氏距离)
若 ,则 。因此在单位向量之中,以固定单位向量 为基准,按欧氏距离由小到大排序,与按余弦相似度由大到小排序结果相同。
证明
(展开平方范数)
,而两个范数都是 1,所以 。映射 严格递减,所以它把余弦值的顺序反转。
反例模式
余弦相异度不是度量
它非负而且对称,所以有人可能声称 是度量。取 、、。则 ,所以 ,而 给出 。因为 ,三角不等式不成立。同一性公理也不成立: 与 是不同的点, 却为 。方向之间的夹角 避开了这两个问题。
夹角 本身则是方向之间的度量,但此处不证明。Jaccard 距离与 Hamming 距离都是度量;我们不加证明地引用这个标准事实。
缩放数值特征
欧氏距离把各特征的平方差相加,所以数值范围大的特征会主导总和。两种常见补救方法,是用训练数据分别重新缩放每个特征。
定义 14.1.5
(最小最大缩放与标准化)
设某特征的训练值最小为 ,最大为 ,均值为 ,总体标准差为 。最小最大缩放把值 变为 ,使训练范围落在 。标准化(z 分数)把 变为 ,使训练值均值为 、方差为 。常数特征有 及 ,必须剔除或不缩放,因为公式没有定义。
常数 只用训练数据拟合,之后原封不动地应用于验证与测试数据。若在合并的数据上计算,测试信息会影响变换,这是一种泄漏,会使评估过于乐观。落在训练范围之外的测试值会被映射到 之外,这是正确的行为,不应不声不响地截断。
例题
例题 14.1.6
(缩放可以改变最近邻)
四位客户的(年龄,收入)为 、、、。未缩放时,从 出发的欧氏距离为 、、,故最近邻是 :收入一列主导了距离,而 最近,只因它的收入与 相同。
以训练范围作最小最大缩放:年龄 至 ,收入 至 。缩放后的点为 、、、。从 出发的距离, 为 , 为 , 为 。现在最近的是 。两个答案在抽象意义上都没有“正确”与否;缩放后的版本把任一特征上一个全范围的差异视为同样大,这是建模选择,应有意为之。
例题 14.1.7
(以训练统计量标准化,以及集合与向量度量)
某训练特征的值为 。均值 ,平方偏差为 ,总和 ,所以总体方差为 ,。标准化后的训练值为 。测试值 以训练的 与 变为 。若把 计入再重算统计量,均值会变为 ,并在不知不觉间改变每一个变换后的值。
对集合 与 ,,,所以 ,Jaccard 距离为 。
例题 14.1.8
(最小最大缩放下的离群值与常数特征)
某特征的训练值为 。则 、、,缩放后的值为 ,约为 。若没有离群值,范围是 ,四个普通值会映射到 。现在普通点之间相差一个单位,只对缩放后的坐标贡献 ,而不是 ,所以这个特征几乎不影响它们之间的距离。
第二个特征在每个训练行都取 。则 , 是 ,标准化的 。这个特征无法区分训练行,所以缩放前须先移除(或不缩放),并预先规定处理策略。
常见错误与细节
常见错误
(缩放并非没有代价,距离也必须匹配数据类型)
把本来已在有意义的共同尺度上的特征标准化,可能抹去有用的信息。最小最大缩放对单个离群值很敏感,它会拉大 ,把其余所有值压缩。把二值指示特征写成 与 并用欧氏距离,等于暗中计算不匹配的个数;这是否合用,应当决定,而非假设。最后,三角不等式之所以重要,是因为有些算法(例如剪枝近邻搜索的算法)只对度量才正确;未经检查,不要在那里改用余弦相异度。
练习
快速检查
(1. 比较三种距离)
计算 与 之间的 。
解答 · 解答 1
各坐标差为 。所以 ,,。
快速检查
(2. 缩放一个测试值)
某特征的训练值为 。以训练统计量,求新测试值 的最小最大值与 z 分数。
解答 · 解答 2
训练最小值与最大值为 与 ,故最小最大值为 ,如预期落在 之外。以 、 计,z 分数为 。
快速检查
(3. Jaccard 距离)
计算 与 的 Jaccard 距离。
解答 · 解答 3
有 个元素, 有 个。所以 ,距离为 。
快速检查
(4. 单位向量上的余弦与欧氏距离)
设 ,。验证两者都是单位向量,计算 与 ,并核对恒等式 。
解答 · 解答 4
,。余弦为 。又 ,而 ,与恒等式一致。