---

 

一、数据集的结构

  数据挖掘的数据集 $S$，在数学上可以定义为 $d$ 维向量的一个集合，即 S = { X 1 , X 2 , ⋯   , X n } S=\{X_1 ,X_2, \cdots,X_n\} S={X1​,X2​,⋯,Xn​}，其中 $X_i=(x_{i1},x_{i2},\cdots ,x_{id})(i=1,2,\cdots ,n)$，且将 $X_i$ 称为第 $i$ 个向量的标识符（identifier）。

（一）二维表

  许多数据挖掘任务都假定数据集 $S$ 是一张二维表的结构（表7-1），其中的数据对象 $X_i(i=1,2,\cdots ,n)$ 在表中以一条记录的形式表示。

表7-1 数据集S对应的二维表

1、标识名区域

  二维表的左上角 id 所在单元格，说明其所在列下面的所有字符为数据对象的标识符，且每个标识符是唯一的。

2、标识符区域

  在标识名区域的下面，每一个标识符都是所在行的唯一标识。比如 $X_i$ 就代表第i行对应的 $d$ 维向量 $(x_{i1},x_{i2},\cdots ,x_{id})$。

3、属性名区域

  在标识名的右侧，每一列称为一个属性（attribute）或字段（field），并用一个字符串命名，比如 $A_1,A_2,\dots ,A_d$ 称为属性名，它们规定了该列下面数据的性质或特性，它们因实际问题不同而取不同的名称。

4、数据区域

  在标识符右侧和属性名下面，每一列的数据具有相同的性质或来自具有相同性质的数据集合。

  若将二维表以名为 $S$ 的对象存放在关系数据库中，则为基本表或关系，并将第一行称为表的结构，id 所在列称为主键列或主键属性，每个 $X_i$ 称为主键值，$X_i$ 所在的行称为元组或记录。因此，将主键值 $X_i$ 连同对应的 $d$ 维向量作为一个记录 $(X_i,x_{i1},x_{i2},\cdots ,x_{id})$ 来表示向量 $X_i=(x_{i1},x_{i2},\cdots ,x_{id})$。

例 7-1 设有数据集 S = { X 1 , X 2 , ⋯   , X 8 } S=\{X_1 ,X_2, \cdots,X_8\} S={X1​,X2​,⋯,X8​} 为某商场的顾客消费记录，其中
$X_1$= (男, 已婚, 博士, 1230)；$X_2$= (男, 未婚, 硕士, 2388)；$X_3$= (男, 离异, 学士, 3586)；
$X_4$= (女, 已婚, 博士, 3670)；$X_5$= (男, 未婚, 硕士, 1025)；$X_6$= (女, 丧偶, 其它, 2890)
向量的每个分量值分别表示性别、婚姻状况、学位以及当月消费额等，其中，学位取值 “其它” 表示为大专及以下学历者。请构造 $S$ 的二维表，并举例说明表的结构、主键属性和记录等。

解： 因为 $S$ 是 $d=4$ 维向量的集合，现有6个元素。根据 $d$ 维向量集合 $S$ 的二维表构造方法，可得表7-2所示的二维表，并另取名为 Customers。

表7-2 描述顾客消费记录的二维表Customers

（二）数据矩阵

  对于 $d$ 维向量的集合 S = { X 1 , X 2 , ⋯   , X n } S=\{X_1 ,X_2, \cdots,X_n\} S={X1​,X2​,⋯,Xn​}，在有些数据挖掘任务中也常用 $n\times d$ 的数据矩阵结构来表示。
$$S=\left(\begin{array}{ccccc}{x}_{11}& \cdots & x_{1j}& \cdots & x_{1d}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ x_{i1}& \cdots & x_{ij}& \cdots & x_{id}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ x_{n1}& \cdots & x_{nj}& \cdots & x_{nd}\end{array}\right)\text{\hspace{1em}(7-1)}$$

第 $i$ 行表示第 $i$ 个向量 $X_i=(x_{i1},x_{i2},\cdots ,x_{id})$，称为第 $i$ 个数据对象。第 $k$ 列表示第 $k$ 个属性，因此 $x_{ik}$ 称为第 $i$ 个数据对象的第 $k$ 个属性值或分量。由于矩阵的行对应数据对象，列对应于属性，因此 $S$ 也称为 “对象-属性” 矩阵。

例 7-2 请用数据矩阵结构表示例 7-1所示的顾客消费记录数据集 S = { X 1 , X 2 , ⋯   , X 6 } S=\{X_1 ,X_2, \cdots,X_6\} S={X1​,X2​,⋯,X6​}。

