哈希快速屬性約簡(jiǎn)算法

1、哈希快速屬性約簡(jiǎn)算法 本課題得到國(guó)家自然科學(xué)基金（60803053, 60675049），浙江省自然科學(xué)基金項(xiàng)目（Y106414），國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目基金（2008AA04Z209），國(guó)家博士后科學(xué)基金（20081459）資助，武器裝備預(yù)研基金（9140A06050609JW0402）資助，劉勇，男，博士，講師，研究方向?yàn)槿斯ぶ悄埽畔⑻幚? E-mail: yongliu. 熊蓉，女，副教授，研究方向?yàn)橹悄軝C(jī)器人. 褚健，男，教授，研究方向?yàn)橹悄芸刂?劉勇 熊蓉 褚?。ㄕ憬髮W(xué)工業(yè)控制國(guó)家重點(diǎn)實(shí)驗(yàn)室 杭州 310027）（浙江大學(xué)智能系統(tǒng)與控制研究所 杭州 310027）摘

2、要 從決策系統(tǒng)的不一致情況出發(fā)，給出了不一致度的概念及其性質(zhì)，并證明了不一致記錄與正區(qū)域的等價(jià)關(guān)系。在此基礎(chǔ)上，提出了基于哈希的正區(qū)域計(jì)算方法，時(shí)間復(fù)雜度下降為O(|U|)，利用不一致情況的性質(zhì)設(shè)計(jì)了一個(gè)基于不一致記錄數(shù)的屬性重要性測(cè)量參數(shù)，用新的測(cè)量參數(shù)設(shè)計(jì)了一個(gè)基于二次哈希的約簡(jiǎn)算法，其復(fù)雜度下降為O(|C|2|U/C|),并證明采用該測(cè)量參數(shù)所獲得約簡(jiǎn)的完備性。最后通過(guò)實(shí)驗(yàn)證明本文正區(qū)域算法和約簡(jiǎn)算法的高效性。關(guān)鍵詞 粗糙集；正區(qū)域；約簡(jiǎn)；哈希; 不一致度中圖分類號(hào) TP18Quick Attribute Reduction Algorithm with HashLIU Yong XIO

3、NG Rong CHU Jian(State Key Lab. of Industrial Control Technology, Zhejiang University, Hangzhou 310027) (Institute of Cyber-Systems and Control, Zhejiang University Hangzhou 310027)Abstract This paper presents the concept and property of inconsistency from the inconsistent condition of decision syst

4、em. It also presents the relationship between the positive region and inconsistent records. A hash based algorithm to calculating positive region has been presented and its temporal complexity decreases to O(|U|). Based on the characteristics of inconsistency, a new attribute measure has been introd

5、uced, then a corresponding reduction algorithm with twice-hash is presented, and its temporal complexity is O(|C|2|U/C|), we also prove this algorithm is complete. The efficiency of our algorithms is proved by the experiments. Keywords rough set; positive region; reduction; hash; inconsistency1 引言求信

6、息系統(tǒng)的約簡(jiǎn)和最小約簡(jiǎn)是粗糙集理論研究中的基本問(wèn)題之一。與其它數(shù)據(jù)降維的方法1, 2相比，使用粗糙集方法進(jìn)行約簡(jiǎn)的優(yōu)勢(shì)在于能夠保持其數(shù)據(jù)本身的語(yǔ)義特征（Semantic features）3。許多學(xué)者都對(duì)屬性約簡(jiǎn)問(wèn)題進(jìn)行過(guò)研究3-9，其中已經(jīng)公認(rèn)的結(jié)論是求解信息系統(tǒng)最短約簡(jiǎn)是一個(gè)NP難問(wèn)題8。通常情況下，約簡(jiǎn)算法并不需要計(jì)算出信息系統(tǒng)的所有約簡(jiǎn)，僅需獲得用戶感興趣或者可用的約簡(jiǎn)即可。依據(jù)粗糙集理論中獲取約簡(jiǎn)方法的不同，常用的計(jì)算方法有Greedy法和差別矩陣法。在Greedy法5中，待求約簡(jiǎn)集通常初始化為核（Core）5,10或空集（NULL）3，然后依次掃描剩下的屬性，從中選取一個(gè)使得分類質(zhì)

