基于粗糙集理论的数据挖掘模型

CN1122223󰃗N.39,No.1JTsinghuaUniv(Sci&Tech),1999,Vol29󰃗33

110～113

基于粗糙集理论的数据挖掘模型3

李永敏,　朱善君,　陈湘晖,　张岱崎,　韩曾晋

清华大学自动化系,北京100084文　摘　提出了一种基于粗糙集理论的数据挖掘模型,以利于信息不完备情况下的推理和决策问题的解决和研究。该模型从已知数据的初始决策系统出发,建立一系列的不同简化层次的子系统,然后推导出各个子系统的规则集,其中每条规则都有相应的置信度。在应用模型进行推理和决策分析时,用给定对象的信息与模型中相应节点的规则进行匹配,然后选用某种评判算法得出结论。给出了一个简单的例子来说明如何建立和应用这种数据挖掘模型。这样的模型可以很方便地根据给定的信息,在最符合的子系统上得出尽可能好的结论。

关键词　粗糙集;知识发现;数据挖掘;决策系统分类号　TP18

潜在价值的、以及最终的可理解的模式的非常规的过程。知识发现的过程包括数据准备、模式搜索、知识评估以及知识提炼等许多步骤,而这些步骤构成一个多重循环的过程。一般认为,数据挖掘是组成知识发现过程的一个环节,它是在某种可接受的约束条件下,应用数据分析和数据发现算法,从数据中获取某些特定模式的过程。

知识发现和数据挖掘的研究方法包括:分类、回归、聚类、归纳等等。但是,目前研究也碰到一些问题和挑战,如大数据量和维数灾难问题、过度匹配问题、数据及其结构的改变对知识发现的影响、如何有效地利用操作者的先验知识的问题等[2,3]。

知识发现和数据挖掘的研究融合了许多领域的研究成果,如模式识别、神经网络、机器学习、数据库、分类与聚类、最优化技术、高性能并行计算、知识建模、可视化等。

　　粗糙集理论的特点是不需要预先给定某些特征

或属性的数量描述,如统计学中的概率分布、模糊集理论中的隶属度或隶属函数等,而是直接从给定问题的描述集合出发,通过不可分辨关系和不可分辨类确定给定问题的近似域,从而找出该问题中的内在规律[1]。

近年来,粗糙集理论和应用的研究取得了很快发展,其涉及的领域很广,包括模式识别、机器学习、决策分析和决策支持、知识获取、知识发现等。粗糙集理论同模糊集、神经网络、证据理论等其它理论一起,成为不确定性计算的一个重要分支。

本文提出了一种基于粗糙集理论的数据挖掘模型,这种模型能够将问题定义为一系列不同简化层次上的子问题,从而在许多数据不完备的情况下也能够迅速地给出相对满意的输出。

2　粗糙集

粗糙集理论的出发点是,根据目前已有的对给定问题的知识将问题的论域进行划分,然后对划分后的每一个组成部分确定其对某一概念的支持程度:即肯定支持此概念、肯定不支持此概念和可能支持此概念。在粗糙集理论中,以上三种情况分别用三个近似集合来表示为正域、负域和边界。为描述方便,可以采用文[1]提出的知识表示系统和决策系统对问题进行描述,这样,粗糙集的方法和模型就可以建立在一种非常直观的二维表的基础上[4]。2.1　知识表示系统和决策系统

1　知识发现和数据挖掘

知识发现是指从数据中识别合法的、新颖的、有

　　收稿日期:1998205213

　　第一作者:男,1967年生,讲师

　3基金项目:国家自然科学基金项目,69784005

定义1　称S=(U,A,{Va},a)为知识表示系统,其中,U为非空有限集,称论域;A为非空有限集,称属性集合;Va为属性a∈A的值域;a:U→Va为一单射,使论域U中任一元素取属性a在Va中的某一唯一值。如果A由条件属性集合C和结论属

李永敏,等:　基于粗糙集理论的数据挖掘模型111

性集合D组成,C,D满足C∪D=A,C∩D=5,则称S为决策系统[5]。

为了表示简单,有时用(U,C∪{d})表示决策系统,即结论属性集合只包含一个元素。

