（计算机应用技术专业论文）隐私保护分类数据挖掘研究.pdf

内蒙古科技大学硕士学位论文 论文题目：堕塑堡茎坌誊攀搀# 零研窖 圳f | f 洲i | f i 川洲f | 0 y 1 7 8 9 5 7 6 。 作者： 汤彪 指导教师：堕堕燮墼望：单位：塑鍪重型垫奎堂 协助指导教师： 论文提交日期：2 0 1 0 年0 6 月1 2 日 学位授予单位：内蒙古科技大学 单位： 单位： 隐私保护分类数据挖掘研究 r e s e a r c ho n p r i v a c yp r e s e r v i n gc l a s s i f i c a t i o n data m i n i n g 研究生姓名：汤彪 指导教师姓名：张晓琳 内蒙古科技大学信息工程学院 包头0 1 4 0 1 0 ，中国 s c h o o lo fi n f o r m a t i o ne n g i n e e r i n g 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并 表示了谢意。 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留、使用学位论文的规定， u r j 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 l ( 保密的论文在解密后应遵循此规定) ：签名：雄导师签名：鍪拯吼 - 【 内蒙古科技大学硕士学位论文 摘要 近几年来，随着数据库技术和网络技术的发展，许多领域都积累了大量的数 据。巨增的数据背后蕴藏着丰富的知识，如何从这些数据中提取出对决策有价值 的知识，成为人们关注的焦点。数据挖掘作为一个强有力的数据分析工具，可以 发现数据中潜在的模式和规律，在许多领域做出了巨大的贡献，具有广泛的应用 前景。数据挖掘技术带来巨大利益的同时，由于被挖掘的资料或数据包含着许多 个人的隐私信息，例如：病人的病情信息、顾客的喜好、个人背景资料等，这些 信息一旦被泄露会给个人带来很大危害。如果把这些数据库的真实数据直接交给 挖掘者，难免会产生隐私信息泄露。随着数据挖掘技术应用领域不断深入，隐私 泄露问题越来越严重，引起业界和社会各方面的广泛关注。因此，如何在隐私保 护条件下进行数据挖掘成了数据挖掘领域的研究热点之一，隐私保护数据挖掘 ( p p d m ) 也随之产生。 分类数据挖掘是数据挖掘的主要类型，决策树是分类挖掘最常用的分类器，所 以采用决策树分类的隐私保护分类数据挖掘方法已经成为近年来数据挖掘领域的研 究热点。目前，隐私保护分类数据挖掘采用修改数据的方法很多，随机扰动技术是 比较常用的一种，它可以不改变原数据本质特征。但现有的隐私保护分类数据挖掘 方法有很多缺陷，如：适用的数据类型有限、随机扰动后会产生隐私破坏、重建原 数据分布的错误率较高、隐私保护度低或挖掘精度低等。针对这些缺陷，提出一种 隐私保护分类数据挖掘的方法，该方法利用随机扰动矩阵对数据进行转变，通过由 单属性随机扰动矩阵生成的多属性联合随机扰动矩阵和转变后的数据集来重建原数 据分布。为使其适应于多种数据类型，对原始数据集的每个属性的不同值编码；给 每个属性都选择一个随机扰动矩阵，增加了隐私保护度，而且在选择随机扰动矩阵 时，引入r - a m p l i f y i n g 方法防止数据转换后隐私破坏：引入矩阵条件数，降低了重建 原数据分布的错误率，提高了挖掘的精度。 关键词：数据挖掘；隐私保护；判定树；随机扰动矩阵 内蒙古科技大学硕士学位论文 a b s t r a c t r e c e n t l y , w i t ht h ed e v e l o p m e n to ft e c h n o l o g yo ft h ed a t a b a s ea n dn e t w o r k , l a r g e a m o u n to fd a t ah a sb e e na c c u m u l a t e d , i th a sb e a 黜t h ef o c u so fp e o p l e sa t t e n t i o nt h a th o w t oe x t r a c tv a l u a b l ek n o w l e d g et om a k ed e c i s i o n s d a t am i n i n gw h i c hi sa p o w e r f u lt o o l 啪 f i n dp o t e 砌m o d e la n dl a w i th a sm a d eg r e a tc o n t r i b u t i o ni nm a n ya r e a sa n dh a sa b r i g h t f u t u r e d a t am i n i n gm a k eg r e a tb e n e f i t s , m e a n w h i l e , o n c ep r i v a t ei n f o r m a t i o n d i s c l o s e dc a l l b r i n gg r e a th a r mt op e o p l e , b e c a u s et h ed a t af o rd a t am i n i n gc o n t a i nan u m b e ro fp e r s o n a l p r i v a c yi n f o r m a t i o ns u c ha st h ep a t i e n t si n f o r m a t i o na b o u td m a s e , c u s t o m e r sf a v o r i t e , p e r s o n a lb a c k g r o u n da n d s oo n i ft h ei n f o r m a t i o ni sg i v e nt od a t am i n e r s , i t si n e v i t a b l et o d i s c l o s ep r i v a c yi n f o r m a t i o n w i t ht h ef i e l do fd a t am i n i n gb eu s e dd e e p l y , i t saf o c u st h a t p r i v a c yi n f o r m a t i o ni sd i s c l o s e dm o r ea n dm o r es e r i o u s l y f o rt h e s er e a s o n s ，h o wt o i m p l e m e n tad a t am i n i n gu n d e rp r i v a c yp r o t e c t i o nb e 0 3 m c sah o tf o c u si nr e s e a r c ho fd a t a m i n i n g a n d p r i v a c yp r o t e c td a t am i n i n g ( p p d m ) c o m e si n t ob e i n g t h em e t h o dt h a tp r i v a c yp r e s e r v i n gc l a s s i f i c a t i o nd a t am i n i n g u s i n gd e c i s i o nh a sb e c o m e f o c u so f s t u d yi na r e ao fd a t am i n i n gr e c e n ty e a r s , b e c a u s ec l a s s i f i c a t i o nd a t am i n i n gi st h e m a i nt y p eo fd a t am i n i n ga n dd e c i s i o nt r e ei sm o s tu s e da sc l a s s i f i e r i nc l a s s i f i c a t i o nm i n i n g c u r r e n t l y , t h e r e r em a n yw a y st om o d i f yd a t ai np r i v a c yp r o t e c t i o nd a t am i n i n g r a n d o m p e r t u r b a t i o nt e c h n o l o g yt h a tc a n tc h a n g et h ee s s e n t i a lc h a r a c t e ro ft h e 嘶g i n a ld a t ai su s e d m o s t l y h o w e v e r , t h em e t h o do fp r i v a c yp r e s e r v i n gc l a s s i f i c a t i o nd a t am i n i n gh a sm a n y d e f e c t s , s u c ha sl i m i t e dt od a t a sc h a r a c t e r , g e n e r a t i n gp r i v a c yd e s t r o ya f t e rr a n d o m p e r t u r b a t i o n , h i g hf i l l o rr a t eo fr e c o n s t r u c t i n gd i s m b u t i o no ft h eo r i g i n a ld a t a , p r i v a c y p r e s e r v i n gd e g r e ei sl o w , a c c u r a c yo fm i n i n gr e s u l t sa n ds oo i lf o rt h e s er e a s o n s ，w e p r o p o s et h em e t h o do fp r i v a c yp r o t e c t i o nc l a s s i f i c a t i o nm i n i n g i tu s er a n d o mp e r t u r b a t i o n m a t r i xt oc h a n g ed a t aa n dr e c o n s t r u c td i s t r i b u t i o no fo r i g i n a ld a t as e tb yr a n d o mp e r t u r b a t i o n m a t r i xo fu n i t e dm u l t i - a t t n b u t eg e n e r a t e db yr a n d o mp e r t u r b a t i o nm a t r i xo fs i n g l e - a t t r i b u t e w ee n c o d ed i f f e r e n tv a l u ef o re a c ha t m b u t eo fo r i g h l a ld a t as e tt om a k et h et e c h n o l o g yb e s u i t a b l et ov a r i e t i e so fd a t at y p e s t h et e c h n o l o g ys e l e c t sar a n d o mp e r t u r b a t i o nm a t r i xf o r e a c ha t m b u t et oi n c r e a s et h ed e g r e eo f p r i v a c yp r e s e r v i n ga n d u s e st h er - a m p l i f y i n gm e t h o d t op r e v e n tp r i v a c yb r e a c ha f t e rt h ed a t ac o n v e r t e d w ea d o p tm a t r i xc o n d i t i o nn u m b e rt o r e d u c et h ee r r o rr a t eo fr e c o n s t r u c t i n gt h ed i s m b u t i o no fo r i g i n a ld a t aa n di m p r o v et h e a c c u r a c yo fm i n i n g k e yw o r d s ：d a t am i n i n g ；p r i v a c yp r e s e r v i n g ；d e c i s i o nt r e e ；r a n d o mp e r t u r b a t i o n m a t r i x 内蒙古科技大学硕士学位论文 摘 目录 1 绪论 1 1 课题研究背景。 1 2 课题研究意义 1 3 课题的主要工作 1 4 论文的结构和组织。 2 数据挖掘 数据挖掘的概述 】【 】【 2 1 1 数据挖掘概念 2 1 2 数据挖掘对象及任务 2 1 3 数据挖掘的基本过程 2 2 传统分类数据挖掘 2 2 1 分类数据挖掘算法 1 2 4 。4 4 4 2 2 2 决策树分类 3 隐私保护数据挖掘综述 3 1 隐私信息与隐私保护 3 1 1 隐私信息 3 1 2 隐私保护对象。 3 2 隐私保护数据挖掘产生 3 3 隐私保护数据挖掘的分类 1 7 3 4 隐私保护数据挖掘研究现状。 3 4 1 基于集中分布数据的隐私保护数据挖掘 3 4 2 基于分布式数据的隐私保护数据挖掘。 3 5 算法分析 4 隐私保护分类数据挖掘 4 1 基本思想与框架。2 5 4 2 数据预处理2 6 4 3 数据转换。 4 3 1 相关定义2 8 4 3 2 设置单属性随机扰动矩阵。 4 3 3 多属性联合随机扰动矩阵的生成。 4 3 4 数据扰动3 1 4 4 分类数据挖掘 3 2 l 内蒙古科技大学硕士学位论文 4 4 1 相关公式 4 4 2 建立决策树 3 2 4 4 3 决策树剪枝3 4 4 4 4 决策树提取分类规则3 5 5 实验结果与分析 实验环境 5 2 算法评估标准 5 3 实验结果分析 结论 参考文献。 。3 6 。3 6 3 6 在学研究成果4 3 鸳筻谢 、 内蒙古科技大学硕士学位论文 1 绪论 1 1 课题研究背景 随着数据库技术和网络技术的发展，许多领域都积累了大量的数据，这些数据已被 认为是最重要的财富，那么如何把这些财富变成现实呢? 数据挖掘作为一种重要的转化 工具，它可以从数据集中自动抽取隐藏在数据中的那些有用信息和规律，数据挖掘给人 类带来巨大利益同时，也引出了许多问题。由于信息技术的发展使人们收集了大量的个 人数据，如：犯罪记录、购物习惯、信用和医疗历史以及驾驶记录等。这些信息在许多 领域，如：医疗研究、法律实施和国家安全非常有用。例如：对犯罪数据的分析、医疗 数据分析，数据挖掘技能已经被美国联邦调查局作为调查俄克拉荷马州城市爆炸案的辅 助工具。尽管数据挖掘技术对社会有很大利用价值，但对它的使用引发了保留意见。由 于公众对个体隐私越来越关注，人们最容易想象到的是对不被授权的金融交易和医疗记 录的利用存在潜在的危害。美国的民意调查显示关于使用个人信息的忧虑日益上升，最 近的民意调查显示：有7 0 以上的被访者反对将医疗记录不受制约地应用于研究项目； 有7 8 的被访者认为计算机技术加大了对个人隐私的威胁。因此如果要保护隐私，将来 要严格控制计算机的使用，将近有7 6 的人觉得自己对个人信息已经失去了控制，个人 隐私受到威胁。英国广播电视、时代周刊和其它最近的研究表明：至少有9 3 的被访者 认为公司在出售个人数据之前必须获得个人的允许。另一项调查显示：有9 6 的被访 者认为不应该在没有被允许的情况下使用私人信息，超过2 0 的被访者亲身体验过隐 私被侵犯。 目前，隐私泄露给人们带来巨大的危害，给数据收集带来障碍，制约着数据挖掘技 术的发展。 1 2 课题研究意义 数据挖掘【1 l 是一个强有力数据分析工具，在商务决策、科学和医学研究等领域 运用越来越深入，它给人们带来丰厚利益的同时也伴随着巨大的危险，致使人们害 怕隐私泄露，不敢把真实数据给挖掘者进行挖掘。此外，随着网络技术的发展，越 来越多的个人隐私信息( 比如：个人的电话号码、家庭住址、银行帐号等) 可以从 网上查到，经常造成个人隐私泄露事件发生，使得大多数人认为网络不安全，不愿 把自己真实信息留在网上。例如：某公司在网上做产品调查时，许多用户出于隐私 保护的目的，提交一些虚假信息，甚至，有的人直接拒绝调查，这样给数据挖掘中 = l 内蒙古科技大学硕士学位论文 的数据收集带来很大的不便，而且收集起来的数据也没有实际价值，这样给数据挖 掘技术的发展带来障碍。隐私保护数据挖掘弥补这些不足，成为数据挖掘技术研究 的一个重要的方向。 目前，隐私保护数据挖掘( p p d m ) 已成了数据挖掘的一个分支，其主要目的 是在严格保护个人隐私的条件下，得到准确的挖掘结果。它保护的隐私信息体现在 如下两方面：第一保护个人信息，就是在数据挖掘过程中可以直接或间接确定用户 的不能泄漏的特征信息；第二保护产生模式，限制挖掘中部分敏感模式的产生和泄 漏。根据挖掘出知识的模式不同，隐私保护数据挖掘算法大致可分为隐私保护分类 数据挖掘、隐私保护关联规则挖掘、隐私保护聚类挖掘等几个方面。在隐私保护分 类数据挖掘中，用于修改数据的技术种类繁多，其中随机扰动技术是最常用的一 种。随机扰动技术根据设置概率对数据进行随机转换，转换后再根据概率公式重建 原始数据分布。由于它在数据转换过程中不改变原数据的本质特征，在隐私保护分 类挖掘中得到广大挖掘者的青睐。但在现有的基于随机扰动技术的隐私分类挖掘中 存在很多不足。如：适用的数据类型有限，扰动后可能产生隐私破坏，隐私保护度 不高或挖掘精度低等。针对这些不足本文提出一种改进的隐私保护分类数据挖掘的 方法。 1 3 课题的主要工作 本文的主要工作分四部分： 1 数据预处理：把数据集的连续属性进行离散化：给属性域的每个值用自然数编 码，编码后生成属性域编码表；根据属性域编码表把数据集转换为编码数据集。 2 数据转换：设计单属性概率转移矩阵：由单属性概率转移矩阵生成多属性联合概 率转移矩阵；设计数据扰乱算法。 3 分类挖掘：根据转换后的数据集和生成多属性联合概率转移矩阵建立决策树；设 计决策树剪技算法；由决策树提取规则；根据属性域编码表翻译规则。 4 通过实验进行性能分析。 1 4 论文的结构和组织 第一章绪论，主要介绍课题研究背景、现实意义和课题的主要工作；第二章数据挖 掘，介绍数据挖掘概念、数据挖掘对象和任务和数据挖掘的基本过程，传统分类数据挖 掘，主要介绍了分类算法的种类和决策树分类，在决策树分类中，介绍了决策分类的优 内蒙古科技大学硕士学位论文 点、构造过程和经典的决策树构造算法) 3 ；第三章隐私保护数据挖掘综述，介绍了隐 私信息和隐私权，隐私保护数据挖掘产生和发展，隐私保护数据挖掘的分类和隐私保护 分类算法的分析：第四章隐私保护分类数据挖掘，介绍本文提出隐私保护分类数据挖掘 方法，主要内容分两个部分：本文方法的基本思想和框架以及方法的具体过程；第五章 为实验测试和结果分析；最后第六章对本文进行了总结。 内蒙古科技大学硕士学位论文 2 数据挖掘 2 1 数据挖掘的橛述 2 1 1 数据挖掘概念 随着全球信息化发展，人类利用信息技术收集、加工、组织、生产信息的能力 也大大提高，致使数以万计的各种类型的数据库产生，它们在科学研究、技术开 发、商业运营、市场扩张、生产管理、政府办公等方面发挥着巨大作用。然而，随 着信息量的不断增多，特别是网络信息资源的迅猛扩张，人类面临着新的挑战。如 何不被堆积如山的信息所淹没? 如何能够迅速地从海量信息中获取有用数据? 如何 能够充分提高信息的利用率? 这些问题引起了许多入的思考，数据挖掘( d a t a m i n i n g ) 技术应运而生。 数据挖掘是指从数据集合中自动抽取隐藏在数据中的那些有用信息的过程，这 些信息的表现形式为：规则、规律、概念及模式等。它可帮助决策者分析当前数据 和历史数据，并从中发现隐藏的关系和模式，进而预测未来可能发生的行为。数据 挖掘的过程也叫知识发现的过程，它是一门涉及面很广的交叉性新兴学科，汇集了 统计学、数据库、机器学习、知识获取、模式识别、专家系统、数据可视化和高性 能计算等多种学科。数据挖掘的研究是以应用为驱动的，从一诞生，就带上了强烈 的应用色彩。由于其本身的特点，数据挖掘在金融、零售业、医学、保险业、制造 业、运输业、科学与工程研究等众多领域都有广阔的应用。当前，数据挖掘领域还 在不断的扩大，数据挖掘技术的研究与应用越来越显出强大的生命力。 2 1 2 数据挖掘对象及任务 数据挖掘对象【2 】主要有关系数据库、数据仓库、文本数据库、多媒体数据库 等。数据挖掘的任务是从大量的数据中发现知识，知识是人类认识的成果或结晶， 包括经验知识和理论知识。数据挖掘发现的知识通常是用以下形式表示：概念 ( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 、约束 ( c 0 n s 仃a i l l t s ) 、可视化( v i s u a l i z a t i o n s ) 等。 比较典型的数据挖掘任务有：概念描述、分类1 3 】( c l a s s i f i c a t i o na n d p r e d i c t i o n ) 、关联分析 4 1 ( a s s o c i a t i o na n a l y s i s ) 、聚类分析【5 】( c l u s t e r i n g a n a l y s i s ) 、孤立点分( o u t l i e rm i n i n g ) 、演变分析( e v o l u t i o na n a l y s i s ) 等。其中分 类和预测挖掘是目前活跃、研究最深入的领域。 内蒙古科技大学硕士学位论文 1 概念描述 概念描述本质上就是对某类对象的内涵特征进行概括。一个概念常常是对一个 包含大量数据的数据集合总体情况的概述。如对一个商店所售电脑基本情况的总结 就会获得所售电脑基本情况的一个整体概念( 如：某商店所售的电脑，基本上为p 以上的兼容机) 。对含有大量数据的数据集合进行概述性的总结并获得简明、准 确的描述，这种描述就称为概念描述。概念描述分为特征描述和区别性描述。前者 描述某类对象的共同特征，后者描述不同类对象之间的区别。 2 分类和预测 分类是数据挖掘的一个重要的任务和目标。目前分类数据挖掘的研究在商业上 应用比较广泛。分类就是对数据的过滤、抽取、压缩以及概念提取等。分类的目的 是构造一个分类函数或分类模型( 也常常称作分类器) 。由于数据挖掘是从数据中 挖掘知识的过程，因此要构造这样一个分类器，这种类知识也必须来自于数据，即 需要有一个训练样本数据作为输入。分类器的作用就是能够根据数据的属性将数据 分派到不同的组中，即：分析数据的各种属性，并且找出数据的属性模型，确定哪 些数据属于哪些组。这样我们就可以利用该分类器来分析已有的数据，并预测新数 据将属于哪一个组，即：数据对象的类标记，然而，在某些应用中，人们可能希望 预测某些空缺的或不知道的数据值，而不是类标记。当被预测的是数值数据时，通 常称之为预测。分类模式可以采用多种形式表示，如分类( m n 砸n ) 规则，数学 公式或神经网络等。可以应用于分类知识挖掘的一些有代表性的分类技术有：决策 树、贝叶斯分类、遗传算法、神经网络分类、类比学习和案例学习，以及粗糙集和 模糊集等方法。分类应用的实例很多，例如，我们可以将银行网点分为好、一般和 较差三种类型，并以此分析这三种类型银行网点的各种属性，特别是位置、盈利情 况等属性并决定它们分类的关键属性及相互问的关系。此后就可以根据这些关键属 性对每一个预期的银行网点进行分析，以便决定预期银行网点属于哪一种类型。 3 关联分析 从广义上讲，关联分析是挖掘数据项之间的本质联系。既然数据挖掘的目的是 发现潜藏在数据背后的知识，那么这种知识一定是反映不同对象之间的关联。它是 数据项之间关联及其程度的刻画。关联知识反映一个事件和其他事件之间的依赖或 关联。数据库中的数据一般都存在着关联关系，也就是说，两个或多个变量的取值 之间存在某种规律性。数据库中的数据关联是现实世界中事物联系的表现。数据库 作为一种结构化的数据组织形式，利用其依附的数据模型可能刻画了数据间的关 联。但是，数据之间的关联是复杂的、有时是隐含的。关联分析的目的就是要找出 内蒙古科技大学硕士学位论文 数据库中隐藏的关联信息。这种关联关系有简单关联、时序关联、因果关联、数量 关联等。这些关联并不总是事先知道的，而是通过数据库中数据的关联分析获得 的，因而对商业决策具有新价值。简单关联，例如：购买面包的顾客中有9 0 的人 同时购买牛奶。时序关联，例如：若a t & t 股票连续上涨两天且d e c 股票不下 跌，则第三天m m 股票上涨的可能性为7 5 。它在简单关联中增加了时间属性。 关联规则挖掘是关联知识发现的最常用方法。为了发现出有意义的关联规则，需要 给定两个阈值：最小支持度( m i n i m u ms u p p o r t ) 和最小可信度( m i n i m u m c o n f i d e n c e ) 。挖掘出的关联规则必须满足用户规定的最小支持度，它表示了一组项 目关联在一起需要满足的最低联系程度。挖掘出的关联规则也必须满足用户规定的 最小可信度，它反映了一个关联规则的最低可靠度。在这个意义上，数据挖掘系统 的目的就是从数据库中挖掘出满足最小支持度和最小可信度的关联规则。关联规则 的研究和应用是数据挖掘中最活跃和比较深入的分支，已经提出了许多关联规则挖 掘的理论和算法。 4 聚类分析 一般把学习算法分成有导师和无导师学习两种方式，主要区别是有没有类信息 作为指导。聚类是典型的无导师学习算法，一般用于自动分类。数据挖掘的目标之 一就是进行聚类分析。聚类就是将数据对象分组成为多个类或簇，同一类中的对象 具有较高的相似度，而在不同类中的对象差别较大。一般情况下，聚类分析不要求 训练数据提供类标记，聚类可以用于产生这种标记。聚类按照某个特定标准( 通常是 某种距离) ，最终形成的每个类，在空间上都是一个稠密的区域。所形成的每个类可 以导出规则。通过聚类技术可以把数据划分为一系列有意义的子集，进而实现对数 据的分析。例如，一个商业销售企业，可能关心哪些( 同类) 客户对制定的促销策 略更感兴趣。聚类分析与分类和预测不同，前者总是在类标识下寻求新元素属于哪 个类；而后者通过对数据的分析比较生成新的类标识。聚类分析生成的类标识( 可 能以某种容易理解的形式展示给用户) 刻画了数据所蕴含的类知识。当然，数据挖 掘中的分类和聚类技术都是在已有的技术基础上发展起来的，它们互有交叉和补 充。聚类技术主要是以统计方法、机器学习、神经网络等方法为基础。常用的聚类 算法有基于划分、层次、密度、网格和模型的五大类聚类算法。作为统计学的一个 重要分支。聚类分析有很广泛的应用，包括市场或客户分割、模式识别、生物学研 究、空间数据分析、互联网文档分类及许多其它方面。 5 孤立点分析 一个数据库中的数据一般不可能都符合分类预测或聚类分析所获得的模型。那 内蒙古科技大学硕士学位论文 些不符合大多数数据对象所构成的规律或模型的数据对象就被称为孤立点。在数据 挖掘正常类知识时，通常总是把它们作为噪音来处理。因此以前许多数据挖掘方法 都在正式进行数据挖掘之前就将这类孤立点数据作为噪声或者意外而将其排出在数 据挖掘的分析处理范围之外。然而在一些应用场合中，如信用欺诈、入侵检测等小 概率发生的事件往往比经常发生的事件更有挖掘价值。因此当人们发现这些数据可 以用于欺诈检测，异常监测等方面时，这些数据是非常有价值的。 6 w c b 挖掘 i n t e m e t 是一个巨大、分布广泛、全球性的信息服务中心，近年来，i n t e r n e t 正 以令人难以置信的速度在飞速发展，越来越多的机构、团体和个人在i n t e m e t 上发 布信息、查找信息。虽然i n t e m e t 上有海量数据，但是由于w e b 是无结构的、动 态的，并且w e b 页面的复杂程度远远超过了文本文档，人们想要找到自己想要的 数据犹如大海捞针。信息检索界面开发了许多搜索引擎，但其覆盖率有限，另外不 能针对有不同的兴趣的特定用户给出特殊的服务，因此不具有个性化。不仅i n t e m e t 涉及新闻、广告、消费信息、金融管理、教育、政府、电子商务和许多其它信息服 务，而且网页还包含了丰富和动态的链接信息，以及网页页面的访问和使用信息， 这为数据挖掘提供了丰富的资源。解决上述问题的一个途径，就是将传统的数据挖 掘技术和w c b 结合起来，进行w e b 挖掘。w e b 挖掘一般的定义为：从与w c b 相 关的资源和活动中抽取感兴趣的、潜在的、有用的模式和潜藏的信息。w e b 挖掘可 以在很多方面发挥作用，如对搜索引擎的结构进行挖掘，确定权威页面，w c b 文档 分类，w e bl o g 挖掘、智能查询等。 2 1 , 3 数据挖掘的基本过程 数据挖掘是从大量数据中抽取未知的、有价值的模式或规律等知识的复杂过 程。简单的说，一个典型的数据挖掘过程可以分成四个阶段，即数据预处理、数据 挖掘、模式评估及知识表示。数据预处理阶段主要包括数据的整理、数据中的噪声 及空缺值处理、属性选择和连续属性离散化等。数据挖掘包括挖掘算法的选择和算 法参数的确定等。模式评估对得到的模式进行评价、训练和测试。这三个阶段是循 环往复的过程，直到得到用户满意的模式为止。数据挖掘过程是交互的，需要用户 ( 特别是领域专家) 的参与。 数据挖掘具体过程如图2 1 。 内蒙古科技大学硕士学位论文 图2 1 数据挖掘流程 数据清理( 消除噪声或不一致数据) ； 数据集成( 各种数据源可以组合在一起) ： 一数据选择( 从数据库中检索与分析任务相关的数据) ； 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作) ； _ 数据挖掘( 使用智能方法提取数据模式) ； 一模式评估( 根据某种兴趣度量、识别表示知识的真正有趣的模式) ：数据挖掘的 结果有些是有实际意义的，而有些是没有实际意义的，或是与实际情况不相符的， 这就需要进行评估。评估可以根据用户多年的经验，也可以直接用实际数据来验证 模型的正确性，进而调整挖掘模型，不断重复进行数据挖掘。 一知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) ：数据挖掘的 结果一般表现为模式，而且这种模式必须能被用户理解。模式可以看作是我们所说 的知识，它给出了数据的特性或数据之间的关系，是对数据包含的信息抽象的描 述。因此模式可以是一组规则、聚类、决策树或者其他方式表示的知识，如“学习 刻苦并且善于思考的学生成绩都非常优秀 。 在理解数据挖掘的具体实施过程时，我们还应该注意以下几点：( 1 ) 数据挖掘 仅仅是整个挖掘过程中的一个重要阶段；c 2 ) 数据挖掘的质量不但取决于所选用的 数据挖掘技术，而且还取决于所挖掘数据的数量和质量，如果选择了错误的数据或 不适当的数据，或对数据进行了不适当的转换，则挖掘结果不会准确：( 3 ) 整个挖 掘过程是一个不断反馈的过程。比如，用户在挖掘过程中发现选择的数据不太满 8 内蒙古科技大学硕士学位论文 意，或使用的挖掘技术产生不了期望的结果。这时，用户需要重复先前的过程，甚 至重新开始；( 4 ) 可视化技术在数据挖掘的各个阶段都起着重要的作用。比如在数 据预处理阶段，用户可以使用散点图、直方图等统计可视化技术来显示有关数据， 以期望对数据有一个初步的了解，从而为更好地选取数据打下基础；在数据挖掘阶 段，用户则要使用与领域问题有关的可视化工具；在结果表示阶段，则可能要用到 可视化技术以使发现的知识更易于理解等。 2 2 1 分类数据挖掘算法 分类挖掘( c l a s s i f i c a t i o nm i n i n g ) 就是找出一组能够描述数据集合典型特征的模 型( 或函数) ，以便能够分类识别未知数据的归属或类别( c l a s s ) 。数据挖掘涉及 的学科领域很多，根据任务的不同，数据挖掘有多种分类，其中分类数据挖掘是最 常用的一种。在分类数据挖掘中，常见的分类算法有：决策树分类【刚，贝叶斯分 类，k 最近邻1 7 1 ( k - n e a r e s tn e i g h b o r ，简称k n n ) 分类，s 一( s u p p o r tv e c t o r m a c h i n e ) 分类，v s m 【9 j ( v e c t o rs p a c em o d e l ) 分类，神经网络等，其中决策树分类和 贝叶斯分类最为典型。 1 决策树是一个可以自动对数据进行分类的树型结构，是树形结构的知识表 示，可以直接转换为决策规则。它能被看作一棵树的预测模型，树的根节点是整个 数据集合空间，每个分节点是一个分裂，它是对一个单一变量的测试，该测试将数 据集合空间分割成两个或更多块，每个叶节点是带有分类的数据分割。决策树也可 解释成一种特殊形式的规则集，其特征是规则的层次组织关系。决策树算法主要是 用来学习以离散型变量作为属性类型的学习方法。连续型变量必须被离散化才能被 学习。一棵决策树的内部结点是属性或属性的集合，叶结点就是所要学习划分的 类，内部结点的属性称为测试属性。当经过一批实例训练集的训练产生一棵决策 树，决策树可以根据属性的取值对一个未知实例集进行分类。使用决策树对实例进 行分类的时候，由树根开始对该对象的属性值逐渐测试，并且顺着分支向下走，直 至到达某个叶结点，此叶结点代表的类为该对象所处的类。 2 贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算 出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为 该对象所属的类。目前研究较多的贝叶斯分类器主要有四种，分别是：n a i v e b a y e s 1 们、t a n 、b a n 和g b n 。 内蒙古科技大学硕士学位论文 贝叶斯网络是一个带有概率注释的有向无环图，图中的每一个结点均表示 一个随机变量，图中两结点间若存在着一条弧，则表示这两结点相对应的随机变 量是概率相依的，反之则说明这两个随机变量是条件独立的。网络中任意一个 结点x 均有一个相应的条件概率表示( c o n d i t i o n a lp r o b a b i l i t yt a b l e ，c p t ) ， 用以表示结点x 在其父结点取各种可能值时的条件概率。若结点x 无父结 点，则x 的c p t 为其先验概率分布。贝叶斯网络的结构及各结点的c p t 定 义了网络中各变量的概率分布。 贝叶斯分类器是用于分类的贝叶斯网络。该网络中应包含类结点c ，其中 c 的取值来自类集合 c l ，c 2 ，c m ，还包含一组结点x - x 。，x ：，x 。) ，表示用于 分类的特征。对于贝叶斯网络分类器，若某一待分类的样本d ，其分类特征值 为x 一 x ，x ：，x 。) ，则样本d 属于类别c i 的概率。 p ( c = c , x 1 - x l ，x 2 一x 2 ，x 。一x 。) ，( i = 1 ，2 ，m ) 应满足下式： 即= q x = 力= 朋缸f 即= q x = 破即一c 2 x 一破，即= x = 功 ( 式2 1 ) 而由贝叶斯公式： 即邴咖坚等筹幽 ( 式2 2 ) 其中，p ( c 。c i ) 可由领域专家的经验得到，而p ( x x c c i ) 和p ( x - x ) 的计 算则较困难。 应用贝叶斯网络分类器进行分类主要分成两阶段。第一阶段是贝叶斯网络 分类器的学习，即从样本数据中构造分类器，包括结构学习和c p t 学习；第二 阶段是贝叶斯网络分类器的推理，即计算类结点的条件概率，对分类数据进行 分类。这两个阶段的时间复杂性均取决于特征值间的依赖程度，甚至可以是n p 完全问题，因而在实际应用中，往往需要对贝叶斯网络分类器进行简化。根据 对特征值间不同关联程度的假设，可以得出各种贝叶斯分类器，n a i v eb a y e s 、 t a n 、b a n 、g b n 就是其中较典型、研究较深入的贝叶斯分类器。 3 k n n 即k 最近邻分类法最初由c o v e r 和h a r t 于1 9 6 8 年提出的，是个理论上 比较成熟的方法。该方法基于类比学习，是一种非参数的分类技术，它在基于统计的 内蒙古科技大学硕士学位论文 模式识别中非常有效，并对未知和非正态分布可取得较高的分类准确度，具有鲁棒 性、概念清晰等优点。该方法的思路非常简单直观：如果一个样本在特征空间中的k 个最相似( 即：特征空间中最邻近) 的样本中的大多数属于某一个类别，则该样本也属 于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分 样本所属的类别。k n n 方法虽然从原理上也依赖于极限定理，但在类别决策时，只与 极少量的相邻样本有关。因此，采用这种方法可以较好地解决样本的不平衡问题。另 外，由于k n n - 方法主要靠周围有限邻近的样本，而不是靠判别类域的方法来确定所属 的类别，因此对于类域的交叉或重叠较多的待分样本集来说，k n n 方法较其他方法更 为适合。该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到 全体已知样本的距离，才能求得它的k 个最近邻点。目前常用的解决方法是事先对已 知样本点进行剪辑，事先去除对分类作用不大的样本。另外还有一种r e v e r s ek n n 法， 能降低k n n 算法的计算复杂度，提高分类的效率。该算法比较适用于样本容量比较大 的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生错误分类。 4 s v m 分类，即：支持向量机( s u p p o r tv e c t o rm a c h i n e ) 法，是一种二分法的分 类算法，由v a p n i k 等人于1 9 9 5 年提出，具有相对优良的性能指标。该方法是建立在统 计学习理论基础上的机器学习方法。通过学习算法，s v m 可以自动寻找出那些对分类 有较好区分能力的支持向量，由此构造出的分类器可以使类与类的间隔最大化，因而有 较好的适应能力和较高的分类准确率。该方法只需要由各类域的边界样本的类别来决定 最后的分类结果。支持向量机算法的目的在于寻找一个超平面h l ，d ) ，该超平面可以将训 练集中的数据分开，且与类域边界的沿垂直于该超平面方向的距离最大，故s v m 法亦 被称为最大边缘算法。待分样本集中的大部分样本不是支持向量，移去或者减少这些样 本对分类结果没有影响，s v m 法对小样本情况下的自动分类有着较好的分类结果。 5 v s m 分类，v s m 法即向量空间模型( v e c t o rs p a c em o d e l ) 法，由s a l t o n 等人于 6 0 年代末提出。这是最早也是最出名的信息检索方面的数学模型。其基本思想是将文 档表示为加权的特征向量：d = d ，w ；t 2 ，w z ；l ，w ：) ，然后通过计算文本相似 度的方法来确定待分样本的类别。当文本被表示为空间向量模型时，文本的相似度就可 以借助特征向量之间的内积来表示。在实际应用中，v s m 法一般事先依据语料库中的 训练样本集和分类体系建立类别向量空间。当需要对一篇待分样本进行分类的时候，只 需要计算待分样本和每一个类别向量的相似度即内积，然后选取相似度最大的类别作为 该待分样本所对应的类别。由于v s m 法中需要事先计算类别的空间向量，而该空间向 量的建立又在很大程度上依赖于该类别向量中所包含的特征项。根据研究发现，类别中 内蒙古科技大学硕士学位论文 所包含的非零特征项越多，其包含的每个特征项对于类别的表达能力越弱。因此，v s m 法相对其他分类方法而言，更适合于专业文献的分类。 6 神经网络，神经网络分类算法的重点是构造阈值逻辑单元