一種基於sql語言的粗糙集屬性約簡方法

2023-06-12 13:47:36 2

專利名稱：一種基於sql語言的粗糙集屬性約簡方法
技術領域：
本發明涉及一種粗糙集屬性約簡方法，具體屬於一種基於SQL語言的粗糙集屬性約簡方法。
背景技術：
在數據挖掘的諸多方法中，粗糙集理論與方法對於處理複雜系統不失為一種較為有效的方法，它是由波蘭的Pawlak Z教授於1982年提出的，是一種處理不精確、不確定和模糊知識的軟計算工具。經過二十多年的發展，粗糙集理論已經在信息系統分析、人工智慧、決策支持系統、知識與數據發現、模式識別與分類、故障檢測等方面取得了較為成功的應用。屬性約簡是粗糙集理論中的核心內容之一，它是指在保持知識庫分類能力不變的條件下，刪除其中不相關或不重要的知識。粗糙集屬性約簡的目標就是最小屬性約簡，它已經被證明是NP問題。經典的最小屬性約簡方法是基於區分矩陣的粗糙集屬性約簡方法，但由於該方法在面對大數據集的時候，由於運行時間過長而變得不再實用。

發明內容
本發明的目的在於克服基於區分矩陣的粗糙集屬性約簡方法的不足，提供一種運行速度快又實用的基於SQL語言的粗糙集屬性約簡方法。
本發明提供了一種基於SQL語言的粗糙集屬性約簡方法，該方法利用標準SQL語言中的GROUP BY子句對信息系統分組得到的元組數與原信息系統元組數的比值作為屬性區分能力的度量，對信息系統的屬性集生成的冪集，將冪集中的所有元素按照基數大小排序，根據屬性約簡的目的，如果屬性集中的一個子集為約簡，則包含該子集的其他元素一定不是約簡，這樣可以減少搜索空間，提高約簡速度。具體包括如下步驟(1)輸入信息系統S＝(U，A)，其中U是對象的非空有限集合，A是屬性的非空有限集合；(2)初始化約簡結果集red為空集；(3)生成屬性集A的冪集對屬性集A的元素進行排序，用二進位數(k1，k2，…，k|A|)2來表示A的子集，其中ki＝0或1，當ki＝0表示該子集中不包含A的第i個屬性，當ki＝1表示該子集中包含A的第i個屬性，初始值為(01，02，…，0|A|-1，1)2，用二進位的方法依次加1，直到(11，12，…，1|A|-1，1)2，則得到屬性集A不包含空集的冪集Powerset，對冪集Powerset中元素按照其元素基數大小從小到大排序，將結果放入存儲區中；(4)計算屬性集A的區分能力α(A)通過GROUP BY子句，在屬性集A上對U進行分組運算，得到的元組數|UA|與|U|的比值，即為(A)=|UA||U|;]]>(5)搜索過程依次從存儲區取冪集Powerset中的第一個元素，如果它與整個屬性集A的區分能力一樣，則第一個元素即為一個約簡，並將其放入到約簡結果集中，在冪集Powerset中查找包含該約簡的所有元素，並將其刪除，重複以上過程，直到冪集Powerset為空，這樣可以逐步減少搜索空間，提高約簡速度；(6)停止條件判別冪集Powerset為空，即冪集中所有元素均已處理，停止判斷。
基於SQL語言的粗糙集屬性約簡方法的設計思想在粗糙集理論中，對於信息系統S＝(U，A)，其中U是對象的非空有限集合，A是對象的屬性集，設PA，求不可區分關係IND(P)的一般方法是將對象集U中未分類的個體兩兩比較，比較它們對P的每一個屬性，如果所有的取值都相同，則屬於同一個等價類。根據IND(P)的定義，兩個個體同屬於一個等價類若且唯若對P中的每一個屬性，它們的取值都相同。在標準SQL(Structured Query Language)語言中，GROUP BY子句和COUNT(*)集函數將數據集按某一列(屬性)或多列(屬性)值分組，值相等的為一組，同時得到每組個數。組的個數在粗糙集理論中也就是劃分的等價類的數目，每組所包含對象的個數也就是某一等價類所包含的對象數目。根據上述原理，給出了屬性集區分能力的計算方法設SS＝(U，A)是一個信息系統。設PA，則屬性集P對S＝(U，A)分組(GROUP BY)後，得到信息系統為SP＝(UP，PU{Pnum})，其中Pnum為通過集函數COUNT(*)得到的附加屬性，簡記為SP＝(UP，P′)，則屬性集P的區分能力的計算方法如下式(P)=|Up||U|]]>α(P)越大，它的區分能力越強，說明屬性集P對U的分類越細，且有0＜α(P)≤1。
與現有技術相比，本發明通過粗糙集理論與資料庫技術的耦合，用SQL語言來定義知識以及在約簡過程中搜索策略的改進，減少了搜索空間，提高了約簡速度。
四

圖1為本發明方法的流程圖。
五具體實施例方式
為了更好地理解本發明的技術方案，下面結合附圖和實施例作進一步描述。
實施例1
(1)信息系統S＝(U，A)如表1，其中U＝{1，2，3，4，5}，A＝{a，b，c，d}表1

