作为数据挖掘的重要工具，聚类分析已经得到了广泛关注。近年来，随着信息技术的迅猛发展，具有不同结构特点的数据不断涌现，为聚类分析的研究提出了新的挑战。尽管如此，聚类分析研究中的基本问题始终是人们研究工作的重点内容，其有效解决对于数据挖掘、模式识别中的许多问题都具有重要的借鉴意义。这些基本问题包括：①对于不同结构特征的数据，如何合理计算数据点之间的相异或相似程度；②对于包含噪声或例外点的数据，如何提高算法的健壮性；③对于高维数据，如何进行特征降维；④对于包含多个类簇的数据，如何确定数据集包含的聚类数目；⑤对于大规模数据集，如何进行高效的聚类。本节将在前人工作的基础上对解决这些问题的常用方法进行论述。

5.1.5.1　如何合理计算数据点之间的相异或相似程度

如何衡量数据点之间的相异或相似程度是设计聚类算法的基础问题，其会直接影响聚类分析的效果，最直观的方法是使用距离函数或相似性函数。通常而言，数据集上的距离函数应该满足对称性和非负性，如果它还满足三角不等式和自反性，则该距离函数就是一个度量，数据集上的相似性函数也有类似的性质。

5.1.5.2　如何提高聚类算法对噪声、例外点的健壮性

噪声和例外点在各种类型的数据集中普遍存在。为了减少聚类过程中噪声、例外点对正常数据的影响，提高聚类算法的抗噪性能具有重要意义。在聚类过程中，使用对噪声鲁棒的距离度量来计算数据点之间的距离成为提高算法健壮性的另一种方法。

5.1.5.3　如何对高维数据进行聚类

许多聚类算法对高维数据显得无能为力，这是因为在高维空间中，传统的距离函数会出现不稳定现象，数据点之间的距离变得几乎相等。在实际应用中，文本数据、基因数据、时间序列、基因表达数据、生物特征数据等都是典型的高维数据，如何对这些高维数据进行有效的聚类成为当前研究的热点和难点。

（1）特征约简技术

为了对高维数据进行聚类，通常可以先进行特征约简，将高维特征空间中的数据转换到低维特征空间，然后使用K－Means等传统的聚类算法在低维特征空间中进行聚类。特征约简技术可分为特征选择和特征提取两种策略，前者是指从一组特征中选取一些最有代表性的特征以达到降低特征空间维数的目的，后者是指将高维空间中的数据通过线性或非线性变换映射到低维空间中。特征约简技术可以有效降低计算开销，并且使用户对感兴趣的数据有更清晰的理解。但是，在特征约简过程中会不可避免地发生信息损失，从而使聚类结果产生失真。

（2）特征加权技术(www.daowen.com)

对于高维数据而言，每个特征在聚类过程中所起的作用是不同的，部分特征在聚类过程中起了主导作用，它们对簇的形成起到积极作用，而另一部分特征在聚类过程中起的作用通常不大，有时甚至会引入噪声而为簇的生成带来负面影响。以此为出发点，对特征进行加权成为处理高维数据的有效方法，这相当于在欧氏空间中拉长或缩短不同特征所对应的轴。此外，对于高维数据，为每一维特征指定权重在实际应用中也不尽可行。这些方法的共同点在于，先通过学习算法对特征权重进行学习，在此基础上形成特征加权的距离函数。近年来，自动特征加权技术得到了充分研究，这类方法将特征权重的学习融合在聚类分析的过程中。

（3）子空间聚类技术

在高维空间中，属于不同类簇的样本点通常分布在由不同特征子集构成的子空间中。子空间聚类技术就是针对类簇的这一分布特点而设计的聚类方法。根据各个特征对于不同类簇的从属关系，子空间聚类算法可以分为硬子空间聚类和软子空间聚类两大类。在硬子空间聚类中，数据集不同的特征子集张成不同的子空间，硬子空间聚类则在这些不同的子空间中搜索类簇。对于硬子空间聚类而言，某个特征或者属于某个类簇，或者不属于某个类簇。与数据集“硬划分”概念不同的是，一个特征可以同时从属于多个类簇。研究表明，硬子空间聚类算法能够成功地发现高维数据集不同子空间中任意形状的类簇，但它们对参数的选取比较敏感，如何合理地选取参数仍是进一步需要研究的问题。在特征子集的选择上引入模糊概念，学术界提出了“软子空间”的概念。相应地，软子空间聚类技术也成为近年来的研究热点，其基本思想是，数据集中的各类别赋予不同的特征权重向量，以此来表示聚类过程中各维特征对此类别贡献的大小。在聚类过程中，每一维特征对于各个类别都有不同的贡献，因此每一类都有不同的特征权重向量，从而在整个特征空间中形成了若干个“软子空间”，聚类过程就是在各个“软子空间”中进行的。

5.1.5.4　如何确定数据集包含的聚类数目

聚类过程将数据集划分为若干个子集，虽然在某些情况下，用户根据自身经验可以为数据集选择较为合理的聚类数目，但大多数情况下，数据集包含的聚类数目对用户而言是未知的。许多聚类算法将聚类数目作为一个需要预先设定的输入参数，对这类聚类算法而言，聚类结果的质量与此参数的设置密切相关。如果用户设置的聚类数目过大，则会使聚类结果过于复杂而难以解释；相反，如果数目过少，则聚类结果中会丢失许多有价值的信息。可见，为数据集确定合理的聚类数目，无论对实际应用还是对聚类算法的有效运行都具有十分重要的意义。

估计聚类数目最简单的方法是将数据可视化。对于可以有效地投影到二维欧氏空间中的数据集而言，通过数据点在二维空间中的分布图可以直观地获取数据集包含的聚类数目信息。但是，对于高维数据和结构复杂的数据而言，这种方法往往不适用。

5.1.5.5　如何对大规模数据进行高效聚类

近年来，大规模数据集在各领域的频繁出现对聚类分析研究提出了新的挑战。对大规模数据集进行聚类分析通常从两方面进行考虑：一方面，开发算法复杂度较低的算法，通常认为，当算法的时间与空间复杂度与数据集大小接近线性关系时，该算法适合于处理大规模数据集；另一方面对原数据集进行采样或压缩，在不影响聚类效果的前提下得到原数据集的子集。