数据挖掘概念及国内外现状

摘要：随着信息技术的高速发展，人们积累的数据量急剧增长，如何从海量的数据中提取有用的知识成为当务之急。数据挖掘就是为顺应这种需要应运而生发展起来的数据处理技术。其主要任务是关联分析、分类、预测时序模式和偏差分析等。是知识发现（knowledge discovery in database）的关键步骤。数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种商业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展到对数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系，从而促进信息的传递。

关键词：Data Mining；数据仓库；OLAP；K均值算法；K中心点算法

中图分类号：TP311 文献标识码：A 文章编号：1007-9599 （2012） 20-0000-03

1 基本概念

对于技术人员来说，Data Mining[1]指的是由许多看似没有规则并且混乱不完整的现实数据中，提炼出其深层次并且不易为人所知的，却具有潜在价值的数据信息和资料的过程。对于商业人员而言，Data Mining则可以帮助他们合理整理商业数据的好方法，因为它可以对这些Database里将大部分的业务数据执行提炼、变换、剖析以及一些模型化操作，之后得到可以帮助商业决策的信息，比如牛奶和婴儿尿布的关联性信息。总的来说，Data Mining的工作就是对数据进行关联性分析，提炼出规则。它有以下几个重要的元素[2]：

1.1 知识

人类通过不断的实战而得到的宝贵经验；被检测的相关数据状态的变化规则；从数据中提取得到的不具体事物。知识的形式可能为数据模板、关联规则、数据变动、数据异常或者其他具实际用途的结构。

1.2 模式

针对集合（Collection） 里的所有元素，能够使用语言（Language） 来展示这些元素本质上的特征，然后整理得到一个表达式（Expression） ， 里所说的元素是 中的某个子集 。仅仅在 比 里所有数据的展示方法更加简单的时候， 会成为模式。

1.3 概念/类别描述

指对数据集构建一个简洁的总体性描述并/或描述它与某一对照数据集的差别。

1.4 关联分析

从一个项目集中发现关联规则（Association Rules），该Rules表现了被挖掘的数据综合起来会得到的属性-值条件这样的元组。

1.5 分类与估值

分类指通过分析一个类别已知的Database的特点来建立一组模型M，M能够被用来预测类别未知的以后的数据。该分类模型可以表现为多种形式：分类规则（ ），决策树或者数学公式，甚至是神经网络。估值与分类类似，只不过它要预测的不是类别，而是一个连续的数值。

1.6 时间序列分析

也就是预测（ ），是指通过对大量时间序列数据的分析找到特定的规则和感兴趣的特性，包括搜索相似序列或者子序列，挖掘序列模式、周期性、趋势和偏差。

2 OW与OLAP

数据仓库（OW或OWH）[3]指的是在公司管理和决策里面向主题的（Subject-oriented）、集成的（Integrated）、与时间有关的（Time-related）、不能被改动的数据集合，所谓面向应用，指的是系统实现过程中主要围绕着一些应用或功能。而面向主题则考虑一个个的问题域，对问题域涉及到的数据和分析数据所采用的功能给予同样的重视；OW里的数据来源于很多不同的Database，由于历史的原因，每个Database的组织结构通常是不同的，当这些不同结构的数据还没输入到OW的时候，必须经历一个集成过程；OW以维的形式对数据进行组织，时间维是数据仓库中很重要的一个维度，并且数据仓库中的数据时间跨度大，从几年甚至到几十年，称为历史数据；面向应用的事务Database应该不断的执行数据插入（Insert）、更新（Update）操作，而对于OW里的数据只是做初始的导入和记录查询操作。OW的组成如图1-1所示。

图1-1 OW组成图

OW的管理器包含三个[4]：（1）加载管理器，即Load Manager，执行提炼与Load程序；（2）仓库管理器，即Warehouse Manager，执行数据的Arrange与Convert程序、Backup与Kept程序；（3）查询管理器，即Query Manager，执行Query和Manage程序。

，即 ，是OW的分析展示工具，它创建的基础是数据的多维视图（Multidimensional Views，即MV），其特点包含以下两个：一是 ，表现在其对User的请求信息可以快速的Response以及交互式（interactive）操作；二是 ，是 的核心。 与 的区别如表1-1所示。

表1-1 与 的区别

用户 职员、IT人员 知识工作人员

功能 日常操作 决策支持

