分布式环境下的数据挖掘算法的研究与实现.pdf

复旦大学
硕士学位论文
分布式环境下的数据挖掘算法的研究与实现
姓名:张世安
申请学位级别:硕士
专业:计算机软件与理论
指导教师:汪卫
20040519
摘要挖掘系统——系统,并使用系统对瓺惴ń辛似拦馈储,单台计算机的资源对于挖掘大规模数据集越来越无能为力,所以在分布式环我岢隽艘桓龇秩缡骄劾嗨惴℅.。狣惴ㄖ饕J窃诰狣惴ǖ玫饺ň帜P停⑹褂肎惴ǘ阅P兔枋鼋屑蚧W詈关键词:分粕式,网格,聚类挖掘,基于密度分类号:随着网络技术的发展和计算机使用的婀惴海缱踊菰嚼丛蕉啵嗣道路,并越来越受到人们的重视。但随着数据集规模越来越庞大,且多为分卸存境惺萃诰蛩惴ǖ难芯肯缘糜任V匾!对分布式算法的研究主要有两个途径,一个是改造现有的串行算法,使之适应分布式并行环境:另一个则是设计全新的分布式并行算法。由于前一种方法容易进行工作衔接,而且能够充分利用已有的集中式环境下的研究成果,所以被广典的基芏鹊腄惴ǖ幕∩辖懈慕模⒔岷狭丝占渚匦胃哺撬法。在各个局部节点,狣惴ㄓ肈惴ú植磕P停并使用算法对局部模型进行近似处理,以减少传输到中央节点的数据量。中央节点根据局部节点提交的局部模型,使用空间分格以及我们改进的将全局模型发送到各个局部节点以更新局部模型。另外,利用算法,我们还开发了一个网格环境下的分向式聚类【面佟笆莘岣欢J镀斗Α钡奈侍狻J萃诰蚣际跷=饩龃宋侍饪1倭艘惶泛采用。分布式环境下的数据挖掘算法的研究实现复口人学硕貉宦畚筇彻
坌塑些堕垫塑丝塑竺堕塑壅兰壅型塑炙苣琣珿琣瑃甌甀琒,保瓺..,.珿瓽·猙—,瑃狣,,,瓵.:珿珻珼复旦犬学硕士学位论文“.
第一章引言数据挖掘简介信息都以最原始的方式——数据的形式存在。如果数据可以看作是人们记录的事据库、面向对象的数据库、对象一关系数据库、空间数据库、文本数据库和多媒收集、数据清理、降维、规则规约、模式识别、数据结果分析及评估、可视化输出等多种过程于一身,是数据库技术、人工智能、机器学习、神经网络、统计学、的、新颖的、有潜在使用价值的、最终可理解的模式的非平凡的过程。它包括数据选取、数据预处理和数据清洗、数据挖掘、知识评估等多个步骤。数计算机和通讯技术的发展,使得我们这个社会越来越依赖信息,而大多数的着网络和存储技术的发展以及条形码在大部分商业产品中的广泛应用,商业公司和政府机构办公自动化逐步普及,数据采集工具迅速发展,这一切使得我们产生、收集和存储数据的能力已经迅速提高。这一切将我们淹没在数据的海洋中,而“丰富的数据与贫乏的知识”问题也嫱怀觥2煌煊虻娜嗣嵌计诖糯诱庑┦中得到自己想要的答案,将数据转化为信息,从数据的矿山中找到蕴涵的知识金钦庋恢执邮葜型诰蛐畔⒌墓ぞ撸模式识别、知识库系统、知识获取、信息检索、高性能计算和数据可视化相结合的产物。它出现于世纪年代后期,年代有了突飞猛进的发展,并可望在新年中继续繁荣。实际上,世界科笠抵械ザ忌孀闶萃诰虻那罢性研究或拥有一个或多个数据挖掘产品系统。它们帮助企业进行客,叵倒芾恚减少不必要的投资,提高资金周转和回报;帮助人们迅速获取所需的知识和信息,提高工作效率,改进服务质量。它让人们有能力最终认识数据的真正价值,即真正认识蕴藏在数据中的信息和知识,俊目前,对数据挖掘有广义的和狭义的两种理解。广义的理解认为数据挖掘即数据库中的知识发现,,即从大规模的数据库中抽取非平凡的、隐含的、未知的、有潜在使用价值的信息的过程。狭义的理解认为数据挖掘是囊桓霾街琛为从数据中识别正确据挖掘足其中对经过预处理的数据进行处理,抽取知识的过程。数据挖掘可以在众多的数据库上进行,包括关系数据库、数据仓库、事务数实,则信息就是数据中暗含的一组规则,或者况是期望。在过去的数十年中,随数据挖掘矿。复且大学硕士学位论文
夺概念描述卣髅枋龊颓数据可以由~‘定的概念和类来抽象表示人们对其关心的那部分性质。分别简窃谝桓龈ǖ氖菁蟹⑾志M狈⑸夺分类和预测性,如果用户可以接受,则用该模型对未知其类别的数据进行分类预测。所谓预欺诈检测中,例外却成为了最受关注的焦点。例外分析大致有统计、基于距离、夺趋势分析数据挖掘的任务一般可分为描述和预测两类,其中描述性数据挖掘任务刻划数据库中数据的‘一般特性,预测性数据挖掘任务在当前数据上进行推断,咀进行预测。而数据挖掘的功能指定了数据挖掘任务中要找的模式类型。:【校壳暗氖萃诰蚣际踔饕7为以下几类:概念描述、关联分析、分类和预测、聚类分析、例外分析、趋势分单明了地描述这些概念和类显然是非常有用的。关于这些概念的描述称为概念描夺关联分析的多个属性值条件愠莆9亓9嬖的过程,最常用于市场销售和事务数据分类是指为了能够使用模型预测类标签知的对象所属的类,而寻找可以描述和区分类或概念的模型的过程,其中类标签指用来区分类的属性。包括两个步骤:通过分析训练数据空间中的数据,运