基于C-Vine Copula理论的监督学习分类器的优化

Optimization for C-Vine Copula-Based Supervised Learning Classification

摘要: 由于朴素贝叶斯分类器对特征变量作了独立性假设，忽略了相关性，导致在某些特征相关的情况下分类效果很差。为了提高分类效果，本文对有缺失的数据集利用C-Vine Copula理论进行填补从而得到完整的数据集，并结合Copula函数研究特征变量之间的相关性优化问题，用C-Vine Copula分类器对完整数据集做分类。结果表明，基于C-Vine Copula理论的监督学习分类器具备良好的分类性能。

Abstract: Because of the feature independence assumption, the correlation between variables is ignored, causing that the Naive Bayes works poorly in classification for some cases when the features are correlated. In this paper, for improving the classification effect, the missing datasets are filled by using C-Vine Copula theory. As a result, the complete datasets are got after imputation. By combining the copula function and investigating on the correlation between features, C-vine copula classifier is used to classify complete datasets. The obtained results show that the supervised learning classifier based on the C-Vine Copula theory has better performance.

1. 引言

随着信息技术与网络技术的高速发展，各个行业每天都会产生大量数据。然而现实世界中的数据集通常有质量问题，如存在一些错误数据、缺失数据、不确定数据。在数据质量问题中，缺失数据现象尤其常见。

朴素贝叶斯分类是机器学习和数据挖掘中最流行的学习算法之一，主要用于给定特征变量的分类问题。朴素贝叶斯分类器对分类对象的特征变量作了条件独立性假设，该假设忽略了特征变量之间的相关性，从而忽略了实际数据中的相关性 [1]。

Sklar (1959) [2] 提出的Copula理论指出，一个多元联合分布可以分解为k个边缘分布和一个Copula函数，这个Copula函数描述了变量间的相关性。Nelsen (1999) [3] 较为系统地介绍了Copula函数的定义和构建方法，使得Copula理论成为构造多元变量联合分布及描述随机变量间相依结构的重要工具。Joe (1996) [4] 首次提出了Pair Copula的理念，Bedford和Cooke (2001) [5] 基于Joe的研究提出了Pair Copula构建(PCC)方法，利用图论中藤(Vine)描述结构，将高维Copula函数仿照树藤结构的分解形式分解为一系列二元成对Copula函数，称为Vine Copula模型。Aas (2009) [6] 等进一步深入研究Vine Copula模型，详细论述了Vine Copula模型的参数估计和数值模拟的方法。

针对有缺失的数据集，本文设计并提出基于C-Vine Copula理论的贝叶斯分类器，进一步优化贝叶斯分类器。首先，确定需要归因的特征变量，通过C-Vine Copula理论将数据集的联合概率分布分解为一系列二元Copula函数与边缘概率密度函数乘积的形式；然后，将归因特征作为目标特征，对其他特征变量根据特征样本间的相关性，选择适当的二元Copula函数，计算条件分布函数和相应的逆函数，从而提出C-Vine Copula Imputation算法(CVI)，用该算法得到的预测值替换缺失值得到新的数据集，对新的数据集构建贝叶斯分类器中的条件概率密度函数；最后，将优化后的分类器应用到实际分类问题中，对模型进行分析验证。与样本丢弃法(NADel)、均值归因法(Mean)、预测平均匹配插补法(PMM)、贝叶斯线性回归归因法(Norm)、分类回归树归因法(Cart)和在观测值中随机抽样归因法(Sample)比较，本文提出的分类器具备良好的性能，能够为有缺失的数据集的分类提供新的实现途径。

2. C-vine Copula贝叶斯分类器

2.1. Copula函数

根据Sklar定理可知，一组n维随机向量，其联合概率分布可以分解为n个一元的边缘分布函数与一个n维Copula函数的乘积。设 $X=\left(X_1,\cdots ,X_n\right)$ 为一组n维随机变量，其联合概率分布 $F\left(x_1,\cdots ,x_n\right)$ 与边缘分布 $F_1,\cdots ,F_n$ 的关系可以表示为：

$F\left(x_1,\cdots ,x_n\right)=C\left(F_1\left(x_1\right),\cdots ,F_n\left(x_n\right)\right)$，

如果各边缘分布函数都是连续的，则Copula函数是唯一的。若 $F_k$ 的逆函数 $F_k^{-1}$ 存在，则

$C\left(u_1,\cdots ,u_n\right)=F\left(F_1{}^{-1}\left(u_1\right),\cdots ,F_n{}^{-1}\left(u_n\right)\right)$，

其中 $u_k=F_k\left(x_k\right)\in \left(0,1\right)$， $k=1,2,\cdots ,p$。当Copula函数可微时，可以得到F的联合概率分布

$f\left(x_1,\cdots ,x_n\right)={\displaystyle \underset{k-1}{\overset{p}{\prod }}{f}_k}\left(x_k\right)\cdot c\left(F_1\left(x_1\right),\cdots ,F_n\left(x_n\right)\right)$，

