周世睿,郭星

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

一種快速求核算法

周世睿,郭星

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

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

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

1 引言

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

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

2 基本定義

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

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

定義3［2］在決策表S中，若對任意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中相對D不必要的.若POSc （D）≠POS（c-｛a｝）（D），則a稱為C中相對D必要的.Core（C）是C中所有必要屬性集合，稱為C的核集.

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

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

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

顯然，新決策表S'是一個相容決策表.

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

3 等價性證明

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

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

證明因為mij不為空，根據(jù)定理1可知：

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

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

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

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

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

實例分析：

Step1對于等價類，取代表元素，去除冗余對象：

去除第九個對象；

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

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

S1

S2

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

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

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

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

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

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

Step3：分別計算U按C1,C2生成的等價類，其中

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

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

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

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

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

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

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

5.結(jié)論

本文將基數(shù)排序與二分法結(jié)合，提出了一種新的求核算法，并通過例子證明了該算法的正確性.本算法時間復(fù)雜度為O（|C||U|2）.由于本算法不需求取差別矩陣，空間復(fù)雜度與時間復(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〕葉東毅，陳昭炯.一個新的差別矩陣及其求核方法［J］.電子學(xué)報，2002，30（7）：1086-1088.

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

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

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

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

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

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

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

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

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

TP181

A

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