一種快速求核算法

周世睿,郭星

（安徽大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，安徽，合肥 230000）

一種快速求核算法

周世睿,郭星

（安徽大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，安徽，合肥 230000）

隨著粗糙集理論在諸多領(lǐng)域的廣泛應(yīng)用，特別是針對(duì)海量數(shù)據(jù)應(yīng)用粗糙集理論，對(duì)于實(shí)時(shí)性有了更高要求，在這種情況下針對(duì)求核與屬性約簡(jiǎn)也提出了更高的要求，目前有許多粗糙集求核算法，但是在時(shí)間復(fù)雜度或者空間復(fù)雜度上都或多或少有著缺陷.本研究利用基數(shù)排序和二分法的思想設(shè)計(jì)了一種快速求核算法，其時(shí)間復(fù)雜度為O（|U||C|2）通過(guò)實(shí)驗(yàn)，證明了算法的正確性和高效性.

粗糙集；基數(shù)排序；二分法；核

1 引言

Rough粗糙集理論是波蘭數(shù)學(xué)家Pawlak［1］在1982年提出的，是一種描述模糊與處理不確定數(shù)學(xué)問(wèn)題的數(shù)學(xué)工具，由于無(wú)需先驗(yàn)知識(shí)，并且可以從規(guī)模巨大的數(shù)據(jù)中挖掘出隱含的信息，被廣泛應(yīng)用于人工智能、模式識(shí)別、數(shù)據(jù)挖掘等領(lǐng)域.啟發(fā)式屬性約簡(jiǎn)算法由于時(shí)間復(fù)雜度低，速度較快，因而應(yīng)用較為廣泛.求核作為常見(jiàn)啟發(fā)式算法的重要步驟，重要程度不言而喻.

Skowron在1995年最早提出了基于差別矩陣的求核算法，Hu［2,3］等人對(duì)此算法加以改進(jìn).葉東毅［4］利用實(shí)例證明了Hu算法在對(duì)不一致決策表求核中存在錯(cuò)誤，在改進(jìn)差別矩陣的基礎(chǔ)上，給出了一個(gè)新的差別矩陣的定義和求核方法；趙軍［5］等基于決策系統(tǒng)的一致性，提出了一種不需要建立差別矩陣的核屬性計(jì)算方法，但是該方法在處理不相容策表時(shí)，具有很大的局限性，為了解決因決策表的不相容性導(dǎo)致所求得的核出現(xiàn)錯(cuò)誤的問(wèn)題，閆德勤等將決策表規(guī)范化后再構(gòu)造差別矩陣，然后利用規(guī)范化后建立的差別矩陣求核屬性，其時(shí)間復(fù)雜度為O（|U||C|2）；楊明［7］提出了一種改進(jìn)的差別矩陣及其求核方法.徐章艷［8］等給出了簡(jiǎn)化的差別矩陣的定義，并設(shè)計(jì)了一種求核算法，算法的時(shí)間復(fù)雜度被降為max（O（|U/C|2|C|）,O（|U||C|）但以上方法均需要?jiǎng)?chuàng)建差別矩陣或者簡(jiǎn)化的差別矩陣,如果樣本的對(duì)象集很大，差別矩陣就要占用很多的空間，增加了計(jì)算量和計(jì)算時(shí)間，影響了計(jì)算效率［11,12］在本論文中的將介紹一種快速求核算法，該算法可以對(duì)不一致粗糙集求核，避免HU算法在不一致粗糙集求核中存在的問(wèn)題，并且有較好的時(shí)間復(fù)雜度.本算法首先對(duì)不一致粗糙集進(jìn)行預(yù)處理，通過(guò)修改不一致決策表內(nèi)決策屬性屬性值，將不一致決策表轉(zhuǎn)化為一致性決策表，并證明該一致性決策表的核屬性等同于不一致決策表核屬性.然后進(jìn)行求核.并通過(guò)UCI數(shù)據(jù)集的實(shí)驗(yàn)證明本文的求核算法有較好的時(shí)間、空間復(fù)雜度.

2 基本定義

定義1［1］稱五元組S=（U,A∪d,V,f）為信息系統(tǒng)，其中U為所有對(duì)象形成的非空有限集合，稱為論域；A為屬性的有限集合，d為決策屬性.

定義2［2］若P?U，且P不等于空集，則P中所有等價(jià)關(guān)系的交集也是一個(gè)等價(jià)關(guān)系，稱為P上的不可分辨關(guān)系，記為IND（P），且有IND（P）=∩［X］R.表示與等價(jià)關(guān)系族P相關(guān)的知識(shí)，稱為K中關(guān)于U的P的基本知識(shí)即P的基本集.為簡(jiǎn)單起見(jiàn)，我們用U/P代替U/IND（P），IND（P）的等價(jià)類稱為知識(shí)的基本概念或基本范疇.

