基于最小約簡的粗糙集數(shù)據(jù)挖掘算法研究*

楊曉波

（浙江樹人學(xué)院 杭州 314408）

1 引言

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

2 算法原理

約簡算法在數(shù)據(jù)挖掘領(lǐng)域，用于在原始數(shù)據(jù)集中發(fā)現(xiàn)最小子集，并將數(shù)據(jù)進(jìn)行分類。相關(guān)學(xué)者通過分析數(shù)據(jù)的內(nèi)在關(guān)聯(lián)提出了幾種主流約簡算法。Connolly等［7］提出利用屬性值獲取最小約簡的方法，但計算準(zhǔn)確度較差；Y.He 等［8］利用深度層次聚類算法計算最小約簡，計算的準(zhǔn)確度有所提高，但耗時較大；B. Xu 等［9］提出以區(qū)分矩陣為基礎(chǔ)獲取最小約簡，運(yùn)算效率進(jìn)一步提高，但生成規(guī)則較復(fù)雜。本文將在總結(jié)專家學(xué)者研究的基礎(chǔ)上，提出一種基于粗糙集理論的優(yōu)化約簡算法。

該算法以屬性特征為基礎(chǔ)，利用其在區(qū)分矩陣的出現(xiàn)次數(shù)構(gòu)造生成規(guī)則，通過計算獲得最小約簡。由于約簡與區(qū)分矩陣之間存在一定聯(lián)系，在算法設(shè)計時應(yīng)予以考慮，具體的算法設(shè)計流程如圖1所示。

圖1 優(yōu)化約簡算法流程圖

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

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

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

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

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

為了清晰表達(dá)如何通過生成規(guī)則獲得最小約簡，算法的實現(xiàn)流程如圖2所示。

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

圖2 利用生成規(guī)則獲得最小約簡

3 擴(kuò)展模型

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

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

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

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

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

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

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

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

當(dāng)數(shù)據(jù)集元素的屬性值缺失，傳統(tǒng)粗糙集模型的分類誤差將增加，這時，我們借助可變精度擴(kuò)展模型的近似關(guān)系，降低分類誤差，提高數(shù)據(jù)分類的準(zhǔn)確度。

當(dāng)使用可變精度擴(kuò)展模型的近似關(guān)系區(qū)分?jǐn)?shù)據(jù)類型時，相似類與原集合存在部分重疊，且相似類不再用于區(qū)分?jǐn)?shù)據(jù)類型，我們可以利用相似集S(x)來劃分原集合。

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

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

圖3 相似關(guān)系的屬性約簡算法

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

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

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

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

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

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

信息函數(shù)f=U×C。

4 實現(xiàn)過程

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

最小約簡的粗糙集數(shù)據(jù)挖掘算法，實現(xiàn)過程如圖4所示。

圖4 最小約簡算法的實現(xiàn)過程

另外，借助區(qū)分矩陣的生成規(guī)則約簡算法表述如下：

輸入：區(qū)分矩陣T

輸出：約簡集合

Begin

初始值Red=φ

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

5 實驗分析

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

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

表1 數(shù)據(jù)集的基本特性

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

RSL算法找到的約簡如下：

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

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

對于數(shù)據(jù)集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）。

對于數(shù)據(jù)集Food，兩種算法所得到的約簡均為

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

從表1的數(shù)據(jù)比較中，可以得到如下結(jié)論：

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

2）兩種算法在執(zhí)行實例數(shù)較小的數(shù)據(jù)集時，運(yùn)行時間比較接近，當(dāng)在實行實例數(shù)較大的數(shù)據(jù)集時，本文算法的時間復(fù)雜度較低，而且運(yùn)行時間也少于RSL算法。

3）對大多數(shù)數(shù)據(jù)集而言，較短的時間內(nèi)就可以求出所有約簡，約簡算法的執(zhí)行時間取決于兩個主要因素，即實例數(shù)及核的長度，當(dāng)核較大時，約簡計算相對簡單，同時產(chǎn)生的約簡個數(shù)也較少。

存在唯一約簡數(shù)據(jù)集的計算結(jié)果如圖5所示。

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

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

6 結(jié)語

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

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

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

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

4）今后的研究方向包括開發(fā)更有效的屬性頻率加權(quán)機(jī)制，進(jìn)一步降低本文所提算法的復(fù)雜度等。