定义2　对决策系统S=(U,C∪{d}),BΑC是条件属性集合的一个子集,称二元关系ind(B,{d})={(x,y)∈U×U:d(x)=d(y)或者Πa∈B,

a(x)=a(y)}为S的不可分辨关系,其中,x,y为U

这样,通过一组相对简约,可以得到决策系统S=(U,C∪{d})中最简单的规则集,其中,每个相对简约就是一条规则的前件。

3　基于粗糙集理论的数据挖掘模型

数据挖掘的目的在于从大量数据中发现那些令人感兴趣的规则,一般地讲,这些规则在表现形式上应比较简洁,并且具有一定程度的概括性。同时,在实际问题中,待处理的数据常有某种程度的不完备,这表现在知识表示系统或决策系统中即某些属性没有赋值。造成这种情况的原因可能有以下几种:1)有些信息无法获取;2)获取这些信息的代价较大;3)实时性能要求较高,即要求在得到这些信息之前就要迅速做出判断或决策。

如果能提供一种解决问题的模型,使在每种信息不完备的状况下都能尽可能给出问题的最大可能的解,则无疑是很有实际意义的。假设某决策系统有n个条件属性,则首先可计算出在所有条件属性完备情况下的一组规则;然后,去除某一个条件属性,根据剩下的n-1个属性计算出在这组不完备属性下的另一组规则……如此简化下去,得到系统在各种信息不完备情况下的规则集合。这样,应用这个模型进行推理或决策,在信息不完备情况下也能给出一个较好的输出。

本文提出的数据挖掘模型的思路是,给定目标规则的置信度Λ0,从样本数据出发,依据粗糙集理论,发现决策系统在不同简化层次上符合置信度要求的规则;应用得到的规则进行推理或决策,由于问题的信息不一定完备,所以根据已有的信息在模型上逐层匹配,再按照某种优先级判定算法,给出问题的最优解。3.1　模型建立

中的元素[5]。2.2　粗糙集

定义3　对于知识表示系统S=(U,A),设BΑA,XΑU,定义集合　XB={x∈U󰃜[x]ind(B)ΑX},XB={x∈U󰃜[x]ind(B)∩X≠5}分别为X的B下近似和B上近似。进一步,SPOSB(X)=XB,SNEGB(X)=U-XB,SBNB(X)=XB-XB分别称为X在B

下的正域、负域和边界[5]。

定义4　ΛB(x,X)=

card([x]B∩X)为元素x

card([x]B)

对集合X的粗糙隶属函数[5]。2.3　简约和核

在一个决策系统中,各个条件属性之间往往存在着某些程度上的依赖或关联,简约可以理解为在不丢失信息的前提下,可以最简单地表示决策系统的结论属性对条件属性的集合的依赖和关联。

定义5　对于一个给定的决策系统S=(U,C∪{d}),条件属性集合C的简约是C的一个非空子集C′,它满足

(1)ind(C′,{d})=ind(C,{d});(2)不存在C″C的所有简约的集合记作SRED(C)。C的所有

的简约的交集叫作核,记作Score(C),Score(C)=∩

[5]

SRED(C)。

定义6　对于决策系统S=(U,C∪{d}),不可分辨关系ind(C)将U划分为t个不可分辨类X1,

X2,…,Xt,令D(Xi)为Xi的所有结论属性d的取

值的集合,即D(Xi)={v=d(x):x∈Xi},如果D([Xi]ind(C-{a}))=D(Xi),条件属性a∈C称为相对于不可分辨类Xi可去除的。C′ΑC称为C相对于不可分辨类Xi的简约,如果Πa∈C′,a为相对于

X

i

模型建立的步骤如下:

1)数据准备。从原始数据出发,确定条件属性集合和结论属性集合,选择各属性的值域,并将原始数据中相应的数值进行转换,这样,得到一个符合上文所述的决策系统,记作(U,C∪{d})。

2)衍生节点。计算SRED(C,{d}),并以这些简约为基础建立模型的初始节点,将包含属性数相同的节点放置在模型的同一层;然后,依次从每个节点中去掉一个属性,得到该节点的后继节点,依此类推,直到空节点(不包含任何条件属性),如图1所示。用N

