畢業(yè)論文-不完備信息系統(tǒng)中基于不可區(qū)分度的知識(shí)約簡(jiǎn)算法的程序設(shè)計(jì)與實(shí)現(xiàn)

1、 山西大學(xué)論文 編號(hào)：論文題目 不完備信息系統(tǒng)中基于不可區(qū)分度的 知識(shí)約簡(jiǎn)算法的程序設(shè)計(jì)與實(shí)現(xiàn)姓 名 院 系 計(jì)算機(jī)與信息技術(shù)學(xué)院 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)習(xí)年限 2005 年 9 月至 2009 年 7 月指導(dǎo)教師 學(xué)位級(jí)別 學(xué) 士 2009年5月23日不完備信息系統(tǒng)中基于不可區(qū)分度的知識(shí)約簡(jiǎn)算法的程序設(shè)計(jì)與實(shí)現(xiàn)學(xué)生姓名： 指導(dǎo)教師：內(nèi)容提要 由于不完備信息系統(tǒng)（含有缺省數(shù)據(jù)或不精確數(shù)據(jù)）普遍存在，近年來，對(duì)不完備信息系統(tǒng)的研究已經(jīng)引起了人們的廣泛注意。但到目前為止，對(duì)基于不可區(qū)分度的不完備信息系統(tǒng)知識(shí)約簡(jiǎn)算法的研究還集中在理論方面，缺乏實(shí)際成型、有效的應(yīng)用程序或軟件。本課題完成了不完備

2、信息表中基于不可區(qū)分度的知識(shí)約簡(jiǎn)算法和不完備決策表中基于不可區(qū)分度的相對(duì)約簡(jiǎn)算法的程序設(shè)計(jì)與實(shí)現(xiàn)。本程序設(shè)計(jì)可作為該算法的輔助工具，具有實(shí)際意義。關(guān)鍵詞 不完備信息系統(tǒng)，不可區(qū)分度，重要性，（相對(duì)）核，（相對(duì)）約簡(jiǎn) 1 引言粗糙集理論是一種處理不精確、不確定與不完全數(shù)據(jù)的新的數(shù)學(xué)方法，該理論已被廣泛應(yīng)用于知識(shí)獲取、專家系統(tǒng)、決策分析和決策支持等各種應(yīng)用領(lǐng)域。知識(shí)約簡(jiǎn)是粗糙集理論處理信息系統(tǒng)的重要手段。現(xiàn)實(shí)生活中存在著大量的不完備信息系統(tǒng)（含有缺省值或不精確數(shù)據(jù)），因此不完備信息系統(tǒng)中的知識(shí)約簡(jiǎn)算法就具有重要的實(shí)際意義。文13基于不完備信息系統(tǒng)提出了信息系統(tǒng)的可區(qū)分度和不可區(qū)分度的概念，給出了它

3、們的重要性質(zhì)，并建立了二者之間的關(guān)系，并且證實(shí)了不完備信息系統(tǒng)的不可區(qū)分度和可區(qū)分度可退化為完備信息系統(tǒng)的知識(shí)粒度與信息熵。文9在文13研究的基礎(chǔ)上提出了一種基于不完備信息系統(tǒng)的知識(shí)獲取方法，該算法將含有缺省值的不完備信息系統(tǒng)的知識(shí)約簡(jiǎn)方法與多值信息系統(tǒng)的知識(shí)約簡(jiǎn)統(tǒng)一起來，最終能得到不完備信息表的約簡(jiǎn)和不完備決策表的相對(duì)約簡(jiǎn)。到目前為止，對(duì)基于不可區(qū)分度的不完備信息系統(tǒng)知識(shí)約簡(jiǎn)算法的研究已經(jīng)有了大量的理論研究，但是還缺少實(shí)現(xiàn)它的軟件工具，這是這方面的研究方向。2 基本原理2.1 基本概念2.1.1 不完備信息系統(tǒng)一個(gè)信息系統(tǒng)是一個(gè)二元組,其中（1）是對(duì)象的非空有限集合；（2）是屬性的非空有限集

