（计算机应用技术专业论文）基于分布式概念格的序列模式发现研究.pdf

基于分布式概念格的序列模式发现研究 摘要 知识发现和数据挖掘是人工智能、机器学习、数据库和统计理论等相结合而形 成的新的研究与应用领域，序列模式发现是数据挖掘的一个重要分支，具有广阔的 应用前景。随着信息技术日新月异的发展和应用，从更大规模数据中高效地提取序 列模式已经成为一挑战。本文将具有坚实的理论基础、完备的结构以及并行性特征 的概念格模型引入到序列模式挖掘中，以实现当前大规模分布式数据的序列模式挖 掘。 主要工作如下： ( 1 ) 概述了知识发现和数据挖掘的研究动态，相关的数据挖掘技术及应用，以 及几种典型模式发现问题。 ( 2 ) 分析了a p r i o r i a l l 算法、g s p 算法和p r e f i x s p a n 算法等几种经典序列模 式挖掘算法，并做了必要的比较。介绍了概念格的模型以及基于概念格的序列模式 的数据挖掘研究成果和性能。 ( 3 ) 针对当前的数据库的大规模现象，基于子全概念的概念格构造算法s e a ， 提出一种新的基于分布式概念格的序列模式挖掘算法，以实现大规模数据的频繁序 列模式挖掘。 ( 4 ) 针对序列模式的可信度的评价展开研究，提出了挖掘满足支持度条件的 有高可信度的序列模式的算法。研究了先清理( 取高可信度) 数据库再挖掘满足高 支持度的序列模式，以及先挖掘满足高支持度的序列模式，再清理两种不同方式， 结果表明第一种方式效率高。 关键词；数据库知识发现；序列模式；概念格；分布式；可信度 r e s e a r c ho ns e q u e n t i a lp a t t e r n sm i n i n g b a s e do nd i s t r i b u t e dc o n c e p tl a t t i c e s a b s t r a c t a st h er e s u l to f a r t i f i c i a li n t e l l i g e n c e ，m a c h i n el e a r n i n g ，d a t a b a s e sa n ds t a t i s t i c sa n d o t h e rs u b j e c t s ，t h ea i mo fd a t am i n i n ga n dk d di st of i n dm e a n i n g f u lp a t t e r n sf r o m d a t a b a s e s s oi ti so fg r e a tv a l u e s e q u e n t i a lp a t t e r nm i i l i n gi so n eb r a n c ho fd a t am i n i n g w i t ht h eq u i c k l yd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , m i n i n gm e a n i n g f u lp a r e n t s e f f e c t i v e l yf r o ml a r g ed a t a b a s e sh a v eb e c o m eac h a l l e n g e a ne f f e c t i v ew a yt os o l v et h e p r o b l e mi sp a r a l l do rd i s t r i b u t e dt e c h n o l o g y d u i n gt os t a b i l i t yt h e o r yb a s ea n dc o m p l e t e s t r u c t u r ea n dp a r a l l e lc h a r a c t e r i s t i c ，c o n c e p tl a t t i c ei sa ni m p o r t a n tt o o lt ok n o w l e d g e i n t h i sd i s s e r t a t i o n , t h em o d e lo fd i s t r i b u t e dc o n c e p tl a t t i c ea n dd a t am i m n gr e s e a r c ho nw h i c h i ss t u d i e d t h e m a i nc o n t e x ti sa sf o l l o w s 1 t h er e s e a r c ht r e n d sa n dt h e a p p l i c a t i o no f t h ed a t am i n i n ga n dk d d i si n t r o d u c e d 2 t h ec l a s s i c a ls e q u e n t i a lp a t t e r n sm i i l i n ga l g o r i t h m ss u c ha sa p r i o r i a l l ，g s pa n d p r e f i x s p a na l ed i s c u s s e da n dc o m p a r e d t h es e q u e n t i a lp a t t e r nm i n i n gb a s e do i l c o n c e p tl a t t i c ea r ed e s c r i b e d 3 an e w a l g o r i t h mo fs e q u e n t i a lp a t t e r n sb a s e do nd i s t r i b u t e dc o n c e p tl a t t i c ea n d s e aa r ep r o p o s e d a l lt h e s ea r eb u i l to nl a r g e rd a t a b a s e sa n ds e at os o l v et h e p r o b l e mo fs e q u e n t i a lp a t t e r n sm i n i n gf o rl a r g e rd a t a b a s e s 4 r e s e a r c ho nt h ec e r t a i n t yo fs e q u e n t i a lp a t t e r n sm i n i n g a na l g o r i t h mo fs e q u e n t i a l p a t t e r n sb a s e do nh j l g hc e r t a i n t ya r ep r o p o s e d t h et w od i f f e r e n tm e t h o d sw a s s t u d i e d ，t h eo n ei ss e q u e n t i a lp a t t e r n sm i n i n gb e f o r ec e r t a i n t yu s e d ，t h eo t h e ro n ei s s e q u e n t i a lp a t t e r n sm i n i n gb e f o r ec e r t a i n t yu s e d t h er e s u l ti st h a tt h ef i r s to n e s e f f i c i e n c yw a sh i g h k e y w o r d s ：k d d ；s e q u e n t i a lp a t t e r n ；c o n c e p tl a t t i c e ；d i s t r i b u t e d ；c c n a i n t y 插图清单 图2 i 对应表2 9 的序列格的h a s s e 图 图3 1 根据子全概念生成的子格 图3 2 由子格l l 、l 2 、l 3 合成的完整格l 表格清单 表2 1 部分交易库数据8 表2 2 排序后的数据库9 表2 3 频繁项集及映射9 表2 4 转换后的数据库( 客户序列) 9 表2 5 客户序列1 0 表2 6 不同序列的支持度1 0 表2 7 最大的频繁序列1 0 表2 8 交易库数据d 1 7 表2 9 对应于d 的形式背景1 8 表4 1 客户交易库( 已按客户号和交易时间排序) 3 0 表4 2 表4 1 对应的客户序列数据库3 0 协拍” 一 | | 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得金型王些太堂 或其他教育机构的学位或证书而使用过的材料与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字：互扛钐咚签字日期：2 7 年，胡。日 学位论文版权使用授权书 本学位论文作者完全了解佥壁王些太堂有关保留，使用学位论文的规定，有权保留并向 国家有关部fj 或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权盒日b 王些左 兰二一可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：互扛锄 导师签名： 签字日期：2 0 0 7 年，月o 日 签字日 学位论文作者毕业厉去向： 工作单位； 通讯地址： 电话： 邮编： 瑚罗日 ( 致谢 值此论文完成之际，谨向我的导师胡学钢教授表示最真挚的谢意! 在硕士学位论 文撰写的过程中，自始至终得到了导师的悉心指导，无论从课程学习、论文选题，还 是到收集资料、论文成稿，都倾注了导师的心血。胡老师渊博精深的学识，严谨求实 的科研态度，宽以待人严于律己的学者作风，使我受益菲浅，并激励我勇往直前。 同时，感谢王浩、郭骏、沈明玉、周国祥等老师，在他们的教导下，我完成了研 究生课程，我还要感谢张玉红、吴共庆、张晶等老师，与他们的交流，丰富了我的知 识，给了我有益的启示。感谢合肥工业大学人工智能与数据挖掘研究室对我的关怀和 帮助。 向合肥工业大学研究生部及计算机与信息学院的院系领导、老师付出的辛勤工作 表示忠心感谢。 最后，也要感谢我的家人，正是他们给予我的大力支持与一如既往的鼓励，使我 得以顺利完成学业。 作者：王红侠 2 0 0 7 年9 月1 6 日 第一章绪论 随着计算机、网络技术的发展，获得有关资料已经非常简单易行。但是对 于数量大、涉及面宽的数据，依靠以往那种由简单汇总、按指定模式去分析的 统计方法是无法完成这类数据的分析的。从拥有大量数据库中发现知识 ( 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 s ，文献【l 】简称k d d ) ，是一个新兴的然而又 十分迷人和富有广泛应用前景的将人工智能技术与数据库理论相融合的研究领 域。因此，一种智能化的、综合应用各种统计分析、数据库、智能语言来分析 庞大数据资料的技术就应运而生，这就是目前国际上统计最热门的话题“数据挖 掘”( d a t am i n i n g 1 】，d m ) 技术的市场需求和它的技术支持背景。本章对k d d 和数据挖掘技术进行了较全面的回顾，介绍了k d d 的产生、发展和研究现状， 并提出了全文的研究内容和组织结构。 1 1k d d 与数据挖掘的产生和发展 数据挖掘与知识发现是一个以数据库、人工智能、数理统计、可视化四大 支柱技术为基础，多学科交叉、渗透、融合形成的新的交叉学科。 近十几年来，随着科学技术飞速的发展，经济和社会都取得了极大的进步， 与此同时在各个领域产生了大量的数据，如人类对太空的探索，银行每天的巨 额交易数据。在这些具有丰富信息数据中，如何处理这些数据，得到有益的信 息，人们进行了大量的探索。数据库中存储的大量数据和从数据库中发现知识 是两个完全不同的概念，计算机技术的迅速发展使得处理数据成为可能，这就 推动了数据库技术的极大发展，但是面对不断如潮水般增加的数据，人们不再 满足于数据库的查询功能，而提出了更深层次问题：如能不能从数据中提取信 息或者知识为决策服务。就数据库技术而言已经显得无能为力了，同样，传统 的统计技术也面临了极大的挑战，这就急需有新的方法来处理这些海量般的数 据。于是，人们结合统计学、数据库、机器学习等技术，提出数据挖掘来解决 这一难题。 k d d 一词是在1 9 8 9 年于美国底特律市召开的第十一届国际人工智能联合 会议上首次提出的，这届学术会议上举行了以k d d 为主题的学术讨论，随后 相继在1 9 9 1 年、1 9 9 3 年、1 9 9 4 年举行了k d d 的专题讨论会。以后每年都召 开国际及亚太地区的k d d 会议。目前，i j c a i 、a a a i 、v l d b 等代表人工智能 与数据库技术研究最高水平的国际学术会议上，和k n o w l e d g ea n d i n f o r m a t i o n s y s t e m s ，i e e ec o n c u r r e n c y 等著名杂志对k d d 的研究都占有较大的比例。k d d 已经成为当今计算机科学与技术领域研究、应用的热点领域之一。随着k d d 在国际上的兴起，我国也积极地开展了相应的研究和应用。目前国内许多学术 会议，如数据库学术会议、机器学术会议等，也都将k d d 列为重要的研究方 向。 随着对k d d 的深入研究以及k d d 在许多领域广泛而成功的应用，众多的 学者根据自己对k d d 的认识和理解，给出了很多定义，而其中被公认为比较 完整、深刻和全面的是由f r a w l e y 和f a y y a d 1 】【2 1 分别在1 9 9 1 年和1 9 9 6 年的会 议论文中对k d d 的定义： “t h en o n t r i v i a le x t r a c t i o no fi m p l i c i t ，p r e v i o u s l yu n k n o w n ，a n dp o t e n t i a l l y u s e f u li n f o r n l a t i o nf r o md a t a ” “t h en o n t r i v i a lp r o c e s so fi d e n t i l y i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n d u l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a 即k d d 是从大量数据中提取出有效的、新颖的、有潜在作用的、可信的、 并能最终被人理解的模式的非平凡的处理过程。 数据挖掘的历史虽然较短，但从2 0 世纪9 0 年代以来，它的发展速度很快， 加之它是多学科综合的产物，目前还没有一个完整的定义，人们提出了多种数 据挖掘的定义，例如： s a s 研究所( 1 9 9 7 ) ：“在大量相关数据基础之上进行数据探索和建立相关 模型的先进方法”。 b h a v a n i ( 1 9 9 9 ) ：“使用模式识别技术、统计和数学技术，在大量的数据中 发现有意义的新关系、模式和趋势的过程”。 h a n de ta l ( 2 0 0 0 ) ：“数据挖掘就是在大型数据库中寻找有意义、有价值信 息的过程”。 目前较新的观点认为：数据挖掘就是从海量的数据中挖掘出可能有潜在价 值的信息的技术。这些信息是可能有潜在价值的，支持决策，可以为企业带来 利益，或者为科学研究寻找突破口。 一般认为，从实际数据到发现潜在知识的整个k d d 过程主要分为以下几 个步骤：数据准备，数据选择，数据预处理，数据转换，确定k d d 目标，确 定知识发现算法，数据挖掘，模式解释与评价，知识表示。 通常将k d d 中进行知识发现的阶段称作数据挖掘，目前关于k d d 的研究 大多着眼于对数据挖掘步骤的研究。某些应用领域对数据挖掘与k d d 不加区 分地使用，某种意义上二者可看作同一概念。 1 2 数据挖掘技术及其应用现状 现今资料流通量之巨大已到了令人咂舌地步，就实际限制而言，便遇到了 诸如巨量的纪录，高维的资料增加的传统分析技术上的困难，搜集到的资料仅 有5 至1 0 用来分析，以及资料搜集过程中并不探讨特性等问题，这就让我 们不得不利用d a t am i n i n g 技术。 2 数据挖掘综合了各个学科技术，有很多的功能，当前的主要功能如下： ( 1 ) 分类：按照分析对象的属性、特征，建立不同的组类来描述事物。例 如：银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据这些 来区分新申请贷款的客户，以采取相应的贷款方案。 ( 2 ) 聚类：识别出分析对内在的规则，按照这些规则把对象分成若干类 例如：将申请人分为高度风险申请者，中度风险申请者，低度风险申请者 ( 3 ) 关联规则和序列模式的发现：关联是某种事物发生时其他事物会发生 的这样一种联系。例如：每天购买啤酒的人也有可能购买香烟，比重有多大， 可以通过关联的支持度和可信度来描述。与关联不同，序列是一种纵向的联系。 例如：今天银行调整利率，明天股市的变化。 ( 4 ) 预测：把握分析对象发展的规律，对未来的趋势做出预见。例如：对 未来经济发展的判断。 ( 5 ) 偏差的检测：对分析对象的少数的、极端的特例的描述，揭示内在的 原因。例如：在银行的1 0 0 万笔交易中有5 0 0 例的欺诈行为，银行为了稳健经 营，就要发现这5 0 0 例的内在因素，减小以后经营的风险。 需要注意的是：数据挖掘的各项功能不是独立存在的，在数据挖掘中互相 联系，发挥作用。 作为一门处理数据的新兴技术，数据挖掘有许多的新特征。首先，数据挖 掘面对的是海量的数据，这也是数据挖掘产生的原因。其次，数据可能是不完 全的、有噪声的、随机的，有复杂的数据结构，维数大。最后，数据挖掘是许 多学科的交叉，运用了统计学，计算机，数学等学科的技术。以下是常见和应 用最广泛的算法和模型： ( 1 ) 传统统计方法：抽样技术：我们面对的是大量的数据，对所有的数 据进行分析是不可能的也是没有必要的，这就要在理论的指导下进行合理的抽 样。多元统计分析：因子分析，聚类分析等。统计预测方法，如回归分 析，时间序列分析等。 ( 2 ) 可视化技术：用图表等方式把数据特征直观地表述出来，如直方图等， 这其中运用了许多描述统计的方法。可视化技术面对的一个难题是高维数据的 可视化。 ( 3 ) 决策树：利用一系列规则划分，建立树状图，可用于分类和预测。常 用的算法有c a r t 、c h a i d 、i d 3 、c 4 5 、c 5 0 等。 ( 4 ) 神经网络：模拟人的神经元功能，经过输入层，隐藏层，输出层等， 对数据进行调整，计算，最后得到结果，用于分类和回归。 ( 5 ) 遗传算法：基于自然进化理论，模拟基因联合、突变、选择等过程的 一种优化技术。 ( 6 ) 关联规则挖掘算法：关联规则是描述数据之间存在关系的规则，形式 为“a 1 a a 2 a a n b 1 a b 2 a b n ”。一般分为两个步骤：求出大数据项集。 用大数据项集产生关联规则。 除了上述的常用方法外，还有粗集方法，模糊集合方法，b a y e s i a nb e l i e f n e t w o r k ，最邻近算法( k n e a r e s tn e i g h b o r sm e t h o d ( k n n ) ) 等。 1 3 数据挖掘的实施步骤和应用现状 数据挖掘的一般实施步骤如下： 问题理解和提出；数据准备；数据整理；建立模型；评价和解释。 ( 1 ) 问题理解和提出：在开始数据挖掘之前最基础的就是理解数据和实际 的业务问题，在这个基础之上提出问题，对目标有明确的定义。 ( 2 ) 数据准备：获取原始的数据，并从中抽取一定数量的子集，建立目标 数据库，其中一个问题是如果企业原来的数据仓库满足数据挖掘的要求，就可 以将数据仓库作为数据挖掘库。 ( 3 ) 数据整理：由于数据可能是不完全的、有噪声的、随机的，有复杂的 数据结构，就要对数据进行初步的整理，清洗不完全的数据，做初步的描述分 析，选择与数据挖掘有关的变量，或者转变变量。 ( 4 ) 建立模型：根据数据挖掘的目标和数据的特征，选择合适的模型。 ( 5 ) 评价和解释：对数据挖掘的结果进行评价，选择最优的模型，作出评 价，运用于实际问题，并且要和专业知识结合，对结果进行解释。 以上的步骤不是一次完成的，可能其中某些步骤或者全部要反复进行。 数据挖掘所要处理的问题，就是在庞大的数据库中找出有价值的隐藏事件， 并且加以分析，获取有意义的信息，归纳出有用的结构，作为企业进行决策的 依据。其应用非常广泛，只要该产业有分析价值与需求的数据库，皆可利用 m i n i n g 工具进行有目的的发掘分析。常见的应用案例多发生在零售业、制造业、 财务金融保险、通讯及医疗服务： ( 1 ) 商家从顾客购买商品中发现购买模式，采取相应的措施，提高销售额。 ( 2 ) 保险公司通过数据挖掘建立预测模型，辨别出可能的欺诈行为，避免道 德风险，减少成本，提高利润。 ( 3 1 在制造业中，半导体的生产和测试中都产生大量的数据，通过对这些数 据进行分析，找出存在的问题，提高质量。 ( 4 ) 电子商务的作用越来越大，可以用数据挖掘对网站进行分析，识别用户 的行为模式，保留客户，提供个性化服务，优化网站设计。 一些公司运用数据挖掘的成功案例，显示了数据挖掘的强大生命力： 美国a u t o t r a d e r t o n i 是世界上最大的汽车销售站点，每天都会有大量的用 户对网站上的信息点击，寻求信息，其运用了s a s 软件进行数据挖掘，每天对 数据进行分析，找出用户的访问模式，对产品的喜欢程度进行判断，并设特定 4 一 服务区，取得了成功。 r e u t e r e s 是世界著名的金融信息服务公司，其利用的数据大都是外部的数 据，这样数据的质量就是公司生存的关键所在，必须从数据中检测出错误的成 分。r e u t e r e s 用s p s s 的数据挖掘工具s p s s c l e m e n t i n e ，建立数据挖掘模型， 极大地提高了错误的检测，保证了信息的正确和权威性。 b a s se x p o r t 是世界最大的啤酒进出口商之一，在海外8 0 多个市场从事交 易，每个星期传送2 3 0 0 0 份定单，这就需要了解每个客户的习惯，如品牌的喜 好等，b a s s e x p o r t 用i b m 的i n t e l l i g e n t m i n e r 很好的解决了上述问题。 1 4 数据挖掘的发展和面临的挑战 数据挖掘的发展已经经历了多个发展阶段，朱建秋【”提出将数据挖掘系统 从技术角度划分为四代，从发展观点经历三个阶段的论断，从而归纳出数据挖 掘系统与应用相结合的趋势，提出数据挖掘应用平台的概念。构建了一种新颖 的数据挖掘体系结构，将数据挖掘划分成数据层、算法层、业务逻辑层、行业 表示层五个层次。改进和优化了部分数据挖掘算法，提高了算法的性能和适用 范围。提出了带负属性的关联规则算法和带时间特征的序列模式算法t e s p 。 尽管数据挖掘有如此多的优点，但数据挖掘也面临着许多的问题，这也为 数据挖掘的未来的发展提供了更大的空间。 ( 1 ) 数据挖掘的基本问题就在于数据的数量和维数，数据结构也因此显的 非常复杂，如何进行探索，选择分析变量，也就成为首先要解决的问题。 ( 2 ) 面对如此大的数据，现有的统计方法等都遇到了问题，我们直接的想 法就是对数据进行抽样，那么怎么抽样，抽取多大的样本，又怎样评价抽样的 效果，这些都是值得研究的难题。 ( 3 ) 既然数据是海量的，那么数据中就会隐含一定的变化趋势，在数据挖 掘中也要对这个趋势做应有的考虑和评价。 ( 4 ) 各种不同的模型如何应用，其效果如何评价。不同的人对同样的数据 进行挖掘，可能产生不同的结果，甚至差异很大，这就涉及到可靠性的问题。 ( 5 ) 当前互联网的发展迅速，如何进行互联网的的数据挖掘，还有文本等 非标准数据的挖掘，都引起了极大的兴趣。 ( 6 ) 数据挖掘涉及到数据也就碰到了数据的私有性和安全性。 ( 7 ) 数据挖掘的结果是不确定的，要和专业知识相结合才能对其做出判断。 总之，数据挖掘可以发现一些潜在的用户，但是不会告诉你为什么，也不 能保证这些潜在的用户成为现实。数据挖掘的成功要求对期望解决问题的领域 有深刻的了解，理解数据，了解其过程，才能对数据挖掘的结果找出合理的解 释。例如曾经用数据挖掘找出的啤酒和尿布的例子，如何去解释这种现象，是 应该将两者放在一起还是分开销售，这还需要对消费心理学有所研究才能做出 决定，而不是数据挖掘能力所及的了。 1 5 本文的研究内容及安排 随着信息技术日新月异的发展和应用，从更大规模数据中高效地提取有用 模式已经成为一挑战。数据挖掘要求有更好的时间和空间性能。为此，本文将 具有坚实的理论基础、完备的结构以及并行性特征的概念格模型，引入到序列 模式挖掘中，以实现当前大规模分布式数据的序列模式挖掘。内容组织如下： 第一章是绪论，主要概述了知识发现产生的背景，数据挖掘的功能、方法、 工具、实施步骤、应用现状、面临挑战等，概述了知识发现和数据挖掘的诞生、 发展，介绍数据挖掘技术及其应用现状，以及几种模式发现的简介和比较。 最后简要给出文章的组织结构。 第二章主要分析和比较了a p r i o r i a l l 算法、g s p 算法、p r e f i x s p a n 算法等几 种经典序列模式的挖掘算法。 第三章介绍了概念格的模型以及基于概念格的序列模式的数据挖掘研究成 果和性能。 第四章针对当前的数据库的大规模现象，基于子全概念相关概念格构造算 法s e a ，提出一种新的基于分布式概念格的序列模式挖掘的算法思想d c m s p ( d i s t r i b u t e dc o n c e p tm i n i n go fs e q u e n t i a lp a t t e r n s ) ，实现大规模数据的频繁序列 模式挖掘。 第五章针对序列模式的可信度的评价展开研究，提出了在满足支持度的条 件下又有高可信度的序列模式的挖掘算法。研究了先清理( 取高可信度) 数据 库再挖掘满足高支持度的序列模式，以及先挖掘满足高支持度的序列模式，再 清理两种不同方式，结果表明前者效率高。 第二章基于概念格的序列模式挖掘 本章首先介绍序列模式和概念格的基本概念，然后讨论基于概念格的序列 模式的挖掘算法。传统的序列模式发现算法( 如a p r i o r i a l l 算法，g s p 算法等) 在序列模式挖掘时需要多遍扫描( m u l t i p l e p a s s ) 的候选子序列产生和测试方法， 可能产生大量候选序列，因而时间开销较大。概念格适用于挖掘包括序列模式 在内的各种知识。依据序列模式发现的特点和阈值，对概念格进行剪枝而得到 频繁概念格，运用概念格挖掘序列模式的过程仅需扫描数据库一次，因而具有 一定的优越性。 2 1 序列模式及其发现 序列模式的概念最早是由a g r a w a l 和s r i k a n t 4 】提出的：给定一个序列集， 其中每一个序列由项集构成，序列模式挖掘就是去发现所有的频繁子序列( e p ： 这些子序列的出现频率不小于给定的最小支持度) 。 已有的序列模式的发现算法基本上可以分为两大类。第一类是基于a p r i o r i 特性的、逐层( 1 e v e l w i s e ) 的发现方法，包括a p r i o r i a l l 【6 】算法和g s p 【6 “1 算法 等。p s p 5 】算法是g s p 算法的改进。g s p 算法将候选序列组织在哈希树( h a s h t r e e ) 中，而p s p 算法将候选序列组织在前缀树( p r e f i x t r e e ) 中，因而提高了效率。 另一类方法由h a n 等人提出，称为基于序列模式增长( s e q u e n t i a lp a t t e r n s g r o w t h ) 方法，包括f r e e s p a n 8 1 ，p r e f i x s p a n 9 】算法等。这类方法采取了一种分 而治之( d i v i d e a n d c o n q u e r ) 的思想，挖掘过程中无需生成候选序列，而是以某 种压缩的形式保留了原数据库的基本的数据分组。随后的分析可以聚焦于计算 相关数据集而非候选序列的频率。算法的每一次迭代不是扫描完整的原数据库 来匹配相应的全部候选序列，而是通过数据库投影来对将要检查的数据集和序 列模式进行划分。这样分而治之的方法将减小搜索空间，提高算法性能。文献 1 0 1 1 提出了几种有效的序列模式维护算法，解决序列模式的增量式更新问 题。 挖掘序列模式是数据挖掘的一个重要范畴。对它的研究始于对货篮数据的 分析，其目的是为了从交易数据库中发现大多数顾客的序列购买行为。 在交易数据库d b 中，每个商品称为一个数据项( i t e m ，以下简称项) ，非空 集合i = i l ，i 2 ，i m ) 称为数据项集( i t e m s e t ，以下简称项集) ，其中每个i k ( 1 - k m ) 是一个项。长度为k 的项集称为k 项集。d b 中每个交易( t r a n s a c t i o n ) 由顾客号、 交易时间和该交易所购买的项集构成。不考虑顾客购买项的数量并假定同一时 间一位顾客只进行一次交易。 定义2 1 ：序列是不同项集的有序排列。i = i i ，i 2 ，i m ) 是项集，i k ( 1 k m ) 是一个项，序列s 记为s = ，其中s j ( 1 j n ) 为项集( 也称序列s 的元素) ，即s ；i 。每个元素由不同项组成。序列的元素可表示为( i l ，i 2 ，i k ) ， 若一个序列只有一个项，则括号可以省略。 序列包含的所有项的个数称为序列的长度。长度为三的序列记为一序列。 定义2 2 给定两个序列a = 和l = ，如果存在一组整 数i l i 2 i r a 使得a l c ：b i l ，a 2 c b i 2 ，a m c ：b i m ，则称序列a 被序列b 包含。 不包含在任何其它序列中的序列称为最大序列( m a x i m a ls e q u e n c e ) 。 若一个序列s 不包含在任何其他的序列之中，则称序列s 是最大的。 用于序列模式挖掘的交易数据库d 是由顾客序列组成的。顾客序列是顾客 的所有交易按交易时间升序的列表，以顾客标识符c i d 标识。顾客序列中的每个 交易有唯一的标识符t i d ，我们假设同一时间一位顾客只进行一次交易，所以可 以以交易时间作为t i d 。如果顾客序g d c 包含序列s ，我们称c 支持s ，s 在c 中的 位置定义为c 中包含s 中最后一个元素的交易标识符，以( c i d ，t i d ) 对表示。s 在c 中可能有多个位置，s 在所有顾客序列中的位置的集合的并组成了s 在d 中的位 置集合p ( s ) 。序列s 的支持度是支持s 的顾客数目。如果序列s 的支持度满足用户 定义的最小支持阈值( m i n s u p ) ，则称s 是一个频繁序列。序列s 的长度是序列中 项集的数量，长度为k 的频繁序列称频繁k 一序列。 给定交易数据库d ，序列模式挖掘的问题就是发现d 中所有大于最小支持 度的最大序列，每一个这样的最大序列代表了一个序列模式。 2 1 1a p r i o r i a l l 算法 a p r i o r i a l l 算法将序列的长度定义为序列中包含的项集的数量。算法将序 列模式发现的过程分为以下五个阶段：排序阶段、频繁项集阶段、变换阶段、 序列阶段、最大序列阶段。 表2 i 部分交易库数据 交易发生的时间客户购买项交易发生的时间客户购买项 标识标识 j u n e1 0 0 42a bj u n e2 5 0 43 c 。e ，g j u n e1 2 0 45hj u n e2 5 0 4l c j u n e1 5 0 42cj u n e3 0 0 4lh j u n e2 0 o g2 d ，f ，g j u n e3 0 0 44d g j u n e2 5 0 4 4 c j u l y2 5 0 4 4h 8 表2 2 排序后的数据库 客户标识交易时间购买项 1j u n e2 5 0 4c 1j u n e3 0 0 4h 2 j u n e1 0 0 4 a b 2j u n e1 5 0 4c 2j u n e2 0 0 4 d ，f g 3j u n e2 5 0 4c ，e ，g 4 j u n e2 5 0 4 c 4j u n e3 0 0 4d g 4 j u l y2 5 0 4 h 5 j u n e1 2 0 4 h 事例，某一交易库如表2 1 所示： 表2 3 频繁项集及映射 客户号客户序列频繁项集映射 l ( c ) 1 2 ( d ) 2 3 ( g ) 3 4 ( d ，g ) 4 5 ( h ) 5 频繁项集分别是( c ) 、( d ) 、( g ) 、( d ，g ) 和( h ) 表2 4 转换后的数据库( 客户序列) 客 由 标 原始客户序列 转换后客户序列映射后序列 识 1 2 3 4 ( c ) ( d ，g ) ( h ) 2 - 5 注：以下为了简便起见，序列中间逗号省略。 表2 5 客户序列 客户号 客户序列 1 15 2 3 4 p 2 3 4 5 表2 6 不同序列的支持度 l l ：l 2 ：l 3 1 序列支持度 4 2 4 4 4 2 一序列支持度 2 1 3 4 3 3 2 2 3 2 2 3 序列支持度 2 2 3 2 2 l 4 ： 4 序列支持度 2 l ( 1 ) 排序阶段： 客户标识及交易发生的时间为关键字所排序的数据库如表2 2 所示。 ( 2 ) 发现频繁项集阶段如表2 3 所示： ( 3 ) 转换阶段如表2 4 所示： ( 4 ) 序列阶段如表2 5 ，表2 6 所示： ( 5 ) 最大的频繁序列如表2 7 所示： 表2 7 最大的频繁序列 序列支持度 2 2 2 a p r i o r i a l l 算法存在以下的局限性：缺少时间约束、对交易的死板的定义、 缺少分类层次。为克服以上局限性，文献 6 】将序列模式的基本模型进行了扩展， 加入了时间约束、滑动时间窗口和分类层次，提出了泛化序列模式发现问题并 给出了相应的g s p 算法( g e n e r a l i z e ds e q u e n t i a lp a t t e r n s ) 。g s p 算法在序列模式 1 0 发现过程中应结合时间约束、滑动时间窗口和分类层次进行。 2 1 2 g s p 算法 g s p 算法是一个迭代的过程。在每一次迭代中，首先生成候选序列，然后 扫描序列数据库计算候选序列的支持度以确定频繁序列。主要包括( 1 ) 候选序 列的生成( 本阶段包括连接阶段和修剪阶段) 、( 2 ) 候选序列的支持度计数、( 3 ) 对分类层次的处理等。 g s p 算法存在的主要问题： ( 1 ) 如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式 ( 2 ) 需要对序列数据库进行循环扫描 ( 3 ) 对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模 太大，本算法很难处理 2 1 3p r e f i x s p a n 算法 f r e e s p a n 算法和p r e f i x s p a n 算法都是基于序列增长的发现方法。其中， f r e e s p a n 算法基于任何频繁子序列对序列数据库投影，并在子序列的任何位置 上增长；而p r e f i x s p a n 算法仅仅基于频繁前缀子序列投影并通过在其后添加后 缀来实现序列的增长。p r e f i x s p a n 算法因包含更少的投影库和子序列连接而比 f r e e s p a n 算法性能更优。下面以p r e f i x s p a n 算法来说明基于序列增长的方法。 p r e f i x s p a n 算法的主要开销在于投影库的构造。算法的优化在于如何减少投影 库的数量。有伪投影和隔层投影两种方法。 p r e f i x s p a n 算法不需要产生候选序列模式，从而大大缩减了检索空间，相 对于原始的序列数据库而言，投影数据库的规模不断减小，p r e f i x s p a n 算法的 主要开销在于投影数据库的构造。 2 1 4 序列模式的应用领域及其发展方向 序列模式发现来源于具有次序关系的购买行为的分析，现在己用于其他有 时间关联的事件分析。目前，序列模式的挖掘在网络通信、气象分析、商业零 售、金融证券等领域有广阔的应用前景，具体包括：客户购买行为模式预测、 w e b 访问模式预测、疾病诊断、自然灾害预测、d n a 序列分析。自序列模式概 念被提出之后，该问题成为数据挖掘的一个重要领域，国内外诸多研究人员对 此进行了研究。当前的研究在以下几个方面进行： ( 1 ) 序列模型的扩展 约束的序列模式发现；闭合频繁序列模式挖掘；带数据项约束的序列模式 挖掘；t o p k 闭合序列模式挖掘；不考虑支持度的序列模式挖掘等。 ( 2 ) 序列模式发现算法 主要研究序列模式原型发现，目前这类算法基本上分为两大类：一类是基 于a p r i o r i 特性的、逐层发现算法。一类是基于序列增长的算法。 ( 3 ) 序列模式更新算法 这是一个在数据更新情况下如何进行数据挖掘的问题。因为在大规模数据 库中发现序列模式的代价是非常昂贵的，为了避免在整个更新后的数据库上重 新进行数据挖掘，对已发现的序列模式的维护技术的研究十分必要。有多种序 列模式维护算法，其基本思想都是尽可能地利用已发现序列模式的信息来发现 新条件下的序列模式，从而提高算法效率。 2 1 5 几种算法的比较 经典的序列模式发现算法如a p r i o r i a l l 算法、g s p 算法主要存在以下问题： 如果序列数据库的规模比较大，则有可能产生大量的候选序列。 算法的每一次迭代都需要对序列数据库扫描以计算候选序列的支持度， 因而需要多次扫描数据库。 基于概念格的序列模式发现方法有以下特点： 以概念格为工具，仅需对原始交易数据库扫描一次即可得到与挖掘任务 相关的信息，从而减少了扫描原始交易数据库的次数。 通过子序列位置集合上的先后的连接得到候选序列的支持度，避免了使 用复杂的内部数据结构( 如哈希树) 来判断候选序列与顾客序列之间的包含关 系。 由于概念格节点是完备的，即只有最大扩展的概念才出现在格结构中。 利用格来生成序列模式，能有效减少中间序列的生成数量。 经典算法使用的是水平数据库的形式，在算法的第一步需要将交易数据 库转换为顾客序列数据库。而基于概念格发现序列模式使用垂直数据库的形式， 直接由交易数据库构造概念格，不需要做这样的转换。由于概念格中的概念( 结 点) 反映了概念内涵和外延的统一，概念之问的关系反映了概念的泛化和例化 关系。概念格通过h a s s e 图生动和简洁地体现了概念之间的泛化和特化关系， 因此被认为是进行数据分析的有力工具，非常适合于作数据挖掘的模型。 基于以上原因，本文提出基于概念格的序列模式的挖掘方法。利用概念格 为工具来发现序列模式，可以从几个方面提高经典算法的效率。 2 2 概念格 2 2 1 基本定义 r w i l l e 在1 9 8 2 年首先提出根据二元关系来构造概念格( 或g a l o i s 格) 的思想【2 2 1 ，也称为形式概念分析，就是以概念格中的每个节点表示一个形式概 念，其中概念的外延代表相应的一组对象，内涵则为这组对象所具有的公共特 征( 属性) ；而概念格对应的哈斯图则形象地揭示了概念间的泛化和例化关系， 反映出一种概念层次结构( c o n c e p th i e r a r c h y ) ，实现了对数据的可视化，适用 于从数据库中进行知识挖掘的描述，从而成为数据分析和规则提取的一种有效 工具。 然而，概念格结构也存在着一定的不足：( 1 ) 由于在定义概念和概念间关 系中的限制，等价知识不能被有效地表示出来；( 2 ) 在生成概念格和挖掘规则 时计算量偏大。为此，文f 1 2 对g a l o i s 格进行了扩展，进一步提出了多种扩展 形式如约简、相对约简及量化概念格，使其能更清晰地表示数据和知识，更有 效的提取概念间的各种规则。 现实世界由各种各样的对象组成，每个对象有相应的属性或者特征描述。 概念格结构是反映对象与属性之间联系以及概念泛化与例化关系的一种完备 的概念层次结构。下面简要介绍概念格的基本概念，关于概念格的详细的形式 化描述可参考文献【1 3 ，1 4 ，1 5 】。 定义2 1