一種基于SQL的用戶自定義精度的粗糙集屬性約簡算法

馬凌 喻幸

摘 要：將數(shù)據(jù)庫的關(guān)系運算運用于粗糙集的屬性約簡，引入用戶自定義精度，改進(jìn)基于SQL的屬性約簡算法。仿真實驗結(jié)果表明，該方法與經(jīng)典粗糙集相關(guān)方法相比，有更高的執(zhí)行效率和抗噪性，為粗糙集理論更廣泛地應(yīng)用于海量數(shù)據(jù)的數(shù)據(jù)挖掘提供了一種方法。

關(guān)鍵詞：粗糙集；SQL語言；屬性約簡

數(shù)據(jù)庫系統(tǒng)具有存儲空間利用率高、存取效率高等優(yōu)點，如果將粗糙集理論中的決策表以關(guān)系數(shù)據(jù)庫二維表的形式表示，通過將粗糙集理論中的相關(guān)算法嵌入到數(shù)據(jù)庫管理系統(tǒng)中，實現(xiàn)對屬性約簡算法的改進(jìn)。在標(biāo)準(zhǔn)SQL語言中，GROUP BY子句可將數(shù)據(jù)庫中二維表的數(shù)據(jù)按某一列或多列的取值進(jìn)行分組，值相等的為一組，該操作可對應(yīng)粗糙集理論中劃分等價類。而聚集函數(shù)COUNT（*）可統(tǒng)計每組所包含的記錄個數(shù)，即為粗糙集理論中等價類所包含的對象數(shù)目。基于SQL的屬性約簡算法已有部分學(xué)者進(jìn)行了研究。馮林和李天瑞[1]提出了用SQL語句求數(shù)據(jù)庫中相對核屬性、屬性約簡和值核的算法。田迪和劉建平[2]提出了基于SQL語言的條件信息熵屬性約簡算法。劉井蓮[3]給出了一種基于SQL的屬性約簡算法，該算法是從條件屬性集做遞減，不需要存儲中間結(jié)果，具有空間復(fù)雜度低的優(yōu)點，同時易于改造成并行算法，能求出所有約簡。但該算法缺乏對噪音數(shù)據(jù)的適應(yīng)能力，不適應(yīng)高速公路管理系統(tǒng)中海量數(shù)據(jù)的數(shù)據(jù)分析。下面將在討論這種算法的基礎(chǔ)上，提出一種由用戶自定義精確度的基于SQL的屬性約簡算法。

1 理論基礎(chǔ)

定義1：一個信息表的知識表達(dá)系統(tǒng)可以表示為四元組S=，其中，U是對象的有限集合，也稱為論域；R=C∪D為屬性的有限集合，C為條件屬性的子集，D為決策屬性的子集；是屬性值的集合，Vr為屬性r的值域；f：U×R→V為一個信息函數(shù)，U的任一元素取屬性r在V中有唯一確定值。

如果U為一個論域，P為U上的一個屬性集合，r∈P，且ind（P-r）=ind（P），則稱屬性r在P中是不必要的；否則，稱r在P中是必要的。去掉不必要的屬性不會改變屬性集合的分類能力；反之，若去掉一個必要的屬性，則一定會改變屬性集合的分類能力。

定義2：設(shè)U為一個論域，P、Q為U上的兩個屬性集合，且Q為P的子集，若ind（Q）=ind（P）且Q中沒有不必要的屬性；則稱Q是P的一個約簡。如果Q是P的約簡，則U中通過P可區(qū)分的對象，同樣可以用Q來區(qū)分。通常P的簡化不止一個，P的所有簡化族記為RED（P）。

2 屬性約簡算法

算法1：判斷ai是否為符合用戶自定義精確度的不必要屬性算法

輸入：信息系統(tǒng)S=（U，A）， accurate，ai。其中，accurate為用戶輸入的精確度，ai為需要判斷的屬性。

輸出：1（表示該屬性為不必要屬性）或者0（表示該屬性為必要屬性）

Step 1：統(tǒng)計S中根據(jù)A-{ai}分組后，每組包含的記錄個數(shù)，生成新表temp。方法如下：

SELECT COUNT（ DISTINCT ai） AS NUM

into temp

FROM S

GROUP BY A-{ai}

Step 2：統(tǒng)計表temp中數(shù)值為1的記錄個數(shù)占記錄總數(shù)的比例Confidence。方法如下：

DECLARE @Confidence decimal（3，2），@ConCount int，@TotalCount int

SELECT @TotalCount=COUNT（*）

FROM temp

SELECT @ConCount=COUNT（*）

FROM temp

WHERE NUM=1

SELECT @ConCount

SET @Confidence=cast（@ConCount as decimal（3，2））/@TotalCount

SELECT @Confidence

Step 3：若Confidence>accurate，輸出1，否則，輸出0。

由算法1可判斷出ai是否為符合用戶自定義精確度的不必要屬性。如果ai為不必要屬性，則繼續(xù)從A-{ai}中尋找不必要屬性，最終得到約簡屬性集。