解： 因为例 7-1所示的顾客消费记录数据集 $S$ 是一个有 6 个数据对象的 4 维向量集合，因此可以用 $6\times 4$ 的数据矩阵来表示。

  二维表看上去更容易理解，因为它在消费数据的基础上增加了表结构及其属性名称，并且用标识符（主键值）来唯一标识数据对象的数据记录。数据矩阵存储结构仅存放消费数据，优点是没有引入任何冗余的数据，但理解起来比较困难。比如，单从数据矩阵本身很难理解第 4 列 1230 等数字的含义。

二、属性的类型

（一）连续属性

  在机器学习和数据挖掘领域，通常把属性粗略地分为连续型和离散型两大类，并在对它们的数据对象进行相似性度量时必须采用不同的度量方法。

  连续属性（Continuous attributes）通常在一个实数区间内取值，因此其取值个数理论上是不可数无限的。如表7-2中当月消费额，其属性的取值就是连续的，因为顾客的当月消费额理论上可以是 $[0,+\infty )$ 区间的任意一个实数，因此称为连续属性或连续型属性。
  连续属性的特点是，可进行各种数学运算，不仅可以进行加、减、乘、除的基本运算，也可以计算均值、中位数、众数等刻画数据集 “中心” 的度量值，还可以计算描述数据集分散程度的方差等参数。

1、均值

  最常用，也是最有效的数据集 “中心” 度量方法。 设 $a_1,a_2,\cdots ,a_n$ 为某数值属性 $A$（比如考试成绩）的 $n$ 个观测值，则它们的均值为 $n$ 个数的算术平均值，记作$$\overline{a}=\frac{\sum _{i=1}^n{a}_i}{n}=\frac{a_1+a_2+\cdots +a_n}{n}\text{\hspace{1em}(7-2)}$$

例 7-3 假设有11个学生的百分制考试成绩按递增排序为：55, 60, 70, 75, 75, 75, 80, 80, 80, 90, 95，则按照公式（7-2）得其均值为 $835/11=75.91$。

  在有些应用中，可以给每个 $a_i$ 赋予一个非负的权重 ${\omega }_i(i=1,2,\cdots ,n)$，它们刻画了 $a_i$ 在数据集中的重要性。属性 A 加权算术平均值，也称加权均值计算方法。$$\overline{a}=\frac{\sum _{i=1}^n{\omega }_i{a}_i}{\sum _{i=1}^n{\omega }_i}=\frac{{\omega }_1{a}_1+{\omega }_2{a}_2+\cdots +{\omega }_n{a}_n}{{\omega }_1+{\omega }_2+\cdots +{\omega }_n}\text{\hspace{1em}(7-3)}$$

例 7-4 设某村有10户人家，其中一户做企业年收入1001万，其余9家靠务农年收入1万元，则该村平均每户年收入为 $(9+1001)/10=101$ 万。

  此例说明，均值对数据集中的极端数据（离群点）非常敏感，为了抵消少数极端数据的影响，通常使用 “截头尾均值”（trimmed mean）方法，即将数据集中极少数最大和最小的数据删除后再计算均值。

  例如，将该村每户年收入按照非减方式排序为1, 1, 1, 1, 1, 1, 1, 1, 1, 1001，删除左端一个最小值1和右端大一个最大值1001，再对剩下的8个数据计算均值为1万。对于数据量很大的数据集，通常可考虑去掉高端和低端2％左右的数据，但要避免在两端截去太多（如20％以上）的数据，以防止丢失有价值的信息。

2、中位数

  是有序数据集的中间值，它是把数据较高的一半与较低的一半分开的值。其方法是先把 $n$ 个数据按大小顺序排列，
① 如果 $n$ 为奇数，则取处在最中间位置的那个数据作为这个数据集的中位数（median），也简称中数。
② 如果 $n$ 为偶数，则将最中间两个数的平均值作为该数据集的中位数。

例 7-5 对11个学生的考试成绩11个学生的百分制考试成绩按递增排序为：55，60，70，75，75，75，80，80，80，90，95，则它们的中位数为75，其平均值为75.91。对10户农家的年收入，因为 $n=10$ 是偶数，将排在第5和第6位的两个年收入的均值作为中位数，其值为1，而该数据集的均值为101，两者差别很大。

  中位数对数据集中部分数据的剧烈变化不敏感。对于倾斜（非对称）的数据集，中位数是一个比平均值更好的，刻画数据集中心的度量。

3、众数

  众数（mode）是另一种数据集中心的度量值,是集合中出现最频繁的那个数据值。
