6.5 划分聚类方法

6.5划分聚类方法划

分

聚

类

方

法划分方法给定包含n个数据对象的数据库和所要形成的聚类个数k，划分算法将对象集合划分为k份（k≤n），其中每个划分均代表一个聚类。所形成的聚类将使得一个客观划分标准（常称为相似函数，如距离）最优化；从而使得一个聚类中的对象是“相似”的；而不同聚类中的对象是“不相似”的。遵循的是全局最优原则，需要穷举所有可能的划分。划分聚类方法给定一个包含n个对象的集合，构建数据的K个分区。大部分分割方法是基于距离的，所以只能发现球类簇。划

分聚类方法划分方法的特点Ø发现球状互斥的簇Ø基于距离Ø可以用均值或者中心点代表簇的中心Ø对中小规模数据有效划

分

聚

类

方

法划分方法（K-means）K-means聚类又称K-平均算法，是MacQueen提出的一种无监督的聚类算法，它在最小化误差函数的基础上将样本集划分为预定的类数k。划

分

聚

类

方

法K-means步骤可视化初始化散点图

初始化聚类中心迭代10次，聚类中心轨迹

最终聚类效果划

分

聚

类

方

法示例

假设空间数据对象分布如图5-5(a)所示，设是k＝3，也就是需要将数据集划分为3个簇（聚类）。图5-5k-means算法聚类过程示意描述划

分聚类方法示例

根据算法5.1，从数据集中任意选择三个对象作为初始聚类中心(图(a)中这些对象被标上了“+”)，其余对象则根据与这三个聚类中心(对象)的距离，根据最近距离原则，逐个分别聚类到这三个聚类中心所代表的(3个)聚类中，由此获得了如图(a)所示的三个聚类(以虚线圈出)。划

分聚类方法示例

在完成第一轮聚类之后，各聚类中心发生了变化。继而更新3个聚类的聚类中心(图(b)中这些对象被标上了“十”)，也就是分别根据各聚类中的对象重新计算相应聚类的(对象)均值。根据所获得的3个新聚类中心，以及各对象与这三个聚类中心的距离，(根据最近距离原则)对所有对象进行重新归类。有关变化情况如图(b)所示(已用粗虚线圈出)。划

分聚类方法示例

再次重复上述过程就可获得如图(c)所示的聚类结果(已用实线圈出)，这时由于各聚类中的对象(归属)已不再变化，整个聚类结束。算法的特点：只适用于聚类均值有意义的场合，在某些应用中，如：数据集中包含符号属性时，直接应用k-means算法就有问题；用户必须事先指定k的个数；对噪声和孤立点数据敏感，少量的该类数据能够对聚类均值起到很大的影响；通常以局部最优结束。不适合发现非凸形状的簇，或者大小差别很大的簇划

分

聚

类

方

法基于密度的聚类方法DBSCAN算法是一种基于高密度联通区域的聚类算法，它将类簇定义为高密度相连点的最大集合。它本身对噪声不敏感，并且能发现任意形状的类簇。基本思想为：如果一个对象在它半径为ℇ的邻域中至少包含有MinPts个对象，那么该区域被认为是密集的。为了明确这样的密集区域，该算法涉及到有关密度的一系列定义，进而根据这些定义来确定密集区域，即确定各个类并隔离出异常值。划

分

聚

类

方

法基于密度的聚类方法n

ε−近邻：

一个给定对象的ε半径内的近邻就称为该对象的ε−近邻；n对象阈值： 一个对象的ε−近邻中数据对象阈值；n核对象： 若一个对象的ε−近邻至少包含一定数目（MinPts）的对象，该对象就称为核对象；n直接密度可达： 给定一组对象集，若对象为另一个对象的ε−近邻且为核对象，那么就说是从可以“直接密度可达”；划

分

聚

类

方

法基于密度的聚类方法

划

分

聚

类

方

法划分方法（DBSCAN）DBSCAN是一个基于高密度连接区域的密度聚类方法，该算法将具有足够高密度的区域划分为簇，它定义簇为密度相连的点的最大集合。DBSCAN通过检查数据库中每个点的ε−近邻，不断生长足够高密度区域来寻找聚类，能够在带有“噪声”的空间数据库中发现任意形状的聚类。划

分

聚

类

方

法基于网格的方法基于网格聚类方法利用多维网格数据结构。它将空间划分为有限数目的单元，以构成一个可以进行聚类分析的网格结构。这种方法的主要特点就是处理时间与数据对象数目无关，仅依赖于量化空间中每一维上的单元数目，因此基于网格聚类方法处理时间很短。下面是其中两种代表算法：STING将空间划分为方形单元。不同层次的方形单元对应不同层次的分辨率。这些单元构成了一个层次结构：高层次单元被分解形成一组低层次单元。有关各网格单元属性的统计信息（如均值、最大、最小）可以事先运算和存储。这些信息将在查询处理用到。CLIQUE给定一个大规模多维数据点，数据空间中的数据点通常并不是均匀分布的。聚类识别稀疏和“拥挤”空间区域（unit），以便发现数据集的整个分布；若一个unit所包含数据点中的一部分超过了输入模型参数，那么这个unit就是密集的。方法中，一个聚类被定义为连接的密集的最大集合。划

分

聚

类

方

法

基于模型的聚类方法试图对给定数据与某个数学模型达成最佳拟合。这类方法基于数据都是有一个内在的混合概率分布假设来进行的，通常假定数据具备一定的概率分布，并通过优化给定的数据，使其适应某些数学模型，并基于此产生聚类。基于模型聚类方法主要有两种：统计方法和神经网络方法。神经网络聚类方法是将每个聚类描述成一个例证（exemplar）。每个例证作为聚类的一个“典型”；它不必与一个示例或对象相对应。可以根据新对象与哪个例证最相似（基于某种距离计算方法）而将它分派到相应的聚类中。可以通过聚类的例证来预测分派到该聚类的一个对象的属性。划

分

聚

类

方

法模糊聚类算法FCM在一些没有确定支持的情况中，聚类可以引入模糊逻辑概念。对于模糊集来说，一个数据点都是以一定程度属于某个类，也可以同时以不同的程度属于几个类。常用的模糊聚类算法是1973年提出的模糊C平均值(FuzzyC-Means，FCM)算法，经常用于模式识别。FCM算法采用误差平方和函数作为聚类准则函数，即FCM试图最小化误差的平方和。划

分

聚

类

方

法例6.8Iris鸢尾花数据集是常用的分类实验数据集，其内包含3类分别为山鸢尾（Iris-setosa）、变色鸢尾（Iris-versicolor）和维吉尼亚鸢尾（Iris-virginica），共150条记录，每类各50个数据，每条记录都有4项特征：花萼长度、花萼宽度、花瓣长度、花瓣宽度，以上四个特征的单位