数据挖掘原理.算法.技术

1． 时代的挑战 近十几年来,人们利用信息技术生产和搜集数据的能力大幅度提高,千千万万个数据库被用于商业管理、政府办公、科学研究和工程开发等等,这一势头仍将持续发展下去。于是,一个新的挑战被提了出来:在这被称之为信息爆炸的时代,信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没,从中及时发现有用的知识,提高信息利用率呢?要想使数据真正成为一个公司的资源,只有充分利用它为公司自身的业务决策和战略发展服务才行,否则大量的数据可能成为包袱,甚至成为垃圾。需要是发明之母，因此,面对"人们被数据淹没,人们却饥饿于知识"的挑战,数据挖掘和知识发现(DMKD)技术应运而生,并得以蓬勃发展,越来越显示出其强大的生命力。 这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。 2． 历史的必然 从商业数据到商业信息的进化过程中，每一步前进都是建立在上一步的基础上的。见下表。表中我们可以看到，第四步进化是革命性的，因为 从用户的角度来看，这一阶段的数据库技术已经可以快速地回答商业上的很多问题了。 从下表中还可以清晰得看到，数据挖掘的应运而生是历史必然的选择，它符合人类社会的认识事物的客观发展规律，仅从这一点上来讲，刚刚开始处于流行中的数据挖掘的前景还是非常乐观的。 进化阶段 商业问题 支持技术 产品厂家 产品特点 数据搜集 (60年代) “过去五年中我的总收入是多少？” 计算机、磁带和磁盘 IBM,CDC 提供历史性的、静态的数据信息 数据访问 (80年代) “在纽约的分部去年三月的销售额是多少？” 关系数据库（RDBMS），结构化查询语言（SQL），ODBC Oracle、Sybase、Informix、IBM、Microsoft 在记录级提供历史性的、动态数据信息 数据仓库；决策支持 (90年代) “在纽约的分部去年三月的销售额是多少？洛杉矶据此可得出什么结论？” 联机分析处理（OLAP）、多维数据库、数据仓库 Pilot、Comshare、Arbor、Cognos、Microstrategy 在各种层次上提供回溯的、动态的数据信息 数据挖掘 （正在流行） “下个月洛杉矶的销售会怎么样？为什么？” 高级算法、多处理器计算机、海量数据库 Pilot、Lockheed、IBM、SGI、其他初创公司 提供预测性的信息 3． 数据挖掘的定义 数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。还有很多和这一术语相近似的术语,如从数据库中发现知识(KDD)、数据分析、数据融合(Data Fusion)以及决策支持等。人们把原始数据看作是形成知识的源泉,就像从矿石中采矿一样。原始数据可以是结构化的,如关系数据库中的数据,也可以是半结构化的,如文本、图形、图像数据,甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的,也可以是非数学的;可以是演绎的,也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等,还可以用于数据自身的维护。因此,数据挖掘是一门非常广义的交叉学科,它汇聚了不同领域的研究者,尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。 简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于商业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。 数据挖掘是一种潜在的功能强大的新技术，它能帮助企业在他们的数据仓库中找到最重要的信息。数据挖掘工具能预测未来趋势和行为，使得商务活动具有前瞻性，并作出具有知识驱动的决策。数据挖掘所提供的自动的预期分析已经远远超出由典型的决策支持系统工具对过去事件所做的回顾性分析的范围。数据挖掘工具可以回答传统上需费很多时间解决的商务问题。它能搜遍数据库去查找隐藏的模式，找出那些专家也会错过的预测信息，因为它并不在人们期待的位置上； 数据挖掘(Data Mine)简称 DM，其本质就是发现数据实质与数据间的关系的探索过程，找出潜在于数据中的现实事务的规律和趋势，进而把感觉转化为事实。数据挖掘大致可分为三类：关系发现、模式发现、趋势行为发现。数据挖掘技术主要应用于决策支持系统(DSS)。 数据挖掘从技术上讲有如下几种： 神经网络(Neural Networks)、联系发现、分类(连续维?)、分簇(离散维?)、连续发现(基于时间的?)。另外的分法还会有：决策树(Decision Tree)、分类和衰退树(Classification And Regression Tree)、遗传算法(Genetic Algorithm)、规则归纳(Rules Induction)、最近邻居算法(Nearest Neighbor)。正方自动交互发现(Chi Square Automation Interactive Detection, CHAID)...... 数据挖掘技术的三大支柱 （1） 数据库技术。 （2） 人工智能技术。 （3） 概率与数理统计。 数据库技术已经从原始的文件处理发展到开发具有查询和事务处理的数据库管理系统。进一步的发展已经导致越来越需要有效的高级数据分析工具。这种需求是各种应用收集的数据爆炸性增长的必然结果，这些应用包括商务和管理、行政管理、科学和工程以及环境控制。 数据挖掘是从大量数据中发现有趣模式，其中数据可以存放在数据库、数据仓库或其他信息库中。这是一个年轻的跨学科领域，源于诸如数据库系统、数据仓库、统计学、机器学习、数据可视化、信息检索和高性能计算。其他有贡献的领域包括神经网络、模式识别、空间数据分析、图像数据库、信号处理和许多应用领域，如商务、经济学和生物信息学。 知识发现过程包括数据清理、数据集成、数据选择、数据变换、数据挖掘、模式评估和知识表示。 典型的数据挖掘系统结构包括数据库和/或数据仓库及相应的服务器，数据挖掘引擎和模式评估模块（二者与知识库交互），以及图形用户界面。作为一个整体，数据挖掘组件与数据库或数据仓库系统集成可能是不耦合、松散耦合、半紧密耦合或紧密耦合。一个设计良好的数据挖掘系统应当提供与数据库和/或数据仓库系统的紧密耦合或半紧密耦合。 数据模式可以从许多不同类型的数据库挖掘，如关系数据库、数据仓库、事务数据库和对象-关系数据库。有趣的数据模式也可以从其他类型的信息库中提取，包括空间的、时间序列的、序列的、文本的、多媒体的数据库和遗产数据库、数据流和万维网。 数据仓库是一种数据的长期存储储存库，这些数据来自多个数据源，经过组织数据仓库以有利于管理决策的方式组织。这些数据在一种一致的模式下存放，并且通常是汇总的。数据仓库提供一些数据分析能力，称作OLAP（联机分析处理）。 数据挖掘功能包括发现概念/类描述、关联和相关、分类、预测、聚类、趋势分析、离群点和偏差分析以及相似性分析。特征化和区分是数据汇总形式。 模式表示知识，如果它是易于理解的，在某种必然程度上对于检验数据是有效的，并且可能有用、新颖或者验证用户好奇的直觉。模式兴趣度度量，无论是客观的还是主观的，都可以用来指导发现过程。 数据挖掘系统可以根据所挖掘的数据库类型、所挖掘的知识类型、所使用的技术或应用加以区分。 我们研究了五种以数据挖掘查询形式说明数据挖掘任务的原语。这些原语说明任务相关的数据（即待挖掘的数据集）、挖掘的知识类型、背景知识（通常是概念分层形式）、兴趣度度量以及用来显示所发现模式的知识表示和可视化技术。 可以设计数据挖掘查询语言，支持即席的和交互的数据挖掘。数据挖掘查询语言（DMQL）应当提供说明每种数据挖掘原语的命令。这种查询语言是基于SQL的，并且可以最终形成标准，成为数据挖掘图形用户界面的基础。 数据预处理对于数据仓库和数据挖掘都是一个重要的问题，因为现实中的数据多半是不完整的、有噪声的和不一致的。数据预处理包括数据清理、数据集成、数据变换和数据规约。 描述性数据汇总为数据预处理提供分析基础。数据汇总的基本统计学度量包括度量数据集中趋势的均值、加权平均、中位数和众数，度量数据离散程度的极差、四分位数、四分位数间距、方差和标准差。图形表示，如直方图、盒图、分位数图、分位数-分位数图、散布图和散布图矩阵都有利于数据的视觉考察，因此对数据预处理和挖掘是有用的。 数据清理例程试图填补缺失的值，光滑噪声，识别离群点并纠正数据的不一致性。数据清理通常是一个迭代的两步过程，包括偏差检测和数据变换。 数据集成将来自不同数据源的数据整合成一致的数据存储。元数据、相关分析、数据冲突检测和语义异构性的解决都有助于数据的顺利集成。 数据变换例程将数据变换成适于挖掘的形式。例如：属性数据可以规范化，使得它们可以落在较小的区间，如0.0~1.0。 数据规约技术，如数据立方体聚集、属性子集选择、维度规约、数值规约和离散化都可以用来得到数据的规约表示，而使信息内容的损失最小。 数值数据的数据离散化和概念分层自动产生可能涉及诸如分箱、直方图分析、基于熵的离散化、X2分析、聚类分析和基于直观划分的离散化等技术。对于分类数据，概念分层可以根据定义分层的属性的不同值个数自动产生。 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聚类分析 数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括了划分方法，层次的方法，基于密度的方法和基于模型的方法。还有一些聚类算法继承了多种聚类方法的思想。 6.5概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的共性，它将大的任务相关的数据集从较低的概念层抽象到较高的概念层。大的数据集有效的，灵活的概化方法可以分成两类：1：数据立方体（或OLAP）方法，和2：面向属性的归纳方法。生成区别性描述的方法很多，如判定树方法、遗传算法等。 6.6偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意义的差别。