7、量增益最大的屬性，并把該屬性加入到待求約簡(jiǎn)集中，直到當(dāng)前候選集計(jì)算出的分類質(zhì)量等于所有條件屬性計(jì)算出的分類質(zhì)量。差別矩陣（也稱為差異矩陣或分明矩陣、區(qū)分矩陣）法11-13，首先計(jì)算數(shù)據(jù)集的差別矩陣和差別函數(shù)，然后通過(guò)求差別矩陣中所有項(xiàng)的最小析取范式來(lái)獲得約簡(jiǎn)。該算法的優(yōu)點(diǎn)在于直觀，易于理解，而且能夠很容易地計(jì)算出核與所有約簡(jiǎn)。但這個(gè)算法也存在著不足之處，即，由于在矩陣中會(huì)出現(xiàn)大量的重復(fù)元素（或元素之間存在著包含關(guān)系），這就大大降低了屬性約簡(jiǎn)算法的效率。通常此類算法的復(fù)雜度為，其中|C|為屬性個(gè)數(shù)，|U|為數(shù)據(jù)紀(jì)錄數(shù)。上述約簡(jiǎn)方法中差別矩陣方法計(jì)算過(guò)程需耗費(fèi)巨大的時(shí)間和空間，故不常采用。其它方法

8、中都需要頻繁計(jì)算決策表的正區(qū)域，因而計(jì)算正區(qū)域的時(shí)間復(fù)雜度直接決定了約簡(jiǎn)算法的時(shí)間復(fù)雜度。通常采用的正區(qū)域計(jì)算方法時(shí)間復(fù)雜度為，文獻(xiàn)14中基于快速排序思想給出了一種快速求解正區(qū)域算法，其時(shí)間復(fù)雜度可降為。在此基礎(chǔ)上文獻(xiàn)15中類似的提出了一種基數(shù)排序的計(jì)算正區(qū)域算法，其時(shí)間復(fù)雜度下降至。在本文的屬性約簡(jiǎn)算法中，提出了一種基于哈希表的正區(qū)域計(jì)算方法，能夠?qū)r(shí)間復(fù)雜度降為。在對(duì)采用正區(qū)域作為啟發(fā)式搜索條件的約簡(jiǎn)算法進(jìn)行充分分析后，給出了一個(gè)適用于哈希方法計(jì)算的屬性重要性度量參數(shù)，并基于此參數(shù)設(shè)計(jì)了一個(gè)完備二次哈希屬性約簡(jiǎn)算法，將時(shí)間復(fù)雜度下降到，并通過(guò)實(shí)驗(yàn)和分析證明本文算法的高效性。本文第2節(jié)介紹相

9、關(guān)的基本概念及不一致的定義和性質(zhì)，證明了不一致記錄數(shù)與正區(qū)域間的等價(jià)性；第3節(jié)中介紹了基于哈希表的快速正區(qū)域計(jì)算方法，并且給出其時(shí)間復(fù)雜度分析；第4節(jié)提出了一個(gè)建立在不一致性質(zhì)上的二次哈?？焖賹傩约s簡(jiǎn)算法，并通過(guò)實(shí)例予以說(shuō)明；第5節(jié)通過(guò)實(shí)驗(yàn)證明本文算法的高效性；最后給出結(jié)論和展望。2 不一致的定義及其性質(zhì)屬性約簡(jiǎn)11過(guò)程實(shí)際上是尋找一個(gè)屬性子集，使該子集能夠保有與原條件屬性集合相同的記錄辨識(shí)能力。因而其本質(zhì)上是通過(guò)分類能力來(lái)衡量屬性子集是否構(gòu)成一個(gè)約簡(jiǎn)。正區(qū)域11的定義恰好描述一個(gè)屬性子集能夠辨別區(qū)分的記錄數(shù)。從條件屬性集區(qū)分紀(jì)錄的能力考慮，給出如下定義：定義1 不一致 信息系統(tǒng)U（C，D）中

