论文创新实验DS证据理论与数据挖掘

1、本科创新实验报告实验题目：DS证据理论与数据挖掘学生：学号：专 业：计算机科学与技术武警国防牛指导教师： 评分（百分制）：2012 年 6 月 25 日目录本科创新实验报告 1实验目的 3实验容 3实验平台及语言 3实验原理 3实验步骤 7实验结果 8实验小结 12参考文献 13实验目的实现 D-S 证据理论基本算法，并验证其对不确定性的影响。随机赋予基本概 率分配 bpa 后求得 （ 质量函数 ） m, 进一步求出 （ 信任函数（置信函数） bel 和似然 函数 pls, 即概率上限和概率下限，将原来信息的不确定性转换成不确定区间的 形式进行 表达。实验容实现程序从文本文件、 excel 文

2、件和数据库中读写数据。二.D-S证据理论的基本算法1. 实现动态数组；2. 求指定集合的幕集；3. 求两集合的交并差集和子集；4. 为幕集中的每个集合给定一个基本概率分配 bpa, 将其标准化后作为质量函数；5. 求幕集中的每个集合的信任函数及似然函数，获得不确定区间。三.D-S证据理论与数据挖掘将证据理论引入数据挖掘领域中挖掘带不确定数据的关联规则。 这一模块的实验容正在进行当中。实验平台及语言平台：Microsoft Visual C+ 6.0语言：C+实验原理D-S证据理论Dempster -Shafer 证据理论也称 D-S 证据理论或“信念函数理论”（ TheD-S theory o

3、f evidenee ） , 起源于 Dempster 早期提出的由多值映射导出的所谓上限概率和下限概率， 由于该理论满足比概率论更弱的公理体系比道”概率推理理论中的更为直观、更容易获得，能够区分“不确定”与“不知的差异并能够处理由未知弓I起的不确定性具有较大的灵活性从而受到人们的重视。基本理论：设D是变量x所有可能取值的集合，且 D中的元素是互斥的，在任 一 时刻x都取且只能取D中的某一个元素为值，则称 D为x的样本空间， 也称 D为辨别框。在证据理论中，D的任何一个子集A都对应于一个关于x的命 题，称该命题为“ x的值在A中”引入三个函数：概率分配函数，信任函数及似然函数概念。1.概率分配

4、函数设D为样本空间，领域的命题都用 D的子集表示，则概率分配函数 定 义如下：定义1:设函数M 2d 0, 1,且满足M ()二0则称M是2d上的概率分配函数，M (A)称为A的基本概率数。 说明：(1)设样本空间D中有n个元素，贝u D中子集的个数为2n个，定义中的2 就是表示这些子集的。(2) 概率分配函数的作用是把 D的任意一个子集A都与一个映射为0, 1上的数M( A)。当A? D时，M( A)表示对相应命题的精确信任度。实 际上 就是对D的各个子集进行信任分配，M(A)表示分配给A的那一部分。 当A由 多个元素组成时，M(A)不包括对A的子集的精确信任度，而且也不 知道该对 它如何进

5、行分配。定义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 ()=0Bel (D)= P 甘厂门:(B) = 13 .似然函数定义4:似然函数Pl : 2d- 0, 1,且Pl (A)= 1-Bel (A)其中 A? D似然函数的含义：由于Bel(A)表示对A为真的信任程度，所以Bel(A)就表 示对非A为真，即A为假的信任程度，由此可推出 Pl (

6、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)由于

