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

1、本科創(chuàng)新實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：DS證據(jù)理論與數(shù)據(jù)挖掘 學(xué)生姓名：楊勝達(dá) 學(xué) 號(hào)：20091060120 專 業(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)康?實(shí)驗(yàn)內(nèi)容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)12實(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)內(nèi)容一 實(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)內(nèi)容正在進(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ù)理論”(The D-S theory of e

3、vidence) ,起源于Dempster早期提出的由多值映射導(dǎo)出的所謂上限概率和下限概率， 由于該理論滿足比概率論更弱的公理體系比概率推理理論中的更為直觀、更容易獲得，能夠區(qū)分“不確定”與“不知道”的差異并能夠處理由未知引起的不確定性, 具有較大的靈活性從而受到人們的重視?；纠碚?設(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. 概率分配函數(shù)設(shè)D為樣本空間，領(lǐng)

4、域內(nèi)的命題都用D的子集表示，則概率分配函數(shù)定義如下：定義1： 設(shè)函數(shù)M：2D0，1，且滿足M（）0ADM（A）1 則稱M是2D上的概率分配函數(shù)，M（A）稱為A的基本概率數(shù)。說(shuō)明 ：（1）設(shè)樣本空間D中有n個(gè)元素，則D中子集的個(gè)數(shù)為2n個(gè)，定義中的2D就是表示這些子集的。 （2）概率分配函數(shù)的作用是把D的任意一個(gè)子集A都與一個(gè)映射為0，1上的數(shù)M（A）。當(dāng)AD時(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)行分配。定義2：若AD且有M(A)0，稱A為M

5、的一個(gè)焦元。 2. 信任函數(shù)定義3:命題的信任函數(shù)Bel：2D0，1，且對(duì)所有的AD 有Bel(A）BAM（B） 其中2D表示D的所有子集。*Bel函數(shù)又稱為下限函數(shù)，Bel（A）表示對(duì)命題A為真的信任程度。由信任函數(shù)及概率分配函數(shù)的定義推出：Bel（）M（）0Bel（D）BDM（B）1 3. 似然函數(shù)定義4: 似然函數(shù)Pl：2D0，1，且Pl（A）1Bel（A） 其中AD似然函數(shù)的含義：由于Bel(A)表示對(duì)A為真的信任程度，所以Bel(A)就表示對(duì)非A為真，即A為假的信任程度，由此可推出Pl（A）表示對(duì)A為非假的信任程度。*似然函數(shù)又稱為不可駁斥函數(shù)或上限函數(shù)。推廣到一般情況可得出：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. 信任函數(shù)與似然函數(shù)的關(guān)系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）表示對(duì)A為真的信任程度，Pl（A）表示對(duì)A為非假的信任程度，因此可分別稱Bel（A）和Pl(A）為對(duì)A信任程度的下限與上限，記為 A(Be

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

8、另外，由于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.15，說(shuō)明對(duì)A為假有0.15的信任度。所以A(0.25,0.85)表示對(duì)A為真的信任度比對(duì)A為假的信任度稍高一些。在上面的討論中已經(jīng)指出,Bel(A)表示對(duì)A為真的信任程度;Bel(

9、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ù)理解的不斷深入，不確定性數(shù)據(jù)（uncertain data）得到廣泛的重視。這使得證據(jù)理論在專家系統(tǒng)、信息融合，情報(bào)分析、法律案件分析、多屬性決策分析等領(lǐng)域中得到了廣泛應(yīng)用?；谧C據(jù)理論的不確定性推理，大體可分為以下步驟：（1）建

10、立問(wèn)題的識(shí)別集合Q（2）給冪集 定義基本概率分配函數(shù) （3）計(jì)算所關(guān)心的子集X （即Q的子集）的信任函數(shù)值Bel(X)、似然函數(shù)值Pl(X) （4）由Bel(X)和Pls(X)推理演化，得出結(jié)論二 關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)涵式，其中且， X和Y分別稱為關(guān)聯(lián)規(guī)則的先導(dǎo)(LHS)和后繼(RHS) 。假設(shè)I是項(xiàng)的集合。給定一個(gè)事務(wù)集，其中每個(gè)事務(wù)t是I的非空子集，即，每一個(gè)交易都與一個(gè)唯一的標(biāo)識(shí)符TID對(duì)應(yīng)。關(guān)聯(lián)規(guī)則在D中的支持度是D中事務(wù)同時(shí)包含X、Y的百分比，即概率；置信度是包含X的事務(wù)中同時(shí)又包含Y的百分比，即條件概率。如果規(guī)則滿足最小支持度閾值和最小置信度閾值，該關(guān)聯(lián)規(guī)則是用戶感興

11、趣。 關(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è)滿足最小支持度的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)

12、生規(guī)則，在最小信賴度(Minimum Confidence)的條件閾值下，若一規(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)中發(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)用于MBA（購(gòu)物籃分析），這里的數(shù)據(jù)集是一個(gè)事務(wù)記錄的集合，每條記錄包含顧客在一次事務(wù)中購(gòu)買的所有項(xiàng)的清單。已有的大多數(shù)關(guān)聯(lián)規(guī)則挖掘算法所考慮的數(shù)據(jù)集都

13、有一個(gè)假設(shè)前提，它們是確切的或始終如一的，并且不含模棱兩可的意義。然而，對(duì)于真實(shí)世界的應(yīng)用，數(shù)據(jù)集通常決不會(huì)是完美的。數(shù)據(jù)集通常包含一些不確定性，特別是不完備性和矛盾。分布式信息環(huán)境就是例子，它的數(shù)據(jù)集從不同的源產(chǎn)生和收集，而且每個(gè)源可能有不同的約束。這會(huì)導(dǎo)致項(xiàng)之間不同的相互關(guān)系強(qiáng)加于數(shù)據(jù)集中。因此，項(xiàng)之間的相互關(guān)系會(huì)呈現(xiàn)不同并導(dǎo)致不確定項(xiàng)關(guān)系。DS證據(jù)推理理論被用于產(chǎn)生滿足不確定性條件下預(yù)定義支持度和置信度的關(guān)聯(lián)規(guī)則?；谠械腷pa、Bel和Pl，用一個(gè)似香農(nóng)的總的不確定性度量來(lái)反映不確定性條件下的支持度和置信度，以便獲得所考慮的數(shù)據(jù)集中隱藏的總的不確定程度。實(shí)驗(yàn)步驟一實(shí)驗(yàn)步驟1. 從不同

14、數(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） 輸入：文本文件名（程序所在文件夾與文本文檔文件夾為同一文件夾）；（2） 從文件中讀取一個(gè)字符；（3） 若字符為數(shù)字跳到過(guò)程（4），若字符為結(jié)束符號(hào)結(jié)束程序，否則跳到過(guò)程（6）；（4） 繼續(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ù)組；并且

15、返回過(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） 若a0，則執(zhí)行過(guò)程（3），否則執(zhí)行過(guò)程（4）；（3） b=b*2;a=a-1,返回過(guò)程（2）;（4） int*p=newb;（5） 輸出：動(dòng)態(tài)產(chǎn)生的數(shù)組。3. 求兩集合的交、并、差集和子集；交集：（1） 自動(dòng)生成兩個(gè)集合a，b；（2） 掃描集合a的一個(gè)元素；（3） 掃描集合b的一個(gè)元素，如果兩元素相等，將元素存入交集，并且跳回步驟（2），否則重復(fù)步驟（3）直至b中元素全部被掃描；（4） 跳回步驟（2）直至a中所有元素都被掃描。并集：（1） 自動(dòng)生成兩個(gè)長(zhǎng)度為n的集合a，b，定義k=

16、0；（2） 復(fù)制集合a的所有元素存入并集；（3） 掃描b的一個(gè)元素；（4） 掃描a的一個(gè)元素，如果兩元素不相等，k賦值為k+1；重復(fù)步驟（4）直至a中所有元素都被掃描；（5） 如果kn，將b中這個(gè)元素存入并集，反回步驟（3）直至b中元素全部被掃描。差集：（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） 求樣本冪

17、集并給所有集合賦值一個(gè)0,1的隨機(jī)數(shù)作為基本概率分配函數(shù)，同時(shí)求隨機(jī)數(shù)總和sum;（3） 將樣本冪集中每個(gè)集合的bpa除以sum進(jìn)行標(biāo)準(zhǔn)化，得到質(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ù)集支持的程度sl；（5） 根據(jù)sl求出相應(yīng)的置信度和支持度；（6） 輸出滿足最小支持度和置信度的關(guān)聯(lián)規(guī)則。實(shí)驗(yàn)結(jié)果一

18、D-S證據(jù)理論1. 讀取txt文件；程序能將文本文件原模原樣的讀出來(lái)并顯示。程序自動(dòng)分類文本文件的數(shù)據(jù)，將字?jǐn)?shù)和字符分開(kāi)顯示。2. 求兩集合的交并差集；輸入：第一個(gè)集合為：2, 5dg , 89, de第二個(gè)集合為：9999, 2 , de, nqig, lg, aaaaaaa2, 38結(jié)果：兩集合的交集為：2, de兩集合的并集為：2, 5dg , 89, de, 9999, nqig, lg, aaaaaaa2, 38兩集合的差集為：5dg, 89輸入：第一個(gè)集合為：564657, 8413 , 發(fā), 25第二個(gè)集合為：發(fā), 格拉斯哥, dg, 8413兩集合的交集為：8413, 發(fā)結(jié)果：

19、兩集合的并集為：564657, 8413 , 發(fā), 25, 格拉斯哥, dg兩集合的差集為：564657, 253. 基于以上條件，求集合的冪集并給冪集中的每個(gè)集合分配一個(gè)概率，將其標(biāo)準(zhǔn)化后得到質(zhì)量函數(shù)；上圖表示輸入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. 由質(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é)一閱讀材料心得體會(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í)到

21、了數(shù)據(jù)挖掘中最基本的方法關(guān)聯(lián)規(guī)則挖掘，其目標(biāo)是把數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)從數(shù)據(jù)集中挖掘出來(lái)。如何把關(guān)聯(lián)規(guī)則挖掘與實(shí)際問(wèn)題緊密結(jié)合，是數(shù)據(jù)挖掘的一個(gè)重要研究方向。二實(shí)驗(yàn)中的心得體會(huì)實(shí)驗(yàn)過(guò)程中我發(fā)現(xiàn)自己的編程能力有待提高，遇到很多問(wèn)題，如最開(kāi)始使用了指針實(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)行分