聚类分析是将数据对象集合分组为由相似对象构成的多个类的分析过程。
基本概念聚类(Clustering )是一种寻找数据之间内在结构的技术。 集群将整个数据实例组织成若干相似组,这些相似组称为集群。 位于同一个集群上的数据实例彼此相同,而位于不同集群上的实例彼此不同。
集群技术通常也称为无监视学习,与监视学习不同,集群中没有表示数据类别的分类和组信息。
数据之间的相似性可以通过定义距离或相似性系数来确定。 图1示出了基于数据对象之间的距离进行聚类的例子,其中距离近的数据对象被划分成一个集群。
图1聚类分析示意图
聚类分析可以应用于数据预处理过程中,可以通过聚类分析的方法对结构复杂的多维数据进行数据收集,使结构复杂的数据标准化。
群集分析还可以用于发现数据项之间的依赖关系,并删除或集成具有密切依赖关系的数据项。 聚类分析还可以为某些数据挖掘方法(如关联规则、粗糙集方法等)提供预处理功能。
在企业中,集群分析是细分市场的有效工具,用于发现不同的客户群,并通过刻画不同客户群的特征,研究消费者行为,寻找新的潜在市场。
在生物上,聚类分析用于将动植物和基因分类,获得对种群固有结构的认识。
在保险业,聚类分析可以通过平均消费来鉴定汽车保险单的所有者群体,同时通过住宅类型、价值、地理位置来鉴定城市房地产群体。
在网络APP应用中,聚类分析被用于在互联网上进行文档分类。
在电子商务中,集群分析通过分组找出具有相似浏览行为的顾客,分析顾客的共同特征,帮助电子商务企业了解自己的顾客,为顾客提供更好的服务。
聚类分析方法的类别目前存在许多聚类算法,算法的选择取决于数据的类型、聚类的目的和具体应用。 聚类算法主要分为基于划分的聚类方法、基于层次的聚类方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法五种。
1 .基于划分的聚类方法
基于划分的聚类方法是自顶向下的方法,其中针对给定n个数据对象的数据集d,将数据对象组织成k(kn )个分区。 其中,每个分区表示一个集群。 图2是基于分段的聚类方法的图像。
图2层次聚类算法综述
在基于划分的聚类方法中,最典型的是k均值(k均值)算法和k中心(k均值) k均值(k-medoids )算法,许多算法都被这两种算法改进。
基于划分的聚类方法的优点是收敛速度快,缺点是聚类数目k可以被合理估计,初始中心的选择和噪声对聚类结果有很大的影响。
2 .基于层次的聚类方法
基于层次的聚类方法是指将给定的数据进行层次分解直到满足一定条件为止。 该算法按层次分解顺序分为自下而上法和自上而下法,即凝聚式层次聚类算法和分裂式层次聚类算法。
1 )自下而上法。
首先,每个数据对象都是一个群集,计算数据对象之间的距离,然后每次将最近的点合并到同一个群集中。 然后,计算集群和集群之间的距离,将最近的集群合并成一个大集群。 在一个簇合成或达到某个终止条件之前,不断合并。
聚类与聚类距离的计算方法有最短距离法、中间距离法、聚类平均法等。 其中,最短距离法将簇与簇的距离定义为簇与簇之间的数据对象的最短距离。 自下而上法的代表性算法是Agnes(agglomerativenesing )算法。
2 )自上而下法。
该方法最初所有个体都属于一个集群,然后逐渐被细分成小集群,直到每个数据对象在不同集群中或者到达一个终止条件。 自上而下法的代表性算法是动态分析(gld ws )算法。
基于层次的聚类算法的主要优点是距离和规则相似度容易定义,约束少,不需要预先确定聚类的个数,可以发现聚类的层次关系。 基于层次的聚类算法的主要缺点是计算复杂度太高,对奇异值也有很大的影响,算法很可能被成链聚类。
3 .基于密度的聚类方法
基于密度的聚类方法的主要目标是寻找被低密度区域分隔开的高密度区域。 与基于距离的聚类算法不同,基于距离的聚类算法的聚类结果是球形聚类,而基于密度的聚类算法可以发现任意形状的聚类。
基于密度的聚类方法从数据对象分布区域的密度着手。 如果指定类中的数据对象在指定范围内,则当数据对象的密度超过某个阈值时,群集将继续进行。
这个方法可以如图3所示通过连结密度大的区域来形成不同形状的集群,并且可以去除孤立点和噪声对集群质量的影响,从而发现任意形状的集群。
基于密度的聚类方法中最具代表性的是DBSAN算法、OPTICS算法和DENCLUE算法。 图2是基于分层的聚类算法的示意图,上面示出了AGNES算法的过程,下面示出了gldws算法的过程。 这两种方法都没有优劣之分,但实际使用时,根据数据的特点和所需集群的数量,考虑自下而上还是自上而下更快。
图3密度聚类算法约简
4 .基于网格的聚类方法
基于网格的聚类方法可以将空间量化为有限数目的单元,从而形成一个网格结构、所有聚类
都在网格上进行。基本思想就是将每个属性的可能值分割成许多相邻的区间,并创建网格单元的集合。每个对象落入一个网格单元,网格单元对应的属性空间包含该对象的值,如图 4 所示。
图 4 基于网格的聚类算法示意
基于网格的聚类方法的主要优点是处理速度快,其处理时间独立于数据对象数,而仅依赖于量化空间中的每一维的单元数。这类算法的缺点是只能发现边界是水平或垂直的簇,而不能检测到斜边界。另外,在处理高维数据时,网格单元的数目会随着属性维数的增长而成指数级增长。
5. 基于模型的聚类方法
基于模型的聚类方法是试图优化给定的数据和某些数学模型之间的适应性的。该方法给每一个簇假定了一个模型,然后寻找数据对给定模型的最佳拟合。假定的模型可能是代表数据对象在空间分布情况的密度函数或者其他函数。这种方法的基本原理就是假定目标数据集是由一系列潜在的概率分布所决定的。
图 5 对基于划分的聚类方法和基于模型的聚类方法进行了对比。左侧给出的结果是基于距离的聚类方法,核心原则就是将距离近的点聚在一起。右侧给出的基于概率分布模型的聚类方法,这里采用的概率分布模型是有一定弧度的椭圆。
图 5 中标出了两个实心的点,这两点的距离很近,在基于距离的聚类方法中,它们聚在一个簇中,但基于概率分布模型的聚类方法则将它们分在不同的簇中,这是为了满足特定的概率分布模型。
图 5 聚类方法对比示意
在基于模型的聚类方法中,簇的数目是基于标准的统计数字自动决定的,噪声或孤立点也是通过统计数字来分析的。基于模型的聚类方法试图优化给定的数据和某些数据模型之间的适应性。
推荐学习目录:54.聚类分析简介
55.k-means聚类算法