数据仓库与数据挖掘原理与应用-8-数据挖掘介绍

数据挖掘介绍 数据挖掘基本概念 近年来数据挖掘引起了人们的极大关注，其主要原因是： 存在大量的数据，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以广泛用于各种应用，包括商务管理、生产控制、市场分析、工程设计和科学探索等。 数据挖掘基本概念（续） 数据挖掘是信息技术自然演化的结果。 数据收集和 DB创建 机制的早期开发已成为稍后 数据管理 有效机制开发的必备基础，随着提供查询和事务处理的大量 DBS广泛付诸实践， 数据分析和理解 自然成为下一个目标。 数据挖掘基本概念（续） 这必将带来对强有力的数据分析工具的需求。实际上，面对快速增长的海量数据，没有强有力的工具，理解它们已远远超出了人们的能力。 回顾数据管理技术： DB技术 ： 能有效地存储数据和查询数据， 但不能有效地分析数据。 数据挖掘基本概念（续） DW与 OLAP技术： 具有汇总、合并和聚集功能，以及从不同的角度观察数据的能力。但只是客观、忠实地表现出用户想查询的众多因素分析汇总得出的报表，而报表的翻译将由用户判断。即缺乏对数据的深层次分析。 数据挖掘基本概念（续） DM技术： 特别强调挖掘隐藏在大型数据集中有趣的数据 模式 （知识、规律），用于决策过程控制、信息管理、查询处理等。不但分析数据，而且帮助用户得知原因，并预测未来。 模式：它给出了数据特性或数据之间的关系，是对数据所包含的信息更抽象的描述。 模式按功能可以分为预测型模式和描述型模式。 在实际应用中，可以细分为关联模式、分类模式、聚类模式和序列模式等。 数据库应用的规模和深度 点 线 在线分析处理 (OLAP) 在线事务处理 决策支持 (DS) (OLTP) 数据挖掘 (Data Mining) 数据挖掘基本概念（续） 因此，数据挖掘被普遍认为是非常有效的数据分析工具，是信息产业最重要的前沿之一，是最有前途的交叉学科。 数据挖掘基本概念（续） 数据挖掘涉及多学科技术的集成： DB技术，统计学，机器学习，高性能计算，模式识别，神经网络，数据可视化，信息检索，图象与信号处理和空间数据分析。数据挖掘基本概念（续） 广义观点： 数据挖掘是从存放在 DB， DW或其他信息库中的大量数据中挖掘有趣知识的过程。 “从数据中发现有用模式”历来有很多称法，如 : 数据挖掘 （ data mining） 知识提取 (knowledge extraction) 信息发现 (information discovery) 信息收获 (information harvesting) 数据考古 (data archaeology) 数据模式处理 (data pattern processing) “数据挖掘”的称法大部分是由统计学家，数据分析学家和 MIS团体使用的，在数据库领域也得到了广泛接受。 数据挖掘的发展 70 80年代：知识发现与数据挖掘结合 1989年 6月：在美国底特律举行了第一届“ 从数据库中 知识发现”的国际学术会议，在这次会议中第一次使用了 KDD 这个词来强调“知识”是数据驱动 (data-driven)发现的最终结果。 1995：加拿大召开第一届知识发现与数据挖掘国际学术会议 历届有关 KDD的学术会议 时间 会议名称 会议地点 接受论文数 提交 论文数 Jun.1989 Workshop on KDD Detroit,Michigan,USA 29 69 Jul.1991 Workshop on KDD Anaheim,California, USA 25 46 Jul.1993 Workshop on KDD Washington,USA 28 40 1995 KDD95 Montreal,Canada 40 135 Aug.1996 KDD96 Portland,Oregon,USA 45 220 Feb.1997 PAKDD97 Singapore 35 97 Aug.1997 KDD97 California,USA Apr.1998 PAKDD98 Melbourne,Australia Aug.1998 KDD98 New York,USA 数据挖掘的发展 数据挖掘技术的应用开发在国外已经迅速发展，许多大公司（如 Informix, Oracle, IBM等）都投入了巨资对其进行研究，并开发出了一些产品和原型，如 DBMiner、 Quest、 EXPLORA等。 第一本关于数据挖掘的国际学术杂志 Data Mining and Knowledge Discovery 于 1997年 3月创刊。 国内在这方面的研究起步比较晚，早期研究的方向多集中于关联规则的挖掘，近来关于时序模式、分类、聚类、 WEB数据挖掘等的研究也日益受到重视，并取得了不少可喜的成果，一些原型系统或数据挖掘工具已经研制成功并在不断完善中。 DM系统的体系结构 （ 1） DW 的步骤： 数据准备： 数据集成 数据选择 预分析 挖掘 表述 评价 （ 2） DW 系统的结构： 用户界面 结果输出 数据挖掘核心 知识库 数据仓库 数据库 文件系统 其他 数据源 ODBC或其他专用数据库接口 数据挖掘系统的结构 数据挖掘系统可以采用三层的 C/S结构： 第一层：为图形用户界面，位于系统的客户端； 第二层：为数据挖掘引擎，它是数据挖掘系统的核心，位于系统的应用服务器端； 第三层：为数据库与数据仓库，位于数据服务器端。 数据挖掘系统的结构 图形用户界面 该模块实现用户与数据挖掘系统之间的通信，允许用户与系统交互。用户可以通过图形化界面指定数据挖掘任务、输入有关信息，根据系统以可视化形式输出的数据挖掘的中间结果进行探索式的数据挖掘。此外，该模块还提供用户浏览数据库和数据仓库模式或数据结构、评价数据挖掘的模式等功能。 数据挖掘系统的结构 数据挖掘引擎 数据挖掘引擎是数据挖掘系统最基本、最重要的部分，是数据挖掘系统的核心。该部分由一系列功能模块组成，分别用于关联规则挖掘、分类规则挖掘、聚类规则挖掘、时序与序列数据挖掘和WEB数据挖掘等。 数据挖掘系统的结构 数据库与数据仓库 该部分位于数据服务器端，包括数据库、知识库、文件系统、其他数据源以及存放经过数据准备提取和集成后数据的数据仓库。在知识库中存放领域知识，用于搜索和对模式进行评价。 数据库与数据仓库服务器的功能是根据用户的数据挖掘请求，提取相应的数据供数据挖掘引擎使用。 数据挖掘概述 KDD定义 研究 选择目标 数据 数据 模式 应用 问题域 数据集 预处理 挖掘 解释与评价 KDD步骤 数据准备阶段：经过处理过的数据一般存储在数据仓库中。数据准备是否做得充分将影响到数据挖掘的效率和准确度以及最终模式的有效性。包括： 数据的选择：选择相关的数据 数据的净化：消除噪音、冗余数据 数据的推测：推算缺失数据 数据的转化：离散值数据与连续值数据之间的相互转换、数据值的分组分类、数据项之间的计算组合等 数据的缩减：减少数据量 数据挖掘的过程 数据挖掘的过程 挖掘阶段：该阶段是数据挖掘的核心步骤，也是技术难点所在。根据数据挖掘的目标，采用人工智能、集合论、统计学等方法，应用相应的数据挖掘算法，分析数据并通过可视化工具表述所获得的模式或规则。 数据挖掘的过程 评价阶段：在数据挖掘中得到的模式可能是没有实际意义或没有使用价值的，也有可能不能准确反映数据的真实意义，甚至在某些情况下是与事实相反的，因此需要评估，确定哪些是有效的、有用的模式。评估可以根据用户多年的经验，有些模式也可以直接用数据来检验其准确性。 数据挖掘的过程 巩固和运用阶段：用户理解的、并被认为是符合实际和有价值的模式形成了知识。同时还要对知识进行一致性检查，解决与以前得到的知识互相冲突、矛盾的地方，使知识得到巩固。运用知识有两种方法：一种是只需看知识本身所描述的关系或结果，就可以对决策提供支持；另一种是要求运用知识对新的数据进行分析，由此可能产生新的问题，而需要对知识作进一步的优化。 数据挖掘的数据源 1.关系数据库 2.数据仓库 3.事务数据库 数据挖掘的数据源（续） 空间数据库 时间数据库和时间序列数据库 文本数据库和多媒体数据库 异种数据库和遗产数据库 WWW 数据挖掘的功能 数据挖掘任务分两类： 描述式数据挖掘： 刻划 DB中数据的一般特性。 预测式数据挖掘： 在当前数据上进行推断，以进行预测。 数据挖掘的功能（续） 数据挖掘系统应具备： 能够挖掘多种类型的模式 能够发现各种粒度的模式 允许用户给出指示，指导或聚焦有趣模式的搜索。 1. 总结规则挖掘 它所要做的是从指定的大量数据中挖掘出（从不同的角度或在不同的层次上）平均值 /极小值 /极大值、总和、百分比等。挖掘结果运用交叉表、特征规则和统计的曲线图表等表示。 2. 关联规则挖掘 通过关联分析发现关联规则。即给定一组项和一个记录集合，通过分析记录集合，推导出项之间的相关性。 2. 关联规则挖掘（续） 典型的例子：购物篮分析，该过程通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯，通过了解哪些商品频繁地被顾客同时购买，用于制定营销政策。 3. 分类规则挖掘 在已知训练数据的特征和分类结果的基础上，为每一种类别找到一个合理的描述或模型，然后再用这些分类的描述或模型来对未知的新数据进行分类。 4. 群集规则挖掘 又称为无监督式的分类，其目的在于实事求是地、即客观地按被处理对象的特征分类，有相同特征的对象被归为一类。它与分类规则挖掘的区别在于：分类面向训练数据，而群集则直接对数据进行处理。 4. 群集规则挖掘（续） 在群集化作业中，我们并不需要事先定义好该如何分类，同时也不需要训练组的数据，数据是依靠本身的相似性而群集在一起，而群集的意义也是要靠事后的解释才能得知。 5. 预测分析 当分类工作偏向于插入漏掉的数据、预测数据分类或发展的趋势时，就是预测分析。 所有用来进行分类及估计的技术都可以经修正之后，通过已知变量数值的训练组数据来得到。 5. 预测分析（续） 其中历史数据就是很好的数据来源。历史数据可以用来建立模型，以检查近年来观察值的变化。若运用最新数据作为输入值，可以获得未来变化的预测值。 5. 预测分析（续） 像 “ 购物篮 ” 分析，就可以预测在超市中哪些商品总是会被同时购买。而经过修正后，也可以通过最新的更新数据来预测未来的购买行为。 6. 趋势分析 又称时间序列分析。描述行为随时间变化的对象的规律或趋势，并对其建模。 7. 偏差分析 又称比较分析，它找出一系列判别式的规则，以区别客户设置的两个不同类别。 8. 孤立点分析 DB中有些数据，它们与大多数数据的一般行为或模型不一致，称其为孤立点，大部分挖掘方法将孤立点视为噪声或异常而丢弃。而在一些应用中，罕见事件可能比正常出现的更有意义。 数据挖掘分类 数据挖掘有几种分类方法 1、根据挖掘的数据源类型分类 2、根据采用的挖掘技术分类 3、根据发现的知识类型分类 描述性挖掘 1、特征与比较描述 2、关联规则挖掘 3、聚类分析 预测性挖掘 1、数据分类 2、数值预测 数据挖掘方法 数据挖掘的主要方法及其重点如下： 1.统计分析方法 统计分析方法主要用于完成知识总结和关系型知识挖掘。对关系表中各属性进行统计分析，找到它们之间存在的关系。 1. 统计分析方法（续） 在关系表的属性间一般存在两种关系： 函数关系 相关关系 但确定性关系和相关关系之间并没有一道不可逾越的鸿沟。 1. 统计分析方法（续） 由于有测量误差等原因，确定性关系实际上往往通过相关关系呈现出来；当事物内部规律被得到了解时，相关关系又可能转化为确定性关系。 对它们可采用回归分析，相关分析，主成分分析等方法。 2. 决策树 决策树可用于分类，利用信息论中的信息增益寻找 DB中具有最大信息量的字节，建立决策树的一个结点，再根据字段的不同取值建立树的分支。在每个分支子集中重复建立下层结点和分支，便生成一棵决策树。 2. 决策树（续） 然后还要对决策树进行剪枝处理，最后将决策树转化为规则。运用这些规则，可以对新事例进行分类。 典型的决策树方法有：分类回归树，ID3、 C4.5、卡方自动归纳法、卡方自动互动侦测器等。 2. 决策树（续） 决策树可应用在监督式数据挖掘上，尤其是数据分类。它们能够将训练模块的记录区分为独立的子群，而其中子群都有自己的规律。 3. 人工神经网络 人工神经网络用于分类、群集、特征挖掘、预测和模式识别。 人工神经网络仿真生物神经网络，本质上是一个分散型或矩阵结构，它通过对训练数据的挖掘，逐步计算网络连接的加权值。人工神经网络可分为下列三种： 3. 人工神经网络（续） 前馈式网络 它以感应机、逆向传播模型、函数型网络为代表，可用于预测及模式识别等方面。 3. 人工神经网络（续） 反馈式网络 它以 Hopfield的离散模型和连续模型为代表，分别用于联想记忆和最优化计算。 自组织型网络 它以 ART模型、 Koholon模型为代表，用于群集。 3. 人工神经网络（续） 人工神经网络具有分散型或储存信息、平行处理信息和进行推理、自我组织和自我学习等特点，解决了众多以往方法很难解决的问题。 3. 人工神经网络（续） 它在多数应用中可以从训练数据组中学习，并产生归类和预测的模型。它也可以通过自我组织图和相关结构，应用于非监督或数据挖掘和时间原则分析，其新的应用及结构正在快速增加中。 4. 基因算法 基因算法用于分类、关系型规则挖掘等。基因算法模仿人工选择培育良种的思路，从一个初始规则集合开始，逐代地通过交换对象成员产生群体，评估并择优复制，优胜劣败，逐代积累计算，最终得到最优化的知识集。 5. 粗糙集 粗糙集用于数据简化、数据意义评估、对象相似性或共性分析、因果关系及范式挖掘等。粗糙集理论由 Z. Pawlak在 20世纪 80年代提出，用于处理不确定性。其主要思路如下： 5. 粗糙集（续） 把对象的属性分为条件属性和决策属性，按各个属性值相同划分成等价类。条件属性上的等价类 E与决策属性上的等价类Y之间有三种情况 : (1)下近似 Y包含 E； 5. 粗糙集（续） (2)上近似 Y和 E的交集并非空集合； (3)无关 Y和 E的交集为空集合。 对下近似建立确定性规则，对上近似建立不确定性规则（含可信度），而无关情况下不存在规则。 6. 联机分析处理技术 用具体图形将信息模式、数据的关联或趋势呈现给决策者，使客户能交互式地分析数据的关系，而 OLAP技术将人的观察力和智力融入挖掘系统中，极大地改善了系统挖掘的速度和深度。 6. 联机分析处理技术（续） “联机分析处理系统”是以多维数据库为基础。多维数据库是数据的典型代表，使得用户能深入数据内涵，了解重要的结论，它对数据转化成信息或知识非常有帮助。 数据挖掘系统 数据挖掘系统的结构 图形用户界面 模式解释与评价 数据挖掘引擎 数据源服务器 数据源 知识库 数据挖掘系统的设计 1、数据挖掘系统怎样与数据源集成 2、数据挖掘系统怎样指定目标数据集 3、数据挖掘系统怎样指定数据挖掘任务 4、数据挖掘系统怎样解释与评价模式 5、数据挖掘系统怎样利用领域知识 6、数据挖掘系统怎样提交知识 数据挖掘系统的发展 代 集成 算法 数据模型 数据处理 计算模型 代表 第一代 独立系统 支持一个或几个算法 支持向量数据 支持能够一次调入内存的数据 单机 CART 第二代 集成数据管理系统，包括数据库与数据仓库 支持多个算法 支持文本、媒体、对象数据 支持不能一次调入内存的大量、复杂数据 同质、局部计算机群 DBMiner 第三代 集成语言模型系统 支持多个算法 支持半结构化、Web数据 支持分布、异质的数据 Intranet/Extranet Clementine 第四代 集成移动等各种信息系统 支持多个算法 支持普遍存在的数据模型 支持移动等各种类型数据 移动等各种计算设备 数据挖掘的应用 1.企业界的数据挖掘 直效行销 顾客关系管理 交叉销售 信用评估 财务预测 2. 针对金融数据分析的数据挖掘 为多维数据分析和数据挖掘设计和构造 DW 贷款偿还预测和客户信用政策分析（特征选择和属性相关性计算） 2. 针对金融数据分析的数据挖掘 (续 ) 对目标市场客户的分类与聚类 洗黑钱和其他金融犯罪的侦破（可视化工具 ,链接分析工具 ,分类工具 ,聚类分析 ,孤立点分析 ,序列模式分析） 3. 零售业中的数据挖掘 基于数据挖掘的 DW的设计与构造 销售、顾客、产品、时间和地区的多维分析 促销活动的有效性分析（多维分析，关联分析） 3. 零售业中的数据挖掘 (续 ) 顾客保持力 顾客忠诚分析（序列模式分析） 购买推荐和商品参照（关联分析） 4. 电信业中的数据挖掘 电信数据的多维分析 盗用模式分析和异常模式识别 (多维分析，聚类分析，孤立点分析） 多维关联和序列模式分析 电信数据分析中 可视化工具的使用 数据预处理 数据清理 消除不完整 使用全局常量填充 使用属性平均值填充 使用相同类的属性平均值填充 使用最可能的值填充 消除噪声 通过平滑数据消除噪声 通过识别孤立点消除噪声 消除不一致 通过元数据消除不一致 数据集成 在数据集成时，有许多问题需要考虑 冗余：一个属性是冗余的，如果它能由另外的属性导出，如年薪。 有些冗余可以被相关分析检测到 重复 冲突检测和处理 BABAnBBAAr)1()(, 数据变换 最小 -最大规格化 零 -均值规格化 小数定标规格化 数据规约 属性规约 数据规约 记录规约 给定关系表、各个属性的概念层次树及属性阈值 步骤 根据属性 A的概念层次树，将关系表中 A的属性值转换为最底层的相应概念 统计关系表中 A的不同叶概念个数，如果 A的不同叶概念个数大于 A的属性阈值，再根据 A的概念层次树，将关系表中 A的叶概念转换为上一层的相应概念 如此重复，直至关系表中 A的不同概念个数小于等于 A的属性阈值 最后合并相同记录，并统计重复记录书目。 地名 气温 玉溪 18 通海 18 五华 17 安宁 16 曲靖 15 宣威 14 云南省 玉溪地区 曲靖地区 昆明市 玉溪市 通海县 五华区 安宁市 宣威市 曲靖市 -4040 -400 040 -40-20 -200 2040 020 地名 气温 count 玉溪地区 10-20 2 昆明市 10-20 2 曲靖地区 10-20 2 属性概念分层的自动生成 离散属性概念分层的自动生成 概念层次树中高层的概念个数一般少于低层的概念个数 统计属性不同值的个数 得到概念层次树结构，也称模式定义的概念分层 得到属性的概念层次树 例如：“地址”属性 连续属性概念分层的自动生成 例如：“气温”属性，取值区间是 【 -100， 100】 ，在区间上的属性值及记录数，如何生成属性的概念层次树 基于熵的离散化技术 属性值 -3 6 18 22 26 记录数 6 9 36 28 21 信息理论（ Information Theory）和熵（ Entropy） 1948年，香农（ C. E. Shannon）提出了信息论。 信息论的发展是以信息可以度量为基础的，度量信息的量称为信息量。 给出了关于信息量（ Information）和熵（ Entropy）的定义，熵实际上是系统信息量的加权平均，也就是系统的平均信息量。 掷骰子可表示为： 616161621)( XPX而某一天简单的天气气象则可表示为： 81814121)(x)(x)(x)(x)X(PX 4321雪雨阴晴根据香农信息的概念，消息中所包含的不确定性的成分才是信息，不确定性的成分越大，或者说出现的概率越小，信息量就越大 如果将信源输出 xi 所包含的信息量用I(xi)来表示，则其必须满足的条件是： I(xi)与输出 xi的概率相关； I(xi)是 P(xi)的减函数，且当 P(xi) =1时 I(xi) =0 。 I(xi)是 P(xi)的连续函数； 因此， xi 的信息量的定义为： )(lo g)( ixi xPxI 当对数底为 2时，自信息量的单位为比特(bit,binary unit)；对数底为 e时，其单位为奈特 (nat,nature unit)；对数底为 10时，其单位为哈特 (Hart, Hartley)。 目前的通信系统或其他信息传输系统大多以二进制为基础，因此信息量的单位以 bit最为常用。 )(lo g)( ii xPxI 以 bit为单位的信息量可记为： 信息量的性质 I(xi)是非负值； ),0)(l o g)(0,()(l o g1,0)(iiiixPxIxPxP故 I(xi)是随机量； I(xi)是 P(xi)的单调递减函数。 0)(l og)( l n)()(l og)()()(1,0)(iiiiiiiixPexPxdPdl bexPxdPdxdPxdIxP例 1，求掷骰子这一信源发出各种消息所包含的信息量。 解： 该信源的数学模型为 )(585.26l o g61l o g)1(l o g)1( b i tPI 616161621)X(PX)(585.2)1()6()5()4()3()2(b i tIIIIII同理，解： 该信源的数学模型为： 81814121)(x)(x)(x)(x)X(PX 4321雪雨阴晴例 2，求某一天简单的天气气象这一信源发出各种消息所包含的信息量。 )(12l o g21l o g)(l o g)( 11 b i txPxI )(24l o g41l o g)(l o g)( 22 b i txPxI )(38l o g81l o g)(l o g)( 33 b i txPxI )(38l o g81l o g)(l o g)( 44 b i txPxI 在布袋中放入 81枚硬币 ,它们外形完全相同 .已知有一枚硬币的重量与其他 80枚重量不同 .问随意取出的一枚恰好是重量不同的一枚硬币 ,并进一步确定它比其他硬币重还是轻所需要的信息量是多少 ? 信息理论（ Information Theory）和熵（ Entropy） 考虑一个任意的变量，它有两个不同的值 A和 B。假设已知这个变量不同值的概率分配，将估测该概率分配的不纯度。 情况 1 .如果 P（ A） = 1 和 P（ B） = 0，那么知道这个变量的值一定为 A，不存在不纯度，因此已知变量结果值不会带来任何的信息。 情况 2 .如果 P（ A） = P（ B） = 0.5，那么它的不纯度明显地高于 P（ A） = 0.1和 P（ B） =0.9的情况。在这种情况下，已知变量的结果值就会携带信息。 不纯度的最佳评估方法是平均信息量，也就是信息熵（ Entropy）： S = - (pi * log(Pi) 在上面的例子中，情况 1和情况 2的信息熵分别是： S1 = - ( 1 * log 1 + 0 * log 0) = 0 S2 = - ( 0.5 * log 0.5 +