1、第八章 数据挖掘,人工智能,华中师范大学计算机科学系,第八章 数据挖掘,数据挖掘（Data Mining）是一个多学科交叉研究领域，它融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化等最新技术的研究成果。经过十几年的研究，产生了许多新概念和方法。特别是最近几年来，一些基本概念和方法趋于清晰，它的研究正向着更深入的方向发展。数据挖掘技术正在以一种全新的概念改变着人类利用数据的方式，它被认为是未来信息处理的骨干技术之一，网络之后的下一个技术热点。,8.1 数据挖掘概述,8.1.1数据挖掘的定义 数据挖掘（Data Mining）是一门受到来自
2、各种不同领域的研究者关注的交叉性学科，有很多不同的术语名称，除了常用的“数据挖掘”和“知识发现”之外，与数据挖掘相近的同义词有数据融合、数据分析、知识抽取、信息发现、数据采掘、知识获取、数据考古、信息收获和决策支持等。 从技术的角度讲，数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证
3、明，只要能支持特定的发现问题即可。实际上，利用数据挖掘从数据集中所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。,8.1 数据挖掘概述,从商业的角度讲，数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由于
4、各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯机会的商业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。,8.1 数据挖掘概述,8.1.2数据挖掘与数据库中的知识发现（1）KDD看成数据挖掘的一个特例 数据挖掘系统可以在关系数据库、事务数据库、数据仓库、空间数据库（Spatial Database）、文本数据（Text Data）以及诸如WEB等多种数据组织形式中挖掘知识，既然如此，那么可以说数据库中的知识发现只是数据挖掘的一个方面，这是早期比较流行的观点。因此，从这个意义说，数据
5、挖掘就是从数据库、数据仓库以及其它数据存储方式中挖掘有用知识的过程。这种描述强调了数据挖掘在源数据形式上的多样性。(2) 数据挖掘是KDD过程的一个步骤 在“知识发现96国际会议” 上，许多学者建议对这两个名词加以区分。核心思想是：KDD是从数据库中发现知识的全部过程，而Data Mining则是此全部过程的一个特定的、关键步骤，这种观点有它的合理性。虽然我们可以从数据仓库、WEB等源数据中挖掘知识，但是这些数据源都是和数据库技术相关的。数据仓库是由源数据库集成而来的，即使是像WEB这样的数据源恐怕也离不开数据库技术来组织和存储抽取的信息。因此KDD是一个更广义的范畴，它包括数据清洗、数据集成
6、、数据选择、数据转换、数据挖掘、模式生成及评估等一系列步骤。这样，我们可以把KDD看作是一些基本功能构件的系统化协同工作系统，而数据挖掘则是这个系统中的一个关键的部分。,8.1 数据挖掘概述,（3）KDD与Data Mining含义相同 也有些人认为，KDD与Data Mining只是叫法不一样，它们的含义基本相同。事实上，在现今的文献中，许多场合，如技术综述等，这两个术语仍然不加区分地使用着。也有人说，KDD在人工智能界更流行；Data Mining在数据库界使用更多。所以，从广义的观点，数据挖掘是从大型数据集（可能是不完全的、有噪声的、不确定性的、各种存储形式的）中，挖掘隐含在其中的、人们
7、事先不知道的、对决策有用的知识的过程。 从上面的描述中可以看出，数据挖掘概念可以在不同的技术层面上来理解，但是其核心仍然是从数据中挖掘知识。从本质来讲，数据挖掘与知识发现是有区别的，但是在很多场合人们往往不严格区分数据挖掘和数据库中的知识发现，两者互为使用。一般在科研领域中称为KDD，而在工程领域则多称为数据挖掘。,8.1 数据挖掘概述,8.1.3数据挖掘研究的理论基础 数据挖掘方法可以是基于数学理论的，也可以是非数学的；可以是演绎的，也可以是归纳的。从研究的历史看，它们可能是数据库、人工智能、数理统计、计算机科学以及其它方面的学者和工程技术人员，在数据挖掘的探讨性研究过程中创立的理论体系。1
8、997年，Mannila对当时流行的数据挖掘的理论框架给出了综述。结合最新的研究成果，有下面一些重要的理论框架可以帮助我们准确地理解数据挖掘的概念与技术特点。 模式发现架 规则发现架构 基于概率和统计理论 微观经济学观点 基于数据压缩理论 基于归纳数据库理论,8.1 数据挖掘概述,8.1.4数据挖掘与其它数据处理方法的区别及联系1数据挖掘与传统分析方法的区别 数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先未知，有效和可实用三个特征。 先前未知的信息是指该信息是预先未曾预料到的，既数据挖掘是要发
9、现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越有价值，在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系。2. 数据挖掘和数据仓库 大部分情况下，数据挖掘都要先把数据从数据仓库中拿到数据挖掘库或数据集市中（见图8.1）。从数据仓库中直接得到进行数据挖掘的数据有许多好处。,8.1 数据挖掘概述,数据仓库的数据清理和数据挖掘的数据清理差不多，如果数据在导入数据仓库时已经清理过，那很可能在做数据挖掘时就没必要在清理一次了，而且所有的数据不一致的问题都已经被解决了。数据挖掘库可能是数据仓库的一个逻辑上的子集，而不一
10、定非得是物理上单独的数据库。但如果数据仓库的计算资源已经很紧张，那最好还是建立一个单独的数据挖掘库,图8.1 数据挖掘苦聪数据仓库中得出,8.1 数据挖掘概述,3. 数据挖掘和在线分析处理（OLAP） 数据挖掘和OLAP是完全不同的工具，基于的技术也大相径庭。OLAP是决策支持领域的一部分。传统的查询和报表工具是告诉人们数据库中都有什么，OLAP则更进一步告诉人们下一步会怎么样和如果人们采取这样的措施又会怎么样。用户首先建立一个假设，然后用OLAP检索数据库来验证这个假设是否正确。 数据挖掘与OLAP不同的地方是，数据挖掘不是用于验证某个假定的模式（模型）的正确性，而是在数据库中自己寻找模型。
11、它在本质上是一个归纳的过程。 数据挖掘和OLAP具有一定的互补性。在利用数据挖掘出来的结论采取行动之前，也许要验证一下如果采取这样的行动会带来什么样的影响，那么OLAP工具能回答这些问题。,8.1 数据挖掘概述,4. 数据挖掘与机器学习和统计分析方法 数据挖掘利用了人工智能（AI）和统计分析的进步所带来的好处。这两门学科都致力于模式发现和预测。数据挖掘不是为了替代传统的统计分析技术。相反，它是统计分析方法学的延伸和扩展。大多数的统计分析技术都基于完善的数学理论和高超的技巧，预测的准确度还是令人满意的，但对使用者的要求很高。而随着计算机计算能力的不断增强，我们有可能利用计算机强大的计算能力只通过
12、相对简单和固定的方法完成同样的功能。 一些新兴的技术同样在知识发现领域取得了很好的效果，如神经元网络和决策树，在足够多的数据和计算能力下，它们几乎不用人的关照自动就能完成许多有价值的功能。,8.1 数据挖掘概述,8.1.5数据挖掘的内容 随着DM和KDD研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三根强大的技术支柱：数据库、人工智能和数理统计。因此，KDD大会程序委员会曾经由这三个学科的权威人物同时来任主席。目前DMKD的主要研究内容包括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以及网上数据挖掘等
13、。数据挖掘所发现的知识最常见的有以下四类。 广义知识 关联知识 分类知识 预测型知识,8.1 数据挖掘概述,8.1.6数据挖掘的研究历史和现状 数据库中发现知识（KDD）是在 1989 年召开的第 11 届国际人工智能联合学术会议 (IJCAI) 上首次提出的。在这届学术会议上举行了以 KDD 为主题的学术研讨会，在 1991 年、 1993 年和 1994 年相继举行了 KDD 专题研讨会。随着 KDD 的深入研究以及 KDD 在许多领域的成功应用，于 1995 年在加拿大召开了第一届知识发现和数据挖掘国际学术会议，此后每年都召开大规模的国际会议，其研究重点也逐渐从发现方法转向系统应用，注重
14、多种发现策略和技术的集成，以及多种学科之间的相互渗透。第一本关于 DM和KDD 的国际学术杂志 Data Mining and Knowledge Discovery 也于 97 年 3 月创刊发行。亚太地区于 1997 年在新加坡召开了首次 KDD 研讨会，其后又在澳大利亚的墨尔本召开了第二届，在中国北京召开了第三届。目前，在 IJCAI 、 AAAI 、 VLDB 、 ACM-SIGMOD 等代表人工智能与数据库技术研究最高水平的国际学术会议上，数据挖掘和知识发现的研究都占有较大的比例，数据挖掘和知识发现的研究已经成为当今计算机科学与技术研究、应用的热点领域之一。,8.2 数据挖掘技术简介
15、,根据挖掘的任务可以分为：分类和预测模型发现、数据总结和聚类、关联规则发现、序列模式发现、相似模式发现和混沌模式发现等。根据挖掘对象来分，数据挖掘方法有面向关系数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、面向对象数据库、异质数据库以及WEB信息等。根据挖掘方法来分，数据挖掘方法可分为机器学习方法、统计方法、神经网络方法和数据库方法。其中机器学习可细分为归纳学习方法、基于范例学习、遗传算法等；统计方法可细分为回归分析、判别分析、聚类分析、探索性分析等；神经网络方法可细分为前向神经网络、自组织神经网络等；数据库方法主要是多维数据分析或联机分析方法，另外还有面向属性的归纳方法。,8.2
16、 数据挖掘技术简介,8.2.1分类和预测 分类是数据挖掘中一项非常重要的任务，目前在商业上的应用最多。分类的目的是提出一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类和回归都可用于预测，预测的目的是从历史数据记录中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。 分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺省值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合各种特点的数据。下面介绍几种常用的分类算法。,8.2 数据挖掘技术简介,1决策树 构造一个决策树分
17、类器通常分为两步：树的生成和剪枝。树的生成采用自上而下的递归分治法。如果当前训练例子集合中的所有实例是同类的, 构造一个叶节点, 节点内容即是该类别。否则, 根据某种策略选择一个属性, 按照该属性的不同取值, 把当前实例集合划分为若干子集合。对每个子集合重复此过程, 直到当前集中的实例是同类的为止。剪枝就是剪去那些不会增大树的错误预测率的分枝。 经过剪枝, 不仅能有效的克服噪声, 还使树变得简单, 容易理解。生成最优的决策树同样是NP问题。 目前的决策树算法通过启发式属性选择策略来解决问题。,8.2 数据挖掘技术简介,2AQ算法 存在大量的基于规则的分类方法，以及对规则进行后处理如剪枝等工作。
18、AQ是一种典型的基于规则的方法。 AQ是一种覆盖算法，由Micalski和洪家荣提出。算法的核心是所谓的”星”。 一个正例集合在反例集合背景下的星是覆盖所有正例而排斥所有反例的极大复合的集合。算法就是要求得这样的最大复合。算法从正例中的一个种子的一个选择子(属性值对)出发，逐渐地增加选择子，直到找到覆盖所有正例的最大复合。在最初的AQ11基础上，AQ15增加了渐近学习，构造学习和近似推理等功能，成为比较成熟的覆盖算法。,8.2 数据挖掘技术简介,3Bayes方法 贝叶斯统计分析起源于英国学者Bayes T.R.的一篇论文An essay towards solving a problem in
19、 the doctrine of chances(1763年), 给出了著名的贝叶斯公式和一种归纳推理方法。 其后一些统计学家将其发展成一种系统的统计推断方法，到本世纪30年代形成了贝叶斯学派，5060年代发展成了一个有影响的统计学派。 贝叶斯方法的学习机制是利用贝叶斯公式将先验信息与样本信息综合得到后验信息。 在数据挖掘中，主要有两种bayes方法，即Nave-bayes方法和bayes网络。前者直接利用bayes公式进行预测，把从训练样本中计算出的各个属性值和类别频率比作为先验概率， 并假定各个属性之间是独立的，就可以用 bayes公式和相应的概率公司计算出要预测实例的对各类别的条件概率值
20、。选取概率值最大的类别作为预测值。此方法简单易行并且具有较好的精度。,8.2 数据挖掘技术简介,4神经网络 神经网络是一种很好的函数逼近工具，在过去十几年里取得了飞速的发展，发展出了很多的模型及其改进，例如BP、Hopfield、Kohonen、ART、RNN、KBANN、RBF等等。虽然试验表明，神经网络在某些分类问题上具有比符号方法更好的表现，但是神经网络用于数据挖掘主要不利之处在于无法获取显式的规则。近年来许多学者提出了从神经网络中提取规则的方法，典型的如KBANN等。主要可以分为三类方法：分解法、学习法以及这两种的折衷方法,5粗糙集 粗糙集(Rougn Set,RS)理论是一种刻划不完
21、整性和不确定性的数学工具，能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律，是由波兰科学家Z. Pawlak在1982年首先提出。粗糙集理论的研究对象是由一个多值属性（特征、症状、特性等）级和描述的一个对象集合，对于每个对象及其属性都有一个值作为其描述符号，对象、属性和描述符号是表达决策问题的3个基本要素。通常关于对象的可得到的信息不一定足以划分其成员类别，换句话说，这种不精确性导致了对象的不可分辨性。给定对象间的一种等价关系，即导致由等价类构成的近似空间的不分明关系，Rough集就用不分明对象类形成的上近似和下近似来描述。前者指的是所有对象都一定
22、被包含，后者指的是所有对象可能被包含。,8.2 数据挖掘技术简介,8.2 数据挖掘技术简介,8.2.2聚类分析 聚类和数据挖掘中的分类不同，聚类是在预先不知道目标数据库到底有多少类的情况下，希望将所有的记录组成不同的类或者说聚类，并且使得在这种分类情况下，以某种度量为标准的相似性，在同一聚类之间最小化，而在不同聚类之间最大化。换句话说，聚类（clustering）是一个将数据集划分为若干组或类的过程，并使得同一个组内的数据对象具有较高的相似度；而不同组中的数据对象是不相似的。相似或不相似的描述是基于数据描述属性的取值来确定的。通常就是利用（各对象间）距离来进行表示的。许多领域，包括数据挖掘、统
23、计学和机器学习都有聚类研究和应用。,8.2 数据挖掘技术简介,1.聚类分析概念 将一组物理的或抽象的对象，根据它们之间的相似程度，分为若干组；其中相似的对象构成一组，这一过程就称为聚类过程（clustering）。一个聚类就是由彼此相似的一组对象所构成的集合；不同聚类中对象是不相似的。就是从给定的数据集中搜索数据项（items）之间所存在的有价值联系。在许多应用，一个聚类中所有对象常常被当作一个对象来进行处理或分析等操作。,8.2 数据挖掘技术简介,2.聚类分析的主要方法 在聚类分析中有大量的算法可供选择。需要根据应用所涉及的数据类型、聚类的目的以及具体应用要求来选择合适的聚类算法。如果利用聚
24、类分析作为描述性或探索性的工具，那么就可以使用若干聚类算法对同一个数据集进行处理以观察可能获得的有关（数据特征）描述。通常聚类分析算法可以划分为以下几大类： （1）划分方法（2）层次方法（3）基于密度方法（4）基于网格方法（5）基于模型方法,8.3 关联规则挖掘,关联规则的概念是由.grawal、Imieelinski和Swami提出来的。在数据挖掘领域,关联规则的挖掘有着广泛的应用背景。关联规则挖掘目的就是从大量的数据中挖掘出有价值描述数据项之间相互联系的有关知识。随着收集和存储在数据库中的数据规模越来越大，人们对从这些数据中挖掘相应的关联知识越来越有兴趣。例如：从大量的商业交易记录中发现有
25、价值的关联知识就可帮助进行商品目录的设计、交叉营销或帮助进行其它有关的商业决策。,8.3 关联规则挖掘,8.3.1关联规则概述 关联规则是描述在一个事件中不同的项之间同时出现的规律的知识模式，具体地针对一个事物数据库来说，关联规则就是通过量化的数据描述某种物品的出现对另一种物品的出现有多大的影响。 关联规则的挖掘研究具有以下发展趋势：一是从单一的概念层次关联规则的发现发展到多概念层次的关联规则的发现。也就是说在很多应用中，挖掘规则可以作用到数据库的不同层面上。例如，在分析超市销售事务数据库过程中，若单单从数据库的原始字段，如面包、牛奶等等进行规则挖掘，可能很难发现令人感兴趣的规则。这时如果把一
26、些抽象层次的概念也考虑进去，比如面包、牛奶更抽象的概念食品，则有可能新的更为抽象的规则。所以研究在数据库中的不同的抽象层次上发掘规则是数据挖掘新的研究内容。,8.3 关联规则挖掘,二是提高算法效率。显然在挖掘规则过程中，需要处理大量的数据库记录，并且可能对数据库记录进行多次扫描，所以如何提高算法的效率是非常重要的。目前共有三种提高效率的思路，一种技术是减少数据库扫描次数；另一种是利用采样技术，对要挖掘的数据集合进行选择；最后是采用并行数据挖掘技术。 此外，对获取的关联规则总规模的控制，即如何选择和进一步处理所获得的关联规则；模糊关联规则的获取和发现；高效的关联规则挖掘算法等也是关联规则要研究的
27、关键性课题。从采掘的对象上看，由仅在关系数据库中进行挖掘扩充到在文本和web数据中进行关联的发现等课题也是未来关联规则挖掘要深入研究和解决的问题。,8.3 关联规则挖掘,下面介绍关联规则挖掘过程中所涉及到的有关概念和术语。(1)数据项和数据项集设I =i1，i2，.，im是n个不同项目的集合,则每一个项目ik(=1,2,n)称为数据项(item)。为数据项集(itemset),n为数据项集的长度。长度为的数据项集称为-项集(k-itemsets)。(2)事务一个事务(Transaction)是数据项集中的一组项目的集合,即TI。每一个事务赋予一个唯一的标识符TID。所有事务的全体就构成一个事务
28、数据库。(3)数据项集的支持度数据项集的支持度(Support)就是数据项集出现的概率。设是中的一个子集,称一个事务包含,当且仅当。的支持度为: Support ()=(),8.3 关联规则挖掘,(4)关联规则及其支持度和置信度 一个关联规则就是具有“ XY ”形式的蕴含式，其中有X I， Y I且XY= 。称作规则的前提,是结果。规则XY的支持度为,是指在中有%的事务,既包含同时又包含,即同时出现数据项集和的概率。其表达式为Support(XY)=P(XY)。规则XY的置信度(Confidence)为,是指在中包含的事务有%的事务同时又包含, 即出现数据项集的前提下,出现数据项集的概率,其表
29、达式为confidence(XY)=P(YX)。支持度体现了项目集在交易集中出现的频度,置信度体现了项目集和之间的关联程度。（5）频繁项集一个项集的出现频度就是整个交易数据集D中包含该项集的交易记录数, 若一个项集的出现频度大于最小支持度阈值乘以交易记录集D中记录数，那么就称该项集满足最小支持度阈值；而满足最小支持度阈值所对应的交易记录数就称为最小支持频度。,8.3 关联规则挖掘,满足最小支持阈值的项集就称为频繁项集(或称大项集)。所有频繁k-项集的集合就记为Lk。挖掘关联规则的问题就是找出这样一些规则,它们的Support和confidence分别大于用户指定的最小支持度(minisuppo
30、rt)和最小置信度(miniconfidence)的限度,称这些规则为强规则。通常为方便起见，都将最小支持度阈值简写为min_sup；最小信任度阈值简写为min_conf。这两个阈值均在0%到100%之间，而不是0到1之间。 如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷多的关联规则。事实上，人们一般只对满足一定的支持度和可信度的关联规则感兴趣。因此，为了发现出有意义的关联规则，需要给定两个阈值:最小支持度和最小可信度。前者即用户规定的关联规则必须满足的最小支持度，它表示了一个项集在统计意义上的需满足的最低程度;后者即用户规定的关联规则必须满足的最小可信度，它反应了关联规则的最
31、低可靠度。,8.3 关联规则挖掘,挖掘关联规则主要包含以下二个步骤：步骤一：发现所有的频繁项集，根据定义，这些项集的频度至少应等于（预先设置的）最小支持频度；步骤二：根据所获得的频繁项集，产生相应的强关联规则。根据定义这些规则必须满足最小信任度阈值。 此外还可利用有趣性度量标准来帮助挖掘有价值的关联规则知识。由于步骤二中的相应操作极为简单，因此挖掘关联规则的整个性能就是由步骤一中的操作处理所决定。,8.3 关联规则挖掘,8.3.2关联规则的分类 （1）根据关联规则所处理的变量的类别来划分，关联规则可分为布尔型和数值型（2）根据规则中数据的维数来划分，关联规则可分为单维的和多维的（3）根据规则中
32、数据挖掘的抽象层次来划分，可以分为单层关联规则和多层关联规则（4）根据关联规则所涉及的关联特性来进行分类划分 关联挖掘可扩展到其它数据挖掘应用领域，如进行分类学习，或进行相关分析（即可以通过相关数据项出现或不出现来进行相关属性识别与分析）,8.3 关联规则挖掘,8.3.3经典关联规则挖掘算法 1Apriori算法 Apriori算法是挖掘产生布尔关联规则所需频繁项集的基本算法；它也是一个很有影响的关联规则挖掘算法。Apriori算法就是根据有关频繁项集特性的先验知识而命名的。该算法利用了一个层次顺序搜索的循环方法来完成频繁项集的挖掘工作。这一循环方法就是利用k-项集来产生(k+1)-项集。具体
33、做法就是：首先找出频繁1-项集，记为L1；然后利用L1来挖掘L2 ，即频繁2-项集；不断如此循环下去直到无法发现更多的频繁k-项集为止。每挖掘一层Lk就需要扫描整个数据库一遍。,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) for
34、each t D /扫描数据库，以确定每个候选项集的支持频度(5) Ct = subset( Ck, t ); /获得t所包含的候选项集(6) for each c Ct c.count + ; (7) Lk = c Ck | c.count min_sup(8) Return L=k Lk ;,8.3 关联规则挖掘,2. Apriori算法的改进 虽然Apriori算法自身已经进行了一定的优化，但是在实际应用中，还是存在不令人满意的地方，于是人们相继提出了一个改进的方法。下面介绍三种改进方法。(1)基于划分的方法(2)基于HASH技术的方法(3)基于采样技术的方法,8.3.4多层关联规则挖掘
35、 对于很多应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。但我们引入概念层次后，就可以在就高的层次上进行挖掘。虽然较高层次得到的规则可能是跟普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供一种在多个层次上进行挖掘的功能。 多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。一般地，可以采用自顶向下策略，由概念层1开始向下，到较低的更特定的概念层，对每个概念层分别计算频繁项集，直到不能再找到频繁项集。也就是说一旦找到概念层1的所有频繁项集，开始在第2层找频繁项集，找出第2层所有频繁项集后，在开始找第3层，如此下去。
36、对于每一层可以是用发现频繁项集的任何算法，如前面介绍的Apriori算法及其任意变形。不过，在支持度的设置问题上有一些又考虑的东西。通常，根据规则中涉及到的层次，多层关联规则可以分为同层关联规则和层间关联规则。,8.3 关联规则挖掘,8.4 序列模式挖掘,序列模式挖掘是基于时间或者其它序列的经常发生的模式。序列模式挖掘与关联规则挖掘相似, 其目的也是为了挖掘数据之间的关系。但序列模式挖掘侧重点在于分析数据间的前后序列关系。它能发现数据库中形如“在某一段时间内, 顾客购买商品A , 接着购买商品B , 而后购买商品C , 即序列A B C 出现的频度较高”之类的知识。,8.4 序列模式挖掘,8.
37、4.1序列模式的概念及定义 1数据源的形式 假设我们给定一个由客户交易(customer transaction)组成的大型数据库D，每个交易(transaction)由客户号(customer-id)、交易时间(transaction-time)及在交易中购买的项(item)组成。同一个顾客在一个交易时间只能进行一次交易，我们不考虑顾客在一次交易中所购买物品的数量，每种物品都由一个二进制变量代替，只关心一个项目在交易中被购买与否。2基本定义 序列模式的元素也可以不只是一个元素(如一本书)，它也可以是一个项集(item set)。所谓项集，指的是多个物品组成的集合，内部元素不分排列顺序，比如“
38、枕头和枕头套”就可以看作是由两个项(item)组成的项集，它也可以作为某一个序列模式的元素。,8.4 序列模式挖掘,一个序列(sequence)是一列排好序的项集。不失一般性我们假定项集中的项由一些连续整数代替，这样一个项集i可以表示为(i1,i2im)，而这里的ij代表了一个项。一个序列s可以表示为，这里的sj代表的是一个项集。 设有两个序列a 和b ，如果存在整数i1包含于序列，因为(3)包含于(3,8)，(4,5)包含于(4,5,6)以及(8)包含于(8)。但是序列不包含于，反之亦然。前者表示项3和项5是先后购买的，而后者则表示项3和项5是同时购买的，这就是区别所在。在一个序列集(a s
39、et of sequences)中如果序列s不包含于任何其他序列中，则称序列s为最大的(maximal)。,8.4 序列模式挖掘,一个客户所有的事务(transactions)可以综合的看成是一个序列，每一个事务都由相应的一个项集来表示。事务按交易时间序排列就成了一个序列。我们称这样的序列为客户序列(customer-sequence)。通常，将一个客户的交易按交易时间排序成T1 ，T2 ，Tn。Ti中的项集定义成itemset(Ti)。这样，这个客户的客户序列就成了这样的一个序列：itemset(T1) itemset(T2) itemset(Tn)。如图8.6所示。 如果一个序列s包含于一
40、个客户序列中，则我们称该客户支持(support)序列s。一个具体序列的支持(support)定义为那一部分支持该序列的客户总数。 给定一个由客户交易组成的数据库D，挖掘序列模式的问题就是在那些具有客户指定最小支持度(minimum support)的序列中找出最大序列(maximal sequence)。而每个这样的最大序列就代表了一个序列模式(sequential pattern)。,8.4 序列模式挖掘,8.4.2序列模式的发现 一个序列的长度(length)是它所包含的项集(itemset)的总数。具有k长度的序列称为k-序列。有两个序列x和y，x，y表示x和y经过连接运算形成的新的序
41、列。 一个项集i的支持是指那一部分在单次交易中买了项集i中的项的那一部分客户。于是项集i和1-序列具有相同的支持。具有最小支持(minimum support)的项集称为大项集(large itemset or litemset)。需要注意的是，大序列中的每一个项集都必须具有最小支持。因此，任何大序列都是大项集的列表所组成。 分5个具体阶段来找出所有的序列模式。其找出过程分为: 排序阶段、大项集阶段、转换阶段、序列阶段和选最大阶段。,8.4 序列模式挖掘,8.4.3序列阶段的算法 序列阶段算法的基本结构是对数据进行多次遍历。在每次遍历中，我们从一个由大序列(large sequence)组成的
42、种子集(seed set)开始，利用这个种子集，可以产生新的潜在的大序列。在遍历数据的过程中，我们计算出这些候选序列的支持度，这样在一次遍历的最后，我们就可以决定哪些候选序列是真正的大序列，这些序列构成下一次遍历的种子集。在第一次遍历前，所有在大项集阶段得到的具有最小支持度(minimum support)的大1-序列组成了种子集。 这里给出两种算法，分别称为count-all和count-some。count-all 累计所有大序 列，包括非最大序列(non-maximal sequence)，在找最大阶段(maximal phase)，这些非最大序列必须被删除。给出一个count-all算
43、法，称为AprioriAll，给出一个count-some算法，称为AprioriSome。,8.5 WEB挖掘,8.5.1概述 随着Internet的日益普及，人们通过Web接触到了比以前多得多的数据和信息。然而，尽管Web上有海量的数据，但由于Web页面过于复杂、而且是无结构的、动态的，导致人们难以迅速、方便地在Web上找到所需要的数据和信息。在面临如此庞大的信息空间以及Web组织无序化的情况下，搜索是解决网络信息无序和混乱的一个基本方法，现代社会的竞争趋势要求能够对这些信息进行实时和深层次的分析，因此，如何利用数据挖掘知识，进一步提高Web信息搜索的性能成为众多学者研究的热点。 Web挖
44、掘就是从Web文档和Web活动中抽取感兴趣的、潜在的有用模式和隐藏的信息。Web挖掘可以在确定权威页面、Web文档分类、Web Log挖掘、智能查询等在很多方面发挥作用。 与传统数据挖掘技术所面对的数据相比，Web挖掘的数据源具有以下特点：,8.5 WEB挖掘,（1）对有效的数据仓库和数据挖掘而言，Web似乎太庞大了。Web的数据量目前以Terabytes计算，而且仍然在迅速地增长。这使得几乎不可能去构造一个数据仓库来复制、存储或集成Web上的所有数据。 （2）Web页面的复杂性高于任何传统的文本文档。Web页面缺乏统一的结构，它包含了远比任何一组书籍或文本文档多得多的风格和内容。（3）Web
45、是一个动态性极强的信息源。Web不仅以极快的速度增长，而且其信息还在不断地发生着更新。新闻、股票市场、公司广告和Web服务中心都在不断地更新着各自的页面。链接信息和访问记录也在频繁地更新之中。（4）Web面对的是一个广泛的形形色色的用户群体。目前因特网用户在不断的快速增加，各个用户可以有不同的背景、兴趣和使用目的。大部分的用户并不了解信息网络结构，不清楚搜索的高昂代价，极易在网络中迷失方向，也极易在跳跃式的访问中烦乱不已和在等待中失去耐心。因此web挖掘应能根据不同的用户提供个性化的服务。,8.5 WEB挖掘,（5）web上的信息只有很小的一部分是相关的或有用的。因为每个用户可能只关心很小的对
46、自己有用的一部分信息，其余的信息对这个用户来说就是不感兴趣的，而且会淹没所希望搜索的结果。 Web 是一个巨大的、广泛分布的、异构的、半结构的、超文本P超媒体的、相互联系并且不断变化的信息仓库, 其中包括链接信息、访问使用信息等。这大量的非结构化数据是无法使用现有数据库管理系统来处理和管理的, 这就对Web 进行有效的信息抽取和知识发现带来了极大的挑战, 也使得Web 数据挖掘更加复杂。 web上的信息的多样性决定了web数据挖掘的多样性。按照处理对象的不同我们将web数据挖掘分为三大类：Web内容挖掘、Web结构挖掘和Web使用记录挖掘。,8.6 数据挖掘的研究热点与发展趋势,8.6.1研究热点 随着网络技术和数据挖掘技术的发展，从应用的角度来看，目前有这样一些研究热点：网站的数据挖掘、生物信息和DNA数据分析的数据挖掘、文本数据挖掘等几个方面。 1电子商务网站的数据挖掘 2生物信息和DNA数据分析的数据挖掘 3文本数据挖掘,8.6 数据挖掘的研究热点与发展趋势,8.6.2发展趋势研究焦点可能会集中到以下几个方面。（1）数据挖掘语言的标准化（2）可视化数据挖掘（3）Web 挖掘（4）复杂数据类型挖掘的新方法（5）交互式发现（6）可伸缩的数据挖掘方法（7）数据挖掘与数据库系统、数据仓库系统和Web 数据库系统的集成（8）数据挖掘中的隐私保护与信息安全（9）应用的探索,
