人工智能数据挖掘

第八章

数据挖掘人工智能华中师范大学计算机科学系人工智能数据挖掘第1页第八章数据挖掘数据挖掘（DataMining）是一个多学科交叉研究领域，它融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化等最新技术研究结果。经过十几年研究，产生了许多新概念和方法。尤其是最近几年来，一些基本概念和方法趋于清楚，它研究正向着更深入方向发展。数据挖掘技术正在以一个全新概念改变着人类利用数据方式，它被认为是未来信息处理骨干技术之一，网络之后下一个技术热点。人工智能数据挖掘第2页8.1数据挖掘概述8.1.1数据挖掘定义数据挖掘（DataMining）是一门受到来自各种不一样领域研究者关注交叉性学科，有很多不一样术语名称，除了惯用“数据挖掘”和“知识发觉”之外，与数据挖掘相近同义词有数据融合、数据分析、知识抽取、信息发觉、数据采掘、知识获取、数据考古、信息收获和决议支持等。从技术角度讲，数据挖掘就是从大量、不完全、有噪声、含糊、随机实际应用数据中，提取隐含在其中、人们事先不知道、但又是潜在有用信息和知识过程。这个定义包含好几层含义：数据源必须是真实、大量、含噪声；发觉是用户感兴趣知识；发觉知识要可接收、可了解、可利用；并不要求发觉放之四海皆准知识，也不是要去发觉崭新自然科学定理和纯数学公式，更不是什么机器定理证实，只要能支持特定发觉问题即可。实际上，利用数据挖掘从数据集中全部发觉知识都是相正确，是有特定前提和约束条件，面向特定领域，同时还要能够易于被用户了解。最好能用自然语言表示所发觉结果。人工智能数据挖掘第3页8.1数据挖掘概述从商业角度讲，数据挖掘是一个新商业信息处理技术，其主要特点是对商业数据库中大量业务数据进行抽取、转换、分析和其它模型化处理，从中提取辅助商业决议关键性数据。简而言之，数据挖掘其实是一类深层次数据分析方法。数据分析本身已经有很多年历史，只不过在过去数据搜集和分析目标是用于科学研究，另外，因为当初计算能力限制，对大数据量进行分析复杂数据分析方法受到很大限制。现在，因为各行业业务自动化实现，商业领域产生了大量业务数据，这些数据不再是为了分析目标而搜集，而是因为纯机会商业运作而产生。分析这些数据也不再是单纯为了研究需要，更主要是为商业决议提供真正有价值信息，进而取得利润。人工智能数据挖掘第4页8.1数据挖掘概述8.1.2数据挖掘与数据库中知识发觉（1）KDD看成数据挖掘一个特例数据挖掘系统能够在关系数据库、事务数据库、数据仓库、空间数据库（SpatialDatabase）、文本数据（TextData）以及诸如WEB等各种数据组织形式中挖掘知识，既然如此，那么能够说数据库中知识发觉只是数据挖掘一个方面，这是早期比较流行观点。所以，从这个意义说，数据挖掘就是从数据库、数据仓库以及其它数据存放方式中挖掘有用知识过程。这种描述强调了数据挖掘在源数据形式上多样性。(2)数据挖掘是KDD过程一个步骤在“知识发觉96国际会议”上，许多学者提议对这两个名词加以区分。关键思想是：KDD是从数据库中发觉知识全部过程，而DataMining则是此全部过程一个特定、关键步骤，这种观点有它合理性。即使我们能够从数据仓库、WEB等源数据中挖掘知识，不过这些数据源都是和数据库技术相关。数据仓库是由源数据库集成而来，即使是像WEB这么数据源恐怕也离不开数据库技术来组织和存放抽取信息。所以KDD是一个更广义范围，它包含数据清洗、数据集成、数据选择、数据转换、数据挖掘、模式生成及评定等一系列步骤。这么，我们能够把KDD看作是一些基本功效构件系统化协同工作系统，而数据挖掘则是这个系统中一个关键部分。人工智能数据挖掘第5页8.1数据挖掘概述（3）KDD与DataMining含义相同

