2022年聚类算法学习笔记.docx

《2022年聚类算法学习笔记.docx》由会员分享，可在线阅读，更多相关《2022年聚类算法学习笔记.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 细心整理 欢迎下载聚类的定义聚类是一个将数据集划分为如干个子集的过程,并使得同一集合内的数据对象具有较高的相像度, 而不同集合中的数据对象就是不相同的,相像或不相像的度量是基于数据对象描述属性的聚类值来确定的,通常就是利用各个聚类间的距离来进行描述的； 聚类分析的基本指导思想是最大程度地实现类中对象相像度最 大,类间对象相像度最小；聚类与分类不同, 在分类模型中, 存在样本数据, 这些数据的类标号是已知的,分类的目的是从训练样本集中提取出分类的规章,用于对其他标号未知的对象进行类标识； 在聚类中, 预先不知道目标数据的有关类的信息,需要以某种度

2、量为标准将全部的数据对象划分到各个簇中；习；聚类主要包括以下几个过程：因此,聚类分析又称为无监督的学（1）数据预备：包括特点标准化和降维；（2）特点挑选、提出：从最初的特点中挑选是有效的特点,并将其储备于 向量中；（3）特点提取：通过对所挑选的特点进行转换,形成新的突出特点；（4）聚类（或分组）：第一挑选合适特点类型的某种距离函数（或构造新的 距离函数）进行接近程度的度量,然后执行聚类或分组；聚类结果评估：指对聚类结果进行评估；评估主要有 部有效性评估和相关性测试评估；聚类算法的要求（1）可扩展性；很多聚类算法在小数据集（少于3 种：外部有效性评估、内200 个数据对象）时可以工作很好； 但一

3、个大数据库可能会包含数以百万的对象；利用采样方法进行聚类 分析可能得到一个有偏差的结果,这时就需要可扩展的聚类分析算法；（2）处理不同类型属性的才能；很多算法是针对基于区间的数值属性而设 计的；但是有些应用需要对实类型数据；如：二值类型、符号类型、次序类型,或这些数据类型的组合；（3）发觉任意外形的聚类；很多聚类算法是依据欧氏距离和 Manhattan 距 离来进行聚类的； 基于这类距离的聚类方法一般只能发觉具有类似大小和密度的名师归纳总结 - - - - - - -第 1 页,共 6 页精选学习资料 - - - - - - - - - 细心整理 欢迎下载圆形或球状聚类； 而实际一个聚类是可以

4、具有任意外形的,因此设计能够发觉任意开关类集的聚类算法是特别重要的；（4）需要（由用户）打算的输入参数最少；很多聚类算法需要用户输入聚类分析中所需要的一些参数（如：期望所获得聚类的个数）；而聚类结果通常都与输入参数亲密相关； 而这些参数经常也很难打算, 特殊是包含高维对象的数据集；这不仅构成了用户的负担,也使得聚类质量难以掌握；（5）处理噪声数据的才能；大多数现实世界的数据库均包含反常数据、不 明数据、数据丢失和噪声数据, 有些聚类算法对这样的数据特别敏锐并会导致获 得质量较差的数据；（6）对输入记录次序不敏锐；一些聚类算法对输入数据的次序敏锐,也就是不同的数据输入次序会导致获得特别不同的结果

5、；敏锐的聚类算法也是特别重要的；因此设计对输入数据次序不（7）高维问题；一个数据库或一个数据仓库或许包含如干维属性；很多聚 类算法在处理低维数据时 （仅包含二到三个维） 时表现很好, 然而设计对高维空 间中的数据对象, 特殊是对高维空间稀疏和怪异分布的的数据对象,能进行较好 聚类分析的聚类算法已成为聚类讨论中的一项挑战；（8）基于约束的聚类；现实世界中的应用可能需要在各种约束之下进行聚类分析；假设需要在一个城市中确定一些新加油站的位置,就需要考虑诸如： 城市中的河流、 调整路,以及每个区域的客户需求等约束情形下居民住地的聚类分 析；设计能够发觉满意特定约束条件且具有较好聚类质量的聚类算法也是一

6、个重 要聚类讨论任务；（9）可说明性和可用性；用户往往期望聚类结果是可懂得的、可说明的,以及可用的, 这就需要聚类分析要与特定的说明和应用联系在一起；因此讨论一 个应用的目标是如何影响聚类方法挑选也是特别重要的；各种聚类算法介绍随着人们对数据挖掘的深化讨论和明白,各种聚类算法的改进算法也相继提出,很多新算法在前人提出的算法中做了某些方面的提高和改进,且很多算法是有针对性地为特定的领域而设计； 我们必需清晰地明白各种算法的优缺点和应用范畴,依据实际问题挑选合适的算法；名师归纳总结 - - - - - - -第 2 页,共 6 页精选学习资料 - - - - - - - - - 细心整理 欢迎下载

