knn推导过程中的一个细节

  统计/机器学习 监督式学习    浏览次数: 482
1

周志华的书里关于knn的这一段,画出来的蓝圈里第一个“约等于”我可以理解,第二个“小于等于号”我就不明白了。

有知道的大牛分享一下思路吗?

谢谢!


 

剪叔   2017-12-20 13:24



   2个回答 
3

注意看第二段的最后一句话,根据这句话中$c^*$的意义,我们就知道,对于任意的$c$

$$P(c^*|x)\geq P(c|x)$$

对于k分类问题,$\mathcal Y$就有k个元素,那么蓝色框框里的式子就可以写成

$$1-\sum_{c\in\mathcal{Y}}P^2(c|x)\leq 1-kP^2(c^*|x)\leq 1-P^2(c^*|x)$$

这样看就很显然了



0101RG   2017-12-21 09:06

谢谢!写出来挺简单,自己想却想不明白了 - 剪叔   2017-12-22 13:41
这个结论挺有意思。kNN不会比naive bayes差太多。 - kykix   2018-04-16 12:37
注意结论的条件是在任意小距离内有训练样本,也就是说训练样本要无限多。相当于训练样本包括了所有的输入范围,这种情况下knn错误当然小了。 - Zealing   2018-04-16 13:06
第二个不等式中的第一个符号不对吧,应该是>= - xwemin   2018-06-04 21:17
3

0101RG 的推导有错误。

根据$\sum_{c\in Y} P(c|x)=1 \geq P(c^*|x)=max(P(c|x))$

有$\sum_{c\in Y} P^2(c|x)) \geq P^2(c^*|x)$

所以$1-\sum_{c\in Y} P^2(c|x) \leq 1-P^2(c^*|x)$

Zealing   2018-04-16 23:52

0101RG第二个式子,中间那一步似乎不对,$1−kP^2(c^*|x)$那里画蛇添足了 - 木子周   2018-04-17 09:57
第一步到第二步不准确,看推导是两边平方得出的;但是左边应该是和的平方,不是平方的和,应该加一步,和的平方大于平方的和,容易被误导 - xwemin   2018-06-04 21:26


  相关主题

线性可分是什么意思?   1回答

k-NN的k取1会怎么样   3回答

kNN的k=1为什么训练误差为0?   3回答

adaboost里的learning rate是什么意思?   1回答

支持向量机(SVM)里的支持向量是什么意思   5回答

欠采样后概率还原问题   0回答

python里如何实现线性判别分析(LDA)?   1回答

逻辑回归的前提假设是什么?   1回答

线性回归的bagging   2回答

可以对线性回归进行boosting吗?   3回答

GBDT+LR的工作原理?   3回答

python中可以做beta regression的包?   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!