一種快速求核算法

周世睿,郭星

（安徽大學計算機科學技術學院，安徽，合肥 230000）

一種快速求核算法

周世睿,郭星

（安徽大學計算機科學技術學院，安徽，合肥 230000）

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

粗糙集；基數排序；二分法；核

1 引言

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

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

2 基本定義

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

定義2［2］若P?U，且P不等于空集，則P中所有等價關系的交集也是一個等價關系，稱為P上的不可分辨關系，記為IND（P），且有IND（P）=∩［X］R.表示與等價關系族P相關的知識，稱為K中關于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］不可分辨關系，在決策表S=（U,A∪d,V,f）中，定義如下：

定義8新的決策表定義方式：S'=（U',C∪D',V',f'）其中D'=D'∪｛*｝，f'為信息函數滿足?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與轉化后的一致性決策表S'核集具有等價性

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

證明因為mij不為空，根據定理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）

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

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

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

實例分析：

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

去除第九個對象；

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

產生兩個子表S1、S2

S1

S2

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

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

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

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

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

Step3：讀取決策表S內元素個數，記作n.

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

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

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

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

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

Step3時間復雜度為0（U*C）

實驗本文選取了UCI數據庫中中5組數據，分別用葉東毅教授求核方法與本文求核方法進行實驗比較，實驗環境為2.60GHz,2G內存，Window XP操作系統，算法開發在VS2010下進行，實驗結果如下表所示：

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

5.結論

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

〔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］.電子學報，2002，30（7）：1086-1088.

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

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

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

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

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

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

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

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

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

TP181

A

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