不确定性数据的分类方法研究综述

沈 杰 许高建 杨 阳 李绍稳

(安徽农业大学信息与计算机学院， 合肥 230036)

不确定性数据的分类方法研究综述

沈 杰 许高建 杨 阳 李绍稳

(安徽农业大学信息与计算机学院， 合肥 230036)

传统的数据挖掘分类方法能够成功地应用于确定性数据分类，但却无法满足绝大多数领域中复杂的不确定性数据的分类需求，由此出现了一系列针对不确定性数据的分类方法。通过大量研究，目前经典的分类算法及针对不确定数据分类的改进方法得到了很大发展，如改进后的支持向量机算法、朴素贝叶斯算法、决策树算法等日渐成熟。

不确定性数据； 分类； 支持向量机； 朴素贝叶斯； 决策树

面临海量的、复杂的不确定性数据，针对不确定性数据的数据挖掘成为智能分析数据并获取知识的重要手段，分类算法成为其主要的研究方向之一。2006年，第六届IEEE数据挖掘国际会议(ICDM)评选了最具影响的10个数据挖掘算法，其中分类算法占据了6个：k-NN、Naive Bayes、C4.5、CART、SVM、AdaBoost[1]。分类的任务就是通过分析来建立区分对象的分类模型，即分类器。传统的分类算法通常将精确数据作为研究背景，只考虑了精准数据的输入和分类，因而不能直接应用于不确定性数据分类，如支持向量机(SVM)、决策树、朴素贝叶斯算法等。针对此现象，基于这些算法的原有经典模式加以改进，加入不确定性数据分析，可使得不确定知识数据挖掘技术更加成熟。

1 不确定性数据

1.1 不确定性数据的产生

数据的不确定性源于数据本身。数据不确定性分以下几种情况：采集数据时出现缺省值、干扰值等；在实验时受周围环境的影响而导致数据不确定；在数据传输过程中的失真导致不确定性。

1.2 不确定性数据的表示

不确定性一般可分为存在(元组级)不确定性和值(属性级)不确定性[2]。其中，存在(元组级)不确定性是指一个对象即有出现的可能性，也有不出现的可能，如某天可能会下雨或者可能不会下雨；而值(属性级)不确定性是指这个对象取值的不确定性。在高维空间中，确定性数据对象表现为某些具体的点，而不确定数据对象的表现形式为满足某种分布的一个范围。

2 常见的不确定性数据分类方法

2.1 支持向量机算法

Vapnik等人提出的传统支持向量机是一种基于统计学理论、以结构风险最小化为原则的判别式分类器[3-5]。其基本思想是，在n维数据空间中寻找一个超平面，可以极大化地将空间属于不同类别的样本点分开，对于精确的小样本数据有很好的分类效果。孙喜晨等人对不确定数据作了预处理，在属性均值聚类(AMC)与支持向量机(SVM)的基础上，提出基于(属性)聚类的属性支持向量机(AMC-ASVM)算法[6]。该算法对样本进行属性均值聚类，然后将各个聚类中心及其属性作为新的样本点来训练，进而得到分类器[7]。但该方法本质上是将数据的不确定性转化为确定性来处理，对不确定性考虑得不够充分。

Jianqiang Yang等人在SVM中引入多维高斯分布模型来描述不确定数据的，提出USVC、 AUSVC及MPSVC支持向量机分类算法[8]。USVC的原始问题通过引入约束得到，将机会约束的规划问题转化为二次规划问题来求解。而AUSVC以及MPSVC是由USVC算法改进而来，即通过调整USVC中的机会约束的置信参数来减小不确定性对构造分类器的负面影响。但该算法由于二次规划问题而导致计算过程复杂、难以理解。

相对于区间的不确定，李文进等人提出了区间不确定性超球支持向量机(IUHSVM)[9]。该方法的基本思想是：将不确定数据表示为球体凸集区域，形成区间，找到一个超平面使得各类球体区域之间的间隔尽可能大，使其能正确划分。建立超球支持向量机模型，将该模型转化为2层嵌套约束规划问题，使得其在寻找最优超平面的计算过程中，降低计算难度。大量的实验结果表明，IUHSVM算法相比其他算法有较强的多分类处理能力，其球体凸集模型能较好地描述不确定性。

