衡量2个对象之间的距离和相似度在数据挖掘^[1]和机器学习^[2]任务中起着重要作用，它往往只是算法^[3]嵌入式的一个小步骤，却能对整个学习算法效果产生巨大影响。所以，确定一个合适的距离度量是数据挖掘和机器学习的重要研究内容。

当对象数据是数值数据，常用闵可夫斯基距离、欧氏距离和马氏距离^[4]衡量对象的距离。但当对象数据是分类数据^[5]，它的属性值是类别属性而不是数字，因此数值数据的距离度量不能在分类数据上使用。为了解决这个问题，最简单的方法就是将分类数据转化成数值数据，然后运用数值数据的距离度量。

然而将分类数据转化成数值数据的方法会丢失分类数据原有的数据分布和结构特点，因此很多学者利用分类数据的特点来衡量分类数据的距离和相似度。文献[6]提出汉明距离(Hamming Distance Metric, HDM) ，它给相同属性值距离定义为0，不同属性值距离定义为1。这种简单的方式不仅忽略了属性值的分布特征，而且平等地对待每一个属性。所以越来越多的学者从分类数据的分布特征和属性之间关系定义分类数据的距离度量。如Ahmad等^[7]提出了一种无监督分类数据距离度量(Ahmad’s Distance Metric, ADM) ，Ienco等^[8-9]提出基于上下文的距离(Context-Based Distance Metric, CBDM) ，这些度量在定义一个属性的2个值之间的距离时利用了相关属性的数据信息，所以它们都不适用于独立属性数据集。Jia等^[10]利用目标属性的频率信息提出了一个新的距离度量(Jia’s Distance Metric, JDM)，Chen等^[11]提出了一个概率分布函数来衡量属性的距离，Jian等^[12]基于分类数据的内在异构关系，针对非独立同分布数据提出了分类数据耦合相似度量(Coupled Metric Similarity, CMS) ，但是，这些度量方法都没有区分分类数据的有序属性^[13-14]，而是将有序属性当作标称属性来对待。

针对这一问题，有学者提出了区分有序属性的分类数据距离度量方法。其中最简单的方式是在汉明距离的基础上用连续的整数来编码有序属性的等级结构，并用数字之间的距离除以最大整数与最小整数差的商来衡量2个有序值的距离^[15]。但这样的定义方式同样忽略了属性之间的影响。近几年来，既区分有序属性又考虑属性之间关系的分类数据距离度量方法被提出^[16-18]。其中文献[16]提出了一种基于熵的距离度量(Entropy-Based Distance Metric, EBDM) ，EBDM利用了信息熵的和来定义同一个属性中的2个属性值之间的距离；文献[17]提出了一种统一的分类数据距离度量(Unified Distance Metric, UDM) ，UDM在定义同一个属性中的2个属性值之间的距离不仅考虑了这个属性的影响，还考虑了其他属性的影响。EBDM和UDM都考虑了有序属性的顺序结构关系，并提出了有序属性和标称属性统一的分类数据距离度量。但是这2种度量方法都利用信息熵来定义分类数据距离，而信息熵是从数据的概率分布中得到的，它依赖于数据的概率分布，间接地描述了分类数据的特征，并没有直接从分类数据的数据特征中定义距离。

因此针对这个问题，本文提出了一种基于图结构的分类数据距离度量(New Distance Metric, NewDM) 。它利用有序属性和标称属性的图结构，定义了2个概率分布列之间的距离，并利用平均信息熵占总体平均信息熵的比值来衡量属性的重要性。NewDM同时兼备了概率和信息熵的优点，使异构属性距离的度量更准确且更具可比性。NewDM是无参数的，在6个数据集上的实验结果验证了NewDM的度量性能优于其他度量方法。同时本文总结了区分有序属性的分类数据距离定义的基本框架公式，使分类数据的距离定义更加简单明了。

1 相关工作 1.1 分类属性的图结构

分类数据按属性划分为有序属性和标称属性，有序属性和标称属性的相同点是它们都由类别属性值构成，不同点是有序属性的属性值之间具有等级关系，例如学生成绩的属性值：优秀、良好、及格、不及格。这些属性值都是由类别属性构成，但是很明显它们之间还具有等级顺序关系，所以有序属性也可以看作是特殊的标称属性。

