文档介绍：哈希快速属性约简算法
刘勇 熊蓉 褚健
(浙江大学工业控制国家重点实验室杭州310027)
(浙江大学智能系统与控制研究所杭州310027)
摘要从决策系统的不一致情况出发，给出了不一致度的概念及其性质，并证明了不一 致记录与正区域于理解，而且能够很容易地计算出核与所有约简。但这个算法也存在着不足之 处，即，由于在矩阵中会出现大量的重复元素(或元素之间存在着包含关系)，这就大大降 低了属性约简算法的效率。通常此类算法的复杂度
为。(1。|2|1/|2),其中|C|为属性个数， u|为数据纪录数。
上述约简方法中差别矩阵方法计算过程需耗费巨大的时间和空间，故不常采用。其它方 法中都需要频繁计算决策表的正区域，因而计算正区域的时间复杂度直接决定了约简算法的 时间复杂度。
通常采用的正区域计算方法时间复杂度为。(ICIIUF),文献［14］中基于快速排序思想 给出了一种快速求解正区域算法，其时间复杂度可降为。(I CIIU I log(l U I))。在此基础上 文献［15］中类似的提出了一种基数排序的计算正区域算法，其时间复杂度下降至 O(ICIIt/l)o在本文的属性约简算法中，提出了一种基于哈希表的正区域计算方法，能够 将时间复杂度降为。(IUI) o在对采用正区域作为启发式搜索条件的约简算法进行充分分析 后，给出了一个适用于哈希方法计算的属性重要性度量参数，并基于此参数设计了一个完备 二次哈希属性约简算法，将时间复杂度下降到O(\C\2\U/C\),并通过实验和分析证明本 文算法的高效性。
本文第2节介绍相关的基本概念及不一致的定义和性质，证明了不一致记录数与正区域 间的等价性；第3节中介绍了基于哈希表的快速正区域计算方法，并且给出其时间复杂度分 析；第4节提出了一个建立在不一致性质上的二次哈希快速属性约简算法，并通过实例予以 说明；第5节通过实验证明本文算法的高效性；最后给出结论和展望。
2不一致的定义及其性质
属性约简凹过程实际上是寻找一个属性子集，使该子集能够保有与原条件属性集合相 同的记录辨识能力。因而其本质上是通过分类能力来衡量属性子集是否构成一个约简。正区 域的定义恰好描述一个属性了集能够辨别区分的记录数。
从条件属性集区分纪录的能力考虑，给出如下定义：
定义1不一致信息系统［/ (C, 中，C为条件属性集，。为决策属性集，PjC, xvx2 e U ,若 Va e P,a(xJ = a(x2)且有3d e £),(/(%；) ^d(x2),则称此时也与 x2之间在 属性P上存在不一致情况，若P = C,此时的U也称为不一致信息系统。
定义2不一致记录数/不一致记录信息系统 信息系统［/ (C,中，C为条件属性集, 。为决策属性集，U'gU ,若有 PgC，E^U'/P, i = 1,2,3,...,\U'/P \,记属性集 P
的在上不一致记录数为INU'(P)(通常U =U'时，可简写为计算如下：
INU'(P) = £l旦I, Ek是在属性P上存在不一致情况的等价类，
我们将U中所有在P上的不一致记录构成的信息系统称为相对属性P的不一致记录信 息系统，记为0。即有
Ip={ UX, \XieU/P, IX./Dl^l},若 P =(/),IP=U =
这里显然有
\lp 1= IN(P) = IN，P (P)o
在给出了不一致情况的相关定义后，可得如下几个性质：
性质1信息系统V (C, D)中，。为条件属性集，。为决策属性集，VQcC,信息 系统U(Q, D)是一致的(consistent)当且仅当/N(Q) = 0。
证明：若信息系统U(Q, D)是一致的(consistent)则显然有/N(Q) = 0 ,反过来若 7N(Q) = 0 ,根据不一致记录数的定义，表明信息系统中无不一致情况，即信息系统是一致 的。
性质2信息系统U (C, D)中，C为条件属性集，D为决策属性集，VP uC ,
I POSp(D) l=l POSc(D) I 当且仅当 IN(P) = IN(C)=
证明：根据定义有P0Sp(D)= U £X,也就是在信息系统"(C,方中有
PX ={Ei\Ei^U/P&E^X^X^U/D}
这里 i = l,2,3,...,\U/P\,j=l,2,..,\U/D\
山 EgXj 可 得 对 任 意 的 xm,xn e Et 有，Pa e P,a(Xm)= a(xQ ,且 Vrf e D,d(xJ = d(xn),对于E^PX的等价类则表明E中存在不一致情况，故U/P中的 等价类可以分为两种，一种是属于£X,另外一种是不属£X存在不一致情况的等价类。故 有
card{ U £X)=IUI-/N(P)
XeU/D 即
\POSP(