Part1-聚类

无监督学习

监督学习：

训练集：$\{(x^{(1)}.y^{(1)}),(x^{(2)},y^{(2)}), \cdots,(x^{(m)},y^{(m)}) \}$

如图，是一个典型的监督学习，即具有一个带标签的训练集，而我们的目标则是找到一条能够区分正样本和负样本的决策边界。

监督学习就是我们有一系列的标签，然后用假设函数去拟合它。

而在无监督学习中，我们的数据并不带有任何标签，如图：

训练集：$\{x^{(1)},x^{(2)},x^{(3)},\cdots,x^{(m)} \}$

在无监督学习中，我们要做的就是要将些无标签的数据输入到算法中，然后让算法找到一些隐含在数据中的结构，通过图中这些数据，我们能通过算法找到的一个结构就是数据集中的点可以分成两组分开的点集(簇(Cluster))，像这样能够找出这些簇的算法，被称为聚类算法。

K-means算法

在聚类问题中，我们会给定一组未加标签的数据集，同时希望有一个算法，能够自动地将这些数据分成有紧密关系的子集或是簇。K均值(K-means)算法是比较流行的一种聚类算法。

如图，有一个无标签的数据集，并且想要将其分为两个簇，现在进行K-means算法如下：

随机生成两个点，这两个点也叫做聚类中心，选择两个点的原因是我们想将数据聚成两类

K-means是一个迭代算法，它会做两件事情，第一个是簇分配，第二个是移动聚类中心
内循环：
1. 簇分配；即遍历每个样本，然后根据每个点是与图中红色聚类中心更近，还是和蓝色聚类中心更近，来将每个数据点分配给两个聚类中心之一，可以理解成如图所示的，将每个点染成红色或蓝色
2. 移动聚类中心；计算出所有蓝点的均值和所有红点的均值，然后移动两个聚类中心
3. 循环进行

使用更规范的格式，如下：

输入：

K(簇的个数)
训练集$\{x^{(1)},x^{(2)},\cdots,x^{(m)} \}$ $x^{(i)} R^n $(删除$x_0=1$的惯例)

K-means：

随机初始化K个聚类中心，记作$\mu_1,\mu_2,\cdots,\mu_K \in \mathbb R^n$
循环：$\}$

$ for i=1 to m: $

$c^{(i)}:=最接近x^{(i)}的聚类中心$

$for\ k=1\ to\ K:$

$\mu_k:=分配给第k簇的点(x)的均值$

$\}$

假设$\mu_k$是某个簇的均值，那么如果存在一个没有点的聚类中心会怎样？

这里，最常见的做法就是直接移除那个聚类中心，这样的话，最终会得到K-1个簇而不是K个簇；然而，有时确实需要K个簇，这时就可以随机初始化这个聚类中心。

K-means另一个常见的应用就是可以用来解决分离不佳的簇的问题：

如图，对于人们不同的身高、体重，现在需要给T恤设计三种不同的大小(小号、中号和大号)，则小号应该设计多大？中号多大？大号多大？

有一个方法就是对这些数据执行K-means聚类算法，虽然这些数据不像之前的例子能够明确分为三簇，但K-means还是能将这些数据分为几个簇

优化目标

$c^{(i)}=样本x^{(i)}当前所属的簇的索引$

$\mu_k=第k个聚类中心$

$\mu_{c^{(i)}=x^{(i)}}所属的那个簇的聚类中心$

优化目标：

$J(c^{(1)},\cdots,c^{(m)},\mu_1,\cdots,\mu_K)=\frac{1}{m}\sum_{i=1}^m||x^{(i)}-\mu_{c^{(i)}}||^2$

$\min_{(c^{(1)},\cdots,c^{(m)},\mu_1,\cdots,\mu_K)}J(c^{(1)},\cdots,c^{(m)},\mu,\cdots,\mu_K)$

这个代价函数，有时也叫失真代价函数(Distortion cost function)

随机初始化

如何初始化聚类中心？

通常，效果最好的如下：

应该设计K小于样本数量ｍ，然后随机挑选K个训练样本，然后设定$\mu_1,\cdots,\mu_K$等于这K个样本

局部最优问题：

如图，给定这样一个数据集

它看起来好像有3个簇，如果运行K-means算法，如图，假设它最后得到一个比较好的局部最优，事实上，它应该是全局最优了，可能会得到图中这样的聚类结果

但如果随机初始化得到的结果不好，就可能会得到不同的局部最优值，如图：

因此，如果担心K-means算法落到局部最优，如果相让K-means找到最有可能的聚类，我们可以尝试多次随机初始化，而不是仅仅初始化一次。

具体的，我们可以这样：

$for\ i\ to\ 100:\{$

$随机初始化K-means$

$运行K-means，得到c^{(1)},\cdots,c^{(m)},\mu_1,\cdots,\mu_K$

$计算代价函数J(c^{(1)},\cdots,c^{(m)},\mu_1,\cdots,\mu_K)$

$\}$

最后，选择代价函数最小的聚类结果。

然而，实际上，当K=2~10时，多次随机初始化是有用的，而当K太大时，多次随机初始化就并没有太大改善了。

选取聚类数量

对于一个数据集，对应的K可能有多个答案，而并没有完全正确的答案。

选择K的值：

肘部法则：

我们需要使用不同的K，然后计算代价函数，画出类似如下图的图：

观察这条曲线，可以发现它有一个"肘部"，大致对应于$K=3$的位置，这样，则我们就可以选择$K=3$

然而，在实际操作过程中，大多时候，这个"肘部"其实并不明显，我们并不能准确确定拐点最合适的位置。

另一种选择K值的思路：

通常人们选择K-means聚类是为了得到聚类用于后面的目的，也许想用K均值聚类来做市场分割就像之前说的T恤的例子等，如果后续目的如市场分割能给定一个评估标准，则决定K值的更好的方式是看哪个K值能更好地应用于后续目的。

如，还是以上述T恤的为例，可能有3种尺寸(S,M,L)或5种尺寸(XS,S,M,L,XL)，