[發明專利]粗糙集屬性約簡的方法

在審

• 申請號: 201611062288.0
• 申請日: 2016-11-25
• 公開（公告）號: CN106650936A
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 趙昶宇;邢懷崗
• 申請（專利權）人: 天津津航計算技術研究所
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 中國兵器工業集團公司專利中心11011
• 代理人: 劉東升

技術領域

本發明涉及數據挖掘與知識發現技術領域，具體涉及一種粗糙集屬性約簡的方法。

背景技術

Wong S.K.M.和Ziarko在1985年已經證明找出一個信息系統或決策表的最小約簡是一個NP-hard問題，這是由數據組合爆炸引起的，不存在統一、規范的高效方法，對大型數據庫，最小約簡事實上并不存在，得到了只是近似約簡。為研究更為有效的約簡方法，有效地獲取較優的屬性約簡，并降低實現的時間復雜度，尋求快速的約簡方法是目前粗糙集理論的主要研究課題之一。

目前最常見的粗糙集屬性約簡的方法有：

1)基于區分矩陣的屬性約簡算法

該算法直觀易于理解，但是在處理大量數據集合時，算法的時間復雜度和空間復雜度成指數增長，約簡的速度非常慢。

2)基于屬性依賴度的約簡算法

該算法在對大量數據集合的約簡時，效率較高，但是該算法只得到了條件屬性的核，并沒有得到屬性的一個約簡，且不適合不相容系統的約簡。

3)基于屬性重要度的約簡算法

該算法和基于屬性依賴度的約簡算法相比，能夠更好的處理屬性滿足確定性關系，且有強烈因果關系的屬性集。但該算法并能不保證一定能夠找到信息系統的最優解。

4)基于遺傳算法的屬性約簡算法

遺傳約簡算法大大提高了決策表約簡結果的準確性和算法的高效性，但是該算法不能夠處理不相容和不確定關系的信息系統。

發明內容

(一)要解決的技術問題

本發明要解決的技術問題是：如何設計一種新的粗糙集屬性約簡的方法，以便能夠提高屬性約簡準確性和效率，又能夠處理不相容和不確定關系的信息系統。

(二)技術方案

為了解決上述技術問題，本發明提供了一種粗糙集屬性約簡的方法，所述方法包括以下步驟：首先，利用屬性核本身的特征確定初始種群，建立適應度函數；然后，利用遺傳算法找到條件屬性集合中適應值最大的染色體作為遺傳的優化解集合；最后，使用所述遺傳算法生成初始信息素，利用蟻群算法的局部尋優和正反饋機制得到粗糙集屬性約簡的最優解。

優選地，所述方法具體包括以下步驟：

S₁：

S₁₁：染色體編碼

采用長度為N的二進制串來表示一個染色體，“l”表示該染色體包含對應的條件屬性，“0”表示該染色體不包含對應的條件屬性；

S₁₂：確定初始種群

利用屬性核本身的特征對初始種群進行限制，在每個染色體中，將屬性核所在的位置上的基因強制取值為“1”；所述屬性核是所有屬性約簡的交集；

S₁₃：建立適應度函數

定義染色體的適應度函數為：F(v)＝|C|-L_v，其中：v表示一條染色體，即一個個體，|C|是染色體所代表的條件屬性集中屬性的個數；L_v是染色體中所包含的條件屬性的個數；

S₁₄：判斷是否滿足終止條件

終止條件：如果連續繁殖W代的最優條件屬性的適應值沒有變化時，則結束，否則轉步驟S₁₅；W為整數，是預設閾值；

S₁₅：選擇算子

a1)設條件屬性集合的長度為N，每個屬性的適應度為F_i，i＝1,2,…,N，計算條件屬性集合中每個屬性在下一代條件屬性集合中的期望生存數目

b1)用N_i的整數部分確定各個對應條件屬性在下一代條件屬性集合中的生存數目，其中表示取不大于N_i的最大整數，從確定下一代條件屬性集合中的個屬性；

c1)以表示各個條件屬性新的適應度，選擇算子隨機確定下一代條件屬性集合中還未確定的個條件屬性；

S₁₆：交叉算子

采用多點位單基因交叉的方式，用父代最優解T_max與子代染色體池T進行交叉操作：

a2)在染色體池T中選擇進行交叉操作的條件屬性集合T_i和屬性約簡的最優解T_max；

b2)隨機生成交叉片段和交叉區域；

c2)將T_i的交叉區域加到T_max前面，刪除與交叉區域相同的條件屬性，得到一個新的條件屬性集合；