10、，C為條件屬性集，D為決策屬性集，若且有，則稱此時(shí)與之間在屬性P上存在不一致情況，若，此時(shí)的U也稱為不一致信息系統(tǒng)。定義2 不一致記錄數(shù)/不一致記錄信息系統(tǒng) 信息系統(tǒng)U（C，D）中，C為條件屬性集，D為決策屬性集，若有，記屬性集P的在上不一致記錄數(shù)為（通常時(shí)，可簡(jiǎn)寫(xiě)為），計(jì)算如下：， 是在屬性P上存在不一致情況的等價(jià)類，若。我們將U中所有在P上的不一致記錄構(gòu)成的信息系統(tǒng)稱為相對(duì)屬性P的不一致記錄信息系統(tǒng)，記為。即有 ，若。這里顯然有。在給出了不一致情況的相關(guān)定義后，可得如下幾個(gè)性質(zhì)：性質(zhì) 1信息系統(tǒng)U（C，D）中，C為條件屬性集，D為決策屬性集，信息系統(tǒng)U(Q，D) 是一致的（consiste

11、nt）當(dāng)且僅當(dāng)。證明：若信息系統(tǒng)U(Q，D) 是一致的（consistent）則顯然有，反過(guò)來(lái)若，根據(jù)不一致記錄數(shù)的定義，表明信息系統(tǒng)中無(wú)不一致情況，即信息系統(tǒng)是一致的。性質(zhì) 2信息系統(tǒng)U（C，D）中，C為條件屬性集，D為決策屬性集，當(dāng)且僅當(dāng)。證明：根據(jù)定義有，也就是在信息系統(tǒng)U（C，D）中有這里由可得對(duì)任意的有，且，對(duì)于的等價(jià)類則表明E中存在不一致情況，故U/ P中的等價(jià)類可以分為兩種，一種是屬于，另外一種是不屬存在不一致情況的等價(jià)類。故有即同樣可得故，若顯然有。通過(guò)上面給出的性質(zhì)，可得如下定理：定理 1信息系統(tǒng)U（C，D）中，C為條件屬性集，D為決策屬性集，R是C的一個(gè)約簡(jiǎn)，當(dāng)且僅當(dāng)，且有

12、。證明：由性質(zhì)2可得 即，且有，故R是C的一個(gè)約簡(jiǎn)。3 正區(qū)域快速計(jì)算方法由上節(jié)中的不一致定義和性質(zhì)可知，正區(qū)域可通過(guò)計(jì)算不一致紀(jì)錄數(shù)間接獲得，即。式中|U|為常數(shù)，故只需計(jì)算不一致紀(jì)錄數(shù)。通常正區(qū)域計(jì)算方法需逐個(gè)比較U中紀(jì)錄的每一屬性是否都相同，若相同則歸入同一等價(jià)類，再比較其決策是否相同，以獲得決策一致的等價(jià)類，從而計(jì)算出正區(qū)域，其時(shí)間復(fù)雜度達(dá)到。文獻(xiàn)15中采用基數(shù)排序思想設(shè)計(jì)的算法能夠?qū)?fù)雜度下降為，但是此算法需預(yù)先統(tǒng)計(jì)每一個(gè)屬性的取值范圍，并多次遍歷決策表。本文中根據(jù)不一致紀(jì)錄數(shù)與正區(qū)域的計(jì)算關(guān)系，設(shè)計(jì)了一個(gè)通過(guò)哈希表來(lái)實(shí)現(xiàn)的正區(qū)域計(jì)算方法，其時(shí)間復(fù)雜度可控制在。算法 1. 計(jì)算正區(qū)域

13、輸入：信息系統(tǒng)，屬性集合R，輸出： 和1 Count=0, 初始化哈希表 H（）2 對(duì)每一 有如下操作2.1 / 將紀(jì)錄放入對(duì)應(yīng)哈希到的表分項(xiàng)中，2.2 2.3 若 ， /比較是決策是否相等，即是否一致3 對(duì)每一 /遍歷哈希表，計(jì)算正區(qū)域記錄數(shù)3.1若 ，Count = Count + 4返回計(jì)數(shù)Count , 哈希表H，算法結(jié)束。其中為哈希編碼計(jì)算函數(shù)，計(jì)算紀(jì)錄在屬性集R上的編碼值，實(shí)現(xiàn)過(guò)程中可直接取紀(jì)錄在屬性R上所有取值的并，即 。H表示哈希表，是哈希表中當(dāng)前紀(jì)錄命中項(xiàng)，步2.1中對(duì)進(jìn)行hash后將紀(jì)錄加入到哈希表的對(duì)應(yīng)分項(xiàng)中，同時(shí)遞增分項(xiàng)計(jì)數(shù)（步2.2），以及檢測(cè)是否存在不一致情況（步2

