3.3.4 数据聚类和剖分
在数据可视化的过程中,有时会使用聚类算法将数据划分为不同的群组,从而能更好地看出不同群组中数据的不同变化趋势。聚类算法一般可分为基于层次的、基于划分的、基于密度的、基于网格的和基于模型的五种。
(1)基于层次的聚类算法
层次的聚类算法对给定数据对象进行层次上的分解。根据层次分解的顺序是自下向上的还是自上向下的,可分为凝聚算法(自下向上)和分裂算法(自上向下)。
①凝聚算法思想
初始的时候,每一个成员都是一个单独的簇,在以后的迭代过程中,再把那些相互临近的簇组成一个新簇,直到把所有的成员组成一个簇为止。其具体代表算法:单连接算法、全连接算法和平均连接算法。
单连接算法:该算法的主要思想是发现最大连通子图,如果至少存在一条连接两个簇的边,并且两点之间的最短距离小于或等于给定的阈值,则合并这两个簇。
全连接算法:该算法寻找的是一个团,而不是连通的分量,一个团是一个最大的图,其中任意两个顶点之间都存在一个条边。如果两个簇中的点之间的距离小于距离阈值,则合并这两个簇。
平均连接算法:如果在两个目标簇中,一个簇中的所有成员与另一个簇中的所有成员之间的平均距离小于距离阈值,则合并这两个簇。
②分裂算法思想
初始的时候,所有的数据成员都包含在一个簇中,是一个簇,然后将上层的簇重复地分裂为两个下层簇,直到每一个成员都组成一个单独的簇为止。代表算法:基于单连接算法MST。其分裂过程为:将最小生成树的边从最长到最短依次进行剪切。该算法将产生与凝聚方法完全相同的簇集,只是产生过程的次序完全相反。
层次聚类方法的前提条件是假设数据是一次性提供的,因此都不是增量算法。其缺陷在于,一旦一个步骤(合并或分裂)完成,它就不能被撤销,因而不能更正错误的决定。改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成,如BIRCH算法。
(2)基于划分的聚类算法
将一个有N个样本的数据库,分为K个划分(K≤N),每个划分表示一个簇,并同时满足以下两个条件的过程,称为划分算法。①每个簇至少包含一个样本;②每个样本必须属于且仅属于一个簇。其具体代表算法有:PAM(partitioning around medoids)算法、CLARA(clustering large applications)算法、CLARANS(clustering large applications based upon randomized search)算法等。
①PAM算法
该算法也称作K-中心点算法,是指用中心点来代表一个簇。利用中心点这个概念能够很好地处理异常点。初始时,将N个成员中的K个随机成员设置为中心点集合,然后在每一步中,对输入数据集中目前还不是中心点的成员进行逐个检验,看是否可成为中心点。
该算法将判定是否存在一个成员,可以取代已存在的一个中心点。通过检验所有的中心点与非中心点组成的对,PAM算法将选择最能提高聚类效果的对。该方法的聚类效果的度量是簇中的非中心点到簇的中心点的所有距离之和。由于在每次迭代过程中需要确定出K(N-K)个交换对,在每个交换对中又要计算N-K个非中心点到簇的中心点距离之和的变化,故每次迭代的总的复杂度是O(K(N-K)2)。所以该算法的复杂性太高。但其算法逻辑较简单,适合小型的数据库。
②CLARA算法
通过数据库抽样,改进了PAM的时间复杂性。其基本思想是首先对数据库进行抽样,然后将利用PAM算法在抽样后的数据上进行聚类,得到的中心点就是整个数据库的中心点,最后将数据库中所有成员分配到离自身距离最近的中心点所代表的簇中。(https://www.daowen.com)
为了提高CLARA的精度,可以分别进行几组抽样,然后在每组抽样上都应用PAM算法,最后将最好的聚类结果作为最终的聚类结果。由于使用了抽样技术,对于大型数据库而言,CLARA比PAM更有效率,但其效果则取决于样本规模。有研究结果表明,样本规模为40+2K的数据库,进行5次抽样会得到较好的结果。
③CLARANS算法
CLARANS通过利用多次不同抽样来改进CLARA。除需要与PAM一样的输入外,CLARANS还需要输入maxneighbor和numlocal两个参数。maxneighbor表示一个节点可以与任意特定节点(邻居)进行比较的数目。随着maxneighbor的增长,CLARANS与PAM更加相近,这是由于所有节点都可能被检验。numlocal表示抽样次数。
由于在每个样本上都要进行新的聚类,所以numlocal也表示需要进行聚类的次数。研究结果表明当numlocal=2和maxneighbor=max((0.012 5*K(N-K)),250)时,聚类效果较好。对于任意规模的数据集,CLARANS比CLARA和PAM效率要高。
(3)基于密度的聚类算法
提出基于密度的聚类方法是为了发现任意形状的聚类结果。其主要思想是:只要临近区域的密度超过某个阈值,就继续聚类。这样的方法可以用来过滤“噪声”孤立点数据,发现任意形状的簇。其代表算法:DBSCAN(density-based spatial clustering with noise)。
DBSCAN算法可以将足够高密度的区域划分为簇,并可以在带有“噪声”的空间数据库中发现任意形状的聚类。该算法定义簇为密度相连的点的最大集合。
DBSCAN通过检查数据库中每个点的邻域来寻找聚类。如果一个点p的邻域中包含数据项的个数多于最小阀值,则创建一个以p作为核心对象的新簇。然后反复地寻找从这些核心对象直接密度可达的对象,当没有新的点可以被添加到任何簇时,该过程结束。不被包含在任何簇中的对象被认为是“噪声”。如果采用空间索引,DBSCAN的计算复杂度是O(nlogn),这里n是数据库中对象数目。否则,计算复杂度是O(n^2)。
DBSCAN算法具有很多优点:能够发现空间数据库中任意形状的密度连通集;在给定合适的参数条件下,能很好地处理噪声点;对用户领域知识要求较少;对数据的输入顺序不太敏感;适用于大型数据库。其缺点:DBSCAN算法要求事先指定领域和阈值;具体使用的参数依赖于应用的目的。
(4)基于网格的聚类算法
这种算法首先将数据空间划分成为有限个单元的网格结构,所有的处理都是以单个的单元为对象的。处理速度通常与目标数据库中记录的个数无关,它只与单元的个数有关,故这种算法的一个突出优点就是处理速度很快。其代表算法有:STING(statistical information grid based method)算法。
STING算法将空间区域划分为矩形单元。针对不同级别的分辨率,通常存在多个级别的矩形单元,这些单元形成了一个层次结构:高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易地从低层单元的计算得到。这些参数包括:属性无关的参数count;属性相关的参数m(平均值),s(标准偏差),min(最小值),max(最大值),以及该单元中属性值遵循的分布(distribution)类型。STING扫描数据库一次来计算单元的统计信息,因此产生聚类的时间复杂度是O(n),其中n是对象的数目。在层次结构建立后,查询处理时间是O(g),g是最低层风格单元的数目,通常远远小于n。
(5)基于模型的聚类算法
基于模型的方法为每个簇都假定了一个模型,并寻找数据对给定模型的最佳拟合。该算法通过构建反映数据点空间分布的密度函数来实现聚类。这种聚类方法试图优化给定的数据和某些数学模型之间的适应性。其代表算法有COBWEB算法。
COBWEB算法以一个分类树的形式创建层次聚类,它的输入对象用“分类属性”-“值”对来描述。其工作流程是:在给定一个新的对象后,COBWEB沿一条适当的路径向下,修改计数,以寻找可以分类该对象的最好节点。该判定基于将对象临时置于每个节点,并计算结果划分的分类效用。产生最高分类效用的位置应当是对象节点的一个好的选择。
给定一个新的对象,COBWEB沿一条适当的路径向下,修改计数,寻找可以分类该对象的最好节点。在该过程中,将对象临时置于每个节点上,并计算划分的分类效用结果。产生最高分类效用的位置是对象节点的一个好的选择。
COBWEB可以自动修正划分中类的数目;不需要用户提供输入参数。其缺点在于COBWEB基于这样一个假设:在每个属性上的概率分布是彼此独立的。但这个假设并不总是成立。分类树对于偏斜的输入数据不是高度平衡的,它可能导致时间和空间复杂性的剧烈变化。COBWEB不适用于聚类大型数据库的数据。
通过以上的分析可知,没有一种算法是十全十美的,需要根据实际情况(例如,发现聚类的形状,数据输入顺序是否敏感,适用数据库的大小或者算法效率)来选择聚类算法对数据进行划分。