2.2 贝叶斯分类算法

贝叶斯分类算法是基于贝叶斯定理的一种算法统称。在统计资料的基础上，依据某些特征，计算各个类别的概率，以后验条件概率来判断是否属于该类，从而实现分类。朴素贝叶斯(Naive Bayes)法是是基于贝叶斯定理和特征条件独立假设的分类方法。对于给定的训练数据集，首先基于特征条件独立假设学习输入输出的联合分布概率；然后基于此模型，对给定的输入x，再利用贝叶斯定理求出其后验概率最大的输出y[10]。

对不确定性数据进行贝叶斯分类时，会使用概率分布函数来表示该不确定区域[11]。当数值型数据属性是不确定的时候，称之为不确定性数值属性(UNA)[12]。有3种扩展的贝叶斯方法可以解决不确定性数据分类，分别是均值的方法、基于分布的方法及基于公式的方法[13]。

均值的方法是最为简单直接的一种方法。用平均值(期望)代替概率密度函数，从而使其变为点值，实际上也是将不确定性数据转化为确定性数据，再使用原本的贝叶斯模型和核密度函数实现分类。这个方法最大的优势就是简单明了，不需要使用新的不确定性数据分类算法。但其缺点也很明显：用平均值代替区间同样对不确定性考虑得不够充分；基于分布的方法重点在于对不确定性数据的类条件分布进行估计，用概率密度函数来表示不确定数据，再将原本的核密度估计函数进行扩展，来进行不确定性数据的分类。相对而言，基于分布的方法对不确定性数据的处理更完善；而基于公式的方法是通过这些不确定性数据来确定新的核密度估计公式，再利用这个核密度估计公式完成分类。该方法的关键在于正确地生成核密度估计函数的公式，但该方式仅仅适用于一些密度函数和概率分布函数的联合。

2.3 决策树算法

决策树，是一种用某种策略筛选条件而建立起来的树，利用递归的方式和分治的思想，自顶向下的分类方法。决策树学习的目的是为了产生一颗范化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的分而治之策略。

针对不确定性数据，目前有Dempste和Shafe提出的“证据理论”和经典决策树结合的D-S决策树算法[14]。D-S决策树在不确定环境中(即目标所在的类和属性的值是不确定的)，通过证据理论决策树分类模型中的置信度和似然函数来表达这个不确定的值[15-16]。在该算法中利用不确定测量函数(称为D-S熵)来选择划分属性，用经典决策树方法生成决策树。首先计算全集D的不确定测量，假设用E(D)表示；然后求不确定区间的中心，即全集的信任函数与全集的最大似然函数和的二分之一，假设用N(D)表示，最后求出的总不确定度测量函数是两者之和，H(D)=E(D)+N(D)。若要选择属性A作为划分属性，且有V个可能取值，则要计算A属性的D-S熵，最终求出平均互信息量[14]。具有最大互信息量的属性将作为划分属性。在该算法中，主要运用了置信度和最大似然函数来表达不确定性，建树的过程参考经典决策树。

DTU[17]也是一种利用决策树处理不确定性数据的算法，主要是通过扩展传统的信息熵和信息增益来建立不确定性的决策树分类模型，当元组的概率密度函数(probability density function，PDF)所在的域跨越分裂点时，PDF通过分数元组技术将元组分裂到子集中[18-19]。

3 不确定性数据的组合分类算法

上述几种分类算法最终形成的分类器也只是单一的分类器，每一种分类器都有各自适用的场合。在实际应用中，单一的分类器很难使其具有稳定性。组合分类器可通过参考多个分类信息来提高分类精度，优化单一分类器的稳定性。

3.1 基于期望值的AUG算法

AUG(Average)算法处理不确定性问题的一般思路是，将不确定性输入转化为确定性的输入。在高维空间中，不确定性表现为集中的一团数据。在这一团数据中有一个期望值，那么取这个期望值作为新的样本，如此问题可转化为确定性分类，继而直接使用传统的分类算法即可。但该算法的严重缺点在于，损失了大量的不确定信息，使得其分类结果不够准确。

