数据挖掘之聚类分析学习笔记(3)

主要聚类方法的分类

算法的选择取决于数据的类型， 聚类的目的和应用

大体上，主要的聚类算法可以划分为如下几类：

划分方法（partitioning methods）：给定一个n 个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚类，并且k<=n。也就是说，它将数据划分为k 个组，同时满足如下的要求：（1）每个组至少包含一个对象；（2）每个对象必须属于且只属于一个组。注意在某些模糊划分技术中第二个要求可以放宽。

给定k，即要构建的划分的数目，划分方法首先创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是：在同一个类中的对象之间的距离尽可能小，而不同类中的对象之间的距离尽可能大。

为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方法：（1）k-means 算法，在该算法中，每个簇用该簇中对象的平均值来表示。（2）k-medoids 算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。

层次的方法（hierarchical methods）：层次的方法对给定数据集合进行层次的分解。根据层次的分解。如何形成，层次的方法可以被分为凝聚的或分裂的方法。

凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后继续地合并相近的对象或组，直到所有的组合并为一个（层次的最上层），或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。

层次的方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较小。但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果：（1）在每层划分中，仔细分析对象间的联接，例如CURE 和Chameleon 中的做法。（2）综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。

基于密度的方法：绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法，其主要思想是：只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须包含至少某个数目的点。这样的方法可以用来过滤“噪音”数据，发现任意形状的簇。

DBSCAN 是一个有代表性的基于密度的方法，它根据一个密度阈值来控制簇的增长。OPTICS是另一个基于密度的方法，它为自动的，交互的聚类分析计算一个聚类顺序。

基于网格的方法（grid-based methods）：基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构（即量化的空间）上进行。

这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。STING 是基于网格方法的一个典型例子。CLIQUE 和WaveCluster 这两种算法既是基于网格的，又是基于密度的

基于模型的方法（model-based methods）：基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳匹配。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪音”数据和孤立点，从而产生健壮的聚类方法。

划分方法（partitioning methods）

给定一个包含n 个数据对象的数据库，以及要生成的簇的数目k，一个划分类的算法将数据对象组织为k 个划分（k≤n），其中每个划分代表一个簇。通常会采用一个划分准则（经常称为相似度函数，similarity function），例如距离，以便在同一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”。

算法：k-means。

输入：簇的数目k 和包含n 个对象的数据库。

输出：k 个簇，使平方误差最小。

方法：

（1） 任意选择k 个对象作为初始的簇中心；

（2） repeat

（3） 根据与每个中心的距离，将每个对象赋给“最近”的簇；

（4） 重新计算每个簇的平均值；

（5） until 不再发生变化

基于质心（centroid）的技术：k-Means 方法

k-means 算法以k 为参数，把n 个对象分为k 个簇，以使类内具有较高的相似度，而类间的相似度最低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。

“k-means 算法是怎样工作的？”k-means 算法的处理流程如下。首先，随机地选择k 个对象，每个对象初始地代表了一个簇中心。对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。

这个算法尝试找出使平方误差函数值最小的k 个划分。当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好。对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度是O（nkt），n 是所有对象的数目，k 是簇的数目，t 是迭代的次数。通常地，k<<n，且t<<n。这个算法经常以局部最优结束。

但是，k-means方法只有在簇的平均值被定义的情况下才能使用。这可能不适用于某些应用，例如涉及有分类属性的数据。要求用户必须事先给出k（要生成的簇的数目）可以算是该方法的一个缺点。K-means方法不适合于发现非凸面形状的簇，或者大小差别很大的簇。而且，它对于“噪音”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。

“k-medoids 算法在大数据集合上的效率如何？”典型的k-medoids 算法，如PAM，对小的数据集合非常有效，但对大的数据集合没有良好的可伸缩性。为了处理较大的数据集合，可以采用一个基于样本的方法CLARA（Clustering LARge Applications）。

CLARA 的主要思想是：不考虑整个数据集合，选择实际数据的一小部分作为数据的样本。然后用PAM 方法从样本中选择代表对象。如果样本是以非常随机的方式选取的，它应当足以代表原来的数据集合。从中选出的代表对象很可能与从整个数据集合中选出的非常近似。CLARA 抽取数据集合的多个样本，对每个样本应用PAM 算法，返回最好的聚类结果作为输出。

层次方法

一个层次的聚类方法将数据对象组成一棵聚类的树。根据层次分解是自底向上，还是自顶向下形成，层次的聚类方法可以进一步分为凝聚（agglomerative）和分裂(divisive)层次聚类。一个纯粹的层次聚类方法的聚类质量受限于如下特点：一旦一个合并或分裂被执行，就不能修正。最近的研究集中于凝聚层次聚类和迭代重定位方法的集成。

一般来说，有两种类型的层次聚类方法：

凝聚的层次聚类：这种自底向上的策略首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类方法属于这一类，它们只是在簇间相似度的定义上有所不同。

分裂的层次聚类：这种自顶向下的策略与凝聚的层次聚类不同，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件，例如达到了某个希望的簇数目，或者两个最近的簇之间的距离超过了某个阈值。

在凝聚或者分裂的层次聚类方法中，用户能定义希望得到的簇数目作为一个结束条件。