在数学领域中，图论^[19]是一个以图为研究对象的重要分支。其中图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。由于有序属性中的属性值之间具有等级关系，当有序属性的属性值按等级从高到低排列并用线将每一个属性值与邻近的属性值连接，同时将属性值当作是顶点，则有序属性的图结构是单链状的树^[20]。对于标称属性，标称属性值之间没有等级关系，所以每两个属性之间都可以连接起来，因此标称属性值之间的图结构是完全图^[21]。若有序属性的属性值按等级从高到低排列分别为 $ {a_{r,1}},{a_{r,2}},{a_{r,3}},{a_{r,4}} $ ，则有序属性的图结构如图1(a)所示。若标称属性的属性值分别是 $ {a_{r,1}},{a_{r,2}},{a_{r,3}},{a_{r,4}} $ ，则标称属性的图结构如图1(b)所示。

1.2 区分有序属性的分类数据距离度量

目前区分有序属性的分类距离度量的方式可分成2种。第1种，仅利用有序属性之间具有等级结构的思路出发，在原有不区分有序属性的分类距离度量中单独定义有序属性值之间的距离。例如文献[15]中将有序属性编码数值后，用数值数据的方法来定义有序属性之间的距离。第2种，利用有序属性是特殊的标称属性的思路，在原有不区分有序属性的分类距离度量中将有序属性的结构特点融入到距离定义中加以区分^[16-18]。

对于这2种区分有序属性的思路，第1种单独区分的方式，容易造成标称属性和有序属性尺度之间的差异，不能很好地揭示分类数据的数据特征。第2种区分的方式既考虑到有序属性和标称属性之间的共同特性，又考虑到这2种不同属性之间的差异，所以第2种区分的方式会优于第1种。由于文献[16-18]中区分有序属性的思路大致相同，所以这些度量方法在定义分类数据任意属性下2个属性值之间距离的基本框架公式也大致相同。不同的是它们量化2个属性值之间距离的方法和属性之间权重的定义。

因此将同一个属性下2个属性值之间距离的基本框架公式进行梳理。先给定第 $ r $ 个属性中2个属性值 $ m $ 和 $ h $ 之间距离的公式，记为 $ \varphi (m,h) $ ，权重记为 $ w $ 。然后，2个属性值之间距离的基本框架公式需要有以下2个步骤：第1步，区分第 $ r $ 个属性是有序属性还是标称属性，当第 $ r $ 个属性是标称属性时， $ \varphi (m,h) $ 无需改变，当第 $ r $ 个属性是有序属性时，因为有序属性中属性值之间具有等级结构，将所有属性值按等级从低到高用连续整数 $ 1,2,3, \cdots ,n $ 编码后，则 $ \varphi (m,h) $ 需要变为 $\displaystyle \sum\limits_{s = \min (m,h) }^{\max (m,h) - 1} {\varphi (s,s + 1) }$ ，式中： $ \min (m,h) $ 为属性值 $ m $ 和 $ h $ 中等级较低的那个属性值， $ \max (m,h) {{ - }}1 $ 为属性值 $ m $ 和 $ h $ 中等级较高的那个属性值还要低一级的属性值；第2步，加入权重 $ w $ 衡量属性的重要程度。通过这2个步骤，最终得到了第r个属性下2个属性值 $ m $ 和 $ h $ 之间距离的基本框架公式，用 $ D(m,h) $ 表示，可记为

$ D(m,h) =\left\{\begin{array}{l}w{\displaystyle \sum _{s=\mathrm{min}(m,h) }^{\mathrm{max}(m,h) -1}\varphi (s,s+1) ,\;\;当{r}为有序属性}\\ w\varphi (m,h) ,\;\;当{r}为标称属性\end{array} \right.$

(1)

$ D(m,h) $ 不仅将有序属性的等级结构融入到距离定义中，还考虑了属性之间的重要程度。它使区分有序属性的分类数据的距离定义变得更加清晰明了，仅需定义 $ \varphi (m,h) $ 和 $ w $ 即可。也为本文提出的距离度量提供了基本框架公式和定义的思路。

2 本文方法

给定分类数据 $ n $ 个对象 $ {\boldsymbol{X}} = \left\{ {{{\boldsymbol{x}}_1},{{\boldsymbol{x}}_2}, \cdots ,{{\boldsymbol{x}}_n}} \right\} $ ，第 $ i $ 个对象记为 $ {{\boldsymbol{x}}_i} = \left( {{x_{i1}},{x_{i2}}, \cdots ,{x_{id}}} \right) $ ， $ d $ 个属性分别由 ${A_1}, {A_2}, \cdots ,{A_d}$ 表示，且前 ${d_{{\rm{ord}}}}$ 个属性表示有序属性，后 $ {d_{{\text{nom}}}} $ 个属性表示标称属性，则 $ d = {d_{{\text{ord}}}} + {d_{{\text{nom}}}} $ 。对任意 $ {A_r} $ 由 $ {a_{r,1}},{a_{r,2}}, \cdots ,{a_{r,{v^r}}} $ 属性值构成， $ \left| {{A_r}} \right| $ 表示 $ {A_r} $ 中属性值的数量。当 $ {A_r} $ 为有序属性，其属性值之间等级关系从高到低排列可写成： $ {a_{r,1}} \succ {a_{r,2}} \succ \cdots \succ {a_{r,{v^r}}} $ ，符号“ $ \succ $ ”表示左边属性值等级高于右边属性值。

对任意2个数据对象 $ {{\boldsymbol{x}}_i} $ 与 $ {{\boldsymbol{x}}_j} $ ，它们的距离表示为 $ {\text{Dist}}( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} ) $ ，则 ${\text{Dist}}( {{\boldsymbol{x}_i},{{\boldsymbol{x}}_j}} )$ 可用 $ d $ 个子距离的欧氏距离来表示，记为

