下载掌阅APP，畅读海量书库
立即打开
k近邻算法主要思想是对未标记样本的类别，由距离其最近的k个邻居投票来决定属于哪个类别。假设有一个已标记好的数据集，此时有一个未标记的数据样本，我们的任务是预测出这个数据样本所属的类别。kNN的原理是：计算待标记样本和数据集中每个样本的距离，取距离最近的k个样本。待标记的样本所属类别就由这k个距离最近的样本投票产生。
假设X_test为待标记的样本，X_train为已标记的数据集，算法原理描述如下：
（1）遍历X_train中的所有样本，计算每个样本与X_test的距离，并把距离保存在数组D[]中。
（2）对数组D[]进行排序，取距离最近的k个点，记为X_knn。
（3）在X_knn中统计每个类别的个数，即class0在X_knn中有几个样本；class1在X_knn中有几个样本等。
待标记样本的类别，就是在X_knn中样本个数最多的那个类别。
例如，在图2-1中，有两类不同的样本数据，分别用三角形和正方形表示，而中间的圆形表示的是待分类的数据，还不知道属于哪一类，我们用“？”标记。下面我们根据k近邻的思想为该圆形表示的样本进行分类。
图2-1 k近邻算法示例
如果 k =5，在圆形最近的样本点中，有4个正方形和1个三角形，根据少数从属于多数的原则，判定圆形这个待分类样本属于正方形表示的样本一类。
如果 k =11，在离圆形最近的样本中，有6个三角形和5个正方形，还是少数从属于多数的原则，判定圆形这个待分类样本属于三角形一类。
在机器学习算法中，当模型确定后，所有算法都将转化为对一个既定模型的参数学习，即参数估计。例如朴素贝叶斯就是一种参数估计方法，它是在概率密度函数形式已知的情况下，对部分未知参数进行求解。
非参数估计与参数估计不同，它是未对函数形式作出假设，直接从训练样本中估计出概率密度，然后对样本进行分类。最简单的非参数估计有直方图估计法、Parzen矩形窗估计及Parzen正态核估计方法。
对于随机变量
X
的一组抽样，即使
X
的值是连续的，我们也可以划分出若干宽度相同的区间，统计这组样本在各个区间的频率，并画出直方图。图2-2所示是均值为0，方差为4的正态分布直方图，其中，
x
为直方图个数，
f
（
x
）为概率密函数。我们对样本
X
分成
k
个等间隔区间，假设样本总数为
N
，每个区间内样本数为
q
i
，则每个区间的概率密度为
。因此，
x
处的概率密度估计可表示为：
在 x 处发生的概率为区间内样本数/（总的样本数/收集器的宽度）。直方图非参数密度估计的一般形式为：
其中， V 是包含 x 的容器（窗口）的宽度， N 是样例总数， k N 是 V 中的样例数。
当
x
为
d
维向量时，可以对每个维度的量都分成
m
个等间隔的区间，可以将整个空间分成
m
d
个小空间，每个空间大小为
，其中
volumn
i
为第
i
维分量每个区间大小。
图2-2 均值为0、方差为4的正态分布直方图
Parzen矩形窗是以目标样本 x 作为中心点，根据窗口大小 h ，判断样本落入以 x 为中心的窗口内的样本数，从而得到 x 的概率。Parzen矩形窗估计与直方图估计的区别是：Parzen矩形窗是根据目标样本点 x 确定矩形窗，直方图估计是先确定矩形窗，然后根据样本点找相应的矩形窗。假设 x ∈ R d 是 d 维的向量，每个区间是一个超立方体，它在每一维上的棱长都是h，则每个区域的体积为 V=h d ，若定义 d 维单位方窗函数，公式如下：
若
x
落入窗口内，函数
ϕ
（（
u
1
,
u
2
,...,
u
d
）
T
）的取值为1，否则取值为0。若确定一个样本
x
i
是否落在以
x
为中心、
h
为棱长的超立方体内，可通过
的取值进行判断。样本
X
落在
x
为中心的超立方体的样本数可写成：
将其代入公式2-2，可得到任一点 x 的概率密度估计：
其中，
称为核函数，且满足：
K
（
x
,
x
i
）≥0且∫
K
（
x
,
x
i
）
dx
=0。当满足：
时，称为Parzen矩形窗。
当 K （ x , x i ）满足公式2-6时：
也就是以样本 x i 为均值，协方差矩阵∑= ρ 2 Q的正态分布，一维情况为：
对于多维数据，为了简便运算，可以假设各维数据相互独立。若随机变量 X 与 Y 独立，则 X 与 Y 不相关，即相关系数ρ=0。
假设 p （ x ′）是 x ′的密度函数，向量 x 落在区域 R 的概率为：
N 个向量中 k 个向量落在 R 内的概率为：
k / N 的均值和方差分别为：
当 N →∞时，频率与概率的取值趋于相等，公式为：
当 N 足够小时， p （ x ）在 R 上是不变的，公式为：
公式2-12与公式2-13结合，结果为：
如何通过data-driven的方式估计参数呢？策略叫作triall-and-error，即不断试错，通过不断的迭代，根据误差反复调整参数使误差尽可能地降低，最终得到最优参数。