信息系统中基于属性贴近度的属性约简算法研究

何建仓* 侯泽民

（郑州科技学院 信息工程学院，河南 郑州450064）

粗糙集理论[1-2]由Pawlak 于1982 年提出，是一种处理不精确、不完备等知识的数据分析方法，并被广泛应用于人工智能、知识发现等领域。作为粗糙集的核心内容，属性约简[3]是删除属性集中的冗余属性，得到不影响原有属性集分类能力的简化属性集。目前，针对属性约简，许多学者利用知识划分相似性[4-5]、强化正域[6]、粒度[7-8]、相似关系[9]、类间区分度[10]、区分矩阵[11]等方法提出了相应的属性约简改进算法，丰富了粗糙集的理论体系。本文在文献[4，5]的基础上，利用属性贴近度来刻画属性集之间的相似程度，并结合属性贴近度给出属性约简满足的条件，进而提出了基于属性贴近度的属性约简改进算法，进一步丰富了信息系统中不确定信息度量理论。

1 基本概念

定义1[3]设四元组S=（U，A，V，f）为一个信息系统，其中：

①U 为论域，且U={x1，x2，…，xn}（n 为论域U 中对象个数）；

②A 为属性集，且A={a1，a2，…，am}（m 为属性集A 中属性个数）；

③V 为所有属性的取值范围，即V=∪{Vai}（ai为属性集A中某个属性，1≤i≤m）；

④f：U×A→V，即对任意属性ai和对象x，均有f（x，a）∈Vai。

定义2[3]设U 为论域，P 是U 上的等价关系，[x]P={y|f（x，P）=f（y，P），x、y∈U}称为x 在信息系统中的P 等价类，U/P={[x]P|x∈U}为信息系统中P 针对U 的划分。

性质1[3]设S=（U，A，V，f）为一个信息系统，P、Q⊆A，对任意x∈U，则有：

（1）若P⊆Q，则有U/Q⊆U/P，且[x]Q⊆[x]P，此时称划分U/Q更精细，划分U/P 更粗糙。

（2）若P=Q，则有U/P=U/Q，且[x]P=[x]Q，此时称P、Q 划分能力相同。

定义3[3]设S=（U，A，V，f）为一个信息系统，P⊆A，对任意的属性a∈P，若U/P-{a}≠U/P，则称a 在P 中是必要的，否则称a在P 中是不必要的。

定义4[3]设S=（U，A，V，f） 为一个信息系统，P⊆A，若U/P=U/A，且对对任意的属性a∈P，均有U/P-{a}≠U/A，则称P为A 的一个约简。

2 属性贴近度

定义5 设S=（U，A，V，f）为一个信息系统，P、Q⊆A，P、Q 针对U 的划分分别为U/P={[xi]P|xi∈U}，U/Q={[xi]Q|xi∈U}，其中1≤i≤|U|。对于任意的xi∈U，[xi]P、[xi]Q之间的相似性定义为：

则称sim（[xi]P，[xi]Q）为等价类[xi]P、[xi]Q之间的贴近程度。由定义5 可知，sim（[xi]P，[xi]Q）度量的是等价类[xi]P、[xi]Q之间的贴近程度，其值越大，说明[xi]P、[xi]Q越贴近。

性质2 设S=（U，A，V，f）为一个信息系统，P、Q⊆A，对于任意的xi∈U，则有1/|U|≤sim（[xi]P，[xi]Q）≤1，且sim（[xi]P，[xi]Q）=sim（[xi]Q，[xi]P）。

证明：对于任意的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。另外，根据定义5，可得sim（[xi]P，[xi]Q）=sim（[xi]Q，[xi]P）。

定义6 设S=（U，A，V，f）为一个信息系统，P、Q⊆A，P、Q 针对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 针对U 的划分U/P、U/Q 之间的相似程度，其值越大，说明U/P、U/Q 越相似。

性质3 设S=（U，A，V，f）为一个信息系统，P、Q⊆A，则有1/|U|≤S（P，Q）≤1，且S（P，Q）=S（Q，P）。

