AL123 人文社科会员免费专区文学 2024-07-21

数据挖掘（第2版）_王朝霞主编_AZW3_MOBI_EPUB_PDF_电子书（无页码）_王朝霞主编

内容节选

5.1 聚类基本概念聚类是一种常见的数据分析方法，就是将对象集合分组成为由类似的对象组成的多个类或簇的过程。由聚类所生成的类是对象的集合，这些对象与同一个类中的对象彼此相似，与其他类中的对象相异。在许多应用中，可以将一个类中的数据对象作为一个整体来对待。下面给出聚类的数学描述。被研究的对象集为X，度量对象空间相似度的标准为s，聚类系统的输出是对对象的区分结果，即C={C1,C2,…,Ck}，其中Ci⊆X，i=1,2,…,k，且满足如下条件。（1）C1∪C2∪…∪Ck=X. （2）Ci∩Cj=∅,i,j=1,2,…,k,i≠ j. C中的成员C1,C2,…,Ck称为类或簇。由第一个条件可知，对象集X中的每个对象必定属于某一个类；由第二个条件可知，对象集X中的每个对象最多只属于一个类。每个类可以通过一些特征来描述，有如下几种表示方式。（1）通过类的中心或边界点表示一个类。（2）使用对象属性的逻辑表达式表示一个类。（3）使用聚类树中的节点表示一个类。聚类分析就是根据发现的数据对象的特征及其关系的信息，将数据对象分簇。簇内的相似性越大，簇间差别越大，聚类效果越好。虽然聚类也起到了分类的作用，但和大多数分类是有差别的。大多数分类都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别的标准，然后将各要素划归于各类别中。聚类分析是归纳的，不需要事先确定分类的准则来分析数据对象，不考虑已知的类标记。聚类分析方法取决于数据的类型、聚类的目的和应用。按照聚类分析方法的主要思路，聚类分析方法可以分为划分聚类方法、层次聚类方法、密度聚类方法、网格聚类方法、模型聚类方法[1]。（1）划分聚类方法。给定一个包含n个对象的数据集，划分聚类方法构建数据集的k个划分，每个划分表示一个簇，并且k≤n。划分聚类方法首先创建一个初始划分，然后采用一种迭代的重定位技术，尝试通过对象在划分间的移动来改进划分。也就是说，它将数据集划分为k个组，同时满足以下要求：每个组至少包括一个对象，并且每个对象必须属于且只属于一个组（硬划分）。属于该类的聚类算法有k-平均算法、k-模算法、k-原型算法、k-中心点算法、PAM算法、CLARA算法、CLARANS算法等。（2）层次聚类方法。划分聚类方法获得的是单级聚类，而层次聚类方法是将数据集分解成多级进行聚类，层的分解可以用树形图来表示。根据层次的分解方法，层次聚类方法可以分为凝聚层次聚类算法和分裂层次聚类算法。凝聚层次聚类算法也称为自底向上的聚类算法，一开始将每个对象作为单独的一簇，然后不断地合并相近的对象或簇，如AGNES算法属于此类。分裂层次聚类算法也称为自顶向下的聚类算法，一开始将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到每个对象在一个单独的簇中，或者达到算法终止条件，如DIANA算法属于此类。相对于划分聚类方法，层次聚类方法不需要指定聚类数目，在凝聚或者分裂的层次聚类方法中，用户可以定义希望得到的聚类数目作为一个约束条件。（3）密度聚类方法。绝大多数划分聚类方法基于对象之间的距离进行聚类，这样的方法只能发现球状的类，而在发现任意形状的类上遇到了困难。密度聚类方法的主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤噪声和孤立点数据，发现任意形状的类。属于该类的聚类方法有DBSCAN算法、OPTICS算法等。（4）网格聚类方法。网格聚类方法首先把对象空间划分成有限个单元的网状结构，所有的处理都是以单个单元为对象的。这种方法的主要优点是处理速度快，其处理时间独立于数据对象的数目，只与划分数据空间的单元数有关。属于该类的聚类算法有STING算法、Wave Cluster算法、CLIQUE算法等。（5）模型聚类方法。模型聚类方法为每个簇假定一个模型，然后寻找能够很好地满足这个模型的数据集。这种聚类方法经常基于这样的假定：数据集是由一系列的概率分布所决定的。模型聚类方法主要有两类：统计学模型聚类方法和神经网络模型聚类方法。基于聚类分析的数据挖掘在实践中已经取得了很好的效果，但由于要处理巨大的、复杂的数据集，对聚类分析方法也提出了特殊的挑战，根据应用类型的不同，数据挖掘对聚类分析方法的要求主要有以下9个方面。（1）可伸缩性。可伸缩性是指算法不论对小数据集还是对大数据集，都应是有效的。很多聚类算法在几百个小数据集合上稳健性很好，而对包含上万个数据对象的大规模数据库进行聚类时，将导致不同的偏差结果。因此，研究大容量可伸缩性高效聚类算法是数据挖掘必须面对的挑战。（2）处理不同类型属性的能力。聚类算法不仅要能处理数值型数......