基于屬性一致度的屬性約簡算法

達列雄　鄧方安　劉杰

摘要：在屬性一致度的概念和性質基礎之上，提出一種基于屬性一致度的屬性約簡算法。利用一致度構造屬性間模糊相似矩陣，并用模糊聚類分析方法對屬性重要性作了分類，從而得到動態屬性分類圖，得到了與粗糙集屬性約簡方法完全一致的結果。最后，用實例表明算法的有效性。

關鍵詞：屬性一致度；屬性約簡；模糊聚類分析

中圖分類號：TP182 文獻標識碼：A

1引言

粗糙集在處理不精確、不相容、不完備數據中具有明顯的優勢。粗糙集理論在模式識別、決策分析、數據分析處理、機器學習以及數據庫中知識發現等多個領域得到了廣泛應用。在當前的粗糙集理論中，知識約簡算法主要有三種：一種是按定義求解，而按照這種方法計算所有的約簡已被證明是NP一完全問題，無法實際中得到應用。另一種是1991年分辨矩陣求解，而這種方法在求解過程中，需要兩個不同決策對象的所有屬性值進行逐一比較，這樣會產生海量矩陣元素，既占用非常大的存儲空問，且時空性能又差。近年來，很多學者對此方法作了大量改進，但還是存在一定的缺陷。2008年孟慶全，金傳山等從傳統的屬性依賴度概念出發，對屬性集和屬性集依賴度兩個概念進行了擴展，提出了獨立于定義求解分辨矩陣法之外的新方法，即通過屬性依賴度求解屬性約簡和知識核的新方法。而第三種屬性約簡算法基本都是基于屬性重要性為主的一種算法，這類方法通常都會遇到如下兩個問題：

第一，屬性的重要性沒有統一的定義，使得約簡結果存在一定的差別，甚至會使約簡結果出現相互矛盾的情況；

第二，在約簡屬性得重要性相等的情況下，其相對約簡很難確定。

屬性相似度反映著粒度的相似程度，也反映著屬性之問的相似關系。為了解決以上存在的問題，夏克文博士從屬性相似度出發，提出了一種基于屬性相似度的屬性約簡算法，該算法不僅計算簡便，同時還能區分不同約簡的優劣性，克服傳統的粗糙集屬性約簡算法存在的缺點。

文獻雖然給出了一種基于屬性相似度的屬性約簡算法，但該文只考慮了決策屬性與條件屬性之間的相似度問題。本文將定義條件屬性之間相似度及條件屬性與決策屬性問的一致度，利用一致度構造屬性問的模糊相似矩陣，并用模糊聚類分析方法對屬性重要性做出分類，從而得到屬性的動態分類圖，得到了與粗糙集屬性約簡方法完全一致的結果。

2屬性一致度的概念與性質

定義1 在一個信息系統（U，C，D）中，U為論域，即U={x₁，x₂，…，x_n}，C為條件屬性集，P，Q∈U，D為決策屬性集，定義屬性問的一致度（consistent degree）如下：

上述公式（1）對于條件屬性集C中的任意屬性與決策屬性問的一致度計算也適用。

條件屬性子集P∈C與D為決策屬性集的一致性σ（P，D）也可類似定義。

命題1在一個信息系統（U，C，D）中，U為論域，即U={x₁，x₂，…，x_n}，C為條件屬性集，且P，Q∈C，D為決策屬性集，屬性的一致度具有如下性質：

3一種基于屬性一致度的屬性約簡算法

1）依據信息表，計算屬性的一致度。

2）依據屬性一致度，構造屬性問關系模糊相似矩陣。

3）依據屬性問關系模糊相似矩陣，進行模糊聚類分析。

4）依據聚類分析求屬性約簡，并確定核。

根據基于屬性一致度的屬性約簡算法，通過表1樣本信息表，先給出對象集的按各個屬性的等價分類。按照定義1可得：

根據以上3.2給出的屬性問的一致度，可以構造屬性問模糊相似矩陣：因為R²≥R，因此R不是模糊等價矩陣。容易求得模糊相似矩陣R的傳遞閉包

這是一個模糊等價矩陣，求t（R）=R^*的水平截集，得到動態分類：

通過上面的例子，可以看出，條件屬性c₂，c₃與決策屬性D的一致度偏低，它們是必要屬性，構成約簡的核，c₁，c₄與決策屬性D的一致度高，在屬性約簡時，可以把條件屬性集中與決策屬性D一致度高的條件屬性約去，構成最簡屬性約簡。

不難看出，{c₁，c₂，c₃），{c₄，c₂，c₃）是信息表1的兩個約簡，由于σ（c₁，D）=0.8，

σ（c₄，D）=1.0，因此{c₄，c₂，c₃}是比{c₁，c₂，c₃}更好的約簡，這與屬性分類動態聚類圖是一致的。

4結束語

本文主要針對信息系統中的屬性相似度與屬性的約簡，對條件屬性之間的相似度、條件屬性與決策屬性間的一致度進行定義，在此基礎之上，提出了一種基于屬性一致度的屬性約簡算法。并根據給出的屬性一致度的基本性質，采用模糊聚類分析方法，對屬性重要性作了分類，得到了與粗糙集屬性約簡方法一致的結果，表明了算法的有效性。