（模式识别与智能系统专业论文）水平分布式数据背景异质性对分类算法的影响.pdf

摘要 摘要 随着计算机网络和数据库技术的进一步发展，分布式计算环境的普遍存在促 使分布式数据挖掘技术成为当今的一大研究热点。在实际的分布式环境中，数据 不仅在物理上是分散的，而且具有背景异质性，现有的分布式数据挖掘技术能够 对物理上分散的数据进行处理和分析，却没有解决背景异质性的问题，因而其应 用范围受到局限。 本文以水平分布式数据的背景异质性为研究对象，通过量化的测试这种背景 异质性对具体分类算法，全局错分率和局部错分率的相对变化，为优化元学习组 合策略提供必要参考，课题研究内容归纳如下： 1 ) 早先简要介绍数据挖掘技术发展历史，国内数据挖掘应用商务智能市场 的发展背景和趋势，以及国内外分布式数据挖掘研究现状，课题来源和课题研究 内容。 2 ) 以数据挖掘的定义，过程以及对象为基础，研究了分类学习的两个基本 过程，基于交叉验证法建立分类学习器，用错分率评估其准确性能的方法。分布 式数据挖掘的发展需求和技术框架，探讨了分布式计算环境中，数据分散存储和 水平分布的特点。 3 ) 通过具体的商业虚拟企业水平分布式数据的特点研究，提出数据源之间 的差异为背景异质性的概念；确定研究的对象是水平分布式数据的背景异质性， 并根据问题研究对象确定了研究思路和方案，软件系统模型，最终建立问题研究 的分析系统。 4 ) 基于客户购买行为和心脏病诊断两个水平分布式实例数据集必要的预处 理，参照交叉验证的方法确立软件系统分析方案，通过分析系统测试，分别对贝 叶斯分类学习算法，函数分类学习算法，惰性分类学习算法和基于规则分类学习 算法的全局错分率和局部错分率进行对比分析，最后，由此总结出四个数据背景 异质性对分类算法影响的规律。 关键词：背景异质性，数据挖掘，分类算法，分布式数据挖掘 a b s t r a c t a b s tr a c t w i t ht h ef u r t h e rd e v e l o p m e n to fc o m p u t e rn e t w o r k sa n dd a t a b a s et e c h n o l o g y , t h e d i s t r i b u t e dc o m p u t i n ge n v i r o n m e n t ，d i s t r i b u t e dd a t am i n i n gt e c h n o l o g yb e c o m ea m a j o rr e s e a r c hf o c u s i nt h ea c t u a ld i s t r i b u t e dc o m p u t i n ge n v i r o n m e n t ，t h ed a t ai sn o t o n l yi ss c a t t e r e dp h y s i c a l l y ，b u ta l s oi t sc o n t e x t u a lh e t e r o g e n e i t yi se x i s t i n g t h e t r a d i t i o n a ld i s t r i b u t e dd a t am i n i n gt e c h n o l o g yc a na n a l y s i sd i s p e r s e dd a t ap p h y s i c a l l y , b u td o e sn o ts o l v et h ec o n t e x to fh e t e r o g e n e o u si s s u e s ，w h i c hl i m i t e di t ss c o p eo f a p p l i c a t i o n i nt h i sp a p e r , b a s e do nt h ec o n t e x t u a lh e t e r o g e n e i t yo ft h eh o r i z o n t a ld i s t r i b u t e dd a t a , i tt e s t st h ev a l u eo ft h ew h o l ee r r o rr a t ea n dt h el o c a le r r o rr a t eo fc l a s s i f i e ro n h e t e r o g e n e i t yo ft h i sb a c k g r o u n dt or e s e a r c ht h ec o n t e x t u lh e t e r o g e n e i t yo nt h e s p e c i f i cc l a s s i f i c a t i o na l g o r i t h m i no r d e rt oo p t i m i z et h ec o m b i n a t i o ns t r a t e g yo f m e t a - l e a m i n g i tc a np r o v i d et h en e c e s s a r yr e f e r e n c e ，t h et o p i c so ft h i sr e s e a r c ha r e s u m m a r i z e da sf o l l o w s ： a tf i r s t ，i ti n t r o d u c e sb r i e f l yt h eh i s t o r yo ft h ed e v e l o p m e n to fd a t am i n i n gt e c h n o l o g y , t h ed o m e s t i cd e v e l o p m e n ta n dt r e n d so fd a t am i n i n gb u s i n e s si n t e l l i g e n c em a r k e t ，a s w e l la sd o m e s t i ca n df o r e i g nd i s t r i b u t e dd a t am i n i n gr e s e a r c h ，i s s u e sa n dr e s e a r c h c 0 n t e n t b a s e do nt h ed e f i n i t i o n ，p r o c e s sa n do b j e c t - b a s e do fd a t am i n i n g ，i tf o c u s e so nt w o b a s i cp r o c e s so fc l a s s i f i e rl e a r n i n gp r o c e s s t h e ni tr e s e a r c h sd e t a i l l yt h em e t h o do f c r o s s - v a l i d a t i o nc l a s s i f i c a t i o nl e a r n i n g ，a n dt h ee r r o rr a t eo fc l a s s i f i e r si nt h e a s s e s s m e n to ft h e i r p e r f o r m a n c e ；o n t h eo t h e r h a n d ，i ta l s of o c u s e s o nt h e b i r t h ，d e v e l o p m e n ta n df r a m e w o r ko fd i s t r i b u t e dd a t am i n i n g ，t h e nb a s e do nt h e d i s t r i b u t e dc o m p u t i n ge n v i r o n m e n t ，i te x p l o r e st h ec h a r a c t e r i s t i c so fd a t as t o r e d d i s p e r s e d l ya n dh o r i z o n t a ld i s t r i b u t i o n i i a b s t r a c t t h r o u g he x p l o r a t i o no nt h e h o r i z o n t a l d i s t r i b u t e dd a t ao fc o m m e r c i a lv i r t u a l e n t e r p r i s e ，i tt a k e so u tt h ed e f i n i t i o no ft h ec o n t e x t u a lh e t e r o g e n e i t y , a st h ed i f f e r e n c e b e t w e e nt h ed a t as o u r c e i tc o n f i r mt h ef o c u so fr e s e a r c hi st h ec o n t e x t u a l h e t e r o g e n e i t yo fh o r i z o n t a ld i s t r i b u t e dd a t aa n dt h ef o c u so ft h es t u d y ，t h ei ti d e n t i f i e s i d e a sa n dp r o g r a m s ，b u i l d st h es o f t w a r ea n ds y s t e mm o d e lt o g e tu l t i m a t e l yt h e e s t a b l i s h m e n to ft h ea n a l y s i ss y s t e mi nt h ee n d o nt h et w od i s t r i b u t e dd a t as e t ss a m p l e so fc u s t o m e rb u y i n gb e h a v i o ra n dt h e d i a g n o s i so fh e a r td i s e a s e ，a f t e rn e c e s s a r yp r e p r o c e s s i n g ，i tr e f e r st h ee s t a b l i s h m e n t o fc r o s s - v a l i d a t i o nm e t h o dt ob u i l dt h es o f t w a r ea n a l y s i s p r o g r a m ；t h r o u g ht h e a n a l y s i so fs y s t e mt e s t i n g ，i ta n a l y s i z e st h ec h a n g eb e t w e e nt h ew h o l ee r r o rr a t ea n d t h el o c a le r r o rr a t e ，r e s p e c t i v e l yo nb a y e s i a n ，f u n c t i o n , e a g e rl e a r n e ra n dr u l e - b a s e d c l a s s i f i e r ；i nt h ee n d ，i ts u m su pf o u rr u l e sb a s e do nt h ep r e - r e s e a r c h k e yw o r d s ：d a t am i n i n g ，c l a s s i f i c a t i o na l g o r i t h m ，d i s t r i b u t i o n ，c o n t e x t u a l h e t e r o g e n e i t y i i i 独创性声明 独创性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包含 本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 5 9 指导教师签字： 论文作者签字： 1 年6 月争日 前延 肇红同 第一章绪论 1 1 课题背景 第一章绪论 帚一早三百t 匕 计算机硬件技术的稳定进步为人类提供了大量的数据收集设备和存储介质， 数据库技术的成熟和普及已使人类积累的数据量正在以指数方式增长。在这个信 息爆炸的时代，面对着浩瀚无垠的信息海洋，人们呼唤着一个去粗取精、去伪存 真的能将浩如烟海的数据转换成知识的技术，数据挖掘技术就是在这个背景下产 生的【l 】。 数据挖掘出现于2 0 世纪8 0 年代后期，是数据库研究中一个很有应用价值的新 领域，融合了人工智能，数据库技术，模式识别，机器学习，统计学和数据可视 化等多个领域的理论和技术。数据仓库是整个数据挖掘技术的基础，数据仓库之 父w h i n m o n 在建立数据仓库一书中对这样定义：数据仓库是一个面向主题 的【：】，集成的，非易失的，随时间变化的用来支持管理人员决策的数据集合。传 统的数据库管理系统的主要任务是联机事务处理，基于结构查询语言对数据库进 行简单的查询已经不能满足大量数据的用户分析需求，决策分析需要对数据记录 的大量复杂的计算才能得到结果，而每个计算都需要重新编写独立的过程代码来 实现，由此关系数据库之父c o d d 提出了多维数据库和多维分析的概念，后来又提 出了联机分析处理；而数据仓库则是在数据分析和决策方面提供o l a p j 艮务的系统 环境。 从功能角度上看，数据挖掘的广义观点是- 从存放在数据库、数据仓库或其 他信息库中的大量数据中发现有趣知识的过程c ，】。在较浅的层次上，它利用现有 数据库管理系统的查询、检索及报表功能，与多维分析、统计分析方法相结合， 进行联机分析处理( o l a p ) ，从而得到可供决策参考的统计分析数据。在深层次上， 则从数据库中发现前所未有的、隐含的知识。o l a p 的出现早于数据挖掘，它们都 是从数据库中抽取有用信息的方法，就决策支持的需要而言两者是相辅相成的。 o l a p 可以看作一种广义的数据挖掘方法，它旨在简化和支持联机分析，而数据挖 掘的目的是使这一过程尽可能自动化。 数据挖掘技术从一开始就是面向应用的，拥有为企业创造巨大经济效益的潜 广东t 业大学 = 学硕上论文 力。伴随数据库技术的提高和数据处理技术的发展以及各行业业务自动化的实 现，商业领域产生了大量的业务数据，要从这海量数据中提取出真正有价值的信 息，将数据转化为知识，以支持商业决策，需要用到能提取、存储有用信息，支 持决策的数据仓库( d w ) 、联机分析处理( o l a p ) 工具和数据挖掘( d m ) 等技术。因此 从技术层面上讲，d w 、o l a p 和d m 等技术在商业中的综合运用，又提出了商业智能 ( b u s i n e s si n t e l l i g e n c e ) ，简称b i ，通常被理解为将企业中现有的数据转化 为知识，帮助企业做出明智的业务经营决策的工具和企业级系统解决方梨l 。 商业智能作为一种企业信息集成解决方案，为企业不同的应用系统，如企业 资源规划( b r p ) 、客户关系管理( c r i v l ) 、供应链管理( s c m ) 以及外部环境扫描等系 统之间架起了互通的桥梁。同时，这些信息化系统也为商业智能提供了数据源， 离开了它们，商业智能就会成为无源之水，无本之木。但商业智能的价值又在这 些系统之上，因为它可以发现数据背后隐藏的商机或威胁，获得洞察力，了解企 业和市场的现状，把握趋势，识别异常情况，理解企业业务的推动力量认清正 在对企业的业务产生影响的行为及影响程度如何等。 2 0 0 7 年国内商业智能应用市场仍然保持增长态势，2 0 0 7 年市场规模达到 1 8 6 3 亿元，比2 0 0 6 年增长2 5 3 。商业智能用户趋于理性，以达到决策迅速、营 销精确、成本降低、利润提升等为目的购买商业智能产品及服务，逐步转向业务 驱动，注重商业智能的投资回报。国内商业智能行业发展呈现出明显行业需求特 征。电信业以“巩固实力，提升服务”为主要b i 需求；银行、证券、保险等金融企 业以“筛选客户、防范风险”为主要b i 需求；税务、公安、社保、卫生等政府部门 以“加大监管、科学决策为主要b i 需求；连锁零售企业、物流、电子商务等流通 业用户以“动态跟踪、应即调配”为主要b i 需求；电力、石油石化、煤炭等能源企 业以“整合资源、完善保障”为主要b i 需求；特别是制造业，以“优化配置、高效 生产”为主要b i 需求，在钢铁、消费电子、电器、汽车、食品、烟草、医药等企业 得到广泛应用。b i 提升绩效的价值凸显，使得用户接受度大幅提升。国际b i 巨头 厂商，如b o 公司、h y p e r i o n ( 已被o r a c l e 公司收购) 、n c r 、i b m 、甲骨文、微软、 s a s 公司等，品牌与规模优势依然非常突出，是国内大部分b i 厂商难以与之匹敌 的。起步比较早的国内b i 厂商，如从1 9 9 7 年开始进入b i 领域的菲奈特、先进数通 公司、吉贝克公司等，凭借本土化的优势以及对国内b i 用户所需要的应用的独特 2 第一章绪论 见解，也在国内的b i 市场上占有超过3 0 的市场份额。其中菲奈特是国内b i 厂商 中无可争议的领军人物，该公司为银行、保险、税务、海关、烟草及制造业成功 地实施了超过1 0 0 个b i 项目，并且是目前国内唯一拥有自主知识产权的平台级b 工 产品的国内b i 厂商的菲奈特公司在十年的发展中积累了丰富的行业经验及大量 的b 1 人才( 超过3 0 人的b i 行业顾问及超过2 0 0 人的专业实施团队) 。无论其跨行 业、跨平台的专业实施能力，还是成功案例的数量，都是国内其他b 工厂商难以望 其项背的，被誉为“国内b i 厂商领先代表扛起国产化大旗”。 2 0 0 7 年大型商业智能供货商市场最明显的特征是并购与整合。i b m 、 m i c r o s o f t 、o r a c l e 和s a p 都不约而同地专注于b i 市场，并投入数十亿美金在顶级 b i 和绩效管理系统厂商。2 0 0 7 年3 月3 日，o r a c l e 宣布以3 3 亿美元收购 h y p e r i o n ：2 0 0 7 年1 0 月7 日下午，s a p 宣布将以6 8 亿美元现金收购b u s i n e s s o b j e c t s ：2 0 0 7 年1 1 月1 4 日，i b m 同意以5 0 亿美元收购c o g n o s 。虽然m i c r o s o f t 在 2 0 0 7 年并没有做出任何大规模的b i 并购动作，但它却在背地里奋力追击。根据 g a r t n e r 的报告，m i c r o s o f t 在定价策略及m i c r o s o f to f f i c e ( 包括2 0 0 7 年的创新 产品一p e r f o m a n c e p o i n t 服务器) 和s q ls e r v e r 产品的整合上，对原先使用 m i c r o s o f t 信息架构平台的组织是特别具有吸引力的。 商业智能( b i ) 技术进入中国市场十年来，经过了漫长的认知期，走过了艰难 的市场培育期，到今天已经迎来了爆发式的市场高速增长期。目前国内的高端b i 市场己打破国际厂商一统天下的局面。国内的高端b i 厂商凭借本土化的优势，经 过多年的努力，目前也已经在国内某些行业的高端市场上占有了一席之地。国际 厂商在b i 平台领域仍然占有优势，而对于b i 应用领域和中低端b i 市场( 如中小企 业和规模较小的金融机构) ，国内b i 厂商的优势则更为明显。国际b i 厂商通过总 结多年来在国内市场发展的经验，也对自己的不足有了一定的认识而开始转向寻 求与国内b i 厂商的领军者进行合作。国内的b i 厂商也可以通过与国际b i 厂商的合 作来完善自身的不足。在目前的国内市场，学贯东西的专业b 1 人才的不足，无疑 是制约国内b i 市场发展的重要因素之一。专业b 1 人才的培育和储备对国际b i 厂商 和国内b i 厂商都尤为重要。在国内未来的b i 市场中，谁拥有更多懂得中国用户的 实际需要，并掌握先进的b i 技术的人才，谁就必将成为未来中国b i 市场的霸主。 随着计算机网络以及数据库技术的不断发展，尤其是i n t e r n e t ，私有的企业 广东1 = 业大学工学硕士论文 内部网以及无线网络等的广泛使用，网格计算越来越备受关注。然而传统的数据 挖掘系统所处理的数据是集中存储于数据库或者数据仓库中的，于是迫切需要对 传统的数据挖掘技术加以改进，使之具有较好的可扩展性，从而实现分布式计算 环境下的数据挖掘，以满足目前实际应用的需要【4 5 】。 分布式数据挖掘正是在这一背景下产生的。它是数据挖掘技术与分布式计算 的有机结合，主要用于分布式环境下的模式发现【s 】；同时，分布式数据挖掘也为 更好地利用大型或者超大规模数据库进行数据挖掘与知识发现提供了一条有效 的途径。 当前，国外分布式数据挖掘理论和应用发展迅猛，己开发的分布式数据挖掘 软件以及实验系统主要有： 1 ) j a m 系统( j a v aa g e n t s f o rm e t a - l e a r n i n go v e rd is t r i b u t e d d a t a b a s e s ) 【6 】：美国哥伦比亚大学、f l o r i d at e c h ，t h ef i n a n c i a ls e r v i c e s t e c h n o l o g yc o n s o r ti u m ( f s t c ) 开发的商业银行诈骗和入侵检测系统。 2 ) p a d m a 系统( p a r a l l e ld a t am i n i n ga g e n t s x n ：由美国l o s a l a m o s 国家实 验室开发的一个文本分析工具； 3 ) p a p y r u s 系统【8 j ：伊利诺斯大学国立数据挖掘中心研制的、基于工作站机 群的数据挖掘工具，它支持包括移动数据、移动模型以及结果移动等混合传输策 略。 4 ) w o r l d 系统( t h ew o r l d w i d er e l a t i o nl e a n i n gd a e m o ) 【9 】：美国匹兹堡大 学人工智能实验室开发的用来实现从分布在网上的多个数据库中的多个表进行 归纳学习。 在我国，分布式数据挖掘技术的研究还处于起步阶段，已有的研究工作大多 是在解决数据的物理分散性这一层面上跟踪国际主流方法，而对数据背景异质性 的研究还处于起步探索阶段，迫切需要在这方面开展大量的基础研究工作，以提 高我国在分布式数据挖掘领域的理论研究和应用水平。 1 2 课题来源与研究内容 分布式计算环境的普遍存在促使分布式数据挖掘技术成为当今的一大研究 热点。在实际的分布式环境中，数据不仅在物理上是分散的，而且具有背景异质 4 第一章绪论 性。现有的分布式数据挖掘技术能够对物理上分散的数据进行处理和分析，却没 有解决背景异质性的问题，因而其应用范围受到局限。基于水平分布式数据挖掘， 对数据背景异质性问题，我的导师邢延副教授在爱尔兰国立大学期间，与合作者 做了很多十分重要的前期工作e 1 0 , 1 1 】，其中已经证明了数据的背景异质性对估值预 测的误差是有影响。本项目立足于这个基础，基于背景异质性的估值模型泛化到 广义的分类模型，为后续的背景异质性的知识发现和利用做一些必要的基础工 作。本项目属于教育部留学回国人员启动基金项目。 第一章绪论，简要介绍了分布式数据挖掘研究和应用背景，以及课题来源和 研究内容。 第二章，重点介绍了分类学习的训练和测试两个基本过程，基于交叉验证法 建立分类学习器，然后用错分率评估其准确性能的方法，简要介绍了在分布式数 据挖掘的发展需求和技术框架，仔细研究分布式计算环境中，数据分散存储和水 平分布的特点。 第三章，通过具体的商业虚拟企业水平分布式数据的研究特点，定义了数据 源之间的差异为背景异质性；确定了研究的对象是水平分布式数据的背景异质性 对分类算法的影响，并根据问题研究对象确定了研究思路和方案，软件系统模型， 最终建立了问题研究的分析系统。 第四章，基于客户购买行为和心脏病诊断两个实例分布式数据集必要的预处 理，参照交叉验证的方法确立了软件系统分析方案，通过分析系统测试，分别对 贝叶斯分类学习算法，函数分类学习算法，惰性分类学习算法和基于规则分类学 习算法的全局错分率和局部错分率进行对比分析，最后，由此总结出了四个数据 背景异质性对分类算法影响的规律。 广东工业人学丁学硕上论文 第二章分布式数据挖掘相关知识综述 2 1 经典数据挖掘技术的相关简介 经典数据挖掘技术是分布式数据挖掘技术发展的基础，与问题研究紧密 相关的知识包括：数据挖掘技术的工作流程，可挖掘的数据形式，分类器的工作 流程，分类器准确度的错分率评估方法。 2 1 1 数据挖掘技术的工作流程 数据挖掘功能的广义观点：数据挖掘是从存放在数据库、数据仓库或其他信 息库中的大量数据中发现有趣知识的过程，基于这种观点1 1 2 ，如图2 - 1 ，典型的数 据挖掘系统具有以下主要模块： 用户界面 l 上t 模式评估 l 上t 数据挖掘引擎 l 1 lt 。数据库或数据仓库服务器1 t 图2 1 典型数据挖掘技术工作流程 f i g 2 - 1w o r k f l o wo fat y p i c a ld a t am i n i n gs y s t e m 数据挖掘引擎：是数据挖掘系统的基本部分，理想情况下由一组功能模块组 6 第二章分布式数据挖掘相关知识综述 成，用与执行特征化、关联和相关分析、分类、预测、聚类分析、离群点分析和 演变分析等任务。 知识库：是指领域知识，用于指导搜索和评估结果模式的兴趣度。这种知识 可能包括概念分层和用户经验知识。 模式评估模块：通常该成分使用兴趣度度量，并与数据挖掘模块交互，以便 将搜索聚焦在有趣的模式上。 用户界面：该模块主要是用户和系统的通信中介，也以不同的形式对模式可 视化的界面f 3 】。 数据库中的数据挖掘是一个多步骤的处理过程，一般分为m 】： 1 ) 问题定义，了解相关领域的有关情况，熟悉背景知识，弄清用户要求。 2 ) 数据提取，根据要求从数据库中提取相关的数据。 3 ) 数据预处理，主要对前一阶段产生的数据进行再加工，检查数据的完整 性及数据的一致性，对其中的噪音数据进行处理，对丢失的数据进行填补。 4 ) 知识提取，运用选定的知识发现算法，从数据中提取用户所需要的知识， 这些知识可以用一种特定的方式表示或使用一些常用的表示方式 5 ) 知识评估，将发现的知识以用户能理解的方式呈现，如某种规则，再根 据实际情况对知识发现过程中的具体处理阶段进行优化，直到满足用户要求 2 1 2 可挖掘的数据形式 原则上，分布式数据挖掘和集中式的对象也没有根本上的差别，只是这些数 据对象的物理存储具有分布性。可以应用与任何类型的信息库以及瞬态数据( 数 据流) 。目前主要数据存储库主要包括关系数据库、数据仓库、事务数据库、高 级数据库、般文件、图片、数据流和万维网。高级数据库系统包括对象一关系 数据库和面向特殊应用的数据库，如空间数据库、空间数据库、时间序列数据库、 文本数据库、多媒体数据库。挖掘的难题和技术可能因存储系统而异【，。 当前关系数据库最常见，理论和技术最成熟，于是可供现有数据挖掘算法应 用的资源最为丰富。同时数据仓库技术也取得了长足的发展，数据仓库从多个数 据源收集信息，通过数据清理( d a t ac l e a n ) 、数据转换( d a t at r a n s a c t i o n ) 、 数据集成( d a t ai n t e g r a t i o n ) 、数据装入( d a t al o a d i n g ) 和定期刷新过程来 7 广东工业大学丁学硕十论文 构造多维数据库模型，为后续数据挖掘过程做好了数据源的必要准备【1 4 】。 2 1 3 分类器的工作流程 分类是数据挖掘中应用领域极其广泛的重要技术之一，至今已经提出很多算 法。分类是根据数据集的特点构造一个分类器，利用分类器对未知类别的样本赋 予类别的一种技术。构造分类器的学习过程一般分为训练和测试两个步骤【1 5 】：在 训练阶段，分析训练数据集的特点，为每个类别产生一个对相应数据集的准确描 述或模型；在测试阶段，利用类别的描述或模型对测试进行分类，测试其分类准 确度。一般来说，测试阶段的代价远远低于训练阶段1 1 6 1 。分类过程如下2 - 2 图所 示 图2 2 分类过程图 f i g 2 2p r o c e s so fc l a s s i f i c a t i o n 当类属性只有类标号( 通常用名词性n o m i n a l 表示) ，数据建模分析任务就 是分类学习；如果类属性是一个连续函数或者有序值( 通常用数值性n u m e r i c a l 表示) ，该学习类型归类为数值预测。由于每个训练元组都有类属性，分类学习 属于有监督学习 1 7 1 ，区别于无监督学习( 聚类) 。 2 1 4 分类器的准确度评估 为了能预测一个分类器在新数据上的性能表现，需要一组没有参与分类器建 立模型的数据集，并在此数据集上评估分类器的误差率。这组独立的数据集是称 为测试集，而且必须假设训练集和测试集都是某个特定问题的代表性样本。 对于分类问题，采用误差率( e r r o r r a t e ) 来衡量一个分类器的性能，分类 第二章分布式数据挖掘相关知识综述 器对每个测试集实例进行类预测，如果预测正确，则分类成功，反之则分类错误。 误差率就是所有错误分类实例个数在整体事例集中所占的比率，是总体性能的一 个衡量，如式( 2 1 ) ： errorrate：。m i n c o r r e c t ( 2 1 ) m w i t h c l a s s 当数据来源很充足时，只要在一个大的训练集上建模，然后在一个大的测试 集验证，评估结果可以反映分类模型性能。当训练和测试数据数量有限时，旁置 法保留一定数量的数据作为测试用，剩余的数据用于训练，在实践中，一般三分 之一的数据用于测试，而剩余的三分之二用于训练【3 】。 由于数据量小，也许用训练或者测试的样本不具有代表性，例如某一类的实 例在这三分之二样本的训练集中一个都没有，就很难保证，用这样的训练集建立 起来的分类器模型来对属于这一类的实例进行分类时有很好的表现，而且这一类 实例，由于没有分布在训练集，那么肯定全部在测试集中。因此，随机取样时必 须确保在训练集和测试集中每个类各种应有的比例，这个过程是分层，可以防范 训练集和测试集数据的样本代表性不一致。于是为了避免旁置法引起的偏差，分 层重复旁置法就是重复的用不同随机样本进行几次训练和测试，每一次迭代过程 中，随机抽取一个特定比例( 如三分之二) 的数据进行训练，可能经过分层处理， 剩余的数据用于测试，最后将每次不同迭代过程中所得的误差率进行平均得到一 个综合误差率。 在单次旁置过程中，交换训练集和测试集的角色，即用测试集数据进行训练， 并用训练集进行测试，然后将不同的结果平均一下，以此来减少训练集和测试集 数据代表性不一致所产生的影响，这个过程称为交叉验证。 基于有限数据的预测性能评估现在依然存在争议的问题，有很多不同的技 术，其中重复交叉验证在实践中适合大部分有限数据情形的评估方法。将数据集 分成n 份，轮流将其中( n 一1 ) 份作为训练数据建立模型，剩下的1 份作为测试数 据进行试验。每次试验都会得出相应的正确率，然后平均计算总的正确率来评估 分类器的准确性。通常设定n 等于1 0 ，是因为通过利用大量数据集、使用不同 学习技术进行的大量试验，表明1 0 折是获得最好误差估计的恰当选择【佴1 ，而且 也有一些理论根据可以证明这一点，这就是分层1 0 折交叉验证法。 9 广东工业大学工学硕l 论文 2 2 分布式数据挖掘技术的相关简介 分布式数据挖掘是当前国内外业界研究的热点，与本论文研究相关的知 识包括：分布式数据挖掘的作用，水平分布式数据的特点，水平分布式数据挖掘 的算法框架等三个主题。 2 2 1 分布式数据挖掘的作用 随着计算机网络以及数据库技术的不断发展，尤其是i n t e r n e t ，私有的企业 内部网以及无线网络等的广泛使用，然而传统的数据挖掘系统所处理的数据是集 中存储于数据库或者数据仓库中的，于是迫切需要对传统的数据挖掘技术加以改 进，使之具有较好的可扩展性，从而实现分布式计算环境下的数据挖掘，以满足 目前实际应用的需要1 2 ，嚣】。下面三个例子很好的说明这个问题： 例l ：假设某流行病学家正在调查丙型肝炎在美国的传播情况，她想研究丙 型肝炎的发病情况与各地气候之间的关系，为此她必须访问美国疾病控制中心关 于丙型肝炎的数据库以及美国环保署的环境数据库。由于分析所需的数据存放于 不同地点，如果使用传统的数据挖掘技术进行分析则需要将所有的数据集中在一 起，但由于数据量大大，这显然是不可行的。 例2 ：假设n 家大型的金融组织希望通过合作来共同防止信用卡欺诈，为此 这些组织之间必须共享一些相关的数据模式，从而构造一个全局预测模型用以对 可能出现的信用卡欺诈进行预测。但是从商业竞争的角度出发，它们并不想共享 数据库中的具体数据，因此将所有数据集中在一起进行分析是不可行的，传统的 数据挖掘方法将无法解决这个问题。 例3 ：一家大型的跨国公司希望通过对客户交易记录的分析来及时地制定一 套成功的营销策略，由于该公司在全球具有上千个销售点。因此如果将所有的数 据集中在一起构造一个数据仓库，然后再使用已有的商用数据挖掘软件进行分 析，那么仅仅构造出所需的数据仓库就需要大约一个月的时间，这显然不能满足 要求。 分布式数据挖掘正是面向上述类型的问题而产生的。总的来说，使用分布式 数据挖掘技术进行知识发现具有以下两个优点【6 1 ： 1 0 第二章分布式数据挖掘相关知识综述 1 ) 由于各种网络的广泛使用，目前许多实际应用所需的数据都是固有地分布 在各个不同的结点上的。同时出于对安全性、容错性、商业竞争以及法律约束等 多方面因素的考虑，将所有数据集中在一起进行分析往往是不可行的，而分布式 数据挖掘系统则可以充分利用分布式计算的能力对相关的数据进行分析与综合。 2 ) 另一方面，大多数传统的数据挖掘系统所采用的算法计算复杂度都相当 高，而且算法要求当前所据的数据都位于主存之中，这就使得对于大型或者超大 规模数据库进行数据挖掘变得十分困难甚至难以实现。这时，如果能将数据合理 地划分为若干个小棋块，并由数据挖掘系统并行地处理，最后再将各个局部处理 结果合成最终的输出模式，这样不仅能够完成预期的数据挖掘任务，同时也节省 了大量的时间和空间开销。 2 2 2 水平分布式数据的特点 在分布式的环境下，数据挖掘系统的设计和运行，早先系统是基于数据的固 有的分布式特性上的，早先，数据在物理上是分布式的，即数据存储在物理上分 散的多个数据站点中；而且由于商业机密和隐私保护等原因，这些分散存储的具 体数据在多数应用中是不能共享的。 数据在物理存储上的分散特性表现为：可以分为水平分布式( 如图2 5 ) 垂 直分布式( 如图2 - 5 ) 两种分布式数据挖掘系统。a 和b 站点数据具有相同的属 性空间( 同构) ；而b 站点和c 站点数据具有不同的属性空间( 异构) ，包含了 不同种类的信息，因此对于异构结点进行数据挖掘往往比较困难。 基于关系数据库，水平分布式数据集往往来源同一个组织或者不同组织相似 领域。现在大部分的分布式算法都是基于水平分布式数据集的。垂直分布式数据 集通常由于特别的目的，用得最多的是关联分析【，9 】，这些数据来源于同一组织的 不同部门，或者不同组织，最大的特点是每个数据集通常都有起联系作用的键 2 0 i ， 研究垂直分布式数据的主流技术有协同学习( c o l l e c t i v el e a r n i n g ) 【2 l 】。 由于本项目的关注点在于数据的背景异质性对分类算法影响的基础研究，早 先分类样本的属性空间要相同，故我们的研究是基于水平分布式数据集。 广东工业大学工学硕十论文 fx 3x 4x 5 1 13 14 73 1 2 32 46 42 2 8 9 4 51 o2 5 图2 5 水平分布式数据集示例 f i g 2 - 5t h es a m p l eo fh o r i z o n t a ld i s t r i b u t e dd a t as e t 2 2 3 水平分布式数据挖掘的算法框架 分布式数据挖掘和传统的数据挖掘最大的不同是前者是基于网络的分布式 计算环境的 2 2 , 2 3 ，后者的数据对象都是集中在一个存储地点的。分布式数据挖掘 的系统构架i ：】如下： 本地学习 l 数据源l ( 邳 。厂 、 旧雩2 l 模型联系 i 。7和共享 j i 数据源nk 兰警乡 元学习 图2 6 水平分布式数据挖掘算法框架 f i g 2 6a r c h i t e c h t u r eo fh o r i z o n t a ld i s t r i b u t e dd a t am i n i n gs y s t e m 分布式数据挖掘技术的共同框架图2 6 ，其主要的过程包括三步： 1 ) 局部学习：局部站点并行的学习过程可以分别采用不同的算法建立局部 模型，这些算法包括决策树、神经网络、基因算法、基本统计分析方法、贝叶斯 网络、支持向量机等。 2 ) 局部模型共享：信息通信与共享必要的其他信息。所有的局部模型通过 网络被传送到一个中心站点( 有些算法还要求传送部分具体数据作为验证数 据) ，并生成元数据( 所有的局部模型通过网络被传送到一个中心站点( 有些算法 还要求传送部分具体数据作为验证数据) ，并生成元数据。 1 2 灯一勉硝 也一”“m灿一“铋f 一躬聃烙一m”也一 “灿一躬档f 一”眄 第二章分布式数据挖掘相关知识综述 3 ) 全局模型集成，通过采用不同的集成机制，生成全局模型。 4 ) 基于分布式计算环境，在构建分布式数据挖掘系统构架的研究中，核心 内容是如何协调利用局部站点数据来构建全局模型，基于水平分布式数据的分类 和估值问题。主流的方案有三个，它们分别是充分统计学习方法【：s 】，抽样学习方 法【2 6 1 ，元学习方法1 6 ，2 7 , 2 9 。 5 ) 充分统计学习的统计量是数据的函数。函数就是一种浓缩信息的动作。 因此，统计量中所包含的信息，通常比整个样本数据所包含的来得少。例如样本 的顺序统计量只包含了有哪些值出现，而不同值出现的顺序这样的信息不见了。 6 ) 但统计量比样本原数据少掉的信息可能是无关紧要的，或者和我们要了 解的群体特性不相干，如上述数据出现顺序在很多时候和我们关心的群体特性无 关。统计量所包含关于群体特性的信息不比原样本数据少，就是充分统计且【拥。 对一数据集求得充分统计量的过程称为充分统计。 在分布式计算环境中，常用的方法是先求得局部站点数据的分布函数，通常 包括均值，方差等常用统计参数，也就是求得充分统计量 2 5 - 3 1 ，然后把局部充分 统计量通过网络传输到处理中心汇总，以支持全局模式的发现。 抽样学习方法，抽样是通过抽取总体中部分单元，收集这些单元的信息，用 来对作为整体的总体进行推断的手段。抽样有两种方法；非概率抽样和概率抽样 【3 2 】。使用哪种方法主要取决于我们是否打算对总体进行推断。 非概率抽样用主观的( 非随机的) 方法从总体中抽取单元，它是一种快速、 简易且省钱的抽样方法。但要能从样本对总体进行推算，必须假定样本对总体具 有代表性，而在非概率抽样情形做这样的假设将有很大风险。 概率抽样则是基于随机的原则从总体中抽取单元。与非概率抽样相比，概率 抽样较为复杂、费时、费用也较高，然而，由于单元是从总体中随机抽取出来的。 而且能计算每一个单元的入样概率，因此能得到可靠的估计值及其抽样误差的估 计值，并对总体进行推断。 在分布式计算环境中，对各分散站点数据进行抽样，然后把样本通过网络传 输到处理中心进行汇总，以支持全局模式的发现。 广东工业大学丁学硕 = 论文 第三章水平分布式数据背景异质性及其问题研究 3 1 背景异质性 数据背景异质性是分布式数据挖掘研究和应用的重要的课题之一，本论 文从背景异质性的定义，背景异质性对分类算法的影响两个方面来研究。 3 1 1 背景异质性的定义 在分布式的计算环境中，数据固有的分布式特性对数据挖掘技术提出了更高 的要求。为了清楚地说明问题，这里给出一个商业领域的分布式数据挖掘的例子。 如图3 1 所示，一个由多家超市组成的商业虚拟企业需要对其客户的具体数据 ( 包括客户i d 、性别s e x 、年龄a g e 、所花钱数d o l l a r 、购买次数o r d e r 、购买 商品件数i t e m 等信息) 进行挖掘和分析，建立具有全局意义的客户购买行为特 征模型( 高消费客户h b u y e r = f l s e x ，a g e ，d o l l a r , o r d e r , i t e m ) ) ，并用此模型对 客户进行分类( 是否为高消费客户) ，以便对不同类型的客户采取相