一種啟發(fā)信息遺傳算法的粗糙集屬性約簡算法

孫宇航　常晉義　謝從華

摘要：屬性約簡在粗糙集理論研究中一直占據(jù)重要位置。為了能夠更加快速有效的獲得決策表中屬性的最優(yōu)約簡，提出了一種新的啟發(fā)信息遺傳算法的粗糙集屬性約簡算法。引入屬性頻率作為啟發(fā)式信息構(gòu)造適應(yīng)度函數(shù)，相比于傳統(tǒng)矩陣方法，減少了大量矩陣操作。在交叉操作時(shí)，基于屬性重要度的特性，引入判別屬性相似度這一操作，父代相似個(gè)體不進(jìn)行交叉，避免了不必要的個(gè)體交叉。實(shí)驗(yàn)結(jié)果表明，該算法比傳統(tǒng)方法更準(zhǔn)確的獲得關(guān)鍵屬性，且迭代的次數(shù)更少，能更有效地約簡屬性。

關(guān)鍵詞：粗糙集；屬性約簡；遺傳算法；屬性頻率；屬性相似度

中圖分類號(hào) TP391 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào)：1009-3044（2015）07-0281-05

Abstract： Attribute reduction is a key problem for the rough set theory. In order to be more effective to obtain the minimal attribute reduction， the paper put forward a new attribute reduction algorithm based on GA， In the fitness selection， proposing the attribute frequency as the heuristic information， compared to the traditional matrix method， it has reduced the amount of operation. In the crossover operation， introducing the distinguishing attribute similarity which based on the importance of attribute in the crossover operation， so similar parents do not cross， so as to avoid unnecessary individual cross. The experimental results show that， the algorithm can not only obtain the excellent properties more accurately， but also can reduce the number of iterations， it can quickly and effectively to attribute reduction.

Key words： rough set； attribute reduction； genetic algorithm； attribute frequency； attribute similarity

粗糙集[1]是由波蘭Pawlak教授于1982年提出的一種對(duì)復(fù)雜數(shù)據(jù)進(jìn)行分析的理論，主要用于處理不確定性、模糊的知識(shí)。其優(yōu)點(diǎn)在于處理問題時(shí)，不需要任何先驗(yàn)信息，只需提供需要處理的數(shù)據(jù)集本身，因此在數(shù)據(jù)挖掘、決策分析、模式識(shí)別等領(lǐng)域[2]都可見其身影。

決策系統(tǒng)的屬性約簡是一直是粗糙集中研究的重點(diǎn)[3]。在決策系統(tǒng)中，每個(gè)條件屬性相對(duì)于最后的決策，重要性不會(huì)完全相同，甚至?xí)腥哂鄬傩?。屬性約簡就是，保留重要屬性、刪除冗余屬性，保持系統(tǒng)分類和決策能力不變或增強(qiáng)的情況下，使問題最終決策和規(guī)則分類 [3]更加簡易明確。

屬性約簡已被證明是一個(gè)NP難題。如今，常用的屬性約簡方法有：基于Pawlak屬性重要度、基于決策系統(tǒng)的差別矩陣、基于條件信息熵等[3]，但這些方法會(huì)經(jīng)常陷入某些屬性極值（局部最優(yōu)）而不能求得最優(yōu)解，同時(shí)，在約簡過程中，隨決策系統(tǒng)的增大，算法計(jì)算的復(fù)雜性呈指數(shù)增長，對(duì)于數(shù)據(jù)量大的高維數(shù)據(jù)，操作復(fù)雜，資源消耗多，不易求得最優(yōu)解。

遺傳算法是模擬生物演化過程中選擇、淘汰的計(jì)算模型。由美國J.Holland教授于1975年首次提出[4]，具有自組織性、自適應(yīng)和自學(xué)習(xí)性，并且內(nèi)在并行。其求解方式并不是單一或者線性的，它將解空間所有的個(gè)體作為可行解，根據(jù)“優(yōu)勝劣汰”準(zhǔn)則，進(jìn)行整體尋優(yōu)。由于其本身具有的全局尋優(yōu)的特性，因此經(jīng)常被用于幫助解決規(guī)模大、非線性的復(fù)雜問題。

比較粗糙集和遺傳算法各自的特點(diǎn)，可以將二者結(jié)合起來，在遺傳算法基礎(chǔ)上對(duì)粗糙集進(jìn)行屬性約簡 [6-14]。本文提出一種啟發(fā)信息遺傳算法對(duì)粗糙集進(jìn)行屬性約簡，該算法通過在遺傳算法的適應(yīng)度函數(shù)中引入屬性頻度作為啟發(fā)信息、在交叉操作中進(jìn)行屬性相似度的判斷等操作，明顯改善了算法獲得最優(yōu)屬性的效率。實(shí)驗(yàn)結(jié)果表明，此方法快速、有效，能很好的獲得決策系統(tǒng)最小屬性約簡集。