4、合；（3）對(duì)，有一個(gè)映射，其中是的冪集，表示空集，每一個(gè)屬性集決定一個(gè)二元不可區(qū)分關(guān)系，即 易證,是集合上的一個(gè)等價(jià)關(guān)系。關(guān)系，構(gòu)成了的一個(gè)劃分，用表示13。2.1.2 相容類令，定義相容關(guān)系（滿足自反性和對(duì)稱性）如下： 用表示分類，即為由相容關(guān)系決定的最大相容類集合。2.1.3 不可區(qū)分度文13基于不完備信息系統(tǒng)（含有缺省數(shù)據(jù)或不精確數(shù)據(jù)）提出了信息系統(tǒng)的不可區(qū)分度和可區(qū)分度的概念，給出了它們的重要性質(zhì)，并建立了二者之間的關(guān)系。設(shè)是一個(gè)不完備信息系統(tǒng)，。則信息系統(tǒng)關(guān)于的不可區(qū)分度定義為： 若，則可取得最小值。若，且對(duì)有，則可取得最大值。不可區(qū)分度和可區(qū)分度的關(guān)系為+=1。其中定義為： 表示決

5、策屬性集的條件可分度，定義為：。表示決策屬性集的條件不可分度，且與關(guān)系為+=1。2.1.4 屬性重要性度量設(shè)是一個(gè)不完備信息表，任意屬性關(guān)于屬性集的重要性定義為： 該定義表明，對(duì)一個(gè)屬性集合，添加一個(gè)屬性引起的不可區(qū)分度變化量越大，則該屬性對(duì)此屬性集就越重要。因此可用它作為啟發(fā)知識(shí)以減少搜索空間來尋找約簡(jiǎn)9。設(shè)是一個(gè)不完備決策表，屬性相對(duì)于決策屬性集的重要性定義為： 該定義表明，屬性在屬性集中的相對(duì)重要性由去掉它所引起的條件不可區(qū)分度的大小來度量9。2.1.5（相對(duì)）約簡(jiǎn)，（相對(duì)）核令為一族等價(jià)關(guān)系,r，如果(-r),則稱r為中必要的,否則稱r為中不必要的。如果每一個(gè)r都為中必要的，則稱為獨(dú)立

6、的，否則稱為依賴的。如果是獨(dú)立的，則也是獨(dú)立的。設(shè)，如果是獨(dú)立的，且，則稱為的一個(gè)約簡(jiǎn)。中所有必要關(guān)系組成的集合稱為的核，記作。，其中表示的所有約簡(jiǎn)。令和為等價(jià)關(guān)系族，如果,則稱為中不必要的，否則為中必要的。如果中的每一個(gè)都為必要的，則稱為獨(dú)立的。設(shè)，為的約簡(jiǎn)當(dāng)且僅當(dāng)是的獨(dú)立子族且。的約簡(jiǎn)簡(jiǎn)稱為相對(duì)約簡(jiǎn)。中所有必要的原始關(guān)系構(gòu)成的集合稱為的核，簡(jiǎn)稱為相對(duì)核。記為：。2.2 算法原理2.2.1 基于不可區(qū)分度的不完備信息表屬性約簡(jiǎn)算法由重要性的定義表明，對(duì)一個(gè)屬性集合，添加一個(gè)屬性引起的可區(qū)分度變化量越大，則該屬性對(duì)此屬性集就越重要。因此可用它作為啟發(fā)知識(shí)以減少搜索空間來尋找約簡(jiǎn)。由性質(zhì)可方便地