也有些人认为，KDD与DataMining只是叫法不一样，它们含义基本相同。实际上，在现今文件中，许多场所，如技术综述等，这两个术语依然不加区分地使用着。也有些人说，KDD在人工智能界更流行；DataMining在数据库界使用更多。所以，从广义观点，数据挖掘是从大型数据集（可能是不完全、有噪声、不确定性、各种存放形式）中，挖掘隐含在其中、人们事先不知道、对决议有用知识过程。

从上面描述中能够看出，数据挖掘概念能够在不一样技术层面上来了解，不过其关键依然是从数据中挖掘知识。从本质来讲，数据挖掘与知识发觉是有区分，不过在很多场所人们往往不严格区分数据挖掘和数据库中知识发觉，二者互为使用。普通在科研领域中称为KDD，而在工程领域则多称为数据挖掘。人工智能数据挖掘第6页8.1数据挖掘概述8.1.3数据挖掘研究理论基础数据挖掘方法能够是基于数学理论，也能够是非数学；能够是演绎，也能够是归纳。从研究历史看，它们可能是数据库、人工智能、数理统计、计算机科学以及其它方面学者和工程技术人员，在数据挖掘探讨性研究过程中创建理论体系。1997年，Mannila对当初流行数据挖掘理论框架给出了综述。结合最新研究结果，有下面一些主要理论框架能够帮助我们准确地了解数据挖掘概念与技术特点。模式发觉架规则发觉架构基于概率和统计理论微观经济学观点基于数据压缩理论基于归纳数据库理论人工智能数据挖掘第7页8.1数据挖掘概述8.1.4数据挖掘与其它数据处理方法区分及联络1．数据挖掘与传统分析方法区分数据挖掘与传统数据分析(如查询、报表、联机应用分析)本质区分是数据挖掘是在没有明确假设前提下去挖掘信息、发觉知识。数据挖掘所得到信息应含有先未知，有效和可实用三个特征。先前未知信息是指该信息是预先未曾预料到，既数据挖掘是要发觉那些不能靠直觉发觉信息或知识，甚至是违反直觉信息或知识，挖掘出信息越是出乎意料，就可能越有价值，在商业应用中最经典例子就是一家连锁店经过数据挖掘发觉了小孩尿布和啤酒之间有着惊人联络。2.数据挖掘和数据仓库大部分情况下，数据挖掘都要先把数据从数据仓库中拿到数据挖掘库或数据集市中（见图8.1）。从数据仓库中直接得到进行数据挖掘数据有许多好处。人工智能数据挖掘第8页8.1数据挖掘概述数据仓库数据清理和数据挖掘数据清理差不多，假如数据在导入数据仓库时已经清理过，那很可能在做数据挖掘时就没必要在清理一次了，而且全部数据不一致问题都已经被处理了。数据挖掘库可能是数据仓库一个逻辑上子集，而不一定非得是物理上单独数据库。但假如数据仓库计算资源已经很担心，那最好还是建立一个单独数据挖掘库图8.1数据挖掘苦聪数据仓库中得出人工智能数据挖掘第9页8.1数据挖掘概述3.数据挖掘和在线分析处理（OLAP）数据挖掘和OLAP是完全不一样工具，基于技术也大相径庭。OLAP是决议支持领域一部分。传统查询和报表工具是告诉人们数据库中都有什么，OLAP则更深入告诉人们下一步会怎么样和假如人们采取这么办法又会怎么样。用户首先建立一个假设，然后用OLAP检索数据库来验证这个假设是否正确。数据挖掘与OLAP不一样地方是，数据挖掘不是用于验证某个假定模式（模型）正确性，而是在数据库中自己寻找模型。它在本质上是一个归纳过程。数据挖掘和OLAP含有一定互补性。在利用数据挖掘出来结论采取行动之前，可能要验证一下假如采取这么行动会带来什么样影响，那么OLAP工具能回答这些问题。

