簇与聚类：数据样本集的分组过程

简单起见，本小节先给出一些聚类相关的符号说明及定义：

符号说明4.1：数据样本记为X，它由d个属性值组成：X=（x1，x2，…，xd），其中xi表示样本中的各属性，d是样本空间的维数（或属性个数）。

符号说明4.2：数据样本集记为χ｛ X1，X2，…，Xn｝，第i个样本记为Xi=｛xi1，…，xid｝，许多情况下聚类的样本集看成是一个n×d（n个样本×d个属性）的数据矩阵：

定义4.1（簇，cluster）：数据样本集χ分成k个簇（1≤k≤n），每个簇Ci是相应数据样本的集合，相似样本在同一簇中，相异样本在不同簇中。Ci（i=1， …， k）是χ的子集，如下所示：

C1 ∪ C2 ∪ … ∪ Ck = χ且Ci∩Cj=φ， i≠j

常用以下特征描述一个簇Ci：

（1）簇的质心（centroid）^[1]：簇的质心是簇的“中间值”（middle），即样本的平均值，但并不一定是簇中的实际点。

令ni表示簇Ci中样本的数量，mi表示对应样本的均值，则簇Ci的质心由式4-1计算得出：

定义4.1（簇，cluster）：数据样本集χ分成k个簇（1≤k≤n），每个簇Ci是相应数据样本的集合，相似样本在同一簇中，相异样本在不同簇中。Ci（i=1， …， k）是χ的子集，如下所示：

C1 ∪ C2 ∪ … ∪ Ck = χ且Ci∩Cj=φ， i≠j

常用以下特征描述一个簇Ci：

（1）簇的质心（centroid）^[1]：簇的质心是簇的“中间值”（middle），即样本的平均值，但并不一定是簇中的实际点。

令ni表示簇Ci中样本的数量，mi表示对应样本的均值，则簇Ci的质心由式4-1计算得出：

（2）簇的半径（radius）：簇的半径是簇中任意一点到质心之间距离的均方差的平方根（average mean squared distance），见式4-2。

（2）簇的半径（radius）：簇的半径是簇中任意一点到质心之间距离的均方差的平方根（average mean squared distance），见式4-2。

定义4.2（聚类，clustering）：给定一数据样本集χ ｛X1 ， X2， … ， Xn｝，根据数据间的相似程度将数据集合分成k个簇：｛C1，C2，…，Ck｝，使得相似样本在同一个簇中，相异样本在不同簇中的过程称为聚类，即∪i=1 kCi=χ且Ci∩Cj=φ，i≠j。

聚类分析除了作为单独的数据归类技术外，还常常作为其他算法的预处理步骤，用于获得对数据分布和聚集特性的初步了解，以在此基础上进行其他数据挖掘操作（如分类器的构造等）。

实际应用中的数据集具有不同特点，在各类数据上聚类算法的聚类能力的要求也不相同，这也是聚类算法不断改进的推动力，如由经典的k-means算法到改进后的适合大数据量、能发现任意形状簇的OPTICS算法等。评价一个聚类算法的聚类分析能力主要有以下几个衡量标准：(www.xing528.com)

（1）能够适用于大数据量：有些聚类算法在小于200个数据对象的小数据集合上工作很好，但随着数据对象的增加，这些聚类算法的处理能力就会下降，因此一个好的聚类算法要求能够处理大的数据集合。

（2）能够处理不同类型数据：聚类作为一种分析技术，要求能够分析不同类型的数据，如区间标度型、序数型等，从而提供一个较普遍的模型。

（3）能够发现任意形状的簇：许多聚类算法采用欧氏距离来定义相似度，这种度量方式趋向于发现球状的簇，而现实中存在各种形状的簇，因此要求聚类算法能够发现任意形状的簇。

（4）能够处理高维数据：当前的数据集合具有各类不同属性，数据处于高维空间中，人们对三维以下的数据聚类情况能够较好地判别聚类结果的好坏，而在高维情况下，数据分布可能很稀疏且高度倾斜，所以聚类这样的数据对象是一个具有挑战性的课题。

（5）具有处理噪声的能力：有些聚类算S法对噪声是敏感的，将导致较差的结果。现实数据中不可避免地存在各类噪声，这些噪声的出现不应该对聚类产生较强的影响，这要求聚类算法具有处理噪声的能力。

（6）聚类结果的可解释性、可使用性：聚类为分析数据服务，人们期望通过聚类从数据中抽取出某种特定语义的解释，也就是聚类的结果应该是可解释的、可理解的和可用的。

以上六条标准是衡量一个聚类算法能力的几个主要指标，还有其他的衡量指标，如不依赖于预先的领域知识来确定输入参数、对数据顺序不敏感、处理快速等要求。

定义4.2（聚类，clustering）：给定一数据样本集χ ｛X1 ， X2， … ， Xn｝，根据数据间的相似程度将数据集合分成k个簇：｛C1，C2，…，Ck｝，使得相似样本在同一个簇中，相异样本在不同簇中的过程称为聚类，即∪i=1 kCi=χ且Ci∩Cj=φ，i≠j。

聚类分析除了作为单独的数据归类技术外，还常常作为其他算法的预处理步骤，用于获得对数据分布和聚集特性的初步了解，以在此基础上进行其他数据挖掘操作（如分类器的构造等）。

实际应用中的数据集具有不同特点，在各类数据上聚类算法的聚类能力的要求也不相同，这也是聚类算法不断改进的推动力，如由经典的k-means算法到改进后的适合大数据量、能发现任意形状簇的OPTICS算法等。评价一个聚类算法的聚类分析能力主要有以下几个衡量标准：

（1）能够适用于大数据量：有些聚类算法在小于200个数据对象的小数据集合上工作很好，但随着数据对象的增加，这些聚类算法的处理能力就会下降，因此一个好的聚类算法要求能够处理大的数据集合。

（2）能够处理不同类型数据：聚类作为一种分析技术，要求能够分析不同类型的数据，如区间标度型、序数型等，从而提供一个较普遍的模型。

（3）能够发现任意形状的簇：许多聚类算法采用欧氏距离来定义相似度，这种度量方式趋向于发现球状的簇，而现实中存在各种形状的簇，因此要求聚类算法能够发现任意形状的簇。

（4）能够处理高维数据：当前的数据集合具有各类不同属性，数据处于高维空间中，人们对三维以下的数据聚类情况能够较好地判别聚类结果的好坏，而在高维情况下，数据分布可能很稀疏且高度倾斜，所以聚类这样的数据对象是一个具有挑战性的课题。

（5）具有处理噪声的能力：有些聚类算S法对噪声是敏感的，将导致较差的结果。现实数据中不可避免地存在各类噪声，这些噪声的出现不应该对聚类产生较强的影响，这要求聚类算法具有处理噪声的能力。

（6）聚类结果的可解释性、可使用性：聚类为分析数据服务，人们期望通过聚类从数据中抽取出某种特定语义的解释，也就是聚类的结果应该是可解释的、可理解的和可用的。

以上六条标准是衡量一个聚类算法能力的几个主要指标，还有其他的衡量指标，如不依赖于预先的领域知识来确定输入参数、对数据顺序不敏感、处理快速等要求。