第七讲 数据聚类

1、第七讲 数据聚类学习过程模式采集预处理分类器设计分类决策特征提取和特征选择识别过程有监督学习无监督学习线性分类器贝叶斯分类器数据拟合主成分分析聚 类区别：样本集是否具有类别标签学习过程一、 数据聚类的基本概念1、 数据聚类的定义：聚类是指在模式空间S中，给定N个样本，按照样本间的相似程度，将S划分为k个决策区域Si（i1，2，.，k）的过程，该过程使得各样本均能归入其中一个类，且不会同时属于两个类。即 S1S2S3SkS， SiSj0，ij聚类Clustering；聚类分析：Clustering Analysis讨论：· 聚类是对整个样本集的划分，而不是对单个样本的识别；·

2、 聚类的依据是“样本间的相似程度”；· 聚类结果是“无遗漏”、“无重复”的。2、 数据聚类的特点：特点一：聚类是典型的无监督学习· 没有预先分好类的样本集· 没有已知的分类决策规则· 由待分类样本特征的内在规律来驱动分类过程特点二：聚类结果多样化· 受特征选取和聚类准则的影响· 受相似度度量标准的影响· 受各特征量纲标尺的影响3、 数据聚类的应用：（1）数据聚类的应用目标· 获得初始的训练样本集，启动分类器的设计· 揭示样本间的内在联系，获得数据中隐藏的知识和规律· 对样本集中的大量样本进行合并

3、和删减，以降低问题的复杂度（2）数据聚类的具体应用领域思考题：你能找到数据聚类在社会生活中的更多应用实例吗？4、 数据聚类的完整过程（1） 选取特征l 聚类任务的需求l 特征对聚类的有效性x2x1l 维度和算法效率（2）确定相似性度量标准· 样本间的相似度· 绝对值距离：· 欧几里德距离：· 明考夫斯基距离· 切比雪夫距离· 非距离相似度x2x111220abc3绝对值距离：Dab1.5，Dac=2，Dbc=3.5；欧几里德距离：Dab1.5，Dac=1.414，Dbc=2.693；切比雪夫距离：Dab1.5，Dac=1，Dbc=2.

4、5；· 类间的相似度· 最短距离：两类中相距最近的两样本间的距离。· 最长距离：两类中相距最远的两样本间的距离。· 重心距离：两类的均值点（重心）间的距离。· 类平均距离：两类中各个元素两两之间的距离相加后取平均值（3）设定聚类准则· 紧致性准则：概念性的基本准则· 误差平方和准则：几何准则，可计算简单，但与紧致性要求不完全一致· 散布准则：类内散布矩阵和类间散布矩阵，能更好地表示样本分布· 分布形式准则：不仅考虑紧致性，而且考虑各类别应具有相同的分布形式（4） 选择聚类算法· 试探法：直接算法

5、，对每个样本至少处理一次；· 层次法：按照层次完成聚类树；· 迭代法：根据准则函数动态调整聚类结果，直至达到最优；· 密度法：以样本分布密度的变化来完成聚类，使得围绕一个密度中心的样本聚到一个类中。（5） 对聚类结果进行评价· 聚类得到的各个类别分布是否合理· 聚类结果是否能发现和适应样本集的样本分布特点；· 是否存在大量的孤立样本或边界样本· 聚类过程是否需要大量的人工干预· 聚类后是否是否可以发现样本集中的分类规则，建立决策边界二、 基于试探的聚类算法1、 基本算法思路：（1） 设定初始的聚类中心；（2） 依次

6、处理各样本；（3） 按照某种聚类准则，将样本归入已有类别，或者建立新的类别；（4） 完成全部数据聚类优点：简单快速缺点：对初始条件敏感，聚类顺序影响聚类结果，需要分类的先验知识，聚类结果需进行评估2、基于最近邻规则的聚类算法（1）选取阀值T，并任取一个样本作为初始聚类中心，如Z1X1；（2）取下一个样本X2，计算X2到Z1的距离D21； 若D21<=T，则将X2归入以Z1为中心的类， 若D21>T，则将X2作为新的类的聚类中心Z2；（3）继续取样本Xi，分别计算Xi到Zj（j1，k）的距离Dij， 如Dij>T， （j1，k），则将Xi作为第k+1个聚类中心Z k+1; 否则