① 一个数据集有可能存在好几个数据，其出现的频率都是最高的，即一个数据集有可能出现多个众数。
② 通常将具有一个、两个、三个众数的数据集合分别称为单峰的（unimodal）、双峰的（bimodal）和三峰的（trimodal）。
  一般来说，具有两个或更多众数的数据集称为多峰的（muhimodal）数据集。但如果数据集中任何两个数都不相等，即每个数据值仅出现一次，则该集合没有众数。

例 7-6 对于例 7-3中11个学生的考试成绩数据集有两个众数，分别是75和80，而对例 7-4农户收入数据集的众数为1。因此，众数1万更真实地反映了该村 “广大农户” 年收入的实际情况，比户均101万的年收入更靠谱。

4、方差与标准差

  方差与标准差都是描述数据集分散程度的参数。方差或标准差的值约小，意味数据集中的每个数据越靠近其均值，方差或标准差的值大，表示数据集分散在离均值两端较大的区间之中。

  设 $a_1,a_2,\cdots ,a_n$ 为某数值属性 A 的 $n$ 个观测值，则它们的方差（variance）记作
$${\sigma }^2=\frac{1}{n}\sum _{i=1}^n(a_i-\overline{a}{)}^2\text{\hspace{1em}(7-4)}$$ 其中 $\overline{a}$ 是 $a_1,a_2,\cdots ,a_n$ 的均值，而它们的标准差（standard deviation）是方差 ${\sigma }^2$ 的平方根 $\sigma$。

（二）离散属性

  如果属性不是连续的，则它就是离散的。离散属性（Discrete attributes）是指该属性可以取有限或可数无限个不同的值，其取值可用字母或自然数表示，也可用单词或短语表示。

  在表7-2中的性别属性可取 {男,女} 2个值之一，婚姻状况可以取 {未婚,已婚,离异} 中3个值的任何一个，学位可取 {博士,硕士,学士,其它} 的4个值之一。即顾客id、姓名、性别、婚姻状况和学位等5个属性都是离散的，也称为离散型属性或离散属性。

  离散属性的共同特点是，其值可以进行 $=$ 和 $\ne$ 的比较运算。比如，性别属性的值 “男”$\ne$“女”。有的离散属性的值可以按照 $<$ 或 $\le$ 进行大小或高低排序。比如学位属性的值，可以按照学位从低到高排序为：其它$<$学士$<$硕士$<$博士。

（三）分类属性

  分类属性（categorical attributes）是一种特殊的离散属性，即离散属性的一个细分类型。分类属性的取值是一些符号或事物的名称，每个值代表某种类别、编码或状态，并且这些值之间不存在大小或顺序关系。

  在有些文献中也称为标称属性（nominal attribute），而在计算机科学中，分类属性的取值也被看作是枚举的（enumeration）。

  例如，在表7-2的所有属性中，婚姻状况就是一个分类属性，它可以取单身、已婚、离异和丧偶等4个值之一。在实际生活中，还有很多分类属性的例子。比如，描述人的职业属性，其取值可以为教师、医生、程序员、工人等等。分类属性可以数字或字母代码表示，如婚姻状况等，可以指定代码1表示单身、2表示已婚、3表示离异、4表示丧偶。但分类属性的代码数字并没有数学上的四则运算意义，即对其进行加、减、乘、除或求平均值等运算是没有实际意义。

（四）二元属性

  二元属性（binary attributes）是分类属性的一种特殊情况，即这种属性只取两种可能的值或只能处于两个状态之一，如1或0，其中1表示该状态出现，而0表示不出现。

  属性的取值也可以用 y 或 n 来表示。因此，二元属性又常称为布尔属性，且两种状态分别用t和f来表示。比如，性别属性就是一个二元属性，因此，可以指定代码0表示女，1表示男。

（五）序数属性

  序数属性（ordinal attributes）也是离散属性的一种，其特殊性表现在，它所有可能的取值之间可以进行排序（ranking），虽然任意两个相继值之间的差值是未知的。

（六）数值属性

  数值属性（numeric attributes）是一种定量属性，也看作是一种连续属性。它的取值是可以度量的，一般用整数或实数值表示。数值属性可以是区间标度或比率标度属性。

