5
Debbie
Todd Kim Amy Wynette
女
男 女 女 女
1.8
1.95 1.9 1.8 1.75
中等
中等 中等 中等 中等
KNN的例子
序 号 1 2 3 4 5
姓名 Kristina Jim Maggie Martha Stephanie
性别 女 男 女 女 女
i i z
序 号 1 2 3 4 5 6 7 8 9 10
KNN的例子（1）
姓名 Kristina Jim Maggie Martha Stephanie Bob Kathy Dave Worth Steven 性别 女 男 女 女 女 男 女 男 男 男 身高 1.6 2 1.9 1.88 1.7 1.85 1.6 1.7 2.2 2.1 类别 矮 高 中等 中等 矮 中等 矮 矮 高 高
• 得到p的置信区间为：
2 2 2 N acc Z / 2 Z / 2 Z / 2 4 Nacc 4 Nacc2 2 2 N Z / 2
下表给出了在不同置信水平下 Z / 2 的值：
1
0.99
2.58
0.98
2.33
0.95
1.96
0.9
1.65
0.8
1.85
1.6 1.7 2.2 2.1 1.8 1.95 1.9 1.8 1.75
中等
矮 矮 高 高 中等 中等 中等 中等 中等
•对第7个记录d=< Kathy，女，1.6>，得到 N={<Kristina，女， 1.6>、< Bob，男， 1.85>、< Kathy，女，1.6>、< Martha， 女，1.88>和< Stephanie，女，1.7>}。 •对第8个记录d=< Dave，男，1.7>，得到 N={<Kristina，女， 1.6>、< Dave，男， 1.7>、< Kathy，女，1.6>、< Bob，男， 1.85>和< Stephanie，女，1.7>}。 •对第9和10个记录，没变化。 •对第11个记录d=< Debbie，女，1.8>，得 到N={<Kristina，女， 1.6>、< Dave，男， 1.7>、< Kathy，女，1.6>、< Debbie，女， 1.8>和< Stephanie，女，1.7>}。 •对第12到14个记录，没变化。
欧式距离来度量。
形象的例子
KNN的分类思想
如果它走路像鸭子, 叫声也像鸭子, 那么他可能就是只鸭子。
Compute Distance
Test Record
Training Records
Choose k of the “nearest” records
KNN的直观解释
1、定义的直观形式：
•找出与目标最接近的K个样本； •将目标划分到找出的K个样本中出现最频繁的类。
1.28
0.7
1.04
0.5
0.67
Z / 2
比较两个模型的性能
• 模型 M 1 ：检验集 D1 记录数 n1 错误率 e1 • 模型 M 2 ：检验集 D2 记录数 n2 错误率 e2 目标是检验 e1 与 e2 的观察差是否是统计显著 的。
比较两个模型的性能
• 令 d e1 e2 表示错误率的观测差，则d服从均 值为 d t ，方差为 d2 的正态分布。d的方差为：
比较分类器的方法
1.估计准确度的置信区间 2.比较两个模型的性能 3.比较两种分类法的性能
估计准确度的置信区间
通过将分类任务用二项式实验建模来 推导置信区间。二项式实验的特性如下： 1.N个独立实验，只有两种可能的结果。 2.每个实验成功的概率p是常数。
估计准确度的置信区间
• 令X是模型正确预测的记录数，p是模型真正准 确率。
身高 1.6 2 1.9 1.88 1.7
类别 矮 高 中等 中等 矮
“高度”用于计算距离，K=5，对<Pat，女， 1.6>分类。
6
7 8 9 10 11 12 13 14 15
Bob
Kathy Dave Worth Steven Debbie Todd Kim Amy Wynette
男
女 男 男 男 女 男 女 女 女
比较两种分类法的性能
• 假设用k折交叉验证的方法比较。 • 令 M ij 表示分类技术 Li 在第j次迭代产生的模型。 • 每对模型
M1j
和 M 2 j 在相同的划分j上进行检验。
• 用 e1 j 和 e2 j 分别表示他们的错误率，则 d j e1 j e2 j
比较两种分类法的性能
d • k充分大时， j 服从服从 均值为 d t ，方差为 cv 的正态分布，其中观察的差的总方差用下式 进行估计： 2 k j 1 d j d 2 ˆ d cv k (k 1)
• X服从均差为Np、方差为Np(1-p)的二项分布。
• 准确率acc=X/N服从均值为p、方差为p(1-p)/N 的二项分布
估计准确度的置信区间
• 当N充分大时，用正态分布来近似，推导 出acc的置信区间为：
P ( Z / 2
acc p Z1 / 2 ) 1 p(1 p) / N
cv
其中 d 是平均差。用t分布计算 d tcv 的置信区间：
d
cv t
ˆ d t1 ，k 1 d cv
最近邻分类
• 最近邻：和测试样例的属性相对接近的所有训练样例。 • k-最近邻：给定样例z的k-最近邻是指和z距离最近的k
个数据点。简称KNN。
• 邻近性度量：表示某种距离(或相似度)度量，常用
k值的确定
k太小了，最近邻分类器容易受到由于训 练数据中的噪声而产生过分拟合的影响。
那么如何确定 合适的k值呢？
k太大，最近邻分类器可能会误分类测试样例， 因为最近邻列表中可能包含远离其近邻的数据点。
• 确定K的值：通过实验确定。进行若干次 实验，取分类误差率最小的k值。
y ' arg max 多数表决：
e1 1 e1 e 2 1 e 2 ˆ n1 n2
2 d 2 d
在置信水平1 % 下，d t 的置信区间为：
ˆ d t d z / 2 d
比较两个模型的性能
例4.5解：错误率的观察差 d 0.15 0.25 0.1 假设 H 0：dt 0对H1：dt 0 估计方差计算如下：
v
( xi , yi )Dz
I (v y )
i
在多数表决方法中，每个近邻对分类的影响 都一样，这使得算法对k值的选择很敏感。降低k 的影响的一种途径就是根据每个最近邻 xi 距离 的不同对其作用加权： i 1 / d x' , xi 2。 w
距离加权表决：
y ' arg max
v ( xi , yi )Dz
w I (v y )
i i
算法
1. 令k是最近邻数目，D是训练样例的集合 ' ' 2. for 每个测试样例 z x , y do 3. 计算z和每个样例 ( x, y) D 之间的距 离 d ( x ' , x) 4. 选择离z最近的k个训练样例的集合Dz D 5. y ' arg max ( x , y )D I (v yi ) v 6.end for
“高度”用于计算距离，K=5，对<Pat，女， 1.6>分类。 •对T前K=5个记录，N={<Kristina，女， 1.6>、< Jim，男，2>、< Maggie，女， 1.9>、< Martha，女，1.88>和< Stephanie，女，1.7>}。 •对第6个记录d=< Bob，男，1.85>，得到 N={<Kristina，女， 1.6>、< Bob，男， 1.85>、< Maggie，女，1.9>、< Martha，女，1.88>和< Stephanie，女， 1.7>}。 •对第7个记录d=< Kathy，女，1.6>，得 到N={<Kristina，女， 1.6>、< Bob，男， 1.85>、< Kathy，女，1.6>、< Martha， 女，1.88>和< Stephanie，女，1.7>}。
“高度”用于计算距离，K=5，对<Pat，女， 1.6>分类。
•N={<Kristina，女， 1.6>、< Dave，男， 1.7>、< Kathy，女，1.6>、< Debbie，女， 1.8>和< Stephanie，女，1.7>}。 •对第15个记录d=< Wynette，女，1.75>， 得到N={<Kristina，女， 1.6>、< Dave， 男，1.7>、< Kathy，女，1.6>、< Wynette，女，1.75>和< Stephanie，女， 1.7>}。
（二）曼哈坦距离 对应元素间差值绝对值的和表示，即
d (a, b) xa1 xb1 xa 2 xb 2 xan xbn
欧几里得距离与曼哈坦距离的共同点 d (a, b) 0 (1)即距离是一个非负的数值 d (a, a) 0, d (b, b) 0 (2)自身的距离为0 d (a, b) d (b, a) (3)即距离函数具有对称性 (4)即距离函数满足三角不等式 d (a, b) d (a, k ) d (b, k )
