2.3　数据聚类性

数据聚类是指根据数据的内在性质将数据分成一些聚合类，每一聚合类中的元素尽可能具有相同的特性，不同聚合类之间的特性差别尽可能大。

聚类分析的目的是分析数据是否属于各个独立的分组，使一组中的成员彼此相似，而与其他组中的成员不同。它对一个数据对象的集合进行分析，但与分类分析不同的是，所划分的类是未知的，因此聚类分析也称为无指导或无监督（Unsupervised）学习。聚类分析的一般方法是将数据对象分组为多个类或簇（Cluster），在同一簇中的对象之间具有较高的相似度，而不同簇中的对象差异较大。由于聚类分析的上述特征，在许多应用中，对数据集进行了聚类分析后可将一个簇中的各数据对象作为一个整体对待。

数据聚类（Cluster Analysis）是对于静态数据分析的一门技术，在许多领域受到广泛应用，包括机器学习、数据挖掘、模式识别、图像分析以及生物信息。

1．聚类应用

随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，积累了大量的数据，而这些激增的数据后面隐藏着许多重要的信息，因此人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效、方便地实现数据的录入、查询、统计等功能，但是无法发现数据中存在的各种关系和规则，更无法根据现有的数据预测未来的发展趋势。数据聚类分析正是解决这一问题的有效途径，它是数据挖掘的重要组成部分，用于发现在数据库中未知的对象类，为数据挖掘提供有力的支持，它是近年来广为研究的问题之一。聚类分析是一个极富挑战性的研究领域，采用基于聚类分析方法的数据挖掘在实践中取得了较好的效果。聚类分析也可以作为其他一些算法的预处理步骤，聚类可以作为一个独立的工具来获知数据的分布情况，使数据形成簇，其他算法再针对生成的簇进行处理，聚类算法既可作为特征和分类算法的预处理步骤，也可将聚类结果用于进一步关联分析。迄今为止，人们提出了许多聚类算法，所有这些算法都试图解决大规模数据的聚类问题。聚类分析还成功地应用在了模式识别、图像处理、计算机视觉、模糊控制等领域，并在这些领域中取得了长足的发展。

2．数据聚类

聚类就是将一个数据单位的集合分割成几个称为簇或类别的子集，每个类中的数据都有相似性，它的划分依据就是“物以类聚”。数据聚类分析是根据事物本身的特性，研究对被聚类的对象进行类别划分的方法。聚类分析依据的原则是使同一聚簇中的对象具有尽可能大的相似性，而不同聚簇中的对象具有尽可能大的相异性，聚类分析主要解决的问题就是如何在没有先验知识的前提下，实现满足这种要求的聚簇的聚合。聚类分析称为无监督学习（Unsupervised Study），主要体现是聚类学习的数据对象没有类别标注，需要由聚类学习算法自动计算。

3．聚类类型

经过持续了半个多世纪的深入研究聚类算法，聚类技术已经成为最常用的数据分析技术之一。各种算法的提出、发展、演化使聚类算法家族不断壮大。下面就针对目前数据分析和数据挖掘业界主流的认知对聚类算法进行介绍。

（1）划分方法

给定具有n个对象的数据集，采用划分方法对数据集进行k个划分，每个划分（每个组）代表一个簇。其中，k≤n，并且每个簇至少包含一个对象，而且每个对象一般只能属于一个组。对于给定的k值，一般要做一个初始划分，然后采取迭代重新定位技术，通过让对象在不同组间移动来改进划分的准确度和精度。一个好的划分原则是：同一个簇中对象之间的相似性很高（或距离很近），而不同簇的对象之间相异度很高（或距离很远）。

① K-Means算法：又叫K均值算法，是目前最著名、使用最广泛的聚类算法。在给定一个数据集和需要划分的数目k后，该算法可以根据某个距离函数反复把数据划分到k个簇中，直到收敛为止。K-Means算法用簇中对象的平均值来表示划分的每个簇，其大致的步骤是：首先将随机抽取的k个数据点作为初始的聚类中心（种子中心），然后计算每个数据点到每个种子中心的距离，并把每个数据点分配到距离它最近的种子中心；一旦所有的数据点都被分配完成，每个聚类的聚类中心（种子中心）就按照本聚类（本簇）的现有数据点重新计算；这个过程不断重复，直到收敛，即满足某个终止条件为止。最常见的终止条件是误差平方和SSE（指令集的简称）局部最小。

