数据挖掘与知识发现(8--模糊聚类).doc

装订线第8章 模糊聚类8.1 概 述聚类是人类一项最基本的认识活动，如“物以类聚，人以群分”。所谓聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽量小，类内的相似性尽量大。其数学描述为设给定数据集合，其中为数据对象，根据数据对象间的相似程度将数据集合分成组，并满足： 则该过程称为聚类，称为簇。聚类的基本方法经常是定义两个对象之间的距离，也可采用不依赖于距离的方法：首先定义一个优化目标，再优化得到某个局部最小值。聚类与分类区别：聚类是一个无监督的学习过程，属观察学习；而分类是有监督的学习过程，属示例学习。它们的根本区别在于，分类时需要事先知道分类所依据的属性值，而聚类是要找到这个分类的属性值。一般属性值有两类：数值属性和符号属性。关于数值属性聚类方法很多，而对符号属性聚类方法较少，常是将其转化为数值后再处理。聚类分析目前已广泛应用于诸多领域，包括模式识别、数据分析、图像处理、自动控制以及市场研究等。通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间的有趣的相互关系。8.2 聚类方法的分类聚类分析方法很多，通常是针对数据库中的记录，根据一定的分类规则，合理地划分记录集合，确定每个记录所在类别（如，-平均算法、-中心点算法、基于凝聚的层次聚类和基于分裂的层次聚类等）。一般来说，对于相同的数据集，若采用不同的聚类方法，可能有不同的划分结果。（1）按聚类的标准分，有统计聚类方法和概念聚类方法l 统计聚类方法：基于相似性测量。包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类，它需要考察所有个体才能决定类的划分。因此，它要求所有的数据必须预先给定，而不能动态增加新的数据对象。l 概念聚类方法：基于对象具有的概念。这里的距离不再是统计方法中的几何距离，而是根据概念的描述来确定的。典型的概念聚类或形成方法有：COBWEB、OLOC和基于列联表的方法。（2）按聚类的对象分，有数值聚类方法和符号值聚类方法l 数据聚类方法：所分析的数据的属性为数值数据，因此可对所处理的数据直接比较大小；l 符号值聚类方法：所分析的数据的属性为符号数据，因此对所处理的数据不能直接比较大小。 （3）按聚类尺寸分，有基于距离聚类、基于密度聚类和基于连续的聚类l 基于距离的聚类：根据数据之间的距离进行聚类。这种算法对于噪声数据和孤立点数据比较敏感；l 基于密度的聚类：该方法认为簇是具有相同密度的连通区域。因此，密度聚类需要扫描整个数据集，将数据空间划分为不同的小方格，并使用小方格的并来近似表示簇。该方法有可能不够精确，但该方法对于噪声数据和孤立点不敏感。该方法也可利用空间索引结构，通过计算超球区内的密度进行聚类，但该方法因为要维护复杂的索引结构，故对于海量数据存在效率问题；l 基于连续的聚类：将聚类对象映射为图模型或超图模型，然后根据边或者超边寻找连通的结点集合。8.3 常用的聚类算法聚类问题本质上是一个优化问题，即通过一种迭代运算使得系统的目标函数达到一个极小值。该目标函数为划分的评价函数。通常采用距离作为划分的评价标准，对数值属性主要采用欧氏距离，而对符号属性则通常采用Hamming距离。基于划分的聚类算法通过优化一个评价函数把数据集划分为个部分。当采用聚类内的距离的平方作为评价函数时，聚类内的所有点向聚类中心汇集，因此采用基于距离的划分评价函数方法得到的聚类是球形的。一般，不同的评价函数会优先选择不同的聚类结构。（1）-平均方法 -平均法是一种常用的基于划分的聚类方法。它根据最终分类的个数随机地选取个初始聚类中心，不断地迭代，直至达到目标函数的最小值，即得到最终的聚类结果为止。其中，目标函数通常采用平方误差准则，即 这里，为聚类对象；为类的各聚类对象（样本）的平均值。即 该方法在每一次迭代中，要计算每一个点和各聚类中心的距离，并将距离最近的聚类作为该点所属的类。所以-平均法的算法复杂度为，其中，-聚类数；-结点数；-迭代次数。-平均法是解决聚类问题的一种经典算法，是一种爬山式搜索算法。优点：算法简洁、快速。缺点：对初值敏感，且易陷入局部最优。（2）-中心点方法 与平均法的算法过程相似。唯一不同之处就是聚类中心的计算和表达。-中心点法是用类中最靠近中心的一个样本来代表该类。-中心点法最初随机选择个中心点，然后反复地试图找出更好的中心点。-中心点法的核心是中心点的选择。假设聚类C原先的中心点，现拟改为，则根据样本属于和其距离最近的聚类的原则，可能引起各样本所属聚类的情况发生调整。对于原先聚类C中的任意样本可能有两种情况：l 和的距离仍然小于和其他各聚类的中心点的距离，因此仍属于聚类聚类c；l 和其他某一聚类的中心点的距离最短，则将改属于聚类；假如使得总的距离平方和下降，则代替成为聚类C的新聚类中心，反之，则说明目前不适合作为聚类C的新的聚类中心，重新试探其他的点。相比于-平均法，-中心点算法对于噪声数据和异常数据不敏感，但计算量比-平均算法要大。（3）层次聚类层次的方法是对给定数据对象集合进行层次的分解。层次聚类的基本思想是：将模式样本按距离准则逐步聚类，直到满足分类要求为止。其聚类过程可表示为一个二叉层次树，叶结点表示一个样本，中间结点表示将数据集分割为两个不同的类，或一个类由它的两个子类合并而成。在层次聚类方法中，一旦一个步骤（合并或分裂）完成，它就不能被撤消。这既是优点，不用担心组合数目的不同选择，计算代价会较小；同时又是缺点，不能更正错误的决定。根据层次聚类的分解形成原理，层次聚类的方法可以分为凝聚方法和分裂方法。a) 凝聚方法也称为自底向上方法。一开始将每个对象作为单独的一个类，然后相继地合并相近的对象或组，将较小的数据对象子集合依据相似程度进行合并，这些小的数据对象子集合逐渐合并成较大的数据对象子集合，直到所有的类合并为一个，或者达到一个终止条件为止，从而构成一个类的层次。假设和是两个聚类，则两类间的最短距离定义为 其中，表示样本和间的距离。凝聚方法的算法描述为 For i=1,2,n 令； While 存在一个以上的聚类 do If then ; 删除; End;采用凝聚方法的典型聚类算法有：BIRCH、CURE、CHAMELON等。b) 分裂方法也称自顶向下方法。一开始将所有的对象置于一个类中，在迭代的每一步中，一个类被分裂为更小的类，直到每个对象在单独的一个类中，或者达到一个终止条件为止。通常情况下，凝聚方法优于分裂方法。DIANA是分裂方法的代表。8.4模糊聚类在客观世界中，存在着大量的界限模糊并不分明的聚类问题，如区分“年青人”和“中年人”时就需要模糊的划分，由此诞生了模糊聚类。模糊聚类的开创性工作是由Ruspini于1969年提出的，是基于Zadeh教授1965年提出的模糊集合论。之后，Bezdek和Dunn于1987年提出了C-均值模糊聚类法。目前，有关模糊聚类的方法很多，并已应用于生物学、商业、经济、工程、信息科学、医药学等许多领域。常用的模糊聚类方法有：系统聚类法、传递闭包法以及与此等价的最大支撑树的Prim算法及Kruskal算法、动态直接聚类法，基于摄动的模糊聚类法FCMBP、模糊C-均值法、模糊ISODATA算法、人工神经网络模糊聚类法等。聚类算法分为分割和分层两种。分割聚类算法通过优化目标函数，把数据集分割成若干部分，如模糊k-均值聚类法。分层聚类是由不同层次的分割聚类组成，层次之间的分割具有嵌套的关系，如传递闭包法和摄动的模糊聚类法FCMBP。1）聚类结果的表示通常的聚类是把含n个对象的集合划分成K个不相交的部分，称之为聚类块。聚类的结果可表示为一个阶矩阵，其中 （说明每个元素属于且仅属于1个聚类） 模糊聚类的结果表示，就是将上面通常的聚类结果表示替换为使 2）模糊聚类的一般模型聚类问题实质上是在一定的聚类准则下的优化问题，只是不同的聚类方法其聚类对象的属性值与目标函数不同。三维数据模糊聚类可以看作一个模糊聚类的一般模型。（对象、属性、情形）设三维数据由n个对象在T个时刻的p个属性的值构成。记为 （即每时刻对应一张二维表）聚类的目的，就是将n个对象的集合分成K个模糊聚类块。即是上的模糊集合。这K个模糊集合的隶属函数即每个对象相对于聚类块的隶属度表示为 ，时刻的聚类中心表示为 时刻的目标函数为 （按列求方差）如果存在一个解使得最小，则就是最优解。但通常这种最优解不存在，所以，三维数据聚类是一个多目标优化问题。设是可行解的集合，那么加权和的单聚类准则为 8.5 传递闭包法 1）模糊相似系数的标定基于模糊相似关系的模糊聚类，首先是建立模糊相似矩阵，建立模糊相似矩阵的关键就是相似系数。相似系数反映了样本之间相对于某些属性的相似程度。确定相似系数的方法很多，可根据实际问题选择使用。设为被分类对象的全体，以表示每一对象的特征数据。常用的方法有： 数量积法 如果中出现负值，可采用如下方法调整： 法1：令 ，则； 法2：令 其中，。于是 夹角余弦法 ，当出现负数时，用上面的方法调整 统计相关系数法 其中，。 最大最小法 算术平均最小法 几何平均最小法 绝对值指数法 指数相似系数法 绝对值倒数法 其中，M适当选取，使且分开。 绝对值减数法 其中，c适当选取，使且分开。 非参数法 令 ， 中的正数个数 中的负数个数 贴近度法 如果把的特征归一化，使，则的相似程度取为其贴近度。距离贴近度为 其中，为适当选择参数值；为模糊集各种距离，可以取闵可夫斯基距离： 当p=1时为海明距离，p=2时为欧氏距离。 专家打分法 请若干专家直接对的相似程度打分，取其平均值作为。上述方法均可建立模糊相似矩阵，由于它满足对称性和自反性，不满足传递性。所以还需建立一个Fuzzy等价阵，根据模糊等价阵才能聚类。 2）传递闭包法模糊相似矩阵R的传递闭包是指包含R的最小模糊等价矩阵。利用平方法可以求得模糊相似矩阵的传递闭包，其理论依据为定理：设为阶模糊相似矩阵，则存在一个最小自然数，使得传递闭包，且对一切大于的自然数，恒有。该定理说明，从模糊相似矩阵出发，利用平方法依次计算，当第一次出现时，就是传递闭包。计算方法为，设模糊相似矩阵，则，其中 计算量是。 3）动态直接聚类法基本概念：主元、双重主元、单重主元、填充替换、合并变换、清洗变换、分解集、连通元、连接元。定义1：设为模糊相似矩阵，的第行非主对角线上的元素可写为 （1）我们称式（1）中的最大元或重复出现的几个极大元中的最左侧的元素称为的第行主元。定义2：如果为模糊相似矩阵，为第行第列的主元，则称为的双重主元。在R的主元中，非双重主元的主元称为R的单重主元。定义3：给定若干个两两不交的集合 （2）若存在集合及式（2）中唯一集合，使得，则用代替。称这种变换为T对式（2）进行填充变换。若存在集合及式（2）中两个集合和，使得，则用代替，并将从式（2）中删除，得到新集合列的过程，称为对式（2）进行合并变换。若，则在R中去掉的过程，称为对R进行清理变换。定义4：假设R的各个双重主元的足码集合为 （3）若R的各个双重主元的足码集对式（3）进行填充变换而得新的足码集，称为R的行标分解集。 算法8.1 连接元算法 找出R的各个双重主元与单重主元，并写出R的行标分解集； 如果，且不是R的双重主元与单重主元，我们称之为R的连通元。找出R的所有连通元； 在R的除去主元与连通元的元素中，取一个最大的元，称为R的连接元，如果有几个可任取一个。如果已选取到个连接元，则算法停止；否则转步骤下一步； 用连接元对已有足码集进行合并变换，并对R进行清理变换，而后转步骤。定义5：R的双重主元、单重主元、连接元统称为R的基元。算法8.2 动态直接聚类法 建立模糊相似矩阵； 求R的基元； 画出动态聚类图，或以集合方式写出各水平下的聚类结果。 4）最大树法 最大树法是我国学者吴望名提出的，它有两种算法：Prim法和Kruskal法。总体步骤为l 建立模糊相似矩阵；l 画出最大树；l 聚类算法1：Prim法设待分类对象的集合简记为，给定的模糊相似矩阵为（） 先取对象，在对象，中，找出与相关系数最大的，这里0.8(1,3)，画出下图：在，中，找出与对象的最大系数.5=R(1,4)；找出与对象最大的相关系数0.3=R(3,4)，因为0.50.3，取对象，得下图：，再在，中找出与，最大的相关系数，0.6=R(4,5)，得下图最后找出与，之间最大的相关系数.4=R(2,5)，得最大树为（） 取，砍断连接权重小于的枝，就可得到一个不连通的图，而各连通分支就构成了水平上的分类。如，若取，则只得一类，；若取，则得两类，；若取，则得三类，；若取，则得四类，；若取，则得五类，算法：ruskal法（） 先在的非主对角线中找到最大元0.8=R(1,3)，得下图：再找次最大元0.6=R(4,5)，0.=R(,)，得下图：最后得到0.=R(,)，至此所有顶点都被连到，且不含圈，从而得到最大树。（） 以下算法同算法中的步骤注：用上述两种方法得到的最大树可能不同，但可以证明其分类结果相同。用rim法至多需要进行次运算，用ruskal法至多需要进行次运算。传递闭包法和动态直接聚类法，以及最大树法的分类结果相同的。但动态直接聚类法计算量比较小。8.6 系统聚类法是目前国内外使用最多的一种方法。其基本思想是：先将n个样本各自看成一类，然后规定样本之间的距离和类与类之间的距离。开始时，各个样本自成一类，类与类之间的距离与样本之间的距离是相等的。选择距离最近的一对合并为一个新类。计算新类与其他类的距离，再将距离最近的两类合并，这样每次减少一类，直至所有的样品都归为一类为止。类与类之间的距离定义多种多样，最常用的有8种之多，包括最短距离、最长距离、中间距离、重心距离、类平均距离、可变类平均法、可变法、离差平方和法。以上8种系统聚类法的并类原则和步骤是完全相同的，所不同的是类与类之间的距离有不同的定义，从而得到不同的递推公式。Wishart在1969年把它们的递推公式统一了起来。为简单起见，这里只给出最短距离的步骤。1. 最短距离法用表示样本与的距离，表示类，定义类与类之间的距离为两类最近样品的距离，用表示与之间的距离，则用最小距离法聚类的算法步骤如下： 规定样本之间的距离，计算样本两两距离的对称阵，记为，开始每个样品自成一类，因此，； 选择的最小元素，设为，将与合并为一类，记为； 计算新类与其他类之间的距离 将中行列合并为一个新行新列。新行新列对应，所得到的矩阵记为； 对重复上面对的两步，得到，如此下去直到所有元素聚为一类。如果某一步中的最小元素不止一个，则对应之些最小元素的类同时合并。2. 最长距离法 3. 中间距离法 中间距离法的推广形式： 4. 重心距离法 其距离推广公式为： 其中，类与的样本个数为。将与合并为，则样本个数为 5. 类平均距离法 其递推公式为 6. 可变类平均法 7. 可变法 8. 离差平方和法 设将n个样品分成k类，用表示中的样品，表示中样品的个数，是的重心，则在中的样品的整个类内距离差平方和是 Wart提出如下算法：l 先将n个样品各自成一类；l 然后每次缩小一类，每缩小一类距离差平方和都要增加l 选择使S增加最小的两类合并，直到所有的样品归为一类为止。把两类合并所得的距离差平方和看成平方距离，则以下递推公式： Wishart在1969年提出了系统聚类的统一公式为： 其中，系统对于不同方法有不同的取值。8.7 C-均值聚类法C-均值聚类是一种简便实用的无监督学习算法，此种方法能够用于已知类数的数据聚类和分类。其基本步骤如下： 选取聚类块数k； 从训练集中任意