（控制理论与控制工程专业论文）基于位表的关联规则挖掘及关联分类研究.pdf

大连理工大学博士学位论文 摘要 随着人们利用信息技术生产和搜集数据的能力大幅度提高，数据资料的规模急速膨 胀。如何快速有效的从海量数据中发现隐藏的、预先未知的信息和知识显得尤为重要， 数据挖掘是解决这一问题的有力工具。关联规则( a s s o c i a t i o nr u l e s ) 获取是数据挖掘研 究的一个重要领域，从某种意义上来讲，关联规则挖掘就是数据挖掘的本质。近年来相 关的研究与应用一直占有重要的比例并得到了迅速发展。研究如何快速有效的从海量数 据库中挖掘蕴含其中的关联规则，并将挖掘得到的关联规则合理利用，具有十分重要的 理论和实际意义。本文在分析现有挖掘算法中存在问题的基础上，提出基于位表的完全 频繁项集和事务间频繁闭项集的挖掘算法，并进一步研究关联规则在分类问题中的应 用，利用其解决遥感影像分类问题。本文的研究工作可概括为如下三个方面的内容： 1 、研究事务内完全频繁项集的快速挖掘算法。现有的完全频繁项集挖掘算法多基 于a p r i o r i 算法，称为a p r i o r i 类算法。其在生成候选集须逐个比较两个项集的前门1 项， 并且在计算支持度需对全部或部分数据库进行逐条扫描，占用大量的计算时间和i o 操 作，成为此类算法的主要瓶颈。针对以上问题，本文首先提出了位表( b i t t a b l e ) 数据 结构及其相应的二进制操作。利用其对事务数据库进行压缩，同时通过二进制“与、 “或 操作快速计算候选项集的支持度，改善了低效率的数据库扫描操作；利用其对候 选项集和频繁项集进行横向压缩，可直接生成候选项集，避免了逐项比较的复杂操作。 该数据结构及其操作可以直接应用于现有的a p r i o r i 类算法中，有效地改善此类算法的 效率问题。在位表数据结构的基础上，本文进一步提出了基于位表的关联规则挖掘算法 b i t t a b l e f i 。对常用数据集的仿真试验表明了该算法的有效性。 2 、研究事务间频繁闭项集及其快速挖掘算法。相对于事务内频繁项集，事务间频 繁项集能够有效的揭示各属性在不同时刻的关联性，是事务内频繁项集的扩展。然而事 务间频繁项集的数量随滑动时间窗口的增大而迅速增加，造成挖掘效率降低，利用闭项 集来表示事物间频繁项集能够在不丢失信息的情况下有效的减少项集的数量。本文通过 分析事务内频繁闭项集和事务间频繁闭项的内在关系，提出了一种利用事务内频繁闭项 集生成事务间频繁闭项集的算法。算法采用分割和条件数据库技术，有效的避免了生成 庞大的扩展事务数据库，利用扩展的位表结构压缩事务从而提高支持度的计算效率。此 外，采用动态排序和哈希技术极大地减少了频繁闭项集的测试次数。该算法为挖掘事物 问频繁闭项集提供了一种有效而快速的算法。 3 、研究模糊关联分类算法，并利用其解决遥感影像分类问题。关联分类将挖掘获 取的频繁项集应用于解决分类问题，将关联规则的挖掘和应用问题紧密结合。将模糊方 基于位表的关联规则挖掘及关联分类研究 法引入到关联分类问题中，能够较好的解决规则的“尖锐边界“问题。然而，现有的模 糊关联分类算法多采用固定模糊隶属度函数对连续型属性进行模糊划分，没有考虑数据 本身的特性。基于此，本章提出一种基于自适应区间划分的模糊关联分类算神a r c ( f u z z ya s s o c i a t i o nr u l e sc l a s s i f i c a t i o n ) ，利用模糊c 均值聚类算法根据数据本身的特点 自适应地建立模糊区间，并在挖掘模糊关联规则时采用了新的剪枝策略，极大地减少了 候选集的数量。新的规则权重度量方法能够更好的利用多模糊关联规则进行分类。对 u ci r v i n em a c h i n el e m n i n gr e p o s i t o r y 测试数据的实验表明，f a r c 不仅是具有高精度 的分类精度，同时具有对训练样本数量的不敏感性，在训练样本减少的情况下仍能保持 较好的分类精度，是一种有效的分类方法。同时，本文将模糊关联分类算法引入遥感图 像分类问题的研究中，在实际遥感分类问题中，训练样本往往较难获取，训练样本的不 足会导致分类精度的下降，本文提出的f a r c 算法能够较好的适应训练样本较低情况下 的分类问题，从而能够很好的应用于实际遥感分类问题。 关键词：数据挖掘；关联规则；关联分类；频繁项集挖掘；遥感分类 大连理工大学博士学位论文 a b s t r a c t w i mt h ei n c r e a s eo fh u m a na b i l i t yo fu s i n gi n f o r m a t i o nt e c h n o l o g yt op r o d u c ea n dc o l l e c t 幽纽t h es c a l eo fd a t ai n f l a t e sr a p i d l y i ti sv e r yi m p o r t a n tt od i s c o v e rt h eh i d d e na n d u n k n o w nk n o w l e d g ei nt h ed a t a b a s e s d a t am i n i n gi sap o w e r f u lt o o lt os o l v et h e s ep r o b l e m s a s s o c l a r i o nr u l e sm i n i n gi sa l li m p o r t a n tf i l e do fd a t am i n i n g i nas e n s e ，a s s o c i a t i o nr u l e s m i n i n gi st h ee s s e n c eo fd a t am i n i n g t h er e s e a r c ha n da p p l i c a t i o no f i to c c u p ya l li m p o r t a n t p r o p o r t i o no fd a t am i n i n gr e s e a r c ha n dh a v eb e e nd e v e l o p e dr a p i d l y t h er e s e a r c ho nh o w t o m i l l et h ea s s o c i a t i o nr u l e sf r o mt h em a s s i v ed a t a b a s e se f f i c i e n t l ya n du s et h e mr e a s o n a b l yi s o fg r e a tt h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e b a s e do nt h ea n a l y s i so fc u r r e n tm i n i n g a l g o r i t h m s ，a l li n t e r - t r a n s a c t i o nf r e q u e n ti t e m s e t sm i n i n ga l g o r i t h ma n da ni n t r a - t r a n s a c t i o n f r e q u e n ti t e m s e t sm i n i n ga l g o r i t h ma r ep r o p r o s e dt os o l v et h ep r o b l e mo fr e m o t es e n s i n g i m a g ec l a s s i f i c a t i o n i nt h i sd i s s e r t a t i o n , t h er e s e a r c hw o r kc a l l b es u m m a r i z e da st h e f o l l o w i n gt h r e ea s p e c t s ： 1 们1 er e s e a r c ho nt h ef a s tm i n i n ga l g o r i t h mo fc o m p l e t ef r e q u e n ti t e m s e t s m o s to f m o d e mc o m p l e t ef r e q u e n ti t e m s e t sm i n i n ga l g o r i t h m sa r eb a s e d0 1 1t h ea p r i o r ia l g o r i t h m , c a l l e da p r i o r i l i k ea l g o r i t h m s m e ng e n e r a t i n gc a n d i d a t ei t e m s e t s ，t h e yn e e dt oc h e c ki fa n y t w oi t e m s e t sh a v et h es a m en 1i t e m sa n dw h e nc o u n t i n gt h es u p p o r t ，t h ew h o l eo rp a r to ft h e d a t a b a s e sn e e d st ob es c a n n e do n eb yo n e w h i c hw a s t e sal o to fc p u t i m ea n di oo p e r a t i o n s t h et w op r o b l e m sa r et h em a i nb o t t l e n e c k so ft h ea p r i o r i l i k ea l g o r i t h m s a c c o r d i n gt ot h e t w op r o b l e m s t h ed i s s e r t a t i o np r o p o s e sas p e c i a ld a t as t r u c t u r en a m e db i t t a b l ea n di t s b i t w i s eo p e r a t i o n b i 仃a b l ei sa d o p t e dt oc o m p r e s sd a t a b a s e sa n dg e n e r a t ec a n d i d a t ei t e m s e t s q u i c k l yb yt h eb i t w i s ea n d o ro p e r a t i o nt oa v o i ds c a r f i n gd a t a b a s e s i ta l s oh o r i z o n t a l l y c o m p r e s s e st h ec a n d i d a t ei t e m s e t sa n df r e q u e n ti t e m s e t s ，a n dg e n e r a t e sc a n d i d a t ei t e m s e t s d i r e c t l yt oa v o i dt h eo p e r a t i o no fc o m p a r i n ge a c hi t e m t h i sd a t as t r u c t u r ec a nb ea p p l i e di n a p r i o r i 1 i k ea l g o r i t h m sd i r e c t l ya n di m p r o v et h e i rp e r f o r m a n c ee f f e c t i v e l y m o r e o v e r ，a l l a s s o c i a t i o nr u l e sm i n i n ga l g o r i t h mn a m e db i t t a b l e f ii sp r o p o s e db a s e do nb i t t a b l e t h e e x p e r i m e n tr e s u l t sd e m o n s t r a t et h ee f f e e t i v e n e s so f t h eb i t t a b l e f ia l g o r i t h m 2 t h er e s e a r c ho ni n t e r t r a n s a c t i o nf r e q u e n tc l o s e di t e m s e t sa n di t sf a s tm i n i n ga l g o r i t h m c o m p a r e dw i t hi n t r a - t r a n s a c t i o nf r e q u e n ti t e m s e t s ，t h ei n t e r - t r a n s a c t i o nf r e q u e n ti t e m s e t sc a l l e f f e c t i v e l yr e v e a lt h er e l e v a n c eo fv a r i o u sa t t r i b u t e s a td i f f e r e n tm o m e n t s ，a n da r et h e e x p a n s i o no fi n t r a - t r a n s a c t i o nf r e q u e n ti t e m s e t s h o w e v e r , t h ea m o u n to fi n t e r - t r a n s a c t i o n f r e q u e n ti t e m s e t si n c r e a s e sr a p i d l yw i t ht h ei n e a s eo fs l i d i n gt i m ew i n d o w ，w h i c hw i l l r e d u c et h ee 蚯c i e n c yo ft h em i n i n ga l g o r i t h m i tc a l le f f e c t i v e l yr e d u c et h ea m o u n to fi t e m s e t s w i t h o u tl o s so fi n f o r m a t i o nt ou t i l i z ec l o s e di t e m s e t st or e p r e s e n ti n t e r - t r a n s a c t i o nl r e q u e n t i t e m s e t s t 1 1 i sd i s s e r t a t i o np r o p o s e sa ni n t e r - t r a n s a c t i o nf r e q u e n te l o s e di t e m s e t sm m m g i i i a l g o r i t h m ，b ya n a l y z i n gt h ei n t e r n a l r e l a t i o nb e t w e e nt h ei n t e r - t r a n s a c t i o na n dt h e i n t r a - t r a n s a c t i o nf i e q u e n ti t e m s e t s t h ep r o p o s e da l g o r i t h ma d o p t sd i v i s i o na n de o n d i t i o n d a t a b a s et e c h n o l o g yt oa v o i dt h eg e n e r a t i o no fh u g ee x t e n d e dd a t a b a s e ，u t i l i z e st h ee x t e n d e d b i t t a b l et oc o m p r e s st h et r a n s a c t i o na n d i m p r o v e st h ec o u n t i n ge f f i c i e n c yo ft h es u p p o r t d y n a m i co r d e r i n ga n dh a s ht a b l ed e c r e a s et h et e s t i n gt i m e so ft h ec a n d i d a t ec l o s e d i n t e r - t r a n s a c a t i o ni t e m s e t s s i m u l a t i o n ss h o wt h a tt h e a l g o r i t h mi s af a s ta n de 街c i e n t i n t e r - t r a n s a c t i o nf r e q u e n tc l o s e di t e m s e t sm i n i n ga l g o r i t h m 3 t h er e s e a r c ho nf u z z ya s s o c i a t i v ec l a s s i f i c a t i o na n di t s a p p l i c a t i o no nr e m o t es e n s i n g i m a g ec l a s s i f i c a t i o n a s s o c i a t i v ee l a s s i f i c a t i o nu t i l i z e sa s s o c i a t i o nr u l e st os o l v et h e c l a s s i f i c a t i o np r o b l e m f u z z yc o n c e p ti si n t r o d u c e dt oa s s o c i a t i v ec l a s s i f i c a t i o n ，w h i c hc a n a v o i dt h ep r o b l e mo f s h a r pb o u n d a r y h o w e v e r , m o s to ff u z z ya s s o c i a t i v ec l a s s i f i c a t i o n a l g o r i t h m sa d o p tt h ef i x e dm e m b e r s h i pf u n c t i o nt og e n e r a t ef u z z ys e t s ，w i t h o u tc o n s i d e r i n g t h ei n t r i n s i cc h a r a c t e r i s t i co fd a t a t oa d d r e s st h i s i s s u e ，t h ed i s s e r t a t i o np r o p o s e saf u z z y a s s o c i a t i v ec l a s s i f i c a t i o na l g o r i t h mf a r cb a s e do n 也ea d a p t i v ei n t e r v a lp a r t i t i o n a c c o r d i n g t ot h ei n t r i n s i cc h a r a c t e r i s t i co fd a t a , f a r ce m p l o y sf u z z yc - m e a n st op a r t i t i o nc o n t i n u o u s a t t r i b u t e s ，a d o p t sn e wj o i n t i n ga n dp r u n i n gt e c h n i q u et oa v o i dg e n e r a t i n gu n u s e f u lc a n d i d a t e i t e m s e t sa n di n t r o d u c e saw e i g h t e dp a r a m e t e rt os c o r et h ef u z z ya s s o c i a t i o nr u l e s t h e e x p e r i m e n t so nu c id a t a s e t ss h o wt h a tt h em e t h o dp r o p o s e di nt h i sd i s s e r t a t i o nn o to n l yh a sa h i g h e rc l a s s i f i c a t i o na c c u r a c y , b u ta l s oi si n s e n s i t i v et o 也ev a r i a t i o no fa m o u n to ft h et r a i n i n g d a t as e t i nt h i sd i s s e r t a t i o n ，t h ef u z z ya s s o c i a t i v ec l a s s i f i c a t i o ni si n t r o d u c e dt ot h er e s e a r c h o nr e m o t es e n s i n gi m a g ec l a s s i f i c a t i o n h o w e v e r , i nt h ea c t u a lr e m o t es e n s i n ga p p l i c a t i o n s ， t r a i n i n gd a t ai sh a r dt oo b t a i n , w h i c ha f f e c t st h ec l a s s i f i c a t i o na c c u r a c yo ft r a d i t i o n a l c l a s s i f i e r sg r e a t l y t h ep r o p o s e da l g o r i t h mf a r cc a l le f f e c t i v e l yo v e r c o m et h ep r o b l e mo f l a c k i n gt r a i n i n gd a t as e ti nt h ea c m a lr e m o t es e n s i n gc l a s s i f i c a t i o na n dg e th i 曲c l a s s i f i c a t i o n a c c u r a c y k e yw o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e s ；a s s o c i a t i v ec l a s s i f i c a t i o n ；f r e q u e n ti t e m s e t s ； r e m o t es e n s i n gc l a s s i f i c a t i o n l v 大连理工大学博士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：塑童丝筮鱼趣塑塑造选邀墨鱼 作者签名：缢星日期：坦2 年厶月乙l 日 导师签名 ：j 军鸶竣- 一 日期：兰4 年j 乙肚日 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：么z日期：2 丝乞：望 大连理工大学博士学位论文 1 绪论 本章主要介绍数据挖掘和关联规则的基本概念，对关联规则挖掘和关联分类的研究 进展和现状进行简要回顾，在论述研究问题现状和存在问题的基础上，给出本文的主要 研究工作和内容安排。 1 1 数据挖掘研究概述 数据挖掘( d a t am i n i n g ) 是从大量的、不完全的、有噪声的、模糊的、随机的实际 应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的 过程。这个定义包括多层含义：数据源必须是真实的、大量的、含噪声的；发现的是用 户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准 的知识，仅支持特定的发现问题。数据挖掘是一种新的商业信息处理技术，其主要特点 是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取 辅助商业决策的关键性数据。简而言之，数据挖掘其实是一类深层次的数据分析方法。 1 1 1 数据挖掘技术的产生和发展 随着数据库技术的迅速发展，数据库的规模不断扩大，存储在其中的数据急剧增加。 数据库技术的应用给人们对大量甚至海量数据的存储、管理和查询带来了极大方便。与 此同时，出现了一个新的问题：“数据丰富，但信息( 知识) 贫乏”。大量的数据背后 隐藏着许多重要的信息 1 1 ，人们希望能够对其进行更高层次的分析，以便更好地利用这 些数据【2 】。但海量的数据湮没了蕴含于其中的丰富信息，而传统的查询、报表工具亦无 法满足挖掘这些信息的需求。因此，需要一种新的数据分析技术处理大量数据，并从中 抽取有价值的潜在知识，数据挖掘( d a t am i n i n g ) 技术由此应运而生【3 】。数据挖掘技术 是伴随着数据库技术的发展而不断完善的，它使数据库技术进入了一个更高级的阶段， 不仅能对历史数据进行查询和遍历，而且能够找出历史数据之间的潜在联系，促进信息 的传递，进而“自动”或者帮助人们发现新的知训4 1 。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果，同时，也是信息技 术自然演化的结果。从机器学习到知识工程，从知识工程到专家系统，2 0 世纪8 0 年代 人们又在新的神经网络理论的指导下重新回到机器学习，随后又进入到数据库中的知识 发现，接着又相辅相成地产生数据挖掘。世界上对数据挖掘的正式研究始于1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议。到目前为止，由美国人工智能协会主办 的k d d 国际研讨会已经召开了1 0 余次，规模由原来的专题讨论会发展到国际学术大会， 研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种 基于位表的关联规则挖掘及关联分类研究 学科之间的相互渗透。从大型数据库中发现信息或知识已经成为数据库和机器学习领域 的一个重要的研究课题。对于数据挖掘的研究逐渐成为热点【5 1 ，出现了关联规则【6 1 、决 策树【7 1 、粗糙集法【8 1 、聚类方法 9 1 、遗传算法【1 0 1 和统计分析等多种数据挖掘方法。同时 许多公司也意识到数据挖掘是提高公司决策能力，增加企业收益，提高企业竞争力的一 个重要方面。目前世界上知名大学的研究机构和各大i t 公司的研究部门都投入了大量 精力对其进行研究，并取得了诸多的研究成果。美国斯坦福大学智能数据库系统实验室 开发出了商用化数据挖掘系统d b m i n e r ，该系统包含许多先进的挖掘算法，并有很多优 秀的特点：底层的挖掘细节对于用户不透明，用户无需具有高级的统计知识和培训即可 使用该软件：挖掘的知识类型多种多样，从关联规则、序列模式到发现驱动的分类等； 采用许多先进的研究成果，使得该产品的速度能够达到其同类竞争者的2 0 倍；该系统 可以在多种平台上运行，并与许多主流的数据库系( s q l s e v e r 、o r a c l e 等) 紧密结合； 同时还引入在线分析挖掘技术，使得系统更能充分发挥数据仓库的分析优势。m m 的 a l m a d e n 实验室所进行的q u e s t 项目同样也是数据挖掘研究领域中的佼佼者，该项研究 包含了对关联规则、序列模式、分类及时间序列聚类的研究，其代表性的产品有d b 2 i n t e l l i g e n tm i n e rf o rd a t a 。数据挖掘发现的知识可以应用于信息管理、决策支持、过程 控制等领域，包括数据库领域、机器学习、统计学、知识工程与知识管理、人工智能等 领域的专家都对数据挖掘产生了浓厚的兴趣，数据挖掘已被广泛的应用到金融业u 1 1 、零 售业【1 2 】、制造业【1 3 】以及生物 1 4 】等各个领域，数据挖掘技术的产生和发展历程如表1 1 所 示。 表1 1 数据挖掘的进化历程 t a b 1 1t h ep r o g r e s so fd a t am i n i n g - 2 - 大连理工大学博士学位论文 一个典型的数据挖掘过程主要包含数据准备、数据预处理、模式提取和评价解释等 四个步骤，其过程如图1 1 所示： 数据准备数据预处理 模式提取 v 评价与解释 ，_ o 、，_ o 、 r 、 ， 育。 、一一一一 l j l 库 数据挖掘过程 1 1 t h ep r o r e s so fl a am i n n g 据准备：获取原始的数据，并从中抽取一定数量的子集，建立数据挖掘库。 如果异构数据源中进行，则必须建立统一的数据源，进行多源信息数据的集成。 据预处理：数据预处理是数据挖掘的必要环节。由于数据可能是不完全的、 有噪、随机的，并具有复杂的数据结构。因此，必须要对数据进行初步的整理，清 洗不的数据，对数据做简单的泛化处理和初步的描述分析，选择与数据挖掘有关的 变量者转变变量。 式提取：根据数据挖掘的目标和数据的特征，选择合适的模型，从预处理后 的数提取相应的模式。 价和解释：模式提取的结果有些是有实际意义的，而有些是没有实际意义的， 或是际情况相违背的，这就需要对模式提取的结果进行评价，进而调整挖掘模型， 不断进行数据挖掘。 12数据挖掘的功能和方法 的功能用于指定数据挖掘任务中要找的模式类型，其任务一般可以分为两 类：和预测。描述性挖掘任务刻画数据库中数据的一般特性；预测性挖掘任务在当 前数进行推断，以进行预测。 功能及其可以发现的模式类型主要有概念类描述、关联分析、分类和预测、 聚类、孤立点分析和演变分析等。 念类描述：概念类描述就是对某类对象的内涵进行描述，并概括这类对象的 有关。概念类描述分为特征性描述和区别性描述，前者描述某类对象或概念的共同 特征者描述不同类对象或概念之间的区别。概念类描述可以通过数据特征化和数据- 3 基于位表的关联规则挖掘及关联分类研究 区分两种方法获得：数据特征化是目标类数据的一般特征或特性的汇总；数据区 分是将目标类对象的一般特性与一个或多个对比类对象的一般特性进行比较，目标类和 对比类由用户指定，对应得数据通过数据库查询检索。 ( 2 ) 关联分析：关联分析就是从事务数据库、关系数据库和其他信息存储中的大量 数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。已知一个数据项目集， 确定属性和项目之间的相互关系，例如一个模式的出现意味着另一个模式的出现，它是 数据库中存在的一类重要的可被发现的知识，包括简单关联、时序关联和因果关联等。 关联规则挖掘是关联分析中最常用的方法，也是数据挖掘中一种非常重要的技术。为了 发现有意义的关联规则，需要给定最小信任度( m i n i n u mc o n f i d e n c e ) 和最小支持度 ( m i n i n u ms u p p o r t ) 。最小信任度表明了一组项目关联在一起需要满足的最低联系程度， 最小支持度则反映了一个关联规则的最低可靠度。关联规则挖掘的目的就是找出数据中 满足最小信任度和最小支持度的关联规则。 ( 3 ) 分类和预测：分类是按照分析对象的属性、特征，建立不同的类来描述事物。 分类分析的输入集是一组记录集合和几种标记，标记是指一组具有不同特征的类别。首 先为每一个记录赋予一个标记，然后检查这些标定的记录，描述出这些记录的特征。分 类可以用来预测数据对象的类标记。然而，在某些应用中，人们希望预测某些空缺的或 不知道的数据值，而不是类标记。当被预测的值是数值数据时，通常称之为预测。 分类和预测的应用实例很多。例如，可以将超市的利润水平分为高、中和低三种类 型，并以此分析这三种类型超市的各种属性，特别是位置、主要客户等属性，并决定它 们分类的关键属性及相互间关系。此后就可以根据这些关键属性对每一个预期的超市进 行分析，以便决定预期银行网点属于哪一种类型。当希望预测出超市的利润值时，则分 类问题转化为预测问题。 ( 4 ) 聚类分析：聚类分析是根据所选样本间关联的标准将其划分成多个类或簇，同 一类内的样本具有较高的相似度，不同类的则相异。与分类问题不同，一般情况下，聚 类分析不要求训练数据提供类标记，聚类可以按照某个特定标准自动产生这种类别标 记。通过聚类分析可以把数据划分为一系列有意义的子集，进而实现对数据的分析。聚 类方法适合于探讨样本间的内部关系，从而对样本结构做出合理的评价。聚类分析己被 应用于经济分析、模式识别、图像处理等多种领域，尤其在商业上，聚类分析可以帮助 市场人员发现顾客群中所存在的不同特征组群。聚类分析的技术关键除了算法的选择之 外，就是对样本的度量标准的选择。并非由聚类分析算法得到的类对决策都有效，在运 用某一个算法之前，一般要先对数据的聚类趋势进行检验。 大连理工大学博士学位论文 ( 5 ) 孤立点分析：数据库中可能包含一些数据对象，它们与数据的一般行为或模型 不一致，这些数据对象被称为孤立点。在大部分的数据挖掘方法中，孤立点通常被作为 噪声来进行处理，将其排出在数据挖掘的分析处理范围之外。然而，在一些应用中，如 网络入侵检测，罕见的时间可能比正常出现的那些更有趣，更有挖掘价值，这就为数据 挖掘提供了新的研究课题，即孤立点分析。孤立点分析的主要方法有基于概率统计、基 于距离和基于偏差等检测技术的三类方法。 ( 6 ) 演变分析：描述时间序列数据随时间变化的数据的规律或趋势，并对其建模。 主要包括时间序列趋势分析、周期模式匹配等。 作为一门处理数据的新兴技术，数据挖掘有许多的新特征。首先，数据挖掘面对的 是海量数据，这也是数据挖掘产生的主要原因之一。其次，数据可能是不完全的、有噪 声的、随机的、数据结构复杂、维数大。最后，数据挖掘是许多学科的交叉，运用了统 计学，计算机，数学等学科的技术。以下是常见和应用最广泛的算法和模型： ( 1 ) 传统统计方法：抽样技术：我们面对的是大量的数据，对所有的数据进行分 析是不可能的也是没有必要的，就要在理论的指导下进行合理的抽样；多元统计分 析：因子分析，聚类分析等；统计预测方法：回归分析，时间序列分析等。 ( 2 ) 可视化技术：现代的数据可视化( d a t av i s u a l i z a t i o n ) 技术指的是运用计算机图 形学和图像处理技术，将数据转换为图形或图像在屏幕上显示出来，并进行交互处理的 理论、方法和技术。它涉及到计算机图形学、图像处理、计算机辅助设计、计算机视觉 及人机交互技术等多个领域。数据可视化概念首先来自科学计算可视化( v i s u a l i z a t i o ni n s c i e n t i f i cc o m p u t i n g ) ，随着计算机技术的发展，数据可视化概念己大大扩展，它不仅 包括科学计算数据的可视化，而且包括工程数据和测量数据的可视化。学术界常把这种 空间数据的可视化称为体视化( v o l u mv i s u a l i z a t i o n ) 技术。近年来，随着网络技术和 电子商务的发展，提出了信息可视化( h a l o r m a t i o nv i s u a l i z a t i o n ) 的要求。利用数据可 视化技术，能够发现大量金融、通信和商业数据中隐含的规律，从而为决策提供依据。 这已成为数据可视化技术中新的热蒯巧d 1 丌。 ( 3 ) 决策树：每个决策或事件( 即自然状态) 都可能引出两个或多个事件，导致不同 的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树( d e c i s i o nt r e e ) 。决 策树一般都是自上而下生成的。利用一系列规则划分，建立树状图，可用于分类和预测。 其主要具有以下优点：可以生成可以理解的规则；计算量相对来说不是很大；可以处理 连续和种类字段；可以清晰的显示哪些字段比较重要。但决策树也同时存在对连续性的 字段比较难预测，对有时间顺序的数据需要很多预处理的工作，当类别太多时错误可能 会快速增加等缺点。常用的算法有c a r t 18 1 、c h a d 19 1 、i d 3 2 0 1 、c 4 5 2 1 】等。 - 5 - 基于位表的关联规则挖掘及关联分类研究 ( 4 ) 神经网络：人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，简写为a n n s ) ，也简称 为神经网络( n n s ) 或称作连接模型( c o n n e c t i o n i s tm o d e l ) ，是对人脑或自然神经网络 ( n a t u r a ln e u r a ln e t w o r k ) 若干基本特性的抽象和模拟。人工神经网络是以对大脑的生 理研究成果为基础的，其目的在于模拟大脑的某些机理与机制，实现某个方面的功能。 国际著名的神经网络研究专家，第一家神经计算机公司的创立者与领导人h e c h tn i e l s e n 给人工神经网络下的定义是：“人工神经网络是由人工建立的以有向图为拓扑结构的动 态系统，它通过对连续或断续的输入作状态相应而进行信息处理 。目前在神经网络研 究方法上已形成多个流派，最富有成果的研究工作包括：多层网络b p 算法，h o p f i e l d 网络模型，自适应共振理论，自组织特征映射理论等。人工神经网络是在现代神经科学 的基础上提出来的。它虽然反映了人脑功能的基本特征，但远不是自然神经网络的逼真 描写，而只是它的某种简化抽象和模拟。其模拟人的神经元功能，经过输入层、隐藏层、 输出层等，对数据进行调整、计算，最后得到结果用于分类和回归 2 2 彩】。 ( 5 ) 遗传算法：遗传算法是一类借鉴生物界的进化规律( 适者生存，优胜劣汰遗传机 制) 演化而来的随机化搜索方法。它是由美国的j h o l l a n d 教授1 9 7 5 年首先提出，其主 要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并 行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空 间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛 地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有 关智能计算中的关键技术之一 2 卯9 1 。 ( 6 ) 关联规则挖掘算法：数据关联是数据库中存在的一类重要的可被发现的知识。若 两个或多个变量的取值之间存在某种规律性，则称为关联。关联可分为简单关联、时序 关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库 中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。关 联规则挖掘发现大量数据中项集之间有趣的关联或相关联系 3 0 - 3 4 ，其形式为 彳l 八彳2 八4 拧_ b l 八恳玩”。挖掘过程一般分为两个步骤：求出大数据项集。 用大数据项集产生关联规则。常见的算法有a p r i o r i 、f p g r o w t h 和m a f i a 等。 除上述常用方法外，还有粗集方法、模糊集合方法、b a y e s i a nb e l i e f n e t o r d s 方法、 最邻近算法等。但是从某种意义上来讲，关联规则挖掘是数据挖掘的本质【3 5 1 。 1 2 关联规则挖掘的概念和研究内容 数据挖掘的目的是发现潜藏在数据背后的知识，那么这种知识一定是反映不同对象 之间的关联。关联规则集中在数据库中对象之间关联及其程度的刻画【3 6 - 3 8 】。因此，如何 大连理工大学博士学位论文 快速有效的从海量数据库中挖掘蕴含其中的关联规则，并将挖掘得到的关联规则合理利 用，具有十分重要的理论和实际意义【5 , 3 9 - 4 1 】。 1 2 1 关联规则的基本概念 关联规则的概念最早由r a g r a w a l 等人于1 9 9 3 年提出【4 2 1 。关联规则的相关概念如 下： ( 1 ) 数据项和项集 令= e t ，e 2 ，e n ) ，其中每个e ；( f = 1 ，2 ，刀) 称为数据项。，= i l ，f 2 ，稿是尼个不 同项目的集合，称为