ds证据理论

ds证据理论

陆地动物-慢走丝

本科创新实验报告

实验题目：DS证据理论与数据挖掘

学生：________________________

学号：___________________

专业：计算机科学与技术武警国防生

指导教师：___________________________

评分（百分制）：______________________

2012年6月25日

目录

本科创新实验报告..............................1

实验目的.....................................3

实验容.......................................3

实验平台及语言...............................3

实验原理.....................................3

实验步骤.....................................7

实验结果.....................................8

实验小结....................................12

参考文献....................................13

实验目的

实现D-S证据理论基本算法，并验证其对不确定性的影响。随机赋予基本概率分

配bpa后求得（质量函数）m,进一步求出（信任函数（置信函数））bel和似然函

数pls,即概率上限和概率下限，将原来信息的不确定性转换成不确定区间的形式进行

表达。

实验容

实现程序从文本文件、excel文件和数据库中读写数据。

二.D-S证据理论的基本算法

1.实现动态数组；

2.求指定集合的幕集；

3.求两集合的交并差集和子集；

4.为幕集中的每个集合给定一个基本概率分配bpa,将其标准化后作为质量函

数；

5.求幕集中的每个集合的信任函数及似然函数，获得不确定区间。

三.D-S证据理论与数据挖掘

将证据理论引入数据挖掘领域中挖掘带不确定数据的关联规则。这一模块的实验

容正在进行当中。

实验平台及语言

平台：MicrosoftVisualC++6.0

语言：C++

实验原理

D-S证据理论

Dempster-Shafer证据理论也称D-S证据理论或“信念函数理论”（The

D-Stheoryofevidenee）,起源于Dempster早期提出的由多值映射导出

的所谓上限概率和下限概率，由于该理论满足比概率论更弱的公理体系比

概率推理理论中的更为直观、更容易获得，能够区分“不确定”与“不知道”

的差异并能够处理由未知引起的不确定性，具有较大的灵活性从而受到人们的

重视。

基本理论：

设D是变量x所有可能取值的集合，且D中的元素是互斥的，在任一

时刻x都取且只能取D中的某一个元素为值，则称D为x的样本空间，也称

D为辨别框。在证据理论中，D的任何一个子集A都对应于一个关于x的命

题，称该命题为“x的值在A中”引入三个函数：概率分配函数，信任函数

及似然函数概念。

1.概率分配函数

设D为样本空间，领域的命题都用D的子集表示，则概率分配函数定

义如下：

定义1:设函数M2D—［0，1］，且满足

M(①)=0

则称M是2D上的概率分配函数，M(A)称为A的基本概率数。

说明：

(1)设样本空间D中有n个元素，贝UD中子集的个数为2n个，定义中的2

就是表示这些子集的。

(2)概率分配函数的作用是把D的任意一个子集A都与一个映射为］0，

1］上的数M(A)。当A?D时，M(A)表示对相应命题的精确信任度。实际上

就是对D的各个子集进行信任分配，M(A)表示分配给A的那一部分。当A由

多个元素组成时，M(A)不包括对A的子集的精确信任度，而且也不知道该对

它如何进行分配。

定义2:若A?D且有M(A)工0,称A为M的一个焦元。

2.信任函数

定义3:命题的信任函数Bel:2D-［0，1］，且对所有的A?D有

Bel(A)

其中2D表示D的所有子集。

*Bel函数又称为下限函数，Bel(A)表示对命题A为真的信任程度。

由信任函数及概率分配函数的定义推出：

Bel(①)=M(①)=0

Bel(D)=P甘匚门抽(B)］=1

3.似然函数

定义4:似然函数Pl:2D-］0，1］，且

Pl(A)=1-Bel(「A)其中A?D

似然函数的含义：由于Bel(A)表示对A为真的信任程度，所以Bel(「A)就表

示对非A为真，即A为假的信任程度，由此可推出Pl(A)表示对A为非假的

信任程度。

*似然函数又称为不可驳斥函数或上限函数。

推广到一般情况可得出：

Pl(A)=£上门丘丰

证明如下:

