1、第第8章章 聚类聚类n熟悉聚类的基本思想以及聚类和分类的异同点熟悉聚类的基本思想以及聚类和分类的异同点。n熟悉常用的聚类算法。熟悉常用的聚类算法。n掌握掌握k-均值均值算法的原理、优缺点及改进算法。算法的原理、优缺点及改进算法。n熟悉初始的熟悉初始的k个聚类中心（簇中心）对个聚类中心（簇中心）对k-均值均值算法的影响。算法的影响。n熟悉聚类特征和聚类特征树（熟悉聚类特征和聚类特征树（CF-Tree）的概念。）的概念。n熟悉熟悉CF-Tree的构建过程及的构建过程及BIRCH算法的优缺点。算法的优缺点。n熟悉熟悉DBSCAN算法的优缺点。算法的优缺点。n了解了解OPTICS算法的原理以及适用场合
2、。算法的原理以及适用场合。本章学习目标本章学习目标n8.1 聚类概述聚类概述n8.2 k-均值均值算法算法n8.3 BIRCH算法算法n8.4 基于密度的聚类算法基于密度的聚类算法第第8章章 聚类聚类8.1 聚类聚类概述概述n8.1.1 聚类的概念聚类的概念n聚类聚类是是非监督式非监督式机器学习任务，没有训练过程，这是和分类最本机器学习任务，没有训练过程，这是和分类最本质的区别质的区别。n聚类聚类仅限于对仅限于对未知类别标签未知类别标签的一批数据对象（实例）进行归类，的一批数据对象（实例）进行归类，只把相似性高的数据对象归到同一个簇内，把差异性大的数据对只把相似性高的数据对象归到同一个簇内，把
3、差异性大的数据对象归到不同的簇中象归到不同的簇中。n聚类聚类没有事先定义好的类别，其类别所表达的含义通常是没有事先定义好的类别，其类别所表达的含义通常是不确定不确定的。的。8.1 聚类聚类概述概述n8.1.1 聚类的概念聚类的概念n聚类分析聚类分析的的应用：应用：n模式识别模式识别n天气预报天气预报n模糊控制模糊控制n计算机视觉计算机视觉n消费者行为分析消费者行为分析n交易数据分析交易数据分析n动植物种群分类动植物种群分类n疾病诊断疾病诊断8.1 聚类聚类概述概述n8.1.2 聚类算法的分类聚类算法的分类n划分聚类划分聚类n层次聚类层次聚类n基于密度的聚类基于密度的聚类n基于网格的聚类基于网格
4、的聚类n基于模型的聚类基于模型的聚类n基于图的聚类基于图的聚类n模糊聚类模糊聚类8.1 聚类聚类概述概述n8.1.2 聚类算法的分类聚类算法的分类n划分聚类划分聚类：将数据集划分为将数据集划分为个簇，并对其中的样本计算距离个簇，并对其中的样本计算距离以获得假设簇中心点，然后以簇的中心点重新迭代计算新的中以获得假设簇中心点，然后以簇的中心点重新迭代计算新的中心点，直到心点，直到 个簇的中心点收敛为止。常见的划分聚类算法有：个簇的中心点收敛为止。常见的划分聚类算法有：nk-均值（均值（k-means）算法）算法nk-均值均值+（k-means+）算法）算法nk-中心点（中心点（k-medoids）
5、算法）算法n小批量小批量k-均值均值算法算法8.1 聚类聚类概述概述n8.1.2 聚类算法的分类聚类算法的分类n层次聚类层次聚类：按层次对数据集进行划分，把实例划分到不同层次的簇按层次对数据集进行划分，把实例划分到不同层次的簇中，从而形成一个中，从而形成一个树形树形的聚类结构的聚类结构。n常见的常见的层次层次聚类聚类算法算法有：有：n利用层次方法的平衡迭代规约和聚类利用层次方法的平衡迭代规约和聚类（Balanced Iterative Reducing and Clustering using Hierarchies，BIRCH）算法）算法nCURE（Clustering Using Repr
6、esentatives）算法）算法8.1 聚类聚类概述概述n8.1.2 聚类算法的分类聚类算法的分类n基于密度的聚类：基于密度的聚类：根据样本的密度不断增长聚类，最终形成一根据样本的密度不断增长聚类，最终形成一组组“密集连接密集连接”的点集，其核心思想是只要数据的密度大于阈的点集，其核心思想是只要数据的密度大于阈值就将其合并成一个簇值就将其合并成一个簇。n基于密度的聚类方法主要包括基于密度的聚类方法主要包括：nDBSCAN（Density-Based Spatial Clustering of Application with Noise）nOPTICS（Ordering Points To
7、Identify the Clustering Structure）8.1 聚类聚类概述概述n8.1.2 聚类算法的分类聚类算法的分类n基于基于网格的网格的聚类：聚类：将一个数据集空间划分成有限数目的网格单将一个数据集空间划分成有限数目的网格单元，形成一个网格结构，然后将数据集中的实例映射到网格单元，形成一个网格结构，然后将数据集中的实例映射到网格单元，接着在这些网格单元上进行聚类操作。元，接着在这些网格单元上进行聚类操作。n基于基于网格的网格的聚类聚类算算法主要包括法主要包括：n统计信息网格（统计信息网格（STatistical INformation Grid，STING）算法）算法nWa
8、veCluster 算法算法8.1 聚类聚类概述概述n8.1.2 聚类算法的分类聚类算法的分类n基于模型基于模型的的聚类：聚类：首先假设数据集中蕴含的每个类簇分别服从首先假设数据集中蕴含的每个类簇分别服从某种概率分布模型，然后利用数据集对模型进行多次迭代，最某种概率分布模型，然后利用数据集对模型进行多次迭代，最终确定最优组合时模型中所对应的具体参数值。终确定最优组合时模型中所对应的具体参数值。n基于模型基于模型的的聚类聚类算算法主要包括法主要包括：n基于统计基于统计：以高斯混合模型（以高斯混合模型（Gaussian Mixture Models，GMM）为代表。为代表。n基于神经网络基于神经网
9、络：以自组织特征映射网络（以自组织特征映射网络（Self-Organizing Feature Mapping，SOFM）为代表）为代表。8.1 聚类聚类概述概述n8.1.2 聚类算法的分类聚类算法的分类n基于图基于图的的聚类：聚类：把实例看作把实例看作图图的顶点，根据实例之间的距离构的顶点，根据实例之间的距离构造边（造边（Edge），形成带权重的图（），形成带权重的图（Graph）。通过图的切割实）。通过图的切割实现聚类，即将图切分成多个子图，这些子图就是对应的簇。现聚类，即将图切分成多个子图，这些子图就是对应的簇。n基于图基于图的的聚类聚类的的典型代表是典型代表是谱聚类谱聚类（Spectr
10、al Clustering）算法算法，首先构造数据集的邻接图，得到图的拉普拉斯矩阵，然后对矩首先构造数据集的邻接图，得到图的拉普拉斯矩阵，然后对矩阵进行特征值分解，通过对特征向量进行处理构造出簇。阵进行特征值分解，通过对特征向量进行处理构造出簇。8.1 聚类聚类概述概述n8.1.2 聚类算法的分类聚类算法的分类n模糊模糊聚类：聚类：是一种采用是一种采用模糊数学模糊数学语言对事物按一定的要求进行语言对事物按一定的要求进行描述和归类的方法，它允许实例可以同时以不同的描述和归类的方法，它允许实例可以同时以不同的隶属度隶属度属于属于各个不同的簇类。各个不同的簇类。n模糊模糊聚类聚类方法中最典型的算法是
11、模糊方法中最典型的算法是模糊-C均值（均值（Fuzzy C-means，FCM）聚类算法。）聚类算法。n8.1 聚类概述聚类概述n8.2 k-均值均值算法算法n8.3 BIRCH算法算法n8.4 基于密度的聚类算法基于密度的聚类算法第第8章章 聚类聚类8.2 k-均值均值算法算法n8.2.1 k-均值均值算法算法流程流程nk-均值均值（k-means）算法算法是一种是一种划分聚类算法，其目标是将划分聚类算法，其目标是将一一个没有标签个没有标签的数据集中的的数据集中的个数据对象个数据对象(实例实例)划分为划分为个簇，个簇，使得每个簇内的数据对象具有高度的相似性，不同簇间的数据使得每个簇内的数据对
12、象具有高度的相似性，不同簇间的数据对象具有较大的差异性。对象具有较大的差异性。nk-均值均值算法算法具有一个迭代过程，在这个过程中，数据集被分组具有一个迭代过程，在这个过程中，数据集被分组成成个预定义的不重叠的个预定义的不重叠的簇簇，使簇的内部点尽可能相似，同时，使簇的内部点尽可能相似，同时试图保持簇在不同的空间，它将数据点分配给簇，以便簇的质试图保持簇在不同的空间，它将数据点分配给簇，以便簇的质心和数据点之间的平方距离之和最小，在这个位置，簇的质心心和数据点之间的平方距离之和最小，在这个位置，簇的质心是簇中数据点的算术平均值。是簇中数据点的算术平均值。8.2 k-均值均值算法算法n8.2.1
13、 k-均值均值算法算法流程流程8.2 k-均值均值算法算法n8.2.1 k-均值均值算法算法流程流程初始化簇质心初始化簇质心步骤一：步骤一：初始化簇的质心（初始化簇的质心（聚类中心聚类中心）。）。初始化时，必须注意簇的质心必须小于训初始化时，必须注意簇的质心必须小于训练数据点的数目。因为该算法是一种迭代练数据点的数目。因为该算法是一种迭代算法，接下来的两个步骤是迭代执行的。算法，接下来的两个步骤是迭代执行的。8.2 k-均值均值算法算法n8.2.1 k-均值均值算法算法流程流程簇赋值簇赋值8.2 k-均值均值算法算法n8.2.1 k-均值均值算法算法流程流程步骤三：步骤三：移动质心，迭代更新。
14、因为上面移动质心，迭代更新。因为上面步骤中形成的簇没有优化，所以需要形成步骤中形成的簇没有优化，所以需要形成优化的簇。为此，我们需要迭代地将质心优化的簇。为此，我们需要迭代地将质心移动到一个新位置。取一个簇的数据点，移动到一个新位置。取一个簇的数据点，计算它们的平均值，然后将该簇的质心移计算它们的平均值，然后将该簇的质心移动到这个新位置。对所有其他簇重复相同动到这个新位置。对所有其他簇重复相同的步骤。的步骤。迭代更新迭代更新8.2 k-均值均值算法算法n8.2.1 k-均值均值算法算法流程流程最后，算法收敛后，形成不同的簇。最后，算法收敛后，形成不同的簇。该算法可以根据簇在第一步中的初始该算法
15、可以根据簇在第一步中的初始化方式给出不同的结果。化方式给出不同的结果。收敛收敛8.2 k-均值均值算法算法n8.2.1 k-均值均值算法算法流程流程初始化簇质心初始化簇质心簇赋值簇赋值迭代更新迭代更新收敛收敛k-均值算法流程总结均值算法流程总结8.2 k-均值均值算法算法n8.2.1 k-均值均值算法算法流程流程8.2 k-均值均值算法算法n8.2.2 k-均值均值算法算法的特点的特点nk-均值均值算法算法的优点的优点：n原理原理比较简单，容易实现，收敛速度快，可解释性较好。比较简单，容易实现，收敛速度快，可解释性较好。n需要需要调节的参数较少（主要是聚类簇调节的参数较少（主要是聚类簇数数 k
16、），），且聚类效果较好。且聚类效果较好。nk-均值算法的缺点：均值算法的缺点：n聚类聚类簇簇数数 k 值值的选取不好把握，一般只能通过暴力搜索法来确定。的选取不好把握，一般只能通过暴力搜索法来确定。n只只适合簇型数据，对其他类型的数据聚类效果一般。适合簇型数据，对其他类型的数据聚类效果一般。n如果如果各隐含类别的数据不平衡各隐含类别的数据不平衡，则，则聚类效果不佳。聚类效果不佳。n采用采用迭代方法，得到的结果只是局部最优。迭代方法，得到的结果只是局部最优。n当当数据量较大时，计算量也比较大，采用小数据量较大时，计算量也比较大，采用小批量批量 k-均值均值的的方式虽然可以缓方式虽然可以缓解，但可
17、能会牺牲准确率。解，但可能会牺牲准确率。n对对噪音和异常点比较的敏感噪音和异常点比较的敏感。8.2 k-均值均值算法算法n8.2.3 k-均值均值算法算法的改进的改进nk-均值均值+算法算法8.2 k-均值均值算法算法n8.2.3 k-均值均值算法算法的改进的改进nk-中心点中心点算法算法8.2 k-均值均值算法算法n8.2.3 k-均值均值算法算法的改进的改进n小批量小批量k-均值均值算法算法n小批量小批量k-均值均值的的思想是先对大数据集进行一个随机采样（一思想是先对大数据集进行一个随机采样（一般是无放回的），对采样得到的数据子集再般是无放回的），对采样得到的数据子集再用用k-均值均值算法
18、算法进进行聚类行聚类。n为了为了提高聚类的准确性，一般要对数据集进行多次随机采提高聚类的准确性，一般要对数据集进行多次随机采样得到多个数据子集后再进行样得到多个数据子集后再进行多次多次k-均值均值聚类聚类，最后选择最，最后选择最优的聚类簇优的聚类簇。n采用采用小小批量批量k-均值均值的的方式虽然可以减轻计算负担，但可能会方式虽然可以减轻计算负担，但可能会牺牲准确度牺牲准确度。n8.1 聚类概述聚类概述n8.2 k-均值均值算法算法n8.3 BIRCH算法算法n8.4 基于密度的聚类算法基于密度的聚类算法第第8章章 聚类聚类8.3 BIRCH算法算法n8.3.1 聚类特征和聚类特征树聚类特征和聚
19、类特征树nBIRCH算法的核心就是构建算法的核心就是构建一棵一棵聚类特征树聚类特征树（CF-Tree）。）。nC F-Tr e e 的 每 一 个 节 点的 每 一 个 节 点（Node）都由若干个）都由若干个聚类特聚类特征征（CF）组成，其中非叶子）组成，其中非叶子节点的节点的CF有指向子节点的指有指向子节点的指针，所有的叶子节点用一个针，所有的叶子节点用一个双向链表链接起来，如图双向链表链接起来，如图8-3所示。所示。8.3 BIRCH算法算法n8.3.1 聚类特征和聚类特征树聚类特征和聚类特征树例如，图例如，图-示例了在示例了在 CF-Tree中的某个节点的某一个簇中的某个节点的某一个簇
20、中，有如下中，有如下5个个实例实例:(3，4)，(2，6)，(4，5)，(4，7)，(3，8)，则，则该簇对应该簇对应的的CF为为(N，LS，SS)=(5，(16，30)，(54，190)，其中，其中，N=5 8.3 BIRCH算法算法n8.3.1 聚类特征和聚类特征树聚类特征和聚类特征树8.3 BIRCH算法算法n8.3.2 聚类特征树的构建聚类特征树的构建8.3 BIRCH算法算法n8.3.2 聚类特征树的构建聚类特征树的构建8.3 BIRCH算法算法n8.3.2 聚类特征树的构建聚类特征树的构建8.3 BIRCH算法算法n8.3.2 聚类特征树的构建聚类特征树的构建8.3 BIRCH算法
21、算法n8.3.2 聚类特征树的构建聚类特征树的构建8.3 BIRCH算法算法n8.3.3 BIRCH算法的优缺点算法的优缺点nBIRCH算法的算法的优点优点n1）不需要事先指定聚类的簇数。）不需要事先指定聚类的簇数。n2）实际存放数据的叶子节点是保存在本地硬盘上的，非叶子节点）实际存放数据的叶子节点是保存在本地硬盘上的，非叶子节点仅保存特征向量仅保存特征向量CF和用于指向父亲节点和子节点的指针，这样非和用于指向父亲节点和子节点的指针，这样非常节省内存，可以大大降低内存资源需求常节省内存，可以大大降低内存资源需求。n3）聚类速度快，只需要扫描一遍数据集就可以建立）聚类速度快，只需要扫描一遍数据集
22、就可以建立CF-Tree。将。将两个簇进行合并时只需要对两个簇的两个簇进行合并时只需要对两个簇的CF特征向量进行加法运算。特征向量进行加法运算。衡量簇与簇之间里距离时只需要将合并前后的衡量簇与簇之间里距离时只需要将合并前后的CF的值进行减法运的值进行减法运算即可算即可。因此。因此在处理大规模数据集时速度快，效率高。在处理大规模数据集时速度快，效率高。n4）可以在聚类的过程中发现数据集中的噪声实例（离群点），且）可以在聚类的过程中发现数据集中的噪声实例（离群点），且算法本身对噪声实例（离群点）不敏感算法本身对噪声实例（离群点）不敏感。8.3 BIRCH算法算法n8.3.3 BIRCH算法的优缺点
23、算法的优缺点nBIRCH算法算法的的缺点缺点n1）由于受枝平衡因子）由于受枝平衡因子B和叶平衡因子和叶平衡因子L的约束，对每个节点的的约束，对每个节点的CF个数有限制，可能会导致聚类结果与实际的簇类分布情况不同。个数有限制，可能会导致聚类结果与实际的簇类分布情况不同。n2）对数据特征维数高的实例聚类效果不好。）对数据特征维数高的实例聚类效果不好。n3）如果数据集的类簇分布不是类似于超球体，或者说不是凸的分）如果数据集的类簇分布不是类似于超球体，或者说不是凸的分布，则聚类效果不好。布，则聚类效果不好。n4）聚类结果受到数据插入顺序的影响，本属于同一个簇的数据点）聚类结果受到数据插入顺序的影响，本
24、属于同一个簇的数据点可能由于插入顺序不同而被分到不同的簇中。可能由于插入顺序不同而被分到不同的簇中。n5）由于采用欧式距离计算方法，只能够处理连续型属性的）由于采用欧式距离计算方法，只能够处理连续型属性的数据。数据。n8.1 聚类概述聚类概述n8.2 k-均值均值算法算法n8.3 BIRCH算法算法n8.4 基于密度的聚类算法基于密度的聚类算法第第8章章 聚类聚类8.4 基于密度的聚类基于密度的聚类算法算法n8.4.1 基于密度聚类的基本概念基于密度聚类的基本概念n基于密度的聚类：基于密度的聚类：一般假定可以由实例分布的紧密程度（一般假定可以由实例分布的紧密程度（密度密度）来进行聚类分析。同一
25、簇内的实例之间是紧密相连的，通过将来进行聚类分析。同一簇内的实例之间是紧密相连的，通过将紧密相连的实例划到同一个簇，就可得到一个聚类类别。通过紧密相连的实例划到同一个簇，就可得到一个聚类类别。通过将所有各组紧密相连的实例划为各个不同的簇，就得到了最终将所有各组紧密相连的实例划为各个不同的簇，就得到了最终的聚类结果。的聚类结果。8.4 基于密度的聚类基于密度的聚类算法算法n8.4.1 基于密度聚类的基本概念基于密度聚类的基本概念8.4 基于密度的聚类基于密度的聚类算法算法n8.4.1 基于密度聚类的基本概念基于密度聚类的基本概念8.4 基于密度的聚类基于密度的聚类算法算法n8.4.1 基于密度聚
26、类的基本概念基于密度聚类的基本概念8.4 基于密度的聚类基于密度的聚类算法算法n8.4.1 基于密度聚类的基本概念基于密度聚类的基本概念8.4 基于密度的聚类基于密度的聚类算法算法n8.4.1 基于密度聚类的基本概念基于密度聚类的基本概念8.4 基于密度的聚类基于密度的聚类算法算法n8.4.2 DBSCAN算法算法8.4 基于密度的聚类基于密度的聚类算法算法n8.4.2 DBSCAN算法算法n8.4.3 DBSCAN算法的优缺点算法的优缺点nDBSCAN算法算法的的优点优点n1）不需要事先指定聚类的簇数）不需要事先指定聚类的簇数。n2）基于）基于“密度密度”概念进行聚类，可以对任意形状的稠密数
27、据集进概念进行聚类，可以对任意形状的稠密数据集进行聚类；行聚类；而而 k-means之类的算法一般只适用于对球状分布的凸数据之类的算法一般只适用于对球状分布的凸数据集进行聚类。集进行聚类。n3）可以在聚类的过程中发现数据集中的噪声实例（离群点），且）可以在聚类的过程中发现数据集中的噪声实例（离群点），且算法本身对噪声实例（离群点）不敏感。算法本身对噪声实例（离群点）不敏感。n4）在传统）在传统的的 k-means算法中算法中，k个个聚类中心的初始值选择以及实聚类中心的初始值选择以及实例的输入顺序会直接影响需要迭代的次数，对输出的聚类结果也例的输入顺序会直接影响需要迭代的次数，对输出的聚类结果也
28、有影响；而有影响；而DBSCAN算法对输入顺序不敏感，聚类结果没有偏差。算法对输入顺序不敏感，聚类结果没有偏差。n5）速度较快，可适用于较大的数据集）速度较快，可适用于较大的数据集。8.4 基于密度的聚类基于密度的聚类算法算法n8.4.3 DBSCAN算法的优缺点算法的优缺点n8.4 基于密度的聚类基于密度的聚类算法算法8.4 基于密度的聚类基于密度的聚类算法算法n8.4.4 OPTICS算法算法n8.4 基于密度的聚类基于密度的聚类算法算法n8.4.4 OPTICS算法算法n每个对象需要存储两个值每个对象需要存储两个值：n对象对象p的的核心距离核心距离(core-distance)是使得是使
29、得p成为核心对象的最成为核心对象的最小小。如果。如果p不是核心对象，不是核心对象，p的核心距离没有定义。的核心距离没有定义。n对象对象q关于另一个对象关于另一个对象p的的可达距离可达距离(reachability-distance)是是p的核心距离和的核心距离和p与与q的欧几里得距离之间的较大值。如果的欧几里得距离之间的较大值。如果p不是一个核心对象，不是一个核心对象，p和和q之间的可达距离没有定义。之间的可达距离没有定义。8.4 基于密度的聚类基于密度的聚类算法算法n8.4.4 OPTICS算法算法8.4 基于密度的聚类基于密度的聚类算法算法n8.4.4 OPTICS算法算法n8.4.4 O
30、PTICS算法算法n8.4 基于密度的聚类基于密度的聚类算法算法n8.4.4 OPTICS算法算法nOPTICS算法算法的的步骤步骤n4）判断该拓展点是否是）判断该拓展点是否是核心对象核心对象，若该点是核心对象，则找到该，若该点是核心对象，则找到该拓展点所有的拓展点所有的直接密度可达点直接密度可达点；若不是，则跳至；若不是，则跳至步骤步骤 3），取可达取可达距离倒数第二小的样本点。再判断该直接密度可达样本点是否已距离倒数第二小的样本点。再判断该直接密度可达样本点是否已经存在结果队列，是则不处理，否则下一步经存在结果队列，是则不处理，否则下一步。n5）将所有的直接密度可达点放入）将所有的直接密度
31、可达点放入有序队列有序队列，且将有序队列中的点，且将有序队列中的点按照可达距离重新排序，如果该点已经在有序队列中且新的可达按照可达距离重新排序，如果该点已经在有序队列中且新的可达距离较小，则更新该点的可达距离；如果有序队列中不存在该直距离较小，则更新该点的可达距离；如果有序队列中不存在该直接密度可达样本点，则插入该点并对有序队列进行重新排序接密度可达样本点，则插入该点并对有序队列进行重新排序。n6）迭代上述）迭代上述步骤步骤 2）至步骤至步骤 5），直至有序队列为空，此时输出直至有序队列为空，此时输出结果队列中样本点序列。结果队列中样本点序列。8.4 基于密度的聚类基于密度的聚类算法算法Question?