14、.3）。 算法步1至步2完成對(duì)U遍歷一次，將每一條紀(jì)錄hash至對(duì)應(yīng)的分項(xiàng)（即等價(jià)類），其時(shí)間復(fù)雜度為O（|U|）。步1中的哈希表的初始化可放在哈希表中的項(xiàng)第一次命中時(shí)，其總時(shí)間耗費(fèi)為。步3對(duì)哈希表遍歷完成正區(qū)域的計(jì)算，其時(shí)間復(fù)雜度為，故算法1的總時(shí)間復(fù)雜度為O（|U|）。 表1 信息系統(tǒng)abcDX11110X21232X32320X43121X51111X61232對(duì)表1所示的決策表中6個(gè)對(duì)象，用算法1計(jì)算計(jì)算，過(guò)程如下：對(duì)U中紀(jì)錄，例如X1，hash（X1）= 111，做hash操作后有，依次遍歷完記錄后，可得如下圖的哈希表。圖1 遍歷完成后的哈希表H再對(duì)H遍歷即可得為 X2, X6, X

15、3, X4。4 二次哈希屬性約簡(jiǎn)算法4.1 屬性重要性參數(shù)及其計(jì)算定理1說(shuō)明屬性約簡(jiǎn)過(guò)程可建立在對(duì)信息系統(tǒng)中不一致情況的判定基礎(chǔ)上。若能夠找到一個(gè)屬性子集，使用該集合獲得的不一致紀(jì)錄數(shù)等于采用全部屬性計(jì)算得到的不一致記錄數(shù)，則此屬性子集是信息系統(tǒng)的一個(gè)約簡(jiǎn)或其子集中包含有約簡(jiǎn)。據(jù)此可以設(shè)計(jì)出本文約簡(jiǎn)算法的搜索判定參數(shù)。此外，對(duì)于本文的屬性重要性參數(shù)也可采用文獻(xiàn)14，15中的搜索空間遞減方法，以期提高算法效率?；诓灰恢碌亩x和性質(zhì)，本文給出一個(gè)新的屬性重要性參數(shù)如下：定義 3 基于不一致記錄數(shù)的屬性重要性參數(shù) 信息系統(tǒng)U (C,D)中，的重要性定義為，其中為相對(duì)屬性P的不一致記錄信息系統(tǒng)。定理

16、 2 信息系統(tǒng)U（ C , D）中， ，若，則是信息系統(tǒng)的一個(gè)約簡(jiǎn)或其子集中包含有信息系統(tǒng)的約簡(jiǎn)。證明，若，此時(shí)，即，由性質(zhì)2和約簡(jiǎn)的定義可得是信息系統(tǒng)的一個(gè)約簡(jiǎn)。若，此時(shí)，此處，表示是屬性集R相對(duì)于決策D在信息系統(tǒng)上的正區(qū)域。由不一致記錄信息系統(tǒng)的定義可得：，即可得，由已知條件 且 可得即，由正區(qū)域的定義及性質(zhì)有如下式子由的定義這里顯然有由上可得故可得為信息系統(tǒng)約簡(jiǎn)，或其子集中包含信息系統(tǒng)約簡(jiǎn)，證明完畢。上述定義中的屬性重要性，可直觀上理解為屬性未能夠區(qū)分的記錄數(shù)。根據(jù)約簡(jiǎn)定義，未能夠區(qū)分的記錄數(shù)越少越好，故本文中的屬性重要性值越小代表屬性的重要程度越高。此外，在屬性重要性計(jì)算過(guò)程中，沒(méi)有采

