数据挖掘技术综述

数据挖掘技术综述

1新一代知识基于数据的提取随着数据库技术的发展和数据库管理系统的广泛应用，数据库中存储的数据数量急剧增加（指数增加），数据理解和数据生成之间存在着越来越大的差距。在堆积如山的数据中包含着许多待提取的有用知识,这些有用知识如同成熟的庄稼,不及时收割便会浪费,人们迫切需要新一代的计算技术和工具来帮助开采数据山中蕴藏的矿藏,并加以提炼,使之成为有用知识。于是,一个新的研究领域——知识发现应运而生。由于蕴藏知识的数据信息大多存储于数据库中,因此又称作数据库中的知识发现(KnowledgeDiscoveryinDatabase)或者数据挖掘(DM——DataMining)。2工资计算的一般过程在KDD96国际会议上,根据知识发现研究领域知名学者的阐述,一个被一致接受的KDD定义表述如下:“对数据库中蕴涵的、未知的、有潜在应用价值的、非平凡的模式的提取”。其中,“模式”是指用高级语言表示的表达一定逻辑含义的信息,通常指数据库中数据之间的逻辑关系(也即要发现的知识)。而“非平凡”则是指在KDD中,知识的发现过程应具有某种不断定性和一定的自由度。对于能够以确定的计算过程提取的模式(如在人事数据库中,已知职工的工资,求出职工的总工资或平均工资等问题),一般称之为平凡知识,而平凡知识不是KDD的目标。一般地,KDD的基本原理可用如下的处理过程加以说明:(1)首先熟悉应用领域的数据、背景知识,明确所要完成的KDD/DM任务性质;(2)数据选择根据用户要求,从数据库中提取与KDD相关的数据,KDD将主要从这些数据中进行数据提取;(3)数据预处理与转换从与KDD相关的数据集合中除去明显错误的数据和冗余的数据,进一步精减所选数据中的有用部分,并将数据转换成为有效形式,以使数据开采更有效;(4)数据挖掘(DM)根据KDD发现任务的要求,选择合适的数据开采算法(包括选取合适的模型和参数),在数据库中寻求感兴趣的模型,并用一定的方法表达成某种易于理解的形式;(5)模式解释对发现的模式进行解释和评估,必要时需要返回前面处理中的某些步骤以反复提取;(6)知识评价将发现的知识以用户能理解的方式提供给用户,并试用之。从以上的处理步骤来看,整个发现过程不是简单的线性流程,步骤之间包含了循环和反复。上述众多处理环节实际上也可简化为:KDD=数据预处理十DM十解释评价。由于预处理和解释评价研究较为成熟,目前KDD的研究和实现难点都集中在数据挖掘上。作为KDD的一个特定而关键步骤,数据挖掘是最为重要的。正是因为如此,人们在很多场合往往不加区分地使用KDD和DM这两个术语。3数据库中的常用研究算法鉴于数据挖掘对于KDD的重要性,数据挖掘集中了研究人员的主要精力,相关的研究工作也取得了较大的进展。通常,根据发现任务与发现目标的不同,数据挖掘器所能发现的典型知识主要包括以下几类:(1)关联规则(Associationrule)所谓关联规则,是指数据对象之间的相互依赖关系,而发现规则的任务就是从数据库中发现那些确信度(Confidence)和支持度(Support)都大于给定值的强壮规则。从数据库中发现关联规则近几年研究最多。目前,已经从单一概念层次关联规则的发现发展到多个概念层次的关联规则的发现。在概念层次上的不断深入,使得发观的关联规则所提供的信息越来越具体,实际上这是个逐步深化所发现知识的过程。在许多实际应用中,能够得到的相关规则的数目可能是相当大的,而且,用户也并不是对所有的规则感兴趣,有些规则可能误导人们的决策,所以,在规则发现中常常引入“兴趣度”(指一则在一定数据域上为真的知识被用户关注的程度)概念。而基于更高概念层次上的规则发现研究(如一般化抽象层次上的规则和多层次上的规则发现)则是当前研究的重点之一。在数据挖掘中,常见的关联规则发现算法有:AIS、SETM、APriori、DHP、ML-T2L1、ML-TML1等,其中,Apriori和DHP是比较成功的两个算法。(2)分类(Classification)分类是最基本的一种认知形式。数据分类就是对数据库中的每一类数据,挖掘出关于该类数据的描述或模型,而这些数据库中的类是事先利用训练数据建立起来的。作为数据挖掘的一个重要主题,数据分类在统计学、机器学习、人工智能等领域中得到了较早的研究,只是近些年来,人们才将它与数据库技术结合起来解决实际问题。在数据挖掘中,分类算法的研究成果较多,常用的数据分类算法有:CART、C45、ID3、SLIQ、Knn、GA-Knn等。(3)聚类(Clustering)在机器学习中,数据分类称为监督学习,而数据聚类则称为非监督学习,两者所采用的方法相差甚远。数据聚类是将物理的或抽象的对象分成几个群体,在每个群体内部,对象之间只有较高的相似性,而在不同群体之间,相似性则比较低。一般地,一个群体也就是一个类,但与数据分类不同的是,聚类结果主要基于当前所处理的数据,我们事先并不知道类目结构及每个对象所属的类别。另外,数据聚类计算量巨大,其时间复杂度也要比数据分类大得多。目前,数据聚类已有很多不同的方法和技术,常见的算法有PAM、CLARA、CLARANS、BIRCH等。除上述主要发现目标外,数据挖掘所发现的知识类型还有特征规则、趋势分析、异常分析、模式分析等。数据挖掘中使用的技术和方法主要来自以下相关学科和技术领域:(1)统计学统计学方法旨在从抽样分析中提取未知的数学模型。在数据挖掘中常常会涉及一定的统计过程,如数据抽样和建模、判断假设以及误差控制等。(2)决策树(DecisionTree)决策树方法上要用于数据分类。一般分成两个阶段:树的构造和树的修剪。首先利用训练数据生成一个测试函数,根据不同取值建立树的分支;在每个分支子集中重复建立下层结点和分支,从而生成一棵决策树。然后对决策树进行剪枝处理,最后把决策树转化为规则,利用这些规则可以对新事例进行分类。基于决策树的分类方法与其它分类方法比较起来,具有速度较快、较易转化成简单且容易理解的分类规则、较易转换成数据库查询语句等优点,尤其在问题维数高的领域可以得到很好的分类结果。(3)人工神经网络(NeuralNetworks)人工神经网络在结构上模仿生物神经网络,是一种通过训练来学习的非线性预测模型,在数据挖掘中可用来进行分类、聚类、特征采掘等操作。(4)遗传算法遗传算法走一种优化技术,它利用生物进化的一系列概念进行问题的搜索,最终达到优化的目的。在遗传算法的实施中,首先要对求解的问题进行编码(称为染色体),产生初始群体,然后计算个体的适应度;再进行染色体的复制、交换、突变等操作,产生新个体。重复这个操作,直到求得最佳或较佳个体。在数据挖掘中,往往把数据挖掘任务表达为一种搜索问题,使用遗传算法强大的搜索能力,找到最优解。(5)粗集(RoughSet)粗集理论是一种处理含糊和不确定问题的新型数学工具,它具有较强的数学基础、方法简单、较强的针对性和计算量小等优点。利用粗集理论可以处理的问题包括数据简化、数据相关性发现、数据意义的评估、数据的近似分析等。(6)模糊逻辑(FuzzyLogic)模糊逻辑糙模糊集合与布尔逻辑的融合。一个公式的真值,可在区间任意取值。在数据挖掘和KDD中,常用来进行证据合成、置信度计算等。(7)可视化技术可视化技术采用直观的图形方式将信息模式、数据的关联成趋势呈现给用户(决策者),以便用户交互地分析数据关系。一般说来,不存在一个普遍适用的数据挖掘方法。一个方法或算法在某个领域非常有效,但在另一个领域却可能不太适合。因此,在实际应用中,需要针对特定的领域,精心选择有效的数据挖掘模型与挖掘算法。而对于一个成功的KDD系统,选择合适的模型与算法常被视为是一个非常重要的技巧。4drs页面过滤方法在个人网页上的应用—数据挖掘技术的应用从已经出现的KDD/DM原型系统和应用系统来看,应用KDD/DM技术的领域都是信息丰富、环境多变、尚无模型、需要知识帮助进行管理和决策的领域。例如,由美国市场研究公司A.C.Nielsen公司推出的市场预测系统OpportunityExplorer、通用电器公司(GE)和法国飞机制造公司(SNECMA)合作研制的飞机故障发现系统CASSIOPEE、用于医疗保健的KEFIR系统、监测地壳构造活动的Quakfinder系统、宇宙图像分类分析系统SCICAT、基因发现和构造核糖核酸模型的HAMMs和SAM系统、寻找最佳投资时机的AI(AutomatedInvestor)系统,等等。上述系统大多基于传统的数据库技术,在KDD领域多已取得较好的应用效果,有关它们的详细情况,很多期刊和会议文献中都有介绍和分析。本文对此不打算多做论述,这里主要想对近年来数据挖掘在Web上的一些应用研究进行说明和介绍。目前,基于Web的数据挖掘工作才刚刚起步,比较典型的几个系统有:(1)Ahoy!这是一个个人主页搜索系统。用户只要输入个人的姓名以及机构或单位名称等信息,Ahoy!就可以在WWW网上找到此人的主页(URL)。Shakes在Ahoy!系统中,使用DRS(DynamicsReferenceSift)页面过滤方法,实现了个人网页的挖掘和较为精确的定位。其实现原理是:首先,根据用户输入的姓名等信息,DRS把它传递给元搜索引擎MetaCrawler,MetaCrawler查询后,会返回许多候选主页;DRS还同时把名字传给E-mail目录服务(WhoWhere和IAF),得到许多E-mail地址(以便于与机构名对比)。然后,利用内部数据库,DRS采用两种类型的过滤器(基于交叉的过滤和基于启发的过滤)将明显不正确的URL排除,剩下的URL则作为候选URL排列在一些称为桶的类别中。最后,分别判断候选的URL是否和个人姓名、机构名匹配以及页面和个人主页的相似程度,从而得到最终的个人主页。DRS最关键之处是它的模式抽取,即它能够从成功的搜索结果中抽取某一国家或机构URL的通用模式,并记录下来,供将来使用。这种学习适应能力,使得DRS在使用过程中,能逐步提高精确率和覆盖面。(2)ParaSite这是一个比较简单的WWW网结构知识挖掘系统。在ParaSite系统中,Spertus把超级链接按方向分成这样几类:.向上链接:所指向的文档目录是同一服务器的上层目录;.向下链接:所指向的文档目录是同一服务器的下层目录;.交叉链接:所指向的文档父目录与本目录没有父子关系;.向外链接:所指向的文档在其它的服务器。通过考察一些搜索引擎(例如Yahoo!等)的目录结构,获取一系列启发性规则,如:.如果两个URLU1和U2在同一个页面中距离很近,那么它们有可能具有类似的主题或特征;.在一个层次索引中,从一个页面开始,由向下或交叉链接得到的页面,其主题和原始页面的主题相关:.从一个索引开始,任何由本页面的向外链接得到的页面,其主题很可能是相同的;……利用这些规则,ParaSite系统中的搜索器就可以得到页面之间的结构关系,从而实现发现个人主页、搜索新页面和自动索引等目的。(3)WebKBWebKB是卡内基梅隆大学(CMU)的万维网信息挖掘研究项目。它致力于建造一个大型的知识库,这样的知识库能够推动对WWW网更有效的信息抽取,以及对基于Web的知识推理和问题求解的支持。WebKB中提供了多种信息挖掘的方法,这些方法采用了许多比较成熟的NLP技术,功能很强,既可以适应多个特定的类别,也可以在理论上支持通用信息的挖掘,不过实现的难度都比较大。WebKB具有多种基本的学习能力,其采用的学习方法主要是文本分类的统计方法和一阶文本分类方法。(4)ShophotShopbot是这样一个系统,它能够针对商业网页,从产品制造商或销售商的主页中提取关于产品的一些属性,如价格等,通过比较,为用户选择一个最佳的购买商。(5)Predict(6)WebMiner这是国家自然科学基金会资助的一项研究。WebMiner的目标是实现一个人机交互的基于Web的数据挖掘系统,它采掘的对象是Web上指定的某类事物,通过对该类事物领域知识和文本格式的学习,从中提取有用的数据放到数据仓库中,然后在数据仓库中进行关联规则采掘和数据分类。整个系统主要由五部分构成:Web资源获取模块WebObtainer、Web数据过滤模块WebFilter、数据挖掘模块Miner以及用来进行挖掘的数据仓库和一个领域知识库。与数据库中的信息不同,Web网上的信息具有无序、非结构化、动态、多样性等特点,有时数据源之间还可能存在冗余、不一致甚至矛盾,因此基于Web的数据挖掘工作难度很大,上述系统或研究项目所做的工作还都是初步的、开创性的。但数据挖掘技术应用于WWW网,特别是和Web上的搜索引擎技术的结合,无疑会对网络信息的发现、搜集、查询、利用等带来巨大的效益和光明的前景。5dd/dm研究的前景展望数据挖掘是一个多学科交叉的新兴研究领域,在这个新兴领域中,汇集了来自机器学习、模式识别、数据库、统计学、人工智能以及管理信息系统等各学科的成果,多元化的投入,使得这一学科得以蓬勃发展,而且已初具规模。除学术上的需要外,极大的商业应用前景更是推动KDD/DM研究不断深入的关键因