另外，根据定义6，可得S（P，Q）=S（Q，P）。

定理1 设S=（U，A，V，f）为一个信息系统，P、Q⊆A，P、Q 针对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 设S=（U，A，V，f）为一个信息系统，P⊆Q⊆R⊆A，P、Q、R 针对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，则由性质1（1）可知，对任意的xi∈U，有[xi]R⊆[xi]Q⊆[xi]P。根据定义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 说明，对于P⊆Q，随着P 中属性的不断增加，P 越与Q 相似，P 针对U 的划分越与Q 针对U 的划分相似。

3 属性约简

定理3 设S=（U，A，V，f）为一个信息系统，P⊆A，对任意的属性a∈P 在P 中是必要的当且仅当S（P-{a}，A）≠S（P，A）。

证明：一方面，由定义3 可知，若a 在P 中是必要的，则有U/P-{a}≠U/P，则必存在xi∈U，使得[xi]P≠[xi]P-{a}，而由性质1（1）可知[xi]P-{a}⊆[xi]P，则知[xi]P-{a}⊆[xi]P，从而根据定理2 可知S（P-{a}，A）＜S（P，A），即S（P-{a}，A）≠S（P，A）。另一方面，若S（P-{a}，A）≠S（P，A），则必存在一个xi∈U，使得[xi]P≠[xi]P-{a}，U/P-{a}≠U/P，所以a 在P 中是必要的。

定理4 设S=（U，A，V，f）为一个信息系统，P⊆A，对任意的属性a∈P 在P 中是必要的且S（P，A）=1，则称P 为A 的一个约简。

证明：由定理1 可知，若S（P，A）=1，则有U/P=U/A。又知对于属性集P⊆A，其任意的属性a∈P 在P 中是必要的，即U/P-{a}≠U/P，根据定义4 可知，P 为A 的一个约简。

4 基于属性贴近度的属性约简改进算法

本算法将从属性集A 中选择其必要属性作为初始约简集，然后在此基础上逐渐添加属性来求解信息系统的属性约简。下面给出基于属性贴近度的属性约简改进算法。

输入：一个信息系统S=（U，A，V，f）。

输出：信息系统的约简Red（S）。

步骤1：令P=Ø。对任意属性a∈A，若S（A-{a}，A）＜1，令P=P∪{a}；

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

步骤3：若S（Red（S），A）=1，则跳转到步骤5，否则，执行步骤4；

步骤4：对任意的属性b∈A-Red（S）}，计算S（Red（S）∪{b}，A），并将使S（Red（S）∪{b}，A）值最大的属性并入Red（S）中，转步骤3。

步骤5：算法结束，输出约简Red（S）。

5 实例分析

下面以文献[3]中的信息系统为例，来验证本文算法的有效性，其中文献[3]得到的约简为{a1，a2}、{a2，a4}。

表1 信息系统

（1）令P=Ø。对任意属性a∈A，计算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）对任意的属性b∈A-Red（S）}，计算S（Red（S）∪{b}，A）。由定义6 可知，S（{a1，a2}，A）=S（{a2，a4}，A）=1，S（{a2，a3}，A）=4/5，此时选择a1（选择a4也可以）并入Red（S）中，此时Red（S）={a1，a2}，转步骤3；

（5）由于S（{a1，a2}，A）=1，算法结束，此时的约简即为{a1，a2}。

同样地，若在第（4）选择将a4并入Red（S）中，也可得到{a2，a4}也为该信息系统的约简。所以，该信息系统的约简为{a1，a2}、{a2，a4}，这与文献[3]的结果是一致的，从而验证的本算法的有效性。另外，本文每次在属性集A 的必要属性集中添加与A 属性贴近度最大的属性加入约简集中，降低了数据处理工作量。

6 结论

本文在考虑等价类相似的基础上，提出了用于度量属性集之间相似性的属性贴近度概念，进而提出了基于属性贴近度的属性约简改进算法，并通过实例分析验证了该方法的可行性，为属性约简提供了一种新的研究思路。