$ {\text{Dist}}\left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right) = \sqrt {{{\sum\nolimits_{r = 1}^d {{\text{dist}}( {{x_{ir}},{x_{jr}}} ) } }^2}} $

(2)

子距离 $ {\text{dist}}( {{x_{ir}},{x_{jr}}} ) $ 为 $ {{\boldsymbol{x}}_i} $ ， ${\boldsymbol{x}_j}$ 在 $ {A_r} $ 属性中 $ {x_{ir}} $ 和 $ {x_{jr}} $ 的距离，若 $ {x_{ir}},{x_{jr}} $ 分别为 $ {a_{r,t}},{a_{r,h}} $ ，则有

$ {\text{dist}}( {{x_{ir}},{x_{jr}}} ) = {\text{dist}}( {{a_{r,t}},{a_{r,h}}} ) $

(3)

文献[17]中提出了 $ {a_{r,t}},{a_{r,h}} $ 的距离不仅与 $ {A_r} $ 有关系，还与其他属性有关系。所以令 ${\psi _{r,m}}( {{a_{r,t}},{a_{r,h}}} )$ 表示 $ {A_r} $ 属性值 $ {a_{r,t}},{a_{r,h}} $ 在 $ {A_m} $ 属性中的距离， ${\psi _{r,m}}( {{a_{r,t}},{a_{r,h}}} )$ 的公式详见2.1。

2.1 图结构下两个概率分布列的距离

在 $ {A_r} $ 属性值为 $ {a_{r,t}} $ 的条件下 $ {A_m} $ 属性值分别是 $ {a_{m,1}},{a_{m,2}}, \cdots ,{a_{m,{v^m}}} $ 的概率分布列表示为 $[p_1^{{a_{r,t}}},p_2^{{a_{r,t}}}, \cdots , p_{{v^m}}^{{a_{r,t}}}]$ ， $ {A_r} $ 属性值为 $ {a_{r,h}} $ 的条件下 $ {A_m} $ 属性值分别是 ${a_{m,1}}, {a_{m,2}}, \cdots ,{a_{m,{v^m}}}$ 的概率分布列表示为 $[p_1^{{a_{r,h}}}, p_2^{{a_{r,h}}}, \cdots ,p_{{v^m}}^{{a_{r,h}}}]$ ，其中 $ p_{{v^m}}^{{a_{r,t}}} $ 是 $ {A_r} $ 的属性值 $ {a_{r,t}} $ 的条件下 $ {A_m} $ 属性值为 $ {v^m} $ 的概率。对于这2个概率分布列 $ [p_1^{{a_{r,t}}},p_2^{{a_{r,t}}}, \cdots ,p_{{v^m}}^{{a_{r,t}}}] $ 与 $[p_1^{{a_{r,h}}}, p_2^{{a_{r,h}}}, \cdots ,p_{{v^m}}^{{a_{r,h}}}]$ 的距离，最常用的方法是把这2个概率分布列当成数值向量，利用闵可夫斯基距离和欧氏距离等数值距离方法来度量^[11]。但是这些度量方法仅从数值的差异量化这2个分布列的距离，未能真正从不同属性的结构特征中量化这2个分布列的距离。例如，当 $ {A_m} $ 是有序属性，概率分布列 $ [1,0,0] $ 与 $ [0,1,0] $ 的欧氏距离与 $ [1,0,0] $ 和 $ [0,0,1] $ 的欧氏距离是相等，但是因为有序属性值具有等级结构，所以 $ [1,0,0] $ 和 $ [0,0,1] $ 的距离要比 $ [1,0,0] $ 与 $ [0,1,0] $ 的距离大^[18]。所以本文分别利用标称属性和有序属性图结构来定义2个概率分布列之间的距离。