$f_k\left(x_k\right)$ 是 $F_k$ 的边缘密度，c是C的Copula密度。

$f\left(x_1,\cdots ,x_n\right)=f_n\left(x_n\right)\cdot f\left(x_{n-1}|x_n\right)\cdot f\left(x_{n-2}|x_{n-1},x_n\right)\cdots f\left(x_1|x_2,\cdots ,x_n\right)$ (1)

根据Aas [6] 等的论述，可以再次分解条件概率密度函数式(1)，可得

$f\left(x|\nu \right)=c_{x,v_j|\nu {}_{-j}}\left(F\left(x|{\nu }_{-j}\right),F\left(v_k|{\nu }_{-j}\right)\right)\cdot f\left(x|{\nu }_{-j}\right)$，

其中，条件分布的表达式为

$F\left(x|\nu \right)=\frac{\partial C_{x,{\nu }_j|{\nu }_{-j}}\left(F\left(x|{\nu }_{-j}\right),F\left(v_j|{\nu }_{-j}\right)\right)}{\partial F\left(v_j|{\nu }_{-j}\right)}$，

$\nu$ 是随机变量x去掉 $x_i$ 后的 $n-1$ 维向量； ${\nu }_{-j}$ 是 $\nu$ 中去掉 ${\nu }_j$ 后的向量； ${\nu }_j$ 为 $\nu$ 中任意一个成分； $c_{x,{\nu }_j|{\nu }_{-j}}$ 为相应条件下的二元Copula条件概率密度函数。

当 ${\nu }_{-k}=\Phi$，x和 $\nu$ 都是均匀分布时，式(6)可简化得到

$h\left(x,\nu \right)=F\left(x|\nu \right)=\frac{\partial C_{x,\nu }\left(x,\nu \right)}{\partial \nu }$， (2)

其中 $h(\cdot )$ 称为h-函数，是用于生成伪观测值的函数，之后将用它来拟合C-Vine结构的模型 [7]。

2.2. C-Vine Copula Imputation算法

在构建多维变量的联合概率分布函数时，可以用多种二元Copula结构描述变量之间的相关性，其中C-vine Copula和D-vine Copula是最典型的两种 [8]。本文采用C-vine Copula结构对随机变量的复杂相关性进行建模。图1为一个4维C-Vine的分解实例。

Figure 1. A 4-dimensional C-vine example

图1. 4维C-vine结构

逆采样方法是较为常见的生成随机数的方法，令F是 $\Re$ 上连续递增的分布函数，它的逆函数 $F^{-1}$ 定义为：

$F^{-1}:\left(0,1\right)\to \Re$， $F^{-1}\left(x\right):=\text{inf}\left\{y\in \Re :F\left(y\right)\ge x\right\}$。

如果 $U~U\left[0,1\right]$ 是在 $\left[0,1\right]$ 上的均匀分布随机变量，则 $F^{-1}\left(U\right)$ 有分布函数F。如果X有分布函数F，则 $F\left(X\right)$ 是 $\left[0,1\right]$ 上的均匀分布。

Bedford和Cooke [5] [9] 以及Kurowicka和Cooke等 [10] 对Vine抽样算法都有讨论。Aas等 [6] 给出C-Vine和D-Vine的一般性算法。对于 $X=\left(X_1,\cdots ,X_{n-1},X_n\right)$ 这组n维随机变量， $X_n$ 上有缺失数据。首先，生成与缺失数据数量相等的随机数 $v_n$ ；再根据条件分布函数和h-函数可以得到

$F\left(x_n|x_1,\cdots ,x_{n-1}\right)=\frac{{\partial }_{n-1}{C}_{n,n-1|1:n-2}\left(F\left(x_n|x_1,\cdots ,x_{n-2}\right),F\left(x_{n-1}|x_1,\cdots ,x_{n-2}\right)\right)}{\partial F\left(x_{n-1}|x_1,\cdots ,x_{n-2}\right)}$。

所以，缺失数据 $X_n$ 可以表示为

$X_n=F_{n|1:n-1}^{-1}\left(V_n|X_1,\cdots ,X_{n-1}\right)$。

2.3. C-Vine Copula分类器

在n维C-Vine结构中，有 $n-1$ 颗树 $T_j\left(j=1,\cdots ,n-1\right)$，每棵树由节点和边组成。每条边对应一个二元Copula，树 $T_j$ 的边是树 $T_{j+1}$ 的节点。整个分解由n个边缘分布和 $n\left(n-1\right)/2$ 个二元Copula的乘积得到的。由此可知，C-vine Copula结构的联合概率分布函数可以分解为

$f\left(x_1,\cdots ,x_n\right)={\displaystyle \underset{k=1}{\overset{n}{\prod }}f\left(x_k\right)}\times {\displaystyle \underset{i=1}{\overset{n-1}{\prod }}{\displaystyle \underset{j=1}{\overset{n-i}{\prod }}{c}_{i,i+j;1:\left(i-1\right)}}}\left(F\left(x_i|x_1,\cdots ,x_{i-1}\right),F\left(x_{i+j}|x_1,\cdots ,x_{i-1}\right)\right)$， (3)

