落园 » 统计学习精要(The Elements of Statistical Learning)课堂笔记(二十三):原型方法和最近邻KNN|专注经济视角下的互联网

统计学习精要(The Elements of Statistical Learning)课堂笔记(二十三):原型方法和最近邻KNN

笔记(二十二)需要等我找到上一本笔记本再说,暂时不知道扔到哪里去了...汗。届时补上。

这一章主要是讲的原型方法(prototype)和最近邻(KNN)。相对而言直觉更强,公式没那么复杂。

--------------------------笔记开始-------------------

1. 原型方法

1) 1-NN 最近邻居方法

最极端的情况:只找到最近的一位邻居。

数据集D=\{(x_{i},y_{i}),1\leq i\leq N\},输入x_{i},在\{x_{j},j\neq i\}中找到与x_{i}最近的邻居x_{k},输出x_{k}对应的类标记y_{k}

2) 类中心的方法

类中心: c_{k}=\frac{1}{N_{k}}\sum_{y_{i}=k}x_{i},1\leq k\leq K,相当于对于一群有着同样类标记的点,对x取平均。

输入:x_{i},而后在所有类中心中与其最近的类中心c_{l}

输出:c_{l}对应的类标记。

3) 对每个类可计算若干个“中心”(称之为原型或者样板,比如在每类中做聚类)。

输入:x_{i},而后在所有类中心中与其最近的类中心c_{l}

输出:c_{l}对应的类标记。

4) K-NN方法

输入:x_{i},在\{x_{j},j\neq i\}中找到与x_{i}最近的K个邻居。

输出:\max y_{k}(最多的那一类,从众原则的感觉)。

由于这一类方法都比较懒,所以称之为lazy learning methods.

2. K-NN方法的错误率(渐近性质)

1) 结果

P*(e)为Bayes分类器的错误概率(最优分类器);\bar{P}(e)为1-NN分类器的错误概率。

则有:当样本数N\rightarrow\infty时,P*(e)\leq\bar{P}(e)\leq2P*(e)。接下来会证明这个优良的性质。

2) 分类问题

给定(x,y),则P(x,y)=P(y)P(x|y)

这里我们称 P(y=k)=\pi_{k}为先验分布,P(x|y=k)=f_{k}(x)为类分布。从而

P_{k}(x)=P(y=k|x)=\frac{P(y=k,x)}{P(x)}=\frac{P(y=k)P(x|y=k)}{\sum_{k}P(x,y)}=\frac{\pi_{k}f_{k}(x)}{\sum_{k}\pi_{k}f_{k}(x)},称之为后验概率。

3) Bayes分类器

x对应的k=\arg\max_{k}P_{k}(x),即使得后验概率最大的k。

所以,P*(e|x)=P*(y\neq k^{*}|x)=1-P(y=k^{*}|x)=1-P_{k*}(x),从P*(e)=E_{x}[P*(e|x)]

4) 1-NN分类器

1-NN输出的是离x最近的\bar{x}对应的\bar{y},则

\bar{P}(e|x)=P(y\neq\bar{y}|x)=1-P(y=\bar{y}|x)=\sum_{k=1}^{K}P(y=k,y\neq\bar{y}|x)=\sum_{k=1}^{K}P(y=k|x)P(k\neq\bar{y}|x,y=k)

由于k\neq\bar{y}只限训练集,而y=k那部分只跟测试集有关,所以由独立性我们可以拆分为:

=\sum_{k=1}^{K}P_{k}(x)P(k\neq\bar{y}|x),则当N\rightarrow\infty时,x\rightarrow\bar{x},y\rightarrow\bar{y},上面一项可以收敛为\sum_{k=1}^{K}P_{k}(x)(1-P_{k}(x))=1-\sum_{k=1}^{K}P_{k}^{2}(x),为后验概率(条件误差)。

5)由于P*(e|x)=1-P_{k*}(x),设P_{k*}为所有P_{k}中最大的,则

\bar{P}(e|x)=1-P_{k*}^{2}-\sum_{k\neq k*}P_{k}^{2}\leq1-P_{k*}^{2}-\frac{1}{K-1}(1-P_{k*}^{2})=2P*(e|x)-P*(e|x)^{2}-\frac{1}{K-1}P*(e|x)^{2}

6)\bar{P}(e)=E_{x}[\bar{P}(e|x)]=E_{x}[2P*(e|x)-P*(e|x)^{2}-\frac{1}{K-1}P*(e|x)^{2}]\leq2P*(e)-\frac{K}{K-1}P*(e)^{2}\leq2P*(e)。得证。

下一章会讲到聚类,然后就是降维了。


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *