信息系統(tǒng)中基于屬性貼近度的屬性約簡(jiǎn)算法研究

何建倉(cāng)* 侯澤民

（鄭州科技學(xué)院 信息工程學(xué)院，河南 鄭州450064）

粗糙集理論[1-2]由Pawlak 于1982 年提出，是一種處理不精確、不完備等知識(shí)的數(shù)據(jù)分析方法，并被廣泛應(yīng)用于人工智能、知識(shí)發(fā)現(xiàn)等領(lǐng)域。作為粗糙集的核心內(nèi)容，屬性約簡(jiǎn)[3]是刪除屬性集中的冗余屬性，得到不影響原有屬性集分類能力的簡(jiǎn)化屬性集。目前，針對(duì)屬性約簡(jiǎn)，許多學(xué)者利用知識(shí)劃分相似性[4-5]、強(qiáng)化正域[6]、粒度[7-8]、相似關(guān)系[9]、類間區(qū)分度[10]、區(qū)分矩陣[11]等方法提出了相應(yīng)的屬性約簡(jiǎn)改進(jìn)算法，豐富了粗糙集的理論體系。本文在文獻(xiàn)[4，5]的基礎(chǔ)上，利用屬性貼近度來刻畫屬性集之間的相似程度，并結(jié)合屬性貼近度給出屬性約簡(jiǎn)滿足的條件，進(jìn)而提出了基于屬性貼近度的屬性約簡(jiǎn)改進(jìn)算法，進(jìn)一步豐富了信息系統(tǒng)中不確定信息度量理論。

1 基本概念

定義1[3]設(shè)四元組S=（U，A，V，f）為一個(gè)信息系統(tǒng)，其中：

①U 為論域，且U={x1，x2，…，xn}（n 為論域U 中對(duì)象個(gè)數(shù)）；

②A 為屬性集，且A={a1，a2，…，am}（m 為屬性集A 中屬性個(gè)數(shù)）；

③V 為所有屬性的取值范圍，即V=∪{Vai}（ai為屬性集A中某個(gè)屬性，1≤i≤m）；

④f：U×A→V，即對(duì)任意屬性ai和對(duì)象x，均有f（x，a）∈Vai。

定義2[3]設(shè)U 為論域，P 是U 上的等價(jià)關(guān)系，[x]P={y|f（x，P）=f（y，P），x、y∈U}稱為x 在信息系統(tǒng)中的P 等價(jià)類，U/P={[x]P|x∈U}為信息系統(tǒng)中P 針對(duì)U 的劃分。

性質(zhì)1[3]設(shè)S=（U，A，V，f）為一個(gè)信息系統(tǒng)，P、Q?A，對(duì)任意x∈U，則有：

（1）若P?Q，則有U/Q?U/P，且[x]Q?[x]P，此時(shí)稱劃分U/Q更精細(xì)，劃分U/P 更粗糙。

（2）若P=Q，則有U/P=U/Q，且[x]P=[x]Q，此時(shí)稱P、Q 劃分能力相同。

定義3[3]設(shè)S=（U，A，V，f）為一個(gè)信息系統(tǒng)，P?A，對(duì)任意的屬性a∈P，若U/P-{a}≠U/P，則稱a 在P 中是必要的，否則稱a在P 中是不必要的。

定義4[3]設(shè)S=（U，A，V，f） 為一個(gè)信息系統(tǒng)，P?A，若U/P=U/A，且對(duì)對(duì)任意的屬性a∈P，均有U/P-{a}≠U/A，則稱P為A 的一個(gè)約簡(jiǎn)。

2 屬性貼近度

定義5 設(shè)S=（U，A，V，f）為一個(gè)信息系統(tǒng)，P、Q?A，P、Q 針對(duì)U 的劃分分別為U/P={[xi]P|xi∈U}，U/Q={[xi]Q|xi∈U}，其中1≤i≤|U|。對(duì)于任意的xi∈U，[xi]P、[xi]Q之間的相似性定義為：

則稱sim（[xi]P，[xi]Q）為等價(jià)類[xi]P、[xi]Q之間的貼近程度。由定義5 可知，sim（[xi]P，[xi]Q）度量的是等價(jià)類[xi]P、[xi]Q之間的貼近程度，其值越大，說明[xi]P、[xi]Q越貼近。

性質(zhì)2 設(shè)S=（U，A，V，f）為一個(gè)信息系統(tǒng)，P、Q?A，對(duì)于任意的xi∈U，則有1/|U|≤sim（[xi]P，[xi]Q）≤1，且sim（[xi]P，[xi]Q）=sim（[xi]Q，[xi]P）。

證明：對(duì)于任意的xi∈U，則有{xi}?[xi]P∩[xi]Q?U，且[xi]P、[xi]Q?U，則知1≤|[xi]P∩[xi]Q|≤|U|，且|[xi]P|≤|U|，|[xi]Q|≤|U|，從而1/|U|≤sim（[xi]P，[xi]Q）≤1。另外，根據(jù)定義5，可得sim（[xi]P，[xi]Q）=sim（[xi]Q，[xi]P）。

定義6 設(shè)S=（U，A，V，f）為一個(gè)信息系統(tǒng)，P、Q?A，P、Q 針對(duì)U 的劃分分別為U/P={[xi]P|xi∈U}，U/Q={[xi]Q|xi∈U}，其中1≤i≤|U|。屬性集P、Q 之間的相似性定義為：

則稱S（P，Q）為P、Q 之間的屬性貼近度。由定義6 可知，S（P，Q）度量的是屬性集P、Q 針對(duì)U 的劃分U/P、U/Q 之間的相似程度，其值越大，說明U/P、U/Q 越相似。

性質(zhì)3 設(shè)S=（U，A，V，f）為一個(gè)信息系統(tǒng)，P、Q?A，則有1/|U|≤S（P，Q）≤1，且S（P，Q）=S（Q，P）。

另外，根據(jù)定義6，可得S（P，Q）=S（Q，P）。

定理1 設(shè)S=（U，A，V，f）為一個(gè)信息系統(tǒng)，P、Q?A，P、Q 針對(duì)U 的劃分分別為U/P={[xi]P|xi∈U}，U/Q={[xi]Q|xi∈U}，其中1≤i≤|U|。若S（P，Q）=1，則有U/P=U/Q。

定理2 設(shè)S=（U，A，V，f）為一個(gè)信息系統(tǒng)，P?Q?R?A，P、Q、R 針對(duì)U 的劃分分別為U/P= {[xi]P|xi∈U}，U/Q= {[xi]Q|xi∈U}，U/R={[xi]R|xi∈U}，其中1≤i≤|U|，則有S（P，R）≤S（Q，R）。

證明：若P?Q?R，則由性質(zhì)1（1）可知，對(duì)任意的xi∈U，有[xi]R?[xi]Q?[xi]P。根據(jù)定義5 可知，sim（[xi]P，[xi]R）=min（|[xi]P∩[xi]R|/|[xi]P|，|[xi]P∩[xi]R|/|[xi]R|）=min（|[xi]R|/|[xi]P|，|[xi]R|/|[xi]R|）=|[xi]R|/|[xi]P|，同理可得sim（[xi]Q，[xi]R）=|[xi]R|/|[xi]Q|。由于[xi]Q?[xi]P，所以|[xi]Q|≤|[xi]P|，1/|[xi]P|≤1/|[xi]Q|，|[xi]R|/|[xi]P|≤|[xi]R|/|[xi]Q|，由定義6 可知，S（P，R）≤S（Q，R）。

定理2 說明，對(duì)于P?Q，隨著P 中屬性的不斷增加，P 越與Q 相似，P 針對(duì)U 的劃分越與Q 針對(duì)U 的劃分相似。

3 屬性約簡(jiǎn)

定理3 設(shè)S=（U，A，V，f）為一個(gè)信息系統(tǒng)，P?A，對(duì)任意的屬性a∈P 在P 中是必要的當(dāng)且僅當(dāng)S（P-{a}，A）≠S（P，A）。

證明：一方面，由定義3 可知，若a 在P 中是必要的，則有U/P-{a}≠U/P，則必存在xi∈U，使得[xi]P≠[xi]P-{a}，而由性質(zhì)1（1）可知[xi]P-{a}?[xi]P，則知[xi]P-{a}?[xi]P，從而根據(jù)定理2 可知S（P-{a}，A）＜S（P，A），即S（P-{a}，A）≠S（P，A）。另一方面，若S（P-{a}，A）≠S（P，A），則必存在一個(gè)xi∈U，使得[xi]P≠[xi]P-{a}，U/P-{a}≠U/P，所以a 在P 中是必要的。

定理4 設(shè)S=（U，A，V，f）為一個(gè)信息系統(tǒng)，P?A，對(duì)任意的屬性a∈P 在P 中是必要的且S（P，A）=1，則稱P 為A 的一個(gè)約簡(jiǎn)。

證明：由定理1 可知，若S（P，A）=1，則有U/P=U/A。又知對(duì)于屬性集P?A，其任意的屬性a∈P 在P 中是必要的，即U/P-{a}≠U/P，根據(jù)定義4 可知，P 為A 的一個(gè)約簡(jiǎn)。

4 基于屬性貼近度的屬性約簡(jiǎn)改進(jìn)算法

本算法將從屬性集A 中選擇其必要屬性作為初始約簡(jiǎn)集，然后在此基礎(chǔ)上逐漸添加屬性來求解信息系統(tǒng)的屬性約簡(jiǎn)。下面給出基于屬性貼近度的屬性約簡(jiǎn)改進(jìn)算法。

輸入：一個(gè)信息系統(tǒng)S=（U，A，V，f）。

輸出：信息系統(tǒng)的約簡(jiǎn)Red（S）。

步驟1：令P=?。對(duì)任意屬性a∈A，若S（A-{a}，A）＜1，令P=P∪{a}；

步驟2：令Red（S）=P；

步驟3：若S（Red（S），A）=1，則跳轉(zhuǎn)到步驟5，否則，執(zhí)行步驟4；

步驟4：對(duì)任意的屬性b∈A-Red（S）}，計(jì)算S（Red（S）∪{b}，A），并將使S（Red（S）∪{b}，A）值最大的屬性并入Red（S）中，轉(zhuǎn)步驟3。

步驟5：算法結(jié)束，輸出約簡(jiǎn)Red（S）。

5 實(shí)例分析

下面以文獻(xiàn)[3]中的信息系統(tǒng)為例，來驗(yàn)證本文算法的有效性，其中文獻(xiàn)[3]得到的約簡(jiǎn)為{a1，a2}、{a2，a4}。

表1 信息系統(tǒng)

（1）令P=?。對(duì)任意屬性a∈A，計(jì)算S（A-{a}，A）。由定義6可知，S（A-{a1}，A）=S（A-{a3}，A）=S（A-{a4}，A）=1，S（A-{a，2}，A）=4/5＜1，則知P={a，2}；

（2）令Red（S）=P={a，2}；

（4）對(duì)任意的屬性b∈A-Red（S）}，計(jì)算S（Red（S）∪{b}，A）。由定義6 可知，S（{a1，a2}，A）=S（{a2，a4}，A）=1，S（{a2，a3}，A）=4/5，此時(shí)選擇a1（選擇a4也可以）并入Red（S）中，此時(shí)Red（S）={a1，a2}，轉(zhuǎn)步驟3；

（5）由于S（{a1，a2}，A）=1，算法結(jié)束，此時(shí)的約簡(jiǎn)即為{a1，a2}。

同樣地，若在第（4）選擇將a4并入Red（S）中，也可得到{a2，a4}也為該信息系統(tǒng)的約簡(jiǎn)。所以，該信息系統(tǒng)的約簡(jiǎn)為{a1，a2}、{a2，a4}，這與文獻(xiàn)[3]的結(jié)果是一致的，從而驗(yàn)證的本算法的有效性。另外，本文每次在屬性集A 的必要屬性集中添加與A 屬性貼近度最大的屬性加入約簡(jiǎn)集中，降低了數(shù)據(jù)處理工作量。

6 結(jié)論

本文在考慮等價(jià)類相似的基礎(chǔ)上，提出了用于度量屬性集之間相似性的屬性貼近度概念，進(jìn)而提出了基于屬性貼近度的屬性約簡(jiǎn)改進(jìn)算法，并通過實(shí)例分析驗(yàn)證了該方法的可行性，為屬性約簡(jiǎn)提供了一種新的研究思路。