首先将 $ [p_1^{{a_{r,t}}},p_2^{{a_{r,t}}}, \cdots ,p_{{v^m}}^{{a_{r,t}}}] $ 与 $ [p_1^{{a_{r,h}}},p_2^{{a_{r,h}}}, \cdots ,p_{{v^m}}^{{a_{r,h}}}] $ 的距离看作是 $ [p_1^{{a_{r,t}}},p_2^{{a_{r,t}}}, \cdots ,p_{{v^m}}^{{a_{r,t}}}] $ 转变成 $ [p_1^{{a_{r,h}}},p_2^{{a_{r,h}}}, \cdots ,p_{{v^m}}^{{a_{r,h}}}] $ 的最小转变量，所以 $ [p_1^{{a_{r,t}}},p_2^{{a_{r,t}}}, \cdots ,p_{{v^m}}^{{a_{r,t}}}] $ 和 $ [p_1^{{a_{r,h}}},p_2^{{a_{r,h}}}, \cdots ,p_{{v^m}}^{{a_{r,h}}}] $ 之间的最小转化量与 $[p_1^{{a_{r,t}}} - p_1^{{a_{r,h}}},p_2^{{a_{r,t}}} - p_2^{{a_{r,h}}}, \cdots ,p_{{v^m}}^{{a_{r,t}}} - p_{{v^m}}^{{a_{r,h}}}]$ 和 $ [0,0, \cdots ,0] $ 之间的最小转化量是等价的。

定义1 　当 $ {A_m} $ 为标称属性时， $ [0,0, \cdots ,0] $ 与 $ [p_1^{{a_{r,t}}} - p_1^{{a_{r,h}}},p_2^{{a_{r,t}}} - p_2^{{a_{r,h}}}, \cdots ,p_{{v^m}}^{{a_{r,t}}} - p_{{v^m}}^{{a_{r,h}}}] $ 之间的最小转化量可定义为 $\dfrac{1}{2}{{\displaystyle\sum\limits_{i = 1}^{{v^m}} {\left| {p_i^{a{}_{r,t}} - p_i^{a{}_{r,h}}} \right|} }}$ 。

当2个分布列分别为 $ [0.4,0.4,0.1,0.1] $ 和 $ [0.3,0.2, 0.1,0.4] $ 时，这2个分布列相减后得 $ [0.1,0.2,0, - 0.3] $ ，很明显 $ [0.4,0.4,0.1,0.1] $ 与 $ [0.3,0.2,0.1,0.4] $ 之间的最小转化量就是将 $ [0.1,0.2,0, - 0.3] $ 变为 $ [0,0,0,0] $ 所需要的最小转化量。由于标称属性值的图结构为完全图，每个属性值之间都直接相连，所以每个属性之间的转化距离可定义为1，其中每一步的转化量会等于这一步的数值乘以距离，若最小转化过程是用正数将负数抵消，则转化过程如图2所示，其中虚线表示的是最小转化过程。这个最小转化过程是将 $ 0.1 $ 转化到 $ - 0.3 $ 的位置，这一步的转化量为 $ 0.1 \times 1 $ ；将 $ 0.2 $ 转到 $ - 0.3 $ 的位置，这一步的转化量为 $ 0.2 \times 1 $ ，所以这2个分布列的最小转化量是这2步转化量的和： $ 0.3 $ 。因此当 $ {A_m} $ 为标称属性时，这2个分布列的距离是 $ 0.3 $ 。

定义2 　当 $ {A_m} $ 为有序属性时， $ [0,0,\cdots ，0] $ 与 $ [{p}_{1}^{{a}_{r,t}}-{p}_{1}^{{a}_{r,h}},{p}_{2}^{{a}_{r,t}}-{p}_{2}^{{a}_{r,h}},\cdots ，{p}_{{v}^{m}}^{{a}_{r,t}}-{p}_{{v}^{m}}^{{a}_{r,h}}] $ 之间的最小转化量可定义为 $\dfrac{1}{{{v^m} - 1}}{{\displaystyle\sum\limits_{i = 1}^{{v^m} - 1} {\left| {\sum\limits_{w = 1}^i {\left( {p_w^{{a_{r,t}}} - p_w^{{a_{r,h}}}} \right) } } \right|} }}$ 。

