数据算法（共12篇）
数据算法 篇1
摘要：关于磁盘阵列在线重构的研究一直以来都是国内外研究热点。提出面向数据重构算法。面向数据重构算法只对正被使用逻辑块上数据进行重构,而不需对整个磁盘进行数据重构。测试结果说明了面向数据重构算法相对于现有重构方法显著改善了磁盘阵列的重构性能。相对于DOR算法(现在最常用且最有效重构算法之一),面向数据重构算法将重构性能提高了1至2.2倍,并且没有降低重构过程中磁盘阵列服务性能。
关键词：磁盘阵列,在线重构,面向数据重构算法
0 引 言
关于磁盘阵列在线重构的研究一直以来都是国内外研究热点。本文提出了面向数据重构算法,面向数据重构算法只对正被使用逻辑块上数据进行重构,而不需对整个磁盘进行数据重构。面向数据重构算法相对于现有重构方法显著改善了磁盘阵列的重构性能,并且没有降低重构过程中磁盘阵列服务性能。
1 面向数据重构算法
对于磁盘阵列在线重构,国内外相关研究主要从spare布局[1]、数据布局[2]和重构策略[3,4]三个方面来加速磁盘阵列在线重构。但是,现有重构方法都需要对整个磁盘进行数据重构,而不能根据磁盘实际使用情况进行重构。因此,面向数据重构算法的核心思想就是:当磁盘阵列出现磁盘失效时,仅重构正被使用逻辑块上数据,即可将磁盘阵列恢复至正常运行状态。面向数据重构算法的最大优点为:能够将失效磁盘上数据按需重构至空闲盘上,从而缩短了重构时间,提高了磁盘阵列的可靠性和可用性。.
基于面向数据重构算法的核心思想,我们构建了面向数据的RAID架构,对面向磁盘重构算法(DOR)进行了改进,实现了面向数据重构算法(DataOR)。
1.1 面向数据的RAID架构
通过对传统RAID进行简单改进,我们实现了面向数据的RAID架构(见图1所示)。面向数据的RAID架构与传统RAID架构根本差异就是:面向数据的RAID中未被使用逻辑块上数据一定为零;我们使用一个全局位图记录磁盘阵列中所有逻辑块(数据块和校验块)的使用情况,并通过在传统RAID转发读写请求路径上添加访问位图接口,从而实现了面向数据的RAID架构。面向数据RAID必须按照条带分配和释放逻辑单元,以避免引起附加的读写操作。
图1描叙了面向数据RAID架构的实现机制,磁盘阵列RAID5由4块磁盘构成,每块磁盘由两个逻辑块组成;磁盘阵列RAID5由8个逻辑块构成,包括6个数据块和2个校验块;位图vd-bmp上每个位对应一个磁盘逻辑块,位图vd-bmp上第0、4位对应磁盘disk0上逻辑块d00和d01,位图vd-bmp上第1、5位对应磁盘disk1上逻辑块d10和d11,其余对应关系类推。如图1(a1)和(a2)所示,对逻辑块d10进行读取操作时,首先访问位图vd-bmp的第1位,该位为0,因此,逻辑块d10上数据为零,直接返回零;如图1(b1)和(b2)所示,对逻辑块d00进行读取操作时,首先访问位图vd-bmp的第0位,该位为1,因此,逻辑块d00上已存放数据,读请求被直接转发给磁盘disk0;如图1(a1)和(a2)所示,对逻辑块d00进行写操作时,将新数据和新校验数据分别写入逻辑块d00和p30之后,将位图vd-bmp第0位和第3位设为1;如图1(c1)和(c2)所示,由于按照条带分配和释放逻辑单元,直接将位图vd-bmp第0、1、2和3位都设为0。
1.2 面向数据重构算法的原型实现
在面向数据的RAID架构上,通过对面向磁盘重构算法(DOR)改进,实现了面向数据重构算法(DataOR)。以下详细阐述DataOR算法的关键点:
(1) 面向数据RAID维护了正被使用逻辑块的位置标识(全局位图)。根据全局位图和磁盘阵列基本信息,可以创建磁盘阵列内任一磁盘上正被使用逻辑块的位置标识。
(2) 磁盘阵列发生磁盘失效时,创建失效磁盘上需要进行重构数据的位置标识(版本数据位图),以及初始状态为零的辅助位图。
(3) 通过版本数据位图和辅助位图相互协作,从而完成重构过程,使得磁盘阵列恢复到正常运行状态。
通过版本数据位图和辅助位图相互合作,重构管理构件实现了按需重构功能。版本数据位图为正被使用逻辑块的位置标识,辅助位图上所有位初始为0,两个位图上每一位与磁盘上4KB逻辑块一一对应。通过版本数据位图和辅助位图之间合作,可以判断逻辑块上数据是否有效。磁盘逻辑块上数据被定义了两种状态:
VALID—如果版本数据位图上某位为0或者辅助位图上某位为1,所对应逻辑块上数据则有效。
INVALID—如果版本数据位图上某位为1且辅助位图上相应位为0,所对应逻辑块上数据则无效,即逻辑块上数据必须重构。
在重构阶段,版本数据位图和辅助位图协作过程如下:
(1) 根据版本数据位图和辅助位图,顺序发出对于无效数据块的重构请求。当所计算出的数据被写入空闲盘之后,则将辅助位图上相应位设为1,从而标识逻辑块上数据已经有效。
(2) 用户读请求访问spare磁盘时,被访问逻辑块上数据有效,则直接访问spare磁盘;否则,通过同一条带上其它数据块构建出被访问的数据块,并写入spare磁盘,同时,将辅助位图上相应位设为1,从而标识被访问逻辑块上数据已经有效。
(3) 用户写请求访问spare磁盘时,将版本数据位图上相应位设为1,并直接将写请求发送给spare磁盘;写请求完成之后,则将辅助位图上相应位设为1,标识被访问逻辑块上数据已经有效。
2 性能分析
本节主要以面向磁盘重构算法作为参照,对面向数据重构算法进行性能分析。为了方便描述,面向磁盘重构算法简称为DOR,面向数据重构算法简称为DataOR。
本节的测试配置详细情况如下所述。服务器配置如下:Intel(R) Xeon(TM) CPU 2.40GHz,2GB内存,操作系统为32位的Fedora Core4,采用2.6.12-gentoo-r12内核,采用软RAID构成RAID5。RAID5基本属性如下设置:chunk大小为64KB,左对称算法,由9块磁盘构成,第3块磁盘失效。应用模式分别为:cello99(12-25、03-11、06-24、09-22和10-05)、F2.spc、F1.spc和tpcc94应用模式;对于cello99、F2.spc、F1.spc和tpcc94这四种应用模式,RAID5单块磁盘容量分别设为92GB、37GB、31GB和11GB。
图2描述了DataOR(RAID5)重构性能与DOR对比情况,相对于DOR,DataOR显著提高了重构性能。如图2所示,对于cello99应用模式,DataOR重构性能相对于DOR提高了1.7至2.2倍,对于F2.spc、F1.spc和tpcc94三种应用模式,DataOR重构性能相对于DOR提高了1倍左右。相对于DOR,DataOR重构性能得以显著提高的主要原因是重构数据量仅占磁盘实际分配空间的一部分。对于cello99应用模式,实际数据总量占磁盘实际分配空间的31%,对于F2.spc、F1.spc和tpcc94三种应用模式,实际数据总量占磁盘实际分配空间的47%至50%。
当实际存储容量远大于实际分配空间时,DataOR相对于DOR对重构性能有巨大改善。
3 结 语
本文介绍了面向数据重构算法的核心思想和实现机制。面向数据重构算法只对正被使用逻辑块上数据进行重构,而不需对整个磁盘进行数据重构。
测试结果说明了面向数据重构算法显著改善了磁盘阵列的重构性能和服务性能。磁盘阵列存储空间仅满足实际需求时,相对于DOR算法(目前最常用且最有效算法之一),面向数据重构算法将重构性能提高了1至2.2倍,并且没有降低重构过程中磁盘阵列服务性能。由于在更短时间将磁盘阵列恢复到正常运行状态,面向数据重构算法显著改善了磁盘阵列的服务性能。当磁盘阵列存储空间远大于实际分配空间时,面向数据重构算法对重构性能改善巨大。
参考文献
[1]Reddy A N N,Chandy J,Banerjee P.Design and Evaluation of Grace-fully Degradable Disk Arrays[J].Journal of Parallel and DistributedComputing,1993,17:28-40.
[2] Muntz R,Lui J.Performance Analysis of Disk Arrays Under Failure[C]//Proceedings of the 16th International Conference on Very Large Data Bases,1990,3:162-173.
[3]Fu Gang,Thomasian A,Han Chunqi,et al.Rebuild Strategies for Re-dundant Disk Arrays[C]//The Twelfth Conference on Mass StorageSystems and Technologies,2004,2:128-139.
[4]Lei Tian,Dan Feng,Hong Jiang,et al.PRO:A Popularity-based Multi-threaded Reconstruction Optimization for RAID-Structured Storage Sys-tems[C]//5th USENIX Conference on File and Storage Technologies,2007,5:89-103.
数据算法 篇2
100401200510计本（4）班章兴春
本学期所学习的《数据结构与算法》课程已经告一段落，就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。以便在所学习知识有更深刻的认识。
一、《数据结构与算法》知识点：
学习数据结构之前、一直以为数据结构是一门新的语言、后来才知道学习数据结构是为了更加高效的的组织数据、设计出良好的算法，而算法则是一个程序的灵魂。经过了一学期的数据结构了，在期末之际对其进行总结。首先，学完数据结构我们应该知道数据结构讲的是什么，数据结构课程主要是研究非数值计算的研究的程序设计问题中所出现的计算机处理对象以及它们之间关系和操作的学科。
第一章主要介绍了相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。
第二章具体地介绍了顺序表的定义、特点及其主要操作，如查找、插入和删除的实现。需要掌握对它们的性能估计。包括查找算法的平均查找长度，插入与删除算法中的对象平均移动次数。
链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。
第三章介绍了堆栈与队列这两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。算法上要求掌握进栈、退栈、取栈顶元素、判栈空盒置空栈等五种操作及掌握使用元素个数计数器及少用一个元素空间来区分队列空、队列满的方法。
第四章串和数组中，我们知道串是一种特殊的线性表，是由零个或多个任意字符组成的字符序列。串的储存结构分为紧缩模式和非紧缩模式。
基本运算需掌握求串长、串赋值、连接操作、求子串、串比较、串定位、串插入、串删除、串替换等。
第五章二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序。
树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。
第六章介绍了图的概念及其应用，图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。
最后两章集体说明了查找和排序算法，查找教材上介绍了静态查找表和哈希查找表，静态查找表中介绍了顺序查找、折半查找以及分块查找。哈希法中，学习要点包括哈希函数的比较；解决地址冲突的线性探查法的运用，平均探查次数；解决地址冲突的二次哈希法的运用。
排序是使用最频繁的一类算法，可分为内部排序和外部排序。主要需要理解排序的基本概念，在算法上、需要掌握插入排序（包括直接插入排序算法、折半插入排序算法），交换排序（包括冒泡排序算法、快速排序递归算法）,选择排序（包括直接选择排序算法、堆排序算法）等。
二、对各知识点的掌握情况
总体来看，对教材中的知识点理解较为完善，但各个章节均出现有个别知识点较为陌生的现象。现将各个章节出现的知识点理解情况列举如下。
第一章中我对数据和数据结构的概念理解较为透彻，熟悉数据结构的逻辑结构和存储结构。而对算法的时间、空间性能分析较为模糊，尤其是空间性能分析需要加强。
第二章，顺序表的概念、生成算法理解较为清晰，并且熟悉简单顺序查找和二分查找，对分块查找较为含糊；排序问题中，由于冒泡排序在大一C语言课上已经学习过，再来学习感觉很轻松。对插入排序和选择排序理解良好，但是，在实际运用中仍然出现明显不熟练的现象。由于在归并排序学习中感觉较吃力，现在对这种排序方法仍然非常模糊，所以需要花较多的时间来补习。此外串的模式匹配也是较难理解的一个地方。
链表这一章中，除对双向循环链表这一知识点理解困难之外，其他的知识点像单链表的建立和基本算法等都较为熟悉。
接下来的有关堆栈以及队列的知识点比较少，除有关算法较为特殊以外，其余算法都是先前学过的顺序表和链表的知识，加上思想上较为重视，因此这部分内容是我对全书掌握最好的一部分。不足之处仍然表现在算法的性能分析上。
在学习第六章时感觉较为吃力的部分在于矩阵的应用上，尤其对矩阵转置算法的C语言描述不太理解。稀疏矩阵相加算法中，用三元组表实现比较容易理解，对十字链表进行矩阵相加的方法较为陌生。
第七章是全书的重点，却也有一些内容没有完全理解。在第一节基本概念中，二叉树的性质容易懂却很难记忆。对二叉树的存储结构和遍历算法这部分内容掌握较好，能够熟练运用，而对于二叉树应用中的哈弗曼树却比较陌生。
第八章内容较少，牵涉到所学的队列的有关内容，总体来说理解上没有什么困难，问题依旧出现在算法的性能分析上。
散列结构这一章理解比较完善的知识点有：基本概念和存储结构。散列函数中直接定址法和除留余数法学得比较扎实，对数字分析法等方法则感觉较为陌生。对两种冲突处理的算法思想的理解良好，问题在于用C语言描述上。
最后一章，图及其应用中，图的定义、基本运算如图的生成等起初理解有困难，但随着学习深入，对它的概念也逐步明朗起来。邻接矩阵、邻接表和逆邻接表掌握较好，而对十字链表和邻接多重表则较为陌生。感觉理解较为吃力的内容还有图的遍历（包括深度和广度优先遍历），最小生成树问题也是比较陌生的知识点。最短路径和AOV网学习起来感觉比较轻松，而对于C语言描述却又不大明白。
由于平时上机练习的少，对于教材中很多算法都掌握的不是很熟悉、不过这些都是可以弥补的，我会在剩下的时间中不断练习书上给出的算法和练习，正如教材上说的，学习数据结构，仅从书本上学习是不够的，必须经过大量的程序设计实践，在实践中体会构造性思维方法，掌握数据组织与程序设计技术。
三、学习体会：
多做实验！这个就没有太多理由了，我一直觉得编程是一门熟练科学，多编程，水平肯定会提高，最重要的是能够养成一种感觉，就是对程序对算法的敏感，为什么那些牛人看一个算法一下子就看懂了？而自己要看很久才能弄懂，而且弄懂了过了一阵子又忘记了？其实这个是因为牛人们以前看的程序很多，编得也很多，所以他们有了那种感觉，所以我觉得大家应该多看程序，多写程序，培养自己的感觉。
复习和考试的技巧，我想大家应该都有这样的感觉，就是觉得自己什么都掌握了，但是在考试的时候就是会犯晕，有时候一出考场就知道错在哪个了，然后考完以后一对答案，发现其实考得很简单，应该都是自己会做的，这个就是与自己的复习和考试的技巧有关系了。
首先就是复习，前面已经说过其实我们学的算法也就是几十个，那么我们的任务也就是理解这几十个算法，复习也就是要加深你的理解。如何理解算法，然后理解到什么程度呢？ 是能默出整个算法吗？其实不是这样的，数据结构的考试有它的特点，考过程考试了，大家应该都发现数据结构其实不要求你把整个算法背出来，它注重考察你的理解，那么怎么考察呢？其实也就是两种方式吧，一种就是用实例，就是给你一个例子，要你用某个算法运行出结果，我想这个期末考试的时候仍然会有很多这样的题目，比如排序那块就很好出这样的题目，要复习这种题目我觉得很简单，就是每个算法都自己用例子去实践一下，以不变应万变，我期中复习的时候就是这样去做的，而且考试之前我就觉得那个并查集的题目就很有可能会考，于是就自己出了几个例子，做了一下。另外一种考察方式就是算法填空和算法改错，可能有一些同学觉得这种题目很难，其实我们首先可以确定这两种题目肯定是与书上算法有关系的，只要理解了书上的算法就可以了，有人觉得看完书以后什么都懂了，而且要默也默得出来，其实不是这样的，算法改错和填空主要是考察的细微处，虽然你觉得你默得出来，那是能够默出算法的主体部分，很多细微的地方你就会很容易忽略。我想大家考过期中考以后应该都有这种感觉吧？那要怎样解决这种问题呢？ 我觉得有两种方法，一种就是自己去编程实现，这种方法比较有意义，还能够提高编程水平，另外一种就是用实例分析算法的每句话，我认为这种方法是最有效的。
然后还有一种题目，就是最后的写算法的题目，我觉得这种题目还是很好解决的，只要是能够自己做出作业的，基本上都会很容易做出来，这也是为什么我前面觉得平时做作业应该自己独立思考的原因，同时做这种题目千万要小心，尤其是题目简单的时候，那肯定会有一些小地方要考虑清楚，一不小心就会被扣掉很多分，这样很不值。
我觉得考试的时候没有太多要讲的，只要复习好了，考试的时候细心一点就可以了，然后就是做一个题目开始就要尽量保证正确，如果觉得留在那里等后面做完了再来检查，这样错误还是很有可能检查不出来，我期中考试的时候就基本上没有检查，因为我做每个题目都是确保正确，用的时间也挺多的，然后也觉得没有检查的必要了。
三、对《数据结构与算法》课程教学的建议
1、建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生保持良好的精神状态。
2、建议在课时允许的情况下，增加习题课的分量，通过课堂的习题讲解，加深对知识点的掌握，同时对各知识点的运用有一个更为直观和具体的认识。
3、要更加重视实验的重要性。
数据库检索算法研究 篇3
关键词：数据库；检索；算法
中图分类号：TP391
数据库的检索效率在数据库管理系统中一直是需要不断优化的方向，而一个良好的数据库检索算法则对数据库的检索效率起着至关重要的作用。目前，对于各种类型的数据库有不同的检索算法。
其中，小型数据库有XML型数据库，由于XML数据库的嵌套结构均可以使用树型结构的数据模型来表示，对于这种XML检索树，目前广泛采用小枝模式对数据库进行检索；对于海量的数据库，由于其数据量较大，数据库检索时的读取、检索等使用一般的算法效率通常非常低，目前针对这种数据库的特点，结合目前比较热门的云计算技术，发展出一种针对大数据的基于云计算的数据库检索算法；对于分布式数据库的检索，对于整个分布式数据库系统的可用性、可扩展性以及提高分布式数据库的使用效率和可靠性的作用是不可估量的，对于分布式数据库，经常采用基于多关系半连接的检索算法；对于目前数据库技术和网格技术的一种结合，网格数据库也是一种新的数据库应用，为了对网络上的海量数据库资源进行高效的检索，通常采用的是基于启发函数的数据库检索算法。
1 基于小枝模式的数据库检索算法
XML目前已成为互联网上的一种数据交互的标准，而对于XML文档的嵌套结构的特点，XML文档常用树型结构的数据模型表示，叫做XML文档树，也叫做XML检索树。XML文档使用文档树表示后，XML查询表达式可以使用查询树表示。将查询语言表达式转换为查询树的方法是将表达式的元素、属性和文本用节点表示。它们之间的父子关系用单斜线边（/）连接，祖先后代关系用双斜线边（//）连接。当查询树中有多个分支时，称为小技模式查询。
小枝模式检索最常用的方法是将XML检索树分解为多个二元结构的父/子或祖先/后代关系，然后在XML文档树中进行匹配，最后采用结构连接算法来对结果进行合并。使用这种方法的不足之处是在检索的过程中会产生大量的中间结果，而这些中间结果中的一部分对最终的小枝模式查询没有什么贡献。
针对小枝模式检索的特点，需要对小枝模式检索进行整体的考虑。在小枝模式检索的基础上衍生出两种优化的小枝模式检索算法：路径栈算法（PathStack算法）和小枝栈算法（TwigStack算法）。这两个算法先通过索引结构，将参与查询的每个元素按照其先序遍历的顺序进行存储。然后顺序扫描一次这些参与连接的元素列表，通过维护多个节点栈，实现小枝模式查询。PathStack算法需要将小枝模式分解为多个路径模式，然后对查询结果进行合并，查询过程中也会产生一些中间结果；TwigStack算法对小枝模式整体考虑，保证找到小枝模式的根节点后才进行入栈操作。
后来又在TwigStack算法的基础上，对小枝模式中含有“包含关系”的结构连接问题进行研究，提出了一般性的整体小枝连接算法（TSGeneric算法，TSGeneric算法可以通过索引，尽可能多地跳过不参与祖先/后代连接的元索，优化了小枝检索模式的效率。
2 基于云计算的数据库检索算法
对于海量的数库的检索，单机查询效率往往不尽如人意。通常与目前比较热门的云计算技术结合，但是云计算由于其特点，数据库检索需要一个良好的检索调度算法。研究表明，将连续读取的特性应用到基于云计算的数据库检索调度算法中，即对数据库中要检索的数据可以重组出某些连续关系使之具有连续读取特性，然后将此连续的特性利用到数据存储器上，这种连续的存储方式可以大大提高云计算数据的随机读速率，缩短检索的执行时间，可以大幅度提高系统的性能。目前应用到云计算数据库检索调度的算法有两种：即批处理调度算法与基于计划的调度算法。批处理调度算法重复考虑到内存与I/O的有效运用，使相关的检索操作尽量以批量一次性执行完毕，这样可减少大量的不必要的I/O。但该调度对最大平行度与平衡负载的考虑不够周全，因此可能出现选取的查询仅仅局限于部分节点执行，而对另外部分资源闲置造成节点有不平衡负载的情况。另外一种调度算法是基于计划的调度算法，主要思想是是将现有空闲节点计划检索调度，在有足够可用检索节点的情况下可执行数据库检索，若多个查询同时拥有所需节点，则它们可同时执行。它发展出最大适应优先算法（Largest-Fit-First算法，简称LFF）和最先适应优先算法（First-Fit-First算法，简称FFF）两种算法。LFF将待执行检索的数据库按所需节点数目按照降序排列，使用节点较多的检索会优先处理；而FFF算法按照先进先出原则，对最先进入系统的检索优先处理。
3 多关系半连接数据库检索算法
分布式数据库管理系统的性能最关键的决定因素取决于分布式数据库检索算法，因此对于分布式数据库检索处理和优化对整个使用分布式数据库的应用系统数据的可用性、可扩展性、提高分布式数据库的使用效率和可靠性起着不可估量的作用。分布式数据库检索通常采用的是基于多关系半连接的数据库检索算法。由于半连接操作可以充分减小数据库连接时的关系元组，因而可以有效地减少分布式数据库站点间数据的传输量。但是半连接也有可能导致通信次数的大量增加与本地处理时间的延长等不良影响。并且半连接操作会经过两次关系的传递，每次传递到不同的节点后又会执行连接操作，这使得本地的处理时间又延长了。因此可以得到普通半连接检索算法的特点：是按照关系间的连接顺序来执行半连接的，具有处理简单、速度快的优点，但是由于没有考虑对子查询的半连接优化，造成网络通信代价较高。基于上述半连接算法的不足，发展出一种基于多关系的半连接数据库检索算法，该算法解决了执行子查询的中间结果的数据通信造成网络资源的消耗的问题，还定义了确定多关系半连接检索算法的优化函数。实验表明在分布式数据库检索算法中，与普通的半连接算法相比，多关系半连接数据库检索算法的效率更高。使用基于多关系半连接的检索优化算法，使得中间结果数据量和网络通信总代价大大地降低。通过实验表明，在分布式数据库的检索优化中，基于多关系的半连接检索算法比普通的半连接检索算法具有更高的检索效率。
4 网格数据库检索算法
网格数据库，是将网格技术与数据库技术相结合的新兴产物。其主要用于有效地对网络上大量的数据资源进行管理，目的是为用户提供一个可以统一化访问的接口。网格数据库系统最重要的应用是用来接收用户的数据检索，并且对检索数据进行优化，并将优化后的检索数据发送到各个网格节点上并行执行，将最终结果返回给用户。网格数据库检索主要用到了数据库副本技术，数据库副本技术主要包含副本创建与迁移、副本的一致性维护以及基于副本的查询处理技术。目前网格数据库检索算法主要有启发函数检索算法，是一种基于缓存的查询处理的检索模型，在此模型上设计一个启发函数，并充分考虑到网格节点负载能力。网格数据库检索的处理框架自上到下由用户接口层、中间协调层与网格执行层三部分组成。用户接口层用于响应用户提交的检索请求，将检索请求交给中间协调层来处理，中间协调层在接收到用户接口层提交的检索请求后，会调用自身的编译解释权对检索信息进行解析和优化，转化为内部统一检索形式，由中间协调层按照一定算法将检索任务分解为多个子任务，并分发到每个网格执行层的网格节点去执行检索。最后对对每个子任务的检索结果进行合并处理，并返回给用户接口层。
5 总结
综上看来，各种数据库都各自有不同的数据库检索算法，目前各种数据库检索算法较多，选择合适的数据库及对应的算法对提高检索速度，优化检索结果有非常重要的意义。
参考文献：
[1]李建中.并行数据操作算法和查询优化技术[J].软件学报，1994，5（10）：11-23.
[2]李建中.基于多重加权树的并行数据库查询优化方法[J].计算机学报，1998，21（5）.
[3]金胜华.基于启发函数的网格数据库查询算法[J].四川理工学院学报（自然科学版），2011，24（6）.
[3]杨一展.一种基于数据库查询的改进的决策树算法[J].计算机工程与应用，2008，44（15）.
作者简介：王文宜，女，山东青岛人，实验师，硕士，研究方向：数据库。
数据算法 篇4
鉴于大数据的海量, 复杂多样, 信息的维度多, 颗粒度细, 信息更非结构化等特性, 使得大数据环境的构建颇为复杂。大数据时代数据的收集问题不再成为我们的困扰, 采集全量的数据成为现实。全量数据带给我们视角上的宏观与高远, 这将使我们可以站在更高的层级全貌看待问题, 看见曾经被淹没的数据价值, 发现藏匿在整体中有趣的细节。因为拥有全部或几乎全部的数据, 就能使我们获得从不同的角度更细致更全面的观察研究数据的可能性, 从而使得大数据的分析过程成为惊喜的发现过程和问题域的拓展过程。很多人自始至终都认为数据是越多越好, 那么理想中的大数据是更多的数据, 还是由各种算法构成智能处理技术。
大数据的理想形态是不用构建算法模型, 也可以说已经构建了完整的统计模型, 不用根据具体的问题再单独建立模型, 数据自身会从数据特性, 规律去进行统计分析, 人们只需要将所有数据输入, 计算机就能利用完整的统计模型, 决策出哪些数据适用哪个模型, 解决了哪些数据的问题。最后大数据的输出成果将不是一份报告, 而是一个完整的体系, 给出了在各种条件下的结论的体系。这个体系没有一份报告能容纳如此多的结果。大数据给出的体系具有普遍性, 客观性, 解决了人们片面的使用数学模型, 得出片面结果的问题。
当然, 这是一种理想的智能环境模式。智能环境的理想状态就是, 计算机能够自己的进行推理, 能够自适应数据的维度、结构。到了那个时候, 更多的数据将胜过更好的算法, 因为那时候已经没有了算法, 没有什么是不能计算的。
但现实是, 我们目前的大数据离理想中的大数据形态还有很远的距离。首先, 模型本身就是大数据的一部分, 各种不同模型都有各自的适用范围;其次, 已有的模型可能不适合新的数据, 那么就要构建新的模型, 这都给大数据环境的架构带来很大的困难。
数据分析员总是习惯带着预先设定的结论去分析, 这是统计学随机样本检测的特点, 随机样本带给我们的只能是事先预设问题的答案。他们会不自觉地以对自己有利的方式对这些数据进行分析和解释, 即使这些方式很可能与这些数据所代表的客观现实不相吻合。出于各种原因, 数据分析员很难从干扰他们的噪声中分辨出有用的信号, 甚至会无视这些真实有用的信号。
于是, 数据展示给他们的通常都是他们想要的结果, 而且他们通常也能确保这些数据令大家皆大欢喜。同时, 我们有时天真的相信各种预测分析模型, 却没有人认真地去验证这些模型是否科学合理, 是否与事实相符, 也许这些模型在进行架设选择时根本不堪一击。这种缺乏延展性的结果, 无疑会使我们错失更多的问题域。
大数据时代, 算法不再受限于传统的思维模式和先验的假定, 数据会为我们呈现出新的深刻洞见和释放出巨大的价值, 只有更好的使数据和算法融合, 才能在随时接收着来自数据的同时做出快速的决策, 这样效率会大大提升, 大数据的价值也正是在于将及时的信息及时的传递给需要的人手中并及时的做出决策。
笔者认为数据只是基础, 而更多的是如何建构起有效的算法、模型, 这比数据本身更重要, 网络中有时更多的数据意味着更多的噪声。信号是真相, 噪声却使我们离真相越来越远。
目前的大数据与理想中的大数据形态的距离并不在于数据源的多少上, 数据源从来不是问题, 问题是在于我们如何去构建一个科学合理的分析模型, 并坚信分析模式的输出结果。通过不断地修正、累积各种正确的分析模型, 我们将不断接近理想形态。
我们以为自己需要更多的信息, 但其实我们真正需要的是知识, 需要的是更多的解决问题的模型。所以, 大数据是一种理想的智能环境, 目前我们只是站在一个很长过程的起点上。
参考文献
[1]Big data[EB/OL].[2012-10-02].http://en.wikipedia.org/wiki/Big_data.
[2]王元卓, 靳小龙, 程学旗.网络大数据:现状与展望.计算机学报, 2013 (6) :1125-1138.
算法与数据结构实验册 篇5
学 生 实 验 报 告 册
课程名称：
学生学号：
所属院部：
（理工类）
算法与数据结构 专业班级： 14计单（2）
1413201007 学生姓名： 毛卓
计算机工程学院 指导教师： 章海鸥 16 ——20 17 学年 第 二 学期
金陵科技学院教务处制
金陵科技学院实验报告
实验报告书写要求
实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。
实验报告书写说明
实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。
填写注意事项
（1）细致观察，及时、准确、如实记录。（2）准确说明，层次清晰。
（3）尽量采用专用术语来说明事物。
（4）外文、符号、公式要准确，应使用统一规定的名词和符号。（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。
实验报告批改说明
实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。
实验报告装订要求
实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。
金陵科技学院实验报告
实验项目名称： 顺序表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间：
金陵科技学院实验报告
实验1 顺序表
一、实验目的和要求
掌握顺序表的定位、插入、删除等操作。
二、实验仪器和设备
VC6.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。
（2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。（3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。
解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。
（4）删除顺序表中所有等于X的数据元素。
2、选做题
（5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。
程序清单：
（1）:/*编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。*/ #include
金陵科技学院实验报告
}sequenlist;void main(){ sequenlist L;int i,n;printf(“请输入元素个数：”);scanf(“%d”,&n);printf(“n请输入元素：”);for(i=0;i 如果不存在，返回－1。*/ #include int fun(sequenlist L,int x,int n){ 金陵科技学院实验报告 } int i;for(i=0;i } int i,n,y;int x; printf(“请输入元素个数：”);scanf(“%d”,&n);printf(“n请输入元素：”);for(i=0;i printf(“n请输入要查找的数据元素：”);scanf(“%d”,&x);y=fun(L,x,n);if(y==-1)else printf(“n数据元素 %d 所在的位置为 %d n”,x,y);printf(“n所要查找的数据元素不存在。n”);(3): /*在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作； 从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置； 金陵科技学院实验报告 然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。*/ #define maxsize 100 typedef struct{ int data[maxsize]; int last;}sequenlist;main(){ int i,x,j; sequenlist l={{1,3,5,6,7,9},5}; printf(“n插入元素前的数据为:”); for(i=0;i<=l.last;i++) printf(“%2d”,l.data[i]); printf(“n请输入要插入的元素:”); scanf(“%d”,&x); for(i=1;i<=l.last;i++) if(l.data[i-1]>x)break; if(i>l.last) { l.data [l.last +1]=x; } else { for(j=l.last;j>=i-1;j--)l.data[j+1]=l.data[j];l.data[i-1]=x; } l.last++; printf(“插入元素后的数据为:n”); 金陵科技学院实验报告 for(j=0;j<=l.last;j++) printf(“%3d”,l.data[j]); printf(“n”);}(4): /*删除顺序表中所有等于X的数据元素。*/ #define maxsize 100 typedef struct{ int data[maxsize]; int last;}sequenlist;main(){ int i,j,x=0,k=0; sequenlist L={{1,3,5,7,2,4,6,8,2,9},9}; printf(“n原数据为:”); for(i=0;i<=L.last;i++)printf(“%3d”,L.data[i]); printf(“n请输入要删除的数据:”); scanf(“%d”,&x); for(i=1;i<=L.last+1;i++) if(L.data[i-1]==x){ for(j=i;j<=L.last+1;j++)L.data[j-1]=L.data[j]; L.last--; i--; k=1; } if(k==1){ printf(“删除后的数据为:n”); for(j=0;j<=L.last;j++)printf(“%3d”,L.data[j]); } else printf(“Not found!n”); 金陵科技学院实验报告 printf(“n”);} 四、实验结果与分析（程序运行结果及其分析）（1）结果： 请输入元素个数：5 请输入元素：1 2 3 4 5 元素输出：1 2 3 4 5（2）结果： 请输入元素个数：5 请输入元素：1 2 3 4 5 请输入要查找的数据元素：5 数据元素5所在的位置为 4（3）结果：插入数据前的元素为：1 3 5 6 7 9 请输入要插入的元素为：10 插入元素后的数据为: 5 6 7 9 10（4）结果：原数据为：1 3 5 7 2 4 6 8 2 9 请输入要删除的数据为：7 删除后的数据为： 3 5 2 4 6 8 2 9 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 单链表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验2 单链表 一、实验目的和要求 1、实验目的 掌握单链表的定位、插入、删除等操作。 2、实验要求 （1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。 （2）链表不能实现直接定位，一定注意指针的保存，防止丢失。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2）在递增有序的单链表中插入一个新结点x，保持单链表的有序性。 解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。 （3）编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。 2、选做题 已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。程序清单： 金陵科技学院实验报告 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 堆栈和队列 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验3 堆栈和队列 一、实验目的和要求 （1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。 （3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）判断一个算术表达式中开括号和闭括号是否配对。（2）测试“汉诺塔”问题。 （3）假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。 2、选做题 在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 串 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验4 串 一、实验目的和要求 掌握串的存储及应用。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。 （2）编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。 解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。（3）设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。 2、选做题 假设以链结构表示串，编写算法实现将串S插入到串T中某个字符之后，若串T中不存在这个字符，则将串S联接在串T的末尾。 提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 二叉树 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验5 二叉树 一、实验目的和要求 （1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。 （2）在第一题基础上，求二叉树中叶结点的个数。（3）在第一题基础上，求二叉树中结点总数。（4）在第一题基础上，求二叉树的深度。 2、选做题 已知一棵完全二叉树存于顺序表sa中，sa.elem[1…sa.last]存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。 解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 图 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验6 图 一、实验目的和要求 （1）熟练掌握图的基本概念、构造及其存储结构。 （2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）构造一个无向图（用邻接矩阵表示存储结构）。 （2）对上面所构造的无向图，进行深度优先遍历和广度优先遍历，输出遍历序列。 2、选做题 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。简单路径是指其顶点序列中不含有重复顶点的路径。提示：两个顶点及k值均作为参数给出。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 排序 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验7 排序 一、实验目的和要求 （1）熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的基本概念。 （2）掌握以上各种排序的算法。区分以上不同排序的优、缺点。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 用随机数产生100000个待排序数据元素的关键字值。测试下列各排序函数的机器实际执行时间（至少测试两个）：直接插入排序、希尔排序（增量为4，2，1）、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序和基于链式队列的基数排序。 2、选做题 假设含n个记录的序列中，其所有关键字为值介于v和w之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v…w]，令number[i]统计关键字为整数i的纪录个数，然后按number重排序列以达到有序。试编写算法实现上述排序方法，并讨论此种方法的优缺点。程序清单： 金陵科技学院实验报告 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 查找 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验8 查找 一、实验目的和要求 （1）掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。（2）掌握哈希表设计。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）在一个递增有序的线性表中利用二分查找法查找数据元素X。 2、选做题 （2）构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。 提示：构造哈希表只是完成查找的第一步，大家应该掌握在哈希表上进行查找的过程，可以试着编程序实现。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 【关键词】海量数据 MapReduce算法 hash 一、背景以及现状 随着互联网的发展，在许多科学领域，信息数量呈指数型增长。截止到2011年全球信息总量为1.8ZB[1]。海量数据的时代已经来临，然而面对海量数据该如何存储，如何有效的处理，及时有效的处理了这些数据对于各行各业乃至整个社会的发展有着重要的意义。过去的几年里单机的性能得到发展，硬件也得到发展。但在理论上这些硬件技术的发展是有限的。现今的多核技术就是并行技术发展的一个实例[2]。 二、MapReduce的技术特征 1）横向扩展与纵向扩展。对于MapReduce集群的构建采用低廉且容易扩展的低端商用服务器，考虑到大量数据存储的需要，基于低端服务器的集群远比基于高端服务器的集群优越，所以基于低端服务器实现都会使用MapReduce并行计算集群。 2）失效与常态。相对低端的服务器适用于MapReduce集群，无论哪个节点失效，其他的节点要无缝接管着失效节点的计算任务；当该节点恢复以后将不需要人工配置而是能自动无缝加入集群。 3）处理向数据迁移。MapReduce采取数据与代码互定位的技术时，计算节点首先计算其本地存储的数据并对其负责使数据发挥本地化的特点。 三、对MapReduce改进 （一）预处理算法 大量事实证明，在数据挖掘中整个工作量的60%到80%都是数据预处理[3]。通过数据预处理工作可以使残缺的数据变得完整，能达到数据类型相同化、数据格式的一致化、数据存储集中化和数据信息精练化[4]。采用Hash算法，间接取余法。公式：f（x）：= x mod maxM ； maxM一般是不太接近 2^t 的一个质数。得余数x，根据x对源数据进行预处理分配，采用Hash取模进行等价映射。 （二）分布缓存 对由N台缓存服务器组成的集群缓存把集群依次编号为0 - （N-1）。 1）hash机器节点。首先求出机器节点处的hash值，然后把它分布到0～2^32的一个圆环上（顺时针分布）。如图3-1，集群中有ABCDE五台机器，通过hash算法把它们分布到如图3-1所示的环上。 2）访问方式。写入缓存的请求，Key值为K计算器hash值为hash（K），Hash（K）对应着图3-1环中的某一个点。若该点没有对应映射到具体的某个机器节点上，就进行顺时针查找直到找到确定的目标节点，也就是首次有映射机器的节点。Hash（K）的值介于A～B之间时，那么它命中的机器节点应当就是图3-1中的B节点。 3）增加节点的处理。如图3-1中如果在原有集群的基础上想再增加一台机器F，过程如下，首先要计算机器节点的Hash值，找到环中的一个节点，把机器映射上，如图3-2所示。在增加机器节点F以后访问策略不发生改变，按2）中的方式继续访问，那么此时仍然是不可避免的是缓存不命中的情况，hash（K）在增加节点之前不能命中的数据是落在C～F之间的数据。hash它使用了虚拟节点的思想，在圆上分配了100～200个点为其中的每一个物理节点，这样就能较好的抑制了分布的不均匀的情况，还能最大限度减小当服务器增减时缓存的重新分布。 {三}复用中间结果 在对海量数据进行了预处理和分布式缓存之后，采用简单随机取样[5]的方法对缓存好的数据进行随机取样具体实现该方法。 四、实验 本论文的实验可以对是某地区房价数据进行处理，简要的过程如下： 第一数据预处理阶段，首先让每一组数据分别自动编号，然后采用取余的方法。第二根据分组情况，分别把各组数据放置到不同的服务器上。第三采用简单随机取样的方法对缓存好的数据进行随机取样，选择出最适合的房产。 五、结束语 本文在算法方面也还有一些不足之处，有待深入的分析。目前海量数据的处理还有很多值得深入研究和挖掘的地方，还将会是热门的话题以及更多专家学者热衷研究的方向。 【参考文献】 [1] John Gantz， David Reinsel .The 2011 Digital Universe study： Extracting Value from Chaos [J]. International Data Corporation （IDC）， 2011 [2]陈康，郑纬民.云计算：系统实例与研究现状[J].软件学报，2009，20（5） ：1337 -1348. [3]D. Romano， Data Mining Leading Edge： Insurance&Banking， InProceedings of Knowledge Discovery and Data Mining， Unicorn， BrunelUniversity， 1997. [4]刘军强，高建民，李言等.基于逆向工程的点云数据预处理技术研究.现代制造工程.2005.7： 73-75. 数据挖掘的任务是发现隐藏在数据中的模式,可以发现的模式分为两大类:描述型模式和预测型模式[2]。描述型模式是对当前数据中存在的事实做规范描述,刻画当前数据的一般特性;而预测型模式则是以时间为关键参数,对于时间序列型数据,根据其历史和当前的值预测未来的值。 关联模式是反映一个事件和其他事件之间依赖或关联的知识,其目的是为了生成部分数据的概要,寻找数据子集之间关联关系与数据之间的派生关系,即在同一事件中出现的不同项之间的相关性。如果两项或多项属性之间存在关联,那么就可以依据已知的属性值预测某一项的属性值。关联规则的挖掘可分为两步,首先是通过迭代识别所有的频繁项目集,然后再从频繁项目集中构造可信度不低于用户设定的最低值的规则。识别和挖掘所有频繁项目集是关联规则挖掘算法的核心,也是计算量最大的部分[3]。 关联规则中最典型的是购物篮分析,在关联规则的分析中有助于发现交易数据库中不同商品之间的联系,找出顾客购买的行为模式。 分类就是通过构造一个分类函数,把具有某些特征的数据项划分到某个给定的类别上。分类由模型创建和模型使用两步组成,模型创建是指通过对训练数据集的学习来建立分类模型;模型使用是指使用分类模型对测试数据和新的数据进行分类。训练数据集中的数据带有类标号,通过训练集的训练,使得使用分类函数可以把标号未知的数据正确的分类到其相应的标号中[4]。 聚类就是将数据项分组成多个类或簇,类之间的数据差别应尽可能大,类内的数据差别应尽可能小,即为“最小化类间的相似性,最大化类内的相似性”原则。与分类模式不同的是,聚类中要划分的类别是未知的,是一种不依赖于预先定义的类和带类标号的训练数据集的非监督学习,无需背景知识,其中类的数量由系统按照某种性能指标自动确定。聚类分析作为数据挖掘中的一个模块,既可以作为一个单独的工具以发现数据库中数据分布的一些深入的信息,概括出每一类的特点,又可以把注意力放在某一个特定的类上以作进一步的分析,还可以作为数据挖掘算法中其他分析算法的一个预处理步骤。 2 关联分析算法 常用的经典频繁项集挖掘算法有下面几种[5]。 2.1 Apriori算法 在关联分析中经典算法是R.Agrawal等人提出的Apriori算法,这是一种很有影响力的挖掘关联规则频繁项集的算法,探查逐级挖掘Apriori性质:频繁项集的所有非空子集都必须是频繁的。根据频繁k-项集,形成频繁(k+1)-项集候选,并扫描数据库1次,完成第k次迭代(k>1),找出完整的频繁(k+1)-项集Lk+1。 Apriori算法是最早用于解决关联规则问题的算法,也是目前数据挖掘领域里应用最广泛的算法之一。该算法的优点是简单易懂并且能够有效地产生所有关联规则,在频繁项目不多时表现出了明显优势;但是,当最小支持度低时,该算法会生成大量的候选频繁项集,可能会遇到组合爆炸的问题,另外,在判定每个候选项集支持度的时候,Apriori算法需要反复多次的遍历事务数据库,导致系统的输入输出代价过高。 2.2 Apriori-Tid算法 为了提高Apriori算法的有效性,目前已经提出了许多Apriori变形,旨在提高原算法的效率,Apriori-Tid算法就是一种Apriori变形算法。 Apriori-Tid算法仅在第1次扫描时用事务数据库D计算候选频繁项集的支持度,其它各次扫描用其上一次扫描生成的候选事务数据库D'来计算候选频繁项集的支持度。该做法可以减少对数据库的扫描次数,在一定情况下能迅速削减候选频繁项集。虽然Apriori-Tid算法进行了改进,但是仍然无法克服Apriori算法的固有缺陷,仍然存在下面的问题:可能产生大量的候选集;可能需要重复扫描数据库,通过模式匹配检查一个很大的候选集;无法对稀有信息进行分析。 3 分类算法 常用的分类算法有下面的几种[6]。 3.1 决策树方法 决策树是一种以实例为基础的归纳学习算法,在其树型结构中,每个结点表示对一个属性值的测试,其分支表示测试的结果,而树的叶结点表示类别,从决策树的根结点到叶结点的一条路径对应着一条合取规则,整个决策树对应着一组析取表达式规则。 决策树算法中最著名的是ID3和C4.5两个算法。ID3算法用信息论的知识作为基础,来计算具有最大信息增益的属性字段,然后建立一个决策树结点,再根据该属性字段的不同取值来建立分支。该方法描述简单且分类速度快,但是只对较小的数据集有效,而且抗噪性差。C4.5算法在继承ID3算法的优点的基础上对其进行了改进,用信息增益率代替信息增益来选择属性,同时在树的构造过程中对树进行剪枝避免了过拟合问题,还能够处理属性值缺少的样本,提高了抗噪能力。C4.5算法产生的分类规则仍然易于理解,准确率较高,但是在构造树的过程中,对数据集进行多次的顺序扫描和排序,导致算法的效率降低,而且C4.5仍然不适合大训练集数据。 3.2 人工神经网络 人工神经网络是多个神经元按一定规则连接构成的网络系统,通过模拟人类大脑的结构和功能完成对外部输入信息的动态响应,并将获取的知识存储在网络单元之间的连接权系数中,使网络具有很强的容错性和鲁棒性。 反向传播算法是人工神经网络中采用最多的训练方法。该算法通过对训练样本集的学习,将每次的处理结果与该样本已知类别进行比较,用所得的误差帮助完成学习,并且对每个训练样本动态的修改权值从而让网络的输出值与实际的类别的均方差最小。 神经网络的优点就是并行分布处理能力强,分类的准确度高,对噪声数据有较强的鲁棒性和容错能力,具备联想记忆的功能等。但是该方法获取的模式隐含在网络结构中,导致分类结果较难理解,网络的训练时间较长,不适于大数据量的学习。 3.3 贝叶斯分类 贝叶斯分类以统计学中的贝叶斯定理为理论基础,通过贝叶斯定理得到的后验概率来预测类成员关系的可能性,是一种具有最小错误率的概率分类方法。在计算过程中,如果假设所有变量都是条件独立的,则可以使用朴素贝叶斯分类方法,但所有变量都是条件独立的情况非常少。贝叶斯网络可以综合先验信息和样本信息,减少了定义全联合概率分布的概率数目,又避免了朴素贝叶斯分类器要求所有变量都是条件独立的不足,成为近年的主要研究方向。 4 结束语 数据挖掘是当今计算机学领域研究的一个主要热门课题,在各个领域都有广泛的应用,数据挖掘的算法对数据挖掘技术的实现起到关键的作用,也直接影响到能否把数据挖掘应用到具体的实践中。本文综合研究了数据挖掘的各种算法的优劣,为算法的改进和创新提供了基础。 参考文献 [1]王光宏,蒋平.数据挖掘综述[J].上海.同济大学学报,2004,32(2):246-252. [2]Fayyad U.Knowledge Discovery and Data Mining towards a U-inifying Framework.KDD'96Proc.2nd Intl.Conf.on Knowled-ge Discovery&Data Mining,1996. [3]邹志文,朱金伟.数据挖掘算法研究与综述[J].北京.计算机工程与设计,2005,26(9):2304-2307. [4]韩家炜.数据挖掘:概念与技术[M].北京:机械工业出版社,2001. [5]R.Agrawal,T.Imielinski,A.N.Swamy.Mining association rules between sets of items in large databases[A].Proceedings of1993ACM SIGMOD International Conference on Managem-ent of Data,Washington D.C.USA,1993:207-216. 1 关联规则挖掘算法 关联规则是通过用户给定支持度和置信度来寻找规则的过程[1]。基本思想包含2个过程: (1)发现最大频繁项目集。通过用户给定的支持度,寻找数据集中支持度大于或等于给定支持度的所有项目集,即频繁项目集,再从频繁项目集中选出所有不被其他项目包含的频繁项目集,即最大频繁项目集。 (2)生成关联规则。通过用户给定的置信度,在发现最大频繁的项目集中生成置信度大于或等于给定置信度的关联规则。 思想中支持度是数据集D中包含项目集i1的事务在数据集D上的百分比,公式如下: 式中:t是数据集D上的一个事务。置信度是指包含i1和i2的事务数与包含i1的事务数的支持度比值,公式如下: 2 分类算法 分类是根据数据集的特点构造一个分类器,利用该分类器将数据集中的数据映射到给定类别中某一类的过程。主要分类算法有k-最邻近算法、决策树分类算法和贝叶斯分类算法。 2.1 k-最邻近算法 k-最邻近算法(kNN)是一种基于距离的分类算法,距离越近,相似性越大,距离越远,相似性越小[2]。算法的基本思想是为:计算每个分类样本到待分类元组的距离,即计算相似度,选取与待分类数据相似度最大的k个数据,将待分类元组划分到这k个数据分类属性最集中的类别中。 2.2 决策树算法 决策树算法采用自上而下的方法递归构造决策树,分两个步骤:决策树生成和决策树剪枝。典型的决策树算法有ID3算法、C4.5算法等[3]。 2.2.1 决策树生成算法 决策树生成算法采用信息增益来选择能使样本最好分类的属性,信息增益的计算如下: 有n个消息,概率分布为p=(p1,p2,…,pn),则该样本S的期望信息为: 对于给定的样本si∈S,其样本总数为Si,根据类别属性值将si划分为m个子集,每个子集中所包含的样本数分别为sij(1≤j≤m),其概率分布为p=(Si1/Si,Si2/Si,…,Sim/Si)。根据公式得样本si的期望信息为I(si)=I(p)。 样本集S的熵为: 样本S的信息增益为: 算法的基本思想: (1)以代表训练样本的单个结点开始建树。 (2)如果样本S都属于同一个分类,则将该结点作为叶子结点。 (3)否则,利用公式计算各个属性的信息增益,比较计算所得的信息增益值,选取信息增益最大的属性作为根结点。 (4)递归划分选取的根结点,直到下面3个条件之一满足时结束:给定结点的所有样本属于同一分类;没有多余的属性可以用来进一步划分样本,此时采用多数表决法来创建叶节点;分支属性样本为空。 2.2.2 决策树剪枝算法 理想的决策树分为3种:叶结点数最少;叶子结点深度最小;叶结点数最少,且叶子结点的深度最小[4]。在决策树生成算法中没有考虑噪声等影响的因素,因此可能出现过度拟合现象,使分类预测性能降低,导致生成的决策树不尽理想。为了避免过度拟合,提出了决策树剪枝算法,该方法有预先剪枝和后剪枝2种。预先剪枝指在生成决策树的同时,决定是继续划分还是停止划分。预先剪枝的最大缺点是可能使树的生长过早停止,导致生成的决策树不完整,因此应用较少。后剪枝是一种先拟合后化简的方法,首先采用决策树生成算法对训练样本生成决策树,然后从树的叶子结点开始逐步向根的方向进行剪枝,具体的剪枝算法在本文不予以讨论。 2.3 贝叶斯分类 贝叶斯分类以贝叶斯定理为基础[5],贝叶斯定理是:H为某种假定,P(H)为先验概率,P(X|H)为H成立条件下X的概率,则后验概率P(H|X)为: 贝叶斯分类的原理是通过某对象的先验概率,利用贝叶斯定理计算出其后验概率,即该对象属于某一类的概率,选择具有最大后验概率的类作为该对象所属的类。 算法的基本思想: (1)根据训练样本计算分类属性的先验概率P(ci)。 (2)计算待分类数据每个非分类属性的条件概率P(x|ci)。 (3)由于各非分类属性可视为条件独立,故。 (4)利用式(6)计算ci的后验概率。 因为P(x)和P(ci)是常数,所以P(x|ci)最大,则后验概率最大,故将待分类数据划分到P(x|ci)最大的ci所在类别中。 3 聚类方法 聚类就是将数据对象分成多个簇,簇内有较高的相似性,而簇间差异很大。典型的聚类分析方法有划分方法和层次方法。 3.1 划分方法 划分方法依据数据点在几何空间的距离来判断个体间的相似度,距离越近就越相似,就越容易划分为一类。划分的原则是在同一个簇中的对象间有较高的相似性,而不同簇间差异很大。 3.1.1 k-平均算法 k-平均算法(k-means)是一种以簇内对象的均值为中心点的划分方法[6]。算法用欧氏距离来表示点到簇的距离: 算法的准则函数定义为: 算法基本思想: (1)随机地选取k个对象,每个对象代表一个簇的初始中心。 (2)根据式(7)计算剩余对象到中心点的欧氏距离,将每个对象赋给与其欧氏距离最小的簇,即最相似的簇。 (3)重新选取每个簇的中心点,即重新计算簇内各点的平均值。 (4)计算平方误差和E,循环(1),(2),(3)直到准则函数E变化不明显为止。 3.1.2 PAM算法 PAM算法是一种以簇中位置最中心的对象为中心点的划分方法[7]。中心点被称为代表对象,其他对象被称为非代表对象。算法基本思想: (1)随机地选取k个对象,每个对象代表一个簇的初始中心点。 (2)根据中心点计算每个非中心点y到中心点x的绝对距离|y-x|,将每个对象赋给与其绝对距离最小的簇,即最相似的簇。 (3)选择一个未被选过的中心点oi及oi所在簇中的一个未被选过的非中心点oh,计算oh代替oi的总代价Tcih,并记录在S中。 (4)如果S中有小于0的记录,则找出S最小,记录的非中心点,并用该非中心点代替被选择的中心点,重新组建k个划分的簇。 (5)如果S中所有的记录都大于等于0,则不再划分新的簇。 总代价为:。其中n为所有节点数;cjhi表示oj在oi被oh代替后所产生的代价。每一个oi被oh代替后,对于非中心点oj,有四种情况需要考虑(如图1~图4所示)。 (1)oj当前在oi所在簇内,但oh代替oi后,oj被划分到了中心点om所在的簇。此时。 (2)oj当前在oi所在簇内,但oh代替oi后,oj被重新划分到了中心点oh所在簇,此时cjhi=d(j,h)-d(j,i)。 (3)oj当前在中心点om所在簇内,但oh代替oi后,oj被重新划分到了中心点oh所在簇,此时cjhi=d(j,h)-d(j,m)。 (4)oj当前在中心点om所在簇内,但oh代替oi后,oj仍在中心点om所在簇,此时cjhi=0。 图中实线为oh代替oi前oj的所属关系,虚线为代替后oj的所属关系。 3.2 层次方法 层次方法是根据某种给定的条件对数据集进行层次的分解,有凝聚和分裂2种方式[8]。 凝聚采用自底向上的策略,先将每个对象作为独立的簇,然后合并各个簇,满足用户指定的终止条件时停止。凝聚方法有AGNES算法等。 分裂采用自顶向下的分类策略,先将所有对象作为一个簇,然后将该簇细分为越来越小的簇,满足用户指定的终止条件时停止。分裂方法有DIANA算法等。 3.2.1 AGNES算法 AGNES算法采用对象间的欧氏距离作为评价2个簇间距离的标准[9]。算法基本思想: (1)将每个对象作为独立的初始簇。 (2)将欧氏距离最小的2个对象所在簇进行合并,组成一个新的簇。 (3)达到用户指定的簇的数目时终止。 3.2.2 DIANA算法 DIANA算法以簇的直径和平均相异度为划分层次的标准[10]。其中,簇的直径是指簇中任意两对象间的最大欧氏距离,平均相异度指平均距离: 式中:ni是Cj中包含属性的个数;nj是Cj中包含属性的个数。算法基本思想: (1)将所有对象作为一个整体划分到同一个簇。 (2)在所有簇中挑选出簇直径最大的簇,并在该簇中选取一个与其他点平均相异度最大的点作为一个新簇,然后选取原簇中到新簇距离小于等于到原簇距离的点放入新簇中。 (3)循环(2)直到满足用户指定簇的数目为止。 4 几种算法的比较 关联规则方法主要用于对事物数据库进行数据挖掘,在商业领域使用得相对频繁一些。分类和聚类方法则用于对关系数据库进行数据挖掘,通过分析有属性描述的数据库元组来构造模型。 在实际应用过程中,不同方法有不同的优点和缺点。下面对本文提出几种算法的时间复杂度、使用范围、依赖条件、误差估计进行比较,如表1所示。 从表1可以看出,不同算法在不同应用上有各自的优缺点。如kNN算法时间复杂度最小,然而仅限于小数据集,对于数据集较大的情况,则可选用决策树和贝叶斯分类;k-平均算法对簇密集型数据有很高的效率。在实际应用中可以根据需要将几种算法结合,以达到更高的效率。 5 结 语 数据挖掘使信息处理技术从简单的数据存储转入更为高级的知识发现阶段,它正以一种全新的理念改变着人类信息管理方式。本文分析了3种数据挖掘算法的基本思想,并对不同算法进行了比较,指出了各算法的优缺点及使用范围,并展望了各算法对不同特征数据集的应用前景。 参考文献 [1]毕建新,张岐山.关联规则挖掘算法综述[J].中国工程科学,2005(15):77-79. [2]潘丽芳,杨炳儒.基于簇的k最邻近(kNN)分类算法研究[J].计算机工程与设计,2009,30(18):52-54. [3]刘佳,王新伟.一种改进的C4.5算法及实验分析[J].计算机应用与软件,2008,25(12):51-53. [4]魏红宁.决策树剪枝方法比较[J].西南交通大学学报,2005(1):36-39. [5]王国才.朴素贝叶斯分类器的研究与应用[D].重庆:重庆交通大学,2010. [6]金薇,陈慧萍.基于分层聚类的k-means算法[J].河海大学常州分校学报,2007,21(1):25-27. [7]TAN Pang-ning,STEINBACH M,KUMAR V.Introduc-tionto Data Mining[M].[S.l.]:Posts&TelecomPress,2006. [8]刘坤朋.数据挖掘中聚类算法的研究[D].长沙:长沙理工大学,2010. [9]刘畅,戴勃.基于AGNES算法的网格资源分析[J].辽宁工业大学学报,2009,29(1):62-63. 1 数据挖掘算法 数据挖掘算法的根本作用在于从大量的数据当中提取出所需要的信息。具体来说, 这些提取信息对象主要包含了半结构性数据源、非结构性数据源、结构性数据源, 比如视频、音频的数据源等。而对于数据算法, 其必须具备有 限准则、模型以搜索算法条件。 目前, 决策树法、神经网络法、统计分析法等, 即为数据挖掘的主要算法。那么, 为了让数据挖掘处理达到更加良好的效果, 即可以以新型的云数据方法进行相关的研究。就当前的情况来看, 在云数据的基础上, 基于Map Reduce分布式计算模型下的Apriori算法即是最为常见的数据挖掘算法。通过它的应用, 能够让人们更容易发现隐藏在大规模数据之中的知识信息, 从而让信息数据的应用效果得到实质性的提升。 2 Map Reduce 分布式计算模型 2.1 分类算法执行框架 在Map Reduce框架中, 无论是任何类型的分类算法, 其整个执行的过程都完全相同。具体来说, 整个运行的框架由若干个Mapper与一个Reducer组成。而针对于数据的处理 ,可以将整个处理过程划分为两个阶段, 即Map构建基本分类器阶段、Reduce集成阶段。在Map构建基本分类器阶段中,始终都是以置换抽样方式为依据的, 并且将数据集 (D) 划分为m个子集, 形成“D1, D2, …Dm”的模式, 而m值则是由用户自己所决定的。而在第Reduce集成阶段中, 针对于每一个Map任务都会通过分类算法的应用来在数据集上建立起一个基本的分类器 (Ci), 并且始终保持的状态[1]。 2.2 数据转换过程 针对Map Reduce模型而言, 无论是map函数、reduce还是execute函数, 对数据的来源要求都不高, 往往只负责处理已经输入的key/value键值, 并生成key/value键值, 而中间的结果则用在输出上。之后, 根据键值来对所有的中间结果进行排序, 使所有中间结果合并在一起。当然, 每一个键值都有自身的对应值, 而此时reduce函数则会对其进行相应的处理, 从而得出最终的输出结果。 3 数据挖掘算法在云数据平台下的实现 Apriori算法是云数据下应用最为广泛的一种数据挖掘算法。Apriori算法所使用的是频繁项集性质的先验知识, 并通过逐层搜索迭代方法的应用, 以k项集来实现对 (k+1) 项集的探索, 一直到找不到频繁k项集为止。 3.1 可行性 云计算平 台数据处 理的形式 是并行的 , 而数据存 储则是分布 的。那么 , 为了让最 终的结果 与传统算 法挖掘的 结果相同 , 就必须着 重考虑map部分的数 据传输。 那么 , 在Apriori算法的执 行过程中 , 如果想让 挖掘的准 确性得到 保障 , 数据的划 分就必须 满足以下 要求 : 首先 , 应该在原 始数据的重 多属性中 选择出合 理的主键 , 并要保证 其能够实现 对数据的 合理划分 。然而 , 在选择主 键的过程 中 , 主健值始终 都应该是 离散的或 者是可以 离散化的 , 否则将很 难把数据完 全划分开 来。一般 情况下 , 主键都能 够将数据 划分为若干个不同的类别, 而划分类别越少, 且子数据集数据量越大的属性则优先选作为主健。其次, 应该选择一个或多个属性来当做key, 然后根据key来对数据 进行科学 有效的划分 , 并且根据 数据分布 的策略来 将子数据 集传送到 相应的子数 据节点中 。通过这 样的过程 , 子数据节 点当中的 数据即会含 有相同的 键。所以 , 得出结论 “在子节点 存储能力的范围之内, 任意两个子数据节点绝对不会含有相同ke的数据项。 3.2 Apriori 算法 Map Reduce化过程及分析两个部分 , 即map、reduce。一般情况下, map、reduce节点构架的确定都是依据待挖掘数据信息和传输数据流情况来决定的[2]。那么 , Apriori算法Map Reduce化架构应该为 : 3.2.1 map 函数 “实现对大型数据集的拆分 , 并初步扫描数据 , 对频繁1项集进行计算, 将该频繁项与含频繁项的数据以及该数据出现的次数作为一条数据来传递给renuce函数。”这样的过程即是map函数的主要功能。通常情况下, map都分为两类节点,而map的节点数量则是由处理数据的实际情况所决定的, 通过对原数据库中的数据进行有效处理, 然后再综合两类ma节点的计算结果来传输至reduce节点。具体而言, map节点所具备的功能为数据分片。其根据某一个或多个属性值来实现对数据的拆分, 同时也能够根据某一类数据的特点来为其赋予一个key值, 这个key值具备了唯一性。而针对于划分策略的基本原则来说, 其应该尽可能保证数据的平均划分, 而划分之后数据集合中的数量绝不能够过多, 否则将会对reduc节点的正常工作带来极大的影响。而就具体分片 策略而言 ,其始终都应该根据实际情况来制定。所有数据都具有实际含义与语法语义的关系, 所以应该根据数据语义含义与用户希望挖掘的结果来决定到底该如何进行分片。通常情况下, 新生成的数据格式都被极为“<key,value>”, 而分片之后的数据则应该在value部分。同时, 作为nash算法中的参数, key值也将对数据应传输到哪一个reduce节点起到决定性的作用。其次, map节点2所具备的功能则是实现对长度为“1”的频繁项集的计算。其通过对数据库的扫描, 来将不同属性的不同取值存入到相应的列表之中, 并标记其出现的次数。然后再将列表传入到Green Plum平台的内部函数sum之中。sum函数的主要功能即是实现对属性相同项的累加, 并得出出现的次数和, 最终将结果输出[3]。另外 , 在对输出列表结果进行判断时, 应该对出现次数不满足阈值的项进行删除处理。最后,通过mao节点1与节点2的计算, 即能够实现对两个结果数据交集的计算, 也就是将map节点1当中所有含有频繁1-项集中的任何一项数据进行输出。显然, 通过这样的过程, 必然能够在不影响结果的前提下实现对数据传输量的减少。 3.2.2 reduce 函数 Ruduce函数不仅能够实现对数据的接受 , 并且能够从数据当中发现频繁结构。总体来说, reduce的处理过程相对较复杂。首先是对map函数输出数据的处理, 通过input函数的应用来实现对map输出数据的转换, 将其转换成便于reduce函数处理的格式。其次, 在接收input输出数据之后, reduce通常都会其传输到finalize和transition函数之中。 3.2.3 传递参数 一般情况下, input函数都负责对格式转变、数据输入输出的处 理。而在Map Reduce架构中 , 其则负责 综合、处 理doc1_map和doc2_map函数的输出参数。一般而言 , input的函数实质都为“SQL”语句。input函数在输出参数的过程中始终都应该满足以下条件, 即doc1_map输出值应该记为data; doc2_map输出值应该记为freqelement; 候选频繁项的最小支持度应该为thresholdmul; 1-频繁项最 小支持度 为threshod1, 且保证thresholdmulthreshold1 [4]。另外 , 传统的Apriori算法都要通过对原始数据库的扫描才能够实现对新生成结构的判断, 有效的判断出新生成结构是否为频繁结构。所以, 原数据库必然是不可少的部分。那么, 为了让数据传输量得到实质性的减少, input函数部分就必须每一条待输出数据进行判断, 判断是否含有频繁1项集中的元素。通过判断, 如果含有这样的元素, 则应该将其作为一条数据传递到reduce节点之中。而不含有这样的元素, 则不作处理。显然, 通过这样的处理过程, 大量的网络资源和磁盘空间的浪费现象都将得到遏制。 4 结语 要想让数据处理的效果得到实质性的提升, 就必须加强对数据挖掘算法的研究, 将用户所需的数据信息在大量数据中提取出来, 从而推动各领域的发展。就目前的情 况来看 ,作为一种新型计算方式, 云计算技术在数据挖掘中的应用明显还应该在现有基础上做更进一步的研究, 以此来不断促进数据信息应用效率的提高。 摘要：对数据挖掘算法以及Map Reduce分布式计算模型进行了简要的分析,详细地阐述了数据挖掘算法中最为常见的Apriori算法在云数据平台下的实现。 关键词：数据抽取,排序,参照完整性 由于数据表之间存在参照关系,为了遵循关系数据库参照完整性约束,在数据抽取时,被关联的数据表应当先抽取数据,也就是说在数据抽取之前,要对所有数据表进行排序,排序在前的数据表先抽取数据,排序在后的数据表后抽取数据,确保不违反参照完整性约束。 一、数据表末尾移动排序算法描述 设有N个数据表需要抽取数据,它们分别是T1,T2,T3,…,Ti-1,Ti,Ti+1,…,TN。如果Ti有关联参照表,则观察关联表排在Ti前面还是排在Ti后面,如果关联表排在Ti后面,必然影响关联抽取,则把Ti表放到整个队列的最后面,并且Ti+1至TN数据表依次向前移动一位,调整后的顺序为T1,T2,T3,…,Ti-1,Ti+1…,TN,Ti,以保证Ti的所有参照表都排在Ti的前面。依次类推,直至所有的数据表排序都调整完毕为止。 排序算法的流程图如图1所示,从i=1开始,判断Ti表是否有参照表(通过数据库中的数据字典信息来判断),如果Ti表有参照表,观察Ti表的所有参照表是否都排在Ti的前面,如果有参照表排在Ti的后面并影响关联抽取,则把数据表Ti移到队列的最后面。如果Ti表的排列顺序没有调整,则i=i+1,接下来继续分析判断Ti表,直到i=N为止。 二、数据表末尾移动算法举例 下面以表名为A、B、C、D、E的五个数据表为例说明上述数据表排序算法。下表中列出了数据表名称及其参照的数据表名称,其中两个数据表包含参照关系,A表参照了C表和D表,D表参照了E表,如表1所示。 初始化,i=1。如表1所示,i=1对应的数据表为A,数据表A参照的数据表C和D排在A的后面,根据排序算法,数据表A要调整到队列的最后面,调整后的数据表顺序为B、C、D、E、A,如表2所示。 继续,i=1。如表2所示,i=1对应的数据表为B,数据表B没有参照数据表,不需要调整其顺序,i=2。 继续,i=2。如表2所示,i=2对应的数据表为C,数据表C没有参照数据表,不需要调整其顺序,i=3。 继续,i=3。如表2所示,i=3对应的数据表为D,数据表D参照的数据表E排在数据表D的后面,根据排序算法,数据表D要调整到队列的最后面,调整后的数据表顺序为B、C、E、A、D,如表3所示。 海量数据实时处理算法设计与分析 篇6
数据挖掘算法综述 篇7
数据挖掘算法研究 篇8
数据算法 篇9
数据算法 篇10
继续,i=3。如表3所示,i=3对应的数据表为E,数据表E没有参照数据表,不需要调整其顺序,i=4。
继续,i=4。如表3所示,i=4对应的数据表为A,数据表A参照的数据表D排在A的后面,根据排序算法,数据表A要调整到队列的最后面,调整后的数据表顺序为B、C、E、D、A,如表4所示。
继续,i=4。如表4所示,i=4对应的数据表为D,数据表D参照的数据表E排在D的前面,不需要调整,i=5。
继续,i=5。i=5达到了数据表的总数,算法运行结束,排序结束,最终的数据表抽取由前到后的顺序是B、C、E、D、A,不会违反参照完整性规则。
三、数据表末尾移动算法收敛性分析
由于关系数据库中不存在循环参照关系,因此就不会因循环参照关系而出现数据表之间循环末尾移动。
如果数据表存在自参照关系,依据本算法,该数据表不会因自参照关系而移动。
在算法举例中,数据表A移动了两次,是因为这里存在传递参照关系,即数据表A参照C和D,D又参照E。也就是说,即使数据表序列中存在传递参照关系,数据表末尾移动算法执行的移动次数也是有限的。
基于数据结构的程序递归算法设计 篇11
关键词：递归；数据结构；算法实现
中图分类号：TP311.11 文献标识码：A文章编号：1007-9599 (2011) 08-0000-01
Program Recursive Algorithm Design Based on Data Structure
Yang Jun,Xiong Bicheng,Zhan Hongyun
(Jiangxi Tourism Business Vocational College,Nanchang330100,China)
Abstract:Recursive programming is an important approach,but in the teaching process has been a difficulty.From the methodological point of view of recursive program design make a systematic exposition,introduces the general recursive programming steps and methods,and how to divide and conquer and backtracking through strategies such as recursive programming.
Keywords:Recursion;Data structure;Algorithm
一、递归程序的实现策略
（一）分治。若操作对象可定义成由若干结构相同但规模更小的部分组成，则对原对象的操作可递归分解到其各组成部分上分别进行，如此递归分解直到不可再分时停止，此类求解策略称为分治。根据分治策略很容易得到相应的递归关系定义和递归边界，从而构造出具体的递归函数。
如非空的二叉树可看作为由根结点、根节点的左子树以及根结点的右子树三部分组成，每一部分又都是一颗树。如右图所示二叉树T可看作由根节点A、结点B、C构成的左子树和结点D、E、F构成的右子树组成。欲设计递归函数NodeCount（T）求二叉树T的结点总数，显然T的结点数是T的左子树结点数与T的右子树结点数之和再加1，这实际就是递归关系的定义：
int NodeCount（BiTree T）
{int n；
if（T==NULL）
n=0；
else
n=NodeCount（T->lchild）+NodeCount（T->rchild）+1；
return n；}
（二）回溯。回溯也是一种问题求解策略，通常指让计算机从某种可能的情况出发自动向前进行搜索，碰到符合的情况就输出或者保存起来，在一条路径上走到“尽头”后就回到原来的岔路口选择一条以前没有走过的路重新向前进行探测，直到找到解或者走完所有路径为止。回溯具体编程实现时通常都用递归：“向前进行搜索”对应递归调用，“尽头”对应递归边界。
比如N皇后问题。题目是说，一个N*N的国际象棋棋盘上主放置N个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上，要求输出所有可能的摆放方案。其实，题目就是要找出所有可能的合法情况，可以考虑用回溯法求解。
让计算机逐行前进，每行摆放一个棋子，若合法则前进到下一行。为此可设递归函数void NQueens（int arr[N][N]，int i）；第一个参数代表棋盘，第二个参数代表目前标号为0的行到标号为i-1的行已经各有一个棋子，且符合规则要求。递归函数第一次被调用时时形参i值应为0，函数体内递归调用语句应为NQueens（arr，i+1）。至此递归关系定义已经找到，但还有一个问题，即递归何时停止或者说计算机前进过程中如何判断是否“走到尽头”。分析可见共有两种情况：其一，当前行下完一个棋子后出现了非法情况，如同一列或同一斜线上出现了多个皇后，此时应抹掉该行所下棋子，在其右侧重新下一个棋子再重新检查；其二，当前行下完一个棋子后仍然合法，但恰巧当前行是最后一行，这实际意味着已经得到了一种合法的摆放方案，此时应输出该方案，之后抹掉该行所下棋子，在其右侧下一个棋子重新检查。由上述递归边界和递归关系定义可构造递归函数如下：
void NQueens（int arr[N][N]，int i）
{for（int j=0；j {arr[i][j]=1； if（Verify（arr，i）==0）{arr[i][j]=0；continue；} else if（i==N-1）{PrintChessBoard（arr）；arr[i][j]=0；continue；} else{NQueens（arr，i+1）；arr[i][j]=0；continue；}}} 通过上例可见，回溯法的主要特点是递归结束的条件在搜索的最后一步，关键是找到递归边界条件 二、递归存在的问题 使用递归进行程序设计思路清晰、代码简洁，但递归调用过程中，每一次发生调用系统都要将返回地址、局部变量等信息入栈保存，因此，递归程序的运行效率较低，而且递归次数过多还容易造成栈溢出。此外，尤其要避免重复递归调用的现象发生。比如求Fibnacci数列的第n项可通过递归函数实现： long f（int n） {int r； if（n==1||n==0）r=1； else r=f（n-1）+f（n-2）； return r；} 假设n=4则递归执行过程中发生的递归调用如图3所示，可见n=4时f（1）已经被重复调用了3次。在Core 2CPU T5500、内存1G的机器上进行测试，计算f（40）约需20.374秒的时间，其主要原因在于计算f（40）时f（1）会被重复调用165580141次；而计算f（50）更是需要40多分钟！ 参考文献： [1]谭浩强.C程序设计[M].北京:清华大学出版社,2005,7 [2]王晓东.计算机算法设计与分析[J].北京:电子工业出版社,2007,5 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多，激增的数据背后隐藏着许多重要的信息，人们希望对其进行高层次分析，以便更好地利用这些数据。因此，知识发现与数据挖掘在最近几年得到快速的发展。 对于关联规则算法，传统经典的关联规则Apriori算法有许多不同的改进方法。可能产生大量的候选集以及可能需要重复扫描数据库，是Apriori算法的两大缺点。针对Apriori算法的固有缺陷，需要对该算法进行改进，以满足许多不同场合的应用。 2 基本理论 笔者研究了一种有效的多层次关联规则挖掘方法，这种方法把OLAP技术和Apriori关联规则挖掘算法结合了起来，是对Apriori算法的一种改进。由于在方法中要涉及到数据仓库、OLAP、关联规则挖掘等概念，所以下面先对这些概念进行简要的介绍。 数据仓库是面向主题的、稳定的、完整的、时变性的数据集合，数据仓库为决策支持提供支持。为了进行有效的数据处理，数据仓库中的一部分必须预先计算，笔者把数据仓库中预先计算的那部分称为数据立方体。 OLAP是由数据仓库提供的，用于以多层次，多维的形式来操作数据。联机分析处理的过程就是根据数据分析的要求，从原始数据中构造各种数据立方体，并对立方体执行有关的操作，把结果返回给用户的过程。 关联规则是数据挖掘的主要技术之一，它从大量数据中的项集之间发现有趣的关联或相关联系，从而达到认识事物客观规律的技术方法。从数据库中发现强关联规则的步骤为： 1) 预处理与挖掘任务有关的数据，根据具体问题的要求对数据库进行相应的处理，从而生成规格化的数据库D。 2) 从数据库D中找到所有支持度大于最小支持度的项集，这些项集称为频繁项集。 3) 使用上一步中找到的频繁项集产生期望的规则R，这些规则必须满足最小置信度，形成输出规则R。 3 关联规则数据挖掘改进算法描述 Apriori算法是一种找频繁项集的基本算法，其基本原理是逐层搜索的迭代：频繁K项Lk集用于搜索频繁 (K+1) 项集Lk+1，如此下去，直到不能找到维度更高的频繁项集为止。尽管Apriori算法已经可以压缩候选数据项集Ck，但是对于频繁项集尤其是2维的候选数据项集产生仍然需要大量的存储空间，换句话说，就是对于2维的候选数据项集，Apriori算法的剪枝操作几乎不起任何作用;另一方面，这种空间复杂度以指数形式的增长，使得这个经典的算法的执行效率很难让人满意。Apriori算法的两大缺点就是产生大量的候选集，以及需要重复扫描数据库。 本文提出的改进算法是通过数据库和Web日志构建概念层次树，在继承Apriori算法思想的基础上，根据概念层次树来挖掘多层包括交叉层次的关联规则。[1] 简单的说，该改进算法输入的是log表和支持度阈值，输出的是多层频繁项集L。具体来讲，在对Apriori算法进行改进、进行OLAP关联规则挖掘时，可以分为三个步骤： 1) 预处理。从log表过滤出相关的信息，然后根据概念层次树，自顶向下，对数据库中的项进行编码，得到编码后的数据库D。 2) 执行改进的Apriori算法，分别找出各个层次的频繁项集。 3) 找出交叉层次的关联规则。 下面逐一进行说明设计： 3.1 预处理 输入：log表和支持度阈值; 输出：编码后的数据库D。 由于Apriori算法会产生大量的候选集，以及需要重复扫描数据库，因此对数据库log表进行相关信息的过滤预处理，具体按照以下步骤执行： 1) 从log表过滤出相关的信息，得出经过数据清洗后的log表d。 2) 根据概念层次树，自顶向下，对数据库中的项进行编码，得到编码后的数据库D。 概念层次树可以由专家给出，也可以从数据库和Web日志生成。 经过log表清洗后的表d，删除了大量无关的候选集，从而大大减少了扫描数据库的次数，同时也可以为后面的执行步骤中删去冗余的多层(后代)频繁项集。[2] 3.2 执行改进算法 输入：编码后的D，及各个层次的支持度阈值; 输出：分别找出各个层次的频繁项集。 当计算多层次事务数据库中项集的支持度时，普通的算法是按普通组合的方法计算交叉层次的支持度，这样数据挖掘的开销巨大;而改进算法在计算某项集的支持度时，按该项集所在的层次分开计算，含交叉层次的项集，采用区间支持度的方法来表示其支持度。 改进算法的基本思想是：自顶向下，逐层寻找每层的频繁项集，删去不满足阈值的项集，如果其祖先不满足最小支持度阈值，则不需要再计算它的支持度，直接删去即可。 对于每层 (设层号为i) 寻找频繁项集，均执行下面步骤： 1) 找出频繁l项集 扫描编码后的数据库D，收集每项的支持度。按支持度降序排列，删去不满足对应第i层的最小支持度的项，结果为频繁l项集，存入频繁项表L[i];同时，删去冗余的多层(后代)频繁l项集。 2) 构建Apriori算法树 a) 根节点标记为null，它的子节点为一个项前缀子树的集合，还有一个频繁项组成的头表。 b) 每个项前缀子树的节点有3个域：item-name, count, node_link。item-name记录该节点所代表的项的名字，count记录所在路径代表的交易中达到此节点的交易个数，node_link指向下一个具有同样的item-name域的节点，如果没有这样一个节点，就为null。 c) 频繁项头表的每个表项由两个域组成：item-name和node_link。node_link指向Apriori-tree中具有与该表项相同item-name域的第1个节点。 d) 创建Apriori算法树根节点，记为T，并标记为null。对于D中每个会话session，执行：选择session中的频繁项，并按L[i]中的次序排序。设排序后的频繁项表为[p|P]，其中p是第1个元素，P是剩余元素的表。调用insert_tree ([p|P]，T) 。 函数insert_tree ([p|P]，T) 的运行如下：如果T有一个子结点N，其中N.item-name=p.item-name，则将N的count域值增加1;否则，创建一个新节点N，使它的count为1，使它的父节点为T，并且使它的node_link和那些具有相同item_name域串起来。如果P非空，则递归调用insert_tree (P, N) 。 3) 递归挖掘Apriori算法树 Apriori算法树的挖掘通过调用预先设计好的子函数来实现。 在执行了改进后的算法，一方面能够在有效的找出各个层次的频繁项集的同时保证了算法的效率性，另一方面，在最低层或原始层的数据项之间，由于在计算某项集的支持度时，按该项集所在的层次分开计算，含交叉层次的项集，采用区间支持度的方法来表示其支持度，因此能够相对比较容易的找出强关联规则及多层次的挖掘规则。 3.3 找出交叉层次的关联规则 输入：各个层次的频繁项集; 输出：交叉层次的频繁项集L; 从各个层次的频繁项集中计算出交叉层次的频繁项集L，避免了在最低层或原始层的数据项之间寻找关联规则，在较高的概念层寻找关联规则不仅具有相对较高的执行效率，而且发现的强关联规则也相对更加容易，其可能提供知识也更具有普遍意义。 寻找交叉层次的关联规则的基本思想：自底向上，从最低层的频繁项集开始，计算交叉层次的频繁项集。对交叉层次的频繁项集，根据满足最小支持度阈值的概率来筛选出合适的频繁项集，删去不满足概率的项集。 由于篇幅的关系这里只对维之间关联规则挖掘的经常项目集产生方法做一具体介绍。维之间关联规则就是存在于一组维之内的相关规则。算法的整个过程也是以Apriori算法为基础。因为项目存在于不同的维中，这里通过利用数据立方体的概念分层结构来直接获取每个项目集的置信度。这个算法的输入条件是n维的数据立方体CB[d1, d2, …, dn]和所要求的最低支持度。 按某项集所在的层次分开计算频繁项集，含交叉层次的项集，采用区间支持度的方法来表示其支持度，实现了交叉层次的频繁项集L的快速计算，同时对于强关联规则的挖掘也提供了更加有效的挖掘算法，在多个概念层的项之间找有趣的关联比仅在原始层数据之间更容易，在较高的概念层发现的强关联规则可能提供普遍意义的知识。[3] 4 算法仿真 为了比较上述多层空间关联规则挖掘算法的效率，用Visual C++在内存为512MB的C4 1.7G计算机上实现了Apriori算法与本改进算法的性能比较。测试数据集共包括2个数据层各含有5个属性，每个属性泛化后有2～10个属性值，采用的元模式形如P (t, x) ∧Q (t, y) →R (t, z) ，而各层的最低支持度均为12%，最低信任均为50%。 测试了算法的随记录的增加时间的变化(时间复杂性)，将测试数据库的元组数从1000开始，逐渐递增到5000。两算法的时间复杂性数据曲线如图1所示，从图中可以发现，两个算法的时间复杂性均较好，不过随数据库规模的增大，针对Apriori算法的改进OLAP结构算法在执行时间更为迅速，而且在时间的增长上更为平缓一些，所以本论文提出的改进算法是可行的。 5 结束语 本文提出的挖掘多层关联规则算法，通过数据库和Web日志构建概念层次树，在继承Apriori算法思想的基础上，利用OLAP关联规则的结构，由概念层次树挖掘多层包括交叉层次的关联规则算法。本算法是对数据挖掘算法的必要补充，具有一定的理论意义，不仅能有效地应用于电子商务的个性化推荐，而且能方便地推广到其他有关的应用中。 参考文献 [1]王金城, 王晓琳, 庞古风.关联规则挖掘算法及其在冷轧生产中的应用[J].清华大学学报 (自然科学版) , 2007, 47 (S2) :1761-1765. [2]王文清, 乔雪峰.带有时态约束的多层次关联规则的挖掘[J].北京理工大学学报, 2003, 23 (1) :87-90. [3]Chen J P, Bian F L, Fu Z L, et al.An Imp roved Algorithm of Apriori[J].Geomatics and Inform ation Science of Wuhan University, 2003 (1) :94-99.数据算法 篇12