聚类算法_kmeans_层次聚类

层次聚类

层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。分为聚合(agglomerative)聚类（自下而上）、分裂(divisive)聚类（自上而下），每个样本只属于一个类，所以层次聚类属于硬聚类。

聚合聚类算法：
输入：$n$个样本组成的样本集合及样本之间的距离；
输出：对样本集合的一个层次化聚类。

1. 计算$n$个样本两两之间的欧氏距离 { d i j } \{d_{ij}\} {dij?}，记作矩阵$D={[d_{ij}]}_{n?n}$。
2. 构造$n$个类，每个类只包含一个样本。
3. 合并类间距离最小的两个类，其中最短距离为类间距离，构建一个新类。
4. 计算新类与当前各类的距离。若类的个数为1，终止计算，否则回到步3。

算法复杂度$O(n^{3}m)$，其中$m$是样本的维数，$n$是样本个数。

$K$均值聚类

$K$均值聚类是基于样本集合划分的聚类算法。$K$均值聚类将样本集合划分为$K$个子集，构成$K$个类，将$n$个样本分到$K$个类中，每个样本到其所属类的中心的距离最小。每个样本只属于一个类，因此$K$聚类也是硬聚类。

算法：
输入：$n$个样本的集合$X$。
输出：样本集合的聚类$C$。

1. 初始化。令$t=0$，随机选择$K$个样本点作为初始聚类中心$m^{(0)}=(m_1^{(0)},...,m_l^{(0)},...,m_k^{(0)})$。
2. 对样本进行聚类。对固定的类中心$m^{(t)}=(m_1^{(t)},...,m_l^{(t)},...,m_k^{(t)})$，其中$m_l^{(t)}$是类$G_l$的中心，计算每个样本到类中心的距离，将每个样本指派到与其最近的中心的类中，构成聚类结果$C^{(t)}$。
3. 计算新的类中心，对聚类结果$C^{(t)}$，计算当前各个类中的样本的均值，作为新的类中心$m^{(t+1)}=(m_1^{(t+1)},...,m_l^{(t+1)},...,m_k^{(t+1)})$。
4. 如果迭代收敛或符合停止条件，输出$C^{?}=C^{(t)}$，否则，令$t=t+1$，返回步2。

算法复杂度$O(mnk)$，其中$m$是样本维数，$n$是样本个数，$k$是类别个数。