7、，将Xi归入距离最近的聚类中心所属的类中。（4）以此类推，直至全部样本分到正确的模式类中。分类结果受下列因素的影响：l 第一个聚类中心的选择l 待分类模式样本的排列顺序l 阈值T的大小l 样本分布的几何性质3、最大最小距离聚类算法：（1）任取一个样本作为第一个聚类中心，如Z1X1；（2）计算其余样本到Z1的距离Di1，取Di1最大的样本为第二个聚类中心Z2；（3）计算其余样本到Z1，Z2的距离Di1，Di2，即 Di1 | Xi Z1 |,Di2 | Xi Z2 |, 取其最小值Min（Di1,Di2）；（4）若剩余各样本到已有聚类中心的最小距离中的最大值满足：（0< <1，通常取

8、1/2） MaxMin(Di1,Di2)，i1，2，N-2>| Z1 - Z2 |； 则取对应样本为第三个聚类中心Z3（5）若有Z3存在，则进一步计算余下各模式与三个中心的最小距离，并求 MaxMin(Di1，Di2，Di3)，i1，2，N-3>| Z1 - Z2 | 若有某一模式满足上述条件，则存在Z4，否则寻找聚类中心的计算结束；（6）将所有样本按最小距离准则分配到最近的聚类中心。算法讨论：l 该算法的聚类结果与参数以及第一个聚类中心的选取有关l 如果没有先验指示指导和Z1选取，可适当调整和Z1 ，比较多次试探分类结果，选取最合理的一种聚类。三、 层次聚类算法1、 基本算法思路

9、：（1）将所有样本在不同的聚类级别上，按照类间的相似性，形成二叉树的分类结构；（2）其顶端是所有样本属于同一个类，其底端是每个样本都属于一个独立的类；（3）按层次聚类算法的完成顺序可分为：融合算法，分解算法x2x1x6x3x4x51个类2个类3个类4个类6个类5个类2、 融合算法：（1）对于含n个样本的样本集，先令每个样本自成一类，总分类数k = n；（2）计算类间距离，将距离最小（最相似）的两个类合并，总分类数减少为k = n-1；（3）继续合并类，直至总分类数k或类间距离Dij满足要求；例：注：使用重心距离来计算类间距离算法步骤：（1） 令分类数k6，每个样本自成一类；（2） 计算类间距离

10、：1234523314474855262685913（3） 将类间距离最小的类1和3合并为7，分类数k5；类包含样本重心2G254G495G576G6107G1，G31.5x2x1x6x3x4x56个类5个类（4） 计算类间距离：245644522651373.52.55.58.5（5） 将类间距离最小的类4和6合并为8，分类数k4；类包含样本重心2G255G577G1，G31.58G4，G69.5x2x1x6x3x4x56个类5个类4个类（6） 计算类间距离：2575273.55.584.52.58（7） 将类间距离最小的类2和5合并为9，分类数k3；类包含样本重心7G1，G31.58G4，

11、G69.59G2，G56x2x1x6x3x4x56个类5个类4个类3个类（8） 计算类间距离：788894.53.5（9） 将类间距离最小的类8和9合并为10，分类数k2；类包含样本重心7G1，G31.510G4，G6, G2，G57.75x2x1x6x3x4x56个类5个类4个类3个类2个类（10） 计算类间距离：7106.25（11） 将类7和10合并为11，分类数k1；x2x1x6x3x4x56个类5个类4个类3个类2个类1个类（12） 完整的层次聚类过程结束。· 如进行某次类合并后，计算得到的类间距离大幅上升，则意味着已经得到了较好的聚类结果3、 分解算法：（1）对于含n个样

12、本的样本集，先将所有样本作为一类，总分类数k = 1；（2）将已得到的类分成两类，计算类间距离，将类间距离最大（最不相似）的分类方法作为本级分类结果，总分类数增加为k = 2；（3）对每一个得到的类再进行分类，直至总分类数k或类间距离Dij满足要求；例：注：使用重心距离来计算类间距离算法步骤：（1） 令分类数k1，所有样本作为一类；1个类x1, x2, x3, x4,x1,x1,（2） 按不同方法将样本分为两类，计算类间距离；（x1） （x2, x3, x4）2.33（x2） （x1, x3, x4）1.33（x3） （x1, x2, x4）3.67（x4） （x1, x2, x3）4.33（x1, x2） （ x3, x4）0.5（x1, x3） （ x2, x4）4.5（x1, x4） （ x2, x3）1.5（3） 按照类间距离最大的原则，将x1, x3分为一类，x2, x4分为一类，分类数k2；2个类1个类x1, x3x1,x1,x2, x4,x1,x1,（4） 将各类各自再分为两类，计算类间距离；（x1） （x3）1（x2） （x4）2（5） 按照类间距离最大的原则，将x2分为一类，x4分为一类，分类数k3；2个类1个类x1, x3x1,x1,x4,x1,x1,3个类x2x1,x1