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

1、本科创新实验报告实验题目：DS证据理论与数据挖掘 学生姓名：杨胜达 学 号：20091060120 专 业：计算机科学与技术武警国防生 指导教师：肖清 评分（百分制）： 2012 年 6 月 25 日目录本科创新实验报告1实验目的3实验内容3实验平台及语言3实验原理3实验步骤7实验结果8实验小结12参考文献12实验目的实现 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证据理论或“信念函数理论”(The D-S theory of e

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

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

5、的一个焦元。 2. 信任函数定义3:命题的信任函数Bel：2D0，1，且对所有的AD 有Bel(A）BAM（B） 其中2D表示D的所有子集。*Bel函数又称为下限函数，Bel（A）表示对命题A为真的信任程度。由信任函数及概率分配函数的定义推出：Bel（）M（）0Bel（D）BDM（B）1 3. 似然函数定义4: 似然函数Pl：2D0，1，且Pl（A）1Bel（A） 其中AD似然函数的含义：由于Bel(A)表示对A为真的信任程度，所以Bel(A)就表示对非A为真，即A为假的信任程度，由此可推出Pl（A）表示对A为非假的信任程度。*似然函数又称为不可驳斥函数或上限函数。推广到一般情况可得出：Pl(

6、A)= AB M(B)证明如下：Pl(A) AB M(B) 1-Bel(A)-AB M(B) 1-(Bel(A)+AB M(B) 1-(CA M(C)+AB M(B) 1-ED M(E) 0Pl（A）ABM（B） 4. 信任函数与似然函数的关系Pl（A）Bel（A） 证明： Bel（A）十Bel（A）BAM（B）CAM（C）EDM（E）1Pl（A）Bel（A）1Bel（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(Be

7、l(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(A)=1-1=0,说明对A不信任。所以A(1,1)表示A为真。 A(0.25,1).由于Bel(A)= 0.25，说明对A为真有一定程度的信任，信任度为0.25;

8、另外，由于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(

9、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）建

10、立问题的识别集合Q（2）给幂集 定义基本概率分配函数 （3）计算所关心的子集X （即Q的子集）的信任函数值Bel(X)、似然函数值Pl(X) （4）由Bel(X)和Pls(X)推理演化，得出结论二 关联规则挖掘关联规则是形如XY的蕴涵式，其中且， X和Y分别称为关联规则的先导(LHS)和后继(RHS) 。假设I是项的集合。给定一个事务集，其中每个事务t是I的非空子集，即，每一个交易都与一个唯一的标识符TID对应。关联规则在D中的支持度是D中事务同时包含X、Y的百分比，即概率；置信度是包含X的事务中同时又包含Y的百分比，即条件概率。如果规则满足最小支持度阈值和最小置信度阈值，该关联规则是用户感兴

11、趣。 关联规则挖掘过程主要包含两个阶段：第一阶段：从给定的事务集中，找出所有频繁项集。频繁的意思是指某一项集出现的频率相对于所有事务而言，必须达到指定值。项集出现的频率称为支持度，以一个包含A与B两个项集的2-itemset为例，若支持度大于等于所设定的最小支持度阈值时，则A,B称为频繁项。一个满足最小支持度的k-itemset，则称为频繁k-项集(Frequent k-itemset)。算法并从Large k的项集中再产生Large k+1，直到无法再找到更长的频繁项集为止。第二阶段：产生关联规则(Association Rules)。从频繁项集产生关联规则，是利用前一步骤的频繁k-项集来产

12、生规则，在最小信赖度(Minimum Confidence)的条件阈值下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。三 证据理论引入到关联规则挖掘中关联规则挖掘是数据库知识发现或数据挖掘中一种应用广泛的算法。它最初在文献（）中提出，其基本思想是在数据项中发现重要的和有趣的关联，一些项在一个事务中出现将暗示另一些项会在同一个事务中出现。从关联规则挖掘产生的输出是一些规则，这些规则满足用户指定的最小支持度和置信度。关联规则挖掘广泛应用于MBA（购物篮分析），这里的数据集是一个事务记录的集合，每条记录包含顾客在一次事务中购买的所有项的清单。已有的大多数关联规则挖掘算法所考虑的数据集都

13、有一个假设前提，它们是确切的或始终如一的，并且不含模棱两可的意义。然而，对于真实世界的应用，数据集通常决不会是完美的。数据集通常包含一些不确定性，特别是不完备性和矛盾。分布式信息环境就是例子，它的数据集从不同的源产生和收集，而且每个源可能有不同的约束。这会导致项之间不同的相互关系强加于数据集中。因此，项之间的相互关系会呈现不同并导致不确定项关系。DS证据推理理论被用于产生满足不确定性条件下预定义支持度和置信度的关联规则。基于原有的bpa、Bel和Pl，用一个似香农的总的不确定性度量来反映不确定性条件下的支持度和置信度，以便获得所考虑的数据集中隐藏的总的不确定程度。实验步骤一实验步骤1. 从不同

14、数据文件中读取数据；2. 实现动态数组；3. 求两集合的交、并、差集和子集；4. 实现DS基本算法；5. 利用DS理论挖掘关联规则。二实验的算法1. 从不同数据文件中读取数据（以文本文档为例）；（1） 输入：文本文件名（程序所在文件夹与文本文档文件夹为同一文件夹）；（2） 从文件中读取一个字符；（3） 若字符为数字跳到过程（4），若字符为结束符号结束程序，否则跳到过程（6）；（4） 继续读取下一个字符，若字符依然为数字，重复过程（4）；（5） 把整个数字串存储到实型数组；并且返回过程（3）；（6） 继续读取下一个字符，若字符依然为字符，重复过程（6）；（7） 把整个字符串存储到字符串数组；并且

15、返回过程（3）；（8） 输入：文本中数据。2. 实现动态数组；（1） 输入：控制动态数组动态大小的数值a；（2） 若a0，则执行过程（3），否则执行过程（4）；（3） b=b*2;a=a-1,返回过程（2）;（4） int*p=newb;（5） 输出：动态产生的数组。3. 求两集合的交、并、差集和子集；交集：（1） 自动生成两个集合a，b；（2） 扫描集合a的一个元素；（3） 扫描集合b的一个元素，如果两元素相等，将元素存入交集，并且跳回步骤（2），否则重复步骤（3）直至b中元素全部被扫描；（4） 跳回步骤（2）直至a中所有元素都被扫描。并集：（1） 自动生成两个长度为n的集合a，b，定义k=

16、0；（2） 复制集合a的所有元素存入并集；（3） 扫描b的一个元素；（4） 扫描a的一个元素，如果两元素不相等，k赋值为k+1；重复步骤（4）直至a中所有元素都被扫描；（5） 如果kn，将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） 求样本幂

17、集并给所有集合赋值一个0,1的随机数作为基本概率分配函数，同时求随机数总和sum;（3） 将样本幂集中每个集合的bpa除以sum进行标准化，得到质量函数m;（4） 根据m求出bel和pl;（5） 输出：不确定区间。5. 利用DS理论挖掘关联规则。（1） 输入：最小支持度和置信度，事务集；（2） 根据含有不确定信息的事务集创建问题的识别框架并给定基本概率分配函数bpa；（3） 结合bpa和事务集将不确定性事务集转换为证据集；（4） 定义衡量不确定度的量并求出识别框架中每个命题被证据集支持的程度sl；（5） 根据sl求出相应的置信度和支持度；（6） 输出满足最小支持度和置信度的关联规则。实验结果一

18、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, 发结果：

19、两集合的并集为：564657, 8413 , 发, 25, 格拉斯哥, dg两集合的差集为：564657, 253. 基于以上条件，求集合的幂集并给幂集中的每个集合分配一个概率，将其标准化后得到质量函数；上图表示输入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

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

21、了数据挖掘中最基本的方法关联规则挖掘，其目标是把数据项之间的关联从数据集中挖掘出来。如何把关联规则挖掘与实际问题紧密结合，是数据挖掘的一个重要研究方向。二实验中的心得体会实验过程中我发现自己的编程能力有待提高，遇到很多问题，如最开始使用了指针实现了实现动态数组，但是到后面发现以向量的方式会简便得多，也让我发现很多事情只是你不去做而已，真正的认真的去钻研后，会发现其实它并不像想象中的那样困难，而且我也终于明白最难的地方不是编程而是思想。总之，这次创新实验让我更加理解计算机科学与技术专业的实际意义。本实验暂时只实现了DS证据理论的基本方法，目前暂时还不能够进行与文件关联及数据的融合，把DS证据理论与数据库等连接起来后，将里面的数据进行分