1、区间标度属性

  区间标度（interval-scaled）属性用相等的单位尺度度量。区间属性的值是有序的，可以为 正、0或负。区间标度值可以比较大小，定量评估任意值之间的差值。

  例如，描述室外温度的属性是区间标度的。对过去5天的温度值从小到大进行排序 $10^{\circ }C,12^{\circ }C,13^{\circ }C,15^{\circ }C,19^{\circ }C$。还可以量化不同值之间的差值，比如，温度 $19^{\circ }C$ 比 $12^{\circ }C$ 高出 $7^{\circ }C$。摄氏温度没有真正的零点，即 $0^{\circ }C$ 不表示 “没有温度”，也不能说一个温度值 $20^{\circ }C$ 是另一个温度 $5^{\circ }C$ 的4倍。

2、比率标度属性

  比率标度（ratio-scaled）属性是具有固有零点的数值属性，它弥补了区间标度无固定0点的不足，故可有一个值是另一个的倍数（或比率）。

  例如，开氏温标($K$)与摄氏和华氏温度不同，它具有绝对零点（$0^{\circ }K=-273.15^{\circ }C$），其物理学意义是，构成物质的粒子在 $0^{\circ }K$ 时具有零动能。因此，我们说温度值 $20^{\circ }K$ 是 $5^{\circ }K$ 的4倍是有意义的。

  许多文献中常常将 “连续属性” 与 “数值属性” 互换地使用。但在有些数据挖掘任务中，我们还是应该注意它们的一些细微差别，避免在中午气温 $20^{\circ }C$ 与凌晨气温 $5^{\circ }C$ 比较的时后，用 “早上气温是凌晨气温的4倍” 这种比率来描述。

三、相似度与相异度

  两个数据对象之间的相似度（similarity）是两个对象相似性程度的一个度量值，取值区间通常为 $[0,1]$，0表示两者不相似，1表示两者相同。

  设数据集 S = { X 1 , X 2 , … X n } S=\{X_1 ,X_2, …X_n\} S={X1​,X2​,…Xn​}，$X_i,X_j\in S$，并用 $s(X_i,X_j)$ 表示数据点之间的相似度，则它具有如下性质：
（1）非负有界性：$0\le s(X_i,X_j)\le 1$，仅当 $X_i=X_j$ 时，$s(X_i,X_j)=1$；
（2）对称性：对于任意 $X_i,X_j$ 之间 $s(X_i,X_j)=s(X_j,X_i)$；

  因此，可以定义 $S$ 的相似度矩阵（similarity matrix）为
$$Sim(S)=\left(\begin{array}{ccccc}1& & & & \\ s(X_2,X_1)& 1& & & \\ s(X_3,X_1)& s(X_3,X_2)& 1& & \\ ⋮& ⋮& ⋮& ⋮& \\ s(X_n,X_1)& s(X_n,X_2)& \cdots & s(X_n,X_{n-1})& 1\end{array}\right)\text{\hspace{1em}(7-5)}$$

说明：有些文献也引进了不在 $[0,1]$ 区间内取值的相似度函数 $s(X,Y)$，即 $s(X,Y)$ 的值越大越，则 $X$ 与 $Y$ 越相似，反之 $X$ 与 $Y$ 越不相似。最简单的方法，就是当 $d(X,Y)\ne 0$ 时，令 $s(X,Y)=1/d(X,Y)$。

  同理，若记 $d(X_i,X_j)$ 表示它们之间的相异度，则可以定义 $S$ 的相异度矩阵（dissimilarity matrix）为
$$D(S)=\left(\begin{array}{ccccc}0& & & & \\ d(X_2,X_1)& 0& & & \\ d(X_3,X_1)& d(X_3,X_2)& 0& & \\ ⋮& ⋮& ⋮& ⋮& \\ d(X_n,X_1)& d(X_n,X_2)& \cdots & d(X_n,X_{n-1})& 0\end{array}\right)\text{\hspace{1em}(7-6)}$$

  因此，要得到数据集 $S$ 的相似度矩阵 $Sim(S)$ 或相异度矩阵 $D(S)$，其关键是相似度 $s(X_i,X_j)$ 或相异度 $d(X_i,X_j)$ 的计算方法。但相似度或相异度的计算通常与数据集的属性类型有关，且不同的数据类型有不同的计算方法。比如，当 $S$ 的所有属性都为数值型时，$X_i$ 和 $X_j$ 之间的距离 $d(X_i,X_j)$ 就是一种常用的相异度函数。许多文献中甚至将距离作为相异度的同义词使用，因此，在没有特别说明的情况下，公式 (7-3) 中的 $d(X_i,X_j)$ 就是它们之间的某种距离。

（一）数值属性的距离

  距离作为空间中任意两点 $X_i$ 与 $X_j$ 之间相距远近的一种测度，应该满足如下三个数学性质。