其中， $F\left(\cdot |\cdot \right)$ 是条件分布函数，可由式(2)得到； $c_{i,i+j;1:\left(i-1\right)}$ 为二元Copula条件概率密度。

根据贝叶斯准则，向量 $X=\left(X_1,\cdots ,X_n\right)$ 是类别 $e\in E$ 的概率为

$\mathrm{Pr}\left(e|x\right)\propto \mathrm{Pr}\left(x|e\right)\cdot \mathrm{Pr}\left(e\right)$， (4)

其中E是类向量， $E={\left(e_1,\cdots ,e_l\right)}^{\prime }$，l是类别总数。结合联合概率分布函数式(3)，式(4)写作

$\mathrm{Pr}\left(e|x\right)\propto \underset{f\left(x|e\right)}{\underset{︸}{{\displaystyle \underset{k=1}{\overset{n}{\prod }}{f}_k\left(x_k|e\right)}{\displaystyle \underset{i=1}{\overset{n-1}{\prod }}{\displaystyle \underset{j=1}{\overset{n-i}{\prod }}{c}_{i,i+j;1:\left(i-1\right)}}}\left(F\left(x_i|x_1,\cdots ,x_{i-1}\right),F\left(x_{i+j}|x_1,\cdots ,x_{i-1}\right)|e\right)}}\times \mathrm{Pr}\left(e\right)$。

根据最大后验决策规则(MAP)，可以得到

$\text{classify}\left(x\right)=\left\{e:\arg \max f\left(x|e\right)\cdot \mathrm{Pr}\left(e\right)\right\}$。

本文采用核函数方法估计边缘概率密度函数。核函数方法是一种非参数方法， $x_1,\cdots ,x_n$ 是独立同分布的n个样本点，设概率密度函数为f，则测试样本x的概率密度估计值为

${\hat{f}}_n\left(x\right)=\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{K}_n\left(x-x_i\right)}=\frac{1}{nh}{\displaystyle \underset{i=1}{\overset{n}{\sum }}K\left(\frac{x-x_i}{h}\right)}$，

其中， $K(\cdot )$ 是高斯核函数； $h>0$ 称为带宽 [11] [12]。

3. 实证分析

为验证本文提出方法的有效性和可行性，用UCI数据库中的数据集对比不同填补缺失数据方法下的分类结果。

3.1. 实验设计

首先，对数据集某一列 $X_n$ 做完全随机缺失，缺失率分别为5%、10%、20%、50%和70%，将数据集分为完整数据(complete)和缺失数据(missing)。然后，根据CVI得出缺失数据 $u_n$，并将 $u_n$ 与70%的完整数据(complete)放在一起作为新的训练集，剩下的30%完整数据作为测试集，依据新的训练集用C-vine Copula分类器对测试集进行分类。接下来，分别用样本丢弃法(NADel)、均值归因法(Mean)、预测平均匹配插补法(PMM)、贝叶斯线性回归归因法(Norm)、分类回归树归因法(Cart)及从观测值中随机抽样归因法(Sample)填补缺失数据，再在C-Vine Copula分类器上对测试集分类。最后，重复以上步骤100次，得到不同填补算法的平均分类准确性。各个填补算法的分类结果如下。

3.2. 结果分析

对UCI中的2个数据集分别在缺失率为5%、10%、20%、50%和70%的情况下，用CVI、NADel、Mean、PMM、Norm、Cart和Sample做填补处理。分类准确率的测试结果如表1和表2所示。由表1、表2可知，相比其他填补算法，CVI算法在大多数情况下均能得到更高的分类准确率。

Table 1. Classification accuracy for Iris data set

表1. Iris数据集填补算法分类性能表

Table 2. Classification accuracy for Breast Cancer data set

表2. Breast Cancer数据集填补算法分类性能表

图2描绘了数据集Breast Cancer在5种不同数据缺失率的情况下，用7种填补算法得到的分类性能比较图。由折线图可知，CVI算法在7种填补算法中具有最好的分类性能。

Figure 2. Classification performance of Breast Cancer dataset

图2. Breast Cancer的分类性能图

4. 结论

本文针对数据集中存在缺失数据的情况，结合C-vine Copula函数，利用条件分布函数填补缺失数据，再将变量的联合概率分布分解成二元Copula函数与边缘概率密度函数乘积的形式，分别对二元Copula函数和边缘概率密度函数进行优化估计，将特征变量之间的复杂相关性构建在条件概率密度函数中。与其他算法相比，提高了贝叶斯分类器处理具有复杂相关性特征变量数据的分类性能，在实际应用中得到了较好的分类结果。

基金项目

辽宁省教育厅自然科学基金项目(LJC201914)；辽宁省自然科学基金(2019MS285)。