定義3［2］在決策表S中，若對(duì)任意Xi∈U/C,存在Yj∈U/D,使得Xi∈Yj，則S為一致決策表.

定義4［4］葉東毅教授差別矩陣Mij中元素mij定義如下：

定義5［9］在決策表S=（U,A∪d,V,f）中，若POSc（D）=POS （c-｛a｝）（D）,且a∈C，則a稱為C中相對(duì)D不必要的.若POSc （D）≠POS（c-｛a｝）（D），則a稱為C中相對(duì)D必要的.Core（C）是C中所有必要屬性集合，稱為C的核集.

定義6［10］指出決策表核為差別矩陣中所有單個(gè)元素屬性的合集，其求核公式為：

定義7［4］不可分辨關(guān)系，在決策表S=（U,A∪d,V,f）中，定義如下：

定義8新的決策表定義方式：S'=（U',C∪D',V',f'）其中D'=D'∪｛*｝，f'為信息函數(shù)滿足?x∈UC，有如下定義：

顯然，新決策表S'是一個(gè)相容決策表.

定義9決策表分解對(duì)于決策表S=（U,C∪D,V,f）分解為兩個(gè)子表：S1=（U1,C1'∪D,V,f）與子表S2=（U2,C2'∪D,V,f），其中：

3 等價(jià)性證明

3.1 證明原決策表S與轉(zhuǎn)化后的一致性決策表S'核集具有等價(jià)性

葉東毅定義的差別矩陣，求核算法，改進(jìn)了Hu算法不能處理不一致性決策表的問(wèn)題，但時(shí)間空間性能較差.設(shè)Mij為原決策表S根據(jù)定義4轉(zhuǎn)化的差別矩陣，Mij'?｛mij'｝為S'根據(jù)定義8轉(zhuǎn)化的差別矩陣，當(dāng)?mij∈M（mij≠?），?ma,b'=mij且mij'?M'.

證明因?yàn)閙ij不為空，根據(jù)定理1可知：

反之，證明必要性.類似可證.

3.2 證明：決策表S的核集CORE（C）與子表S1、S2核集CORE（C1）CORE（C2）具有等價(jià)性，即CORE（C）=CORE（C1）∪CORE（C2）；該證明可以從兩個(gè)方面進(jìn)行，證明其充分性、必要性；充分性：若?（ci∈C）∧（ci∈CORE（C）則必存在ci∈CORE （C1）∪CORE（C2）

證明根據(jù)定義6，核屬性是差別矩陣中所有單個(gè)元素屬性的集合，決策表S的差別矩陣記作Mij=｛mij｝，則一定有mij=ci，當(dāng)ci∈C1時(shí)，由于mij=ci,即對(duì)象xi、xj在非ci的所有屬性上取值相同，即只有ci能唯一分辨xi、xj兩個(gè)對(duì)象.所以｛xi, xj｝?［xi］C2,|［xi］C2|≠1,所以根據(jù)定義9，xi、xj都屬于U1，所以ci∈CORE（C1），同理當(dāng)ci∈C2時(shí)，有ci∈CORE（C1）；綜上充分性得證.

必要性：若?ci∈CORE（C1）∪CORE（C2）且ci∈C則必存在：（ci∈C）∧（ci∈CORE（C））

證明因?yàn)閏i∈CORE（C1）∪CORE（C2）且ci∈C，當(dāng)ci∈CORE（C1）時(shí)，根據(jù)定義6，核屬性是差別矩陣中所有單個(gè)元素屬性的集合，決策表的S1差別矩陣記作M1ij=｛mij｝，則一定有mij=ci，由于mij=ci,即對(duì)象xi、xj在非ci的所有屬性上取值相同，即只有ci能唯一分辨xi、xj兩個(gè)對(duì)象.此時(shí)f（xi,t1）=f（xj,t1）.根據(jù)定義5，可知U/t1=U/C2；所以f（xi,C2）=f（xj,C2）,綜上此時(shí)ci∈CORE（C1）.當(dāng)ci∈CORE（C2）時(shí)，類似可證，綜上，必要性得證.

實(shí)例分析：

Step1對(duì)于等價(jià)類，取代表元素，去除冗余對(duì)象：

去除第九個(gè)對(duì)象；

添加兩個(gè)新屬性t1、t2，令U/t1=U/C2、U/t2=U/C1根據(jù)定義4：

產(chǎn)生兩個(gè)子表S1、S2

S1

S2