（1）非负性：$d(X_i,X_j)\ge 0$，即距离是一个非负的实数，$d(X_i,X_j)=0$ 当且仅当 $X_i=X_j$。
（2）对称性：$d(X_i,X_j)=d(X_j,X_i)$，即距离关于数据对象 $X_i,X_j$ 是一个对称函数。
（3）三角不等式：$d(X_i,X_j)\le d(X_i,X_k)+d(X_k,X_j)$，即从对象 $X_i$ 到对象 $X_j$ 的直接距离不会大于途经任何其它对象 $X_k$ 的距离之和。

1、明可夫斯基(Minkowski)距离
$$d(X_i,X_j)={\left[\sum _{k=1}^d|x_{ik}-x_{jk}{|}^p\right]}^{\frac{1}{p}}\text{\hspace{1em}(7-7)}$$

（1）若 $p=1$，则得绝对值距离公式，也称曼哈坦(Manhattan)距离：
$$d(X_i,X_j)=\sum _{k=1}^d|x_{ik}-x_{jk}|\text{\hspace{1em}(7-8)}$$

（2）若 $p=2$，则得欧几里得(Euclidean)距离，也简称为欧氏距离：
$$d(X_i,X_j)={\left[\sum _{k=1}^d|x_{ik}-x_{jk}{|}^2\right]}^{\frac{1}{2}}\text{\hspace{1em}(7-9)}$$

（3）如果让公式（7-7）中的 $r\to \infty$，称切比雪夫(Chebyshev)距离：
$$d(X_i,X_j)=\underset{1\le k\le n}{\max }|x_{ik}-x_{jk}|\text{\hspace{1em}(7-10)}$$

2、二次型距离

  设 $A$ 是 $n$ 阶非负定矩阵，则向量 $X_i$ 与 $X_j$ 的二次型距离定义为
$$d({\mathbf{X}}_{\mathbf{i}},{\mathbf{X}}_{\mathbf{j}})=(({\mathbf{X}}_{\mathbf{i}}-{\mathbf{X}}_{\mathbf{j}})\mathbf{A}({\mathbf{X}}_{\mathbf{i}}-{\mathbf{X}}_{\mathbf{j}}{)}^T{)}^{\frac{1}{2}}$$

（1）当 $\mathbf{A}=\mathbf{I}$（单位矩阵）时，二次型距离蜕变成欧氏距离（公式7-9）。

（2）若 $\mathbf{A}$ 为对角矩阵，即 $\mathbf{A}$ 的对角线上元素为（$a_{11},a_{22},\cdots ,a_{nn}$），其余元素全为 0，则二次型距离特化成加权欧氏距离。
$$d({\mathbf{X}}_{\mathbf{i}},{\mathbf{X}}_{\mathbf{j}})={\left[\sum _{k=1}^d{a}_{kk}|x_{ik}-x_{jk}{|}^2\right]}^{\frac{1}{2}}\text{\hspace{1em}(7-11)}$$

（3）若 $\mathbf{A}={\Omega }^{-1}$，则二次型距离蜕变成马氏(Mahalanobis)距离。
$$d({\mathbf{X}}_{\mathbf{i}},{\mathbf{X}}_{\mathbf{j}})=(({\mathbf{X}}_{\mathbf{i}}-{\mathbf{X}}_{\mathbf{j}}){\Omega }^{-1}({\mathbf{X}}_{\mathbf{i}}-{\mathbf{X}}_{\mathbf{j}}{)}^T{)}^{\frac{1}{2}}\text{\hspace{1em}(7-12)}$$

其中 $\Omega$ 为数据集 S = { X 1 , X 2 , ⋯   , X n } S=\{X_1,X_2 ,\cdots,X_n\} S={X1​,X2​,⋯,Xn​} 的协方差矩阵，
$$\Omega =\frac{1}{n}\sum _{i=1}^n({\mathbf{X}}_{\mathbf{i}}-\overline{\mathbf{X}}{)}^T({\mathbf{X}}_{\mathbf{i}}-\overline{\mathbf{X}})$$ $$\overline{\mathbf{X}}=\frac{1}{n}\sum _{i=1}^n{\mathbf{X}}_{\mathbf{i}}$$

3、MP马氏距离

  马氏距离需计算协方差矩阵 $\Omega$ 的逆矩阵，其复杂性较高 $O(n^3)$，MP马氏距离公式用广义逆矩阵 ${\Omega }^{+}$ 构造，不需要计算逆矩阵 ${\mathbf{S}}^{-1}$。