3.2 基于采样的USM算法

在上述AUG算法中，只取了一团数据样本中的期望值作为一个确定的样本点，其结果导致分类不准确。为此，USM(Uniform Sampling Method)算法在取样的时候并不再只取期望值一个样本，而是在期望值的附近采样，这样一些样本也都接近期望值。可以看出，这样的算法效率依赖于取样规模的大小，规模过大，消耗大，效率低，且规模过小也会出现分类结果不准确。

3.3 基于采样的EUS算法

对于上述USM算法，规模大小影响分类结果，可以采用一种组合分类器策略：即对不确定性数据进行规模大小一致的采样，但采样的点各不相同。在若干次采样之后得到n个采样结果，对每一个采样结果构建分类器，使得出现了n个分类器，将这n个分类器组合起来形成EUS(Ensemble Uniform Sampling)算法。该算法从原来的单一分类器变成多分类器的组合，分类精度提高了，但与此同时也增加了更多的消耗，效率问题仍有待解决。

3.4 基于权重采样的EWS算法

在上述EUS算法中，每个子分类器采样的规模是相同的。但在现实情况下，很多数据都会存在重要性的问题，也就是权重大小的问题。进行数据采样时，应多采集权重大的数据，运用EWS(Ensemble Weight Sampling)算法。这就需要考虑，如何定义权重的大小。Schapire于1996年提出了AdaBoost算法，旨在通过寻找仅仅比随机猜测略好一些的弱学习算法，就可以将其提升为强学习算法[20]。该算法的核心思想是，每分类一次得到一个分类器，每次都会出现一些错分的情况。将错分的点权值变大，迭代上述步骤，将这些分类器组合起来，会有很好的分类效果。

4 不确定性数据分类算法在各领域的研究

上述分类算法在各领域经过了实验验证与应用。严信等人针对遥感影像数据的具有边界模糊和解译过程不确定性的特点，将遥感影像数据作为实验对象，通过将云模型和模糊支持向量机结合来提高分类精度[21]。王超等人提出了3类不确定性支持向量机算法的数值验证以及用于人脸识别的应用[22]。李芳等人利用美国加州大学Irvine分校用于分类算法开发和测试的标准数据集bollon仿真和分析D-S证据理论决策树，仿真结果表明，D-S证据理论决策树能有效地对不确定性数据进行分类，有较好的分类精度[14]。赵大雷等人利用不确定性贝叶斯分类模型有效刻画了降雨量这一属性级不确定性，并利用黄土滑坡不确定性特征集数据设计了不确定性贝叶斯分类模型和朴素贝叶斯分类模型的对比试验[23]。实验结果表明，不确定性贝叶斯分类器更具分类精度。黄凯等人利用不确定性贝叶斯模型解决水质评价中检测数据、水质级别、水质标准所蕴含的不确定性数据[24]。

5 结 语

传统的分类方法针对确定性数据有很好的分类效果，很多基于传统分类算法上的改进，使得这些算法越来越成熟。然而这些算法仍然不能将不确定性数据正确分类，于是将不确定性数据考虑到这些分类算法中，成为数据挖掘的研究热点。在支持向量机中，使用超球凸集数学模型来表示不确定性；在朴素贝叶斯理论中使用概率分布函数来表示不确定性；在决策树算法中使用分类模型中的置信度和似然函数来表达不确定性数据。

[1] WU X，KUMAR V，QUINLAN J R，et al.Top 10 algorithms in data mining[J].Knowledge & Information Systems，2007，14(1):1-37.

[2] 陈红梅.不确定性数据的分类研究[D].昆明：云南大学，2012:10-20.

[3] 丁世飞，齐丙娟，谭红艳.支持向量机理论与算法研究综述[J].电子科技大学学报，2011，40(1):2-10.

[4] 褚洪波.支持向量机理论与算法研究[J].和田师范专科学校学报:汉文综合版，2012(5):104-106.