人工智能数据挖掘第10页8.1数据挖掘概述4.数据挖掘与机器学习和统计分析方法数据挖掘利用了人工智能（AI）和统计分析进步所带来好处。这两门学科都致力于模式发觉和预测。数据挖掘不是为了替换传统统计分析技术。相反，它是统计分析方法学延伸和扩展。大多数统计分析技术都基于完善数学理论和高超技巧，预测准确度还是令人满意，但对使用者要求很高。而伴随计算机计算能力不停增强，我们有可能利用计算机强大计算能力只经过相对简单和固定方法完成一样功效。一些新兴技术一样在知识发觉领域取得了很好效果，如神经元网络和决议树，在足够多数据和计算能力下，它们几乎不用人关照自动就能完成许多有价值功效。人工智能数据挖掘第11页8.1数据挖掘概述8.1.5数据挖掘内容

伴随DM和KDD研究逐步走向深入，数据挖掘和知识发觉研究已经形成了三根强大技术支柱：数据库、人工智能和数理统计。所以，KDD大会程序委员会曾经由这三个学科权威人物同时来任主席。当前DMKD主要研究内容包含基础理论、发觉算法、数据仓库、可视化技术、定性定量交换模型、知识表示方法、发觉知识维护和再利用、半结构化和非结构化数据中知识发觉以及网上数据挖掘等。数据挖掘所发觉知识最常见有以下四类。广义知识关联知识分类知识预测型知识人工智能数据挖掘第12页8.1数据挖掘概述8.1.6数据挖掘研究历史和现实状况

数据库中发觉知识（KDD）是在1989年召开第11届国际人工智能联合学术会议(IJCAI)上首次提出。在这届学术会议上举行了以KDD为主题学术研讨会，在1991年、1993年和1994年相继举行了KDD专题研讨会。伴随KDD深入研究以及KDD在许多领域成功应用，于1995年在加拿大召开了第一届知识发觉和数据挖掘国际学术会议，今后每年都召开大规模国际会议，其研究重点也逐步从发觉方法转向系统应用，重视各种发觉策略和技术集成，以及各种学科之间相互渗透。第一本关于DM和KDD国际学术杂志《DataMiningandKnowledgeDiscovery》也于97年3月创刊发行。亚太地域于1997年在新加坡召开了首次KDD研讨会，其后又在澳大利亚墨尔本召开了第二届，在中国北京召开了第三届。当前，在IJCAI、AAAI、VLDB、ACM-SIGMOD等代表人工智能与数据库技术研究最高水平国际学术会议上，数据挖掘和知识发觉研究都占有较大百分比，数据挖掘和知识发觉研究已经成为当今计算机科学与技术研究、应用热点领域之一。人工智能数据挖掘第13页8.2数据挖掘技术介绍

依据挖掘任务能够分为：分类和预测模型发觉、数据总结和聚类、关联规则发觉、序列模式发觉、相同模式发觉和混沌模式发觉等。依据挖掘对象来分，数据挖掘方法有面向关系数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、面向对象数据库、异质数据库以及WEB信息等。依据挖掘方法来分，数据挖掘方法可分为机器学习方法、统计方法、神经网络方法和数据库方法。其中机器学习可细分为归纳学习方法、基于范例学习、遗传算法等；统计方法可细分为回归分析、判别分析、聚类分析、探索性分析等；神经网络方法可细分为前向神经网络、自组织神经网络等；数据库方法主要是多维数据分析或联机分析方法，另外还有面向属性归纳方法。人工智能数据挖掘第14页8.2数据挖掘技术介绍

8.2.1分类和预测分类是数据挖掘中一项非常主要任务，当前在商业上应用最多。分类目标是提出一个分类函数或分类模型（也经常称作分类器），该模型能把数据库中数据项映射到给定类别中某一个。分类和回归都可用于预测，预测目标是从历史数据统计中自动推导出对给定数据推广描述，从而能对未来数据进行预测。分类效果普通和数据特点相关，有数据噪声大，有有缺省值，有分布稀疏，有字段或属性间相关性强，有属性是离散而有是连续值或混合式。当前普遍认为不存在某种方法能适合各种特点数据。下面介绍几个惯用分类算法。人工智能数据挖掘第15页8.2数据挖掘技术介绍

1．决议树结构一个决议树分类器通常分为两步：树生成和剪枝。树生成采取自上而下递归分治法。假如当前训练例子集合中全部实例是同类,结构一个叶节点,节点内容即是该类别。不然,依据某种策略选择一个属性,按照该属性不一样取值,把当前实例集合划分为若干子集合。对每个子集合重复此过程,直到当前集中实例是同类为止。剪枝就是剪去那些不会增大树错误预测率分枝。经过剪枝,不但能有效克服噪声,还使树变得简单,轻易了解。生成最优决议树一样是NP问题。当前决议树算法经过启发式属性选择策略来处理问题。人工智能数据挖掘第16页8.2数据挖掘技术介绍

2．AQ算法存在大量基于规则分类方法，以及对规则进行后处理如剪枝等工作。AQ是一个经典基于规则方法。AQ是一个覆盖算法，由Micalski和洪家荣提出。算法关键是所谓”星”。一个正例集合在反例集合背景下星是覆盖全部正例而排斥全部反例极大复合集合。算法就是要求得这么最大复合。算法从正例中一个种子一个选择子(属性值对)出发，逐步地增加选择子，直到找到覆盖全部正例最大复合。在最初AQ11基础上，AQ15增加了渐近学习，结构学习和近似推理等功效，成为比较成熟覆盖算法。人工智能数据挖掘第17页8.2数据挖掘技术介绍

3．Bayes方法贝叶斯统计分析起源于英国学者BayesT.R.一篇论文＂Anessaytowardssolvingaprobleminthedoctrineofchances＂(1763年),给出了著名贝叶斯公式和一个归纳推理方法。其后一些统计学家将其发展成一个系统统计推断方法，到本世纪30年代形成了贝叶斯学派，50~60年代发展成了一个有影响统计学派。贝叶斯方法学习机制是利用贝叶斯公式将先验信息与样本信息综合得到后验信息。在数据挖掘中，主要有两种bayes方法，即Naïve-bayes方法和bayes网络。前者直接利用bayes公式进行预测，把从训练样本中计算出各个属性值和类别频率比作为先验概率，并假定各个属性之间是独立，就能够用bayes公式和对应概率企业计算出要预测实例对各类别条件概率值。选取概率值最大类别作为预测值。此方法简单易行而且含有很好精度。人工智能数据挖掘第18页8.2数据挖掘技术介绍

4．神经网络神经网络是一个很好函数迫近工具，在过去十几年里取得了飞速发展，发展出了很多模型及其改进，比如BP、Hopfield、Kohonen、ART、RNN、KBANN、RBF等等。即使试验表明，神经网络在一些分类问题上含有比符号方法更加好表现，不过神经网络用于数据挖掘主要不利之处于于无法获取显式规则。近年来许多学者提出了从神经网络中提取规则方法，经典如KBANN等。主要能够分为三类方法：分解法、学习法以及这两种折衷方法人工智能数据挖掘第19页5．粗糙集粗糙集(RougnSet,RS)理论是一个刻划不完整性和不确定性数学工具，能有效地分析和处理不准确、不一致、不完整等各种不完备信息，并从中发觉隐含知识，揭示潜在规律，是由波兰科学家Z.Pawlak在1982年首先提出。粗糙集理论研究对象是由一个多值属性（特征、症状、特征等）级和描述一个对象集合，对于每个对象及其属性都有一个值作为其描述符号，对象、属性和描述符号是表示决议问题3个基本要素。通常关于对象可得到信息不一定足以划分其组员类别，换句话说，这种不准确性造成了对象不可分辨性。给定对象间一个等价关系，即造成由等价类组成近似空间不分明关系，Rough集就用不分明对象类形成上近似和下近似来描述。前者指是全部对象都一定被包含，后者指是全部对象可能被包含。8.2数据挖掘技术介绍

人工智能数据挖掘第20页8.2数据挖掘技术介绍

8.2.2聚类分析

聚类和数据挖掘中分类不一样，聚类是在预先不知道目标数据库到底有多少类情况下，希望将全部统计组成不一样类或者说聚类，而且使得在这种分类情况下，以某种度量为标准相同性，在同一聚类之间最小化，而在不一样聚类之间最大化。换句话说，聚类（clustering）是一个将数据集划分为若干组或类过程，并使得同一个组内数据对象含有较高相同度；而不一样组中数据对象是不相同。相同或不相同描述是基于数据描述属性取值来确定。通常就是利用（各对象间）距离来进行表示。许多领域，包含数据挖掘、统计学和机器学习都有聚类研究和应用。人工智能数据挖掘第21页8.2数据挖掘技术介绍

1.聚类分析概念

将一组物理或抽象对象，依据它们之间相同程度，分为若干组；其中相同对象组成一组，这一过程就称为聚类过程（clustering）。一个聚类就是由彼此相同一组对象所组成集合；不一样聚类中对象是不相同。就是从给定数据集中搜索数据项（items）之间所存在有价值联络。在许多应用，一个聚类中全部对象经常被看成一个对象来进行处理或分析等操作。人工智能数据挖掘第22页8.2数据挖掘技术介绍

2.聚类分析主要方法

在聚类分析中有大量算法可供选择。需要依据应用所包括数据类型、聚类目标以及详细应用要求来选择适当聚类算法。假如利用聚类分析作为描述性或探索性工具，那么就能够使用若干聚类算法对同一个数据集进行处理以观察可能取得相关（数据特征）描述。通常聚类分析算法能够划分为以下几大类：（1）划分方法（2）层次方法（3）基于密度方法（4）基于网格方法（5）基于模型方法人工智能数据挖掘第23页8.3关联规则挖掘关联规则概念是由Ｒ.Ａgrawal、Imieelinski和Swami提出来。在数据挖掘领域,关联规则挖掘有着广泛应用背景。关联规则挖掘目标就是从大量数据中挖掘出有价值描述数据项之间相互联络相关知识。伴随搜集和存放在数据库中数据规模越来越大，人们对从这些数据中挖掘对应关联知识越来越有兴趣。比如：从大量商业交易统计中发觉有价值关联知识就可帮助进行商品目录设计、交叉营销或帮助进行其它相关商业决议。人工智能数据挖掘第24页8.3关联规则挖掘8.3.1关联规则概述关联规则是描述在一个事件中不一样项之间同时出现规律知识模式，详细地针对一个事物数据库来说，关联规则就是经过量化数据描述某种物品出现对另一个物品出现有多大影响。关联规则挖掘研究含有以下发展趋势：一是从单一概念层次关联规则发觉发展到多概念层次关联规则发觉。也就是说在很多应用中，挖掘规则能够作用到数据库不一样层面上。比如，在分析超市销售事务数据库过程中，若单单从数据库原始字段，如面包、牛奶等等进行规则挖掘，可能极难发觉令人感兴趣规则。这时假如把一些抽象层次概念也考虑进去，比如面包、牛奶更抽象概念——食品，则有可能新更为抽象规则。所以研究在数据库中不一样抽象层次上发掘规则是数据挖掘新研究内容。人工智能数据挖掘第25页8.3关联规则挖掘二是提升算法效率。显然在挖掘规则过程中，需要处理大量数据库统计，而且可能对数据库统计进行屡次扫描，所以怎样提升算法效率是非常主要。当前共有三种提升效率思绪，一个技术是降低数据库扫描次数；另一个是利用采样技术，对要挖掘数据集合进行选择；最终是采取并行数据挖掘技术。另外，对获取关联规则总规模控制，即怎样选择和深入处理所取得关联规则；含糊关联规则获取和发觉；高效关联规则挖掘算法等也是关联规则要研究关键性课题。从采掘对象上看，由仅在关系数据库中进行挖掘扩充到在文本和web数据中进行关联发觉等课题也是未来关联规则挖掘要深入研究和处理问题。人工智能数据挖掘第26页8.3关联规则挖掘下面介绍关联规则挖掘过程中所包括到相关概念和术语。(1)数据项和数据项集设I={i1，i2，...，im}是n个不一样项目标集合,则每一个项目ik(ｋ=1,2,…,n)称为数据项(item)。Ｉ为数据项集(itemset),n为数据项集长度。长度为ｋ数据项集称为ｋ-项集(k-itemsets)。(2)事务一个事务Ｔ(Transaction)是数据项集Ｉ中一组项目标集合,即T