•••PI(A)—禹丽毛/(刃|=1-Bel(「A)-E冲

=1-(BeI(「A)+L川上」l)

=i-EZ匹I

=0

•PI(A=门月革e"(B)

4.信任函数与似然函数的关系

PI(A)>Bel(A)

证明：

•••Bel(A)十Bel厂厲=丽匸严(恥|亠险「严心

(E)

•Pl(A)—Bel(A)=1—Bel(「A)—Bel(A)

=1—(Bel(「A)+Bel(A))

>0

•Pl(A)>Bel(A)

由于Bel(A)表示对A为真的信任程度，Pl(A)表示对A为非假的信任程度，因

此可分别称Bel(A)和Pl(A)为对A信任程度的下限与上限，记为

A(Bel(A),Pl(A))

例如：

A(0,0):由于Bel(A)=0，说明对A为真不信任；另外，由于Bel(「A)=1-Pl(A)=1-

0=1，说明对」A信任。所以A(0,0)表示A为假。

A(0,1):由于Bel(A)=0，说明对A为真不信任;另外，由于Bel「A)=1-Pl(A)=1-

1=0，说明对「A也不信任。所以A(0,1)表示对A一无所知。

A(1,1):由于Bel(A)=1,说明对A为真信任；另外，由于Bel(「A)=

1-Pl(A)=1-1=0,说明对「A不信任。所以A(1,1)表示A为真。

A(0.25,1).由于Bel(A)=0.25，说明对A为真有一定程度的信任，信任度为

0.25;另外，由于Bel(「A)=1-Pl(A)=0,说明对？A不信任。所以A(0.25,1)表示对A

为真有0.25的信任度。

A(0,0.85).由于Bel(A)=0，而Bel(「A)=1-Pl(A)=1-0.85=0.15,所以

A(0,0.85)表示对A为假有一定程度的信任，信仟度为0.15。

A(0.25,0.85):由于Bel(A)=0.25,说明对A为真有0.25的信任度；由于

Bel(?A)=1-0.85=O.15，说明对A为假有0.15的信任度。所以A(0.25,0.85)表示对

A为真的信任度比对A为假的信任度稍高一些。

在上面的讨论中已经指出,Bel(A)表示对A为真的信任程度;Bel(「A)表示对「A,

即A为假的信任程度;Pl(A)表示对A为非假的信任程度。那么，

Pl(A)-Bel(A)是什么含义呢？它表示对A不知道的程度，即既非对A信任又

非不信任的那部分。在上例的A(0.25,0.85)中,0.85-0.25=0.60就表示了对A不

知道的程度。

Dempster合成公式可以综合不同专家或数据源的知识或数据，随着技术的进

步和人们对数据采集和处理技术理解的不断深入，不确定性数据(uncertain

data)得到广泛的重视。这使得证据理论在专家系统、信息融合，情报分析、法律案

件分析、多属性决策分析等领域中得到了广泛应用。

基于证据理论的不确定性推理，大体可分为以下步骤：

(1)建立问题的识别集合

(2)给幕集定义基本概率分配函数

(3)计算所关心的子集X€(即的子集)的信任函数值Bel(X)、似然函数值Pl(X)

(4)由Bel(X)和Pls(X)推理演化，得出结论

二.关联规则挖掘

关联规则是形如X-Y的蕴涵式，其中且，X和Y分别称为关联规则的先导(LHS)

和后继(RHS)。

假设I是项的集合。给定一个事务集，其中每个事务t是I的非空子集，即,每一

个交易都与一个唯一的标识符TID对应。关联规则在D中的支持度是D中事务同时

包含X、丫的百分比，即概率；置信度是包含X的事务中同时又包含丫的百分比，即

条件概率。如果规则满足最小支持度阈值和最小置信度阈值，该关联规则是用户感兴

趣。

关联规则挖掘过程主要包含两个阶段：

第一阶段：

从给定的事务集中，找出所有频繁项集。频繁的意思是指某一项集出现的频率相

对于所有事务而言，必须达到指定值。项集出现的频率称为支持度，以一个包含A

与B两个项集的2-itemset为例，若支持度大于等于所设定的最小支持度阈值时，则

｛A,B｝称为频繁项。一个满足最小支持度的k-itemset，则称为频繁

k-项集(Frequentk-itemset)。算法并从Largek的项集中再产生Largek+1，

直到无法再找到更长的频繁项集为止。

第二阶段：

产生关联规则(AssociationRules)。从频繁项集产生关联规则，是利用前一步骤

的频繁k-项集来产生规则，在最小信赖度(MinimumConfidenee)的条件阈值下，若

一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。

三.证据理论引入到关联规则挖掘中

关联规则挖掘是数据库知识发现或数据挖掘中一种应用广泛的算法。它最初

在文献()中提出，其基本思想是在数据项中发现重要的和有趣的关联，一些项在一个

事务中出现将暗示另一些项会在同一个事务中出现。从关联规则挖掘

产生的输出是一些规则，这些规则满足用户指定的最小支持度和置信度。关联规则挖

掘广泛应用于MB(购物篮分析)，这里的数据集是一个事务记录的集合，每

条记录包含顾客在一次事务中购买的所有项的清单。

已有的大多数关联规则挖掘算法所考虑的数据集都有一个假设前提，它们是

确切的或始终如一的，并且不含模棱两可的意义。然而，对于真实世界的应用，数据

集通常决不会是完美的。数据集通常包含一些不确定性，特别是不完备性和矛盾。分

布式信息环境就是例子，它的数据集从不同的源产生和收集，而且每个源可能有不

同的约束。这会导致项之间不同的相互关系强加于数据集中。因此，项之间的相互关

系会呈现不同并导致不确定项关系。

DS证据推理理论被用于产生满足不确定性条件下预定义支持度和置信度的

关联规则。基于原有的bpa、Bel和PI，用一个似香农的总的不确定性度量来反映不

确定性条件下的支持度和置信度，以便获得所考虑的数据集中隐藏的总的不确定程

度。

实验步骤

一.实验步骤

1.从不同数据文件中读取数据；

2.实现动态数组；

3.求两集合的交、并、差集和子集；

4.实现DS基本算法；

5.利用DS理论挖掘关联规则。

二.实验的算法

1.从不同数据文件中读取数据(以文本文档为例)；

(1)输

入：文本文件名(程序所在文件夹与文本文档文件夹为同一文件夹)；

(2)从文件中读取一个字符；

(3)若字符为数字跳到过程(4),若字符为结束符号结束程序，否则跳到过程

(6)；

(4)继续读取下一个字符，若字符依然为数字，重复过程(4);

(5)把整个数字串存储到实型数组；并且返回过程(3)；

(6)继续读取下一个字符，若字符依然为字符，重复过程(6)；

(7)把整个字符串存储到字符串数组；并且返回过程(3)；

(8)输入：文本中数据。

2.实现动态数组；

(1)输入：控制动态数组动态大小的数值a；

(2)若a>0，则执行过程(3)，否则执行过程(4);

(3)b=b*2;a=a-1,返回过程(2);

(4)int*p=new[b];

(5)输出：动态产生的数组。

3.求两集合的交、并、差集和子集；

交集：

(1)自动生成两个集合a，b；

(2)扫描集合a的一个元素；

(3)扫描集合b的一个元素，如果两元素相等，将元素存入交集，并且跳回步骤

（2）,否则重复步骤（3）直至b中元素全部被扫描；

（4）跳回步骤（2）直至a中所有元素都被扫描。并集：

（1）自动生成两个长度为n的集合a，b,定义k=0；

（2）复制集合a的所有元素存入并集；

（3）扫描b的一个元素；

（4）扫描a的一个元素，如果两元素不相等，k赋值为k+1;重复步骤（4）直至

a中所有元素都被扫描；

（5）如果kvn,将b中这个元素存入并集，反回步骤（3）直至b中元素全部被扫

描。

差集：

（1）自动生成两个长度为n的集合a，b,定义k=0；

（2）扫描a的一个元素；

（3）扫描b的一个元素，如果两元素相等，k赋值为k+1;重复步骤（4）直至b

中所有元素都被扫描；

（4）如果k==0，将a中这个元素存入差集，反回步骤（2）直至a中元素全部被

扫描。

输入：集合的运算结果。

4.实现DS基本算法；

（1）输入：样本集合；

（2）求样本幕集并给所有集合赋值一个［0,1］的随机数作为基本概率分配函数，

同时求随机数总和sum;

（3）将样本幕集中每个集合的bpa除以sum进行标准化，得到质量函数m;

（4）根据m求出bel和pl;

（5）输出：不确定区间。

5.利用DS理论挖掘关联规则。

（1）输入：最小支持度和置信度，事务集；

（2）根据含有不确定信息的事务集创建问题的识别框架并给定基本概率分配函数

bpa；

（3）结合bpa和事务集将不确定性事务集转换为证据集；

（4）定义衡量不确定度的量并求出识别框架中每个命题被证据集支持的程度si；

（5）根据si求出相应的置信度和支持度；

（6）输出满足最小支持度和置信度的关联规则。

实验结果

一.D-S证据理论

1.读取txt文件；

程序能将文本文件原模原样的读出来并显示

程序自动分类文本文件的数据，将字数和字符分开显示

2.求两集合的交并差集；

输入：

第一个集合为：{2,5dg,89,de}

第二个集合为：{9999,2,de,nqig,lg,aaaaaaa2,38}

结果：

两集合的交集为：{2,de}

两集合的并集为：{2,5dg,89,de,9999,nqig,lg,aaaaaaa2,38}

两集合的差集为：{5dg,89}

输入：

第一个集合为：{564657,8413,发,25}

第二个集合为：{发，格拉斯哥,dg,8413}两集合的交集为：{8413,发}

结果：

两集合的并集为：{564657,8413,发,25,格拉斯哥,dg}

两集合的差集为：{564657,25}

3.基于以上条件，求集合的幕集并给幕集中的每个集合分配一个概率，将其标准

化后得到质量函数；

■-5学习&礼幵站曲昌过-,2IJ回■

墙够狡回车结束=备:个幕集是

第3个幫集足

第:个幕集是

2

H.

1

12

上图表示输入2得到2的幕集的元素分别为{}、{2}、{1}、{12}并且分别给他们赋

值的概率为：

|{}|=0.27532,|{2}|=0.394446,|{1}|=0.301683,|{12}|=0.0285506

上图表示输入3得到3的幕集的元素分别为{}、{3}、{2}、{23}、{1}、

{13}、{12}、{123}

并且分别给他们赋值的概率为：

|{}|=0.160501,|{3}|=0.0341196,|{2}|=0.0659064,|{23}|=0.0920301，

|{1}|=0.223801,|{13}|=0.122018,|{12}|=0.113228,|{123}|=0.188395。

4.由质量函数求其信任函数及似然函数

上面是基于前面的改进，0为结束符号，表示｛1｝的信任函数值为0.579967.

｛2｝的似然函数值为0.420033.

上图表示表示集合｛123｝的信任函数值为1.

｛23｝的似然函数值为0.783251.

实验小结

一.阅读材料心得体会

本次创新实验我了解了一种新的理论一一DS证据理论并且介绍了DS证据推理

几个基本概念的物理意义它可以用于处理证据影响一类假设的情况，并准备将其应

用于不确定性数据质量检测。

此外，通过这次实验我还学习到了数据挖掘中最基本的方法——关联规则挖掘，

其目标是把数据项之间的关联从数据集中挖掘出来。如何把关联规则挖掘与实际问

题紧密结合，是数据挖掘的一个重要研究方向。

二.实验中的心得体会

实验过程中我发现自己的编程能力有待提高，遇到很多问题，如最开始使用了指

针实现了实现动态数组，但是到后面发现以向量的方式会简便得多，也让我发现很多

事情只是你不去做而已，真正的认真的去钻研后，会发现其实它并不像想象中的那样

困难，而且我也终于明白最难的地方不是编程而是思想。总之，这

次创新实验让我更加理解计算机科学与技术专业的实际意义。

本实验暂时只实现了DS证据理论的基本方法，目前暂时还不能够进行与文件关

联及数据的融合，把DS证据理论与数据库等连接起来后，将里面的数据进行分类并

将数据进行融合便可以建立起一个不确定性的推理模型，给其中数据分

配概率后便可以求得其概率的上限与下限，这样这个实验就会变得更具有实际意

义了，在接下来的一年里我会以创新实验为基础,

更加认真的去做出一个优秀的

毕业设计。

参考文献

[1]l,nski,,“MiningAssociationRules

BetweenSetsofItemsinLargeDatabases,”CMSIGMOD

ConferenceonManagementofData,pp.207-216,1993.

[2]欧阳志宏，董霖，钟俊华编著MFC程序设计轻松入门人民邮电，2009

[3]曾凡锋，苗雨编著MFC编程技巧与例详解：清华大学，2008

[4]肖人彬等.相关证据合成方法的研究.模式识别与人工智能，1993,6(3):227-234

⑸周傲英，金澈清，王国仁，建中.不确定性数据管理技术研究综述.计算机学报，

2009(1)

⑹邬永革.证据理论的推广及其在多传感器信息融合中的应用：[硕士论文].华东工学

院，1992

[7]烈彪，海鹏，周亚峰.Web日志挖掘中数据预处理方法的研究.计算机技术

与发展，2007，17(7):46—52.

[8]候亚丽，袁方.Web日志挖掘中的数据预处理技术大学学报，2005,25(2):202

—205.

[9]娥，秋红，宣慧玉Web使用模式研究中的数据挖掘.计算机应用研究，

2001(3):80—83.

[10]./view/

[11]./view/

[12].docin./

[13]./view/

[14]./view/