論文創(chuàng)新實(shí)驗(yàn)DS證據(jù)理論與數(shù)據(jù)挖掘

1、本科創(chuàng)新實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：DS證據(jù)理論與數(shù)據(jù)挖掘?qū)W生：學(xué)號(hào)：專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)武警國(guó)防牛指導(dǎo)教師： 評(píng)分（百分制）：2012 年 6 月 25 日目錄本科創(chuàng)新實(shí)驗(yàn)報(bào)告 1實(shí)驗(yàn)?zāi)康?3實(shí)驗(yàn)容 3實(shí)驗(yàn)平臺(tái)及語(yǔ)言 3實(shí)驗(yàn)原理 3實(shí)驗(yàn)步驟 7實(shí)驗(yàn)結(jié)果 8實(shí)驗(yàn)小結(jié) 12參考文獻(xiàn) 13實(shí)驗(yàn)?zāi)康膶?shí)現(xiàn) D-S 證據(jù)理論基本算法，并驗(yàn)證其對(duì)不確定性的影響。隨機(jī)賦予基本概 率分配 bpa 后求得 （ 質(zhì)量函數(shù) ） m, 進(jìn)一步求出 （ 信任函數(shù)（置信函數(shù)） bel 和似然 函數(shù) pls, 即概率上限和概率下限，將原來(lái)信息的不確定性轉(zhuǎn)換成不確定區(qū)間的 形式進(jìn)行 表達(dá)。實(shí)驗(yàn)容實(shí)現(xiàn)程序從文本文件、 excel 文

2、件和數(shù)據(jù)庫(kù)中讀寫數(shù)據(jù)。二.D-S證據(jù)理論的基本算法1. 實(shí)現(xiàn)動(dòng)態(tài)數(shù)組；2. 求指定集合的幕集；3. 求兩集合的交并差集和子集；4. 為幕集中的每個(gè)集合給定一個(gè)基本概率分配 bpa, 將其標(biāo)準(zhǔn)化后作為質(zhì)量函數(shù)；5. 求幕集中的每個(gè)集合的信任函數(shù)及似然函數(shù)，獲得不確定區(qū)間。三.D-S證據(jù)理論與數(shù)據(jù)挖掘?qū)⒆C據(jù)理論引入數(shù)據(jù)挖掘領(lǐng)域中挖掘帶不確定數(shù)據(jù)的關(guān)聯(lián)規(guī)則。 這一模塊的實(shí)驗(yàn)容正在進(jìn)行當(dāng)中。實(shí)驗(yàn)平臺(tái)及語(yǔ)言平臺(tái)：Microsoft Visual C+ 6.0語(yǔ)言：C+實(shí)驗(yàn)原理D-S證據(jù)理論Dempster -Shafer 證據(jù)理論也稱 D-S 證據(jù)理論或“信念函數(shù)理論”（ TheD-S theory o

3、f evidenee ） , 起源于 Dempster 早期提出的由多值映射導(dǎo)出的所謂上限概率和下限概率， 由于該理論滿足比概率論更弱的公理體系比道”概率推理理論中的更為直觀、更容易獲得，能夠區(qū)分“不確定”與“不知的差異并能夠處理由未知弓I起的不確定性具有較大的靈活性從而受到人們的重視。基本理論：設(shè)D是變量x所有可能取值的集合，且 D中的元素是互斥的，在任 一 時(shí)刻x都取且只能取D中的某一個(gè)元素為值，則稱 D為x的樣本空間， 也稱 D為辨別框。在證據(jù)理論中，D的任何一個(gè)子集A都對(duì)應(yīng)于一個(gè)關(guān)于x的命 題，稱該命題為“ x的值在A中”引入三個(gè)函數(shù)：概率分配函數(shù)，信任函數(shù)及似然函數(shù)概念。1.概率分配

