浅谈聚类算法

浅谈聚类算法第一页，共十六页，2022年，8月28日1.引言数据挖掘：指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。它是人工智能和数据库发展相结合的产物，是国际上数据库和信息决策系统最前沿的研究方向之一。数据挖掘主要的算法有分类模式、关联规则、决策树、序列模式、聚类模式分析、神经网络算法等等。聚类是数据挖掘中的一个非常重要的研究课题，广泛应用于各个领域，它对未知数能达到合理的效果。研究和运用聚类是完成数据挖掘任务的重要手段，因此对聚类的研究具有重要的理论价值和现实意义。第二页，共十六页，2022年，8月28日2.聚类算法基本原理概述俗话说：“人以群分，物以类聚”。聚类就是利用计算机技术来实现这一目的的一种技术。聚类是指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。聚类与分类不同：分类问题中我们知道数据集的分类属性。而聚类问题则需要我们从数据集中找这个分类属性。迄今为止,聚类还没有一个学术界公认的定义.这里给出Everitt在1974年关于聚类所下的定义:一个类簇内的实体是相似的,不同类簇的实体是不相似的;一个类簇是测试空间中点的会聚,同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离;类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域,它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离.。聚类的标准是使簇内相似度尽可能大，簇间相似度尽可能小。第三页，共十六页，2022年，8月28日3.数据挖掘算法对聚类的典型要求伸缩性：聚类算法对小数据集和大规模数据集要同样有效。处理不同类型属性的能力：实际应用要求算法能够处理不同类型的数据。能发现任意形状的聚类：聚类特征的未知性决定聚类算法要能发现球形的、嵌套的、中空的等任意复杂形状和结构的聚类。使决定输入参数的领域知识最小化：聚类算法要尽可能地减少用户估计参数的最佳取值所需要的领域知识。能够有效地处理噪声数据：聚类算法要能处理现实世界的数据库中普遍包含的孤立点，空缺或者错误的数据。第四页，共十六页，2022年，8月28日对于输入纪录的顺序不敏感：聚类算法对不同的次序的记录输入应具有相同的聚类结果。高维性：聚类算法不仅要擅长处理低维的数据集，而且要能处理高维、数据可能非常稀疏且高度偏斜的数据集。基于约束的聚类：聚类结果既要满足特定的约束。又要具有良好聚类特性。可解释性和可用性：聚类结果应该是可解释的、可理解的和可用的。第五页，共十六页，2022年，8月28日4.聚类算法分类研究没有任何一种聚类技术(聚类算法)可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构.根据数据在聚类中的积聚规则以及应用这些规则的方法,有多种聚类算法.聚类算法有多种分类方法,这里将聚类算法大致分成层次化聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法.

