（计算机应用技术专业论文）遗传归纳逻辑程序设计技术研究.pdf

摘要 摘要 数据挖掘技术是当前计算机技术的研究热点之一。当前的数据挖掘研究主要在命题逻 辑的框架内，存在描述能力弱和不便于利用背景知识的局限性。而且，这些方法多采用了 单表假设，算法寻找单表数据中的模式。但数据通常保存在关系数据库的多张表中，若想 利用现有的数据挖掘算法，存在将数据转换到单表中的难题。 基于一阶逻辑的一阶规则挖掘技术常被称作归纳逻辑程序设计( i l p ) 。一阶逻辑为i l p 提供了一致的和非常有表达力的表示手段：背景知识、例子以及挖掘到的知识都可表示为 子句语言的公式，所以在挖掘过程中可非常自然地利用背景知识。另外得到的知识表示为 相关谓词构成的一阶规则，比命题规则具有更强的表达能力，使知识的内涵更加丰富并易 于人们理解。因此，i l p 可克服传统命题规则挖掘方法的两个主要限制：描述能力的限制 与背景知识利用的限制。此外，由于关系数据库的形式描述一“关系代数”与i l p 的子句 逻辑有着内在的关联性，i l p 技术可被直接用于涉及关系数据库中多个关系( 表) 的数据 挖掘任务。 一阶规则挖掘可看作是对一阶规则空间的搜索。由于一阶规则空间的庞大和复杂性， 为了实现有效的搜索，绝大多数一阶规则挖掘系统采用了贪婪的搜索策略，并需要对具体 问题给出极其严格的语言偏向( 即挖掘过程中待测规则构成的特征描述) 来缩小搜索的范 围或作为启发知识来指导搜索过程。贪婪的搜索策略可能使算法陷于局部优解，语言偏向 的添加也只对与其相适的目标规则的搜索有良好的效果，不适于数据挖掘这种目标规则构 成先验知识少的任务环境。 遗传算法是模拟生物进化机制而发展起来的随机化搜索算法。算法根据概率的变迁规 则来指导搜索方向，利用演化过程中获得和积累的有关搜索空间的信息自行组织搜索，并 自适应地控制搜索过程，基本上不用搜索空间的知识或其它的辅助信息，对问题本身没有 过多的要求，适于数据挖掘的任务环境。遗传算法采用群体搜索策略，具有较好的全局搜 索性能，减少了陷于局部优解的风险。因此，采用遗传算法作为i l p 的搜索策略，可从整 体上提高一阶规则挖掘方法的鲁棒性和适应性，解决一阶规则获取的性能瓶颈问题。 本论文主要开展了遗传归纳逻辑程序设计技术的初步研究。用遗传算法挖掘一阶规则 依赖于两个因素：遗传空间的“地貌”和在遗传空间中的“航行”。两者分别反映了算法 的静态和动态特性。遗传空间的“地貌”体现了算法的静态特性，它与以下三者相关：( 1 ) 把一阶规则表示成遗传算子可操作形式的编码。依据给定的编码，所有待搜索的一阶规则 被映射为遗传空间相应的点。( 2 ) 评判一阶规则优劣的适应度函数，一阶规则适应度的相 应变化形成了遗传空间高低起伏的地貌特征：( 3 ) 由交叉和变异算子决定的规则间的邻接 关系，描述了遗传空间地貌的沟壑或桥梁。在遗传空间的“航行”则体现了算法的动态特 性，是种群在选择，交叉以及变异算子的作用下逐渐逼近最优解的过程。本论文重点研究 了遗传归纳逻辑程序设计技术中的一阶规则编码，遗传算子的设计，选择策略及算法结构 北京工业大学工学博士学位论文 等关键技术。此外，我们还对自己提出的g i l p 算法运行中的个体编码生长现象进行了研 究，并在对一阶规则挖掘中的等价类问题的研究基础上，提出了基于信息赢取的适应度函 数。最后，基于研究成果，开发了g i l p 系统并进行了挖掘工作。主要研究成果和创新点 如下： ( 1 ) 在认识到一阶规则挖掘实质上是目标谓词和背景知识谓词构成的各种原子的组 合优化问题基础上，我们依据0 t e a m sr a z o r 原理，提出了符合最小字符集编码原则的一 阶规h u 位串编码。该编码仅需用户在付出的计算代价和获取知识复杂度( 规则中可能出现 的相异变量的序号上界) 之间作权衡，不需给出描述了待测规则构成特征的语言偏向，适 于数据挖掘这种目标规则构成先验知识少的任务环境。为我们提出的位串编码设计了符合 一阶规则语法约束的遗传算子。提出了基于覆盖删除策略的遗传归纳逻辑程序设计算法 g i l p 。 ：2 ) 通过对变长位串编码作模式分析，初步解释了g i l p 运行过程中的个体编码生长 现象。并发现，若简单地从初始种群开始，在适应度中添加长度惩罚项解决生长问题时， 种群会出现退化现象。为此，提出了基于演化周期的惩罚策略，既避免了种群退化，又有 效抑止了个体编码的生长。 ( 3 ) 用遗传算法有效地搜索一阶规则的关键在于如何准确地评价一阶规则，即规则 的适应度能有效地量化规则的优劣，指导算法逼近最优解。在i l p 技术通常采用的基于规 则覆盖正负例数目的评价标准中，存在一阶规则的等价类问题。等价类问题使g 1 l p 的遗 传搜索过程盲目地倾向于长规则，将严重地降低算法的搜索效率和规则的可读性。我们在 绑定概念的基础上，依据信息理论，提出了基于信息赢取的适应度函数。分析和对比实验 表明，折的适应度函数可区分一阶等价规则的优劣，更好地指导算法的搜索方向。 ( 4 ) 我们实验了选择策略对g i l p 收敛性能的影响，提出了采用竞赛规模动态改变的 锦标赛选择策略，来解决遗传搜索中存在的未成熟收敛和随机漫游问题。基于我们的研究 成果，开发出了g i l p 原形系统，在连通图问题，g o d 函数定义问题以及现实的房地产价 格规律问题上取得了好的挖掘结果。 关键词数据挖掘：归纳逻辑程序设计；遗传算法；一阶规则 i i a b s t r a c t a b s t r a c t d a t am i n i n gt e c h n i q u ei so n eo f t h ek e yr e s e a r c hf i e l d si nt h ec u r r e n tc o m p u t e rt e c h n o l o g y m o s tc u r r e n tr e s e a r c h e so f d a t a m i n i n ga r el i m i t e di nt h ep r o p o s i t i o nl o g i cf r a m e w o r k ，i nw h i c h t h e n ：e x i s td i s a d v a n t a g e so fw e a kr e p r e s e n t a t i o np o w e ra n dn o tb e i n ga b l et ou t i l i z en a t u r a l l y b a c k g r o u n dk n o w l e d g e f u r t h e r m o r e ，m o s tr e s e a r c h e sh a v eu s e dt h e “s i n g l e - t a b l ea s s u m p t i o n a n df i n do u tap a t t e r nf r o md a t as t o r e di ns i n g l e - t a b l e ，b u td a t ai s u s u a l l ys t o r e di nm u l t i p l e t a b l e so fr e l a t i o n a ld a t a b a s e i fo n ew a n t st ou s et h e s e e x i s t i n gm e t h o d s ，h ew i l l h a v et o o v e r c o m et h ep r o b l e mo f h o wt os q u e e z ed a t ai n t os i n g l e t a b l e f i r s t - o r d e rr u l em i n i n gt e c h n i q u eb a s e do nf i r s t o r d e rl o g i ci so f t e nc a l l e da si n d u c t i v e l o g i cp r o g r a m m i n g ( i l p ) f i r s t o r d e rl o g i cp r o v i d e si l pw i t hau n i f o r ma n dv e r ye x p r e s s i v e m e a n so fr e p r e s e n t a t i o n ：t h eb a c k g r o u n dk n o w l e d g ea n dt h ee x a m p l e s ，a sw e l la st h em i n e d r u l e s ，c a na l l b er e p r e s e n t e da sf o r m u l a si nac l a u s a l l a n g u a g e s ow ec a n u s e n a t u r a l l y b a c k g r o u n dk n o w l e d g e i nt h em i n i n gp r o c e s s f u r t h e r m o r e ，t h em i n e d k n o w l e d g ei sr e p r e s e n t e d a sf i r s t - o r d e rr u l e sc o n s t r u c t e db yc e r t a i np r e d i c a t e s ，w h i c hi sm o r ep o w e r f u li n d e s c r i p t i o n c a p a c i t yt h a np r o p o s i t i o nr u l e t h er e p r e s e n t a t i o na l l o w s f o rk n o w l e d g ew i t hm o r ea b u n d a n t i n t e n s i o na n dm o r ee a s i l yu n d e r s t o o d t h e r e f o r e ，i l pc a no v e r c o m et w ok e yl i m i t a t i o n se x i s t i n g i np r o p o s i t i o nr u l em i n i n gm e t h o d s ：t h el i m i t a t i o no f d e s c r i p t i o nc a p a b i l i t ya n d t h el i m i t a t i o no f u t i l i z i n gb a c k g r o u n dk n o w l e d g e i na d d i t i o n ，b e c a u s et h e r ei si n t e r n a lr e l a t i o n s h i pb e t w e e nt h e f o m l a l i s mo fr e l a t i o n a ld a t a b a s e ，r e l a t i o n a la l g e b r a ，a n dt h ec l a u s a ll o g i cu s e db y1 l p , i l p m e t h o d sc a nd i r e c t l yd e a lw i t h m i n i n g t a s ki n v o l v e di nm u l t i p l et a b l e so f r e l a t i o n a ld a t a b a s e f i r s t o r d e rr u l em i n i n gc a nb ev i e w e da st h es e a r c ht h r o u g ht h ef i r s t - o r d e rr u l e s p a c e c o n s i d e rt h eh u g e n e s sa n dt h ee x t r e m ec o m p l e x i t yo ff i r s t - o r d e rr u l es p a c e ，i no r d e rt oc a r r yo u t a ne f f e c t i v es e a r c h ，m o s ti l p s y s t e m sh a v eu s e dg r e e d ys e a r c hs t r a t e g ya n dr e q u i r e dt oe x p l i c i t l y p r e s e n ts t r o n gl a n g u a g eb i a sr e l a t e dt ot h em i n i n gt a s k ，t h es t r u c t u r ef e a t u r ed e s c r i p t i o no f f i r s t o r d e rr u l e se x p l o r e di nm i n i n gp r o c e s s ，t or e d u c et h es e a r c hr a n g eo ri su s e da sh e u r i s t i c st o g u i d et h es e a r c h t h eg r e e d ys e a r c hs t r a t e g ym a yl e ts e a r c ht r a p p e di nal o c a lm a x i m u m t h e a d d i t i o n a ll a n g u a g eb i a sp r o d u c e s g o o ds e a r c he f f e c to n l yw h e n t h et a r g e tr u l e sm a t c h i t ，w h i c h i sn o ta p p l i c a b l ef o rt h ef a c tt h a tt h ep r i o rk n o w l e d g ea b o u tt h es t r u c t u r e so ft a r g e tr u l e si s u s u a l l yl a c ki nd a t am i n i n g t a s k g e n e t i ca l g o r i t h m ( g a ) s i m u l a t i n g b i o l o g i ce v o l u t i o nm e c h a n i s mi ss t o c h a s t i c l i k es e a r c h m e t h o d i tg u i d e st h es e a r c hd i r e c t i o na c c o r d i n gt op r n b a b i l i s f i ct r a n s i t i o nr e g u l a r i t y i tu t i l i z e s t h ei n f o r m a t i o na c q u i r e da n da c c u m u l a t e di ne v o l u t i o np r o c e s st oo r g a n i z es e a r c hb yi t s e l fa n d a d a p t i v e l yc o n t r o lt h es e a r c hd i r e c t i o n i tn e e d sl i t t l ek n o w l e d g ea b o u ts e a r c hs p a c eo ro t h e r a u x i l i a r yi n f o r m a t i o n ，w h i c hf i t st h ed a t am i n i n gt a s k g aa d o p t sp o p u l a t i o ns e a r c hs t r a t e g y , s o i th a ss t r o n gg l o b a ls e a r c hp e r f o r m a n c ea n dr e d u c e st h er i s ko f t r a p p i n gi n t ol o c a lm a x i m u m i i i 北京工业大学工学博士学位论文 h e n c e ，i no r d e rt oe n h a n c et h er o b u s t n e s sa n da d a p t a b i l i t yo f f i r s t - o r d e rr u l em i n i n gt e c h n i q u e a n ds o l v et h ep e r f o r m a n c ep r o b l e mo ff i r s t - o r d e rr u l em i n i n g ，i l pc a na d o p tg e n e t i ca l g o r i t h m a st h es e a r c hs t r a t e g y t h i sd i s s e r t a t i o nc o n c e n t r a t e so nt h ei n i t i a lr e s e a r c hw o r ki n g e n e t i c i n d u c t i v e l o g i c p r o g n a n m i n gt e c h n i q u e u s i n gg e n e t i ca l g o r i t h mt om i n et h ef i r s t - o r d e rr u l e sd e p e n d so nt w o f a c t o r s ：t h e l a n d s c a p e i ng e n e t i cs p a c ea n dt h e “n a v i g a t i o n ”i ng e n e t i cs p a c e t h et w of a c t o r s r e f l e c tr e s p e c t i v e l yt h es t a t i ca n dd y n a m i cf e a t u r e so fa l g o r i t h m t h e “l a n d s c a p e ”i ng e n e t i c s p a c ed e s c r i b e st h e s t a t i cf e a t u r eo fa l g o r i t h m ，w h i c hi sa s s o c i a t e dw i t ht h et r i p l e s ：( 1 ) t h e c o d i n g ，w h i c h t r a n s f o r m sf i r s t o r d e rr u l ei n t ot h er e p r e s e n t a t i o na p p l i c a b l et og e n e t i co p e r a t i o n b y t h ec o d i n g ，a l lf i r s t o r d e rr u l e sn e e d e dt oe x p l o r ea r cm a p p e di n t ot h ep o i n t si ng e n e t i cs p a c e ； ( 2 ) t h ef i t n e s sf u n c t i o n ，w h i c he v a l u a t e st h eq u a l i t yo ff i r s t - o r d e rr u l e t h ev a r i a t i o n o f f i r s t - o r d e rr u l ef i t n e s s p r e s e n t t h e u p a n d - d o w nl a n d s c a p e i n g e n e t i cs p a c e ( 3 ) t h e n e i g h b o r h o o dr e l a t i o n o ff i r s t - o r d e rr u l e s ，w h i c hi sd e t e r m i n e db yc r o s s o v e ra n dm u t a t i o n o p e r a t o ra n dr e p r e s e n tt h eg a p sa n db r i d g e si ng e n e t i cs p a c el a n d s c a p e t h e “n a v i g a t i o n ”i n g e n e t i cs p a c er e f l e c t st h ed y n a m i c c h a r a c t e r o f a l g o r i t h m ，w h i c hi st h ep r o c e s s t h a tp o p u l a t i o ni s o p e r a t e db ys e l e c t i o n ，c r o s s o v e ra n dm u t a t i o no p e r a t o rt o c l o s et oo p t i m a t h i sd i s s e r t a t i o n m a i n l yi n v e s t i g a t e s t h ek e yt e c h n i q u e si n g e n e t i c i n d u c t i v el o g i c p r o g r a m m i n g ，i n c l u d i n g f i r s t - o r d e rr u l ec o d i n g ，t h ed e s i g no fg e n e t i co p e r a t o r , s e l e c t i o ns t r a t e g ya n dt h es t r u c t u r eo f g i l pa l g o r i t h m f u r t h e r m o r e ，w ea n a l y z ea n de x p l a i nt h eg r o w t hp h e n o m e n o no fi n d i v i d u a l s c o d e l e n g t h i n g e n e t i ci n d u c t i v el o g i cp r o g r a m m i n g o nt h e b a s i so ft h er e s e a r c ha b o u t e q u i w d e n c ec l a s sp r o b l e me x i s t i n g i nf i r s t - o r d e rr u l e m i n i n g ，w ep r o p o s eaf i t n e s s f u n c t i o n b a s e do ni n f o r m a t i o ng a i n i nt e r m so fo u rr e s e a r c hr e s u l t s ，w eh a v ed e v e l o p e dap r o t o t y p e s y s t e ma n du s e di t t om i n i n gf i r s t - o r d e rr u l e s t h em a i nr e s e a r c hr e s u l t sa n di n n o v a t i o n sa r e g i v e n a sf o l l o w s ： ( 1 ) o nb a s i s o fh a v i n gc o g n i z a n c eo ft h ef i r s t - o r d e rr u l e m i n i n gi s t h ec o m b i n a t i o n o p t i m i z a t i o np r o b l e mo fa t o m s ，c o n s t r u c t e db yt a r g e tp r e d i c a t ea n db a c k g r o u n dk n o w l e d g e p r e d i c a t e s ，i ne s s e n c e ，w em a k e u s eo f o c c a m sr a z o rp r i n c i p l et op r o p o s eab i ts t r i n gc o d i n go f f i r s t o r d e rr u l e ，w h i c hm e e tt h em i n i m u mc h a r a c t e rs e tc o d i n gc r i t e r i o n t h ec o d i n go n l ya s k u s e rt ot r a d eo f fb e t w e e nt h ec o m p u t i n gc o s ta n dt h ec o m p l e x i t y , g i v e nb yt h em a x i m u mo f s e q u e n c en u m b e ro fd i f f e r e n tv a r i a b l e sa p p e a r i n gi ne x p l o r e dr u l e ，o fm i n e dk n o w l e d g e u s e r n e e d n tp r e s e n te x p l i c i t l yl a n g u a g eb i a sd e s c r i b i n gt h es t r u c t u r ef e a t u r eo fe x p l o r e dr u l e s t h a t m e e t st h ed a t am i n i n gt a s ks e t t i n g ，i nw h i c ht h ep r i o rk n o w l e d g ea b o u tt h es t r u c t u r eo f t a r g e t r u l ei sl a c k w ed e s i g ng e n e t i co p e r a t o rf o rb i ts t r i n gc o d i n gd e s i g n e db yu s ，w h i c hm e e t st h e f i r s t r u l es y n t a xc o n s t r a i n t w ep u tf o r w a r dg e n e t i ci n d u c t i v el o g i cp r o g r a m m i n ga l g o r i t h m g i l pb a s e do nt h ec o v e r i n g - a n d - r e m o v i n g s t r a t e g y ( 2 ) t h r o u g ht h es c h e m aa n a l y s i so fi n d i v i d u a l sw i t hv a r i a b l el e n g t h ，t h ei n d i v i d u a l s c o d e g r o w t h d e t e c t e di ng i l pi s e x p l a i n e d i na d d i t i o n ，w ed i s c o v e rt h a t t h e p o p u l a t i o n w i l l d e g e n e r a t ei f t h el e n g t hp e n a l t yo fi n d i v i d u a l sf i t n e s si sa d d e df r o mt h ei n i t i a lp o p u l a t i o n t h u s a b s t r a c t w e p r o p o s ep e n a l t ys t r a t e g yb a s e d o ne v o l u t i o np e r i o d ，w h i c hc a na v o i dp o p u l a t i o nd e g e n e r m i o n a n dr e s t r a i ne f f e c t i v e l yt h ei n d i v i d u a l sc o d eg r o w t ha tt h es a m et i m e ( 3 ) t h ek e yo fu s i n gg e n e t i ca l g o r i t h mt om i n ef i r s t - o r d e rr u l e si sh o w t op r e c i s e l ye v a l u a t et h e q u a l i t yo f e a c h f i r s t - o r d e rr u l e ，t h a ti s ，r u l e s f i t n e s sc a l ls c o r et h e i rq u a l i t yr i g h t l ya n d e f f e c t i v e l y g u i d eg e n e t i ca l g o r i t h m t oc l o s et ot h et a r g e tr u l e t h e r ee x i s t se q u i v a l e n c ec l a s sp r o b l e mi nt h e c o m m o ne v a l u a t i o nc r i t e r i o nb a s e do nt h en u m b e ro f e x a m p l e sc o v e r e db yr u l e s ，w h i c hl e a d st h e s e a r c hp r o c e s so fg i l pt ob eb l i n d l yi n c l i n e dt ot h el o n gr u l ea n dw i l lb a d l yr e d u c et h es e a r c h e f f i c i e n c yo fa l g o r i t h ma n dt h er e a d a b i l i t yo fr u l e s b ya d o p t i n gt h ec o n c e p to fb i n d i n ga n d i n f o r m a t i o nt h e o r y , w ep r o p o s ean e wf i t n e s sf u n c t i o nb a s e do ni n f o r m a t i o ng a i n aa n a l y s i sa n d ac o n t r a s te x p e r i m e n td e m o n s t r a t et h a tt h en e wf i t n e s sf u n c t i o nc a nd i s t i n g u i s ht h eq u a l i t yo f e q u i v a l e n c er u l e sa n dg u i d e sm o r ee f f e c t i v e l yt h es e a r c hd i r e c t i o no f a l g o r i t h m ( 4 ) w et e s tt h ei n f l u e n c ee x e r t e db ys e l e c t i o ns t r a t e g yo ng 1 l pc o n v e r g e n c ep e r f o r m a n c e a n d p r o p o s et oa d o p tt o u r n a m e n ts e l e c t i o n w i t h d y n a m i ct o u r n a m e n t s i z et os o l v e p r e m a t u r e c o n v e r g e n c ea n ds t o c h a s t i cr o a m i n gp r o b l e m se x i s t i n gg e n e t i cs e a r c h o nb a s i so fo u rr e s e a r c h r e s u l t s ，w eh a v ed e v e l o p e dg i l p p r o t o t y p es y s t e m w eu s eg i l p i nc o n n e c tg r a p h p r o b l e m ，g c d f u n c t i o np r o b l e ma n dr e a le s t a t ep r i c er e g u l a r i t yp r o b l e m ，a n dh a v e g o tg o o dm i n i n gr e s u l t k e y w o r d sd a t a m i n i n g ；i n d u c t i v el o g i cp r o g r a m m i n g ；g e n e t i ca l g o r i t h m ； f i r s t - o r d e rr u l e v 第1 章绪论 第1 章绪论 随着计算机的普及和数据处理在计算机应用中所占比重的上升，数据库的 应用已经触及到人类生活的各个方面。特别是随着传感器，通讯，存储等技术 的迅速发展，使得收集和存储大量的科学、工业和商业数据成为可能。 目前对数据库中数据的开发应用还主要是检索查询和统计。简单的数据查 询或统计虽然可以满足某些低层次的需求，但随着数据在日常决策中的重要性 越来越显著，人们更为需要的是从大量数据资源中挖掘出对各类决策有指导意 义的一般知识。这些知识是对大量数据的高度浓缩和抽象，是对数据整体的全 面而深刻的认识。这些经过智能分析和表示的数据才是有价值和竞争力的社会 资源。 1 1 知识发现和数据挖掘 从数据库中抽取大量琐碎数据中隐含的、预先未知和潜在有用信息的知识 发现k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 技术及数据挖掘技术d m ( d a t a m i n i n g ) 就是在这样一个时代背景下应运而生的，它们的目的就是分析处理数 据厍中大量的数据，发现有用的知识，为用户提供所需问题的答案。 1 1 1k d d 和d m k d d 术语是在1 9 8 9 年8 月于美国底特律市召开的第一届k d d 专题讨论会 上首次被采用的。1 9 9 5 年，在加拿大召开了第一届知识发现和数据挖掘国际学 术会议，由于数据库中的数据被形象地喻为矿床，因此数据挖掘一词很快流传 开来。长期以来，在知识发现领域这两个术语的范畴和使用界限一直不很清晰。 为此，f a y y a d 、p i a t e t s k y s h a p i r o r 和s m y t h 对k d d 作了确切定义l l j 。： 定义l ：k d d 是扶大量的数据中提取函司信的、新颖的、有效的 并能被人理解的模式的处理过程，这嵇处理过程是非平 凡的过程， k d d 系统是由完成从访问数据库管理系统( d b m s ) 中的数据、使用模式 提取算法、直至评价和和解释结果这一知识发现完整过程的所有组件的集成。 k d d 过程可以划分为3 个主要的阶段：数据准备、数据挖掘和结果表达和解释。 北京工业大学工学博士学位论文 其中d m 是使用挖掘算法进行模式挖掘的子过程，是k d d 过程的核心步骤。 它可概略地定义为对数据集合进行分析，发现有价值和有意义的模式或模型。 由于知识发现过程中各部分之间的紧密相关性和d m 技术的核心作用，通常不 严格区分k d d 和d m 。 1 1 2 知识发现过程 k d d 是一个多步骤的处理过程，在处理过程中可能会有多次反复。主要处 理步骤见图1 1 。 | 一数据准备 一数据挖掘4 _ 一结果表达叫 数据源 图1 - 1k d d 过程 f i g 1 - 1t h e k d dp r o c e s s 完整的知识发现步骤如下： i 确定业务对象 数据挖掘的最后结果是不可预测的，但要探索的问题应是有预见的。为了 数据挖掘而数据挖掘则带有盲目性，也是没有意义的。因此数据挖掘第一步是 清晰地定义出业务问题，认清数据挖掘的目的。 2 数据准备 数据准备主要包括数据集成，数据的选择，数据的预处理和数据的转换四 个步骤： 1 ) 数据集成 从各种数据源中获取所有与业务对象有关的内部和外部信息数据。在数据 第1 章绪论 挖掘中，可能一些外部数据也是必须的，需要从公共数据库中获取( 如人口统 计或天气数据) 或向数据拥有者购买( 比如信用卡使用数据) 。 2 ) 数据的选择 从数据集成得到的原始数据中选择出用于数据挖掘的数据。这与对数据进 行采样和选择预测变量是不同的，这里只是粗略地把一些冗余或无关的数据除 去，或由于资源的限制、费用的限制、数据使用的5 1 1 l f 0 而做出的选择。 3 ) 数据的预处理 主要对前一阶段产生的数据进行再加工，检查数据的完整性和数据的一致 性，对噪音数据进行处理，对丢失的数据域进行填补，为进一步的分析做准备。 4 ) 数据的转换 将数据转换成一个分析模型。这个分析模型是针对挖掘算法建立的。建立 一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 3 数据挖掘 针对所要发现任务的所属类别，如关联、分类、回归、聚类等，设计或选 择某个特定的数据挖掘算法进行数据挖掘，找出数据中的模式。 4 结果分析 解释并评估发现的模式，去掉多余的不切题意的模式，并将有用的模式以 用户能理解的方式呈现。 5 知识的同化 用预先、可信的知识检查和解决知识中可能的矛盾，将分析所得到的知识 集成到业务信息系统的组织结构中去，验证这些知识的作用，根据实际情况对 知识发现过程中的具体处理阶段进行优化，直到满足用户要求。 1 i 3 数据挖掘与传统分析方法的区别 数据挖掘与传统数据分析( 如查询、报表、联机应用分析) 的本质区别在于： 数据分析只是已有数据的直接或简单的使用；而数据挖掘则是从中找出隐含的 知识。数据挖掘所得到的信息具有新颖，有效和实用三个特征： 新颖的信息是指该信息是预先未曾预料到的，既数据挖掘是要发现那些不 能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越 是出乎意料，就可能越有价值。在商业应用中最典型的例子就是一家连锁店通 过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系 信息的有效要求挖掘前要对被挖掘的数据进行仔细检查，保证它们的有效 性和分布具有代表性，才能保证挖掘出来的信息的有效性。 最为重要的数据挖掘得到的信息具有实用性，即这些信息或知识对于所讨 北京工业大学工学博士学位论文 论的业务或研究领域是有实用价值且可实现的。常识性的结论，或已被人们或 竞争对手早已掌握的，或无法实现的事实都是没有意义的。 1 1 4 数据挖掘技术的发展过程 数据挖掘技术的发展是一个逐渐演变的过程。它起先主要应用于商业活动， 例如市场管理、风险管理和欺诈管理。数据挖掘的核心模块技术经历了数十年 的发展，其中包括数理统计、人工智能、机器学习。今天，这些成熟的技术， 加上高性能的关系数据库引擎以及广泛的数据集成，让数据挖掘技术在当前的 数据仓库环境中进入了实用的阶段。表1 1 给出了最具代表性的从商业数据到 商业信息的发展过程1 2j 。在这一过程中，每一步前进都是建立在上一步的基础 上的。从表中我们可以看到，第四步进化是革命性的，因为从用户的角度来看， 这一阶段的数据库技术已经可以快速地回答商业上的很多问题。 表1 - 1 数据挖掘的发展过程 t a b l e1 - 1t h ee v o l u t i o np r o c e s so f d a t am i n i n g p r o c e s s商业问题支持技术 产品厂家产品特点 数据搜集“过去五年中我的计算机、磁带和提供历史性的、 ( 6 0 年代)总收入是多少? ” 磁盘 i b m c d c 静态的数据信息 数据访问 “在新英格兰的分 关系数据库 部去年三月的销 ( r d b m s ) ，结 o r a c l e 、s y b a s e 、 在记录级提供历 ( 8 0