(q)i

不可去除。相对于Xi的所有简约的集合记作

SRED(C,Xi),Score(C,Xi)=∩SRED(C,Xi)称相对于Xi的核。

表示第q层的第i个节点,其对应的决策

(q)

系统为(U,Ci∪{d})。

112清华大学学报(自然科学版)

()

1999,39(1)

()

q

3)计算节点,获取规则集。设ind(Ci)将U划

节点N

(q)iq

(U󰃗ind(Ci)={X1,X2,…,Xt})如果存在

分称不可分辨类X1,X2,…,Xt,对每个Xj计算其相对简约,从而得到简化的一组规则;计算规则的

粗糙隶属函数Λ,取Λ>Λ0的规则,存入该节点的规则集中。

4)停止条件。如果一个节点的某个前向节点的规则的置信度均小于Λ0,停止计算。3.1.1　RED(C,{d})的计算

(q-1(q-(U󰃗一个前向节点Njind(Cj

…,X′})满足以下条件t′

)1)

)={X′1,X′2,

ΠX′,1≤l≤p,k,Dl,1≤k≤t′

Λ(X′k,Dl)<Λ0,

那么,

ΠXk,Dl,1≤k≤t,1≤l≤p,Λ(Xk,Dl)<Λ0.定理3说明了若一个节点的某一个前向节点产生的规则的置信度均小于Λ0,则该节点不可能产生置信度大于等于Λ0,因此,该节点不需计算。3.2　模型运行定义7　对于决策系统(U,C∪{d}),ind(C,

{d})将U={x1,x2,…,xn}划分为X1,X2,…,Xt,D(Xi)={v=d(x):x∈Xi}为Xi的所有结论值的集合。称(cij)n×n为S的分辨矩阵,即{a∈C:a(Xi)≠a(Xj)},D(Xi)≠D(Xj);cij=

5,其他

1≤i,　j≤t.

模型建立后,就可以利用此模型对新的数据进行推理和决策了。模型运行的步骤如下:

1)用要处理的数据具有的条件属性集合去匹配模型中的节点(如图1所示),如果有匹配节点,取匹配的第一个节点;

2)用匹配上的属性的值匹配该节点的规则集,若存在匹配规则,返回这些规则;否则,进到3);

3)取该节点的所有后继节点,对其中的每一个节点返回2)。

经以上步骤得到的结果可分为以下几种情况:1)只有一条规则返回;2)有多条规则返回;3)没有规则返回。

对于1),只需取该规则的输出即可;对于3),说明根据已有的知识无法给出问题的解。第2)种情况的处理较为复杂,一般用以下处理方法:

a)如果返回的规则中有两条规则分别属于两个相连的节点,则删除后继节点的规则;

b)以某种评判算法,选择优先级较高的规则。

关于优先级评判算法,可以选用取粗糙隶属函数作为评判函数或综合评判算法[6]。

设所有的规则共有d1,d2,…,dr个结论,其中得出di的规则为r1,r2,…,rm,定义di的评判函数为v(di)=

称f(S)=

i≤i,j≤n

∧∨cij为S的分辨函数,其中,∨cij表

示cij中所有属性的析取运算,∧表示合取运算。

定理1　对于决策系统(U,C∪{d}),f(S)为S的分辨函数,设f(S)经运算后化为析取范式f′

(S)=∨∧Σi,其中,Σi∈2C,∧Σi为f′(S),即f′

1≤i≤k(S)的一个合取子式,k为f′(S)中合取子式的个数,那么,SRED(A)={Σi:1≤i≤k}.

定理1给出了一种计算简约的方法,将分辨函数化为析取范式,则每个子式所包含的条件属性即构成一个简约。3.1.2　相对简约的计算

定义8　对于决策系统S=(U,C∪{d}),U={x1,x2,…,xn}经ind(C,{d})划分为不可分辨类

X1,X2,…,Xt,D(Xi)={v=d(x):x∈Xi},则f

(Xi,S)=∧∨cij称S相对于Xi的分辨函数,其

1≤i≤t

