数据挖掘——学习笔记（系统聚类法和K均值聚类法）

一.系统聚类法

1**.基本思想**

按照距离准则有步骤地进行分类，在类别数量逐渐减少的过程中，直至满足所需的分类标准时为止

算法：

第一步：设初始模式样本共有N个，每个样本自成一类，即建立N类，

通过计算不同类别之间的距离（在初始阶段即等同于各样本间的距离），从而获得一个N×N维度的距离矩阵D^{(0)。在此处，符号D}(0)表示聚类运算前的状态

在第二步中，在前一步骤结束后已经获得了距离矩阵D（n），其中n表示逐步聚类合并的总次数，则需从D（n）中找出最小值；如果该最小值对应于Gi（n）与Gj（n）两类之间的距离，则应将Gi（n）与Gj（n）两类归为一类

，由此建立新的分类：

。

第三步：计算合并后新类别之间的距离，得D(n+1)。

计算

与其它没有发生合并的

之间的距离，可采用多种不同的距离计算准则进行计算。

第四步：转回第二步操作，在持续地进行计算和合并处理的过程中不断优化直至获得预期的分类结果。（具体而言，则是在满足所需分类数量的标准下实现数据集内部的最优划分；或者当数据集中的最小分量达到设定的阈值D时停止运算并输出结果。）

2.距离计算准则

那么什么是距离计算准则呢？

在每次迭代过程中所涉及的聚类之间的相互关系以及这些聚类与样本之间的间距测量构成了聚类合并的核心。使用不同的间距度量方法会导致计算结果产生差异。

主要的距离计算准则：

–最短距离法

–最长距离法

–中间距离法

–重心法

–类平均距离法

聚类准则函数：

（1）最短距离法：设H和K是两个聚类，则两类间的最短距离定义为：

du,v 表示 H 类别中 xu 与 xv 之间的距离；DH,K 定义为 H 类别中所有样本与 K 类别中所有样本之间的最小距离。

递推运算：假若K类是由I和J两类合并而成，则

（2）最长距离法：设H和K是两个聚类，则两类间的最长距离定义为：

其中du,v的含义与上面相同。

递推运算：假若K类是由I和J两类合并而成，则

（3）中间距离法：设K类是由I和J两类合并而成，则H和K类之间的距离为：

它介于最长距离和最短距离之间。

（4）重心法：假定类别I包含n_I个样本而类别J包含n_J个样本，则合并后的总样本数量为n_I + n_J个。将它们分别替代中间距离法中的权重参数以获得新的计算基础从而推导出重心法的类别间距离计算公式

（5）类平均距离法：若采用样本间所有距离的平均距离，则有：

递推运算公式：

二. k均值算法

1.算法思想及基本步骤

将给定的样本划分为K类，K预先指定。

算法核心概念：为了降低聚类性能指标的值而设计的方法采用了聚类目标函数作为指导标准。这种目标函数通过计算并累加每个数据点与所属类别中心之间距离的平方，并寻求使这个总和达到最小的目标来实现分类任务。

算法步骤：

1.为每个聚类确定一个初始聚类中心，这样，就有K个初始聚类中心。

2.将样本集中的样本Xi按照最小距离原则分配到最邻近聚类Zj

3.使用每个聚类中的样本均值作为新的聚类中心。

4.重复步骤2.3直到聚类中心不再变化。

5.结束，得到K个聚类。

2.算法的优化目标

K均值算法的聚类准则函数为：

在算法中我们需要计算K个聚类的样本均值，算法名称由此得来。

我们的目标是寻求聚类准则函数J达到最小值即为算法优化的目标。当J取到最小值时该函数对每个聚类中心而言其梯度等于零

得到

。这说明取类内样本均值为聚类中心可以使得聚类准则函数达到最小。

3.初始聚类中心的选取

初始聚类中心的选择会影响迭代计算所需的时间，并且对最终得到的结果是否为全局最优解具有重要影响；因此合理选择一个合适的初始聚类中心是非常必要的。

首先选择第一个样本点作为第一个聚类中心。

然后选取距离第一个点最远的点作为第二个聚类中心。

……

第j个聚类中心要远离第1~j-1个聚类中心。

或者可以多次随机取初始聚类中心，得到聚类结果，取平均值。

三.聚类结果的评价

对聚类结果进行快速评估在整个迭代计算过程中具有重要意义。其中特别值得注意的是针对那些具有高维特征向量的对象其聚类效果难以直观判断因此可以采用以下几个指标来衡量聚类效果

–聚类中心之间的距离

距离值大，通常可考虑分为不同类

–聚类域中的样本数目

样本数目少且聚类中心距离远，可考虑是否为噪声

–聚类域内样本的距离方差

方差过大的样本可考虑是否属于这一类

目前为止还未发现一种普遍适用的方法能够适用于各个领域；具体情况具体分析时才有可能找到合适的解决方案。

转载于:https://www.cnblogs.com/yangmier/archive/2012/04/09/2438447.html