不協(xié)調(diào)決策形式背景α屬性約簡(jiǎn)

李仲玲

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

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

本文基于形式背景中對(duì)象集的粒覆蓋，定義了基于包含度的另外一種對(duì)象集的覆蓋，從另外一種角度研究了不協(xié)調(diào)決策形式背景的屬性約簡(jiǎn)問(wèn)題。提出了一種基于包含度的α 約簡(jiǎn)，給出了α 協(xié)調(diào)集的判定定理，并證明了求解α 約簡(jiǎn)的辨識(shí)矩陣法。

1 基本概念

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

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

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

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

定義3 設(shè)S=(U,A,R,C,Q)是一個(gè)決策形式背景，如果對(duì)于滿足則稱決策形式背景S 是協(xié)調(diào)的，否則稱決策形式背景S 為不協(xié)調(diào)的。

以下討論均為不協(xié)調(diào)決策形式背景，且決策屬性為一個(gè)屬性的決策形式背景。

2 不協(xié)調(diào)決策形式背景基于協(xié)調(diào)度的α約簡(jiǎn)

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

其中| |表示集合中元素的個(gè)數(shù)。

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

定理1 設(shè)S=(U,A,R,d,Q)是一個(gè)決策形式背景，若B是α 協(xié)調(diào)集當(dāng)且僅當(dāng)時(shí)，有

證明：首先證必要性。

表1：決策形式背景

接下來(lái)證充分性。

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

定理2 設(shè)S={U,A,R,d,Q}是一個(gè)不協(xié)調(diào)的決策形式背景，若B 是α 協(xié)調(diào)集當(dāng)且僅當(dāng)對(duì)非空集合

證明：首先證必要性。

再證充分性。

定理3 設(shè)S={U,A,R,d,Q}是一個(gè)不協(xié)調(diào)的決策形式背景，辨識(shí)公式的極小析取范式為則所有的是形式背景S 的α 約簡(jiǎn)。

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

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

由定義2 容易得出

由以上計(jì)算及定義6 得：

我們有所有的約簡(jiǎn)為

3 結(jié)束語(yǔ)

本文從形式背景中對(duì)象集的粒覆蓋出發(fā)定義了另外一種對(duì)象集的覆蓋，這個(gè)覆蓋基以包含度為基礎(chǔ)，從而更深入的研究了不協(xié)調(diào)決策形式背景的屬性約簡(jiǎn)問(wèn)題。提出了一種新的基于包含度的α 約簡(jiǎn)，討論了某個(gè)屬性子集是α 協(xié)調(diào)集的判定定理，證明了某個(gè)屬性子集為α 約簡(jiǎn)的差別矩陣法。接下來(lái)，我們將進(jìn)一步研究α 約簡(jiǎn)的算法，并將結(jié)果推廣到其他形式背景中。