定义 7-1 对于任意矩阵 $\mathbf{A}$，必存在唯一的矩阵 $\mathbf{B}$，它与 ${\mathbf{A}}^T$ 的阶数相同且满足如下4个方程：

（1）$\mathbf{ABA}=\mathbf{A}$； （2）$\mathbf{BAB}=\mathbf{B}$； （3）$(\mathbf{AB}{)}^T=\mathbf{AB}$； （4）${(\mathbf{BA})}^T=\mathbf{BA}$；

称矩阵 $\mathbf{B}$ 为 $\mathbf{A}$ 的 Moore-Penrose 广义逆矩阵并记作 ${\mathbf{A}}^{+}$，简称为 $\mathbf{A}$ 的 MP 广义逆。

定理 7-2 (${\mathbf{A}}^{+}$的构造) 若 $\mathbf{A}$ 是 $m\ast n$ 矩阵且其奇异值分解形式为 $\mathbf{A}={\mathbf{UMV}}^T$，则 ${\mathbf{A}}^{+}={\mathbf{VTU}}^T$，其中 $M=diag(a_1,a_2,\cdots ,a_r)$ 且 $a_i>0$，$r$ 是矩阵 $\mathbf{A}$ 的秩，$\mathbf{U}$、$\mathbf{V}$ 为正交阵，而矩阵 $\mathbf{T}$ 由 $\mathbf{M}$ 构造而得：若 $M(i,j)\ne 0$，则 $T(i,j)=1/M(i,j)$；若 $M(i,j)=0$，则 $T(i,j)=0$。

  由此可以得到关于数据集 $S=X_1,X_2,\cdots ,X_m$ 的 MP 马氏距离公式
$$d_{mp}(X_i,X_j)={\left[(X_i-X_j{)}^T{\Omega }^{+}(X_i-X_j)\right]}^{\frac{1}{2}}\text{\hspace{1em}(7-13)}$$

其中 $X_i,X_j\in S$，$\Omega$ 为数据集 $S$ 的协方差阵。

（二）分类属性的相似度

1、二元属性的相似度

表7-3 有11个二元属性的数据集S

其中1表示 “出现”、“是” 等，0表示 “未出现”、“否” 等。对 $X_i$ 和 $X_j$ 的分量 $x_{ik}$ 与 $x_{jk}$ $(k=1,2,\cdots ,n)$ 的取值情况进行比较，获得分量的4种不同取值对比的统计参数：
（1）$f_{11}$ 是 $X_i$ 和 $X_j$ 中分量满足 $x_{ik}=1$ 且 $x_{jk}=1$ 的属性个数 (1-1相同)；
（2）$f_{10}$ 是 $X_i$ 和 $X_j$ 中分量满足 $x_{ik}=1$ 且 $x_{jk}=0$ 的属性个数 (1-0相异)；
（3）$f_{01}$ 是 $X_i$ 和 $X_j$ 中分量满足 $x_{ik}=0$ 且 $x_{jk}=1$ 的属性个数 (0-1相异)；
（4）$f_{00}$ 是 $X_i$ 和 $X_j$ 中分量满足 $x_{ik}=0$ 且 $x_{jk}=0$ 的属性个数 (0-0相同)。

显然 $f_{11}+f_{10}+f_{01}+f_{00}=d$，因此 $X_i$ 和 $X_j$ 之间的相似度可以有下几种定义。

（1）简单匹配系数（simple match coefficient,smc）相似度
$$s_{mc}(X_i,X_j)=\frac{f_{11}+f_{00}}{f_{11}+f_{10}+f_{01}+f_{00}}=\frac{f_{11}+f_{00}}{d}\text{\hspace{1em}(7-14)}$$也称作对称的二元相似度。

（2）Jaccard系数相似度
$$s_{jc}(X_i,X_j)=\frac{f_{11}}{f_{11}+f_{10}+f_{01}}=\frac{f_{11}}{d-f_{00}}\text{\hspace{1em}(7-15)}$$也称为非对称的二元相似度。

（3）Rao系数相似度
$$s_{rc}(X_i,X_j)=\frac{f_{11}}{f_{11}+f_{10}+f_{01}+f_{00}}=\frac{f_{11}}{d}\text{\hspace{1em}(7-16)}$$是另一种非对称的二元相似度。

