相似度量和聚类原理

聚类分析是将一个数据对象的集合划分成若干个簇的过程，使得每个簇中的数据对象之间尽可能的相似，但与其他簇的对象尽可能的不相似。同一个簇中的样本比来自不同簇的样本更为相似的判断问题主要涉及以下两个子问题：

（1）如何度量样本之间的相似性。

（2）如何衡量对样本集划分的好坏。

1）相似性度量

相似度用于判断两个样本之间的差异程度，它是定义一个簇的基础，聚类分析过程的质量取决于对相似度度量标准的选择。常常使用“距离”来描述数据之间的相似程度。

定义4.3（样本间距离，distance） ： Xi ｛ xi1 ， … ， xid ｝和Xj ｛xj1 ， …， xjd｝是两个具有d个属性的样本，d（Xi， Xj）表示第i个样本与第j个样本间的距离，满足条件：

（1）非负性：对所有的xi和xj，恒有（Xi， Xj）≥0。同时，当且仅当两个样本的d个属性值对应相等时，等式才成立。

（2）对称性：对所有的xi和xj，恒有d（Xi， Xj）=d（Xj， Xi）。

满足三角不等式：即对所有的i， j， k，恒有

d（Xi， Xj）≤d（Xii， Xk）+d（Xk， Xj）

显然，两个样本间的距离在0→∞时，距离越小，两个样本越接近。当第i个和第j个样本相似时，距离d（Xi， Xj）最小；当第i个和第j个不相似时，则d（Xi， Xj）较大。

定义4.4（相似度，similarity）：相似度表示两个样本之间的相似程度或相近程度。常常用样本间的距离表示相似度，记为sim（Xi， Xj）：

sim（Xi， Xj）=d（Xi， Xj），其中d（Xi， Xj）表示Xi和Xj之间的距离，不难看出距离越小，两个数据越相似。

其他一些文献中衡量两个样本之间的差异程度的度量也称为相异度。

在聚类分析中，最常用的距离度量标准有：

（1）著名的距离度量标准是d维空间中的欧几里得距离：

（2）更广义的距离度量标准为d维空间中的明考斯基（Minkowski）距离：

通常明考斯基距离也被称为Lq范数，这样，欧几里得距离就是L2范数，L1范数常被称为曼哈坦（Manhattan）距离或城区（city bloc distance）距离。

例4.2：具有4维属性的样本X1=｛1， 0， 1， 0｝和X2=｛2， 1，—3，—1｝，它们的距离度量标准是L1（X1， X2）=1+1+4+1=7， L2 （X1， X2）=（1+1+16+1）12/=4.36以及L3（X1， X2）=（1+1+64+1）13/=4.06。

欧氏d维空间模型不仅给出了欧几里得距离，而且还给出了另外的相似度度量标准，余弦相关（cosine-correlation）就是其中之一。有兴趣的读者可以参见相关文献。

2）聚类分析中的数据类型

已经知道，聚类结果的质量是基于样本间的相似度来评估的，样本可以用于度量物理对象（如一台计算机）或度量抽象概念（如一种写作风格），这些样本常常是由多维属性表示的，例如“重量”和“颜色”是被使用的两个属性，那么（20，黑色）表示一个重量为20单位的黑色对象。因此两个样本之间的相似性计算还可能涉及它们的各属性值的组合。

样本间的距离函数是常用的相似度度量标准，然而属性的数据类型不同，其距离函数定义则不同。相似度计算常常要求对多种类型的属性数据进行计算，包括区间标度变量、二元变量、标称变量、序数型变量、比例标度变量或者这些变量类型的组合。类型不同相似度的计算方法也有所差异，上一小节介绍的是基本的距离度量标准，下面再对区间标度遍历、二元变量、标称变量、序数型变量等进行更详细的介绍。

（1）区间标度变量（interval-valued variables）。区间标度变量是一个粗略线性标度的连续度量，例如：重量和高度、经度和纬度坐标、大气温度等。区间标度变量相似度度量最常用的距离方法是前面提到的欧几里得距离、曼哈坦距离、明考斯基距离等。但需要注意的是，在实际应用中存在几个问题：

①在许多应用中样本的各个属性常常不具有可比性，如对网站访问用户进行聚类时，如何能够将用户访问页面的停留时间和用户访问页面序列的频率等进行比较。