第六页，共十六页，2022年，8月28日4.1划分式聚类算法划分聚类算法把数据点集分为k个划分，每个划分作为一个聚类。它一般从一个初始划分开始，然后通过重复的控制策略，使某个准则函数最优化，而每个聚类由其质心来代表(K-MEANS算法)，或者由该聚类中最靠近中心的一个对象来代表(K-MEDOIDS算法)。划分聚类算法收敛速度快，缺点在于它倾向于识别凸形分布大小相近、密度相近的聚类，不能发现分布形状比较复杂的聚类，它要求类别数目k可以合理地估计，并且初始中心的选择和噪声会对聚类结果产生很大影响。划分式聚类算法需要预先指定聚类数目或聚类中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。第七页，共十六页，2022年，8月28日K均值聚类1967年,MacQueen首次提出了K均值聚类算法(K-means算法).迄今为止,很多聚类任务都选择该经典算该算法的核心思想是找出K个聚类中心C1,C2,…,Ck,使得每一个数据点xi和与其最近的聚类中心Cv的平方距离和被最小化(该平方距离和被称为偏差D).K均值(K-means)聚类算法(对n个样本进行聚类) 1[初始化].随机指定K个聚类中心(C1,C2,…,Ck); 2[分配xi].对每一个样本xi,找到离它最近的聚类中心Cv,并将其分配到Cv所标明类; 3[修正Cw].将每一个Cw移动到其标明的类的中心; 4[计算偏差]. 5[D收敛?].如果D值收敛,则return(C1,C2,…,Ck)并终止本算法;否则,返回步骤K2.第八页，共十六页，2022年，8月28日K-means算法的优点与不足。优点：能对大型数据集进行高效分类，其计算复杂性为O(tkmn)，其中，t为迭代次数，K为聚类数，m为特征属性数，n为待分类的对象数，通常K、m、t<<n。在对大型数据集聚类时，K-means算法比层次聚类算法快得多。不足：通常会在获得一个局部最优值时终止；仅适合对数值型数据聚类。第九页，共十六页，2022年，8月28日4.2层次化聚类算法分层聚类算法把数据对象分组而形成一个聚类树。分层聚类算法分为两大类：聚结型和分裂型。聚结型算法采用自底向上的策略，首先把每个对象单独作为一个聚类，然后根据一定的规则合并成为越来越大的聚类，直到最后所有的对象都归入到一个聚类中。大多数分层聚类算法都属于聚结型算法，它们之间的区别在于类间相似度的定义不同。与聚结型算法相反，分裂型算法采用自顶向下的方法。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。纯粹的分层聚类算法的缺点在于一旦进行合并或分裂之后，就无法再进行调整。现在的一些研究侧重于分层聚类算法与循环的重新分配方法的结合。适合于小型数据集的分类。第十页，共十六页，2022年，8月28日层次聚结算法该算法由树状结构的底部开始逐层向上进行聚合,假定样本集S={o1,o2,…,on}共有n个样本. 1[初始化].置每个样本oi为一个类; /*共形成n个类:o1,o2,…,on*/ 2[找最近的两个类],distance(or,ok)=min[distance(ou,ov)],其中ou,ov属于S，但不相等. /*从现有的所有类中找出距离最近(相似度最大)的两个类or和ok*/

3[合并or和ok].将类or和ok合并成一个新类ork; /*现有的类数将减1*/

4若所有的样本都属于同一个类,则终止本算法;否则,返回步骤HA2.第十一页，共十六页，2022年，8月28日4.3基于网格和密度的聚类算法基于网格和密度的聚类方法是一类重要的聚类方法,它们在以空间信息处理为代表的众多领域有着广泛应用.特别是伴随着新近处理大规模数据集、可伸缩的聚类方法的开发,其在空间数据挖掘研究子域日趋活跃。很多算法中都使用距离来描述数据之间的相似性，但是，对于非凸数据集，只用距离来描述是不够的。对于这种情况，要用密度来取代相似性，这就是基于密度的聚类算法。基于密度(单位区域内的实例数)的算法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可以发现任意形状的类。此类算法除了可以发现任意形状的类，还能够有效去除噪声。第十二页，共十六页，2022年，8月28日基于网格的聚类算法，把空间量化为有限个单元(即长方体或超长方体)，然后对量化后的空间进行聚类。此类算法具有很快的处理速度。缺点是只能发现边界是水平或垂直的聚类，而不能检测到斜边界。此类算法具有很快的处理速度。时间复杂度一般由网格单元的数目决定，而与数据集的大小无关。此外，聚类的精度取决于网格单元的大小。此类算法不适用于高维情况，因为网格单元的数目随着维数的增加而呈指数增长。所有基于网格的聚类算法都存在下列问题：一是如何选择合适的单元大小和数目；二是怎样对每个单元中对象的信息进行汇总。第十三页，共十六页，2022年，8月28日5.聚类算法的用途与发展聚类分析是数据挖掘中一种非常有用的技术，它可作为特征和分类算法的预处理步骤，这些算法再在生成的簇上进行处理，也可将聚类结果用于进一步关联分析。还可以作为一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇做进一步分析。其应用范围涉及商务，生物，地理，web文档分类，仿真等诸多领域。例如在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯，然后指导自身的工作制造出更好的产品，制定出更高效的营销策略和模式。第十四页，共十六页，2022年，8月28日聚类能更好地应用到现实生活中是很必要的。这些新算法正努力把静态的聚类推向动态的