中,cij定义如前,1≤i,j≤t.

定理2　对于决策系统S=(U,C∪{d}),U={x1,x2,…,xn}经ind(C,{d})划分为不可分辨类

X1,X2,…,Xt,f(Xi,S)为S相对于Xi的分辨函

(Xi,S),数,设f(Xi,S)经运算后化为析取范式f′

(Xi,S)=∨∧Σj,其中,Σj∈2C,∧Σi为f′即f′

1≤j≤k(Xi,S)的一个合取子式,k为f′(Xi,S)中合取子式的个数,那么,SRED(Xi,C)={Σj:1≤j≤k},1≤i≤t.

3.1.3　终止条件

6

m

sj

j=1

6

m

(sj󰃗Λj).其中,sj为规则rj的

j=1

支持数,即支持rj的U中的元素的个数;Λj为粗糙

隶属函数。3.3　举　例

决策系统S=(U,C∪{e})如表1所示,其中条件属性值全相同的元素归并为一条记录,以索引号

I表示,其对应的元素样本个数用k表示。设规则的

定理3　在对决策系统S=(U,C∪{d})建立的上述模型中,设U󰃗ind({d})={D1D2,…,Dp},对于

置信度阈值为Λ0=018。

经计算得S的分辨矩阵,如表2所示。由分辨矩

李永敏,等:　基于粗糙集理论的数据挖掘模型113

阵得简约集SRED(C,{e})={{b,c,d},{a,b}},从这两个简约出发,衍生出如图1所示的一系列节点。

再经每个节点的决策系统的计算,将Λ>Λ0的规则记入与其前件相匹配节点的规则集中。限于篇幅,本文只列出节点Nbc上的规则集合,如表3所示。

表1　决策系统

I

k

a

b

c

d

e

念出发,通过将给定问题的数据的近似域的划分,找出这些数据中隐藏的关联和规律。这个特点使得粗糙集理论非常适用于知识发现和数据挖掘的应用。

本文提出的数据挖掘模型能够在不同的简化层次上给出相对满意的输出,由于其运行机制和人思考及判断的特征很相似,因此应用起来比较灵活。具体地说,该模型具有以下特点:

1)能够在给定数据不完备的情况下给出具有某种置信度的输出;

2)具有一定的容错能力,即在数据不一致的情况下,也能有比较满意的运行效果;

3)决策者的先验知识可以在模型建立时很方便地输入到系统中,即可以有选择地扩展某些节点和在某些节点上停止计算;

4)各节点的计算可以并行进行,这在系统规模较大时会很大程度地提高运行速度。

12345678

1560101053025405000111222012012011101100022122211100011002221表2　分辨矩阵

1123456782bcd

3bd

4abcab

5adabcd

6abcabdacdbcdb

7acabdabcdacdab

8abcdacdabcdabcdacdabcdbcd

然而,由于许多实际应用中的数据经常是不断更新的,如何动态地修正现有模型结构和规则集是本文尚未解决的问题,也正是下一步研究的重点。

参　考　文　献

1

PawlakZ,Grzymala2BusseJ,SlowinskiR,etal.Roughsets.CommunicationsoftheACM,1995,38(11):88～95

FayyadU,Piatetsky2ShapiroG,SmythP.TheKDDprocessforextractingusefulknowledgefromvolumesofdata.CommunicationsoftheACM,1996,39(11):27～34

FayyadU,HausslerD,StolorzP.Miningscientificdata.CommunicationsofACM,1996,39(11):51～57

BanerjeeM,ChakrabortyMK.Acategoryforroughsets.FoundationsofComputinganddecisionsciences,1993,18(324):167～180

PawlakZ.Roughsets,theoreticalaspectsofreasoningaboutdata.Dordrecht:KluwerAcademicPublishers,1991AasheimOT,SolheimHG.Roughsetsasaframeworkfordatamining.ProjectReport,NorwegianUniversityofScienceandTechnology,1996.See:ftp:󰃗󰃗ftp.ii.pw.edu.pl󰃗pub󰃗Reports

LubaT,RybnikJ.Algorithmicapproachtodiscernibilityfunctionwithrespecttoattributesandobjectsreduction.FoundationsofComputingandDecisionSciences,1993,18(324):241～258

