不協調決策形式背景α屬性約簡

李仲玲

（河北師范大學匯華學院 河北省石家莊市 050091）

形式概念分析是1982年由德國數學家Wille 提出的，是一種對數據進行分析以及獲取知識的一種非常有效的工具，形式概念分析的其中一個重要的研究課題是形式背景的屬性約簡問題，這個理論已被成功地運用到許多領域，比如：模式識別、數據挖掘、信息檢索等。而形式背景是由三部分組成：有限對象集合、有限屬性集合、對象集合與屬性集合間的關系，在實際問題中，相當一部分形式背景都會或多或少的具有若干多余的屬性，這樣導致其所生成的概念格結構會相對復雜很多，為了得到更加簡潔的概念格，需要我們對對應的形式背景或決策形式背景中的數據進行一些必要地處理，也就是要對屬性按照一定的要求進行約簡，因而，我們很有必要找到有效的屬性約簡方法，形式背景的屬性約簡的討論已經得到了一些學者的關注，并取得了很多非常好的研究成果[1-18]。另外，考慮到形式背景是信息系統的一種特殊形式，因此某些信息系統中適用的理論可以在形式背景中得到更加具體的結論。Zhang 等在[1]中提出了基于概念格的屬性約簡理論，并證明了屬性協調集的判定方法，從而構造出了求解約簡的形式概念的差別矩陣的概念；Wu 等給出了粒協調決策形式背景的基本定義，并通過對象的差別屬性矩陣給出了求粒協調決策形式背景的約簡方法[2]；Wang 等介紹了協調決策形式背景的屬性約簡的概念，討論了這種約簡的等價定義，并構造了屬性約簡的判定定理和差別矩陣，為計算此約簡提供了有效的方法[4]；Mi 等在包含度理論和變精度粗糙集理論的基礎之上，提出了不協調目標信息系統的上分布約簡以及下分布約簡的定義，并討論了兩種約簡之間的關系[5]。以上對非決策形式背景、協調決策形式背景的約簡問題討論的比較多，而對不協調決策形式背景的約簡問題討論的相對比較少。

本文基于形式背景中對象集的粒覆蓋，定義了基于包含度的另外一種對象集的覆蓋，從另外一種角度研究了不協調決策形式背景的屬性約簡問題。提出了一種基于包含度的α 約簡，給出了α 協調集的判定定理，并證明了求解α 約簡的辨識矩陣法。

1 基本概念

本部分給出形式背景、決策形式背景、粒覆蓋的相關定義，詳細的表述可參考[2]。

定義1 形式背景S=(U,A,R)是由兩個有限集合U 和A 及兩個集合U 和A 之間的關系R 組成，其U={u1,u2,u3,...,un}是對象集，A={a1,a2,a3,...,am}是屬性集，(xi, aj)∈R 或者xiRaj表示xi具有aj屬性，假設每一個對象xi都至少具有一個屬性aj。

設(U,A,R)和(U,C,Q)是兩個非決策形式背景，則稱(U,A,R,C,Q)是一個決策形式背景，其中U={u1,u2,u3,...,un}是有限對象集，A={a1,a2,a3,...,am}是有限條件屬性集，C={c1,c2,c3,...,ck}是有限決策屬性集，并且。

用*來表示(xi, aj)∈R，用空格來表示這樣一個形式背景就可以用一個表格表現出來。

定義3 設S=(U,A,R,C,Q)是一個決策形式背景，如果對于滿足則稱決策形式背景S 是協調的，否則稱決策形式背景S 為不協調的。

以下討論均為不協調決策形式背景，且決策屬性為一個屬性的決策形式背景。

2 不協調決策形式背景基于協調度的α約簡

定義4 設S=(U,A,R,d,Q)是一個決策形式背景，有限對象集U={x1,x2,......,xn}，對于任意定義

其中| |表示集合中元素的個數。

定義5 設S=(U,A,R,C,Q)是一個決策形式背景，對于有則稱B 為α 協調集；如果屬性子集B 為α 協調集，且B 的任意真子集都不是α 協調集，那么稱B為α 約簡集。

定理1 設S=(U,A,R,d,Q)是一個決策形式背景，若B是α 協調集當且僅當時，有

證明：首先證必要性。

表1：決策形式背景

接下來證充分性。

定義6 設S={U,A,R,C,Q}是一個決策形式背景，定義：

定理2 設S={U,A,R,d,Q}是一個不協調的決策形式背景，若B 是α 協調集當且僅當對非空集合

證明：首先證必要性。

再證充分性。

定理3 設S={U,A,R,d,Q}是一個不協調的決策形式背景，辨識公式的極小析取范式為則所有的是形式背景S 的α 約簡。

證明：由極小析取范式的定義及定理2.2 易證。

例：表1 為一個決策形式背景S={U,A,R,d,Q}，其中U={x1,x2, x3,x4,x5,x6}，A={a1,a2,a3,a4}，C=g0gggggg，其中“ ”代表相應的對象不具有這個屬性，“*”代表相對應的對象具有這個屬性。

由定義2 容易得出

由以上計算及定義6 得：

我們有所有的約簡為

3 結束語

本文從形式背景中對象集的粒覆蓋出發定義了另外一種對象集的覆蓋，這個覆蓋基以包含度為基礎，從而更深入的研究了不協調決策形式背景的屬性約簡問題。提出了一種新的基于包含度的α 約簡，討論了某個屬性子集是α 協調集的判定定理，證明了某個屬性子集為α 約簡的差別矩陣法。接下來，我們將進一步研究α 約簡的算法，并將結果推廣到其他形式背景中。