7、求出不完備信息表的核，由于核的唯一性，因此可以將它作為求約簡(jiǎn)的起點(diǎn)，令，并由重要性定義逐次選擇重要性最大的屬性添加到約簡(jiǎn)中，直到系統(tǒng)關(guān)于的不可區(qū)分度與系統(tǒng)關(guān)于整個(gè)屬性集合的不可區(qū)分度相等時(shí)算法結(jié)束。2.2.2 基于條件不可區(qū)分度的不完備決策表屬性約簡(jiǎn)算法對(duì)于決策表,可以利用每個(gè)條件屬性對(duì)決策屬性的相對(duì)重要性大小來判斷添加它之后引起的條件不可區(qū)分度的變化大小，可以通過不斷增加相對(duì)重要性最大的屬性尋找相對(duì)約簡(jiǎn)。由性質(zhì)可方便地求出不完備決策表的相對(duì)核，由于相對(duì)核的唯一性，因此可以將它作為求相對(duì)約簡(jiǎn)的起點(diǎn)，令，并由相對(duì)重要性定義逐次選擇相對(duì)重要性最大的屬性添加到相對(duì)約簡(jiǎn)中，直到系統(tǒng)關(guān)于相對(duì)于的條件不可

8、區(qū)分度與系統(tǒng)關(guān)于相對(duì)于的條件不可區(qū)分度相等時(shí)算法結(jié)束。2.3 相關(guān)技術(shù)（1）C#程序設(shè)計(jì)語言C#是一種面向?qū)ο蟮木幊陶Z言，它不但有著C+的強(qiáng)大功能，語法也和C+基本相同，并且還包含了大量的高效代碼和面向?qū)ο蟮奶匦裕?，C#語言將在保持C/C+靈活性的特點(diǎn)上，為程序員帶來更高效的開發(fā)方式，它不僅能用于WEB網(wǎng)站服務(wù)程序，而且還能開發(fā)強(qiáng)大的系統(tǒng)工具，總體來說，它具有以下特性：1：C#代碼在.net框架提供的受控環(huán)境下運(yùn)行，不允許直接操作內(nèi)存，增強(qiáng)了程序的安全性。2：C/C+中的指針已經(jīng)不在C#中出現(xiàn)了。3：C#具有面向?qū)ο笳Z言編程的一切特性，如封裝，繼承，多態(tài)等。在C#的類型系統(tǒng)中，每種類型都可

9、以看做是一個(gè)對(duì)象，但C#只允許單繼承，這樣避免了類型定義的混亂。（2）SQL Server 2000數(shù)據(jù)庫SQL是英文Structured Query Language的縮寫。SQL語言的主要功能就是同各種數(shù)據(jù)庫建立聯(lián)系，進(jìn)行溝通。SQL語句可以用來執(zhí)行各種各樣的操作，例如更新數(shù)據(jù)庫中的數(shù)據(jù)，從數(shù)據(jù)庫中提取數(shù)據(jù)等。目前，絕大多數(shù)流行的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，如Oracle, Sybase, Microsoft SQL Server, Access等都采用了SQL語言標(biāo)準(zhǔn)。雖然很多數(shù)據(jù)庫都對(duì)SQL語句進(jìn)行了再開發(fā)和擴(kuò)展，但是包括Select, Insert, Update, Delete, Cre

10、ate以及Drop在內(nèi)的標(biāo)準(zhǔn)的SQL命令仍然可以被用來完成幾乎所有的數(shù)據(jù)庫操作。 2.4 開發(fā)環(huán)境及工具軟件環(huán)境：Microsoft Windows XP、SQL Server 2000數(shù)據(jù)庫、Microsoft Visual Studio 2005。硬件環(huán)境：AMD Sempron(tm) Processor 3000+處理器、1M內(nèi)存、4G硬盤。3 系統(tǒng)分析3.1 需求分析本算法是不完備信息系統(tǒng)基于不可區(qū)分度的知識(shí)約簡(jiǎn)算法的程序設(shè)計(jì)與實(shí)現(xiàn)，按照具體環(huán)境設(shè)定對(duì)其提出如下具體要求：（1）程序有登錄界面，并有能連接、斷開數(shù)據(jù)庫和選擇并打開庫中表的功能；（2）程序能創(chuàng)建表，只要對(duì)表名，字段名及其類