4 算法具體步驟及性能比較分析

輸入：一個(gè)決策表S=（U,C∪D,V,f）,其中U為對(duì)象集合，C為條件屬性集合，D為決策屬性集合.

輸出：決策表S的核集CORE（C）

Step1：利用基數(shù)排序思想,對(duì)U按C生成等價(jià)類｛［x1］C，［x2］C，［x2］C，…［xn］C｝，然后利用定義2，修改決策屬性，將不一致決策表轉(zhuǎn)化為一致決策表.

Step2：刪除一致性決策表中冗余信息.

Step3：讀取決策表S內(nèi)元素個(gè)數(shù)，記作n.

Step3：分別計(jì)算U按C1,C2生成的等價(jià)類，其中

C1=｛c1，c2，c3…cn/2｝，通過(guò)等價(jià)類計(jì)算結(jié)果，按照定義5構(gòu)造決策表S1，S2.

Step4：分別計(jì)算S1，S2的核集，按照定義5得出核集：

時(shí)間復(fù)雜度分析：step1，采用基數(shù)排序思想，劃分等價(jià)類時(shí)間復(fù)雜度為：0（U*C）.

Step2,在每一個(gè)等價(jià)類中提取一個(gè)代表元素，其時(shí)間復(fù)雜度為：0（C）.

Step3時(shí)間復(fù)雜度為0（U*C）

實(shí)驗(yàn)本文選取了UCI數(shù)據(jù)庫(kù)中中5組數(shù)據(jù)，分別用葉東毅教授求核方法與本文求核方法進(jìn)行實(shí)驗(yàn)比較，實(shí)驗(yàn)環(huán)境為2.60GHz,2G內(nèi)存，Window XP操作系統(tǒng)，算法開(kāi)發(fā)在VS2010下進(jìn)行，實(shí)驗(yàn)結(jié)果如下表所示：

數(shù)據(jù)庫(kù)對(duì)象數(shù)目核屬性數(shù)目葉方法時(shí)間本文方法時(shí)間本文方法求核正確率Housing86620.9870.125100% Mushroom8124613.2293.05100% Zoo10120.1370.52100% Car1728615.4637.632100% Solar-Flare103644.1351.072100%

5.結(jié)論

本文將基數(shù)排序與二分法結(jié)合，提出了一種新的求核算法，并通過(guò)例子證明了該算法的正確性.本算法時(shí)間復(fù)雜度為O（|C||U|2）.由于本算法不需求取差別矩陣，空間復(fù)雜度與時(shí)間復(fù)雜度都較優(yōu).

〔1〕Pawlak Z.rough sets［J］.International of computer and information I science，1982，11（5）：341-356.

〔2〕Hu X，Cercone N.Learning in relational databases：.rough set approach［J］Computational intelligence，1995，11（2）：323-338.

〔3〕Skowron A，Rauszer C.The discernibility matrices and functions in information systems［M］/Intelligent Decision Support.Springer Nether lands，1992：331-362.

〔4〕葉東毅，陳昭炯.一個(gè)新的差別矩陣及其求核方法［J］.電子學(xué)報(bào)，2002，30（7）：1086-1088.

〔5〕趙軍，土國(guó)撤，吳中福，等.一種高效的屬性核計(jì)算方法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2003，24（11）：1950-1953.

〔6〕閆德勤，劉菲斐.屬性約簡(jiǎn)中的差別矩陣與近似精度［J］.小型微型計(jì)算機(jī)系統(tǒng)，2005，26（11）：1975-1977.

〔7〕楊明.一種基J飛改進(jìn)差別矩陣的屬性約簡(jiǎn)增量式更新算法［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30（5）：815-822.

〔8〕徐章艷，楊炳儒，宋威.一個(gè)基于差別矩陣的快速求核算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42（6）：4-6.

〔9〕葛浩，李龍澎，楊傳健.向向數(shù)據(jù)刪除的核屬性更新算法［J］.控制與決策，2012，27（5）.

〔10〕蔣瑜，王嘉響.一種快速屬性核求解算法「J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（26）：53-54.

〔11〕錢文彬，楊炳儒，徐章艷，等.一種高效的核屬性動(dòng)態(tài)更新算法［J］.計(jì)算機(jī)科學(xué)，2012，39（7）：210-214.

〔12〕胡秦斌.一種基于決策信息系統(tǒng)的求核屬性算法［J］.微電子學(xué)與計(jì)算機(jī)，2012，29（007）：23-25.

〔13〕張文修，吳偉志，梁吉業(yè)，等.粗糙集理論和方法［M］.北京：科學(xué)出版社，2001.

TP181

A

1673-260X（2015）05-0006-03