基於屬性重要度約簡演算法在資料探勘中的應用研究論文

　　摘要：屬性約簡是粗糙集理論研究的核心內容之一，本文透過對屬性重要度的計算，以核為基礎計算條件屬性集中除核以外其他屬性的重要性來確定最小的約簡，最後透過例項分析驗證了演算法的有效性與可行性。

　　關鍵詞：資料探勘屬性約簡重要度

　　資料探勘是從海量的且不斷動態變化的資料中，藉助有效的方法挖掘出潛在、有價值的知識過程。而粗糙集理論它是一種刻畫不完整性和不確定性的數學工具，能在保持分類能力不變的前提下，透過知識約簡從中發現隱含的知識，揭示潛在的規律，是由波蘭科學家Pawlak在1982年提出的。而屬性約簡是粗糙集理論研究的核心內容之一，它能保證在分類能力不變的情況下，消除重複、冗餘的屬性和屬性值，減少資料探勘要處理的資訊量，提高資料探勘的效率。本文提出了透過計算單個屬性的重要性，以重要性大於零的屬性為核，來選取其它屬性加入核中形成新的集合RED，直至剩下的所有屬性的重要性為零，得到的集合REDn即為屬性約簡。

　　1 粗糙集的基本理論[1-2]

　　定義1設是一個資訊系統，其中是物件的非空有限集合，即 ; 是屬性的非空有限集合; ，是屬性的值域; 是一個資訊函式，即每個物件在每個屬性上對應的`資訊值。若，其中為非空有限條件屬性集合，為非空有限決策屬性集合，且，則稱資訊系統為決策表。

　　定義2對決策表，，，考慮單決策屬性的情況，即，則的分辨矩陣是一個矩陣，其中的元素定義如下：

　　定義3對分辨矩陣中每個，用布林函式來表示，若，則決策表的分辨函式可定義為：。

　　2 基於粗糙集的資料探勘的屬性約簡演算法[3-4]

　　2.1 演算法分析

　　第一步：求核。透過求條件屬性C中的每個屬性a對在整個條件屬性集C的重要性SigC(x)來確定屬性核CORE(x)，重要性SigC(x)>0的屬性為核屬性。

　　第二步：透過向屬性核CORE(x)中依次加入重要性大的屬性來確定屬性集x的最小約簡，詳細步驟如下：(1)把a加入到屬性集R 中，計算重要性，選擇重要性最大的屬性;(2)如果兩個屬性有相同的重要性，取離散值小的屬性。

　　2.2 演算法複雜度

　　透過演算法的分析，在對決策表進行劃分的時間複雜度為O(n2)。而計算條件屬性的重要性也是滿足劃分的線性關係，因此所求屬性核的時間複雜度為O(n2)，依次新增次重要度的屬性也沒有增加額外的開銷，因此整個時間複雜度還是O(n2)。

　　2.3 例項及分析

　　為了進一步驗證演算法的可行性，下面以表1中的決策表為例進行分析說明，其中物件集，條件屬性集，決策屬性。