11、型和長(zhǎng)度進(jìn)行正確填寫即可創(chuàng)建新表，并鏈接到數(shù)據(jù)庫，操作簡(jiǎn)單；（3）程序能對(duì)信息表及決策表進(jìn)行相容類分類，計(jì)算不可區(qū)分度、屬性重要性和相對(duì)重要性、核和相對(duì)核，最后得出約簡(jiǎn)及相對(duì)約簡(jiǎn)結(jié)果；（4）程序具有可移植性，即不改源代碼在別的計(jì)算機(jī)上也能連接數(shù)據(jù)庫使用；（5）約簡(jiǎn)后的表數(shù)據(jù)不能覆蓋原數(shù)據(jù)，另存也沒意義，故不提供保存功能；（6）保證程序的穩(wěn)定性。3.2 系統(tǒng)總體設(shè)計(jì)本系統(tǒng)主要完成了連接、斷開數(shù)據(jù)庫，創(chuàng)建表，打開表，對(duì)表進(jìn)行相容類分類，約簡(jiǎn)（信息表約簡(jiǎn)和決策表相對(duì)約簡(jiǎn)）等功能。系統(tǒng)功能模塊圖如3-2-1所示，系統(tǒng)流程圖如圖3-2-2所示。圖3-2-1 系統(tǒng)功能模塊圖圖3-2-2 系統(tǒng)流程圖3.3

12、后臺(tái)數(shù)據(jù)庫設(shè)計(jì)圖 創(chuàng)建不完備決策表，表格式如表3-1所示，表內(nèi)容如表3-2所示。表的創(chuàng)建：只要對(duì)表名，字段名及其類型和長(zhǎng)度進(jìn)行正確填寫即可創(chuàng)建新表。表3-1 不完備決策表格式表3-2 不完備決策表內(nèi)容 注意：表內(nèi)容“*”表示信息缺失或空值。3.4 用戶界面設(shè)計(jì)（1）登錄界面該界面用于連接數(shù)據(jù)庫，只要?jiǎng)?chuàng)建數(shù)據(jù)庫成功并設(shè)置用戶名、密碼，連接數(shù)據(jù)源便可使用。如圖3-4-1所示。圖3-4-1 登錄界面（2）選擇表界面該界面用于選擇表，創(chuàng)建表，打開表，斷開數(shù)據(jù)庫，退出程序。此界面主要用于顯示數(shù)據(jù)庫中的表，它只搜索SQL Server 2000數(shù)據(jù)庫中的用戶表，能保證庫中系統(tǒng)表的安全性，并在界面中顯示出來

13、。如圖3-4-2所示。 圖3-4-2選擇表界面（3）約簡(jiǎn)界面該界面主要用于對(duì)表進(jìn)行約簡(jiǎn)，可以顯示相容類分類，不可區(qū)分度，屬性（相對(duì)）重要性，（相對(duì)）約簡(jiǎn)、核的計(jì)算結(jié)果。圖3-4-3為信息表約簡(jiǎn)界面，圖3-4-4為決策表相對(duì)約簡(jiǎn)界面。圖3-4-3 信息表約簡(jiǎn)界面圖3-4-4 決策表相對(duì)約簡(jiǎn)界面4 系統(tǒng)約簡(jiǎn)關(guān)鍵算法及其流程圖4.1 基于不可區(qū)分度的不完備信息表屬性約簡(jiǎn)算法該算法流程圖如圖3-5-1所示。圖3-5-1 信息表的約簡(jiǎn)算法流程圖算法過程為：輸入：一個(gè)不完備信息表；輸出：的一個(gè)屬性約簡(jiǎn)。步驟1：計(jì)算系統(tǒng)關(guān)于屬性集的不可區(qū)分度；步驟2：令，計(jì)算每個(gè)屬性對(duì)于的重要性。若，則令。最后得到的即為的

