基于最小約簡的粗糙集數據挖掘算法研究*

楊曉波

（浙江樹人學院 杭州 314408）

1 引言

近年來，粗糙集理論在數據挖掘領域的應用日益廣泛。Christie 等［1］提出了利用粗糙集實現數據彈性變化的方法，但未解決數據規則隨條件變化的問題；Y.Zhang 等［2］提出了粗糙集的決策表生成算法，但沒有降低粗糙集的時間復雜度；Raghuwanshi等［3］提出了模糊理論與粗糙集相結合，但關聯規則的生成較復雜；Fetouh 等［4］提出了在粗糙集中引入遺傳算法，提高了運算效率，但也帶來一定的誤差；G. H. Zhang 等［5］提出在關系數據庫中引入粗糙度模型，數據的檢索效率有所提高，但并未降低計算復雜度；Choubey 等［6］通過采用遞推算法確定關聯規則，但對多維度的數據挖掘效率較低。隨著數據分析和挖掘技術的不斷改進，傳統的粗糙集理論已經越來越不適應新形式的需求，也暴露出數據挖掘效率較低、算法單一、誤差較大等問題。粗糙集理論雖然能夠分析隱藏在數據中的事實且不需要提供數據的附加信息，但在實際應用中，還需要處理數據中的噪聲和有效計算等問題。因此，需要尋求有效的約簡算法以擴展經典粗糙集理論。本文提出一種基于最小約簡的粗糙集數據挖掘算法，優化改進傳統粗糙集在數據挖掘領域應用的不足。

2 算法原理

約簡算法在數據挖掘領域，用于在原始數據集中發現最小子集，并將數據進行分類。相關學者通過分析數據的內在關聯提出了幾種主流約簡算法。Connolly等［7］提出利用屬性值獲取最小約簡的方法，但計算準確度較差；Y.He 等［8］利用深度層次聚類算法計算最小約簡，計算的準確度有所提高，但耗時較大；B. Xu 等［9］提出以區分矩陣為基礎獲取最小約簡，運算效率進一步提高，但生成規則較復雜。本文將在總結專家學者研究的基礎上，提出一種基于粗糙集理論的優化約簡算法。

該算法以屬性特征為基礎，利用其在區分矩陣的出現次數構造生成規則，通過計算獲得最小約簡。由于約簡與區分矩陣之間存在一定聯系，在算法設計時應予以考慮，具體的算法設計流程如圖1所示。

圖1 優化約簡算法流程圖

從圖1 得到的約簡值，不一定是最小約簡，要獲取最小約簡需要制定相應的約簡生成規則。

制定生成規則首先將區分矩陣成員c 進行排序，然后計算每個成員項的屬性值，區分矩陣的屬性值唯一，則成為約簡候選成員；另外還需計算區分矩陣成員的長度和頻率，一般長度與頻率成正比，長度值可以通過計算成員屬性的加權平均值獲得，頻率值可通過計算成員屬性的加權求和獲得。

區分矩陣成員的屬性值每計算一次，便更新一次屬性頻率，屬性頻率的表示如下：

其中p(a)表示屬性頻率函數，N表示滿足條件的屬性個數，c表示區分矩陣的成員項。

從式（1）可知，屬性頻率與屬性個數N 成正比，與每個成員項的屬性值成反比。屬性頻率值越大，當計算區分矩陣的成員項時，越有可能得到最小約簡。

為了清晰表達如何通過生成規則獲得最小約簡，算法的實現流程如圖2所示。

從圖2 可知，區分矩陣是計算最小約簡的基礎，通過計算成員項的屬性頻率來建立生成規則，并從屬性頻率中找到頻率值最大的屬性，以確定最小約簡。利用生成規則可以大概率確定最小約簡，即使沒有獲得最小約簡，也會獲得次優約簡，同時降低算法實現的復雜度。

圖2 利用生成規則獲得最小約簡

3 擴展模型

約簡算法在實際應用中，經常面臨噪聲干擾、數據不完整等問題，為了解決這一問題，我們采用在粗糙集中引入擴展模型。

引入擴展模型目的是提升約簡粗糙集的抗干擾能力，提高獲取最小約簡的準確度。本文提出一種精度可變的粗糙集擴展模型，當數據集中的數據變化較劇烈時，可以通過改變精度降低誤差。

通常模型的分類誤差有一定范圍，一般小于5%，可以利用可變精度參數α(0 ≤α≤0.5) 來表示。

假設集合A 與集合B 均為論域U 的非空子集，我們利用式（2）表示約簡算法的擴展模型。

當集合A 與集合B 中的元素存在一一對應時，分類誤差的概率小于α。當α=0 時，說明集合B包含集合A；當α≠0 時，說明集合A 與集合B 存在一定的近似關系。

集合A 的下限一般表示集合元素在集合A 的分類誤差小于α，與之相對應，集合A 的上限通常表示集合元素在集合A的分類誤差大于α。

借助集合的下限特點，我們可以定義屬性之間的近似關系，這種近似關系以可變精度參數α為基礎，通過計算分類誤差來評測可變精度參數α的分類能力。需要說明的是，近似分類有別于傳統的粗糙集分類，傳統的粗糙集以精確度為分類基礎，更多地依賴于函數特性。

可變精度擴展模型與傳統粗糙集模型可以做到相互兼容，我們可以將可變精度參數α近似看作約簡的最小子集，當α=0 時，可變精度擴展模型便等價于傳統粗糙集模型，因此可變精度擴展模型繼承了傳統粗糙集模型的基本特性，因而適用面更廣。

當數據集元素的屬性值缺失，傳統粗糙集模型的分類誤差將增加，這時，我們借助可變精度擴展模型的近似關系，降低分類誤差，提高數據分類的準確度。