17、用U作為每次的搜索空間，而是采用了相對(duì)屬性集P的不一致記錄信息系統(tǒng)作為搜索空間。這是因?yàn)?，?duì)于屬性P已經(jīng)可以區(qū)分的數(shù)據(jù)記錄來(lái)說(shuō)，增加一個(gè)新的屬性a后其仍然是可被區(qū)分的，此部分不會(huì)對(duì)未區(qū)分記錄數(shù)構(gòu)成影響?；诖它c(diǎn)，僅需考慮屬性P未能區(qū)分的信息系統(tǒng)，可大大減少搜索范圍，提高算法效率。下面給出可遞歸的屬性重要性參數(shù)計(jì)算方法。算法2 計(jì)算屬性重要參數(shù)輸入：對(duì)信息系統(tǒng)U(C, D)中屬性C，調(diào)用算法1后的哈希表輸出：1. INS=0, 初始化新的哈希表,（）2. 對(duì)輸入哈希表中的每一項(xiàng)進(jìn)行如下操作2.1 / 將H作為紀(jì)錄放入哈希到的表分項(xiàng)中，2.2 / 加上H中所包含記錄數(shù)2.3 若，2.4 若，/ 如

18、H自身是存在不一致的等價(jià)類3.遍歷中的每一個(gè)哈希項(xiàng)4.若，對(duì)中每一項(xiàng)進(jìn)行如下操作4.1 4.2 / 加上H中所包含記錄數(shù)4.3 若， / 新等價(jià)類中有不一致4.4 若，/ H自身是存在不一致的等價(jià)類5.遍歷中每一個(gè)哈希項(xiàng)5.1若 ，INS =INS + 6.返回INS值。算法2中求SGF的過(guò)程是將全部條件屬性C進(jìn)行哈希后的哈希表項(xiàng)作為輸入重新進(jìn)行哈希計(jì)算，易得步2的復(fù)雜度為，步3和4的復(fù)雜度為，步5的復(fù)雜度為，故算法復(fù)雜度為，即。 進(jìn)一步分析可知，算法2中步2的計(jì)算復(fù)雜度最高，其目的是計(jì)算和，而在此兩項(xiàng)已知的情況下計(jì)算復(fù)雜度可下降到，因此可以考慮將約簡(jiǎn)算法設(shè)計(jì)為逐步遞增計(jì)算，即在保留的基礎(chǔ)上計(jì)

19、算。4.2 約簡(jiǎn)算法約簡(jiǎn)算法給出如下，算法3二次哈希快速屬性約簡(jiǎn)算法輸入：信息系統(tǒng)輸出：C相對(duì)D的某個(gè)約簡(jiǎn)1. 置為空集合2. 用算法1計(jì)算，。3. 對(duì)每一個(gè)屬性，有如下操作4. 計(jì)算屬性重要性參數(shù) 5. 在CR中找出使得SGF(R, a) 取值最小的屬性值(若存在多個(gè)這樣的屬性則任選一個(gè))，并記，6. 將加入中，即7. 若，轉(zhuǎn)步驟3，否則繼續(xù)8. 從R的尾部開(kāi)始從后往前對(duì)每個(gè)屬性b進(jìn)行判斷是否可省，若則說(shuō)明b是可省的，從R中把b刪除。9. 否則算法結(jié)束，返回R。上述約簡(jiǎn)算法首先對(duì)原決策表哈希（步2），然后在此結(jié)果上再次通過(guò)哈希來(lái)計(jì)算約簡(jiǎn)，因而稱之為二次哈希約簡(jiǎn)算法。下面給出算法的正確性分析，

20、算法的終止條件為， 即R所不能區(qū)分的記錄數(shù)等于C所不能區(qū)分的記錄數(shù)，由定理2可知，此條件是充分的，故此時(shí)的R是信息系統(tǒng)的一個(gè)約簡(jiǎn)或者包括了約簡(jiǎn)，可通過(guò)步驟8來(lái)消除冗余屬性獲得最終約簡(jiǎn)。算法復(fù)雜度分析如下，步2中計(jì)算所需時(shí)間為，由算法2中分析可得步4中計(jì)算一次需要的時(shí)間復(fù)雜度為，從而步3至步7計(jì)算的最差時(shí)間復(fù)雜度為，步驟8最壞情況下時(shí)間復(fù)雜度為，因而算法總的時(shí)間復(fù)雜度為，即。下面以表1中的數(shù)據(jù)為例說(shuō)明算法3的執(zhí)行過(guò)程，決策表經(jīng)第一次哈希后的結(jié)構(gòu)如圖1所示，對(duì)表1中數(shù)據(jù)執(zhí)行算法3的步2后可得如下表2的以哈希項(xiàng)為單位的信息系統(tǒng)。此后在表2上繼續(xù)哈希，由算法3的第3，4步可得如下的哈希表： = h1,

