重点

Clustering Criteria

Intra-cluster distances are minimized.

Inter-cluster distances are maximized.

Types of Clustering

1. Partitional Clustering（分区聚类）: A division of data objects into non overlapping subsets (clusters) such that each data object is in exactly one subset.（可能需要用户指定聚类数目）

2. Hierarchical clustering（层次聚类）: A set of nested clusters organized as a hierarchical tree.（可以使用 dendrogram 来描述）

K-means

1. k 是 cluster 的数目，由用户指定。
2. 每个聚类有一个中心，称为 centroid。

算法步骤

1. 确定 k。
2. （随机）初始化 k 个聚类中心。
3. 遍历所有样本点，把其划分到离其最近的聚类中心所处的聚类中。
4. 遍历所有聚类，重新计算其中心。
5. 如果没有样本点的类别在上次迭代中发生改变，就退出，否则回到步骤 3 。

距离的度量可以考虑使用欧几里得距离（Euclidean Distance）。

问题：如何确定 k 即聚类的数目？

一种近似方法是寻找转折点，即所谓的 Elbow Finding。

如何实现？

寻找使  最小的 K 即可，其中 c 是一个常数（即所有样本点到其中心点的距离外加一个关于聚类个数的惩罚项）。

问题：如何处理 outliers？

1. 一种方法是移除相较于本聚类中其他数据点，其离聚类中心过远的数据点；为了安全，我们可能需要在多个 iteration 中观测这些点。
2. 另一种方法是使用随机取样，每次我们只选数据集的一个较小的子集，因此选择中一个 outlier 的概率很小；之后通过距离或者相似度比较将剩余的数据点归类。

问题：K-means 对于初始的 K 个聚类中心的选择较为敏感？

那就使用不同的随机数种子以进行多次初始化，选择表现好的。

问题：K-means 不适合寻找聚类形状非超球体（hyper-sphere）的聚类？

对 K-means 的评价：

1. 简单高效。
2. 没有清晰的证据表明其他聚类算法在一般情况下比 K-means 要好。

Fuzzy C-means （FCM）

核心思想：每个样本可以同时以不同程度属于多个类别。

其中：

1. C 是聚类数目。
2. N 是数据点个数。
3.  是第 k 个数据点对于第 i 个聚类的 fuzzy membership。
4.  是第 k 个数据点与第 i 个聚类的中心的欧几里得距离。
5. m 是一个大于 1 的数，称之为 fuzzy weighting factor which defines the degree of fuzziness of the results (normally chosen m =2, to get analytical solution)。

样本点到中心的距离：

Fuzzy membership / 样本点 k 属于聚类 i 的程度：

聚类 i 的 centroid 的计算方法：

算法步骤：

Pros and Cons

优点：

1. 无监督。
2. 总是可以收敛。

缺点：

1. 较大的计算量。
2. 对初始中心的选择较为敏感。
3. 对噪声较为敏感。

Hierarchical Clustering

训练方法：

1. Agglomerative（聚集）：从每个点都是一个聚类开始，每一步都将两个距离最近的聚类合并到一起，直到只剩下一个聚类。
2. Divisive：从一个包含所有数据点的聚类开始，每一步都分裂出一个聚类直到每个聚类只包含一个点。

传统的层次算法使用一个相似矩阵 / 距离矩阵。

优点：

1. 无需指定聚类数目；
2. They may correspond to meaningful taxonomies.

缺点：

1. 一旦合并两个聚类的决定被做出，无法撤销。
2. 没有可以直接最小化的损失函数。
3. 可能有以下问题：
1. 对噪声和离群点敏感；
2. 难以处理不同尺寸的簇集以及 convex shape（凸形）；
3. 打破大的簇集。

Agglomerative Clustering Algorithm

算法步骤：

关键操作是两个聚类的相似度（proximity）的计算，有以下几种方式：

1. 使用两个聚类的最近点间的距离（one link / single link）。
1. 优点：可以处理非椭圆形状（non-elliptical shapes）的聚类。
2. 缺点：对噪声和离群点敏感。
2. 使用两个聚类的最远点间的距离（complete link）。
1. 优点：不易受噪声和离群点影响（Less susceptible to noise and outliers）。
2. 缺点：
1. Tends to break large clusters;
2. Biased towards globular（球状） clusters.
3. 使用两个聚类的平均点间的距离。
1. 优点：不易受噪声和离群点影响。
2. 缺点：Biased towards globular（球状） clusters.
4. 使用两个聚类的中心点间的距离。

总结

问题一

首先遍历所有样本点为其划分簇集，之后遍历所有簇集为其计算新的中心点。

问题二

首先为每个类别计算其中心，然后计算该店到各个中心点的距离，将其划分为离其距离最小的中心所属的类别。

问题三