当 $ {A_m} $ 为有序属性， $ {v^m} $ 个属性值之间按等级将属性值连接后的图结构是单链状的树。每个属性值只与它们邻近等级的属性值相连，所以，转化的过程只能从最高级的属性值到最低级的属性值的方向或者从最低级属性值到最高级属性值的方向进行。由于最高级的属性值到最低级属性值需要走 $ {v^m} - 1 $ 步，若最高级的属性值到最低级属性值的总距离定义为1，则每一步的距离应该是 ${1}/\left({{{v^m} - 1}}\right)$ 。和标称属性一样，每一步的转化量是这一步转化的数值乘以距离。

也就是说当 $ {A_m} $ 为有序属性， $ [0.1,0.2,0, - 0.3] $ 转变为 $ [0,0,0,0] $ 所需要的最小转化过程若是从 $ 0.1 $ 的位置向 $ - 0.3 $ 的位置方向进行会有以下3个步骤，转化过程图详见图3，其中虚线表示每一步的转化过程，虚线中间的数值是这一步的转化量：第1步，将第1位置中的 $ 0.1 $ 移到第2位置，转化量为 ${{0.1}}/{3}$ ，此时第2位置上的值应为 $ 0.1 + 0.2 = 0.3 $ ；第2步，将第2位置的 $ 0.3 $ 移到第3位置，转化量为 ${{0.3}}/{3}$ ，此时第3位置上的值是仍是 $ 0.3 $ ；第3步，将第3位置上的 $ 0.3 $ 移到第4列，转化量为 ${{0.3}}/{3}$ ，此时第4个位置上的值为 $ 0.3 + \left( { - 0.3} \right) = 0 $ ，转化结束。因此转化过程的最小转化量是每一步转化量的和 $\left({{0.1 + 0.3 + 0.3}}\right)/{3}$ 。

综上所述， $ {\psi _{r,m}}\left( {{a_{r,t}},{a_{r,h}}} \right) $ 的公式可记为

