统计学习方法——k临近模型

//2021年11月30日14点19分

//参考资料《统计学习》

//内容：k临近与一些聚类方法

========================================================================================================================

先来看KNN的概要

　　输入：训练集数据

　　　　$T = \{(x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N)\}$

　　　　其中，$x_i\in \chi\subseteq \mathbf{R}^n$为实例的特征向量；$y_i\in \gamma =\{c_1,c_2,\ldots,c_K\}$为实例的类别，$i=1,2,\ldots,N$;实例特征向量$x$。（这里开始读的时候有点奇怪，后面发现$x$对应的是待分类的训练集数据）

　　　　也就是说对于$(x_i,y_i)$，$x$是数据（或数据的特征向量），$y$是标签。

　　输出：实例$x$所属的类$y$

　　算法：

1. 根据给定距离度量，在训练集$T$中找出与$x$最邻近的$k$个点，涵盖这$k$个点的$x$的邻域记作$N_{k}(x)$;
2. 在$N_{k}(x)$中根据分类决策规则（如多数表决）决定$x$的类别$y$;

　　　　　　$y=argmax_{c_j}{\sum_{x_i \in N_{k}(x)}I(y_i=c_j)}, \quad i=1,2,\ldots,N;j=1,2,\ldots,K$

　　　　　　式中，$I$为指示函数，当$y_i =c_j$时$I=1$否则为0。

　　　**KNN没有显式的学习过程（所谓显式学习是否是力学下的显式概念？）**??这个疑问没有解决

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

然后是KNN的模型

　　我从算法流程中观察到KNN的几个关键要素，并大概对KNN的模型有一定认知。

　　训练集：

　　　　$(x,y)$

　　距离度量：

　　　　特征空间中的两个实例点的距离是两个实例点相似程度的反应。??（这句话绝了，高度概括了特征在聚类任务中扮演的角色。）

　　　　k邻近模型的特征空间一般是$n$维实数向量空间$\mathbf{R}^n$，一般用$L_p$距离（Minkowski distance）??（这里省略了大部分定义的内容）

　　　　$L_p(x_i,x_j)=(\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|^p)^{\frac{1}{p}}$

　　　　$p=1$称为曼哈顿距离；

　　　　$p=2$称为欧式距离；

　　　　$p=\infty$是各个坐标的最大值（切比雪夫距离）；??（矩阵论上划的水，现在的泪）

　　$k$值：

　　　　$k$值的选择对KNN结果会产生重大影响；

　　　　影响的主要评价指标是：

　　　　　　近似误差（approximation error）:

　　　　　　估计误差（estimation error）:

　　　　那么我们讨论$1

　　　　　　$k$较小时，approximation error 较小，estimation error 较大??

　　　　　　$k$较大时，approximation error 较大，estimation error 较小??（$k$越大，被预测出现错误的概率越大。错误分为是该类的没被分到该类，不是该类的被分入该类）

　　　　到$k=N$时：

　　　　　　无论输入实例是什么，都将其预测为训练实例中最多的类。

　　　　**一般采用交叉验证法取一个较小的$k$值** 　　　　　　

　　分类决策规则：

　　　　多数表决：

　　　　　　由输入实例的$k$个邻近的训练实例中多数类决定输入实例的类。

　　　　　　其解释为：如果分类的损失函数为0-1损失函数，分类函数为$f:\mathbf{R}^{n}\to\{c_1,c_2,\ldots,c_K\}$；

　　　　　　误分类概率：误分类概率=1-分对的概率；??（这还是个均匀分布）

如上吧啦吧啦了一堆，那么KNN的实现kd树（$k-dimension tree$）：

= ========================================================================================================================

在倒回到“聚类方法中”，“聚类”与“KNN“到底有什么样的联系？

　　同样的我们有：

　　输入:

　　　　$ X=[x_{ij}]_{m\times n}=\begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1n}\\ x_{21} & x_{22} & \cdots & x_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m1} & x_{m2} & \cdots & x_{mn} \\ \end{pmatrix}$

　　　　从这里看到我们有$x_{1\times j}$的样本，有$x_{i\times 1}$的特征。??（如果我们输入数据可以由矩阵形式写出，相应的我们可以利用矩阵运算出$X$的聚类结果）

　　　　??（我想为什么样本是$x_{1\times j}$而不是$x_{j\times i}$。后来发现，样本是一个一个按顺序放入算法的，那从左到右排列样本符合我们的一般阅读习惯，哈哈。）

