《学年论文 创新实验 DS证据理论与数据挖掘》由会员分享，可在线阅读，更多相关《学年论文 创新实验 DS证据理论与数据挖掘（13页珍藏版）》请在金锄头文库上搜索。
1、本科创新实验报告实验题目：DS证据理论与数据挖掘 学生姓名：杨胜达 学 号：20091060120 专 业：计算机科学与技术武警国防生 指导教师：肖清 评分（百分制）： 2012 年 6 月 25 日13目录本科创新实验报告1实验目的3实验内容3实验平台及语言3实验原理3实验步骤7实验结果8实验小结12参考文献12实验目的实现 D-S证据理论基本算法，并验证其对不确定性的影响。随机赋予基本概率分配bpa后求得 (质量函数)m，进一步求出(信任函数(置信函数)bel和似然函数pls,即概率上限和概率下限，将原来信息的不确定性转换成不确定区间的形式进行表达。实验内容一 实现程序从文本文件、exce
2、l文件和数据库中读写数据。二 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
3、 evidence) ,起源于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
5、为M的一个焦元。 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为非假的信任程度。*似然函数又称为不可驳斥函数或上限函数。推广到一般情况可得出：P
6、l(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(
7、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(A)=1-1=0,说明对A不信任。所以A(1,1)表示A为真。 A(0.25,1).由于Bel(A)= 0.25，说明对A为真有一定程度的信任，信任度为0.2
8、5;另外，由于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为真的信任程度;Be
9、l(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） 把整个字符串存储到字符串数组；并且返回过程（3）；（8） 输入：文本中数据。2. 实现动态数组；（1） 输入：控制动态数组动态大小的数值a；（2） 若a0，则执行过程（3），否则执行过程（4）；（3） b=b*2;a=a-1,返回过程（2）;（4） int*p=newb;（5） 输出：动态产生的数组
