次屬性原理.pdf

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

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

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

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