　　输出：实例$x$所属的类$y$

那么“聚类”和“KNN”哪里不一样了？

　　聚类有多种相似度（similarity）和距离（distance）的定义（以下举例为书中使用的例子）：

　　　　①闵可夫斯基距离（上文KNN中已经讲到）：$L_p(x_i,x_j)=(\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|^p)^{\frac{1}{p}}$；

　　　　②马哈拉诺比斯距离：

　　　　　　　　马氏距离考虑各个分量（特征）之间的相关性并于各个特征分量的尺度无关

　　　　　　　　定义：给定一个样本集合$X$,$X=[x_{i,j}]_{m\times n}$，其协方差矩阵记作$S$。样本$x_i$与样本$x_j$之间的马氏距离$d_ij$为

　　　　　　　　　　　　$d_{ij}=[ (x_{i}-x_{j})^{T} S^{-1} (x_{i}-x_{j}) ]^{\frac{1}{2}}$

　　　　　　　　　　其中，$x_{i}=(x_{1i},x_{2i},\ldots,x_{mi})^{T}$,$x_{j}=(x_{1j},x_{2j},\ldots,x_{mj})^{T}$

　　　　　　　　　　当$S$为单位矩阵时，即样本数据的各个分量相互独立（$j$个样本，$X$的列秩为$j$）且各个分量的方差为1（这里应该讲的是standardized eucildean distance）时，马氏距离就是欧式距离，所以马氏距离是欧式距离的推广。

　　　　　　　　　　这里就要问一句为什么马氏距离是这样设计的？??（这里先挖坑，后面填）

　　　　③相关系数（correlation coeffcient）：

　　　　　　　　相关系数的绝对值越接近1，表示样本越相似，以此也可以作为聚类的标准。

　　　　　　　　定义：样本$x_i$与样本$x_j$之间的相关系数定义为

　　　　　　　　　　　　$ r_{ij}=\frac{\sum_{k=1}^{m}(x_{ki}-\overline{x}_{i})(x_{kj}-\overline{x}_{j})}{[\sum_{k=1}^{m}(x_{ki}-\overline{x}_{i})^{2}\sum_{k=1}^{m}(x_{kj}-\overline{x}_{j})^{2}]} $??（这里公式有点小）

　　　　　　　　　　　　其中，$\overline{x}_i=\frac{1}{m}\sum_{k=1}^{m}x_{ki}$，$\overline{x}_{j}=\frac{1}{m}\sum_{k=1}^{m}x_{kj}$。??（求均值）

　　　　④夹角余弦（cosine）：

　　　　　　　　夹角余弦越接近于1，表示样本越相似。

　　　　　　　　定义：样本$x_i$与样本$x_{j}$之间的夹角余弦定义为

　　　　　　　　　　　　$s_{ij}=\frac{\sum_{k=1}^{m}x_{ki}x_{kj}}{[\sum_{k=1}^{m}x^{2}_{ki}\sum_{k=1}^{m}x^{2}_{kj}]^{\frac{1}{2}}}$

　　　　**总结一下上文提到的距离或者相似度度量，发现选用何种度量方式和特征向量长啥样直接相关**

“聚类”的“类”或者“簇”

　　通过聚类得到的类或者簇，本质是样本的子集。

　　假定一个样本属于一个类，或类的交集属于空集??（此为硬聚类 hard clustering）

　　一个样本属于多个类，或类的交集不为空集??（此为软聚类 soft clustering）

　　书中只讲述了硬聚类的方法。

　　用$G$表示类或者簇（cluster），用$x_i$,$x_j$表示类中样本，用$n_G$表示$G$中样本的个数，用$d_{ij}$表示样本$x_{i}$与$x_{j}$之间的距离。

　　现给出几个常见定义

　　　　定义1：设$T$为给定的整数，若集合$G$中任意两个样本$x_{i}$，$x_{j}$，有 ??（翻译翻译就是距离小于$T$的都是一类或者簇）

　　　　　　　　$d_{ij}\leq T$

　　　　　　　则称$G$为一个类或者簇。

　　　　定义2：使$T$为给定的正数，若对集合$G$的任意样本$x_{i}$，一定存在$G$中的另一个样本$x_{j}$，使得 ??（翻译翻译就是只要有数据且$i>1$那就能聚出一类或簇）??（存在定理？）

　　　　　　　　$d_{ij}\leq T$

　　　　　　　则称$G$为一个类或簇。