I。每一个事务赋予一个唯一标识符TID。全部事务全体就组成一个事务数据库Ｄ。(3)数据项集支持度数据项集支持度(Support)就是数据项集出现概率。设Ｘ是Ｉ中一个子集,称一个事务Ｔ包含Ｘ,当且仅当ＸＴ。Ｘ支持度为:Support(Ｘ)=Ｐ(Ｘ)人工智能数据挖掘第27页8.3关联规则挖掘(4)关联规则及其支持度和置信度一个关联规则就是含有“X→Y”形式蕴含式，其中有X

I，YI且X∩Y=

。Ｘ称作规则前提,Ｙ是结果。规则X→Y支持度为ｓ,是指在Ｄ中有ｓ%事务,既包含Ｘ同时又包含Ｙ,即同时出现数据项集Ｘ和Ｙ概率。其表示式为Support(X→Y)=P(X∩Y)。规则X→Y置信度(Confidence)为ｃ,是指在Ｄ中包含Ｘ事务有ｃ%事务同时又包含Ｙ,即出现数据项集Ｘ前提下,出现数据项集Ｙ概率,其表示式为confidence(X→Y)=P(Y∣X)。支持度表示了项目集Ｘ在交易集中出现频度,置信度表示了项目集Ｘ和Ｙ之间关联程度。（5）频繁项集一个项集出现频度就是整个交易数据集D中包含该项集交易统计数,若一个项集出现频度大于最小支持度阈值乘以交易统计集D中统计数，那么就称该项集满足最小支持度阈值；而满足最小支持度阈值所对应交易统计数就称为最小支持频度。人工智能数据挖掘第28页8.3关联规则挖掘满足最小支持阈值项集就称为频繁项集(或称大项集)。全部频繁k-项集集合就记为Lk。挖掘关联规则问题就是找出这么一些规则,它们Support和confidence分别大于用户指定最小支持度(minisupport)和最小置信度(miniconfidence)程度,称这些规则为强规则。通常为方便起见，都将最小支持度阈值简写为min_sup；最小信任度阈值简写为min_conf。这两个阈值均在0%到100%之间，而不是0到1之间。假如不考虑关联规则支持度和可信度，那么在事务数据库中存在无穷多关联规则。实际上，人们普通只对满足一定支持度和可信度关联规则感兴趣。所以，为了发觉出有意义关联规则，需要给定两个阈值:最小支持度和最小可信度。前者即用户要求关联规则必须满足最小支持度，它表示了一个项集在统计意义上需满足最低程度;后者即用户要求关联规则必须满足最小可信度，它反应了关联规则最低可靠度。人工智能数据挖掘第29页8.3关联规则挖掘挖掘关联规则主要包含以下二个步骤：步骤一：发觉全部频繁项集，依据定义，这些项集频度最少应等于（预先设置）最小支持频度；步骤二：依据所取得频繁项集，产生对应强关联规则。依据定义这些规则必须满足最小信任度阈值。另外还可利用有趣性度量标准来帮助挖掘有价值关联规则知识。因为步骤二中对应操作极为简单，所以挖掘关联规则整个性能就是由步骤一中操作处理所决定。人工智能数据挖掘第30页8.3关联规则挖掘8.3.2关联规则分类