14、核，令；步驟3：若，則轉(zhuǎn)至步驟5；否則轉(zhuǎn)至步驟4；步驟4：對(duì)，計(jì)算，令，則，轉(zhuǎn)至步驟3；步驟5：最后得到的即為的一個(gè)屬性約簡(jiǎn)。算法結(jié)束。4.2 基于條件不可區(qū)分度的不完備決策表屬性約簡(jiǎn)算法該算法流程圖如圖3-5-2所示。計(jì)算不可區(qū)分度令，計(jì)算每個(gè)相對(duì)于決策屬性的令， 則, 否是令 得到的即為的一個(gè)相對(duì)約簡(jiǎn)對(duì)，計(jì)算結(jié) 束開 始圖3-5-2 決策表相對(duì)約簡(jiǎn)算法流程圖算法過程為：輸入：一個(gè)不完備決策表；輸出：的一個(gè)相對(duì)約簡(jiǎn)。步驟1：計(jì)算；步驟2：令，計(jì)算每個(gè)相對(duì)于決策屬性的重要性。若>0，則令。最后得到的即為相對(duì)核，令；步驟3：若，則轉(zhuǎn)至步驟5；否則轉(zhuǎn)至步驟4； 步驟4：對(duì)，計(jì)算，令， 則，轉(zhuǎn)

15、至步驟3；步驟5：最后得到的即為的一個(gè)相對(duì)約簡(jiǎn)。算法結(jié)束。5 系統(tǒng)的優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：（1）本系統(tǒng)具有可移植性，只要?jiǎng)?chuàng)建數(shù)據(jù)源并設(shè)定數(shù)據(jù)名和密碼，即可連接本地SQL Server 200數(shù)據(jù)庫。（2）本系統(tǒng)界面友好，用戶操作簡(jiǎn)單，使用方便。（3）本系統(tǒng)不修改后臺(tái)數(shù)據(jù)庫內(nèi)容，安全性高。（4）本系統(tǒng)可呈現(xiàn)十分詳細(xì)的計(jì)算過程，容易理解。缺點(diǎn)：本系統(tǒng)完成了用戶登錄，連接、斷開數(shù)據(jù)庫，新建表，打開表，對(duì)表進(jìn)行相容類分類、(相對(duì))約簡(jiǎn)及（相對(duì)）核計(jì)算等功能。因?yàn)閷?duì)C#語言不是很熟練，實(shí)現(xiàn)算法的代碼量稍大，運(yùn)行時(shí)間稍長(zhǎng)，沒有達(dá)到理想效果，加大了工作量，而且由于技術(shù)及時(shí)間原因擴(kuò)展功能也不是很多，這是本系統(tǒng)的不足

16、之處。6 結(jié)束語經(jīng)過了一個(gè)學(xué)期的學(xué)習(xí)，我終于完成了該系統(tǒng)的算法設(shè)計(jì)及實(shí)現(xiàn)。從開始接到論文題目到系統(tǒng)的實(shí)現(xiàn)，再到論文的完成，每走一步對(duì)我來說都是新的嘗試與挑戰(zhàn)，這也是我在大學(xué)期間獨(dú)立完成的最大的項(xiàng)目。在這段時(shí)間里，我學(xué)到了很多知識(shí)也有很多感受，從對(duì)數(shù)據(jù)挖掘知識(shí)的一無所知，對(duì)C#語言等相關(guān)技術(shù)很不了解的狀態(tài)，我開始了獨(dú)立的學(xué)習(xí)和試驗(yàn)，查看相關(guān)的資料和書籍，讓自己頭腦中模糊的概念逐漸清晰，使自己作品一步步完善起來，每一次改進(jìn)都有進(jìn)步，都是我學(xué)習(xí)的收獲。本次設(shè)計(jì)是在指導(dǎo)老師龐繼芳老師的指導(dǎo)下完成的。在實(shí)驗(yàn)研究的過程中，龐老師給予了指導(dǎo)，并提供了很多與該研究相關(guān)的重要信息，給我以思路上的引導(dǎo)和拓寬，培養(yǎng)