与相似度类似，还可以定义对称二元属性数据集的相异度计算公式：
$$d_{mc}(X_i,X_j)=\frac{f_{10}+f_{01}}{f_{11}+f_{10}+f_{01}+f_{00}}=\frac{f_{10}+f_{01}}{d}\text{\hspace{1em}(7-17)}$$以及非对称二元属性数据集的相异度公式：
$$d_{jc}(X_i,X_j)=\frac{f_{10}+f_{01}}{f_{11}+f_{10}+f_{01}}=\frac{f_{10}+f_{01}}{d-f_{00}}\text{\hspace{1em}(7-18)}$$显然，$s_{mc}(X_i,X_j)+d_{mc}(X_i,X_j)=1,s_{jc}(X_i,X_j)+d_{jc}(X_i,X_j)=1$

2、分类属性的相似度

如果 $S$ 的属性都是分类属性（婚姻状况），则 $X_i$ 和 $X_j$ 的相似度可定义为
$$s(X_i,X_j)=p/d\text{\hspace{1em}(7-19)}$$ 其中 $p$ 是 $X_i$ 和 $X_j$ 的对应属性值 $x_{ik}=x_{jk}$（相等值）的个数，$d$ 是向量的维数。

表7-4 有5个分类属性的数据集

3、序数属性的相似度

  序数属性的值之间具有实际意义的顺序或排位，但相继值之间的差值是未知的，可用mk表示第k个属性的可能取值有状态。

  假设某校用考试成绩、奖学金和月消费3个属性来描写学生在校的信息（表7-5）。其中第1个属性考试成绩取 $m_1=5$ 个状态，其顺序排位为优秀>良好>中等>及格>不及格；第2个属性奖学金取 $m_2=3$ 个状态，其顺序排位为甲等>乙等>丙等；第3个属性月消费取 $m_3=3$ 个状态，其顺序排位为高>中>低。

表7-5 有3个序数属性的数据集

  序数属性的数据对象之间相异度计算的基本思想是将其转换为数值型属性，并用距离函数来计算，主要分为三个步骤：

（1）将第 $k$ 个属性的域映射为一个整数的排位集合，比如考试成绩的域为 {优秀, 良好, 中等, 及格, 不及格} ，其整数排位集合为 {5, 4, 3, 2, 1}；然后将每个数据对象Xi对应分量的取值 $x_{ik}$ 用其对应排位数代替并仍记为 $x_{ik}$ ，比如，表7-5中 $X_2$ 的考试成绩属性值 $x_{21}$ 为 “良好”，则用4代替，这样得到整数表示的数据对象仍记为 $X_i$。

表7-6 用其排位的整数代替的序数属性数据集

（2）将整数表示的数据对象 $X_i$ 的每个分量映射到 $[0,1]$ 实数区间之上，其映射方法为
$$z_{ik}=(x_{ik}-1)/(m_k-1)\text{\hspace{1em}(7-20)}$$ 其中 $m_k$ 是第 $k$ 个属性排位整数的最大值，再以 $z_{ik}$ 代替 $X_i$ 中的 $x_{ik}$，就得到数值型的数据对象，并仍然记作 $X_i$。

  比如，$X_2$ 的考试成绩排位整数是4，映射为 $z_{21}=(4-1)/(5-1)=0.75$；$X_2$ 的奖学金排位整数是2，映射为 $z_{13}=(2-1)/(3-1)=0.50$；

表7-7 用其实数代替排位数的数据集

（3）根据实际情况选择一种距离公式，计算任意两个数值型数据对象 $X_i$ 和 $X_j$ 的相异度。
比如，选用欧几里得距离函数计算任意两点之间的相异度
$$d(X_1,X_2)=\sqrt{(1-0.75{)}^2+(1-0.5{)}^2+(0.5-1{)}^2}=\sqrt{0.0625+0.25+0.25}=\sqrt{0.5625}=0.75$$ 同理可得：$d(X_1,X_3)=1.22$；$d(X_2,X_3)=0.56$

  从计算结果可知 $d(X_2,X_3)$ 的值是最小的，而且从表7-5也可以看出，三个数据对象之间的确是 $X_2$ 与 $X_3$ 的差异度最小。

（三）余弦相似度

  对数值型或属性值用数字表示的数据集中任意两个数据对象 $X_i=(x_{i1},x_{i2},\cdots ,x_{in})$ 和 $X_j=(x_{j1},x_{j2},\cdots ,x_{jn})$，其余弦 (cosine) 相似度定义为：
$$s_{cos}(X_i,X_j)=\frac{X_i\cdot X_j}{\Vert X_i\Vert \cdot \Vert X_j\Vert }\text{\hspace{1em}(7-21)}$$ 其中 $X_i\cdot X_j$ 表示两个向量的内积，$\Vert X_i\Vert$ 表示向量 $X_i$ 的欧几里得范数，即 $X_i$ 到坐标原点的距离，也就是向量 $X_i$ 的长度。