21、 h2, cons=false, count=4, h3, cons=true, count=1, h4, cons=true, count=1, SGF(a) = 4. = h1, h4, cons=false, count=3, h2, cons=true, count=2, h3, cons=true, count=1, SGF(b) = 3. = h1, cons=false, count=2, h2, cons=true, count=2, h3, h4, cons=false, count=2, SGF(a) = 4.由算法3的步5取獲得最小SGF的屬性b，Rb, . 轉(zhuǎn)算法步3，

22、哈希后有= h1, cons=false, count=2, h4, cons=true, count=1, SGF(a，b) =2.= h1, cons=false, count=2, h4, cons=true, count=1, SGF(a，b) =2.信息系統(tǒng)中，故此時(shí)a,b和b,c都是信息系統(tǒng)的約簡(jiǎn)。表2 第一次哈希后的決策表abcDConsCounth11110False2h21232True2h32320True1h43121True15 實(shí)驗(yàn)及結(jié)果分析本節(jié)中采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中數(shù)據(jù)，如表3所示，在PC（Dell GX520，1G內(nèi)存，windows XP， Intel P

23、4 2.8GHZ）上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)一采用本文中算法和文獻(xiàn)15以及文獻(xiàn)16中的Semi-minimal Reduct算法（即Johnson Reduct Algorithm）進(jìn)行屬性約簡(jiǎn)，上述三種算法皆采用JAVA語(yǔ)言實(shí)現(xiàn)，運(yùn)行在同一系統(tǒng)硬件/軟件平臺(tái)下，且每種算法運(yùn)行10次，分別去除最初一次和和最后一次的運(yùn)算結(jié)果，對(duì)中間8次的運(yùn)行結(jié)果取平均值。實(shí)驗(yàn)結(jié)果如表3所示。其中POSC(D)表示計(jì)算正區(qū)域的時(shí)間。表3 約簡(jiǎn)算法執(zhí)行時(shí)間對(duì)比數(shù)據(jù)集實(shí)例數(shù)屬性數(shù)本文方法（ms）Semi-minimal Reduct（ms）文獻(xiàn)15算法（ms）約簡(jiǎn)POSC(D)約簡(jiǎn)POSC(D)約簡(jiǎn)POSC(D)Mushroo

24、m812422235910477591576703153Vote43516182145034063Tic-tac-toe9589125320271886為進(jìn)一步對(duì)比本文提出的正域計(jì)算方法與其它計(jì)算方法的性能差異，設(shè)計(jì)了第二個(gè)實(shí)驗(yàn)。實(shí)驗(yàn)二在實(shí)驗(yàn)一相同的硬件軟件環(huán)境下實(shí)現(xiàn)了Jensen的Quickreduct算法3，算法中正域的計(jì)算方法分別采用本文的哈希方法和文獻(xiàn)16中的快速排序方法。實(shí)驗(yàn)結(jié)果如下：表4相同約簡(jiǎn)策略下不同正區(qū)域算法性能對(duì)比數(shù)據(jù)集實(shí)例數(shù)屬性數(shù)哈希（ms）快速排序（ms）約簡(jiǎn)POSC(D)約簡(jiǎn)POSC(D)lung-cancer3257471581German-credit100021

25、78313910pendigits109921746271116281139letter20000172135520226297232從表3和表4可以看出，本文的哈希約簡(jiǎn)方法無(wú)論在約簡(jiǎn)還是在單個(gè)正區(qū)域計(jì)算上性能都優(yōu)于文獻(xiàn)15和semi-minimal reduct方法。本文方法和文獻(xiàn)15中算法在時(shí)間復(fù)雜度上同為，但是本文中采用的哈希表數(shù)據(jù)結(jié)構(gòu)能夠更有效的減少計(jì)算量，具體原因分析如下： 1. 在哈希過(guò)程天然可劃分好等價(jià)類，不需要文獻(xiàn)15中算法1的步4來(lái)搜索等價(jià)類（約O（|C|U|）的復(fù)雜度耗費(fèi)）；2. 在哈希時(shí)通過(guò)一次比較操作，直接可以得知當(dāng)前等價(jià)類是否可歸于正區(qū)域內(nèi)，不需要額外的計(jì)算，也不需要