17、了我對(duì)科學(xué)研究的嚴(yán)謹(jǐn)態(tài)度。這將非常有利于我們今后的學(xué)習(xí)和工作。我對(duì)龐繼芳老師表示深深的敬意和由衷的感謝！參考文獻(xiàn)：1Z.Pawlak.Rough Sets J.International Journal of Computer and Information Sciences.1982,11:341-356. 2Z. Pawlak. Rough sets:Theoretical Aspects of Reasoning about Data M.Kluwer Academic Publishers, Boston,1991.3王亞英,邵惠鶴.基于粗糙集理論的規(guī)則知識(shí)獲取技術(shù)J.上海交通大學(xué)學(xué)報(bào)

18、,2000,24(5):638-640.4A. Skowron, J.F. Peteres.Rough sets:Trends and Challenges C.In:G.Y.Wang, Q.Liu, Y.Y.Yao, A.Skow- ron (eds.). Proceedings of 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and GraGranular Computing, Chongqing, China: Springer-Verlag Heidelberg,2003,25-34.5D.

19、Y.Li, B.Zhang, Y.Leung. On knowledge reduction in inconsistent decision information systems J. International Journal of Uncertainty,Fuzziness and Knowledge Based Systems,2004,12(5):651-672.6王國胤. Rough集理論與知識(shí)獲取M.西安:西安交通大學(xué)出版社,2001,11(6):197-203.7梁吉業(yè),曲開社,徐宗本.信息系統(tǒng)的屬性約簡(jiǎn)J.系統(tǒng)工程理論與實(shí)踐,2001,21(12):76-80.8梁吉業(yè),徐

20、宗本,李月香.含度與粗糙集數(shù)據(jù)分析中的度量J.計(jì)算機(jī)學(xué)報(bào),2001,24(5):544-547.9Yi Zhang,Jifang Pang,Jiahua Liang,Yiye Liang.A Method of Knowledge Acquisition Based on the Discernibility Imperfect Information SystemJ.November 18-20,Nanjing,China.Proceeding of 2007 IEEE International Conference on Grey Systems and Intelligent Serv

21、ices,2007,1602-1606.10何偉,劉春亞,趙軍,李華.不完備信息系統(tǒng)下的屬性約簡(jiǎn)算法J.計(jì)算機(jī)科學(xué),2004,31(2):117-119.11張偉,廖曉峰,吳中福.一種基于Rough集理論的不完備數(shù)據(jù)分析方法J.模式識(shí)別與人工智能，2003,16(2):158-162.12黃兵,周獻(xiàn)中.不完備信息系統(tǒng)中基于聯(lián)系度的粗集模型拓展J.系統(tǒng)工程理論與實(shí)踐,2004,11(1)： 88-92.13J.Y.Liang,J.F.Pang,A Measure method for Indiscernibility in Imperfect Information SystemJ,9th Jo

22、int Conference on Information Science,The Splender Kaohsiung,Taiwan,ROC,October8-11,2006, 896-899.14趙衛(wèi)東,曹文彬,戴偉輝.不完全信息下的粗集拓展J.系統(tǒng)工程學(xué)報(bào),2002,17(6):481-485.Design and Implementation of Knowledge Reduction Algorithm Based on the Discernibility in Imperfect Information SystemStudent Name：Jin Yuan Tutor：Pang JifangAbstract Due to imperfect information systems (with missing data or imprecise data) widespread,the research of imperfect