②度量单位的选用会直接影响聚类分析的结果，如对网站访问用户进行聚类时，用户访问页面的停留时间的单位采用秒还是毫秒。一般而言，所用的度量单位越小，可能的值域就越大，对聚类结果的影响也越大。

③如何处理样本中的各个属性代表不同物理意义的样本。

一般不存在通用的方法来解答这些问题，但为了避免对度量单位选择的依赖，需要对数据进行规格化，引入额外的信息赋予这些操作的物理意义。规格化度量值使得所有的属性具有相同的权重。当没有关于数据的先验知识时，这样做十分有用。但是，在一些应用中，用户可能会给某些属性较大的权重，如对篮球运动员挑选进行聚类时，将会给高度属性较大的权重。

下面介绍一种将度量值转换为无单位的值以实现度量值规格化的方法。

给定一个变量f的度量值，可以进行如下的变换：

①计算平均的绝对偏差（mean absolute deviation）Sf：

其中x1f，…，xnf是f的n个度量值，mf是f的平均值。

②计算规格化的度量值（standardized measurement z-score） ：

在计算平均绝对偏差时，度量值与平均值的偏差（即|xif—mf|）没有被平方，在一定程度上减少了对孤立点的影响，因此使用平均的绝对偏差Sf比标准差σf对孤立点具有更好的鲁棒性。当然，不同的应用中，数据的规格化是否有必要，需要用户根据应用的特点自己选择。

（2）二元变量（binary variables）。二元变量只有两个状态：0或1，0表示变量为空，1表示变量非空。如果采用处理区间标度变量的方法来处理二元变量则会误导聚类的结果，因此针对二元变量要求用特定的方法来计算相似度。

计算由d个二元变量组成的样本xi和Xj间的距离的常规方法是借助样本Xi和Xj的2×2列联表（表4-2）。表4-2中n1.1是对于样本Xi和样本Xj值都为1的属性的数目，n10.是对于样本xi值为1而样本Xj值为0的属性的数目，n0.1是对于样本Xi值为0而样本Xj值为1的属性的数目，n0.0是对于样本Xi和样本Xj值都为0的属性的数目。属性总数是d，d=n1.1 + n1.0+n0.1+ n0.0。

表4-2　样本Xi和Xj的2×2列联表

①对称的二元变量描述的样本间的相似度。具有同等价值且相同权重的两个状态的二元变量是对称的（symmetric），即两个取值0或1没有优先权。例如，属性“性别”具有两个值：“女性”和“男性”。

基于对称二元变量的相似度称为恒定的相似度，即当一些或全部二元变量编码改变时，计算结果不会发生变化。用简单匹配系数（simple matching coefficient， SMC）评价这样的样本Xi和样本Xj之间的相似度（两个样本取相同值的变量数占总变量数的比例）：

②非对称的二元变量描述的样本间的相似度。如果两个状态的输出不是同等重要，则该二元变量是非对称的（asymmetric）。如一个疾病检查的结果：｛阳性，阴性｝。一般的，将比较重要的输出结果（通常是出现概率较小的结果）编码为1，而另一种编码为0。给定两个非对称的二元变量，两个都取值1的情况（正匹配）被认为比两个都取值为0的情况（负匹配）更有意义。因此，这样的二元变量被认为好像只有一个状态。

基于非对称的二元变量的相似度称为非恒定的相似度。评价系数是Jaccard系数（计算时，忽略负匹配的数目，因为负匹配数目认为是不重要的）。

例4.3：样本Xi和样本Xj具有8个二元类型变量：

Xi=｛0， 0， 1， 1， 0， 1， 0， 1｝和Xj=｛0， 1， 1， 0， 0，1，0，0｝，则n1.1=2， n1.0=2，n0.1=1， n0.0=3，根据式3-8、式3-9，计算得：

Ssmc （Xi， Xj） = 5/8， Sjc （Xi， Xj） = 2/5。

当对称的和非对称的二元变量出现在同一个数据集中，可以使用下面将要描述的混合变量方法计算样本间的相似性。

（3）标称变量。标称变量是二元变量的推广，它可以具有多于两个的状态值。例如肤色是一个标称变量，可能具有黄色、白色、黑色和棕色等几种状态。

假设一个标称变量的状态数目是M，这些状态可以用字母、符号或者一组整数（如1，2，…， M）来表示（这些整数只是用于数据处理，并不代表任何特定的顺序）。这样，具有n个标称变量的样本Xi和Xj的相似度可以用简单匹配的方法来计算：