数据库设计 Application-oriented Subject-oriented

数据特点 当前的，更新的；

详细的，关系型的；

孤立的 历史的；

汇总的，多维的；

集成的

使用 repetitive ad-hoc

存取方式 读/写；

索引 大量的扫描

工作单元 简单的事务办理 复杂的查询

记录访问量 几十 上百万

用户数量 数以千计 数以百计

数据库规模 100MB-GB 100GB-TB

按照数据的集成方式， 可以分为两种：基于多维Database的 （MD-OLAP）和基于关系Database的 （ROLAP）。MD-OLAP响应速度快、执行效率高，但源于结构的局限，灵活性不高；比较而言，ROLAP因为是建立于很多现存Database（或者OW）的基础上，它的可变性和扩展性会更好，而且其所能承受的数据量会更大、对于多维数据的操作性更强。因此，ROLAP尽管在Response速度、操作的效率上没MD-OLAP好，却还是被很多人使用。现有的 工具大多基于ROLAP。

对OW中数据的操作是针对MV（又被称为超立方体）开展的。基于MV的经典操作为：切片、切块以及旋转等。切片就是说在一个多维数组（MA）上裁剪出某个二维的子集；切块是指在一个MA上裁剪出某个三维的子集；旋转指的是随意转动MV展示的方位，使得人们能够根据不同视角更加清楚和直观地观测数据信息。

将 与数据挖掘结合起来，发展出一种为数据挖掘服务的具有新型 的数据仓库，即 （ ）将更能满足需要。

3 基本算法

本文主要是对重要资料进行聚类（Clustering）和整理（Arrange），而经典的两个Clustering算法是： 均值算法和 中心点算法[5]。

3.1 均值算法（KMA）

KMA是一种简便、实用的不受监督的Clustering算法。它在已知簇的个数时，能够很好地对数据信息进行聚类并分析。其基本思想为：首先，在所有数据元素中任意选择 个成为聚类的中心点；然后，计算其它点到这些聚类中心点的距离，通过对簇中距离平均值的计算，不断改变这些聚类中心的位置，直到这些聚类中心不再变化为止。该算法的大致流程如图1-2所示：

图1-2算法流程

算法如下：

输入： 个数据的数据集合和已知有 个簇

输出： 个数据所属的 个簇中的哪个的信息

算法步骤：

1）随机从 个数据中选择 个当作初始的簇中心CC；

2）将剩余的 个数据按照一定的距离函数DF划分到最相近的簇；

3）repeat；

4）按一定的DF得出所有簇里的数据所有属性的平均值，并且把它当作新的CC；

5）重新将 个数据按照一定的距离函数划分到最相近的簇；

6）直到簇的中心不会变动为止。

3.2 中心点算法（KCA）

KCA是KMA的一个改进，它的基本思想为：一开始给每个簇任意的给予某个样本（Sample）作为中心点（Center），而剩下来的这些点根据距离的大小进行划分；随后用其它的非Center数据作为Center，并查看聚类情况。如果替换的聚类总代价小于零，那么就执行替换直到中心点不再发生变化，也就是说达到代价最小值时停止算法。KCA流程跟KMA类似，如图1-3所示。

图1-3算法流程

算法如下：

输入： 个簇，共有 个Sample

输出：各样本属于 个簇的信息

算法步骤：

1）任意选择 个Sample作为初始Center；

2）repeat；

3）将非Center的数据依照与各Center的距离划分到最近的簇中；

4）随机的在非Center中选择一个Sample；

5）计算使用该点做Center来代替原Center的代价；

6） 用该点替换原Center，形成新的簇集合；

7）直到Center不会有变动为止。

本文在写作过程中得到了陈志刚老师多次精心指导，在此表示感谢.

参考文献：

[1]M.Berry and G.Linoff.Data Mining Techniques.John Wiley，1997.

[2]William S.Cleveland.The Elements of Graphing Data，revised，Hobart Press，1994.

[3]R.Kennedy，Lee，Reed，and Van Roy.Solving Pattern Recognition Problems.Prentice-Hall，1998.

[4]U.Fayyad，Piatetsky-Shapiro，Smyth，and Uthurusamy.Advanced in Knowledge Discovery and Data Mining.MIT Press，1996.

[5]Vasant Dhar and Roger Stein.Seven Methods for Transforming Corporate Data into Business Intelligence.Prentice Hall，1997.