1 粗糙集的相關(guān)概念

2 改進(jìn)的遺傳算法

遺傳算法是具有生成以及檢測功能的全局優(yōu)化算法。本文在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上，重新定義適應(yīng)度函數(shù)和交叉操作，引入屬性頻度概念和屬性相似度概念，使改進(jìn)遺傳算法更快更有效率的實(shí)現(xiàn)屬性約簡。

2.1編碼

根據(jù)屬性約簡的特點(diǎn)和需求，將原始解空間數(shù)據(jù)通過二進(jìn)制編碼方式轉(zhuǎn)換為遺傳算法可以處理的基因型串結(jié)構(gòu)數(shù)據(jù)，即將原始解轉(zhuǎn)換為符號(hào)0和1組成的解，每個(gè)個(gè)體都由一個(gè)長度為n（n為屬性總數(shù)）的二進(jìn)制串來表示，其中每一位對(duì)應(yīng)個(gè)體某個(gè)屬性。若某一位取值為1，則表示保留此屬性；若某位取值為0，則表示舍棄此屬性。例如，1110001100表示長度n=10的一個(gè)個(gè)體，其對(duì)應(yīng)選擇的條件屬性為{c1，c2，c3，c7，c8}。

2.2適應(yīng)度函數(shù)

4 仿真實(shí)驗(yàn)與結(jié)果分析

本文采用與獻(xiàn)文[6]和[7]相同的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，表1是關(guān)于汽車數(shù)據(jù)的決策表，其中論域U共有21個(gè)對(duì)象，表格第一行表示對(duì)象所擁有的10個(gè)屬性，前9個(gè)為條件屬性，最后“里程”為決策屬性。

5 結(jié)束語

本文將屬性頻率作為啟發(fā)式信息，引入屬性相似度概念，提出了新的基于啟發(fā)式遺傳算法的粗糙集屬性約簡算法，減少了一些多余的交叉操作，加強(qiáng)了局部搜索能力的同時(shí)還保持了算法的全局優(yōu)化特性，實(shí)驗(yàn)結(jié)果表明，該算法能有效的隊(duì)決策表進(jìn)行屬性約簡。當(dāng)然，由于遺傳算法的容錯(cuò)性等問題，以后還需要更進(jìn)一步的改善。

參考文獻(xiàn)：

[1] Pawlak Z.Rough set theory and it s applications t o data analysis [J].Cybernetics and Sys tem，1998，29（ 27）：661-688.

[2] Pawlak Z.Rough sets and intelligent data analysis [J].Information Science， 2002，147（ 1/4）：1- 12.

[3] 苗奪謙，李道國.粗糙集理論、算法與應(yīng)用[M].北京：清華大學(xué)出版社，2008.

[4] 陳國良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，2001.

[5] 王國胤，姚一豫，于洪.粗糙集理論與應(yīng)用研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（7）：1229-1246.

[6] 孫娓娓，王春生，姚云飛.基于自適應(yīng)遺傳算法的粗糙集屬性約簡算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（33）：49-51.

[7] 潘偉，王云峰，傘治.基于自適應(yīng)遺傳算法的粗糙集知識(shí)約簡算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（15）：1-4.

[8] Feng Lin.An approach of attribute reduction based on quantum genetic algorithm and rough set[J].Information and Control，2011.40 （2）：198-201，203.

[9] 鄒瑞芝.一種基于遺傳算法的粗糙集屬性約簡算法[J]. 電腦知識(shí)與技術(shù)，2011，7（12）：2943-2944，2947.

[10]馮林.一種基于量子遺傳算法與粗糙集理論的屬性約簡算法[J].信息與控制，2011，40（2）：198-201.

[11]Jaddi，N.S，Abdullah，S.Hybrid of genetic algorithm and great deluge algorithm for rough set attribute reduction[J].Turkish Journal of Electrical Engineering & Computer Sciences，2013，21（6）：1737-1750.

[12]Chebrolu，Srilatha，Sanjeevi，etc.Reduction in decision theoretic rough set models using genetic algorithm[J].Lecture Notes in Computer Science.2011.7076（1）：307-314.

[13]Kohavi，Becker.UCI Repository of machine learning databases [EB/OL].Department of Information and Computer Science，University of California，Irvine，CA， 1996.http：//archive.ics.uci.edu/ml/datasets.html.