聚类算法
聚类问题，即对给定的样本集S，每个样本具有n个可观察属性，使用某种算法，将S划分成多个子类，要求子类内部样本尽量相似，子类间样本尽量相异，分类之前，类核心并不确定。与分类问题不同的是，分类通过已知类别的样本，学习获得分类函数（或已有分类标准），对未知类别样本进行分类，关键过程在于分类标准的确定，分类之前，分类依据确定。聚类对样本的划分，由内部样本的分布决定，而分类由分类函数（即训练集或经验）决定。在机器学习领域，分类算法为监督学习算法，聚类为非监督学习算法。
分类问题直接计算分类函数获得样本分类，聚类问题使得 $ f(\mu, C)= \sum_{j=1}^m\parallel\mu_{C_{j}}-x_{j}\parallel^2 $ (C为分类簇，$ \mu_{C_j} $ 为类簇C核心) 最小。
K-means算法
K均值算法，常见聚类算法，用于将样本分割成K个分类，使得类间距离和最小。
算法过程
K-means算法核心包含类核心选取、样本归类、类核心调整三个过程以及一个循环控制逻辑
- 在样本的属性值空间随机选择K个类核心；
- 根据样本点相对类核心的距离，将样本归类到最近一个类核心所属分类，形成K个不相交聚类；
- 类核心调整，将类核心调整为类中所有样本点的中心点；
- 重复2-3过程，直到类核心不再移动，此时生成的分类为最终分类。
距离
根据属性类型的不同，距离的计算方法也不同
- 数值变量: $ d(X, Y) = \sqrt[p]{\sum_{i=1}^n\mid X_i - Y_i \mid^p} $ (闵可夫斯基距离)，p常用取值(1,2)分别为曼哈顿距离和欧式距离，为了平衡不同属性的取值空间影响，需要对变量进行规格化，将属性值映射到相同的值空间 $ a_i^\prime =\frac{a_i - \min(a_i)}{\max{a_i} - \min{a_i}} $
- 分类变量: 取值不同的同位属性数/单个元素的全部属性数
- 向量: $ s(X, Y) = \frac{X^tY}{\parallel X \parallel \parallel Y \parallel} $
在样本拥有的可观察属性比较多的情况下，属性值可能有多种类型，可以将分类变量转换为数值类型，同时不同属性可能有不一样的加权。
样本中心点
$ \overline X = \frac{1}{\mid C_i \mid}\sum_{x \in C_i}X $，也即几何样本的几何中心点。
但是分类变量的连续值没有意义，因此，具有分类变量的样本集合无法计算样本中心点。
评价函数
$ E = \sum_{i=1}^k\sum_{x \in C}{\mid x- \overline x_i \mid}^2$ 迭代过程中，评价函数值不再产生明显变化，K-means算法退出循环，分类结束。
K-means算法的收敛性
K-means算法在运行过程中，进行类核心的移动，聚类调整，以使得评价函数不断变小，验证过程如下：
- 将类核心作为固定值，进行聚类，聚类过程将样本s归类到最近一个类核心所属聚类$c$，原属归类$c\prime$，由于c是距离s最近的类核心，${\mid s - c \mid}^2 \le {\mid s - c\prime\mid}^2 $，因此$F(s, c)=\sum_{i=1}^k\sum_{x \in C}{\mid x- c \mid}^2\le\sum_{i=1}^k\sum_{x \in C\prime}{\mid x- c\prime \mid}^2=F(s,c\prime)$，也就是说，样本的聚类调整使得评价函数减小，
- 将分类固定，进行类核心调整，调整前类核心为c，调整后类核心为类中样本中心点$\overline x (x \in C)$，而空间中的所有点中，所给点集合的几何中心点到该集合所有点的距离和最小(几何中值)，因此$\forall s \in C, {\mid s - \overline C\mid}^2 \le {\mid s - c \mid}^2 , 其中c为调整前的类核心,\overline C为C中样本中心点$，$F(s, c)=\sum_{i=1}^k\sum_{x \in C}{\mid x- c \mid}^2\le\sum_{i=1}^k\sum_{x \in C\prime}{\mid x- c\prime \mid}^2=F(s,c\prime)$，也就是说，类核心的调整使得评价函数减小。
- 由于1和2过程在每个迭代中依次进行，且$F \ge 0$，因此K-means算法一个梯度下降的过程，具有收敛性。
算法分析
优点：
- 算法简单，快速；
- 结果分类密集时，收敛速度比较快。
缺点：
- 由于在迭代中不能调整分类变量类型的样本集合的中心点，K-means并不能这类数据，同时K-means算法也不能分类具有离散值的数据；
- K值需要提前确定，而且，对于初始类核心点的选取，比较敏感，不同的初始值会产生不同的结果；
- 对于噪声和孤立值敏感，少量的数据就能对平均值产生比较大的影响。
K-means算法的改进版算法
K-means++
改进了初始类核心的选择，使得产生的分类更有可能获得更好的结果，其初始值的选择过程为：
- 从样本集中随机选择一个样本作为初始聚类核心$c_1$;
- 计算每个样本与当前已有的聚类核心之间的最短距离（即与最近的一个聚类核心之间的距离），值为D(x)，这个样本被选为下一个聚类核心的概率为$\frac{D(x)^2}{\sum_{m \in C}D(m)^2}$，按概率随机选择一个样本点，作为下一个聚类核心；
- 重复2过程，直到选择出k个聚类核心。
ISODATA
可以在算法运行过程中通过分裂或者合并操作调整分类数，使得聚类数不必过分依赖人工干预，但是需要提供：
- 预期聚类数$K_0$，最终聚类为[$\frac{K_0}{2}$, $2K_0$]；
- 聚类最小样本数$N_{min}$，判断是否应该进行合并；
- 类间最大方差$V_{max}$，结合2中条件判断是否应该进行分裂；
- 聚类中心最小值$d_{min}$，结合1中条件判断是否应该进行合并。
算法过程是：
- 随机选择$K_0$个样本作为初始聚类核心；
- 对其余样本，根据样本点相对类核心的距离，将样本归类到最近一个类核心所属分类，生成$K_0$个聚类；
- 对2中生成的聚类，进行判断，如果有聚类中元素数目小于$N_{min}$，如果有，则将此分类丢弃，其中的样本重新分配给其他$K_0-1$个聚类中；
- 将聚类的核心调整为各聚类的几何中心点；
- 如果当前$K < \frac{K_0}{2}$，计算聚类核心间的距离$D(i,j)$，对于$D(i,j)<d_{min}(i \ne j)$，则将类i与j进行合并，变成新聚类，其核心为$c_{new}=\frac{1}{n_i+n_j}(n_i c_i + n_j c_j), n_i n_j分别为i和j聚类的样本数目$；
- 如果当前$K > 2K_0$，计算每个聚类下所有样本的每个属性上的方差，找出每个聚类的最大方差$\sigma_{max}$，如果某个聚类的$\sigma_{max} < V_{max}$且其包含样本数$n_i \ge 2N_{min}$，则将此聚类分裂成两个子聚类，两个子聚类的核心分别为原聚类核心在对应属性相反方向上移动$\sigma_{max}$，将类中样本分配给两个子聚类，并将聚类数更改为K+1；
- 如果迭代次数未超过最大迭代次数，则回到2，再次进行迭代，否则跳出迭代。