7、基于层次的聚类算法 基于层次的聚类算法对给定数据对象进行层次上的分解,可分为凝结算法和 分裂算法； 1 自底向上的凝结聚类方法；这种策略是以数据对象作为原子类,然后将 这些原子类进行聚合； 逐步聚合成越来越大的类, 直到满意终止条件； 凝结算法 的过程为：在初始时,每一个成员都组成一个单独的簇,在以后的迭代过程中,再把那些相互邻近的簇合并成一个簇,直到全部的成员组成一个簇为止；其时间 和空间复杂性均为 On2；通过凝结式的方法将两簇合并后,无法再将其分别到 之前的状态；在凝结聚类时,挑选合适的类的个数和画出原始数据的图像很重要； 2 自顶向下分裂聚类方法；与凝结法相反,该法先将全部对象置于一个

8、簇中,然后逐步细分为越来越小的簇, 直到每个对象自成一簇, 或者达到了某个终结条 件；其主要思想是将那些成员之间不是特别紧密的簇进行分裂；跟凝结式方法的 方向相反, 从一个簇动身, 一步一步细化； 它的优点在于讨论者可以把留意力集 中在数据的结构上面； 一般情形下不使用分裂型方法, 由于在较高的层很难进行 正确的拆分 基于密度的聚类算法很多算法都使用距离来描述数据之间的相像性,但对于非凸数据集, 只用距离来描述是不够的； 此时可用密度来取代距离描述相像性,即基于密度的聚类算法；它不是基于各种各样的距离, 所以能克服基于距离的算法只能发觉“ 类圆形”的聚类的缺点； 其指导思想是： 只要一个区域中

9、的点的密度 （对象或数据点的数目）大过某个阈值, 就把它加到与之相近的聚类中去；该法从数据对象的分布密度动身,把密度足够大的区域连接起来,从而可发觉任意外形的簇, 并可用来过滤“ 噪声” 数据；常见算法有 DBSCAN,DENCLUE等基于划分的聚类算法给定一个 N 个对象的元组或数据库,依据给定要创建的划分的数目 k,将数据划分为 k 个组,每个组表示一个簇类（ =N）时满意如下两点： 1 每个组至少包含一个对象； 2 每个对象必需属于且只属于一个组；算法先随机创建一个初始划分,然后采纳一种迭代的重定位技术,通过将对象依据簇类之间的差异从一名师归纳总结 个划分移到另一个划分来提高簇类内数据之

10、间的相像程度；一种好的划分的一般第 3 页,共 6 页- - - - - - -精选学习资料 - - - - - - - - - 细心整理 欢迎下载准就是：在同一个类中的对象尽可能“ 接近” 或相像,而不同类中的对象尽可能“ 远离” 或不同； 为了达到全局最优, 基于划分的聚类会要求穷举全部可能的划 分；典型的划包括： K-means,PAM,EM等；划分法收敛速度快,在对中小规模 的数据库中发觉球状簇很适用； 缺点是它倾向于识别凸形分布大小相近、密度相 近的聚类, 不能发觉分布外形比较复杂的聚类,它要求类别数目 k 可以合理地估计,且初始中心的挑选和噪声会对聚类结果产生很大影响；聚类个数；基

11、于网格的聚类算法仍要求用户预先指定第一将数据空间量化为有限个单元的网格结构,然后对量化后的单个的单元为对象进行聚类；典型的算法有STING,CLIQUE等；网格聚类法处理速度快,处理时间与数据对象的数目无关, 一般由网格单元的数目打算； 缺点是只能发觉边 界是水平或垂直的聚类, 不能检测到斜边界； 该类算法也不适用于高维情形,因 为网格单元的数目随着维数的增加而呈指数增长；另外仍有以下问题：一是如 何挑选合适的单元大小和数目, 二是怎样对每个单元中对象的信息进行汇总,三 是存在量化尺度的问题；基于模型的聚类算法基于模型的方法给每一个聚簇假定了一个模型,然后去查找能够很好满意这个模型的数据集；

12、这个模型可能是数据点在空间中的密度分布函数,它由一系列的概率分布打算, 也可能通过基于标准的统计数字自动打算聚类的数目；它的一个潜在假定是： 目标数据集是由一系列的概率分布所打算的；一般有 2 种尝试方向：统计的方案和神经网络的方案；COBWEB 是一种流行的简洁增量概念聚类算法,以一个分类树的形式来创建层次聚类,它的输入对象用分类属性- 值对来描 述； COBWEB 的优点为：可以自动修正划分中类的数目；不需要用户供应输入参 数；缺点为： COBWEB 基于这样一个假设：在每个属性上的概率分布是彼此独立 的；但这个假设并不总是成立； 且对于偏斜的输入数据不是高度平稳的,它可能 导致时间和空间

