




已阅读5页,还剩59页未读, 继续免费阅读
(计算机应用技术专业论文)基于rs理论的增量更新算法在数据挖掘中的研究与应用.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
摘要 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 摘要:数据挖掘是数据库系统和数据库应用的一个有希望的、欣欣向荣的学科前沿。 它是一个多学科领域,从多个学科吸取营养。进行数据挖掘的方法有许多,而r s 方 法便是其中的主要方法之一,本文主要研究基于r s 理论的增量更新算法。文中在对 r s 理论进行研究,在分析和综合基于r s 理论的数据挖掘算法基础上,给出了扩展差 别矩阵和扩展决策矩阵的定义,提出了新的属性约简算法和增量更新算法,即基于 扩展差别矩阵的属性约简算法和基于扩展决策矩阵的增量式规则获取算法,讨论和 研究了规则的增量更新算法。由于使用了增量更新算法和并行处理技术,从而提高 了数据挖掘的效率,降低了时间复杂度。通过实验,应用实例说明此算法是正确, 有效和可行的。 关键词:数据挖掘:知识发现;r s 理论;增量更新算法;扩展差别矩阵;扩展决策 矩阵;数据约简;并行算法 a b s t r a c t s t u d yo f i n c r e m e n t a lu p d a t i n g a l g o r i t h mb a s e do u r o u g hs e tt h e o r ya n d i t sa p p l i c a t i o ni nd a t am i n i n g a b s t r a c t :d a t am i n i n g ( m d ) i sa p r o m i s i n ga n df l o u r i s h i n gf r o n t i e ri nd a t a b a s es y s t e m a n dd a t a b a s ea p p l i c a t i o n s d a t am i n i n gi sam u l t i d i s c i p l i n a r yf i e l d , d r a w i n gf r o mm a n y d i s c i p l i n e s t h e r ea r el o t so fm e t h o d sf o rd a t am i n i n g a n dr o u g hs e tm e t h o d o l o g yi s o n eo fi m p o r t a n tm e t h o d t h i sp a p e rs t u d ya ni n c r e m e n t a lu p d a t i n ga l g o r i t h mb a s e do n r o u g hs e tt h e o r y i nt h i sp a p e r , r o u g hs e tt h e o r yh a sb e e nd i s c u s s e d ,b ya n a l y z i n ga n d s y n t h e s i z i n gd a t am i n i n ga l g o r i t h mb a s e do nr o u g hs e tt h e o r y , d e f i n i t i o no fe x t e n d e d d i s c e r n i b i l i t ym a t r i xa n de x t e n d e dd e c i s i o nm a t r i xh a sb e e ni n t r o d u c c x l , n e wa t t r i b u t e r e d u c t i o na l g o r i t h ma n di n c r e m e n t a lu p d a t i n ga l g o r i t h mh a v eb e e np r e s e n t e d , m m e l y , a t t r i b u t er e d u c t i o na l g o r i t h mb a s e do n t e n d e dd i s c e m i b i l i t ym a t r i xa n di n c r e m e n t a lr u l e a c q u i s i t i o na l g o r i t h mb a s e do ne x t e n d e dd e c i s i o nm a t r i x ,i n c r e m e n t a lu p d a t i n ga l g o r i t h m o fr u l e sh a sb e e nd i s c u s s e da n dr e s e a r c h e d i n c r e m e n t a lu p d a t i n ga l g o r i t h ma n dp a r a l l e l p r o c e s s i n gt e c h n o l o g ya r eu s e d ,w h i c hi m p r o v e st h ee f f i c i e n c yo fd a t am i n i n ga n d d e d u c e st h ec o m p l e xo ft i m e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi s e f f i c i e n ta n df e a s i b l e w r i t t e nb y :x i a os h u i j i n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db y :p r o f b a i s h i x u e k e yw o r d s :d a t am i n i n g ;k n o w l e d g ed i s c o v e r ;r o u g hs e tt h e o r y ;i n c r e m e n t a l u p d a t i n ga l g o r i t h m ;e x t e n d e dd i s c e r n i b i l i t ym a t r i x ;e x t e n d e dd e c i s i o nm a t r i x ;d a t a r e d u c t i o n ;p a r a l l e la l g o r i t h m 独创性声明 y9 2 8 7 7 4 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人 已经发表或撰写过的研究成果,也不包含为获得南昌史学或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 学位敝作者躲方枷签字魄易年,月矿日 学位论文版权使用授权书 本学位论文作者完全了解 壶墨叁鲎 有关保留、使用学位论文的规定,有 权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。 本人授权壹量圭堡可以将学位论文的全部或部分内容编入有关数据库进行检索, 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位敝储繇方班办新妣旧“芬 签字日期:乡咿占年广月扩日 签字日期:搠易年5 月,子臼 学位论文作者毕业后去向: 工作单位:、劫易水力 通讯地址:p 即物氕弓朔耙 电话:f 聊。归7 钙 邮编:宇弓卿” 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 1 1 论文的研究意义 第一章前言 随着数据库技术的迅速发展以及数据库管理系统的广泛应用,人们积累的数据 越来越多,产生和收集数据的能力已经迅速提高。起作用的因素包括在大部分商业 产品中的广泛使用,许多商务、科学和行政事务的计算机化,以及由文本和图像扫 描平台到卫星遥感系统的数据收集工具的进步。激增的数据背后隐藏着许多重要的 信息,人们希望能够对其进行更高层次的分析,以便更好地利用这些数据。目前的 数据库系统可以高效地实现数据的录入、查询、统计等功能,但无法发现数据中存 在的关系和规则,无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐 藏的知识的手段,导致了“数据爆炸但知识贫乏”的现象n 1 。此外,作为全球信息 系统的i n t e r n e t ( f e b ) 的流行,已经将人们淹没在数据和信息的汪洋大海之中,无 边无尽,难以辨别哪些数据有用,哪些数据没有用。若要提取有用的信息,需要花 费大量的人力和时间。传统的数据库概念、方法和技术已经难以解决现在所面临的 新问题。而且,若要从数据中发现和提取知识,更是一件不容易的事。存储数据的 爆炸性增长已经激起对新技术和自动工具的需求,以便帮助我们将海量数据转换成 有用的信息和知识。因此,我们必须找到有关方法,自动地分析数据、自动地对数 据进行分类、自动地对数据进行汇总、自动地发现和描述数据中的趋势、自动地标 记异常。所以,一种能分析数据,并提出新的为人所理解的知识的计算机系统应运 而生,而这一过程就是数据挖掘( d a t am i n i n g ,简称d m ) 。数据挖掘是一种能够智能 地自动地把数据转换成有用信息和知识的枝术和工具。数据挖掘已经在邮政、银行、 金融保险、企业管理、医疗机构、电子政务、d n a 分析、证券、零售业、电信业、语 言识别等行业得到了广泛的应用,并对它们的发展起了积极的作用。 数据挖掘使数据库技术进入了一个更高级的阶段,它不仅能对过去的数据进行 查询和遍历,并且能够找出过去数据之间的潜在联系,从而促进信息的传递。现在 数据挖掘技术已经应用于商业中,因为对这种技术进行支持的三种基础技术已经 发展成熟,它们分别是: 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 ( 1 ) 海量数据搜集 ( 2 ) 强大的多处理器计算机 ( 3 ) 数据挖掘算法 数据挖掘是数据库系统和数据库应用的一个有希望的、欣欣向荣的学科前沿。 数据挖掘通常又称为数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ,简称 k d d ) ,是自动的或方便的模式提取,这些模式代表隐藏在大型数据库、数据仓库或 其它大量信息存储中的知识。 数据挖掘是一个多学科领域,从多个学科吸取营养圆。这些学科主要包括数据 库技术、人工智能、机器学习、神经网络、统计学、模式识别、知识库系统、知识 获取、信息检索、高性能计算和数据可视化等。 进行数据挖掘的方法有许多,而r s 方法便是其中的主要方法之一 2 , 3 1o 一般来讲, 大多数机构建立数据库的目的是为了有效的管理信息资源。也就是说,在大多数机 构,数据被存储在数据库中很少是专门为了挖掘发现知识,而且数据库会有许多不 完善之处,常常包含许多对发现规则来讲是冗余的和不必要的属性,不确定值或会 导致不精确测量的错误、噪音等。如果这些冗余属性不去掉,不仅发现规则的时间 复杂性增长,而且发现规则的质量也要下降。而r s 方法是一种采用新方法来处理不 精确性和不确定数据的数学方法。r s 方法可以用来处理这些类型的问题,它可以对 数据进行预处理,通过属性和值约简约去冗余信息,从而可提高发现效率,降低错 误率。随着k d d 的兴起,r s 理论越来越受至u k d d 研究者的重视,因为r s 理论有其先天 的优势: ( 1 ) k d d 研究的对象多为关系型数据库。关系表可被看作为r s 理论中的决策表,这给 r s 方法的应用带来了极大的方便。 ( 2 ) 现实世界中的规则有确定性的,也有不确定性的。从数据库中发现不确定性知 识,为r s 方法提供了用武之地。 ( 3 ) 从数据中发现异常,排除知识发现过程中的噪声干扰也是r s 方法的特长。 ( 4 ) 运用r s 方法得到的知识发现算法有利于并行执行,可以极大的提高发现效率。 对于大型数据库中的知识发现来说,这是非常关键的。 ( 5 ) k d d 采用的其它技术,如神经网络的方法,不能自动的选择合适的属性集,而利 2 r 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 用r s 方法进行预处理,去掉冗余属性,可以提高发现效率。 ( 6 ) 用r s 方法得到的决策规则及推理过程,比模糊集方法或神经网络方法,更容易 验证和检测。 k d d 理论的研究和发展使得信息技术应用越来越广泛,银行、电信、电力和证 券等部门积累了大量的数据,同时这些部门的数据每天都在不断地增加,但是新增 数据和原来积累的数据相比要少得多,在这些数据上进行数据挖掘,如果每一次都 要在所有数据上进行重新计算显然是不划算和不现实的:由于有变化的只是新增数 据,如果能有一种算法只要研究新增数据就能得到与处理所有数据相同的结果,那 么在效率和效益上肯定都有很大的提高,因此在这种新的形势下研究增量更新算法 成为了一种现实的迫切需求,r s 理论目前是否具备有这方面的算法呢? 1 2 国内外增量算法的研究现状 自从1 9 8 2 年r s 理论创立至今己有2 0 多年的历史了,但是在r s 理论增量更新算法 方面的研究却不多,而且实际应用效果不明显。主要的研究有加拿大的s h a n n 、z i a r k o w 嘲,日本的s h u s a k ut s u m o t o 嘲,韩国的l i o n c h u fb a n g 蚴,美国的c h i e n c h u n g 吲 和中国的刘宗田嗍等。这些人的研究主要都是理论上的分析,而且存在一定的缺陷 和不足。目前,常见的增量更新算法有a s r a i 算法旧、s h a n 算法踟、i u a r 算法剐、f i u a 算法、l 从算法嘲等算法。本文结合r s 理论的特性和增量数据挖掘的特点,提出 了一种新的增量更新算法基于扩展决策矩阵的增量规则更新算法,并通过实例 说明算法的正确性和有效性。 1 3 论文的组织结构 第一章为前言,主要介绍了论文的研究意义和国内外增量更新算法的研究现状; 第二章综述了数据挖掘的基本概念和基本思想;第三章概括地介绍了r s 理论的基本概 念,提出了扩展差别矩阵和扩展决策矩阵的概念;第四章介绍了数据预处理的几种典 型方法;第五章介绍了数据挖掘中的增量更新算法:第六章介绍了基于扩展差别矩阵 的属性约简算法和基于扩展决策矩阵的增量规则更新算法,并用实例加以说明论证。 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 第二章数据挖掘的基本概念 近年来,数据挖掘( d a t am i n i n g ,简称d m ) 引起了信息产业界的极大关注,其主 要原因是存在大量数据,可以广泛使用,并且迫切需要将这些数据转换成有用的信 息和知识。本章主要介绍数据挖掘的基本概念n 到: 2 1 数据挖掘的重要意义 数据挖掘引起信息产业界的极大关注的主要原因是存在大量数据,可以广泛使 用,并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识有广泛 的应用,包括商务管理、市场分析、工程设计、科学探索、信息管理、查询处理、 决策支持、过程控制以及其它领域。例如:高度自动化地分析企业原有的数据,做出 归纳性的推理,从中挖掘出潜在的模式,预测客户的行为,帮助企业的决策者调整 市场策略,减少风险,做出正确的决策。 数据挖掘是信息技术自然演化的结果。演化过程的见证是数据库业界开发以下 功能:数据收集和数据库创建,数据管理( 包括数据存储和检索,数据库事务处理) , 以及数据分析与理解( 涉及数据仓库和数据挖掘) 。 自2 0 世纪6 0 年代以来,数据库和信息技术已经系统地从原始的文件处理演化到 复杂的、功能强大的数据库系统。自7 0 年代以来,数据库系统的研究和开发已经从 层次和网状数据库系统发展到开发关系数据库系统( 数据存放在关系表结构中) 、数 据建模工具、索引和数据组织技术。自8 0 年代中期以来,数据库技术的特点是广泛 接受关系技术,研究和开发新的、功能强大的数据库系统。在过去的几十年里,计 算机硬件技术的迅速发展提供了大量的功能强大的计算机、数据收集设备和存储介 质。这些技术大大推动了数据库和信息产业的发展,使得大量数据库和信息存储用 于事务管理、信息检索和数据分析。 现在,数据可以存放在不同类型的数据库中。例如,一种新的数据结构是数据 仓库,这是一种多个异种数据源在单个站点以统一的模式组织的存储,以支持管理 决策。数据仓库技术包括数据清理、数据集成和联机分析处理( o n - l i n ea n a l y t i c a l p r o c e s s i n g ,简称o l a p ) ,o l a p 是一种分析技术,具有汇总、合并和聚集功能,以及 4 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 从不同的角度观察信息的能力。 随着计算机技术的迅速发展,人类收集各种数据的能力也在随之迅速地增长, 使得各种相关种类的数据库也相应地越来越大,但人类处理数据信息的能力却远远 落后于收集数据的能力。数据的丰富激发了人们对强有力的数据分析工具的渴望。 面对数据丰富,知识贫乏的大量数据,人们已经无能为力。结果,收集在大型数据 库中的数据变成了“数据坟墓”一一难以再访问的数据档案。因此,重要的决定常常 不是基于数据库中丰富的数据信息,而是基于决策者的直觉,因为决策者缺乏从海 量数据中提取有价值知识的工具。除此之外,当前的专家系统系统通常依赖用户或 领域专家人工地将知识输入知识库,然而,这一过程常常有偏差和错误,并且耗时、 费用高。所以,人们渴望一种能够从大量数据中挖掘出真实、准确而有效信息的数 据分析工具。在这种情况下,数据挖掘工具应运而生。利用数据挖掘工具进行数据 分析,可以发现重要的数据模式,对商务决策、知识库、科学和医学研究作出了巨 大贡献。数据和信息之间的鸿沟要求系统地开发数据挖掘工具,将“数据坟萼”转 换成知识“金块”。 2 2 数据挖掘的定义 目前对数据挖掘的描述有许多不同的说法,一种普通的描述如下:数据挖掘就 是从大量的不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人 们事先不知道的、但又是潜在有用的信息和知识的过程n 1 。简单地说,数据挖掘是 从大量数据中提取或“挖掘”知识,即“从数据中挖掘知识”圆。挖掘抓住了从大 量的、未加工的材料中发现少量“金块”这一过程的特点。还有一些术语,具有和 数据挖掘类似但稍有不同的含义,如数据库中知识挖掘、知识提取、数据模式分析、 数据考古和数据捕捞。虽然对数据挖掘有许多不同定义,但它们几乎都使用日益增 强的计算机技术和高级统计分析技术( 如:神经网络、基因算法等等) 来揭示大型数据 库中的可用关系。 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是数据 挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 具有先前未知、有效和可实用三个特征。先前未知的信息是指该信息是预先未曾预 料到的,即数据挖掘是要发现那些不能靠直觉发现的信息或知识,甚至是违背直觉 的信息或知识,挖掘出的信息越是出乎意料,就可能越有价值。在商业应用中最典 型的例子就是一家连锁店通过数据挖掘发现了“小孩尿布和啤酒之间有着惊人的联 系 。 有些人把数据挖掘视为另一个常用的术语数据库中的知识发现( k d d ) 的同义 词。而另一些人却认为数据挖掘是数据库中知识发现过程的一个基本步骤。知识发 现过程,如图l 所示,由以下步骤组成圆。 ( 1 ) 、数据清理( 消除噪声或不一致数据) : ( 2 ) 、数据集成( 多种数据源可以组合在一起) : ( 3 ) 、数据选择( 从数据库中检索与分析任务相关的数据) : ( 4 ) 、数据变换( 数据变换或统一成适合挖掘的形式,如通过汇总或聚集操作) : ( 5 ) 、数据挖掘( 基本步骤,使用智能方法提取数据模式) : ( 6 ) 、模式评估( 根据某种兴趣度度量,识别表示知识的真正有趣的模式) : ( 7 ) 、知识表示( 使用可视化和知识表示技术,向用户提供挖掘的知识) 。 敏姐i :i 乍 ;j 提j | 盘= 什 图1 知识发现的全过程 由此可见,数据挖掘只是知识发现过程中的一个步骤。因为它发现隐藏的模式, 所以是最重要的一步。数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给 6 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 用户,或作为新的知识存放在知识库中。 本文采用了数据挖掘的广义观点:数据挖掘是从存放在数据库、数据仓库或其 它信息库中的大量数据中挖掘有趣知识的过程。 按照这种观点,典型的数据挖掘系统具有以下主要成分( 如图2 所示) : ( 1 ) 数据库、数据仓库或其它信息库:这是一个或一组数据库、数据仓库、电子表格 或其它类型的信息库,可以在数据上进行数据清理和集成。 ( 2 ) 数据库或数据仓库服务器:根据用户的数据挖掘请求,数据库或数据仓库服务器 负责提取相关数据。 ( 3 ) 知识库:这是领域知识,用于指导搜索或评估结果模式的兴趣度。 ( 4 ) 数据挖掘引擎:这是数据挖掘系统基本的部分,由一组功能模块组成,用于特征 化、关联、分类、聚类分析以及演变和偏差分析。 ( 5 ) 模式评估模块:通常,此成分使用兴趣度度量,并与数据挖掘模块交互,以便将 搜索聚焦在有趣的模式上。 ( 6 ) 、图形用户界面:本模块在用户和数据挖掘系统之间通信,允许用户与系统交互, 指定数据挖掘查询或任务,提供信息,帮助搜索聚焦,根据数据挖掘的中间结果进行 探索式数据挖掘。 散 图2 典型的数据挖掘系统结构 数据挖掘是涉及多学科技术的交叉学科瞄3 ( 如图3 所示) ,包括数据库技术、数学 技术、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、信息 检索、图像与信号处理和空间数据分析等。通过数据挖掘,可以从数据库提取有趣 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 的知识、规律或高层信息,并可以从不同角度观察或浏览。发现的知识可以用于决 策、过程控制、信息管理、查询处理等。 图3 数据挖掘受多学科的影响 数据挖掘可以在任何类型的信息存储上进行乜3 。这包括关系数据库、事务数据 库、数据仓库、高级数据库系统、展开文件和i n t e r n e t ( w e b ) 。高级数据库系统包 括面向对象和对象一关系数据库:面向特殊应用的数据库,如空间数据库、时间序列 数据库、文本数据库和多媒体数据库等。数据挖掘技术从一开始就是面向应用的, 它不仅是面向特定数据库的简单检索、查询和调用,而且要对这些数据进行统计、 分析、综合和推理,以指导实际问题的求解,企图发现事件间的相互关联,甚至利 用已有的数据对未来的活动进行预测。因此,就把人们对数据的应用,从低层次的 末端查询操作,提高到为各级经营决策者提供决策支持,这种需求驱动力比数据库查 询更为强大。但是通过数据挖掘所有发现的知识都是相对的而不是绝对的,都有其 特定前提和约束条件、面向特定领域的,同时还要能够易于被用户理解,最好能用 自然语言表达发现结果。因此d m k d ( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) 的研 究成果是很讲求实际的。 2 3 数据挖掘过程 数据挖掘过程中各步骤的基本内容如下n 1 ( 如图4 所示) : ( 1 ) 确定业务对象 清晰地定义出业务问题,认清数据挖掘的目的是数据挖掘的重要一步。挖掘的 最后结构是不可预测的,但要探索的问题应是有预见的,为了数据挖掘而数据挖掘 则带有盲目性,成功的可能性相当小。 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 ( 2 ) 数据准备 数据的选择:搜索所有与业务对象有关的内部和外部数据信息,并从中选择出适 用于数据挖掘应用的数据。 数据的预处理:研究数据的质量,为进一步的分析做准备,并确定将要进行的挖掘 操作的类型。 数据的转换:将数据转换成一个分析模型。这个分析模型是针对挖掘算法建立的。 建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 ( 3 ) 数据挖掘:对所得到的经过转换的数据进行挖掘。除了完善从选择合适的挖掘 算法外,其余一切工作都应该能自动地完成。 ( 4 ) 结果分析:解释并评估结果,其使用的分析方法一般应作数据挖掘操作而定,通 常会用到可视化技术。 ( 5 ) 知识的同化:将分析所得到的知识集成到业务信息系统的组织结构中去。 2 4 数据挖掘的功能 图4 数据挖掘的基本过程和主要步骤 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般分 为两类:描述和预测。描述性挖掘任务刻划了数据库中数据的一般特性。预测性挖掘 任务在当前数据上进行分析、推断,以进行预测。有些情况下,用户不知道他们的数 据中什么类型的模式是有趣的,最可能的做法是并行地搜索多种不同的模式。所以 数据挖掘系统要能够挖掘多种类型的模式是非常重要的,这样才能适应不同的用户 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 需求或不同的应用。 数据挖掘功能以及它们可以发现的模式类型介绍如下馏1 : 2 4 1 概念类描述:特征化和区分 数据可以与类或概念相关联,用汇总的、简洁的、精确的方式描述每个类和概 念可能是有用的。这种类或概念的描述称为类概念描述( c l a s s c o n c e p t d e s c r i p ti o n ) 。这种描述可以通过下述方法得到: ( 1 ) 数据特征化,一般地汇总所研究类( 通常称作目标类( t a r g e tc l a s s ) ) 的数据: ( 2 ) 数据区分,将目标类与一个或多个比较类( 通常称作对比类( c o n t r a s t i n g c l a s s ) ) 进行比较: ( 3 ) 数据特征化和比较 数据特征化( d a t ac h a r a c t e r i z a t i o n ) 是目标类数据的一般特征或特性的汇总。 通常,用户指定类的数据通过数据库查询收集。例如,为研究上一年销售增2 1 2 0 的软件产品的特征,可以通过执行一个s q l 查询收集关于这些产品的数据。 数据区分( d a t ad i s c r i m i n a t i o n ) 是将目标类对象的一般特性与一个或多个对 比类对象的一般特性比较。目标类和对比类由用户指定,而对应的数据通过数据库 查询检索。例如,可能想要将上一年销售增2 1 2 0 的软件产品与同一时期销售至少下 降2 0 的那些产品进行比较。用于数据区分的方法与用于数据特征化的类似。 2 4 2 关联分析 关联分析( a s s o c i a t i o na n a l y s i s ) 发现关联规则( 关联规则是发现交易数据库 中不同商品( 项) 之间的联系,通过这些规则找出顾客购买行为模式,如购买了某一 商品对购买其它商品的影响。发现这样的规则可以应用于商品货架设计、货存安排 以及根据购买模式对用户进行分类) ,这些规则展示属性一值频繁地在给定数据集中 同时出现的条件。关联分析广泛地用于购物篮或事务数据分析。 关联规则( a s s o c i a t i o nr u l e ) 是形如xj 】,即: “a 1 人a 2a 人a 。jb l b 2 人b 。” l o 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 的规则,其中,4 0 = 1 , 2 ,m ) ,易( = 1 , 2 ,玎) 是属性一值对。关联规则“xj y ” 解释为“满足x 中条件的数据库元组多半也满足】,中条件”。关联规则所涉及的属 性称为维,包含了单维关联规则和多维关联规则。 现在有了很多有效的关联规则挖掘算法,在本文的第六章将会讨论一些典型的 关联规则挖掘算法。 2 4 3 分类和预测 现在数据库的内容丰富,蕴藏了大量的信息,这些信息都可以用来作为智能的 商务决策。分类和预测是数据分析的两种形式,可以用来提取描述重要数据类的模 型或预测未来的数据趋势。然而,分类是预测分类标号( 或离散值) ,而预测建立连 续值函数模型。例如,可以建立一个分类模型,对银行货款的安全或风险进行分类, 同时可以建立预测模型,给定潜在顾客的收入和职业,预测他们在计算机设备上的 花费。许多分类和预测方法已被机器学习、专家系统、统计学和神经生物学等方面 的研究者提出。 2 4 3 1 分类和预测概念 分类( c l a s s i f i c a t i o n ) 是找出描述并区分数据类型或概念的模型( 或函数) ,以 便能够使用模型预测类标记未知的对象类。分类可以用来预测数据对象的类标记, 但是,在某些应用中,人们可能希望预测某些空缺的或不知道的数据值,而不是类 标记。当被预测的值是数值数据时,通常称之为预测( p r e d i c t i o n ) 。尽管预测可以 涉及数据值预测和类标记预测,通常预测仅限于值预测,因此不同于分类。预测也 包含基于可用数据的分布趋势识别。 数据分类( d a t ac l a s s i f i c a t i o n ) 分两步:第一步,建立一个模型,描述预定的 数据类集或概念集。通过分析由属性描述的数据库元组来构造模型。假定每个元组 属于一个预定义的类,由一个称作类标号属性( c l a s sl a b e la t t r i b u t e ) 的属性确定。 对于分类,数据元组也称作样本、实例或对象。第二步,使用模型进行分类,并评估 模型( 分类法) 的预测准确率,并利用准确率确定满足一定条件的模型,用它对类标 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 号未知的数据元组或对象进行分类。 2 4 3 2 分类和预测的预处理问题 数据进行如下的预处理,可以提高分类和预测过程的准确性、有效性和可伸缩 性。 ( 1 ) 数据清理:是旨在消除或减少数据噪声( 例如使用平滑技术) 和处理空缺值( 例 如,用该属性最常出现的值,或根据统计用最可能的值替换空缺值) 的数据预处理。 尽管大部分分类算法都有处理噪声和空缺值的机制,但该步骤有助于减少学习时的 混乱。 ( 2 ) 相关性分析:数据中有许多属性可能与分类和预测任务不相关。例如,记录银行 货款申请是星期几提出的数据可能与申请的成功与否不相关,此外,其它属性也可 能是冗余的。因此,可以进行相关分析,删除学习过程中不相关的或冗余的属性。 这一步需要在分类和预测之前进行,它试图识别对于分类和预测无用的属性,这些属 性应当删除。 ( 3 ) 数据变换:数据可以概化到较高层概念。对于连续值属性,这一步非常有用。 为了分析和说明分类和预测方法的效果,可以根据下列标准对分类和预测方法 进行比较和评估: ( 1 ) 预测的准确率:这涉及模型正确地预测新的或先前未见过的数据的类标号的能 力。 ( 2 ) 速度:这涉及产生和使用模型的计算花费。 ( 3 ) 强壮性:这涉及给定噪声数据或具有空缺值的数据,模型正确预测的能力。 ( 4 ) 可伸缩性:这涉及给定大量数据,有效地构造模型的能力。 ( 5 ) 可解释性:这涉及模型提供的理解和洞察的层次。 分类和预测具有广泛的应用,包括荣誉证实、医疗诊断、性能预测和选择购物 虚盘 口o 1 2 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 2 4 4 聚类分析 聚类( c l u s t e r i n g ) 是把一组个体按照相似性归成若干类别,即“物以类聚 。 它的目的是使得属于同一类别的个体之间的距离尽可能的小,而不同类别上的个体 间的距离尽可能的大。聚类方法包括统计方法、机器学习方法、神经网络方法和面 向数据库的方法。 在统计方法中,聚类称聚类分析,它是多元数据分析的三大方法之一( 其它两 种是回归分析和判别分析) 。它主要研究基于几何距离的聚类,如欧氏距离、明考斯 基距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类 法、有序样本聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较 的聚类,它需要考察所有的个体才能决定类的划分,因此它要求所有的数据必须预先 给定,而不能动态增加新的数据对象。聚类分析方法不具有线性的计算复杂度,难 以适用于数据库非常大的情况。 聚类分析数据对象,而不考虑已知的类标记。一般情况下,训练数据中不提供 类标记,因为不知道从何开始聚类,可以用于产生这种标记。对象根据最大化类内 的相似性、最小化类间的相似性的原则进行聚类或分组,使得在一个簇中的对象具 有很高的相似性,而与其它簇中的对象又很不相似。所形成的每一个簇可以看作一 个对象类,由它可以导出规则。 2 4 5 孤立点分析 数据库中可能包含一些数据对象,它们与数据的一般行为或模型不一致。这些 数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪声或异常而丢 弃。但是在某些应用中( 如欺骗检测) ,罕见的事件可能比正常出现的那些更有趣。 孤立点数据分析称作孤立点挖掘( o u t li e rm i n i n g ) 。 孤立点可以使用统计试验检测。它假定一个数据分布或概率模型,并使用距离 度量,到其它聚类的距离最大的对象被视为孤立点。基于偏差的方法是通过考察一 群对象主要特征上的差别识别孤立点。 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 2 4 6 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋 势,并对其建模。虽然它可能包括时间相关数据的特征化、区分、关联、分类或聚 类,但是这类分析的不同特点包括了时间序列数据分析、序列或周期模式匹配和基 于类似性的数据分析。 2 5 数据挖掘的挖掘任务、方法及分类 2 5 1 数据挖掘发现的知识分类 数据挖掘中所发现的知识主要有一下几类n 1 : ( 1 ) 广义型知识:反映同类事物共同性质的知识。根据数据的微观特性发现其表征 的、带有普遍性的、较高层次概念的、中观和宏观的知识,反映同类事物共同性质, 是对数据的概括、精炼和抽象。 ( 2 ) 特征型知识:反映事物各方面的特征知识。 ( 3 ) 差异型知识:反映不同事物之间属性差别的知识。 ( 4 ) 关联型知识:反映事物之间依赖或关联的知识。如果两项或多项属性之间存在关 联,那么其中一项的属性值就可以依据其它属性值进行预测。 ( 5 ) 预测型知识:根据时间序列型数据,由历史的和当前的数据来推测未来的数据, 也可以认为是以时间为关键属性的关联知识。 ( 6 ) 偏离型知识:它是对差异和极端特例的描述,揭示事物偏离常规的异常现象, 如标准类外的特例,数据聚类外的离群值等。 所有这些知识都可以在不同的概念层次上被发现,随着概念树的提升,从微观 到宏观,以满足不同用户、不同层次决策的需要。例如,从一家超市的数据仓库中, 可以发现的一条典型关联规则可能是“买面包和黄油的顾客十有八九也买牛奶”, 也可能是“买食品的顾客几乎都用信用卡”,这种规则对于商家开发和实施客户化 的销售计划和策略是非常有用的。至于发现工具和方法,常用的有分类、聚类、减 维、模式识别、可视化、决策树、遗传算法、不确定性处理等。 1 4 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 2 5 2 数据挖掘的任务 数据挖掘的任务主要是关联分析、聚类分析、分类、预测、时序模式和偏差分 析等。数据挖掘的任务是从是从大量的、不完全的、有噪声的、模糊的、随机的数 据中发现和提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识。 所谓知识是指人类认识的成果或结晶,包括经验知识和理论知识。在传统的决策支 持系统中,知识库中的知识和规则是由专家或程序人员建立的,是由外部输入的。 数据挖掘的任务是发现大量数据中尚未被发现的知识,是从系统内部自动获取知识 的过程,对于决策者明确了解的信息,可以用查询、联机分析处理或其它工具直接 获取,而隐藏在大量数据中的关系、趋势,即使是管理这些数据的专家也是没有能 力发现的,这些信息对于决策可能又是至关重要的,就由数据挖掘来处理这类问题。 2 5 3 数据挖掘的分类 从不同的角度看,数据挖掘有多种分类方法,如根据所采用的技术分类n 训,根 据挖掘的任务分类,根据挖掘的数据类型分类等等。 2 5 3 1 根据数据挖掘技术分类 目前常用的数据挖掘技术包括如下: ( 1 ) 决策树方法 利用信息论中信息增益寻找数据库中具有最大信息量的字段,建立决策树的一 个结点,再根据字段的不同取值建立树的分支:在每个分支子集中重复建立树的下层 结点和分支的过程,即可建立决策树。国际上最有影响和最早的决策树算法是 q u i u l a n 研制的i d 3 方法,数据库越大它的效果越好。此后又发展了各种决策树方法, 如i b l e 方法使识别率提高了1 0 。 ( 2 ) 神经网络方法 神经网络模拟人脑神经元结构,以m p 模型和h e b b 学习规则为基础,用神经网络连接 的权值表示知识,其学习体现在神经网络权值的逐步计算上,但是它的缺点是“黑 箱 性,人们难以理解网络的学习和决策过程。目前主要有三大类神经网络模型: 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 前馈式网络:它以感知机、b p 反向传播模型、函数型网络为代表,可用于分类、 预测和模式识别等方面。 反馈式网络:它以h o p f i e l d 的离散模型和连续模型为代表,分别用于联想记忆和 优化计算。 自组织网络:它以基于r s 理论的关联规则挖掘的研究a r t 模型、k o h o l o n 模型为代 表,用于聚类。 ( 3 ) 覆盖正例排斥反例方法 覆盖正例排斥反例方法是利用覆盖所有正例、排斥所有反例的思想来寻找规 则。首先在正例集合中任选一个种子,到反例集合中逐个比较,与字段取值构成的 选择子相容则舍去,相反则保留,按此思想循环所有正例种子,将得到正例的规则( 选 择子的合取式) 。比较典型的算法有m i c h a l s k i 的a q i1 方法、洪家荣改进的a q l 5 方法 以及他的a e 5 方法。 ( 4 ) r s 方法 在数据库中,将行元素看成对象,列元素看成属性( 包含条件属性和决策属性) 。 等价关系r 定义为不同对象在某个( 或几个) 属性上取值相同,这些满足等价关系的对 象组成的集合称为该等价关系r 的等价类。条件属性上的等价类e 与决策属性上的等 价类y 之间有三种情况: 下近似:y 包含e : 上近似:y 和e 的交非空: 无关:y 和e 的交为空。 对下近似建立确定性规则,对上近似建立不确定性规则( 含可信度) ,而无关情 况则不存在规则。 ( 5 ) 概念树方法 对数据库中记录的属性字段按归类方式进行抽象,建立起来的层次结构称之为 概念树。利用概念树提升的方法可以大大浓缩数据库中的记录。对多个属性字段的 概念树进行提升,将得到高度概括的知识基表,然后可再将它转换成规则。 ( 6 ) 遗传算法 遗传算法是模拟生物进化过程的算法,由三个基本算子组成: 1 6 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 繁殖( 选择) :是从1 个旧种群( 父代) 选出生命力强的个体,产生新种群( 后代) 的 过程。 交叉( 重组) :选择2 个不同个体( 染色体) 的部分( 基因) 进行交换,形成新个体。 变异( 突变) :对某些个体的某些基因进行变异( 1 变0 ,0 变1 ) 。这种遗传算法可以 起到产生优良后代的作用。这些后代需满足适应度值,经过若干代的遗传,将得到 满足要求的后代( 问题的解) 。遗传算法己在优化计算和分类机器学习方面显示了明 显的优势。 ( 7 ) 公式发现 在工程和科学数据库( 由实验数据组成) 中,对若干数据项( 变量) 进行一定的数 学运算,求得相应的数学公式。比较典型的b h c o n 发现系统完成了对物理学中大量定 律的重新发现,其基本思想是:对数据项进行初等数学运算( 加、减、乘、除等) ,形 成组合数据项,若它的值为常数项,就得到了组合数据项等于常数的公式。 ( 8 ) 统计分析方法 在数据库字段项之间存在两种关系:函数关系( 能用函数公式表示的确定性关 系) 和相关关系( 不能用函数公式表示,但仍是相关确定关系) 。对它们的分析采用如 下方法:回归分析、相关分析、主成分分析。 ( 9 ) 模糊集方法 利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚 类分析。模糊性是客观存在的。系统的复杂性越高,精确化能力就越低,即模糊性 就越强。这是z a d e h 总结出的互克性原理。 ( 1 0 ) 可视化技术 可视化数据分析技术拓宽了传统的图表功能,使用户对数据的剖析更清楚。例 如,把数据库中的多维数据变成多种图形,这对揭示数据的状况、内在本质及规律 性起了很大作用。 2 5 3 2 根据挖掘的对象分类 有以下各种数据源:文本数据源据库、多媒体数据库、遗产数据库、 基于r s 理论的增量更新算法在数据挖掘中的研究与应用 i n t e r n e t ( w e b ) 、关系数据库、面向对象数、空间数据库、异质数据库等。 2 5 3 3 根据挖掘的任务分类 ( 1 ) 关联规则( a s s o c i a t i o n ) 关联规则用于发现大量数据中项集之间有意义的关联或相关联系,寻找给定数 据集中项之间的有趣联系。关联规则的支持度和置信度是两个规则兴趣度度量,它 们分别反映发现规则的有用性和确定性。 ( 2 ) 分类规则( c 1 a s s i f i c a t i o n ) 分类是最普通的数据挖掘任务之一,它是对已知训练数据的特征和分类结果, 为每一个类找到一个合理的描述或模型,然后再用这些分类的描述或模型来对未知 的新的数据进行分类。 ( 3 ) 聚类规则( c l u s t e r i n g ) 聚类算法是通过对变量的比较,把具有相似特征的数据归为一类。因此,通过 聚类以后,数据集就转化成类集,在类集中同一类中的数据具有相似的变量值,不 同类之间数据的变量值不就有相似性。区分不同的类是属于
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 恶心和呕吐症状的护理
- 数据分析与可视化 课件 第3章 Pandas数据分析
- 消防控制室监控专用课件
- 2025届十堰市茅箭区中考猜题数学试卷含解析
- 一般固废综合利用处置中心工程招商引资报告
- 云南省玉溪市通海县2025年中考试题猜想数学试卷含解析
- 乡村人居环境改造项目规划设计方案(范文参考)
- 思维导图在初中英语课堂中的应用研究
- 一年级数学下册六100以内的加法和减法二练习十三2课件苏教版
- 外科腹部常见疾病的CT简析
- 北京市海淀区2024-2025学年下学期初二期末考试道德与法治试题(含答案)
- 阳江市阳东区区内选调教师笔试真题2024
- 2025年滁州市来安县招聘社区专职工作者考试笔试试题(含答案)
- 2025年湖南省株洲市石峰区事业单位教师招聘考试《教育基础知识》真题(附答案)
- 注册安全工程师课件辅导
- 校级名师示范课活动方案
- 支气管肺炎的说课
- 设备技改异动管理制度
- 徐州市教师业务能力测试题库(数学)
- 全球与美国纯碱工业的近况及分析
- 大型造纸厂抄五车间操作规程
评论
0/150
提交评论