数据挖掘概念和技术读书笔记时代的挑战近十几年来,人们利用信息技术生产和搜集数据的能力大幅度提高,千千万万个数据库被用于商业管理、政府办公、科学研究和工程开发等等,这一势头仍将持续发展下去。于是,一个新的挑战被提了出来：在这被称之为信息爆炸的时代,信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没,从中及时发现有用的知识,提高信息利用率呢?要想使数据真正成为一个公司的资源,只有充分利用它为公司自身的业务决策和战略发展服务才行,否则大量的数据可能成为包袱,甚至成为垃圾。需要是发明之母，因此,面对人们被数据淹没,人们却饥饿于知识的挑战,数据挖掘和知识发现(DMKD)技术应运而生,并得以蓬勃发展,越来越显示出其强大的生命力。这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。2.历史的必然从商业数据到商业信息的进化过程中，每一步前进都是建立在上一步的基础上的。见下表。表中我们可以看到，第四步进化是革命性的，因为从用户的角度来看，这一阶段的数据库技术已经可以快速地回答商业上的很多问题了。从下表中还可以清晰得看到，数据挖掘的应运而生是历史必然的选择，它符合人类社会的认识事物的客观发展规律，仅从这一点上来讲，刚刚开始处于流行中的数据挖掘的前景还是非常乐观的。进化阶段商业问题支持技术产品厂家产品特点数据搜集(60年代)过去五年中我的总收入是多少?计算机、磁带和磁盘IBM,CDC提供历史性的、静态的数据信息数据访问(80年代)在纽约的分部去年三月的销售额是多少?关系数据库(RDBMS)，结构化查询语言(SQL)，ODBCOracle、Sybase、Informix、IBM、Microsoft在记录级提供历史性的、动态数据信息数据仓库；决策支持(90年代)在纽约的分部去年三月的销售额是多少?洛杉矶据此可得出什么结论?联机分析处理(OLAP)、多维数据库、数据仓库Pilot、Comshare、Arbor、Cognos、Microstrategy在各种层次上提供回溯的、动态的数据信息数据挖掘(正在流行)下个月洛杉矶的销售会怎么样?为什么?高级算法、多处理器计算机、海量数据库Pilot、Lockheed、IBM、SGI、其他初创公司提供预测性的信息3.数据挖掘的定义数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。还有很多和这一术语相近似的术语,如从数据库中发现知识(KDD)、数据分析、数据融合(Data Fusion)以及决策支持等。人们把原始数据看作是形成知识的源泉,就像从矿石中采矿一样。原始数据可以是结构化的,如关系数据库中的数据,也可以是半结构化的,如文本、图形、图像数据,甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的,也可以是非数学的；可以是演绎的,也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等,还可以用于数据自身的维护。因此,数据挖掘是一门非常广义的交叉学科,它汇聚了不同领域的研究者,尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于商业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。4.数据挖掘的知识分类4.1概化知识(Generalization)概化知识指类别特征的概括性描述知识。根据数据的微观特性发现其表征的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同性质，是对数据的概括、精炼和抽象。概化知识的发现方法和实现技术有很多，如数据立方体、面向属性的归约等。数据立方体还有其他一些别名，如多维数据库、实现视图、OLAP等。该方法的基本思想是实现某些常用的代价较高的聚集函数的计算，诸如计数、求和、平均、最大值等，并将这些实现视图储存在多维数据库中。既然很多聚集函数需经常重复计算，那么在多维数据立方体中存放预先计算好的结果将能保证快速响应，并可灵活地提供不同角度和不同抽象层次上的数据视图。另一种概化知识发现方法是加拿大SimonFraser大学提出的面向属性的归约方法。这种方法以类SQL语言表示数据挖掘查询，收集数据库中的相关数据集，然后在相关数据集上应用一系列数据推广技术进行数据推广，包括属性删除、概念树提升、属性阈值控制、计数及其他聚集函数传播等。4.2关联知识(Association)它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。最为著名的关联规则发现方法是R.Agrawal提出的Apriori算法。关联规则的发现可分为两步。第一步是迭代识别所有的频繁项目集，要求频繁项目集的支持率不低于用户设定的最低值；第二步是从频繁项目集中构造可信度不低于用户设定的最低值的规则。识别或发现所有频繁项目集是关联规则发现算法的核心，也是计算量最大的部分。4.3分类和聚类知识(Classification&Clustering)它反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知识。最为典型的分类方法是基于决策树的分类方法。它是从实例集中构造决策树，是一种有指导的学习方法。该方法先根据训练子集(又称为窗口)形成决策树。如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到窗口中，重复该过程一直到形成正确的决策集。最终结果是一棵树，其叶结点是类名，中间结点是带有分枝的属性，该分枝对应该属性的某一可能值。最为典型的决策树学习系统是ID3，它采用自顶向下不回溯策略，能保证找到一个简单的树。算法C4.5和C5.0都是ID3的扩展，它们将分类领域从类别属性扩展到数值型属性。数据分类还有统计、粗糙集(RoughSet)等方法。线性回归和线性辨别分析是典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。最近也有人研究使用神经网络方法在数据库中进行分类和规则提取，其中的代表就是向后传播分类。4.4预测型知识(Prediction)它根据时间序列型数据，由历史的和当前的数据去推测未来的数据，也可以认为是以时间为关键属性的关联知识。目前，时间序列预测方法有经典的统计方法、神经网络和机器学习等。1968年Box和Jenkins提出了一套比较完善的时间序列建模理论和分析方法，这些经典的数学方法通过建立随机模型，如自回归模型、自回归滑动平均模型、求和自回归滑动平均模型和季节调整模型等，进行时间序列的预测。由于大量的时间序列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化。因此，仅仅通过对某段历史数据的训练，建立单一的神经网络预测模型，还无法完成准确的预测任务。为此，人们提出了基于统计学和基于精确性的再训练方法，当发现现存预测模型不再适用于当前数据时，对模型重新训练，获得新的权重参数，建立新的模型。也有许多系统借助并行算法的计算优势进行时间序列预测。4.5偏差型知识(Deviation)-此外，还可以发现其他类型的知识，如偏差型知识(Deviation)，它是对差异和极端特例的描述，揭示事物偏离常规的异常现象，如标准类外的特例，数据聚类外的离群值等。所有这些知识都可以在不同的概念层次上被发现，并随着概念层次的提升，从微观到中观、到宏观，以满足不同用户不同层次决策的需要。5.数据挖掘的常用技术5.1人工神经网络仿照生理神经网络结构的非线形预测模型，通过学习进行模式识别。粗略的说，神经网络是一组连接的神经单元，其中每个连接都与一个权相联。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确类标号来学习。由于单元之间的连接，神经网络学习又称连接者学习。它的优点包括对噪声数据的高承受力，以及它对未经训练的数据分类模型的能力。5.2判定树什么是判定树?判定树(decision tree)是一个类似于流程图的树结构。它和算法与数据结构中的二叉判定树的概念很类似。其中每个内部节点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层界定就是根节点。5.3遗传算法基于进化理论，并采用遗传结合、遗传变异、以及自然选择等设计方法的优化技术。根据适者生存的原则，形成由当前群体中最合适的规则组成新的群体，以及这些规则的后代。典型情况下，规则的适合度(fitness)用它对训练样本集的分类准确率评估。后代通过使用诸如交叉和变异等遗传操作来创建。5.4最近邻算法将数据集合中每一个记录进行分类的方法。最临近分类是基于要求的或懒散的学习法，即它存放所有的训练样本，并且直到新的(未标记的)样本需要分类时才建立分类。它也可用于预测，即返回给定的位置样本的实数值预测。5.5Apriori算法它是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的名字基于这样的事实：算法使用频繁项集性质的先验知识。它用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。首先找出频繁1-项集的集合。然后利用前者找出2-项集的集合，如此迭代，直到不能找出频繁k-项集。最后由频繁项集产生关联规则。5.6频繁模式增长(FP-增长)和上面的方法相比，它是一种不产生候选的挖掘频繁项集的方法。它构造一个高度压缩的数据结构(FP-增长)，压缩原来的事物数据库。它聚焦于频繁模式增长，避免了高代价的候选产生，获得更好的效率。采用上述技术的某些专门的分析工具已经发展了大约十年的历史，不过这些工具所面对的数据量通常较小。而现在这些技术已经被直接集成到许多大型的工业标准的数据仓库和联机分析系统中去了。1.数据挖掘的功能数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下五类功能。6.1自动预测趋势和行为数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它可预测的问题包括预报破产以及认定对指定事件最可能作出反应的群体。6.2关联分析数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有置信度和支持度。6.3相关性分析数据中许多属性可能与分类和预测任务不相关。例如：记录银行贷款申请是星期几提出的数据可能与申请的成功不相关。此外，其他的属性可能是冗余的。因此，可以进行相关性分析，删除学习过程中不相关的或冗余的属性。在机器学习中，这一过程称为特征选择。6.4聚类分析数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括了划分方法，层次的方法，基于密度的方法和基于模型的方法。还有一些聚类算法继承了多种聚类方法的思