s-粗集

S-粗集為動態數據挖掘-規律發現研究提供理論支持。在2002年，史開泉對Z.Pawlak粗集做出了改進，給出動態R-元素等價類的概念；提出S-粗集（singular rough sets），S-粗集是以具有動態特性的R-元素等價類x定義的。

基本介紹

• 中文名：s-粗集
• 外文名：singular rough sets
• 提出時間：2002年
• 改進人：史開泉

簡介

波蘭數學家Z.Pawlak 在1982 提出的粗糙集(Rough Set) ，給出粗集的一般性研究，Z.Pawlak粗集是以R-元素等價類[x]定義的。Z.Pawlak粗集是一個具有靜態特徵的元素集合X∈U的粗集。

2002年史開泉對Z.Pawlak粗集做出改進，給出動態R-元素等價類的概念；提出了S-粗集（singular rough sets），S-粗集是以具有動態特性的R-元素等價類[x]定義的。S-粗集具有兩類基本形式：單向S-粗集（one directions singular rough sets）單向S-粗集對偶（dual of one directions singular rough sets）,雙向S-粗集（two directions singular rough sets）S-粗集為動態數據挖掘-規律發現研究提供了理論支持。

理論特點

粗集(rough set) 理論的特點是不需要預先給定某些特徵或屬性的數量描述， 如統計學中的機率分布，模糊集理論中的隸屬度或隸屬函式等，而是直接從給定問題出發，通過不可分辨關係和不可分辨類，確定問題的近似域，從而找出該問題中的內在規律。粗集理論同模糊集、神經網路、證據理論等其它理論均成為不確定性計算的一個重要分支。

粗集理論是根據已有的給定問題的知識，將問題的論域進行劃分，然後對劃分後的每一個組成部分確定其對某一概念的支持， 即肯定支持此概念或不支持此概念。在粗集理論中，上述情況分別用3 個近似集合來表示正域、負域和邊界。

在數據挖掘中，從實際系統採集到的數據可能包含各種噪聲， 存在許多不確定的因素和不完全信息有待處理。傳統的不確定信息處理方法，如模糊集理論、證據理論和機率統計理論等，因需要數據的附加信息或先驗知識(難以得到)，有時在處理大量數據的資料庫方面無能為力。粗集作為一種軟計算方法，可以克服傳統不確定處理方法的不足，並且和它們有機結合，可望進一步增強對不確定、不完全信息的處理能力。

粗集理論中，知識被定義為對事物的分類能力。這種能力由上近似集、下近似集、等價關係等概念體現。因為粗集處理的對象是類似二維關係表的信息表（決策表）。成熟的關係資料庫管理系統和新發展起來的數據倉庫管理系統，為粗集的數據挖掘奠定了堅實的基礎。

分析方法

粗集從決策表挖掘規則，輔助決策，其關鍵步驟是求值約簡或數據濃縮，包括屬性約簡Wong SK和Ziarko W已經證明求最小約簡是一個NP hard 問題。最小約簡的求解需要屬性約簡和值約簡兩個過程，決策表約簡涉及到核和差別矩陣兩個重要概念。一般來講，決策表的相對約簡有許多, 最小約簡（含有最小屬性）是人們期望的。另一方面，決策表的核是唯一的，它定義為所有約簡的交集，所以，核可以作為求解最小約簡的起點。差別矩陣突出屬性的分辨能力，從中可以求出決策表的核，以及約簡規則。藉助啟發式搜尋解決，苗奪謙等人從資訊理論的角度對屬性的重要性作了定義，並在此基礎上提出了一種新的知識約簡算法MIBARK，但其對最小約簡都是不完備的，此外，上述方法還只局限於完全決策表。Marzena K套用差別矩陣，推廣了等價關係（相似關係） 、集合近似等概念，研究了不完全決策表（屬性的取值含有空值的情況）的規則的發展問題， 從而為粗集的實用化邁出了可喜的一步。Marzena K還比較了幾種不完全系統的分析方法，得出如下結論：

①一個規則是確定的，如果此規則在原不完全系統的每個完全拓展中是確定的；

②刪除從不完全決策表包含空值的對象後, 採掘的知識可能成為偽規則.

數學基礎

