次屬性原理.pdf

1、目前，一個數(shù)據(jù)集合常常由許多用戶共享。但不同的用戶希望從這個數(shù)據(jù)庫中獲得的知識卻可能不同。這意味著我們需要能夠根據(jù)用戶需求從數(shù)據(jù)庫中挖掘滿足用戶需求解的有效算法。如果把用戶的需求看作是一種語義，那么，建立在信息系統(tǒng)條件屬性集合上的屬性序可以理解為描述用戶對需求的一種原語。這樣，尋找滿足用戶需求解的問題可以轉(zhuǎn)變?yōu)楦鶕?jù)屬性序計算reduct的問題。屬性序作為一種描述用戶需求的原語，對從信息系統(tǒng)中尋找用戶需要的規(guī)則與例外有著重要的意義。因此，

2、仔細(xì)研究屬性序與信息系統(tǒng)reduct之間的關(guān)系，對信息系統(tǒng)解的計算和應(yīng)用都是必要的。 基于屬性序的reduct算法已經(jīng)在文[WW01]中提出。由于該算法對reduct完備且其輸出對給定的屬性序唯一，因此可以看作是由屬性序集合到reduct集合的一個映射。因為不同的屬性序可以對應(yīng)相同的reduct，因此這個影射不是一一的映射。這就產(chǎn)生了一些問題：給定一個reduct，哪些屬性序與其對應(yīng)?對于兩個不同的屬性序，是否存在直接判定其re

3、duct相同的準(zhǔn)則?在一定條件下，是否可以根據(jù)用戶的特定需求從已知的解推斷其它的解?本文基于這些問題展開討論。主要工作包括以下幾個方面： 一、通過形式化屬性序reduct算法，分析了屬性序集合和reduct集合之間的關(guān)系，證明了鄰近屬性序偶基本判定定理，給出了一系列直接判定鄰近屬性序偶reduct相等的判定規(guī)則。 二、提出了次屬性原理，并由此構(gòu)造性地證明了次屬性定理。次屬性定理是全文的核心，一方面，它可以作為直接判定由r

4、educt屬性向右移動獲得的鄰近屬性序偶reduct是否相同的判定準(zhǔn)則；另一方面，它又可以作為設(shè)計任意屬性序偶reduct是否相同判定準(zhǔn)則的基礎(chǔ)。 三、基于次屬性定理和屬性范序，設(shè)計了直接判定任意屬性序偶reduct是否相同的判定準(zhǔn)則，并證明了利用次屬性定理可以在屬性序集合中確定具有相同reduct的屬性序的范圍。 四、次屬性定理的證明依賴差別矩陣，它暗示的次屬性算法的復(fù)雜性為O(n2×m)。由于大多數(shù)信息系統(tǒng)的對象的個