7、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为真不信任；另外，由于 BelA尸1-Pl(A)=1- 1=0,说明对A也不信任。所以A(0,1)表示对A无所知。A(1,1):由于Bel(A)=1,说明对A为真信任；另外，由于Bel(A尸1-Pl(

8、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.

9、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 合成公式可以综合不同专家或数据源的知识或数据， 随着技术的进步和人们对数据采集和处理技术理解的不断深入，不确定

10、性数据 ( un certain data ) 得到广泛的重视。这使得证据理论在专家系统、信息融合，情报分析、法 律案 件分析、多属性决策分析等领域中得到了广泛应用。基于证据理论的不确定性推理，大体可分为以下步骤：(1) 建立问题的识别集合(2) 给幕集定义基本概率分配函数(3) 计算所关心的子集X? ( 即 的子集 ) 的信任函数值Bel(X) 、似然函数值Pl(X)(4)由Bel(X)和Pls(X)推理演化，得出结论二 . 关联规则挖掘关联规则是形如 X-Y 的蕴涵式，其中且， X 和 Y 分别称为关联规则的先导 (LHS) 和后继 ( RHS) 。假设 I 是项的集合。给定一个事务集，其

11、中每个事务t 是 I 的非空子集，即 , 每一个交易都与一个唯一的标识符 TID 对应。关联规则在D 中的支持度是D 中事 务同时包含 X、 丫 的百分比，即概率；置信度是包含X 的事务中同时又包含丫 的 百分比，即条件概率。如果规则满足最小支持度阈值和最小置信度阈值，该关联规则是用户感兴趣。关联规则挖掘过程主要包含两个阶段：第一阶段：从给定的事务集中，找出所有频繁项集。频繁的意思是指某一项集出现的频 率相对于所有事务而言，必须达到指定值。项集出现的频率称为支持度，以一个 包含 A与 B 两个项集的 2-itemset 为例，若支持度大于等于所设定的最小支持度 阈值时，则A,B称为频繁项。一个

12、满足最小支持度的k-itemset ,则称为频繁k-项集(Frequent k-itemset)。算法并从Large k的项集中再产生 Large k+1 ,直到无法再找到更长的频繁项集为止。第二阶段：产生关联规则 (Association Rules) 。从频繁项集产生关联规则，是利用前 一步骤 的频繁k-项集来产生规则，在最小信赖度(Minimum Confidenee)的条件阈值下，若 一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。三 . 证据理论引入到关联规则挖掘中关联规则挖掘是数据库知识发现或数据挖掘中一种应用广泛的算法。它 最初在文献 () 中提出，其基本思想是在数据项中

13、发现重要的和有趣的关联，一 些项在一个事务中出现将暗示另一些项会在同一个事务中出现。 从关联规则挖掘产生的输出是一些规则，这些规则满足用户指定的最小支持度和置信度。关联规则挖掘广泛应用于MB(购物篮分析)，这里的数据集是一个事务记录的集合，每条记录包含顾客在一次事务中购买的所有项的清单。已有的大多数关联规则挖掘算法所考虑的数据集都有一个假设前提， 它们是确切的或始终如一的，并且不含模棱两可的意义。然而，对于真实世界的应用， 数据集通常决不会是完美的。数据集通常包含一些不确定性，特别是不完备性和 矛盾。分布式信息环境就是例子，它的数据集从不同的源产生和收集， 而且每个 源可能有不项之间的相互关系

14、会呈现不同并导致不确定项关系。DS 证据推理理论被用于产生满足不确定性条件下预定义支持度和置信度的bpa、 Bel 和 PI ，用一个似香农的总的不确定性度量来反 映不确定程度。实验步骤实验步骤1. 从不同数据文件中读取数据；2. 实现动态数组；3. 求两集合的交、并、差集和子集；4. 实现DS 基本算法；5. 利用DS 理论挖掘关联规则。实验的算法1. 从不同数据文件中读取数据( 以文本文档为例 ) ；1(1 入：文本文件名) 23 (输( 程序所在文件夹与文本文档文件夹为同一文件夹 )；从文件中读取一个字符；若字符为数字跳到过程( 4), 若字符为结束符号结束程序，否则跳到过程(6)；(4

15、) 继续读取下一个字符，若字符依然为数字，重复过程(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) in t*p=n ewb;(5) 输出：动态产生的数组。3. 求两集合的交、并、差集和子集；交集：(1) 自动生成两个集合a ， b

16、；(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 中

17、元素全部 被扫描。差集：（ 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 进行标准化

18、，得到质量函数m;4 ） 根据 m 求出 bel 和 pl;5 ） 输出：不确定区间。5. 利用 DS 理论挖掘关联规则。1 ）输入：最小支持度和置信度，事务集；2 ）根 据含有不确定信息的事务集创建问题的识别框架并给定基本概率分配函数bpa；3 ）结合bpa和事务集将不确定性事务集转换为证据集；4 ）定 义衡量不确定度的量并求出识别框架中每个命题被证据集支持的程度si；5 ）根据si 求出相应的置信度和支持度；6 ）输出满足最小支持度和置信度的关联规则。实验结果D-S 证据理论1. 读取txt 文件；程序能将文本文件原模原样的读出来并显示程序自动分类文本文件的数据，将字数和字符分开显示2.求

19、两集合的交并差集;输入：第一个集合为：2, 5dg , 89, de 第二个集合为：9999, 2 , de, n qig, lg, aaaaaaa2, 38结果：两集合的交集为：2, de 两集合的并集为：2, 5dg , 89, de, 9999, nq ig, 1g, aaaaaaa2, 38两集合的差集为：5dg, 89 输入：第一个集合为：564657, 8413 ,发,25 第二个集合为：发，格拉斯哥,dg, 8413 两集合的交集为：8413，发结果：两集合的并集为：564657, 8413 ,发,25,格拉斯哥,dg 两集合的差集为：564657, 25 3.基于以上条件，求集

20、合的幕集并给幕集中的每个集合分配一个概率，将其标准化后得到质量函数； -5学习 &礼开站曲昌过-,2I J回上图表示输入2得到2的幕集的元素分别为、2、1、1 2 并且分别给他们赋 值的概率为：|=0.27532, |2|=0.394446, |1|=0.301683, |1 2|=0.0285506上图表示输入3得到3的幕集的元素分别为、3、2、2 3 、1、1 3 、1 2 、1 2 3 并且分别给他们赋值的概率为：|=0.160501, |3|=0.0341196, |2|=0.0659064, |2 3|=0.0920301|1|=0.223801,|1 3|=0.122018

21、,|1 2|=0.113228,|1 2 3|=0.1883954.由质量函数求其信任函数及似然函数上面是基于前面的改进，0为结束符号，表示 1的信任函数值为0.579967.2的似然函数值为0.420033.上图表示表示集合 1 2 3的信任函数值为1.2 3的似然函数值为0.783251.实验小结1 .阅读材料心得体会本次创新实验我了解了一种新的理论一一 DS证据理论并且介绍了 DS证据推 理 几个基本概念的物理意义它可以用于处理证据影响一类假设的情况，并准备将 其应用于不确定性数据质量检测。此外，通过这次实验我还学习到了数据挖掘中最基本的方法一一关联规则挖 掘， 其目标是把数据项之间的关

22、联从数据集中挖掘出来。 如何把关联规则挖掘与 实际问 题紧密结合，是数据挖掘的一个重要研究方向。2 .实验中的心得体会实验过程中我发现自己的编程能力有待提高，遇到很多问题，如最开始使用了指针实现了实现动态数组，但是到后面发现以向量的方式会简便得多，也让我发现很多事情只是你不去做而已，真正的认真的去钻研后，会发现其实它并不像想象中的那样困难，而且我也终于明白最难的地方不是编程而是思想。总之，这次创新实验让我更加理解计算机科学与技术专业的实际意义。本实验暂时只实现了 DS证据理论的基本方法，目前暂时还不能够进行与文件关联及数据的融合，把 DS证据理论与数据库等连接起来后，将里面的数据进行分类并将数据进行融合便可以建立起一个不确定性的推理模型，给其中数据分配概率后便可以求得其概率的上限与下限，这样这个实验就会变得更具有实际意义了，在接下来的一年里我会以创新实验为基础,更加认真的去做出一个优秀的毕业设计。参考文献1 R. Agrawal, T. Imielinski, and A. Swa