粗集的數學基礎是集合論，難以直接處理連續的屬性. 而現實決策表中連續屬性是普遍存在的, 因此,連續屬性的離散化是制約粗集理論實用化的難點之一, 這個問題一直是人工智慧界關注的焦點. 連續屬性的離散化的根本出發點, 是在儘量減少決策表信息損失的前提下(保持決策表不同類對象的可分辨關係) , 得到簡化和濃縮的決策表, 以便用粗集理論分析, 獲得決策所需要的知識. 最優離散化問題(離散的切點數最少) 已被證明是NP - hard 問題, 利用一些啟發式算法可以得到滿意的結果. 總體上講, 現有離散化方法主要分為非監督離散和監督離散化. 前者包括等寬度(將連續值屬性的值域等份) 與等頻率離散化(每個離散化區間所含的對象相同) . 非監督離散化的方法簡單, 其忽略了對象的類別信息, 必須能用在屬性具有特殊分布的情況中. 針對上述的問題, 監督離散化方法考慮分類的一些信息, 要提高離散效果.有代表性的監督離散化方法有下面幾種:

① Holte 提出了一種貪婪的單規則離散器(one rule dis2cretizer) 方法;

② 統計檢驗方法;

③ 信息熵方法等.

這一些方法各有特點, 但普遍存在一個不足, 即每個屬性的離散化過程為相互獨立的, 忽略屬性之間的關聯, 從而使得離散結果中含有冗餘或不合理的分割點. 針對這一個問題, 有的人給出了一種連續屬性的整體離散化方法, 實驗表明其, 不僅能顯著減少離散化劃分點與歸納規則數, 而且提高分類精度. 連續屬性離散化還存在的問題為缺乏遞增的離散化方法, 即當新的對象加入決策表時候, 原有的分割點可能不是其最優或最滿意的.

數據挖掘

粗集理論與其它軟計算方法的結合, 能夠提高前數據挖掘能力. Mohua Banerjee 等利用集理論獲得了初始規則集, 然後, 構造對應的模糊多層神經網路(規則的置信度對應網路連線權) , 訓練後可得到精化知識. 粗集與其它軟計算方法的集成為數據挖掘的一種趨勢. 基於粗集的數據挖掘在以下方面有待於深化.

(1) 粗集和其它軟計算方法的進一步結合問題;

(2) 粗集知識採掘的遞增算法;

(3) 粗集基本運算的並行算法和硬體實現, 大幅度改善數據挖掘的效率. 已有的粗集軟體適用範圍還比較有限. 決策表里的實例數量和屬性數量受限制. 面對大量數據, 有必要設計高效的啟發式簡化算法或研究實時性較好並行算法;

(4) 擴大處理屬性的類型範圍, 實際資料庫離散化方法主要分為非監督離散化和監督離散化. 前者包括等寬度(將連續值屬性值域等份) 和等頻率離散化(每個離散化區間所含的對象相同) . 非監督離散化方法很簡單, 忽略了對象的類別信息, 只能用在屬性具有特殊分布的情況中. 針對上述的問題, 監督離散化方法考慮分類信息, 提高了離散效果. 比較有代表性的監督離散化方法有下面幾種: ① Holte 提出了一種貪婪的單規則離散器(one rule dis2cretizer) 方法; ② 統計檢驗方法; ③ 信息熵方法等. 這些方法各有特點, 但都存在一個不足, 即每個屬性的離散化過程是相互獨立的, 忽略了屬性之間的關聯, 從而使得離散結果中含有冗餘或不合理的分割點. 針對這個問題, 有人給出了一種連續屬性的整體離散化方法, 實驗表明, 不僅能顯著減少離散化劃分點和歸納規則數, 而且提高了分類精度. 連續屬性離散化還存在的問題是缺乏遞增的離散化方法, 即當新的對象加入決策表時, 原有的分割點可能不是最優或最滿意的.

挖掘能力

粗集理論和其它軟計算方法的結合, 能夠提高數據挖掘能力. Mohua Banerjee 等利用集理論獲得初始規則集, 然後, 構造對應的模糊多層神經網路(規則的置信度對應網路的連線權) [10 ] , 訓練後可得到精化的知識. 粗集與其它軟計算方法的集成是數據挖掘的一種趨勢. 基於粗集的數據挖掘在以下方面有待深化.

(1) 粗集和其它軟計算方法的進一步結合問題;

(2) 粗集知識採掘的遞增算法;

(3) 粗集基本運算的並行算法及硬體實現, 將大幅度改善數據挖掘的效率. 已有的粗集軟體適用範圍還很有限. 決策表中的實例數量和屬性數量受限制. 面對大量的數據, 有必要設計高效的啟發式簡化算法或研究實時性較好的並行算法;

(4) 擴大處理屬性的類型範圍, 實際資料庫的屬性類型是多樣的, 既有離散屬性, 也有連續屬性; 既有字元屬性, 也有數值屬性. 粗集理論只能處理離散屬性, 因此, 需要設計連續值的離散算法.