26、額外的開(kāi)銷來(lái)維護(hù)正區(qū)域和負(fù)區(qū)域記錄集；3. 哈希表中的哈希項(xiàng)（）可以直接作為基本處理單元（類似文15中簡(jiǎn)化決策表的項(xiàng)）重新哈希，效率得到提高。4. 文獻(xiàn)15中的算法2需要判斷等價(jià)類是否被包含在負(fù)區(qū)域或者正區(qū)域集中，帶來(lái)了大量額外運(yùn)算。綜上所述，哈希表的存儲(chǔ)結(jié)構(gòu)和操作效率要明顯好于文獻(xiàn)15中采用的離散雙向鏈表數(shù)據(jù)管理方式。此外本文算法是一個(gè)完備的屬性約簡(jiǎn)算法，能夠嚴(yán)格保證計(jì)算結(jié)果為約簡(jiǎn)?；谏厦娴膶?shí)驗(yàn)結(jié)果和分析表明本文算法是可靠高效的，且尤其適用于海量數(shù)據(jù)約簡(jiǎn)。6 總結(jié)與展望約簡(jiǎn)是粗糙集理論中的一個(gè)重要研究部分，但是由于約簡(jiǎn)計(jì)算的復(fù)雜性，限制了其在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域的應(yīng)用和推廣。因而研究快

27、速高效的約簡(jiǎn)算法對(duì)粗糙集理論的應(yīng)用和推廣有著極其重大的意義?，F(xiàn)有約簡(jiǎn)算法中，或需數(shù)據(jù)集保持一致，或計(jì)算效率過(guò)低，很大程度上限制了約簡(jiǎn)算法的應(yīng)用。實(shí)際問(wèn)題中的數(shù)據(jù)集很多都難以保證其一致性，并且由于誤差或干擾等因素造成的數(shù)據(jù)不一致情況也非常普遍，因而需要約簡(jiǎn)算法在能夠很好的支持不一致數(shù)據(jù)的同時(shí)具有良好的計(jì)算效率。本文從數(shù)據(jù)不一致性出發(fā)，證明了決策系統(tǒng)中不一致情況與正區(qū)域的等價(jià)關(guān)系，并在此基礎(chǔ)上給出一個(gè)基于不一致記錄數(shù)的二次哈希快速約簡(jiǎn)算法，該算法通過(guò)掃描數(shù)據(jù)集中的不一致情況從而計(jì)算約簡(jiǎn)。算法具有如下優(yōu)點(diǎn):1. 能夠非常好地支持不一致數(shù)據(jù)，可處理因噪音干擾等因素所形成的不一致數(shù)據(jù)集。2能夠有效去除冗

28、余無(wú)關(guān)屬性，保證輸出約簡(jiǎn)的完備性。3掃描獲得不一致數(shù)和計(jì)算正區(qū)域的時(shí)間復(fù)雜度為O（|U|），整個(gè)約簡(jiǎn)算法復(fù)雜度控制在之內(nèi)，能夠大大降低算法時(shí)間耗費(fèi)。在未來(lái)的工作中將進(jìn)一步考慮約簡(jiǎn)算法在數(shù)據(jù)特征選擇中的應(yīng)用，利用約簡(jiǎn)后的結(jié)果來(lái)構(gòu)建機(jī)器學(xué)習(xí)中的分類器，達(dá)到提高分類器泛化能力的目的。 參考文獻(xiàn)1. Kira K., Rendell L. A. The feature selection problem: traditional methods and a new algorithm/Proceedings of the Ninth International Workshop on Machine

29、Learning (ML 1992), Aberdeen, Scotland, UK, 1992: 129-134.2. Blum A., Langley P. Selection of relevant features and examples in machine learning. Artificial Intelligence, 1997, 97(1-2): 245-271.3. Jensen R., Shen Q. Semantics-preserving dimensionality reduction: rough and fuzzy-rough-based approache

