分类问题：
其输入是输入空间(mathcal{X} = mathbb{R}^d)中的(n)个样本(x_1, ldots, x_n)，输出是离散空间(mathcal{Y})中的某个值。当(mathcal{Y} = {-1,+1})或({0,1})时，问题是一个二元分类问题；当(mathcal{Y} = {1, ldots, K})时，问题是一个多元分类问题
分类问题使用函数(f)（即分类器）将输入(x)映射到类别(y)上，即(y = f(x))
近邻分类
其算法思想是，给定数据((x_1, y_1), ldots, (x_n, y_n))，构造分类器(hat{f}(x) rightarrow y)如下：
- 对于不在训练数据里的(x)，令(x_i)是((x_1, y_1), ldots, (x_n, y_n))中离(x)“最近”的点
- 返回其标签(y_i)
如何衡量(x)之间的距离？常见的是使用欧几里得距离，即 [ |!|u-v|!|_2 = left(sum_{i=1}^d (u_i - v_i)^2right)^{frac{1}{2}} ] 当然也可以使用其它衡量方法，例如(ell_p)、编辑距离（适用于字符串）或者相关距离（衡量两个向量的相关性）
k近邻分类
与原始的近邻分类类似，不过是选取“最近”的(k)个点，然后得票最多的类别是判定的类别
分类器有效的基本假定也是测试数据（未知数据）与训练数据（已知数据）独立同分布
贝叶斯分类
最优分类器
假设((X,Y) mathop{sim}^{iid} mathcal{P})，而且我们不知道(mathcal{P})的分布，那么关于分布(mathcal{P})有两个性质
- 一个事件的指示变量的期望是这个事件的概率。即若定义(mathbb{1}(cdot) = 0{rm or 1})取决于(cdot)是否为真，则有 [ mathbb{E}_P[1(Y=1)] = P(Y=1) ]
- 条件概率的期望可能会是随机变量，但是这个随机变量的期望是一个常数，即 [ C = mathbb{E}[A|B], mathbb{E}[C] = mathbb{E}[mathbb{E}[A|B]] = mathbb{E}[A] ]
对于任意分类器(f: mathcal{X} rightarrow mathcal{Y})，其预测误差为 [ P(f(X) not= Y) = mathbb{E}[1(f(X) not= Y)] = mathbb{E}[mathbb{E}[1(f(X) not= Y)|X]] ] 对每个(xin mathcal{X})，有 [ mathbb{E}[1(f(X) not= Y)|X=x] = sum_{y in mathcal{Y}} P(Y=y|X=x)cdot 1(f(x) not= y) ]
所以上式取得最小值的条件是分类器(f^star)对所有(x in mathcal{X})，都取 [ f^star (x) = {rm arg}max_{y in mathcal{Y}} P(Y=y|X=x) ] 对所有(x in mathcal{X})都具有这一属性的分类器(f)称为贝叶斯分类器，它在所有分类器中有最小预测误差
贝叶斯分类器
对于上式，根据贝叶斯定律，等价于有 [ f^star (x) = {rm arg}max_{y in mathcal{Y}} P(Y = y) times P(X = x|Y = y) ] 其中(P(Y=y))称为类别先验，(P(X=x|Y=y))称为(X)的类别条件分布（当(X)是连续随机变量时，(P(X=x|Y=y))写为(p(x|Y=y))，称为类别条件密度）。在实际中，这两个分布我们都不知道会是什么，所以只能去近似之
（以下四段摘抄于http://blog.csdn.net/zouxy09 ）
判别方法：由数据直接学习决策函数Y=f(X)或者条件概率分布P(Y|X)作为预测的模型，即判别模型。基本思想是有限样本条件下建立判别函数，不考虑样本的产生模型，直接研究预测模型。典型的判别模型包括k近邻，感知级，决策树，支持向量机等。
生成方法：由数据学习联合概率密度分布P(X,Y)，然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型：P(Y|X)= P(X,Y)/ P(X)。这样的方法之所以称为生成方法，是因为模型表示了给定输入X产生输出Y的生成关系。用于随机生成的观察值建模，特别是在给定某些隐藏参数情况下。典型的生成模型有：朴素贝叶斯和隐马尔科夫模型等。
生成方法的特点：上面说到，生成方法学习联合概率密度分布P(X,Y)，所以就可以从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度。但它不关心到底划分各类的那个分类边界在哪。生成方法可以还原出联合概率分布P(Y|X)，而判别方法不能。生成方法的学习收敛速度更快，即当样本容量增加的时候，学到的模型可以更快的收敛于真实模型，当存在隐变量时，仍可以用生成方法学习。此时判别方法就不能用。
判别方法的特点：判别方法直接学习的是决策函数Y=f(X)或者条件概率分布P(Y|X)。不能反映训练数据本身的特性。但它寻找不同类别之间的最优分类面，反映的是异类数据之间的差异。直接面对预测，往往学习的准确率更高。由于直接学习P(Y|X)或P(X)，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。
plug-in分类器
通常情况下，我们并不知道(P(Y=y|X=x), P(X=x|Y=y))和(P(Y=y))，我们只有从分布(mathcal{P})中得到的带标签的样本。但是按照道理来讲，在不知道(mathcal{P})的情况下我们无法构建贝叶斯分类器，所以需要用手头数据去估计(P(Y=y))和(P(X=x|Y=y))，其代价是得到的结果不会是最好的结果——这种分类器称为plug-in分类器
对于(mathcal{X} = mathbb{R}^d)和(mathcal{Y} = {1,ldots, K})，可以通过MLE来估计贝叶斯分类器。类别的先验的MLE估计(pi_y)为 [ hat{pi}_y = frac{1}{n} sum_{i=1}^n 1(y_i = y) ] 类别的条件概率密度可以假设为(p(x|Y=y) = N(x|mu_y, Sigma_y))，两个参数的MLE估计为 [ begin{align*} hat{mu}_y &= frac{1}{n_y} sum_{i=1}^n 1(y_i = y)x_i \ hat{Sigma}_y &= frac{1}{n_y} sum_{i=1}^n 1(y_i = y)(x_i - hat{mu}_y)(x_i - hat{mu}_y)^T end{align*} ] 对应的plug-in分类器为 [ hat{f}(x) = {rm arg}max_{y in mathcal{Y}} hat{pi}_y |hat{Sigma}_y|^{-frac{1}{2}}expleft{-frac{1}{2} (x - hat{mu}_y)^mathsf{T}hat{Sigma}_y ^{-1}(x-hat{mu}_y)right} ]
例如，在垃圾邮件分类器中，使用朴素贝叶斯，其假设(X)的各个维度在(y)下条件独立，忽略了它们之间的相关性使得概率容易算，即 [ p(X= x|Y=y) = prod_{j=1}^d p_j(x(j)|Y=y) ]
这时类别的先验为 [ P(Y=y) = frac{#{rm observations in class }y}{ {rm # observations}} ]
条件分布使用泊松分布，即 [ P(X=x|Y=y) = prod_j p_j(x(j)|Y=y) = prod_j {rm Poisson}(x(j)|lambda_j^{(y)}) ] 其中(lambda_j^{(y)})的MLE为 [ lambda_j^{(y)} = frac{#{rm unique uses of word }j{rm in observations from class }y}{#{rm observations in class }y} ]
原文:大专栏 EdX Columbia ML 7. K-最近邻分类与贝叶斯分类器