模糊数据挖掘_严小卫

文章编号:1000-1220(2001)04-0504-03 收稿日期:2000-03-01　基金项目:广西“十百千人才工程”专项资金和广西自然科学基金(0007008)资助　作者简介:严小卫,教授,主要研究领域为数据库技术.蒋运承,硕士,主要研究领域为人工智能.模糊数据挖掘严小卫　蒋运承(广西师范大学计算机科学系　广西桂林541004)摘　要:本文在数据库中知识发现(KDD )和数据挖掘(DM )技术的基础上,提出了模糊数据库中知识发现(K D FD )和模糊数据挖掘(FDM )的概念与技术,并给出FDM 的算法,它能有效地挖掘出模糊数据库中潜在的有价值的知识.本文具体讨论了模糊关联规则及模糊数据依赖的挖掘.关键词:数据挖掘;数据库中知识发现;模糊数据处理分类号:T P 391 文献标识码:A1　引　言随着数据库技术的不断发展及数据库管理系统的广泛应用,数据库中存储的数据量急剧增加.但目前数据库系统中数据的开发应用主要是在于数据的检索和查询.而蕴藏在数据库中丰富的、有价值的信息远远没有得到充分的挖掘和利用,为了提取这些隐含的、事先未知的、潜在有用的信息,以满足人们实际工作中的需要,数据库中的知识发现即K DD (Know ledg e Discov ery in Data base )技术逐渐发展起来.目前,模糊数据库的研究取得了很大进展,已逐步投入实际应用.如美国和日本已把模糊数据库用于能源决策、医疗会诊等许多领域,显示了其重要的实用价值.如何快速、方便、有效地查询和分析模糊数据库中大量的模糊数据以发现潜在的、有价值的和人们感兴趣的信息是模糊数据库应用中的一大难题.本文提出了K DFD (K no wledg e Discov ery in Fuzzy Da ta base )概念和技术,并给出了模糊数据挖掘FDM (Fuzzy Da ta M ining )的算法,它能有效地从模糊数据库中挖掘出有价值的、人们感兴趣的知识.2　相关的KDD 技术定义2.1给定一个事实(数据)集F,以及一个语言L,一个模式S 就是L 中的一个陈述,用来描述F 的一个子集F s 中的关系,并使得S 要易于对F s 中所有事实的简单枚举.我们对KD D 定义如下.定义 2.2K DD 是从大量数据中提取新颖的、有效的、可信的、并能被人们理解的模式的处理过程,这种处理过程是非平凡的过程.KDD 的核心是那些用来发现各种各样的模式或规则的算法.而在获取有用的知识的整个问题中,对模式或规则的推理仅仅只是一小部分.K DD 应该是一个多步骤的处理过程,在处理过程中可能会有很多次反复.大致来说,KD D 主要包括以下一些处理步骤.(1)数据准备;(2)数据挖掘DM ;(3)结果表达和知识评价.可见,DM 是K DD 中最重要的一个步骤.它主要是利用某些特定的知识发现算法,在一定的运算效率的限制内,从大量数据中发现出有关的知识.最常用的DM 技术有:规则归纳、人工神经网络、遗传算法、决策树、最近邻技术、可视化技术等等.本文采用规则归纳技术,即通过统计方法来归纳、提取有价值的If-the n 规则.规则归纳的技术在数据挖掘中被广泛使用,例如关联规则的挖掘等.DM 的目的就是要发现人们感兴趣的知识.而要提取人们感兴趣的知识,其主要任务就是找出数据中经常发生的模式,然后从这些模式中发现人们感兴趣的知识.从而DM 的任务可描述为下面两个步骤:(1)DM (p )={p ∈Q |p 在Q 中经常发生},其中Q 为模式集合,它描述了数据的某些性质.(2)在DM (p )中挖掘出人们感兴趣的知识.3　模糊数据库中的知识发现与KD D 类似,我们可以把模糊数据库中的知识发现即K DFD 定义为:从大量模糊数据中提取新颖的、有效的、带信度的、并能被人们所理解的模糊模式的处理过程.这种处理过程是非平凡的过程.其中模糊模式是指带可信度的模式.K DFD 也是一个多步骤的处理过程,主要包括以下步骤:(1)模糊数据准备.选择模糊数的表示方法,确定模糊数据的可信度及模糊模式的可信度的计算方法,检查数据的完整性,对丢失的数据可以利用统计方法进行填补.说明K DFD 过程的有关数据及必要的背景知识.(2)模糊数据挖掘FDM.选择模糊模式的发现方法,说明要发现哪一种知识及有关参数的选择,运用选定的知识发现算法,从数据中提出有价值的、用户感兴趣的、带信度的知　第22卷第4期 2001年4月小型微型计算机系统M IN I -M ICRO SY ST EM V o l.22No.4 Apr .2001 识.(3)结果表达和知识评价.根据用户的目的对发现的知识进行分析,并以用户能了解的方式呈现给用户.这期间也包括对知识的信度进行修正,以确保本次发现的知识的信度与以前发现的知识的信度不相抵触.下面,给出模糊数据的有关概念.定义3.1设X是一个模糊数据,用二元组X=(c,b)表示,其中c为X的内容,b为X中所有模糊词的量化词,且b ∈〔0,1〕.例如,X表示“很可能买苹果”,用二元组表示为:X=(买苹果,0.90).定义3.2设X=(c,b)是一个模糊数据,给定α∈〔0,1〕,如果b>α,则称X为α-发生,其中α由专家给定.定义3.3设模糊数据X=(c,b)为α-发生,则X为α-发生的可信度Belief(X)定义为: Belief(X)= b.定义 3.4设X1=(c1,b1),X2=(c2,b2),…,X n=(c n, b n)是n个模糊数据,给定(∈〔0,1〕,如果min{b1,b2,…, b n}>α,则称X1X2…X n为α-发生,其α-发生的可信度Be-lief(X1X2…X n)=min{b1,b2,…,b\-n}.其中α由专家给定.要从大量模糊数据中提取人们感兴趣的、带信度的知识,本质上就是要找出数据中经常α-发生的、带可信度的模糊模式,然后从这些模糊模式中发现人们感兴趣的、带信度的知识.也就是说,FDM分为两个步骤:(1)求F DM1(p1)={p1∈Q|p1在Q中经常α-发生,并且给p1确定了一个可信度}.其中Q为模糊模式的集合,它描述了模糊数据的某些模糊性质.(2)求FDM2(p)={p∈FDM1(p1)|p为从FDM1(p1)中提取的、人们感兴趣的、带信度的知识}.对于求FDM1(p),我们给出以下查找经常α-发生的模糊模式的算法F FF P(Find-f requent-fuzzy-pa tterns).算法FF FP:(假设模糊模式集合Q中定义了序<,即(Q,<)为有序集) (1)把Q中所有最小的模糊模式放入C中,即:C={p∈Q|不存在q∈Q使得q<p} (2)F= (3)W hile C≠ do (4)　Begin (5) 对每一个p∈C,判断p是否经常α-发生 (6) K={p∈C|p经常α-发生,且p带一个可信度} (7) F=F∪K (8) C={p∈Q|任意的q∈Q,对满足q<p的所有模糊模式都已计算,并且Prune(P,1)K} (9)　End (10)FDM1(p)=F (11)输出FDM1(p) (12)End其中函数Prune(P,1)表示从P中删去任意一个单位模式后所得到的所有模糊模式的集合.例如:设P=ABC,则Prune(P,1)={AB,AC,BC}.对于求FDM2(p),所谓令人感兴趣的知识要因人而异,不同的用户有不同的要求,如有的用户想挖掘模糊关联规则,有的用户想进行模糊聚类等等.很显然,由于要求不同,所采用的算法也不同.下面以模糊数据库中模糊关联规则及模糊数据的模糊依赖关系的挖掘为例来说明FDM算法的应用.4　模糊关联规则FAR的挖掘F A R(Fuzzy Asso ciatio n Rule)表示模糊数据库中一组对象之间某种模糊关联关系的规则,也就是指具有一定信度的关联关系的规则.例如“从一个模糊对象能以0.95的信度推出另一个模糊对象”就是一条F A R.设R={A,B,C,…,D}是一个模糊数据库模式,r是R 上的一个模糊关系,对于r中的每一个属性值都用定义 2.1的方法表示,精确数据也表示成模糊数的形式,如“买苹果”可表示为:(买苹果, 1.0).定义 4.1设W是R的子集,r是R中的一个模糊关系, W在r上α-发生的次数为K,则W在r上的α-支持被定义为:α-Suppo rt(W,r)=K/r的总元组数.定义 4.2对于r,给定一个最小的α-支持,设为α-min-sup,如果α-Suppo rt(W,r)>α-minsup,则称W在r中经常发生.下面,给出挖掘F A R的第一步,即找出R中经常α-发生的模糊模式的算法,我们称之为M FA R1算法.算法M F AR1: (1)C={{A}|A∈R} (2)F= (3)i=1 (4)While C≠ (5)　Begin (6) F’={X|X∈C且X经常α-发生,并对X置可信度} (7) F=F∪F’ (8) C={Y|Prune(P,1)F’,size(Y)=i+1,且满足:若对任意的W Y,size(W)=i,则W经常α-发生} (9) i=i+1 (10)　End (11)输出F (12)End其中函数size(X)表示计算模糊模式X的大小,如size(A)的值为1,size(ABD)的值为 3.下面再给出如何从F中挖掘出FA R的算法,即M F AR2算法.首先定义几个概念.定义4.3设X是模糊关系r中的一模糊模式,m为r的总元组数,τi为r中的元组,i=1,2,…,m.τi(X)表示模糊模式X在元组τi上的值,如果τi(X)α-发生的次数为k(k≤m),则模糊模式X的可信度定义为:Belief(X)=(Belief(τ1(X))+Belief(τ2(X))+…+Belief (τm(X)))/k.定义4.4模糊关系r中的模糊关联规则X→Y的可信度定义为:5054期 严小卫等:模糊数据挖掘 Belief(X→Y)=Belief(X∪Y).定义 4.5模糊关系r中的模糊关联规则X→Y的α-支持定义为:α-Suppo r t(X→Y)=α-Suppo r t(X∪Y).定义4.6模糊关系r中的模糊关联规则X→Y的置信度定义为:confidence(X→Y)=α-Suppo rt(X∪Y)/α-Suppo rt(X).定义4.7设X→Y是模糊关系r中的模糊关联规则,r中的最小置信度为minco nf,如果co nfidence(X→Y)>minco nf,则称模糊关系r中的模糊关联规则X→Y为有效规则,其信度C F(X→Y)定义为min{Belief(X→Y),confidence(X→Y)},简记为CF.算法M F A R2:设F={F1,F2,…,Fn}. (1)Set= (2)For i=1To n (3) 取L Fi且L≠ (4) 如果(Fi-L→L)有效,则确定关联规则(Fi-L→L)的信度CF,且Set=Set∪(Fi-L→L,CF) (5) 判断满足L F i的非空L是否计算完.若没有,则 (6) 取L’F i,L’≠ 且L≠L’ (7) L=L’,GO TO(4) (8)Next i (9)输出带信度C F的模糊关系集合Set (10)End现在,用户可以从集合Se t中选取自己感兴趣的模糊关联规则.下面举例说明.设某模糊事务数据库中有如下一个模糊关系r:A B C D(a,0.90)(b,0.80)(c,0.85)(d,0.40)(a,0.83)(b,0.77)(c,0.73)(d,0.75)(a,0.47)(b,0.93)(c,0.80)(d,0.88)(a,0.72)(b,0.98)(c,0.92)(d,0.33)取α=0.70,α-minsup=0.70,minco nf=0.90,则经常α-发生的模糊模式有:{A},{B},{C},{AB},{A C},{BC},{A BC}.有效的模糊关联规则有:　A→C　CF=0.77,　B→C　CF=0.81,　B→A　CF=0.73,　A→BC CF=0.75,AC→B CF=0.72,AB→C CF=0.72.用户可以从中提取自己感兴趣的关联规则.5　模糊数据依赖FDD的挖掘FDD(Fuzzy data Dependency)是模糊数据库理论中的一个重要概念,但要找出模糊关系中所有模糊数据的依赖关系是一件较困难的事.利用算法M F AR1,我们可以容易地找出模糊事务关系中所有的模糊数据的依赖关系.主要思想为:首先,利用算法M FA R1找出模糊关系中经常发生的模糊模式的集合F;然后,通过下面的结论4.1找出所有FDD.结论5.1对任意的u,v∈F,如果u∈Pr une(v,1),则u 模糊依赖于v-u.模糊数据库中查找关键字集是查找FDD的特殊情况.目前,已给出的查找关键字集的各种算法都非常复杂,人们一般利用抽样(sample)技术来查找关键字集,但这样找出的关键字集不一定正确.我们利用与上述查找F DD相类似的思想来改进抽样查找方法,使得找出的关键字集更加符合实际.其具体过程如下: (1)对关系r进行抽样,得到一个关系s (2)找出关系s的关键字集keys (3)K=keys (4)判断是否存在X∈K,使得X不是r的一个关键字 (5)如果不存在,则Goto(10);否则 (6)增加元组u、v给关系s,其中u∈r,v∈r且u(X)=εv(X) (7)找出关系s的关键字集keys (8)K=keys (9)Goto(4) (10)输出keys (11)End其中"=ε"表示模糊数据库中的近似相等.6　结论随着模糊数据库管理系统的应用,人们在模糊数据库中积累了大量的模糊数据,如何从这些数据中挖掘出潜在的、有价值的知识是模糊数据库研究中的重大课题之一.本文提出了KD FD的定义和有关技术,给出了F DM算法,它能有效地挖掘出模糊数据库中潜在的、有价值的知识,并具体讨论了模糊数据库中模糊关联规则和模糊数据依赖关系的挖掘.但是,模糊数据毕竟是一个复杂的对象,至于K DFD的一些其它理论,如查询语言及各种算法的优化等研究工作有待进一步探索.参　考　文　献1V.Dh ar and A.Taz hilin.Abs tract-d riv en pattern discov ery in database.〔J〕IEE E Transactions on know ledge and Data Engi-neering,December19935(6):926～9382U.Fayyad,G.Piatets ky-Shapiro and P.Smyth.From d ata min-ing to k nowledge dicov ery in database.〔J〕AI M agaz ine1996.17(3):37～543R.Ag raw al,H.M annila,R.Srikant,H.Toivonen and A.I.Verkamo.Fas t discovery and data mining.〔M〕AAAI Pres s, M enlo Park,CA,1996:307～3284Kan,Hu.Res earch summary over data mining bas ed on larg e da-ta store.〔J〕J ou rnal of Softw are.1998.9(1):53～62FUZZY DATA MININ GY AN　Xiao-w ei　JI AN G　Y un-cheng(Depar tment of Compu ter Science,Guang xi Normal Un iversity　Guang xi Gu ilin541004,China)Abstract　Based o n th e techniques of KDD and DM,we present the co ncepts a nd tech niques o f KD FD and FDM.W e also giv e an alg o rith m ca lled FDM,which can be used to mine effec tiv ely the latent and v aluable kno wledg e in fuzzy database.At last, w e discuss th e fuzzy associa tio n r ule mining and fuzzy da ta dependency mining.Key words　Da ta mining;Know ledg e discov er y in da tabase;Fuzzy data pro cessing506 小　型　微　型　计　算　机　系　统 2001年。