第1章 数据挖掘算法资料

第1章概述1.1从数据中获取知识1.2数据挖掘的基本概念1.3数据挖掘的发展历程1.4数据挖掘的功能和数据挖掘系统的分类1.5数据挖掘的过程1.6数据挖掘与其他学科的关系1.7数据挖掘的应用和发展趋势1.1从数据中获取知识知识是人类对客观世界的观察和了解，是人类对客观世界是什么、为什么、应该怎么做的认知，知识推动人类的进步和发展。人类所作出的正确判断和决策，以及采取正确的行动都是基于智慧和知识。数据是反映客观事物的数字、词语、声音和图像等，是可以进行计算加工的“原料”。数据是对客观事物的数量、属性、位置及其相互关系的抽象表示，适合于保存、传递和处理。面对大量的数据，迫使人们不断寻找新的工具，对规律进行探索，为决策提供有价值的信息。数据挖掘有助于发现趋势，揭示已知的事实，预测未知的结果。1.2数据挖掘的基本概念数据挖掘：是一种信息处理技术，从大量数据中自动分析并提取知识的技术。是一个处理过程，从大量数据中挖掘出隐含的、先前未知的、对决策有价值的知识的过程是通过仔细分析大量数据来揭示有意义的新的关系、模式和趋势的过程。数据挖掘所获取的知识:是以模型或数据概化的形式给出。数据挖掘技术:有许多种类，其方法都采用基于归纳的学习。数据挖掘的目的：从所获取的数据中发现新的、规律性信息和知识，辅助科学决策。1.2数据挖掘的基本概念说明：（1）数据量太小，常常无法反映出真实世界中的普遍特性，这样挖掘算法得出的结论不可靠。但并非小数据量就不可以进行挖掘，近年来研究者也提出了一些对小样本进行挖掘的方法，如支撑向量机方法就是基于小样本学习理论的非常实用的方法。（2）从理论上说，数据量越大越好。但随着数据量的增大，算法执行效率会越来越低，甚至无法计算。（3）在现实世界中，所获取数据往往具有不完全、有噪声、模糊、随机性等特点。当进行数据挖掘时，可以删除这些样本或记录，也可以采用一定的方法将这些缺失数据补上，或者使用可以自动处理缺失数据的算法。在实际工作中，还会遇到异常情况的干扰，使获得的数据偏离了真实值。这些问题，都需要在数据挖掘过程中予以解决。1.3数据挖掘的发展历程上世纪70年代，使用关系式数据库。上世纪60年代，计算机以文件方式对数据进行管理。在1989年8月第11届国际人工智能联合会议上，提出了数据挖掘的概念，即从数据库中的知识发现（KnowledgeDiscoveryinDatabase，KDD）。上世纪90年代开始，科研界习惯沿用KDD这个术语，而在商用领域，普遍采用了“数据挖掘”。1.3数据挖掘的发展历程特征数据挖掘算法集成分布计算模型数据模型第一代数据挖掘作为一个独立的应用支持一个或多个算法单独的系统单机向量数据第二代与数据库以及数据仓库集成多个算法：能够挖掘一次不能放进内存的数据数据管理系统，包括：数据库和数据仓库同质/局部区域的计算机群集有些系统支持对象、文本和连续的媒体数据第三代与预言模型系统集成多个算法数据管理和预言模型系统Internet/Extranet网络计算支持半结构化数据和Web数据第四代与移动数据/各种计算数据联合多个算法数据管理、预言模型、移动系统移动和各种计算设备普遍存在的计算模型数据挖掘系统的发展1.4数据挖掘的功能和数据挖掘系统的分类数据挖掘技术的基本任务主要体现在：分类与回归、聚类、关联规则发现、时序模式、异常检测1.4数据挖掘的功能和数据挖掘系统的分类分类与回归主要用于解决下列问题：1.4.1分类与回归如何将信用卡申请人分为低、中、高风险群。如何预测哪些顾客在未来半年内会取消该公司服务，哪些电话用户会申请增值服务。如何预测具有某些特征的顾客是否会购买一台新的计算机。如何预测病人应当接受三种具体治疗方案的哪一种。如何预测一位顾客在一次销售期间将花多少钱。如何预测银行可以安全地贷给贷款人的贷款量。使用2G通信网络的手机用户哪些有可能转换到3G通信网络。如何有效预测房地产开发中存在的风险。1.4数据挖掘的功能和数据挖掘系统的分类分类（Classification）是构造一个分类函数(分类模型)，把具有某些特征的数据项映射到某个给定的类别上。分类算法要求基于数据属性值来定义类别，通常通过已知所属类别的数据的特征来描述类别。分类过程由两步构成：模型创建和模型使用。模型创建是指通过对训练数据集的学习来建立分类模型；模型使用是指使用分类模型对测试数据和新的数据进行分类。其中的训练数据集是带有类标号的，也就是说在分类之前，要划分的类别是已经确定的。通常分类模型是以分类规则，决策树或数学表达式的形式给出。1.4.1分类与回归1.4数据挖掘的功能和数据挖掘系统的分类聚类分析主要用于解决下列问题：1.4.2聚类分析如何通过一些特定的症状归纳某类特定的疾病。谁是银行信用卡的黄金客户。谁喜欢打国际长途，在什么时间，打到那里。对住宅区进行聚类，确定自动提款机ATM的安放位置。如何对用户WAP上网行为进行分析，通过客户分群，进行精确营销。1.4数据挖掘的功能和数据挖掘系统的分类1.4.2聚类分析聚类就是将数据划分或分割成相交或者不相交的群组的过程，通过确定数据之间在预先指定的属性上的相似性就可以完成聚类任务。聚类的输入是一组未被标记的数据，根据数据自身的距离或相似度进行划分。划分的原则是保持最大的组内相似性和最小的组间相似性，也就是使得不同聚类中的数据尽可能地不同，而同一聚类中的数据尽可能地相似。聚类除了将样本分类外，还可以完成孤立点挖掘。1.4数据挖掘的功能和数据挖掘系统的分类关联规则主要用于解决下列问题：1.4.3关联规则商业销售上，如何通过交叉销售，以得到更大的收入。保险方面，如何分析索赔要求，发现潜在的欺诈行为。银行方面，如何分析顾客消费行业，以便有针对性的向其推荐感兴趣的服务。哪些制造零件和设备设置与故障事件关联。哪些病人和药物属性与结果关联。哪些商品是已经购买商品A的人最有可能购买的。1.4数据挖掘的功能和数据挖掘系统的分类关联规则（Association）揭示数据之间的相互关系，而这种关系没有在数据中直接表示出来。关联分析的任务就是发现事物间的关联规则，或称相关程度。关联规则的一般形式是：如果A发生，则B有百分之C的可能发生。C称为关联规则的置信度（Confidence）。常用的2种技术：关联规则，发现一个事物与其他事物间的相互关联性或相互依赖性；序列模式分析，重点放在分析数据之间的前后因果关系。1.4.3关联规则1.4数据挖掘的功能和数据挖掘系统的分类时序模式主要用于解决下列问题：1.4.4时序模式下个月的商品销量、销售额或库存量是多少。明天广州市的最高用电负荷是多少。时序模式是描述基于时间或其他序列的经常发生的规律或趋势，并对其建模。是用已知的数据预测未来的值，重点考虑数据之间在时间维度上的关联性，包含时间序列分析和序列发现。时间序列分析（TimeSeries）用已有的数据序列预测未来。数据的属性值是随着时间不断变化的。尤其要考虑时间周期的层次，如天、周、月、年等，有时还要考虑日历的影响，如节假日等。序列发现用于确定数据之间与时间相关的序列模式。这些模式与在数据（或者事件）中发现的相关的关联规则很相似，只是这些序列是与时间相关的。1.4数据挖掘的功能和数据挖掘系统的分类1.4.5异常检测异常是对差异和极端特例的表述，如分类中的反常实例、聚类外的离群值、不满足规则的特例等。大部分数据挖掘方法都将这种差异信息视为噪声而丢弃，然而在一些应用中，罕见的数据可能比正常的数据更有用。异常检测（OutlierDetection，也称为离群点检测）是用来发现与正常情况不同的异常和变化，并进一步分析这种变化是否是有意的诈骗行为，还是正常的变化。1.4数据挖掘的功能和数据挖掘系统的分类1.4.6数据挖掘系统的分类根据数据源类型分类：例如，有关系的、事务的、对象-关系的或数据仓库的挖掘系统。根据数据挖掘的功能分类：如特征提取、区分、关联和相关分析、分类、预测、聚类、异常检测和演变分析。根据所用的技术分类：用户交互程度（例如自动系统、交互探查系统、查询驱动系统；所用的数据分析方法（例如面向数据库或面向数据仓库的技术、机器学习、统计学、可视化、模式识别、神经网络等）根据应用分类：例如，金融、电信、股票市场、e-mail等。一般情况下，泛化的全能的数据挖掘系统可能并不适合特定领域的挖掘任务。1.5数据挖掘的过程1.5.1数据挖掘的一般流程数据挖掘的过程可以分为：明确问题、数据准备、数据挖掘、结果解释和评估。•明确问题：数据挖掘的首要工作是研究发现何种知识。•数据准备（数据收集和数据预处理）：数据选取、确定操作对象，即目标数据，一般是从原始数据库中抽取的组数据；数据预处理一般包括：消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换。•数据挖掘：确定数据挖掘的任务，例如：分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样的算法。•结果解释和评估：对于数据挖掘出来的模式，要进行评估，删除冗余或无关的模式。如果模式不满足要求，需要重复先前的过程，1.5数据挖掘的过程1.5.2跨行业数据挖掘标准过程跨行业数据挖掘标准过程CRISP-DM(CRoss-IndustryStandardProcessforDataMining)，1996年，三个公司（数据仓储供货商NCR、德国汽车航天公司Daimler-Chrysler、统计分析软件供货商SPSS）建立社团，目的是建立数据挖掘方法和过程的标准。获得了EC（EuropeanCommission）的资助，创建了CRISP-DM特别小组（SpecialInterestGroup，简称SIG）。1999年，SIG开发并提炼出CRISP-DM，同时在Mercedes-Benz和OHRA（保险领域）企业进行了大规模数据挖掘项目的实际试用。SIG组织目前在伦敦、纽约、布鲁塞尔已经发展到200多个成员。2000年，正式推出CRISP-DM1.0版。1.5数据挖掘的过程1.5.2跨行业数据挖掘标准过程数据理解数据业务理解数据准备建立模型实施评价和解释1.5数据挖掘的过程1.5.2跨行业数据挖掘标准过程CRISP-DM分为六个阶段和四个层次，这六个阶段的顺序是不固定的，经常需要前后调整。主要取决于每个阶段或是阶段中特定任务的产出物是否是下一个阶段必需的输入。图中箭头指出了最重要的和依赖度高的阶段关系。图中外圈象征数据挖掘自身是循环的，在一个解决方案发布之后一个数据挖掘的过程才可以继续。在这个过程中得到的知识可以触发新的，经常是更聚焦的问题。后续的过程可以从前一个过程得到益处。1.5数据挖掘的过程1.5.2跨行业数据挖掘标准过程(1)业务理解（BusinessUnderstanding）是对数据挖掘的需求进行了解确认，对目标有一个清晰明确的定义，针对不同的需求做深入的了解，将其转换成数据挖掘的问题，并拟定初步计划。在此阶段中，需要与企业各层次进行讨论，了解相关领域的有关情况，熟悉背景知识，对要解决的问题非常清楚和全面了解，明确到底想干什么，才能正确地针对问题拟定分析过程。1.5数据挖掘的过程1.5.2跨行业数据挖掘标准过程(2)数据理解（dataunderstanding）在明确了需要进行数据挖掘的预测目标后，要建立数据库与分析数据。在这个阶段必须先收集数据，了解数据的含义与特性，并过滤出所有可能有用的数据，然后进行数据整理并评估数据的质量，必要时再将分属不同数据库的数据加以合并或整合。1.5数据挖掘的过程1.5.2跨行业数据挖掘标准过程针对海量数据，要考虑下列问题：用哪些数据源，哪些数据与当前问题相关。取样数据是否满足数据挖掘目标，样本属性与挖掘目标之间是否存在相关性。如何保证取样数据的质量，是否在足够范围内有代表性。数据样本取多少合适，如何分类（训练集、验证集、测试集）。抽样数据是否存在明显的规律和趋势，数据是否存在周期性。样本数据是否按时间顺序排列，不同时间粒度数据是否存在明显分组。数据中是否