1 最近邻规则

给定集合包含n对数，$({\mathbf{x}}_1,t_1)$, …，$({\mathbf{x}}_n,t_n)$，其中${\mathbf{x}}_i$为实数，t_i属于集合{1,…，M}\{1,…，M\}{1,…，M}，每个${\mathbf{x}}_i$是同一测量规则得到的$i$th个独立量，而每个$t_i$是对应的样本类别
上述规则可以简称为：${\mathbf{x}}_i$属于类别$t_i$

对于其中一个样本$\mathbf{x}$，可以给它从{1,…，M}\{1,…，M\}{1,…，M}分配一个标签，令${\mathbf{x}}_k$是$\mathbf{x}$最近邻，则有：
$$\min d(\mathbf{x},{\mathbf{x}}_i)=d(\mathbf{x},{\mathbf{x}}_k),i=1,\dots ,n$$

一个常用的距离度量是平方和，假设$\mathbf{x}=[x_1,x_2{]}^T$，${\mathbf{x}}_k=[x_{k}1,x_{k}2{]}^T$，则有：
$$d(\mathbf{x},{\mathbf{x}}_k)=(x_1,x_{k1}{)}^2+(x_2-x_{k2}{)}^2$$

例1
为了选择最好的候选者，学校入学考试包括两个学科，英语和数学。假设知道5个候选者的分数和分类结果（下表）。如果一个候选者被录取，认为他是类别1，其他的是类别2 。采用最近邻规则来确定Andy如果英语和数学都超过70会不会被录取。

解法：

1. 计算Andy成绩与上述5个候选者的距离：
   
2. 找到{d1,d2,d3,d4,d5}\{d_1,d_2,d_3,d_4,d_5\}{d1​,d2​,d3​,d4​,d5​}中的最小值为$d_2=100$
3. 最小值对应的是2号候选人，他的类别是2，所以Andy应该也是不会被录取的

2 K近邻规则（k-nn）

k近邻规则是最近邻规则的延伸，就是每次将标本划分到k个最近邻样本

通过k个最近邻样本的标签进行投票可以决定目标样本的标签

3 K-means聚类

聚类算法是找到一组中心点来反应数据点的分布，中心点的个数M可以提前确定，每个中心${\mathbf{c}}_i$被认为是一组数据点的代表

假设n个数据点${\mathbf{x}}_j,j=1,...,n\}$。可以找到$M$个代表向量${\mathbf{c}}_i，i=1,...,M$。算法将所有数据点划分到$M$的子集$S_i$中，并使得下列求和式子最小化：
$$J=\sum _{i=1}^M\sum _{{\mathbf{x}}_j\in S_i}||{\mathbf{x}}_j-{\mathbf{c}}_i|{|}^2$$

$J$的最小化条件是：
$${\mathbf{c}}_i=\frac{1}{N_i}\sum _{{\mathbf{x}}_j\in S_i}{\mathbf{x}}_j$$

算法步骤：

1. K-means聚类的初始会任意划分$M$个集合，然后分别计算各个集合的中心
2. 然后根据集合中心，将数据点按照最近邻规则重新划分到各个集合中
3. 上述两个步骤重复进行，直到每次划分的集合数据点不再发生变化为止

在线K-means聚类算法
最初的中心随机从训练数据集中选取，然后还是将数据点分配给各个中心，重新计算中心的式子为：
$${\mathbf{c}}_k^{new}={\mathbf{c}}_k^{old}+\eta ({\mathbf{x}}_j-{\mathbf{c}}_k^{old})$$
将${\mathbf{c}}_k^{new}$替换${\mathbf{c}}_k^{old}$，这里$\eta$是学习率，上述步骤重复进行，知道中心不再发生改变为止