（1）依据关联规则所处理变量类别来划分，关联规则可分为布尔型和数值型（2）依据规则中数据维数来划分，关联规则可分为单维和多维（3）依据规则中数据挖掘抽象层次来划分，能够分为单层关联规则和多层关联规则（4）依据关联规则所包括关联特征来进行分类划分关联挖掘可扩展到其它数据挖掘应用领域，如进行分类学习，或进行相关分析（即能够经过相关数据项出现或不出现来进行相关属性识别与分析）人工智能数据挖掘第31页8.3关联规则挖掘8.3.3经典关联规则挖掘算法

1．Apriori算法Apriori算法是挖掘产生布尔关联规则所需频繁项集基本算法；它也是一个很有影响关联规则挖掘算法。Apriori算法就是依据相关频繁项集特征先验知识而命名。该算法利用了一个层次次序搜索循环方法来完成频繁项集挖掘工作。这一循环方法就是利用k-项集来产生(k+1)-项集。详细做法就是：首先找出频繁1-项集，记为L1；然后利用L1来挖掘L2，即频繁2-项集；不停如此循环下去直到无法发觉更多频繁k-项集为止。每挖掘一层Lk就需要扫描整个数据库一遍。人工智能数据挖掘第32页8.3关联规则挖掘算法8.1：（Apriori）利用层次循环发觉频繁项集。输入：交易数据库D最小支持阈值min_sup输出：Li，D中频繁项集；处理流程：(1)L1=find_frequent_1_itemset(D)；//发觉1-项集(2)for(k=2;Lk-1≠;k++){(3)Ck=apriori-gen(Lk-1,min_sup);//依据频繁(k-1)-项集产生候选k-项集(4)foreacht

D{//扫描数据库，以确定每个候选项集支持频度(5)Ct=subset(Ck,t);//取得t所包含候选项集(6)foreachc

Ctc.count++;}(7)Lk={c

Ck|c.count

min_sup}(8)ReturnL=∪kLk;人工智能数据挖掘第33页8.3关联规则挖掘2.Apriori算法改进即使Apriori算法本身已经进行了一定优化，不过在实际应用中，还是存在不令人满意地方，于是人们相继提出了一个改进方法。下面介绍三种改进方法。(1)基于划分方法(2)基于HASH技术方法(3)基于采样技术方法人工智能数据挖掘第34页8.3.4多层关联规则挖掘对于很多应用来说，因为数据分布分散性，所以极难在数据最细节层次上发觉一些强关联规则。但我们引入概念层次后，就能够在就高层次上进行挖掘。即使较高层次得到规则可能是跟普通信息，不过对于一个用户来说是普通信息，对于另一个用户却未必如此。所以数据挖掘应该提供一个在多个层次上进行挖掘功效。多层关联规则挖掘基本上能够沿用“支持度-可信度”框架。普通地，能够采取自顶向下策略，由概念层1开始向下，到较低更特定概念层，对每个概念层分别计算频繁项集，直到不能再找到频繁项集。也就是说一旦找到概念层1全部频繁项集，开始在第2层找频繁项集，找出第2层全部频繁项集后，在开始找第3层，如此下去。对于每一层能够是用发觉频繁项集任何算法，如前面介绍Apriori算法及其任意变形。不过，在支持度设置问题上有一些又考虑东西。通常，依据规则中包括到层次，多层关联规则能够分为同层关联规则和层间关联规则。8.3关联规则挖掘人工智能数据挖掘第35页8.4序列模式挖掘序列模式挖掘是基于时间或者其它序列经常发生模式。序列模式挖掘与关联规则挖掘相同,其目标也是为了挖掘数据之间关系。但序列模式挖掘侧重点在于分析数据间前后序列关系。它能发觉数据库中形如“在某一段时间内,用户购置商品A,接着购置商品B,而后购置商品C,即序列A→B→C出现频度较高”之类知识。人工智能数据挖掘第36页8.4序列模式挖掘8.4.1序列模式概念及定义