其中，m是匹配的数目，即对样本Xi和Xj取值相同的变量的数目，n是全部变量的数目，可以通过赋权重来增加m的影响，或者赋给有较多状态的变量匹配以更大的权重。

另一个方法是通过为每个标称状态创建一个新的二元变量，用非对称的二元变量来编码标称变量，对一个有特定状态值的对象，对应于该状态值的二元变量值置为1，而其余的二元变量值置为0。例如，为了对标称变量“肤色”进行编码，对应于上面所列四种颜色分别建立一个二元变量，如果一个样本是“黄色”，那么“黄色”变量被赋值为1，其余三个变量被赋值为0，再对这种形式的编码，采用计算二元变量相似度的方法来计算标称变量的相似度。

（4）序数型变量。一个离散的序数型变量类似于标称变量，不同之处在于序数型变量的M个状态是以有意义的顺序排列的。序数型变量针对记录那些难以客观度量的主观评价非常有用，例如比赛的名次，经常按金牌、银牌、铜牌顺序排列，其值的大小并不重要，但它们的相对顺序却是必要的。区间标度变量也可以通过对其值域进行区间划分以离散化而转换为序数型变量。

3）其他相似度度量

简单的距离度量如欧氏距离常可用于反映两个样本间的相似性，而其他相似性度量常用于特征化样本间的概念上的相似性。

考虑周围或邻近点的其他距离度量，这些近邻点称为上下文（context），在给定上下文的情况下，两个样本Xi和Xj的相似性定义为

其中是context（近邻点的集合），相似性用相互间近邻距离（mutual neighbor distance， MND）来度量，定义如下：

其中NN（Xi， Xj）是Xj对于Xi的近邻数目。如果Xi是离Xj最近的点，那么NN（Xi，Xj）等于1，如果它是第二近的点，NN（ Xi ， Xj）等于2，以此类推。

图4-1和图4-2给出了有关MND度量的例子。图4-1中，A是B的最近邻点，B的最近邻点是A。因此NN（A， B）=NN（B，A）=1，MND（A，B）=2。而NN（B，C） =1，NN（C，B）=2，因此MND（B，C）=3。图4-2表示增加三个新的数据样本点D， E和F后的情况，此时MND（B，C）仍等于3，而NN（A，B）=1，NN（B，A）=4，此时MND（A，B）=5。虽然A和B的位置没有改变，但由于引入额外的点，使得A， B间的MND度量值增加了。

图4-1　A和B比A和C更为相似

图4-2　环境改变后，B和C比B和A更为相似

由于MND不满足三角不等式，所以它不是标准度量，但尽管如此，MND度量也被成功用于一些聚类应用中，这也表明相似度度量不一定需要是标准度量。

4）衡量聚类的准则函数(www.xing528.com)

前面讨论了如何衡量相似性的问题，现在来考虑第二个重要概念：用于衡量样本集划分好坏的准则函数。通过定义准则函数，聚类问题可以转化为找到一种划分使得准则函数最优的问题。衡量所获得簇的结果意味着证实所得的簇和聚类分析的初始目标是一致的，即满足内部聚合（相似样本在同一个簇中）和外部分离（相异样本不在同一个簇中）的原则。

（1）误差平方和准则（sum-of-squared-error criterion）：误差平方和准则试图使生成的结果簇尽可能地紧凑和独立，是一种简单而且应用广泛的准则。误差平方和准则函数定义如下：

式中，Je是所有样本的误差平方和。

Je的值取决于簇的数目和样本的分布情况，最优划分是使得Je最小的划分，即对任何一个簇Ci，要使得簇Ci中误差（X—mi）平方和为最小，则样本均值mi最能代表Ci中所有样本。因此，Je衡量的是用k个样本均值m1 ， …， mk分别代表n类样本X1 ， …， Xn产生的平方和误差。

在数据样本能划分成易于区分的几个簇，且簇内数据又很密的情况下采用Je比较适合，但Je准则存在一个潜在的问题是当不同簇所包含的样本个数相差较大时，如孤立点出现时，将一个大的簇分割开反而可能具有更小的误差平方和，造成最小化Je的结果并不理想，此时，这些孤立点也应该被综合起来构成一个更好的准则函数。

（2）相关的最小方差准则：经过一些简单的代数操作，可以从Je的表达式（式4-13）中去掉均值向量，得到一个等价的表达式：