② K-Medoids算法：又叫K中心点算法，用最接近簇中心的一个对象来表示划分的每个簇。K-Medoids算法与K-Means算法的划分过程相似，两者最大的区别是：K-Medoids算法是用簇中最靠近中心点的一个真实的数据对象来代表该簇，而K-Means算法是用计算出来的簇中对象的平均值（这个平均值是虚拟的，并没有一个真实的数据对象具有这个平均值）来代表该簇。

（2）层次方法

在给定n个对象的数据集后，可用层次方法（Hierarchical Methods）对数据集进行层次分解，直到满足某种收敛条件为止。按照层次分解的形式不同，层次方法又可以分为凝聚层次聚类和分裂层次聚类。

①凝聚层次聚类：又叫自底向上方法，一开始将每个对象作为单独的一类，然后相继合并与其相近的对象或类，直到所有小的类别合并成一个类，即层次的最上面，或者达到一个收敛，即终止条件为止。

②分裂层次聚类：又叫自顶向下方法，一开始将所有对象置于一个簇中，在迭代的每一步中类会被分裂成更小的类，直到最终每个对象在一个单独的类中，或者满足一个收敛，即终止条件为止。

（3）基于密度的方法

传统的聚类算法都是基于对象之间的距离（距离作为相似性的描述指标）进行聚类划分，但是这些基于距离的方法只能发现球状类型的数据，对于非球状类型的数据来说只根据距离来描述和判断是不够的。鉴于此，人们提出了一个密度的概念——基于密度的方法（Density-Based Methods），其原理是：只要邻近区域内的密度（对象的数量）超过了某个阈值，就继续聚类。换言之，给定某个簇中的每个数据点（数据对象），在一定范围内必须包含一定数量的其他对象。该算法从数据对象的分布密度出发，把密度足够大的区域连接在一起，因此可以发现任意形状的类。该算法还可以过滤噪声数据（异常值）。基于密度的方法的典型算法包括DBSCAN（Density-Based Spatial Clustering of Application with Noise，具有噪声的基于密度的空间聚类应用算法）以及其扩展算法OPTICS（Ordering Points to Identify the Clustering Structure，即通过点排序识别聚类结构的密度聚类算法）。其中，DBSCAN算法会根据一个密度阈值来控制簇的增长，将具有足够高密度的区域划分为类，并可在带有噪声的空间数据库里发现任意形状的聚类。尽管此算法优势明显，但是其最大的缺点是需要用户确定输入参数，而且对参数十分敏感。

（4）基于网格的方法

基于网格的方法（Grid-Based Methods）将把对象空间量化为有限数目的单元，这些单元再形成网格结构，让所有的聚类操作都在这个网格结构中进行。该算法的优点是处理速度快，其处理时间常常独立于数据对象的数目，只跟量化空间中每一维的单元数目有关。基于网格方法的典型算法是STING（统计信息网格方法，Statistical Information Grid）算法。该算法是一种基于网格的多分辨率聚类技术，将空间区域划分为不同分辨率级别的矩形单元，并形成一个层次结构，且高层的低分辨率单元会被划分为多个低一层次的较高分辨率单元。这种算法从最底层的网格开始逐渐向上计算网格内数据的统计信息并储存。网格建立完成后，就用类似DBSCAN的方法对网格进行聚类。

4．数据聚类需解决的问题

在聚类分析的研究中，有许多急待进一步解决的问题，比如：处理数据为大数据量、具有复杂数据类型的数据集合时，聚类分析结果的精确性问题；对高属性维数据的处理能力；数据对象分布形状不规则时的处理能力；处理噪声数据的能力，能够处理数据中包含的孤立点，未知数据、空缺或者错误的数据；对数据输入顺序的独立性，也就是对于任意的数据输入顺序产生相同的聚类结果；减少对先决知识或参数的依赖型……这些问题的存在使得我们研究高正确率、低复杂度、I /O开销小、适合高维数据、具有高度可伸缩性的聚类方法迫在眉睫，这也是今后聚类方法研究的方向。

5．数据聚类应用

聚类分析可以作为一个独立的工具来获得数据的分布情况，通过观察每个簇的特点，集中对特定的某些簇做进一步分析，以获得需要的信息。聚类分析应用广泛，除了在数据挖掘、模式识别、图像处理、计算机视觉、模糊控制等领域的应用，还被应用在气象分析、食品检验、生物种群划分、市场细分、业绩评估等诸多方面。例如，在商务上，聚类分析可以帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群特征。聚类分析还可以应用在欺诈探测中，聚类中的孤立点就可能预示着欺诈行为的存在。聚类分析的发展过程也是聚类分析的应用过程，目前聚类分析在相关领域已经取得丰硕的成果。