　　　　定义3：设$T$为给定的整数，若对集合$G$中任意一个样本$x_{i}$，$G$中的另一个样本$x_j$，使得 ??（翻译翻译就是距离度量均值小于$T$的都是一类或簇）

　　　　　　　　$\frac{1}{n_{G}-1} \sum_{x_{j}\in {G} } d_{ij}\in T$

　　　　　　　其中$n_{G}$为$G$中样本的个数，则称$G$为一个类或者簇。

　　　　定义4：设$T$和$V$为给定的两个正数，如果集合$G$中任意两个样本$x_{i}$，$x_{j}$的距离$d_ij$满足 ??（翻译翻译就是这是按数据特征向量的部分元素聚类）

　　　　　　　　$\frac{1}{n_{G}(n_{G}-1)} \sum_{x_{j}\in {G} } \sum_{x_{j}\in {G}} d_{ij}\in T$

　　　　　　　　$d_{ij}\leq V$

　　　　　　　则称$G$为一个类或者簇

　　　　**定义1可推广得其他定义**

　　　　**不难看出定义4是定义3的严格版本**

　　对于“类”的特征还有以下一些刻画

　　　　①类的均值$\overline{x}_G$，又称类的中心

　　　　　　　　$\overline{x}_{G}=\frac{1}{n_G}\sum_{i=1}^{n_G}x_i$

　　　　②类的直径（diameter）$D_G$

　　　　　　　　$D_G=\underset{x_{i},x_{i}\in G}{max}d_{ij}$

　　　　③类的样本散布矩阵$A_G$（scatter matrix）

　　　　　　　　$A_{G}=\sum_{i=1}^{n_G}(x_{i}-\overline{x}_{G})(x_{i}-\overline{x}_{G})^{T}$

　　　　④类的样本协方差矩阵$S_G$(covariance matrix)

　　　　　　　　$S_G =\frac{1}{n_{G}-1}A_{G} =\frac{1}{n_{G}-1}\sum_{i=1}^{n_G}(x_{i}-\overline{x}_{G})^{T}$

　　类与类之间也存在距离

　　　　如果有一数据$G$中两个类$G_p$和$G_q$，他们之间的距离表示为$D(p,q)$，也称其为链接（linkage）。

　　　　设类$G_p$包含$n_p$个样本，$G_q$包含$n_q$个样本，分别用$\overline{x}_p$和$\overline{x}_q$表示$G_p$和$G_q$的均值（类的中心）

　　　　①最短距离（单链接 single linkage）:$D_{pq}=min\{d_{ij}|x_{i}\in G_{p},x_{j}\in G_{q}\}$

　　　　②最长距离（完全链接 complete linkage）:$D_{pq}=max\{d_{ij}|x_{i}\in G_{p},x_{j}\in G_{q}\}$

　　　　③中心距离：$D_{pq}=d_{\overline{x}_{p}\overline{x}_{q}}$

　　　　④平均距离：$D_{pq}=\frac{1}{n_{p}n_{q}}\sum_{x_{i}\in G_{p}}\sum_{x_{j}\in G_{q}}d_{ij}$

========================================================================================================================

　　到此，我们返回聚类的几种方式

　　　　首先是层次聚类的两种方式：

　　　　①聚合（agglomerative）$\to$自下而上（bottom-up）??（以下聚类方法均为聚合式）

　　　　③分裂（divisive）$\to$自上而下（top-down）

　　　　这种分类方式假设的是数据有层次结构，他是一种hard clustering。

　　聚合聚类的流程是：

　　　　　　　for $i=1\ldots j$　
　　　　　　　　　将每个样本各自分到一个类；??（$j$个样本有$j$个类）
　　　　　　　　　距离相近的两个类合并成为一个新类；
　　　　　　　　　if $i=c$
　　　　　　　　　　　$return 0;

　　　　因此可以观察到，聚合聚类需要确定一些超参数：Ⅰ聚类距离或相似度量。Ⅱ合并规则。Ⅲ停止条件c。

　k均值聚类

　　　　模型：

　　　　　　$n$个样本的集合$X=\{x_{1},x_{2},\ldots,x_{n}\}$，每个样本由一个特征向量表示，特征向量的维数假设为$m$，k均值聚类的目标是将$n$个样本分到$k$个不同类中；

　　　　　　设$k

　　　　　　用$C$表示划分，一个划分对应一个聚类结果。即类$l\in \{1,2,\ldots,k\}$，样本$i\in \{1,2,\ldots,n\}$。

　　　　策略：