（计算机应用技术专业论文）数据挖掘技术在乒乓球比赛技战术分析中的应用研究.pdf

北方工业大学硕士学位论文 摘要 随着信息技术的不断发展和各行业数据规模的不断庞大，数据挖掘技术不断成熟并 逐渐向领域应用方向发展。数据挖掘是从大规模的数据中抽取出非平凡的、隐含的、未 知的、有潜在使用价值的信息的技术。随着体育信息化事! j k 的不断发展，体育领域积累 了大量的数据，数据挖掘应用于体育领域尤其是对抗性竞技体育比赛的数据分析将成为 一种趋势。 本文在学习乒乓球比赛的领域知识以及对数据挖掘技术深入研究的基础上，详细阐 述了数据挖掘技术在乒乓球比赛技战术分析中的应用方法。本文的主要内容如下： 首先，作为本文研究的理论基础，介绍了数据挖掘的概念、发展过程、研究现状、 主要研究内容、常用方法、实际应用和发展趋势等。 其次，从数据挖掘技术入手，分别介绍了关联规则分析、聚类分析和基于马尔科夫 过程的数据挖掘算法在乒乓球比赛技战术分析中的应用方法和实现过程。对关联规则分 析算法，详细介绍了f p g r o w t h 算法及其在乒乓球比赛技战术分析中的应用实现过程及 挖掘结果；对聚类分析算法，详细介绍了k m e a n s 动态聚类算法及其在乒乓球比赛技 战术分析中的应用实现过程及挖掘结果；本文重点对基于马尔科夫过程的数据挖掘算法 进行了较深入的研究，并给出了该算法的详细实现过程及其在乒乓球比赛技战术分析中 的应用方法和挖掘结果。该算法的实现和在乒乓球比赛技战术分析中的应用是本文主要 的创新点。 再次，根据乒乓球比赛技战术的实际特点，本文提出了一套适用于乒乓球比赛技战 术数据采集的脚本描述语言。脚本描述语言是一项创新设计，它解决了乒乓球比赛中大 量技战术数据的采集问题。 最后，实现了一个乒乓球比赛技战术统计分析系统，本文对这个系统的体系结构、 数据模型以及各个功能模块都做了比较详细的介绍，并给出了系统的测试结果。该系统 实现了利用计算机对乒乓球比赛技战术进行统计分析，解决了目前主要采用的人工进行 分析所带来的问题，使得教练员能够更加准确的对比赛技战术数据进行分析，从而为教 练员进行合理的指导和决策提供科学的依据。 关键词：数据挖掘，乒乓球比赛，脚本描述，马尔科夫过程 北方工业大学硕士学位论文 s t u d y o nt h ea p p l i c a t i o nm e t h o do fd a t am i n i n gi na n a l y z i n g t e c h n i q u ea n d t a c t i c so ft a b l et e n n i sm a t c h a b s t r a c t a l o n gw i t ht h ed 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 ya n dt h eg r o w i n go f t h ea m o u n to f d a t af r o mv a r i o u sf i e l d s ，d a t am i n i n gt e c h n o l o g yi sb e i n gd e v e l o p e dc o n t i n u a l l ya n da p p l i e di n m a n yf i e l d sg r a d u a l l y d a t am i n i n gi sap r o c e s so fe x t r a c t i n gv a l i d ，p r e v i o u s l ym k n o w n ， c o m p r e h e n s i b l e , a n da c t i o n a b l ei n f o r m a t i o nf r o ml a r g ed a t a b a s e s ，a l o n gw i t ht h ed e v e l o p i n go f t h ei n f o r m a t i o nt e c h n o l o g y , m o r ea n dm o r ed a t ah a v eb e e na c c u m u l a t e di nt h ef i e l do f a t h l e t i c s p o r t s i ts h o u l db eat r e n dt h a td a t am i n i n gw a sa p p l i e dt oa t h l e t i cs p o r t se s p e c i a l l yo p p o s i t i o n a l a t h l e t i cs p o r t sd a t aa n a l y s i s 1 1 sp a p e rs t u d i e st h ef i e l do ft a b l et e n n i ss p o r t sa n dg o e sd e e pi n t ot h ed a t am i n i n g t e c h n o l o g y i ti l l u m i n a t e st h ea p p l i c a t i o no f d a t am i l l i n gi nd a t aa n a l y s i so f t a b l et e n n i sm a t c h t h em a j o r i t yo f t h ep a p e ri ss u m m a r i z e dh e r e ： f i r s t l y , a st h ea c a d e m i cf o t m d a t i o no ft h ep a p e r , i tp r e s e n t st h ec o n c e p t i o n ，d e v e l o p i n g b a c k g r o u n d ，r e s e a r c ha c t u a l i t y ，e s e a r c hc o n t e n t , r e s e a r c hm e t h o d , a p p l i c a t i o na n dd e v e l o p i n g t r e n do f d a t am i m n g s e c o n d l y ，t h ep a p e rs p e c i f i e st h ea p p l i c a t i o nm e t h o dm a dr e a l i z a t i o np r o c e s so f d a t am i m n g a l g o r i t h r n si na n a l y z i n gt e c h n i q u ea n dt a c t i c so f t a b l et e n n i sm a t c h ，w h i c hi n c l u d e sa s s o c i a t i o n n i l ea n a l y s i sa l g o r i t h m ，c l u s t e ra n a l y s i sa l g o r i t h ma n dai l e - wa l g o r i t h mb a s e do nm a r k o v p r o c e s s f o ra s s o c i a t i o nr u l ea l g o r i t h m , t h ep a p e rd e s c r i b e sf p - g r o w t ha l g o r i t h mi nd e t a i l ，a n d p r o v i d e st h er e a l i z a t i o np r o c e s sa n dm i n i n gr e s u l t so ft h ea l g o r i t h m f o rc l u s t e ra l g o r i t h m ，t h e p a p e rd e s c r i b e sk - m e a n sa l g o r i t h mi nd e t a i l ，a n dp r o v i d e st h er e a l i z a t i o na n dm i n i n gr e s u l t so f t h ea l g o r i t h m t h ep a p e rg o e sd e e pi n t os t u d yt h em i n i n gm e t h o db a s e do nm a r k o vp r o c e s s s p e c i a l l y , i t p r o v i d e s t h er e a l i z a t i o n p r o c e s s i n d e t a i l a n d t h e r e s u l t s o f i t t h i r d l y ，a c c o r d i n gt ot h et a b l et e n n i ss k i l l sf e a t u r e ，as c r i p td e s c r i p t i o nl a n g u a g ei sp u t f o r w a r df o rc o l l e c t i n gt a b l et e n n i sm a t c hd a t a 确es c r i p td e s c r i p t i o nl a n g u a g ei so l l eo f i n n o v a t i o ni nt h ep a p e r , a n di ts o l v e st h ep r o b l e mh o wt h el a r g ea m o u n to fd a t ao ft h et a b l e t e n n i sm a t c hi sc o l l e c t e d f i n a l l y ，ad a t am i n i n gs y s t e mf o ra n a l y s i so f t e c h n i q u ea n dt a c t i c so f t a b l et e n n i sm a t c hi s a c c o m p l i s h e d t h ep a p e rd e s c r i b e st h ea r c h i t e c t u r e , d a t am o d e l sa n de v e r yf u n c t i o n a lm o d u l eo f t h es y s t e mi nd e t a i la n d p r e s e n t st h et e s t i n gr e s u l t so f t h es y s t e m k e yw o r d s ：d a t am i n i n g , t a b l et e n n i sm a t c h ，s c r i p td e s c r i p t i o n ，m a r k o vp r o c e s s 一3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得韭直王些太堂或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名潍字日期撕6 月j 日 学位论文版权使用授权书 本学位论文作者完全了解j 直王些太堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本入授权j e 直王些盔兰可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：喜谬歌 签字日期列年6 月j 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师繇易豸印 签字日期：瞬j 月7 - 日 ， 电话： 邮编： 北方工业大学硕士学位论文 1 引言 作为本文的开篇部分，本章主要介绍了课题“数据挖掘技术在乒乓球比赛技战术分 析中的应用研究”的研究背景和主要研究内容，然后介绍了本文的组织结构。 1 1 课题研究背景 随着计算机技术和网络技术的迅速发展，人们迎来了一个以信息和知识为主要特征 的网络新时代。人们接触的信息特别是数字化信息呈指数增长。信息量持续地强劲增势 带给人们的不仅仅是方便，更多的却是严峻的挑战。因为信息的剧增使得信息供给与信 息消费之问动态平衡被打破，二者差距越来越大。在堆积如山的信息库中包含着许多待 提取的有用知识，这些知识如同成熟的庄稼，如不及时地收割便会浪费。那么，如何从 信息海洋中“及时地收割成熟的庄稼”? 人们迫切需要新一代的技术方法和工具来帮助 开采信息山中蕴藏的宝藏，并加以提炼，使之成为有用的知识。于是，一个新的研究领 域数据挖掘( d a t am i n i n g 简称d m ) 应运而型”。 随着人们对数据挖掘技术逐渐深入的认识和理解以及数据挖掘在实际应用中产生的 显著经济效益，数据挖掘在各个领域的应用蓬勃发展。如电讯公司、信用卡公司、保险 公司和证券公司利用数据挖掘技术检测欺诈行为；医疗应用中通过数据挖掘来判断某些 方法可能对治疗某种疾病产生效果；超市利用数据挖掘分析交易数据，安排货架上的货 物摆放布局，以提高销售额：金融领域利用数据挖掘技术发现某个客户、消费群体或组 织的金融和商业兴趣，并可观察金融市场的变化趋势b ”。 认识到数据挖掘的功能以后，国外已经将数据挖掘技术应用于竞技体育中。例如， 美国n b a 的教练利用i b m 公司提供的数据挖掘工具a d v a n c e ds c o u t 临场辅助决定替换 队员，取得了很好的效果。目前，大约2 0 个n b a 球队使用了该软件系统来优化他们的 战术组合。然而，在我国，数据挖掘在体育领域的应用极少，还尚处于刚刚起步的阶 段，但是已经日渐得到重视。随着我国体育事业信息化的逐步实现，在竞技体育领域积 累了大量的数据，如何充分利用这些数据并从中发现有价值的、却被人们忽视的重要信 息，已成为科研人员一项重要任务【2 】。乒乓球是一项对抗性质的竞技体育项目，它不但 要求运动员自身具有较高的技术水平，同时对战术的运用有较高的要求，很多时候比赛 中的战术运用都会对比赛的胜负起到决定性的作用，因此，我们有必要在乒乓球比赛分 析中应用数据挖掘和知识发现，其目的是对乒乓球比赛相关数据库提供的大量繁杂信息 北方工业大学硕士学位论文 进行实时和深层次的分析，从中找出真正有价值的信息和知识，从而对教练员决策战术 运用提供参考和依据。 1 2 本文主要研究内容 本文主要是以数据挖掘技术、现代统计学和乒乓球技术作为理论基础，利用计算机 作为数据采集和分析工具，研究利用数据挖掘技术实现乒乓球比赛技战术统计、分析的 方法，并设计实现支持乒乓球技战术统计分析方法的计算机软件。本文研究内容主要包 括以下几个方面： 1 乒乓球比赛技战术数据的采集：研究如何对乒乓球比赛技战术数据进行合理、 快速、有效的采集。本文采用了两种数据采集方法：鼠标点击方法和脚本描述方法，重 点研究了如何提高脚本描述方法采集比赛数据的速度和如何缩减脚本描述符数据库，设 计了一套适用于乒乓球比赛技战术数据采集的脚本描述语言。 2 数据挖掘技术在乒乓球比赛技战术分析中的应用方法研究：通过实验找出适合 于乒乓球比赛技战术分析的数据挖掘算法并研究算法在乒乓球比赛技战术分析中如何应 用。 3 对关联规则分析方法，主要研究了一种改进的高效的f p g r o w t h 算法及其在乒 乓球比赛技战术分析中的应用方法及实现过程。 4 对聚类算法，主要研究了k - m e a n s 动态聚类算法及其在乒乓球比赛技战术分析 中的应用方法及实现过程。 5 本文重点对基于马尔科夫过程的数据挖掘算法进行了深入的研究，研究了该算 法在乒乓球比赛技战术分析中的应用方法及实现过程。 1 _ 3 本文2 吉构 本文在对数据挖掘相关理论进行阐述的基础之上，详细地叙述了数据挖掘技术在乒 乓球比赛技战术分析中的应用实现过程。本文主要从以下几个方面进行论述： 摘要部分，对本文的主要内容和研究工作进行了概括性叙述。引言部分，简要介绍 了本文的研究背景、主要研究内容以及本文结构。第二章，作为本文的理论基础，主要 介绍了数据挖掘的概念、发展过程、研究现状、主要研究内容、常用方法、实际应用和 发展趋势等。第三章，是本文的主体部分，从数据挖掘技术入手，分别介绍了数据挖掘 北方工业大学硕士学位论文 中关联规则分析算法、聚类算法和基于马尔科夫过程的数据挖掘方法的实现过程及其在 乒乓球比赛技战术分析中的应用。第四章，对本文实现的“乒乓球比赛技战术统计分析 系统”进行了介绍，比较详细的介绍了该系统的分析、设计、实现方法和测试结果。第 五章，结论部分，首先对本文所作的主要工作进行了总结，然后对本文的后续工作进行 了概括叙述。 一3 一 北方工业大学硕士学位论文 2 数据挖掘基本理论综述 作为本文研究的理论基础，本章对本文作者所阅读的中外资料进行了综述，主要介 绍了数据挖掘的概念、发展过程、研究现状、主要研究内容、常用研究方法以及发展趋 势。 2 1 数据挖掘的发展过程及研究现状 数据库技术的成熟和普及使人类积累的数据量正在以指数方式增长；i n t e m e t 技术 的出现和发展已将整个世界连接成一个地球村，人们可以穿越时空般地在网上交换信息 和协同工作。在这个信息爆炸的时代，面对着浩瀚无垠的信息海洋，人们呼唤着一个去 粗取精、去伪存真的能将浩如烟海的数据转换成知识的技术。数据挖掘就是在这个背景 下产生和发展的。本节将对数据挖掘的发展过程和研究现状进行介绍。 2 ，1 1 发展过程 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，千万个数据库 被用于商业管理、政府办公、科学研究和工程开发等等，并且这一势头仍将继续发展下 去。于是，一个新的挑战被提了出来：在这个被称之为信息爆炸的时代，信息过量几乎 成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没，从中发现及时有用的 知识，提高信息利用率呢? 要想使数据真正成为一个公司的资源，只有充分利用它为公 司自身的业务决策和战略发展服务才行，否则大量的数据可能成为垃圾，甚至成为包 袱。因此，面对人们渴求获取知识却又可能被数据淹没的挑战，数据挖掘和知识发现 ( d m k d ) 技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种商业数据 是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展到对 数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能对过去 的数据进行查询和遍历，并且能够找出数据之间的潜在联系，从而促进有用信息的产 生。现在数据挖掘技术在商业应用中已经可以马上投入使用，因为对这种技术进行支持 的三种基础技术( 海量数据搜集、强大的多处理器计算机、数据挖掘算法1 已经发展成 熟。 - 4 一 北方工业大学硕士学位论文 f r i e d m a n 列举了激发数据挖掘的开发、应用和研究的兴趣的四个主要的技术理由： ( 1 ) 超大规模数据库的出现，例如商业数据仓库和计算机自动收集的数据记录：( 2 ) 先进 的计算机技术，例如更快和更强大的计算能力和并行体系结构；( 3 ) 对巨大量数据的快速 访问；( 4 ) 对这些数据应用精深的统计方法计算的能力。 商业数据库现在正以一个空前的速度增长，并且数据仓库正在广泛地应用于各种行 业；对计算机硬件性能越来越高的要求，也可以用现在已经成熟的并行多处理机的技术 来满足；另外数据挖掘算法经过了这1 0 多年的发展也已经成为一种成熟、稳定且易于 理解和操作的技术。 数据挖掘的核心模块技术历经了数十年的发展，其中包括数理统计、人工智能、机 器学习。今天，这些成熟的技术，加上高性能的关系数据库引擎以及广泛的数据集成， 让数据挖掘技术在当前的数据仓库环境中进入了实用的阶段。 2 1 2 研究现状 数据挖掘在研究和应用方面发展迅速，尤其是在商业和银行领域，其应用比研究的 发展速度还要快。目前，国际上有关于数据挖掘的研究主要包括：对知识发现方法的研 究进一步发展，如近年来比较注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和 改进；传统的统计学回归法在数据挖掘中的应用；数据挖掘与数据库、数据仓库的紧密 结合。在应用方面主要包括：数据挖掘商业软件工具不断产生和完善，注重建立解决问 题的整体系统，而不是孤立的过程。用户主要集中在大型银行、保险公司、电信公司， 此外，销售业、制造业的应用也正在逐渐展开。国外很多计算机和软件公司也非常重视 数据挖掘软件的开发和应用，m 和微软都成立了相应的研究中心进行这方面的工作。 目前，世界上比较有影响的数据挖掘系统有：s a s 公司的e n t e r p r i s em i l l e r 、m m 公司 的i n t e l l i g e n tm i n e r 、s g i 公司的s e tm i l l e r 、s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的 w a r e h o u s es t u d i o 、r u l eq u e s tr e s e a r c h 公司的s e e 5 ，此外，还有c o v e rs t o r y 、 e x p l o r a 、k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d b m i n e r 、q u e s t 等。 与国外相比，国内对数据挖掘的研究起步稍晚。1 9 9 3 年国家自然科学基金首次支 持该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知识发现的基础 理论及应用研究，如清华大学、中科院计算技术研究所、空军第三研究所、海军装备论 证中心等。北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究， 北京大学也在开展对数据立方体代数的研究；华中理工大学、复旦大学、浙江大学、中 北方工业大学硕士学位论文 国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则挖掘算法的优化和 改造；南京大学、四川大学和上海交通大学等单位探讨、研究了非结构化数据的知识发 现以及w e b 数据挖掘。 从以上介绍的内容可以看出，目前，数据挖掘技术在国内外各行各业已经得到了广 泛的应用，并在国内也已经蓬勃发展起来。但是在体育领域的应用相对于在其他领域的 应用来说还比较少。在国外，数据挖掘在体育领域已有一些应用，比如美国n b a 的教 练利用i b m 公司提供的数据挖掘工具a d v a n c e ds c o u t 临场辅助决定替换队员，意大利 开发了d a t av o l l e y 软件系统实现了排球比赛的技战术统计分析。然而在国内，数据挖 掘在体育领域的应用尚处于理论探讨阶段。文献【2 4 2 】提出了利用数据挖掘技术对体育 比赛数据进行分析的方法，但所提出的方法也只是介绍了数据挖掘可以在该领域的应用 前景而已，并没有给出具体的研究背景和实例。 2 _ 2 数据挖掘的概念 数据挖掘出现于2 0 世纪8 0 年代后期，是数据库研究中一个很有应用价值的新领 域，是一门交叉性学科，它融合了人工智能、数据库技术、模式识别、机器学习、统计 学和数据可视化等多个领域的理论和技术【4 ”。在k d d 9 6 国际会议上，根据知识发现领 域知名学者的阐述，一个被一致接受的知识发现( k d d ) 定义表述为：“对数据库中蕴 涵的、未知的、有潜在应用价值的、非平凡的模式的提取”。一般认为数据挖掘是知识 发现的一个主要过程，并不对二者做出严格区分1 6 。根据w j f r a w l e y 和g p s h a p i r o 等 人提出的定义，数据挖掘( d a t am i n i n g ) 是指从大量的、不完全的、有噪声的、模糊 的、随机的数据中，提取出隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程。它对数据的处理不仅仅局限于查询和访问，而且能够找出数据之间潜在 的联系【2 】。这个定义包括几层含义：数据是数据挖掘的“源”，它们来自数据库、数据 仓库、某些非数据库系统以及网络数据。数据源必须是真实的、大量的：数据挖掘的结 果是用户感兴趣的、概念化的知识；而发现的知识需要可接受、可理解、可运用，并支 持特定的问题发现。 数据挖掘其实是一个逐渐演变进化的过程。从数据库的角度看，它是一个从数据库 的数据中识别出有效的、新颖的、具有潜在效用的并最终可理解的信息( 如规则、约束 等) 的非平凡过程。非平凡是一个数学概念，即数据挖掘既不是把数据全部抽取，也不 是一点儿也不抽耿，而是抽取出隐含的、未知的、可能有用的信息。从决策支持的角度 北方工业大学硕士学位论文 看，数据挖掘是一种决策支持过程，主要基于人工智能、机器学习、统计学和数据库技 术等多种技术，能高度自动地分析数据源，进行归纳推理，从中挖掘出潜在的模式，预 测客户的行为，帮助企业的决策者调整行为策略，从而减少风险，辅助作出正确的决 策。它是提高商业和科学决策过程质量和效率的一种新方法【l 【。 与传统的数据分析( 如查询、报表、联机应用分析) 相比，数据挖掘最大的区别在 于数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识，数据挖掘所得到的信息 应具有事先未知、有效和实用三个特征。 2 3 数据挖掘的主要研究内容及常用方法 介绍了数据挖掘的发展过程、研究现状以及数据挖掘的概念之后，本节将进一步介 绍数据挖掘的主要研究内容和常用研究方法。 2 3 1 主要研究内容 数据挖掘的任务就是发现隐减在数据中的模式。其可以发现的模式般分为两大 类：描述型( d e s c r i p t i v e ) 模式和预测型( p r e d i c t i v e ) 模式。描述型模式是对当前数据中存在 的事实做规范描述，刻画当前数据的一般特性；预测型模式则是以时间为关键参数，对 于时间序列型数据，根据其历史和当前的值去预测其未来的值。根据模式特征，可将模 式大致细分如下 4 叫】。 1 分类模式( c l a s s i f i c a t i o n ) 分类就是构造一个分类函数( 分类模型) ，把具有某些特征的数据项映射到某个给 定的类别上。该过程由2 步构成：模型创建和模型使用。模型创建是指通过对训练数据 集的学习来建立分类模型；模型使用是指使用分类模型对测试数据和新的数据进行分 类。其中的训练数据集是带有类标号的，也就是说在分类之前，要划分的类别是已经确 定的。通常分类模型是以分类规则、决策树或数学表达式的形式给出的。 2 聚类模式( c l u s t e r i n g ) 聚类就是将数据项分组成多个类或簇，类之问的数据差别应尽可能大，类内的数据 差别应尽可能小，即为“最小化类间的相似性，最大化类内的相似性”原则。与分类模 式不同的是，聚类中要划分的类别是未知的，它是一种不依赖于预先定义的类和带类标 北方工业大学硕士学位论文 号的训练数据集的非监督学习( u n s u p e r v i s e dl e a r n i n g ) ，无需背景知识，其中类的数量 由系统按照某种性能指标自动确定。 3 关联模式( a s s o c i a t i o n ) 关联模式是数据项之间存在的关联规则，是在同一事件中出现的不同项之间的相关 性，比如顾客在同一次购买活动中所购买的不同商品之间的相关性 最著名的关联规则挖掘算法是由a g r a w a l 等人于1 9 9 4 年提出的a p r i o r i 算法【。 a p f i o r i 算法的基本思想是：统计多种商品在一次购买中共同出现的频数，然后将出现频 数多的搭配转换为关联规则。a p r i o r i 算法的核心是：用前次扫描数据库的结果产生本 次扫描的候选项目集，从而提高搜索的效率。其后人们又提出了诸多关联规则挖掘算 法，主要工作集中在如何提高项集的生成效率和降低计算代价上。 4 序列模式( s e q u e n t i a l ) 序列模式是描述基于时间或其他序列的经常发生的规律或趋势，并对其建模。一个 典型的例子就是：在购买p c 机的顾客当中，7 0 的人会在半年内购买内存条。序列模 式将关联模式和时间序列模式结合起来，重点考虑数据之间在时间维上的关联性。有3 个参数的选择对序列模式挖掘的结果影响很大：序列的持续时间t ，也就是某个时间 序列的有效时间或者是用户选择的一个时间段；时间折叠窗口( w t ) ，在某段时间 内发生的事件可以被看作是同时发生的；所发现模式的时间间隔。 5 回归模式( r e g r e s s i o n ) 回归模式的函数定义与分类模式相似，主要差别在于分类模式采用离散预测值( 例 如类标号) ，而回归模式采用连续的预测值。在这种观点下，分类和回归都是预测问 题。但在数据挖掘业界，大家普遍认为：用预测法预测类标号为分类，预测连续值( 例 如使用回归方法) 为预测【9 】。许多问题可以用线性回归解决，对于许多非线性问题可以 通过对变量进行变换，从而转换为线性问题来解决。 6 偏差模式( d e v i a t i o n ) 偏差模式是对差异和极端特例的描述，如聚类外的离群值。大部分数据挖掘方法都 将这种差异信息视为噪声而丢弃，然而在一些应用中，罕见的数据可能比正常的数据更 有用 9 1 。比如信用卡的欺骗检测( f r a u dd e t e c t i o n ) ，通过检测一个给定帐号与其历史上 - 8 一 北方工业大学硕士学位论文 正常的付费相比，可以以付款数额特别大这一异常数据为依据来发现信用卡被欺骗性使 用。 2 3 2 常用方法 1 模糊( f u z z y ) 方法 美国控制论专家、数学家查德( z a d e h ) 于1 9 6 5 年发表的论文模糊集合( f u z z y s e t s ) t ”1 ，标志着模糊数学这门学科的诞生。模糊集合和模糊推理是模糊方法的数学基 础，模糊集理论以不确定性的事物为研究对象，是经典集合理论的扩展。隶属度函数是 模糊集合的特征函数，是模糊概念的核心，它的取值范围从普通集合 o ，1 的两个值扩充 n o ，1 闭区间内连续值，隶属度函数的定义如下。 设给定论域u ，un o ，1 n = 区f g j 的任一映射z 叫， ，厶4 ：u _ 【o ，1 】，u - t a ( u ) u eu 都确定u 的一个模糊子集a ，d 是a 的隶属度函数，肛4 ( u ) 是u 对a 的隶属度， 表征u 属于a 的程度。其实模糊集合并不是一个集合，因为其核心是隶属度函数，如 同概率中的随机变量，所以更确切地应该称其为模糊函数 模糊推理就是由日u 提( a ) ，依规贝j j ( i fat h e n b ) 推理，得到结论( b ) 。规则是一种蕴 涵关系，推理中将前提和规则结合是一种合成关系。在模糊方法中，关系就是模糊集 合，找关系便是找隶属度函数。如何选择蕴涵关系和合成算法是模糊推理的关键，这里 有许多经验的成分。模糊推理注重的是把握结论的趋势，是近似的而不是精确的结果。 当然，模糊推理的结果也可能是错的，所以还要实践检验。 模糊逻辑系统已用于许多特别是基于规则的分类领域，包括医疗和财经。在基于规 则的分类系统中引入模糊逻辑，就可以定义“模糊”阈值或边界，可以避免原系统固有 的缺陷：对于连续值，有陡峭的截断【9 】。从而可能获得一个更合理的分类结果。 2 粗糙集( r o u g hs e t s ) 理论 r o u g h 集理论是由波兰华沙理工大学的z p a w l a k 教授于1 9 8 2 年提出的一种研究不 完整、不确定知识和数据的表达、学习和归纳的理论方法【，现已成为d m k d d 研究 中的最有力工具，也最有发展前途。r o u g h 集理论采用上近似集合( u p p e ra p p r o x i m a t i o n s ) r + 和下近似集合( 1 0 w e r a p p r o x i m a t i o n s ) r ，来定义r o u g h 集【1 1 ，即 北方工业大学硕士学位论文 r + d n _ 1r ty u r ：y n x 尹j f1 r 。( ) = u ty u r ：y _ c xj 其中：u 是全域；x c - u 是目标集合；r 是u 上的等价关系；y e 帆表示y 是u 上按等价关系r 做成的等价类。上近似集合可理解为所有那些与x 有交的等价类的并 集；下近似集合可理解为所有那些被包含在x 里面的等价类的并集。 上近似集合和下近似集合之间的差称为x 的r 边界线集( b o u n d a r yr e g i o n ) ，表示 为：b n r - - r * ( x ) 一m 0 0 。它是那些通过等价关系r 既不能在x 上分类，也不能在x 上 分类的元素的集合。 从语义角度来看，r + ( 两x r + ，介于r 和r + 之间的集合簇均属r o u g h 集，而上下近似集合则是该空间的两个极限。在r o u g h 逻辑推理中，不必涉及隶属度函 数，这样的软计算技术有助于知识获取瓶颈的突破。r o u g h 集理论的核心特点是无需提 供问题所需处理的数据集合以外的任何先验信息，这也可能是因为其无法获得客观事实 的足够支持。从这点看，r o u g h 集理论是对f u 互y 集理论的发展和重大拓展。 r o u g h 集理论可以用于分类，发现不准确数据或噪声数据内在的联系。找出可以描 述给定数据集中所有概念的最小属性子集是个n p 一难问题。在给定的现实世界数据 中，往往有些类不能被可用的属性区分，那么就可以用r o u g h 集来近似地定义这些类。 3 云化1 0 u d ) 理论 云理论是李德毅教授于1 9 9 5 年提出的用于处理不确定性的一种新理论。2 】。作为处 理模糊性问题的主要工具，f u z z y 集理论提出了隶属度函数来刻画模糊事物的亦此亦彼 性；然而，一旦用精确的隶属度函数来描述模糊集，之后的模糊推理等环节就不再有模 糊性了。这就是传统模糊集理论的不彻底性。针对这一问题，李德毅教授在传统模糊集 理论和概率统计的基础上提出了定性定量不确定性转换模型云模型，把定性概念的 模糊性和随机性完全集成到一起，构成定性和定量相互间的映射，作为知识表示的基础 【1 3 】。 云是用语言值描述的某个定性概念与其数值表示之间的不确定性转换模型。设论域 u = x l ，x 2 ，, x n ) ，t 是与u 相联系的语言值。u 中的元素x 对于t 所表达的定性概念 的隶属度c 1 ( x ) ( 或称x 对于t 的相容度) 是一个具有稳定倾向的在 0 ，1 】中取值的随机数， 隶属度在论域上的分布称为隶属云，简称为云。对于任意的x eu 到区间 o ，1 】的映射是 一对多的转换，二对于t 的隶属度是一个概率分布而非固定值，从而产生了云，而不是 1 0 北方工业大学硕士学位论文 f u z z y 集理论中的一条明晰的隶属度曲线。云由云滴组成，每个云滴是定性概念在定量 上的一次实现，单个云滴可能无足轻重，但云的整体形状反映了定性概念的基本特征。 如果从f u z z y 集理论的观点来看，云的数学期望曲线是f u z z y 集理论中的隶属度曲线。 期望值e x ( e x p e c t e dv a l u e ) ：是概念在论域中的中心值，是最能代表这个定性概念的 值，也就是说，它1 0 0 隶属于这个定性概念。 熵e n ( e n t r o p y ) ：是定性概念模糊度的度量， 数值范围，体现了定性概念亦此亦彼性的裕度。 大，概念就越模糊。 反映了在论域中可被这个概念所接受的 熵越大，概念所能接受的数值范围也越 超熵h e ( h y p e re n t r o p y ) ：是熵的熵，反映了云滴的离散程度。超熵越大，云滴离散 度越大，隶属度的随机性越大，云的“厚度”也越大。云的“厚度”是不均匀的，腰部 最为分散，顶部和底部汇聚性好。这表明，靠近概念中心或远离概念中心处隶属度的随 机i 生较小，而离概念中心不近不远处隶属度的随机陆较大。这与人的主观感受一致。 在数据挖掘中，云理论常和r o u g h 集理论相结合。前者研究的是数据的模糊性和 随机性，为定量定性间的不确定性转换提供模型；而后者强调的是数据的不完备性和不 可分辨性，但其处理方法是确定性的，要求属性值都是定性值。所以两者具有某种互补 性。 4 证据理论( e v i d e n c et h e o r y ) 证据理论又称d e m p s t e r s h a f e r 理论，是经典概率论的扩充【14 】。首先由d e m p s t e 在 2 0 世纪6 0 年代提出，在7 0 年代中期由s h a f e r 进一步发展，形成处理不确定信息的证 据理论。该理论的一个重要贡献就是划清了不确定和不知的界限【1 3 】。 在证据理论中，一个样本空间称为一个识别框架，用q 表示。q 由系列对象构 成，对象之间两两互斥，且包含当前要识别的全体对象。q 的所有子集的集合记为 2 “。若q 中有1 3 _ 个对象，则有2 “个子集。每个子集对应一个命题( 证据或结论) 。证据 理论的基本问题是：已知识别框架q ，判明q 中一个先验的未定位对象属于q 的某个 子集a 的程度。 a n a n d 等人于1 9 9 4 年提出了一个基于证据理论的通用数据挖掘框架e d m ( d a t a b a s e m i n i n gb a s e do ne v i d e n c et h e o r y ) 【1 5 】，在e d m 框架下d m k d d 的技巧主要是根据不同的 任务选择和开发不同的算子。e d m 已经用于从关系数据库发现强规则，以及从大量的 金星表面图像数据中识别火山。同时，e d m 的算法本质上是并行的，在处理并行、分 北方工业大学硕士学位论文 布及异构数据库时有显著的优越性。由于证据理论在处理不确定性方面的优点，加之 e d m 的开发和应用，使得基于证据理论的方法在数据挖掘中具有潜在的应用性。 5 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) 人工神经网络由多个神经元按照某种方式相互连接形成，靠网络状态对外部输人信 息的动态响应来处理信息，网络的信息分布式存储于连接权系数中，使网络具有很强的 容错性和鲁棒性。神经网络的核心是结构和算法，例如以结构见长的h o p f i e l d 网和以算 法见长的b p ( b a c kp r o p a g a t i o n ) l 嘲”6 j 。 同模糊逻辑系统相比，模糊逻辑系统是从宏观功能上“软”模拟人脑的逻辑思维机 制，而神经网络是从微观结构上“硬”模拟人脑的经验思维机制；模糊逻辑系统的智能 级别为推理级，而神经网络的智能级别为感知级。 在数据挖掘中，神经网络主要用于获取分类模式。但是由于神经网络分类方法获取 的模式隐含在网络结构中，而不是显示地表达为规则，不容易被人们理解和解释；另外 要多次扫描训练数据，网络的训练时间较长。因此与其他数据挖掘方法不同，神经网络 用于数据挖掘，要解决好两个关键问题：一是降低训练时间，二是挖掘结果的可理解 性。 6 遗传算法( g e n e t i cf l g o f i t h m s ，g a ) 遗传算法最先由j o h nh o l l a n d 于1 9 7 5 年提出【1 7 】。其模拟生物的进化和遗传，借助 选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 并h 变异( m u t a t i o n ) 操作，使要解决的问题从初始解逐步逼 近最优解，解决了许多全局优化问题。可以说“优胜劣汰”原则和种群“多样性”是 g a 的灵魂。“选择”保证了前者，“交叉”和“变异”保证了后者。但“选择”容易 产生早熟个体，使“多样性”过早丧失，而“交叉”和“变异”的随机性太大，带有盲 目性。 g a 通过编码将优化等问题从问题空间映射到o a 的操作空间，再通过译码将操作 结果从操作空间映射回问题空间。对于具体的问题，常常有限制条件，即存在一个可行 解空间。为了保证最后的解是可行的，可以采取两种方法：一是将可行解空间与g a 的 操作空间一一对应；二是将可行解空间包含于问题空间中。 g a 是依据随机技术来保证其寻优方向的确定算法，从“最优个体在运动过程中越 来越多”可推断出：g a 只能保证全局寻优的趋势。已有理论证明，不改造的g a 不能 达到全局最优，只能寻到全局最优的邻域。在达到该邻域后可采用局部寻优( 如梯度法) 1 2 北方工业大学硕士学位论文 来最终达到全局最优点。目前关于g a 的最好理论结果是：经过改进的g a 能够依概率 达到全局最优。由于小概率事件有可能发生，所以算法有可能不收敛。这与理想的期 望依概率1 收敛到全局最优有一定的距离。 遗传算法易于并行，已广泛用于分类和优化问题。在数据挖掘中，还可用于评估其 他挖掘算法的适合度 9 1 。 7 归纳学习( 1 n c i c t i o nl e a r n i n 9 1 归纳学习是从大量的经验数据中归纳抽取出一般的规则和模式，是一种重要的数据 挖掘方法。归纳学习的算法大部分来自于机器学 习( m a c h i n el e a r n i n g ) 领域