$ \begin{array}{l}{\psi }_{r,m}\left({a}_{r,t},{a}_{r,h}\right) \text=\\ \left\{ \begin{array}{l}\dfrac{1}{{{v^m} - 1}}{{\displaystyle \sum _{i=1}^{{v}^{m}-1}\left|{\displaystyle \sum _{w=1}^{i}\left({p}_{w}^{{a}_{r,t}}-{p}_{w}^{{a}_{r,h}}\right) }\right|}}\text{，} 当{a}_{r,t} \ne {a}_{r,h},m \le {d}_{{\rm{ord}}}\\ \;0,当{a}_{r,t}={a}_{r,h}\\\dfrac{1}{{2}} {{\displaystyle \sum _{i=1}^{{v}^{m}}\left|{p}_{i}^{a{}_{r,t}}-{p}_{i}^{a{}_{r,h}}\right|}}\text{，}当{a}_{r,t}\ne {a}_{r,h},m > {d}_{{\rm{ord}}}\end{array} \right.\end{array}$

(4)

式中： $\dfrac{1}{{2}}{{\displaystyle\sum\limits_{i = 1}^{{v^m}} {\left| {p_i^{a{}_{r,t}} - p_i^{a{}_{r,h}}} \right|} }}$ 和 $\dfrac{1}{{{v^m} - 1}}{{\displaystyle\sum\limits_{i = 1}^{{v^m} - 1} {\left| {\displaystyle\sum\limits_{w = 1}^i {\left( {p_w^{{a_{r,t}}} - p_w^{{a_{r,h}}}} \right) } } \right|} }}$ 的取值范围都为 $ [0,1] $ 。若 $ {A_m} $ 为标称属性，2个分布列形如两个不同的单位向量， $\dfrac{1}{{2}}{{\displaystyle\sum\limits_{i = 1}^{{v^m}} {\left| {p_i^{a{}_{r,t}} - p_i^{a{}_{r,h}}} \right|} }} = 1$ 。若 $ {A_m} $ 为有序属性，当且仅当2个分布列分别形如首尾取值的单位向量时， $\dfrac{1}{{{v^m} - 1}}{{\displaystyle\sum\limits_{i = 1}^{{v^m} - 1} {\left| {\sum\limits_{w = 1}^i {\left( {p_w^{{a_{r,t}}} - p_w^{{a_{r,h}}}} \right) } } \right|} }}$ 的值为1。

2.2 权重的定义

在同一个数据集中，每一个属性的重要程度是不一样的，信息理论用信息熵来描述数据的不确定性，不确定越大代表着数据的信息量越大，信息量越大也代表着这个数据是更重要的，因此可用信息熵来量化每个属性的重要程度。

若属性 $ {A_r} $ 中的属性值 $ {a_{r,1}},{a_{r,2}}, \cdots ,{a_{r,{v^r}}} $ 的概率分布列表示成 $ [{p_1},{p_2}, \cdots ,{p_{{v^r}}}] $ ，其中 $ {p_s} = {{\sigma ({a_{r,s}}) } \mathord{\left/ {\vphantom {{\sigma ({a_{r,s}}) } n}} \right. } n} $ ， $ \sigma ({a_{r,s}}) $ 是 $ {A_r} $ 属性值为 $ {a_{r,s}} $ 的数量， $ s $ 可取 $ 1,2, \cdots ,{v^r} $ 。则属性 $ {A_r} $ 的信息熵可表示为

$ W({A_r}) = \sum\limits_{s = 1}^{{v^r}} { - {p_s}\ln {p_s}} $

(5)

但是，一个属性的属性值的类别数量越多，信息熵 $ W({A_r}) $ 也会越大，为了使 $ W({A_r}) $ 不受属性值类别数量的影响，利用平均信息熵 $ H\left( {{A_r}} \right) $ 来衡量一个属性的信息量。

定义3 　若 $ {A_r} $ 属性的概率分布列表示成 $ [{p_1}, {p_2}, \cdots ,{p_{{v^r}}}] $ ，则平均信息熵可定义为

$ H\left( {{A_r}} \right) =\frac{1}{{{ - \ln ({1}/{{{v^r}}})}}}{{\displaystyle\sum\limits_{s = 1}^{{v^r}} { - {p_s}\ln {p_s}} }} $

(6)

式中： $ H\left( {{A_r}} \right) $ 的取值范围为 $ [0,1] $ 。

所以属性 $ {A_r} $ 的重要程度可以利用 $ {A_r} $ 属性的平均信息熵占所有属性的平均信息熵和的比值 $ {w_r} $ 来表示，则 $ {w_r} $ 的公式可记为

$ {w_r} = {{H\left( {{A_r}} \right) }}\Bigg/{{\displaystyle\sum\limits_{{{i}} = 1}^d {H\left( {{A_i}} \right) } }} $

(7)

2.3 一种新的分类数据距离度量方法(NewDM)

本文利用有序属性和标称属性的图结构特征定义了 $ {a_{r,t}} $ 和 $ {a_{r,h}} $ 在 $ {A_m} $ 中2个概率分布列的距离 ${\psi _{r,m}}( {{a_{r,t}},{a_{r,h}}} )$ ，并利用平均信息熵占总体平均信息熵的比值 $ {w_r} $ 来衡量属性的重要程度。根据式(1)的基本框架公式，将 $ {A_r} $ 区分有序属性并加入权重 $ {w_r} $ 后， ${\text{dist}}( {{a_{r,t}},{a_{r,h}}} )$ 可记为

$ \text{dist}({a}_{r,t},{a}_{r,h} ) = \left\{ \begin{array}{l}{w}_{r}\displaystyle \sum _{s=\mathrm{min}(t,h) }^{\mathrm{max}(t,h) -1}{\displaystyle \sum _{m=1}^{d}{\psi }_{r,m}({a}_{r,s},{a}_{r,s+1} ) , 当t \ne h且r \leqslant {d}_{{\rm{ord}}}}\\ {w}_{r}{\displaystyle \sum _{m=1}^{d}{\psi }_{r,m}({a}_{r,t},{a}_{r,h})，当t\ne h且r > {d}_{{\rm{ord}}}}\\ 0,当t=h\end{array}\right. $

(8)

本文提出的NewDM计算步骤详见算法1。

算法1 　NewDM

输入：数据集 $ {X = \left\{ {{{\boldsymbol{x}}_1},{{\boldsymbol{x}}_2}, \cdots ,{{\boldsymbol{x}}_n}} \right\}}$ ， $ { d} $ , $ {{d_{{\rm{ord}}}} }$

输出： $ {{\text{Dist}}( {{{\boldsymbol{x}}_i},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {{\boldsymbol{x}}_j}}) }$ ，其中 $ { i,j \in \left\{ {1,2, \cdots ,n} \right\}} $

1.for $ { r = 1 }$ to $ { d} $

2.　　根据式(6)和(7)计算 $ { {w_r} }$ ；

3.end for

4.for $ {r = 1} $ to $ { d} $

5.　　for $ { m = 1 }$ to $ { d }$

6.　　　　根据式(4)计算 $ { {\psi _{r,m}}( {{x_{ir}},{x_{jr}}} ) }$ ；

7.　　end for

8.　　根据式(8)计算 $ { {\text{dist}}( {{x_{ir}},{x_{jr}}} ) }$ ；

9.end for

10.根据式(2)计算 $ {{\text{Dist}}( {{{\boldsymbol{x}}_i},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {{\boldsymbol{x}}_j}} ) }$ 。

首先利用式(6)、(7)计算出每个属性的权重 $ {w_r} $ ，然后利用式(4)、(8)计算这2个对象在每个属性中的距离 ${\text{dist}}( {{x_{ir}},{x_{jr}}} )$ ，最后利用式(2)求出这2个对象的距离。

3 实验

为了验证NewDM在分类数据中的有效性，使用6个公开的分类数据集，利用3种聚类评价指标，设计2个实验来验证NewDM的有效性。

3.1 实验设置 3.1.1 数据集说明

本文使用6个分类数据集来进行实验，这6个数据集都来自美国加州大学UCI机器学习数据库，它们分别是Qualitative、Car、Zoo、Solar、Hayes、Student。其中 Qualitative、Car是只有有序属性的分类数据，Zoo、Solar 是只有标称属性的分类数据，Hayes、Student是既有有序属性又有标称属性的混合型分类数据，所有数据集中缺失属性值的数据都被忽略，具体数据集信息如表1所示。其中 $ n $ 表示数据集的样本数量， ${d_{{\rm{ord}}}}$ 和 ${d_{{\rm{nom}}}}$ 分别表示数据集中有序属性和标称属性的个数。

3.1.2 实验评价指标说明

为了衡量不同分类数据距离度量的聚类效果，采用3种评价指标，分别是聚类精度(Clustering Accuracy, CA)^[22]，调整的兰德指数(Adjusted Rand Index, ARI)^[23]和归一化信息(Normalized Mutual Information, NMI)^[24]。

CA为分类正确的数据对象的百分比，表达式为

$ {\text{CA}} =\frac{1}{n} {{\displaystyle\sum\nolimits_{i = 1}^n {\delta ( {{c_i},{\text{map}}\left( {{l_i}} \right) } ) } } } $

式中： $ {c_i} $ 为第 $ i $ 个数据的真实标签， $ {\rm{map}}\left( {{l_i}} \right) $ 为映射到真实标签后的预测标签值，当 ${c_i} = {\text{map}}\left( {{l_i}} \right) ,\delta ( {{c_i},{\text{map}}\left( {{l_i}} \right) } ) = 1$ ，当 $ {c_i} \ne {\text{map}}\left( {{l_i}} \right) $ ， $\delta ( {{c_i},{\text{map}}\left( {{l_i}} \right) } ) = 0$ 。CA的取值范围是 $ \left[ {0,1} \right] $ ，且CA值越大聚类效果越好。

ARI比RI更有区分度，表达式为

$ {\text{ARI}} = {{\left( {{\text{RI}} - E\left( {{\text{RI}}} \right) } \right) } \mathord{\left/ {\vphantom {{\left( {{\text{RI}} - E\left( {{\text{RI}}} \right) } \right) } {\left( {{\text{max}}\left( {{\text{RI}}} \right) - E\left( {{\text{RI}}} \right) } \right) }}} \right. } {\left( {{\text{max}}\left( {{\text{RI}}} \right) - E\left( {{\text{RI}}} \right) } \right) }}$

式中： $ E\left( {{\text{RI}}} \right) $ ， $ {\text{max}}\left( {{\text{RI}}} \right) $ 为RI的均值和最大值。ARI的取值范围是 $ \left[ { - 1,1} \right] $ ，值越大效果越好。当ARI为负数时，用符号“−”表示。

NMI从信息理论角度来衡量预测标签和真实标签的一致性，表达式为

$ {\rm{NMI}} = \frac{{\left( {\displaystyle\sum\nolimits_{r = 1}^k {\displaystyle\sum\nolimits_{t = 1}^k {{{{c_{r,t}}\lg ( {n {c_{r,t}}} ) } \mathord{\left/ {\vphantom {{{c_{r,t}}\lg \left( {n \cdot {c_{r,t}}} \right) } {{c_r} \cdot {c_t}}}} \right. } {{c_r} {c_t}}}} } } \right) }}{{\left( {\left( {\displaystyle\sum\nolimits_{r = 1}^k {{c_r}\lg {{{c_r}} \mathord{\left/ {\vphantom {{{c_r}} N}} \right. } N}} } \right) \left( {\displaystyle\sum\nolimits_{t = 1}^k {{c_t}\lg {{{c_t}} \mathord{\left/ {\vphantom {{{c_t}} N}} \right. } N}} } \right) } \right) }} $

式中： $ k $ 为类标签的数量， $ {c_r} $ 为预测标签值为 $ r $ 的数量， $ {c_t} $ 为真实标签值为 $ t $ 的数量， $ {c_{r,t}} $ 为同时满足预测标签值为 $ r $ 、真实标签值为 $ t $ 的数量。NMI取值范围是 $ \left[ {0,1} \right] $ ，NMI越大效果越好。

3.1.3 实验方案

为了验证NewDM的有效性，设置了2个实验。实验1将分类数据距离度量HDM、JDM、EBDM、UDM和NewDM分别嵌入到K-Modes算法^[25]，比较这5种度量方法的聚类效果，来验证NewDM的有效性。其中以HDM为度量基准，JDM是未区分有序属性的度量中较为经典的一种分类数据距离度量。EBDM和UDM都是区分有序属性和标称属性的分类数据距离度量方法，所以NewDM的主要对比距离是EBDM和UDM。

实验2将NewDM嵌入到不同的分类数据聚类算法中，与原有算法的聚类效果进行比较，来验证NewDM在不同聚类算法的有效性。选择K-Modes算法作为算法基准，基于子空间的聚类算法有较好的聚类效果，所以选择文献[26]中的熵加权聚类算法(Entropy Weighting K-Means, EWKM) 和文献[27] 中的加权 OCIL聚类算法(Weighted Object-cluster Similarity metric, WOCIL) 作为经典的聚类算法。为了实验的公平，所有算法都随机选取聚类中心，其中聚类中心数从真实标签中获取，并对每个数据集运行10次后取平均值及其标准差作为最后结果，用“平均值±标准差”来表示。对实验1的结果用黑体、“ ＿” “ $\uwave {\quad} $ ”来分别表示K-Modes算法，EWKM和WOCIL与它们各自嵌入NewDM的聚类算法中效果更好的实验结果。

3.2 实验结果及分析

实验1的结果如表2所示。在只有有序属性的数据集Qualitative和Car中，NewDM的优势非常明显，表明了基于有序属性图结构的概率分布列距离比利用信息熵的度量方法更好地揭示和量化了有序属性数据的特征。在只有标称属性的数据集Zoo和Solar中，NewDM效果不如有序属性中显著，但在其他4种分类数据距离度量中的效果仍是最好的。它表明了在纯标称属性的分类数据中利用2个概率分布列之间的距离和利用平均信息熵信息作为权重也是可行的。在既有有序属性又有标称属性的数据集Hayes和Student中，NewDM效果仍然优于其他几种距离度量,这表明了NewDM分别利用有序属性和标称属性图结构定义的概率分布列距离，使异构属性距离的度量更加准确。综上所述，在每个数据集中，NewDM在K-Modes聚类算法中的3个指标的结果都是最好的，它验证了NewDM不仅优于不区分有序属性的距离度量，也优于区分有序属性中利用熵来定义距离的EBDM和UDM。

实验2用来验证NewDM嵌入到3个不同聚类算法的有效性。表3的实验结果表明，嵌入了NewDM的聚类算法的聚类效果整体上都优于原有的聚类算法距离或相似度量，这验证了将NewDM嵌入到分类数据聚类算法中不仅可行而且可以提升聚类的效果。同时也验证了NewDM兼备了概率和信息熵的优点，使异构属性距离的度量更准确且更具可比性。

4 结论

为了更好地揭示和量化分类数据中不同属性的数据特点，本文利用标称属性和有序属性的图结构定义了2种概率分布列之间的距离，并利用平均信息熵占总体平均信息熵的比值作为权重，提出了一种新的分类数据距离度量方法NewDM，通过与现有的几种分类数据距离度量方法和聚类算法进行对比，验证了NewDM的度量性能优于其他度量方法。同时本文还总结了2个属性值之间距离的基本框架公式，它为区分有序属性的分类数据距离度量提供了更加清晰的定义思路和改进方向。