如果令 $\theta$ 是向量 $X_i$ 和 $X_j$ 之间夹角，则 $s_{cos}(X_i,X_j)=cos\theta$。
（1）当 $s_{cos}(X_i,X_j)=0$，即向量 $X_i$ 和 $X_j$ 呈 $90^{\circ }$ 夹角，也就是说它们是相互垂直的，亦即它们是不相似的。
（2）当 $s_{cos}(X_i,X_j)=1$，即向量 $X_i$ 和 $X_j$ 的方向是一致的，它们的方向是完全相似的。

  余弦相似度常常用来评价文档间的相似性。每一个文档通常用一个词频向量（term-frequency vector）来表示，每个属性为文档中可能出现的特定词或短语，属性取值为该词或短语在文档中出现的频度。

表7-8 三个文档的词频向量集

（四）混合属性的相异度

  若数据集 S = { X 1 , X 2 , ⋯   , X m } S=\{X_1 ,X_2, \cdots,X_m\} S={X1​,X2​,⋯,Xm​} 的所有属性都是数值属性（连续属性），则称 $S$ 为数值属性数据集。若 $S$ 的所有属性都是离散属性，则称 $S$ 为离散属性集。若 $S$ 既有数值属性，又有离散属性时，称 $S$ 为混合属性数据集。

  对于混合属性数据集 $S$，通常有两种思路来描述其数据对象之间的相似度或相异度。将每种类型的属性分成一组，然后使用每种属性类型的相似度或相异度定义，分别对 $S$ 进行数据挖掘分析（如聚类分析）。如果这些分析能够得到兼容的结果，则将其融合形成 $S$ 的挖掘结果，但在实际应用中常常不能产生兼容的结果。

  一种更可取的方法是将所有属性类型集成处理，保证在数据挖掘时只做一次分析。基本思想是，假设 $S$ 有 $d$ 个属性，根据第 $k$ 属性的类型，计算 $S$ 关于第 $k$ 属性的相异度矩阵 $D^{(k)}(S)(k=1,2,\cdots ,d)$，最后将其集成为 $S$ 的相异度矩阵 $D(S)$，如公式 (7-22) 就是 $S$ 相异度的一种集成方法。$$d(X_i,X_j)=\frac{\sum _{k=1}^d{\delta }^{(k)}(X_i,X_j)\times d^{(k)}(X_i,X_j)}{\sum _{k=1}^n{\delta }^{(k)}(X_i,X_j)}\text{\hspace{1em}(7-22)}$$ 其中相异度 $d^{(k)}(X_i,X_j)$ 的取值都在 $[0,1]$ 内，因属性类型有3种计算方法。

（1）当第 $k$ 属性是分类或二元属性时，比较 $X_i$ 和 $X_j$ 在第 $k$ 属性的取值，
如果 $x_{ik}=x_{jk}$，则 $d^{(k)}(X_i,X_j)=0$，否则 $d^{(k)}(X_i,X_j)=1$。

（2）当第 $k$ 属性是数值属性时，先求出 $S$ 第 $k$ 属性所有非缺失值的最大值 $ma{x}_k$ 和最小值 $mi{n}_k$，则有$$d^{(k)}(X_i,X_j)=\frac{|x_{ik}-x_{jk}|}{ma{x}_k-mi{n}_k}\text{\hspace{1em}(7-23)}$$

（3）当第 $k$ 属性是序数属性时，先将 $X_i$ 的第 $k$ 属性值转换为 $[0,1]$ 区间的实数 $z_{ik}=(x_{ik}-1)/(m_k-1)$，其 $m_k$ 是 $S$ 第 $k$ 属性排位数的最大值，$x_{ik}$ 是 $X_i$ 的第 $k$ 属性值对应的排位数。用 $z_{ik}$ 和 $z_{jk}$ 代替第（2）种方法公式中的 $x_{ik}$ 和 $x_{jk}$ 即可。

通常，以上公式中的指示符 ${\delta }^{(k)}(X_i,X_j)=1$，仅在以下情况取值为0。
（1）$X_i$ 和 $X_j$ 的第 $k$ 属性分量 $x_{ik}$ 和 $x_{jk}$ 都取空值或有一个取空值；
（2）当第 $k$ 属性为非对称二元属性且 $x_{ik}=x_{jk}=0$ 时；

因此，${\delta }^{(k)}(X_i,X_j)=0$ 表示对象 $X_i$ 和对象 $X_j$ 在第 $k$ 属性上的相异度集成到 $S$ 的相异度矩阵 $D(S)$ 中没有意义。