其中

是第i个簇中的点与点距离平方的平均值，最小误差平方和准则用欧几里得距离作为相似性度量的。

同样的，还可以构造其他准则函数。比如将替换为第i个簇中点与点距离的平均值、中值或最大值。更一般地，可以引入一个合适的相似性函数s（X，X′）按照下面的方式替换：

或

此时，定义最优划分就是使得准则函数取极值的划分。

除了以上介绍的两个准则外，还有诸如散布准则等其他的准则函数。

评价聚类过程质量的另一个必不可少的标准是簇间距离度量标准，常用于簇Ci和簇Cj之间的距离度量标准是：

（mi和mj是Ci和Cj的质心）

④平均距离：

（Xi∈Ci和Xj ∈ Cj，且ni和nj是类Ci和Cj|间的样本数）

5）聚类分析过程

聚类分析的输入是一组样本集χ和一个度量两个样本间相似性度量s（或相异度d），可以用一组有序数对（χ， s）（ 或（χ， d））表示，聚类分析的输出是样本集的k个簇，表示为｛C1 ，C2，…，Ck｝，每一个簇Ci通过一些属性描述，因此，聚类分析的一个附加结果可以是对每个簇的综合描述，这种结果对于更进一步深入分析数据集的特性是很重要的。

聚类分析过程可以分为以下几个步骤（图4-3）：

图4-3　聚类分析步骤

步骤一：收集数据样本、可用样本数量、相应属性、属性数量、类型、簇的数量，其中一些信息可能是不可控（或预先未知）的。

步骤二：属性选择或属性抽取：

①属性的选择，从原始属性中选取用于聚类的更有效的属性子集。

②属性的抽取，利用对输入属性的一次或多次转换产生新的更显著的属性。

步骤三：产生一个相似度矩阵：

样本的相似性是由定义在样本对的距离函数度量的。

定义4.5（ 相似度矩阵，similarity matrix）：用于存储n个样本两两间的相似性，表现形式是一个n×n维的矩阵：

其中d（Xi，Xj）是样本Xi和样本Xj之间相似性的量化表示。

步骤四：确定目标划分的簇的数目或聚类划分的某个终止条件及每一个簇的相应定义。

该步可由多种聚类算法实现。

步骤五：实施聚类分析，产生结果。

在以上聚类分析过程中，需要注意一些最基本但又最重要的对聚类分析结果将产生较大影响的问题：

（1）相似性（或距离）度量的选择。相似性（或距离）度量的选择是聚类分析面临的一个关键问题。

聚类分析算法先定义一个合适的相似性度量，然后计算任意两个样本之间的距离。如果该距离确实反映了样本之间的相似性，则希望同一簇中样本之间的距离比不同簇之间样本间的距离小，因此，当两个样本之间的距离小于某个距离阈值d0时，这两个样本就可被认为属于同一类。而这个距离阈值d0将影响簇的数量和大小，选择d0非常关键，d0越小，每个簇就越小，簇的数目就越多。如果d0太大，则所有样本将会被分为同一簇；如果d0太小，每个样本又会单独聚成一类。

另一方面，对于包含部分或全部不连续属性的样本，选择计算样本间的距离或相似度的度量标准更加困难，因为不同类型的属性常常是不可比的，只用一个标准作为度量可能是不合适的。因此，实际中对于样本的不同属性应该使用不同的距离度量标准。

（2）簇的数量的选取。聚类分析得到结果簇的数量的任意性是聚类过程中的主要问题。如图4-4a所示，表示一组分散在二维平面上的点（二维空间样本），簇个数k事先未知，图4-4b给出了以虚线为边界的簇C1 、 C2和C3。由于簇的数量没有预先给出，还可以另外得到如图4-4c所示的分成四个簇的分区，和图4-4b一样简单。

图4-4　簇的数量的选取

选择正确的簇个数非常重要，获得尽可能同质的组需要增加簇的个数，而简约表示则需要减少簇的个数，这两者之间需要一个折中。

（3）属性的选取。属性的选取会影响聚类分析的最终结果，选取时需要考虑能满足所要求目标的所有相关方面，使用不重要的属性将使得结果较差。通常令人满意的情况应该是聚类结果对所使用属性集的微小变化不会太敏感。

