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

聚类分析中的数据类型

 

假设要聚类的数据集合包含n 个数据对象，许多基于内存的聚类算法选择如下两种有代表性的数据结构：

数据矩阵（Data matrix，或称为对象属性结构）：它用p 个变量（也称为属性）来表现n 个对象，例如用年龄，身高，性别，种族等属性来表现对象“人”。这种数据结构是关系表的形式，或者看为n*p 维（n 个对象*p 个属性）的矩阵。

 

相异度矩阵（dissimilarity matrix，或称为对象-对象结构）：存储n 个对象两两之间的近似性，表现形式是一个n*n 维的矩阵。

d(i,j)是对象i 和对象j 之间相异性的量化表示，通常它是一个非负的数值，当对象i 和

j 越相似，其值越接近0；两个对象越不同，其值越大

d(i,j) = d(j,i)，而且d(i,i)=0

 

数据矩阵经常被称为二模（two-mode）矩阵，而相异度矩阵被称为单模（one-mode）矩阵。这是因为前者的行和列代表不同的实体，而后者的行和列代表相同的实体。许多聚类算法以相异度矩阵为基础。如果数据是用数据矩阵的形式表现的，在使用该类算法之前要将其转化为相异度矩阵。

 

区间标度（Interval-Scaled）变量

 

距离度量，它通常用于计算用该类变量描述的对象的相异性。距离的度量包括欧几里得距离，曼哈顿距离，以及明考斯基距离。

 

“什么是区间标度变量？” 区间标度变量是一个线性标度的连续度量。典型的例子包括重量和高度，经度和纬度坐标，以及大气温度。

选用的度量单位将直接影响聚类分析的结果。。一般而言，所用的度量单位越小，变量可能的值域就越大，这样对聚类结果的影响也越大。为了避免对度量单位选择的依赖，数据应当标准化。标准化度量值试图给所有的变量相等的权重。

 

“怎样将一个变量的数据标准化？”为了实现度量值的标准化，一种方法是将原来的度量值转。换为无单位的值。给定一个变量f 的度量值，可以进行如下的变换：

1．计算平均的绝对偏差（mean absolute deviation）Sf:

Sf = (|x1f-mf|+|x2f-mf|+…+|xnf-mf|)/n

这里的x1f,…,xnf 是f 的n 个度量值，mf 是f 的平均值，即

mf =(|x1f +x2f+…+xnf)/n

2．计算标准化的度量值，或z-score：

zif = (xif – mf) / sf

 

对象间的相异度（或相似度）是基于对象间的距离来计算的。最常用的距离度量方法是欧几里得距离；这里的i=（xi1，xi2，…,xip）和 j=(xj1,xj2,…xjp)是两个p 维的数据对象。

另一个著名的度量方法是曼哈顿距离，其定义如下：

d（I，j）= |xi1-xj1|+|xi2-xj2|+…+|xip-xjp|

 

上面的两种距离度量方法都满足对距离函数的如下数学要求：

1．d（i，j）≥0：距离是一个非负的数值。

2．d（i，i）=0：一个对象与自身的距离是0。

3．d（i，j）= d（j，i）：距离函数具有对称性。

4．d（i，j）≤ d（i，h）+d（h，j）：从对象I到对象j的直接距离不会大于途径任何其他对象的距离。

 

明考斯基距离是欧几里得距离和曼哈顿距离的概化，它的定义如下：

D（I，j）=（|xi1-xj1|q+|xi2-xj2|q+…+|xip-xjp|q）1/q

这里的q 是一个正整数。当q=1 时，它表示曼哈顿距离；当a=2 表示欧几里得距离。

 

如果对每个变量根据其重要性赋予一个权重，加权的欧几里得距离。

 

 

计算用二元变量描述的对象间的相似度

一个二元变量只有两个状态：0 或1，0 表示该变量为空，1 表示该变量存在

 

“对称的二元变量和不对称的二元变量之间的区别是什么？”如果它的两个状态有相同的权重, 那么该二元变量是对称的，也就是两个取值0 或1 没有优先权。

 

如果假设所有的二元变量有相同的权重，我们得到一个两行两列的可能性表8.1。在表中，q 是对对象i 和j 值都为1 的变量的数目，r 是在对象i 中值为1，在对象j 中值为0 的变量的数目，s 是在对象i 中值为0，在对象j 中值为1 的变量的数目，t 是在对象i 和j 中值都为0 的变量的数目。变量的总数是p，p=q+r+s+t。

 

基于对称二元变量的相似度称为恒定的相似度，即当一些

或者全部二元变量编码改变时，计算结果不会发生变化。对恒定的相似度来说，评价两个对象i 和j 之间相异度的最著名的系数是简单匹配系数，其定义如下：

d(I,j) = (r+s) / (q+r+s+t)

如果两个状态的输出不是同样重要，那么该二元变量是不对称的。

 

对非恒定的相似度，最著名的评价系数是Jaccard 系数，在它的计算中，负匹配的数目被认为是不重要的，因此被忽略。D(I,j) = (r+s) / (q+r+s)

 

标称型、序数型和比例标度型变量

 

标称变量

标称变量是二元变量的推广，它可以具有多于两个的状态值。例如，map_color 是一个标称变量，它可能有五个值：红色 ,黄色，绿色，粉红色，和蓝色。

假设一个标称变量的状态数目是M。这些状态可以用字母，符号，或者一组整数（如1，2，…,M）

来表示。要注意这些整数只是用于数据处理，并不代表任何特定的顺序。

“如何计算标称变量所描述的对象之间的相异度？”两个对象i 和j 之间的相异度可以用简单匹配方法来计算：

d(I,j) = (p-m)/p

 

m 是匹配的数目，即对i 和j 取值相同的变量的数目；而 p 是全部变量的数目。我们可以通过赋权重来增加m 的影响，或者赋给有较多状态的变量的匹配更大的权重。

 

 

通过为每个状态创建一个二元变量，可以用二元变量来表示标称变量。对一个有特定状态值的对象，对应该状态值的二元变量值置为1，而其余的二元变量值置为0。

 

序数型变量

一个离散的序数型变量类似于标称变量，除了序数型变量的M 个状态是以有意义的序列排序的。序数型变量对记录那些难以客观度量的主观评价是非常有用的

 

将区间标度变量的值域划分为有限个区间，从而将其值离散化，也可以得到序数型变量。一个序数型变量的值可以映射为排序。例如，假设一个变量f 有Mf 个状态，这些有序的状态定义了一个序列1，…,Mf。

 

 

假设f 是用于描述n 个对象的一组序数型变量之一，关于f 的相异度计算包括如下步骤：

第i 个对象的f 值为xif，变量f 有Mf 个有序的状态，对应于序列1，…，Mf。用对应的rif 代替xif，rif∈ {1,…,Mf}。

既然每个序数型变量可以有不同数目的状态，我们经常必须将每个变量的值域映射到 [0 .0, 1.0]上，以便每个变量都有相同的权重。这一点可以通过用zif 代替rif 来实现。

Zif = (rif –1) / (Mf-1)

 

比例标度型变量

比例标度型变量在非线性的刻度取正的度量值，例如指数