当前位置： >>
数据挖掘中的数据预处理
内容提要随着社会的发展和数据库的应用，各领域的应用数据库中都积累 了大量的历史数据。如何利用这些有潜在价值的数据，从中提取出有 用的信息和知识，是应用者日益关注的问题，也是数据挖掘技术的关 键所在。要进行数据挖掘，首先要保证数据质量，良好的数据能提高 数据挖掘效果和效率，数据预处理逐渐成为数据挖掘不可缺少的重要 前提。 在数据挖掘的过程中如果只着眼于数据挖掘算法
的探讨，而忽视 了对数据预处理的研究，在一定程度上往往会失去数据挖掘的某些重 要意义。因为实际系统中的数据一般都具有不完整性、冗余性和模糊 性，很少能直接满足数据挖掘算法的要求。另外，海量的数据中无意 义的成分很多，严重影响了数据挖掘算法的执行效率，而且由于其中 的噪音干扰还会造成挖掘结果的偏差。因此，对不理想的原始数据进 行有效的归纳和预处理，已经成为数据挖掘系统实现过程中的关键问 题。 本文通过对数据挖掘、数据预处理技术和理论的学习，以及对国 内 外 数 据 挖 掘 与 数 据 预 处 理 系 统 的 发 展 情 况 的 研 究 ，归 纳 总 结 了 国 内 、 外数据挖掘系统中数据预处理的特点，根据当今数据挖掘技术和数据 挖掘系统的发展趋势，设计了一个数据预处理系统，该软件设计实现 的预处理系统主要包括数据预处理过程中最常用、最直接、最有效的 和 有 一 定 通 用 价 值 的 维 规 约 、聚 集 、过 滤 异 常 值 、去 掉 重 复 记 录 处 理 ， 软件在一定程度上实现了对大量数据的清洗工作，为进一步数据挖掘 提供了可靠的数据保障。关 键 词 ：数 据 挖 掘 数 据 预 处 理 维 规 约 聚 集 过 滤 异 常 值 重 复 记 录 处 理目内容提要 第一章 绪录论......................................................................................................... 11.1 引言................................................................................................................... 1 1.2 数据挖掘（DATA MINING）............................................................................. 1 1.3 数据挖掘与知识发现简介............................................................................... 2 1.4 数据挖掘系统简介........................................................................................... 6 1.5 本文的主要内容............................................................................................. 12 第二章 国内外数据挖掘系统介绍....................................................................... 132.1 国外数据挖掘系统......................................................................................... 13 2.2 国内数据挖掘系统......................................................................................... 15 2.3 国内数据挖掘系统的发展环境及趋势......................................................... 17 2.4 本章小结......................................................................................................... 20 第三章 数据预处理简介....................................................................................... 213.1 数据预处理..................................................................................................... 21 3.2 数据清洗(DATA CLEANSING) ........................................................................... 22 第四章 数据预处理方法....................................................................................... 284.1 数据预处理方式............................................................................................. 28 4.2 发现异常......................................................................................................... 29 4.3 识别重复记录................................................................................................. 30 第五章 软件实现数据预处理............................................................................... 325.1 系统的总体框架及流程................................................................................. 32 5.2 系统的功能模块及实现情况......................................................................... 341第六章全文总结................................................................................................... 546.1 结论和展望..................................................................................................... 54 参考文献................................................................................................................... 56 摘 要ABSTRACT 致 谢导师及作者简介2吉林大学硕士学位论文第一章1.1 引言绪论数据作为现代企业的宝贵资源，占据着越来越重要的地位，它是 科学管理的基础、正确决策的前提、有效调控的手段。人们越来越希 望从大量的数据中提取出有用的信息供决策使用。从数据中提取有用 的信息或发现知识可以通过数据挖掘的方法来实现，但前提是数据必 须 具 有 正 确 性 （ Correctness ） 、 一 致 性 （ Consistency ） 、 完 整 性 （ Completeness ） 和 可 靠 性 （ Reliability ） [1 ] ， 而 目 前 的 现 存 数 据 库 或 数据仓库中的数据普遍存在很多的问题。如数据输入错误、不同来源 的数据引起的不同表示方法，数据间的不一致等，导致现有的数据中 存在这样或那样的脏数据（即存在数据质量问题） 。他们主要表现为： 拼写问题、打印错误、不合法值、空值、不一致值、简写、同一实体 的 多 种 表 示（ 重 复 ） 、不 遵 循 应 用 完 整 等 。这 样 的 数 据 被 定 义 为 脏 的 数 据，这些脏数据可能带来如数据质量不高、决策制定失败甚至于错误 等等。因此，针对脏数据的有效处理是进行数据挖掘，尤其是辅助决 策的必要步骤。而数据预处理可以有效的清除脏数据、保证数据的质 量。1.2 数据挖掘（Data Mining）数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的 实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜 在有用的信息和知识的过程，是当前计算机科学研究的热点之一。 数据挖掘的主要特点是对商业数据库中的大量业务数据进行抽 取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性 数据。近年来，数据挖掘引起了信息产业界的极大关注，其主要原因 是由于企业数据库的广泛使用积累了大量的数据，并迫切需要从这些 数据中获取有用的信息的知识。 数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违 背 直 觉 的 信 息 或 知 识 ，挖 掘 出 的 信 息 越 是 出 乎 意 料 ，就 可 能 越 有 价 值 。 在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩1吉林大学硕士学位论文尿布和啤酒之间有着惊人的联系。经过十多年的发展，数据挖掘的研 究重点逐渐从发现方法转向系统应用，注重多种发现策略和技术的集 成，以及多学科之间的相互渗透。数据挖掘系统也从第一、二代系统 转 向 第 三 、四 代 系 统 的 研 制 。数 据 挖 掘 是 面 向 应 用 的 多 学 科 交 叉 领 域 ， 应用推动了数据挖掘技术和理论的研究。而数据挖掘系统是数据挖掘 研究和应用的桥梁，对数据挖掘技术的推广起到很大的作用。 数据挖掘定义包括好几层含义：数据源必须是真实的、大量的、 不含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可 理解、可运用；并不要求发现放之四海皆准的知识，也不是要去发现 崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际 上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特 定领域的，同时还要能够易于被用户理解，最好能用自然语言表达所 发现的结果。 数据挖掘可分为两类：预言性数据挖掘和描述性数据挖掘。预言 性数据挖掘是进行数据分析，建立一个或一组模型，并根据模型产生 关于数据的预测；描述性数据挖掘是以概要的方式对数据信息进行描 述，提供数据的有趣的一般性质。1.3 数据挖掘与知识发现简介计算机技术的迅猛发展的今天，数据库技术和数据库管理系统 （ DBMS ） 的 广 泛 使 用 ， 商 业 、 各 级 政 府 机 构 和 科 研 部 门 等 的 数 据 库 中存储的数据量急剧增大并趋于分散。人们迫切需要有效地处理大规 模数据的方法，希望能从中提取深层次的用于描述信息、整体特征以 及事物发展趋势的预测内容。 有需求就有发展， 1989 年 8 月 在 美 国 底 特 律 召 开 的 第 11 届 国 际 人 [2] 工智能联合会议 （ AAAI ） 上， 首次提出基于数据库的知识发现 （ KDD ） 一 词 。人 们 给 KDD 下 过 很 多 定 义 ，内 涵 也 各 不 相 同 ，目 前 公 认 的 定 义 是 由 Fayyad 等 人 提 出 的 。所 谓 基 于 数 据 库 的 知 识 发 现（ KDD ）是 指 从 大量数据中提取有效的、新颖的、潜在有用的、最终可被理解的模式 的 非 平 凡 过 程 。 数 据 挖 掘 （ DM ） 是 知 识 发 现 过 程 的 一 个 重 要 步 骤 。2吉林大学硕士学位论文1.3.1 数 据 挖 掘 与 知 识 发 现 过 程知 识 发 现 （ KDD ） 是 一 个 反 复 迭 代 的 人 机 交 互 处 理 过 程 ， 该 过 程 需要经历多个步骤， 并 且 很 多 决 策 需 要 由 用 户 提 供 。从 宏 观 上 看 ， KDD 过 程 主 要 由 三 个 部 分 组 成 ，即 数 据 整 理 、数 据 挖 掘 和 结 果 的 解 释 评 估 。 详 细 的 ， KDD 过 程 主 要 由 以 下 步 骤 组 成 ： 1. 数 据 准 备 ： 了 解 KDD 应 用 领 域 的 有 关 情 况 。 该 步 骤 包 括 熟 悉 相 关的背景知识，搞清用户需求。 2. 数 据 选 取 ： 数 据 选 取 的 目 的 是 确 定 目 标 数 据 ， 根 据 用 户 的 需 要 从原始数据库中选取相关数据或样本。在此过程中，将利用一些数据 库操作对数据库进行相关的处理。 3. 数 据 预 处 理 ：对 步 骤 2 中 选 出 的 数 据 进 行 再 处 理 ，检 查 数 据 的 完 整性及数据一致性，消除噪声，滤除与数据挖掘无关的冗余数据，根 据时间序列和已知的变化情况利用统计等方法填充丢失的数据。 4. 数 据 变 换 ： 根 据 知 识 发 现 的 任 务 对 经 过 预 处 理 的 数 据 进 行 再 处 理，主要是通过投影或利用数据库的其它操作减少数据量。 5. 确 定 KDD 目 标 ：根 据 用 户 的 要 求 ，确 定 KDD 是 发 现 何 种 类 型 的 知 识 ， 因 为 对 KDD 的 不 同 要 求 会 在 具 体 的 知 识 发 现 过 程 中 采 用 不 同 的 知识发现算法。如分类、时间序列、关联规则、聚类等。 6. 选 择 算 法 ： 根 据 确 定 的 任 务 选 择 合 适 的 知 识 发 现 算 法 ， 包 括 选 取合适的模型和参数。同样的目标可以选择用不同的算法来解决，可 以根据具体情况进行分析选择。有两种选择算法的途径，一是根据数 据的特点不同，选择与之相关的算法；二是根据用户的要求，有的用 户希望得到描述型的结果，有的用户希望得到预测准确度尽可能高的 结 果 ， 不 能 一 概 而 论 。 总 之 ， 要 做 到 选 择 算 法 与 整 个 KDD 过 程 的 评 判 标准相一致。 7. 数 据 挖 掘 ： 这 是 整 个 KDD 过 程 中 很 重 要 的 一 个 步 骤 。 运 用 前 面 选择的算法，从数据库中提取用户感兴趣的知识，并以一定的方式表 示 出 来 (如 产 生 式 规 则 等 )是 数 据 挖 掘 的 目 的 。 8. 模 式 解 释 ： 对 在 数 据 挖 掘 步 骤 中 发 现 的 模 式 (知 识 )进 行 解 释 。 经过用户或机器的评估后，可能会发现这些模式中存在冗余或无关的 模 式 ，此 时 应 该 将 其 剔 除 。当 然 ，有 些 模 式 也 许 不 能 满 足 用 户 的 要 求 ， 这就需要返回到前面的某些处理步骤中去反复提取。例如，重新选取 数据、采用新的数据变换方法、修改数据挖掘算法的某些参数值，甚 至换另外的一种挖掘算法，从而提取出更有效的知识。3吉林大学硕士学位论文9. 知 识 评 价 ： 将 发 现 的 知 识 以 用 户 能 了 解 的 方 式 呈 现 给 用 户 。 这 期间也包含对知识的一致性检查，以确信本次发现的知识不会与以前 发 现 的 知 识 相 抵 触 。由 于 挖 掘 出 来 的 知 识 最 终 是 呈 现 给 用 户 的 ，所 以 ， 应该以用户所能够理解的最直观的方式作为最终结果。因此，知识发 现工作还包括对模式进行可视化处理等等。 在上述步骤中，数据挖掘主要目的是利用某些特定的知识发现算 法，在一定的运算效率范围内，从数据中发现出有关知识，数据挖掘 决 定 了 整 个 KDD 过 程 的 效 果 与 效 率 。 人们已经遵循以上知识发现过程 开发了很多实用的数据挖掘工具。1.3.2 数 据 挖 掘 的 相 关 领 域图 1.1 粗 略 地 展 示 了 一 些 数 据 挖 掘 方 法 。 数据挖掘方法的三个主要 来源是机器学习、数据库技术和统计学，与数据挖掘相关的理论和技 术可以分别按挖掘任务、挖掘对象和挖掘方法来分类。数据库 统计学 基于规则的系统 可视化技术 高性能计算 模糊集 知识发现 与 数据挖掘知识表示 机器学习 粗糙集 模式识别 人工神经网络图 1.1 数 据 挖 掘 方 法 与 相 关 领 域1. 按 挖 掘 任 务 分 类 ： 包 括 分 类 与 预 测 、 聚 类 、 关 联 规 则 、 时 序 模 式、数据总结、依赖关系或依赖模型发现、异常和趋势发现等。 2. 按 挖 掘 对 象 分 类 ： 包 括 关 系 数 据 库 、 面 向 对 象 数 据 库 、 空 间 数 据库、时态数据库、文本数据库、多媒体数据库、异构数据库、数据 仓 库 、 演 绎 数 据 库 和 Web 数 据 库 等 。 3. 按 挖 掘 方 法 分 类 ： 包 括 机 器 学 习 方 法 、 统 计 方 法 、 数 据 库 方 法 和 神 经 网 络 方 法 等 。 机 器 学 习 方 法 可 以 细 分 为 归 纳 学 习 方 法 [3] （ 决 策4吉林大学硕士学位论文树、规则归纳等）、基于范例学习、遗传算法等。统计方法又可细分 为回归分析（多元回归、自回归等）、判别分析（贝叶斯判别、费歇 尔判别、非参数判别等）、聚类分析（系统聚类、动态聚类等）、探 索性分析（主成分分析、相关分析等）等。数据库方法主要是多维数 据 分 析 和 OLAP 技 术 ， 此 外 还 有 面 向 属 性 的 归 纳 方 法 。 神 经 网 络 方 法 可 以 进 一 步 分 为 前 向 神 经 网 络 （ BP 算 法 等 ） ， Hopfield 神 经 网 络 ， 自 组织神经网络（自组织特征映射、竞争学习等）。1.3.3 数 据 挖 掘 的 任 务 和 方 法数据挖掘可以理解为能从数据中自动提取有用模式的一组特定方 法。数据挖掘的任务是从数据中发现模式，它的任务主要包括： 1. 数 据 约 简 数据约简的目的是对数据信息进行浓缩，给出信息的紧凑描述。 最简单的数据约简方法是利用统计学理论计算出和值、平均值、方差 值等，或者利用简单、直观的图形方式（如直方图、饼状图等）表示 统计结果。 2. 分 类 与 估 计 分类旨在找到一个分类函数或分类模型，利用分类函数或分类模 型将被分类数据项映射到某一个给定类别中。分类可从历史数据结果 中自动推导出给定数据的推广描述，从而预测未来数据，预测准确性 的检验需等待事件完成。分类模型的构造方法包括：数理统计、机器 学习、决策树、贝叶斯网络、神经网络及粗糙集等方法。针对不同分 类 对 象 构 造 不 同 的 分 类 模 型 ，不 存 在 适 合 于 各 种 数 据 的 模 型 构 造 方 法 。 分类处理的输出结果是离散的类别值，与分类方法不同，估计处 理的结果是连续的，但两者的函数定义类似。分类与估计都可用于预 测。 3. 聚 类 聚类是根据对象数据的不同特性，将对象数据集划分为多个组， 聚 类 生 成 的 组 称 为 簇 （ Cluster ） ， 即 簇 是 数 据 对 象 的 集 合 。 聚 类 的 目 的是使簇内对象间的差别或距离尽可能小，簇间对象的差别或距离尽 可能大。聚类与分类的区别在于聚类并不依赖于已确定的组别。聚类 方法主要包括统计法、机器学习法、神经网络法等。 4. 关 联 分 析 关联分析的任务是发现数据对象之间的相互依赖性或相互关联5吉林大学硕士学位论文性 。 如 果 由 对 象 A 可 以 推 导 出 对 象 B， 可 以 用 A → B 表 示 ， 并 称 为 对 象 B 依 赖 于 对 象 A。 常 用 的 分 析 技 术 有 估 计 分 析 、 关 联 规 则 、 信 念 网 络 等 。关 联 分 析 主 要 是 针 对 事 务 型 数 据 库（ 如 销 售 数 据 库 等 ） ，构 造 出 的关联规则可利于商业决策，能帮助规划市场、降低成本、预测市场 趋势、改进客户关系管理等。 目前国内从事数据挖掘研究的人员主要在大学，也有部分在研究 所或公司。所涉及的研究领域一般集中于数据挖掘算法的研究、实际 应用和有关理论方面的研究。领域研究者进行的多数项目，如国家自 然 科 学 基 金 、 863 计 划 、 “十五”计划等，都是由国家政府资助的研究 项目，有关于国内数据挖掘系统的报道较少，数据挖掘工具的开发与 国际先进水平还有很大差距。 数据挖掘是应用于大型数据库中的技术，是具有广阔前景的研究 领域，除理论和技术方面的问题外，在开发和应用中经常遇到的技术 难题包括：海量数据、噪声数据、数据类型不一致、数据缺陷、数据 的动态性和数据的私有性、安全性等问题。今后可能的研究方向是： 高效并行的挖掘算法，挖掘结果有效性、确定性的提高，多源数据挖 掘，多抽象层次上的交互式数据挖掘，数据挖掘系统的实用性、安全 性和保密性等。1.4 数据挖掘系统简介随着数据库技术的迅速发展以及数据库管理系统的广泛应用，数 据规模的膨胀和分析需求的增长给数据库、数据仓库厂商和各种数据 库应用企业带来了前所未有的冲击和挑战。在这种情况下，各种类型 的 数 据 挖 掘 系 统 和 商 业 智 能 （ Business Intelligence ） 软 件 不 断 被 开 发 、 研制产生。 数据挖掘系统属于智能决策支持系统，是一种以信息技术为手段， 应用管理科学、计算机科学及有关学科的理论和方法，结合具体行业 的知识背景和历史数据，针对半结构化和非结构化的决策问题，通过 提供背景材料、协助明确问题、修改完善模型、列举可能方案、进行 分析比较等方式，为管理者提供知识和模式，帮助管理者做出正确决 策的智能人机交互信息系统。 近年来，人们已经对数据挖掘过程和数据挖掘系统进行了大量研 究 。 1996 年 ， 美 国 人 工 智 能 协 会 的 Brachman 和 Anand 在 文 中 提 出 强 调以用户为中心的过程模型， Reinartz 在 文 章 中 进 一 步 强 调 了 以 用 户 为6吉林大学硕士学位论文中心的重要性，上述工作都强调了用户交互的必要性以及用户交互在 成 功 的 数 据 挖 掘 过 程 中 的 作 用 。 Williams 对 整 个 数 据 挖 掘 过 程 进 行 了 理论上的形式化描述，从而有助于对不同的方法进行比较和区分。 Imielinski 和 Mannila 在 96 年 提 出 了 第 二 代 数 据 挖 掘 的 概 念 ， Virmani 在 98 年 实 现 了 一 个 第 二 代 数 据 挖 掘 系 统 ， Grossman 在 98 年 提 出 了 第 四代数据挖掘系统的概念， Goeble 等 在 KDD’99 上 对 43 个 数 据 挖 掘 系 统 进 行 了 分 析 和 比 较 ，提 出 了 一 种 数 据 挖 掘 系 统 分 类 的 方 法 ，Piatetsky Shaprio 在 KDD2000 上 总 结 了 数 据 挖 掘 系 统 发 展 的 三 个 阶 段 [ 4 ] ， Hongjun Lu 在 PAKDD’01 上 进 一 步 提 出 数 据 挖 掘 系 统 与 数 据 库 管 理 系 统 集 成 的 趋 势 ， Jiawei Han 在 2001 年 提 出 数 据 挖 掘 技 术 与 应 用 相 结 合 开发纵向的数据挖掘系统的发展方向。1.4.1 数 据 挖 掘 过 程 模 型数据挖掘过程模型是开发数据挖掘系统的基础，对数据挖掘系统 的 开 发 设 计 有 着 直 接 的 指 导 作 用 。对 于 数 据 挖 掘 过 程 模 型 的 研 究 很 多 ， 根据这些过程模型，设计和实现了许多相应的数据挖掘原型系统和商 业 系 统 。 KDNuggests （ /software ） 上 介 绍 了 上 百 个 数 据 挖 掘 系 统 ， 大 致 可 以 将 数 据 挖 掘 模 型 分 为 两 类 ， 一 种 是 Fayyad 总 结 出 的 过 程 模 型 ， 另 一 种 是 遵 循 CRISP―DM 的 过 程 模 型 。 Fayyad 过 程 模 型 （ 如 图 1.2 ） 的 主 要 步 骤 ： 数 据 选 择 、 数 据 预 处 理 、 数 据 转 换 、 数 据 挖 掘 、 解 释 和 评 估 。 Fayyad 过 程 模 型 是 一 个 偏 重 技术的模型，该模型从数据入手，到知识结束。目前早期开发的大部 分 数 据 挖 掘 系 统 都 遵 循 Fayyad 过 程 模 型 ，即 数 据 挖 掘 系 统 的 功 能 是 发 现模式，生成模型，但是该模型存在几个问题： ① 为什么选择这些数据 ② 模型如何被使用 ③ 如何与现有的信息系统集成 以 上 几 点 这 些 系 统 并 没 有 实 现 。典 型 的 遵 循 Fayyad 过 程 模 型 的 系 统 有 ： IBM Intelligent Miner 、 SAS Enterprise Miner 、 DBMiner 等 。7吉林大学硕士学位论文选择预处理转换挖掘评估数据目标数据处理后数据转换数据模式知识图 1.2Fayyad 提 出 的 过 程 模 型CRISP-DM [ 5 ] 全 称 为 Cross- Industry Standard Process for Data Mining ，即 交 叉 行 业 数 据 挖 掘 过 程 标 准 。由 SPSS 、NCR 、Daimler-Benz 在 1996 年 制 定 ， CRISP-DM 模 型 （ 如 图 1.3 ） 注 重 技 术 的 应 用 ， 解 决 了 Fayyad 模 型 存 在 的 两 个 问 题 ， 该 模 型 经 过 不 断 的 完 善 和 实 验 ， 于 1999 年 发 布 了 CRISP-DM1.0 。CRISP-DM 过 程 模 型 从 数 据 挖 掘 技 术 应 用的角度划分数据挖掘任务，将数据挖掘技术与应用紧密结合，更加 注重数据挖掘模型的质量和如何与业务问题相结合、如何应用挖掘出 的 模 型 等 实 际 应 用 中 用 户 最 关 心 的 问 题 ， 因 此 CRISP-DM 过 程 模 型 从 商业的角度给出了对数据挖掘方法的理解。目前数据挖掘系统的研制 和 开 发 大 都 遵 循 CRISP-DM 标 准 ， 将 模 式 的 挖 掘 和 模 型 的 部 署 紧 密 结 合 。 CRISP-DM 模 型 包 括 以 下 主 要 步 骤 ：商 业 理 解 、数 据 理 解 、数 据 准备、建立模型、模型评估、模型发布。图 1.3 CRISP-DM 过 程 模 型8吉林大学硕士学位论文1.4.2 数 据 挖 掘 系 统 的 发 展1. 四 代 数 据 挖 掘 系 统 [ 5 ] Grossman 从 技 术 层 面 提 出 将 数 据 挖 掘 系 统 划 分 为 四 代（ 如 表 1.1 ）表 1.1 四 代 数 据 挖 掘 系 统 数据挖掘 算法 支持一个 或者多个 算法 多个算 和数据库以 第二代 及数据仓库 集成 法：挖掘 一次不能 放进内存 的数据 和预言模型 系统集成 和移动数据 第四代 /各 种 计 算 设备的数据 联合 多个算法 数据库管理 系统：包括 数据库和数 据仓库 数据库管理 多个算法 系统和预言 模型系统 数据库管 理、预言模 型、移动系 统 移动和各种计 算设备 同质、 局部区域 的计算机集群 有些系统 支持对 象、 文本、 和连续的 媒体数据 支持半结 intranet/extrane t网 络 计 算 构化数据 和 Web 数 据 普遍存在 的计算模 型 独立的系统 单个机器 向量数据代特征集成分布计算模型数据模型数据挖掘作 第一代 为一个独立 的应用第三代概括地讲，第二代系统提供数据库管理系统和数据挖掘系统之间 的有效接口，这可以作为如何标记合适的数据挖掘原语的一个研究问 题，数据挖掘原语能够在数据仓库或者数据库内部执行以改善数据挖 掘系统的性能；第三代系统另外还提供数据挖掘系统和预言模型系统 之间的有效接口。这些接口的研究与开发使得数据挖掘系统能够和预 言 模 型 系 统 以 及 数 据 库 / 数 据 仓 库 合 并 ，以 提 供 一 个 集 成 的 系 统 来 管 理 日常的商业过程。9吉林大学硕士学位论文与 数 据 挖 掘 过 程 模 型 对 应 起 来 ，第 一 、二 代 系 统 支 持 Fayyad 过 程 模 型 ， 第 三 、 四 代 支 持 CRISP-DM 模 型 。 第 一 代 系 统 和 第 二 代 系 统 相 比由于不具有和数据管理系统之间的有效接口，所以在数据预处理方 面有一定的缺陷，第三、四代系统强调预言模型的使用和在操作型环 境 下 的 部 署 ， 能 更 好 的 支 持 CRISP-DM 模 型 。 目前，随着新的挖掘算法的开发和研究，第一代数据挖掘系统仍 然会出现，第二代系统是商业软件的主流，部分第二代系统在开发上 已经研制出相应的第三代数据挖掘系统，第四代数据挖掘系统尚未见 报 道 ，只 在 PKDD2001 上 Kargupta 发 表 了 一 篇 在 移 动 环 境 下 挖 掘 决 策 树的论文。 2. 数 据 挖 掘 系 统 的 三 个 发 展 阶 段 上面从技术层面将数据挖掘系统划分为四代，并没有涉及数据挖 掘系统的应用发展，下面从应用的角度将数据挖掘系统的发展归纳为 三个阶段： 1) 第 一 阶 段 ： 独 立 的 数 据 挖 掘 系 统 独立的数据挖掘系统对应第一代系统，出现在数据挖掘技术发展 早期，研究人员开发出一种新型的数据挖掘算法，就形成一个软件。 这类系统要求用户对具体的算法和数据挖掘技术有相当的了解，还要 负 责 大 量 的 数 据 预 处 理 工 作 。 比 如 C4.5 决 策 树 ， 平 行 坐 标 可 视 化 （ parallel-coordinate visualization ） 等 。 2) 第 二 阶 段 ： 横 向 的 数 据 挖 掘 工 具 随着数据挖掘应用的发展，人们逐渐认识到数据挖掘软件需要和 以下三个方面紧密结合： ①数据库和数据仓库 ②多种类型的数据挖掘算法 ③数据转换、数据清洗等预处理工作 随着这些需求的出现， 1995 年 左 右 软 件 开 发 商 开 始 提 供 称 之 为 “ 工 具 集 ”的 数 据 挖 掘 系 统 。 此 类 工 具 集 的 特 点 是 提 供 多 种 数 据 挖 掘 算 法 （通常有关联规则、 分类和聚类等） ， 同时也包括数据的转换和可视化。 由于此类工具并非面向特定的应用，是通用的算法集合，可以称之为 横 向 的 数 据 挖 掘 工 具 （ Horizontal Data Mining Tools ） 。数据挖掘系统 的第二、三、四代系统都属于横向的数据挖掘工具。横向的工具一般 都 支 持 Fayyad 过 程 模 型 ， 部分系统增加了模型评价和部署， 比如： SPSS Clementine ， 从 而 支 持 CRISP-DM 模 型 。 典 型 的 横 向 工 具 有 ： IBM Intelligent Miner 、 SAS Enterprise Miner 、 SPSS Clementine 、 SGI 的10吉林大学硕士学位论文Mineset 、 Oracle Darwin 等 。 3) 第 三 阶 段 ： 纵 向 的 数 据 挖 掘 解 决 方 案 随着横向数据挖掘工具使用的日渐广泛，人们也发现这类数据挖 掘工具只有精通数据挖掘算法的专家才能熟练使用，如果对算法不了 解 ， 难 以 得 出 好 的 模 型 。 所 以 为 了 推 动 数 据 挖 掘 技 术 的 应 用 ， 从 1999 年开始，大量的数据挖掘工具研制者开始提供纵向的数据挖掘解决方 案，即针对特定的应用提供完整的数据挖掘方案，这些方案提供商主 要 有 KD1 （ 主 要 用 于 零 售 业 ） 、 Option&Choice （ 主 要 用 于 保 险 业 ） 、 HNC （ 欺 诈 行 为 侦 测 ） 和 Unical Model （ 主 要 用 于 市 场 营 销 ） 等 。 纵 向 的 解 决 方 案 大 都 支 持 CRISP-DM 模 型 ， 强 调 模 型 的 应 用 和 部 署 ， 以 及与操作型系统的集成。1.4.3 数 据 挖 掘 系 统 的 国 际 业 界 标 准数 据 挖 掘 国 际 会 议（ KDD ）在 2000 年 开 始 专 门 开 辟 标 准 专 题 讨 论 区，目前数据挖掘已经存在一些标准，包括数据挖掘过程标准 CRISP-DM ，预 言 模 型 交 换 标 准 PMML ，Microsoft 的 OLE DB For Data Mining 等 。 CRISP-DM 已 经 被 许 多 数 据 挖 掘 系 统 遵 循 ， PMML 和 OLE DB For DM 因 为 正 在 制 定 和 发 展 中 ， 遵 循 的 数 据 挖 掘 系 统 较 少 。 CRISP-DM ： 全 称 是 交 叉 行 业 数 据 挖 掘 过 程 标 准 （ Cross-Industry Standard Process for Data Mining ）。 它 由 SPSS 、 NCR 以 及 DaimlerChrysler 三 个 公 司 在 1996 年 提 出 ， 是数据挖掘公司和使用数据 挖掘软件的企业一起制定的数据挖掘过程的标准。这套标准被各个数 据挖掘软件商用来指导其数据挖掘软件的开发，同时也是开发数据挖 掘项目过程的标准方法。 PMML ： 全 称 是 “ 预 言 模 型 标 记 语 言 ” （ Predictive Model Markup [6] Language, PMML ） 。 它 由 数 据 挖 掘 协 会 （ The Data Mining Group, http://www.dmg.org, DMG ） 开 发 。 PMML 是 对 数 据 挖 掘 模 型 进 行 描 述 和 定 义 的 语 言 ，已 经 被 W3C 接 受 ，成 为 国 际 标 准 。如 果 数 据 挖 掘 系 统 在 模 型 定 义 和 描 述 方 面 遵 循 PMML 标 准 ，那 么 各 数 据 挖 掘 系 统 之 间 可 以共享模型。 OLE DB For DM ： 是 微 软 公 司 在 2000 年 3 月 推 出 的 数 据 挖 掘 标 准 。 OLE DB for DM 的 规 范 包 括 创 建 原 语 以 及 许 多 重 要 数 据 挖 掘 模 型 的定义和使用（包括预言模型和聚集） 。 它 是 一 个 基 于 SQL 语 言 的 协 议，为软件商和应用开发人员提供了一个开放的接口，该接口将数据11吉林大学硕士学位论文挖 掘 工 具 更 有 效 地 和 商 业 以 及 电 子 商 务 应 用 集 成 。 同 时 ， OLE DB for DM 已 经 与 DMG 发 布 的 PMML 标 准 结 合 。1.5 本文的主要内容本文综合目前市场及科研领域较为流行和成熟的数据挖掘产品 （ 如 SAS Enterprise Miner 、 Weka 等 ） 的 优 点 ， 设 计 了 一 个 数 据 挖 掘 系统的预处理过程，目前国内外数据挖掘系统，都侧重于挖掘算法的 实现，数据的预处理软件相对较少，功能有限，更没有通用的软件， 本文通过对数据预处理进行了深入的研究，软件设计实现了数据预处 理一些常用的算法的通用处理程序。能够通过维规约、聚集、过滤异 常值、去掉重复记录处理办法对数据进行一定程度的清洗，达到去掉 脏数据、去掉噪声、提高数据挖掘算法的效率的作用。软件设计本身 也 进 行 一 定 程 度 的 优 化 ，达 到 高 效 数 据 预 处 理 的 目 的 。主 要 内 容 如 下 ： 第一章介绍了数据挖掘和知识发现的概念和方法，对数据挖掘系 统的产生和发展进行了介绍。 第二章对国内外同类的数据挖掘系统进行了较为全面的介绍，对 数据挖掘工具的发展前景和趋势进行了分析。 第三章介绍了数据挖掘系统中数据预处理的必要性、以及数据预 处理的功能和主要的方法。 第四章详细介绍了软件设计实现的几种数据预处理方法的处理过 程。 第五章介绍了软件开发情况，介绍了软件的界面功能，和部分程 序设计主要代码编写情况。 第六章对全文进行总结，提出了数据预处理在今后发展时值得研 究和注意的问题。12吉林大学硕士学位论文第二章国内外数据挖掘系统介绍2.1 国外数据挖掘系统在国外，数据挖掘理论研究开展得相对早，数据挖掘技术的发展 也很迅速。在这种环境下，很多实力强大、技术领先的商业公司和研 究机构投入大量的人力和财力来开发各自的数据挖掘产品。目前，已 经开发出了许多功能强大并且使用简便的数据挖掘系统，其中很多系 统已经形成产品，为需要对数据进行处理的企业提供支持。下面，对 当前国外流行的一些数据挖掘系统作一些简单介绍： 1. SAS Enterprise Miner SAS 系 统 全 称 为 Statistics Analysis System ， 最 早 由 北 卡 罗 来 纳 大 学 的 两 位 生 物 统 计 学 研 究 生 编 制 ， 并 于 1976 年 成 立 了 SAS 软 件 研 究 所 ，正 式 推 出 了 SAS 软 件 。 SAS 是 美 国 使 用 最 为 广 泛 的 三 大 著 名 统 计 分 析 软 件 （ SAS ， SPSS 和 SYSTAT ） 之 一 ， 是 目 前 国 际 上 最 为 流 行 的 一种大型统计分析系统，被誉为统计分析的标准软件。 SAS Enterprise Miner 模 块 是 一 个 基 于 图 形 化 界 面 、 菜 单 驱 动 、 拖 拉式操作、对用户非常友好且功能强大的数据挖掘集成环境。其中集 成了：数据获取工具、数据抽样工具、数据筛选工具、数据变量转换 工具、数据挖掘数据库、数据挖掘模型、多种形式的回归工具、为建 立决策树的数据剖分工具、决策树浏览工具、人工神经元网络、数据 挖掘的评价模型等工具。这些具有明确代表意义的图形化模块将各个 数据挖掘的工具单元组成一个处理流程图，并依此来组织数据挖掘的 过程。同时可以根据具体情况的需要进行修改、更新并将需要的模式 存储起来，以便此后重新调出来使用。 目 前 SAS 已 在 全 球 100 多 个 国 家 和 地 区 拥 有 29000 多 个 客 户 群 ， 直 接 用 户 超 过 300 万 人 。 在 我 国 ， 国 家 信 息 中 心 、 国 家 统 计 局 、 卫 生 部 、 中 国 科 学 院 等 都 是 SAS 系 统 的 大 用 户 。 SAS 已 被 广 泛 应 用 于 政 府 行 政 管 理、科研、教育、生产和金融等不同领域，并且发挥着愈来愈重要的 作 用 [7]。 2. SPSS Clementine SPSS 是 世 界 上 最 早 的 统 计 分 析 软 件 之 一 ， 由 美 国 斯 坦 福 大 学 的 三 位 研 究 生 于 20 世 纪 60 年 代 末 研 制 ， 同 时 成 立 了 SPSS 公 司 ， 并 于 1975 年 在 美 国 伊 利 诺 斯 的 芝 加 哥 市 组 建 了 SPSS 总 部 。迄 今 SPSS 软 件 已 有 30 多13吉林大学硕士学位论文年 的 成 长 历 史 ， 全 球 约 有 25 万 家 产 品 用 户 ， 他 们 分 布 于 通 讯 、 医 疗 、 银行、证券、保险、制造、商业、市场研究、科研教育等多个领域和 行业，是世界上应用最广泛的专业统计软件之一。 SPSS 是 世 界 上 最 早 采 用 图 形 菜 单 驱 动 界 面 的 统 计 软 件 ， 它 最 突 出 的 特 点 就 是 操 作 界 面 极 为 友 好 ， 输 出 结 果 美 观 漂 亮 。 SPSS 采 用 类 似 于 EXCEL 表 格 的 方 式 输 入 与 管 理 数 据 ， 数 据 接 口 较 为 通 用 ， 能 方 便 地 从 其 它 数 据 库 中 读 入 数 据 。 SPSS 数 据 挖 掘 产 品 和 服 务 通 过 支 持 交 叉 行 业 数 据 挖 掘 标 准 CRISP-DM 来 保 证 及 时 、 可 靠 的 结 果 。 其 中 SPSS Clementine 模 块 把 有 价 值 的 商 务 知 识 融 入 到 数 据 挖 掘 的 每 一 步 过 程 ， 实 现交互式数据挖掘。并且提供分类、神经网络、关联规则、聚类、时 间序列等丰富的数据挖掘模型，应用业界领先的模型发布技术使数据 挖掘结果更好的传递到相应的管理和决策人员手中。 3. IBM Intelligent Miner IBM 公 司 的 Intelligent Miner 通 过 其 领 先 的 技 术 ， 如 典 型 数 据 集 自 动 生 成 、关 联 发 现 、序 列 规 律 发 现 、概 念 性 分 类 和 可 视 化 呈 现 等 技 术 ， 可以自动实现数据选择、数据转换、数据挖掘和结果呈现等一整套数 据挖掘操作。可以帮助用户从企业数据资产中识别和提炼有价值的信 息， 包 括 分 析 软 件 工 具 Intelligent Miner for Data 和 IBM Intelligent Miner for Text ， 帮 助 企 业 选 取 以 前 未 知 的 、 有 效 的 、 可 行 的 业 务 知 识 。 Intelligent Miner for Data 可 以 寻 找 包 含 于 传 统 文 件 、 数 据 库 、 数 据仓库和数据中心中的隐含信息。拥有改进的用户界面，增强了并行 性，提供新的平台支持、统计功能、新的价值预测技术以及优化的算 法 。其 采 集 算 法 已 成 功 应 用 于 IBM 的 客 户 及 贸 易 伙 伴 之 中 ，能 够 满 足 市场分析、诈骗行为监测、客户联系管理等业务领域的需求。 IBM Intelligent Miner for Text 允 许 企 业 从 文 本 信 息 中 获 取 有 价 值 的 客 户 信 息 。 文 本 数 据 源 可 以 是 Web 页 面 、 在 线 服 务 、 传 真 、 电 子 邮 件 、 Lotus Notes 数 据 库 、 协 定 和 专 利 库 。 它 扩 展 了 IBM 的 数 据 采 集 功 能，可以从文本文档和数据源中获取信息。数据源包括客户反馈、在 线 新 闻 服 务 、 电 子 邮 件 和 Web 页 面 。 其 功 能 包 括 ： 识 别 文 档 语 言 ； 建 立姓名、用语或其它词汇的词典；提取文本的涵义；将类似的文档分 组；根据内容将文档归类等。新版本中还包括一个多功能的先进文本 搜 索 引 擎 和 非 常 高 效 的 Web 文 本 搜 索 功 能 。 4. Insightful Miner Insightful Miner （ I-Miner ） 是 由 美 国 Insightful 公 司 开 发 的 具 有 高 度 可 扩 展 性 的 数 据 分 析 和 数 据 挖 掘 软 件 。它 既 适 用 于 数 据 挖 掘 初 学 者 ， 又 适 用 于 有 经 验 的 数 据 分 析 专 家 。 其 主 要 特 点 是 ： I-Miner 可 视 化 编 程14吉林大学硕士学位论文界面减少了数据挖掘的复杂性，使得广泛的非高级用户也能使用复杂 的 预 测 模 型 建 模 ；用 户 界 面 基 于 独 特 的 管 道 式 架 构 确 保 高 度 可 扩 展 性 ； 所 有 的 I-Miner 组 件 ，如 数 据 获 取 、探 索 性 分 析 、数 据 操 纵 、数 据 清 洗 、 统计模型、机器学习、模型评估和发布都充分利用独特的管道式架构 保证在数据规模和数据处理速度方面的可扩展性；与其它挖掘工具不 同 的 是 ， 所 有 I-Miner 组 件 既 能 运 行 于 驻 留 内 存 中 的 数 据 集 ， 又 能 运 行 于驻留于内存外的数据集； I-Miner 与 数 据 分 析 语 言 ― S 语 言 的 集 成 使 其 成为数据挖掘市面上算法最丰富和最具有可扩展性的工具之一； I-Miner 在 数 据 挖 掘 工 具 市 场 上 设 立 了 新 的 性 价 比 标 准 ， 低 成 本 初 始 费 用 、 提 供 桌 面 版 、 永 久 的 License 无 需 每 年 缴 纳 年 费 。 Insightful Miner 目前在金融、生物科技、政府机构等企事业单位应用非常广泛。 除此以外，国外还有其它一些比较成熟的数据挖掘系统，包括： Oracle 公 司 从 Thinking Machines 公 司 取 得 的 Darwin ； Unica 公 司 开 发 的 Affinium Model ； Angoss Software 所 开 发 的 KnowledgeSEEKER ； 加 拿 大 Simon Fraser 大 学 开 发 的 DBMiner ； SGI 公 司 和 美 国 Standford 大 学 联 合 开 发 的 Minset ； HNC 公 司 开 发 的 用 于 信 用 卡 诈 骗 分 析 的 Database Mining Workstation ；IBM 公 司 Almaden 研 究 中 心 开 发 的 Quest 、NeoVista 开 发 的 Decision Series ；以 及 KEFIR 系 统 、SKICAT 系 统 等 。这 些 数 据 挖 掘系统的特点各不相同，有的适合大规模企业的长期数据挖掘项目， 有的针对特殊行业的数据应用，还有的用于实验室科研机构的数据挖 掘理论研究等。这些数据挖掘系统面向应用，并且在应用中得到了广 泛的推广和使用，反过来也大大推动了数据挖掘理论的研究与发展。2.2 国内数据挖掘系统1. DMiner DMiner 是 由 上 海 复 旦 德 门 软 件 公 司 开 发 的 具 有 自 主 知 识 产 权 的 数 据挖掘平台。平台提供了关联规则、序列模式、决策树分类、神经元 网络、聚类、异常检测等多种数据挖掘算法，并提供了相应的数据挖 掘模型可视化方法，用户可以查看模型可视化结果，了解数据分布情 况 ， 并 能 用 预 测 模 型 对 未 来 的 情 况 做 出 合 理 的 预 测 。 DMiner 智 能 分 析 平 台 采 用 自 定 义 的 基 于 XML 的 数 据 分 析 流 程 语 言 DMAPML 将 数 据 分 析 的 各 种 方 法 （ ETL 、 数 据 探 索 、 数 据 处 理 、 统 计 分 析 、 数 据 挖 掘 、 信息发布等）以可视化分析流程的方式集成。采用可扩展的数据分析 功 能 库 ， 提 供 丰 富 的 数 据 可 视 化 控 件 ， 使 用 JDBC 作 为 数 据 访 问 接 口 ，15吉林大学硕士学位论文支 持 目 前 主 流 的 数 据 库 管 理 系 统 。 DMiner 采 用 基 于 构 件 的 软 件 设 计 方 法 ，通 过 OLE DB 可 以 与 多 种 数 据 源（ 关 系 、文 本 、数 据 立 方 体 等 ）进 行连接，利用插件的概念实现了系统对新算法的可扩展性，对于挖掘 出 的 模 型 采 用 基 于 XML 的 PMML 标 准 格 式 进 行 存 储 和 管 理 ， 方 便 了 系 [8] 统和预言模型系统之间的集成 。 2. iDMiner iDMiner 是 由 海 尔 青 大 公 司 开 发 的 具 有 自 主 知 识 产 权 的 数 据 挖 掘 系 统 。 系 统 中 的 数 据 挖 掘 算 法 符 合 OLE DB For Data Mining 规 范 ， 并 且被独立封装，与应用服务层之间存在统一的接口；算法与算法之间 不存在任何联系， 只 需 对 算 法 的 DLL 动 态 链 接 库 进 行 注 册 、 注销操作， 即可增删算法，系统具有良好的可扩展性。系统中，无论哪类算法生 成 的 模 型 ，都 以 PMML 格 式 描 述 ，用 PMML 描 述 数 据 挖 掘 模 型 ，可 以 将 系 统 分 析 出 的 规 则 和 知 识 描 述 成 单 独 的 XML 文 档 。 这些文档可以脱 离 系 统 环 境 使 用 。由 于 XML 文 档 的 可 读 性 及 平 台 无 关 性 ，能 够 很 轻 易 的重用于其它系统中。 该软件的着眼点不在于算法的精确性或界面的美观性，而致力于 构造一个开放的、可重构、可扩展的软件平台。尤其对国际通用业界 标准的大胆采用，为该软件今后的发展预留了很大的空间，同时也为 国内同类软件融入世界及开发提供了一条新的思路。 3. MSMiner MSMiner 是 由 中 科 院 计 算 技 术 研 究 所 智 能 信 息 处 理 实 验 室 开 发 的 多策略数据挖掘平台。系统的基本特点是：集成基于数据仓库和新型 的元数据管理，按照主题创建数据仓库，并通过元数据进行管理和维 护；数据的抽取、转换、装载等方便的预处理手段；支持多维数据在 线 分 析 处 理（ OLAP ） ；提 供 决 策 树 、支 持 向 量 机 、粗 糙 集 、模 糊 聚 类 、 基于范例推理、统计方法、神经网络计算等多种数据挖掘算法；支持 特征抽取、分类、聚类、预测、关联规则发现、统计分析等数据挖掘 功能，并支持高层次的决策分析；挖掘平台利用扩展了数据仓库某些 功 能 和 特 征 的 数 据 库 管 理 系 统 （ 如 SQL Server, Sybase, Oracle, Informix ） 作后台， 可以与现有的系统无缝的连接， 也从关系型数据库、 文本、万维网等外部数据源中抽取数据，费用低，周期短；实现了可 视化的任务编辑环境，以及功能强大的任务处理引擎，能够快捷有效 地实现各种数据转换和数据挖掘任务；具有良好的可扩展性，转换规 则和挖掘算法是封装的、模块化的，系统提供了一个开放的、灵活通 用的接口，使用户能够加入新的规则和算法，容易进行二次开发。将 MSMiner 与 具 体 的 领 域 相 结 合 ， 构 造 实 际 的 应 用 系 统 时 具 有 方 便 、 快16吉林大学硕士学位论文速、灵活、高效等特点，能够有效地进行验证性发现和探索性发现。 除此之外，国内还有一些其它相关数据挖掘产品的报道，如：复 旦 德 门 公 司 开 发 的 ARMiner 和 CIAS 、 东 北 大 学 开 发 的 面 向 先 进 制 造 企 业 的 综 合 数 据 挖 掘 系 统 ScopeMiner 、东 北 大 学 软 件 中 心 基 于 SAS 开 发 的 OpenMiner 以 及 长 春 工 业 大 学 开 发 的 数 据 挖 掘 工 具 软 件 等 。2.3 国内数据挖掘系统的发展环境及趋势2.3.1 数 据 挖 掘 系 统 的 市 场 环 境如何有效的从大量历史数据中找到有价值的信息，从而帮助企业 对 未 来 变 化 做 出 及 时 正 确 的 决 策 ，最 终 在 激 烈 的 市 场 竞 争 中 占 据 主 动 ， 已经成为当前企业越来越迫切需要解决的问题。 商业智能 （ BI ： Business Intelligence ） 就 是 这 样 一 种 用 于 从 大 量 的 企 业 数 据 中 创 建 出 智 能 知 识 的技术。从它诞生到现在的短短几年发展中，其技术和市场都取得了 巨 大 的 发 展 ，各 种 BI 产 品 也 纷 纷 面 世 。数 据 挖 掘 系 统 、决 策 支 持 系 统 等 都 属 于 BI 软 件 。 据 权 威 研 究 报 告 显 示 ， 2003 年 全 球 BI 软 件 市 场 价 值 约 为 71 亿 美 元 ， 比 2002 年 的 55 亿 美 元 增 长 了 近 三 成 ，成 为 继 ERP 之 后 ，管 理 软 件 领 域 的 新 的 增 长 点 。 从 国 内 市 场 来 看 ， 2003 年 以 来 中 国 BI 软 件 市场增长速度较快，并且远未达到成熟和饱和，市场潜力还很大。据 权 威 研 究 报 告 预 测 未 来 5 年 中 国 BI 市 场 的 年 复 合 增 长 率 将 达 到 64.6% 。 低端数据挖掘运用的是那些提供几种机器学习算法如决策树、神 经网络等的厂商。通常不具有可扩展性，没有自己的脚本语言，也不 提供任何操作日志记录。低端数据挖掘工具不能很好地支持数据获取 和 预 处 理 ， 而 这 部 分 任 务 往 往 占 据 数 据 挖 掘 任 务 60%-80% 的 工 作 量 。 最为关键的是低端数据挖掘工具算法的计算过程必须一次性进入内 存，因此本质上使其不具有可扩展性；而同时他们也缺乏丰富的数据 分析语言，所以不能快速适应用户需求的变化。总体上说，低端数据 挖掘工具价格便宜，但不能单独解决数据挖掘问题，也根本不具有处 理大数据量的能力。 高端数据挖掘主要来自于那些将数据挖掘工具与其数据库系统捆 绑 的 厂 商 。这 些 厂 商 优 势 在 于 IT 技 能 而 非 数 据 分 析 能 力 。这 种 硬 件 与 软件系统相捆绑的方式保证了挖掘产品的可扩展性。但是严格的讲， 他们更多的不是工具而是花费巨大的系统集成项目。他们所依赖的实17吉林大学硕士学位论文施 流 程 反 映 出 很 大 ERP 和 CRM 的 痕 迹 。 不 幸 的 是 ， 高 端 数 据 挖 掘 工 具 也 往 往 不 能 很 好 满 足 用 户 运 行 效 率 、投 资 回 报 上 的 期 望 。总 而 言 之 ， 高 端 数 据 挖 掘 平 台 适 用 于 那 些 大 的 系 统 集 成 项 目 ， 而 不 是 “量 体 裁 衣 ” 的解决方案。 处于中间层次的数据挖掘工具数量众多。这是数据分析和贴身解 决方案的领域。这些数据挖掘工具能支持整个数据挖掘流程并拥有可 集成的分析语言。但是，这些工具在扩展性、灵活性、易用性等方面 仍然存在严重缺陷。受他们的核心架构限定，这些缺陷难以解决。让 人 疑 惑 的 是 ，这 些 工 具 并 不 要 求 整 个 IT 部 门 实 施 ，但 他 们 却 不 提 供 可 供给广大用户买得起的桌面版。事实上，他们拒绝了那些希望使用单 授权密码的桌面版用户。这些工具初始购置费用十分昂贵（约 $35,000-$100,000 ） ， 有 些 还 要 收 取 年 费 以 保 证 继 续 拥 有 所 有 权 [9]。2.3.2 国 内 数 据 挖 掘 系 统 的 分 类中 国 的 高 端 BI 市 场 被 国 际 大 厂 商 占 据 ， 低 端 市 场 是 国 内 的 BI 厂 商 及 行 业 的 ISV 和 集 成 商 在 竞 争 。 可 以 将 国 内 市 场 的 BI 软 件 公 司 分 为 以下三类。 第一类公司是那些提供数据库软件或统计分析软件的跨国大公 司 ， 凭 借 着 先 进 的 技 术 势 力 和 雄 厚 的 资 金 支 持 ， 将 产 品 延 伸 到 BI 领 域 ， 并 将 其 BI 产 品 打 包 在 其 数 据 库 或 统 计 软 件 中 推 广 ， 从 而 抢 占 高 端市场。 第 二 类 公 司 是 专 门 做 BI 软 件 的 厂 商 。 第 三 类 公 司 是 国 内 的 BI 厂 商 及 行 业 ISV ，他 们 一 直 在 开 发 一 些 联 机分析数据类软件，并将其作为财务套装软件的一部分，进行捆绑销 售 。 作 为 BI 产 品 ， 他 们 所 服 务 的 是 低 端 市 场 。 随 着 BI 在 国 内 需 求 日 趋 迫 切 ， BI 市 场 规 模 巨 大 ， 而 且 增 长 迅 速 。 但 是 从 以 上 分 析 可 以 看 出 ， 国 内 的 BI 厂 商 并 没 有 完 整 的 BI 产 品 ， 主 要 是 利 用 国 外 的 产 品 在 各 个 行 业 进 行 BI 解 决 方 案 的 实 施 ，或 者 在 开 发 报表和联机分析等功能的低端分析软件。 国内数据挖掘相关产品，根据技术特点大致分为三类： 1. 面 向 某 一 行 业 甚 至 某 一 应 用 的 专 用 数 据 挖 掘 产 品 。 这 些 产 品 是 由开发商为某一特定用户或者特定应用开发的专用数据挖掘系统衍化 而来的。其特点是算法针对性强，模型设计科学严谨，功能较强；缺 点是通用性差，不易修改。18吉林大学硕士学位论文2. 基 于 国 外 产 品 经 过 二 次 开 发 而 来 的 软 件 。 国 内 有 一 些 数 据 挖 掘 产 品 是 在 SAS 、 SAP 等 国 外 产 品 的 基 础 上 经 过 二 次 开 发 得 到 的 。 严 格 意 义 上 讲 ，这 些 软 件 不 具 有 完 全 的 自 主 知 识 产 权 ，不 是 纯 粹 的 “ 国 货 ” 。 3. 自 主 研 发 的 通 用 数 据 挖 掘 产 品 。 也 有 少 量 数 据 挖 掘 软 件 是 国 内 厂商完全自主开发的。该类软件功能比前两类强，不但包含算法多， 可 用 范 围 广 ，同 时 可 修 改 、可 维 护 性 较 强 。但 是 由 于 某 些 原 因 的 影 响 ， 国内自主版权的软件绝大多数未遵照国外数据挖掘业界的工业标准， 造成扩展性及兼容性的缺陷。2.3.3 国 内 数 据 挖 掘 系 统 的 发 展 趋 势目前，国内的一些数据挖掘软件开发厂商已经开发了一系列的数 据挖掘产品。这些产品有的功能不够完善，有的针对具体行业，适用 范围小，与国际领先水平还有很大差距。因此，国内数据挖掘软件开 发业的发展潜力和上升空间都很大，结合当前国内数据挖掘系统的发 展趋势，在今后开发过程中主要应该注意的有： 1. 与 国 际 标 准 接 轨 ， 采 用 数 据 挖 掘 业 界 的 通 用 标 准 。 采 用 数 据 挖 掘 的 业 界 标 准 （ 如 ： CRISP-DM 、 PMML 、 OLE DB for DM ） 可 以 使 数 据挖掘系统更好的与国际先进水平接轨，共享系统的数据挖掘模型， 为软件今后的发展预留空间，使国产软件尽早融入世界。 2. 对 日 益 增 长 的 大 规 模 海 量 数 据 的 高 效 处 理 。 数 据 挖 掘 面 临 着 如 何处理现实数据库中日益增长的大规模海量数据的问题，目前系统可 以采用数据仓库、嵌入灵活的数据预处理语言、缓冲技术、并行数据 挖掘等技术来解决此类问题。 3. 数 据 挖 掘 算 法 的 行 业 适 用 性 及 灵 活 的 嵌 入 、 更 新 策 略 。 利 用 数 据挖掘算法对数据进行挖掘是整个数据挖掘过程的核心，因此，开发 准确性好、效率高、行业适用性强的数据挖掘算法和提供灵活、方便 的算法嵌入策略，也是开发数据挖掘系统时应当注意的问题。 4. 开 发 友 好 的 交 互 界 面 和 图 形 可 视 化 技 术 。 友 好 、 方 便 的 数 据 选 取、算法设置，结果显示等图形可视化技术，是好的数据挖掘系统应 该具备的。 5. 建 立 好 的 预 言 模 型 打 分 方 法 和 模 型 评 估 评 价 标 准 。 如 何 评 价 多 个数据挖掘模型之间的效率高低、准确程度，也是数据挖掘系统急待 解决的问题。 6. 网 络 环 境 、 新 兴 领 域 （ 如 生 物 技 术 、 基 因 工 程 ） 以 及 移 动 设 备19吉林大学硕士学位论文联 合 方 面 的 挖 掘 。在 一 些 新 兴 领 域 开 发 具 有 Web 挖 掘 功 能 和 与 移 动 设 备结合的数据挖掘系统，符合现代数据挖掘的发展趋势。2.4 本章小结本章分别介绍了当前数据挖掘行业国内外流行的几种数据挖掘系 统以及这些系统的基本特点和应用领域。接下来结合整个数据挖掘系 统的市场环境，重点分析了国内数据挖掘系统的分类及发展情况，并 且分析了国内数据挖掘系统今后的发展趋势， 为 DBIN Miner 系 统 的 开 发指明了方向。20吉林大学硕士学位论文第三章3.1 数据预处理数据预处理简介3.1.1 系 统 的 原 始 数 据 中 存 在 的 问 题1. 杂 乱 性 ， 原 始 数 据 是 从 各 个 实 际 应 用 系 统 中 获 取 的 ， 由 于 各 应 用系统的数据缺乏统一标准的定义，数据结构也有较大的差异，因此 各系统间的数据存在较大的不一致性，往往不能直接拿来使用。 2. 重 复 性 ， 是 指 对 于 同 一 个 客 观 事 物 在 数 据 库 中 存 在 其 两 个 或 两 个以上完全相同的物理描述。这是应用系统实际使用过程中普遍存在 的问题，几乎所有应用系统中都存在数据的重复和信息的冗余现象。 3. 不 完 整 性 ， 由 于 实 际 系 统 设 计 时 存 在 的 缺 陷 以 及 一 些 使 用 过 程 中人为因素所造成的，数据记录中可能会出现有些数据属性的值丢失 或不确定的情况，还可能缺失必需的数据而造成数据不完整。实际使 用的系统中，存在大量的模糊信息，有些数据甚至还具有一定的随机 性质。3.1.2 预 处 理 的 必 要 性一个完整的数据挖掘系统必须包括数据预处理模块。它以发现任 务作为目标，以领域知识作为指导，用全新的“业务模型”来组织原 来的业务数据，摈弃一些与挖掘目标不相关的属性，为数据挖掘内核 算法提供干净、准确、更有针对性的数据，从而减少挖掘内核的数据 处理量，提高挖掘效率，提高知识发现的起点和知识的准确度。数据 预处理是数据挖掘前的数据准备工作，一方面保证挖掘数据的正确性 和有效性，另一方面通过对数据格式和内容的调整，使数据更符合挖 掘的需要。其目的在于把一些与数据分析、挖掘无关的项清除掉，为 了给挖掘算法提供更高质量的数据。 目前进行的关于数据挖掘的研究工作，大多着眼于数据挖掘算法 的探讨，而忽视了对数据预处理的研究。但是一些比较成熟的算法对 要处理的数据集合一般都有一定的要求，比如数据的完整性要好、数21吉林大学硕士学位论文据的冗余少、属性之间的相关性小。然而，实际系统中的数据一般都 具 有 不 完 整 、冗 余 性 和 模 糊 性 ，很 少 能 直 接 满 足 数 据 挖 掘 算 法 的 要 求 。 另外，海量的实际数据中无意义的成分很多，严重影响了数据挖掘算 法的执行效率，而且由于其中的噪音干扰还会造成挖掘结果的偏差。 因此，对不理想的原始数据进行有效的归纳分析和预处理，已经成为 数据挖掘系统实现过程中必须面对的问题。3.1.3 数 据 预 处 理 的 功 能 和 主 要 方 法数据预处理的主要方法有基于粗糙集理论的约简方法；基于概念 树的数据浓缩方法；信息论思想和知识发现；基于统计分析的属性选 取方法；遗传算法。而常见的数据预处理方法有：数据清洗、数据集 成、数据变换和数据归约。 1. 数 据 集 成 （ Data Integration) 是 将 多 文 件 或 多 数 据 库 运 行 环 境 中 的异构数据进行合并处理，解决语义的模糊性。该部分主要涉及数据 的选择、数据的冲突问题以及不一致数据的处理问题。 2. 数 据 清 洗 （ Data Cleaning ） ： 数 据 清 洗 的 目 的 不 只 是 要 消 除 错 误、冗余和数据噪音。其目的是要将按不同的、不兼容的规则所得的 各种数据集一致起来。 3. 数 据 变 换（ Data Transformation ）：是 找 到 数 据 的 特 征 表 示 ，用 维变换或转换来减少有效变量的数目或找到数据的不变式，包括规格 化、规约、切换和投影等操作。 4. 数 据 简 化（ Data Reduction ）：是 在 对 发 现 任 务 和 数 据 本 身 内 容 理解的基础上，寻找依赖于发现目标的表达数据的有用特征，以缩减 数据模型，从而在尽可能保持数据原貌的前提下最大限度的精简数据 量。其主要有两个途径：属性选择和数据抽样，分别针对数据库中的 [9] 属性和记录 。3.2 数据清洗(data cleansing)3.2.1 研 究 背 景各领域用户在实际工作中积累了大量数据，由于企业合并以及企 业环境随着时间的推移而改变，形成对数据的不同要求、录入错误等22吉林大学硕士学位论文这些都会影响所存放数据的质量。因此，有必要以形式化的方法定义 数 据 的 一 致 性 (consistency) 、 正 确 性 (correctness) 、 完 整 性 (completeness) 和 最 小 性 (minimality) ， 而 数 据 质 量 则 被 定 义 为 这 四 个 指 标 在 信 息 系 统 中得到满足的程度。数据质量的衡量指标分为两类：数据质量指示器 [10] 和数据质量参数。 数据质量指示器是客观的信息，比如数据的收集 时间、来源等；数据质量参数是主观性的，比如数据来源的可信度 (credibility) 、 数 据 的 及 时 性 (timeliness) 等 。 在单个数据源中可能存在的质量问题。例如，某个字段是一个自 由格式的字符串类型，比如地址信息、参考文献等，可能会录入错误 的 字 段 值 。 在 多 个 数 据 源 的 情 形 ， 比 如 数 据 仓 库 系 统 或 者 是 基 于 Web 的信息系统，问题更加复杂。来自不同数据源的数据，对同一个概念 有不同的表示方法。还有相似重复记录的问题，需要检测出并且合并 这些记录。解决这些问题的过程称为数据清洗过程。其目的是检测数 据中存在的错误和不一致，剔除或者改正它们，这样就提高了数据的 质量。 在模式转化和集成方面，人们已经做了很多的研究工作。而对于 数据清洗， 尽管工业界已经开发了很多数据抽取、 转 化 和 装 载 工 具 (ETL tool) ， 但 是 它 并 没 有 得 到 足 够 多 的 研 究 人 员 的 关 注 。 一 些 研 究 人 员 研 究相似重复记录的识别和剔除，还有一些与数据清洗相关的工作。在 通过模式转化和集成获得了一致模式以后，在实例层次上仍然需要消 除不一致性。同一个现实实体在两个数据源的记录中可能用不同的主 键来标识，它们的信息可能存在冗余，有些互为补充，甚至有些互相 矛盾。 绝大多数相关领域的研究认为，要很好地完成数据清洗过程，一 定要结合特定应用领域的知识。因此，通常将领域知识用规则的形式 表示出来。利用专家系统，以方便规则的表示和利用于清洗过程中。 当系统碰到不能处理的情况时，报告异常，要求用户辅助做出决定。 同时，系统可以通过机器学习的方法修改知识库，以后碰到类似情况 时，它就知道怎样做出相应的处理了。 市场上的各种数据抽取、转化和装载工具或多或少提供了一些数 据清洗功能，但是都缺乏扩展性。鉴于此，一些研究人员提出了数据 清洗系统的框架。他们围绕这样的框架，提出了数据清洗的模型和语 言 。 这 些 语 言 在 SQL 基 础 上 扩 展 了 新 的 数 据 清 洗 操 作 ， 比 如 Merge 、 Cluster 等 。 有 的 框 架 模 型 采 用 了 分 层 抽 象 的 方 法 ， 最 上 面 是 逻 辑 层 ， 可以用来定义数据清洗的流程，不需要关心具体采用的算法；最下面 是物理实现层，这一层根据用户定义的逻辑流程，采用合适的算法和23吉林大学硕士学位论文参数，对算法的优化过程也是在这一层完成的。 最初，数据清洗过程应用在数据仓库装载数据之前，其目的是为 了 提 高 数 据 的 质 量 。 这 样 ， 后 继 的 联 机 分 析 处 理 (OLAP) 和 数 据 挖 掘 应 用才可能得到正确的结果，决策支持系统才能够辅助管理者做出正确 的决策。但是，一些研究人员提出，可以反过来将数据挖掘的技术应 用到数据清洗过程之中。结合数据挖掘和数据清洗，利用数据挖掘技 术可以发现数据中的模式和匹配规则。3.2.2 国 内 外 研 究 现 状 及 发 展 趋 势数 据 清 洗 主 要 在 数 据 仓 库（ Data Warehousing ）、数 据 库 中 的 知 识 发 现 (KDD)和 总 体 数 据 质 量 管 理 (Total Data qualitymanagement，TDQM) 这三个领域应用。数据清洗处理是进行数据挖掘的第一步，鉴于数据 的海量，不可能进行人工处理，因此自动化数据清洗受到工业界的广 泛关注。提出了自动数据清洗：定义和判断错误类型；查找并标示错 误实例；修改发现的错误。但是，又由于这个问题比较凌乱而显得难 以采用通用的方法进行处理，数据清洗的研究目前并不是特别活跃。 大多数研究工作都针对特定领域的数据集，或者是对不同性质的异常 数据进行的通用处理。目前还没有提出一个公认的自动数据清洗的通 用处理系统。 想要使用专门的数据清洗工具的公司能从多个来源获得。过去， 最常见的选择是自己编制这些工具，但现在想购买数据清洗软件的公 司 有 很 多 选 择 。Oracle 公 司 和 Group1 软 件 公 司 是 领 先 于 其 他 公 司 的 供 应 商 。 其 他 还 有 PeopleSoft 、 SAS 和 Informatica 等 公 司 。 主 要 的 数 据 仓库和业务智能软件供应商在其产品中也有数据清洗功能。 Acxiom 公 司 和 Sagent 技 术 公 司 等 提 供 在 线 的 数 据 清 洗 和 增 强 服 务。这些服务通过因特网以近实时的方式提供数据清洗，以及在一个 一个记录的基础上补充信息。 国内关于数据仓库领域的研究都是以理论为主，很少涉及实例层 次的研究。上海交通大学模式识别和智能系统专业有一位博士对数据 处理进行了研究，其的重点就是在于挖掘中的数据处理，结合领域背 景知识构建专家系统，处理了数据侧重于数据离散化，数据清洗讨论 了对空值等几种单一数据源问题的处理。 有 一 些 比 较 成 熟 的 数 据 清 洗 软 件 ，例 如 ，DBPut 2.0 通 用 数 据 转 换 工 具 。 DBPut 是 一 款 比 较 实 用 的 数 据 转 换 软 件 。 使 用 方 法 简 单 ， 但 功24吉林大学硕士学位论文能 不 多 ， 不 需 掌 握 任 何 程 序 设 计 技 术 或 SQL 语 法 ， 最 多 只 需 要 掌 握 DBPut 的 几 个 关 键 功 能 和 一 些 常 用 的 函 数 ， 通 过 图 形 化 的 设 计 界 面 ， 就可以将复杂的数据转换成所需格式的数据。 DBPut 2.0 的 特 点 ： 支 持 Oracle 直 接 连 接 、 ODBC 连 接 ， 能 直 接 读 取 文 本 格 式 数 据 。 支持图形化的数据转换规则模型编辑方式。 通过任务模型编辑器模块，可设计出比较复杂的数据转换规则模 型。 任务运行调试。可设置任务的调试断点，并能单步运行或暂停， 可监控任务执行过程中的数据抽取、计算结果和装载情况。 其界面如下图：图 3.1 DBPut 2.0 的 软 件 界 面现在国外的相关研究主要包括以下几个方面： 1) 提 出 高 效 的 数 据 异 常 检 测 算 法 ， 来避免扫描整个庞大的数据集； 2) 在 自 动 检 测 数 据 异 常 和 进 行 清 洗 处 理 的 步 骤 之 间 增 加 人 工 判 断 处理，来防止对正确数据进行错误处理； 3) 数 据 清 洗 时 对 数 据 集 文 件 的 并 行 处 理 ； 4) 如 何 消 除 合 并 后 数 据 集 中 的 重 复 数 据 ； 5) 建 立 一 个 通 用 的 领 域 无 关 的 数 据 清 洗 框 架 ； 6) 关 于 模 式 集 成 问 题 。 理想的状况是，被清洗过的数据是没有错误的和一致的，有些数 据清洗软件甚至还能对处理中的数据检查其有用性。对于任何公司的 IT 运 行 来 说 ， 数 据 清 洗 是 一 件 基 础 工 作 ， 但 它 只 是 开 端 。25吉林大学硕士学位论文3.2.3 数 据 清 洗 问 题 研 究 意 义众所周知，数据仓库和知识发现、数据挖掘已经从理论走向了实 际的应用， 世 界 500 强 企 业 中 99% 使 用 了 数 据 仓 库 进 行 信 息 辅 助 决 策 。 而数据清洗保证信息源的数据质量，从而保证了辅助决策的原始数据 的正确性和准确性。没有数据清洗，很可能就会导致错误的决策，因 此数据清洗是构建数据仓库和知识发现的必要因素。从前面提到的研 究现状看来，数据清洗处理的是海量数据集，因此，增量式的数据异 常检测、数据转换算法是必需的，而且对于算法的效率提出了很高的 要求。数据清洗又是一个领域相关性非常强的工作，国内外的研究人 员始终没有提出一个通用的自动化的数据清洗框架，所有关于该领域 的研究都是针对特定领域数据的，通用的清理方案会受到越来越多的 重视。3.2.4 数 据 清 洗 总 结数据清洗的目的不只是要消除错误、冗余和数据噪音。数据清洗 过程必须满足如下几个条件：不论是单数据源还是多数据源，都要检 测并且除去数据中所有明显的错误和不一致；尽可能地减小人工干预 和用户的编程工作量，而且要容易扩展到其他数据源；应该和数据转 化相结合；要有相应的描述语言来指定数据转化和数据清洗操作。 如果没有数据清洗，当将它们进行数据挖掘时，所得的结论就是 不可靠、不真实。数据清洗在不同的应用领域其要求不完全相同。例 如 ， 在 数 据 仓 库 环 境 下 ， 数 据 清 洗 是 ETL（ 抽 取 、 转 换 、 转 贮 ） 过 程 的一个重要部分，要考虑数据仓库的集成性与面向主题的需要（包括 数 据 的 清 理 及 结 构 转 换 ） ； 在 KDD（ K nowledge discovery in databases ） 中数据清洗主要是提高数据的可利用性（去除噪音、无关数据、空白 数据域，考虑时间顺序和数据的变化等），但主要内容还是一样的。 数 据 清 洗 （ Data Cleaning） 是 一 个 减 少 错 误 和 不 一 致 性 、 解 决 对 象 识 别的过程。 数据清洗原理：利用有关技术如数理统计、数据挖掘或预定义的 清洗规则将脏数据转化为满足数据质量要求的数据，如图所示：26吉林大学硕士学位论文图 3.2 数 据 清 洗 原 理在早期阶段，大多数数据清理是用手工完成的。单靠人的双眼做 这件事的时候，发现并改正错误的、不完整的或重复的纪录是一项很 费钱的辛苦任务，还常常会导入新的错误。 现在，专门的软件工具利用专业的算法分析、标准化、纠正、匹 配和合并数据。它们的功能包括从简单的清洗和单一数据集的增强， 到来自不同数据库和文件系统的数据项进行匹配、纠正和合并。27吉林大学硕士学位论文第四章4.1 数据预处理方式数据预处理方法数据预处理方式可分为 4 种： 1. 手 工 实 现 ， 通 过 人 工 检 查 ， 只 要 投 入 足 够 的 人 力 物 力 财 力 ， 也 能发现所有的错误，但效率底下。在大数据量的情况下，几乎是不可 能的。 2. 通 过 专 门 编 写 程 序 ， 这 种 方 法 能 解 决 某 个 特 定 的 问 题 ， 但 不 够 灵活，特别是在清洗过程需要反复进行（一般来说，数据清洗一遍就 达到要求的很少）时，导致程序复杂，清洗过程变化时，工作量大。 而且这种方法也没有充分利用目前数据库提供的强大数据处理能力。 3. 解 决 某 类 特 定 应 用 域 的 问 题 ， 如 根 据 概 率 统 计 学 原 理 查 找 数 值 的记录，对姓名、地址、邮政编码等进行清洗，这是目前研究得较多 的领域， 也是应用最成功的一类。 如 商 用 系 统 ： Trillinm software system, MatchMakert 等 。 4. 与 特 定 应 用 领 域 无 关 的 数 据 清 洗 ， 这 一 部 分 的 研 究 主 要 集 中 在 清 洗 重 复 的 记 录 上 ， 如 Data Cleanser DataBlade Modul,Integrity 系 统 等。 这四种实现方法，由于后两种具有某种通用性，较大的实用性， 引 起 了 越 来 越 多 的 注 意 。但 是 不 管 那 种 方 法 ，大 致 都 由 三 个 阶 段 组 成 ： ①数据分析、定义错误类型；②搜索、识别错误记录；③修正错误。 数据预处理系统发展阶段： 第一阶段，尽管已有一些数据分析工具，但仍以人工分析为主。 第二阶段，有两种基本的思路用于识别错误：一种是发掘数据中 存在的模式，然后利用这些模式清理数据；另一种是基于数据的，根 据预定的清理规则，查找不匹配的记录。后者用得更多。 第三阶段，某些特定领域能够根据发现的错误模式，编制程序或 借助于外部标准文件、数据字典，来一定程度上修正错误；对数值字 段，有时能根据数理统计知识自动修正，但经常须编制复杂的程序或 借助于人工干预完成。 绝大部分数据预处理方案提供接口用于数据挖掘系统。它们一般 来说包括很多耗时的排序、比较、匹配过程，且这些过程多次重复， 用户必须等待较长时间。下面介绍一个交互式的数据清洗方案：系统28吉林大学硕士学位论文将错误检测与清洗紧密结合起来，用户能通过直观的图形界面一步步 地 指 定 清 洗 操 作 ，且 能 立 即 看 到 此 时 的 清 洗 结 果 ， （仅仅在所见的数据 上 进 行 清 洗 所 以 速 度 很 快 ）不 满 意 清 洗 效 果 时 还 能 撤 销 上 一 步 的 操 作 ， 最后将所有清洗操作编译执行。并且这种方案对清洗循环错误非常有 [11] 效 。 许多数据预处理工具提供了描述性语言解决用户友好性，降低用 户编程复杂度。数据预处理属于一个较新的研究领域，直接针对这方 面的研究并不多，中文数据清洗系统更少。现在的研究主要为解决两 个问题：发现异常、清理重复记录。4.2 发现异常所有记录中如果一个或几个字段间绝大部分遵循某种模式，其他 不遵循该模式的记录就可以认为是异常的。例如，如果一个整型字段 99%的 值 在 某 一 范 围 内（ 如 0-1 间 ） ，则 剩 下 的 1%的 记 录（ 该 字 段 &1 或 &0） 可 认 为 是 异 常 。 最 容 易 发 现 的 是 数 值 异 常 （ 特 别 是 单 一 字 段 的 数 值异常） ， 可用数理统计的方法 （如平均值、 值域、 信任区间等） 。 Maletic 和 Marcus 将 人 工 智 能 的 方 法 （ 如 聚 类 、 基 于 模 式 的 方 法 、 关 联 规 则 ） 引入到数据清洗中，并做了一些实验测试其效果。尽管这些方法在其 他领域（如数据仓库，决策支持系统）中能教好地使用，但在用于发 现异常时，却达不到预期的目的。下面介绍几种发现异常的方法： 1. 基 于 契 比 雪 夫 定 理 的 统 计 学 方 法 ： 这 种 方 法 可 以 随 机 选 取 样 本 数据进行分析，加快了检测速度，但是这是以牺牲准确性为代价的。 2. 模 式 识 别 的 方 法 ： 基 于 数 据 挖 掘 和 机 器 学 习 算 法 来 查 找 异 常 数 据，主要牵涉关联规则算法。 3. 基 于 距 离 的 聚 类 方 法 （ 聚 类 分 析 是 一 种 新 兴 的 多 元 统 计 方 法 ， 是当代分类学与多元分析的结合。聚类分析是将分类对象置于一个多 维空间中，按照它们空间关系的亲疏程度进行分类。通俗的讲，聚类 分析就是根据事物彼此不同的属性进行辨认，将具有相似属性的事物 聚为一类，使得同一类的事物具有高度的相似性。 ） ：这也是数据挖掘 中 的 算 法 ，重 点 在 于 它 的 类 的 评 测 标 准 为 Edit 距 离 ，来 发 现 数 据 集 中 的重复纪录。 4. 增 量 式 的 方 法 ： 如 果 数 据 源 允 许 ， 我 们 可 以 采 取 随 机 的 方 法 获 取元组。这允许给异常检测算法一个随机元组流的输入。一些异常检 测 算 法 对 这 种 输 入 可 以 使 用 增 量 、统 计 学 方 式 ，可 以 发 现 更 多 的 异 常 。29吉林大学硕士学位论文从数据源中获得元组，然后转换之后作为异常检测算法的输入。 异 常 的 清 洗 过 程 主 要 统 分 为 六 个 步 骤 [12]： ① 元 素 化 (elementizing) ：将 非 标 准 的 数 据 ，统 一 格 式 化 成 结 构 数 据。 ② 标 准 化 (standardizing) ：将 元 素 标 准 化 ，根 据 字 典 消 除 不 一 致 的 缩写等等。 ③ 校 验 (verifying) ： 对 标 准 化 的 元 素 进 行 一 致 性 校 验 ， 即 在 内 容 上修改错误。 ④ 匹 配 (matching) ： 在 其 它 记 录 中 寻 找 相 似 的 记 录 ， 发 现 重 复 异 常。 ⑤ 消 除 重 复 记 录 ：根 据 匹 配 结 果 进 行 处 理 ，可 以 删 除 部 分 记 录 或 者多个记录合并为一个更完整信息的记录。 ⑥ 档 案 化 (documenting) ：将 前 5 个 步 骤 的 结 果 写 入 元 数 据 存 储 中 心。这样可以更好地进行后续的清理过程，使得用户容易理解数据库 以及更好地进行切片、切块等操作。4.3 识别重复记录由于各种原因，数据中可能包含重复的记录，它们（主要指字符 串）的表示形式可能不同，但指的是同一对象实体。例如，两条记录 除 了 日 期 字 段 不 同 （ 分 别 为
） 其 它 都 相 同 ， 我 们 有 理 由 相 信 20006 就 是 2006 ， 两 记 录 应 该 是 重 复 记 录 。 检 测 这 种 语义相同，而表现形式不同的记录是数据预处理的一项重要任务，也 是目前研究最多的内容。检测出的重复记录可用两种方法处理：把一 种作为正确的，删除其它重复的记录；或者综合所有的重复记录，从 而得到更完整的信息。 标准地检测完全相同记录（两个字符串一一对应）的方法是先将 数据库中的所有记录排序，然后看邻近的记录是否相同。在数据预处 理中必须将其扩展到能识别的大致相同的记录，但即使如此，由于时 间 复 杂 性 太 大 （ 所 能 检 测 所 有 重 复 记 录 时 ， 需 比 较 N(n-1)/2 次 ， 其 中 N 为总的记录数） ，为 了 提 高 匹 配 效 率 ，有 一 种 基 本 领 近 排 序 方 法（ the Basic Sorted_Neighborhood Method) ， 其 主 要 思 想 ： 先 选 定 某 一 个 字 段 或 根 据 已 有 字 段 生 成 一 个 新 字 段 作 为 关 键 字 ，然 后 按 照 此 关 键 字 排 序 ， 将 一 个 固 定 长 度 为 W 的 窗 口 中 的 最 后 记 录 与 前 面 的 W-1 条 记 录 相 比 较。每次将窗口中最前面的一条记录作为下一轮比较对象，这种方法30吉林大学硕士学位论文相 对 地 提 高 了 识 别 速 度 ， 只 要 进 行 WN 次 比 较 （ 其 中 N 为 总 记 录 数 ） 但仍存在一些缺陷，例如，关键字的选取非常重要。选取不当时容易 造成识别遗漏，从而增加识别次数，这极大地影响了识别效率。但并 没有一种明确的方案作为选取关键字的标准，人们提出了各种改进方 法：多次选取不同字段作为关键字，将每次识别出的记录合并作为所 有重复记录。 也 可 将 基 本 领 近 排 序 法 做 改 进（ 通 过 将 排 序 的 记 录 分 成 两 个 列 表 ： 一个重复表，一个非常重复表。在这两种不同类型的表上操作）但基 本 领 近 排 序 法 的 缺 陷 仍 存 在 。这 几 种 方 法 ，都 没 有 避 免 这 样 一 个 问 题 。 为了识别更多的重复记录（高精确度）必须增加检测次数（效率低） ， 而效率高必然降低检索精度。 在 记 录 排 序 后 ，将 比 较 领 近 记 录 的 各 对 应 字 段 ，计 算 其 的 相 似 度 ， 如果两记录相似度超过了某一阀值，则记录为两条记录是相同的，否 则，认为是指向不同实体的记录，其中计算字段相似度是其核心，目 前常用的算法有： 1. 基 本 字 段 匹 配 算 法 。 其 思 想 为 ： 将 待 比 较 的 两 个 字 符 串 划 分 为 最小的子串（不包括无意义的字串）将其排序，比较一个字符串是否 与 另 一 字 符 串 子 串 相 同 或 为 起 前 缀 。 是 相 似 度 K/((|A|+|B|)/2), 其 中 |A| ， |B| 分 别 为 两 个 字 符 串 的 子 串 数 ， K 为 所 有 匹 配 的 子 串 数 的 和 。 缺 点 ： 子串匹配没有考虑非前缀缩写的情况。 2. 递 归 字 段 匹 配 算 法 。 考 虑 了 几 个 缩 写 情 况 （ 包 括 其 前 缀 、 前 缀 后缀混合、首字母缩写、前缀序列） 。其思想为：如果两字符串匹配， 其 相 似 度 为 1 ，否 则 为 0 。字 段 相 似 为 字 符 串 A 中 所 有 子 串 与 字 符 串 B 中具有最大匹配的子串的相似度的和的平均值。缺点：具有二次时间 [12] 复 杂 度 ， 及 Smith Waterman 算 法 等 。31吉林大学硕士学位论文第五章软件实现数据预处理数 据 预 处 理 软 件 是 参 照 SAS 等 数 据 挖 掘 软 件 的 一 些 特 点 和 一 些 数 据 筛 选 工 具 （ 如 DBPUT ） 、数据变量转化工具的处理流程进行的总体 设计和开发。 软件功能包括： 数据变换：数据维规约、聚集； 数据清洗：过滤异常值（空值处理、条件判定异常值处理） 、 去掉重复纪录。 数 据 选 取 之 后 首 先 要 进 行 维 规 约 ，数 据 的 维 度（ 数 据 属 性 的 个 数 ） 较低，使数据挖掘的算法的效果更好，因为维规约可以删除不相关的 特 征 并 降 低 噪 声 ，数 据 挖 掘 中 可 能 只 涉 及 到 较 少 的 属 性 如 特 征 属 性 集 ， 使用维规约降低了数据挖掘算法对时间和内存的需求。 数据的聚集，是将两个或多个对象合并成单个对象。如数据集中 记录了一段时间内在各地商店的商品销售情况，对该数据集的聚集方 法 可 以 是 用 新 的 按 商 品 分 类 汇 总（ 价 格 可 以 求 平 均 值 、销 售 额 求 合 计 ） 的 商 店 数 据 对 象 替 换 商 店 的 所 有 单 个 数 据 对 象（ 商 品 销 售 明 细 ） ，也 可 以是对数据对象进行按月、按商店，而不是按天、按商品分类的大量 记 录 进 行 挖 掘 ，这 样 聚 集 后 的 数 据 对 象 大 大 降 低 了 数 据 挖 掘 的 数 据 量 。 实际上聚集起到了标度转换的作用。 过滤异常值包括对空值处理，采用平均值、中位值或默认值替换 方法，软件筛选出数据集中某个属性为空缺值的记录，然后替换空缺 值，也可以输入判定条件筛选出异常记录，进行相应替换。 软件通过分析能对选取的数据进行多个字段和全部记录的比对， 挑选出重复记录，对重复记录进行删除处理，并保留最新一条记录。5.1 系统的总体框架及流程系统的实现采用灵活的处理流程，预处理过程首先接受已经选好 地数据样本，然后根据情况进行有选择的进行预处理工作，在进行数 据预处理过程中，可以执行维规约、聚集、过滤异常值或删除重复记 录中的一项或几项功能，但一般是要先进行维规约、聚集后再进行过32吉林大学硕士学位论文滤异常值或删除重复记录处理。当然也可以根据需要直接进行过滤异 常值或删除重复记录处理，而不经过维规约、聚集等环节，系统的框 架及流程如下：数据抽样数据变换维规约聚集数据清洗过滤异常值（空值处理）去掉重复纪录准备好的数据 用于数据挖掘图 5.1 系 统 的 框 架 及 流 程 图1. 数 据 选 取 数据选取是从用户的原始数据库中由用户指定选出用户感兴趣的 与知识发现任务相关的数据表项，用户在选择过程中可以通过查看所 选数据表的记录数据，来作出进一步的选择判断，通常用户都是对数 据库中的数据包含的某个主题感兴趣，希望通过数据挖掘工具对相关 数据的操作来发现该主题下一些隐含的规律，从而对所从事的行业行 为 有 所 指 导 。而 数 据 库 中 的 数 据 数 量 巨 大 ，涵 盖 范 围 也 相 对 比 较 广 泛 ， 有些数据表格中的数据根本上是没有联系的，如果不对数据库进行简 单筛选，则会使无用数据参与挖掘过程，造成各种资源上的浪费。更 为 严 重 的 问 题 是 ，由 于 一 般 挖 掘 算 法 仅 对 抽 象 的 数 据 进 行 操 作 , 即 使 完 全不相关的数据也会挖掘出规律，这种规律可以说毫无实际意义，仅33吉林大学硕士学位论文是数据海量造成的结果。考虑到数据量的巨大，如果完全由人来进行 选取是不现实的，一般我们采取人机结合的方式由人来选择较高概念 层次上的数据类别，而通过预先编制好的程序来选择数据库中具体的 数据表格。如果数据挖掘在数据仓库的基础上进行，那么操作起来会 方便一些。如果没有建立数据仓库，在数据表选取的时候会遇到所谓 实体识别问题，即同一实体在不同数据表中由不同的属性来表示，通 常我们可以通过元数据的查询来解决这一问题，实体识别问题在数据 表属性一致化中将得到根本解决。 2. 数 据 表 属 性 一 致 化 当待挖掘的数据表已经选取完毕时，我们开始对这些数据表中的 数据进行挖掘前的预处理。首先，在数据表的属性这一层次上进行统 一 ，主 要 解 决 上 边 提 到 的 实 体 识 别 问 题 。具 体 来 说 , 一 个 在 商 品 销 售 数 据 库 中 ，商 品 名 称 字 段 在 一 个 数 据 表 中 可 能 记 为“ 商 品 名 称 ” ，而 在 另 一个数据表中可能以拼音来描述： “ spmc ” ，作为挖掘前的准备，需要 根据数据字典对同一实体的不同命名表示来进行一致化，得到一个统 一的、清晰的数据表示。具体实现方法可以以其中的某一个表示方式 为准，更改其他的表示方式，或者重定义一个表示。需要注意的是， 有时候同一属性的属性值有可能采用不同的度量单位，如商品质量等 级有的表示为一等、二等、三等，有的表示为优质、中等、一般等， 我们可以根据需要来确定一个标准，并且规定一个转换方式，将非标 准表示转换为标准表示。所有的更改需要记录下来，已备将来查阅或 者数据更新时需要。 3. 在 数 据 预 处 理 方 法 选 取 上 应 根 据 不 同 的 数 据 情 况 有 选 择 的 进 行，比如实际试验对于商店销售记录，一般应先进行维规约去掉操作 员、商品描述信息、备注等字段，因为这些信息可能对数据挖掘没有 意义。对于商品销售信息聚集就有着十分重要的意义，可以按地域或 时间的维度去观察数据，希望能挖掘出关于不同季度的商品销售的有 关知识，就应该对数据进行按时间、地域等方面的聚集，原来的商品 销售是按天的明细，可以计算出按月的累计情况再进行数据挖掘。选 取适当的角度对数据进行聚集对数据挖掘的结果十分重要。5.2 系统的功能模块及实现情况软件采用开发环境： Jdk-1.5.0-windows-i586.Multi-language.34吉林大学硕士学位论文Eclipse-SDK-3.1.2-win32 数 据 库 采 用 目 前 较 流 行 ： Oracle9i 软件实现的维规约、聚集、过滤异常值、去掉重复记录算法都采 用插件的方式开发，使得算法能较好的被数据挖掘系统灵活调用。5.2.1 数 据 变 换 中 的 维 规 约软件实现维规约是找到数据的特征表示，用维变换或转换来找到 数据的不变式以减少有效变量的数目。 数 据 归 约 可 以 通 过 聚 集 、删 除 冗 余 特 性 或 聚 类 等 方 法 来 压 缩 数 据 。 这些数据处理技术在数据挖掘之前使用，可以大大提高数据挖掘模式 的 质 量 ， 降 低 实 际 挖 掘 所 需 要 的 时 间 。 而 数 据 归 约 (datareduction) 得 到 数 据 集 的 压 缩 表 示 ， 它 虽 小 但 能 够 产 生 同 样 的 (或 几 乎 同 样 的 )分 析 结 果 。 有 许 多 数 据 归 约 的 策 略 ， 包 括 数 据 聚 集 (例 如 :建 立 数 据 立 方 体 )、 维 归 约 (例 如 :通 过 相 关 分 析 ,去 掉 不 相 关 的 属 性 )、 数 据 压 缩 (例 如 :使 用 诸 如 最 短 编 码 或 小 波 等 编 码 方 案 )和 数 字 归 约 (例 如 :使 用 聚 类 或 参 数 模 型 等 较 短 的 表 示 替 换 数 据 )、 概 化 也 可 以 归 约 数 据 。 用于数据分析的数据可能包含数以百计的属性，其中大部分属性 与 挖 掘 任 务 不 相 关 ，是 冗 余 的 。例 如 ，分 析 任 务 是 按 顾 客 听 到 广 告 后 , ， 是 否 愿 意 在 该 商 场 买 流 行 的 磁 带 将 顾 客 分 类 ，与 属 性 age 、music 、taste 不同，诸如顾客的电话号码多半是不相关的。冗余特征重复地包含了 一个或多个属性中的许多或所有信息。例如，一种产品的购买价格和 所支付的销售税额包含许多相同的信息。不相关特征包含对于手头的 数据挖掘任务几乎完全没用的信息， 如 学 生 的 ID 号 码 对 于 预 测 学 生 的 总平均成绩是不相关的。冗余和不相关的特征可能降低分类的准确率 或所发现的聚类的质量。 尽管领域专家可以挑选出有用的属性，但这可能是一项困难而费 时的任务，特别是数据的行为不清楚时更是如此。遗漏相关属性或留 下不相关属性是有害的，会导致所用的挖掘算法无所适从，导致发现 的模式质量很差。此外，不相关或冗余的属性增加了数据量，可能会 减 慢 挖 掘 速 度 ， 维 归 约 通 过 删 除 不 相 关 的 属 性 (或 维 )减 少 数 据 量 。 当确定分析问题的主题后，与该主题相关的属性可能很多，其中35吉林大学硕士学位论文大部分属性可能与挖掘并不相关。通常使用属性子集选择方法。属性 子集选择的目标是找出最小属性集，使得数据类的概率分布尽可能地 接近使用所有属性的原分布，在压缩的属性集上进行挖掘，它减少了 出现在发现模式上的属性数目，使得模式更易于理解。 如何找出原属性的一个好的子集，穷举搜索可能是不现实的，特 别是当属性集的数目很大的时候。因此，对于属性子集选择，通常使 用压缩搜索空间的启发式算法。通常，这些算法是贪心算法，在搜索 属性空间时，总是做看上去是最佳的选择的策略是做局部最优选择， 期望由此导致全局最优解。实践中，这种贪心方法是有效的，并可以 接近最优、最好的解。 属 性 使 用 统 计 意 义 的 测 试 选 择 ，这 种 测 试 假 定 属 性 是 相 互