（4）算法的选择（如k-means）。 目前已存在大量的聚类算法，主要的聚类算法大体上有基于划分的方法（partitioning method）、基于层次的方法（hierarchical method）、基于密度的方法（density-based method）、基于网格的方法（grid-based method）以及基于模型的方法（model-based method）等几类（图4-5），这些算法有早期出现的传统算法，也有针对数据挖掘特殊要求的大规模数据的可伸缩性等标准的改进算法。还有一些聚类算法集成了多种聚类方法的思想，因此难以将某个给定的算法划分为某类聚类方法。此外，某些应用可能有特定的聚类标准，要求综合多种聚类技术。总之，算法的选择取决于样本集的数据类型、聚类目的和应用等。

图4-5　聚类方法及相应算法概览

①层次方法。层次聚类方法将给定数据样本组成一棵聚类的树，并进行层次的分解。根据层次分解是自底向上还是自顶向下形成，又可分为凝聚的层次聚类AGNES（AGglomerative NESting）和分裂的层次聚类DIANA（DIvisive ANAlysis）。在凝聚或分裂层次聚类方法中，用户能定义希望得到的簇的数目或其他条件等作为聚类结束条件。

凝聚的层次聚类采用自底向上策略，首先将所有样本分成n个原子簇，每个原子簇仅含有一个样本，然后合并这些原子簇形成越来越大的簇，减少簇的数目，先是n-1个簇，接着是n—2个簇，直到所有样本都在一个簇中，或某个终结条件被满足，例如达到了某个希望的簇的数目或两个最近的簇之间的距离超过了某个阈值。簇的数目k（k=n—i+1）对应层次结构的第i层，即第1层对应n个簇，而第n层对应一个簇。

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

层次聚类虽然比较简单，但是在选择凝聚或者分裂点的时候经常会遇到一些困难，这是非常关键的，因为一旦样本被凝聚或分裂以后，下一步的工作是建立在新形成的簇的基础之上的。因此，如果其中任何一步没有做好，则会影响最终聚类的结果。

层次方法的聚类质量的改进方向是将层次聚类和其他的聚类结合起来，这样的代表算法有BIRCH、 CURE、 ROCK和Chameleon等。

②划分方法。基于划分的聚类方法得到的是数据的一个划分，而不同于通过层次聚类方法生成的树状图结构。

划分方法的基本思想是，给定一个包含n个样本的数据集，划分方法将数据划分为k个划分（k≤n），每个划分表示一个簇，同时满足：

a.每个簇至少包含一个样本；

b.每个样本必须属于且仅属于一个簇。

划分方法的一般过程：

a.给定要构建的划分的数目k，创建一个初始划分；

b.采用一种迭代的重定位技术，通过对象在划分间移动来改进划分，优化准则函数把数据集划分成k个簇。

显然，选取期望得到的簇的数目k是划分方法面临的问题，另外，划分方法需要某些度量标准或准则函数用于衡量聚类策略。

绝大多数应用中采用了两种最常用的启发式方法：k-平均（k-means）算法，用每个簇中对象的平均值来表示该簇；k-中心点（k-medoids）算法，每个簇用接近该簇中心的一个样本来表示。这些启发式聚类方法对在中小规模的数据集中发现球状簇很适用，但为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步扩展，如采用基于选择的方法CLARA （Clustering Large Applications）算法以及改进后的CLARANS（Clustering Large Application based upon RANdomized Search）算法等。

③基于密度的方法。基于密度的方法克服了基于距离算法只能发现球状簇的缺点，可以发现任意形状的簇，还可用来过滤孤立点数据。

基于密度的聚类方法的主要思想是只要一个区域中的点的密度（样本的数目）超过某个阈值则继续聚类。也就是对于给定簇中的每个样本，在一个给定范围的区域中必须至少包含一定数目的样本。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。

④基于网格的方法。基于网格的方法是把样本空间量化为有限数目的单元（cell）的网格结构，所有的聚类操作都以单个单元为对象，即在这个网格结构上进行。基于网格方法的突出优点是处理速度快，处理时间与目标数据库中样本个数无关，只与把样本空间分为多少个单元有关。代表算法有；STING算法、CLIQUE算法、WAVE-CLUSTER算法（后两种是既基于网格，又基于密度的）等。

⑤基于模型的方法。基于模型的方法基本思想是，为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。该方法试图优化给定的数据和某些数学模型之间的适应性。它基于以下假设：数据是根据潜在的概率分布生成。基于模型的方法主要有两类：统计学方法和神经网络方法。