（计算机系统结构专业论文）基于投影的高维数据异常检测研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 数据挖掘是从大量的数据集中提取隐含的、未知的、潜在有用的知识的过程。 异常检测是数据挖掘中一个非常重要的分支，能发现隐含在数据集中的小模式， 这种小模式常常隐含着重要信息，在很多应用领域有重要的研究价值。如电信和 信用卡交易中的诈骗检测、天气预报中的灾害预报、网络访问中的入侵检测等。 在实际应用中经常会碰到高维数据，如交易数据、文档词频数据等，因此加 强对高维数据挖掘的研究有着非常重要的意义。但由于高维数据的特殊性，如随 着数据维数的升高，高维索引结构的性能迅速下降；由于高维数据的稀疏性，采 用l p 距离作为数据之间的相似性度量，在很多情况下这种相似性的概念已不复存 在等等，这些都给高维数据挖掘带来了极大的困难。 很多常规聚类算法虽然能进行异常检测，但仅仅将异常点作为聚类的副产品。 近几年，出现了一些专门的异常检测算法，在理论上和算法应用上有一定的突破， 但主要针对低维数值型数据集的研究。现实世界中，很多数据集具有内在高维特 性，使得这些算法检测性能急剧下降，而且算法对异常点的解释相对滞后。 本文针对目前主流的异常检测算法存在的问题，对异常检测技术进行了深入 研究，指出了这些算法在高维数据集应用上存在的缺陷，并基于投影思想和频繁 项集的概念，提出了一种新的异常检测算法o h d h m a p ，该算法不仅能较好地解 决高维数据集的稀疏性问题，也能将数据集的类型从数值型扩展到混合型，并且 能对异常点作出一定的解释，有利于区分异常点和噪声。实验表明，该算法具有 较好的检测性能。 本论文针对对异常挖掘的研究，对高维数据异常检测提供了新的思路，初步探 讨了异常的可解释性问题，具有一定的理论意义和应用价值。 关键词：数据挖掘，异常检测，投影，频繁项集 重庆丈学硕七学位论文英文摘要 a b s t r a c t d a t am i n i n gr e f e r st oap r o c e d u r ew h e r es o m ei m p l i c i t ，u n d i s c o v e r e da n du s e f u l k n o w l e d g ei s e x t r a c t e df r o ml a r g ea m o u n t so fd a t a o u t l i e rd e t e c t i o ni so n eo ft h e i m p o r t a n tb r a n c h e si nd a t am i n g , i tc a nd i s c o v e rt h es m a l ls c h e m a s ，m a y b es o m e i n t e r e s t i n g i n f o r m a t i o ni sh i d d e ni nt h e m i ti sw o r t ht o r e s e a r c h i n gi n m u c h a p p l i c a t i o n s ，s u c ha sf r a u dd e t e c t i o ni nc r e d i tc a r d ，d i s a s t e ra l a r mi nw e a t h e rf o r e c a s t a n di n t r u s i o nd e t e c t i o ni nn e t w o r ka c c g s sa n ds oo n i nf h c t ，w ec o n f r o n tm o s to fh j i g hd i m e n s i o n a ld a t a ，f o re x a m p l e ，e x c h a n g i n gd a t a i nb u s i n e s s ，i n d e x i n gd a t ai nd o c u m e n ta n ds oo n i naw o r d ，i ti sa l li m p o r t a n tr e s e a r c h f o rh i 。g hd i m e n s i o n a ld a t ai nd a t am i n i n g b u th i g hd i m e n s i o n a ld a t ah a ss o m es p e c i a l c h a r a c t e r s f o re x a m p l e ，w i mt h ei n c r e m e n to fd i m e n s i o n s ，t h ee f f i c i e n c yo fh i g h d i m e n s i o n a li n d e xb e c o m e sw o r s em o l ea n dm o r e , o nt h eo t h e rh a n d ，f o rt h ec u r s eo f t h es p a r s i t yi nh i 曲d i m e n s i o n ，t h es i m i l a rm c a s u l ei nt h ed a t ad o s en o te x i s tb ya i do f t h ep a r a m e t e ro fh d i s t a n c e a l lo ft h ec h a r a c t e r sb n n gt h ed i f f i c u l t yt od a t am i n gi n h i g hd i m e n s i o n a ld a t a m a n yc o n v e n t i o n a lc l u s t e r i n ga l g o r i t h m sc a l ld e t e c tt h eo u t l i e r , b u tt h eo u t l i e ri s f o u n da st h es i d e - p r o d u c t i nr e c e n ty e a r s ，af e ws p e c i a lo u t l i e ra l g o r i t h m sa r i s e ，b u t m o s to ft h ea l g o r i t h m sf o c u so nt h el o wd i m e n s i o n a ld a t a s o m ed a t as e th a v et h e c h a r a c t e ro fh i g hd i m e n s i o ni nt h ee s s e n c e , f o rw h i c ht h ea l g o r i t h m sh a v em a n yd e f e c t ， a n dt h ei n t e r p r e t a t i o nf o rt h eo u t l i e ro b v i o u s l yi sl a t e i nt h et h e s i s ，f o c u s e do nt h es h o r t c o m i n go ft h ec o n v e n t i o n a la l g o r i t h m s ，w e d e e p l yr e s e a r c ht h eo u t l i e rd e t e c t i o nt e c h n i q u e s ，a n di n d i c a t e t h ed e f e c to ft h e a p p l i c a t i o ni nh i g hd i m e n s i o n a ld a t a , a tl a s t ，w ep r e s e n tan e wo u t l i e rd e t e c t i o n a l g o r i t h mb a s e d o nt h ec o n c e p t i o no fp r o j e c t i o na n df r e q u e n ti t e m s t h ea l g o r i t h mc a n w e l ld e a lw i t ht h es p a r s i t yi nh i 曲d i m e n s i o n a ld a t a ，c a ne x p a n dt h ed i m e n s i o nf r o m n u m e r i ct om i x t u r e ，c a ng i v er e a s o n a b l ei n t e r p r e t a t i o nt ot h eo u t l i e r , w h i c hb e n e f i tt o d i s t i n g u i s ht h eo u t l i e rf o r mt h en o i s e s h o w na s t h ee x p e r i m e n t ，t h ea l g o r i t h mi s f e a s i b l e i nt h et h e s i s ，w ep r e s e n tan e v ra p p r o a c hi no u t l i e rd e t e c t i o nf o rh i g hd i m e n s i o n a l d a t a , r o u g h l ye x p l o r et h ep r o b l e mo fi n t e r p r e t a t i o no ft h eo u t l i e r , a l lo fw h i c ha r e i i 重庆大学硕七学付论文英文摘要 m e a n i n g f u li n t h eo u t l i e rd e t e c t i o nr e s e a r c ha n dh a v em a j o ra d v a n t a g ei nt h e a p p l i c a t i o n k e y w o r d s ：d a t am i n i n g , o u t l i e rd e t e c t i o n ，p r o j e c t i o n , f r e q u e n ti t e m i l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庞太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名俄 坐易签字嗍砷年彳肿日 学位论文版权使用授权书 本学位论文作者完全了解重废太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重废太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( v ) 。 ( 请只在上述一个括号内打“”) 学位敝作者签名试t 甚易 答字醐：1 钳即钼 导师签名： 签字日期：研年衫月 丌u 一 9矿矿q 重庆大学硕十学位论文l 绪论 1 绪论 1 1 选题的意义 人类的各项认知活动都是基于对外部信息的观察和了解，从而做出正确的判 断、决策和行动，而数据仅仅是人们用各种工具和手段观察外部世界信息的载体。 因此，从数据到知识，需要经过分析加工处理精炼的过程( 如图1 1 ) 。 图1 1 客观世界信息流转图 f i g1 1t h ei n f o r m a t i o np r o c e e d i n g so f a c t u a lw o r l d 在过去的几十年中，随着社会的飞速发展，各行各业的信息总量呈指数级数 增长，理解他们已经远远超出了人的能力。结果，收集在大型数据库中的数据变 成了“数据坟墓”，人们迫切需求强有力的数据分析工具，从海量数据中寻求有价值 的信息，将“数据坟墓”转换成“知识金块”。 伴随着数据仓库出现的o l a p u ( o n l i n e a n a l y t t c a l p r o c e s s m g ) 联机分析处理技术， 具有总结、概化和聚集的功能，可以从不同角度来观察数据，支持多维分析和决 策支持，为更深入地对数据进行分析提供了条件。但o l a p 分析过程需要用户具 有较强的领域知识，由用户指导信息分析与知识的发现的全过程。人们迫切需要 有基于计算机与信息技术的智能化自动工具，来帮助挖掘隐藏在数据中的各类知 识，这类工具不应再基于用户假设，而应能自身生成多种假设。 多年来，数理统计技术方法以及人工智能和知识工程等领域的研究成果，诸 如机器学习、模糊理论、神经网络、进化计算、模式识别、粗糙集理论等等诸多 研究分支，给这种数据分析需求提供了坚实而丰富的理论和技术基础。 在数据挖掘技术的发展前期，多数研究人员关注的是低维数据集常规模式的 研究，如关联规则、特征描述、聚类和分类等，而较少关注数据集的小模式发现。 小模式发现，又称为异常检测，是数据挖掘领域中一个非常重要的分支，它能发 现数据集中明显与其它数据不同且数量相对较少的对象，而这些对象隐含着重要 的信息。随着异常检测在许多领域的广泛应用，如客户分类、信用卡欺诈甄别、 重庆大学硕士学付论文1 绪论 网络入侵检测、电子商务中犯罪活动的发现、视频监视、药物研究及天气预报等 等。近几年来，越来越多的科学工作者将目光投向了异常检测的理论基础、算法【2 - 5 】 和应用【6 7 】的研究，并取得了较多的研究成果。 但是，这些针对低维数据集提出的异常检测算法，在实际应用中，效果很不 理想，算法效率很低，无法广泛运用和推广。研究人员发现，现实世界中所面临 的数据大部分都是高维的，正是高维数据具有不同于低维数据的特殊性质，导致 很多常规检测算法的失效。因此，加强对高维数据特性的研究，寻找更适合高维 数据的异常检测算法，是一个具有现实意义的课题。 1 2 研究现状 数据挖掘涉及多学科技术的集成，包括数掘库技术、统计学、机器学习、高 性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理和空 间数据分析。通过数据挖掘，可以从数据库提取有趣的知识，发现的知识可以用 于决策、过程控制、信息管理、查询处理等等，因此，数据挖掘是信息产业最有 前途的交叉学科，是目前国际上数据库和信息决策领域的最前沿研究方向之一， 引起了学术界和工业界的广泛关注。 随着对数据挖掘技术研究的不断深入，相应的数据挖掘研究重点也在不断的 扩展，当前，数据挖掘研究的重点主要有以下几个方面。 1 2 1 挖掘方法与用户交互问题 这其中涉及所挖掘知识的类型、领域知识的利用、定制挖掘和知识挖掘的可 视化。 从数据库中挖掘不同类型的知识。由于不同的应用需要不同类型的知识， 因此数据挖掘应该涵盖广泛的数据分析与知识发现任务需求。这其中包括：数据 概念描述、对比概念描述、关联知识、分类知识、聚类分析、趋势和偏差分析， 以及相似性分析。这些挖掘任务可以是对同一个数据库进行不同的操作。因此需 要设计开发大量的数据挖掘技术。 基于多层抽象水平的交互挖掘。由于无法准确了解从一个数据库中究竟能 够发现什么，因此一个数据挖掘过程应该是交互的，对于数据库中包含的数据， 首先需要利用合适的采样技术来帮助实现交互式数据挖掘的探索。交互数掘挖掘 能够让用户参与并指导对要挖掘模式的搜索，或通过用户的帮助精炼所返回的挖 掘结果。与数据仓库o l a p 交互模式类似，用户也可以与数据挖掘系统进行交互 来帮助进行更有效的数据挖掘，以便能从多个不同角度发现多个抽象层次。 数据挖掘结果表达与可视化。数据挖掘应该能够用更完整的标准语言、可 视化表示方式来描述所挖掘出的知识，以使用户更加容易地理解和应用所挖掘出 2 重庆人学硕十学位论文 1 绪论 的知识。数据挖掘结果的可视化表示，对于交互式数据挖掘系统而占是非常重要 的，同时也要求系统采用多种表示形式，如：树、表格、规则、图、示意图、矩 阵、曲线来描述所挖掘的结果。 1 2 2 性能问题 性能问题，主要包括效率、可扩展性和数据挖掘算法的并行化等问题。 数据挖掘算法的效率与可扩展性。为了能够有效地从大规模数据集中抽取 模式知识，数据挖掘算法必须是高效的和可扩展的。算法的可扩展性表现在挖掘 系统可利用的其它资源不变的情况下( 如：内存和硬盘空间等) ，数据挖掘的运行时 间与所处理的数据规模呈线性关系，这也就意味着当被挖掘数据的规模确定后， 相应数据挖掘算法的运行时间是可以预测的，并且也是可以接受的。从数据库角 度来要求知识发现算法、效率和可扩展性也是构造数据挖掘系统的一个关键问题。 并行、分布和增量更新算法。许多数据库中数据的规模巨大、广泛分布的 数据地点、以及挖掘算法的计算复杂性等，都极大地推动了并行分布数据挖掘算 法的研究与开发。这类算法将数据分为若干份进行并行处理，然后将处理结果合 并在一起。此外，一些数据挖掘过程所涉及的高昂代价也促使了增量数据挖掘算 法的发展，这类增量挖掘算法无需每次挖掘时都要对整个数据库进行挖掘，而只 需对数据库中增量数据进行挖掘即可，当然增量挖掘算法需要对之前所挖掘获得 的模式知识进行增量式修改与完善。 1 2 3 数据库类型多样化所涉及的问题 关系和复杂类型数据的处理。数掘库与数据仓库的类型有许多种，期望一 个数据挖掘系统能够对所有类型的数据都能够很好地完成挖掘任务是不现实的。 鉴于关系数据库与数据仓库应用较广，研究设计高效地挖掘系统是必需的。然而 其它数据库包含复杂数据对象，如超文本、多媒体数据、时间数据或交易数据等， 显然一个数据挖掘系统不可能满足挖掘不同数据类型并完成不同挖掘任务的要 求。因此需要根据特定的挖掘数据，构造相应的数据挖掘系统。 异构数据库和全球信息系统的信息挖掘。本地和广域计算机网络系统将许 多数据源连接在一起，从而构成了一个巨大的、分布的、异构的数据库。如何从 来自具有不同数据语义的不同数据源( 包括结构化、半结构化和无结构数据) ，挖 掘出需要的模式知识是数据挖掘研究面临巨大的挑战。数据挖掘或许能够帮助从 多个异构数据库中挖掘高层次的数据规律，而这些数据规律是无法通过简单查询 系统就可获取的。由此甚至还可以帮助改善信息交换和异构数据库之间的互操作 性。 国际上一些工业研究实验室，例如i b m a l m a d e n 和g t e ，众多的学术单位， 例如u cb e r k e l e y ，都在这个领域开展了各种各样的研究计划。研究的主要目标是 3 重庆大学硕七学位论文1 绪论 发展有关的理论、方法和工具，以支持从大量数据中提取有用的和让人感兴趣的 知识和模式。算法方面主要有，对知识发现方法的进一步发展；k d d 与数据库的 紧密结合。在应用方面包括，k d d 商业软件工具不断产生和完善，注重建立解决 问题的整体系统，而不是孤立的过程。国外很多计算机公司非常重视数掘挖掘的 开发应用，i b m 和微软都成立了相应的研究中心进行这方面的工作。 与国外相比，国内开展数据挖掘研究起步比较晚，研究人员主要集中在高校， 也有部分在研究所。所涉及的研究领域很多，但一般集中于数据挖掘算法改进的 研究、实际应用的尝试以及有关数据挖掘理论方面的拓展。如清华大学、中科院 计算技术研究所、空军第三研究所、海军装备论证中心、北京系统工程研究所对 模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立 方体代数的研究；华中理工大学、复旦大学、浙江大学、中国科技大学、中科院 数学研究所、吉林大学、重庆大学等单位重点开展了对关联规则挖掘算法的优化 和改造，南京大学、四川i 联合大学和上海交通大学等单位更关注非结构化数据的 知识发现以及w e b 数据挖掘的研究。目前进行的大多数研究项目是由政府资助进 行的，如国家自然科学基金、8 6 3 计划等，目前还没有相关的具体数据挖掘产品的 报道。 1 3 论文的组织结构 本文主要针对数据挖掘的异常检测问题，讨论了异常定义的理论基础，介绍 了当前数据挖掘技术的主流异常点检测算法，详细分析了高维数据的特性，指出 了常规检测算法在高维数据集应用上存在的缺点，针对高维数据特性，本文给出 了一种新的异常检测算法，并进行了详细研究分析，用合成数据集和k d d 9 9 数据 集对算法进行了验证。 第一章，指出了课题的研究背景及其重要的研究意义，从数据挖掘的理论研 究和应用研究方面，对当前数据挖掘的国内与国外的研究动态进行分析，并对当 前数据挖掘研究重点问题作了详细介绍，给出了本论文的总体框架结构。 第二章，对数据挖掘技术进行了全面的介绍，通过对数据挖掘产生背景的分 析，指出了数据挖掘的必要性，详细介绍了数据挖掘定义组成和研究对象，分析 了数据挖掘的组成、技术方法以及未来研究的方向， 第三章，回顾了异常检测研究过程及当前研究动态，介绍了基于距离、基于 密度、基于偏离以及面向高维的异常检测算法，具体分析了各类算法的主要思想， 并比较了各类算法的优劣及其适用范围。 第四章，主要针对高维异常检测中存在的问题，给出了一种基于投影的改进 算法。首先对数据集在各属性维上的投影值分别进行初始分类优化，结合频繁项 4 重庆人学硕七学位论文1 绪论 集的概念，依次对各属性维投影聚类结果计算笛卡尔交集，在计算笛卡尔交集的 过程忠，根据事先设定的剪枝策略对结果集进行剪枝，剪掉包含数据点数低于阈 值的候选集，直到所有维组合完毕，最终得到在整个维空间聚类结果；依掘全维 聚类结果，对检测出的点区分噪声和异常点，并对异常点作出解释。 第五章，对第四章中提出的算法进行分析和验证，根据实验结果对算法作出 评价，指出算法存在的主要问题，并对算法进行改进，最后用实验进行了实证。 第六章，对全文工作进行了总结，指出了本算法研究中存在的问题和今后研 究工作的展望。 重庆大学硕士学位论文2 数据挖掘概述 2 数据挖掘概述 2 1 数据挖掘的定义、组成及研究对象 2 1 1 数据挖掘的定义 “挖掘”一词最早出现于统计学中。从统计学的角度，数据挖掘是指分析所观察 的数据集，以发现可信的数据间的未知关系并提供给数据拥有者可理解的、新颖 的和有用的归纳数据 8 】。从数据库的观点来看，数据挖掘是指从存储在数据库、数 据仓库或其它信息仓库中的大量数据中发现有趣的知识的过程 9 】。从机器学习的角 度，数据挖掘定义为从数据中抽取隐含的、明显未知的和潜在有用的信息【l “。目 前，人们比较倾向认为数掘挖掘，也叫数据库中的发现知识( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ， k d d ) ，就是从大量的、不完全的、有噪声的、模糊的、随机的实际 应用数据中，提取隐含在其中的、人们事先不知道的、但又潜在有用的信息和知 识的过程l l “。 从数据库中发现知识( k d d ) 一词首先出现在1 9 8 9 年举行的第十一届国际 联合人工智能学术会议上。从1 9 8 9 年到1 9 9 4 年举行了四次k d d 的国际研讨 会。随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委会于1 9 9 5 年把 专题讨论会更名为国际会议，在加拿大蒙特利尔市召开了第一届k d d 国际学术会 议，以后每年召开一次。规模由原来的专题讨论会发展到国际学术大会。1 9 9 8 年 建立了新的学术组织a c m s i g m o d ，即a c m 下的数据库中的知识发现专业组 ( s p e c i a l i n t e r e s t e d g r o u p o i lk n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 。1 9 9 9 年 a c m s i g m o d 组织了第五届知识发现与数据挖掘国际学术会议( k d d 9 9 ) ，专题杂 志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 自1 9 9 7 年起由k l u w e r s 出版社出版。此 外，还有一些国际和地区性数据挖掘会议，如“知识发现与数据挖掘太平洋亚洲会 议”f p a k d d ) ， a c m s i g m o d 数据管理国际会议”( s i g m o d ) ，“超大型数据库国 际会议”f v l d b ) ， a c m s i g m o d s i g a r t 数据库原理研讨会”( p o d s ) ，“数据库 系统高级应用国际会议”( d a s f a a ) ，“人工智能国际联合会议”( i j c a i ) ，“美国人工 智能学会会议”( a a a i ) 等等。 2 1 2 数据挖掘的组成 许多人把数据挖掘视为另一个常用的术语数据中的知识发现或k d d 的同义 词。而另一些人只是把数据挖掘视为数据库中知识发现过程的一个基本步骤。 6 重庆大学硕士学位论文2 数据挖掘概述 知识发现由以下步骤组成：数据清理、数据集成、数据选择、数据变换、数 据挖掘、模式评估和知识表示，也可粗略地理解为三部曲：数据准备、数据挖掘 以及结果的解释评价。 图2 1 知识发现的步骤 f i g2 1t h es t e po f k n o w l e d g ed i s c o v e r i n g 数据准备 数据准备又可分为三个子步骤：数据选取、数据预处理和数据变换。数据选 取的目的是确定挖掘任务的操作对象，即目标数据，它是根据用户需要从原始数 据库中抽取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消 除重复记录、完成数据类型变换等操作。 数据挖掘阶段 数据挖掘阶段首先要确定挖掘的任务或目的，如数据描述、分类、聚类、关 联规则或序列模式等。确定了挖掘任务后，就要决定使用什么样的挖掘算法。相 同的任务可以用不同的算法来实现。 结果解释和评价 数掘挖掘阶段发现的模式，经过用户或者机器的评价，可能存在冗余或无关 的模式，这时需要将其剔除；也可能模式不满足用户要求，这时就需要整个过程 退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、设定新的数据 挖掘参数值，甚至换一种挖掘算法。 2 1 3 数据挖掘的研究对象 数据挖掘中要分析的数据范围非常广泛，从自然科学、社会科学、商业数据 到科学处理产生的数据或卫星观测数据；它们的数据表示形式也是各种各样，有 7 重庆大学硕十学位论文2 数据挖掘概述 关系型，也有层次型，网状型的。由于关系数据库应用广泛，具有规整统一的组 织结构、规范通用的查询语吉，特别是关系之间及属性之间具有平等性的优点， 因此，目前k d d 主要面向的是以结构化数据为主的关系数据库、事务数据库和 数据仓库。 随着数据处理工具、先进数据库技术以及w w w 技术的迅速发展，大量形式 各异的复杂数据类型不断涌现，包括时间序列数据、文本数据、空间数据和w e b 数据等。下面简单介绍一下这些数据挖掘的对象。 数据库，从关系数据库中进行数掘挖掘是当前研究的主流方向。目前研究 的主要问题是：海量数据、动态变化数据、噪声平滑、数据不完整及冗余信息的 处理、数据稀疏处理等。 时间序列，是指随着时间顺序取得的一系列观察值。时间序列是一种十 分常见的数据形式，在工业、气象、医学、金融、交通等领域广泛存在。目前， 对时间序列数据挖掘已经成为一个热点问题。 文本数据，是指存在着大量以文本或文档形式存储着的信息，如书籍、 技术论文、电子邮件、w e b 页面等。文本分析过程就是通过分析文本，从中找出 一些特征值。文本挖掘超过了基于关键字和基于相似度的信息检索范畴，而是利 用基于关键字的关联和文档分类等方法从半结构化的文本数据中发现知识。 空间数据，是指具有空间特征的数据，如地图、遥感数据、医学图像数据 等。空间数据挖掘是指对空间数据库中非显式存在的知识、空间关系或其他有意 义的模式等的提取，主要有：空间数据特征比较、空间聚类分析、空间分类、空 间关联、空间模式分析、空i 日j 趋势与空间异常分析等，基于地理信息系统的空问 数据挖掘近年来获得了广泛的关注。 w 曲数据，随着i n t e r n e t 技术的发展，网络包含的数据越来越丰富，所含的 信息随着网络不断发展而呈指数增长。w e b 信息挖掘技术是根据面向i r l t e r n e t 的分 布式信息资源的特点的一种模式抽取过程，它不仅能查找到分布式信息资源中己 存在的信息，还能识别出大量存在于数据中的隐含的、有效的规律。结合近年来 飞速发展的w e b 搜索技术，w e b 挖掘也将是今后一段时期内的研究热点。w e b 挖 掘的问题主要包括：对内容的挖掘、对w e b 链接结构的挖掘和对w e b 访问模式的 挖掘。 2 2 数据挖掘的主要模式 数据是指一个有关事实f 的集合，它是用来描述事物有关方面的信息，如： 学生档案数据库中有关学生基本情况的各条记录，一般说来这些数据应该是准确 无误的；模式是一个用语言l 来表示的一个表达式e ，它可以用来描述数据集f 重庆大学硕七学位论文2 数据挖掘概述 中数据的特性，e 所描述的数据是集合f 的一个子集f e ，e 作为一个模式比列 举数据子集f e 中所有元素的描述方法简单，例如：如果成绩在8 1 9 0 之间，则表 示成绩优良这种描述可称为一个模式而如果成绩为8 l 、8 2 、8 3 、8 4 、8 5 、8 6 、 8 7 、8 8 、8 9 或9 0 则成绩优良就不能称之为是一个模式。 数据挖掘是知识发现过程中最核心最重要的部分，数据挖掘的实质就是从数 据中发现未知的关系和模式而发现的关系和模式就是我们的目标知识。 2 2 1 模式的分类 概念类描述：特征化和区分 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类和 概念可能是有用的。这种类或概念的描述称为类概念描述( c l a s s c o n c e p t d e s c r i p t i o n ) 。这种描述可以通过下述方法得到：1 ) 数据特征化，一般地汇总所研 究类( 通常称为目杯类( t a r g e t c l a s s ) ) 的数据；2 ) 数据区分，将目标类与一个或 多个比较类( 通常称为对比类( c o n t r a s t i n gc l a s s ) ) 进行比较。 数据特征化( d a t ac h a r a c t e r i z a t i o n ) 是目标类数据的一般特征或特性的汇总。 通常，用户指定类的数据通过数据库查询收集。例如，为研究上一年销售增加1 0 的软件产品的特征，可以通过执行一个s q l 查询收集关于这些产品的数据。有许 多有效的方法将数据特征化和汇总。例如，基于数据立方体的o l a p 上卷操作可 以执行用户控制的、沿着指定维的数据汇总，一种面向属性的归约技术可以用来 进行数据的概化和特征化，而不必一步步地与用户交互。数据特征的输出可以用 多种形式提供，包括饼图、条图、曲线、多维数据立方体和包括交叉表在内的多 维表。 数据区分( d a t ad i s c r i m i n a t i o n ) 是将目标类对象的一般特征与一个或多个对比 类对象的一般特性比较。目标类和对比类由用户指定，而对应的数据通过数据库 查询检索。例如，你可能希望将上一年销售增加1 0 的软件产品与同一时期销售 至少下降3 0 的那些产品进行比较。用于数据区分的方法与用于数据特征化的类 似，数据区分的输出形式类似于特征描述，但区分描述应当包括比较度量，帮助 区分目标类和对比类。 关联分析 关联规则挖掘( a s s o c i a t i o n a n a l y m s ) 给出了数掘集中项之间的有趣的联系，是 k d d 研究中的一个重要分支。自从a g r a w a l 等人t 1 2 j 在s i g m o d 9 3 第一次提出 这个概念以来，关联规则一直是众多学者的研究热点。关联规则挖掘的目的是在 交易数据库中发现各项之间的关联关系。从大量商务事务记录中发现有趣的关联 关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析。关联 规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不 9 重庆大学硕士学位论文2 数据挖掘概述 同商品之间的联系，分析顾客的购买习惯，帮助零售商制定营销策略。 更形式地，关联规则是形如x j y ，即“a 1 八八a m ，j “b l 八八b 。”的规则， 其中，a 。( i 1 ，m ) ，b j ( j l ，n ) 是属性值对。关联规则x y 解 释为“满足x 中条件的数据库元组也多半满足y 中条件”。 a 叫o r i 算澍”】是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的 名字基于这样的事实：算法使用频繁项集性质的先验知识，利用一种称作逐层搜 索的迭代方法，k - 项集用于探索( k + 1 ) 项集。首先，找出频繁1 ，项集的集合，该 集合记做l l ，l ，用于找频繁一2 项集的集合l 2 ，而l 2 用于找l 3 ，如此下去，直到 不能找到频繁k 项集。 分类分析 数据分类是一个两步过程。第一步，建立一个模型，描述预定的数据类集或 概念集。通过分析由属性描述的数据库元组来构造模型，假定每个元组属于一个 预定义的类，由一个称作类标号属性的属性确定，为建立模型而被分析的数据元 组形成数掘训练集。由于提供了每个训练样本的类标号，该步也称作有指导的学 习。第二步，使用模型进行分类。在使用该模型之前，需要使用测试集对模型的 预测准确率进行评估。 分类模型应用的实例很多。例如，我们可以将银行网点分为好、一般和较差3 种类型，并以此分析这3 种类型银行网点的各种属性，特别是位置、盈利情况等 属性，找出决定它们分类的关键属性及相互间关系，此后就可以根据这些关键属 性对每一个预期的银行网点进行分析，以便决定预期银行网点属于哪一种类型。 许多分类和预测方法可以根据如下标准进行比较和评估：预测的准确率，这 涉及模型正确地预测新的或先前未见过的数据的类标号的能力；速度，这涉及产 生和使用模型的计算花费；强壮性，这涉及给定噪声数据或具有空缺值的数据， 模型正确预测的能力；可伸缩性，这涉及给定大量数据，有效地构造模型的能力。 很多方法已被机器学习、专家系统、统计学和神经生物学方面的研究者提出，但 现在大部分算法是内存驻留算法，通常假定数据量很小。最近的数据库挖掘研究 算法建立在大数据集上，开发了可伸缩的分类和预测技术，能够处理大量的、驻 留硬盘的数据。这些技术通常考虑并行和分布式处理。 完成分类任务的方法有决策树、统计学方法【1 4 1 、机器学习【”1 、神经网络方法 【16 】等等，其中决策树方法由于具有速度快、精度高、生成模式简单等优点备受关 注，比较典型的决策树算法有1 1 9 3 和c 4 5 。 聚类分析 聚类是将物理或抽象对象的集合分组，组成多个簇的过程，使得在同一个簇 中的对象之间具有较高的相似度，而不同簇中的对象差别很大，距离是经常采用 o 重庆大学硕士学位论文2 数据挖掘概述 的度量方式。在很多应用中，可以将一个簇中的数据对象作为一个整体来对待。 聚类和分类分析方法不同，它是一种无指导的学习过程。 聚类分析已经广泛地存在于许多应用中，包括模式识别、数据分布，图像处 理，以及市场研究。在商务上，聚类能帮助市场分析人员从客户基本库中发现不 同的客户群，并且用购买模式来刻画不同的客户群的特征；在生物学上，聚类能 用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。 作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情 况，观察每个簇的特点，集中对特定的某些簇做进一步地分析。聚类分析已经成 为数据挖掘研究领域中一个非常活跃的研究课题。 目前，在文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类 的目的和应用，大体上，主要的聚类算法可以划分为如下几类： 1 ) 基于划分的方法( p a t i t i o n i n gm e t h o d ) ：给定一个1 1 个对象或元组的数据库， 一个划分方法构建数据的k 个划分，每个划分表示一个聚簇，并且k 鱼，也就是所， 它将数据划分为k 个组，同时满足如下要求：( i ) 每个组至少包含一个对象：( i i ) 每个对象必须属于且只属于一个组。在一些模糊划分技术中第二个要求可以放宽。 具有代表性的算法有如k - m e a n s 、p a m ，c l a r a 、c l a r a n s 等。 2 ) 基于层次的方法( h i e r a r c h i c a lm e t h o d ) ：层次的方法对给定数据对象集合 进行层次的分解。根据层次的分解形成方式不同，可以进一步划分为凝聚的和分 裂的。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个 组，然后相继地合并相近的对象或组，直到所有的组合成一个或者达到一个终止 条件；分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中， 在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个 簇中，或者达到一个终止条件。典型代表算法有a g n e s 、b i r c h 、c u r e 、r o c k 、 c h a m e l e o n 等 3 ) 基于密度的方法( d e n s i t y - b a s e dm e t h o d ) 绝大多数划分方法基于对象之间 的距离进行聚类，这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到 了困难，随之提出了基于密度的另一类聚类方法，其主要思想是：只要临近区域 的密度( 对象或数据点的数目) 超过某个阈值，就继续聚类。也就是说，对给定 类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点，这样 方法可以用来发现任意形状的簇。典型算法有d b s c a n 、o p t i c s 、d e n c l u e 等。 4 ) 基于网格的方法( g r i d b a s e dm e t h o d ) ：基于网格的方法把对象空间量化为 有限数目的单元，形成了一个网格结构，所有的聚类操作都在这个网格结构( 即 量化空间) 上进行，这种方法的主要优点是它的处理速度快，其处理时间独立于 数据对象的数目，只与量化空间中每一维的单元数目有关。典型算法有s t i n g 、 重庆大学硕士学位论文2 数据挖掘概述 w a v e c i u s t e r 等。其中，s t i n g 是基于网格方法的一个典型例子。c l i q u e 和 w a v e c l u s t e r 这两种算法既是基于网格的，又是基于密度的。 时序分析 时问序列模式根据数掘随时间变化的趋势预测将来的值，这里时间具有广义 坐标的含义，既可以指按时间的先后顺序排列的数据，也可以指按空间的前后顺 序排列的随机数据。它与关联模式相仿，其目的也是为了挖掘数据之问的联系， 但是时序模式分析的侧重点在于分析数据之间的前因后果。为了发现序列模式， 不仅需要知道事件是否发生，而且需要确定事件发生的时间。时序模式主要用于 分析数据仓库中的某类同时i 日j 相关的数据，并发现某一时间段内数掘的相关处理 模型。 从经济到工程技术，从天文到地理气象，几乎在各种领域都会遇到时间序列， 例如，某地区的逐月降雨量，其实际记录结果，按月份先后排列，便是一个时间 序列；证券公司股票交易信息；人造卫星观测的气象信息和科学仪器所检测到的 大量生物、地矿等信息；心电图和脑电图就包含着关于人类健康状况的丰富信息。 商品销售中，客户现在定购一台激光打印机，以后还可能定购打印纸，可能在初 始购买时有大量定货，在售后服务请求时定货量较小，在服务请求完成后可能又 有大量的定货，销售商就可以针对上述情况指定相应的促销或营销方法。 因此， 对时间序列进行分析具有很重要的价值。 时间序列相似性查找成为目前数据挖掘领域的一个新的研究课题，时间序列 的相似性搜索并不是个容易的问题其主要困难在于相似性度量的定义和算法的 时间复杂度而这两者都依赖于时间序列的表示方法，时间序列表示方法的不同会 严重地影响其距离度量、对各种变形扭曲的敏感程度，并决定相似性搜索的有效 性。因此，人们都在寻找鲁棒性强，能有效地应用于时间序列模式匹配的时间序 列表示方法 2 2 2 模式的评价 尽管任务相关的数据和要挖掘的知识类型的说明可以大幅度减少产生规则的 数量，数据挖掘过程仍然可能产生大量模式。通常，这些模式中只有一小部分是 特定用户感兴趣的。这样，用户需要进一步限制挖掘过程产生的不感兴趣的模式 数量，这可以通过设定兴趣度度量来实现。兴趣度度量评估模式的简洁性、确定 性、实用性和新颖性。 简洁性( s i m p l i c i t y ) ：模式兴趣度的一个重要因素是对于人的理解，数据挖 掘的目标就是将数据库中隐含的模式以容易被人理解的形式表现出来，从而帮助 人们更好地了解数据库中所包含的信息，当然一个模式是否容易被人理解这本身 就很难衡量，比较常用的方法是对其简洁程度进行衡量。简洁性的客观度量可以 重庆大学硕十学位论文2 数据挖掘概述 看作模式结构的函数，用模式的二进位位数、属性数或模式中出现的操作符数来 定义。例如，一个规则的结构约复杂，它就越难解释，从而就可能对它没有多少 兴趣。 确定性( c e r t a i n t y ) ：每个发现的模式都应当由一个表示其有效性或“值得信 赖性”的确定性度量。对于形如a j b ”的关联规则，其确定性度量是置信度，其中 a 和b 是项目的集合。给定一个任务相关的数据元组集合，“a j b ”的置信度定义 为： 置信度c aj b ，= 皇雹害罢晶豁 对于分类规则，该置信度定义也可以方便地称作可靠性或准确性地确定性度 量。低可靠性表明不正确的分类，对比类的许多对象也在目标类中，因此，规则 的可靠性也称为规则的