不完备不一致决策系统的最大分布约简及计算方法

不完备不一致决策系统的最大分布约简及计算方法蒙祖强;许珂;周石泉【摘要】Ininconsistentincompletedecisionsystems(IIDSs),sometoleranceclassesintolerancepartitionoverlapmorethanonedecisionclass,soastoproducecomplexoverlappingsubsetsbetweentolerancepartitionanddecisionpartition.ThisleadstooccurrenceofmanyconceptsofreductionsinIIDSsandmakesthereductionproblemmorecomplex.Therefore,theconceptofmaximumdistributionreductisextendedtoIIDSsinthispaper,then,someofitspropertiesinIIDSsareanalyzed.Itisfoundthat,unlikeotherreducts'coreattributes,themaximumdistributionreduct'scoreattributedoesnothaveinheritabletrait.Thisshowsthatthemaximumdistributionreductcannotbegeneratedbyaddingattributestocoreattributeset.But,byusingthetestinganddeletingoperationsrepeatedly,analgorithmforcomputingthemaximumdistributionreductinIIDSsissuccessfullyconstructedinthispaper.Thealgorithm'sdescriptionanditscomplexityanalysisarealsogiven.Finally,theproposedalgorithmisillustratedtobeeffectiveandbeofpracticalsignificancethroughsampleanalysis.%不完备不一致决策系统中，条件属性下的相容划分与决策属性下的等价划分形成了复杂的交集,导致出现了多种不同的约简概念,从而使约简问题变得更加复杂.本文将最大分布约简的概念引入不完备不一致决策系统中,然后研究其在不完备不一致决策系统中的性质,发现其核属性不具备传统约简核属性通常所具备的继承特性,因而不能通过增加属性的方法来计算此类约简.但是通过不断的属性测试和删除操作,成功地构造了不完备不一致决策系统中计算最大分布约简的算法,并给出了算法的描述和复杂度分析.通过实例分析,本文算法是有效的且具有实际意义.期刊名称】《广西师范大学学报(自然科学版)》年(卷),期】2011(029)003【总页数】5页(P89-93)【关键词】决策系统;不一致性;不完备性;最大分布约简【作者】蒙祖强;许珂;周石泉【作者单位】广西大学计算机与电子信息学院,广西南宁530004;广西大学计算机与电子信息学院,广西南宁530004;广西大学计算机与电子信息学院,广西南宁530004【正文语种】中文【中图分类】TP18随着计算机技术和网络技术的发展，数据的来源更趋广泛，数据呈现形式更加复杂化和多样化。这些数据可能是包含空值、丢失值或不一致的数据样本等。根据是否存在丢失值［1-2］以及是否一致，决策系统可分为4类：完备一致决策系统、完备不一致决策系统、不完备一致决策系统和不完备不一致决策系统(IIDSs,incompleteinconsistentdecisionsystems)。目前，属性约简的研究主要集中在完备一致决策系统上，在约简算法效率等方面已取得较为完美的成果［3-4］；针对不完备一致决策系统，也已有相对成熟的研究［5］；对于完备不一致决策系统，由于条件属性下的等价划分对决策类形成了交集，出现了多种不同的约简概念［6］，张文修等学者［7-8］对此进行了深入的研究，给出基于分辨矩阵的各种约简的计算方法。在实际应用中，由于数据获取途径等方面的原因，不完备不一致决策系统广泛存在［2］。在此类系统中，由于数据的不完备性和不一致性交织在一起，使得约简问题变得更加复杂化。目前，仍然缺乏对不完备不一致决策系统中有关约简问题的充分研究。为此，本文将在文献［5,7］研究的基础上，将最大分布约简的概念拓展到不完备不一致决策系统中，并给出该约简的计算方法。不完备不一致决策系统—个信息系统通常表示为四元组：IS=(U,A,V,f)，其中：U为对象集，表示论域；A为属性集；为属性a的值域；f:UxA-V称为信息系统S的一个信息函数。显然，对vaEA,xeU,有f(x,a)wVa。如果存在x0EU,aeA,使得f(xO,a)的值为一个丢失值，则此信息系统称为不完备信息系统，否则称为完备信息系统。丢失值通常用星号“*”来表示。如果V和f是已知的,(UAV,f)也可以简写为(U,A)。对任意BeA，子集B决定一个二元关系，表示为TR(B)。该关系定义如下［9］:TR(B)={(x,y)|f(x,a)=f(y/a)orf(x,a)=*orf(y,a)=*,vawB,x,ywU}。易证，TR(B)是自反和对称的，因此是相容关系。令SB(x)={y|(x,y)ETR(B)/yeU}o不完备决策系统是一种特殊的不完备信息系统，可以表示为一个四元组(U,CUD,V,f),*wVC,其中U的意义同上，C"D二,C和D分别称为条件属性集和决策属性集，四元组(U,CUD,V,f)可简写为(U,CUD)。不失一般性，令D={d},即D仅由一个决策属性构成。令P(Vd)表示Vd的幕集，Vd表示属性dED的值域，定义函数dB:U-P(Vd),BcC:dB(x)={f(y,d)|ySB(x)}o如果对任意xeU,均有|dC(x)|=1,则称不完备决策系统是一致的，否则称是不一致的［9］;相应决策系统分别称为不完备一致决策系统和不完备不一致决策系统。例1考虑不完备决策系统(U,CU{d}),如表1所示，其中U二{1,2,...,6},C二{P,M,S,X}二{Price,Mileage,Size,Max-Speed},d表示Acceleration。表1不完备不一致决策系统Tab.1AnincompleteinconsistentdecisionsystemCarPMSXd1highhighfullLowgood2low*fullLowgood3**compacthighpoor4low*fullhighgood5**fullhighexcel6lowhighfull*good表2SC(x)和dC(x)的值Tab.2ValuesofSC(x)anddC(x)xSC(x)dC(x)1{1}{good}2{2,6}{good}3{3}{poor}4{4,5,6}{good,excel}5{4,5,6}{good,excel}6{2,4,5,6}{good,excel}计算SC(x)和dC(x),结果如表2所示。从表2中，我们发现|dC(4)|=|dC⑸|=|dC(6)|=2>1,因此该决策系统是一个不完备不一致决策系统。IIDS中最大分布约简的概念文献［7］在完备不一致决策系统中引入了最大分布约简的概念，并给出了基于分辨矩阵的约简计算方法。本文将此概念引入不完备不一致的决策系统中，然后讨论它的计算方法。为表述方便，下文约定：对于IIDS=(U,CU{d}),Vd二{v1,v2,...,vr},Xvi二{xwU|f(x,d)二vi}。显然,U/{d}二{Xv1,Xv2,...,Xvr}。定义1令则BeC称为IIDS的一个最大分布约简，当且仅当对任意x^U有YB(x)=yC(x),且对任意B'uB总存在x0EU使得yB'(xO)HyC(xO)。例2考虑例1中的IIDS=(U,CU{d}),如表1所示。易观察到，U/{d}={Xgood,Xpoor,Xexcel}，其中Xgood二{1,2,4,6},Xpoor二{3},Xexcel二{5}。利用表2中有关SC(x)的值，可以计算所有的YC(x):YC(1)=yC(2)=yC(3)=yC(4)=yC5)=YC(6)={Xgood}。由此可以验证，⑸是该IIDS的最大分布约简。完备不一致决策系统中基于分辨矩阵的属性约简方法不适合于不完备不一致决策系统。为此，下面进一步讨论不完备不一致决策系统中最大分布约简的计算方法，给出非分辨矩阵的约简算法。IIDS中最大分布约简的计算方法定义2令IIDS(B)=(U,BU{d})表示这样的不完备不一致决策系统：该系统中的属性集B是从C中删除若干属性而形成的，其中C是原决策系统(U,CU{d})中的条件属性集。显然，BeC。为讨论方便，用IIDS(C)表示原系统(U,CU{d}),即IIDS(C)=(U,CU{d})。定义3对于IIDS(B)=(U,BU{d}),awB,a称为IIDS(B)的一个最大分布核属性，如果存在X0EU,使得YB-{a}(xO)HYB(xO),否则称为最大分布冗余属性。所有最大分布核属性的集合称为最大分布核属性集，记为MDCore(B)，即MDCore(B)={aeB|3xOeU,使得YB-{a}(xO)HYB(xO)}。与传统核属性不同，最大分布核属性不具有继承性，即MDCore(B)eMDCore(B-{b})不一定成立，其中b是IIDS(B)的一个最大分布冗余属性。MDCore(B-{b})不能从MDCore(B)中继承其核属性。例3考虑不完备不一致决策系统IIDS=(U,CU{d}),如表3所示，其中U二{1,2,...,6},C二{P,M,S,X}二{Price,Mileage,Size,Max-Speed},{d}二{Acceleration}。显然，U/{d}二{{126},{3,4,5}}={X1,X2}。分别令B'={P,M,S,X},{M,S,X},{PSX},{S,X},对所有xeU计算各yB'(x)的值。根据yB'(x)的值可以看到，YB-{P}⑸HYB(5),故PwMDCore(B)。类似地可以验证PMDCore(B-{M}),M是IIDS(B)的一个最大分布冗余属性。这说明，MDCore(B)eMDCore(B-{M})不成立。这就说明了最大分布核属性不具有继承性。由于最大分布核属性不具有继承性，因此不能像传统方法那样，通过使用启发式方法来求出核属性集，然后依次增加感兴趣的属性到核属性集中，直到形成约简。幸运的是，我们可以通过删除属性的方法来完成约简任务。即是说，可以不断地删除C中的属性，直到留在C中的属性均为当前最大分布核属性为止，结果剩下的属性便构成了最大分布约简。基于以上考虑，我们设计了计算最大分布约简算法，描述如下：表3不完备不一致决策系统Tab.3IncompleteinconsistentdecisionsystemCarPMSXdlhighmiddle*Iowgood2**full*good3middlelownoncompacthighexcel4**fullhigherexcel5lowmiddlenoncompact*excel6*highcompactmiddlegood输入:IIDS(C)=(U,CU{d}),其中C二{a1,a2,...,an}。输出:最大分布约简reduct。根据用户的感兴趣程度对C中的属性进行升序排列，假设结果为S=〈aj1,aj2,.,ajn〉;令B=C,对所有xeU计算SB(x)，进而计算yB(x)；令i=1；While(YB-{S[i]}(x)HYB(x)foronexeUandi<|S|)doi=i+1;//S[i]表示S中第i个元素Ifi<|S|then{令B=B-{S[i]},S=S-{S[i]};转③；}令reduct二B，返回reduct。不难看出，对任意BeC,如果对所有xeU均有yB(x)=yC(x),则B必定包含至少一个最大分布约简。步骤④〜⑥可保证：对所有xwU有yB(x)=yC(x)，且当对所有xeU均有YB-{a}(x)=YB(x)时，属性a被从B中删除，这样仍然保持yB-{a}(x)=YC(x)。因此，算法结束后可保证对所有xeU均有yreduct(x)二yC(x),且对任意B'ureduct，总存在xOeU,使得yB'(xO)hyC(xO)。所以reduct必为一^个最大分布约简。算法中有一个嵌套循环，外循环是步骤③〜⑦，内循环是步骤④。外循环次数不超过|S|=|C|次，即最高是|C|次，最低是1次，内循环次数也不超过|C|次。在内循环中对所有XEU计算YB-{S[i]}(x)是整个算法中最耗时的操作°YB-{S[i]}(x)的计算需要利用SB(x)和U/{d}来完成。当SB(x)和U/{d}已知时，对所有xeU计算yB-{S[i]}(x)的复杂度为O(|U||U/{d}|)=O(|U|)，因为|U/{d}|是常数。这样，在内循环中实际计算最耗时的操作是计算SB(x)，其复杂度在O(|B||U|)至0(|B||U|log|U|)之间⑸。因此，上述算法复杂度的最好情况为O(|C|(|U|+|U|))=O(|C||U|)，最坏情况为O(|C|2(|U|log|U|+|U|))=O(|C|2|U|log|U|)。对不一致决策系统来说，这是相对理想的知识约简算法。实例分析考虑例1中的不一致不完备决策系统IIDS=(U,CU{d}),假设用户感兴趣的升序序列为〈X,S,M,P〉，显然U/{d}二{{124,6},{3},{5}}={X1,X2,X3}。按上述算法，计算最大分布约简的步骤如下：S=〈X,S,M,P〉;令B=C={P,M,S,X},则yB(1)={X1},yB(2)={X1},yB(3)={X2},yB(4)={X1},yB(5)={X1},yB(6)={X1};令i=1，YB-{S[i]}(1)=yB-{X}(1)=y{P,M,S}(1)={X1,X3}/{X1}=yB(1),因此yB-{S[i]}(x)HYB(x)成立，这时,i=1<4=|S|,故i=i+1=2;YB-{S[i]}(3)=yB-{S}(3)=y{P,M,X}(3)={X1}/{X3}=yB(3),故YB-{S[i]}(x)HYB(x)成立，这时i=2<4=|S|,故i=i+1=3;当i=3时,可发现对所有xeU,有YB-{S[i]}(x)二yB-{M}(x)二yB(x),这时在步骤④中退出循环;由于i=3v|S|,letB-{S[i]}=B-{M}={P,S,X},S=S-{S[i]}=S-{M}=〈X,S,P〉，转到步骤③,i变为1；YB-{S[i]}(x)二yB-{X}(x)hyB(x)且i=1<3=|S|,故i二i+1=2；YB-{S[i]}(x)二yB-⑸(x)hyB(x)且i=2v|S|,故i=i+1=3;当i=3时,YB-{S[i]}(x)二yB-{P}(x)二yB(x)，且i=3=|S|,故退出循环；B=B-{S[i]}=B=B-{P}={S,X},S=S-{P}=〈X,S〉，转步骤③,i变为1；YB-{S[i]}(x)=YB-{X}(x)=YB(x),i=1v2=|S|,故退出循环；B=B-{S[i]}=B=B-{X}={S},S=S-{X}=⑸，转步骤③,i变为1；YB-{S[i]}(x)=YB-{S}(x)hyB(x)」=1=|S|,因此i=i+1=2,这时i>|S|,转步骤⑧返回reduect={S}。故{S}为该IIDS的最大分布约简。通过定义也可以验证这一点，因此本文提出的算法是有效的。为了说明本文提出的最大分布约简算法的实际意义，我们使用表4所示的数据集进行实验。该数据集是描述有关汽车在其生命周期中行驶总里程与汽车相关配置属性的关系。其中，出于某些原因，有些配置属性值在登记、采集时被漏掉了或者是根本无法获得这些信息(表4中用*表示)。我们的任务是根据手头现有的这些“低质量”数据，从中找出哪些配置属性对汽车的行驶总里程有影响作用。表4有关汽车配置信息的不完备不一致决策系统Tab.4Incompleteinconsistentdecisionsystemaboutcar'sconfigurationinformationsizecylturbofuelsysdisplacecomppowertransweightmileagecompact6yEFImediumhighhigh*mediummedium*6nEFI*mediumhighmanualmediummedium***EFI*highhighmanualmediummedium***EFI*highhigh**highcompact**EFImediummediummedium**mediumcompact**2-BBLmediummediummedium**lowcompact*nEFImedium*high**lowcompact*n2-BBLsmall*lowmanual*highcompact4n2-BBL**lowmanual*mediumcompact4n***mediumauto*mediumcompact4n****manual*high*4*******high*4*******medium*4*EFIn****manual*high*4*****BBL***manualmediumhigh***EFI*medium*manualmediummedium***EFI*medium**mediummedium***EFI*medium***medium**nEFI*high***high**n*smallhigh*manual*highcompact4n*smallhighmediummanualmediummedium显然，针对这个问题，传统的约简方法是难以胜任的，因为由这些数据构成的决策系统不但不完备，而且不一致。如果通过删除包含丢失值的数据记录和删除引起不一致的数据记录来进行完备化和一致化，这会导致大量数据的丢失(例如，表4中的数据将全部被删除)。但本文提出的算法则可以较好地处理这些数据。利用本文提出的算法，结果得到的约简是｛cyl,fuelsys,displace,comp,trans,mileage｝，即这些属性对汽车的行驶总里程起着决定性作用。这样，厂家可以在一定程度上通过优化这些属性的配置来提高汽车的行驶总里程。这说明，与传统的约简算法相比，本文提出的算法对处理这类在工程实践中经常遇到的“低质量”数据有现实意义。5结语不完备不一致决策系统在当今复杂数据环境下具有很强的数据建模和表示能力，因而具有较好的实用价值。但目前仍然缺乏针对不完备不一致决策系统中属性约简的充分研究。本文在相关研究成果的基础上，在不完备不一致决策系统中引入了最大分布约简的概念，讨论该约简的相关性质，并给出了计算最大分布约简的算法，分析了其复杂度，最后通过实验证实了本文算法的有效性和相对高效性。本文的工作为不完备不一致决策系统的约简问题提供了一种有效的解决思路。参考文献