不完備決策表屬性約簡(jiǎn)和求核算法.pdf

1、現(xiàn)在在全世界范圍掀起了一股股IT浪潮，例如云計(jì)算和物聯(lián)網(wǎng)的興起、移動(dòng)通信服務(wù)進(jìn)入了4G時(shí)代、大數(shù)據(jù)時(shí)代的到來(lái)等。這些IT革命使人類的工作生活更加便捷和輕松。特別是大數(shù)據(jù)時(shí)代，現(xiàn)在要處理的數(shù)據(jù)都已經(jīng)到PB級(jí)別，這也加大了數(shù)據(jù)處理的難度。粗糙集是一個(gè)優(yōu)秀的數(shù)學(xué)工具，尤其在處理不精確、不完備、不一致數(shù)據(jù)表現(xiàn)突出。粗糙集理論是人工智能與模式識(shí)別共同研究所得到重要研究成果之一。粗糙集的最大特點(diǎn)是不要任何先驗(yàn)知識(shí)，不需要其他額外數(shù)據(jù)信息就可以達(dá)到處

2、理數(shù)據(jù)的目的。
　　屬性約簡(jiǎn)和求核一直都是粗糙集理論的熱門研究重心之一。屬性約簡(jiǎn)的目的是在不改變?cè)紨?shù)據(jù)背后的隱藏規(guī)則和數(shù)據(jù)關(guān)系的前提下，盡可能化簡(jiǎn)原始數(shù)據(jù)。屬性約簡(jiǎn)又劃分成無(wú)核屬性約簡(jiǎn)和有核屬性約簡(jiǎn)。無(wú)核屬性約簡(jiǎn)是根據(jù)某些模型或者啟發(fā)信息來(lái)進(jìn)行約簡(jiǎn)。有核屬性約簡(jiǎn)則是要先在計(jì)算核屬性的基礎(chǔ)上，然后在進(jìn)行約簡(jiǎn)。其實(shí)，核屬性是所有屬性約簡(jiǎn)的交集。因此，求核是非常有意義的研究課題之一。
　　同時(shí)，如今關(guān)于粗糙集的屬性約簡(jiǎn)和求核的探

3、討多半是作用在完備決策表中。在實(shí)際情況中，由于數(shù)據(jù)丟失、信息不確定或者噪聲數(shù)據(jù)影響，使得信息系統(tǒng)中存在空值或者遺漏信息。然而以往的經(jīng)典的屬性約簡(jiǎn)和求核方法已經(jīng)不適用于這種情況。這也導(dǎo)致了研究不完備決策表的屬性約簡(jiǎn)與求核是一種新的趨勢(shì)。王國(guó)胤教授針對(duì)不完備信息系統(tǒng)制定了容差關(guān)系、限制容差關(guān)系、相似關(guān)系等。各國(guó)學(xué)者則使用了正區(qū)域、矩陣、信息量、知識(shí)粒度等方式來(lái)計(jì)算不完備決策表的屬性約簡(jiǎn)和求核。
　　本文首先簡(jiǎn)單介紹了粗糙集的發(fā)展歷程及

4、相關(guān)概念，然后針對(duì)不完備決策表先后使用沖突域和限制容差關(guān)系來(lái)求解屬性約簡(jiǎn)和屬性。下面將從三個(gè)方面論述本文的研究工作:
　　(1)在不完備決策表中的首先用分步計(jì)數(shù)的方法求出容差類，這比之前給出的算法更加高效且易于理解。通過(guò)自己給出的沖突域的定義結(jié)合矩陣思想構(gòu)造出布爾沖突矩陣的模型，然后通過(guò)矩陣的邏輯運(yùn)算和屬性重要度的定義，逐個(gè)找出約簡(jiǎn)后的屬性。這樣的方法相比以往的差別矩陣的屬性約簡(jiǎn)方法是一種創(chuàng)新的方法，在時(shí)間效率也有不錯(cuò)提高。其中新

5、設(shè)計(jì)的算法時(shí)間復(fù)雜度為max{O(|K‖C‖U|)，O(|C|2|POSC(D)‖U|)}，空間復(fù)雜度為O(|C|2|POSC(D)‖U|)。
　　(2)在關(guān)于核屬性研究時(shí)，首先給出了沖突域的定義和在沖突域下的決策表的核屬性判斷方法。通過(guò)相比于普通正區(qū)域，沖突域可以減少元素決策值的比較次數(shù)，這樣在算法效率上有所加強(qiáng)。在此之前，在計(jì)算容差類時(shí)用了鏈?zhǔn)交鶖?shù)排序的方法，這一步大大降低了算法的時(shí)間復(fù)雜度。該求核算法的時(shí)間復(fù)雜度為O(|K‖