(2)初始化red＝；(3)生成屬性集A的冪集PowersetPowerset＝{{a}，{b}，{c}，{d}，{a，b}，{a，c}，{a，d}，{b，c}{b，d}，{c，d}，{a，b，c}，{a，b，d}，{b，c，d}，{a，c，d}，{a，b，c，d}}；(4)計算(A)=|UA||U|=1;]]>(5)由於Powerset不為空，則取Powerset中的第一個元素{a}，有({a})=35,]]>由α({a})≠α(A)，從Powerset中刪除{a}；(6)由於Powerset＝{{b}，{c}，{d}，{a，b}，{a，c}，{a，d}，{b，c}{b，d}，{c，d}，{a，b，c}，{a，b，d}，{b，c，d}，{a，c，d}，{a，b，c，d}}不為空，則取Powerset中的第一個元素{b}，有({b})=35,]]>由α({b})≠α(A)，從Powerset中刪除{b}；(7)同理依次從Powerset中刪除{c}和{d}；(8)由於Powerset＝{{a，b}，{a，c}，{a，d}，{b，c}{b，d}，{c，d}，{a，b，c}，{a，b，d}，{b，c，d}，{a，c，d}，{a，b，c，d}}不為空，則取Powerset中的第一個元素{a，b}，有α({a，b})＝1，由α({a，b})＝α(A)，則red＝red∪{{a，b}}，在Powerset中刪除包含{a，b}的元素，即刪除{a，b}，{a，b，c}，{a，b，d}和{a，b，c，d}；(9)由於Powerset＝{{a，c}，{a，d}，{b，c}，{b，d}，{c，d}，{b，c，d}，{a，c，d}}不為空，則取Powerset中的第一個元素{a，c}，有({a,c})=45,]]>由α({a，c})≠α(A)，從Powerset中刪除{a，c}；(10)同理依次從Powerset中刪除{a，d}和{b，c}；(11)由於Powerset＝{{b，d}，{c，d}，{b，c，d}，{a，c，d}}不為空，則取Powerset中的第一個元素{b，d}，有α({b，d})＝1，由α({b，d})＝α(4)，則red＝red∪{{b，d}}，在Powerset中刪除包含{b，d}的元素，即刪除{b，d}，{b，c，d}；(12)由於Powerset＝{{c，d}，{a，c，d}}不為空，則取Powerset中的第一個元素{c，d}，有({c,d})=45,]]>由α({c，d})≠α(A)，從Powerset中刪除{c，d}；(13)由於Powerset＝{{a，c，d}}不為空，則取Powerset中的第一個元素{a，c，d}，有({a,c,d})=45,]]>由α({a，c，d})≠α(A)，從Powerset中刪除{a，c，d}；(14)由於Powerset＝，則得到所有約簡為red＝{{a，b}，{b，d}}，計算完畢。
為了驗證該方法的有效性，從UCI數據集中挑選了5組數據，並和基於區分矩陣的粗糙集屬性約簡方法進行了比較，實驗環境使用的是Windows XP，CPU 2.4GHz，Ram 1GB，C#編程，SQL Server2000為後臺資料庫，實驗結果如下表2表2 兩種約簡算法比較表

從實驗結果數據可以看到，基於SQL語言的粗糙集屬性約簡方法和基於區分矩陣的方法結果完全一樣，但基於SQL語言的粗糙集屬性約簡方法約簡速度快，特別是在屬性少、實例多的時候效果更為明顯。
權利要求
1.一種基於SQL語言的粗糙集屬性約簡方法，其特徵在於包括如下步驟(1)輸入信息系統S＝(U，A)，其中U是對象的非空有限集合，A是屬性的非空有限集合；(2)初始化約簡結果集為空集；(3)生成屬性集A的冪集對屬性集A的元素進行排序，用二進位數(k1，k2，…，k|A|)2來表示A的子集，其中ki＝0或1，當ki＝0表示該子集中不包含A的第i個屬性，當ki＝1表示該子集中包含A的第i個屬性，初始值為(01，02，…，0|A|-1)2，用二進位的方法依次加1，直到(11，12，…，1|A|-1，1)2，則得到屬性集A不包含空集的冪集Powerset，對冪集Powerset中元素按照其元素基數大小從小到大排序，將結果放入存儲區中；(4)計算屬性集A的區分能力α(A)通過GROUP BY子句，在屬性集A上對U進行分組運算，得到的元組數|UA|與|U|的比值，即為(A)=|UA||U|;]]>(5)搜索過程依次從存儲區取冪集Powerset中的第一個元素，如果它與整個屬性集A的區分能力一樣，則第一個元素即為一個約簡，並將其放入到約簡結果集中，在冪集Powerset中查找包含約簡的所有元素，並將其刪除，重複以上過程，直到冪集Powerset為空；(6)停止條件判別冪集Powerset為空。
全文摘要
一種基於SQL語言的粗糙集屬性約簡方法，該方法利用標準SQL語言中的GROUP BY子句對信息系統分組得到的元組數與原信息系統元組數的比值作為屬性區分能力的度量，對信息系統的屬性集生成的冪集，將冪集中的所有元素按照基數大小排序，根據屬性約簡的目的，如果屬性集中的一個子集為約簡，則包含該子集的其他元素一定不是約簡，這樣可以減少搜索空間，提高約簡速度。本發明方法實現靈活簡單，針對性強，和資料庫實現了有效地耦合，可廣泛應用於粗糙集屬性約簡領域。
文檔編號G06F17/30GK101082925SQ20071006228
公開日2007年12月5日 申請日期2007年7月9日 優先權日2007年7月9日
發明者曹付元, 梁吉業, 姜廣, 寧姝 申請人:山西大學