當使用可變精度擴展模型的近似關系區分數據類型時，相似類與原集合存在部分重疊，且相似類不再用于區分數據類型，我們可以利用相似集S(x)來劃分原集合。

式（3）中S(x)表示元素與屬性集合B 之間的相似度，相似集S(x)并不代表決策類，為了確定決策類集合，我們可以借助相似集S(x)定義決策類。

集合B 包含于論域U 之中，如U 中的任意元素存在與集合B 中元素相似，則說明兩個集合的決策值是相同的。相似關系的屬性約簡算法過程表示如圖3所示。

圖3 相似關系的屬性約簡算法

從圖3 可知，屬性約簡首先初始化屬性值，再從屬性集合中選取最大值，并將屬性加入到約簡集中，最后在信息表中查找不同類型的樣本對，并輸出約簡值。

在此算法中，分辨信息表DF 用于評價屬性在對象類中的相似性，與傳統分類矩陣相比，該表增加了同類樣本的屬性差異值，因此，評價屬性特征時，可以從同類樣本的相似性和不同類樣本的相異性兩方面衡量。分辨信息表DF的定義如下：

其中論域U={x1,x2,…xn} ；

條件屬性C={c1,c2,…cm} ；

決策屬性D={d1,d2,…dn} ；

屬性值域V=[0 ,1] ；

信息函數f=U×C。

4 實現過程

區分矩陣往往占用的空間較大，甚至比原始數據集還要大，為了節約存儲空間，可以用0或1表示區分矩陣每項的屬性，當值為0 時，表示該項不存在屬性，不需要存儲；當值為1 時，表示該項存在屬性，這時才需要存儲，這樣就可以節約大量存儲空間。

最小約簡的粗糙集數據挖掘算法，實現過程如圖4所示。

圖4 最小約簡算法的實現過程

另外，借助區分矩陣的生成規則約簡算法表述如下：

輸入：區分矩陣T

輸出：約簡集合

Begin

初始值Red=φ

計算區分矩陣T 并同時計算每項的屬性頻率p(ai),i=1,…n；

5 實驗分析

為了檢驗本文所提算法的可靠性，擬采用40個數據集進行測試，測試環境是：硬件平臺，Intel Core i6-4790 4.5GHz CPU，IntelG51 Express Chip?set，8GB DDR3 Ram；軟件平臺，Visual Studio 2010，數據集采用具有連續屬性的數據集，首先利用熵方法對數據集進行離散化，然后利用區分函數方法［11］計算數據集中的所有約簡，最后借助本文算法找出數據集中的最小約簡。同時采用RSL 算法進行對比，分析兩種算法的優劣性。

經過計算，在40個數據集中，有17個數據集存在唯一約簡，兩種算法均能成功找到這些約簡，它們都是由長度唯一的區分矩陣組成；另外，有5 個數據集無法計算所有約簡，說明不是每個數據集都存在唯一約簡。實驗數據集的基本特性如表1 所示。

表1 數據集的基本特性

以數據集Forest 為例，介紹利用約簡算法找到約簡的過程，為簡單起見，屬性名采用整數進行編碼。

RSL算法找到的約簡如下：

本文算法找到的約簡如下：

兩種算法都找到了最小約簡：（0 1 3 5 9 10 11）。

對于數據集Connect 1，RSL算法找到的約簡如下：

（0 1 2 5 6 10 13）；（0 1 3 5 6 11 15）；（0 3 2 5 7 10 17）

其中最小約簡為（0 1 2 5 6 10 13）。

本文算法找到的約簡如下：

（0 3 2 5 6 12 15）；（0 3 1 5 7 10 17）；（0 1 2 5 6 10 13）；（0 3 2 5 6 11 18）；（0 1 3 5 6 10 13）

本文算法所得到的最小約簡超集為（0 1 2 5 6 10 13）。

對于數據集Food，兩種算法所得到的約簡均為

其中第2 個約簡，本文算法得到的是一個次優解。

從表1的數據比較中，可以得到如下結論：

1）在大多數情況下，兩種算法都能找到最小約簡。本文所用算法有16 個數據集表現比RSL 好，RSL在兩個數據集中超過本文算法。

2）兩種算法在執行實例數較小的數據集時，運行時間比較接近，當在實行實例數較大的數據集時，本文算法的時間復雜度較低，而且運行時間也少于RSL算法。

3）對大多數數據集而言，較短的時間內就可以求出所有約簡，約簡算法的執行時間取決于兩個主要因素，即實例數及核的長度，當核較大時，約簡計算相對簡單，同時產生的約簡個數也較少。

存在唯一約簡數據集的計算結果如圖5所示。

圖5 兩種不同算法效率對比圖

從圖5 可知，17 個數據集中，RSL 算法的運行時間均超過本文所提算法的運行時間，前者的平均運行時間比后者多出近30%，換言之，本文所提算法的運行效率優于RSL算法。

6 結語

本文提出一種基于約簡粗糙集的數據挖掘算法，通過算法分析和對比性實驗得出以下結論：

1）利用區分矩陣中項的長度和屬性頻率信息，制定啟發規則，并從中尋找最小約簡，在大多數情況下，可以找到最小約簡，即使找不到最小約簡，也會找到次優約簡，且算法復雜度較低。

2）采用精度可變的粗糙集擴展模型可以提升粗糙集的抗干擾能力，同時能夠提高獲取最小約簡的準確度。為了客觀評價屬性在對象類中的相似性，提出相似關系的屬性約簡算法。

3）為了驗證本文所提算法的可靠性，采用40個數據集進行對比性實驗，結果表明：本文所提算法的運行效率高出其他主流算法近30%。

4）今后的研究方向包括開發更有效的屬性頻率加權機制，進一步降低本文所提算法的復雜度等。