四个广泛采用的簇间距离度量方法如下：

最小距离：dmin(Ci,Cj) = min p∈Ci,p’∈Cj |p-p’|

最大距离：dmax(Ci,Cj) = max p∈Ci,p’∈Cj |p-p’|

平均值的距离：dmean(Ci,Cj) = | mI - mj |

平均距离：davg(Ci,Cj) =Σ p∈Ci Σp’∈Cj |p-p’|

这里|p-p’|是两个对象p 和p’之间的距离，mI 是簇Ci 的平均值，而nI 是簇Cj 中对象的数目。

基于密度的方法

为了发现任意形状的聚类结果，提出了基于密度的聚类方法。这类方法将簇看作是数据空间中由低密度区域分割开的高密度对象区域。

DBSCAN:一个基于密度和高密度的连结区域的聚类算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个基于密度的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以在带有“噪音”的空间数据库中发现任意形状的聚类。它定义簇为密度相连的点的最大集合。

基于密度的聚类的基本想法涉及一些新的定义。我们先给出这些定义，然后用一个例子加以说明。

n 一个给定对象周围半径e内的区域称为该对象的e –邻域。

n 如果一个对象的e–邻域至少包含最小数目MinPts 的对象，那么该对象称为核心对象。

n 给定一个对象集合D，如果p 是在q 的e–邻域内，而q 是一个核心对象，我们说对象p 从对象q 出发是直接密度可达的，。

n 如果存在一个对象链p1,p2,…,pn，p1=q， pn=p，对pi∈ D，1≤i≤n，pi+1 是从pi 关于e和 MinPts直接密度可达的，则对象p 是从对象q 关于e和MinPts 密度可达的(density-reachable)。

n 如果对象集合D 中存在一个对象o，使得对象p 和q 是从o 关于e和MinPts 密度可达的，那么对象p 和q 是关于e和MinPts 密度相连的（density-connected）。

密度可达性是直接密度可达性的传递闭包，这种关系是非对称的。只有核心对象之间是相互密度可达的。不过，密度相连性是一个对称的关系。

基于网格的方法

基于网格的聚类方法采用一个多分辨率的网格数据结构。它将空间量化为有限数目的单元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。这种方法的主要优点是处理速度快，其处理时间独立于数据对象的数目，仅依赖于量化空间中每一维上的单元数目。

基于网格方法的有代表性的例子包括STING，它利用了存储在网格单元中的统计信息；

WaveCluster，它用一种小波转换方法来聚类对象；CLIQUE，它是在高维数据空间中基于网格和密度的聚类方法。

STING：统计信息网格(STatistical INformation Grid)

STING 是一个基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值，最大值，和最小值）被预先计算和存储。这些统计变量可以方便下面描述的查询处理使用。

“这些统计信息怎样用于回答查询？”统计变量的使用可以以自顶向下的基于网格的方法。首先，在层次结构中选定一层作为查询处理的开始点。通常，该层包含少量的单元。对当前层次的每个单元，我们计算置信度区间（或者估算其概率），用以反映该单元与给定查询的关联程度。不相关的单元就不再考虑。低一层的处理就只检查剩余的相关单元。这个处理过程反复进行，直到达到最底层。此时，如果查询要求被满足，那么返回相关单元的区域。否则，检索和进一步的处理落在相关单元中的数据，直到它们满足查询要求。

“与其它聚类算法相比，STING 有什么优点？”STING 有几个优点：（1）由于存储在每个单元中的统计信息描述了单元中数据的与查询无关的概要信息，所以基于网格的计算是独立于查询的；

（2）网格结构有利于并行处理和增量更新；（3）该方法的效率很高：STING 扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O（n），n 是对象的数目。在层次结构建立后，查询处理时间是O（g），这里g 是最底层网格单元的数目，通常远远小于n。

WaveCluster：采用小波变换聚类

WaveCluster 是一种多分辨率的聚类算法，它首先通过在数据空间上强加一个多维网格结构来汇总数据，然后采用一种小波变换来变换原始的特征空间，在变换后的空间中找到密集区域。

在该方法中，每个网格单元汇总了一组映射到该单元中的点的信息。这种汇总信息适合于在内存中进行多分辨率小波变换使用，以及随后的聚类分析。

“什么是小波变换？”小波变换是一种信号处理技术，它将一个信号分解为不同频率的子波段。

通过应用一维小波变换n 次，小波模型可以应用于n 维信号。在进行小波变换时，数据被变换以在不同的分辨率层次保留对象间的相对距离。这使得数据的自然聚类变得更加容易区别。通过在新的空间中寻找高密度区域，可以确定聚类。

“为什么小波变换对聚类是有用的？”它主要有如下的优点：

它提供了没有监控的聚类。它采用了hat-shape 过滤，强调点密集的区域，而忽视在密集区域外的较弱的信息。这样，在原始特征空间中的密集区域成为了附近点的吸引点（attractor），距离较远的点成为抑制点（inhibitor）。这意味着数据的聚类自动地显示出来，并“清理”了周围的区域。这样，小波变换的的另一个优点是能够自动地排除孤立点。