13、复杂性的猛烈变化,不适用于聚类大型数据库的数据；模糊聚类算法 现实中很多对象没有严格的属性, 其类属和外形存在着中介性, 适合软划分；恰好模糊聚类具有描述样本类属中间性的优点,因此成为当今聚类分析讨论的主名师归纳总结 - - - - - - -第 4 页,共 6 页精选学习资料 - - - - - - - - - 细心整理 欢迎下载流；常用的模糊聚类有动态直接聚类法、最大树法、FCM等；基本原理为：假设有 N个要分析的样本,每个样本有M个可量化的指标,一般步骤为：1 标准化数据：常用的数据标准化方法有：小数定标规范化,最大最小值规范化,标准差规范化等； 2 建立模糊相像矩阵,标定相像系数；3

14、运算多极相像矩阵,运算整体相像关系矩阵,有传递闭包法,动态直接聚类法,最大树法等；4 给定一个聚类水平, 运算肯定相像矩阵, 按行列调整肯定相像矩阵, 每个分块即为一个分类；其它聚类算法（1）基于群的聚类方法该法是进化运算的一个分支, 模拟了生物界中蚁群、 鱼群等在觅食或避敌时的行为；可分为蚁群算法ACO和 PSO；蚁群聚类算法的很多特性,如敏捷性、健壮性、分布性和自组织性等, 使其特别适合本质上是分布、动态及又要交叉的问题求解中,能解决无人监督的聚类问题,具有宽阔的前景；PSO模拟了鱼群或鸟群的行为；在优化领域, PSO可以与遗传算法相媲美,并在猜测精度和运行速度方面占优势； 对 ACO或

15、PSO在数据挖掘中应用的讨论仍处于早期阶段,要将这些方法用到实际的大规模数据挖掘的聚类分析中仍需要做大量的讨论工作；（2）基于粒度的聚类方法从粒度的角度看,我们会发觉聚类和分类有很大的相通之处：聚类操作实际上是在一个统一粒度下进行运算的；分类操作是在不同粒度下进行的；所以说在粒度原理下,聚类和分类是相通的,很多分类的方法也可以用在聚类方法中；作为一个新的讨论方向, 虽然目前粒度运算仍不成熟, 特殊是对粒度运算语义的讨论仍相当少, 但信任随着粒度理论的不断进展,其相关领域得到广泛的应用；（3）谱聚法今后几年它必将在聚类算法及谱聚类方法建立在谱图理论基础之上,并利用数据的相像矩阵的特点向量 进行聚

16、类,是一种基于两点间相像关系的方法, 这使得该方法适用于非测度空间；它与数据点的维数无关, 而仅与数据点的个数有关, 可以防止由特点向量的过高 维数所造成的奇特性问题； 它又是一个判别式算法, 不用对数据的全局结构作假名师归纳总结 设,而是第一收集局部信息来表示两点属于同一类的可能性；然后依据某一聚类第 5 页,共 6 页- - - - - - -精选学习资料 - - - - - - - - - 细心整理 欢迎下载判据作全局决策, 将全部数据点划分到不同的数据集合中；通常这样的判据可以 在一个嵌入空间中得到说明,该嵌入空间是由数据矩阵的某几个特点向量张成 的；谱聚类算法胜利缘由在于： 通过特点

17、分解, 可以获得聚类判据在放松了的连 续域中的全局最优解；与其他算法相比,它不仅思想简洁、易于实现、不易陷入局部最优解, 而且具有识别非凸分布的聚类才能,特别适合于很多实际问题； 目前,该算法已应用于语音识别、VLSI 设计、文本挖掘等领域；（4）多种聚类方法的融合实际应用的复杂性和数据的多样性往往使得单一的算法无能为力；因此,很多人对多种算法的融合进行了广泛讨论并取得了一些成果；大致可分为以下几类： 1 基于传统聚类方法的融合,如CLIQUE、CUBN等； 2 模糊理论与其他聚类法的融合, 如遗传模糊 C2均值混合聚类法等； 3 遗传算法与机器学习的融 合； 4 传统聚类法与其他学科理论的融合,如谱算法等；总之,很多新算法是以上几类方法中两种或两种以上方法有机结合而得的,这也是我们数据挖掘讨论人员要努力的讨论方向之一；它们取长补短,优势明显,名师归纳总结 - - - - - - -第 6 页,共 6 页