数据挖掘的发展历史
数据挖掘的发展历史是建立在相关学科发展的基础上的。随着数据库技术的发展及数应用,人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息,
简单的查询和统计已经无法满足商业的需求,需要出现一种挖掘数据背后隐藏的知识的手段。
同时,计算机技术的另一领域-人工智能自 1956 年诞生之后取得了重大进展。经历了博 弈时期、自然语言理解、知识工程等阶段,目前的热点是机器学习。
用数据库管理系统来存储数据,用机器学习的方法来分析数据,挖掘大量数据背后的知识,这两者的结合促成了数据库中的知识发现(KDD:Knowledge D
iscovery in Databases)的产生。数据库中的知识发现是一门交叉性学科,涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、
高性能计算、专家系统等多个领域。从数据库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许多方面。
1989 年 8 月在美国底特律召开的第 11 届国际人工智能联合会议的专题讨论会上首次出 现知识发现(KDD)这个术语。此后,由美国人工智能协会主办的
KDD 国际研讨会已经召开了 8 次,规模由原来的专题讨论会发展到国际学术大会,研究重点也逐渐从发现方法转向系统应用,注重多种发现策略和技术的集
成,以及多种学科之间的相互渗透。
数据挖掘(DM)是知识发现(KDD)最核心的部分。1998 年第四届知识发现与数据挖掘国际学术会议上不仅进行了学术讨论,并且有 30 多家软件公司
展示了他们的数据挖掘软件产品,不少软件已在北美、欧洲等国得到应用。经历十多年的发展,数据挖掘已经成为一个自成体系的应用学科。
数据挖掘应用的主要对象是海量数据,这正符合电信行业的特点。所以数据挖掘技术兴起不久,特别是成熟的软件产品问世后,立刻就在电信业得到应用。数
据挖掘是作为电信行业商业智能建设的一个重要组成部分,是近年来国内外电信企业关注的焦点之一。不妨看看一些世界知名电信运营企业的数据挖掘应用情
况。
1.英国电信采用数据挖掘手段,建立模型来确定潜在客户的购买倾向和他们变为用户之后可能的价值。建立精确的客户特征以后,英国电信打算开发针对于特
定客户群的产品。
2.沃达丰利用数据挖掘技术建立模型研究客户离网的原因,并从不同的角度来进行市场细分.
3. 法国电信利用数据挖掘技术在预防欺诈、客户流失分析和预测、交叉销售等各方面都取得很多成果。
4.NTT 在自己的 CRM 系统 COMWARE 中使用数据挖掘的方法来分析数据和提高对客户的管理水平!
5.韩国 SK Telecom 公司的 CRM 中,应用数据挖掘技术分析客户和通话行为,预测通话中的掉线情况。
国外知名的电信运营企业都已经建立起了自己的商业智能系统。国内的电信企业对此也越来越重视。不少企业已经发布了经营分析系统和 CRM 类系统相关的
业务标准。一些地方的运营商已经成功的实现了部分功能。
无论国内还是国外,数据挖掘领域都是一个方兴未艾的技术,其应用前景很广。麻省理工学院的《科技评论》杂志去年提出未来 5 年对人类产生重大影响的 1
0 大新兴技术,“数据挖掘”位居第三。近年电信行业数据挖掘的热潮正佐证了这一点。
数据挖掘算法工具集
随着数据量的增加,需要利用数据库或者数据仓库技术进行管理,所
以数据挖掘系统与数据库和数据仓库结合是自然的发展。现实领域的问题是多种
多样的,一种或少数数据挖掘算法难以解决,同时,挖掘的数据通常不符合算法
的要求,需要有数据清洗、转换等数据预处理的配合,才能得出有价值的模型。
1995 年左右软件开发商开始提供称之为"工具集"的第二代数据挖掘系统
[Shapiro00]。主要因为在应用中发现用户需要多种类型 的数据挖掘算法,而且
大部分精力都花费在数据清理和预处理阶段。典型的系统有 IBM Intelligent
Miner、SPSS 的 Clementine、SAS 的 Enterprise Miner、SGI 的 MineSet、Oracle
Darwin 等。此类工具集的特点是提供多种数据挖掘算法(通常有关联规则、分
类和聚类等),同时也包括数据的转换和可视化。由于此类工具并非面向特定的
应用,可以称之为横向的数据挖掘工具(Horizontal Data Ming Tools)。
数据挖掘解决方案
随着横向的数据挖掘工具的使用日渐广泛,人们也发现这类工具只有
精通数数据挖掘算法的专家才能熟练使用,如果对算法不了解,难以得出好的模
型。所以为了推动数据挖掘技术的应用,从 1999 年开始,大量的数据挖掘工具
研制者开始提供纵向的数据挖掘解决方案(Vertical Solution),即针对特定
的应用提供完整的数据挖掘方案。这些方案提供商有 KD1(主要用于零售业)、
Options&Choice(主要用于保险业)、HNC(欺诈行为侦测)和 Unica Model 1(主
要用于市场营销)等(www.kdnuggets.com/software)。对于纵向的解决方案,
数据挖掘技术的应用多数还是为了解决某些特定的难题,而嵌入在应用系统中。
例如,在证券系统中嵌入神经网络预测功能、在欺诈检测系统中嵌入欺诈行为的
分类/识别模型、在客户关系管理系统中嵌入客户成簇/分类功能或客户行为分析
功能、在机器维护系统中嵌入监/检测或识别难以定性的设备故障功能、在数据
库营销中嵌入选择最可能购买产品的客户功能、在机场管理系统中嵌入旅客人数
预测、货运优化功能、在基因分析系统中嵌入 DNA 识别功能、在制造/生产系统
中嵌入质量控制功能等。这样一些应用就要利用数据挖掘系统作为工具来开发应
用系统所必须的数据挖掘功能。即,用数据挖掘系统来建立数据挖掘模型。然后
将模型嵌入应用系统中解决难题。这里要注意的是,由于时间的变化,数据也发
生变化,数据中所含有的信息和知识也随之发生变化(例如,在网络入侵检测系
统中,新的入侵方法和行为不断出现和变化;在新产品出现后,客户的兴趣会发
生变化,客户类群也将发生变化),因此旧的模型需要更新。这时必须重新在数
据挖掘系统上、在包含新数据的情况下来建立新的模型,然后将新的模型用于应
用系统。
5、数据挖掘技术的应用前景
2002 年麻省理工学院的《科技评论》杂志提出未来 5 年对人类产生重
大影响的 10 大新兴技术,"数据挖掘"位居第三。
数据挖掘应用领域非常广阔 先期将在数据积累比较充分的领域银行、
证券、电信等领域到应用,以后将在各行各业各领域中获得应用。只要数据积累
充分,就需要数据挖掘技术。
数据挖掘技术将被社会长期使用 随着信息化工作的深入发展,计算机
中积累的数据只会越来越多,人们会越来越重视对这些信息的挖掘利用,所以对
数据挖掘技术的需求也会越来越大。当然,数据挖掘技术本身会不断发展进步,
该技术将被长期使用。
数据挖掘技术相对门槛较高 掌握这门技术需要有数理统计学、数据
库、人工智能等基础,硕士研究生才可能有这样的基础,再通过努力学习才可能
较好地掌握这门技术,因此目前国内数据挖掘人才奇缺,从而造成了较高的技术
门槛。
下图是数据挖掘技术应用开发的几个层次。
我们仅仅以银行为例来介绍一下数据挖掘技术的应用。近年来,在金
融信息化的框架下,银行业的信息基础建设不断完善,网络平台建设逐步迈向成
熟。依托网络平台,国有商业银行加快了实现数据大集中建设的步伐。如工商银
行已经将该行系统内的所有的交易和管理集中在北京和上海两个大中心进行。
而接下来金融信息化面临的任务就是:在数据大集中的基础上,利用
数据挖掘技术建立起有效的数据集成、管理、利用机制,即建立商业银行数据挖
掘软件系统,充分挖掘数据价值,为银行科学化管理决策和发展新的业务服务。
2002 年以来,商业银行对数据挖掘技术需求的快速升温,各商业银行相继将数
据挖掘应用列入近年实施计划,充分说明了这一大趋势。如交通银行已经在全行
推广应用采用数据挖掘技术的客户分析系统,并拟在其他业务中应用数据挖掘技
术。
风险管理:识别、防范和控制银行卡申办和使用过程中的各种风险,
其业务流程包括客户档案的录入与审核、资信评估与信用控制、基础数据分析、
为客户提供分类服务、透支管理控制、诉讼、预警等多个环节。
数据挖掘和知识发现的技术、方法及应用
一幅凝固的油画
Keywords:
data mining,Knowledge discovery in databases,DM,KDD,CRISP-DM,Internet
概念
基于 Internet 的全球信息系统的发展使我们拥有了前所未有的丰富数据。大量
信息在给人们带来方便的同时也带来了一大堆问题:第一是信息过量,难以消化;
第二是信息真假难以辨识;第三是信息安全难以保证;第四是信息形式不一致,
难以统一处理。数据丰富、知识贫乏已经成为一个典型问题。Data Mining(数
据挖掘)的目的就是有效地从海量数据中提取出需要的答案,实现“数据-〉信
息-〉知识-〉价值”的转变过程。
Data Mining(数据挖掘)是指用非平凡的方法从海量的数据中抽取出潜在的、
有价值的知识(模型或规则)的过程。该术语还有其他一些同义词:数据库中的
知识发现(Knowledge discovery in databases)、信息抽取(Information
extraction)、信息发现(Information discovery)、智能数据分析(Intelligent
data analysis)、探索式数据分析(exploratory data analysis)、信息收获
(information harvesting)、数据考古(data archeology)等。
数据挖掘的发展历程大致如下:
•1989 IJCAI 会议: 数据库中的知识发现讨论专题
–Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley,
1991)
•1991-1994 KDD 讨论专题
–Advances in Knowledge Discovery and Data Mining (U. Fayyad, G.
Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996)
•1995-1998 KDD 国际会议 (KDD’95-98)
–Journal of Data Mining and Knowledge Discovery (1997)
•1998 ACM SIGKDD, SIGKDD’1999-2002 会议,以及 SIGKDD Explorations
•数据挖掘方面更多的国际会议
–PAKDD, PKDD, SIAM-Data Mining, (IEEE) ICDM, DaWaK, SPIE-DM, etc.
Data Mining(数据挖掘)是数据库研究、开发和应用最活跃的一个分支,是多
学科的交叉领域,它涉及数据库技术、人工智能、机器学习、神经网络、数学、
统计学、模式识别、知识库系统、知识获取、信息提取、高性能计算、并行计算、
数据可视化等多方面知识。
数据挖掘技术从一开始就是面向应用的,它不仅是面向特定数据库的简单检索查
询调用,而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理,
以指导实际问题的求解,企图发现事件间的相互关联,甚至利用已有的数据对未
来的活动进行预测。例如加拿大 BC 省电话公司要求加拿大 SimonFraser 大学 KDD
研究组,根据其拥有十多年的客户数据,总结、分析并提出新的电话收费和管理
办法,制定既有利于公司又有利于客户的优惠政策。这样一来,就把人们对数据
的应用,从低层次的末端查询操作,提高到为各级经营决策者提供决策支持。这
种需求驱动力,比数据库查询更为强大。同时,这里所说的数据挖掘,不是要求
发现放之四海而皆准的真理,也不是要去发现崭新的自然科学定理和纯数学公
式,更不是什么机器定理证明。所有发现的知识都是相对的,是有特定前提和约
束条件、面向特定领域的,同时还要能够易于被用户理解,最好能用自然语言表
达发现结果。因此数据挖掘的研究成果是很讲求实际的。
技术
Data Mining(数据挖掘)主要任务有数据汇总、概念描述、分类、聚类、相关
性分析、偏差分析、建模等。具体技术包括:
统计分析(statistical analysis)
常见的统计方法有回归分析(多元回归、自回归等)、判别分析(贝叶
斯分析、费歇尔判别、非参数判别等)、聚类分析(系统聚类、动态聚类等)和
探索性分析(主元分析法、相关分析法等)。其处理过程可以分为三个阶段:搜
集数据、分析数据和进行推理。
决策树(decision tree)
决策树是一棵树,树的根节点是整个数据集合空间,每个分节点是对一个单一变
量的测试,该测试将数据集合空间分割成两个或更多块。每个叶节点是属于单一
类别的记录。首先,通过训练集生成决策树,再通过测试集对决策树进行修剪。
决策树的功能是预言一个新的记录属于哪一类。
决策树分为分类树和回归树两种,分类树对离散变量做决策树,回归树对连续变
量做决策树。
通过递归分割的过程来构建决策树:1 寻找初始分裂,整个训练集作为产生决策
树的集合,训练集每个记录必须是已经分好类的。决定哪个属性(Field)域作
为目前最好的分类指标。一般的做法是穷尽所有的属性域,对每个属性域分裂的
好坏做出量化,计算出最好的一个分裂。量化的标准是计算每个分裂的多样性
(diversity)指标 GINI 指标。2 树增长到一棵完整的树,重复第一步,直至每
个叶节点内的记录都属于同一类。3 数据的修剪,去掉一些可能是噪音或者异常
的数据。
其基本算法(贪心算法)为:自上而下分而治之的方法,开始时,所有的数据都
在根节点;属性都是种类字段 (如果是连续的,将其离散化);所有记录用所选
属性递归的进行分割;属性的选择是基于一个启发式规则或者一个统计的度量
(如, information gain)。停止分割的条件:一个节点上的数据都是属于同一个
类别;没有属性可以再用于对数据进行分割。
伪代码(Building Tree)为:
Procedure BuildTree(S){
用数据集 S 初始化根节点 R
用根结点 R 初始化队列 Q
While Q is not Empty do {
取出队列 Q 中的第一个节点 N
if
N 不纯 (Pure) {
for 每一个属性 A
估计该节点在 A 上的信息增益
选出最佳的属性,将 N 分裂为 N1、N2
}
}
}
属性选择的统计度量为:?信息增益——Information gain (ID3/C4.5),所有属
性假设都是种类字段,经过修改之后可以适用于数值字段;?基尼指数——Gini
index (IBM IntelligentMiner),能够适用于种类和数值字段。
关联规则(correlation rules)
规则反映了数据项中某些属性或数据集中某些数据项之间的统计相关性,其一般
形式为: X1∧…∧Xn Y[C,S],表示由 X1∧…∧Xn 可以预测 Y,其中可信度为 C,
支持度为 S。
设 I={i1,i2,…,im}是二进制文字的集合,其中的元素称为项(item)。记 D为交
易(transaction)T的集合,这里交易 T是项的集合,并且 T 5;I 。对应每一个
交易有唯一的标识,如交易号,记作 TID。设 X是一个 I中项的集合,如果 X 5;T,
那么称交易 T包含 X。
一个关联规则是形如 XÞY 的蕴涵式,这里 XÌI, YÌI,并且 XÇY=F。规则 XÞY 在交
易数据库 D 中的支持度(support)是交易集中包含 X 和 Y 的交易数与所有交易
数之比,记为 support(XÞY),即
support(XÞY)=|{T:XÈY 5;T,TÎD}|/|D|
规则 XÞY 在交易集中的可信度(confidence)是指包含 X 和 Y 的交易数与包含 X
的交易数之比,记为 confidence(XÞY),即
confidence(XÞY)=|{T: XÈY 5;T,TÎD}|/|{T:X 5;T,TÎD}|
给定一个交易集 D,挖掘关联规则问题就是产生支持度和可信度分别大于用户给
定的最小支持度(minsupp)和最小可信度(minconf)的关联规则。
基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。布尔型关联
规则处理的值都是离散的、种类化的,它显示了这些变量之间的关系;而数值型
关联规则可以和多维关联或多层关联规则结合起来,对数值型字段进行处理,将
其进行动态的分割,或者直接对原始的数据进行处理,当然数值型关联规则中也
可以包含种类变量。基于规则中数据的抽象层次,可以分为单层关联规则和多层
关联规则。在单层的关联规则中,所有的变量都没有考虑到现实的数据是具有多
个不同的层次的;而在多层的关联规则中,对数据的多层性已经进行了充分的考
虑。基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。在单
维的关联规则中,我们只涉及到数据的一个维,如用户购买的物品;而在多维的
关联规则中,要处理的数据将会涉及多个维。
Agrawal 等于 1993 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题,
其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘
问题进行了大量的研究。他们的工作包括对原有的算法进行优化,如引入随机采
样、并行的思想等,以提高算法挖掘规则的效率;提出各种变体,如泛化的关联
规则、周期关联规则等,对关联规则的应用进行推广。
Agrawal 等在 1993 年设计了一个基本算法,提出了挖掘关联规则的一个重要方
法 — 这是一个基于两阶段频集思想的方法,将关联规则挖掘算法的设计可以分
解为两个子问题:
1) 找到所有支持度大于最小支持度的项集(Itemset),这些项集称为频集
(Frequent Itemset)。
2) 使用第 1 步找到的频集产生期望的规则。
这里的第 2 步相对简单一点。如给定了一个频集 Y=I1I2...Ik,k³2,Ij∈I,产生
只包含集合{I1,I2,...,Ik}中的项的所有规则(最多 k条),其中每一条规则的
右部只有一项,(即形如[Y-Ii]ÞIi,"1£i£k)。一旦这些规则被生成,那么只有那
些大于用户给定的最小可信度的规则才被留下来。对于规则右部含两个以上项的
规则,在其以后的工作中进行了研究。为了生成所有频集,使用了递推的方法。
其核心思想如下:
L1 = {large 1-itemsets};
for (k=2; Lk-1 5;F; k++)
{
Ck=apriori-gen(Lk-1);
//新的候选集
for all transactions tÎD
{
Ct=subset(Ck,t);
//事务 t 中包含的候选集
for( all candidates cÎ Ct )
c.count++;
}
Lk={cÎ Ck |c.count³minsup}