（计算机应用技术专业论文）基于修补项的关联规则可视化挖掘方法的研究.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 随着计算机硬件和信息技术的迅速发展，使得海量数据的处理己经成为研究与 生产中一项重要的工作，数据挖掘技术应运而生。同时，如何帮助用户和分析人员 更快更直观地找到感兴趣的信息或是直接提供新颖的结论成为新的问题。而可视化 技术一直是人们解决复杂问题的一种有利工具。研究如何将可视化技术有效地使用 在数据挖掘中是一件长远而有意义的工作。 将可视化技术应用于数据挖掘中，有利于用户直观的了解数据挖掘的过程，获 得挖掘结果，从而做出决策。不同的挖掘模式，需要不同的挖掘算法，并需要选择 不同的可视化处理方法与之对应。可视化的数据挖掘技术是数据挖掘研究领域的一 个热点问题。 本文在总结国内外可视化数据挖掘的研究成果基础上，主要从两个方面进行了 研究。 着重对关联规则的挖掘算法进行研究。特别研究了多种关联规则挖掘算法，针 对多层结构下的跨层次关联规则存在的冗余问题，提出了一种冗余删除方法，改进 基于修补项的挖掘算法，通过仿真实验证明这种改进后的算法具有较好的性能。 通过比较研究各种关联规则的可视化方法，对它们的优缺点进行讨论。设计了 一种基于坐标轴的可视化用于直观的体现关联规则的相关属性的方法。该方法较多 的考虑了用户与系统中的交互性。对设计的关联规则可视化挖掘系统涉及到的每一 个步骤进行描述与实现。 关键词：数据挖掘；关联规则；修补项；冗余；可视化技术 硕士学位论文 m a s t e r st h e s i s a b s t r a c t a st h es w i f td e v e l o p m e n to fc o m p u t e rh a r d w a r ea n di n f o r m a t i o nt e c h n o l o g y , h o wt o p r o c e s sm a s s i v ed a t ah a sb e c o m ea ni m p o r t a n tw o r ki nr e s e a r c h i n ga n dm a n u f a c t u r e f i e l d s ，s ot h et e c h n o l o g yo fd a t am i n i n gc a n l ei n t ob e i n g a tt h es a m et i m e ，h o wt oh e l p u s e r sa n da n a l y s t st od i s c o v e ri n t e r e s t i n gi n f o r m a t i o nm o r eq u i c k l ya n dm o r ei n t u i t i v e l y o rt op r o v i d et h e m 、而t 1 1m o r en o v e ls o l u t i o nb e c a m et ob ea n o t h e rq u e s t i o n f o r t u n a t e l y , v i s u a l i z a t i o nt e c h n o l o g ya l w a y si sau s e f u lt o o lt ot h i sk i n do fq u e s t i o n s s o ，r e s e a r c ho f a p p l y i n gv i s u a l i z a t i o nt e c h n o l o g yi n t od a t am i n i n gi saj o bo fm e a n i n g f u l a p p l y i n gv i s u a l i z a t i o nt e c h n o l o g yt od a t am i n i n gi sh e l p f u lf o ru s e r st ou n d e r s t a n d t h em i n i n gp r o c e s s ，g e tt h em i n i n gr e s u l ta n dm a k ead e c i s i o nm o r eq u i c k l y d i f f e r e n t m i n i n gp a t t e r nr e q u i r ed i f f e r e n ta l g o r i t h m sa n dd i f f e r e n tv i s u a l i z a t i o nt e c h n o l o g i e sa r c a l s on e e d e d v i s u a ld a t am i n i n gi sah o t s p o t q u e s t i o ni nt h ed a t am i n i n gf i e l d b a s e do i lt h er e s e a r c hr e s u l t sa th o m ea n da b r o a d ，w ec h o o s et h ef o l l o w i n ga st w o o fo u rr e s e a r c hd i r e c t s ： o u rr e s e a r c hf o c u so na l g o r i t h m so fa s s o c i a t i o nr u l e s ，e s p e c i a l l yt h ea l g o r i t h m so f m i n i n gm u l t i l e v e la s s o c i a t i o nr u l e s w ea l s on o t i c et h ep r o b l e mo fr e d u n d a n c ye x i s t i n g i nm u l t i l e v e ls t r u c t u r e ，a n dp r o p o s ear e d u n d a n c yd e l e t i n gm e t h o da n da p p l y i n gi tt ot h e a l g o r i t h mb a s e d o np a t c h i n gi t e m w ep r o v et h a tt h ea l g o r i t h mi s i m p r o v e db i e x p e r i m e n t w ea l s oc o m p a r es e v e r a lv i s u a l i z a t i o nm e t h o d sa n dd i s c u s st h e i ra d v a n t a g e sa n d d i s a d v a n t a g e s w ed e s i g na v i s u a l i z a t i o nm e t h o dt oi n d i c a t ea s s o c i a t i o nr u l e si n t u i t i v e l y , i nw h i c h ，w eh a v ea l r e a d yt h o u g h to ft h ei n t e r a c t i v e l yb e t w e e nu s e r sa n dt h ec o m p u t e r i nt h el a s t ，w ed e s c r i b ee a c hs t e po fav i s u a l i z a t i o ns y s t e ma n dr e a l i z et h e m k e y w 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 ；p a t c h i n gi t e m ；r e d u n d a n e y ；v i s u a l i z a t i o n t e c h n o l o g y 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 名：纹稹 a 努：7 勺缉曩疑矛b 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者签名：轧衣&导师签名： 竺? ! 竺三竺翌三兰三二 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人 的学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程 中的规定享受相关权益。回童诠塞握銮卮溢卮；旦坐生；旦二生；旦三生发壶! 作者签名：乳莰 日期- 矿产歹月日 锄瓠叙奶 帆a 7 年多月扩日 硕士学位论文 m a s l e r st h e s i s 1 引言 数据挖掘，指的是从数据库、数据仓库等大型数据集中提取一些事先未知的、隐 含的潜在知识的过程，这些知识可能是对人们有用的信息。还有一种叫法是知识发 现。提取到的信息的表现形式是概念、规律、模式、规则等【1 】。数据库管理系统 已经越来越广泛的应用于数据存储，而如今分析数据的有力工具是机器学习，数据 挖掘技术起源于数据库管理系统和机器学习相融合的基础上。数据挖掘具有很强 的综合性，它与多个领域的知识有千丝万缕的关系，例如高性能计算 ( 1 l i g h p e r f o r m a n c ec a l c u l a t i o n ) 、数据库技术( d a t a b a s et e c h n o l o g y ) 、统计学( s t a t i s t i c s ) 、 模式识y j i j ( p a t t e r nr e c o g n i t i o n ) 、归纳推t 里( i n d u c t i v ei n f e r e n c e ) 、机器学习( m a c h i n e l e a r n i n g ) 、数据可视化( d a t av i s u a l i z a t i o n ) 。 可视化技术是一种具备交互功能的技术，它利用图像处理技术( i m a g ep r o c e s s i n g t e c h n i q u e s ) 乘l 计算机图形学技术( c o m p u t e rg r a p h i c s ) ，先以动态的图片形式或者以形 状或色彩的方式来表示数据，然后呈现在显示终端上。而我们要研究探讨的数据可 视化，则是将可视化技术应用到大型数据集合中，例如数据仓库( d a t aw a r e h o u s e ) 和数据库( d a t ab a s e ) 。它将数据图像来表示数据较多的数据集，而单个的图元元素则 用来表示单个数据项。当数据存在多个属性值时表现起来比较复杂，一般采用多维 数据、，在这种方式下，纵观数据的维度都可以不同，这样可以更深入的挖掘数据 中隐含的信息【2 】。 信息可视化技术和数据挖掘技术的发展促成了可视化数据挖掘的产生和发展， 这其中也融入了人在某领域的专业知识和感知能力。人类对模式、特征、趋势的感 知能力、可视化技术对显示数据和刻画结构的功能性都成为可视化数据挖掘的基础， 可视化的方式是加强数据挖掘处理的有力工具。可视化就是一个过程，它把数据、 知识和信息以可以被直观观察到的形式表现【3 】，所以可视化可以作为一个接口存在 于人类与计算机之间。合适的可视化方法，在用户与大量数据打交道的过程中可以 挖掘效率更高，快速而正确地发现其中潜在的知识。对于决策者来说，某些挖掘算 法和结果通常过于隐晦而难于理解的，而可视化技术可以有效的解决这个问题，同 时还使用户不仅能够检验结果，还能够对不同的结果对比，动态的改变参数或是挖 掘算法，从而实现用户与系统分析过程之间的交互。 硕士学位论文 m a s t e r st h e s i s 1 1 研究背景 信息产业界在近年来对数觉挖掘表现出极大的关注。数据挖掘被许多业内人士 看作是由信息技术逐步的演化而逐渐形成的。数据挖掘的形成过程经历了以下的一 些过程：数据收集、数据库创建、数据存储、数据检索、失误处理、分析和理解数 据。由于具备查询功能和事务处理功能的数据库系统在现实工作于生活中的广泛应 用，对数据的理解和分析成为急需解决的问题。由于数据量的庞大，自然需要有强 有力的数据分析工具与之对应。巨大数量的数据却存在着“数据丰富，但信息贫乏” 的问题。在大量的大型数据库中存放着海量的数据，并且以非常迅速的速度在增长， 在缺乏强有力的工具的情况下，以人的能力显然是是几乎不可能理解它们的【4 】。 从巨大数量的数据中发现、提取知识的过程就是数据挖掘。利用有效数据挖掘 工具分析海量的数据，可以发现隐含其中的一些数据模式，这些数据模式可能是一 些有趣的规律、知识、位于不同层次的信息等等。并且对于这些被挖掘到的信息、 数据挖掘还提供不同角度供用户浏览或观察它们。 关联规则是主要的数据挖掘内容之一，它的目的是发现存在于大量数据项集间 的有趣的相关联系，从而给决策者制定决策带来方便。1 9 9 3 年a g r a w a l 等首先提出 了了关联规则问题，当时是如何解决如何存在于挖掘存放客户交易数据的事务数据 库中项集间的关系而提出的 5 】。从那以后，关联规则挖掘的理论和应用领域引起许 多研究人员的兴趣，并成为他们的研究重点，如今在商业尤其在零售业上，关联规 则的应用已经十分广泛。 从巨大数量的数据中发现有趣的信息，数据挖掘可谓非常有效的方式。但数据 挖掘的算法相当繁琐而复杂，其抽象的过程、晦涩的挖掘结果一般对用于而言是非 常难以理解的。对用户来说，这就好像是一个黑箱一样，因为整个挖掘过程用户是 无法看到的，用户在整个挖掘过程中都无法干预，挖掘结果也是不直观的，文字是 最终挖掘信息的主要形式，远远达不到直观的要求。如何能让用户更交互地参与到 挖掘的整个过程中去，并对挖掘到的结果进行直观地观察、分析和判断? 数据可视 化技术扮演了桥梁的角色，这个桥梁存在于计算机与用户之间，使他们可以互相沟 通。数据挖掘和可视化技术之间的完美融合，不仅可以使整个数据挖掘过程具有更 高的效率，变得更灵活，而且在与用户的交互性、提高挖掘结果的可信度这些方面， 都发挥了重要作用。对于更复杂的多维数据，数据可视化技术以图形的方式展示其 客观的属性及其内在的联系，使得发现多维数据的过程更加丰富、发现内容更加充 足。在表达原始数据、挖掘过程、挖掘结果方面，数据可视化技术因其优秀的图形 展现能力而显得游刃有余。对用户而言，借助数据可视化技术可以更深刻地理解问 2 硕士学位论文 m a s t e r st h e s i s 题，根据专业知识，挑选合适的挖掘算法，从而对数据的分析可以更加精确。因此， 凭借用户在某领域的专业经验与知识，再加上充分利用可视化技术在准确表达数据 的优越性，可以达到人机交互的目的，这样就可以让用户更加深入地理解问题，并 根据需要不断地选择挖掘参数和算法，这样整个知识挖掘过程可以逐步的被优化， 这样最后挖掘出来的结果会更可靠、更精确。 1 2 关联规则挖掘综述 计算机硬件和信息技术发展的猛烈趋势，使得日常生活越来越信息化。人们已 经习惯于利用信息化的技术来进行生活工作和搜集各种各样的数据，各种各样的庞 大规模的数据库已经在许多领域得到空前广泛的应用，而这也将是一个会持续发展 的趋势。信息的累积已呈现排山倒海的势头，人们要如何能从中有效地获取感兴趣 的信息，而不被庞大的数据锁淹没，主要问题就是要在逐渐积累的数据中能发现新 的知识并且主动的去对其中的关系进行剖析，这是信息技术领域所面临的新的挑 战。数据挖掘作为一种数据处理技术，它的之所以能以如此快的速度发展起来正是 由于这个原因， 1 2 1 数据挖掘的概念 对于数据挖掘的普遍定义是，数据挖掘是从大型放的数据集合中( 这些数据可能 是不确定的、有噪声的、不完全的以及以各种形式存储的) ，发现未知的、潜在的、 有用的知识的过程 6 】。 基于对数据挖掘的普遍定义，典型数据挖掘系统结构如图2 1 所示 4 】： 图2 - 1 数据挖掘系统结构图 对应的步骤如下： 数据清洗、集成和过滤：先将存储在源数据库中的数据整理出来，然后对它 们清洗，然后将经过清理的、可以用于挖掘的数据加载到d w 或者d b 中。 硕士学位论文 m a s t e r st h e s i s 数据库或数据仓库服务器：首先由用户提出挖掘请求和相关要求，数据库或 数据仓库服务器接到请求后，会从数据库或数据仓库中把相关的数据提出出来。 数据挖掘引擎：这个部分是个关键的部分，它包含了一组具有特定功能的模 块，用于执行相关分析的任务，比如关联( a s s o c i a t i o n ) 、分类( c l a s s i f i c a t i o n ) 、聚类 ( c l u s t e r i n g ) 、预测( p r e d i c t ) 、特征化分析( c h a r a c t e r i z a t i o na n a l y s i s ) 等。 模式评估：这部分的功能是识别有趣的模式，这些模式能够真正的表示有 用的知识。这部分还能够与挖掘模块之间进行交互，使有趣的模式的过程更加有效。 当然，发现这些模式需要有某种或某些兴趣度的支持。 用户界面：这部分使用户能够与系统的交互。它在用户和挖掘系统之间进行 信息的传递，用户可以指定数据挖掘的任务，还可以根据挖掘的中间结果进行参数 或者其他方面的相关改进，以可视化的技术表示挖掘到的知识，使得结果以直观的 方式呈现给用户。 1 2 2 数据挖掘模式 发现隐藏在数据中的有趣知识是数据挖掘的基本任务和主要目的，大量数据中 蕴含的非常丰富的可挖掘的模式。描述型模式和预测模式两类是可挖掘的模式的主 要类型。对当前数据中客观存在的事实，比如数据属性、数据项的值做出的很规范 的、很严格的描述，称为描述型模式，它主要是刻画数据所表现出来的一般性质； 而预测性模式的对象是时间序列性的数据，它以时间为基本的参数，以它们曾经的 值和现在的值为依据，对将来的值做出推断。 一般研究的模式类型有以下几种：分类、聚类、关联、孤立点分析等。下面简 单介绍一下这几种模式： 1 ) 分类：构造一个分类模型是分类的主要目的，这个模型也叫分类函数。模型的 创建需要有一个数据集，作为训练的样本输入。再把其中的数据项分别映照到指定 的类别中。 2 ) 聚类：聚类是按照相似性，把一组不同的个体归成一些类别，属于同类别的个 体之间的差别尽可能小，属于不同类别的个体问差则应该别尽可能大。通过聚类分 析，源数据库中的数据将被划分为一些有特殊含义的子集。 3 ) 关联：关联反映的是事件间的联系。关联规则是同时出现的不同项目之间的相 关性。 4 ) 孤立点分析：也称偏差模式。孤立点通常会被当做噪音而丢弃，因为它不符合 一般数据模型。但这类数据也可能成为某种有用信息，比如发现信用欺诈。发现和 4 ：_ 硕士学位论文 m a s t e r st h e s i s 检测孤立点已成为新的课题，基于距离、概率和偏差等等方法都可用于孤立点的检 测。 1 2 3 关联规则概念 关联规则问题是1 9 9 3 年a g r a w a l 等人首先的，当时是针对顾客交易数据库中 如何挖掘项集间关系。在这之后，针对关联规则的挖掘问题，有许多的研究人员都 进行了大量的研究。这些研究工作主要是一下几个方面： ( 1 ) 优化关联规则算法，提高挖掘算法的效率； ( 2 ) 对关联规则的可视化方式行的研究，如何使用户能直观观察挖掘出来的关 联规则的相关属性。关联规则的可视化方法有：规则表、有向图、二( 三) 维矩阵 等等； ( 3 ) 推广关联规则的应用； 购物篮分析是关联规则挖掘的经典例子。数据库中的存在的有趣关联可以通过 对顾客的交易数据的分析而得来： 如果顾客购买了一台新的计算机，那么他同时财务管理软件的可能性是5 0 ， 并且两种商品同时出现的概率为6 。关联规则的形式一般是这样的；“i f aa n db t h e n c 。 从形式上看，规则包含了2 个部分。规则的左边叫前项，一般包含一个或多个 条件，右边叫后项一般只有一个条件。如果要保证后项以某种概率成立，首先要确 保所有前项都是成立的。为了更准确的描述发现的规则，并证明它是有趣的，通常 还会附加一些参数：支持度与置信度 规则的置信度有时候会变得极其重要。因为置信度越高，表示规则前项和后项 之问的关系越必然。就算他们的支持度很低，也可能包含有用的信息。比如某个规 则置信度高达9 0 以上，但是支持度只有0 1 ，即在一千条交易中一定会出现， 但是只会出现一次。如果出现的这一次交易意味着高的利润，那么这条规则就是很 有意义的。 1 2 4 关联规则的相关问题描述 1 d 是数据集，d = t 。，f 2 f 。) ，= i l , f 2 f p ) ，吒( k = 1 , 2 ，刀) 叫做事务， 项目表示为f 。( 册= 1 , 2 ，p ) 。每个事务都有唯一的标识符t i d 。 2 d 中所有项目的集合用i = f 。f 2 f m ) 来表示，d 中的项目集是i 中的任一 子集x ，如果i x l = k ，则称集合石为k 项集。如果x 吒，意思就是项目集x 包 5 ： 硕士学位论文 m a s t e r st h e s i s 含在事务f 中 3 盯。是项目集x 的支持数，它表示数据集d 中，包含了项目集z 的事物数。 s u p p o r t ( x ) 是项目集x 的支持度： s u p p o t r ( x ) 2 茵灯0 0 ( 2 - 1 ) 其中d 的事务数用l 叫来表示，若s u pp o r t ( x ) 大于或等于指定的最小支持度阈 值，那么x 就是频繁项集，否则就是非频繁项集。 4 若x 、】，是d 中的项目集，xny = ，一条关联规则是形如x 】，的蕴 含式。关联规则xjy 的支持度就是项目集xu 】，的支持度。记做： s u p p o r t ( x j n ， s u p p o r t ( xjd = s u p p o r t ( xud( 2 2 ) 关联规则xjy 的置信度记做e o n f i d e n c e ( xj 功 c o n f i d e 甩c e ( x d = 兰等鬻1 。 ( 2 3 ) 最小支持度和置信度一般由挖掘领域的专家指定，分别为m i n s u p p o r t 和 m i n - c o n f i d e n c e 5 如果s u pp o r t ( xj 】，) m i ns u pp o r t ，且c o n f i d e n c e ( xjy ) m i nc o n f i d e n c e ， 则称关联规则xjy 为强规则，否则就是弱规则。 找出数据集中的所有强规则是挖掘关联规则的目标，它由两个步骤组成： ( 1 ) 找出所有频繁项集。 ( 2 ) 由频繁项集产生关联规则。 关联规则挖掘算法的总体性能由第一步决定。 ( 2 2 ) 和( 2 3 ) 贝j j 是第二步的解决 方法。 1 2 5 关联规则的分类 我们将关联规则按照不同的情况分类： ( 1 ) 关联规则根据所处理的的属性的类型，分为布尔型关联规则和量化型关 联规则。布尔型关联规则，顾名思义，意思就是指所处理的数据值都是离散的，它 只体现了项的存在与否。关联规则( 买自行车的人- 2 1 2 人) 就是一个布尔型的；量 化型规则所描述的关系是存在于经过量化了的属性或项之间。在规则( 买自行车的 6 硕士学位论文、 m a s t e r st h e s l s 人收入 购买松下的数码相机，就比 2 0 岁的学生- 购买数码相机涉及到的概念层降低，我们将这样的规则叫做多层次关 联规则。 在对关联规则的分类进行了定义后，就可以先判断所挖掘的关联规则属于那个 类型，再选取相应的挖掘方法进行挖掘。 1 3 关联规则挖掘算法 1 3 1a p r i o r i 算法 a p r i o d 算法是一种最著名的关联规则挖掘算法，它是由a g r a w a l 等在1 9 9 3 年提 出的，主要用于在布尔型事物数据库中挖掘频繁项集间的关联。“逐层搜索”的方 法在算法中被迭代使用，根据已生成的频繁k 一项集产生( 七十1 ) 一项集。第一遍扫描 数据库首先计算出频繁1 项集的集合，记作：厶；然后执行下面的迭代运算计算出 频繁k 一项集，直到不能在找到频繁k 一项集集合： 1 连接：丘一。进行自连接运算，生成候选七一项集集合g 。所有的频繁后一项集都 包含在g 中。 2 剪枝：g 是丘的超集，也就是说g 中的成员可以是频繁的，也可以是不 频繁的。再扫描数据库，对q 中每个候选项集的支持度计数，只要是支持度大于用 户给定最小支持度阈值的候选k 一项集，就是频繁k 一项集。 经过这个迭代过程，就可以找到在给定数据库d 中满足最小支持度的所有频繁 项目集。 以下是a p r i o r i 算法相关过程的伪代码： 输入：事务数据库d ，最小支持度阈值m i ns u p l l = f i n d f r e q u e n t 一1 一i t e m s e t s ( d ) ； f o r ( k = 1 ，l k l ，k + + ) 7 硕士学位论文 m a s t e r st h e s i s c r = a p r i o r i g e n ( l k l ，m i n _ s u p ) ； f o re v e r yt r a n s a c t i o nf d c = s u b s e t s ( c k ，f ) ； f o r e v e r yc a n d i d a t ec c t c 7 0 u r l t + + ； l i = c c i l c c o u n t m i n _ s u p ， r e t u r n l = u 置l r ； p r o c c s sa p r i o r i _ g e n ( l r l ：f r e q u e n t ( k - 1 ) - i t e m s e t s ；r a i n _ s u p ) f o re v e r yi t e m s e t i i l t - l f o re v e r yi t e m s e t 1 2 l k _ l i f ( 1 l 【1 】= 【l d 八“【2 】= j 。b a 八“k 一1 】= ，陆一2 d 八( 1 1 陆一1 】：，。陆一1 d t h e n c = ，l q 1 2 ；连接步：产生候选集 i fh a s _ i n f r e q u e n t _ s u b s e t ( c ，三h ) t h e n d e l e t ec ；剪枝步：去除无效的候选集 e l s ea d dc t o c r ； r e t u r nc r ； p r o c c s sh a s _ i n f r c q u c n t _ s u b s c t ( c ；k i t e m s e t ；l k l ：) f o re v e r y 体一1 ) _ s u b s c tso f c i f s 正l k l t h e n r e t u r nt u r c ；e l s e r e t u r nf a l s e a p r i o r i _ g c n 函数执行两个动作，首先在连接步把k 一。自相连接以获得候选超集 c x 。然后在修剪步，如果c 的一些( 七一1 ) 一项集不在l k - 中，则删除这个项目集 c q 。 8 硕士学位论文 m a s t e r st h e s i s 1 3 2f p g r o w t h 算法 后来有不少学者对a 研o r i 算法进行了时间上或空间上的侥化， 缺陷还是无法克服： ( 1 ) 也许导致很大数目的候选项集。假设有1 0 4 个频繁1 项集， 能产生的候选2 项集几乎会达到1 0 7 个。 但其一些固有的 利用这种算法可 ( 2 ) 可能需要重复的扫描数据库，以模式匹配的方法检查候选项集。 以上的缺点导致了在a p r i o r i 以及相关算法在某些情况下的效率低下。针对这些 问题，j h a n 提出了一种算法f p g r o w t h 2 2 ，这种算法可以避免了大量的候选项集 的产生。基本思想是：先把数据库中的事务压缩进一棵频繁模式树，每个事务在树 中有一个分支与之对应，分支的节点用于保留项间的关联信息。随后再将f p t r e e 上 的初始后缀模式构造条件模式基，然后构造条件模式基的f p t r e e ，在递归的对这个数 进行挖掘。 无论是挖掘长的频繁模式，还是短的频繁模式，f p g r o w t h 都是有效的，它的基 本思想就是，把长的频繁模式的挖掘过程转换为递归的挖掘一些短的模式，它在速 度上比a p r i o r i 算法快一个数量级。 1 3 3 多层关联规则的挖掘 通常情况下，藏匿在某些属性或项里的概念之间是遵循一定的层次结构的。由 于种种原因，人们不容易在较低层或原始层上发现令人感兴趣的信息，但这并不代 表在低层就没有有趣信息的存在。有时候，位于同层的项之间可能难以发现有趣信 息，但是跨层次的项之间却可能有些有趣信息可以被挖掘。所以在研究对多层关联 规则挖掘的时候，既应该涉及到处于同一概念层上的关联规则的挖掘，还应该涉及 到位于不同概念层上的跨层次关联规则的挖掘 7 】。 多层关联规则挖掘算法一般采用的是逐层深入的方法，由顶向下进行挖掘。每 一层上的规则挖掘采用的仍然是a p r i o r i 算法思想。m l t 2 l 1 8 】算法和c u m u l a t e 9 】 算法是两个比较常用的多层关联规则挖掘的算法。但是m l t 2 l 1 算法不能挖掘跨 层次的关联规则。c u m u l a t e 算法可以挖掘跨层次的关联规则，但是它没有考虑待挖 掘数据在概念层上的结构；“支持度一置信度”是多层关联规则挖掘中采用的的框 架，最小支持度随着挖掘中涉及到的层数的降低而递减，最低层的最小支持数也最 小；但这类算法中仍然无法避免a p r i o r i 存在的两大缺点，即需要把每个频繁项目集 都列举，就会产生大量的候选项目集，同时在计算候选项集中子集的支持数时，需 要不停的扫描数据库。f p g r o w t h 算法避免了大量候选项目集的产生，所以不少研究 9 硕士学位论文 m a s t e r st h e s i s 人员提出了f p g r o w t h 算法为基础的多层关联规则挖掘算法。如文献 7 】中引入修补项 的概念来计算跨层次频繁项集的支持数。文献【1 0 】采用区间支持度的概念来计算跨 层次频繁项集的支持数。这两种方法都是对f p g r o w t h 的改进。 概念分层的结构在数据挖掘中有一定的作用，因为它使在不同的概念层发现有 趣信息成为了可能。然而由于项之间可能存在的“祖先子孙”关系，当涉及到 跨层次的关联规则时，会出现冗余情况。所以，本文研究内容之一就是，在生成跨 层次的候选项集时如何避免冗余的关联规则。这些内容将在下一章具体描述。 1 4 国内外研究现状 到目前为止，国外的许多研究工作都集中在以下几个方面，一是数据挖掘过 程中的可视化方法，二是如何规范挖掘语言的标准和数据挖掘系统规范，这些研究 都取得了丰硕的成果，有不少产品已经投入了使用。文献 6 】中介绍了当前一些主流 的可视化数据挖掘系统，其中s a sc n t e r pr i s c m i n e r 、s p s sc l e m e n t i n e ，i b m i n t e l l i g e n tm i n e r 、t e r a d a t aw a r c h o u s em i n e r 笔b 都是比较具有影响力的。 国内的一些研究单位和高校也开展了可视化数据挖掘的理论研究和应用研究， 也取得了一定成果，但与国外先进技术还是存在质量和数量上的差距。目前，国内 的研究成果主要有，复旦大学的朱扬勇等人开发的d m c a 信用卡智能分析平 台、c d m i n c r _ 银行客户分析系统、c i a s 客户智能分析平台、c c m i i l e r 电子商务系统以及a i t m i n e 广关联规则挖掘工具，还有中科院的m s m i r l e r 多 策略数据挖掘平台，这些产品目前在通信、商业和金融业等领域得到广泛应用。就 目前国内可视化数据挖掘的研究情况看，对可视化数据挖掘的技术创新，开发高性 能的、具有自主产权的可视化数据挖掘应用平台，对推动我国可视化数据挖掘技术 的理论进步和应用的推广都具有非常重要的意义。 上面列举的都是国内外比较成熟的可视化挖掘系统，这些系统里面可以对关联 规则进行可视化。还有一些专门用于关联规则可视化挖掘的系统，如a r m i n e r 、 x m d v t o o l 1 1 】、v i s a r 1 2 】、a r v i r 1 3 】r u l e v i z 、c f i s t a l c l e a r 。现阶段用于关联 规则的可视化技术有：关联规则表、规则多边形、二维矩阵、平行坐标、有向图。 这些关联规则可视化技术普遍存在一下不足： ( 1 ) 只能以二维的方式来展示挖掘结果； ( 2 ) 多维关联规则的描绘仍然是个难题； ( 3 ) 当有较多数量关联规则时，会产生歧义以及可视化界面紊乱的问题； ( 4 ) 没有清楚地标注关联规则的支持度和置信度等参数； 1 0 ：一， 硕士学位论文 m a s t e r st h e s i s 关联规则挖掘一直是数据挖掘中的研究热点。目前，对关联规则的研究主要集 中在以下两方面： 如何开发更高效的挖掘算法。由于数据挖掘的对象是海量的数据，因此，提高 算法效率，如何减少算法在时间和空间上的复杂度是基本问题。另外，由于待挖掘 的数据对象的类型是复杂的，在挖掘过程中有许多问题都需要改进原有算法或者提 出新算法来解决。本文的研究内容之一就是针对多层关联规则中的冗余问题进行研 究。 另一方面，如何实现关联规则的可视化挖掘。目前国内对于提供关联规则可视 化的方法的文献不多。在本文中，作者将对目前适用于关联规则表示的可视化技术 进行总结，对它们的优点与缺点进行分析，并在前面研究人员提出的适用于关联规 则可视化的基础上，设计一个简洁的可视化界面，用户可以与系统进行交互。 1 5 本文研究内容 本论文的目标在于对关联规则的挖掘算法和可视化技术进行研究，设计实现一 个可视化的关联规则挖掘工具。针对这个目标，论文中将要完成如下的工作： 1 分析比较了目前的关联规则算法，提出了一种冗余删除方法，改进基于修 补项的挖掘算法，减少冗余规则的产生，提高挖掘的有效率。 2 总结现有的用于关联规则的可视化技术，讨论了现有的可视化技术在表示 关联规则时的不足。 本文结构安排如下： 第1 章为引言部分。主要介绍研究的背景及意义，详细阐述了数据挖掘的基本 概念、主要方法，以及数据挖掘中的一个重要问题关联规则的相关概念与相关 算法。然后分析了国内外关于可视化数据挖掘的发展动态与成果，并确定了研究的 内容。 第2 章首先讨论多层关联规则尤其是跨层次规则的挖掘算法，特别针对跨层次 关联规则的冗余问题进行研究，设计出一种冗余删除算法加入到挖掘算法中，以优 化挖掘结果，剔除冗余，提高挖掘的有效性。 第3 章对数据挖掘的可视化技术进行总结，介绍目前比较成熟的适用于关联规 则挖掘的可视化技术。接着分析了这些方法的有点与不足，介绍一些研究人员针对 这些不足之处提出克服的方法。 第4 可视化关联规则挖掘系统的系统设计和各个模块的实现。 第5 章是全文的总结部分，并对未来的工作进行展望 硕士学位论文 m a s t e r st h e s i s 2 多层关联规则挖掘算法中的冗余问题 2 1 引言 基于支持度和置信度的框架一般会产生的大量的无用关联规则，降低挖掘算法 的有效率。因此，必须对挖掘到的关联规则进行冗余判断处理，去掉冗余的规则。 目前已有一些解决冗余的办法，比如冗余的删除规贝t j l 9 、规则集1 2 0 1 的概念、文献 【2 1 贝j j 是引入了一个参数兴趣度，以这个作为规则有效性的衡量参数。 2 2 多层关联规则的概念 2 2 1 什么是概念分层 概念分层 1 4 】被用于多层关联规则的挖掘中。概念树是一种概念层次结构的表 示方式。每个概念在概念树中都有一个节点来对应，以数字来表示概念树的层数， 0 是根节点的层数，以下节点的层数逐渐加一。在概念树的结构中，越高的层次对 应的层数越大，越低的层次对应的层数较大。例如在 2 3 】给出的一个概念树的例子 o 层a l i 1 层c o u n t r y 2 层s t a t e 3 层c i t y 图2 1 维l o c a t i o n 的一个概念分层 该概念树6 1 4 层组成。根节点a l l 为0 层，层1 表示概念c o u n t r y ，层2 和层3 分别表示 概念s t a t e 和c i t y 。概念分层的叶子节点对应于原始数据值( 原始层数据) 。这些是给 定属性或维的最细节的值或概念。 1 2 硕士学位论文 m a s t e r st h e s i s 2 2 2 什么是多层关联规则 在第二章中关于关联规则分类的内容中介绍了多层关联规则，根据所涉及的抽 象层概念，有些挖掘的关联规则的属性属于不同的概念层。假设挖掘的关联规则有： a g e ( x , 2 0 4 9 ”) _ b u y s ( x , l a p t o p c o m p u t e r ”) ( 2 一1 ) a g e ( x , 2 0 4 9 ”) - b u y s ( x , c o m p u t e r ”) ( 2 - 2 ) 在规则( 3 1 ) 和( 3 - 2 ) 中涉及到不同的概念层( 因为“c o m p u 纪r ”比 “i a p t o p c o m p u t e r ”所处的概念层更高) ，我们将这样的关联规则称为多层关联规则。 而如果在挖掘到的关联规则集合中，每个规则都没有涉及不同概念层的项，这样的 规则称为单层关联规则。 如果一个规则的所有项不是处于同一概念层，例如【2 3 】中的一个例子， c o m p u 纪r _ b w p r i n t e r ( 2 3 ) 在这个规则中c o m p u 胞r 与p r i n t e r 是处于同一概念层，而b w p r i n t e r 则是比 p r i n t e r 更低的概念层，所以规贝j j ( 2 3 ) 称作一个交叉层关联规则或者跨层次关联规 则( c r o s s 1 e v e la s s o c i a t i o nr u l e ) 。频繁项集中的项目中，如果至少有2 个项目在概 念树中的父节点不同，且它们所在的层次也不相同，这样的频繁项集称为跨层次频 繁项集。 2 2 3 多层关联规则的挖掘方法 在第一章中介绍到，经典的多层关联挖掘算法采用的是自顶向下的策略。从鬼 高概念层1 开始向下，累加的计数每个概念层的频繁项集的支持数，直到找不到更 多的频繁项集。对于同一概念层上的频繁项集的发现，无论使用哪种发现频繁项集 的算法都可以，如a p r i o r i 及其变形算法、f p g r o w t h 算法。对于每层最小支持度的设 置，有如下的情况： ( 1 ) 一致支持度：即对于每一概念层的关联规则挖掘时，使用的最小支持度都 是相同的。由于阈值的一致，使得这种搜索过程相对变得不是那么复杂。由于祖先 项集是其子孙项集的超集，所以如果有的项集的祖先就不是频繁项集的话，那么这 样的项集可以不予考察。 ( 2 ) 支持度递减：给每个概念层设置一个最小支持度阈值。层次越低，对应的 最小支持度阈值越低。对于这种挖掘方法，有以下三种频繁项集的考察方法，分别 是： 逐层独立无论一个节点的父节点是否频繁，这个节点都要被考察。 硕士学位论文 m a s t e r st h e s i s 层交叉单项过滤如果一个父节点是频繁的，它的子女将被考察，否则， 它的子孙被剪枝。 层交叉k 项集过滤如果一个父节点k 项集是频繁的，那么它子女的k - 项集 将被考察。 ( 3 ) 在跨层次的关联规则挖掘中，如果事挖掘由层i 到层j ( i i ) 的频繁项集时， 则应当较低层i 层的最小支持度阈值。 2 2 4 跨层次关联规则的挖掘算法 在发现处于同一抽象层的频繁项集时，无论采用哪种发现频繁项集的算法都可 以，例如a p f i o f i 以 ) 它的改进算