基于rough sets的不完備數據分析研究

趙東陽

（魯東大學信息科學與工程學院，山東 煙臺 264025）

1982年，波蘭數學家Pawlak等人首次提出了粗糙集理論，粗糙集理論的主要思想是在保持知識庫分類能力不變的前提下，導出問題的決策和分類規則。粗糙集理論自身的特點和優勢使其在數據挖掘方面獲得了巨大的成功，在數據挖掘和數據庫知識發現等研究領域正在扮演越來越重要的角色，逐漸成為該領域研究的重要分支。

1 不完備信息系統RS處理方法

Pawlak所提出的RS理論是面向完備信息系統的，在面對某些不完備系統時，必須對 RS理論的基本概念進行必要的擴充，以使其能夠對這些系統進行直接處理。擴充法是一種直接處理方法，也是研究不完備信息系統的最有效的方法。

1.1 容差關系

在“遺漏”語義下處理不完備信息系統而定義的一種二元關系即容差關系。每個個體對象都具有潛在的完備信息，而當前只是遺漏了這些值，于是由于這些不精確的知識迫使人們去處理只有部分信息的不完備信息表。

1.2 非對稱相似關系

由Stefanow ski 等人提出的面向不完備信息系統的相似關系則是基于對“缺失值”語義的如下理解：一個屬性的缺失值不僅可能由于現有知識的不精確，還可能因為它根本就不能用現有的屬性值來描述。因此相似關系中不允許比較缺失值，不完備信息系統S＝（U，A）上的相似關系定義S為：

顯然，相似關系S是不對稱的，實質上是一種包含關系的表示，因為只要滿足“x的描述”包含于“y的描述”就可以認為“x相似于y”。

1.3 限制容差關系

王國胤教授將容差關系和相似關系看作是對不可分辨關系擴充的兩個極端，因為容差關系的條件太寬松，易于將根本沒有相同已知屬性信息的實例誤分到同一個容差類；而相似關系卻可能將具有很多相同關系一直屬性信息的實例分到不同的相似類。因此，王國胤教授提出了一種介于這兩種極端擴充之間的限制容差關系——限制容差關系的粗糙集模型。該模型是基于容差關系與基于非對稱相似關系粗糙集模型的改進。

1.4 量化容差關系

為了進一步刻畫容差關系和相似關系中兩個實例之間的“相似”程度，Stefanow ski等人提出了基于量化容差關系的擴充 RS理論模型。通過應用不同的比較規則可以得到不同類型的量化容差關系。給定一個量化容差關系，對論域U中的每個實例，Stefanow ski定義了“容差類”的概念，它是一個用關于參考元素的“容差度”作為成員函數的模糊集。量化容差關系著重于對存在容差關系或相似關系的實例之間的“容差（或相似）程度”進行進一步的細化，其研究思路是自然、正確的。

2 屬性約簡

數據挖掘要處理的初始信息系統中經常包含大量的無關或冗余屬性，這些屬性的存在不僅會阻礙挖掘進程，而且會降低最終挖掘知識的正確性和精簡度。RS理論中將刪除信息系統中的無關或冗余屬性的過程稱作屬性約簡。通過屬性約簡最終得到的屬性集成為信息系統的一個約簡（Reduct），它是保持原始決策表中條件屬性和決策屬性的依賴關系不發生變化的最小屬性集合。由于求取一個決策表的所有約簡是一個 NP問題，通常在實際應用中很難實現。因此 Liang等人提出了一種不完備信息系統中求取屬性約簡的啟發性算法。對數據進行屬性約簡的意義，主要從以下幾個方面考慮：①從機器學習的角度來看，屬性約簡對于去除噪聲非常有意義；②對一些學習算法而言，訓練或分類時間隨著數據維數的增加而增加，經過屬性約簡可以降低計算復雜度，減少計算時間；③假如不進行屬性約簡，噪聲或不相關屬性和期望屬性對分類的作用一樣，就會對最終結果產生負面影響；④當用較多的特征來描述數據時，數據均值將表現得更加相似，難以區分。

3 規則抽取

使用 RS理論進行數據挖掘，其最終獲得的知識是以規則的形式給出的。規則抽取是數據挖掘中最重要和最關鍵的一步，它是指從經過處理的決策表中抽取出以規則形式表示的知識。目前用于分類問題的方法主要分為兩類：符號方法和連接主義方法。符號方法是基于決策樹、粗集理論等技術，得到的分類知識以分類規則的形式出現；而連接主義方法則以神經網絡為代表，其知識蘊含在結構中不易為人所理解，因此一度被人們認為不適合進行數據挖掘。然而由于神經網絡在分類問題中具有分類精度高、魯棒性好等優點，很多研究者都致力于從神經網絡中抽取分類規則。神經網絡的基本思路是基于搜索的算法，對于任一給定的隱結點或輸出結點，先提取符號規則，然后對生成的規則按網絡的傳導途徑進行連接和整理。有的文獻提出了一種從訓練后的三層前饋網絡中抽取分類規則的方法。該方法首先對每個隱層結點的輸出值進行離散化；然后分別導出隱層結點與輸出層結點之間的規則（規則集 1）和輸入層結點與隱層結點之間的規則（規則集2）；最后將兩部分規則進行合并得到最終的分類規則。總之，從神經網絡中抽取規則是一個復雜的過程，這其中隱結點的離散化過程不僅繁瑣，而且易丟失信息。另外，當數據量增多、網絡規模變大時，網絡訓練和規則抽取的時間代價將會非常大。

1 陳珂、宣仲良.一種基于粗糙集理論的 ROUSTIDA改進算法［J］.電腦與信息技術，2008（3）：32～33.

2 朱小飛、卓麗霞.一種基于量化容差關系的不完備數據分析方法［J］.重慶工學院學報，2005（5）：23～24.