今日頭條
官方微信
官方抖音
案例頻道
曾慶雙 （1964-）
男，教授，博士生導師。研究方向為機器學習和故障診斷。
基金項目：國防科技預研基金項目（9140A17030207HT0150）
摘要：針對現實中含有數值型屬性的決策系統的約簡問題，提出了基于鄰域?；瓦z傳算法的約簡方法。該方法采用基于鄰域等價關系建立的粗糙集模型，用鄰域等價關系度量粗糙集不可分辨關系，通過鄰域信息粒子逼近論域空間。構造了遺傳約簡算法，論述了遺傳算法適應度函數的選擇，設計了自適應交叉概率，給出了算法的具體實現。對經典數據集和UCI數據庫中4個數據庫約簡的結果證明了算法的有效性和可行性。
關鍵詞：鄰域；粗糙集；約簡；遺傳算法
Abstract: In order to reduce the practical decision system
including numerical attributes, a reduction algorithm based on
neighborhood granulation and genetic algorithm is proposed. In
this algorithm, a rough set model is used based on neighborhood
equivalence, the indiscernibility relation is measured by neighborhood
relation, and the universe spaces is approximated by neighborhood
information granules. The choice of fitness function and the adaptive
across probability is discussed, and the reduction algorithm is presented
as well. Furthermore, the dependency function is used to evaluate the
significance of numerical attributes. The validity and feasibility of the
algorithm are demonstrated by the results of experiments on a classical
data set and four UCI machine learning databases.
Key words: Neighborhood; Rough set; Reduction; Genetic algorithm
粗糙集理論是波蘭數學家Pawlak于1982年提出的一種數據分析理論[1]，它作為一種刻劃具有不完整性和不確定性信息的全新數學工具， 已經成為人工智能領域的一個新的學術熱點。Pawlak粗糙集將研究對象的全體稱為論域，采用等價關系將論域?；癁槿舾苫コ獾牡葍r類，并定義了兩個等價類的并集：下近似和上近似來逼近這一概念。但是，作為一種有效的粒度計算模型，Pawlak粗糙集建立在嚴格的等價關系和等價類基礎上，只適合處理符號變量，但實際應用的數據庫中普遍存在數值變量，這為粗糙集的應用帶來了困難。在用粗集理論處理數值型數據時，一般采用離散化算法把數值型屬性轉化為符號型屬性，這一轉換不可避免的造成信息損失，計算處理結果在很大程度上依賴于離散化的效果。隨后提出的可變精度粗糙集模型雖然給出了一個不一致性容忍的域值，將Pawlak粗糙集中正域求取的嚴格包含修正為絕大部分包含，但需要用戶設定閾值，并將閾值以下的少量不一致樣本當成一致樣本進行處理也是不合理的，不能有效估計特征的分類能力[2]。
1988年Lin提出了鄰域模型的基本概念[3]。1998年姚一豫以及2002年吳偉志教授分別研究了鄰域算子和鄰域系統的基本性質[4,5]。鄰域模型通過點的鄰域來?；撚?，將鄰域作為基本信息粒子。鄰域粗糙集方法直觀、易于理解，能夠直接處理數值型屬性，而無須對其進行離散化處理。因此，與經典粗糙集方法相比，該方法省去了離散化的過程，模型可以直接分析數值型數據，從而拓展了經典粗糙集理論的應用范圍。
知識約簡問題是粗糙集理論的一個核心問題。所謂知識約簡， 就是在保持知識庫分類能力不變的條件下， 刪除其中不相關或不重要的冗余知識，已經證明它是NP難問題[6]，計算量隨屬性個數呈指數級增長。現有的約簡算法， 主要是從粗糙集的核出發， 采用啟發式搜索的方法構造所含條件屬性最少的約簡， 即最小約簡。但是這種算法并非對所有的知識表達系統都適用[7]， 而且隨著問題規模的增大會越來越復雜。遺傳算法，恰好由于它本身具有全局優化和隱含并行性等優點，因此很適合于這個問題的求解。
遺傳算法是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴梯度信息，是一種有效的全局優化搜索算法，因此遺傳算法具有很強的全局搜索能力，能夠在較短時間內找到全局最優解[8]。將遺傳算法和鄰域?；碚撓嘟Y合，設計了一種基于鄰域粒化的自適應遺傳約簡算法。該算法可直接處理數值型數據，降低約簡時間，提高計算效率，并通過對交叉概率的自適應設計，保證算法的收斂性。
1 鄰域?；按植诒平?/font>
Pawlak粗糙集以等價類和劃分為基礎，論域被等價關系分割為互不相交的若干子集，如圖1所示，容易造成部分樣本具有相同的特征但決策卻不相同。對于被數值描述的分類問題，如圖2所示，很難得到取值完全相同的樣本。此時通過適當放寬屬性值相等的條件，改為屬性值相近的假設，使得屬性值相近的樣本具有相同的決策，否則決策是不一致的，就是鄰域粗糙集的基本思想。從圖1、圖2可以看出，Pawlak粗糙集是鄰域粗糙集的特例，當定義鄰域大小
時，鄰域關系即退化為等價關系，鄰域粒子退化為等價類，相應的，鄰域粗糙集退化為Pawlak粗糙集[9]。
定義1. 設
是非空度量空間，
，
，稱點集
為以
為中心，以
為半徑的閉球，又稱為
的
鄰域。
論域中所有對象的鄰域形成了論域的?；?，鄰域粒子族是構成論域空間的基本要素。
圖1 Pawlak粗糙集
圖2 鄰域粗糙集
設
為一信息系統，其中U是對象的非空有限集合，稱為論域；A是屬性集合；V是屬性值域；f是
的映射，為U中各對象的屬性指定唯一值。如果
，
，其中C，D分別表示條件屬性集和決策屬性集，那么該信息系統稱為決策系統。
定義2. 給定鄰域決策系統
，D將U劃分為N個等價類：
，
生成U上的鄰域關系NB，那么決策D關于B的鄰域下近似和上近似分別為：
決策的邊界定義為
決策D的下近似也稱為決策正域，正域的大小反映了分類問題在給定屬性空間中的可分離程度。正域越大，表明各類的重疊區域即邊界越少。這類分類問題可以用下面的定義描述。
定義3. 給定一個鄰域決策系統，
，決策屬性D對條件屬性的依賴度為
（1）
依賴度
表示在條件屬性C下能夠確切劃入決策在U/D的對象占論域中總對象數的比率，表達了決策屬性對條件屬性的依賴程度。需要指出的是，鄰域粒化不能區分線性還是非線性可分問題，鄰域大小只是反映了樣本之間的距離。度量數據的可分性時，如果依賴度為1，則是可分的，并不去考慮是線性可分還是非線性可分。
系統中的部分屬性對某個分類問題可能是冗余的或者是無關的，這些屬性不會引起分類邊界的變化，但是它們的存在，可能會導致模型過擬合、學習速度變慢、分類器變復雜。如果從系統中去掉一個屬性a，系統的正域不變，各類的可區分性不變，可以視屬性a是冗余的，相反，如果刪除a后決策屬性D對剩余條件屬性的依賴度變小，則表明a屬性不能被刪除，否則影響系統的可區分性。
定義4. 給定一個鄰域決策系統，
，
，如果B滿足下面兩個條件，則稱B是A的一個相對約簡：
（1）充分條件：
（2）必要條件：
，
。
第一個條件確保屬性B能形成和全部屬性A相同大小的分類正域，因此其保留了充分的分類信息。第二個條件確保B中的任何一個屬性都是必要的，在約簡中不存在多余的屬性。
同樣，對給定決策系統
，屬性
的重要性可以如下定義：
（2）
2 基于鄰域模型的核屬性計算
給定一個鄰域決策系統
，C中所有D必要的原始屬性構成的集合，稱為D的C核，簡稱核，記為COREC(D)。
這是核的一個很樸素的定義，核還可以理解為A所有約簡的交集，因此一個決策系統不一定存在核，如果存在核，核將包含于任一個約簡中。核是所有約簡的基礎，計算一個決策系統的約簡一般先從獲得核開始。
定理1：給定一個鄰域決策系統
，屬性 
，如果
，則a是核屬性。
證明：根據核屬性定義可證。
根據定理1，基于屬性的重要度，設計了鄰域模型的核屬性計算算法，描述見算法1。
算法1：鄰域模型核屬性算法
輸入：
和
輸出：核屬性CORE
1：
2：For each 
3：計算
4：If 
5：
6：End if
7：End for
3 遺傳約簡算法
遺傳算法是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。由美國Holland J教授提出。其主要特點是，群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。遺傳約簡算法是決策問題中尋找最小約簡的一種方法。實踐證明，遺傳算法對于組合優化中的NP問題非常有效。例如遺傳算法已經在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。結合自適應遺傳算法及最小相對約簡問題的特點與要求，本文提出的自適應遺傳算法主要運算過程如圖3所示，其中G和M分別表示當前進化代數和進化終止代數。
圖3 自適應遺傳算法
3.1 編碼方法
由于遺傳算法不能直接處理解空間的解數據，必須通過編碼將它們表示成遺傳空間的基因型串結構數據。本文使用固定長度的二進制符號串來表示群體中的個體，其等位基因是由二值符號集{0，1}組成，其中每一位對應一個條件屬性，若某位取值為1，則表示選擇其對應的條件屬性，若某位取值為0，則表示不選擇其對應的條件屬性。染色體的長度為條件屬性的個數，每一個染色體個體對應了條件屬性空間中的一個屬性子集，即屬性選取的一個可能解。
3.2 適應度函數的確定
適應度函數是對個體位串的適應性進行評價的惟一確定性指標，所以適應度函數的形式直接決定著群體的進化行為。按照知識約簡問題的實際要求，我們定義適應度函數如下[10]：
（4）
其中，f(x)為目標函數，card(x)為染色體中1的個數，即染色體所含條件屬性的個數，n為染色體的長度，即條件屬性的個數；
為罰因子；P(x)為罰函數，
為x所含條件屬性對決策屬性D的依賴度，
是預設的閾值。通過這三部分構造的適應度函數，可以在保持決策屬性對整體條件屬性依賴度不變的情況下，獲得知識約簡問題的最佳搜索效果。
3.3 選擇運算
預設一個種群規模為m，長度為n的由0、1表示的染色體作為初始種群，為加快算法的收斂，將核中所含的屬性加入到初始種群中。選擇操作采用適應度比例選擇方法，通過輪盤賭的方式實現。對于給定規模m的群體
， 
個體的適應度為
，其被選擇次數的期待值為：
（5）
gj反映了父代種群中個體生存的期望數目。將gj四舍五入得到個體xj被選擇的次數，從而由種群G1成為G2。為保證某一代的最優解不被破壞，采用最優個體保護法，取每一代中適應度最大的個體不進行遺傳操作，而是直接復制到下一代的種群中，這樣每一代的最優個體的特征呈單調遞增的趨勢。
3.4 交叉運算
按照預先設定的概率Pc隨機選擇
對染色體，對每一對染色體的每一位按相同的概率進行交叉。設染色體編碼為
，
，則操作描述為：
：
，
（6）
其中，x是在[0，1]上取值的均勻分布的隨機變量。
從群體進化過程來看，交叉概率應該隨進化過程逐漸減小，最終趨于某一穩定值，以免對算法后期的穩定性造成沖擊而影響算法的收斂性。本文選擇交叉概率公式為：
（7）
其中，G為進化代數，
為常數。
3.5 變異運算
對于給定的變異概率Pm，隨機選擇
個染色體，隨機改變某位的編碼來實現變異操作。設選定的染色體為
，操作描述為：
：
（8）
其中，x是在[0，1]上取值均勻分布的隨機變量。
4 遺傳約簡算法實現
隨機產生m個長度為n的二進制串組成初始種群X，對于核中的屬性，其對應位取1，并在整個進化過程中保持不變，其它對應位隨機取0或者1，這樣可以加快算法的收斂。在進化過程中，對最優個體進行保護，取每代中適應度最大的個體直接復制到下一代，其它個體以輪盤賭的方式生成交配池，并且采用自適應的交叉概率，加快進化速度，保證算法收斂，詳細描述見算法2。
算法2.鄰域?；Ｐ瓦z傳約簡算法
輸入：
，
和X
輸出：約簡red
1：
2：For each 
3：計算決策屬性對
所含條件屬性的依賴度
4：計算
5：End for
6：
7：計算
以輪盤賭方式進行選擇操作
8：計算
，按（6）式進行交叉操作
9：根據
，按（8）式進行變異操作，核屬性位不發生變異
10：IF連續t代最優個體適應度不再提高，或者達到最大進化代數，則終止計算，輸出red
11：Else go to step 2
5 算例
某型旋轉機械設備[11]常有轉子不平衡、轉子不對中、油膜振蕩、喘振和碰撞五種故障，由歷史振動波形測量數據可建立如表1所示的原始故障診斷決策表。在表1中，包含20個故障樣本；7個故障特征屬性：C1表示0.01~0.40f、C2表示0.41~0.50f、C3表示0.51~0.99f、C4表示1f、C5表示2f、C6表示3~5f、C7表示5f；5種故障類型：F1為不平衡、F2為不對中、F3為油膜振蕩、F4為喘振、F5為碰撞。
表1 故障診斷決策表
U C1 C2 C3 C4 C5 C6 C7 D
X1 0.1109 0.0060 0.1145 0.9612 0.0323 0.0504 0.0243 F1
X2 0.1063 0.1464 0.1177 0.9560 0.0061 0.0446 0.0505 F1
X3 0.0455 0.0643 0.0927 0.7393 0.0645 0.2117 0.0014 F1
X4 0.0461 0.0229 0.0850 0.5890 0.0798 0.2980 0.0319 F1
X5 0.1305 0.1077 0.1389 0.2096 0.4240 0.1203 0.0767 F2
X6 0.0875 0.0095 0.1287 0.5120 0.3437 0.0010 0.1309 F2
X7 0.1462 0.0124 0.0788 0.2828 0.5551 0.0313 0.1263 F2
X8 0.0968 0.0320 0.0600 0.5011 0.3414 0.1319 0.0502 F2
X9 0.3467 0.2398 0.0829 0.2610 0.1152 0.1250 0.0586 F3
X10 0.0251 0.2192 0.0776 0.2307 0.0503 0.1087 0.1233 F3
X11 0.3952 0.5224 0.1090 0.1985 0.0640 0.1036 0.0865 F3
X12 0.2115 0.2110 0.0209 0.3587 0.0751 0.0266 0.0661 F3
X13 0.0572 0.2167 0.0332 0.5933 0.0876 0.1395 0.0696 F4
X14 0.0847 0.2787 0.0518 0.2452 0.1443 0.0845 0.3499 F4
X15 0.0738 0.3300 0.0317 0.3837 0.0705 0.0511 0.2287 F4
X16 0.3560 0.3027 0.0861 0.1889 0.0914 0.1307 0.2771 F4
X17 0.1422 0.0438 0.0327 0.8313 0.0838 0.1313 0.0637 F5
X18 0.0911 0.0637 0.0620 0.5326 0.0208 0.0615 0.0840 F5
X19 0.0821 0.1161 0.1175 0.4476 0.1481 0.3588 0.0973 F5
X20 0.1491 0.1093 0.0942 0.3806 0.0536 0.3499 0.1699 F5
根據鄰域?；Ｐ秃瓦z傳算法，在無需離散化，無需其它先驗知識的情況下，可以正確的求得決策系統的最小約簡。表2是利用本遺傳算法求解最小約簡的一個計算結果。計算中各參數取值為：m=30，Pm=0.03，
=15，
=2，
=0.9，
，
。結果中顯示了每一代的最優個體、最優個體適應度、當前群體總適應度和進化代數。在本例中第5代就出現最優個體，求得最小約簡為{C2，C4，C7}，核屬性為C7。相對于文獻[10，12]，本文無需對數據進行預處理，直接快速求出最小約簡，并且采用自適應交叉概率，具有更好的收斂性。
表2 遺傳算法結果
最優個體 適應度 群體適應度 進化代數
1001101 0.7008 14.3671 1
1101001 0.7008 17.6711 2
1011001 0.7008 17.9321 3
1011001 0.7008 16.0659 4
0101001 0.9344 16.4312 5
0101001 0.9344 16.2942 6
0101001 0.9344 14.0870 7
0101001 0.9344 9.7942 8
0101001 0.9344 7.0915 9
0101001 0.9344 10.8893 10
為檢驗算法求出的相對約簡的有效性，選用了美國加州大學Irvine分校（UCI）建立的機器學習數據庫“Credit”、“German”、“Vote”和“Wine”。利用支持向量機（SVM）分類器作為評價函數，將數據樣本分為訓練集和測試集，分別用原始數據和約簡后的數據來訓練支持向量機，然后用預測精度來評價約簡質量，實驗中遺傳算法仍采用前面的參數，“Vote”數據庫對應的SVM采用linear核函數，其它采用spline函數，實驗結果如表3所示。
表3 約簡結果
數據 樣本 屬性 原始預測精度 約簡預測精度
Credit 690 15 82.63 81.44
German 1000 19 66.46 71.72
Vote 435 16 95.40 93.07
Wine 178 13 89.79 96.89
約簡后的預測精度和原始數據預測精度相比，“Credit”和“Vote”有所下降，原因是由于在復雜條件下，遺傳算法獲得的約簡受到進化代數的限制，結果不是最優的，另外數據中的噪聲也會造成預測精度的下降。預測精度提高是因為原始數據中冗余屬性影響了決策，約簡后降低了對決策的影響，提高了預測精度。
6 結論與展望
本文基于鄰域關系的概念，以論域空間中任意對象的鄰域形成論域空間的?；?，擴展了經典粗糙集的應用范圍。利用遺傳算法，提出了一種基于遺傳算法的數值型屬性約簡方法。由于遺傳算法本身具有全局優化的特點，所以可以解決現有算法難以解決的問題。通過實驗分析表明，這種算法是求解數值型屬性知識約簡問題的一種行之有效的方法。但是由于遺傳算法計算量比較大，耗時長，基于鄰域粗糙集模型的海量數據快速約簡是下一步的研究方向。另外鄰域算子的選擇及對系統性能的影響也需要進一步的深入探討。
參考文獻
[1] Pawlak Zdzislaw. Rough Sets [J]. International Journal
of Computer and Information Sciences，1982，11(5): 341-356.
[2] Xia Zhao, Minghu Ha, Aiquan Zhang. Variable Precision Rough
Set Model in Incomplete Ordered Decision System [C]. Innovative
Computing Information and Control，2008 ICICIC ’08. 3rd International
Conference，2008，498-498.
[3] T. Y. Lin, Q. Liu, K J Huang. Rough Sets Neighborhood Systems and
Approximation [C]. In: Fifth International Symposium on Methodologies
of Intelligent Systems. Selected Papers 1990.
[4] Y. Y. Yao. Relational Interpretations of Neighborhood Operators
and Rough Set Approximation Operators [J]. Information Sciences，1998，111: 239-259.
[5] W. Z. Wu, W. X. Zhang. Neighborhood Operator Systems and
Approximations [J]. Inf. Sci. 2002，144(1-4): 201-217.
[6] Skowron A, Rauszer C. The Discernibility Matrices and Functions in
Information Systems [M]. In: Slowiński R, ed. Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory，1991: 331-362.
[7] Wang J, Miao D Q. Analysis on Attribute Reduct ion Strategies of
Rough Set [J]. Journal of Computer Science and Techno logy，1998，13 (2): 189-192.
[8] Forrest S. Genetic Algorithms[C]. Proceedings of the Fifth International Conference on Genetic Algorithms. San Mateo，CA: Morgan Kaufmann Publishers，1993: 35-42.
[9] 胡清華，于達仁，謝宗霞. 基于鄰域粒化和粗糙逼近的數值屬性約簡[J]. 軟件學報，2008，19 (3): 640-649.
[10] 陶志，許寶棟，汪定偉，李冉. 基于遺傳算法的粗糙集知識約簡方法[J]. 系統工程， 2003，21(4): 116 -122.
[11] 齊繼陽，竺長安. 設備故障智能診斷方法的研究[J]. 儀器儀表學報，2006，27 (10) : 1270-1275.
[12] 張超，馬存寶，宋東，許家棟. 基于粗糙決策樹模型的復雜設備智能故障診斷 [J]. 兵工學報，2008，29 (9): 3211-8211.
北京市公安局海淀分局備案號：11010802023656號