算法2 基于SQL的用戶自定義精確度的屬性約簡算法

輸入：信息系統(tǒng)S=（U，A）， accurate。其中，A=a1，a2，…，an為屬性集，accurate為用戶輸入的精確度。

輸出：A所有的屬性約簡。

Step 1：設(shè)初始約簡的集合為red=？覬，flag=0；

Step 2：如果i<=n，則根據(jù)算法4.3判斷ai是否為符合用戶自定義精確度的不必要屬性。若算法4.3輸出1，則flag=1，轉(zhuǎn)到Step 4，若i>n，轉(zhuǎn)Step 5；

Step 3：i=i+1，轉(zhuǎn)到Step 2；

Step 4：A=A-{ai}，n=n-1，轉(zhuǎn)Step 2；

Step 5：若flag的值為0，則屬性集A為屬性約簡，將其加入集合red，結(jié)束。

3 算法對比

下面通過一個例子來說明文獻(xiàn)[4]給出算法的局限性，以及文章提出的用戶自定義精確度基于SQL的屬性約簡算法的有效性。設(shè)S=（U，A），其中U={U1，U2，U3，U4，U5，U6，U7，U8}，屬性集A={a1，a2，a3，a4}。信息系統(tǒng)見表l。

表1 一個信息系統(tǒng)S

根據(jù)文獻(xiàn)[4]給出的算法，分別計算IsUnnecessary（a2，a3，a4，a1）、IsUnnecessary（a1，a3，a4，a2）、IsUnnecessary（a1，a2，a4，a3）、IsUnnecessary（a1，a2，a3，a4）均得到的結(jié)果為false，即所有屬性均為必要屬性無法實現(xiàn)屬性約簡。而采用算法2，設(shè)用戶輸入的精度為0.85。運算過程如下：

（1）先根據(jù)算法1，計算屬性a1的Confidence。

Confidence=0.86>0.85

則屬性a1為不必要屬性。

（2）根據(jù)算法4.3，計算屬性a2在屬性集A={a2，a3，a4}中的Confidence。

Confidence=0.5<0.85

則屬性a2為必要屬性。

（3）根據(jù)算法4.3，計算屬性a3在屬性集A={a2，a3，a4}中的Confidence。

Confidence=0.6<0.85

則屬性a3為必要屬性。

（4）根據(jù)算法4.3，計算屬性a4在屬性集A={a2，a3，a4}中的Confidence。

Confidence=0.25<0.85

則屬性a3為必要屬性。

（5）通過以上計算，可得到{a2，a3，a4}為該信息系統(tǒng)的一個約簡，同理，可得到{a1，a3，a4}也為信息系統(tǒng)的一個約簡。

為了驗證算法2的有效性，文章從UCI數(shù)據(jù)集中挑選了4組數(shù)據(jù)，并和文獻(xiàn)[4]給出的算法以及經(jīng)典的可分辨矩陣約簡算法進(jìn)行了比較，實驗環(huán)境使用的是Windows 7家庭普通版，CPU雙核 1.33GHz，RAM 2.00GB，Java編程，SQL Server 2005為后臺數(shù)據(jù)庫。用戶自定義精度為0.85，實驗結(jié)果見表2。

由以上實驗結(jié)果數(shù)據(jù)可以看出，算法2比文獻(xiàn)[4]中的算法能夠更好的進(jìn)行屬性約簡，約簡后屬性的個數(shù)更少，適用于海量數(shù)據(jù)的屬性約簡。由于算法2需要計算精度，所以相比之下執(zhí)行時間要長一點。算法2與可分辨矩陣約簡算法相比在效率方面具有明顯的優(yōu)勢。

4 結(jié)束語

文章研究了基于SQL的屬性約簡算法，發(fā)現(xiàn)了算法中存在的問題，提出一種由用戶自定義精度的基于SQL的屬性約簡算法，并通過實驗證明該算法的有效性，為海量數(shù)據(jù)的數(shù)據(jù)挖掘提供了新的途徑。

參考文獻(xiàn)

[1]吳學(xué)輝.基于粗糙集的決策樹算法在高校評教中的應(yīng)用[D].太原：太原理工大學(xué)，2011.

[2]馮林，李天瑞.基于SQL的屬性核與約簡高效計算方法[J].計算機(jī)科學(xué)，2010，37（1）：236-238.

[3]田迪，劉建平.基于SQL的屬性約簡算法的改進(jìn)[J].工業(yè)控制計算機(jī)，2011，24（6）：93-94.

[4]劉井蓮.一種基于SQL的屬性約簡算法[J].科學(xué)技術(shù)與工程，2010，10（25）：6291-6292.

作者簡介：馬凌（1981-），女，碩士，講師，主要研究領(lǐng)域為數(shù)據(jù)挖掘。

喻幸（1981-），男，碩士，主要研究領(lǐng)域為計算機(jī)應(yīng)用技術(shù)。