无监督学习算法
给定数据，不给标签，探寻数据本身的结构。按照贝叶斯的描述，就是去对\(p(x)\)建模
聚类
（问题描述没新意的不写了，老司机都懂）
K均值算法
最简单，最基础的聚类算法 输入：\(x_1, \ldots, x_n\)，其中\(x \in \mathbb{R}^d\) 输出：向量\(c\)代表给每个数据点赋的类别编号，以及\(K\)个均值向量\(\mu\)
- \(\mathbf{c} = (c_1, \ldots, c_n), c_i \in \{1,\ldots, K\}\)。如果\(c_i = c_j = k\)，说明\(x_j\)和\(x_i\)被一起归到了类别\(k\)中
- \(\mathbf{\mu} = (\mu_1, \ldots, \mu_K), \mu_k \in \mathbb{R}^d\)，每个\(\mu_k\)（称作中点centroid）都定义了一个类别
这个问题对应的目标函数需要满足两个条件：1. 能说明什么是好的\(\mathbf{c}\)和\(\mathbf{\mu}\)，2. 易于优化
因此对应的目标函数是 \[ \mathcal{L} = \sum_{i=1}^n\sum_{k=1}^K 1\{c_i = k\}|\!|x_i - \mu_k|\!|^2 = \sum_{i=1}^K\sum_{i:c_i = k}|\!|x_i - \mu_k|\!|^2 \] 对应最优的\(\mathbf{c}\)和\(\mathbf{\mu}\)为： \[ \mu^\ast, \mathbf{c}^\ast = {\rm arg}\min_{\mu, \mathbf{c}}\sum_{i=1}^n\sum_{k=1}^K 1\{c_i = k\}|\!|x_i - \mu_k|\!|^2 \] 这里我们只对各个数据点与对应中心点之间的距离进行惩罚，并不考虑那些没有与其对应的中心点。此外这个问题是一个非凸问题，因此只能得到局部最优解。
该函数也没有解析解，不能直接令导数为0求解，只能迭代。但是迭代的方法有别于前面提到的梯度下降法，因为\(c\)是一个离散值，不可能对\(c\)进行求导，因此需要使用别的方法。这里使用的是坐标下降法，即先固定\(c\)求解最优的\(\mu\)，再固定\(\mu\)求解最优的\(c\)，如此反复。\(\mu\)的初始值可以随机取。迭代的原因是，求解出的新的最优的\(c\)可能会与之前求解\(\mu\)时固定的\(c\)不一样，进而得到更优的\(\mu\)，反之亦然——即是因为\(\mu\)和\(c\)有相互依赖关系
所以整个算法每步可以分两个子步骤：
- 赋类步骤：在\(\mu\)确定的前提下，对\(\mathbf{c}\)进行更新。可以把目标函数进行改写 \[ \mathcal{L} = \underbrace{\left(\sum_{k=1}^K1\{c_1=k\}|\!|x_1-\mu_k|\!|^2\right)}_{\text{distance of }x_1\text{ to its assigned centroid}} + \cdots + \underbrace{\left(\sum_{k=1}^K1\{c_n=k\}|\!|x_n-\mu_k|\!|^2\right)}_{\text{distance of }x_n\text{ to its assigned centroid}} \] 可以看到，加法项之间互相独立，因此如果要使目标函数最小，只需要分别将各求和项取到最小。由于\(c_i\)只能取\(K\)个离散值，因此无法求导。但是由于一般\(K\)值不大，因此可以遍历\(K\)个中点找到最优的\(c_i\)有 \[ c_i = {\rm arg}\min_k |\!|x_i - \mu_k|\!|^2 \]
- 更新步骤：在\(\mathbf{c}\)确定的前提下， 对\(\mu\)进行更新。可以把目标函数写成另一种形式（\(K\)个求和项的和） \[ \mathcal{L} = \underbrace{\left(\sum_{i=1}^N1\{c_i=1\}|\!|x_i-\mu_1|\!|^2\right)}_{\text{sum squared distance of data in cluster #1}} + \cdots + \underbrace{\left(\sum_{i=1}^N1\{c_i=K\}|\!|x_i-\mu_K|\!|^2\right)}_{\text{sum squared distance of data in cluster #K}} \] 各求和项之间也独立，因此可以分别对每个\(k\)进行优化。令\(n_k = \sum_{i=1}^n 1\{c_i =k \}\)，因此 \[ \mu_k = {\rm arg}\min_\mu \sum_{i=1}^n 1\{c_i = k\}|\!|x_i - \mu|\!|^2 \rightarrow \mu_k = \frac{1}{n_k}\sum_{i=1}^n x_i 1\{c_i = k\} \] 即\(\mu_k\)是类\(k\)中所有点的均值
k均值算法的流程就是重复上述两个步骤直至收敛——由于每次对\(c\)或者\(\mu\)的更新都会减少\(\mathcal{L}\)，因此\(\mathcal{L}\)总是会单调递减，且\(\mathcal{L} \ge 0\)，因此最终会收敛在某个点上。但是由于\(\mathcal{L}\)非凸，因此最后应该会收敛到一个局部最优解
算法的另一个问题是如何选择最优的\(K\)。实际上，随着\(K\)的增大，目标函数一定会减少（极端情况下，当\(K=N\)时，所有类别的中心店就是数据点本身，此时\(\mathcal{L}=0\)），因此看什么时候不减是不现实的。常用的选择方法包括
- 使用先验知识
- 观察相对变化量。假设最优的\(K\)为\(K^\ast\)，那么对\(K \le K^\ast\)，增加\(K\)导致的\(\mathcal{L}\)相对变化量肯定比\(K > K^\ast\)要大
- 通常k均值的结果是一个更大应用的组成部分，因此在超过某个点以后即便\(\mathcal{L}\)还在变小，主应用的效果可能也会变差
扩展：K-medoid算法，就是不使用欧几里得距离计算\(x\)与中心点的距离。例如可以使用\(\ell_1\)正则化的方法来计算\(|x_i - \mu_k|\)，这样可以对离群点更加鲁棒