[5] 范昕炜.支持向量机算法的研究及其应用[D].杭州：浙江大学，2003：1-20.

[6] 孙喜晨，贺仁亚，封举富.一种新的分类方法：属性均值聚类属性支持向量机(AMC-ASVM)[J].北京大学学报(自然科学版)，2007，43(1):82-84.

[7] 高华.基于聚类分块支持向量机的入侵检测算法[D].南京：南京理工大学，2007：1-20.

[8] YANG J，GUNN S.Iterative Constraints in Support Vector Classification with Uncertain Information [G].Constraint-Based Mining and Learning，2007：49.

[9] 李文进，熊小峰，毛伊敏.不确定性数据的超球支持向量机分类方法[J].计算机工程与设计，2015(7):1778-1783.

[10] 陈旋，刘健，冯新淇,等.基于朴素贝叶斯的差分隐私合成数据集发布算法[J].计算机科学，2015，42(1):236-238.

[11] REN J，LEE S D，CHEN X，et al.Naive Bayes Classification of Uncertain Data[C]// Ninth IEEE International Conference on Data Mining.IEEE Computer Society.2009:944-949.

[12] CHENG R，KALASHNIKOV D V，PRABHAKAR S J，et al.A fast decision tree learning algorithm[C]// National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference.2006.

[13] 马恺.不确定数据的朴素贝叶斯分类[J].洛阳师范学院学报，2016(2):20-21.

[14] 李芳，李一媛，王冲.不确定数据的决策树分类算法[J].计算机应用，2009，29(11):3092-3095.

[15] 徐洪文.关于“置信度”选取问题的讨论[J].大学化学，1998，13(5):46-47.

[16] 王家骥.求最大似然函数参数估值的一种对分法[J].中国科学院上海天文台年刊，1997(18):45-48.

[17] QIN B，XIA Y，LI F.DTU：A Decision Tree for Uncertain Data[C]// Advances in Knowledge Discovery and Data Mining，Pacific-Asia Conference，PAKDD 2009，Bangkok，Thailand.2009:4-15.

[18] TSANG S，KAO B，YIP K Y，et al.Decision Trees for Uncertain Data[C]// International Conference on Data Engineering，ICDE 2009 .2009:441-444.

[19] 张潮，李晨，王勇,等.uPOSC4.5:一种针对不确定数据的PU学习决策树算法[J].计算机研究与发展，2010，47(增刊1):316-324.

[20] 曹莹，苗启广，刘家辰,等.AdaBoost算法研究进展与展望[J].自动化学报，2013，39(6):745-758.

[21] 严信.基于云模型的模糊支持向量机分类方法研究[D].太原：太原理工大学，2013：10-20.

[22] 王超.三类不确定支持向量机及其应用[D].石家庄：河北大学，2013：1-20.

[23] 刘大雷.基于不确定贝叶斯算法在滑坡危险性预测的应用研究[D].南昌：江西理工大学，2015：1-20.

[24] 黄凯，张晓玲.贝叶斯方法在水环境系统不确定性分析中的应用述评[J].水电能源科学，2012(9):47-49.

Research on Classification Methods of Uncertain Data

SHENJieXUGaojianYANGYangLIShaowen

(School of Information and Computer, Anhui Agriculture University, Hefei 230039, China)

Traditional classification method has a successful application in various fields for the classification of determined knowledge; however, it cannot satisfy the demand for classification of complex uncertain knowledge. Hence, a series of classification methods for uncertain knowledge have emerged. Based on extensive research in this paper, it is proved that at present, classic classification algorithms and improved methods for classifying uncertain data have been greatly developed, such as the improved classification methods about Support Vector Machines, Naive Bayes and Decision Tree.

uncertain data; classification; support vector machines; Naive Bayes; Decision Tree

2017-03-23

国家自然科学基金项目“农业领域(茶学)云本体建模与方法研究”(31271615)

沈杰(1990 — )，女，合肥人，在读硕士研究生，研究方向为人工智能和数据挖掘。

TP301

A

1673-1980(2017)04-0096-04