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

馬凌 喻幸

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

關鍵詞：粗糙集；SQL語言；屬性約簡

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

1 理論基礎

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

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

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

2 屬性約簡算法

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

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

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

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

SELECT COUNT（ DISTINCT ai） AS NUM

into temp

FROM S

GROUP BY A-{ai}

Step 2：統計表temp中數值為1的記錄個數占記錄總數的比例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為不必要屬性，則繼續從A-{ai}中尋找不必要屬性，最終得到約簡屬性集。

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

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

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

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

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

Step 3：i=i+1，轉到Step 2；

Step 4：A=A-{ai}，n=n-1，轉Step 2；

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

3 算法對比

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

表1 一個信息系統S

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

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

Confidence=0.86>0.85

則屬性a1為不必要屬性。

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

Confidence=0.5<0.85

則屬性a2為必要屬性。

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

Confidence=0.6<0.85

則屬性a3為必要屬性。

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

Confidence=0.25<0.85

則屬性a3為必要屬性。

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

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

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

4 結束語

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

參考文獻

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

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

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

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

作者簡介：馬凌（1981-），女，碩士，講師，主要研究領域為數據挖掘。

喻幸（1981-），男，碩士，主要研究領域為計算機應用技術。