ZiarkoW.Analysisofuncertaininformationintheframeworkofvariableprecisionroughsets.FoundationsofComputingandDecisionSciences,1993,18(324):381～396

2

表3　节点Nbc的规则集合

规则b=0,c=1→e=b=1,c=0→e=b=2,c=1→e=b=2,c=0→e=b=0,c=0→e=c=2→e=2样本数256510302545置信度1.000.921.001.001.000.893

01122

4

5

6

7

8

图1　模型中的节点连接关系示意图

4　结　论

粗糙集理论从不可分辨关系和不可分辨类的概

(下转第117页)

管志远,等:　环流气浮分离技术在含Cu(󰂫)废水处理中的应用

3LuoChien2Shu,HuangShang2Da.Removalofcopper

fromaqueousamminecopper(󰂫)solutionbyfoamflotation.SeparationScienceandTechnology,1993,28(7):1395～14084

SancioloP,HardingIH,MainwaringDE.removalofChromium,with

a

Sodium

Nickel,

The

andZincfrom

acid

117

possessesobviousadvantageovertheconventionalbubble

flotationcolumnintermsofthefinalremovalefficiencyandthereductioinrateofCu(󰂫)andcouldbewidelyusedinwastewatertreatment.

Keywords　gasflotation;loopflotationcolumn;waste

watertreatment;bivaleneecopperCu(󰂫)

electroplatingwastwaterbyadsorbingcolloidflotation

Dodecylsulfate󰃗Dodecanoic

mixture.SeparationScienceandTechnology,1992,27(3):375～388

5ChoiSang2June,IhmSK.RemovalofCu(󰂫)from

aqueoussolutionbythefoamseparationtechniquesofprecipitateandadsorbingclloidflotation.SeparationScienceandTechnology,1988,23(4,5):363～3746MatisKA,ZouboulisAI.Biosorptiveflotationinmetal

ions

recovery.

Separation

Science

and

Technology,1994,29(8):1095～1071

(上接第113页)

Dataminingmodelbasedon

roughsettheory

LIYongmin,ZHUShanjun,CHENXianghui,

ZHANGDaiqi,HANZengjin

DepartmentofAutomation,

TsinghuaUniversity,Beijing100084,China

ApplicationofloopflotationseparationapproachintreatmentofwastewatercontainingCu(󰂫)

GUANZhiyuan,DINGFuxin,YUANNaiju

DepartmentofChemicalEngineering,TsinghuaUniversity,Beijing100084,China

Abstract　TheexperimentalstudyontheremovalofCu(󰂫)fromaqueoussolutionbyadsorptionflotationtechniquesinloopflotationcolumnhasbeenconducted.Thiscolumnhasaverticaldrafttubeandaporousgassparger,whicharespeciallydesigned.Theeffectsofgasvelocity,pH,surfactantaddingrate,andtheconcentrationofFe(󰂬)ontheremovalefficiencywerestudiedandthesuitableoperatingconditionsweredetermined.Theexperimentalresultsindicatethattheloopflotationcolumn

Abstract　Onpurposeofimprovingthesolutionand

researchinreasoninganddecisionmakingproblemswhentheinformationinhandisnotsufficient,adataminingmodelbasedonroughsettheoryispresented.Fromtheinitialdecisionsystemdefinedbytheprimitivedata,aseriesofsub2systemswithvariousreductivelevelsarecreated.Foreachsub2system,therulesetswithrespectivebeliefdegreesareinducedandsaved.Whenapplyingthemodeltoreasoninganddecisionanalysis,onecanmatchtheinformationofthegivenobjecttotherulesetsofrelativenodes,andthendrawtheconclusionbyusingsomekindofevaluationalgorithm.Asimpleexampleonhowtocreateandapplythemodelisgiven.Thepresentedmodelcanbeappliedconvenientlybyselectingsuitablesub2systemsinaccordancewiththegiveninformationandcomputingthebestdecisionfromtherulesinthosesub2systems.Keywords　roughsets;knowledge

mining;decisionsystems

discovery;

data