1．数据源形式假设我们给定一个由客户交易(customertransaction)组成大型数据库D，每个交易(transaction)由客户号(customer-id)、交易时间(transaction-time)及在交易中购置项(item)组成。同一个用户在一个交易时间只能进行一次交易，我们不考虑用户在一次交易中所购置物品数量，每种物品都由一个二进制变量代替，只关心一个项目在交易中被购置是否。2．基本定义序列模式元素也能够不只是一个元素(如一本书)，它也能够是一个项集(itemset)。所谓项集，指是多个物品组成集合，内部元素不分排列次序，比如“枕头和枕头套”就能够看作是由两个项(item)组成项集，它也能够作为某一个序列模式元素。人工智能数据挖掘第37页8.4序列模式挖掘一个序列(sequence)是一列排好序项集。不失普通性我们假定项集中项由一些连续整数代替，这么一个项集i能够表示为(i1,i2…im)，而这里ij代表了一个项。一个序列s能够表示为<s1,s2…sn>，这里sj代表是一个项集。设有两个序列a<a1,a2…an>和b<b1,b2…bm>，假如存在整数i1<i2<…<in且a1包含于bi1，a2包含于bi2，…，an包含于bin，则称序列a包含于序列b。比如序列<(3)(4,5)(8)>包含于序列<(7)(3,8)(9)(4,5,6)(8)>，因为(3)包含于(3,8)，(4,5)包含于(4,5,6)以及(8)包含于(8)。不过序列<(3)(5)>不包含于<(3,5)>，反之亦然。前者表示项3和项5是先后购置，而后者则表示项3和项5是同时购置，这就是区分所在。在一个序列集(asetofsequences)中假如序列s不包含于任何其它序列中，则称序列s为最大(maximal)。人工智能数据挖掘第38页8.4序列模式挖掘一个客户全部事务(transactions)能够综合看成是一个序列，每一个事务都由对应一个项集来表示。事务按交易时间序排列就成了一个序列。我们称这么序列为客户序列(customer-sequence)。通常，将一个客户交易按交易时间排序成T1，T2，……，Tn。Ti中项集定义成itemset(Ti)。这么，这个客户客户序列就成了这么一个序列：〈itemset(T1)itemset(T2)…itemset(Tn)〉。如图8.6所表示。假如一个序列s包含于一个客户序列中，则我们称该客户支持(support)序列s。一个详细序列支持(support)定义为那一部分支持该序列客户总数。给定一个由客户交易组成数据库D，挖掘序列模式问题就是在那些含有客户指定最小支持度(minimumsupport)序列中找出最大序列(maximalsequence)。而每个这么最大序列就代表了一个序列模式(sequentialpattern)。人工智能数据挖掘第39页8.4序列模式挖掘8.4.2序列模式发觉

一个序列长度(length)是它所包含项集(itemset)总数。含有k长度序列称为k-序列。有两个序列x和y，x，y表示x和y经过连接运算形成新序列。一个项集i支持是指那一部分在单次交易中买了项集i中项那一部分客户。于是项集i和1-序列<i>含有相同支持。含有最小支持(minimumsupport)项集称为大项集(largeitemsetorlitemset)。需要注意是，大序列中每一个项集都必须含有最小支持。所以，任何大序列都是大项集列表所组成。分5个详细阶段来找出全部序列模式。其找出过程分为:排序阶段、大项集阶段、转换阶段、序列阶段和选最大阶段。人工智能数据挖掘第40页8.4序列模式挖掘8.4.3序列阶段算法序列阶段算法基本结构是对数据进行屡次遍历。在每次遍历中，我们从一个由大序列(largesequence)组成种子集(seedset)开始，利用这个种子集，能够产生新潜在大序列。在遍历数据过程中，我们计算出这些候选序列支持度，这么在一次遍历最终，我们就能够决定哪些候选序列是真正大序列，这些序列组成下一次遍历种子集。在第一次遍历前，全部在大项集阶段得到含有最小支持度(minimumsupport)大1-序列组成了种子集。这里给出两种算法，分别称为count-all和count-some。count-all累计全部大序列，包含非最大序列(non-maximalsequence)，在找最大阶段(maximalphase)，这些非最大序列必须被删除。给出一个count-all算法，称为AprioriAll，给出一个count-some算法，称为AprioriSome。人工智能数据挖掘第41页8