1 什么是聚类
聚类(clustering) 就是将具体或抽象对象的集合分成由相似对象组成的多个类或者簇的过程。
由聚类生成的簇是一组数据对象的集合,簇必须同时满足两个条件。第一个条件是每个簇至少包含一个数据对象;另外一个条件就是每个数据对象必须属于且唯一地属于一个簇。
聚类的用途是很广泛的。在商业上,聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来,并且概括出每一类消费者的消费模式或者说习惯。
2 聚类过程
聚类是将数据对象分类到不同的类或者簇的一个过程,所以同一个簇中的对象有很大的相似性,而不同簇间的对象有很大的相异性。
从机器学习的角度讲,聚类是搜索簇的无监督学习过程。与分类不同,无监督学习不依赖预先定义的类或带类标记的训练实例,需要由聚类学习算法自动确定标记,而分类学习的实例或数据对象有类别标记。聚类是观察式学习,而不是示例式的学习。
聚类分析是一种探索性的分类,在分类的过程中,人们不必事先给出一个分类的标准,聚类分析能够从样本数据出发,自动进行分类。聚类分析所使用方法的不同,常常会得到不同的结论。不同研究者对同一组数据进行聚类分析,所得到的聚类数也未必一致。
从实际应用的角度看,聚类分析是数据挖掘的主要任务之一。而且聚类能够作为一种独立的工具获得数据的分布状况,观察每一簇数据的特征,集中对特定的聚簇集合作进一步分析。聚类分析还可以作为其他算法(如分类和定性归纳算法)的预处理步骤。
1)聚类步骤
聚类一般包括以下几个主要过程或步骤。
①数据预处理:包括选择数据数量、类型、特征标度、移除孤立点、降维等。特征标度主要包括特征选择和特征抽取。特征选择就是选择数据的重要特征;特征抽取就是把输入的特征转化为一个新的显著特征。
②定义距离函数:聚类过程中,不同数据在同一个特征空间中的相似度衡量就非常重要,距离计算是最为常见的相似度度量方法,定义合适特征类型的距离函数是聚类的关键之一。
③聚类或分组:用距离函数对数据对象进行相似度度量,根据度量结果将数据对象分到不同的类中。
④评估输出:评估聚类结果的质量。通过类有效索引来评估,一般来说,几何性质(包括类间的分离和类内部的耦合)都是用来评价聚类结果的质量。类有效索引在决定类的数目时,经常扮演着重要角色。一个通常的决定类数目的方法,就是选择一个特定的类有效索引的最佳值,这个索引能否真实得出类的数目是判断该索引是否有效的标准。
2)聚类算法分类
聚类算法种类繁多,具体的算法选择取决于数据类型、聚类的应用和目的等。常用的聚类算法大致可以分为:划分聚类、层次聚类、密度聚类、网格聚类、模型聚类等几大类型,在实际应用中的有效聚类算法,往往是多种聚类算法的整合。
(1)基于划分的聚类算法
给定一个有 N 个元组或者记录的数据集,划分法将构造 K 个分组,每一个分组就代表一个聚类, K < N 。
特点:计算量大,很适合发现中小规模的数据库中的球状簇。
典型算法:K—means算法、K—Medoids算法、Clarans算法等。
(2)基于层次的聚类算法
对给定的数据集进行层次式的分解,直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。
特点:较小的计算开销,但不能更正错误的决定。
典型算法:Birch算法、Cure算法、Chameleon算法等。
(3)基于密度的聚类算法
只要一个区域中的点的密度超过某个阈值,就把它加到与之相近的聚类中去。
特点:能克服基于划分的算法只能发现“类圆形”聚类的缺点。
典型算法:Dbscan算法、Opiics算法、Denclue算法等。
(4)基于网格的聚类算法
将数据空间划分成有限个单元(cell)的网格结构,所有的处理都是以单个的单元为对象。
特点:处理速度很快,通常与目标数据库中记录的个数无关,只与把数据空间分为多少个单元有关。
典型算法:STING算法、CLIQUE算法、WaveCluste算法等。
(5)基于模型的聚类算法
为每个聚类假定了一个模型,寻找数据对给定模型的最佳拟合。这样一个模型可能是数据点在空间中的密度分布函数或者其他函数。
特点:这类算法试图优化给定的数据和某些数学模型之间的适应性,通常会假设“数据是根据潜在的概率分布生成的”。
典型算法:K—means算法、EM算法、COBWEB算法、SOM算法等。
3)聚类要求
聚类算法一般有以下要求:
(1)可伸缩性
许多聚类算法在小于200个数据对象的小数据集合上工作得很好。但是,一个大规模数据库可能包含几百万个对象,在这样的大数据集合样本上进行聚类可能会导致有偏的结果。这时就需要具有高度可伸缩性的聚类算法。
(2)不同属性
许多算法被设计用来聚类数值类型的数据。但是,应用可能要求聚类其他类型的数据,如二元类型(binary)、分类/标称类型(categorical/nominal)、序数型(ordinal)数据,或者这些数据类型的混合。这时就要求聚类算法具有处理不同类型属性的能力。
(3)任意形状
许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是,一个簇可能是任意形状的,这时就需要能发现任意形状簇的聚类算法。
(4)领域最小化
许多聚类算法在聚类分析中要求用户输入一定的参数,例如希望产生的簇数目。聚类结果对于输入参数十分敏感。然而,参数通常很难确定,特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担,也使得聚类的质量难以控制。这时就要求聚类算法需要用户输入的参数最少。
(5)处理噪声
绝大多数现实中的数据库都包含了孤立点、缺失或者错误的数据。一些聚类算法对于这样的数据敏感,可能导致低质量的聚类结果。这就要求聚类算法具有处理噪声数据的能力。
(6)记录顺序
一些聚类算法对于输入数据的顺序是敏感的。例如,同一个数据集合,当以不同的顺序提交给同一个算法时,可能生成差别很大的聚类结果。这时,开发对数据输入顺序不敏感的算法具有重要的意义。
(7)高维度
一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理低维的数据,可能只涉及两到三维。人类的眼睛在最多三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的,特别是考虑到这样的数据可能分布非常稀疏,而且高度偏斜。设计对高维空间中的数据对象(特别是对高维空间稀疏和怪异分布的数据对象)能进行较好聚类分析的聚类算法已经成为聚类研究中的一项挑战。
(8)基于约束
现实世界的应用可能需要在各种约束条件下进行聚类。假设你的工作是在一个城市中为给定数目的自动提款机选择安放位置。为了作出决定,你可以对住宅区进行聚类,同时考虑如城市的河流和公路网,每个地区的客户要求等情况。要找到既满足特定的约束,又具有良好聚类特性的数据分组是一项具有挑战性的任务。
(9)解释性和可用性
用户希望聚类结果是可解释的、可理解的和可用的。也就是说,聚类可能需要和特定的语义解释和应用相联系。应用目标如何影响聚类方法的选择也是一个重要的研究课题。