4、函數(shù)設(shè)D為樣本空間，領(lǐng)域的命題都用 D的子集表示，則概率分配函數(shù) 定 義如下：定義1:設(shè)函數(shù)M 2d 0, 1,且滿足M ()二0則稱M是2d上的概率分配函數(shù)，M (A)稱為A的基本概率數(shù)。 說(shuō)明：(1)設(shè)樣本空間D中有n個(gè)元素，貝u D中子集的個(gè)數(shù)為2n個(gè)，定義中的2 就是表示這些子集的。(2) 概率分配函數(shù)的作用是把 D的任意一個(gè)子集A都與一個(gè)映射為0, 1上的數(shù)M( A)。當(dāng)A? D時(shí)，M( A)表示對(duì)相應(yīng)命題的精確信任度。實(shí) 際上 就是對(duì)D的各個(gè)子集進(jìn)行信任分配，M(A)表示分配給A的那一部分。 當(dāng)A由 多個(gè)元素組成時(shí)，M(A)不包括對(duì)A的子集的精確信任度，而且也不 知道該對(duì) 它如何進(jìn)

5、行分配。定義2:若A? D且有M(A)工0,稱A為M的一個(gè)焦元。2 .信任函數(shù)定義3:命題的信任函數(shù)Bel: 2d- 0, 1,且對(duì)所有的A? D有Bel(A)其中2d表示D的所有子集。*Bel函數(shù)又稱為下限函數(shù)，Bel (A)表示對(duì)命題A為真的信任程度。由信任函數(shù)及概率分配函數(shù)的定義推出：Bel (尸M ()=0Bel (D)= P 甘廠門:(B) = 13 .似然函數(shù)定義4:似然函數(shù)Pl : 2d- 0, 1,且Pl (A)= 1-Bel (A)其中 A? D似然函數(shù)的含義：由于Bel(A)表示對(duì)A為真的信任程度，所以Bel(A)就表 示對(duì)非A為真，即A為假的信任程度，由此可推出 Pl (

6、A)表示對(duì)A為非假的 信任程度。*似然函數(shù)又稱為不可駁斥函數(shù)或上限函數(shù)。推廣到一般情況可得出:Pl(A-£上門丘證明如下：? PI(A)禹麗毛/(刃| = 1-Bel(A)-E 沖=1-(BeI( A)+L川上l)=i-EZ 匹 I=0? PI ( A=門月革 e" ( B)4 .信任函數(shù)與似然函數(shù)的關(guān)系PI (A)> Bel (A)證明：? Bel(A)十Bel廠屬=麗匚嚴(yán)(的| 一險(xiǎn)嚴(yán) 心(E)? Pl (A) Bel (A)= 1 Bel (A) Bel (A) =1一( Bel (A) + Bel (A) >0? Pl (A)> Bel (A)由于

7、Bel (A)表示對(duì)A為真的信任程度，Pl (A)表示對(duì)A為非假的信任 程度，因 此可分別稱Bel (A)和Pl(A )為對(duì)A信任程度的下限與上限，記為A(Bel(A), Pl( A)例如：A(0,0):由于Bel(A)=0 ,說(shuō)明對(duì)A為真不信任；另外，由于 Bel (A )= 1-Pl(A)=1- 0=1,說(shuō)明對(duì)A信任。所以A(0,0)表示A為假。A(0,1):由于Bel(A)=0 ,說(shuō)明對(duì) A為真不信任；另外，由于 BelA尸1-Pl(A)=1- 1=0,說(shuō)明對(duì)A也不信任。所以A(0,1)表示對(duì)A無(wú)所知。A(1,1):由于Bel(A)=1,說(shuō)明對(duì)A為真信任；另外，由于Bel(A尸1-Pl(

8、A)=1-1=0,說(shuō)明對(duì)A不信任。所以A(1,1)表示A為真。A(0.25,1).由于Bel(A)= 0.25 ,說(shuō)明對(duì)A為真有一定程度的信任，信任度為0.25;另外，由于Bel (A)=1-Pl(A)=0,說(shuō)明對(duì)？ A不信任。所以 A(0.25,1)表示對(duì)A 為真有0. 25的信任度。A(0,0.85).由于 Bel(A) = 0 ,而 Bel(A)=1-Pl(A)=1-0.85=0.15, 所以A(0,0.85)表示對(duì)A為假有一定程度的信任，信仟度為0.15。A (0.25,0.85):由于Bel(A)=0.25,說(shuō)明對(duì)A為真有0.25的信任度；由于 Bel( ? A)=1-0.85=O.

9、15 ,說(shuō)明對(duì) A為假有0.15的信任度。所以 A(0.25,0.85)表示對(duì) A為真的信任度比對(duì)A為假的信任度稍高一些。在上面的討論中已經(jīng)指出，Bel(A)表示對(duì)A為真的信任程度;Bel(A)表 示對(duì)A, 即A為假的信任程度；Pl(A)表示對(duì)A為非假的信任程度。那么，Pl( A)-Bel( A )是什么含義呢？它表示對(duì)A不知道的程度，即既非對(duì) A信任 又非不信任的那部分。在上例的 A(0.25,0.85)中,0.85-0.25=0.60就表示了 對(duì)A不 知道的程度。Dempster 合成公式可以綜合不同專家或數(shù)據(jù)源的知識(shí)或數(shù)據(jù)， 隨著技術(shù)的進(jìn)步和人們對(duì)數(shù)據(jù)采集和處理技術(shù)理解的不斷深入，不確定

10、性數(shù)據(jù) ( un certain data ) 得到廣泛的重視。這使得證據(jù)理論在專家系統(tǒng)、信息融合，情報(bào)分析、法 律案 件分析、多屬性決策分析等領(lǐng)域中得到了廣泛應(yīng)用?；谧C據(jù)理論的不確定性推理，大體可分為以下步驟：(1) 建立問(wèn)題的識(shí)別集合(2) 給幕集定義基本概率分配函數(shù)(3) 計(jì)算所關(guān)心的子集X? ( 即 的子集 ) 的信任函數(shù)值Bel(X) 、似然函數(shù)值Pl(X)(4)由Bel(X)和Pls(X)推理演化，得出結(jié)論二 . 關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則是形如 X-Y 的蘊(yùn)涵式，其中且， X 和 Y 分別稱為關(guān)聯(lián)規(guī)則的先導(dǎo) (LHS) 和后繼 ( RHS) 。假設(shè) I 是項(xiàng)的集合。給定一個(gè)事務(wù)集，其

11、中每個(gè)事務(wù)t 是 I 的非空子集，即 , 每一個(gè)交易都與一個(gè)唯一的標(biāo)識(shí)符 TID 對(duì)應(yīng)。關(guān)聯(lián)規(guī)則在D 中的支持度是D 中事 務(wù)同時(shí)包含 X、 丫 的百分比，即概率；置信度是包含X 的事務(wù)中同時(shí)又包含丫 的 百分比，即條件概率。如果規(guī)則滿足最小支持度閾值和最小置信度閾值，該關(guān)聯(lián)規(guī)則是用戶感興趣。關(guān)聯(lián)規(guī)則挖掘過(guò)程主要包含兩個(gè)階段：第一階段：從給定的事務(wù)集中，找出所有頻繁項(xiàng)集。頻繁的意思是指某一項(xiàng)集出現(xiàn)的頻 率相對(duì)于所有事務(wù)而言，必須達(dá)到指定值。項(xiàng)集出現(xiàn)的頻率稱為支持度，以一個(gè) 包含 A與 B 兩個(gè)項(xiàng)集的 2-itemset 為例，若支持度大于等于所設(shè)定的最小支持度 閾值時(shí)，則A,B稱為頻繁項(xiàng)。一個(gè)

12、滿足最小支持度的k-itemset ,則稱為頻繁k-項(xiàng)集(Frequent k-itemset)。算法并從Large k的項(xiàng)集中再產(chǎn)生 Large k+1 ,直到無(wú)法再找到更長(zhǎng)的頻繁項(xiàng)集為止。第二階段：產(chǎn)生關(guān)聯(lián)規(guī)則 (Association Rules) 。從頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則，是利用前 一步驟 的頻繁k-項(xiàng)集來(lái)產(chǎn)生規(guī)則，在最小信賴度(Minimum Confidenee)的條件閾值下，若 一規(guī)則所求得的信賴度滿足最小信賴度，稱此規(guī)則為關(guān)聯(lián)規(guī)則。三 . 證據(jù)理論引入到關(guān)聯(lián)規(guī)則挖掘中關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)或數(shù)據(jù)挖掘中一種應(yīng)用廣泛的算法。它 最初在文獻(xiàn) () 中提出，其基本思想是在數(shù)據(jù)項(xiàng)中

13、發(fā)現(xiàn)重要的和有趣的關(guān)聯(lián)，一 些項(xiàng)在一個(gè)事務(wù)中出現(xiàn)將暗示另一些項(xiàng)會(huì)在同一個(gè)事務(wù)中出現(xiàn)。 從關(guān)聯(lián)規(guī)則挖掘產(chǎn)生的輸出是一些規(guī)則，這些規(guī)則滿足用戶指定的最小支持度和置信度。關(guān)聯(lián)規(guī)則挖掘廣泛應(yīng)用于MB(購(gòu)物籃分析)，這里的數(shù)據(jù)集是一個(gè)事務(wù)記錄的集合，每條記錄包含顧客在一次事務(wù)中購(gòu)買的所有項(xiàng)的清單。已有的大多數(shù)關(guān)聯(lián)規(guī)則挖掘算法所考慮的數(shù)據(jù)集都有一個(gè)假設(shè)前提， 它們是確切的或始終如一的，并且不含模棱兩可的意義。然而，對(duì)于真實(shí)世界的應(yīng)用， 數(shù)據(jù)集通常決不會(huì)是完美的。數(shù)據(jù)集通常包含一些不確定性，特別是不完備性和 矛盾。分布式信息環(huán)境就是例子，它的數(shù)據(jù)集從不同的源產(chǎn)生和收集， 而且每個(gè) 源可能有不項(xiàng)之間的相互關(guān)系

14、會(huì)呈現(xiàn)不同并導(dǎo)致不確定項(xiàng)關(guān)系。DS 證據(jù)推理理論被用于產(chǎn)生滿足不確定性條件下預(yù)定義支持度和置信度的bpa、 Bel 和 PI ，用一個(gè)似香農(nóng)的總的不確定性度量來(lái)反 映不確定程度。實(shí)驗(yàn)步驟實(shí)驗(yàn)步驟1. 從不同數(shù)據(jù)文件中讀取數(shù)據(jù)；2. 實(shí)現(xiàn)動(dòng)態(tài)數(shù)組；3. 求兩集合的交、并、差集和子集；4. 實(shí)現(xiàn)DS 基本算法；5. 利用DS 理論挖掘關(guān)聯(lián)規(guī)則。實(shí)驗(yàn)的算法1. 從不同數(shù)據(jù)文件中讀取數(shù)據(jù)( 以文本文檔為例 ) ；1(1 入：文本文件名) 23 (輸( 程序所在文件夾與文本文檔文件夾為同一文件夾 )；從文件中讀取一個(gè)字符；若字符為數(shù)字跳到過(guò)程( 4), 若字符為結(jié)束符號(hào)結(jié)束程序，否則跳到過(guò)程(6)；(4

15、) 繼續(xù)讀取下一個(gè)字符，若字符依然為數(shù)字，重復(fù)過(guò)程(4);(5) 把整個(gè)數(shù)字串存儲(chǔ)到實(shí)型數(shù)組；并且返回過(guò)程 (3) ；(6) 繼續(xù)讀取下一個(gè)字符，若字符依然為字符，重復(fù)過(guò)程( 6) ；(7) 把整個(gè)字符串存儲(chǔ)到字符串?dāng)?shù)組；并且返回過(guò)程 (3) ；(8) 輸入：文本中數(shù)據(jù)。2. 實(shí)現(xiàn)動(dòng)態(tài)數(shù)組；(1) 輸入：控制動(dòng)態(tài)數(shù)組動(dòng)態(tài)大小的數(shù)值a ；(2) 若 a>0 ，則執(zhí)行過(guò)程(3) ，否則執(zhí)行過(guò)程(4);(3) b=b*2;a=a-1, 返回過(guò)程(2) ;(4) in t*p=n ewb;(5) 輸出：動(dòng)態(tài)產(chǎn)生的數(shù)組。3. 求兩集合的交、并、差集和子集；交集：(1) 自動(dòng)生成兩個(gè)集合a ， b

16、；(2) 掃描集合 a 的一個(gè)元素；(3) 掃描集合 b 的一個(gè)元素，如果兩元素相等，將元素存入交集，并且跳回步 驟（ 2 ） , 否則重復(fù)步驟（ 3 ）直至 b 中元素全部被掃描；（ 4 ）跳回步驟（2 ）直至a 中所有元素都被掃描。 并集：（ 1 ） 自動(dòng)生成兩個(gè)長(zhǎng)度為 n 的集合 a， b, 定義 k=0 ；（ 2 ） 復(fù)制集合 a 的所有元素存入并集；（ 3 ） 掃描 b 的一個(gè)元素；（ 4 ） 掃描 a 的一個(gè)元素，如果兩元素不相等， k 賦值為 k+1 ; 重復(fù)步驟（ 4 ）直 至 a 中所有元素都被掃描；（5） 如果 kvn, 將 b 中這個(gè)元素存入并集，反回步驟（3）直至b 中

17、元素全部 被掃描。差集：（ 1 ） 自動(dòng)生成兩個(gè)長(zhǎng)度為 n 的集合 a， b, 定義 k=0 ；（ 2 ） 掃描 a 的一個(gè)元素；（ 3 ） 掃描 b 的一個(gè)元素，如果兩元素相等， k 賦值為 k+1 ; 重復(fù)步驟（ 4 ）直至 b 中所有元素都被掃描；（ 4 ） 如果 k=0 ，將 a 中這個(gè)元素存入差集，反回步驟（2 ）直至a 中元素全部 被掃描。輸入：集合的運(yùn)算結(jié)果。4. 實(shí)現(xiàn) DS 基本算法；1 ） 輸入：樣本集合；2 ） 求樣本幕集并給所有集合賦值一個(gè) 0,1 的隨機(jī)數(shù)作為基本概率分配函 數(shù)， 同時(shí)求隨機(jī)數(shù)總和 sum;3 ） 將樣本幕集中每個(gè)集合的 bpa 除以 sum 進(jìn)行標(biāo)準(zhǔn)化

18、，得到質(zhì)量函數(shù)m;4 ） 根據(jù) m 求出 bel 和 pl;5 ） 輸出：不確定區(qū)間。5. 利用 DS 理論挖掘關(guān)聯(lián)規(guī)則。1 ）輸入：最小支持度和置信度，事務(wù)集；2 ）根 據(jù)含有不確定信息的事務(wù)集創(chuàng)建問(wèn)題的識(shí)別框架并給定基本概率分配函數(shù)bpa；3 ）結(jié)合bpa和事務(wù)集將不確定性事務(wù)集轉(zhuǎn)換為證據(jù)集；4 ）定 義衡量不確定度的量并求出識(shí)別框架中每個(gè)命題被證據(jù)集支持的程度si；5 ）根據(jù)si 求出相應(yīng)的置信度和支持度；6 ）輸出滿足最小支持度和置信度的關(guān)聯(lián)規(guī)則。實(shí)驗(yàn)結(jié)果D-S 證據(jù)理論1. 讀取txt 文件；程序能將文本文件原模原樣的讀出來(lái)并顯示程序自動(dòng)分類文本文件的數(shù)據(jù)，將字?jǐn)?shù)和字符分開顯示2.求

19、兩集合的交并差集;輸入：第一個(gè)集合為：2, 5dg , 89, de 第二個(gè)集合為：9999, 2 , de, n qig, lg, aaaaaaa2, 38結(jié)果：兩集合的交集為：2, de 兩集合的并集為：2, 5dg , 89, de, 9999, nq ig, 1g, aaaaaaa2, 38兩集合的差集為：5dg, 89 輸入：第一個(gè)集合為：564657, 8413 ,發(fā),25 第二個(gè)集合為：發(fā)，格拉斯哥,dg, 8413 兩集合的交集為：8413，發(fā)結(jié)果：兩集合的并集為：564657, 8413 ,發(fā),25,格拉斯哥,dg 兩集合的差集為：564657, 25 3.基于以上條件，求集

20、合的幕集并給幕集中的每個(gè)集合分配一個(gè)概率，將其標(biāo)準(zhǔn)化后得到質(zhì)量函數(shù)； -5學(xué)習(xí) &禮開站曲昌過(guò)-,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.由質(zhì)量函數(shù)求其信任函數(shù)及似然函數(shù)上面是基于前面的改進(jìn)，0為結(jié)束符號(hào)，表示 1的信任函數(shù)值為0.579967.2的似然函數(shù)值為0.420033.上圖表示表示集合 1 2 3的信任函數(shù)值為1.2 3的似然函數(shù)值為0.783251.實(shí)驗(yàn)小結(jié)1 .閱讀材料心得體會(huì)本次創(chuàng)新實(shí)驗(yàn)我了解了一種新的理論一一 DS證據(jù)理論并且介紹了 DS證據(jù)推 理 幾個(gè)基本概念的物理意義它可以用于處理證據(jù)影響一類假設(shè)的情況，并準(zhǔn)備將 其應(yīng)用于不確定性數(shù)據(jù)質(zhì)量檢測(cè)。此外，通過(guò)這次實(shí)驗(yàn)我還學(xué)習(xí)到了數(shù)據(jù)挖掘中最基本的方法一一關(guān)聯(lián)規(guī)則挖 掘， 其目標(biāo)是把數(shù)據(jù)項(xiàng)之間的關(guān)

22、聯(lián)從數(shù)據(jù)集中挖掘出來(lái)。 如何把關(guān)聯(lián)規(guī)則挖掘與 實(shí)際問(wèn) 題緊密結(jié)合，是數(shù)據(jù)挖掘的一個(gè)重要研究方向。2 .實(shí)驗(yàn)中的心得體會(huì)實(shí)驗(yàn)過(guò)程中我發(fā)現(xiàn)自己的編程能力有待提高，遇到很多問(wèn)題，如最開始使用了指針實(shí)現(xiàn)了實(shí)現(xiàn)動(dòng)態(tài)數(shù)組，但是到后面發(fā)現(xiàn)以向量的方式會(huì)簡(jiǎn)便得多，也讓我發(fā)現(xiàn)很多事情只是你不去做而已，真正的認(rèn)真的去鉆研后，會(huì)發(fā)現(xiàn)其實(shí)它并不像想象中的那樣困難，而且我也終于明白最難的地方不是編程而是思想?？傊@次創(chuàng)新實(shí)驗(yàn)讓我更加理解計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的實(shí)際意義。本實(shí)驗(yàn)暫時(shí)只實(shí)現(xiàn)了 DS證據(jù)理論的基本方法，目前暫時(shí)還不能夠進(jìn)行與文件關(guān)聯(lián)及數(shù)據(jù)的融合，把 DS證據(jù)理論與數(shù)據(jù)庫(kù)等連接起來(lái)后，將里面的數(shù)據(jù)進(jìn)行分類并將數(shù)據(jù)進(jìn)行融合便可以建立起一個(gè)不確定性的推理模型，給其中數(shù)據(jù)分配概率后便可以求得其概率的上限與下限，這樣這個(gè)實(shí)驗(yàn)就會(huì)變得更具有實(shí)際意義了，在接下來(lái)的一年里我會(huì)以創(chuàng)新實(shí)驗(yàn)為基礎(chǔ),更加認(rèn)真的去做出一個(gè)優(yōu)秀的畢業(yè)設(shè)計(jì)。參考文獻(xiàn)1 R. Agrawal, T. Imielinski, and A. Swa