30、s. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12): 1457-1471.4. Chouchoulas A., Shen Q. Rough set-aided keyword reduction for text categorization. Applied Artificial Intelligence, 2001, 15(9): 843-873.5. Hu X. H. Knowledge discovery in database: an attribute-oriented rough set app

31、roach D. Regina, Canada: University of Regina, 1995.6. Jelonek J., Krawiec K., Slowinski R., Rough set reduction of attributes and their domains for neural networks. Computational Intelligence, 1995, 11: 339-347.7. Lin T. Y., Yin P. Heuristically Fast Finding of the Shortest Reducts/Rough Sets and C

32、urrent Trends in Computing(RSCTC2004), Uppsala, Sweden, 2004: 465-470.8. Skowron A., Rauszer C. The discernibility matrices and functions in information systems / R. Slowinski. Intelligent Decision Support: Handbook of Applications and Advances to Rough Sets Theory. Dordrecht: Kluwer Academic, 1992:

33、 331-362.9. Swiniarski R.W., Skowron A. Rough set methods in feature selection and recognition, Pattern Recognition Letters, 2003, 24(6): 833-849.10. Zhong N., Dong J., Ohsuga S. Using rough sets with heuristics for feature selection, Journal of Intelligent Information System, 2001, 16(3): 199-214.1

34、1. Pawlak, Z., Rough sets: theoretical aspects and reasoning about data. Dordrecht: Kluwer Academic Publishers, 1991.12. Zhang Wen-Xiu, Mi Ju-Sheng, Wu Wei-Zhi. Approaches to knowledge reductions in inconsistent systems. International Journal of Intelligent System, 2003, 18(9): 989-1000.13. Zhang We

35、n-Xiu, Mi Ju-Sheng, Wu Wei-Zhi. Knowledge reductions in inconsistent information systems. Chinese Journal of Computers, 2003, 26(1): 12-18.(張文修,米據(jù)生,吳偉志.不協(xié)調(diào)目標(biāo)信息系統(tǒng)的知識(shí)約簡(jiǎn). 計(jì)算機(jī)學(xué)報(bào), 2003, 26(1): 1218.)14. Liu Shao-Hui, Sheng Qiu-Jian, Wu Bin, Shi Zhong-Zhi, Hu Fei. Research on efficient algorithms for roug

36、h set methods. Chinese Journal of Computers, 2003, 26(5): 524-529.(劉少輝, 盛秋戩, 吳斌, 史忠植, 胡斐. Rough集高效算法的研究. 計(jì)算機(jī)學(xué)報(bào), 2003, 26(5): 524-529.)15. Xu Zhang-Yan, Liu Zuo-Peng, Yang Bing-Ru, Song Wei. A quick attribute reduction algorithm with complexity of max(O(|C|U|),O(|C|2|U/C|), Chinese Journal of Compute

37、rs, 2006, 29(3):391-399.(徐章艷, 劉作鵬, 楊炳儒, 宋威. 一個(gè)復(fù)雜度為max (O(|C|U|), O(|C|2|U/C|)的快速屬性約簡(jiǎn)算法. 計(jì)算機(jī)學(xué)報(bào), 2006, 29(3):391-399.)16. Nguyen S. H. Some efficient algorithms for rough set methods /Proceedings of the conference on Information Processing and Managements of Uncertainty in Knowledge Based Systems(IPMU

38、1996), Granada, Spain, 1996: 1451-1456.BackgroundThe attribute reduction is one of the most important concepts in rough set theory. With the attribute reduction, the irrelevant attributes can be removed from the original attribute set and the remained attributes can keep the discriminability as same

39、 as the original attribute set and also keep the internal semantic correlations among attributes. The attribute reduction has been widely used in data mining, which normally needs to deal with very large data set, so a fast and easy attribute reduction algorithm is especially important when implemen

40、ting the reduction concept in data mining applications with huge data sets. The mainly reduction algorithms fall in two categories: the discernibility matrix based approaches and positive region based approaches. The previous approaches are almost not able to implement in large data set condition du

41、e to the huge spatial requirement; and the latter approaches need to calculate the positive region iteratively. The procedure of positive region is a calculation intensive and tactical task. With the increasing of the attribute dimension and the number of instances, the processing time for positive region has grown tremendously. So it is significant to present a fast positive region method in attribute reduction algo